/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef nsTArray_h_
#define nsTArray_h_

#include <string.h>

#include <algorithm>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <new>
#include <ostream>
#include <type_traits>
#include <utility>

#include "mozilla/ArrayIterator.h"
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/BinarySearch.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/FunctionTypeTraits.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/NotNull.h"
#include "mozilla/Span.h"
#include "mozilla/fallible.h"
#include "mozilla/mozalloc.h"
#include "nsAlgorithm.h"
#include "nsDebug.h"
#include "nsISupports.h"
#include "nsRegionFwd.h"
#include "nsTArrayForwardDeclare.h"

namespace JS {
template <class T>
class Heap;
} /* namespace JS */

class nsCycleCollectionTraversalCallback;
struct TraceCallbacks;
class nsRegion;

namespace mozilla::a11y {
class BatchData;
}

namespace mozilla {
namespace layers {
class Animation;
class FrameStats;
struct PropertyAnimationGroup;
struct TileClient;
}  // namespace layers
}  // namespace mozilla

namespace mozilla {
struct SerializedStructuredCloneBuffer;
class SourceBufferTask;
}  // namespace mozilla

namespace mozilla::dom::binding_detail {
template <typename, typename>
class RecordEntry;
}

namespace mozilla::dom {
class MessagePortIdentifier;
template <typename T>
struct Nullable;
class OwningFileOrDirectory;
class OwningStringOrBooleanOrObject;
class OwningUTF8StringOrDouble;
class Pref;
class RefMessageData;
class ResponsiveImageCandidate;
class ServiceWorkerRegistrationData;
namespace indexedDB {
class SerializedStructuredCloneReadInfo;
class ObjectStoreCursorResponse;
class IndexCursorResponse;
}  // namespace indexedDB
}  // namespace mozilla::dom

namespace mozilla::ipc {
class ContentSecurityPolicy;
template <class T>
class Endpoint;
}  // namespace mozilla::ipc

class JSStructuredCloneData;

template <class T>
class RefPtr;

//
// nsTArray<E> is a resizable array class, like std::vector.
//
// Unlike std::vector, which follows C++'s construction/destruction rules,
// By default, nsTArray assumes that instances of E can be relocated safely
// using memory utils (memcpy/memmove).
//
// The public classes defined in this header are
//
//   nsTArray<E>,
//   CopyableTArray<E>,
//   FallibleTArray<E>,
//   AutoTArray<E, N>,
//   CopyableAutoTArray<E, N>
//
// nsTArray, CopyableTArray, AutoTArray and CopyableAutoTArray are infallible by
// default. To opt-in to fallible behaviour, use the `mozilla::fallible`
// parameter and check the return value.
//
// CopyableTArray and CopyableAutoTArray< are copy-constructible and
// copy-assignable. Use these only when syntactically necessary to avoid implcit
// unintentional copies. nsTArray/AutoTArray can be conveniently copied using
// the Clone() member function. Consider using std::move where possible.
//
// If you just want to declare the nsTArray types (e.g., if you're in a header
// file and don't need the full nsTArray definitions) consider including
// nsTArrayForwardDeclare.h instead of nsTArray.h.
//
// The template parameter E specifies the type of the elements and has the
// following requirements:
//
//   E MUST be safely memmove()'able.
//   E MUST define a copy-constructor.
//   E MAY define operator< for sorting.
//   E MAY define operator== for searching.
//
// (Note that the memmove requirement may be relaxed for certain types - see
// nsTArray_RelocationStrategy below.)
//
// There is a public type value_type defined as E within each array class, and
// we reference the type under this name below.
//
// For member functions taking a Comparator instance, Comparator must be either
// a functor with a tri-state comparison function with a signature compatible to
//
//   /** @return negative iff a < b, 0 iff a == b, positive iff a > b */
//   int (const value_type& a, const value_type& b);
//
// or a class defining member functions with signatures compatible to:
//
//   class Comparator {
//     public:
//       /** @return True if the elements are equals; false otherwise. */
//       bool Equals(const value_type& a, const value_type& b) const;
//
//       /** @return True if (a < b); false otherwise. */
//       bool LessThan(const value_type& a, const value_type& b) const;
//   };
//
// The Equals member function is used for searching, and the LessThan member
// function is used for searching and sorting.  Note that some member functions,
// e.g. Compare, are templates where a different type Item can be used for the
// element to compare to. In that case, the signatures must be compatible to
// allow those comparisons, but the details are not documented here.
//

//
// nsTArrayFallibleResult and nsTArrayInfallibleResult types are proxy types
// which are used because you cannot use a templated type which is bound to
// void as an argument to a void function.  In order to work around that, we
// encode either a void or a boolean inside these proxy objects, and pass them
// to the aforementioned function instead, and then use the type information to
// decide what to do in the function.
//
// Note that public nsTArray methods should never return a proxy type.  Such
// types are only meant to be used in the internal nsTArray helper methods.
// Public methods returning non-proxy types cannot be called from other
// nsTArray members.
//
struct nsTArrayFallibleResult {
  // Note: allows implicit conversions from and to bool
  MOZ_IMPLICIT constexpr nsTArrayFallibleResult(bool aResult)
      : mResult(aResult) {}

  MOZ_IMPLICIT constexpr operator bool() { return mResult; }

 private:
  bool mResult;
};

struct nsTArrayInfallibleResult {};

//
// nsTArray*Allocators must all use the same |free()|, to allow swap()'ing
// between fallible and infallible variants.
//

struct nsTArrayFallibleAllocatorBase {
  typedef bool ResultType;
  typedef nsTArrayFallibleResult ResultTypeProxy;

  static constexpr ResultType Result(ResultTypeProxy aResult) {
    return aResult;
  }
  static constexpr bool Successful(ResultTypeProxy aResult) { return aResult; }
  static constexpr ResultTypeProxy SuccessResult() { return true; }
  static constexpr ResultTypeProxy FailureResult() { return false; }
  static constexpr ResultType ConvertBoolToResultType(bool aValue) {
    return aValue;
  }
};

struct nsTArrayInfallibleAllocatorBase {
  typedef void ResultType;
  typedef nsTArrayInfallibleResult ResultTypeProxy;

  static constexpr ResultType Result(ResultTypeProxy aResult) {}
  static constexpr bool Successful(ResultTypeProxy) { return true; }
  static constexpr ResultTypeProxy SuccessResult() { return ResultTypeProxy(); }

  [[noreturn]] static ResultTypeProxy FailureResult() {
    MOZ_CRASH("Infallible nsTArray should never fail");
  }

  template <typename T>
  static constexpr ResultType ConvertBoolToResultType(T aValue) {
    if (!aValue) {
      MOZ_CRASH("infallible nsTArray should never convert false to ResultType");
    }
  }

  template <typename T>
  static constexpr ResultType ConvertBoolToResultType(
      const mozilla::NotNull<T>& aValue) {}
};

struct nsTArrayFallibleAllocator : nsTArrayFallibleAllocatorBase {
  static void* Malloc(size_t aSize) { return malloc(aSize); }
  static void* Realloc(void* aPtr, size_t aSize) {
    return realloc(aPtr, aSize);
  }

  static void Free(void* aPtr) { free(aPtr); }
  static void SizeTooBig(size_t) {}
};

struct nsTArrayInfallibleAllocator : nsTArrayInfallibleAllocatorBase {
  static void* Malloc(size_t aSize) MOZ_NONNULL_RETURN {
    return moz_xmalloc(aSize);
  }
  static void* Realloc(void* aPtr, size_t aSize) MOZ_NONNULL_RETURN {
    return moz_xrealloc(aPtr, aSize);
  }

  static void Free(void* aPtr) { free(aPtr); }
  static void SizeTooBig(size_t aSize) { NS_ABORT_OOM(aSize); }
};

// nsTArray_base stores elements into the space allocated beyond
// sizeof(*this).  This is done to minimize the size of the nsTArray
// object when it is empty.
struct nsTArrayHeader {
  uint32_t mLength;
  uint32_t mCapacity : 31;
  uint32_t mIsAutoArray : 1;
};

// Given an nsTArray which is an AutoTArray, this is the offset from the `this`
// pointer to the `mAutoBuf` member. We guarantee this by forcing mAutoBuf to be
// 8-byte aligned, which makes the location independent of the alignment of T
// (since we don't support over-aligned values in nsTArray).
constexpr static size_t kAutoTArrayHeaderOffset = 8;

extern "C" {
extern const nsTArrayHeader sEmptyTArrayHeader;
}

template <class T>
class nsCOMPtr;

namespace mozilla {
template <class T>
class OwningNonNull;
}  // namespace mozilla

namespace detail {
template <typename Iter, typename Comparator>
void AssertStrictWeakOrder(Iter aBegin, Iter aEnd, const Comparator& aCmp) {
  // This check is present in newer libc++ versions, and it is a useful check,
  // so check for it ourselves if we're not using libc++. Ported from:
  // https://github.com/llvm/llvm-project/blob/cf0efb31880dab5f5b2f20bda6634c68a42d6908/libcxx/include/__cxx03/__debug_utils/strict_weak_ordering_check.h#L28
#if defined(DEBUG) && !defined(_LIBCPP_VERSION)
  MOZ_ASSERT(std::is_sorted(aBegin, aEnd, aCmp),
             "Invalid strict-weak ordering comparator");
  // Limit the number of elements we need to check.
  auto size = std::min(size_t(aEnd - aBegin), size_t(100));
  size_t p = 0;
  while (p < size) {
    size_t q = p + size_t(1);
    // Find first element that is greater than *(aBegin+p).
    while (q < size && !aCmp(*(aBegin + p), *(aBegin + q))) {
      ++q;
    }
    // Check that the elements from p to q are equal between each other.
    for (size_t b = p; b < q; ++b) {
      for (size_t a = p; a <= b; ++a) {
        MOZ_ASSERT(!aCmp(*(aBegin + a), *(aBegin + b)),
                   "Your comparator is not a valid strict-weak ordering");
        MOZ_ASSERT(!aCmp(*(aBegin + b), *(aBegin + a)),
                   "Your comparator is not a valid strict-weak ordering");
      }
    }
    // Check that elements between p and q are less than between q and size.
    for (size_t a = p; a < q; ++a) {
      for (size_t b = q; b < size; ++b) {
        MOZ_ASSERT(aCmp(*(aBegin + a), *(aBegin + b)),
                   "Your comparator is not a valid strict-weak ordering");
        MOZ_ASSERT(!aCmp(*(aBegin + b), *(aBegin + a)),
                   "Your comparator is not a valid strict-weak ordering");
      }
    }
    // Skip these equal elements.
    p = q;
  }
#endif
}

template <typename T>
struct SafeElementAtPointerValue;

template <typename T>
struct SafeElementAtPointerValue<T*> {
  using type = T*;
};
template <typename T>
struct SafeElementAtPointerValue<nsCOMPtr<T>> {
  using type = T*;
};
template <typename T>
struct SafeElementAtPointerValue<RefPtr<T>> {
  using type = T*;
};
template <typename T>
struct SafeElementAtPointerValue<mozilla::OwningNonNull<T>> {
  using type = T*;
};
}  // namespace detail

// This class serves as a base class for nsTArray.  It shouldn't be used
// directly.  It holds common implementation code that does not depend on the
// element type of the nsTArray.
//
template <typename RelocationStrategy>
class nsTArray_base {
  // Needed for AppendElements from an array with a different allocator, which
  // calls ShiftData.
  template <typename E, typename Alloc>
  friend class nsTArray_Impl;

 protected:
  using Header = nsTArrayHeader;

 public:
  using size_type = size_t;
  using index_type = size_t;

  // @return The number of elements in the array.
  size_type Length() const { return mHdr->mLength; }

  // @return True if the array is empty or false otherwise.
  bool IsEmpty() const { return Length() == 0; }

  // @return The number of elements that can fit in the array without forcing
  // the array to be re-allocated.  The length of an array is always less
  // than or equal to its capacity.
  size_type Capacity() const { return mHdr->mCapacity; }

#ifdef DEBUG
  void* DebugGetHeader() const { return mHdr; }
#endif

  nsTArray_base(const nsTArray_base&) = delete;
  nsTArray_base& operator=(const nsTArray_base&) = delete;

 protected:
  nsTArray_base() = default;
  ~nsTArray_base();

  // Resize the storage if necessary to achieve the requested capacity.
  // @param aCapacity The requested number of array elements.
  // @param aElemSize The size of an array element.
  // @return False if insufficient memory is available; true otherwise.
  template <typename Alloc>
  typename Alloc::ResultTypeProxy EnsureCapacity(size_type aCapacity,
                                                 size_type aElemSize) {
    // Do this check here so that our callers can inline it.
    if (aCapacity <= mHdr->mCapacity) {
      return Alloc::SuccessResult();
    }
    return EnsureCapacityImpl<Alloc>(aCapacity, aElemSize);
  }

  // The rest of EnsureCapacity. Should only be called if aCapacity >
  // mHdr->mCapacity.
  template <typename Alloc>
  typename Alloc::ResultTypeProxy EnsureCapacityImpl(size_type aCapacity,
                                                     size_type aElemSize);

  // Extend the storage to accommodate aCount extra elements.
  // @param aLength The current size of the array.
  // @param aCount The number of elements to add.
  // @param aElemSize The size of an array element.
  // @return False if insufficient memory is available or the new length
  //   would overflow; true otherwise.
  template <typename Alloc>
  typename Alloc::ResultTypeProxy ExtendCapacity(size_type aLength,
                                                 size_type aCount,
                                                 size_type aElemSize);

  // Tries to resize the storage to the minimum required amount. If this fails,
  // the array is left as-is.
  // @param aElemSize  The size of an array element.
  void ShrinkCapacity(size_type aElemSize);

  // Resizes the storage to 0. This may only be called when Length() is already
  // 0.
  void ShrinkCapacityToZero();

  // This method may be called to resize a "gap" in the array by shifting
  // elements around.  It updates mLength appropriately.  If the resulting
  // array has zero elements, then the array's memory is free'd.
  // @param aStart     The starting index of the gap.
  // @param aOldLen    The current length of the gap.
  // @param aNewLen    The desired length of the gap.
  // @param aElemSize  The size of an array element.
  template <typename Alloc>
  void ShiftData(index_type aStart, size_type aOldLen, size_type aNewLen,
                 size_type aElemSize);

  // This method may be called to swap elements from the end of the array to
  // fill a "gap" in the array. If the resulting array has zero elements, then
  // the array's memory is free'd.
  // @param aStart     The starting index of the gap.
  // @param aCount     The length of the gap.
  // @param aElemSize  The size of an array element.
  template <typename Alloc>
  void SwapFromEnd(index_type aStart, size_type aCount, size_type aElemSize);

  // This method increments the length member of the array's header.
  // Note that mHdr may actually be sEmptyTArrayHeader in the case where a
  // zero-length array is inserted into our array. But then aNum should
  // always be 0.
  void IncrementLength(size_t aNum) {
    if (HasEmptyHeader()) {
      if (MOZ_UNLIKELY(aNum != 0)) {
        // Writing a non-zero length to the empty header would be extremely bad.
        MOZ_CRASH();
      }
    } else {
      mHdr->mLength += aNum;
    }
  }

  // This method inserts blank slots into the array.
  // @param aIndex the place to insert the new elements. This must be no
  //               greater than the current length of the array.
  // @param aCount the number of slots to insert
  // @param aElementSize the size of an array element.
  template <typename Alloc>
  typename Alloc::ResultTypeProxy InsertSlotsAt(index_type aIndex,
                                                size_type aCount,
                                                size_type aElementSize);

  template <typename Alloc>
  typename Alloc::ResultTypeProxy SwapArrayElements(
      nsTArray_base<RelocationStrategy>& aOther, size_type aElemSize);

  void MoveConstructNonAutoArray(nsTArray_base<RelocationStrategy>& aOther,
                                 size_type aElemSize);

  void MoveInit(nsTArray_base<RelocationStrategy>& aOther, size_type aElemSize);

  // Helper function for move construction and SwapArrayElements.
  // Takes the storage from the nsTArray as a non-auto Header pointer.
  // If the array is holding a reference to an AutoTArray buffer,
  // it will be moved to the heap before being returned.
  template <typename Alloc>
  Header* TakeHeaderForMove(size_type aElemSize);

  // Returns whether we're using our auto-array inline buffer.
  bool UsesAutoArrayBuffer() const { return mHdr == GetAutoArrayHeader(); }
  Header* GetAutoArrayHeader() const {
    if (!mHdr->mIsAutoArray) {
      return nullptr;
    }
    return const_cast<Header*>(reinterpret_cast<const Header*>(
        reinterpret_cast<const uint8_t*>(this) + kAutoTArrayHeaderOffset));
  }

  // The array's elements (prefixed with a Header).  This pointer is never
  // null.  If the array is empty, then this will point to sEmptyTArrayHeader.
  Header* mHdr{EmptyHdr()};

  Header* Hdr() const MOZ_NONNULL_RETURN { return mHdr; }
  Header** PtrToHdr() MOZ_NONNULL_RETURN { return &mHdr; }
  static constexpr Header* EmptyHdr() MOZ_NONNULL_RETURN {
    return const_cast<Header*>(&sEmptyTArrayHeader);
  }

