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

Differential Revision: https://reviews.llvm.org/D130321

12 files changed, 375 insertions, 85 deletions

diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv
index 787ec9b08d4f..40ebffa1adf6 100644
--- a/libcxx/docs/Status/RangesAlgorithms.csv
+++ b/libcxx/docs/Status/RangesAlgorithms.csv
@@ -69,7 +69,7 @@ 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>`_,✅
diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h
index cb6887e39bfd..24016e5cf5a5 100644
--- a/libcxx/include/__algorithm/partial_sort.h
+++ b/libcxx/include/__algorithm/partial_sort.h
@@ -54,14 +54,6 @@ _RandomAccessIterator __partial_sort_impl(
   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,
@@ -69,12 +61,12 @@ _RandomAccessIterator __partial_sort(_RandomAccessIterator __first, _RandomAcces
   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;
 }
diff --git a/libcxx/include/__algorithm/ranges_shuffle.h b/libcxx/include/__algorithm/ranges_shuffle.h
index bf9c28b4ce26..b101a8582eac 100644
--- a/libcxx/include/__algorithm/ranges_shuffle.h
+++ b/libcxx/include/__algorithm/ranges_shuffle.h
@@ -9,23 +9,22 @@
 #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
@@ -33,29 +32,57 @@
 
 #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));
   }
 
 };
@@ -69,6 +96,8 @@ inline namespace __cpo {
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
diff --git a/libcxx/include/__algorithm/shuffle.h b/libcxx/include/__algorithm/shuffle.h
index 077881562192..e32c6a7608ba 100644
--- a/libcxx/include/__algorithm/shuffle.h
+++ b/libcxx/include/__algorithm/shuffle.h
@@ -136,11 +136,15 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
 }
 #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)
     {
@@ -152,12 +156,14 @@ void __shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _Uni
                 _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));
 }
 
diff --git a/libcxx/include/__debug_utils/randomize_range.h b/libcxx/include/__debug_utils/randomize_range.h
index 9ed22556c416..9843709019d4 100644
--- a/libcxx/include/__debug_utils/randomize_range.h
+++ b/libcxx/include/__debug_utils/randomize_range.h
@@ -22,8 +22,9 @@
 
 _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
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index aea6ad86eb59..5958ad1a95af 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -710,6 +710,16 @@ namespace ranges {
     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>
@@ -1603,6 +1613,7 @@ template <class BidirectionalIterator, class Compare>
 #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>
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_random_shuffle.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_random_shuffle.pass.cpp
deleted file mode 100644
index 5277a805a6c9..000000000000
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_random_shuffle.pass.cpp
+++ /dev/null
@@ -1,48 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// 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;
-}
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp
new file mode 100644
index 000000000000..b3abf61f7f7e
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.shuffle/ranges_shuffle.pass.cpp
@@ -0,0 +1,269 @@
+//===----------------------------------------------------------------------===//
+//
+// 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;
+}
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
index 52d9f26280fb..e474c65d49ae 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
@@ -60,6 +60,8 @@ constexpr void dangling_both(Func&& func, Input& in1, Input& in2, 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;
@@ -91,7 +93,6 @@ constexpr bool test_all() {
   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};
@@ -181,7 +182,8 @@ constexpr bool test_all() {
   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())
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
index d13ff1fcc728..b7d32b18b5b8 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
@@ -48,6 +48,8 @@ constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> m
   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}};
@@ -69,7 +71,6 @@ constexpr void run_tests() {
   //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);
@@ -148,8 +149,10 @@ constexpr void run_tests() {
   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.
diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
index 8327090f1e79..e8861c37ab2c 100644
--- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
+++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
@@ -57,7 +57,7 @@ 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]
 
@@ -137,7 +137,7 @@ 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));
diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h
index 2f20e50e54c2..a1eef1a2a10a 100644
--- a/libcxx/test/support/test_iterators.h
+++ b/libcxx/test/support/test_iterators.h
@@ -758,6 +758,7 @@ namespace adl {
 class Iterator {
  public:
   using value_type = int;
+  using reference = int&;
   using difference_type = ptrdiff_t;
 
  private:
@@ -786,9 +787,27 @@ class Iterator {
   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; }
@@ -805,7 +824,8 @@ class Iterator {
     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_);
     }
@@ -818,7 +838,12 @@ class Iterator {
     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