[libc++][ranges] Implement `ranges::shuffle`.

[var-const]

Add a comment, update patch number.

[var-const]

Rebase.

[var-const]

Mark a libc++-specific check as such.

[var-const]

Improve comments, fix the CI.

[var-const]

libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp

243

The standard requirement that the number of swaps is "exact" instead of "at most" doesn't make sense to me. Is this a wording issue, or am I missing something?

[var-const]

Add forgotten hide-from-ABI annotations, undefine min/max macros.

[var-const]

Fix the CI.

[ldionne]

libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp

243

It is somewhat unusual indeed -- I don't think anybody would complain for making fewer swaps than specified.

[jloser]

libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp

243

There are some algorithms that enforce exactly a certain number of swaps (like swap_ranges), but I think the wording should be changed to say "at most" rather than "exactly" for ranges::shuffle. I filed https://github.com/cplusplus/draft/issues/5636 for clarification.

[huixie90]

LGTM

libcxx/test/support/test_iterators.h

828

not sure how this is used in the test but usually iter_swap would swap the underlying references i.e std::swap(*a.ptr_, *b.ptr_)

[huixie90]

libcxx/include/__algorithm/ranges_shuffle.h

70

not an issue but just write it down as I had thought about it.

Not sure how this could possibly go wrong but the original requirement is that you can do std::invoke(__gen). I guess it is ok to call __gen() instead of but I'd still prefer to stick to original requirement

libcxx/docs/Status/RangesAlgorithms.csv

 Merge,set_difference,Hui Xie,`D128983 <https://llvm.org/D128983>`_,✅
 Merge,set_intersection,Hui Xie,`D129233 <https://llvm.org/D129233>`_,✅
 Merge,set_symmetric_difference,Hui Xie,`D129520 <https://llvm.org/D129520>`_,✅
 Merge,set_union,Hui Xie,`D129657 <https://llvm.org/D129657>`_,✅
 Permutation,remove,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
 Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review
-Permutation,shuffle,Not assigned,n/a,Not started
+Permutation,shuffle,Konstantin Varlamov,`D130321 <https://llvm.org/D130321>`_,✅
 Permutation,unique,Not assigned,n/a,Not started
 Permutation,partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
 Permutation,stable_partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
 Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅
 Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅
 Permutation,nth_element,Konstantin Varlamov,`D128149 <https://llvm.org/D128149>`_,✅
 Permutation,partial_sort,Konstantin Varlamov,`D128744 <https://llvm.org/D128744>`_,✅
 Permutation,inplace_merge,Not assigned,n/a,Not started

libcxx/include/__algorithm/partial_sort.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
for (; __i != __last; ++__i)
       }
 
   }
   std::__sort_heap<_AlgPolicy, _Compare>(std::move(__first), std::move(__middle), __comp);
 
   return __i;
 }
 
