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

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

(cherry picked from commit 6bdb64223473585f783572c9fbf0673b4b324a35)

14 files changed, 542 insertions, 59 deletions

diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv
index 131f698ee859..94fa26e8e0af 100644
--- a/libcxx/docs/Status/RangesAlgorithms.csv
+++ b/libcxx/docs/Status/RangesAlgorithms.csv
@@ -56,7 +56,7 @@ Write,replace_copy_if,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,✅
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
-Write,sample,Not assigned,n/a,Not started
+Write,sample,Konstantin Varlamov,`D130865 <https://llvm.org/D130865>`_,✅
 Write,unique_copy,Hui Xie,`D130404 <https://llvm.org/D130404>`_,✅
 Write,partition_copy,Konstantin Varlamov,`D130070 <https://llvm.org/D130070>`_,✅
 Write,partial_sort_copy,Konstantin Varlamov,`D130532 <https://llvm.org/D130532>`_,✅
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 1193f680c4fe..297e9029f3bf 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -133,6 +133,7 @@ set(files
   __algorithm/ranges_reverse.h
   __algorithm/ranges_reverse_copy.h
   __algorithm/ranges_rotate_copy.h
+  __algorithm/ranges_sample.h
   __algorithm/ranges_search.h
   __algorithm/ranges_search_n.h
   __algorithm/ranges_set_difference.h
@@ -178,6 +179,7 @@ set(files
   __algorithm/stable_sort.h
   __algorithm/swap_ranges.h
   __algorithm/transform.h
+  __algorithm/uniform_random_bit_generator_adaptor.h
   __algorithm/unique.h
   __algorithm/unique_copy.h
   __algorithm/unwrap_iter.h
diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h
index e060574652d4..2222b9883d60 100644
--- a/libcxx/include/__algorithm/iterator_operations.h
+++ b/libcxx/include/__algorithm/iterator_operations.h
@@ -10,9 +10,11 @@
 #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
 
 #include <__algorithm/iter_swap.h>
+#include <__algorithm/ranges_iterator_concept.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
+#include <__iterator/incrementable_traits.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
@@ -40,6 +42,12 @@ struct _IterOps<_RangeAlgPolicy> {
   template <class _Iter>
   using __value_type = iter_value_t<_Iter>;
 
+  template <class _Iter>
+  using __iterator_category = ranges::__iterator_concept<_Iter>;
+
+  template <class _Iter>
+  using __difference_type = iter_difference_t<_Iter>;
+
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
   static constexpr auto __iter_move = ranges::iter_move;
@@ -58,6 +66,12 @@ struct _IterOps<_ClassicAlgPolicy> {
   template <class _Iter>
   using __value_type = typename iterator_traits<_Iter>::value_type;
 
+  template <class _Iter>
+  using __iterator_category = typename iterator_traits<_Iter>::iterator_category;
+
+  template <class _Iter>
+  using __difference_type = typename iterator_traits<_Iter>::difference_type;
+
   // advance
   template <class _Iter, class _Distance>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
diff --git a/libcxx/include/__algorithm/ranges_sample.h b/libcxx/include/__algorithm/ranges_sample.h
new file mode 100644
index 000000000000..a8477f803788
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_sample.h
@@ -0,0 +1,74 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_SAMPLE_H
+#define _LIBCPP___ALGORITHM_RANGES_SAMPLE_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/sample.h>
+#include <__algorithm/uniform_random_bit_generator_adaptor.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/iterator_traits.h>
+#include <__random/uniform_random_bit_generator.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.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_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __sample {
+
+struct __fn {
+
+  template <input_iterator _Iter, sentinel_for<_Iter> _Sent, weakly_incrementable _OutIter, class _Gen>
+  requires (forward_iterator<_Iter> || random_access_iterator<_OutIter>) &&
+           indirectly_copyable<_Iter, _OutIter> &&
+           uniform_random_bit_generator<remove_reference_t<_Gen>>
+  _LIBCPP_HIDE_FROM_ABI
+  _OutIter operator()(_Iter __first, _Sent __last,
+                      _OutIter __out_first, iter_difference_t<_Iter> __n, _Gen&& __gen) const {
+    _ClassicGenAdaptor<_Gen> __adapted_gen(__gen);
+    return std::__sample<_RangeAlgPolicy>(
+        std::move(__first), std::move(__last), std::move(__out_first), __n, __adapted_gen);
+  }
+
+  template <input_range _Range, weakly_incrementable _OutIter, class _Gen>
+  requires (forward_range<_Range> || random_access_iterator<_OutIter>) &&
+           indirectly_copyable<iterator_t<_Range>, _OutIter> &&
+           uniform_random_bit_generator<remove_reference_t<_Gen>>
+  _LIBCPP_HIDE_FROM_ABI
+  _OutIter operator()(_Range&& __range, _OutIter __out_first, range_difference_t<_Range> __n, _Gen&& __gen) const {
+    return (*this)(ranges::begin(__range), ranges::end(__range),
+                   std::move(__out_first), __n, std::forward<_Gen>(__gen));
+  }
+
+};
+
+} // namespace __sample
+
+inline namespace __cpo {
+  inline constexpr auto sample = __sample::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_SAMPLE_H
diff --git a/libcxx/include/__algorithm/ranges_shuffle.h b/libcxx/include/__algorithm/ranges_shuffle.h
index b101a8582eac..9b7f81e489b3 100644
--- a/libcxx/include/__algorithm/ranges_shuffle.h
+++ b/libcxx/include/__algorithm/ranges_shuffle.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/shuffle.h>
+#include <__algorithm/uniform_random_bit_generator_adaptor.h>
 #include <__config>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
@@ -32,43 +33,12 @@
 
 #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>>
@@ -96,8 +66,6 @@ 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/sample.h b/libcxx/include/__algorithm/sample.h
index e04466a08d5a..f403ba612580 100644
--- a/libcxx/include/__algorithm/sample.h
+++ b/libcxx/include/__algorithm/sample.h
@@ -9,12 +9,14 @@
 #ifndef _LIBCPP___ALGORITHM_SAMPLE_H
 #define _LIBCPP___ALGORITHM_SAMPLE_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/min.h>
 #include <__assert>
 #include <__config>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__random/uniform_int_distribution.h>
+#include <__utility/move.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -26,13 +28,14 @@ _LIBCPP_PUSH_MACROS
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _PopulationIterator, class _SampleIterator, class _Distance,
+template <class _AlgPolicy,
+          class _PopulationIterator, class _PopulationSentinel, class _SampleIterator, class _Distance,
           class _UniformRandomNumberGenerator>
 _LIBCPP_INLINE_VISIBILITY
 _SampleIterator __sample(_PopulationIterator __first,
-                         _PopulationIterator __last, _SampleIterator __output_iter,
+                         _PopulationSentinel __last, _SampleIterator __output_iter,
                          _Distance __n,
-                         _UniformRandomNumberGenerator & __g,
+                         _UniformRandomNumberGenerator& __g,
                          input_iterator_tag) {
 
   _Distance __k = 0;
@@ -47,15 +50,16 @@ _SampleIterator __sample(_PopulationIterator __first,
   return __output_iter + _VSTD::min(__n, __k);
 }
 
-template <class _PopulationIterator, class _SampleIterator, class _Distance,
+template <class _AlgPolicy,
+          class _PopulationIterator, class _PopulationSentinel, class _SampleIterator, class _Distance,
           class _UniformRandomNumberGenerator>
 _LIBCPP_INLINE_VISIBILITY
 _SampleIterator __sample(_PopulationIterator __first,
-                         _PopulationIterator __last, _SampleIterator __output_iter,
+                         _PopulationSentinel __last, _SampleIterator __output_iter,
                          _Distance __n,
                          _UniformRandomNumberGenerator& __g,
                          forward_iterator_tag) {
-  _Distance __unsampled_sz = _VSTD::distance(__first, __last);
+  _Distance __unsampled_sz = _IterOps<_AlgPolicy>::distance(__first, __last);
   for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
     _Distance __r = uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
     if (__r < __n) {
@@ -66,24 +70,22 @@ _SampleIterator __sample(_PopulationIterator __first,
   return __output_iter;
 }
 
-template <class _PopulationIterator, class _SampleIterator, class _Distance,
+template <class _AlgPolicy,
+          class _PopulationIterator, class _PopulationSentinel, class _SampleIterator, class _Distance,
           class _UniformRandomNumberGenerator>
 _LIBCPP_INLINE_VISIBILITY
 _SampleIterator __sample(_PopulationIterator __first,
-                         _PopulationIterator __last, _SampleIterator __output_iter,
+                         _PopulationSentinel __last, _SampleIterator __output_iter,
                          _Distance __n, _UniformRandomNumberGenerator& __g) {
-  typedef typename iterator_traits<_PopulationIterator>::iterator_category
-        _PopCategory;
-  typedef typename iterator_traits<_PopulationIterator>::difference_type
-        _Difference;
-  static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value ||
-                __is_cpp17_random_access_iterator<_SampleIterator>::value,
-                "SampleIterator must meet the requirements of RandomAccessIterator");
-  typedef typename common_type<_Distance, _Difference>::type _CommonType;
   _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
-  return _VSTD::__sample(
-      __first, __last, __output_iter, _CommonType(__n),
-      __g, _PopCategory());
+
+  using _PopIterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_PopulationIterator>;
+  using _Difference = typename _IterOps<_AlgPolicy>::template __difference_type<_PopulationIterator>;
+  using _CommonType = typename common_type<_Distance, _Difference>::type;
+
+  return std::__sample<_AlgPolicy>(
+      std::move(__first), std::move(__last), std::move(__output_iter), _CommonType(__n),
+      __g, _PopIterCategory());
 }
 
 #if _LIBCPP_STD_VER > 14
@@ -93,8 +95,14 @@ inline _LIBCPP_INLINE_VISIBILITY
 _SampleIterator sample(_PopulationIterator __first,
                        _PopulationIterator __last, _SampleIterator __output_iter,
                        _Distance __n, _UniformRandomNumberGenerator&& __g) {
-    return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
+  static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value ||
+                __is_cpp17_random_access_iterator<_SampleIterator>::value,
+                "SampleIterator must meet the requirements of RandomAccessIterator");
+
+  return std::__sample<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), std::move(__output_iter), __n, __g);
 }
+
 #endif // _LIBCPP_STD_VER > 14
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h b/libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h
new file mode 100644
index 000000000000..04a67752dd0b
--- /dev/null
+++ b/libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h
@@ -0,0 +1,62 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_UNIFORM_RANDOM_BIT_GENERATOR_ADAPTOR_H
+#define _LIBCPP___ALGORITHM_RANGES_UNIFORM_RANDOM_BIT_GENERATOR_ADAPTOR_H
+
+#include <__config>
+#include <__functional/invoke.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// Range versions of random algorithms (e.g. `std::shuffle`) are less constrained than their classic counterparts.
+// Range algorithms only require the given generator to satisfy the `std::uniform_random_bit_generator` concept.
+// Classic algorithms require 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 be able to reuse classic implementations, 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(); }
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP_STD_VER > 17
+
+#endif // _LIBCPP___ALGORITHM_RANGES_UNIFORM_RANDOM_BIT_GENERATOR_ADAPTOR_H
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index 0a4077837a99..15ba340aa766 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -758,6 +758,18 @@ 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<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen>
+    requires (forward_iterator<I> || random_access_iterator<O>) &&
+            indirectly_copyable<I, O> &&
+            uniform_random_bit_generator<remove_reference_t<Gen>>
+    O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g);                              // Since C++20
+
+  template<input_range R, weakly_incrementable O, class Gen>
+    requires (forward_range<R> || random_access_iterator<O>) &&
+            indirectly_copyable<iterator_t<R>, O> &&
+            uniform_random_bit_generator<remove_reference_t<Gen>>
+    O sample(R&& r, O out, range_difference_t<R> n, Gen&& g);                                       // 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>>
@@ -1773,6 +1785,7 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_reverse_copy.h>
 #include <__algorithm/ranges_rotate_copy.h>
+#include <__algorithm/ranges_sample.h>
 #include <__algorithm/ranges_search.h>
 #include <__algorithm/ranges_search_n.h>
 #include <__algorithm/ranges_set_difference.h>
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index 8777db3e72db..94da66c6d0e7 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -372,6 +372,7 @@ module std [system] {
       module ranges_reverse                  { private header "__algorithm/ranges_reverse.h" }
       module ranges_reverse_copy             { private header "__algorithm/ranges_reverse_copy.h" }
       module ranges_rotate_copy              { private header "__algorithm/ranges_rotate_copy.h" }
+      module ranges_sample                   { private header "__algorithm/ranges_sample.h" }
       module ranges_search                   { private header "__algorithm/ranges_search.h" }
       module ranges_search_n                 { private header "__algorithm/ranges_search_n.h" }
       module ranges_set_difference           { private header "__algorithm/ranges_set_difference.h" }
@@ -385,6 +386,9 @@ module std [system] {
       module ranges_stable_sort              { private header "__algorithm/ranges_stable_sort.h" }
       module ranges_swap_ranges              { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform                { private header "__algorithm/ranges_transform.h" }
+      module uniform_random_bit_generator_adaptor {
+        private header "__algorithm/uniform_random_bit_generator_adaptor.h"
+      }
       module ranges_unique                   { private header "__algorithm/ranges_unique.h" }
       module ranges_unique_copy              { private header "__algorithm/ranges_unique_copy.h" }
       module ranges_upper_bound              { private header "__algorithm/ranges_upper_bound.h" }
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
index 516991b2ac26..d43bf1302cba 100644
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -170,6 +170,7 @@ END-SCRIPT
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_reverse_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse_copy.h'}}
 #include <__algorithm/ranges_rotate_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate_copy.h'}}
+#include <__algorithm/ranges_sample.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sample.h'}}
 #include <__algorithm/ranges_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search.h'}}
 #include <__algorithm/ranges_search_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search_n.h'}}
 #include <__algorithm/ranges_set_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.h'}}
@@ -215,6 +216,7 @@ END-SCRIPT
 #include <__algorithm/stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/stable_sort.h'}}
 #include <__algorithm/swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/swap_ranges.h'}}
 #include <__algorithm/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/transform.h'}}
+#include <__algorithm/uniform_random_bit_generator_adaptor.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/uniform_random_bit_generator_adaptor.h'}}
 #include <__algorithm/unique.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unique.h'}}
 #include <__algorithm/unique_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unique_copy.h'}}
 #include <__algorithm/unwrap_iter.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unwrap_iter.h'}}
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.pass.cpp
new file mode 100644
index 000000000000..1b15acd715ac
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.random.sample/ranges_sample.pass.cpp
@@ -0,0 +1,334 @@
+//===----------------------------------------------------------------------===//
+//
+// 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<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen>
+//   requires (forward_iterator<I> || random_access_iterator<O>) &&
+//           indirectly_copyable<I, O> &&
+//           uniform_random_bit_generator<remove_reference_t<Gen>>
+//   O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g);                              // Since C++20
+//
+// template<input_range R, weakly_incrementable O, class Gen>
+//   requires (forward_range<R> || random_access_iterator<O>) &&
+//           indirectly_copyable<iterator_t<R>, O> &&
+//           uniform_random_bit_generator<remove_reference_t<Gen>>
+//   O sample(R&& r, O out, range_difference_t<R> n, 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 Out = int*, class Gen = RandGen>
+concept HasSampleIter =
+    requires(Iter&& iter, Sent&& sent, Out&& out, std::iter_difference_t<Iter> n, Gen&& gen) {
+      std::ranges::sample(std::forward<Iter>(iter), std::forward<Sent>(sent),
+                          std::forward<Out>(out), n, std::forward<Gen>(gen));
+    };
+
+static_assert(HasSampleIter<int*, int*, int*, RandGen>);
+
+// !input_iterator<I>
+static_assert(!HasSampleIter<InputIteratorNotDerivedFrom>);
+static_assert(!HasSampleIter<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasSampleIter<InputIteratorNotInputOrOutputIterator>);
+
+// !sentinel_for<S, I>
+static_assert(!HasSampleIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasSampleIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !weakly_incrementable<O>
+static_assert(!HasSampleIter<int*, int*, WeaklyIncrementableNotMovable>);
+
+// (forward_iterator<I> || random_access_iterator<O>)
+static_assert(HasSampleIter<
+    forward_iterator<int*>, forward_iterator<int*>,
+    cpp20_output_iterator<int*>
+>);
+static_assert(HasSampleIter<
+    cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>,
+    random_access_iterator<int*>
+>);
+// !(forward_iterator<I> || random_access_iterator<O>)
+static_assert(!HasSampleIter<
+    cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>,
+    cpp20_output_iterator<int*>
+>);
+
+// !indirectly_copyable<I, O>
+static_assert(!HasSampleIter<int*, int*, int**>);
+
+// !uniform_random_bit_generator<remove_reference_t<Gen>>
+static_assert(!HasSampleIter<int*, int*, int*, BadGen>);
+
+// Test constraints of the (range) overload.
+// =========================================
+
+template <class Range, class Out = int*, class Gen = RandGen>
+concept HasSampleRange =
+    requires(Range&& range, Out&& out, std::ranges::range_difference_t<Range> n, Gen&& gen) {
+      std::ranges::sample(std::forward<Range>(range), std::forward<Out>(out), n, std::forward<Gen>(gen));
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasSampleRange<R<int*>, int*, RandGen>);
+
+// !input_range<R>
+static_assert(!HasSampleRange<InputRangeNotDerivedFrom>);
+static_assert(!HasSampleRange<InputRangeNotIndirectlyReadable>);
+static_assert(!HasSampleRange<InputRangeNotInputOrOutputIterator>);
+
+// !weakly_incrementable<O>
+static_assert(!HasSampleRange<R<int*>, WeaklyIncrementableNotMovable>);
+
+// (forward_range<R> || random_access_iterator<O>)
+static_assert(HasSampleRange<
+    R<forward_iterator<int*>>,
+    cpp20_output_iterator<int*>
+>);
+static_assert(HasSampleRange<
+    R<cpp20_input_iterator<int*>>,
+    random_access_iterator<int*>
+>);
+// !(forward_range<R> || random_access_iterator<O>)
+static_assert(!HasSampleRange<
+    R<cpp20_input_iterator<int*>>,
+    cpp20_output_iterator<int*>
+>);
+
+// !indirectly_copyable<I, O>
+static_assert(!HasSampleRange<R<int*>, int**>);
+
+// !uniform_random_bit_generator<remove_reference_t<Gen>>
+static_assert(!HasSampleRange<R<int*>, int*, BadGen>);
+
+template <class Iter, class Sent, class Out, size_t N, class Gen>
+void test_one(std::array<int, N> in, size_t n, Gen gen) {
+  assert(n <= static_cast<size_t>(N));
+
+  auto verify_is_subsequence = [&] (auto output) {
+    auto sorted_input = in;
+    std::ranges::sort(sorted_input);
+    auto sorted_output = std::ranges::subrange(output.begin(), output.begin() + n);
+    std::ranges::sort(sorted_output);
+    assert(std::ranges::includes(sorted_input, sorted_output));
+  };
+
+  { // (iterator, sentinel) overload.
+    auto begin = Iter(in.data());
+    auto end = Sent(Iter(in.data() + in.size()));
+    std::array<int, N> output;
+    auto out = Out(output.begin());
+
+    std::same_as<Out> decltype(auto) result = std::ranges::sample(
+        std::move(begin), std::move(end), std::move(out), n, gen);
+    assert(base(result) == output.data() + n);
+    verify_is_subsequence(output);
+    // The output of `sample` is implementation-specific.
+  }
+
+  { // (range) overload.
+    auto begin = Iter(in.data());
+    auto end = Sent(Iter(in.data() + in.size()));
+    std::array<int, N> output;
+    auto out = Out(output.begin());
+
+    std::same_as<Out> decltype(auto) result = std::ranges::sample(std::ranges::subrange(
+        std::move(begin), std::move(end)), std::move(out), n, gen);
+    assert(base(result) == output.data() + n);
+    verify_is_subsequence(output);
+    // The output of `sample` is implementation-specific.
+  }
+}
+
+template <class Iter, class Sent, class Out>
+void test_iterators_iter_sent_out() {
+  RandGen gen;
+
+  // Empty sequence.
+  test_one<Iter, Sent, Out, 0>({}, 0, gen);
+  // 1-element sequence.
+  test_one<Iter, Sent, Out, 1>({1}, 1, gen);
+  // 2-element sequence.
+  test_one<Iter, Sent, Out, 2>({1, 2}, 1, gen);
+  test_one<Iter, Sent, Out, 2>({1, 2}, 2, gen);
+  // n == 0.
+  test_one<Iter, Sent, Out, 3>({1, 2, 3}, 0, gen);
+
+  // Longer sequence.
+  {
+    std::array input = {1, 8, 2, 3, 4, 6, 5, 7};
+    for (int i = 0; i <= static_cast<int>(input.size()); ++i){
+      test_one<Iter, Sent, Out, input.size()>(input, i, gen);
+    }
+  }
+}
+
+template <class Iter, class Sent>
+void test_iterators_iter_sent() {
+  if constexpr (std::forward_iterator<Iter>) {
+    test_iterators_iter_sent_out<Iter, Sent, cpp20_output_iterator<int*>>();
+    test_iterators_iter_sent_out<Iter, Sent, forward_iterator<int*>>();
+  }
+  test_iterators_iter_sent_out<Iter, Sent, random_access_iterator<int*>>();
+  test_iterators_iter_sent_out<Iter, Sent, contiguous_iterator<int*>>();
+  test_iterators_iter_sent_out<Iter, Sent, int*>();
+}
+
+template <class Iter>
+void test_iterators_iter() {
+  if constexpr (std::sentinel_for<Iter, Iter>) {
+    test_iterators_iter_sent<Iter, Iter>();
+  }
+  test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
+}
+
+void test_iterators() {
+  test_iterators_iter<cpp20_input_iterator<int*>>();
+  test_iterators_iter<random_access_iterator<int*>>();
+  test_iterators_iter<contiguous_iterator<int*>>();
+  test_iterators_iter<int*>();
+  test_iterators_iter<const 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};
+  constexpr int N = 5;
+  std::array<int, N> output;
+  auto begin = in.begin();
+  auto end = in.end();
+  auto out = output.begin();
+
+  { // Lvalue.
+    Gen g;
+    std::ranges::sample(begin, end, out, N, g);
+    std::ranges::sample(in, out, N, g);
+  }
+
+  if constexpr (CheckConst) { // Const lvalue.
+    const Gen g;
+    std::ranges::sample(begin, end, out, N, g);
+    std::ranges::sample(in, out, N, g);
+  }
+
+  { // Prvalue.
+    std::ranges::sample(begin, end, out, N, Gen());
+    std::ranges::sample(in, out, N, Gen());
+  }
+
+  { // Xvalue.
+    Gen g1, g2;
+    std::ranges::sample(begin, end, out, N, std::move(g1));
+    std::ranges::sample(in, out, N, 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();
+
+  { // Stable (if `I` models `forward_iterator`).
+    struct OrderedValue {
+      int value;
+      int original_order;
+      bool operator==(const OrderedValue&) const = default;
+      auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; }
+    };
+
+    const std::array<OrderedValue, 8> in = {{
+      {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}
+    }};
+
+    { // (iterator, sentinel) overload.
+      std::array<OrderedValue, in.size()> out;
+      std::ranges::sample(in.begin(), in.end(), out.begin(), in.size(), RandGen());
+      assert(out == in);
+    }
+
+    { // (range) overload.
+      std::array<OrderedValue, in.size()> out;
+      std::ranges::sample(in, out.begin(), in.size(), RandGen());
+      assert(out == in);
+    }
+  }
+}
+
+int main(int, char**) {
+  test();
+  // Note: `ranges::sample` is not `constexpr`.
+
+  return 0;
+}
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
index 12d764aaf6d0..013b6d7984dd 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
@@ -139,7 +139,7 @@ constexpr bool test_all() {
   // `swap_ranges` has neither a projection nor a predicate.
   // `reverse_copy` has neither a projection nor a predicate.
   // `rotate_copy` has neither a projection nor a predicate.
-  // `sample` has no requirement that the given generator be invoked via `std::invoke`.
+  // For `sample`, whether the given generator is invoked via `std::invoke` is not observable.
   test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val);
   test(std::ranges::partition_copy, in, out, out2, &Foo::unary_pred, &Bar::val);
   test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
@@ -152,7 +152,7 @@ constexpr bool test_all() {
   test(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val);
   // `reverse` has neither a projection nor a predicate.
   // `rotate` has neither a projection nor a predicate.
-  // `shuffle` has neither a projection nor a predicate.
+  // For `shuffle`, whether the given generator is invoked via `std::invoke` is not observable.
   test(std::ranges::unique, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::partition, in, &Foo::unary_pred, &Bar::val);
   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 b5dd483d6f71..0dda0cf6ca7a 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
@@ -150,8 +150,10 @@ constexpr void run_tests() {
   //test_mid(std::ranges::rotate, in, mid);
   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());
+  if (!std::is_constant_evaluated()) {
+    if constexpr (std::copyable<T>)
+      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 6e0ab4495f7d..2f137d07772a 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
@@ -130,7 +130,7 @@ static_assert(test(std::ranges::reverse, a));
 static_assert(test(std::ranges::reverse_copy, a, a));
 //static_assert(test(std::ranges::rotate, a, a+5));
 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::sample, a, a, 5, g));
 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));