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>

20 files changed, 230 insertions, 91 deletions

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 6e1e06c..609b82e 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1683,9 +1683,11 @@ namespace ranges
 		    if constexpr (__is_pod(iter_value_t<_Iter>))
 		      if (__k == 1)
 			{
+			  auto __mid = ranges::next(__p, __n - 1);
+			  auto __end = ranges::next(__mid);
 			  auto __t = std::move(*__p);
-			  ranges::move(__p + 1, __p + __n, __p);
-			  *(__p + __n - 1) = std::move(__t);
+			  ranges::move(ranges::next(__p), __end, __p);
+			  *__mid = std::move(__t);
 			  return {std::move(__ret), std::move(__lasti)};
 			}
 		    auto __q = __p + __k;
@@ -1709,8 +1711,10 @@ namespace ranges
 		    if constexpr (__is_pod(iter_value_t<_Iter>))
 		      if (__k == 1)
 			{
-			  auto __t = std::move(*(__p + __n - 1));
-			  ranges::move_backward(__p, __p + __n - 1, __p + __n);
+			  auto __mid = ranges::next(__p, __n - 1);
+			  auto __end = ranges::next(__mid);
+			  auto __t = std::move(*__mid);
+			  ranges::move_backward(__p, __mid, __end);
 			  *__p = std::move(__t);
 			  return {std::move(__ret), std::move(__lasti)};
 			}
@@ -1970,7 +1974,7 @@ namespace ranges
 	if (__urngrange / __urange >= __urange)
 	  // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
 	  {
-	    _Iter __i = __first + 1;
+	    _Iter __i = ranges::next(__first);
 
 	    // Since we know the range isn't empty, an even number of elements
 	    // means an uneven number of elements /to swap/, in which case we
@@ -1979,7 +1983,7 @@ namespace ranges
 	    if ((__urange % 2) == 0)
 	      {
 		__distr_type __d{0, 1};
-		ranges::iter_swap(__i++, __first + __d(__g));
+		ranges::iter_swap(__i++, ranges::next(__first, __d(__g)));
 	      }
 
 	    // Now we know that __last - __i is even, so we do the rest in pairs,
@@ -1990,11 +1994,11 @@ namespace ranges
 	      {
 		const __uc_type __swap_range = __uc_type(__i - __first) + 1;
 
-		const pair<__uc_type, __uc_type> __pospos =
+		const pair<_DistanceType, _DistanceType> __pospos =
 		  __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
 
-		ranges::iter_swap(__i++, __first + __pospos.first);
-		ranges::iter_swap(__i++, __first + __pospos.second);
+		ranges::iter_swap(__i++, ranges::next(__first, __pospos.first));
+		ranges::iter_swap(__i++, ranges::next(__first, __pospos.second));
 	      }
 
 	    return __i;
@@ -2002,9 +2006,11 @@ namespace ranges
 
 	__distr_type __d;
 
-	_Iter __i = __first + 1;
+	_Iter __i = ranges::next(__first);
 	for (; __i != __last; ++__i)
-	  ranges::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
+	  ranges::iter_swap(__i,
+			    ranges::next(__first,
+					 __d(__g, __p_type(0, __i - __first))));
 
 	return __i;
       }
@@ -2060,7 +2066,7 @@ namespace ranges
 	  {
 	    auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
 	    __detail::__push_heap(__first, (__last - __first) - 1,
-				  0, ranges::iter_move(__last - 1),
+				  0, ranges::iter_move(ranges::prev(__last)),
 				  __comp_proj);
 	    return __last;
 	  }
@@ -2137,8 +2143,9 @@ namespace ranges
 	  {
 	    if (__last - __first > 1)
 	      {
+		auto __back = ranges::prev(__last);
 		auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
-		__detail::__pop_heap(__first, __last - 1, __last - 1, __comp_proj);
+		__detail::__pop_heap(__first, __back, __back, __comp_proj);
 	      }
 	    return __last;
 	  }
@@ -2356,12 +2363,12 @@ namespace ranges
 	if (__first == __last)
 	  return;
 
