On Thu, 11 Sept 2025 at 22:41, Jonathan Wakely <jwak...@redhat.com> wrote:
>
> Whenever we use operator+ or similar operators on random access
> iterators we need to be careful to use the iterator's difference_type
> rather than some other integer type. It's not guaranteed that an
> expression with an arbitrary integer type, such as `it + 1u`, has the
> same effects as `it + iter_difference_t<It>(1)`.
>
> Some of our algorithms need changes to cast values to the correct type,
> or to use std::next or ranges::next instead of `it + n`. Several tests
> also need fixes where the arithmetic occurs directly in the test.
>
> The __gnu_test::random_access_iterator_wrapper class template is
> adjusted to have deleted operators that make programs ill-formed if the
> argument to relevant operators is not the difference_type. This will
> make it easier to avoid regressing in future.
>
> libstdc++-v3/ChangeLog:
>
> PR libstdc++/121890
> * include/bits/ranges_algo.h (ranges::rotate, ranges::shuffle)
> (__insertion_sort, __unguarded_partition_pivot, __introselect):
> Use ranges::next to advance iterators. Use local variables in
> rotate to avoid duplicate expressions.
> (ranges::push_heap, ranges::pop_heap, ranges::partial_sort)
> (ranges::partial_sort_copy): Use ranges::prev.
> (__final_insertion_sort): Use iter_difference_t<Iter>
> for operand of operator+ on iterator.
> * include/bits/ranges_base.h (ranges::advance): Use iterator's
> difference_type for all iterator arithmetic.
> * include/bits/stl_algo.h (__search_n_aux, __rotate)
> (__insertion_sort, __unguarded_partition_pivot, __introselect)
> (__final_insertion_sort, for_each_n, random_shuffle): Likewise.
> Use local variables in __rotate to avoid duplicate expressions.
> * include/bits/stl_algobase.h (__fill_n_a, __lc_rai::__newlast1):
> Likewise.
> * include/bits/stl_heap.h (push_heap): Likewise.
> (__is_heap_until): Add static_assert.
> (__is_heap): Convert distance to difference_type.
> * include/std/functional (boyer_moore_searcher::operator()): Use
> iterator's difference_type for iterator arithmetic.
> * testsuite/util/testsuite_iterators.h
> (random_access_iterator_wrapper): Add deleted overloads of
> operators that should be called with difference_type.
> * testsuite/24_iterators/range_operations/advance.cc: Use
> ranges::next.
> * testsuite/25_algorithms/heap/constrained.cc: Use ranges::next
> and ranges::prev.
> * testsuite/25_algorithms/nth_element/58800.cc: Use std::next.
> * testsuite/25_algorithms/nth_element/constrained.cc: Use
> ptrdiff_t for loop variable.
> * testsuite/25_algorithms/nth_element/random_test.cc: Use
> iterator's difference_type instead of int.
> * testsuite/25_algorithms/partial_sort/check_compare_by_value.cc:
> Use std::next.
> * testsuite/25_algorithms/partial_sort/constrained.cc: Use
> ptrdiff_t for loop variable.
> * testsuite/25_algorithms/partial_sort/random_test.cc: Use
> iterator's difference_type instead of int.
> * testsuite/25_algorithms/partial_sort_copy/constrained.cc:
> Use ptrdiff_t for loop variable.
> * testsuite/25_algorithms/partial_sort_copy/random_test.cc:
> Use iterator's difference_type instead of int.
> * testsuite/std/ranges/adaptors/drop.cc: Use ranges::next.
> * testsuite/25_algorithms/fill_n/diff_type.cc: New test.
> * testsuite/25_algorithms/for_each/diff_type.cc: New test.
> * testsuite/25_algorithms/lexicographical_compare/diff_type.cc:
> New test.
> * testsuite/25_algorithms/push_heap/diff_type.cc: New test.
> * testsuite/25_algorithms/nth_element/diff_type.cc: New test.
> * testsuite/25_algorithms/rotate/diff_type.cc: New test.
> * testsuite/25_algorithms/search_n/diff_type.cc: New test.
> * testsuite/25_algorithms/sort/diff_type.cc: New test.
> ---
>
> v3: Change in boyer_moore_searcher suggested by Tomasz. Reverted
> unnecessary ranges::next in ranges::rotate noticed by Patrick, and
> changed it to use local variables as done for std::rotate in v2.
I found one more change that's needed for debug mode:
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -180,7 +180,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
- __glibcxx_requires_heap(__first, __last - 1);
+ __glibcxx_requires_heap(__first, __last - _DistanceType(1));
__gnu_cxx::__ops::_Iter_less_val __comp;
_ValueType __value = _GLIBCXX_MOVE(*(__last - _DistanceType(1)));
I'm also removing all but these two of the new tests:
* testsuite/25_algorithms/fill_n/diff_type.cc: New test.
* testsuite/25_algorithms/lexicographical_compare/diff_type.cc
That's because for the other algos the existing tests already use
__gnu_test::random_access_iterator_wrapper and so already fail with
the new deleted operators in that wrapper. So we don't need new tests
to check things that we're already checking.
For fill_n and lexicographical_compare, the existing tests didn't
trigger the deleted operators.
