[libc++][ranges] Implement `ranges::is_permutation`

[var-const]

libcxx/docs/Status/RangesAlgorithms.csv

31–36

Missing link.

libcxx/include/__algorithm/is_permutation.h

122

Question: using __invoke slightly changes the behavior of the non-ranges version of the algorithm as well, right?

213–214

Optional: can you use using like other similar places that were refactored in this patch?

libcxx/include/__algorithm/ranges_is_permutation.h

27

Please add the language version/no incomplete ranges guard.

45

Nit: please move the iterators (and add the include).

55

Can we do the same optimization in the iterator version (by checking sized_sentinel_for)?

60

Should this go to the else branch of the if constexpr?

libcxx/include/algorithm

1797

Missing synopsis.

libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp

9

Missing synopsis.

88

Please also check with a single-element range.

96

Nit: there's an unnecessary blank line.

110

Please also add test cases that use a non-default projection or a non-default predicate.

191

Should be ranges of different sizes or similar. Also, is there a reason that these test cases aren't part of the test function?

[philnik]

libcxx/include/__algorithm/is_permutation.h

122

Any changes to the behaviour should be negated by the __is_callable check.

[var-const]

Changes to is_permutation.h:

• refactor out the common part of __is_partition overloads taking 3 and 4 iterators;
• rename __is_partition to __is_partition3 and __is_partition4 depending on the number of iterators;
• to optimize __is_partition for constant-time distance, replace the existing tag dispatch based on iterator category with a custom trait. This works with ranges and covers more cases in C++20 mode;
• fix the bug in the optimization above which would prevent it from being selected by overload resolution (incorrect iterator types in the signature) unless all iterator types are the same;
• use _IterOps in __is_partition;
• other miscellaneous cleanup.

Changes to the tests:

• check SFINAE on the predicate;
• add tests for a custom predicate;
• add tests for a custom projection;
• add more complexity tests and use counting_{projection,predicate};
• add a couple more test cases.

Also address the existing feedback and rebase on main.

[var-const]

libcxx/include/__algorithm/is_permutation.h

154–155

I think this was a bug -- the type of __last1 should be _RandomAccessIterator1, not 2. This would only work if both iterator types are the same, IIUC.

[var-const]

Test the constant-time distance optimization with different iterator types.

[var-const]

Reduce the number of iterations in constexpr std::sort tests to prevent
Clang from exceeding the maximum step limit.

[var-const]

Increase the constexpr evaluation steps limit on constexpr std::sort tests;
now that there is one extra function in the is_permutation call stack, it
started to exceed the default limit.

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[var-const]

Fix the CI and rebase.

[var-const]

"Fix" the constexpr step limit again.

[ldionne]

libcxx/include/__algorithm/is_permutation.h

34–63

Is this #if wrong, or is the #endif comment wrong?

59

I would suggest naming this __is_permutation_impl or something like that. I think it expresses most clearly what the function actually does.

Otherwise, I was trying to understand how it was different from std::equal_range (which has very little in common).

100

Here and elsewhere.

101–107

FWIW I think this is a reimplementation of std::mismatch.

I don't mind whether we refactor this now or after (or not at all if it turns out not to be a good idea). But we should at least look into it.

175–181

Instead, why not have just two versions of __is_permutation4 and use enable_if_t? I don't think you need this function at all.

libcxx/include/__algorithm/ranges_is_permutation.h

42

I would suggest looking into naming __is_permutation4 and __is_permutation3 just __is_permutation. That way, they can be called as std::__is_permutation<Policy>, which is nicely consistent with what we do for other algorithms.

69–72

Is this still needed here, or do we handle this in __is_permutation?

[var-const]

Address feedback.

[var-const]

libcxx/include/__algorithm/is_permutation.h

34–63

Fixed. I think the #if is correct -- we only guard sized_sentinel_for with the language version, so it's okay to use regardless of whether ranges are enabled, and it covers more cases than the more simplistic check in the #else branch.

101–107

I'd like to try it out, but would leave it to a follow-up patch.

175–181

The _ConstTimeDistance == true overload relies on the ability to delegate to the _ConstTimeDistance == false overload (which is easy because it can pass false_type directly instead of using the trait). It seems like it would be more difficult to achieve with enable_if (unless there's some approach I didn't think of).

libcxx/include/__algorithm/ranges_is_permutation.h

42

Done. I found myself getting confused between all the different overloads, but it's a good point that having a single name would be consistent with other algorithms.

69–72

Unfortunately, I think it's still necessary. It's possible for the range to be a sized_range without the sentinel satisfying sized_sentinel_for -- e.g. the range type could define size() member function but the sentinel is just a forward iterator that doesn't support subtracting (on which sized_sentinel_for relies).

[h-vetinari]

That was the last algorithm in RangesAlgorithms.csv - congratulations! :)

[var-const]

In D127194#3700467, @h-vetinari wrote:

That was the last algorithm in RangesAlgorithms.csv - congratulations! :)

Thank you! There are more range algorithms added in C++23, but we're now finished with what was in the original One Ranges Proposal.

libcxx/docs/Status/RangesAlgorithms.csv

 Search,minmax_element,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,count,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,count_if,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,search,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Search,search_n,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Search,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Read-only,is_partitioned,Nikolas Klauser,`D124440 <https://llvm.org/D124440>`_,✅
 Read-only,is_sorted,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,is_sorted_until,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,includes,Hui Xie,`D130116 <https://llvm.org/D130116>`_,✅
 Read-only,is_heap,Konstantin Varlamov,`D130547 <https://llvm.org/D130547>`_,✅
 Read-only,is_heap_until,Konstantin Varlamov,`D130547 <https://llvm.org/D130547>`_,✅
 Read-only,clamp,Nikolas Klauser,`D126193 <https://llvm.org/D126193>`_,✅
