[gcc r14-12588] libstdc++: Clear std::priority_queue after moving from it [PR118088]

[Jonathan Wakely]

https://gcc.gnu.org/g:c25979d42d6d640b6024aa9a06e50f5104d2584e

commit r14-12588-gc25979d42d6d640b6024aa9a06e50f5104d2584e
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 ada354b911db..53a9a47a2d2b 100644
--- a/libstdc++-v3/include/bits/stl_queue.h
+++ b/libstdc++-v3/include/bits/stl_queue.h
@@ -564,6 +564,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)
@@ -592,7 +612,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
 
       /**
@@ -607,8 +628,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();
+}