C++ Coroutine 入门

七辰

目标

c++20 虽然引入了coroutine，但是众所周知C++20对Coroutines的库支持基本等于没有， c++23 才有 std::generator。
generator 可以说是 coroutine 最常见的使用类型，c++23 不知道什么时候才能用上，这篇文章就来分析一下 如何使用 coroutine实现 一个generator，目标见下面的代码
Generator<uint32_t> Func(uint32_t n) {
  co_yield n;
  if (n > 0) {
    co_yield Func(n - 1);
  }
}
...
auto g = Func(10);
for (const auto& i : g) {
  std::cout << std::format("{} \n", j); // 10 9 8 ... 0
}
最终结果的完整代码见 https://github.com/MarcusMogg/coroutine
基本Generator

上面的目标其实比较复杂，Generator需要支持递归。让我们先从一个简单的Generator开始，支持最简单的迭代生成 斐波那契数列。
SimpleGenerator<int> Fib(int n) {
  if (n == 0 || n == 1) {
    co_return;
  }
  int a = 0, b = 1;
  co_yield a;
  co_yield b;

  for (int i = 2; i <= n; ++i) {
    co_yield a + b;

    b = a + b;
    a = b - a;
  }
  co_return;
}
基础结构

参考之前的 (摸鱼王：C++ Coroutine 入门 -  cppreference 示例简析) ， 我们首先要做的还是一个支持 协程切换的简单结构，代码如下。
template <typename T>
class SimpleGenerator {
public:
  struct promise_type;
  using handle_type = std::coroutine_handle<promise_type>;
  struct promise_type {
    auto co() { return handle_type::from_promise(*this); }
    auto get_return_object() { return SimpleGenerator(co()); }
    std::suspend_always initial_suspend() { return {}; }
    std::suspend_always final_suspend() noexcept { return {}; }
    void unhandled_exception() { throw; }
    void return_void() {}
  };

  explicit SimpleGenerator(handle_type h) : h_(h) {}
  ~SimpleGenerator() {
    if (h_) {
      h_.destroy();
    }
  }

  handle_type h_; // 表示和当前对象关联的协程handle
};
代码比较简单，具体分析可以看我之前的文章。
yield_value

接下来就是真正支持 co_yield。
事实上， co_yield 表达式 等价于 co_await promise.yield_value(表达式)， 所以我们要做的就是在SimpleGenerator::promise_type 里支持 yield_value 函数。
最简单的写法如下
template <typename T>
class SimpleGenerator {
...
  struct promise_type {
    T value_;
    ...
    std::suspend_always yield_value(T& value) {
      value_ = std::forward<T>(value);
      return {};
    }
    std::suspend_always yield_value(T&& value) {
      value_ = std::forward<T>(value);
      return {};
    }
    T& value() { return value_; }
  };
  ...
};
co_await 接受一个 awaitable对象，这里 yield_value 这里直接使用了标准库中的 std::suspend_always， 也就是每次co_yield都会挂起当前协程。
promise 中缓存了 yield 的结果，所以在generator中可以直接使用h_.promise().value() 获取当前结果。
到此就结束了吗？ 不，我们应该仔细思考一下promise中缓存value的类型。
上面的代码直接使用T 作为 value的类型，然后使用完美转发进行赋值， 所以这里必然会有一次 T类型的 拷贝或者移动， 这个操作能否避免 ？答案是肯定的，我们完全可以使用指针来避免这次操作，即
template <typename T>
class SimpleGenerator {
...
  struct promise_type {
    using pointer = std::add_pointer_t<T>;
    pointer value_;
    ...
    std::suspend_always yield_value(T& value) {
      value_ = std::addressof(value);
      return {};
    }
    std::suspend_always yield_value(T&& value) {
      value_ = std::addressof(value);
      return {};
    }
    T& value() { return *value_; }
  };
  ...
};
这似乎违背了我们之前c++中的经验，返回函数内部声明对象的指针是经典危险操作
T* UBfunc() {
    return &T{};
}
那为什么 co_yield 就可以呢？
c++协程在创建时 会 new 一个协程状态coroutine state对象，分配在堆上。协程状态 包含 承诺promise 对象，各个形参、生命周期跨过暂停点的局部变量和 临时对象，并将这些对象分配在堆上。
co_yield T{}; 会生成一个T类型的临时对象，这个对象的创建实在语句执行开始时，销毁是在语句执行完成后，也就是说这个临时对象 生命周期跨过暂停点，所以它会在堆上而不是栈上进行分配，在协程 resume完成之前，我们使用这个临时对象是安全的！
支持迭代器

