Как можно надурить голову себе, а затем QA на ровном месте? Тестировать не тот код, который выполняется приложением!

Это очень простая мораль, из немного более сложной истории, в которой случались моя самоуверенность, чрезмерная вера в тесты, недостаточное понимание того, как работают методы BCL. Пришлось с этим разобраться. Собственно рассказ об этом разбирательстве последует ниже.

Завязка

Положим у нас стоит задача отслеживать изменения в выписке по счету, которую можно запрашивать из банка. Интересующая нас часть выписки представляет собой коллекцию транзакций по счету, где каждая транзакция обладает следующими атрибутами:

• Идентификатор получателя транзакции (куда собственно ушли деньги, может быть не заполнен, т.е. null)

• "Номер" транзакции - это устаревшее поле, гарантируется, что поле уникально в рамках одного получателя. Может быть не заполнен (для "новых" транзакций)

• Уникальный идентификатор транзакции - глобально уникальная строка, так же может быть не заполнена.

Конечно, есть еще различные атрибуты, типа даты, суммы и т.д., но для упрощения мы их рассматривать не будем. Далее будем работать со следующей моделью транзакции:

public record Transaction(int? TargetId, string? Uid, string? Account);

Рассматриваемый сервис должен отслеживать появление новых транзакций, и оповещать пользователя о том, что добавилась новая транзакция, при этом надо учитывать некоторые особенности:

• Транзакция не может поменять получателя.

• Транзакция может пропасть из выписки

• Транзакция может появиться "задним числом" или изменить свою дату (поэтому дата транзакции не учитывается как ключевое поле)

• Произошло изменение формата: часть транзакций имеет только номер, часть имеет номер и уид, часть имеет только уид.

• При этом присвоенный уид не может пропасть

• Присвоенный номер может пропасть, но только если он был заменен на уид

В сухом остатке, задача выглядит достаточно просто: надо "вычесть" из множества транзакций текущей выписки множество транзакций предыдущей выписки и зарепортить все новые элементы. При этом сравнение транзакций проводить по некоторым нехитрым правилам. И, кажется, что для этого есть метод IEnumerable<T>.Except<T>() в linq, который принимает на вход "компаратор": объект реализующий интерфейс IEqualityComparer<T> отвечающий на вопрос равенства двух объектов типа T.

Пишем код

Сообразим незамысловатый сравниватель. Метод Equals() выглядит довольно прямолинейно:

public bool Equals(Transaction? x, Transaction? y)
{
    // null не обрабатываем, простите меня, Барбара Лисков
    if (x == null || y == null) throw new ArgumentNullException(); 
     // early exit: если получатель платежа заполнен для обоих транзакций и они не равны, то это явно разные транзакции.
    if (x.TargetId.HasValue && y.TargetId.HasValue && x.TargetId != y.TargetId) return false;
    
    // сравниваем уникальные идентификаторы, только если они оба заполнены
    if (!string.IsNullOrEmpty(x.Uid) && !string.IsNullOrEmpty(y.Uid)) 
        return string.Equals(x.Uid, y.Uid, StringComparison.OrdinalIgnoreCase);

    // то же для номеров счетов
    if (!string.IsNullOrEmpty(x.Account) && !string.IsNullOrEmpty(y.Account)) 
         return string.Equals(x.Account, y.Account, StringComparison.OrdinalIgnoreCase);
 
    return false; // ничего не сработало, значит это разные транзакции
}

Получение хэшкода сделаем также незамысловатым:

public int GetHashCode(Transaction obj) => 
    HashCode.Combine(
        obj.TargetId.GetHashCode(),
        obj.Uid?.GetHashCode(),
        obj.Account?.GetHashCode()
      );

Пока всё выглядит валидно и не видно никаких проблем. Но что за код без тестов!
Протестируем просто: подготовим (возможно с экспертами доменной области) несколько тестовых примеров, на которых прогоним следующий тест:

[Test, TestCaseSource(typeof(TestData))]
public void Equals_WhenCalled_ReturnsExpectedValue(Transaction x, Transaction y, bool expected)
{
    //arrange
    var sut = new TransactionComparer();
    
    //act & assert
    sut.Equals(x, y).Should().Be(expected);
    sut.Equals(y, x).Should().Be(expected);
}

Тестовые примеры разместим рядом:

