C++コルーチン拡張メモ

次期標準 C++20 に向けて導入が検討されている「コルーチン(Coroutine)」のお勉強メモ。

2020年6月現在、C++20 言語仕様へのコルーチン導入は正式に決定している。https://cpprefjp.github.io/lang/cpp20/coroutines.html 参照。


2018年4月現在、<del>プログラミング言語C++の正式機能としてではなく、コルーチン拡張(Coroutines TS)として仕様定義される。[Clang 5][clang5]以降でサポート（要`-fcoroutines-ts`オプション）。</del>

[clang5]: http://releases.llvm.org/5.0.0/tools/clang/docs/ReleaseNotes.html#c-coroutines

# 遅延実行
https://wandbox.org/permlink/v3DCYQ97szuIy6kk

```cpp:C++11
#include <future>
#include <iostream>

// 通常関数の定義
int AtLtUaE()
{
  std::cout << "answer to life the universe and everything" << std::endl;
  return 42;
}

int main()
{
  // 通常関数AtLtUaEを遅延実行する
  auto ftr = std::async(std::launch::deferred, AtLtUaE);

  // (その他の処理)
  std::cout << "(other stuff)" << std::endl;

  // 関数の遅延実行＆結果取得
  int answer = ftr.get();
  std::cout << "answer=" << answer << std::endl;
}
```

https://wandbox.org/permlink/mqGsm6BRVpXmR6Jz

```cpp:CoroutinesTS
#include <iostream>
#include <experimental/coroutine>  // CoroutinesTS

// コルーチンの戻り値my_future型
struct my_future {
  // コルーチン内部で利用されるpromise_type型
  struct promise_type {
    int result_ = 0;
    auto get_return_object() { return my_future{handle_type::from_promise(*this)}; }
    std::experimental::suspend_always initial_suspend() { return {}; }
    std::experimental::suspend_always final_suspend() { return {}; }
    void return_value(int value) { result_ = value; }
    void unhandled_exception() { std::terminate(); }
  };
  using handle_type = std::experimental::coroutine_handle<promise_type>;

  explicit my_future(handle_type h)
    : coro_(h) {}
  my_future(const my_future&) = delete;
  my_future(my_future&& rhs)
    : coro_(rhs.coro_) { rhs.coro_ = nullptr; }
  ~my_future()
  {
    if (coro_)
      coro_.destroy();
  }

  int get()
  {
    // コルーチン完了までコルーチン側の進行を促す
    while (!coro_.done()) {
      coro_.resume();
    }
    return coro_.promise().result_;
  }

  handle_type coro_;
};

// コルーチン(coroutine)定義
my_future AtLtUaE()
{
  std::cout << "answer to life the universe and everything" << std::endl;
  co_return 42;
  // return ではなく co_return キーワードを利用することで、
  // 通常関数ではなくコルーチン(coroutine)として解釈される。
}

int main()
{
  // コルーチンを開始する
  auto ftr = AtLtUaE();
  // promise_type::initial_suspendがsuspend_alwaysを返すため、
  // コルーチン本体実行は開始されず(suspend状態)後続処理が実行される。

  // (その他の処理)
  std::cout << "(other stuff)" << std::endl;

  // コルーチン完了待ち＆結果取得
  int answer = ftr.get();
  std::cout << "answer=" << answer << std::endl;
}
```

実行結果：

```
(other stuff)
answer to life the universe and everything
answer=42
```


# ジェネレータ(1)
https://wandbox.org/permlink/QdmuJQyztvF3BqDV