-	for (_Iter __i = __first + 1; __i != __last; ++__i)
+	for (_Iter __i = ranges::next(__first); __i != __last; ++__i)
 	  {
 	    if (__comp(*__i, *__first))
 	      {
 		iter_value_t<_Iter> __val = ranges::iter_move(__i);
-		ranges::move_backward(__first, __i, __i + 1);
+		ranges::move_backward(__first, __i, ranges::next(__i));
 		*__first = std::move(__val);
 	      }
 	    else
@@ -2383,10 +2390,11 @@ namespace ranges
       constexpr void
       __final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
       {
-	if (__last - __first > __sort_threshold)
+	constexpr iter_difference_t<_Iter> __threshold = __sort_threshold;
+	if (__last - __first > __threshold)
 	  {
-	    __detail::__insertion_sort(__first, __first + __sort_threshold, __comp);
-	    __detail::__unguarded_insertion_sort(__first + __sort_threshold, __last,
+	    __detail::__insertion_sort(__first, __first + __threshold, __comp);
+	    __detail::__unguarded_insertion_sort(__first + __threshold, __last,
 						 __comp);
 	  }
 	else
@@ -2416,8 +2424,10 @@ namespace ranges
       __unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp __comp)
       {
 	_Iter __mid = __first + (__last - __first) / 2;
-	__detail::__move_median_to_first(__first, __first + 1, __mid, __last - 1, __comp);
-	return __detail::__unguarded_partition(__first + 1, __last, __first, __comp);
+	__detail::__move_median_to_first(__first, ranges::next(__first), __mid,
+					 ranges::prev(__last), __comp);
+	return __detail::__unguarded_partition(ranges::next(__first), __last,
+					       __first, __comp);
       }
 
     template<typename _Iter, typename _Comp>
@@ -2745,7 +2755,7 @@ namespace ranges
 			    std::__invoke(__proj, *__first)))
 	    {
 	      ranges::pop_heap(__first, __middle, __comp, __proj);
-	      ranges::iter_swap(__middle-1, __i);
+	      ranges::iter_swap(std::prev(__middle), __i);
 	      ranges::push_heap(__first, __middle, __comp, __proj);
 	    }
 	ranges::sort_heap(__first, __middle, __comp, __proj);
@@ -2812,7 +2822,7 @@ namespace ranges
 	    {
 	      ranges::pop_heap(__result_first, __result_real_last,
 			       __comp, __proj2);
-	      *(__result_real_last-1) = *__first;
+	      *ranges::prev(__result_real_last) = *__first;
 	      ranges::push_heap(__result_first, __result_real_last,
 				__comp, __proj2);
 	    }
@@ -2924,7 +2934,8 @@ namespace ranges
 	  {
 	    if (__depth_limit == 0)
 	      {
-		__detail::__heap_select(__first, __nth + 1, __last, __comp);
+		__detail::__heap_select(__first, ranges::next(__nth), __last,
+					__comp);
 		// Place the nth largest element in its final position.
 		ranges::iter_swap(__first, __nth);
 		return;
diff --git a/libstdc++-v3/include/bits/ranges_base.h b/libstdc++-v3/include/bits/ranges_base.h
index 2782908..1c4bf43 100644
--- a/libstdc++-v3/include/bits/ranges_base.h
+++ b/libstdc++-v3/include/bits/ranges_base.h
@@ -900,7 +900,7 @@ namespace ranges
 		if constexpr (assignable_from<_It&, _Sent>)
 		  __it = std::move(__bound);
 		else if constexpr (random_access_iterator<_It>)
-		  __it += 0;
+		  __it += iter_difference_t<_It>(0);
 		return __n;
 	      }
 	    else if (__diff > 0 ? __n >= __diff : __n <= __diff)
@@ -920,7 +920,7 @@ namespace ranges
 	      {
 		// inline any possible side effects of advance(it, n)
 		if constexpr (random_access_iterator<_It>)
-		  __it += 0;
+		  __it += iter_difference_t<_It>(0);
 		return 0;
 	      }
 	  }
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 81a2457..78c63e7 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -204,7 +204,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  while (__unary_pred(--__backTrack))
 	    {
 	      if (--__remainder == 0)
-		return (__first - __count); // Success
+		return __first - _DistanceType(__count); // Success
 	    }
 	  __remainder = __count + 1 - (__first - __backTrack);
 	}
