libstdc++: Clear RB tree after moving elements [PR103501]

If the allocator-extended move constructor move-constructs each element
into the new container, the contents of the old container are left in
moved-from states. We cannot know if those states preserve the
container's ordering and uniqueness guarantees, so just erase all
moved-from elements.

libstdc++-v3/ChangeLog:

	PR libstdc++/103501
	* include/bits/stl_tree.h (_Rb_tree(_Rb_tree&&, false_type)):
	Clear container if elements have been moved-from.
	* testsuite/23_containers/map/allocator/move_cons.cc: Expect
	moved-from container to be empty.
	* testsuite/23_containers/multimap/allocator/move_cons.cc:
	Likewise.
	* testsuite/23_containers/multiset/allocator/103501.cc: New test.
	* testsuite/23_containers/set/allocator/103501.cc: New test.

(cherry picked from commit 056551414a328b427c4bf4955b9a3832f344685c)

5 files changed, 70 insertions, 4 deletions

diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 550195a2749..ca7a663aaef 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1644,9 +1644,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_move_data(__x, true_type());
       else
 	{
+	  constexpr bool __move = !__move_if_noexcept_cond<value_type>::value;
 	  _Alloc_node __an(*this);
-	  _M_root() =
-	    _M_copy<!__move_if_noexcept_cond<value_type>::value>(__x, __an);
+	  _M_root() = _M_copy<__move>(__x, __an);
+	  if _GLIBCXX17_CONSTEXPR (__move)
+	    __x.clear();
 	}
     }
 
diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc
index 5beb26276b0..b82d3532135 100644
--- a/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc
@@ -41,7 +41,7 @@ void test01()
   VERIFY(1 == v1.get_allocator().get_personality());
   VERIFY(2 == v2.get_allocator().get_personality());
 
-  VERIFY( v1[1].empty() );
+  VERIFY( v1.empty() );
   VERIFY( v2[1] == str );
 }
 
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc
index 91f2d0be508..37db0f005d1 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc
@@ -41,7 +41,7 @@ void test01()
   VERIFY(1 == v1.get_allocator().get_personality());
   VERIFY(2 == v2.get_allocator().get_personality());
 
-  VERIFY( v1.begin()->second.empty() );
+  VERIFY( v1.empty() );
   VERIFY( v2.begin()->second == str );
 }
 
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/103501.cc b/libstdc++-v3/testsuite/23_containers/multiset/allocator/103501.cc
new file mode 100644
index 00000000000..24f657eceba
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/103501.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++11 } }
+
+// PR libstdc++/103501
+
+#include <set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct Y
+{
+  int i;
+
+  Y(int i) : i(i) { }
+  Y(const Y& y) noexcept : i(y.i) { }
+  Y(Y&& y) noexcept : i(y.i) { y.i = -y.i; }
+
+  bool operator<(const Y& rhs) const { return i < rhs.i; }
+};
+
+int main()
+{
+  using Alloc = __gnu_test::uneq_allocator<Y>;
+  std::multiset<Y, std::less<Y>, Alloc> s1{ {1, 2, 3}, Alloc(1)};
+  std::multiset<Y, std::less<Y>, Alloc> s2{ std::move(s1), Alloc(2) };
+  const Y* prev = nullptr;
+  for (const Y& y : s1)
+  {
+    if (prev)
+      VERIFY( !(y < *prev) );
+    prev = &y;
+  }
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/103501.cc b/libstdc++-v3/testsuite/23_containers/set/allocator/103501.cc
new file mode 100644
index 00000000000..7267cf9663f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/allocator/103501.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++11 } }
+
+// PR libstdc++/103501
+
+#include <set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct X
+{
+  int i;
+
+  X(int i) : i(i) { }
+  X(const X& x) noexcept : i(x.i) { }
+  X(X&& x) noexcept : i(x.i) { x.i = -1; }
+
+  bool operator<(const X& rhs) const { return i < rhs.i; }
+};
+
+int main()
+{
+  using Alloc = __gnu_test::uneq_allocator<X>;
+  std::set<X, std::less<X>, Alloc> s1{ {1, 2, 3}, Alloc(1)};
+  std::set<X, std::less<X>, Alloc> s2{ std::move(s1), Alloc(2) };
+  const X* prev = nullptr;
+  for (const X& x : s1)
+  {
+    if (prev)
+      VERIFY( *prev < x );
+    prev = &x;
+  }
+}