[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

This is copied from the sort patch.

[Mordante]

Thanks for working on this! Some small remarks.

libcxx/include/__algorithm/ranges_stable_sort.h

40

Please remove the constexpr

libcxx/include/__algorithm/stable_sort.h

211

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

40

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–43

Why is this not static but instead marked const?

43

Maybe name it __ranges_stable_sort_impl?

46

This probably also applies to ranges::sort.

libcxx/include/__algorithm/stable_sort.h

212

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–43

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.

46

Thanks! Fixed both.

libcxx/include/__algorithm/stable_sort.h

212

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_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,Not assigned,n/a,Not started
 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,n/a,In progress
-Permutation,stable_sort,Konstantin Varlamov,n/a,In progress
+Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,Under review
 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_max_element.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_none_of.h
   __algorithm/ranges_reverse.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_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_STABLE_SORT_H
+#define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_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/projected.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 __stable_sort {
+
+struct __fn {
+  template <class _Iter, class _Sent, class _Comp, class _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) const {
+    auto __projected_comp = [&](auto&& __lhs, auto&& __rhs) {
+      return std::invoke(__comp,
+                         std::invoke(__proj, std::forward<decltype(__lhs)>(__lhs)),
+                         std::invoke(__proj, std::forward<decltype(__rhs)>(__rhs)));
+    };
+
+    auto __last_iter = ranges::next(__first, __last);
+    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
+  _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    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
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __stable_sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __stable_sort
+
+inline namespace __cpo {
+  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_STABLE_SORT_H

libcxx/include/__algorithm/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_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))
-    {
-        __buf = _VSTD::get_temporary_buffer<value_type>(__len);
-        __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);
+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)) {
+  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>
+    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>
     constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);            // since C++20

 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_reverse.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

module __algorithm {
       module ranges_max_element       { private header "__algorithm/ranges_max_element.h" }
       module ranges_min               { private header "__algorithm/ranges_min.h" }
       module ranges_min_element       { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax            { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element    { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch          { private header "__algorithm/ranges_mismatch.h" }
       module ranges_none_of           { private header "__algorithm/ranges_none_of.h" }
       module ranges_reverse           { private header "__algorithm/ranges_reverse.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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
#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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
#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