[ExcludeFromCodeCoverage]
public class TestData : IEnumerable
{
    public IEnumerator GetEnumerator()
    {
        yield return new object[] { new Transaction(42, "uid", "account"),  new Transaction(69, "uid", "account"),  false };
        
        yield return new object[] { new Transaction(42, "uid", null),       new Transaction(42, "uid", null),       true  };
        yield return new object[] { new Transaction(42, "uid", ""),         new Transaction(42, "uid", null),       true  };
        yield return new object[] { new Transaction(42, "uid", "account"),  new Transaction(42, "uid", null),       true  };
        yield return new object[] { new Transaction(42, "uid", "acc1"),     new Transaction(42, "uid", "acc2"),     true  };
        
        yield return new object[] { new Transaction(42, "uid", null),       new Transaction(null, "uid", null),     true  };
        yield return new object[] { new Transaction(42, "uid", ""),         new Transaction(null, "uid", null),     true  };
        yield return new object[] { new Transaction(42, "uid", "account"),  new Transaction(null, "uid", null),     true  };
        yield return new object[] { new Transaction(42, "uid", "acc1"),     new Transaction(null, "uid", "acc2"),   true  };
        
        yield return new object[] { new Transaction(42, "uid", null),       new Transaction(42, "diu", null),       false  };
        yield return new object[] { new Transaction(42, "uid", ""),         new Transaction(42, "diu", null),       false  };
        yield return new object[] { new Transaction(42, "uid", "account"),  new Transaction(42, "diu", null),       false  };
        yield return new object[] { new Transaction(42, "uid", "acc1"),     new Transaction(42, "diu", "acc2"),     false  };
        
        yield return new object[] { new Transaction(42, "uid", null),       new Transaction(null, "olo", null),     false  };
        yield return new object[] { new Transaction(42, "uid", ""),         new Transaction(null, "olo", null),     false  };
        yield return new object[] { new Transaction(42, "uid", "account"),  new Transaction(null, "olo", null),     false  };
        yield return new object[] { new Transaction(42, "uid", "acc1"),     new Transaction(null, "olo", "acc2"),   false  };
        
        yield return new object[] { new Transaction(42, null, "acc"),       new Transaction(null, null, "acc"),     true   };
        yield return new object[] { new Transaction(42, "", "acc"),         new Transaction(null, null, "acc"),     true   };
        yield return new object[] { new Transaction(42, "uid", "acc"),      new Transaction(null, null, "caa"),     false  };
        yield return new object[] { new Transaction(42, "uid", "acc1"),     new Transaction(null, null, "acc1"),    true   };
        
        yield return new object[] { new Transaction(42, "uid", null),       new Transaction(42, null, "acc"),       false  };
        yield return new object[] { new Transaction(42, "uid", null),       new Transaction(null, null, "acc"),     false  };
    }
}

Чтож, этот набор тестов дает нам почти полное покрытие метода Equals (вырожденный случай сравнения с null рассматривать не будем).

Теперь можно вычесть из одной коллекции другую при помощи .Except() и идти пить чай. Или нет? Ведь тестировщики приносят примеры, когда код работает не так как ожидалось. Почему?

А что тестировали-то?

Реальный код, который использует компаратор немного отличается от тестового и выглядит примерно следующим образом:

var currentCollection = GetFromCurrentReport();
var previousCollection = _store.GetFromPreviousReport();
var diff = currentCollection.Except(previousCollection, sut);

Это немного полностью отличается от того что мы тестировали. Но кажется, что метод Equals() там все равно используется! Что же пошло не так? Прежде чем расчехлять отладчик, напишем еще один тест, работающий на тех же данных:

[Test, TestCaseSource(typeof(TestData))]
public void Except_WhenCalled_ReturnsEmptyCollection(Transaction x, Transaction y, bool isDiffEmpty)
{
    //arrange
    var sut = new TransactionComparer();
    var currentCollection = new[]{x};
    var previousCollection = new []{y};
    
    //act
    var diff = currentCollection.Except(previousCollection, sut).ToList();
    
    //assert
    if (isDiffEmpty)
        diff.Should().BeEmpty();
    else
        diff.Should().NotBeEmpty();
}

В этом тесте проверяется консистентность поведения прямого вызова метода Equals() (он уже протестирован и ему можно доверять!) с наблюдаемым эффектом от "вычитания" множеств.
И... 10 из 23 тестов не проходят!

