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

[var-const]

Use the actual patch number.

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

139

For some reason, the compiler fails to parse this construct as an initializer list of OrderedValues without this hint.

libcxx/test/support/almost_satisfies_types.h

304 ↗

(On Diff #437076)

This is copied from the sort patch.

[Mordante]

Thanks for working on this! Some small remarks.

libcxx/include/__algorithm/ranges_stable_sort.h

39

Please remove the constexpr

libcxx/include/__algorithm/stable_sort.h

224

While you're at it.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

140

I would suggest to make the original_order member a simple integer sequence: 1, 2, 3, etc. That makes it easier to verify whether the output is correct. Identical values will have incrementing values.

151

Is the trailing comma allowed?

169

It would be good to validate stability in these tests too.

247

Here we can validate complexity. Obviously implementations can make different choices regarding when there's not "enough extra memory" but we can test the N log (N) for a small number of items.

256

Interesting since it's possible to allocate memory in constexpr functions.

[var-const]

Apply feedback from the sort patch where appropriate.

[var-const]

Rebase on main, apply changes from the ranges::sort patch, address feedback.

libcxx/include/__algorithm/ranges_stable_sort.h

39

Thanks!

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

140

I started with that, but then I had the idea of enumerating each duplicate value instead (read those 31, 32, 33 as 3.1, 3.2, 3.3, etc.). I think it makes it more readable because following the numbering within a duplicate is much easier than following the numbering across all the elements. What do you think?

151

Yes. Removed it for redundancy.

169

To clarify, do you mean all the tests in test()? Or just the tests with a custom comparator?

247

Similar to the sort patch, I don't think we have a great way of doing this:

• we can use the exact number of operations our implementation happens to perform (we have some precedent in e.g. test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/complexity.pass.cpp), but that would make it libc++-specific and, IMO, has limited usefulness;
• simply testing for num_operations < N*log(N) isn't going to work because it's actually k*N*log(N), where k is an arbitrary constant;
• the "proper" way would be to test with increasingly large inputs and applying some math to calculate the growth factor, but that seems like a sizable project in itself, even assuming it's worth the implementation effort.

256

I know that P0202 was adding constexpr to algorithms. At the time (in 2017), making stable_sort constexpr was infeasible:

Algorithms stable_partition, inplace_merge and stable_sort allocate memory, construct variables using placement new, use unique_ptr and do other things not acceptable in constexpr expressions. Making those algorithms constexpr seems to be a hard task that would require a lot of intrinsics. Those algorithms are not marked with constexpr in this wording.

I don't know if there's been any work in that direction since then. Perhaps it's ripe for a new paper?

[philnik]

Nothing major, but I'd like to take another look after my comments have been addressed.

libcxx/include/__algorithm/ranges_stable_sort.h

42–44

Why is this not static but instead marked const?

43

Maybe name it __ranges_stable_sort_impl?

45–46

This probably also applies to ranges::sort.

libcxx/include/__algorithm/stable_sort.h

225

Would you be interested in removing std::get_temporary_buffer and std::return_temporary_buffer in a follow-up patch? It's deprecated and just forwards to new and delete.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

130–133

As always, I think this should work. I'm not yet fluent in spaceship operator.

138

Does it not work to just use std::array orig_in = {V{10, 101}, ...}?

188

Isn't this be unnecessary and even counter-productive?

214

Again, I don't think this should be here.

[ldionne]

I'll let others give final approval, but this LGTM.

libcxx/docs/Status/RangesAlgorithms.csv

77

Once you commit this, it'll be done, not under review.

[Mordante]

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

140

How do you feel about making the original_order a double and use 3.1?

Since the same constants written the same in the source there shouldn't be an issue with floating point rounding.

151

TIL, fun that it's allowed in some places.

169

I think it's mainly important for this test and the ones below.

247

Here http://eel.is/c++draft/stable.sort#5 lists the exact number of comparisons to do and that the number of projections is double of that. So I think we can use that value as an upper bound, for example with N = 10.

256

I didn't investigate the reason, but this is indeed what I expected :-)

Based on the unanimous consent in this poll https://github.com/cplusplus/papers/issues/1222#issuecomment-1159203566
the time is indeed ripe and a paper is already available.

[var-const]

Address feedback

libcxx/include/__algorithm/ranges_stable_sort.h

42–44

Thanks for spotting!

43

I somewhat prefer the current version (name of the algorithm + fn to indicate that the function is contained within the function object + impl for disambiguation). I'd keep the current state unless you feel strongly about it.

45–46

Thanks! Fixed both.

libcxx/include/__algorithm/stable_sort.h

225

Yes, I can do this in a follow-up (unless you beat me to it :) ).

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