  [[nodiscard]] bool HasEmptyHeader() const { return mHdr == EmptyHdr(); }
};

namespace detail {

// Used for argument checking in nsTArrayElementTraits::Emplace.
template <typename... T>
struct ChooseFirst;

template <>
struct ChooseFirst<> {
  // Choose a default type that is guaranteed to not match E* for any
  // nsTArray<E>.
  typedef void Type;
};

template <typename A, typename... Args>
struct ChooseFirst<A, Args...> {
  typedef A Type;
};

}  // namespace detail

//
// This class defines convenience functions for element specific operations.
// Specialize this template if necessary.
//
template <class E>
class nsTArrayElementTraits {
 public:
  // Invoke the default constructor in place.
  static inline void Construct(E* aE) {
    // Do NOT call "E()"! That triggers C++ "default initialization"
    // which zeroes out POD ("plain old data") types such as regular
    // ints.  We don't want that because it can be a performance issue
    // and people don't expect it; nsTArray should work like a regular
    // C/C++ array in this respect.
    new (static_cast<void*>(aE)) E;
  }
  // Invoke the copy-constructor in place.
  template <class A>
  static inline void Construct(E* aE, A&& aArg) {
    using E_NoCV = std::remove_cv_t<E>;
    using A_NoCV = std::remove_cv_t<A>;
    static_assert(!std::is_same_v<E_NoCV*, A_NoCV>,
                  "For safety, we disallow constructing nsTArray<E> elements "
                  "from E* pointers. See bug 960591.");
    new (static_cast<void*>(aE)) E(std::forward<A>(aArg));
  }
  // Construct in place.
  template <class... Args>
  static inline void Emplace(E* aE, Args&&... aArgs) {
    using E_NoCV = std::remove_cv_t<E>;
    using A_NoCV =
        std::remove_cv_t<typename ::detail::ChooseFirst<Args...>::Type>;
    static_assert(!std::is_same_v<E_NoCV*, A_NoCV>,
                  "For safety, we disallow constructing nsTArray<E> elements "
                  "from E* pointers. See bug 960591.");
    new (static_cast<void*>(aE)) E(std::forward<Args>(aArgs)...);
  }
  // Invoke the destructor in place.
  static inline void Destruct(E* aE) { aE->~E(); }
};

// The default comparator used by nsTArray
template <class A, class B>
class nsDefaultComparator {
 public:
  bool Equals(const A& aA, const B& aB) const { return aA == aB; }
  bool LessThan(const A& aA, const B& aB) const { return aA < aB; }
};

//
// Normally elements are copied with memcpy and memmove, but for some element
// types that is problematic.  The nsTArray_RelocationStrategy template class
// can be specialized to ensure that copying calls constructors and destructors
// instead, as is done below for JS::Heap<E> elements.
//

//
// A class that defines how to copy elements using memcpy/memmove.
//
struct nsTArray_RelocateUsingMemutils {
  const static bool allowRealloc = true;

  static void RelocateNonOverlappingRegionWithHeader(void* aDest,
                                                     const void* aSrc,
                                                     size_t aCount,
                                                     size_t aElemSize) {
    memcpy(aDest, aSrc, sizeof(nsTArrayHeader) + aCount * aElemSize);
  }

  static void RelocateOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
                                        size_t aElemSize) {
    memmove(aDest, aSrc, aCount * aElemSize);
  }

  static void RelocateNonOverlappingRegion(void* aDest, void* aSrc,
                                           size_t aCount, size_t aElemSize) {
    memcpy(aDest, aSrc, aCount * aElemSize);
  }
};

//
// A template class that defines how to relocate elements using the type's move
// constructor and destructor appropriately.
//
template <class ElemType>
struct nsTArray_RelocateUsingMoveConstructor {
  typedef nsTArrayElementTraits<ElemType> traits;

  const static bool allowRealloc = false;

  static void RelocateNonOverlappingRegionWithHeader(void* aDest, void* aSrc,
                                                     size_t aCount,
                                                     size_t aElemSize) {
    nsTArrayHeader* destHeader = static_cast<nsTArrayHeader*>(aDest);
    nsTArrayHeader* srcHeader = static_cast<nsTArrayHeader*>(aSrc);
    *destHeader = *srcHeader;
    RelocateNonOverlappingRegion(
        static_cast<uint8_t*>(aDest) + sizeof(nsTArrayHeader),
        static_cast<uint8_t*>(aSrc) + sizeof(nsTArrayHeader), aCount,
        aElemSize);
  }

  // RelocateNonOverlappingRegion and RelocateOverlappingRegion are defined by
  // analogy with memmove and memcpy that are used for relocation of
  // trivially-relocatable types through nsTArray_RelocateUsingMemutils. What
  // they actually do is slightly different: RelocateOverlappingRegion checks to
  // see which direction the movement needs to take place, whether from
  // back-to-front of the range to be moved or from front-to-back.
  // RelocateNonOverlappingRegion assumes that relocating front-to-back is
  // always valid.  They use RelocateRegionForward and RelocateRegionBackward,
  // which are analogous to std::move and std::move_backward respectively,
  // except they don't move-assign the destination from the source but
  // move-construct the destination from the source and destroy the source.
  static void RelocateOverlappingRegion(void* aDest, void* aSrc, size_t aCount,
                                        size_t aElemSize) {
    ElemType* destBegin = static_cast<ElemType*>(aDest);
    ElemType* srcBegin = static_cast<ElemType*>(aSrc);

    // If destination and source are the same, this is a no-op.
    // In practice, we don't do this.
    if (destBegin == srcBegin) {
      return;
    }

    ElemType* srcEnd = srcBegin + aCount;
    ElemType* destEnd = destBegin + aCount;

    // Figure out whether to relocate back-to-front or front-to-back.
    if (srcEnd > destBegin && srcEnd < destEnd) {
      RelocateRegionBackward(srcBegin, srcEnd, destEnd);
    } else {
      RelocateRegionForward(srcBegin, srcEnd, destBegin);
    }
  }

  static void RelocateNonOverlappingRegion(void* aDest, void* aSrc,
                                           size_t aCount, size_t aElemSize) {
    ElemType* destBegin = static_cast<ElemType*>(aDest);
    ElemType* srcBegin = static_cast<ElemType*>(aSrc);
    ElemType* srcEnd = srcBegin + aCount;
#ifdef DEBUG
    ElemType* destEnd = destBegin + aCount;
    MOZ_ASSERT(srcEnd <= destBegin || srcBegin >= destEnd);
#endif
    RelocateRegionForward(srcBegin, srcEnd, destBegin);
  }

 private:
  static void RelocateRegionForward(ElemType* srcBegin, ElemType* srcEnd,
                                    ElemType* destBegin) {
    ElemType* srcElem = srcBegin;
    ElemType* destElem = destBegin;

    while (srcElem != srcEnd) {
      RelocateElement(srcElem, destElem);
      ++destElem;
      ++srcElem;
    }
  }

  static void RelocateRegionBackward(ElemType* srcBegin, ElemType* srcEnd,
                                     ElemType* destEnd) {
    ElemType* srcElem = srcEnd;
    ElemType* destElem = destEnd;
    while (srcElem != srcBegin) {
      --destElem;
      --srcElem;
      RelocateElement(srcElem, destElem);
    }
  }

  static void RelocateElement(ElemType* srcElem, ElemType* destElem) {
    traits::Construct(destElem, std::move(*srcElem));
    traits::Destruct(srcElem);
  }
};

//
// The default behaviour is to use memcpy/memmove for everything.
//
template <class E>
struct MOZ_NEEDS_MEMMOVABLE_TYPE nsTArray_RelocationStrategy {
  using Type = nsTArray_RelocateUsingMemutils;
};

//
// Some classes require constructors/destructors to be called, so they are
// specialized here.
//
#define MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(E)     \
  template <>                                              \
  struct nsTArray_RelocationStrategy<E> {                  \
    using Type = nsTArray_RelocateUsingMoveConstructor<E>; \
  };

#define MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(T) \
  template <typename S>                                             \
  struct nsTArray_RelocationStrategy<T<S>> {                        \
    using Type = nsTArray_RelocateUsingMoveConstructor<T<S>>;       \
  };

MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(JS::Heap)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(std::function)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR_FOR_TEMPLATE(mozilla::ipc::Endpoint)

MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(nsRegion)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(nsIntRegion)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::layers::TileClient)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
    mozilla::SerializedStructuredCloneBuffer)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
    mozilla::dom::indexedDB::ObjectStoreCursorResponse)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
    mozilla::dom::indexedDB::IndexCursorResponse)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(
    mozilla::dom::indexedDB::SerializedStructuredCloneReadInfo);
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(JSStructuredCloneData)
MOZ_DECLARE_RELOCATE_USING_MOVE_CONSTRUCTOR(mozilla::SourceBufferTask)

namespace detail {

// These helpers allow us to differentiate between tri-state comparator
// functions and classes with LessThan() and Equal() methods. If an object, when
// called as a function with two instances of our element type, returns an int,
// we treat it as a tri-state comparator.
//
// T is the type of the comparator object we want to check. L and R are the
// types that we'll be comparing.
//
// V is never passed, and is only used to allow us to specialize on the return
// value of the comparator function.
template <typename T, typename L, typename R, typename V = int>
struct IsCompareMethod : std::false_type {};

template <typename T, typename L, typename R>
struct IsCompareMethod<
    T, L, R, decltype(std::declval<T>()(std::declval<L>(), std::declval<R>()))>
    : std::true_type {};

// These two wrappers allow us to use either a tri-state comparator, or an
// object with Equals() and LessThan() methods interchangeably. They provide a
// tri-state Compare() method, and Equals() method, and a LessThan() method.
//
// Depending on the type of the underlying comparator, they either pass these
// through directly, or synthesize them from the methods available on the
// comparator.
//
// Callers should always use the most-specific of these methods that match their
// purpose.

// Comparator wrapper for a tri-state comparator function
template <typename T, typename L, typename R,
          bool IsCompare = IsCompareMethod<T, L, R>::value>
struct CompareWrapper {
#ifdef _MSC_VER
#  pragma warning(push)
#  pragma warning(disable : 4180) /* Silence "qualifier applied to function \
                                     type has no meaning" warning */
#endif
  MOZ_IMPLICIT CompareWrapper(const T& aComparator)
      : mComparator(aComparator) {}

  template <typename A, typename B>
  int Compare(A& aLeft, B& aRight) const {
    return mComparator(aLeft, aRight);
  }

  template <typename A, typename B>
  bool Equals(A& aLeft, B& aRight) const {
    return Compare(aLeft, aRight) == 0;
  }

  template <typename A, typename B>
  bool LessThan(A& aLeft, B& aRight) const {
    return Compare(aLeft, aRight) < 0;
  }

  const T& mComparator;
#ifdef _MSC_VER
#  pragma warning(pop)
#endif
};

// Comparator wrapper for a class with Equals() and LessThan() methods.
template <typename T, typename L, typename R>
struct CompareWrapper<T, L, R, false> {
  MOZ_IMPLICIT CompareWrapper(const T& aComparator)
      : mComparator(aComparator) {}

  template <typename A, typename B>
  int Compare(A& aLeft, B& aRight) const {
    if (LessThan(aLeft, aRight)) {
      return -1;
    }
    if (Equals(aLeft, aRight)) {
      return 0;
    }
    return 1;
  }

  template <typename A, typename B>
  bool Equals(A& aLeft, B& aRight) const {
    return mComparator.Equals(aLeft, aRight);
  }

  template <typename A, typename B>
  bool LessThan(A& aLeft, B& aRight) const {
    return mComparator.LessThan(aLeft, aRight);
  }

  const T& mComparator;
};

}  // namespace detail

enum class SortBoundsCheck { Enable, Disable };

