Обзор всех вариантов итераторов

— 2025-02-12 Yoshua Wuyts Источник

  • введение
  • базовый итератор
  • ограниченный итератор
  • объединённый итератор
  • потокобезопасный итератор
  • dyn-совместимый итератор
  • двусторонний итератор
  • позиционируемый итератор
  • итератор времени компиляции
  • заимствующий итератор
  • итератор с возвращаемым значением
  • итератор с аргументом в next
  • итератор с досрочным завершением
  • чувствительный к адресу итератор
  • итератор с гарантированным разрушением
  • асинхронный итератор
  • конкурентный итератор
  • заключение

Введение

О да, тебе нравятся итераторы? Назови их все. —

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

В Rust трейт Iterator — самый сложный трейт в стандартной библиотеке. Он предоставляет 76 методов и, по моим оценкам (я остановился на 120), имеет около 150 реализаций трейтов только в стандартной библиотеке. Он также включает широкий спектр трейтов-расширений, таких как FusedIterator и ExactSizeIterator, которые предоставляют дополнительные возможности. И сам по себе он является трейтовым выражением одного из основных эффектов управления потоком в Rust; то есть он находится в центре многих интересных вопросов о том, как мы комбинируем такие эффекты.

Несмотря на всё это, мы знаем, что трейт Iterator сегодня недостаточен, и мы хотели бы расширить его возможности. Асинхронная итерация — одна из популярных возможностей, которых не хватает в качестве встроенной. Другая — возможность создавать чувствительные к адресу (самоссылающиеся) итераторы. Менее модные, но не менее важные — итераторы, которые могут заимствовать элементы с временем жизни, условно завершаться досрочно и принимать внешние аргументы при каждом вызове next.

Я пишу этот пост, чтобы перечислить все варианты итераторов, используемые сегодня в Rust. Чтобы мы могли определить границы пространства проблем, учитывая все из них. Я также делаю это, потому что начал слышать разговоры о возможном (мягком) устаревании Iterator. Я считаю, что у нас есть только один шанс провести такое устаревание1, и если мы собираемся это сделать, нужно убедиться, что это решение, которое, вероятно, позволит нам преодолеть все наши известные ограничения. Не только одно или два.

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

Базовый итератор

Iterator — это трейт, представляющий состояние компонента итерации; IntoIterator представляет способность типа быть итерируемым. Вот трейт Iterator, каким он есть сегодня в стандартной библиотеке. Трейты Iterator и IntoIterator тесно связаны, поэтому на протяжении всего поста мы будем показывать оба, чтобы получить более полную картину.

На протяжении этого поста мы будем рассматривать варианты Iterator, которые предоставляют новые возможности. Этот трейт представляет отсутствие этих возможностей: он блокирующий, не может быть вычислен во время компиляции, строго последовательный и так далее. Вот как сегодня выглядит основа подмодуля core::iter:

#![allow(unused)]
fn main() {
/// Итерируемый тип.
pub trait IntoIterator {
    /// Тип элементов, выдаваемых итератором.
    type Item;
    /// В какой вид итератора мы превращаем этот тип?
    type IntoIter: Iterator<Item = Self::Item>;
    /// Возвращает итератор по элементам этого типа.
    fn into_iter(self) -> Self::IntoIter;
}

/// Тип, который выдаёт значения одно за другим.
pub trait Iterator {
    /// Тип элементов, выдаваемых итератором.
    type Item;
    /// Продвигает итератор и выдаёт следующее значение.
    fn next(&mut self) -> Option<Self::Item>;
    /// Возвращает границы оставшейся длины итератора.
    fn size_hint(&self) -> (usize, Option<usize>) { .. }
}
}

Хотя это не строго необходимо: ассоциированный тип IntoIterator::Item существует для удобства. Таким образом, люди, использующие трейт, могут напрямую указать Item с помощью impl IntoIterator<Item = Foo>, что намного удобнее, чем I: <IntoIterator::IntoIter as Iterator>::Item и т.д.

Ограниченный итератор

Базовый трейт Iterator представляет потенциально бесконечную (неограниченную) последовательность элементов. У него есть метод size_hint, который возвращает, сколько элементов итератор ещё ожидает выдать. Однако это значение не гарантированно является правильным и предназначено только для оптимизаций. Из документации:

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

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

Стандартная библиотека Rust предоставляет два подтрейта Iterator, которые позволяют гарантировать его ограниченность: ExactSizeIterator (стабильный) и TrustedLen (нестабильный). Оба трейта принимают : Iterator в качестве супертрейта и на поверхности кажутся почти идентичными. Но есть одно ключевое отличие: TrustedLen является unsafe для реализации, что позволяет использовать его для гарантии инвариантов безопасности.

#![allow(unused)]
fn main() {
/// Итератор, который знает свою точную длину.
pub trait ExactSizeIterator: Iterator {
    /// Возвращает точную оставшуюся длину итератора.
    fn len(&self) -> usize { .. }
    /// Возвращает `true`, если итератор пуст.
    fn is_empty(&self) -> bool { .. }
}

/// Итератор, который сообщает точную длину с помощью `size_hint`.
#[unstable(feature = "trusted_len")]
pub unsafe trait TrustedLen: Iterator {}
}

ExactSizeIterator имеет те же гарантии безопасности памяти, что и Iterator::size_hint, то есть: на него нельзя полагаться как на правильный. Это означает, что если вы, скажем, собираете элементы из итератора в вектор, вы не можете опустить проверки границ и использовать ExactSizeIterator::len в качестве аргумента для Vec::set_len. Однако если реализован TrustedLen, проверки границ можно опустить, поскольку значение, возвращаемое size_hint, теперь является инвариантом безопасности итератора.

Объединённый итератор

При работе с итератором мы обычно перебираем элементы, пока итератор не вернёт None, после чего считаем итератор «завершённым». Однако документация для Iterator::next включает следующее:

Возвращает None, когда итерация завершена. Отдельные реализации итераторов могут возобновить итерацию, поэтому повторный вызов next() может или не может снова начать возвращать Some(Item) в какой-то момент.

Редко приходится работать с итераторами, которые возвращают None, а затем снова возобновляют работу, но трейт Iterator явно это позволяет. Так же как он позволяет итератору паниковать, если next вызывается снова после того, как None был возвращён один раз. К счастью, существует подтрейт FusedIterator, который гарантирует, что после того, как None был возвращён один раз из итератора, все последующие вызовы next продолжат возвращать None.

#![allow(unused)]
fn main() {
/// Итератор, который всегда продолжает возвращать `None` после исчерпания.
pub trait FusedIterator: Iterator {}
}

Большинство итераторов в стандартной библиотеке реализуют FusedIterator. Для итераторов, которые не являются объединёнными, можно вызвать комбинатор Iterator::fuse. Документация стандартной библиотеки рекомендует никогда не использовать ограничение FusedIterator, отдавая предпочтение Iterator в ограничениях и вызову fuse для гарантии объединённого поведения. Для итераторов, которые уже реализуют FusedIterator, это считается отсутствием операции.

