xpcom/tests/gtest/TestTArray2.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
   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
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "mozilla/ArrayUtils.h"
   8 #include "mozilla/Unused.h"
   9 #include "mozilla/TimeStamp.h"
  10
  11 #include <stdlib.h>
  12 #include <stdio.h>
  13 #include <iostream>
  14 #include "nsTArray.h"
  15 #include "nsString.h"
  16 #include "nsDirectoryServiceDefs.h"
  17 #include "nsDirectoryServiceUtils.h"
  18 #include "nsComponentManagerUtils.h"
  19 #include "nsXPCOM.h"
  20 #include "nsIFile.h"
  21
  22 #include "gtest/gtest.h"
  23 #include "mozilla/gtest/MozAssertions.h"
  24
  25 using namespace mozilla;
  26
  27 namespace TestTArray {
  28
  29 // Define this so we can use test_basic_array in test_comptr_array
  30 template <class T>
  31 inline bool operator<(const nsCOMPtr<T>& lhs, const nsCOMPtr<T>& rhs) {
  32   return lhs.get() < rhs.get();
  33 }
  34
  35 //----
  36
  37 template <class ElementType>
  38 static bool test_basic_array(ElementType* data, size_t dataLen,
  39                              const ElementType& extra) {
  40   CopyableTArray<ElementType> ary;
  41   const nsTArray<ElementType>& cary = ary;
  42
  43   ary.AppendElements(data, dataLen);
  44   if (ary.Length() != dataLen) {
  45     return false;
  46   }
  47   if (!(ary == ary)) {
  48     return false;
  49   }
  50   size_t i;
  51   for (i = 0; i < ary.Length(); ++i) {
  52     if (ary[i] != data[i]) return false;
  53   }
  54   for (i = 0; i < ary.Length(); ++i) {
  55     if (ary.SafeElementAt(i, extra) != data[i]) return false;
  56   }
  57   if (ary.SafeElementAt(ary.Length(), extra) != extra ||
  58       ary.SafeElementAt(ary.Length() * 10, extra) != extra)
  59     return false;
  60   // ensure sort results in ascending order
  61   ary.Sort();
  62   size_t j = 0, k = ary.IndexOfFirstElementGt(extra);
  63   if (k != 0 && ary[k - 1] == extra) return false;
  64   for (i = 0; i < ary.Length(); ++i) {
  65     k = ary.IndexOfFirstElementGt(ary[i]);
  66     if (k == 0 || ary[k - 1] != ary[i]) return false;
  67     if (k < j) return false;
  68     j = k;
  69   }
  70   for (i = ary.Length(); --i;) {
  71     if (ary[i] < ary[i - 1]) return false;
  72     if (ary[i] == ary[i - 1]) ary.RemoveElementAt(i);
  73   }
  74   if (!(ary == ary)) {
  75     return false;
  76   }
  77   for (i = 0; i < ary.Length(); ++i) {
  78     if (ary.BinaryIndexOf(ary[i]) != i) return false;
  79   }
  80   if (ary.BinaryIndexOf(extra) != ary.NoIndex) return false;
  81   size_t oldLen = ary.Length();
  82   ary.RemoveElement(data[dataLen / 2]);
  83   if (ary.Length() != (oldLen - 1)) return false;
  84   if (!(ary == ary)) return false;
  85
  86   if (ary.ApplyIf(
  87           extra, []() { return true; }, []() { return false; }))
  88     return false;
  89   if (ary.ApplyIf(
  90           extra, [](size_t) { return true; }, []() { return false; }))
  91     return false;
  92   // On a non-const array, ApplyIf's first lambda may use either const or non-
  93   // const element types.
  94   if (ary.ApplyIf(
  95           extra, [](ElementType&) { return true; }, []() { return false; }))
  96     return false;
  97   if (ary.ApplyIf(
  98           extra, [](const ElementType&) { return true; },
  99           []() { return false; }))
 100     return false;
 101   if (ary.ApplyIf(
 102           extra, [](size_t, ElementType&) { return true; },
 103           []() { return false; }))
 104     return false;
 105   if (ary.ApplyIf(
 106           extra, [](size_t, const ElementType&) { return true; },
 107           []() { return false; }))
 108     return false;
 109
 110   if (cary.ApplyIf(
 111           extra, []() { return true; }, []() { return false; }))
 112     if (cary.ApplyIf(
 113             extra, [](size_t) { return true; }, []() { return false; }))
 114       // On a const array, ApplyIf's first lambda must only use const element
 115       // types.
 116       if (cary.ApplyIf(
 117               extra, [](const ElementType&) { return true; },
 118               []() { return false; }))
 119         if (cary.ApplyIf(
 120                 extra, [](size_t, const ElementType&) { return true; },
 121                 []() { return false; }))
 122           return false;
 123
 124   size_t index = ary.Length() / 2;
 125   ary.InsertElementAt(index, extra);
 126   if (!(ary == ary)) return false;
 127   if (ary[index] != extra) return false;
 128   if (ary.IndexOf(extra) == ary.NoIndex) return false;
 129   if (ary.LastIndexOf(extra) == ary.NoIndex) return false;
 130   // ensure proper searching
 131   if (ary.IndexOf(extra) > ary.LastIndexOf(extra)) return false;
 132   if (ary.IndexOf(extra, index) != ary.LastIndexOf(extra, index)) return false;
 133   if (!ary.ApplyIf(
 134           extra,
 135           [&](size_t i, const ElementType& e) {
 136             return i == index && e == extra;
 137           },
 138           []() { return false; }))
 139     return false;
 140   if (!cary.ApplyIf(
 141           extra,
 142           [&](size_t i, const ElementType& e) {
 143             return i == index && e == extra;
 144           },
 145           []() { return false; }))
 146     return false;
 147
 148   nsTArray<ElementType> copy(ary.Clone());
 149   if (!(ary == copy)) return false;
 150   for (i = 0; i < copy.Length(); ++i) {
 151     if (ary[i] != copy[i]) return false;
 152   }
 153   ary.AppendElements(copy);
 154   size_t cap = ary.Capacity();
 155   ary.RemoveElementsAt(copy.Length(), copy.Length());
 156   ary.Compact();
 157   if (ary.Capacity() == cap) return false;
 158
 159   ary.Clear();
 160   if (ary.IndexOf(extra) != ary.NoIndex) return false;
 161   if (ary.LastIndexOf(extra) != ary.NoIndex) return false;
 162   if (ary.ApplyIf(
 163           extra, []() { return true; }, []() { return false; }))
 164     return false;
 165   if (cary.ApplyIf(
 166           extra, []() { return true; }, []() { return false; }))
 167     return false;
 168
 169   ary.Clear();
 170   if (!ary.IsEmpty()) return false;
 171   if (!(ary == nsTArray<ElementType>())) return false;
 172   if (ary == copy) return false;
 173   if (ary.SafeElementAt(0, extra) != extra ||
 174       ary.SafeElementAt(10, extra) != extra)
 175     return false;
 176
 177   ary = copy;
 178   if (!(ary == copy)) return false;
 179   for (i = 0; i < copy.Length(); ++i) {
 180     if (ary[i] != copy[i]) return false;
 181   }
 182
 183   ary.InsertElementsAt(0, copy);
 184   if (ary == copy) return false;
 185   ary.RemoveElementsAt(0, copy.Length());
 186   for (i = 0; i < copy.Length(); ++i) {
 187     if (ary[i] != copy[i]) return false;
 188   }
 189
 190   // These shouldn't crash!
 191   nsTArray<ElementType> empty;
 192   ary.AppendElements(reinterpret_cast<ElementType*>(0), 0);
 193   ary.AppendElements(empty);
 194
 195   // See bug 324981
 196   ary.RemoveElement(extra);
 197   ary.RemoveElement(extra);
 198
 199   return true;
 200 }
 201
 202 TEST(TArray, test_int_array)
 203 {
 204   int data[] = {4, 6, 8, 2, 4, 1, 5, 7, 3};
 205   ASSERT_TRUE(test_basic_array(data, ArrayLength(data), int(14)));
 206 }
 207
 208 TEST(TArray, test_int64_array)
 209 {
 210   int64_t data[] = {4, 6, 8, 2, 4, 1, 5, 7, 3};
 211   ASSERT_TRUE(test_basic_array(data, ArrayLength(data), int64_t(14)));
 212 }
 213
 214 TEST(TArray, test_char_array)
 215 {
 216   char data[] = {4, 6, 8, 2, 4, 1, 5, 7, 3};
 217   ASSERT_TRUE(test_basic_array(data, ArrayLength(data), char(14)));
 218 }
 219
 220 TEST(TArray, test_uint32_array)
 221 {
 222   uint32_t data[] = {4, 6, 8, 2, 4, 1, 5, 7, 3};
 223   ASSERT_TRUE(test_basic_array(data, ArrayLength(data), uint32_t(14)));
 224 }
 225
 226 //----
 227
 228 class Object {
 229  public:
 230   Object() : mNum(0) {}
 231   Object(const char* str, uint32_t num) : mStr(str), mNum(num) {}
 232   Object(const Object& other) = default;
 233   ~Object() = default;
 234
 235   Object& operator=(const Object& other) = default;
 236
 237   bool operator==(const Object& other) const {
 238     return mStr == other.mStr && mNum == other.mNum;
 239   }
 240
 241   bool operator<(const Object& other) const {
 242     // sort based on mStr only
 243     return Compare(mStr, other.mStr) < 0;
 244   }
 245
 246   const char* Str() const { return mStr.get(); }
 247   uint32_t Num() const { return mNum; }
 248
 249  private:
 250   nsCString mStr;
 251   uint32_t mNum;
 252 };
 253
 254 TEST(TArray, test_object_array)
 255 {
 256   nsTArray<Object> objArray;
 257   const char kdata[] = "hello world";
 258   size_t i;
 259   for (i = 0; i < ArrayLength(kdata); ++i) {
 260     char x[] = {kdata[i], '\0'};
 261     objArray.AppendElement(Object(x, i));
 262   }
 263   for (i = 0; i < ArrayLength(kdata); ++i) {
 264     ASSERT_EQ(objArray[i].Str()[0], kdata[i]);
 265     ASSERT_EQ(objArray[i].Num(), i);
 266   }
 267   objArray.Sort();
 268   const char ksorted[] = "\0 dehllloorw";
 269   for (i = 0; i < ArrayLength(kdata) - 1; ++i) {
 270     ASSERT_EQ(objArray[i].Str()[0], ksorted[i]);
 271   }
 272 }
 273
 274 class Countable {
 275   static int sCount;
 276
 277  public:
 278   Countable() { sCount++; }
 279
 280   Countable(const Countable& aOther) { sCount++; }
 281
 282   static int Count() { return sCount; }
 283 };
 284
 285 class Moveable {
 286   static int sCount;
 287
 288  public:
 289   Moveable() { sCount++; }
 290
 291   Moveable(const Moveable& aOther) { sCount++; }
 292
 293   Moveable(Moveable&& aOther) {
 294     // Do not increment sCount
 295   }
 296
 297   static int Count() { return sCount; }
 298 };
 299
 300 class MoveOnly_RelocateUsingMemutils {
 301  public:
 302   MoveOnly_RelocateUsingMemutils() = default;
 303
 304   MoveOnly_RelocateUsingMemutils(const MoveOnly_RelocateUsingMemutils&) =
 305       delete;
 306   MoveOnly_RelocateUsingMemutils(MoveOnly_RelocateUsingMemutils&&) = default;
 307
 308   MoveOnly_RelocateUsingMemutils& operator=(
 309       const MoveOnly_RelocateUsingMemutils&) = delete;
 310   MoveOnly_RelocateUsingMemutils& operator=(MoveOnly_RelocateUsingMemutils&&) =
 311       default;
 312 };
 313
 314 static_assert(
 315     std::is_move_constructible_v<nsTArray<MoveOnly_RelocateUsingMemutils>>);
 316 static_assert(
 317     std::is_move_assignable_v<nsTArray<MoveOnly_RelocateUsingMemutils>>);
 318 static_assert(
 319     !std::is_copy_constructible_v<nsTArray<MoveOnly_RelocateUsingMemutils>>);
 320 static_assert(
 321     !std::is_copy_assignable_v<nsTArray<MoveOnly_RelocateUsingMemutils>>);
 322
 323 class MoveOnly_RelocateUsingMoveConstructor {
 324  public:
 325   MoveOnly_RelocateUsingMoveConstructor() = default;
 326
 327   MoveOnly_RelocateUsingMoveConstructor(
 328       const MoveOnly_RelocateUsingMoveConstructor&) = delete;
 329   MoveOnly_RelocateUsingMoveConstructor(
 330       MoveOnly_RelocateUsingMoveConstructor&&) = default;
 331
 332   MoveOnly_RelocateUsingMoveConstructor& operator=(
 333       const MoveOnly_RelocateUsingMoveConstructor&) = delete;
 334   MoveOnly_RelocateUsingMoveConstructor& operator=(
 335       MoveOnly_RelocateUsingMoveConstructor&&) = default;
 336 };
 337 }  // namespace TestTArray
 338
 339 MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
 340     TestTArray::MoveOnly_RelocateUsingMoveConstructor)
 341
 342 namespace TestTArray {
 343 static_assert(std::is_move_constructible_v<
 344               nsTArray<MoveOnly_RelocateUsingMoveConstructor>>);
 345 static_assert(
 346     std::is_move_assignable_v<nsTArray<MoveOnly_RelocateUsingMoveConstructor>>);
 347 static_assert(!std::is_copy_constructible_v<
 348               nsTArray<MoveOnly_RelocateUsingMoveConstructor>>);
 349 static_assert(!std::is_copy_assignable_v<
 350               nsTArray<MoveOnly_RelocateUsingMoveConstructor>>);
 351 }  // namespace TestTArray
 352
 353 namespace TestTArray {
 354
 355 /* static */
 356 int Countable::sCount = 0;
 357 /* static */
 358 int Moveable::sCount = 0;
 359
 360 static nsTArray<int> returns_by_value() {
 361   nsTArray<int> result;
 362   return result;
 363 }
 364
 365 TEST(TArray, test_return_by_value)
 366 {
 367   nsTArray<int> result = returns_by_value();
 368   ASSERT_TRUE(true);  // This is just a compilation test.
 369 }
 370
 371 TEST(TArray, test_move_array)
 372 {
 373   nsTArray<Countable> countableArray;
 374   uint32_t i;
 375   for (i = 0; i < 4; ++i) {
 376     countableArray.AppendElement(Countable());
 377   }
 378
 379   ASSERT_EQ(Countable::Count(), 8);
 380
 381   const nsTArray<Countable>& constRefCountableArray = countableArray;
 382
 383   ASSERT_EQ(Countable::Count(), 8);
 384
 385   nsTArray<Countable> copyCountableArray(constRefCountableArray.Clone());
 386
 387   ASSERT_EQ(Countable::Count(), 12);
 388
 389   nsTArray<Countable>&& moveRefCountableArray = std::move(countableArray);
 390   moveRefCountableArray.Length();  // Make compilers happy.
 391
 392   ASSERT_EQ(Countable::Count(), 12);
 393
 394   nsTArray<Countable> movedCountableArray(std::move(countableArray));
 395
 396   ASSERT_EQ(Countable::Count(), 12);
 397
 398   // Test ctor
 399   FallibleTArray<Countable> differentAllocatorCountableArray(
 400       std::move(copyCountableArray));
 401   // operator=
 402   copyCountableArray = std::move(differentAllocatorCountableArray);
 403   differentAllocatorCountableArray = std::move(copyCountableArray);
 404   // And the other ctor
 405   nsTArray<Countable> copyCountableArray2(
 406       std::move(differentAllocatorCountableArray));
 407   // with auto
 408   AutoTArray<Countable, 3> autoCountableArray(std::move(copyCountableArray2));
 409   // operator=
 410   copyCountableArray2 = std::move(autoCountableArray);
 411   // Mix with FallibleTArray
 412   FallibleTArray<Countable> differentAllocatorCountableArray2(
 413       std::move(copyCountableArray2));
 414   AutoTArray<Countable, 4> autoCountableArray2(
 415       std::move(differentAllocatorCountableArray2));
 416   differentAllocatorCountableArray2 = std::move(autoCountableArray2);
 417
 418   ASSERT_EQ(Countable::Count(), 12);
 419
 420   nsTArray<Moveable> moveableArray;
 421   for (i = 0; i < 4; ++i) {
 422     moveableArray.AppendElement(Moveable());
 423   }
 424
 425   ASSERT_EQ(Moveable::Count(), 4);
 426
 427   const nsTArray<Moveable>& constRefMoveableArray = moveableArray;
 428
 429   ASSERT_EQ(Moveable::Count(), 4);
 430
 431   nsTArray<Moveable> copyMoveableArray(constRefMoveableArray.Clone());
 432
 433   ASSERT_EQ(Moveable::Count(), 8);
 434
 435   nsTArray<Moveable>&& moveRefMoveableArray = std::move(moveableArray);
 436   moveRefMoveableArray.Length();  // Make compilers happy.
 437
 438   ASSERT_EQ(Moveable::Count(), 8);
 439
 440   nsTArray<Moveable> movedMoveableArray(std::move(moveableArray));
 441
 442   ASSERT_EQ(Moveable::Count(), 8);
 443
 444   // Test ctor
 445   FallibleTArray<Moveable> differentAllocatorMoveableArray(
 446       std::move(copyMoveableArray));
 447   // operator=
 448   copyMoveableArray = std::move(differentAllocatorMoveableArray);
 449   differentAllocatorMoveableArray = std::move(copyMoveableArray);
 450   // And the other ctor
 451   nsTArray<Moveable> copyMoveableArray2(
 452       std::move(differentAllocatorMoveableArray));
 453   // with auto
 454   AutoTArray<Moveable, 3> autoMoveableArray(std::move(copyMoveableArray2));
 455   // operator=
 456   copyMoveableArray2 = std::move(autoMoveableArray);
 457   // Mix with FallibleTArray
 458   FallibleTArray<Moveable> differentAllocatorMoveableArray2(
 459       std::move(copyMoveableArray2));
 460   AutoTArray<Moveable, 4> autoMoveableArray2(
 461       std::move(differentAllocatorMoveableArray2));
 462   differentAllocatorMoveableArray2 = std::move(autoMoveableArray2);
 463
 464   ASSERT_EQ(Moveable::Count(), 8);
 465
 466   AutoTArray<Moveable, 8> moveableAutoArray;
 467   for (uint32_t i = 0; i < 4; ++i) {
 468     moveableAutoArray.AppendElement(Moveable());
 469   }
 470
 471   ASSERT_EQ(Moveable::Count(), 12);
 472
 473   const AutoTArray<Moveable, 8>& constRefMoveableAutoArray = moveableAutoArray;
 474
 475   ASSERT_EQ(Moveable::Count(), 12);
 476
 477   CopyableAutoTArray<Moveable, 8> copyMoveableAutoArray(
 478       constRefMoveableAutoArray);
 479
 480   ASSERT_EQ(Moveable::Count(), 16);
 481
 482   AutoTArray<Moveable, 8> movedMoveableAutoArray(std::move(moveableAutoArray));
 483
 484   ASSERT_EQ(Moveable::Count(), 16);
 485 }
 486
 487 template <typename TypeParam>
 488 class TArray_MoveOnlyTest : public ::testing::Test {};
 489
 490 TYPED_TEST_SUITE_P(TArray_MoveOnlyTest);
 491
 492 static constexpr size_t kMoveOnlyTestArrayLength = 4;
 493
 494 template <typename ArrayType>
 495 static auto MakeMoveOnlyArray() {
 496   ArrayType moveOnlyArray;
 497   for (size_t i = 0; i < kMoveOnlyTestArrayLength; ++i) {
 498     EXPECT_TRUE(moveOnlyArray.AppendElement(typename ArrayType::value_type(),
 499                                             fallible));
 500   }
 501   return moveOnlyArray;
 502 }
 503
 504 TYPED_TEST_P(TArray_MoveOnlyTest, nsTArray_MoveConstruct) {
 505   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 506   nsTArray<TypeParam> movedMoveOnlyArray(std::move(moveOnlyArray));
 507
 508   ASSERT_EQ(0u, moveOnlyArray.Length());
 509   ASSERT_EQ(kMoveOnlyTestArrayLength, movedMoveOnlyArray.Length());
 510 }
 511
 512 TYPED_TEST_P(TArray_MoveOnlyTest, nsTArray_MoveAssign) {
 513   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 514   nsTArray<TypeParam> movedMoveOnlyArray;
 515   movedMoveOnlyArray = std::move(moveOnlyArray);
 516
 517   ASSERT_EQ(0u, moveOnlyArray.Length());
 518   ASSERT_EQ(kMoveOnlyTestArrayLength, movedMoveOnlyArray.Length());
 519 }
 520
 521 TYPED_TEST_P(TArray_MoveOnlyTest, nsTArray_MoveReAssign) {
 522   nsTArray<TypeParam> movedMoveOnlyArray;
 523   movedMoveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 524   // Re-assign, to check that move-assign does not only work on an empty array.
 525   movedMoveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 526
 527   ASSERT_EQ(kMoveOnlyTestArrayLength, movedMoveOnlyArray.Length());
 528 }
 529
 530 TYPED_TEST_P(TArray_MoveOnlyTest, nsTArray_to_FallibleTArray_MoveConstruct) {
 531   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 532   FallibleTArray<TypeParam> differentAllocatorMoveOnlyArray(
 533       std::move(moveOnlyArray));
 534
 535   ASSERT_EQ(0u, moveOnlyArray.Length());
 536   ASSERT_EQ(kMoveOnlyTestArrayLength, differentAllocatorMoveOnlyArray.Length());
 537 }
 538
 539 TYPED_TEST_P(TArray_MoveOnlyTest, nsTArray_to_FallibleTArray_MoveAssign) {
 540   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 541   FallibleTArray<TypeParam> differentAllocatorMoveOnlyArray;
 542   differentAllocatorMoveOnlyArray = std::move(moveOnlyArray);
 543
 544   ASSERT_EQ(0u, moveOnlyArray.Length());
 545   ASSERT_EQ(kMoveOnlyTestArrayLength, differentAllocatorMoveOnlyArray.Length());
 546 }
 547
 548 TYPED_TEST_P(TArray_MoveOnlyTest, FallibleTArray_to_nsTArray_MoveConstruct) {
 549   auto moveOnlyArray = MakeMoveOnlyArray<FallibleTArray<TypeParam>>();
 550   nsTArray<TypeParam> differentAllocatorMoveOnlyArray(std::move(moveOnlyArray));
 551
 552   ASSERT_EQ(0u, moveOnlyArray.Length());
 553   ASSERT_EQ(kMoveOnlyTestArrayLength, differentAllocatorMoveOnlyArray.Length());
 554 }
 555
 556 TYPED_TEST_P(TArray_MoveOnlyTest, FallibleTArray_to_nsTArray_MoveAssign) {
 557   auto moveOnlyArray = MakeMoveOnlyArray<FallibleTArray<TypeParam>>();
 558   nsTArray<TypeParam> differentAllocatorMoveOnlyArray;
 559   differentAllocatorMoveOnlyArray = std::move(moveOnlyArray);
 560
 561   ASSERT_EQ(0u, moveOnlyArray.Length());
 562   ASSERT_EQ(kMoveOnlyTestArrayLength, differentAllocatorMoveOnlyArray.Length());
 563 }
 564
 565 TYPED_TEST_P(TArray_MoveOnlyTest, AutoTArray_AutoStorage_MoveConstruct) {
 566   auto moveOnlyArray =
 567       MakeMoveOnlyArray<AutoTArray<TypeParam, kMoveOnlyTestArrayLength>>();
 568   AutoTArray<TypeParam, kMoveOnlyTestArrayLength> autoMoveOnlyArray(
 569       std::move(moveOnlyArray));
 570
 571   ASSERT_EQ(0u, moveOnlyArray.Length());
 572   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 573 }
 574
 575 TYPED_TEST_P(TArray_MoveOnlyTest, AutoTArray_AutoStorage_MoveAssign) {
 576   auto moveOnlyArray =
 577       MakeMoveOnlyArray<AutoTArray<TypeParam, kMoveOnlyTestArrayLength>>();
 578   AutoTArray<TypeParam, kMoveOnlyTestArrayLength> autoMoveOnlyArray;
 579   autoMoveOnlyArray = std::move(moveOnlyArray);
 580
 581   ASSERT_EQ(0u, moveOnlyArray.Length());
 582   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 583 }
 584
 585 TYPED_TEST_P(TArray_MoveOnlyTest,
 586              nsTArray_to_AutoTArray_AutoStorage_MoveConstruct) {
 587   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 588   AutoTArray<TypeParam, kMoveOnlyTestArrayLength> autoMoveOnlyArray(
 589       std::move(moveOnlyArray));
 590
 591   ASSERT_EQ(0u, moveOnlyArray.Length());
 592   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 593 }
 594
 595 TYPED_TEST_P(TArray_MoveOnlyTest,
 596              nsTArray_to_AutoTArray_AutoStorage_MoveAssign) {
 597   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 598   AutoTArray<TypeParam, kMoveOnlyTestArrayLength> autoMoveOnlyArray;
 599   autoMoveOnlyArray = std::move(moveOnlyArray);
 600
 601   ASSERT_EQ(0u, moveOnlyArray.Length());
 602   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 603 }
 604
 605 TYPED_TEST_P(TArray_MoveOnlyTest,
 606              nsTArray_to_AutoTArray_HeapStorage_MoveConstruct) {
 607   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 608   AutoTArray<TypeParam, kMoveOnlyTestArrayLength - 1> autoMoveOnlyArray(
 609       std::move(moveOnlyArray));
 610
 611   ASSERT_EQ(0u, moveOnlyArray.Length());
 612   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 613 }
 614
 615 TYPED_TEST_P(TArray_MoveOnlyTest,
 616              nsTArray_to_AutoTArray_HeapStorage_MoveAssign) {
 617   auto moveOnlyArray = MakeMoveOnlyArray<nsTArray<TypeParam>>();
 618   AutoTArray<TypeParam, kMoveOnlyTestArrayLength - 1> autoMoveOnlyArray;
 619   autoMoveOnlyArray = std::move(moveOnlyArray);
 620
 621   ASSERT_EQ(0u, moveOnlyArray.Length());
 622   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 623 }
 624
 625 TYPED_TEST_P(TArray_MoveOnlyTest,
 626              FallibleTArray_to_AutoTArray_HeapStorage_MoveConstruct) {
 627   auto moveOnlyArray = MakeMoveOnlyArray<FallibleTArray<TypeParam>>();
 628   AutoTArray<TypeParam, 4> autoMoveOnlyArray(std::move(moveOnlyArray));
 629
 630   ASSERT_EQ(0u, moveOnlyArray.Length());
 631   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 632 }
 633
 634 TYPED_TEST_P(TArray_MoveOnlyTest,
 635              FallibleTArray_to_AutoTArray_HeapStorage_MoveAssign) {
 636   auto moveOnlyArray = MakeMoveOnlyArray<FallibleTArray<TypeParam>>();
 637   AutoTArray<TypeParam, 4> autoMoveOnlyArray;
 638   autoMoveOnlyArray = std::move(moveOnlyArray);
 639
 640   ASSERT_EQ(0u, moveOnlyArray.Length());
 641   ASSERT_EQ(kMoveOnlyTestArrayLength, autoMoveOnlyArray.Length());
 642 }
 643
 644 REGISTER_TYPED_TEST_SUITE_P(
 645     TArray_MoveOnlyTest, nsTArray_MoveConstruct, nsTArray_MoveAssign,
 646     nsTArray_MoveReAssign, nsTArray_to_FallibleTArray_MoveConstruct,
 647     nsTArray_to_FallibleTArray_MoveAssign,
 648     FallibleTArray_to_nsTArray_MoveConstruct,
 649     FallibleTArray_to_nsTArray_MoveAssign, AutoTArray_AutoStorage_MoveConstruct,
 650     AutoTArray_AutoStorage_MoveAssign,
 651     nsTArray_to_AutoTArray_AutoStorage_MoveConstruct,
 652     nsTArray_to_AutoTArray_AutoStorage_MoveAssign,
 653     nsTArray_to_AutoTArray_HeapStorage_MoveConstruct,
 654     nsTArray_to_AutoTArray_HeapStorage_MoveAssign,
 655     FallibleTArray_to_AutoTArray_HeapStorage_MoveConstruct,
 656     FallibleTArray_to_AutoTArray_HeapStorage_MoveAssign);
 657
 658 using BothMoveOnlyTypes =
 659     ::testing::Types<MoveOnly_RelocateUsingMemutils,
 660                      MoveOnly_RelocateUsingMoveConstructor>;
 661 INSTANTIATE_TYPED_TEST_SUITE_P(InstantiationOf, TArray_MoveOnlyTest,
 662                                BothMoveOnlyTypes);
 663
 664 //----
 665
 666 TEST(TArray, test_string_array)
 667 {
 668   nsTArray<nsCString> strArray;
 669   const char kdata[] = "hello world";
 670   size_t i;
 671   for (i = 0; i < ArrayLength(kdata); ++i) {
 672     nsCString str;
 673     str.Assign(kdata[i]);
 674     strArray.AppendElement(str);
 675   }
 676   for (i = 0; i < ArrayLength(kdata); ++i) {
 677     ASSERT_EQ(strArray[i].CharAt(0), kdata[i]);
 678   }
 679
 680   const char kextra[] = "foo bar";
 681   size_t oldLen = strArray.Length();
 682   strArray.AppendElement(kextra);
 683   strArray.RemoveElement(kextra);
 684   ASSERT_EQ(oldLen, strArray.Length());
 685
 686   ASSERT_EQ(strArray.IndexOf("e"), size_t(1));
 687   ASSERT_TRUE(strArray.ApplyIf(
 688       "e", [](size_t i, nsCString& s) { return i == 1 && s == "e"; },
 689       []() { return false; }));
 690
 691   strArray.Sort();
 692   const char ksorted[] = "\0 dehllloorw";
 693   for (i = ArrayLength(kdata); i--;) {
 694     ASSERT_EQ(strArray[i].CharAt(0), ksorted[i]);
 695     if (i > 0 && strArray[i] == strArray[i - 1]) strArray.RemoveElementAt(i);
 696   }
 697   for (i = 0; i < strArray.Length(); ++i) {
 698     ASSERT_EQ(strArray.BinaryIndexOf(strArray[i]), i);
 699   }
 700   auto no_index = strArray.NoIndex;  // Fixes gtest compilation error
 701   ASSERT_EQ(strArray.BinaryIndexOf(""_ns), no_index);
 702
 703   nsCString rawArray[MOZ_ARRAY_LENGTH(kdata) - 1];
 704   for (i = 0; i < ArrayLength(rawArray); ++i)
 705     rawArray[i].Assign(kdata + i);  // substrings of kdata
 706
 707   ASSERT_TRUE(
 708       test_basic_array(rawArray, ArrayLength(rawArray), nsCString("foopy")));
 709 }
 710
 711 //----
 712
 713 typedef nsCOMPtr<nsIFile> FilePointer;
 714
 715 class nsFileNameComparator {
 716  public:
 717   bool Equals(const FilePointer& a, const char* b) const {
 718     nsAutoCString name;
 719     a->GetNativeLeafName(name);
 720     return name.Equals(b);
 721   }
 722 };
 723
 724 TEST(TArray, test_comptr_array)
 725 {
 726   FilePointer tmpDir;
 727   NS_GetSpecialDirectory(NS_OS_TEMP_DIR, getter_AddRefs(tmpDir));
 728   ASSERT_TRUE(tmpDir);
 729   const char* kNames[] = {"foo.txt", "bar.html", "baz.gif"};
 730   nsTArray<FilePointer> fileArray;
 731   size_t i;
 732   for (i = 0; i < ArrayLength(kNames); ++i) {
 733     FilePointer f;
 734     tmpDir->Clone(getter_AddRefs(f));
 735     ASSERT_TRUE(f);
 736     ASSERT_NS_SUCCEEDED(f->AppendNative(nsDependentCString(kNames[i])));
 737     fileArray.AppendElement(f);
 738   }
 739
 740   ASSERT_EQ(fileArray.IndexOf(kNames[1], 0, nsFileNameComparator()), size_t(1));
 741   ASSERT_TRUE(fileArray.ApplyIf(
 742       kNames[1], 0, nsFileNameComparator(), [](size_t i) { return i == 1; },
 743       []() { return false; }));
 744
 745   // It's unclear what 'operator<' means for nsCOMPtr, but whatever...
 746   ASSERT_TRUE(
 747       test_basic_array(fileArray.Elements(), fileArray.Length(), tmpDir));
 748 }
 749
 750 //----
 751
 752 class RefcountedObject {
 753  public:
 754   RefcountedObject() : rc(0) { val = std::rand(); }
 755   void AddRef() {
 756     MOZ_DIAGNOSTIC_ASSERT(rcchangeallowed);
 757     ++rc;
 758   }
 759   void Release() {
 760     MOZ_DIAGNOSTIC_ASSERT(rcchangeallowed);
 761     if (--rc == 0) delete this;
 762   }
 763   ~RefcountedObject() = default;
 764
 765   int32_t GetVal() const { return val; }
 766
 767   static void AllowRCChange() { rcchangeallowed = true; }
 768   static void ForbidRCChange() { rcchangeallowed = false; }
 769
 770   bool operator<(const RefcountedObject& b) const {
 771     return this->GetVal() < b.GetVal();
 772   };
 773
 774   bool operator==(const RefcountedObject& b) const {
 775     return this->GetVal() == b.GetVal();
 776   };
 777
 778  private:
 779   int rc;
 780   int32_t val;
 781   static bool rcchangeallowed;
 782 };
 783 bool RefcountedObject::rcchangeallowed = true;
 784
 785 class ObjectComparatorRaw {
 786  public:
 787   bool Equals(RefcountedObject* const& a, RefcountedObject* const& b) const {
 788     return a->GetVal() == b->GetVal();
 789   }
 790
 791   bool LessThan(RefcountedObject* const& a, RefcountedObject* const& b) const {
 792     return a->GetVal() < b->GetVal();
 793   }
 794 };
 795
 796 class ObjectComparatorRefPtr {
 797  public:
 798   bool Equals(RefPtr<RefcountedObject> const& a,
 799               RefPtr<RefcountedObject> const& b) const {
 800     return a->GetVal() == b->GetVal();
 801   }
 802
 803   bool LessThan(RefPtr<RefcountedObject> const& a,
 804                 RefPtr<RefcountedObject> const& b) const {
 805     return a->GetVal() < b->GetVal();
 806   }
 807 };
 808
 809 TEST(TArray, test_refptr_array)
 810 {
 811   nsTArray<RefPtr<RefcountedObject>> objArray;
 812
 813   RefcountedObject* a = new RefcountedObject();
 814   a->AddRef();
 815   RefcountedObject* b = new RefcountedObject();
 816   b->AddRef();
 817   RefcountedObject* c = new RefcountedObject();
 818   c->AddRef();
 819
 820   objArray.AppendElement(a);
 821   objArray.AppendElement(b);
 822   objArray.AppendElement(c);
 823
 824   ASSERT_EQ(objArray.IndexOf(b), size_t(1));
 825   ASSERT_TRUE(objArray.ApplyIf(
 826       b,
 827       [&](size_t i, RefPtr<RefcountedObject>& r) { return i == 1 && r == b; },
 828       []() { return false; }));
 829
 830   a->Release();
 831   b->Release();
 832   c->Release();
 833 }
 834
 835 TEST(TArray, test_sort_refptr)
 836 {
 837   int numobjects = 1111111;
 838   std::vector<RefPtr<RefcountedObject>> myobjects;
 839   for (int i = 0; i < numobjects; i++) {
 840     auto* obj = new RefcountedObject();
 841     myobjects.push_back(obj);
 842   }
 843
 844   {
 845     nsTArray<RefPtr<RefcountedObject>> objArray(numobjects);
 846     std::vector<RefPtr<RefcountedObject>> plainRefPtrArray(numobjects, nullptr);
 847
 848     for (int i = 0; i < numobjects; i++) {
 849       objArray.AppendElement(myobjects[i]);
 850       plainRefPtrArray[i] = myobjects[i];
 851     }
 852
 853     ASSERT_EQ(objArray.IndexOf(myobjects[1]), size_t(1));
 854     ASSERT_TRUE(objArray.ApplyIf(
 855         myobjects[1],
 856         [&](size_t i, RefPtr<RefcountedObject>& r) {
 857           return i == 1 && r == myobjects[1];
 858         },
 859         []() { return false; }));
 860
 861     // Do not expect that sorting affects the reference counters of elements.
 862     RefcountedObject::ForbidRCChange();
 863
 864     // Sort objArray with explicit, pointee value based comparator
 865     objArray.Sort(ObjectComparatorRefPtr());
 866     for (int i = 0; i < numobjects - 1; i++) {
 867       ASSERT_TRUE(objArray[i]->GetVal() <= objArray[i + 1]->GetVal());
 868     }
 869
 870     // std::sort plainRefPtrArray
 871     auto comp = ObjectComparatorRefPtr();
 872     std::sort(plainRefPtrArray.begin(), plainRefPtrArray.end(),
 873               [&comp](auto const& left, auto const& right) {
 874                 return comp.LessThan(left, right);
 875               });
 876
 877     // We expect the order to be the same.
 878     for (int i = 0; i < numobjects; i++) {
 879       ASSERT_TRUE(objArray[i]->GetVal() == plainRefPtrArray[i]->GetVal());
 880     }
 881
 882     RefcountedObject::AllowRCChange();
 883     // Destroy the arrays
 884   }
 885
 886   for (int i = 0; i < numobjects; i++) {
 887     myobjects.pop_back();
 888   }
 889 }
 890
 891 //----
 892
 893 TEST(TArray, test_ptrarray)
 894 {
 895   nsTArray<uint32_t*> ary;
 896   ASSERT_EQ(ary.SafeElementAt(0), nullptr);
 897   ASSERT_EQ(ary.SafeElementAt(1000), nullptr);
 898
 899   uint32_t a = 10;
 900   ary.AppendElement(&a);
 901   ASSERT_EQ(*ary[0], a);
 902   ASSERT_EQ(*ary.SafeElementAt(0), a);
 903
 904   nsTArray<const uint32_t*> cary;
 905   ASSERT_EQ(cary.SafeElementAt(0), nullptr);
 906   ASSERT_EQ(cary.SafeElementAt(1000), nullptr);
 907
 908   const uint32_t b = 14;
 909   cary.AppendElement(&a);
 910   cary.AppendElement(&b);
 911   ASSERT_EQ(*cary[0], a);
 912   ASSERT_EQ(*cary[1], b);
 913   ASSERT_EQ(*cary.SafeElementAt(0), a);
 914   ASSERT_EQ(*cary.SafeElementAt(1), b);
 915 }
 916
 917 //----
 918
 919 // This test relies too heavily on the existence of DebugGetHeader to be
 920 // useful in non-debug builds.
 921 #ifdef DEBUG
 922 TEST(TArray, test_autoarray)
 923 {
 924   uint32_t data[] = {4, 6, 8, 2, 4, 1, 5, 7, 3};
 925   AutoTArray<uint32_t, MOZ_ARRAY_LENGTH(data)> array;
 926
 927   void* hdr = array.DebugGetHeader();
 928   ASSERT_NE(hdr, nsTArray<uint32_t>().DebugGetHeader());
 929   ASSERT_NE(hdr,
 930             (AutoTArray<uint32_t, MOZ_ARRAY_LENGTH(data)>().DebugGetHeader()));
 931
 932   array.AppendElement(1u);
 933   ASSERT_EQ(hdr, array.DebugGetHeader());
 934
 935   array.RemoveElement(1u);
 936   array.AppendElements(data, ArrayLength(data));
 937   ASSERT_EQ(hdr, array.DebugGetHeader());
 938
 939   array.AppendElement(2u);
 940   ASSERT_NE(hdr, array.DebugGetHeader());
 941
 942   array.Clear();
 943   array.Compact();
 944   ASSERT_EQ(hdr, array.DebugGetHeader());
 945   array.AppendElements(data, ArrayLength(data));
 946   ASSERT_EQ(hdr, array.DebugGetHeader());
 947
 948   nsTArray<uint32_t> array2;
 949   void* emptyHdr = array2.DebugGetHeader();
 950   array.SwapElements(array2);
 951   ASSERT_NE(emptyHdr, array.DebugGetHeader());
 952   ASSERT_NE(hdr, array2.DebugGetHeader());
 953   size_t i;
 954   for (i = 0; i < ArrayLength(data); ++i) {
 955     ASSERT_EQ(array2[i], data[i]);
 956   }
 957   ASSERT_TRUE(array.IsEmpty());
 958
 959   array.Compact();
 960   array.AppendElements(data, ArrayLength(data));
 961   uint32_t data3[] = {5, 7, 11};
 962   AutoTArray<uint32_t, MOZ_ARRAY_LENGTH(data3)> array3;
 963   array3.AppendElements(data3, ArrayLength(data3));
 964   array.SwapElements(array3);
 965   for (i = 0; i < ArrayLength(data); ++i) {
 966     ASSERT_EQ(array3[i], data[i]);
 967   }
 968   for (i = 0; i < ArrayLength(data3); ++i) {
 969     ASSERT_EQ(array[i], data3[i]);
 970   }
 971 }
 972 #endif
 973
 974 //----
 975
 976 // IndexOf used to potentially scan beyond the end of the array.  Test for
 977 // this incorrect behavior by adding a value (5), removing it, then seeing
 978 // if IndexOf finds it.
 979 TEST(TArray, test_indexof)
 980 {
 981   nsTArray<int> array;
 982   array.AppendElement(0);
 983   // add and remove the 5
 984   array.AppendElement(5);
 985   array.RemoveElementAt(1);
 986   // we should not find the 5!
 987   auto no_index = array.NoIndex;  // Fixes gtest compilation error.
 988   ASSERT_EQ(array.IndexOf(5, 1), no_index);
 989   ASSERT_FALSE(array.ApplyIf(
 990       5, 1, []() { return true; }, []() { return false; }));
 991 }
 992
 993 //----
 994
 995 template <class Array>
 996 static bool is_heap(const Array& ary, size_t len) {
 997   size_t index = 1;
 998   while (index < len) {
 999     if (ary[index] > ary[(index - 1) >> 1]) return false;
1000     index++;
1001   }
1002   return true;
1003 }
1004
1005 //----
1006
1007 // An array |arr| is using its auto buffer if |&arr < arr.Elements()| and
1008 // |arr.Elements() - &arr| is small.
1009
1010 #define IS_USING_AUTO(arr)                              \
1011   ((uintptr_t) & (arr) < (uintptr_t)(arr).Elements() && \
1012    ((ptrdiff_t)(arr).Elements() - (ptrdiff_t) & (arr)) <= 16)
1013
1014 #define CHECK_IS_USING_AUTO(arr)     \
1015   do {                               \
1016     ASSERT_TRUE(IS_USING_AUTO(arr)); \
1017   } while (0)
1018
1019 #define CHECK_NOT_USING_AUTO(arr)     \
1020   do {                                \
1021     ASSERT_FALSE(IS_USING_AUTO(arr)); \
1022   } while (0)
1023
1024 #define CHECK_USES_SHARED_EMPTY_HDR(arr)            \
1025   do {                                              \
1026     nsTArray<int> _empty;                           \
1027     ASSERT_EQ(_empty.Elements(), (arr).Elements()); \
1028   } while (0)
1029
1030 #define CHECK_EQ_INT(actual, expected) \
1031   do {                                 \
1032     ASSERT_EQ((actual), (expected));   \
1033   } while (0)
1034
1035 #define CHECK_ARRAY(arr, data)                               \
1036   do {                                                       \
1037     CHECK_EQ_INT((arr).Length(), (size_t)ArrayLength(data)); \
1038     for (size_t _i = 0; _i < ArrayLength(data); _i++) {      \
1039       CHECK_EQ_INT((arr)[_i], (data)[_i]);                   \
1040     }                                                        \
1041   } while (0)
1042
1043 TEST(TArray, test_swap)
1044 {
1045   // Test nsTArray::SwapElements.  Unfortunately there are many cases.
1046   int data1[] = {8, 6, 7, 5};
1047   int data2[] = {3, 0, 9};
1048
1049   // Swap two auto arrays.
1050   {
1051     AutoTArray<int, 8> a;
1052     AutoTArray<int, 6> b;
1053
1054     a.AppendElements(data1, ArrayLength(data1));
1055     b.AppendElements(data2, ArrayLength(data2));
1056     CHECK_IS_USING_AUTO(a);
1057     CHECK_IS_USING_AUTO(b);
1058
1059     a.SwapElements(b);
1060
1061     CHECK_IS_USING_AUTO(a);
1062     CHECK_IS_USING_AUTO(b);
1063     CHECK_ARRAY(a, data2);
1064     CHECK_ARRAY(b, data1);
1065   }
1066
1067   // Swap two auto arrays -- one whose data lives on the heap, the other whose
1068   // data lives on the stack -- which each fits into the other's auto storage.
1069   {
1070     AutoTArray<int, 3> a;
1071     AutoTArray<int, 3> b;
1072
1073     a.AppendElements(data1, ArrayLength(data1));
1074     a.RemoveElementAt(3);
1075     b.AppendElements(data2, ArrayLength(data2));
1076
1077     // Here and elsewhere, we assert that if we start with an auto array
1078     // capable of storing N elements, we store N+1 elements into the array, and
1079     // then we remove one element, that array is still not using its auto
1080     // buffer.
1081     //
1082     // This isn't at all required by the TArray API. It would be fine if, when
1083     // we shrink back to N elements, the TArray frees its heap storage and goes
1084     // back to using its stack storage.  But we assert here as a check that the
1085     // test does what we expect.  If the TArray implementation changes, just
1086     // change the failing assertions.
1087     CHECK_NOT_USING_AUTO(a);
1088
1089     // This check had better not change, though.
1090     CHECK_IS_USING_AUTO(b);
1091
1092     a.SwapElements(b);
1093
1094     CHECK_IS_USING_AUTO(b);
1095     CHECK_ARRAY(a, data2);
1096     int expectedB[] = {8, 6, 7};
1097     CHECK_ARRAY(b, expectedB);
1098   }
1099
1100   // Swap two auto arrays which are using heap storage such that one fits into
1101   // the other's auto storage, but the other needs to stay on the heap.
1102   {
1103     AutoTArray<int, 3> a;
1104     AutoTArray<int, 2> b;
1105     a.AppendElements(data1, ArrayLength(data1));
1106     a.RemoveElementAt(3);
1107
1108     b.AppendElements(data2, ArrayLength(data2));
1109     b.RemoveElementAt(2);
1110
1111     CHECK_NOT_USING_AUTO(a);
1112     CHECK_NOT_USING_AUTO(b);
1113
1114     a.SwapElements(b);
1115
1116     CHECK_NOT_USING_AUTO(b);
1117
1118     int expected1[] = {3, 0};
1119     int expected2[] = {8, 6, 7};
1120
1121     CHECK_ARRAY(a, expected1);
1122     CHECK_ARRAY(b, expected2);
1123   }
1124
1125   // Swap two arrays, neither of which fits into the other's auto-storage.
1126   {
1127     AutoTArray<int, 1> a;
1128     AutoTArray<int, 3> b;
1129
1130     a.AppendElements(data1, ArrayLength(data1));
1131     b.AppendElements(data2, ArrayLength(data2));
1132
1133     a.SwapElements(b);
1134
1135     CHECK_ARRAY(a, data2);
1136     CHECK_ARRAY(b, data1);
1137   }
1138
1139   // Swap an empty nsTArray with a non-empty AutoTArray.
1140   {
1141     nsTArray<int> a;
1142     AutoTArray<int, 3> b;
1143
1144     b.AppendElements(data2, ArrayLength(data2));
1145     CHECK_IS_USING_AUTO(b);
1146
1147     a.SwapElements(b);
1148
1149     CHECK_ARRAY(a, data2);
1150     CHECK_EQ_INT(b.Length(), size_t(0));
1151     CHECK_IS_USING_AUTO(b);
1152   }
1153
1154   // Swap two big auto arrays.
1155   {
1156     const unsigned size = 8192;
1157     AutoTArray<unsigned, size> a;
1158     AutoTArray<unsigned, size> b;
1159
1160     for (unsigned i = 0; i < size; i++) {
1161       a.AppendElement(i);
1162       b.AppendElement(i + 1);
1163     }
1164
1165     CHECK_IS_USING_AUTO(a);
1166     CHECK_IS_USING_AUTO(b);
1167
1168     a.SwapElements(b);
1169
1170     CHECK_IS_USING_AUTO(a);
1171     CHECK_IS_USING_AUTO(b);
1172
1173     CHECK_EQ_INT(a.Length(), size_t(size));
1174     CHECK_EQ_INT(b.Length(), size_t(size));
1175
1176     for (unsigned i = 0; i < size; i++) {
1177       CHECK_EQ_INT(a[i], i + 1);
1178       CHECK_EQ_INT(b[i], i);
1179     }
1180   }
1181
1182   // Swap two arrays and make sure that their capacities don't increase
1183   // unnecessarily.
1184   {
1185     nsTArray<int> a;
1186     nsTArray<int> b;
1187     b.AppendElements(data2, ArrayLength(data2));
1188
1189     CHECK_EQ_INT(a.Capacity(), size_t(0));
1190     size_t bCapacity = b.Capacity();
1191
1192     a.SwapElements(b);
1193
1194     // Make sure that we didn't increase the capacity of either array.
1195     CHECK_ARRAY(a, data2);
1196     CHECK_EQ_INT(b.Length(), size_t(0));
1197     CHECK_EQ_INT(b.Capacity(), size_t(0));
1198     CHECK_EQ_INT(a.Capacity(), bCapacity);
1199   }
1200
1201   // Swap an auto array with a TArray, then clear the auto array and make sure
1202   // it doesn't forget the fact that it has an auto buffer.
1203   {
1204     nsTArray<int> a;
1205     AutoTArray<int, 3> b;
1206
1207     a.AppendElements(data1, ArrayLength(data1));
1208
1209     a.SwapElements(b);
1210
1211     CHECK_EQ_INT(a.Length(), size_t(0));
1212     CHECK_ARRAY(b, data1);
1213
1214     b.Clear();
1215
1216     CHECK_USES_SHARED_EMPTY_HDR(a);
1217     CHECK_IS_USING_AUTO(b);
1218   }
1219
1220   // Same thing as the previous test, but with more auto arrays.
1221   {
1222     AutoTArray<int, 16> a;
1223     AutoTArray<int, 3> b;
1224
1225     a.AppendElements(data1, ArrayLength(data1));
1226
1227     a.SwapElements(b);
1228
1229     CHECK_EQ_INT(a.Length(), size_t(0));
1230     CHECK_ARRAY(b, data1);
1231
1232     b.Clear();
1233
1234     CHECK_IS_USING_AUTO(a);
1235     CHECK_IS_USING_AUTO(b);
1236   }
1237
1238   // Swap an empty nsTArray and an empty AutoTArray.
1239   {
1240     AutoTArray<int, 8> a;
1241     nsTArray<int> b;
1242
1243     a.SwapElements(b);
1244
1245     CHECK_IS_USING_AUTO(a);
1246     CHECK_NOT_USING_AUTO(b);
1247     CHECK_EQ_INT(a.Length(), size_t(0));
1248     CHECK_EQ_INT(b.Length(), size_t(0));
1249   }
1250
1251   // Swap empty auto array with non-empty AutoTArray using malloc'ed storage.
1252   // I promise, all these tests have a point.
1253   {
1254     AutoTArray<int, 2> a;
1255     AutoTArray<int, 1> b;
1256
1257     a.AppendElements(data1, ArrayLength(data1));
1258
1259     a.SwapElements(b);
1260
1261     CHECK_IS_USING_AUTO(a);
1262     CHECK_NOT_USING_AUTO(b);
1263     CHECK_ARRAY(b, data1);
1264     CHECK_EQ_INT(a.Length(), size_t(0));
1265   }
1266
1267   // Test fallible SwapElements of nsTArray.
1268   {
1269     nsTArray<int> a;
1270     nsTArray<int> b;
1271
1272     a.AppendElements(data1, ArrayLength(data1));
1273
1274     ASSERT_TRUE(a.SwapElements(b, fallible));
1275
1276     CHECK_ARRAY(b, data1);
1277     CHECK_EQ_INT(a.Length(), size_t(0));
1278   }
1279
1280   // Test fallible SwapElements of FallibleTArray.
1281   {
1282     FallibleTArray<int> a;
1283     FallibleTArray<int> b;
1284
1285     ASSERT_TRUE(a.AppendElements(data1, ArrayLength(data1), fallible));
1286
1287     ASSERT_TRUE(a.SwapElements(b, fallible));
1288
1289     CHECK_ARRAY(b, data1);
1290     CHECK_EQ_INT(a.Length(), size_t(0));
1291   }
1292
1293   // Test fallible SwapElements of FallibleTArray with large AutoTArray.
1294   {
1295     FallibleTArray<int> a;
1296     AutoTArray<int, 8192> b;
1297
1298     ASSERT_TRUE(a.AppendElements(data1, ArrayLength(data1), fallible));
1299
1300     ASSERT_TRUE(a.SwapElements(b, fallible));
1301
1302     CHECK_IS_USING_AUTO(b);
1303     CHECK_ARRAY(b, data1);
1304     CHECK_EQ_INT(a.Length(), size_t(0));
1305   }
1306 }
1307
1308 // Bug 1171296: Disabled on andoid due to crashes.
1309 #if !defined(ANDROID)
1310 TEST(TArray, test_fallible)
1311 {
1312   // Test that FallibleTArray works properly; that is, it never OOMs, but
1313   // instead eventually returns false.
1314   //
1315   // This test is only meaningful on 32-bit systems.  On a 64-bit system, we
1316   // might never OOM.
1317   if (sizeof(void*) > 4) {
1318     ASSERT_TRUE(true);
1319     return;
1320   }
1321
1322   // Allocate a bunch of 128MB arrays.  Larger allocations will fail on some
1323   // platforms without actually hitting OOM.
1324   //
1325   // 36 * 128MB > 4GB, so we should definitely OOM by the 36th array.
1326   const unsigned numArrays = 36;
1327   FallibleTArray<char> arrays[numArrays];
1328   bool oomed = false;
1329   for (size_t i = 0; i < numArrays; i++) {
1330     // SetCapacity allocates the requested capacity + a header, and we want to
1331     // avoid allocating more than 128MB overall because of the size padding it
1332     // will cause, which depends on allocator behavior, so use 128MB - an
1333     // arbitrary size larger than the array header, so that chances are good
1334     // that allocations will always be 128MB.
1335     bool success = arrays[i].SetCapacity(128 * 1024 * 1024 - 1024, fallible);
1336     if (!success) {
1337       // We got our OOM.  Check that it didn't come too early.
1338       oomed = true;
1339 #  ifdef XP_WIN
1340       // 32-bit Windows sometimes OOMs on the 6th, 7th, or 8th.  To keep the
1341       // test green, choose the lower of those: the important thing here is
1342       // that some allocations fail and some succeed.  We're not too
1343       // concerned about how many iterations it takes.
1344       const size_t kOOMIterations = 6;
1345 #  else
1346       const size_t kOOMIterations = 8;
1347 #  endif
1348       ASSERT_GE(i, kOOMIterations)
1349           << "Got OOM on iteration " << i << ". Too early!";
1350     }
1351   }
1352
1353   ASSERT_TRUE(oomed)
1354   << "Didn't OOM or crash?  nsTArray::SetCapacity"
1355      "must be lying.";
1356 }
1357 #endif
1358
1359 TEST(TArray, test_conversion_operator)
1360 {
1361   FallibleTArray<int> f;
1362   const FallibleTArray<int> fconst;
1363
1364   nsTArray<int> t;
1365   const nsTArray<int> tconst;
1366   AutoTArray<int, 8> tauto;
1367   const AutoTArray<int, 8> tautoconst;
1368
1369 #define CHECK_ARRAY_CAST(type)                  \
1370   do {                                          \
1371     const type<int>& z1 = f;                    \
1372     ASSERT_EQ((void*)&z1, (void*)&f);           \
1373     const type<int>& z2 = fconst;               \
1374     ASSERT_EQ((void*)&z2, (void*)&fconst);      \
1375     const type<int>& z9 = t;                    \
1376     ASSERT_EQ((void*)&z9, (void*)&t);           \
1377     const type<int>& z10 = tconst;              \
1378     ASSERT_EQ((void*)&z10, (void*)&tconst);     \
1379     const type<int>& z11 = tauto;               \
1380     ASSERT_EQ((void*)&z11, (void*)&tauto);      \
1381     const type<int>& z12 = tautoconst;          \
1382     ASSERT_EQ((void*)&z12, (void*)&tautoconst); \
1383   } while (0)
1384
1385   CHECK_ARRAY_CAST(FallibleTArray);
1386   CHECK_ARRAY_CAST(nsTArray);
1387
1388 #undef CHECK_ARRAY_CAST
1389 }
1390
1391 template <class T>
1392 struct BufAccessor : public T {
1393   void* GetHdr() { return T::mHdr; }
1394 };
1395
1396 TEST(TArray, test_SetLengthAndRetainStorage_no_ctor)
1397 {
1398   // 1050 because sizeof(int)*1050 is more than a page typically.
1399   const int N = 1050;
1400   FallibleTArray<int> f;
1401
1402   nsTArray<int> t;
1403   AutoTArray<int, N> tauto;
1404
1405 #define LPAREN (
1406 #define RPAREN )
1407 #define FOR_EACH(pre, post) \
1408   do {                      \
1409     pre f post;             \
1410     pre t post;             \
1411     pre tauto post;         \
1412   } while (0)
1413
1414   // Setup test arrays.
1415   FOR_EACH(; Unused <<, .SetLength(N, fallible));
1416   for (int n = 0; n < N; ++n) {
1417     FOR_EACH(;, [n] = n);
1418   }
1419
1420   void* initial_Hdrs[] = {
1421       static_cast<BufAccessor<FallibleTArray<int>>&>(f).GetHdr(),
1422       static_cast<BufAccessor<nsTArray<int>>&>(t).GetHdr(),
1423       static_cast<BufAccessor<AutoTArray<int, N>>&>(tauto).GetHdr(), nullptr};
1424
1425   // SetLengthAndRetainStorage(n), should NOT overwrite memory when T hasn't
1426   // a default constructor.
1427   FOR_EACH(;, .SetLengthAndRetainStorage(8));
1428   FOR_EACH(;, .SetLengthAndRetainStorage(12));
1429   for (int n = 0; n < 12; ++n) {
1430     ASSERT_EQ(f[n], n);
1431     ASSERT_EQ(t[n], n);
1432     ASSERT_EQ(tauto[n], n);
1433   }
1434   FOR_EACH(;, .SetLengthAndRetainStorage(0));
1435   FOR_EACH(;, .SetLengthAndRetainStorage(N));
1436   for (int n = 0; n < N; ++n) {
1437     ASSERT_EQ(f[n], n);
1438     ASSERT_EQ(t[n], n);
1439     ASSERT_EQ(tauto[n], n);
1440   }
1441
1442   void* current_Hdrs[] = {
1443       static_cast<BufAccessor<FallibleTArray<int>>&>(f).GetHdr(),
1444       static_cast<BufAccessor<nsTArray<int>>&>(t).GetHdr(),
1445       static_cast<BufAccessor<AutoTArray<int, N>>&>(tauto).GetHdr(), nullptr};
1446
1447   // SetLengthAndRetainStorage(n) should NOT have reallocated the internal
1448   // memory.
1449   ASSERT_EQ(sizeof(initial_Hdrs), sizeof(current_Hdrs));
1450   for (size_t n = 0; n < sizeof(current_Hdrs) / sizeof(current_Hdrs[0]); ++n) {
1451     ASSERT_EQ(current_Hdrs[n], initial_Hdrs[n]);
1452   }
1453
1454 #undef FOR_EACH
1455 #undef LPAREN
1456 #undef RPAREN
1457 }
1458
1459 template <typename Comparator>
1460 bool TestCompareMethods(const Comparator& aComp) {
1461   nsTArray<int> ary({57, 4, 16, 17, 3, 5, 96, 12});
1462
1463   ary.Sort(aComp);
1464
1465   const int sorted[] = {3, 4, 5, 12, 16, 17, 57, 96};
1466   for (size_t i = 0; i < MOZ_ARRAY_LENGTH(sorted); i++) {
1467     if (sorted[i] != ary[i]) {
1468       return false;
1469     }
1470   }
1471
1472   if (!ary.ContainsSorted(5, aComp)) {
1473     return false;
1474   }
1475   if (ary.ContainsSorted(42, aComp)) {
1476     return false;
1477   }
1478
1479   if (ary.BinaryIndexOf(16, aComp) != 4) {
1480     return false;
1481   }
1482
1483   return true;
1484 }
1485
1486 struct IntComparator {
1487   bool Equals(int aLeft, int aRight) const { return aLeft == aRight; }
1488
1489   bool LessThan(int aLeft, int aRight) const { return aLeft < aRight; }
1490 };
1491
1492 TEST(TArray, test_comparator_objects)
1493 {
1494   ASSERT_TRUE(TestCompareMethods(IntComparator()));
1495   ASSERT_TRUE(
1496       TestCompareMethods([](int aLeft, int aRight) { return aLeft - aRight; }));
1497 }
1498
1499 struct Big {
1500   uint64_t size[40] = {};
1501 };
1502
1503 TEST(TArray, test_AutoTArray_SwapElements)
1504 {
1505   AutoTArray<Big, 40> oneArray;
1506   AutoTArray<Big, 40> another;
1507
1508   for (size_t i = 0; i < 8; ++i) {
1509     oneArray.AppendElement(Big());
1510   }
1511   oneArray[0].size[10] = 1;
1512   for (size_t i = 0; i < 9; ++i) {
1513     another.AppendElement(Big());
1514   }
1515   oneArray.SwapElements(another);
1516
1517   ASSERT_EQ(oneArray.Length(), 9u);
1518   ASSERT_EQ(another.Length(), 8u);
1519
1520   ASSERT_EQ(oneArray[0].size[10], 0u);
1521   ASSERT_EQ(another[0].size[10], 1u);
1522 }
1523
1524 }  // namespace TestTArray