https://gcc.gnu.org/g:9082a3384ec5b4368b28e8dc85843947b1ccdc51
commit r17-4828-g9082a3384ec5b4368b28e8dc85843947b1ccdc51 Author: Odysseas Georgoudis <[email protected]> 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 <[email protected]> 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; +}
