Re: [PATCH] Help compiler detect invalid code

[François Dumont <frs dot dumont at gmail dot com>]

Here is a version with __detail::__copy and __detail::__copy_backward.

I prefered to introduce the __detail namespace cause __copy is quite a 
common name so putting it in __detail namespace will I hope clarify that 
it is for internal usage only.

I even hesitated to put more details into this namespace, maybe for 
another patch later.

    * include/bits/stl_algobase.h (__memmove): Replace by...
    (__detail::__copy) ...that. Return void, loop as long as __n != 0.
    (__copy_move<_IsMove, true, 
std::random_access_iterator_tag>::__copy_m):
    Adapt to use latter.
    (__detail::__copy_backward): New.
    (__copy_move_backward<_IsMove, true,
    std::random_access_iterator_tag>::__copy_m): Adapt to use latter.
    (__copy_move_backward_a): Remove std::is_constant_evaluated block.
    * testsuite/25_algorithms/copy/constexpr.cc (test): Add check on copied
    values.
    * testsuite/25_algorithms/copy_backward/constexpr.cc (test): Likewise
    and rename in test1.
    (test2): New.
    * testsuite/25_algorithms/copy/constexpr_neg.cc: New.
    * testsuite/25_algorithms/copy_backward/constexpr.cc: New.
    * testsuite/25_algorithms/equal/constexpr_neg.cc: New.
    * testsuite/25_algorithms/move/constexpr.cc: New.
    * testsuite/25_algorithms/move/constexpr_neg.cc: New.

François