Но кое что изменилось, теперь появилось покрытие в методе TransactionComparer.GetHashCode(). Проблема локализована, пора заглянуть под капот linq-метода Except()

Как вычитаются множества

Расчехляем декомпилятор или скачиваем символы отладки и начинаем проваливаться в реализацию Except().
Собственно сам метод проверяет входные параметры и возвращает генератор из приватного метода:

private static IEnumerable<TSource> ExceptIterator<TSource>(
    IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource> comparer)
{
    HashSet<TSource> set = new HashSet<TSource>(second, comparer);
    foreach (TSource source in first)
    {
        if (set.Add(source))
            yield return source;
    }
}

Что происходит? Из вычитаемой последовательности создается HashSet, в который в цикле напихиваются элементы левой (уменьшаемой) последовательности. Те, которые запихнуть удалось - возвращаются как элементы результирующей последовательности (их не было в вычитаемой последовательности).
We need to go deeper! Что происходит в вызове HashSet.Add()? Как хэшсет определяет новые элементы?
За полным кодом с разными хитрыми хаками можно сходить в репозиторий рантайма, рассмотрим основные пути выполнения:

private bool AddIfNotPresent(T value, out int location)
{
    /* Код всякой подготовки */
    if (comparer == null)
    {
        /* Не наш случай - comparer предоставляется */
    }
    else
    {
        hashCode = value != null ? comparer.GetHashCode(value) : 0;
        bucket = ref GetBucketRef(hashCode);
        int i = bucket - 1; // Value in _buckets is 1-based
        while (i >= 0)
        {
            ref Entry entry = ref entries[i];
            if (entry.HashCode == hashCode && comparer.Equals(entry.Value, value))
            {
                location = i;
                return false; // <<== Выход в случае, если элемент не может быть добавлен
            }
            i = entry.Next;
            collisionCount++;
            /*Обаботка конкуретного обновления коллекции*/
        }
    }
    /*
    Бла бла бла, какой то сложный код, который обрабатывает добавление элемента в хэшсет
    */
    return true; // <<== А это выход, если элемент таки удалось добавить
}

Какой вывод можно сделать из увиденного? В методе только два возможных выхода, чтобы новый элемент нельзя было добавить в хэшсет (т.к. там уже есть старый элемент) должно выполниться 2 условия:

• хэшкоды этих элементов совпадают

• метод Equals() возвращает true для этой пары.

Очевидно, что реализация GetHashCode() использованная ранее генерирует хэшкоды неконсистетно с функцией сравнения, что и приводит к тому, что некоторые "одинаковые" (по мнению Equals()) элеметы можно добавить в один хэшсет.

Исправляем баг

Перепишем функцию GetHashCode(), чтобы она всегда возвращала константу, тогда левая часть условия entry.HashCode == hashCode && comparer.Equals(entry.Value, value) всегда будет истинна, и условие будет тождественно comparer.Equals(entry.Value, value), то есть результат будет определяться только методом Equals().

public class PatchedTransactionComparer : TransactionComparer
{
    public override int GetHashCode(Transaction obj) => 0;
}

И voilà! Все тесты зеленые, баг исправлен.

Для подтверждения того что баг побежден и теперь Equals() и Except() ведут себя консистентно добавим property based тест:

[FsCheck.NUnit.Property]
public void Except_Consistent_WithEquals()
{
    var sut = new PatchedTransactionComparer();
    Prop.ForAll<Transaction, Transaction>((l, r) =>
    {
        var equals = sut.Equals(l, r);
        var diff = new[] { l }.Except(new[] { r }, sut).ToList(); 
        diff.Any().Should().Be(!equals);
    }).QuickCheckThrowOnFailure();
}

В этом тесте проверяется следующее свойство компаратора: для любой пары значений их равенство через Equals() обеспечит пустой список разности, полученный вызовом Except(), множеств состоящих из одного левого и одного правого значения соответственно; обратное тоже верно - неравенство элементов будет пораждать непустой список разности.

Тест зеленый, все работает. Работа сделана.

Tradeoff

Тут стоит задать вопрос: так если с этим GetHashCode() столько проблем, зачем оно вообще надо? Если в компараторах можно реализовать сложную и интересную логику в методе Equals(), которая будет осуществлять сравнение двух записей по различным, возможно переменным, ключам, то что дает правильная реализация хэш-кода?

