[libc++] Implement ranges::{reverse, rotate}_copy

[var-const]

libcxx/docs/Status/RangesAlgorithms.csv

56–58

As per usual, please update. :)

libcxx/include/__algorithm/ranges_reverse_copy.h

20

Nit: include <__utility/move.h>.

26

Please add the language version / no incomplete ranges guard (other file as well).

40–41

These functions are verbose and using them seems a little clunky (they take a different number of arguments, it's not obvious whether e.g. begin in the name means "make rbegin" or "make rend from the begin iterator", etc.). How about having a single function that returns a pair of iterators instead? I don't think it should add any noticeable overhead:

auto [__rfirst, __rlast] = std::__to_reverse_iterators(__first, __last);
auto __ret = ranges::copy(std::move(__rfirst), std::move(__rlast), std::move(__result));

libcxx/include/algorithm

1407–1408

Please add the synopsis.

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp

13

Missing synopsis.

48

Nit: decltype(auto).

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges.rotate_copy.pass.cpp

13

Missing synopsis.

24

s/Reverse/Rotate/.

48

Nit: decltype(auto).

76

Please also check with a two-element range (the smallest range that can actually be rotated, and it has an even number of elements which otherwise is not tested).

[philnik]

• Address comments

[ldionne]

libcxx/include/__iterator/reverse_iterator.h

331

inline is unnecessary since this is a template.
I suspect constexpr won't work in C++11/14/17 (but you could check 17, it might).

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp

30

I would like an explicit test that is_same<reverse_copy_result<....>, in_out_result<...>>. In fact, I don't see that type mentioned anywhere in the tests, so we wouldn't even notice if we didn't define it. Please do that here but also for all the other algorithms that have been added and that had accompanying foo_result types.

[var-const]

LGTM with just a couple of minor things. I'll leave the final approval to @ldionne since he had comments.

libcxx/include/__iterator/reverse_iterator.h

341

make_pair?

libcxx/include/algorithm

484

Please add the definition of {reverse,rotate}_copy_result to the synopsis as well.

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp

30

Maybe create a dedicated file for this, similar to ranges_robust_against_copying_*? It seems like these checks will be really similar.

[philnik]

• Address comments

@var-const could you take another look? I basically rewrote ranges::reverse_copy.

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp

30

I'll make a dedicated ranges_result_alias_declarations.compile.pass.cpp in it's own PR.

[huixie90]

LGTM

libcxx/include/__algorithm/ranges_reverse_copy.h

17

I might miss something but where is this used? (same apply to the other range algorithm header in the review

[var-const]

libcxx/include/__algorithm/ranges_reverse_copy.h

52

While this allows for a very elegant implementation, the view is way more heavyweight than a simple eager implementation would be. I'd rather avoid the dependency: it adds compilation time overhead, gives users a way to accidentally depend on something they don't include directly, and it might be less efficient (caching logic looks suspicious in that regard).

Whichever approach we settle upon will likely affect some other algorithms as well, so let's check with @ldionne.

[ldionne]

libcxx/include/__algorithm/ranges_reverse_copy.h

52

I think I'd be OK with this. We're trying to granularize headers so that this kind of reuse becomes possible. And we do have an optimization for reverse iterators in std::__copy, so this should end up being as efficient as a hand-written implementation for contiguous iterators.

I would suggest creating a really simple utility, something like std::__reverse_range(rng) that returns a pair of reverse_iterators from a range. This basically does the job of reverse_view, but without the need for caching and any other complicated logic. It only needs to have logic for using std::make_reverse_iterator(ranges::end(rng)) or std::make_reverse_iterator(ranges::next(ranges::begin(rng), ranges::end(rng))) depending on whether rng is a common view. I suspect this would tackle the concern of pulling in too many dependencies.

[philnik]

• Address comments

[philnik]

• Try to fix CI

[philnik]

• Try to fix CI

[philnik]

• Add include

[philnik]

• Add header to modulemap

[philnik]

• Next tryx

[philnik]

• Fix modulemap

[philnik]

• Fix CMakeLists

[philnik]

• Next try

libcxx/docs/Status/RangesAlgorithms.csv

 Write,generate,Nikolas Klauser,n/a,Not started
 Write,generate_n,Nikolas Klauser,n/a,Not started
 Write,remove_copy,Nikolas Klauser,n/a,Not started
 Write,remove_copy_if,Nikolas Klauser,n/a,Not started
 Write,replace,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
 Write,replace_if,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
 Write,replace_copy,Nikolas Klauser,n/a,Not started
 Write,replace_copy_if,Nikolas Klauser,n/a,Not started
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
-Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
-Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
+Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
+Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,sample,Not assigned,n/a,Not started
 Write,unique_copy,Not assigned,n/a,Not started
 Write,partition_copy,Not assigned,n/a,Not started
 Write,partial_sort_copy,Not assigned,n/a,Not started
 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,n/a,Not started

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_nth_element.h
   __algorithm/ranges_pop_heap.h
   __algorithm/ranges_push_heap.h
   __algorithm/ranges_remove.h
   __algorithm/ranges_remove_if.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
+  __algorithm/ranges_reverse_copy.h
+  __algorithm/ranges_rotate_copy.h
   __algorithm/ranges_set_difference.h
   __algorithm/ranges_set_intersection.h
   __algorithm/ranges_sort.h
   __algorithm/ranges_sort_heap.h
   __algorithm/ranges_stable_sort.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h

libcxx/include/__algorithm/ranges_reverse_copy.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_REVERSE_COPY_H
+#define _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H
+
+#include <__algorithm/in_out_result.h>
+#include <__algorithm/ranges_copy.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/next.h>
+#include <__iterator/reverse_iterator.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.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 {
+
+template <class _InIter, class _OutIter>
+using reverse_copy_result = in_out_result<_InIter, _OutIter>;
+
+namespace __reverse_copy {
+struct __fn {
+
+  template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter>
+    requires indirectly_copyable<_InIter, _OutIter>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  reverse_copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {
+    return (*this)(subrange(std::move(__first), std::move(__last)), std::move(__result));
+  }
+
+  template <bidirectional_range _Range, weakly_incrementable _OutIter>
+    requires indirectly_copyable<iterator_t<_Range>, _OutIter>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  reverse_copy_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, _OutIter __result) const {
+    auto __ret = ranges::copy(std::__reverse_range(__range), std::move(__result));
+    return {ranges::next(ranges::begin(__range), ranges::end(__range)), std::move(__ret.out)};
+  }
+
+};
+} // namespace __reverse_copy
+
+inline namespace __cpo {
+  inline constexpr auto reverse_copy = __reverse_copy::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H

libcxx/include/__algorithm/ranges_rotate_copy.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_COPY_H
+#define _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H
+
+#include <__algorithm/in_out_result.h>
+#include <__algorithm/ranges_copy.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/reverse_iterator.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
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _InIter, class _OutIter>
+using rotate_copy_result = in_out_result<_InIter, _OutIter>;
+
+namespace __rotate_copy {
+struct __fn {
+
+  template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter>
+    requires indirectly_copyable<_InIter, _OutIter>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  rotate_copy_result<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __middle, _Sent __last, _OutIter __result) const {
+    auto __res1 = ranges::copy(__middle, __last, std::move(__result));
+    auto __res2 = ranges::copy(__first, __middle, std::move(__res1.out));
+    return {std::move(__res1.in), std::move(__res2.out)};
+  }
+
+  template <bidirectional_range _Range, weakly_incrementable _OutIter>
+    requires indirectly_copyable<iterator_t<_Range>, _OutIter>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  rotate_copy_result<borrowed_iterator_t<_Range>, _OutIter>
+  operator()(_Range&& __range, iterator_t<_Range> __middle, _OutIter __result) const {
+    return (*this)(ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__result));
+  }
+
+};
+} // namespace __rotate_copy
+
+inline namespace __cpo {
+  inline constexpr auto rotate_copy = __rotate_copy::__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_COPY_H

libcxx/include/__iterator/reverse_iterator.h

 #ifndef _LIBCPP___ITERATOR_REVERSE_ITERATOR_H
 #define _LIBCPP___ITERATOR_REVERSE_ITERATOR_H
 
 #include <__algorithm/unwrap_iter.h>
 #include <__compare/compare_three_way_result.h>
 #include <__compare/three_way_comparable.h>
 #include <__concepts/convertible_to.h>
 #include <__config>
+#include <__iterator/advance.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__iterator/readable_traits.h>
 #include <__memory/addressof.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/subrange.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

 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
 {
     return reverse_iterator<_Iter>(__i);
 }
 #endif
 
 template <class _Iter>
 using _ReverseWrapper = reverse_iterator<reverse_iterator<_Iter> >;
 
 template <class _Iter, bool __b>
 struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> {
   static _LIBCPP_CONSTEXPR decltype(std::__unwrap_iter(std::declval<_Iter>()))
   __apply(_ReverseWrapper<_Iter> __i) _NOEXCEPT {
     return std::__unwrap_iter(__i.base().base());
   }
 };
 
 template <class _OrigIter, class _UnwrappedIter>
 struct __rewrap_iter_impl<_ReverseWrapper<_OrigIter>, _UnwrappedIter> {
   template <class _Iter>
   struct _ReverseWrapperCount {
     static _LIBCPP_CONSTEXPR const size_t value = 1;
   };
 
   template <class _Iter>
   struct _ReverseWrapperCount<_ReverseWrapper<_Iter> > {
struct __rewrap_iter_impl<_ReverseWrapper<_OrigIter>, _UnwrappedIter> {
   }
 
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR _ReverseWrapper<_OrigIter> __apply(_ReverseWrapper<_OrigIter> __iter1,
                                                                                     _UnwrappedIter __iter2) {
     return __rewrap<_ReverseWrapperCount<_OrigIter>::value>(__iter1, __iter2);
   }
 };
 
+#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
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H

libcxx/include/algorithm

template<input_range R1, forward_range R2,
     requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
     constexpr borrowed_iterator_t<R1>
       ranges::find_first_of(R1&& r1, R2&& r2,
                             Pred pred = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {});                            // since C++20
 
   template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_binary_predicate<projected<I, Proj>,
                                      projected<I, Proj>> Pred = ranges::equal_to>
     constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});     // since C+20
 
   template<forward_range R, class Proj = identity,
            indirect_binary_predicate<projected<iterator_t<R>, Proj>,
                                      projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
     constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});  // since C++20
 
   template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
