Page MenuHomePhabricator

[libc++][ranges] Implement rbegin, rend, crbegin and crend.
ClosedPublic

Authored by var-const on Feb 4 2022, 10:42 PM.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Quuxplusone added inline comments.Feb 5 2022, 8:41 AM
libcxx/include/__ranges/access.h
285

I believe your __can_reverse needs to include !__unqualified_rbegin<_Tp> && !__member_rbegin<_Tp> &&, or else you need to include them ad-hoc right here. I have a moderate preference for not ad-hoc, even if it means that you'll have to duplicate the concept into a __can_reverse_begin and a __can_reverse_end for use further down.
Please add a regression test that causes overload resolution ambiguity with your current overload set.

286

Attn @ldionne — it's our new policy to start using unadorned std:: in new code, is that right? Or should we keep the _VSTD:: convention in case the release/14.x process discovers an unexpected problem and we need to roll back the #define _VSTD std change?
(Using std:: here is totally fine if it's our policy; I just want to hear a clear "yes" from @ldionne.)

291

You don't need this — do you? Check whether ranges::begin has it, and be consistent with whatever it is that they do.

334

As above: this overload as written is asking for complete types, which should be handled by points (2.4) and (2.5) instead; so remove this overload.

libcxx/test/std/ranges/range.access/begin.pass.cpp
1 ↗(On Diff #406161)

These changes to begin.pass.cpp and end.pass.cpp LGTM, but not directly relevant to this PR. I say go ahead and land these two files (assuming that they still pass after rebasing on trunk), and then this PR will get a bit shorter. Thanks for the cleanup!

This revision now requires changes to proceed.Feb 5 2022, 8:41 AM

Btw, once the bugs are polished out, I think this would be an obvious candidate to cherry-pick back to release/14.x. It would be really great to be able to say that libc++14 includes all of the iterator CPOs.

@var-const: Please also update libcxx/test/std//library/description/conventions/customization.point.object/cpo.compile.pass.cpp, and git grep rbegin to see if there's any more places that need updating.

var-const updated this revision to Diff 406722.Feb 8 2022, 1:14 AM
var-const marked 7 inline comments as done.

Address review feedback

var-const updated this revision to Diff 406723.Feb 8 2022, 1:15 AM

Rebase upon main.

var-const updated this revision to Diff 406725.Feb 8 2022, 1:17 AM
var-const marked an inline comment as done.

Remove redundant redefinition of __can_borrow.

var-const updated this revision to Diff 406726.Feb 8 2022, 1:19 AM

Run libcxx-generate-files

libcxx/include/__ranges/access.h
16

Done. (Note that in __iterator/, the header structure is access.h/reverse_access.h)

226–229

Thanks for calling it out. For now, I'd prefer to leave this as a copy-paste from the Standard, but I'm interested to play around with whether the two versions are equivalent. I'll let you know what I find.

262

You suggested on D118963 that sizeof(_Tp) != 0 would be better, and I agree with you. Please make the substitution throughout.

Done.

Also, please order the overloads in the same order as the bullet points in the Standard, just for the benefit of future readers. http://eel.is/c++draft/range.access#rbegin-2 This is bullet point... uh... wait... actually this isn't one of the points at all! The "bounded array of complete type" case is handled in the Standard by point (2.5).

Yeah, I was trying to use the same ordering and created an extra clause for handling arrays specifically to satisfy 2.2 (which is otherwise identical to 2.5). Removed it now since like you said it is already handled implicitly.

I suspect you can dig into this and find a situation where your current overload set produces ambiguity.

Hmm, both Mine[10] and std::string[10] compile fine. When I was writing this, I thought there would be no ambiguity because constraints are only checked on functions with the same signature; thus, template argument deduction would always prefer the (_Tp (&)[_Np]) signature over the (_Tp&&) signature, before concepts come into play. I might well be wrong, though.

285

This is a great catch, thanks! Added a test structure (MemberBeginAndRBegin) and made sure it fails without the code change.

286

(Yeah, I did that due to the recent patch/direction to remove _VSTD. Happy to use _VSTD if necessary)

291

It is the same in ranges::begin. I don't know the rationale -- presumably if overload resolution selects a deleted function, it produces a less verbose error than when it cannot find a match.

299

Removed. I don't want to block this patch on this, but in general I prefer to have blank lines. I feel like the opening (or closing) of a namespace and the first (last) element of that namespace don't have any special relationship to warrant grouping them together.

libcxx/test/std/ranges/range.access/begin.pass.cpp
1 ↗(On Diff #406161)
Quuxplusone requested changes to this revision.Feb 8 2022, 11:52 AM

Continues to look pretty much good. Please see what you can do to shorten the tests — 535 lines for rend.pass.cpp seems excessive, for example. I know a big part of that comes from being consistent with the existing end.pass.cpp, though, so it's not a blocker.

libcxx/include/__ranges/rbegin.h
19

You don't need enable_borrowed_range in this file. (Just the borrowed_range concept itself, which comes from concepts.h). enable_borrowed_range.h is the bare-bones "just the trait" header for people who need to specialize the trait but don't care about querying the concept.

I suspect the similar inclusion in __ranges/access.h might also be unused.

21

Can you be more granular than all of <concepts>?

25
86
libcxx/include/__ranges/rend.h
18

also #include <__ranges/rbegin.h>

88

Consider adding a regression test, although maybe that'll end up looking too silly, once you try it.

libcxx/test/std/ranges/range.access/rbegin.pass.cpp
125–129

As in the other review, I'd say that EmptyRBeginMember is redundant with RBeginMemberReturnsInt; consider removing it.

301

remove extra blank line

302

SGTM. Do you have a test for struct EndWithoutBegin { int *end() const; } that proves such a type is not rbegin'able?

365–366

This is an even simpler case, IIUC: both types are iterators, with the same value_type, interconvertible (well, at least in one direction), and yet still they aren't the same type, so the type is not rbegin'able.

I consider FunctionBeginEndDifferentTypes redundant with this test.

383

I consider FunctionBeginEndForwardIterators redundant with MemberBeginEndForwardIterators.

402

I consider FunctionEndOnly redundant with MemberEndOnly (I'd just keep the latter); and I'm not sure that MemberBeginOnly and FunctionBeginOnly are actually testing anything worth testing, since "obviously" one can't get a reverse-iterator-to-end-of-range out of nothing but a begin() method.

libcxx/test/std/ranges/range.access/rend.pass.cpp
445

LGTM, but please also test that

static_assert(std::same_as<std::invoke_result_t<RangeREndT, MemberBeginAndRBegin&>, int*>);

(and not reverse_iterator<int*>). Actually, it would be profitable to replace all your positive std::is_invocable_v assertions with positive std::same_as assertions. It's free test coverage!

This revision now requires changes to proceed.Feb 8 2022, 11:52 AM
var-const updated this revision to Diff 407044.Feb 8 2022, 9:42 PM
var-const marked 10 inline comments as done.

Address review feedback.

libcxx/include/__ranges/rbegin.h
19

Right. access.h still needs to keep the include (it uses enable_borrowed_range in the definition of __can_borrow).

21

Done (and it looks like access.h doesn't need <concepts> at all).

libcxx/include/__ranges/rend.h
88

Thanks for catching this! Added two tests structs (NoThrowBeginThrowingEnd and NoThrowEndThrowingBegin).

I think, however, that it has to be just ranges::begin(__t), not std::make_reverse_iterator(ranges::begin(__t)). make_reverse_iterator is not marked noexcept, so IIUC, it will always lead to noexcept(false). At the same time, it doesn't throw any exceptions of its own, thus the actual behavior solely depends on whether ranges::begin(__t) can throw. Does this sound right to you? I can confirm that adding make_reverse_iterator breaks the existing noexcept tests.

libcxx/test/std/ranges/range.access/rbegin.pass.cpp
301

Hmm, this is consistently used in the existing begin/end.pass.cpp tests to separate different groups of test cases (basically, two empty lines after every test function). I don't particularly like the style, but I followed it for consistency. If these are to be removed, they should be removed from the existing tests as well. What do you think?

302

I think MemberEndOnly is the equivalent test.

365–366

Replaced char* with const int*. I'd rather keep bidirectional_iterator for consistency with other test cases.

383

See my comment below re. Function/MemberEndOnly.

402

I don't feel particularly strongly about keeping these. My intention was to make sure that all these incorrect cases are silently SFINAE'd away as opposed to leading to compilation errors (and they come two versions, member and free, because these are handled by different overloads). So the idea is not to make sure that these can't work (which, like you said, is pretty obvious), but rather that they fail in the expected quiet fashion. If you still feel this isn't worth testing, I can remove these.

libcxx/test/std/ranges/range.access/rend.pass.cpp
445

Done.

Actually, it would be profitable to replace all your positive std::is_invocable_v assertions with positive std::same_as assertions. It's free test coverage!

I'm not sure. It does add to the test coverage, but it's also more verbose and, IMO, doesn't reflect the intention quite as well. In any case, if this is to be done, it should also be done in the existing tests, so it seems more suitable for a separate patch.

Quuxplusone added a reviewer: ldionne.

Somehow the size of rend.pass.cpp went up since I complained about its size. ;)
Anyway, once the "noexcept/expression-equivalent" thing is fixed, I think this is good to go.

@ldionne LGTY? Thoughts on cherry-picking into release/14.x so we can say we've got all of [range.access] in 14.x?

libcxx/include/__ranges/rend.h
88

https://eel.is/c++draft/range.access.rbegin#2.5 is 100% clear that ranges::rbegin(t) must be expression-equivalent to std::make_reverse_iterator(ranges::end(t)), which means that the two expressions must have exactly the same noexceptness. If that means that right now today libc++'s ranges::rbegin is never-noexcept, then OK, that's what it means.

And yep,
https://eel.is/c++draft/reverse.iter.nonmember#7
is also clear that it remains conforming, even in C++20, for make_reverse_iterator to be never-noexcept.

The only thing we could do here that would be non-conforming, would be to have make_reverse_iterator non-noexcept and ranges::rbegin noexcept. That's definitely not permitted by the Standard, because it says the two must be expression-equivalent.

So, please do the "you must write it three times" thing for now (i.e. noexcept(noexcept(the-exact-expression-you're-going-to-return))). And please also triple-check the rest of your noexcept-specifications to make sure they're all correct by this logic.

libcxx/test/std/ranges/range.access/rbegin.pass.cpp
402

Yeah, I'd prefer to see them removed. The place for the silent-SFINAE test is end.pass.cpp/begin.pass.cpp, and I'm 99% sure we've got those tests over there.

libcxx/test/std/ranges/range.access/rend.pass.cpp
445

It does add to the test coverage, but it's also more verbose and, IMO, doesn't reflect the intention quite as well

Well, maybe it changes the perceived intention. Instead of a bunch of similar tests — "this invocation compiles, this one doesn't compile..." — it gives us a bunch of similar tests plus a few "outlier" cases — "this invocation gives T, this invocation gives U, this one doesn't even compile, this invocation gives V..."
Anyway, we can defer this to a followup (or whatever).

@ldionne LGTY? Thoughts on cherry-picking into release/14.x so we can say we've got all of [range.access] in 14.x?

This would be disabled due to it being incomplete anyway, so I don't see the point in cherry-picking it back to 14.x.

libcxx/include/__ranges/access.h
286

Yes, we can use std::, but thanks for checking.

libcxx/include/__ranges/rbegin.h
29

This should be guarded by HAS_NO_INCOMPLETE_RANGES too (and other headers too).

Quuxplusone added inline comments.Feb 9 2022, 2:47 PM
libcxx/include/__ranges/rbegin.h
29

Yes (perhaps), but that's D118736; I think as long as this header is consistent with what we currently do, it's better not to introduce potential churn over it here.

My impression of D118736 is that we're still kinda confused about what we want HAS_NO_INCOMPLETE_RANGES to encompass — I believe in my original PR it would have been included because it's in ranges::; and then in my subsequent tentative proposal it wouldn't have been because it has no ABI implications (no struct layout); and then in your current proposal it would again be included because it's in ranges:: and no std:: concept depends on it. I assume we'll talk about that offline soon. :)

var-const updated this revision to Diff 407391.Feb 9 2022, 9:44 PM
var-const marked 6 inline comments as done.

Address review feedback:

  • fix noexcept and the return types in the overloads that return std::make_reverse_iterator;
  • adjust tests to expect this overload to always not be noexcept;
  • remove redundant tests.
libcxx/include/__ranges/rbegin.h
29

My reasoning was pretty much what @Quuxplusone said -- until D118736 lands, I think new code should follow the existing approach. Do you think we should start applying HAS_NO_INCOMPLETE_RANGES now, without waiting for that patch?

libcxx/include/__ranges/rend.h
88

Thanks for the explanation. Made this function, in both rbegin and rend, follow the "write it 3 times" approach (which also meant replacing the return types).

I think the other overloads are fine -- noexcept is exactly the expression being returned, and I think they can get away with returning auto because _LIBCPP_AUTO_CAST is applied to the return type (same as in the existing begin and end).

philnik accepted this revision.Feb 10 2022, 4:15 AM
philnik added a subscriber: philnik.

LGTM when rebased and CI is happy.

libcxx/include/__ranges/rend.h
67–68

I think every where else struct __fn is used.

This revision is now accepted and ready to land.Feb 10 2022, 4:15 AM
libcxx/include/__ranges/rend.h
67–68

Nice catch! Yes please. @var-const there's one other use of class __fn in __ranges/access.h; if you could drive-by change that to struct (perhaps in a separate one-line commit), that'd be appreciated. :)

88

follow the "write it 3 times" approach (which also meant replacing the return types)

Sorry for my vagueness there; I really intended only the noexcept(noexcept(exactly-expression)) part — I wasn't requesting the -> decltype(exactly-expression) part. I think you should remove the -> decltype part, because:

  • Consistency with other CPOs
  • If it is needed, then please keep it but write a regression test demonstrating the need; if it's not needed then it should go away

(D115607 is related, in the sense that we might one day choose to consistently use an approach that includes -> decltype, but that's far out of scope for this PR.)

ldionne added inline comments.Feb 10 2022, 10:21 AM
libcxx/include/__ranges/rbegin.h
29

I agree. I just spoke with Arthur offline and we agreed on what we needed to do -- we'll try to do it, but the burden shouldn't be on this patch.

var-const marked 6 inline comments as done.
  • replace class __fn with struct __fn (in rend.h and access.h);
  • make overloads that return std::make_reverse_iterator return auto, not decltype(expr);
  • include reverse_iterator.h in rend.h to hopefully fix the modular build.
libcxx/include/__ranges/rend.h
88

Sure, reverted that part.

var-const updated this revision to Diff 408080.Feb 11 2022, 3:23 PM

Rebase on main (note that it made the changes to begin/end.pass.cpp go away).

var-const updated this revision to Diff 408148.Feb 11 2022, 9:46 PM

Fix the CI.