好了，到现在为止，我们事实上已经完成了 对  斐波那契数列生成函数的支持，可以这样调用了
auto g = Fib(n);
  while (!g.h_.done()) {
    g.h_.resume();
    auto value = g.h_.promise().value();
    ...
  }
但这样调用无疑很蠢，更好的方式无疑是迭代器（c++20应该是 range）了。简单支持一下迭代器。
// 空对象，只是为了兼容迭代器模式
struct GeneratorEnd {};

template <typename HandleType, typename ValueType>
struct GeneratorIter {
  using iterator_category = std::input_iterator_tag;
  using difference_type = std::ptrdiff_t;
  using value_type = std::remove_reference_t<ValueType>;
  using reference = std::conditional_t<std::is_reference_v<ValueType>, ValueType, ValueType&>;
  using pointer = std::add_pointer_t<ValueType>;

  bool operator!=(const GeneratorEnd&) { return !h.done(); }
  void operator++() { h(); }
  value_type& operator*() { return h.promise().value(); }

  HandleType h;
};

template <typename T>
class SimpleGenerator {
public:
  ...
  auto end() const { return GeneratorEnd{}; }
  auto begin() {
    auto it = GeneratorIter<handle_type, T>{h_};
    // 我们的promise是lazy模式，第一次创建的时候会挂起，不会执行到第一个暂停点
    if (!begin_) {
      ++it;
      begin_ = true;
    }
    return it;
  }

private:
  ...
  bool begin_ = false;
};
完整代码见 https://github.com/MarcusMogg/coroutine/blob/master/src/cxx20_generator.h
递归Generator

原理分析

对比一下递归和普通yield，Generator看起来只需要支持Generator::yield_value(Generator&& g) ，但是我们并不能把子协程的值全部缓存到一个promise对象里。
回顾一下普通函数的调用，就像一个栈 ， 支持递归的generator也应该像一个栈一样，最外层调用（root节点）持有一个协程handle，这个handle持有其子协程的handle，然后一直递归下去，直到最里层的协程（称为leaf节点），其持有当前generator的暂停点。
参考上面的想法，我们的promise需要改造一下
template <typename T>
class RecursiveGenerator {
...
  struct promise_type {
    using pointer = std::add_pointer_t<T>;
    pointer value_;
    promise_type* parent_; // 当前节点的父节点
    promise_type* root_;
    promise_type* leaf_;
    ...
    promise_type() : value_(nullptr), parent_(nullptr), root_(this), leaf_(this) {}
  };
  ...
};
然后按照递归的套路，我们将问题简化为只考虑 子问题 和 结束点，也就是考虑 子协程是如何执行和终止的。
子协程开始

也就是 co_yield Generator{} 时，我们应该怎么处理 Generator::yield_value(Generator&& g)  函数？想想需要做什么，需要持有子generator，挂起当前协程，让子协程开始执行，而这些都是由  co_await awaitable中 awaitable对象决定的。
首先是 子generator 的生命周期，在子generator执行完之前，需要一直存活。仔细想想 ，这其实就是 co_await awaitable中 awaitable对象的生命周期，所以我们完全可以在 awaitable 中存储 子generator。即
auto yield_value(RecursiveGenerator&& g) {
  struct YieldAwaitable {
    YieldAwaitable(RecursiveGenerator&& g) : g_(std::forward<RecursiveGenerator>(g)) {}
    bool await_ready();
    ? await_suspend(handle_type h);
    void await_resume() noexcept {} // 暂时不在resume时做任何事
    RecursiveGenerator g_;
  };
  return YieldAwaitable(std::move(g));
}
那这个awaitable对象应该如何执行呢？
首先是 await_ready , 肯定是要返回false，这样才回去执行 await_suspend 函数。但是这里要考虑到 可以 co_yield 一个已经执行完的 generator，这时 其实可以忽略直接往下执行。所以这里只需要判断一下 子协程是否为空即可。
bool await_ready() noexcept { return !g_.h_; }
那await_suspend 需要做什么呢？ 首先就是 子协程的入栈。await_suspend的参数表示当前协程（父协程），我们需要把子协程设置为叶子节点
? await_suspend(handle_type h) noexcept
  auto& current = h.promise();
  auto& nested = g_.h_.promise();
  auto& root = current.root_;
  // merge g to h
  nested.parent_ = &current;
  nested.root_ = root;
  root->leaf_ = &nested;
  ...
}
子协程入栈之后就结束了吗？不是。调用方希望获取下一个生成的value，而现在子协程没有执行，如果我们直接让出协程到 调用方的话，它会获取上一次 yield的value，这显然不符合预期。 所以此时应该让出当前协程 给 子协程执行， 而这个可以通过await_suspend 返回值决定。

