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

что такое генератор

в С++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);
}
подробный разбор недостатков std::generator

  • end - возвращает std::default_sentinel всегда, при этом метод не является статическим

  • деструктор - неявно noexcept, хотя .destroy на хендле который он вызывает может бросить исключение при разрушении локальных объектов на корутине. То есть помимо UB вам подсунули ещё и неявный std::terminate

  • мув конструктор - проблема в том, что он есть. А дефолтного конструктора нет! Это нонсенс, таким образом после мува конструктор является invalid объектом, который использовать нельзя. Никак. Вообще.

  • std::pmr::generator - проблема опять же в том, что это существует. Это алиас на генератор с std::pmr::polymorphic_alloc, хотя генератор не является контейнером и не использует этот аллокатор буквально никак, не вдаваясь в подробности - создание этого алиаса это банальный обман пользователя

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

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

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

  • 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