-// TODO(ranges): once `ranges::shuffle` is implemented, remove this helper and make `__debug_randomize_range` support
-// sentinels.
-template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
-void __maybe_randomize(_RandomAccessIterator __first, _Sentinel __last) {
-  std::__debug_randomize_range<_AlgPolicy>(__first, _IterOps<_AlgPolicy>::next(__first, __last));
-}
-
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>
 _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last,
                                      _Compare& __comp) {
   if (__first == __middle)
       return _IterOps<_AlgPolicy>::next(__middle, __last);
 
-  std::__maybe_randomize<_AlgPolicy>(__first, __last);
+  std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 
   using _Comp_ref = typename __comp_ref_type<_Compare>::type;
   auto __last_iter = std::__partial_sort_impl<_AlgPolicy, _Comp_ref>(__first, __middle, __last, __comp);
 
-  std::__maybe_randomize<_AlgPolicy>(__middle, __last);
+  std::__debug_randomize_range<_AlgPolicy>(__middle, __last);
 
   return __last_iter;
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,

libcxx/include/__algorithm/ranges_shuffle.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
 #define _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
 
-#include <__algorithm/make_projected.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/shuffle.h>
 #include <__config>
-#include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 #include <__iterator/permutable.h>
-#include <__iterator/projected.h>
 #include <__random/uniform_random_bit_generator.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
-#include <__type_traits/remove_reference.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 namespace __shuffle {
 
 struct __fn {
+  // `std::shuffle` is more constrained than `std::ranges::shuffle`. `std::ranges::shuffle` only requires the given
+  // generator to satisfy the `std::uniform_random_bit_generator` concept. `std::shuffle` requires the given
+  // generator to meet the uniform random bit generator requirements; these requirements include satisfying
+  // `std::uniform_random_bit_generator` and add a requirement for the generator to provide a nested `result_type`
+  // typedef (see `[rand.req.urng]`).
+  //
+  // To reuse the implementation from `std::shuffle`, make the given generator meet the classic requirements by wrapping
+  // it into an adaptor type that forwards all of its interface and adds the required typedef.
+  template <class _Gen>
+  class _ClassicGenAdaptor {
+  private:
+    // The generator is not required to be copyable or movable, so it has to be stored as a reference.
+    _Gen& __gen;
+
+  public:
+    using result_type = invoke_result_t<_Gen&>;
+
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto min() { return __uncvref_t<_Gen>::min(); }
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto max() { return __uncvref_t<_Gen>::max(); }
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr explicit _ClassicGenAdaptor(_Gen& __g) : __gen(__g) {}
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr auto operator()() const { return __gen(); }
+  };
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Gen>
   requires permutable<_Iter> && uniform_random_bit_generator<remove_reference_t<_Gen>>
   _LIBCPP_HIDE_FROM_ABI
   _Iter operator()(_Iter __first, _Sent __last, _Gen&& __gen) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__gen;
-    return {};
+    _ClassicGenAdaptor<_Gen> __adapted_gen(__gen);
+    return std::__shuffle<_RangeAlgPolicy>(std::move(__first), std::move(__last), __adapted_gen);
   }
 
   template<random_access_range _Range, class _Gen>
   requires permutable<iterator_t<_Range>> && uniform_random_bit_generator<remove_reference_t<_Gen>>
   _LIBCPP_HIDE_FROM_ABI
   borrowed_iterator_t<_Range> operator()(_Range&& __range, _Gen&& __gen) const {
-    // TODO: implement
-    (void)__range; (void)__gen;
-    return {};
+    return (*this)(ranges::begin(__range), ranges::end(__range), std::forward<_Gen>(__gen));
   }
 
 };
 
 } // namespace __shuffle
 
 inline namespace __cpo {
   inline constexpr auto shuffle = __shuffle::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H

libcxx/include/__algorithm/shuffle.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
if (__d > 1)
             difference_type __i = __rand(__d);
             if (__i != difference_type(0))
               swap(*__first, *(__first + __i));
         }
     }
 }
 #endif
 
