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/ilist.h"
10 #include "llvm/ADT/iterator.h"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/SmallVector.h"
14 #include "gtest/gtest.h"
15 
16 using namespace llvm;
17 
18 namespace {
19 
20 template <int> struct Shadow;
21 
22 struct WeirdIter : std::iterator<std::input_iterator_tag, Shadow<0>, Shadow<1>,
23                                  Shadow<2>, Shadow<3>> {};
24 
25 struct AdaptedIter : iterator_adaptor_base<AdaptedIter, WeirdIter> {};
26 
27 // Test that iterator_adaptor_base forwards typedefs, if value_type is
28 // unchanged.
29 static_assert(std::is_same<typename AdaptedIter::value_type, Shadow<0>>::value,
30               "");
31 static_assert(
32     std::is_same<typename AdaptedIter::difference_type, Shadow<1>>::value, "");
33 static_assert(std::is_same<typename AdaptedIter::pointer, Shadow<2>>::value,
34               "");
35 static_assert(std::is_same<typename AdaptedIter::reference, Shadow<3>>::value,
36               "");
37 
38 // Ensure that pointe{e,r}_iterator adaptors correctly forward the category of
39 // the underlying iterator.
40 
41 using RandomAccessIter = SmallVectorImpl<int*>::iterator;
42 using BidiIter = ilist<int*>::iterator;
43 
44 template<class T>
45 using pointee_iterator_defaulted = pointee_iterator<T>;
46 template<class T>
47 using pointer_iterator_defaulted = pointer_iterator<T>;
48 
49 // Ensures that an iterator and its adaptation have the same iterator_category.
50 template<template<typename> class A, typename It>
51 using IsAdaptedIterCategorySame =
52   std::is_same<typename std::iterator_traits<It>::iterator_category,
53                typename std::iterator_traits<A<It>>::iterator_category>;
54 
55 // pointeE_iterator
56 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
57                                         RandomAccessIter>::value, "");
58 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
59                                         BidiIter>::value, "");
60 // pointeR_iterator
61 static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,
62                                         RandomAccessIter>::value, "");
63 static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,
64                                         BidiIter>::value, "");
65 
66 TEST(PointeeIteratorTest, Basic) {
67   int arr[4] = {1, 2, 3, 4};
68   SmallVector<int *, 4> V;
69   V.push_back(&arr[0]);
70   V.push_back(&arr[1]);
71   V.push_back(&arr[2]);
72   V.push_back(&arr[3]);
73 
74   typedef pointee_iterator<SmallVectorImpl<int *>::const_iterator>
75       test_iterator;
76 
77   test_iterator Begin, End;
78   Begin = V.begin();
79   End = test_iterator(V.end());
80 
81   test_iterator I = Begin;
82   for (int i = 0; i < 4; ++i) {
83     EXPECT_EQ(*V[i], *I);
84 
85     EXPECT_EQ(I, Begin + i);
86     EXPECT_EQ(I, std::next(Begin, i));
87     test_iterator J = Begin;
88     J += i;
89     EXPECT_EQ(I, J);
90     EXPECT_EQ(*V[i], Begin[i]);
91 
92     EXPECT_NE(I, End);
93     EXPECT_GT(End, I);
94     EXPECT_LT(I, End);
95     EXPECT_GE(I, Begin);
96     EXPECT_LE(Begin, I);
97 
98     EXPECT_EQ(i, I - Begin);
99     EXPECT_EQ(i, std::distance(Begin, I));
100     EXPECT_EQ(Begin, I - i);
101 
102     test_iterator K = I++;
103     EXPECT_EQ(K, std::prev(I));
104   }
105   EXPECT_EQ(End, I);
106 }
107 
108 TEST(PointeeIteratorTest, SmartPointer) {
109   SmallVector<std::unique_ptr<int>, 4> V;
110   V.push_back(std::make_unique<int>(1));
111   V.push_back(std::make_unique<int>(2));
112   V.push_back(std::make_unique<int>(3));
113   V.push_back(std::make_unique<int>(4));
114 
115   typedef pointee_iterator<
116       SmallVectorImpl<std::unique_ptr<int>>::const_iterator>
117       test_iterator;
118 
119   test_iterator Begin, End;
120   Begin = V.begin();
121   End = test_iterator(V.end());
122 
123   test_iterator I = Begin;
124   for (int i = 0; i < 4; ++i) {
125     EXPECT_EQ(*V[i], *I);
126 
127     EXPECT_EQ(I, Begin + i);
128     EXPECT_EQ(I, std::next(Begin, i));
129     test_iterator J = Begin;
130     J += i;
131     EXPECT_EQ(I, J);
132     EXPECT_EQ(*V[i], Begin[i]);
133 
134     EXPECT_NE(I, End);
135     EXPECT_GT(End, I);
136     EXPECT_LT(I, End);
137     EXPECT_GE(I, Begin);
138     EXPECT_LE(Begin, I);
139 
140     EXPECT_EQ(i, I - Begin);
141     EXPECT_EQ(i, std::distance(Begin, I));
142     EXPECT_EQ(Begin, I - i);
143 
144     test_iterator K = I++;
145     EXPECT_EQ(K, std::prev(I));
146   }
147   EXPECT_EQ(End, I);
148 }
149 
150 TEST(PointeeIteratorTest, Range) {
151   int A[] = {1, 2, 3, 4};
152   SmallVector<int *, 4> V{&A[0], &A[1], &A[2], &A[3]};
153 
154   int I = 0;
155   for (int II : make_pointee_range(V))
156     EXPECT_EQ(A[I++], II);
157 }
158 
159 TEST(PointeeIteratorTest, PointeeType) {
160   struct S {
161     int X;
162     bool operator==(const S &RHS) const { return X == RHS.X; };
163   };
164   S A[] = {S{0}, S{1}};
165   SmallVector<S *, 2> V{&A[0], &A[1]};
166 
167   pointee_iterator<SmallVectorImpl<S *>::const_iterator, const S> I = V.begin();
168   for (int j = 0; j < 2; ++j, ++I) {
169     EXPECT_EQ(*V[j], *I);
170   }
171 }
172 
173 TEST(FilterIteratorTest, Lambda) {
174   auto IsOdd = [](int N) { return N % 2 == 1; };
175   int A[] = {0, 1, 2, 3, 4, 5, 6};
176   auto Range = make_filter_range(A, IsOdd);
177   SmallVector<int, 3> Actual(Range.begin(), Range.end());
178   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
179 }
180 
181 TEST(FilterIteratorTest, CallableObject) {
182   int Counter = 0;
183   struct Callable {
184     int &Counter;
185 
186     Callable(int &Counter) : Counter(Counter) {}
187 
188     bool operator()(int N) {
189       Counter++;
190       return N % 2 == 1;
191     }
192   };
193   Callable IsOdd(Counter);
194   int A[] = {0, 1, 2, 3, 4, 5, 6};
195   auto Range = make_filter_range(A, IsOdd);
196   EXPECT_EQ(2, Counter);
197   SmallVector<int, 3> Actual(Range.begin(), Range.end());
198   EXPECT_GE(Counter, 7);
199   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
200 }
201 
202 TEST(FilterIteratorTest, FunctionPointer) {
203   bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; };
204   int A[] = {0, 1, 2, 3, 4, 5, 6};
205   auto Range = make_filter_range(A, IsOdd);
206   SmallVector<int, 3> Actual(Range.begin(), Range.end());
207   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
208 }
209 
210 TEST(FilterIteratorTest, Composition) {
211   auto IsOdd = [](int N) { return N % 2 == 1; };
212   std::unique_ptr<int> A[] = {std::make_unique<int>(0), std::make_unique<int>(1),
213                               std::make_unique<int>(2), std::make_unique<int>(3),
214                               std::make_unique<int>(4), std::make_unique<int>(5),
215                               std::make_unique<int>(6)};
216   using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>;
217   auto Range = make_filter_range(
218       make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))),
219       IsOdd);
220   SmallVector<int, 3> Actual(Range.begin(), Range.end());
221   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
222 }
223 
224 TEST(FilterIteratorTest, InputIterator) {
225   struct InputIterator
226       : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> {
227     using BaseT =
228         iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag>;
229 
230     InputIterator(int *It) : BaseT(It) {}
231   };
232 
233   auto IsOdd = [](int N) { return N % 2 == 1; };
234   int A[] = {0, 1, 2, 3, 4, 5, 6};
235   auto Range = make_filter_range(
236       make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))),
237       IsOdd);
238   SmallVector<int, 3> Actual(Range.begin(), Range.end());
239   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
240 }
241 
242 TEST(FilterIteratorTest, ReverseFilterRange) {
243   auto IsOdd = [](int N) { return N % 2 == 1; };
244   int A[] = {0, 1, 2, 3, 4, 5, 6};
245 
246   // Check basic reversal.
247   auto Range = reverse(make_filter_range(A, IsOdd));
248   SmallVector<int, 3> Actual(Range.begin(), Range.end());
249   EXPECT_EQ((SmallVector<int, 3>{5, 3, 1}), Actual);
250 
251   // Check that the reverse of the reverse is the original.
252   auto Range2 = reverse(reverse(make_filter_range(A, IsOdd)));
253   SmallVector<int, 3> Actual2(Range2.begin(), Range2.end());
254   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual2);
255 
256   // Check empty ranges.
257   auto Range3 = reverse(make_filter_range(ArrayRef<int>(), IsOdd));
258   SmallVector<int, 0> Actual3(Range3.begin(), Range3.end());
259   EXPECT_EQ((SmallVector<int, 0>{}), Actual3);
260 
261   // Check that we don't skip the first element, provided it isn't filtered
262   // away.
263   auto IsEven = [](int N) { return N % 2 == 0; };
264   auto Range4 = reverse(make_filter_range(A, IsEven));
265   SmallVector<int, 4> Actual4(Range4.begin(), Range4.end());
266   EXPECT_EQ((SmallVector<int, 4>{6, 4, 2, 0}), Actual4);
267 }
268 
269 TEST(PointerIterator, Basic) {
270   int A[] = {1, 2, 3, 4};
271   pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A));
272   EXPECT_EQ(A, *Begin);
273   ++Begin;
274   EXPECT_EQ(A + 1, *Begin);
275   ++Begin;
276   EXPECT_EQ(A + 2, *Begin);
277   ++Begin;
278   EXPECT_EQ(A + 3, *Begin);
279   ++Begin;
280   EXPECT_EQ(Begin, End);
281 }
282 
283 TEST(PointerIterator, Const) {
284   int A[] = {1, 2, 3, 4};
285   const pointer_iterator<int *> Begin(std::begin(A));
286   EXPECT_EQ(A, *Begin);
287   EXPECT_EQ(A + 1, std::next(*Begin, 1));
288   EXPECT_EQ(A + 2, std::next(*Begin, 2));
289   EXPECT_EQ(A + 3, std::next(*Begin, 3));
290   EXPECT_EQ(A + 4, std::next(*Begin, 4));
291 }
292 
293 TEST(PointerIterator, Range) {
294   int A[] = {1, 2, 3, 4};
295   int I = 0;
296   for (int *P : make_pointer_range(A))
297     EXPECT_EQ(A + I++, P);
298 }
299 
300 TEST(ZipIteratorTest, Basic) {
301   using namespace std;
302   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
303   SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};
304   const char message[] = "yynyyy\0";
305 
306   for (auto tup : zip(pi, odd, message)) {
307     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
308     EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup));
309   }
310 
311   // note the rvalue
312   for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) {
313     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
314   }
315 }
316 
317 TEST(ZipIteratorTest, ZipFirstBasic) {
318   using namespace std;
319   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
320   unsigned iters = 0;
321 
322   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
323     EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01);
324     iters += 1;
325   }
326 
327   EXPECT_EQ(iters, 4u);
328 }
329 
330 TEST(ZipIteratorTest, ZipLongestBasic) {
331   using namespace std;
332   const vector<unsigned> pi{3, 1, 4, 1, 5, 9};
333   const vector<StringRef> e{"2", "7", "1", "8"};
334 
335   {
336     // Check left range longer than right.
337     const vector<tuple<Optional<unsigned>, Optional<StringRef>>> expected{
338         make_tuple(3, StringRef("2")), make_tuple(1, StringRef("7")),
339         make_tuple(4, StringRef("1")), make_tuple(1, StringRef("8")),
340         make_tuple(5, None),           make_tuple(9, None)};
341     size_t iters = 0;
342     for (auto tup : zip_longest(pi, e)) {
343       EXPECT_EQ(tup, expected[iters]);
344       iters += 1;
345     }
346     EXPECT_EQ(iters, expected.size());
347   }
348 
349   {
350     // Check right range longer than left.
351     const vector<tuple<Optional<StringRef>, Optional<unsigned>>> expected{
352         make_tuple(StringRef("2"), 3), make_tuple(StringRef("7"), 1),
353         make_tuple(StringRef("1"), 4), make_tuple(StringRef("8"), 1),
354         make_tuple(None, 5),           make_tuple(None, 9)};
355     size_t iters = 0;
356     for (auto tup : zip_longest(e, pi)) {
357       EXPECT_EQ(tup, expected[iters]);
358       iters += 1;
359     }
360     EXPECT_EQ(iters, expected.size());
361   }
362 }
363 
364 TEST(ZipIteratorTest, Mutability) {
365   using namespace std;
366   const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9};
367   char message[] = "hello zip\0";
368 
369   for (auto tup : zip(pi, message, message)) {
370     EXPECT_EQ(get<1>(tup), get<2>(tup));
371     get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n';
372   }
373 
374   // note the rvalue
375   for (auto tup : zip(message, "yynyyyzip\0")) {
376     EXPECT_EQ(get<0>(tup), get<1>(tup));
377   }
378 }
379 
380 TEST(ZipIteratorTest, ZipFirstMutability) {
381   using namespace std;
382   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
383   unsigned iters = 0;
384 
385   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
386     get<1>(tup) = get<0>(tup);
387     iters += 1;
388   }
389 
390   EXPECT_EQ(iters, 4u);
391 
392   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
393     EXPECT_EQ(get<0>(tup), get<1>(tup));
394   }
395 }
396 
397 TEST(ZipIteratorTest, Filter) {
398   using namespace std;
399   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
400 
401   unsigned iters = 0;
402   // pi is length 6, but the zip RHS is length 7.
403   auto zipped = zip_first(pi, vector<bool>{1, 1, 0, 1, 1, 1, 0});
404   for (auto tup : make_filter_range(
405            zipped, [](decltype(zipped)::value_type t) { return get<1>(t); })) {
406     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
407     get<0>(tup) += 1;
408     iters += 1;
409   }
410 
411   // Should have skipped pi[2].
412   EXPECT_EQ(iters, 5u);
413 
414   // Ensure that in-place mutation works.
415   EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; }));
416 }
417 
418 TEST(ZipIteratorTest, Reverse) {
419   using namespace std;
420   vector<unsigned> ascending{0, 1, 2, 3, 4, 5};
421 
422   auto zipped = zip_first(ascending, vector<bool>{0, 1, 0, 1, 0, 1});
423   unsigned last = 6;
424   for (auto tup : reverse(zipped)) {
425     // Check that this is in reverse.
426     EXPECT_LT(get<0>(tup), last);
427     last = get<0>(tup);
428     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
429   }
430 
431   auto odds = [](decltype(zipped)::value_type tup) { return get<1>(tup); };
432   last = 6;
433   for (auto tup : make_filter_range(reverse(zipped), odds)) {
434     EXPECT_LT(get<0>(tup), last);
435     last = get<0>(tup);
436     EXPECT_TRUE(get<0>(tup) & 0x01);
437     get<0>(tup) += 1;
438   }
439 
440   // Ensure that in-place mutation works.
441   EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; }));
442 }
443 
444 TEST(RangeTest, Distance) {
445   std::vector<int> v1;
446   std::vector<int> v2{1, 2, 3};
447 
448   EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1));
449   EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2));
450 }
451 
452 TEST(IteratorRangeTest, DropBegin) {
453   SmallVector<int, 5> vec{0, 1, 2, 3, 4};
454 
455   for (int n = 0; n < 5; ++n) {
456     int i = n;
457     for (auto &v : drop_begin(vec, n)) {
458       EXPECT_EQ(v, i);
459       i += 1;
460     }
461     EXPECT_EQ(i, 5);
462   }
463 }
464 
465 } // anonymous namespace
466