01.07.2024 02:21
SergVasiliev 24 6900 Источник

Сегодня поговорим о неочевидной особенности некоторых коллекций в .NET. Долго вокруг да около ходить не будем и начнём с задачки на самопроверку.

An enumerator remains valid as long as the collection remains unchanged

Итак, вопрос: как будут вести себя методы SetRemove и ListRemove? Для удобства продублирую код текстом; результаты начнём обсуждать сразу после листинга кода.

void SetRemove()
{
    int[] arr = { 1, 2, 3 };
    HashSet<int> set = arr.ToHashSet();

    foreach (var item in set)
    {
        set.Remove(item);
    }
}

void ListRemove()
{
    int[] arr = { 1, 2, 3 };
    List<int> list = arr.ToList();

    foreach (var item in list)
    {
        list.Remove(item);
    }
}

Самое интересное начинается при тестировании этих методов на разных фреймворках:

  • на .NET Framework и в ListRemove, и в SetRemove ожидаемо возникает исключение InvalidOperationException;

  • на современном .NET в методе ListRemove ожидаемо возникает исключение, а вот в SetRemove — нет.

И если с поведением ListRemove всё понятно, то SetRemove вызывает вопросы. Разве нет контракта на то, что итерируемая в foreach коллекция не должна изменяться?

Освежим память и посмотрим доки по HashSet<T>.GetEnumerator на learn.microsoft.com:

An enumerator remains valid as long as the collection remains unchanged. If changes are made to the collection, such as adding, modifying, or deleting elements, the enumerator is irrecoverably invalidated and the next call to MoveNext or IEnumerator.Reset throws an InvalidOperationException.

Ага, с .NET Framework сходится, а с .NET — нет.

Что ж, пойдём известным и проверенным способом — покопаемся в исходниках.

Как работает проверка на изменение коллекции?

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

Мы рассмотрим пример с List<T>, так как он чуть проще. В целом, для остальных коллекций суть та же. К HashSet<T> вернёмся немного позже.

Сама проверка работает достаточно просто:

  • коллекция хранит свою версию в поле _version;

  • методы Add, RemoveAt и им подобные эту версию изменяют;

  • метод GetEnumerator создаёт итератор, в конструкторе которого сохраняется текущая версия коллекции, а также ссылка на саму коллекцию;

  • методы MoveNext и Reset прямо или косвенно версию проверяют;

  • если версия, сохранённая в итераторе, отличается от текущей версии коллекции, значит коллекция изменилась — генерируется исключение.

Рассмотрим пример:

int[] arr = { 1, 2, 3 };
var list = arr.ToList();

foreach (var item in list)
{
    list.Remove(item);
}

Убираем сахар и явно вводим работу с итераторами — код станет примерно таким:

...
var list = arr.ToList();
var enumerator = list.GetEnumerator();

try
{
    while (enumerator.MoveNext())
    {
       int current = enumerator.Current;
       list.Remove(current);
    }
}
finally
{ ... }

Проверка версий здесь отработает так:

  • создаётся объект list; list._version — 0;

  • создаётся объект enumerator, в него записывается версия из list; list._version — 0, enumerator._version — 0;

  • вызов enumerator.MoveNext(). Версии совпадют, всё ОК;

  • вызов list.Remove() меняет версию коллекции; list._version — 1; enumerator._version — 0;

  • вызов enumerator.MoveNext() — версии не совпадают, выбрасывается исключение InvalidOperationException.

Надеюсь, стало понятнее. Теперь возвращаемся к HashSet<T>.

В чём загвоздка с HashSet.Remove?

Вернёмся к нашему примеру со множеством:

int[] arr = { 1, 2, 3 };
HashSet<int> set = arr.ToHashSet();

foreach (var item in set)
{
    set.Remove(item);
}

Мы помним, что на .NET Framework этот код работает ожидаемо и кидает исключение. Всё потому, что концепт укладывается в описанный нами алгоритм:

А что же в современном .NET?

Вот мы и нашли основную причину странного поведения: Remove не меняет версию -> в MoveNext проверка на совпадение успешно проходит -> исключение не генерируется -> в современном .NET можно изменять интегрируемый HashSet<T>.

Факт того, что версия действительно не меняется, элементарно проверяется в отладчике:

var set = new HashSet<int>();
// set._version -> 0
set.Add(62);
// set._version -> 1
set.Remove(62);
// set._version -> 1

Вернёмся к исходникам. Покопавшись в blame, можно найти интересующий нас коммит:

Видим комментарий:

Functionally, bringing over Dictionary's implementation yields a few notable changes, namely that Remove and Clear no longer invalidate enumerations. The tests have been updated accordingly.

Выходит, что такое поведение актуально и для Dictionary<TKey, TValue>, а также для метода Clear.

Поведение словаря так же легко проверяется через отладчик:

