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