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