libstdc++: Make self-move well-defined for containers [PR 85828]

The C++ LWG recently confirmed that self-move assignment should not have
undefined behaviour for standard containers (see the proposed resolution
of LWG 2839). The result should be a valid but unspecified value, just
like other times when a container is moved from.

Our std::list, std::__cxx11::basic_string and unordered containers all
have bugs which result in undefined behaviour.

For std::list the problem is that we clear the previous contents using
_M_clear() instead of clear(). This means the _M_next, _M_prev and
_M_size members are not zeroed, and so after we "update" them (with
their existing values), we are left with dangling pointers and a
non-zero size, but no elements.

For the unordered containers the problem is similar. _Hashtable first
deallocates the existing contents, then takes ownership of the pointers
from the RHS object (which has just had its contents deallocated so the
pointers are dangling).

For std::basic_string it's a little more subtle. When the string is
local (i.e. fits in the SSO buffer) we use char_traits::copy to copy the
contents from this->data() to __rhs.data(). When &__rhs == this that
copy violates the precondition that the ranges don't overlap. We only
need to check for self-move for this case where it's local, because the
only other case that can be true for self-move is that it's non-local
but the allocators compare equal. In that case the data pointer is
neither deallocated nor leaked, so the result is well-defined.

This patch also makes a small optimization for std::deque move
assignment, to use the efficient move when is_always_equal is false, but
the allocators compare equal at runtime.

Finally, we need to remove all the Debug Mode checks which abort the
program when a self-move is detected, because it's not undefined to do
that.

Before PR 85828 can be closed we should also look into fixing
std::shuffle so it doesn't do any redundant self-swaps.

libstdc++-v3/ChangeLog:

	PR libstdc++/85828
	* include/bits/basic_string.h (operator=(basic_string&&)): Check
	for self-move before copying with char_traits::copy.
	* include/bits/hashtable.h (operator=(_Hashtable&&)): Check for
	self-move.
	* include/bits/stl_deque.h (_M_move_assign1(deque&&, false_type)):
	Check for equal allocators.
	* include/bits/stl_list.h (_M_move_assign(list&&, true_type)):
	Call clear() instead of _M_clear().
	* include/debug/formatter.h (__msg_self_move_assign): Change
	comment.
	* include/debug/macros.h (__glibcxx_check_self_move_assign):
	(_GLIBCXX_DEBUG_VERIFY): Remove.
	* include/debug/safe_container.h (operator=(_Safe_container&&)):
	Remove assertion check for safe move and make it well-defined.
	* include/debug/safe_iterator.h (operator=(_Safe_iterator&&)):
	Remove assertion check for self-move.
	* include/debug/safe_local_iterator.h
	(operator=(_Safe_local_iterator&&)): Likewise.
	* testsuite/21_strings/basic_string/cons/char/self_move.cc: New test.
	* testsuite/23_containers/deque/cons/self_move.cc: New test.
	* testsuite/23_containers/forward_list/cons/self_move.cc: New test.
	* testsuite/23_containers/list/cons/self_move.cc: New test.
	* testsuite/23_containers/set/cons/self_move.cc: New test.
	* testsuite/23_containers/unordered_set/cons/self_move.cc: New test.
	* testsuite/23_containers/vector/cons/self_move.cc: New test.

16 files changed, 356 insertions, 19 deletions

diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index e34b5c1..a9fe09f 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -717,10 +717,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 
 	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());
