[Перевод] Джон Скит. Реализация LINQ to Objects: Часть 2 – Where

Это перевод второй части серии статей Джона Скита "Реализация LINQ to Objects". С оригинальной версией поста можно ознакомиться здесь.

---

Предупреждение: этот пост достаточно длинный. Несмотря на то, что я выбрал простой оператор для реализации, в пути мы столкнемся с несколькими исключительными случаями и важными принципами, касающимися LINQ. Это будет отчасти экспериментальный, в плане формата, пост, поскольку я стараюсь выработать наилучший способ подачи материала.

Мы собираемся реализовать выражение/метод/оператор "Where". Его достаточно просто понять в общем, но отложенное выполнение и потоковый вывод могут вызвать проблемы. Он обобщенный, но использует только один параметр типа (что, на мой взгляд, важно: чем больше параметров типа имеет метод, тем сложнее его понять в общем). О, и это стартовая точка для выражений запросов, что является бонусом.

Что это такое?

У «Where» есть 2 перегрузки:

public static IEnumerable<TSource> Where(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)

public static IEnumerable<TSource> Where(
    this IEnumerable<TSource> source,
    Func<TSource, int, bool> predicate)

Перед тем, как я расскажу, что этот код действительно делает, я укажу на пару вещей, которые будут общими для практически всех операторов LINQ, которые мы будем имплементировать:

• Это – методы расширения. Они объявляются в невложенном статическом классе высшего уровня, и первый параметр содержит модификатор «this». Они могут быть вызваны, как будто являются методами объекта типа первого параметра.
• Это – обобщенные методы. В данном случае присутствует всего лишь один параметр типа (TSource), который указывает тип последовательности, с которой мы работаем. Поэтому для, скажем, списка строк, TSource будет типа string.
• Они принимают обобщенные делегаты семейства Func<...>. Они часто определяются при помощи лямбда выражений, но также можно предоставить и делегат.
• Они работают с последовательностями, которые представлены интерфейсом IEnumerable<T>, с итератором, который представляется интерфейсом IEnumerable<T>./li>
  

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

Теперь, несколько важных деталей о поведении:

