to the top
close form
Для получения триального ключа
заполните форму ниже
Team license
Enterprise license
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Бесплатная лицензия PVS-Studio для специалистов Microsoft MVP
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Мне интересно попробовать плагин на:
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
check circle
Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

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

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

22 Мар 2022

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

0928_OrderBy_Errors_ru/image1.png

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. В анализаторе как раз есть диагностика на тему возможного неправильного использования OrderByV3078.

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

Примеры из 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, чтобы не пропускать тематические публикации.

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

Популярные статьи по теме
Под капотом SAST: как инструменты анализа кода ищут дефекты безопасности

Дата: 26 Янв 2023

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

Сегодня речь о том, как SAST-решения ищут дефекты безопасности. Расскажу, как разные подходы к поиску потенциальных уязвимостей дополняют друг друга, зачем нужен каждый из них и как теория ложится на…
Wave Function Collapse для процедурной генерации в Unity

Дата: 24 Янв 2023

Автор: Андрей Москалёв

Wave Function Collapse – это алгоритм, c помощью которого можно реализовать генерацию чего угодно, что можно было бы описать с помощью правил или конкретным примером. В этой статье мы рассмотрим, как…
PVS-Studio научился анализировать Blazor компоненты

Дата: 10 Янв 2023

Автор: Алексей Авдеев

Всем привет. Перед вами небольшая статья о добавлении анализа Blazor компонентов в PVS-Studio. По ходу рассказа постараемся предугадать ваши немые вопросы по теме и ответить на них. Приятного прочтен…
Создание .NET библиотеки от А до Я

Дата: 05 Янв 2023

Автор: Гость

Думаете о создании .NET библиотеки, но не знаете, в какую сторону двигаться? Уже разрабатываете нечто подобное, но хочется открыть для себя что-то новое? Ищете варианты расширить автоматизацию? Не зн…
Топ-10 ошибок, найденных в C#-проектах за 2022 год

Дата: 28 Дек 2022

Автор: Никита Липилин

За 2022 год разработчики PVS-Studio написали много статей, в которых рассказали об ошибках, найденных в различных Open Source проектах. Пришло время подвести итоги и представить десяток самых интерес…

Комментарии (0)

Следующие комментарии next comments
close comment form
Unicorn with delicious cookie
Мы используем куки, чтобы пользоваться сайтом было удобно.
Хорошо