Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@polytypic
Last active January 20, 2024 17:08
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save polytypic/17ff7693d27d8ccf53ee47beaa166f45 to your computer and use it in GitHub Desktop.
Save polytypic/17ff7693d27d8ccf53ee47beaa166f45 to your computer and use it in GitHub Desktop.
Recursive generator using C++20 coroutines

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;
#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};
}
}
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)
#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());
}
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment