«Разработчики не делают простых ошибок» на примере сортировок в Unity, ASP.NET Core и не только

Есть мнение, что опытные разработчики не допускают простых ошибок. Ошибки сравнения? Разыменования нулевых ссылок? Нет, это точно не про нас… 😉 Кстати, а что насчёт ошибок сортировки? Как вы уже поняли из заголовка, с этим тоже есть нюансы.

OrderBy(…).OrderBy(…)

Есть в C# такой паттерн ошибки — при сортировке коллекции два раза подряд вызывают метод OrderBy. Намерение разработчика простое — выполнить вторичную сортировку, сохранив результаты первичной.

Проще всего объяснить проблему на примере. Допустим, у нас есть какой-нибудь тип (Wrapper) с двумя целочисленными свойствами (Primary и Secondary). Имеется массив экземпляров этого типа, который нужно отсортировать по возрастанию, сначала по первичному ключу, затем — по вторичному.

Код:

class Wrapper {   public int Primary { get; init; }   public int Secondary { get; init; } }  var arr = new Wrapper[] {   new() { Primary = 1, Secondary = 2 },   new() { Primary = 0, Secondary = 1 },   new() { Primary = 2, Secondary = 1 },   new() { Primary = 2, Secondary = 0 },   new() { Primary = 0, Secondary = 2 },   new() { Primary = 0, Secondary = 3 }, };  var sorted = arr.OrderBy(p => p.Primary)                 .OrderBy(p => p.Secondary);  foreach (var wrapper in sorted) {   Console.WriteLine($"Primary: {wrapper.Primary}                        Secondary: {wrapper.Secondary}"); }

К сожалению, результат работы этого кода будет неправильным:

Primary: 2 Secondary: 0 Primary: 0 Secondary: 1 Primary: 2 Secondary: 1 Primary: 0 Secondary: 2 Primary: 1 Secondary: 2 Primary: 0 Secondary: 3

Последовательность оказалась отсортирована по вторичному ключу, но не по первичному. Если вы хотя бы раз использовали «многоуровневую» сортировку в C#, то уже догадались, в чём здесь подвох.

Да, повторный вызов метода OrderBy сбрасывает результат предыдущей сортировки. Правильным будет последовательность вызовов OrderBy(…).ThenBy(…):

var sorted = arr.OrderBy(p => p.Primary)                 .ThenBy(p => p.Secondary);

Тогда результат работы кода будет ожидаемым:

Primary: 0 Secondary: 1 Primary: 0 Secondary: 2 Primary: 0 Secondary: 3 Primary: 1 Secondary: 2 Primary: 2 Secondary: 0 Primary: 2 Secondary: 1

В документации на метод ThenBy на docs.microsoft.com есть примечание по этому поводу: Because IOrderedEnumerable<TElement> inherits from IEnumerable<T>, you can call OrderBy or OrderByDescending on the results of a call to OrderBy, OrderByDescending, ThenBy or ThenByDescending. Doing this introduces a new primary ordering that ignores the previously established ordering.

Так получилось, что недавно я прошёлся по C# проектам на GitHub и погонял их код через PVS-Studio. В анализаторе как раз есть диагностика на тему неправильного использования OrderBy —V3078.

И что, неужели кто-то допускает подобные ошибки? Ну, как вам сказать… 🙂

Примеры из open source проектов

Unity

В Unity было найдено сразу 2 подобные проблемы.

Первое место

private List<T> GetChildrenRecursively(bool sorted = false,                                         List<T> result = null) {   if (result == null)     result = new List<T>();    if (m_Children.Any())   {     var children        = sorted ?            (IEnumerable<MenuItemsTree<T>>)m_Children.OrderBy(c => c.key)                                                    .OrderBy(c => c.m_Priority)                 : m_Children;     ....   }   .... }

Код на GitHub.

Всё просто — хотели отсортировать коллекцию m_Children сначала по ключу (c.key), затем — по приоритету (c.priority). Однако итоговая последовательность будет отсортирована только по приоритету.

Второе место

static class SelectorManager {   public static List<SearchSelector> selectors { get; private set; }   ....   internal static void RefreshSelectors()   {     ....     selectors        = ReflectionUtils.LoadAllMethodsWithAttribute(           generator,            supportedSignatures,            ReflectionUtils.AttributeLoaderBehavior.DoNotThrowOnValidation)                        .Where(s => s.valid)                        .OrderBy(s => s.priority)                        .OrderBy(s => string.IsNullOrEmpty(s.provider))                        .ToList();   } }

