PR libstdc++/87749 fix (and optimize) string move construction

The move constructor for the SSO string uses assign(const basic_string&)
when either:

(1) the source string is "local" and so the contents of the small string
buffer need to be copied, or

(2) the allocator does not propagate and is_always_equal is false.

Case (1) is suboptimal, because the assign member is not noexcept and
the compiler isn't smart enough to see it won't actually throw in this
case. This causes extra code in the move assignment operator so that any
exception will be turned into a call to std::terminate. This can be
fixed by copying small strings inline instead of calling assign.

Case (2) is a bug, because the specific instances of the allocators
could be equal even if is_always_equal is false. This can result in an
unnecessary deep copy (and potentially-throwing allocation) when the
storage should be moved. This can be fixed by simply checking if the
allocators are equal.

	PR libstdc++/87749
	* include/bits/basic_string.h [_GLIBCXX_USE_CXX11_ABI]
	(basic_string::operator=(basic_string&&)): For short strings copy the
	buffer inline. Only fall back to using assign(const basic_string&) to
	do a deep copy when reallocation is needed.
	* testsuite/21_strings/basic_string/modifiers/assign/char/87749.cc:
	New test.
	* testsuite/21_strings/basic_string/modifiers/assign/char/
	move_assign_optim.cc: New test.
	* testsuite/21_strings/basic_string/modifiers/assign/wchar_t/87749.cc:
	New test.
	* testsuite/21_strings/basic_string/modifiers/assign/wchar_t/
	move_assign_optim.cc: New test.

git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@265493 138bc75d-0d04-0410-961f-82ee72b054a4

6 files changed, 258 insertions, 6 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 575e52a70b6..fe43ed27f67 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,19 @@
+2018-10-25  Jonathan Wakely  <jwakely@redhat.com>
+
+	PR libstdc++/87749
+	* include/bits/basic_string.h [_GLIBCXX_USE_CXX11_ABI]
+	(basic_string::operator=(basic_string&&)): For short strings copy the
+	buffer inline. Only fall back to using assign(const basic_string&) to
+	do a deep copy when reallocation is needed.
+	* testsuite/21_strings/basic_string/modifiers/assign/char/87749.cc:
+	New test.
+	* testsuite/21_strings/basic_string/modifiers/assign/char/
+	move_assign_optim.cc: New test.
+	* testsuite/21_strings/basic_string/modifiers/assign/wchar_t/87749.cc:
+	New test.
+	* testsuite/21_strings/basic_string/modifiers/assign/wchar_t/
+	move_assign_optim.cc: New test.
+
 2018-10-25  Marc Glisse  <marc.glisse@inria.fr>
 
 	PR libstdc++/87106
diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index ba94b51f616..ae6530fcdc9 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -744,20 +744,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 	// Replace allocator if POCMA is true.
 	std::__alloc_on_move(_M_get_allocator(), __str._M_get_allocator());
 
-	if (!__str._M_is_local()
-	    && (_Alloc_traits::_S_propagate_on_move_assign()
-	      || _Alloc_traits::_S_always_equal()))
+	if (__str._M_is_local())
+	  {
+	    // We've always got room for a short string, just copy it.
+	    if (__str.size())
+	      this->_S_copy(_M_data(), __str._M_data(), __str.size());
+	    _M_set_length(__str.size());
+	  }
+	else if (_Alloc_traits::_S_propagate_on_move_assign()
+	    || _Alloc_traits::_S_always_equal()
+	    || _M_get_allocator() == __str._M_get_allocator())
 	  {
+	    // Just move the allocated pointer, our allocator can free it.
 	    pointer __data = nullptr;
 	    size_type __capacity;
 	    if (!_M_is_local())
 	      {
 		if (_Alloc_traits::_S_always_equal())
 		  {
+		    // __str can reuse our existing storage.
 		    __data = _M_data();
 		    __capacity = _M_allocated_capacity;
 		  }
-		else
+		else // __str can't use it, so free it.
 		  _M_destroy(_M_allocated_capacity);
 	      }
 
@@ -772,8 +781,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 	    else
 	      __str._M_data(__str._M_local_buf);
 	  }
