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

Co-authored-by: Konstantin Varlamov <varconst@apple.com>

Differential Revision: https://reviews.llvm.org/D127194

18 files changed, 601 insertions, 125 deletions

diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv
index 6982f1e35715..642989677c9d 100644
--- a/libcxx/docs/Status/RangesAlgorithms.csv
+++ b/libcxx/docs/Status/RangesAlgorithms.csv
@@ -33,7 +33,7 @@ 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>`_,✅
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 7ce9b66db5ca..f7c2d99e78b0 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -97,6 +97,7 @@ set(files
   __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
diff --git a/libcxx/include/__algorithm/is_permutation.h b/libcxx/include/__algorithm/is_permutation.h
index cdd742048412..06a4949e21b5 100644
--- a/libcxx/include/__algorithm/is_permutation.h
+++ b/libcxx/include/__algorithm/is_permutation.h
@@ -11,10 +11,16 @@
 #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
@@ -22,140 +28,211 @@
 
 _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 (__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());
 }
 
-#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))
+// 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);
 }
 
-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))
+// 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 _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
-                               _BinaryPredicate&>(__first1, __last1, __first2, __pred);
+  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>());
 }
 
+// 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_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_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,
                _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
 
diff --git a/libcxx/include/__algorithm/ranges_is_permutation.h b/libcxx/include/__algorithm/ranges_is_permutation.h
new file mode 100644
index 000000000000..41e302fe99dc
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_is_permutation.h
@@ -0,0 +1,89 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h
index 254f8c2339e4..5600a2b2f526 100644
--- a/libcxx/include/__iterator/iterator_traits.h
+++ b/libcxx/include/__iterator/iterator_traits.h
@@ -507,6 +507,12 @@ using __iterator_category_type = typename iterator_traits<_Iter>::iterator_categ
 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
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index bf8a9846440c..69ada038747c 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -793,6 +793,21 @@ namespace ranges {
     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>
@@ -1794,6 +1809,7 @@ template <class BidirectionalIterator, class Compare>
 #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>
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index 0b33ffd933d7..204fe408b1e7 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -336,6 +336,7 @@ module std [system] {
       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" }
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
index 1582981b935f..419e2eb412cc 100644
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
@@ -132,8 +132,8 @@ constexpr bool all_the_algorithms()
     (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);
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
index 074df6eca7fc..c0295b81f879 100644
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
@@ -115,8 +115,8 @@ constexpr bool all_the_algorithms()
     (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);
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
index 49fce411e734..a6a07f49e7f3 100644
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -134,6 +134,7 @@ END-SCRIPT
 #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'}}
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp
new file mode 100644
index 000000000000..14bc747d0cc7
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp
@@ -0,0 +1,281 @@
+//===----------------------------------------------------------------------===//
+//
+// 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;
+}
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp
index d719f002351d..afe199da1c1a 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.pass.cpp
@@ -21,6 +21,8 @@
 #include "test_iterators.h"
 #include "MoveOnly.h"
 
+const int LargeN = 128;
+
 template<int N, class T, class Iter>
 TEST_CONSTEXPR_CXX20 bool test()
 {
@@ -61,14 +63,14 @@ 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**>();
@@ -80,9 +82,9 @@ int main(int, char**)
 
 #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**>>();
@@ -90,16 +92,16 @@ int main(int, char**)
     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**>>());
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp
index bfdefedb7f34..134830fe5411 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_comp.pass.cpp
@@ -22,6 +22,8 @@
 #include "test_iterators.h"
 #include "MoveOnly.h"
 
+const int LargeN = 128;
+
 template<int N, class T, class Iter>
 TEST_CONSTEXPR_CXX20 bool test()
 {
@@ -62,14 +64,14 @@ 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**>();
@@ -81,9 +83,9 @@ int main(int, char**)
 
 #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**>>();
@@ -91,16 +93,16 @@ int main(int, char**)
     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**>>());
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp
index 5293fab120f6..00a0b635b21a 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp
@@ -56,7 +56,7 @@ constexpr bool test_all() {
 
   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);
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp
index 114a099c192b..367059bb3556 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp
@@ -110,7 +110,7 @@ constexpr bool test_all() {
   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);
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
index 787c92f9cbd5..80416b0249e9 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
@@ -117,7 +117,7 @@ constexpr bool test_all() {
   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.
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
index 709913d8af0f..5517e7b221bc 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
@@ -104,7 +104,7 @@ constexpr void run_tests() {
   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>) {
diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
index 2be8a7ec333d..9e5398bf1612 100644
--- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
+++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
@@ -91,7 +91,7 @@ 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));