libstdc++: Do not use use memmove for 1-element ranges [PR108846, PR116471]

Hello,

This patch completes the fix for PR108846, extending it to range-based 
copy/move algorithms, and also fixes a faulty static_assert in them 
(PR116471).
It's a minor improvement over the patch I've attached to PR116471 (I've 
fixed the constraints of __assign_one).

Thank you,

On Fri, 30 Aug 2024 at 11:52, Giuseppe D'Angelo wrote:
>
> Hello,
>
> This patch completes the fix for PR108846, extending it to range-based
> copy/move algorithms, and also fixes a faulty static_assert in them
> (PR116471).
> It's a minor improvement over the patch I've attached to PR116471 (I've
> fixed the constraints of __assign_one).

Nice, thanks for the patch.

Is there any need to constrain __assign_one? It's only going to be
called from internal functions where we know the constraint is already
satisfied. Constraining __assign_one just gives the compiler more work
to do to check satisfaction that all callers have already checked.

The calls to __assign_one should all be qualified to prevent ADL.

For C++20 code we can use [[likely]] instead of __builtin_expect.

And a very minor comment on the ChangeLog part, the new function
should be named in parentheses, just like the existing functions being
changed, i.e.

           * include/bits/ranges_algobase.h (__assign_one): New helper
           function.

But I can make these minor changes locally and push it if you want -
there's no need for a v2 patch.

Hello,

Thank you for the review!

Il 13/09/24 10:49, Jonathan Wakely ha scritto:
> 
> But I can make these minor changes locally and push it if you want -
> there's no need for a v2 patch.
I'd gladly take this offer, please feel free to amend as needed and push :)

Cheers,

On Fri, 13 Sept 2024 at 11:00, Giuseppe D'Angelo wrote:
>
> Hello,
>
> Thank you for the review!
>
> Il 13/09/24 10:49, Jonathan Wakely ha scritto:
> >
> > But I can make these minor changes locally and push it if you want -
> > there's no need for a v2 patch.
> I'd gladly take this offer, please feel free to amend as needed and push :)

I also needed to fix the new tests for copy and copy_backward, to not
use a defaulted assignment in C++98 mode.

Here's what I pushed.
commit 5938e0681c3907b2771ce6717988416b0ddd2f54
Author: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
Date:   Fri Aug 23 14:05:54 2024

    libstdc++: Do not use use memmove for 1-element ranges [PR108846,PR116471]
    
    This commit ports the fixes already applied by r13-6372-g822a11a1e642e0
    to the range-based versions of copy/move algorithms.
    
    When doing so, a further bug (PR116471) was discovered in the
    implementation of the range-based algorithms: although the algorithms
    are already constrained by the indirectly_copyable/movable concepts,
    there was a failing static_assert in the memmove path.
    
    This static_assert checked that iterator's value type was assignable by
    using the is_copy_assignable (move) type traits. However, this is a
    problem, because the traits are too strict when checking for constness;
    a type like
    
      struct S { S& operator=(S &) = default; };
    
    is trivially copyable (and thus could benefit of the memmove path),
    but it does not satisfy is_copy_assignable because the operator takes
    by non-const reference.
    
    Now, the reason for the check to be there is because a type with
    a deleted assignment operator like
    
      struct E { E& operator=(const E&) = delete; };
    
    is still trivially copyable, but not assignable. We don't want
    algorithms like std::ranges::copy to compile because they end up
    selecting the memmove path, "ignoring" the fact that E isn't even
    copy assignable.
    
    But the static_assert isn't needed here any longer: as noted before,
    the ranges algorithms already have the appropriate constraints; and
    even if they didn't, there's now a non-discarded codepath to deal with
    ranges of length 1 where there is an explicit assignment operation.
    
    Therefore, this commit removes it. (In fact, r13-6372-g822a11a1e642e0
    removed the same static_assert from the non-ranges algorithms.)
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/108846
            PR libstdc++/116471
            * include/bits/ranges_algobase.h (__assign_one): New helper
            function.
            (__copy_or_move): Remove a spurious static_assert; use
            __assign_one for memcpyable ranges of length 1.
            (__copy_or_move_backward): Likewise.
            * testsuite/25_algorithms/copy/108846.cc: Extend to range-based
            algorithms, and cover both memcpyable and non-memcpyable
            cases.
            * testsuite/25_algorithms/copy_backward/108846.cc: Likewise.
            * testsuite/25_algorithms/copy_n/108846.cc: Likewise.
            * testsuite/25_algorithms/move/108846.cc: Likewise.
            * testsuite/25_algorithms/move_backward/108846.cc: Likewise.
    
    Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>

diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h
index fd35b8ba14c..9b45cbc5ef4 100644
--- a/libstdc++-v3/include/bits/ranges_algobase.h
+++ b/libstdc++-v3/include/bits/ranges_algobase.h
@@ -225,6 +225,16 @@ namespace ranges
 			      copy_backward_result<_Iter, _Out>>
     __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
 
+  template<bool _IsMove, typename _Iter, typename _Out>
+    constexpr void
+    __assign_one(_Iter& __iter, _Out& __result)
+    {
+      if constexpr (_IsMove)
+	  *__result = std::move(*__iter);
+      else
+	  *__result = *__iter;
+    }
+
   template<bool _IsMove,
 	   input_iterator _Iter, sentinel_for<_Iter> _Sent,
 	   weakly_incrementable _Out>
@@ -279,23 +289,19 @@ namespace ranges
 	      if constexpr (__memcpyable<_Iter, _Out>::__value)
 		{
 		  using _ValueTypeI = iter_value_t<_Iter>;
-		  static_assert(_IsMove
-		      ? is_move_assignable_v<_ValueTypeI>
-		      : is_copy_assignable_v<_ValueTypeI>);
 		  auto __num = __last - __first;
-		  if (__num)
+		  if (__num > 1) [[likely]]
 		    __builtin_memmove(__result, __first,
-			sizeof(_ValueTypeI) * __num);
+				      sizeof(_ValueTypeI) * __num);
+		  else if (__num == 1)
+		    ranges::__assign_one<_IsMove>(__first, __result);
 		  return {__first + __num, __result + __num};
 		}
 	    }
 
 	  for (auto __n = __last - __first; __n > 0; --__n)
 	    {
-	      if constexpr (_IsMove)
-		*__result = std::move(*__first);
-	      else
-		*__result = *__first;
+	      ranges::__assign_one<_IsMove>(__first, __result);
 	      ++__first;
 	      ++__result;
 	    }
@@ -305,10 +311,7 @@ namespace ranges
 	{
 	  while (__first != __last)
 	    {
-	      if constexpr (_IsMove)
-		*__result = std::move(*__first);
-	      else
-		*__result = *__first;
+	      ranges::__assign_one<_IsMove>(__first, __result);
 	      ++__first;
 	      ++__result;
 	    }
@@ -414,13 +417,12 @@ namespace ranges
 	      if constexpr (__memcpyable<_Out, _Iter>::__value)
 		{
 		  using _ValueTypeI = iter_value_t<_Iter>;
-		  static_assert(_IsMove
-		      ? is_move_assignable_v<_ValueTypeI>
-		      : is_copy_assignable_v<_ValueTypeI>);
 		  auto __num = __last - __first;
-		  if (__num)
+		  if (__num > 1) [[likely]]
 		    __builtin_memmove(__result - __num, __first,
 				      sizeof(_ValueTypeI) * __num);
+		  else if (__num == 1)
+		    ranges::__assign_one<_IsMove>(__first, __result);
 		  return {__first + __num, __result - __num};
 		}
 	    }
@@ -432,10 +434,7 @@ namespace ranges
 	    {
 	      --__tail;
 	      --__result;
-	      if constexpr (_IsMove)
-		*__result = std::move(*__tail);
-	      else
-		*__result = *__tail;
+	      ranges::__assign_one<_IsMove>(__tail, __result);
 	    }
 	  return {std::move(__lasti), std::move(__result)};
 	}
