On Fri, 2 Oct 2026 at 16:11, Jonathan Wakely <[email protected]> wrote: > > On Fri, 2 Oct 2026 at 15:39, Tomasz Kaminski <[email protected]> wrote: > > > > > > > > On Thu, Oct 1, 2026 at 3:31 PM Jonathan Wakely <[email protected]> wrote: > >> > >> As noted in the bugzilla PR, there are debug mode assertions in the > >> ov_tree_map and ov_tree_set code which fail occasionally (but not > >> consistently because the tests use the current time as a random seed). > >> > >> This change first allows the time-based random seed to be overridden > >> using the same GLIBCXX_SEED_TEST_RNG environment variable already > >> checked elsewhere in the testsuite. This allows failures to be triggered > >> reliably. > >> > >> The bug in erase_if is an exception-safety bug where most state is > >> rolled back cleanly if an exception occurs, but some modifications to > >> the debug_base::m_keys list are not rolled back. This leaves the > >> container in an inconsistent state where the values in m_keys do not > >> match the contents of the container. This triggers debug assertions on > >> the next operation when the container checks its invariants. > >> > >> The bug in erase(It) is much simpler and easier to trigger: the function > >> calls alloc.allocate(m_size - 1) unconditionally, even if m_size == 1. > >> It is unspecified what allocators return for zero-sized allocations, so > >> this can return a non-null pointer. That is then inconsistent with the > >> debug assertions which require m_a_values == nullptr to be true when > >> m_size == 0. The solution here is to simply avoid allocating anything > >> when m_size == 1. > >> > >> Finally, the split and join members of the debug_base are refactored to > >> use std::list::splice instead of inserting and erasing elements from the > >> two lists. This means they perform no allocations and no copies, so > >> cannot throw exceptions (unless the comparison function passed to split > >> throws). Although this doesn't fix any known bugs, it makes the callers > >> of those functions more robust and makes it easier to ensure those > >> callers are exception-safe. > >> > >> libstdc++-v3/ChangeLog: > >> > >> PR libstdc++/127675 > >> * include/ext/pb_ds/detail/debug_map_base.hpp (split, join): Use > >> std::list::splice to move elements without reallocating. > >> * > >> include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp > >> (copy_from_ordered_range(It, It, It, It)): Do not allocate new > >> storage for an empty container. > >> * include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp > >> (erase_if): Do not modify this->debug_base::m_keys until all > >> allocations and other potentially-throwing operations have > >> completed successfully. > >> (erase_imp): Do not allocate new storage for an empty container. > >> * testsuite/ext/pb_ds/regression/127675.cc: New test. > >> * testsuite/util/testsuite_rng.h (get_time_determined_seed): Use > >> getenv("GLIBCXX_SEED_TEST_RNG") to allow the seed to be fixed. > >> --- > >> > >> Tested x86_64-linux. > > > > LGTM, with one suggestion for commit description below: > >> > >> > >> .../ext/pb_ds/detail/debug_map_base.hpp | 19 +++---- > >> .../constructors_destructor_fn_imps.hpp | 2 + > >> .../detail/ov_tree_map_/erase_fn_imps.hpp | 13 +++-- > >> .../testsuite/ext/pb_ds/regression/127675.cc | 53 +++++++++++++++++++ > >> libstdc++-v3/testsuite/util/testsuite_rng.h | 7 ++- > >> 5 files changed, 77 insertions(+), 17 deletions(-) > >> create mode 100644 libstdc++-v3/testsuite/ext/pb_ds/regression/127675.cc > >> > >> diff --git a/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp > >> b/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp > >> index 67bdc3c942f0..8083f1617316 100644 > >> --- a/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp > >> +++ b/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp > >> @@ -312,10 +312,7 @@ namespace __gnu_pbds > >> iterator it = m_keys.begin(); > >> while (it != m_keys.end()) > >> if (cmp_fn(r_key, *it)) > >> - { > >> - other.insert_new(*it); > >> - it = m_keys.erase(it); > >> - } > >> + other.m_keys.splice(other.m_keys.end(), m_keys, it++); > >> else > >> ++it; > >> } > >> @@ -325,16 +322,12 @@ namespace __gnu_pbds > >> PB_DS_CLASS_C_DEC:: > >> join(PB_DS_CLASS_C_DEC& other, bool with_cleanup) > >> { > >> - iterator it = other.m_keys.begin(); > >> - while (it != other.m_keys.end()) > >> - { > >> + if (with_cleanup) > >> + m_keys.splice(m_keys.end(), other.m_keys); > >> + else > >> + for (iterator it = other.m_keys.begin(), e = other.m_keys.end(); > >> + it != e; ++it) > >> insert_new(*it); > >> - if (with_cleanup) > >> - it = other.m_keys.erase(it); > >> - else > >> - ++it; > >> - } > >> - _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty()); > >> } > >> > >> #undef PB_DS_CLASS_T_DEC > >> diff --git > >> a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp > >> > >> b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp > >> index 713d25640487..dffc2f275ee4 100644 > >> --- > >> a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp > >> +++ > >> b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp > >> @@ -162,6 +162,8 @@ copy_from_ordered_range(It first_it, It last_it, It > >> other_first_it, > >> clear(); > >> const size_type len = std::distance(first_it, last_it) > >> + std::distance(other_first_it, other_last_it); > >> + if (len == 0) > >> + return; > > > > This function is only called in join from split_join_from_impls.h, after > > checking that both rangs > > are not empty and it's private, so that change does not seem strictly > > necessary. > > I am not opposed adding this check, but mention that in commit description. > > Ah yes, I forgot to say something about that. You're right, it's an > unreachable condition today. > > But if the caller changed or it got a new caller, then this would have > the same bug as fixed elsewhere in this patch, because the next line > is: > > >> value_vector a_values = s_value_alloc.allocate(len); > > So this would allocate zero elements and then we would have m_a_values > != nullptr && m_size == 0, which would trigger the debug assertion. It > seems more robust to make this function able to cope with an empty > range, which is what the two-parameter overload directly above it > already does: > > copy_from_ordered_range(It first_it, It last_it) > { > const size_type len = std::distance(first_it, last_it); > if (len == 0) > return; > > I'll put that explanation in the commit log, thanks.
I added this paragraph to the commit log: There's a similar latent bug in the 4-param overload of copy_from_ordered_range, which would call allocate(0) if called with two empty ranges. Although its only caller today already checks for empty ranges, it would be more robust to make copy_from_ordered_range safe for this case. That avoids a potential future bug where the debug assertions fail again because copy_from_ordered_range allocates a non-null pointer for m_size == 0. The change made in this commit is to return early if len == 0, which is exactly what the 2-param overload of copy_from_ordered_range already does.
