Сергей Васильев

22 Мар 2022

Теги:

#CSharp

Подозрительные сортировки в Unity, ASP.NET Core и не только

22 Мар 2022

Автор: Сергей Васильев

OrderBy(...).OrderBy(...)
Примеры из open source проектов
Человеческий фактор?

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

OrderBy(...).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.

В результате сортировки получится такой порядок:

сначала идут те элементы, у которых есть провайдеры. Затем те, у которых их нет;
в этих группах элементы отсортированы по приоритету.

Возможно, ошибки здесь нет. Однако согласитесь, что последовательность вызовов OrderBy().ThenBy() читалась бы проще и вызывала меньше вопросов:

.OrderBy(s => string.IsNullOrEmpty(s.provider))
.ThenBy(s => s.priority)

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

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

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() не является 100% ошибкой, такой код сразу вызывает вопросы. Точно ли он корректен? Не должна ли использоваться последовательность OrderBy().ThenBy()?

Если в коде всё же есть ошибка, интересно порассуждать, откуда она могла взяться.

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

В общем — будьте внимательны. :)

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

Напоследок хочу спросить: сталкивались ли вы с подобным паттерном?

#CSharp