On 10/10/19 10:03 PM, Jonathan Wakely wrote:
> On 01/10/19 22:05 +0200, François Dumont wrote:
> > On 9/27/19 1:24 PM, Jonathan Wakely wrote:
> > > On 20/09/19 07:08 +0200, François Dumont wrote:
> > > > I already realized that previous patch will be too controversial to 
> > > > be accepted.
> > > >
> > > > In this new version I just implement a real memmove in __memmove so
> > >
> > > A real memmove doesn't just work backwards, it needs to detect any
> > > overlaps and work forwards *or* backwards, as needed.
> > ok, good to know, I understand now why using __builtin_memcopy didn't 
> > show any performance enhancement when I tested it !
> > > I think your change will break this case:
> > >
> > > #include <algorithm>
> > >
> > > constexpr int f(int i, int j, int k)
> > > {
> > >  int arr[5] = { 0, 0, i, j, k };
> > >  std::move(arr+2, arr+5, arr);
> > >  return arr[0] + arr[1] + arr[2];
> > > }
> > >
> > > static_assert( f(1, 2, 3) == 6 );
> > >
> > > This is valid because std::move only requires that the result iterator
> > > is not in the input range, but it's OK for the two ranges to overlap.
> > >
> > > I haven't tested it, but I think with your change the array will end
> > > up containing {3, 2, 3, 2, 3} instead of {1, 2, 3, 2, 3}.
> > Indeed, I've added a std::move constexpr test in this new proposal 
> > which demonstrate that.
> >
> > C++ Standard clearly states that [copy|move]_backward is done 
> > backward. So in this new proposal I propose to add a __memcopy used 
> > in copy/move and keep __memmove for *_backward algos. Both are using 
> > __builtin_memmove as before.
>
> Then they *really* need better names now (__memmove was already a bad
> name, but now it's terrible). If the difference is that one goes
> forwards and one goes backwards, the names should reflect that.
>
> I'll review it properly tomorrow.

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 98d324827ed..dc6b3d3fc76 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -77,19 +77,22 @@ namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
+namespace __detail
+{
   /*
    * A constexpr wrapper for __builtin_memmove.
+   * When constant-evaluated performs a forward copy.
    * @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)
+    inline void
+    __copy(_Tp* __dst, const _Tp* __src, ptrdiff_t __num)
     {
 #ifdef __cpp_lib_is_constant_evaluated
       if (std::is_constant_evaluated())
 	{
-	  for(; __num > 0; --__num)
+	  for (; __num != 0; --__num)
 	    {
 	      if constexpr (_IsMove)
 		*__dst = std::move(*__src);
@@ -98,13 +101,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      ++__src;
 	      ++__dst;
 	    }
-	  return __dst;
 	}
       else
 #endif
-	return __builtin_memmove(__dst, __src, sizeof(_Tp) * __num);
-      return __dst;
+	__builtin_memmove(__dst, __src, sizeof(_Tp) * __num);
+    }
+
+  /*
+   * A constexpr wrapper for __builtin_memmove.
+   * When constant-evaluated performs a backward copy.
+   * @param __num The number of elements of type _Tp (not bytes).
+   */
+  template<bool _IsMove, typename _Tp>
+    _GLIBCXX14_CONSTEXPR
+    inline void
+    __copy_backward(_Tp* __dst, const _Tp* __src, ptrdiff_t __num)
+    {
+#ifdef __cpp_lib_is_constant_evaluated
+      if (std::is_constant_evaluated())
+	{
+	  __dst += __num;
+	  __src += __num;
+	  for (; __num != 0; --__num)
+	    {
+	      if constexpr (_IsMove)
+		*--__dst = std::move(*--__src);
+	      else
+		*--__dst = *--__src;
+	    }
+	}
+      else
+#endif
+	__builtin_memmove(__dst, __src, sizeof(_Tp) * __num);
     }
+} // namespace __detail
 
   /*
    * A constexpr wrapper for __builtin_memcmp.
@@ -446,7 +476,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 	  const ptrdiff_t _Num = __last - __first;
 	  if (_Num)
-	    std::__memmove<_IsMove>(__result, __first, _Num);
+	    std::__detail::__copy<_IsMove>(__result, __first, _Num);
 	  return __result + _Num;
 	}
     };
@@ -658,7 +688,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 	  const ptrdiff_t _Num = __last - __first;
 	  if (_Num)
-	    std::__memmove<_IsMove>(__result - _Num, __first, _Num);
+	    std::__detail::__copy_backward<_IsMove>(__result - _Num,
+						    __first, _Num);
 	  return __result - _Num;
 	}
     };
@@ -676,12 +707,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			     && __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/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/copy/constexpr.cc
index 67910b8773e..a0460603496 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy/constexpr.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/constexpr.cc
@@ -24,12 +24,12 @@
 constexpr bool
 test()
 {
-  constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  constexpr std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
   std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
 
   const auto out6 = std::copy(ca0.begin(), ca0.begin() + 8, ma0.begin() + 2);
 
-  return out6 == ma0.begin() + 10;
+  return out6 == ma0.begin() + 10 && *(ma0.begin() + 2) == 1 && *out6 == 0;
 }
 
 static_assert(test());
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/constexpr_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/constexpr_neg.cc
new file mode 100644
index 00000000000..49052467409
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/constexpr_neg.cc
@@ -0,0 +1,38 @@
+// Copyright (C) 2019 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 xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test()
+{
+  constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+  const auto out6 = std::copy(ca0.begin() + 8, ca0.begin(), ma0.begin() + 2);
+
+  return out6 == ma0.begin() + 10;
+}
+
+static_assert(test()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc
index ed7487905a8..c0e1a747832 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr.cc
@@ -22,15 +22,27 @@
 #include <array>
 
 constexpr bool
-test()
+test1()
 {
-  constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  constexpr std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
 
   std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
   const auto out7 = std::copy_backward(ca0.begin(), ca0.begin() + 8,
 				       ma0.begin() + 10);
 
-  return true;
+  return out7 == ma0.begin() + 2 && *out7 == 1 && *(ma0.begin() + 10) == 0;
 }
 
-static_assert(test());
+static_assert(test1());
+
+constexpr bool
+test2()
+{
+  std::array<int, 12> ma0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  const auto out7 = std::copy_backward(ma0.begin(), ma0.begin() + 8,
+				       ma0.begin() + 10);
+
+  return out7 == ma0.begin() + 2 && *out7 == 0 && *(ma0.begin() + 9) == 7;
+}
+
+static_assert(test2());
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr_neg.cc
new file mode 100644
index 00000000000..3dc595d239f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/constexpr_neg.cc
@@ -0,0 +1,39 @@
+// Copyright (C) 2019 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 xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test()
+{
+  constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+  const auto out7 = std::copy_backward(ca0.begin() + 8, ca0.begin(),
+				       ma0.begin() + 10);
+
+  return out7 == ma0.begin() + 2;
+}
+
+static_assert(test()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/constexpr_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/constexpr_neg.cc
new file mode 100644
index 00000000000..065ca1e89ff
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/constexpr_neg.cc
@@ -0,0 +1,49 @@
+// Copyright (C) 2019 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 xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test01()
+{
+  constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  constexpr std::array<int, 12> ca1{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+
+  const auto outa = std::equal(ca0.end(), ca0.begin(), ca1.begin());
+  return outa;
+}
+
+static_assert(test01()); // { dg-error "outside the bounds" }
+
+constexpr bool
+test02()
+{
+  constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  constexpr std::array<int, 11> ca1{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}};
+
+  const auto outa = std::equal(ca0.begin(), ca0.end(), ca1.begin());
+  return outa;
+}
+
+static_assert(test02()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/move/constexpr.cc
new file mode 100644
index 00000000000..140df5ceb2c
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/constexpr.cc
@@ -0,0 +1,47 @@
+// Copyright (C) 2019 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>
+#include <array>
+
+constexpr bool
+test1()
+{
+  constexpr std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
+  std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+  const auto out6 = std::move(ca0.begin(), ca0.begin() + 8, ma0.begin() + 2);
+
+  return out6 == ma0.begin() + 10 && *(ma0.begin() + 2) == 1 && *out6 == 0;
+}
+
+static_assert(test1());
+
+constexpr bool
+test2()
+{
+  std::array<int, 12> ca0{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}};
+
+  const auto out6 = std::move(ca0.begin() + 2, ca0.begin() + 8, ca0.begin());
+
+  return out6 == ca0.begin() + 6 && *(ca0.begin()) == 3 && *out6 == 7;
+}
+
+static_assert(test2());
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/constexpr_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move/constexpr_neg.cc
new file mode 100644
index 00000000000..333dbfae742
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/constexpr_neg.cc
@@ -0,0 +1,38 @@
+// Copyright (C) 2019 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 xfail *-*-* } }
+
+#include <algorithm>
+#include <array>
+
+constexpr bool
+test()
+{
+  constexpr std::array<int, 12> ca0{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}};
+  std::array<int, 12> ma0{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+
+  const auto out6 = std::move(ca0.begin() + 8, ca0.begin(), ma0.begin() + 2);
+
+  return out6 == ma0.begin() + 10;
+}
+
+static_assert(test()); // { dg-error "outside the bounds" }
+
+// { dg-prune-output "non-constant condition" }
+// { dg-prune-output "in 'constexpr'" }