constexpr generator
This paper is proposing making std::generator constexpr and it depends on P3367: constexpr coroutines. I was told to put it into a separate paper, so here it is. I don't want this only coroutine type to lag behind language as before.
Changes
- R0 → R1: Removal (from previous paper) of constexpr support for alternative allocators (these functions are elided during constant evaluation of coroutines).
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)
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>();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!).
Once you have constexpr coroutine support, making std::generator constexpr is easy, just mark all function members with constexpr. But because there is no std::generator at all in libc++, I needed to implement it from scratch.
Impact of existing code
None, this is a pure extension, it allows usage of std::generator during constant evaluation which wasn't possible before.
Intention for wording changes
Mark every member function in [coro.generator] with constexpr.
Proposed wording changes
26.8 Range generators [coro.generator]
26.8.1 Overview [coroutine.generator.overview]
Class template generator presents
a view of the elements yielded by the evaluation of a coroutine.
A generator generates a sequence of elements by
repeatedly resuming the coroutine from which it was returned.
Elements of the sequence are produced by the coroutine
each time a co_yield statement is evaluated.
When the co_yield statement is of the form
co_yield elements_of(r),
each element of the range r
is successively produced as an element of the sequence.
[Example 1: generator<int> ints(int start = 0) {
while (true)
co_yield start++;
}
void f() {
for (auto i : ints() | views::take(3))
cout << i << ' '; // prints 0 1 2
}
— end example]
26.8.2 Header <generator> synopsis [generator.syn]
namespace std {
// [coro.generator.class], class template generator
template<class Ref, class Val = void, class Allocator = void>
class generator;
namespace pmr {
template<class Ref, class Val = void>
using generator = std::generator<Ref, Val, polymorphic_allocator<>>;
}
}
26.8.3 Class template generator [coro.generator.class]
namespace std {
template<class Ref, class Val = void, class Allocator = void>
class generator : public ranges::view_interface<generator<Ref, Val, Allocator>> {
private:
using value = conditional_t<is_void_v<Val>, remove_cvref_t<Ref>, Val>; // exposition only
using reference = conditional_t<is_void_v<Val>, Ref&&, Ref>; // exposition only
// [coro.generator.iterator], class generator::iterator
class iterator; // exposition only
public:
using yielded =
conditional_t<is_reference_v<reference>, reference, const reference&>;
// [coro.generator.promise], class generator::promise_type
class promise_type;
constexpr generator(const generator&) = delete;
constexpr generator(generator&& other) noexcept;
constexpr ~generator();
constexpr generator& operator=(generator other) noexcept;
constexpr iterator begin();
constexpr default_sentinel_t end() const noexcept;
private:
coroutine_handle<promise_type> coroutine_ = nullptr; // exposition only
unique_ptr<stack<coroutine_handle<>>> active_; // exposition only
};
}
Mandates:
- value is a cv-unqualified object type.
- reference is either a reference type, or a cv-unqualified object type that models copy_constructible.
- Let RRef denote remove_reference_t<reference>&& if reference is a reference type, and reference otherwise.Each of:
- common_reference_with<reference&&, value&>,
- common_reference_with<reference&&, RRef&&>, and
- common_reference_with<RRef&&, const value&>
[Note 1:These requirements ensure the exposition-only iterator type can model indirectly_readable and thus input_iterator.— end note]
26.8.4 Members [coro.generator.members]
constexpr generator(generator&& other) noexcept;
constexpr ~generator();
constexpr generator& operator=(generator other) noexcept;
constexpr iterator begin();
Preconditions: coroutine_ refers to a coroutine
suspended at its initial suspend point ([dcl.fct.def.coroutine]).
constexpr default_sentinel_t end() const noexcept;
26.8.5 Class generator::promise_type [coro.generator.promise]
namespace std {
template<class Ref, class Val, class Allocator>
class generator<Ref, Val, Allocator>::promise_type {
public:
constexpr generator get_return_object() noexcept;
constexpr suspend_always initial_suspend() const noexcept { return {}; }
constexpr auto final_suspend() noexcept;
constexpr suspend_always yield_value(yielded val) noexcept;
constexpr auto yield_value(const remove_reference_t<yielded>& lval)
requires is_rvalue_reference_v<yielded> &&
constructible_from<remove_cvref_t<yielded>, const remove_reference_t<yielded>&>;
template<class R2, class V2, class Alloc2, class Unused>
requires same_as<typename generator<R2, V2, Alloc2>::yielded, yielded>
constexpr auto yield_value(ranges::elements_of<generator<R2, V2, Alloc2>&&, Unused> g) noexcept;
template<ranges::input_range R, class Alloc>
requires convertible_to<ranges::range_reference_t<R>, yielded>
constexpr auto yield_value(ranges::elements_of<R, Alloc> r);
constexpr void await_transform() = delete;
constexpr void return_void() const noexcept {}
constexpr void unhandled_exception();
void* operator new(size_t size)
requires same_as<Allocator, void> || default_initializable<Allocator>;
template<class Alloc, class... Args>
requires same_as<Allocator, void> || convertible_to<const Alloc&, Allocator>
void* operator new(size_t size, allocator_arg_t, const Alloc& alloc, const Args&...);
template<class This, class Alloc, class... Args>
requires same_as<Allocator, void> || convertible_to<const Alloc&, Allocator>
void* operator new(size_t size, const This&, allocator_arg_t, const Alloc& alloc,
const Args&...);
void operator delete(void* pointer, size_t size) noexcept;
private:
add_pointer_t<yielded> value_ = nullptr; // exposition only
exception_ptr except_; // exposition only
};
}
constexpr generator get_return_object() noexcept;
constexpr auto final_suspend() noexcept;
Preconditions: A handle referring to the coroutine
whose promise object is *this
is at the top of *active_
of some generator object x.
This function is called by that coroutine
upon reaching its final suspend point ([dcl.fct.def.coroutine]).
Returns: An awaitable object of unspecified type ([expr.await])
whose member functions arrange for the
calling coroutine to be suspended,
pop the coroutine handle
from the top of *x.active_,
and resume execution of the coroutine referred to by
x.active_->top()
if *x.active_ is not empty.
If it is empty, control flow returns to the
current coroutine caller or resumer ([dcl.fct.def.coroutine]).
constexpr suspend_always yield_value(yielded val) noexcept;
constexpr auto yield_value(const remove_reference_t<yielded>& lval)
requires is_rvalue_reference_v<yielded> &&
constructible_from<remove_cvref_t<yielded>, const remove_reference_t<yielded>&>;
Returns: An awaitable object of an unspecified type ([expr.await])
that stores an object of type remove_cvref_t<yielded>
direct-non-list-initialized with lval,
whose member functions arrange for
value_ to point to that stored object
and then suspend the coroutine.
Returns: An awaitable object of an unspecified type ([expr.await])
into which g.range is moved,
whose member await_ready returns false,
whose member await_suspend
pushes g.range.coroutine_
into *x.active_
and resumes execution of the coroutine referred to
by g.range.coroutine_, and
whose member await_resume evaluates
rethrow_exception(except_)
if bool(except_) is true.
template<ranges::input_range R, class Alloc>
requires convertible_to<ranges::range_reference_t<R>, yielded>
constexpr auto yield_value(ranges::elements_of<R, Alloc> r);
Effects: Equivalent to:
auto nested = [](allocator_arg_t, Alloc, ranges::iterator_t<R> i, ranges::sentinel_t<R> s)
-> generator<yielded, ranges::range_value_t<R>, Alloc> {
for (; i != s; ++i) {
co_yield static_cast<yielded>(*i);
}
};
return yield_value(ranges::elements_of(nested(
allocator_arg, r.allocator, ranges::begin(r.range), ranges::end(r.range))));
[Note 1: — end note]
constexpr void unhandled_exception();
void* operator new(size_t size)
requires same_as<Allocator, void> || default_initializable<Allocator>;
template<class Alloc, class... Args>
requires same_as<Allocator, void> || convertible_to<const Alloc&, Allocator>
void* operator new(size_t size, allocator_arg_t, const Alloc& alloc, const Args&...);
template<class This, class Alloc, class... Args>
requires same_as<Allocator, void> || convertible_to<const Alloc&, Allocator>
void* operator new(size_t size, const This&, allocator_arg_t, const Alloc& alloc,
const Args&...);
Effects: Initializes an allocator b of type B with A(alloc),
for the overloads with a function parameter alloc,
and with A() otherwise.
Uses b to allocate storage for the smallest array
of U sufficient to provide storage for
a coroutine state of size size, and
unspecified additional state necessary to ensure that
operator delete can later deallocate this memory block
with an allocator equal to b.
void operator delete(void* pointer, size_t size) noexcept;
26.8.6 Class generator::iterator [coro.generator.iterator]
namespace std {
template<class Ref, class Val, class Allocator>
class generator<Ref, Val, Allocator>::iterator {
public:
using value_type = value;
using difference_type = ptrdiff_t;
constexpr iterator(iterator&& other) noexcept;
constexpr iterator& operator=(iterator&& other) noexcept;
constexpr reference operator*() const noexcept(is_nothrow_copy_constructible_v<reference>);
constexpr iterator& operator++();
constexpr void operator++(int);
constexpr friend bool operator==(const iterator& i, default_sentinel_t);
private:
coroutine_handle<promise_type> coroutine_; // exposition only
};
}
constexpr iterator(iterator&& other) noexcept;
constexpr iterator& operator=(iterator&& other) noexcept;
constexpr reference operator*() const noexcept(is_nothrow_copy_constructible_v<reference>);
constexpr iterator& operator++();
constexpr void operator++(int);
constexpr friend bool operator==(const iterator& i, default_sentinel_t);
Feature test macro
17.3.2 Header <version> synopsis [version.syn]
#define __cpp_lib_generator 2024??L // also in <generator>