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