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> test_iterator;
46 
47   test_iterator Begin, End;
48   Begin = V.begin();
49   End = test_iterator(V.end());
50 
51   test_iterator I = Begin;
52   for (int i = 0; i < 4; ++i) {
53     EXPECT_EQ(*V[i], *I);
54 
55     EXPECT_EQ(I, Begin + i);
56     EXPECT_EQ(I, std::next(Begin, i));
57     test_iterator J = Begin;
58     J += i;
59     EXPECT_EQ(I, J);
60     EXPECT_EQ(*V[i], Begin[i]);
61 
62     EXPECT_NE(I, End);
63     EXPECT_GT(End, I);
64     EXPECT_LT(I, End);
65     EXPECT_GE(I, Begin);
66     EXPECT_LE(Begin, I);
67 
68     EXPECT_EQ(i, I - Begin);
69     EXPECT_EQ(i, std::distance(Begin, I));
70     EXPECT_EQ(Begin, I - i);
71 
72     test_iterator K = I++;
73     EXPECT_EQ(K, std::prev(I));
74   }
75   EXPECT_EQ(End, I);
76 }
77 
78 TEST(PointeeIteratorTest, SmartPointer) {
79   SmallVector<std::unique_ptr<int>, 4> V;
80   V.push_back(make_unique<int>(1));
81   V.push_back(make_unique<int>(2));
82   V.push_back(make_unique<int>(3));
83   V.push_back(make_unique<int>(4));
84 
85   typedef pointee_iterator<
86       SmallVectorImpl<std::unique_ptr<int>>::const_iterator> test_iterator;
87 
88   test_iterator Begin, End;
89   Begin = V.begin();
90   End = test_iterator(V.end());
91 
92   test_iterator I = Begin;
93   for (int i = 0; i < 4; ++i) {
94     EXPECT_EQ(*V[i], *I);
95 
96     EXPECT_EQ(I, Begin + i);
97     EXPECT_EQ(I, std::next(Begin, i));
98     test_iterator J = Begin;
99     J += i;
100     EXPECT_EQ(I, J);
101     EXPECT_EQ(*V[i], Begin[i]);
102 
103     EXPECT_NE(I, End);
104     EXPECT_GT(End, I);
105     EXPECT_LT(I, End);
106     EXPECT_GE(I, Begin);
107     EXPECT_LE(Begin, I);
108 
109     EXPECT_EQ(i, I - Begin);
110     EXPECT_EQ(i, std::distance(Begin, I));
111     EXPECT_EQ(Begin, I - i);
112 
113     test_iterator K = I++;
114     EXPECT_EQ(K, std::prev(I));
115   }
116   EXPECT_EQ(End, I);
117 }
118 
119 TEST(FilterIteratorTest, Lambda) {
120   auto IsOdd = [](int N) { return N % 2 == 1; };
121   int A[] = {0, 1, 2, 3, 4, 5, 6};
122   auto Range = make_filter_range(A, IsOdd);
123   SmallVector<int, 3> Actual(Range.begin(), Range.end());
124   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
125 }
126 
127 TEST(FilterIteratorTest, CallableObject) {
128   int Counter = 0;
129   struct Callable {
130     int &Counter;
131 
132     Callable(int &Counter) : Counter(Counter) {}
133 
134     bool operator()(int N) {
135       Counter++;
136       return N % 2 == 1;
137     }
138   };
139   Callable IsOdd(Counter);
140   int A[] = {0, 1, 2, 3, 4, 5, 6};
141   auto Range = make_filter_range(A, IsOdd);
142   EXPECT_EQ(2, Counter);
143   SmallVector<int, 3> Actual(Range.begin(), Range.end());
144   EXPECT_GE(Counter, 7);
145   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
146 }
147 
148 TEST(FilterIteratorTest, FunctionPointer) {
149   bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; };
150   int A[] = {0, 1, 2, 3, 4, 5, 6};
151   auto Range = make_filter_range(A, IsOdd);
152   SmallVector<int, 3> Actual(Range.begin(), Range.end());
153   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
154 }
155 
156 TEST(FilterIteratorTest, Composition) {
157   auto IsOdd = [](int N) { return N % 2 == 1; };
158   std::unique_ptr<int> A[] = {make_unique<int>(0), make_unique<int>(1),
159                               make_unique<int>(2), make_unique<int>(3),
160                               make_unique<int>(4), make_unique<int>(5),
161                               make_unique<int>(6)};
162   using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>;
163   auto Range = make_filter_range(
164       make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))),
165       IsOdd);
166   SmallVector<int, 3> Actual(Range.begin(), Range.end());
167   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
168 }
169 
170 TEST(FilterIteratorTest, InputIterator) {
171   struct InputIterator
172       : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> {
173     using BaseT =
174         iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag>;
175 
176     InputIterator(int *It) : BaseT(It) {}
177   };
178 
179   auto IsOdd = [](int N) { return N % 2 == 1; };
180   int A[] = {0, 1, 2, 3, 4, 5, 6};
181   auto Range = make_filter_range(
182       make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))),
183       IsOdd);
184   SmallVector<int, 3> Actual(Range.begin(), Range.end());
185   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
186 }
187 
188 TEST(PointerIterator, Basic) {
189   int A[] = {1, 2, 3, 4};
190   pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A));
191   EXPECT_EQ(A, *Begin);
192   ++Begin;
193   EXPECT_EQ(A + 1, *Begin);
194   ++Begin;
195   EXPECT_EQ(A + 2, *Begin);
196   ++Begin;
197   EXPECT_EQ(A + 3, *Begin);
198   ++Begin;
199   EXPECT_EQ(Begin, End);
200 }
201 
202 TEST(PointerIterator, Const) {
203   int A[] = {1, 2, 3, 4};
204   const pointer_iterator<int *> Begin(std::begin(A));
205   EXPECT_EQ(A, *Begin);
206   EXPECT_EQ(A + 1, std::next(*Begin, 1));
207   EXPECT_EQ(A + 2, std::next(*Begin, 2));
208   EXPECT_EQ(A + 3, std::next(*Begin, 3));
209   EXPECT_EQ(A + 4, std::next(*Begin, 4));
210 }
211 
212 TEST(ZipIteratorTest, Basic) {
213   using namespace std;
214   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
215   SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};
216   const char message[] = "yynyyy\0";
217 
218   for (auto tup : zip(pi, odd, message)) {
219     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
220     EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup));
221   }
222 
223   // note the rvalue
224   for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) {
225     EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
226   }
227 }
228 
229 TEST(ZipIteratorTest, ZipFirstBasic) {
230   using namespace std;
231   const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
232   unsigned iters = 0;
233 
234   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
235     EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01);
236     iters += 1;
237   }
238 
239   EXPECT_EQ(iters, 4u);
240 }
241 
242 TEST(ZipIteratorTest, Mutability) {
243   using namespace std;
244   const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9};
245   char message[] = "hello zip\0";
246 
247   for (auto tup : zip(pi, message, message)) {
248     EXPECT_EQ(get<1>(tup), get<2>(tup));
249     get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n';
250   }
251 
252   // note the rvalue
253   for (auto tup : zip(message, "yynyyyzip\0")) {
254     EXPECT_EQ(get<0>(tup), get<1>(tup));
255   }
256 }
257 
258 TEST(ZipIteratorTest, ZipFirstMutability) {
259   using namespace std;
260   vector<unsigned> pi{3, 1, 4, 1, 5, 9};
261   unsigned iters = 0;
262 
263   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
264     get<1>(tup) = get<0>(tup);
265     iters += 1;
266   }
267 
268   EXPECT_EQ(iters, 4u);
269 
270   for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
271     EXPECT_EQ(get<0>(tup), get<1>(tup));
272   }
273 }
274 
275 } // anonymous namespace
276