[libc++] Fix algorithms which use reverse_iterator

[philnik]

Summary

This adds a C++20-version of reverse_iterator which doesn't SFINAE away the operators for use inside the classic STL algorithms. Pre-C++20 _AlgRevIter is just an alias for reverse_iterator.

[philnik]

It's quite a bit of code duplication and complexity for __unwrap_iter_impl, but I think it's the best solution. Using reverse_iterator and other wrappers allows us to simplify a lot of algorithms. Not having a C++20-compatible reverse_iterator would also mean that we'd have to duplicate __half_inplace_merge. I'm open to other suggestions though. I hope we can remove _AlgRevIter in a few versions, since it's clearly a language bug. (BTW did anybody file a CWG issue yet?)

libcxx/include/__iterator/iterator_traits.h

498–502

I'm planning to use these in other parts of the code base, but I think it would be better to do this in NFC patches.

[philnik]

• Try to fix C++03

[Mordante]

libcxx/include/__iterator/reverse_iterator.h

342

I'm not really happy with this name, it doesn't tell me anything. I also would like some comment what this iterator wrapper is.

342

How is this class tested?

362

In general we prefer not to use compiler deduced auto on return types.

[philnik]

Rebased on top of D129039

libcxx/include/__iterator/reverse_iterator.h

342

Do you have any naming suggestion? Or would you just like to have it spelled out more like _AlgorihtmReverseIterator?

342

It's tested indirectly through copy_backward, inplace_merge and stable_sort. I'm planning to use it in more algorithms. Would you like have some explicit tests?

362

That makes sense to me with ABI-relevant parts of the code, but what's wrong with it in an implementation-detail class?

[Mordante]

libcxx/include/__iterator/reverse_iterator.h

342

Do you have any naming suggestion? Or would you just like to have it spelled out more like _AlgorihtmReverseIterator?

How do you about cpp17_reverse_iterator? I'm not sure whether we want to use algorithm in the name, this implies it should only be used in algorithms and not at other places.

At least with the comment it's easier to understand what the class is about. I had other associations with Alg which didn't make much sense.

342

It's tested indirectly through copy_backward, inplace_merge and stable_sort. I'm planning to use it in more algorithms. Would you like have some explicit tests?

I think it would be good to have some sanity checks for this class. That way when another test fails you can be sure it's the new code and not a bug in this class.

362

In my experience it makes it harder to understand the code. Instead of looking at a function signature I need to look in the function to see the returned type. It just saves typing a few characters for the writer, but puts a higher burden on the reader. I agree with Google in that regard; code should be optimized for the reader.

[philnik]

• Address comments

libcxx/include/__iterator/reverse_iterator.h

342

I think the implication you get from the name is correct. IMO we should only use _AlgRevIter (or whatever we will call it) in the places in which it is necessary. The only places I know of where that applies is in the classic STL algorithms. I think __cpp17_reverse_iterator sounds a bit too much like "this should be used pre-C++20 if you want a reverse_iterator", but it might be the better option if there are indeed other places where we want to use this reverse iterator.

342

I've copy-pasted the tests for reverse_iterator and removed a few tests (for iter_move, iter_swap, concepts and a few thing I haven't implemented like reverse_iterator<const char*> = reverse_oterator<char*> which should never be used in any algorithm anyways).

[huixie90]

libcxx/include/__iterator/reverse_iterator.h

344

