[committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 918 bytes --]

The std::move and std::move_backward algorithms dispatch to the
std::__memmove helper when appropriate. That function uses a
pointer-to-const for the source values, preventing them from being
moved. The two callers of that function have the same problem.

Rather than altering __memmove and its callers to work with const or
non-const source pointers, this takes a more conservative approach of
casting away the const at the point where we want to do a move
assignment. This relies on the fact that we only use __memmove when the
type is trivially copyable, so we know the move assignment doesn't alter
the source anyway.

	PR libstdc++/93872
	* include/bits/stl_algobase.h (__memmove): Cast away const before
	doing move assignment.
	* testsuite/25_algorithms/move/93872.cc: New test.
	* testsuite/25_algorithms/move_backward/93872.cc: New test.

Tested powerpc64le-linux, committed to master.



[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 3329 bytes --]

commit 5b904f175ff26269615f148459a8604f45880591
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Feb 25 12:21:44 2020 +0000

    libstdc++: Fix regression in std::move algorithm (PR 93872)
    
    The std::move and std::move_backward algorithms dispatch to the
    std::__memmove helper when appropriate. That function uses a
    pointer-to-const for the source values, preventing them from being
    moved. The two callers of that function have the same problem.
    
    Rather than altering __memmove and its callers to work with const or
    non-const source pointers, this takes a more conservative approach of
    casting away the const at the point where we want to do a move
    assignment. This relies on the fact that we only use __memmove when the
    type is trivially copyable, so we know the move assignment doesn't alter
    the source anyway.
    
            PR libstdc++/93872
            * include/bits/stl_algobase.h (__memmove): Cast away const before
            doing move assignment.
            * testsuite/25_algorithms/move/93872.cc: New test.
            * testsuite/25_algorithms/move_backward/93872.cc: New test.

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index efda15f816e..c6b7148b39c 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -95,7 +95,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  for(; __num > 0; --__num)
 	    {
 	      if constexpr (_IsMove)
-		*__dst = std::move(*__src);
+		// This const_cast looks unsafe, but we only use this function
+		// for trivially-copyable types, which means this assignment
+		// is trivial and so doesn't alter the source anyway.
+		// See PR 93872 for why it's needed.
+		*__dst = std::move(*const_cast<_Tp*>(__src));
 	      else
 		*__dst = *__src;
 	      ++__src;
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/93872.cc b/libstdc++-v3/testsuite/25_algorithms/move/93872.cc
new file mode 100644
index 00000000000..c4dd43dfb64
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/93872.cc
@@ -0,0 +1,39 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a } }
+
+#include <algorithm>
+
+struct X
+{
+  X() = default;
+
+  X(const X&) = delete;
+  X& operator=(const X&) = delete;
+
+  X(X&&) = default;
+  X& operator=(X&&) = default;
+};
+
+void
+test01()
+{
+  X a[2], b[2];
+  std::move(std::begin(a), std::end(a), std::begin(b));
+}

Re: [committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1033 bytes --]

On 25/02/20 12:40 +0000, Jonathan Wakely wrote:
>The std::move and std::move_backward algorithms dispatch to the
>std::__memmove helper when appropriate. That function uses a
>pointer-to-const for the source values, preventing them from being
>moved. The two callers of that function have the same problem.
>
>Rather than altering __memmove and its callers to work with const or
>non-const source pointers, this takes a more conservative approach of
>casting away the const at the point where we want to do a move
>assignment. This relies on the fact that we only use __memmove when the
>type is trivially copyable, so we know the move assignment doesn't alter
>the source anyway.
>
>	PR libstdc++/93872
>	* include/bits/stl_algobase.h (__memmove): Cast away const before
>	doing move assignment.
>	* testsuite/25_algorithms/move/93872.cc: New test.
>	* testsuite/25_algorithms/move_backward/93872.cc: New test.
>

Oops, I forgot to 'git add' one of the new tests.

Tested x86_64-linux, committed to master.


