[libc++] Implement ranges::find_first_of

[Mordante]

In general looks good modulo some minor issues. But before approving I like to know whether or not we want to avoid code duplication between the "old" algorithms and their ranges based equivalents.

libcxx/include/__algorithm/ranges_find_first_of.h

43

I saw @ldionne recently raised some concerns regarding duplicating algorithms for the ranges and non-ranges version. Have we found a solution for that concern?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp

76

I find it a bit confusion the have an array<int, x> and an int expected not related.
Since the expected is an offset giving it a better type helps to avoid the confusion for me.

102

This is a duplicate of line 99.

113

I would like to see two non-empty ranges that have no match at all. For example
test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 3, 5, 7}, .input2 = {0, 2, 4, 6}, .expected = 5});

148

For clarity I would prefer to use std::begin() and std::end() here.

208

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_find_first_of.h

43

I think we have to decide that on a case-by-case basis. There are cases where I think it's more hassle than it's worth like here and there are cases where it's a definite win, like copy or move. There are of course also cases where it's not really clear, like binary_search. Note that there are optimizations possible for the ranges algorithms which are simply not possible for the classical algorithms (like in ranges::is_permutation) and ones where making optimizations for the ranges version properly is a lot harder (like ranges::move).

[Mordante]

LGTM, modulo one comment.
Since I'm not too involved in ranges I prefer to leave the final approval to @var-const or @ldionne.

libcxx/include/__algorithm/ranges_find_first_of.h

43

Thanks for the info!

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp

148

Can you do the same for similar places in the tests?

[var-const]

Almost LGTM, just some nits.

libcxx/docs/Status/RangesAlgorithms.csv

7–8

Nit: please update the link. Also, I don't think there should be a space between the tilde and the < character.

libcxx/include/__algorithm/ranges_find_first_of.h

44

Why are we creating a new variable instead of incrementing __first2, which would be consistent with __first1?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp

98

(By the way, I like these "named arguments")

107

For exhaustiveness, I'd also add a test case when input2 consists of a single element (currently, all the successful cases have input2 with several elements).

123

Nit: unnecessary blank line.

171

Great test, can you please check if there are any other range algorithm tests where a similar test would be valuable?

183

Nit: swap the order, so that the iterator overload goes before the range overload?

222

Question: perhaps check for the exact value?

[philnik]

libcxx/include/__algorithm/ranges_find_first_of.h

44

Because we go a few times over [__first2, __last2).

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp

171

I think I mostly added this test to other ranges algorithms. A few of the first ones might be missing a few tests, but I think that is a problem for later. They should probably be refactored and extended at some point.

[philnik]

• Address comments

[var-const]

libcxx/include/__algorithm/ranges_find_first_of.h

44

Oh, sorry for missing that, it's quite obvious.

libcxx/docs/Status/RangesAlgorithms.csv

 Category,Algorithm,Assignee,CL,Complete
 Search,any_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,all_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,none_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 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,Nikolas Klauser,`D126529 <https://reviews.llvm.org/D126529>`_,Under review
+Search,find_first_of,Nikolas Klauser,`D126529 <https://reviews.llvm.org/D126529>`_,✅
 Search,adjacent_find,Nikolas Klauser,`D126610 <https://reviews.llvm.org/D126610>`_,Under review
 Search,mismatch,Nikolas Klauser,`D117817 <https://llvm.org/D117817>`_,✅
 Search,equal,Nikolas Klauser,`D123681 <https://reviews.llvm.org/D123681>`_,✅
 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,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,upper_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,equal_range,Christopher Di Bella,n/a,Not started

libcxx/include/CMakeLists.txt

