1601 lines · 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-exception6//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 "gmock/gmock.h"17#include "gtest/gtest.h"18#include <list>19#include <stdarg.h>20 21using namespace llvm;22 23namespace {24 25/// A helper class that counts the total number of constructor and26/// destructor calls.27class Constructable {28private: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 40public: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 src.value = 0;58 ++numConstructorCalls;59 ++numMoveConstructorCalls;60 }61 62 ~Constructable() {63 EXPECT_TRUE(constructed);64 ++numDestructorCalls;65 constructed = false;66 }67 68 Constructable & operator=(const Constructable & src) {69 EXPECT_TRUE(constructed);70 value = src.value;71 ++numAssignmentCalls;72 ++numCopyAssignmentCalls;73 return *this;74 }75 76 Constructable & operator=(Constructable && src) {77 EXPECT_TRUE(constructed);78 value = src.value;79 src.value = 0;80 ++numAssignmentCalls;81 ++numMoveAssignmentCalls;82 return *this;83 }84 85 int getValue() const {86 return abs(value);87 }88 89 static void reset() {90 numConstructorCalls = 0;91 numMoveConstructorCalls = 0;92 numCopyConstructorCalls = 0;93 numDestructorCalls = 0;94 numAssignmentCalls = 0;95 numMoveAssignmentCalls = 0;96 numCopyAssignmentCalls = 0;97 }98 99 static int getNumConstructorCalls() {100 return numConstructorCalls;101 }102 103 static int getNumMoveConstructorCalls() {104 return numMoveConstructorCalls;105 }106 107 static int getNumCopyConstructorCalls() {108 return numCopyConstructorCalls;109 }110 111 static int getNumDestructorCalls() {112 return numDestructorCalls;113 }114 115 static int getNumAssignmentCalls() {116 return numAssignmentCalls;117 }118 119 static int getNumMoveAssignmentCalls() {120 return numMoveAssignmentCalls;121 }122 123 static int getNumCopyAssignmentCalls() {124 return numCopyAssignmentCalls;125 }126 127 friend bool operator==(const Constructable &c0, const Constructable &c1) {128 return c0.getValue() == c1.getValue();129 }130 131 [[maybe_unused]] friend bool operator!=(const Constructable &c0,132 const Constructable &c1) {133 return c0.getValue() != c1.getValue();134 }135 136 friend bool operator<(const Constructable &c0, const Constructable &c1) {137 return c0.getValue() < c1.getValue();138 }139 [[maybe_unused]] friend bool operator<=(const Constructable &c0,140 const Constructable &c1) {141 return c0.getValue() <= c1.getValue();142 }143 [[maybe_unused]] friend bool operator>(const Constructable &c0,144 const Constructable &c1) {145 return c0.getValue() > c1.getValue();146 }147 [[maybe_unused]] friend bool operator>=(const Constructable &c0,148 const Constructable &c1) {149 return c0.getValue() >= c1.getValue();150 }151};152 153int Constructable::numConstructorCalls;154int Constructable::numCopyConstructorCalls;155int Constructable::numMoveConstructorCalls;156int Constructable::numDestructorCalls;157int Constructable::numAssignmentCalls;158int Constructable::numCopyAssignmentCalls;159int Constructable::numMoveAssignmentCalls;160 161struct NonCopyable {162 NonCopyable() = default;163 NonCopyable(NonCopyable &&) {}164 NonCopyable &operator=(NonCopyable &&) { return *this; }165private:166 NonCopyable(const NonCopyable &) = delete;167 NonCopyable &operator=(const NonCopyable &) = delete;168};169 170LLVM_ATTRIBUTE_USED void CompileTest() {171 SmallVector<NonCopyable, 0> V;172 V.resize(42);173}174 175TEST(SmallVectorTest, ConstructNonCopyableTest) {176 SmallVector<NonCopyable, 0> V(42);177 EXPECT_EQ(V.size(), (size_t)42);178}179 180// Assert that v contains the specified values, in order.181template <typename VectorT>182void assertValuesInOrder(VectorT &v, size_t size, ...) {183 EXPECT_EQ(size, v.size());184 185 va_list ap;186 va_start(ap, size);187 for (size_t i = 0; i < size; ++i) {188 int value = va_arg(ap, int);189 EXPECT_EQ(value, v[i].getValue());190 }191 192 va_end(ap);193}194 195template <typename VectorT> void assertEmpty(VectorT &v) {196 // Size tests197 EXPECT_EQ(0u, v.size());198 EXPECT_TRUE(v.empty());199 200 // Iterator tests201 EXPECT_TRUE(v.begin() == v.end());202}203 204// Generate a sequence of values to initialize the vector.205template <typename VectorT> void makeSequence(VectorT &v, int start, int end) {206 for (int i = start; i <= end; ++i) {207 v.push_back(Constructable(i));208 }209}210 211template <typename T, unsigned N>212constexpr static unsigned NumBuiltinElts(const SmallVector<T, N> &) {213 return N;214}215 216class SmallVectorTestBase : public testing::Test {217protected:218 void SetUp() override { Constructable::reset(); }219};220 221// Test fixture class222template <typename VectorT>223class SmallVectorTest : public SmallVectorTestBase {224protected:225 VectorT theVector;226 VectorT otherVector;227};228 229using SmallVectorTestTypes = ::testing::Types<230 SmallVector<Constructable, 0>, SmallVector<Constructable, 1>,231 SmallVector<Constructable, 2>, SmallVector<Constructable, 4>,232 SmallVector<Constructable, 5>>;233TYPED_TEST_SUITE(SmallVectorTest, SmallVectorTestTypes, );234 235// Constructor test.236TYPED_TEST(SmallVectorTest, ConstructorNonIterTest) {237 SCOPED_TRACE("ConstructorTest");238 auto &V = this->theVector;239 V = SmallVector<Constructable, 2>(2, 2);240 assertValuesInOrder(V, 2u, 2, 2);241}242 243// Constructor test.244TYPED_TEST(SmallVectorTest, ConstructorIterTest) {245 SCOPED_TRACE("ConstructorTest");246 int arr[] = {1, 2, 3};247 auto &V = this->theVector;248 V = SmallVector<Constructable, 4>(std::begin(arr), std::end(arr));249 assertValuesInOrder(V, 3u, 1, 2, 3);250}251 252// Constructor test.253TYPED_TEST(SmallVectorTest, ConstructorFromArrayRefSimpleTest) {254 SCOPED_TRACE("ConstructorFromArrayRefSimpleTest");255 std::array<Constructable, 3> StdArray = {Constructable(1), Constructable(2),256 Constructable(3)};257 ArrayRef<Constructable> Array = StdArray;258 auto &V = this->theVector;259 V = SmallVector<Constructable, 4>(Array);260 assertValuesInOrder(V, 3u, 1, 2, 3);261 ASSERT_EQ(NumBuiltinElts(TypeParam{}), NumBuiltinElts(V));262}263 264// New vector test.265TYPED_TEST(SmallVectorTest, EmptyVectorTest) {266 SCOPED_TRACE("EmptyVectorTest");267 auto &V = this->theVector;268 assertEmpty(V);269 EXPECT_TRUE(V.rbegin() == V.rend());270 EXPECT_EQ(0, Constructable::getNumConstructorCalls());271 EXPECT_EQ(0, Constructable::getNumDestructorCalls());272}273 274// Simple insertions and deletions.275TYPED_TEST(SmallVectorTest, PushPopTest) {276 SCOPED_TRACE("PushPopTest");277 auto &V = this->theVector;278 // Track whether the vector will potentially have to grow.279 bool RequiresGrowth = V.capacity() < 3;280 281 // Push an element282 V.push_back(Constructable(1));283 284 // Size tests285 assertValuesInOrder(V, 1u, 1);286 EXPECT_FALSE(V.begin() == V.end());287 EXPECT_FALSE(V.empty());288 289 // Push another element290 V.push_back(Constructable(2));291 assertValuesInOrder(V, 2u, 1, 2);292 293 // Insert at beginning. Reserve space to avoid reference invalidation from294 // V[1].295 V.reserve(V.size() + 1);296 V.insert(V.begin(), V[1]);297 assertValuesInOrder(V, 3u, 2, 1, 2);298 299 // Pop one element300 V.pop_back();301 assertValuesInOrder(V, 2u, 2, 1);302 303 // Pop remaining elements304 V.pop_back_n(2);305 assertEmpty(V);306 307 // Check number of constructor calls. Should be 2 for each list element,308 // one for the argument to push_back, one for the argument to insert,309 // and one for the list element itself.310 if (!RequiresGrowth) {311 EXPECT_EQ(5, Constructable::getNumConstructorCalls());312 EXPECT_EQ(5, Constructable::getNumDestructorCalls());313 } else {314 // If we had to grow the vector, these only have a lower bound, but should315 // always be equal.316 EXPECT_LE(5, Constructable::getNumConstructorCalls());317 EXPECT_EQ(Constructable::getNumConstructorCalls(),318 Constructable::getNumDestructorCalls());319 }320}321 322// Clear test.323TYPED_TEST(SmallVectorTest, ClearTest) {324 SCOPED_TRACE("ClearTest");325 auto &V = this->theVector;326 V.reserve(2);327 makeSequence(V, 1, 2);328 V.clear();329 330 assertEmpty(V);331 EXPECT_EQ(4, Constructable::getNumConstructorCalls());332 EXPECT_EQ(4, Constructable::getNumDestructorCalls());333}334 335// Resize smaller test.336TYPED_TEST(SmallVectorTest, ResizeShrinkTest) {337 SCOPED_TRACE("ResizeShrinkTest");338 auto &V = this->theVector;339 V.reserve(3);340 makeSequence(V, 1, 3);341 V.resize(1);342 343 assertValuesInOrder(V, 1u, 1);344 EXPECT_EQ(6, Constructable::getNumConstructorCalls());345 EXPECT_EQ(5, Constructable::getNumDestructorCalls());346}347 348// Truncate test.349TYPED_TEST(SmallVectorTest, TruncateTest) {350 SCOPED_TRACE("TruncateTest");351 auto &V = this->theVector;352 V.reserve(3);353 makeSequence(V, 1, 3);354 V.truncate(1);355 356 assertValuesInOrder(V, 1u, 1);357 EXPECT_EQ(6, Constructable::getNumConstructorCalls());358 EXPECT_EQ(5, Constructable::getNumDestructorCalls());359 360#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST361 EXPECT_DEATH(V.truncate(2), "Cannot increase size");362#endif363 V.truncate(1);364 assertValuesInOrder(V, 1u, 1);365 EXPECT_EQ(6, Constructable::getNumConstructorCalls());366 EXPECT_EQ(5, Constructable::getNumDestructorCalls());367 368 V.truncate(0);369 assertEmpty(V);370 EXPECT_EQ(6, Constructable::getNumConstructorCalls());371 EXPECT_EQ(6, Constructable::getNumDestructorCalls());372}373 374// Resize bigger test.375TYPED_TEST(SmallVectorTest, ResizeGrowTest) {376 SCOPED_TRACE("ResizeGrowTest");377 auto &V = this->theVector;378 V.resize(2);379 380 EXPECT_EQ(2, Constructable::getNumConstructorCalls());381 EXPECT_EQ(0, Constructable::getNumDestructorCalls());382 EXPECT_EQ(2u, V.size());383}384 385TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) {386 auto &V = this->theVector;387 V.resize(2);388 389 Constructable::reset();390 391 V.resize(4);392 393 size_t Ctors = Constructable::getNumConstructorCalls();394 EXPECT_TRUE(Ctors == 2 || Ctors == 4);395 size_t MoveCtors = Constructable::getNumMoveConstructorCalls();396 EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2);397 size_t Dtors = Constructable::getNumDestructorCalls();398 EXPECT_TRUE(Dtors == 0 || Dtors == 2);399}400 401// Resize with fill value.402TYPED_TEST(SmallVectorTest, ResizeFillTest) {403 SCOPED_TRACE("ResizeFillTest");404 auto &V = this->theVector;405 V.resize(3, Constructable(77));406 assertValuesInOrder(V, 3u, 77, 77, 77);407}408 409TEST(SmallVectorTest, ResizeForOverwrite) {410 {411 // Heap allocated storage.412 SmallVector<unsigned, 0> V;413 V.push_back(5U);414 V.pop_back();415 V.resize_for_overwrite(V.size() + 1U);416 EXPECT_EQ(5U, V.back());417 V.pop_back();418 V.resize(V.size() + 1);419 EXPECT_EQ(0U, V.back());420 }421 {422 // Inline storage.423 SmallVector<unsigned, 2> V;424 V.push_back(5U);425 V.pop_back();426 V.resize_for_overwrite(V.size() + 1U);427 EXPECT_EQ(5U, V.back());428 V.pop_back();429 V.resize(V.size() + 1);430 EXPECT_EQ(0U, V.back());431 }432}433 434// Overflow past fixed size.435TYPED_TEST(SmallVectorTest, OverflowTest) {436 SCOPED_TRACE("OverflowTest");437 auto &V = this->theVector;438 // Push more elements than the fixed size.439 makeSequence(V, 1, 10);440 441 // Test size and values.442 EXPECT_EQ(10u, V.size());443 for (int i = 0; i < 10; ++i) {444 EXPECT_EQ(i + 1, V[i].getValue());445 }446 447 // Now resize back to fixed size.448 V.resize(1);449 450 assertValuesInOrder(V, 1u, 1);451}452 453// Iteration tests.454TYPED_TEST(SmallVectorTest, IterationTest) {455 auto &V = this->theVector;456 makeSequence(V, 1, 2);457 458 // Forward Iteration459 typename TypeParam::iterator it = V.begin();460 EXPECT_TRUE(*it == V.front());461 EXPECT_TRUE(*it == V[0]);462 EXPECT_EQ(1, it->getValue());463 ++it;464 EXPECT_TRUE(*it == V[1]);465 EXPECT_TRUE(*it == V.back());466 EXPECT_EQ(2, it->getValue());467 ++it;468 EXPECT_TRUE(it == V.end());469 --it;470 EXPECT_TRUE(*it == V[1]);471 EXPECT_EQ(2, it->getValue());472 --it;473 EXPECT_TRUE(*it == V[0]);474 EXPECT_EQ(1, it->getValue());475 476 // Reverse Iteration477 typename TypeParam::reverse_iterator rit = V.rbegin();478 EXPECT_TRUE(*rit == V[1]);479 EXPECT_EQ(2, rit->getValue());480 ++rit;481 EXPECT_TRUE(*rit == V[0]);482 EXPECT_EQ(1, rit->getValue());483 ++rit;484 EXPECT_TRUE(rit == V.rend());485 --rit;486 EXPECT_TRUE(*rit == V[0]);487 EXPECT_EQ(1, rit->getValue());488 --rit;489 EXPECT_TRUE(*rit == V[1]);490 EXPECT_EQ(2, rit->getValue());491}492 493// Swap test.494TYPED_TEST(SmallVectorTest, SwapTest) {495 SCOPED_TRACE("SwapTest");496 auto &V = this->theVector;497 auto &U = this->otherVector;498 makeSequence(V, 1, 2);499 std::swap(V, U);500 501 assertEmpty(V);502 assertValuesInOrder(U, 2u, 1, 2);503}504 505// Append test506TYPED_TEST(SmallVectorTest, AppendTest) {507 SCOPED_TRACE("AppendTest");508 auto &V = this->theVector;509 auto &U = this->otherVector;510 makeSequence(U, 2, 3);511 512 V.push_back(Constructable(1));513 V.append(U.begin(), U.end());514 515 assertValuesInOrder(V, 3u, 1, 2, 3);516}517 518// Append repeated test519TYPED_TEST(SmallVectorTest, AppendRepeatedTest) {520 SCOPED_TRACE("AppendRepeatedTest");521 auto &V = this->theVector;522 V.push_back(Constructable(1));523 V.append(2, Constructable(77));524 assertValuesInOrder(V, 3u, 1, 77, 77);525}526 527// Append test528TYPED_TEST(SmallVectorTest, AppendNonIterTest) {529 SCOPED_TRACE("AppendRepeatedTest");530 auto &V = this->theVector;531 V.push_back(Constructable(1));532 V.append(2, 7);533 assertValuesInOrder(V, 3u, 1, 7, 7);534}535 536struct output_iterator {537 using iterator_category = std::output_iterator_tag;538 using value_type = int;539 using difference_type = int;540 using pointer = value_type *;541 using reference = value_type &;542 operator int() { return 2; }543 operator Constructable() { return 7; }544};545 546TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) {547 SCOPED_TRACE("AppendRepeatedTest");548 auto &V = this->theVector;549 V.push_back(Constructable(1));550 V.append(output_iterator(), output_iterator());551 assertValuesInOrder(V, 3u, 1, 7, 7);552}553 554TYPED_TEST(SmallVectorTest, AppendSmallVector) {555 SCOPED_TRACE("AppendSmallVector");556 auto &V = this->theVector;557 SmallVector<Constructable, 3> otherVector = {7, 7};558 V.push_back(Constructable(1));559 V.append(otherVector);560 assertValuesInOrder(V, 3u, 1, 7, 7);561}562 563// Assign test564TYPED_TEST(SmallVectorTest, AssignTest) {565 SCOPED_TRACE("AssignTest");566 auto &V = this->theVector;567 V.push_back(Constructable(1));568 V.assign(2, Constructable(77));569 assertValuesInOrder(V, 2u, 77, 77);570}571 572// Assign test573TYPED_TEST(SmallVectorTest, AssignRangeTest) {574 SCOPED_TRACE("AssignTest");575 auto &V = this->theVector;576 V.push_back(Constructable(1));577 int arr[] = {1, 2, 3};578 V.assign(std::begin(arr), std::end(arr));579 assertValuesInOrder(V, 3u, 1, 2, 3);580}581 582// Assign test583TYPED_TEST(SmallVectorTest, AssignNonIterTest) {584 SCOPED_TRACE("AssignTest");585 auto &V = this->theVector;586 V.push_back(Constructable(1));587 V.assign(2, 7);588 assertValuesInOrder(V, 2u, 7, 7);589}590 591TYPED_TEST(SmallVectorTest, AssignSmallVector) {592 SCOPED_TRACE("AssignSmallVector");593 auto &V = this->theVector;594 SmallVector<Constructable, 3> otherVector = {7, 7};595 V.push_back(Constructable(1));596 V.assign(otherVector);597 assertValuesInOrder(V, 2u, 7, 7);598}599 600TYPED_TEST(SmallVectorTest, AssignArrayRef) {601 SCOPED_TRACE("AssignArrayRef");602 auto &V = this->theVector;603 Constructable Other[] = {7, 8, 9};604 V.push_back(Constructable(1));605 V.assign(ArrayRef(Other));606 assertValuesInOrder(V, 3u, 7, 8, 9);607}608 609// Move-assign test610TYPED_TEST(SmallVectorTest, MoveAssignTest) {611 SCOPED_TRACE("MoveAssignTest");612 auto &V = this->theVector;613 auto &U = this->otherVector;614 // Set up our vector with a single element, but enough capacity for 4.615 V.reserve(4);616 V.push_back(Constructable(1));617 618 // Set up the other vector with 2 elements.619 U.push_back(Constructable(2));620 U.push_back(Constructable(3));621 622 // Move-assign from the other vector.623 V = std::move(U);624 625 // Make sure we have the right result.626 assertValuesInOrder(V, 2u, 2, 3);627 628 // Make sure the # of constructor/destructor calls line up. There629 // are two live objects after clearing the other vector.630 U.clear();631 EXPECT_EQ(Constructable::getNumConstructorCalls()-2, 632 Constructable::getNumDestructorCalls());633 634 // There shouldn't be any live objects any more.635 V.clear();636 EXPECT_EQ(Constructable::getNumConstructorCalls(), 637 Constructable::getNumDestructorCalls());638}639 640// Erase a single element641TYPED_TEST(SmallVectorTest, EraseTest) {642 SCOPED_TRACE("EraseTest");643 auto &V = this->theVector;644 makeSequence(V, 1, 3);645 const auto &theConstVector = V;646 V.erase(theConstVector.begin());647 assertValuesInOrder(V, 2u, 2, 3);648}649 650// Erase a range of elements651TYPED_TEST(SmallVectorTest, EraseRangeTest) {652 SCOPED_TRACE("EraseRangeTest");653 auto &V = this->theVector;654 makeSequence(V, 1, 3);655 const auto &theConstVector = V;656 V.erase(theConstVector.begin(), theConstVector.begin() + 2);657 assertValuesInOrder(V, 1u, 3);658}659 660// Insert a single element.661TYPED_TEST(SmallVectorTest, InsertTest) {662 SCOPED_TRACE("InsertTest");663 auto &V = this->theVector;664 makeSequence(V, 1, 3);665 typename TypeParam::iterator I = V.insert(V.begin() + 1, Constructable(77));666 EXPECT_EQ(V.begin() + 1, I);667 assertValuesInOrder(V, 4u, 1, 77, 2, 3);668}669 670// Insert a copy of a single element.671TYPED_TEST(SmallVectorTest, InsertCopy) {672 SCOPED_TRACE("InsertTest");673 auto &V = this->theVector;674 makeSequence(V, 1, 3);675 Constructable C(77);676 typename TypeParam::iterator I = V.insert(V.begin() + 1, C);677 EXPECT_EQ(V.begin() + 1, I);678 assertValuesInOrder(V, 4u, 1, 77, 2, 3);679}680 681// Insert repeated elements.682TYPED_TEST(SmallVectorTest, InsertRepeatedTest) {683 SCOPED_TRACE("InsertRepeatedTest");684 auto &V = this->theVector;685 makeSequence(V, 1, 4);686 Constructable::reset();687 auto I = V.insert(V.begin() + 1, 2, Constructable(16));688 // Move construct the top element into newly allocated space, and optionally689 // reallocate the whole buffer, move constructing into it.690 // FIXME: This is inefficient, we shouldn't move things into newly allocated691 // space, then move them up/around, there should only be 2 or 4 move692 // constructions here.693 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||694 Constructable::getNumMoveConstructorCalls() == 6);695 // Move assign the next two to shift them up and make a gap.696 EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());697 // Copy construct the two new elements from the parameter.698 EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());699 // All without any copy construction.700 EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());701 EXPECT_EQ(V.begin() + 1, I);702 assertValuesInOrder(V, 6u, 1, 16, 16, 2, 3, 4);703}704 705TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) {706 SCOPED_TRACE("InsertRepeatedTest");707 auto &V = this->theVector;708 makeSequence(V, 1, 4);709 Constructable::reset();710 auto I = V.insert(V.begin() + 1, 2, 7);711 EXPECT_EQ(V.begin() + 1, I);712 assertValuesInOrder(V, 6u, 1, 7, 7, 2, 3, 4);713}714 715TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) {716 SCOPED_TRACE("InsertRepeatedTest");717 auto &V = this->theVector;718 makeSequence(V, 1, 4);719 Constructable::reset();720 auto I = V.insert(V.end(), 2, Constructable(16));721 // Just copy construct them into newly allocated space722 EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());723 // Move everything across if reallocation is needed.724 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||725 Constructable::getNumMoveConstructorCalls() == 4);726 // Without ever moving or copying anything else.727 EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());728 EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());729 730 EXPECT_EQ(V.begin() + 4, I);731 assertValuesInOrder(V, 6u, 1, 2, 3, 4, 16, 16);732}733 734TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) {735 SCOPED_TRACE("InsertRepeatedTest");736 auto &V = this->theVector;737 makeSequence(V, 10, 15);738 739 // Empty insert.740 EXPECT_EQ(V.end(), V.insert(V.end(), 0, Constructable(42)));741 EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, 0, Constructable(42)));742}743 744// Insert range.745TYPED_TEST(SmallVectorTest, InsertRangeTest) {746 SCOPED_TRACE("InsertRangeTest");747 auto &V = this->theVector;748 Constructable Arr[3] =749 { Constructable(77), Constructable(77), Constructable(77) };750 751 makeSequence(V, 1, 3);752 Constructable::reset();753 auto I = V.insert(V.begin() + 1, Arr, Arr + 3);754 // Move construct the top 3 elements into newly allocated space.755 // Possibly move the whole sequence into new space first.756 // FIXME: This is inefficient, we shouldn't move things into newly allocated757 // space, then move them up/around, there should only be 2 or 3 move758 // constructions here.759 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||760 Constructable::getNumMoveConstructorCalls() == 5);761 // Copy assign the lower 2 new elements into existing space.762 EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());763 // Copy construct the third element into newly allocated space.764 EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());765 EXPECT_EQ(V.begin() + 1, I);766 assertValuesInOrder(V, 6u, 1, 77, 77, 77, 2, 3);767}768 769 770TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) {771 SCOPED_TRACE("InsertRangeTest");772 auto &V = this->theVector;773 Constructable Arr[3] =774 { Constructable(77), Constructable(77), Constructable(77) };775 776 makeSequence(V, 1, 3);777 778 // Insert at end.779 Constructable::reset();780 auto I = V.insert(V.end(), Arr, Arr + 3);781 // Copy construct the 3 elements into new space at the top.782 EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());783 // Don't copy/move anything else.784 EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());785 // Reallocation might occur, causing all elements to be moved into the new786 // buffer.787 EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||788 Constructable::getNumMoveConstructorCalls() == 3);789 EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());790 EXPECT_EQ(V.begin() + 3, I);791 assertValuesInOrder(V, 6u, 1, 2, 3, 77, 77, 77);792}793 794TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) {795 SCOPED_TRACE("InsertRangeTest");796 auto &V = this->theVector;797 makeSequence(V, 1, 3);798 799 // Empty insert.800 EXPECT_EQ(V.end(), V.insert(V.end(), V.begin(), V.begin()));801 EXPECT_EQ(V.begin() + 1, V.insert(V.begin() + 1, V.begin(), V.begin()));802}803 804// Comparison tests.805TYPED_TEST(SmallVectorTest, ComparisonEqualityTest) {806 SCOPED_TRACE("ComparisonEqualityTest");807 auto &V = this->theVector;808 auto &U = this->otherVector;809 makeSequence(V, 1, 3);810 makeSequence(U, 1, 3);811 812 EXPECT_TRUE(V == U);813 EXPECT_FALSE(V != U);814 815 U.clear();816 makeSequence(U, 2, 4);817 818 EXPECT_FALSE(V == U);819 EXPECT_TRUE(V != U);820}821 822// Comparison tests.823TYPED_TEST(SmallVectorTest, ComparisonLessThanTest) {824 SCOPED_TRACE("ComparisonLessThanTest");825 auto &V = this->theVector;826 auto &U = this->otherVector;827 V = {1, 2, 4};828 U = {1, 4};829 830 EXPECT_TRUE(V < U);831 EXPECT_TRUE(V <= U);832 EXPECT_FALSE(V > U);833 EXPECT_FALSE(V >= U);834 835 EXPECT_FALSE(U < V);836 EXPECT_FALSE(U <= V);837 EXPECT_TRUE(U > V);838 EXPECT_TRUE(U >= V);839 840 U = {1, 2, 4};841 842 EXPECT_FALSE(V < U);843 EXPECT_TRUE(V <= U);844 EXPECT_FALSE(V > U);845 EXPECT_TRUE(V >= U);846 847 EXPECT_FALSE(U < V);848 EXPECT_TRUE(U <= V);849 EXPECT_FALSE(U > V);850 EXPECT_TRUE(U >= V);851}852 853// Constant vector tests.854TYPED_TEST(SmallVectorTest, ConstVectorTest) {855 const TypeParam constVector;856 857 EXPECT_EQ(0u, constVector.size());858 EXPECT_TRUE(constVector.empty());859 EXPECT_TRUE(constVector.begin() == constVector.end());860}861 862// Direct array access.863TYPED_TEST(SmallVectorTest, DirectVectorTest) {864 auto &V = this->theVector;865 EXPECT_EQ(0u, V.size());866 V.reserve(4);867 EXPECT_LE(4u, V.capacity());868 EXPECT_EQ(0, Constructable::getNumConstructorCalls());869 V.push_back(1);870 V.push_back(2);871 V.push_back(3);872 V.push_back(4);873 EXPECT_EQ(4u, V.size());874 EXPECT_EQ(8, Constructable::getNumConstructorCalls());875 EXPECT_EQ(1, V[0].getValue());876 EXPECT_EQ(2, V[1].getValue());877 EXPECT_EQ(3, V[2].getValue());878 EXPECT_EQ(4, V[3].getValue());879}880 881TYPED_TEST(SmallVectorTest, IteratorTest) {882 auto &V = this->theVector;883 std::list<int> L;884 V.insert(V.end(), L.begin(), L.end());885}886 887template <typename InvalidType> class DualSmallVectorsTest;888 889template <typename VectorT1, typename VectorT2>890class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase {891protected:892 VectorT1 theVector;893 VectorT2 otherVector;894};895 896using DualSmallVectorTestTypes = ::testing::Types<897 // Small mode -> Small mode.898 std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>,899 // Small mode -> Big mode.900 std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>,901 // Big mode -> Small mode.902 std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 4>>,903 // Big mode -> Big mode.904 std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 2>>>;905 906TYPED_TEST_SUITE(DualSmallVectorsTest, DualSmallVectorTestTypes, );907 908TYPED_TEST(DualSmallVectorsTest, MoveAssignment) {909 SCOPED_TRACE("MoveAssignTest-DualVectorTypes");910 auto &V = this->theVector;911 auto &U = this->otherVector;912 // Set up our vector with four elements.913 for (unsigned I = 0; I < 4; ++I)914 U.push_back(Constructable(I));915 916 const Constructable *OrigDataPtr = U.data();917 918 // Move-assign from the other vector.919 V = std::move(static_cast<SmallVectorImpl<Constructable> &>(U));920 921 // Make sure we have the right result.922 assertValuesInOrder(V, 4u, 0, 1, 2, 3);923 924 // Make sure the # of constructor/destructor calls line up. There925 // are two live objects after clearing the other vector.926 U.clear();927 EXPECT_EQ(Constructable::getNumConstructorCalls()-4,928 Constructable::getNumDestructorCalls());929 930 // If the source vector (otherVector) was in small-mode, assert that we just931 // moved the data pointer over.932 EXPECT_TRUE(NumBuiltinElts(U) == 4 || V.data() == OrigDataPtr);933 934 // There shouldn't be any live objects any more.935 V.clear();936 EXPECT_EQ(Constructable::getNumConstructorCalls(),937 Constructable::getNumDestructorCalls());938 939 // We shouldn't have copied anything in this whole process.940 EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0);941}942 943struct notassignable {944 int &x;945 notassignable(int &x) : x(x) {}946};947 948TEST(SmallVectorCustomTest, NoAssignTest) {949 int x = 0;950 SmallVector<notassignable, 2> vec;951 vec.push_back(notassignable(x));952 x = 42;953 EXPECT_EQ(42, vec.pop_back_val().x);954}955 956struct MovedFrom {957 bool hasValue;958 MovedFrom() : hasValue(true) {959 }960 MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) {961 m.hasValue = false;962 }963 MovedFrom &operator=(MovedFrom&& m) {964 hasValue = m.hasValue;965 m.hasValue = false;966 return *this;967 }968};969 970TEST(SmallVectorTest, MidInsert) {971 SmallVector<MovedFrom, 3> v;972 v.push_back(MovedFrom());973 v.insert(v.begin(), MovedFrom());974 for (MovedFrom &m : v)975 EXPECT_TRUE(m.hasValue);976}977 978enum EmplaceableArgState {979 EAS_Defaulted,980 EAS_Arg,981 EAS_LValue,982 EAS_RValue,983 EAS_Failure984};985template <int I> struct EmplaceableArg {986 EmplaceableArgState State;987 EmplaceableArg() : State(EAS_Defaulted) {}988 EmplaceableArg(EmplaceableArg &&X)989 : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {}990 EmplaceableArg(EmplaceableArg &X)991 : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {}992 993 explicit EmplaceableArg(bool) : State(EAS_Arg) {}994 995private:996 EmplaceableArg &operator=(EmplaceableArg &&) = delete;997 EmplaceableArg &operator=(const EmplaceableArg &) = delete;998};999 1000enum EmplaceableState { ES_Emplaced, ES_Moved };1001struct Emplaceable {1002 EmplaceableArg<0> A0;1003 EmplaceableArg<1> A1;1004 EmplaceableArg<2> A2;1005 EmplaceableArg<3> A3;1006 EmplaceableState State;1007 1008 Emplaceable() : State(ES_Emplaced) {}1009 1010 template <class A0Ty>1011 explicit Emplaceable(A0Ty &&A0)1012 : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {}1013 1014 template <class A0Ty, class A1Ty>1015 Emplaceable(A0Ty &&A0, A1Ty &&A1)1016 : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),1017 State(ES_Emplaced) {}1018 1019 template <class A0Ty, class A1Ty, class A2Ty>1020 Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2)1021 : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),1022 A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {}1023 1024 template <class A0Ty, class A1Ty, class A2Ty, class A3Ty>1025 Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3)1026 : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),1027 A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)),1028 State(ES_Emplaced) {}1029 1030 Emplaceable(Emplaceable &&) : State(ES_Moved) {}1031 Emplaceable &operator=(Emplaceable &&) {1032 State = ES_Moved;1033 return *this;1034 }1035 1036private:1037 Emplaceable(const Emplaceable &) = delete;1038 Emplaceable &operator=(const Emplaceable &) = delete;1039};1040 1041TEST(SmallVectorTest, EmplaceBack) {1042 EmplaceableArg<0> A0(true);1043 EmplaceableArg<1> A1(true);1044 EmplaceableArg<2> A2(true);1045 EmplaceableArg<3> A3(true);1046 {1047 SmallVector<Emplaceable, 3> V;1048 Emplaceable &back = V.emplace_back();1049 EXPECT_TRUE(&back == &V.back());1050 EXPECT_TRUE(V.size() == 1);1051 EXPECT_TRUE(back.State == ES_Emplaced);1052 EXPECT_TRUE(back.A0.State == EAS_Defaulted);1053 EXPECT_TRUE(back.A1.State == EAS_Defaulted);1054 EXPECT_TRUE(back.A2.State == EAS_Defaulted);1055 EXPECT_TRUE(back.A3.State == EAS_Defaulted);1056 }1057 {1058 SmallVector<Emplaceable, 3> V;1059 Emplaceable &back = V.emplace_back(std::move(A0));1060 EXPECT_TRUE(&back == &V.back());1061 EXPECT_TRUE(V.size() == 1);1062 EXPECT_TRUE(back.State == ES_Emplaced);1063 EXPECT_TRUE(back.A0.State == EAS_RValue);1064 EXPECT_TRUE(back.A1.State == EAS_Defaulted);1065 EXPECT_TRUE(back.A2.State == EAS_Defaulted);1066 EXPECT_TRUE(back.A3.State == EAS_Defaulted);1067 }1068 {1069 SmallVector<Emplaceable, 3> V;1070 Emplaceable &back = V.emplace_back(A0);1071 EXPECT_TRUE(&back == &V.back());1072 EXPECT_TRUE(V.size() == 1);1073 EXPECT_TRUE(back.State == ES_Emplaced);1074 EXPECT_TRUE(back.A0.State == EAS_LValue);1075 EXPECT_TRUE(back.A1.State == EAS_Defaulted);1076 EXPECT_TRUE(back.A2.State == EAS_Defaulted);1077 EXPECT_TRUE(back.A3.State == EAS_Defaulted);1078 }1079 {1080 SmallVector<Emplaceable, 3> V;1081 Emplaceable &back = V.emplace_back(A0, A1);1082 EXPECT_TRUE(&back == &V.back());1083 EXPECT_TRUE(V.size() == 1);1084 EXPECT_TRUE(back.State == ES_Emplaced);1085 EXPECT_TRUE(back.A0.State == EAS_LValue);1086 EXPECT_TRUE(back.A1.State == EAS_LValue);1087 EXPECT_TRUE(back.A2.State == EAS_Defaulted);1088 EXPECT_TRUE(back.A3.State == EAS_Defaulted);1089 }1090 {1091 SmallVector<Emplaceable, 3> V;1092 Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1));1093 EXPECT_TRUE(&back == &V.back());1094 EXPECT_TRUE(V.size() == 1);1095 EXPECT_TRUE(back.State == ES_Emplaced);1096 EXPECT_TRUE(back.A0.State == EAS_RValue);1097 EXPECT_TRUE(back.A1.State == EAS_RValue);1098 EXPECT_TRUE(back.A2.State == EAS_Defaulted);1099 EXPECT_TRUE(back.A3.State == EAS_Defaulted);1100 }1101 {1102 SmallVector<Emplaceable, 3> V;1103 Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3);1104 EXPECT_TRUE(&back == &V.back());1105 EXPECT_TRUE(V.size() == 1);1106 EXPECT_TRUE(back.State == ES_Emplaced);1107 EXPECT_TRUE(back.A0.State == EAS_RValue);1108 EXPECT_TRUE(back.A1.State == EAS_LValue);1109 EXPECT_TRUE(back.A2.State == EAS_RValue);1110 EXPECT_TRUE(back.A3.State == EAS_LValue);1111 }1112 {1113 SmallVector<int, 1> V;1114 V.emplace_back();1115 V.emplace_back(42);1116 EXPECT_EQ(2U, V.size());1117 EXPECT_EQ(0, V[0]);1118 EXPECT_EQ(42, V[1]);1119 }1120}1121 1122TEST(SmallVectorTest, DefaultInlinedElements) {1123 SmallVector<int> V;1124 EXPECT_TRUE(V.empty());1125 V.push_back(7);1126 EXPECT_EQ(V[0], 7);1127 1128 // Check that at least a couple layers of nested SmallVector<T>'s are allowed1129 // by the default inline elements policy. This pattern happens in practice1130 // with some frequency, and it seems fairly harmless even though each layer of1131 // SmallVector's will grow the total sizeof by a vector header beyond the1132 // "preferred" maximum sizeof.1133 SmallVector<SmallVector<SmallVector<int>>> NestedV;1134 NestedV.emplace_back().emplace_back().emplace_back(42);1135 EXPECT_EQ(NestedV[0][0][0], 42);1136}1137 1138TEST(SmallVectorTest, InitializerList) {1139 SmallVector<int, 2> V1 = {};1140 EXPECT_TRUE(V1.empty());1141 V1 = {0, 0};1142 EXPECT_TRUE(ArrayRef(V1).equals({0, 0}));1143 V1 = {-1, -1};1144 EXPECT_TRUE(ArrayRef(V1).equals({-1, -1}));1145 1146 SmallVector<int, 2> V2 = {1, 2, 3, 4};1147 EXPECT_TRUE(ArrayRef(V2).equals({1, 2, 3, 4}));1148 V2.assign({4});1149 EXPECT_TRUE(ArrayRef(V2).equals({4}));1150 V2.append({3, 2});1151 EXPECT_TRUE(ArrayRef(V2).equals({4, 3, 2}));1152 V2.insert(V2.begin() + 1, 5);1153 EXPECT_TRUE(ArrayRef(V2).equals({4, 5, 3, 2}));1154}1155 1156namespace namespace_with_adl {1157struct MyVector {1158 std::vector<int> data;1159};1160 1161std::vector<int>::const_iterator begin(const MyVector &V) {1162 return V.data.begin();1163}1164std::vector<int>::const_iterator end(const MyVector &V) { return V.data.end(); }1165} // namespace namespace_with_adl1166 1167TEST(SmallVectorTest, ToVector) {1168 {1169 std::vector<char> v = {'a', 'b', 'c'};1170 auto Vector = to_vector<4>(v);1171 static_assert(NumBuiltinElts(Vector) == 4u);1172 ASSERT_EQ(3u, Vector.size());1173 for (size_t I = 0; I < v.size(); ++I)1174 EXPECT_EQ(v[I], Vector[I]);1175 }1176 {1177 std::vector<char> v = {'a', 'b', 'c'};1178 auto Vector = to_vector(v);1179 static_assert(NumBuiltinElts(Vector) != 4u);1180 ASSERT_EQ(3u, Vector.size());1181 for (size_t I = 0; I < v.size(); ++I)1182 EXPECT_EQ(v[I], Vector[I]);1183 }1184 {1185 // Check that to_vector and to_vector_of work with types that require ADL1186 // for being/end iterators.1187 namespace_with_adl::MyVector V = {{1, 2, 3}};1188 auto IntVector = to_vector(V);1189 EXPECT_THAT(IntVector, testing::ElementsAre(1, 2, 3));1190 IntVector = to_vector<3>(V);1191 EXPECT_THAT(IntVector, testing::ElementsAre(1, 2, 3));1192 }1193}1194 1195struct To {1196 int Content;1197 friend bool operator==(const To &LHS, const To &RHS) {1198 return LHS.Content == RHS.Content;1199 }1200};1201 1202class From {1203public:1204 From() = default;1205 From(To M) { T = M; }1206 operator To() const { return T; }1207 1208private:1209 To T;1210};1211 1212TEST(SmallVectorTest, ConstructFromArrayRefOfConvertibleType) {1213 To to1{1}, to2{2}, to3{3};1214 std::vector<From> StdVector = {From(to1), From(to2), From(to3)};1215 ArrayRef<From> Array = StdVector;1216 {1217 llvm::SmallVector<To> Vector(Array);1218 1219 ASSERT_EQ(Array.size(), Vector.size());1220 for (size_t I = 0; I < Array.size(); ++I)1221 EXPECT_EQ(Array[I], Vector[I]);1222 }1223 {1224 llvm::SmallVector<To, 4> Vector(Array);1225 1226 ASSERT_EQ(Array.size(), Vector.size());1227 ASSERT_EQ(4u, NumBuiltinElts(Vector));1228 for (size_t I = 0; I < Array.size(); ++I)1229 EXPECT_EQ(Array[I], Vector[I]);1230 }1231}1232 1233TEST(SmallVectorTest, ToVectorOf) {1234 To to1{1}, to2{2}, to3{3};1235 std::vector<From> StdVector = {From(to1), From(to2), From(to3)};1236 {1237 llvm::SmallVector<To> Vector = llvm::to_vector_of<To>(StdVector);1238 1239 ASSERT_EQ(StdVector.size(), Vector.size());1240 for (size_t I = 0; I < StdVector.size(); ++I)1241 EXPECT_EQ(StdVector[I], Vector[I]);1242 }1243 {1244 auto Vector = llvm::to_vector_of<To, 4>(StdVector);1245 1246 ASSERT_EQ(StdVector.size(), Vector.size());1247 static_assert(NumBuiltinElts(Vector) == 4u);1248 for (size_t I = 0; I < StdVector.size(); ++I)1249 EXPECT_EQ(StdVector[I], Vector[I]);1250 }1251 {1252 // Check that to_vector works with types that require ADL for being/end1253 // iterators.1254 namespace_with_adl::MyVector V = {{1, 2, 3}};1255 auto UnsignedVector = to_vector_of<unsigned>(V);1256 EXPECT_THAT(UnsignedVector, testing::ElementsAre(1u, 2u, 3u));1257 UnsignedVector = to_vector_of<unsigned, 3>(V);1258 EXPECT_THAT(UnsignedVector, testing::ElementsAre(1u, 2u, 3u));1259 }1260}1261 1262template <class VectorT>1263class SmallVectorReferenceInvalidationTest : public SmallVectorTestBase {1264protected:1265 const char *AssertionMessage =1266 "Attempting to reference an element of the vector in an operation \" "1267 "\"that invalidates it";1268 1269 VectorT V;1270 1271 template <class T> static bool isValueType() {1272 return std::is_same_v<T, typename VectorT::value_type>;1273 }1274 1275 void SetUp() override {1276 SmallVectorTestBase::SetUp();1277 1278 // Fill up the small size so that insertions move the elements.1279 for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)1280 V.emplace_back(I + 1);1281 }1282};1283 1284// Test one type that's trivially copyable (int) and one that isn't1285// (Constructable) since reference invalidation may be fixed differently for1286// each.1287using SmallVectorReferenceInvalidationTestTypes =1288 ::testing::Types<SmallVector<int, 3>, SmallVector<Constructable, 3>>;1289 1290TYPED_TEST_SUITE(SmallVectorReferenceInvalidationTest,1291 SmallVectorReferenceInvalidationTestTypes, );1292 1293TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBack) {1294 // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.1295 auto &V = this->V;1296 int N = NumBuiltinElts(V);1297 1298 // Push back a reference to last element when growing from small storage.1299 V.push_back(V.back());1300 EXPECT_EQ(N, V.back());1301 1302 // Check that the old value is still there (not moved away).1303 EXPECT_EQ(N, V[V.size() - 2]);1304 1305 // Fill storage again.1306 V.back() = V.size();1307 while (V.size() < V.capacity())1308 V.push_back(V.size() + 1);1309 1310 // Push back a reference to last element when growing from large storage.1311 V.push_back(V.back());1312 EXPECT_EQ(int(V.size()) - 1, V.back());1313}1314 1315TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) {1316 // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.1317 auto &V = this->V;1318 int N = NumBuiltinElts(V);1319 1320 // Push back a reference to last element when growing from small storage.1321 V.push_back(std::move(V.back()));1322 EXPECT_EQ(N, V.back());1323 if (this->template isValueType<Constructable>()) {1324 // Check that the value was moved (not copied).1325 EXPECT_EQ(0, V[V.size() - 2]);1326 }1327 1328 // Fill storage again.1329 V.back() = V.size();1330 while (V.size() < V.capacity())1331 V.push_back(V.size() + 1);1332 1333 // Push back a reference to last element when growing from large storage.1334 V.push_back(std::move(V.back()));1335 1336 // Check the values.1337 EXPECT_EQ(int(V.size()) - 1, V.back());1338 if (this->template isValueType<Constructable>()) {1339 // Check the value got moved out.1340 EXPECT_EQ(0, V[V.size() - 2]);1341 }1342}1343 1344TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) {1345 auto &V = this->V;1346 (void)V;1347 int N = NumBuiltinElts(V);1348 V.resize(N + 1, V.back());1349 EXPECT_EQ(N, V.back());1350 1351 // Resize to add enough elements that V will grow again. If reference1352 // invalidation breaks in the future, sanitizers should be able to catch a1353 // use-after-free here.1354 V.resize(V.capacity() + 1, V.front());1355 EXPECT_EQ(1, V.back());1356}1357 1358TYPED_TEST(SmallVectorReferenceInvalidationTest, Append) {1359 auto &V = this->V;1360 (void)V;1361 V.append(1, V.back());1362 int N = NumBuiltinElts(V);1363 EXPECT_EQ(N, V[N - 1]);1364 1365 // Append enough more elements that V will grow again. This tests growing1366 // when already in large mode.1367 //1368 // If reference invalidation breaks in the future, sanitizers should be able1369 // to catch a use-after-free here.1370 V.append(V.capacity() - V.size() + 1, V.front());1371 EXPECT_EQ(1, V.back());1372}1373 1374TYPED_TEST(SmallVectorReferenceInvalidationTest, AppendRange) {1375 auto &V = this->V;1376 (void)V;1377#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST1378 EXPECT_DEATH(V.append(V.begin(), V.begin() + 1), this->AssertionMessage);1379 1380 ASSERT_EQ(3u, NumBuiltinElts(V));1381 ASSERT_EQ(3u, V.size());1382 V.pop_back();1383 ASSERT_EQ(2u, V.size());1384 1385 // Confirm this checks for growth when there's more than one element1386 // appended.1387 EXPECT_DEATH(V.append(V.begin(), V.end()), this->AssertionMessage);1388#endif1389}1390 1391TYPED_TEST(SmallVectorReferenceInvalidationTest, Assign) {1392 // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.1393 auto &V = this->V;1394 (void)V;1395 int N = NumBuiltinElts(V);1396 ASSERT_EQ(unsigned(N), V.size());1397 ASSERT_EQ(unsigned(N), V.capacity());1398 1399 // Check assign that shrinks in small mode.1400 V.assign(1, V.back());1401 EXPECT_EQ(1u, V.size());1402 EXPECT_EQ(N, V[0]);1403 1404 // Check assign that grows within small mode.1405 ASSERT_LT(V.size(), V.capacity());1406 V.assign(V.capacity(), V.back());1407 for (int I = 0, E = V.size(); I != E; ++I) {1408 EXPECT_EQ(N, V[I]);1409 1410 // Reset to [1, 2, ...].1411 V[I] = I + 1;1412 }1413 1414 // Check assign that grows to large mode.1415 ASSERT_EQ(2, V[1]);1416 V.assign(V.capacity() + 1, V[1]);1417 for (int I = 0, E = V.size(); I != E; ++I) {1418 EXPECT_EQ(2, V[I]);1419 1420 // Reset to [1, 2, ...].1421 V[I] = I + 1;1422 }1423 1424 // Check assign that shrinks in large mode.1425 V.assign(1, V[1]);1426 EXPECT_EQ(2, V[0]);1427}1428 1429TYPED_TEST(SmallVectorReferenceInvalidationTest, AssignRange) {1430 auto &V = this->V;1431#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST1432 EXPECT_DEATH(V.assign(V.begin(), V.end()), this->AssertionMessage);1433 EXPECT_DEATH(V.assign(V.begin(), V.end() - 1), this->AssertionMessage);1434#endif1435 V.assign(V.begin(), V.begin());1436 EXPECT_TRUE(V.empty());1437}1438 1439TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) {1440 // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.1441 auto &V = this->V;1442 (void)V;1443 1444 // Insert a reference to the back (not at end() or else insert delegates to1445 // push_back()), growing out of small mode. Confirm the value was copied out1446 // (moving out Constructable sets it to 0).1447 V.insert(V.begin(), V.back());1448 EXPECT_EQ(int(V.size() - 1), V.front());1449 EXPECT_EQ(int(V.size() - 1), V.back());1450 1451 // Fill up the vector again.1452 while (V.size() < V.capacity())1453 V.push_back(V.size() + 1);1454 1455 // Grow again from large storage to large storage.1456 V.insert(V.begin(), V.back());1457 EXPECT_EQ(int(V.size() - 1), V.front());1458 EXPECT_EQ(int(V.size() - 1), V.back());1459}1460 1461TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) {1462 // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.1463 auto &V = this->V;1464 (void)V;1465 1466 // Insert a reference to the back (not at end() or else insert delegates to1467 // push_back()), growing out of small mode. Confirm the value was copied out1468 // (moving out Constructable sets it to 0).1469 V.insert(V.begin(), std::move(V.back()));1470 EXPECT_EQ(int(V.size() - 1), V.front());1471 if (this->template isValueType<Constructable>()) {1472 // Check the value got moved out.1473 EXPECT_EQ(0, V.back());1474 }1475 1476 // Fill up the vector again.1477 while (V.size() < V.capacity())1478 V.push_back(V.size() + 1);1479 1480 // Grow again from large storage to large storage.1481 V.insert(V.begin(), std::move(V.back()));1482 EXPECT_EQ(int(V.size() - 1), V.front());1483 if (this->template isValueType<Constructable>()) {1484 // Check the value got moved out.1485 EXPECT_EQ(0, V.back());1486 }1487}1488 1489TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) {1490 auto &V = this->V;1491 (void)V;1492 1493 // Cover NumToInsert <= this->end() - I.1494 V.insert(V.begin() + 1, 1, V.back());1495 int N = NumBuiltinElts(V);1496 EXPECT_EQ(N, V[1]);1497 1498 // Cover NumToInsert > this->end() - I, inserting enough elements that V will1499 // also grow again; V.capacity() will be more elements than necessary but1500 // it's a simple way to cover both conditions.1501 //1502 // If reference invalidation breaks in the future, sanitizers should be able1503 // to catch a use-after-free here.1504 V.insert(V.begin(), V.capacity(), V.front());1505 EXPECT_EQ(1, V.front());1506}1507 1508TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertRange) {1509 auto &V = this->V;1510 (void)V;1511#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST1512 EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.begin() + 1),1513 this->AssertionMessage);1514 1515 ASSERT_EQ(3u, NumBuiltinElts(V));1516 ASSERT_EQ(3u, V.size());1517 V.pop_back();1518 ASSERT_EQ(2u, V.size());1519 1520 // Confirm this checks for growth when there's more than one element1521 // inserted.1522 EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.end()), this->AssertionMessage);1523#endif1524}1525 1526TYPED_TEST(SmallVectorReferenceInvalidationTest, EmplaceBack) {1527 // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.1528 auto &V = this->V;1529 int N = NumBuiltinElts(V);1530 1531 // Push back a reference to last element when growing from small storage.1532 V.emplace_back(V.back());1533 EXPECT_EQ(N, V.back());1534 1535 // Check that the old value is still there (not moved away).1536 EXPECT_EQ(N, V[V.size() - 2]);1537 1538 // Fill storage again.1539 V.back() = V.size();1540 while (V.size() < V.capacity())1541 V.push_back(V.size() + 1);1542 1543 // Push back a reference to last element when growing from large storage.1544 V.emplace_back(V.back());1545 EXPECT_EQ(int(V.size()) - 1, V.back());1546}1547 1548template <class VectorT>1549class SmallVectorInternalReferenceInvalidationTest1550 : public SmallVectorTestBase {1551protected:1552 const char *AssertionMessage =1553 "Attempting to reference an element of the vector in an operation \" "1554 "\"that invalidates it";1555 1556 VectorT V;1557 1558 void SetUp() override {1559 SmallVectorTestBase::SetUp();1560 1561 // Fill up the small size so that insertions move the elements.1562 for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)1563 V.emplace_back(I + 1, I + 1);1564 }1565};1566 1567// Test pairs of the same types from SmallVectorReferenceInvalidationTestTypes.1568using SmallVectorInternalReferenceInvalidationTestTypes =1569 ::testing::Types<SmallVector<std::pair<int, int>, 3>,1570 SmallVector<std::pair<Constructable, Constructable>, 3>>;1571 1572TYPED_TEST_SUITE(SmallVectorInternalReferenceInvalidationTest,1573 SmallVectorInternalReferenceInvalidationTestTypes, );1574 1575TYPED_TEST(SmallVectorInternalReferenceInvalidationTest, EmplaceBack) {1576 // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.1577 auto &V = this->V;1578 int N = NumBuiltinElts(V);1579 1580 // Push back a reference to last element when growing from small storage.1581 V.emplace_back(V.back().first, V.back().second);1582 EXPECT_EQ(N, V.back().first);1583 EXPECT_EQ(N, V.back().second);1584 1585 // Check that the old value is still there (not moved away).1586 EXPECT_EQ(N, V[V.size() - 2].first);1587 EXPECT_EQ(N, V[V.size() - 2].second);1588 1589 // Fill storage again.1590 V.back().first = V.back().second = V.size();1591 while (V.size() < V.capacity())1592 V.emplace_back(V.size() + 1, V.size() + 1);1593 1594 // Push back a reference to last element when growing from large storage.1595 V.emplace_back(V.back().first, V.back().second);1596 EXPECT_EQ(int(V.size()) - 1, V.back().first);1597 EXPECT_EQ(int(V.size()) - 1, V.back().second);1598}1599 1600} // end namespace1601