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

[var-const]

libcxx/docs/Status/RangesAlgorithms.csv

36

Missing link.

libcxx/include/__algorithm/is_permutation.h

99

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

172

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

libcxx/include/__algorithm/ranges_is_permutation.h

26

Please add the language version/no incomplete ranges guard.

44

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

54

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

59

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

libcxx/include/algorithm

1121

Missing synopsis.

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

8

Missing synopsis.

87

Please also check with a single-element range.

95

Nit: there's an unnecessary blank line.

109

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

190

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

99

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

149

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

48

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

73

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

82

Here and elsewhere.

83–89

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.

166–172

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

48

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.

83–89

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

166–172

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,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,Under review
 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_unitl,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,includes,Not assigned,n/a,Not started
 Read-only,is_heap,Not assigned,n/a,Not started
 Read-only,is_heap_until,Not assigned,n/a,Not started
 Read-only,clamp,Nikolas Klauser,`D126193 <https://llvm.org/D126193>`_,Under review
-Read-only,is_permutation,Not assigned,n/a,Not started
+Read-only,is_permutation,Nikolas Klauser,` <https://llvm.org/>`_,✅
 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>`_,Under review
 Write,move_backward,Nikolas Klauser,`D126616 <https://llvm.org/D126616>`_,Under review

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_fill_n.h
   __algorithm/ranges_find.h
   __algorithm/ranges_find_first_of.h
   __algorithm/ranges_find_if.h
   __algorithm/ranges_find_if_not.h
   __algorithm/ranges_for_each.h
   __algorithm/ranges_for_each_n.h
   __algorithm/ranges_is_partitioned.h
+  __algorithm/ranges_is_permutation.h
   __algorithm/ranges_is_sorted.h
   __algorithm/ranges_is_sorted_until.h
   __algorithm/ranges_lower_bound.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.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 <__config>
+#include <__iterator/concepts.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.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)
+  for (; __first1 != __last1; ++__first1, (void)++__first2) {
     if (!__pred(*__first1, *__first2))
       break;
+  }
+
   if (__first1 == __last1)
     return true;
 
   //  __first1 != __last1 && *__first1 != *__first2
-  typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
-  _D1 __l1 = _VSTD::distance(__first1, __last1);
+  using _D1 = __iter_diff_t<_ForwardIterator1>;
+  _D1 __l1 = std::distance(__first1, __last1);
   if (__l1 == _D1(1))
     return false;
-  _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
+  auto __last2 = std::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) {
+  for (auto __i = __first1; __i != __last1; ++__i) {
     //  Have we already counted the number of *__i in [f1, l1)?
-    _ForwardIterator1 __match = __first1;
+    auto __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)
+      for (auto __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)
+      for (auto __j = std::next(__i); __j != __last1; ++__j)
         if (__pred(*__i, *__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>());
+  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
-template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
+template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Proj1, class _Proj2, class _Pred>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
-                 _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) {
+__is_permutation(_Iter1 __first1, _Sent1 __last1,
+                 _Iter2 __first2, _Sent2 __last2,
+                 _Pred& __pred,
+                 _Proj1& __proj1,
+                 _Proj2& __proj2) {
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+  if constexpr (sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>) {
+    if (__last1 - __first1 != __last2 - __first2)
+      return false;
+  }
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
   //  shorten sequences as much as possible by lopping of any equal prefix
-  for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2)
-    if (!__pred(*__first1, *__first2))
+  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)
     return false;
 
-  typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
-  _D1 __l1 = _VSTD::distance(__first1, __last1);
+  using _D1 = __iter_diff_t<_Iter1>;
+  _D1 __l1 = std::__ranges_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 = std::__ranges_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) {
+  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 = std::next(__i); __j != __last1; ++__j)
+        if (std::__invoke(__pred, std::__invoke(__proj1, *__i), std::__invoke(__proj2, *__j)))
           ++__c1;
       if (__c1 != __c2)
         return false;
     }
   }
   return true;
 }
 
 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))
+  if (std::distance(__first1, __last1) != std::distance(__first2, __last2))
     return false;
