[PATCH] libstdc++: Fix debug mode for pb_ds ordered-vector trees [PR127675]

[Jonathan Wakely]

On Fri, 2 Oct 2026 at 16:11, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> On Fri, 2 Oct 2026 at 15:39, Tomasz Kaminski <tkaminsk@redhat.com> wrote:
> >
> >
> >
> > On Thu, Oct 1, 2026 at 3:31 PM Jonathan Wakely <jwakely@redhat.com> 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.