[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 1789 bytes --]

commit 6de946e65c9558515a2c31be76853ae7653d4fc9
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Feb 25 12:42:03 2020 +0000

    libstdc++: Add test accidentally left out of previous commit
    
            * testsuite/25_algorithms/move_backward/93872.cc: Add test left out of
            previous commit.

diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/93872.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/93872.cc
new file mode 100644
index 00000000000..69774fa86c6
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/93872.cc
@@ -0,0 +1,39 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a } }
+
+#include <algorithm>
+
+struct X
+{
+  X() = default;
+
+  X(const X&) = delete;
+  X& operator=(const X&) = delete;
+
+  X(X&&) = default;
+  X& operator=(X&&) = default;
+};
+
+void
+test01()
+{
+  X a[2], b[2];
+  std::move_backward(std::begin(a), std::end(a), std::begin(b));
+}

Re: [committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 2090 bytes --]

On 25/02/20 12:40 +0000, Jonathan Wakely wrote:
>The std::move and std::move_backward algorithms dispatch to the
>std::__memmove helper when appropriate. That function uses a
>pointer-to-const for the source values, preventing them from being
>moved. The two callers of that function have the same problem.
>
>Rather than altering __memmove and its callers to work with const or
>non-const source pointers, this takes a more conservative approach of
>casting away the const at the point where we want to do a move
>assignment. This relies on the fact that we only use __memmove when the
>type is trivially copyable, so we know the move assignment doesn't alter
>the source anyway.
>
>	PR libstdc++/93872
>	* include/bits/stl_algobase.h (__memmove): Cast away const before
>	doing move assignment.
>	* testsuite/25_algorithms/move/93872.cc: New test.
>	* testsuite/25_algorithms/move_backward/93872.cc: New test.

I think what I'd really like to do is get rid of __memmove entirely.
We already have code that does the explicit assignment in a loop, for
the cases where we can't use __builtin_memmove because the type is not
trivially copyable.

We should just use that existing code during constant evaluation, i.e.
don't do the __builtin_memmove optimizations during constant
evaluation. It seems much cleaner to just not use the optimization
rather than wrap it to be usable in constant expressions.

We already have to do that for {copy,move}_backward anyway, because
__memmove doesn't correctly implement the std::memmove semantics for
overlapping ranges. But we do it **wrong** and turn copy_backward into
move_backward during constant evaluation.

Here's a patch that gets rid of __memmove and fixes that bug
(generated with 'git diff -b' so that the changes to the logic aren't
obscured by the whitespace changes caused by re-indenting).

Maybe I should just go ahead and do this now, since __memmove (and the
problems it causes) are new for GCC 10 anyway. That would revert
<bits/stl_algobase.h> to something closer to the GCC 9 version.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 6999 bytes --]

diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h
index 73f0205ba7f..feb6c5723dd 100644
--- a/libstdc++-v3/include/bits/ranges_algobase.h
+++ b/libstdc++-v3/include/bits/ranges_algobase.h
@@ -248,6 +248,10 @@ namespace ranges
 	}
       else if constexpr (sized_sentinel_for<_Sent, _Iter>)
 	{
+#ifdef __cpp_lib_is_constant_evaluated
+	  if (!std::is_constant_evaluated())
+#endif
+	    {
 	      using _ValueTypeI = iter_value_t<_Iter>;
 	      using _ValueTypeO = typename iterator_traits<_Out>::value_type;
 	      constexpr bool __use_memmove
@@ -263,11 +267,12 @@ namespace ranges
 		      : is_copy_assignable_v<_ValueTypeI>);
 		  auto __num = __last - __first;
 		  if (__num)
-		std::__memmove<_IsMove>(__result, __first, __num);
+		    __builtin_memmove(__result, __first,
+			sizeof(_ValueTypeI) * __num);
 		  return {__first + __num, __result + __num};
 		}