138

It does -- it just gives an easy way to make sure both arrays have the same number of elements (since they are long, it's easier to make a mistake).

140

I really like this, thanks -- makes the intention a lot clearer and looks better, too.

188

It's used to compare check the in array after it's sorted:

assert((in == std::array{A{1}, A{2}, A{3}}));

Perhaps I'm missing something?

214

Same -- it's necessary to compare arrays.

247

I'd rather do this in a follow-up. I think perhaps it would be good to have a dedicated test file for this, similar to the robust_against_copying_*.

256

Thanks for finding that paper!

[Mordante]

In D127834#3595819, @philnik wrote:

Nothing major, but I'd like to take another look after my comments have been addressed.

LGTM, I leave the final approval to @philnik.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

247

Sounds good to me.

[philnik]

LGTM.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp

188

Ah OK, I missed that.

libcxx/benchmarks/CMakeLists.txt

 set(BENCHMARK_TESTS
     algorithms/lower_bound.bench.cpp
     algorithms/make_heap.bench.cpp
     algorithms/make_heap_then_sort_heap.bench.cpp
     algorithms/min_max_element.bench.cpp
     algorithms/pop_heap.bench.cpp
     algorithms/push_heap.bench.cpp
     algorithms/ranges_sort.bench.cpp
+    algorithms/ranges_stable_sort.bench.cpp
     algorithms/sort.bench.cpp
     algorithms/sort_heap.bench.cpp
     algorithms/stable_sort.bench.cpp
     algorithms.partition_point.bench.cpp
     allocation.bench.cpp
     deque.bench.cpp
     filesystem.bench.cpp
     function.bench.cpp

libcxx/benchmarks/algorithms/ranges_stable_sort.bench.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
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+
+#include "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct StableSort {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](auto& Copy) { std::ranges::stable_sort(Copy); });
+  }
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_RangesStableSort" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  }
+};
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+  makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/docs/Status/RangesAlgorithms.csv

 Permutation,remove_if,Not assigned,n/a,Not started
 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,unique,Not assigned,n/a,Not started
 Permutation,partition,Not assigned,n/a,Not started
 Permutation,stable_partition,Not assigned,n/a,Not started
 Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅
-Permutation,stable_sort,Konstantin Varlamov,n/a,In progress
+Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅
 Permutation,partial_sort,Konstantin Varlamov,n/a,In progress
 Permutation,nth_element,Not assigned,n/a,Not started
 Permutation,inplace_merge,Not assigned,n/a,Not started
 Permutation,make_heap,Not assigned,n/a,Not started
 Permutation,push_heap,Not assigned,n/a,Not started
 Permutation,pop_heap,Not assigned,n/a,Not started
 Permutation,sort_heap,Not assigned,n/a,Not started
 Permutation,prev_permutation,Not assigned,n/a,Not started

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_move.h
   __algorithm/ranges_move_backward.h
   __algorithm/ranges_none_of.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_sort.h
+  __algorithm/ranges_stable_sort.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h
   __algorithm/replace.h

libcxx/include/__algorithm/ranges_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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H
 #define _LIBCPP___ALGORITHM_RANGES_SORT_H
 
 #include <__algorithm/make_projected.h>
 #include <__algorithm/sort.h>
-#include <__concepts/same_as.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/projected.h>

 namespace __sort {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = __make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
     std::__sort_impl(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr

libcxx/include/__algorithm/ranges_stable_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
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H
-#define _LIBCPP___ALGORITHM_RANGES_SORT_H
+#ifndef _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H
+#define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H
 
 #include <__algorithm/make_projected.h>
-#include <__algorithm/sort.h>
-#include <__concepts/same_as.h>
+#include <__algorithm/stable_sort.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/projected.h>
 #include <__iterator/sortable.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
 #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 __sort {
+namespace __stable_sort {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
-  _LIBCPP_HIDE_FROM_ABI constexpr static
-  _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
+  _LIBCPP_HIDE_FROM_ABI
+  static _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = __make_projected_comp(__comp, __proj);
-    std::__sort_impl(std::move(__first), __last_iter, __projected_comp);
+    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
-  _LIBCPP_HIDE_FROM_ABI constexpr
+  _LIBCPP_HIDE_FROM_ABI
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
-    return __sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+    return __stable_sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
   }
 
   template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<iterator_t<_Range>, _Comp, _Proj>
-  _LIBCPP_HIDE_FROM_ABI constexpr
+  _LIBCPP_HIDE_FROM_ABI
   borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
-    return __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+    return __stable_sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
   }
 };
 
