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