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

[zoecarver]

libcxx/include/__iterator/concepts.h

150

Will be removed when rebased.

[zoecarver]

• Fix comment.

[cjdb]

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?

[Mordante]

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]

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.)

[Mordante]

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]

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]

• Apply review comments to random_access_iterator.compile.pass.cpp

[zoecarver]

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]

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.

[zoecarver]

• Fix range concept conformance tests.

[cjdb]

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.

[zoecarver]

• Fix based on review.

[zoecarver]

• Remove msvc xfail.
• Add range conformance tests.

[cjdb]

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.

[zoecarver]

@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]

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]

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]

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

[zoecarver]

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]

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]

• 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]

• Fix typo: tests now pass.

[cjdb]

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]

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.

[• Quuxplusone]

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]

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]

• Add the tests Arthur wanted (reverse iterator for vector, vector.bool).

[ldionne]

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

146

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

[cjdb]

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]

• Update synopsis.
• Remove double positive tests for iterator concepts.

libcxx/include/__iterator/concepts.h

 concept bidirectional_iterator =
   forward_iterator<_Ip> &&
   derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> &&
   requires(_Ip __i) {
     { --__i } -> same_as<_Ip&>;
     { __i-- } -> same_as<_Ip>;
   };
 
-  // clang-format on
+template<class _Ip>
+concept random_access_iterator =
+  bidirectional_iterator<_Ip> &&
+  derived_from<_ITER_CONCEPT<_Ip>, random_access_iterator_tag> &&
+  totally_ordered<_Ip> &&
+  sized_sentinel_for<_Ip, _Ip> &&
+  requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
+    { __i += __n } -> same_as<_Ip&>;
+    { __j +  __n } -> same_as<_Ip>;
+    { __n +  __j } -> same_as<_Ip>;
+    { __i -= __n } -> same_as<_Ip&>;
+    { __j -  __n } -> same_as<_Ip>;
+    {  __j[__n]  } -> same_as<iter_reference_t<_Ip>>;
+  };
+
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ITERATOR_CONCEPTS_H

libcxx/include/__ranges/concepts.h

namespace ranges {
   template <class _Tp>
   concept forward_range = input_range<_Tp> && forward_iterator<iterator_t<_Tp> >;
 
   template <class _Tp>
   concept bidirectional_range = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp> >;
 
   template <class _Tp>
   concept common_range = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp> >;
+
+  template <class _Tp>
+  concept random_access_range =
+      bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp> >;
 } // namespace ranges
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 // clang-format on
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_RANGES_CONCEPTS_H

libcxx/include/iterator

 // [iterator.concept.forward], concept forward_iterator
 template<class I>
   concept forward_iterator = see below;                    // since C++20
 
 // [iterator.concept.bidir], concept bidirectional_iterator
 template<class I>
   concept bidirectional_iterator = see below;              // since C++20
 
