[libc++][ranges] Implement `ranges::{prev, next}_permutation`

[huixie90]

libcxx/include/CMakeLists.txt

114

could you please update the RangeAlgorithms.csv file?

libcxx/include/__algorithm/ranges_prev_permutation.h

41–63

I think this algorithm is complex enough to reuse the classic one. what do you think?

56

std::move(__last)

60

std::move(__last)

libcxx/test/support/test_iterators.h

758

take the arguments by const ref, as indirectly_swappable requires const

760

why does the rhs counter not incremented?

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_prev_permutation.h

41–63

I think it's harder to combine the two than to use separate ones. The algorithms isn't that long, and I would have to teach reverse to dispatch between versions. If that changes we can still think about combining the two.

libcxx/test/support/test_iterators.h

758

Weird that this didn't show in the test. Maybe I just missed it.

760

Because that would increment the counter two times per swap.

[var-const]

libcxx/include/CMakeLists.txt

123

Looks like this line is unsorted (might be what the CI is complaining about).

libcxx/include/__algorithm/ranges_prev_permutation.h

41–63

I'd also prefer reuse, but don't want to block this patch on this.

45

Nit: can you add a blank line before this line?

48

Nit: blank line above.

53

Nit: blank line above.

57

Nit: blank line above.

71

Nit: move?

libcxx/include/algorithm

736

Please also add the definition of the result types to the synopsis.

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp

46

Does the argument have to be forwarded, perhaps? (here and in the other concept above)

64

There's a bunch of references to prev_permutation here. I presume this is simply a copy-pasting issue? (if there's a reason to test them here, please point it out)

121

Question: why is static_assert here instead of the common pattern of asserting test() in main()?

141

return 0; (unless something changed recently in that regard)

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp

91

Is the output of prev_permutation deterministic? If yes, I'd prefer several simple test cases that check the exact output.

libcxx/test/support/test_iterators.h

755

Nit: this creates an object with uninitialized variables (counter_ and potentially iter_), maybe value-initialize those?

758

Would it be possible to just inherit from Iter and add the constructor and the iter_swap specialization in the derived class?

763

