Coroutine task

Mircea Baja - 5 Sept 2023

# C++ coroutine mechanics

<div align="center">
<svg xmlns="http://www.w3.org/2000/svg" id="svg20230623-1-1" width="100%" viewBox="0 0 250 100">
  <style>
    #svg20230623-1-1 {
      border: 1px solid #e8e8e8;
      background-color: #f5f5f5;
    }
    .svg20230623-1-t1 {
      font-family: sans-serif;
      font-size: 16px;
      font-weight: bold;
      dominant-baseline: middle;
    }
    .svg20230623-1-task_blue {
      stroke: #000000;
      stroke-width: 4;
      fill: #2d93ad;
    }
    .svg20230623-1-task_purple {
      stroke: #000000;
      stroke-width: 4;
      fill: #9665ac;
    }
    .svg20230623-1-task_orange {
      stroke: #000000;
      stroke-width: 4;
      fill: #f5bb00;
    }
  </style>
  <rect x="-10" y="-10" width="80" height="80" class="svg20230623-1-task_purple"/>
  <rect x="70" y="-10" width="60" height="80" class="svg20230623-1-task_blue"/>
  <rect x="130" y="-10" width="30" height="80" class="svg20230623-1-task_orange"/>
  <rect x="160" y="-10" width="40" height="80" class="svg20230623-1-task_blue"/>
  <rect x="200" y="-10" width="60" height="80" class="svg20230623-1-task_purple"/>
  <rect x="-10" y="80" width="100" height="80" class="svg20230623-1-task_orange"/>
  <rect x="90" y="80" width="80" height="80" class="svg20230623-1-task_purple"/>
  <rect x="170" y="80" width="90" height="80" class="svg20230623-1-task_orange"/>
</svg>
</div>

---

# C++ functions reminder

<div align="center">
<svg xmlns="http://www.w3.org/2000/svg" id="svg20230623-13-1" width="100%" viewBox="0 0 800 290">
  <style>
    #svg20230623-13-1 {
      border: 1px solid #e8e8e8;
      background-color: #f5f5f5;
    }
    .svg20230623-13-l1 {
      stroke: #000000;
      stroke-width: 2;
      fill: none;
    }
    .svg20230623-13-l2 {
      stroke: #000000;
      stroke-width: 2;
      fill: none;
      stroke-dasharray: 5;
    }
    .svg20230623-13-task_white {
      stroke: #000000;
      stroke-width: 4;
      fill: #ffffff;
    }
    .svg20230623-13-task_grey {
      stroke: #000000;
      stroke-width: 4;
      fill: #cccccc;
    }
    .svg20230623-13-task_green {
      stroke: #000000;
      stroke-width: 4;
      fill: #c2b102;
    }
    .svg20230623-13-task_neutral2 {
      stroke: #000000;
      stroke-width: 4;
      fill: #6ac3d9;
    }
  </style>
  <rect x="10" y="10" width="100" height="20" class="svg20230623-13-task_grey"/>
  <rect x="10" y="30" width="100" height="80" class="svg20230623-13-task_green"/>
  <rect x="10" y="110" width="100" height="20" class="svg20230623-13-task_green"/>
  <rect x="10" y="130" width="100" height="60" class="svg20230623-13-task_green"/>
  <rect x="10" y="190" width="100" height="30" class="svg20230623-13-task_green"/>
  <rect x="10" y="220" width="100" height="55" class="svg20230623-13-task_white"/>
  <text class="svg20230623-13-t1" x="120" y="212">1. return value</text>
  <text class="svg20230623-13-t1" x="120" y="167">2. arguments</text>
  <text class="svg20230623-13-t1" x="120" y="127">3. return address</text>
  <text class="svg20230623-13-t1" x="120" y="77">4. local variables</text>
</svg>
</div>

- optimisations are on top of this model e.g.:
 - return value and arguments might be passed via registers (calling
   conventions)
 - function body might be inlined

---

# C++ coroutines

- introduced in C++20
- spec has a large number of types and rules, most different from the others, ranging
  - from new keywords and compiler implementation
  - user implemented, but with language defined hooks for customization
  - to "nice to have"s, but could be entirely implemented by user
- NOTE: user(s) can further be divided into library writers and users of the
  library (will conflate both together here)