-template <class _AlgPolicy, class _RandomAccessIterator, class _UniformRandomNumberGenerator>
-void __shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
+template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
+_RandomAccessIterator __shuffle(
+    _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef uniform_int_distribution<ptrdiff_t> _Dp;
     typedef typename _Dp::param_type _Pp;
+
+    auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
+    auto __last = __original_last;
     difference_type __d = __last - __first;
     if (__d > 1)
     {
         _Dp __uid;
         for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
         {
             difference_type __i = __uid(__g, _Pp(0, __d));
             if (__i != difference_type(0))
                 _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
         }
     }
+
+    return __original_last;
 }
 
 template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _UniformRandomNumberGenerator&& __g) {
-  std::__shuffle<_ClassicAlgPolicy>(
+  (void)std::__shuffle<_ClassicAlgPolicy>(
       std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H

libcxx/include/__debug_utils/randomize_range.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___LIBCXX_DEBUG_RANDOMIZE_RANGE_H
 #define _LIBCPP___LIBCXX_DEBUG_RANDOMIZE_RANGE_H
 
 #include <__config>
 
 #ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
 #  include <__algorithm/shuffle.h>
 #  include <__type_traits/is_constant_evaluated.h>
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _Iterator>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __debug_randomize_range(_Iterator __first, _Iterator __last) {
+template <class _AlgPolicy, class _Iterator, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __debug_randomize_range(_Iterator __first, _Sentinel __last) {
 #ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
 #  ifdef _LIBCPP_CXX03_LANG
 #    error Support for unspecified stability is only for C++11 and higher
 #  endif
 
   if (!__libcpp_is_constant_evaluated())
     std::__shuffle<_AlgPolicy>(__first, __last, __libcpp_debug_randomizer());
 #else
   (void)__first;
   (void)__last;
 #endif
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___LIBCXX_DEBUG_RANDOMIZE_RANGE_H

libcxx/include/algorithm

template<forward_iterator I, sentinel_for<I> S, weakly_incrementable O>
     constexpr ranges::rotate_copy_result<I, O>
       ranges::rotate_copy(I first, I middle, S last, O result);                                     // since C++20
 
   template<forward_range R, weakly_incrementable O>
     requires indirectly_copyable<iterator_t<R>, O>
     constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
       ranges::rotate_copy(R&& r, iterator_t<R> middle, O result);                                   // since C++20
 
+  template<random_access_iterator I, sentinel_for<I> S, class Gen>
+    requires permutable<I> &&
+            uniform_random_bit_generator<remove_reference_t<Gen>>
+    I shuffle(I first, S last, Gen&& g);                                                           // Since C++20
+
+  template<random_access_range R, class Gen>
+    requires permutable<iterator_t<R>> &&
+            uniform_random_bit_generator<remove_reference_t<Gen>>
+    borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);                                                // Since C++20
+
   template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
            sentinel_for<I2> S2, class Pred = ranges::equal_to,
            class Proj1 = identity, class Proj2 = identity>
     requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
     constexpr subrange<I1>
       ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                      Proj1 proj1 = {}, Proj2 proj2 = {});                                           // since C++20
 

 #include <__algorithm/ranges_reverse_copy.h>
 #include <__algorithm/ranges_rotate_copy.h>
 #include <__algorithm/ranges_search.h>
 #include <__algorithm/ranges_search_n.h>
 #include <__algorithm/ranges_set_difference.h>
 #include <__algorithm/ranges_set_intersection.h>
 #include <__algorithm/ranges_set_symmetric_difference.h>
 #include <__algorithm/ranges_set_union.h>
+#include <__algorithm/ranges_shuffle.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_sort_heap.h>
 #include <__algorithm/ranges_stable_partition.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>

libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_random_shuffle.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-// UNSUPPORTED: c++03, c++11, c++14, c++17
-// UNSUPPORTED: libcpp-has-no-incomplete-ranges
-
-// <algorithm>
-
-// template<random_access_iterator I, sentinel_for<I> S, class Gen>
-//   requires permutable<I> &&
-//            uniform_random_bit_generator<remove_reference_t<Gen>>
-//   I shuffle(I first, S last, Gen&& g);                                                           // Since C++20
-//
-// template<random_access_range R, class Gen>
-//   requires permutable<iterator_t<R>> &&
-//            uniform_random_bit_generator<remove_reference_t<Gen>>
-//   borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);                                                // Since C++20
-
-#include <algorithm>
-#include <array>
-#include <concepts>
-#include <functional>
-#include <ranges>
-
-#include "almost_satisfies_types.h"
-#include "test_iterators.h"
-
-// TODO: SFINAE tests.
-
-constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
-
-  return true;
-}
-
-int main(int, char**) {
-  test();
-  static_assert(test());
-
-  return 0;
-}

libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<random_access_iterator I, sentinel_for<I> S, class Gen>
+//   requires permutable<I> &&
+//            uniform_random_bit_generator<remove_reference_t<Gen>>
+//   I shuffle(I first, S last, Gen&& g);                                                           // Since C++20
+//
+// template<random_access_range R, class Gen>
+//   requires permutable<iterator_t<R>> &&
+//            uniform_random_bit_generator<remove_reference_t<Gen>>
+//   borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);                                                // Since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#include <random>
+#include <ranges>
+#include <utility>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+class RandGen {
+public:
+  constexpr static size_t min() { return 0; }
+  constexpr static size_t max() { return 255; }
+
+  constexpr size_t operator()() {
+    flip = !flip;
+    return flip;
+  }
+
+private:
+  bool flip = false;
+};
+
+static_assert(std::uniform_random_bit_generator<RandGen>);
+// `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that
+// a type satisfying the required minimum is still accepted by `ranges::shuffle`.
+LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);
+
+struct BadGen {
+  constexpr static size_t min() { return 255; }
+  constexpr static size_t max() { return 0; }
+  constexpr size_t operator()() const;
+};
+static_assert(!std::uniform_random_bit_generator<BadGen>);
+
+// Test constraints of the (iterator, sentinel) overload.
+// ======================================================
+
+template <class Iter = int*, class Sent = int*, class Gen = RandGen>
+concept HasShuffleIter =
+    requires(Iter&& iter, Sent&& sent, Gen&& gen) {
+      std::ranges::shuffle(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Gen>(gen));
+    };
+
+static_assert(HasShuffleIter<int*, int*, RandGen>);
+
+// !random_access_iterator<I>
+static_assert(!HasShuffleIter<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasShuffleIter<RandomAccessIteratorBadIndex>);
+
+// !sentinel_for<S, I>
+static_assert(!HasShuffleIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasShuffleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !permutable<I>
+static_assert(!HasShuffleIter<PermutableNotForwardIterator>);
+static_assert(!HasShuffleIter<PermutableNotSwappable>);
+
+// !uniform_random_bit_generator<remove_reference_t<Gen>>
+static_assert(!HasShuffleIter<int*, int*, BadGen>);
+
+// Test constraints of the (range) overload.
+// =========================================
+
+template <class Range, class Gen = RandGen>
+concept HasShuffleRange =
+    requires(Range&& range, Gen&& gen) {
+      std::ranges::shuffle(std::forward<Range>(range), std::forward<Gen>(gen));
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasShuffleRange<R<int*>, RandGen>);
+
+// !random_access_range<R>
+static_assert(!HasShuffleRange<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasShuffleRange<RandomAccessRangeBadIndex>);
+
+// !permutable<iterator_t<R>>
+static_assert(!HasShuffleRange<PermutableNotForwardIterator>);
+static_assert(!HasShuffleRange<PermutableNotSwappable>);
+
+// !uniform_random_bit_generator<remove_reference_t<Gen>>
+static_assert(!HasShuffleRange<R<int*>, BadGen>);
+
+template <class Iter, class Sent, size_t N, class Gen>
+void test_one(const std::array<int, N> input, Gen gen) {
+  { // (iterator, sentinel) overload.
+    auto shuffled = input;
+    auto begin = Iter(shuffled.data());
+    auto end = Sent(Iter(shuffled.data() + shuffled.size()));
+
+    std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(begin, end, gen);
+
+    assert(result == Iter(shuffled.data() + shuffled.size()));
+    // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
+    //assert(std::ranges::is_permutation(shuffled, input);
+    {
+      auto shuffled_sorted = shuffled;
+      std::ranges::sort(shuffled_sorted);
+      auto original_sorted = input;
+      std::ranges::sort(original_sorted);
+      assert(shuffled_sorted == original_sorted);
+    }
+  }
+
+  { // (range) overload.
+    auto shuffled = input;
+    auto begin = Iter(shuffled.data());
+    auto end = Sent(Iter(shuffled.data() + shuffled.size()));
+    auto range = std::ranges::subrange(begin, end);
+
+    std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(range, gen);
+
+    assert(result == Iter(shuffled.data() + shuffled.size()));
+    // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
+    //assert(std::ranges::is_permutation(shuffled, input);
+    {
+      auto shuffled_sorted = shuffled;
+      std::ranges::sort(shuffled_sorted);
+      auto original_sorted = input;
+      std::ranges::sort(original_sorted);
+      assert(shuffled_sorted == original_sorted);
+    }
+  }
+}
+
+template <class Iter, class Sent>
+void test_iterators_iter_sent() {
+  RandGen gen;
+
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, gen);
+  // 1-element sequence.
+  test_one<Iter, Sent, 1>({1}, gen);
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({2, 1}, gen);
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({2, 1, 3}, gen);
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, gen);
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, gen);
+  // All elements are the same.
+  test_one<Iter, Sent, 3>({1, 1, 1}, gen);
+}
+
+template <class Iter>
+void test_iterators_iter() {
+  test_iterators_iter_sent<Iter, Iter>();
+  test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
+}
+
+void test_iterators() {
+  test_iterators_iter<random_access_iterator<int*>>();
+  test_iterators_iter<contiguous_iterator<int*>>();
+  test_iterators_iter<int*>();
+}
+
+// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of
+// the given generator object.
+template <class Gen, bool CheckConst = true>
+void test_generator() {
+  std::array in = {1, 2, 3, 4, 5, 6, 7, 8};
+  auto begin = in.begin();
+  auto end = in.end();
+
+  { // Lvalue.
+    Gen g;
+    std::ranges::shuffle(begin, end, g);
+    std::ranges::shuffle(in, g);
+  }
+
+  if constexpr (CheckConst) { // Const lvalue.
+    const Gen g;
+    std::ranges::shuffle(begin, end, g);
+    std::ranges::shuffle(in, g);
+  }
+
+  { // Prvalue.
+    std::ranges::shuffle(begin, end, Gen());
+    std::ranges::shuffle(in, Gen());
+  }
+
+  { // Xvalue.
+    Gen g1, g2;
+    std::ranges::shuffle(begin, end, std::move(g1));
+    std::ranges::shuffle(in, std::move(g2));
+  }
+}
+
+// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given
+// generator class has a const or non-const invocation operator (or both).
+void test_generators() {
+  struct GenBase {
+    constexpr static size_t min() { return 0; }
+    constexpr static size_t max() { return 255; }
+  };
+  struct NonconstGen : GenBase {
+    size_t operator()() { return 1; }
+  };
+  struct ConstGen : GenBase {
+    size_t operator()() const { return 1; }
+  };
+  struct ConstAndNonconstGen : GenBase {
+    size_t operator()() { return 1; }
+    size_t operator()() const { return 1; }
+  };
+
+  test_generator<ConstGen>();
+  test_generator<NonconstGen, /*CheckConst=*/false>();
+  test_generator<ConstAndNonconstGen>();
+}
+
+void test() {
+  test_iterators();
+  test_generators();
+
+  { // Complexity: Exactly `(last - first) - 1` swaps.
+    {
+      std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2}; //14
+
+      int swaps = 0;
+      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
+      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);
+
+      std::ranges::shuffle(begin, end, RandGen());
+      int expected = in.size() - 1;
+      // Note: our implementation doesn't perform a swap when the distribution returns 0, so the actual number of swaps
+      // might be less than specified in the standard.
+      assert(swaps <= expected);
+      swaps = 0;
+    }
+  }
+}
+
+int main(int, char**) {
+  test();
+  // Note: `ranges::shuffle` is not `constexpr`.
+
+  return 0;
+}

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 
 // (dangling_in1, dangling_in2, ...)
 template <class ExpectedT = std::ranges::dangling, class Func, std::ranges::range Input, class ...Args>
 constexpr void dangling_both(Func&& func, Input& in1, Input& in2, Args&& ...args) {
   decltype(auto) result = func(R(in1), R(in2), std::forward<Args>(args)...);
   static_assert(std::same_as<decltype(result), ExpectedT>);
 }
 
