unittests/ADT/SmallVectorTest.cpp

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