[libc++][ranges] Implement `ranges::rotate`.

[var-const]

Summary

Also fix ranges::stable_sort and ranges::inplace_merge to support
proxy iterators now that their internal implementations can correctly
dispatch rotate.

[var-const]

Use the actual patch number.

[var-const]

Undo unnecessary change, fix the CI.

libcxx/include/__algorithm/algorithm_family.h

6

While swap_ranges is a very simple algorithm, the range version and the classic version take a different number of parameters (the range version takes __last2 as well). I can try unifying them but not sure if it's worth pursuing.

libcxx/include/__algorithm/move.h

114

The changes to move.h and move_backward.h are essentially to pass around _AlgPolicy to be able to call _IterOps::__iter_move instead of plain std::move(*iter).

libcxx/include/__algorithm/ranges_move.h

39

Now that we dispatch to iter_move, I think it should take care of this case.

libcxx/include/__algorithm/rotate.h

202

The sentinel has to be converted into an iterator early in the call stack to accommodate for the early returns below. This simplifies the other internal functions in this file significantly because they can still accept __last as an iterator and return the same type.

libcxx/include/__iterator/reverse_iterator.h

397

The lack of iter_move was caught by the robust_against_proxy_iterators tests in the implementation of inplace_merge.

[var-const]

Mark the new test as unsupported pre-C++20.

[ldionne]

libcxx/include/__algorithm/algorithm_family.h

0

Doesn't it become possible to remove this entirely now that __move accepts a _AlgPolicy? I guess we'd have to also accept an _AlgPolicy in __swap_ranges, and then we can get rid of this and use __swap_ranges<_AlgPolicy> and __move<_AlgPolicy> instead?

1–2

Non blocking, but I don't understand the purpose of this TODO. Isn't that already the case with __move right above?

libcxx/include/__algorithm/rotate.h

191

Why not do class _IterCategory = _IterOps<_AlgPolicy>::__iterator_category since you added it to _IterOps? Then it doesn't need to be passed explicitly when calling __rotate from rotate(), but also from ranges::rotate and from inplace_merge.

In fact, I think you can straight up just call __rotate_impl with the category without even making it a template argument of __rotate.

205–206

Couldn't we instead return _Ret(__last_iter, __last_iter)? That would save us from advancing the iterator all the way to __last twice.

[var-const]

Address feedback, fix the CI.

libcxx/include/__algorithm/algorithm_family.h

0

Done. Also made ranges::swap_ranges delegate to the internal function.

(I originally hesitated to do that because the ranges and classic versions of swap_ranges take a different number of arguments, but it was easy to accommodate for)

1–2

Thanks for flagging this, this has encouraged me to dig a little more and now it looks like the return value is equivalent; removed the TODO.

Most of the time, the range algorithm returns the same iterator value as the classic algorithm plus an additional value (very often the last iterator); for example, the classic version would return out + N, whereas the ranges version would return {last, out + N}. Thus, it's trivial to convert the ranges result type to classic by simply dropping a value.

In this case, however, the return value is specified differently -- classic version returns last2 and the range version returns first2 + M, where M is defined as min(last1 - first1, last2 - first2). I do think, however, that the two are actually equivalent.

[var-const]

Rebase on main.

[var-const]

Fix the CI.

[var-const]

Rebase on main.

[var-const]

Rebase on main.

[var-const]

Restart CI.

libcxx/docs/Status/RangesAlgorithms.csv

 Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅
 Merge,set_difference,Hui Xie,`D128983 <https://llvm.org/D128983>`_,✅
 Merge,set_intersection,Hui Xie,`D129233 <https://llvm.org/D129233>`_,✅
 Merge,set_symmetric_difference,Hui Xie,`D129520 <https://llvm.org/D129520>`_,✅
 Merge,set_union,Hui Xie,`D129657 <https://llvm.org/D129657>`_,✅
 Permutation,remove,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
-Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review
+Permutation,rotate,Konstantin Varlamov and Nikolas Klauser,`D130758 <https://llvm.org/D130758>`_,✅
 Permutation,shuffle,Konstantin Varlamov,`D130321 <https://llvm.org/D130321>`_,✅
 Permutation,unique,Hui Xie,`D130404 <https://llvm.org/D130404>`,✅
 Permutation,partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
 Permutation,stable_partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
 Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅
 Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅
 Permutation,nth_element,Konstantin Varlamov,`D128149 <https://llvm.org/D128149>`_,✅
 Permutation,partial_sort,Konstantin Varlamov,`D128744 <https://llvm.org/D128744>`_,✅

