1 // Copyright (c) 2016 Google Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <memory>
16 #include <vector>
17
18 #include "gmock/gmock.h"
19
20 #include "source/opt/iterator.h"
21 #include "source/util/make_unique.h"
22
23 namespace spvtools {
24 namespace opt {
25 namespace {
26
27 using ::testing::ContainerEq;
28
TEST(Iterator,IncrementDeref)29 TEST(Iterator, IncrementDeref) {
30 const int count = 100;
31 std::vector<std::unique_ptr<int>> data;
32 for (int i = 0; i < count; ++i) {
33 data.emplace_back(new int(i));
34 }
35
36 UptrVectorIterator<int> it(&data, data.begin());
37 UptrVectorIterator<int> end(&data, data.end());
38
39 EXPECT_EQ(*data[0], *it);
40 for (int i = 1; i < count; ++i) {
41 EXPECT_NE(end, it);
42 EXPECT_EQ(*data[i], *(++it));
43 }
44 EXPECT_EQ(end, ++it);
45 }
46
TEST(Iterator,DecrementDeref)47 TEST(Iterator, DecrementDeref) {
48 const int count = 100;
49 std::vector<std::unique_ptr<int>> data;
50 for (int i = 0; i < count; ++i) {
51 data.emplace_back(new int(i));
52 }
53
54 UptrVectorIterator<int> begin(&data, data.begin());
55 UptrVectorIterator<int> it(&data, data.end());
56
57 for (int i = count - 1; i >= 0; --i) {
58 EXPECT_NE(begin, it);
59 EXPECT_EQ(*data[i], *(--it));
60 }
61 EXPECT_EQ(begin, it);
62 }
63
TEST(Iterator,PostIncrementDeref)64 TEST(Iterator, PostIncrementDeref) {
65 const int count = 100;
66 std::vector<std::unique_ptr<int>> data;
67 for (int i = 0; i < count; ++i) {
68 data.emplace_back(new int(i));
69 }
70
71 UptrVectorIterator<int> it(&data, data.begin());
72 UptrVectorIterator<int> end(&data, data.end());
73
74 for (int i = 0; i < count; ++i) {
75 EXPECT_NE(end, it);
76 EXPECT_EQ(*data[i], *(it++));
77 }
78 EXPECT_EQ(end, it);
79 }
80
TEST(Iterator,PostDecrementDeref)81 TEST(Iterator, PostDecrementDeref) {
82 const int count = 100;
83 std::vector<std::unique_ptr<int>> data;
84 for (int i = 0; i < count; ++i) {
85 data.emplace_back(new int(i));
86 }
87
88 UptrVectorIterator<int> begin(&data, data.begin());
89 UptrVectorIterator<int> end(&data, data.end());
90 UptrVectorIterator<int> it(&data, data.end());
91
92 EXPECT_EQ(end, it--);
93 for (int i = count - 1; i >= 1; --i) {
94 EXPECT_EQ(*data[i], *(it--));
95 }
96 // Decrementing .begin() is undefined behavior.
97 EXPECT_EQ(*data[0], *it);
98 }
99
TEST(Iterator,Access)100 TEST(Iterator, Access) {
101 const int count = 100;
102 std::vector<std::unique_ptr<int>> data;
103 for (int i = 0; i < count; ++i) {
104 data.emplace_back(new int(i));
105 }
106
107 UptrVectorIterator<int> it(&data, data.begin());
108
109 for (int i = 0; i < count; ++i) EXPECT_EQ(*data[i], it[i]);
110 }
111
TEST(Iterator,Comparison)112 TEST(Iterator, Comparison) {
113 const int count = 100;
114 std::vector<std::unique_ptr<int>> data;
115 for (int i = 0; i < count; ++i) {
116 data.emplace_back(new int(i));
117 }
118
119 UptrVectorIterator<int> it(&data, data.begin());
120 UptrVectorIterator<int> end(&data, data.end());
121
122 for (int i = 0; i < count; ++i, ++it) EXPECT_TRUE(it < end);
123 EXPECT_EQ(end, it);
124 }
125
TEST(Iterator,InsertBeginEnd)126 TEST(Iterator, InsertBeginEnd) {
127 const int count = 100;
128
129 std::vector<std::unique_ptr<int>> data;
130 std::vector<int> expected;
131 std::vector<int> actual;
132
133 for (int i = 0; i < count; ++i) {
134 data.emplace_back(new int(i));
135 expected.push_back(i);
136 }
137
138 // Insert at the beginning
139 expected.insert(expected.begin(), -100);
140 UptrVectorIterator<int> begin(&data, data.begin());
141 auto insert_point = begin.InsertBefore(MakeUnique<int>(-100));
142 for (int i = 0; i < count + 1; ++i) {
143 actual.push_back(*(insert_point++));
144 }
145 EXPECT_THAT(actual, ContainerEq(expected));
146
147 // Insert at the end
148 expected.push_back(-42);
149 expected.push_back(-36);
150 expected.push_back(-77);
151 UptrVectorIterator<int> end(&data, data.end());
152 end = end.InsertBefore(MakeUnique<int>(-77));
153 end = end.InsertBefore(MakeUnique<int>(-36));
154 end = end.InsertBefore(MakeUnique<int>(-42));
155
156 actual.clear();
157 begin = UptrVectorIterator<int>(&data, data.begin());
158 for (int i = 0; i < count + 4; ++i) {
159 actual.push_back(*(begin++));
160 }
161 EXPECT_THAT(actual, ContainerEq(expected));
162 }
163
TEST(Iterator,InsertMiddle)164 TEST(Iterator, InsertMiddle) {
165 const int count = 100;
166
167 std::vector<std::unique_ptr<int>> data;
168 std::vector<int> expected;
169 std::vector<int> actual;
170
171 for (int i = 0; i < count; ++i) {
172 data.emplace_back(new int(i));
173 expected.push_back(i);
174 }
175
176 const int insert_pos = 42;
177 expected.insert(expected.begin() + insert_pos, -100);
178 expected.insert(expected.begin() + insert_pos, -42);
179
180 UptrVectorIterator<int> it(&data, data.begin());
181 for (int i = 0; i < insert_pos; ++i) ++it;
182 it = it.InsertBefore(MakeUnique<int>(-100));
183 it = it.InsertBefore(MakeUnique<int>(-42));
184 auto begin = UptrVectorIterator<int>(&data, data.begin());
185 for (int i = 0; i < count + 2; ++i) {
186 actual.push_back(*(begin++));
187 }
188 EXPECT_THAT(actual, ContainerEq(expected));
189 }
190
TEST(IteratorRange,Interface)191 TEST(IteratorRange, Interface) {
192 const uint32_t count = 100;
193
194 std::vector<std::unique_ptr<uint32_t>> data;
195
196 for (uint32_t i = 0; i < count; ++i) {
197 data.emplace_back(new uint32_t(i));
198 }
199
200 auto b = UptrVectorIterator<uint32_t>(&data, data.begin());
201 auto e = UptrVectorIterator<uint32_t>(&data, data.end());
202 auto range = IteratorRange<decltype(b)>(b, e);
203
204 EXPECT_EQ(b, range.begin());
205 EXPECT_EQ(e, range.end());
206 EXPECT_FALSE(range.empty());
207 EXPECT_EQ(count, range.size());
208 EXPECT_EQ(0u, *range.begin());
209 EXPECT_EQ(99u, *(--range.end()));
210
211 // IteratorRange itself is immutable.
212 ++b, --e;
213 EXPECT_EQ(count, range.size());
214 ++range.begin(), --range.end();
215 EXPECT_EQ(count, range.size());
216 }
217
TEST(Iterator,FilterIterator)218 TEST(Iterator, FilterIterator) {
219 struct Placeholder {
220 int val;
221 };
222 std::vector<Placeholder> data = {{1}, {2}, {3}, {4}, {5},
223 {6}, {7}, {8}, {9}, {10}};
224
225 // Predicate to only consider odd values.
226 struct Predicate {
227 bool operator()(const Placeholder& data) { return data.val % 2; }
228 };
229 Predicate pred;
230
231 auto filter_range = MakeFilterIteratorRange(data.begin(), data.end(), pred);
232
233 EXPECT_EQ(filter_range.begin().Get(), data.begin());
234 EXPECT_EQ(filter_range.end(), filter_range.begin().GetEnd());
235
236 for (Placeholder& data : filter_range) {
237 EXPECT_EQ(data.val % 2, 1);
238 }
239
240 for (auto it = filter_range.begin(); it != filter_range.end(); it++) {
241 EXPECT_EQ(it->val % 2, 1);
242 EXPECT_EQ((*it).val % 2, 1);
243 }
244
245 for (auto it = filter_range.begin(); it != filter_range.end(); ++it) {
246 EXPECT_EQ(it->val % 2, 1);
247 EXPECT_EQ((*it).val % 2, 1);
248 }
249
250 EXPECT_EQ(MakeFilterIterator(data.begin(), data.end(), pred).Get(),
251 data.begin());
252 EXPECT_EQ(MakeFilterIterator(data.end(), data.end(), pred).Get(), data.end());
253 EXPECT_EQ(MakeFilterIterator(data.begin(), data.end(), pred).GetEnd(),
254 MakeFilterIterator(data.end(), data.end(), pred));
255 EXPECT_NE(MakeFilterIterator(data.begin(), data.end(), pred),
256 MakeFilterIterator(data.end(), data.end(), pred));
257
258 // Empty range: no values satisfies the predicate.
259 auto empty_range = MakeFilterIteratorRange(
260 data.begin(), data.end(),
261 [](const Placeholder& data) { return data.val > 10; });
262 EXPECT_EQ(empty_range.begin(), empty_range.end());
263 }
264
265 } // namespace
266 } // namespace opt
267 } // namespace spvtools
268