Coroutine Tutorial: Generators

Preface

要掌握 C++20 协程，仅仅看完文档是远远不够的。C++ 和其他语言的协程的最大不同点在于，C++ 提供了最少量的编译器实现和极大量的「可定制点」，而其他语言可能连「调度器」都给用户准备好了。

在茫茫多的可定制点面前，如果你能一眼看出「为什么 C++ 要这样设计」，那么我愿称你为天才。否则，还是从常见的范式下手，逐渐体会设计者的思想吧。

我们将从最简单的范式——Generator 下手。

本文力求概念定义的权威性，但无法做任何保证。

What is Generator

Generator 泛指一段序列（有限或无限长）的生成器。在协程的语境下，Generator 特指一个懒惰的协程，它每次运行时会在调用者线程同步地计算一个值，然后暂停自己，同时把值返回给调用者。

因为 Generator 在是在调用者线程下立即同步执行的，所以它不需要任何调度器。

Fibonacci 数列就是 Generator 的 hello-world。我们来看一看效果：

Generator<int> fibonacci(int a0, int a1) {
    co_yield a0;
    co_yield a1;

    for (int a2; true;) {
        a2 = a0 + a1;
        a0 = a1;
        a1 = a2;
        co_yield a2;
    }
};

int main() {
    for (int len=10; int i : fibonacci(1, 1)) {
        std::cout << i << std::endl;
        if (--len == 0) break;
    }
    return 0;
}

要实现这个效果，只要实现 Generator<T>，虽然很麻烦。

Why Generator

上一段例子很愚蠢，我随手写一个 struct Fibo 重载 operator()，内置一个迭代器不香？为什么要大费周章实现 Generator，还要付出协程的运行时代价？

我也不知道为什么，纯纯为了学而学 Generator 可以免去你每次重新设计结构体的麻烦，无需你重写各种迭代器，可以看作一个又香又臭的语法糖。更进一步，Generator 可以很方便地相互嵌套，相比其他做法大大降低了编程复杂度。

Analyze How-to

希望你已经大致了解 C++ Coroutine 的运作方式，至少了解 co_await 关键字的作用。顺便推销一下我的另一篇文章 C++20 Coroutine，它可以帮助你记住 co_await。

现在按照协程的生命周期来分析 Generator<T>，看看它应该具有哪些接口和行为。

get_return_object

协程在初次进入的时候会调用 promise.get_return_object()，其返回值会在第一次暂停的时候返回给 caller。caller 要向协程索取返回值，通常只能通过这个return_object 去要，所以它相当于一个 handler。

按照 C++ 标准规定 promise.get_return_object() 的返回值必须是协程类型，也就是 Generator<T>，也好，省得我们思考了。

template<typename T>
class Generator {
  public:
    class promise_type {
      public:
        Generator get_return_object() noexcept {
            return Generator{<unspecified>};
        }
        // ...
    };
    // ...
};

inital_suspend

协程在初次进入的时候（且在上一步之后）会调用 co_await promise.inital_suspend()。我们希望的是协程不要做任何计算（懒惰），并且直接让出执行权给 caller。所以有如下设计：

template<typename T>
class Generator {
  public:
    class promise_type {
      public:
        Generator get_return_object() noexcept {
            return Generator{<unspecified>};
        }

        std::suspend_always initial_suspend() const noexcept { return {}; }
        // ...
    };
    // ...
};

别去找 std::suspend_always 的实现了，我已经给你准备好了：

struct suspend_always
{
  constexpr bool await_ready() const noexcept { return false; }

  constexpr void await_suspend(coroutine_handle<>) const noexcept {}

  constexpr void await_resume() const noexcept {}
};

struct suspend_never
{
  constexpr bool await_ready() const noexcept { return true; }

  constexpr void await_suspend(coroutine_handle<>) const noexcept {}

  constexpr void await_resume() const noexcept {}
};

可以看出，std::suspend_always 在被 co_await 的时候总是会让出执行权给 caller/resumer，而且不做任何调度。如果 caller/resumer 未来不将这个协程加入调度，那它就被永远遗忘在堆内存中了。

另一方面，可以发现 co_await std::suspend_always{} 的返回值总是 void。

caller resume

目前为止，一个协程已经构造好了，而且已经暂停了。用户程序大概长这个样子：

Generator<int> fibonacci(int a0, int a1) {
    // ...
}

int main() {
    Generator<int> fibo = fibonacci(1, 1);
    // 运行时，因为 co_await initial_suspend() 而跳出协程，执行到这里
    // fibo 就是我们要用的 handler
    // 要再入协程、获取返回值、销毁协程等等都要靠 fibo

    // ...
}

这时，我们想做两件事：

1. resume 一下 fibo，从而计算出第一个值
2. 通过 fibo 拿到第一个值

根据 C++ 标准，要恢复一个协程，必须持有对应的 std::coroutine_handle，换句话说 fibo 必须持有 std::coroutine_handle：

// ...
class Generator {
  public:
    class promise_type { /*...*/ };
    // ...
  private:
    std::coroutine_handle<promise_type> m_handle;
};