 //===----------------------------------------------------------------------===//
 //
 // 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/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.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_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.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();
+
+  { // The sort is stable (equivalent elements remain in the same order).
+    struct OrderedValue {
+      int value;
+      int original_order;
+      bool operator==(const OrderedValue&) const = default;
+      bool operator<(const OrderedValue& rhs) const { return value < rhs.value; }
+      bool operator<=(const OrderedValue& rhs) const { return value <= rhs.value; }
+      bool operator>(const OrderedValue& rhs) const { return value > rhs.value; }
+      bool operator>=(const OrderedValue& rhs) const { return value >= rhs.value; }
+    };
+
+    using V = OrderedValue;
+    using Array = std::array<V, 20>;
+    Array orig_in = {
+      V{10, 101}, {12, 121}, {3, 31}, {5, 51}, {3, 32}, {3, 33}, {11, 111}, {12, 122}, {4, 41}, {4, 42}, {4, 43},
+      {1, 11}, {6, 61}, {3, 34}, {10, 102}, {8, 81}, {12, 123}, {1, 12}, {1, 13}, {5, 52}
+    };
+    Array expected = {
+      V{1, 11}, {1, 12}, {1, 13},
+      {3, 31}, {3, 32}, {3, 33}, {3, 34},
+      {4, 41}, {4, 42}, {4, 43},
+      {5, 51}, {5, 52},
+      {6, 61},
+      {8, 81},
+      {10, 101}, {10, 102},
+      {11, 111},
+      {12, 121}, {12, 122}, {12, 123},
+    };
+
+    {
+      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.
+    {
+      std::array in = {1, 2, 3, 4, 5};
+      auto last = std::ranges::stable_sort(in.begin(), in.end(), std::greater{});
+      assert((in == std::array{5, 4, 3, 2, 1}));
+      assert(last == in.end());
+    }
+
+    {
+      std::array in = {1, 2, 3, 4, 5};
+      auto last = std::ranges::stable_sort(in, std::greater{});
+      assert((in == std::array{5, 4, 3, 2, 1}));
+      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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 //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]

libcxx/test/support/almost_satisfies_types.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
 //
 //===----------------------------------------------------------------------===//
 

 
 using OutputRangeNotIndirectlyWritable = UncheckedRange<OutputIteratorNotIndirectlyWritable>;
 
 static_assert(std::input_or_output_iterator<OutputIteratorNotIndirectlyWritable>);
 static_assert(!std::indirectly_writable<OutputIteratorNotIndirectlyWritable, int>);
 static_assert(!std::output_iterator<OutputIteratorNotIndirectlyWritable, int>);
 static_assert(!std::ranges::output_range<OutputIteratorNotIndirectlyWritable, int>);
 
+class RandomAccessIteratorNotDerivedFrom {
+  using Self = RandomAccessIteratorNotDerivedFrom;
+
+public:
+  using value_type = int;
+  using difference_type = long;
+  using pointer = int*;
+  using reference = int&;
+  // Deliberately not using the `std::random_access_iterator_tag` category.
+  using iterator_category = std::bidirectional_iterator_tag;
+
+  reference operator*() const;
+  reference operator[](difference_type) const;
+
+  Self& operator++();
+  Self& operator--();
+  Self operator++(int);
+  Self operator--(int);
+
+  Self& operator+=(difference_type);
+  Self& operator-=(difference_type);
+  friend Self operator+(Self, difference_type);
+  friend Self operator+(difference_type, Self);
+  friend Self operator-(Self, difference_type);
+  friend difference_type operator-(Self, Self);
+
+  friend bool operator==(const Self&, const Self&);
+  friend bool operator!=(const Self&, const Self&);
+  friend bool operator< (const Self&, const Self&);
+  friend bool operator<=(const Self&, const Self&);
+  friend bool operator> (const Self&, const Self&);
+  friend bool operator>=(const Self&, const Self&);
+};
+
+static_assert(std::bidirectional_iterator<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!std::random_access_iterator<RandomAccessIteratorNotDerivedFrom>);
+
+using RandomAccessRangeNotDerivedFrom = UncheckedRange<RandomAccessIteratorNotDerivedFrom>;
+
+class RandomAccessIteratorBadIndex {
+  using Self = RandomAccessIteratorBadIndex;
+
+public:
+  using value_type = int;
+  using difference_type = long;
+  using pointer = int*;
+  using reference = int&;
+  using iterator_category = std::random_access_iterator_tag;
+
+  reference operator*() const;
+  // Deliberately returning a type different from `reference`.
+  const int& operator[](difference_type) const;
+
+  Self& operator++();
+  Self& operator--();
+  Self operator++(int);
+  Self operator--(int);
+
+  Self& operator+=(difference_type);
+  Self& operator-=(difference_type);
+  friend Self operator+(Self, difference_type);
+  friend Self operator+(difference_type, Self);
+  friend Self operator-(Self, difference_type);
+  friend difference_type operator-(Self, Self);
+
+  auto operator<=>(const Self&) const = default;
+};
+
+static_assert(std::bidirectional_iterator<RandomAccessIteratorBadIndex>);
+static_assert(!std::random_access_iterator<RandomAccessIteratorBadIndex>);
+
+using RandomAccessRangeBadIndex = UncheckedRange<RandomAccessIteratorBadIndex>;
+
+template <class Iter>
+class ComparatorNotCopyable {
+public:
+  ComparatorNotCopyable(ComparatorNotCopyable&&) = default;
+  ComparatorNotCopyable& operator=(ComparatorNotCopyable&&) = default;
+  ComparatorNotCopyable(const ComparatorNotCopyable&) = delete;
+  ComparatorNotCopyable& operator=(const ComparatorNotCopyable&) = delete;
+
+  bool operator()(Iter&, Iter&) const;
+};
+
 #endif // ALMOST_SATISFIES_TYPES_H