Сегодня поговорим о неочевидной особенности некоторых коллекций в .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 этот код работает ожидаемо и кидает исключение. Всё потому, что концепт укладывается в описанный нами алгоритм:
при создании HashSet<T> устанавливается версия;
при получении итератора в него тоже записывается версия;
HashSet<T>.Remove изменяет версию;
Enumerator.MoveNext проверяет совпадение версий и генерирует исключение, если версии отличаются.
А что же в современном .NET?
в HashSet<T> всё так же есть версия;
при получении итератора в него всё так же сохраняется версия;
[!] HashSet<T>.Remove больше НЕ ИЗМЕНЯЕТ версию;
Enumerator.MoveNext всё так же проверяет совпадение версий.
Вот мы и нашли основную причину странного поведения: 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". Кажется, использование описанных особенностей для множеств / словарей только привнесёт дополнительной неразберихи.
Что ж, поживём — увидим ¯_(ツ)_/¯