Скорость. HashSet он же не просто Set, а использует хэши для поиска сравнения объектов. В худшем случае, при GetHashCode() => const добавление множества в самое себя выполняется за квадратичное время (каждый объект надо сравнить с каждым), а в оптимальном случае, когда хэшкод однозначно идентифицирует каждый экземпляр - добавление будет выполнено за линейное время (каждая запись добавляется за O(1)).

Продемонстрируем это бенчмарком с немного измененной моделью данных:

public record Data(int Group, string Key);

На которой сравним два вида компараторов:

public abstract class Comparer : IEqualityComparer<Data>
{
    public bool Equals(Data? x, Data? y)
    {
        if (x == null || y == null) return false;
        if (x.Group != y.Group)
        {
            return false;
        }

        return string.Equals(x.Key, y.Key, StringComparison.OrdinalIgnoreCase);
    }

    public abstract int GetHashCode(Data obj);
}

public class ConstHashComparer : Comparer
{
    public override int GetHashCode(Data obj) => 0;
}

public class FullKeyComparer : Comparer
{
    public override int GetHashCode(Data obj) =>
        HashCode.Combine(obj.Group.GetHashCode(), obj.Key.GetHashCode(StringComparison.OrdinalIgnoreCase));
}

Собственно код бенчмарка незамысловат. Перед стартом итерации он создаст 2 списка из случайных элементов, затем будет вычислять разность между этими множествами используя один или другой компаратор:

public class Bench
{
    private Data BuildNewData(Random rng, int keyLen)
    {
        const string alphabet = "abcdefghijklmnopqrstuwxyz0123456789";
        var sb = new StringBuilder(keyLen);
        for (int i = 0; i < keyLen; ++i)
        {
            sb.Append(alphabet[rng.Next(0, alphabet.Length-1)]);
        }

        return new(rng.Next(0, 10), sb.ToString());
    }

    private List<Data> left;
    private List<Data> right;
    private readonly ConstHashComparer _constHashComparer = new();
    private readonly FullKeyComparer _fullKeyComparer = new();
    
    [Params(100, 10_000)]
    public int LeftLen { get; set; }

    [Params(100, 10_000)]
    public int RightLen { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        var rng = new Random();
        left = new List<Data>(LeftLen);
        for(int i = 0; i<LeftLen; ++i)
            left.Add(BuildNewData(rng, 10));

        right = new List<Data>(RightLen);
        for(int i = 0; i<RightLen; ++i)
            right.Add(BuildNewData(rng, 10));
    }

    [Benchmark]
    public List<Data> ConstHashComparer() => left.Except(right, _constHashComparer).ToList();

    [Benchmark]
    public List<Data> FullKeyComparer() => left.Except(right, _fullKeyComparer).ToList();
}

Пуск, немного ожидания и вот они результаты:

// * Summary *

BenchmarkDotNet=v0.13.5, OS=ubuntu 23.04
AMD Ryzen 5 2400G with Radeon Vega Graphics, 1 CPU, 8 logical and 4 physical cores
.NET SDK=7.0.105
  [Host]     : .NET 7.0.5 (7.0.523.17801), X64 RyuJIT AVX2
  DefaultJob : .NET 7.0.5 (7.0.523.17801), X64 RyuJIT AVX2


|            Method | LeftLen | RightLen |            Mean |         Error |        StdDev |
|------------------ |-------- |--------- |----------------:|--------------:|--------------:|
| ConstHashComparer |     100 |      100 |       239.67 us |      4.559 us |      5.067 us |
|   FullKeyComparer |     100 |      100 |        12.05 us |      0.123 us |      0.109 us |
| ConstHashComparer |     100 |    10000 |   593,223.83 us | 11,283.344 us | 10,002.390 us |
|   FullKeyComparer |     100 |    10000 |       621.23 us |     11.546 us |     11.339 us |
| ConstHashComparer |   10000 |      100 |   582,710.39 us |  3,615.278 us |  3,381.733 us |
|   FullKeyComparer |   10000 |      100 |       902.72 us |      2.939 us |      2.606 us |
| ConstHashComparer |   10000 |    10000 | 2,389,666.31 us | 47,119.876 us | 56,092.861 us |
|   FullKeyComparer |   10000 |    10000 |     1,794.25 us |     33.850 us |     49.618 us |

Очевидная победа за FullKeyComparer!

Весь код доступен в демо-репозитории