```C++:CoroutinesTS
#include <iostream>
#include <experimental/coroutine>  // CoroutinesTS

// コルーチンの戻り値generator型
struct generator {
  // コルーチン内部で利用されるpromise_type型
  struct promise_type {
    int value_ = 0;
    auto get_return_object() { return generator{handle_type::from_promise(*this)}; }
    std::experimental::suspend_always initial_suspend() { return {}; }
    std::experimental::suspend_always final_suspend() { return {}; }
    std::experimental::suspend_always yield_value(int value)
    {
      value_ = value;
      // co_yield文のたびにコルーチン(ジェネレータ)処理をsuspendし、
      // ジェネレータ利用側からの値取得current_valueと処理進行を促す。
      return {};
    }
    void return_void() {}
    void unhandled_exception() { std::terminate(); }
  };
  using handle_type = std::experimental::coroutine_handle<promise_type>;

  explicit generator(handle_type h)
    : coro_(h) {}
  generator(const generator&) = delete;
  generator(generator&& rhs)
    : coro_(rhs.coro_) { rhs.coro_ = nullptr; }
  ~generator()
  {
    if (coro_)
      coro_.destroy();
  }

  int current_value() {
    return coro_.promise().value_;
  }

  bool move_next() {
    // コルーチン処理を次のco_yield/co_returnまで進める
    coro_.resume();
    // 本プログラムの場合、ジェネレータはco_returnを呼び出さないため
    // coro_.done()は常にfalseとなり、本関数の戻り値は常にtrueとなる。
    return !coro_.done();
  }

  handle_type coro_;
};

// コルーチン(coroutine)定義
generator fibonacci()
{
  int a = 1, b = 1;
  co_yield a;
  while (true) {
    co_yield a;
    int t = a;
    a += b;
    b = t;
  }
  // 無限ループ構造となっているが、co_yieldキーワードによって
  // 値を1回生成するたびにコルーチン処理をsuspendしている。

  // 仕様上はコルーチン末尾到達時は暗黙にco_return;が呼ばれるが、
  // 本コルーチン実装では無限ループ構造により到達することはない。
}

int main()
{
  // コルーチン(ジェネレータ)を開始する
  auto g = fibonacci();
  // promise_type::initial_suspendがsuspend_alwaysを返すため、
  // コルーチン本体実行は開始されず(suspend状態)後続処理が実行される。

  while ( g.move_next() ) {
    // コルーチン(ジェネレータ)処理を次のco_yieldまで1ステップ進める。
    // 本プログラムの場合、ジェネレータはco_returnを呼び出さないため
    // move_next()関数呼び出しは常に値true(処理継続)を返す。
    int n = g.current_value();
    if (100 < n)
      break;
    std::cout << n << " ";
  }
}
```

実行結果：

```
1 1 2 3 5 8 13 21 34 55 89
```


# ジェネレータ(2)
https://wandbox.org/permlink/OuHWIATnpsyxdKhg

```cpp:CoroutinesTS
#include <iostream>
#include <experimental/coroutine>  // CoroutinesTS

// コルーチンの戻り値generator型
struct generator {
  // コルーチン内部で利用されるpromise_type型
  struct promise_type {
    int value_ = 0;
    auto get_return_object() { return generator{handle_type::from_promise(*this)}; }
    std::experimental::suspend_never  initial_suspend() { return {}; }
    std::experimental::suspend_always final_suspend() { return {}; }
    std::experimental::suspend_always yield_value(int value)
    {
      value_ = value;
      // co_yield文のたびにコルーチン(ジェネレータ)処理をsuspendし、
      // ジェネレータ利用側からのiterator経由値取得と処理進行を促す。
      return {};
    }
    void return_void() {}
    void unhandled_exception() { std::terminate(); }
  };
  using handle_type = std::experimental::coroutine_handle<promise_type>;

  explicit generator(handle_type h)
    : coro_(h) {}
  generator(const generator&) = delete;
  generator(generator&& rhs)
    : coro_(rhs.coro_) { rhs.coro_ = nullptr; }
  ~generator()
  {
    if (coro_)
      coro_.destroy();
  }

  // range-based for構文サポート用イテレータ
  struct iterator {
    generator* owner_;
    iterator& operator++()
    {
      // イテレータの前置インクリメント演算子呼び出し時に、
      // コルーチン(ジェネレータ)の処理を1ステップ進める。
      if (!owner_->coro_.done())
        owner_->coro_.resume();
      return *this;
    }
    int operator*()
    {
      return owner_->coro_.promise().value_;
    }
    bool operator!=(const iterator&) const
    {
      return (!owner_ || !owner_->coro_.done());    
    }
  };

  iterator begin() { return {this}; }
  iterator end() { return {nullptr}; }

  handle_type coro_;
};

// コルーチン(coroutine)定義
generator gen_range(int minval, int maxval)
{
  // promise_type::initial_suspendはsuspend_neverを返すため、
  // コルーチン呼び出しによって初回のco_yield呼び出しまで実行される。
  for (int i = minval; i <= maxval; i++)
    co_yield i;

  // コルーチン末尾到達時は暗黙にco_return;が呼ばれる。
}

int main()
{
  for (auto n : gen_range(1, 10)) {
    std::cout << n << " ";
  }
}
```

