mfbt/tests/TestVector.cpp

   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
  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
  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
 119   static void resetCounts() {
 120     constructCount = 0;
 121     moveCount = 0;
 122     destructCount = 0;
 123   }
 124
 125   S(size_t j, size_t k) : j(j), k(MakeUnique<size_t>(k)) { constructCount++; }
 126
 127   S(S&& rhs) : j(rhs.j), k(std::move(rhs.k)) {
 128     rhs.j = 0;
 129     rhs.k.reset(0);
 130     moveCount++;
 131   }
 132
 133   ~S() { destructCount++; }
 134
 135   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
 144   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
 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
 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
 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
 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
 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
 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
 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
 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
 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 // Vector with no inline storage should occupy the absolute minimum space in
 689 // non-debug builds.  (Debug adds a laundry list of other constraints, none
 690 // directly relevant to shipping builds, that aren't worth precisely modeling.)
 691 #ifndef DEBUG
 692
 693 template <typename T>
 694 struct NoInlineStorageLayout {
 695   T* mBegin;
 696   size_t mLength;
 697   struct CRAndStorage {
 698     size_t mCapacity;
 699   } mTail;
 700 };
 701
 702 // Only one of these should be necessary, but test a few of them for good
 703 // measure.
 704 static_assert(sizeof(Vector<int, 0>) == sizeof(NoInlineStorageLayout<int>),
 705               "Vector of int without inline storage shouldn't occupy dead "
 706               "space for that absence of storage");
 707
 708 static_assert(sizeof(Vector<bool, 0>) == sizeof(NoInlineStorageLayout<bool>),
 709               "Vector of bool without inline storage shouldn't occupy dead "
 710               "space for that absence of storage");
 711
 712 static_assert(sizeof(Vector<S, 0>) == sizeof(NoInlineStorageLayout<S>),
 713               "Vector of S without inline storage shouldn't occupy dead "
 714               "space for that absence of storage");
 715
 716 #endif  // DEBUG
 717
 718 static void TestVectorBeginNonNull() {
 719   // Vector::begin() should never return nullptr, to accommodate callers that
 720   // (either for hygiene, or for semantic reasons) need a non-null pointer even
 721   // for zero elements.
 722
 723   Vector<bool, 0> bvec0;
 724   MOZ_RELEASE_ASSERT(bvec0.length() == 0);
 725   MOZ_RELEASE_ASSERT(bvec0.begin() != nullptr);
 726
 727   Vector<bool, 1> bvec1;
 728   MOZ_RELEASE_ASSERT(bvec1.length() == 0);
 729   MOZ_RELEASE_ASSERT(bvec1.begin() != nullptr);
 730
 731   Vector<bool, 64> bvec64;
 732   MOZ_RELEASE_ASSERT(bvec64.length() == 0);
 733   MOZ_RELEASE_ASSERT(bvec64.begin() != nullptr);
 734
 735   Vector<int, 0> ivec0;
 736   MOZ_RELEASE_ASSERT(ivec0.length() == 0);
 737   MOZ_RELEASE_ASSERT(ivec0.begin() != nullptr);
 738
 739   Vector<int, 1> ivec1;
 740   MOZ_RELEASE_ASSERT(ivec1.length() == 0);
 741   MOZ_RELEASE_ASSERT(ivec1.begin() != nullptr);
 742
 743   Vector<int, 64> ivec64;
 744   MOZ_RELEASE_ASSERT(ivec64.length() == 0);
 745   MOZ_RELEASE_ASSERT(ivec64.begin() != nullptr);
 746
 747   Vector<long, 0> lvec0;
 748   MOZ_RELEASE_ASSERT(lvec0.length() == 0);
 749   MOZ_RELEASE_ASSERT(lvec0.begin() != nullptr);
 750
 751   Vector<long, 1> lvec1;
 752   MOZ_RELEASE_ASSERT(lvec1.length() == 0);
 753   MOZ_RELEASE_ASSERT(lvec1.begin() != nullptr);
 754
 755   Vector<long, 64> lvec64;
 756   MOZ_RELEASE_ASSERT(lvec64.length() == 0);
 757   MOZ_RELEASE_ASSERT(lvec64.begin() != nullptr);
 758
 759   // Vector<T, N> doesn't guarantee N inline elements -- the actual count is
 760   // capped so that any Vector fits in a not-crazy amount of space -- so the
 761   // code below won't overflow stacks or anything crazy.
 762   struct VeryBig {
 763     int array[16 * 1024 * 1024];
 764   };
 765
 766   Vector<VeryBig, 0> vbvec0;
 767   MOZ_RELEASE_ASSERT(vbvec0.length() == 0);
 768   MOZ_RELEASE_ASSERT(vbvec0.begin() != nullptr);
 769
 770   Vector<VeryBig, 1> vbvec1;
 771   MOZ_RELEASE_ASSERT(vbvec1.length() == 0);
 772   MOZ_RELEASE_ASSERT(vbvec1.begin() != nullptr);
 773
 774   Vector<VeryBig, 64> vbvec64;
 775   MOZ_RELEASE_ASSERT(vbvec64.length() == 0);
 776   MOZ_RELEASE_ASSERT(vbvec64.begin() != nullptr);
 777 }
 778
 779 int main() {
 780   VectorTesting::testReserved();
 781   VectorTesting::testConstRange();
 782   VectorTesting::testEmplaceBack();
 783   VectorTesting::testReverse();
 784   VectorTesting::testExtractRawBuffer();
 785   VectorTesting::testExtractOrCopyRawBuffer();
 786   VectorTesting::testReplaceRawBuffer();
 787   VectorTesting::testInsert();
 788   VectorTesting::testErase();
 789   VectorTesting::testShrinkStorageToFit();
 790   VectorTesting::testAppend();
 791   TestVectorBeginNonNull();
 792 }