+	    // We've always got room for a short string, just copy it
+	    // (unless this is a self-move, because that would violate the
+	    // char_traits::copy precondition that the ranges don't overlap).
+	    if (__builtin_expect(std::__addressof(__str) != this, true))
+	      {
+		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()
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index dc8ed2e..7b772a4 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -1296,6 +1296,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_move_assign(_Hashtable&& __ht, true_type)
     {
+      if (__builtin_expect(std::__addressof(__ht) == this, false))
+	return;
+
       this->_M_deallocate_nodes(_M_begin());
       _M_deallocate_buckets();
       __hashtable_base::operator=(std::move(__ht));
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 3959dd7..baebf7a 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -2156,6 +2156,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       void
       _M_move_assign1(deque&& __x, /* always equal: */ false_type)
       {
+	if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator())
+	  return _M_move_assign1(std::move(__x), true_type());
+
 	constexpr bool __move_storage =
 	  _Alloc_traits::_S_propagate_on_move_assign();
 	_M_move_assign2(std::move(__x), __bool_constant<__move_storage>());
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index e7135e3..d63a965 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -1947,7 +1947,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
       void
       _M_move_assign(list&& __x, true_type) noexcept
       {
-	this->_M_clear();
+	this->clear();
 	this->_M_move_nodes(std::move(__x));
 	std::__alloc_on_move(this->_M_get_Node_allocator(),
 			     __x._M_get_Node_allocator());
diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
index bb9b3e5..c4283fe 100644
--- a/libstdc++-v3/include/debug/formatter.h
+++ b/libstdc++-v3/include/debug/formatter.h
@@ -143,7 +143,7 @@ namespace __gnu_debug
     // unordered container local iterators
     __msg_local_iter_compare_bad,
     __msg_non_empty_range,
-    // self move assign
+    // self move assign (no longer used)
     __msg_self_move_assign,
     // unordered container buckets
     __msg_bucket_index_oob,
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index 73fb50d..ed60680 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -447,12 +447,6 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned_upper(		\
 		      ._M_iterator(_Last, #_Last)			\
 		      ._M_string(#_Pred))
 
-// Verify that the container is not self move assigned
-#define __glibcxx_check_self_move_assign(_Other)			\
-_GLIBCXX_DEBUG_VERIFY(this != &_Other,					\
-		      _M_message(__gnu_debug::__msg_self_move_assign)	\
-                      ._M_sequence(*this, "this"))
-
 // Verify that load factor is positive
 #define __glibcxx_check_max_load_factor(_F)				\
 _GLIBCXX_DEBUG_VERIFY(_F > 0.0f,					\
diff --git a/libstdc++-v3/include/debug/safe_container.h b/libstdc++-v3/include/debug/safe_container.h
index 36b3e01..2059eca 100644
--- a/libstdc++-v3/include/debug/safe_container.h
+++ b/libstdc++-v3/include/debug/safe_container.h
@@ -80,7 +80,14 @@ namespace __gnu_debug
       _Safe_container&
       operator=(_Safe_container&& __x) noexcept
       {
-	__glibcxx_check_self_move_assign(__x);
+	if (std::__addressof(__x) == this)
+	  {
+	    // Standard containers have a valid but unspecified value after
+	    // self-move, so we invalidate all debug iterators even if the
+	    // underlying container happens to preserve its contents.
+	    this->_M_invalidate_all();
+	    return *this;
+	  }
 
 	if (_IsCxx11AllocatorAware)
 	  {
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index 687b844..84a9f1d 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -263,15 +263,15 @@ namespace __gnu_debug
       _Safe_iterator&
       operator=(_Safe_iterator&& __x) noexcept
       {
-	_GLIBCXX_DEBUG_VERIFY(this != &__x,
-			      _M_message(__msg_self_move_assign)
-			      ._M_iterator(*this, "this"));
 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 			      || __x.base() == _Iterator(),
 			      _M_message(__msg_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
 
+	if (std::__addressof(__x) == this)
+	  return *this;
+
 	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 	  {
 	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h
index d0abcf6..5b051d0 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -209,15 +209,15 @@ namespace __gnu_debug
       _Safe_local_iterator&
       operator=(_Safe_local_iterator&& __x) noexcept
       {
-	_GLIBCXX_DEBUG_VERIFY(this != &__x,
-			      _M_message(__msg_self_move_assign)
-			      ._M_iterator(*this, "this"));
 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 			      || __x.base() == _Iterator(),
 			      _M_message(__msg_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
 
+	if (std::__addressof(__x) == this)
+	  return *this;
+
 	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 	  {
 	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/self_move.cc b/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/self_move.cc
new file mode 100644
index 0000000..456b033
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/self_move.cc
@@ -0,0 +1,52 @@
+// 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-do run { target c++11 } }
+
+#include <string>
+#include <debug/string>
+#include <testsuite_hooks.h>
+
+template<typename String>
+void
+test(const char* s)
+{
+  String s1 = s;
+  std::string s2 __attribute__((unused)) = s1.c_str();
+  s1 = std::move(s1);
+
+  String s3 __attribute__((unused)) = s1;
+  s1 = std::move(s1);
+
+  s1.begin(); // causes COW string to "leak"
+  s1 = std::move(s1);
+
+  String s4 __attribute__((unused)) = s1;
+  s1 = std::move(s1);
+
+  s1.reserve(2 * s1.capacity()); // causes SSO string to be on the heap
+  s1 = std::move(s1);
+}
+
+int
+main()
+{
+  test<std::string>("short");
+  test<std::string>("very, very, very, VERY long");
+  test<__gnu_debug::string>("short");
+  test<__gnu_debug::string>("very, very, very, VERY long");
+}
diff --git a/libstdc++-v3/testsuite/23_containers/deque/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/deque/cons/self_move.cc
new file mode 100644
index 0000000..e05f43c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/cons/self_move.cc
@@ -0,0 +1,44 @@
+// 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-do run { target c++11 } }
+
+#include <deque>
+#include <debug/deque>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(std::initializer_list<typename Container::value_type> vals)
+{
+  Container c{vals};
+  c = std::move(c);
+  VERIFY( c == c );
+
+  auto it = c.begin();
+  it = std::move(it);
+  VERIFY( it == c.begin() );
+}
+
+int
+main()
+{
+  test<std::deque<int>>({1, 2, 3});
+  test<std::deque<std::deque<int>>>({{1,2}, {3,4}, {5,6}, {7,8}});
+  test<__gnu_debug::deque<int>>({1, 2, 3});
+  test<__gnu_debug::deque<std::deque<int>>>({{1,2}, {3,4}});
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/forward_list/cons/self_move.cc
new file mode 100644
index 0000000..35525ca
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/cons/self_move.cc
@@ -0,0 +1,44 @@
+// 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-do run { target c++11 } }
+
+#include <forward_list>
+#include <debug/forward_list>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(std::initializer_list<typename Container::value_type> vals)
+{
+  Container c{vals};
+  c = std::move(c);
+  VERIFY( c == c );
+
+  auto it = c.begin();
+  it = std::move(it);
+  VERIFY( it == c.begin() );
+}
+
+int
+main()
+{
+  test<std::forward_list<int>>({1, 2, 3});
+  test<std::forward_list<std::forward_list<int>>>({{1,2}, {3,4}, {5,6}, {7,8}});
+  test<__gnu_debug::forward_list<int>>({1, 2, 3});
+  test<__gnu_debug::forward_list<std::forward_list<int>>>({{1,2}, {3,4}});
+}
diff --git a/libstdc++-v3/testsuite/23_containers/list/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/list/cons/self_move.cc
new file mode 100644
index 0000000..6ff6f15
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/cons/self_move.cc
@@ -0,0 +1,44 @@
+// 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-do run { target c++11 } }
+
+#include <list>
+#include <debug/list>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(std::initializer_list<typename Container::value_type> vals)
+{
+  Container c{vals};
+  c = std::move(c);
+  VERIFY( c == c );
+
+  auto it = c.begin();
+  it = std::move(it);
+  VERIFY( it == c.begin() );
+}
+
+int
+main()
+{
+  test<std::list<int>>({1, 2, 3});
+  test<std::list<std::list<int>>>({{1,2}, {3,4}, {5,6}, {7,8}});
+  test<__gnu_debug::list<int>>({1, 2, 3});
+  test<__gnu_debug::list<std::list<int>>>({{1,2}, {3,4}});
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/set/cons/self_move.cc
new file mode 100644
index 0000000..9c22662
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/self_move.cc
@@ -0,0 +1,47 @@
+// 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-do run { target c++11 } }
+
+#include <set>
+#include <debug/set>
+#include <string>
+#include <stdlib.h>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(std::initializer_list<typename Container::value_type> vals)
+{
+  Container c{vals};
+  c = std::move(c);
+  VERIFY( c == c );
+
+  auto it = c.begin();
+  it = std::move(it);
+  VERIFY( it == c.begin() );
+}
+
+int
+main()
+{
+  std::string s = "how long is a piece of SSO string?";
+  test<std::set<int>>({1, 2, 3});
+  test<std::set<std::string>>({s, s, s, s});
+  test<__gnu_debug::set<int>>({1, 2, 3});
+  test<__gnu_debug::set<std::string>>({s, s, s, s});
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/self_move.cc
new file mode 100644
index 0000000..089f2c0
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/self_move.cc
@@ -0,0 +1,50 @@
+// 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-do run { target c++11 } }
+
+#include <unordered_set>
+#include <debug/unordered_set>
+#include <string>
+#include <stdlib.h>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(std::initializer_list<typename Container::value_type> vals)
+{
+  Container c{vals};
+  c = std::move(c);
+  VERIFY( c == c );
+
+  auto it = c.begin();
+  it = std::move(it);
+  VERIFY( it == c.begin() );
+
+  auto localit = c.begin(0);
+  localit = std::move(localit);
+}
+
+int
+main()
+{
+  std::string s = "how long is a piece of SSO string?";
+  test<std::unordered_set<int>>({1, 2, 3});
+  test<std::unordered_set<std::string>>({s, s, s, s});
+  test<__gnu_debug::unordered_set<int>>({1, 2, 3});
+  test<__gnu_debug::unordered_set<std::string>>({s, s, s, s});
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/vector/cons/self_move.cc
new file mode 100644
index 0000000..02159ee
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/cons/self_move.cc
@@ -0,0 +1,44 @@
+// 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-do run { target c++11 } }
+
+#include <vector>
+#include <debug/vector>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(std::initializer_list<typename Container::value_type> vals)
+{
+  Container c{vals};
+  c = std::move(c);
+  VERIFY( c == c );
+
+  auto it = c.begin();
+  it = std::move(it);
+  VERIFY( it == c.begin() );
+}
+
+int
+main()
+{
+  test<std::vector<int>>({1, 2, 3});
+  test<std::vector<std::vector<int>>>({{1,2}, {3,4}, {5,6}, {7,8}});
+  test<__gnu_debug::vector<int>>({1, 2, 3});
+  test<__gnu_debug::vector<std::vector<int>>>({{1,2}, {3,4}});
+}