[gcc r17-4828] libstdc++: Make forward_list::sort exception-safe [PR124051]

[Jonathan Wakely]

https://gcc.gnu.org/g:9082a3384ec5b4368b28e8dc85843947b1ccdc51

commit r17-4828-g9082a3384ec5b4368b28e8dc85843947b1ccdc51
Author: Odysseas Georgoudis <odygrd@hotmail.com>
Date:   Thu Oct 1 23:23:18 2026 +0100

    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/124051.cc: New test.
    
    Signed-off-by: Odysseas Georgoudis <odygrd@hotmail.com>

Diff:
---
 libstdc++-v3/include/bits/forward_list.tcc         | 50 +++++++++---
 .../forward_list/operations/124051.cc              | 95 ++++++++++++++++++++++
 2 files changed, 133 insertions(+), 12 deletions(-)

diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index ffe2a2de84be..c5b417d8b872 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/124051.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/124051.cc
new file mode 100644
index 000000000000..d3a7d763e095
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/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;
+}