1 | //===- IteratorTest.cpp - Unit tests for iterator utilities ---------------===// |
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 | #include "llvm/ADT/iterator.h" |
10 | #include "llvm/ADT/ArrayRef.h" |
11 | #include "llvm/ADT/STLExtras.h" |
12 | #include "llvm/ADT/SmallVector.h" |
13 | #include "llvm/ADT/ilist.h" |
14 | #include "gmock/gmock.h" |
15 | #include "gtest/gtest.h" |
16 | #include <optional> |
17 | #include <type_traits> |
18 | #include <vector> |
19 | |
20 | using namespace llvm; |
21 | using testing::ElementsAre; |
22 | |
23 | namespace { |
24 | |
25 | template <int> struct Shadow; |
26 | |
27 | struct WeirdIter |
28 | : llvm::iterator_facade_base<WeirdIter, std::input_iterator_tag, Shadow<0>, |
29 | Shadow<1>, Shadow<2>, Shadow<3>> {}; |
30 | |
31 | struct AdaptedIter : iterator_adaptor_base<AdaptedIter, WeirdIter> {}; |
32 | |
33 | // Test that iterator_adaptor_base forwards typedefs, if value_type is |
34 | // unchanged. |
35 | static_assert(std::is_same_v<typename AdaptedIter::value_type, Shadow<0>>, "" ); |
36 | static_assert(std::is_same_v<typename AdaptedIter::difference_type, Shadow<1>>, |
37 | "" ); |
38 | static_assert(std::is_same_v<typename AdaptedIter::pointer, Shadow<2>>, "" ); |
39 | static_assert(std::is_same_v<typename AdaptedIter::reference, Shadow<3>>, "" ); |
40 | |
41 | // Ensure that pointe{e,r}_iterator adaptors correctly forward the category of |
42 | // the underlying iterator. |
43 | |
44 | using RandomAccessIter = SmallVectorImpl<int*>::iterator; |
45 | using BidiIter = ilist<int*>::iterator; |
46 | |
47 | template<class T> |
48 | using pointee_iterator_defaulted = pointee_iterator<T>; |
49 | template<class T> |
50 | using pointer_iterator_defaulted = pointer_iterator<T>; |
51 | |
52 | // Ensures that an iterator and its adaptation have the same iterator_category. |
53 | template<template<typename> class A, typename It> |
54 | using IsAdaptedIterCategorySame = |
55 | std::is_same<typename std::iterator_traits<It>::iterator_category, |
56 | typename std::iterator_traits<A<It>>::iterator_category>; |
57 | |
58 | // Check that dereferencing works correctly adapting pointers and proxies. |
59 | template <class T> |
60 | struct PointerWrapper : public iterator_adaptor_base<PointerWrapper<T>, T *> { |
61 | PointerWrapper(T *I) : PointerWrapper::iterator_adaptor_base(I) {} |
62 | }; |
63 | struct IntProxy { |
64 | int &I; |
65 | IntProxy(int &I) : I(I) {} |
66 | void operator=(int NewValue) { I = NewValue; } |
67 | }; |
68 | struct ConstIntProxy { |
69 | const int &I; |
70 | ConstIntProxy(const int &I) : I(I) {} |
71 | }; |
72 | template <class T, class ProxyT> |
73 | struct PointerProxyWrapper |
74 | : public iterator_adaptor_base<PointerProxyWrapper<T, ProxyT>, T *, |
75 | std::random_access_iterator_tag, T, |
76 | ptrdiff_t, T *, ProxyT> { |
77 | PointerProxyWrapper(T *I) : PointerProxyWrapper::iterator_adaptor_base(I) {} |
78 | }; |
79 | using IntIterator = PointerWrapper<int>; |
80 | using ConstIntIterator = PointerWrapper<const int>; |
81 | using IntProxyIterator = PointerProxyWrapper<int, IntProxy>; |
82 | using ConstIntProxyIterator = PointerProxyWrapper<const int, ConstIntProxy>; |
83 | |
84 | // There should only be a single (const-qualified) operator*, operator->, and |
85 | // operator[]. This test confirms that there isn't a non-const overload. Rather |
86 | // than adding those, users should double-check that T, PointerT, and ReferenceT |
87 | // have the right constness, and/or make fields mutable. |
88 | static_assert(&IntIterator::operator* == &IntIterator::operator*, "" ); |
89 | static_assert(&IntIterator::operator-> == &IntIterator::operator->, "" ); |
90 | static_assert(&IntIterator::operator[] == &IntIterator::operator[], "" ); |
91 | |
92 | template <class T, std::enable_if_t<std::is_assignable_v<T, int>, bool> = false> |
93 | constexpr bool canAssignFromInt(T &&) { |
94 | return true; |
95 | } |
96 | template <class T, |
97 | std::enable_if_t<!std::is_assignable_v<T, int>, bool> = false> |
98 | constexpr bool canAssignFromInt(T &&) { |
99 | return false; |
100 | } |
101 | |
102 | TEST(IteratorAdaptorTest, Dereference) { |
103 | int Number = 1; |
104 | |
105 | // Construct some iterators and check whether they can be assigned to. |
106 | IntIterator I(&Number); |
107 | const IntIterator IC(&Number); |
108 | ConstIntIterator CI(&Number); |
109 | const ConstIntIterator CIC(&Number); |
110 | EXPECT_EQ(true, canAssignFromInt(*I)); // int * |
111 | EXPECT_EQ(true, canAssignFromInt(*IC)); // int *const |
112 | EXPECT_EQ(false, canAssignFromInt(*CI)); // const int * |
113 | EXPECT_EQ(false, canAssignFromInt(*CIC)); // const int *const |
114 | |
115 | // Prove that dereference and assignment work. |
116 | EXPECT_EQ(1, *I); |
117 | EXPECT_EQ(1, *IC); |
118 | EXPECT_EQ(1, *CI); |
119 | EXPECT_EQ(1, *CIC); |
120 | *I = 2; |
121 | EXPECT_EQ(2, Number); |
122 | *IC = 3; |
123 | EXPECT_EQ(3, Number); |
124 | |
125 | // Construct some proxy iterators and check whether they can be assigned to. |
126 | IntProxyIterator P(&Number); |
127 | const IntProxyIterator PC(&Number); |
128 | ConstIntProxyIterator CP(&Number); |
129 | const ConstIntProxyIterator CPC(&Number); |
130 | EXPECT_EQ(true, canAssignFromInt(*P)); // int * |
131 | EXPECT_EQ(true, canAssignFromInt(*PC)); // int *const |
132 | EXPECT_EQ(false, canAssignFromInt(*CP)); // const int * |
133 | EXPECT_EQ(false, canAssignFromInt(*CPC)); // const int *const |
134 | |
135 | // Prove that dereference and assignment work. |
136 | EXPECT_EQ(3, (*P).I); |
137 | EXPECT_EQ(3, (*PC).I); |
138 | EXPECT_EQ(3, (*CP).I); |
139 | EXPECT_EQ(3, (*CPC).I); |
140 | *P = 4; |
141 | EXPECT_EQ(4, Number); |
142 | *PC = 5; |
143 | EXPECT_EQ(5, Number); |
144 | } |
145 | |
146 | // pointeE_iterator |
147 | static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted, |
148 | RandomAccessIter>::value, "" ); |
149 | static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted, |
150 | BidiIter>::value, "" ); |
151 | // pointeR_iterator |
152 | static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted, |
153 | RandomAccessIter>::value, "" ); |
154 | static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted, |
155 | BidiIter>::value, "" ); |
156 | |
157 | TEST(PointeeIteratorTest, Basic) { |
158 | int arr[4] = {1, 2, 3, 4}; |
159 | SmallVector<int *, 4> V; |
160 | V.push_back(Elt: &arr[0]); |
161 | V.push_back(Elt: &arr[1]); |
162 | V.push_back(Elt: &arr[2]); |
163 | V.push_back(Elt: &arr[3]); |
164 | |
165 | typedef pointee_iterator<SmallVectorImpl<int *>::const_iterator> |
166 | test_iterator; |
167 | |
168 | test_iterator Begin, End; |
169 | Begin = V.begin(); |
170 | End = test_iterator(V.end()); |
171 | |
172 | test_iterator I = Begin; |
173 | for (int i = 0; i < 4; ++i) { |
174 | EXPECT_EQ(*V[i], *I); |
175 | |
176 | EXPECT_EQ(I, Begin + i); |
177 | EXPECT_EQ(I, std::next(Begin, i)); |
178 | test_iterator J = Begin; |
179 | J += i; |
180 | EXPECT_EQ(I, J); |
181 | EXPECT_EQ(*V[i], Begin[i]); |
182 | |
183 | EXPECT_NE(I, End); |
184 | EXPECT_GT(End, I); |
185 | EXPECT_LT(I, End); |
186 | EXPECT_GE(I, Begin); |
187 | EXPECT_LE(Begin, I); |
188 | |
189 | EXPECT_EQ(i, I - Begin); |
190 | EXPECT_EQ(i, std::distance(Begin, I)); |
191 | EXPECT_EQ(Begin, I - i); |
192 | |
193 | test_iterator K = I++; |
194 | EXPECT_EQ(K, std::prev(I)); |
195 | } |
196 | EXPECT_EQ(End, I); |
197 | } |
198 | |
199 | TEST(PointeeIteratorTest, SmartPointer) { |
200 | SmallVector<std::unique_ptr<int>, 4> V; |
201 | V.push_back(Elt: std::make_unique<int>(args: 1)); |
202 | V.push_back(Elt: std::make_unique<int>(args: 2)); |
203 | V.push_back(Elt: std::make_unique<int>(args: 3)); |
204 | V.push_back(Elt: std::make_unique<int>(args: 4)); |
205 | |
206 | typedef pointee_iterator< |
207 | SmallVectorImpl<std::unique_ptr<int>>::const_iterator> |
208 | test_iterator; |
209 | |
210 | test_iterator Begin, End; |
211 | Begin = V.begin(); |
212 | End = test_iterator(V.end()); |
213 | |
214 | test_iterator I = Begin; |
215 | for (int i = 0; i < 4; ++i) { |
216 | EXPECT_EQ(*V[i], *I); |
217 | |
218 | EXPECT_EQ(I, Begin + i); |
219 | EXPECT_EQ(I, std::next(Begin, i)); |
220 | test_iterator J = Begin; |
221 | J += i; |
222 | EXPECT_EQ(I, J); |
223 | EXPECT_EQ(*V[i], Begin[i]); |
224 | |
225 | EXPECT_NE(I, End); |
226 | EXPECT_GT(End, I); |
227 | EXPECT_LT(I, End); |
228 | EXPECT_GE(I, Begin); |
229 | EXPECT_LE(Begin, I); |
230 | |
231 | EXPECT_EQ(i, I - Begin); |
232 | EXPECT_EQ(i, std::distance(Begin, I)); |
233 | EXPECT_EQ(Begin, I - i); |
234 | |
235 | test_iterator K = I++; |
236 | EXPECT_EQ(K, std::prev(I)); |
237 | } |
238 | EXPECT_EQ(End, I); |
239 | } |
240 | |
241 | TEST(PointeeIteratorTest, Range) { |
242 | int A[] = {1, 2, 3, 4}; |
243 | SmallVector<int *, 4> V{&A[0], &A[1], &A[2], &A[3]}; |
244 | |
245 | int I = 0; |
246 | for (int II : make_pointee_range(Range&: V)) |
247 | EXPECT_EQ(A[I++], II); |
248 | } |
249 | |
250 | TEST(PointeeIteratorTest, PointeeType) { |
251 | struct S { |
252 | int X; |
253 | bool operator==(const S &RHS) const { return X == RHS.X; }; |
254 | }; |
255 | S A[] = {S{.X: 0}, S{.X: 1}}; |
256 | SmallVector<S *, 2> V{&A[0], &A[1]}; |
257 | |
258 | pointee_iterator<SmallVectorImpl<S *>::const_iterator, const S> I = V.begin(); |
259 | for (int j = 0; j < 2; ++j, ++I) { |
260 | EXPECT_EQ(*V[j], *I); |
261 | } |
262 | } |
263 | |
264 | TEST(FilterIteratorTest, Lambda) { |
265 | auto IsOdd = [](int N) { return N % 2 == 1; }; |
266 | int A[] = {0, 1, 2, 3, 4, 5, 6}; |
267 | auto Range = make_filter_range(Range&: A, Pred: IsOdd); |
268 | SmallVector<int, 3> Actual(Range.begin(), Range.end()); |
269 | EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); |
270 | } |
271 | |
272 | TEST(FilterIteratorTest, Enumerate) { |
273 | auto IsOdd = [](auto N) { return N.value() % 2 == 1; }; |
274 | int A[] = {0, 1, 2, 3, 4, 5, 6}; |
275 | auto Enumerate = llvm::enumerate(First&: A); |
276 | SmallVector<int> Actual; |
277 | for (const auto &IndexedValue : make_filter_range(Range&: Enumerate, Pred: IsOdd)) |
278 | Actual.push_back(Elt: IndexedValue.value()); |
279 | EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); |
280 | } |
281 | |
282 | TEST(FilterIteratorTest, CallableObject) { |
283 | int Counter = 0; |
284 | struct Callable { |
285 | int &Counter; |
286 | |
287 | Callable(int &Counter) : Counter(Counter) {} |
288 | |
289 | bool operator()(int N) { |
290 | Counter++; |
291 | return N % 2 == 1; |
292 | } |
293 | }; |
294 | Callable IsOdd(Counter); |
295 | int A[] = {0, 1, 2, 3, 4, 5, 6}; |
296 | auto Range = make_filter_range(Range&: A, Pred: IsOdd); |
297 | EXPECT_EQ(2, Counter); |
298 | SmallVector<int, 3> Actual(Range.begin(), Range.end()); |
299 | EXPECT_GE(Counter, 7); |
300 | EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); |
301 | } |
302 | |
303 | TEST(FilterIteratorTest, FunctionPointer) { |
304 | bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; }; |
305 | int A[] = {0, 1, 2, 3, 4, 5, 6}; |
306 | auto Range = make_filter_range(Range&: A, Pred: IsOdd); |
307 | SmallVector<int, 3> Actual(Range.begin(), Range.end()); |
308 | EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); |
309 | } |
310 | |
311 | TEST(FilterIteratorTest, Composition) { |
312 | auto IsOdd = [](int N) { return N % 2 == 1; }; |
313 | std::unique_ptr<int> A[] = {std::make_unique<int>(args: 0), std::make_unique<int>(args: 1), |
314 | std::make_unique<int>(args: 2), std::make_unique<int>(args: 3), |
315 | std::make_unique<int>(args: 4), std::make_unique<int>(args: 5), |
316 | std::make_unique<int>(args: 6)}; |
317 | using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>; |
318 | auto Range = make_filter_range( |
319 | Range: make_range(x: PointeeIterator(std::begin(arr&: A)), y: PointeeIterator(std::end(arr&: A))), |
320 | Pred: IsOdd); |
321 | SmallVector<int, 3> Actual(Range.begin(), Range.end()); |
322 | EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); |
323 | } |
324 | |
325 | TEST(FilterIteratorTest, InputIterator) { |
326 | struct InputIterator |
327 | : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> { |
328 | InputIterator(int *It) : InputIterator::iterator_adaptor_base(It) {} |
329 | }; |
330 | |
331 | auto IsOdd = [](int N) { return N % 2 == 1; }; |
332 | int A[] = {0, 1, 2, 3, 4, 5, 6}; |
333 | auto Range = make_filter_range( |
334 | Range: make_range(x: InputIterator(std::begin(arr&: A)), y: InputIterator(std::end(arr&: A))), |
335 | Pred: IsOdd); |
336 | SmallVector<int, 3> Actual(Range.begin(), Range.end()); |
337 | EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); |
338 | } |
339 | |
340 | TEST(FilterIteratorTest, ReverseFilterRange) { |
341 | auto IsOdd = [](int N) { return N % 2 == 1; }; |
342 | int A[] = {0, 1, 2, 3, 4, 5, 6}; |
343 | |
344 | // Check basic reversal. |
345 | auto Range = reverse(C: make_filter_range(Range&: A, Pred: IsOdd)); |
346 | SmallVector<int, 3> Actual(Range.begin(), Range.end()); |
347 | EXPECT_EQ((SmallVector<int, 3>{5, 3, 1}), Actual); |
348 | |
349 | // Check that the reverse of the reverse is the original. |
350 | auto Range2 = reverse(C: reverse(C: make_filter_range(Range&: A, Pred: IsOdd))); |
351 | SmallVector<int, 3> Actual2(Range2.begin(), Range2.end()); |
352 | EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual2); |
353 | |
354 | // Check empty ranges. |
355 | auto Range3 = reverse(C: make_filter_range(Range: ArrayRef<int>(), Pred: IsOdd)); |
356 | SmallVector<int, 0> Actual3(Range3.begin(), Range3.end()); |
357 | EXPECT_EQ((SmallVector<int, 0>{}), Actual3); |
358 | |
359 | // Check that we don't skip the first element, provided it isn't filtered |
360 | // away. |
361 | auto IsEven = [](int N) { return N % 2 == 0; }; |
362 | auto Range4 = reverse(C: make_filter_range(Range&: A, Pred: IsEven)); |
363 | SmallVector<int, 4> Actual4(Range4.begin(), Range4.end()); |
364 | EXPECT_EQ((SmallVector<int, 4>{6, 4, 2, 0}), Actual4); |
365 | } |
366 | |
367 | TEST(PointerIterator, Basic) { |
368 | int A[] = {1, 2, 3, 4}; |
369 | pointer_iterator<int *> Begin(std::begin(arr&: A)), End(std::end(arr&: A)); |
370 | EXPECT_EQ(A, *Begin); |
371 | ++Begin; |
372 | EXPECT_EQ(A + 1, *Begin); |
373 | ++Begin; |
374 | EXPECT_EQ(A + 2, *Begin); |
375 | ++Begin; |
376 | EXPECT_EQ(A + 3, *Begin); |
377 | ++Begin; |
378 | EXPECT_EQ(Begin, End); |
379 | } |
380 | |
381 | TEST(PointerIterator, Const) { |
382 | int A[] = {1, 2, 3, 4}; |
383 | const pointer_iterator<int *> Begin(std::begin(arr&: A)); |
384 | EXPECT_EQ(A, *Begin); |
385 | EXPECT_EQ(A + 1, std::next(*Begin, 1)); |
386 | EXPECT_EQ(A + 2, std::next(*Begin, 2)); |
387 | EXPECT_EQ(A + 3, std::next(*Begin, 3)); |
388 | EXPECT_EQ(A + 4, std::next(*Begin, 4)); |
389 | } |
390 | |
391 | TEST(PointerIterator, Range) { |
392 | int A[] = {1, 2, 3, 4}; |
393 | int I = 0; |
394 | for (int *P : make_pointer_range(Range&: A)) |
395 | EXPECT_EQ(A + I++, P); |
396 | } |
397 | |
398 | namespace rbegin_detail { |
399 | struct WithFreeRBegin { |
400 | int data[3] = {42, 43, 44}; |
401 | }; |
402 | |
403 | auto rbegin(const WithFreeRBegin &X) { return std::rbegin(arr: X.data); } |
404 | auto rend(const WithFreeRBegin &X) { return std::rend(arr: X.data); } |
405 | } // namespace rbegin_detail |
406 | |
407 | TEST(ReverseTest, ADL) { |
408 | // Check that we can find the rbegin/rend functions via ADL. |
409 | rbegin_detail::WithFreeRBegin Foo; |
410 | EXPECT_THAT(reverse(Foo), ElementsAre(44, 43, 42)); |
411 | } |
412 | |
413 | TEST(ZipIteratorTest, Basic) { |
414 | using namespace std; |
415 | const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9}; |
416 | SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1}; |
417 | const char message[] = "yynyyy\0" ; |
418 | std::array<int, 2> shortArr = {42, 43}; |
419 | |
420 | for (auto tup : zip(t: pi, u&: odd, args: message)) { |
421 | EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); |
422 | EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup)); |
423 | } |
424 | |
425 | // Note the rvalue. |
426 | for (auto tup : zip(t: pi, u: SmallVector<bool, 0>{1, 1, 0, 1, 1})) { |
427 | EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); |
428 | } |
429 | |
430 | // Iterate until we run out elements in the *shortest* range. |
431 | for (auto [idx, elem] : enumerate(First: zip(t&: odd, u&: shortArr))) { |
432 | EXPECT_LT(idx, static_cast<size_t>(2)); |
433 | } |
434 | for (auto [idx, elem] : enumerate(First: zip(t&: shortArr, u&: odd))) { |
435 | EXPECT_LT(idx, static_cast<size_t>(2)); |
436 | } |
437 | } |
438 | |
439 | TEST(ZipIteratorTest, ZipEqualBasic) { |
440 | const SmallVector<unsigned, 6> pi = {3, 1, 4, 1, 5, 8}; |
441 | const SmallVector<bool, 6> vals = {1, 1, 0, 1, 1, 0}; |
442 | unsigned iters = 0; |
443 | |
444 | for (auto [lhs, rhs] : zip_equal(t: vals, u: pi)) { |
445 | EXPECT_EQ(lhs, rhs & 0x01); |
446 | ++iters; |
447 | } |
448 | |
449 | EXPECT_EQ(iters, 6u); |
450 | } |
451 | |
452 | template <typename T> |
453 | constexpr bool IsConstRef = |
454 | std::is_reference_v<T> && std::is_const_v<std::remove_reference_t<T>>; |
455 | |
456 | template <typename T> |
457 | constexpr bool IsBoolConstRef = |
458 | std::is_same_v<llvm::remove_cvref_t<T>, std::vector<bool>::const_reference>; |
459 | |
460 | /// Returns a `const` copy of the passed value. The `const` on the returned |
461 | /// value is intentional here so that `MakeConst` can be used in range-for |
462 | /// loops. |
463 | template <typename T> const T MakeConst(T &&value) { |
464 | return std::forward<T>(value); |
465 | } |
466 | |
467 | TEST(ZipIteratorTest, ZipEqualConstCorrectness) { |
468 | const std::vector<unsigned> c_first = {3, 1, 4}; |
469 | std::vector<unsigned> first = c_first; |
470 | const SmallVector<bool> c_second = {1, 1, 0}; |
471 | SmallVector<bool> second = c_second; |
472 | |
473 | for (auto [a, b, c, d] : zip_equal(t: c_first, u&: first, args: c_second, args&: second)) { |
474 | b = 0; |
475 | d = true; |
476 | static_assert(IsConstRef<decltype(a)>); |
477 | static_assert(!IsConstRef<decltype(b)>); |
478 | static_assert(IsConstRef<decltype(c)>); |
479 | static_assert(!IsConstRef<decltype(d)>); |
480 | } |
481 | |
482 | EXPECT_THAT(first, ElementsAre(0, 0, 0)); |
483 | EXPECT_THAT(second, ElementsAre(true, true, true)); |
484 | |
485 | std::vector<bool> nemesis = {true, false, true}; |
486 | const std::vector<bool> c_nemesis = nemesis; |
487 | |
488 | for (auto &&[a, b, c, d] : zip_equal(t&: first, u: c_first, args&: nemesis, args: c_nemesis)) { |
489 | a = 2; |
490 | c = true; |
491 | static_assert(!IsConstRef<decltype(a)>); |
492 | static_assert(IsConstRef<decltype(b)>); |
493 | static_assert(!IsBoolConstRef<decltype(c)>); |
494 | static_assert(IsBoolConstRef<decltype(d)>); |
495 | } |
496 | |
497 | EXPECT_THAT(first, ElementsAre(2, 2, 2)); |
498 | EXPECT_THAT(nemesis, ElementsAre(true, true, true)); |
499 | |
500 | unsigned iters = 0; |
501 | for (const auto &[a, b, c, d] : |
502 | zip_equal(t&: first, u: c_first, args&: nemesis, args: c_nemesis)) { |
503 | static_assert(!IsConstRef<decltype(a)>); |
504 | static_assert(IsConstRef<decltype(b)>); |
505 | static_assert(!IsBoolConstRef<decltype(c)>); |
506 | static_assert(IsBoolConstRef<decltype(d)>); |
507 | ++iters; |
508 | } |
509 | EXPECT_EQ(iters, 3u); |
510 | iters = 0; |
511 | |
512 | for (const auto &[a, b, c, d] : |
513 | MakeConst(value: zip_equal(t&: first, u: c_first, args&: nemesis, args: c_nemesis))) { |
514 | static_assert(!IsConstRef<decltype(a)>); |
515 | static_assert(IsConstRef<decltype(b)>); |
516 | static_assert(!IsBoolConstRef<decltype(c)>); |
517 | static_assert(IsBoolConstRef<decltype(d)>); |
518 | ++iters; |
519 | } |
520 | EXPECT_EQ(iters, 3u); |
521 | } |
522 | |
523 | TEST(ZipIteratorTest, ZipEqualTemporaries) { |
524 | unsigned iters = 0; |
525 | |
526 | // These temporary ranges get moved into the `tuple<...> storage;` inside |
527 | // `zippy`. From then on, we can use references obtained from this storage to |
528 | // access them. This does not rely on any lifetime extensions on the |
529 | // temporaries passed to `zip_equal`. |
530 | for (auto [a, b, c] : zip_equal(t: SmallVector<int>{1, 2, 3}, u: std::string("abc" ), |
531 | args: std::vector<bool>{true, false, true})) { |
532 | a = 3; |
533 | b = 'c'; |
534 | c = false; |
535 | static_assert(!IsConstRef<decltype(a)>); |
536 | static_assert(!IsConstRef<decltype(b)>); |
537 | static_assert(!IsBoolConstRef<decltype(c)>); |
538 | ++iters; |
539 | } |
540 | EXPECT_EQ(iters, 3u); |
541 | iters = 0; |
542 | |
543 | for (auto [a, b, c] : |
544 | MakeConst(value: zip_equal(t: SmallVector<int>{1, 2, 3}, u: std::string("abc" ), |
545 | args: std::vector<bool>{true, false, true}))) { |
546 | static_assert(IsConstRef<decltype(a)>); |
547 | static_assert(IsConstRef<decltype(b)>); |
548 | static_assert(IsBoolConstRef<decltype(c)>); |
549 | ++iters; |
550 | } |
551 | EXPECT_EQ(iters, 3u); |
552 | } |
553 | |
554 | #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST |
555 | // Check that an assertion is triggered when ranges passed to `zip_equal` differ |
556 | // in length. |
557 | TEST(ZipIteratorTest, ZipEqualNotEqual) { |
558 | const SmallVector<unsigned, 6> pi = {3, 1, 4, 1, 5, 8}; |
559 | const SmallVector<bool, 2> vals = {1, 1}; |
560 | |
561 | EXPECT_DEATH(zip_equal(pi, vals), "Iteratees do not have equal length" ); |
562 | EXPECT_DEATH(zip_equal(vals, pi), "Iteratees do not have equal length" ); |
563 | EXPECT_DEATH(zip_equal(pi, pi, vals), "Iteratees do not have equal length" ); |
564 | EXPECT_DEATH(zip_equal(vals, vals, pi), "Iteratees do not have equal length" ); |
565 | } |
566 | #endif |
567 | |
568 | TEST(ZipIteratorTest, ZipFirstBasic) { |
569 | using namespace std; |
570 | const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9}; |
571 | unsigned iters = 0; |
572 | |
573 | for (auto tup : zip_first(t: SmallVector<bool, 0>{1, 1, 0, 1}, u: pi)) { |
574 | EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01); |
575 | iters += 1; |
576 | } |
577 | |
578 | EXPECT_EQ(iters, 4u); |
579 | } |
580 | |
581 | #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST |
582 | // Make sure that we can detect when the first range is not the shortest. |
583 | TEST(ZipIteratorTest, ZipFirstNotShortest) { |
584 | const std::array<unsigned, 6> longer = {}; |
585 | const std::array<unsigned, 4> shorter = {}; |
586 | |
587 | EXPECT_DEATH(zip_first(longer, shorter), |
588 | "First iteratee is not the shortest" ); |
589 | EXPECT_DEATH(zip_first(longer, shorter, longer), |
590 | "First iteratee is not the shortest" ); |
591 | EXPECT_DEATH(zip_first(longer, longer, shorter), |
592 | "First iteratee is not the shortest" ); |
593 | } |
594 | #endif |
595 | |
596 | TEST(ZipIteratorTest, ZipLongestBasic) { |
597 | using namespace std; |
598 | const vector<unsigned> pi{3, 1, 4, 1, 5, 9}; |
599 | const vector<StringRef> e{"2" , "7" , "1" , "8" }; |
600 | |
601 | { |
602 | // Check left range longer than right. |
603 | const vector<tuple<optional<unsigned>, optional<StringRef>>> expected{ |
604 | make_tuple(args: 3, args: StringRef("2" )), make_tuple(args: 1, args: StringRef("7" )), |
605 | make_tuple(args: 4, args: StringRef("1" )), make_tuple(args: 1, args: StringRef("8" )), |
606 | make_tuple(args: 5, args: std::nullopt), make_tuple(args: 9, args: std::nullopt)}; |
607 | size_t iters = 0; |
608 | for (auto tup : zip_longest(t: pi, u: e)) { |
609 | EXPECT_EQ(tup, expected[iters]); |
610 | iters += 1; |
611 | } |
612 | EXPECT_EQ(iters, expected.size()); |
613 | } |
614 | |
615 | { |
616 | // Check right range longer than left. |
617 | const vector<tuple<optional<StringRef>, optional<unsigned>>> expected{ |
618 | make_tuple(args: StringRef("2" ), args: 3), make_tuple(args: StringRef("7" ), args: 1), |
619 | make_tuple(args: StringRef("1" ), args: 4), make_tuple(args: StringRef("8" ), args: 1), |
620 | make_tuple(args: std::nullopt, args: 5), make_tuple(args: std::nullopt, args: 9)}; |
621 | size_t iters = 0; |
622 | for (auto tup : zip_longest(t: e, u: pi)) { |
623 | EXPECT_EQ(tup, expected[iters]); |
624 | iters += 1; |
625 | } |
626 | EXPECT_EQ(iters, expected.size()); |
627 | } |
628 | } |
629 | |
630 | TEST(ZipIteratorTest, Mutability) { |
631 | using namespace std; |
632 | const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9}; |
633 | char message[] = "hello zip\0" ; |
634 | |
635 | for (auto tup : zip(t: pi, u&: message, args&: message)) { |
636 | EXPECT_EQ(get<1>(tup), get<2>(tup)); |
637 | get<2>(t&: tup) = get<0>(t&: tup) & 0x01 ? 'y' : 'n'; |
638 | } |
639 | |
640 | // note the rvalue |
641 | for (auto tup : zip(t&: message, u: "yynyyyzip\0" )) { |
642 | EXPECT_EQ(get<0>(tup), get<1>(tup)); |
643 | } |
644 | } |
645 | |
646 | TEST(ZipIteratorTest, ZipFirstMutability) { |
647 | using namespace std; |
648 | vector<unsigned> pi{3, 1, 4, 1, 5, 9}; |
649 | unsigned iters = 0; |
650 | |
651 | for (auto tup : zip_first(t: SmallVector<bool, 0>{1, 1, 0, 1}, u&: pi)) { |
652 | get<1>(t&: tup) = get<0>(t&: tup); |
653 | iters += 1; |
654 | } |
655 | |
656 | EXPECT_EQ(iters, 4u); |
657 | |
658 | for (auto tup : zip_first(t: SmallVector<bool, 0>{1, 1, 0, 1}, u&: pi)) { |
659 | EXPECT_EQ(get<0>(tup), get<1>(tup)); |
660 | } |
661 | } |
662 | |
663 | TEST(ZipIteratorTest, Filter) { |
664 | using namespace std; |
665 | vector<unsigned> pi{3, 1, 4, 1, 5, 9}; |
666 | |
667 | unsigned iters = 0; |
668 | // pi is length 6, but the zip RHS is length 7. |
669 | auto zipped = zip_first(t&: pi, u: vector<bool>{1, 1, 0, 1, 1, 1, 0}); |
670 | for (auto tup : make_filter_range( |
671 | Range&: zipped, Pred: [](decltype(zipped)::value_type t) { return get<1>(t&: t); })) { |
672 | EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); |
673 | get<0>(t&: tup) += 1; |
674 | iters += 1; |
675 | } |
676 | |
677 | // Should have skipped pi[2]. |
678 | EXPECT_EQ(iters, 5u); |
679 | |
680 | // Ensure that in-place mutation works. |
681 | EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; })); |
682 | } |
683 | |
684 | TEST(ZipIteratorTest, Reverse) { |
685 | using namespace std; |
686 | vector<unsigned> ascending{0, 1, 2, 3, 4, 5}; |
687 | |
688 | auto zipped = zip_first(t&: ascending, u: vector<bool>{0, 1, 0, 1, 0, 1}); |
689 | unsigned last = 6; |
690 | for (auto tup : reverse(C&: zipped)) { |
691 | // Check that this is in reverse. |
692 | EXPECT_LT(get<0>(tup), last); |
693 | last = get<0>(t&: tup); |
694 | EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup)); |
695 | } |
696 | |
697 | auto odds = [](decltype(zipped)::value_type tup) { return get<1>(t&: tup); }; |
698 | last = 6; |
699 | for (auto tup : make_filter_range(Range: reverse(C&: zipped), Pred: odds)) { |
700 | EXPECT_LT(get<0>(tup), last); |
701 | last = get<0>(t&: tup); |
702 | EXPECT_TRUE(get<0>(tup) & 0x01); |
703 | get<0>(t&: tup) += 1; |
704 | } |
705 | |
706 | // Ensure that in-place mutation works. |
707 | EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; })); |
708 | } |
709 | |
710 | // Int iterator that keeps track of the number of its copies. |
711 | struct CountingIntIterator : IntIterator { |
712 | unsigned *cnt; |
713 | |
714 | CountingIntIterator(int *it, unsigned &counter) |
715 | : IntIterator(it), cnt(&counter) {} |
716 | |
717 | CountingIntIterator(const CountingIntIterator &other) |
718 | : IntIterator(other.I), cnt(other.cnt) { |
719 | ++(*cnt); |
720 | } |
721 | CountingIntIterator &operator=(const CountingIntIterator &other) { |
722 | this->I = other.I; |
723 | this->cnt = other.cnt; |
724 | ++(*cnt); |
725 | return *this; |
726 | } |
727 | }; |
728 | |
729 | // Check that the iterators do not get copied with each `zippy` iterator |
730 | // increment. |
731 | TEST(ZipIteratorTest, IteratorCopies) { |
732 | std::vector<int> ints(1000, 42); |
733 | unsigned total_copy_count = 0; |
734 | CountingIntIterator begin(ints.data(), total_copy_count); |
735 | CountingIntIterator end(ints.data() + ints.size(), total_copy_count); |
736 | |
737 | size_t iters = 0; |
738 | auto zippy = zip_equal(t&: ints, u: llvm::make_range(x: begin, y: end)); |
739 | const unsigned creation_copy_count = total_copy_count; |
740 | |
741 | for (auto [a, b] : zippy) { |
742 | EXPECT_EQ(a, b); |
743 | ++iters; |
744 | } |
745 | EXPECT_EQ(iters, ints.size()); |
746 | |
747 | // We expect the number of copies to be much smaller than the number of loop |
748 | // iterations. |
749 | unsigned loop_copy_count = total_copy_count - creation_copy_count; |
750 | EXPECT_LT(loop_copy_count, 10u); |
751 | } |
752 | |
753 | TEST(RangeTest, Distance) { |
754 | std::vector<int> v1; |
755 | std::vector<int> v2{1, 2, 3}; |
756 | |
757 | EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1)); |
758 | EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2)); |
759 | } |
760 | |
761 | TEST(RangeSizeTest, CommonRangeTypes) { |
762 | SmallVector<int> v1 = {1, 2, 3}; |
763 | EXPECT_EQ(range_size(v1), 3u); |
764 | |
765 | std::map<int, int> m1 = {{1, 1}, {2, 2}}; |
766 | EXPECT_EQ(range_size(m1), 2u); |
767 | |
768 | auto it_range = llvm::make_range(x: m1.begin(), y: m1.end()); |
769 | EXPECT_EQ(range_size(it_range), 2u); |
770 | |
771 | static constexpr int c_arr[5] = {}; |
772 | static_assert(range_size(Range: c_arr) == 5u); |
773 | |
774 | static constexpr std::array<int, 6> cpp_arr = {}; |
775 | static_assert(range_size(Range: cpp_arr) == 6u); |
776 | } |
777 | |
778 | struct FooWithMemberSize { |
779 | size_t size() const { return 42; } |
780 | auto begin() { return Data.begin(); } |
781 | auto end() { return Data.end(); } |
782 | |
783 | std::set<int> Data; |
784 | }; |
785 | |
786 | TEST(RangeSizeTest, MemberSize) { |
787 | // Make sure that member `.size()` is preferred over the free fuction and |
788 | // `std::distance`. |
789 | FooWithMemberSize container; |
790 | EXPECT_EQ(range_size(container), 42u); |
791 | } |
792 | |
793 | struct FooWithFreeSize { |
794 | friend size_t size(const FooWithFreeSize &) { return 13; } |
795 | auto begin() { return Data.begin(); } |
796 | auto end() { return Data.end(); } |
797 | |
798 | std::set<int> Data; |
799 | }; |
800 | |
801 | TEST(RangeSizeTest, FreeSize) { |
802 | // Make sure that `size(x)` is preferred over `std::distance`. |
803 | FooWithFreeSize container; |
804 | EXPECT_EQ(range_size(container), 13u); |
805 | } |
806 | |
807 | struct FooWithDistance { |
808 | auto begin() { return Data.begin(); } |
809 | auto end() { return Data.end(); } |
810 | |
811 | std::set<int> Data; |
812 | }; |
813 | |
814 | TEST(RangeSizeTest, Distance) { |
815 | // Make sure that we can fall back to `std::distance` even the iterator is not |
816 | // random-access. |
817 | FooWithDistance container; |
818 | EXPECT_EQ(range_size(container), 0u); |
819 | container.Data = {1, 2, 3, 4}; |
820 | EXPECT_EQ(range_size(container), 4u); |
821 | } |
822 | } // anonymous namespace |
823 | |