This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] implement `std::views::elements_view`
ClosedPublic

Authored by huixie90 on Oct 19 2022, 10:05 AM.

Details

Summary

subrange is also a tuple-like. To avoid the add entire subrange dependencies to tuple-like, we need forward declaration of subrange. However, the class template constraints of subrange currently requires __iterator/concepts.h, which requires <concepts>. The problem is that currently tuple-like is used in several different places, including libc++ extension for pair constructors. we don't want to add <concepts> to pair and other stuff. So this change also created several small headers that subrange's declaration needed inside __iterator/concepts/

Diff Detail

Event Timeline

huixie90 created this revision.Oct 19 2022, 10:05 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 19 2022, 10:05 AM
huixie90 edited the summary of this revision. (Show Details)Oct 19 2022, 11:54 PM
huixie90 updated this revision to Diff 469279.Oct 20 2022, 10:26 AM

subrange forward declaration

huixie90 updated this revision to Diff 470409.Oct 25 2022, 1:40 AM

more tests

huixie90 edited the summary of this revision. (Show Details)Oct 26 2022, 1:58 AM
huixie90 edited the summary of this revision. (Show Details)Oct 26 2022, 2:02 AM
huixie90 edited the summary of this revision. (Show Details)Oct 26 2022, 2:05 AM
huixie90 edited the summary of this revision. (Show Details)
huixie90 published this revision for review.Oct 26 2022, 2:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 26 2022, 2:10 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Sorry about the very slow review. I have reviewed the code changes but haven't looked at the tests yet. Looking pretty good so far!