//
// nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,
// AutoTArray.
//
// The only situation in which you might need to use nsTArray_Impl in your code
// is if you're writing code which mutates a TArray which may or may not be
// infallible.
//
// Code which merely reads from a TArray which may or may not be infallible can
// simply cast the TArray to |const nsTArray&|; both fallible and infallible
// TArrays can be cast to |const nsTArray&|.
//
template <class E, class Alloc>
class nsTArray_Impl
    : public nsTArray_base<typename nsTArray_RelocationStrategy<E>::Type> {
 private:
  friend class nsTArray<E>;

  typedef nsTArrayFallibleAllocator FallibleAlloc;
  typedef nsTArrayInfallibleAllocator InfallibleAlloc;

 public:
  typedef typename nsTArray_RelocationStrategy<E>::Type relocation_type;
  typedef nsTArray_base<relocation_type> base_type;
  typedef typename base_type::size_type size_type;
  typedef typename base_type::index_type index_type;
  typedef E value_type;
  typedef nsTArray_Impl<E, Alloc> self_type;
  typedef nsTArrayElementTraits<E> elem_traits;
  typedef mozilla::ArrayIterator<value_type&, self_type> iterator;
  typedef mozilla::ArrayIterator<const value_type&, self_type> const_iterator;
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  using base_type::EmptyHdr;

  // A special value that is used to indicate an invalid or unknown index
  // into the array.
  static const index_type NoIndex = index_type(-1);

  using base_type::Length;

  //
  // Finalization method
  //

  ~nsTArray_Impl() {
    if (!base_type::IsEmpty()) {
      ClearAndRetainStorage();
    }
    // mHdr cleanup will be handled by base destructor
  }

  //
  // Initialization methods
  //

  nsTArray_Impl() = default;

  // Initialize this array and pre-allocate some number of elements.
  explicit nsTArray_Impl(size_type aCapacity) { SetCapacity(aCapacity); }

  // Initialize this array with an r-value.
  // Allow different types of allocators, since the allocator doesn't matter.
  template <typename Allocator>
  explicit nsTArray_Impl(nsTArray_Impl<E, Allocator>&& aOther) noexcept {
    // We cannot be a (Copyable)AutoTArray because that overrides this ctor.
    MOZ_ASSERT(!this->UsesAutoArrayBuffer());

    // This does not use SwapArrayElements because that's unnecessarily complex.
    this->MoveConstructNonAutoArray(aOther, sizeof(value_type));
  }

  // The array's copy-constructor performs a 'deep' copy of the given array.
  // @param aOther The array object to copy.
  //
  // It's very important that we declare this method as taking |const
  // self_type&| as opposed to taking |const nsTArray_Impl<E, OtherAlloc>| for
  // an arbitrary OtherAlloc.
  //
  // If we don't declare a constructor taking |const self_type&|, C++ generates
  // a copy-constructor for this class which merely copies the object's
  // members, which is obviously wrong.
  //
  // You can pass an nsTArray_Impl<E, OtherAlloc> to this method because
  // nsTArray_Impl<E, X> can be cast to const nsTArray_Impl<E, Y>&.  So the
  // effect on the API is the same as if we'd declared this method as taking
  // |const nsTArray_Impl<E, OtherAlloc>&|.
  nsTArray_Impl(const nsTArray_Impl&) = default;

  // Allow converting to a const array with a different kind of allocator,
  // Since the allocator doesn't matter for const arrays
  template <typename Allocator>
  [[nodiscard]] operator const nsTArray_Impl<E, Allocator>&() const& {
    return *reinterpret_cast<const nsTArray_Impl<E, Allocator>*>(this);
  }
  // And we have to do this for our subclasses too
  [[nodiscard]] operator const nsTArray<E>&() const& {
    return *reinterpret_cast<const nsTArray<E>*>(this);
  }
  [[nodiscard]] operator const FallibleTArray<E>&() const& {
    return *reinterpret_cast<const FallibleTArray<E>*>(this);
  }

  // The array's assignment operator performs a 'deep' copy of the given
  // array.  It is optimized to reuse existing storage if possible.
  // @param aOther The array object to copy.
  nsTArray_Impl& operator=(const nsTArray_Impl&) = default;

  // The array's move assignment operator steals the underlying data from
  // the other array.
  // @param other  The array object to move from.
  self_type& operator=(self_type&& aOther) {
    if (this != &aOther) {
      Clear();
      this->MoveInit(aOther, sizeof(value_type));
    }
    return *this;
  }

  // Return true if this array has the same length and the same
  // elements as |aOther|.
  template <typename Allocator>
  [[nodiscard]] bool operator==(
      const nsTArray_Impl<E, Allocator>& aOther) const {
    size_type len = Length();
    if (len != aOther.Length()) {
      return false;
    }

    // XXX std::equal would be as fast or faster here
    for (index_type i = 0; i < len; ++i) {
      if (!(operator[](i) == aOther[i])) {
        return false;
      }
    }

    return true;
  }

  // Return true if this array does not have the same length and the same
  // elements as |aOther|.
  [[nodiscard]] bool operator!=(const self_type& aOther) const {
    return !operator==(aOther);
  }

  // If Alloc == FallibleAlloc, ReplaceElementsAt might fail, without a way to
  // signal this to the caller, so we disallow copying via operator=. Callers
  // should use ReplaceElementsAt with a fallible argument instead, and check
  // the result.
  template <typename Allocator,
            typename = std::enable_if_t<std::is_same_v<Alloc, InfallibleAlloc>,
                                        Allocator>>
  self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther) {
    AssignInternal<InfallibleAlloc>(aOther.Elements(), aOther.Length());
    return *this;
  }

  template <typename Allocator>
  self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther) {
    Clear();
    this->MoveInit(aOther, sizeof(value_type));
    return *this;
  }

  // @return The amount of memory used by this nsTArray_Impl, excluding
  // sizeof(*this). If you want to measure anything hanging off the array, you
  // must iterate over the elements and measure them individually; hence the
  // "Shallow" prefix.
  [[nodiscard]] size_t ShallowSizeOfExcludingThis(
      mozilla::MallocSizeOf aMallocSizeOf) const {
    if (this->UsesAutoArrayBuffer() || this->HasEmptyHeader()) {
      return 0;
    }
    return aMallocSizeOf(this->Hdr());
  }

  // @return The amount of memory used by this nsTArray_Impl, including
  // sizeof(*this). If you want to measure anything hanging off the array, you
  // must iterate over the elements and measure them individually; hence the
  // "Shallow" prefix.
  [[nodiscard]] size_t ShallowSizeOfIncludingThis(
      mozilla::MallocSizeOf aMallocSizeOf) const {
    return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
  }

  //
  // Accessor methods
  //

  // This method provides direct access to the array elements.
  // @return A pointer to the first element of the array.  If the array is
  // empty, then this pointer must not be dereferenced.
  [[nodiscard]] value_type* Elements() MOZ_NONNULL_RETURN {
    return reinterpret_cast<value_type*>(Hdr() + 1);
  }

  // This method provides direct, readonly access to the array elements.
  // @return A pointer to the first element of the array.  If the array is
  // empty, then this pointer must not be dereferenced.
  [[nodiscard]] const value_type* Elements() const MOZ_NONNULL_RETURN {
    return reinterpret_cast<const value_type*>(Hdr() + 1);
  }

  // This method provides direct access to an element of the array. The given
  // index must be within the array bounds.
  // @param aIndex The index of an element in the array.
  // @return A reference to the i'th element of the array.
  [[nodiscard]] value_type& ElementAt(index_type aIndex) {
    if (MOZ_UNLIKELY(aIndex >= Length())) {
      mozilla::detail::InvalidArrayIndex_CRASH(aIndex, Length());
    }
    return Elements()[aIndex];
  }

  // This method provides direct, readonly access to an element of the array
  // The given index must be within the array bounds.
  // @param aIndex The index of an element in the array.
  // @return A const reference to the i'th element of the array.
  [[nodiscard]] const value_type& ElementAt(index_type aIndex) const {
    if (MOZ_UNLIKELY(aIndex >= Length())) {
      mozilla::detail::InvalidArrayIndex_CRASH(aIndex, Length());
    }
    return Elements()[aIndex];
  }

  // This method provides direct access to an element of the array in a bounds
  // safe manner. If the requested index is out of bounds the provided default
  // value is returned.
  // @param aIndex The index of an element in the array.
  // @param aDef   The value to return if the index is out of bounds.
  [[nodiscard]] value_type& SafeElementAt(index_type aIndex, value_type& aDef) {
    return aIndex < Length() ? Elements()[aIndex] : aDef;
  }

  // This method provides direct access to an element of the array in a bounds
  // safe manner. If the requested index is out of bounds the provided default
  // value is returned.
  // @param aIndex The index of an element in the array.
  // @param aDef   The value to return if the index is out of bounds.
  [[nodiscard]] const value_type& SafeElementAt(index_type aIndex,
                                                const value_type& aDef) const {
    return aIndex < Length() ? Elements()[aIndex] : aDef;
  }

  [[nodiscard]] auto SafeElementAt(index_type aIndex) const {
    typename ::detail::SafeElementAtPointerValue<E>::type result;
    if (aIndex < Length()) {
      result = Elements()[aIndex];
    } else {
      result = nullptr;
    }
    return result;
  }

  // Shorthand for ElementAt(aIndex)
  [[nodiscard]] value_type& operator[](index_type aIndex) {
    return ElementAt(aIndex);
  }

  // Shorthand for ElementAt(aIndex)
  [[nodiscard]] const value_type& operator[](index_type aIndex) const {
    return ElementAt(aIndex);
  }

  // Shorthand for ElementAt(length - 1)
  [[nodiscard]] value_type& LastElement() { return ElementAt(Length() - 1); }

  // Shorthand for ElementAt(length - 1)
  [[nodiscard]] const value_type& LastElement() const {
    return ElementAt(Length() - 1);
  }

  // Shorthand for SafeElementAt(length - 1, def)
  [[nodiscard]] value_type& SafeLastElement(value_type& aDef) {
    return SafeElementAt(Length() - 1, aDef);
  }

  // Shorthand for SafeElementAt(length - 1, def)
  [[nodiscard]] const value_type& SafeLastElement(
      const value_type& aDef) const {
    return SafeElementAt(Length() - 1, aDef);
  }

  // Methods for range-based for loops.
  [[nodiscard]] iterator begin() { return iterator(*this, 0); }
  [[nodiscard]] const_iterator begin() const {
    return const_iterator(*this, 0);
  }
  [[nodiscard]] const_iterator cbegin() const { return begin(); }
  [[nodiscard]] iterator end() { return iterator(*this, Length()); }
  [[nodiscard]] const_iterator end() const {
    return const_iterator(*this, Length());
  }
  [[nodiscard]] const_iterator cend() const { return end(); }

  // Methods for reverse iterating.
  [[nodiscard]] reverse_iterator rbegin() { return reverse_iterator(end()); }
  [[nodiscard]] const_reverse_iterator rbegin() const {
    return const_reverse_iterator(end());
  }
  [[nodiscard]] const_reverse_iterator crbegin() const { return rbegin(); }
  [[nodiscard]] reverse_iterator rend() { return reverse_iterator(begin()); }
  [[nodiscard]] const_reverse_iterator rend() const {
    return const_reverse_iterator(begin());
  }
  [[nodiscard]] const_reverse_iterator crend() const { return rend(); }

  // Span integration

  [[nodiscard]] operator mozilla::Span<value_type>() {
    return mozilla::Span<value_type>(Elements(), Length());
  }

  [[nodiscard]] operator mozilla::Span<const value_type>() const {
    return mozilla::Span<const value_type>(Elements(), Length());
  }

  //
  // Search methods
  //

  // This method searches for the first element in this array that is equal
  // to the given element.
  // @param aItem  The item to search for.
  // @param aComp  The Comparator used to determine element equality.
  // @return       true if the element was found.
  template <class Item, class Comparator>
  [[nodiscard]] bool Contains(const Item& aItem,
                              const Comparator& aComp) const {
    return ApplyIf(
        aItem, 0, aComp, []() { return true; }, []() { return false; });
  }

  // Like Contains(), but assumes a sorted array.
  template <class Item, class Comparator>
  [[nodiscard]] bool ContainsSorted(const Item& aItem,
                                    const Comparator& aComp) const {
    return BinaryIndexOf(aItem, aComp) != NoIndex;
  }

  // This method searches for the first element in this array that is equal
  // to the given element.  This method assumes that 'operator==' is defined
  // for value_type.
  // @param aItem  The item to search for.
  // @return       true if the element was found.
  template <class Item>
  [[nodiscard]] bool Contains(const Item& aItem) const {
    return Contains(aItem, nsDefaultComparator<value_type, Item>());
  }

  // Like Contains(), but assumes a sorted array.
  template <class Item>
  [[nodiscard]] bool ContainsSorted(const Item& aItem) const {
    return BinaryIndexOf(aItem) != NoIndex;
  }

  // This method searches for the offset of the first element in this
  // array that is equal to the given element.
  // @param aItem  The item to search for.
  // @param aStart The index to start from.
  // @param aComp  The Comparator used to determine element equality.
  // @return       The index of the found element or NoIndex if not found.
  template <class Item, class Comparator>
  [[nodiscard]] index_type IndexOf(const Item& aItem, index_type aStart,
                                   const Comparator& aComp) const {
    ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);

    const value_type* iter = Elements() + aStart;
    const value_type* iend = Elements() + Length();
    for (; iter != iend; ++iter) {
      if (comp.Equals(*iter, aItem)) {
        return index_type(iter - Elements());
      }
    }
    return NoIndex;
  }

  // This method searches for the offset of the first element in this
  // array that is equal to the given element.  This method assumes
  // that 'operator==' is defined for value_type.
  // @param aItem  The item to search for.
  // @param aStart The index to start from.
  // @return       The index of the found element or NoIndex if not found.
  template <class Item>
  [[nodiscard]] index_type IndexOf(const Item& aItem,
                                   index_type aStart = 0) const {
    return IndexOf(aItem, aStart, nsDefaultComparator<value_type, Item>());
  }

  // This method searches for the offset of the last element in this
  // array that is equal to the given element.
  // @param aItem  The item to search for.
  // @param aStart The index to start from.  If greater than or equal to the
  //               length of the array, then the entire array is searched.
  // @param aComp  The Comparator used to determine element equality.
  // @return       The index of the found element or NoIndex if not found.
  template <class Item, class Comparator>
  [[nodiscard]] index_type LastIndexOf(const Item& aItem, index_type aStart,
                                       const Comparator& aComp) const {
    ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);

    size_type endOffset = aStart >= Length() ? Length() : aStart + 1;
    const value_type* iend = Elements() - 1;
    const value_type* iter = iend + endOffset;
    for (; iter != iend; --iter) {
      if (comp.Equals(*iter, aItem)) {
        return index_type(iter - Elements());
      }
    }
    return NoIndex;
  }

  // This method searches for the offset of the last element in this
  // array that is equal to the given element.  This method assumes
  // that 'operator==' is defined for value_type.
  // @param aItem  The item to search for.
  // @param aStart The index to start from.  If greater than or equal to the
  //               length of the array, then the entire array is searched.
  // @return       The index of the found element or NoIndex if not found.
  template <class Item>
  [[nodiscard]] index_type LastIndexOf(const Item& aItem,
                                       index_type aStart = NoIndex) const {
    return LastIndexOf(aItem, aStart, nsDefaultComparator<value_type, Item>());
  }

  // This method searches for the offset for the element in this array
  // that is equal to the given element. The array is assumed to be sorted.
  // If there is more than one equivalent element, there is no guarantee
  // on which one will be returned.
  // @param aItem  The item to search for.
  // @param aComp  The Comparator used.
  // @return       The index of the found element or NoIndex if not found.
  template <class Item, class Comparator>
  [[nodiscard]] index_type BinaryIndexOf(const Item& aItem,
                                         const Comparator& aComp) const {
    using mozilla::BinarySearchIf;
    ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);

    size_t index;
    bool found = BinarySearchIf(
        Elements(), 0, Length(),
        // Note: We pass the Compare() args here in reverse order and negate the
        // results for compatibility reasons. Some existing callers use Equals()
        // functions with first arguments which match aElement but not aItem, or
        // second arguments that match aItem but not aElement. To accommodate
        // those callers, we preserve the argument order of the older version of
        // this API. These callers, however, should be fixed, and this special
        // case removed.
        [&](const value_type& aElement) {
          return -comp.Compare(aElement, aItem);
        },
        &index);
    return found ? index : NoIndex;
  }

  // This method searches for the offset for the element in this array
  // that is equal to the given element. The array is assumed to be sorted.
  // This method assumes that 'operator==' and 'operator<' are defined.
  // @param aItem  The item to search for.
  // @return       The index of the found element or NoIndex if not found.
  template <class Item>
  [[nodiscard]] index_type BinaryIndexOf(const Item& aItem) const {
    return BinaryIndexOf(aItem, nsDefaultComparator<value_type, Item>());
  }

  //
  // Mutation methods
  //
 private:
  template <typename ActualAlloc, class Item>
  typename ActualAlloc::ResultType AssignInternal(const Item* aArray,
                                                  size_type aArrayLen);

 public:
  template <class Allocator, typename ActualAlloc = Alloc>
  [[nodiscard]] typename ActualAlloc::ResultType Assign(
      const nsTArray_Impl<E, Allocator>& aOther) {
    return AssignInternal<ActualAlloc>(aOther.Elements(), aOther.Length());
  }

  template <class Allocator>
  [[nodiscard]] bool Assign(const nsTArray_Impl<E, Allocator>& aOther,
                            const mozilla::fallible_t&) {
    return Assign<Allocator, FallibleAlloc>(aOther);
  }

  template <class Allocator>
  void Assign(nsTArray_Impl<E, Allocator>&& aOther) {
    Clear();
    this->MoveInit(aOther, sizeof(value_type));
  }

  // This method call the destructor on each element of the array, empties it,
  // but does not shrink the array's capacity.
  // See also SetLengthAndRetainStorage.
  // Make sure to call Compact() if needed to avoid keeping a huge array
  // around.
  MOZ_REINITIALIZES void ClearAndRetainStorage() {
    if (this->HasEmptyHeader()) {
      return;
    }

    DestructRange(0, Length());
    base_type::mHdr->mLength = 0;
  }

  // This method modifies the length of the array, but unlike SetLength
  // it doesn't deallocate/reallocate the current internal storage.
  // The new length MUST be shorter than or equal to the current capacity.
  // If the new length is larger than the existing length of the array,
  // then new elements will be constructed using value_type's default
  // constructor.  If shorter, elements will be destructed and removed.
  // See also ClearAndRetainStorage.
  // @param aNewLen  The desired length of this array.
  void SetLengthAndRetainStorage(size_type aNewLen) {
    MOZ_ASSERT(aNewLen <= base_type::Capacity());
    size_type oldLen = Length();
    if (aNewLen > oldLen) {
      /// XXX(Bug 1631367) SetLengthAndRetainStorage should be disabled for
      /// FallibleTArray.
      InsertElementsAtInternal<InfallibleAlloc>(oldLen, aNewLen - oldLen);
      return;
    }
    if (aNewLen < oldLen) {
      DestructRange(aNewLen, oldLen - aNewLen);
      base_type::mHdr->mLength = aNewLen;
    }
  }

  // This method replaces a range of elements in this array.
  // @param aStart    The starting index of the elements to replace.
  // @param aCount    The number of elements to replace.  This may be zero to
  //                  insert elements without removing any existing elements.
  // @param aArray    The values to copy into this array.  Must be non-null,
  //                  and these elements must not already exist in the array
  //                  being modified.
  // @param aArrayLen The number of values to copy into this array.
  // @return          A pointer to the new elements in the array, or null if
  //                  the operation failed due to insufficient memory.
 private:
  template <typename ActualAlloc, class Item>
  value_type* ReplaceElementsAtInternal(index_type aStart, size_type aCount,
                                        const Item* aArray,
                                        size_type aArrayLen);

 public:
  template <class Item>
  [[nodiscard]] value_type* ReplaceElementsAt(index_type aStart,
                                              size_type aCount,
                                              const Item* aArray,
                                              size_type aArrayLen,
                                              const mozilla::fallible_t&) {
    return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aArray,
                                                    aArrayLen);
  }

  // A variation on the ReplaceElementsAt method defined above.
  template <class Item>
  [[nodiscard]] value_type* ReplaceElementsAt(index_type aStart,
                                              size_type aCount,
                                              const nsTArray<Item>& aArray,
                                              const mozilla::fallible_t&) {
    return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aArray);
  }

  template <class Item>
  [[nodiscard]] value_type* ReplaceElementsAt(index_type aStart,
                                              size_type aCount,
                                              mozilla::Span<Item> aSpan,
                                              const mozilla::fallible_t&) {
    return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aSpan);
  }

  // A variation on the ReplaceElementsAt method defined above.
  template <class Item>
  [[nodiscard]] value_type* ReplaceElementsAt(index_type aStart,
                                              size_type aCount,
                                              const Item& aItem,
                                              const mozilla::fallible_t&) {
    return ReplaceElementsAtInternal<FallibleAlloc>(aStart, aCount, aItem);
  }

  // A variation on the ReplaceElementsAt method defined above.
  template <class Item>
  mozilla::NotNull<value_type*> ReplaceElementAt(index_type aIndex,
                                                 Item&& aItem) {
    value_type* const elem = &ElementAt(aIndex);
    elem_traits::Destruct(elem);
    elem_traits::Construct(elem, std::forward<Item>(aItem));
    return mozilla::WrapNotNullUnchecked(elem);
  }

  // InsertElementsAt is ReplaceElementsAt with 0 elements to replace.
  // XXX Provide a proper documentation of InsertElementsAt.
  template <class Item>
  [[nodiscard]] value_type* InsertElementsAt(index_type aIndex,
                                             const Item* aArray,
                                             size_type aArrayLen,
                                             const mozilla::fallible_t&) {
    return ReplaceElementsAtInternal<FallibleAlloc>(aIndex, 0, aArray,
                                                    aArrayLen);
  }

  template <class Item, class Allocator>
  [[nodiscard]] value_type* InsertElementsAt(
      index_type aIndex, const nsTArray_Impl<Item, Allocator>& aArray,
      const mozilla::fallible_t&) {
    return ReplaceElementsAtInternal<FallibleAlloc>(
        aIndex, 0, aArray.Elements(), aArray.Length());
  }

  template <class Item>
  [[nodiscard]] value_type* InsertElementsAt(index_type aIndex,
                                             mozilla::Span<Item> aSpan,
                                             const mozilla::fallible_t&) {
    return ReplaceElementsAtInternal<FallibleAlloc>(aIndex, 0, aSpan.Elements(),
                                                    aSpan.Length());
  }

 private:
  template <typename ActualAlloc>
  value_type* InsertElementAtInternal(index_type aIndex);

  // Insert a new element without copy-constructing. This is useful to avoid
  // temporaries.
  // @return A pointer to the newly inserted element, or null on OOM.
 public:
  [[nodiscard]] value_type* InsertElementAt(index_type aIndex,
                                            const mozilla::fallible_t&) {
    return InsertElementAtInternal<FallibleAlloc>(aIndex);
  }

 private:
  template <typename ActualAlloc, class Item>
  value_type* InsertElementAtInternal(index_type aIndex, Item&& aItem);

  // Insert a new element, move constructing if possible.
 public:
  template <class Item>
  [[nodiscard]] value_type* InsertElementAt(index_type aIndex, Item&& aItem,
                                            const mozilla::fallible_t&) {
    return InsertElementAtInternal<FallibleAlloc>(aIndex,
                                                  std::forward<Item>(aItem));
  }

  // Reconstruct the element at the given index, and return a pointer to the
  // reconstructed element.  This will destroy the existing element and
  // default-construct a new one, giving you a state much like what single-arg
  // InsertElementAt(), or no-arg AppendElement() does, but without changing the
  // length of the array.
  //
  // array[idx] = value_type()
  //
  // would accomplish the same thing as long as value_type has the appropriate
  // moving operator=, but some types don't for various reasons.
  mozilla::NotNull<value_type*> ReconstructElementAt(index_type aIndex) {
    value_type* elem = &ElementAt(aIndex);
    elem_traits::Destruct(elem);
    elem_traits::Construct(elem);
    return mozilla::WrapNotNullUnchecked(elem);
  }

  // This method searches for the smallest index of an element that is strictly
  // greater than |aItem|. If |aItem| is inserted at this index, the array will
  // remain sorted and |aItem| would come after all elements that are equal to
  // it. If |aItem| is greater than or equal to all elements in the array, the
  // array length is returned.
  //
  // Note that consumers who want to know whether there are existing items equal
  // to |aItem| in the array can just check that the return value here is > 0
  // and indexing into the previous slot gives something equal to |aItem|.
  //
  //
  // @param aItem  The item to search for.
  // @param aComp  The Comparator used.
  // @return        The index of greatest element <= to |aItem|
  // @precondition The array is sorted
  template <class Item, class Comparator>
  [[nodiscard]] index_type IndexOfFirstElementGt(
      const Item& aItem, const Comparator& aComp) const {
    using mozilla::BinarySearchIf;
    ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);

    size_t index;
    BinarySearchIf(
        Elements(), 0, Length(),
        [&](const value_type& aElement) {
          return comp.Compare(aElement, aItem) <= 0 ? 1 : -1;
        },
        &index);
    return index;
  }

  // A variation on the IndexOfFirstElementGt method defined above.
  template <class Item>
  [[nodiscard]] index_type IndexOfFirstElementGt(const Item& aItem) const {
    return IndexOfFirstElementGt(aItem,
                                 nsDefaultComparator<value_type, Item>());
  }

 private:
  template <typename ActualAlloc, class Item, class Comparator>
  value_type* InsertElementSortedInternal(Item&& aItem,
                                          const Comparator& aComp) {
    index_type index = IndexOfFirstElementGt<Item, Comparator>(aItem, aComp);
    return InsertElementAtInternal<ActualAlloc>(index,
                                                std::forward<Item>(aItem));
  }

  // Inserts |aItem| at such an index to guarantee that if the array
  // was previously sorted, it will remain sorted after this
  // insertion.
 public:
  template <class Item, class Comparator>
  [[nodiscard]] value_type* InsertElementSorted(Item&& aItem,
                                                const Comparator& aComp,
                                                const mozilla::fallible_t&) {
    return InsertElementSortedInternal<FallibleAlloc>(std::forward<Item>(aItem),
                                                      aComp);
  }

  // A variation on the InsertElementSorted method defined above.
 public:
  template <class Item>
  [[nodiscard]] value_type* InsertElementSorted(Item&& aItem,
                                                const mozilla::fallible_t&) {
    return InsertElementSortedInternal<FallibleAlloc>(
        std::forward<Item>(aItem), nsDefaultComparator<value_type, Item>{});
  }

 private:
  template <typename ActualAlloc, class Item>
  value_type* AppendElementsInternal(const Item* aArray, size_type aArrayLen);

  // This method appends elements to the end of this array.
  // @param aArray    The elements to append to this array.
  // @param aArrayLen The number of elements to append to this array.
  // @return          A pointer to the new elements in the array, or null if
  //                  the operation failed due to insufficient memory.
 public:
  template <class Item>
  [[nodiscard]] value_type* AppendElements(const Item* aArray,
                                           size_type aArrayLen,
                                           const mozilla::fallible_t&) {
    return AppendElementsInternal<FallibleAlloc>(aArray, aArrayLen);
  }

  template <class Item>
  [[nodiscard]] value_type* AppendElements(mozilla::Span<Item> aSpan,
                                           const mozilla::fallible_t&) {
    return AppendElementsInternal<FallibleAlloc>(aSpan.Elements(),
                                                 aSpan.Length());
  }

  // A variation on the AppendElements method defined above.
  template <class Item, class Allocator>
  [[nodiscard]] value_type* AppendElements(
      const nsTArray_Impl<Item, Allocator>& aArray,
      const mozilla::fallible_t&) {
    return AppendElementsInternal<FallibleAlloc>(aArray.Elements(),
                                                 aArray.Length());
  }

 private:
  template <typename ActualAlloc, class Item, class Allocator>
  value_type* AppendElementsInternal(nsTArray_Impl<Item, Allocator>&& aArray);

  // Move all elements from another array to the end of this array.
  // @return A pointer to the newly appended elements, or null on OOM.
 public:
  template <class Item, class Allocator>
  [[nodiscard]] value_type* AppendElements(
      nsTArray_Impl<Item, Allocator>&& aArray, const mozilla::fallible_t&) {
    return AppendElementsInternal<FallibleAlloc>(std::move(aArray));
  }

  // Append a new element, constructed in place from the provided arguments.
 protected:
  template <typename ActualAlloc, class... Args>
  value_type* EmplaceBackInternal(Args&&... aItem);

 public:
  template <class... Args>
  [[nodiscard]] value_type* EmplaceBack(const mozilla::fallible_t&,
                                        Args&&... aArgs) {
    return EmplaceBackInternal<FallibleAlloc, Args...>(
        std::forward<Args>(aArgs)...);
  }

 private:
  template <typename ActualAlloc, class Item>
  value_type* AppendElementInternal(Item&& aItem);

  // Append a new element, move constructing if possible.
 public:
  template <class Item>
  [[nodiscard]] value_type* AppendElement(Item&& aItem,
                                          const mozilla::fallible_t&) {
    return AppendElementInternal<FallibleAlloc>(std::forward<Item>(aItem));
  }

 private:
  template <typename ActualAlloc>
  value_type* AppendElementsInternal(size_type aCount) {
    if (!ActualAlloc::Successful(this->template ExtendCapacity<ActualAlloc>(
            Length(), aCount, sizeof(value_type)))) {
      return nullptr;
    }
    value_type* elems = Elements() + Length();
    size_type i;
    for (i = 0; i < aCount; ++i) {
      elem_traits::Construct(elems + i);
    }
    this->IncrementLength(aCount);
    return elems;
  }

  // Append new elements without copy-constructing. This is useful to avoid
  // temporaries.
  // @return A pointer to the newly appended elements, or null on OOM.
 public:
  [[nodiscard]] value_type* AppendElements(size_type aCount,
                                           const mozilla::fallible_t&) {
    return AppendElementsInternal<FallibleAlloc>(aCount);
  }

 private:
  // Append a new element without copy-constructing. This is useful to avoid
  // temporaries.
  // @return A pointer to the newly appended element, or null on OOM.
 public:
  [[nodiscard]] value_type* AppendElement(const mozilla::fallible_t&) {
    return AppendElements(1, mozilla::fallible);
  }

  // This method removes a single element from this array, like
  // std::vector::erase.
  // @param pos to the element to remove
  const_iterator RemoveElementAt(const_iterator pos) {
    MOZ_ASSERT(pos.GetArray() == this);

    RemoveElementAt(pos.GetIndex());
    return pos;
  }

  // This method removes a range of elements from this array, like
  // std::vector::erase.
  // @param first iterator to the first of elements to remove
  // @param last iterator to the last of elements to remove
  const_iterator RemoveElementsRange(const_iterator first,
                                     const_iterator last) {
    MOZ_ASSERT(first.GetArray() == this);
    MOZ_ASSERT(last.GetArray() == this);
    MOZ_ASSERT(last.GetIndex() >= first.GetIndex());

    RemoveElementsAt(first.GetIndex(), last.GetIndex() - first.GetIndex());
    return first;
  }

  // This method removes a range of elements from this array.
  // @param aStart The starting index of the elements to remove.
  // @param aCount The number of elements to remove.
  void RemoveElementsAt(index_type aStart, size_type aCount);

 private:
  // Remove a range of elements from this array, but do not check that
  // the range is in bounds.
  // @param aStart The starting index of the elements to remove.
  // @param aCount The number of elements to remove.
  void RemoveElementsAtUnsafe(index_type aStart, size_type aCount);

 public:
  // Similar to the above, but it removes just one element. This does bounds
  // checking only in debug builds.
  void RemoveElementAtUnsafe(index_type aIndex) {
    MOZ_ASSERT(aIndex < Length(), "Trying to remove an invalid element");
    RemoveElementsAtUnsafe(aIndex, 1);
  }

  // A variation on the RemoveElementsAt method defined above.
  void RemoveElementAt(index_type aIndex) { RemoveElementsAt(aIndex, 1); }

  // A variation on RemoveElementAt that removes the last element.
  void RemoveLastElement() { RemoveLastElements(1); }

  // A variation on RemoveElementsAt that removes the last 'aCount' elements.
  void RemoveLastElements(const size_type aCount) {
    // This assertion is redundant, but produces a better error message than the
    // release assertion within TruncateLength.
    MOZ_ASSERT(aCount <= Length());
    TruncateLength(Length() - aCount);
  }

  // Removes the last element of the array and returns a copy of it.
  [[nodiscard]] value_type PopLastElement() {
    // This function intentionally does not call ElementsAt and calls
    // TruncateLengthUnsafe directly to avoid multiple release checks for
    // non-emptiness.
    // This debug assertion is redundant, but produces a better error message
    // than the release assertion below.
    MOZ_ASSERT(!base_type::IsEmpty());
    const size_type oldLen = Length();
    if (MOZ_UNLIKELY(0 == oldLen)) {
      mozilla::detail::InvalidArrayIndex_CRASH(1, 0);
    }
    value_type elem = std::move(Elements()[oldLen - 1]);
    TruncateLengthUnsafe(oldLen - 1);
    return elem;
  }

  // This method performs index-based removals from an array without preserving
  // the order of the array. This is useful if you are using the array as a
  // set-like data structure.
  //
  // These removals are efficient, as they move as few elements as possible. At
  // most N elements, where N is the number of removed elements, will have to
  // be relocated.
  //
  // ## Examples
  //
  // When removing an element from the end of the array, it can be removed in
  // place, by destroying it and decrementing the length.
  //
  // [ 1, 2, 3 ] => [ 1, 2 ]
  //         ^
  //
  // When removing any other single element, it is removed by swapping it with
  // the last element, and then decrementing the length as before.
  //
  // [ 1, 2, 3, 4, 5, 6 ]  => [ 1, 6, 3, 4, 5 ]
  //      ^
  //
  // This method also supports efficiently removing a range of elements. If they
  // are at the end, then they can all be removed like in the one element case.
  //
  // [ 1, 2, 3, 4, 5, 6 ] => [ 1, 2 ]
  //         ^--------^
  //
  // If more elements are removed than exist after the removed section, the
  // remaining elements will be shifted down like in a normal removal.
  //
  // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 2, 7, 8 ]
  //         ^--------^
  //
  // And if fewer elements are removed than exist after the removed section,
  // elements will be moved from the end of the array to fill the vacated space.
  //
  // [ 1, 2, 3, 4, 5, 6, 7, 8 ] => [ 1, 7, 8, 4, 5, 6 ]
  //      ^--^
  //
  // @param aStart The starting index of the elements to remove. @param aCount
  // The number of elements to remove.
  void UnorderedRemoveElementsAt(index_type aStart, size_type aCount);

  // A variation on the UnorderedRemoveElementsAt method defined above to remove
  // a single element. This operation is sometimes called `SwapRemove`.
  //
  // This method is O(1), but does not preserve the order of the elements.
  void UnorderedRemoveElementAt(index_type aIndex) {
    UnorderedRemoveElementsAt(aIndex, 1);
  }

  void Clear() {
    ClearAndRetainStorage();
    base_type::ShrinkCapacityToZero();
  }

  // This method removes elements based on the return value of the
  // callback function aPredicate. If the function returns true for
  // an element, the element is removed. aPredicate will be called
  // for each element in order. It is not safe to access the array
  // inside aPredicate.
  //
  // Returns the number of elements removed.
  template <typename Predicate>
  size_type RemoveElementsBy(Predicate aPredicate);

  // This helper function combines IndexOf with RemoveElementAt to "search
  // and destroy" the first element that is equal to the given element.
  // @param aItem The item to search for.
  // @param aComp The Comparator used to determine element equality.
  // @return true if the element was found
  template <class Item, class Comparator>
  bool RemoveElement(const Item& aItem, const Comparator& aComp) {
    index_type i = IndexOf(aItem, 0, aComp);
    if (i == NoIndex) {
      return false;
    }
    RemoveElementsAtUnsafe(i, 1);
    return true;
  }

  // A variation on the RemoveElement method defined above that assumes
  // that 'operator==' is defined for value_type.
  template <class Item>
  bool RemoveElement(const Item& aItem) {
    return RemoveElement(aItem, nsDefaultComparator<value_type, Item>());
  }

  // Variations for RemoveElement that uses unordered removal.
  template <class Item, class Comparator>
  bool UnorderedRemoveElement(const Item& aItem, const Comparator& aComp) {
    index_type i = IndexOf(aItem, 0, aComp);
    if (i == NoIndex) {
      return false;
    }
    UnorderedRemoveElementAt(i);
    return true;
  }

  template <class Item>
  bool UnorderedRemoveElement(const Item& aItem) {
    return UnorderedRemoveElement(aItem,
                                  nsDefaultComparator<value_type, Item>());
  }

  // This helper function combines IndexOfFirstElementGt with
  // RemoveElementAt to "search and destroy" the last element that
  // is equal to the given element.
  // @param aItem The item to search for.
  // @param aComp The Comparator used to determine element equality.
  // @return true if the element was found
  template <class Item, class Comparator>
  bool RemoveElementSorted(const Item& aItem, const Comparator& aComp) {
    index_type index = IndexOfFirstElementGt(aItem, aComp);
    if (index > 0 && aComp.Equals(ElementAt(index - 1), aItem)) {
      RemoveElementsAtUnsafe(index - 1, 1);
      return true;
    }
    return false;
  }

  // A variation on the RemoveElementSorted method defined above.
  template <class Item>
  bool RemoveElementSorted(const Item& aItem) {
    return RemoveElementSorted(aItem, nsDefaultComparator<value_type, Item>());
  }

  // This method causes the elements contained in this array and the given
  // array to be swapped.
  template <class Allocator>
  void SwapElements(nsTArray_Impl<E, Allocator>& aOther) {
    // The only case this might fail were if someone called this with a
    // AutoTArray upcast to nsTArray_Impl, under the conditions mentioned in the
    // overload for AutoTArray below.
    this->template SwapArrayElements<InfallibleAlloc>(aOther,
                                                      sizeof(value_type));
  }

  template <size_t N>
  void SwapElements(AutoTArray<E, N>& aOther) {
    // Allocation might fail if Alloc==FallibleAlloc and
    // Allocator==InfallibleAlloc and aOther uses auto storage. Allow this for
    // small inline sizes, and crash in the rare case of a small OOM error.
    static_assert(!std::is_same_v<Alloc, FallibleAlloc> ||
                  sizeof(E) * N <= 1024);
    this->template SwapArrayElements<InfallibleAlloc>(aOther,
                                                      sizeof(value_type));
  }

  template <class Allocator>
  [[nodiscard]] auto SwapElements(nsTArray_Impl<E, Allocator>& aOther,
                                  const mozilla::fallible_t&) {
    // Allocation might fail if Alloc==FallibleAlloc and
    // Allocator==InfallibleAlloc and aOther uses auto storage.
    return FallibleAlloc::Result(
        this->template SwapArrayElements<FallibleAlloc>(aOther,
                                                        sizeof(value_type)));
  }

 private:
  // Used by ApplyIf functions to invoke a callable that takes either:
  // - Nothing: F(void)
  // - Index only: F(size_t)
  // - Reference to element only: F(maybe-const value_type&)
  // - Both index and reference: F(size_t, maybe-const value_type&)
  // `value_type` must be const when called from const method.
  template <typename T, typename Param0, typename Param1>
  struct InvokeWithIndexAndOrReferenceHelper {
    static constexpr bool valid = false;
  };
  template <typename T>
  struct InvokeWithIndexAndOrReferenceHelper<T, void, void> {
    static constexpr bool valid = true;
    template <typename F>
    static auto Invoke(F&& f, size_t, T&) {
      return f();
    }
  };
  template <typename T>
  struct InvokeWithIndexAndOrReferenceHelper<T, size_t, void> {
    static constexpr bool valid = true;
    template <typename F>
    static auto Invoke(F&& f, size_t i, T&) {
      return f(i);
    }
  };
  template <typename T>
  struct InvokeWithIndexAndOrReferenceHelper<T, T&, void> {
    static constexpr bool valid = true;
    template <typename F>
    static auto Invoke(F&& f, size_t, T& e) {
      return f(e);
    }
  };
  template <typename T>
  struct InvokeWithIndexAndOrReferenceHelper<T, const T&, void> {
    static constexpr bool valid = true;
    template <typename F>
    static auto Invoke(F&& f, size_t, T& e) {
      return f(e);
    }
  };
  template <typename T>
  struct InvokeWithIndexAndOrReferenceHelper<T, size_t, T&> {
    static constexpr bool valid = true;
    template <typename F>
    static auto Invoke(F&& f, size_t i, T& e) {
      return f(i, e);
    }
  };
  template <typename T>
  struct InvokeWithIndexAndOrReferenceHelper<T, size_t, const T&> {
    static constexpr bool valid = true;
    template <typename F>
    static auto Invoke(F&& f, size_t i, T& e) {
      return f(i, e);
    }
  };
  template <typename T, typename F>
  static auto InvokeWithIndexAndOrReference(F&& f, size_t i, T& e) {
    using Invoker = InvokeWithIndexAndOrReferenceHelper<
        T, typename mozilla::FunctionTypeTraits<F>::template ParameterType<0>,
        typename mozilla::FunctionTypeTraits<F>::template ParameterType<1>>;
    static_assert(Invoker::valid,
                  "ApplyIf's Function parameters must match either: (void), "
                  "(size_t), (maybe-const value_type&), or "
                  "(size_t, maybe-const value_type&)");
    return Invoker::Invoke(std::forward<F>(f), i, e);
  }

 public:
  // 'Apply' family of methods.
  //
  // The advantages of using Apply methods with lambdas include:
  // - Safety of accessing elements from within the call, when the array cannot
  //   have been modified between the iteration and the subsequent access.
  // - Avoiding moot conversions: pointer->index during a search, followed by
  //   index->pointer after the search when accessing the element.
  // - Embedding your code into the algorithm, giving the compiler more chances
  //   to optimize.

  // Search for the first element comparing equal to aItem with the given
  // comparator (`==` by default).
  // If such an element exists, return the result of evaluating either:
  // - `aFunction()`
  // - `aFunction(index_type)`
  // - `aFunction(maybe-const? value_type&)`
  // - `aFunction(index_type, maybe-const? value_type&)`
  // (`aFunction` must have one of the above signatures with these exact types,
  //  including references; implicit conversions or generic types not allowed.
  //  If `this` array is const, the referenced `value_type` must be const too;
  //  otherwise it may be either const or non-const.)
  // But if the element is not found, return the result of evaluating
  // `aFunctionElse()`.
  template <class Item, class Comparator, class Function, class FunctionElse>
  auto ApplyIf(const Item& aItem, index_type aStart, const Comparator& aComp,
               Function&& aFunction, FunctionElse&& aFunctionElse) const {
    static_assert(
        std::is_same_v<
            typename mozilla::FunctionTypeTraits<Function>::ReturnType,
            typename mozilla::FunctionTypeTraits<FunctionElse>::ReturnType>,
        "ApplyIf's `Function` and `FunctionElse` must return the same type.");

    ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);

    const value_type* const elements = Elements();
    const value_type* const iend = elements + Length();
    for (const value_type* iter = elements + aStart; iter != iend; ++iter) {
      if (comp.Equals(*iter, aItem)) {
        return InvokeWithIndexAndOrReference<const value_type>(
            std::forward<Function>(aFunction), iter - elements, *iter);
      }
    }
    return aFunctionElse();
  }
  template <class Item, class Comparator, class Function, class FunctionElse>
  auto ApplyIf(const Item& aItem, index_type aStart, const Comparator& aComp,
               Function&& aFunction, FunctionElse&& aFunctionElse) {
    static_assert(
        std::is_same_v<
            typename mozilla::FunctionTypeTraits<Function>::ReturnType,
            typename mozilla::FunctionTypeTraits<FunctionElse>::ReturnType>,
        "ApplyIf's `Function` and `FunctionElse` must return the same type.");

    ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);

    value_type* const elements = Elements();
    value_type* const iend = elements + Length();
    for (value_type* iter = elements + aStart; iter != iend; ++iter) {
      if (comp.Equals(*iter, aItem)) {
        return InvokeWithIndexAndOrReference<value_type>(
            std::forward<Function>(aFunction), iter - elements, *iter);
      }
    }
    return aFunctionElse();
  }
  template <class Item, class Function, class FunctionElse>
  auto ApplyIf(const Item& aItem, index_type aStart, Function&& aFunction,
               FunctionElse&& aFunctionElse) const {
    return ApplyIf(aItem, aStart, nsDefaultComparator<value_type, Item>(),
                   std::forward<Function>(aFunction),
                   std::forward<FunctionElse>(aFunctionElse));
  }
  template <class Item, class Function, class FunctionElse>
  auto ApplyIf(const Item& aItem, index_type aStart, Function&& aFunction,
               FunctionElse&& aFunctionElse) {
    return ApplyIf(aItem, aStart, nsDefaultComparator<value_type, Item>(),
                   std::forward<Function>(aFunction),
                   std::forward<FunctionElse>(aFunctionElse));
  }
  template <class Item, class Function, class FunctionElse>
  auto ApplyIf(const Item& aItem, Function&& aFunction,
               FunctionElse&& aFunctionElse) const {
    return ApplyIf(aItem, 0, std::forward<Function>(aFunction),
                   std::forward<FunctionElse>(aFunctionElse));
  }
  template <class Item, class Function, class FunctionElse>
  auto ApplyIf(const Item& aItem, Function&& aFunction,
               FunctionElse&& aFunctionElse) {
    return ApplyIf(aItem, 0, std::forward<Function>(aFunction),
                   std::forward<FunctionElse>(aFunctionElse));
  }

  //
  // Allocation
  //

  // This method may increase the capacity of this array object to the
  // specified amount.  This method may be called in advance of several
  // AppendElement operations to minimize heap re-allocations.  This method
  // will not reduce the number of elements in this array.
  // @param aCapacity The desired capacity of this array.
  // @return True if the operation succeeded; false if we ran out of memory
 protected:
  template <typename ActualAlloc = Alloc>
  MOZ_REINITIALIZES typename ActualAlloc::ResultType SetCapacity(
      size_type aCapacity) {
    return ActualAlloc::Result(this->template EnsureCapacity<ActualAlloc>(
        aCapacity, sizeof(value_type)));
  }

 public:
  [[nodiscard]] bool SetCapacity(size_type aCapacity,
                                 const mozilla::fallible_t&) {
    return SetCapacity<FallibleAlloc>(aCapacity);
  }

  // This method modifies the length of the array.  If the new length is
  // larger than the existing length of the array, then new elements will be
  // constructed using value_type's default constructor.  Otherwise, this call
  // removes elements from the array (see also RemoveElementsAt).
  // @param aNewLen The desired length of this array.
  // @return True if the operation succeeded; false otherwise.
  // See also TruncateLength for a more efficient variant if the new length is
  // guaranteed to be smaller than the old.
 protected:
  template <typename ActualAlloc = Alloc>
  typename ActualAlloc::ResultType SetLength(size_type aNewLen) {
    const size_type oldLen = Length();
    if (aNewLen > oldLen) {
      return ActualAlloc::ConvertBoolToResultType(
          InsertElementsAtInternal<ActualAlloc>(oldLen, aNewLen - oldLen) !=
          nullptr);
    }

    TruncateLengthUnsafe(aNewLen);
    return ActualAlloc::ConvertBoolToResultType(true);
  }

 public:
  [[nodiscard]] bool SetLength(size_type aNewLen, const mozilla::fallible_t&) {
    return SetLength<FallibleAlloc>(aNewLen);
  }

  // This method modifies the length of the array, but may only be
  // called when the new length is shorter than the old.  It can
  // therefore be called when value_type has no default constructor,
  // unlike SetLength.  It removes elements from the array (see also
  // RemoveElementsAt).
  // @param aNewLen The desired length of this array.
  void TruncateLength(size_type aNewLen) {
    // This assertion is redundant, but produces a better error message than the
    // release assertion below.
    MOZ_ASSERT(aNewLen <= Length(), "caller should use SetLength instead");

    if (MOZ_UNLIKELY(aNewLen > Length())) {
      mozilla::detail::InvalidArrayIndex_CRASH(aNewLen, Length());
    }

    TruncateLengthUnsafe(aNewLen);
  }

 private:
  void TruncateLengthUnsafe(size_type aNewLen) {
    const size_type oldLen = Length();
    if (oldLen) {
      DestructRange(aNewLen, oldLen - aNewLen);
      base_type::mHdr->mLength = aNewLen;
    }
  }

  // This method ensures that the array has length at least the given
  // length.  If the current length is shorter than the given length,
  // then new elements will be constructed using value_type's default
  // constructor.
  // @param aMinLen The desired minimum length of this array.
  // @return True if the operation succeeded; false otherwise.
 protected:
  template <typename ActualAlloc = Alloc>
  typename ActualAlloc::ResultType EnsureLengthAtLeast(size_type aMinLen) {
    size_type oldLen = Length();
    if (aMinLen > oldLen) {
      return ActualAlloc::ConvertBoolToResultType(
          !!InsertElementsAtInternal<ActualAlloc>(oldLen, aMinLen - oldLen));
    }
    return ActualAlloc::ConvertBoolToResultType(true);
  }

 public:
  [[nodiscard]] bool EnsureLengthAtLeast(size_type aMinLen,
                                         const mozilla::fallible_t&) {
    return EnsureLengthAtLeast<FallibleAlloc>(aMinLen);
  }

  // This method inserts elements into the array, constructing
  // them using value_type's default constructor.
  // @param aIndex the place to insert the new elements. This must be no
  //               greater than the current length of the array.
  // @param aCount the number of elements to insert
 private:
  template <typename ActualAlloc>
  value_type* InsertElementsAtInternal(index_type aIndex, size_type aCount) {
    if (!ActualAlloc::Successful(this->template InsertSlotsAt<ActualAlloc>(
            aIndex, aCount, sizeof(value_type)))) {
      return nullptr;
    }

    // Initialize the extra array elements
    value_type* iter = Elements() + aIndex;
    value_type* iend = iter + aCount;
    for (; iter != iend; ++iter) {
      elem_traits::Construct(iter);
    }

    return Elements() + aIndex;
  }

 public:
  [[nodiscard]] value_type* InsertElementsAt(index_type aIndex,
                                             size_type aCount,
                                             const mozilla::fallible_t&) {
    return InsertElementsAtInternal<FallibleAlloc>(aIndex, aCount);
  }

  // This method inserts elements into the array, constructing them
  // value_type's copy constructor (or whatever one-arg constructor
  // happens to match the Item type).
  // @param aIndex the place to insert the new elements. This must be no
  //               greater than the current length of the array.
  // @param aCount the number of elements to insert.
  // @param aItem the value to use when constructing the new elements.
 private:
  template <typename ActualAlloc, class Item>
  value_type* InsertElementsAtInternal(index_type aIndex, size_type aCount,
                                       const Item& aItem);

 public:
  template <class Item>
  [[nodiscard]] value_type* InsertElementsAt(index_type aIndex,
                                             size_type aCount,
                                             const Item& aItem,
                                             const mozilla::fallible_t&) {
    return InsertElementsAt<Item, FallibleAlloc>(aIndex, aCount, aItem);
  }

  // This method may be called to minimize the memory used by this array.
  void Compact() { ShrinkCapacity(sizeof(value_type)); }

  //
  // Sorting
  //

  // This method sorts the elements of the array.  It uses the LessThan
  // method defined on the given Comparator object to collate elements or
  // it wraps a tri-state comparison lambda into such a comparator.
  // It uses std::sort. It expects value_type to be move assignable and
  // constructible and uses those always, regardless of the chosen
  // nsTArray_RelocationStrategy.
  //
  // @param aComp The Comparator used to collate elements.
  template <SortBoundsCheck Check = SortBoundsCheck::Enable, class Comparator>
  void Sort(const Comparator& aComp) {
    static_assert(std::is_move_assignable_v<value_type>);
    static_assert(std::is_move_constructible_v<value_type>);

    ::detail::CompareWrapper<Comparator, value_type, value_type> comp(aComp);
    auto compFn = [&comp](const auto& left, const auto& right) {
      return comp.LessThan(left, right);
    };
    if constexpr (Check == SortBoundsCheck::Enable) {
      std::sort(begin(), end(), compFn);
    } else {
      std::sort(Elements(), Elements() + Length(), compFn);
    }
    ::detail::AssertStrictWeakOrder(Elements(), Elements() + Length(), compFn);
  }

  // A variation on the Sort method defined above that assumes that
  // 'operator<' is defined for 'value_type'.
  template <SortBoundsCheck Check = SortBoundsCheck::Enable>
  void Sort() {
    Sort(nsDefaultComparator<value_type, value_type>());
  }

  // This method sorts the elements of the array in a stable way (i.e. not
  // changing the relative order of elements considered equal by the
  // Comparator).  It uses the LessThan method defined on the given Comparator
  // object to collate elements.
  // It uses std::stable_sort. It expects value_type to be move assignable and
  // constructible and uses those always, regardless of the chosen
  // nsTArray_RelocationStrategy.
  //
  // @param aComp The Comparator used to collate elements.
  template <SortBoundsCheck Check = SortBoundsCheck::Enable, class Comparator>
  void StableSort(const Comparator& aComp) {
    static_assert(std::is_move_assignable_v<value_type>);
    static_assert(std::is_move_constructible_v<value_type>);

    const ::detail::CompareWrapper<Comparator, value_type, value_type> comp(
        aComp);
    auto compFn = [&comp](const auto& lhs, const auto& rhs) {
      return comp.LessThan(lhs, rhs);
    };
    if constexpr (Check == SortBoundsCheck::Enable) {
      std::stable_sort(begin(), end(), compFn);
    } else {
      std::stable_sort(Elements(), Elements() + Length(), compFn);
    }
    ::detail::AssertStrictWeakOrder(Elements(), Elements() + Length(), compFn);
  }

  // A variation on the StableSort method defined above that assumes that
  // 'operator<' is defined for 'value_type'.
  template <SortBoundsCheck Check = SortBoundsCheck::Enable>
  void StableSort() {
    StableSort(nsDefaultComparator<value_type, value_type>());
  }

  // This method reverses the array in place.
  void Reverse() {
    value_type* elements = Elements();
    const size_type len = Length();
    for (index_type i = 0, iend = len / 2; i < iend; ++i) {
      std::swap(elements[i], elements[len - i - 1]);
    }
  }

 protected:
  using base_type::Hdr;
  using base_type::ShrinkCapacity;

  // This method invokes value_type's destructor on a range of elements.
  // @param aStart The index of the first element to destroy.
  // @param aCount The number of elements to destroy.
  void DestructRange(index_type aStart, size_type aCount) {
    value_type* iter = Elements() + aStart;
    value_type* iend = iter + aCount;
    for (; iter != iend; ++iter) {
      elem_traits::Destruct(iter);
    }
  }

  // This method invokes value_type's copy-constructor on a range of elements.
  // @param aStart  The index of the first element to construct.
  // @param aCount  The number of elements to construct.
  // @param aValues The array of elements to copy.
  template <class Item>
  void AssignRange(index_type aStart, size_type aCount, const Item* aValues) {
    std::uninitialized_copy(aValues, aValues + aCount, Elements() + aStart);
  }
};