Код на GitHub.

На этот раз ключом вторичной сортировки выступали провайдеры (s.provider). Но, как мы знаем, это единственный критерий, по которому будет отсортирована результирующая последовательность.

Об обеих проблемах я сообщил через Unity Bug Reporter. В результате QA командой были открыты 2 issues:

• issue #1;
• issue #2.

Комментариев по ним пока не было – ждём.

ASP.NET Core

В ASP.NET Core нашлось 3 места, где дублировались вызовы OrderBy. Все они были обнаружены в файле KnownHeaders.cs.

Первое место

RequestHeaders = commonHeaders.Concat(new[] {   HeaderNames.Authority,   HeaderNames.Method,   .... } .Concat(corsRequestHeaders) .OrderBy(header => header) .OrderBy(header => !requestPrimaryHeaders.Contains(header)) ....

Ссылка на код на GitHub.

Второе место

ResponseHeaders = commonHeaders.Concat(new[] {   HeaderNames.AcceptRanges,   HeaderNames.Age,   .... }) .Concat(corsResponseHeaders) .OrderBy(header => header) .OrderBy(header => !responsePrimaryHeaders.Contains(header)) ....

Ссылка на код на GitHub.

Третье место

ResponseTrailers = new[] {   HeaderNames.ETag,   HeaderNames.GrpcMessage,   HeaderNames.GrpcStatus } .OrderBy(header => header) .OrderBy(header => !responsePrimaryHeaders.Contains(header)) ....

Ссылка на код на GitHub.

Паттерн везде один и тот же, меняются только используемые переменные. Все три случая я описал в issue на странице проекта.

Разработчики ответили, что в данном случае это не баг, но код исправили. Ссылка на коммит с исправлением.

В любом случае подобного кода лучше избегать – он сразу вызывает вопросы.

CosmosOS (IL2CPU)

private Dictionary<MethodBase, int?> mBootEntries; private void LoadBootEntries() {   ....   mBootEntries = mBootEntries.OrderBy(e => e.Value)                              .OrderByDescending(e => e.Value.HasValue)                              .ToDictionary(e => e.Key, e => e.Value);   .... }

Ссылка на код на GitHub.

Здесь имеем дело со странной сортировкой по полям типа int?. Я также создал issue по этому поводу. В данном случае повторная сортировка оказалась избыточной, поэтому вызов метода OrderByDescending просто удалили. Коммит можно найти здесь.

GrandNode

public IEnumerable<IMigration> GetCurrentMigrations() {   var currentDbVersion = new DbVersion(int.Parse(GrandVersion.MajorVersion),                                         int.Parse(GrandVersion.MinorVersion));    return GetAllMigrations()            .Where(x => currentDbVersion.CompareTo(x.Version) >= 0)            .OrderBy(mg => mg.Version.ToString())            .OrderBy(mg => mg.Priority)            .ToList(); }

Ссылка на код на GitHub.

Хотели выполнить сортировку сначала по версии, затем — по приоритету. В итоге сортировка выполняется только по приоритету.

Как и в предыдущих случаях, открыл issue. В результате исправления второй вызов OrderBy заменили на ThenBy:

.OrderBy(mg => mg.Version.ToString()) .ThenBy(mg => mg.Priority)

Коммит с исправлением можно найти здесь.

Человеческий фактор?

Появление сложных и комплексных ошибок можно объяснить недостатком опыта. Кажется, что вызов OrderBy(…).OrderBy(…) — не из числа подобных. Откуда тогда берутся подобные проблемы?

Здесь у меня 2 теории:

• первая — всё-таки играет недостаток опыта. Если код пишет человек, который никогда с этим не сталкивался и не тестирует результаты работы. 🙂
• вторая — человеческий фактор. Мы уже знаем, что людям свойственно ошибаться в функциях сравнения, существует эффект последней строки, часто ошибки допускаются просто из-за copy-paste. Возможно, двойной вызов OrderBy — ещё одно проявление человеческого фактора.

Если от человеческого взгляда подобные проблемы могут ускользнуть, то от статического анализатора — уже маловероятно. Здорово, когда он используется в IDE или встроен в пайплайн, а ещё лучше, если используется и там, и там.

В общем — автоматизируйте поиск ошибок. 🙂

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

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Sergey Vasiliev. «Developers don’t make silly errors» by the example of sorting in Unity, ASP.NET Core, and more.