-} // namespace __sort
+} // namespace __stable_sort
 
 inline namespace __cpo {
-  inline constexpr auto sort = __sort::__fn{};
+  inline constexpr auto stable_sort = __stable_sort::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
-#endif // _LIBCPP___ALGORITHM_RANGES_SORT_H
+#endif // _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H

libcxx/include/__algorithm/stable_sort.h

 #define _LIBCPP___ALGORITHM_STABLE_SORT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/inplace_merge.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 #include <__utility/swap.h>
 #include <memory>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
//                                  __first, __comp);
         return;
     }
     _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
     _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
     _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    difference_type __len = __last - __first;
-    pair<value_type*, ptrdiff_t> __buf(0, 0);
-    unique_ptr<value_type, __return_temporary_buffer> __h;
-    if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
-    {
+inline _LIBCPP_HIDE_FROM_ABI
+void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+  using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+  using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+
+  if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {
 // TODO: Remove the use of std::get_temporary_buffer
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
-        __buf = _VSTD::get_temporary_buffer<value_type>(__len);
+      __buf = std::get_temporary_buffer<value_type>(__len);
 _LIBCPP_SUPPRESS_DEPRECATED_POP
-        __h.reset(__buf.first);
-    }
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
+
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
+}
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_HIDE_FROM_ABI
+void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  std::__stable_sort_impl(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-    _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI
+void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
+  std::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H

libcxx/include/algorithm

template<input_range R, class Proj = identity,
   template<input_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_unary_predicate<projected<I, Proj>> Pred>
     constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});      // since C++20
 
   template<input_range R, class Proj = identity,
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});                // since C++20
 
-
   template<bidirectional_iterator I, sentinel_for<I> S>
     requires permutable<I>
     constexpr I ranges::reverse(I first, S last);                                           // since C++20
 
   template<bidirectional_range R>
     requires permutable<iterator_t<R>>
     constexpr borrowed_iterator_t<R> ranges::reverse(R&& r);                                // since C++20
 
   template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
             class Proj = identity>
     requires sortable<I, Comp, Proj>
     constexpr I
-      sort(I first, S last, Comp comp = {}, Proj proj = {});                                // since C++20
+      ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});                        // since C++20
 
   template<random_access_range R, class Comp = ranges::less, class Proj = identity>
     requires sortable<iterator_t<R>, Comp, Proj>
     constexpr borrowed_iterator_t<R>
-      sort(R&& r, Comp comp = {}, Proj proj = {});                                          // since C++20
+      ranges::sort(R&& r, Comp comp = {}, Proj proj = {});                                  // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});                 // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    borrowed_iterator_t<R>
+      ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});                           // since C++20
 
   template<class T, output_iterator<const T&> O, sentinel_for<O> S>
     constexpr O ranges::fill(O first, S last, const T& value);                              // since C++20
 
   template<class T, output_range<const T&> R>
     constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);                   // since C++20
 
   template<class T, output_iterator<const T&> O>

 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_sort.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>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/replace.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_mismatch                 { private header "__algorithm/ranges_mismatch.h" }
       module ranges_move                     { private header "__algorithm/ranges_move.h" }
       module ranges_move_backward            { private header "__algorithm/ranges_move_backward.h" }
       module ranges_none_of                  { private header "__algorithm/ranges_none_of.h" }
       module ranges_replace                  { private header "__algorithm/ranges_replace.h" }
       module ranges_replace_if               { private header "__algorithm/ranges_replace_if.h" }
       module ranges_reverse                  { private header "__algorithm/ranges_reverse.h" }
       module ranges_sort                     { private header "__algorithm/ranges_sort.h" }
+      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 ranges_upper_bound              { private header "__algorithm/ranges_upper_bound.h" }
       module remove                          { private header "__algorithm/remove.h" }
       module remove_copy                     { private header "__algorithm/remove_copy.h" }
       module remove_copy_if                  { private header "__algorithm/remove_copy_if.h" }
       module remove_if                       { private header "__algorithm/remove_if.h" }
       module replace                         { private header "__algorithm/replace.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0);
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); }
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); }
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); }
 #if TEST_STD_VER > 20
     //(void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::transform(first, last, first2, UnaryTransform(&copies)); assert(copies == 0);
     (void)std::ranges::transform(a, first2, UnaryTransform(&copies)); assert(copies == 0);
     (void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(&copies)); assert(copies == 0);
     (void)std::ranges::transform(a, b, first2, BinaryTransform(&copies)); assert(copies == 0);
     //(void)std::ranges::unique(first, last, Equal(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); }
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); }
 #if TEST_STD_VER > 20
     //(void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::transform(first, last, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::transform(a, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::transform(a, b, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::unique(first, last, Equal(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
 #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