+std::mt19937 rand_gen() { return std::mt19937(); }
+
 // TODO: also check the iterator values for algorithms that return `*_result` types.
 constexpr bool test_all() {
   using std::ranges::dangling;
 
   using std::ranges::binary_transform_result;
   using std::ranges::copy_result;
   //using std::ranges::copy_backward_result;
   using std::ranges::copy_if_result;
constexpr bool test_all() {
   using std::ranges::set_union_result;
   using std::ranges::swap_ranges_result;
   using std::ranges::unary_transform_result;
   //using std::ranges::unique_copy_result;
 
   auto unary_pred = [](int i) { return i > 0; };
   auto binary_pred = [](int i, int j) { return i < j; };
   //auto gen = [] { return 42; };
-  //std::mt19937 rand_gen;
 
   std::array in = {1, 2, 3};
   std::array in2 = {4, 5, 6};
 
   auto mid = in.begin() + 1;
 
   std::array output = {7, 8, 9, 10, 11, 12};
   auto out = output.begin();
dangling_both<set_symmetric_difference_result<dangling, dangling, int*>>(
       std::ranges::set_symmetric_difference, in, in2, out);
   dangling_1st<set_union_result<dangling, int*, int*>>(std::ranges::set_union, in, in2, out);
   dangling_2nd<set_union_result<int*, dangling, int*>>(std::ranges::set_union, in, in2, out);
   dangling_both<set_union_result<dangling, dangling, int*>>(std::ranges::set_union, in, in2, out);
   dangling_1st(std::ranges::remove, in, x);
   dangling_1st(std::ranges::remove_if, in, unary_pred);
   dangling_1st(std::ranges::reverse, in);
   //dangling_1st(std::ranges::rotate, in, mid);
-  //dangling_1st(std::ranges::shuffle, in, rand_gen);
+  if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`.
+    dangling_1st(std::ranges::shuffle, in, rand_gen());
   //dangling_1st(std::ranges::unique, in);
   dangling_1st(std::ranges::partition, in, unary_pred);
   if (!std::is_constant_evaluated())
     dangling_1st(std::ranges::stable_partition, in, unary_pred);
   dangling_1st(std::ranges::sort, in);
   if (!std::is_constant_evaluated())
     dangling_1st(std::ranges::stable_sort, in);
   dangling_1st(std::ranges::partial_sort, in, mid);

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 
 // (in, mid, ...)
 template <class Func, std::ranges::range Input, class ...Args>
 constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&& ...args) {
   func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
   func(in, mid, std::forward<Args>(args)...);
 }
 
+std::mt19937 rand_gen() { return std::mt19937(); }
+
 template <class T>
 constexpr void run_tests() {
   std::array input = {T{1}, T{2}, T{3}};
   ProxyRange in{input};
   std::array input2 = {T{4}, T{5}, T{6}};
   ProxyRange in2{input2};
 
   auto mid = in.begin() + 1;
 
   std::array output = {T{4}, T{5}, T{6}, T{7}, T{8}, T{9}};
   ProxyIterator out{output.begin()};
   ProxyIterator out2{output.begin() + 1};
 
   T num{2};
   Proxy<T&> x{num};
   int count = 1;
 
   auto unary_pred = [](const Proxy<T&>&) { return true; };
   //auto binary_pred = [](const Proxy<T>&, const Proxy<T>&) { return return false; };
   auto binary_func = [](const Proxy<T>&, const Proxy<T>&) -> Proxy<T> { return Proxy<T>(T()); };
   //auto gen = [] { return Proxy<T>(T{42}); };
-  //std::mt19937 rand_gen;
 
   test(std::ranges::any_of, in, unary_pred);
   test(std::ranges::all_of, in, unary_pred);
   test(std::ranges::none_of, in, unary_pred);
   test(std::ranges::find, in, x);
   test(std::ranges::find_if, in, unary_pred);
   test(std::ranges::find_if_not, in, unary_pred);
   test(std::ranges::find_first_of, in, in2);
if constexpr (std::copyable<T>) {
     test(std::ranges::set_intersection, in, in2, out);
     test(std::ranges::set_symmetric_difference, in, in2, out);
     test(std::ranges::set_union, in, in2, out);
   }
   test(std::ranges::remove, in, x);
   test(std::ranges::remove_if, in, unary_pred);
   test(std::ranges::reverse, in);
   //test_mid(std::ranges::rotate, in, mid);
-  //test(std::ranges::shuffle, in, rand_gen);
-  //test(std::ranges::sample, in, out, count, rand_gen);
+  if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`.
+    test(std::ranges::shuffle, in, rand_gen());
+  //if (!std::is_constant_evaluated())
+  //  test(std::ranges::sample, in, out, count, rand_gen());
   //test(std::ranges::unique, in);
   test(std::ranges::partition, in, unary_pred);
   // TODO(ranges): `stable_partition` requires `ranges::rotate` to be implemented.
   //if (!std::is_constant_evaluated())
   // test(std::ranges::stable_partition, in, unary_pred);
   test(std::ranges::sort, in);
   // TODO(ranges): `stable_sort` requires `ranges::rotate` to be implemented.
   //if (!std::is_constant_evaluated())

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 }
 
 int *p;
 int a[10];
 auto odd = [](int x) { return x % 2 != 0; };
 auto triple = [](int x) { return 3*x; };
 //auto gen = [] { return 42; };
 //auto plus = [](int x, int y) { return x == y; };
-//std::mt19937 g;
+std::mt19937 g;
 
 // [algorithm.syn]
 
 static_assert(test(std::ranges::adjacent_find, a));
 static_assert(test(std::ranges::all_of, a, odd));
 static_assert(test(std::ranges::any_of, a, odd));
 static_assert(test(std::ranges::binary_search, a, 42));
 //static_assert(test(std::ranges::clamp, 42, 42, 42));

 static_assert(test(std::ranges::rotate_copy, a, a+5, a));
 //static_assert(test(std::ranges::sample, a, a, 5));
 static_assert(test(std::ranges::search, a, a));
 static_assert(test(std::ranges::search_n, a, 10, 42));
 static_assert(test(std::ranges::set_difference, a, a, a));
 static_assert(test(std::ranges::set_intersection, a, a, a));
 static_assert(test(std::ranges::set_symmetric_difference, a, a, a));
 static_assert(test(std::ranges::set_union, a, a, a));
-//static_assert(test(std::ranges::shuffle, a, g));
+static_assert(test(std::ranges::shuffle, a, g));
 static_assert(test(std::ranges::sort, a));
 static_assert(test(std::ranges::sort_heap, a));
 static_assert(test(std::ranges::stable_partition, a, odd));
 static_assert(test(std::ranges::stable_sort, a));
 //static_assert(test(std::ranges::starts_with, a, a));
 static_assert(test(std::ranges::swap_ranges, a, a));
 static_assert(test(std::ranges::transform, a, a, triple));
 //static_assert(test(std::ranges::unique, a));

libcxx/test/support/test_iterators.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
private:
     decltype(base(std::declval<It>())) base_;
 };
 
 namespace adl {
 
 class Iterator {
  public:
   using value_type = int;
+  using reference = int&;
   using difference_type = ptrdiff_t;
 
  private:
   value_type* ptr_ = nullptr;
   int* iter_moves_ = nullptr;
   int* iter_swaps_ = nullptr;
 
   constexpr Iterator(int* p, int* iter_moves, int* iter_swaps)
public:
   static constexpr Iterator TrackSwaps(int* p, int& iter_swaps) {
     return Iterator(p, /*iter_moves=*/nullptr, &iter_swaps);
   }
 
   constexpr int iter_moves() const { assert(iter_moves_); return *iter_moves_; }
   constexpr int iter_swaps() const { assert(iter_swaps_); return *iter_swaps_; }
 
   constexpr value_type& operator*() const { return *ptr_; }
+  constexpr reference operator[](difference_type n) const { return ptr_[n]; }
 
-  constexpr Iterator operator+(difference_type n) const {
-    return Iterator(ptr_ + n, iter_moves_, iter_swaps_);
+  friend constexpr Iterator operator+(Iterator i, difference_type n) {
+    return Iterator(i.ptr_ + n, i.iter_moves_, i.iter_swaps_);
+  }
+  friend constexpr Iterator operator+(difference_type n, Iterator i) {
+    return i + n;
+  }
+  constexpr Iterator operator-(difference_type n) const {
+    return Iterator(ptr_ - n, iter_moves_, iter_swaps_);
+  }
+  constexpr difference_type operator-(Iterator rhs) const {
+    return ptr_ - rhs.ptr_;
+  }
+  constexpr Iterator& operator+=(difference_type n) {
+    ptr_ += n;
+    return *this;
+  }
+  constexpr Iterator& operator-=(difference_type n) {
+    ptr_ -= n;
+    return *this;
   }
 
   constexpr Iterator& operator++() { ++ptr_; return *this; }
   constexpr Iterator operator++(int) {
     Iterator prev = *this;
     ++ptr_;
     return prev;
   }
 
   constexpr Iterator& operator--() { --ptr_; return *this; }
   constexpr Iterator operator--(int) {
     Iterator prev = *this;
     --ptr_;
     return prev;
   }
 
-  constexpr friend void iter_swap(Iterator a, Iterator) {
+  constexpr friend void iter_swap(Iterator a, Iterator b) {
+    std::swap(a.ptr_, b.ptr_);
     if (a.iter_swaps_) {
       ++(*a.iter_swaps_);
     }
   }
 
   constexpr friend value_type&& iter_move(Iterator iter) {
     if (iter.iter_moves_) {
       ++(*iter.iter_moves_);
     }
     return std::move(*iter);
   }
 
-  constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) { return lhs.ptr_ == rhs.ptr_; }
+  constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) {
+    return lhs.ptr_ == rhs.ptr_;
+  }
+  constexpr friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {
+    return lhs.ptr_ <=> rhs.ptr_;
+  }
 };
 
 } // namespace adl
 
 // Proxy
 // ======================================================================
 // Proxy that can wrap a value or a reference. It simulates C++23's tuple
 // but simplified to just hold one argument.