libcxx/include/CMakeLists.txt

 set(files
   __algorithm/adjacent_find.h
-  __algorithm/algorithm_family.h
   __algorithm/all_of.h
   __algorithm/any_of.h
   __algorithm/binary_search.h
   __algorithm/clamp.h
   __algorithm/comp.h
   __algorithm/comp_ref_type.h
   __algorithm/copy.h
   __algorithm/copy_backward.h
set(files
   __algorithm/ranges_remove_copy_if.h
   __algorithm/ranges_remove_if.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_copy.h
   __algorithm/ranges_replace_copy_if.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_reverse_copy.h
+  __algorithm/ranges_rotate.h
   __algorithm/ranges_rotate_copy.h
   __algorithm/ranges_search.h
   __algorithm/ranges_search_n.h
   __algorithm/ranges_set_difference.h
   __algorithm/ranges_set_intersection.h
   __algorithm/ranges_set_symmetric_difference.h
   __algorithm/ranges_set_union.h
   __algorithm/ranges_shuffle.h

libcxx/include/__algorithm/algorithm_family.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_ALGORITHM_FAMILY_H
-#define _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H
-
-#include <__algorithm/iterator_operations.h>
-#include <__algorithm/move.h>
-#include <__algorithm/ranges_move.h>
-#include <__config>
-#include <__utility/move.h>
-
-#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
-#  pragma GCC system_header
-#endif
-
-_LIBCPP_BEGIN_NAMESPACE_STD
-
-template <class _AlgPolicy>
-struct _AlgFamily;
-
-#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
-
-template <>
-struct _AlgFamily<_RangeAlgPolicy> {
-  static constexpr auto __move = ranges::move;
-};
-
-#endif
-
-template <>
-struct _AlgFamily<_ClassicAlgPolicy> {
-
-  // move
-  template <class _InputIterator, class _OutputIterator>
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 static _OutputIterator
-  __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
-    return std::move(
-        std::move(__first),
-        std::move(__last),
-        std::move(__result));
-  }
-};
-
-_LIBCPP_END_NAMESPACE_STD
-
-#endif // _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H

libcxx/include/__algorithm/inplace_merge.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_INPLACE_MERGE_H
 #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H
 
-#include <__algorithm/algorithm_family.h>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/upper_bound.h>

 void __half_inplace_merge(_InputIterator1 __first1, _Sent1 __last1,
                           _InputIterator2 __first2, _Sent2 __last2,
                           _OutputIterator __result, _Compare&& __comp)
 {
     for (; __first1 != __last1; ++__result)
     {
         if (__first2 == __last2)
         {
-            _AlgFamily<_AlgPolicy>::__move(__first1, __last1, __result);
+            std::__move<_AlgPolicy>(__first1, __last1, __result);
             return;
         }
 
         if (__comp(*__first2, *__first1))
         {
             *__result = _IterOps<_AlgPolicy>::__iter_move(__first2);
             ++__first2;
         }
while (true)
             _Ops::advance(__m1, __len11);
             __m2 = std::lower_bound(__middle, __last, *__m1, __comp);
             __len21 = _Ops::distance(__middle, __m2);
         }
         difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
         // swap middle two partitions
-        // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`.
-        __middle = _VSTD::rotate(__m1, __middle, __m2);
+        __middle = std::__rotate<_AlgPolicy>(__m1, __middle, __m2).first;
         // __len12 and __len21 now have swapped meanings
         // merge smaller range with recursive call and larger with tail recursion elimination
         if (__len11 + __len21 < __len12 + __len22)
         {
             std::__inplace_merge<_AlgPolicy>(
                 __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
             __first = __middle;
             __middle = __m2;

libcxx/include/__algorithm/iterator_operations.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_ITERATOR_OPERATIONS_H
 #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
 
 #include <__algorithm/iter_swap.h>
+#include <__algorithm/ranges_iterator_concept.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
+#include <__iterator/prev.h>
 #include <__iterator/readable_traits.h>
 #include <__utility/declval.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _AlgPolicy> struct _IterOps;
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 struct _RangeAlgPolicy {};
 
 template <>
 struct _IterOps<_RangeAlgPolicy> {
 
   template <class _Iter>
   using __value_type = iter_value_t<_Iter>;
 
+  template <class _Iter>
+  using __iterator_category = decltype(ranges::__iterator_concept<_Iter>());
+
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
   static constexpr auto __iter_move = ranges::iter_move;
   static constexpr auto iter_swap = ranges::iter_swap;
   static constexpr auto next = ranges::next;
+  static constexpr auto prev = ranges::prev;
   static constexpr auto __advance_to = ranges::advance;
 };
 
 #endif
 
 struct _ClassicAlgPolicy {};
 
 template <>
 struct _IterOps<_ClassicAlgPolicy> {
 
   template <class _Iter>
   using __value_type = typename iterator_traits<_Iter>::value_type;
 
+  template <class _Iter>
+  using __iterator_category = typename iterator_traits<_Iter>::iterator_category;
+
   // advance
   template <class _Iter, class _Distance>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
   static void advance(_Iter& __iter, _Distance __count) {
     std::advance(__iter, __count);
   }
 
   // distance
struct _IterOps<_ClassicAlgPolicy> {
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   _Iterator next(_Iterator, _Iterator __last) {
     return __last;
   }
 
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   __uncvref_t<_Iter> next(_Iter&& __it,
-                          typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1){
+                          typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1) {
     return std::next(std::forward<_Iter>(__it), __n);
   }
 
+  // prev
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  __uncvref_t<_Iter> prev(_Iter&& __iter,
+                 typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1) {
+    return std::prev(std::forward<_Iter>(__iter), __n);
+  }
+
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   void __advance_to(_Iter& __first, _Iter __last) {
     __first = __last;
   }
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H

libcxx/include/__algorithm/move.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_MOVE_H
 #define _LIBCPP___ALGORITHM_MOVE_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <cstring>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // move
 
-template <class _InIter, class _Sent, class _OutIter>
+template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) {
   while (__first != __last) {
-    *__result = std::move(*__first);
+    *__result = _IterOps<_AlgPolicy>::__iter_move(__first);
     ++__first;
     ++__result;
   }
   return std::make_pair(std::move(__first), std::move(__result));
 }
 
-template <class _InType,
+template <class _AlgPolicy,
+          class _InType,
           class _OutType,
           class = __enable_if_t<is_same<typename remove_const<_InType>::type, _OutType>::value
                              && is_trivially_move_assignable<_OutType>::value> >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_InType*, _OutType*> __move_impl(_InType* __first, _InType* __last, _OutType* __result) {
   if (__libcpp_is_constant_evaluated()
 // TODO: Remove this once GCC supports __builtin_memmove during constant evaluation
 #ifndef _LIBCPP_COMPILER_GCC
    && !is_trivially_copyable<_InType>::value
 #endif
      )
-    return std::__move_impl<_InType*, _InType*, _OutType*>(__first, __last, __result);
+    return std::__move_impl<_AlgPolicy, _InType*, _InType*, _OutType*>(__first, __last, __result);
   const size_t __n = static_cast<size_t>(__last - __first);
   ::__builtin_memmove(__result, __first, __n * sizeof(_OutType));
   return std::make_pair(__first + __n, __result + __n);
 }
 
 template <class>
 struct __is_trivially_move_assignable_unwrapped_impl : false_type {};
 
 template <class _Type>
 struct __is_trivially_move_assignable_unwrapped_impl<_Type*> : is_trivially_move_assignable<_Type> {};
 
 template <class _Iter>
 struct __is_trivially_move_assignable_unwrapped
     : __is_trivially_move_assignable_unwrapped_impl<decltype(std::__unwrap_iter<_Iter>(std::declval<_Iter>()))> {};
 
-template <class _InIter,
+template <class _AlgPolicy,
+          class _InIter,
           class _OutIter,
           __enable_if_t<is_same<typename remove_const<typename iterator_traits<_InIter>::value_type>::type,
                                 typename iterator_traits<_OutIter>::value_type>::value
                      && __is_cpp17_contiguous_iterator<_InIter>::value
                      && __is_cpp17_contiguous_iterator<_OutIter>::value
                      && is_trivially_move_assignable<__iter_value_type<_OutIter> >::value, int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14
 pair<reverse_iterator<_InIter>, reverse_iterator<_OutIter> >
 __move_impl(reverse_iterator<_InIter> __first,
             reverse_iterator<_InIter> __last,
             reverse_iterator<_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::__move_impl(__last_base, __first_base, __result_first);
+  std::__move_impl<_AlgPolicy>(__last_base, __first_base, __result_first);
   return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first)));
 }
 
-template <class _InIter, class _Sent, class _OutIter>
+template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 __enable_if_t<is_copy_constructible<_InIter>::value
            && is_copy_constructible<_Sent>::value
            && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
 __move(_InIter __first, _Sent __last, _OutIter __result) {
-  auto __ret = std::__move_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result));
+  auto __ret = std::__move_impl<_AlgPolicy>(
+      std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result));
   return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 
