libstdc++: Fix algorithms to use iterators' difference_type for arithmetic [PR121890]

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/lexicographical_compare/diff_type.cc:
	New test.

Reviewed-by: Patrick Palka <ppalka@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>

0 files changed, 0 insertions, 0 deletions