P2168 std::generator: Synchronous Coroutine Generator for Ranges

[brycelelbach]

P2168R0 std::generator: Synchronous Coroutine Generator for Ranges (Corentin Jabot)

[brycelelbach]

P2168R0: std::generator

2020-05-26 Library Evolution Telecon Minutes

Chair: Nevin Liber

Champion: Lewis Baker & Corentin Jabot

Minute Taker: Ben Craig

Start Review: 2020-05-26 10:00 Pacific

POLL: Recursive generators should use the syntax co_yield elements_of(gen), performance the same as co_yield gen as specified in the paper	SF	WF	N	WA	SA
5	10	3	3	1

Author's position: A (CJ), F (LB)

Attendance: 32

That has consensus for.

SA: Adds zero information to the program and more characters to get wrong.

POLL: Recursive generators should use the syntax co_yield gen	SF	WF	N	WA	SA
7	4	9	4	1

Author's position: SF (CJ), N (LB)

Attendance: 32

SA: Automatic recursive nesting of arbitrary ideas has proved tricky in the past with future.then.

That has consensus for.

co_yield elements_of(gen) has stronger consensus than co_yield gen.

POLL: Generator should be in header <generator>	SF	WF	N	WA	SA
14	5	3	1	1

Author's position: A (CJ), SF (LB)

Attendance: 32

SA: Just a perf issue of having too many small headers

That has consensus for.

End: 11:40

SUMMARY:

• A lot of discussion around "recursive generators", where a co_yield of the same type of generator would produce its elements. There was more support for doing so with a syntactical construct such as co_yield elements_of(gen) (instead of co_yield gen as presented in the paper) and the authors will investigate generalizing that to being able to pass in other views.
• The room was generally fine with having the optional second template parameter specifying the value type, but would like to see more motivation in the next revision of the paper.
• Seemed to be general desire to support a single generator type that supports yielding nested generators, rather than two separate generator types, on condition that we show that compilers are able to optimize/inline similarly.
• The destructor for generator may not be O(1), as required by [range.view]. While it will need wording to that effect, this is fine for generator, but is discouraged in most other views.
• Strong preference for putting generator in its own header.
• Ran out of time to do more than a cursory examination of the wording.

OUTCOME: Bring a revision of P2168R0 (std::generator), with the guidance below, to Library Evolution for further design review.

• Explore an explicit syntax for recursive generators, e.g. co_yield elements_of(gen) instead of co_yield gen, as a way to increase consensus.
• Put std::generator in a new header <generator>.
• Clarify that std::generator::~generator may not be O(1), which violates range requirements.

[wg21bot]

P2168R1 generator: A Synchronous Coroutine Generator Compatible With Ranges (Corentin Jabot, Lewis Baker)

[brycelelbach]

2021-02-23 Library Evolution Telecon

P2168R2: std::generator

2021-02-23 Library Evolution Telecon Minutes

Chair: Bryce Adelstein Lelbach

Champion: Lewis Baker and Corentin Jabot

Minute Taker: Mark Hoemmen

Start: 2021-02-23 10:09 Pacific

Does this proposal have:

• Examples?
  • Yes.
• Implementation experience?
  • Yes.
  • Less for elements_of.
• Usage experience?
  • Yes.
  • Less for elements_of.
• Deployment experience?
  • Yes.
  • Less for elements_of.
• Performance considerations?
  • Benchmarks are in the slides.
• Discussion of prior art?
• Changes Library Evolution previously requested?
  • Yes (see below).
• Wording?
  • Yes.
• Feature test macro?

Changes that Library Evolution requested from R0:

• Explore an explicit syntax for recursive generators, e.g. co_yield elements_of(gen) instead of co_yield gen, as a way to increase consensus.
  • Addressed in R1.
• Put std::generator in a new header <generator>.
  • Addressed in R1.
• Clarify that std::generator::~generator may not be O(1), which violates range requirements.
  • Not addressed by this paper, the authors are exploring a resolution to this independent of and broader than this paper (see LWG3452: Are views really supposed to have strict 𝒪(1) destruction?).

It appears the authors have addressed all the changes Library Evolution requested last time.

Implicit conversion between generator element types. Do we want that? Are there any complications?

co_yielding elements_of the same generator type is faster than co_yielding elements_of a different generator type. Should these two cases have a different spelling?

We could always add something that only yields generators of the same generator type, e.g. nested_elements_of. This seems to resolve the concern that was raised.

Are we okay with the split reference/value type template parameters? Necessary to support proxy reference types.

Precedence for split reference/value type template parameters:

• iterator (deprecated)
• mdspan (proposed)

Precedence for proxy reference types in the standard:

• vector<bool>
• zip (proposed)
• flat_map (proposed)

Could we have a basic_generator<Ref, T, Allocator> and an alias generator<Ref, remove_cvref_t<T>, Allocator> as a compromise?