-Read-only,is_permutation,Nikolas Klauser,`D127194 <https://llvm.org/D127194>`_,Under review
+Read-only,is_permutation,Nikolas Klauser,`D127194 <https://llvm.org/D127194>`_,✅
 Read-only,for_each,Nikolas Klauser,`D124332 <https://llvm.org/D124332>`_,✅
 Read-only,for_each_n,Nikolas Klauser,`D124332 <https://llvm.org/D124332>`_,✅
 Write,copy,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,copy_if,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,copy_n,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,copy_backward,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,move,Nikolas Klauser,`D126616 <https://llvm.org/D126616>`_,✅
 Write,move_backward,Nikolas Klauser,`D126616 <https://llvm.org/D126616>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_for_each_n.h
   __algorithm/ranges_generate.h
   __algorithm/ranges_generate_n.h
   __algorithm/ranges_includes.h
   __algorithm/ranges_inplace_merge.h
   __algorithm/ranges_is_heap.h
   __algorithm/ranges_is_heap_until.h
   __algorithm/ranges_is_partitioned.h
+  __algorithm/ranges_is_permutation.h
   __algorithm/ranges_is_sorted.h
   __algorithm/ranges_is_sorted_until.h
   __algorithm/ranges_iterator_concept.h
   __algorithm/ranges_lexicographical_compare.h
   __algorithm/ranges_lower_bound.h
   __algorithm/ranges_make_heap.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h

libcxx/include/__algorithm/is_permutation.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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_IS_PERMUTATION_H
 #define _LIBCPP___ALGORITHM_IS_PERMUTATION_H
 
 #include <__algorithm/comp.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__iterator/concepts.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
+#include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
-               _BinaryPredicate __pred) {
-  //  shorten sequences as much as possible by lopping of any equal prefix
-  for (; __first1 != __last1; ++__first1, (void)++__first2)
-    if (!__pred(*__first1, *__first2))
-      break;
-  if (__first1 == __last1)
-    return true;
+template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class = void>
+struct _ConstTimeDistance : false_type {};
 
-  //  __first1 != __last1 && *__first1 != *__first2
-  typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
-  _D1 __l1 = _VSTD::distance(__first1, __last1);
-  if (__l1 == _D1(1))
-    return false;
-  _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
-  // For each element in [f1, l1) see if there are the same number of
-  //    equal elements in [f2, l2)
-  for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) {
+#if _LIBCPP_STD_VER > 17
+
+template <class _Iter1, class _Sent1, class _Iter2, class _Sent2>
+struct _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2, __enable_if_t<
+  sized_sentinel_for<_Sent1, _Iter1> &&
+  sized_sentinel_for<_Sent2, _Iter2>
+>> : true_type {};
+
+#else
+
+template <class _Iter1, class _Iter2>
+struct _ConstTimeDistance<_Iter1, _Iter1, _Iter2, _Iter2, __enable_if_t<
+    is_same<typename iterator_traits<_Iter1>::iterator_category, random_access_iterator_tag>::value &&
+    is_same<typename iterator_traits<_Iter2>::iterator_category, random_access_iterator_tag>::value
+> > : true_type {};
+
+#endif // _LIBCPP_STD_VER > 17
+
+// Internal functions
+
+// For each element in [f1, l1) see if there are the same number of equal elements in [f2, l2)
+template <class _AlgPolicy,
+          class _Iter1, class _Sent1, class _Iter2, class _Sent2,
+          class _Proj1, class _Proj2, class _Pred>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__is_permutation_impl(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+                      _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2) {
+  using _D1 = __iter_diff_t<_Iter1>;
+
+  for (auto __i = __first1; __i != __last1; ++__i) {
     //  Have we already counted the number of *__i in [f1, l1)?
-    _ForwardIterator1 __match = __first1;
-    for (; __match != __i; ++__match)
-      if (__pred(*__match, *__i))
+    auto __match = __first1;
+    for (; __match != __i; ++__match) {
+      if (std::__invoke(__pred, std::__invoke(__proj1, *__match), std::__invoke(__proj1, *__i)))
         break;
+    }
+
     if (__match == __i) {
       // Count number of *__i in [f2, l2)
       _D1 __c2 = 0;
-      for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
-        if (__pred(*__i, *__j))
+      for (auto __j = __first2; __j != __last2; ++__j) {
+        if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj2, *__j)))
           ++__c2;
+      }
       if (__c2 == 0)
         return false;
+
       // Count number of *__i in [__i, l1) (we can start with 1)
       _D1 __c1 = 1;
-      for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
-        if (__pred(*__i, *__j))
+      for (auto __j = _IterOps<_AlgPolicy>::next(__i); __j != __last1; ++__j) {
+        if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj1, *__j)))
           ++__c1;
+      }
       if (__c1 != __c2)
         return false;
     }
   }
+
   return true;
 }
 
-template <class _ForwardIterator1, class _ForwardIterator2>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) {
-  typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
-  typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
-  return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
+// 2+1 iterators, predicate. Not used by range algorithms.
+template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _BinaryPredicate>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__is_permutation(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2,
+                 _BinaryPredicate&& __pred) {
+  // Shorten sequences as much as possible by lopping of any equal prefix.
+  for (; __first1 != __last1; ++__first1, (void)++__first2) {
+    if (!__pred(*__first1, *__first2))
+      break;
   }
 
-#if _LIBCPP_STD_VER > 11
-template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
-                 _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) {
-  //  shorten sequences as much as possible by lopping of any equal prefix
-  for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2)
-    if (!__pred(*__first1, *__first2))
+  if (__first1 == __last1)
+    return true;
+
+  //  __first1 != __last1 && *__first1 != *__first2
+  using _D1 = __iter_diff_t<_ForwardIterator1>;
+  _D1 __l1 = _IterOps<_AlgPolicy>::distance(__first1, __last1);
+  if (__l1 == _D1(1))
+    return false;
+  auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __l1);
+
+  return std::__is_permutation_impl<_AlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+      __pred, __identity(), __identity());
+}
+
+// 2+2 iterators, predicate, non-constant time `distance`.
+template <class _AlgPolicy,
+          class _Iter1, class _Sent1, class _Iter2, class _Sent2,
+          class _Proj1, class _Proj2, class _Pred>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+                 _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2,
+                 /*_ConstTimeDistance=*/false_type) {
+  // Shorten sequences as much as possible by lopping of any equal prefix.
+  while (__first1 != __last1 && __first2 != __last2) {
+    if (!std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
       break;
+    ++__first1;
+    ++__first2;
+  }
+
   if (__first1 == __last1)
     return __first2 == __last2;
-  else if (__first2 == __last2)
+  if (__first2 == __last2) // Second range is shorter
     return false;
 
-  typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
-  _D1 __l1 = _VSTD::distance(__first1, __last1);
+  using _D1 = __iter_diff_t<_Iter1>;
+  _D1 __l1 = _IterOps<_AlgPolicy>::distance(__first1, __last1);
 
-  typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
-  _D2 __l2 = _VSTD::distance(__first2, __last2);
+  using _D2 = __iter_diff_t<_Iter2>;
+  _D2 __l2 = _IterOps<_AlgPolicy>::distance(__first2, __last2);
   if (__l1 != __l2)
     return false;
 
-  // For each element in [f1, l1) see if there are the same number of
-  //    equal elements in [f2, l2)
-  for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) {
-    //  Have we already counted the number of *__i in [f1, l1)?
-    _ForwardIterator1 __match = __first1;
-    for (; __match != __i; ++__match)
-      if (__pred(*__match, *__i))
-        break;
-    if (__match == __i) {
-      // Count number of *__i in [f2, l2)
-      _D1 __c2 = 0;
-      for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
-        if (__pred(*__i, *__j))
-          ++__c2;
-      if (__c2 == 0)
-        return false;
-      // Count number of *__i in [__i, l1) (we can start with 1)
-      _D1 __c1 = 1;
-      for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
-        if (__pred(*__i, *__j))
-          ++__c1;
-      if (__c1 != __c2)
-        return false;
-    }
-  }
-  return true;
+  return std::__is_permutation_impl<_AlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+      __pred, __proj1, __proj2);
+}
+
+// 2+2 iterators, predicate, specialization for constant-time `distance` call.
+template <class _AlgPolicy,
+          class _Iter1, class _Sent1, class _Iter2, class _Sent2,
+          class _Proj1, class _Proj2, class _Pred>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+                 _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2,
+                 /*_ConstTimeDistance=*/true_type) {
+  if (std::distance(__first1, __last1) != std::distance(__first2, __last2))
+    return false;
+  return std::__is_permutation<_AlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+      __pred, __proj1, __proj2,
+      /*_ConstTimeDistance=*/false_type());
+}
+
+// 2+2 iterators, predicate
+template <class _AlgPolicy,
+          class _Iter1, class _Sent1, class _Iter2, class _Sent2,
+          class _Proj1, class _Proj2, class _Pred>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__is_permutation(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+                 _Pred&& __pred, _Proj1&& __proj1, _Proj2&& __proj2) {
+  return std::__is_permutation<_AlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+      __pred, __proj1, __proj2,
+      _ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2>());
 }
 
-template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 bool __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
-                                                    _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
-                                                    _BinaryPredicate __pred, random_access_iterator_tag,
-                                                    random_access_iterator_tag) {
-  if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
-    return false;
-  return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
-                               _BinaryPredicate&>(__first1, __last1, __first2, __pred);
-}
+// Public interface
 
+// 2+1 iterators, predicate
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
-               _ForwardIterator2 __last2, _BinaryPredicate __pred) {
-  return _VSTD::__is_permutation<_BinaryPredicate&>(
-      __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(),
-      typename iterator_traits<_ForwardIterator2>::iterator_category());
+               _BinaryPredicate __pred) {
+  static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value,
+      "The predicate has to be callable");
+
+  return std::__is_permutation<_ClassicAlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2), __pred);
 }
 
+// 2+1 iterators
 template <class _ForwardIterator1, class _ForwardIterator2>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) {
+  using __v1 = __iter_value_type<_ForwardIterator1>;
+  using __v2 = __iter_value_type<_ForwardIterator2>;
+  return std::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
+}
+
+#if _LIBCPP_STD_VER > 11
+
+// 2+2 iterators
+template <class _ForwardIterator1, class _ForwardIterator2>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
                _ForwardIterator2 __last2) {
-  typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
-  typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
-  return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
-                                 typename iterator_traits<_ForwardIterator1>::iterator_category(),
-                                 typename iterator_traits<_ForwardIterator2>::iterator_category());
+  using __v1 = __iter_value_type<_ForwardIterator1>;
+  using __v2 = __iter_value_type<_ForwardIterator2>;
+
+  return std::__is_permutation<_ClassicAlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+      __equal_to<__v1, __v2>(), __identity(), __identity());
 }
-#endif
+
+// 2+2 iterators, predicate
+template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
+               _ForwardIterator2 __last2, _BinaryPredicate __pred) {
+  static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value,
+      "The predicate has to be callable");
+
+  return std::__is_permutation<_ClassicAlgPolicy>(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+      __pred, __identity(), __identity());
+}
+
+#endif // _LIBCPP_STD_VER > 11
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_PERMUTATION_H

libcxx/include/__algorithm/ranges_is_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_IS_PERMUTATION_H
+#define _LIBCPP___ALGORITHM_RANGES_IS_PERMUTATION_H
+
+#include <__algorithm/is_permutation.h>
+#include <__algorithm/iterator_operations.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/distance.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __is_permutation {
+struct __fn {
+
+  template <class _Iter1, class _Sent1, class _Iter2, class _Sent2,
+            class _Proj1, class _Proj2, class _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  bool __is_permutation_func_impl(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+                                  _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
+    return std::__is_permutation<_RangeAlgPolicy>(
+        std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+        __pred, __proj1, __proj2);
+  }
+
+  template <forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+            forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+            class _Proj1 = identity,
+            class _Proj2 = identity,
+            indirect_equivalence_relation<projected<_Iter1, _Proj1>,
+                                          projected<_Iter2, _Proj2>> _Pred = ranges::equal_to>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  bool operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+                  _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
+    return __is_permutation_func_impl(
+        std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+        __pred, __proj1, __proj2);
+  }
+
+  template <forward_range _Range1,
+            forward_range _Range2,
+            class _Proj1 = identity,
+            class _Proj2 = identity,
+            indirect_equivalence_relation<projected<iterator_t<_Range1>, _Proj1>, projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  bool operator()(_Range1&& __range1, _Range2&& __range2,
+                  _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
+    if constexpr (sized_range<_Range1> && sized_range<_Range2>) {
+      if (ranges::distance(__range1) != ranges::distance(__range2))
+        return false;
+    }
+
+    return __is_permutation_func_impl(
+        ranges::begin(__range1), ranges::end(__range1), ranges::begin(__range2), ranges::end(__range2),
+        __pred, __proj1, __proj2);
+  }
+};
+} // namespace __is_permutation
+
+inline namespace __cpo {
+  inline constexpr auto is_permutation = __is_permutation::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_IS_PERMUTATION_H

libcxx/include/__iterator/iterator_traits.h

using __iter_to_alloc_type = pair<
     typename iterator_traits<_InputIterator>::value_type::second_type>;
 
 template <class _Iter>
 using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category;
 
 template <class _Iter>
 using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;
 
+template <class _Iter>
+using __iter_diff_t = typename iterator_traits<_Iter>::difference_type;
+
+template<class _InputIterator>
+using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H

libcxx/include/algorithm

template<random_access_iterator I, sentinel_for<I> S, class Gen>
     I shuffle(I first, S last, Gen&& g);                                                           // Since C++20
 
   template<random_access_range R, class Gen>
     requires permutable<iterator_t<R>> &&
             uniform_random_bit_generator<remove_reference_t<Gen>>
     borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);                                                // Since C++20
 
   template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
+         sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
+         indirect_equivalence_relation<projected<I1, Proj1>,
+                                       projected<I2, Proj2>> Pred = ranges::equal_to>
+  constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
+                                        Pred pred = {},
+                                        Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20
+
+  template<forward_range R1, forward_range R2,
+         class Proj1 = identity, class Proj2 = identity,
+         indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>,
+                                       projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
+  constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
+                                        Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20
+
+  template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
            sentinel_for<I2> S2, class Pred = ranges::equal_to,
            class Proj1 = identity, class Proj2 = identity>
     requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
     constexpr subrange<I1>
       ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                      Proj1 proj1 = {}, Proj2 proj2 = {});                                           // since C++20
 
   template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,

 #include <__algorithm/ranges_copy_backward.h>
 #include <__algorithm/ranges_copy_if.h>
 #include <__algorithm/ranges_copy_n.h>
 #include <__algorithm/ranges_count.h>
 #include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_equal.h>
 #include <__algorithm/ranges_equal_range.h>
 #include <__algorithm/ranges_fill.h>
 #include <__algorithm/ranges_fill_n.h>
 #include <__algorithm/ranges_find.h>
 #include <__algorithm/ranges_find_end.h>
 #include <__algorithm/ranges_find_first_of.h>
 #include <__algorithm/ranges_find_if.h>
 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_for_each.h>
 #include <__algorithm/ranges_for_each_n.h>
 #include <__algorithm/ranges_generate.h>
 #include <__algorithm/ranges_generate_n.h>
 #include <__algorithm/ranges_includes.h>
 #include <__algorithm/ranges_inplace_merge.h>
 #include <__algorithm/ranges_is_heap.h>
 #include <__algorithm/ranges_is_heap_until.h>
 #include <__algorithm/ranges_is_partitioned.h>
+#include <__algorithm/ranges_is_permutation.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_make_heap.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_merge.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_for_each_n               { private header "__algorithm/ranges_for_each_n.h" }
       module ranges_generate                 { private header "__algorithm/ranges_generate.h" }
       module ranges_generate_n               { private header "__algorithm/ranges_generate_n.h" }
       module ranges_includes                 { private header "__algorithm/ranges_includes.h" }
       module ranges_inplace_merge            { private header "__algorithm/ranges_inplace_merge.h" }
       module ranges_is_heap                  { private header "__algorithm/ranges_is_heap.h" }
       module ranges_is_heap_until            { private header "__algorithm/ranges_is_heap_until.h" }
       module ranges_is_partitioned           { private header "__algorithm/ranges_is_partitioned.h" }
+      module ranges_is_permutation           { private header "__algorithm/ranges_is_permutation.h" }
       module ranges_is_sorted                { private header "__algorithm/ranges_is_sorted.h" }
       module ranges_is_sorted_until          { private header "__algorithm/ranges_is_sorted_until.h" }
       module ranges_iterator_concept         { private header "__algorithm/ranges_iterator_concept.h" }
       module ranges_lexicographical_compare  { private header "__algorithm/ranges_lexicographical_compare.h" }
       module ranges_lower_bound              { private header "__algorithm/ranges_lower_bound.h" }
       module ranges_make_heap                { private header "__algorithm/ranges_make_heap.h" }
       module ranges_max                      { private header "__algorithm/ranges_max.h" }
       module ranges_max_element              { private header "__algorithm/ranges_max_element.h" }

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

#endif
     (void)std::ranges::includes(first, last, first2, last2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::includes(a, b, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap_until(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap_until(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(a, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::is_permutation(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::is_permutation(a, b, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::is_permutation(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::is_permutation(a, b, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted_until(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted_until(a, Less(&copies)); assert(copies == 0);
     if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(&copies)); assert(copies == 0); }
     if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(&copies)); assert(copies == 0); }
     (void)std::ranges::lexicographical_compare(first, last, first2, last2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::lexicographical_compare(a, b, Less(&copies)); assert(copies == 0);

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

#endif
     (void)std::ranges::includes(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::includes(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap_until(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_heap_until(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::is_permutation(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::is_permutation(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::is_permutation(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::is_permutation(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted_until(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted_until(a, Less(), Proj(&copies)); assert(copies == 0);
     if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); }
     if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(), Proj(&copies)); assert(copies == 0); }
     (void)std::ranges::lexicographical_compare(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::lexicographical_compare(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}}
 #include <__algorithm/ranges_generate.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_generate.h'}}
 #include <__algorithm/ranges_generate_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_generate_n.h'}}
 #include <__algorithm/ranges_includes.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_includes.h'}}
 #include <__algorithm/ranges_inplace_merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_inplace_merge.h'}}
 #include <__algorithm/ranges_is_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_heap.h'}}
 #include <__algorithm/ranges_is_heap_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_heap_until.h'}}
 #include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}}
+#include <__algorithm/ranges_is_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_permutation.h'}}
 #include <__algorithm/ranges_is_sorted.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted.h'}}
 #include <__algorithm/ranges_is_sorted_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted_until.h'}}
 #include <__algorithm/ranges_iterator_concept.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_iterator_concept.h'}}
 #include <__algorithm/ranges_lexicographical_compare.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lexicographical_compare.h'}}
 #include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}}
 #include <__algorithm/ranges_make_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_make_heap.h'}}
 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}

libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
+//        sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
+//        indirect_equivalence_relation<projected<I1, Proj1>,
+//                                      projected<I2, Proj2>> Pred = ranges::equal_to>
+// constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
+//                                       Pred pred = {},
+//                                       Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20
+//
+// template<forward_range R1, forward_range R2,
+//        class Proj1 = identity, class Proj2 = identity,
+//        indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>,
+//                                      projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
+// constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
+//                                       Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <list>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "counting_predicates.h"
+#include "counting_projection.h"
+#include "test_iterators.h"
+
+template <class Iter1, class Sent1 = int*, class Iter2 = int*, class Sent2 = int*>
+concept HasIsPermutationIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
+  std::ranges::is_permutation(first1, last1, first2, last2);
+};
+
+template <class Range1, class Range2 = UncheckedRange<int*>>
+concept HasIsPermutationR = requires(Range1 range1, Range2 range2) {
+  std::ranges::is_permutation(range1, range2);
+};
+
+static_assert(HasIsPermutationIt<int*>);
+static_assert(!HasIsPermutationIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasIsPermutationIt<ForwardIteratorNotIncrementable>);
+static_assert(!HasIsPermutationIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasIsPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotDerivedFrom>);
+static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotIncrementable>);
+static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
+// !indirect_equivalence_relation<Pred, projected<I1, Proj1>, projected<I2, Proj2>>;
+static_assert(!HasIsPermutationIt<int*, int*, int**, int**>);
+
+static_assert(HasIsPermutationR<UncheckedRange<int*>>);
+static_assert(!HasIsPermutationR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasIsPermutationR<ForwardRangeNotIncrementable>);
+static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
+static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
+static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
+// !indirect_equivalence_relation<Pred, projected<iterator_t<I1>, Proj1>, projected<iterator_t<I2>, Proj2>>;
+static_assert(!HasIsPermutationIt<UncheckedRange<int*>, UncheckedRange<int**>>);
+
+template <int N, int M>
+struct Data {
+  std::array<int, N> input1;
+  std::array<int, M> input2;
+  bool expected;
+};
+
+template <class Iter1, class Sent1, class Iter2, class Sent2, int N, int M>
+constexpr void test(Data<N, M> d) {
+  {
+    std::same_as<bool> decltype(auto) ret = std::ranges::is_permutation(Iter1(d.input1.data()),
+                                                                        Sent1(Iter1(d.input1.data() + N)),
+                                                                        Iter1(d.input2.data()),
+                                                                        Sent1(Iter1(d.input2.data() + M)));
+    assert(ret == d.expected);
+  }
+  {
+    auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + N)));
+    auto range2 = std::ranges::subrange(Iter1(d.input2.data()), Sent1(Iter1(d.input2.data() + M)));
+    std::same_as<bool> decltype(auto) ret = std::ranges::is_permutation(range1, range2);
+    assert(ret == d.expected);
+  }
+}
+
+template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
+constexpr void test_iterators() {
+  // Ranges are identical.
+  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2, 3, 4}, .input2 = {1, 2, 3, 4}, .expected = true});
+
+  // Ranges are reversed.
+  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2, 3, 4}, .input2 = {4, 3, 2, 1}, .expected = true});
+
+  // Two elements are swapped.
+  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {4, 2, 3, 1}, .input2 = {1, 2, 3, 4}, .expected = true});
+
+  // The first range is shorter.
+  test<Iter1, Sent1, Iter2, Sent2, 4, 5>({.input1 = {4, 2, 3, 1}, .input2 = {4, 3, 2, 1, 5}, .expected = false});
+
+  // The first range is longer.
+  test<Iter1, Sent1, Iter2, Sent2, 5, 4>({.input1 = {4, 2, 3, 1, 5}, .input2 = {4, 3, 2, 1}, .expected = false});
+
+  // The first range is empty.
+  test<Iter1, Sent1, Iter2, Sent2, 0, 4>({.input1 = {}, .input2 = {4, 3, 2, 1}, .expected = false});
+
+  // The second range is empty.
+  test<Iter1, Sent1, Iter2, Sent2, 5, 0>({.input1 = {4, 2, 3, 1, 5}, .input2 = {}, .expected = false});
+
+  // Both ranges are empty.
+  test<Iter1, Sent1, Iter2, Sent2, 0, 0>({.input1 = {}, .input2 = {}, .expected = true});
+
+  // 1-element range, same value.
+  test<Iter1, Sent1, Iter2, Sent2, 1, 1>({.input1 = {1}, .input2 = {1}, .expected = true});
+
+  // 1-element range, different values.
+  test<Iter1, Sent1, Iter2, Sent2, 1, 1>({.input1 = {1}, .input2 = {2}, .expected = false});
+}
+
+template <class Iter1, class Sent1 = Iter1>
+constexpr void test_iterators1() {
+  test_iterators<Iter1, Sent1, forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, forward_iterator<int*>>();
+  test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
+  test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
+  test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
+  test_iterators<Iter1, Sent1, int*>();
+  test_iterators<Iter1, Sent1, const int*>();
+}
+
+constexpr bool test() {
+  test_iterators1<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
+  test_iterators1<forward_iterator<int*>>();
+  test_iterators1<bidirectional_iterator<int*>>();
+  test_iterators1<random_access_iterator<int*>>();
+  test_iterators1<contiguous_iterator<int*>>();
+  test_iterators1<int*>();
+  test_iterators1<const int*>();
+
+  { // A custom comparator works.
+    struct A {
+      int a;
+      constexpr bool pred(const A& rhs) const { return a == rhs.a; }
+    };
+
+    std::array in1 = {A{2}, A{3}, A{1}};
+    std::array in2 = {A{1}, A{2}, A{3}};
+
+    {
+      auto ret = std::ranges::is_permutation(in1.begin(), in1.end(), in2.begin(), in2.end(), &A::pred);
+      assert(ret);
+    }
+
+    {
+      auto ret = std::ranges::is_permutation(in1, in2, &A::pred);
+      assert(ret);
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+
+      constexpr bool operator==(const A&) const = default;
+
+      constexpr A x2() const { return A{a * 2}; }
+      constexpr A div2() const { return A{a / 2}; }
+    };
+
+    std::array in1 = {A{1}, A{2}, A{3}};  // [2, 4, 6] after applying `x2`.
+    std::array in2 = {A{4}, A{8}, A{12}}; // [2, 4, 6] after applying `div2`.
+
+    {
+      auto ret = std::ranges::is_permutation(
+          in1.begin(), in1.end(), in2.begin(), in2.end(), {}, &A::x2, &A::div2);
+      assert(ret);
+    }
+
+    {
+      auto ret = std::ranges::is_permutation(in1, in2, {}, &A::x2, &A::div2);
+      assert(ret);
+    }
+  }
+
+
+  { // Check that complexity requirements are met.
+    int predCount = 0;
+    int proj1Count = 0;
+    int proj2Count = 0;
+    auto reset_counters = [&] {
+      predCount = proj1Count = proj2Count = 0;
+    };
+
+    counting_predicate pred(std::ranges::equal_to{}, predCount);
+    counting_projection<> proj1(proj1Count);
+    counting_projection<> proj2(proj2Count);
+
+    {
+      // 1. No applications of the corresponding predicate if `ForwardIterator1` and `ForwardIterator2` meet the
+      //    requirements of random access iterators and `last1 - first1 != last2 - first2`.
+      int a[] = {1, 2, 3, 4, 5};
+      int b[] = {1, 2, 3, 4};
+      // Make sure that the iterators have different types.
+      auto b_begin = random_access_iterator<int*>(std::begin(b));
+      auto b_end = random_access_iterator<int*>(std::end(b));
+
+      {
+        auto ret = std::ranges::is_permutation(a, a + 5, b_begin, b_end, pred, proj1, proj2);
+        assert(!ret);
+
+        assert(predCount == 0);
+        assert(proj1Count == 0);
+        assert(proj2Count == 0);
+        reset_counters();
+      }
+
+      {
+        auto ret = std::ranges::is_permutation(a, std::ranges::subrange(b_begin, b_end), pred, proj1, proj2);
+        assert(!ret);
+
+        assert(predCount == 0);
+        assert(proj1Count == 0);
+        assert(proj2Count == 0);
+        reset_counters();
+      }
+    }
+
+    // 2. Otherwise, exactly last1 - first1 applications of the corresponding predicate if
+    // `equal(first1, last1, first2, last2, pred)` would return true.
+    {
+      int a[] = {1, 2, 3, 4, 5};
+      int b[] = {1, 2, 3, 4, 5};
+      int expected = 5;
+
+      {
+        auto ret = std::ranges::is_permutation(a, a + 5, b, b + 5, pred, proj1, proj2);
+        assert(ret);
+
+        assert(predCount == expected);
+        assert(proj1Count == expected);
+        assert(proj2Count == expected);
+        reset_counters();
+      }
+
+      {
+        auto ret = std::ranges::is_permutation(a, b, pred, proj1, proj2);
+        assert(ret);
+
+        assert(predCount == expected);
+        assert(proj1Count == expected);
+        assert(proj2Count == expected);
+        reset_counters();
+      }
+    }
+
+    // Note: we currently don't have the setup to test big-O complexity, but copying the requirement for completeness'
+    // sake.
+    // 3. Otherwise, at worst `O(N^2)`, where `N` has the value `last1 - first1`.
+  }
+
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp

 
 #include <algorithm>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 #include "MoveOnly.h"
 
+const int LargeN = 128;
+
 template<int N, class T, class Iter>
 TEST_CONSTEXPR_CXX20 bool test()
 {
     int orig[N] = {};
     unsigned x = 1;
     for (int i=0; i < N; ++i) {
         x = (x * 1664525) + 1013904223;
         orig[i] = x % 1000;
TEST_CONSTEXPR_CXX20 bool test_pointers()
 
     return true;
 }
 
 int main(int, char**)
 {
     test<7, int, int*>();
     test<7, int, random_access_iterator<int*> >();
-    test<257, int, int*>();
-    test<257, int, random_access_iterator<int*> >();
+    test<LargeN, int, int*>();
+    test<LargeN, int, random_access_iterator<int*> >();
 
 #if TEST_STD_VER >= 11
     test<7, MoveOnly, MoveOnly*>();
     test<7, MoveOnly, random_access_iterator<MoveOnly*> >();
-    test<257, MoveOnly, MoveOnly*>();
-    test<257, MoveOnly, random_access_iterator<MoveOnly*> >();
+    test<LargeN, MoveOnly, MoveOnly*>();
+    test<LargeN, MoveOnly, random_access_iterator<MoveOnly*> >();
 #endif
 
     test_pointers<17, char, char**>();
     test_pointers<17, char, random_access_iterator<char**> >();
     test_pointers<17, const char, const char**>();
     test_pointers<17, const char, random_access_iterator<const char**> >();
     test_pointers<17, int, int**>();
     test_pointers<17, int, random_access_iterator<int**> >();
 
 #if TEST_STD_VER >= 20
     test<7, int, contiguous_iterator<int*>>();
-    test<257, int, contiguous_iterator<int*>>();
+    test<LargeN, int, contiguous_iterator<int*>>();
     test<7, MoveOnly, contiguous_iterator<MoveOnly*>>();
-    test<257, MoveOnly, contiguous_iterator<MoveOnly*>>();
+    test<LargeN, MoveOnly, contiguous_iterator<MoveOnly*>>();
     test_pointers<17, char, contiguous_iterator<char**>>();
     test_pointers<17, const char, contiguous_iterator<const char**>>();
     test_pointers<17, int, contiguous_iterator<int**>>();
 
     static_assert(test<7, int, int*>());
     static_assert(test<7, int, random_access_iterator<int*>>());
     static_assert(test<7, int, contiguous_iterator<int*>>());
-    static_assert(test<257, int, int*>());
-    static_assert(test<257, int, random_access_iterator<int*>>());
-    static_assert(test<257, int, contiguous_iterator<int*>>());
+    static_assert(test<LargeN, int, int*>());
+    static_assert(test<LargeN, int, random_access_iterator<int*>>());
+    static_assert(test<LargeN, int, contiguous_iterator<int*>>());
 
     static_assert(test<7, MoveOnly, MoveOnly*>());
     static_assert(test<7, MoveOnly, random_access_iterator<MoveOnly*>>());
     static_assert(test<7, MoveOnly, contiguous_iterator<MoveOnly*>>());
-    static_assert(test<257, MoveOnly, MoveOnly*>());
-    static_assert(test<257, MoveOnly, random_access_iterator<MoveOnly*>>());
-    static_assert(test<257, MoveOnly, contiguous_iterator<MoveOnly*>>());
+    static_assert(test<LargeN, MoveOnly, MoveOnly*>());
+    static_assert(test<LargeN, MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<LargeN, MoveOnly, contiguous_iterator<MoveOnly*>>());
 
     static_assert(test_pointers<17, char, char**>());
     static_assert(test_pointers<17, char, random_access_iterator<char**>>());
     static_assert(test_pointers<17, char, contiguous_iterator<char**>>());
     static_assert(test_pointers<17, const char, const char**>());
     static_assert(test_pointers<17, const char, random_access_iterator<const char**>>());
     static_assert(test_pointers<17, const char, contiguous_iterator<const char**>>());
     static_assert(test_pointers<17, int, int**>());
     static_assert(test_pointers<17, int, random_access_iterator<int**>>());
     static_assert(test_pointers<17, int, contiguous_iterator<int**>>());
 #endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp

 #include <algorithm>
 #include <cassert>
 #include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 #include "MoveOnly.h"
 
+const int LargeN = 128;
+
 template<int N, class T, class Iter>
 TEST_CONSTEXPR_CXX20 bool test()
 {
     int orig[N] = {};
     unsigned x = 1;
     for (int i=0; i < N; ++i) {
         x = (x * 1664525) + 1013904223;
         orig[i] = x % 1000;
TEST_CONSTEXPR_CXX20 bool test_pointers()
 
     return true;
 }
 
 int main(int, char**)
 {
     test<7, int, int*>();
     test<7, int, random_access_iterator<int*> >();
-    test<257, int, int*>();
-    test<257, int, random_access_iterator<int*> >();
+    test<LargeN, int, int*>();
+    test<LargeN, int, random_access_iterator<int*> >();
 
 #if TEST_STD_VER >= 11
     test<7, MoveOnly, MoveOnly*>();
     test<7, MoveOnly, random_access_iterator<MoveOnly*> >();
-    test<257, MoveOnly, MoveOnly*>();
-    test<257, MoveOnly, random_access_iterator<MoveOnly*> >();
+    test<LargeN, MoveOnly, MoveOnly*>();
+    test<LargeN, MoveOnly, random_access_iterator<MoveOnly*> >();
 #endif
 
     test_pointers<17, char, char**>();
     test_pointers<17, char, random_access_iterator<char**> >();
     test_pointers<17, const char, const char**>();
     test_pointers<17, const char, random_access_iterator<const char**> >();
     test_pointers<17, int, int**>();
     test_pointers<17, int, random_access_iterator<int**> >();
 
 #if TEST_STD_VER >= 20
     test<7, int, contiguous_iterator<int*>>();
-    test<257, int, contiguous_iterator<int*>>();
+    test<LargeN, int, contiguous_iterator<int*>>();
     test<7, MoveOnly, contiguous_iterator<MoveOnly*>>();
-    test<257, MoveOnly, contiguous_iterator<MoveOnly*>>();
+    test<LargeN, MoveOnly, contiguous_iterator<MoveOnly*>>();
     test_pointers<17, char, contiguous_iterator<char**>>();
     test_pointers<17, const char, contiguous_iterator<const char**>>();
     test_pointers<17, int, contiguous_iterator<int**>>();
 
     static_assert(test<7, int, int*>());
     static_assert(test<7, int, random_access_iterator<int*>>());
     static_assert(test<7, int, contiguous_iterator<int*>>());
-    static_assert(test<257, int, int*>());
-    static_assert(test<257, int, random_access_iterator<int*>>());
-    static_assert(test<257, int, contiguous_iterator<int*>>());
+    static_assert(test<LargeN, int, int*>());
+    static_assert(test<LargeN, int, random_access_iterator<int*>>());
+    static_assert(test<LargeN, int, contiguous_iterator<int*>>());
 
     static_assert(test<7, MoveOnly, MoveOnly*>());
     static_assert(test<7, MoveOnly, random_access_iterator<MoveOnly*>>());
     static_assert(test<7, MoveOnly, contiguous_iterator<MoveOnly*>>());
-    static_assert(test<257, MoveOnly, MoveOnly*>());
-    static_assert(test<257, MoveOnly, random_access_iterator<MoveOnly*>>());
-    static_assert(test<257, MoveOnly, contiguous_iterator<MoveOnly*>>());
+    static_assert(test<LargeN, MoveOnly, MoveOnly*>());
+    static_assert(test<LargeN, MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<LargeN, MoveOnly, contiguous_iterator<MoveOnly*>>());
 
     static_assert(test_pointers<17, char, char**>());
     static_assert(test_pointers<17, char, random_access_iterator<char**>>());
     static_assert(test_pointers<17, char, contiguous_iterator<char**>>());
     static_assert(test_pointers<17, const char, const char**>());
     static_assert(test_pointers<17, const char, random_access_iterator<const char**>>());
     static_assert(test_pointers<17, const char, contiguous_iterator<const char**>>());
     static_assert(test_pointers<17, int, int**>());
     static_assert(test_pointers<17, int, random_access_iterator<int**>>());
     static_assert(test_pointers<17, int, contiguous_iterator<int**>>());
 #endif
 
     return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp

constexpr bool test_all() {
   std::ranges::equal_to eq;
   std::ranges::less less;
   auto sum = [](int lhs, A rhs) { return lhs + rhs.x; };
   auto proj1 = [](int x) { return x * -1; };
   auto proj2 = [](A a) { return a.x * -1; };
 
   test(std::ranges::equal, in, in2, eq, proj1, proj2);
   test(std::ranges::lexicographical_compare, in, in2, eq, proj1, proj2);
-  //test(std::ranges::is_permutation, in, in2, eq, proj1, proj2);
+  test(std::ranges::is_permutation, in, in2, eq, proj1, proj2);
   test(std::ranges::includes, in, in2, less, proj1, proj2);
   test(std::ranges::find_first_of, in, in2, eq, proj1, proj2);
   test(std::ranges::mismatch, in, in2, eq, proj1, proj2);
   test(std::ranges::search, in, in2, eq, proj1, proj2);
   test(std::ranges::find_end, in, in2, eq, proj1, proj2);
   test(std::ranges::transform, in, in2, out, sum, proj1, proj2);
   test(std::ranges::transform, in, in2, out2, sum, proj1, proj2);
   test(std::ranges::partial_sort_copy, in, in2, less, proj1, proj2);

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

constexpr bool test_all() {
   test(std::ranges::find_end, in, in2, binary_pred);
   test(std::ranges::is_partitioned, in, unary_pred);
   test(std::ranges::is_sorted, in, binary_pred);
   test(std::ranges::is_sorted_until, in, binary_pred);
   test(std::ranges::includes, in, in2, binary_pred);
   test(std::ranges::is_heap, in, binary_pred);
   test(std::ranges::is_heap_until, in, binary_pred);
   std::ranges::clamp(2, 1, 3, binary_pred);
-  //test(std::ranges::is_permutation, in, in2, binary_pred);
+  test(std::ranges::is_permutation, in, in2, binary_pred);
   test(std::ranges::copy_if, in, out, unary_pred);
   test(std::ranges::remove_copy_if, in, out, unary_pred);
   test(std::ranges::replace_if, in, unary_pred, x);
   test(std::ranges::replace_copy_if, in, out, unary_pred, x);
   test(std::ranges::unique_copy, in, out, binary_pred);
   test(std::ranges::partition_copy, in, out, out2, unary_pred);
   test(std::ranges::partial_sort_copy, in, in2, binary_pred);
   test(std::ranges::merge, in, in2, out, binary_pred);

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

constexpr bool test_all() {
   test(std::ranges::find_end, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::is_partitioned, in, &Foo::unary_pred, &Bar::val);
   test(std::ranges::is_sorted, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::is_sorted_until, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val);
   std::ranges::clamp(b, a, c, &Foo::binary_pred, &Bar::val);
-  //test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val);
   std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val);
   // `copy`, `copy_n` and `copy_backward` have neither a projection nor a predicate.
   test(std::ranges::copy_if, in, out, &Foo::unary_pred, &Bar::val);
   // `move` and `move_backward` have neither a projection nor a predicate.
   // `fill` and `fill_n` have neither a projection nor a predicate.
   {
     std::array out_transform = {false, true, true};

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

constexpr void run_tests() {
   test(std::ranges::search_n, in, count, x);
   test(std::ranges::find_end, in, in2);
   test(std::ranges::is_partitioned, in, unary_pred);
   test(std::ranges::is_sorted, in);
   test(std::ranges::is_sorted_until, in);
   test(std::ranges::includes, in, in2);
   test(std::ranges::is_heap, in);
   test(std::ranges::is_heap_until, in);
-  //test(std::ranges::is_permutation, in, in2);
+  test(std::ranges::is_permutation, in, in2);
   test(std::ranges::for_each, in, std::identity{});
   std::ranges::for_each_n(in.begin(), count, std::identity{});
   if constexpr (std::copyable<T>) {
     test(std::ranges::copy, in, out);
     std::ranges::copy_n(in.begin(), count, out);
     test(std::ranges::copy_if, in, out, unary_pred);
     test(std::ranges::copy_backward, in, out_end);
   }

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

 static_assert(test(std::ranges::for_each_n, a, 10, odd));
 static_assert(test(std::ranges::generate, a, gen));
 static_assert(test(std::ranges::generate_n, a, 10, gen));
 static_assert(test(std::ranges::includes, a, a));
 static_assert(test(std::ranges::inplace_merge, a, a+5));
 static_assert(test(std::ranges::is_heap, a));
 static_assert(test(std::ranges::is_heap_until, a));
 static_assert(test(std::ranges::is_partitioned, a, odd));
-//static_assert(test(std::ranges::is_permutation, a, a));
+static_assert(test(std::ranges::is_permutation, a, a));
 static_assert(test(std::ranges::is_sorted, a));
 static_assert(test(std::ranges::is_sorted_until, a));
 static_assert(test(std::ranges::lexicographical_compare, a, a));
 static_assert(test(std::ranges::lower_bound, a, 42));
 static_assert(test(std::ranges::make_heap, a));
 static_assert(test(std::ranges::max, a));
 static_assert(test(std::ranges::max_element, a));
 static_assert(test(std::ranges::merge, a, a, a));