template <typename E, class Alloc>
template <typename ActualAlloc, class Item>
auto nsTArray_Impl<E, Alloc>::AssignInternal(const Item* aArray,
                                             size_type aArrayLen) ->
    typename ActualAlloc::ResultType {
  static_assert(std::is_same_v<ActualAlloc, InfallibleAlloc> ||
                std::is_same_v<ActualAlloc, FallibleAlloc>);

  if constexpr (std::is_same_v<ActualAlloc, InfallibleAlloc>) {
    ClearAndRetainStorage();
  }
  // Adjust memory allocation up-front to catch errors in the fallible case.
  // We might relocate the elements to be destroyed unnecessarily. This could be
  // optimized, but would make things more complicated.
  if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
          aArrayLen, sizeof(value_type)))) {
    return ActualAlloc::ConvertBoolToResultType(false);
  }

  MOZ_ASSERT_IF(this->HasEmptyHeader(), aArrayLen == 0);
  if (!this->HasEmptyHeader()) {
    if constexpr (std::is_same_v<ActualAlloc, FallibleAlloc>) {
      ClearAndRetainStorage();
    }
    AssignRange(0, aArrayLen, aArray);
    base_type::mHdr->mLength = aArrayLen;
  }

  return ActualAlloc::ConvertBoolToResultType(true);
}

