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

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

---

Это будет небольшой пост, и далее, возможно, будут еще более короткие. Я считаю, что имеет смысл описывать несколько операторов в одном посте, если они действительно подобны (вспоминаются Count и LongCount). Впрочем, я в ваших руках – если вы предпочитаете более «толстые» посты, пишите в комментариях.

Этот пост будет иметь дело с оператором генерации Range.

Что это?

Range имеет единственную сигнатуру:

public static IEnumerable<int> Range(
    int start,
    int count)

В отличие от большинства методов LINQ, это – не метод расширения, а старый добрый статический метод. Он возвращает объект, который будет выдавать “count” чисел, которые начинаются со "start", и каждый раз увеличиваются на 1 – так, к примеру, вызов Enumerable.Range(6, 3) вернет сначала 6, потом 7, а потом 8.

Поскольку он не работает с исходной последовательностью, нет смысла буферизировать или выдавать в потоке исходные данные, но:

• Аргументы должны быть сразу проверены; count не может быть отрицательным, и оно не должно быть таким, чтобы любой элемент из области переполнил Int32.
• Значения будут возвращены по требованию – Range должен быть дешевым, вместо создания, скажем, массива «count» элементов и их возврата.

Как мы собираемся это тестировать?

Тестирование простого статического метода приносит нам новые проблемы с точки зрения переключения между «нормальной» реализацией LINQ и Edulinq. Это артефакт пространств имён, которые я использую – тесты находятся в Edulinq.Tests, а имплементация – в Edulinq. «Родительские» пространства имен всегда предпочтительнее, когда компилятор пытается найти тип, и они имеют приоритет перед любой из директив using – даже директивы using, которая пытается явно указать псевдонимом (alias) типа.

Решение (слегка некрасивое), которое я выбрал – включать директивы using, чтобы создавать псевдонимы, которые не могу быть разрешены иначе – в этом случае, RangeClass. Директива using будет служить псевдонимом либо System.Linq.Enumerable либо Edulinq.Enumerable. Теперь все тесты будут использовать RangeClass.Range. Также я изменил способ переключения между имплементациями – теперь у меня есть две конфигурации проекта, одна из которых определяет символ препроцессора NORMAL_LINQ, а другая – нет. Следовательно, класс RangeTest теперь содержит:

#if NORMAL_LINQ
using RangeClass = System.Linq.Enumerable;
#else
using RangeClass = Edulinq.Enumerable;
#endif

Конечно, существуют и альтернативы:

• Я бы мог переместить тесты в другое пространство имен
• Я бы мог сделать так, чтобы ссылки на проект зависели от конфигурации, так, конфигурация «нормального LINQ» не ссылалась бы на проект Edulinq, а конфигурация «реализации Edulinq» не ссылалась бы на System.Core. Дале, я бы просто мог использовать Enumerable.Range с соответствующей директивой using для условия System.Linq, которое основывается на директиве препроцессора NORMAL_LINQ, как и для других тестов.

Мне нравится второй подход, но он подразумевает изменение файла тестового проекта - Visual Studio не располагает средствами условного включения ссылок. Я могу сделать это позже… идеи приветствуются.

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

Существует не так много ситуаций, на которые можно протестировать диапазон: у меня есть только восемь тестов, и не один из них не является по-настоящему увлекательным:

• Простой правильный диапазон должен работать нормально, когда тестируется при помощи AssertSequenceEqual
• Начальное значение может быть отрицательным
• Range(Int32.MinValue, 0) является пустым диапазоном
• Range(Int32.MaxValue, 1) возвращает только Int32.MaxValue
• count не может быть отрицательным
• count может равняться 0
• start+count-1 не может превышать Int32.MaxValue (поэтому Range(Int32.MaxValue, 2) не является правильным)
• start+count-1 может быть Int32.MaxValue (поэтому Range(Int32.MaxValue, 1) является правильным)

Последние два тестируются на нескольких разных примерах каждый – с большим start и маленьким count, с маленьким start и большим count, и «достаточно большими» значениями для обоих start и count.

Обратите внимание, что у меня нет тестов на отложенное выполнение – хотя я мог бы проверить, что возвращаемое значение не имплементирует никаких других интерфейсов коллекций, было бы странно делать так. С другой стороны, у нас есть тесты, в которых задано огромное значение count – такое, что если бы что-то действительно попробовало создать коллекцию такого размера, практически наверняка потерпело бы неудачу.

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

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

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

public static IEnumerable<int> Range(int start, int count)
{
    if (count < 0)
    {
        throw new ArgumentOutOfRangeException("count");
    }
    // Преобразовываем всё в long, чтобы избежать переполнения. Существуют и другие способы 
    // проверки на переполнение, но эта делает код правильным наиболее очевидным способом.
    if ((long)start + (long)count - 1L > int.MaxValue)
    {
        throw new ArgumentOutOfRangeException("count");
    }
    return RangeImpl(start, count);
}

private static IEnumerable<int> RangeImpl(int start, int count)
{
    for (int i = 0; i < count; i++)
    {
        yield return start + i;
    }
}

Здесь есть несколько моментов:

• Возможно, это комбинация «start» и «count» является неправильной во второй проверке, а не только count. Было бы неплохо позволить ArgumentOutOfRangeException (либо ArgumentException в общем) винить несколько аргументов, а не один из них. Как бы ни было, использование «count» совпадает с оригинальной имплементацией фреймворка.
• Есть другие способы выполнения второй проверки, и я точно не был обязан делать все операнды выражения типа long. Несмотря на это, я считаю, что это самый простой код, просто и понятно основанный на документации. Я не обязан думать обо всех возможных ситуациях и проверять, что все они работают. Арифметика будет корректной, если использовать диапазон значений Int64, поэтому я не хочу беспокоиться о переполнении, и я не должен решать, когда использовать checked или unchecked контекст.
• Существуют другие способы организации циклов в приватном методе блока итератора, но я считаю этот самым простым. Другой очевидной и простой альтернативой является хранение двух значений: одного для количества выведенных значений, и другого для следующего значения, которое следует вывести, и увеличение их на каждой итерации. Более сложным подходом может являться использование всего лишь одной переменной цикла – но вы не можете использовать «value < start + count» в случае, если конечное значение равно Int32.MaxValue, и вы не можете использовать «value <= start + count - 1» в случае, когда аргументы равны (int.MinValue, 0). Вместо того чтобы учитывать все крайние случаи, я пошел методом очевидно правильного решения. Если бы вас действительно, действительно беспокоила производительность Range, вы бы захотели исследовать многие другие случаи.

До написания этого поста у меня не было хороших тестов для Range(Int32.MaxValue, 1) и Range(Int32.MinValue, 0)… но поскольку они могли с легкостью провалиться, о чем писалось выше, я их добавил. Я нахожу интересным то, как рассмотрение альтернативных реализаций подсказывает дополнительные тесты.

Заключение

Реализация метода Range оказалась полезна для тестирования некоторых других операторов, таких как Count. Теперь, когда я затронул методы, не являющиеся методами расширения, я так же могу сделать остальные два (Empty и Repeat). Я уже имплементировал Empty и надеюсь написать о нём сегодня. «Repeat» не должен занять больше времени, а потом мы сможем перейти к Count и LongCount.

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