On Fri, Oct 2, 2026 at 5:17 PM Jonathan Wakely <[email protected]> wrote:
> 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. > Thanks.