-template <class _InIter, class _Sent, class _OutIter>
+template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 __enable_if_t<!is_copy_constructible<_InIter>::value
            || !is_copy_constructible<_Sent>::value
            || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
 __move(_InIter __first, _Sent __last, _OutIter __result) {
-  return std::__move_impl(std::move(__first), std::move(__last), std::move(__result));
+  return std::__move_impl<_AlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
-  return std::__move(__first, __last, __result).second;
+  return std::__move<_ClassicAlgPolicy>(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MOVE_H

libcxx/include/__algorithm/move_backward.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_MOVE_BACKWARD_H
 #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__utility/move.h>
 #include <cstring>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _InputIterator, class _OutputIterator>
+template <class _AlgPolicy, class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 _OutputIterator
 __move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     while (__first != __last)
-        *--__result = _VSTD::move(*--__last);
+        *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last);
     return __result;
 }
 
-template <class _InputIterator, class _OutputIterator>
+template <class _AlgPolicy, class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 _OutputIterator
-__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+__move_backward_impl(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
-    return _VSTD::__move_backward_constexpr(__first, __last, __result);
+    return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result);
 }
 
-template <class _Tp, class _Up>
+template <class _AlgPolicy, class _Tp, class _Up>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename enable_if
 <
     is_same<typename remove_const<_Tp>::type, _Up>::value &&
     is_trivially_move_assignable<_Up>::value,
     _Up*
 >::type
-__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
+__move_backward_impl(_Tp* __first, _Tp* __last, _Up* __result)
 {
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
     {
         __result -= __n;
         _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     }
     return __result;
 }
 
-template <class _BidirectionalIterator1, class _BidirectionalIterator2>
+template <class _AlgPolicy, class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _BidirectionalIterator2
-move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
+__move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
                 _BidirectionalIterator2 __result)
 {
     if (__libcpp_is_constant_evaluated()) {
-        return _VSTD::__move_backward_constexpr(__first, __last, __result);
+        return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result);
     } else {
         return _VSTD::__rewrap_iter(__result,
-            _VSTD::__move_backward(_VSTD::__unwrap_iter(__first),
+            _VSTD::__move_backward_impl<_AlgPolicy>(_VSTD::__unwrap_iter(__first),
                                                     _VSTD::__unwrap_iter(__last),
                                                     _VSTD::__unwrap_iter(__result)));
     }
 }
 