実行結果：

```
1 2 3 4 5 6 7 8 9 10 
```

最適化：https://godbolt.org/g/MFx3w4


# ジェネレータ(3)

https://wandbox.org/permlink/LkIT42bSX4PSlve5

```cpp:CoroutinesTS
#include <iostream>
#include <experimental/coroutine>  // CoroutinesTS

// コルーチンの戻り値generator型
struct generator {
  // コルーチン内部で利用されるpromise_type型
  struct promise_type {
    double send_val_ = 0;
    double yield_val_ = 0;
    auto get_return_object() { return generator{handle_type::from_promise(*this)}; }
    std::experimental::suspend_never  initial_suspend() { return {}; }
    std::experimental::suspend_always final_suspend() { return {}; }
    auto yield_value(double value)
    {
      yield_val_ = value;
      // await_resumeメンバ関数を除いてsuspend_alwaysと同じ動作をする型
      // await_resumeメンバ関数の戻り値がco_yield式の評価結果となる。
      struct awaiter {
        promise_type* self_;
        bool await_ready() { return false; }
        void await_suspend(std::experimental::coroutine_handle<>) {}
        auto await_resume() { return self_->send_val_; }
      };
      // co_yield式のたびにコルーチン(ジェネレータ)処理をsuspendし、
      // ジェネレータ利用側への値返却(next戻り値)と処理進行を促す。
      // またco_yield式評価結果としてnext関数への指定値を返す。
      return awaiter{this};
    }
    void return_void() {}
    void unhandled_exception() { std::terminate(); }
  };
  using handle_type = std::experimental::coroutine_handle<promise_type>;

  explicit generator(handle_type h)
    : coro_(h) {}
  generator(const generator&) = delete;
  generator(generator&& rhs)
    : coro_(rhs.coro_) { rhs.coro_ = nullptr; }
  ~generator()
  {
    if (coro_)
      coro_.destroy();
  }

  double send(double value) {
    coro_.promise().send_val_ = value;
    if (!coro_.done())
      coro_.resume();
    return coro_.promise().yield_val_;
  }

  handle_type coro_;
};

// コルーチン(coroutine)定義
generator average()
{
  double acc = co_yield 0;  
  size_t num = 1;
  for (;;) {
    acc += co_yield (acc / num);
    num += 1;
  }
}

int main()
{
  auto g = average();
  std::cout << g.send(10) << " ";
  std::cout << g.send(20) << " ";
  std::cout << g.send(5)  << " ";
  std::cout << g.send(15) << " ";
}
```

出力結果：

```
10 15 11.6667 12.5
```

最適化：https://godbolt.org/g/iS5dw8


# 非同期処理

https://wandbox.org/permlink/rPKkxpz2oWuv21mx

