unittests/ADT/STLExtrasTest.cpp

   1 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/STLExtras.h"
  10 #include "gtest/gtest.h"
  11
  12 #include <list>
  13 #include <vector>
  14
  15 using namespace llvm;
  16
  17 namespace {
  18
  19 int f(rank<0>) { return 0; }
  20 int f(rank<1>) { return 1; }
  21 int f(rank<2>) { return 2; }
  22 int f(rank<4>) { return 4; }
  23
  24 TEST(STLExtrasTest, Rank) {
  25   // We shouldn't get ambiguities and should select the overload of the same
  26   // rank as the argument.
  27   EXPECT_EQ(0, f(rank<0>()));
  28   EXPECT_EQ(1, f(rank<1>()));
  29   EXPECT_EQ(2, f(rank<2>()));
  30
  31   // This overload is missing so we end up back at 2.
  32   EXPECT_EQ(2, f(rank<3>()));
  33
  34   // But going past 3 should work fine.
  35   EXPECT_EQ(4, f(rank<4>()));
  36
  37   // And we can even go higher and just fall back to the last overload.
  38   EXPECT_EQ(4, f(rank<5>()));
  39   EXPECT_EQ(4, f(rank<6>()));
  40 }
  41
  42 TEST(STLExtrasTest, EnumerateLValue) {
  43   // Test that a simple LValue can be enumerated and gives correct results with
  44   // multiple types, including the empty container.
  45   std::vector<char> foo = {'a', 'b', 'c'};
  46   typedef std::pair<std::size_t, char> CharPairType;
  47   std::vector<CharPairType> CharResults;
  48
  49   for (auto X : llvm::enumerate(foo)) {
  50     CharResults.emplace_back(X.index(), X.value());
  51   }
  52   ASSERT_EQ(3u, CharResults.size());
  53   EXPECT_EQ(CharPairType(0u, 'a'), CharResults[0]);
  54   EXPECT_EQ(CharPairType(1u, 'b'), CharResults[1]);
  55   EXPECT_EQ(CharPairType(2u, 'c'), CharResults[2]);
  56
  57   // Test a const range of a different type.
  58   typedef std::pair<std::size_t, int> IntPairType;
  59   std::vector<IntPairType> IntResults;
  60   const std::vector<int> bar = {1, 2, 3};
  61   for (auto X : llvm::enumerate(bar)) {
  62     IntResults.emplace_back(X.index(), X.value());
  63   }
  64   ASSERT_EQ(3u, IntResults.size());
  65   EXPECT_EQ(IntPairType(0u, 1), IntResults[0]);
  66   EXPECT_EQ(IntPairType(1u, 2), IntResults[1]);
  67   EXPECT_EQ(IntPairType(2u, 3), IntResults[2]);
  68
  69   // Test an empty range.
  70   IntResults.clear();
  71   const std::vector<int> baz{};
  72   for (auto X : llvm::enumerate(baz)) {
  73     IntResults.emplace_back(X.index(), X.value());
  74   }
  75   EXPECT_TRUE(IntResults.empty());
  76 }
  77
  78 TEST(STLExtrasTest, EnumerateModifyLValue) {
  79   // Test that you can modify the underlying entries of an lvalue range through
  80   // the enumeration iterator.
  81   std::vector<char> foo = {'a', 'b', 'c'};
  82
  83   for (auto X : llvm::enumerate(foo)) {
  84     ++X.value();
  85   }
  86   EXPECT_EQ('b', foo[0]);
  87   EXPECT_EQ('c', foo[1]);
  88   EXPECT_EQ('d', foo[2]);
  89 }
  90
  91 TEST(STLExtrasTest, EnumerateRValueRef) {
  92   // Test that an rvalue can be enumerated.
  93   typedef std::pair<std::size_t, int> PairType;
  94   std::vector<PairType> Results;
  95
  96   auto Enumerator = llvm::enumerate(std::vector<int>{1, 2, 3});
  97
  98   for (auto X : llvm::enumerate(std::vector<int>{1, 2, 3})) {
  99     Results.emplace_back(X.index(), X.value());
 100   }
 101
 102   ASSERT_EQ(3u, Results.size());
 103   EXPECT_EQ(PairType(0u, 1), Results[0]);
 104   EXPECT_EQ(PairType(1u, 2), Results[1]);
 105   EXPECT_EQ(PairType(2u, 3), Results[2]);
 106 }
 107
 108 TEST(STLExtrasTest, EnumerateModifyRValue) {
 109   // Test that when enumerating an rvalue, modification still works (even if
 110   // this isn't terribly useful, it at least shows that we haven't snuck an
 111   // extra const in there somewhere.
 112   typedef std::pair<std::size_t, char> PairType;
 113   std::vector<PairType> Results;
 114
 115   for (auto X : llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
 116     ++X.value();
 117     Results.emplace_back(X.index(), X.value());
 118   }
 119
 120   ASSERT_EQ(3u, Results.size());
 121   EXPECT_EQ(PairType(0u, '2'), Results[0]);
 122   EXPECT_EQ(PairType(1u, '3'), Results[1]);
 123   EXPECT_EQ(PairType(2u, '4'), Results[2]);
 124 }
 125
 126 template <bool B> struct CanMove {};
 127 template <> struct CanMove<false> {
 128   CanMove(CanMove &&) = delete;
 129
 130   CanMove() = default;
 131   CanMove(const CanMove &) = default;
 132 };
 133
 134 template <bool B> struct CanCopy {};
 135 template <> struct CanCopy<false> {
 136   CanCopy(const CanCopy &) = delete;
 137
 138   CanCopy() = default;
 139   CanCopy(CanCopy &&) = default;
 140 };
 141
 142 template <bool Moveable, bool Copyable>
 143 struct Range : CanMove<Moveable>, CanCopy<Copyable> {
 144   explicit Range(int &C, int &M, int &D) : C(C), M(M), D(D) {}
 145   Range(const Range &R) : CanCopy<Copyable>(R), C(R.C), M(R.M), D(R.D) { ++C; }
 146   Range(Range &&R) : CanMove<Moveable>(std::move(R)), C(R.C), M(R.M), D(R.D) {
 147     ++M;
 148   }
 149   ~Range() { ++D; }
 150
 151   int &C;
 152   int &M;
 153   int &D;
 154
 155   int *begin() { return nullptr; }
 156   int *end() { return nullptr; }
 157 };
 158
 159 TEST(STLExtrasTest, EnumerateLifetimeSemantics) {
 160   // Test that when enumerating lvalues and rvalues, there are no surprise
 161   // copies or moves.
 162
 163   // With an rvalue, it should not be destroyed until the end of the scope.
 164   int Copies = 0;
 165   int Moves = 0;
 166   int Destructors = 0;
 167   {
 168     auto E1 = enumerate(Range<true, false>(Copies, Moves, Destructors));
 169     // Doesn't compile.  rvalue ranges must be moveable.
 170     // auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));
 171     EXPECT_EQ(0, Copies);
 172     EXPECT_EQ(1, Moves);
 173     EXPECT_EQ(1, Destructors);
 174   }
 175   EXPECT_EQ(0, Copies);
 176   EXPECT_EQ(1, Moves);
 177   EXPECT_EQ(2, Destructors);
 178
 179   Copies = Moves = Destructors = 0;
 180   // With an lvalue, it should not be destroyed even after the end of the scope.
 181   // lvalue ranges need be neither copyable nor moveable.
 182   Range<false, false> R(Copies, Moves, Destructors);
 183   {
 184     auto Enumerator = enumerate(R);
 185     (void)Enumerator;
 186     EXPECT_EQ(0, Copies);
 187     EXPECT_EQ(0, Moves);
 188     EXPECT_EQ(0, Destructors);
 189   }
 190   EXPECT_EQ(0, Copies);
 191   EXPECT_EQ(0, Moves);
 192   EXPECT_EQ(0, Destructors);
 193 }
 194
 195 TEST(STLExtrasTest, ApplyTuple) {
 196   auto T = std::make_tuple(1, 3, 7);
 197   auto U = llvm::apply_tuple(
 198       [](int A, int B, int C) { return std::make_tuple(A - B, B - C, C - A); },
 199       T);
 200
 201   EXPECT_EQ(-2, std::get<0>(U));
 202   EXPECT_EQ(-4, std::get<1>(U));
 203   EXPECT_EQ(6, std::get<2>(U));
 204
 205   auto V = llvm::apply_tuple(
 206       [](int A, int B, int C) {
 207         return std::make_tuple(std::make_pair(A, char('A' + A)),
 208                                std::make_pair(B, char('A' + B)),
 209                                std::make_pair(C, char('A' + C)));
 210       },
 211       T);
 212
 213   EXPECT_EQ(std::make_pair(1, 'B'), std::get<0>(V));
 214   EXPECT_EQ(std::make_pair(3, 'D'), std::get<1>(V));
 215   EXPECT_EQ(std::make_pair(7, 'H'), std::get<2>(V));
 216 }
 217
 218 class apply_variadic {
 219   static int apply_one(int X) { return X + 1; }
 220   static char apply_one(char C) { return C + 1; }
 221   static StringRef apply_one(StringRef S) { return S.drop_back(); }
 222
 223 public:
 224   template <typename... Ts>
 225   auto operator()(Ts &&... Items)
 226       -> decltype(std::make_tuple(apply_one(Items)...)) {
 227     return std::make_tuple(apply_one(Items)...);
 228   }
 229 };
 230
 231 TEST(STLExtrasTest, ApplyTupleVariadic) {
 232   auto Items = std::make_tuple(1, llvm::StringRef("Test"), 'X');
 233   auto Values = apply_tuple(apply_variadic(), Items);
 234
 235   EXPECT_EQ(2, std::get<0>(Values));
 236   EXPECT_EQ("Tes", std::get<1>(Values));
 237   EXPECT_EQ('Y', std::get<2>(Values));
 238 }
 239
 240 TEST(STLExtrasTest, CountAdaptor) {
 241   std::vector<int> v;
 242
 243   v.push_back(1);
 244   v.push_back(2);
 245   v.push_back(1);
 246   v.push_back(4);
 247   v.push_back(3);
 248   v.push_back(2);
 249   v.push_back(1);
 250
 251   EXPECT_EQ(3, count(v, 1));
 252   EXPECT_EQ(2, count(v, 2));
 253   EXPECT_EQ(1, count(v, 3));
 254   EXPECT_EQ(1, count(v, 4));
 255 }
 256
 257 TEST(STLExtrasTest, for_each) {
 258   std::vector<int> v{0, 1, 2, 3, 4};
 259   int count = 0;
 260
 261   llvm::for_each(v, [&count](int) { ++count; });
 262   EXPECT_EQ(5, count);
 263 }
 264
 265 TEST(STLExtrasTest, ToVector) {
 266   std::vector<char> v = {'a', 'b', 'c'};
 267   auto Enumerated = to_vector<4>(enumerate(v));
 268   ASSERT_EQ(3u, Enumerated.size());
 269   for (size_t I = 0; I < v.size(); ++I) {
 270     EXPECT_EQ(I, Enumerated[I].index());
 271     EXPECT_EQ(v[I], Enumerated[I].value());
 272   }
 273 }
 274
 275 TEST(STLExtrasTest, ConcatRange) {
 276   std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};
 277   std::vector<int> Test;
 278
 279   std::vector<int> V1234 = {1, 2, 3, 4};
 280   std::list<int> L56 = {5, 6};
 281   SmallVector<int, 2> SV78 = {7, 8};
 282
 283   // Use concat across different sized ranges of different types with different
 284   // iterators.
 285   for (int &i : concat<int>(V1234, L56, SV78))
 286     Test.push_back(i);
 287   EXPECT_EQ(Expected, Test);
 288
 289   // Use concat between a temporary, an L-value, and an R-value to make sure
 290   // complex lifetimes work well.
 291   Test.clear();
 292   for (int &i : concat<int>(std::vector<int>(V1234), L56, std::move(SV78)))
 293     Test.push_back(i);
 294   EXPECT_EQ(Expected, Test);
 295 }
 296
 297 TEST(STLExtrasTest, PartitionAdaptor) {
 298   std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
 299
 300   auto I = partition(V, [](int i) { return i % 2 == 0; });
 301   ASSERT_EQ(V.begin() + 4, I);
 302
 303   // Sort the two halves as partition may have messed with the order.
 304   llvm::sort(V.begin(), I);
 305   llvm::sort(I, V.end());
 306
 307   EXPECT_EQ(2, V[0]);
 308   EXPECT_EQ(4, V[1]);
 309   EXPECT_EQ(6, V[2]);
 310   EXPECT_EQ(8, V[3]);
 311   EXPECT_EQ(1, V[4]);
 312   EXPECT_EQ(3, V[5]);
 313   EXPECT_EQ(5, V[6]);
 314   EXPECT_EQ(7, V[7]);
 315 }
 316
 317 TEST(STLExtrasTest, EraseIf) {
 318   std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
 319
 320   erase_if(V, [](int i) { return i % 2 == 0; });
 321   EXPECT_EQ(4u, V.size());
 322   EXPECT_EQ(1, V[0]);
 323   EXPECT_EQ(3, V[1]);
 324   EXPECT_EQ(5, V[2]);
 325   EXPECT_EQ(7, V[3]);
 326 }
 327
 328 namespace some_namespace {
 329 struct some_struct {
 330   std::vector<int> data;
 331   std::string swap_val;
 332 };
 333
 334 std::vector<int>::const_iterator begin(const some_struct &s) {
 335   return s.data.begin();
 336 }
 337
 338 std::vector<int>::const_iterator end(const some_struct &s) {
 339   return s.data.end();
 340 }
 341
 342 void swap(some_struct &lhs, some_struct &rhs) {
 343   // make swap visible as non-adl swap would even seem to
 344   // work with std::swap which defaults to moving
 345   lhs.swap_val = "lhs";
 346   rhs.swap_val = "rhs";
 347 }
 348 } // namespace some_namespace
 349
 350 TEST(STLExtrasTest, ADLTest) {
 351   some_namespace::some_struct s{{1, 2, 3, 4, 5}, ""};
 352   some_namespace::some_struct s2{{2, 4, 6, 8, 10}, ""};
 353
 354   EXPECT_EQ(*adl_begin(s), 1);
 355   EXPECT_EQ(*(adl_end(s) - 1), 5);
 356
 357   adl_swap(s, s2);
 358   EXPECT_EQ(s.swap_val, "lhs");
 359   EXPECT_EQ(s2.swap_val, "rhs");
 360
 361   int count = 0;
 362   llvm::for_each(s, [&count](int) { ++count; });
 363   EXPECT_EQ(5, count);
 364 }
 365
 366 TEST(STLExtrasTest, EmptyTest) {
 367   std::vector<void*> V;
 368   EXPECT_TRUE(llvm::empty(V));
 369   V.push_back(nullptr);
 370   EXPECT_FALSE(llvm::empty(V));
 371
 372   std::initializer_list<int> E = {};
 373   std::initializer_list<int> NotE = {7, 13, 42};
 374   EXPECT_TRUE(llvm::empty(E));
 375   EXPECT_FALSE(llvm::empty(NotE));
 376
 377   auto R0 = make_range(V.begin(), V.begin());
 378   EXPECT_TRUE(llvm::empty(R0));
 379   auto R1 = make_range(V.begin(), V.end());
 380   EXPECT_FALSE(llvm::empty(R1));
 381 }
 382
 383 TEST(STLExtrasTest, EarlyIncrementTest) {
 384   std::list<int> L = {1, 2, 3, 4};
 385
 386   auto EIR = make_early_inc_range(L);
 387
 388   auto I = EIR.begin();
 389   auto EI = EIR.end();
 390   EXPECT_NE(I, EI);
 391
 392   EXPECT_EQ(1, *I);
 393 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 394 #ifndef NDEBUG
 395   // Repeated dereferences are not allowed.
 396   EXPECT_DEATH(*I, "Cannot dereference");
 397   // Comparison after dereference is not allowed.
 398   EXPECT_DEATH((void)(I == EI), "Cannot compare");
 399   EXPECT_DEATH((void)(I != EI), "Cannot compare");
 400 #endif
 401 #endif
 402
 403   ++I;
 404   EXPECT_NE(I, EI);
 405 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 406 #ifndef NDEBUG
 407   // You cannot increment prior to dereference.
 408   EXPECT_DEATH(++I, "Cannot increment");
 409 #endif
 410 #endif
 411   EXPECT_EQ(2, *I);
 412 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 413 #ifndef NDEBUG
 414   // Repeated dereferences are not allowed.
 415   EXPECT_DEATH(*I, "Cannot dereference");
 416 #endif
 417 #endif
 418
 419   // Inserting shouldn't break anything. We should be able to keep dereferencing
 420   // the currrent iterator and increment. The increment to go to the "next"
 421   // iterator from before we inserted.
 422   L.insert(std::next(L.begin(), 2), -1);
 423   ++I;
 424   EXPECT_EQ(3, *I);
 425
 426   // Erasing the front including the current doesn't break incrementing.
 427   L.erase(L.begin(), std::prev(L.end()));
 428   ++I;
 429   EXPECT_EQ(4, *I);
 430   ++I;
 431   EXPECT_EQ(EIR.end(), I);
 432 }
 433
 434 TEST(STLExtrasTest, splat) {
 435   std::vector<int> V;
 436   EXPECT_FALSE(is_splat(V));
 437
 438   V.push_back(1);
 439   EXPECT_TRUE(is_splat(V));
 440
 441   V.push_back(1);
 442   V.push_back(1);
 443   EXPECT_TRUE(is_splat(V));
 444
 445   V.push_back(2);
 446   EXPECT_FALSE(is_splat(V));
 447 }
 448
 449 TEST(STLExtrasTest, to_address) {
 450   int *V1 = new int;
 451   EXPECT_EQ(V1, to_address(V1));
 452
 453   // Check fancy pointer overload for unique_ptr
 454   std::unique_ptr<int> V2 = std::make_unique<int>(0);
 455   EXPECT_EQ(V2.get(), to_address(V2));
 456
 457   V2.reset(V1);
 458   EXPECT_EQ(V1, to_address(V2));
 459   V2.release();
 460
 461   // Check fancy pointer overload for shared_ptr
 462   std::shared_ptr<int> V3 = std::make_shared<int>(0);
 463   std::shared_ptr<int> V4 = V3;
 464   EXPECT_EQ(V3.get(), V4.get());
 465   EXPECT_EQ(V3.get(), to_address(V3));
 466   EXPECT_EQ(V4.get(), to_address(V4));
 467
 468   V3.reset(V1);
 469   EXPECT_EQ(V1, to_address(V3));
 470 }
 471
 472 TEST(STLExtrasTest, partition_point) {
 473   std::vector<int> V = {1, 3, 5, 7, 9};
 474
 475   // Range version.
 476   EXPECT_EQ(V.begin() + 3,
 477             partition_point(V, [](unsigned X) { return X < 7; }));
 478   EXPECT_EQ(V.begin(), partition_point(V, [](unsigned X) { return X < 1; }));
 479   EXPECT_EQ(V.end(), partition_point(V, [](unsigned X) { return X < 50; }));
 480 }
 481
 482 } // namespace