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