-  return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
+  return std::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
                                _BinaryPredicate&>(__first1, __last1, __first2, __pred);
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _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());
 }
 
 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,
                _ForwardIterator2 __last2) {
-  typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
-  typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
+  typedef __iter_value_type<_ForwardIterator1> __v1;
+  typedef __iter_value_type<_ForwardIterator2> __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());
 }
 #endif
 
 _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 <__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>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __is_permutation {
+struct __fn {
+
+  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 std::__is_permutation(__first1, __last1, __first2, __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 std::__is_permutation(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___ALGORITHM_RANGES_IS_PERMUTATION_H

libcxx/include/__iterator/iterator_traits.h

 template<class _InputIterator>
 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
 
 template<class _InputIterator>
 using __iter_to_alloc_type = pair<
     typename add_const<typename iterator_traits<_InputIterator>::value_type::first_type>::type,
     typename iterator_traits<_InputIterator>::value_type::second_type>;
 
+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

 #include <__algorithm/ranges_copy.h>
 #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_fill.h>
 #include <__algorithm/ranges_fill_n.h>
 #include <__algorithm/ranges_find.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_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_lower_bound.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>

libcxx/include/module.modulemap

module __algorithm {
       module ranges_fill_n            { private header "__algorithm/ranges_fill_n.h" }
       module ranges_find              { private header "__algorithm/ranges_find.h" }
       module ranges_find_first_of     { private header "__algorithm/ranges_find_first_of.h" }
       module ranges_find_if           { private header "__algorithm/ranges_find_if.h" }
       module ranges_find_if_not       { private header "__algorithm/ranges_find_if_not.h" }
       module ranges_for_each          { private header "__algorithm/ranges_for_each.h" }
       module ranges_for_each_n        { private header "__algorithm/ranges_for_each_n.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_lower_bound       { private header "__algorithm/ranges_lower_bound.h" }
       module ranges_max               { private header "__algorithm/ranges_max.h" }
       module ranges_max_element       { private header "__algorithm/ranges_max_element.h" }
       module ranges_min               { private header "__algorithm/ranges_min.h" }
       module ranges_min_element       { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax            { private header "__algorithm/ranges_minmax.h" }

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_fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill_n.h'}}
 #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}}
 #include <__algorithm/ranges_find_first_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_first_of.h'}}
 #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}}
 #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}}
 #include <__algorithm/ranges_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}}
 #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_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_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.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'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}

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
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <list>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.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>);
+
+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>);
+
+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 changed
+  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {4, 2, 3, 1}, .input2 = {4, 3, 2, 1}, .expected = true});
+
+  // ranges have different lengths
+  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});
+
+}
+
+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*>();
+
+  { // check that the complexity requirements are met with identical ranges
+    {
+      int predCount = 0;
+      auto pred = [&](int, int) { ++predCount; return true; };
+      auto proj1Count = 0;
+      auto proj1 = [&](int i) { ++proj1Count; return i; };
+      auto proj2Count = 0;
+      auto proj2 = [&](int i) { ++proj2Count; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      auto ret = std::ranges::is_permutation(a, a + 5, a, a + 5, pred, proj1, proj2);
+      assert(ret);
+      assert(predCount == 5);
+      assert(proj1Count == 5);
+      assert(proj2Count == 5);
+    }
+    {
+      int predCount = 0;
+      auto pred = [&](int, int) { ++predCount; return true; };
+      auto proj1Count = 0;
+      auto proj1 = [&](int i) { ++proj1Count; return i; };
+      auto proj2Count = 0;
+      auto proj2 = [&](int i) { ++proj2Count; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      auto ret = std::ranges::is_permutation(a, a, pred, proj1, proj2);
+      assert(ret);
+      assert(predCount == 5);
+      assert(proj1Count == 5);
+      assert(proj2Count == 5);
+    }
+  }
+
+  { // check that std::invoke is used
+    struct S {
+      constexpr S(int i_) : i(i_) {}
+      constexpr bool compare(const S& j) const { return j.i == i; }
+      constexpr const S& identity() const { return *this; }
+      int i;
+    };
+    {
+      S a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::is_permutation(std::begin(a), std::end(a),
+                                             std::begin(a), std::end(a),
+                                             &S::compare, &S::identity, &S::identity);
+      assert(ret);
+    }
+    {
+      S a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::is_permutation(a, a, &S::compare, &S::identity, &S::identity);
+      assert(ret);
+    }
+  }
+
+  { // check that the implicit conversion to bool works
+    {
+      int a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::is_permutation(a, a + 4, a, a + 4, [](int i, int j) { return BooleanTestable{i == j}; });
+      assert(ret);
+    }
+    {
+      int a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::is_permutation(a, a, [](int i, int j) { return BooleanTestable{i == j}; });
+      assert(ret);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  { // check that the complexity requirements are met with identical ranges
+    {
+      int predCount = 0;
+      auto pred = [&](int, int) { ++predCount; return true; };
+      auto proj1Count = 0;
+      auto proj1 = [&](int i) { ++proj1Count; return i; };
+      auto proj2Count = 0;
+      auto proj2 = [&](int i) { ++proj2Count; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      int b[] = {1, 2, 3, 4};
+      auto ret = std::ranges::is_permutation(a, a + 5, b, b + 4, pred, proj1, proj2);
+      assert(!ret);
+      assert(predCount == 0);
+      assert(proj1Count == 0);
+      assert(proj2Count == 0);
+    }
+    {
+      int predCount = 0;
+      auto pred = [&](int, int) { ++predCount; return true; };
+      auto proj1Count = 0;
+      auto proj1 = [&](int i) { ++proj1Count; return i; };
+      auto proj2Count = 0;
+      auto proj2 = [&](int i) { ++proj2Count; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      std::list<int> b = {1, 2, 3, 4};
+      auto ret = std::ranges::is_permutation(a, b, pred, proj1, proj2);
+      assert(!ret);
+      assert(predCount == 0);
+      assert(proj1Count == 0);
+      assert(proj2Count == 0);
+    }
+  }
+
+  return 0;
+}

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, 42));
 //static_assert(test(std::ranges::generate_n, a, 10, 42));
 //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));