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