```cpp:CoroutinesTS
#include <future>
#include <iostream>
#include <thread>
#include <experimental/coroutine>  // CoroutinesTS

// コルーチンの戻り値my_future型
struct my_future {
  // コルーチン内部で利用されるpromise_type型
  struct promise_type {
    std::promise<int> promise_;
    auto get_return_object()
    {
      // promise/futureペアとコルーチンハンドラを生成し、
      // promise_type型からmy_future型を構築する。
      return my_future{promise_.get_future(), handle_type::from_promise(*this)};
    }
    std::experimental::suspend_never  initial_suspend() { return {}; }
    std::experimental::suspend_always final_suspend() { return {}; }
    void return_value(int value) { promise_.set_value(value); }
    void unhandled_exception() { std::terminate(); }

    // コルーチン内の co_await <duration>待機処理 をサポート
    template <class Rep, class Period>
    auto await_transform(const std::chrono::duration<Rep, Period>& d)
    {
      struct awaiter {
        std::chrono::duration<Rep, Period> d_;
        bool await_ready() { return false; }
        void await_suspend(handle_type h)
        {
          // 指定時間経過後にコルーチンをresumeするワーカスレッドを生成。
          std::thread([h, d=d_]() mutable {
            std::this_thread::sleep_for(d);
            if (!h.done())
              h.resume();
          }).detach();
          // 本プログラムでは簡単のためワーカスレッドを毎回生成しているが、
          // より効率的な実装としてスレッドプール方式などが考えられる。
          // 非同期I/Oを行う場合も同様にresume操作を行うスレッドが必要。
        }
        void await_resume() {}
      };
      return awaiter{d};
    }
  };
  using handle_type = std::experimental::coroutine_handle<promise_type>;

  explicit my_future(std::future<int> f, handle_type h)
    : future_(std::move(f)), coro_(h) {}
  my_future(const my_future&) = delete;
  my_future(my_future&& rhs)
    : future_(std::move(rhs.future_)), coro_(rhs.coro_) { rhs.coro_ = nullptr; }
  ~my_future()
  {
    if (coro_)
      coro_.destroy();
  }

  int get()
  {
    // promise_type::initial_suspendがsuspend_neverを返すため、
    // コルーチンはco_await待機中または実行完了状態のいずれかにある。
    return future_.get();
  }

  std::future<int> future_;
  handle_type coro_;
};


// コルーチン(coroutine)定義
my_future async_AtLtUaE()
{
  using namespace std::chrono_literals;
  std::cout << "answer to life the universe and everything" << std::endl;
  co_await 2s;
  std::cout << "." << std::flush;
  co_await 2s;
  std::cout << "." << std::flush;
  co_await 2s;
  std::cout << "." << std::endl;
  co_return 42;
  // co_await式の前後で実行スレッドが切り替わることに注意。
  // 本コルーチンの処理は4個のスレッドにより順次実行されることになる。
  // （1個目のco_wait式まではメインスレッドで実行される）
}

// コルーチン(coroutine)定義
my_future sync_AtLtUaE()
{
  std::cout << "(prepare)" << std::endl;

  auto ftr = async_AtLtUaE();

  std::cout << "(processing)" << std::endl;

  co_return ftr.get();
}

int main()
{
  auto ftr = sync_AtLtUaE();

  std::cout << "(other stuff)" << std::endl;

  int answer = ftr.get();
  std::cout << "answer=" << answer << std::endl;
}
```

実行結果：

```
(prepare)
answer to life the universe and everything
(processing)
...
(other stuff)
answer=42
```


# Optionalモナド風
https://wandbox.org/permlink/rHpvhyar77P493Ij