+// [iterator.concept.random.access], concept random_access_iterator
+template<class I>
+  concept random_access_iterator = see below;              // since C++20
+
 template<class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
 struct iterator
 {
     typedef T         value_type;
     typedef Distance  difference_type;
     typedef Pointer   pointer;
     typedef Reference reference;

libcxx/test/libcxx/iterators/iterator.concepts/iterator.concept.random.access/subsumption.compile.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14, c++17
 // UNSUPPORTED: libcpp-no-concepts
 // UNSUPPORTED: gcc-10
 
 // template<class T>
-// concept bidirectional_iterator;
+// concept random_access_iterator;
 
 #include <iterator>
 
 #include <concepts>
 
-template<std::forward_iterator I>
-[[nodiscard]] constexpr bool check_subsumption() {
+template<std::bidirectional_iterator I>
+requires std::derived_from<std::_ITER_CONCEPT<I>, std::random_access_iterator_tag>
+constexpr bool check_subsumption() {
   return false;
 }
 
-template<std::bidirectional_iterator>
-[[nodiscard]] constexpr bool check_subsumption() {
+template<std::random_access_iterator>
+constexpr bool check_subsumption() {
   return true;
 }
 
 static_assert(check_subsumption<int*>());

libcxx/test/std/containers/associative/map/iterator_concept_conformance.compile.pass.cpp

 
 using iterator = std::map<int, int>::iterator;
 using const_iterator = std::map<int, int>::const_iterator;
 using reverse_iterator = std::map<int, int>::reverse_iterator;
 using const_reverse_iterator = std::map<int, int>::const_reverse_iterator;
 using value_type = std::pair<const int, int>;
 
 static_assert(std::bidirectional_iterator<iterator>);
+static_assert(!std::random_access_iterator<iterator>);
 static_assert(!std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
 static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(!std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/containers/associative/map/range_concept_conformance.compile.pass.cpp

 #include <ranges>
 
 using range = std::map<int, int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::bidirectional_range<range>);
+static_assert(!stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::bidirectional_range<range const>);
+static_assert(!stdr::random_access_range<range const>);

libcxx/test/std/containers/associative/multimap/iterator_concept_conformance.compile.pass.cpp

 
 using iterator = std::multimap<int, int>::iterator;
 using const_iterator = std::multimap<int, int>::const_iterator;
 using reverse_iterator = std::multimap<int, int>::reverse_iterator;
 using const_reverse_iterator = std::multimap<int, int>::const_reverse_iterator;
 using value_type = std::pair<const int, int>;
 
 static_assert(std::bidirectional_iterator<iterator>);
+static_assert(!std::random_access_iterator<iterator>);
 static_assert(!std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
 static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(!std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/containers/associative/multimap/range_concept_conformance.compile.pass.cpp

 #include <ranges>
 
 using range = std::multimap<int, int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::bidirectional_range<range>);
+static_assert(!stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::bidirectional_range<range const>);
+static_assert(!stdr::random_access_range<range const>);

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

 
 using iterator = std::multiset<int>::iterator;
 using const_iterator = std::multiset<int>::const_iterator;
 using reverse_iterator = std::multiset<int>::reverse_iterator;
 using const_reverse_iterator = std::multiset<int>::const_reverse_iterator;
 using value_type = int;
 
 static_assert(std::bidirectional_iterator<iterator>);
+static_assert(!std::random_access_iterator<iterator>);
 static_assert(!std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
 static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(!std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/containers/associative/multiset/range_concept_conformance.compile.pass.cpp

 #include <ranges>
 
 using range = std::multiset<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::bidirectional_range<range>);
+static_assert(!stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::bidirectional_range<range const>);
+static_assert(!stdr::random_access_range<range const>);

libcxx/test/std/containers/associative/set/iterator_concept_conformance.compile.pass.cpp

 
 using iterator = std::set<int>::iterator;
 using const_iterator = std::set<int>::const_iterator;
 using reverse_iterator = std::set<int>::reverse_iterator;
 using const_reverse_iterator = std::set<int>::const_reverse_iterator;
 using value_type = int;
 
 static_assert(std::bidirectional_iterator<iterator>);
+static_assert(!std::random_access_iterator<iterator>);
 static_assert(!std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
 static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(!std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/containers/associative/set/range_concept_conformance.compile.pass.cpp

 
 #include <concepts>
 #include <ranges>
 
 using range = std::set<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
+static_assert(stdr::bidirectional_range<range>);
+static_assert(!stdr::random_access_range<range>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::input_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
+static_assert(stdr::bidirectional_range<range const>);
+static_assert(!stdr::random_access_range<range const>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::input_range<range>);

libcxx/test/std/containers/sequences/array/iterator_concept_conformance.compile.pass.cpp

 
 #include <iterator>
 
 using iterator = std::array<int, 10>::iterator;
 using const_iterator = std::array<int, 10>::const_iterator;
 using reverse_iterator = std::array<int, 10>::reverse_iterator;
 using const_reverse_iterator = std::array<int, 10>::const_reverse_iterator;
 
-static_assert(std::bidirectional_iterator<iterator>);
+static_assert(std::random_access_iterator<iterator>);
 static_assert(std::indirectly_writable<iterator, int>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<iterator, iterator>);
 static_assert(std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
-static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, int>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/containers/sequences/array/range_concept_conformance.compile.pass.cpp

 #include <concepts>
 #include <ranges>
 
 using range = std::array<int, 10>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
-static_assert(stdr::bidirectional_range<range>);
+static_assert(stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
-static_assert(stdr::bidirectional_range<range const>);
+static_assert(stdr::random_access_range<range const>);

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

 #include <iterator>
 
 using iterator = std::deque<int>::iterator;
 using const_iterator = std::deque<int>::const_iterator;
 using reverse_iterator = std::deque<int>::reverse_iterator;
 using const_reverse_iterator = std::deque<int>::const_reverse_iterator;
 using value_type = int;
 
-static_assert(std::bidirectional_iterator<iterator>);
+static_assert(std::random_access_iterator<iterator>);
 static_assert(std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<iterator, iterator>);
 static_assert(std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
-static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/containers/sequences/deque/range_concept_conformance.compile.pass.cpp

 #include <concepts>
 #include <ranges>
 
 using range = std::deque<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
-static_assert(stdr::bidirectional_range<range>);
+static_assert(stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
-static_assert(stdr::bidirectional_range<range const>);
+static_assert(stdr::random_access_range<range const>);

libcxx/test/std/containers/sequences/list/iterator_concept_conformance.compile.pass.cpp

 
 using iterator = std::list<int>::iterator;
 using const_iterator = std::list<int>::const_iterator;
 using reverse_iterator = std::list<int>::reverse_iterator;
 using const_reverse_iterator = std::list<int>::const_reverse_iterator;
 using value_type = int;
 
 static_assert(std::bidirectional_iterator<iterator>);
+static_assert(!std::random_access_iterator<iterator>);
 static_assert(std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
 static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(!std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

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

 #include <ranges>
 
 using range = std::list<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
 static_assert(stdr::bidirectional_range<range>);
+static_assert(!stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
 static_assert(stdr::bidirectional_range<range const>);
+static_assert(!stdr::random_access_range<range const>);

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

 #include <iterator>
 
 using iterator = std::vector<bool>::iterator;
 using const_iterator = std::vector<bool>::const_iterator;
 using reverse_iterator = std::vector<bool>::reverse_iterator;
 using const_reverse_iterator = std::vector<bool>::const_reverse_iterator;
 using value_type = bool;
 
-static_assert(std::bidirectional_iterator<iterator>);
+static_assert(std::random_access_iterator<iterator>);
+static_assert(std::random_access_iterator<reverse_iterator>);
 static_assert(!std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<iterator, iterator>);
 static_assert(std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
-static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_reverse_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

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

 #include <concepts>
 #include <ranges>
 
 using range = std::vector<bool>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
-static_assert(stdr::bidirectional_range<range>);
+static_assert(stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
-static_assert(stdr::bidirectional_range<range const>);
+static_assert(stdr::random_access_range<range const>);

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

 #include <iterator>
 
 using iterator = std::vector<int>::iterator;
 using const_iterator = std::vector<int>::const_iterator;
 using reverse_iterator = std::vector<int>::reverse_iterator;
 using const_reverse_iterator = std::vector<int>::const_reverse_iterator;
 using value_type = int;
 
-static_assert(std::bidirectional_iterator<iterator>);
+static_assert(std::random_access_iterator<iterator>);
+static_assert(std::random_access_iterator<reverse_iterator>);
 static_assert(std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<iterator, iterator>);
 static_assert(std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
-static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_reverse_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/containers/sequences/vector/range_concept_conformance.compile.pass.cpp

 #include <concepts>
 #include <ranges>
 
 using range = std::vector<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
-static_assert(stdr::bidirectional_range<range>);
+static_assert(stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::const_iterator>);
 static_assert(stdr::common_range<range const>);
-static_assert(stdr::bidirectional_range<range const>);
+static_assert(stdr::random_access_range<range const>);

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

 
 // span
 
 #include <span>
 
 #include <concepts>
 #include <ranges>
 
 using range = std::span<int>;
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<range>, range::iterator>);
 static_assert(stdr::common_range<range>);
-static_assert(stdr::bidirectional_range<range>);
+static_assert(stdr::random_access_range<range>);
 
 static_assert(std::same_as<stdr::iterator_t<range const>, range::iterator>);
 static_assert(stdr::common_range<range const>);
-static_assert(stdr::bidirectional_range<range const>);
+static_assert(stdr::random_access_range<range const>);

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

 #include <span>
 
 #include <iterator>
 
 using iterator = std::span<int>::iterator;
 using reverse_iterator = std::span<int>::reverse_iterator;
 using value_type = int;
 
-static_assert(std::bidirectional_iterator<iterator>);
+static_assert(std::random_access_iterator<iterator>);
 static_assert(std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(std::sized_sentinel_for<iterator, iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);

libcxx/test/std/input.output/filesystems/class.path/range_concept_conformance.compile.pass.cpp

 #include <concepts>
 #include <ranges>
 
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<fs::path>, fs::path::iterator>);
 static_assert(stdr::common_range<fs::path>);
 static_assert(stdr::bidirectional_range<fs::path>);
+static_assert(!stdr::random_access_range<fs::path>);
 
 static_assert(std::same_as<stdr::iterator_t<fs::path const>, fs::path::const_iterator>);
 static_assert(stdr::common_range<fs::path const>);
 static_assert(stdr::bidirectional_range<fs::path const>);
+static_assert(!stdr::random_access_range<fs::path const>);

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.bidir/subsumption.compile.pass.cpp

 // template<class T>
 // concept bidirectional_iterator;
 
 #include <iterator>
 
 #include <concepts>
 
 template<std::forward_iterator I>
-[[nodiscard]] constexpr bool check_subsumption() {
+constexpr bool check_subsumption() {
   return false;
 }
 
 template<std::bidirectional_iterator>
-[[nodiscard]] constexpr bool check_subsumption() {
+constexpr bool check_subsumption() {
   return true;
 }
 
 static_assert(check_subsumption<int*>());

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

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// template<class T>
+// concept random_access_iterator;
+
+#include <iterator>
+
+#include "test_iterators.h"
+#include "test_macros.h"
+
+static_assert(!std::random_access_iterator<cpp17_input_iterator<int*> >);
+static_assert(!std::random_access_iterator<cpp20_input_iterator<int*> >);
+static_assert(!std::random_access_iterator<forward_iterator<int*> >);
+static_assert(!std::random_access_iterator<bidirectional_iterator<int*> >);
+static_assert( std::random_access_iterator<random_access_iterator<int*> >);
+static_assert( std::random_access_iterator<contiguous_iterator<int*> >);
+
+static_assert(std::random_access_iterator<int*>);
+static_assert(std::random_access_iterator<int const*>);
+static_assert(std::random_access_iterator<int volatile*>);
+static_assert(std::random_access_iterator<int const volatile*>);
+
+struct wrong_iterator_category {
+    typedef std::bidirectional_iterator_tag iterator_category;
+    typedef int                             value_type;
+    typedef std::ptrdiff_t                  difference_type;
+    typedef int*                            pointer;
+    typedef int&                            reference;
+    typedef wrong_iterator_category         self;
+
+    reference operator*() const;
+    pointer operator->() const;
+    friend bool operator==(const self&, const self&);
+    friend bool operator< (const self&, const self&);
+    friend bool operator<=(const self&, const self&);
+    friend bool operator> (const self&, const self&);
+    friend bool operator>=(const self&, const self&);
+
+    self& operator++();
+    self operator++(int);
+
+    self& operator--();
+    self operator--(int);
+
+    self& operator+=(difference_type n);
+    self operator+(difference_type n) const;
+    friend self operator+(difference_type n, self x);
+
+    self& operator-=(difference_type n);
+    self operator-(difference_type n) const;
+    difference_type operator-(const self&) const;
+
+    reference operator[](difference_type n) const;
+};
+static_assert(std::bidirectional_iterator<wrong_iterator_category>);
+static_assert(!std::random_access_iterator<wrong_iterator_category>);
+
+template<class Child>
+struct common_base {
+    typedef std::random_access_iterator_tag iterator_category;
+    typedef int                             value_type;
+    typedef std::ptrdiff_t                  difference_type;
+    typedef int*                            pointer;
+    typedef int&                            reference;
+    typedef Child                           self;
+
+    reference operator*() const;
+    pointer operator->() const;
+    friend bool operator==(const self&, const self&);
+    friend bool operator< (const self&, const self&);
+    friend bool operator<=(const self&, const self&);
+    friend bool operator> (const self&, const self&);
+    friend bool operator>=(const self&, const self&);
+
+    self& operator++();
+    self operator++(int);
+
+    self& operator--();
+    self operator--(int);
+};
+
+struct simple_random_access_iterator
+  : common_base<simple_random_access_iterator> {
+
+    self& operator+=(difference_type n);
+    self operator+(difference_type n) const;
+    friend self operator+(difference_type n, self x);
+
+    self& operator-=(difference_type n);
+    self operator-(difference_type n) const;
+    difference_type operator-(const self&) const;
+
+    reference operator[](difference_type n) const;
+};
+static_assert(std::bidirectional_iterator<simple_random_access_iterator>);
+static_assert(std::random_access_iterator<simple_random_access_iterator>);
+
+struct no_plus_equals
+  : common_base<no_plus_equals> {
+
+ /* self& operator+=(difference_type n); */
+    self operator+(difference_type n) const;
+    friend self operator+(difference_type n, self x);
+
+    self& operator-=(difference_type n);
+    self operator-(difference_type n) const;
+    difference_type operator-(const self&) const;
+
+    reference operator[](difference_type n) const;
+};
+static_assert( std::bidirectional_iterator<no_plus_equals>);
+static_assert(!std::random_access_iterator<no_plus_equals>);
+
+struct no_plus_difference_type
+  : common_base<no_plus_difference_type> {
+
+    self& operator+=(difference_type n);
+ /* self operator+(difference_type n) const; */
+    friend self operator+(difference_type n, self x);
+
+    self& operator-=(difference_type n);
+    self operator-(difference_type n) const;
+    difference_type operator-(const self&) const;
+
+    reference operator[](difference_type n) const;
+};
+static_assert( std::bidirectional_iterator<no_plus_difference_type>);
+static_assert(!std::random_access_iterator<no_plus_difference_type>);
+
+struct difference_type_no_plus
+  : common_base<difference_type_no_plus> {
+
+    self& operator+=(difference_type n);
+    self operator+(difference_type n) const;
+ /* friend self operator+(difference_type n, self x); */
+
+    self& operator-=(difference_type n);
+    self operator-(difference_type n) const;
+    difference_type operator-(const self&) const;
+
+    reference operator[](difference_type n) const;
+};
+static_assert( std::bidirectional_iterator<difference_type_no_plus>);
+static_assert(!std::random_access_iterator<difference_type_no_plus>);
+
+struct no_minus_equals
+  : common_base<no_minus_equals> {
+
+    self& operator+=(difference_type n);
+    self operator+(difference_type n) const;
+    friend self operator+(difference_type n, self x);
+
+ /* self& operator-=(difference_type n); */
+    self operator-(difference_type n) const;
+    difference_type operator-(const self&) const;
+
+    reference operator[](difference_type n) const;
+};
+static_assert( std::bidirectional_iterator<no_minus_equals>);
+static_assert(!std::random_access_iterator<no_minus_equals>);
+
+struct no_minus
+  : common_base<no_minus> {
+
+    self& operator+=(difference_type n);
+    self operator+(difference_type n) const;
+    friend self operator+(difference_type n, self x);
+
+    self& operator-=(difference_type n);
+ /* self operator-(difference_type n) const; */
+    difference_type operator-(const self&) const;
+
+    reference operator[](difference_type n) const;
+};
+static_assert( std::bidirectional_iterator<no_minus>);
+static_assert(!std::random_access_iterator<no_minus>);
+
+struct not_sized_sentinel
+  : common_base<not_sized_sentinel> {
+
+    self& operator+=(difference_type n);
+    self operator+(difference_type n) const;
+    friend self operator+(difference_type n, self x);
+
+    self& operator-=(difference_type n);
+    self operator-(difference_type n) const;
+ /* difference_type operator-(const self&) const; */
+
+    reference operator[](difference_type n) const;
+};
+static_assert( std::bidirectional_iterator<not_sized_sentinel>);
+static_assert(!std::random_access_iterator<not_sized_sentinel>);
+
+struct no_subscript
+  : common_base<no_subscript> {
+
+    self& operator+=(difference_type n);
+    self operator+(difference_type n) const;
+    friend self operator+(difference_type n, self x);
+
+    self& operator-=(difference_type n);
+    self operator-(difference_type n) const;
+    difference_type operator-(const self&) const;
+
+ /* reference operator[](difference_type n) const; */
+};
+static_assert( std::bidirectional_iterator<no_subscript>);
+static_assert(!std::random_access_iterator<no_subscript>);

libcxx/test/std/iterators/predef.iterators/reverse.iterators/iterator_concept_conformance.compile.pass.cpp

[[nodiscard]] consteval bool common_reverse_iterator_checks() {
   static_assert(std::sentinel_for<I1, std::reverse_iterator<float*>>);
   static_assert(!std::sized_sentinel_for<I1, std::reverse_iterator<float*>>);
   return true;
 }
 
 using reverse_bidirectional_iterator = std::reverse_iterator<bidirectional_iterator<int*>>;
 static_assert(common_reverse_iterator_checks<reverse_bidirectional_iterator>());
 static_assert(std::bidirectional_iterator<reverse_bidirectional_iterator>);
+static_assert(!std::random_access_iterator<reverse_bidirectional_iterator>);
 static_assert(!std::sized_sentinel_for<reverse_bidirectional_iterator, reverse_bidirectional_iterator>);
 
 using reverse_random_access_iterator = std::reverse_iterator<random_access_iterator<int*>>;
 static_assert(common_reverse_iterator_checks<reverse_random_access_iterator>());
-static_assert(std::bidirectional_iterator<reverse_random_access_iterator>);
+static_assert(std::random_access_iterator<reverse_random_access_iterator>);
 static_assert(std::sized_sentinel_for<reverse_random_access_iterator, reverse_random_access_iterator>);
 
 using reverse_contiguous_iterator = std::reverse_iterator<contiguous_iterator<int*>>;
 static_assert(common_reverse_iterator_checks<reverse_contiguous_iterator>());
-static_assert(std::bidirectional_iterator<reverse_contiguous_iterator>);
+static_assert(std::random_access_iterator<reverse_contiguous_iterator>);
 static_assert(std::sized_sentinel_for<reverse_contiguous_iterator, reverse_contiguous_iterator>);

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

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// template<range _Rp>
+// concept random_access_range;
+
+#include <ranges>
+
+#include "test_range.h"
+#include "test_iterators.h"
+
+namespace ranges = std::ranges;
+
+template <template <class...> class I>
+constexpr bool check_range() {
+  constexpr bool result = ranges::random_access_range<test_range<I> >;
+  static_assert(ranges::random_access_range<test_range<I> const> == result);
+  static_assert(ranges::random_access_range<test_non_const_common_range<I> > == result);
+  static_assert(ranges::random_access_range<test_non_const_range<I> > == result);
+  static_assert(ranges::random_access_range<test_common_range<I> > == result);
+  static_assert(ranges::random_access_range<test_common_range<I> const> == result);
+  static_assert(!ranges::random_access_range<test_non_const_common_range<I> const>);
+  static_assert(!ranges::random_access_range<test_non_const_range<I> const>);
+  return result;
+}
+
+static_assert(!check_range<cpp20_input_iterator>());
+static_assert(!check_range<forward_iterator>());
+static_assert(!check_range<bidirectional_iterator>());
+static_assert(check_range<random_access_iterator>());
+static_assert(check_range<contiguous_iterator>());

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

 template<std::ranges::bidirectional_range>
 requires true
 [[nodiscard]] constexpr bool check_bidirectional_range_subsumption() {
   return true;
 }
 // clang-format on
 
 static_assert(check_bidirectional_range_subsumption<range>());
+
+template<std::ranges::bidirectional_range R>
+requires std::random_access_iterator<std::ranges::iterator_t<R> >
+constexpr bool check_random_access_range_subsumption() {
+  return false;
+}
+
+template<std::ranges::random_access_range>
+requires true
+constexpr bool check_random_access_range_subsumption() {
+  return true;
+}
+
+static_assert(check_random_access_range_subsumption<range>());

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

 
 #include <concepts>
 #include <ranges>
 
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<std::cmatch>, std::cmatch::iterator>);
 static_assert(stdr::common_range<std::cmatch>);
-static_assert(stdr::bidirectional_range<std::cmatch>);
+static_assert(stdr::random_access_range<std::cmatch>);
 
 static_assert(std::same_as<stdr::iterator_t<std::cmatch const>, std::cmatch::const_iterator>);
 static_assert(stdr::common_range<std::cmatch const>);
-static_assert(stdr::bidirectional_range<std::cmatch const>);
+static_assert(stdr::random_access_range<std::cmatch const>);

libcxx/test/std/strings/basic.string/range_concept_conformance.compile.pass.cpp

 
 #include <concepts>
 #include <ranges>
 
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<std::string>, std::string::iterator>);
 static_assert(stdr::common_range<std::string>);
-static_assert(stdr::bidirectional_range<std::string>);
+static_assert(stdr::random_access_range<std::string>);
 
 static_assert(std::same_as<stdr::iterator_t<std::string const>, std::string::const_iterator>);
 static_assert(stdr::common_range<std::string const>);
-static_assert(stdr::bidirectional_range<std::string const>);
+static_assert(stdr::random_access_range<std::string const>);

libcxx/test/std/strings/basic.string/string.iterators/iterator_concept_conformance.compile.pass.cpp

 #include <iterator>
 
 using iterator = std::string::iterator;
 using const_iterator = std::string::const_iterator;
 using reverse_iterator = std::string::reverse_iterator;
 using const_reverse_iterator = std::string::const_reverse_iterator;
 using value_type = char;
 
-static_assert(std::bidirectional_iterator<iterator>);
+static_assert(std::random_access_iterator<iterator>);
 static_assert(std::indirectly_writable<iterator, value_type>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<iterator, iterator>);
 static_assert(std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
-static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, value_type>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);

libcxx/test/std/strings/string.view/range_concept_conformance.compile.pass.cpp

 
 #include <concepts>
 #include <ranges>
 
 namespace stdr = std::ranges;
 
 static_assert(std::same_as<stdr::iterator_t<std::string_view>, std::string_view::iterator>);
 static_assert(stdr::common_range<std::string_view>);
-static_assert(stdr::bidirectional_range<std::string_view>);
+static_assert(stdr::random_access_range<std::string_view>);
 
 static_assert(std::same_as<stdr::iterator_t<std::string_view const>, std::string_view::const_iterator>);
 static_assert(stdr::common_range<std::string_view const>);
-static_assert(stdr::bidirectional_range<std::string_view const>);
+static_assert(stdr::random_access_range<std::string_view const>);

libcxx/test/std/strings/string.view/string.view.iterators/iterator_concept_conformance.compile.pass.cpp

 
 #include <iterator>
 
 using iterator = std::string_view::iterator;
 using const_iterator = std::string_view::const_iterator;
 using reverse_iterator = std::string_view::reverse_iterator;
 using const_reverse_iterator = std::string_view::const_reverse_iterator;
 
-static_assert(std::bidirectional_iterator<iterator>);
+static_assert(std::random_access_iterator<iterator>);
 static_assert(!std::indirectly_writable<iterator, char>);
 static_assert(std::sentinel_for<iterator, iterator>);
 static_assert(std::sentinel_for<iterator, const_iterator>);
 static_assert(!std::sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<iterator, iterator>);
 static_assert(std::sized_sentinel_for<iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
 
-static_assert(std::bidirectional_iterator<const_iterator>);
+static_assert(std::random_access_iterator<const_iterator>);
 static_assert(!std::indirectly_writable<const_iterator, char>);
 static_assert(std::sentinel_for<const_iterator, iterator>);
 static_assert(std::sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, iterator>);
 static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
 static_assert(!std::sized_sentinel_for<const_iterator, const_reverse_iterator>);