template<permutable I, sentinel_for<I> S, class Proj = identity,
            indirect_unary_predicate<projected<I, Proj>> Pred>
     constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});            // since C++20
 
   template<forward_range R, class Proj = identity,
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     requires permutable<iterator_t<R>>
     constexpr borrowed_subrange_t<R>
       ranges::remove_if(R&& r, Pred pred, Proj proj = {});                                          // since C++20
-  
   template<class I, class O>
-    using set_difference_result = in_out_result<I, O>;                                              // since C++20                                              
+    using set_difference_result = in_out_result<I, O>;                                              // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_difference_result<I1, O>
       set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                      Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                           // since C++20
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       set_intersection(R1&& r1, R2&& r2, O result,
                        Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                         // since C++20
 
+  template <class _InIter, class _OutIter>
+  using reverse_copy_result = in_out_result<_InIter, _OutIter>;                                     // since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
+    requires indirectly_copyable<I, 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 <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
+
+  template<forward_range R, weakly_incrementable O>
+    requires indirectly_copyable<iterator_t<R>, O>
+    constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
+      ranges::rotate_copy(R&& r, iterator_t<R> middle, O result);                                   // since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_for_each_n.h>
 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_make_heap.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_merge.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_nth_element.h>
 #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_copy.h>
 #include <__algorithm/ranges_set_difference.h>
 #include <__algorithm/ranges_set_intersection.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_sort_heap.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_nth_element              { private header "__algorithm/ranges_nth_element.h" }
       module ranges_pop_heap                 { private header "__algorithm/ranges_pop_heap.h" }
       module ranges_push_heap                { private header "__algorithm/ranges_push_heap.h" }
       module ranges_remove                   { private header "__algorithm/ranges_remove.h" }
       module ranges_remove_if                { private header "__algorithm/ranges_remove_if.h" }
       module ranges_replace                  { private header "__algorithm/ranges_replace.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_copy              { private header "__algorithm/ranges_rotate_copy.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_sort                     { private header "__algorithm/ranges_sort.h" }
       module ranges_sort_heap                { private header "__algorithm/ranges_sort_heap.h" }
       module ranges_stable_sort              { private header "__algorithm/ranges_stable_sort.h" }
       module ranges_swap_ranges              { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform                { private header "__algorithm/ranges_transform.h" }
       module ranges_upper_bound              { private header "__algorithm/ranges_upper_bound.h" }

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_nth_element.h'}}
 #include <__algorithm/ranges_pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_pop_heap.h'}}
 #include <__algorithm/ranges_push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_push_heap.h'}}
 #include <__algorithm/ranges_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.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_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_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate_copy.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_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
 #include <__algorithm/ranges_sort_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort_heap.h'}}
 #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}

libcxx/test/libcxx/transitive_includes/expected.charconv

 cerrno
 charconv
 cmath
 concepts
 cstddef
 cstdint
 cstdlib
 cstring
+initializer_list
 iosfwd
 limits
 type_traits
 version

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.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
+
+// template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
+//   requires indirectly_copyable<I, O>
+//   constexpr ranges::reverse_copy_result<I, O>
+//     ranges::reverse_copy(I first, S last, O result);
+// 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);
+
+// <algorithm>
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter, class Out = int*, class Sent = sentinel_wrapper<Iter>>
+concept HasReverseCopyIt = requires(Iter first, Sent last, Out out) { std::ranges::reverse_copy(first, last, out); };
+
+template <class Range, class Out = int*>
+concept HasReverseCopyR = requires(Range range, Out out) { std::ranges::reverse_copy(range, out); };
+
+static_assert(HasReverseCopyIt<int*>);
+static_assert(!HasReverseCopyIt<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasReverseCopyIt<BidirectionalIteratorNotDecrementable>);
+static_assert(!HasReverseCopyIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasReverseCopyIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasReverseCopyIt<int*, OutputIteratorNotIndirectlyWritable>);
+static_assert(!HasReverseCopyIt<int*, OutputIteratorNotInputOrOutputIterator>);
+
+static_assert(HasReverseCopyR<UncheckedRange<int*>>);
+static_assert(!HasReverseCopyR<BidirectionalRangeNotDerivedFrom>);
+static_assert(!HasReverseCopyR<BidirectionalRangeNotDecrementable>);
+static_assert(!HasReverseCopyR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasReverseCopyR<UncheckedRange<int*>, OutputIteratorNotIndirectlyWritable>);
+static_assert(!HasReverseCopyR<UncheckedRange<int*>, OutputIteratorNotInputOrOutputIterator>);
+
+static_assert(std::is_same_v<std::ranges::reverse_copy_result<int, int>, std::ranges::in_out_result<int, int>>);
+
+template <class Iter, class OutIter, class Sent, int N>
+constexpr void test(std::array<int, N> value, std::array<int, N> expected) {
+  {
+    std::array<int, N> out;
+    std::same_as<std::ranges::in_out_result<Iter, OutIter>> decltype(auto) ret =
+        std::ranges::reverse_copy(Iter(value.data()),
+                                 Sent(Iter(value.data() + value.size())),
+                                 OutIter(out.data()));
+    assert(base(ret.in) == value.data() + value.size());
+    assert(base(ret.out) == out.data() + out.size());
+    assert(out == expected);
+  }
+  {
+    std::array<int, N> out;
+    auto range = std::ranges::subrange(Iter(value.data()), Sent(Iter(value.data() + value.size())));
+    std::same_as<std::ranges::in_out_result<Iter, OutIter>> decltype(auto) ret =
+        std::ranges::reverse_copy(range, OutIter(out.data()));
+    assert(base(ret.in) == value.data() + value.size());
+    assert(base(ret.out) == out.data() + out.size());
+    assert(out == expected);
+  }
+}
+
+template <class Iter, class OutIter, class Sent>
+constexpr void test_iterators() {
+  // simple test
+  test<Iter, OutIter, Sent, 4>({1, 2, 3, 4}, {4, 3, 2, 1});
+
+  // check that an empty range works
+  test<Iter, OutIter, Sent, 0>({}, {});
+
+  // check that a single element range works
+  test<Iter, OutIter, Sent, 1>({1}, {1});
+
+  // check that a two element range works
+  test<Iter, OutIter, Sent, 2>({1, 2}, {2, 1});
+}
+
+template <class Iter, class Sent = Iter>
+constexpr void test_out_iterators() {
+  test_iterators<Iter, cpp20_output_iterator<int*>, Sent>();
+  test_iterators<Iter, forward_iterator<int*>, Sent>();
+  test_iterators<Iter, bidirectional_iterator<int*>, Sent>();
+  test_iterators<Iter, random_access_iterator<int*>, Sent>();
+  test_iterators<Iter, contiguous_iterator<int*>, Sent>();
+  test_iterators<Iter, int*, Sent>();
+}
+
+constexpr bool test() {
+  test_out_iterators<bidirectional_iterator<int*>>();
+  test_out_iterators<random_access_iterator<int*>>();
+  test_out_iterators<contiguous_iterator<int*>>();
+  test_out_iterators<int*>();
+  test_out_iterators<const int*>();
+
+  {
+    struct AssignmentCounter {
+      int* counter;
+
+      constexpr AssignmentCounter(int* counter_) : counter(counter_) {}
+      constexpr AssignmentCounter& operator=(const AssignmentCounter&) { ++*counter; return *this; }
+    };
+
+    {
+      int c = 0;
+      AssignmentCounter a[] = {&c, &c, &c, &c};
+      AssignmentCounter b[] = {&c, &c, &c, &c};
+      std::ranges::reverse_copy(a, a + 4, b);
+      assert(c == 4);
+    }
+    {
+      int c = 0;
+      AssignmentCounter a[] = {&c, &c, &c, &c};
+      AssignmentCounter b[] = {&c, &c, &c, &c};
+      std::ranges::reverse_copy(a, b);
+      assert(c == 4);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges.rotate_copy.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
+
+// 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);
+// template<forward_range R, weakly_incrementable O>
+//   requires indirectly_copyable<iterator_t<R>, O>
+//   constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
+//     ranges::rotate_copy(R&& r, iterator_t<R> middle, O result);
+
+// <algorithm>
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter, class Out = int*, class Sent = sentinel_wrapper<Iter>>
+concept HasRotateCopyIt = requires(Iter first, Sent last, Out out) { std::ranges::rotate_copy(first, first, last, out); };
+
+template <class Range, class Out = int*>
+concept HasRotateCopyR = requires(Range range, Out out) { std::ranges::rotate_copy(range, nullptr, out); };
+
+static_assert(HasRotateCopyIt<int*>);
+static_assert(!HasRotateCopyIt<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasRotateCopyIt<BidirectionalIteratorNotDecrementable>);
+static_assert(!HasRotateCopyIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasRotateCopyIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasRotateCopyIt<int*, OutputIteratorNotIndirectlyWritable>);
+static_assert(!HasRotateCopyIt<int*, OutputIteratorNotInputOrOutputIterator>);
+
+static_assert(HasRotateCopyR<UncheckedRange<int*>>);
+static_assert(!HasRotateCopyR<BidirectionalRangeNotDerivedFrom>);
+static_assert(!HasRotateCopyR<BidirectionalRangeNotDecrementable>);
+static_assert(!HasRotateCopyR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasRotateCopyR<UncheckedRange<int*>, OutputIteratorNotIndirectlyWritable>);
+static_assert(!HasRotateCopyR<UncheckedRange<int*>, OutputIteratorNotInputOrOutputIterator>);
+
+static_assert(std::is_same_v<std::ranges::rotate_copy_result<int, int>, std::ranges::in_out_result<int, int>>);
+
+template <class Iter, class OutIter, class Sent, int N>
+constexpr void test(std::array<int, N> value, size_t middle, std::array<int, N> expected) {
+  {
+    std::array<int, N> out;
+    std::same_as<std::ranges::in_out_result<Iter, OutIter>> decltype(auto) ret =
+        std::ranges::rotate_copy(Iter(value.data()),
+                                 Iter(value.data() + middle),
+                                 Sent(Iter(value.data() + value.size())),
+                                 OutIter(out.data()));
+    assert(base(ret.in) == value.data() + value.size());
+    assert(base(ret.out) == out.data() + out.size());
+    assert(out == expected);
+  }
+  {
+    std::array<int, N> out;
+    auto range = std::ranges::subrange(Iter(value.data()), Sent(Iter(value.data() + value.size())));
+    std::same_as<std::ranges::in_out_result<Iter, OutIter>> decltype(auto) ret =
+        std::ranges::rotate_copy(range, Iter(value.data() + middle), OutIter(out.data()));
+    assert(base(ret.in) == value.data() + value.size());
+    assert(base(ret.out) == out.data() + out.size());
+    assert(out == expected);
+  }
+}
+
+template <class Iter, class OutIter, class Sent>
+constexpr void test_iterators() {
+  // simple test
+  test<Iter, OutIter, Sent, 4>({1, 2, 3, 4}, 2, {3, 4, 1, 2});
+
+  // check that an empty range works
+  test<Iter, OutIter, Sent, 0>({}, 0, {});
+
+  // check that a single element range works
+  test<Iter, OutIter, Sent, 1>({1}, 0, {1});
+
+  // check that a two element range works
+  test<Iter, OutIter, Sent, 2>({1, 2}, 1, {2, 1});
+
+  // rotate on the first element
+  test<Iter, OutIter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 0, {1, 2, 3, 4, 5, 6, 7});
+
+  // rotate on the second element
+  test<Iter, OutIter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 1, {2, 3, 4, 5, 6, 7, 1});
+
+  // rotate on the last element
+  test<Iter, OutIter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 6, {7, 1, 2, 3, 4, 5, 6});
+
+  // rotate on the one-past-the-end pointer
+  test<Iter, OutIter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 7, {1, 2, 3, 4, 5, 6, 7});
+}
+
+template <class Iter, class Sent = Iter>
+constexpr void test_out_iterators() {
+  test_iterators<Iter, cpp20_output_iterator<int*>, Sent>();
+  test_iterators<Iter, forward_iterator<int*>, Sent>();
+  test_iterators<Iter, bidirectional_iterator<int*>, Sent>();
+  test_iterators<Iter, random_access_iterator<int*>, Sent>();
+  test_iterators<Iter, contiguous_iterator<int*>, Sent>();
+  test_iterators<Iter, int*, Sent>();
+}
+
+constexpr bool test() {
+  test_out_iterators<bidirectional_iterator<int*>>();
+  test_out_iterators<random_access_iterator<int*>>();
+  test_out_iterators<contiguous_iterator<int*>>();
+  test_out_iterators<int*>();
+  test_out_iterators<const int*>();
+
+  {
+    struct AssignmentCounter {
+      int* counter;
+
+      constexpr AssignmentCounter(int* counter_) : counter(counter_) {}
+      constexpr AssignmentCounter& operator=(const AssignmentCounter&) { ++*counter; return *this; }
+    };
+
+    {
+      int c = 0;
+      AssignmentCounter a[] = {&c, &c, &c, &c};
+      AssignmentCounter b[] = {&c, &c, &c, &c};
+      std::ranges::rotate_copy(a, a + 2, a + 4, b);
+      assert(c == 4);
+    }
+    {
+      int c = 0;
+      AssignmentCounter a[] = {&c, &c, &c, &c};
+      AssignmentCounter b[] = {&c, &c, &c, &c};
+      std::ranges::rotate_copy(a, a + 2, b);
+      assert(c == 4);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //static_assert(test(std::ranges::remove_copy, a, a, 42));
 //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::reverse_copy, a, a));
 //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::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));
 //static_assert(test(std::ranges::shuffle, a, g));