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

source code of llvm/unittests/ADT/SmallVectorTest.cpp