Maybe we could have a value_or_reference<Ref, Val = ...> that allows us to pass these things around?

POLL: std::generator should have split reference and value type template parameters.

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
5	13	1	3	0

Attendance: 28

# of Authors: 2

Author Position: 2x SF

Outcome: That has consensus.

Is there precedence for void meaning type-erased allocator? Can it just be an unspecified default type instead?

We'll resume the review in future weeks.

End: 11:04

Summary

During this review of generator, we primarily discussed two matters.

First, we discussed the differences between co_yield elements_of(x) when x is the same generator type as the outer coroutine versus a different generator type than the outer coroutine. When the generator type is different, the performance of elements_of will be worse. Because elements_of works in both cases, it may not always be obvious when you are on the slow path. The discussion was resolved when it was suggested that in the future we could add another operation (nested_elements_of) that only yields generators of the same generator type if needed.

Next, we discussed the split reference/value type template parameters of generator. The rationale for this design is to support proxy references and some important ranges/views use cases. It was noted that this design is somewhat novel. There was some concern that this design might enable people to instantiate the template with ill-advised pairings of reference types and value types. We briefly considered whether we should add a simpler, more user friendly template alias that only takes a single type (and possibly an allocator), but we determined this had no real benefit; all template parameters except the first are already defaulted. There was also some suggestion that perhaps we should create a facility for passing pairings of reference/value types as a single template parameter. In the end, we had consensus to move forward with the current split reference/value type design as described in the paper.

Outcome

Bring a revision of D2168R2 (std::generator), with the guidance below, to Library Evolution for further design review.

• Keep the split reference/value type template parameters.

Library Evolution will resume its review of this revision D2168R2 (std::generator) at a future meeting.

[brycelelbach]

2021-03-08 Library Evolution Telecon

P2168R2: std::generator

2021-03-08 Library Evolution Telecon Minutes

Chair: Bryce Adelstein Lelbach

Champion: Lewis Baker & Corentin Jabot

Minute Taker: Ben Craig

Start: 2021-03-08 10:02 Pacific

Does this proposal have:

• Examples?
  • Yes.
• Implementation experience?
  • Yes.
  • Less for elements_of.
• Usage experience?
  • Yes.
  • Less for elements_of.
• Deployment experience?
  • Yes.
  • Less for elements_of.
• Performance considerations?
  • Yes. Benchmarks are in the slides.
• Discussion of prior art?
  • Yes.
• Changes Library Evolution previously requested?
  • Yes (see below).
• Wording?
  • Yes.
• Feature test macro?
  • ???

Is there precedence for void meaning type-erased allocator? It sounds like this is novel library technology.

Can the allocator parameter have some unspecified default type instead?

Why not use PMR for allocator type-erasure?

Why take a typed allocator instead of an untyped memory resource?

Why not std::allocator by default (e.g. no type erasure)?

Should we add a new std::allocator_traits<...>::propagate_on for elements_of?

If we only had an elements_of that worked with the same generator type, then we wouldn't have this elements_of allocator problem.

The underlying problem is that you can't get access to the allocator to rebind it.

POLL: generator must support allocators.

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
3	5	8	6	1

Attendance: 27

# of Authors: 2

Author Position: 2x SF

Outcome: No consensus in either direction.

POLL: If generator supports allocators, the default should be to accept any allocator and type erase it.

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
3	10	4	3	0

Attendance: 25

# of Authors: 2

Author Position: SF, WF

Outcome: Consensus in favor.

WA: This is novel, and I'm not sure why we need it here. If I have to use any allocator with a vector, I either use pmr::vector or specify the allocator.

WA: I think it adds overhead, both when you use and when you don't.

POLL: void should be the type that indicates that generator should accept any allocator and type erase it.

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
0	2	9	6	1

Attendance: 25

# of Authors: 2

Author Position: WF, N

Outcome: Weak consensus against.

EXPLORE: The type that indicates that generator should type erase its should be unnamed.

__EXPLORE: elements_of should have an overload that accepts an allocator.__