template <typename E, class Alloc>
template <typename ActualAlloc, class Item>
auto nsTArray_Impl<E, Alloc>::ReplaceElementsAtInternal(index_type aStart,
                                                        size_type aCount,
                                                        const Item* aArray,
                                                        size_type aArrayLen)
    -> value_type* {
  if (MOZ_UNLIKELY(aStart > Length())) {
    mozilla::detail::InvalidArrayIndex_CRASH(aStart, Length());
  }
  if (MOZ_UNLIKELY(aCount > Length() - aStart)) {
    mozilla::detail::InvalidArrayIndex_CRASH(aStart + aCount, Length());
  }

  // Adjust memory allocation up-front to catch errors.
  if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
          Length() + aArrayLen - aCount, sizeof(value_type)))) {
    return nullptr;
  }
  DestructRange(aStart, aCount);
  this->template ShiftData<ActualAlloc>(aStart, aCount, aArrayLen,
                                        sizeof(value_type));
  AssignRange(aStart, aArrayLen, aArray);
  return Elements() + aStart;
}

template <typename E, class Alloc>
void nsTArray_Impl<E, Alloc>::RemoveElementsAt(index_type aStart,
                                               size_type aCount) {
  MOZ_ASSERT(aCount == 0 || aStart < Length(), "Invalid aStart index");

  mozilla::CheckedInt<index_type> rangeEnd = aStart;
  rangeEnd += aCount;

  if (MOZ_UNLIKELY(!rangeEnd.isValid() || rangeEnd.value() > Length())) {
    mozilla::detail::InvalidArrayIndex_CRASH(aStart, Length());
  }

  RemoveElementsAtUnsafe(aStart, aCount);
}

