1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 // <algorithm>
10 
11 // UNSUPPORTED: c++03, c++11, c++14, c++17
12 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
13 
14 // template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
15 //   requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
16 //   constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});
17 // template<input_range R, class T, class Proj = identity>
18 //   requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
19 //   constexpr borrowed_iterator_t<R>
20 //     ranges::find(R&& r, const T& value, Proj proj = {});
21 
22 #include <algorithm>
23 #include <array>
24 #include <cassert>
25 #include <ranges>
26 
27 #include "almost_satisfies_types.h"
28 #include "boolean_testable.h"
29 #include "test_iterators.h"
30 
31 struct NotEqualityComparable {};
32 
33 template <class It, class Sent = It>
34 concept HasFindIt = requires(It it, Sent sent) { std::ranges::find(it, sent, *it); };
35 static_assert(HasFindIt<int*>);
36 static_assert(!HasFindIt<NotEqualityComparable*>);
37 static_assert(!HasFindIt<InputIteratorNotDerivedFrom>);
38 static_assert(!HasFindIt<InputIteratorNotIndirectlyReadable>);
39 static_assert(!HasFindIt<InputIteratorNotInputOrOutputIterator>);
40 static_assert(!HasFindIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
41 static_assert(!HasFindIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
42 
43 static_assert(!HasFindIt<int*, int>);
44 static_assert(!HasFindIt<int, int*>);
45 
46 template <class Range, class ValT>
47 concept HasFindR = requires(Range r) { std::ranges::find(r, ValT{}); };
48 static_assert(HasFindR<std::array<int, 1>, int>);
49 static_assert(!HasFindR<int, int>);
50 static_assert(!HasFindR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);
51 static_assert(!HasFindR<InputRangeNotDerivedFrom, int>);
52 static_assert(!HasFindR<InputRangeNotIndirectlyReadable, int>);
53 static_assert(!HasFindR<InputRangeNotInputOrOutputIterator, int>);
54 static_assert(!HasFindR<InputRangeNotSentinelSemiregular, int>);
55 static_assert(!HasFindR<InputRangeNotSentinelEqualityComparableWith, int>);
56 
57 template <class It, class Sent = It>
58 constexpr void test_iterators() {
59   {
60     int a[] = {1, 2, 3, 4};
61     std::same_as<It> auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4);
62     assert(base(ret) == a + 3);
63     assert(*ret == 4);
64   }
65   {
66     int a[] = {1, 2, 3, 4};
67     auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
68     std::same_as<It> auto ret = std::ranges::find(range, 4);
69     assert(base(ret) == a + 3);
70     assert(*ret == 4);
71   }
72 }
73 
74 struct OneWayComparable {
75   bool isLeft;
76   friend constexpr bool operator==(OneWayComparable l, OneWayComparable) { return l.isLeft; }
77 };
78 
79 struct NonConstComparableLValue {
80   friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; }
81   friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; }
82   friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; }
83   friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; }
84 };
85 
86 struct NonConstComparableRValue {
87   friend constexpr bool operator==(const NonConstComparableRValue&, const NonConstComparableRValue&) { return false; }
88   friend constexpr bool operator==(const NonConstComparableRValue&&, const NonConstComparableRValue&&) { return false; }
89   friend constexpr bool operator==(NonConstComparableRValue&&, NonConstComparableRValue&&) { return false; }
90   friend constexpr bool operator==(NonConstComparableRValue&&, const NonConstComparableRValue&) { return true; }
91 };
92 
93 constexpr bool test() {
94   test_iterators<int*>();
95   test_iterators<const int*>();
96   test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
97   test_iterators<bidirectional_iterator<int*>>();
98   test_iterators<forward_iterator<int*>>();
99   test_iterators<random_access_iterator<int*>>();
100   test_iterators<contiguous_iterator<int*>>();
101 
102   {
103     // check that projections are used properly and that they are called with the iterator directly
104     {
105       int a[] = {1, 2, 3, 4};
106       auto ret = std::ranges::find(a, a + 4, a + 3, [](int& i) { return &i; });
107       assert(ret == a + 3);
108     }
109     {
110       int a[] = {1, 2, 3, 4};
111       auto ret = std::ranges::find(a, a + 3, [](int& i) { return &i; });
112       assert(ret == a + 3);
113     }
114   }
115 
116   { // check that the first element is returned
117     {
118       struct S {
119         int comp;
120         int other;
121       };
122       S a[] = { {0, 0}, {0, 2}, {0, 1} };
123       auto ret = std::ranges::find(a, 0, &S::comp);
124       assert(ret == a);
125       assert(ret->comp == 0);
126       assert(ret->other == 0);
127     }
128     {
129       struct S {
130         int comp;
131         int other;
132       };
133       S a[] = { {0, 0}, {0, 2}, {0, 1} };
134       auto ret = std::ranges::find(a, a + 3, 0, &S::comp);
135       assert(ret == a);
136       assert(ret->comp == 0);
137       assert(ret->other == 0);
138     }
139   }
140 
141   { // check that end + 1 iterator is returned with no match
142     {
143       int a[] = {1, 1, 1};
144       auto ret = std::ranges::find(a, a + 3, 0);
145       assert(ret == a + 3);
146     }
147     {
148       int a[] = {1, 1, 1};
149       auto ret = std::ranges::find(a, 0);
150       assert(ret == a + 3);
151     }
152   }
153 
154   {
155     // check that ranges::dangling is returned
156     [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret =
157       std::ranges::find(std::array{1, 2}, 3);
158   }
159 
160   {
161     // check that an iterator is returned with a borrowing range
162     int a[] = {1, 2, 3, 4};
163     std::same_as<int*> auto ret = std::ranges::find(std::views::all(a), 1);
164     assert(ret == a);
165     assert(*ret == 1);
166   }
167 
168   {
169     // check that std::invoke is used
170     struct S { int i; };
171     S a[] = { S{1}, S{3}, S{2} };
172     std::same_as<S*> auto ret = std::ranges::find(a, 4, &S::i);
173     assert(ret == a + 3);
174   }
175 
176   {
177     // count invocations of the projection
178     {
179       int a[] = {1, 2, 3, 4};
180       int projection_count = 0;
181       auto ret = std::ranges::find(a, a + 4, 2, [&](int i) { ++projection_count; return i; });
182       assert(ret == a + 1);
183       assert(*ret == 2);
184       assert(projection_count == 2);
185     }
186     {
187       int a[] = {1, 2, 3, 4};
188       int projection_count = 0;
189       auto ret = std::ranges::find(a, 2, [&](int i) { ++projection_count; return i; });
190       assert(ret == a + 1);
191       assert(*ret == 2);
192       assert(projection_count == 2);
193     }
194   }
195 
196   {
197     // check comparison order
198     {
199       OneWayComparable a[] = { OneWayComparable{true} };
200       auto ret = std::ranges::find(a, a + 1, OneWayComparable{false});
201       assert(ret == a);
202     }
203     {
204       OneWayComparable a[] = { OneWayComparable{true} };
205       auto ret = std::ranges::find(a, OneWayComparable{false});
206       assert(ret == a);
207     }
208   }
209 
210   {
211     // check that the return type of `iter::operator*` doesn't change
212     {
213       NonConstComparableLValue a[] = { NonConstComparableLValue{} };
214       auto ret = std::ranges::find(a, a + 1, NonConstComparableLValue{});
215       assert(ret == a);
216     }
217     {
218       using It = std::move_iterator<NonConstComparableRValue*>;
219       NonConstComparableRValue a[] = { NonConstComparableRValue{} };
220       auto ret = std::ranges::find(It(a), It(a + 1), NonConstComparableRValue{});
221       assert(ret.base() == a);
222     }
223     {
224       NonConstComparableLValue a[] = { NonConstComparableLValue{} };
225       auto ret = std::ranges::find(a, NonConstComparableLValue{});
226       assert(ret == a);
227     }
228     {
229       using It = std::move_iterator<NonConstComparableRValue*>;
230       NonConstComparableRValue a[] = { NonConstComparableRValue{} };
231       auto range = std::ranges::subrange(It(a), It(a + 1));
232       auto ret = std::ranges::find(range, NonConstComparableRValue{});
233       assert(ret.base() == a);
234     }
235   }
236 
237   {
238     // check that an empty range works
239     {
240       std::array<int ,0> a = {};
241       auto ret = std::ranges::find(a.begin(), a.end(), 1);
242       assert(ret == a.begin());
243     }
244     {
245       std::array<int, 0> a = {};
246       auto ret = std::ranges::find(a, 1);
247       assert(ret == a.begin());
248     }
249   }
250 
251   {
252     // check that the implicit conversion to bool works
253     {
254       StrictComparable<int> a[] = {1, 2, 3, 4};
255       auto ret = std::ranges::find(a, a + 4, StrictComparable<int>{2});
256       assert(ret == a + 1);
257     }
258     {
259       StrictComparable<int> a[] = {1, 2, 3, 4};
260       auto ret = std::ranges::find(a, StrictComparable<int>{2});
261       assert(ret == a + 1);
262     }
263   }
264 
265   return true;
266 }
267 
268 int main(int, char**) {
269   test();
270   static_assert(test());
271 
272   return 0;
273 }
274