[gcc r11-9441] libstdc++: Fix std::char_traits<C>::move for constexpr

[gcc r11-9441] libstdc++: Fix std::char_traits<C>::move for constexpr

[Jonathan Wakely]

https://gcc.gnu.org/g:226210894e53259940a8e1453125e37c65299ba4

commit r11-9441-g226210894e53259940a8e1453125e37c65299ba4
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Nov 18 12:39:20 2021 +0000

    libstdc++: Fix std::char_traits<C>::move for constexpr
    
    The constexpr branch in __gnu_cxx::char_traits::move compares the string
    arguments to see if they overlap, but relational comparisons between
    unrelated pointers are not core constant expressions.
    
    I want to replace the comparisons with a loop using pointer equality to
    determine whether the end of the source string is in the destination
    string. However, that doesn't work with GCC, due to PR c++/89074 so
    allocate a temporary buffer instead and copy out into that first, so
    that overlapping source and destination don't matter. The allocation
    isn't supported by the current Intel icc so use the loop as a fallback.
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/char_traits.h (__gnu_cxx::char_traits::move):
            Do not compare unrelated pointers during constant evaluation.
            * testsuite/21_strings/char_traits/requirements/constexpr_functions_c++20.cc:
            Improve tests for char_traits::move.
    
    (cherry picked from commit ca243ada71656651a8753e88164a1f0f019be1c3)

Diff:
---
 libstdc++-v3/include/bits/char_traits.h            | 40 ++++++++++++++++++----
 .../requirements/constexpr_functions_c++20.cc      | 23 +++++++++++--
 2 files changed, 54 insertions(+), 9 deletions(-)

diff --git a/libstdc++-v3/include/bits/char_traits.h b/libstdc++-v3/include/bits/char_traits.h
index c143d74a9ba..faccb7ba784 100644
--- a/libstdc++-v3/include/bits/char_traits.h
+++ b/libstdc++-v3/include/bits/char_traits.h
@@ -192,18 +192,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       if (__n == 0)
 	return __s1;
-#ifdef __cpp_lib_is_constant_evaluated
+#if __cpp_lib_is_constant_evaluated
       if (std::is_constant_evaluated())
 	{
-	  if (__s1 > __s2 && __s1 < __s2 + __n)
-	    std::copy_backward(__s2, __s2 + __n, __s1 + __n);
+	  if (__s1 == __s2) // unlikely, but saves a lot of work
+	    return __s1;
+#if __cpp_constexpr_dynamic_alloc
+	  // The overlap detection below fails due to PR c++/89074,
+	  // so use a temporary buffer instead.
+	  char_type* __tmp = new char_type[__n];
+	  copy(__tmp, __s2, __n);
+	  copy(__s1, __tmp, __n);
+	  delete[] __tmp;
+#else
+	  const auto __end = __s2 + __n - 1;
+	  bool __overlap = false;
+	  for (std::size_t __i = 0; __i < __n - 1; ++__i)
+	    {
+	      if (__s1 + __i == __end)
+		{
+		  __overlap = true;
+		  break;
+		}
+	    }
+	  if (__overlap)
+	    {
+	      do
+		{
+		  --__n;
+		  assign(__s1[__n], __s2[__n]);
+		}
+	      while (__n > 0);
+	    }
 	  else
-	    std::copy(__s2, __s2 + __n, __s1);
+	    copy(__s1, __s2, __n);
+#endif
 	  return __s1;
 	}
 #endif
-      return static_cast<_CharT*>(__builtin_memmove(__s1, __s2,
-						    __n * sizeof(char_type)));
+      __builtin_memmove(__s1, __s2, __n * sizeof(char_type));
+      return __s1;
     }
 
   template<typename _CharT>
diff --git a/libstdc++-v3/testsuite/21_strings/char_traits/requirements/constexpr_functions_c++20.cc b/libstdc++-v3/testsuite/21_strings/char_traits/requirements/constexpr_functions_c++20.cc
index 0d1595fe030..0fb461a2a3b 100644
--- a/libstdc++-v3/testsuite/21_strings/char_traits/requirements/constexpr_functions_c++20.cc
+++ b/libstdc++-v3/testsuite/21_strings/char_traits/requirements/constexpr_functions_c++20.cc
@@ -1,5 +1,5 @@
-// { dg-options "-std=gnu++2a" }
-// { dg-do compile { target c++2a } }
+// { dg-options "-std=gnu++20" }
+// { dg-do compile { target c++20 } }
 
 // Copyright (C) 2017-2021 Free Software Foundation, Inc.
 //
@@ -25,9 +25,26 @@ template<typename CT>
   test_move()
   {
     using char_type = typename CT::char_type;
+
+    // Overlapping strings
     char_type s1[3] = {1, 2, 3};
     CT::move(s1+1, s1, 2);
-    return s1[0]==char_type{1} && s1[1]==char_type{1} && s1[2]==char_type{2};
+    if (s1[0] != char_type{1} || s1[1] != char_type{1} || s1[2] != char_type{2})
+      throw 1;
+    CT::move(s1, s1+1, 2);
+    if (s1[0] != char_type{1} || s1[1] != char_type{2} || s1[2] != char_type{2})
+      throw 2;
+
+    // Disjoint strings
+    char_type why_is_six_scared_of_seven[] = {4, 5, 6};
+    char_type because789[] = {7, 8, 9};
+    CT::move(why_is_six_scared_of_seven, because789, 3);
+    if (why_is_six_scared_of_seven[0] != char_type{7}
+	|| why_is_six_scared_of_seven[1] != char_type{8}
+	|| why_is_six_scared_of_seven[2] != char_type{9})
+      throw 3;
+
+    return true;
   }
 
 #ifndef __cpp_lib_constexpr_string