@@ -448,10 +447,7 @@ namespace ranges
 	    {
 	      --__tail;
 	      --__result;
-	      if constexpr (_IsMove)
-		*__result = std::move(*__tail);
-	      else
-		*__result = *__tail;
+	      ranges::__assign_one<_IsMove>(__tail, __result);
 	    }
 	  return {std::move(__lasti), std::move(__result)};
 	}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc
index 964028901b8..e3b722c068a 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc
@@ -26,6 +26,10 @@ test_pr108846()
     // If this is optimized to memmove it will overwrite tail padding.
     std::copy(src, src+1, dst);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 struct B2 {
@@ -49,10 +53,44 @@ test_non_const_copy_assign()
     // Ensure the not-taken trivial copy path works for this type.
     std::copy(src, src+1, dst);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#endif
+}
+
+struct B3 {
+    B3(int i, short j) : i(i), j(j) {}
+#if __cplusplus >= 201103L
+    B3& operator=(B3& b) = default;
+#endif
+    int i;
+    short j;
+};
+struct D3 : B3 {
+    D3(int i, short j, short x) : B3(i, j), x(x) {}
+    short x; // Stored in tail padding of B3
+};
+
+void
+test_non_const_copy_assign_trivial()
+{
+    D3 ddst(1, 2, 3);
+    D3 dsrc(4, 5, 6);
+    B3 *dst = &ddst;
+    B3 *src = &dsrc;
+    // If this is optimized to memmove it will overwrite tail padding.
+    std::copy(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 int main()
 {
   test_pr108846();
   test_non_const_copy_assign();
+  test_non_const_copy_assign_trivial();
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc
index 84b3d5a285b..206748d92d3 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc
@@ -26,6 +26,10 @@ test_pr108846()
     // If this is optimized to memmove it will overwrite tail padding.
     std::copy_backward(src, src+1, dst+1);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 struct B2 {
@@ -49,10 +53,44 @@ test_non_const_copy_assign()
     // Ensure the not-taken trivial copy path works for this type.
     std::copy_backward(src, src+1, dst+1);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#endif
+}
+
+struct B3 {
+    B3(int i, short j) : i(i), j(j) {}
+#if __cplusplus >= 201103L
+    B3& operator=(B3& b) = default;
+#endif
+    int i;
+    short j;
+};
+struct D3 : B3 {
+    D3(int i, short j, short x) : B3(i, j), x(x) {}
+    short x; // Stored in tail padding of B3
+};
+
+void
+test_non_const_copy_assign_trivial()
+{
+    D3 ddst(1, 2, 3);
+    D3 dsrc(4, 5, 6);
+    B3 *dst = &ddst;
+    B3 *src = &dsrc;
+    // If this is optimized to memmove it will overwrite tail padding.
+    std::copy_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 int main()
 {
   test_pr108846();
   test_non_const_copy_assign();
+  test_non_const_copy_assign_trivial();
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc
index 9ed43e154b7..50deb5dd051 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc
@@ -26,11 +26,15 @@ test_pr108846()
     // If this is optimized to memmove it will overwrite tail padding.
     std::copy_n(src, 1, dst);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy_n(src, 1, dst);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 struct B2 {
     B2(int i, short j) : i(i), j(j) {}
-    B2& operator=(B2&) = default;
+    B2& operator=(B2& b) { i = b.i; j = b.j; return *this; }
     int i;
     short j;
 };
@@ -49,10 +53,42 @@ test_non_const_copy_assign()
     // Ensure the not-taken trivial copy path works for this type.
     std::copy_n(src, 1, dst);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy_n(src, 1, dst);
+    VERIFY(ddst.x == 3);
+#endif
+}
+
+struct B3 {
+    B3(int i, short j) : i(i), j(j) {}
+    B3& operator=(B3& b) = default;
+    int i;
+    short j;
+};
+struct D3 : B3 {
+    D3(int i, short j, short x) : B3(i, j), x(x) {}
+    short x; // Stored in tail padding of B3
+};
+
+void
+test_non_const_copy_assign_trivial()
+{
+    D3 ddst(1, 2, 3);
+    D3 dsrc(4, 5, 6);
+    B3 *dst = &ddst;
+    B3 *src = &dsrc;
+    // If this is optimized to memmove it will overwrite tail padding.
+    std::copy_n(src, 1, dst);
+    VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::copy_n(src, 1, dst);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 int main()
 {
   test_pr108846();
   test_non_const_copy_assign();
+  test_non_const_copy_assign_trivial();
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/108846.cc b/libstdc++-v3/testsuite/25_algorithms/move/108846.cc
index 8248b87d5e2..2dd52a44290 100644
--- a/libstdc++-v3/testsuite/25_algorithms/move/108846.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/move/108846.cc
@@ -26,6 +26,37 @@ test_pr108846()
     // If this is optimized to memmove it will overwrite tail padding.
     std::move(src, src+1, dst);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::move(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#endif
+}
+
+struct B2 {
+    B2(int i, short j) : i(i), j(j) {}
+    B2& operator=(B2&& b) { i = b.i; j = b.j; return *this; }
+    int i;
+    short j;
+};
+struct D2 : B2 {
+    D2(int i, short j, short x) : B2(i, j), x(x) {}
+    short x; // Stored in tail padding of B2
+};
+
+void
+test_move_only()
+{
+    D2 ddst(1, 2, 3);
+    D2 dsrc(4, 5, 6);
+    B2 *dst = &ddst;
+    B2 *src = &dsrc;
+    // Ensure the not-taken trivial copy path works for this type.
+    std::move(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::move(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 struct B3 {
@@ -40,19 +71,24 @@ struct D3 : B3 {
 };
 
 void
-test_move_only()
+test_move_only_trivial()
 {
     D3 ddst(1, 2, 3);
     D3 dsrc(4, 5, 6);
     B3 *dst = &ddst;
     B3 *src = &dsrc;
-    // Ensure the not-taken trivial copy path works for this type.
+    // If this is optimized to memmove it will overwrite tail padding.
     std::move(src, src+1, dst);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::move(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 int main()
 {
   test_pr108846();
   test_move_only();
+  test_move_only_trivial();
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc
index 035743560e0..92ac0f5bae5 100644
--- a/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc
@@ -26,6 +26,37 @@ test_pr108846()
     // If this is optimized to memmove it will overwrite tail padding.
     std::move_backward(src, src+1, dst+1);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::move_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#endif
+}
+
+struct B2 {
+    B2(int i, short j) : i(i), j(j) {}
+    B2& operator=(B2&& b) { i = b.i; j = b.j; return *this; }
+    int i;
+    short j;
+};
+struct D2 : B2 {
+    D2(int i, short j, short x) : B2(i, j), x(x) {}
+    short x; // Stored in tail padding of B2
+};
+
+void
+test_move_only()
+{
+    D2 ddst(1, 2, 3);
+    D2 dsrc(4, 5, 6);
+    B2 *dst = &ddst;
+    B2 *src = &dsrc;
+    // Ensure the not-taken trivial copy path works for this type.
+    std::move_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::move_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 struct B3 {
@@ -40,7 +71,7 @@ struct D3 : B3 {
 };
 
 void
-test_move_only()
+test_move_only_trivial()
 {
     D3 ddst(1, 2, 3);
     D3 dsrc(4, 5, 6);
@@ -49,10 +80,15 @@ test_move_only()
     // Ensure the not-taken trivial copy path works for this type.
     std::move_backward(src, src+1, dst+1);
     VERIFY(ddst.x == 3);
+#if __cpp_lib_ranges >= 201911L
+    std::ranges::move_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+#endif
 }
 
 int main()
 {
   test_pr108846();
   test_move_only();
+  test_move_only_trivial();
 }