EXPLORE: Explore two separate generator types: nested generators (which uses symmetric transfer) and non-nested generators (which doesn't use symmetric transfer).

FUTURE POLL: generator must supported nesting.

We will resume discussion of this revision in 2021-04. It will probably be at a special time to accommodate Lewis's time zone.

End: 11:30

Summary

We continued our review of P2168R2 std::generator, focusing primarily on a discussion of allocator support.

The current proposal is for generator's default allocator template parameter to indicate that a generator can be constructed with any type of allocator, which would be type erased. This interface design seems to be novel, but we had weak consensus in favor of it. Currently, the spelling of that default parameter is void; we had weak consensus to find a different spelling.

We also discussed the implications of allocator support on elements_of, especially in cases where there are different generator types in play. It was suggested that we explore an overload of elements_of that accepts an allocator.

By the end of our discussion, it was unclear if we had consensus that generator should have allocator support at all. We are aware of some stakeholders that have important use cases who were not present for the discussion, so the authors have been asked to reach out to said stakeholders and return with more information on whether generator should support allocators or not.

Outcome

Bring a revision of P2168R2 (std::generator), with the guidance below, to Library Evolution for further design review.

• Keep the split reference/value type template parameters.
• Keep the default behavior of accepting any allocator and type erasing it, but find a different syntax for expressing the default allocator template parameter.
• Contact stakeholders and add additional justification and rationale for supporting allocators.

Library Evolution will resume its review of this revision P2168R2 (std::generator) at another session.

[brycelelbach]

2021-04-19 Library Evolution Telecon

D2168R3: std::generator

2021-04-19 Library Evolution Telecon Minutes

Chair: Bryce Adelstein Lelbach

Champion: Lewis Baker and Corentin Jabot

Minute Taker: Gasper Azman

Start: 2021-04-19 08:07 Pacific

Does this proposal have:

• Examples?
  • Yes.
• Implementation experience?
  • Yes.
• Usage experience?
  • Yes, but more is desired.
• Deployment experience?
  • Yes, but more is desired.
• Performance considerations?
  • Still needed.
• Discussion of prior art?
  • Yes.
• Changes Library Evolution previously requested?
  • Yes.
• Wording?
  • Yes.
• Feature test macro?
  • ???

What should the order of value/reference type template parameters be? The current order is reference then value. If we make value then reference, can we pick a reasonable default for what the reference type will be?

Instead, we could make the iterators always return references, because you have to store the value in the promise anyways. Then the first template parameter can name the storage type. You'd still need a split value and reference type - consider wanting string and string_view.

Matthias' model: the value type is what you pass to the co_yield expression.

Have Matthias, David, and authors write a section of the paper that explores all the options for value/reference semantics of std::generator and its iterators.

• Value Type: The type used to store an independent copy of an element of the sequence.
• Reference Type: The type you get from dereferencing the iterator.
• Yielded Expression Type: The type that co_yield constructs.

Future Poll Ideas:

• The first template parameter of std::generator should describe the value type instead of the reference type.
• If the value type of std::generator is T, then the default reference type should be T&.
• If the value type of std::generator is T, then the default reference type should be T&&.

Examples we want to see:

• Generator of ints.
• Generator of strings where you want to get string_view reference types, e.g. different-from-default reference type.
• Generator of unique_ptrs, e.g. conveying ownership of a value from a co_yield to its consumer without copying the value.
• Dereferencing an iterator multiple types.

Can input iterators be dereferenced multiple times?

Wording Review:

• elements_of example should take the range by forward reference.
• Exposition only members should be private.
• Consider making elements_of::allocator is consistent with existing precedent in the Standard Library:
  • Consider renaming allocator to get_allocator.
  • Consider making it return by value and const qualified.
• Fix deduction guides that have return in them.
• Qualify std::forward and std::move.
• ranges::element_of -> ranges::elements_of.
• Missing semicolons for ranges::elements_of constructor declarations.
• Fix common_reference_with requirement for generator.
• Change the default allocator from void to some tag type.
• input_view -> input_range.
• generator::operator= should take its argument by rvalue ref not value.
• Consider adding swap.

Should generator be default constructible?

• We need to decide whether we want generator to support allocators. If it does, we need to be confident in the design. We need to get feedback from allocator experts.
• We need to settle the questions regarding the value categories.

End: 09:39

Summary

In this review of P2168 std::generator, we focused on the meaning of the value type and reference type template parameters, and their relation to the type and category of value given to certain operations involving std::generator.

In addition to the model in the paper at present, a few alternative models were suggested during the discusison. We instructed the authors to add a section to the paper considering these different models and their tradeoffs in greater detail, and identified specific examples we'd like to see to help compare these different models.

We also discussed the order of the value type and reference type parameter, if they are to both exist.

Additionally, we began reviewing the wording of the paper to prepare it for advancement to Library.

Outcome

Bring a revision of P2168R3 (std::generator), with the guidance below, to Library Evolution for further design review.

• Add a section exploring different models for value / reference / yielded expression type, including examples for each model of at least the following:
  • A generator of a value type and the default reference type, e.g. generator<int>.
  • A generator with a non-default reference type, e.g. generator<string, string_view>.
  • A generator conveying ownership of an object from a co_yield to its consumer without copying the value, e.g. generator<unique_ptr<T>>.
  • Dereferencing a generator::iterator multiple times.
• Keep the split reference/value type template parameters.
  • Consider what order they should be in; show examples.
• Keep the default behavior of accepting any allocator and type erasing it, but find a different syntax for expressing the default allocator template parameter.
• Contact stakeholders and add additional justification and rationale for supporting allocators.
• elements_of example should take the range by forward reference.
• Exposition only members should be private.
• Consider making elements_of::allocator is consistent with existing precedent in the Standard Library:
  • Consider renaming allocator to get_allocator.
  • Consider making it return by value and const qualified.
• Fix deduction guides that have return in them.
• Qualify std::forward and std::move.
• ranges::element_of should be ranges::elements_of.
• Missing semicolons for ranges::elements_of constructor declarations.
• Fix common_reference_with requirement for generator.
• Change the default allocator from void to some tag type.
• input_view should be input_range.
• generator::operator= should take its argument by rvalue ref not value.
• Consider adding swap for generator.
• Make generator::~generator's noexceptness consistent between synopsis and definition.

[wg21bot]

P2168R2 generator: A Synchronous Coroutine Generator Compatible With Ranges (Corentin Jabot, Lewis Baker)

[wg21bot]

P2168R3 generator: A Synchronous Coroutine Generator Compatible With Ranges (Corentin Jabot, Lewis Baker)

[brycelelbach]

2021-12-13 Library Evolution Telecon

P2168R3: std::generator

P2502R0: std::generator

2021-12-13 Library Evolution Telecon Minutes

Chair: Bryce Adelstein Lelbach

Champion: Casey Carter

Minute Taker: Ben Craig

Start: 2021-12-13 8:12 Pacific

Does this proposal have:

• Examples?
  • Yes.
  • Adding before/after examples might be helpful, as the author states that std::generator greatly reduces the amount of code you'd have to write for the examples.
• Implementation experience?
  • Yes, in third party libraries like CppCoro and Folly, but not in any major Standard Library.
• Usage experience?
  • Yes, in third party libraries like CppCoro and Folly, but not in any major Standard Library.
• Deployment experience?
  • Yes, in third party libraries like CppCoro and Folly, but not in any major Standard Library.
• Performance considerations?
  • Yes.
• Discussion of prior art?
  • Yes. Direct descendant of P2168, which builds on experience from third party libraries.
• Changes Library Evolution previously requested?
  • The paper considers and attempts to address open questions that arose during previous discussions.
• Wording?
  • Yes.
• Feature test macro?
  • Yes.

Key Insights:

Template parameters in P2168:

template <class Ref,
          common_reference_with<Ref> Value = remove_cvref_t<Ref>,
          class Allocator = void>
class generator;

Template parameters in P2502:

template <class T,
          class Allocator = void,
          class U = void>
class generator;

where:

using Value = conditional_t<is_void_v<U>, remove_cvref_t<T>, U>;}
using Reference = conditional_t<is_void_v<U>,
                                conditional_t<is_reference_v<T>, T, const T&>,
                                T>;
