[Bug libstdc++/121917] [16 Regression] ranges::shuffle incorrectly requires its arguments to model sized_sentinel_for

[redi at gcc dot gnu.org via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=121917

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|ranges::shuffle incorrectly |[16 Regression]
                   |requires its arguments to   |ranges::shuffle incorrectly
                   |model sized_sentinel_for    |requires its arguments to
                   |                            |model sized_sentinel_for
     Ever confirmed|0                           |1
            Version|15.2.0                      |16.0
      Known to work|                            |15.2.1
             Status|UNCONFIRMED                 |NEW
      Known to fail|                            |16.0
   Last reconfirmed|                            |2025-09-11

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oops, fixed testcase:

#include <algorithm>
#include <iterator>
#include <random>

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; }

int main()
{
  int a[2]{};
  std::counted_iterator iter(a, 2);
  std::default_random_engine e;
  std::ranges::shuffle(iter, non_default_sentinel_t{}, e);
}


The problem is that we assume that last - first is valid, because we have a
random access iterator and its sentinel. But an arbitrary sentinel doesn't have
to model sized_sentinel_for.

This code was copied from std::shuffle where we always have two iterators of
the same type, so last - first is always valid. This is a regression because in
GCC 15 ranges::shuffle just forwarded its arguments to std::shuffle, so didn't
have this problem (but was non-conforming in other ways).

Patrick suggested that we just disable the optimization to use the URBG more
efficiently for the non-sized sentinel case:

-- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1968,6 +1968,8 @@ namespace ranges
        using __uc_type
          = common_type_t<typename remove_reference_t<_Gen>::result_type,
__ud_type>;

+       if constexpr (sized_sentinel_for<_Sent, _Iter>)
+         {
        const __uc_type __urngrange = __g.max() - __g.min();
        const __uc_type __urange = __uc_type(__last - __first);

@@ -2003,6 +2005,7 @@ namespace ranges

            return __i;
          }
+         }

        __distr_type __d;