среда, 19 ноября 2014 г.

Сайд-эффект внутренней реализации List

Блог переехал. Актуальная версия поста находится по адресу: http://aakinshin.net/ru/blog/dotnet/list-version-side-effect/.


Если вы делаете foreach по некоторому List-у, то менять итерируемый лист внутри цикла крайне не рекомендуется, ведь это верный способ получить InvalidOperationException. А теперь загадка: как думаете, что случится со следующим кодом:

var list = new List<int> { 0, 1, 2 };
foreach(var x in list)
{
  if (x == 0)
  {
    for (int i = int.MinValue; i < int.MaxValue; i++)
      list[0] = 0;
    list.Add(3);
  }
  Console.WriteLine(x);
}

Правильный ответ: этот код замечательно отработает. На консоли вы увидете:

0
1
2
3

Разгадка кроется во внутренней реализации класса List (см. реализацию в MS.NET и в Mono 3.10). При итерировании наш List должен как-то следить, не поменял ли его кто-нибудь внутри очередной итерации. Для этого используется приватное поле _version. При любой операции _version увеличивается на 1. При создании Enumerator-для цикла это значение запоминается, а при каждом вызове MoveNext происходит проверка, что номер версии не поменялся. Если кто-то менял элементы коллекции, то будет брошен InvalidOperationException.

Но приведённый выше код отлично отрабатывает без всяких исключений. Как же так? Разгадка проста: для хранения _version используется тип int. А что будет, если int-переменную увеличить на 1 ровно 232 раза? Она вернётся к своему исходному значению. В примере внутренний цикл (от int.MinValue до int.MaxValue) изменяет бедный _version ровно 232-1 раз. А строчка list.Add(3) пополняет лист новым элементом и совершает финальный инкремент _version, который возвращает его к исходному значению. В результате при следующем вызове MoveNext() никто не подозревает, что мы что-то поменяли. Идеальное преступление.

Документация нам говорит, что исключение должно быть брошено, если кто-то поменял коллекцию. Так что формально данный пример иллюстрирует небольшую .NET-багу. Впрочем, особо волноваться по этому поводу не стоит: вероятность наткнуться на подобную проблему реальной жизни достаточно мала. Закладываться на такое поведение и как-то его учитывать тоже не стоит, т.к. впоследствии оно может поменяться (например, _version сделают 64-битным).

Написано по мотивам: StackOverflow: Why this code throws 'Collection was modified' and when I iterate something before it, it doesn't?