• Исходная последовательность никоим образом не модифицируется: это, к примеру, не похоже на List<T>.RemoveAll.
• Метод использует отложенное выполнение – до того момента, пока вы не попытаетесь достать элементы из конечной последовательности, элементы не начнут извлекаться из исходной последовательности.
• Несмотря на отложенное выполнение, он сразу проверит, не являются ли параметры null.
• Он возвращает результаты в потоке – ему всегда нужен только один результат в один момент времени, и он будет возвращать его, не храня на него ссылку. Это значит, что вы можете применять этот метод к последовательностям бесконечной длины (например, к последовательности случайных чисел.)
• Каждый раз, когда вы будете обходить конечную последовательность, он будет проходить по исходной последовательности точно один раз.
• Освобождение итератора конечной последовательности освободит соответствующий итератор исходной последовательности. (В случае если вы не знали, оператор foreach в C# использует блок try/finally, чтобы удостовериться, что итератор всегда освобождается, как бы ни закончился цикл).

Многие из этих деталей также будут справедливы и для большинства остальных операторов.

Перегрузка, которая принимает Func<TSource, int, bool> позволяет предикату использовать индекс внутри последовательности так же, как и значение. Индекс всегда начинается с 0, и увеличивается на 1 каждый раз вне зависимости от предыдущих результатов предиката.

Что мы собираемся тестировать?

Было бы идеально, если бы мы протестировали все вышеуказанные аспекты. Детали потокового вывода и количество обходов последовательности являются вещами, с которыми, к сожалению, сложно работать. Зная, сколько нам уже предстоит имплементировать, мы вернемся к этому позже.

Давайте взглянем на некоторые тесты. Во-первых, вот первый «позитивный» тест – мы начинаем с массивом целых чисел, и используем лямбда-выражения, чтобы включить только элементы меньше 4. (Слово «фильтр» является вездесущим, но не уместным. Гораздо проще говорит о «фильтрации» элементов, чем об их «включении», но предикат представлен в положительном смысле.)

[Test]
public void SimpleFiltering()
{
    int[] source = { 1, 3, 4, 2, 8, 1 };
    var result = source.Where(x => x < 4);
    result.AssertSequenceEqual(1, 3, 2, 1);
}

Я оставил TestExtensions из MoreLINQ, несмотря на то, что NUnit поставляется с CollectionAssert. Я считаю, что с методами расширения легче работать по трём причинам:

• Они - методы расширения, и это помогает избегать беспорядка.
• Они могут использовать массив-параметр для ожидаемого вывода, что делает тест более выразительным.
• Более понятное сообщение при провале теста.

В основном, AssertSequenceEqual делает то, что вы от него ожидаете – он проверяет, что результат (обычно представленный как переменная, на которой вы вызываете метод) совпадает с ожидаемым результатом (обычно представленный массивом-параметром).

Пока всё идет хорошо. Теперь давайте проверим валидацию аргументов:

[Test]
public void NullPredicateThrowsNullArgumentException()
{
    int[] source = { 1, 3, 7, 9, 10 };
    Func<int, bool> predicate = null;
    Assert.Throws<ArgumentNullException>(() => source.Where(predicate));
}

[Test]
public void WithIndexNullSourceThrowsNullArgumentException()
{
    IEnumerable<int> source = null;
    Assert.Throws<ArgumentNullException>(() => source.Where((x, index) => x > 5));
}

Меня не беспокоит проверка имени внутри ArgumentNullException, я тестирую то, что аргументы проверяются мгновенно. Я не перечисляю конечную последовательность – поэтому, если валидация является отложенной, тест провалится.

Последний интересный тест на данный момент также проверяет отложенное выполнение. Он использует вспомогательный класс ThrowingEnumerable. Это последовательность, которая бросает исключение InvalidOperationException, если вы когда-либо попытаетесь пройти по ней. По существу, мы хотим проверить две вещи:

• Вызов только Where не начинает процесс обхода исходной последовательности.
• Когда мы вызываем GetEnumerator() чтобы получить итератор, а потом MoveNext() на этом итераторе, мы должны начать обход не бросая исключения

Мы должны будем сделать что-то подобное для других операторов, поэтому я написал небольшой вспомогательный метод в ThrowingEnumerable:

internal static void AssertDeferred<T>(
Func<IEnumerable<int>, IEnumerable<T>> deferredFunction)
{
    ThrowingEnumerable source = new ThrowingEnumerable();
    var result = deferredFunction(source);
    using (var iterator = result.GetEnumerator())
    {
        Assert.Throws<InvalidOperationException>(() => iterator.MoveNext());
    }
}

Теперь мы можем проверить, действительно ли Where откладывает выполнение:

[Test]
public void ExecutionIsDeferred()
{
    ThrowingEnumerable.AssertDeferred(src => src.Where(x => x > 0));
}

Эти тесты работают с простой перегрузкой предиката – где предикату передается только элемент, но не индекс. Тесты, затрагивающие индекс, очень похожи.

Давайте имплементируем это!

Имея тесты, которые проходят с настоящим LINQ to Objects, пришло время имплементировать его в нашем производственном коде. Мы собираемся использовать блоки итераторов, которые были представлены в C# 2, чтобы облегчить имплементацию IEnumerable. У меня есть несколько статей, которые вы можете прочесть, если вы хотите получить более глубокие знания… или прочесть шестую главу C# in Depth (любое из изданий). Они дают нам возможность отложенного выполнения бесплатно… но это может быть как хорошо, так и плохо, в чем мы скоро убедимся.

В действительности имплементация будет выглядеть следующим образом:

// Наивная имплементация
public static IEnumerable<TSource> Where<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)
{
    foreach (TSource item in source)
    {
        if (predicate(item))
        {
            yield return item;
        }
    }
} 

Легко, не правда ли? Блоки итераторов позволяют писать код так, как мы бы его описывали: мы проходим по каждому элементу в исходной последовательности, и если предикат возвращает true для текущего элемента, мы включаем его в конечную последовательность.

Подумать только, некоторые тесты уже проходят. Теперь нам осталось добавить только валидацию аргументов. Это легко, правда? Давайте так и сделаем:

