[libc++][ranges] Fix the return value of `{copy,move}_backward`.

[var-const]

Summary

The return value for both of these algorithms is specified as

`{last, result - N}` for the overloads in namespace `ranges`.

But the current implementation instead returns {first, result - N}.

Also add both algorithms to the relevant "robust" tests.

[philnik]

LGTM % nit.

libcxx/include/__algorithm/ranges_move_backward.h

44–45

Pre-existing: Could you make copy and move consistent w.r.t. using __reverse_range?

[ldionne]

libcxx/include/__algorithm/ranges_move_backward.h

44–45

I'm neutral on this given that we're about to refactor these algorithms significantly to remove their dependency on reverse_iterator altogether.

[var-const]

libcxx/include/__algorithm/ranges_move_backward.h

44–45

I'm inclined to leave as is for the reason that @ldionne mentioned (though I agree it's a good idea).

libcxx/include/__algorithm/copy_backward.h

 #include <__algorithm/unwrap_iter.h>
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
 #include <__ranges/subrange.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
 
 template <class _AlgPolicy, class _InputIterator, class _OutputIterator,
           __enable_if_t<is_same<_AlgPolicy, _ClassicAlgPolicy>::value, int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_InputIterator, _OutputIterator>
 __copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   auto __ret = std::__copy(
       __unconstrained_reverse_iterator<_InputIterator>(__last),
       __unconstrained_reverse_iterator<_InputIterator>(__first),
       __unconstrained_reverse_iterator<_OutputIterator>(__result));
   return pair<_InputIterator, _OutputIterator>(__ret.first.base(), __ret.second.base());
 }
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 template <class _AlgPolicy, class _Iter1, class _Sent1, class _Iter2,
           __enable_if_t<is_same<_AlgPolicy, _RangeAlgPolicy>::value, int> = 0>
 _LIBCPP_HIDE_FROM_ABI constexpr pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) {
-  auto __reverse_range = std::__reverse_range(std::ranges::subrange(std::move(__first), std::move(__last)));
+  auto __last_iter     = _IterOps<_AlgPolicy>::next(__first, std::move(__last));
+  auto __reverse_range = std::__reverse_range(std::ranges::subrange(std::move(__first), __last_iter));
   auto __ret           = ranges::copy(std::move(__reverse_range), std::make_reverse_iterator(__result));
-  return std::make_pair(__ret.in.base(), __ret.out.base());
+  return std::make_pair(__last_iter, __ret.out.base());
 }
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {
   return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H

libcxx/include/__algorithm/ranges_move_backward.h

 using move_backward_result = in_out_result<_InIter, _OutIter>;
 
 namespace __move_backward {
 struct __fn {
 
   template <class _InIter, class _Sent, class _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   move_backward_result<_InIter, _OutIter> __move_backward_impl(_InIter __first, _Sent __last, _OutIter __result) {
-    auto __ret = ranges::move(std::make_reverse_iterator(ranges::next(__first, __last)),
+    auto __last_iter = ranges::next(__first, std::move(__last));
+    auto __ret = ranges::move(std::make_reverse_iterator(__last_iter),
                               std::make_reverse_iterator(__first),
                               std::make_reverse_iterator(__result));
-    return {std::move(__ret.in.base()), std::move(__ret.out.base())};
+    return {std::move(__last_iter), std::move(__ret.out.base())};
   }
 
   template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, bidirectional_iterator _OutIter>
     requires indirectly_movable<_InIter, _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr
   move_backward_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     return __move_backward_impl(std::move(__first), std::move(__last), std::move(__result));
   }

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp

 constexpr void test_iterators() {
   { // simple test
     {
       std::array in {1, 2, 3, 4};
       std::array<int, 4> out;
       std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
         std::ranges::copy_backward(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data() + out.size()));
       assert(in == out);
-      assert(base(ret.in) == in.data());
+      assert(base(ret.in) == in.data() + in.size());
       assert(base(ret.out) == out.data());
     }
     {
       std::array in {1, 2, 3, 4};
       std::array<int, 4> out;
       auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
       std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
           std::ranges::copy_backward(range, Out(out.data() + out.size()));
       assert(in == out);
-      assert(base(ret.in) == in.data());
+      assert(base(ret.in) == in.data() + in.size());
       assert(base(ret.out) == out.data());
     }
   }
 
   { // check that an empty range works
     {
       std::array<int, 0> in;
       std::array<int, 0> out;
       auto ret =
           std::ranges::copy_backward(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data() + out.size()));
-      assert(base(ret.in) == in.data());
+      assert(base(ret.in) == in.data() + in.size());
       assert(base(ret.out) == out.data());
     }
     {
       std::array<int, 0> in;
       std::array<int, 0> out;
       auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
       auto ret = std::ranges::copy_backward(range, Out(out.data()));
-      assert(base(ret.in) == in.data());
+      assert(base(ret.in) == in.data() + in.size());
       assert(base(ret.out) == out.data());
     }
   }
 }
 
 template <class InIter, class OutIter>
 constexpr void test_sentinels() {
   test_iterators<InIter, OutIter, InIter>();
test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
     assert((out == std::array{1, 2, 3, 4}));
   }
 
   { // check that an iterator is returned with a borrowing range
     std::array in {1, 2, 3, 4};
     std::array<int, 4> out;
     std::same_as<std::ranges::in_out_result<int*, int*>> auto ret =
         std::ranges::copy_backward(std::views::all(in), out.data() + out.size());
-    assert(ret.in == in.data());
+    assert(ret.in == in.data() + in.size());
     assert(ret.out == out.data());
     assert(in == out);
   }
 
   { // check that every element is copied exactly once
     struct CopyOnce {
       bool copied = false;
       constexpr CopyOnce() = default;
       constexpr CopyOnce(const CopyOnce& other) = delete;
       constexpr CopyOnce& operator=(const CopyOnce& other) {
         assert(!other.copied);
         copied = true;
         return *this;
       }
     };
     {
       std::array<CopyOnce, 4> in {};
       std::array<CopyOnce, 4> out {};
       auto ret = std::ranges::copy_backward(in.begin(), in.end(), out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));
     }
     {
       std::array<CopyOnce, 4> in {};
       std::array<CopyOnce, 4> out {};
       auto ret = std::ranges::copy_backward(in, out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));
     }
   }
 
   { // check that the range is copied backwards
     struct OnlyBackwardsCopyable {
       OnlyBackwardsCopyable* next = nullptr;
       bool canCopy = false;
       OnlyBackwardsCopyable() = default;
       constexpr OnlyBackwardsCopyable& operator=(const OnlyBackwardsCopyable&) {
         assert(canCopy);
         if (next != nullptr)
           next->canCopy = true;
         return *this;
       }
     };
     {
       std::array<OnlyBackwardsCopyable, 3> in {};
       std::array<OnlyBackwardsCopyable, 3> out {};
       out[1].next = &out[0];
       out[2].next = &out[1];
       out[2].canCopy = true;
       auto ret = std::ranges::copy_backward(in, out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(out[0].canCopy);
       assert(out[1].canCopy);
       assert(out[2].canCopy);
     }
     {
       std::array<OnlyBackwardsCopyable, 3> in {};
       std::array<OnlyBackwardsCopyable, 3> out {};
       out[1].next = &out[0];
       out[2].next = &out[1];
       out[2].canCopy = true;
       auto ret = std::ranges::copy_backward(in.begin(), in.end(), out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(out[0].canCopy);
       assert(out[1].canCopy);
       assert(out[2].canCopy);
     }
   }
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp

 
 template <class In, class Out, class Sent, int N>
 constexpr void test(std::array<int, N> in) {
   {
     std::array<int, N> out;
     std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret =
       std::ranges::move_backward(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data() + out.size()));
     assert(in == out);
-    assert(base(ret.in) == in.data());
+    assert(base(ret.in) == in.data() + in.size());
     assert(base(ret.out) == out.data());
   }
   {
     std::array<int, N> out;
     auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
     std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret =
         std::ranges::move_backward(range, Out(out.data() + out.size()));
     assert(in == out);
-    assert(base(ret.in) == in.data());
+    assert(base(ret.in) == in.data() + in.size());
     assert(base(ret.out) == out.data());
   }
 }
 
 template <class In, class Out, class Sent = In>
 constexpr void test_iterators() {
   // simple test
   test<In, Out, Sent, 4>({1, 2, 3, 4});
test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
     assert((out == std::array{1, 2, 3, 4}));
   }
 
   { // check that an iterator is returned with a borrowing range
     std::array in {1, 2, 3, 4};
     std::array<int, 4> out;
     std::same_as<std::ranges::in_out_result<int*, int*>> auto ret =
         std::ranges::move_backward(std::views::all(in), out.data() + out.size());
-    assert(ret.in == in.data());
+    assert(ret.in == in.data() + in.size());
     assert(ret.out == out.data());
     assert(in == out);
   }
 
   { // check that every element is moved exactly once
     struct MoveOnce {
       bool moved = false;
       constexpr MoveOnce() = default;
       constexpr MoveOnce(const MoveOnce& other) = delete;
       constexpr MoveOnce& operator=(const MoveOnce& other) {
         assert(!other.moved);
         moved = true;
         return *this;
       }
     };
     {
       std::array<MoveOnce, 4> in {};
       std::array<MoveOnce, 4> out {};
       auto ret = std::ranges::move_backward(in.begin(), in.end(), out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; }));
     }
     {
       std::array<MoveOnce, 4> in {};
       std::array<MoveOnce, 4> out {};
       auto ret = std::ranges::move_backward(in, out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; }));
     }
   }
 
   { // check that the range is moved backwards
     struct OnlyBackwardsMovable {
       OnlyBackwardsMovable* next = nullptr;
       bool canMove = false;
       OnlyBackwardsMovable() = default;
       constexpr OnlyBackwardsMovable& operator=(const OnlyBackwardsMovable&) {
         assert(canMove);
         if (next != nullptr)
           next->canMove = true;
         return *this;
       }
     };
     {
       std::array<OnlyBackwardsMovable, 3> in {};
       std::array<OnlyBackwardsMovable, 3> out {};
       out[1].next = &out[0];
       out[2].next = &out[1];
       out[2].canMove = true;
       auto ret = std::ranges::move_backward(in, out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(out[0].canMove);
       assert(out[1].canMove);
       assert(out[2].canMove);
     }
     {
       std::array<OnlyBackwardsMovable, 3> in {};
       std::array<OnlyBackwardsMovable, 3> out {};
       out[1].next = &out[0];
       out[2].next = &out[1];
       out[2].canMove = true;
       auto ret = std::ranges::move_backward(in.begin(), in.end(), out.end());
-      assert(ret.in == in.begin());
+      assert(ret.in == in.end());
       assert(ret.out == out.begin());
       assert(out[0].canMove);
       assert(out[1].canMove);
       assert(out[2].canMove);
     }
   }
 
   { // check that iter_move is used properly
     {
       int a[] = {1, 2, 3, 4};
       std::array<int, 4> b;
       auto ret = std::ranges::move_backward(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4), b.data() + b.size());
-      assert(ret.in == a);
+      assert(ret.in == a + 4);
       assert(ret.out == b.data());
       assert((b == std::array {42, 42, 42, 42}));
     }
     {
       int a[] = {1, 2, 3, 4};
       std::array<int, 4> b;
       auto range = std::ranges::subrange(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4));
       auto ret = std::ranges::move_backward(range, b.data() + b.size());
-      assert(ret.in == a);
+      assert(ret.in == a + 4);
       assert(ret.out == b.data());
       assert((b == std::array {42, 42, 42, 42}));
     }
   }
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp

 std::mt19937 rand_gen() { return std::mt19937(); }
 
 // TODO: also check the iterator values for algorithms that return `*_result` types.
 constexpr bool test_all() {
   using std::ranges::dangling;
 
   using std::ranges::binary_transform_result;
   using std::ranges::copy_result;
-  //using std::ranges::copy_backward_result;
+  using std::ranges::copy_backward_result;
   using std::ranges::copy_if_result;
   using std::ranges::for_each_result;
   using std::ranges::merge_result;
   using std::ranges::minmax_result;
   using std::ranges::mismatch_result;
   using std::ranges::move_result;
-  //using std::ranges::move_backward_result;
+  using std::ranges::move_backward_result;
   using std::ranges::partial_sort_copy_result;
   using std::ranges::partition_copy_result;
   using std::ranges::remove_copy_result;
   using std::ranges::remove_copy_if_result;
   using std::ranges::reverse_copy_result;
   using std::ranges::rotate_copy_result;
   using std::ranges::set_difference_result;
   using std::ranges::set_intersection_result;
constexpr bool test_all() {
   dangling_1st<minmax_result<dangling>>(std::ranges::minmax_element, in);
   dangling_1st(std::ranges::search, in, in2);
   dangling_1st(std::ranges::search_n, in, count, x);
   dangling_1st(std::ranges::find_end, in, in2);
   dangling_1st(std::ranges::is_sorted_until, in);
   dangling_1st(std::ranges::is_heap_until, in);
   dangling_1st<for_each_result<dangling, decltype(unary_pred)>>(std::ranges::for_each, in, unary_pred);
   dangling_1st<copy_result<dangling, int*>>(std::ranges::copy, in, out);
-  // TODO: uncomment `copy_backward` once https://reviews.llvm.org/D128864 lands.
-  //dangling_1st<copy_backward_result<dangling, int*>>(std::ranges::copy_backward, in, out);
+  dangling_1st<copy_backward_result<dangling, int*>>(std::ranges::copy_backward, in, output.end());
   dangling_1st<copy_if_result<dangling, int*>>(std::ranges::copy_if, in, out, unary_pred);
   dangling_1st<move_result<dangling, int*>>(std::ranges::move, in, out);
-  // TODO: uncomment `move_backward` once https://reviews.llvm.org/D128864 lands.
-  //dangling_1st<move_backward_result<dangling, int*>>(std::ranges::move_backward, in, out);
+  dangling_1st<move_backward_result<dangling, int*>>(std::ranges::move_backward, in, output.end());
   dangling_1st(std::ranges::fill, in, x);
   { // transform
     std::array out_transform = {false, true, true};
     dangling_1st<unary_transform_result<dangling, bool*>>(std::ranges::transform, in, out_transform.begin(), unary_pred);
     dangling_1st<binary_transform_result<dangling, int*, bool*>>(
         std::ranges::transform, in, in2, out_transform.begin(), binary_pred);
     dangling_2nd<binary_transform_result<int*, dangling, bool*>>(
         std::ranges::transform, in, in2, out_transform.begin(), binary_pred);

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

constexpr void run_tests() {
   std::array input2 = {T{4}, T{5}, T{6}};
   ProxyRange in2{input2};
 
   auto mid = in.begin() + 1;
 
   std::array output = {T{4}, T{5}, T{6}, T{7}, T{8}, T{9}};
   ProxyIterator out{output.begin()};
   ProxyIterator out2{output.begin() + 1};
+  ProxyIterator out_end{output.end()};
 
   T num{2};
   Proxy<T&> x{num};
   int count = 1;
 
   auto unary_pred = [](const Proxy<T&>&) { return true; };
   //auto binary_pred = [](const Proxy<T>&, const Proxy<T>&) { return return false; };
   auto binary_func = [](const Proxy<T>&, const Proxy<T>&) -> Proxy<T> { return Proxy<T>(T()); };
constexpr void run_tests() {
   test(std::ranges::is_heap_until, in);
   //test(std::ranges::is_permutation, in, in2);
   test(std::ranges::for_each, in, std::identity{});
   std::ranges::for_each_n(in.begin(), count, std::identity{});
   if constexpr (std::copyable<T>) {
     test(std::ranges::copy, in, out);
     std::ranges::copy_n(in.begin(), count, out);
     test(std::ranges::copy_if, in, out, unary_pred);
-    // TODO: uncomment `copy_backward` once https://reviews.llvm.org/D128864 lands.
-    //test(std::ranges::copy_backward, in, out);
+    test(std::ranges::copy_backward, in, out_end);
   }
   test(std::ranges::move, in, out);
-  // TODO: uncomment `move_backward` once https://reviews.llvm.org/D128864 lands.
-  // test(std::ranges::move_backward, in, out);
+  test(std::ranges::move_backward, in, out_end);
   if constexpr (std::copyable<T>) {
     test(std::ranges::fill, in, x);
     std::ranges::fill_n(in.begin(), count, x);
     test(std::ranges::transform, in, out, std::identity{});
     test(std::ranges::transform, in, in2, out, binary_func);
   }
   test(std::ranges::generate, in, gen);
   std::ranges::generate_n(in.begin(), count, gen);