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

• R2 → R3: added motivation text, added AST transform approach examples
• 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)

Motivation

Currently C++'s doesn't allow coroutines to be constexpr. This limitation forces users to choose between having constexpr compatible library or (maybe) simpler coroutine interface. As a library author I do prefer constexpr but I do not want to make this decision.

I think this limitation and weak library support for coroutines are main limiting factors for bigger adoption of coroutines. I personally want to be able to write CTRE coroutine interface which allows partially process input on a regular expression state and continue later when it will be resumed.

Coroutines are not just for asynchronous

Most people see uses for coroutines for asynchronous and event based programming. Coroutines are useful for parsers, modeling clock-perfect timing in emulators, and generally any state machines.

Fibonnaci generator

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>();

Tokenizer

TODO: tokenizer

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)

C++ coroutines are already defined as a set of transformations over a function based on detection of co_await, co_yield, and co_return keywords. This approach is going a bit further but it can still be done manually.

Standard transformation

Simple generator which take a value, yield it and later yield value².

auto simple(T start) -> std::generator<T> {
	co_yield start;
	auto quad = start * start;
	co_yield quad;
}

This code is current transformed into:

auto simple(T start) -> std::generator<T> {
	return std::generator<T>{ coroutine-frame {
		std::generator<T>::promise_type _promise{};
		auto start = start; // copy arguments
		try {
			co_await _promise.initial_suspend();
			co_await _promise.yield_value(start);
			auto quad = start * start;
			co_await _promise.yield_value(quad);
			// body
		} catch (...) {
			if (!initial-await-resume-called) {
				throw;
			}
			_promise.promise.unhandled_exception();
		}
		// final-suspend:
		 co_await promise.final_suspend() ;
	}};
}

As you can see, it's all just transformation. A function into a coroutine body explicitly managing life-time of a promise type, and co_yield into co_await. Compiler is already doing a lot of transformation in frontend. This proposed implementation strategy is just making a bit more transformations.

Transformation into void-style continuation

Any coroutine can be transformed into a set of void returning functions:

coroutine simple(T argument) {
	auto result = co_await normal_function(argument);
	co_return result;
}

With resulting code looking somehow like this:

struct coroutine_state_base {
	// where to jump
	void (*resume_point)(coroutine_state_base *) = nullptr;
};	

// unique type per each coroutine function
struct __coroutine_state: coroutine_state_base {
	// all arguments here...
	T argument;
	
	// promise type
	coroutine::promise_type promise;

	// all variables / temporaries which can survive suspension
	initial_awaiter initial_suspend_result;
	final_awaiter final_suspend_result;
	decltype(normal_function(argument)) tmp;
};

constexpr coroutine simple(T argument) { // <------------- starting point
	// create state
	auto * state = new __coroutine_state{};
	
	// copy arguments
	state->argument = argument;
	
	// construct promise
	new (&state->promise) coroutine::promise_type{...};
	
	// construct result
	auto result = state->promise.get_return_object();
	
	// call (jump-into) coroutine body
	simple_start(state);
	
	// return result object with coroutine handle (usually)
	return result;
}

constexpr void simple_start(coroutine_state_base * vstate) {
	auto * state = static_cast<__coroutine_state *>(vstate);
	
	// INITIAL SUSPEND
	state->initial_suspend_result = state->promise.initial_suspend()
	if (!state->initial_suspend_result.await_ready()) {
		state->resume_point = &simple_after_init_suspend;
		
		// tail-recursion jump to next coroutine or continue
		NEXT-COROUTINE(state->initial_suspend_result.await_suspend(std::coroutine_handle{state}));
	}
	return simple_after_init_suspend(state); // tail-recursion
}

