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/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     ++numConstructorCalls;
  57     ++numMoveConstructorCalls;
  58   }
  59
  60   ~Constructable() {
  61     EXPECT_TRUE(constructed);
  62     ++numDestructorCalls;
  63     constructed = false;
  64   }
  65
  66   Constructable & operator=(const Constructable & src) {
  67     EXPECT_TRUE(constructed);
  68     value = src.value;
  69     ++numAssignmentCalls;
  70     ++numCopyAssignmentCalls;
  71     return *this;
  72   }
  73
  74   Constructable & operator=(Constructable && src) {
  75     EXPECT_TRUE(constructed);
  76     value = src.value;
  77     ++numAssignmentCalls;
  78     ++numMoveAssignmentCalls;
  79     return *this;
  80   }
  81
  82   int getValue() const {
  83     return abs(value);
  84   }
  85
  86   static void reset() {
  87     numConstructorCalls = 0;
  88     numMoveConstructorCalls = 0;
  89     numCopyConstructorCalls = 0;
  90     numDestructorCalls = 0;
  91     numAssignmentCalls = 0;
  92     numMoveAssignmentCalls = 0;
  93     numCopyAssignmentCalls = 0;
  94   }
  95
  96   static int getNumConstructorCalls() {
  97     return numConstructorCalls;
  98   }
  99
 100   static int getNumMoveConstructorCalls() {
 101     return numMoveConstructorCalls;
 102   }
 103
 104   static int getNumCopyConstructorCalls() {
 105     return numCopyConstructorCalls;
 106   }
 107
 108   static int getNumDestructorCalls() {
 109     return numDestructorCalls;
 110   }
 111
 112   static int getNumAssignmentCalls() {
 113     return numAssignmentCalls;
 114   }
 115
 116   static int getNumMoveAssignmentCalls() {
 117     return numMoveAssignmentCalls;
 118   }
 119
 120   static int getNumCopyAssignmentCalls() {
 121     return numCopyAssignmentCalls;
 122   }
 123
 124   friend bool operator==(const Constructable & c0, const Constructable & c1) {
 125     return c0.getValue() == c1.getValue();
 126   }
 127
 128   friend bool LLVM_ATTRIBUTE_UNUSED
 129   operator!=(const Constructable & c0, const Constructable & c1) {
 130     return c0.getValue() != c1.getValue();
 131   }
 132 };
 133
 134 int Constructable::numConstructorCalls;
 135 int Constructable::numCopyConstructorCalls;
 136 int Constructable::numMoveConstructorCalls;
 137 int Constructable::numDestructorCalls;
 138 int Constructable::numAssignmentCalls;
 139 int Constructable::numCopyAssignmentCalls;
 140 int Constructable::numMoveAssignmentCalls;
 141
 142 struct NonCopyable {
 143   NonCopyable() {}
 144   NonCopyable(NonCopyable &&) {}
 145   NonCopyable &operator=(NonCopyable &&) { return *this; }
 146 private:
 147   NonCopyable(const NonCopyable &) LLVM_DELETED_FUNCTION;
 148   NonCopyable &operator=(const NonCopyable &) LLVM_DELETED_FUNCTION;
 149 };
 150
 151 LLVM_ATTRIBUTE_USED void CompileTest() {
 152   SmallVector<NonCopyable, 0> V;
 153   V.resize(42);
 154 }
 155
 156 // Test fixture class
 157 template <typename VectorT>
 158 class SmallVectorTest : public testing::Test {
 159 protected:
 160   VectorT theVector;
 161   VectorT otherVector;
 162
 163   void SetUp() {
 164     Constructable::reset();
 165   }
 166
 167   void assertEmpty(VectorT & v) {
 168     // Size tests
 169     EXPECT_EQ(0u, v.size());
 170     EXPECT_TRUE(v.empty());
 171
 172     // Iterator tests
 173     EXPECT_TRUE(v.begin() == v.end());
 174   }
 175
 176   // Assert that theVector contains the specified values, in order.
 177   void assertValuesInOrder(VectorT & v, size_t size, ...) {
 178     EXPECT_EQ(size, v.size());
 179
 180     va_list ap;
 181     va_start(ap, size);
 182     for (size_t i = 0; i < size; ++i) {
 183       int value = va_arg(ap, int);
 184       EXPECT_EQ(value, v[i].getValue());
 185     }
 186
 187     va_end(ap);
 188   }
 189
 190   // Generate a sequence of values to initialize the vector.
 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 typedef ::testing::Types<SmallVector<Constructable, 0>,
 199                          SmallVector<Constructable, 1>,
 200                          SmallVector<Constructable, 2>,
 201                          SmallVector<Constructable, 4>,
 202                          SmallVector<Constructable, 5>
 203                          > SmallVectorTestTypes;
 204 TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes);
 205
 206 // New vector test.
 207 TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
 208   SCOPED_TRACE("EmptyVectorTest");
 209   this->assertEmpty(this->theVector);
 210   EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
 211   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 212   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 213 }
 214
 215 // Simple insertions and deletions.
 216 TYPED_TEST(SmallVectorTest, PushPopTest) {
 217   SCOPED_TRACE("PushPopTest");
 218
 219   // Track whether the vector will potentially have to grow.
 220   bool RequiresGrowth = this->theVector.capacity() < 3;
 221
 222   // Push an element
 223   this->theVector.push_back(Constructable(1));
 224
 225   // Size tests
 226   this->assertValuesInOrder(this->theVector, 1u, 1);
 227   EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
 228   EXPECT_FALSE(this->theVector.empty());
 229
 230   // Push another element
 231   this->theVector.push_back(Constructable(2));
 232   this->assertValuesInOrder(this->theVector, 2u, 1, 2);
 233
 234   // Insert at beginning
 235   this->theVector.insert(this->theVector.begin(), this->theVector[1]);
 236   this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
 237
 238   // Pop one element
 239   this->theVector.pop_back();
 240   this->assertValuesInOrder(this->theVector, 2u, 2, 1);
 241
 242   // Pop remaining elements
 243   this->theVector.pop_back();
 244   this->theVector.pop_back();
 245   this->assertEmpty(this->theVector);
 246
 247   // Check number of constructor calls. Should be 2 for each list element,
 248   // one for the argument to push_back, one for the argument to insert,
 249   // and one for the list element itself.
 250   if (!RequiresGrowth) {
 251     EXPECT_EQ(5, Constructable::getNumConstructorCalls());
 252     EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 253   } else {
 254     // If we had to grow the vector, these only have a lower bound, but should
 255     // always be equal.
 256     EXPECT_LE(5, Constructable::getNumConstructorCalls());
 257     EXPECT_EQ(Constructable::getNumConstructorCalls(),
 258               Constructable::getNumDestructorCalls());
 259   }
 260 }
 261
 262 // Clear test.
 263 TYPED_TEST(SmallVectorTest, ClearTest) {
 264   SCOPED_TRACE("ClearTest");
 265
 266   this->theVector.reserve(2);
 267   this->makeSequence(this->theVector, 1, 2);
 268   this->theVector.clear();
 269
 270   this->assertEmpty(this->theVector);
 271   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
 272   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
 273 }
 274
 275 // Resize smaller test.
 276 TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
 277   SCOPED_TRACE("ResizeShrinkTest");
 278
 279   this->theVector.reserve(3);
 280   this->makeSequence(this->theVector, 1, 3);
 281   this->theVector.resize(1);
 282
 283   this->assertValuesInOrder(this->theVector, 1u, 1);
 284   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
 285   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 286 }
 287
 288 // Resize bigger test.
 289 TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
 290   SCOPED_TRACE("ResizeGrowTest");
 291
 292   this->theVector.resize(2);
 293
 294   EXPECT_EQ(2, Constructable::getNumConstructorCalls());
 295   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 296   EXPECT_EQ(2u, this->theVector.size());
 297 }
 298
 299 TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) {
 300   this->theVector.resize(2);
 301
 302   Constructable::reset();
 303
 304   this->theVector.resize(4);
 305
 306   size_t Ctors = Constructable::getNumConstructorCalls();
 307   EXPECT_TRUE(Ctors == 2 || Ctors == 4);
 308   size_t MoveCtors = Constructable::getNumMoveConstructorCalls();
 309   EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2);
 310   size_t Dtors = Constructable::getNumDestructorCalls();
 311   EXPECT_TRUE(Dtors == 0 || Dtors == 2);
 312 }
 313
 314 // Resize with fill value.
 315 TYPED_TEST(SmallVectorTest, ResizeFillTest) {
 316   SCOPED_TRACE("ResizeFillTest");
 317
 318   this->theVector.resize(3, Constructable(77));
 319   this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
 320 }
 321
 322 // Overflow past fixed size.
 323 TYPED_TEST(SmallVectorTest, OverflowTest) {
 324   SCOPED_TRACE("OverflowTest");
 325
 326   // Push more elements than the fixed size.
 327   this->makeSequence(this->theVector, 1, 10);
 328
 329   // Test size and values.
 330   EXPECT_EQ(10u, this->theVector.size());
 331   for (int i = 0; i < 10; ++i) {
 332     EXPECT_EQ(i+1, this->theVector[i].getValue());
 333   }
 334
 335   // Now resize back to fixed size.
 336   this->theVector.resize(1);
 337
 338   this->assertValuesInOrder(this->theVector, 1u, 1);
 339 }
 340
 341 // Iteration tests.
 342 TYPED_TEST(SmallVectorTest, IterationTest) {
 343   this->makeSequence(this->theVector, 1, 2);
 344
 345   // Forward Iteration
 346   typename TypeParam::iterator it = this->theVector.begin();
 347   EXPECT_TRUE(*it == this->theVector.front());
 348   EXPECT_TRUE(*it == this->theVector[0]);
 349   EXPECT_EQ(1, it->getValue());
 350   ++it;
 351   EXPECT_TRUE(*it == this->theVector[1]);
 352   EXPECT_TRUE(*it == this->theVector.back());
 353   EXPECT_EQ(2, it->getValue());
 354   ++it;
 355   EXPECT_TRUE(it == this->theVector.end());
 356   --it;
 357   EXPECT_TRUE(*it == this->theVector[1]);
 358   EXPECT_EQ(2, it->getValue());
 359   --it;
 360   EXPECT_TRUE(*it == this->theVector[0]);
 361   EXPECT_EQ(1, it->getValue());
 362
 363   // Reverse Iteration
 364   typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
 365   EXPECT_TRUE(*rit == this->theVector[1]);
 366   EXPECT_EQ(2, rit->getValue());
 367   ++rit;
 368   EXPECT_TRUE(*rit == this->theVector[0]);
 369   EXPECT_EQ(1, rit->getValue());
 370   ++rit;
 371   EXPECT_TRUE(rit == this->theVector.rend());
 372   --rit;
 373   EXPECT_TRUE(*rit == this->theVector[0]);
 374   EXPECT_EQ(1, rit->getValue());
 375   --rit;
 376   EXPECT_TRUE(*rit == this->theVector[1]);
 377   EXPECT_EQ(2, rit->getValue());
 378 }
 379
 380 // Swap test.
 381 TYPED_TEST(SmallVectorTest, SwapTest) {
 382   SCOPED_TRACE("SwapTest");
 383
 384   this->makeSequence(this->theVector, 1, 2);
 385   std::swap(this->theVector, this->otherVector);
 386
 387   this->assertEmpty(this->theVector);
 388   this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
 389 }
 390
 391 // Append test
 392 TYPED_TEST(SmallVectorTest, AppendTest) {
 393   SCOPED_TRACE("AppendTest");
 394
 395   this->makeSequence(this->otherVector, 2, 3);
 396
 397   this->theVector.push_back(Constructable(1));
 398   this->theVector.append(this->otherVector.begin(), this->otherVector.end());
 399
 400   this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
 401 }
 402
 403 // Append repeated test
 404 TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
 405   SCOPED_TRACE("AppendRepeatedTest");
 406
 407   this->theVector.push_back(Constructable(1));
 408   this->theVector.append(2, Constructable(77));
 409   this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
 410 }
 411
 412 // Assign test
 413 TYPED_TEST(SmallVectorTest, AssignTest) {
 414   SCOPED_TRACE("AssignTest");
 415
 416   this->theVector.push_back(Constructable(1));
 417   this->theVector.assign(2, Constructable(77));
 418   this->assertValuesInOrder(this->theVector, 2u, 77, 77);
 419 }
 420
 421 // Move-assign test
 422 TYPED_TEST(SmallVectorTest, MoveAssignTest) {
 423   SCOPED_TRACE("MoveAssignTest");
 424
 425   // Set up our vector with a single element, but enough capacity for 4.
 426   this->theVector.reserve(4);
 427   this->theVector.push_back(Constructable(1));
 428
 429   // Set up the other vector with 2 elements.
 430   this->otherVector.push_back(Constructable(2));
 431   this->otherVector.push_back(Constructable(3));
 432
 433   // Move-assign from the other vector.
 434   this->theVector = std::move(this->otherVector);
 435
 436   // Make sure we have the right result.
 437   this->assertValuesInOrder(this->theVector, 2u, 2, 3);
 438
 439   // Make sure the # of constructor/destructor calls line up. There
 440   // are two live objects after clearing the other vector.
 441   this->otherVector.clear();
 442   EXPECT_EQ(Constructable::getNumConstructorCalls()-2,
 443             Constructable::getNumDestructorCalls());
 444
 445   // There shouldn't be any live objects any more.
 446   this->theVector.clear();
 447   EXPECT_EQ(Constructable::getNumConstructorCalls(),
 448             Constructable::getNumDestructorCalls());
 449 }
 450
 451 // Erase a single element
 452 TYPED_TEST(SmallVectorTest, EraseTest) {
 453   SCOPED_TRACE("EraseTest");
 454
 455   this->makeSequence(this->theVector, 1, 3);
 456   this->theVector.erase(this->theVector.begin());
 457   this->assertValuesInOrder(this->theVector, 2u, 2, 3);
 458 }
 459
 460 // Erase a range of elements
 461 TYPED_TEST(SmallVectorTest, EraseRangeTest) {
 462   SCOPED_TRACE("EraseRangeTest");
 463
 464   this->makeSequence(this->theVector, 1, 3);
 465   this->theVector.erase(this->theVector.begin(), this->theVector.begin() + 2);
 466   this->assertValuesInOrder(this->theVector, 1u, 3);
 467 }
 468
 469 // Insert a single element.
 470 TYPED_TEST(SmallVectorTest, InsertTest) {
 471   SCOPED_TRACE("InsertTest");
 472
 473   this->makeSequence(this->theVector, 1, 3);
 474   typename TypeParam::iterator I =
 475     this->theVector.insert(this->theVector.begin() + 1, Constructable(77));
 476   EXPECT_EQ(this->theVector.begin() + 1, I);
 477   this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
 478 }
 479
 480 // Insert a copy of a single element.
 481 TYPED_TEST(SmallVectorTest, InsertCopy) {
 482   SCOPED_TRACE("InsertTest");
 483
 484   this->makeSequence(this->theVector, 1, 3);
 485   Constructable C(77);
 486   typename TypeParam::iterator I =
 487       this->theVector.insert(this->theVector.begin() + 1, C);
 488   EXPECT_EQ(this->theVector.begin() + 1, I);
 489   this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
 490 }
 491
 492 // Insert repeated elements.
 493 TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
 494   SCOPED_TRACE("InsertRepeatedTest");
 495
 496   this->makeSequence(this->theVector, 1, 4);
 497   Constructable::reset();
 498   auto I =
 499       this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
 500   // Move construct the top element into newly allocated space, and optionally
 501   // reallocate the whole buffer, move constructing into it.
 502   // FIXME: This is inefficient, we shouldn't move things into newly allocated
 503   // space, then move them up/around, there should only be 2 or 4 move
 504   // constructions here.
 505   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
 506               Constructable::getNumMoveConstructorCalls() == 6);
 507   // Move assign the next two to shift them up and make a gap.
 508   EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());
 509   // Copy construct the two new elements from the parameter.
 510   EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
 511   // All without any copy construction.
 512   EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
 513   EXPECT_EQ(this->theVector.begin() + 1, I);
 514   this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4);
 515 }
 516
 517
 518 TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) {
 519   SCOPED_TRACE("InsertRepeatedTest");
 520
 521   this->makeSequence(this->theVector, 1, 4);
 522   Constructable::reset();
 523   auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
 524   // Just copy construct them into newly allocated space
 525   EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
 526   // Move everything across if reallocation is needed.
 527   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
 528               Constructable::getNumMoveConstructorCalls() == 4);
 529   // Without ever moving or copying anything else.
 530   EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
 531   EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
 532
 533   EXPECT_EQ(this->theVector.begin() + 4, I);
 534   this->assertValuesInOrder(this->theVector, 6u, 1, 2, 3, 4, 16, 16);
 535 }
 536
 537 TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) {
 538   SCOPED_TRACE("InsertRepeatedTest");
 539
 540   this->makeSequence(this->theVector, 10, 15);
 541
 542   // Empty insert.
 543   EXPECT_EQ(this->theVector.end(),
 544             this->theVector.insert(this->theVector.end(),
 545                                    0, Constructable(42)));
 546   EXPECT_EQ(this->theVector.begin() + 1,
 547             this->theVector.insert(this->theVector.begin() + 1,
 548                                    0, Constructable(42)));
 549 }
 550
 551 // Insert range.
 552 TYPED_TEST(SmallVectorTest, InsertRangeTest) {
 553   SCOPED_TRACE("InsertRangeTest");
 554
 555   Constructable Arr[3] =
 556     { Constructable(77), Constructable(77), Constructable(77) };
 557
 558   this->makeSequence(this->theVector, 1, 3);
 559   Constructable::reset();
 560   auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3);
 561   // Move construct the top 3 elements into newly allocated space.
 562   // Possibly move the whole sequence into new space first.
 563   // FIXME: This is inefficient, we shouldn't move things into newly allocated
 564   // space, then move them up/around, there should only be 2 or 3 move
 565   // constructions here.
 566   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
 567               Constructable::getNumMoveConstructorCalls() == 5);
 568   // Copy assign the lower 2 new elements into existing space.
 569   EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
 570   // Copy construct the third element into newly allocated space.
 571   EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());
 572   EXPECT_EQ(this->theVector.begin() + 1, I);
 573   this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
 574 }
 575
 576
 577 TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) {
 578   SCOPED_TRACE("InsertRangeTest");
 579
 580   Constructable Arr[3] =
 581     { Constructable(77), Constructable(77), Constructable(77) };
 582
 583   this->makeSequence(this->theVector, 1, 3);
 584
 585   // Insert at end.
 586   Constructable::reset();
 587   auto I = this->theVector.insert(this->theVector.end(), Arr, Arr+3);
 588   // Copy construct the 3 elements into new space at the top.
 589   EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());
 590   // Don't copy/move anything else.
 591   EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
 592   // Reallocation might occur, causing all elements to be moved into the new
 593   // buffer.
 594   EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
 595               Constructable::getNumMoveConstructorCalls() == 3);
 596   EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
 597   EXPECT_EQ(this->theVector.begin() + 3, I);
 598   this->assertValuesInOrder(this->theVector, 6u,
 599                             1, 2, 3, 77, 77, 77);
 600 }
 601
 602 TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) {
 603   SCOPED_TRACE("InsertRangeTest");
 604
 605   this->makeSequence(this->theVector, 1, 3);
 606
 607   // Empty insert.
 608   EXPECT_EQ(this->theVector.end(),
 609             this->theVector.insert(this->theVector.end(),
 610                                    this->theVector.begin(),
 611                                    this->theVector.begin()));
 612   EXPECT_EQ(this->theVector.begin() + 1,
 613             this->theVector.insert(this->theVector.begin() + 1,
 614                                    this->theVector.begin(),
 615                                    this->theVector.begin()));
 616 }
 617
 618 // Comparison tests.
 619 TYPED_TEST(SmallVectorTest, ComparisonTest) {
 620   SCOPED_TRACE("ComparisonTest");
 621
 622   this->makeSequence(this->theVector, 1, 3);
 623   this->makeSequence(this->otherVector, 1, 3);
 624
 625   EXPECT_TRUE(this->theVector == this->otherVector);
 626   EXPECT_FALSE(this->theVector != this->otherVector);
 627
 628   this->otherVector.clear();
 629   this->makeSequence(this->otherVector, 2, 4);
 630
 631   EXPECT_FALSE(this->theVector == this->otherVector);
 632   EXPECT_TRUE(this->theVector != this->otherVector);
 633 }
 634
 635 // Constant vector tests.
 636 TYPED_TEST(SmallVectorTest, ConstVectorTest) {
 637   const TypeParam constVector;
 638
 639   EXPECT_EQ(0u, constVector.size());
 640   EXPECT_TRUE(constVector.empty());
 641   EXPECT_TRUE(constVector.begin() == constVector.end());
 642 }
 643
 644 // Direct array access.
 645 TYPED_TEST(SmallVectorTest, DirectVectorTest) {
 646   EXPECT_EQ(0u, this->theVector.size());
 647   this->theVector.reserve(4);
 648   EXPECT_LE(4u, this->theVector.capacity());
 649   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
 650   this->theVector.push_back(1);
 651   this->theVector.push_back(2);
 652   this->theVector.push_back(3);
 653   this->theVector.push_back(4);
 654   EXPECT_EQ(4u, this->theVector.size());
 655   EXPECT_EQ(8, Constructable::getNumConstructorCalls());
 656   EXPECT_EQ(1, this->theVector[0].getValue());
 657   EXPECT_EQ(2, this->theVector[1].getValue());
 658   EXPECT_EQ(3, this->theVector[2].getValue());
 659   EXPECT_EQ(4, this->theVector[3].getValue());
 660 }
 661
 662 TYPED_TEST(SmallVectorTest, IteratorTest) {
 663   std::list<int> L;
 664   this->theVector.insert(this->theVector.end(), L.begin(), L.end());
 665 }
 666
 667 struct notassignable {
 668   int &x;
 669   notassignable(int &x) : x(x) {}
 670 };
 671
 672 TEST(SmallVectorCustomTest, NoAssignTest) {
 673   int x = 0;
 674   SmallVector<notassignable, 2> vec;
 675   vec.push_back(notassignable(x));
 676   x = 42;
 677   EXPECT_EQ(42, vec.pop_back_val().x);
 678 }
 679
 680 struct MovedFrom {
 681   bool hasValue;
 682   MovedFrom() : hasValue(true) {
 683   }
 684   MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) {
 685     m.hasValue = false;
 686   }
 687   MovedFrom &operator=(MovedFrom&& m) {
 688     hasValue = m.hasValue;
 689     m.hasValue = false;
 690     return *this;
 691   }
 692 };
 693
 694 TEST(SmallVectorTest, MidInsert) {
 695   SmallVector<MovedFrom, 3> v;
 696   v.push_back(MovedFrom());
 697   v.insert(v.begin(), MovedFrom());
 698   for (MovedFrom &m : v)
 699     EXPECT_TRUE(m.hasValue);
 700 }
 701
 702 enum EmplaceableArgState {
 703   EAS_Defaulted,
 704   EAS_Arg,
 705   EAS_LValue,
 706   EAS_RValue,
 707   EAS_Failure
 708 };
 709 template <int I> struct EmplaceableArg {
 710   EmplaceableArgState State;
 711   EmplaceableArg() : State(EAS_Defaulted) {}
 712   EmplaceableArg(EmplaceableArg &&X)
 713       : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {}
 714   EmplaceableArg(EmplaceableArg &X)
 715       : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {}
 716
 717   explicit EmplaceableArg(bool) : State(EAS_Arg) {}
 718
 719 private:
 720   EmplaceableArg &operator=(EmplaceableArg &&) LLVM_DELETED_FUNCTION;
 721   EmplaceableArg &operator=(const EmplaceableArg &) LLVM_DELETED_FUNCTION;
 722 };
 723
 724 enum EmplaceableState { ES_Emplaced, ES_Moved };
 725 struct Emplaceable {
 726   EmplaceableArg<0> A0;
 727   EmplaceableArg<1> A1;
 728   EmplaceableArg<2> A2;
 729   EmplaceableArg<3> A3;
 730   EmplaceableState State;
 731
 732   Emplaceable() : State(ES_Emplaced) {}
 733
 734   template <class A0Ty>
 735   explicit Emplaceable(A0Ty &&A0)
 736       : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {}
 737
 738   template <class A0Ty, class A1Ty>
 739   Emplaceable(A0Ty &&A0, A1Ty &&A1)
 740       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
 741         State(ES_Emplaced) {}
 742
 743   template <class A0Ty, class A1Ty, class A2Ty>
 744   Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2)
 745       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
 746         A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {}
 747
 748   template <class A0Ty, class A1Ty, class A2Ty, class A3Ty>
 749   Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3)
 750       : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
 751         A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)),
 752         State(ES_Emplaced) {}
 753
 754   Emplaceable(Emplaceable &&) : State(ES_Moved) {}
 755   Emplaceable &operator=(Emplaceable &&) {
 756     State = ES_Moved;
 757     return *this;
 758   }
 759
 760 private:
 761   Emplaceable(const Emplaceable &) LLVM_DELETED_FUNCTION;
 762   Emplaceable &operator=(const Emplaceable &) LLVM_DELETED_FUNCTION;
 763 };
 764
 765 TEST(SmallVectorTest, EmplaceBack) {
 766   EmplaceableArg<0> A0(true);
 767   EmplaceableArg<1> A1(true);
 768   EmplaceableArg<2> A2(true);
 769   EmplaceableArg<3> A3(true);
 770   {
 771     SmallVector<Emplaceable, 3> V;
 772     V.emplace_back();
 773     EXPECT_TRUE(V.size() == 1);
 774     EXPECT_TRUE(V.back().State == ES_Emplaced);
 775     EXPECT_TRUE(V.back().A0.State == EAS_Defaulted);
 776     EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
 777     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 778     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 779   }
 780   {
 781     SmallVector<Emplaceable, 3> V;
 782     V.emplace_back(std::move(A0));
 783     EXPECT_TRUE(V.size() == 1);
 784     EXPECT_TRUE(V.back().State == ES_Emplaced);
 785     EXPECT_TRUE(V.back().A0.State == EAS_RValue);
 786     EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
 787     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 788     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 789   }
 790   {
 791     SmallVector<Emplaceable, 3> V;
 792     V.emplace_back(A0);
 793     EXPECT_TRUE(V.size() == 1);
 794     EXPECT_TRUE(V.back().State == ES_Emplaced);
 795     EXPECT_TRUE(V.back().A0.State == EAS_LValue);
 796     EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
 797     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 798     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 799   }
 800   {
 801     SmallVector<Emplaceable, 3> V;
 802     V.emplace_back(A0, A1);
 803     EXPECT_TRUE(V.size() == 1);
 804     EXPECT_TRUE(V.back().State == ES_Emplaced);
 805     EXPECT_TRUE(V.back().A0.State == EAS_LValue);
 806     EXPECT_TRUE(V.back().A1.State == EAS_LValue);
 807     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 808     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 809   }
 810   {
 811     SmallVector<Emplaceable, 3> V;
 812     V.emplace_back(std::move(A0), std::move(A1));
 813     EXPECT_TRUE(V.size() == 1);
 814     EXPECT_TRUE(V.back().State == ES_Emplaced);
 815     EXPECT_TRUE(V.back().A0.State == EAS_RValue);
 816     EXPECT_TRUE(V.back().A1.State == EAS_RValue);
 817     EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
 818     EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
 819   }
 820   {
 821     SmallVector<Emplaceable, 3> V;
 822     V.emplace_back(std::move(A0), A1, std::move(A2), A3);
 823     EXPECT_TRUE(V.size() == 1);
 824     EXPECT_TRUE(V.back().State == ES_Emplaced);
 825     EXPECT_TRUE(V.back().A0.State == EAS_RValue);
 826     EXPECT_TRUE(V.back().A1.State == EAS_LValue);
 827     EXPECT_TRUE(V.back().A2.State == EAS_RValue);
 828     EXPECT_TRUE(V.back().A3.State == EAS_LValue);
 829   }
 830 }
 831
 832 } // end namespace