var dictionary = new Dictionary<int, string>();
// dictionary._version -> 0
dictionary.Add(0, string.Empty);
// dictionary._version -> 1
dictionary.Remove(0);
// dictionary._version -> 1

Ну и последний интересный момент: соответствующий коммит датируется 2020 годом, то есть это достаточно старые правки. Интересно, как много разработчиков знало об этих особенностях? :)

**
Что интересно лично для меня — это даже не детали реализации, а что контракт вида "итерируемые в foreach коллекции не должны меняться" теперь со звёздочкой. Да, в целом не должны, но могут. Не все, и не на всех фреймворках, но могут.

Я бы предпочёл, чтобы обсуждаемый контракт остался "as is". Кажется, использование описанных особенностей для множеств / словарей только привнесёт дополнительной неразберихи.

Что ж, поживём — увидим ¯_(ツ)_/¯

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


  1. KamushekDev
    01.07.2024 03:21
    #26990444
    +4

    Осталось понять зачем они сделали это изменение в Dictionary


    1. mayorovp
      01.07.2024 03:21
      #26990758
      +2

      Скорее всего - потому что могли. Просто в какой-то момент пришли к такой структуре Dictionary, в которой вызов Remove посреди итерации ничего не ломает.


      1. freeExec
        01.07.2024 03:21
        #26993044

        А чего он ломает в списках?


        1. troepolik
          01.07.2024 03:21
          #26994222
          +2

          При удалении все последующие элементы смещаются и дальше в зависимости от места удаления относительно текущей позиции итерации- ты можешь один и тот же элемент проитерировать 2 раза или пропустить один из элементов.


          1. mayorovp
            01.07.2024 03:21
            #26994572

            Проитерировать два раза - это при добавлении, при удалении может случиться только пропуск.


  1. CrazyElf
    01.07.2024 03:21
    #26990740

    Если очень нужно лучше всегда делать копию коллекции и итерироваться по ней уже. Но так то ещё лучше вообще без такого сценария обойтись, а сделать вычитание множеств или ещё что-то более высокоуровневое, чем удаление отдельных элементов по одному.


    1. ritorichesky_echpochmak
      01.07.2024 03:21
      #26991040
      +1

      сделать вычитание множеств или ещё что-то более высокоуровневое

      А можно пару примеров на пальцах? Кажется, в плане потребления ресурсов это не будет "ещё лучше"


      1. CrazyElf
        01.07.2024 03:21
        #26991418
        +2

        Зависит от конкретного use case. Где-то вообще будет лучше фильтрация коллекции в новую через Linq. Нужно смотреть - сколько вообще данных, какой процент предполагается удалить, и т.п.


    1. mynameco
      01.07.2024 03:21
      #26993732

      У нас в юнити борьба даже за боксинг итераторов. А тут целую копию коллекции делать. Сейчас выкручиваемся таким ужасным способом, что стыдно рассказывать. После удаления, делаем goto перед циклом, и ищем следующий элемент. При том количестве элементов и удаляемых данных, все всех устраивает.


      1. VanKrock
        01.07.2024 03:21
        #26998766

        Звучит интересно, а можете подсказать какая у вас исходная коллекция? List?


  1. aamonster
    01.07.2024 03:21
    #26990834
    +1

    Чувак, попиши на крестиках – там нарушение подобных контрактов не бросит тебе простое и понятное исключение, а приведёт к UB. И ты навсегда перестанешь полагаться на исключения в таких местах, и начнёшь использовать filter или ещё что.

    Кстати, емнип JavaScript позволяет менять коллекции во время итерации. Но я настолько привык так не делать...

    ЗЫ: В опросе не хватает варианта "мне всё равно".


    1. domix32
      01.07.2024 03:21
      #26991838

      JS в худшем случае просто бросит исключение про undefined т.к. его задача не ронять фронт никогда.

      использовать filter или ещё что

      во-во, удивляет желание людей заниматься подобным в обычных циклах.


      1. aamonster
        01.07.2024 03:21
        #26992092
        +3

        JS – это не только фронт, но и на фронте не всегда лучше "не ронять" – порой лучше упасть и дать юзеру перезагрузить страницу, чем, к примеру, испортить его данные.
        Но суть в том, что там изменение объекта во время итерации (ну, одного из видов объектов) не просто "в худшем случае бросит исключение", а абсолютно законно и ведёт себя предсказуемо: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...in#deleted_added_or_modified_properties
        Но всё равно проще так не делать, чтобы не выстрелить себе в ногу при переходе с языка на язык и чтобы тот, кто читает твой код, не должен был лезть в документацию.

        Понятно, почему так сделано в JS, понятно, почему так не сделано в C++, ну и подход .net тоже понятен (раз уж можно задёшево предупредить юзера, что он стреляет себе в ногу – почему нет?) и даже понятно, почему в текущей версии нет exception (раз уж мы не ломаем коллекцию при итерации по ней – в этом нет большого смысла).


    1. SergVasiliev Автор
      01.07.2024 03:21
      #26992058
      +1

      попиши на крестиках – там нарушение подобных контрактов не бросит тебе простое и понятное исключение, а приведёт к UB

      При чём тут плюсы вообще? В C++ одно поведение, в C# — другое. Речь вообще ни разу не шла о "полагаться на исключения". Очень сомневаюсь, что в C# / .NET кто-то пытается менять итерируемую коллекцию с расчётом на исключения — "контракт" о том, что так в принципе не надо делать.

      ЗЫ: В опросе не хватает варианта "мне всё равно".

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


      1. aamonster
        01.07.2024 03:21
        #26992114
        +1

        Так контракт вам никто не мешает соблюдать (лично я его соблюдаю даже в JS, потому как не желаю запоминать, где он есть, а где его нет: мой код должен читаться без привлечения документации). Просто больше никто не будет проверять, что вы его соблюдаете, потому что его нарушение перестало ломать данные.
        И да, C++ я привёл в качестве примера, поскольку там был ровно тот же контракт. Просто никто не следил за его выполнением, а нарушение могло сломать вам вообще всё и без всякой диагностики.


  1. aegoroff
    01.07.2024 03:21
    #26990862
    +2

    Могу предположить, что сделали это лишь для удобства, несколько странно конечно, но как есть. К примеру надо удалить из HashSet, существующие элементы по какому-либо условию, - к примеру (если хэшсет чисел), удалить все четные, которые там есть, если это строки, удалить строки удовлетворяющие каким-либо условиям. Использовать для удаления всего - глупо ибо есть метод Clear, использовать для удаления заранее известных элементов - тоже глупо, ибо итерироваться можно по этому, известному множеству.

    А вот в случае что я упомянул, иначе бы пришлось сначала найти все такие элементы, скопировав их в другую коллекцию (привет выделение памяти и дополнительный проход по элементам), и только потом, итерируясь по этой новой коллекции, поменять HashSet


    1. a-tk
      01.07.2024 03:21
      #26991264

      Очистка от элементов по какому-то критерию во время итерирования - вполне себе юз-кейс.


    1. ignorance
      01.07.2024 03:21
      #26992094

      Есть встроенная Hashset.RemoveWhere(Predicate)


      1. aegoroff
        01.07.2024 03:21
        #26992324
        +1

        public int RemoveWhere(Predicate<T> match)
{
    if (match == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    }

    Entry[]? entries = _entries;
    int numRemoved = 0;
    for (int i = 0; i < _count; i++)
    {
        ref Entry entry = ref entries![i];
        if (entry.Next >= -1)
        {
            // Cache value in case delegate removes it
            T value = entry.Value;
            if (match(value))
            {
                // Check again that remove actually removed it.
                if (Remove(value))
                {
                    numRemoved++;
                }
            }
        }
    }

    return numRemoved;
}

        так она по сути и использует то, что описано в статье


        1. ignorance
          01.07.2024 03:21
          #26992814

          Только она никак не проверяет инкремент версий, соответственно, изменение поведения Remove на ней не должно было отразиться


        1. Hallfire
          01.07.2024 03:21
          #26993712

          так она по сути и использует то, что описано в статье

          насколько я понимаю, нет
          эта функция использует цикл for для прохода по внутреннему массиву (при этом, судя по этой реализации метода Remove из внутреннего массива ничего не удаляется, а меняется значение на default(T))
          но не итератор


          1. aegoroff
            01.07.2024 03:21
            #26993752

            Не совсем так - RemoveWhere идет по списку значений, а Remove по списку бакетов, а это не совсем одно и тоже, точнее совсем разное - в один бакет может попасть несколько разных значений (если у них хэш код один), а в списке значений такое невозможно. Но собственно, ни один, ни другой метод не меняют поле _version у коллекции, изменение которого, приводит к инвалидации итератора.


            1. Hallfire
              01.07.2024 03:21
              #26993876

              а это не совсем одно и тоже, точнее совсем разное

              да, но в данном случае это не важно, т.к. речь про способ прохода по коллекции

              и то что методы не меняют поле _version будет играть роль только если использовать Remove или RemoveWhere внутри foreach (или если самостоятельно использовать итератор)

              зы

              так она по сути и использует то, что описано в статье

              я трактовал это сообщение не как

              метод RemoveWhere тоже использует внутри себя Remove

              но как

              метод RemoveWhere "пользуется" описанным в статье "багом", поэтому успешно выполняется и не падает при вызове Remove

              соотв. в предыдущем комментарии я и хотел сказать, что это не так, т.к. даже если бы в Remove менялось поле _version, то метод RemoveWhere всё так-же нормально работал бы, из-за того, что в нём не используется итератор, а значит и выкидывать исключение некому


  1. casualkex
    01.07.2024 03:21
    #27000480

    Возможно позволяют такое делать потому что элементы списка имеют порядок, а элементы словаря/сета не обязаны иметь порядка