template <typename E, class Alloc>
void nsTArray_Impl<E, Alloc>::RemoveElementsAtUnsafe(index_type aStart,
                                                     size_type aCount) {
  DestructRange(aStart, aCount);
  this->template ShiftData<InfallibleAlloc>(aStart, aCount, 0,
                                            sizeof(value_type));
}

template <typename E, class Alloc>
void nsTArray_Impl<E, Alloc>::UnorderedRemoveElementsAt(index_type aStart,
                                                        size_type aCount) {
  MOZ_ASSERT(aCount == 0 || aStart < Length(), "Invalid aStart index");

  mozilla::CheckedInt<index_type> rangeEnd = aStart;
  rangeEnd += aCount;

  if (MOZ_UNLIKELY(!rangeEnd.isValid() || rangeEnd.value() > Length())) {
    mozilla::detail::InvalidArrayIndex_CRASH(aStart, Length());
  }

  // Destroy the elements which are being removed, and then swap elements in to
  // replace them from the end. See the docs on the declaration of this
  // function.
  DestructRange(aStart, aCount);
  this->template SwapFromEnd<InfallibleAlloc>(aStart, aCount,
                                              sizeof(value_type));
}

template <typename E, class Alloc>
template <typename Predicate>
auto nsTArray_Impl<E, Alloc>::RemoveElementsBy(Predicate aPredicate)
    -> size_type {
  if (this->HasEmptyHeader()) {
    return 0;
  }

  index_type j = 0;
  const index_type len = Length();
  value_type* const elements = Elements();
  for (index_type i = 0; i < len; ++i) {
    const bool result = aPredicate(elements[i]);

    // Check that the array has not been modified by the predicate.
    MOZ_DIAGNOSTIC_ASSERT(len == base_type::mHdr->mLength &&
                          elements == Elements());

    if (result) {
      elem_traits::Destruct(elements + i);
    } else {
      if (j < i) {
        relocation_type::RelocateNonOverlappingRegion(
            elements + j, elements + i, 1, sizeof(value_type));
      }
      ++j;
    }
  }

  base_type::mHdr->mLength = j;
  return len - j;
}

template <typename E, class Alloc>
template <typename ActualAlloc, class Item>
auto nsTArray_Impl<E, Alloc>::InsertElementsAtInternal(index_type aIndex,
                                                       size_type aCount,
                                                       const Item& aItem)
    -> value_type* {
  if (!ActualAlloc::Successful(this->template InsertSlotsAt<ActualAlloc>(
          aIndex, aCount, sizeof(value_type)))) {
    return nullptr;
  }

  // Initialize the extra array elements
  value_type* iter = Elements() + aIndex;
  value_type* iend = iter + aCount;
  for (; iter != iend; ++iter) {
    elem_traits::Construct(iter, aItem);
  }

  return Elements() + aIndex;
}

template <typename E, class Alloc>
template <typename ActualAlloc>
auto nsTArray_Impl<E, Alloc>::InsertElementAtInternal(index_type aIndex)
    -> value_type* {
  if (MOZ_UNLIKELY(aIndex > Length())) {
    mozilla::detail::InvalidArrayIndex_CRASH(aIndex, Length());
  }

  // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
  if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
          Length() + 1, sizeof(value_type)))) {
    return nullptr;
  }
  this->template ShiftData<ActualAlloc>(aIndex, 0, 1, sizeof(value_type));
  value_type* elem = Elements() + aIndex;
  elem_traits::Construct(elem);
  return elem;
}

template <typename E, class Alloc>
template <typename ActualAlloc, class Item>
auto nsTArray_Impl<E, Alloc>::InsertElementAtInternal(index_type aIndex,
                                                      Item&& aItem)
    -> value_type* {
  if (MOZ_UNLIKELY(aIndex > Length())) {
    mozilla::detail::InvalidArrayIndex_CRASH(aIndex, Length());
  }

  // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
  if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
          Length() + 1, sizeof(value_type)))) {
    return nullptr;
  }
  this->template ShiftData<ActualAlloc>(aIndex, 0, 1, sizeof(value_type));
  value_type* elem = Elements() + aIndex;
  elem_traits::Construct(elem, std::forward<Item>(aItem));
  return elem;
}

template <typename E, class Alloc>
template <typename ActualAlloc, class Item>
auto nsTArray_Impl<E, Alloc>::AppendElementsInternal(const Item* aArray,
                                                     size_type aArrayLen)
    -> value_type* {
  if (!ActualAlloc::Successful(this->template ExtendCapacity<ActualAlloc>(
          Length(), aArrayLen, sizeof(value_type)))) {
    return nullptr;
  }
  index_type len = Length();
  AssignRange(len, aArrayLen, aArray);
  this->IncrementLength(aArrayLen);
  return Elements() + len;
}

template <typename E, class Alloc>
template <typename ActualAlloc, class Item, class Allocator>
auto nsTArray_Impl<E, Alloc>::AppendElementsInternal(
    nsTArray_Impl<Item, Allocator>&& aArray) -> value_type* {
  if constexpr (std::is_same_v<Alloc, Allocator>) {
    MOZ_ASSERT(&aArray != this, "argument must be different aArray");
  }
  index_type len = Length();
  if (len == 0) {
    // XXX This might still be optimized. If aArray uses auto-storage but we
    // won't, we might better retain our storage if it's sufficiently large.
    this->ShrinkCapacityToZero();
    this->MoveInit(aArray, sizeof(value_type));
    return Elements();
  }

  index_type otherLen = aArray.Length();
  if (!ActualAlloc::Successful(this->template ExtendCapacity<ActualAlloc>(
          len, otherLen, sizeof(value_type)))) {
    return nullptr;
  }
  relocation_type::RelocateNonOverlappingRegion(
      Elements() + len, aArray.Elements(), otherLen, sizeof(value_type));
  this->IncrementLength(otherLen);
  aArray.template ShiftData<ActualAlloc>(0, otherLen, 0, sizeof(value_type));
  return Elements() + len;
}

template <typename E, class Alloc>
template <typename ActualAlloc, class Item>
auto nsTArray_Impl<E, Alloc>::AppendElementInternal(Item&& aItem)
    -> value_type* {
  // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
  if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
          Length() + 1, sizeof(value_type)))) {
    return nullptr;
  }
  value_type* elem = Elements() + Length();
  elem_traits::Construct(elem, std::forward<Item>(aItem));
  this->mHdr->mLength += 1;
  return elem;
}

template <typename E, class Alloc>
template <typename ActualAlloc, class... Args>
auto nsTArray_Impl<E, Alloc>::EmplaceBackInternal(Args&&... aArgs)
    -> value_type* {
  // Length() + 1 is guaranteed to not overflow, so EnsureCapacity is OK.
  if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
          Length() + 1, sizeof(value_type)))) {
    return nullptr;
  }
  value_type* elem = Elements() + Length();
  elem_traits::Emplace(elem, std::forward<Args>(aArgs)...);
  this->mHdr->mLength += 1;
  return elem;
}

template <typename E, typename Alloc>
inline void ImplCycleCollectionUnlink(nsTArray_Impl<E, Alloc>& aField) {
  aField.Clear();
}

template <typename E, typename Alloc, typename Callback>
inline void ImplCycleCollectionIndexedContainer(nsTArray_Impl<E, Alloc>& aField,
                                                Callback&& aCallback) {
  for (auto& value : aField) {
    aCallback(value);
  }
}

//
// nsTArray is an infallible vector class.  See the comment at the top of this
// file for more details.
//
template <class E>
class MOZ_GSL_OWNER nsTArray
    : public nsTArray_Impl<E, nsTArrayInfallibleAllocator> {
 public:
  using InfallibleAlloc = nsTArrayInfallibleAllocator;
  using base_type = nsTArray_Impl<E, InfallibleAlloc>;
  using self_type = nsTArray<E>;
  using typename base_type::index_type;
  using typename base_type::size_type;
  using typename base_type::value_type;

  constexpr nsTArray() = default;
  explicit nsTArray(size_type aCapacity) : base_type(aCapacity) {}
  MOZ_IMPLICIT nsTArray(std::initializer_list<E> aIL) {
    AppendElements(aIL.begin(), aIL.size());
  }

  template <class Item>
  nsTArray(const Item* aArray, size_type aArrayLen) {
    AppendElements(aArray, aArrayLen);
  }

  template <class Item>
  explicit nsTArray(mozilla::Span<Item> aSpan) {
    AppendElements(aSpan);
  }

  template <class Allocator>
  explicit nsTArray(const nsTArray_Impl<E, Allocator>& aOther)
      : base_type(aOther) {}
  template <class Allocator>
  MOZ_IMPLICIT nsTArray(nsTArray_Impl<E, Allocator>&& aOther)
      : base_type(std::move(aOther)) {}

  template <class Allocator>
  self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther) {
    base_type::operator=(aOther);
    return *this;
  }
  template <class Allocator>
  self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther) {
    // This is quite complex, since we don't know if we are an AutoTArray. While
    // AutoTArray overrides this operator=, this might be called on a nsTArray&
    // bound to an AutoTArray.
    base_type::operator=(std::move(aOther));
    return *this;
  }

  using base_type::AppendElement;
  using base_type::AppendElements;
  using base_type::EmplaceBack;
  using base_type::EnsureLengthAtLeast;
  using base_type::InsertElementAt;
  using base_type::InsertElementsAt;
  using base_type::InsertElementSorted;
  using base_type::ReplaceElementsAt;
  using base_type::SetCapacity;
  using base_type::SetLength;

  template <class Item>
  mozilla::NotNull<value_type*> AppendElements(const Item* aArray,
                                               size_type aArrayLen) {
    return mozilla::WrapNotNullUnchecked(
        this->template AppendElementsInternal<InfallibleAlloc>(aArray,
                                                               aArrayLen));
  }

  template <class Item>
  mozilla::NotNull<value_type*> AppendElements(mozilla::Span<Item> aSpan) {
    return mozilla::WrapNotNullUnchecked(
        this->template AppendElementsInternal<InfallibleAlloc>(aSpan.Elements(),
                                                               aSpan.Length()));
  }

  template <class Item, class Allocator>
  mozilla::NotNull<value_type*> AppendElements(
      const nsTArray_Impl<Item, Allocator>& aArray) {
    return mozilla::WrapNotNullUnchecked(
        this->template AppendElementsInternal<InfallibleAlloc>(
            aArray.Elements(), aArray.Length()));
  }

  template <class Item, class Allocator>
  mozilla::NotNull<value_type*> AppendElements(
      nsTArray_Impl<Item, Allocator>&& aArray) {
    return mozilla::WrapNotNullUnchecked(
        this->template AppendElementsInternal<InfallibleAlloc>(
            std::move(aArray)));
  }

  template <class Item>
  mozilla::NotNull<value_type*> AppendElement(Item&& aItem) {
    return mozilla::WrapNotNullUnchecked(
        this->template AppendElementInternal<InfallibleAlloc>(
            std::forward<Item>(aItem)));
  }

  mozilla::NotNull<value_type*> AppendElements(size_type aCount) {
    return mozilla::WrapNotNullUnchecked(
        this->template AppendElementsInternal<InfallibleAlloc>(aCount));
  }

  mozilla::NotNull<value_type*> AppendElement() {
    return mozilla::WrapNotNullUnchecked(
        this->template AppendElementsInternal<InfallibleAlloc>(1));
  }

  self_type Clone() const {
    self_type result;
    result.Assign(*this);
    return result;
  }

  mozilla::NotNull<value_type*> InsertElementsAt(index_type aIndex,
                                                 size_type aCount) {
    return mozilla::WrapNotNullUnchecked(
        this->template InsertElementsAtInternal<InfallibleAlloc>(aIndex,
                                                                 aCount));
  }

  template <class Item>
  mozilla::NotNull<value_type*> InsertElementsAt(index_type aIndex,
                                                 size_type aCount,
                                                 const Item& aItem) {
    return mozilla::WrapNotNullUnchecked(
        this->template InsertElementsAtInternal<InfallibleAlloc>(aIndex, aCount,
                                                                 aItem));
  }

  template <class Item>
  mozilla::NotNull<value_type*> InsertElementsAt(index_type aIndex,
                                                 const Item* aArray,
                                                 size_type aArrayLen) {
    return mozilla::WrapNotNullUnchecked(
        this->template ReplaceElementsAtInternal<InfallibleAlloc>(
            aIndex, 0, aArray, aArrayLen));
  }

  template <class Item, class Allocator>
  mozilla::NotNull<value_type*> InsertElementsAt(
      index_type aIndex, const nsTArray_Impl<Item, Allocator>& aArray) {
    return mozilla::WrapNotNullUnchecked(
        this->template ReplaceElementsAtInternal<InfallibleAlloc>(
            aIndex, 0, aArray.Elements(), aArray.Length()));
  }

  template <class Item>
  mozilla::NotNull<value_type*> InsertElementsAt(index_type aIndex,
                                                 mozilla::Span<Item> aSpan) {
    return mozilla::WrapNotNullUnchecked(
        this->template ReplaceElementsAtInternal<InfallibleAlloc>(
            aIndex, 0, aSpan.Elements(), aSpan.Length()));
  }

  mozilla::NotNull<value_type*> InsertElementAt(index_type aIndex) {
    return mozilla::WrapNotNullUnchecked(
        this->template InsertElementAtInternal<InfallibleAlloc>(aIndex));
  }

  template <class Item>
  mozilla::NotNull<value_type*> InsertElementAt(index_type aIndex,
                                                Item&& aItem) {
    return mozilla::WrapNotNullUnchecked(
        this->template InsertElementAtInternal<InfallibleAlloc>(
            aIndex, std::forward<Item>(aItem)));
  }

  template <class Item>
  mozilla::NotNull<value_type*> ReplaceElementsAt(index_type aStart,
                                                  size_type aCount,
                                                  const Item* aArray,
                                                  size_type aArrayLen) {
    return mozilla::WrapNotNullUnchecked(
        this->template ReplaceElementsAtInternal<InfallibleAlloc>(
            aStart, aCount, aArray, aArrayLen));
  }

  template <class Item>
  mozilla::NotNull<value_type*> ReplaceElementsAt(
      index_type aStart, size_type aCount, const nsTArray<Item>& aArray) {
    return ReplaceElementsAt(aStart, aCount, aArray.Elements(),
                             aArray.Length());
  }

  template <class Item>
  mozilla::NotNull<value_type*> ReplaceElementsAt(index_type aStart,
                                                  size_type aCount,
                                                  mozilla::Span<Item> aSpan) {
    return ReplaceElementsAt(aStart, aCount, aSpan.Elements(), aSpan.Length());
  }

  template <class Item>
  mozilla::NotNull<value_type*> ReplaceElementsAt(index_type aStart,
                                                  size_type aCount,
                                                  const Item& aItem) {
    return ReplaceElementsAt(aStart, aCount, &aItem, 1);
  }

  template <class Item, class Comparator>
  mozilla::NotNull<value_type*> InsertElementSorted(Item&& aItem,
                                                    const Comparator& aComp) {
    return mozilla::WrapNotNullUnchecked(
        this->template InsertElementSortedInternal<InfallibleAlloc>(
            std::forward<Item>(aItem), aComp));
  }

  template <class Item>
  mozilla::NotNull<value_type*> InsertElementSorted(Item&& aItem) {
    return mozilla::WrapNotNullUnchecked(
        this->template InsertElementSortedInternal<InfallibleAlloc>(
            std::forward<Item>(aItem),
            nsDefaultComparator<value_type, Item>{}));
  }

  template <class... Args>
  mozilla::NotNull<value_type*> EmplaceBack(Args&&... aArgs) {
    return mozilla::WrapNotNullUnchecked(
        this->template EmplaceBackInternal<InfallibleAlloc, Args...>(
            std::forward<Args>(aArgs)...));
  }
};

