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

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.

Differential Revision: https://reviews.llvm.org/D130968

(cherry picked from commit f537a01d3989d37aafc050a92c74e69d35381f8c)

6 files changed, 31 insertions, 33 deletions

diff --git a/libcxx/include/__algorithm/copy_backward.h b/libcxx/include/__algorithm/copy_backward.h
index 26b8c4d791fd..c5fa64bc8d75 100644
--- a/libcxx/include/__algorithm/copy_backward.h
+++ b/libcxx/include/__algorithm/copy_backward.h
@@ -20,7 +20,6 @@
 #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)
@@ -44,9 +43,10 @@ __copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator _
 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)
 
diff --git a/libcxx/include/__algorithm/ranges_move_backward.h b/libcxx/include/__algorithm/ranges_move_backward.h
index b3dfa7139603..583a6bf29d51 100644
--- a/libcxx/include/__algorithm/ranges_move_backward.h
+++ b/libcxx/include/__algorithm/ranges_move_backward.h
@@ -40,10 +40,11 @@ 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>
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
index b75eced30b79..d99fa4888430 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
@@ -65,7 +65,7 @@ constexpr void test_iterators() {
       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());
     }
     {
@@ -75,7 +75,7 @@ constexpr void test_iterators() {
       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());
     }
   }
@@ -86,7 +86,7 @@ constexpr void test_iterators() {
       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());
     }
     {
@@ -94,7 +94,7 @@ constexpr void test_iterators() {
       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());
     }
   }
@@ -143,7 +143,7 @@ constexpr bool test() {
     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);
   }
@@ -163,7 +163,7 @@ constexpr bool test() {
       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; }));
     }
@@ -171,7 +171,7 @@ constexpr bool test() {
       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; }));
     }
@@ -196,7 +196,7 @@ constexpr bool test() {
       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);
@@ -209,7 +209,7 @@ constexpr bool test() {
       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);
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp
index 2211409f6ab3..fc2706d1e07f 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp
@@ -64,7 +64,7 @@ constexpr void test(std::array<int, N> in) {
     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());
   }
   {
@@ -73,7 +73,7 @@ constexpr void test(std::array<int, N> in) {
     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());
   }
 }
@@ -186,7 +186,7 @@ constexpr bool test() {
     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);
   }
@@ -206,7 +206,7 @@ constexpr bool test() {
       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; }));
     }
@@ -214,7 +214,7 @@ constexpr bool test() {
       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; }));
     }
@@ -239,7 +239,7 @@ constexpr bool test() {
       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);
@@ -252,7 +252,7 @@ constexpr bool test() {
       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);
@@ -265,7 +265,7 @@ constexpr bool test() {
       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}));
     }
@@ -274,7 +274,7 @@ constexpr bool test() {
       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}));
     }
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
index b280dca05ad9..de2ed6920b06 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
@@ -68,14 +68,14 @@ constexpr bool test_all() {
 
   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;
@@ -128,12 +128,10 @@ constexpr bool test_all() {
   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};
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
index 9193333457a9..332a562ff366 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
@@ -62,6 +62,7 @@ constexpr void run_tests() {
   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};
@@ -110,12 +111,10 @@ constexpr void run_tests() {
     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);