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

This avoids overwriting tail padding when algorithms like std::copy are
used to write a single value through a pointer to a base subobject.

The pointer arithmetic on a Base* is valid for N==1, but the copy/move
operation needs to be done using assignment, not a memmove or memcpy of
sizeof(Base) bytes.

Instead of putting a check for N==1 in all of copy, copy_n, move etc.
this adds it to the __copy_move and __copy_move_backward partial
specializations used for trivially copyable types. When N==1 those
partial specializations dispatch to new static member functions of the
partial specializations for non-trivial types, so that a copy/move
assignment is done appropriately for the _IsMove constant.

libstdc++-v3/ChangeLog:

	PR libstdc++/108846
	* include/bits/stl_algobase.h (__copy_move<false, false, RA>)
	Add __assign_one static member function.
	(__copy_move<true, false, RA>): Likewise.
	(__copy_move<IsMove, true, RA>): Do not use memmove for a single
	value.
	(__copy_move_backward<IsMove, true, RA>): Likewise.
	* testsuite/25_algorithms/copy/108846.cc: New test.
	* testsuite/25_algorithms/copy_backward/108846.cc: New test.
	* testsuite/25_algorithms/copy_n/108846.cc: New test.
	* testsuite/25_algorithms/move/108846.cc: New test.
	* testsuite/25_algorithms/move_backward/108846.cc: New test.

6 files changed, 314 insertions, 22 deletions

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index a30fc29..4a6f8195d 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -391,6 +391,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  return __result;
 	}
+
+      template<typename _Tp, typename _Up>
+	static void
+	__assign_one(_Tp* __to, _Up* __from)
+	{ *__to = *__from; }
     };
 
 #if __cplusplus >= 201103L
@@ -411,27 +416,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  return __result;
 	}
+
+      template<typename _Tp, typename _Up>
+	static void
+	__assign_one(_Tp* __to, _Up* __from)
+	{ *__to = std::move(*__from); }
     };
 #endif
 
   template<bool _IsMove>
     struct __copy_move<_IsMove, true, random_access_iterator_tag>
     {
-      template<typename _Tp>
+      template<typename _Tp, typename _Up>
 	_GLIBCXX20_CONSTEXPR
-	static _Tp*
-	__copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
+	static _Up*
+	__copy_m(_Tp* __first, _Tp* __last, _Up* __result)
 	{
-#if __cplusplus >= 201103L
-	  using __assignable = __conditional_t<_IsMove,
-					       is_move_assignable<_Tp>,
-					       is_copy_assignable<_Tp>>;
-	  // trivial types can have deleted assignment
-	  static_assert( __assignable::value, "type must be assignable" );
-#endif
 	  const ptrdiff_t _Num = __last - __first;
-	  if (_Num)
+	  if (__builtin_expect(_Num > 1, true))
 	    __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
+	  else if (_Num == 1)
+	    std::__copy_move<_IsMove, false, random_access_iterator_tag>::
+	      __assign_one(__result, __first);
 	  return __result + _Num;
 	}
     };