(I wish we had something like Boost.Iterator to cut down on this boilerplate. Of course, it's not related to this patch)

[philnik]

• Address comments

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp

46

I don't think so, since {prev, next}_permutation only supports copyable iterators/ranges.

121

The static_asserts are here because putting them anywhere else would hit the constant evaluation step limit.

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp

91

Yes, the output is deterministic. This test checks the exact output of prev_permutation. It checks after every call to ranges::prev_permutation that it's lexicographically less than the input. It's also checked that there were N! rounds. Since there are N! permutations of a range, every input to prev_permutation has to have resulted in the permutation before the input.

libcxx/test/support/test_iterators.h

755

These are uninitialized on purpose. Algorithms aren't allowed to read from a default-constructed allocator and the tests always have to provide one. If these are uninitialized for any reason the constexpr tests will fail. That wouldn't be the case if I value-initialized them.

758

Inheriting wouldn't work with raw pointers. (inheriting was actually my initial design)

[ldionne]

libcxx/include/__algorithm/ranges_prev_permutation.h

41–63

I think we should reuse. Teaching reverse about _AlgPolicy should be trivial.

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp

91

I think this is a clever way to test this. Maybe a little bit too clever to be the only test we have. I'd be OK with this approach if it were also augmented with a small number (e.g. 10 with boundary conditions) of explicit input/output comparisons. Does that sound reasonable?

Also, a comment explaining what the testing methodology here would be really helpful.

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp

91

I refactored this function into several and added comments. However, it adds a lot of complexity and takes a while to run (I had to increase the number of constexpr steps and reduce the length of the input array since the growth factor is factorial).

[var-const]

• Make ranges::{next,prev}_permutation delegate to the classic algorithm;
• modify the classic {next,prev}_permutation and their dependencies to support _AlgPolicy;
• refactor and comment the test functions that run all possible permutations of a given sequence;
• increase the constexpr evaluation step limit for the new tests and move the static_assert back to main like in most other tests;
• add test cases with expected output;
• add tests for a custom predicate and a custom projection;
• remove the SwapCountingIterator and replace its usages with the existing adl::Iterator::TrackSwaps.

[var-const]

Reduce the input size used for the exhaustive permutation checks to avoid
hitting constexpr step limit in Clang; remove the Clang command-line option
because it's unrecognized by GCC.

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[ldionne]

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp

88

Applies in a few places.

[h-vetinari]

There are still a few tests for these commented out, e.g. in:
libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

[var-const]

In D129859#3698830, @h-vetinari wrote:

There are still a few tests for these commented out, e.g. in:
libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

Thanks! I plan to uncomment any remaining ones in a dedicated patch once all the remaining algorithms land.

[var-const]

In D129859#3698987, @var-const wrote:

In D129859#3698830, @h-vetinari wrote:

There are still a few tests for these commented out, e.g. in:
libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

Thanks! I plan to uncomment any remaining ones in a dedicated patch once all the remaining algorithms land.

Follow-up: https://reviews.llvm.org/D131235

libcxx/docs/Status/RangesAlgorithms.csv

 Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅
 Permutation,partial_sort,Konstantin Varlamov,n/a,In progress
 Permutation,nth_element,Konstantin Varlamov,`D128149 <https://llvm.org/D128149>`_,✅
 Permutation,inplace_merge,Not assigned,n/a,Not started
 Permutation,make_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,push_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,pop_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,sort_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
-Permutation,prev_permutation,Not assigned,n/a,Not started
-Permutation,next_permutation,Not assigned,n/a,Not started
+Permutation,Nikolas Klauser,`D129859 <https://llvm.org/D129859>`_,✅
+Permutation,Nikolas Klauser,`D129859 <https://llvm.org/D129859>`_,✅
 Uninitialised memory,uninitialized_copy,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_copy_n,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_fill,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,uninitialized_fill_n,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,uninitialized_move,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_move_n,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_default_construct,Konstantin Varlamov,`D115315 <https://llvm.org/D115315>`_,✅
 Uninitialised memory,uninitialized_default_construct_n,Konstantin Varlamov,`D115315 <https://llvm.org/D115315>`_,✅
 Uninitialised memory,uninitialized_value_construct,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,uninitialized_value_construct_n,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,destroy,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅
 Uninitialised memory,destroy_n,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅
 Uninitialised memory,destroy_at,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅
 Uninitialised memory,construct_at,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_merge.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_move.h
   __algorithm/ranges_move_backward.h
+  __algorithm/ranges_next_permutation.h
   __algorithm/ranges_none_of.h
   __algorithm/ranges_nth_element.h
   __algorithm/ranges_partial_sort_copy.h
   __algorithm/ranges_partition.h
   __algorithm/ranges_partition_copy.h
   __algorithm/ranges_partition_point.h
   __algorithm/ranges_pop_heap.h
   __algorithm/ranges_push_heap.h
+  __algorithm/ranges_prev_permutation.h
   __algorithm/ranges_remove.h
   __algorithm/ranges_remove_copy.h
   __algorithm/ranges_remove_copy_if.h
   __algorithm/ranges_remove_if.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_copy.h
   __algorithm/ranges_replace_copy_if.h
   __algorithm/ranges_replace_if.h

libcxx/include/__algorithm/ranges_next_permutation.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_NEXT_PERMUTATION_H
+#define _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H
+
+#include <__algorithm/in_found_result.h>
+#include <__algorithm/ranges_prev_permutation.h>
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+namespace ranges {
+
+template <class _InIter>
+using next_permutation_result = in_found_result<_InIter>;
+
+namespace __next_permutation {
+
+struct __fn {
+  template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<_Iter, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr next_permutation_result<_Iter>
+  operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __comp_reverse_args = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+    return ranges::__prev_permutation_impl(__first, __last, __comp_reverse_args, __proj);
+  }
+
+  template <bidirectional_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr next_permutation_result<borrowed_iterator_t<_Range>>
+  operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __comp_reverse_args = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+    return ranges::__prev_permutation_impl(ranges::begin(__range), ranges::end(__range), __comp_reverse_args, __proj);
+  }
+};
+
+} // namespace __next_permutation
+
+inline namespace __cpo {
+constexpr inline auto next_permutation = __next_permutation::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H

libcxx/include/__algorithm/ranges_prev_permutation.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_PREV_PERMUTATION_H
+#define _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H
+
+#include <__algorithm/in_found_result.h>
+#include <__algorithm/ranges_reverse.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iter_swap.h>
+#include <__iterator/next.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+namespace ranges {
+
+template <class _InIter>
+using prev_permutation_result = in_found_result<_InIter>;
+
+template <class _Iter, class _Sent, class _Comp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<_Iter>
+__prev_permutation_impl(_Iter __first, _Sent __sent, _Comp& __comp, _Proj& __proj) {
+  auto __last = ranges::next(__first, __sent);
+  auto __i = __last;
+  if (__first == __last || __first == --__i)
+    return {std::move(__last), false};
+  while (true) {
+    auto __ip1 = __i;
+    --__i;
+    if (std::invoke(__comp, std::invoke(__proj, *__ip1), std::invoke(__proj, *__i))) {
+      auto __j = __last;
+      do {
+        --__j;
+      } while (!std::invoke(__comp, std::invoke(__proj, *__j), std::invoke(__proj, *__i)));
+      ranges::iter_swap(__i, __j);
+      ranges::reverse(__ip1, __last);
+      return {std::move(__last), true};
+    }
+    if (__i == __first) {
+      ranges::reverse(__first, __last);
+      return {std::move(__last), false};
+    }
+  }
+}
+
+namespace __prev_permutation {
+
+struct __fn {
+  template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<_Iter, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<_Iter>
+  operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return ranges::__prev_permutation_impl(__first, __last, __comp, __proj);
+  }
+
+  template <bidirectional_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
+  operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const {
+    return ranges::__prev_permutation_impl(ranges::begin(__range), ranges::end(__range), __comp, __proj);
+  }
+};
+} // namespace __prev_permutation
+
+inline namespace __cpo {
+constexpr inline auto prev_permutation = __prev_permutation::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_symmetric_difference_result<I1, I2, O>
       set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                                Comp comp = {}, Proj1 proj1 = {},
                                Proj2 proj2 = {});                                                   // since C++20