set(files
   __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_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_sorted.h
   __algorithm/ranges_is_sorted_until.h
   __algorithm/ranges_lower_bound.h

libcxx/include/__algorithm/ranges_find_first_of.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_FIND_FIRST_OF_H
+#define _LIBCPP___ALGORITHM_RANGES_FIND_FIRST_OF_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/indirectly_comparable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __find_first_of {
+struct __fn {
+
+  template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  _Iter1 __find_first_of_impl(_Iter1 __first1, _Sent1 __last1,
+                              _Iter2 __first2, _Sent2 __last2,
+                              _Pred& __pred,
+                              _Proj1& __proj1,
+                              _Proj2& __proj2) {
+    for (; __first1 != __last1; ++__first1) {
+      for (auto __j = __first2; __j != __last2; ++__j) {
+        if (std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__j)))
+          return __first1;
+      }
+    }
+    return __first1;
+  }
+
+  template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+            forward_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
+  _Iter1 operator()(_Iter1 __first1, _Sent1 __last1,
+                    _Iter2 __first2, _Sent2 __last2,
+                    _Pred __pred = {},
+                    _Proj1 __proj1 = {},
+                    _Proj2 __proj2 = {}) const {
+    return __find_first_of_impl(std::move(__first1), std::move(__last1),
+                                std::move(__first2), std::move(__last2),
+                                __pred,
+                                __proj1,
+                                __proj2);
+  }
+
+  template <input_range _Range1,
+            forward_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
+  borrowed_iterator_t<_Range1> operator()(_Range1&& __range1,
+                                          _Range2&& __range2,
+                                          _Pred __pred = {},
+                                          _Proj1 __proj1 = {},
+                                          _Proj2 __proj2 = {}) const {
+    return __find_first_of_impl(ranges::begin(__range1), ranges::end(__range1),
+                                ranges::begin(__range2), ranges::end(__range2),
+                                __pred,
+                                __proj1,
+                                __proj2);
+  }
+
+};
+} // namespace __find_first_of
+
+inline namespace __cpo {
+  inline constexpr auto find_first_of = __find_first_of::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_FIND_FIRST_OF_H

libcxx/include/algorithm

template<forward_range R, class T, class Proj = identity,
              ranges::less>
     constexpr borrowed_iterator_t<R>
       lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});                     // since C++20
 
   template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
     constexpr bool binary_search(I first, S last, const T& value, Comp comp = {},
                                          Proj proj = {});                                     // since C++20
+
   template<forward_range R, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
              ranges::less>
     constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
                                          Proj proj = {});                                     // since C++20