libcxx/include/__iterator/concepts/can_reference.h
14 ↗(On Diff #470745)

Nit: extraneous blank line.

libcxx/include/__iterator/concepts/input_or_output_iterator.h
16 ↗(On Diff #470745)

Nit: extraneous blank line.

libcxx/include/__iterator/concepts/weakly_incrementable.h
18 ↗(On Diff #470745)

Nit: unnecessary extra blank line.

libcxx/include/__ranges/elements_view.h
82

Optional: consider using __iterator</*_Const=*/false>. Personally, I find this trick of "annotating" the meaning of literals pretty helpful when reading code.

142

This doesn't need _LIBCPP_HIDE_FROM_ABI because it's consteval?

179

Question: what does _Ele stand for? Abbreviated names like this usually end with a consonant.

184

Optional: I wonder if a generic __get_iterator_concept function that allows setting a "maximum" (most constrained) tag would be useful. This function is mostly the same as the one in ranges_iterator_concept.h, except it can never return a contiguous_iterator. It might be overkill, though -- and in either case, it's just a thought, not something to address in this patch.

336

Would this benefit from no_unique_address?

344

Question: the parentheses are to make sure decltype(auto) deduces a reference, right?

var-const added inline comments.Nov 10 2022, 3:37 PM
libcxx/include/__tuple/make_tuple_types.h
65 ↗(On Diff #470745)

Question: can you explain the idea here?

66 ↗(On Diff #470745)

Nit: can you separate these two aliases with a blank line?

philnik added inline comments.Nov 10 2022, 4:22 PM
libcxx/include/__iterator/concepts/can_reference.h
2 ↗(On Diff #470745)

I don't think we should granularize __iterator/concepts.h. Compiling the header takes just ~35ms, 20 of which are including <type_traits>. So we'd save maybe 10ms by granularizing it, which I don't think is worth it. __iterator/concepts.h also isn't very large at ~300 LoC, so it also doesn't increase readability much.

huixie90 added inline comments.Nov 15 2022, 7:41 AM
libcxx/include/__iterator/concepts/can_reference.h
2 ↗(On Diff #470745)

I wasn't too concerned about compilation time. Without doing this, we will add public dependency from <tuple> to <concepts> (see description). I'd like to avoid adding dependencies like this so lifted several headers required by subrange's forward declaration

philnik added inline comments.Nov 15 2022, 8:31 AM
libcxx/include/__iterator/concepts/can_reference.h
2 ↗(On Diff #470745)

I'm not sure what exactly you mean. __iterator/concepts.h doesn't include <concepts>. Did this change between the creation of this patch and current trunk?

huixie90 added inline comments.Nov 18 2022, 12:47 PM
libcxx/include/__iterator/concepts/can_reference.h
2 ↗(On Diff #470745)

Yes. things changed a lot since the creation of this patch. I think the main change is this patch
https://github.com/llvm/llvm-project/commit/89b356f05ab7aa3d96fc7b68aece6e7a5bdb0db5

After this patch, I guess the dependency is removed. I will try rebase and see what happens in the CI

huixie90 updated this revision to Diff 476588.Nov 18 2022, 1:29 PM
huixie90 marked 7 inline comments as done.

rebase

avogelsgesang added inline comments.
libcxx/include/__ranges/elements_view.h
297

please also mark elements_view::iterator on https://libcxx.llvm.org/Status/Spaceship.html as done

huixie90 updated this revision to Diff 476744.Nov 20 2022, 7:32 AM
huixie90 marked 3 inline comments as done.

address comments

libcxx/include/__ranges/elements_view.h
142

That is my understanding. After all it is a function used only at compile time so it does not have any ABI concerns. Or did I miss anything?

344

yes.

libcxx/include/__tuple/make_tuple_types.h
65 ↗(On Diff #470745)

the spec defines subrange is also a tuple-like
https://eel.is/c++draft/tuple.like#concept:tuple-like

Before this patch, libc++ defines tuple-like to be only pair, array and tuple
https://github.com/llvm/llvm-project/blob/main/libcxx/include/__tuple/tuple_like.h

This patch makes subrange also a tuple-like. (see the diff in tuple_like.h)

The file in question is creating some meta functions to create a flat list of underlying types given a tuple-like type, and this function is used in the conversions between tuple-like types. One example would be pair::pair(pair-like auto&&)

You will see the few line above there are several specialisations.

  1. for tuple<Ts...> it just produces Ts...
  2. for array<T, N> it produces T, T, T, T, ...
  3. for pair<First, Second>, it produces First, Second

Now I am adding another one

  1. for subrange<Iter, Sent, Kind>, it produces Iter, Sent (note that subrange has a non-type template parameter at the 3rd place, so it won't match any of the existing specialisations.

Sorry about the very slow review. Looks good with just a few nits/comments.

libcxx/include/__ranges/elements_view.h
82

Please apply below as well (with __sentinel, mostly).

134

Does this also need a test?

libcxx/include/__tuple/make_tuple_types.h
65 ↗(On Diff #470745)

Thanks for the explanation! In that case, perhaps the variadic __element_type is unnecessary? Would something like this work?

template <class _Tp, class _ApplyFn = __apply_cv_t<_Tp>>
using __apply_quals = __tuple_types<
    typename _ApplyFn::template __apply<_Iter>,
    typename _ApplyFn::template __apply<_Sent>>;
libcxx/test/std/ranges/range.adaptors/range.elements/adaptor.pass.cpp
139

I'd suggest also testing e.g. keys | values, or any other case where the two adaptors use different indices.

libcxx/test/std/ranges/range.adaptors/range.elements/base.pass.cpp
77

Ultranit: please add a newline before this line.

libcxx/test/std/ranges/range.adaptors/range.elements/ctor.view.pass.cpp
30

This should probably be std::is_convertible_v.

libcxx/test/std/ranges/range.adaptors/range.elements/general.pass.cpp
31

Nit: I don't feel strongly about using snake_case or camelCase for local variables (I _personally_ use snake case when I can, but I don't think we have a hard rule on that), but it would be better to use one style consistently (currently historical_figures and expectedYears are inconsistent with each other).

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/arithmetic.pass.cpp
49

Nit: I think ElemIter would be a little better as a name (applies throughout).

53

Question: is the empty comment to enforce a certain formatting?

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/base.pass.cpp
54

Question: why not use std::same_as<> decltype(auto) on the previous line instead?

83

Same nit: s/Ele/Elem/.

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/compare.pass.cpp
35

Nit: empty lines after each comparison operator would be pretty helpful.

112

Optional: check that it1 == it1 and it2 == it2 as well? (Maybe even the same for the != operator)

132

Perhaps also check not_equal_to, for completeness' sake?

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/ctor.base.pass.cpp
12

Nit: extra semicolon.

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/ctor.default.pass.cpp
50

Ultranit: please add a newline before this line.

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/decrement.pass.cpp
68

Optional: consider switching the order of branches (so that the check becomes if (!std::bidirectional_iterator)). The else branch is much shorter, so if it's close to the condition, it's easy to see both branches at the same time. In the current state it requires a bit of scrolling to find the else.

68

Optional: consider adding a blank line before this line.

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/increment.pass.cpp
52

Optional: consider adding a blank line before this line.

libcxx/test/std/ranges/range.adaptors/range.elements/range.concept.compile.pass.cpp
46

Optional: would it make sense to also static_assert these conditions? If you think it's overkill, feel free to disregard.

libcxx/test/std/ranges/range.adaptors/range.elements/sentinel/minus.pass.cpp
100

Optional nit: would writing a constraint be slightly more readable? (Maybe not -- feel free to push back)

libcxx/test/std/ranges/range.adaptors/range.elements/size.pass.cpp
45

Very optional: I think theoretically it's also possible to have a size() const without size() (if you = delete the non-const size), but it's probably too convoluted to test.

libcxx/test/std/ranges/range.adaptors/range.elements/types.h
37

Ultranit: extra space.

91–93

Ultranit: the assignments are slightly unaligned.

philnik added inline comments.Nov 29 2022, 2:08 AM
libcxx/include/__ranges/elements_view.h
128–132

I know it sucks, but we have to move the iterators and sentinels outside the views.

var-const added inline comments.Dec 9 2022, 7:39 PM
libcxx/docs/Status/Cxx20Issues.csv
284

Can you also check if this patch addresses https://wg21.link/LWG3302, and if so, mark it as complete as well?

var-const added inline comments.Dec 9 2022, 7:44 PM
libcxx/docs/Status/Cxx20Issues.csv
284

And also https://cplusplus.github.io/LWG/issue3323 (that one looks like it was superseded by a later revision of the Standard).

huixie90 updated this revision to Diff 481914.Dec 11 2022, 8:58 AM
huixie90 marked 26 inline comments as done.

address comments

huixie90 added inline comments.Dec 11 2022, 9:00 AM
libcxx/include/__tuple/make_tuple_types.h
65 ↗(On Diff #470745)

Yes that looks much better. I will remove the ....
Thanks for the suggestion

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/arithmetic.pass.cpp
53

Yes. if you have strong feelings I can remove them and put

// clang-format off
// clang-format on

around them

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/base.pass.cpp
54

as of the patch was written (about 2-3 months ago?), Some compilers in the CI which were based on older version of clang has a bug where std::same_as<Foo&> decltype(auto) = ... does not work if the return type is a reference

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/decrement.pass.cpp
68

clang-format will remove that empty line

var-const accepted this revision.Dec 12 2022, 12:41 PM

Thanks a lot for working on this! Once this lands, we will only have split_view between our current state and a full C++20 implementation of Ranges.

I can do a follow-up to mark some papers and LWG issues that are complete now that elements_view is implemented (there are quite a few!). Feel free to ignore my comments re. papers and issues.

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/arithmetic.pass.cpp
53

No strong feelings, just making sure it's deliberate.

libcxx/test/std/ranges/range.adaptors/range.elements/iterator/base.pass.cpp
54

Ah, in that case, let's keep as is.

This revision is now accepted and ready to land.Dec 12 2022, 12:41 PM
var-const added inline comments.Dec 12 2022, 5:25 PM
libcxx/docs/Status/Cxx20Papers.csv
111

It's a _major_ paper, so it should definitely be added to libcxx/docs/ReleaseNotes.rst.

@huixie90 I did the follow-up to mark papers and issues as done: https://reviews.llvm.org/D139900. Many of those are finished by this patch. If you'd like, feel free to update this patch to mark more papers (I think everything except P2325 is completed by this patch). But otherwise, feel free to submit as-is (except my comment about release notes, although we can do that in a follow-up as well if you'd like).

ldionne added inline comments.Dec 13 2022, 9:53 AM
libcxx/include/__tuple/tuple_like.h
29–33 ↗(On Diff #481924)

Here we seem to be conflating two things:

  1. This old __tuple_like extension that I've been trying to get rid of (and did get rid of in std::tuple), and
  2. The new tuple-like exposition-only concept that was introduced recently and was retrofitted into std::pair.

I would prefer if we introduced (2) without touching (1), so that we can proceed to the cleanup of (1) and related machinery like __tuple_convertible & friends separately.

It'll end up being nearly equivalent, but what I would do instead is introduce the new tuple-like and pair-like C++20 concepts separately and give them a name like __cpp20_tuple_like. We can then clean up the mess inside <pair>, remove the non-standard extension pre-C++20 and finally rename __cpp20_tuple_like and __cpp20_pair_like to __tuple_like and __pair_like once that's done.

That way, this patch will be completely orthogonal to touching pair, which I think is a good thing.

philnik added inline comments.Dec 13 2022, 10:19 AM
libcxx/include/__tuple/tuple_like.h
29–33 ↗(On Diff #481924)

IMO it would be better to rename the current __tuple_like etc. to something like __tuple_like_ext. Otherwise people will assume that __tuple_like is the standard tuple-like, since that's what our naming scheme normally is.

huixie90 updated this revision to Diff 483611.Dec 16 2022, 11:19 AM
huixie90 marked 4 inline comments as done.

Address feedback

Herald added a project: Restricted Project. · View Herald TranscriptDec 16 2022, 11:19 AM
huixie90 added inline comments.Dec 16 2022, 11:23 AM
libcxx/include/__tuple/tuple_like.h
29–33 ↗(On Diff #481924)

I renamed the exiting __tuple_like to __tuple_like_ext and introduced the new __tuple_like exposition only concept

var-const accepted this revision.Dec 16 2022, 2:22 PM
ldionne accepted this revision.Jan 12 2023, 9:27 AM
This revision was landed with ongoing or failed builds.Jan 15 2023, 9:36 AM
This revision was automatically updated to reflect the committed changes.