-  
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_symmetric_difference_result<borrowed_iterator_t<R1>,
                                                       borrowed_iterator_t<R2>, O>
       set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
                                Proj1 proj1 = {}, Proj2 proj2 = {});                                 // since C++20
-  
   template<class I1, class I2, class O>
     using set_union_result = in_in_out_result<I1, I2, O>;                                           // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_union_result<I1, I2, O>
       set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
 
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+           class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr ranges::prev_permutation_result<I>
+      ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});                    // since C++20
+
+  template<bidirectional_range R, class Comp = ranges::less,
+           class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr ranges::prev_permutation_result<borrowed_iterator_t<R>>
+      ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {});                              // since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+           class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr ranges::next_permutation_result<I>
+      ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {});                    // since C++20
+
+  template<bidirectional_range R, class Comp = ranges::less,
+           class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr ranges::next_permutation_result<borrowed_iterator_t<R>>
+      ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {});                              // since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_merge.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_move.h>
 #include <__algorithm/ranges_move_backward.h>
+#include <__algorithm/ranges_next_permutation.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_nth_element.h>
 #include <__algorithm/ranges_pop_heap.h>
+#include <__algorithm/ranges_prev_permutation.h>
 #include <__algorithm/ranges_push_heap.h>
 #include <__algorithm/ranges_remove.h>
 #include <__algorithm/ranges_remove_if.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_reverse_copy.h>
 #include <__algorithm/ranges_rotate_copy.h>

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