如果 await_suspend 返回 void，那么立即将控制返回给当前协程的调用方/恢复方（此协程保持暂停），否则     如果 await_suspend 返回 bool，那么：         -   值为 true 时将控制返回给当前协程的调用方/恢复方         -   值为 false 时恢复当前协程。     如果 await_suspend 返回某个其他协程的协程句柄，那么（通过调用 handle.resume()）恢复该句柄（注意这可以连锁进行，并最终导致当前协程恢复）

所以完整代码如下：
std::coroutine_handle<> await_suspend(handle_type h) noexcept {
  auto& current = h.promise();
  auto& nested = g_.h_.promise();
  auto& root = current.root_;
  // merge g to h
  nested.parent_ = &current;
  nested.root_ = root;
  root->leaf_ = &nested;
  return g_.h_; // 唤醒子协程
}
子协程挂起

即 调用 co_yield T{} 时，这和之前的唯一区别是 value指针的持有者
template <typename T>
class RecursiveGenerator {
...
  struct promise_type {
    ...
    std::suspend_always yield_value(T& value) {
      root_->value_ = std::addressof(value);
      return {};
    }
    std::suspend_always yield_value(T&& value) {
      root_->value_ = std::addressof(value);
      return {};
    }
    T& value() { return *root_->value_; }
  };
  ...
};
子协程重入

调用方只持有最外层的 genenrator ,但是重入的时候其实要唤醒最里层的 协程（即 leaf）
template <typename T>
class RecursiveGenerator {
...
  struct promise_type {
    ...
    void resume() { handle_type::from_promise(*leaf_).resume(); }
  };
  ...
  struct iterator {
    ...
    // 调用我们自己定义的resume，而不是handle_type 自己的resume
    void operator++() { h.promise().resume(); }
    ...
  };
};
子协程结束

协程执行完成之后我们需要将其弹出栈，并恢复父协程的执行。这和子协程开始非常类似。
c++ 提供了 awaitable final_suspend() 来供我们自定义协程结束事件
template <typename T>
class RecursiveGenerator {
...
  struct promise_type {
    ...
    auto final_suspend() noexcept {
      struct FinalAwaitable {
        // 让出协程
        bool await_ready() noexcept { return false; }
        std::coroutine_handle<> await_suspend(std::coroutine_handle<promise_type> h) noexcept {
          auto& promise = h.promise();
          auto parent = h.promise().parent_;
          // 如果有父节点，将leaf设置为父节点
          // 然后恢复父节点的执行
          if (parent) {
            promise.root_->leaf_ = parent;
            return handle_type::from_promise(*parent);
          }
          // 啥都不做 https://en.cppreference.com/w/cpp/coroutine/noop_coroutine
          return std::noop_coroutine();
        }
        void await_resume() noexcept {}
      };
      return FinalAwaitable{};
    }
  };
  ...
};
实现了上述的过程，generator了就可以支持递归 。
完整代码见https://github.com/MarcusMogg/coroutine/blob/master/src/recursive_generator.hpp
TODO

上述过程 ，功能已经齐全，但是实际使用还是有些点需要更加细致的考虑，比如

• 更加完善的迭代器
  
• 支持range
  
• 支持子协程抛出异常
  
• 子协程内部手动使用 await 如何处理？
  
• .....