llvm/unittests/ADT/SmallVectorTest.cpp

   1 //===- llvm/unittest/ADT/SmallVectorTest.cpp ------------------------------===//
   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 // SmallVector unit tests.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/ADT/SmallVector.h"
  14 #include "llvm/ADT/ArrayRef.h"
  15 #include "llvm/Support/Compiler.h"
  16 #include "gtest/gtest.h"
  17 #include <list>
  18 #include <stdarg.h>
  19
  20 using namespace llvm;
  21
  22 namespace {
  23
  24 /// A helper class that counts the total number of constructor and
  25 /// destructor calls.
  26 class Constructable {
  27 private:
  28   static int numConstructorCalls;
  29   static int numMoveConstructorCalls;
  30   static int numCopyConstructorCalls;
  31   static int numDestructorCalls;
  32   static int numAssignmentCalls;
  33   static int numMoveAssignmentCalls;
  34   static int numCopyAssignmentCalls;
  35
  36   bool constructed;
  37   int value;
  38
  39 public:
  40   Constructable() : constructed(true), value(0) {
  41     ++numConstructorCalls;
  42   }
  43
  44   Constructable(int val) : constructed(true), value(val) {
  45     ++numConstructorCalls;
  46   }
  47
  48   Constructable(const Constructable & src) : constructed(true) {
  49     value = src.value;
  50     ++numConstructorCalls;
  51     ++numCopyConstructorCalls;
  52   }
  53
  54   Constructable(Constructable && src) : constructed(true) {
  55     value = src.value;
  56     src.value = 0;
  57     ++numConstructorCalls;
  58     ++numMoveConstructorCalls;
  59   }
  60
  61   ~Constructable() {
  62     EXPECT_TRUE(constructed);
  63     ++numDestructorCalls;
  64     constructed = false;
  65   }
  66
  67   Constructable & operator=(const Constructable & src) {
  68     EXPECT_TRUE(constructed);
  69     value = src.value;
  70     ++numAssignmentCalls;
  71     ++numCopyAssignmentCalls;
  72     return *this;
  73   }
  74
  75   Constructable & operator=(Constructable && src) {
  76     EXPECT_TRUE(constructed);
  77     value = src.value;
  78     src.value = 0;
  79     ++numAssignmentCalls;
  80     ++numMoveAssignmentCalls;
  81     return *this;
  82   }
  83
  84   int getValue() const {
  85     return abs(value);
  86   }
  87
  88   static void reset() {
  89     numConstructorCalls = 0;
  90     numMoveConstructorCalls = 0;
  91     numCopyConstructorCalls = 0;
  92     numDestructorCalls = 0;
  93     numAssignmentCalls = 0;
  94     numMoveAssignmentCalls = 0;
  95     numCopyAssignmentCalls = 0;
  96   }
  97
  98   static int getNumConstructorCalls() {
  99     return numConstructorCalls;
 100   }
 101
 102   static int getNumMoveConstructorCalls() {
 103     return numMoveConstructorCalls;
 104   }
 105
 106   static int getNumCopyConstructorCalls() {
 107     return numCopyConstructorCalls;
 108   }
 109
 110   static int getNumDestructorCalls() {
 111     return numDestructorCalls;
 112   }
 113
 114   static int getNumAssignmentCalls() {
 115     return numAssignmentCalls;
 116   }
 117
 118   static int getNumMoveAssignmentCalls() {
 119     return numMoveAssignmentCalls;
 120   }
 121
 122   static int getNumCopyAssignmentCalls() {
 123     return numCopyAssignmentCalls;
 124   }
 125
 126   friend bool operator==(const Constructable &c0, const Constructable &c1) {
 127     return c0.getValue() == c1.getValue();
 128   }
 129
 130   friend bool LLVM_ATTRIBUTE_UNUSED operator!=(const Constructable &c0,
 131                                                const Constructable &c1) {
 132     return c0.getValue() != c1.getValue();
 133   }
 134
 135   friend bool operator<(const Constructable &c0, const Constructable &c1) {
 136     return c0.getValue() < c1.getValue();
 137   }
 138   friend bool LLVM_ATTRIBUTE_UNUSED operator<=(const Constructable &c0,
 139                                                const Constructable &c1) {
 140     return c0.getValue() <= c1.getValue();
 141   }
 142   friend bool LLVM_ATTRIBUTE_UNUSED operator>(const Constructable &c0,
 143                                               const Constructable &c1) {
 144     return c0.getValue() > c1.getValue();
 145   }
 146   friend bool LLVM_ATTRIBUTE_UNUSED operator>=(const Constructable &c0,
 147                                                const Constructable &c1) {
 148     return c0.getValue() >= c1.getValue();
 149   }
 150 };
 151
 152 int Constructable::numConstructorCalls;
 153 int Constructable::numCopyConstructorCalls;
 154 int Constructable::numMoveConstructorCalls;
 155 int Constructable::numDestructorCalls;
 156 int Constructable::numAssignmentCalls;
 157 int Constructable::numCopyAssignmentCalls;
 158 int Constructable::numMoveAssignmentCalls;
 159
 160 struct NonCopyable {
 161   NonCopyable() {}
 162   NonCopyable(NonCopyable &&) {}
 163   NonCopyable &operator=(NonCopyable &&) { return *this; }
 164 private:
 165   NonCopyable(const NonCopyable &) = delete;
 166   NonCopyable &operator=(const NonCopyable &) = delete;
 167 };
 168
 169 LLVM_ATTRIBUTE_USED void CompileTest() {
 170   SmallVector<NonCopyable, 0> V;
 171   V.resize(42);
 172 }
 173
 174 TEST(SmallVectorTest, ConstructNonCopyableTest) {
 175   SmallVector<NonCopyable, 0> V(42);
 176   EXPECT_EQ(V.size(), (size_t)42);
 177 }
 178
 179 // Assert that v contains the specified values, in order.
 180 template <typename VectorT>
 181 void assertValuesInOrder(VectorT &v, size_t size, ...) {
 182   EXPECT_EQ(size, v.size());
 183
 184   va_list ap;
 185   va_start(ap, size);
 186   for (size_t i = 0; i < size; ++i) {
 187     int value = va_arg(ap, int);
 188     EXPECT_EQ(value, v[i].getValue());
 189   }
 190
 191   va_end(ap);
 192 }
 193
 194 template <typename VectorT> void assertEmpty(VectorT &v) {
 195   // Size tests
 196   EXPECT_EQ(0u, v.size());
 197   EXPECT_TRUE(v.empty());
 198
 199   // Iterator tests
 200   EXPECT_TRUE(v.begin() == v.end());
 201 }
 202
 203 // Generate a sequence of values to initialize the vector.
 204 template <typename VectorT> void makeSequence(VectorT &v, int start, int end) {
 205   for (int i = start; i <= end; ++i) {
 206     v.push_back(Constructable(i));
 207   }
 208 }
 209
 210 template <typename T, unsigned N>
 211 constexpr static unsigned NumBuiltinElts(const SmallVector<T, N> &) {
 212   return N;
 213 }
 214
 215 class SmallVectorTestBase : public testing::Test {
 216 protected:
 217   void SetUp() override { Constructable::reset(); }
 218 };
 219
 220 // Test fixture class
 221 template <typename VectorT>
 222 class SmallVectorTest : public SmallVectorTestBase {
 223 protected:
 224   VectorT theVector;
 225   VectorT otherVector;
 226 };
 227
 228
 229 typedef ::testing::Types<SmallVector<Constructable, 0>,
 230                          SmallVector<Constructable, 1>,
 231                          SmallVector<Constructable, 2>,
 232                          SmallVector<Constructable, 4>,
 233                          SmallVector<Constructable, 5>
 234                          > SmallVectorTestTypes;
 235 TYPED_TEST_SUITE(SmallVectorTest, SmallVectorTestTypes, );
 236
 237 // Constructor test.
 238 TYPED_TEST(SmallVectorTest, ConstructorNonIterTest) {
 239   SCOPED_TRACE("ConstructorTest");
 240   auto &V = this->theVector;
 241   V = SmallVector<Constructable, 2>(2, 2);
 242   assertValuesInOrder(V, 2u, 2, 2);
 243 }
 244
 245 // Constructor test.
 246 TYPED_TEST(SmallVectorTest, ConstructorIterTest) {
 247   SCOPED_TRACE("ConstructorTest");
 248   int arr[] = {1, 2, 3};
 249   auto &V = this->theVector;
 250   V = SmallVector<Constructable, 4>(std::begin(arr), std::end(arr));
 251   assertValuesInOrder(V, 3u, 1, 2, 3);
 252 }
 253
 254 // Constructor test.
 255 TYPED_TEST(SmallVectorTest, ConstructorFromArrayRefSimpleTest) {
 256   SCOPED_TRACE("ConstructorFromArrayRefSimpleTest");
 257   std::array<Constructable, 3> StdArray = {Constructable(1), Constructable(2),
 258                                            Constructable(3)};
 259   ArrayRef<Constructable> Array = StdArray;
 260   auto &V = this->theVector;
 261   V = SmallVector<Constructable, 4>(Array);
 262   assertValuesInOrder(V, 3u, 1, 2, 3);
 263   ASSERT_EQ(NumBuiltinElts(TypeParam{}), NumBuiltinElts(V));
 264 }
 265
 266 // New vector test.
 267 TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
 268   SCOPED_TRACE("EmptyVectorTest");
 269   auto &V = this->theVector;
 270   assertEmpty(V);
 271   EXPECT_TRUE(V.rbegin() == V.rend());
 272   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 273   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 274 }
 275
 276 // Simple insertions and deletions.
 277 TYPED_TEST(SmallVectorTest, PushPopTest) {
 278   SCOPED_TRACE("PushPopTest");
 279   auto &V = this->theVector;
 280   // Track whether the vector will potentially have to grow.
 281   bool RequiresGrowth = V.capacity() < 3;
 282
 283   // Push an element
 284   V.push_back(Constructable(1));
 285
 286   // Size tests
 287   assertValuesInOrder(V, 1u, 1);
 288   EXPECT_FALSE(V.begin() == V.end());
 289   EXPECT_FALSE(V.empty());
 290
 291   // Push another element
 292   V.push_back(Constructable(2));
 293   assertValuesInOrder(V, 2u, 1, 2);
 294
 295   // Insert at beginning. Reserve space to avoid reference invalidation from
 296   // V[1].
 297   V.reserve(V.size() + 1);
 298   V.insert(V.begin(), V[1]);
 299   assertValuesInOrder(V, 3u, 2, 1, 2);
 300
 301   // Pop one element
 302   V.pop_back();
 303   assertValuesInOrder(V, 2u, 2, 1);
 304
 305   // Pop remaining elements
 306   V.pop_back_n(2);
 307   assertEmpty(V);
 308
 309   // Check number of constructor calls. Should be 2 for each list element,
 310   // one for the argument to push_back, one for the argument to insert,
 311   // and one for the list element itself.
 312   if (!RequiresGrowth) {
 313     EXPECT_EQ(5, Constructable::getNumConstructorCalls());
 314     EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 315   } else {
 316     // If we had to grow the vector, these only have a lower bound, but should
 317     // always be equal.
 318     EXPECT_LE(5, Constructable::getNumConstructorCalls());
 319     EXPECT_EQ(Constructable::getNumConstructorCalls(),
 320               Constructable::getNumDestructorCalls());
 321   }
 322 }
 323
 324 // Clear test.
 325 TYPED_TEST(SmallVectorTest, ClearTest) {
 326   SCOPED_TRACE("ClearTest");
 327   auto &V = this->theVector;
 328   V.reserve(2);
 329   makeSequence(V, 1, 2);
 330   V.clear();
 331
 332   assertEmpty(V);
 333   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 334   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
 335 }
 336
 337 // Resize smaller test.
 338 TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
 339   SCOPED_TRACE("ResizeShrinkTest");
 340   auto &V = this->theVector;
 341   V.reserve(3);
 342   makeSequence(V, 1, 3);
 343   V.resize(1);
 344
 345   assertValuesInOrder(V, 1u, 1);
 346   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 347   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 348 }
 349
 350 // Truncate test.
 351 TYPED_TEST(SmallVectorTest, TruncateTest) {
 352   SCOPED_TRACE("TruncateTest");
 353   auto &V = this->theVector;
 354   V.reserve(3);
 355   makeSequence(V, 1, 3);
 356   V.truncate(1);
 357
 358   assertValuesInOrder(V, 1u, 1);
 359   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 360   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 361
 362 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
 363   EXPECT_DEATH(V.truncate(2), "Cannot increase size");
 364 #endif
 365   V.truncate(1);
 366   assertValuesInOrder(V, 1u, 1);
 367   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 368   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 369
 370   V.truncate(0);
 371   assertEmpty(V);
 372   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 373   EXPECT_EQ(6, Constructable::getNumDestructorCalls());
 374 }
 375
 376 // Resize bigger test.
 377 TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
 378   SCOPED_TRACE("ResizeGrowTest");
 379   auto &V = this->theVector;
 380   V.resize(2);
 381
 382   EXPECT_EQ(2, Constructable::getNumConstructorCalls());
 383   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 384   EXPECT_EQ(2u, V.size());
 385 }
 386
 387 TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) {
 388   auto &V = this->theVector;
 389   V.resize(2);
 390
 391   Constructable::reset();
 392
 393   V.resize(4);
 394
 395   size_t Ctors = Constructable::getNumConstructorCalls();
 396   EXPECT_TRUE(Ctors == 2 || Ctors == 4);
 397   size_t MoveCtors = Constructable::getNumMoveConstructorCalls();
 398   EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2);
 399   size_t Dtors = Constructable::getNumDestructorCalls();
 400   EXPECT_TRUE(Dtors == 0 || Dtors == 2);
 401 }
 402
 403 // Resize with fill value.
 404 TYPED_TEST(SmallVectorTest, ResizeFillTest) {
 405   SCOPED_TRACE("ResizeFillTest");
 406   auto &V = this->theVector;
 407   V.resize(3, Constructable(77));
 408   assertValuesInOrder(V, 3u, 77, 77, 77);
 409 }
 410
 411 TEST(SmallVectorTest, ResizeForOverwrite) {
 412   {
 413     // Heap allocated storage.
 414     SmallVector<unsigned, 0> V;
 415     V.push_back(5U);
 416     V.pop_back();
 417     V.resize_for_overwrite(V.size() + 1U);
 418     EXPECT_EQ(5U, V.back());
 419     V.pop_back();
 420     V.resize(V.size() + 1);
 421     EXPECT_EQ(0U, V.back());
 422   }
 423   {
 424     // Inline storage.
 425     SmallVector<unsigned, 2> V;
 426     V.push_back(5U);
 427     V.pop_back();
 428     V.resize_for_overwrite(V.size() + 1U);
 429     EXPECT_EQ(5U, V.back());
 430     V.pop_back();
 431     V.resize(V.size() + 1);
 432     EXPECT_EQ(0U, V.back());
 433   }
 434 }
 435
 436 // Overflow past fixed size.
 437 TYPED_TEST(SmallVectorTest, OverflowTest) {
 438   SCOPED_TRACE("OverflowTest");
 439   auto &V = this->theVector;
 440   // Push more elements than the fixed size.
 441   makeSequence(V, 1, 10);
 442
 443   // Test size and values.
 444   EXPECT_EQ(10u, V.size());
 445   for (int i = 0; i < 10; ++i) {
 446     EXPECT_EQ(i + 1, V[i].getValue());
 447   }
 448
 449   // Now resize back to fixed size.
 450   V.resize(1);
 451
 452   assertValuesInOrder(V, 1u, 1);
 453 }
 454
 455 // Iteration tests.
 456 TYPED_TEST(SmallVectorTest, IterationTest) {
 457   auto &V = this->theVector;
 458   makeSequence(V, 1, 2);
 459
 460   // Forward Iteration
 461   typename TypeParam::iterator it = V.begin();
 462   EXPECT_TRUE(*it == V.front());
 463   EXPECT_TRUE(*it == V[0]);
 464   EXPECT_EQ(1, it->getValue());
 465   ++it;
 466   EXPECT_TRUE(*it == V[1]);
 467   EXPECT_TRUE(*it == V.back());
 468   EXPECT_EQ(2, it->getValue());
 469   ++it;
 470   EXPECT_TRUE(it == V.end());
 471   --it;
 472   EXPECT_TRUE(*it == V[1]);
 473   EXPECT_EQ(2, it->getValue());
 474   --it;
 475   EXPECT_TRUE(*it == V[0]);
 476   EXPECT_EQ(1, it->getValue());
 477
 478   // Reverse Iteration
 479   typename TypeParam::reverse_iterator rit = V.rbegin();
 480   EXPECT_TRUE(*rit == V[1]);
 481   EXPECT_EQ(2, rit->getValue());
 482   ++rit;
 483   EXPECT_TRUE(*rit == V[0]);
 484   EXPECT_EQ(1, rit->getValue());
 485   ++rit;
 486   EXPECT_TRUE(rit == V.rend());
 487   --rit;
 488   EXPECT_TRUE(*rit == V[0]);
 489   EXPECT_EQ(1, rit->getValue());
 490   --rit;
 491   EXPECT_TRUE(*rit == V[1]);
 492   EXPECT_EQ(2, rit->getValue());
 493 }
 494
 495 // Swap test.
 496 TYPED_TEST(SmallVectorTest, SwapTest) {
 497   SCOPED_TRACE("SwapTest");
 498   auto &V = this->theVector;
 499   auto &U = this->otherVector;
 500   makeSequence(V, 1, 2);
 501   std::swap(V, U);
 502
 503   assertEmpty(V);
 504   assertValuesInOrder(U, 2u, 1, 2);
 505 }
 506
 507 // Append test
 508 TYPED_TEST(SmallVectorTest, AppendTest) {
 509   SCOPED_TRACE("AppendTest");
 510   auto &V = this->theVector;
 511   auto &U = this->otherVector;
 512   makeSequence(U, 2, 3);
 513
 514   V.push_back(Constructable(1));
 515   V.append(U.begin(), U.end());
 516
 517   assertValuesInOrder(V, 3u, 1, 2, 3);
 518 }
 519
 520 // Append repeated test
 521 TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
 522   SCOPED_TRACE("AppendRepeatedTest");
 523   auto &V = this->theVector;
 524   V.push_back(Constructable(1));
 525   V.append(2, Constructable(77));
 526   assertValuesInOrder(V, 3u, 1, 77, 77);
 527 }
 528
 529 // Append test
 530 TYPED_TEST(SmallVectorTest, AppendNonIterTest) {
 531   SCOPED_TRACE("AppendRepeatedTest");
 532   auto &V = this->theVector;
 533   V.push_back(Constructable(1));
 534   V.append(2, 7);
 535   assertValuesInOrder(V, 3u, 1, 7, 7);
 536 }
 537
 538 struct output_iterator {
 539   typedef std::output_iterator_tag iterator_category;
 540   typedef int value_type;
 541   typedef int difference_type;
 542   typedef value_type *pointer;
 543   typedef value_type &reference;
 544   operator int() { return 2; }
 545   operator Constructable() { return 7; }
 546 };
 547
 548 TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) {
 549   SCOPED_TRACE("AppendRepeatedTest");
 550   auto &V = this->theVector;
 551   V.push_back(Constructable(1));
 552   V.append(output_iterator(), output_iterator());
 553   assertValuesInOrder(V, 3u, 1, 7, 7);
 554 }
 555
 556 TYPED_TEST(SmallVectorTest, AppendSmallVector) {
 557   SCOPED_TRACE("AppendSmallVector");
 558   auto &V = this->theVector;
 559   SmallVector<Constructable, 3> otherVector = {7, 7};
 560   V.push_back(Constructable(1));
 561   V.append(otherVector);
 562   assertValuesInOrder(V, 3u, 1, 7, 7);
 563 }
 564
 565 // Assign test
 566 TYPED_TEST(SmallVectorTest, AssignTest) {
 567   SCOPED_TRACE("AssignTest");
 568   auto &V = this->theVector;
 569   V.push_back(Constructable(1));
 570   V.assign(2, Constructable(77));
 571   assertValuesInOrder(V, 2u, 77, 77);
 572 }
 573
 574 // Assign test
 575 TYPED_TEST(SmallVectorTest, AssignRangeTest) {
 576   SCOPED_TRACE("AssignTest");
 577   auto &V = this->theVector;
 578   V.push_back(Constructable(1));
 579   int arr[] = {1, 2, 3};
 580   V.assign(std::begin(arr), std::end(arr));
 581   assertValuesInOrder(V, 3u, 1, 2, 3);
 582 }
 583
 584 // Assign test
 585 TYPED_TEST(SmallVectorTest, AssignNonIterTest) {
 586   SCOPED_TRACE("AssignTest");
 587   auto &V = this->theVector;
 588   V.push_back(Constructable(1));
 589   V.assign(2, 7);
 590   assertValuesInOrder(V, 2u, 7, 7);
 591 }
 592
 593 TYPED_TEST(SmallVectorTest, AssignSmallVector) {
 594   SCOPED_TRACE("AssignSmallVector");
 595   auto &V = this->theVector;
 596   SmallVector<Constructable, 3> otherVector = {7, 7};
 597   V.push_back(Constructable(1));
 598   V.assign(otherVector);
 599   assertValuesInOrder(V, 2u, 7, 7);
 600 }
 601
 602 // Move-assign test
 603 TYPED_TEST(SmallVectorTest, MoveAssignTest) {
 604   SCOPED_TRACE("MoveAssignTest");
 605   auto &V = this->theVector;
 606   auto &U = this->otherVector;
 607   // Set up our vector with a single element, but enough capacity for 4.
 608   V.reserve(4);
 609   V.push_back(Constructable(1));
 610
 611   // Set up the other vector with 2 elements.
 612   U.push_back(Constructable(2));
 613   U.push_back(Constructable(3));
 614
 615   // Move-assign from the other vector.
 616   V = std::move(U);
 617
 618   // Make sure we have the right result.
 619   assertValuesInOrder(V, 2u, 2, 3);
 620
 621   // Make sure the # of constructor/destructor calls line up. There
 622   // are two live objects after clearing the other vector.
 623   U.clear();
 624   EXPECT_EQ(Constructable::getNumConstructorCalls()-2,
 625             Constructable::getNumDestructorCalls());
 626
 627   // There shouldn't be any live objects any more.
 628   V.clear();
 629   EXPECT_EQ(Constructable::getNumConstructorCalls(),
 630             Constructable::getNumDestructorCalls());
 631 }
 632
 633 // Erase a single element
 634 TYPED_TEST(SmallVectorTest, EraseTest) {
 635   SCOPED_TRACE("EraseTest");
 636   auto &V = this->theVector;
 637   makeSequence(V, 1, 3);
 638   const auto &theConstVector = V;
 639   V.erase(theConstVector.begin());
 640   assertValuesInOrder(V, 2u, 2, 3);
 641 }
 642
 643 // Erase a range of elements
 644 TYPED_TEST(SmallVectorTest, EraseRangeTest) {
 645   SCOPED_TRACE("EraseRangeTest");
 646   auto &V = this->theVector;
 647   makeSequence(V, 1, 3);
 648   const auto &theConstVector = V;
 649   V.erase(theConstVector.begin(), theConstVector.begin() + 2);
 650   assertValuesInOrder(V, 1u, 3);
 651 }
 652
 653 // Insert a single element.
 654 TYPED_TEST(SmallVectorTest, InsertTest) {
 655   SCOPED_TRACE("InsertTest");
 656   auto &V = this->theVector;
 657   makeSequence(V, 1, 3);
 658   typename TypeParam::iterator I = V.insert(V.begin() + 1, Constructable(77));
 659   EXPECT_EQ(V.begin() + 1, I);
 660   assertValuesInOrder(V, 4u, 1, 77, 2, 3);
 661 }
 662
 663 // Insert a copy of a single element.
 664 TYPED_TEST(SmallVectorTest, InsertCopy) {
 665   SCOPED_TRACE("InsertTest");
 666   auto &V = this->theVector;
 667   makeSequence(V, 1, 3);
 668   Constructable C(77);
 669   typename TypeParam::iterator I = V.insert(V.begin() + 1, C);
 670   EXPECT_EQ(V.begin() + 1, I);
 671   assertValuesInOrder(V, 4u, 1, 77, 2, 3);
 672 }
 673
 674 // Insert repeated elements.
 675 TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
 676   SCOPED_TRACE("InsertRepeatedTest");
 677   auto &V = this->theVector;
 678   makeSequence(V, 1, 4);
 679   Constructable::reset();
 680   auto I = V.insert(V.begin() + 1, 2, Constructable(16));
 681   // Move construct the top element into newly allocated space, and optionally
 682   // reallocate the whole buffer, move constructing into it.
 683   // FIXME: This is inefficient, we shouldn't move things into newly allocated
 684   // space, then move them up/around, there should only be 2 or 4 move
 685   // constructions here.
 686   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
 687               Constructable::getNumMoveConstructorCalls() == 6);
 688   // Move assign the next two to shift them up and make a gap.
 689   EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());
 690   // Copy construct the two new elements from the parameter.
 691   EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
 692   // All without any copy construction.
 693   EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
 694   EXPECT_EQ(V.begin() + 1, I);
 695   assertValuesInOrder(V, 6u, 1, 16, 16, 2, 3, 4);
 696 }
 697
 698 TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) {
 699   SCOPED_TRACE("InsertRepeatedTest");
 700   auto &V = this->theVector;
 701   makeSequence(V, 1, 4);
 702   Constructable::reset();
 703   auto I = V.insert(V.begin() + 1, 2, 7);
 704   EXPECT_EQ(V.begin() + 1, I);
 705   assertValuesInOrder(V, 6u, 1, 7, 7, 2, 3, 4);
 706 }
 707
 708 TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) {
 709   SCOPED_TRACE("InsertRepeatedTest");
 710   auto &V = this->theVector;
 711   makeSequence(V, 1, 4);
 712   Constructable::reset();
 713   auto I = V.insert(V.end(), 2, Constructable(16));
 714   // Just copy construct them into newly allocated space
 715   EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
 716   // Move everything across if reallocation is needed.
 717   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
 718               Constructable::getNumMoveConstructorCalls() == 4);
 719   // Without ever moving or copying anything else.
 720   EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
 721   EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
 722
 723   EXPECT_EQ(V.begin() + 4, I);
 724   assertValuesInOrder(V, 6u, 1, 2, 3, 4, 16, 16);
 725 }
 726
 727 TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) {
 728   SCOPED_TRACE("InsertRepeatedTest");
 729   auto &V = this->theVector;
 730   makeSequence(V, 10, 15);
 731
 732   // Empty insert.
 733   EXPECT_EQ(V.end(), V.insert(V.end(), 0, Constructable(42)));
 734   EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, 0, Constructable(42)));
 735 }
 736
 737 // Insert range.
 738 TYPED_TEST(SmallVectorTest, InsertRangeTest) {
 739   SCOPED_TRACE("InsertRangeTest");
 740   auto &V = this->theVector;
 741   Constructable Arr[3] =
 742     { Constructable(77), Constructable(77), Constructable(77) };
 743
 744   makeSequence(V, 1, 3);
 745   Constructable::reset();
 746   auto I = V.insert(V.begin() + 1, Arr, Arr + 3);
 747   // Move construct the top 3 elements into newly allocated space.
 748   // Possibly move the whole sequence into new space first.
 749   // FIXME: This is inefficient, we shouldn't move things into newly allocated
 750   // space, then move them up/around, there should only be 2 or 3 move
 751   // constructions here.
 752   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
 753               Constructable::getNumMoveConstructorCalls() == 5);
 754   // Copy assign the lower 2 new elements into existing space.
 755   EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
 756   // Copy construct the third element into newly allocated space.
 757   EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());
 758   EXPECT_EQ(V.begin() + 1, I);
 759   assertValuesInOrder(V, 6u, 1, 77, 77, 77, 2, 3);
 760 }
 761
 762
 763 TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) {
 764   SCOPED_TRACE("InsertRangeTest");
 765   auto &V = this->theVector;
 766   Constructable Arr[3] =
 767     { Constructable(77), Constructable(77), Constructable(77) };
 768
 769   makeSequence(V, 1, 3);
 770
 771   // Insert at end.
 772   Constructable::reset();
 773   auto I = V.insert(V.end(), Arr, Arr + 3);
 774   // Copy construct the 3 elements into new space at the top.
 775   EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());
 776   // Don't copy/move anything else.
 777   EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
 778   // Reallocation might occur, causing all elements to be moved into the new
 779   // buffer.
 780   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
 781               Constructable::getNumMoveConstructorCalls() == 3);
 782   EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
 783   EXPECT_EQ(V.begin() + 3, I);
 784   assertValuesInOrder(V, 6u, 1, 2, 3, 77, 77, 77);
 785 }
 786
 787 TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) {
 788   SCOPED_TRACE("InsertRangeTest");
 789   auto &V = this->theVector;
 790   makeSequence(V, 1, 3);
 791
 792   // Empty insert.
 793   EXPECT_EQ(V.end(), V.insert(V.end(), V.begin(), V.begin()));
 794   EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, V.begin(), V.begin()));
 795 }
 796
 797 // Comparison tests.
 798 TYPED_TEST(SmallVectorTest, ComparisonEqualityTest) {
 799   SCOPED_TRACE("ComparisonEqualityTest");
 800   auto &V = this->theVector;
 801   auto &U = this->otherVector;
 802   makeSequence(V, 1, 3);
 803   makeSequence(U, 1, 3);
 804
 805   EXPECT_TRUE(V == U);
 806   EXPECT_FALSE(V != U);
 807
 808   U.clear();
 809   makeSequence(U, 2, 4);
 810
 811   EXPECT_FALSE(V == U);
 812   EXPECT_TRUE(V != U);
 813 }
 814
 815 // Comparison tests.
 816 TYPED_TEST(SmallVectorTest, ComparisonLessThanTest) {
 817   SCOPED_TRACE("ComparisonLessThanTest");
 818   auto &V = this->theVector;
 819   auto &U = this->otherVector;
 820   V = {1, 2, 4};
 821   U = {1, 4};
 822
 823   EXPECT_TRUE(V < U);
 824   EXPECT_TRUE(V <= U);
 825   EXPECT_FALSE(V > U);
 826   EXPECT_FALSE(V >= U);
 827
 828   EXPECT_FALSE(U < V);
 829   EXPECT_FALSE(U <= V);
 830   EXPECT_TRUE(U > V);
 831   EXPECT_TRUE(U >= V);
 832
 833   U = {1, 2, 4};
 834
 835   EXPECT_FALSE(V < U);
 836   EXPECT_TRUE(V <= U);
 837   EXPECT_FALSE(V > U);
 838   EXPECT_TRUE(V >= U);
 839
 840   EXPECT_FALSE(U < V);
 841   EXPECT_TRUE(U <= V);
 842   EXPECT_FALSE(U > V);
 843   EXPECT_TRUE(U >= V);
 844 }
 845
 846 // Constant vector tests.
 847 TYPED_TEST(SmallVectorTest, ConstVectorTest) {
 848   const TypeParam constVector;
 849
 850   EXPECT_EQ(0u, constVector.size());
 851   EXPECT_TRUE(constVector.empty());
 852   EXPECT_TRUE(constVector.begin() == constVector.end());
 853 }
 854
 855 // Direct array access.
 856 TYPED_TEST(SmallVectorTest, DirectVectorTest) {
 857   auto &V = this->theVector;
 858   EXPECT_EQ(0u, V.size());
 859   V.reserve(4);
 860   EXPECT_LE(4u, V.capacity());
 861   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 862   V.push_back(1);
 863   V.push_back(2);
 864   V.push_back(3);
 865   V.push_back(4);
 866   EXPECT_EQ(4u, V.size());
 867   EXPECT_EQ(8, Constructable::getNumConstructorCalls());
 868   EXPECT_EQ(1, V[0].getValue());
 869   EXPECT_EQ(2, V[1].getValue());
 870   EXPECT_EQ(3, V[2].getValue());
 871   EXPECT_EQ(4, V[3].getValue());
 872 }
 873
 874 TYPED_TEST(SmallVectorTest, IteratorTest) {
 875   auto &V = this->theVector;
 876   std::list<int> L;
 877   V.insert(V.end(), L.begin(), L.end());
 878 }
 879
 880 template <typename InvalidType> class DualSmallVectorsTest;
 881
 882 template <typename VectorT1, typename VectorT2>
 883 class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase {
 884 protected:
 885   VectorT1 theVector;
 886   VectorT2 otherVector;
 887 };
 888
 889 typedef ::testing::Types<
 890     // Small mode -> Small mode.
 891     std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>,
 892     // Small mode -> Big mode.
 893     std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>,
 894     // Big mode -> Small mode.
 895     std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 4>>,
 896     // Big mode -> Big mode.
 897     std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 2>>
 898   > DualSmallVectorTestTypes;
 899
 900 TYPED_TEST_SUITE(DualSmallVectorsTest, DualSmallVectorTestTypes, );
 901
 902 TYPED_TEST(DualSmallVectorsTest, MoveAssignment) {
 903   SCOPED_TRACE("MoveAssignTest-DualVectorTypes");
 904   auto &V = this->theVector;
 905   auto &U = this->otherVector;
 906   // Set up our vector with four elements.
 907   for (unsigned I = 0; I < 4; ++I)
 908     U.push_back(Constructable(I));
 909
 910   const Constructable *OrigDataPtr = U.data();
 911
 912   // Move-assign from the other vector.
 913   V = std::move(static_cast<SmallVectorImpl<Constructable> &>(U));
 914
 915   // Make sure we have the right result.
 916   assertValuesInOrder(V, 4u, 0, 1, 2, 3);
 917
 918   // Make sure the # of constructor/destructor calls line up. There
 919   // are two live objects after clearing the other vector.
 920   U.clear();
 921   EXPECT_EQ(Constructable::getNumConstructorCalls()-4,
 922             Constructable::getNumDestructorCalls());
 923
 924   // If the source vector (otherVector) was in small-mode, assert that we just
 925   // moved the data pointer over.
 926   EXPECT_TRUE(NumBuiltinElts(U) == 4 || V.data() == OrigDataPtr);
 927
 928   // There shouldn't be any live objects any more.
 929   V.clear();
 930   EXPECT_EQ(Constructable::getNumConstructorCalls(),
 931             Constructable::getNumDestructorCalls());
 932
 933   // We shouldn't have copied anything in this whole process.
 934   EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0);
 935 }
 936
 937 struct notassignable {
 938   int &x;
 939   notassignable(int &x) : x(x) {}
 940 };
 941
 942 TEST(SmallVectorCustomTest, NoAssignTest) {
 943   int x = 0;
 944   SmallVector<notassignable, 2> vec;
 945   vec.push_back(notassignable(x));
 946   x = 42;
 947   EXPECT_EQ(42, vec.pop_back_val().x);
 948 }
 949
 950 struct MovedFrom {
 951   bool hasValue;
 952   MovedFrom() : hasValue(true) {
 953   }
 954   MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) {
 955     m.hasValue = false;
 956   }
 957   MovedFrom &operator=(MovedFrom&& m) {
 958     hasValue = m.hasValue;
 959     m.hasValue = false;
 960     return *this;
 961   }
 962 };
 963
 964 TEST(SmallVectorTest, MidInsert) {
 965   SmallVector<MovedFrom, 3> v;
 966   v.push_back(MovedFrom());
 967   v.insert(v.begin(), MovedFrom());
 968   for (MovedFrom &m : v)
 969     EXPECT_TRUE(m.hasValue);
 970 }
 971
 972 enum EmplaceableArgState {
 973   EAS_Defaulted,
 974   EAS_Arg,
 975   EAS_LValue,
 976   EAS_RValue,
 977   EAS_Failure
 978 };
 979 template <int I> struct EmplaceableArg {
 980   EmplaceableArgState State;
 981   EmplaceableArg() : State(EAS_Defaulted) {}
 982   EmplaceableArg(EmplaceableArg &&X)
 983       : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {}
 984   EmplaceableArg(EmplaceableArg &X)
 985       : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {}
 986
 987   explicit EmplaceableArg(bool) : State(EAS_Arg) {}
 988
 989 private:
 990   EmplaceableArg &operator=(EmplaceableArg &&) = delete;
 991   EmplaceableArg &operator=(const EmplaceableArg &) = delete;
 992 };
 993
 994 enum EmplaceableState { ES_Emplaced, ES_Moved };
 995 struct Emplaceable {
 996   EmplaceableArg<0> A0;
 997   EmplaceableArg<1> A1;
 998   EmplaceableArg<2> A2;
 999   EmplaceableArg<3> A3;
1000   EmplaceableState State;
1001
1002   Emplaceable() : State(ES_Emplaced) {}
1003
1004   template <class A0Ty>
1005   explicit Emplaceable(A0Ty &&A0)
1006       : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {}
1007
1008   template <class A0Ty, class A1Ty>
1009   Emplaceable(A0Ty &&A0, A1Ty &&A1)
1010       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
1011         State(ES_Emplaced) {}
1012
1013   template <class A0Ty, class A1Ty, class A2Ty>
1014   Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2)
1015       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
1016         A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {}
1017
1018   template <class A0Ty, class A1Ty, class A2Ty, class A3Ty>
1019   Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3)
1020       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
1021         A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)),
1022         State(ES_Emplaced) {}
1023
1024   Emplaceable(Emplaceable &&) : State(ES_Moved) {}
1025   Emplaceable &operator=(Emplaceable &&) {
1026     State = ES_Moved;
1027     return *this;
1028   }
1029
1030 private:
1031   Emplaceable(const Emplaceable &) = delete;
1032   Emplaceable &operator=(const Emplaceable &) = delete;
1033 };
1034
1035 TEST(SmallVectorTest, EmplaceBack) {
1036   EmplaceableArg<0> A0(true);
1037   EmplaceableArg<1> A1(true);
1038   EmplaceableArg<2> A2(true);
1039   EmplaceableArg<3> A3(true);
1040   {
1041     SmallVector<Emplaceable, 3> V;
1042     Emplaceable &back = V.emplace_back();
1043     EXPECT_TRUE(&back == &V.back());
1044     EXPECT_TRUE(V.size() == 1);
1045     EXPECT_TRUE(back.State == ES_Emplaced);
1046     EXPECT_TRUE(back.A0.State == EAS_Defaulted);
1047     EXPECT_TRUE(back.A1.State == EAS_Defaulted);
1048     EXPECT_TRUE(back.A2.State == EAS_Defaulted);
1049     EXPECT_TRUE(back.A3.State == EAS_Defaulted);
1050   }
1051   {
1052     SmallVector<Emplaceable, 3> V;
1053     Emplaceable &back = V.emplace_back(std::move(A0));
1054     EXPECT_TRUE(&back == &V.back());
1055     EXPECT_TRUE(V.size() == 1);
1056     EXPECT_TRUE(back.State == ES_Emplaced);
1057     EXPECT_TRUE(back.A0.State == EAS_RValue);
1058     EXPECT_TRUE(back.A1.State == EAS_Defaulted);
1059     EXPECT_TRUE(back.A2.State == EAS_Defaulted);
1060     EXPECT_TRUE(back.A3.State == EAS_Defaulted);
1061   }
1062   {
1063     SmallVector<Emplaceable, 3> V;
1064     Emplaceable &back = V.emplace_back(A0);
1065     EXPECT_TRUE(&back == &V.back());
1066     EXPECT_TRUE(V.size() == 1);
1067     EXPECT_TRUE(back.State == ES_Emplaced);
1068     EXPECT_TRUE(back.A0.State == EAS_LValue);
1069     EXPECT_TRUE(back.A1.State == EAS_Defaulted);
1070     EXPECT_TRUE(back.A2.State == EAS_Defaulted);
1071     EXPECT_TRUE(back.A3.State == EAS_Defaulted);
1072   }
1073   {
1074     SmallVector<Emplaceable, 3> V;
1075     Emplaceable &back = V.emplace_back(A0, A1);
1076     EXPECT_TRUE(&back == &V.back());
1077     EXPECT_TRUE(V.size() == 1);
1078     EXPECT_TRUE(back.State == ES_Emplaced);
1079     EXPECT_TRUE(back.A0.State == EAS_LValue);
1080     EXPECT_TRUE(back.A1.State == EAS_LValue);
1081     EXPECT_TRUE(back.A2.State == EAS_Defaulted);
1082     EXPECT_TRUE(back.A3.State == EAS_Defaulted);
1083   }
1084   {
1085     SmallVector<Emplaceable, 3> V;
1086     Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1));
1087     EXPECT_TRUE(&back == &V.back());
1088     EXPECT_TRUE(V.size() == 1);
1089     EXPECT_TRUE(back.State == ES_Emplaced);
1090     EXPECT_TRUE(back.A0.State == EAS_RValue);
1091     EXPECT_TRUE(back.A1.State == EAS_RValue);
1092     EXPECT_TRUE(back.A2.State == EAS_Defaulted);
1093     EXPECT_TRUE(back.A3.State == EAS_Defaulted);
1094   }
1095   {
1096     SmallVector<Emplaceable, 3> V;
1097     Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3);
1098     EXPECT_TRUE(&back == &V.back());
1099     EXPECT_TRUE(V.size() == 1);
1100     EXPECT_TRUE(back.State == ES_Emplaced);
1101     EXPECT_TRUE(back.A0.State == EAS_RValue);
1102     EXPECT_TRUE(back.A1.State == EAS_LValue);
1103     EXPECT_TRUE(back.A2.State == EAS_RValue);
1104     EXPECT_TRUE(back.A3.State == EAS_LValue);
1105   }
1106   {
1107     SmallVector<int, 1> V;
1108     V.emplace_back();
1109     V.emplace_back(42);
1110     EXPECT_EQ(2U, V.size());
1111     EXPECT_EQ(0, V[0]);
1112     EXPECT_EQ(42, V[1]);
1113   }
1114 }
1115
1116 TEST(SmallVectorTest, DefaultInlinedElements) {
1117   SmallVector<int> V;
1118   EXPECT_TRUE(V.empty());
1119   V.push_back(7);
1120   EXPECT_EQ(V[0], 7);
1121
1122   // Check that at least a couple layers of nested SmallVector<T>'s are allowed
1123   // by the default inline elements policy. This pattern happens in practice
1124   // with some frequency, and it seems fairly harmless even though each layer of
1125   // SmallVector's will grow the total sizeof by a vector header beyond the
1126   // "preferred" maximum sizeof.
1127   SmallVector<SmallVector<SmallVector<int>>> NestedV;
1128   NestedV.emplace_back().emplace_back().emplace_back(42);
1129   EXPECT_EQ(NestedV[0][0][0], 42);
1130 }
1131
1132 TEST(SmallVectorTest, InitializerList) {
1133   SmallVector<int, 2> V1 = {};
1134   EXPECT_TRUE(V1.empty());
1135   V1 = {0, 0};
1136   EXPECT_TRUE(ArrayRef(V1).equals({0, 0}));
1137   V1 = {-1, -1};
1138   EXPECT_TRUE(ArrayRef(V1).equals({-1, -1}));
1139
1140   SmallVector<int, 2> V2 = {1, 2, 3, 4};
1141   EXPECT_TRUE(ArrayRef(V2).equals({1, 2, 3, 4}));
1142   V2.assign({4});
1143   EXPECT_TRUE(ArrayRef(V2).equals({4}));
1144   V2.append({3, 2});
1145   EXPECT_TRUE(ArrayRef(V2).equals({4, 3, 2}));
1146   V2.insert(V2.begin() + 1, 5);
1147   EXPECT_TRUE(ArrayRef(V2).equals({4, 5, 3, 2}));
1148 }
1149
1150 TEST(SmallVectorTest, ToVector) {
1151   {
1152     std::vector<char> v = {'a', 'b', 'c'};
1153     auto Vector = to_vector<4>(v);
1154     static_assert(NumBuiltinElts(Vector) == 4u);
1155     ASSERT_EQ(3u, Vector.size());
1156     for (size_t I = 0; I < v.size(); ++I)
1157       EXPECT_EQ(v[I], Vector[I]);
1158   }
1159   {
1160     std::vector<char> v = {'a', 'b', 'c'};
1161     auto Vector = to_vector(v);
1162     static_assert(NumBuiltinElts(Vector) != 4u);
1163     ASSERT_EQ(3u, Vector.size());
1164     for (size_t I = 0; I < v.size(); ++I)
1165       EXPECT_EQ(v[I], Vector[I]);
1166   }
1167 }
1168
1169 struct To {
1170   int Content;
1171   friend bool operator==(const To &LHS, const To &RHS) {
1172     return LHS.Content == RHS.Content;
1173   }
1174 };
1175
1176 class From {
1177 public:
1178   From() = default;
1179   From(To M) { T = M; }
1180   operator To() const { return T; }
1181
1182 private:
1183   To T;
1184 };
1185
1186 TEST(SmallVectorTest, ConstructFromArrayRefOfConvertibleType) {
1187   To to1{1}, to2{2}, to3{3};
1188   std::vector<From> StdVector = {From(to1), From(to2), From(to3)};
1189   ArrayRef<From> Array = StdVector;
1190   {
1191     llvm::SmallVector<To> Vector(Array);
1192
1193     ASSERT_EQ(Array.size(), Vector.size());
1194     for (size_t I = 0; I < Array.size(); ++I)
1195       EXPECT_EQ(Array[I], Vector[I]);
1196   }
1197   {
1198     llvm::SmallVector<To, 4> Vector(Array);
1199
1200     ASSERT_EQ(Array.size(), Vector.size());
1201     ASSERT_EQ(4u, NumBuiltinElts(Vector));
1202     for (size_t I = 0; I < Array.size(); ++I)
1203       EXPECT_EQ(Array[I], Vector[I]);
1204   }
1205 }
1206
1207 TEST(SmallVectorTest, ToVectorOf) {
1208   To to1{1}, to2{2}, to3{3};
1209   std::vector<From> StdVector = {From(to1), From(to2), From(to3)};
1210   {
1211     llvm::SmallVector<To> Vector = llvm::to_vector_of<To>(StdVector);
1212
1213     ASSERT_EQ(StdVector.size(), Vector.size());
1214     for (size_t I = 0; I < StdVector.size(); ++I)
1215       EXPECT_EQ(StdVector[I], Vector[I]);
1216   }
1217   {
1218     auto Vector = llvm::to_vector_of<To, 4>(StdVector);
1219
1220     ASSERT_EQ(StdVector.size(), Vector.size());
1221     static_assert(NumBuiltinElts(Vector) == 4u);
1222     for (size_t I = 0; I < StdVector.size(); ++I)
1223       EXPECT_EQ(StdVector[I], Vector[I]);
1224   }
1225 }
1226
1227 template <class VectorT>
1228 class SmallVectorReferenceInvalidationTest : public SmallVectorTestBase {
1229 protected:
1230   const char *AssertionMessage =
1231       "Attempting to reference an element of the vector in an operation \" "
1232       "\"that invalidates it";
1233
1234   VectorT V;
1235
1236   template <class T> static bool isValueType() {
1237     return std::is_same_v<T, typename VectorT::value_type>;
1238   }
1239
1240   void SetUp() override {
1241     SmallVectorTestBase::SetUp();
1242
1243     // Fill up the small size so that insertions move the elements.
1244     for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)
1245       V.emplace_back(I + 1);
1246   }
1247 };
1248
1249 // Test one type that's trivially copyable (int) and one that isn't
1250 // (Constructable) since reference invalidation may be fixed differently for
1251 // each.
1252 using SmallVectorReferenceInvalidationTestTypes =
1253     ::testing::Types<SmallVector<int, 3>, SmallVector<Constructable, 3>>;
1254
1255 TYPED_TEST_SUITE(SmallVectorReferenceInvalidationTest,
1256                  SmallVectorReferenceInvalidationTestTypes, );
1257
1258 TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBack) {
1259   // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
1260   auto &V = this->V;
1261   int N = NumBuiltinElts(V);
1262
1263   // Push back a reference to last element when growing from small storage.
1264   V.push_back(V.back());
1265   EXPECT_EQ(N, V.back());
1266
1267   // Check that the old value is still there (not moved away).
1268   EXPECT_EQ(N, V[V.size() - 2]);
1269
1270   // Fill storage again.
1271   V.back() = V.size();
1272   while (V.size() < V.capacity())
1273     V.push_back(V.size() + 1);
1274
1275   // Push back a reference to last element when growing from large storage.
1276   V.push_back(V.back());
1277   EXPECT_EQ(int(V.size()) - 1, V.back());
1278 }
1279
1280 TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) {
1281   // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
1282   auto &V = this->V;
1283   int N = NumBuiltinElts(V);
1284
1285   // Push back a reference to last element when growing from small storage.
1286   V.push_back(std::move(V.back()));
1287   EXPECT_EQ(N, V.back());
1288   if (this->template isValueType<Constructable>()) {
1289     // Check that the value was moved (not copied).
1290     EXPECT_EQ(0, V[V.size() - 2]);
1291   }
1292
1293   // Fill storage again.
1294   V.back() = V.size();
1295   while (V.size() < V.capacity())
1296     V.push_back(V.size() + 1);
1297
1298   // Push back a reference to last element when growing from large storage.
1299   V.push_back(std::move(V.back()));
1300
1301   // Check the values.
1302   EXPECT_EQ(int(V.size()) - 1, V.back());
1303   if (this->template isValueType<Constructable>()) {
1304     // Check the value got moved out.
1305     EXPECT_EQ(0, V[V.size() - 2]);
1306   }
1307 }
1308
1309 TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) {
1310   auto &V = this->V;
1311   (void)V;
1312   int N = NumBuiltinElts(V);
1313   V.resize(N + 1, V.back());
1314   EXPECT_EQ(N, V.back());
1315
1316   // Resize to add enough elements that V will grow again. If reference
1317   // invalidation breaks in the future, sanitizers should be able to catch a
1318   // use-after-free here.
1319   V.resize(V.capacity() + 1, V.front());
1320   EXPECT_EQ(1, V.back());
1321 }
1322
1323 TYPED_TEST(SmallVectorReferenceInvalidationTest, Append) {
1324   auto &V = this->V;
1325   (void)V;
1326   V.append(1, V.back());
1327   int N = NumBuiltinElts(V);
1328   EXPECT_EQ(N, V[N - 1]);
1329
1330   // Append enough more elements that V will grow again. This tests growing
1331   // when already in large mode.
1332   //
1333   // If reference invalidation breaks in the future, sanitizers should be able
1334   // to catch a use-after-free here.
1335   V.append(V.capacity() - V.size() + 1, V.front());
1336   EXPECT_EQ(1, V.back());
1337 }
1338
1339 TYPED_TEST(SmallVectorReferenceInvalidationTest, AppendRange) {
1340   auto &V = this->V;
1341   (void)V;
1342 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
1343   EXPECT_DEATH(V.append(V.begin(), V.begin() + 1), this->AssertionMessage);
1344
1345   ASSERT_EQ(3u, NumBuiltinElts(V));
1346   ASSERT_EQ(3u, V.size());
1347   V.pop_back();
1348   ASSERT_EQ(2u, V.size());
1349
1350   // Confirm this checks for growth when there's more than one element
1351   // appended.
1352   EXPECT_DEATH(V.append(V.begin(), V.end()), this->AssertionMessage);
1353 #endif
1354 }
1355
1356 TYPED_TEST(SmallVectorReferenceInvalidationTest, Assign) {
1357   // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
1358   auto &V = this->V;
1359   (void)V;
1360   int N = NumBuiltinElts(V);
1361   ASSERT_EQ(unsigned(N), V.size());
1362   ASSERT_EQ(unsigned(N), V.capacity());
1363
1364   // Check assign that shrinks in small mode.
1365   V.assign(1, V.back());
1366   EXPECT_EQ(1u, V.size());
1367   EXPECT_EQ(N, V[0]);
1368
1369   // Check assign that grows within small mode.
1370   ASSERT_LT(V.size(), V.capacity());
1371   V.assign(V.capacity(), V.back());
1372   for (int I = 0, E = V.size(); I != E; ++I) {
1373     EXPECT_EQ(N, V[I]);
1374
1375     // Reset to [1, 2, ...].
1376     V[I] = I + 1;
1377   }
1378
1379   // Check assign that grows to large mode.
1380   ASSERT_EQ(2, V[1]);
1381   V.assign(V.capacity() + 1, V[1]);
1382   for (int I = 0, E = V.size(); I != E; ++I) {
1383     EXPECT_EQ(2, V[I]);
1384
1385     // Reset to [1, 2, ...].
1386     V[I] = I + 1;
1387   }
1388
1389   // Check assign that shrinks in large mode.
1390   V.assign(1, V[1]);
1391   EXPECT_EQ(2, V[0]);
1392 }
1393
1394 TYPED_TEST(SmallVectorReferenceInvalidationTest, AssignRange) {
1395   auto &V = this->V;
1396 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
1397   EXPECT_DEATH(V.assign(V.begin(), V.end()), this->AssertionMessage);
1398   EXPECT_DEATH(V.assign(V.begin(), V.end() - 1), this->AssertionMessage);
1399 #endif
1400   V.assign(V.begin(), V.begin());
1401   EXPECT_TRUE(V.empty());
1402 }
1403
1404 TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) {
1405   // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
1406   auto &V = this->V;
1407   (void)V;
1408
1409   // Insert a reference to the back (not at end() or else insert delegates to
1410   // push_back()), growing out of small mode. Confirm the value was copied out
1411   // (moving out Constructable sets it to 0).
1412   V.insert(V.begin(), V.back());
1413   EXPECT_EQ(int(V.size() - 1), V.front());
1414   EXPECT_EQ(int(V.size() - 1), V.back());
1415
1416   // Fill up the vector again.
1417   while (V.size() < V.capacity())
1418     V.push_back(V.size() + 1);
1419
1420   // Grow again from large storage to large storage.
1421   V.insert(V.begin(), V.back());
1422   EXPECT_EQ(int(V.size() - 1), V.front());
1423   EXPECT_EQ(int(V.size() - 1), V.back());
1424 }
1425
1426 TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) {
1427   // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
1428   auto &V = this->V;
1429   (void)V;
1430
1431   // Insert a reference to the back (not at end() or else insert delegates to
1432   // push_back()), growing out of small mode. Confirm the value was copied out
1433   // (moving out Constructable sets it to 0).
1434   V.insert(V.begin(), std::move(V.back()));
1435   EXPECT_EQ(int(V.size() - 1), V.front());
1436   if (this->template isValueType<Constructable>()) {
1437     // Check the value got moved out.
1438     EXPECT_EQ(0, V.back());
1439   }
1440
1441   // Fill up the vector again.
1442   while (V.size() < V.capacity())
1443     V.push_back(V.size() + 1);
1444
1445   // Grow again from large storage to large storage.
1446   V.insert(V.begin(), std::move(V.back()));
1447   EXPECT_EQ(int(V.size() - 1), V.front());
1448   if (this->template isValueType<Constructable>()) {
1449     // Check the value got moved out.
1450     EXPECT_EQ(0, V.back());
1451   }
1452 }
1453
1454 TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) {
1455   auto &V = this->V;
1456   (void)V;
1457
1458   // Cover NumToInsert <= this->end() - I.
1459   V.insert(V.begin() + 1, 1, V.back());
1460   int N = NumBuiltinElts(V);
1461   EXPECT_EQ(N, V[1]);
1462
1463   // Cover NumToInsert > this->end() - I, inserting enough elements that V will
1464   // also grow again; V.capacity() will be more elements than necessary but
1465   // it's a simple way to cover both conditions.
1466   //
1467   // If reference invalidation breaks in the future, sanitizers should be able
1468   // to catch a use-after-free here.
1469   V.insert(V.begin(), V.capacity(), V.front());
1470   EXPECT_EQ(1, V.front());
1471 }
1472
1473 TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertRange) {
1474   auto &V = this->V;
1475   (void)V;
1476 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
1477   EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.begin() + 1),
1478                this->AssertionMessage);
1479
1480   ASSERT_EQ(3u, NumBuiltinElts(V));
1481   ASSERT_EQ(3u, V.size());
1482   V.pop_back();
1483   ASSERT_EQ(2u, V.size());
1484
1485   // Confirm this checks for growth when there's more than one element
1486   // inserted.
1487   EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.end()), this->AssertionMessage);
1488 #endif
1489 }
1490
1491 TYPED_TEST(SmallVectorReferenceInvalidationTest, EmplaceBack) {
1492   // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
1493   auto &V = this->V;
1494   int N = NumBuiltinElts(V);
1495
1496   // Push back a reference to last element when growing from small storage.
1497   V.emplace_back(V.back());
1498   EXPECT_EQ(N, V.back());
1499
1500   // Check that the old value is still there (not moved away).
1501   EXPECT_EQ(N, V[V.size() - 2]);
1502
1503   // Fill storage again.
1504   V.back() = V.size();
1505   while (V.size() < V.capacity())
1506     V.push_back(V.size() + 1);
1507
1508   // Push back a reference to last element when growing from large storage.
1509   V.emplace_back(V.back());
1510   EXPECT_EQ(int(V.size()) - 1, V.back());
1511 }
1512
1513 template <class VectorT>
1514 class SmallVectorInternalReferenceInvalidationTest
1515     : public SmallVectorTestBase {
1516 protected:
1517   const char *AssertionMessage =
1518       "Attempting to reference an element of the vector in an operation \" "
1519       "\"that invalidates it";
1520
1521   VectorT V;
1522
1523   void SetUp() override {
1524     SmallVectorTestBase::SetUp();
1525
1526     // Fill up the small size so that insertions move the elements.
1527     for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)
1528       V.emplace_back(I + 1, I + 1);
1529   }
1530 };
1531
1532 // Test pairs of the same types from SmallVectorReferenceInvalidationTestTypes.
1533 using SmallVectorInternalReferenceInvalidationTestTypes =
1534     ::testing::Types<SmallVector<std::pair<int, int>, 3>,
1535                      SmallVector<std::pair<Constructable, Constructable>, 3>>;
1536
1537 TYPED_TEST_SUITE(SmallVectorInternalReferenceInvalidationTest,
1538                  SmallVectorInternalReferenceInvalidationTestTypes, );
1539
1540 TYPED_TEST(SmallVectorInternalReferenceInvalidationTest, EmplaceBack) {
1541   // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
1542   auto &V = this->V;
1543   int N = NumBuiltinElts(V);
1544
1545   // Push back a reference to last element when growing from small storage.
1546   V.emplace_back(V.back().first, V.back().second);
1547   EXPECT_EQ(N, V.back().first);
1548   EXPECT_EQ(N, V.back().second);
1549
1550   // Check that the old value is still there (not moved away).
1551   EXPECT_EQ(N, V[V.size() - 2].first);
1552   EXPECT_EQ(N, V[V.size() - 2].second);
1553
1554   // Fill storage again.
1555   V.back().first = V.back().second = V.size();
1556   while (V.size() < V.capacity())
1557     V.emplace_back(V.size() + 1, V.size() + 1);
1558
1559   // Push back a reference to last element when growing from large storage.
1560   V.emplace_back(V.back().first, V.back().second);
1561   EXPECT_EQ(int(V.size()) - 1, V.back().first);
1562   EXPECT_EQ(int(V.size()) - 1, V.back().second);
1563 }
1564
1565 } // end namespace