-	  else
-	    {
+	    }
+
 	  for (auto __n = __last - __first; __n > 0; --__n)
 	    {
 	      if constexpr (_IsMove)
@@ -279,7 +284,6 @@ namespace ranges
 	    }
 	  return {std::move(__first), std::move(__result)};
 	}
-	}
       else
 	{
 	  while (__first != __last)
@@ -385,6 +389,10 @@ namespace ranges
 	}
       else if constexpr (sized_sentinel_for<_Sent, _Iter>)
 	{
+#ifdef __cpp_lib_is_constant_evaluated
+	  if (!std::is_constant_evaluated())
+#endif
+	    {
 	      using _ValueTypeI = iter_value_t<_Iter>;
 	      using _ValueTypeO = typename iterator_traits<_Out>::value_type;
 	      constexpr bool __use_memmove
@@ -399,11 +407,12 @@ namespace ranges
 		      : is_copy_assignable_v<_ValueTypeI>);
 		  auto __num = __last - __first;
 		  if (__num)
-		std::__memmove<_IsMove>(__result - __num, __first, __num);
+		    __builtin_memmove(__result - __num, __first,
+				      sizeof(_ValueTypeI) * __num);
 		  return {__first + __num, __result - __num};
 		}
-	  else
-	    {
+	    }
+
 	  auto __lasti = ranges::next(__first, __last);
 	  auto __tail = __lasti;
 
@@ -418,7 +427,6 @@ namespace ranges
 	    }
 	  return {std::move(__lasti), std::move(__result)};
 	}
