[gcc r13-10312] libstdc++: Clear std::priority_queue after moving from it [PR118088]

[Jonathan Wakely]

https://gcc.gnu.org/g:5d54e351e405e872be47352611bd1b6ea285b00c

commit r13-10312-g5d54e351e405e872be47352611bd1b6ea285b00c
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Sat Dec 14 01:17:27 2024 +0000

    libstdc++: Clear std::priority_queue after moving from it [PR118088]
    
    We don't know what state an arbitrary sequence container will be in
    after moving from it, so a moved-from std::priority_queue needs to clear
    the moved-from container to ensure it doesn't contain elements that are
    in an invalid order for the queue. An alternative would be to call
    std::make_heap again to re-establish the rvalue queue's invariant, but
    that could potentially cause an exception to be thrown. Just clearing it
    so the sequence is empty seems safer and more likely to match user
    expectations.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/118088
            * include/bits/stl_queue.h (priority_queue(priority_queue&&)):
            Clear the source object after moving from it.
            (priority_queue(priority_queue&&, const Alloc&)): Likewise.
            (operator=(priority_queue&&)): Likewise.
            * testsuite/23_containers/priority_queue/118088.cc: New test.
    
    Reviewed-by: Patrick Palka <ppalka@redhat.com>
    (cherry picked from commit 15aab0d00ca1ed5ce428555bf89ecfe0525f9b81)

Diff:
---
 libstdc++-v3/include/bits/stl_queue.h              | 26 ++++++-
 .../23_containers/priority_queue/118088.cc         | 83 ++++++++++++++++++++++
 2 files changed, 106 insertions(+), 3 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h
index 8a8dc95f8896..88e1a6268d6d 100644
--- a/libstdc++-v3/include/bits/stl_queue.h
+++ b/libstdc++-v3/include/bits/stl_queue.h
@@ -566,6 +566,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : c(std::move(__s)), comp(__x)
       { std::make_heap(c.begin(), c.end(), comp); }
 
+      priority_queue(const priority_queue&) = default;
+      priority_queue& operator=(const priority_queue&) = default;
+
+      priority_queue(priority_queue&& __q)
+      noexcept(__and_<is_nothrow_move_constructible<_Sequence>,
+		      is_nothrow_move_constructible<_Compare>>::value)
+      : c(std::move(__q.c)), comp(std::move(__q.comp))
+      { __q.c.clear(); }
+
+      priority_queue&
+      operator=(priority_queue&& __q)
+      noexcept(__and_<is_nothrow_move_assignable<_Sequence>,
+		      is_nothrow_move_assignable<_Compare>>::value)
+      {
+	c = std::move(__q.c);
+	__q.c.clear();
+	comp = std::move(__q.comp);
+	return *this;
+      }
+
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	explicit
 	priority_queue(const _Alloc& __a)
@@ -594,7 +614,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	priority_queue(priority_queue&& __q, const _Alloc& __a)
-	: c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
+	: c(std::move(__q.c), __a), comp(std::move(__q.comp))
+	{ __q.c.clear(); }
 #endif
 
       /**
@@ -609,8 +630,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        *  the copy according to @a __x.
        *
        *  For more information on function objects, see the
-       *  documentation on @link functors functor base
-       *  classes@endlink.
+       *  documentation on @link functors functor base classes@endlink.
        */
 #if __cplusplus < 201103L
       template<typename _InputIterator>
diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/118088.cc b/libstdc++-v3/testsuite/23_containers/priority_queue/118088.cc
new file mode 100644
index 000000000000..b59175d8786a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/priority_queue/118088.cc
@@ -0,0 +1,83 @@
+// { dg-do run { target c++11 } }
+
+#include <queue>
+#include <vector>
+#include <testsuite_hooks.h>
+
+template<typename T, typename Seq>
+bool
+check(std::priority_queue<T, Seq>& p)
+{
+  if (!p.empty())
+    {
+      T prev = p.top();
+      p.pop();
+      while (!p.empty())
+	{
+	  if ( prev < p.top() )
+	    return false;
+	  prev = p.top();
+	  p.pop();
+	}
+    }
+  return true;
+}
+
+// A vector-like type that has a non-empty moved-from state.
+struct Vector : std::vector<int>
+{
+  using Base = std::vector<int>;
+
+  using Base::Base;
+
+  Vector(const Vector&) = default;
+  Vector& operator=(const Vector&) = default;
+
+  Vector(Vector&& v) : Base(static_cast<const Base&>(v))
+  {
+    invalidate_heap(v);
+  }
+
+  Vector(Vector&& v, const std::allocator<int>&)
+  : Base(static_cast<const Base&>(v))
+  {
+    invalidate_heap(v);
+  }
+
+  Vector&
+  operator=(Vector&& v)
+  {
+    static_cast<Base&>(*this) = static_cast<const Base&>(v);
+    invalidate_heap(v);
+    return *this;
+  }
+
+  void invalidate_heap(Base& v) { v = {1,2,3}; }
+};
+
+void
+test_moves()
+{
+  std::priority_queue<int, Vector> p;
+  p.push(1);
+  p.push(3);
+  p.push(5);
+  p.push(2);
+  p.push(2);
+  p.push(2);
+  p.push(2);
+  std::priority_queue<int, Vector> p2 = std::move(p);
+  VERIFY( check(p) );
+
+  // Allocator-extended move constructor:
+  std::priority_queue<int, Vector> p3(std::move(p2), std::allocator<int>());
+  VERIFY( check(p2) );
+
+  p2 = std::move(p3);
+  VERIFY( check(p3) );
+}
+
+int main()
+{
+  test_moves();
+}