+template <class _BidirectionalIterator1, class _BidirectionalIterator2>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_BidirectionalIterator2
+move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
+              _BidirectionalIterator2 __result)
+{
+  return std::__move_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MOVE_BACKWARD_H

libcxx/include/__algorithm/ranges_move.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_RANGES_MOVE_H
 #define _LIBCPP___ALGORITHM_RANGES_MOVE_H
 
 #include <__algorithm/in_out_result.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/move.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iter_move.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/move.h>

 
 template <class _InIter, class _OutIter>
 using move_result = in_out_result<_InIter, _OutIter>;
 
 namespace __move {
 struct __fn {
 
   template <class _InIter, class _Sent, class _OutIter>
-    requires __iter_move::__move_deref<_InIter> // check that we are allowed to std::move() the value
   _LIBCPP_HIDE_FROM_ABI constexpr static
   move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) {
-    auto __ret = std::__move(std::move(__first), std::move(__last), std::move(__result));
+    auto __ret = std::__move<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
     return {std::move(__ret.first), std::move(__ret.second)};
   }
 
-  template <class _InIter, class _Sent, class _OutIter>
-  _LIBCPP_HIDE_FROM_ABI constexpr static
-  move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) {
-    while (__first != __last) {
-      *__result = ranges::iter_move(__first);
-      ++__first;
-      ++__result;
-    }
-    return {std::move(__first), std::move(__result)};
-  }
-
   template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter>
     requires indirectly_movable<_InIter, _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr
   move_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     return __move_impl(std::move(__first), std::move(__last), std::move(__result));
   }
 
   template <input_range _Range, weakly_incrementable _OutIter>

libcxx/include/__algorithm/ranges_rotate.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_RANGES_ROTATE_H
+#define _LIBCPP___ALGORITHM_RANGES_ROTATE_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/ranges_iterator_concept.h>
+#include <__algorithm/rotate.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/permutable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/subrange.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __rotate {
+
+struct __fn {
+
+  template <class _Iter, class _Sent>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  static subrange<_Iter> __rotate_fn_impl(_Iter __first, _Iter __middle, _Sent __last) {
+    auto __ret = std::__rotate<_RangeAlgPolicy>(
+      std::move(__first), std::move(__middle), std::move(__last));
+    return {std::move(__ret.first), std::move(__ret.second)};
+  }
+
+  template <permutable _Iter, sentinel_for<_Iter> _Sent>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  subrange<_Iter> operator()(_Iter __first, _Iter __middle, _Sent __last) const {
+    return __rotate_fn_impl(std::move(__first), std::move(__middle), std::move(__last));
+  }
+
+  template <forward_range _Range>
+  requires permutable<iterator_t<_Range>>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_subrange_t<_Range> operator()(_Range&& __range, iterator_t<_Range> __middle) const {
+    return __rotate_fn_impl(ranges::begin(__range), std::move(__middle), ranges::end(__range));
+  }
+
+};
+
+} // namespace __rotate
+
+inline namespace __cpo {
+  inline constexpr auto rotate = __rotate::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_ROTATE_H

libcxx/include/__algorithm/ranges_swap_ranges.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_RANGES_SWAP_RANGES_H
 #define _LIBCPP___ALGORITHM_RANGES_SWAP_RANGES_H
 
 #include <__algorithm/in_in_result.h>
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/swap_ranges.h>
 #include <__config>
 #include <__iterator/concepts.h>
-#include <__iterator/iter_swap.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

 
 namespace __swap_ranges {
 struct __fn {
   template <input_iterator _I1, sentinel_for<_I1> _S1,
             input_iterator _I2, sentinel_for<_I2> _S2>
     requires indirectly_swappable<_I1, _I2>
   _LIBCPP_HIDE_FROM_ABI constexpr swap_ranges_result<_I1, _I2>
   operator()(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2) const {
-    while (__first1 != __last1 && __first2 != __last2) {
-      ranges::iter_swap(__first1, __first2);
-      ++__first1;
-      ++__first2;
-    }
-    return {_VSTD::move(__first1), _VSTD::move(__first2)};
+    auto __ret = std::__swap_ranges<_RangeAlgPolicy>(
+        std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2));
+    return {std::move(__ret.first), std::move(__ret.second)};
   }
 
   template <input_range _R1, input_range _R2>
     requires indirectly_swappable<iterator_t<_R1>, iterator_t<_R2>>
   _LIBCPP_HIDE_FROM_ABI constexpr
   swap_ranges_result<borrowed_iterator_t<_R1>, borrowed_iterator_t<_R2>>
   operator()(_R1&& __r1, _R2&& __r2) const {
     return operator()(ranges::begin(__r1), ranges::end(__r1),

libcxx/include/__algorithm/rotate.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_ROTATE_H
 #define _LIBCPP___ALGORITHM_ROTATE_H
 
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/move.h>
 #include <__algorithm/move_backward.h>
 #include <__algorithm/swap_ranges.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__iterator/next.h>
-#include <__iterator/prev.h>
 #include <__utility/move.h>
-#include <__utility/swap.h>
+#include <__utility/pair.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _AlgPolicy, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
-    value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__first);
-    // TODO(ranges): pass `_AlgPolicy` to `move`.
-    _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
+    using _Ops = _IterOps<_AlgPolicy>;
+
+    value_type __tmp = _Ops::__iter_move(__first);
+    _ForwardIterator __lm1 = std::__move<_AlgPolicy>(
+        _Ops::next(__first), __last, __first).second;
     *__lm1 = _VSTD::move(__tmp);
     return __lm1;
 }
 
 template <class _AlgPolicy, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
-    // TODO(ranges): pass `_AlgPolicy` to `prev`.
-    _BidirectionalIterator __lm1 = _VSTD::prev(__last);
-    value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__lm1);
-    // TODO(ranges): pass `_AlgPolicy` to `move_backward`.
-    _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
+    using _Ops = _IterOps<_AlgPolicy>;
+
+    _BidirectionalIterator __lm1 = _Ops::prev(__last);
+    value_type __tmp = _Ops::__iter_move(__lm1);
+    _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last));
     *__first = _VSTD::move(__tmp);
     return __fp1;
 }
 
 template <class _AlgPolicy, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator
 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {

 }
 
 template <class _AlgPolicy, typename _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+    using _Ops = _IterOps<_AlgPolicy>;
 
     const difference_type __m1 = __middle - __first;
