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

[Jonathan Wakely]

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.