libstdc++: Begin lifetime of chars in constexpr std::string [PR103295]

Clang gives errors for constexpr std::string because the memory returned
by std::allocator<T>::allocate does not contain any objects yet, and
attempting to set them using char_traits::assign or char_traits::copy
fails with:

assignment to object outside its lifetime is not allowed in a constant expression
              *__result = *__first;
                        ^
This adds code to std::char_traits to use std::construct_at to begin
lifetimes when called during constant evaluation. To support
specializations of std::basic_string that don't use std::char_traits
there is now another layer of wrapper around the allocator_traits, so
that the lifetime of characters is begun as soon as the memory is
allocated. By doing it in the char traits and allocator traits, the rest
of basic_string can ignore the problem.

While modifying char_traits::copy and char_traits::assign to begin
lifetimes for the constexpr cases, I also replaced their uses of
std::copy and std::fill_n respectively. That means we don't need
<bits/stl_algobase.h> for char_traits.

libstdc++-v3/ChangeLog:

	PR libstdc++/103295
	* include/bits/basic_string.h (_Alloc_traits): Replace typedef
	with struct for C++20 mode.
	* include/bits/basic_string.tcc (_M_replace): Use _Alloc_traits
	for allocation.
	* include/bits/char_traits.h (__gnu_cxx::char_traits::assign):
	Use std::_Construct during constant evaluation.
	(__gnu_cxx::char_traits::assign(CharT*, const CharT*, size_t)):
	Likewise. Replace std::fill_n with memset or manual loop.
	(__gnu_cxx::char_traits::copy): Likewise, replacing std::copy
	with memcpy.
	* include/ext/vstring.h: Include <bits/stl_algobase.h> for
	std::min.
	* include/std/string_view: Likewise.
	* testsuite/21_strings/basic_string/capacity/char/resize_and_overwrite.cc:
	Add constexpr test.

6 files changed, 141 insertions, 15 deletions

diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index d29c9cd..6e7de73 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -87,7 +87,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
     {
       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
 	rebind<_CharT>::other _Char_alloc_type;
+
+#if __cpp_lib_constexpr_string < 201907L
       typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
+#else
+      template<typename _Traits2, typename _Dummy_for_PR85282>
+	struct _Alloc_traits_impl : __gnu_cxx::__alloc_traits<_Char_alloc_type>
+	{
+	  typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Base;
+
+	  [[__gnu__::__always_inline__]]
+	  static constexpr typename _Base::pointer
+	  allocate(_Char_alloc_type& __a, typename _Base::size_type __n)
+	  {
+	    pointer __p = _Base::allocate(__a, __n);
+	    if (__builtin_is_constant_evaluated())
+	      // Begin the lifetime of characters in allocated storage.
+	      for (size_type __i = 0; __i < __n; ++__i)
+		std::construct_at(__builtin_addressof(__p[__i]));
+	    return __p;
+	  }
+	};
+
+      template<typename _Dummy_for_PR85282>
+	struct _Alloc_traits_impl<char_traits<_CharT>, _Dummy_for_PR85282>
+	: __gnu_cxx::__alloc_traits<_Char_alloc_type>
+	{
+	  // std::char_traits begins the lifetime of characters.
+	};
+
+      using _Alloc_traits = _Alloc_traits_impl<_Traits, void>;
+#endif
 
       // Types:
     public:
@@ -485,7 +515,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       basic_string()
       _GLIBCXX_NOEXCEPT_IF(is_nothrow_default_constructible<_Alloc>::value)
       : _M_dataplus(_M_local_data())
-      { _M_set_length(0); }
+      {
+	_M_use_local_data();
+	_M_set_length(0);
+      }
 
       /**
        *  @brief  Construct an empty string using allocator @a a.
@@ -494,7 +527,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       explicit
       basic_string(const _Alloc& __a) _GLIBCXX_NOEXCEPT
       : _M_dataplus(_M_local_data(), __a)
-      { _M_set_length(0); }
+      {
+	_M_use_local_data();
+	_M_set_length(0);
+      }
 
       /**
        *  @brief  Construct string with copy of value of @a __str.
diff --git a/libstdc++-v3/include/bits/basic_string.tcc b/libstdc++-v3/include/bits/basic_string.tcc
index 9a54b63..374406c 100644
--- a/libstdc++-v3/include/bits/basic_string.tcc
+++ b/libstdc++-v3/include/bits/basic_string.tcc
@@ -490,7 +490,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cpp_lib_is_constant_evaluated
 	  if (__builtin_is_constant_evaluated())
 	    {
-	      auto __newp = this->_M_get_allocator().allocate(__new_size);
+	      auto __newp = _Alloc_traits::allocate(_M_get_allocator(),
+						    __new_size);
 	      _S_copy(__newp, this->_M_data(), __pos);
 	      _S_copy(__newp + __pos, __s, __len2);
 	      _S_copy(__newp + __pos + __len2, __p + __len1, __how_much);
@@ -569,6 +570,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{
 	  __p = _M_create(__n, __capacity);
 	  this->_S_copy(__p, _M_data(), length()); // exclude trailing null
+#if __cpp_lib_is_constant_evaluated
+	  if (__builtin_is_constant_evaluated())
+	    traits_type::assign(__p + length(), __n - length(), _CharT());
+#endif
 	  _M_dispose();
 	  _M_data(__p);
 	  _M_capacity(__n);
diff --git a/libstdc++-v3/include/bits/char_traits.h b/libstdc++-v3/include/bits/char_traits.h
index 3c9f4ad..b1cdc55 100644
--- a/libstdc++-v3/include/bits/char_traits.h
+++ b/libstdc++-v3/include/bits/char_traits.h
@@ -36,11 +36,11 @@
 
 #pragma GCC system_header
 
-#include <bits/stl_algobase.h>  // std::copy, std::fill_n
 #include <bits/postypes.h>      // For streampos
 #include <cwchar>               // For WEOF, wmemmove, wmemset, etc.
-#if __cplusplus > 201703L
+#if __cplusplus >= 202002L
 # include <compare>
+# include <bits/stl_construct.h>
 #endif
 
 #ifndef _GLIBCXX_ALWAYS_INLINE
@@ -100,7 +100,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       static _GLIBCXX14_CONSTEXPR void
       assign(char_type& __c1, const char_type& __c2)
-      { __c1 = __c2; }
+      {
+#if __cpp_constexpr_dynamic_alloc && __cpp_lib_is_constant_evaluated
+	if (std::is_constant_evaluated())
+	  std::construct_at(__builtin_addressof(__c1), __c2);
+	else
+#endif
+	__c1 = __c2;
+      }
 
       static _GLIBCXX_CONSTEXPR bool
       eq(const char_type& __c1, const char_type& __c2)
@@ -240,8 +247,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     char_traits<_CharT>::
     copy(char_type* __s1, const char_type* __s2, std::size_t __n)
     {
-      // NB: Inline std::copy so no recursive dependencies.
-      std::copy(__s2, __s2 + __n, __s1);
+#if __cpp_lib_is_constant_evaluated
+      if (std::is_constant_evaluated())
+	{
+	  for (std::size_t __i = 0; __i < __n; ++__i)
+	    std::construct_at(__s1 + __i, __s2[__i]);
+	  return __s1;
+	}
+#endif
+
+      __builtin_memcpy(__s1, __s2, __n * sizeof(char_type));
       return __s1;
     }
 
@@ -251,8 +266,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     char_traits<_CharT>::
     assign(char_type* __s, std::size_t __n, char_type __a)
     {
-      // NB: Inline std::fill_n so no recursive dependencies.
-      std::fill_n(__s, __n, __a);
+#if __cpp_lib_is_constant_evaluated
+      if (std::is_constant_evaluated())
+	{
+	  for (std::size_t __i = 0; __i < __n; ++__i)
+	    std::construct_at(__s + __i, __a);
+	  return __s;
+	}
+#endif
+
+      if _GLIBCXX17_CONSTEXPR (sizeof(_CharT) == 1 && __is_trivial(_CharT))
+	{
+	  unsigned char __c;
+	  __builtin_memcpy(&__c, __builtin_addressof(__a), 1);
+	  __builtin_memset(__s, __c, __n);
+	}
+      else
+	{
+	  for (std::size_t __i = 0; __i < __n; ++__i)
+	    __s[__i] = __a;
+	}
       return __s;
     }
 
@@ -304,7 +337,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       static _GLIBCXX17_CONSTEXPR void
       assign(char_type& __c1, const char_type& __c2) _GLIBCXX_NOEXCEPT
-      { __c1 = __c2; }
+      {
+#if __cpp_constexpr_dynamic_alloc && __cpp_lib_is_constant_evaluated
+	if (std::is_constant_evaluated())
+	  std::construct_at(__builtin_addressof(__c1), __c2);
+	else
+#endif
+	__c1 = __c2;
+      }
 
       static _GLIBCXX_CONSTEXPR bool
       eq(const char_type& __c1, const char_type& __c2) _GLIBCXX_NOEXCEPT
@@ -435,7 +475,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       static _GLIBCXX17_CONSTEXPR void
       assign(char_type& __c1, const char_type& __c2) _GLIBCXX_NOEXCEPT
-      { __c1 = __c2; }
+      {
+#if __cpp_constexpr_dynamic_alloc && __cpp_lib_is_constant_evaluated
+	if (std::is_constant_evaluated())
+	  std::construct_at(__builtin_addressof(__c1), __c2);
+	else
+#endif
+	__c1 = __c2;
+      }
 
       static _GLIBCXX_CONSTEXPR bool
       eq(const char_type& __c1, const char_type& __c2) _GLIBCXX_NOEXCEPT
@@ -556,7 +603,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       static _GLIBCXX17_CONSTEXPR void
       assign(char_type& __c1, const char_type& __c2) _GLIBCXX_NOEXCEPT
-      { __c1 = __c2; }
+      {
+#if __cpp_constexpr_dynamic_alloc && __cpp_lib_is_constant_evaluated
+	if (std::is_constant_evaluated())
+	  std::construct_at(__builtin_addressof(__c1), __c2);
+	else
+#endif
+	__c1 = __c2;
+      }
 
       static _GLIBCXX_CONSTEXPR bool
       eq(const char_type& __c1, const char_type& __c2) _GLIBCXX_NOEXCEPT
@@ -692,7 +746,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       static _GLIBCXX17_CONSTEXPR void
       assign(char_type& __c1, const char_type& __c2) noexcept
-      { __c1 = __c2; }
+      {
+#if __cpp_constexpr_dynamic_alloc && __cpp_lib_is_constant_evaluated
+	if (std::is_constant_evaluated())
+	  std::construct_at(__builtin_addressof(__c1), __c2);
+	else
+#endif
+	__c1 = __c2;
+      }
 
       static constexpr bool
       eq(const char_type& __c1, const char_type& __c2) noexcept
@@ -806,7 +867,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       static _GLIBCXX17_CONSTEXPR void
       assign(char_type& __c1, const char_type& __c2) noexcept
-      { __c1 = __c2; }
+      {
+#if __cpp_constexpr_dynamic_alloc && __cpp_lib_is_constant_evaluated
+	if (std::is_constant_evaluated())
+	  std::construct_at(__builtin_addressof(__c1), __c2);
+	else
+#endif
+	__c1 = __c2;
+      }
 
       static constexpr bool
       eq(const char_type& __c1, const char_type& __c2) noexcept
diff --git a/libstdc++-v3/include/ext/vstring.h b/libstdc++-v3/include/ext/vstring.h
index cb5872a..331282c 100644
--- a/libstdc++-v3/include/ext/vstring.h
+++ b/libstdc++-v3/include/ext/vstring.h
@@ -38,6 +38,7 @@
 #include <ext/vstring_util.h>
 #include <ext/rc_string_base.h>
 #include <ext/sso_string_base.h>
+#include <bits/stl_algobase.h> // std::min
 
 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
 {
diff --git a/libstdc++-v3/include/std/string_view b/libstdc++-v3/include/std/string_view
index fd92df6..f2863c1 100644
--- a/libstdc++-v3/include/std/string_view
+++ b/libstdc++-v3/include/std/string_view
@@ -39,9 +39,11 @@
 
 #include <iosfwd>
 #include <bits/char_traits.h>
+#include <bits/functexcept.h>
 #include <bits/functional_hash.h>
 #include <bits/range_access.h>
 #include <bits/ostream_insert.h>
+#include <bits/stl_algobase.h>
 #include <ext/numeric_traits.h>
 
 #if __cplusplus >= 202002L
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/capacity/char/resize_and_overwrite.cc b/libstdc++-v3/testsuite/21_strings/basic_string/capacity/char/resize_and_overwrite.cc
index f0e8112..c9087b5 100644
--- a/libstdc++-v3/testsuite/21_strings/basic_string/capacity/char/resize_and_overwrite.cc
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/capacity/char/resize_and_overwrite.cc
@@ -105,10 +105,24 @@ test04()
   }
 }
 
+constexpr bool
+test05()
+{
+  std::string s;
+  s.resize_and_overwrite(20, [](char* p, auto n) {
+    *p = '!'; // direct assignment should be OK
+    std::char_traits<char>::copy(p, "constexpr", 9);
+    return 9;
+  });
+  VERIFY( s == "constexpr" );
+  return true;
+}
+
 int main()
 {
   test01();
   test02();
   test03();
   test04();
+  static_assert( test05() );
 }