Как написать хороший генератор

В интернете невероятное количество статей о том «как написать свой генератор на С++20», но почти все они сводятся к новичковым хело вордам и почти ни одной статьи о том как написать хороший генератор. Что ж, это нужно исправлять!

generator<int> ints() { // после каждого co_yield мы возвращаемся в функцию 'use'   co_yield 1;   co_yield 2;    co_yield 3; } void use() {   for(int i : ints()) foo(i); }

Сначала определимся что такое хороший генератор, для меня это когда он:

• эффективен, мы всё таки на С++ пишем

• удобен в использовании(не провоцирует неявных ошибок, интерфейс понятен даже новичку)

В связи с этим возникает вопрос, зачем писать свой, ведь в С++23 уже добавили std::generator? Ну, во-первых С++23 в проде будет ещё не скоро, а во-вторых std::generator это, к сожалению, одна из худших вещей добавленных в стандартную библиотеку.

Вкратце опишу свои претензии к нему(кстати, его невозможно реализовать без компиляторной магии)

Интерфейс

template<typename Reference,  typename Value = void, typename Alloc = void> class std::generator;

Первый = void означает «по дефолту», второй = void означает type erasure! Это сбивает с толку даже матёрого С++ программиста и даже после чтения документации.

Сами авторы признают, что Alloc в этом интерфейсе лишний — логика генератора никак не зависит от того как его аллоцировали. Это должно достигаться специализацией coroutine_traits.

Ну это ещё полбеды, вот вы захотели генератор строк.

Пишем

std::generator<string> foo(); // уже ошиблись = )

Это уже будет неэффективно, потому что первый аргумент шаблона — ссылка. Правильно было бы написать generator<string_view>, но тогда на принимающей стороне нужно копировать. В итоге у вас выйдет что то типа generator<string&&, string> или что похуже и одному богу известно будет ли это эффективно.

std::generator буквально неюзабелен. Пройдусь банально по всем его методам:

• begin — нельзя вызывать дважды, при этом нет способа проверить вызван ли он уже. Вызовете второй раз — undefined behavior. Хотя ожидаемое лично мной поведение — продолжение итерации с того места, где остановились в предыдущий раз

void foo(std::generator<int> x) {   for(int i : x) // возможно UB, причём проверить будет ли UB нельзя никак     do_smth(i); }

Ух, что то я увлёкся…

Пишем наконец свой генератор

Итак, мы определились с тем что хотим видеть в генераторе и чего не хотим, для реализации нам понадобится написать

• promise type нашей корутины с возможностью yield значение

• сущность generator управляющую через промис корутиной

• итератор, который будет ссылаться на генератор

Очевидно, что главное что надо сделать это yield и вы можете найти тысячи реализаций в интернете, которые выглядят как-то так:

struct promise {   YieldType value;    auto yield_value(YieldType x) {      value = std::move(x);      return std::suspend_always{};   } };

И это .. неэффективно! Зачем нам хранить и создавать значение, если можно просто взять на него указатель?

struct promise {   YieldType* value;    auto yield_value(Yield&& x) {      value = std::addressof(x);      return std::suspend_always{};   } };

Каждый уважающий себя программист на С++ сразу же, как ему покажется, увидит ошибку. Мы сохраняем указатель на «временный» объект, который разрушится как только вызов yield_value закончится

Но вы забыли, это же корутины! Давайте посмотрим на это из генератора

generator<int> foo() {   co_yield 5;   // мы дойдём до этой точки ТОЛЬКО после того как   // значение будет обработано вызывающей стороной! }

Поэтому, если вспомнить правило «временные значения живут до конца выражения» и цитату стандарта «co_yield x» это yield-expression можно понять, что сохранять указатель это абсолютно безопасно и главное — эффективно.

Теперь насчёт других специальных методов промиса: мы должны решить как будет вести себя генератор на старте, генерировать первое значение сразу или подождать? Тут решение на самом деле неочевидно, но в итоге все реализации приходят к приостановке перед генерацией, чтобы в .begin сгенерировать первое значение и не пропустить ничего… А ещё чтобы генератор не стал за эту первую свою итерацию рекурсивным, сломав что-нибудь по дороге (но о рекурсивности — позже)

  std::suspend_always initial_suspend() {     return {};   }   void return_void() {} // пока приостанавливаемся в конце, чтобы не не уничтожить корутину раньше времени // но это ещё не окончательно!   std::suspend_always final_suspend() const;

Почему то что мы делали до этого неэффективно из зачем нужен рекурсивный генератор

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

 generator<int> g() {   for(int x : another_generator())     co_yield x; }

Генератор выбрасывает значения другого генератора. Что при этом происходит?

1. пробуждается генератор ‘g’

2. он будит генератор ‘another_generator’

3. тот будит какой то ещё генератор и так по цепочке O(N) раз, в конце концов получается значение.

Каждое из пробуждений — достаточно дорогая операция, сравнимая с вызовом функции по указателю

А что если мы будем сразу из самого верхнего генератора в цепочке пробуждать самый нижний, а тот когда сгенерирует значение будет будить опять самый верхний? В этом и кроется суть рекурсивного генератора, он превращает O(N) вызовов для получения значения в гарантированное O(1) и это прекрасно.

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

Но главное — что получается в конце. Нет буквально ни одного лишнего if относительно обычного генератора, весь оверхед — память, 1-2 указателя на 1 генератор. Фактически — оверхед смешной учитывая какие плюсы он даёт.

Идея будет простой: если генератор видит yield другого генератора, то он подключает его в цепочку, говорит ему куда генерировать значения и … передаёт управление симметричным трансфером. Название сложное, а на деле это просто пробуждение другого генератора. Тот в свою очередь в final_suspend вернёт управление обратно

// Leaf == generator template <typename Leaf> struct attach_leaf {   Leaf leaf;    bool await_ready() const noexcept {     return leaf.empty();   }    std::coroutine_handle<> await_suspend(typename Leaf::handle_type owner) const noexcept {     // верим в лучшее, что никто не сделал истинно "рекурсивный"     // генератор и не yield'нул сам себя     assert(owner != leaf.top);     auto& leaf_p = leaf.top.promise();     auto& root_p = *owner.promise().root;     leaf_p.current_worker.promise().root = &root_p;     leaf_p._owner = owner;     root_p.current_worker = leaf_p.current_worker;     return leaf_p.current_worker; // собственно симметричный трансфер управления   }   void await_resume() {   } };

Тут мы вводим несколько новых сущностей:

• current_worker — генератор, который сейчас активен(самый нижний в цепочке)

• root — самый высокий в цепочке генератор

• owner — генератор, в котором yield’нули генератор

Самое интерерсное здесь, пожалуй, то как устроен промис

  struct generator_promise {     generator_promise* root = this;     handle_type current_worker = self_handle();     union {       Yield** _current_result_ptr;  // setted only in root       handle_type _owner;           // setted only in leafs     };   };

То есть root по умолчанию это сам генератор, current_worker по умолчанию — тоже он же сам, current_result_ptr вовсе указывает на generator, то есть активный генератор прямо сразу туда складывает значения, минуя вообще всех

Интерфейс нашего генератора:

template <yieldable Y> struct generator {  private:   Y* current_result = nullptr;   // ещё один хак, чтобы убрать лишние ифы. Можете посмотреть в исходниках   always_done_or<promise_type> top = always_done_coroutine();  public:   ... } // максимально просто и понятно

Итог

Мы получили генератор, который эффективен, рекурсивен, имеет дефолтный конструктор и вызов цикл for по дефолтно сконструированному генератору даст 0 значений(напомню std::generator даст UB), можно вызывать begin повторно и просто продолжать итерацию,

dd::generator<int> ints() {   for(int i = 0; i < 50; ++i)     co_yield i; } dd::generator<int> other_ints() {   for(int i = 0; i < 50; ++i)     co_yield i;   // elements_of всего лишь тег, рекурсивно yield'им 'ints'    co_yield dd::elements_of(ints()); }  int use_generators() {   auto g = other_ints();   int res = 0;   for(int v : gg) {     res += v;     if (v == 33) break;   }   // спокойно продолжаем итерацию   for (int v : gg)     res += v;   return res; }

Ещё очень много тонкостей с обработкой исключений, кастомизацией аллокаций и мелочами для эффективности, всё это вы можете посмотреть в исходном коде: https://github.com/kelbon/kelcoro