-    const difference_type __m2 = __last - __middle;
+    const difference_type __m2 = _Ops::distance(__middle, __last);
     if (__m1 == __m2)
     {
-        // TODO(ranges): pass `_AlgPolicy` to `swap_ranges`.
-        _VSTD::swap_ranges(__first, __middle, __middle);
+        std::__swap_ranges<_AlgPolicy>(__first, __middle, __middle, __last);
         return __middle;
     }
     const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
     {
-        value_type __t(_IterOps<_AlgPolicy>::__iter_move(--__p));
+        value_type __t(_Ops::__iter_move(--__p));
         _RandomAccessIterator __p1 = __p;
         _RandomAccessIterator __p2 = __p1 + __m1;
         do
         {
-            *__p1 = _IterOps<_AlgPolicy>::__iter_move(__p2);
+            *__p1 = _Ops::__iter_move(__p2);
             __p1 = __p2;
-            const difference_type __d = __last - __p2;
+            const difference_type __d = _Ops::distance(__p2, __last);
             if (__m1 < __d)
                 __p2 += __m1;
             else
                 __p2 = __first + (__m1 - __d);
         } while (__p2 != __p);
         *__p1 = _VSTD::move(__t);
     }
     return __first + __m2;
if (is_trivially_move_assignable<value_type>::value)
             return std::__rotate_left<_AlgPolicy>(__first, __last);
         if (_IterOps<_AlgPolicy>::next(__middle) == __last)
             return std::__rotate_right<_AlgPolicy>(__first, __last);
         return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);
     }
     return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
 }
 
-template <class _AlgPolicy, class _RandomAccessIterator, class _IterCategory>
+template <class _AlgPolicy, class _Iterator, class _Sentinel>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-_RandomAccessIterator __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle,
-    _RandomAccessIterator __last, _IterCategory __iter_category) {
+pair<_Iterator, _Iterator>
+__rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) {
+  using _Ret = pair<_Iterator, _Iterator>;
+  _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last);
+
   if (__first == __middle)
-      return __last;
+      return _Ret(__last_iter, __last_iter);
   if (__middle == __last)
-      return __first;
+      return _Ret(std::move(__first), std::move(__last_iter));
+
+  using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>;
+  auto __result = std::__rotate_impl<_AlgPolicy>(
+      std::move(__first), std::move(__middle), __last_iter, _IterCategory());
 
-  return std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __iter_category);
+  return _Ret(std::move(__result), std::move(__last_iter));
 }
 
 template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
-  return std::__rotate<_ClassicAlgPolicy>(__first, __middle, __last,
-                                          typename iterator_traits<_ForwardIterator>::iterator_category());
+  return std::__rotate<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__middle), std::move(__last)).first;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_ROTATE_H

libcxx/include/__algorithm/stable_partition.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
 //
 //===----------------------------------------------------------------------===//
 
__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
     }
     // TTTFFFFFTTTF??????
     // f  ff   m  m1     l
     __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
         __m1, __last, __pred, __len_half, __p, __fit);
 __second_half_done:
     // TTTFFFFFTTTTTFFFFF
     // f  ff   m    sf   l
-    return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false, __fit);
+    return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
     // TTTTTTTTFFFFFFFFFF
     //         |
 }
 
 template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
 _ForwardIterator
 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
                    forward_iterator_tag)
__first_half_done:
     }
     // TTTFFFFFTTTF?????T
     // f  ff   m  m1    l
     __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
         __m1, __last, __pred, __len_half, __p, __bit);
 __second_half_done:
     // TTTFFFFFTTTTTFFFFF
     // f  ff   m    sf  l
-    return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false, __bit);
+    return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first;
     // TTTTTTTTFFFFFFFFFF
     //         |
 }
 
 template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
 _BidirectionalIterator
 __stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
                    bidirectional_iterator_tag)

libcxx/include/__algorithm/swap_ranges.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_SWAP_RANGES_H
 #define _LIBCPP___ALGORITHM_SWAP_RANGES_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__config>
-#include <__utility/swap.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+// 2+2 iterators: the shorter size will be used.
+template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _Sentinel2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+pair<_ForwardIterator1, _ForwardIterator2>
+__swap_ranges(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, _Sentinel2 __last2) {
+  while (__first1 != __last1 && __first2 != __last2) {
+    _IterOps<_AlgPolicy>::iter_swap(__first1, __first2);
+    ++__first1;
+    ++__first2;
+  }
+
+  return pair<_ForwardIterator1, _ForwardIterator2>(std::move(__first1), std::move(__first2));
+}
+
+// 2+1 iterators: size2 >= size1.
+template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+pair<_ForwardIterator1, _ForwardIterator2>
+__swap_ranges(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2) {
+  while (__first1 != __last1) {
+    _IterOps<_AlgPolicy>::iter_swap(__first1, __first2);
+    ++__first1;
+    ++__first2;
+  }
+
+  return pair<_ForwardIterator1, _ForwardIterator2>(std::move(__first1), std::move(__first2));
+}
+
 template <class _ForwardIterator1, class _ForwardIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator2
 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) {
-  for (; __first1 != __last1; ++__first1, (void)++__first2)
-    swap(*__first1, *__first2);
-  return __first2;
+  return std::__swap_ranges<_ClassicAlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SWAP_RANGES_H

libcxx/include/__iterator/reverse_iterator.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//

 // 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.
 template <class _Iter>
 class __unconstrained_reverse_iterator {
   _Iter __iter_;
 
 public:
-  static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value);
+  static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value || bidirectional_iterator<_Iter>);
 
   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>;
