1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
6 
7 #include <utility>
8 
9 #include "mozilla/IntegerRange.h"
10 #include "mozilla/UniquePtr.h"
11 #include "mozilla/Vector.h"
12 
13 using mozilla::IntegerRange;
14 using mozilla::MakeUnique;
15 using mozilla::UniquePtr;
16 using mozilla::Vector;
17 using mozilla::detail::VectorTesting;
18 
19 struct mozilla::detail::VectorTesting {
20   static void testReserved();
21   static void testConstRange();
22   static void testEmplaceBack();
23   static void testReverse();
24   static void testExtractRawBuffer();
25   static void testExtractOrCopyRawBuffer();
26   static void testReplaceRawBuffer();
27   static void testInsert();
28   static void testErase();
29   static void testShrinkStorageToFit();
30   static void testAppend();
31 };
32 
testReserved()33 void mozilla::detail::VectorTesting::testReserved() {
34 #ifdef DEBUG
35   Vector<bool> bv;
36   MOZ_RELEASE_ASSERT(bv.reserved() == 0);
37 
38   MOZ_RELEASE_ASSERT(bv.append(true));
39   MOZ_RELEASE_ASSERT(bv.reserved() == 1);
40 
41   Vector<bool> otherbv;
42   MOZ_RELEASE_ASSERT(otherbv.append(false));
43   MOZ_RELEASE_ASSERT(otherbv.append(true));
44   MOZ_RELEASE_ASSERT(bv.appendAll(otherbv));
45   MOZ_RELEASE_ASSERT(bv.reserved() == 3);
46 
47   MOZ_RELEASE_ASSERT(bv.reserve(5));
48   MOZ_RELEASE_ASSERT(bv.reserved() == 5);
49 
50   MOZ_RELEASE_ASSERT(bv.reserve(1));
51   MOZ_RELEASE_ASSERT(bv.reserved() == 5);
52 
53   Vector<bool> bv2(std::move(bv));
54   MOZ_RELEASE_ASSERT(bv.reserved() == 0);
55   MOZ_RELEASE_ASSERT(bv2.reserved() == 5);
56 
57   bv2.clearAndFree();
58   MOZ_RELEASE_ASSERT(bv2.reserved() == 0);
59 
60   Vector<int, 42> iv;
61   MOZ_RELEASE_ASSERT(iv.reserved() == 0);
62 
63   MOZ_RELEASE_ASSERT(iv.append(17));
64   MOZ_RELEASE_ASSERT(iv.reserved() == 1);
65 
66   Vector<int, 42> otheriv;
67   MOZ_RELEASE_ASSERT(otheriv.append(42));
68   MOZ_RELEASE_ASSERT(otheriv.append(37));
69   MOZ_RELEASE_ASSERT(iv.appendAll(otheriv));
70   MOZ_RELEASE_ASSERT(iv.reserved() == 3);
71 
72   MOZ_RELEASE_ASSERT(iv.reserve(5));
73   MOZ_RELEASE_ASSERT(iv.reserved() == 5);
74 
75   MOZ_RELEASE_ASSERT(iv.reserve(1));
76   MOZ_RELEASE_ASSERT(iv.reserved() == 5);
77 
78   MOZ_RELEASE_ASSERT(iv.reserve(55));
79   MOZ_RELEASE_ASSERT(iv.reserved() == 55);
80 
81   Vector<int, 42> iv2(std::move(iv));
82   MOZ_RELEASE_ASSERT(iv.reserved() == 0);
83   MOZ_RELEASE_ASSERT(iv2.reserved() == 55);
84 
85   iv2.clearAndFree();
86   MOZ_RELEASE_ASSERT(iv2.reserved() == 0);
87 #endif
88 }
89 
testConstRange()90 void mozilla::detail::VectorTesting::testConstRange() {
91 #ifdef DEBUG
92   Vector<int> vec;
93 
94   for (int i = 0; i < 10; i++) {
95     MOZ_RELEASE_ASSERT(vec.append(i));
96   }
97 
98   const auto& vecRef = vec;
99 
100   Vector<int>::ConstRange range = vecRef.all();
101   for (int i = 0; i < 10; i++) {
102     MOZ_RELEASE_ASSERT(!range.empty());
103     MOZ_RELEASE_ASSERT(range.front() == i);
104     range.popFront();
105   }
106 #endif
107 }
108 
109 namespace {
110 
111 struct S {
112   size_t j;
113   UniquePtr<size_t> k;
114 
115   static size_t constructCount;
116   static size_t moveCount;
117   static size_t destructCount;
118 
resetCounts__anon70451cfd0111::S119   static void resetCounts() {
120     constructCount = 0;
121     moveCount = 0;
122     destructCount = 0;
123   }
124 
S__anon70451cfd0111::S125   S(size_t j, size_t k) : j(j), k(MakeUnique<size_t>(k)) { constructCount++; }
126 
S__anon70451cfd0111::S127   S(S&& rhs) : j(rhs.j), k(std::move(rhs.k)) {
128     rhs.j = 0;
129     rhs.k.reset(0);
130     moveCount++;
131   }
132 
~S__anon70451cfd0111::S133   ~S() { destructCount++; }
134 
operator =__anon70451cfd0111::S135   S& operator=(S&& rhs) {
136     j = rhs.j;
137     rhs.j = 0;
138     k = std::move(rhs.k);
139     rhs.k.reset();
140     moveCount++;
141     return *this;
142   }
143 
operator ==__anon70451cfd0111::S144   bool operator==(const S& rhs) const { return j == rhs.j && *k == *rhs.k; }
145 
146   S(const S&) = delete;
147   S& operator=(const S&) = delete;
148 };
149 
150 size_t S::constructCount = 0;
151 size_t S::moveCount = 0;
152 size_t S::destructCount = 0;
153 
154 }  // namespace
155 
testEmplaceBack()156 void mozilla::detail::VectorTesting::testEmplaceBack() {
157   S::resetCounts();
158 
159   Vector<S> vec;
160   MOZ_RELEASE_ASSERT(vec.reserve(20));
161 
162   for (size_t i = 0; i < 10; i++) {
163     S s(i, i * i);
164     MOZ_RELEASE_ASSERT(vec.append(std::move(s)));
165   }
166 
167   MOZ_RELEASE_ASSERT(vec.length() == 10);
168   MOZ_RELEASE_ASSERT(S::constructCount == 10);
169   MOZ_RELEASE_ASSERT(S::moveCount == 10);
170 
171   for (size_t i = 10; i < 20; i++) {
172     MOZ_RELEASE_ASSERT(vec.emplaceBack(i, i * i));
173   }
174 
175   MOZ_RELEASE_ASSERT(vec.length() == 20);
176   MOZ_RELEASE_ASSERT(S::constructCount == 20);
177   MOZ_RELEASE_ASSERT(S::moveCount == 10);
178 
179   for (size_t i = 0; i < 20; i++) {
180     MOZ_RELEASE_ASSERT(vec[i].j == i);
181     MOZ_RELEASE_ASSERT(*vec[i].k == i * i);
182   }
183 }
184 
testReverse()185 void mozilla::detail::VectorTesting::testReverse() {
186   // Use UniquePtr to make sure that reverse() can handler move-only types.
187   Vector<UniquePtr<uint8_t>, 0> vec;
188 
189   // Reverse an odd number of elements.
190 
191   for (uint8_t i = 0; i < 5; i++) {
192     auto p = MakeUnique<uint8_t>(i);
193     MOZ_RELEASE_ASSERT(p);
194     MOZ_RELEASE_ASSERT(vec.append(std::move(p)));
195   }
196 
197   vec.reverse();
198 
199   MOZ_RELEASE_ASSERT(*vec[0] == 4);
200   MOZ_RELEASE_ASSERT(*vec[1] == 3);
201   MOZ_RELEASE_ASSERT(*vec[2] == 2);
202   MOZ_RELEASE_ASSERT(*vec[3] == 1);
203   MOZ_RELEASE_ASSERT(*vec[4] == 0);
204 
205   // Reverse an even number of elements.
206 
207   vec.popBack();
208   vec.reverse();
209 
210   MOZ_RELEASE_ASSERT(*vec[0] == 1);
211   MOZ_RELEASE_ASSERT(*vec[1] == 2);
212   MOZ_RELEASE_ASSERT(*vec[2] == 3);
213   MOZ_RELEASE_ASSERT(*vec[3] == 4);
214 
215   // Reverse an empty vector.
216 
217   vec.clear();
218   MOZ_RELEASE_ASSERT(vec.length() == 0);
219   vec.reverse();
220   MOZ_RELEASE_ASSERT(vec.length() == 0);
221 
222   // Reverse a vector using only inline storage.
223 
224   Vector<UniquePtr<uint8_t>, 5> vec2;
225   for (uint8_t i = 0; i < 5; i++) {
226     auto p = MakeUnique<uint8_t>(i);
227     MOZ_RELEASE_ASSERT(p);
228     MOZ_RELEASE_ASSERT(vec2.append(std::move(p)));
229   }
230 
231   vec2.reverse();
232 
233   MOZ_RELEASE_ASSERT(*vec2[0] == 4);
234   MOZ_RELEASE_ASSERT(*vec2[1] == 3);
235   MOZ_RELEASE_ASSERT(*vec2[2] == 2);
236   MOZ_RELEASE_ASSERT(*vec2[3] == 1);
237   MOZ_RELEASE_ASSERT(*vec2[4] == 0);
238 }
239 
testExtractRawBuffer()240 void mozilla::detail::VectorTesting::testExtractRawBuffer() {
241   S::resetCounts();
242 
243   Vector<S, 5> vec;
244   MOZ_RELEASE_ASSERT(vec.reserve(5));
245   for (size_t i = 0; i < 5; i++) {
246     vec.infallibleEmplaceBack(i, i * i);
247   }
248   MOZ_RELEASE_ASSERT(vec.length() == 5);
249   MOZ_ASSERT(vec.reserved() == 5);
250   MOZ_RELEASE_ASSERT(S::constructCount == 5);
251   MOZ_RELEASE_ASSERT(S::moveCount == 0);
252   MOZ_RELEASE_ASSERT(S::destructCount == 0);
253 
254   S* buf = vec.extractRawBuffer();
255   MOZ_RELEASE_ASSERT(!buf);
256   MOZ_RELEASE_ASSERT(vec.length() == 5);
257   MOZ_ASSERT(vec.reserved() == 5);
258   MOZ_RELEASE_ASSERT(S::constructCount == 5);
259   MOZ_RELEASE_ASSERT(S::moveCount == 0);
260   MOZ_RELEASE_ASSERT(S::destructCount == 0);
261 
262   MOZ_RELEASE_ASSERT(vec.reserve(10));
263   for (size_t i = 5; i < 10; i++) {
264     vec.infallibleEmplaceBack(i, i * i);
265   }
266   MOZ_RELEASE_ASSERT(vec.length() == 10);
267   MOZ_ASSERT(vec.reserved() == 10);
268   MOZ_RELEASE_ASSERT(S::constructCount == 10);
269   MOZ_RELEASE_ASSERT(S::moveCount == 5);
270   MOZ_RELEASE_ASSERT(S::destructCount == 5);
271 
272   buf = vec.extractRawBuffer();
273   MOZ_RELEASE_ASSERT(buf);
274   MOZ_RELEASE_ASSERT(vec.length() == 0);
275   MOZ_ASSERT(vec.reserved() == 0);
276   MOZ_RELEASE_ASSERT(S::constructCount == 10);
277   MOZ_RELEASE_ASSERT(S::moveCount == 5);
278   MOZ_RELEASE_ASSERT(S::destructCount == 5);
279 
280   for (size_t i = 0; i < 10; i++) {
281     MOZ_RELEASE_ASSERT(buf[i].j == i);
282     MOZ_RELEASE_ASSERT(*buf[i].k == i * i);
283   }
284 
285   free(buf);
286 }
287 
testExtractOrCopyRawBuffer()288 void mozilla::detail::VectorTesting::testExtractOrCopyRawBuffer() {
289   S::resetCounts();
290 
291   Vector<S, 5> vec;
292   MOZ_RELEASE_ASSERT(vec.reserve(5));
293   for (size_t i = 0; i < 5; i++) {
294     vec.infallibleEmplaceBack(i, i * i);
295   }
296   MOZ_RELEASE_ASSERT(vec.length() == 5);
297   MOZ_ASSERT(vec.reserved() == 5);
298   MOZ_RELEASE_ASSERT(S::constructCount == 5);
299   MOZ_RELEASE_ASSERT(S::moveCount == 0);
300   MOZ_RELEASE_ASSERT(S::destructCount == 0);
301 
302   S* buf = vec.extractOrCopyRawBuffer();
303   MOZ_RELEASE_ASSERT(buf);
304   MOZ_RELEASE_ASSERT(vec.length() == 0);
305   MOZ_ASSERT(vec.reserved() == 0);
306   MOZ_RELEASE_ASSERT(S::constructCount == 5);
307   MOZ_RELEASE_ASSERT(S::moveCount == 5);
308   MOZ_RELEASE_ASSERT(S::destructCount == 5);
309 
310   for (size_t i = 0; i < 5; i++) {
311     MOZ_RELEASE_ASSERT(buf[i].j == i);
312     MOZ_RELEASE_ASSERT(*buf[i].k == i * i);
313   }
314 
315   S::resetCounts();
316 
317   MOZ_RELEASE_ASSERT(vec.reserve(10));
318   for (size_t i = 0; i < 10; i++) {
319     vec.infallibleEmplaceBack(i, i * i);
320   }
321   MOZ_RELEASE_ASSERT(vec.length() == 10);
322   MOZ_ASSERT(vec.reserved() == 10);
323   MOZ_RELEASE_ASSERT(S::constructCount == 10);
324   MOZ_RELEASE_ASSERT(S::moveCount == 0);
325   MOZ_RELEASE_ASSERT(S::destructCount == 0);
326 
327   buf = vec.extractOrCopyRawBuffer();
328   MOZ_RELEASE_ASSERT(buf);
329   MOZ_RELEASE_ASSERT(vec.length() == 0);
330   MOZ_ASSERT(vec.reserved() == 0);
331   MOZ_RELEASE_ASSERT(S::constructCount == 10);
332   MOZ_RELEASE_ASSERT(S::moveCount == 0);
333   MOZ_RELEASE_ASSERT(S::destructCount == 0);
334 
335   for (size_t i = 0; i < 10; i++) {
336     MOZ_RELEASE_ASSERT(buf[i].j == i);
337     MOZ_RELEASE_ASSERT(*buf[i].k == i * i);
338   }
339 
340   free(buf);
341 }
342 
testReplaceRawBuffer()343 void mozilla::detail::VectorTesting::testReplaceRawBuffer() {
344   S::resetCounts();
345 
346   S* s = nullptr;
347 
348   {
349     Vector<S> v;
350     MOZ_RELEASE_ASSERT(v.reserve(4));
351     v.infallibleEmplaceBack(1, 2);
352     v.infallibleEmplaceBack(3, 4);
353     MOZ_ASSERT(S::constructCount == 2);
354     s = v.extractRawBuffer();
355   }
356 
357   MOZ_ASSERT(S::constructCount == 2);
358   MOZ_ASSERT(S::moveCount == 0);
359   MOZ_ASSERT(S::destructCount == 0);
360 
361   {
362     Vector<S, 10> v;
363     v.replaceRawBuffer(s, 2);
364     MOZ_ASSERT(v.length() == 2);
365     MOZ_ASSERT(v.reserved() == 2);
366     MOZ_ASSERT(v.capacity() == 10);
367     MOZ_ASSERT(v[0].j == 1);
368     MOZ_ASSERT(v[1].j == 3);
369     MOZ_ASSERT(S::destructCount == 2);
370   }
371 
372   MOZ_ASSERT(S::constructCount == 2);
373   MOZ_ASSERT(S::moveCount == 2);
374   MOZ_ASSERT(S::destructCount == 4);
375 
376   S::resetCounts();
377 
378   {
379     Vector<S, 2> v;
380     MOZ_RELEASE_ASSERT(v.reserve(4));
381     v.infallibleEmplaceBack(9, 10);
382     MOZ_ASSERT(S::constructCount == 1);
383     s = v.extractRawBuffer();
384     MOZ_ASSERT(S::constructCount == 1);
385     MOZ_ASSERT(S::moveCount == 0);
386   }
387 
388   MOZ_ASSERT(S::destructCount == 0);
389 
390   {
391     Vector<S> v;
392     v.replaceRawBuffer(s, 1, 4);
393     MOZ_ASSERT(v.length() == 1);
394     MOZ_ASSERT(v.reserved() == 4);
395     MOZ_ASSERT(v.capacity() == 4);
396     MOZ_ASSERT(v[0].j == 9);
397     for (size_t i = 0; i < 5; i++) MOZ_RELEASE_ASSERT(v.emplaceBack(i, i));
398     MOZ_ASSERT(v.length() == 6);
399     MOZ_ASSERT(v.reserved() == 6);
400     MOZ_ASSERT(S::constructCount == 6);
401     MOZ_ASSERT(S::moveCount == 4);
402     MOZ_ASSERT(S::destructCount == 4);
403   }
404 
405   MOZ_ASSERT(S::destructCount == 10);
406 }
407 
testInsert()408 void mozilla::detail::VectorTesting::testInsert() {
409   S::resetCounts();
410 
411   Vector<S, 8> vec;
412   MOZ_RELEASE_ASSERT(vec.reserve(8));
413   for (size_t i = 0; i < 7; i++) {
414     vec.infallibleEmplaceBack(i, i * i);
415   }
416 
417   MOZ_RELEASE_ASSERT(vec.length() == 7);
418   MOZ_ASSERT(vec.reserved() == 8);
419   MOZ_RELEASE_ASSERT(S::constructCount == 7);
420   MOZ_RELEASE_ASSERT(S::moveCount == 0);
421   MOZ_RELEASE_ASSERT(S::destructCount == 0);
422 
423   S s(42, 43);
424   MOZ_RELEASE_ASSERT(vec.insert(vec.begin() + 4, std::move(s)));
425 
426   for (size_t i = 0; i < vec.length(); i++) {
427     const S& s = vec[i];
428     MOZ_RELEASE_ASSERT(s.k);
429     if (i < 4) {
430       MOZ_RELEASE_ASSERT(s.j == i && *s.k == i * i);
431     } else if (i == 4) {
432       MOZ_RELEASE_ASSERT(s.j == 42 && *s.k == 43);
433     } else {
434       MOZ_RELEASE_ASSERT(s.j == i - 1 && *s.k == (i - 1) * (i - 1));
435     }
436   }
437 
438   MOZ_RELEASE_ASSERT(vec.length() == 8);
439   MOZ_ASSERT(vec.reserved() == 8);
440   MOZ_RELEASE_ASSERT(S::constructCount == 8);
441   MOZ_RELEASE_ASSERT(S::moveCount == 1 /* move in insert() call */ +
442                                          1 /* move the back() element */ +
443                                          3 /* elements to shift */);
444   MOZ_RELEASE_ASSERT(S::destructCount == 1);
445 }
446 
testErase()447 void mozilla::detail::VectorTesting::testErase() {
448   S::resetCounts();
449 
450   Vector<S, 8> vec;
451   MOZ_RELEASE_ASSERT(vec.reserve(8));
452   for (size_t i = 0; i < 7; i++) {
453     vec.infallibleEmplaceBack(i, i * i);
454   }
455 
456   // vec: [0, 1, 2, 3, 4, 5, 6]
457   MOZ_RELEASE_ASSERT(vec.length() == 7);
458   MOZ_ASSERT(vec.reserved() == 8);
459   MOZ_RELEASE_ASSERT(S::constructCount == 7);
460   MOZ_RELEASE_ASSERT(S::moveCount == 0);
461   MOZ_RELEASE_ASSERT(S::destructCount == 0);
462   S::resetCounts();
463 
464   vec.erase(&vec[4]);
465   // vec: [0, 1, 2, 3, 5, 6]
466   MOZ_RELEASE_ASSERT(vec.length() == 6);
467   MOZ_ASSERT(vec.reserved() == 8);
468   MOZ_RELEASE_ASSERT(S::constructCount == 0);
469   // 5 and 6 should have been moved into 4 and 5.
470   MOZ_RELEASE_ASSERT(S::moveCount == 2);
471   MOZ_RELEASE_ASSERT(S::destructCount == 1);
472   MOZ_RELEASE_ASSERT(vec[4] == S(5, 5 * 5));
473   MOZ_RELEASE_ASSERT(vec[5] == S(6, 6 * 6));
474   S::resetCounts();
475 
476   vec.erase(&vec[3], &vec[5]);
477   // vec: [0, 1, 2, 6]
478   MOZ_RELEASE_ASSERT(vec.length() == 4);
479   MOZ_ASSERT(vec.reserved() == 8);
480   MOZ_RELEASE_ASSERT(S::constructCount == 0);
481   // 6 should have been moved into 3.
482   MOZ_RELEASE_ASSERT(S::moveCount == 1);
483   MOZ_RELEASE_ASSERT(S::destructCount == 2);
484   MOZ_RELEASE_ASSERT(vec[3] == S(6, 6 * 6));
485 
486   S s2(2, 2 * 2);
487   S::resetCounts();
488 
489   vec.eraseIfEqual(s2);
490   // vec: [0, 1, 6]
491   MOZ_RELEASE_ASSERT(vec.length() == 3);
492   MOZ_ASSERT(vec.reserved() == 8);
493   MOZ_RELEASE_ASSERT(S::constructCount == 0);
494   // 6 should have been moved into 2.
495   MOZ_RELEASE_ASSERT(S::moveCount == 1);
496   MOZ_RELEASE_ASSERT(S::destructCount == 1);
497   MOZ_RELEASE_ASSERT(vec[2] == S(6, 6 * 6));
498   S::resetCounts();
499 
500   // Predicate to find one element.
501   vec.eraseIf([](const S& s) { return s.j == 1; });
502   // vec: [0, 6]
503   MOZ_RELEASE_ASSERT(vec.length() == 2);
504   MOZ_ASSERT(vec.reserved() == 8);
505   MOZ_RELEASE_ASSERT(S::constructCount == 0);
506   // 6 should have been moved into 1.
507   MOZ_RELEASE_ASSERT(S::moveCount == 1);
508   MOZ_RELEASE_ASSERT(S::destructCount == 1);
509   MOZ_RELEASE_ASSERT(vec[1] == S(6, 6 * 6));
510   S::resetCounts();
511 
512   // Generic predicate that flags everything.
513   vec.eraseIf([](auto&&) { return true; });
514   // vec: []
515   MOZ_RELEASE_ASSERT(vec.length() == 0);
516   MOZ_ASSERT(vec.reserved() == 8);
517   MOZ_RELEASE_ASSERT(S::constructCount == 0);
518   MOZ_RELEASE_ASSERT(S::moveCount == 0);
519   MOZ_RELEASE_ASSERT(S::destructCount == 2);
520 
521   for (size_t i = 0; i < 7; i++) {
522     vec.infallibleEmplaceBack(i, i * i);
523   }
524   // vec: [0, 1, 2, 3, 4, 5, 6]
525   MOZ_RELEASE_ASSERT(vec.length() == 7);
526   S::resetCounts();
527 
528   // Predicate that flags all even numbers.
529   vec.eraseIf([](const S& s) { return s.j % 2 == 0; });
530   // vec: [1 (was 0), 3 (was 1), 5 (was 2)]
531   MOZ_RELEASE_ASSERT(vec.length() == 3);
532   MOZ_ASSERT(vec.reserved() == 8);
533   MOZ_RELEASE_ASSERT(S::constructCount == 0);
534   MOZ_RELEASE_ASSERT(S::moveCount == 3);
535   MOZ_RELEASE_ASSERT(S::destructCount == 4);
536 }
537 
testShrinkStorageToFit()538 void mozilla::detail::VectorTesting::testShrinkStorageToFit() {
539   // Vectors not using inline storage realloc capacity to exact length.
540   {
541     Vector<int, 0> v1;
542     MOZ_RELEASE_ASSERT(v1.reserve(10));
543     v1.infallibleAppend(1);
544     MOZ_ASSERT(v1.length() == 1);
545     MOZ_ASSERT(v1.reserved() == 10);
546     MOZ_ASSERT(v1.capacity() >= 10);
547     v1.shrinkStorageToFit();
548     MOZ_ASSERT(v1.length() == 1);
549     MOZ_ASSERT(v1.reserved() == 1);
550     MOZ_ASSERT(v1.capacity() == 1);
551   }
552 
553   // Vectors using inline storage do nothing.
554   {
555     Vector<int, 2> v2;
556     MOZ_RELEASE_ASSERT(v2.reserve(2));
557     v2.infallibleAppend(1);
558     MOZ_ASSERT(v2.length() == 1);
559     MOZ_ASSERT(v2.reserved() == 2);
560     MOZ_ASSERT(v2.capacity() == 2);
561     v2.shrinkStorageToFit();
562     MOZ_ASSERT(v2.length() == 1);
563     MOZ_ASSERT(v2.reserved() == 2);
564     MOZ_ASSERT(v2.capacity() == 2);
565   }
566 
567   // shrinkStorageToFit uses inline storage if possible.
568   {
569     Vector<int, 2> v;
570     MOZ_RELEASE_ASSERT(v.reserve(4));
571     v.infallibleAppend(1);
572     MOZ_ASSERT(v.length() == 1);
573     MOZ_ASSERT(v.reserved() == 4);
574     MOZ_ASSERT(v.capacity() >= 4);
575     v.shrinkStorageToFit();
576     MOZ_ASSERT(v.length() == 1);
577     MOZ_ASSERT(v.reserved() == 1);
578     MOZ_ASSERT(v.capacity() == 2);
579   }
580 
581   // Non-pod shrinking to non-inline storage.
582   {
583     static size_t sConstructCounter = 0;
584     static size_t sCopyCounter = 0;
585     static size_t sMoveCounter = 0;
586     static size_t sDestroyCounter = 0;
587     struct NonPod {
588       int mSomething = 10;
589 
590       NonPod() { sConstructCounter++; }
591 
592       NonPod(const NonPod& aOther) : mSomething(aOther.mSomething) {
593         sCopyCounter++;
594       }
595       NonPod(NonPod&& aOther) : mSomething(aOther.mSomething) {
596         sMoveCounter++;
597       }
598       ~NonPod() { sDestroyCounter++; }
599     };
600 
601     Vector<NonPod, 5> v;
602     MOZ_RELEASE_ASSERT(v.reserve(10));
603     for (size_t i = 0; i < 8; ++i) {
604       v.infallibleEmplaceBack();
605     }
606     MOZ_RELEASE_ASSERT(sConstructCounter == 8);
607     MOZ_RELEASE_ASSERT(sCopyCounter == 0);
608     MOZ_RELEASE_ASSERT(sMoveCounter == 0);
609     MOZ_RELEASE_ASSERT(sDestroyCounter == 0);
610     MOZ_RELEASE_ASSERT(v.length() == 8);
611     MOZ_ASSERT(v.reserved() == 10);
612     MOZ_RELEASE_ASSERT(v.capacity() >= 10);
613     MOZ_RELEASE_ASSERT(v.shrinkStorageToFit());
614 
615     MOZ_RELEASE_ASSERT(sConstructCounter == 8);
616     MOZ_RELEASE_ASSERT(sCopyCounter == 0);
617     MOZ_RELEASE_ASSERT(sMoveCounter == 8);
618     MOZ_RELEASE_ASSERT(sDestroyCounter == 8);
619     MOZ_RELEASE_ASSERT(v.length() == 8);
620     MOZ_ASSERT(v.reserved() == 8);
621     MOZ_RELEASE_ASSERT(v.capacity() == 8);
622   }
623 
624   // Non-POD shrinking to inline storage.
625   {
626     static size_t sConstructCounter = 0;
627     static size_t sCopyCounter = 0;
628     static size_t sMoveCounter = 0;
629     static size_t sDestroyCounter = 0;
630     struct NonPod {
631       int mSomething = 10;
632 
633       NonPod() { sConstructCounter++; }
634 
635       NonPod(const NonPod& aOther) : mSomething(aOther.mSomething) {
636         sCopyCounter++;
637       }
638       NonPod(NonPod&& aOther) : mSomething(aOther.mSomething) {
639         sMoveCounter++;
640       }
641       ~NonPod() { sDestroyCounter++; }
642     };
643 
644     Vector<NonPod, 5> v;
645     MOZ_RELEASE_ASSERT(v.reserve(10));
646     for (size_t i = 0; i < 3; ++i) {
647       v.infallibleEmplaceBack();
648     }
649     MOZ_RELEASE_ASSERT(sConstructCounter == 3);
650     MOZ_RELEASE_ASSERT(sCopyCounter == 0);
651     MOZ_RELEASE_ASSERT(sMoveCounter == 0);
652     MOZ_RELEASE_ASSERT(sDestroyCounter == 0);
653     MOZ_RELEASE_ASSERT(v.length() == 3);
654     MOZ_ASSERT(v.reserved() == 10);
655     MOZ_RELEASE_ASSERT(v.capacity() >= 10);
656     MOZ_RELEASE_ASSERT(v.shrinkStorageToFit());
657 
658     MOZ_RELEASE_ASSERT(sConstructCounter == 3);
659     MOZ_RELEASE_ASSERT(sCopyCounter == 0);
660     MOZ_RELEASE_ASSERT(sMoveCounter == 3);
661     MOZ_RELEASE_ASSERT(sDestroyCounter == 3);
662     MOZ_RELEASE_ASSERT(v.length() == 3);
663     MOZ_ASSERT(v.reserved() == 3);
664     MOZ_RELEASE_ASSERT(v.capacity() == 5);
665   }
666 }
667 
testAppend()668 void mozilla::detail::VectorTesting::testAppend() {
669   // Test moving append/appendAll with a move-only type
670   Vector<UniquePtr<int>> bv;
671   for (const int val : IntegerRange<int>(0, 3)) {
672     MOZ_RELEASE_ASSERT(bv.append(MakeUnique<int>(val)));
673   }
674 
675   Vector<UniquePtr<int>> otherbv;
676   for (const int val : IntegerRange<int>(3, 8)) {
677     MOZ_RELEASE_ASSERT(otherbv.append(MakeUnique<int>(val)));
678   }
679   MOZ_RELEASE_ASSERT(bv.appendAll(std::move(otherbv)));
680 
681   MOZ_RELEASE_ASSERT(otherbv.length() == 0);
682   MOZ_RELEASE_ASSERT(bv.length() == 8);
683   for (const int val : IntegerRange<int>(0, 8)) {
684     MOZ_RELEASE_ASSERT(*bv[val] == val);
685   }
686 }
687 
688 // Declare but leave (permanently) incomplete.
689 struct Incomplete;
690 
691 // We could even *construct* a Vector<Incomplete, 0> if we wanted.  But we can't
692 // destruct it, so it's not worth the trouble.
693 static_assert(sizeof(Vector<Incomplete, 0>) > 0,
694               "Vector of an incomplete type will compile");
695 
696 // Vector with no inline storage should occupy the absolute minimum space in
697 // non-debug builds.  (Debug adds a laundry list of other constraints, none
698 // directly relevant to shipping builds, that aren't worth precisely modeling.)
699 #ifndef DEBUG
700 
701 template <typename T>
702 struct NoInlineStorageLayout {
703   T* mBegin;
704   size_t mLength;
705   struct CRAndStorage {
706     size_t mCapacity;
707   } mTail;
708 };
709 
710 // Only one of these should be necessary, but test a few of them for good
711 // measure.
712 static_assert(sizeof(Vector<int, 0>) == sizeof(NoInlineStorageLayout<int>),
713               "Vector of int without inline storage shouldn't occupy dead "
714               "space for that absence of storage");
715 
716 static_assert(sizeof(Vector<bool, 0>) == sizeof(NoInlineStorageLayout<bool>),
717               "Vector of bool without inline storage shouldn't occupy dead "
718               "space for that absence of storage");
719 
720 static_assert(sizeof(Vector<S, 0>) == sizeof(NoInlineStorageLayout<S>),
721               "Vector of S without inline storage shouldn't occupy dead "
722               "space for that absence of storage");
723 
724 static_assert(sizeof(Vector<Incomplete, 0>) ==
725                   sizeof(NoInlineStorageLayout<Incomplete>),
726               "Vector of an incomplete class without inline storage shouldn't "
727               "occupy dead space for that absence of storage");
728 
729 #endif  // DEBUG
730 
TestVectorBeginNonNull()731 static void TestVectorBeginNonNull() {
732   // Vector::begin() should never return nullptr, to accommodate callers that
733   // (either for hygiene, or for semantic reasons) need a non-null pointer even
734   // for zero elements.
735 
736   Vector<bool, 0> bvec0;
737   MOZ_RELEASE_ASSERT(bvec0.length() == 0);
738   MOZ_RELEASE_ASSERT(bvec0.begin() != nullptr);
739 
740   Vector<bool, 1> bvec1;
741   MOZ_RELEASE_ASSERT(bvec1.length() == 0);
742   MOZ_RELEASE_ASSERT(bvec1.begin() != nullptr);
743 
744   Vector<bool, 64> bvec64;
745   MOZ_RELEASE_ASSERT(bvec64.length() == 0);
746   MOZ_RELEASE_ASSERT(bvec64.begin() != nullptr);
747 
748   Vector<int, 0> ivec0;
749   MOZ_RELEASE_ASSERT(ivec0.length() == 0);
750   MOZ_RELEASE_ASSERT(ivec0.begin() != nullptr);
751 
752   Vector<int, 1> ivec1;
753   MOZ_RELEASE_ASSERT(ivec1.length() == 0);
754   MOZ_RELEASE_ASSERT(ivec1.begin() != nullptr);
755 
756   Vector<int, 64> ivec64;
757   MOZ_RELEASE_ASSERT(ivec64.length() == 0);
758   MOZ_RELEASE_ASSERT(ivec64.begin() != nullptr);
759 
760   Vector<long, 0> lvec0;
761   MOZ_RELEASE_ASSERT(lvec0.length() == 0);
762   MOZ_RELEASE_ASSERT(lvec0.begin() != nullptr);
763 
764   Vector<long, 1> lvec1;
765   MOZ_RELEASE_ASSERT(lvec1.length() == 0);
766   MOZ_RELEASE_ASSERT(lvec1.begin() != nullptr);
767 
768   Vector<long, 64> lvec64;
769   MOZ_RELEASE_ASSERT(lvec64.length() == 0);
770   MOZ_RELEASE_ASSERT(lvec64.begin() != nullptr);
771 
772   // Vector<T, N> doesn't guarantee N inline elements -- the actual count is
773   // capped so that any Vector fits in a not-crazy amount of space -- so the
774   // code below won't overflow stacks or anything crazy.
775   struct VeryBig {
776     int array[16 * 1024 * 1024];
777   };
778 
779   Vector<VeryBig, 0> vbvec0;
780   MOZ_RELEASE_ASSERT(vbvec0.length() == 0);
781   MOZ_RELEASE_ASSERT(vbvec0.begin() != nullptr);
782 
783   Vector<VeryBig, 1> vbvec1;
784   MOZ_RELEASE_ASSERT(vbvec1.length() == 0);
785   MOZ_RELEASE_ASSERT(vbvec1.begin() != nullptr);
786 
787   Vector<VeryBig, 64> vbvec64;
788   MOZ_RELEASE_ASSERT(vbvec64.length() == 0);
789   MOZ_RELEASE_ASSERT(vbvec64.begin() != nullptr);
790 }
791 
main()792 int main() {
793   VectorTesting::testReserved();
794   VectorTesting::testConstRange();
795   VectorTesting::testEmplaceBack();
796   VectorTesting::testReverse();
797   VectorTesting::testExtractRawBuffer();
798   VectorTesting::testExtractOrCopyRawBuffer();
799   VectorTesting::testReplaceRawBuffer();
800   VectorTesting::testInsert();
801   VectorTesting::testErase();
802   VectorTesting::testShrinkStorageToFit();
803   VectorTesting::testAppend();
804   TestVectorBeginNonNull();
805 }
806