Дизайн FusedIterator работает, потому что Option::None идемпотентен: никогда не возникает ситуации, когда мы не можем создать новый экземпляр None. Сравните это с перечислениями, такими как Poll, у которых отсутствует состояние «завершено», — и вы увидите, что экосистемные трейты, такие как FusedFuture, пытаются вернуть эту недостающую выразительность другими способами. Необходимость идемпотентного состояния «завершено» важно помнить по мере изучения других вариантов итераторов в этом посте.

Потокобезопасный итератор

В то время как ограниченные и объединённые итераторы можно получить, уточнив трейт Iterator с помощью подтрейтов, потокобезопасные итераторы получаются путём композиции автотрейтов Send и Sync с трейтом Iterator. Это означает, что нет необходимости в специальных трейтах SendIterator или SyncIterator. «Потокобезопасный итератор» становится композицией Iterator и Send / Sync:

#![allow(unused)]
fn main() {
struct Cat;

// Ручная реализация `Iterator`
impl Iterator for Cat { .. }

// Эти реализации подразумеваются тем,
// что `Send` и `Sync` являются автотрейтами
unsafe impl Send for Cat {}
unsafe impl Sync for Cat {}
}

И при использовании impl в ограничениях мы снова можем выразить наше намерение, комбинируя трейты в ограничениях. Я уже высказывал мнение, что использование Iterator непосредственно в ограничениях — это редко то, что люди действительно хотят, поэтому ограничение будет выглядеть так:

#![allow(unused)]
fn main() {
fn thread_safe_sink(iter: impl IntoIterator + Send) { .. }
}

Если мы также хотим, чтобы отдельные элементы, выдаваемые итератором, были помечены как потокобезопасные, мы должны добавить дополнительные ограничения:

#![allow(unused)]
fn main() {
fn thread_safe_sink<I>(iter: I)
where
    I: IntoIterator<Item: Send> + Send,
{ .. }
}

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

Dyn-совместимый итератор

Dyn-совместимость — это ещё одна ось, по которой разделяются трейты. В отличие от, например, потокобезопасности, dyn-совместимость является неотъемлемой частью трейта и регулируется ограничениями Sized. К счастью, оба трейта Iterator и IntoIterator по своей природе являются dyn-совместимыми. Это означает, что их можно использовать для создания объектов трейта с помощью ключевого слова dyn:

#![allow(unused)]
fn main() {
struct Cat;
impl Iterator for Cat { .. }

let cat = Cat {};
let dyn_cat: &dyn Iterator = &cat; // ок
}

Некоторые комбинаторы итераторов, такие как count, принимают дополнительное ограничение Self: Sized2. Но поскольку объекты трейта сами по себе являются Sized, всё в основном работает как ожидается:

#![allow(unused)]
fn main() {
let mut cat = Cat {};
let dyn_cat: &mut dyn Iterator = &mut cat;
assert_eq!(dyn_cat.count(), 1); // ок
}

Двусторонний итератор

Часто итераторы по коллекциям хранят все данные в памяти, и их можно обходить в любом направлении. Для этой цели Rust предоставляет трейт DoubleEndedIterator. В то время как Iterator основан на методе next, DoubleEndedIterator основан на методе next_back. Это позволяет брать элементы как с логического начала, так и с конца итератора. И как только оба курсора встречаются, итерация считается завершённой.

#![allow(unused)]
fn main() {
/// Итератор, способный выдавать элементы с обоих концов.
pub trait DoubleEndedIterator: Iterator {
    /// Удаляет и возвращает элемент с конца итератора.
    fn next_back(&mut self) -> Option<Self::Item>;
}
}

Хотя можно ожидать, что этот трейт будет реализован для, например, VecDeque, интересно отметить, что он также реализован для Vec, String и других коллекций, которые растут только в одном направлении. Также, в отличие от некоторых других уточнений итератора, которые мы видели, DoubleEndedIterator имеет обязательный метод, который используется в качестве основы для нескольких новых методов, таких как rfold (обратная свёртка) и rfind (обратный поиск).

Позиционируемый итератор

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

Но не все потоки созданы равными. Когда мы читаем данные из обычного файла3 на диске, мы можем быть уверены, что, пока не было записей, мы можем прочитать тот же файл снова и получить тот же вывод. Та же гарантия, однако, не верна для сокетов, где после того, как мы прочитали данные из него, мы не можем прочитать те же данные снова. В Rust это различие проявляется через трейт Seek, который даёт контроль над курсором Read в типах, которые его поддерживают.

В Rust трейт Iterator не предоставляет механизма для управления базовым курсором, несмотря на его сходство с Read. Язык, который предоставляет абстракцию для этого, — это C++ в виде random_access_iterator. Это концепт C++ (аналог трейта), который дополнительно уточняет bidirectional_iterator. Мои знания C++ ограничены, поэтому я лучше процитирую документацию напрямую, чем попытаюсь перефразировать:

[...] random_access_iterator уточняет bidirectional_iterator, добавляя поддержку постоянного времени продвижения с помощью операторов +=, +, -= и -, постоянного времени вычисления расстояния с помощью - и нотации массива с индексированием [].

Возможность напрямую управлять курсором в реализациях Iterator может оказаться полезной при работе с типами коллекций в памяти, такими как Vec, а также при работе с удалёнными объектами, такими как API с постраничным выводом. Очевидной отправной точкой для такого трейта было бы зеркальное отражение существующего трейта io::Seek и адаптация его в качестве подтрейта Iterator:

#![allow(unused)]
fn main() {
/// Перечисление возможных методов позиционирования внутри итератора.
pub enum SeekFrom {
    /// Устанавливает смещение на указанный индекс.
    Start(usize),
    /// Устанавливает смещение на размер этого объекта плюс указанный индекс.
    End(isize),
    /// Устанавливает смещение на текущую позицию плюс указанный индекс.
    Current(isize),
}

/// Итератор с курсором, который можно перемещать.
pub trait SeekingIterator: Iterator {
    /// Переместиться к смещению в итераторе.
    fn seek(&mut self, pos: SeekFrom) -> Result<usize>;
}
}

Итератор времени компиляции

В Rust мы можем использовать блоки const {} для выполнения кода во время компиляции. Только функции const fn могут вызываться из блоков const {}. Свободные функции и методы const fn стабильны, но методы трейтов const fn — нет. Это означает, что такие трейты, как Iterator, ещё нельзя вызывать из блоков const {}, и поэтому выражения for..in также нельзя.