public:
   _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 friend constexpr
+  iter_rvalue_reference_t<_Iter> iter_move(const __unconstrained_reverse_iterator& __i)
+    noexcept(is_nothrow_copy_constructible_v<_Iter> &&
+        noexcept(ranges::iter_move(--declval<_Iter&>()))) {
+    auto __tmp = __i.base();
+    return ranges::iter_move(--__tmp);
+  }
+
   _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator++() {
     --__iter_;
     return *this;
   }
 
   _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator++(int) {
     auto __tmp = *this;
     --__iter_;

libcxx/include/algorithm

template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
     constexpr ranges::reverse_copy_result<I, O>
       ranges::reverse_copy(I first, S last, O result);                                              // since C++20
 
   template<bidirectional_range R, weakly_incrementable O>
     requires indirectly_copyable<iterator_t<R>, O>
     constexpr ranges::reverse_copy_result<borrowed_iterator_t<R>, O>
       ranges::reverse_copy(R&& r, O result);                                                        // since C++20
 
+  template<permutable I, sentinel_for<I> S>
+    constexpr subrange<I> rotate(I first, I middle, S last);                                        // since C++20
+
+  template<forward_range R>
+    requires permutable<iterator_t<R>>
+    constexpr borrowed_subrange_t<R> rotate(R&& r, iterator_t<R> middle);                           // Since C++20
+
   template <class _InIter, class _OutIter>
   using rotate_copy_result = in_out_result<_InIter, _OutIter>;                                      // since C++20
 
   template<forward_iterator I, sentinel_for<I> S, weakly_incrementable O>
     requires indirectly_copyable<I, O>
     constexpr ranges::rotate_copy_result<I, O>
       ranges::rotate_copy(I first, I middle, S last, O result);                                     // since C++20
 

 #include <__algorithm/ranges_pop_heap.h>
 #include <__algorithm/ranges_push_heap.h>
 #include <__algorithm/ranges_remove.h>
 #include <__algorithm/ranges_remove_if.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_reverse_copy.h>
+#include <__algorithm/ranges_rotate.h>
 #include <__algorithm/ranges_rotate_copy.h>
 #include <__algorithm/ranges_search.h>
 #include <__algorithm/ranges_search_n.h>
 #include <__algorithm/ranges_set_difference.h>
 #include <__algorithm/ranges_set_intersection.h>
 #include <__algorithm/ranges_set_symmetric_difference.h>
 #include <__algorithm/ranges_set_union.h>
 #include <__algorithm/ranges_shuffle.h>

libcxx/include/module.modulemap.in

module std [system] {
 
   module algorithm {
     header "algorithm"
     export initializer_list
     export *
 
     module __algorithm {
       module adjacent_find                   { private header "__algorithm/adjacent_find.h" }
-      module algorithm_family                { private header "__algorithm/algorithm_family.h" }
       module all_of                          { private header "__algorithm/all_of.h" }
       module any_of                          { private header "__algorithm/any_of.h" }
       module binary_search                   { private header "__algorithm/binary_search.h" }
       module clamp                           { private header "__algorithm/clamp.h" }
       module comp                            { private header "__algorithm/comp.h" }
       module comp_ref_type                   { private header "__algorithm/comp_ref_type.h" }
       module copy                            { private header "__algorithm/copy.h" }
       module copy_backward                   { private header "__algorithm/copy_backward.h" }
module __algorithm {
       module ranges_remove_copy_if           { private header "__algorithm/ranges_remove_copy_if.h" }
       module ranges_remove_if                { private header "__algorithm/ranges_remove_if.h" }
       module ranges_replace                  { private header "__algorithm/ranges_replace.h" }
       module ranges_replace_copy             { private header "__algorithm/ranges_replace_copy.h" }
       module ranges_replace_copy_if          { private header "__algorithm/ranges_replace_copy_if.h" }
       module ranges_replace_if               { private header "__algorithm/ranges_replace_if.h" }
       module ranges_reverse                  { private header "__algorithm/ranges_reverse.h" }
       module ranges_reverse_copy             { private header "__algorithm/ranges_reverse_copy.h" }
+      module ranges_rotate                   { private header "__algorithm/ranges_rotate.h" }
       module ranges_rotate_copy              { private header "__algorithm/ranges_rotate_copy.h" }
       module ranges_search                   { private header "__algorithm/ranges_search.h" }
       module ranges_search_n                 { private header "__algorithm/ranges_search_n.h" }
       module ranges_set_difference           { private header "__algorithm/ranges_set_difference.h" }
       module ranges_set_intersection         { private header "__algorithm/ranges_set_intersection.h" }
       module ranges_set_symmetric_difference { private header "__algorithm/ranges_set_symmetric_difference.h" }
       module ranges_set_union                { private header "__algorithm/ranges_set_union.h" }
       module ranges_shuffle                  { private header "__algorithm/ranges_shuffle.h" }

libcxx/test/libcxx/private_headers.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
 //
 //===----------------------------------------------------------------------===//
 
for header in private_headers:
   ))
 
 END-SCRIPT
 */
 
 // DO NOT MANUALLY EDIT ANYTHING BETWEEN THE MARKERS BELOW
 // GENERATED-MARKER
 #include <__algorithm/adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/adjacent_find.h'}}
-#include <__algorithm/algorithm_family.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/algorithm_family.h'}}
 #include <__algorithm/all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/all_of.h'}}
 #include <__algorithm/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/any_of.h'}}
 #include <__algorithm/binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/binary_search.h'}}
 #include <__algorithm/clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/clamp.h'}}
 #include <__algorithm/comp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/comp.h'}}
 #include <__algorithm/comp_ref_type.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/comp_ref_type.h'}}
 #include <__algorithm/copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy.h'}}
 #include <__algorithm/copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_backward.h'}}

 #include <__algorithm/ranges_remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_copy_if.h'}}
 #include <__algorithm/ranges_remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_if.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_copy.h'}}
 #include <__algorithm/ranges_replace_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_copy_if.h'}}
 #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_reverse_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse_copy.h'}}
+#include <__algorithm/ranges_rotate.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate.h'}}
 #include <__algorithm/ranges_rotate_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate_copy.h'}}
 #include <__algorithm/ranges_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search.h'}}
 #include <__algorithm/ranges_search_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search_n.h'}}
 #include <__algorithm/ranges_set_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.h'}}
 #include <__algorithm/ranges_set_intersection.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_intersection.h'}}
 #include <__algorithm/ranges_set_symmetric_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_symmetric_difference.h'}}
 #include <__algorithm/ranges_set_union.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_union.h'}}
 #include <__algorithm/ranges_shuffle.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_shuffle.h'}}

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges_rotate.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-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<permutable I, sentinel_for<I> S>
+//   constexpr subrange<I> rotate(I first, I middle, S last);                                        // since C++20
+//
+// template<forward_range R>
+//   requires permutable<iterator_t<R>>
+//   constexpr borrowed_subrange_t<R> rotate(R&& r, iterator_t<R> middle);                           // Since C++20
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+// Test constraints of the (iterator, sentinel) overload.
+// ======================================================
+
+template <class Iter = int*, class Sent = int*>
+concept HasRotateIter =
+    requires(Iter&& iter, Sent&& sent) {
+      std::ranges::rotate(std::forward<Iter>(iter), std::forward<Iter>(iter), std::forward<Sent>(sent));
+    };
+
+static_assert(HasRotateIter<int*, int*>);
+
+// !permutable<I>
+static_assert(!HasRotateIter<PermutableNotForwardIterator>);
+static_assert(!HasRotateIter<PermutableNotSwappable>);
+
+// !sentinel_for<S, I>
+static_assert(!HasRotateIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasRotateIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// Test constraints of the (range) overload.
+// =========================================
+
+template <class Range>
+concept HasRotateRange =
+    requires(Range&& range, std::ranges::iterator_t<Range> iter) {
+      std::ranges::rotate(std::forward<Range>(range), iter);
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasRotateRange<R<int*>>);
+
+// !forward_range<R>
+static_assert(!HasRotateRange<ForwardRangeNotDerivedFrom>);
+static_assert(!HasRotateRange<ForwardRangeNotIncrementable>);
+static_assert(!HasRotateRange<ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasRotateRange<ForwardRangeNotSentinelEqualityComparableWith>);
+
+// !permutable<iterator_t<R>>
+static_assert(!HasRotateRange<PermutableRangeNotForwardIterator>);
+static_assert(!HasRotateRange<PermutableRangeNotSwappable>);
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_one(const std::array<int, N> input, size_t mid_index, std::array<int, N> expected) {
+  assert(mid_index <= N);
+
+  { // (iterator, sentinel) overload.
+    auto in = input;
+    auto begin = Iter(in.data());
+    auto mid = Iter(in.data() + mid_index);
+    auto end = Sent(Iter(in.data() + in.size()));
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::rotate(begin, mid, end);
+    assert(base(result.begin()) == in.data() + in.size() - mid_index);
+    assert(base(result.end()) == in.data() + in.size());
+    assert(in == expected);
+  }
+
+  { // (range) overload.
+    auto in = input;
+    auto begin = Iter(in.data());
+    auto mid = Iter(in.data() + mid_index);
+    auto end = Sent(Iter(in.data() + in.size()));
+    auto range = std::ranges::subrange(std::move(begin), std::move(end));
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::rotate(range, mid);
+    assert(base(result.begin()) == in.data() + in.size() - mid_index);
+    assert(base(result.end()) == in.data() + in.size());
+    assert(in == expected);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iter_sent() {
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, 0, {});
+
+  // 1-element sequence.
+  test_one<Iter, Sent, 1>({1}, 0, {1});
+
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({1, 2}, 1, {2, 1});
+
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({1, 2, 3}, 1, {2, 3, 1});
+  test_one<Iter, Sent, 3>({1, 2, 3}, 2, {3, 1, 2});
+
+  // Longer sequence.
+  test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 2, {3, 4, 5, 6, 7, 1, 2});
+
+  // Rotate around the middle.
+  test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 3, {4, 5, 6, 7, 1, 2, 3});
+
+  // Rotate around the 1st element (no-op).
+  test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 0, {1, 2, 3, 4, 5, 6, 7});
+
+  // Rotate around the 2nd element.
+  test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 1, {2, 3, 4, 5, 6, 7, 1});
+
+  // Rotate around the last element.
+  test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 6, {7, 1, 2, 3, 4, 5, 6});
+
+  // Pass `end()` as `mid` (no-op).
+  test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 7, {1, 2, 3, 4, 5, 6, 7});
+}
+
+template <class Iter>
+constexpr void test_iter() {
+  test_iter_sent<Iter, Iter>();
+  test_iter_sent<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iter<forward_iterator<int*>>();
+  test_iter<bidirectional_iterator<int*>>();
+  test_iter<random_access_iterator<int*>>();
+  test_iter<contiguous_iterator<int*>>();
+  test_iter<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // Complexity: at most `last - first` swaps.
+    const std::array input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+    auto expected = static_cast<int>(input.size());
+
+    {
+      auto in = input;
+      int swaps = 0;
+      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
+      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);
+
+      for (size_t mid = 0; mid != input.size(); ++mid) {
+        std::ranges::rotate(begin, begin + mid, end);
+        assert(swaps <= expected);
+      }
+    }
+
+    {
+      auto in = input;
+      int swaps = 0;
+      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
+      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);
+      auto range = std::ranges::subrange(begin, end);
+
+      for (size_t mid = 0; mid != input.size(); ++mid) {
+        std::ranges::rotate(range, begin + mid);
+        assert(swaps <= expected);
+      }
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/ranges_robust_against_dangling.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
 //
 //===----------------------------------------------------------------------===//
 
