Введение
Каждый C#-разработчик хотя бы раз писал что-то вроде:
var result = numbers.Where(x => x > 10).Select(x => x * 2).Take(5);
И почти каждый на старте карьеры удивлялся, узнав, что эта строчка ничего не вычисляет. Ни один элемент коллекции ещё не тронут, ни один предикат не вызван — вся цепочка спит. Вычисления начнутся только тогда, когда мы начнём перебирать result в foreach или вызовем .ToList().
Для многих LINQ так и остаётся чёрным ящиком: работает — и слава богу. Но за этим стоит вполне конкретный и воспроизводимый механизм — отложенные вычисления. Это подход, при котором код выполняется не в момент вызова метода, а только когда результат действительно понадобится. Это позволяет строить длинные цепочки преобразований без промежуточных коллекций, экономя память и процессорное время.
И никакой магии тут нет — в основе лежит обычная фича языка, доступная каждому: ключевое слово yield.
В этой статье мы разберём, как устроены ленивые методы LINQ изнутри. Пройдём путь от наивной реализации без yield к тому, во что он на самом деле разворачивается компилятором, а дальше соберём из таких кирпичиков мини‑библиотеку, которая объяснит, почему одни методы не требуют памяти вообще, другие буферизуют данные частично, а третьи материализуют всю последовательность целиком, прежде чем отдать хоть один элемент.
К статье приложен репозиторий с реализацией куда большего числа методов — как без yield, так и с ним, — так что если какие‑то детали захочется рассмотреть подробнее, ссылка будет в конце.
К концу статьи LINQ перестанет быть чёрным ящиком — вы будете точно знать, что происходит под капотом каждый раз, когда пишете .Where(...).Select(...).
Погружаемся в историю
Итак, представим, что мы пишем в старых версиях C#, в которых нет ни LINQ, ни ключевого слова yield. Пусть нам требуется написать статический метод Where, которому будет передаваться предикат и он лениво будет возвращать отфильтрованную последовательность.
Требования:
1) Метод не должен ничего вычислять и не должен трогать исходную последовательность в момент вызова (отложенное выполнение)
2) Метод должен возвращать объект, реализующий IEnumerable<TSource>, чтобы результат можно было передать дальше по цепочке подобных методов или перебрать в foreach
3) Сама фильтрация должна происходить оптимально по памяти: мы должны брать из исходного источника ровно столько элементов, сколько нужно, чтобы найти следующий подходящий, — и не больше. Никакого забегания вперёд и никакой промежуточной коллекции.
Приступим к реализации. На текущем этапе известно, что Where — это статический метод, который принимает IEnumerable<TSource> и предикат, а также возвращает наследника IEnumerable<TSource>. Получается, сам метод Where не составляет большого труда: мы просто проверяем, что все входные параметры не null и возвращаем WhereEnumerable<TSource>, реализующий интерфейс IEnumerable<TSource>..
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Where<TSource>( this IEnumerable<TSource> source, Func<TSource, bool> predicate) { ArgumentNullException.ThrowIfNull(source); ArgumentNullException.ThrowIfNull(predicate); return new WhereEnumerable<TSource>(source, predicate); } }
Давайте разбираться с WhereEnumerable<TSource>. Но прежде чем мы погрузимся в имплементации, давайте взглянем на сам интерфейс IEnumerable<T>:
public interface IEnumerable<out T> : IEnumerable { IEnumerator<T> GetEnumerator(); } public interface IEnumerable { IEnumerator GetEnumerator(); }
Как можно заметить, у него всего один метод, который возвращает какой-то IEnumerator<T>. Это базовый интерфейс для перечислителей в C#. Он реализует паттерн проектирования Итератор и используется для последовательного обхода элементов коллекции. Вот как он выглядит:
public interface IEnumerator<out T> : IDisposable, IEnumerator { T Current { get; } } public interface IEnumerator { object Current { get; } bool MoveNext(); void Reset(); }
Разберем из чего он состоит. Свойство Current возвращает элемент коллекции, на котором стоит перечислитель в текущий момент. Метод MoveNext() перемещает перечислитель на следующий элемент. Метод Reset() сбрасывает перечислитель в исходное положение перед первым элементом. И последний метод Dispose() из интерфейса IDisposable освобождает ресурсы, занятые итератором, если это необходимо. На последних двух методах мы не будем подробно останавливаться)
Именно IEnumerator<T> скрыт внутри конструкции foreach. Компилятор C# самостоятельно вызывает GetEnumerator() у коллекции, а затем по очереди вызывает MoveNext() и обращается к Current для каждого элемента. Это именно то поведение, которое нам и нужно.
Теперь предельно понятно, что должен делать WhereEnumerable<TSource>.
internal class WhereEnumerable<TSource>( IEnumerable<TSource> source, Func<TSource, bool> predicate) : IEnumerable<TSource> { public IEnumerator<TSource> GetEnumerator() => new WhereEnumerator<TSource>(source.GetEnumerator(), predicate); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); }
Каждый раз при вызове GetEnumerator() мы будем возвращать новый объект итератора, реализующий интерфейс IEnumerator<TSource>. Внутрь WhereEnumerator<TSource> передаем итератор исходной коллекции, которым он будет управлять, и предикат, согласно которому он будет пропускать элементы в исходной коллекции.
Переходим к самому непростому — реализации WhereEnumerator<TSource>. По факту, основная логика заключена в методе MoveNext() и поле Current. Так как в своем Where мы никак не преобразовываем элементы исходной последовательности, то отдавать мы тоже должны именно их. То есть спокойно можно писать вот так:
TSource IEnumerator<TSource>.Current => enumerator.Current; object? IEnumerator.Current => enumerator.Current;
Теперь метод MoveNext(). Как мы уже сказали выше, он перемещает перечислитель на следующий элемент. Если удалось переместить, то возвращается true, иначе false. Мы должны реализовать логику фильтрации исходной последовательности. Это значит, что мы должны двигать итератор исходной последовательности до тех пор, пока не найдем элемент, который удовлетворяет предикату. Если такой элемент найден, то возвращаем true, иначе, продолжаем итерацию. Если последовательность закончилась, возвращаем false. Получаем вот такую реализацию:
internal class WhereEnumerator<TSource>( IEnumerator<TSource> enumerator, Func<TSource, bool> predicate) : IEnumerator<TSource> { TSource IEnumerator<TSource>.Current => enumerator.Current; object? IEnumerator.Current => enumerator.Current; public bool MoveNext() { while (enumerator.MoveNext()) if (predicate(enumerator.Current)) return true; return false; } public void Reset() => enumerator.Reset(); public void Dispose() => enumerator.Dispose(); }
Готово. Мы успешно реализовали метод Where, соблюдая все поставленные требования.
Ключевое слово yield
Ради одного метода фильтрации понадобилось: класс‑обёртка, класс‑перечислитель, ручная реализация обоих интерфейсов (IEnumerable<T>/IEnumerator<T> вместе с их неявными версиями), ручное протаскивание состояния через конструкторы и реализация логики в MoveNext.
А теперь представим, что нужно реализовать не один Where, а десяток похожих методов — Select, Take, Skip, TakeWhile. Для каждого пришлось бы заново писать одну и ту же пару классов, отличающуюся только телом MoveNext(). Вся эта инфраструктура — по сути бойлерплейт, не несущий уникальной логики.
Именно от него разработчиков C# избавляет yield: он позволяет писать метод как обычный последовательный код, а всю машинерию с классом-состоянием компилятор генерирует сам.
Посмотрим, как будет выглядеть Where с использованием yield return.
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Where<TSource>( this IEnumerable<TSource> source, Func<TSource, bool> predicate) { ArgumentNullException.ThrowIfNull(source); ArgumentNullException.ThrowIfNull(predicate); return WhereIterator(source, predicate); } private static IEnumerable<TSource> WhereIterator<TSource>( this IEnumerable<TSource> source, Func<TSource, bool> predicate) { foreach (var item in source) if (predicate(item)) yield return item; } }
Вот и все! Мы сократили код приблизительно в 2 раза. Все благодаря ключевому слову yield и магии компилятора.
Что же происходит при компиляции метода с yield return? Давайте разбираться
Метод с yield return (или yield break) называется итераторным. Он обязан возвращать IEnumerable<T>, IEnumerator<T> или их необобщённые версии.
Компилятор превращает такой метод в скрытый класс — конечный автомат, реализующий сразу IEnumerable<T> и IEnumerator<T>, который и возвращается из метода. По сути, он проделывает ту же работу, что мы только что сделали руками для Where, только автоматически:
Тело метода становится телом
MoveNext().Локальные переменные и параметры превращаются в поля класса — их нужно хранить между вызовами.
Заводится скрытое поле
state, хранящее состояние, на котором мы остановились в прошлый раз, — по немуMoveNext()при каждом новом вызове понимает, откуда продолжить выполнение, а не начинает с начала.yield returnотдаёт значение черезCurrentи возвращаетtrue;yield break— сигнализирует о конце и возвращаетfalse.
Важный нюанс: тело метода не выполняется в момент вызова. Вызов лишь создаёт экземпляр автомата с переданными параметрами — как в нашей ручной реализации WhereEnumerable. Код начинает исполняться только при первом MoveNext(). Именно поэтому я и вынес цикл foreach в отдельный приватный метод WhereIrerator, так как иначе ArgumentNullException.ThrowIfNull(source) внутри метода сработает не сразу, а только при первом обращении к перечислителю.
Реализации других методов
Давайте попробуем реализовать некоторые другие методы при помощи ключевого слова yield.
Select
Тут все еще проще, чем с Where. Мы просто перебираем исходную последовательность и применяем к ней selector.
public static partial class EnumerableExtensions { public static IEnumerable<TResult> Select<TSource, TResult>( this IEnumerable<TSource> source, Func<TSource, TResult> selector) { ArgumentNullException.ThrowIfNull(source); ArgumentNullException.ThrowIfNull(selector); return SelectIterator(source, selector); } private static IEnumerable<TResult> SelectIterator<TSource, TResult>( this IEnumerable<TSource> source, Func<TSource, TResult> selector) { foreach (var item in source) yield return selector(item); } }
Take
Сначала проверяем переданное количество count, и если оно меньше или равно нулю, сразу завершаем выполнение через yield break, возвращая пустую последовательность. В противном случае начинаем обход исходного источника source с помощью обычного цикла foreach. На каждой итерации возвращаем текущий элемент и увеличиваем внутренний счётчик taken. Как только этот счётчик достигает значения count, метод вызывает yield break, прерывая дальнейший обход источника, даже если в нём остались необработанные элементы.
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Take<TSource>( this IEnumerable<TSource> source, int count) { ArgumentNullException.ThrowIfNull(source); return TakeIterator(source, count); } private static IEnumerable<TSource> TakeIterator<TSource>( this IEnumerable<TSource> source, int count) { if (count <= 0) yield break; var taken = 0; foreach (var item in source) { yield return item; ++taken; if (taken >= count) yield break; } } }
Skip
Сначала проверяем переданное значение count: если оно меньше или равно нулю, то просто проходим по всем элементам исходного источника и возвращаем каждый из них, после чего явно ставим yield break для завершения итерации. В основном же случае заводим счётчик skipped и обходим source в цикле. На каждой итерации сравниваем, достиг ли счётчик значения count: если да, мы возвращаем текущий элемент через yield return; если нет — мы просто увеличиваем счётчик на единицу и пропускаем этот элемент, ничего не возвращая.
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Skip<TSource>( this IEnumerable<TSource> source, int count) { ArgumentNullException.ThrowIfNull(source); return SkipIterator(source, count); } private static IEnumerable<TSource> SkipIterator<TSource>( this IEnumerable<TSource> source, int count) { if (count <= 0) { foreach (var item in source) yield return item; yield break; } var skipped = 0; foreach (var item in source) { if (skipped >= count) yield return item; else ++skipped; } } }
SelectMany
Метод принимает исходный источник и функцию‑селектор, которая для каждого элемента исходной коллекции возвращает новую последовательность. Будем использовать два вложенных цикла: внешний foreach будет обходить каждый элемент outerItem в источнике source, а для каждого такого элемента вызовем collectionSelector, получая внутреннюю коллекцию, которую затем будем обходить внутренним foreach, возвращая каждый её элемент через yield return.
public static partial class EnumerableExtensions { public static IEnumerable<TResult> SelectMany<TSource, TResult>( this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> collectionSelector) { ArgumentNullException.ThrowIfNull(source); ArgumentNullException.ThrowIfNull(collectionSelector); return SelectManyIterator(source, collectionSelector); } private static IEnumerable<TResult> SelectManyIterator<TSource, TResult>( this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> collectionSelector) { foreach (var outerItem in source) foreach (var innerItem in collectionSelector(outerItem)) yield return innerItem; } }
Множественный вызов методов
Давайте попробуем разобраться в работе множественного вызова ленивых методов. Рассмотрим вот такую последовательность команд:
var array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; var result = array .Where(x => x > 3) .Select(x => x * 2) .Take(5);
Как мы с вами выяснили выше, каждый из методов возвращает объект‑наследник IEnumerable<T>. То есть сначала метод Where вернет WhereEnumerable, у которого внутри будет исходный array. Затем Select вернет SelectEnumerable, у которого внутри уже будет WhereEnumerable. И Take вернет TakeEnumerable, внутри которого будет SelectEnumerable. Таким образом получаем своеобразную цепочку.
Что теперь случится, если мы захотим пробежаться по result?
foreach (var item in result) Console.WriteLine(item); // Или равносильный код IEnumerator<int> enumerator = result.GetEnumerator(); while (enumerator.MoveNext()) Console.WriteLine(enumerator.Current);
При вызове result.GetEnumerator() произойдет примерно то, что изображено на следующей картинке:
Так как каждый класс‑обертка в переменной result использует перечислитель источника, который он оборачивает, то при вызове result.GetEnumerator() запустится цепочка таких же вызовов для каждой обертки, пока в конечном итоге вызов не дойдет до исходного array, который уже почестному вернет свой ArrayEnumerator. Далее его обернут сначала в WhereEnumerator, затем в SelectEnumerator и наконец в TakeEnumerator.
При вызове enumerator.MoveNext() будет происходить абсолютно то же самое. Каждый перечислитель двигает внутренний до тех пор, пока не будет удовлетворен. Если все перечислители удовлетворены, движение останавливается и возвращается true. Это означает, что сейчас можно обратиться к Current и получить текущий элемент, на котором стоит перечислитель. Движение возобновится, когда у внешнего итератора вновь вызовется MoveNext() и будет возобновляться до тех пор, пока один из методов MoveNext() из цепочки не вернет false.
Методы с частичной буферизацией
Ленивые методы в LINQ делятся на три категории. Пока что мы рассматривали только методы без буферизации. Сейчас же мы перейдем к следующей категории — методы с частичной буферизацией. Что это означает?
Методы с частичной буферизацией — это ленивые операторы LINQ, которые в процессе обработки последовательности вынуждены сохранять в памяти некоторую вспомогательную структуру данных, но не всю входную последовательность целиком.
Далее покажу реализацию таких методов
Distinct
Требуется возвращать только уникальные элементы из последовательности. Для хранения уже встреченных элементов будем использовать HashSet. При обходе будем выдавать только те элементы, которые удалось впервые добавить в множество. Таким образом, мы фильтруем дубликаты, не сохраняя всю последовательность целиком — только уникальные значения.
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Distinct<TSource>( IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer = null) { ArgumentNullException.ThrowIfNull(source); return DistinctIterator(source, comparer); } private static IEnumerable<TSource> DistinctIterator<TSource>( IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer = null) { var set = new HashSet<TSource>(comparer); foreach (var item in source) if (set.Add(item)) yield return item; } }
Union
Метод Union работает по тому же принципу, что и Distinct, но обрабатывает две последовательности: сначала обходит first, добавляя все уникальные элементы в HashSet и выдавая их, а затем обходит second, выдавая только те элементы, которых ещё не было в множестве. Так он возвращает объединение двух коллекций без дубликатов, сохраняя в памяти только уникальные значения из обеих последовательностей.
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Union<TSource>( this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer = null) { ArgumentNullException.ThrowIfNull(first); ArgumentNullException.ThrowIfNull(second); return UnionIterator(first, second, comparer); } private static IEnumerable<TSource> UnionIterator<TSource>( this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer = null) { var set = new HashSet<TSource>(comparer); foreach (var item in first) if (set.Add(item)) yield return item; foreach (var item in second) if (set.Add(item)) yield return item; } }
Intersect
Метод Intersect создаёт HashSet из второй последовательности second, а затем обходит первую first и возвращает только те элементы, которые удалось удалить из этого множества. Так он находит пересечение двух коллекций, при этом буферизирует только вторую последовательность
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Intersect<TSource>( this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer = null) { ArgumentNullException.ThrowIfNull(first); ArgumentNullException.ThrowIfNull(second); return IntersectIterator(first, second, comparer); } private static IEnumerable<TSource> IntersectIterator<TSource>( IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer = null) { var set = new HashSet<TSource>(second, comparer); foreach (var item in first) if (set.Remove(item)) yield return item; } }
Except
Метод Except создаёт HashSet из второй последовательности second, а затем обходит первую first и пытается добавить каждый её элемент в это множество. Если элемент отсутствовал во второй коллекции, он успешно добавляется и немедленно возвращается через yield return; если же он уже присутствовал, добавление не происходит, и элемент пропускается.
public static partial class EnumerableExtensions { public static IEnumerable<TSource> Except<TSource>( this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer = null) { ArgumentNullException.ThrowIfNull(first); ArgumentNullException.ThrowIfNull(second); return ExceptIterator(first, second, comparer); } private static IEnumerable<TSource> ExceptIterator<TSource>( this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer = null) { var set = new HashSet<TSource>(second, comparer); foreach (var item in first) if (set.Add(item)) yield return item; } }
Заключение
В этой статье мы прошли путь от классификации методов LINQ до конкретной механики их работы: реализовали Where вручную, без yield, а затем увидели, во что компилятор превращает yield return и почему это избавляет нас от написания класса-состояния руками. На примерах разобрали, как ленивые методы без буферизации (Where, Select) работают в связке друг с другом, и как устроены методы с частичной буферизацией (Distinct, Except, Intersect), которые по ходу дела накапливают часть состояния, оставаясь при этом честными итераторами.
Методы с полной буферизацией — OrderBy, GroupBy, Join — заслуживают отдельного и подробного разбора, поэтому им будет посвящена вторая часть статьи.
Репозиторий с полной реализацией всех методов (и с yield, и без него): [ссылка]
Вторая часть статьи (про OrderBy, GroupBy, Join и полную буферизацию): [ссылка, появится позже]