- reading list
  - [spec
    N4775](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/n4775.pdf):
    relatively short, readable, but background info required
  - [Lewis Baker's posts](https://lewissbaker.github.io/): long, not up to
    date, but really good background info required to understand coroutines

---

# Visual layout

<div align="center">
<svg xmlns="http://www.w3.org/2000/svg" id="svg20230623-12-1" width="100%" viewBox="0 0 800 320">
  <style>
    #svg20230623-12-1 {
      border: 1px solid #e8e8e8;
      background-color: #f5f5f5;
    }
    .svg20230623-12-l1 {
      stroke: #000000;
      stroke-width: 2;
      fill: none;
    }
    .svg20230623-12-c1 {
      stroke: #000000;
      stroke-width: 2;
      fill: #ff36ab;
    }
    .svg20230623-12-c2 {
      stroke: #000000;
      stroke-width: 2;
      fill: #ff9bd5;
    }
    .svg20230623-12-c3 {
      stroke: #000000;
      stroke-width: 2;
      fill: #ffcdea;
    }
    .svg20230623-12-l2 {
      stroke: #000000;
      stroke-width: 2;
      fill: none;
      stroke-dasharray: 5;
    }
    .svg20230623-12-task_white {
      stroke: #000000;
      stroke-width: 4;
      fill: #ffffff;
    }
    .svg20230623-12-task_green {
      stroke: #000000;
      stroke-width: 4;
      fill: #c2b102;
    }
    .svg20230623-12-task_neutral2 {
      stroke: #000000;
      stroke-width: 4;
      fill: #6ac3d9;
    }
  </style>
  <rect x="10" y="10" width="80" height="300" class="svg20230623-12-task_white"/>
  <rect x="130" y="85" width="80" height="160" class="svg20230623-12-task_neutral2"/>
  <path class="svg20230623-12-l1" d="M 50 30 v 70 h 120 v 20"/>
  <path class="svg20230623-12-l2" d="M 170 120 v 20 l -120 -30 v 55 l 120 -15 v 40 l -120 -15 v 35
    l 120 -10 v 35 l -120 -15 v 70"/>
  <circle cx="50" cy="110" r="7" class="svg20230623-12-c1"/>
  <circle cx="50" cy="175" r="7" class="svg20230623-12-c2"/>
  <circle cx="50" cy="220" r="7" class="svg20230623-12-c3"/>
  <rect x="290" y="250" width="100" height="50" class="svg20230623-12-task_neutral2"/>
</svg>
</div>

- stackless, decomposed into coroutine frame and function(s), first call is
  special

---

# std::coroutine_handle

- allows control of the coroutine frame via members

- `void resume()`
- `void destroy()`
- `bool done()`
- ...

- handle, not RAII (e.g. it has copy, not just move)
- also it's a template (in an unusual way for handles)

- it has to be used with care: don't resume if destroyed, don't resume if not
  suspended, don't destroy more than once, etc.

---

# Coroutine syntax

```cpp
task foo() {
  co_await bar();
}

generator buzz() {
  co_yield 42;
}

task wozz() {
  co_return 42;
}

```

- looks like a function
- three new keywords:
  - `co_await` used to define a suspension point
  - `co_yield` to suspend and yield some value
  - `co_return` to return a value at the end
- no just `return` in the coroutine body
- other than that, normal code inside the coroutine body
- can be member, template, but not destructor, not in `catch` blocks

---

# co_await is more important

eventually resolves expression to an awaiter object that controls suspension

then

```cpp
auto x = co_await awaiter;
```

is roughly equivalent to

```cpp
if (!awaiter.await_ready()) {
  // ... suspend coroutine (save data) here
  awaiter.await_suspend(coroutine_handle) // 3 variations of
  // ... return to caller here
  // ...
  // ... when resumed continue from here
}
auto x = awaiter.await_resume();
```

NOTE: call to `await_suspend` is after the coroutine data is saved (suspended),
this helps with multithreading

---

# std::suspend_always

```cpp
struct suspend_always {
  constexpr bool await_ready() const noexcept {
    return true;
  }

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

- this is an example of "nice to have"

---

# std::suspend_never

```cpp
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 {}
};
```

---

# co_return, co_yield

```cpp
task<int> wozz() {
  co_return 42;
}

task<void> foo() {
  co_await bar();
}

