1 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
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/STLExtras.h"
11 #include "gtest/gtest.h"
12 
13 #include <list>
14 #include <vector>
15 
16 using namespace llvm;
17 
18 namespace {
19 
20 int f(rank<0>) { return 0; }
21 int f(rank<1>) { return 1; }
22 int f(rank<2>) { return 2; }
23 int f(rank<4>) { return 4; }
24 
25 TEST(STLExtrasTest, Rank) {
26   // We shouldn't get ambiguities and should select the overload of the same
27   // rank as the argument.
28   EXPECT_EQ(0, f(rank<0>()));
29   EXPECT_EQ(1, f(rank<1>()));
30   EXPECT_EQ(2, f(rank<2>()));
31 
32   // This overload is missing so we end up back at 2.
33   EXPECT_EQ(2, f(rank<3>()));
34 
35   // But going past 3 should work fine.
36   EXPECT_EQ(4, f(rank<4>()));
37 
38   // And we can even go higher and just fall back to the last overload.
39   EXPECT_EQ(4, f(rank<5>()));
40   EXPECT_EQ(4, f(rank<6>()));
41 }
42 
43 TEST(STLExtrasTest, EnumerateLValue) {
44   // Test that a simple LValue can be enumerated and gives correct results with
45   // multiple types, including the empty container.
46   std::vector<char> foo = {'a', 'b', 'c'};
47   typedef std::pair<std::size_t, char> CharPairType;
48   std::vector<CharPairType> CharResults;
49 
50   for (auto X : llvm::enumerate(foo)) {
51     CharResults.emplace_back(X.Index, X.Value);
52   }
53   ASSERT_EQ(3u, CharResults.size());
54   EXPECT_EQ(CharPairType(0u, 'a'), CharResults[0]);
55   EXPECT_EQ(CharPairType(1u, 'b'), CharResults[1]);
56   EXPECT_EQ(CharPairType(2u, 'c'), CharResults[2]);
57 
58   // Test a const range of a different type.
59   typedef std::pair<std::size_t, int> IntPairType;
60   std::vector<IntPairType> IntResults;
61   const std::vector<int> bar = {1, 2, 3};
62   for (auto X : llvm::enumerate(bar)) {
63     IntResults.emplace_back(X.Index, X.Value);
64   }
65   ASSERT_EQ(3u, IntResults.size());
66   EXPECT_EQ(IntPairType(0u, 1), IntResults[0]);
67   EXPECT_EQ(IntPairType(1u, 2), IntResults[1]);
68   EXPECT_EQ(IntPairType(2u, 3), IntResults[2]);
69 
70   // Test an empty range.
71   IntResults.clear();
72   const std::vector<int> baz;
73   for (auto X : llvm::enumerate(baz)) {
74     IntResults.emplace_back(X.Index, X.Value);
75   }
76   EXPECT_TRUE(IntResults.empty());
77 }
78 
79 TEST(STLExtrasTest, EnumerateModifyLValue) {
80   // Test that you can modify the underlying entries of an lvalue range through
81   // the enumeration iterator.
82   std::vector<char> foo = {'a', 'b', 'c'};
83 
84   for (auto X : llvm::enumerate(foo)) {
85     ++X.Value;
86   }
87   EXPECT_EQ('b', foo[0]);
88   EXPECT_EQ('c', foo[1]);
89   EXPECT_EQ('d', foo[2]);
90 }
91 
92 TEST(STLExtrasTest, EnumerateRValueRef) {
93   // Test that an rvalue can be enumerated.
94   typedef std::pair<std::size_t, int> PairType;
95   std::vector<PairType> Results;
96 
97   auto Enumerator = llvm::enumerate(std::vector<int>{1, 2, 3});
98 
99   for (auto X : llvm::enumerate(std::vector<int>{1, 2, 3})) {
100     Results.emplace_back(X.Index, X.Value);
101   }
102 
103   ASSERT_EQ(3u, Results.size());
104   EXPECT_EQ(PairType(0u, 1), Results[0]);
105   EXPECT_EQ(PairType(1u, 2), Results[1]);
106   EXPECT_EQ(PairType(2u, 3), Results[2]);
107 }
108 
109 TEST(STLExtrasTest, EnumerateModifyRValue) {
110   // Test that when enumerating an rvalue, modification still works (even if
111   // this isn't terribly useful, it at least shows that we haven't snuck an
112   // extra const in there somewhere.
113   typedef std::pair<std::size_t, char> PairType;
114   std::vector<PairType> Results;
115 
116   for (auto X : llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
117     ++X.Value;
118     Results.emplace_back(X.Index, X.Value);
119   }
120 
121   ASSERT_EQ(3u, Results.size());
122   EXPECT_EQ(PairType(0u, '2'), Results[0]);
123   EXPECT_EQ(PairType(1u, '3'), Results[1]);
124   EXPECT_EQ(PairType(2u, '4'), Results[2]);
125 }
126 
127 template <bool B> struct CanMove {};
128 template <> struct CanMove<false> {
129   CanMove(CanMove &&) = delete;
130 
131   CanMove() = default;
132   CanMove(const CanMove &) = default;
133 };
134 
135 template <bool B> struct CanCopy {};
136 template <> struct CanCopy<false> {
137   CanCopy(const CanCopy &) = delete;
138 
139   CanCopy() = default;
140   CanCopy(CanCopy &&) = default;
141 };
142 
143 template <bool Moveable, bool Copyable>
144 struct Range : CanMove<Moveable>, CanCopy<Copyable> {
145   explicit Range(int &C, int &M, int &D) : C(C), M(M), D(D) {}
146   Range(const Range &R) : CanCopy<Copyable>(R), C(R.C), M(R.M), D(R.D) { ++C; }
147   Range(Range &&R) : CanMove<Moveable>(std::move(R)), C(R.C), M(R.M), D(R.D) {
148     ++M;
149   }
150   ~Range() { ++D; }
151 
152   int &C;
153   int &M;
154   int &D;
155 
156   int *begin() { return nullptr; }
157   int *end() { return nullptr; }
158 };
159 
160 TEST(STLExtrasTest, EnumerateLifetimeSemantics) {
161   // Test that when enumerating lvalues and rvalues, there are no surprise
162   // copies or moves.
163 
164   // With an rvalue, it should not be destroyed until the end of the scope.
165   int Copies = 0;
166   int Moves = 0;
167   int Destructors = 0;
168   {
169     auto E1 = enumerate(Range<true, false>(Copies, Moves, Destructors));
170     // Doesn't compile.  rvalue ranges must be moveable.
171     // auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));
172     EXPECT_EQ(0, Copies);
173     EXPECT_EQ(1, Moves);
174     EXPECT_EQ(1, Destructors);
175   }
176   EXPECT_EQ(0, Copies);
177   EXPECT_EQ(1, Moves);
178   EXPECT_EQ(2, Destructors);
179 
180   Copies = Moves = Destructors = 0;
181   // With an lvalue, it should not be destroyed even after the end of the scope.
182   // lvalue ranges need be neither copyable nor moveable.
183   Range<false, false> R(Copies, Moves, Destructors);
184   {
185     auto Enumerator = enumerate(R);
186     (void)Enumerator;
187     EXPECT_EQ(0, Copies);
188     EXPECT_EQ(0, Moves);
189     EXPECT_EQ(0, Destructors);
190   }
191   EXPECT_EQ(0, Copies);
192   EXPECT_EQ(0, Moves);
193   EXPECT_EQ(0, Destructors);
194 }
195 
196 TEST(STLExtrasTest, ApplyTuple) {
197   auto T = std::make_tuple(1, 3, 7);
198   auto U = llvm::apply_tuple(
199       [](int A, int B, int C) { return std::make_tuple(A - B, B - C, C - A); },
200       T);
201 
202   EXPECT_EQ(-2, std::get<0>(U));
203   EXPECT_EQ(-4, std::get<1>(U));
204   EXPECT_EQ(6, std::get<2>(U));
205 
206   auto V = llvm::apply_tuple(
207       [](int A, int B, int C) {
208         return std::make_tuple(std::make_pair(A, char('A' + A)),
209                                std::make_pair(B, char('A' + B)),
210                                std::make_pair(C, char('A' + C)));
211       },
212       T);
213 
214   EXPECT_EQ(std::make_pair(1, 'B'), std::get<0>(V));
215   EXPECT_EQ(std::make_pair(3, 'D'), std::get<1>(V));
216   EXPECT_EQ(std::make_pair(7, 'H'), std::get<2>(V));
217 }
218 
219 class apply_variadic {
220   static int apply_one(int X) { return X + 1; }
221   static char apply_one(char C) { return C + 1; }
222   static StringRef apply_one(StringRef S) { return S.drop_back(); }
223 
224 public:
225   template <typename... Ts>
226   auto operator()(Ts &&... Items)
227       -> decltype(std::make_tuple(apply_one(Items)...)) {
228     return std::make_tuple(apply_one(Items)...);
229   }
230 };
231 
232 TEST(STLExtrasTest, ApplyTupleVariadic) {
233   auto Items = std::make_tuple(1, llvm::StringRef("Test"), 'X');
234   auto Values = apply_tuple(apply_variadic(), Items);
235 
236   EXPECT_EQ(2, std::get<0>(Values));
237   EXPECT_EQ("Tes", std::get<1>(Values));
238   EXPECT_EQ('Y', std::get<2>(Values));
239 }
240 
241 TEST(STLExtrasTest, CountAdaptor) {
242   std::vector<int> v;
243 
244   v.push_back(1);
245   v.push_back(2);
246   v.push_back(1);
247   v.push_back(4);
248   v.push_back(3);
249   v.push_back(2);
250   v.push_back(1);
251 
252   EXPECT_EQ(3, count(v, 1));
253   EXPECT_EQ(2, count(v, 2));
254   EXPECT_EQ(1, count(v, 3));
255   EXPECT_EQ(1, count(v, 4));
256 }
257 
258 TEST(STLExtrasTest, ConcatRange) {
259   std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};
260   std::vector<int> Test;
261 
262   std::vector<int> V1234 = {1, 2, 3, 4};
263   std::list<int> L56 = {5, 6};
264   SmallVector<int, 2> SV78 = {7, 8};
265 
266   // Use concat across different sized ranges of different types with different
267   // iterators.
268   for (int &i : concat<int>(V1234, L56, SV78))
269     Test.push_back(i);
270   EXPECT_EQ(Expected, Test);
271 
272   // Use concat between a temporary, an L-value, and an R-value to make sure
273   // complex lifetimes work well.
274   Test.clear();
275   for (int &i : concat<int>(std::vector<int>(V1234), L56, std::move(SV78)))
276     Test.push_back(i);
277   EXPECT_EQ(Expected, Test);
278 }
279 
280 TEST(STLExtrasTest, PartitionAdaptor) {
281   std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
282 
283   auto I = partition(V, [](int i) { return i % 2 == 0; });
284   ASSERT_EQ(V.begin() + 4, I);
285 
286   // Sort the two halves as partition may have messed with the order.
287   std::sort(V.begin(), I);
288   std::sort(I, V.end());
289 
290   EXPECT_EQ(2, V[0]);
291   EXPECT_EQ(4, V[1]);
292   EXPECT_EQ(6, V[2]);
293   EXPECT_EQ(8, V[3]);
294   EXPECT_EQ(1, V[4]);
295   EXPECT_EQ(3, V[5]);
296   EXPECT_EQ(5, V[6]);
297   EXPECT_EQ(7, V[7]);
298 }
299 
300 TEST(STLExtrasTest, EraseIf) {
301   std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
302 
303   erase_if(V, [](int i) { return i % 2 == 0; });
304   EXPECT_EQ(4u, V.size());
305   EXPECT_EQ(1, V[0]);
306   EXPECT_EQ(3, V[1]);
307   EXPECT_EQ(5, V[2]);
308   EXPECT_EQ(7, V[3]);
309 }
310 
311 }
312