[libc++] Implement ranges::equal

[Mordante]

In general looks good, but some minor issues.

libcxx/include/__algorithm/ranges_equal.h

94

Interesting that the standard uses distance instead of size.

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

90

Please add tests with the same size, but different values.

107

Here too I like to see a test which returns false for a search.

197

This misses the tests when the input isn't a size_sentinel_for or a sized_range.

[Mordante]

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

2

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp should also be updated.

[philnik]

• Address comments

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

197

I don't think there is anything interesting about them. IIUC in theory an implementation could still not call the projections or predicates if it magically knows that it's iterating over two arrays of different sizes.

[Mordante]

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

197

I think the interesting part is that we now have an untested code path. Not that I expect errors, but it would be good to add a test.

[var-const]

libcxx/include/__algorithm/ranges_equal.h

94

Same question -- what's the reason to use size as opposed to distance (which would be closer to the Standard)?

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

76

Optional: a helper function would allow making the call sites quite a bit shorter:

assert(test({1, 2, 3, 4}, {1, 2, 3, 4});
assert(test({1, 2, 3, 4}, {2, 3, 4, 5}, [](int l, int r) { return l != r; });
...
// Comments can help distinguish parameters:
assert(test(/*a=*/ {1, 2, 3, 4}, /*b=*/ {2, 3, 4, 5}, /*pred=*/ [](int l, int r) { return l != r; });

186

Please also test when a) both ranges are empty and b) only one of the ranges is empty.

257

Nit: please add a blank line after this line.

[philnik]

• Address comments

[var-const]

@philnik I see you've addressed a few comments but not sure if this is ready for another round of review. Please ping me (here or on Discord if you prefer) when you'd like me to take another look. Thanks!

[philnik]

• Try to fix CI

@var-const This should be ready for another round.

[philnik]

Rebased

[philnik]

libcxx/include/__algorithm/ranges_equal.h

94

ranges::distance just forwards to ranges::size if it's a sized_range, so I don't see any reason for the additional indirection. If you'd rather have it spelled ranges::distance I can change it though.

[var-const]

LGTM. There's just one blocking comment that should be a very straightforward fix and one completely optional suggestion, so I don't think this needs another round of review (unless something unexpected happens, of course). Thanks!

libcxx/include/__algorithm/ranges_equal.h

94

I'd prefer to use ranges::distance just to be a little more consistent with the standard. That way, somebody reading the code could trivially verify that this part is correct, without looking up or recalling the details of how distance and size are defined. I don't think the extra indirection would cause any noticeable issues.

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

76

Note: it's totally fine to ignore an optional suggestion, but in that case, please write a short comment to make it clear that you deliberately decided to not implement or postpone it. It would just make it more obvious to me whether you decided to not go with the suggestion or simply didn't get to this comment yet. Thanks!

[philnik]

• Address comments

[philnik]

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

76

I've done that in a few of the newly written code and I think it's nice. I might refactor the already-written tests later.

[philnik]

• Fix the modules build

[philnik]

Rebased

libcxx/docs/Status/RangesAlgorithms.csv

 Category,Algorithm,Assignee,CL,Complete
 Search,any_of,Christopher Di Bella,`D105793 <https://llvm.org/D105793>`_
 Search,all_of,Christopher Di Bella,`D105793 <https://llvm.org/D105793>`_
 Search,none_of,Christopher Di Bella,`D105793 <https://llvm.org/D105793>`_
 Search,find,Nikolas Klauser,`D121248 <https://reviews.llvm.org/D121248>`_,✅
 Search,find_if,Nikolas Klauser,`D121248 <https://reviews.llvm.org/D121248>`_,✅
 Search,find_if_not,Nikolas Klauser,`D121248 <https://reviews.llvm.org/D121248>`_,✅
 Search,find_first_of,Not assigned,n/a,Not started
 Search,adjacent_find,Not assigned,n/a,Not started
 Search,mismatch,Nikolas Klauser,`D117817 <https://llvm.org/D117817>`_,✅
-Search,equal,Not assigned,n/a,Not started
+Search,equal,Nikolas Klauser,n/a,✅
 Search,lexicographical_compare,Not assigned,n/a,Not started
 Search,partition_point,Christopher Di Bella,`D105794 <https://llvm.org/D105794>`_,Under review
 Search,lower_bound,Christopher Di Bella,`D105795 <https://llvm.org/D105795>`_,Under review
 Search,upper_bound,Christopher Di Bella,`D105795 <https://llvm.org/D105795>`_,Under review
 Search,equal_range,Christopher Di Bella,n/a,Not started
 Search,binary_search,Christopher Di Bella,n/a,Not started
 Search,min,Nikolas Klauser,`D119589 <https://llvm.org/D119589>`_,✅
 Search,max,Nikolas Klauser,`D122002 <https://llvm.org/D122002>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/prev_permutation.h
   __algorithm/push_heap.h
   __algorithm/ranges_copy.h
   __algorithm/ranges_copy_backward.h
   __algorithm/ranges_copy_if.h
   __algorithm/ranges_copy_n.h
   __algorithm/ranges_count.h
   __algorithm/ranges_count_if.h
+  __algorithm/ranges_equal.h
   __algorithm/ranges_fill.h
   __algorithm/ranges_fill_n.h
   __algorithm/ranges_find.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

libcxx/include/__algorithm/ranges_equal.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_EQUAL_H
+#define _LIBCPP___ALGORITHM_RANGES_EQUAL_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/distance.h>
+#include <__iterator/indirectly_comparable.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 __equal {
+struct __fn {
+private:
+  template <class _Iter1, class _Sent1,
+            class _Iter2, class _Sent2,
+            class _Pred,
+            class _Proj1,
+            class _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  bool __equal_impl(_Iter1 __first1, _Sent1 __last1,
+                    _Iter2 __first2, _Sent2 __last2,
+                    _Pred& __pred,
+                    _Proj1& __proj1,
+                    _Proj2& __proj2) {
+    while (__first1 != __last1 && __first2 != __last2) {
+      if (!std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__first2)))
+        return false;
+      ++__first1;
+      ++__first2;
+    }
+    return __first1 == __last1 && __first2 == __last2;
+  }
+
+public:
+
+  template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+            input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+            class _Pred = ranges::equal_to,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  bool operator()(_Iter1 __first1, _Sent1 __last1,
+                  _Iter2 __first2, _Sent2 __last2,
+                  _Pred __pred = {},
+                  _Proj1 __proj1 = {},
+                  _Proj2 __proj2 = {}) const {
+    if constexpr (sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>) {
+      if (__last1 - __first1 != __last2 - __first2)
+        return false;
+    }
+    return __equal_impl(std::move(__first1), std::move(__last1),
+                        std::move(__first2), std::move(__last2),
+                        __pred,
+                        __proj1,
+                        __proj2);
+  }
+
+  template <input_range _Range1,
+            input_range _Range2,
+            class _Pred = ranges::equal_to,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2>
+  _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 __equal_impl(ranges::begin(__range1), ranges::end(__range1),
+                        ranges::begin(__range2), ranges::end(__range2),
+                        __pred,
+                        __proj1,
+                        __proj2);
+    return false;
+  }
+};
+} // namespace __equal
+
+inline namespace __cpo {
+  inline constexpr auto equal = __equal::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_EQUAL_H

libcxx/include/algorithm

template<input_range R, class Proj = identity,
   template<class T, output_iterator<const T&> O, sentinel_for<O> S>
     constexpr O ranges::fill(O first, S last, const T& value);                              // since C++20
 
   template<class T, output_range<const T&> R>
     constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);                   // since C++20
 
   template<class T, output_iterator<const T&> O>
     constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);            // since C++20
+
+ template<input_iterator I1, sentinel_for<I1> S1, input_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 bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
+                                Pred pred = {},
+                                Proj1 proj1 = {}, Proj2 proj2 = {});                        // since C++20
+
+ template<input_range R1, input_range R2, class Pred = ranges::equal_to,
+          class Proj1 = identity, class Proj2 = identity>
+   requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+   constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
+                                Proj1 proj1 = {}, Proj2 proj2 = {});                        // since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/push_heap.h>
 #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_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>

libcxx/include/module.modulemap

module __algorithm {
       module prev_permutation         { private header "__algorithm/prev_permutation.h" }
       module push_heap                { private header "__algorithm/push_heap.h" }
       module ranges_copy              { private header "__algorithm/ranges_copy.h" }
       module ranges_copy_backward     { private header "__algorithm/ranges_copy_backward.h" }
       module ranges_copy_if           { private header "__algorithm/ranges_copy_if.h" }
       module ranges_copy_n            { private header "__algorithm/ranges_copy_n.h" }
       module ranges_count             { private header "__algorithm/ranges_count.h" }
       module ranges_count_if          { private header "__algorithm/ranges_count_if.h" }
+      module ranges_equal             { private header "__algorithm/ranges_equal.h" }
       module ranges_fill              { private header "__algorithm/ranges_fill.h" }
       module ranges_fill_n            { private header "__algorithm/ranges_fill_n.h" }
       module ranges_find              { private header "__algorithm/ranges_find.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" }

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

constexpr bool all_the_algorithms()
     //(void)std::ranges::clamp(value, value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
 #if TEST_STD_VER > 20
     //(void)std::ranges::ends_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
 #endif
-    //(void)std::ranges::equal(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::equal(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
+    (void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::equal_range(first, last, value, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::equal_range(a, value, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::find_first_of(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::find_first_of(a, b, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(a, UnaryTrue(&copies)); assert(copies == 0);

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

constexpr bool all_the_algorithms()
     (void)std::ranges::count(a, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
 #if TEST_STD_VER > 20
     //(void)std::ranges::ends_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
 #endif
-    //(void)std::ranges::equal(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::equal(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::equal(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::equal(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::equal_range(first, last, value, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::equal_range(a, value, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find(first, last, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find(a, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::find_end(first, last, first2, mid2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::find_end(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::find_first_of(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::find_first_of(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}}
 #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
 #include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}}
 #include <__algorithm/ranges_copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_backward.h'}}
 #include <__algorithm/ranges_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_if.h'}}
 #include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}}
 #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}}
 #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}}
+#include <__algorithm/ranges_equal.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_equal.h'}}
 #include <__algorithm/ranges_fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill.h'}}
 #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_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'}}

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

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<input_iterator I1, sentinel_for<I1> S1, input_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 bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
+//                                Pred pred = {},
+//                                Proj1 proj1 = {}, Proj2 proj2 = {});
+// template<input_range R1, input_range R2, class Pred = ranges::equal_to,
+//          class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+//   constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
+//                                Proj1 proj1 = {}, Proj2 proj2 = {});
+
+#include <algorithm>
+#include <cassert>
+#include <concepts>
+#include <functional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter1, class Sent1 = sentinel_wrapper<Iter1>,
+          class Iter2 = Iter1, class Sent2 = sentinel_wrapper<Iter2>>
+concept HasEqualIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
+  std::ranges::equal(first1, last1, first2, last2);
+};
+
+static_assert(HasEqualIt<int*>);
+static_assert(!HasEqualIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasEqualIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasEqualIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasEqualIt<int*, int*, InputIteratorNotDerivedFrom>);
+static_assert(!HasEqualIt<int*, int*, InputIteratorNotIndirectlyReadable>);
+static_assert(!HasEqualIt<int*, int*, InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasEqualIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasEqualIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasEqualIt<int*, int*, int**>);
+
+template <class Range1, class Range2>
+concept HasEqualR = requires (Range1 range1, Range2 range2) {
+  std::ranges::equal(range1, range2);
+};
+
+static_assert(HasEqualR<UncheckedRange<int*>, UncheckedRange<int*>>);
+static_assert(!HasEqualR<InputRangeNotDerivedFrom, UncheckedRange<int*>>);
+static_assert(!HasEqualR<InputRangeNotIndirectlyReadable, UncheckedRange<int*>>);
+static_assert(!HasEqualR<InputRangeNotInputOrOutputIterator, UncheckedRange<int*>>);
+static_assert(!HasEqualR<InputRangeNotSentinelSemiregular, UncheckedRange<int*>>);
+static_assert(!HasEqualR<InputRangeNotSentinelEqualityComparableWith, UncheckedRange<int*>>);
+static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotDerivedFrom>);
+static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotIndirectlyReadable>);
+static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotInputOrOutputIterator>);
+static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>);
+static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasEqualR<UncheckedRange<int*>, UncheckedRange<int**>>);
+
+template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
+constexpr void test_iterators() {
+  { // simple test
+    {
+      int a[] = {1, 2, 3, 4};
+      int b[] = {1, 2, 3, 4};
+      std::same_as<bool> decltype(auto) ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)),
+                                                                 Iter2(b), Sent2(Iter2(b + 4)));
+      assert(ret);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      int b[] = {1, 2, 3, 4};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
+      std::same_as<bool> decltype(auto) ret = std::ranges::equal(range1, range2);
+      assert(ret);
+    }
+  }
+
+  { // check that the predicate is used (return true)
+    {
+      int a[] = {1, 2, 3, 4};
+      int b[] = {2, 3, 4, 5};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)),
+                                    [](int l, int r) { return l != r; });
+      assert(ret);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      int b[] = {2, 3, 4, 5};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
+      auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });
+      assert(ret);
+    }
+  }
+
+  { // check that the predicate is used (return false)
+    {
+      int a[] = {1, 2, 3, 4};
+      int b[] = {2, 3, 3, 5};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)),
+                                    [](int l, int r) { return l != r; });
+      assert(!ret);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      int b[] = {2, 3, 3, 5};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4)));
+      auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; });
+      assert(!ret);
+    }
+  }
+
+  { // check that the projections are used
+    {
+      int a[] = {1, 2, 3, 4, 5};
+      int b[] = {6, 10, 14, 18, 22};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)),
+                                    Iter2(b), Sent2(Iter2(b + 5)),
+                                    {},
+                                    [](int i) { return i * 4; },
+                                    [](int i) { return i - 2; });
+      assert(ret);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5};
+      int b[] = {6, 10, 14, 18, 22};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));
+      auto ret = std::ranges::equal(range1,
+                                    range2,
+                                    {},
+                                    [](int i) { return i * 4; },
+                                    [](int i) { return i - 2; });
+      assert(ret);
+    }
+  }
+
+  { // check that different sized ranges work
+    {
+      int a[] = {4, 3, 2, 1};
+      int b[] = {4, 3, 2, 1, 5, 6, 7};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7)));
+      assert(!ret);
+    }
+    {
+      int a[] = {4, 3, 2, 1};
+      int b[] = {4, 3, 2, 1, 5, 6, 7};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7)));
+      auto ret = std::ranges::equal(range1, range2);
+      assert(!ret);
+    }
+  }
+
+  { // check that two ranges with the same size but different values are different
+    {
+      int a[] = {4, 6, 34, 76, 5};
+      int b[] = {4, 6, 34, 67, 5};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5)));
+      assert(!ret);
+    }
+    {
+      int a[] = {4, 6, 34, 76, 5};
+      int b[] = {4, 6, 34, 67, 5};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5)));
+      auto ret = std::ranges::equal(range1, range2);
+      assert(!ret);
+    }
+  }
+
+  { // check that two empty ranges work
+    {
+      int a[] = {};
+      int b[] = {};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b)));
+      assert(ret);
+    }
+    {
+      int a[] = {};
+      int b[] = {};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b)));
+      auto ret = std::ranges::equal(range1, range2);
+      assert(ret);
+    }
+  }
+
+  { // check that it works with the first range empty
+    {
+      int a[] = {};
+      int b[] = {1, 2};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b + 2)));
+      assert(!ret);
+    }
+    {
+      int a[] = {};
+      int b[] = {1, 2};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2)));
+      auto ret = std::ranges::equal(range1, range2);
+      assert(!ret);
+    }
+  }
+
+  { // check that it works with the second range empty
+    {
+      int a[] = {1, 2};
+      int b[] = {};
+      auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b), Sent2(Iter2(b)));
+      assert(!ret);
+    }
+    {
+      int a[] = {1, 2};
+      int b[] = {};
+      auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2)));
+      auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b)));
+      auto ret = std::ranges::equal(range1, range2);
+      assert(!ret);
+    }
+  }
+}
+
+template<class Iter1, class Sent1 = Iter1>
+constexpr void test_iterators2() {
+  test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_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_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators2<forward_iterator<int*>>();
+  test_iterators2<bidirectional_iterator<int*>>();
+  test_iterators2<random_access_iterator<int*>>();
+  test_iterators2<contiguous_iterator<int*>>();
+  test_iterators2<int*>();
+  test_iterators2<const int*>();
+
+  { // check that std::invoke is used
+    struct S {
+      constexpr S(int i_) : i(i_) {}
+      constexpr bool equal(int o) { return i == o; }
+      constexpr S& identity() { return *this; }
+      int i;
+    };
+    {
+      S a[] = {7, 8, 9};
+      S b[] = {7, 8, 9};
+      auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i);
+      assert(ret);
+    }
+    {
+      S a[] = {7, 8, 9};
+      S b[] = {7, 8, 9};
+      auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i);
+      assert(ret);
+    }
+  }
+
+  { // check that the complexity requirements are met
+    { // different size
+      {
+        int a[] = {1, 2, 3};
+        int b[] = {1, 2, 3, 4};
+        int predCount = 0;
+        int projCount = 0;
+        auto pred = [&](int l, int r) { ++predCount; return l == r; };
+        auto proj = [&](int i) { ++projCount; return i; };
+        auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj);
+        assert(!ret);
+        assert(predCount == 0);
+        assert(projCount == 0);
+      }
+      {
+        int a[] = {1, 2, 3};
+        int b[] = {1, 2, 3, 4};
+        int predCount = 0;
+        int projCount = 0;
+        auto pred = [&](int l, int r) { ++predCount; return l == r; };
+        auto proj = [&](int i) { ++projCount; return i; };
+        auto ret = std::ranges::equal(a, b, pred, proj, proj);
+        assert(!ret);
+        assert(predCount == 0);
+        assert(projCount == 0);
+      }
+    }
+
+    { // not a sized sentinel
+      {
+        int a[] = {1, 2, 3};
+        int b[] = {1, 2, 3, 4};
+        int predCount = 0;
+        int projCount = 0;
+        auto pred = [&](int l, int r) { ++predCount; return l == r; };
+        auto proj = [&](int i) { ++projCount; return i; };
+        auto ret = std::ranges::equal(a, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj);
+        assert(!ret);
+        assert(predCount <= 4);
+        assert(projCount <= 7);
+      }
+      {
+        int a[] = {1, 2, 3};
+        int b[] = {1, 2, 3, 4};
+        int predCount = 0;
+        int projCount = 0;
+        auto pred = [&](int l, int r) { ++predCount; return l == r; };
+        auto proj = [&](int i) { ++projCount; return i; };
+        auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3));
+        auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4));
+        auto ret = std::ranges::equal(range1, range2, pred, proj, proj);
+        assert(!ret);
+        assert(predCount <= 4);
+        assert(projCount <= 7);
+      }
+    }
+
+    { // same size
+      {
+        int a[] = {1, 2, 3};
+        int b[] = {1, 2, 3};
+        int predCount = 0;
+        int projCount = 0;
+        auto pred = [&](int l, int r) { ++predCount; return l == r; };
+        auto proj = [&](int i) { ++projCount; return i; };
+        auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj);
+        assert(ret);
+        assert(predCount == 3);
+        assert(projCount == 6);
+      }
+      {
+        int a[] = {1, 2, 3};
+        int b[] = {1, 2, 3};
+        int predCount = 0;
+        int projCount = 0;
+        auto pred = [&](int l, int r) { ++predCount; return l == r; };
+        auto proj = [&](int i) { ++projCount; return i; };
+        auto ret = std::ranges::equal(a, b, pred, proj, proj);
+        assert(ret);
+        assert(predCount == 3);
+        assert(projCount == 6);
+      }
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}