@@ -1258,9 +1258,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
 	    {
 	      if (__is_pod(_ValueType) && __k == 1)
 		{
+		  _RandomAccessIterator __mid = __p + _Distance(__n - 1);
+		  _RandomAccessIterator __end = __mid;
+		  ++__end;
 		  _ValueType __t = _GLIBCXX_MOVE(*__p);
-		  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
-		  *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
+		  _GLIBCXX_MOVE3(__p + _Distance(1), __end, __p);
+		  *__mid = _GLIBCXX_MOVE(__t);
 		  return __ret;
 		}
 	      _RandomAccessIterator __q = __p + __k;
@@ -1281,8 +1284,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
 	      __k = __n - __k;
 	      if (__is_pod(_ValueType) && __k == 1)
 		{
-		  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
-		  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
+		  _RandomAccessIterator __mid = __p + _Distance(__n - 1);
+		  _RandomAccessIterator __end = __mid;
+		  ++__end;
+		  _ValueType __t = _GLIBCXX_MOVE(*__mid);
+		  _GLIBCXX_MOVE_BACKWARD3(__p, __mid, __end);
 		  *__p = _GLIBCXX_MOVE(__t);
 		  return __ret;
 		}
@@ -1770,15 +1776,18 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
     __insertion_sort(_RandomAccessIterator __first,
 		     _RandomAccessIterator __last, _Compare __comp)
     {
-      if (__first == __last) return;
+      if (__first == __last)
+	return;
 
-      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+      typedef iterator_traits<_RandomAccessIterator> _IterTraits;
+      typedef typename _IterTraits::difference_type _Dist;
+
+      for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last; ++__i)
 	{
 	  if (__comp(__i, __first))
 	    {
-	      typename iterator_traits<_RandomAccessIterator>::value_type
-		__val = _GLIBCXX_MOVE(*__i);
-	      _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
+	      typename _IterTraits::value_type __val = _GLIBCXX_MOVE(*__i);
+	      _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + _Dist(1));
 	      *__first = _GLIBCXX_MOVE(__val);
 	    }
 	  else
@@ -1812,10 +1821,13 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
     __final_insertion_sort(_RandomAccessIterator __first,
 			   _RandomAccessIterator __last, _Compare __comp)
     {
-      if (__last - __first > int(_S_threshold))
+      typename iterator_traits<_RandomAccessIterator>::difference_type
+	__threshold = _S_threshold;
+
+      if (__last - __first > __threshold)
 	{
-	  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
-	  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
+	  std::__insertion_sort(__first, __first + __threshold, __comp);
+	  std::__unguarded_insertion_sort(__first + __threshold, __last,
 					  __comp);
 	}
       else
@@ -1851,10 +1863,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
     __unguarded_partition_pivot(_RandomAccessIterator __first,
 				_RandomAccessIterator __last, _Compare __comp)
     {
-      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
-      std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
+      typedef iterator_traits<_RandomAccessIterator> _IterTraits;
+      typedef typename _IterTraits::difference_type _Dist;
+
+      _RandomAccessIterator __mid = __first + _Dist((__last - __first) / 2);
+      _RandomAccessIterator __second = __first + _Dist(1);
+      std::__move_median_to_first(__first, __second, __mid, __last - _Dist(1),
 				  __comp);
-      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
+      return std::__unguarded_partition(__second, __last, __first, __comp);
     }
 
   template<typename _RandomAccessIterator, typename _Compare>
@@ -1916,11 +1932,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 		  _RandomAccessIterator __last, _Size __depth_limit,
 		  _Compare __comp)
     {
+      _RandomAccessIterator __after_nth = __nth;
+      ++__after_nth;
+
       while (__last - __first > 3)
 	{
 	  if (__depth_limit == 0)
 	    {
-	      std::__heap_select(__first, __nth + 1, __last, __comp);
+	      std::__heap_select(__first, __after_nth, __last, __comp);
 	      // Place the nth largest element in its final position.
 	      std::iter_swap(__first, __nth);
 	      return;
@@ -3822,7 +3841,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	{
 	  if (__n2 <= 0)
 	    return __first;
-	  auto __last = __first + __n2;
+	  typename iterator_traits<_InputIterator>::difference_type __d = __n2;
+	  auto __last = __first + __d;
 	  std::for_each(__first, __last, std::move(__f));
 	  return __last;
 	}
@@ -4544,6 +4564,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       if (__first == __last)
 	return;
 
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+	_Dist;
+
 #if RAND_MAX < __INT_MAX__
       if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
 	{
@@ -4551,14 +4574,15 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	  // instead of using rand() for all the random numbers needed.
 	  unsigned __xss
 	    = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
-	  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+	  for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last;
+	       ++__i)
 	    {
 	      __xss += !__xss;
 	      __xss ^= __xss << 13;
 	      __xss ^= __xss >> 17;
 	      __xss ^= __xss << 5;
-	      _RandomAccessIterator __j = __first
-					    + (__xss % ((__i - __first) + 1));
+	      _RandomAccessIterator __j
+		= __first + _Dist(__xss % ((__i - __first) + 1));
 	      if (__i != __j)
 		std::iter_swap(__i, __j);
 	    }
@@ -4566,11 +4590,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	}
 #endif
 
-      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+      for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last; ++__i)
 	{
 	  // XXX rand() % N is not uniformly distributed
-	  _RandomAccessIterator __j = __first
-					+ (std::rand() % ((__i - __first) + 1));
+	  _RandomAccessIterator __j
+	    = __first + _Dist(std::rand() % ((__i - __first) + 1));
 	  if (__i != __j)
 	    std::iter_swap(__i, __j);
 	}
@@ -4611,9 +4635,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 
       if (__first == __last)
 	return;
-      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+	_Dist;
+
+      for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last; ++__i)
 	{
-	  _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
+	  _RandomAccessIterator __j
+	    = __first + _Dist(__rand((__i - __first) + 1));
 	  if (__i != __j)
 	    std::iter_swap(__i, __j);
 	}
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index b104ec2..820091a 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1150,10 +1150,12 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
       if (__n <= 0)
 	return __first;
 
-      __glibcxx_requires_can_increment(__first, __n);
+      typename iterator_traits<_OutputIterator>::difference_type __d = __n;
+      __glibcxx_requires_can_increment(__first, __d);
 
-      std::__fill_a(__first, __first + __n, __value);
-      return __first + __n;
+      _OutputIterator __last = __first + __d;
+      std::__fill_a(__first, __last, __value);
+      return __last;
     }
 
   /**
@@ -1310,11 +1312,11 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 	__newlast1(_RAI1 __first1, _RAI1 __last1,
 		   _RAI2 __first2, _RAI2 __last2)
 	{
-	  const typename iterator_traits<_RAI1>::difference_type
-	    __diff1 = __last1 - __first1;
-	  const typename iterator_traits<_RAI2>::difference_type
-	    __diff2 = __last2 - __first2;
-	  return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
+	  typedef typename iterator_traits<_RAI1>::difference_type _Diff1;
+	  typedef typename iterator_traits<_RAI2>::difference_type _Diff2;
+	  const _Diff1 __diff1 = __last1 - __first1;
+	  const _Diff2 __diff2 = __last2 - __first2;
+	  return __diff2 < __diff1 ? __first1 + _Diff1(__diff2) : __last1;
 	}
 
       template<typename _RAI>
diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index 028ac83..f2b1e87 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -76,6 +76,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __is_heap_until(_RandomAccessIterator __first, _Distance __n,
 		    _Compare& __comp)
     {
+#if __cplusplus >= 201103L
+      using _IterTraits = iterator_traits<_RandomAccessIterator>;
+      static_assert(is_same<typename _IterTraits::difference_type,
+			    _Distance>::value,
+		    "Argument 'n' must be the iterator's difference type");
+#endif
       _Distance __parent = 0;
       for (_Distance __child = 1; __child < __n; ++__child)
 	{
@@ -94,8 +100,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline bool
     __is_heap(_RandomAccessIterator __first, _Distance __n)
     {
+      typename iterator_traits<_RandomAccessIterator>::difference_type __d(__n);
       __gnu_cxx::__ops::_Iter_less_iter __comp;
-      return std::__is_heap_until(__first, __n, __comp) == __n;
+      return std::__is_heap_until(__first, __d, __comp) == __n;
     }
 
   template<typename _RandomAccessIterator, typename _Compare,
@@ -104,9 +111,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline bool
     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
     {
+      typename iterator_traits<_RandomAccessIterator>::difference_type __d(__n);
       typedef __decltype(__comp) _Cmp;
       __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
-      return std::__is_heap_until(__first, __n, __cmp) == __n;
+      return std::__is_heap_until(__first, __d, __cmp) == __n;
     }
 
   template<typename _RandomAccessIterator>
@@ -172,10 +180,10 @@ _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 - 1));
+      _ValueType __value = _GLIBCXX_MOVE(*(__last - _DistanceType(1)));
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 		       _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
     }
@@ -208,11 +216,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
-      __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
+      __glibcxx_requires_heap_pred(__first, __last - _DistanceType(1), __comp);
 
       __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
 	__cmp(_GLIBCXX_MOVE(__comp));
-      _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
+      _ValueType __value = _GLIBCXX_MOVE(*(__last - _DistanceType(1)));
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 		       _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
     }
diff --git a/libstdc++-v3/include/std/functional b/libstdc++-v3/include/std/functional
index bf40995..f86030d 100644
--- a/libstdc++-v3/include/std/functional
+++ b/libstdc++-v3/include/std/functional
@@ -1345,7 +1345,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  if (__j < 0)
 	    {
-	      const auto __match = __first + __i + 1;
+	      const auto __match = __first + __diff_type(__i + 1);
 	      return std::make_pair(__match, __match + __patlen);
 	    }
 	  __i += std::max(_M_bad_char_shift(__first[__i]),
diff --git a/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc b/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc
index 2f48181..8229b1e 100644
--- a/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc
+++ b/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc
@@ -42,7 +42,7 @@ test01()
   std::ranges::advance(iter, -2);
   VERIFY( iter == r.begin() );
 
-  std::ranges::advance(iter, r.begin() + 1);
+  std::ranges::advance(iter, std::ranges::next(r.begin()));
   VERIFY( iter != r.begin() );
   VERIFY( iter != r.end() );
   std::ranges::advance(iter, r.begin());
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill_n/diff_type.cc b/libstdc++-v3/testsuite/25_algorithms/fill_n/diff_type.cc
new file mode 100644
index 0000000..7265d39
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill_n/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+  // algorithms do not use iterator's difference_type for arithmetic
+  int a[1];
+  __gnu_test::random_access_container<int> c(a);
+  std::fill_n(c.begin(), 1U, 0);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
index 5486c85..2f818e2 100644
--- a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
@@ -53,17 +53,17 @@ test01()
 
       iter = ranges::pop_heap(rx, pred, proj);
       VERIFY( iter == rx.end() );
-      VERIFY( *(iter-1) == 50 );
-      VERIFY( ranges::is_heap_until(rx, pred, proj) == iter-1 );
+      VERIFY( *ranges::prev(iter) == 50 );
+      VERIFY( ranges::is_heap_until(rx, pred, proj) == ranges::prev(iter) );
 
-      iter = ranges::pop_heap(rx.begin(), iter-1, pred, proj);
-      VERIFY( iter+1 == rx.end() );
-      VERIFY( *(iter-1) == 49 );
-      VERIFY( ranges::is_heap_until(rx, pred, proj) == iter-1 );
+      iter = ranges::pop_heap(rx.begin(), ranges::prev(iter), pred, proj);
+      VERIFY( ranges::next(iter) == rx.end() );
+      VERIFY( *ranges::prev(iter) == 49 );
+      VERIFY( ranges::is_heap_until(rx, pred, proj) == ranges::prev(iter) );
 
-      *(iter-1) = i;
+      *ranges::prev(iter) = i;
       iter = ranges::push_heap(rx.begin(), iter, pred, proj);
-      VERIFY( iter+1 == rx.end() );
+      VERIFY( ranges::next(iter) == rx.end() );
       VERIFY( ranges::is_heap_until(rx, pred, proj) == iter );
 
       *iter = 2*i;
@@ -71,9 +71,9 @@ test01()
       VERIFY( iter == rx.end() );
       VERIFY( ranges::is_heap_until(rx, pred, proj) == iter );
 
-      *(rx.begin()+1) *= -1;
+      *ranges::next(rx.begin()) *= -1;
       VERIFY( !ranges::is_heap(rx, pred, proj) );
-      *(rx.begin()+1) *= -1;
+      *ranges::next(rx.begin()) *= -1;
       VERIFY( ranges::is_heap(rx, pred, proj) );
 
       iter = ranges::sort_heap(rx, pred, proj);
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/diff_type.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/diff_type.cc
new file mode 100644
index 0000000..b790197
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/diff_type.cc
@@ -0,0 +1,57 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+struct Iter
+{
+  using value_type = int;
+  using difference_type = short;
+  using iterator_category = std::random_access_iterator_tag;
+  using pointer = const value_type*;
+  using reference = const value_type&;
+
+  Iter() : p(nullptr) { }
+  explicit Iter(pointer p) : p(p) { }
+  reference operator*() const { return *p; }
+  pointer operator->() const { return p; }
+  reference operator[](difference_type n) const { return p[n]; }
+  Iter& operator++() { ++p; return *this; }
+  Iter& operator--() { --p; return *this; }
+  Iter operator++(int) { return Iter(p++); }
+  Iter operator--(int) { return Iter(p--); }
+  Iter& operator+=(difference_type n) { p += n; return *this; }
+  Iter& operator-=(difference_type n) { p -= n; return *this; }
+
+  friend Iter operator+(Iter i, difference_type n) { return i += n; }
+  friend Iter operator+(difference_type n, Iter i) { return i += n; }
+  friend Iter operator-(Iter i, difference_type n) { return i -= n; }
+  friend difference_type operator-(Iter i, Iter j) { return i.p - j.p; }
+
+  template<typename D> void operator[](D) const = delete;
+  template<typename D> void operator+=(D) = delete;
+  template<typename D> void operator-=(D) = delete;
+  template<typename D> friend void operator+(Iter, difference_type) = delete;
+  template<typename D> friend void operator+(difference_type, Iter) = delete;
+  template<typename D> friend void operator-(Iter, difference_type) = delete;
+
+  friend bool operator==(Iter i, Iter j) { return i.p == j.p; }
+  friend bool operator!=(Iter i, Iter j) { return i.p != j.p; }
+  friend bool operator<(Iter i, Iter j) { return i.p < j.p; }
+  friend bool operator<=(Iter i, Iter j) { return i.p <= j.p; }
+  friend bool operator>(Iter i, Iter j) { return i.p > j.p; }
+  friend bool operator>=(Iter i, Iter j) { return i.p >= j.p; }
+
+private:
+  pointer p;
+};
+
+void
+test_pr121890()
+{
+  // algorithms do not use iterator's difference_type for arithmetic
+  int a[1] = { };
+  __gnu_test::random_access_container<int> c(a);
+  (void) std::lexicographical_compare(c.begin(), c.end(), Iter(a), Iter(a+1));
+  (void) std::lexicographical_compare(Iter(a), Iter(a+1), c.begin(), c.end());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
index 3989ee0..ff86c63 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
@@ -43,7 +43,7 @@ void test01()
 
   Container con(v.data(), v.data() + 7);
 
-  std::nth_element(con.begin(), con.begin() + 3, con.end());
+  std::nth_element(con.begin(), std::next(con.begin(), 3), con.end());
 }
 
 int main()
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
index 8cb1625..8d3a057 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
@@ -38,7 +38,7 @@ test01()
 
   auto pred = std::greater{};
   auto proj = [] (int a) { return -a; };
-  for (int i = 0; i < 50; i++)
+  for (std::ptrdiff_t i = 0; i < 50; i++)
     {
       test_range<int, random_access_iterator_wrapper> rx(x);
       std::ranlux48_base g(i);
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc
index 2e9d4b3..9eaef61 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc
@@ -37,9 +37,9 @@ struct testNthElement
   template<typename Container, typename RandomGen>
   void operator()(Container con, RandomGen& rg)
   {
-    const int size = con.end() - con.begin();
+    const auto size = con.end() - con.begin();
     auto dist = std::uniform_int_distribution<>(0, size);
-    const int element = dist(rg);
+    const decltype(size) element = dist(rg);
 
     std::nth_element(con.begin(), con.begin() + element, con.end());
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
index 05f4f1c..e1ba840 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
@@ -43,7 +43,7 @@ test01()
 	     17, 8, 18, 9, 19 };
   const int N = sizeof(s1) / sizeof(V);
   Container con(s1, s1 + N);
-  std::partial_sort(con.begin(), con.begin() + 10, con.end());
+  std::partial_sort(con.begin(), std::next(con.begin(), 10), con.end());
   VERIFY( s1[0].ok );
   for(int i = 1; i < 10; ++i)
     VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
@@ -59,7 +59,7 @@ test02()
 	     17, 8, 18, 9, 19 };
   const int N = sizeof(s1) / sizeof(V);
   Container con(s1, s1 + N);
-  std::partial_sort(con.begin(), con.begin() + 10, con.end(),
+  std::partial_sort(con.begin(), std::next(con.begin(), 10), con.end(),
 		    __gnu_test::order);
   VERIFY( s1[0].ok );
   for(int i = 1; i < 10; ++i)
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc
index 032ffe7..554a8d7 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc
@@ -47,7 +47,8 @@ test01()
       ranges::shuffle(c, g1);
       ranges::shuffle(ranges::begin(r), ranges::end(r), g2);
 
-      for (unsigned middle = 0; middle < std::min(size, 10U); ++middle)
+      for (std::ptrdiff_t middle = 0, end = std::min(size, 10U);
+	   middle < end; ++middle)
 	{
 	  auto res1 = ranges::partial_sort(c.begin(), c.begin()+middle, c.end(),
 					   {}, std::negate<>{});
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc
index 89eb992..4e69000 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc
@@ -37,9 +37,9 @@ struct testPartialSort
   template<typename Container, typename RandomGen>
   void operator()(Container con, RandomGen& rg)
   {
-    const int size = con.end() - con.begin();
+    const auto size = con.end() - con.begin();
     auto dist = std::uniform_int_distribution<>(0, size);
-    const int element = dist(rg);
+    const decltype(size) element = dist(rg);
 
     std::partial_sort(con.begin(), con.begin() + element, con.end());
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
index a0bd48b..38b2dda 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
@@ -35,7 +35,7 @@ namespace ranges = std::ranges;
 void
 test01()
 {
-  for (unsigned size = 0; size < 50; ++size)
+  for (std::ptrdiff_t size = 0; size < 50; ++size)
     {
       std::vector<int> vref(size);
       std::iota(vref.begin(), vref.end(), 0);
@@ -45,7 +45,7 @@ test01()
       ranges::shuffle(v1, g1);
       ranges::shuffle(v2, g2);
 
-      for (unsigned middle = 0; middle < 10; ++middle)
+      for (std::ptrdiff_t middle = 0; middle < 10; ++middle)
 	{
 	  test_container<int, forward_iterator_wrapper> c
 	    = {v1.data(), v1.data() + size};
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc
index 2c0b8bc..be033a2 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc
@@ -38,9 +38,9 @@ struct testPartialSortCopy
   template<typename Container, typename RandomGen>
   void operator()(Container con, RandomGen& rg)
   {
-    const int size = con.end() - con.begin();
+    const auto size = con.end() - con.begin();
     auto dist = std::uniform_int_distribution<>(0, size);
-    const int element = dist(rg);
+    const decltype(size) element = dist(rg);
 
     std::vector<int> outvec(element + 1); // add +1 to avoid empty issues
 
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
index 4583fb0..57db806 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
@@ -243,7 +243,7 @@ test08()
 
   long b[10]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
   test_range<long, ra_test_wrapper> rb(b);
-  ranges::subrange sized = {rb.begin(), rb.begin()+6};
+  ranges::subrange sized = {rb.begin(), ranges::next(rb.begin(), 6)};
   using Sized = decltype(sized);
   static_assert( ranges::random_access_range<Sized> );
   static_assert( ranges::sized_range<Sized> );
diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h
index acd412a..5bf2e70 100644
--- a/libstdc++-v3/testsuite/util/testsuite_iterators.h
+++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h
@@ -607,6 +607,16 @@ namespace __gnu_test
     T& operator[](std::ptrdiff_t n) const
     { return *(*this + n); }
 
+#if __cplusplus >= 201103L
+    // Ensure that the iterator's difference_type is always used.
+    template<typename D> void operator+=(D) = delete;
+    template<typename D> void operator-=(D) = delete;
+    template<typename D> void operator[](D) const = delete;
+    template<typename D>
+      typename std::enable_if<std::is_integral<D>::value>::type
+      operator-(D) const = delete;
+#endif
+
     _GLIBCXX14_CONSTEXPR
     bool operator<(const random_access_iterator_wrapper<T>& in) const
     {
@@ -645,6 +655,14 @@ namespace __gnu_test
     operator+(std::ptrdiff_t n, random_access_iterator_wrapper<T> it)
     { return it += n; }
 
+#if __cplusplus >= 201103L
+    // Ensure that the iterator's difference_type is always used.
+    template<typename T, typename D>
+      void operator+(random_access_iterator_wrapper<T>, D) = delete;
+    template<typename T, typename D>
+      void operator+(D, random_access_iterator_wrapper<T>) = delete;
+#endif
+
 
   /**
    * @brief A container-type class for holding iterator wrappers