那 Generator 是由谁初始化的呢？别忘了，初始化的事是由 promise.get_return_object() 干的。

问题又来了，如何在 promise.get_return_object() 初始化 std::coroutine_handle？

我们要认识到以下事实：

&promise 和 coroutine_handle 一一对应，它们的偏移量是编译期已知的，可以互相换算。

也就是说，可以根据 promise 的地址算出协程的 std::coroutine_handle，也可以反过来用 std::coroutine_handle 换算出 promise 的地址。

template<typename T>
class Generator {
  public:
    class promise_type {
      public:
        Generator get_return_object() noexcept {
            return Generator{
                std::coroutine_handle<promise_type>::from_promise(*this)
            };
        }
        // ...
    };
    // ...

    Generator(std::coroutine_handle<promise_type> handle) noexcept
        : m_handle(handle) {}
  private:
    std::coroutine_handle<promise_type> m_handle;
};

std::coroutine_handle 的本质是指向协程帧的指针，通常按值传递。

现在，我们可以任意给 Generator 加成员方法，让它利用 m_handle 做任何事情，比如利用 fibo.m_handle.resume() 恢复协程，进行一次计算。

// ...
class Generator {
  public:
    class promise_type { /*...*/ };
    // ...

    void next() { m_handle.resume(); } // 计算下一个值
  private:
    std::coroutine_handle<promise_type> m_handle;
};

co_yield

现在，用户调用了 fibo.next()，协程被恢复执行。现在我们想返回第一个值给用户，意味着必须暂停协程，归还执行权。C++ 给我们提供了关键字 co_yield，它是一个语法糖，co_yield expr 等价于 co_await promise.yield_value(expr)。

所以在 promise.yield_value(expr) 里面，我们要做两件事：

1. 将 expr 保存在 promise 里面，便于外部访问。
2. 返回一个 std::suspend_always{}，令 caller 重获执行权。

template<typename T>
class Generator {
  public:
    class promise_type {
      public:
        const T &result() const noexcept { return m_value; }

        std::suspend_always yield_value(T value) noexcept {
            m_value = value;
            return {};
        }
        // ...

      private:
        T m_value;
    };

  public:
    const T &result() const noexcept { return m_handle.promise().result(); }
    void next() { m_handle.resume(); }
    // ...

  private:
    std::coroutine_handle<promise_type> m_handle;
};

std::coroutine_handle<Promise>::promise() 可以拿到对应的 promise 对象，从而拿到计算结果。但请特别小心协程可能已经被销毁！

从容器的角度看，T m_value 是一个很烂的设计，仅供示意，请勿模仿！

Finish the leftover

现在，Generator 已经具备我们所需的全部功能，但还有一些手续要办：

1. 异常处理
2. 定义 co_return 的行为

uncaught exception handler

协程运行时没有被显式 catch 的异常会导致立即调用 promise.unhandled_exception()，紧接着调用 co_await promise.final_suspend()。

简单起见，我们先不处理异常，留下一个空函数就行。

// ...
class promise_type {
    void unhandled_exception() const noexcept {}
    // ...
};
// ...

define co_return

协程可以显式 co_return [expr]，或者因为执行完函数体而隐式 co_return。

我们的 fibonacci 不需要 co_return 任何东西，但是作为一篇负责任的教程，我还是会告诉你：

co_return expr; 会调用 promise.return_value(expr)，随后析构协程内的自动变量，但 promise 和协程参数仍然存活。

类似地 co_return; 或者 co_return (void)expr; 会调用 promise.return_void()。

return_value(expr) 和 return_void() 是我们访问协程内自动变量的最后机会。但是 promise 和协程参数仍会存活。

return_xxx() 和 自动变量析构后，协程执行 co_await promise.final_suspend()，若协程不暂停，则协程帧析构：

1. 析构 promise
2. 析构协程参数
3. 释放堆空间
4. 转移执行权

若协程暂停，就只能通过 std::coroutine_handle::destroy() 来显式析构，无论是否已经析构都不能再 resume。

关于协程的各类元素的生命周期，是一大坑点，未来我会撰写一篇文章来表述。

言归正传，我们只要随便写一个 final_suspend() 就好，反正这个 Generator 永远不会 co_return。

Demo: fibonacci

#include <iostream>
#include <coroutine>

template<typename T>
class Generator {
  public:
    class promise_type {
      public:
        Generator get_return_object() noexcept {
            return Generator{
                std::coroutine_handle<promise_type>::from_promise(*this)};
        }

        void return_void() const noexcept {}

        std::suspend_always initial_suspend() const noexcept { return {}; }

        std::suspend_always final_suspend() const noexcept { return {}; }

        const T &result() const noexcept { return m_value; }

        std::suspend_always yield_value(T value) noexcept {
            m_value = value;
            return {};
        }

        void unhandled_exception() const noexcept {}

        ~promise_type() { std::cout << "~promise_type\n"; }

      private:
        T m_value;
    };

  public:
    const T &result() const noexcept { return m_handle.promise().result(); }

    Generator() noexcept : m_handle(nullptr) {}

    Generator(std::coroutine_handle<promise_type> handle) noexcept
        : m_handle(handle) {}