@@ -732,21 +738,17 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
   template<bool _IsMove>
     struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
     {
-      template<typename _Tp>
+      template<typename _Tp, typename _Up>
 	_GLIBCXX20_CONSTEXPR
-	static _Tp*
-	__copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
+	static _Up*
+	__copy_move_b(_Tp* __first, _Tp* __last, _Up* __result)
 	{
-#if __cplusplus >= 201103L
-	  using __assignable = __conditional_t<_IsMove,
-					       is_move_assignable<_Tp>,
-					       is_copy_assignable<_Tp>>;
-	  // trivial types can have deleted assignment
-	  static_assert( __assignable::value, "type must be assignable" );
-#endif
 	  const ptrdiff_t _Num = __last - __first;
-	  if (_Num)
+	  if (__builtin_expect(_Num > 1, true))
 	    __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
+	  else if (_Num == 1)
+	    std::__copy_move<_IsMove, false, random_access_iterator_tag>::
+	      __assign_one(__result - 1, __first);
 	  return __result - _Num;
 	}
     };
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc
new file mode 100644
index 0000000..9640289
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/108846.cc
@@ -0,0 +1,58 @@
+// { dg-do run }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/108846 std::copy, std::copy_n and std::copy_backward
+// on potentially overlapping subobjects
+
+struct B {
+    B(int i, short j) : i(i), j(j) {}
+    int i;
+    short j;
+};
+struct D : B {
+    D(int i, short j, short x) : B(i, j), x(x) {}
+    short x; // Stored in tail padding of B
+};
+
+void
+test_pr108846()
+{
+    D ddst(1, 2, 3);
+    D dsrc(4, 5, 6);
+    B *dst = &ddst;
+    B *src = &dsrc;
+    // If this is optimized to memmove it will overwrite tail padding.
+    std::copy(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+}
+
+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_non_const_copy_assign()
+{
+    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::copy(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+}
+
+int main()
+{
+  test_pr108846();
+  test_non_const_copy_assign();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc
new file mode 100644
index 0000000..84b3d5a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/108846.cc
@@ -0,0 +1,58 @@
+// { dg-do run }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/108846 std::copy, std::copy_n and std::copy_backward
+// on potentially overlapping subobjects
+
+struct B {
+    B(int i, short j) : i(i), j(j) {}
+    int i;
+    short j;
+};
+struct D : B {
+    D(int i, short j, short x) : B(i, j), x(x) {}
+    short x; // Stored in tail padding of B
+};
+
+void
+test_pr108846()
+{
+    D ddst(1, 2, 3);
+    D dsrc(4, 5, 6);
+    B *dst = &ddst;
+    B *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);
+}
+
+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_non_const_copy_assign()
+{
+    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::copy_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+}
+
+int main()
+{
+  test_pr108846();
+  test_non_const_copy_assign();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc b/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc
new file mode 100644
index 0000000..9ed43e1
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_n/108846.cc
@@ -0,0 +1,58 @@
+// { dg-do run { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/108846 std::copy, std::copy_n and std::copy_backward
+// on potentially overlapping subobjects
+
+struct B {
+    B(int i, short j) : i(i), j(j) {}
+    int i;
+    short j;
+};
+struct D : B {
+    D(int i, short j, short x) : B(i, j), x(x) {}
+    short x; // Stored in tail padding of B
+};
+
+void
+test_pr108846()
+{
+    D ddst(1, 2, 3);
+    D dsrc(4, 5, 6);
+    B *dst = &ddst;
+    B *src = &dsrc;
+    // If this is optimized to memmove it will overwrite tail padding.
+    std::copy_n(src, 1, dst);
+    VERIFY(ddst.x == 3);
+}
+
+struct B2 {
+    B2(int i, short j) : i(i), j(j) {}
+    B2& operator=(B2&) = default;
+    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_non_const_copy_assign()
+{
+    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::copy_n(src, 1, dst);
+    VERIFY(ddst.x == 3);
+}
+
+int main()
+{
+  test_pr108846();
+  test_non_const_copy_assign();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/108846.cc b/libstdc++-v3/testsuite/25_algorithms/move/108846.cc
new file mode 100644
index 0000000..8248b87
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/108846.cc
@@ -0,0 +1,58 @@
+// { dg-do run { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/108846 std::copy, std::copy_n and std::copy_backward
+// on potentially overlapping subobjects
+
+struct B {
+    B(int i, short j) : i(i), j(j) {}
+    int i;
+    short j;
+};
+struct D : B {
+    D(int i, short j, short x) : B(i, j), x(x) {}
+    short x; // Stored in tail padding of B
+};
+
+void
+test_pr108846()
+{
+    D ddst(1, 2, 3);
+    D dsrc(4, 5, 6);
+    B *dst = &ddst;
+    B *src = &dsrc;
+    // If this is optimized to memmove it will overwrite tail padding.
+    std::move(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+}
+
+struct B3 {
+    B3(int i, short j) : i(i), j(j) {}
+    B3& operator=(B3&&) = 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_move_only()
+{
+    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.
+    std::move(src, src+1, dst);
+    VERIFY(ddst.x == 3);
+}
+
+int main()
+{
+  test_pr108846();
+  test_move_only();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc
new file mode 100644
index 0000000..0357435
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/108846.cc
@@ -0,0 +1,58 @@
+// { dg-do run { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/108846 std::copy, std::copy_n and std::copy_backward
+// on potentially overlapping subobjects
+
+struct B {
+    B(int i, short j) : i(i), j(j) {}
+    int i;
+    short j;
+};
+struct D : B {
+    D(int i, short j, short x) : B(i, j), x(x) {}
+    short x; // Stored in tail padding of B
+};
+
+void
+test_pr108846()
+{
+    D ddst(1, 2, 3);
+    D dsrc(4, 5, 6);
+    B *dst = &ddst;
+    B *src = &dsrc;
+    // If this is optimized to memmove it will overwrite tail padding.
+    std::move_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+}
+
+struct B3 {
+    B3(int i, short j) : i(i), j(j) {}
+    B3& operator=(B3&&) = 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_move_only()
+{
+    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.
+    std::move_backward(src, src+1, dst+1);
+    VERIFY(ddst.x == 3);
+}
+
+int main()
+{
+  test_pr108846();
+  test_move_only();
+}