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

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

---

После нашего краткого визита к скалярным возвращаемым типам с Count и LongCount, мы вернулись к оператору, который возвращает последовательность: Concat.

Что это?

У Concat есть только одна сигнатура, что упрощает жизнь:

public static IEnumerable<TSource> Concat<TSource>(
    this IEnumerable<TSource> first,
    IEnumerable<TSource> second) 

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

Иногда я думаю, жаль, что не существует методов Prepend/Append, которые делали бы ту же работу, но для одного элемента – этого было бы достаточно полезно в таких ситуациях, как когда у вас есть список стран с дополнительной опцией «страна не выбрана». Довольно просто для этих целей использовать Concat, создавая массив с одним элементом, но специфические методы были бы более читабельны, я полагаю. В MoreLINQ для этих целей существуют дополнительные методы Concat, но в Edulinq предполагается реализовать только методы, которые присутствуют в LINQ to Objects.

Как всегда, некоторые заметки о поведении Concat:

• Аргументы валидируются мгновенно: они оба не должны быть null.
• Результат использует отложенное выполнение, кроме валидации. При первом вызове метода аргументы не используются.
• Каждая последовательность вычисляется только тогда, когда она должна быть вычислена. Если вы останавливаете обход конечной последовательности до того, как первая исходная последовательность исчерпалась, вторая исходная последовательность не будет затронута.

В основном, так.

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

Фактическую часть конкатенации очень просто проверить на единственном примере. Мы могли бы также продемонстрировать конкатенацию, используя пустые последовательности, но не существует причин полагать, что она провалится.

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

В итоге, существует несколько тестов для определения моментов, в которых используется каждая входная последовательность. Это достигнуто использованием ThrowingEnumerable, который мы использовали в тестах Where:

[Test]
public void FirstSequenceIsntAccessedBeforeFirstUse()
{
    IEnumerable<int> first = new ThrowingEnumerable();
    IEnumerable<int> second = new int[] { 5 };
    // Пока исключения нет... 
    var query = first.Concat(second);
    // До сих пор никакого исключения... 
    using (var iterator = query.GetEnumerator())
    {
        // Теперь оно возникнет
        Assert.Throws<InvalidOperationException>(() => iterator.MoveNext());
    }
}

[Test]
public void SecondSequenceIsntAccessedBeforeFirstUse()
{
    IEnumerable<int> first = new int[] { 5 };
    IEnumerable<int> second = new ThrowingEnumerable();
    // Пока исключения нет... 
    var query = first.Concat(second);
    // До сих пор никакого исключения... 
    using (var iterator = query.GetEnumerator())
    {
        // С первым элементом всё впрорядке... 
        Assert.IsTrue(iterator.MoveNext());
        Assert.AreEqual(5, iterator.Current);
        // Исключение возникает, как только мы переходим ко 
        // второй последовательности 
        Assert.Throws<InvalidOperationException>(() => iterator.MoveNext());
    }
}

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

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

Реализация достаточно проста, но она заставляет меня жаждать F#... это - обычное разделение между проверкой аргументов и реализацией блоков итератором, каждая часть очень проста:

public static IEnumerable<TSource> Concat<TSource>(
    this IEnumerable<TSource> first,
    IEnumerable<TSource> second)
{
    if (first == null)
    {
        throw new ArgumentNullException("first");
    }
    if (second == null)
    {
        throw new ArgumentNullException("second");
    }
    return ConcatImpl(first, second);
}

private static IEnumerable<TSource> ConcatImpl<TSource>(
    IEnumerable<TSource> first,
    IEnumerable<TSource> second)
{
    foreach (TSource item in first)
    {
        yield return item;
    }
    foreach (TSource item in second)
    {
        yield return item;
    }
}

Сейчас стоит напомнить, что было бы неприятно реализовывать это без использования блоков итераторов. Не так уж и сложно, но нам пришлось бы запоминать, по какой последовательности мы в данный момент проходим (если вообще проходим) и т.п.

Тем не менее, используя F#, мы могли бы сделать это проще при помощи выражения yield!, которое порождает целую последовательность, вместо одного элемента. Правда, для использования yield! в этом случае отсутствует существенный выигрыш в производительности (который наверняка может присутствовать в рекурсивных ситуациях), но было бы более элегантно иметь возможность порождать целые последовательности одним оператором. (Spec# имеет похожую конструкцию, которая называется вложенный итератор, и которая выражается с помощью yield foreach). Я не претендую на то, что знаю достаточно о деталях F# или Spec#, чтобы проводить более детальное сравнение, но мы увидим шаблон «получить элемент из последовательности при помощи foreach, вывести элемент при помощи yield» еще несколько раз, прежде чем мы закончим. Вспомните, что мы не можем вынести это в метод, поскольку ключевое слово «yield» требует специальной трактовки компилятором C#.

Заключение

Даже имея простую реализацию, я могу найти возможность поворчать :) Было бы неплохо, чтобы в C# присутствовали встроенные итераторы, но, если быть честным, количество раз, когда я был расстроен их отсутствием, достаточно мало.

Concat – полезный оператор, но это, на самом деле, только очень частный случай другого оператора: SelectMany. В конце концов, Concat всего лишь соединяет две последовательности в одну… тогда как SelectMany может соединять целую последовательность последовательностей, с даже большей обобщенностью, если требуется. Далее я реализую SelectMany и покажу несколько примеров, как другие операторы могут быть объединены только с помощью SelectMany. (Мы увидим подобную возможность для операторов, возвращающих единое значение, когда будет имплементировать Aggregate.)

Дополнение. Избегание хранения ссылок без надобности

В комментарии было предположено, что мы должны присваивать первой последовательности «null» после того, как мы её используем. Таким образом, как только мы закончили проход по последовательности, она становится пригодной для сборщика мусора. Это ведет к следующей реализации:

private static IEnumerable<TSource> ConcatImpl<TSource>( 
    IEnumerable<TSource> first, 
    IEnumerable<TSource> second) 
{ 
    foreach (TSource item in first) 
    { 
        yield return item; 
    } 
    // Избегаем хранения ссылки, которая нам не нужна
    first = null; 
    foreach (TSource item in second) 
    { 
        yield return item; 
    } 
}

Сейчас я бы сказал – присвоение локальной переменной значения «null», когда она не используется в оставшейся части метода, не будет иметь смысла, когда CLR запущена в оптимизированном режиме, без подключенного отладчика: сборщик мусора заботится только о переменных, к которым может быть получен доступ в оставшейся части метода.

Тем не менее, в данном случае, это имеет смысл, потому что это не обычная локальная переменная. В итоге она становится переменной экземпляра скрытого класса, сгенерированного компилятором C#... и CLR не может сказать, будет ли переменная экземпляра использоваться снова.

Возможно, мы могли бы убрать нашу единственную ссылку на «first» в начале GetEnumerator. Мы можем написать метод в виде:

public static T ReturnAndSetToNull<T>(ref T value) where T : class 
{ 
    T tmp = value; 
    value = null; 
    return tmp; 
}

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

foreach (TSource item in ReturnAndSetToNull(ref first))

Я, конечно, считаю это перебором, особенно потому что кажется очень вероятным, что итератор будет до сих пор иметь ссылку на саму коллекцию, но простая установка “first” в null после прохождения по ней, я считаю, имеет смысл.

Заметьте, я не верю, что «настоящая» реализация LINQ to Objects поступает подобным образом. (Когда-нибудь я проверю это при помощи коллекции, которая имеет финализатор.)