+#include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}
 #include <__algorithm/remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_if.h'}}
 #include <__algorithm/replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.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 Comp = ranges::less,
+//         class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});                 // since C++20
+//
+// template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   borrowed_iterator_t<R>
+//     ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});                           // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+// SFINAE tests.
+
+using BadComparator = ComparatorNotCopyable<int*>;
+static_assert(!std::sortable<int*, BadComparator>);
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less>
+concept HasStableSortIt = requires(Iter first, Sent last, Comp comp) { std::ranges::stable_sort(first, last, comp); };
+
+static_assert(HasStableSortIt<int*>);
+static_assert(!HasStableSortIt<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasStableSortIt<RandomAccessIteratorBadIndex>);
+static_assert(!HasStableSortIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasStableSortIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasStableSortIt<int*, int*, BadComparator>);
+static_assert(!HasStableSortIt<const int*>); // Doesn't satisfy `sortable`.
+
+template <class Range, class Comp = std::ranges::less>
+concept HasStableSortR = requires(Range range, Comp comp) { std::ranges::stable_sort(range, comp); };
+
+static_assert(HasStableSortR<UncheckedRange<int*>>);
+static_assert(!HasStableSortR<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasStableSortR<RandomAccessRangeBadIndex>);
+static_assert(!HasStableSortR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasStableSortR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);
+static_assert(!HasStableSortR<UncheckedRange<int*>, BadComparator>);
+static_assert(!HasStableSortR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.
+
+template <class Iter, class Sent, size_t N>
+void test_one(std::array<int, N> input, std::array<int, N> expected) {
+  { // (iterator, sentinel) overload.
+    auto sorted = input;
+    auto b = Iter(sorted.data());
+    auto e = Sent(Iter(sorted.data() + sorted.size()));
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::stable_sort(b, e);
+    assert(sorted == expected);
+    assert(base(last) == sorted.data() + sorted.size());
+  }
+
+  { // (range) overload.
+    auto sorted = input;
+    auto b = Iter(sorted.data());
+    auto e = Sent(Iter(sorted.data() + sorted.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::stable_sort(range);
+    assert(sorted == expected);
+    assert(base(last) == sorted.data() + sorted.size());
+  }
+}
+
+template <class Iter, class Sent>
+void test_iterators_2() {
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, {});
+  // 1-element sequence.
+  test_one<Iter, Sent, 1>({1}, {1});
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({2, 1}, {1, 2});
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({2, 1, 3}, {1, 2, 3});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, {1, 2, 3, 4, 5, 6, 8, 11});
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 7>({2, 1, 3, 6, 2, 8, 6}, {1, 2, 2, 3, 6, 6, 8});
+  // All elements are the same.
+  test_one<Iter, Sent, 3>({1, 1, 1}, {1, 1, 1});
+  // Already sorted.
+  test_one<Iter, Sent, 5>({1, 2, 3, 4, 5}, {1, 2, 3, 4, 5});
+  // Reverse-sorted.
+  test_one<Iter, Sent, 5>({5, 4, 3, 2, 1}, {1, 2, 3, 4, 5});
+  // Repeating pattern.
+  test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, {1, 1, 1, 2, 2, 2});
+}
+
+template <class Iter>
+void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+void test_iterators() {
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
+
+void test() {
+  test_iterators();
+
+  struct OrderedValue {
+    int value;
+    double original_order;
+    bool operator==(const OrderedValue&) const = default;
+    auto operator<=>(const OrderedValue& rhs) const { return value <=> rhs.value; }
+  };
+
+  { // The sort is stable (equivalent elements remain in the same order).
+    using V = OrderedValue;
+    using Array = std::array<V, 20>;
+    Array orig_in = {
+      V{10, 10.1}, {12, 12.1}, {3, 3.1}, {5, 5.1}, {3, 3.2}, {3, 3.3}, {11, 11.1}, {12, 12.2}, {4, 4.1}, {4, 4.2},
+      {4, 4.3}, {1, 1.1}, {6, 6.1}, {3, 3.4}, {10, 10.2}, {8, 8.1}, {12, 12.3}, {1, 1.2}, {1, 1.3}, {5, 5.2}
+    };
+    Array expected = {
+      V{1, 1.1}, {1, 1.2}, {1, 1.3},
+      {3, 3.1}, {3, 3.2}, {3, 3.3}, {3, 3.4},
+      {4, 4.1}, {4, 4.2}, {4, 4.3},
+      {5, 5.1}, {5, 5.2},
+      {6, 6.1},
+      {8, 8.1},
+      {10, 10.1}, {10, 10.2},
+      {11, 11.1},
+      {12, 12.1}, {12, 12.2}, {12, 12.3}
+    };
+
+    {
+      auto in = orig_in;
+      auto last = std::ranges::stable_sort(in.begin(), in.end());
+      assert(in == expected);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = orig_in;
+      auto last = std::ranges::stable_sort(in);
+      assert(in == expected);
+      assert(last == in.end());
+    }
+  }
+
+  { // A custom comparator works and is stable.
+    using V = OrderedValue;
+    using Array = std::array<V, 11>;
+
+    Array orig_in = {
+      V{1, 1.1}, {2, 2.1}, {2, 2.2}, {3, 3.1}, {2, 2.3}, {3, 3.2}, {4, 4.1}, {5, 5.1}, {2, 2.4}, {5, 5.2}, {1, 1.2}
+    };
+    Array expected = {
+      V{5, 5.1}, {5, 5.2},
+      {4, 4.1},
+      {3, 3.1}, {3, 3.2},
+      {2, 2.1}, {2, 2.2}, {2, 2.3}, {2, 2.4},
+      {1, 1.1}, {1, 1.2}
+    };
+
+    {
+      auto in = orig_in;
+      auto last = std::ranges::stable_sort(in.begin(), in.end(), std::greater{});
+      assert(in == expected);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = orig_in;
+      auto last = std::ranges::stable_sort(in, std::greater{});
+      assert(in == expected);
+      assert(last == in.end());
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+      bool operator==(const A&) const = default;
+    };
+
+    {
+      std::array in = {A{2}, A{3}, A{1}};
+      auto last = std::ranges::stable_sort(in.begin(), in.end(), {}, &A::a);
+      assert((in == std::array{A{1}, A{2}, A{3}}));
+      assert(last == in.end());
+    }
+
+    {
+      std::array in = {A{2}, A{3}, A{1}};
+      auto last = std::ranges::stable_sort(in, {}, &A::a);
+      assert((in == std::array{A{1}, A{2}, A{3}}));
+      assert(last == in.end());
+    }
+  }
+
+  { // `std::invoke` is used in the implementation.
+    struct S {
+      int i;
+      S(int i_) : i(i_) {}
+
+      bool comparator(const S& rhs) const { return i < rhs.i; }
+      const S& projection() const { return *this; }
+
+      bool operator==(const S&) const = default;
+    };
+
+    {
+      std::array in = {S{2}, S{3}, S{1}};
+      auto last = std::ranges::stable_sort(in.begin(), in.end(), &S::comparator, &S::projection);
+      assert((in == std::array{S{1}, S{2}, S{3}}));
+      assert(last == in.end());
+    }
+
+    {
+      std::array in = {S{2}, S{3}, S{1}};
+      auto last = std::ranges::stable_sort(in, &S::comparator, &S::projection);
+      assert((in == std::array{S{1}, S{2}, S{3}}));
+      assert(last == in.end());
+    }
+  }
+
+  { // The comparator can return any type that's convertible to `bool`.
+    {
+      std::array in = {2, 1, 3};
+      auto last = std::ranges::stable_sort(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; });
+      assert((in == std::array{1, 2, 3}));
+      assert(last == in.end());
+    }
+
+    {
+      std::array in = {2, 1, 3};
+      auto last = std::ranges::stable_sort(in, [](int i, int j) { return BooleanTestable{i < j}; });
+      assert((in == std::array{1, 2, 3}));
+      assert(last == in.end());
+    }
+  }
+
+  { // `std::ranges::dangling` is returned.
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
+        std::ranges::stable_sort(std::array{1, 2, 3});
+  }
+}
+
+int main(int, char**) {
+  test();
+  // Note: `stable_sort` is not `constexpr`.
+
+  return 0;
+}

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

 //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::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::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));
 //static_assert(test(std::ranges::unique_copy, a, a));
 static_assert(test(std::ranges::upper_bound, a, 42));
 
 // [memory.syn]