Мы знаем, что хотим поддерживать итерацию в блоках const {}, но мы ещё не знаем, как мы хотим обозначить как объявление трейта, так и ограничения трейта. Самый интересный открытый вопрос здесь — как мы в итоге будем передавать трейт Destruct, который необходим, чтобы типы могли быть уничтожаемыми в контекстах const. Это приводит к дополнительным вопросам о том, должны ли ограничения const трейта подразумевать const Destruct. И должна ли аннотация const быть частью объявления трейта, отдельных методов или, возможно, и того, и другого.

Этот пост — не подходящее место для обсуждения всех компромиссов. Но чтобы дать представление о том, как может выглядеть совместимый со временем компиляции трейт Iterator: вот вариант, в котором и трейт, и отдельные методы помечены const:

#![allow(unused)]
fn main() {
pub const trait IntoIterator {                        // ← `const`
    type Item;
    type IntoIter: const Iterator<Item = Self::Item>; // ← `const`
    const fn into_iter(self) -> Self::IntoIter;       // ← `const`
}

pub const trait Iterator {                                     // ← `const`
    type Item;
    const fn next(&mut self) -> Option<Self::Item>;            // ← `const`
    const fn size_hint(&self) -> (usize, Option<usize>) { .. } // ← `const`
}
}

Заимствующий итератор

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

#![allow(unused)]
fn main() {
pub trait IntoIterator {
    type Item<'a>                                               // ← Время жизни
    where
        Self: 'a;                                               // ← Ограничение
    type IntoIter: for<'a> Iterator<Item<'a> = Self::Item<'a>>; // ← Время жизни
    fn into_iter(self) -> Self::IntoIter;
}

pub trait Iterator {
    type Item<'a>                                 // ← Время жизни
    where
        Self: 'a;                                 // ← Ограничение
    fn next(&mut self) -> Option<Self::Item<'_>>; // ← Время жизни
    fn size_hint(&self) -> (usize, Option<usize>) { .. }
}
}

Были разговоры о добавлении времени жизни 'self в язык в качестве сокращения для where Self:'a. Но даже с этим дополнением этот набор сигнатур — не для слабонервных. Причина в том, что он использует GAT, которые и полезны, и мощны, — но по сути являются функцией системы типов для экспертов и могут быть немного сложными для понимания.

Заимствующая итерация также будет важна, когда мы добавим специальный синтаксис для создания итераторов с помощью ключевого слова yield. Следующий пример показывает блок gen {}, который создаёт строку, а затем возвращает ссылку на неё. Это идеально4 соответствует трейту Iterator, который мы определили:

#![allow(unused)]
fn main() {
let iter = gen {
    let name = String::from("Chashu");
    yield &name; // ← Заимствует локальное значение, хранящееся в куче.
};
}

Итератор с возвращаемым значением

Текущий трейт Iterator имеет ассоциированный тип Item, который соответствует ключевому слову yield в Rust. Но у него нет ассоциированного типа, который соответствовал бы ключевому слову return. Способ думать об итераторах сегодня — это то, что их тип возврата жёстко закодирован как unit. Если мы хотим, чтобы функции-генераторы и блоки могли не только выдавать, но и возвращать, нам потребуется какой-то способ выразить это.

#![allow(unused)]
fn main() {
let counting_iter = gen {
    let mut total = 0;
    for item in iter {
        total += 1;
        yield item;      // ← Выдаёт один тип.
    }
    total                // ← Возвращает другой тип.
};
}

Очевидный способ написать трейт для «итератора, который может возвращать» — это дать Iterator дополнительный ассоциированный элемент Output, который соответствует логическому возвращаемому значению. Чтобы иметь возможность выразить семантику объединения (fuse), функция next должна быть способна возвращать три различных состояния:

  1. Выдача ассоциированного типа Item
  2. Возврат ассоциированного типа Output
  3. Итератор исчерпан (завершён)

Один из способов сделать это — чтобы next возвращал Option<ControlFlow>, где Some(Continue) соответствует yield, Some(Break) — return, а None — завершению. Без финального состояния «завершено» вызов next снова на итераторе после того, как он закончил выдавать значения, вероятно, всегда должен приводить к панике. Это то, что делают большинство фьючерсов в асинхронном Rust, и это станет проблемой, если мы когда-нибудь захотим гарантировать отсутствие паник.

#![allow(unused)]
fn main() {
pub trait IntoIterator {
    type Output;                                            // ← Output
    type Item;
    type IntoIter:
        Iterator<Output = Self::Output, Item = Self::Item>; // ← Output
    fn into_iter(self) -> Self::IntoIter;
}

pub trait Iterator {
    type Output;                                           // ← Output
    type Item;
    fn next(&mut self)
        -> Option<ControlFlow<Self::Output, Self::Item>>;  // ← Output
    fn size_hint(&self) -> (usize, Option<usize>) { .. }
}
}

То, как это будет работать на стороне вызывающего и в комбинаторах, довольно интересно. Начнём с предоставленного метода for_each: он захочет возвращать Iterator::Output, а не (), после того как итератор завершится. Критически важно, что замыкание F, предоставленное for_each, работает только с Self::Output и не имеет знаний о Self::Output. Потому что если бы замыкание имело прямое знание об Output, оно могло бы завершиться досрочно, возвращая Output раньше ожидаемого, что является другим видом итератора, чем имеющий возвращаемое значение.

#![allow(unused)]
fn main() {
fn for_each<F>(self, f: F) -> Self::Output // ← Output
where
    Self: Sized,
    F: FnMut(Self::Item),
{ .. }
}

Если мы попробуем преобразовать «итератор с возвращаемым значением» в for..in, всё становится ещё интереснее. В Rust выражения loop сами могут вычисляться в не-unit типы, вызывая break с некоторым значением. Выражения for..in ещё не могут делать это в общем случае, за исключением обработки ошибок с помощью ?. Но нетрудно представить, как это можно заставить работать, концептуально это эквивалентно вызову Iterator::try_for_each и возврату Some(Break(value)):

#![allow(unused)]
fn main() {
let ty: u32 = for item in iter {  // ← Вычисляется в `u32`
    break 12u32                   // ← Вызывает `break` из тела цикла
};
}

Предполагая, что у нас есть Iterator с собственным возвращаемым значением, это означало бы, что выражения for..in смогут вычисляться в типы возврата, отличные от unit, без вызова break из тела цикла:

#![allow(unused)]
fn main() {
let ty: u32 = for item in iter {  // ← Вычисляется в `u32`
    dbg!(item);                   // ← Не вызывает `break` из тела цикла
};
}

Это, конечно, приводит к вопросам о том, как сочетать «итератор с возвращаемым значением» и «использование break внутри выражения for..in». Я оставлю это как упражнение для читателя, как это выразить (я уверен, что это можно сделать, просто думаю, что это интересно). Обобщение всех режимов досрочного возврата из выражений for..in на вызовы комбинаторов for_each — интересная задача, которую мы рассмотрим более подробно позже, когда будем обсуждать итераторы с досрочным завершением (ошибочные).

Итератор с аргументом в Next