#endif
     (void)std::ranges::min_element(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax({ value, value }, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax_element(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax_element(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(a, b, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::next_permutation(first, last, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::next_permutation(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::remove_if(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0);

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

#endif
     (void)std::ranges::min_element(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(T(), T(), Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax_element(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax_element(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::next_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::next_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(a, first2, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::remove(first, last, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::remove(a, value, Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_merge.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_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_next_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_next_permutation.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_nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_nth_element.h'}}
 #include <__algorithm/ranges_partial_sort_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partial_sort_copy.h'}}
 #include <__algorithm/ranges_partition.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition.h'}}
 #include <__algorithm/ranges_partition_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_copy.h'}}
 #include <__algorithm/ranges_partition_point.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_point.h'}}
 #include <__algorithm/ranges_pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_pop_heap.h'}}
+#include <__algorithm/ranges_prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_prev_permutation.h'}}
 #include <__algorithm/ranges_push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_push_heap.h'}}
 #include <__algorithm/ranges_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.h'}}
 #include <__algorithm/ranges_remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_copy.h'}}
 #include <__algorithm/ranges_remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_copy_if.h'}}
 #include <__algorithm/ranges_remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_if.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_copy.h'}}
 #include <__algorithm/ranges_replace_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_copy_if.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+//          class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   constexpr ranges::next_permutation_result<I>
+//     ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
+// template<bidirectional_range R, class Comp = ranges::less,
+//          class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   constexpr ranges::next_permutation_result<borrowed_iterator_t<R>>
+//     ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasNextPermutationIt = requires(Iter first, Sent last) { std::ranges::next_permutation(first, last); };
+
+static_assert(HasNextPermutationIt<int*>);
+static_assert(!HasNextPermutationIt<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasNextPermutationIt<BidirectionalIteratorNotDecrementable>);
+static_assert(!HasNextPermutationIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasNextPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasNextPermutationIt<const int*>); // not sortable
+
+template <class Range>
+concept HasNextPermutationR = requires(Range range) { std::ranges::next_permutation(range); };
+
+static_assert(HasNextPermutationR<UncheckedRange<int*>>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotDerivedFrom>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotDecrementable>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotSentinelSemiregular>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotSentinelWeaklyEqualityComparableWith>);
+static_assert(!HasNextPermutationR<UncheckedRange<const int*>>); // not sortable
+
+constexpr size_t factorial(size_t i) {
+  size_t result = 1;
+  for (; i != 0; --i)
+    result *= i;
+  return result;
+}
+
+template <class Iter, class Sent>
+void test_permutations() {
+  auto test_prev_permutations = [](auto call_prev_permutation) {
+    auto input = std::array{1, 2, 3, 4, 5, 6};
+    std::array<int, input.size()> last_permutation;
+    for (size_t i = 0; i <= input.size(); ++i) {
+      size_t count = 0;
+
+      bool found_permutation = true;
+      while (found_permutation) {
+        last_permutation = input;
+        std::same_as<std::ranges::prev_permutation_result<Iter>> decltype(auto) ret =
+            call_prev_permutation(Iter(input.data()), Sent(Iter(input.data() + i)));
+        found_permutation = ret.found;
+        assert(base(ret.in) == input.data() + i);
+        if (i > 1) {
+          auto input_subrange            = input | std::views::take(i);
+          auto last_permutation_subrange = last_permutation | std::views::take(i);
+          if (found_permutation)
+            assert(std::ranges::lexicographical_compare(last_permutation_subrange, input_subrange));
+          else
+            assert(std::ranges::lexicographical_compare(input_subrange, last_permutation_subrange));
+        }
+        ++count;
+      }
+      assert(count == factorial(i));
+    }
+    return true;
+  };
+
+  auto iterator_overload = [](auto&& first, auto&& last) { return std::ranges::next_permutation(first, last); };
+  auto range_overload    = [](auto&& first, auto&& last) {
+    auto range = std::ranges::subrange(first, last);
+    return std::ranges::next_permutation(range);
+  };
+
+  if constexpr (std::is_same_v<Iter, Sent>) {
+    auto iterator_overload_counted =
+        [](auto first, auto last) -> std::ranges::prev_permutation_result<decltype(first)> {
+      int count = 0;
+      auto ret = std::ranges::next_permutation(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+      assert(count <= (base(last) - base(first) + 1) / 2);
+      return ret;
+    };
+
+    auto range_overload_counted = [](auto first, auto last) -> std::ranges::prev_permutation_result<decltype(first)> {
+      int count  = 0;
+      auto range = std::ranges::subrange(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+      auto ret   = std::ranges::next_permutation(range);
+      assert(count <= (base(last) - base(first) + 1) / 2);
+      return ret;
+    };
+
+    test_prev_permutations(iterator_overload_counted);
+    static_assert(test_prev_permutations(iterator_overload_counted));
+    test_prev_permutations(range_overload_counted);
+    static_assert(test_prev_permutations(range_overload_counted));
+  }
+
+  test_prev_permutations(iterator_overload);
+  static_assert(test_prev_permutations(iterator_overload));
+  test_prev_permutations(range_overload);
+  static_assert(test_prev_permutations(range_overload));
+}
+
+template <class Iter>
+void test_sentinels() {
+  test_permutations<Iter, Iter>();
+  test_permutations<Iter, sentinel_wrapper<Iter>>();
+  test_permutations<Iter, sized_sentinel<Iter>>();
+}
+
+void test() {
+  test_sentinels<bidirectional_iterator<int*>>();
+  test_sentinels<random_access_iterator<int*>>();
+  test_sentinels<contiguous_iterator<int*>>();
+  test_sentinels<int*>();
+}
+
+int main(int, char**) { test(); }

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+//          class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   constexpr ranges::prev_permutation_result<I>
+//     ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
+// template<bidirectional_range R, class Comp = ranges::less,
+//          class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   constexpr ranges::prev_permutation_result<borrowed_iterator_t<R>>
+//     ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasPrevPermutationIt = requires(Iter first, Sent last) { std::ranges::prev_permutation(first, last); };
+
+static_assert(HasPrevPermutationIt<int*>);
+static_assert(!HasPrevPermutationIt<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasPrevPermutationIt<BidirectionalIteratorNotDecrementable>);
+static_assert(!HasPrevPermutationIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasPrevPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasPrevPermutationIt<const int*>); // not sortable
+
+template <class Range>
+concept HasPrevPermutationR = requires(Range range) { std::ranges::prev_permutation(range); };
+
+static_assert(HasPrevPermutationR<UncheckedRange<int*>>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotDerivedFrom>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotDecrementable>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotSentinelSemiregular>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotSentinelWeaklyEqualityComparableWith>);
+static_assert(!HasPrevPermutationR<UncheckedRange<const int*>>); // not sortable
+
+constexpr size_t factorial(size_t i) {
+  size_t result = 1;
+  for (; i != 0; --i)
+    result *= i;
+  return result;
+}
+
+template <class Iter, class Sent>
+void test_permutations() {
+  auto test_prev_permutations = [](auto call_prev_permutation) {
+    auto input = std::array{6, 5, 4, 3, 2, 1};
+    std::array<int, input.size()> last_permutation;
+    for (size_t i = 0; i <= input.size(); ++i) {
+      size_t count = 0;
+
+      bool found_permutation = true;
+      while (found_permutation) {
+        last_permutation = input;
+        std::same_as<std::ranges::prev_permutation_result<Iter>> decltype(auto) ret =
+            call_prev_permutation(Iter(input.data()), Sent(Iter(input.data() + i)));
+        found_permutation = ret.found;
+        assert(base(ret.in) == input.data() + i);
+        if (i > 1) {
+          auto input_subrange            = input | std::views::take(i);
+          auto last_permutation_subrange = last_permutation | std::views::take(i);
+          if (found_permutation)
+            assert(std::ranges::lexicographical_compare(input_subrange, last_permutation_subrange));
+          else
+            assert(std::ranges::lexicographical_compare(last_permutation_subrange, input_subrange));
+        }
+        ++count;
+      }
+      assert(count == factorial(i));
+    }
+    return true;
+  };
+
+  auto iterator_overload = [](auto&& first, auto&& last) { return std::ranges::prev_permutation(first, last); };
+  auto range_overload    = [](auto&& first, auto&& last) {
+    auto range = std::ranges::subrange(first, last);
+    return std::ranges::prev_permutation(range);
+  };
+
+  if constexpr (std::is_same_v<Iter, Sent>) {
+    auto iterator_overload_counted =
+        [](auto first, auto last) -> std::ranges::prev_permutation_result<decltype(first)> {
+      int count = 0;
+      auto ret = std::ranges::prev_permutation(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+      assert(count <= (base(last) - base(first) + 1) / 2);
+      return ret;
+    };
+
+    auto range_overload_counted = [](auto first, auto last) -> std::ranges::prev_permutation_result<decltype(first)> {
+      int count  = 0;
+      auto range = std::ranges::subrange(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+      auto ret   = std::ranges::prev_permutation(range);
+      assert(count <= (base(last) - base(first) + 1) / 2);
+      return ret;
+    };
+
+    test_prev_permutations(iterator_overload_counted);
+    static_assert(test_prev_permutations(iterator_overload_counted));
+    test_prev_permutations(range_overload_counted);
+    static_assert(test_prev_permutations(range_overload_counted));
+  }
+
+  test_prev_permutations(iterator_overload);
+  static_assert(test_prev_permutations(iterator_overload));
+  test_prev_permutations(range_overload);
+  static_assert(test_prev_permutations(range_overload));
+}
+
+template <class Iter>
+void test_sentinels() {
+  test_permutations<Iter, Iter>();
+  test_permutations<Iter, sentinel_wrapper<Iter>>();
+  test_permutations<Iter, sized_sentinel<Iter>>();
+}
+
+void test() {
+  test_sentinels<bidirectional_iterator<int*>>();
+  test_sentinels<random_access_iterator<int*>>();
+  test_sentinels<contiguous_iterator<int*>>();
+  test_sentinels<int*>();
+}
+
+int main(int, char**) { test(); }

libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp

 // static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_union_result<int, long, char>>);
 // static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_intersection_result<int, long, char>>);
 
 // static_assert(std::is_same_v<in_out_out_result<int, long, char>, partition_copy_result<int, long, char>>);
 
 static_assert(std::is_same_v<min_max_result<int>, minmax_result<int>>);
 static_assert(std::is_same_v<min_max_result<int>, minmax_element_result<int>>);
 
-// static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>);
-// static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>);
+static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>);
+static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>);
 
 // static_assert(std::is_same_v<out_value_result<int>, iota_result<int>>);

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp

void test_all() {
   in_pred(std::ranges::stable_sort, in, binary_pred);
   //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
   in_mid_pred(std::ranges::nth_element, in, mid, binary_pred);
   //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
   in_pred(std::ranges::make_heap, in, binary_pred);
   in_pred(std::ranges::push_heap, in, binary_pred);
   in_pred(std::ranges::pop_heap, in, binary_pred);
   in_pred(std::ranges::sort_heap, in, binary_pred);
-  //in_pred(std::ranges::prev_permutation, in, binary_pred);
-  //in_pred(std::ranges::next_permutation, in, binary_pred);
+  in_pred(std::ranges::prev_permutation, in, binary_pred);
+  in_pred(std::ranges::next_permutation, in, binary_pred);
 }

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp

void test_all() {
   in_pred(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val);
   //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
   in_mid_pred(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val);
   //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
   in_pred(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
+  in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
+  in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
 }

libcxx/test/support/almost_satisfies_types.h

public:
   BidirectionalIteratorNotDerivedFrom& operator--();
   BidirectionalIteratorNotDerivedFrom operator--(int);
   int& operator*() const;
 
   bool operator==(const BidirectionalIteratorNotDerivedFrom&) const = default;
 };
 
 using BidirectionalRangeNotDerivedFrom = UncheckedRange<BidirectionalIteratorNotDerivedFrom>;
+using BidirectionalRangeNotSentinelSemiregular =
+    UncheckedRange<bidirectional_iterator<int*>, SentinelForNotSemiregular>;
+using BidirectionalRangeNotSentinelWeaklyEqualityComparableWith =
+    UncheckedRange<bidirectional_iterator<int*>, SentinelForNotWeaklyEqualityComparableWith>;
 
 static_assert(std::forward_iterator<BidirectionalIteratorNotDerivedFrom>);
 static_assert(!std::bidirectional_iterator<BidirectionalIteratorNotDerivedFrom>);
 static_assert(!std::ranges::bidirectional_range<BidirectionalRangeNotDerivedFrom>);
 
 class BidirectionalIteratorNotDecrementable {
 public:
   using difference_type = long;

libcxx/test/support/test_iterators.h

public:
     void operator,(T const &) = delete;
 
 private:
     decltype(base(std::declval<It>())) base_;
     difference_type stride_count_ = 0;
     difference_type stride_displacement_ = 0;
 };
 
+template <std::input_iterator Base>
+consteval auto get_iterator_concept() {
+  if constexpr (std::contiguous_iterator<Base>) {
+    return std::contiguous_iterator_tag();
+  } else if constexpr (std::random_access_iterator<Base>) {
+    return std::random_access_iterator_tag{};
+  } else if constexpr (std::bidirectional_iterator<Base>) {
+    return std::bidirectional_iterator_tag{};
+  } else if constexpr (std::forward_iterator<Base>) {
+    return std::forward_iterator_tag{};
+  } else {
+    return std::input_iterator_tag{};
+  }
+}
+
+template <std::input_iterator Iter>
+using iter_concept_t = decltype(get_iterator_concept<Iter>());
+
+template <class Iter>
+struct SwapCountingIterator {
+  using difference_type  = std::iter_difference_t<Iter>;
+  using value_type       = std::iter_value_t<Iter>;
+  using iterator_concept = iter_concept_t<Iter>;
+
+  Iter iter_;
+  int* counter_;
+  SwapCountingIterator() = default;
+  constexpr SwapCountingIterator(const Iter& iter, int* counter) : iter_(iter), counter_(counter) {}
+
+  constexpr friend void iter_swap(const SwapCountingIterator& lhs, const SwapCountingIterator& rhs) {
+    std::ranges::iter_swap(lhs.iter_, rhs.iter_);
+    ++*lhs.counter_;
+  }
+
+  constexpr SwapCountingIterator& operator++() {
+    ++iter_;
+    return *this;
+  }
+
+  constexpr SwapCountingIterator operator++(int) {
+    auto tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  constexpr SwapCountingIterator& operator--() {
+    --iter_;
+    return *this;
+  }
+
+  constexpr SwapCountingIterator operator--(int) {
+    auto tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  constexpr auto base() { return base(iter_); }
+
+  constexpr decltype(auto) operator*() const { return *iter_; }
+
+  friend bool operator==(const SwapCountingIterator& lhs, const SwapCountingIterator& rhs) = default;
+
+  constexpr operator Iter() {
+    return iter_;
+  }
+
+  // to satisfy random_access_iterator
+  constexpr SwapCountingIterator& operator+=(difference_type n)
+    requires std::random_access_iterator<Iter> {
+    iter_ += n;
+    return *this;
+  }
+
+  constexpr SwapCountingIterator& operator-=(difference_type n)
+    requires std::random_access_iterator<Iter> {
+    iter_ -= n;
+    return *this;
+  }
+
+  constexpr decltype(auto) operator[](difference_type n) const
+    requires std::random_access_iterator<Iter> {
+    return iter_[n];
+  }
+
+  friend constexpr bool operator<(const SwapCountingIterator& x, const SwapCountingIterator& y)
+    requires std::random_access_iterator<Iter> {
+    return x.iter_ < y.iter_;
+  }
+
+  friend constexpr bool operator>(const SwapCountingIterator& x, const SwapCountingIterator& y)
+    requires std::random_access_iterator<Iter> {
+    return x.iter_ > y.iter_;
+  }
+
+  friend constexpr bool operator<=(const SwapCountingIterator& x, const SwapCountingIterator& y)
+    requires std::random_access_iterator<Iter> {
+    return x.iter_ <= y.iter_;
+  }
+
+  friend constexpr bool operator>=(const SwapCountingIterator& x, const SwapCountingIterator& y)
+    requires std::random_access_iterator<Iter> {
+    return x.iter_ >= y.iter_;
+  }
+
+  friend constexpr auto operator<=>(const SwapCountingIterator& x, const SwapCountingIterator& y)
+    requires(std::random_access_iterator<Iter> && std::three_way_comparable<Iter>) {
+    return x.iter_ <=> y.iter_;
+  }
+
+  friend constexpr SwapCountingIterator operator+(const SwapCountingIterator& x, difference_type n)
+    requires std::random_access_iterator<Iter> {
+    return SwapCountingIterator{x.iter_ + n};
+  }
+
+  friend constexpr SwapCountingIterator operator+(difference_type n, const SwapCountingIterator& x)
+    requires std::random_access_iterator<Iter> {
+    return SwapCountingIterator{n + x.iter_};
+  }
+
+  friend constexpr SwapCountingIterator operator-(const SwapCountingIterator& x, difference_type n)
+    requires std::random_access_iterator<Iter> {
+    return SwapCountingIterator{x.iter_ - n};
+  }
+
+  friend constexpr difference_type operator-(const SwapCountingIterator& x, const SwapCountingIterator& y)
+    requires std::random_access_iterator<Iter> {
+    return x.iter_ - y.iter_;
+  }
+
+};
+
+static_assert(std::bidirectional_iterator<SwapCountingIterator<bidirectional_iterator<int*>>>);
+static_assert(std::random_access_iterator<SwapCountingIterator<random_access_iterator<int*>>>);
+
 #endif // TEST_STD_VER > 17
 
 #if TEST_STD_VER > 17
 template <class It>
 class sentinel_wrapper {
 public:
     explicit sentinel_wrapper() = default;
     constexpr explicit sentinel_wrapper(const It& it) : base_(base(it)) {}

 };
 
 } // namespace adl
 
 // Proxy
 // ======================================================================
 // Proxy that can wrap a value or a reference. It simulates C++23's tuple
 // but simplified to just hold one argument.
-// Note that unlike tuple, this class deliberately doesn't have special handling 
-// of swap to cause a compilation error if it's used in an algorithm that relies 
+// Note that unlike tuple, this class deliberately doesn't have special handling
+// of swap to cause a compilation error if it's used in an algorithm that relies
 // on plain swap instead of ranges::iter_swap.
 // This class is useful for testing that if algorithms support proxy iterator
 // properly, i.e. calling ranges::iter_swap and ranges::iter_move instead of
-// plain swap and std::move 
+// plain swap and std::move
 template <class T>
 struct Proxy;
 
 template <class T>
 inline constexpr bool IsProxy = false;
 
 template <class T>
 inline constexpr bool IsProxy<Proxy<T>> = true;

 // iter_value_t -> Proxy<int>
 // iter_move    -> Proxy<int&&>
 template <class Base>
 struct ProxyIteratorBase {};
 
 template <class Base>
   requires std::derived_from<
       typename std::iterator_traits<Base>::iterator_category,
-      std::input_iterator_tag> 
+      std::input_iterator_tag>
 struct ProxyIteratorBase<Base> {
   using iterator_category = std::input_iterator_tag;
 };
 
 template <std::input_iterator Base>
-consteval auto get_iterator_concept() {
-  if constexpr (std::random_access_iterator<Base>) {
-    return std::random_access_iterator_tag{};
-  } else if constexpr (std::bidirectional_iterator<Base>) {
-    return std::bidirectional_iterator_tag{};
-  } else if constexpr (std::forward_iterator<Base>) {
-    return std::forward_iterator_tag{};
-  } else {
-    return std::input_iterator_tag{};
-  }
-}
-
-template <std::input_iterator Base>
 struct ProxyIterator : ProxyIteratorBase<Base> {
   Base base_;
 
-  using iterator_concept = decltype(get_iterator_concept<Base>());
+  using iterator_concept = iter_concept_t<Base>;
   using value_type       = Proxy<std::iter_value_t<Base>>;
   using difference_type  = std::iter_difference_t<Base>;
 
   ProxyIterator()
     requires std::default_initializable<Base>
   = default;
 
   constexpr ProxyIterator(Base base) : base_{std::move(base)} {}
-  
-  template <class T> 
+  template <class T>
     requires std::constructible_from<Base, T&&>
   constexpr ProxyIterator(T&& t) : base_{std::forward<T>(t)} {}
 
   friend constexpr decltype(auto) base(const ProxyIterator& p) { return base(p.base_); }
 
   // Specialization of iter_move
   // If operator* returns Proxy<Foo&>, iter_move will return Proxy<Foo&&>
   // Note std::move(*it) returns Proxy<Foo&>&&, which is not what we want as