Page MenuHomePhabricator

[libc++][ranges] Implement changes to reverse_iterator from One Ranges Proposal.

Authored by var-const on Feb 19 2022, 1:19 AM.



Changes in P0896:

  • add disable_sized_sentinel_for;
  • add iter_move and iter_swap;
  • add a requires clause to the operator->;
  • add iterator_concept;
  • check that the Iterator template parameter is a bidirectional iterator;
  • add constraints to all comparison operators;
  • change the definitions of iterator_category, value_type, difference_type and reference (changes to iterator_category were already implemented).

Also add a few forgotten things to the reverse_iterator synopsis
(notably the spaceship operator).

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
var-const marked 10 inline comments as done.Feb 28 2022, 4:45 AM

Address feedback


I think it would only make sense to remove the comment if it were obvious from a glance. I find the situation not obvious -- somewhat confusing, actually -- so personally I find the comment helpful. If you have any other suggestions on how to improve the wording, please let me know.


I think both are workable, so I'm ok with removing the static_assert, but I still feel that saying why it doesn't compile is more useful than saying what doesn't compile.

sadly gives the programmer no information about how to fix the problem with their code

It leads the programmer in the right direction -- they can look up the bidirectional_iterator requirements or just do static_assert(std::bidirectional_iterator<MySupposedlyBidirectionalIterator>) to see what exactly is missing from their type (which might be more than just the operator--).