В блоках-генераторах ключевое слово yield может использоваться для повторяющейся выдачи значений из итератора. Но что, если вызывающая сторона не просто хочет получать значения, но и передавать новые значения обратно в итератор? Это потребовало бы, чтобы yield мог вычисляться в тип, отличный от unit. Итераторы, имеющие такую функциональность, часто называют «сопрограммами», и они особенно полезны при реализации протоколов без ввода-вывода.

#![allow(unused)]
fn main() {
/// Какой-то RPC-протокол
enum Proto {
    /// Какое-то состояние протокола
    MsgLen(u32),
}

let rpc_handler = gen {
    let len = message.len();
    let next_state = yield Proto::MsgLen(len); // ← `yield` вычисляется в значение
    ..
};
}

Чтобы поддержать это, Iterator::next должен быть способен принимать дополнительный аргумент в виде нового ассоциированного типа Args. Этот ассоциированный тип имеет то же имя, что и входные аргументы Fn и AsyncFn. Если «итератор с аргументом в next» можно рассматривать как представляющий «сопрограмму», то семейство трейтов Fn можно рассматривать как представляющую обычную «подпрограмму» (функцию).

#![allow(unused)]
fn main() {
pub trait IntoIterator {
    type Item;
    type Args;                                          // ← Args
    type IntoIter:
        Iterator<Item = Self::Item, Args = Self::Args>; // ← Args
    fn into_iter(self) -> Self::IntoIter;
}

pub trait Iterator {
    type Item;
    type Args;                                                  // ← Args
    fn next(&mut self, args: Self::Args) -> Option<Self::Item>; // ← Args
    fn size_hint(&self) -> (usize, Option<usize>) { .. }
}
}

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

#![allow(unused)]
fn main() {
fn for_each<F>(self, args: Self::Args, f: F) // ← Args
where
    Self: Sized,
    F: FnMut(Self::Item) -> Self::Args,      // ← Args
{ .. }
}

Чтобы лучше проиллюстрировать, как это будет работать, и развить некоторую интуицию, рассмотрим ручные вызовы next внутри цикла. Мы начнём с создания некоторого начального состояния, которое передаётся в первый вызов next. Это создаст элемент, который можно использовать для создания следующего аргумента для next. И так далее, пока у итератора не останется больше элементов для выдачи:

#![allow(unused)]
fn main() {
let mut iter = some_value.into_iter();
let mut arg = some_initial_value;

// Цикл, пока есть элементы для выдачи
while let Some(item) = iter.next(arg) {
    // используем `item` и вычисляем следующий `arg`
    arg = process_item(item);
}
}

Если бы мы перебирали итератор с функцией next с помощью выражения for..in, эквивалентом возврата значения из замыкания было бы либо продолжение со значением. Это потенциально также может быть конечным выражением в теле цикла, которое, как вы можете думать, само по себе сегодня является подразумеваемым continue. Единственный оставшийся вопрос — как передавать начальные значения при создании цикла, но это в основном кажется упражнением в дизайне синтаксиса:

#![allow(unused)]
fn main() {
// Передача значения в функцию `next` кажется логично
// отображаемой на выражения `continue`.
// (передача начального состояния в цикл намеренно опущена)
for item in iter {
    continue process_item(item);   // ← `continue` со значением
};

// Можно представить, что выражения `for..in` имеют
// подразумеваемый `continue ()` в конце. Как функции
// имеют подразумеваемый `return ()`. Что, если бы он мог принимать
// значение?
// (передача начального состояния в цикл намеренно опущена)
for item in iter {
    process_item(item)             // ← `continue` со значением
};
}

«Итератор с возвращаемым значением» и «итератор с аргументом в next» кажутся особенно хорошо соответствующими break и continue. Я думаю о них как о двойственных, позволяя обоим выражениям переносить не-unit типы. Это кажется важным прозрением, которое я раньше ни от кого не слышал.

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

Итератор с досрочным завершением

Хотя сегодня возможно возвращать Try-типы, такие как Result и Option, из итератора, ещё невозможно немедленно остановить выполнение в случае ошибки5. Такое поведение обычно называют «досрочным завершением»: приостановка нормальной работы и запуск исключительного состояния (как электрический выключатель в здании).

В нестабильном Rust у нас есть блоки try {}, которые полагаются на нестабильный трейт Try, но у нас ещё нет функций try fn. Если мы хотим, чтобы они функционировали в трейтах так, как мы хотим, они должны десугерироваться в impl Try. Вместо того чтобы строить догадки о том, как может выглядеть потенциальный синтаксис try fn в будущем, мы будем писать наши примеры, напрямую используя -> impl Try. Вот как сегодня выглядят трейты Try (и FromResidual):

#![allow(unused)]
fn main() {
/// Оператор `?` и блоки `try {}`.
pub trait Try: FromResidual {
    /// Тип значения, производимого `?`,
    /// когда НЕ происходит досрочное завершение.
    type Output;

    /// Тип значения, передаваемого в `FromResidual::from_residual`
    /// как часть `?` при досрочном завершении.
    type Residual;

    /// Создаёт тип из его типа `Output`.
    fn from_output(output: Self::Output) -> Self;

    /// Используется в `?`, чтобы решить, должен ли оператор производить
    /// значение или распространять значение обратно вызывающей стороне.
    fn branch(self) -> ControlFlow<Self::Residual, Self::Output>;
}

/// Используется для указания, какие остаточные значения могут быть преобразованы
/// в какие типы `Try`.
pub trait FromResidual<R = <Self as Try>::Residual> {
    /// Создаёт тип из совместимого типа `Residual`.
    fn from_residual(residual: R) -> Self;
}
}

Можно думать об итераторе с досрочным завершением как об особом случае «итератора с возвращаемым значением». В своей базовой форме он будет возвращаться досрочно только в случае исключения, в то время как его логический тип возврата остаётся жёстко закодированным как unit. Тип возврата fn next должен быть impl Try, возвращающим Option, со значением Residual, установленным в ассоциированный тип Residual. Это позволяет всем комбинаторам использовать один и тот же Residual, обеспечивая поток типов.

#![allow(unused)]
fn main() {
pub trait IntoIterator {
    type Item;
    type Residual;
    type IntoIter: Iterator<
        Item = Self::Item,
        Residual = Residual   // ← Residual
    >;
    fn into_iter(self) -> Self::IntoIter;
}

pub trait Iterator {
    type Item;
    type Residual;                   // ← Residual
    fn next(&mut self) -> impl Try<  // ← impl Try
        Output = Option<Self::Item>,
        Residual = Self::Residual,   // ← Residual
    >;
}
}

Если мы снова рассмотрим сторону вызывающего, мы захотим предоставить способ для выражений for..in досрочно завершаться. Что интересно здесь, так это то, что базовый трейт итератора уже предоставляет метод try_for_each. Разница между этим методом и for_each, который мы собираемся увидеть, заключается в том, как получается тип Residual. В try_for_each значение локально для метода, в то время как если сам трейт «досрочно завершающийся», тип Residual определяется ассоциированным типом Self::Residual. Или, иными словами: в досрочно завершающемся итераторе тип, с которым мы досрочно завершаем, является свойством трейта, а не свойством метода.

