unittests/ADT/STLExtrasTest.cpp

   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