question: is this class only supposed to be used in the classic algorithms? (that is why it doesn't need iter_move and iter_swap)

354–355

why c++20 iterator_concept is defined in terms of c++17 trait?

370–376

could you please clarify why SFIANE is removed and how do you prevent error on instantiating the class template with an _Iter that does not support ->? (assuming all non-template member functions are generated when class template is instantiated)

[philnik]

libcxx/include/__iterator/reverse_iterator.h

344

Yes, that's correct.

354–355

This is how it's defined in reverse_iterator. (Although it looks like it's a bug there, but that's another PR)

Edit: I think it's actually safe to remove the iterator_concept entirely here. We shouldn't rely on it anywhere in the classic algorithms. We might want to optimize on it at some point, but hopefully at that point this code doesn't exist anymore.

370–376

The new SFINAE in C++20 is the whole reason this PR exists at all. That's the part that breaks the classic algorithms. Regarding operator->: that has to exist for the classic algorithms. See https://en.cppreference.com/w/cpp/named_req/InputIterator.

[huixie90]

libcxx/include/__iterator/reverse_iterator.h

370–376

Then this class is incorrectly constrained (the static assert bit) the input _Iter has to model the c++17 bidi iterator, because c++20 bidi iterator wouldn’t work. It may not have -> , and it may have prvalue reference, which is not allowed in c++ 17 bidi

So the input Iter has to be c++17 and the result iterator is also c++17. Why not just call it c++17 reverse iterator.

Regarding random access operations not sfinae , when you pass in c++17 bidi only , wouldn’t it error on instantiating those member functions?

[philnik]

libcxx/include/__iterator/reverse_iterator.h

348

Fix to only allow C++17 bidirectional iterators.

370–376

Thanks, I made a note for myself at the correct place.

I think _Cpp17RevIter sounds too much like it should be use pre-C++20 if you want a reverse iterator, not that this is added for compatibility and should only be used in specific circumstances (specifically, that you get a user-defined iterator which may be C++20-hostile).

SFINAE only applies when you try to check if a function exists. If you never call the function the compiler doesn't instantiate it and you don't get an error.

[huixie90]

libcxx/include/__iterator/reverse_iterator.h

370–376

I totally agree that cpp17_xxx is really confusing. The standard uses these names
https://eel.is/c++draft/iterator.traits#2
When the standard says cpp17-iterator, it really means the classic iterator that model the classic Iterator named requirement, which has nothing to do with c++ 17. I don’t usually debate about names and I am ok with names that make sense for most people. for me I found the name cpp17, probably just because I used to how the spec calls those things

Regarding SFINAE, IIUC, for non template member function of a class template, the function body is instantiated as soon as the class template is instantiated, and this could trigger hard error in your case even you never call those functions

[philnik]

• Address comments
• Rebased

libcxx/include/__iterator/reverse_iterator.h

370–376

Every major compiler disagrees with you: https://godbolt.org/z/TxxsWxE9o.

[huixie90]

libcxx/include/__iterator/reverse_iterator.h

370–376

I think you are right here. I was thinking more about explicit instantiation. https://godbolt.org/z/T7n6986rz but we shouldn't be doing that as most stl templates are not SFINAE friendly.

anyway, IIUC, the purpose of this class is, in C++20 mode, this class "reverses" a C++17 iterator, and results in a C++17 iterator. The reason to have this class is that the reverse_iterator's SFINAE broke some iterators in C++20 mode.
Could you please elaborate what exactly is broken? This sounds either a bug in the standard or in our implementation of reverse_iterator

[philnik]

libcxx/include/__iterator/reverse_iterator.h

370–376

If you want an example of what breaks you can look at robust_against_cpp20_hostile_iterators.compile.pass.cpp. Basically the problem is that the standard considers the operator== overloads ambiguous. Clang considers them not ambiguous and spits out a warning. The problem now is that overload resolution would be different if clang would also consider it not ambiguous in SFINAE contexts, so there it isn't ambiguous but an error. That means that overload resolution fails instead of selecting the correct overload.

[huixie90]

libcxx/include/__iterator/reverse_iterator.h

370–376

Thanks for the explanation. I think it is worth to put your explanation in the comment in case in the future someone look at this and wonder why we need another reverse_iterator.

But IIUC, some iterators which are valid in C++17 standard, becomes invalid because of == starts being ambiguous in C++20 standard. This sounds a flag to me. Let me put this in sg9's reflector and see what people think.

[philnik]

• Address comment and try to fix CI

[philnik]

• Try to fix CI

[philnik]

• Extend copy_backward tests and try to fix CI

[var-const]

@philnik My initial impression is that we shouldn't try to solve this at the library level. This looks like a legitimate issue with the core language.

If I understand it correctly (and please point out if I'm wrong), the issue is that there is no perfect match for operator==, and the only operator== available has essentially this form:

bool operator==(const BaseIter&, const DerivedIter&);

Which would work except that the C++20 rewriting rules also generate the same function with reversed arguments:

bool operator==(const DerivedIter&, const BaseIter&);

Which then becomes ambiguous.

I think it would be easier to rewrite our existing algorithms to avoid using reverse_iterator. We can add a TODO to revisit the implementation when (and if) the core language issue gets fixed.

[var-const]

libcxx/include/__iterator/reverse_iterator.h

211

If we're doing essentially a workaround, would it be possible/easier to instead define an internal comparator for reverse iterators and use it in the affected algorithms?

bool __reverse_iter_eq(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) {
  return __x.base() == __y.base();
}
// In the algorithm
for (; !std::__reverse_iter_eq(__first, __last); ++__first) {

429

Hmm, so this expression is not ambiguous, but when it's used as a constraint in a requires clause, it is considered ambiguous? Am I missing something?

[philnik]

In D128864#3667664, @var-const wrote:

@philnik My initial impression is that we shouldn't try to solve this at the library level. This looks like a legitimate issue with the core language.

I agree that this is a core issue, but not fixing it is also not an option IMO.

If I understand it correctly (and please point out if I'm wrong), the issue is that there is no perfect match for operator==, and the only operator== available has essentially this form:

bool operator==(const BaseIter&, const DerivedIter&);

Which would work except that the C++20 rewriting rules also generate the same function with reversed arguments:

bool operator==(const DerivedIter&, const BaseIter&);

Which then becomes ambiguous.

Yes.

I think it would be easier to rewrite our existing algorithms to avoid using reverse_iterator. We can add a TODO to revisit the implementation when (and if) the core language issue gets fixed.

I don't think that it would be easier two rewrite existing algorithms. This would lead to a lot of complicated duplicated code. That is always a recipe for chaos and divergence. Effectively duplicating reverse_iterator isn't perfect either, but the code really isn't complicated. Most member functions are a single line.

libcxx/include/__iterator/reverse_iterator.h

211

Not really. There would be no easy way to distinguish between an internal reverse_iterator and an external one.

429

No, that's exactly the case.

[var-const]

libcxx/include/__iterator/reverse_iterator.h

429

Interesting. Why is that?

[philnik]

libcxx/include/__iterator/reverse_iterator.h

429

I don't know exactly why, but I think it is because that would change the overload resolution. With the change in SFINAE contexts you could end up calling different functions, not just allow code that would otherwise be an error.

[ldionne]

I am also not happy with this, but I don't see a better solution for fixing the underlying issue.

Other alternatives:

1. Stop using reverse_iterator in the implementation of algorithms. That would mean reimplementing some of the logic we have in std::copy for lowering to memmove, unwrapping iterators and more. I'm ambivalent about this, but @philnik seems to be convinced that it would be worse than this patch, and I would tend to agree.
2. Stop using reverse_iterator in the implementation of algorithms, and don't try to apply optimizations in those. That way we lose the complexity of this patch, but we also lose the perf benefits. I don't think we should do this.

@philnik, can you please file a CWG issue when the LLVM 15 branch is done? On a related note, I should create a space where we can share issue drafts for libc++ contributors to look at and chime in on. I'm taking this as an action item.

@var-const Can you think of other alternatives that would fix those algorithms with C++20 hostiles iterators?

libcxx/include/__iterator/reverse_iterator.h

338–339

What do you think about __unconstrained_reverse_iterator instead? It's a mouthful, but we don't plan on using it in too many places anyways.

[ldionne]

In D128864#3669132, @ldionne wrote:

@var-const Can you think of other alternatives that would fix those algorithms with C++20 hostiles iterators?

@philnik

@var-const and I just discussed and we agreed to move forward with this approach. We'll spend some time investigating whether another approach would be viable once the branch is cut, but this shouldn't prevent this patch from moving forward. Let's apply outstanding comments and ping me so we can merge this.

[var-const]

After offline discussions, I'm fine with this approach (I'd like to explore simplifying our implementation of copy* and move* and potentially removing the internal reverse iterator, but that's for the future and is not guaranteed to work out well). The most important comment I have is to have a lot of context in the class comment to explain the purpose of the class. It's a tricky issue, so we should help the reader of the code as much as we can.

libcxx/include/__algorithm/copy_backward.h

46

Question: why doesn't this use __copy? (I presume there's a reason, just checking)

libcxx/include/__iterator/reverse_iterator.h

211

Ah, good point.

338–339

+1 -- there might be a better name, but comparing these two, __unconstrained_reverse_iterator makes it easier to understand the purpose of the class.

341–454

Here's my attempt to improve the wording here. IMO, explaining context here is very important because otherwise it's not clear why we want to maintain essentially two versions of reverse_iterator:
"""
This class allows us to use reverse iterators in algorithms' implementation by working around a language issue in C++20.

In C++20, when a reverse iterator wraps certain C++20-"hostile" iterators, calling comparison operators on it will result in a compilation error on Clang. However, calling comparison operators on the pristine hostile iterator is not an error. Thus, we cannot use reverse iterators in the implementation of an algorithm that accepts a hostile iterator. This class is an internal workaround -- it is a copy of reverse_iterator with tweaks to make it support hostile iterators.

A "hostile" iterator is one that defines a comparison operator where one of the arguments is an exact match and the other requires an implicit conversion, for example:

friend bool operator==(const BaseIter&, const DerivedIter&);

C++20 rules for rewriting equality operators create another overload of this function with parameters reversed:

friend bool operator==(const DerivedIter&, const BaseIter&);

This creates an ambiguity in overload resolution.

However, the ambiguity is only a compilation error when used in a requires clause, not in the actual function body. This class simply removes the problematic constraints from comparison functions.
"""

402

Nit: there's one extra blank line here, please remove it.

428

Consider adding a comment like:

// Deliberately unconstrained unlike the comparison functions in `reverse_iterator` -- see the class comment for the rationale.

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/equal.pass.cpp

10

The new reverse iterator is only used in C++20 mode and above, right? Would it make sense to mark these tests as only supporting recent language versions and simplify them (replace TEST_CONSTEXPR_FOO with constexpr, etc.)?

[var-const]

libcxx/include/__iterator/reverse_iterator.h

429

It looks like this paper aims to fix the language issue: https://github.com/cplusplus/papers/issues/1127
Unfortunately, even though the paper was approved this February, it doesn't fix all the potential cases that create ambiguity, so it won't change anything for us even after it's implemented in the compiler (or at least that's how I read it).

[huixie90]

libcxx/include/__iterator/reverse_iterator.h

429

First of all, I think the current clang behaviour is really confusing.
See this example https://godbolt.org/z/v767Kdd7K

• If you write foo1 == foo2, it actually compiles fine with just a warning
• If you write a concept that checks foo1 == foo2 is valid expression, it returns false

I think clang contradicts itself.

@var-const Thanks for posting this paper P2468R2, I actually think the paper fixes our issue. The example in the paper section 1.2.1
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2468r2.html#open-source-sampling
is exactly what we are facing in robust_against_cpp20_hostile_iterators.compile.pass.cpp
https://github.com/llvm/llvm-project/blob/main/libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp#L50

They both have CRTP base with a member == that takes a derived class. And the usage of derived == derived is ambiguous due to the fact that both sides are equally convertible from derived to base.

The straw poll of this paper will happen next Monday. I am not sure what is the best action for us for llvm-15

[var-const]

libcxx/include/__iterator/reverse_iterator.h

429

@huixie90 Yes, this is the part that confuses me. I understand why Clang sees an ambiguity there, but I don't understand why it behaves differently in two different contexts. If Clang wants to be pedantic about this issue, it seems like it should reject foo1 == foo2, not issue a warning. If Clang wants to be permissive, it should evaluate the concept to true. Of course, it's possible that I'm missing something, but it looks like it might be unintentional.

Re. the proposal -- if I'm reading it correctly, it's only proposing the Second resolution, which is to avoid rewrites if the class has both a user-provided operator== and a user-provided operator!=. A valid iterator can still define a "hostile" operator== without defining an operator!=, which would still lead to the same issue we're dealing with. In the proposal, it says that 8 out of 110 projects they evaluated are still failing after the proposed fix. Unfortunately, from our perspective it means that the proposal doesn't really change anything. Even if the number of iterators considered hostile is reduced 10x, it's still a valid use case that we have to support.

[var-const]

libcxx/include/__iterator/reverse_iterator.h

341–454

However, the ambiguity is only a compilation error when used in a requires clause, not in the actual function body.

This sentence would be better as:
"""
Confusingly, Clang treats this ambiguity differently in different contexts. When operator== is actually called in the function body, the code is accepted with a warning. When a concept requires operator== to be a valid expression, however, it evaluates to false. Thus, the implementation of reverse_iterator::operator== can actually call operator== on its base iterators, but the constraints on reverse_iterator::operator== prevent it from being considered during overload resolution. This class simply removes the problematic constraints from comparison functions.
"""

[philnik]

• Address comments

libcxx/include/__algorithm/copy_backward.h

46

Just because it doesn't really make a difference and using the public interface leads to less refactorings when changing the copy internals.

libcxx/include/__iterator/reverse_iterator.h

429

I think clang does that, because allowing it in evaluated contexts only allows a program to compile that would otherwise not be a valid program. Having requires(T lhs, T rhs) { lhs == rhs; } return true would change the meaning of the program, not just let a program compile. IOW, I think Clang is actually the only conforming compiler in this example. I could be completely wrong though.

Regarding the proposal, I think it does solve our issue. I would guess that Clang, GCC and MSVC drop the extension after implementing the paper, meaning that it would be an error anyways and thus not be a problem for us anymore.

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/equal.pass.cpp

10

I think it's not a bad idea to check that the iterator works the same in all language versions. Only running the tests in C++20 and 23 would simplify them a bit, but not that much.

[var-const]

libcxx/include/__iterator/reverse_iterator.h

429

Regarding the proposal, I think it does solve our issue.

Wouldn't an iterator type that only defines bool operator==(const Iter& res); // no const and no corresponding operator!= still be broken?

[philnik]

libcxx/include/__iterator/reverse_iterator.h

429

I think it would be broken, but it would be broken either way. There is nothing we can do about it if the compiler also errors when calling it in a function (which would be my expectation when the paper is implemented).

libcxx/include/__algorithm/copy.h

#endif
   const size_t __n = static_cast<size_t>(__last - __first);
   if (__n > 0)
     ::__builtin_memmove(__result, __first, __n * sizeof(_OutValueT));
   return std::make_pair(__first + __n, __result + __n);
 }
 
 template <class _InIter, class _OutIter,
           __enable_if_t<is_same<typename remove_const<__iter_value_type<_InIter> >::type, __iter_value_type<_OutIter> >::value
-                      && __is_cpp17_contiguous_iterator<_InIter>::value
-                      && __is_cpp17_contiguous_iterator<_OutIter>::value
-                      && is_trivially_copy_assignable<__iter_value_type<_OutIter> >::value, int> = 0>
+                      && __is_cpp17_contiguous_iterator<typename _InIter::iterator_type>::value
+                      && __is_cpp17_contiguous_iterator<typename _OutIter::iterator_type>::value
+                      && is_trivially_copy_assignable<__iter_value_type<_OutIter> >::value
+                      && __is_reverse_iterator<_InIter>::value
+                      && __is_reverse_iterator<_OutIter>::value, int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-pair<reverse_iterator<_InIter>, reverse_iterator<_OutIter> >
-__copy_impl(reverse_iterator<_InIter> __first,
-            reverse_iterator<_InIter> __last,
-            reverse_iterator<_OutIter> __result) {
+pair<_InIter, _OutIter>
+__copy_impl(_InIter __first, _InIter __last, _OutIter __result) {
   auto __first_base = std::__unwrap_iter(__first.base());
   auto __last_base = std::__unwrap_iter(__last.base());
   auto __result_base = std::__unwrap_iter(__result.base());
   auto __result_first = __result_base - (__first_base - __last_base);
   std::__copy_impl(__last_base, __first_base, __result_first);
-  return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first)));
+  return std::make_pair(__last, _OutIter(std::__rewrap_iter(__result.base(), __result_first)));
 }
 
 template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<!(is_copy_constructible<_InIter>::value
                        && is_copy_constructible<_Sent>::value
                        && is_copy_constructible<_OutIter>::value), int> = 0 >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {

libcxx/include/__algorithm/copy_backward.h

 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Iter1, class _Sent1, class _Iter2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_Iter1, _Iter2> __copy_backward_impl(_Iter1 __first, _Sent1 __last, _Iter2 __result) {
-  auto __ret = std::__copy(reverse_iterator<_Iter1>(__last),
-                           reverse_iterator<_Sent1>(__first),
-                           reverse_iterator<_Iter2>(__result));
+  auto __ret = std::__copy(_AlgRevIter<_Iter1>(__last),
+                           _AlgRevIter<_Sent1>(__first),
+                           _AlgRevIter<_Iter2>(__result));
   return pair<_Iter1, _Iter2>(__ret.first.base(), __ret.second.base());
 }
 
 template <class _Iter1, class _Sent1, class _Iter2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) {
   auto __ret = std::__copy_backward_impl(std::__unwrap_iter(__first),
                                          std::__unwrap_iter(__last),
                                          std::__unwrap_iter(__result));
   return pair<_Iter1, _Iter2>(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {
   return std::__copy_backward(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H

libcxx/include/__algorithm/inplace_merge.h

if (__len1 <= __len2)
             ::new ((void*)__p) value_type(_VSTD::move(*__i));
         _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
             ::new ((void*)__p) value_type(_VSTD::move(*__i));
-        typedef reverse_iterator<_BidirectionalIterator> _RBi;
-        typedef reverse_iterator<value_type*> _Rv;
+        typedef _AlgRevIter<_BidirectionalIterator> _RBi;
+        typedef _AlgRevIter<value_type*> _Rv;
         typedef __invert<_Compare> _Inverted;
         _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff),
                                     _RBi(__middle), _RBi(__first),
                                     _RBi(__last), _Inverted(__comp));
     }
 }
 
 template <class _Compare, class _BidirectionalIterator>

