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

[huixie90]

libcxx/include/CMakeLists.txt

116

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 ↗

(On Diff #444987)

take the arguments by const ref, as indirectly_swappable requires const

760 ↗

(On Diff #444987)

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 ↗

(On Diff #444987)

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

760 ↗

(On Diff #444987)

Because that would increment the counter two times per swap.

[var-const]

libcxx/include/CMakeLists.txt

127

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.

46

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

49

Nit: blank line above.

54

Nit: blank line above.

58

Nit: blank line above.

72

Nit: move?

libcxx/include/algorithm

866

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)

122

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

92

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 ↗

(On Diff #445453)

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

758 ↗

(On Diff #445453)

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

763 ↗

(On Diff #445453)

(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.

122

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

92

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 ↗

(On Diff #445453)

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 ↗

(On Diff #445453)

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

92

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

92

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,nth_element,Konstantin Varlamov,`D128149 <https://llvm.org/D128149>`_,✅
 Permutation,partial_sort,Konstantin Varlamov,`D128744 <https://llvm.org/D128744>`_,✅
 Permutation,inplace_merge,Hui Xie,`D130627 <https://llvm.org/D130627>`_,✅
 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,next_permutation,Nikolas Klauser and Konstantin Varlamov,`D129859 <https://llvm.org/D129859>`_,✅
+Permutation,prev_permutation,Nikolas Klauser and Konstantin Varlamov,`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.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_prev_permutation.h
   __algorithm/ranges_push_heap.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
   __algorithm/ranges_reverse.h

libcxx/include/__algorithm/iterator_operations.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_ITERATOR_OPERATIONS_H
 #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
 
 #include <__algorithm/iter_swap.h>
+#include <__algorithm/ranges_iterator_concept.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__iterator/readable_traits.h>

 struct _RangeAlgPolicy {};
 
 template <>
 struct _IterOps<_RangeAlgPolicy> {
 
   template <class _Iter>
   using __value_type = iter_value_t<_Iter>;
 
+  template <class _Iter>
+  using __iterator_category = decltype(ranges::__iterator_concept<_Iter>());
+
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
   static constexpr auto __iter_move = ranges::iter_move;
   static constexpr auto iter_swap = ranges::iter_swap;
   static constexpr auto next = ranges::next;
   static constexpr auto __advance_to = ranges::advance;
 };
 
 #endif
 
 struct _ClassicAlgPolicy {};
 
 template <>
 struct _IterOps<_ClassicAlgPolicy> {
 
   template <class _Iter>
   using __value_type = typename iterator_traits<_Iter>::value_type;
 
+  template <class _Iter>
+  using __iterator_category = typename iterator_traits<_Iter>::iterator_category;
+
   // advance
   template <class _Iter, class _Distance>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
   static void advance(_Iter& __iter, _Distance __count) {
     std::advance(__iter, __count);
   }
 
   // distance

libcxx/include/__algorithm/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_NEXT_PERMUTATION_H
 #define _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/reverse.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _BidirectionalIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17
+pair<_BidirectionalIterator, bool>
+__next_permutation(_BidirectionalIterator __first, _Sentinel __last, _Compare&& __comp)
 {
-    _BidirectionalIterator __i = __last;
+    using _Result = pair<_BidirectionalIterator, bool>;
+
+    _BidirectionalIterator __last_iter = _IterOps<_AlgPolicy>::next(__first, __last);
+    _BidirectionalIterator __i = __last_iter;
     if (__first == __last || __first == --__i)
-        return false;
+        return _Result(std::move(__last_iter), false);
+
     while (true)
     {
         _BidirectionalIterator __ip1 = __i;
         if (__comp(*--__i, *__ip1))
         {
-            _BidirectionalIterator __j = __last;
+            _BidirectionalIterator __j = __last_iter;
             while (!__comp(*__i, *--__j))
                 ;
-            swap(*__i, *__j);
-            _VSTD::reverse(__ip1, __last);
-            return true;
+            _IterOps<_AlgPolicy>::iter_swap(__i, __j);
+            std::__reverse<_AlgPolicy>(__ip1, __last_iter);
+            return _Result(std::move(__last_iter), true);
         }
         if (__i == __first)
         {
-            _VSTD::reverse(__first, __last);
-            return false;
+            std::__reverse<_AlgPolicy>(__first, __last_iter);
+            return _Result(std::move(__last_iter), false);
         }
     }
 }
 
 template <class _BidirectionalIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp);
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  return std::__next_permutation<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), static_cast<_Comp_ref>(__comp)).second;
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     return _VSTD::next_permutation(__first, __last,
                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H

libcxx/include/__algorithm/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_PREV_PERMUTATION_H
 #define _LIBCPP___ALGORITHM_PREV_PERMUTATION_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/reverse.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _BidirectionalIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17
+pair<_BidirectionalIterator, bool>
+__prev_permutation(_BidirectionalIterator __first, _Sentinel __last, _Compare&& __comp)
 {
-    _BidirectionalIterator __i = __last;
+    using _Result = pair<_BidirectionalIterator, bool>;
+
+    _BidirectionalIterator __last_iter = _IterOps<_AlgPolicy>::next(__first, __last);
+    _BidirectionalIterator __i = __last_iter;
     if (__first == __last || __first == --__i)
-        return false;
+        return _Result(std::move(__last_iter), false);
+
     while (true)
     {
         _BidirectionalIterator __ip1 = __i;
         if (__comp(*__ip1, *--__i))
         {
-            _BidirectionalIterator __j = __last;
+            _BidirectionalIterator __j = __last_iter;
             while (!__comp(*--__j, *__i))
                 ;
-            swap(*__i, *__j);
-            _VSTD::reverse(__ip1, __last);
-            return true;
+            _IterOps<_AlgPolicy>::iter_swap(__i, __j);
+            std::__reverse<_AlgPolicy>(__ip1, __last_iter);
+            return _Result(std::move(__last_iter), true);
         }
         if (__i == __first)
         {
-            _VSTD::reverse(__first, __last);
-            return false;
+            std::__reverse<_AlgPolicy>(__first, __last_iter);
+            return _Result(std::move(__last_iter), false);
         }
     }
 }
 
 template <class _BidirectionalIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp);
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  return std::__prev_permutation<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), static_cast<_Comp_ref>(__comp)).second;
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     return _VSTD::prev_permutation(__first, __last,
                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PREV_PERMUTATION_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/iterator_operations.h>
+#include <__algorithm/make_projected.h>
+#include <__algorithm/next_permutation.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.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 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 __result = std::__next_permutation<_RangeAlgPolicy>(
+        std::move(__first), std::move(__last), std::__make_projected(__comp, __proj));
+    return {std::move(__result.first), std::move(__result.second)};
+  }
+
+  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 __result = std::__next_permutation<_RangeAlgPolicy>(
+        ranges::begin(__range), ranges::end(__range), std::__make_projected(__comp, __proj));
+    return {std::move(__result.first), std::move(__result.second)};
+  }
+};
+
+} // 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/iterator_operations.h>
+#include <__algorithm/make_projected.h>
+#include <__algorithm/prev_permutation.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__iterator/concepts.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.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>;
+
+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 {
+    auto __result = std::__prev_permutation<_RangeAlgPolicy>(
+        std::move(__first), std::move(__last), std::__make_projected(__comp, __proj));
+    return {std::move(__result.first), std::move(__result.second)};
+  }
+
+  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 {
+    auto __result = std::__prev_permutation<_RangeAlgPolicy>(
+        ranges::begin(__range), ranges::end(__range), std::__make_projected(__comp, __proj));
+    return {std::move(__result.first), std::move(__result.second)};
+  }
+
+};
+
+} // 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/reverse.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_REVERSE_H
 #define _LIBCPP___ALGORITHM_REVERSE_H
 
 #include <__algorithm/iter_swap.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _BidirectionalIterator>
+template <class _AlgPolicy, class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
-__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
+__reverse_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
 {
     while (__first != __last)
     {
         if (__first == --__last)
             break;
-        _VSTD::iter_swap(__first, __last);
+        _IterOps<_AlgPolicy>::iter_swap(__first, __last);
         ++__first;
     }
 }
 
-template <class _RandomAccessIterator>
+template <class _AlgPolicy, class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
-__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
+__reverse_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
 {
     if (__first != __last)
         for (; __first < --__last; ++__first)
-            _VSTD::iter_swap(__first, __last);
+            _IterOps<_AlgPolicy>::iter_swap(__first, __last);
+}
+
+template <class _AlgPolicy, class _BidirectionalIterator, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void __reverse(_BidirectionalIterator __first, _Sentinel __last) {
+  using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_BidirectionalIterator>;
+  std::__reverse_impl<_AlgPolicy>(std::move(__first), std::move(__last), _IterCategory());
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
-    _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
+  std::__reverse<_ClassicAlgPolicy>(std::move(__first), std::move(__last));
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_REVERSE_H

libcxx/include/algorithm

template<input_range R1, input_range R2, weakly_incrementable O,
     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<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            class Proj1 = identity, class Proj2 = identity,
            indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
              ranges::less>
     constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
 
   template<input_range R1, input_range R2, class Proj1 = identity,
            class Proj2 = identity,
            indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
                                       projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
     constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   template<input_range R, weakly_incrementable O, class Proj = identity,
            indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
     requires indirectly_copyable<iterator_t<R>, O> &&
              (forward_iterator<iterator_t<R>> ||
               (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
               indirectly_copyable_storable<iterator_t<R>, O>)
     constexpr unique_copy_result<borrowed_iterator_t<R>, O>
       unique_copy(R&& r, O result, C comp = {}, Proj proj = {});                                   // Since C++20
+
+  template<class I>
+    using prev_permutation_result = in_found_result<I>;                                            // 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<class I>
+    using next_permutation_result = in_found_result<I>;                                            // 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
+
   }
 
+template <class InputIterator, class Predicate>
     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);
 
 template <class InputIterator, class Predicate>

 #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_partial_sort.h>
 #include <__algorithm/ranges_partial_sort_copy.h>
 #include <__algorithm/ranges_partition.h>
 #include <__algorithm/ranges_partition_copy.h>
 #include <__algorithm/ranges_partition_point.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

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

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

 //===----------------------------------------------------------------------===//
 //
 // 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_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.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partial_sort.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
+// ADDITIONAL_COMPILE_FLAGS: -fconstexpr-steps=3000000
+
+// 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) {
+  std::array memoized = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
+  return memoized[i];
+}
+
+template <class Iter, class Range, class Func>
+constexpr bool run_next_permutation(Func call_next_permutation, Range permuted, Range previous) {
+  using Result = std::ranges::next_permutation_result<Iter>;
+
+  std::same_as<Result> decltype(auto) ret = call_next_permutation(permuted);
+  assert(ret.in == permuted.end());
+  bool next_found = ret.found;
+
+  if (std::ranges::distance(permuted) > 1) {
+    if (next_found) {
+      assert(std::ranges::lexicographical_compare(previous, permuted));
+    } else {
+      assert(std::ranges::lexicographical_compare(permuted, previous));
+      assert(std::ranges::is_sorted(permuted));
+    }
+  }
+
+  return next_found;
+}
+
+template <class Iter, class Sent, class Func>
+constexpr void test_next_permutations(Func call_next_permutation) {
+  std::array input = {1, 2, 3, 4};
+  auto current_permutation = input;
+  auto previous_permutation = current_permutation;
+
+  // For all subarrays of `input` from `[0, 0]` to `[0, N - 1]`, call `next_permutation` until no next permutation
+  // exists.
+  // The number of permutations must equal `!N`. `run_next_permutation` checks that each next permutation is
+  // lexicographically greater than the previous. If these two conditions hold (the number of permutations is `!N`, and
+  // each permutation is lexicographically greater than the previous one), it follows that the
+  // `ranges::next_permutation` algorithm works correctly.
+  for (size_t i = 0; i <= current_permutation.size(); ++i) {
+    size_t count = 0;
+    bool next_found = true;
+
+    while (next_found) {
+      ++count;
+      previous_permutation = current_permutation;
+
+      auto current_subrange = std::ranges::subrange(
+          Iter(current_permutation.data()), Sent(Iter(current_permutation.data() + i)));
+      auto previous_subrange = std::ranges::subrange(
+          Iter(previous_permutation.data()), Sent(Iter(previous_permutation.data() + i)));
+
+      next_found = run_next_permutation<Iter>(call_next_permutation, current_subrange, previous_subrange);
+    }
+
+    assert(count == factorial(i));
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_all_permutations() {
+  test_next_permutations<Iter, Sent>([](auto&& range) {
+    return std::ranges::next_permutation(range.begin(), range.end());
+  });
+
+  test_next_permutations<Iter, Sent>([](auto&& range) {
+    return std::ranges::next_permutation(range);
+  });
+}
+
+template <class Iter, class Sent, int N>
+constexpr void test_one(const std::array<int, N> input, bool expected_found, std::array<int, N> expected) {
+  using Result = std::ranges::next_permutation_result<Iter>;
+
+  { // (iterator, sentinel) overload.
+    auto in = input;
+    auto begin = Iter(in.data());
+    auto end = Sent(Iter(in.data() + in.size()));
+
+    std::same_as<Result> decltype(auto) result = std::ranges::next_permutation(begin, end);
+    assert(result.found == expected_found);
+    assert(result.in == end);
+    assert(in == expected);
+  }
+
+  {  // (range) overload.
+    auto in = input;
+    auto begin = Iter(in.data());
+    auto end = Sent(Iter(in.data() + in.size()));
+    auto range = std::ranges::subrange(begin, end);
+
+    std::same_as<Result> decltype(auto) result = std::ranges::next_permutation(range);
+    assert(result.found == expected_found);
+    assert(result.in == end);
+    assert(in == expected);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iter_sent() {
+  test_all_permutations<Iter, Sent>();
+
+  // Empty range.
+  test_one<Iter, Sent, 0>({}, false, {});
+  // 1-element range.
+  test_one<Iter, Sent, 1>({1}, false, {1});
+  // 2-element range.
+  test_one<Iter, Sent, 2>({1, 2}, true, {2, 1});
+  test_one<Iter, Sent, 2>({2, 1}, false, {1, 2});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({1, 2, 3, 4, 5, 6, 7, 8}, true, {1, 2, 3, 4, 5, 6, 8, 7});
+  // Longer sequence, permutations exhausted.
+  test_one<Iter, Sent, 8>({8, 7, 6, 5, 4, 3, 2, 1}, false, {1, 2, 3, 4, 5, 6, 7, 8});
+}
+
+template <class Iter>
+constexpr void test_iter() {
+  test_iter_sent<Iter, Iter>();
+  test_iter_sent<Iter, sentinel_wrapper<Iter>>();
+  test_iter_sent<Iter, sized_sentinel<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iter<bidirectional_iterator<int*>>();
+  test_iter<random_access_iterator<int*>>();
+  test_iter<contiguous_iterator<int*>>();
+  test_iter<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom predicate works.
+    struct A {
+      int i;
+      constexpr bool comp(const A& rhs) const { return i > rhs.i; }
+      constexpr bool operator==(const A&) const = default;
+    };
+    const std::array input = {A{1}, A{2}, A{3}, A{4}, A{5}};
+    std::array expected = {A{5}, A{4}, A{3}, A{2}, A{1}};
+
+    { // (iterator, sentinel) overload.
+      auto in = input;
+      auto result = std::ranges::next_permutation(in.begin(), in.end(), &A::comp);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+
+    { // (range) overload.
+      auto in = input;
+      auto result = std::ranges::next_permutation(in, &A::comp);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int i;
+      constexpr A negate() const { return A{i * -1}; }
+      constexpr auto operator<=>(const A&) const = default;
+    };
+    const std::array input = {A{1}, A{2}, A{3}, A{4}, A{5}};
+    std::array expected = {A{5}, A{4}, A{3}, A{2}, A{1}};
+
+    { // (iterator, sentinel) overload.
+      auto in = input;
+      auto result = std::ranges::next_permutation(in.begin(), in.end(), {}, &A::negate);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+
+    { // (range) overload.
+      auto in = input;
+      auto result = std::ranges::next_permutation(in, {}, &A::negate);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+  }
+
+  { // Complexity: At most `(last - first) / 2` swaps.
+    const std::array input = {1, 2, 3, 4, 5, 6};
+
+    { // (iterator, sentinel) overload.
+      auto in = input;
+      int swaps_count = 0;
+      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count);
+      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count);
+
+      std::ranges::next_permutation(begin, end);
+      assert(swaps_count <= (base(end) - base(begin) + 1) / 2);
+    }
+
+    { // (range) overload.
+      auto in = input;
+      int swaps_count = 0;
+      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count);
+      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count);
+
+      std::ranges::next_permutation(std::ranges::subrange(begin, end));
+      assert(swaps_count <= (base(end) - base(begin) + 1) / 2);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

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) {
+  std::array memoized = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
+  return memoized[i];
+}
+
+template <class Iter, class Range, class Func>
+constexpr bool run_prev_permutation(Func call_prev_permutation, Range permuted, Range previous) {
+  using Result = std::ranges::prev_permutation_result<Iter>;
+
+  std::same_as<Result> decltype(auto) ret = call_prev_permutation(permuted);
+  assert(ret.in == permuted.end());
+  bool next_found = ret.found;
+
+  if (std::ranges::distance(permuted) > 1) {
+    if (next_found) {
+      assert(std::ranges::lexicographical_compare(permuted, previous));
+    } else {
+      assert(std::ranges::lexicographical_compare(previous, permuted));
+      assert(std::ranges::is_sorted(permuted, std::ranges::greater{}));
+    }
+  }
+
+  return next_found;
+}
+
+template <class Iter, class Sent, class Func>
+constexpr void test_prev_permutations(Func call_prev_permutation) {
+  std::array input = {4, 3, 2, 1};
+  auto current_permutation = input;
+  auto previous_permutation = current_permutation;
+
+  // For all subarrays of `input` from `[0, 0]` to `[0, N - 1]`, call `prev_permutation` until no previous permutation
+  // exists.
+  // The number of permutations must equal `!N`. `run_prev_permutation` checks that each previous permutation is
+  // lexicographically less than the previous. If these two conditions hold (the number of permutations is `!N`, and
+  // each permutation is lexicographically less than the previous one), it follows that the `ranges::prev_permutation`
+  // algorithm works correctly.
+  for (size_t i = 0; i <= current_permutation.size(); ++i) {
+    size_t count = 0;
+    bool next_found = true;
+
+    while (next_found) {
+      ++count;
+      previous_permutation = current_permutation;
+
+      auto current_subrange = std::ranges::subrange(
+          Iter(current_permutation.data()), Sent(Iter(current_permutation.data() + i)));
+      auto previous_subrange = std::ranges::subrange(
+          Iter(previous_permutation.data()), Sent(Iter(previous_permutation.data() + i)));
+
+      next_found = run_prev_permutation<Iter>(call_prev_permutation, current_subrange, previous_subrange);
+    }
+
+    assert(count == factorial(i));
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_all_permutations() {
+  test_prev_permutations<Iter, Sent>([](auto&& range) {
+    return std::ranges::prev_permutation(range.begin(), range.end());
+  });
+
+  test_prev_permutations<Iter, Sent>([](auto&& range) {
+    return std::ranges::prev_permutation(range);
+  });
+}
+
+template <class Iter, class Sent, int N>
+constexpr void test_one(const std::array<int, N> input, bool expected_found, std::array<int, N> expected) {
+  using Result = std::ranges::prev_permutation_result<Iter>;
+
+  { // (iterator, sentinel) overload.
+    auto in = input;
+    auto begin = Iter(in.data());
+    auto end = Sent(Iter(in.data() + in.size()));
+
+    std::same_as<Result> decltype(auto) result = std::ranges::prev_permutation(begin, end);
+    assert(result.found == expected_found);
+    assert(result.in == end);
+    assert(in == expected);
+  }
+
+  {  // (range) overload.
+    auto in = input;
+    auto begin = Iter(in.data());
+    auto end = Sent(Iter(in.data() + in.size()));
+    auto range = std::ranges::subrange(begin, end);
+
+    std::same_as<Result> decltype(auto) result = std::ranges::prev_permutation(range);
+    assert(result.found == expected_found);
+    assert(result.in == end);
+    assert(in == expected);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iter_sent() {
+  test_all_permutations<Iter, Sent>();
+
+  // Empty range.
+  test_one<Iter, Sent, 0>({}, false, {});
+  // 1-element range.
+  test_one<Iter, Sent, 1>({1}, false, {1});
+  // 2-element range.
+  test_one<Iter, Sent, 2>({1, 2}, false, {2, 1});
+  test_one<Iter, Sent, 2>({2, 1}, true, {1, 2});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({8, 7, 6, 5, 4, 3, 2, 1}, true, {8, 7, 6, 5, 4, 3, 1, 2});
+  // Longer sequence, permutations exhausted.
+  test_one<Iter, Sent, 8>({1, 2, 3, 4, 5, 6, 7, 8}, false, {8, 7, 6, 5, 4, 3, 2, 1});
+}
+
+template <class Iter>
+constexpr void test_iter() {
+  test_iter_sent<Iter, Iter>();
+  test_iter_sent<Iter, sentinel_wrapper<Iter>>();
+  test_iter_sent<Iter, sized_sentinel<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iter<bidirectional_iterator<int*>>();
+  test_iter<random_access_iterator<int*>>();
+  test_iter<contiguous_iterator<int*>>();
+  test_iter<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom predicate works.
+    struct A {
+      int i;
+      constexpr bool comp(const A& rhs) const { return i > rhs.i; }
+      constexpr bool operator==(const A&) const = default;
+    };
+    const std::array input = {A{5}, A{4}, A{3}, A{2}, A{1}};
+    std::array expected = {A{1}, A{2}, A{3}, A{4}, A{5}};
+
+    { // (iterator, sentinel) overload.
+      auto in = input;
+      auto result = std::ranges::prev_permutation(in.begin(), in.end(), &A::comp);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+
+    { // (range) overload.
+      auto in = input;
+      auto result = std::ranges::prev_permutation(in, &A::comp);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int i;
+      constexpr A negate() const { return A{i * -1}; }
+      constexpr auto operator<=>(const A&) const = default;
+    };
+    const std::array input = {A{5}, A{4}, A{3}, A{2}, A{1}};
+    std::array expected = {A{1}, A{2}, A{3}, A{4}, A{5}};
+
+    { // (iterator, sentinel) overload.
+      auto in = input;
+      auto result = std::ranges::prev_permutation(in.begin(), in.end(), {}, &A::negate);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+
+    { // (range) overload.
+      auto in = input;
+      auto result = std::ranges::prev_permutation(in, {}, &A::negate);
+
+      assert(result.found == false);
+      assert(result.in == in.end());
+      assert(in == expected);
+    }
+  }
+
+  { // Complexity: At most `(last - first) / 2` swaps.
+    const std::array input = {6, 5, 4, 3, 2, 1};
+
+    { // (iterator, sentinel) overload.
+      auto in = input;
+      int swaps_count = 0;
+      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count);
+      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count);
+
+      std::ranges::prev_permutation(begin, end);
+      assert(swaps_count <= (base(end) - base(begin) + 1) / 2);
+    }
+
+    { // (range) overload.
+      auto in = input;
+      int swaps_count = 0;
+      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count);
+      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count);
+
+      std::ranges::prev_permutation(std::ranges::subrange(begin, end));
+      assert(swaps_count <= (base(end) - base(begin) + 1) / 2);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/ranges_result_alias_declarations.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(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.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
 //
 //===----------------------------------------------------------------------===//
 
constexpr bool test_all() {
   test_mid(std::ranges::partial_sort, in, mid, binary_pred);
   test_mid(std::ranges::nth_element, in, mid, binary_pred);
   if (!std::is_constant_evaluated())
     test_mid(std::ranges::inplace_merge, in, mid, binary_pred);
   test(std::ranges::make_heap, in, binary_pred);
   test(std::ranges::push_heap, in, binary_pred);
   test(std::ranges::pop_heap, in, binary_pred);
   test(std::ranges::sort_heap, in, binary_pred);
-  //test(std::ranges::prev_permutation, in, binary_pred);
-  //test(std::ranges::next_permutation, in, binary_pred);
+  test(std::ranges::prev_permutation, in, binary_pred);
+  test(std::ranges::next_permutation, in, binary_pred);
 
   return true;
 }
 
 int main(int, char**) {
   test_all();
   static_assert(test_all());
 
   return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.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
 //
 //===----------------------------------------------------------------------===//
 
constexpr bool test_all() {
   test_mid(std::ranges::partial_sort, in, mid, &Foo::binary_pred, &Bar::val);
   test_mid(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val);
   if (!std::is_constant_evaluated())
     test_mid(std::ranges::inplace_merge, in, mid, &Foo::binary_pred, &Bar::val);
   test(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
-  //test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
-  //test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
 
   return true;
 }
 
 int main(int, char**) {
   test_all();
   static_assert(test_all());
 
   return 0;
 }

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