#![allow(unused)]
fn main() {
fn for_each<F, R>(self, f: F) -> R                  // ← Тип возврата
where
    Self: Sized,
    F: FnMut(Self::Item) -> R,                      // ← Тип возврата
    R: Try<Output = (), Residual = Self::Residual>, // ← `impl Try`
{ .. }
}

Как упоминалось ранее в этом посте: взаимодействие между «итератором с типом возврата» и «досрочно завершающимся итератором» — интересное. Возврат Option<ControlFlow> из fn next способен кодировать три различных состояния, но эта комбинация возможностей требует от нас кодирования четырёх состояний:

  1. выдать следующий элемент
  2. завершиться с остаточным значением (residual)
  3. вернуть конечный результат (output)
  4. итератор завершён (идемпотентно)

Причина, по которой мы хотим иметь возможность кодировать такую сигнатуру, заключается в том, что при написании функций gen fn вполне разумно хотеть иметь тип возврата, досрочно завершаться при ошибке с помощью ?, а также выдавать значения. Это работает как обычные функции сегодня, но с добавленной возможностью вызывать yield. Наивный способ кодирования этого — возвращать impl Try из Option<ControlFlow<_>> с различными ассоциированными типами для Item, Output и Residual. Однако это начинает казаться немного выходящим из-под контроля, хотя, возможно, нотация try fn первого класса может принести некоторое облегчение.

#![allow(unused)]
fn main() {
pub trait IntoIterator {
    type Item;
    type Output;                           // ← `Output`
    type Residual;                         // ← `Residual`
    type IntoIterator: Iter<
        Item = Self::Item,
        Residual = Self::Residual,         // ← `Residual`
        Output = Self::Output,             // ← `Output`
    >;
    fn into_iter(self) -> Self::IntoIter;
}

pub trait Iterator {
    type Item;
    type Output;                     // ← `Output`
    type Residual;                   // ← `Residual`
    fn next(&mut self) -> impl Try<  // ← `impl Try`
        Output = Option<ControlFlow< // ← `ControlFlow
            Self::Output,            // ← `Output
            Self::Item,
        >>,
        Residual = Self::Residual,   // ← `Residual`
    >;
}
}

Чувствительный к адресу итератор

Преобразование генераторов в Rust может создавать самоссылающиеся типы. То есть: типы, которые имеют поля, заимствующие из других полей того же типа. Мы называем эти типы «чувствительными к адресу», потому что после того, как тип создан, его адрес в памяти должен оставаться стабильным. Это возникает при написании блоков gen {}, которые имеют локальные переменные, размещённые на стеке6, которые сохраняются живыми при вызовах yield. Что является или не является «локальной переменной, размещённой на стеке», может быть немного сложным. Но важно подчеркнуть, что, например, вызов IntoIterator::into_iter на типе и повторная выдача всех элементов — это то, что просто работает (площадка для игр):

#![allow(unused)]
fn main() {
// Этот пример работает сегодня
let iter = gen {
    let cat_iter = cats.into_iter();
    for cat in cat_iter {
        yield cat;
    }
};
}

И чтобы дать представление о том, что, например, не работает, вот один из примеров, собранных Tmandry (T-Lang). Он создаёт промежуточное заимствование, что приводит к ошибке: «Заимствование всё ещё может использоваться, когда тело gen fn выдаёт значение» (площадка для игр):

#![allow(unused)]
fn main() {
gen fn iter_set_rc<T: Clone>(xs: Rc<RefCell<HashSet<T>>>) ... {
    for x in xs.borrow().iter() {
        yield x.clone();
    }
}
}

Чтобы включить работу таких примеров, как последний, Rust должен быть способен выражать некоторую форму «чувствительного к адресу итератора». Очевидной отправной точкой было бы создание нового трейта PinnedIterator, который изменяет тип self метода next, чтобы принимать Pin<&mut Self> вместо &mut self:

#![allow(unused)]
fn main() {
trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;
    fn into_iter(self) -> Self::IntoIter;
}

trait Iterator {
    type Item;
    fn next(self: Pin<&mut Self>) -> Option<Self::Item>; // ← `Pin<&mut Self>`
    fn size_hint(&self) -> (usize, Option<usize>) { .. }
}
}

Перечисление всех проблем Pin заслуживает отдельного поста в блоге. Но всё же кажется достаточно важным указать, что это определение имеет то, что Rust for Linux называет Проблемой безопасной инициализации закреплённых типов (The Safe Pinned Initialization Problem). IntoIterator::into_iter не может возвращать тип, чувствительный к адресу во время создания; вместо этого чувствительность к адресу — это то, что можно гарантировать только позже, после того как тип будет закреплён (pin!) на месте.

В начале этого поста я использовал фразу: «(мягкое) устаревание трейта Iterator». Под этим я имел в виду одно предложение, которое позволяет gen {} возвращать новый трейт Generator с той же сигнатурой, что и наш пример. А также некоторые имплементации моста для совместимости. Основная часть системы совместимости будет следующей:

#![allow(unused)]
fn main() {
/// Все `Iterator` являются `Generator`.
impl<I: IntoIterator> IntoGenerator for I {
    type Item = I::Item;
    type IntoGen = IteratorGenerator<I::IntoIter>;
    fn into_gen(self) -> Self::IntoGen {
        IteratorGenerator(self.into_iter())
    }
}

/// Только закреплённые `Generator` являются `Iterator`.
impl<G> Iterator for Pin<G>
where
    G: DerefMut,
    G::Target: Generator,
{
    type Item = <<G as Deref>::Target as Generator>::Item;
    fn next(&mut self) -> Option<Self::Item> {
        Generator::next(self.as_mut())
    }
}
}

Это создаёт ситуацию, которую я описываю как «совместимость в одну-с-половиной стороны», в отличие от обычной двусторонней совместимости. А нам нужна двусторонняя совместимость, чтобы не было ломающих изменений. Это приводит к ситуации, когда изменение ограничения с приёма Iterator на Generator обратно совместимо. Но изменение имплементации с возврата Iterator на возврат Generator не является обратно совместимым. Очевидным решением тогда было бы мигрировать всю экосистему на использование ограничений Generator везде. В сочетании с тем, что gen {} всегда возвращает Generator, а не Iterator: это устаревание Iterator во всём, кроме имени.

На первый взгляд может показаться, что нас заставляют устаревать Iterator из-за ограничений Pin. Очевидный ответ на это — решить проблемы с Pin, заменив его чем-то лучшим. Но это создаёт ложную дихотомию: ничто не заставляет нас принимать решение по этому поводу сегодня. Как мы установили в начале этого раздела: удивительное количество случаев использования уже работает без необходимости в чувствительных к адресу итераторах. И как мы видели на протяжении этого поста: чувствительная к адресу итерация — далеко не единственная функция, которую блоки gen {} не смогут поддерживать с первого дня.

