This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][ranges] adds `range` access CPOs
ClosedPublic

Authored by cjdb on Apr 10 2021, 10:36 PM.

Details

Summary
  • std::ranges::begin
  • std::ranges::cbegin
  • std::ranges::end
  • std::ranges::cend
  • std::ranges::iterator (required for end)

Implements parts of:

  • P0896R4 The One Ranges Proposal`

Co-author: @zoecarver

Depends on D90999, D100160.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
cjdb requested review of this revision.Apr 10 2021, 10:36 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 10 2021, 10:36 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb updated this revision to Diff 336642.Apr 10 2021, 10:37 PM
cjdb edited the summary of this revision. (Show Details)

fixes dependency in commit message (NFC)

cjdb updated this revision to Diff 336643.Apr 10 2021, 10:45 PM

corrects and suppresses clang-format due to its inexperience with concepts

cjdb updated this revision to Diff 336674.Apr 11 2021, 9:25 AM
cjdb retitled this revision from [libcxx] Implements "forward" range access CPOs to [libcxx] adds `range` access CPOs.
cjdb edited the summary of this revision. (Show Details)

updates commit message (NFC)

Quuxplusone requested changes to this revision.Apr 11 2021, 9:45 AM
Quuxplusone added inline comments.
libcxx/include/ranges
2–4

Please make the appropriate change to libcxx/utils/generate_header_inclusion_tests.py.
Also, this file needs a copyright header.

libcxx/include/type_traits
2816

This is unconditionally noexcept. I don't think you intended that?

libcxx/test/libcxx/ranges/range.access/access.h
9–10

Header guard doesn't match filename.

103–104

Throughout: please break lines to fit the review window. I suggest breaking after the last , (i.e., semantic linebreaks).

324–327

FWIW, rather than reopening namespace std in the tests, I'd prefer to see

template <>
inline constexpr bool
    std::ranges::enable_borrowed_range<unqualified_rvalue_range> = true;
libcxx/test/std/ranges/range.range/iterator_t.compile.pass.cpp
25

Bikeshed: this seems much too easy to typo. I've been using namespace rg = std::ranges in my own slide code; anyone got thoughts?
Of course, I'm also not a huge fan of this test, since it has dependencies on so many containers. It would be better to do just like

#include <ranges>
#include <type_traits>
#include "test_iterators.h"
struct X {
    forward_iterator<int> begin();
    forward_iterator<int> end();
    forward_iterator<char> begin() const;
    forward_iterator<char> end() const;
};
static_assert(std::is_same_v<std::ranges::iterator_t<X>, forward_iterator<int>>);
static_assert(std::is_same_v<std::ranges::iterator_t<const X>, forward_iterator<char>>);
static_assert(std::is_same_v<std::ranges::iterator_t<double[10]>, double*>);
libcxx/test/support/test_macros.h
292

I don't like this macro at all; I'd much rather you just write out

assert(test());
static_assert(test());

if that's what the test is supposed to be testing.
However, if @ldionne asks you to keep it for some reason, then please at least make it
#define CONSTEXPR_ASSERT(...) assert((__VA_ARGS__)) in C++03 mode, and

#define CONSTEXPR_ASSERT(...) do { \
  static_assert((__VA_ARGS__), ""); \
  assert((__VA_ARGS__)); \
} while (0)

in C++11-and-later mode.

This revision now requires changes to proceed.Apr 11 2021, 9:45 AM
cjdb updated this revision to Diff 336676.Apr 11 2021, 10:01 AM

re-adds missing underscore that was deleted in clang-format cleanup

tcanens added inline comments.Apr 11 2021, 11:07 AM
libcxx/include/__ranges/access.h
68

This needs to reject const rvalue arrays.

76

It'd be nice to avoid an extra move when begin returns a prvalue (as they almost always do).

121

Isn't extent_v<_Tp[_Np]> just _Np?

156

This is never going to be called since _Tp can't be deduced.

cjdb updated this revision to Diff 336684.Apr 11 2021, 12:41 PM
cjdb marked 7 inline comments as done.

addresses feedback from @Quuxplusone and @tcanens

cjdb added inline comments.Apr 11 2021, 12:42 PM
libcxx/test/std/ranges/range.range/iterator_t.compile.pass.cpp
25

Bikeshed: this seems much too easy to typo. I've been using namespace rg = std::ranges in my own slide code; anyone got thoughts?

🤷 I'm happy to bikeshed on Discord (not in-review please).

Of course, I'm also not a huge fan of this test, since it has dependencies on so many containers. It would be better to do just like

Part of the point of this test is to ensure backwards compatibility with all of our containers. That was a design goal for ranges, and should be reflected here IMO.

libcxx/test/support/test_macros.h
292

I don't like this macro at all; I'd much rather you just write out

assert(test());
static_assert(test());

That's pretty error-prone. One might forget one of the asserts, both of which are critical.

#define CONSTEXPR_ASSERT(...) assert((__VA_ARGS__)) in C++03 mode, and

Done.

#define CONSTEXPR_ASSERT(...) do { \
 static_assert((__VA_ARGS__), ""); \
 assert((__VA_ARGS__)); \
} while (0)

in C++11-and-later mode.

I don't see why this change is necessary.

cjdb added inline comments.Apr 11 2021, 12:43 PM
libcxx/include/__ranges/access.h
68

See deleted overload below.

cjdb updated this revision to Diff 336702.Apr 11 2021, 2:42 PM

rebases to activate CI

cjdb updated this revision to Diff 337812.Apr 15 2021, 9:56 AM

rebases to activate CI

I'll have a close look once it passes the build server. I expect pre-merge errors due to conflicts with D90999. Both modify add the <ranges> header.

libcxx/include/CMakeLists.txt
136

Please keep the list sorted. The recently added __memory/* are also sorted.

libcxx/include/__ranges/access.h
10

For consistency _LIBCPP_RANGES_ACCESS_H -> _LIBCPP___RANGES_ACCESS_H.

26

I would like to keep _LIBCPP_STD_VER > 17 to be consistent with <concepts>.

39

Shouldn't remove_cvref_t be remove_cv_t?

libcxx/include/ranges
3

Copy-paste "concepts".

cjdb updated this revision to Diff 339041.Apr 20 2021, 4:29 PM

rebases to activate CI

cjdb updated this revision to Diff 339091.Apr 20 2021, 9:00 PM

rebases to activate CI

cjdb updated this revision to Diff 339332.Apr 21 2021, 11:32 AM

rebases to activate CI

Not yet finished reviewing, but I've been accumulating comments here over the past few days and want to submit them before stuff moves around too much. I'll have more comments later when I do a proper review.

libcxx/include/__ranges/end.h
36 ↗(On Diff #339091)

Nit: space.

73 ↗(On Diff #339091)

This should be copied, right?

80 ↗(On Diff #339091)

I haven't quite made it through all the macros/tests yet but can you please make sure there's a test for this where you declare a hidden friend, something like

namespace std { namespace ranges {

struct dummy {
  friend void begin() { }
};

}}

that would be an ODR violation, but isn't because of this inline namespace?

In other words, please make sure this fails to compile when the inline namespace is removed.

89 ↗(On Diff #339091)

I will begrudgingly point out that these should have three underscores.

libcxx/include/ranges
11

Synopsis usually use a multiline comment.

libcxx/test/libcxx/ranges/range.access/access.h
16

Nit: consider just using structs for all of these.

103–104

Note: the review window is different for everyone.

libcxx/test/std/ranges/range.access/array_access.h
31

How about rvalue array types?

cjdb updated this revision to Diff 339407.Apr 21 2021, 3:24 PM

rebases to activate CI

The array-of-incomplete-element case is IFNDR. I think we really want that case to be a SFINAE-unfriendly hard error, since it's a recipe for disaster (ODR violations).

cjdb added a comment.Apr 24 2021, 9:08 AM

The array-of-incomplete-element case is IFNDR. I think we really want that case to be a SFINAE-unfriendly hard error, since it's a recipe for disaster (ODR violations).

Won't the deleted overloads take care of that?

The array-of-incomplete-element case is IFNDR. I think we really want that case to be a SFINAE-unfriendly hard error, since it's a recipe for disaster (ODR violations).

Won't the deleted overloads take care of that?

Deleted is still SFINAE-friendly.

cjdb updated this revision to Diff 340307.Apr 24 2021, 12:09 PM
cjdb marked 8 inline comments as done.
  • adds extra underscores to headers to make it _LIBCPP___RANGES_* (@zoecarver)
  • makes lvalue arrays of incomplete types SFINAE-unfriendly (verification tests added) (@tcanens)
  • removes _LIBCPP_NOEXCEPT_RETURN (@ldionne)
    • makes __decay_copy conditionally noexcept in C++20 mode
  • adds conformance tests for all ranges for std::iterator_t
    • std::ranges::begin is implicitly tested by std::ranges::iterator_t
    • std::ranges::end is implicitly tested by std::ranges::sentinel_t, which is added in D
  • adds test for ODR violation (@zoecarver)
  • sorts headers in CMakeLists.txt (@Mordante)
libcxx/test/std/ranges/range.access/array_access.h
31

Line 29 takes care of this 🙂

libcxx/test/std/ranges/range.range/iterator_t.compile.pass.cpp
25

Since no discussion occurred, I replaced stdr:: in places where it could be ambiguous with std::ranges. Places where it isn't ambiguous can remain as-is.

cjdb updated this revision to Diff 340311.Apr 24 2021, 1:57 PM
cjdb retitled this revision from [libcxx] adds `range` access CPOs to [libcxx][ranges] adds `range` access CPOs.
  • fixes Windows build failure
  • parameterises test_range
zoecarver added inline comments.Apr 26 2021, 12:47 PM
libcxx/include/__ranges/begin.h
30 ↗(On Diff #340311)

Nit: You keep opening and closing this namespace but everything in this file goes in it. Why not just open it at the beginning and leave it open?

36 ↗(On Diff #340311)

Seems like it might be helpful to have this in a more general place, WDYT?

64 ↗(On Diff #340311)

I'm confused, why can't we just do

static_assert(__is_complete<remove_cv_t<_Tp> >, "...");
return __t + 0;

?

libcxx/test/std/ranges/range.access/member_access.h
44

Nit: !std::is_...

libcxx/test/std/ranges/range.access/unqualified_lookup_access.h
23

Maybe make this and the other one noexcept(false) with a comment about why.

Okay, to be honest, I really do not like these tests.

I think we need to workshop the structure here because the current tests fall down in terms of readability and demonstrability. We can get to correctness and completeness later, but let's get the model right first.

Tests shouldn't have too much boilerplate, and in the test file itself, it should be clear what is being tested and how it's being tested. There should be enough context to figure out what's going on.

The current tests in ranges/range.access/* fail at this. There is a lot of boilerplate. We should try to be modest with the use of macros and only use them when they are unequivocally the best answer, and there isn't another clear way to do something. In these tests everything, including the main function, is hidden inside of a macro. This is not readable.

A good test would look like this:

struct a_clearly_named_type;
static_assert(!is_invocable_v<RangesBeginT, a_clearly_named_type>);

There are a few things here: first, it is clear what is being tested because of the context. The name CHECK_MEMBER_ACCESS tells me very little. However, the expression !is_invocable_v tells me that we shouldn't be able to call ranges::begin because of some constraint. Hopefully, the type a_clearly_named_type explains what constraint is being violated.

Second, it's easily verifiable. If I'm reading this test with the standard next to me, I can easily match the text in the standard to the static_assert and check it off mentally. It is much more difficult to do this when you have to follow the input into a macro full of boilerplate and distractions where the code is generated. My mind does not have a large enough cache for this to be feasible, sorry :P

It would be one thing if these macros were stress testing concepts, or ranges, or whatever. But they're not. They're being used for the tests that are supposed to demonstrate the API and its correctness.

The issues above are making it hard for me to verify correctness, but these tests are definitely not complete. For example, where are the tests for a type without any members? Or a member with the wrong return type? I think there are a few tests you need to add; luckily, I think these will be immediately obvious with a new test structure.

cjdb added a comment.Apr 26 2021, 2:39 PM

Okay, to be honest, I really do not like these tests.

I think we need to workshop the structure here because the current tests fall down in terms of readability and demonstrability. We can get to correctness and completeness later, but let's get the model right first.

Tests shouldn't have too much boilerplate, and in the test file itself, it should be clear what is being tested and how it's being tested. There should be enough context to figure out what's going on.

The current tests in ranges/range.access/* fail at this. There is a lot of boilerplate. We should try to be modest with the use of macros and only use them when they are unequivocally the best answer, and there isn't another clear way to do something. In these tests everything, including the main function, is hidden inside of a macro. This is not readable.

A good test would look like this:

struct a_clearly_named_type;
static_assert(!is_invocable_v<RangesBeginT, a_clearly_named_type>);

There are a few things here: first, it is clear what is being tested because of the context. The name CHECK_MEMBER_ACCESS tells me very little. However, the expression !is_invocable_v tells me that we shouldn't be able to call ranges::begin because of some constraint. Hopefully, the type a_clearly_named_type explains what constraint is being violated.

Second, it's easily verifiable. If I'm reading this test with the standard next to me, I can easily match the text in the standard to the static_assert and check it off mentally. It is much more difficult to do this when you have to follow the input into a macro full of boilerplate and distractions where the code is generated. My mind does not have a large enough cache for this to be feasible, sorry :P

It would be one thing if these macros were stress testing concepts, or ranges, or whatever. But they're not. They're being used for the tests that are supposed to demonstrate the API and its correctness.

The issues above are making it hard for me to verify correctness, but these tests are definitely not complete. For example, where are the tests for a type without any members? Or a member with the wrong return type? I think there are a few tests you need to add; luckily, I think these will be immediately obvious with a new test structure.

I agree, will look into this.

libcxx/include/__ranges/begin.h
30 ↗(On Diff #340311)

I think @ldionne wants stuff to be indented inside this namespace, and I don't want to do more than one indentation.

36 ↗(On Diff #340311)

Where do you suggest?

64 ↗(On Diff #340311)

__t + 0 yields a cryptic diagnostic (that could also be a red herring) when the condition is false.

I also agree with Zoe on the point of testing, but it's been said before so no need for me to. I'm looking forward to the update!

libcxx/include/CMakeLists.txt
23–26

I have to admit this is one instance of a split that, IMO, doesn't add anything. I think it makes a lot more sense to group those into the same header since they are basically always used together (you pretty much always need end when you use begin and vice versa).

I'd throw that into something like __ranges/access.h.

libcxx/include/__ranges/begin.h
30 ↗(On Diff #340311)

My general rule of thumb is to go for clarity - when I open a namespace and shove a lot of things in it, I tend not to indent everything, but I add a comment at the closing brace. When I open a namespace for just a few things, I generally indent them and skip the closing brace comment since we can easily see what the brace is related to from the indentation. So, no hard rule here, really just do what's most readable.

68 ↗(On Diff #340311)

Typo: is SFINAE-unfriendly on arrays

Also, of an incomplete types should not be plural.

libcxx/include/__ranges/end.h
62 ↗(On Diff #340311)

Same typos.

libcxx/include/ranges
20

Is it really relevant to mark those as being part of an unspecified inline namespace in the synopsis?

libcxx/test/libcxx/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp
29 ↗(On Diff #340311)

I'd suggest removing the file name here, it's just noise when we move stuff around.

cjdb marked an inline comment as done.Apr 26 2021, 4:04 PM
cjdb added inline comments.
libcxx/include/ranges
20

🤷 Depends on how much we want our synopses to reflect the standard synopses?

expnkx added a subscriber: expnkx.Apr 26 2021, 5:21 PM

Hello. When are we going to have std::ranges::contiguous_range?

Hello. When are we going to have std::ranges::contiguous_range?

When it gets implemented. We're working towards that. I think Zoe was working on it this week.

Also, this is the wrong place to ask for this. This is the right forum for code reviews. Please take a look at our Discord channel for other questions.

ldionne added inline comments.Apr 27 2021, 7:26 AM
libcxx/include/ranges
20

Sure, I don't mind either way.

ldionne requested changes to this revision.Apr 28 2021, 9:16 AM
ldionne added inline comments.
libcxx/test/libcxx/ranges/range.access/access.h
135

I'm not seeing the point of testing those as libc++-only tests. Is it not possible to get equivalent coverage without reaching into the entrails of libc++?

We normally try to only create libc++-specific tests for libc++-specific behavior (like a vendor extension or some specific guarantee that we provide but isn't mandated by the spec).

libcxx/test/support/test_macros.h
292

Honestly I think defining a CONSTEXPR_ASSERT macro is much more error-prone than just spelling it out. I'm generally totally in favour of eliminating duplication, but not when that duplication is both minimal and helpful to see explicitly. I'd rather not add CONSTEXPR_ASSERT, I think it obfuscates things more than anything else.

This revision now requires changes to proceed.Apr 28 2021, 9:16 AM
ldionne added inline comments.Apr 28 2021, 3:07 PM
libcxx/include/__ranges/begin.h
88 ↗(On Diff #340311)

What is the purpose of that overload?

zoecarver added inline comments.Apr 28 2021, 3:10 PM
libcxx/include/__ranges/begin.h
88 ↗(On Diff #340311)

It's supposed to make the error message easier to read. I had it in an earlier version of ranges::size but decided to remove it after some discussion: https://reviews.llvm.org/D101079#inline-953328

Here's a gist I made for the difference in error messages for ranges::size: https://gist.github.com/zoecarver/594015f42664e3daa7ab7c3978027682

The ranges::begin errors may look different, though.

cjdb updated this revision to Diff 341347.Apr 28 2021, 4:10 PM
cjdb marked 4 inline comments as done.
  • updates tests for begin and cbegin (tests for end and cend to come after initial feedback on begin)
  • removes libc++ tests
  • removes CONSTEXPR_ASSERT
zoecarver added inline comments.Apr 29 2021, 9:45 AM
libcxx/test/std/ranges/range.access/begin.h
39 ↗(On Diff #341347)

nit: maybe use borrowed here to match everything else, but it's nonblocking.

71 ↗(On Diff #341347)

I guess it doesn't hurt to have this but at what point are you going to have a const rvalue?

220 ↗(On Diff #341347)

Do we really need a test for this? Could you even write an implementation that picked the wrong begin?

346 ↗(On Diff #341347)

I should add a test like this for ranges::size :)

346 ↗(On Diff #341347)

How about the reverse of this members_with_bad_lvalue_adl?

430 ↗(On Diff #341347)

For future reference: I'm not sure we need rvalue and lvalue types when testing something like this. That logic has already been tested, so one test with a data member should be sufficient.

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

Copy paste error?

228 ↗(On Diff #341347)

Why the extra parens?

229 ↗(On Diff #341347)

Why is this commented out?

libcxx/test/std/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp
28 ↗(On Diff #341347)

I think it would make more sense to call std::ranges::begin directly here. Certainly don't use __begin::__fn, especially if it's not in a libc++ test (which this probably shouldn't be anyway).

libcxx/test/std/ranges/range.access/range.access.cbegin/cbegin.pass.cpp
48 ↗(On Diff #341347)

I'm generally fairly wary of tests like this where the expected value is computed. I think the best tests are the ones where the "desired result" or expected value are concrete/literal. It's easier to read and verify that way. Additionally, if there was a bug in the implementation (for example if we couldn't use as_const for some reason) it wouldn't be caught.

That begin said, I don't need you to change anything here, I just wanted to point it out so you could think about this going forward. The most important check here is the std::invocable<cbegin_t&, T> one, and that one isn't computed (at least not in the same way).

112 ↗(On Diff #341347)

I would expect this to be false. It seems like all over this test rvalues with borrowing disabled are allowed when they shouldn't be.

165 ↗(On Diff #341347)

Same as in the other file.

cjdb added a subscriber: cor3ntin.Apr 29 2021, 10:36 AM

@cjdb the following should work (but doesn't):

static_assert(std::is_invocable_v<RangeBeginT, int (&)[]>);
cjdb updated this revision to Diff 341686.Apr 29 2021, 3:50 PM

nice catch @zoecarver, fixed now

cjdb updated this revision to Diff 341724.Apr 29 2021, 5:48 PM
cjdb edited the summary of this revision. (Show Details)

adopts @zoecarver's simpler tests

cjdb updated this revision to Diff 341728.Apr 29 2021, 6:27 PM

rebases to activate CI

zoecarver accepted this revision as: zoecarver.Apr 29 2021, 10:53 PM

A few nits but other than that this LGTM. Let's finally get this landed (as soon as Louis signs off on it)!

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

You can remove this now that incomplete arrays are tested elsewhere.

libcxx/test/std/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp
24 ↗(On Diff #341728)

I still feel like this is a bit of an awkward way to test this.. why not call it in the body of the function?

libcxx/test/std/ranges/range.access/range.access.cbegin/incomplete.compile.verify copy.cpp
1 ↗(On Diff #341728)

It looks like this file is duplicated. It's named "verify copy.cpp"

libcxx/test/std/ranges/range.access/range.access.end/end.cpp
22 ↗(On Diff #341728)

Why are we making this a reference type?

cjdb added inline comments.Apr 29 2021, 11:48 PM
libcxx/test/std/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp
28 ↗(On Diff #341347)

Do you mean something like static_assert(requires { std::ranges::begin(std::declval<incomplete(&)[]>()) });?

libcxx/test/std/ranges/range.access/range.access.end/end.cpp
22 ↗(On Diff #341728)

std::ranges::end(x) is invoking std::ranges::__end::__fn::operator() as an lvalue, so we should be checking that, IMO.

ldionne accepted this revision.Apr 30 2021, 8:08 AM
ldionne added inline comments.
libcxx/test/std/ranges/range.access/range.access.begin/begin.pass.cpp
205 ↗(On Diff #341728)

Glad to see this, I was going to request exactly it.

Let's land this!

libcxx/test/std/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp
28 ↗(On Diff #341347)

No I mean you could do something like:

void test(incomplete(&arg)[]) {
  std::ranges::begin(arg);
}

Or

std::ranges::begin(std::declval<incomplete(&)[]>());

This is how someone is actually going to be using the function object when we expect to see the error.

Anyway, this isn't a big deal so either way is fine.

cjdb added a comment.Apr 30 2021, 9:51 AM

Most of Zoe's comments have been applied just before merging with main.

libcxx/test/std/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp
28 ↗(On Diff #341347)

Since this is a test for SFINAE friendliness, I don't think I can achieve that (I did try).

This revision was not accepted when it landed; it landed in state Needs Review.Apr 30 2021, 9:57 AM
This revision was automatically updated to reflect the committed changes.
zoecarver added inline comments.Apr 30 2021, 9:58 AM
libcxx/test/std/ranges/range.access/range.access.begin/incomplete.compile.verify.cpp
28 ↗(On Diff #341347)

If this is a test for SFINAE friendliness, then it is important that the above code I posted causes this to fail to compile. Luckily it appears that it does. I just tested this

std::ranges::begin(std::declval<Incomplete(&)[]>());

locally and it produced

atic_assert failed due to requirement '__complete' "`std::ranges::begin` is SFINAE-unfriendly on arrays of an incomplete type."
        static_assert(__complete, "`std::ranges::begin` is SFINAE-unfriendly on arrays of an incomplete type.");
        ^             ~~~~~~~~~~
/Users/zoecarver/Developer/llvm-source/llvm-project/libcxx/test/std/ranges/range.access/range.access.begin/begin.pass.cpp:59:21: note: in instantiation of function template specialization 'std::ranges::__begin::__fn::operator()<Incomplete []>' requested here
  std::ranges::begin(std::declval<Incomplete(&)[]>());