RE: [PATCH v2] libstdc++: Make forward_list::sort exception-safe [PR124051]

From c5b3713abef5c4c3831467a433523e282eb4010a Mon Sep 17 00:00:00 2001
From: Odysseas Georgoudis <[email protected]>
Date: Sun, 16 Aug 2026 21:14:59 +0100
Subject: [PATCH v2] libstdc++: Make forward_list::sort exception-safe
 [PR124051]

The bottom-up merge sort keeps its partially merged list in local
pointers while the container head still points into the original chain.
If the comparison throws after links have been changed, the head can
refer to a cycle and some nodes are no longer reachable.

Reconnect the merged prefix and both unconsumed runs, update the
container head, and then rethrow.  This leaves every node reachable
exactly once and preserves all iterators and references.  The success
path still performs the same comparisons and link changes.

libstdc++-v3/ChangeLog:

	PR libstdc++/124051
	* include/bits/forward_list.tcc (forward_list::sort): Restore the
	list before propagating an exception from the comparison.
	* testsuite/23_containers/forward_list/operations/
	sort_exception_124051.cc: New test.

Signed-off-by: Odysseas Georgoudis <[email protected]>
---
 libstdc++-v3/include/bits/forward_list.tcc    | 50 +++++++---
 .../operations/sort_exception_124051.cc       | 95 +++++++++++++++++++
 2 files changed, 133 insertions(+), 12 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/23_containers/forward_list/operations/sort_exception_124051.cc

diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index ffe2a2de84b..c5b417d8b87 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -468,20 +468,46 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			__p = __p->_M_next;
 			--__psize;
 		      }
-		    else if (!__comp(*static_cast<_Node&>(*__q)._M_valptr(),
-				     *static_cast<_Node&>(*__p)._M_valptr()))
-		      {
-			// First node of q is not lower; e must come from p.
-			__e = __p;
-			__p = __p->_M_next;
-			--__psize;
-		      }
 		    else
 		      {
-			// First node of q is lower; e must come from q.
-			__e = __q;
-			__q = __q->_M_next;
-			--__qsize;
+			bool __take_q;
+			__try
+			  {
+			    __take_q
+			      = __comp(*static_cast<_Node&>(*__q)._M_valptr(),
+				       *static_cast<_Node&>(*__p)._M_valptr());
+			  }
+			__catch(...)
+			  {
+			    // Reconnect the merged prefix and unmerged nodes
+			    // before propagating.
+			    _Base_ptr __last_p = __p;
+			    for (unsigned long __i = 1; __i < __psize; ++__i)
+			      __last_p = __last_p->_M_next;
+
+			    if (__tail)
+			      __tail->_M_next = __p;
+			    else
+			      __list = __p;
+			    __last_p->_M_next = __q;
+			    this->_M_impl._M_head._M_next = __list;
+			    __throw_exception_again;
+			  }
+
+			if (!__take_q)
+			  {
+			    // First node of q is not lower; e must come from p.
+			    __e = __p;
+			    __p = __p->_M_next;
+			    --__psize;
+			  }
+			else
+			  {
+			    // First node of q is lower; e must come from q.
+			    __e = __q;
+			    __q = __q->_M_next;
+			    --__qsize;
+			  }
 		      }
 
 		    // Add the next node to the merged list.
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/sort_exception_124051.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/sort_exception_124051.cc
new file mode 100644
index 00000000000..d3a7d763e09
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/sort_exception_124051.cc
@@ -0,0 +1,95 @@
+// { dg-do run { target c++11 } }
+// { dg-require-effective-target exceptions_enabled }
+
+#include <forward_list>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/124051 - forward_list::sort is not exception-safe
+
+struct exception { };
+
+struct throwing_less
+{
+  unsigned* countdown;
+
+  bool operator()(int lhs, int rhs) const
+  {
+    if (--*countdown == 0)
+      throw exception();
+    return lhs < rhs;
+  }
+};
+
+typedef std::forward_list<int> list_type;
+
+void verify_list(const list_type& list, const int* const* addresses,
+		 const list_type::iterator* iterators, unsigned size)
+{
+  for (unsigned i = 0; i < size; ++i)
+    {
+      VERIFY( *iterators[i] == static_cast<int>(i) );
+      VERIFY( &*iterators[i] == addresses[i] );
+    }
+
+  unsigned seen = 0;
+  unsigned count = 0;
+  for (const int& value : list)
+    {
+      VERIFY( count < size );
+      VERIFY( value >= 0 && value < static_cast<int>(size) );
+      const unsigned bit = 1u << value;
+      VERIFY( (seen & bit) == 0 );
+      VERIFY( &value == addresses[value] );
+      seen |= bit;
+      ++count;
+    }
+  VERIFY( count == size );
+  VERIFY( seen == (1u << size) - 1 );
+}
+
+void test01()
+{
+  const int values[] = { 6, 2, 8, 4, 11, 1, 12, 7, 3, 9, 5, 0, 10 };
+  const unsigned size = sizeof(values) / sizeof(values[0]);
+
+  for (unsigned throw_after = 1; ; ++throw_after)
+    {
+      list_type list(values, values + size);
+      const int* addresses[size];
+      list_type::iterator iterators[size];
+      for (list_type::iterator i = list.begin(); i != list.end(); ++i)
+	{
+	  addresses[*i] = &*i;
+	  iterators[*i] = i;
+	}
+
+      unsigned countdown = throw_after;
+      bool caught = false;
+      try
+	{
+	  list.sort(throwing_less{&countdown});
+	}
+      catch (const exception&)
+	{
+	  caught = true;
+	}
+
+      verify_list(list, addresses, iterators, size);
+      if (caught)
+	list.sort();
+
+      int expected = 0;
+      for (int value : list)
+	VERIFY( value == expected++ );
+
+      if (!caught)
+	break;
+      VERIFY( throw_after < 100 );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
-- 
2.43.5