Done, thanks! (I've had to provide definitions for some of the unimportant functions -- otherwise I'm getting errors like

function 'main(int, char **)::It::operator*' has internal linkage but is not defined [-Werror,-Wundefined-internal]



FWIW, I prefer the opposite -- I find it easier when for each subexpression, the operand is right in front of it so I don't have to scan the previous lines (of varying length) to find it. It also makes it easier to insert lines or move them around because this way, they are more "self-contained".


Moved the tests into a new file.

add another test for a type R such that essentially-random_access_iterator<R> && disable_sized_sentinel_for<R, R>, and make sure that requires { reverse_iterator<R>() - reverse_iterator<R>(); } == false.

I'm probably missing something, but reverse_iterator::operator- doesn't check for sized_sentinel_for directly, instead relying on whether operator- is defined for the underlying iterators. It seems like this test would check the behavior of the underlying iterators.


Renamed to {,un}sized_it (but personally I think that trying to avoid line breaks isn't really worth it).


My intention was to check the constraints section of these operators ("Constraints: x.base() <= y.base() is well-formed and convertible to bool"). operator<=> has no constraints section -- unless it should be inferred implicitly somehow?

By the way -- do you think it's worthwhile checking the return type as well? Basically, run all the same checks if the return type is ConvertibleToBool or NotConvertibleToBool? It seems like overkill, but happy to add the tests if you think it's worth testing.

var-const updated this revision to Diff 411792.Feb 28 2022, 4:48 AM

Clarify comment.


easier to insert lines or move them around

It occurs to me that I'd definitely break std::cout << "x" << "y" between "x" and << "y" (although in that case I'd also insert a new ; std::cout so that the statement didn't need to span lines in the first place).
For other operations like x && y or x + y, which don't tend to be chained extensively or ever have new operands inserted in the middle, [insert what I said before].
Btw, I'm a big fan of "trailing comma" in enum definitions and array initializers, and I wish a trailing comma were syntactically allowed everywhere (e.g. function parameter lists, member-initializer-lists).

enum E {

There we get the best of both worlds IMO: the comma gets to stay at the end of the line and we can easily insert new lines in the middle or at the end.


I don't think you ever use the fact that adl::Iterator is a template. Please remove the templateness.


No big deal; but I prefer the shorter code with fewer identifiers on my mental "stack". Otherwise I'm looking and waiting for the place where N will be used, and it never comes.

Ditto throughout.


I suggest removing lines 89-93. We don't need to test operator++ here.


What's the -- doing here and on lines 115 and 159? You can remove it, right?, actually, I guess the long names confused me. This line isn't testing anything about reverse_iterator, but merely about the underlying iterator type NoexceptCopyThrowingMove (which I would just call It in each case).
So lines 136-137 are just testing the setup, and then line 139 is the important line.
Personally I'd still remove lines 136-137, because line 139 is clear enough: we're testing that iter_move is noexcept iff its dependencies are noexcept.

IOW, I'd make this

  struct It {
    using value_type = int;
    using difference_type = ptrdiff_t;
    explicit It() noexcept;
    It(const It&) noexcept;
    int& operator*() const;  // if you need to define a body here, OK
    It& operator++() noexcept;
    It operator++(int) noexcept;
    It& operator--() noexcept;
    It operator--(int) noexcept;
  std::reverse_iterator<It> ri;
  ASSERT_NOT_NOEXCEPT(iter_move(ri));  // because operator*

Oh hey, in replacing the name NoexceptCopyThrowingMove with It, I discovered that the old name was wrong! Type It has no move-ctor at all, much less a throwing one. The non-noexcept operations on lines 121-139 were operator* and operator-- (I assume one or the other was accidental). So the type could have been named NoexceptCopyThrowingDeref or something like that... but fortunately now I don't have to come up with a name for it, because It is fine and good. :)


Ditto here: I don't think you use the fact that adl::Iterator is a template.


You know I'm never thrilled by tests that customize bits of types they don't own. Consider defining struct FooIter as its own type.


Is the purpose of this test just to make sure that reverse_iterator<BarIter> takes its difference_type from iterator_traits<BarIter>::difference_type and not from BarIter::difference_type directly? ...But wait, BarIter::difference_type doesn't exist! And it wouldn't exist for an iterator type like int*, either. So I actually don't think this test is adding any coverage, and therefore would prefer to remove it. Unless I'm missing something.

Which I must be, because how on earth do we end up with is_same_v<typename std::reverse_iterator<BarIter>::reference, bool&> on line 112??

var-const updated this revision to Diff 412959.Mar 4 2022, 2:12 AM
var-const marked 8 inline comments as done.

Address review feedback.

Herald added a project: Restricted Project. · View Herald TranscriptMar 4 2022, 2:12 AM
var-const added inline comments.Mar 4 2022, 2:12 AM

(I made the change, by the way)

I see your point, but I still find it easier to have a single rule that covers everything.


Unless you feel strongly, I'd rather keep as is. For me, the constant a) underscores that the exact value is unimportant; b) makes it obvious that this is the length of the array, as opposed to some arbitrary index within the array; c) prevents me from having to keep track whether the number is the same throughout the scope (with a constant, there would be a compiler error if it's mistyped).


What's the -- doing here and on lines 115 and 159?

I'm emulating how the noexcept specification is defined in iter_move:

noexcept(is_nothrow_copy_constructible_v<_Iter> &&

I discovered that the old name was wrong! Type It has no move-ctor at all, much less a throwing one.

You're right, thanks a lot for noticing this -- this is a mistake on my part. The name should replace Move with Decrement.

I think, however, that this is evidence in favor of keeping both the verbose (but descriptive) names and verifying the properties of the dependencies. Together, they add a certain redundancy (in the information-theory sense) that makes it easier to recover from mistakes. Imagine, for the sake of the argument, that it was the class implementation that was wrong (possibly due to copy-pasting), not the name. It would be much more difficult to notice with a name like It. When the name, the implementation and checking the properties reinforce each other, it's easier to see what exactly is being tested and whether it works like expected.


I understand your concern, but I strongly dislike increasing the amount of boilerplate. I would agree if this were a more "arbitrary" type, but our test iterators have well-defined semantics and quite a few dependencies, so it seems reasonable to rely on this class being there and not changing radically. So I'd rather keep as is, unless you feel strongly about it.


Is the purpose of this test just to make sure that reverse_iterator<BarIter> takes its difference_type from iterator_traits<BarIter>::difference_type..?

BarIter is only for testing reference (to make sure it's implemented correctly both pre- and post-C++20). difference_type is tested via FooIter.

how on earth do we end up with is_same_v<typename std::reverse_iterator<BarIter>::reference, bool&> on line 112?

Pre-C++20, reference would be defined as iterator_traits<I>::reference, so it's taken from the specialization of iterator_traits. In C++20+, reference is iter_reference_t, which is defined as decltype(*declval<T&>());. So the type is taken from the return type of BarIter::operator*() (see line 82).

I'm inclined to green-light this at this point. I haven't given it the fine-tooth-comb treatment this time, but it's been through enough rounds of review and I assume nothing that we covered earlier has regressed lately. However:

  • CI is red for apparently multiple reasons; please make sure it becomes green.
  • I'd like a second libc++ reviewer to take a look too.

Happy to take another look if anything major comes up in the second person's review.


Close. I'd definitely move iterator_concept down to coalesce those two _LIBCPP_STD_VER > 17 blocks together. I'd also either duplicate the iterator_category and pointer lines, or move them up next to iterator_type, to keep the non-ifdef'ed stuff in a block together.


I finally notice your slight modification, and I'm not thrilled by it. Let's not break apart

pointer operator->() const

from the function's curly-braced body just to save two lines of duplication. We generally try (and everyone should generally try ;)) to put preprocessor conditionals only around "sensible" units of code — like, (an extreme example,) prefer

#if X
    return x+1;
    return x;


    return x
#if X

Btw, the difference between

noexcept(ranges::iter_swap(--declval<_Iter&>(), --declval<_Iter2&>()))


noexcept(ranges::iter_swap(--__x, --__y))

is subtle. Do you have a test that will fail if someone makes that substitution? (If not, please add one.)

39 ↗(On Diff #412959)

This is the only diff in this test file; consider reverting it.


I don't know if they're supposed to work in C++20, but in practice, compilers don't like non-dependent requires clauses. You'll have to rewrite this kind of thing as

template<class T> concept HasMinus = requires (T t) { t - t; };


which is honestly easier on the eyes anyway. :)

Circa line 20 above, you should also assert that HasMinus<std::reverse_iterator<sized_it>> (even though I guess it's obvious... well, just for symmetry, let's assert it anyway).


Btw, I believe my confusion at first was due mainly to thinking FooIter and BarIter were the same type (i.e. I misread Bar as Foo or vice versa). I see where bool comes from, now.

It strikes me that FooIter is just plain old bidirectional_iterator — er, kinda sorta — whenever it is not true that TEST_STD_VER > 17. So really, FooIter is a "C++20-only test case"; you dutifully assert things about it when <= 17, but those things aren't really interesting things, because half of the type is missing. I think the entire definition of FooIter should be guarded by TEST_STD_VER > 17.

As I type that comment (specifically the "kinda sorta" part), I recall why inheriting from test iterators is a bad idea: you'll find that std::bidirectional_iterator<FooIter> == false, am I right? In fact FooIter isn't any kind of iterator in C++20, right? This doesn't render the test UB, but it does mean that you're not actually saving too much boilerplate here — you can omit all the iterator boilerplate! I bet you don't need much more than

#if TEST_STD_VER > 17
struct FooIter {
    using value_type = void*;
    using difference_type = void*;
template <>
struct std::indirectly_readable_traits<FooIter> {
  using value_type = int;
template <>
struct std::incrementable_traits<FooIter> {
  using difference_type = char;

static_assert(std::is_same_v<typename std::reverse_iterator<FooIter>::value_type, int>);
static_assert(std::is_same_v<typename std::reverse_iterator<FooIter>::difference_type, char>);
#endif // TEST_STD_VER > 17

The BarIter test should remain enabled for all C++ versions, i.e. something like

struct BarIter {
  bool& operator*() const;
template <>
struct std::iterator_traits<BarIter> {
  using difference_type = char;
  using value_type = char;
  using pointer = char*;
  using reference = char&;
  using iterator_category = std::bidirectional_iterator_tag;

#if TEST_STD_VER > 17
static_assert(std::is_same_v<typename std::reverse_iterator<BarIter>::reference, bool&>);
static_assert(std::is_same_v<typename std::reverse_iterator<BarIter>::reference, char&>);
var-const updated this revision to Diff 414018.Mar 8 2022, 11:10 PM
var-const marked 6 inline comments as done.
  • address feedback;
  • fix CI;
  • rebase on main;
  • fix names of the helper structs in iter_swap.pass.cpp.

Done (moved up the common lines to avoid duplication).


Ok, I reverted to your original version with another slight modification -- duplicated _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 between the two clauses as well (which seems to be consistent with your comment -- I think you originally omitted it for brevity, right?).


Hmm, but __x and __y are const references, so calling -- on them should be invalid, or at least unreasonable? Also, trying to make the change as-is (without adding a new test), I get:

In file included from libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.nonmember/iter_swap.pass.cpp:20:
In file included from build/include/c++/v1/iterator:642:
In file included from build/include/c++/v1/__iterator/common_iterator.h:18:
build/include/c++/v1/__iterator/iter_swap.h:41:7: error: exception specification of 'iter_swap<int *>' uses itself
      iter_swap(_VSTD::forward<_T1>(__x), _VSTD::forward<_T2>(__y));
build/include/c++/v1/__iterator/iter_swap.h:41:7: note: in instantiation of exception specification for 'iter_swap<int *>' requested here
build/include/c++/v1/__iterator/iter_swap.h:41:7: note: in instantiation of requirement here
      iter_swap(_VSTD::forward<_T1>(__x), _VSTD::forward<_T2>(__y));
build/include/c++/v1/__iterator/iter_swap.h:40:5: note: while substituting template arguments into constraint expression here
    requires (_T1&& __x, _T2&& __y) {
build/include/c++/v1/__iterator/iter_swap.h:51:16: note: while checking the satisfaction of concept '__unqualified_iter_swap<const std::reverse_iterator<int *> &, const std::reverse_iterator<int *> &>' requested here
      requires __unqualified_iter_swap<_T1, _T2>
build/include/c++/v1/__iterator/iter_swap.h:51:16: note: while substituting template arguments into constraint expression here
      requires __unqualified_iter_swap<_T1, _T2>
build/include/c++/v1/__iterator/reverse_iterator.h:190:20: note: while checking constraint satisfaction for template 'operator()<const std::reverse_iterator<int *> &, const std::reverse_iterator<int *> &>' required here
          noexcept(ranges::iter_swap(__x, __y))) {
build/include/c++/v1/__iterator/reverse_iterator.h:190:20: note: in instantiation of function template specialization 'std::ranges::__iter_swap::__fn::operator()<const std::reverse_iterator<int *> &, const std::reverse_it
erator<int *> &>' requested here
libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.nonmember/iter_swap.pass.cpp:76:41: note: in instantiation of exception specification for 'iter_swap<int *>' requested here
    static_assert(std::same_as<decltype(iter_swap(rb, re)), void>);

Do you think it's worth digging further, given this?



I still need to define the classic 5 types because reverse_iterator inherits from iterator_traits (evidently _LIBCPP_ABI_NO_ITERATOR_BASES is false when running tests, in my environment at least). And operator* for good measure (because of how reference is defined).

I think the issue with inheritance that you mention can be solved via CRTP.

@Quuxplusone Thanks a lot for a very thorough review! I really appreciate all the feedback.

ldionne requested changes to this revision.Mar 10 2022, 7:47 AM

Looks really good, thanks! I have some comments so I'm requesting changes, but there's nothing major.


I have to say -- I think the static_assert approach is superior for a couple of reasons (in no order):

  • Instantiating reverse_iterator with a non-bidi iterator is a precondition type of error, per What we normally do for these errors is assert, or static_assert when detectable at compile-time. So there's a consistency argument.
  • A static_assert firing makes it clear that the user messed up. When a user sees a static_assert with a message we bothered writing for them, they immediately go "oh, I must have messed up", which provides a nicer experience than letting them scratch their head over "why is this code not compiling".
  • We have a message we can use to make it arbitrarily clear what's going wrong. We shouldn't be shy to explain the issue properly so as to make the static_assert undoubtedly easier to understand than the compilation error.
  • Without a static_assert, it's possible that some users would try to fix their code by just adding the missing operator to their iterator type, without necessarily making it a proper bidirectional iterator. So they'd still be in IFNDR-land, when we could instead have helped them understand the problem and fix their code.
  • It is generally better to fail earlier rather than later. For example, we don't want users to use reverse_iterator<non-bidi> successfully until they finally try to use operator++ on it, which would start failing. For instance, without the assertion, I think users could use reverse_iterator<non-bidi> successfully if they only used operator--, right? If so, that's not a good thing.

By the way, the above applies to anywhere in the library where we have ill-formed code that we're able to diagnose. If we agree on this, we can take it as a blanket policy to prefer static_assert over "lazy instantiation errors" when we have those cases.

So, all that being said, my vote would go for adding a static_assert with a nice error message, and adding a libc++ specific test to check that we do catch it.


The intent of this change is so that a reverse_iterator<contiguous-iterator> advertises itself as a random_access_iterator, not a contiguous_iterator. Right?


This can be made unconditionally constexpr now.


You should be able to replace all instances of _LIBCPP_HAS_NO_CONCEPTS by _LIBCPP_STD_VER > 17 now that we've bumped the compilers.

For this specific instance, it means it can be eliminated altogether.


Any reason for not using verbatim what's in the standard, i.e. prev(current)?


Suggestion: land these NFCs in a separate commit, no need to review or anything. That'll clean up this diff.


Is there a reason why this isn't in a constexpr function and then called as test(); static_assert(test(), ""); so that we test it both at runtime and at compile-time?


Thanks for being diligent on testing even the noexcept clauses. I'm glad this is the standard we hold ourselves to, even though I know those tests are tedious to write.


The same question/comment about constexpr testing applies here too.


Suggestion: move this test to a .compile.pass.cpp test and rename main to something else to remove the impression that we're running anything.

This revision now requires changes to proceed.Mar 10 2022, 7:47 AM
var-const edited the summary of this revision. (Show Details)Mar 10 2022, 6:01 PM
var-const updated this revision to Diff 414537.Mar 10 2022, 6:01 PM
var-const marked 9 inline comments as done.

Address feedback.

var-const added inline comments.Mar 10 2022, 6:10 PM

Restored the static_assertion and its test (bad_template_argument.verify.cpp in libcxx tests). Please let me know if you'd like to expand the error message.

One thing to mention, though -- the Standard's constraints are:

The template parameter Iterator shall either meet the requirements of a Cpp17BidirectionalIterator ([bidirectional.iterators]) or model bidirectional_­iterator ([iterator.concept.bidir]).

I presumed that __is_cpp17_bidirectional_iterator implements Cpp17BidirectionalIterator. However, it seems significantly more lax -- if I'm reading the implementation correctly, it only checks the iterator_category, not the provided operations. So the current check is significantly weaker than it should be -- any type providing the expected iterator_category and the other 3-4 typedefs would do. Do you think I should fix this in this patch or a follow-up? Or perhaps create a local version of __is_cpp17_bidirectional_iterator in this file?

For instance, without the assertion, I think users could use reverse_iterator<non-bidi> successfully if they only used operator--, right? If so, that's not a good thing.

I tried it out to verify, and yes, functions like operator-- and base do work if there is no static_assertion.


I think so (it definitely has this effect), but I would have to do some archaeology to find out if that was the main intention (the One Ranges Proposal omits any rationale). Please let me know if you'd like me to confirm.


That's really cool, done.


I don't think there was a particularly strong reason. Changed to the Standard version.


FWIW, I still strongly disagree with this direction, on principle; but will defer to @ldionne.

Without a static_assert, [...] just adding the missing operator to their iterator [...] they'd still be in IFNDR-land

True, if your goal is to keep people out of IFNDR-land entirely, then the static_assert is the right answer. I still think that for anything in "STL Classic", outside of namespace ranges, it would be better to keep the "Classic" wild-west template semantics so as to avoid breaking code unnecessarily... Basically, I like IFNDR-land. :)

the current check is significantly weaker than it should be

FWIW IMHO, it's not worth creating a local version of anything for just this file; either strengthen __is_cpp17_bidirectional_iterator or do nothing. But if strengthening __is_cpp17_bidirectional_iterator, I'd again caution to avoid breaking existing code if possible. (Or at least avoid breaking it without good reason. For @ldionne, "staying out of IFNDR-land" might count as a good reason. For me it wouldn't. So that's why we end up on different sides of this issue.)

Notice that your new tests are solidly in IFNDR-land right now; Ctrl+F down for where you said "__is_cpp17_bidirectional_iterator is pretty lax." Are you volunteering yourself to clean up that test code now? ;)


I'd explain it as: We know a reverse_iterator is always at least a bidirectional iterator. But if the _Iter type is random-access, then our reverse_iterator should also be random-access!

Your explanation adds: ''...But if the _Iter type is contiguous, then... nothing special. Just leave the reverse_iterator as random-access in that case." Which is absolutely correct, but it's kind of the boring part of the explanation, IMHO. ;)


@var-const: AFAIK, this should be std::prev, not ranges::prev. Please use std::prev. I'm not sure the difference is detectable, but if you can think of some way it is detectable then please add a regression test too.


Do you think it's worth digging further, given this?

For the record, no, that's fine. :)

22–23 ↗(On Diff #410075)

Aha, see libcxx/utils/libcxx/test/

FOO.verify.cpp          - Compiles with clang-verify. This type of test is
                          automatically marked as UNSUPPORTED if the compiler
                          does not support Clang-verify.            - Compiled with clang-verify if clang-verify is
                          supported, and equivalent to a
                          test otherwise. This is supported only for backwards
                          compatibility with the test suite.

So, there's no difference, but for consistency please rename to .verify.cpp.


operator<=> has no constraints section -- unless it should be inferred implicitly somehow?

It has a requires-clause which expresses the same constraints. (A requires-clause makes it a constrained template, i.e., a template with constraints. :) The Standard just doesn't need to say the constraints in English because they're already said in code.)

run all the same checks if the return type is ConvertibleToBool or NotConvertibleToBool?

Hmm, so it would be something like this instead?

struct B { explicit operator bool() const; };
struct NB { };

template<int Version>
struct NoEqualityCompIter : IterBase {
  NB operator==(NoEqualityCompIter) const requires (Version == 1);
  B operator!=(NoEqualityCompIter) const;
  B operator<(NoEqualityCompIter) const;
  B operator>(NoEqualityCompIter) const;
  B operator<=(NoEqualityCompIter) const;
  B operator>=(NoEqualityCompIter) const;

static_assert( HasEqual<std::reverse_iterator<int*>>);
static_assert( HasNotEqual<std::reverse_iterator<NoEqualityCompIter<1>>>);
static_assert( HasLess<std::reverse_iterator<NoEqualityCompIter<1>>>);
static_assert( HasLessOrEqual<std::reverse_iterator<NoEqualityCompIter<1>>>);
static_assert( HasGreater<std::reverse_iterator<NoEqualityCompIter<1>>>);
static_assert( HasNotEqual<std::reverse_iterator<NoEqualityCompIter<2>>>);
static_assert( HasLess<std::reverse_iterator<NoEqualityCompIter<2>>>);
static_assert( HasLessOrEqual<std::reverse_iterator<NoEqualityCompIter<2>>>);
static_assert( HasGreater<std::reverse_iterator<NoEqualityCompIter<2>>>);

That's not terrible but also not thrilling. I'm weakly against, but will leave it up to you and/or whoever has a stronger opinion.


This metaprogramming was a yellow flag for me, especially after all our discussion about lax iterator requirements for legacy iterators. Could you take a look at this Godbolt and see if you agree that it's conforming C++ (i.e. It does literally satisfy the legacy requirements so we're not in IFNDR-land)? Does this PR make us pass this test case? Could you make sure this is tested somewhere?

var-const updated this revision to Diff 415565.Mar 15 2022, 1:42 PM
var-const marked 7 inline comments as done.

Address feedback.


Notice that your new tests are solidly in IFNDR-land right now

Strengthening the requirement by removing the __is_cpp17_bidirectional_iterator part (so that it's just bidirectional_iterator), only 4 tests fail out of 36. I think the cleanup shouldn't be too time consuming if it becomes necessary.


Added some tests for operator<=>.


It doesn't satisfy the requirement that the iterator given to reverse_iterator is at least a bidirectional iterator.

ldionne accepted this revision.Mar 15 2022, 2:25 PM

Thanks! LGTM with rewording suggestion for diagnostic.


I'd prefer something like reverse_iterator<It> requires It to be a bidirectional iterator.

This revision is now accepted and ready to land.Mar 15 2022, 2:25 PM
var-const updated this revision to Diff 416358.Mar 17 2022, 4:38 PM
  • Address feedback;
  • rebase on main and fix the operator-> SFINAE test now that test_iterators.h types don't provide operator->.