generator<int> buzz() {
  co_yield 42;
}
```

- type of `co_return` is not the same as the functions declared return type
- the declared return type allows access to the values passed to `co_return`
  and `co_yield`, and it's often a template class that takes the type of
  `co_return` and/or `co_yield` as a template parameter

---

# Coroutine implemented as functions

- mathematical equivalence of functions and coroutines (duality)
- but the function mechanics uses hardware support such as assembly instruction
  `CALL` knows to save the current address on the stack, increment the stack
  pointer register and continue from the location provided
- in practice a coroutine is reduce to functions to exploit this hardware
  efficiency
  - the first of these functions is special: ramp
  - the following resume or destroy from a previous suspension

---

# Ramp

<div align="center">
<svg xmlns="http://www.w3.org/2000/svg" id="svg20230623-14-1" width="100%" viewBox="0 0 800 320">
  <style>
    #svg20230623-14-1 {
      border: 1px solid #e8e8e8;
      background-color: #f5f5f5;
    }
    .svg20230623-14-l1 {
      stroke: #000000;
      stroke-width: 2;
      fill: none;
    }
    .svg20230623-14-l2 {
      stroke: #000000;
      stroke-width: 2;
      fill: none;
      stroke-dasharray: 5;
    }
    .svg20230623-14-task_white {
      stroke: #000000;
      stroke-width: 4;
      fill: #ffffff;
    }
    .svg20230623-14-task_grey {
      stroke: #000000;
      stroke-width: 4;
      fill: #cccccc;
    }
    .svg20230623-14-task_green {
      stroke: #000000;
      stroke-width: 4;
      fill: #c2b102;
    }
    .svg20230623-14-task_neutral2 {
      stroke: #000000;
      stroke-width: 4;
      fill: #6ac3d9;
    }
  </style>
  <rect x="10" y="10" width="100" height="70" class="svg20230623-14-task_grey"/>
  <rect x="10" y="80" width="100" height="30" class="svg20230623-14-task_green"/>
  <rect x="10" y="110" width="100" height="20" class="svg20230623-14-task_green"/>
  <rect x="10" y="130" width="100" height="60" class="svg20230623-14-task_green"/>
  <rect x="10" y="190" width="100" height="30" class="svg20230623-14-task_green"/>
  <rect x="10" y="220" width="100" height="55" class="svg20230623-14-task_white"/>
  <rect x="400" y="50" width="100" height="80" class="svg20230623-14-task_neutral2"/>
  <rect x="400" y="130" width="100" height="60" class="svg20230623-14-task_neutral2"/>
  <rect x="400" y="190" width="100" height="50" class="svg20230623-14-task_neutral2"/>
  <rect x="400" y="240" width="100" height="35" class="svg20230623-14-task_neutral2"/>
  <text class="svg20230623-14-t1" x="10" y="297">stack</text>
  <text class="svg20230623-14-t1" x="120" y="212">1. return value</text>
  <text class="svg20230623-14-t1" x="120" y="167">2. arguments</text>
  <text class="svg20230623-14-t1" x="120" y="127">3. return address</text>
  <text class="svg20230623-14-t1" x="120" y="102">4. local variables (ramp)</text>
  <text class="svg20230623-14-t1" x="520" y="97">7. local variables (body)</text>
  <text class="svg20230623-14-t1" x="520" y="167">5. arguments</text>
  <text class="svg20230623-14-t1" x="520" y="222">6. promise</text>
  <text class="svg20230623-14-t1" x="520" y="262">8. state machine</text>
  <text class="svg20230623-14-t1" x="400" y="297">coroutine frame</text>
</svg>
</div>

---

# Determine promise type

```cpp
// given
task foo() {
  co_await bar();
}
```

```cpp
class task {
public:
  using promise_type = some_other_type;
};

// or

class task {
public:
  class promise_type {
  };
};

```

- this promise type has nothing to do with `std::promise`
- usually promise type associated to the coroutine via the declared return type
- in the simplest: the `promise_type` type (literally) aliased or defined
  within the declared return type

---

# Coroutine traits

```cpp
template<class, class...>
struct coroutine_traits {};

template<class R, class... Args>
requires requires { typename R::promise_type; }
struct coroutine_traits<R, Args...>
{
  using promise_type = typename R::promise_type;
};
```

- this customization point allows using coroutine declared return types that do
  not need to be change to expose a `promise_type` OR to consider coroutine
  function arguments too in the resolution to the `promise_type`

---

# Body re-write

```cpp
  promise_type promise(<<promise constructor args>>);
  try {
    co_await promise.initial_suspend();
    // ... body here
  }
  catch (...) {
    if (!made enough progress through initial_suspend) {
      throw;
    }
    promise.undhandled_exception();
  }
  co_await promise.final_suspend();
```

- above pseudocode is a over-simplification
- promise is allocated on the coroutine frame
- it allows coroutine behaviour customization:
  - should it suspend at the start?
  - should it suspend at the end?
  - what should it do if exceptions are thrown?
  - space on the frame to handle the values from `co_return` and/or `co_yield`
  - etc.

---

TODO:
- constructing a promise

- how state is stored
- two options

- conversion between promise and coroutine_handle
  - at constant offset

- get_return_object

- customizing awaiters
- temporary awaiters are stored on the coroutine frame
- the purpose of await suspend after coroutine is suspended
- the three versions of await_suspend
  - the tail recursion case

---

# Questions?