From 49142991a685bd427d7e877c29c77371dfb7634c Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Wed, 13 Jan 2021 19:08:42 -0800 Subject: Reapply "ADT: Fix reference invalidation in SmallVector::push_back and single-element insert" This reverts commit 56d1ffb927d03958a7a31442596df749264a7792, reapplying 9abac60309006db00eca0af406c2e16bef26807c, removing insert_one_maybe_copy and using a helper called forward_value_param instead. This avoids use of `std::is_same` (or any SFINAE), so I'm hoping it's more portable and MSVC will be happier. Original commit message follows: For small enough, trivially copyable `T`, take the argument by value in `SmallVector::push_back` and copy it when forwarding to `SmallVector::insert_one_impl`. Otherwise, when growing, update the argument appropriately. Differential Revision: https://reviews.llvm.org/D93779 --- llvm/unittests/ADT/SmallVectorTest.cpp | 107 ++++++++++++++++++++++++++++----- 1 file changed, 91 insertions(+), 16 deletions(-) (limited to 'llvm/unittests/ADT/SmallVectorTest.cpp') diff --git a/llvm/unittests/ADT/SmallVectorTest.cpp b/llvm/unittests/ADT/SmallVectorTest.cpp index d97ab57..c880a6b 100644 --- a/llvm/unittests/ADT/SmallVectorTest.cpp +++ b/llvm/unittests/ADT/SmallVectorTest.cpp @@ -53,6 +53,7 @@ public: Constructable(Constructable && src) : constructed(true) { value = src.value; + src.value = 0; ++numConstructorCalls; ++numMoveConstructorCalls; } @@ -74,6 +75,7 @@ public: Constructable & operator=(Constructable && src) { EXPECT_TRUE(constructed); value = src.value; + src.value = 0; ++numAssignmentCalls; ++numMoveAssignmentCalls; return *this; @@ -1056,11 +1058,16 @@ protected: return N; } + template static bool isValueType() { + return std::is_same::value; + } + void SetUp() override { SmallVectorTestBase::SetUp(); // Fill up the small size so that insertions move the elements. - V.append({0, 0, 0}); + for (int I = 0, E = NumBuiltinElts(V); I != E; ++I) + V.emplace_back(I + 1); } }; @@ -1074,19 +1081,54 @@ TYPED_TEST_CASE(SmallVectorReferenceInvalidationTest, SmallVectorReferenceInvalidationTestTypes); TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBack) { + // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. auto &V = this->V; - (void)V; -#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST - EXPECT_DEATH(V.push_back(V.back()), this->AssertionMessage); -#endif + int N = this->NumBuiltinElts(V); + + // Push back a reference to last element when growing from small storage. + V.push_back(V.back()); + EXPECT_EQ(N, V.back()); + + // Check that the old value is still there (not moved away). + EXPECT_EQ(N, V[V.size() - 2]); + + // Fill storage again. + V.back() = V.size(); + while (V.size() < V.capacity()) + V.push_back(V.size() + 1); + + // Push back a reference to last element when growing from large storage. + V.push_back(V.back()); + EXPECT_EQ(int(V.size()) - 1, V.back()); } TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) { + // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. auto &V = this->V; - (void)V; -#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST - EXPECT_DEATH(V.push_back(std::move(V.back())), this->AssertionMessage); -#endif + int N = this->NumBuiltinElts(V); + + // Push back a reference to last element when growing from small storage. + V.push_back(std::move(V.back())); + EXPECT_EQ(N, V.back()); + if (this->template isValueType()) { + // Check that the value was moved (not copied). + EXPECT_EQ(0, V[V.size() - 2]); + } + + // Fill storage again. + V.back() = V.size(); + while (V.size() < V.capacity()) + V.push_back(V.size() + 1); + + // Push back a reference to last element when growing from large storage. + V.push_back(std::move(V.back())); + + // Check the values. + EXPECT_EQ(int(V.size()) - 1, V.back()); + if (this->template isValueType()) { + // Check the value got moved out. + EXPECT_EQ(0, V[V.size() - 2]); + } } TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) { @@ -1150,20 +1192,53 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, AssignRange) { } TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) { + // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. auto &V = this->V; (void)V; -#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST - EXPECT_DEATH(V.insert(V.begin(), V.back()), this->AssertionMessage); -#endif + + // Insert a reference to the back (not at end() or else insert delegates to + // push_back()), growing out of small mode. Confirm the value was copied out + // (moving out Constructable sets it to 0). + V.insert(V.begin(), V.back()); + EXPECT_EQ(int(V.size() - 1), V.front()); + EXPECT_EQ(int(V.size() - 1), V.back()); + + // Fill up the vector again. + while (V.size() < V.capacity()) + V.push_back(V.size() + 1); + + // Grow again from large storage to large storage. + V.insert(V.begin(), V.back()); + EXPECT_EQ(int(V.size() - 1), V.front()); + EXPECT_EQ(int(V.size() - 1), V.back()); } TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) { + // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. auto &V = this->V; (void)V; -#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST - EXPECT_DEATH(V.insert(V.begin(), std::move(V.back())), - this->AssertionMessage); -#endif + + // Insert a reference to the back (not at end() or else insert delegates to + // push_back()), growing out of small mode. Confirm the value was copied out + // (moving out Constructable sets it to 0). + V.insert(V.begin(), std::move(V.back())); + EXPECT_EQ(int(V.size() - 1), V.front()); + if (this->template isValueType()) { + // Check the value got moved out. + EXPECT_EQ(0, V.back()); + } + + // Fill up the vector again. + while (V.size() < V.capacity()) + V.push_back(V.size() + 1); + + // Grow again from large storage to large storage. + V.insert(V.begin(), std::move(V.back())); + EXPECT_EQ(int(V.size() - 1), V.front()); + if (this->template isValueType()) { + // Check the value got moved out. + EXPECT_EQ(0, V.back()); + } } TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) { -- cgit v1.1