```cpp:CoroutinesTS
#include <optional>
#include <iostream>
#include <experimental/coroutine>  // CoroutinesTS

template <typename T>
struct coro_optional;

// コルーチン内部で利用されるoptional_promise型
template <typename T>
struct optional_promise {
  std::optional<T> value_;

  coro_optional<T> get_return_object();
  std::experimental::suspend_never  initial_suspend() { return {}; }
  std::experimental::suspend_always final_suspend() { return {}; }
  void return_value(T value) { value_ = value; }
  void return_value(std::nullopt_t) { value_ = std::nullopt; }
  void unhandled_exception() { std::terminate(); }

  // コルーチン内の co_await optional<T> 式 をサポート
  auto await_transform(std::optional<T> opt)
  {
    // ここではco_await式を待機処理ではなく、Optionalモナド的な挙動
    // a) 有効値を保持しているときは、同値を返してコルーチンを継続実行する
    // b) 無効値(nullopt)を保持しているときは、コルーチンを継続しない
    // の実現のために利用する。
    struct awaiter {
      std::optional<T> opt_;
      // a) await_ready==trueのとき、コルーチンはsuspendされずに
      //    await_resumeの戻り値がco_await式の評価結果となる。
      // b) await_ready==falseのとき、コルーチンはsuspendされて
      //    await_suspendが呼び出される。同関数は何も処理を行わないため
      //    susupend状態が維持されたまま、最終的に破棄(destroy)される。
      bool await_ready() { return opt_.has_value(); }
      void await_suspend(std::experimental::coroutine_handle<>) {}
      T await_resume() { return std::move(opt_.value()); }
    };
    return awaiter{std::move(opt)};
  }
};

// コルーチンの(内部的)戻り値coro_optional型
template <typename T>
struct coro_optional {
  using handle_type = std::experimental::coroutine_handle<optional_promise<T>>;

  explicit coro_optional(handle_type h)
    : coro_(h) {}
  coro_optional(const coro_optional&) = delete;
  coro_optional(coro_optional&& rhs)
    : coro_(rhs.coro_) { rhs.coro_ = nullptr; }
   ~coro_optional()
  {
    if (coro_)
      coro_.destroy();
  }

  // コルーチンの(外部的)戻り値型optional<T>への型変換を提供
  operator std::optional<T>() const { return {coro_.promise().value_}; }

  handle_type coro_;
};

template <typename T>
inline
coro_optional<T> optional_promise<T>::get_return_object()
{
  using handle_type = std::experimental::coroutine_handle<optional_promise<T>>;
  return coro_optional<T>{ handle_type::from_promise(*this) };
}

// std::experimental::coroutine_traitsトレイトの特殊化によって、
// 戻り値型std::optional<T>を持つ関数をコルーチンとしてアダプトする。
namespace std::experimental {
template <typename T, typename... ArgTypes>
struct coroutine_traits<std::optional<T>, ArgTypes...> {
  // 該当コルーチンの(内部的)戻り値型はoptional_promise<T>となり、
  // 最終的にoperator std::optional<T>ユーザ定義型変換を適用する。
  using promise_type = optional_promise<T>;
};
}

// コルーチン(coroutine)定義: r = x - y
std::optional<int> minus(int x, int y)
{
  if (0 < x && 0 < y && x > y)
    co_return (x - y);
  else
    co_return std::nullopt;
}

// コルーチン(coroutine)定義: r = x / y
std::optional<int> division(int x, int y)
{
  if (0 < x && 0 < y && (x % y) == 0)
    co_return (x / y);
  else
    co_return std::nullopt;
}

// コルーチン(coroutine)定義: r = (x - 5) / y
std::optional<int> calc(int x, int y)
{
  // auto a = co_await minus(x, 5);
  // auto b = co_await division(a, y);
  // co_return b;
  co_return (co_await division(co_await minus(x, 5), y));

  // co_await optional<int>部分式では、optionalがnulloptのとき
  // それ以降の処理は継続せず、本コルーチンの戻り値もnulloptとなる。
}

int main()
{
  auto dump_opt = [](auto&& opt) {
    if (opt)
      std::cout << opt.value() << std::endl;
    else
      std::cout << "(nullopt)" << std::endl;
  };

  // 自然数の範囲内のみで (x - 5) / y を計算する
  dump_opt( calc(11, 3) );  // (11 - 5) / 3 == 2
  dump_opt( calc(7, 3) );   // (7  - 5) / 3 == NA
  dump_opt( calc(4, 3) );   // (4  - 5) == NA
}
```

実行結果：

```
2
(nullopt)
(nullopt)
```


# おまけ: Sleep Sort

https://gist.github.com/yohhoy/a5ec6d4aeeb4c60d3e4f3adfd1df9ebf
https://wandbox.org/permlink/5WhRC2ylx9P9QUwQ

Alt. ver: https://gist.github.com/yohhoy/ecdf00cb2a7852929954a1e6c79bdc25
https://wandbox.org/permlink/X6TaqpJ4egbulzq2


# WG21
- [P0664R4 C++ Coroutine TS Issues](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0664r4.html) (Adopted 2018-06)
- [P0912R5 Merge Coroutines TS into C++20 working draft](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0912r5.html) (Adopted 2019-03)
- [P0913R1 Add symmetric coroutine control transfer](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0913r1.html) (Adopted 2018-03)
- [P0914R1 Add parameter preview to coroutine promise constructor](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0914r1.html) (Adopted 2018-03)
- (PDF)[P0973R0 Coroutines TS Use Cases and Design
Issues](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0973r0.pdf)
- [P0975R0 Impact of coroutines on current and upcoming library facilities](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0975r0.html)
- [P0978R0 A Response to "P0973r0: Coroutines TS Use Cases and Design Issues"](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0978r0.html)
- [P0981R0 Halo: coroutine Heap Allocation eLision Optimization: the joint response](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0981r0.html)
- [P1241R0 In support of merging coroutines into C++20](http://open-std.org/JTC1/SC22/WG21/docs/papers/2018/p1241r0.html)
- (PDF)[P1365R0 Using Coroutine TS with zero dynamic allocations](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1365r0.pdf)