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 | |
19 | using c10::SmallVector; |
20 | using c10::SmallVectorImpl; |
21 | |
22 | namespace { |
23 | |
24 | /// A helper class that counts the total number of constructor and |
25 | /// destructor calls. |
26 | class 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 | |
136 | int Constructable::numConstructorCalls; |
137 | int Constructable::numCopyConstructorCalls; |
138 | int Constructable::numMoveConstructorCalls; |
139 | int Constructable::numDestructorCalls; |
140 | int Constructable::numAssignmentCalls; |
141 | int Constructable::numCopyAssignmentCalls; |
142 | int Constructable::numMoveAssignmentCalls; |
143 | |
144 | struct 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 | |
156 | C10_USED void CompileTest() { |
157 | SmallVector<NonCopyable, 0> V; |
158 | V.resize(42); |
159 | } |
160 | |
161 | class 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 |
202 | template <typename VectorT> |
203 | class SmallVectorTest : public SmallVectorTestBase { |
204 | protected: |
205 | VectorT theVector; |
206 | VectorT otherVector; |
207 | }; |
208 | |
209 | typedef ::testing::Types< |
210 | SmallVector<Constructable, 0>, |
211 | SmallVector<Constructable, 1>, |
212 | SmallVector<Constructable, 2>, |
213 | SmallVector<Constructable, 4>, |
214 | SmallVector<Constructable, 5>> |
215 | SmallVectorTestTypes; |
216 | TYPED_TEST_SUITE(SmallVectorTest, SmallVectorTestTypes, ); |
217 | |
218 | // Constructor test. |
219 | TYPED_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. |
226 | TYPED_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. |
235 | TYPED_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. |
244 | TYPED_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. |
293 | TYPED_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. |
306 | TYPED_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. |
319 | TYPED_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 | |
329 | TYPED_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. |
345 | TYPED_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 | |
352 | TEST(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. |
378 | TYPED_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. |
397 | TYPED_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. |
436 | TYPED_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 |
447 | TYPED_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 |
459 | TYPED_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 |
468 | TYPED_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 | |
476 | struct 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 | |
490 | TYPED_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 | |
498 | TYPED_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 |
508 | TYPED_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 |
517 | TYPED_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 |
527 | TYPED_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 | |
535 | TYPED_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 |
545 | TYPED_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 |
577 | TYPED_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 |
587 | TYPED_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. |
597 | TYPED_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. |
608 | TYPED_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. |
620 | TYPED_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 | |
645 | TYPED_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 | |
655 | TYPED_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 | |
675 | TYPED_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. |
691 | TYPED_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 | |
716 | TYPED_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 | |
741 | TYPED_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. |
762 | TYPED_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. |
779 | TYPED_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. |
788 | TYPED_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 | |
805 | TYPED_TEST(SmallVectorTest, IteratorTest) { |
806 | std::list<int> L; |
807 | this->theVector.insert(this->theVector.end(), L.begin(), L.end()); |
808 | } |
809 | |
810 | template <typename InvalidType> |
811 | class DualSmallVectorsTest; |
812 | |
813 | template <typename VectorT1, typename VectorT2> |
814 | class 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 | |
826 | typedef ::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 | |
837 | TYPED_TEST_SUITE(DualSmallVectorsTest, DualSmallVectorTestTypes, ); |
838 | |
839 | TYPED_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 | |
878 | struct notassignable { |
879 | int& x; |
880 | notassignable(int& x) : x(x) {} |
881 | }; |
882 | |
883 | TEST(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 | |
891 | struct 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 | |
904 | TEST(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 | |
912 | enum EmplaceableArgState { |
913 | EAS_Defaulted, |
914 | EAS_Arg, |
915 | EAS_LValue, |
916 | EAS_RValue, |
917 | EAS_Failure |
918 | }; |
919 | template <int I> |
920 | struct 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 | |
935 | enum EmplaceableState { ES_Emplaced, ES_Moved }; |
936 | struct 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 | |
981 | TEST(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 | |
1062 | TEST(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 | |
1078 | TEST(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 | |
1096 | template <class VectorT> |
1097 | class 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. |
1127 | using SmallVectorReferenceInvalidationTestTypes = |
1128 | ::testing::Types<SmallVector<int, 3>, SmallVector<Constructable, 3>>; |
1129 | |
1130 | TYPED_TEST_SUITE( |
1131 | SmallVectorReferenceInvalidationTest, |
1132 | SmallVectorReferenceInvalidationTestTypes, ); |
1133 | |
1134 | TYPED_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 | |
1156 | TYPED_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 | |
1185 | TYPED_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 | |
1199 | TYPED_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 | |
1215 | TYPED_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 | |
1232 | TYPED_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 | |
1270 | TYPED_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 | |
1280 | TYPED_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 | |
1302 | TYPED_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 | |
1330 | TYPED_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 | |
1349 | TYPED_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 | |
1367 | TYPED_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 | |
1389 | template <class VectorT> |
1390 | class 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. |
1414 | using SmallVectorInternalReferenceInvalidationTestTypes = ::testing::Types< |
1415 | SmallVector<std::pair<int, int>, 3>, |
1416 | SmallVector<std::pair<Constructable, Constructable>, 3>>; |
1417 | |
1418 | TYPED_TEST_SUITE( |
1419 | SmallVectorInternalReferenceInvalidationTest, |
1420 | SmallVectorInternalReferenceInvalidationTestTypes, ); |
1421 | |
1422 | TYPED_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 | |