    ~Generator() {
        std::cout << "~Generator\n";
        if (m_handle) {
            std::cout << "m_handle.destroy()\n";
            m_handle.destroy();
        }
    }

    void next() { m_handle.resume(); }

  private:
    std::coroutine_handle<promise_type> m_handle;

    // TODO begin() end() operator*
};

Generator<int> fibo(int a0, int a1) {
    co_yield a0;
    co_yield a1;

    for (int a2; true;) {
        a2 = a0 + a1;
        a0 = a1;
        a1 = a2;
        co_yield a2;
    }
};

int main() {
    using namespace std;
    auto fi = fibo(1, 1);
    for (int i = 0; i < 10; ++i) {
        fi.next();
        cout << fi.result() << endl;
    }
    return 0;
}

Output:

1
1
2
3
5
8
13
21
34
55
~Generator
m_handle.destroy()
~promise_type

Conclusion and Prospect

我们实现了一个基本能用的 Generator，因为是入门教程，代码故意写得很糙，聪明的你一定知道如何改进。

如果你想自己造一个 Generator，那么还需要改进的地方至少有：

1. promise_type 内置一个更高效、安全的容器
2. Generator<T> 内置一个迭代器类，以支持 range for 循环。
3. 如果你很熟悉生命周期的坑点，promise_type 内置的容器可以仅存放指向协程自动变量的指针，进一步压缩空间，提升 yield 效率。
4. 利用 execution 来实现异步版本的 Generator。
5. 思考递归 yield 的效率问题，以及如何改进（难但秀）。

References

• C++20 Coroutine - 等疾风
• Coroutine (C++20) - cppreference
• cppcoro - lewissbaker
• 协程上手经典案例：实现一个序列生成器 - Benny Huo

Some Slight Improvements

1. 使用 std::optional 来做容器，自动调用正确的构造/析构函数，支持移动语义。(可以进一步改用 std::variant)。
2. 定义了 Generator 的几个构造和赋值函数，增强了安全性(safety)。
3. 在 unhandled_exception() 内存放了 std::exception_ptr。
4. 用例改为稍微复杂一些的字符串生成，里面有一些性能问题，读者有兴趣的可以找找茬。

#include <optional>
#include <coroutine>
#include <exception>

#include <iostream>
#include <random>
#include <cmath>

// 使 Generator::promise_type  成为一个更安全高效的单元素容器
// 限制了 Generator 的所有权，删除了默认构造，拷贝构造和拷贝赋值
// Generator 保证在构造后持有
// coroutine_handle，但可能被移动走，所以析构时要检查非空
// TODO 迭代器，异常传播

template<typename T>
class Generator {
  public:
    class promise_type {
      public:
        promise_type() noexcept = default;

        Generator get_return_object() noexcept {
            return Generator{
                std::coroutine_handle<promise_type>::from_promise(*this)};
        }

        void return_void() const noexcept {}

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

        const T &result() const noexcept { return *m_value; }
        T &result() noexcept { return *m_value; }

        std::suspend_always yield_value(const T &value) noexcept {
            m_value = value;
            return {};
        }

        std::suspend_always yield_value(T &&value) noexcept {
            m_value.emplace(std::move(value));
            return {};
        }

        void unhandled_exception() { m_exception = std::current_exception(); }

      private:
        std::optional<T> m_value;
        std::exception_ptr m_exception;
    };

  public:
    const T &result() const noexcept { return m_handle.promise().result(); }
    T &result() noexcept { return m_handle.promise().result(); }

    Generator() = delete;

    Generator(std::coroutine_handle<promise_type> handle) noexcept
        : m_handle(handle) {}

    Generator(const Generator &) = delete;

    Generator &operator=(const Generator &) = delete;

    Generator &operator=(Generator &&other) noexcept {
        if (this != other) {
            m_handle = other.m_handle;
            other.m_handle = nullptr;
        }
        return *this;
    }

    ~Generator() {
        if (m_handle) m_handle.destroy();
    }

    void next() { m_handle.resume(); }

  private:
    std::coroutine_handle<promise_type> m_handle;

    // TODO begin() end() operator* operator->
};

Generator<std::string> lottery(size_t size, unsigned int mod) {
    std::mt19937 rng(time(nullptr));
    std::string winningNumbers;
    {
        const size_t numLen = std::to_string(mod - 1).size();
        winningNumbers.reserve(size * (numLen + 1));
    }

    co_yield winningNumbers += std::to_string(rng() % mod);

    for (size_t i = 1; i < size; ++i) {
        winningNumbers += " ";
        co_yield winningNumbers += std::to_string(rng() % mod);
    }
};

int main() {
    using namespace std;
    auto fi = lottery(10, 256);
    for (int i = 0; i < 10; ++i) {
        fi.next();
        cout << fi.result() << endl;
    }
    return 0;
}

Output:

253
253 148
253 148 56
253 148 56 2
253 148 56 2 179
253 148 56 2 179 41
253 148 56 2 179 41 96
253 148 56 2 179 41 96 10
253 148 56 2 179 41 96 10 125
253 148 56 2 179 41 96 10 125 123