From 9cbd7afb76f20ce874464c238764c54f86b3ce3b Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Wed, 6 Jul 2011 22:36:59 +0000
Subject: [PATCH] Fix a subtle issue in SmallVector.  The following code did
 not work as expected:   vec.insert(vec.begin(), vec[3]); The issue was that
 vec[3] returns a reference into the vector, which is invalidated when
 insert() memmove's the elements down to make space.  The method needs to
 specifically detect and handle this case to correctly match std::vector's
 semantics.

Thanks to Howard Hinnant for clarifying the correct behavior, and explaining how std::vector solves this problem.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134554 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/SmallVector.h    |  9 +++++-
 unittests/ADT/SmallVectorTest.cpp | 48 +++++++++++++++++--------------
 2 files changed, 35 insertions(+), 22 deletions(-)

diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index 8b0a13d6ed7..5f0a55bec46 100644
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -410,7 +410,14 @@ public:
       this->setEnd(this->end()+1);
       // Push everything else over.
       std::copy_backward(I, this->end()-1, this->end());
-      *I = Elt;
+
+      // If we just moved the element we're inserting, be sure to update
+      // the reference.
+      const T *EltPtr = &Elt;
+      if (I <= EltPtr && EltPtr < this->EndX)
+        ++EltPtr;
+
+      *I = *EltPtr;
       return I;
     }
     size_t EltNo = I-this->begin();
diff --git a/unittests/ADT/SmallVectorTest.cpp b/unittests/ADT/SmallVectorTest.cpp
index f4da54dbca1..0d3535d6dbc 100644
--- a/unittests/ADT/SmallVectorTest.cpp
+++ b/unittests/ADT/SmallVectorTest.cpp
@@ -35,26 +35,26 @@ public:
   Constructable() : value(0) {
     ++numConstructorCalls;
   }
-  
+
   Constructable(int val) : value(val) {
     ++numConstructorCalls;
   }
-  
+
   Constructable(const Constructable & src) {
     value = src.value;
     ++numConstructorCalls;
   }
-  
+
   ~Constructable() {
     ++numDestructorCalls;
   }
-  
+
   Constructable & operator=(const Constructable & src) {
     value = src.value;
     ++numAssignmentCalls;
     return *this;
   }
-  
+
   int getValue() const {
     return abs(value);
   }
@@ -64,7 +64,7 @@ public:
     numDestructorCalls = 0;
     numAssignmentCalls = 0;
   }
-  
+
   static int getNumConstructorCalls() {
     return numConstructorCalls;
   }
@@ -91,10 +91,10 @@ int Constructable::numAssignmentCalls;
 class SmallVectorTest : public testing::Test {
 protected:
   typedef SmallVector<Constructable, 4> VectorType;
-  
+
   VectorType theVector;
   VectorType otherVector;
-  
+
   void SetUp() {
     Constructable::reset();
   }
@@ -111,7 +111,7 @@ protected:
   // Assert that theVector contains the specified values, in order.
   void assertValuesInOrder(VectorType & v, size_t size, ...) {
     EXPECT_EQ(size, v.size());
-    
+
     va_list ap;
     va_start(ap, size);
     for (size_t i = 0; i < size; ++i) {
@@ -121,7 +121,7 @@ protected:
 
     va_end(ap);
   }
-  
+
   // Generate a sequence of values to initialize the vector.
   void makeSequence(VectorType & v, int start, int end) {
     for (int i = start; i <= end; ++i) {
@@ -155,18 +155,24 @@ TEST_F(SmallVectorTest, PushPopTest) {
   theVector.push_back(Constructable(2));
   assertValuesInOrder(theVector, 2u, 1, 2);
 
+  // Insert at beginning
+  theVector.insert(theVector.begin(), theVector[1]);
+  assertValuesInOrder(theVector, 3u, 2, 1, 2);
+
   // Pop one element
   theVector.pop_back();
-  assertValuesInOrder(theVector, 1u, 1);
+  assertValuesInOrder(theVector, 2u, 2, 1);
 
-  // Pop another element
+  // Pop remaining elements
+  theVector.pop_back();
   theVector.pop_back();
   assertEmpty(theVector);
-  
+
   // Check number of constructor calls. Should be 2 for each list element,
-  // one for the argument to push_back, and one for the list element itself.
-  EXPECT_EQ(4, Constructable::getNumConstructorCalls());
-  EXPECT_EQ(4, Constructable::getNumDestructorCalls());
+  // 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());
 }
 
 // Clear test.
@@ -198,7 +204,7 @@ TEST_F(SmallVectorTest, ResizeGrowTest) {
   SCOPED_TRACE("ResizeGrowTest");
 
   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());
@@ -226,10 +232,10 @@ TEST_F(SmallVectorTest, OverflowTest) {
   for (int i = 0; i < 10; ++i) {
     EXPECT_EQ(i+1, theVector[i].getValue());
   }
-  
+
   // Now resize back to fixed size.
   theVector.resize(1);
-  
+
   assertValuesInOrder(theVector, 1u, 1);
 }
 
@@ -364,13 +370,13 @@ TEST_F(SmallVectorTest, ComparisonTest) {
 
   makeSequence(theVector, 1, 3);
   makeSequence(otherVector, 1, 3);
-  
+
   EXPECT_TRUE(theVector == otherVector);
   EXPECT_FALSE(theVector != otherVector);
 
   otherVector.clear();
   makeSequence(otherVector, 2, 4);
-  
+
   EXPECT_FALSE(theVector == otherVector);
   EXPECT_TRUE(theVector != otherVector);
 }
-- 
2.34.1