1 //===- IteratorTest.cpp - Unit tests for iterator utilities ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/ADT/iterator.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/ADT/SmallVector.h"
13 #include "gtest/gtest.h"
14 
15 using namespace llvm;
16 
17 namespace {
18 
19 template <int> struct Shadow;
20 
21 struct WeirdIter : std::iterator<std::input_iterator_tag, Shadow<0>, Shadow<1>,
22                                  Shadow<2>, Shadow<3>> {};
23 
24 struct AdaptedIter : iterator_adaptor_base<AdaptedIter, WeirdIter> {};
25 
26 // Test that iterator_adaptor_base forwards typedefs, if value_type is
27 // unchanged.
28 static_assert(std::is_same<typename AdaptedIter::value_type, Shadow<0>>::value,
29               "");
30 static_assert(
31     std::is_same<typename AdaptedIter::difference_type, Shadow<1>>::value, "");
32 static_assert(std::is_same<typename AdaptedIter::pointer, Shadow<2>>::value,
33               "");
34 static_assert(std::is_same<typename AdaptedIter::reference, Shadow<3>>::value,
35               "");
36 
37 TEST(PointeeIteratorTest, Basic) {
38   int arr[4] = {1, 2, 3, 4};
39   SmallVector<int *, 4> V;
40   V.push_back(&arr[0]);
41   V.push_back(&arr[1]);
42   V.push_back(&arr[2]);
43   V.push_back(&arr[3]);
44 
45   typedef pointee_iterator<SmallVectorImpl<int *>::const_iterator>
46       test_iterator;
47 
48   test_iterator Begin, End;
49   Begin = V.begin();
50   End = test_iterator(V.end());
51 
52   test_iterator I = Begin;
53   for (int i = 0; i < 4; ++i) {
54     EXPECT_EQ(*V[i], *I);
55 
56     EXPECT_EQ(I, Begin + i);
57     EXPECT_EQ(I, std::next(Begin, i));
58     test_iterator J = Begin;
59     J += i;
60     EXPECT_EQ(I, J);
61     EXPECT_EQ(*V[i], Begin[i]);
62 
63     EXPECT_NE(I, End);
64     EXPECT_GT(End, I);
65     EXPECT_LT(I, End);
66     EXPECT_GE(I, Begin);
67     EXPECT_LE(Begin, I);
68 
69     EXPECT_EQ(i, I - Begin);
70     EXPECT_EQ(i, std::distance(Begin, I));
71     EXPECT_EQ(Begin, I - i);
72 
73     test_iterator K = I++;
74     EXPECT_EQ(K, std::prev(I));
75   }
76   EXPECT_EQ(End, I);
77 }
78 
79 TEST(PointeeIteratorTest, SmartPointer) {
80   SmallVector<std::unique_ptr<int>, 4> V;
81   V.push_back(make_unique<int>(1));
82   V.push_back(make_unique<int>(2));
83   V.push_back(make_unique<int>(3));
84   V.push_back(make_unique<int>(4));
85 
86   typedef pointee_iterator<
87       SmallVectorImpl<std::unique_ptr<int>>::const_iterator>
88       test_iterator;
89 
90   test_iterator Begin, End;
91   Begin = V.begin();
92   End = test_iterator(V.end());
93 
94   test_iterator I = Begin;
95   for (int i = 0; i < 4; ++i) {
96     EXPECT_EQ(*V[i], *I);
97 
98     EXPECT_EQ(I, Begin + i);
99     EXPECT_EQ(I, std::next(Begin, i));
100     test_iterator J = Begin;
101     J += i;
102     EXPECT_EQ(I, J);
103     EXPECT_EQ(*V[i], Begin[i]);
104 
105     EXPECT_NE(I, End);
106     EXPECT_GT(End, I);
107     EXPECT_LT(I, End);
108     EXPECT_GE(I, Begin);
109     EXPECT_LE(Begin, I);
110 
111     EXPECT_EQ(i, I - Begin);
112     EXPECT_EQ(i, std::distance(Begin, I));
113     EXPECT_EQ(Begin, I - i);
114 
115     test_iterator K = I++;
116     EXPECT_EQ(K, std::prev(I));
117   }
118   EXPECT_EQ(End, I);
119 }
120 
121 TEST(PointeeIteratorTest, Range) {
122   int A[] = {1, 2, 3, 4};
123   SmallVector<int *, 4> V{&A[0], &A[1], &A[2], &A[3]};
124 
125   int I = 0;
126   for (int II : make_pointee_range(V))
127     EXPECT_EQ(A[I++], II);
128 }
129 
130 TEST(FilterIteratorTest, Lambda) {
131   auto IsOdd = [](int N) { return N % 2 == 1; };
132   int A[] = {0, 1, 2, 3, 4, 5, 6};
133   auto Range = make_filter_range(A, IsOdd);
134   SmallVector<int, 3> Actual(Range.begin(), Range.end());
135   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
136 }
137 
138 TEST(FilterIteratorTest, CallableObject) {
139   int Counter = 0;
140   struct Callable {
141     int &Counter;
142 
143     Callable(int &Counter) : Counter(Counter) {}
144 
145     bool operator()(int N) {
146       Counter++;
147       return N % 2 == 1;
148     }
149   };
150   Callable IsOdd(Counter);
151   int A[] = {0, 1, 2, 3, 4, 5, 6};
152   auto Range = make_filter_range(A, IsOdd);
153   EXPECT_EQ(2, Counter);
154   SmallVector<int, 3> Actual(Range.begin(), Range.end());
155   EXPECT_GE(Counter, 7);
156   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
157 }
158 
159 TEST(FilterIteratorTest, FunctionPointer) {
160   bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; };
161   int A[] = {0, 1, 2, 3, 4, 5, 6};
162   auto Range = make_filter_range(A, IsOdd);
163   SmallVector<int, 3> Actual(Range.begin(), Range.end());
164   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
165 }
166 
167 TEST(FilterIteratorTest, Composition) {
168   auto IsOdd = [](int N) { return N % 2 == 1; };
169   std::unique_ptr<int> A[] = {make_unique<int>(0), make_unique<int>(1),
170                               make_unique<int>(2), make_unique<int>(3),
171                               make_unique<int>(4), make_unique<int>(5),
172                               make_unique<int>(6)};
173   using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>;
174   auto Range = make_filter_range(
175       make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))),
176       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, InputIterator) {
182   struct InputIterator
183       : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> {
184     using BaseT =
185         iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag>;
186 
187     InputIterator(int *It) : BaseT(It) {}
188   };
189 
190   auto IsOdd = [](int N) { return N % 2 == 1; };
191   int A[] = {0, 1, 2, 3, 4, 5, 6};
192   auto Range = make_filter_range(
193       make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))),
194       IsOdd);
195   SmallVector<int, 3> Actual(Range.begin(), Range.end());
196   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
197 }
198 
199 TEST(PointerIterator, Basic) {
200   int A[] = {1, 2, 3, 4};
201   pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A));
202   EXPECT_EQ(A, *Begin);
203   ++Begin;
204   EXPECT_EQ(A + 1, *Begin);
205   ++Begin;
206   EXPECT_EQ(A + 2, *Begin);
207   ++Begin;
208   EXPECT_EQ(A + 3, *Begin);
209   ++Begin;
210   EXPECT_EQ(Begin, End);
211 }
212 
213 TEST(PointerIterator, Const) {
214   int A[] = {1, 2, 3, 4};
215   const pointer_iterator<int *> Begin(std::begin(A));
216   EXPECT_EQ(A, *Begin);
217   EXPECT_EQ(A + 1, std::next(*Begin, 1));
218   EXPECT_EQ(A + 2, std::next(*Begin, 2));
219   EXPECT_EQ(A + 3, std::next(*Begin, 3));
220   EXPECT_EQ(A + 4, std::next(*Begin, 4));
221 }
222 
223 TEST(PointerIterator, Range) {
224   int A[] = {1, 2, 3, 4};
225   int I = 0;
226   for (int *P : make_pointer_range(A))
227     EXPECT_EQ(A + I++, P);
228 }
229 
230 TEST(ZipIteratorTest, Basic) {
231   using namespace std;
232   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
233   SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};
234   const char message[] = "yynyyy\0";
235 
236   for (auto tup : zip(pi, odd, message)) {
237     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
238     EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup));
239   }
240 
241   // note the rvalue
242   for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) {
243     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
244   }
245 }
246 
247 TEST(ZipIteratorTest, ZipFirstBasic) {
248   using namespace std;
249   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
250   unsigned iters = 0;
251 
252   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
253     EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01);
254     iters += 1;
255   }
256 
257   EXPECT_EQ(iters, 4u);
258 }
259 
260 TEST(ZipIteratorTest, Mutability) {
261   using namespace std;
262   const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9};
263   char message[] = "hello zip\0";
264 
265   for (auto tup : zip(pi, message, message)) {
266     EXPECT_EQ(get<1>(tup), get<2>(tup));
267     get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n';
268   }
269 
270   // note the rvalue
271   for (auto tup : zip(message, "yynyyyzip\0")) {
272     EXPECT_EQ(get<0>(tup), get<1>(tup));
273   }
274 }
275 
276 TEST(ZipIteratorTest, ZipFirstMutability) {
277   using namespace std;
278   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
279   unsigned iters = 0;
280 
281   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
282     get<1>(tup) = get<0>(tup);
283     iters += 1;
284   }
285 
286   EXPECT_EQ(iters, 4u);
287 
288   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
289     EXPECT_EQ(get<0>(tup), get<1>(tup));
290   }
291 }
292 
293 TEST(ZipIteratorTest, Filter) {
294   using namespace std;
295   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
296 
297   unsigned iters = 0;
298   // pi is length 6, but the zip RHS is length 7.
299   auto zipped = zip_first(pi, vector<bool>{1, 1, 0, 1, 1, 1, 0});
300   for (auto tup : make_filter_range(
301            zipped, [](decltype(zipped)::value_type t) { return get<1>(t); })) {
302     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
303     get<0>(tup) += 1;
304     iters += 1;
305   }
306 
307   // Should have skipped pi[2].
308   EXPECT_EQ(iters, 5u);
309 
310   // Ensure that in-place mutation works.
311   EXPECT_TRUE(all_of(pi, [](unsigned n) { return (n & 0x01) == 0; }));
312 }
313 
314 TEST(ZipIteratorTest, Reverse) {
315   using namespace std;
316   vector<unsigned> ascending{0, 1, 2, 3, 4, 5};
317 
318   auto zipped = zip_first(ascending, vector<bool>{0, 1, 0, 1, 0, 1});
319   unsigned last = 6;
320   for (auto tup : reverse(zipped)) {
321     // Check that this is in reverse.
322     EXPECT_LT(get<0>(tup), last);
323     last = get<0>(tup);
324     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
325   }
326 
327   auto odds = [](decltype(zipped)::value_type tup) { return get<1>(tup); };
328   last = 6;
329   for (auto tup : make_filter_range(reverse(zipped), odds)) {
330     EXPECT_LT(get<0>(tup), last);
331     last = get<0>(tup);
332     EXPECT_TRUE(get<0>(tup) & 0x01);
333     get<0>(tup) += 1;
334   }
335 
336   // Ensure that in-place mutation works.
337   EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; }));
338 }
339 
340 } // anonymous namespace
341