Есть мнение, что опытные разработчики не допускают простых ошибок. Ошибки сравнения? Разыменования нулевых ссылок? Нет, это точно не про нас… ;) Кстати, а что насчёт ошибок сортировки? Как вы уже поняли из заголовка, с этим тоже есть нюансы.
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.