using Yielded = conditional_t<is_reference_v<Reference>, Reference, const Reference&>;

The above are currently exposition only types, but some expressed a desire for them to be a part of the public interface.

What should the reference type for generator<T> be when T is not a reference type? The paper currently proposes const T&; some suggest T&&.

Consider generator<string> - string&& would be odd reference type for a range. But for generator<unique_ptr<T>>, unique_ptr<T> const& would be odd.

Add a table to generator<meow> showing examples of what the reference type would be for some common cases of T, such as string, string&&, unique_ptr<T>.

Should the allocator parameter come before the U parameter?

Is there any precedent in the Standard Library for an allocator template parameter that's not the last template parameter?

There's some suggestion that supporting recursive generators has an overhead for non-recursive use cases. Should generator support recursive generators, or should we add a separate type for that later?

Open Questions:

• Default reference type for generator<T>.
• generator support for recursion.
• Position of generator's allocator template parameter.
• Header for generator.

Topics to Polls:

• Position of the allocator template parameter.
• Header for generator.

POLL: Make generator's allocator template parameter the last template parameter.

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
2	5	7	5	0

Attendance: 27

# of Authors: 1

Author Position: WA

Outcome: No consensus.

This topic needs further discussion in future revisions.

POLL: Put generator in <ranges> instead of adding a new <generator> header.

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
3	7	2	8	1

Attendance: 26

# of Authors: 1

Author Position: WF

Outcome: No consensus.

This topic needs further discussion in future revisions.

End: 9:30

Summary

Today we discussed P2502, an updated proposal for std::generator. This new revision proposes a new approach for template parameterization, which seems to address some of the issues identified with prior revisions. It was received well.

We discussed some remaining open questions, notably:

• The default reference type for generator<T>.
• generator support for recursion.
• The position of generator's allocator template parameter.
• The header that generator should live in.

We polled on the position of generator's allocator template parameter and the header that generator should live in. Both polls were inconclusive; further discussion is needed.

Outcome

We will continue design review of P2502 generator at our next telecon.

[brycelelbach]

Superseded by P2502 (#1151).