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
20using namespace llvm;
21using testing::ElementsAre;
22
23namespace {
24
25template <int> struct Shadow;
26
27struct WeirdIter
28 : llvm::iterator_facade_base<WeirdIter, std::input_iterator_tag, Shadow<0>,
29 Shadow<1>, Shadow<2>, Shadow<3>> {};
30
31struct AdaptedIter : iterator_adaptor_base<AdaptedIter, WeirdIter> {};
32
33// Test that iterator_adaptor_base forwards typedefs, if value_type is
34// unchanged.
35static_assert(std::is_same_v<typename AdaptedIter::value_type, Shadow<0>>, "");
36static_assert(std::is_same_v<typename AdaptedIter::difference_type, Shadow<1>>,
37 "");
38static_assert(std::is_same_v<typename AdaptedIter::pointer, Shadow<2>>, "");
39static_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
44using RandomAccessIter = SmallVectorImpl<int*>::iterator;
45using BidiIter = ilist<int*>::iterator;
46
47template<class T>
48using pointee_iterator_defaulted = pointee_iterator<T>;
49template<class T>
50using pointer_iterator_defaulted = pointer_iterator<T>;
51
52// Ensures that an iterator and its adaptation have the same iterator_category.
53template<template<typename> class A, typename It>
54using 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.
59template <class T>
60struct PointerWrapper : public iterator_adaptor_base<PointerWrapper<T>, T *> {
61 PointerWrapper(T *I) : PointerWrapper::iterator_adaptor_base(I) {}
62};
63struct IntProxy {
64 int &I;
65 IntProxy(int &I) : I(I) {}
66 void operator=(int NewValue) { I = NewValue; }
67};
68struct ConstIntProxy {
69 const int &I;
70 ConstIntProxy(const int &I) : I(I) {}
71};
72template <class T, class ProxyT>
73struct 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};
79using IntIterator = PointerWrapper<int>;
80using ConstIntIterator = PointerWrapper<const int>;
81using IntProxyIterator = PointerProxyWrapper<int, IntProxy>;
82using 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.
88static_assert(&IntIterator::operator* == &IntIterator::operator*, "");
89static_assert(&IntIterator::operator-> == &IntIterator::operator->, "");
90static_assert(&IntIterator::operator[] == &IntIterator::operator[], "");
91
92template <class T, std::enable_if_t<std::is_assignable_v<T, int>, bool> = false>
93constexpr bool canAssignFromInt(T &&) {
94 return true;
95}
96template <class T,
97 std::enable_if_t<!std::is_assignable_v<T, int>, bool> = false>
98constexpr bool canAssignFromInt(T &&) {
99 return false;
100}
101
102TEST(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
147static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
148 RandomAccessIter>::value, "");
149static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
150 BidiIter>::value, "");
151// pointeR_iterator
152static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,
153 RandomAccessIter>::value, "");
154static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,
155 BidiIter>::value, "");
156
157TEST(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
199TEST(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
241TEST(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
250TEST(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
264TEST(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
272TEST(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
282TEST(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
303TEST(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
311TEST(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
325TEST(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
340TEST(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
367TEST(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
381TEST(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
391TEST(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
398namespace rbegin_detail {
399struct WithFreeRBegin {
400 int data[3] = {42, 43, 44};
401};
402
403auto rbegin(const WithFreeRBegin &X) { return std::rbegin(arr: X.data); }
404auto rend(const WithFreeRBegin &X) { return std::rend(arr: X.data); }
405} // namespace rbegin_detail
406
407TEST(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
413TEST(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
439TEST(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
452template <typename T>
453constexpr bool IsConstRef =
454 std::is_reference_v<T> && std::is_const_v<std::remove_reference_t<T>>;
455
456template <typename T>
457constexpr 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.
463template <typename T> const T MakeConst(T &&value) {
464 return std::forward<T>(value);
465}
466
467TEST(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
523TEST(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.
557TEST(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
568TEST(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.
583TEST(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
596TEST(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
630TEST(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
646TEST(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
663TEST(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
684TEST(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.
711struct 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.
731TEST(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
753TEST(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
761TEST(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
778struct 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
786TEST(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
793struct 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
801TEST(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
807struct FooWithDistance {
808 auto begin() { return Data.begin(); }
809 auto end() { return Data.end(); }
810
811 std::set<int> Data;
812};
813
814TEST(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

source code of llvm/unittests/ADT/IteratorTest.cpp