Move the SmallVector unit tests to be type-parameterized so that we can

test more than a single instantiation of SmallVector.

Add testing for 0, 1, 2, and 4 element sized "small" buffers. These
appear to be essentially untested in the unit tests until now.

Fix several tests to be robust in the face of a '0' small buffer. As
a consequence of this size buffer, the growth patterns are actually
observable in the test -- yes this means that many tests never caused
a grow to occur before. For some tests I've merely added a reserve call
to normalize behavior. For others, the growth is actually interesting,
and so I captured the fact that growth would occur and adjusted the
assertions to not assume how rapidly growth occured.

Also update the specialization for a '0' small buffer length to have all
the same interface points as the normal small vector.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161001 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 176 insertions, 149 deletions

diff --git a/unittests/ADT/SmallVectorTest.cpp b/unittests/ADT/SmallVectorTest.cpp
index d35e5bc08a2..7fd71f5eb06 100644
--- a/unittests/ADT/SmallVectorTest.cpp
+++ b/unittests/ADT/SmallVectorTest.cpp
@@ -88,18 +88,17 @@ int Constructable::numDestructorCalls;
 int Constructable::numAssignmentCalls;
 
 // Test fixture class
+template <typename VectorT>
 class SmallVectorTest : public testing::Test {
 protected:
-  typedef SmallVector<Constructable, 4> VectorType;
-
-  VectorType theVector;
-  VectorType otherVector;
+  VectorT theVector;
+  VectorT otherVector;
 
   void SetUp() {
     Constructable::reset();
   }
 
-  void assertEmpty(VectorType & v) {
+  void assertEmpty(VectorT & v) {
     // Size tests
     EXPECT_EQ(0u, v.size());
     EXPECT_TRUE(v.empty());
@@ -109,7 +108,7 @@ protected:
   }
 
   // Assert that theVector contains the specified values, in order.
-  void assertValuesInOrder(VectorType & v, size_t size, ...) {
+  void assertValuesInOrder(VectorT & v, size_t size, ...) {
     EXPECT_EQ(size, v.size());
 
     va_list ap;
@@ -123,300 +122,327 @@ protected:
   }
 
   // Generate a sequence of values to initialize the vector.
-  void makeSequence(VectorType & v, int start, int end) {
+  void makeSequence(VectorT & v, int start, int end) {
     for (int i = start; i <= end; ++i) {
       v.push_back(Constructable(i));
     }
   }
 };
 
+typedef ::testing::Types<SmallVector<Constructable, 0>,
+                         SmallVector<Constructable, 1>,
+                         SmallVector<Constructable, 2>,
+                         SmallVector<Constructable, 4>
+                         > SmallVectorTestTypes;
+TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes);
+
 // New vector test.
-TEST_F(SmallVectorTest, EmptyVectorTest) {
+TYPED_TEST(SmallVectorTest, EmptyVectorTest) {
   SCOPED_TRACE("EmptyVectorTest");
-  assertEmpty(theVector);
-  EXPECT_TRUE(theVector.rbegin() == theVector.rend());
+  this->assertEmpty(this->theVector);
+  EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
   EXPECT_EQ(0, Constructable::getNumDestructorCalls());
 }
 
 // Simple insertions and deletions.
-TEST_F(SmallVectorTest, PushPopTest) {
+TYPED_TEST(SmallVectorTest, PushPopTest) {
   SCOPED_TRACE("PushPopTest");
 
+  // Track whether the vector will potentially have to grow.
+  bool RequiresGrowth = this->theVector.capacity() < 3;
+
   // Push an element
-  theVector.push_back(Constructable(1));
+  this->theVector.push_back(Constructable(1));
 
   // Size tests
-  assertValuesInOrder(theVector, 1u, 1);
-  EXPECT_FALSE(theVector.begin() == theVector.end());
-  EXPECT_FALSE(theVector.empty());
+  this->assertValuesInOrder(this->theVector, 1u, 1);
+  EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
+  EXPECT_FALSE(this->theVector.empty());
 
   // Push another element
-  theVector.push_back(Constructable(2));
-  assertValuesInOrder(theVector, 2u, 1, 2);
+  this->theVector.push_back(Constructable(2));
+  this->assertValuesInOrder(this->theVector, 2u, 1, 2);
 
   // Insert at beginning
-  theVector.insert(theVector.begin(), theVector[1]);
-  assertValuesInOrder(theVector, 3u, 2, 1, 2);
+  this->theVector.insert(this->theVector.begin(), this->theVector[1]);
+  this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
 
   // Pop one element
-  theVector.pop_back();
-  assertValuesInOrder(theVector, 2u, 2, 1);
+  this->theVector.pop_back();
+  this->assertValuesInOrder(this->theVector, 2u, 2, 1);
 
   // Pop remaining elements
-  theVector.pop_back();
-  theVector.pop_back();
-  assertEmpty(theVector);
+  this->theVector.pop_back();
+  this->theVector.pop_back();
+  this->assertEmpty(this->theVector);
 
   // Check number of constructor calls. Should be 2 for each list element,
   // one for the argument to push_back, one for the argument to insert,
   // and one for the list element itself.
-  EXPECT_EQ(5, Constructable::getNumConstructorCalls());
-  EXPECT_EQ(5, Constructable::getNumDestructorCalls());
+  if (!RequiresGrowth) {
+    EXPECT_EQ(5, Constructable::getNumConstructorCalls());
+    EXPECT_EQ(5, Constructable::getNumDestructorCalls());
+  } else {
+    // If we had to grow the vector, these only have a lower bound, but should
+    // always be equal.
+    EXPECT_LE(5, Constructable::getNumConstructorCalls());
+    EXPECT_EQ(Constructable::getNumConstructorCalls(),
+              Constructable::getNumDestructorCalls());
+  }
 }
 
 // Clear test.
-TEST_F(SmallVectorTest, ClearTest) {
+TYPED_TEST(SmallVectorTest, ClearTest) {
   SCOPED_TRACE("ClearTest");
 
-  makeSequence(theVector, 1, 2);
-  theVector.clear();
+  this->theVector.reserve(2);
+  this->makeSequence(this->theVector, 1, 2);
+  this->theVector.clear();
 
-  assertEmpty(theVector);
+  this->assertEmpty(this->theVector);
   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
   EXPECT_EQ(4, Constructable::getNumDestructorCalls());
 }
 
 // Resize smaller test.
-TEST_F(SmallVectorTest, ResizeShrinkTest) {
+TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {
   SCOPED_TRACE("ResizeShrinkTest");
 
-  makeSequence(theVector, 1, 3);
-  theVector.resize(1);
+  this->theVector.reserve(3);
+  this->makeSequence(this->theVector, 1, 3);
+  this->theVector.resize(1);
 
-  assertValuesInOrder(theVector, 1u, 1);
+  this->assertValuesInOrder(this->theVector, 1u, 1);
   EXPECT_EQ(6, Constructable::getNumConstructorCalls());
   EXPECT_EQ(5, Constructable::getNumDestructorCalls());
 }
 
 // Resize bigger test.
-TEST_F(SmallVectorTest, ResizeGrowTest) {
+TYPED_TEST(SmallVectorTest, ResizeGrowTest) {
   SCOPED_TRACE("ResizeGrowTest");
 
-  theVector.resize(2);
+  this->theVector.resize(2);
 
   // The extra constructor/destructor calls come from the temporary object used
   // to initialize the contents of the resized array (via copy construction).
   EXPECT_EQ(3, Constructable::getNumConstructorCalls());
   EXPECT_EQ(1, Constructable::getNumDestructorCalls());
-  EXPECT_EQ(2u, theVector.size());
+  EXPECT_EQ(2u, this->theVector.size());
 }
 
 // Resize with fill value.
-TEST_F(SmallVectorTest, ResizeFillTest) {
+TYPED_TEST(SmallVectorTest, ResizeFillTest) {
   SCOPED_TRACE("ResizeFillTest");
 
-  theVector.resize(3, Constructable(77));
-  assertValuesInOrder(theVector, 3u, 77, 77, 77);
+  this->theVector.resize(3, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
 }
 
 // Overflow past fixed size.
-TEST_F(SmallVectorTest, OverflowTest) {
+TYPED_TEST(SmallVectorTest, OverflowTest) {
   SCOPED_TRACE("OverflowTest");
 
   // Push more elements than the fixed size.
-  makeSequence(theVector, 1, 10);
+  this->makeSequence(this->theVector, 1, 10);
 
   // Test size and values.
-  EXPECT_EQ(10u, theVector.size());
+  EXPECT_EQ(10u, this->theVector.size());
   for (int i = 0; i < 10; ++i) {
-    EXPECT_EQ(i+1, theVector[i].getValue());
+    EXPECT_EQ(i+1, this->theVector[i].getValue());
   }
 
   // Now resize back to fixed size.
-  theVector.resize(1);
+  this->theVector.resize(1);
 
-  assertValuesInOrder(theVector, 1u, 1);
+  this->assertValuesInOrder(this->theVector, 1u, 1);
 }
 
 // Iteration tests.
-TEST_F(SmallVectorTest, IterationTest) {
-  makeSequence(theVector, 1, 2);
+TYPED_TEST(SmallVectorTest, IterationTest) {
+  this->makeSequence(this->theVector, 1, 2);
 
   // Forward Iteration
-  VectorType::iterator it = theVector.begin();
-  EXPECT_TRUE(*it == theVector.front());
-  EXPECT_TRUE(*it == theVector[0]);
+  typename TypeParam::iterator it = this->theVector.begin();
+  EXPECT_TRUE(*it == this->theVector.front());
+  EXPECT_TRUE(*it == this->theVector[0]);
   EXPECT_EQ(1, it->getValue());
   ++it;
-  EXPECT_TRUE(*it == theVector[1]);
-  EXPECT_TRUE(*it == theVector.back());
+  EXPECT_TRUE(*it == this->theVector[1]);
+  EXPECT_TRUE(*it == this->theVector.back());
   EXPECT_EQ(2, it->getValue());
   ++it;
-  EXPECT_TRUE(it == theVector.end());
+  EXPECT_TRUE(it == this->theVector.end());
   --it;
-  EXPECT_TRUE(*it == theVector[1]);
+  EXPECT_TRUE(*it == this->theVector[1]);
   EXPECT_EQ(2, it->getValue());
   --it;
-  EXPECT_TRUE(*it == theVector[0]);
+  EXPECT_TRUE(*it == this->theVector[0]);
   EXPECT_EQ(1, it->getValue());
 
   // Reverse Iteration
-  VectorType::reverse_iterator rit = theVector.rbegin();
-  EXPECT_TRUE(*rit == theVector[1]);
+  typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
+  EXPECT_TRUE(*rit == this->theVector[1]);
   EXPECT_EQ(2, rit->getValue());
   ++rit;
-  EXPECT_TRUE(*rit == theVector[0]);
+  EXPECT_TRUE(*rit == this->theVector[0]);
   EXPECT_EQ(1, rit->getValue());
   ++rit;
-  EXPECT_TRUE(rit == theVector.rend());
+  EXPECT_TRUE(rit == this->theVector.rend());
   --rit;
-  EXPECT_TRUE(*rit == theVector[0]);
+  EXPECT_TRUE(*rit == this->theVector[0]);
   EXPECT_EQ(1, rit->getValue());
   --rit;
-  EXPECT_TRUE(*rit == theVector[1]);
+  EXPECT_TRUE(*rit == this->theVector[1]);
   EXPECT_EQ(2, rit->getValue());
 }
 
 // Swap test.
-TEST_F(SmallVectorTest, SwapTest) {
+TYPED_TEST(SmallVectorTest, SwapTest) {
   SCOPED_TRACE("SwapTest");
 
-  makeSequence(theVector, 1, 2);
-  std::swap(theVector, otherVector);
+  this->makeSequence(this->theVector, 1, 2);
+  std::swap(this->theVector, this->otherVector);
 
-  assertEmpty(theVector);
-  assertValuesInOrder(otherVector, 2u, 1, 2);
+  this->assertEmpty(this->theVector);
+  this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
 }
 
 // Append test
-TEST_F(SmallVectorTest, AppendTest) {
+TYPED_TEST(SmallVectorTest, AppendTest) {
   SCOPED_TRACE("AppendTest");
 
-  makeSequence(otherVector, 2, 3);
+  this->makeSequence(this->otherVector, 2, 3);
 
-  theVector.push_back(Constructable(1));
-  theVector.append(otherVector.begin(), otherVector.end());
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(this->otherVector.begin(), this->otherVector.end());
 
-  assertValuesInOrder(theVector, 3u, 1, 2, 3);
+  this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
 }
 
 // Append repeated test
-TEST_F(SmallVectorTest, AppendRepeatedTest) {
+TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {
   SCOPED_TRACE("AppendRepeatedTest");
 
-  theVector.push_back(Constructable(1));
-  theVector.append(2, Constructable(77));
-  assertValuesInOrder(theVector, 3u, 1, 77, 77);
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(2, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
 }
 
 // Assign test
-TEST_F(SmallVectorTest, AssignTest) {
+TYPED_TEST(SmallVectorTest, AssignTest) {
   SCOPED_TRACE("AssignTest");
 
-  theVector.push_back(Constructable(1));
-  theVector.assign(2, Constructable(77));
-  assertValuesInOrder(theVector, 2u, 77, 77);
+  this->theVector.push_back(Constructable(1));
+  this->theVector.assign(2, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 2u, 77, 77);
 }
 
 // Erase a single element
-TEST_F(SmallVectorTest, EraseTest) {
+TYPED_TEST(SmallVectorTest, EraseTest) {
   SCOPED_TRACE("EraseTest");
 
-  makeSequence(theVector, 1, 3);
-  theVector.erase(theVector.begin());
-  assertValuesInOrder(theVector, 2u, 2, 3);
+  this->makeSequence(this->theVector, 1, 3);
+  this->theVector.erase(this->theVector.begin());
+  this->assertValuesInOrder(this->theVector, 2u, 2, 3);
 }
 
 // Erase a range of elements
-TEST_F(SmallVectorTest, EraseRangeTest) {
+TYPED_TEST(SmallVectorTest, EraseRangeTest) {
   SCOPED_TRACE("EraseRangeTest");
 
-  makeSequence(theVector, 1, 3);
-  theVector.erase(theVector.begin(), theVector.begin() + 2);
-  assertValuesInOrder(theVector, 1u, 3);
+  this->makeSequence(this->theVector, 1, 3);
+  this->theVector.erase(this->theVector.begin(), this->theVector.begin() + 2);
+  this->assertValuesInOrder(this->theVector, 1u, 3);
 }
 
 // Insert a single element.
-TEST_F(SmallVectorTest, InsertTest) {
+TYPED_TEST(SmallVectorTest, InsertTest) {
   SCOPED_TRACE("InsertTest");
 
-  makeSequence(theVector, 1, 3);
-  VectorType::iterator I =
-    theVector.insert(theVector.begin() + 1, Constructable(77));
-  EXPECT_EQ(theVector.begin() + 1, I);
-  assertValuesInOrder(theVector, 4u, 1, 77, 2, 3);
+  this->makeSequence(this->theVector, 1, 3);
+  typename TypeParam::iterator I =
+    this->theVector.insert(this->theVector.begin() + 1, Constructable(77));
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
 }
 
 // Insert repeated elements.
-TEST_F(SmallVectorTest, InsertRepeatedTest) {
+TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {
   SCOPED_TRACE("InsertRepeatedTest");
 
-  makeSequence(theVector, 10, 15);
-  VectorType::iterator I =
-    theVector.insert(theVector.begin() + 1, 2, Constructable(16));
-  EXPECT_EQ(theVector.begin() + 1, I);
-  assertValuesInOrder(theVector, 8u, 10, 16, 16, 11, 12, 13, 14, 15);
+  this->makeSequence(this->theVector, 10, 15);
+  typename TypeParam::iterator I =
+    this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 8u,
+                      10, 16, 16, 11, 12, 13, 14, 15);
 
   // Insert at end.
-  I = theVector.insert(theVector.end(), 2, Constructable(16));
-  EXPECT_EQ(theVector.begin() + 8, I);
-  assertValuesInOrder(theVector, 10u, 10, 16, 16, 11, 12, 13, 14, 15, 16, 16);
+  I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
+  EXPECT_EQ(this->theVector.begin() + 8, I);
+  this->assertValuesInOrder(this->theVector, 10u,
+                      10, 16, 16, 11, 12, 13, 14, 15, 16, 16);
 
   // Empty insert.
-  EXPECT_EQ(theVector.end(),
-            theVector.insert(theVector.end(), 0, Constructable(42)));
-  EXPECT_EQ(theVector.begin() + 1,
-            theVector.insert(theVector.begin() + 1, 0, Constructable(42)));
+  EXPECT_EQ(this->theVector.end(),
+            this->theVector.insert(this->theVector.end(),
+                                   0, Constructable(42)));
+  EXPECT_EQ(this->theVector.begin() + 1,
+            this->theVector.insert(this->theVector.begin() + 1,
+                                   0, Constructable(42)));
 }
 
 // Insert range.
-TEST_F(SmallVectorTest, InsertRangeTest) {
+TYPED_TEST(SmallVectorTest, InsertRangeTest) {
   SCOPED_TRACE("InsertRangeTest");
 
   Constructable Arr[3] =
     { Constructable(77), Constructable(77), Constructable(77) };
 
-  makeSequence(theVector, 1, 3);
-  VectorType::iterator I =
-    theVector.insert(theVector.begin() + 1, Arr, Arr+3);
-  EXPECT_EQ(theVector.begin() + 1, I);
-  assertValuesInOrder(theVector, 6u, 1, 77, 77, 77, 2, 3);
+  this->makeSequence(this->theVector, 1, 3);
+  typename TypeParam::iterator I =
+    this->theVector.insert(this->theVector.begin() + 1, Arr, Arr+3);
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
 
   // Insert at end.
-  I = theVector.insert(theVector.end(), Arr, Arr+3);
-  EXPECT_EQ(theVector.begin() + 6, I);
-  assertValuesInOrder(theVector, 9u, 1, 77, 77, 77, 2, 3, 77, 77, 77);
+  I = this->theVector.insert(this->theVector.end(), Arr, Arr+3);
+  EXPECT_EQ(this->theVector.begin() + 6, I);
+  this->assertValuesInOrder(this->theVector, 9u,
+                            1, 77, 77, 77, 2, 3, 77, 77, 77);
 
   // Empty insert.
-  EXPECT_EQ(theVector.end(), theVector.insert(theVector.end(),
-                                              theVector.begin(),
-                                              theVector.begin()));
-  EXPECT_EQ(theVector.begin() + 1, theVector.insert(theVector.begin() + 1,
-                                                    theVector.begin(),
-                                                    theVector.begin()));
+  EXPECT_EQ(this->theVector.end(),
+            this->theVector.insert(this->theVector.end(),
+                                   this->theVector.begin(),
+                                   this->theVector.begin()));
+  EXPECT_EQ(this->theVector.begin() + 1,
+            this->theVector.insert(this->theVector.begin() + 1,
+                                   this->theVector.begin(),
+                                   this->theVector.begin()));
 }
 
 // Comparison tests.
-TEST_F(SmallVectorTest, ComparisonTest) {
+TYPED_TEST(SmallVectorTest, ComparisonTest) {
   SCOPED_TRACE("ComparisonTest");
 
-  makeSequence(theVector, 1, 3);
-  makeSequence(otherVector, 1, 3);
+  this->makeSequence(this->theVector, 1, 3);
+  this->makeSequence(this->otherVector, 1, 3);
 
-  EXPECT_TRUE(theVector == otherVector);
-  EXPECT_FALSE(theVector != otherVector);
+  EXPECT_TRUE(this->theVector == this->otherVector);
+  EXPECT_FALSE(this->theVector != this->otherVector);
 
-  otherVector.clear();
-  makeSequence(otherVector, 2, 4);
+  this->otherVector.clear();
+  this->makeSequence(this->otherVector, 2, 4);
 
-  EXPECT_FALSE(theVector == otherVector);
-  EXPECT_TRUE(theVector != otherVector);
+  EXPECT_FALSE(this->theVector == this->otherVector);
+  EXPECT_TRUE(this->theVector != this->otherVector);
 }
 
 // Constant vector tests.
-TEST_F(SmallVectorTest, ConstVectorTest) {
-  VectorType constVector;
+TYPED_TEST(SmallVectorTest, ConstVectorTest) {
+  const TypeParam constVector;
 
   EXPECT_EQ(0u, constVector.size());
   EXPECT_TRUE(constVector.empty());
@@ -424,26 +450,27 @@ TEST_F(SmallVectorTest, ConstVectorTest) {
 }
 
 // Direct array access.
-TEST_F(SmallVectorTest, DirectVectorTest) {
-  EXPECT_EQ(0u, theVector.size());
-  EXPECT_LE(4u, theVector.capacity());
+TYPED_TEST(SmallVectorTest, DirectVectorTest) {
+  EXPECT_EQ(0u, this->theVector.size());
+  this->theVector.reserve(4);
+  EXPECT_LE(4u, this->theVector.capacity());
   EXPECT_EQ(0, Constructable::getNumConstructorCalls());
-  theVector.end()[0] = 1;
-  theVector.end()[1] = 2;
-  theVector.end()[2] = 3;
-  theVector.end()[3] = 4;
-  theVector.set_size(4);
-  EXPECT_EQ(4u, theVector.size());
+  this->theVector.end()[0] = 1;
+  this->theVector.end()[1] = 2;
+  this->theVector.end()[2] = 3;
+  this->theVector.end()[3] = 4;
+  this->theVector.set_size(4);
+  EXPECT_EQ(4u, this->theVector.size());
   EXPECT_EQ(4, Constructable::getNumConstructorCalls());
-  EXPECT_EQ(1, theVector[0].getValue());
-  EXPECT_EQ(2, theVector[1].getValue());
-  EXPECT_EQ(3, theVector[2].getValue());
-  EXPECT_EQ(4, theVector[3].getValue());
+  EXPECT_EQ(1, this->theVector[0].getValue());
+  EXPECT_EQ(2, this->theVector[1].getValue());
+  EXPECT_EQ(3, this->theVector[2].getValue());
+  EXPECT_EQ(4, this->theVector[3].getValue());
 }
 
-TEST_F(SmallVectorTest, IteratorTest) {
+TYPED_TEST(SmallVectorTest, IteratorTest) {
   std::list<int> L;
-  theVector.insert(theVector.end(), L.begin(), L.end());
+  this->theVector.insert(this->theVector.end(), L.begin(), L.end());
 }
 
 struct notassignable {
@@ -451,7 +478,7 @@ struct notassignable {
   notassignable(int &x) : x(x) {}
 };
 
-TEST_F(SmallVectorTest, NoAssignTest) {
+TEST(SmallVectorCustomTest, NoAssignTest) {
   int x = 0;
   SmallVector<notassignable, 2> vec;
   vec.push_back(notassignable(x));