constexpr coroutines

This paper is proposing making coroutines functional during constant evaluation. Even when most of use-cases for coroutines are based on I/O and event based, coroutines are still useful for compile-time based computation, eg. std::generator.

Changes

• R1 → R2: Updated wording to elide allocator functionality in coroutine promise types. Added discussion about alternative implementation strategies. Added information about decision by various groups which seen this paper.
• R0 → R1: Changed wording mentioning lifetime of coroutines after expr.const 5.2

Timeline

EWG in Wroclaw

Result: Consensus

LEWG in Wroclaw

Result: Unanimous consent

CWG in Wroclaw

Multiple implementers expressed concerns about resources needed for the implementation of this feature, where the resources might be better spent implementing C++ features where market demand is higher.

EWG is requested to reconsider putting this feature into the standard.

Note: CWG did review of the wording and only question was about what to do with allocation / deallocation functions. Wording was updated to elide these calls during constant evaluation of a coroutine. Concern about resources was reflected by updating the paper to contain informations about alternative implementation strategies.

Based on anecdotal evidence people don't use coroutines for two reasons: one is missing standard library support (which is partially resolved with std::generator) and second is mutual exclusivity with much more popular constant evaluated code. Having constant evaluation of couroutines will help alleviate this and I do expect seeing libraries implementing lazy coroutine based parsers.

Quote

Well, you just told me coroutines are the best way to solve some problems, so wouldn't I also want to use the Best Way at compile time? (quote from Jason Turner, co-author of "constexpr all the things" talk)

Simple example

When this paper is merged into the standard, users will be able to use std::generator-like coroutines to generate or calculate data.

template <typename T> constexpr auto fib() -> std::generator<T> {
    T a = 0;
    T b = 1;
    co_yield a;
    do {
        co_yield b;
        auto tmp = b;
        b += a;
        a = tmp;
    } while (true);
}

template <typename T, size_t N> constexpr auto calculate_fibonnaci() {
    auto res = std::array<T, N>{};
    std::ranges::copy(fib<T>() | std::views::take(N), res.begin());
    return res;
}

constexpr auto cached_fibonnaci = calculate_fibonnaci<unsigned, 20>();

Evaluation of constexpr coroutines

Implementation must make sure to avoid stack exhaustion and store evaluation state and coroutine's local variables in a way to avoid it. By simply resuming coroutine and evaluating it on system stack (in case of AST walking implementations) will lead to it.

This is because coroutines can be interlieved and their state must be maintained to be resumed. The stack then contains mixed coroutines and normal code together. To avoid this situation the easiest way to model a coroutine is to use coroutine (or coroutine-like functionality) to store the state (represented with values on stack) somewhere else. Because AST walk is unbounded, obvious first choice is a stackfull coroutine (fiber, not a thread!).

Lifetime of coroutine is bounded to be only within constant evaluation similary as memory allocation. Any coroutine leaking outside boundaries of constant evaluation means whole constant evalution failed.

Implementation experience

Partially implemented in clang available on my github, implementation should be ready for its presentation at Wroclaw meeting, and also will be soon available on compiler explorer (thanks Matt!).

Most of functionality needed was already present in Clang, it was mostly about removing checks in the parser.

Another part was implementing the functionality in Clang's interpreter and there I needed to add fibers (stackfull coroutines) as the interpreter recursive walks over AST. Ability to save interpreter's stack content did minimize impact of the change to only resuming, suspending, and variable storage and life-time management.

At the end of evaluation the interpret needs to check objects holding fibers if there is still any coroutine not released, if there is it report similar error as when there is an unreleased memory allocation.

Hardest problem was implementing local "stack", as createLocal function was designed around idea of having only one branch of evaluation. This I solved by providing context of currently evaluated coroutine in EvalInfo and switching it on every suspension / resume of a coroutine.

Alternative implementation approaches

The implementation is using fibers (not threads!) to create a storage for execution of coroutines outside of main stack. Main requirement here is to make sure jumping between coroutines won't run out of the system stack.

Following subpart of paper shows alternative approaches which can model coroutines. All of them have same expressive ability and model coroutines well. These implementation has various advantages and costs. For every model of constant evaluation should be possible found good and usable match.

Byte-code interpreter

Clang implementation is starting to use a byte-code virtual machine based interpreter. In such implementation the implementation approach is identical for actually compiling coroutines to a native code. Only thing you need is ability to change current stack / or reference coroutine variables based on offset to coroutine frame.

Such interpret has many advantages over AST walking one mostly in speed and security. I was told initial measurements in the byte-code interpreter in clang are three orders of magnitude faster over recursive AST walking. Security is inherit to fact of not using system stack for the evaluation at all.

C++ coroutines

For compilers which are using C++20 code itself another implementation strategy is to not use the system stack for walking AST, but change all necessory functions into coroutines which would model ordinary functions with only one return point to its callee. But these functions can be suspended and evaluation can switch to evaluation of a constexpr coroutine. Because all coroutines will be allocated on heap, this also hardens implementation's constexpr evaluator.

AST transformation / split

Last feasible approach is to implement a transformation of coroutine function, into multiple trees, representing all possible paths which can be taken from each suspension point. Everytime such splitted coroutine is suspended, constexpr evaluator can unroll all its recursive functions. Implementation then needs to implement a storage for coroutine local variables which survive suspension. Hardest part is to implement special AST nodes to represent expressions split for suspension in middle.

Note: similar split is already done in compiler (for Clang at LLVM level, GCC just before leaving frontend, for Swift in its frontend)

Comparison

Impact on existing code

None, this is a pure extension, it allows code to be constexpr which wasn't case before.

Intention for wording changes

Remove all obstacles blocking coroutines from being constant evaluatable. Make sure all coroutines are destroyed at end of constant evaluation.

Proposed wording changes

Feature test macros