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, for_each) { 259 std::vector<int> v{0, 1, 2, 3, 4}; 260 int count = 0; 261 262 llvm::for_each(v, [&count](int) { ++count; }); 263 EXPECT_EQ(5, count); 264 } 265 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()); 273 } 274 } 275 276 TEST(STLExtrasTest, ConcatRange) { 277 std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8}; 278 std::vector<int> Test; 279 280 std::vector<int> V1234 = {1, 2, 3, 4}; 281 std::list<int> L56 = {5, 6}; 282 SmallVector<int, 2> SV78 = {7, 8}; 283 284 // Use concat across different sized ranges of different types with different 285 // iterators. 286 for (int &i : concat<int>(V1234, L56, SV78)) 287 Test.push_back(i); 288 EXPECT_EQ(Expected, Test); 289 290 // Use concat between a temporary, an L-value, and an R-value to make sure 291 // complex lifetimes work well. 292 Test.clear(); 293 for (int &i : concat<int>(std::vector<int>(V1234), L56, std::move(SV78))) 294 Test.push_back(i); 295 EXPECT_EQ(Expected, Test); 296 } 297 298 TEST(STLExtrasTest, PartitionAdaptor) { 299 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8}; 300 301 auto I = partition(V, [](int i) { return i % 2 == 0; }); 302 ASSERT_EQ(V.begin() + 4, I); 303 304 // Sort the two halves as partition may have messed with the order. 305 llvm::sort(V.begin(), I); 306 llvm::sort(I, V.end()); 307 308 EXPECT_EQ(2, V[0]); 309 EXPECT_EQ(4, V[1]); 310 EXPECT_EQ(6, V[2]); 311 EXPECT_EQ(8, V[3]); 312 EXPECT_EQ(1, V[4]); 313 EXPECT_EQ(3, V[5]); 314 EXPECT_EQ(5, V[6]); 315 EXPECT_EQ(7, V[7]); 316 } 317 318 TEST(STLExtrasTest, EraseIf) { 319 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8}; 320 321 erase_if(V, [](int i) { return i % 2 == 0; }); 322 EXPECT_EQ(4u, V.size()); 323 EXPECT_EQ(1, V[0]); 324 EXPECT_EQ(3, V[1]); 325 EXPECT_EQ(5, V[2]); 326 EXPECT_EQ(7, V[3]); 327 } 328 329 namespace some_namespace { 330 struct some_struct { 331 std::vector<int> data; 332 std::string swap_val; 333 }; 334 335 std::vector<int>::const_iterator begin(const some_struct &s) { 336 return s.data.begin(); 337 } 338 339 std::vector<int>::const_iterator end(const some_struct &s) { 340 return s.data.end(); 341 } 342 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"; 348 } 349 } // namespace some_namespace 350 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}, ""}; 354 355 EXPECT_EQ(*adl_begin(s), 1); 356 EXPECT_EQ(*(adl_end(s) - 1), 5); 357 358 adl_swap(s, s2); 359 EXPECT_EQ(s.swap_val, "lhs"); 360 EXPECT_EQ(s2.swap_val, "rhs"); 361 362 int count = 0; 363 llvm::for_each(s, [&count](int) { ++count; }); 364 EXPECT_EQ(5, count); 365 } 366 367 } // namespace 368