This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][ranges] Add `random_access_{iterator,range}`.
ClosedPublic

Authored by zoecarver on Apr 26 2021, 11:29 AM.

Diff Detail

Event Timeline

zoecarver requested review of this revision.Apr 26 2021, 11:29 AM
zoecarver created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptApr 26 2021, 11:29 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
zoecarver added inline comments.Apr 26 2021, 11:33 AM
libcxx/include/__iterator/concepts.h
150

Will be removed when rebased.

  • Fix comment.
cjdb added a comment.Apr 26 2021, 1:51 PM

Looking at the list of files, we need to:

  • replace bidirectional_iterator with random_access_iterator for random-access iterators in all iterator_concept_conformance.compile.cpp
  • add a test for all the ranges that are not random_access_ranges (and similarly for any bidirectional_iterators that aren't random-access)
libcxx/test/std/containers/sequences/array/range_concept_conformance.compile.pass.cpp
30

Please replace the bidirectional_range test.

libcxx/test/std/re/re.results/range_concept_conformance.compile.pass.cpp
25

This should be !random_access_range, no?

Some remarks, mostly minor. But I really would like to see it pass a CI run.

libcxx/test/std/containers/sequences/forwardlist/range_concept_conformance.compile.pass.cpp
28 ↗(On Diff #340597)

I don't think forward_list has a random_access_iterator.

libcxx/test/std/containers/sequences/list/range_concept_conformance.compile.pass.cpp
26

I don't think list has a random_access_iterator.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
32

If we don't do this I think we should remove static_assert(std::random_access_iterator<random_access_iterator<int*> >); above.

55

Is there a reason to only name the second argument?

76

These classes share a lot of the same boiler-plate. That makes it hard to spot the part being tested. How do you feel about moving the common part to a macro?

Quuxplusone requested changes to this revision.Apr 28 2021, 12:15 PM
Quuxplusone added inline comments.
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
32

My impression is that we're not adding cxx20_anything_iterator except for cxx20_input_iterator (by which we mean "move-only input iterator"). I don't even think cxx20_forward_iterator (line 28) exists (nor should it).

But @Mordante, why do you say you'd remove the test for std::random_access_iterator<random_access_iterator<int*>>? I would say that all our test iterators should satisfy the appropriate C++20 concepts; if e.g. we have a test bidirectional_iterator that is not a std::bidirectional_iterator, that's a bug and we should fix it. (AFAIK, all our test iterators do satisfy the appropriate C++20 concepts.)

47

explicit (because all ctors should be explicit), or else remove (because the implicitly generated one seems OK enough).

55

Not to mention, passing "by const value" is typically a bug. I think const self& is meant (or, if it wasn't, it should have been). Also, since this test is C++20-only, how would we feel about a single friend std::strong_ordering operator<=>(const self&, const self&);? (Not defaulted, just in case that mattered.)

Personally I would not object to pass-by-value, e.g. replacing the current (or-should-be)

friend int operator-(const self&, const self&);

with

friend int operator-(self, self);

This wouldn't be as realistic, but it would reduce the amount of "stuff" to wade through.

76

I agree, but... Each "part being tested" touches a different line of the boilerplate. Do you have an idea of what kind of macro could help here?
My best offering is, what if you cut-and-pasted the exact same text N times and then simply added the characters // in order to comment out the one line you wanted to affect in each case. That would still have a lot of the same downsides, but at least it would be a tiny bit clearer what line(s) were intentionally missing, and it would make it easier for a human maintainer to verify that the test "correctly fails" when you comment-in any single one of those lines.

A very minor improvement would be to use the short names int*, int&, int instead of pointer, reference, difference_type, throughout. That reduces the amount of "stuff" the human eye has to wade through.

109

In fact, bidirectional! Right? (Ditto throughout.)

This revision now requires changes to proceed.Apr 28 2021, 12:15 PM
Mordante added inline comments.Apr 28 2021, 12:39 PM
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
32

To be clear I prefer to test them both. I only wonder why we should test static_assert(std::random_access_iterator<random_access_iterator<int*> >); but don't test static_assert( std::random_access_iterator<cxx20_random_access_iterator<int*> >);. If the cxx20 versions don't exists that would explain it.

76

If we remove the constructor the classes look the same until friend bool operator>=(const self, const self y);. (Look the same since it takes too much effort to validate.) So that could be put in a macro. Then at the interesting part of the class we could use your suggested comments. I think that would make the test easier to maintain.

zoecarver added inline comments.Apr 28 2021, 1:21 PM
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
76

What about just putting it into a base class, bidirectional_iterator?

zoecarver updated this revision to Diff 341328.Apr 28 2021, 3:11 PM
  • Apply review comments to random_access_iterator.compile.pass.cpp
zoecarver planned changes to this revision.Apr 28 2021, 3:13 PM

Looking at the list of files, we need to:

  • replace bidirectional_iterator with random_access_iterator for random-access iterators in all iterator_concept_conformance.compile.cpp
  • add a test for all the ranges that are not random_access_ranges (and similarly for any bidirectional_iterators that aren't random-access)

I'll work on that later today. I wanted to push my other changes first, though (so I could get feedback in the meantime).

Mordante added inline comments.Apr 29 2021, 9:44 AM
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
76

Sounds good to me, actually better than a macro.

  • Fix range concept conformance tests.
cjdb requested changes to this revision.Apr 30 2021, 6:00 PM

Please add the following tests:

  • subsumption for random_access_iterator
  • subsumption for random_access_range
  • iterator conformance tests
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
57

Please add a test for when iterator_concept = std::bidirectional_iterator_tag.

This revision now requires changes to proceed.Apr 30 2021, 6:00 PM
zoecarver updated this revision to Diff 342504.May 3 2021, 12:17 PM
  • Fix based on review.
zoecarver updated this revision to Diff 342507.May 3 2021, 12:23 PM
  • Remove msvc xfail.
  • Add range conformance tests.
cjdb accepted this revision.EditedMay 3 2021, 12:34 PM

LGTM, pending comments.

libcxx/test/libcxx/iterators/iterator.concepts/iterator.concept.random.access/subsumption.compile.pas.cpp
21 ↗(On Diff #342507)

Per offline discussion, please remove, and move to test/std/....

libcxx/test/std/ranges/range.refinements/random_access_range.compile.pass.cpp
37

Please also add cpp17_input_iterator wherever you check cpp20_input_iterator, for completeness' sake.

@cjdb I will make those changes locally so we don't further overwhelm the CI.

@Quuxplusone ping. This is now the bottom of the stack.

Quuxplusone added inline comments.May 3 2021, 3:43 PM
libcxx/test/libcxx/iterators/iterator.concepts/iterator.concept.random.access/subsumption.compile.pas.cpp
21 ↗(On Diff #342507)

Also, this file's name ends in .pas.cpp.
I sense another automated CI step in our future...

27 ↗(On Diff #342507)

Whatever else you're shuffling around here, please also remove the [[nodiscard]] cruft.

libcxx/test/std/containers/associative/multiset/iterator_concept_conformance.compile.pass.cpp
38

const_iterator (and please triple-check, throughout)

libcxx/test/std/containers/sequences/vector.bool/iterator_concept_conformance.compile.pass.cpp
26

For my own curiosity: I thought the new definition of forward_iterator was that its reference type needed to be value_type&. How does vector<bool>::iterator still manage to qualify as a random_access_iterator, then?
(This is presumably not a bug with this patch; I ask only for information.)

libcxx/test/std/containers/views/range_concept_conformance.compile.pass.cpp
20

Presumably in a separate PR, I'd like to see some tests for span<const int>.
(For consistency with the existing tests, I mean. This is not intended as my ringing endorsement of the current testing strategy. ;))

libcxx/test/std/containers/views/span.iterators/iterator_concept_conformance.compile.pass.cpp
24

It only now occurs to me that it would be useful to verify std::random_access_iterator<reverse_iterator> as well.

To keep the tests simple, I think you should add std::random_access_iterator<reverse_iterator> only on the containers that are in fact random-access. If !std::random_access_iterator<iterator>, then I think we can safely call it obvious that !std::random_access_iterator<reverse_iterator>.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
69

Bikeshed: I'd prefer to call this bidirectional_iterator_base... or random_access_base since its category is actually intentionally random_access_iterator_tag... or heck, just common_base!

Point is, it is not parallel to simple_random_access_iterator below, and its name should reflect that not-parallel-ness.

And, I mean, technically Parent should be named Child, but I get it. ;) I sometimes use the name Crtp for that parameter.

102

Throughout (from line 93 down): The blank lines on 93, 97, 101, 109, 113, 117,... don't seem semantically useful. I'd eliminate them.

libcxx/test/std/ranges/range.refinements/random_access_range.compile.pass.cpp
37

+1

libcxx/test/std/ranges/range.refinements/subsumption.compile.pass.cpp
76

This line is clearly intended to say random_access_iterator instead of random_access_range.

TODO: find a less error-prone way to write these tests. Right now we're just checking that this function isn't the best candidate, which is fairly obviously the case — even if it were viable. We should find a way to do this that doesn't quietly fall into a false negative when there's a problem with the cut-and-paste. (Or, handcraft these test cases more carefully.)

83

Throughout: Remove [[nodiscard]] cruft.

cjdb added inline comments.May 3 2021, 4:13 PM
libcxx/test/std/containers/sequences/vector.bool/iterator_concept_conformance.compile.pass.cpp
26

It's the other way around: Cpp17ForwardIterator demands a genuine reference, while forward_iterator just wants decltype(*i) to be something you can make into a reference (apparently void isn't the only thing you can't make into a reference?).

zoecarver updated this revision to Diff 342614.May 3 2021, 6:13 PM

Rebase off main to unblock Chris. No comments have been applied (yet).

zoecarver added inline comments.May 4 2021, 9:36 AM
libcxx/test/std/containers/views/span.iterators/iterator_concept_conformance.compile.pass.cpp
24

I think we decided as long as we're testing std::reverse_iterator it's ok not to test vector::reverse_iterator (and other reverse iterators that are known to be type aliases for std::reverse_iterator) because we know they're going to be the same.

Quuxplusone added inline comments.May 4 2021, 9:41 AM
libcxx/test/std/containers/views/span.iterators/iterator_concept_conformance.compile.pass.cpp
24

as long as we're testing std::reverse_iterator

Are you testing std::reverse_iterator<std::vector<int>::iterator>, though? Specifically I do think we should be testing std::reverse_iterator<std::vector<int>::iterator> (because it's a __wrap_iter) and std::reverse_iterator<std::vector<bool>::iterator> (because it's special). And personally I'd do it here, adding to the test for vector iterators (rather than, say, adding to the test for reverse_iterator).

zoecarver updated this revision to Diff 342783.May 4 2021, 9:53 AM
  • Apply review comments.
libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
102

At least for me, it's helpful to break things up in my mind. "These are the plus operators, these are the minus operators, this is the subscript." If they were all next to each other, it would be easy for something to get lost (and it's especially important not to let things get lost when the whole point of these objects is to remove one, specific method).

Also, not that this is a good reason on it's own, but this mimics how other iterators are defined (such as test::random_access_iterator).

libcxx/test/std/ranges/range.refinements/subsumption.compile.pass.cpp
76

:/

Unfortunately a lot of thought has gone into these tests. I'd 100% be open, if anyone has a better way to test them, though.

zoecarver updated this revision to Diff 342784.May 4 2021, 9:55 AM
  • Fix typo: tests now pass.
cjdb added inline comments.May 4 2021, 9:58 AM
libcxx/test/std/containers/views/span.iterators/iterator_concept_conformance.compile.pass.cpp
24

It only now occurs to me that it would be useful to verify std::random_access_iterator<reverse_iterator> as well.

To keep the tests simple, I think you should add std::random_access_iterator<reverse_iterator> only on the containers that are in fact random-access. If !std::random_access_iterator<iterator>, then I think we can safely call it obvious that !std::random_access_iterator<reverse_iterator>.

This should be in the reverse_iterator conformance test, and can probably be just reverse_iterator<reverse_iterator<int*>>. This opinion is neutral for addition, strongly in favour for placement.

As for __wrap_iter/vector<bool>::iterator, I'm not convinced that's necessary, since the conformance checks confirms reverse_iterator<some_random_access_iterator> is a random-access iterator. This opinion is weakly-against/borderline neutral for addition and strongly in agreement with Arthur for placement.

cjdb added inline comments.May 4 2021, 10:16 AM
libcxx/test/std/containers/views/span.iterators/iterator_concept_conformance.compile.pass.cpp
24

As for __wrap_iter/vector<bool>::iterator, I'm not convinced that's necessary, since the conformance checks confirms reverse_iterator<some_random_access_iterator> is a random-access iterator.

I didn't finish this thought. We confirm that vector::iterator is a random_access_iterator and we confirm that reverse_iterator plays well with a canonical random-access iterator, so I'm not convinced this is exploring anything new.

libcxx/test/std/containers/views/span.iterators/iterator_concept_conformance.compile.pass.cpp
24

It'd be exploring __wrap_iter specifically, but through a test that would be legal in test/std/. (Sometimes known as "whitebox testing": we'll be poking at the outside of the box, but in a way that we happen to know will exercise one specific implementation detail.)

Orthogonally to __wrap_iter, I still maintain that vector<bool>::iterator is not a canonical random-access iterator, and therefore testing reverse_iterator<random_access_iterator> does not really tell us whether reverse_iterator<vector<bool>::iterator> is going to work or not.

cjdb added inline comments.May 4 2021, 10:44 AM
libcxx/test/std/containers/views/span.iterators/iterator_concept_conformance.compile.pass.cpp
24

It'd be exploring __wrap_iter specifically, but through a test that would be legal in test/std/. (Sometimes known as "whitebox testing": we'll be poking at the outside of the box, but in a way that we happen to know will exercise one specific implementation detail.)

What new territory does reverse_iterator<__wrap_iter> explore that random_access_iterator<__wrap_iter> and random_access_iterator<reverse_iterator<int*>> doesn't already cover? I'm all for expanding coverage, but I'd very much like to understand what you're expanding to.

Orthogonally to __wrap_iter, I still maintain that vector<bool>::iterator is not a canonical random-access iterator, and therefore testing reverse_iterator<random_access_iterator> does not really tell us whether reverse_iterator<vector<bool>::iterator> is going to work or not.

You can believe this all you like, but the definition of iterators was revised specifically to let proxy iterators satisfy concepts stronger than input_iterator. As of C++20, vector<bool>::iterator is a random-access iterator. We confirm as much in libcxx/test/std/containers/sequences/vector.bool/iterator_concept_conformance.compile.pass.cpp. I'm not sure where you're drawing your objection from.

zoecarver updated this revision to Diff 342808.May 4 2021, 11:16 AM
  • Add the tests Arthur wanted (reverse iterator for vector, vector.bool).
ldionne accepted this revision.May 4 2021, 2:41 PM

Nit: We need to update the synopsis in <iterator>.

LGTM, ship this once you feel like you've addressed reviewer's comments sufficiently. I'm not seeing anything that is serious enough to block you once you've addressed what you think should be addressed, how you think it should.

libcxx/test/std/containers/sequences/deque/iterator_concept_conformance.compile.pass.cpp
26

I think this should go above the std::bidirectional_iterator check since we seem to be going from more specific to more general (from top to bottom) as far as the iterator concepts are concerned. This is really a nit though, feel free to skip if you disagree or if it's too tedious to change throughout.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.random.access/random_access_iterator.compile.pass.cpp
145

I really like this, makes it easy to see what's being tested.

cjdb added inline comments.May 4 2021, 3:56 PM
libcxx/test/std/containers/sequences/deque/iterator_concept_conformance.compile.pass.cpp
26

The bidirectional_iterator test should be removed (we're only keeping the top-most true concept and the bottom-most false concept for the conformance tests).

i.e., this will eventually be

static_assert(std::random_access_iterator<iterator>);
static_assert(!std::contiguous_iterator<iterator>);

Looks like this is the case in the range conformance tests, but not the iterator ones?

zoecarver updated this revision to Diff 342902.May 4 2021, 4:27 PM
  • Update synopsis.
  • Remove double positive tests for iterator concepts.
This revision was not accepted when it landed; it landed in state Needs Review.May 4 2021, 9:43 PM
This revision was automatically updated to reflect the committed changes.