constexpr bool test_all() {
   dangling_both<set_symmetric_difference_result<dangling, dangling, int*>>(
       std::ranges::set_symmetric_difference, in, in2, out);
   dangling_1st<set_union_result<dangling, int*, int*>>(std::ranges::set_union, in, in2, out);
   dangling_2nd<set_union_result<int*, dangling, int*>>(std::ranges::set_union, in, in2, out);
   dangling_both<set_union_result<dangling, dangling, int*>>(std::ranges::set_union, in, in2, out);
   dangling_1st(std::ranges::remove, in, x);
   dangling_1st(std::ranges::remove_if, in, unary_pred);
   dangling_1st(std::ranges::reverse, in);
-  //dangling_1st(std::ranges::rotate, in, mid);
+  dangling_1st(std::ranges::rotate, in, mid);
   if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`.
     dangling_1st(std::ranges::shuffle, in, rand_gen());
   dangling_1st(std::ranges::unique, in);
   dangling_1st(std::ranges::partition, in, unary_pred);
   if (!std::is_constant_evaluated())
     dangling_1st(std::ranges::stable_partition, in, unary_pred);
   dangling_1st(std::ranges::sort, in);
   if (!std::is_constant_evaluated())

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.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
 //
 //===----------------------------------------------------------------------===//
 
if constexpr (std::copyable<T>) {
     test(std::ranges::set_difference, in, in2, out);
     test(std::ranges::set_intersection, in, in2, out);
     test(std::ranges::set_symmetric_difference, in, in2, out);
     test(std::ranges::set_union, in, in2, out);
   }
   test(std::ranges::remove, in, x);
   test(std::ranges::remove_if, in, unary_pred);
   test(std::ranges::reverse, in);
-  //test_mid(std::ranges::rotate, in, mid);
+  test_mid(std::ranges::rotate, in, mid);
   if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`.
     test(std::ranges::shuffle, in, rand_gen());
   //if (!std::is_constant_evaluated())
   //  test(std::ranges::sample, in, out, count, rand_gen());
   test(std::ranges::unique, in);
   test(std::ranges::partition, in, unary_pred);
-  // TODO(ranges): `stable_partition` requires `ranges::rotate` to be implemented.
-  //if (!std::is_constant_evaluated())
-  // test(std::ranges::stable_partition, in, unary_pred);
+  if (!std::is_constant_evaluated())
+    test(std::ranges::stable_partition, in, unary_pred);
   test(std::ranges::sort, in);
-  // TODO(ranges): `stable_sort` requires `ranges::rotate` to be implemented.
-  //if (!std::is_constant_evaluated())
-  //  test(std::ranges::stable_sort, in);
+  if (!std::is_constant_evaluated())
+    test(std::ranges::stable_sort, in);
   test_mid(std::ranges::partial_sort, in, mid);
   test_mid(std::ranges::nth_element, in, mid);
-  // TODO(ranges): `inplace_merge` requires `ranges::rotate` to be implemented.
-  //if (!std::is_constant_evaluated())
-  //  test_mid(std::ranges::inplace_merge, in, mid);
+  if (!std::is_constant_evaluated())
+    test_mid(std::ranges::inplace_merge, in, mid);
   test(std::ranges::make_heap, in);
   test(std::ranges::push_heap, in);
   test(std::ranges::pop_heap, in);
   test(std::ranges::sort_heap, in);
   //test(std::ranges::prev_permutation, in);
   //test(std::ranges::next_permutation, in);
 
   // The algorithms that work on uninitialized memory have constraints that prevent proxy iterators from being used with

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.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
 //
 //===----------------------------------------------------------------------===//
 

 //static_assert(test(std::ranges::remove_copy_if, a, a, odd));
 static_assert(test(std::ranges::remove_if, a, odd));
 static_assert(test(std::ranges::replace, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy, a, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43));
 static_assert(test(std::ranges::replace_if, a, odd, 43));
 static_assert(test(std::ranges::reverse, a));
 static_assert(test(std::ranges::reverse_copy, a, a));
-//static_assert(test(std::ranges::rotate, a, a+5));
+static_assert(test(std::ranges::rotate, a, a+5));
 static_assert(test(std::ranges::rotate_copy, a, a+5, a));
 //static_assert(test(std::ranges::sample, a, a, 5));
 static_assert(test(std::ranges::search, a, a));
 static_assert(test(std::ranges::search_n, a, 10, 42));
 static_assert(test(std::ranges::set_difference, a, a, a));
 static_assert(test(std::ranges::set_intersection, a, a, a));
 static_assert(test(std::ranges::set_symmetric_difference, a, a, a));
 static_assert(test(std::ranges::set_union, a, a, a));