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>
test_iterators()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;
operator ==(OneWayComparable l,OneWayComparable)76 friend constexpr bool operator==(OneWayComparable l, OneWayComparable) { return l.isLeft; }
77 };
78
79 struct NonConstComparableLValue {
operator ==(const NonConstComparableLValue &,const NonConstComparableLValue &)80 friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; }
operator ==(NonConstComparableLValue &,NonConstComparableLValue &)81 friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; }
operator ==(const NonConstComparableLValue &,NonConstComparableLValue &)82 friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; }
operator ==(NonConstComparableLValue &,const NonConstComparableLValue &)83 friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; }
84 };
85
86 struct NonConstComparableRValue {
operator ==(const NonConstComparableRValue &,const NonConstComparableRValue &)87 friend constexpr bool operator==(const NonConstComparableRValue&, const NonConstComparableRValue&) { return false; }
operator ==(const NonConstComparableRValue &&,const NonConstComparableRValue &&)88 friend constexpr bool operator==(const NonConstComparableRValue&&, const NonConstComparableRValue&&) { return false; }
operator ==(NonConstComparableRValue &&,NonConstComparableRValue &&)89 friend constexpr bool operator==(NonConstComparableRValue&&, NonConstComparableRValue&&) { return false; }
operator ==(NonConstComparableRValue &&,const NonConstComparableRValue &)90 friend constexpr bool operator==(NonConstComparableRValue&&, const NonConstComparableRValue&) { return true; }
91 };
92
test()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
main(int,char **)268 int main(int, char**) {
269 test();
270 static_assert(test());
271
272 return 0;
273 }
274