libcxx/include/__algorithm/set_intersection.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SET_INTERSECTION_H
 #define _LIBCPP___ALGORITHM_SET_INTERSECTION_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 

libcxx/include/__iterator/iterator_traits.h

 template<class _InputIterator>
 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
 
 template<class _InputIterator>
 using __iter_to_alloc_type = pair<
     typename add_const<typename iterator_traits<_InputIterator>::value_type::first_type>::type,
     typename iterator_traits<_InputIterator>::value_type::second_type>;
 
+template <class _Iter>
+using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category;
+
+template <class _Iter>
+using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H

libcxx/include/__iterator/reverse_iterator.h

void iter_swap(const reverse_iterator& __x, const reverse_iterator<_Iter2>& __y)
           noexcept(ranges::iter_swap(--declval<_Iter&>(), --declval<_Iter2&>()))) {
       auto __xtmp = __x.base();
       auto __ytmp = __y.base();
       ranges::iter_swap(--__xtmp, --__ytmp);
     }
 #endif // _LIBCPP_STD_VER > 17
 };
 
+template <class _Iter>
+struct __is_reverse_iterator : false_type {};
+
+template <class _Iter>
+struct __is_reverse_iterator<reverse_iterator<_Iter> > : true_type {};
+
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 bool
 operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
 #if _LIBCPP_STD_VER > 17
     requires requires {
       { __x.base() == __y.base() } -> convertible_to<bool>;
     }
 #endif // _LIBCPP_STD_VER > 17
 {
     return __x.base() == __y.base();
 }
 
 template <class _Iter1, class _Iter2>

 template <class _Iter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
 {
     return reverse_iterator<_Iter>(__i);
 }
 #endif
 