Итератор с гарантированным разрушением

Текущая формулировка thread::scope требует, чтобы поток, на котором она вызывается, оставался заблокированным до тех пор, пока все потоки не будут присоединены. Это требует входа в замыкание и выполнения всего кода внутри него. Сравните это с чем-то вроде FutureGroup, который логически владеет вычислениями и может свободно перемещаться. Значения фьючерсов, разрешённых внутри, в свою очередь могут быть выданы наружу. Но в отличие от thread::scope, он не может гарантировать, что все вычисления завершатся, и поэтому параллельная версия FutureGroup не может изменяемо удерживать изменяемые заимствования, как это может делать thread::scope.

#![allow(unused)]
fn main() {
// Пример использования `thread::scope`,
// возможность порождать новые потоки
// доступна только внутри замыкания.
thread::scope(|s| {
    s.spawn(|| ..);
    s.spawn(|| ..);
                    // ← Все потоки присоединяются здесь.
});

// Пример использования `FutureGroup`,
// замыкания не требуются.
let mut group = FutureGroup::new();
group.insert(future::ready(2));
group.insert(future::ready(4));
group.for_each(|_| ()).await;
}

Если мы хотим написать тип, аналогичный FutureGroup, с такими же гарантиями, как у thread::scope, нам нужно либо гарантировать, что FutureGroup никогда не может быть уничтожен, либо гарантировать, что деструктор FutureGroup всегда выполняется. Оказывается, довольно непрактично иметь типы, которые нельзя уничтожить в языке, где любая функция может паниковать. Поэтому единственный реальный вариант здесь — иметь типы, деструкторы которых гарантированно выполняются.

Наиболее правдоподобный известный нам способ сделать это — ввести новый автотрейт Leak, запрещающий передачу типов в mem::forget, Box::leak и т.д. Для получения дополнительной информации о дизайне прочитайте Линейные типы: краткий обзор (Linear Types One-Pager). Поскольку Leak является автотрейтом, мы могли бы компоновать его с существующими трейтами Iterator и IntoIterator, подобно Send и Move:

#![allow(unused)]
fn main() {
fn linear_sink(iter: impl IntoIterator<IntoIter: ?Leak>) { .. }
}

Асинхронный итератор

В Rust ключевое слово async может преобразовывать императивные тела функций в стейт-машины, которые можно вручную продвигать, вызывая метод Future::poll. Под капотом это делается с помощью так называемого преобразования сопрограмм, которое мы также используем для десугаринга блоков gen {}. Но это только механика; ключевое слово async в Rust также вводит две новые возможности: ad-hoc конкурентность и ad-hoc отмену. Вместе эти возможности можно комбинировать для создания новых операций управления потоком, таких как Future::race и Future::timeout.

Асинхронные функции в трейтах (Async Functions in Traits) были стабилизированы год назад в Rust 1.75, что позволило использовать async fn в трейтах. Заставить трейт Iterator работать с async — в основном вопрос добавления префикса async к next:

#![allow(unused)]
fn main() {
trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;
    fn into_iter(self) -> Self::IntoIter;
}

trait Iterator {
    type Item;
    async fn next(&mut self) -> Option<Self::Item>;      // ← async
    fn size_hint(&self) -> (usize, Option<usize>) { .. }
}
}

Хотя метод next здесь был бы аннотирован ключевым словом async, метод size_hint, вероятно, не должен. Причина в том, что он действует как простой геттер, и ему действительно не следует выполнять какие-либо асинхронные вычисления. Также неясно, должен ли into_iter быть async fn или нет. Здесь, вероятно, нужно установить шаблон, и это вполне может быть так.

Комбинация вариантов итераторов, которая недавно вызвала некоторый интерес, — это чувствительный к адресу асинхронный итератор. Мы могли бы представить себе его, заставив next принимать self: Pin<&mut Self>:

#![allow(unused)]
fn main() {
trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;
    async fn into_iter(self) -> Self::IntoIter;
}

trait Iterator {
    type Item;
    async fn next(self: Pin<&mut Self>) -> Option<Self::Item>; // ← async + `Pin<&mut Self>`
    fn size_hint(&self) -> (usize, Option<usize>) { .. }
}
}

Эта сигнатура, вероятно, собьёт с толку некоторых людей. async fn next возвращает impl Future, который сам должен быть закреплён перед опросом. В этом примере мы отдельно требуем, чтобы Self также был закреплён. Это потому, что «состояние итератора» и «состояние фьючерса» — не одно и то же состояние. Мы интуитивно понимаем это при работе с неасинхронными чувствительными к адресу итераторами: локальные переменные, созданные внутри next, не захватываются включающим итератором и могут быть закреплены на стеке на время вызова next. Но при работе с асинхронным чувствительным к адресу итератором почему-то люди предполагают, что все локальные переменные, определённые в fn next, теперь должны принадлежать итератору, а не фьючерсу.

В экосистеме асинхронного Rust существует популярная вариация трейта асинхронного итератора под названием Stream. Вместо того чтобы разделять состояние итератора (self) и функцию next, он объединяет оба в одно состояние. Трейт имеет единственный метод poll_next, который действует как смесь Future::poll и Iterator::next. С предоставленной удобной функцией async fn next, которая является тонкой обёрткой вокруг poll_next.

#![allow(unused)]
fn main() {
trait IntoStream {
    type Item;
    type IntoStream: Stream<Item = Self::Item>;
    fn into_stream(self) -> Self::IntoStream;
}

pub trait Stream {
    type Item;
    fn poll_next(                            // ← `fn poll_next`
        self: Pin<&mut Self>,                // ← `Pin<&mut Self>`
        cx: &mut Context<'_>,                // ← `task::Context`
    ) -> Poll<Option<Self::Item>>;           // ← `task::Poll`
    async fn next(&mut self) -> Self::Item   // ← `async`
    where
        Self: Unpin                          // ← `Self: Unpin`
    { .. }
    fn size_hint(&self) -> (usize, Option<usize>) { ... }
}
}

Объединяя оба состояния в одно, этот трейт нарушает один из основных принципов дизайна асинхронного Rust: возможность единообразно сообщать об отмене путём уничтожения фьючерсов. Здесь, если фьючерс от fn next уничтожается, это отсутствие операции, и отмена не произойдёт. Это приводит к тому, что композиционные операторы управления асинхронным потоком, такие как Future::race, не работают, несмотря на компиляцию.

Чтобы вместо этого отменить текущий вызов next, вы вынуждены либо уничтожить весь поток, либо использовать какой-то специальный метод для отмены только состояния фьючерса. Отмена в асинхронном Rust печально известна тем, что её сложно правильно реализовать, что понятно, когда (среди прочего) основные трейты в экосистеме не обрабатывают её корректно.