-	}
       else
 	{
 	  auto __lasti = ranges::next(__first, __last);
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index c6b7148b39c..268569336b0 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -80,39 +80,6 @@ namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
-  /*
-   * A constexpr wrapper for __builtin_memmove.
-   * @param __num The number of elements of type _Tp (not bytes).
-   */
-  template<bool _IsMove, typename _Tp>
-    _GLIBCXX14_CONSTEXPR
-    inline void*
-    __memmove(_Tp* __dst, const _Tp* __src, size_t __num)
-    {
-#ifdef __cpp_lib_is_constant_evaluated
-      if (std::is_constant_evaluated())
-	{
-	  for(; __num > 0; --__num)
-	    {
-	      if constexpr (_IsMove)
-		// This const_cast looks unsafe, but we only use this function
-		// for trivially-copyable types, which means this assignment
-		// is trivial and so doesn't alter the source anyway.
-		// See PR 93872 for why it's needed.
-		*__dst = std::move(*const_cast<_Tp*>(__src));
-	      else
-		*__dst = *__src;
-	      ++__src;
-	      ++__dst;
-	    }
-	  return __dst;
-	}
-      else
-#endif
-	return __builtin_memmove(__dst, __src, sizeof(_Tp) * __num);
-      return __dst;
-    }
-
   /*
    * A constexpr wrapper for __builtin_memcmp.
    * @param __num The number of elements of type _Tp (not bytes).
@@ -453,7 +420,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 	  const ptrdiff_t _Num = __last - __first;
 	  if (_Num)
-	    std::__memmove<_IsMove>(__result, __first, _Num);
+	    __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
 	  return __result + _Num;
 	}
     };
@@ -492,9 +459,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _OI
     __copy_move_a2(_II __first, _II __last, _OI __result)
     {
+      typedef typename iterator_traits<_II>::iterator_category _Category;
+#ifdef __cpp_lib_is_constant_evaluated
+      if (std::is_constant_evaluated())
+	return std::__copy_move<_IsMove, false, _Category>::
+	  __copy_m(__first, __last, __result);
+#endif
       typedef typename iterator_traits<_II>::value_type _ValueTypeI;
       typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
-      typedef typename iterator_traits<_II>::iterator_category _Category;
       const bool __simple = (__is_trivially_copyable(_ValueTypeI)
 			     && __is_pointer<_II>::__value
 			     && __is_pointer<_OI>::__value
@@ -719,7 +691,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 #endif
 	  const ptrdiff_t _Num = __last - __first;
 	  if (_Num)
-	    std::__memmove<_IsMove>(__result - _Num, __first, _Num);
+	    __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
 	  return __result - _Num;
 	}
     };
@@ -729,20 +701,19 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
     inline _BI2
     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
     {
+      typedef typename iterator_traits<_BI1>::iterator_category _Category;
+#ifdef __cpp_lib_is_constant_evaluated
+      if (std::is_constant_evaluated())
+	return std::__copy_move_backward<_IsMove, false, _Category>::
+	  __copy_move_b(__first, __last, __result);
+#endif
       typedef typename iterator_traits<_BI1>::value_type _ValueType1;
       typedef typename iterator_traits<_BI2>::value_type _ValueType2;
-      typedef typename iterator_traits<_BI1>::iterator_category _Category;
       const bool __simple = (__is_trivially_copyable(_ValueType1)
 			     && __is_pointer<_BI1>::__value
 			     && __is_pointer<_BI2>::__value
 			     && __are_same<_ValueType1, _ValueType2>::__value);
 
-#ifdef __cpp_lib_is_constant_evaluated
-      if (std::is_constant_evaluated())
-	return std::__copy_move_backward<true, false,
-			      _Category>::__copy_move_b(__first, __last,
-							__result);
-#endif
       return std::__copy_move_backward<_IsMove, __simple,
 				       _Category>::__copy_move_b(__first,
 								 __last,
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc
index 578ed042cce..704dcf513c0 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc
@@ -34,3 +34,21 @@ test()
 }
 
 static_assert(test());
+
+constexpr bool
+test02()
+{
+  struct X
+  {
+    X() = default;
+    X& operator=(const X&) = default;
+    constexpr X& operator=(X&& x) { i = x.i; x.i = 0; return *this; }
+    int i = 1;
+  };
+
+  X from[1], to[1];
+  std::copy_backward(std::begin(from), std::end(from), std::end(to));
+  return from[0].i == 1;
+}
+
+static_assert(test02());

Re: [committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[Ville Voutilainen]

On Tue, 25 Feb 2020 at 15:36, Jonathan Wakely <jwakely@redhat.com> wrote:
> I think what I'd really like to do is get rid of __memmove entirely.
> We already have code that does the explicit assignment in a loop, for
> the cases where we can't use __builtin_memmove because the type is not
> trivially copyable.
>
> We should just use that existing code during constant evaluation, i.e.
> don't do the __builtin_memmove optimizations during constant
> evaluation. It seems much cleaner to just not use the optimization
> rather than wrap it to be usable in constant expressions.
>
> We already have to do that for {copy,move}_backward anyway, because
> __memmove doesn't correctly implement the std::memmove semantics for
> overlapping ranges. But we do it **wrong** and turn copy_backward into
> move_backward during constant evaluation.
>
> Here's a patch that gets rid of __memmove and fixes that bug
> (generated with 'git diff -b' so that the changes to the logic aren't
> obscured by the whitespace changes caused by re-indenting).
>
> Maybe I should just go ahead and do this now, since __memmove (and the
> problems it causes) are new for GCC 10 anyway. That would revert
> <bits/stl_algobase.h> to something closer to the GCC 9 version.

Looks good to me.

Re: [committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[Jonathan Wakely]

On 25/02/20 16:01 +0200, Ville Voutilainen wrote:
>On Tue, 25 Feb 2020 at 15:36, Jonathan Wakely <jwakely@redhat.com> wrote:
>> I think what I'd really like to do is get rid of __memmove entirely.
>> We already have code that does the explicit assignment in a loop, for
>> the cases where we can't use __builtin_memmove because the type is not
>> trivially copyable.
>>
>> We should just use that existing code during constant evaluation, i.e.
>> don't do the __builtin_memmove optimizations during constant
>> evaluation. It seems much cleaner to just not use the optimization
>> rather than wrap it to be usable in constant expressions.
>>
>> We already have to do that for {copy,move}_backward anyway, because
>> __memmove doesn't correctly implement the std::memmove semantics for
>> overlapping ranges. But we do it **wrong** and turn copy_backward into
>> move_backward during constant evaluation.
>>
>> Here's a patch that gets rid of __memmove and fixes that bug
>> (generated with 'git diff -b' so that the changes to the logic aren't
>> obscured by the whitespace changes caused by re-indenting).
>>
>> Maybe I should just go ahead and do this now, since __memmove (and the
>> problems it causes) are new for GCC 10 anyway. That would revert
>> <bits/stl_algobase.h> to something closer to the GCC 9 version.
>
>Looks good to me.


I've committed it now.

It's not strictly a regression, because the bug only happens when
using std::copy_backwards in a constant expression, which never
compiled before GCC 10 anyway. But enabling it to be used in constant
expressions but with incorrect results doesn't seem useful.

Re: [committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[François Dumont]

I really like this patch but it has a little drawback related to my 
proposal:
https://gcc.gnu.org/ml/libstdc++/2019-10/msg00072.html

Now to make this code less defensive and so allow the compiler to report 
itself invalid usages in constexpr without the _GLIBCXX_DEBUG help we 
will have to change existing code, not some constexpr specific one.

François

On 2/25/20 2:36 PM, Jonathan Wakely wrote:
> On 25/02/20 12:40 +0000, Jonathan Wakely wrote:
>> The std::move and std::move_backward algorithms dispatch to the
>> std::__memmove helper when appropriate. That function uses a
>> pointer-to-const for the source values, preventing them from being
>> moved. The two callers of that function have the same problem.
>>
>> Rather than altering __memmove and its callers to work with const or
>> non-const source pointers, this takes a more conservative approach of
>> casting away the const at the point where we want to do a move
>> assignment. This relies on the fact that we only use __memmove when the
>> type is trivially copyable, so we know the move assignment doesn't alter
>> the source anyway.
>>
>>     PR libstdc++/93872
>>     * include/bits/stl_algobase.h (__memmove): Cast away const before
>>     doing move assignment.
>>     * testsuite/25_algorithms/move/93872.cc: New test.
>>     * testsuite/25_algorithms/move_backward/93872.cc: New test.
>
> I think what I'd really like to do is get rid of __memmove entirely.
> We already have code that does the explicit assignment in a loop, for
> the cases where we can't use __builtin_memmove because the type is not
> trivially copyable.
>
> We should just use that existing code during constant evaluation, i.e.
> don't do the __builtin_memmove optimizations during constant
> evaluation. It seems much cleaner to just not use the optimization
> rather than wrap it to be usable in constant expressions.
>
> We already have to do that for {copy,move}_backward anyway, because
> __memmove doesn't correctly implement the std::memmove semantics for
> overlapping ranges. But we do it **wrong** and turn copy_backward into
> move_backward during constant evaluation.
>
> Here's a patch that gets rid of __memmove and fixes that bug
> (generated with 'git diff -b' so that the changes to the logic aren't
> obscured by the whitespace changes caused by re-indenting).
>
> Maybe I should just go ahead and do this now, since __memmove (and the
> problems it causes) are new for GCC 10 anyway. That would revert
> <bits/stl_algobase.h> to something closer to the GCC 9 version.
>
>

Re: [committed] libstdc++: Fix regression in std::move algorithm (PR 93872)

[Jonathan Wakely]

On 26/02/20 07:25 +0100, François Dumont wrote:
>I really like this patch but it has a little drawback related to my 
>proposal:
>https://gcc.gnu.org/ml/libstdc++/2019-10/msg00072.html
>
>Now to make this code less defensive and so allow the compiler to 
>report itself invalid usages in constexpr without the _GLIBCXX_DEBUG 
>help we will have to change existing code, not some constexpr specific 
>one.

Hmm, yes, good point.

I still prefer to remove the buggy __memmove for now. Let's revisit
this in stage 1 though.