public static IEnumerable<TSource> Where<TSource>(
            this IEnumerable<TSource> source,
            Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }

    foreach (TSource item in source)
    {
        if (predicate(item))
        {
            yield return item;
        }
    }
}

Хмм. Наши тесты валидации до сих пор не проходят, и установка точки прерывания на операторе «throw» не помогает… на ней не происходит остановки. Что же не так?

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

Мы только что натолкнулись на изъян проектирования C#. Блоки итераторов в C# попросту не работают красиво, когда вы хотите разделить выполнение между «мгновенным» (обычно для валидации) и «отложенным».Вместо этого, мы должны разделить нашу имплементацию на две: нормальный метод с валидацией, который потом вызывает метод итератора для отложенной обработки:

public static IEnumerable<TSource> Where<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }
    return WhereImpl(source, predicate);
}

private static IEnumerable<TSource> WhereImpl<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)
{
    foreach (TSource item in source)
    {
        if (predicate(item))
        {
            yield return item;
        }
    }
}

Это некрасиво, но это работает: все наши безиндексные тесты проходят. Требуется небольшой шаг, чтобы имплементировать версию, использующую индексы:

public static IEnumerable<TSource> Where<TSource>(
            this IEnumerable<TSource> source,
            Func<TSource, int, bool> predicate)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }
    return WhereImpl(source, predicate);
}

private static IEnumerable<TSource> WhereImpl<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, int, bool> predicate)
{
    int index = 0;
    foreach (TSource item in source)
    {
        if (predicate(item, index))
        {
            yield return item;
        }
        index++;
    }
}

Теперь тесты зеленые, и мы закончили. Хотя подождите… мы еще не использовали имплементацию всеми возможными способами.

Выражения запросов

Ранее мы вызывали метод напрямую (хоть он и метод расширения) – но LINQ также обеспечивает нас выражениями запросов. Вот наш тест «SimpleFiltering», переписанный с их использованием:

[Test]
public void SimpleFilteringWithQueryExpression()
{
    int[] source = { 1, 3, 4, 2, 8, 1 };
    var result = from x in source
                 where x < 4
                 select x;
    result.AssertSequenceEqual(1, 3, 2, 1);
}

Это сгенерирует точно такой же код, что и наш предыдущий тест. Компилятор, в сущности, транслирует эту форму в предыдущую, оставляя условие (x < 4) в виде лямбда-выражения, позже переводя его соответствующим образом (в данном случае, в делегат). Вы можете быть удивлены, что это работает, ведь у нас пока нет метода Select… но в этом случае мы имеем «холостую» Select-проекцию; на самом деле мы не проводим никакой трансформации. Пока в запросе присутствует что-либо еще (в нашем случае - это условие «where») - компилятор эффективно опускает оператор «select», поэтому не имеет значения, имплементирован он или нет. Если бы мы изменили «select x» на «select x * 2», компиляция нашей только-Where имплементации LINQ не прошла бы.

Факт того, что выражения запросов базируются только на шаблонах типа этого, является очень мощной возможностью для расширения – так, к примеру, LINQ to Rx имплементирует только те операторы, которые актуальны в данной среде. Таким же образом, когда дело касается выражений запросов, компилятор C# ничего не «знает» о IEnumerable - поэтому полностью обособленные интерфейсы, такие, как IObservable, работают как положено.

Чему мы научились?

Многое было затронуто здесь, в обоих смыслах имплементации и основных принципов LINQ:

• LINQ to Objects основан на методах расширения, делегатах и IEnumerable<T>
• Операторы используют отложенное выполнение, где это свойственно и выдают свои данных в виде потока, где это возможно.
• Операторы не меняют источник, вместо этого они возвращают новую последовательность, которая будет содержать нужные данные.
• Выражения запросов основываются на трансляции паттернов компилятором; вы не должны имплементировать больше паттерном, чем требует соответствующее выражение запроса.
• Блоки итераторов великолепно подходят для имплементации отложенного выполнения...
• …но затрудняют валидацию аргументов

Загрузка кода

Linq-To-Objects-2.zip

Многие спрашивали меня о репозитории для кода проекта, и это имеет смысл. Я как раз сейчас создаю репозиторий; скорее всего это будет сделано до того, как я опубликую следующий пост.