constexpr void simple_after_init_suspend(coroutine_state_base * vstate) {
	auto * state = static_cast<__coroutine_state *>(vstate);
	
	// BEFORE CUSTOM CO_AWAIT
	try {
		(void)state->initial_suspend.await_resume();
		std::destroy_at(&state->initial_suspend_result); // lifetime of temporary must be destroyed
		
		// normal body
		state->tmp = normal_function(state->argument);
		
		if (!state->tmp.await_ready()) {
			state->resume_point = &simple_after_first_await;
			
			// tail-recursion jump to next coroutine or continue
			NEXT-COROUTINE(state->tmp.await_suspend(std::coroutine_handle{state}));
		}
		
		return simple_after_first_await(state);
	} catch (...) {
		std::destroy_at(&state->tmp);
		state->promise.unhandled_exception();
		return simple_final_suspend(state);
	}
}

constexpr void simple_after_first_await(coroutine_state_base * vstate) {
	auto * state = static_cast<__coroutine_state *>(vstate);
	
	// RESUMED or just jumped after CUSTOM CO_AWAIT
	try {
		// get result (which doesn't survive suspension, so it can be put here on stack)
		auto result = state->tmp.await_resume();
		
		// co_return result
		state->promise.return_value(result); 
		
		// end of scope for state->tmp
		std::destroy_at(&state->tmp);
		
	} catch (...) {
		std::destroy_at(&state->tmp);
		state->promise.unhandled_exception();
	}
	
	// jump to final suspend
	return simple_final_suspend(state);
}

constexpr void simple_final_suspend(coroutine_state_base * vstate) {
	auto * state = static_cast<__coroutine_state *>(vstate);
	
	// FINAL SUSPEND
	state->final_suspend_result = state->promise.final_suspend();
	if (!state->final_suspend_result.await_ready()) {
		state->resume_point = nullptr;
		
		// tail-recursion jump to next coroutine or continue
		NEXT-COROUTINE(state->final_suspend_result.await_suspend(std::coroutine_handle{state}));
	}
	// destruction of state after final-suspend
	delete &state;
	// no-return ... which will return us to our resumer
}

Whole transformation is just changing all edges to standalone void returning function between which can be jumped with a tail recursion. Each .await_suspend(coroutine_handle) can return handle to next coroutine, boolean with information if it should be a suspend or not, or just void, which means simple suspend.

// NEXT-COROUTINE(EXPR) is:
using type = decltype(EXPR);                                                        
if constexpr (std::is_void_v<type>) {                                         
	EXPR;                                                                             
	return; // return to caller                                                       
} else if constexpr (std::same_as<type, bool>) {                              
	if (EXPR) {                                                                       
		return; // return to caller                                                     
	}                                                                                 
	// continue in coroutine                                                          
} else if constexpr (std::convertible_to<std::coroutine_handle<void>>) {
	auto * next_state = static_cast<coroutine_state_base *>(E(XPR).address());                                                          
	return next_state->resume_point(next_state); // tail-recursion
}                                                                                   

Most of the transformation is lifetime handling and splitting at each co_await. The suspend transformation is already part of compilers so await_ready(), await_suspend(std::coroutine_handle), await_resume() is already part of each compiler.

Loops transformation

constexpr coroutine loops() noexcept {
		while (co_await check()) {
			another_function();
		}
	}

Code above is transformed into:

constexpr void loops_main(coroutine_state_base * vstate) noexcept {
	// initial suspend skipped for readability
		
	auto * state = static_cast<__coroutine_state *>(vstate);
	state->tmp = check();
	if (!state->tmp.await_ready()) {
		state->resume_point = &loops_main_body;
		NEXT-COROUTINE(state->tmp.await_suspend(std::coroutine_handle{state}));
	}
	return loops_main_body(state); // tail-recursion
}

constexpr void loops_main_body(coroutine_handle_base * vstate) noexcept {
	auto * state = static_cast<__coroutine_state *>(vstate);
	if (state->tmp.await_resume()) {
		another_function();
		return loops_main(state); // tail-recursion
	}
	std::destroy_at(&state->tmp);
	return loops_final_suspend(state);
}

Tail-recursion

To implement constexpr coroutines with the AST transformation a tail recursion is needed to be supported in constant evaluator.

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