1 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/STLExtras.h"
11 #include "gtest/gtest.h"
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; }
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>()));
32 // This overload is missing so we end up back at 2.
33 EXPECT_EQ(2, f(rank<3>()));
35 // But going past 3 should work fine.
36 EXPECT_EQ(4, f(rank<4>()));
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>()));
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;
50 for (auto X : llvm::enumerate(foo)) {
51 CharResults.emplace_back(X.index(), X.value());
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]);
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());
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]);
70 // Test an empty range.
72 const std::vector<int> baz{};
73 for (auto X : llvm::enumerate(baz)) {
74 IntResults.emplace_back(X.index(), X.value());
76 EXPECT_TRUE(IntResults.empty());
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'};
84 for (auto X : llvm::enumerate(foo)) {
87 EXPECT_EQ('b', foo[0]);
88 EXPECT_EQ('c', foo[1]);
89 EXPECT_EQ('d', foo[2]);
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;
97 auto Enumerator = llvm::enumerate(std::vector<int>{1, 2, 3});
99 for (auto X : llvm::enumerate(std::vector<int>{1, 2, 3})) {
100 Results.emplace_back(X.index(), X.value());
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]);
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;
116 for (auto X : llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
118 Results.emplace_back(X.index(), X.value());
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]);
127 template <bool B> struct CanMove {};
128 template <> struct CanMove<false> {
129 CanMove(CanMove &&) = delete;
132 CanMove(const CanMove &) = default;
135 template <bool B> struct CanCopy {};
136 template <> struct CanCopy<false> {
137 CanCopy(const CanCopy &) = delete;
140 CanCopy(CanCopy &&) = default;
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) {
156 int *begin() { return nullptr; }
157 int *end() { return nullptr; }
160 TEST(STLExtrasTest, EnumerateLifetimeSemantics) {
161 // Test that when enumerating lvalues and rvalues, there are no surprise
164 // With an rvalue, it should not be destroyed until the end of the scope.
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);
174 EXPECT_EQ(1, Destructors);
176 EXPECT_EQ(0, Copies);
178 EXPECT_EQ(2, Destructors);
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);
185 auto Enumerator = enumerate(R);
187 EXPECT_EQ(0, Copies);
189 EXPECT_EQ(0, Destructors);
191 EXPECT_EQ(0, Copies);
193 EXPECT_EQ(0, Destructors);
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); },
202 EXPECT_EQ(-2, std::get<0>(U));
203 EXPECT_EQ(-4, std::get<1>(U));
204 EXPECT_EQ(6, std::get<2>(U));
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)));
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));
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(); }
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)...);
232 TEST(STLExtrasTest, ApplyTupleVariadic) {
233 auto Items = std::make_tuple(1, llvm::StringRef("Test"), 'X');
234 auto Values = apply_tuple(apply_variadic(), Items);
236 EXPECT_EQ(2, std::get<0>(Values));
237 EXPECT_EQ("Tes", std::get<1>(Values));
238 EXPECT_EQ('Y', std::get<2>(Values));
241 TEST(STLExtrasTest, CountAdaptor) {
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));
258 TEST(STLExtrasTest, for_each) {
259 std::vector<int> v{0, 1, 2, 3, 4};
262 llvm::for_each(v, [&count](int) { ++count; });
266 TEST(STLExtrasTest, ToVector) {
267 std::vector<char> v = {'a', 'b', 'c'};
268 auto Enumerated = to_vector<4>(enumerate(v));
269 ASSERT_EQ(3u, Enumerated.size());
270 for (size_t I = 0; I < v.size(); ++I) {
271 EXPECT_EQ(I, Enumerated[I].index());
272 EXPECT_EQ(v[I], Enumerated[I].value());
276 TEST(STLExtrasTest, ConcatRange) {
277 std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};
278 std::vector<int> Test;
280 std::vector<int> V1234 = {1, 2, 3, 4};
281 std::list<int> L56 = {5, 6};
282 SmallVector<int, 2> SV78 = {7, 8};
284 // Use concat across different sized ranges of different types with different
286 for (int &i : concat<int>(V1234, L56, SV78))
288 EXPECT_EQ(Expected, Test);
290 // Use concat between a temporary, an L-value, and an R-value to make sure
291 // complex lifetimes work well.
293 for (int &i : concat<int>(std::vector<int>(V1234), L56, std::move(SV78)))
295 EXPECT_EQ(Expected, Test);
298 TEST(STLExtrasTest, PartitionAdaptor) {
299 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
301 auto I = partition(V, [](int i) { return i % 2 == 0; });
302 ASSERT_EQ(V.begin() + 4, I);
304 // Sort the two halves as partition may have messed with the order.
305 std::sort(V.begin(), I);
306 std::sort(I, V.end());
318 TEST(STLExtrasTest, EraseIf) {
319 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
321 erase_if(V, [](int i) { return i % 2 == 0; });
322 EXPECT_EQ(4u, V.size());
329 namespace some_namespace {
331 std::vector<int> data;
332 std::string swap_val;
335 std::vector<int>::const_iterator begin(const some_struct &s) {
336 return s.data.begin();
339 std::vector<int>::const_iterator end(const some_struct &s) {
343 void swap(some_struct &lhs, some_struct &rhs) {
344 // make swap visible as non-adl swap would even seem to
345 // work with std::swap which defaults to moving
346 lhs.swap_val = "lhs";
347 rhs.swap_val = "rhs";
349 } // namespace some_namespace
351 TEST(STLExtrasTest, ADLTest) {
352 some_namespace::some_struct s{{1, 2, 3, 4, 5}, ""};
353 some_namespace::some_struct s2{{2, 4, 6, 8, 10}, ""};
355 EXPECT_EQ(*adl_begin(s), 1);
356 EXPECT_EQ(*(adl_end(s) - 1), 5);
359 EXPECT_EQ(s.swap_val, "lhs");
360 EXPECT_EQ(s2.swap_val, "rhs");
363 llvm::for_each(s, [&count](int) { ++count; });