template <class E>
class MOZ_GSL_OWNER CopyableTArray : public nsTArray<E> {
 public:
  using nsTArray<E>::nsTArray;

  CopyableTArray(const CopyableTArray& aOther) : nsTArray<E>() {
    this->Assign(aOther);
  }
  CopyableTArray& operator=(const CopyableTArray& aOther) {
    if (this != &aOther) {
      this->Assign(aOther);
    }
    return *this;
  }
  template <typename Allocator>
  MOZ_IMPLICIT CopyableTArray(const nsTArray_Impl<E, Allocator>& aOther) {
    this->Assign(aOther);
  }
  template <typename Allocator>
  CopyableTArray& operator=(const nsTArray_Impl<E, Allocator>& aOther) {
    if constexpr (std::is_same_v<Allocator, nsTArrayInfallibleAllocator>) {
      if (this == &aOther) {
        return *this;
      }
    }
    this->Assign(aOther);
    return *this;
  }
  template <typename Allocator>
  MOZ_IMPLICIT CopyableTArray(nsTArray_Impl<E, Allocator>&& aOther)
      : nsTArray<E>{std::move(aOther)} {}
  template <typename Allocator>
  CopyableTArray& operator=(nsTArray_Impl<E, Allocator>&& aOther) {
    static_cast<nsTArray<E>&>(*this) = std::move(aOther);
    return *this;
  }

  CopyableTArray(CopyableTArray&&) = default;
  CopyableTArray& operator=(CopyableTArray&&) = default;
};

//
// FallibleTArray is a fallible vector class.
//
template <class E>
class MOZ_GSL_OWNER FallibleTArray
    : public nsTArray_Impl<E, nsTArrayFallibleAllocator> {
 public:
  typedef nsTArray_Impl<E, nsTArrayFallibleAllocator> base_type;
  typedef FallibleTArray<E> self_type;
  typedef typename base_type::size_type size_type;

  FallibleTArray() = default;
  explicit FallibleTArray(size_type aCapacity) : base_type(aCapacity) {}

  template <class Allocator>
  explicit FallibleTArray(const nsTArray_Impl<E, Allocator>& aOther)
      : base_type(aOther) {}
  template <class Allocator>
  explicit FallibleTArray(nsTArray_Impl<E, Allocator>&& aOther)
      : base_type(std::move(aOther)) {}

  template <class Allocator>
  self_type& operator=(const nsTArray_Impl<E, Allocator>& aOther) {
    base_type::operator=(aOther);
    return *this;
  }
  template <class Allocator>
  self_type& operator=(nsTArray_Impl<E, Allocator>&& aOther) {
    base_type::operator=(std::move(aOther));
    return *this;
  }
};

//
// AutoTArray<E, N> is like nsTArray<E>, but with N elements of inline storage.
// Storing more than N elements is fine, but it will cause a heap allocation.
//
template <class E, size_t N>
class MOZ_NON_MEMMOVABLE MOZ_GSL_OWNER AutoTArray : public nsTArray<E> {
  static_assert(N != 0, "AutoTArray<E, 0> should be specialized");

 public:
  typedef AutoTArray<E, N> self_type;
  typedef nsTArray<E> base_type;
  typedef typename base_type::Header Header;
  typedef typename base_type::value_type value_type;

  AutoTArray() {
    static_assert(alignof(value_type) <= 8,
                  "can't handle alignments greater than 8, "
                  "see nsTArray_base::UsesAutoArrayBuffer()");
    static_assert(offsetof(AutoTArray, mAutoBuf) == kAutoTArrayHeaderOffset);
    this->mHdr = &mAutoBuf.mHdr;
  }

  AutoTArray(self_type&& aOther) : AutoTArray() {
    this->MoveInit(aOther, sizeof(value_type));
    MOZ_ASSERT(!this->HasEmptyHeader());
  }

  explicit AutoTArray(base_type&& aOther) : AutoTArray() {
    this->MoveInit(aOther, sizeof(value_type));
  }

  template <typename Allocator>
  explicit AutoTArray(nsTArray_Impl<value_type, Allocator>&& aOther)
      : AutoTArray() {
    this->MoveInit(aOther, sizeof(value_type));
  }

  MOZ_IMPLICIT AutoTArray(std::initializer_list<E> aIL) : AutoTArray() {
    this->AppendElements(aIL.begin(), aIL.size());
  }

  self_type& operator=(self_type&& aOther) {
    base_type::operator=(std::move(aOther));
    return *this;
  }

  template <typename Allocator>
  self_type& operator=(nsTArray_Impl<value_type, Allocator>&& aOther) {
    base_type::operator=(std::move(aOther));
    return *this;
  }

  // Intentionally hides nsTArray_Impl::Clone to make clones usually be
  // AutoTArray as well.
  self_type Clone() const {
    self_type result;
    result.Assign(*this);
    return result;
  }

 private:
  // Declare mAutoBuf aligned to 8 bytes so we have a constant offset to get
  // from the nsTArray to the buffer. This can create 4 otherwise-unnecessary
  // bytes of padding on 32-bit builds if value_type is not 8-byte aligned, but
  // that seems acceptable.
  struct alignas(8) AutoBuffer {
    nsTArrayHeader mHdr;
    union alignas(value_type) {
      // FIXME: Conceptually `value_type mElements[N]`, but that upsets the
      // hazard analysis, see bug 1880185.
      char mStorage[sizeof(value_type) * N];
    };
    AutoBuffer() : mHdr{.mLength = 0, .mCapacity = N, .mIsAutoArray = true} {}
    ~AutoBuffer() = default;
  } mAutoBuf;
  static_assert(offsetof(AutoBuffer, mStorage) == sizeof(nsTArrayHeader),
                "Shouldn't have padding");
};

//
// Specialization of AutoTArray<E, N> for the case where N == 0.
// AutoTArray<E, 0> behaves exactly like nsTArray<E>, but without this
// specialization, it stores a useless inline header.
//
// We do have many AutoTArray<E, 0> objects in memory: about 2,000 per tab as
// of May 2014. These are typically not explicitly AutoTArray<E, 0> but rather
// AutoTArray<E, N> for some value N depending on template parameters, in
// generic code.
//
// For that reason, we optimize this case with the below partial specialization,
// which ensures that AutoTArray<E, 0> is just like nsTArray<E>, without any
// inline header overhead.
//
template <class E>
class AutoTArray<E, 0> : public nsTArray<E> {
  using nsTArray<E>::nsTArray;
};

template <class E, size_t N>
struct nsTArray_RelocationStrategy<AutoTArray<E, N>> {
  using Type = nsTArray_RelocateUsingMoveConstructor<AutoTArray<E, N>>;
};

template <class E, size_t N>
class CopyableAutoTArray : public AutoTArray<E, N> {
 public:
  typedef CopyableAutoTArray<E, N> self_type;
  using AutoTArray<E, N>::AutoTArray;

  CopyableAutoTArray(const CopyableAutoTArray& aOther) : AutoTArray<E, N>() {
    this->Assign(aOther);
  }
  CopyableAutoTArray& operator=(const CopyableAutoTArray& aOther) {
    if (this != &aOther) {
      this->Assign(aOther);
    }
    return *this;
  }
  template <typename Allocator>
  MOZ_IMPLICIT CopyableAutoTArray(const nsTArray_Impl<E, Allocator>& aOther) {
    this->Assign(aOther);
  }
  template <typename Allocator>
  CopyableAutoTArray& operator=(const nsTArray_Impl<E, Allocator>& aOther) {
    if constexpr (std::is_same_v<Allocator, nsTArrayInfallibleAllocator>) {
      if (this == &aOther) {
        return *this;
      }
    }
    this->Assign(aOther);
    return *this;
  }
  template <typename Allocator>
  MOZ_IMPLICIT CopyableAutoTArray(nsTArray_Impl<E, Allocator>&& aOther)
      : AutoTArray<E, N>{std::move(aOther)} {}
  template <typename Allocator>
  CopyableAutoTArray& operator=(nsTArray_Impl<E, Allocator>&& aOther) {
    static_cast<AutoTArray<E, N>&>(*this) = std::move(aOther);
    return *this;
  }

  // CopyableTArray exists for cases where an explicit Clone is not possible.
  // These uses should not be mixed, so we delete Clone() here.
  self_type Clone() const = delete;

  CopyableAutoTArray(CopyableAutoTArray&&) = default;
  CopyableAutoTArray& operator=(CopyableAutoTArray&&) = default;
};

// NOTE: We don't use MOZ_COUNT_CTOR/MOZ_COUNT_DTOR to perform leak checking of
// nsTArray_base objects intentionally for the following reasons:
// * The leak logging isn't as useful as other types of logging, as
//   nsTArray_base is frequently relocated without invoking a constructor, such
//   as when stored within another nsTArray. This means that
//   XPCOM_MEM_LOG_CLASSES cannot be used to identify specific leaks of nsTArray
//   objects.
// * The nsTArray type is layout compatible with the ThinVec crate with the
//   correct flags, and ThinVec does not currently perform leak logging.
//   This means that if a large number of arrays are transferred between Rust
//   and C++ code using ThinVec, for example within another ThinVec, they
//   will not be logged correctly and might appear as e.g. negative leaks.
// * Leaks which have been found thanks to the leak logging added by this
//   type have often not been significant, and/or have needed to be
//   circumvented using some other mechanism. Most leaks found with this type
//   in them also include other types which will continue to be tracked.

template <typename RelocationStrategy>
nsTArray_base<RelocationStrategy>::~nsTArray_base() {
  if (!HasEmptyHeader() && !UsesAutoArrayBuffer()) {
    nsTArrayInfallibleAllocator::Free(mHdr);
  }
}

// defined in nsTArray.cpp
bool IsTwiceTheRequiredBytesRepresentableAsUint32(size_t aCapacity,
                                                  size_t aElemSize);

template <typename RelocationStrategy>
template <typename Alloc>
typename Alloc::ResultTypeProxy
nsTArray_base<RelocationStrategy>::ExtendCapacity(size_type aLength,
                                                  size_type aCount,
                                                  size_type aElemSize) {
  mozilla::CheckedInt<size_type> newLength = aLength;
  newLength += aCount;

  if (!newLength.isValid()) {
    return Alloc::FailureResult();
  }

  return this->EnsureCapacity<Alloc>(newLength.value(), aElemSize);
}

template <class RelocationStrategy>
template <typename Alloc>
typename Alloc::ResultTypeProxy
nsTArray_base<RelocationStrategy>::EnsureCapacityImpl(size_type aCapacity,
                                                      size_type aElemSize) {
  MOZ_ASSERT(aCapacity > mHdr->mCapacity,
             "Should have been checked by caller (EnsureCapacity)");

  // If the requested memory allocation exceeds size_type(-1)/2, then
  // our doubling algorithm may not be able to allocate it.
  // Additionally, if it exceeds uint32_t(-1) then we couldn't fit in the
  // Header::mCapacity member. Just bail out in cases like that.  We don't want
  // to be allocating 2 GB+ arrays anyway.
  if (!IsTwiceTheRequiredBytesRepresentableAsUint32(aCapacity, aElemSize)) {
    Alloc::SizeTooBig((size_t)aCapacity * aElemSize);
    return Alloc::FailureResult();
  }

  size_t reqSize = sizeof(Header) + aCapacity * aElemSize;

  if (HasEmptyHeader()) {
    // Malloc() new data
    Header* header = static_cast<Header*>(Alloc::Malloc(reqSize));
    if (!header) {
      return Alloc::FailureResult();
    }
    header->mLength = 0;
    header->mCapacity = aCapacity;
    header->mIsAutoArray = false;
    mHdr = header;

    return Alloc::SuccessResult();
  }

  // We increase our capacity so that the allocated buffer grows exponentially,
  // which gives us amortized O(1) appending. Below the threshold, we use
  // powers-of-two. Above the threshold, we grow by at least 1.125, rounding up
  // to the nearest MiB.
  const size_t slowGrowthThreshold = 8 * 1024 * 1024;

  size_t bytesToAlloc;
  if (reqSize >= slowGrowthThreshold) {
    size_t currSize = sizeof(Header) + Capacity() * aElemSize;
    size_t minNewSize = currSize + (currSize >> 3);  // multiply by 1.125
    bytesToAlloc = reqSize > minNewSize ? reqSize : minNewSize;

    // Round up to the next multiple of MiB.
    const size_t MiB = 1 << 20;
    bytesToAlloc = MiB * ((bytesToAlloc + MiB - 1) / MiB);
  } else {
    // Round up to the next power of two.
    bytesToAlloc = mozilla::RoundUpPow2(reqSize);
  }

  Header* header;
  if (UsesAutoArrayBuffer() || !RelocationStrategy::allowRealloc) {
    // Malloc() and copy
    header = static_cast<Header*>(Alloc::Malloc(bytesToAlloc));
    if (!header) {
      return Alloc::FailureResult();
    }

    RelocationStrategy::RelocateNonOverlappingRegionWithHeader(
        header, mHdr, Length(), aElemSize);

    if (!UsesAutoArrayBuffer()) {
      Alloc::Free(mHdr);
    }
  } else {
    // Realloc() existing data
    header = static_cast<Header*>(Alloc::Realloc(mHdr, bytesToAlloc));
    if (!header) {
      return Alloc::FailureResult();
    }
  }

  // How many elements can we fit in bytesToAlloc?
  size_t newCapacity = (bytesToAlloc - sizeof(Header)) / aElemSize;
  MOZ_ASSERT(newCapacity >= aCapacity, "Didn't enlarge the array enough!");
  header->mCapacity = newCapacity;

  mHdr = header;

  return Alloc::SuccessResult();
}

// We don't need use Alloc template parameter specified here because failure to
// shrink the capacity will leave the array unchanged.
template <typename RelocationStrategy>
void nsTArray_base<RelocationStrategy>::ShrinkCapacity(size_type aElemSize) {
  if (HasEmptyHeader()) {
    return;
  }

  size_type length = Length();
  // Try to switch to our auto-buffer if possible.
  if (auto* autoHdr = GetAutoArrayHeader()) {
    if (mHdr == autoHdr) {
      return;
    }
    if (autoHdr->mCapacity >= length) {
      RelocationStrategy::RelocateNonOverlappingRegion(autoHdr + 1, mHdr + 1,
                                                       length, aElemSize);
      autoHdr->mLength = length;
      nsTArrayFallibleAllocator::Free(mHdr);
      mHdr = autoHdr;
      return;
    }
  }

  if (length == 0) {
    MOZ_ASSERT(!mHdr->mIsAutoArray, "Should've been dealt with above.");
    nsTArrayFallibleAllocator::Free(mHdr);
    mHdr = EmptyHdr();
    return;
  }

  if (length >= mHdr->mCapacity) {  // should never be greater than...
    return;
  }

  size_type newSize = sizeof(Header) + length * aElemSize;

  Header* newHeader;
  if (!RelocationStrategy::allowRealloc) {
    // Malloc() and copy.
    newHeader =
        static_cast<Header*>(nsTArrayFallibleAllocator::Malloc(newSize));
    if (!newHeader) {
      return;
    }

    RelocationStrategy::RelocateNonOverlappingRegionWithHeader(
        newHeader, mHdr, Length(), aElemSize);

    nsTArrayFallibleAllocator::Free(mHdr);
  } else {
    // Realloc() existing data.
    newHeader =
        static_cast<Header*>(nsTArrayFallibleAllocator::Realloc(mHdr, newSize));
    if (!newHeader) {
      return;
    }
  }

  mHdr = newHeader;
  mHdr->mCapacity = length;
}

template <typename RelocationStrategy>
void nsTArray_base<RelocationStrategy>::ShrinkCapacityToZero() {
  MOZ_ASSERT(mHdr->mLength == 0);

  if (HasEmptyHeader()) {
    return;
  }

  Header* newHdr = EmptyHdr();
  if (auto* autoBuf = GetAutoArrayHeader()) {
    if (mHdr == autoBuf) {
      return;
    }
    newHdr = autoBuf;
    newHdr->mLength = 0;
  }

  nsTArrayFallibleAllocator::Free(mHdr);
  mHdr = newHdr;
}

template <typename RelocationStrategy>
template <typename Alloc>
void nsTArray_base<RelocationStrategy>::ShiftData(index_type aStart,
                                                  size_type aOldLen,
                                                  size_type aNewLen,
                                                  size_type aElemSize) {
  if (aOldLen == aNewLen) {
    return;
  }

  // Determine how many elements need to be shifted
  size_type num = mHdr->mLength - (aStart + aOldLen);

  // Compute the resulting length of the array
  mHdr->mLength += aNewLen - aOldLen;
  if (mHdr->mLength == 0) {
    ShrinkCapacityToZero();
    return;
  }
  // Maybe nothing needs to be shifted
  if (num == 0) {
    return;
  }
  // Perform shift (change units to bytes first)
  aStart *= aElemSize;
  aNewLen *= aElemSize;
  aOldLen *= aElemSize;
  char* baseAddr = reinterpret_cast<char*>(mHdr + 1) + aStart;
  RelocationStrategy::RelocateOverlappingRegion(
      baseAddr + aNewLen, baseAddr + aOldLen, num, aElemSize);
}