+  template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
+           class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+    requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+    constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
+                                       Pred pred = {},
+                                       Proj1 proj1 = {}, Proj2 proj2 = {});                 // since C++20
+
+  template<input_range R1, forward_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 borrowed_iterator_t<R1>
+      ranges::find_first_of(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

 #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_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lower_bound.h>

libcxx/include/module.modulemap

module __algorithm {
       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_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_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" }

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

#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_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_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);
     (void)std::ranges::find_if_not(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::for_each(first, last, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
     (void)std::ranges::for_each(a, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
     (void)std::ranges::for_each_n(first, count, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
     //(void)std::ranges::generate(first, last, NullaryValue(&copies)); assert(copies == 0);

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

#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_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);
+    (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);
     (void)std::ranges::find_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::for_each(first, last, UnaryVoid(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::for_each(a, UnaryVoid(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::for_each_n(first, count, UnaryVoid(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::includes(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #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_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_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'}}

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.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, forward_iterator I2, sentinel_for<I2> S2,
+//          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+//   constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
+//                                      Pred pred = {},
+//                                      Proj1 proj1 = {}, Proj2 proj2 = {});
+// template<input_range R1, forward_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 borrowed_iterator_t<R1>
+//     ranges::find_first_of(R1&& r1, R2&& r2,
+//                           Pred pred = {},
+//                           Proj1 proj1 = {}, Proj2 proj2 = {});
+
+#include <algorithm>
+#include <array>
+#include <functional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+template <class Iter1, class Iter2 = int*, class Sent1 = Iter1, class Sent2 = Iter2>
+concept HasFindFirstOfIt = requires(Iter1 iter1, Sent1 sent1, Iter2 iter2, Sent2 sent2) {
+                             std::ranges::find_first_of(iter1, sent1, iter2, sent2);
+                           };
+
+static_assert(HasFindFirstOfIt<int*>);
+static_assert(!HasFindFirstOfIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasFindFirstOfIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasFindFirstOfIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasFindFirstOfIt<int*, ForwardIteratorNotDerivedFrom>);
+static_assert(!HasFindFirstOfIt<int*, ForwardIteratorNotIncrementable>);
+static_assert(!HasFindFirstOfIt<int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasFindFirstOfIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasFindFirstOfIt<int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasFindFirstOfIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasFindFirstOfIt<int*, int**>); // not indirectly_comparable
+
+template <class Range1, class Range2 = UncheckedRange<int*>>
+concept HasFindFirstOfR = requires(Range1 range1, Range2 range2) {
+                             std::ranges::find_first_of(range1, range2);
+                           };
+
+static_assert(HasFindFirstOfR<UncheckedRange<int*>>);
+static_assert(!HasFindFirstOfR<InputRangeNotDerivedFrom>);
+static_assert(!HasFindFirstOfR<InputRangeNotIndirectlyReadable>);
+static_assert(!HasFindFirstOfR<InputRangeNotInputOrOutputIterator>);
+static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
+static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
+static_assert(!HasFindFirstOfR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>);
+static_assert(!HasFindFirstOfR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
+static_assert(!HasFindFirstOfR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasFindFirstOfR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly_comparable
+
+template <int N1, int N2>
+struct Data {
+  std::array<int, N1> input1;
+  std::array<int, N2> input2;
+  ptrdiff_t expected;
+};
+
+template <class Iter1, class Sent1, class Iter2, class Sent2, int N1, int N2>
+constexpr void test(Data<N1, N2> d) {
+  {
+    std::same_as<Iter1> decltype(auto) ret =
+        std::ranges::find_first_of(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size())),
+                                   Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size())));
+    assert(base(ret) == d.input1.data() + d.expected);
+  }
+  {
+    auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size())));
+    auto range2 = std::ranges::subrange(Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size())));
+    std::same_as<Iter1> decltype(auto) ret = std::ranges::find_first_of(range1, range2);
+    assert(base(ret) == d.input1.data() + d.expected);
+  }
+}
+
+template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
+constexpr void test_iterators() {
+  // simple test
+  test<Iter1, Sent1, Iter2, Sent2, 4, 2>({.input1 = {1, 2, 3, 4}, .input2 = {2, 3}, .expected = 1});
+  // other elements from input2 are checked
+  test<Iter1, Sent1, Iter2, Sent2, 4, 2>({.input1 = {1, 2, 3, 4}, .input2 = {3, 2}, .expected = 1});
+  // an empty second range returns last
+  test<Iter1, Sent1, Iter2, Sent2, 4, 0>({.input1 = {1, 2, 3, 4}, .input2 = {}, .expected = 4});
+  // check that an empty first range works
+  test<Iter1, Sent1, Iter2, Sent2, 0, 1>({.input1 = {}, .input2 = {1}, .expected = 0});
+  // check both ranges empty works
+  test<Iter1, Sent1, Iter2, Sent2, 0, 0>({.input1 = {}, .input2 = {}, .expected = 0});
+  // the first element is checked properly
+  test<Iter1, Sent1, Iter2, Sent2, 5, 2>({.input1 = {5, 4, 3, 2, 1}, .input2 = {1, 5}, .expected = 0});
+  // the last element is checked properly
+  test<Iter1, Sent1, Iter2, Sent2, 5, 2>({.input1 = {5, 4, 3, 2, 1}, .input2 = {1, 6}, .expected = 4});
+  // no match, one-past-the-end iterator should be returned
+  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 3, 5, 7}, .input2 = {0, 2, 4, 6}, .expected = 4});
+  // input2 contains a single element
+  test<Iter1, Sent1, Iter2, Sent2, 4, 1>({.input1 = {1, 3, 5, 7}, .input2 = {1}, .expected = 0});
+}
+
+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*>();
+}
+
+constexpr bool test() {
+  test_iterators1<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators1<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_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*>();
+
+  { // check that std::ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::find_first_of(std::array {1}, std::array {1});
+  }
+
+  { // check that the predicate is used
+    int a[] = {1, 2, 3, 4};
+    int b[] = {2};
+    {
+      auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),
+                                            std::begin(b), std::end(b),
+                                            std::ranges::greater{});
+      assert(ret == a + 2);
+    }
+    {
+      auto ret = std::ranges::find_first_of(a, b, std::ranges::greater{});
+      assert(ret == a + 2);
+    }
+  }
+
+  { // check that the projections are used
+    int a[] = {1, 2, 3, 4};
+    int b[] = {4};
+    {
+      auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),
+                                            std::begin(b), std::end(b), {},
+                                            [](int i) { return i / 2; },
+                                            [](int i) { return i - 3; });
+      assert(ret == a + 1);
+    }
+    {
+      auto ret = std::ranges::find_first_of(a, b, {}, [](int i) { return i / 2; }, [](int i) { return i - 3; });
+      assert(ret == a + 1);
+    }
+  }
+
+  { // check that std::invoke is used
+    struct S1 {
+      constexpr S1(int i_) : i(i_) {}
+      constexpr bool compare(int j) const { return j == i; }
+      constexpr const S1& identity() const { return *this; }
+      int i;
+    };
+    struct S2 {
+      constexpr S2(int i_) : i(i_) {}
+      int i;
+    };
+
+    {
+      S1 a[] = {1, 2, 3, 4};
+      S2 b[] = {2, 3};
+      auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),
+                                            std::begin(b), std::end(b), &S1::compare, &S1::identity, &S2::i);
+      assert(ret == a + 1);
+    }
+    {
+      S1 a[] = {1, 2, 3, 4};
+      S2 b[] = {2, 3};
+      auto ret = std::ranges::find_first_of(a, b, &S1::compare, &S1::identity, &S2::i);
+      assert(ret == a + 1);
+    }
+  }
+
+  { // check that the implicit conversion to bool works
+    StrictComparable<int> a[] = {1, 2, 3, 4};
+    StrictComparable<int> b[] = {2, 3};
+    {
+      auto ret = std::ranges::find_first_of(a, std::end(a), b, std::end(b));
+      assert(ret == a + 1);
+    }
+    {
+      auto ret = std::ranges::find_first_of(a, b);
+      assert(ret == a + 1);
+    }
+  }
+
+  { // check that the complexity requirements are met
+    int a[] = {1, 2, 3, 4};
+    int b[] = {2, 3};
+    {
+      int predCount = 0;
+      auto predCounter = [&](int, int) { ++predCount; return false; };
+      int proj1Count = 0;
+      auto proj1Counter = [&](int i) { ++proj1Count; return i; };
+      int proj2Count = 0;
+      auto proj2Counter = [&](int i) { ++proj2Count; return i; };
+      auto ret = std::ranges::find_first_of(std::begin(a), std::end(a),
+                                            std::begin(b), std::end(b), predCounter, proj1Counter, proj2Counter);
+      assert(ret == a + 4);
+      assert(predCount <= 8);
+      assert(proj1Count <= 8);
+      assert(proj2Count <= 8);
+    }
+    {
+      int predCount = 0;
+      auto predCounter = [&](int, int) { ++predCount; return false; };
+      int proj1Count = 0;
+      auto proj1Counter = [&](int i) { ++proj1Count; return i; };
+      int proj2Count = 0;
+      auto proj2Counter = [&](int i) { ++proj2Count; return i; };
+      auto ret = std::ranges::find_first_of(a, b, predCounter, proj1Counter, proj2Counter);
+      assert(ret == a + 4);
+      assert(predCount == 8);
+      assert(proj1Count == 8);
+      assert(proj2Count == 8);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}