-	else
-	    assign(__str);
+	else // Need to do a deep copy
+	  assign(__str);
 	__str.clear();
 	return *this;
       }
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/char/87749.cc b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/char/87749.cc
new file mode 100644
index 00000000000..ef5f1e708ac
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/char/87749.cc
@@ -0,0 +1,78 @@
+// Copyright (C) 2018 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-do run { target c++11 } }
+
+// PR libstdc++/87749
+
+#include <string>
+#include <testsuite_hooks.h>
+
+bool oom = false;
+
+template<typename T>
+struct alloc
+{
+  using value_type = T;
+
+#if !_GLIBCXX_USE_CXX11_ABI
+  using size_type = unsigned long;
+  using difference_type = long;
+  using reference = T&;
+  using const_reference = T&;
+  using pointer = T*;
+  using const_pointer = const T*;
+  template<typename U>
+    struct rebind { using other = alloc<U>; };
+#endif
+
+  int not_empty = 0; // this makes is_always_equal false
+
+  alloc() = default;
+  template<typename U>
+    alloc(const alloc<U>&) { }
+
+  T* allocate(unsigned long n)
+  {
+    if (oom)
+      throw std::bad_alloc();
+    return std::allocator<T>().allocate(n);
+  }
+
+  void deallocate(T* p, unsigned long n)
+  {
+    std::allocator<T>().deallocate(p, n);
+  }
+};
+
+template<typename T, typename U>
+bool operator==(const alloc<T>&, const alloc<U>&) { return true; }
+
+template<typename T, typename U>
+bool operator!=(const alloc<T>&, const alloc<U>&) { return false; }
+
+int main()
+{
+  using string = std::basic_string<char, std::char_traits<char>, alloc<char>>;
+
+  string s = "PR libstdc++/87749 a string that is longer than a short string";
+  const auto ptr = s.c_str();
+  oom = true;
+  string ss;
+  ss = std::move(s); // allocators are equal, should not allocate new storage
+  VERIFY( ss.c_str() == ptr );
+}
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/char/move_assign_optim.cc b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/char/move_assign_optim.cc
new file mode 100644
index 00000000000..b56bc50e1c1
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/char/move_assign_optim.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2018 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 "-O1" }
+// { dg-do compile { target c++11 } }
+// { dg-final { scan-assembler-not "__throw_length_error" } }
+// { dg-final { scan-assembler-not "__throw_bad_alloc" } }
+
+#include <bits/c++config.h>
+#undef _GLIBCXX_EXTERN_TEMPLATE
+#include <string>
+
+void
+test01(std::string& target, std::string&& source)
+{
+  // The move assignment operator should be simple enough that the compiler
+  // can see that it never results in a length_error or bad_alloc exception
+  // (which would be turned into std::terminate by the noexcept on the
+  // assignment operator).
+  target = std::move(source);
+}
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/wchar_t/87749.cc b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/wchar_t/87749.cc
new file mode 100644
index 00000000000..d4062a9e637
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/wchar_t/87749.cc
@@ -0,0 +1,79 @@
+// Copyright (C) 2018 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-do run { target c++11 } }
+
+// PR libstdc++/87749
+
+#include <string>
+#include <testsuite_hooks.h>
+
+bool oom = false;
+
+template<typename T>
+struct alloc
+{
+  using value_type = T;
+
+#if !_GLIBCXX_USE_CXX11_ABI
+  using size_type = unsigned long;
+  using difference_type = long;
+  using reference = T&;
+  using const_reference = T&;
+  using pointer = T*;
+  using const_pointer = const T*;
+  template<typename U>
+    struct rebind { using other = alloc<U>; };
+#endif
+
+  int not_empty = 0; // this makes is_always_equal false
+
+  alloc() = default;
+  template<typename U>
+    alloc(const alloc<U>&) { }
+
+  T* allocate(unsigned long n)
+  {
+    if (oom)
+      throw std::bad_alloc();
+    return std::allocator<T>().allocate(n);
+  }
+
+  void deallocate(T* p, unsigned long n)
+  {
+    std::allocator<T>().deallocate(p, n);
+  }
+};
+
+template<typename T, typename U>
+bool operator==(const alloc<T>&, const alloc<U>&) { return true; }
+
+template<typename T, typename U>
+bool operator!=(const alloc<T>&, const alloc<U>&) { return false; }
+
+int main()
+{
+  using string
+    = std::basic_string<wchar_t, std::char_traits<wchar_t>, alloc<wchar_t>>;
+
+  string s = L"PR libstdc++/87749 a string that is longer than a short string";
+  const auto ptr = s.c_str();
+  oom = true;
+  string ss;
+  ss = std::move(s); // allocators are equal, should not allocate new storage
+  VERIFY( ss.c_str() == ptr );
+}
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/wchar_t/move_assign_optim.cc b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/wchar_t/move_assign_optim.cc
new file mode 100644
index 00000000000..f54ad36a5d0
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/modifiers/assign/wchar_t/move_assign_optim.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2018 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 "-O1" }
+// { dg-do compile { target c++11 } }
+// { dg-final { scan-assembler-not "__throw_length_error" } }
+// { dg-final { scan-assembler-not "__throw_bad_alloc" } }
+
+#include <bits/c++config.h>
+#undef _GLIBCXX_EXTERN_TEMPLATE
+#include <string>
+
+void
+test01(std::wstring& target, std::wstring&& source)
+{
+  // The move assignment operator should be simple enough that the compiler
+  // can see that it never results in a length_error or bad_alloc exception
+  // (which would be turned into std::terminate by the noexcept on the
+  // assignment operator).
+  target = std::move(source);
+}