Конкурентный итератор

Поскольку мы приближаемся к концу нашего изложения, давайте поговорим о самых сложных вариантах Iterator. Первым в очереди: крейт rayon и трейт ParallelIterator. Rayon предоставляет так называемые «параллельные итераторы», которые обрабатывают элементы конкурентно, а не последовательно, используя потоки операционной системы. Это, как правило, значительно повышает пропускную способность по сравнению с последовательной обработкой, но имеет оговорку, что все потребляемые элементы должны реализовывать Send. Чтобы увидеть, насколько знакомыми могут быть параллельные итераторы: следующий пример выглядит почти идентично последовательному итератору, за исключением вызова into_par_iter вместо into_iter.

#![allow(unused)]
fn main() {
use rayon::prelude::*;

(0..100)
    .into_par_iter()   // ← Вместо вызова `into_iter`.
    .for_each(|x| println!("{:?}", x));
}

Однако трейт ParallelIterator поставляется в паре с трейтом Consumer. Это может немного ошеломить, но способ работы Rayon заключается в том, что комбинаторы могут быть связаны в цепочку для создания обработчика, который в конце цепочки копируется в каждый поток и используется там для обработки элементов. Это, конечно, упрощённое объяснение; я отсылаю к сопровождающим Rayon за подробным объяснением. Чтобы дать вам представление о том, насколько эти трейты отличаются от обычных трейтов Iterator, вот они (упрощённо):

#![allow(unused)]
fn main() {
/// Потребитель — это, по сути, обобщённая операция «свёртки».
pub trait Consumer<Item>: Send + Sized {
    /// Тип папки, в которую этот потребитель может быть преобразован.
    type Folder: Folder<Item, Result = Self::Result>;
    /// Тип редуктора, который создаётся, если этот потребитель разделён.
    type Reducer: Reducer<Self::Result>;
    /// Тип результата, который в конечном итоге произведёт этот потребитель.
    type Result: Send;
}

/// Тип, который можно итерировать параллельно.
pub trait IntoParallelIterator {
    /// Какой итератор мы возвращаем?
    type Iter: ParallelIterator<Item = Self::Item>;
    /// Какой тип элемента мы выдаём?
    type Item: Send;
    /// Возвращает итератор с сохранением состояния для параллельной обработки.
    fn into_par_iter(self) -> Self::Iter;
}

/// Параллельная версия стандартного трейта итератора.
pub trait ParallelIterator: Sized + Send {
    /// Тип элемента, который производит этот параллельный итератор.
    type Item: Send;
    /// Внутренний метод, используемый для определения поведения этого
    /// параллельного итератора. Вам не следует вызывать его напрямую.
    fn drive_unindexed<C>(self, consumer: C) -> C::Result
    where
        C: UnindexedConsumer<Self::Item>;
}
}

Что здесь наиболее важно, так это то, что использование трейта ParallelIterator ощущается похожим на обычный итератор. Всё, что вам нужно сделать, это вызвать into_par_iter вместо into_iter, и вы в деле. На стороне потребления кажется, что мы должны быть способны создать какую-то вариацию for..in для потребления параллельных итераторов. Вместо того чтобы строить догадки о синтаксисе, мы можем посмотреть на сигнатуру ParallelIterator::for_each, чтобы понять, какие гарантии для этого потребуются.

#![allow(unused)]
fn main() {
fn for_each<F>(self, f: F)
where
    F: Fn(Self::Item) + Sync + Send
{ .. }
}

Мы можем наблюдать три изменения здесь по сравнению с базовым трейтом итератора:

  1. Self больше не должен быть Sized.
  2. Несколько предсказуемо, замыкание F должно быть потокобезопасным.
  3. Замыкание F должно реализовывать Fn, а не FnMut, чтобы предотвратить гонки данных.

Затем мы можем сделать вывод, что в случае параллельного выражения for..in тело цикла не сможет захватывать какие-либо изменяемые ссылки. Это дополнение к существующему ограничению, что тела циклов уже не могут выражать семантику FnOnce и перемещать значения (например, «Предупреждение: это значение было перемещено на предыдущей итерации цикла»).

Интересная комбинация — это «параллельная итерация» и «асинхронная итерация». Интересный аспект ключевого слова async в Rust заключается в том, что оно позволяет ad-hoc конкурентное выполнение фьючерсов без необходимости полагаться на специальные системные вызовы или потоки ОС. Это означает, что конкурентность и параллелизм могут быть отделены друг от друга. Хотя мы ещё не видели трейта «параллельный асинхронный итератор» в экосистеме, крейт futures-concurrency кодирует «конкурентный асинхронный итератор»7. Так же, как ParallelIterator, ConcurrentAsyncIterator поставляется в паре с трейтом Consumer.

#![allow(unused)]
fn main() {
/// Описывает тип, который может получать данные.
pub trait Consumer<Item, Fut>
where
    Fut: Future<Output = Item>,
{
    /// Какой тип элемента мы возвращаем при завершении?
    type Output;
    /// Отправить элемент на следующий шаг в очереди обработки.
    async fn send(self: Pin<&mut Self>, fut: Fut) -> ConsumerState;
    /// Двигаться вперёд в потребителе, занимаясь чем-то ещё.
    async fn progress(self: Pin<&mut Self>) -> ConsumerState;
    /// У нас не осталось данных для отправки `Consumer`;
    /// ждём его вывода.
    async fn flush(self: Pin<&mut Self>) -> Self::Output;
}

pub trait IntoConcurrentAsyncIterator {
    type Item;
    type IntoConcurrentAsyncIter: ConcurrentAsyncIterator<Item = Self::Item>;
    fn into_co_iter(self) -> Self::IntoConcurrentAsyncIter;
}

pub trait ConcurrentAsyncIterator {
    type Item;
    type Future: Future<Output = Self::Item>;

    /// Внутренний метод, используемый для определения поведения
    /// этого конкурентного итератора. Вам не следует
    /// вызывать его напрямую.
    async fn drive<C>(self, consumer: C) -> C::Output
    where
        C: Consumer<Self::Item, Self::Future>;
}
}

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

Ещё один интересный момент, на который стоит обратить внимание: конкурентная итерация также взаимно исключает заимствующую итерацию. Заимствующий итератор полагается на то, что выдаваемые элементы имеют последовательные времена жизни, в то время как конкурентные времена жизни полагаются на то, что выдаваемые элементы имеют перекрывающиеся времена жизни. Это принципиально несовместимые концепции.

Заключение

И это каждый вариант итератора, о котором я знаю, что доводит нас до 17 различных вариаций. Если убрать варианты, которые мы можем выразить с помощью подтрейтов (4 варианта) и автотрейтов (5 вариантов), у нас останется 9 различных вариантов. Это 9 вариантов, с 76 методами и примерно 150 реализациями трейтов в стандартной библиотеке. Это большая поверхность API, и это даже не учитывая все различные комбинации итераторов.

