[gcc r16-3842] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]

[Patrick Palka]

https://gcc.gnu.org/g:349affa42c9fa47a12eb7f5f97f5650a77bbf014

commit r16-3842-g349affa42c9fa47a12eb7f5f97f5650a77bbf014
Author: Patrick Palka <ppalka@redhat.com>
Date:   Sat Sep 13 10:44:12 2025 -0400

    libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
    
    ranges::shuffle has a two-at-a-time PRNG optimization (copied from
    std::shuffle) that considers the PRNG width vs the size of the range.
    But in C++20 a random access sentinel isn't always sized so we can't
    unconditionally do __last - __first to obtain the size in constant
    time.
    
    We could instead use ranges::distance, but that'd take linear time for a
    non-sized sentinel which makes the optimization less clear of a win.  So
    this patch instead makes us only consider this optimization for sized
    ranges.
    
            PR libstdc++/121917
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/ranges_algo.h (__shuffle_fn::operator()): Only
            consider the two-at-a-time PRNG optimization if the range is
            sized.
            * testsuite/25_algorithms/shuffle/constrained.cc (test03): New
            test.
    
    Reviewed-by: Jonathan Wakely <jwakely@redhat.com>

Diff:
---
 libstdc++-v3/include/bits/ranges_algo.h            | 66 +++++++++++++---------
 .../testsuite/25_algorithms/shuffle/constrained.cc | 18 ++++++
 2 files changed, 56 insertions(+), 28 deletions(-)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 9b348d82ce55..6ec233f19df8 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1968,40 +1968,43 @@ namespace ranges
 	using __uc_type
 	  = common_type_t<typename remove_reference_t<_Gen>::result_type, __ud_type>;
 
-	const __uc_type __urngrange = __g.max() - __g.min();
-	const __uc_type __urange = __uc_type(__last - __first);
-
-	if (__urngrange / __urange >= __urange)
-	  // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
+	if constexpr (sized_sentinel_for<_Sent, _Iter>)
 	  {
-	    _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
-	    // do the first one up front:
+	    const __uc_type __urngrange = __g.max() - __g.min();
+	    const __uc_type __urange = __uc_type(__last - __first);
 
-	    if ((__urange % 2) == 0)
+	    if (__urngrange / __urange >= __urange)
+	      // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
 	      {
-		__distr_type __d{0, 1};
-		ranges::iter_swap(__i++, ranges::next(__first, __d(__g)));
-	      }
+		_Iter __i = ranges::next(__first);
 
-	    // Now we know that __last - __i is even, so we do the rest in pairs,
-	    // using a single distribution invocation to produce swap positions
-	    // for two successive elements at a time:
+		// 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
+		// do the first one up front:
 
-	    while (__i != __last)
-	      {
-		const __uc_type __swap_range = __uc_type(__i - __first) + 1;
+		if ((__urange % 2) == 0)
+		  {
+		    __distr_type __d{0, 1};
+		    ranges::iter_swap(__i++, ranges::next(__first, __d(__g)));
+		  }
 
-		const pair<_DistanceType, _DistanceType> __pospos =
-		  __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
+		// Now we know that __last - __i is even, so we do the rest in pairs,
+		// using a single distribution invocation to produce swap positions
+		// for two successive elements at a time:
 
-		ranges::iter_swap(__i++, ranges::next(__first, __pospos.first));
-		ranges::iter_swap(__i++, ranges::next(__first, __pospos.second));
-	      }
+		while (__i != __last)
+		  {
+		    const __uc_type __swap_range = __uc_type(__i - __first) + 1;
 
-	    return __i;
+		    const pair<_DistanceType, _DistanceType> __pospos =
+		      __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
+
+		    ranges::iter_swap(__i++, ranges::next(__first, __pospos.first));
+		    ranges::iter_swap(__i++, ranges::next(__first, __pospos.second));
+		  }
+
+		return __i;
+	      }
 	  }
 
 	__distr_type __d;
@@ -2021,8 +2024,15 @@ namespace ranges
       borrowed_iterator_t<_Range>
       operator()(_Range&& __r, _Gen&& __g) const
       {
-	return (*this)(ranges::begin(__r), ranges::end(__r),
-		       std::forward<_Gen>(__g));
+	if constexpr (sized_range<_Range>
+		      && !sized_sentinel_for<sentinel_t<_Range>,
+					     iterator_t<_Range>>)
+	  return (*this)(ranges::begin(__r),
+			 ranges::begin(__r) + ranges::size(__r),
+			 std::forward<_Gen>(__g));
+	else
+	  return (*this)(ranges::begin(__r), ranges::end(__r),
+			 std::forward<_Gen>(__g));
       }
   };
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
index 70c6bdfc3d9e..4d633561508b 100644
--- a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
@@ -86,9 +86,27 @@ test02()
   ranges::shuffle(w, g);
 }
 
+struct non_default_sentinel_t { };
+
+template<std::input_or_output_iterator I>
+bool operator==(const I& i, non_default_sentinel_t)
+{ return i == std::default_sentinel; }
+
+void
+test03()
+{
+  // PR libstdc++/121917 - ranges::shuffle incorrectly requires its arguments
+  // to model sized_sentinel_for
+  int a[2]{};
+  std::counted_iterator iter(a, 2);
+  std::default_random_engine e;
+  std::ranges::shuffle(iter, non_default_sentinel_t{}, e);
+}
+
 int
 main()
 {
   test01();
   test02();
+  test03();
 }