constexpr std::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.
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)
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>();
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.
None, this is a pure extension, it allows usage of std::generator
during constant evaluation which wasn't possible before.
Mark every member function in [coro.generator] with constexpr
.
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 << ' ';
}
—
end example]
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>;
using reference = conditional_t<is_void_v<Val>, Ref&&, Ref>;
class iterator;
public:
using yielded =
conditional_t<is_reference_v<reference>, reference, const reference&>;
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;
unique_ptr<stack<coroutine_handle<>>> active_;
};
}
Mandates:
If
Allocator is not
void,
allocator_traits<Allocator>::pointer is a pointer type
.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
.
If
Allocator is not
void,
it shall meet the
Cpp17Allocator requirements
.The behavior of a program that adds a specialization
for
generator is undefined
.constexpr generator(generator&& other) noexcept;
Effects: Initializes
coroutine_ with
exchange(other.coroutine_, {}) and
active_ with
exchange(other.active_, nullptr). [
Note 1:
Iterators previously obtained from
other are not invalidated;
they become iterators into
*this. —
end note]
Effects: Equivalent to:
if (coroutine_) {
coroutine_.destroy();
}
[
Note 2:
Ownership of recursively yielded generators
is held in awaitable objects
in the coroutine frame of the yielding generator,
so destroying the root generator
effectively destroys the entire stack of yielded generators
. —
end note]
constexpr generator& operator=(generator other) noexcept;
Effects: Equivalent to:
swap(coroutine_, other.coroutine_);
swap(active_, other.active_);
[
Note 3:
Iterators previously obtained from
other are not invalidated;
they become iterators into
*this. —
end note]
constexpr iterator begin();
Effects: Pushes
coroutine_ into
*active_,
then evaluates
coroutine_.resume(). Returns: An
iterator object
whose member
coroutine_
refers to the same coroutine as does
coroutine_. [
Note 4:
A program that calls
begin more than once on the same generator
has undefined behavior
. —
end note]
constexpr default_sentinel_t end() const noexcept;
Returns:
default_sentinel. 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();
constexpr 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>
constexpr 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>
constexpr void* operator new(size_t size, const This&, allocator_arg_t, const Alloc& alloc,
const Args&...);
constexpr void operator delete(void* pointer, size_t size) noexcept;
private:
add_pointer_t<yielded> value_ = nullptr;
exception_ptr except_;
};
}
constexpr generator get_return_object() noexcept;
Returns: A
generator object whose member
coroutine_
is
coroutine_handle<promise_type>::from_promise(*this),
and whose member
active_ points to an empty stack
. 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. 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
. constexpr suspend_always yield_value(yielded val) noexcept;
Effects: Equivalent to
value_ = addressof(val). 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>&>;
Preconditions: A handle referring to the coroutine
whose promise object is
*this
is at the top of
*active_
of some
generator object
. 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
. Throws: Any exception thrown by the initialization of the stored object
. 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;
Preconditions: A handle referring to the coroutine
whose promise object is
*this
is at the top of
*active_
of some
generator object
x. The coroutine referred to by
g.range.coroutine_
is suspended at its initial suspend point
.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. If
bool(except_) is
false,
the
await_resume member has no effects
.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))));
constexpr void unhandled_exception();
Preconditions: A handle referring to the coroutine whose promise object is
*this
is at the top of
*active_
of some
generator object
x. Effects: If the handle referring to the coroutine
whose promise object is
*this
is the sole element of
*x.active_,
equivalent to
throw,
otherwise, assigns
current_exception() to
except_. constexpr 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>
constexpr 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>
constexpr void* operator new(size_t size, const This&, allocator_arg_t, const Alloc& alloc,
const Args&...);
Let
A be
- Allocator, if it is not void,
- Alloc for the overloads with a template parameter Alloc, or
- allocator<void> otherwise.
Let
B be
allocator_traits<A>::template rebind_alloc<U>
where
U is an unspecified type whose size and alignment
are both
__STDCPP_DEFAULT_NEW_ALIGNMENT__.Mandates:
allocator_traits<B>::pointer is a pointer type
. 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.Returns: A pointer to the allocated storage
. constexpr void operator delete(void* pointer, size_t size) noexcept;
Preconditions:
pointer was returned from an invocation of
one of the above overloads of
operator new
with a
size argument equal to
size. Effects: Deallocates the storage pointed to by
pointer
using an allocator equivalent to that used to allocate it
. 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_;
};
}
constexpr iterator(iterator&& other) noexcept;
Effects: Initializes
coroutine_
with
exchange(other.coroutine_, {}). constexpr iterator& operator=(iterator&& other) noexcept;
Effects: Equivalent to
coroutine_ = exchange(other.coroutine_, {}). constexpr reference operator*() const noexcept(is_nothrow_copy_constructible_v<reference>);
Preconditions: For some
generator object
x,
coroutine_ is in
*x.active_ and
x.active_->top() refers to
a suspended coroutine with promise object
p. Effects: Equivalent to:
return static_cast<reference>(*p.value_);
constexpr iterator& operator++();
Preconditions: For some
generator object
x,
coroutine_ is in
*x.active_. Effects: Equivalent to
x.active_->top().resume(). constexpr void operator++(int);
Effects: Equivalent to
++*this. constexpr friend bool operator==(const iterator& i, default_sentinel_t);
Effects: Equivalent to: return i.coroutine_.done();
#define __cpp_lib_generator 2022072024??L