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

From ee72bbd89a9da69aa90f8aa466bceead56f3d25f Mon Sep 17 00:00:00 2001
From: Odysseas Georgoudis <[email protected]>
Date: Sun, 16 Aug 2026 21:14:59 +0100
Subject: [PATCH] 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       | 111 ++++++++++++++++++
 2 files changed, 149 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..eb8ce8d9033
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/sort_exception_124051.cc
@@ -0,0 +1,111 @@
+// { dg-do run { target c++11 } }
+// { dg-require-effective-target exceptions_enabled }
+
+// Copyright (C) 2026 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#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();
+}
-- 
2.43.5