unittests/ADT/SmallVectorTest.cpp

   1 //===- llvm/unittest/ADT/SmallVectorTest.cpp ------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // SmallVector unit tests.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/SmallVector.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/Support/Compiler.h"
  17 #include "gtest/gtest.h"
  18 #include <list>
  19 #include <stdarg.h>
  20
  21 using namespace llvm;
  22
  23 namespace {
  24
  25 /// A helper class that counts the total number of constructor and
  26 /// destructor calls.
  27 class Constructable {
  28 private:
  29   static int numConstructorCalls;
  30   static int numMoveConstructorCalls;
  31   static int numCopyConstructorCalls;
  32   static int numDestructorCalls;
  33   static int numAssignmentCalls;
  34   static int numMoveAssignmentCalls;
  35   static int numCopyAssignmentCalls;
  36
  37   bool constructed;
  38   int value;
  39
  40 public:
  41   Constructable() : constructed(true), value(0) {
  42     ++numConstructorCalls;
  43   }
  44
  45   Constructable(int val) : constructed(true), value(val) {
  46     ++numConstructorCalls;
  47   }
  48
  49   Constructable(const Constructable & src) : constructed(true) {
  50     value = src.value;
  51     ++numConstructorCalls;
  52     ++numCopyConstructorCalls;
  53   }
  54
  55   Constructable(Constructable && src) : constructed(true) {
  56     value = src.value;
  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     ++numAssignmentCalls;
  79     ++numMoveAssignmentCalls;
  80     return *this;
  81   }
  82
  83   int getValue() const {
  84     return abs(value);
  85   }
  86
  87   static void reset() {
  88     numConstructorCalls = 0;
  89     numMoveConstructorCalls = 0;
  90     numCopyConstructorCalls = 0;
  91     numDestructorCalls = 0;
  92     numAssignmentCalls = 0;
  93     numMoveAssignmentCalls = 0;
  94     numCopyAssignmentCalls = 0;
  95   }
  96
  97   static int getNumConstructorCalls() {
  98     return numConstructorCalls;
  99   }
 100
 101   static int getNumMoveConstructorCalls() {
 102     return numMoveConstructorCalls;
 103   }
 104
 105   static int getNumCopyConstructorCalls() {
 106     return numCopyConstructorCalls;
 107   }
 108
 109   static int getNumDestructorCalls() {
 110     return numDestructorCalls;
 111   }
 112
 113   static int getNumAssignmentCalls() {
 114     return numAssignmentCalls;
 115   }
 116
 117   static int getNumMoveAssignmentCalls() {
 118     return numMoveAssignmentCalls;
 119   }
 120
 121   static int getNumCopyAssignmentCalls() {
 122     return numCopyAssignmentCalls;
 123   }
 124
 125   friend bool operator==(const Constructable & c0, const Constructable & c1) {
 126     return c0.getValue() == c1.getValue();
 127   }
 128
 129   friend bool LLVM_ATTRIBUTE_UNUSED
 130   operator!=(const Constructable & c0, const Constructable & c1) {
 131     return c0.getValue() != c1.getValue();
 132   }
 133 };
 134
 135 int Constructable::numConstructorCalls;
 136 int Constructable::numCopyConstructorCalls;
 137 int Constructable::numMoveConstructorCalls;
 138 int Constructable::numDestructorCalls;
 139 int Constructable::numAssignmentCalls;
 140 int Constructable::numCopyAssignmentCalls;
 141 int Constructable::numMoveAssignmentCalls;
 142
 143 struct NonCopyable {
 144   NonCopyable() {}
 145   NonCopyable(NonCopyable &&) {}
 146   NonCopyable &operator=(NonCopyable &&) { return *this; }
 147 private:
 148   NonCopyable(const NonCopyable &) = delete;
 149   NonCopyable &operator=(const NonCopyable &) = delete;
 150 };
 151
 152 LLVM_ATTRIBUTE_USED void CompileTest() {
 153   SmallVector<NonCopyable, 0> V;
 154   V.resize(42);
 155 }
 156
 157 class SmallVectorTestBase : public testing::Test {
 158 protected:
 159   void SetUp() override { Constructable::reset(); }
 160
 161   template <typename VectorT>
 162   void assertEmpty(VectorT & v) {
 163     // Size tests
 164     EXPECT_EQ(0u, v.size());
 165     EXPECT_TRUE(v.empty());
 166
 167     // Iterator tests
 168     EXPECT_TRUE(v.begin() == v.end());
 169   }
 170
 171   // Assert that v contains the specified values, in order.
 172   template <typename VectorT>
 173   void assertValuesInOrder(VectorT & v, size_t size, ...) {
 174     EXPECT_EQ(size, v.size());
 175
 176     va_list ap;
 177     va_start(ap, size);
 178     for (size_t i = 0; i < size; ++i) {
 179       int value = va_arg(ap, int);
 180       EXPECT_EQ(value, v[i].getValue());
 181     }
 182
 183     va_end(ap);
 184   }
 185
 186   // Generate a sequence of values to initialize the vector.
 187   template <typename VectorT>
 188   void makeSequence(VectorT & v, int start, int end) {
 189     for (int i = start; i <= end; ++i) {
 190       v.push_back(Constructable(i));
 191     }
 192   }
 193 };
 194
 195 // Test fixture class
 196 template <typename VectorT>
 197 class SmallVectorTest : public SmallVectorTestBase {
 198 protected:
 199   VectorT theVector;
 200   VectorT otherVector;
 201 };
 202
 203
 204 typedef ::testing::Types<SmallVector<Constructable, 0>,
 205                          SmallVector<Constructable, 1>,
 206                          SmallVector<Constructable, 2>,
 207                          SmallVector<Constructable, 4>,
 208                          SmallVector<Constructable, 5>
 209                          > SmallVectorTestTypes;
 210 TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes);
 211
 212 // Constructor test.
 213 TYPED_TEST(SmallVectorTest, ConstructorNonIterTest) {
 214   SCOPED_TRACE("ConstructorTest");
 215   this->theVector = SmallVector<Constructable, 2>(2, 2);
 216   this->assertValuesInOrder(this->theVector, 2u, 2, 2);
 217 }
 218
 219 // Constructor test.
 220 TYPED_TEST(SmallVectorTest, ConstructorIterTest) {
 221   SCOPED_TRACE("ConstructorTest");
 222   int arr[] = {1, 2, 3};
 223   this->theVector =
 224       SmallVector<Constructable, 4>(std::begin(arr), std::end(arr));
 225   this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
 226 }
 227
 228 // New vector test.
 229 TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
 230   SCOPED_TRACE("EmptyVectorTest");
 231   this->assertEmpty(this->theVector);
 232   EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
 233   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 234   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 235 }
 236
 237 // Simple insertions and deletions.
 238 TYPED_TEST(SmallVectorTest, PushPopTest) {
 239   SCOPED_TRACE("PushPopTest");
 240
 241   // Track whether the vector will potentially have to grow.
 242   bool RequiresGrowth = this->theVector.capacity() < 3;
 243
 244   // Push an element
 245   this->theVector.push_back(Constructable(1));
 246
 247   // Size tests
 248   this->assertValuesInOrder(this->theVector, 1u, 1);
 249   EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
 250   EXPECT_FALSE(this->theVector.empty());
 251
 252   // Push another element
 253   this->theVector.push_back(Constructable(2));
 254   this->assertValuesInOrder(this->theVector, 2u, 1, 2);
 255
 256   // Insert at beginning
 257   this->theVector.insert(this->theVector.begin(), this->theVector[1]);
 258   this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
 259
 260   // Pop one element
 261   this->theVector.pop_back();
 262   this->assertValuesInOrder(this->theVector, 2u, 2, 1);
 263
 264   // Pop remaining elements
 265   this->theVector.pop_back();
 266   this->theVector.pop_back();
 267   this->assertEmpty(this->theVector);
 268
 269   // Check number of constructor calls. Should be 2 for each list element,
 270   // one for the argument to push_back, one for the argument to insert,
 271   // and one for the list element itself.
 272   if (!RequiresGrowth) {
 273     EXPECT_EQ(5, Constructable::getNumConstructorCalls());
 274     EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 275   } else {
 276     // If we had to grow the vector, these only have a lower bound, but should
 277     // always be equal.
 278     EXPECT_LE(5, Constructable::getNumConstructorCalls());
 279     EXPECT_EQ(Constructable::getNumConstructorCalls(),
 280               Constructable::getNumDestructorCalls());
 281   }
 282 }
 283
 284 // Clear test.
 285 TYPED_TEST(SmallVectorTest, ClearTest) {
 286   SCOPED_TRACE("ClearTest");
 287
 288   this->theVector.reserve(2);
 289   this->makeSequence(this->theVector, 1, 2);
 290   this->theVector.clear();
 291
 292   this->assertEmpty(this->theVector);
 293   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 294   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
 295 }
 296
 297 // Resize smaller test.
 298 TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
 299   SCOPED_TRACE("ResizeShrinkTest");
 300
 301   this->theVector.reserve(3);
 302   this->makeSequence(this->theVector, 1, 3);
 303   this->theVector.resize(1);
 304
 305   this->assertValuesInOrder(this->theVector, 1u, 1);
 306   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 307   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 308 }
 309
 310 // Resize bigger test.
 311 TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
 312   SCOPED_TRACE("ResizeGrowTest");
 313
 314   this->theVector.resize(2);
 315
 316   EXPECT_EQ(2, Constructable::getNumConstructorCalls());
 317   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 318   EXPECT_EQ(2u, this->theVector.size());
 319 }
 320
 321 TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) {
 322   this->theVector.resize(2);
 323
 324   Constructable::reset();
 325
 326   this->theVector.resize(4);
 327
 328   size_t Ctors = Constructable::getNumConstructorCalls();
 329   EXPECT_TRUE(Ctors == 2 || Ctors == 4);
 330   size_t MoveCtors = Constructable::getNumMoveConstructorCalls();
 331   EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2);
 332   size_t Dtors = Constructable::getNumDestructorCalls();
 333   EXPECT_TRUE(Dtors == 0 || Dtors == 2);
 334 }
 335
 336 // Resize with fill value.
 337 TYPED_TEST(SmallVectorTest, ResizeFillTest) {
 338   SCOPED_TRACE("ResizeFillTest");
 339
 340   this->theVector.resize(3, Constructable(77));
 341   this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
 342 }
 343
 344 // Overflow past fixed size.
 345 TYPED_TEST(SmallVectorTest, OverflowTest) {
 346   SCOPED_TRACE("OverflowTest");
 347
 348   // Push more elements than the fixed size.
 349   this->makeSequence(this->theVector, 1, 10);
 350
 351   // Test size and values.
 352   EXPECT_EQ(10u, this->theVector.size());
 353   for (int i = 0; i < 10; ++i) {
 354     EXPECT_EQ(i+1, this->theVector[i].getValue());
 355   }
 356
 357   // Now resize back to fixed size.
 358   this->theVector.resize(1);
 359
 360   this->assertValuesInOrder(this->theVector, 1u, 1);
 361 }
 362
 363 // Iteration tests.
 364 TYPED_TEST(SmallVectorTest, IterationTest) {
 365   this->makeSequence(this->theVector, 1, 2);
 366
 367   // Forward Iteration
 368   typename TypeParam::iterator it = this->theVector.begin();
 369   EXPECT_TRUE(*it == this->theVector.front());
 370   EXPECT_TRUE(*it == this->theVector[0]);
 371   EXPECT_EQ(1, it->getValue());
 372   ++it;
 373   EXPECT_TRUE(*it == this->theVector[1]);
 374   EXPECT_TRUE(*it == this->theVector.back());
 375   EXPECT_EQ(2, it->getValue());
 376   ++it;
 377   EXPECT_TRUE(it == this->theVector.end());
 378   --it;
 379   EXPECT_TRUE(*it == this->theVector[1]);
 380   EXPECT_EQ(2, it->getValue());
 381   --it;
 382   EXPECT_TRUE(*it == this->theVector[0]);
 383   EXPECT_EQ(1, it->getValue());
 384
 385   // Reverse Iteration
 386   typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
 387   EXPECT_TRUE(*rit == this->theVector[1]);
 388   EXPECT_EQ(2, rit->getValue());
 389   ++rit;
 390   EXPECT_TRUE(*rit == this->theVector[0]);
 391   EXPECT_EQ(1, rit->getValue());
 392   ++rit;
 393   EXPECT_TRUE(rit == this->theVector.rend());
 394   --rit;
 395   EXPECT_TRUE(*rit == this->theVector[0]);
 396   EXPECT_EQ(1, rit->getValue());
 397   --rit;
 398   EXPECT_TRUE(*rit == this->theVector[1]);
 399   EXPECT_EQ(2, rit->getValue());
 400 }
 401
 402 // Swap test.
 403 TYPED_TEST(SmallVectorTest, SwapTest) {
 404   SCOPED_TRACE("SwapTest");
 405
 406   this->makeSequence(this->theVector, 1, 2);
 407   std::swap(this->theVector, this->otherVector);
 408
 409   this->assertEmpty(this->theVector);
 410   this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
 411 }
 412
 413 // Append test
 414 TYPED_TEST(SmallVectorTest, AppendTest) {
 415   SCOPED_TRACE("AppendTest");
 416
 417   this->makeSequence(this->otherVector, 2, 3);
 418
 419   this->theVector.push_back(Constructable(1));
 420   this->theVector.append(this->otherVector.begin(), this->otherVector.end());
 421
 422   this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
 423 }
 424
 425 // Append repeated test
 426 TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
 427   SCOPED_TRACE("AppendRepeatedTest");
 428
 429   this->theVector.push_back(Constructable(1));
 430   this->theVector.append(2, Constructable(77));
 431   this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
 432 }
 433
 434 // Append test
 435 TYPED_TEST(SmallVectorTest, AppendNonIterTest) {
 436   SCOPED_TRACE("AppendRepeatedTest");
 437
 438   this->theVector.push_back(Constructable(1));
 439   this->theVector.append(2, 7);
 440   this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
 441 }
 442
 443 struct output_iterator {
 444   typedef std::output_iterator_tag iterator_category;
 445   typedef int value_type;
 446   typedef int difference_type;
 447   typedef value_type *pointer;
 448   typedef value_type &reference;
 449   operator int() { return 2; }
 450   operator Constructable() { return 7; }
 451 };
 452
 453 TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) {
 454   SCOPED_TRACE("AppendRepeatedTest");
 455
 456   this->theVector.push_back(Constructable(1));
 457   this->theVector.append(output_iterator(), output_iterator());
 458   this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
 459 }
 460
 461 // Assign test
 462 TYPED_TEST(SmallVectorTest, AssignTest) {
 463   SCOPED_TRACE("AssignTest");
 464
 465   this->theVector.push_back(Constructable(1));
 466   this->theVector.assign(2, Constructable(77));
 467   this->assertValuesInOrder(this->theVector, 2u, 77, 77);
 468 }
 469
 470 // Assign test
 471 TYPED_TEST(SmallVectorTest, AssignRangeTest) {
 472   SCOPED_TRACE("AssignTest");
 473
 474   this->theVector.push_back(Constructable(1));
 475   int arr[] = {1, 2, 3};
 476   this->theVector.assign(std::begin(arr), std::end(arr));
 477   this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
 478 }
 479
 480 // Assign test
 481 TYPED_TEST(SmallVectorTest, AssignNonIterTest) {
 482   SCOPED_TRACE("AssignTest");
 483
 484   this->theVector.push_back(Constructable(1));
 485   this->theVector.assign(2, 7);
 486   this->assertValuesInOrder(this->theVector, 2u, 7, 7);
 487 }
 488
 489 // Move-assign test
 490 TYPED_TEST(SmallVectorTest, MoveAssignTest) {
 491   SCOPED_TRACE("MoveAssignTest");
 492
 493   // Set up our vector with a single element, but enough capacity for 4.
 494   this->theVector.reserve(4);
 495   this->theVector.push_back(Constructable(1));
 496
 497   // Set up the other vector with 2 elements.
 498   this->otherVector.push_back(Constructable(2));
 499   this->otherVector.push_back(Constructable(3));
 500
 501   // Move-assign from the other vector.
 502   this->theVector = std::move(this->otherVector);
 503
 504   // Make sure we have the right result.
 505   this->assertValuesInOrder(this->theVector, 2u, 2, 3);
 506
 507   // Make sure the # of constructor/destructor calls line up. There
 508   // are two live objects after clearing the other vector.
 509   this->otherVector.clear();
 510   EXPECT_EQ(Constructable::getNumConstructorCalls()-2,
 511             Constructable::getNumDestructorCalls());
 512
 513   // There shouldn't be any live objects any more.
 514   this->theVector.clear();
 515   EXPECT_EQ(Constructable::getNumConstructorCalls(),
 516             Constructable::getNumDestructorCalls());
 517 }
 518
 519 // Erase a single element
 520 TYPED_TEST(SmallVectorTest, EraseTest) {
 521   SCOPED_TRACE("EraseTest");
 522
 523   this->makeSequence(this->theVector, 1, 3);
 524   const auto &theConstVector = this->theVector;
 525   this->theVector.erase(theConstVector.begin());
 526   this->assertValuesInOrder(this->theVector, 2u, 2, 3);
 527 }
 528
 529 // Erase a range of elements
 530 TYPED_TEST(SmallVectorTest, EraseRangeTest) {
 531   SCOPED_TRACE("EraseRangeTest");
 532
 533   this->makeSequence(this->theVector, 1, 3);
 534   const auto &theConstVector = this->theVector;
 535   this->theVector.erase(theConstVector.begin(), theConstVector.begin() + 2);
 536   this->assertValuesInOrder(this->theVector, 1u, 3);
 537 }
 538
 539 // Insert a single element.
 540 TYPED_TEST(SmallVectorTest, InsertTest) {
 541   SCOPED_TRACE("InsertTest");
 542
 543   this->makeSequence(this->theVector, 1, 3);
 544   typename TypeParam::iterator I =
 545     this->theVector.insert(this->theVector.begin() + 1, Constructable(77));
 546   EXPECT_EQ(this->theVector.begin() + 1, I);
 547   this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
 548 }
 549
 550 // Insert a copy of a single element.
 551 TYPED_TEST(SmallVectorTest, InsertCopy) {
 552   SCOPED_TRACE("InsertTest");
 553
 554   this->makeSequence(this->theVector, 1, 3);
 555   Constructable C(77);
 556   typename TypeParam::iterator I =
 557       this->theVector.insert(this->theVector.begin() + 1, C);
 558   EXPECT_EQ(this->theVector.begin() + 1, I);
 559   this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
 560 }
 561
 562 // Insert repeated elements.
 563 TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
 564   SCOPED_TRACE("InsertRepeatedTest");
 565
 566   this->makeSequence(this->theVector, 1, 4);
 567   Constructable::reset();
 568   auto I =
 569       this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
 570   // Move construct the top element into newly allocated space, and optionally
 571   // reallocate the whole buffer, move constructing into it.
 572   // FIXME: This is inefficient, we shouldn't move things into newly allocated
 573   // space, then move them up/around, there should only be 2 or 4 move
 574   // constructions here.
 575   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
 576               Constructable::getNumMoveConstructorCalls() == 6);
 577   // Move assign the next two to shift them up and make a gap.
 578   EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());
 579   // Copy construct the two new elements from the parameter.
 580   EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
 581   // All without any copy construction.
 582   EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
 583   EXPECT_EQ(this->theVector.begin() + 1, I);
 584   this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4);
 585 }
 586
 587 TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) {
 588   SCOPED_TRACE("InsertRepeatedTest");
 589
 590   this->makeSequence(this->theVector, 1, 4);
 591   Constructable::reset();
 592   auto I = this->theVector.insert(this->theVector.begin() + 1, 2, 7);
 593   EXPECT_EQ(this->theVector.begin() + 1, I);
 594   this->assertValuesInOrder(this->theVector, 6u, 1, 7, 7, 2, 3, 4);
 595 }
 596
 597 TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) {
 598   SCOPED_TRACE("InsertRepeatedTest");
 599
 600   this->makeSequence(this->theVector, 1, 4);
 601   Constructable::reset();
 602   auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
 603   // Just copy construct them into newly allocated space
 604   EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
 605   // Move everything across if reallocation is needed.
 606   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
 607               Constructable::getNumMoveConstructorCalls() == 4);
 608   // Without ever moving or copying anything else.
 609   EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
 610   EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
 611
 612   EXPECT_EQ(this->theVector.begin() + 4, I);
 613   this->assertValuesInOrder(this->theVector, 6u, 1, 2, 3, 4, 16, 16);
 614 }
 615
 616 TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) {
 617   SCOPED_TRACE("InsertRepeatedTest");
 618
 619   this->makeSequence(this->theVector, 10, 15);
 620
 621   // Empty insert.
 622   EXPECT_EQ(this->theVector.end(),
 623             this->theVector.insert(this->theVector.end(),
 624                                    0, Constructable(42)));
 625   EXPECT_EQ(this->theVector.begin() + 1,
 626             this->theVector.insert(this->theVector.begin() + 1,
 627                                    0, Constructable(42)));
 628 }
 629
 630 // Insert range.
 631 TYPED_TEST(SmallVectorTest, InsertRangeTest) {
 632   SCOPED_TRACE("InsertRangeTest");
 633
 634   Constructable Arr[3] =
 635     { Constructable(77), Constructable(77), Constructable(77) };
 636
 637   this->makeSequence(this->theVector, 1, 3);
 638   Constructable::reset();
 639   auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3);
 640   // Move construct the top 3 elements into newly allocated space.
 641   // Possibly move the whole sequence into new space first.
 642   // FIXME: This is inefficient, we shouldn't move things into newly allocated
 643   // space, then move them up/around, there should only be 2 or 3 move
 644   // constructions here.
 645   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
 646               Constructable::getNumMoveConstructorCalls() == 5);
 647   // Copy assign the lower 2 new elements into existing space.
 648   EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
 649   // Copy construct the third element into newly allocated space.
 650   EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());
 651   EXPECT_EQ(this->theVector.begin() + 1, I);
 652   this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
 653 }
 654
 655
 656 TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) {
 657   SCOPED_TRACE("InsertRangeTest");
 658
 659   Constructable Arr[3] =
 660     { Constructable(77), Constructable(77), Constructable(77) };
 661
 662   this->makeSequence(this->theVector, 1, 3);
 663
 664   // Insert at end.
 665   Constructable::reset();
 666   auto I = this->theVector.insert(this->theVector.end(), Arr, Arr+3);
 667   // Copy construct the 3 elements into new space at the top.
 668   EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());
 669   // Don't copy/move anything else.
 670   EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
 671   // Reallocation might occur, causing all elements to be moved into the new
 672   // buffer.
 673   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
 674               Constructable::getNumMoveConstructorCalls() == 3);
 675   EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
 676   EXPECT_EQ(this->theVector.begin() + 3, I);
 677   this->assertValuesInOrder(this->theVector, 6u,
 678                             1, 2, 3, 77, 77, 77);
 679 }
 680
 681 TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) {
 682   SCOPED_TRACE("InsertRangeTest");
 683
 684   this->makeSequence(this->theVector, 1, 3);
 685
 686   // Empty insert.
 687   EXPECT_EQ(this->theVector.end(),
 688             this->theVector.insert(this->theVector.end(),
 689                                    this->theVector.begin(),
 690                                    this->theVector.begin()));
 691   EXPECT_EQ(this->theVector.begin() + 1,
 692             this->theVector.insert(this->theVector.begin() + 1,
 693                                    this->theVector.begin(),
 694                                    this->theVector.begin()));
 695 }
 696
 697 // Comparison tests.
 698 TYPED_TEST(SmallVectorTest, ComparisonTest) {
 699   SCOPED_TRACE("ComparisonTest");
 700
 701   this->makeSequence(this->theVector, 1, 3);
 702   this->makeSequence(this->otherVector, 1, 3);
 703
 704   EXPECT_TRUE(this->theVector == this->otherVector);
 705   EXPECT_FALSE(this->theVector != this->otherVector);
 706
 707   this->otherVector.clear();
 708   this->makeSequence(this->otherVector, 2, 4);
 709
 710   EXPECT_FALSE(this->theVector == this->otherVector);
 711   EXPECT_TRUE(this->theVector != this->otherVector);
 712 }
 713
 714 // Constant vector tests.
 715 TYPED_TEST(SmallVectorTest, ConstVectorTest) {
 716   const TypeParam constVector;
 717
 718   EXPECT_EQ(0u, constVector.size());
 719   EXPECT_TRUE(constVector.empty());
 720   EXPECT_TRUE(constVector.begin() == constVector.end());
 721 }
 722
 723 // Direct array access.
 724 TYPED_TEST(SmallVectorTest, DirectVectorTest) {
 725   EXPECT_EQ(0u, this->theVector.size());
 726   this->theVector.reserve(4);
 727   EXPECT_LE(4u, this->theVector.capacity());
 728   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 729   this->theVector.push_back(1);
 730   this->theVector.push_back(2);
 731   this->theVector.push_back(3);
 732   this->theVector.push_back(4);
 733   EXPECT_EQ(4u, this->theVector.size());
 734   EXPECT_EQ(8, Constructable::getNumConstructorCalls());
 735   EXPECT_EQ(1, this->theVector[0].getValue());
 736   EXPECT_EQ(2, this->theVector[1].getValue());
 737   EXPECT_EQ(3, this->theVector[2].getValue());
 738   EXPECT_EQ(4, this->theVector[3].getValue());
 739 }
 740
 741 TYPED_TEST(SmallVectorTest, IteratorTest) {
 742   std::list<int> L;
 743   this->theVector.insert(this->theVector.end(), L.begin(), L.end());
 744 }
 745
 746 template <typename InvalidType> class DualSmallVectorsTest;
 747
 748 template <typename VectorT1, typename VectorT2>
 749 class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase {
 750 protected:
 751   VectorT1 theVector;
 752   VectorT2 otherVector;
 753
 754   template <typename T, unsigned N>
 755   static unsigned NumBuiltinElts(const SmallVector<T, N>&) { return N; }
 756 };
 757
 758 typedef ::testing::Types<
 759     // Small mode -> Small mode.
 760     std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>,
 761     // Small mode -> Big mode.
 762     std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>,
 763     // Big mode -> Small mode.
 764     std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 4>>,
 765     // Big mode -> Big mode.
 766     std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 2>>
 767   > DualSmallVectorTestTypes;
 768
 769 TYPED_TEST_CASE(DualSmallVectorsTest, DualSmallVectorTestTypes);
 770
 771 TYPED_TEST(DualSmallVectorsTest, MoveAssignment) {
 772   SCOPED_TRACE("MoveAssignTest-DualVectorTypes");
 773
 774   // Set up our vector with four elements.
 775   for (unsigned I = 0; I < 4; ++I)
 776     this->otherVector.push_back(Constructable(I));
 777
 778   const Constructable *OrigDataPtr = this->otherVector.data();
 779
 780   // Move-assign from the other vector.
 781   this->theVector =
 782     std::move(static_cast<SmallVectorImpl<Constructable>&>(this->otherVector));
 783
 784   // Make sure we have the right result.
 785   this->assertValuesInOrder(this->theVector, 4u, 0, 1, 2, 3);
 786
 787   // Make sure the # of constructor/destructor calls line up. There
 788   // are two live objects after clearing the other vector.
 789   this->otherVector.clear();
 790   EXPECT_EQ(Constructable::getNumConstructorCalls()-4,
 791             Constructable::getNumDestructorCalls());
 792
 793   // If the source vector (otherVector) was in small-mode, assert that we just
 794   // moved the data pointer over.
 795   EXPECT_TRUE(this->NumBuiltinElts(this->otherVector) == 4 ||
 796               this->theVector.data() == OrigDataPtr);
 797
 798   // There shouldn't be any live objects any more.
 799   this->theVector.clear();
 800   EXPECT_EQ(Constructable::getNumConstructorCalls(),
 801             Constructable::getNumDestructorCalls());
 802
 803   // We shouldn't have copied anything in this whole process.
 804   EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0);
 805 }
 806
 807 struct notassignable {
 808   int &x;
 809   notassignable(int &x) : x(x) {}
 810 };
 811
 812 TEST(SmallVectorCustomTest, NoAssignTest) {
 813   int x = 0;
 814   SmallVector<notassignable, 2> vec;
 815   vec.push_back(notassignable(x));
 816   x = 42;
 817   EXPECT_EQ(42, vec.pop_back_val().x);
 818 }
 819
 820 struct MovedFrom {
 821   bool hasValue;
 822   MovedFrom() : hasValue(true) {
 823   }
 824   MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) {
 825     m.hasValue = false;
 826   }
 827   MovedFrom &operator=(MovedFrom&& m) {
 828     hasValue = m.hasValue;
 829     m.hasValue = false;
 830     return *this;
 831   }
 832 };
 833
 834 TEST(SmallVectorTest, MidInsert) {
 835   SmallVector<MovedFrom, 3> v;
 836   v.push_back(MovedFrom());
 837   v.insert(v.begin(), MovedFrom());
 838   for (MovedFrom &m : v)
 839     EXPECT_TRUE(m.hasValue);
 840 }
 841
 842 enum EmplaceableArgState {
 843   EAS_Defaulted,
 844   EAS_Arg,
 845   EAS_LValue,
 846   EAS_RValue,
 847   EAS_Failure
 848 };
 849 template <int I> struct EmplaceableArg {
 850   EmplaceableArgState State;
 851   EmplaceableArg() : State(EAS_Defaulted) {}
 852   EmplaceableArg(EmplaceableArg &&X)
 853       : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {}
 854   EmplaceableArg(EmplaceableArg &X)
 855       : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {}
 856
 857   explicit EmplaceableArg(bool) : State(EAS_Arg) {}
 858
 859 private:
 860   EmplaceableArg &operator=(EmplaceableArg &&) = delete;
 861   EmplaceableArg &operator=(const EmplaceableArg &) = delete;
 862 };
 863
 864 enum EmplaceableState { ES_Emplaced, ES_Moved };
 865 struct Emplaceable {
 866   EmplaceableArg<0> A0;
 867   EmplaceableArg<1> A1;
 868   EmplaceableArg<2> A2;
 869   EmplaceableArg<3> A3;
 870   EmplaceableState State;
 871
 872   Emplaceable() : State(ES_Emplaced) {}
 873
 874   template <class A0Ty>
 875   explicit Emplaceable(A0Ty &&A0)
 876       : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {}
 877
 878   template <class A0Ty, class A1Ty>
 879   Emplaceable(A0Ty &&A0, A1Ty &&A1)
 880       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
 881         State(ES_Emplaced) {}
 882
 883   template <class A0Ty, class A1Ty, class A2Ty>
 884   Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2)
 885       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
 886         A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {}
 887
 888   template <class A0Ty, class A1Ty, class A2Ty, class A3Ty>
 889   Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3)
 890       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
 891         A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)),
 892         State(ES_Emplaced) {}
 893
 894   Emplaceable(Emplaceable &&) : State(ES_Moved) {}
 895   Emplaceable &operator=(Emplaceable &&) {
 896     State = ES_Moved;
 897     return *this;
 898   }
 899
 900 private:
 901   Emplaceable(const Emplaceable &) = delete;
 902   Emplaceable &operator=(const Emplaceable &) = delete;
 903 };
 904
 905 TEST(SmallVectorTest, EmplaceBack) {
 906   EmplaceableArg<0> A0(true);
 907   EmplaceableArg<1> A1(true);
 908   EmplaceableArg<2> A2(true);
 909   EmplaceableArg<3> A3(true);
 910   {
 911     SmallVector<Emplaceable, 3> V;
 912     V.emplace_back();
 913     EXPECT_TRUE(V.size() == 1);
 914     EXPECT_TRUE(V.back().State == ES_Emplaced);
 915     EXPECT_TRUE(V.back().A0.State == EAS_Defaulted);
 916     EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
 917     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 918     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 919   }
 920   {
 921     SmallVector<Emplaceable, 3> V;
 922     V.emplace_back(std::move(A0));
 923     EXPECT_TRUE(V.size() == 1);
 924     EXPECT_TRUE(V.back().State == ES_Emplaced);
 925     EXPECT_TRUE(V.back().A0.State == EAS_RValue);
 926     EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
 927     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 928     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 929   }
 930   {
 931     SmallVector<Emplaceable, 3> V;
 932     V.emplace_back(A0);
 933     EXPECT_TRUE(V.size() == 1);
 934     EXPECT_TRUE(V.back().State == ES_Emplaced);
 935     EXPECT_TRUE(V.back().A0.State == EAS_LValue);
 936     EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
 937     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 938     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 939   }
 940   {
 941     SmallVector<Emplaceable, 3> V;
 942     V.emplace_back(A0, A1);
 943     EXPECT_TRUE(V.size() == 1);
 944     EXPECT_TRUE(V.back().State == ES_Emplaced);
 945     EXPECT_TRUE(V.back().A0.State == EAS_LValue);
 946     EXPECT_TRUE(V.back().A1.State == EAS_LValue);
 947     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 948     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 949   }
 950   {
 951     SmallVector<Emplaceable, 3> V;
 952     V.emplace_back(std::move(A0), std::move(A1));
 953     EXPECT_TRUE(V.size() == 1);
 954     EXPECT_TRUE(V.back().State == ES_Emplaced);
 955     EXPECT_TRUE(V.back().A0.State == EAS_RValue);
 956     EXPECT_TRUE(V.back().A1.State == EAS_RValue);
 957     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 958     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 959   }
 960   {
 961     SmallVector<Emplaceable, 3> V;
 962     V.emplace_back(std::move(A0), A1, std::move(A2), A3);
 963     EXPECT_TRUE(V.size() == 1);
 964     EXPECT_TRUE(V.back().State == ES_Emplaced);
 965     EXPECT_TRUE(V.back().A0.State == EAS_RValue);
 966     EXPECT_TRUE(V.back().A1.State == EAS_LValue);
 967     EXPECT_TRUE(V.back().A2.State == EAS_RValue);
 968     EXPECT_TRUE(V.back().A3.State == EAS_LValue);
 969   }
 970   {
 971     SmallVector<int, 1> V;
 972     V.emplace_back();
 973     V.emplace_back(42);
 974     EXPECT_EQ(2U, V.size());
 975     EXPECT_EQ(0, V[0]);
 976     EXPECT_EQ(42, V[1]);
 977   }
 978 }
 979
 980 TEST(SmallVectorTest, InitializerList) {
 981   SmallVector<int, 2> V1 = {};
 982   EXPECT_TRUE(V1.empty());
 983   V1 = {0, 0};
 984   EXPECT_TRUE(makeArrayRef(V1).equals({0, 0}));
 985   V1 = {-1, -1};
 986   EXPECT_TRUE(makeArrayRef(V1).equals({-1, -1}));
 987
 988   SmallVector<int, 2> V2 = {1, 2, 3, 4};
 989   EXPECT_TRUE(makeArrayRef(V2).equals({1, 2, 3, 4}));
 990   V2.assign({4});
 991   EXPECT_TRUE(makeArrayRef(V2).equals({4}));
 992   V2.append({3, 2});
 993   EXPECT_TRUE(makeArrayRef(V2).equals({4, 3, 2}));
 994   V2.insert(V2.begin() + 1, 5);
 995   EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2}));
 996 }
 997
 998 } // end namespace