+#if _LIBCPP_STD_VER <= 17
+template <class _Iter>
+using _AlgRevIter = reverse_iterator<_Iter>;
+#else
+
+// reverse_iterator breaks some C++20-hostile iterators. This class is essentially a copy-paste of reverse_iterator
+// with the problematic parts removed to make it usable in the classic STL algorithms in C++20.
 template <class _Iter>
-using _ReverseWrapper = reverse_iterator<reverse_iterator<_Iter> >;
+class _AlgRevIter {
+  _Iter __iter_;
 
-template <class _Iter, bool __b>
-struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> {
+public:
+  static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value);
+
+  using iterator_type = _Iter;
+  using iterator_category =
+      _If<__is_cpp17_random_access_iterator<_Iter>::value, random_access_iterator_tag, __iterator_category_type<_Iter>>;
+  using pointer = __iterator_pointer_type<_Iter>;
+  using value_type = iter_value_t<_Iter>;
+  using difference_type = iter_difference_t<_Iter>;
+  using reference = iter_reference_t<_Iter>;
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter() = default;
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter(const _AlgRevIter&) = default;
+  _LIBCPP_HIDE_FROM_ABI constexpr explicit _AlgRevIter(_Iter __iter) : __iter_(__iter) {}
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _Iter base() const { return __iter_; }
+  _LIBCPP_HIDE_FROM_ABI constexpr reference operator*() const {
+    auto __tmp = __iter_;
+    return *--__tmp;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr pointer operator->() const {
+    if constexpr (is_pointer_v<_Iter>) {
+      return std::prev(__iter_);
+    } else {
+      return std::prev(__iter_).operator->();
+    }
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter& operator++() {
+    --__iter_;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter operator++(int) {
+    auto __tmp = *this;
+    --__iter_;
+    return __tmp;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter& operator--() {
+    ++__iter_;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter operator--(int) {
+    auto __tmp = *this;
+    ++__iter_;
+    return __tmp;
+  }
+
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter& operator+=(difference_type __n) {
+    __iter_ -= __n;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter& operator-=(difference_type __n) {
+    __iter_ += __n;
+    return *this;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter operator+(difference_type __n) const {
+    return _AlgRevIter(__iter_ - __n);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr _AlgRevIter operator-(difference_type __n) const {
+    return _AlgRevIter(__iter_ + __n);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr difference_type operator-(const _AlgRevIter& __other) const {
+    return __other.__iter_ - __iter_;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI constexpr auto operator[](difference_type __n) const { return *(*this + __n); }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const _AlgRevIter& __lhs, const _AlgRevIter& __rhs) {
+    return __lhs.base() == __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator!=(const _AlgRevIter& __lhs, const _AlgRevIter& __rhs) {
+    return __lhs.base() != __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<(const _AlgRevIter& __lhs, const _AlgRevIter& __rhs) {
+    return __lhs.base() > __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>(const _AlgRevIter& __lhs, const _AlgRevIter& __rhs) {
+    return __lhs.base() < __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<=(const _AlgRevIter& __lhs, const _AlgRevIter& __rhs) {
+    return __lhs.base() >= __rhs.base();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>=(const _AlgRevIter& __lhs, const _AlgRevIter& __rhs) {
+    return __lhs.base() <= __rhs.base();
+  }
+};
+
+template <class _Iter>
+struct __is_reverse_iterator<_AlgRevIter<_Iter>> : true_type {};
+
+#endif // _LIBCPP_STD_VER <= 17
+
+template <template <class> class _RevIter1, template <class> class _RevIter2, class _Iter>
+struct __unwrap_reverse_iter_impl {
   using _UnwrappedIter = decltype(__unwrap_iter_impl<_Iter>::__unwrap(std::declval<_Iter>()));
+  using _ReverseWrapper = _RevIter1<_RevIter2<_Iter> >;
 
-  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ReverseWrapper<_Iter>
-  __rewrap(_ReverseWrapper<_Iter> __orig_iter, _UnwrappedIter __unwrapped_iter) {
-    return _ReverseWrapper<_Iter>(
-        reverse_iterator<_Iter>(__unwrap_iter_impl<_Iter>::__rewrap(__orig_iter.base().base(), __unwrapped_iter)));
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ReverseWrapper
+  __rewrap(_ReverseWrapper __orig_iter, _UnwrappedIter __unwrapped_iter) {
+    return _ReverseWrapper(
+        _RevIter2<_Iter>(__unwrap_iter_impl<_Iter>::__rewrap(__orig_iter.base().base(), __unwrapped_iter)));
   }
 
-  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _UnwrappedIter __unwrap(_ReverseWrapper<_Iter> __i) _NOEXCEPT {
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _UnwrappedIter __unwrap(_ReverseWrapper __i) _NOEXCEPT {
     return __unwrap_iter_impl<_Iter>::__unwrap(__i.base().base());
   }
 };
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 template <ranges::bidirectional_range _Range>
 _LIBCPP_HIDE_FROM_ABI constexpr ranges::
     subrange<reverse_iterator<ranges::iterator_t<_Range>>, reverse_iterator<ranges::iterator_t<_Range>>>
     __reverse_range(_Range&& __range) {
   auto __first = ranges::begin(__range);
   return {std::make_reverse_iterator(ranges::next(__first, ranges::end(__range))), std::make_reverse_iterator(__first)};
 }
 #endif
 
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<reverse_iterator<reverse_iterator<_Iter> >, __b>
+    : __unwrap_reverse_iter_impl<reverse_iterator, reverse_iterator, _Iter> {};
+
+#if _LIBCPP_STD_VER > 17
+
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<reverse_iterator<_AlgRevIter<_Iter>>, __b>
+    : __unwrap_reverse_iter_impl<reverse_iterator, _AlgRevIter, _Iter> {};
+
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<_AlgRevIter<reverse_iterator<_Iter>>, __b>
+    : __unwrap_reverse_iter_impl<_AlgRevIter, reverse_iterator, _Iter> {};
+
+template <class _Iter, bool __b>
+struct __unwrap_iter_impl<_AlgRevIter<_AlgRevIter<_Iter>>, __b>
+    : __unwrap_reverse_iter_impl<_AlgRevIter, _AlgRevIter, _Iter> {};
+
+#endif // _LIBCPP_STD_VER > 17
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H

libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp

void test() {
   std::mt19937_64 rng;
 
   (void) std::adjacent_find(it, it);
   (void) std::adjacent_find(it, it, pred);
   (void) std::all_of(it, it, pred);
   (void) std::any_of(it, it, pred);
   (void) std::binary_search(it, it, 0);
   (void) std::binary_search(it, it, 0, pred);
+  (void) std::copy_backward(it, it, it);
   (void) std::copy_if(it, it, it, pred);
   (void) std::copy_n(it, 0, it);
   (void) std::copy(it, it, it);
   (void) std::count_if(it, it, pred);
   (void) std::count(it, it, 0);
   (void) std::equal_range(it, it, 0);
   (void) std::equal_range(it, it, 0, pred);
   (void) std::equal(it, it, it);

 #if TEST_STD_VER > 14
   (void) std::for_each_n(it, 0, pred);
 #endif
   (void) std::for_each(it, it, pred);
   (void) std::generate_n(it, 0, pred);
   (void) std::generate(it, it, pred);
   (void) std::includes(it, it, it, it);
   (void) std::includes(it, it, it, it, pred);
-  // (void) std::inplace_merge(it, it, it);
-  // (void) std::inplace_merge(it, it, it, pred);
+  (void) std::inplace_merge(it, it, it);
+  (void) std::inplace_merge(it, it, it, pred);
   (void) std::is_heap_until(it, it);
   (void) std::is_heap_until(it, it, pred);
   (void) std::is_heap(it, it);
   (void) std::is_heap(it, it, pred);
   (void) std::is_partitioned(it, it, pred);
   (void) std::is_permutation(it, it, it);
   (void) std::is_permutation(it, it, it, pred);
 #if TEST_STD_VER > 11
#if TEST_STD_VER > 17
   (void) std::shift_right(it, it, 0);
 #endif
   (void) std::shuffle(it, it, rng);
   (void) std::sort_heap(it, it);
   (void) std::sort_heap(it, it, pred);
   (void) std::sort(it, it);
   (void) std::sort(it, it, pred);
   (void) std::stable_partition(it, it, pred);
-  // (void) std::stable_sort(it, it);
+  (void) std::stable_sort(it, it);
   (void) std::swap_ranges(it, it, it);
   (void) std::transform(it, it, it, pred);
   (void) std::transform(it, it, it, it, pred);
   (void) std::unique_copy(it, it, it);
   (void) std::unique(it, it);
   (void) std::upper_bound(it, it, 0);
 }

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/equal.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <BidirectionalIterator Iter1, BidirectionalIterator Iter2>
+//   requires HasEqualTo<Iter1, Iter2>
+// bool operator==(const _AlgRevIter<Iter1>& x, const _AlgRevIter<Iter2>& y); // constexpr since C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It l, It r, bool x) {
+    const std::_AlgRevIter<It> r1(l);
+    const std::_AlgRevIter<It> r2(r);
+    assert((r1 == r2) == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(bidirectional_iterator<const char*>(s), bidirectional_iterator<const char*>(s), true);
+    test(bidirectional_iterator<const char*>(s), bidirectional_iterator<const char*>(s+1), false);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s), true);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s+1), false);
+    test(s, s, true);
+    test(s, s+1, false);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/greater-equal.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <RandomAccessIterator Iter1, RandomAccessIterator Iter2>
+//   requires HasGreater<Iter1, Iter2>
+// bool operator>=(const _AlgRevIter<Iter1>& x, const _AlgRevIter<Iter2>& y); // constexpr since C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It l, It r, bool x) {
+    const std::_AlgRevIter<It> r1(l);
+    const std::_AlgRevIter<It> r2(r);
+    assert((r1 >= r2) == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s), true);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s+1), true);
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s), false);
+    test(s, s, true);
+    test(s, s+1, true);
+    test(s+1, s, false);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/greater.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <RandomAccessIterator Iter1, RandomAccessIterator Iter2>
+//   requires HasGreater<Iter1, Iter2>
+// bool operator>(const _AlgRevIter<Iter1>& x, const _AlgRevIter<Iter2>& y); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It l, It r, bool x) {
+    const std::_AlgRevIter<It> r1(l);
+    const std::_AlgRevIter<It> r2(r);
+    assert((r1 > r2) == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s), false);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s+1), true);
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s), false);
+    test(s, s, false);
+    test(s, s+1, true);
+    test(s+1, s, false);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/less-equal.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <RandomAccessIterator Iter1, RandomAccessIterator Iter2>
+//   requires HasGreater<Iter1, Iter2>
+// bool operator<=(const _AlgRevIter<Iter1>& x, const _AlgRevIter<Iter2>& y); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It l, It r, bool x) {
+    const std::_AlgRevIter<It> r1(l);
+    const std::_AlgRevIter<It> r2(r);
+    assert((r1 <= r2) == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s), true);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s+1), false);
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s), true);
+    test(s, s, true);
+    test(s, s+1, false);
+    test(s+1, s, true);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/less.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <RandomAccessIterator Iter1, RandomAccessIterator Iter2>
+//   requires HasGreater<Iter1, Iter2>
+// bool operator<(const _AlgRevIter<Iter1>& x, const _AlgRevIter<Iter2>& y); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It l, It r, bool x) {
+    const std::_AlgRevIter<It> r1(l);
+    const std::_AlgRevIter<It> r2(r);
+    assert((r1 < r2) == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s), false);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s+1), false);
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s), true);
+    test(s, s, false);
+    test(s, s+1, false);
+    test(s+1, s, true);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cmp/not-equal.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <BidirectionalIterator Iter1, BidirectionalIterator Iter2>
+//   requires HasEqualTo<Iter1, Iter2>
+// bool operator!=(const _AlgRevIter<Iter1>& x, const _AlgRevIter<Iter2>& y); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It l, It r, bool x) {
+    const std::_AlgRevIter<It> r1(l);
+    const std::_AlgRevIter<It> r2(r);
+    assert((r1 != r2) == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(bidirectional_iterator<const char*>(s), bidirectional_iterator<const char*>(s), false);
+    test(bidirectional_iterator<const char*>(s), bidirectional_iterator<const char*>(s+1), true);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s), false);
+    test(random_access_iterator<const char*>(s), random_access_iterator<const char*>(s+1), true);
+    test(s, s, false);
+    test(s, s+1, true);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cons/assign.LWG3435.verify.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <class U>
+//  requires !same_as<U, Iter> && convertible_to<const U&, Iter> && assignable_from<Iter&, const U&>
+// _AlgRevIter& operator=(const _AlgRevIter<U>& u);
+
+#include <iterator>
+
+struct Base { };
+struct Derived : Base { };
+
+void test() {
+    std::_AlgRevIter<Base*> base;
+    std::_AlgRevIter<Derived*> derived;
+    derived = base; // expected-error {{no viable overloaded '='}}
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cons/ctor.default.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// _AlgRevIter(); // constexpr since C++17
+
+#include <iterator>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test() {
+    std::_AlgRevIter<It> r;
+    (void)r;
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    test<bidirectional_iterator<const char*> >();
+    test<random_access_iterator<char*> >();
+    test<char*>();
+    test<const char*>();
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cons/ctor.iter.explicit.verify.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// explicit _AlgRevIter(Iter x);
+
+// test explicitness
+
+#include <iterator>
+
+int main(int, char**) {
+    char const* it = "";
+    std::_AlgRevIter<char const*> r = it; // expected-error{{no viable conversion from 'const char *' to 'std::_AlgRevIter<const char *>'}}
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cons/ctor.iter.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// explicit _AlgRevIter(Iter x); // constexpr since C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i) {
+    std::_AlgRevIter<It> r(i);
+    assert(r.base() == i);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char s[] = "123";
+    test(bidirectional_iterator<const char*>(s));
+    test(random_access_iterator<const char*>(s));
+    test(s);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.cons/ctor.reverse_iterator.LWG3435.verify.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <class U>
+//  requires !same_as<U, Iter> && convertible_to<const U&, Iter>
+// _AlgRevIter(const _AlgRevIter<U> &);
+
+#include <iterator>
+
+struct Base { };
+struct Derived : Base { };
+
+void test() {
+    std::_AlgRevIter<Base*> base;
+    std::_AlgRevIter<Derived*> derived(base); // expected-error {{no matching constructor for initialization of 'std::_AlgRevIter<Derived *>'}}
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.conv/base.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// iterator_type base() const; // constexpr since C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+TEST_CONSTEXPR_CXX17 bool test() {
+    typedef bidirectional_iterator<int*> Iter;
+    int i = 0;
+    Iter iter(&i);
+    std::_AlgRevIter<Iter> const reverse(iter);
+    std::_AlgRevIter<Iter>::iterator_type base = reverse.base();
+    assert(base == Iter(&i));
+    return true;
+}
+
+int main(int, char**) {
+    test();
+#if TEST_STD_VER > 14
+    static_assert(test(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.elem/arrow.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// pointer operator->() const; // constexpr in C++17
+
+// Be sure to respect LWG 198:
+//    http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#198
+// LWG 198 was superseded by LWG 2360
+//    http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2360
+
+
+#include <iterator>
+#include <list>
+#include <cassert>
+
+#include "test_macros.h"
+
+class A
+{
+    int data_;
+public:
+    A() : data_(1) {}
+    ~A() {data_ = -1;}
+
+    int get() const {return data_;}
+
+    friend bool operator==(const A& x, const A& y)
+        {return x.data_ == y.data_;}
+};
+
+template <class It>
+void
+test(It i, typename std::iterator_traits<It>::value_type x)
+{
+    std::_AlgRevIter<It> r(i);
+    assert(r->get() == x.get());
+}
+
+class B
+{
+    int data_;
+public:
+    B(int d=1) : data_(d) {}
+    ~B() {data_ = -1;}
+
+    int get() const {return data_;}
+
+    friend bool operator==(const B& x, const B& y)
+        {return x.data_ == y.data_;}
+    const B *operator&() const { return nullptr; }
+    B       *operator&()       { return nullptr; }
+};
+
+class C
+{
+    int data_;
+public:
+    TEST_CONSTEXPR C() : data_(1) {}
+
+    TEST_CONSTEXPR int get() const {return data_;}
+
+    friend TEST_CONSTEXPR bool operator==(const C& x, const C& y)
+        {return x.data_ == y.data_;}
+};
+
+TEST_CONSTEXPR  C gC;
+
+int main(int, char**)
+{
+  A a;
+  test(&a+1, A());
+
+  {
+    std::list<B> l;
+    l.push_back(B(0));
+    l.push_back(B(1));
+    l.push_back(B(2));
+
+    {
+      std::list<B>::const_iterator i = l.begin();
+      assert ( i->get() == 0 );  ++i;
+      assert ( i->get() == 1 );  ++i;
+      assert ( i->get() == 2 );  ++i;
+      assert ( i == l.end ());
+    }
+
+    {
+      std::list<B>::const_reverse_iterator ri = l.rbegin();
+      assert ( ri->get() == 2 );  ++ri;
+      assert ( ri->get() == 1 );  ++ri;
+      assert ( ri->get() == 0 );  ++ri;
+      assert ( ri == l.rend ());
+    }
+  }
+
+#if TEST_STD_VER > 14
+  {
+    typedef std::_AlgRevIter<const C *> RI;
+    constexpr RI it1 = std::_AlgRevIter(&gC+1);
+
+    static_assert(it1->get() == gC.get(), "");
+  }
+#endif
+  {
+    ((void)gC);
+  }
+
+  return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.elem/bracket.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// requires RandomAccessIterator<Iter>
+// unspecified operator[](difference_type n) const; // constexpr since C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i,
+                               typename std::iterator_traits<It>::difference_type n,
+                               typename std::iterator_traits<It>::value_type x) {
+    typedef typename std::iterator_traits<It>::value_type value_type;
+    const std::_AlgRevIter<It> r(i);
+    value_type rr = r[n];
+    assert(rr == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s+5), 4, '1');
+    test(random_access_iterator<const char*>(s+5), 0, '5');
+    test(s+5, 4, '1');
+    test(s+5, 0, '5');
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.elem/dereference.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// reference operator*() const; // constexpr in C++17
+
+// Be sure to respect LWG 198:
+//    http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#198
+// LWG 198 was superseded by LWG 2360
+//    http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2360
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+
+class A
+{
+    int data_;
+public:
+    A() : data_(1) {}
+    ~A() {data_ = -1;}
+
+    friend bool operator==(const A& x, const A& y)
+        {return x.data_ == y.data_;}
+};
+
+template <class It>
+void
+test(It i, typename std::iterator_traits<It>::value_type x)
+{
+    std::_AlgRevIter<It> r(i);
+    assert(*r == x);
+}
+
+int main(int, char**)
+{
+    A a;
+    test(&a+1, A());
+
+#if TEST_STD_VER > 14
+    {
+        constexpr const char *p = "123456789";
+        typedef std::_AlgRevIter<const char *> RI;
+        constexpr RI it1 = std::_AlgRevIter(p+1);
+        constexpr RI it2 = std::_AlgRevIter(p+2);
+        static_assert(*it1 == p[0], "");
+        static_assert(*it2 == p[1], "");
+    }
+#endif
+
+  return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/decrement-assign.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// requires RandomAccessIterator<Iter>
+// _AlgRevIter& operator-=(difference_type n); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, typename std::iterator_traits<It>::difference_type n, It x) {
+    std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It>& rr = r -= n;
+    assert(r.base() == x);
+    assert(&rr == &r);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s+5), 5, random_access_iterator<const char*>(s+10));
+    test(s+5, 5, s+10);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/increment-assign.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// requires RandomAccessIterator<Iter>
+// _AlgRevIter& operator+=(difference_type n); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, typename std::iterator_traits<It>::difference_type n, It x) {
+    std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It>& rr = r += n;
+    assert(r.base() == x);
+    assert(&rr == &r);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    char const* s = "1234567890";
+    test(random_access_iterator<const char*>(s+5), 5, random_access_iterator<const char*>(s));
+    test(s+5, 5, s);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/minus.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// requires RandomAccessIterator<Iter>
+// _AlgRevIter operator-(difference_type n) const; // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, typename std::iterator_traits<It>::difference_type n, It x) {
+    const std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It> rr = r - n;
+    assert(rr.base() == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s+5), 5, random_access_iterator<const char*>(s+10));
+    test(s+5, 5, s+10);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/plus.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// requires RandomAccessIterator<Iter>
+// _AlgRevIter operator+(difference_type n) const; // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, typename std::iterator_traits<It>::difference_type n, It x) {
+    const std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It> rr = r + n;
+    assert(rr.base() == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "1234567890";
+    test(random_access_iterator<const char*>(s+5), 5, random_access_iterator<const char*>(s));
+    test(s+5, 5, s);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/postdecrement.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// _AlgRevIter operator--(int); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, It x) {
+    std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It> rr = r--;
+    assert(r.base() == x);
+    assert(rr.base() == i);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "123";
+    test(bidirectional_iterator<const char*>(s+1), bidirectional_iterator<const char*>(s+2));
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s+2));
+    test(s+1, s+2);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/postincrement.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// _AlgRevIter operator++(int); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, It x) {
+    std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It> rr = r++;
+    assert(r.base() == x);
+    assert(rr.base() == i);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "123";
+    test(bidirectional_iterator<const char*>(s+1), bidirectional_iterator<const char*>(s));
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s));
+    test(s+1, s);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/predecrement.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// _AlgRevIter& operator--(); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, It x) {
+    std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It>& rr = --r;
+    assert(r.base() == x);
+    assert(&rr == &r);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "123";
+    test(bidirectional_iterator<const char*>(s+1), bidirectional_iterator<const char*>(s+2));
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s+2));
+    test(s+1, s+2);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nav/preincrement.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// _AlgRevIter& operator++(); // constexpr in C++17
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+TEST_CONSTEXPR_CXX17 void test(It i, It x) {
+    std::_AlgRevIter<It> r(i);
+    std::_AlgRevIter<It>& rr = ++r;
+    assert(r.base() == x);
+    assert(&rr == &r);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    const char* s = "123";
+    test(bidirectional_iterator<const char*>(s+1), bidirectional_iterator<const char*>(s));
+    test(random_access_iterator<const char*>(s+1), random_access_iterator<const char*>(s));
+    test(s+1, s);
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/reverse.iter.nonmember/minus.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// template <RandomAccessIterator Iter1, RandomAccessIterator Iter2>
+//   requires HasMinus<Iter2, Iter1>
+// auto operator-(const _AlgRevIter<Iter1>& x, const _AlgRevIter<Iter2>& y) // constexpr in C++17
+//  -> decltype(y.base() - x.base());
+
+#include <iterator>
+#include <cstddef>
+#include <cassert>
+#include <type_traits>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class, class, class = void> struct HasMinus : std::false_type {};
+template <class R1, class R2> struct HasMinus<R1, R2, decltype((R1() - R2(), void()))> : std::true_type {};
+
+template <class It1, class It2>
+TEST_CONSTEXPR_CXX17 void test(It1 l, It2 r, std::ptrdiff_t x) {
+    const std::_AlgRevIter<It1> r1(l);
+    const std::_AlgRevIter<It2> r2(r);
+    assert((r1 - r2) == x);
+}
+
+TEST_CONSTEXPR_CXX17 bool tests() {
+    char s[3] = {0};
+
+    // Test same base iterator type
+    test(s, s, 0);
+    test(s, s+1, 1);
+    test(s+1, s, -1);
+
+    // Test non-subtractable base iterator types
+    static_assert( HasMinus<std::_AlgRevIter<int*>, std::_AlgRevIter<int*> >::value, "");
+#if TEST_STD_VER >= 11
+    static_assert(!HasMinus<std::_AlgRevIter<int*>, std::_AlgRevIter<char*> >::value, "");
+#endif
+
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+#if TEST_STD_VER > 14
+    static_assert(tests(), "");
+#endif
+    return 0;
+}

libcxx/test/libcxx/iterators/predef.iterators/_AlgRevIter/types.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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// _AlgRevIter
+
+// Test nested types and data member:
+
+// template <BidirectionalIterator Iter>
+// class _AlgRevIter {
+// protected:
+//   Iter current;
+// public:
+//   iterator<typename iterator_traits<Iterator>::iterator_category,
+//   typename iterator_traits<Iterator>::value_type,
+//   typename iterator_traits<Iterator>::difference_type,
+//   typename iterator_traits<Iterator>::pointer,
+//   typename iterator_traits<Iterator>::reference> {
+// };
+
+#include <iterator>
+#include <type_traits>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+void test() {
+  typedef std::_AlgRevIter<It> R;
+  typedef std::iterator_traits<It> T;
+  static_assert((std::is_same<typename R::iterator_type, It>::value), "");
+  static_assert((std::is_same<typename R::value_type, typename T::value_type>::value), "");
+  static_assert((std::is_same<typename R::difference_type, typename T::difference_type>::value), "");
+  static_assert((std::is_same<typename R::reference, typename T::reference>::value), "");
+  static_assert((std::is_same<typename R::pointer, typename std::iterator_traits<It>::pointer>::value), "");
+
+#if TEST_STD_VER <= 14
+  typedef std::iterator<typename T::iterator_category, typename T::value_type> iterator_base;
+  static_assert((std::is_base_of<iterator_base, R>::value), "");
+#endif
+#if TEST_STD_VER > 17
+  if constexpr (std::is_same_v<typename T::iterator_category, std::contiguous_iterator_tag>) {
+    static_assert((std::is_same<typename R::iterator_category, std::random_access_iterator_tag>::value), "");
+  } else {
+    static_assert((std::is_same<typename R::iterator_category, typename T::iterator_category>::value), "");
+  }
+#else
+  static_assert((std::is_same<typename R::iterator_category, typename T::iterator_category>::value), "");
+#endif
+}
+
+#if TEST_STD_VER > 17
+
+struct FooIter {
+  using iterator_category = std::bidirectional_iterator_tag;
+  using value_type = void*;
+  using difference_type = void*;
+  using pointer = void*;
+  using reference = int&;
+  int& operator*() const;
+};
+template <>
+struct std::indirectly_readable_traits<FooIter> {
+  using value_type = int;
+};
+template <>
+struct std::incrementable_traits<FooIter> {
+  using difference_type = char;
+};
+
+// Not using `FooIter::value_type`.
+static_assert(std::is_same_v<typename std::_AlgRevIter<FooIter>::value_type, int>);
+// Not using `FooIter::difference_type`.
+static_assert(std::is_same_v<typename std::_AlgRevIter<FooIter>::difference_type, char>);
+
+#endif
+
+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::_AlgRevIter<BarIter>::reference, bool&>);
+#else
+  static_assert(std::is_same<typename std::_AlgRevIter<BarIter>::reference, char&>::value, "");
+#endif
+
+void test_all() {
+  test<bidirectional_iterator<char*> >();
+  test<random_access_iterator<char*> >();
+  test<char*>();
+}