Recursive generator using C++20 coroutines

.gitignore

build

README.md

C++20 coroutines cheat sheet

See Coroutine support at cppreference.com for more.

Library

#include <coroutine>
// coroutine_traits
// coroutine_handle
// noop_coroutine
// noop_coroutine_promise
// noop_coroutine_handle
// suspend_never - awaitable
// suspend_always - awaitable

Concepts

promise

template <class Value> struct promise {
  coroutine<Value> get_return_object();

  static awaitable<> initial_suspend();
  static awaitable<> final_suspend() noexcept;

  void unhandled_exception();

  // optionally either
  void return_value(Value &&v);
  // or
  void return_void();

  // optionally
  awaitable<> yield_value(Value &&v);

  // optionally
  awaitable<> await_transform(AwaitTarget t);
};

coroutine

template <class Value> struct coroutine {
  using promise_type = promise<Value>;

  ~coroutine();

  coroutine(coroutine &&that);
  coroutine(std::coroutine_handle<promise<Value>> h);
};

awaitable

template <class Value>
struct awaitable {
  bool await_ready();

  Value await_resume();

  // either
  template <class Outer>
  void await_suspend(std::coroutine_handle<promise<Outer>> &h);
  // or
  template <class Outer>
  bool await_suspend(std::coroutine_handle<promise<Outer>> &h);
  // or
  template <class Outer, class Other>
  std::coroutine_handle<promise<Other>>
  await_suspend(std::coroutine_handle<promise<Outer>> &h);
};

operator co_await

// optionally
awaitable<> operator co_await(AwaitTarget value);

Translation

Coroutine body

  promise_type __promise;

  try {
    co_await __promise.initial_suspend();

    // function body

  } catch ( ... ) {
    if (!initial_await_resume_called)
      throw;

    __promise.unhandled_exception();
  }

__final_suspend:
  co_await __promise.final_suspend();

auto result = co_await expr

// await_transform and operator co_await calls are optional
auto &&__expr = operator co_await(__promise.await_transform(expr));

if (!__expr.await_ready()) {
  __expr.await_suspend(__coroutine_handle);
  // suspend/resume point
}

auto result = __expr.await_resume();

co_yield expr

co_await __promise.yield_value(expr)

co_return expr

__promise.return_value(expr);
goto __final_suspend;

co_return

__promise.return_void();
goto __final_suspend;

bst.hpp

#pragma once

#include "generator.hpp"

#include <memory>
#include <utility>

// This is a naïve implementation of binary search tree.

template <class K, class V> struct bst_node;

template <class K, class V> using bst = std::shared_ptr<bst_node<K, V>>;

template <class K, class V> struct bst_node {
  const bst<K, V> lhs, rhs;
  const K key;
  const V value;
};

template <class K, class V> bst<K, V> empty() { return nullptr; }

template <class K, class V>
bst<K, V> put(const bst<K, V> &tree, K &&key, V &&value) {
  if (tree)
    if (key < tree->key)
      return std::make_shared<bst_node<K, V>>(
          put(tree->lhs, std::forward<K>(key), std::forward<V>(value)),
          tree->rhs,
          tree->key,
          tree->value);
    else if (tree->key < key)
      return std::make_shared<bst_node<K, V>>(
          tree->lhs,
          put(tree->rhs, std::forward<K>(key), std::forward<V>(value)),
          tree->key,
          tree->value);
    else
      return std::make_shared<bst_node<K, V>>(
          tree->lhs, tree->rhs, std::forward<K>(key), std::forward<V>(value));
  else
    return std::make_shared<bst_node<K, V>>(
        nullptr, nullptr, std::forward<K>(key), std::forward<V>(value));
}

// Using a recursive generator it is now trivial to provide traversals over a
// BST.

template <class K, class V>
generator<std::pair<K, V>> in_order(const bst<K, V> &node) {
  if (node) {
    co_yield in_order(node->lhs);
    co_yield std::pair{node->key, node->value};
    co_yield in_order(node->rhs);
  }
}

template <class K, class V>
generator<std::pair<K, V>> pre_order(const bst<K, V> &node) {
  if (node) {
    co_yield std::pair{node->key, node->value};
    co_yield pre_order(node->lhs);
    co_yield pre_order(node->rhs);
  }
}

template <class K, class V>
generator<std::pair<K, V>> post_order(const bst<K, V> &node) {
  if (node) {
    co_yield post_order(node->lhs);
    co_yield post_order(node->rhs);
    co_yield std::pair{node->key, node->value};
  }
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.22)

set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED TRUE)
set(CMAKE_CXX_EXTENSIONS FALSE)

set(CMAKE_CXX_FLAGS "-Wall -Wextra -Wpedantic -Werror -fcoroutines")

project(generator)

add_executable(generator main.cpp)

generator.hpp

#pragma once

#include <coroutine>
#include <exception>
#include <utility>
#include <variant>

// This is a naïve implementation of a recursive generator using C++20
// coroutines.

template <class T> struct generator {
  struct promise_type {
    generator get_return_object() {
      return std::coroutine_handle<promise_type>::from_promise(*this);
    }

    static std::suspend_always initial_suspend() { return {}; }
    static std::suspend_always final_suspend() noexcept { return {}; }

    [[noreturn]] void unhandled_exception() { std::terminate(); }

    void return_void() {}

    void await_transform() = delete;

    template <class U> std::suspend_always yield_value(U &&v) {
      state.template emplace<1>(std::forward<U>(v));
      return {};
    }

    std::suspend_always yield_value(generator &&g) {
      state.template emplace<2>(std::move(g));
      return {};
    }

  private:
    friend generator;
    struct empty {};
    std::variant<empty, T, generator> state;
  };

  bool move_next() {
    if (!coro)
      return false;

    auto &p = coro.promise();
    do {
      if (auto g = std::get_if<generator>(&p.state))
        if (g->move_next())
          return true;

      coro.resume();
      if (coro.done()) {
        coro.destroy();
        coro = {};
        return false;
      }

    } while (std::get_if<generator>(&p.state));

    return true;
  }

  T current_value() const {
    auto &p = coro.promise();
    if (auto g = std::get_if<generator>(&p.state)) {
      return g->current_value();
    } else if (auto v = std::get_if<T>(&p.state)) {
      return *v;
    } else {
      std::terminate();
    }
  }

  generator(const generator &) = delete;
  generator(generator &&that) : coro(that.coro) { that.coro = {}; }

  ~generator() {
    if (coro) {
      coro.destroy();
    }
  }

private:
  generator() {}
  generator(std::coroutine_handle<promise_type> h) : coro(h) {}
  std::coroutine_handle<promise_type> coro;
};

template <class Fn, class T> void for_each(Fn &&fn, generator<T> &&generator) {
  while (generator.move_next()) {
    fn(generator.current_value());
  }
}

main.cpp

#include "bst.hpp"

#include <iostream>

int main() {
  auto tree = put(put(put(empty<int, char>(), 42, 'a'), 10, 'b'), 101, 'd');

  auto demo = [&](auto name, auto order) {
    std::cout << name << ':' << std::endl;
    for_each(
        [](auto kv) {
          std::cout << std::get<0>(kv) << ", " << std::get<1>(kv) << std::endl;
        },
        order(tree));
    std::cout << std::endl;
  };

  demo("pre_order", pre_order<int, char>);
  demo("in_order", in_order<int, char>);
  demo("post_order", post_order<int, char>);

  std::cout << "Bye!" << std::endl;

  return 0;
}