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

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

![0928_OrderBy_Errors_ru/image1.png](https://import.viva64.com/docx/blog/0928_OrderBy_Errors_ru/image1.png)

## OrderBy\(\.\.\.\)\.OrderBy\(\.\.\.\)

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

Код:

```cpp
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}");
}
```

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

```cpp
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\(\.\.\.\)_:

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

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

```cpp
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](https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.thenby?view=net-6.0) есть примечание по этому поводу: _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](https://pvs-studio.ru/ru/)\. В анализаторе как раз есть диагностика на тему возможного неправильного использования _OrderBy_ — [V3078](https://pvs-studio.ru/ru/docs/warnings/v3078/)\.

Посмотрим, что интересного удалось найти?

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

### Unity

В Unity было найдено 2 подобных места\.

**Первое место**

```cpp
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](https://github.com/Unity-Technologies/UnityCsReference/blob/9cd0206219e86ba3cbc4af8dca504237e6092694/Editor/Mono/EditorMode/MenuService.cs#L499)\.

Возможно, хотели отсортировать коллекцию _m\_Children_ сначала по ключу \(_c\.key_\), затем — по приоритету \(_c\.priority_\)\. Однако сортировка по приоритету будет выполнена на всей коллекции, а не в группах, отсортированных по ключу\. Ошибка? Посмотрим, что скажут разработчики\.

**Второе место**

```cpp
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](https://github.com/Unity-Technologies/UnityCsReference/blob/9cd0206219e86ba3cbc4af8dca504237e6092694/Modules/QuickSearch/Editor/Selectors/SearchSelector.cs#L177)\.

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

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

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

```cpp
.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\.

**Первое место**

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

[Ссылка на код на GitHub](https://github.com/dotnet/aspnetcore/blob/3b8ce2746c6835690a4e1b9c97e3a9ea43844909/src/Servers/Kestrel/shared/KnownHeaders.cs#L147)\.

**Второе место**

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

[Ссылка на код на GitHub](https://github.com/dotnet/aspnetcore/blob/3b8ce2746c6835690a4e1b9c97e3a9ea43844909/src/Servers/Kestrel/shared/KnownHeaders.cs#L216)\.

**Третье место**

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

[Ссылка на код на GitHub](https://github.com/dotnet/aspnetcore/blob/3b8ce2746c6835690a4e1b9c97e3a9ea43844909/src/Servers/Kestrel/shared/KnownHeaders.cs#L241)\.

Паттерн везде один и тот же, меняются только используемые переменные\. Все три случая я описал в [issue](https://github.com/dotnet/aspnetcore/issues/40062) на странице проекта\. 

Разработчики ответили, что в данном случае это не баг, но код исправили\. [Ссылка на коммит с исправлением](https://github.com/dotnet/aspnetcore/pull/40410/commits/4f0a8570d550056511a1a0df51cd09a42353f0b7)\.

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

### CosmosOS \(IL2CPU\)

```cpp
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](https://github.com/CosmosOS/IL2CPU/blob/a85d287fc31d73dcc8028bb39d01a1b21f040723/source/Cosmos.IL2CPU/CompilerEngine.cs#L462)\.

Здесь имеем дело со странной сортировкой по полям типа _int?_\. Я также создал [issue](https://github.com/CosmosOS/IL2CPU/issues/143) по этому поводу\. В данном случае повторная сортировка оказалась избыточной, поэтому вызов метода _OrderByDescending_ просто удалили\. Коммит можно найти [здесь](https://github.com/CosmosOS/IL2CPU/pull/144/commits/037ccd6c91555ca6be43e751fcc2620e6f4c3f4d)\.

### GrandNode

```cpp
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](https://github.com/grandnode/grandnode2/blob/45c9ee49cea2e97efc5b4035f60f583e5ad848e4/src/Core/Grand.Infrastructure/Migrations/MigrationManager.cs#L40)\.

Возможно, хотели выполнить сортировку сначала по версии, затем — по приоритету\.

Как и в предыдущих случаях, открыл [issue](https://github.com/grandnode/grandnode2/issues/237)\. В результате исправления второй вызов _OrderBy_ заменили на _ThenBy_:

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

Коммит с исправлением можно найти [здесь](https://github.com/grandnode/grandnode2/commit/e80894374940fd49953acb9f464c163c77e85f9d)\.

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

Несмотря на то, что последовательность вызовов _OrderBy\(\)\.OrderBy\(\)_ не является 100% ошибкой, такой код сразу вызывает вопросы\. Точно ли он корректен? Не должна ли использоваться последовательность _OrderBy\(\)\.ThenBy\(\)_?

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

Возможно, дело в человеческом факторе\. Мы уже знаем, что людям свойственно [ошибаться в функциях сравнения](https://pvs-studio.ru/ru/blog/posts/cpp/0509/), существует [эффект последней строки](https://pvs-studio.ru/ru/blog/posts/cpp/0260/), часто ошибки допускаются просто из\-за copy\-paste\. Возможно, двойной вызов _OrderBy_ — ещё одно проявление человеческого фактора\.

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

По доброй традиции приглашаю подписываться на [меня в Twitter](https://twitter.com/_SergVasiliev_), чтобы не пропускать тематические публикации\.

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