Iterator, вероятно, самый сложный трейт в языке. Это перекрёсток в языке, где пересекаются каждый эффект, автотрейт и функция времени жизни. И в отличие от подобных перекрёстков, таких как семейство трейтов Fn; трейт Iterator стабилен, широко используется и имеет множество комбинаторов. Это означает, что он имеет как широкую область применения, так и строгие гарантии обратной совместимости, которые нам необходимо поддерживать.

В то же время Iterator также не так уж и особенный. В конце концов, это довольно простой трейт для написания вручную. Я в основном думаю о нём как о канарейке для общеязыковых недостатков. Iterator, например, не уникален в своём требовании стабильных адресов: мы хотим иметь возможность гарантировать это для произвольных типов и использовать это с произвольными интерфейсами. Я считаю, что вопрос, который следует задать здесь, звучит так: что мешает нам использовать чувствительные к адресу типы с произвольными типами и произвольными интерфейсами? Если мы сможем ответить на это, у нас будет не только ответ для Iterator — мы решим эту проблему для всех других интерфейсов, которые мы сознательно не предвидели, что захотят взаимодействовать с этим8.

В этом посте я сделал всё возможное, чтобы на примерах показать, какие ограничения имеет сегодня трейт Iterator и как каждый вариант может их преодолеть. И хотя я считаю, что мы должны пытаться со временем устранить эти ограничения, я не думаю, что кто-то слишком жаждет, чтобы мы создали 9 новых вариантов подмодуля core::iter. Или тысячу возможных комбинаций этих подмодулей (ура, комбинаторика). Единственный осуществимый подход, который я вижу для навигации в пространстве проблем, — это расширение, а не замена трейта Iterator. Вот мои текущие мысли о том, как мы могли бы расширить Iterator для поддержки всех вариантов итераторов:

  • базовый трейт: по умолчанию, уже поддерживается
  • dyn-совместимый: по умолчанию, уже поддерживается
  • ограниченный: подтрейт, уже поддерживается
  • объединённый: подтрейт, уже поддерживается
  • потокобезопасный: автотрейт, уже поддерживается
  • позиционируемый: подтрейт
  • времени компиляции: полиморфизм по эффекту (const)9
  • заимствующий: время жизни 'move10
  • с возвращаемым значением: не уверен11
  • с аргументом в next: значение по умолчанию + опциональный/вариативный аргумент
  • с досрочным завершением: полиморфизм по эффекту (try)
  • чувствительный к адресу: автотрейт
  • с гарантированным разрушением: автотрейт
  • асинхронный: полиморфизм по эффекту (async)
  • конкурентный: новый вариант трейта (ов)

Развивая язык, я считаю, что вся наша работа заключается в балансировании разработки функций и управления сложностью. Если всё сделано правильно, со временем язык должен не только становиться более способным, но и проще и легче для расширения. Чтобы процитировать то, что TC (T-Lang) сказал в недавнем разговоре: «Мы должны становиться лучше в том, чтобы становиться лучше каждый год»12.

Размышляя о том, как мы хотим преодолеть вызовы, представленные в этом посте, я искренне надеюсь, что мы всё больше начнём думать о способах решения классов проблем, которые просто сначала появляются с Iterator. В то же время ища возможности выпускать функции раньше, не блокируя себя на поддержке всех случаев использования сразу.

Примечания

  1. Я основываю это на своём опыте участия в рабочей группе Node.js Streams WG в середине 2010-х. По моим подсчётам, Node.js теперь имеет пять различных поколений абстракций потоков. Неудивительно, что это не особенно приятно в использовании, и в идеале этого следует избегать в Rust. Хотя я и не против проведения устаревания основных трейтов в Rust, я считаю, что для этого мы хотим приблизиться к 100% уверенности, что это будет последнее устаревание, которое мы сделаем. Если мы собираемся отправиться в путешествие длиной более десяти лет с проблемами миграции, мы должны быть абсолютно уверены, что оно того стоит. ↩

  2. Признаюсь, мои знания о dyn в лучшем случае отрывочны. Из всего в этом посте раздел о dyn был тем, о чём у меня было наименьшее представление. ↩

  3. Нет, файлы в /proc — это не «обычные файлы». Да, я знаю, что сокеты технически являются файловыми дескрипторами. ↩

  4. Помните, что строки выделяются в куче, поэтому нам не нужно учитывать чувствительность к адресу. Хотя компилятор ещё не может выполнить эту десугаризацию, в языке нет ничего, что запрещало бы это. ↩

  5. Под этим я подразумеваю: ошибку, а не панику. ↩

  6. Это также затрагивает локальные переменные, выделенные в куче, но это не ограничение языка, только реализации. ↩

  7. Технически этот трейт называется ConcurrentStream, но здесь мало что зависит от Stream. Я назвал его так, потому что он совместим с трейтом futures_core::Stream, поскольку futures-concurrency предназначен быть производственным крейтом. ↩

  8. Это смежно с «известными неизвестными» и «неизвестными неизвестными» — мы не должны обслуживать только случаи, которые можем предвидеть, но и случаи, которые не можем. И это требует анализа паттернов и мышления в системах. ↩

  9. Сам эффект const уже полиморфен по отношению к эффекту времени компиляции, поскольку const fn означает: «функция, которая может быть выполнена либо во время компиляции, либо во время выполнения». Из всех вариантов эффектов const, скорее всего, произойдёт в ближайшей перспективе. ↩

  10. Мы хотим выразить, что у нас есть ассоциированный тип, который МОЖЕТ принимать время жизни, а НЕ ДОЛЖЕН принимать время жизни. Таким образом, мы можем передать тип по значению там, где в противном случае ожидается передача типа по ссылке. Это отличается как от времён жизни 'static, так и от ссылок &own. ↩

  11. Я пытался ответить, как добавить возвращаемые значения в трейт Iterator, год назад в своём посте Iterator as an Alias, но у меня не получилось. Как я упоминал ранее в посте: сочетание «возврат со значением» и «может досрочно завершаться с ошибкой» кажется сложным. Возможно, здесь есть комбинация, которую я упускаю / мы можем как-то особо обработать. Но я ещё этого не видел. ↩

  12. Я недавно заметил TC, что начал думать об управлении и эволюции языка как о производной языка и проекта. Вместо того чтобы измерять прямые результаты, мы измеряем процесс, который производит эти результаты. TC заметил, что нас на самом деле должна волновать вторая производная. Мы должны не только улучшать наши результаты со временем; процессы, которые производят эти результаты, также должны улучшаться со временем. Или, иными словами: мы должны становиться лучше в том, чтобы становиться лучше каждый год! Мне нравится эта цитата, и я хотел, чтобы вы тоже её прочитали. ↩