template <typename RelocationStrategy>
template <typename Alloc>
void nsTArray_base<RelocationStrategy>::SwapFromEnd(index_type aStart,
                                                    size_type aCount,
                                                    size_type aElemSize) {
  // This method is part of the implementation of
  // nsTArray::SwapRemoveElement{s,}At. For more information, read the
  // documentation on that method.
  if (aCount == 0) {
    return;
  }

  // We are going to be removing aCount elements. Update our length to point to
  // the new end of the array.
  size_type oldLength = mHdr->mLength;
  mHdr->mLength -= aCount;

  if (mHdr->mLength == 0) {
    // If we have no elements remaining in the array, we can free our buffer.
    ShrinkCapacityToZero();
    return;
  }

  // Determine how many elements we need to move from the end of the array into
  // the now-removed section. This will either be the number of elements which
  // were removed (if there are more elements in the tail of the array), or the
  // entire tail of the array, whichever is smaller.
  size_type relocCount = std::min(aCount, mHdr->mLength - aStart);
  if (relocCount == 0) {
    return;
  }

  // Move the elements which are now stranded after the end of the array back
  // into the now-vacated memory.
  index_type sourceBytes = (oldLength - relocCount) * aElemSize;
  index_type destBytes = aStart * aElemSize;

  // Perform the final copy. This is guaranteed to be a non-overlapping copy
  // as our source contains only still-valid entries, and the destination
  // contains only invalid entries which need to be overwritten.
  MOZ_ASSERT(sourceBytes >= destBytes,
             "The source should be after the destination.");
  MOZ_ASSERT(sourceBytes - destBytes >= relocCount * aElemSize,
             "The range should be nonoverlapping");

  char* baseAddr = reinterpret_cast<char*>(mHdr + 1);
  RelocationStrategy::RelocateNonOverlappingRegion(
      baseAddr + destBytes, baseAddr + sourceBytes, relocCount, aElemSize);
}

template <typename RelocationStrategy>
template <typename Alloc>
typename Alloc::ResultTypeProxy
nsTArray_base<RelocationStrategy>::InsertSlotsAt(index_type aIndex,
                                                 size_type aCount,
                                                 size_type aElemSize) {
  if (MOZ_UNLIKELY(aIndex > Length())) {
    mozilla::detail::InvalidArrayIndex_CRASH(aIndex, Length());
  }

  if (!Alloc::Successful(
          this->ExtendCapacity<Alloc>(Length(), aCount, aElemSize))) {
    return Alloc::FailureResult();
  }

  // Move the existing elements as needed.  Note that this will
  // change our mLength, so no need to call IncrementLength.
  ShiftData<Alloc>(aIndex, 0, aCount, aElemSize);

  return Alloc::SuccessResult();
}

template <class RelocationStrategy>
template <typename Alloc>
typename Alloc::ResultTypeProxy
nsTArray_base<RelocationStrategy>::SwapArrayElements(
    nsTArray_base<RelocationStrategy>& aOther, size_type aElemSize) {
  // If neither array uses an auto buffer which is big enough to store the
  // other array's elements, then ensure that both arrays use malloc'ed storage
  // and swap their mHdr pointers.
  if ((!UsesAutoArrayBuffer() || Capacity() < aOther.Length()) &&
      (!aOther.UsesAutoArrayBuffer() || aOther.Capacity() < Length())) {
    auto* thisHdr = TakeHeaderForMove<Alloc>(aElemSize);
    if (MOZ_UNLIKELY(!thisHdr)) {
      return Alloc::FailureResult();
    }
    auto* otherHdr = aOther.template TakeHeaderForMove<Alloc>(aElemSize);
    if (MOZ_UNLIKELY(!otherHdr)) {
      // Ensure thisHdr and the elements inside it are safely
      // cleaned up in this error case, by returning it to
      // being owned by this.
      MOZ_ASSERT(UsesAutoArrayBuffer() || HasEmptyHeader());
      thisHdr->mIsAutoArray = mHdr->mIsAutoArray;
      mHdr = thisHdr;
      return Alloc::FailureResult();
    }
    // Avoid replacing the potentially auto-buffer with the empty header if
    // we're empty.
    if (otherHdr != EmptyHdr()) {
      otherHdr->mIsAutoArray = mHdr->mIsAutoArray;
      mHdr = otherHdr;
    }
    if (thisHdr != EmptyHdr()) {
      thisHdr->mIsAutoArray = aOther.mHdr->mIsAutoArray;
      aOther.mHdr = thisHdr;
    }
    return Alloc::SuccessResult();
  }

  // Swap the two arrays by copying, since at least one is using an auto
  // buffer which is large enough to hold all of the aOther's elements.  We'll
  // copy the shorter array into temporary storage.
  //
  // (We could do better than this in some circumstances.  Suppose we're
  // swapping arrays X and Y.  X has space for 2 elements in its auto buffer,
  // but currently has length 4, so it's using malloc'ed storage.  Y has length
  // 2.  When we swap X and Y, we don't need to use a temporary buffer; we can
  // write Y straight into X's auto buffer, write X's malloc'ed buffer on top
  // of Y, and then switch X to using its auto buffer.)

  if (!Alloc::Successful(EnsureCapacity<Alloc>(aOther.Length(), aElemSize)) ||
      !Alloc::Successful(
          aOther.template EnsureCapacity<Alloc>(Length(), aElemSize))) {
    return Alloc::FailureResult();
  }

  // The EnsureCapacity calls above shouldn't have caused *both* arrays to
  // switch from their auto buffers to malloc'ed space.
  MOZ_ASSERT(UsesAutoArrayBuffer() || aOther.UsesAutoArrayBuffer(),
             "One of the arrays should be using its auto buffer.");

  size_type smallerLength = XPCOM_MIN(Length(), aOther.Length());
  size_type largerLength = XPCOM_MAX(Length(), aOther.Length());
  void* smallerElements;
  void* largerElements;
  if (Length() <= aOther.Length()) {
    smallerElements = Hdr() + 1;
    largerElements = aOther.Hdr() + 1;
  } else {
    smallerElements = aOther.Hdr() + 1;
    largerElements = Hdr() + 1;
  }

  // Allocate temporary storage for the smaller of the two arrays.  We want to
  // allocate this space on the stack, if it's not too large.  Sounds like a
  // job for AutoTArray!  (One of the two arrays we're swapping is using an
  // auto buffer, so we're likely not allocating a lot of space here.  But one
  // could, in theory, allocate a huge AutoTArray on the heap.)
  AutoTArray<uint8_t, 64 * sizeof(void*)> temp;
  if (!Alloc::Successful(temp.template EnsureCapacity<Alloc>(
          smallerLength * aElemSize, sizeof(uint8_t)))) {
    return Alloc::FailureResult();
  }

  RelocationStrategy::RelocateNonOverlappingRegion(
      temp.Elements(), smallerElements, smallerLength, aElemSize);
  RelocationStrategy::RelocateNonOverlappingRegion(
      smallerElements, largerElements, largerLength, aElemSize);
  RelocationStrategy::RelocateNonOverlappingRegion(
      largerElements, temp.Elements(), smallerLength, aElemSize);

  // Swap the arrays' lengths.
  MOZ_ASSERT((aOther.Length() == 0 || !HasEmptyHeader()) &&
                 (Length() == 0 || !aOther.HasEmptyHeader()),
             "Don't set sEmptyTArrayHeader's length.");
  size_type tempLength = Length();

  // Avoid writing to EmptyHdr, since it can trigger false
  // positives with TSan.
  if (!HasEmptyHeader()) {
    mHdr->mLength = aOther.Length();
  }
  if (!aOther.HasEmptyHeader()) {
    aOther.mHdr->mLength = tempLength;
  }

  return Alloc::SuccessResult();
}

template <class RelocationStrategy>
void nsTArray_base<RelocationStrategy>::MoveInit(
    nsTArray_base<RelocationStrategy>& aOther, size_type aElemSize) {
  // This method is similar to SwapArrayElements, but specialized for the case
  // where the target array is empty with no allocated heap storage. It is
  // provided and used to simplify template instantiation and enable better code
  // generation.

  MOZ_ASSERT(Length() == 0);
  MOZ_ASSERT(Capacity() == 0 || UsesAutoArrayBuffer());

  const auto newLength = aOther.Length();
  if (aOther.HasEmptyHeader()) {
    return;
  }

  // If this array doesn't use an auto buffer which is big enough to store the
  // other array's elements, and the other array is using malloc'ed storage,
  // take their mHdr pointer.
  if (!aOther.UsesAutoArrayBuffer() &&
      (!mHdr->mIsAutoArray || Capacity() < newLength)) {
    const bool thisIsAuto = mHdr->mIsAutoArray;
    Header* otherAutoHeader = aOther.GetAutoArrayHeader();
    mHdr = aOther.mHdr;
    mHdr->mIsAutoArray = thisIsAuto;
    if (otherAutoHeader) {
      aOther.mHdr = otherAutoHeader;
      otherAutoHeader->mLength = 0;
    } else {
      aOther.mHdr = EmptyHdr();
    }
    return;
  }

  if (newLength) {
    // Move the data by copying, since at least one has an auto
    // buffer which is large enough to hold all of the aOther's elements.
    EnsureCapacity<nsTArrayInfallibleAllocator>(newLength, aElemSize);

    // The EnsureCapacity calls above shouldn't have caused *both* arrays to
    // switch from their auto buffers to malloc'ed space.
    MOZ_ASSERT(UsesAutoArrayBuffer() || aOther.UsesAutoArrayBuffer(),
               "One of the arrays should be using its auto buffer.");

    RelocationStrategy::RelocateNonOverlappingRegion(
        Hdr() + 1, aOther.Hdr() + 1, newLength, aElemSize);

    // Swap the arrays' lengths.
    MOZ_ASSERT(!HasEmptyHeader() && !aOther.HasEmptyHeader(),
               "Both arrays should have capacity");

    // Update our buffer's length, and reduce the other buffer's length.
    mHdr->mLength = newLength;
    aOther.mHdr->mLength = 0;
  }
  aOther.ShrinkCapacityToZero();
}

template <typename RelocationStrategy>
void nsTArray_base<RelocationStrategy>::MoveConstructNonAutoArray(
    nsTArray_base<RelocationStrategy>& aOther, size_type aElemSize) {
  // We know that we are not an (Copyable)AutoTArray and we know that we are
  // empty, so don't use SwapArrayElements which doesn't know either of these
  // facts and is very complex. Use nsTArrayInfallibleAllocator regardless of
  // Alloc because this is called from a move constructor, which cannot report
  // an error to the caller.
  mHdr =
      aOther.template TakeHeaderForMove<nsTArrayInfallibleAllocator>(aElemSize);
  MOZ_ASSERT(!mHdr->mIsAutoArray);
}

template <class RelocationStrategy>
template <typename Alloc>
auto nsTArray_base<RelocationStrategy>::TakeHeaderForMove(size_type aElemSize)
    -> Header* {
  auto* autoHdr = GetAutoArrayHeader();
  if (!autoHdr) {
    return std::exchange(mHdr, EmptyHdr());
  }

  if (mHdr != autoHdr) {
    MOZ_ASSERT(mHdr->mIsAutoArray);
    MOZ_ASSERT(autoHdr->mIsAutoArray);
    autoHdr->mLength = 0;
    mHdr->mIsAutoArray = false;
    return std::exchange(mHdr, autoHdr);
  }

  const auto length = Length();
  if (!length) {
    return EmptyHdr();
  }

  size_type size = sizeof(Header) + length * aElemSize;
  Header* header = static_cast<Header*>(Alloc::Malloc(size));
  if (!header) {
    return nullptr;
  }

  RelocationStrategy::RelocateNonOverlappingRegionWithHeader(header, mHdr,
                                                             length, aElemSize);
  header->mCapacity = length;
  // This will be set by our caller if needed.
  header->mIsAutoArray = false;

  mHdr->mLength = 0;
  MOZ_ASSERT(UsesAutoArrayBuffer());
  MOZ_ASSERT(IsEmpty());
  return header;
}

namespace mozilla {
template <typename E, typename ArrayT>
class nsTArrayBackInserter {
  ArrayT* mArray;

  class Proxy {
    ArrayT& mArray;

   public:
    explicit Proxy(ArrayT& aArray) : mArray{aArray} {}

    template <typename E2>
    void operator=(E2&& aValue) {
      mArray.AppendElement(std::forward<E2>(aValue));
    }
  };

 public:
  using iterator_category = std::output_iterator_tag;
  using value_type = void;
  using difference_type = void;
  using pointer = void;
  using reference = void;
  explicit nsTArrayBackInserter(ArrayT& aArray) : mArray{&aArray} {}

  // Return a proxy so that nsTArrayBackInserter has the default special member
  // functions, and the operator= template is defined in Proxy rather than this
  // class (which otherwise breaks with recent MS STL versions).
  // See also Bug 1331137, comment 11.
  Proxy operator*() { return Proxy(*mArray); }

  nsTArrayBackInserter& operator++() { return *this; }
  nsTArrayBackInserter& operator++(int) { return *this; }
};
}  // namespace mozilla

template <typename E>
auto MakeBackInserter(nsTArray<E>& aArray) {
  return mozilla::nsTArrayBackInserter<E, nsTArray<E>>{aArray};
}

// Span integration
namespace mozilla {
template <typename E, class Alloc>
Span(nsTArray_Impl<E, Alloc>&) -> Span<E>;

template <typename E, class Alloc>
Span(const nsTArray_Impl<E, Alloc>&) -> Span<const E>;

// Provides a view on a nsTArray through which the existing array elements can
// be accessed in a non-const way, but the array itself cannot be modified, so
// that references to elements are guaranteed to be stable.
template <typename E>
class nsTArrayView {
 public:
  using element_type = E;
  using pointer = element_type*;
  using reference = element_type&;
  using index_type = typename Span<element_type>::index_type;
  using size_type = typename Span<element_type>::index_type;

  explicit nsTArrayView(nsTArray<element_type> aArray)
      : mArray(std::move(aArray)), mSpan(mArray) {}

  element_type& operator[](index_type aIndex) { return mSpan[aIndex]; }

  const element_type& operator[](index_type aIndex) const {
    return mSpan[aIndex];
  }

  size_type Length() const { return mSpan.Length(); }

  auto begin() { return mSpan.begin(); }
  auto end() { return mSpan.end(); }
  auto begin() const { return mSpan.begin(); }
  auto end() const { return mSpan.end(); }
  auto cbegin() const { return mSpan.cbegin(); }
  auto cend() const { return mSpan.cend(); }

  Span<element_type> AsSpan() { return mSpan; }
  Span<const element_type> AsSpan() const { return mSpan; }

 private:
  nsTArray<element_type> mArray;
  const Span<element_type> mSpan;
};

// NOTE(emilio): If changing the name of this or so, make sure to change
// specializations too.
template <typename Range,
          typename = std::enable_if_t<std::is_same_v<
              typename std::iterator_traits<typename std::remove_reference_t<
                  Range>::iterator>::iterator_category,
              std::random_access_iterator_tag>>>
size_t RangeSizeEstimate(const Range& aRange) {
  // See https://en.cppreference.com/w/cpp/iterator/begin, section 'User-defined
  // overloads'.
  using std::begin;
  using std::end;

  return std::distance(begin(aRange), end(aRange));
}

/**
 * Materialize a range as a nsTArray (or a compatible variant, like AutoTArray)
 * of an explicitly specified type. The array value type must be implicitly
 * convertible from the range's value type.
 */
template <typename Array, typename Range>
auto ToTArray(Range&& aRange) {
  using std::begin;
  using std::end;

  Array res;
  if (auto estimate = RangeSizeEstimate(aRange)) {
    res.SetCapacity(estimate);
  }
  std::copy(begin(aRange), end(aRange), MakeBackInserter(res));
  return res;
}

/**
 * Materialize a range as a nsTArray of its (decayed) value type.
 */
template <typename Range>
auto ToArray(Range&& aRange) {
  return ToTArray<nsTArray<std::decay_t<typename std::iterator_traits<
      typename std::remove_reference_t<Range>::iterator>::value_type>>>(
      std::forward<Range>(aRange));
}

/**
 * Appends all elements from a range to an array.
 */
template <typename Array, typename Range>
void AppendToArray(Array& aArray, Range&& aRange) {
  using std::begin;
  using std::end;
  if (auto estimate = RangeSizeEstimate(aRange)) {
    aArray.SetCapacity(aArray.Length() + estimate);
  }
  std::copy(begin(aRange), end(aRange), MakeBackInserter(aArray));
}

}  // namespace mozilla

// MOZ_DBG support

template <class E, class Alloc>
std::ostream& operator<<(std::ostream& aOut,
                         const nsTArray_Impl<E, Alloc>& aTArray) {
  return aOut << mozilla::Span(aTArray);
}

#endif  // nsTArray_h_