Adding upstream version 86.0.1.upstream/86.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

18 files changed, 5842 insertions, 0 deletions

diff --git a/js/src/ds/BitArray.h b/js/src/ds/BitArray.h
new file mode 100644
index 0000000000..bdd78873fd
--- /dev/null
+++ b/js/src/ds/BitArray.h
@@ -0,0 +1,114 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_BitArray_h
+#define ds_BitArray_h
+
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/TemplateLib.h"
+
+#include <limits.h>
+#include <string.h>
+
+#include "jstypes.h"
+
+namespace js {
+
+namespace detail {
+
+template <typename WordT>
+inline uint_fast8_t CountTrailingZeroes(WordT word);
+
+template <>
+inline uint_fast8_t CountTrailingZeroes(uint32_t word) {
+  return mozilla::CountTrailingZeroes32(word);
+}
+
+template <>
+inline uint_fast8_t CountTrailingZeroes(uint64_t word) {
+  return mozilla::CountTrailingZeroes64(word);
+}
+
+}  // namespace detail
+
+template <size_t nbits>
+class BitArray {
+ public:
+  // Use a 32 bit word to make it easier to access a BitArray from JIT code.
+  using WordT = uint32_t;
+
+  static const size_t bitsPerElement = sizeof(WordT) * CHAR_BIT;
+  static const size_t numSlots =
+      nbits / bitsPerElement + (nbits % bitsPerElement == 0 ? 0 : 1);
+
+ private:
+  static const size_t paddingBits = (numSlots * bitsPerElement) - nbits;
+  static_assert(paddingBits < bitsPerElement,
+                "More padding bits than expected.");
+  static const WordT paddingMask = WordT(-1) >> paddingBits;
+
+  WordT map[numSlots];
+
+ public:
+  constexpr BitArray() : map(){};
+
+  void clear(bool value) {
+    memset(map, value ? 0xFF : 0, sizeof(map));
+    if (value) {
+      map[numSlots - 1] &= paddingMask;
+    }
+  }
+
+  inline bool get(size_t offset) const {
+    size_t index;
+    WordT mask;
+    getIndexAndMask(offset, &index, &mask);
+    MOZ_ASSERT(index < nbits);
+    return map[index] & mask;
+  }
+
+  void set(size_t offset) {
+    size_t index;
+    WordT mask;
+    getIndexAndMask(offset, &index, &mask);
+    map[index] |= mask;
+  }
+
+  void unset(size_t offset) {
+    size_t index;
+    WordT mask;
+    getIndexAndMask(offset, &index, &mask);
+    map[index] &= ~mask;
+  }
+
+  bool isAllClear() const {
+    for (size_t i = 0; i < numSlots; i++) {
+      if (map[i]) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  // For iterating over the set bits in the bit array, get a word at a time.
+  WordT getWord(size_t elementIndex) const {
+    MOZ_ASSERT(elementIndex < nbits);
+    return map[elementIndex];
+  }
+
+  static void getIndexAndMask(size_t offset, size_t* indexp, WordT* maskp) {
+    MOZ_ASSERT(offset < nbits);
+    static_assert(bitsPerElement == 32, "unexpected bitsPerElement value");
+    *indexp = offset / bitsPerElement;
+    *maskp = WordT(1) << (offset % bitsPerElement);
+  }
+
+  static size_t offsetOfMap() { return offsetof(BitArray<nbits>, map); }
+};
+
+} /* namespace js */
+
+#endif /* ds_BitArray_h */
diff --git a/js/src/ds/Bitmap.cpp b/js/src/ds/Bitmap.cpp
new file mode 100644
index 0000000000..79f7969e01
--- /dev/null
+++ b/js/src/ds/Bitmap.cpp
@@ -0,0 +1,103 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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/. */
+
+#include "ds/Bitmap.h"
+
+#include <algorithm>
+
+#include "js/UniquePtr.h"
+
+using namespace js;
+
+SparseBitmap::~SparseBitmap() {
+  for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
+    js_delete(r.front().value());
+  }
+}
+
+size_t SparseBitmap::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) {
+  size_t size = data.shallowSizeOfExcludingThis(mallocSizeOf);
+  for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
+    size += mallocSizeOf(r.front().value());
+  }
+  return size;
+}
+
+SparseBitmap::BitBlock* SparseBitmap::createBlock(Data::AddPtr p,
+                                                  size_t blockId) {
+  MOZ_ASSERT(!p);
+  auto block = js::MakeUnique<BitBlock>();
+  if (!block || !data.add(p, blockId, block.get())) {
+    return nullptr;
+  }
+  std::fill(block->begin(), block->end(), 0);
+  return block.release();
+}
+
+SparseBitmap::BitBlock& SparseBitmap::createBlock(
+    Data::AddPtr p, size_t blockId, AutoEnterOOMUnsafeRegion& oomUnsafe) {
+  BitBlock* block = createBlock(p, blockId);
+  if (!block) {
+    oomUnsafe.crash("Bitmap OOM");
+  }
+  return *block;
+}
+
+bool SparseBitmap::getBit(size_t bit) const {
+  size_t word = bit / JS_BITS_PER_WORD;
+  size_t blockWord = blockStartWord(word);
+
+  BitBlock* block = getBlock(blockWord / WordsInBlock);
+  if (block) {
+    return (*block)[word - blockWord] &
+           (uintptr_t(1) << (bit % JS_BITS_PER_WORD));
+  }
+  return false;
+}
+
+void SparseBitmap::bitwiseAndWith(const DenseBitmap& other) {
+  for (Data::Enum e(data); !e.empty(); e.popFront()) {
+    BitBlock& block = *e.front().value();
+    size_t blockWord = e.front().key() * WordsInBlock;
+    bool anySet = false;
+    size_t numWords = wordIntersectCount(blockWord, other);
+    for (size_t i = 0; i < numWords; i++) {
+      block[i] &= other.word(blockWord + i);
+      anySet |= !!block[i];
+    }
+    if (!anySet) {
+      js_delete(&block);
+      e.removeFront();
+    }
+  }
+}
+
+void SparseBitmap::bitwiseOrWith(const SparseBitmap& other) {
+  for (Data::Range r(other.data.all()); !r.empty(); r.popFront()) {
+    const BitBlock& otherBlock = *r.front().value();
+    BitBlock& block = getOrCreateBlock(r.front().key());
+    for (size_t i = 0; i < WordsInBlock; i++) {
+      block[i] |= otherBlock[i];
+    }
+  }
+}
+
+void SparseBitmap::bitwiseOrInto(DenseBitmap& other) const {
+  for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
+    BitBlock& block = *r.front().value();
+    size_t blockWord = r.front().key() * WordsInBlock;
+    size_t numWords = wordIntersectCount(blockWord, other);
+#ifdef DEBUG
+    // Any words out of range in other should be zero in this bitmap.
+    for (size_t i = numWords; i < WordsInBlock; i++) {
+      MOZ_ASSERT(!block[i]);
+    }
+#endif
+    for (size_t i = 0; i < numWords; i++) {
+      other.word(blockWord + i) |= block[i];
+    }
+  }
+}
diff --git a/js/src/ds/Bitmap.h b/js/src/ds/Bitmap.h
new file mode 100644
index 0000000000..74b04bfe3f
--- /dev/null
+++ b/js/src/ds/Bitmap.h
@@ -0,0 +1,176 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_Bitmap_h
+#define ds_Bitmap_h
+
+#include "mozilla/Array.h"
+#include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
+#include "mozilla/MemoryChecking.h"
+
+#include <algorithm>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "js/AllocPolicy.h"
+#include "js/HashTable.h"
+#include "js/HeapAPI.h"
+#include "js/Vector.h"
+
+// This file provides two classes for representing bitmaps.
+//
+// DenseBitmap is an array of words of bits, with size linear in the maximum
+// bit which has been set on it.
+//
+// SparseBitmap provides a reasonably simple, reasonably efficient (in time and
+// space) implementation of a sparse bitmap. The basic representation is a hash
+// table whose entries are fixed length malloc'ed blocks of bits.
+
+namespace js {
+
+class DenseBitmap {
+  using Data = Vector<uintptr_t, 0, SystemAllocPolicy>;
+
+  Data data;
+
+ public:
+  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) {
+    return data.sizeOfExcludingThis(mallocSizeOf);
+  }
+
+  bool ensureSpace(size_t numWords) {
+    MOZ_ASSERT(data.empty());
+    return data.appendN(0, numWords);
+  }
+
+  size_t numWords() const { return data.length(); }
+  uintptr_t word(size_t i) const { return data[i]; }
+  uintptr_t& word(size_t i) { return data[i]; }
+
+  template <typename T>
+  typename std::enable_if_t<std::is_convertible_v<T, uintptr_t>, void>
+  copyBitsFrom(size_t wordStart, size_t numWords, T* source) {
+    MOZ_ASSERT(wordStart + numWords <= data.length());
+    for (size_t i = 0; i < numWords; i++) {
+      data[wordStart + i] = source[i];
+    }
+  }
+
+  template <typename T>
+  typename std::enable_if_t<std::is_convertible_v<T, uintptr_t>, void>
+  bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const {
+    for (size_t i = 0; i < numWords; i++) {
+      target[i] |= data[wordStart + i];
+    }
+  }
+};
+
+class SparseBitmap {
+  // The number of words of bits to use for each block mainly affects the
+  // memory usage of the bitmap. To minimize overhead, bitmaps which are
+  // expected to be fairly dense should have a large block size, and bitmaps
+  // which are expected to be very sparse should have a small block size.
+  static const size_t WordsInBlock = 4096 / sizeof(uintptr_t);
+
+  using BitBlock = mozilla::Array<uintptr_t, WordsInBlock>;
+  using Data =
+      HashMap<size_t, BitBlock*, DefaultHasher<size_t>, SystemAllocPolicy>;
+
+  Data data;
+
+  static size_t blockStartWord(size_t word) {
+    return word & ~(WordsInBlock - 1);
+  }
+
+  // Return the number of words in a BitBlock starting at |blockWord| which
+  // are in |other|.
+  static size_t wordIntersectCount(size_t blockWord, const DenseBitmap& other) {
+    long count = other.numWords() - blockWord;
+    return std::min<size_t>((size_t)WordsInBlock, std::max<long>(count, 0));
+  }
+
+  BitBlock& createBlock(Data::AddPtr p, size_t blockId,
+                        AutoEnterOOMUnsafeRegion& oomUnsafe);
+
+  BitBlock* createBlock(Data::AddPtr p, size_t blockId);
+
+  MOZ_ALWAYS_INLINE BitBlock* getBlock(size_t blockId) const {
+    Data::Ptr p = data.lookup(blockId);
+    return p ? p->value() : nullptr;
+  }
+
+  MOZ_ALWAYS_INLINE BitBlock& getOrCreateBlock(size_t blockId) {
+    // The lookupForAdd() needs protection against injected OOMs, as does
+    // the add() within createBlock().
+    AutoEnterOOMUnsafeRegion oomUnsafe;
+    Data::AddPtr p = data.lookupForAdd(blockId);
+    if (p) {
+      return *p->value();
+    }
+    return createBlock(p, blockId, oomUnsafe);
+  }
+
+  MOZ_ALWAYS_INLINE BitBlock* getOrCreateBlockFallible(size_t blockId) {
+    Data::AddPtr p = data.lookupForAdd(blockId);
+    if (p) {
+      return p->value();
+    }
+    return createBlock(p, blockId);
+  }
+
+ public:
+  ~SparseBitmap();
+
+  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
+
+  MOZ_ALWAYS_INLINE void setBit(size_t bit) {
+    size_t word = bit / JS_BITS_PER_WORD;
+    size_t blockWord = blockStartWord(word);
+    BitBlock& block = getOrCreateBlock(blockWord / WordsInBlock);
+    block[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
+  }
+
+  MOZ_ALWAYS_INLINE bool setBitFallible(size_t bit) {
+    size_t word = bit / JS_BITS_PER_WORD;
+    size_t blockWord = blockStartWord(word);
+    BitBlock* block = getOrCreateBlockFallible(blockWord / WordsInBlock);
+    if (!block) {
+      return false;
+    }
+    (*block)[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
+    return true;
+  }
+
+  bool getBit(size_t bit) const;
+
+  void bitwiseAndWith(const DenseBitmap& other);
+  void bitwiseOrWith(const SparseBitmap& other);
+  void bitwiseOrInto(DenseBitmap& other) const;
+
+  // Currently, this API only supports a range of words that is in a single bit
+  // block.
+  template <typename T>
+  typename std::enable_if_t<std::is_convertible_v<T, uintptr_t>, void>
+  bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const {
+    size_t blockWord = blockStartWord(wordStart);
+
+    // We only support using a single bit block in this API.
+    MOZ_ASSERT(numWords &&
+               (blockWord == blockStartWord(wordStart + numWords - 1)));
+
+    BitBlock* block = getBlock(blockWord / WordsInBlock);
+    if (block) {
+      for (size_t i = 0; i < numWords; i++) {
+        target[i] |= (*block)[wordStart - blockWord + i];
+      }
+    }
+  }
+};
+
+}  // namespace js
+
+#endif  // ds_Bitmap_h
diff --git a/js/src/ds/Fifo.h b/js/src/ds/Fifo.h
new file mode 100644
index 0000000000..236412f2cc
--- /dev/null
+++ b/js/src/ds/Fifo.h
@@ -0,0 +1,187 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 js_Fifo_h
+#define js_Fifo_h
+
+#include <algorithm>
+#include <utility>
+
+#include "js/Vector.h"
+
+namespace js {
+
+// A first-in-first-out queue container type. Fifo calls constructors and
+// destructors of all elements added so non-PODs may be used safely. |Fifo|
+// stores the first |MinInlineCapacity| elements in-place before resorting to
+// dynamic allocation.
+//
+// T requirements:
+//  - Either movable or copyable.
+// MinInlineCapacity requirements:
+//  - Must be even.
+// AllocPolicy:
+//  - see "Allocation policies" in AllocPolicy.h
+template <typename T, size_t MinInlineCapacity = 0,
+          class AllocPolicy = TempAllocPolicy>
+class Fifo {
+  static_assert(MinInlineCapacity % 2 == 0, "MinInlineCapacity must be even!");
+
+ protected:
+  // An element A is "younger" than an element B if B was inserted into the
+  // |Fifo| before A was.
+  //
+  // Invariant 1: Every element within |front_| is older than every element
+  // within |rear_|.
+  // Invariant 2: Entries within |front_| are sorted from younger to older.
+  // Invariant 3: Entries within |rear_| are sorted from older to younger.
+  // Invariant 4: If the |Fifo| is not empty, then |front_| is not empty.
+  Vector<T, MinInlineCapacity / 2, AllocPolicy> front_;
+  Vector<T, MinInlineCapacity / 2, AllocPolicy> rear_;
+
+ private:
+  // Maintain invariants after adding or removing entries.
+  void fixup() {
+    if (front_.empty() && !rear_.empty()) {
+      front_.swap(rear_);
+      std::reverse(front_.begin(), front_.end());
+    }
+  }
+
+ public:
+  explicit Fifo(AllocPolicy alloc = AllocPolicy())
+      : front_(alloc), rear_(alloc) {}
+
+  Fifo(Fifo&& rhs)
+      : front_(std::move(rhs.front_)), rear_(std::move(rhs.rear_)) {}
+
+  Fifo& operator=(Fifo&& rhs) {
+    MOZ_ASSERT(&rhs != this, "self-move disallowed");
+    this->~Fifo();
+    new (this) Fifo(std::move(rhs));
+    return *this;
+  }
+
+  Fifo(const Fifo&) = delete;
+  Fifo& operator=(const Fifo&) = delete;
+
+  size_t length() const {
+    MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0);  // Invariant 4.
+    return front_.length() + rear_.length();
+  }
+
+  bool empty() const {
+    MOZ_ASSERT_IF(rear_.length() > 0, front_.length() > 0);  // Invariant 4.
+    return front_.empty();
+  }
+
+  // Iterator from oldest to yongest element.
+  struct ConstIterator {
+    const Fifo& self_;
+    size_t idx_;
+
+    ConstIterator(const Fifo& self, size_t idx) : self_(self), idx_(idx) {}
+
+    ConstIterator& operator++() {
+      ++idx_;
+      return *this;
+    }
+
+    const T& operator*() const {
+      // Iterate front in reverse, then rear.
+      size_t split = self_.front_.length();
+      return (idx_ < split) ? self_.front_[(split - 1) - idx_]
+                            : self_.rear_[idx_ - split];
+    }
+
+    bool operator!=(const ConstIterator& other) const {
+      return (&self_ != &other.self_) || (idx_ != other.idx_);
+    }
+  };
+
+  ConstIterator begin() const { return ConstIterator(*this, 0); }
+
+  ConstIterator end() const { return ConstIterator(*this, length()); }
+
+  // Push an element to the back of the queue. This method can take either a
+  // |const T&| or a |T&&|.
+  template <typename U>
+  MOZ_MUST_USE bool pushBack(U&& u) {
+    if (!rear_.append(std::forward<U>(u))) {
+      return false;
+    }
+    fixup();
+    return true;
+  }
+
+  // Construct a T in-place at the back of the queue.
+  template <typename... Args>
+  MOZ_MUST_USE bool emplaceBack(Args&&... args) {
+    if (!rear_.emplaceBack(std::forward<Args>(args)...)) {
+      return false;
+    }
+    fixup();
+    return true;
+  }
+
+  // Access the element at the front of the queue.
+  T& front() {
+    MOZ_ASSERT(!empty());
+    return front_.back();
+  }
+  const T& front() const {
+    MOZ_ASSERT(!empty());
+    return front_.back();
+  }
+
+  // Remove the front element from the queue.
+  void popFront() {
+    MOZ_ASSERT(!empty());
+    front_.popBack();
+    fixup();
+  }
+
+  // Convenience utility.
+  T popCopyFront() {
+    T ret = front();
+    popFront();
+    return ret;
+  }
+
+  // Clear all elements from the queue.
+  void clear() {
+    front_.clear();
+    rear_.clear();
+  }
+
+  // Clear all elements for which the given predicate returns 'true'. Return
+  // the number of elements removed.
+  template <class Pred>
+  size_t eraseIf(Pred pred) {
+    size_t frontLength = front_.length();
+    front_.eraseIf(pred);
+    size_t erased = frontLength - front_.length();
+
+    size_t rearLength = rear_.length();
+    rear_.eraseIf(pred);
+    erased += rearLength - rear_.length();
+
+    fixup();
+    return erased;
+  }
+
+  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
+    return front_.sizeOfExcludingThis(mallocSizeOf) +
+           rear_.sizeOfExcludingThis(mallocSizeOf);
+  }
+  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
+    return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
+  }
+};
+
+}  // namespace js
+
+#endif /* js_Fifo_h */
diff --git a/js/src/ds/FixedLengthVector.h b/js/src/ds/FixedLengthVector.h
new file mode 100644
index 0000000000..fab8fb08aa
--- /dev/null
+++ b/js/src/ds/FixedLengthVector.h
@@ -0,0 +1,112 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_FixedLengthVector_h
+#define ds_FixedLengthVector_h
+
+#include "mozilla/Assertions.h"             // MOZ_ASSERT
+#include "mozilla/Attributes.h"             // MOZ_MUST_USE
+#include "mozilla/OperatorNewExtensions.h"  // mozilla::KnownNotNull
+
+#include <stddef.h>  // size_t
+
+#include "js/Utility.h"    // js_free
+#include "vm/JSContext.h"  // JSContext
+
+namespace js {
+
+// A dynamically-allocated fixed-length vector with bounds checking assertions.
+template <typename T>
+class FixedLengthVector {
+  // The pointer to the storage.
+  T* data_ = nullptr;
+
+  // The size of the storage.
+  size_t length_ = 0;
+
+ public:
+  FixedLengthVector() = default;
+
+  FixedLengthVector(FixedLengthVector&) = delete;
+  FixedLengthVector(FixedLengthVector&&) = default;
+
+  ~FixedLengthVector() {
+    if (initialized()) {
+      js_free(data_);
+    }
+  }
+
+  size_t length() const { return length_; }
+
+  bool initialized() const { return !!data_; }
+
+  // Allocate the storage with the given size, wihtout calling constructor.
+  //
+  // If the allocation fails, this returns false and sets the
+  // pending exception on the given context.
+  MOZ_MUST_USE bool allocateUninitialized(JSContext* cx, size_t length) {
+    MOZ_ASSERT(!initialized());
+
+    length_ = length;
+    data_ = cx->pod_malloc<T>(length);
+    if (MOZ_UNLIKELY(!data_)) {
+      return false;
+    }
+
+    return true;
+  }
+
+  // Allocate the storage with the given size and call default constructor.
+  //
+  // If the allocation fails, this returns false and sets the
+  // pending exception on the given context.
+  MOZ_MUST_USE bool allocate(JSContext* cx, size_t length) {
+    if (!allocateUninitialized(cx, length)) {
+      return false;
+    }
+
+    for (size_t i = 0; i < length; i++) {
+      new (mozilla::KnownNotNull, &data_[i]) T();
+    }
+    return true;
+  }
+
+  T* begin() {
+    MOZ_ASSERT(initialized());
+    return data_;
+  }
+
+  const T* begin() const {
+    MOZ_ASSERT(initialized());
+    return data_;
+  }
+
+  T* end() {
+    MOZ_ASSERT(initialized());
+    return data_ + length_;
+  }
+
+  const T* end() const {
+    MOZ_ASSERT(initialized());
+    return data_ + length_;
+  }
+
+  T& operator[](size_t index) {
+    MOZ_ASSERT(initialized());
+    MOZ_ASSERT(index < length_);
+    return begin()[index];
+  }
+
+  const T& operator[](size_t index) const {
+    MOZ_ASSERT(initialized());
+    MOZ_ASSERT(index < length_);
+    return begin()[index];
+  }
+};
+
+}  // namespace js
+
+#endif  // ds_FixedLengthVector_h
diff --git a/js/src/ds/IdValuePair.h b/js/src/ds/IdValuePair.h
new file mode 100644
index 0000000000..acf6b8b5fa
--- /dev/null
+++ b/js/src/ds/IdValuePair.h
@@ -0,0 +1,35 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_IdValuePair_h
+#define ds_IdValuePair_h
+
+#include "gc/Tracer.h"
+#include "js/GCVector.h"
+#include "js/Id.h"
+#include "js/Value.h"
+
+namespace js {
+
+struct IdValuePair {
+  JS::Value value;
+  jsid id;
+
+  IdValuePair() : value(JS::UndefinedValue()), id(JSID_EMPTY) {}
+  explicit IdValuePair(jsid idArg) : value(JS::UndefinedValue()), id(idArg) {}
+  IdValuePair(jsid idArg, const Value& valueArg) : value(valueArg), id(idArg) {}
+
+  void trace(JSTracer* trc) {
+    TraceRoot(trc, &value, "IdValuePair::value");
+    TraceRoot(trc, &id, "IdValuePair::id");
+  }
+};
+
+using IdValueVector = JS::GCVector<IdValuePair, 8>;
+
+} /* namespace js */
+
+#endif /* ds_IdValuePair_h */
diff --git a/js/src/ds/InlineTable.h b/js/src/ds/InlineTable.h
new file mode 100644
index 0000000000..dc898b0c50
--- /dev/null
+++ b/js/src/ds/InlineTable.h
@@ -0,0 +1,645 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_InlineTable_h
+#define ds_InlineTable_h
+
+#include "mozilla/Maybe.h"
+
+#include <utility>
+
+#include "js/AllocPolicy.h"
+#include "js/HashTable.h"
+
+namespace js {
+
+namespace detail {
+
+// The InlineTable below needs an abstract way of testing keys for
+// tombstone values, and to set a key in an entry to a tombstone.
+// This is provided by the KeyPolicy generic type argument, which
+// has a default implementation for pointers provided below.
+
+// A default implementation of a KeyPolicy for some types (only pointer
+// types for now).
+//
+// The `KeyPolicy` type parameter informs an InlineTable of how to
+// check for tombstone values and to set tombstone values within
+// the domain of key (entry).
+//
+// A `KeyPolicy` for some key type `K` must provide two static methods:
+//   static bool isTombstone(const K& key);
+//   static void setToTombstone(K& key);
+template <typename K>
+class DefaultKeyPolicy;
+
+template <typename T>
+class DefaultKeyPolicy<T*> {
+  DefaultKeyPolicy() = delete;
+  DefaultKeyPolicy(const T*&) = delete;
+
+ public:
+  static bool isTombstone(T* const& ptr) { return ptr == nullptr; }
+  static void setToTombstone(T*& ptr) { ptr = nullptr; }
+};
+
+template <typename InlineEntry, typename Entry, typename Table,
+          typename HashPolicy, typename AllocPolicy, typename KeyPolicy,
+          size_t InlineEntries>
+class InlineTable : private AllocPolicy {
+ private:
+  using TablePtr = typename Table::Ptr;
+  using TableAddPtr = typename Table::AddPtr;
+  using TableRange = typename Table::Range;
+  using Lookup = typename HashPolicy::Lookup;
+
+  size_t inlNext_;
+  size_t inlCount_;
+  InlineEntry inl_[InlineEntries];
+  Table table_;
+
+#ifdef DEBUG
+  template <typename Key>
+  static bool keyNonZero(const Key& key) {
+    // Zero as tombstone means zero keys are invalid.
+    return !!key;
+  }
+#endif
+
+  InlineEntry* inlineStart() {
+    MOZ_ASSERT(!usingTable());
+    return inl_;
+  }
+
+  const InlineEntry* inlineStart() const {
+    MOZ_ASSERT(!usingTable());
+    return inl_;
+  }
+
+  InlineEntry* inlineEnd() {
+    MOZ_ASSERT(!usingTable());
+    return inl_ + inlNext_;
+  }
+
+  const InlineEntry* inlineEnd() const {
+    MOZ_ASSERT(!usingTable());
+    return inl_ + inlNext_;
+  }
+
+  bool usingTable() const { return inlNext_ > InlineEntries; }
+
+  MOZ_MUST_USE bool switchToTable() {
+    MOZ_ASSERT(inlNext_ == InlineEntries);
+
+    table_.clear();
+
+    InlineEntry* end = inlineEnd();
+    for (InlineEntry* it = inlineStart(); it != end; ++it) {
+      if (it->key && !it->moveTo(table_)) {
+        return false;
+      }
+    }
+
+    inlNext_ = InlineEntries + 1;
+    MOZ_ASSERT(table_.count() == inlCount_);
+    MOZ_ASSERT(usingTable());
+    return true;
+  }
+
+  MOZ_NEVER_INLINE
+  MOZ_MUST_USE bool switchAndAdd(const InlineEntry& entry) {
+    if (!switchToTable()) {
+      return false;
+    }
+
+    return entry.putNew(table_);
+  }
+
+ public:
+  static const size_t SizeOfInlineEntries = sizeof(InlineEntry) * InlineEntries;
+
+  explicit InlineTable(AllocPolicy a = AllocPolicy())
+      : AllocPolicy(std::move(a)), inlNext_(0), inlCount_(0), table_(a) {}
+
+  class Ptr {
+    friend class InlineTable;
+
+   protected:
+    MOZ_INIT_OUTSIDE_CTOR Entry entry_;
+    MOZ_INIT_OUTSIDE_CTOR TablePtr tablePtr_;
+    MOZ_INIT_OUTSIDE_CTOR InlineEntry* inlPtr_;
+    MOZ_INIT_OUTSIDE_CTOR bool isInlinePtr_;
+
+    explicit Ptr(TablePtr p)
+        : entry_(p.found() ? &*p : nullptr),
+          tablePtr_(p),
+          isInlinePtr_(false) {}
+
+    explicit Ptr(InlineEntry* inlineEntry)
+        : entry_(inlineEntry), inlPtr_(inlineEntry), isInlinePtr_(true) {}
+
+    void operator==(const Ptr& other);
+
+   public:
+    // Leaves Ptr uninitialized.
+    Ptr() {
+#ifdef DEBUG
+      inlPtr_ = (InlineEntry*)0xbad;
+      isInlinePtr_ = true;
+#endif
+    }
+
+    // Default copy constructor works for this structure.
+
+    bool found() const {
+      return isInlinePtr_ ? bool(inlPtr_) : tablePtr_.found();
+    }
+
+    explicit operator bool() const { return found(); }
+
+    bool operator==(const Ptr& other) const {
+      MOZ_ASSERT(found() && other.found());
+      if (isInlinePtr_ != other.isInlinePtr_) {
+        return false;
+      }
+      if (isInlinePtr_) {
+        return inlPtr_ == other.inlPtr_;
+      }
+      return tablePtr_ == other.tablePtr_;
+    }
+
+    bool operator!=(const Ptr& other) const { return !(*this == other); }
+
+    Entry& operator*() {
+      MOZ_ASSERT(found());
+      return entry_;
+    }
+
+    Entry* operator->() {
+      MOZ_ASSERT(found());
+      return &entry_;
+    }
+  };
+
+  class AddPtr {
+    friend class InlineTable;
+
+   protected:
+    MOZ_INIT_OUTSIDE_CTOR Entry entry_;
+    MOZ_INIT_OUTSIDE_CTOR TableAddPtr tableAddPtr_;
+    MOZ_INIT_OUTSIDE_CTOR InlineEntry* inlAddPtr_;
+    MOZ_INIT_OUTSIDE_CTOR bool isInlinePtr_;
+    // Indicates whether inlAddPtr is a found result or an add pointer.
+    MOZ_INIT_OUTSIDE_CTOR bool inlPtrFound_;
+
+    AddPtr(InlineEntry* ptr, bool found)
+        : entry_(ptr),
+          inlAddPtr_(ptr),
+          isInlinePtr_(true),
+          inlPtrFound_(found) {}
+
+    explicit AddPtr(const TableAddPtr& p)
+        : entry_(p.found() ? &*p : nullptr),
+          tableAddPtr_(p),
+          isInlinePtr_(false) {}
+
+   public:
+    AddPtr() = default;
+
+    bool found() const {
+      return isInlinePtr_ ? inlPtrFound_ : tableAddPtr_.found();
+    }
+
+    explicit operator bool() const { return found(); }
+
+    bool operator==(const AddPtr& other) const {
+      MOZ_ASSERT(found() && other.found());
+      if (isInlinePtr_ != other.isInlinePtr_) {
+        return false;
+      }
+      if (isInlinePtr_) {
+        return inlAddPtr_ == other.inlAddPtr_;
+      }
+      return tableAddPtr_ == other.tableAddPtr_;
+    }
+
+    bool operator!=(const AddPtr& other) const { return !(*this == other); }
+
+    Entry& operator*() {
+      MOZ_ASSERT(found());
+      return entry_;
+    }
+
+    Entry* operator->() {
+      MOZ_ASSERT(found());
+      return &entry_;
+    }
+  };
+
+  size_t count() const { return usingTable() ? table_.count() : inlCount_; }
+
+  bool empty() const { return usingTable() ? table_.empty() : !inlCount_; }
+
+  void clear() {
+    inlNext_ = 0;
+    inlCount_ = 0;
+  }
+
+  MOZ_ALWAYS_INLINE
+  Ptr lookup(const Lookup& l) {
+    MOZ_ASSERT(keyNonZero(l));
+
+    if (usingTable()) {
+      return Ptr(table_.lookup(l));
+    }
+
+    InlineEntry* end = inlineEnd();
+    for (InlineEntry* it = inlineStart(); it != end; ++it) {
+      if (it->key && HashPolicy::match(it->key, l)) {
+        return Ptr(it);
+      }
+    }
+
+    return Ptr(nullptr);
+  }
+
+  MOZ_ALWAYS_INLINE
+  AddPtr lookupForAdd(const Lookup& l) {
+    MOZ_ASSERT(keyNonZero(l));
+
+    if (usingTable()) {
+      return AddPtr(table_.lookupForAdd(l));
+    }
+
+    InlineEntry* end = inlineEnd();
+    for (InlineEntry* it = inlineStart(); it != end; ++it) {
+      if (it->key && HashPolicy::match(it->key, l)) {
+        return AddPtr(it, true);
+      }
+    }
+
+    // The add pointer that's returned here may indicate the limit entry of
+    // the linear space, in which case the |add| operation will initialize
+    // the table if necessary and add the entry there.
+    return AddPtr(inlineEnd(), false);
+  }
+
+  template <typename KeyInput, typename... Args>
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key,
+                                          Args&&... args) {
+    MOZ_ASSERT(!p);
+    MOZ_ASSERT(keyNonZero(key));
+
+    if (p.isInlinePtr_) {
+      InlineEntry* addPtr = p.inlAddPtr_;
+      MOZ_ASSERT(addPtr == inlineEnd());
+
+      // Switching to table mode before we add this pointer.
+      if (addPtr == inlineStart() + InlineEntries) {
+        if (!switchToTable()) {
+          return false;
+        }
+        return table_.putNew(std::forward<KeyInput>(key),
+                             std::forward<Args>(args)...);
+      }
+
+      MOZ_ASSERT(!p.found());
+      MOZ_ASSERT(uintptr_t(inlineEnd()) == uintptr_t(p.inlAddPtr_));
+
+      if (!this->checkSimulatedOOM()) {
+        return false;
+      }
+
+      addPtr->update(std::forward<KeyInput>(key), std::forward<Args>(args)...);
+      ++inlCount_;
+      ++inlNext_;
+      return true;
+    }
+
+    return table_.add(p.tableAddPtr_, std::forward<KeyInput>(key),
+                      std::forward<Args>(args)...);
+  }
+
+  void remove(Ptr& p) {
+    MOZ_ASSERT(p);
+    if (p.isInlinePtr_) {
+      MOZ_ASSERT(inlCount_ > 0);
+      MOZ_ASSERT(!KeyPolicy::isTombstone(p.inlPtr_->key));
+      KeyPolicy::setToTombstone(p.inlPtr_->key);
+      --inlCount_;
+      return;
+    }
+    MOZ_ASSERT(usingTable());
+    table_.remove(p.tablePtr_);
+  }
+
+  void remove(const Lookup& l) {
+    if (Ptr p = lookup(l)) {
+      remove(p);
+    }
+  }
+
+  class Range {
+    friend class InlineTable;
+
+   protected:
+    mozilla::Maybe<TableRange> tableRange_;  // `Nothing` if `isInline_==true`
+    InlineEntry* cur_;
+    InlineEntry* end_;
+    bool isInline_;
+
+    explicit Range(TableRange r)
+        : tableRange_(mozilla::Some(r)),
+          cur_(nullptr),
+          end_(nullptr),
+          isInline_(false) {
+      MOZ_ASSERT(!isInlineRange());
+    }
+
+    Range(const InlineEntry* begin, const InlineEntry* end)
+        : tableRange_(mozilla::Nothing()),
+          cur_(const_cast<InlineEntry*>(begin)),
+          end_(const_cast<InlineEntry*>(end)),
+          isInline_(true) {
+      advancePastNulls(cur_);
+      MOZ_ASSERT(isInlineRange());
+    }
+
+    bool assertInlineRangeInvariants() const {
+      MOZ_ASSERT(uintptr_t(cur_) <= uintptr_t(end_));
+      MOZ_ASSERT_IF(cur_ != end_, !KeyPolicy::isTombstone(cur_->key));
+      return true;
+    }
+
+    bool isInlineRange() const {
+      MOZ_ASSERT_IF(isInline_, assertInlineRangeInvariants());
+      return isInline_;
+    }
+
+    void advancePastNulls(InlineEntry* begin) {
+      InlineEntry* newCur = begin;
+      while (newCur < end_ && KeyPolicy::isTombstone(newCur->key)) {
+        ++newCur;
+      }
+      MOZ_ASSERT(uintptr_t(newCur) <= uintptr_t(end_));
+      cur_ = newCur;
+    }
+
+    void bumpCurPtr() {
+      MOZ_ASSERT(isInlineRange());
+      advancePastNulls(cur_ + 1);
+    }
+
+   public:
+    bool empty() const {
+      return isInlineRange() ? cur_ == end_ : tableRange_->empty();
+    }
+
+    Entry front() {
+      MOZ_ASSERT(!empty());
+      if (isInlineRange()) {
+        return Entry(cur_);
+      }
+      return Entry(&tableRange_->front());
+    }
+
+    void popFront() {
+      MOZ_ASSERT(!empty());
+      if (isInlineRange()) {
+        bumpCurPtr();
+      } else {
+        tableRange_->popFront();
+      }
+    }
+  };
+
+  Range all() const {
+    return usingTable() ? Range(table_.all())
+                        : Range(inlineStart(), inlineEnd());
+  }
+};
+
+}  // namespace detail
+
+// A map with InlineEntries number of entries kept inline in an array.
+//
+// The Key type must be zeroable as zeros are used as tombstone keys.
+// The Value type must have a default constructor.
+//
+// The API is very much like HashMap's.
+template <typename Key, typename Value, size_t InlineEntries,
+          typename HashPolicy = DefaultHasher<Key>,
+          typename AllocPolicy = TempAllocPolicy,
+          typename KeyPolicy = detail::DefaultKeyPolicy<Key>>
+class InlineMap {
+  using Map = HashMap<Key, Value, HashPolicy, AllocPolicy>;
+
+  struct InlineEntry {
+    Key key;
+    Value value;
+
+    template <typename KeyInput, typename ValueInput>
+    void update(KeyInput&& key, ValueInput&& value) {
+      this->key = std::forward<KeyInput>(key);
+      this->value = std::forward<ValueInput>(value);
+    }
+
+    MOZ_MUST_USE bool moveTo(Map& map) {
+      return map.putNew(std::move(key), std::move(value));
+    }
+  };
+
+  class Entry {
+    using MapEntry = typename Map::Entry;
+
+    MapEntry* mapEntry_;
+    InlineEntry* inlineEntry_;
+
+   public:
+    Entry() = default;
+
+    explicit Entry(MapEntry* mapEntry)
+        : mapEntry_(mapEntry), inlineEntry_(nullptr) {}
+
+    explicit Entry(InlineEntry* inlineEntry)
+        : mapEntry_(nullptr), inlineEntry_(inlineEntry) {}
+
+    const Key& key() const {
+      MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_);
+      if (mapEntry_) {
+        return mapEntry_->key();
+      }
+      return inlineEntry_->key;
+    }
+
+    Value& value() {
+      MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_);
+      if (mapEntry_) {
+        return mapEntry_->value();
+      }
+      return inlineEntry_->value;
+    }
+  };
+
+  using Impl = detail::InlineTable<InlineEntry, Entry, Map, HashPolicy,
+                                   AllocPolicy, KeyPolicy, InlineEntries>;
+
+  Impl impl_;
+
+ public:
+  using Table = Map;
+  using Ptr = typename Impl::Ptr;
+  using AddPtr = typename Impl::AddPtr;
+  using Range = typename Impl::Range;
+  using Lookup = typename HashPolicy::Lookup;
+
+  static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries;
+
+  explicit InlineMap(AllocPolicy a = AllocPolicy()) : impl_(std::move(a)) {}
+
+  size_t count() const { return impl_.count(); }
+
+  bool empty() const { return impl_.empty(); }
+
+  void clear() { impl_.clear(); }
+
+  Range all() const { return impl_.all(); }
+
+  MOZ_ALWAYS_INLINE
+  Ptr lookup(const Lookup& l) { return impl_.lookup(l); }
+
+  MOZ_ALWAYS_INLINE
+  bool has(const Lookup& l) const {
+    return const_cast<InlineMap*>(this)->lookup(l).found();
+  }
+
+  MOZ_ALWAYS_INLINE
+  AddPtr lookupForAdd(const Lookup& l) { return impl_.lookupForAdd(l); }
+
+  template <typename KeyInput, typename ValueInput>
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key,
+                                          ValueInput&& value) {
+    return impl_.add(p, std::forward<KeyInput>(key),
+                     std::forward<ValueInput>(value));
+  }
+
+  template <typename KeyInput, typename ValueInput>
+  MOZ_MUST_USE bool put(KeyInput&& key, ValueInput&& value) {
+    AddPtr p = lookupForAdd(key);
+    if (p) {
+      p->value() = std::forward<ValueInput>(value);
+      return true;
+    }
+    return add(p, std::forward<KeyInput>(key), std::forward<ValueInput>(value));
+  }
+
+  void remove(Ptr& p) { impl_.remove(p); }
+
+  void remove(const Lookup& l) { impl_.remove(l); }
+};
+
+// A set with InlineEntries number of entries kept inline in an array.
+//
+// The T type must be zeroable as zeros are used as tombstone keys.
+// The T type must have a default constructor.
+//
+// The API is very much like HashMap's.
+template <typename T, size_t InlineEntries,
+          typename HashPolicy = DefaultHasher<T>,
+          typename AllocPolicy = TempAllocPolicy,
+          typename KeyPolicy = detail::DefaultKeyPolicy<T>>
+class InlineSet {
+  using Set = HashSet<T, HashPolicy, AllocPolicy>;
+
+  struct InlineEntry {
+    T key;
+
+    template <typename TInput>
+    void update(TInput&& key) {
+      this->key = std::forward<TInput>(key);
+    }
+
+    MOZ_MUST_USE bool moveTo(Set& set) { return set.putNew(std::move(key)); }
+  };
+
+  class Entry {
+    using SetEntry = typename Set::Entry;
+
+    SetEntry* setEntry_;
+    InlineEntry* inlineEntry_;
+
+   public:
+    Entry() = default;
+
+    explicit Entry(const SetEntry* setEntry)
+        : setEntry_(const_cast<SetEntry*>(setEntry)), inlineEntry_(nullptr) {}
+
+    explicit Entry(InlineEntry* inlineEntry)
+        : setEntry_(nullptr), inlineEntry_(inlineEntry) {}
+
+    operator T() const {
+      MOZ_ASSERT(!!setEntry_ != !!inlineEntry_);
+      if (setEntry_) {
+        return *setEntry_;
+      }
+      return inlineEntry_->key;
+    }
+  };
+
+  using Impl = detail::InlineTable<InlineEntry, Entry, Set, HashPolicy,
+                                   AllocPolicy, KeyPolicy, InlineEntries>;
+
+  Impl impl_;
+
+ public:
+  using Table = Set;
+  using Ptr = typename Impl::Ptr;
+  using AddPtr = typename Impl::AddPtr;
+  using Range = typename Impl::Range;
+  using Lookup = typename HashPolicy::Lookup;
+
+  static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries;
+
+  explicit InlineSet(AllocPolicy a = AllocPolicy()) : impl_(std::move(a)) {}
+
+  size_t count() const { return impl_.count(); }
+
+  bool empty() const { return impl_.empty(); }
+
+  void clear() { impl_.clear(); }
+
+  Range all() const { return impl_.all(); }
+
+  MOZ_ALWAYS_INLINE
+  Ptr lookup(const Lookup& l) { return impl_.lookup(l); }
+
+  MOZ_ALWAYS_INLINE
+  bool has(const Lookup& l) const {
+    return const_cast<InlineSet*>(this)->lookup(l).found();
+  }
+
+  MOZ_ALWAYS_INLINE
+  AddPtr lookupForAdd(const Lookup& l) { return impl_.lookupForAdd(l); }
+
+  template <typename TInput>
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, TInput&& key) {
+    return impl_.add(p, std::forward<TInput>(key));
+  }
+
+  template <typename TInput>
+  MOZ_MUST_USE bool put(TInput&& key) {
+    AddPtr p = lookupForAdd(key);
+    return p ? true : add(p, std::forward<TInput>(key));
+  }
+
+  void remove(Ptr& p) { impl_.remove(p); }
+
+  void remove(const Lookup& l) { impl_.remove(l); }
+};
+
+}  // namespace js
+
+#endif  // ds_InlineTable_h
diff --git a/js/src/ds/LifoAlloc.cpp b/js/src/ds/LifoAlloc.cpp
new file mode 100644
index 0000000000..dc0b172b65
--- /dev/null
+++ b/js/src/ds/LifoAlloc.cpp
@@ -0,0 +1,430 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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/. */
+
+#include "ds/LifoAlloc.h"
+
+#include "mozilla/Likely.h"
+#include "mozilla/MathAlgorithms.h"
+
+#include <algorithm>
+
+#include "ds/MemoryProtectionExceptionHandler.h"
+
+#ifdef LIFO_CHUNK_PROTECT
+#  include "gc/Memory.h"
+#endif
+
+using namespace js;
+
+using mozilla::RoundUpPow2;
+using mozilla::tl::BitSize;
+
+namespace js {
+namespace detail {
+
+/* static */
+UniquePtr<BumpChunk> BumpChunk::newWithCapacity(size_t size) {
+  MOZ_DIAGNOSTIC_ASSERT(size >= sizeof(BumpChunk));
+  void* mem = js_malloc(size);
+  if (!mem) {
+    return nullptr;
+  }
+
+  UniquePtr<BumpChunk> result(new (mem) BumpChunk(size));
+
+  // We assume that the alignment of LIFO_ALLOC_ALIGN is less than that of the
+  // underlying memory allocator -- creating a new BumpChunk should always
+  // satisfy the LIFO_ALLOC_ALIGN alignment constraint.
+  MOZ_ASSERT(AlignPtr(result->begin()) == result->begin());
+  return result;
+}
+
+#ifdef LIFO_CHUNK_PROTECT
+
+static uint8_t* AlignPtrUp(uint8_t* ptr, uintptr_t align) {
+  MOZ_ASSERT(mozilla::IsPowerOfTwo(align));
+  uintptr_t uptr = uintptr_t(ptr);
+  uintptr_t diff = uptr & (align - 1);
+  diff = (align - diff) & (align - 1);
+  uptr = uptr + diff;
+  return (uint8_t*)uptr;
+}
+
+static uint8_t* AlignPtrDown(uint8_t* ptr, uintptr_t align) {
+  MOZ_ASSERT(mozilla::IsPowerOfTwo(align));
+  uintptr_t uptr = uintptr_t(ptr);
+  uptr = uptr & ~(align - 1);
+  return (uint8_t*)uptr;
+}
+
+void BumpChunk::setReadOnly() {
+  uintptr_t pageSize = gc::SystemPageSize();
+  // The allocated chunks might not be aligned on page boundaries. This code
+  // is used to ensure that we are changing the memory protection of pointers
+  // which are within the range of the BumpChunk, or that the range formed by
+  // [b .. e] is empty.
+  uint8_t* b = base();
+  uint8_t* e = capacity_;
+  b = AlignPtrUp(b, pageSize);
+  e = AlignPtrDown(e, pageSize);
+  if (e <= b) {
+    return;
+  }
+  js::MemoryProtectionExceptionHandler::addRegion(base(), capacity_ - base());
+  gc::MakePagesReadOnly(b, e - b);
+}
+
+void BumpChunk::setReadWrite() {
+  uintptr_t pageSize = gc::SystemPageSize();
+  // The allocated chunks might not be aligned on page boundaries. This code
+  // is used to ensure that we are changing the memory protection of pointers
+  // which are within the range of the BumpChunk, or that the range formed by
+  // [b .. e] is empty.
+  uint8_t* b = base();
+  uint8_t* e = capacity_;
+  b = AlignPtrUp(b, pageSize);
+  e = AlignPtrDown(e, pageSize);
+  if (e <= b) {
+    return;
+  }
+  gc::UnprotectPages(b, e - b);
+  js::MemoryProtectionExceptionHandler::removeRegion(base());
+}
+
+#endif
+
+}  // namespace detail
+}  // namespace js
+
+void LifoAlloc::reset(size_t defaultChunkSize) {
+  MOZ_ASSERT(mozilla::IsPowerOfTwo(defaultChunkSize));
+
+  while (!chunks_.empty()) {
+    chunks_.popFirst();
+  }
+  while (!oversize_.empty()) {
+    oversize_.popFirst();
+  }
+  while (!unused_.empty()) {
+    unused_.popFirst();
+  }
+  defaultChunkSize_ = defaultChunkSize;
+  oversizeThreshold_ = defaultChunkSize;
+  markCount = 0;
+  curSize_ = 0;
+  smallAllocsSize_ = 0;
+}
+
+void LifoAlloc::freeAll() {
+  // When free-ing all chunks, we can no longer determine which chunks were
+  // transferred and which were not, so simply clear the heuristic to zero
+  // right away.
+  smallAllocsSize_ = 0;
+
+  while (!chunks_.empty()) {
+    UniqueBumpChunk bc = chunks_.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+  while (!oversize_.empty()) {
+    UniqueBumpChunk bc = oversize_.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+  while (!unused_.empty()) {
+    UniqueBumpChunk bc = unused_.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+
+  // Nb: maintaining curSize_ correctly isn't easy.  Fortunately, this is an
+  // excellent sanity check.
+  MOZ_ASSERT(curSize_ == 0);
+}
+
+// Round at the same page granularity used by malloc.
+static size_t MallocGoodSize(size_t aSize) {
+#if defined(MOZ_MEMORY)
+  return malloc_good_size(aSize);
+#else
+  return aSize;
+#endif
+}
+
+// Heuristic to choose the size of the next BumpChunk for small allocations.
+// `start` is the size of the first chunk. `used` is the total size of all
+// BumpChunks in this LifoAlloc so far.
+static size_t NextSize(size_t start, size_t used) {
+  // Double the size, up to 1 MB.
+  const size_t mb = 1 * 1024 * 1024;
+  if (used < mb) {
+    return std::max(start, used);
+  }
+
+  // After 1 MB, grow more gradually, to waste less memory.
+  // The sequence (in megabytes) begins:
+  // 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, ...
+  return RoundUp(used / 8, mb);
+}
+
+LifoAlloc::UniqueBumpChunk LifoAlloc::newChunkWithCapacity(size_t n,
+                                                           bool oversize) {
+  MOZ_ASSERT(fallibleScope_,
+             "[OOM] Cannot allocate a new chunk in an infallible scope.");
+
+  // Compute the size which should be requested in order to be able to fit |n|
+  // bytes in a newly allocated chunk, or default to |defaultChunkSize_|.
+
+  size_t minSize;
+  if (MOZ_UNLIKELY(!detail::BumpChunk::allocSizeWithRedZone(n, &minSize) ||
+                   (minSize & (size_t(1) << (BitSize<size_t>::value - 1))))) {
+    return nullptr;
+  }
+
+  // Note: When computing chunkSize growth, we only are interested in chunks
+  // used for small allocations. This excludes unused chunks, oversized chunks,
+  // and chunks transferred in from another LifoAlloc.
+  MOZ_ASSERT(curSize_ >= smallAllocsSize_);
+  const size_t chunkSize = (oversize || minSize > defaultChunkSize_)
+                               ? MallocGoodSize(minSize)
+                               : NextSize(defaultChunkSize_, smallAllocsSize_);
+
+  // Create a new BumpChunk, and allocate space for it.
+  UniqueBumpChunk result = detail::BumpChunk::newWithCapacity(chunkSize);
+  if (!result) {
+    return nullptr;
+  }
+  MOZ_ASSERT(result->computedSizeOfIncludingThis() == chunkSize);
+  return result;
+}
+
+LifoAlloc::UniqueBumpChunk LifoAlloc::getOrCreateChunk(size_t n) {
+  // Look for existing unused BumpChunks to satisfy the request, and pick the
+  // first one which is large enough, and move it into the list of used
+  // chunks.
+  if (!unused_.empty()) {
+    if (unused_.begin()->canAlloc(n)) {
+      return unused_.popFirst();
+    }
+
+    BumpChunkList::Iterator e(unused_.end());
+    for (BumpChunkList::Iterator i(unused_.begin()); i->next() != e.get();
+         ++i) {
+      detail::BumpChunk* elem = i->next();
+      MOZ_ASSERT(elem->empty());
+      if (elem->canAlloc(n)) {
+        BumpChunkList temp = unused_.splitAfter(i.get());
+        UniqueBumpChunk newChunk = temp.popFirst();
+        unused_.appendAll(std::move(temp));
+        return newChunk;
+      }
+    }
+  }
+
+  // Allocate a new BumpChunk with enough space for the next allocation.
+  UniqueBumpChunk newChunk = newChunkWithCapacity(n, false);
+  if (!newChunk) {
+    return newChunk;
+  }
+  incrementCurSize(newChunk->computedSizeOfIncludingThis());
+  return newChunk;
+}
+
+void* LifoAlloc::allocImplColdPath(size_t n) {
+  void* result;
+  UniqueBumpChunk newChunk = getOrCreateChunk(n);
+  if (!newChunk) {
+    return nullptr;
+  }
+
+  // This new chunk is about to be used for small allocations.
+  smallAllocsSize_ += newChunk->computedSizeOfIncludingThis();
+
+  // Since we just created a large enough chunk, this can't fail.
+  chunks_.append(std::move(newChunk));
+  result = chunks_.last()->tryAlloc(n);
+  MOZ_ASSERT(result);
+  return result;
+}
+
+void* LifoAlloc::allocImplOversize(size_t n) {
+  void* result;
+  UniqueBumpChunk newChunk = newChunkWithCapacity(n, true);
+  if (!newChunk) {
+    return nullptr;
+  }
+  incrementCurSize(newChunk->computedSizeOfIncludingThis());
+
+  // Since we just created a large enough chunk, this can't fail.
+  oversize_.append(std::move(newChunk));
+  result = oversize_.last()->tryAlloc(n);
+  MOZ_ASSERT(result);
+  return result;
+}
+
+bool LifoAlloc::ensureUnusedApproximateColdPath(size_t n, size_t total) {
+  for (detail::BumpChunk& bc : unused_) {
+    total += bc.unused();
+    if (total >= n) {
+      return true;
+    }
+  }
+
+  UniqueBumpChunk newChunk = newChunkWithCapacity(n, false);
+  if (!newChunk) {
+    return false;
+  }
+  incrementCurSize(newChunk->computedSizeOfIncludingThis());
+  unused_.pushFront(std::move(newChunk));
+  return true;
+}
+
+LifoAlloc::Mark LifoAlloc::mark() {
+  markCount++;
+  Mark res;
+  if (!chunks_.empty()) {
+    res.chunk = chunks_.last()->mark();
+  }
+  if (!oversize_.empty()) {
+    res.oversize = oversize_.last()->mark();
+  }
+  return res;
+}
+
+void LifoAlloc::release(Mark mark) {
+  markCount--;
+#ifdef DEBUG
+  auto assertIsContained = [](const detail::BumpChunk::Mark& m,
+                              BumpChunkList& list) {
+    if (m.markedChunk()) {
+      bool contained = false;
+      for (const detail::BumpChunk& chunk : list) {
+        if (&chunk == m.markedChunk() && chunk.contains(m)) {
+          contained = true;
+          break;
+        }
+      }
+      MOZ_ASSERT(contained);
+    }
+  };
+  assertIsContained(mark.chunk, chunks_);
+  assertIsContained(mark.oversize, oversize_);
+#endif
+
+  BumpChunkList released;
+  auto cutAtMark = [&released](const detail::BumpChunk::Mark& m,
+                               BumpChunkList& list) {
+    // Move the blocks which are after the mark to the set released chunks.
+    if (!m.markedChunk()) {
+      released = std::move(list);
+    } else {
+      released = list.splitAfter(m.markedChunk());
+    }
+
+    // Release everything which follows the mark in the last chunk.
+    if (!list.empty()) {
+      list.last()->release(m);
+    }
+  };
+
+  // Release the content of all the blocks which are after the marks, and keep
+  // blocks as unused.
+  cutAtMark(mark.chunk, chunks_);
+  for (detail::BumpChunk& bc : released) {
+    bc.release();
+
+    // Chunks moved from (after a mark) in chunks_ to unused_ are no longer
+    // considered small allocations.
+    smallAllocsSize_ -= bc.computedSizeOfIncludingThis();
+  }
+  unused_.appendAll(std::move(released));
+
+  // Free the content of all the blocks which are after the marks.
+  cutAtMark(mark.oversize, oversize_);
+  while (!released.empty()) {
+    UniqueBumpChunk bc = released.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+}
+
+void LifoAlloc::steal(LifoAlloc* other) {
+  MOZ_ASSERT(!other->markCount);
+  MOZ_DIAGNOSTIC_ASSERT(unused_.empty());
+  MOZ_DIAGNOSTIC_ASSERT(chunks_.empty());
+  MOZ_DIAGNOSTIC_ASSERT(oversize_.empty());
+
+  // Copy everything from |other| to |this| except for |peakSize_|, which
+  // requires some care.
+  chunks_ = std::move(other->chunks_);
+  oversize_ = std::move(other->oversize_);
+  unused_ = std::move(other->unused_);
+  markCount = other->markCount;
+  defaultChunkSize_ = other->defaultChunkSize_;
+  oversizeThreshold_ = other->oversizeThreshold_;
+  curSize_ = other->curSize_;
+  peakSize_ = std::max(peakSize_, other->peakSize_);
+  smallAllocsSize_ = other->smallAllocsSize_;
+#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
+  fallibleScope_ = other->fallibleScope_;
+#endif
+
+  other->reset(defaultChunkSize_);
+}
+
+void LifoAlloc::transferFrom(LifoAlloc* other) {
+  MOZ_ASSERT(!markCount);
+  MOZ_ASSERT(!other->markCount);
+
+  // Transferred chunks are not counted as part of |smallAllocsSize| as this
+  // could introduce bias in the |NextSize| heuristics, leading to
+  // over-allocations in *this* LifoAlloc. As well, to avoid interference with
+  // small allocations made with |this|, the last chunk of the |chunks_| list
+  // should remain the last chunk. Therefore, the transferred chunks are
+  // prepended to the |chunks_| list.
+  incrementCurSize(other->curSize_);
+
+  appendUnused(std::move(other->unused_));
+  chunks_.prependAll(std::move(other->chunks_));
+  oversize_.prependAll(std::move(other->oversize_));
+  other->curSize_ = 0;
+  other->smallAllocsSize_ = 0;
+}
+
+void LifoAlloc::transferUnusedFrom(LifoAlloc* other) {
+  MOZ_ASSERT(!markCount);
+
+  size_t size = 0;
+  for (detail::BumpChunk& bc : other->unused_) {
+    size += bc.computedSizeOfIncludingThis();
+  }
+
+  appendUnused(std::move(other->unused_));
+  incrementCurSize(size);
+  other->decrementCurSize(size);
+}
+
+#ifdef LIFO_CHUNK_PROTECT
+void LifoAlloc::setReadOnly() {
+  for (detail::BumpChunk& bc : chunks_) {
+    bc.setReadOnly();
+  }
+  for (detail::BumpChunk& bc : oversize_) {
+    bc.setReadOnly();
+  }
+  for (detail::BumpChunk& bc : unused_) {
+    bc.setReadOnly();
+  }
+}
+
+void LifoAlloc::setReadWrite() {
+  for (detail::BumpChunk& bc : chunks_) {
+    bc.setReadWrite();
+  }
+  for (detail::BumpChunk& bc : oversize_) {
+    bc.setReadWrite();
+  }
+  for (detail::BumpChunk& bc : unused_) {
+    bc.setReadWrite();
+  }
+}
+#endif
diff --git a/js/src/ds/LifoAlloc.h b/js/src/ds/LifoAlloc.h
new file mode 100644
index 0000000000..9fe77ac748
--- /dev/null
+++ b/js/src/ds/LifoAlloc.h
@@ -0,0 +1,1031 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_LifoAlloc_h
+#define ds_LifoAlloc_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/MemoryChecking.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/PodOperations.h"
+#include "mozilla/TemplateLib.h"
+
+#include <algorithm>
+#include <new>
+#include <stddef.h>  // size_t
+#include <type_traits>
+#include <utility>
+
+// This data structure supports stacky LIFO allocation (mark/release and
+// LifoAllocScope). It does not maintain one contiguous segment; instead, it
+// maintains a bunch of linked memory segments. In order to prevent malloc/free
+// thrashing, unused segments are deallocated when garbage collection occurs.
+
+#include "js/UniquePtr.h"
+#include "util/Memory.h"
+#include "util/Poison.h"
+
+namespace js {
+
+namespace detail {
+
+template <typename T, typename D>
+class SingleLinkedList;
+
+template <typename T, typename D = JS::DeletePolicy<T>>
+class SingleLinkedListElement {
+  friend class SingleLinkedList<T, D>;
+  js::UniquePtr<T, D> next_;
+
+ public:
+  SingleLinkedListElement() : next_(nullptr) {}
+  ~SingleLinkedListElement() { MOZ_ASSERT(!next_); }
+
+  T* next() const { return next_.get(); }
+};
+
+// Single linked list which is using UniquePtr to hold the next pointers.
+// UniquePtr are used to ensure that none of the elements are used
+// silmutaneously in 2 different list.
+template <typename T, typename D = JS::DeletePolicy<T>>
+class SingleLinkedList {
+ private:
+  // First element of the list which owns the next element, and ensure that
+  // that this list is the only owner of the element.
+  UniquePtr<T, D> head_;
+
+  // Weak pointer to the last element of the list.
+  T* last_;
+
+  void assertInvariants() {
+    MOZ_ASSERT(bool(head_) == bool(last_));
+    MOZ_ASSERT_IF(last_, !last_->next_);
+  }
+
+ public:
+  SingleLinkedList() : head_(nullptr), last_(nullptr) { assertInvariants(); }
+
+  SingleLinkedList(SingleLinkedList&& other)
+      : head_(std::move(other.head_)), last_(other.last_) {
+    other.last_ = nullptr;
+    assertInvariants();
+    other.assertInvariants();
+  }
+
+  ~SingleLinkedList() {
+    MOZ_ASSERT(!head_);
+    MOZ_ASSERT(!last_);
+  }
+
+  // Move the elements of the |other| list in the current one, and implicitly
+  // remove all the elements of the current list.
+  SingleLinkedList& operator=(SingleLinkedList&& other) {
+    head_ = std::move(other.head_);
+    last_ = other.last_;
+    other.last_ = nullptr;
+    assertInvariants();
+    other.assertInvariants();
+    return *this;
+  }
+
+  bool empty() const { return !last_; }
+
+  // Iterates over the elements of the list, this is used to avoid raw
+  // manipulation of pointers as much as possible.
+  class Iterator {
+    T* current_;
+
+   public:
+    explicit Iterator(T* current) : current_(current) {}
+
+    T& operator*() const { return *current_; }
+    T* operator->() const { return current_; }
+    T* get() const { return current_; }
+
+    const Iterator& operator++() {
+      current_ = current_->next();
+      return *this;
+    }
+
+    bool operator!=(const Iterator& other) const {
+      return current_ != other.current_;
+    }
+    bool operator==(const Iterator& other) const {
+      return current_ == other.current_;
+    }
+  };
+
+  Iterator begin() const { return Iterator(head_.get()); }
+  Iterator end() const { return Iterator(nullptr); }
+  Iterator last() const { return Iterator(last_); }
+
+  // Split the list in 2 single linked lists after the element given as
+  // argument.  The front of the list remains in the current list, while the
+  // back goes in the newly create linked list.
+  //
+  // This is used for example to extract one element from a list. (see
+  // LifoAlloc::getOrCreateChunk)
+  SingleLinkedList splitAfter(T* newLast) {
+    MOZ_ASSERT(newLast);
+    SingleLinkedList result;
+    if (newLast->next_) {
+      result.head_ = std::move(newLast->next_);
+      result.last_ = last_;
+      last_ = newLast;
+    }
+    assertInvariants();
+    result.assertInvariants();
+    return result;
+  }
+
+  void pushFront(UniquePtr<T, D>&& elem) {
+    if (!last_) {
+      last_ = elem.get();
+    }
+    elem->next_ = std::move(head_);
+    head_ = std::move(elem);
+    assertInvariants();
+  }
+
+  void append(UniquePtr<T, D>&& elem) {
+    if (last_) {
+      last_->next_ = std::move(elem);
+      last_ = last_->next_.get();
+    } else {
+      head_ = std::move(elem);
+      last_ = head_.get();
+    }
+    assertInvariants();
+  }
+  void appendAll(SingleLinkedList&& list) {
+    if (list.empty()) {
+      return;
+    }
+    if (last_) {
+      last_->next_ = std::move(list.head_);
+    } else {
+      head_ = std::move(list.head_);
+    }
+    last_ = list.last_;
+    list.last_ = nullptr;
+    assertInvariants();
+    list.assertInvariants();
+  }
+  void steal(SingleLinkedList&& list) {
+    head_ = std::move(list.head_);
+    last_ = list.last_;
+    list.last_ = nullptr;
+    assertInvariants();
+    list.assertInvariants();
+  }
+  void prependAll(SingleLinkedList&& list) {
+    list.appendAll(std::move(*this));
+    steal(std::move(list));
+  }
+  UniquePtr<T, D> popFirst() {
+    MOZ_ASSERT(head_);
+    UniquePtr<T, D> result = std::move(head_);
+    head_ = std::move(result->next_);
+    if (!head_) {
+      last_ = nullptr;
+    }
+    assertInvariants();
+    return result;
+  }
+};
+
+static const size_t LIFO_ALLOC_ALIGN = 8;
+
+MOZ_ALWAYS_INLINE
+uint8_t* AlignPtr(uint8_t* orig) {
+  static_assert(mozilla::IsPowerOfTwo(LIFO_ALLOC_ALIGN),
+                "LIFO_ALLOC_ALIGN must be a power of two");
+
+  uint8_t* result = (uint8_t*)AlignBytes(uintptr_t(orig), LIFO_ALLOC_ALIGN);
+  MOZ_ASSERT(uintptr_t(result) % LIFO_ALLOC_ALIGN == 0);
+  return result;
+}
+
+// A Chunk represent a single memory allocation made with the system
+// allocator. As the owner of the memory, it is responsible for the allocation
+// and the deallocation.
+//
+// This structure is only move-able, but not copyable.
+class BumpChunk : public SingleLinkedListElement<BumpChunk> {
+ private:
+  // Pointer to the last byte allocated in this chunk.
+  uint8_t* bump_;
+  // Pointer to the first byte after this chunk.
+  uint8_t* const capacity_;
+
+#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
+  // Magic number used to check against poisoned values.
+  const uintptr_t magic_ : 24;
+  static constexpr uintptr_t magicNumber = uintptr_t(0x4c6966);
+#endif
+
+#if defined(DEBUG)
+#  define LIFO_CHUNK_PROTECT 1
+#endif
+
+  // Poison the memory with memset, in order to catch errors due to
+  // use-after-free, with JS_LIFO_UNDEFINED_PATTERN pattern, or to catch
+  // use-before-init with JS_LIFO_UNINITIALIZED_PATTERN.
+#if defined(DEBUG)
+#  define LIFO_HAVE_MEM_CHECKS 1
+#  define LIFO_MAKE_MEM_NOACCESS(addr, size)       \
+    do {                                           \
+      uint8_t* base = (addr);                      \
+      size_t sz = (size);                          \
+      MOZ_MAKE_MEM_UNDEFINED(base, sz);            \
+      memset(base, JS_LIFO_UNDEFINED_PATTERN, sz); \
+      MOZ_MAKE_MEM_NOACCESS(base, sz);             \
+    } while (0)
+
+#  define LIFO_MAKE_MEM_UNDEFINED(addr, size)          \
+    do {                                               \
+      uint8_t* base = (addr);                          \
+      size_t sz = (size);                              \
+      MOZ_MAKE_MEM_UNDEFINED(base, sz);                \
+      memset(base, JS_LIFO_UNINITIALIZED_PATTERN, sz); \
+      MOZ_MAKE_MEM_UNDEFINED(base, sz);                \
+    } while (0)
+
+#elif defined(MOZ_HAVE_MEM_CHECKS)
+#  define LIFO_HAVE_MEM_CHECKS 1
+#  define LIFO_MAKE_MEM_NOACCESS(addr, size) \
+    MOZ_MAKE_MEM_NOACCESS((addr), (size))
+#  define LIFO_MAKE_MEM_UNDEFINED(addr, size) \
+    MOZ_MAKE_MEM_UNDEFINED((addr), (size))
+#endif
+
+#ifdef LIFO_HAVE_MEM_CHECKS
+  // Red zone reserved after each allocation.
+  static constexpr size_t RedZoneSize = 16;
+#else
+  static constexpr size_t RedZoneSize = 0;
+#endif
+
+  void assertInvariants() {
+    MOZ_DIAGNOSTIC_ASSERT(magic_ == magicNumber);
+    MOZ_ASSERT(begin() <= end());
+    MOZ_ASSERT(end() <= capacity_);
+  }
+
+  BumpChunk& operator=(const BumpChunk&) = delete;
+  BumpChunk(const BumpChunk&) = delete;
+
+  explicit BumpChunk(uintptr_t capacity)
+      : bump_(begin()),
+        capacity_(base() + capacity)
+#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
+        ,
+        magic_(magicNumber)
+#endif
+  {
+    assertInvariants();
+#if defined(LIFO_HAVE_MEM_CHECKS)
+    // The memory is freshly allocated and marked as undefined by the
+    // allocator of the BumpChunk. Instead, we mark this memory as
+    // no-access, as it has not been allocated within the BumpChunk.
+    LIFO_MAKE_MEM_NOACCESS(bump_, capacity_ - bump_);
+#endif
+  }
+
+  // Cast |this| into a uint8_t* pointer.
+  //
+  // Warning: Are you sure you do not want to use begin() instead?
+  const uint8_t* base() const { return reinterpret_cast<const uint8_t*>(this); }
+  uint8_t* base() { return reinterpret_cast<uint8_t*>(this); }
+
+  // Update the bump pointer to any value contained in this chunk, which is
+  // above the private fields of this chunk.
+  //
+  // The memory is poisoned and flagged as no-access when the bump pointer is
+  // moving backward, such as when memory is released, or when a Mark is used
+  // to unwind previous allocations.
+  //
+  // The memory is flagged as undefined when the bump pointer is moving
+  // forward.
+  void setBump(uint8_t* newBump) {
+    assertInvariants();
+    MOZ_ASSERT(begin() <= newBump);
+    MOZ_ASSERT(newBump <= capacity_);
+#if defined(LIFO_HAVE_MEM_CHECKS)
+    // Poison/Unpoison memory that we just free'd/allocated.
+    if (bump_ > newBump) {
+      LIFO_MAKE_MEM_NOACCESS(newBump, bump_ - newBump);
+    } else if (newBump > bump_) {
+      MOZ_ASSERT(newBump - RedZoneSize >= bump_);
+      LIFO_MAKE_MEM_UNDEFINED(bump_, newBump - RedZoneSize - bump_);
+      // The area [newBump - RedZoneSize .. newBump[ is already flagged as
+      // no-access either with the previous if-branch or with the
+      // BumpChunk constructor. No need to mark it twice.
+    }
+#endif
+    bump_ = newBump;
+  }
+
+ public:
+  ~BumpChunk() { release(); }
+
+  // Returns true if this chunk contains no allocated content.
+  bool empty() const { return end() == begin(); }
+
+  // Returns the size in bytes of the number of allocated space. This includes
+  // the size consumed by the alignment of the allocations.
+  size_t used() const { return end() - begin(); }
+
+  // These are used for manipulating a chunk as if it was a vector of bytes,
+  // and used for iterating over the content of the buffer (see
+  // LifoAlloc::Enum)
+  inline const uint8_t* begin() const;
+  inline uint8_t* begin();
+  uint8_t* end() const { return bump_; }
+
+  // This function is the only way to allocate and construct a chunk. It
+  // returns a UniquePtr to the newly allocated chunk.  The size given as
+  // argument includes the space needed for the header of the chunk.
+  static UniquePtr<BumpChunk> newWithCapacity(size_t size);
+
+  // Report allocation.
+  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
+    return mallocSizeOf(this);
+  }
+
+  // Report allocation size.
+  size_t computedSizeOfIncludingThis() const { return capacity_ - base(); }
+
+  // Opaque type used to carry a pointer to the current location of the bump_
+  // pointer, within a BumpChunk.
+  class Mark {
+    // Chunk which owns the pointer.
+    BumpChunk* chunk_;
+    // Recorded of the bump_ pointer of the BumpChunk.
+    uint8_t* bump_;
+
+    friend class BumpChunk;
+    Mark(BumpChunk* chunk, uint8_t* bump) : chunk_(chunk), bump_(bump) {}
+
+   public:
+    Mark() : chunk_(nullptr), bump_(nullptr) {}
+
+    BumpChunk* markedChunk() const { return chunk_; }
+  };
+
+  // Return a mark to be able to unwind future allocations with the release
+  // function. (see LifoAllocScope)
+  Mark mark() { return Mark(this, end()); }
+
+  // Check if a pointer is part of the allocated data of this chunk.
+  bool contains(void* ptr) const {
+    // Note: We cannot check "ptr < end()" because the mark have a 0-size
+    // length.
+    return begin() <= ptr && ptr <= end();
+  }
+
+  // Check if a mark is part of the allocated data of this chunk.
+  bool contains(Mark m) const {
+    MOZ_ASSERT(m.chunk_ == this);
+    return contains(m.bump_);
+  }
+
+  // Release the memory allocated in this chunk. This function does not call
+  // any of the destructors.
+  void release() { setBump(begin()); }
+
+  // Release the memory allocated in this chunk since the corresponding mark
+  // got created. This function does not call any of the destructors.
+  void release(Mark m) {
+    MOZ_RELEASE_ASSERT(contains(m));
+    setBump(m.bump_);
+  }
+
+  // Given an amount, compute the total size of a chunk for it: reserved
+  // space before |begin()|, space for |amount| bytes, and red-zone space
+  // after those bytes that will ultimately end at |capacity_|.
+  static inline MOZ_MUST_USE bool allocSizeWithRedZone(size_t amount,
+                                                       size_t* size);
+
+  // Given a bump chunk pointer, find the next base/end pointers. This is
+  // useful for having consistent allocations, and iterating over known size
+  // allocations.
+  static uint8_t* nextAllocBase(uint8_t* e) { return detail::AlignPtr(e); }
+  static uint8_t* nextAllocEnd(uint8_t* b, size_t n) {
+    return b + n + RedZoneSize;
+  }
+
+  // Returns true, if the unused space is large enough for an allocation of
+  // |n| bytes.
+  bool canAlloc(size_t n) const {
+    uint8_t* newBump = nextAllocEnd(nextAllocBase(end()), n);
+    // bump_ <= newBump, is necessary to catch overflow.
+    return bump_ <= newBump && newBump <= capacity_;
+  }
+
+  // Space remaining in the current chunk.
+  size_t unused() const {
+    uint8_t* aligned = nextAllocBase(end());
+    if (aligned < capacity_) {
+      return capacity_ - aligned;
+    }
+    return 0;
+  }
+
+  // Try to perform an allocation of size |n|, returns nullptr if not possible.
+  MOZ_ALWAYS_INLINE
+  void* tryAlloc(size_t n) {
+    uint8_t* aligned = nextAllocBase(end());
+    uint8_t* newBump = nextAllocEnd(aligned, n);
+
+    if (newBump > capacity_) {
+      return nullptr;
+    }
+
+    // Check for overflow.
+    if (MOZ_UNLIKELY(newBump < bump_)) {
+      return nullptr;
+    }
+
+    MOZ_ASSERT(canAlloc(n));  // Ensure consistency between "can" and "try".
+    setBump(newBump);
+    return aligned;
+  }
+
+#ifdef LIFO_CHUNK_PROTECT
+  void setReadOnly();
+  void setReadWrite();
+#else
+  void setReadOnly() const {}
+  void setReadWrite() const {}
+#endif
+};
+
+// Space reserved for the BumpChunk internal data, and the alignment of the
+// first allocation content. This can be used to ensure there is enough space
+// for the next allocation (see LifoAlloc::newChunkWithCapacity).
+static constexpr size_t BumpChunkReservedSpace =
+    AlignBytes(sizeof(BumpChunk), LIFO_ALLOC_ALIGN);
+
+/* static */ inline MOZ_MUST_USE bool BumpChunk::allocSizeWithRedZone(
+    size_t amount, size_t* size) {
+  constexpr size_t SpaceBefore = BumpChunkReservedSpace;
+  static_assert((SpaceBefore % LIFO_ALLOC_ALIGN) == 0,
+                "reserved space presumed already aligned");
+
+  constexpr size_t SpaceAfter = RedZoneSize;  // may be zero
+
+  constexpr size_t SpaceBeforeAndAfter = SpaceBefore + SpaceAfter;
+  static_assert(SpaceBeforeAndAfter >= SpaceBefore,
+                "intermediate addition must not overflow");
+
+  *size = SpaceBeforeAndAfter + amount;
+  return MOZ_LIKELY(*size >= SpaceBeforeAndAfter);
+}
+
+inline const uint8_t* BumpChunk::begin() const {
+  return base() + BumpChunkReservedSpace;
+}
+
+inline uint8_t* BumpChunk::begin() { return base() + BumpChunkReservedSpace; }
+
+}  // namespace detail
+
+// LIFO bump allocator: used for phase-oriented and fast LIFO allocations.
+//
+// Note: We leave BumpChunks latent in the set of unused chunks after they've
+// been released to avoid thrashing before a GC.
+class LifoAlloc {
+  using UniqueBumpChunk = js::UniquePtr<detail::BumpChunk>;
+  using BumpChunkList = detail::SingleLinkedList<detail::BumpChunk>;
+
+  // List of chunks containing allocated data of size smaller than the default
+  // chunk size. In the common case, the last chunk of this list is always
+  // used to perform the allocations. When the allocation cannot be performed,
+  // we move a Chunk from the unused set to the list of used chunks.
+  BumpChunkList chunks_;
+
+  // List of chunks containing allocated data where each allocation is larger
+  // than the oversize threshold. Each chunk contains exactly one allocation.
+  // This reduces wasted space in the chunk list.
+  //
+  // Oversize chunks are allocated on demand and freed as soon as they are
+  // released, instead of being pushed to the unused list.
+  BumpChunkList oversize_;
+
+  // Set of unused chunks, which can be reused for future allocations.
+  BumpChunkList unused_;
+
+  size_t markCount;
+  size_t defaultChunkSize_;
+  size_t oversizeThreshold_;
+
+  // Size of all chunks in chunks_, oversize_, unused_ lists.
+  size_t curSize_;
+  size_t peakSize_;
+
+  // Size of all chunks containing small bump allocations. This heuristic is
+  // used to compute growth rate while ignoring chunks such as oversized,
+  // now-unused, or transferred (which followed their own growth patterns).
+  size_t smallAllocsSize_;
+
+#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
+  bool fallibleScope_;
+#endif
+
+  void operator=(const LifoAlloc&) = delete;
+  LifoAlloc(const LifoAlloc&) = delete;
+
+  // Return a BumpChunk that can perform an allocation of at least size |n|.
+  UniqueBumpChunk newChunkWithCapacity(size_t n, bool oversize);
+
+  // Reuse or allocate a BumpChunk that can perform an allocation of at least
+  // size |n|, if successful it is placed at the end the list of |chunks_|.
+  UniqueBumpChunk getOrCreateChunk(size_t n);
+
+  void reset(size_t defaultChunkSize);
+
+  // Append unused chunks to the end of this LifoAlloc.
+  void appendUnused(BumpChunkList&& otherUnused) {
+#ifdef DEBUG
+    for (detail::BumpChunk& bc : otherUnused) {
+      MOZ_ASSERT(bc.empty());
+    }
+#endif
+    unused_.appendAll(std::move(otherUnused));
+  }
+
+  // Append used chunks to the end of this LifoAlloc. We act as if all the
+  // chunks in |this| are used, even if they're not, so memory may be wasted.
+  void appendUsed(BumpChunkList&& otherChunks) {
+    chunks_.appendAll(std::move(otherChunks));
+  }
+
+  // Track the amount of space allocated in used and unused chunks.
+  void incrementCurSize(size_t size) {
+    curSize_ += size;
+    if (curSize_ > peakSize_) {
+      peakSize_ = curSize_;
+    }
+  }
+  void decrementCurSize(size_t size) {
+    MOZ_ASSERT(curSize_ >= size);
+    curSize_ -= size;
+    MOZ_ASSERT(curSize_ >= smallAllocsSize_);
+  }
+
+  void* allocImplColdPath(size_t n);
+  void* allocImplOversize(size_t n);
+
+  MOZ_ALWAYS_INLINE
+  void* allocImpl(size_t n) {
+    void* result;
+    // Give oversized allocations their own chunk instead of wasting space
+    // due to fragmentation at the end of normal chunk.
+    if (MOZ_UNLIKELY(n > oversizeThreshold_)) {
+      return allocImplOversize(n);
+    }
+    if (MOZ_LIKELY(!chunks_.empty() &&
+                   (result = chunks_.last()->tryAlloc(n)))) {
+      return result;
+    }
+    return allocImplColdPath(n);
+  }
+
+  // Check for space in unused chunks or allocate a new unused chunk.
+  MOZ_MUST_USE bool ensureUnusedApproximateColdPath(size_t n, size_t total);
+
+ public:
+  explicit LifoAlloc(size_t defaultChunkSize)
+      : peakSize_(0)
+#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
+        ,
+        fallibleScope_(true)
+#endif
+  {
+    reset(defaultChunkSize);
+  }
+
+  // Set the threshold to allocate data in its own chunk outside the space for
+  // small allocations.
+  void disableOversize() { oversizeThreshold_ = SIZE_MAX; }
+  void setOversizeThreshold(size_t oversizeThreshold) {
+    MOZ_ASSERT(oversizeThreshold <= defaultChunkSize_);
+    oversizeThreshold_ = oversizeThreshold;
+  }
+
+  // Steal allocated chunks from |other|.
+  void steal(LifoAlloc* other);
+
+  // Append all chunks from |other|. They are removed from |other|.
+  void transferFrom(LifoAlloc* other);
+
+  // Append unused chunks from |other|. They are removed from |other|.
+  void transferUnusedFrom(LifoAlloc* other);
+
+  ~LifoAlloc() { freeAll(); }
+
+  size_t defaultChunkSize() const { return defaultChunkSize_; }
+
+  // Frees all held memory.
+  void freeAll();
+
+  static const unsigned HUGE_ALLOCATION = 50 * 1024 * 1024;
+  void freeAllIfHugeAndUnused() {
+    if (markCount == 0 && curSize_ > HUGE_ALLOCATION) {
+      freeAll();
+    }
+  }
+
+  MOZ_ALWAYS_INLINE
+  void* alloc(size_t n) {
+#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
+    // Only simulate OOMs when we are not using the LifoAlloc as an
+    // infallible allocator.
+    if (fallibleScope_) {
+      JS_OOM_POSSIBLY_FAIL();
+    }
+#endif
+    return allocImpl(n);
+  }
+
+  // Allocates |n| bytes if we can guarantee that we will have
+  // |needed| unused bytes remaining. Returns nullptr if we can't.
+  // This is useful for maintaining our ballast invariants while
+  // attempting fallible allocations.
+  MOZ_ALWAYS_INLINE
+  void* allocEnsureUnused(size_t n, size_t needed) {
+    JS_OOM_POSSIBLY_FAIL();
+    MOZ_ASSERT(fallibleScope_);
+
+    Mark m = mark();
+    void* result = allocImpl(n);
+    if (!ensureUnusedApproximate(needed)) {
+      release(m);
+      return nullptr;
+    }
+    cancelMark(m);
+    return result;
+  }
+
+  template <typename T, typename... Args>
+  MOZ_ALWAYS_INLINE T* newWithSize(size_t n, Args&&... args) {
+    MOZ_ASSERT(n >= sizeof(T), "must request enough space to store a T");
+    static_assert(alignof(T) <= detail::LIFO_ALLOC_ALIGN,
+                  "LifoAlloc must provide enough alignment to store T");
+    void* ptr = alloc(n);
+    if (!ptr) {
+      return nullptr;
+    }
+
+    return new (ptr) T(std::forward<Args>(args)...);
+  }
+
+  MOZ_ALWAYS_INLINE
+  void* allocInfallible(size_t n) {
+    AutoEnterOOMUnsafeRegion oomUnsafe;
+    if (void* result = allocImpl(n)) {
+      return result;
+    }
+    oomUnsafe.crash("LifoAlloc::allocInfallible");
+    return nullptr;
+  }
+
+  // Ensures that enough space exists to satisfy N bytes worth of
+  // allocation requests, not necessarily contiguous. Note that this does
+  // not guarantee a successful single allocation of N bytes.
+  MOZ_ALWAYS_INLINE
+  MOZ_MUST_USE bool ensureUnusedApproximate(size_t n) {
+    AutoFallibleScope fallibleAllocator(this);
+    size_t total = 0;
+    if (!chunks_.empty()) {
+      total += chunks_.last()->unused();
+      if (total >= n) {
+        return true;
+      }
+    }
+
+    return ensureUnusedApproximateColdPath(n, total);
+  }
+
+  MOZ_ALWAYS_INLINE
+  void setAsInfallibleByDefault() {
+#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
+    fallibleScope_ = false;
+#endif
+  }
+
+  class MOZ_NON_TEMPORARY_CLASS AutoFallibleScope {
+#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
+    LifoAlloc* lifoAlloc_;
+    bool prevFallibleScope_;
+
+   public:
+    explicit AutoFallibleScope(LifoAlloc* lifoAlloc) {
+      lifoAlloc_ = lifoAlloc;
+      prevFallibleScope_ = lifoAlloc->fallibleScope_;
+      lifoAlloc->fallibleScope_ = true;
+    }
+
+    ~AutoFallibleScope() { lifoAlloc_->fallibleScope_ = prevFallibleScope_; }
+#else
+   public:
+    explicit AutoFallibleScope(LifoAlloc*) {}
+#endif
+  };
+
+  template <typename T>
+  T* newArray(size_t count) {
+    static_assert(std::is_trivial_v<T>,
+                  "T must be trivially constructible so that constructors need "
+                  "not be called");
+    static_assert(std::is_trivially_destructible_v<T>,
+                  "T must be trivially destructible so destructors don't need "
+                  "to be called when the LifoAlloc is freed");
+    return newArrayUninitialized<T>(count);
+  }
+
+  // Create an array with uninitialized elements of type |T|.
+  // The caller is responsible for initialization.
+  template <typename T>
+  T* newArrayUninitialized(size_t count) {
+    size_t bytes;
+    if (MOZ_UNLIKELY(!CalculateAllocSize<T>(count, &bytes))) {
+      return nullptr;
+    }
+    return static_cast<T*>(alloc(bytes));
+  }
+
+  class Mark {
+    friend class LifoAlloc;
+    detail::BumpChunk::Mark chunk;
+    detail::BumpChunk::Mark oversize;
+  };
+
+  // Note: MOZ_NEVER_INLINE is a work around for a Clang 9 (PGO) miscompilation.
+  // See bug 1583907.
+  MOZ_NEVER_INLINE Mark mark();
+
+  void release(Mark mark);
+
+ private:
+  void cancelMark(Mark mark) { markCount--; }
+
+ public:
+  void releaseAll() {
+    MOZ_ASSERT(!markCount);
+
+    // When releasing all chunks, we can no longer determine which chunks were
+    // transferred and which were not, so simply clear the heuristic to zero
+    // right away.
+    smallAllocsSize_ = 0;
+
+    for (detail::BumpChunk& bc : chunks_) {
+      bc.release();
+    }
+    unused_.appendAll(std::move(chunks_));
+
+    // On release, we free any oversize allocations instead of keeping them
+    // in unused chunks.
+    while (!oversize_.empty()) {
+      UniqueBumpChunk bc = oversize_.popFirst();
+      decrementCurSize(bc->computedSizeOfIncludingThis());
+    }
+  }
+
+  // Protect the content of the LifoAlloc chunks.
+#ifdef LIFO_CHUNK_PROTECT
+  void setReadOnly();
+  void setReadWrite();
+#else
+  void setReadOnly() const {}
+  void setReadWrite() const {}
+#endif
+
+  // Get the total "used" (occupied bytes) count for the arena chunks.
+  size_t used() const {
+    size_t accum = 0;
+    for (const detail::BumpChunk& chunk : chunks_) {
+      accum += chunk.used();
+    }
+    return accum;
+  }
+
+  // Return true if the LifoAlloc does not currently contain any allocations.
+  bool isEmpty() const {
+    bool empty = chunks_.empty() ||
+                 (chunks_.begin() == chunks_.last() && chunks_.last()->empty());
+    MOZ_ASSERT_IF(!oversize_.empty(), !oversize_.last()->empty());
+    return empty && oversize_.empty();
+  }
+
+  // Return the number of bytes remaining to allocate in the current chunk.
+  // e.g. How many bytes we can allocate before needing a new block.
+  size_t availableInCurrentChunk() const {
+    if (chunks_.empty()) {
+      return 0;
+    }
+    return chunks_.last()->unused();
+  }
+
+  // Get the total size of the arena chunks (including unused space).
+  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
+    size_t n = 0;
+    for (const detail::BumpChunk& chunk : chunks_) {
+      n += chunk.sizeOfIncludingThis(mallocSizeOf);
+    }
+    for (const detail::BumpChunk& chunk : oversize_) {
+      n += chunk.sizeOfIncludingThis(mallocSizeOf);
+    }
+    for (const detail::BumpChunk& chunk : unused_) {
+      n += chunk.sizeOfIncludingThis(mallocSizeOf);
+    }
+    return n;
+  }
+
+  // Like sizeOfExcludingThis(), but includes the size of the LifoAlloc itself.
+  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
+    return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
+  }
+
+  // Get the current size of the arena chunks (including unused space and
+  // bookkeeping space).
+  size_t computedSizeOfExcludingThis() const { return curSize_; }
+
+  // Get the peak size of the arena chunks (including unused space and
+  // bookkeeping space).
+  size_t peakSizeOfExcludingThis() const { return peakSize_; }
+
+  // Doesn't perform construction; useful for lazily-initialized POD types.
+  template <typename T>
+  MOZ_ALWAYS_INLINE T* pod_malloc() {
+    return static_cast<T*>(alloc(sizeof(T)));
+  }
+
+  JS_DECLARE_NEW_METHODS(new_, alloc, MOZ_ALWAYS_INLINE)
+  JS_DECLARE_NEW_METHODS(newInfallible, allocInfallible, MOZ_ALWAYS_INLINE)
+
+#ifdef DEBUG
+  bool contains(void* ptr) const {
+    for (const detail::BumpChunk& chunk : chunks_) {
+      if (chunk.contains(ptr)) {
+        return true;
+      }
+    }
+    for (const detail::BumpChunk& chunk : oversize_) {
+      if (chunk.contains(ptr)) {
+        return true;
+      }
+    }
+    return false;
+  }
+#endif
+
+  // Iterate over the data allocated in a LifoAlloc, and interpret it.
+  class Enum {
+    friend class LifoAlloc;
+    friend class detail::BumpChunk;
+
+    // Iterator over the list of bump chunks.
+    BumpChunkList::Iterator chunkIt_;
+    BumpChunkList::Iterator chunkEnd_;
+    // Read head (must be within chunk_).
+    uint8_t* head_;
+
+    // If there is not enough room in the remaining block for |size|,
+    // advance to the next block and update the position.
+    uint8_t* seekBaseAndAdvanceBy(size_t size) {
+      MOZ_ASSERT(!empty());
+
+      uint8_t* aligned = detail::BumpChunk::nextAllocBase(head_);
+      if (detail::BumpChunk::nextAllocEnd(aligned, size) > chunkIt_->end()) {
+        ++chunkIt_;
+        aligned = chunkIt_->begin();
+        // The current code assumes that if we have a chunk, then we
+        // have allocated something it in.
+        MOZ_ASSERT(!chunkIt_->empty());
+      }
+      head_ = detail::BumpChunk::nextAllocEnd(aligned, size);
+      MOZ_ASSERT(head_ <= chunkIt_->end());
+      return aligned;
+    }
+
+   public:
+    explicit Enum(LifoAlloc& alloc)
+        : chunkIt_(alloc.chunks_.begin()),
+          chunkEnd_(alloc.chunks_.end()),
+          head_(nullptr) {
+      MOZ_RELEASE_ASSERT(alloc.oversize_.empty());
+      if (chunkIt_ != chunkEnd_) {
+        head_ = chunkIt_->begin();
+      }
+    }
+
+    // Return true if there are no more bytes to enumerate.
+    bool empty() {
+      return chunkIt_ == chunkEnd_ ||
+             (chunkIt_->next() == chunkEnd_.get() && head_ >= chunkIt_->end());
+    }
+
+    // Move the read position forward by the size of one T.
+    template <typename T>
+    T* read(size_t size = sizeof(T)) {
+      return reinterpret_cast<T*>(read(size));
+    }
+
+    // Return a pointer to the item at the current position. This returns a
+    // pointer to the inline storage, not a copy, and moves the read-head by
+    // the requested |size|.
+    void* read(size_t size) { return seekBaseAndAdvanceBy(size); }
+  };
+};
+
+class MOZ_NON_TEMPORARY_CLASS LifoAllocScope {
+  LifoAlloc* lifoAlloc;
+  LifoAlloc::Mark mark;
+  LifoAlloc::AutoFallibleScope fallibleScope;
+
+ public:
+  explicit LifoAllocScope(LifoAlloc* lifoAlloc)
+      : lifoAlloc(lifoAlloc),
+        mark(lifoAlloc->mark()),
+        fallibleScope(lifoAlloc) {}
+
+  ~LifoAllocScope() {
+    lifoAlloc->release(mark);
+
+    /*
+     * The parser can allocate enormous amounts of memory for large functions.
+     * Eagerly free the memory now (which otherwise won't be freed until the
+     * next GC) to avoid unnecessary OOMs.
+     */
+    lifoAlloc->freeAllIfHugeAndUnused();
+  }
+
+  LifoAlloc& alloc() { return *lifoAlloc; }
+};
+
+enum Fallibility { Fallible, Infallible };
+
+template <Fallibility fb>
+class LifoAllocPolicy {
+  LifoAlloc& alloc_;
+
+ public:
+  MOZ_IMPLICIT LifoAllocPolicy(LifoAlloc& alloc) : alloc_(alloc) {}
+  template <typename T>
+  T* maybe_pod_malloc(size_t numElems) {
+    size_t bytes;
+    if (MOZ_UNLIKELY(!CalculateAllocSize<T>(numElems, &bytes))) {
+      return nullptr;
+    }
+    void* p =
+        fb == Fallible ? alloc_.alloc(bytes) : alloc_.allocInfallible(bytes);
+    return static_cast<T*>(p);
+  }
+  template <typename T>
+  T* maybe_pod_calloc(size_t numElems) {
+    T* p = maybe_pod_malloc<T>(numElems);
+    if (MOZ_UNLIKELY(!p)) {
+      return nullptr;
+    }
+    memset(p, 0, numElems * sizeof(T));
+    return p;
+  }
+  template <typename T>
+  T* maybe_pod_realloc(T* p, size_t oldSize, size_t newSize) {
+    T* n = maybe_pod_malloc<T>(newSize);
+    if (MOZ_UNLIKELY(!n)) {
+      return nullptr;
+    }
+    MOZ_ASSERT(!(oldSize & mozilla::tl::MulOverflowMask<sizeof(T)>::value));
+    memcpy(n, p, std::min(oldSize * sizeof(T), newSize * sizeof(T)));
+    return n;
+  }
+  template <typename T>
+  T* pod_malloc(size_t numElems) {
+    return maybe_pod_malloc<T>(numElems);
+  }
+  template <typename T>
+  T* pod_calloc(size_t numElems) {
+    return maybe_pod_calloc<T>(numElems);
+  }
+  template <typename T>
+  T* pod_realloc(T* p, size_t oldSize, size_t newSize) {
+    return maybe_pod_realloc<T>(p, oldSize, newSize);
+  }
+  template <typename T>
+  void free_(T* p, size_t numElems) {}
+  void reportAllocOverflow() const {}
+  MOZ_MUST_USE bool checkSimulatedOOM() const {
+    return fb == Infallible || !js::oom::ShouldFailWithOOM();
+  }
+};
+
+}  // namespace js
+
+#endif /* ds_LifoAlloc_h */
diff --git a/js/src/ds/MemoryProtectionExceptionHandler.cpp b/js/src/ds/MemoryProtectionExceptionHandler.cpp
new file mode 100644
index 0000000000..3c4eb00c30
--- /dev/null
+++ b/js/src/ds/MemoryProtectionExceptionHandler.cpp
@@ -0,0 +1,789 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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/. */
+
+#include "ds/MemoryProtectionExceptionHandler.h"
+
+#include "mozilla/Assertions.h"
+#include "mozilla/Atomics.h"
+
+#if defined(XP_WIN)
+#  include "util/Windows.h"
+#elif defined(XP_UNIX) && !defined(XP_DARWIN)
+#  include <signal.h>
+#  include <sys/types.h>
+#  include <unistd.h>
+#elif defined(XP_DARWIN)
+#  include <mach/mach.h>
+#  include <unistd.h>
+#endif
+
+#ifdef ANDROID
+#  include <android/log.h>
+#endif
+
+#include "ds/SplayTree.h"
+
+#include "threading/LockGuard.h"
+#include "threading/Thread.h"
+#include "vm/MutexIDs.h"
+#include "vm/Runtime.h"
+
+namespace js {
+
+// Memory protection occurs at non-deterministic points when
+// recording/replaying.
+static mozilla::Atomic<bool, mozilla::SequentiallyConsistent>
+    sProtectedRegionsInit(false);
+
+/*
+ * A class to store the addresses of the regions recognized as protected
+ * by this exception handler. We use a splay tree to store these addresses.
+ */
+class ProtectedRegionTree {
+  struct Region {
+    uintptr_t first;
+    uintptr_t last;
+
+    Region(uintptr_t addr, size_t size)
+        : first(addr), last(addr + (size - 1)) {}
+
+    // This function compares 2 memory regions. If they overlap they are
+    // considered as identical. This is used for querying if an address is
+    // included in a range, or if an address is already registered as a
+    // protected region.
+    static int compare(const Region& A, const Region& B) {
+      if (A.last < B.first) {
+        return -1;
+      }
+      if (A.first > B.last) {
+        return 1;
+      }
+      return 0;
+    }
+  };
+
+  Mutex lock;
+  LifoAlloc alloc;
+  SplayTree<Region, Region> tree;
+
+ public:
+  ProtectedRegionTree()
+      : lock(mutexid::ProtectedRegionTree),
+        // Here "false" is used to not use the memory protection mechanism of
+        // LifoAlloc in order to prevent dead-locks.
+        alloc(4096),
+        tree(&alloc) {
+    sProtectedRegionsInit = true;
+  }
+
+  ~ProtectedRegionTree() { sProtectedRegionsInit = false; }
+
+  void insert(uintptr_t addr, size_t size) {
+    MOZ_ASSERT(addr && size);
+    LockGuard<Mutex> guard(lock);
+    AutoEnterOOMUnsafeRegion oomUnsafe;
+    if (!tree.insert(Region(addr, size))) {
+      oomUnsafe.crash("Failed to store allocation ID.");
+    }
+  }
+
+  void remove(uintptr_t addr) {
+    MOZ_ASSERT(addr);
+    LockGuard<Mutex> guard(lock);
+    tree.remove(Region(addr, 1));
+  }
+
+  bool isProtected(uintptr_t addr) {
+    if (!addr) {
+      return false;
+    }
+    LockGuard<Mutex> guard(lock);
+    return tree.maybeLookup(Region(addr, 1));
+  }
+};
+
+static bool sExceptionHandlerInstalled = false;
+
+static ProtectedRegionTree sProtectedRegions;
+
+bool MemoryProtectionExceptionHandler::isDisabled() {
+#if defined(XP_WIN) && defined(MOZ_ASAN)
+  // Under Windows ASan, WasmFaultHandler registers itself at 'last' priority
+  // in order to let ASan's ShadowExceptionHandler stay at 'first' priority.
+  // Unfortunately that results in spurious wasm faults passing through the
+  // MemoryProtectionExceptionHandler, which breaks its assumption that any
+  // faults it sees are fatal. Just disable this handler in that case, as the
+  // crash annotations provided here are not critical for ASan builds.
+  return true;
+#elif !defined(MOZ_DIAGNOSTIC_ASSERT_ENABLED)
+  // Disable the exception handler for Beta and Release builds.
+  return true;
+#else
+  return false;
+#endif
+}
+
+void MemoryProtectionExceptionHandler::addRegion(void* addr, size_t size) {
+  if (sExceptionHandlerInstalled && sProtectedRegionsInit) {
+    sProtectedRegions.insert(uintptr_t(addr), size);
+  }
+}
+
+void MemoryProtectionExceptionHandler::removeRegion(void* addr) {
+  if (sExceptionHandlerInstalled && sProtectedRegionsInit) {
+    sProtectedRegions.remove(uintptr_t(addr));
+  }
+}
+
+/* -------------------------------------------------------------------------- */
+
+/*
+ * This helper function attempts to replicate the functionality of
+ * mozilla::MOZ_ReportCrash() in an async-signal-safe way.
+ */
+static MOZ_COLD MOZ_ALWAYS_INLINE void ReportCrashIfDebug(const char* aStr)
+    MOZ_PRETEND_NORETURN_FOR_STATIC_ANALYSIS {
+#ifdef DEBUG
+#  if defined(XP_WIN)
+  DWORD bytesWritten;
+  BOOL ret = WriteFile(GetStdHandle(STD_ERROR_HANDLE), aStr, strlen(aStr) + 1,
+                       &bytesWritten, nullptr);
+#  elif defined(ANDROID)
+  int ret = __android_log_write(ANDROID_LOG_FATAL, "MOZ_CRASH", aStr);
+#  else
+  ssize_t ret = write(STDERR_FILENO, aStr, strlen(aStr) + 1);
+#  endif
+  (void)ret;  // Ignore failures; we're already crashing anyway.
+#endif
+}
+
+/* -------------------------------------------------------------------------- */
+
+#if defined(XP_WIN)
+
+static void* sVectoredExceptionHandler = nullptr;
+
+/*
+ * We can only handle one exception. To guard against races and reentrancy,
+ * we set this value the first time we enter the exception handler and never
+ * touch it again.
+ */
+static mozilla::Atomic<bool> sHandlingException(false);
+
+static long __stdcall VectoredExceptionHandler(
+    EXCEPTION_POINTERS* ExceptionInfo) {
+  EXCEPTION_RECORD* ExceptionRecord = ExceptionInfo->ExceptionRecord;
+
+  // We only handle one kind of exception; ignore all others.
+  if (ExceptionRecord->ExceptionCode == EXCEPTION_ACCESS_VIOLATION) {
+    // Make absolutely sure we can only get here once.
+    if (sHandlingException.compareExchange(false, true)) {
+      // Restore the previous handler. We're going to forward to it
+      // anyway, and if we crash while doing so we don't want to hang.
+      MOZ_ALWAYS_TRUE(
+          RemoveVectoredExceptionHandler(sVectoredExceptionHandler));
+      sExceptionHandlerInstalled = false;
+
+      // Get the address that the offending code tried to access.
+      uintptr_t address = uintptr_t(ExceptionRecord->ExceptionInformation[1]);
+
+      // If the faulting address is in one of our protected regions, we
+      // want to annotate the crash to make it stand out from the crowd.
+      if (sProtectedRegionsInit && sProtectedRegions.isProtected(address)) {
+        ReportCrashIfDebug(
+            "Hit MOZ_CRASH(Tried to access a protected region!)\n");
+        MOZ_CRASH_ANNOTATE("MOZ_CRASH(Tried to access a protected region!)");
+      }
+    }
+  }
+
+  // Forward to the previous handler which may be a debugger,
+  // the crash reporter or something else entirely.
+  return EXCEPTION_CONTINUE_SEARCH;
+}
+
+bool MemoryProtectionExceptionHandler::install() {
+  MOZ_ASSERT(!sExceptionHandlerInstalled);
+
+  // If the exception handler is disabled, report success anyway.
+  if (MemoryProtectionExceptionHandler::isDisabled()) {
+    return true;
+  }
+
+  // Install our new exception handler.
+  sVectoredExceptionHandler = AddVectoredExceptionHandler(
+      /* FirstHandler = */ true, VectoredExceptionHandler);
+
+  sExceptionHandlerInstalled = sVectoredExceptionHandler != nullptr;
+  return sExceptionHandlerInstalled;
+}
+
+void MemoryProtectionExceptionHandler::uninstall() {
+  if (sExceptionHandlerInstalled) {
+    MOZ_ASSERT(!sHandlingException);
+
+    // Restore the previous exception handler.
+    MOZ_ALWAYS_TRUE(RemoveVectoredExceptionHandler(sVectoredExceptionHandler));
+
+    sExceptionHandlerInstalled = false;
+  }
+}
+
+#elif defined(XP_UNIX) && !defined(XP_DARWIN)
+
+static struct sigaction sPrevSEGVHandler = {};
+
+/*
+ * We can only handle one exception. To guard against races and reentrancy,
+ * we set this value the first time we enter the exception handler and never
+ * touch it again.
+ */
+static mozilla::Atomic<bool> sHandlingException(false);
+
+static void UnixExceptionHandler(int signum, siginfo_t* info, void* context) {
+  // Make absolutely sure we can only get here once.
+  if (sHandlingException.compareExchange(false, true)) {
+    // Restore the previous handler. We're going to forward to it
+    // anyway, and if we crash while doing so we don't want to hang.
+    MOZ_ALWAYS_FALSE(sigaction(SIGSEGV, &sPrevSEGVHandler, nullptr));
+
+    MOZ_ASSERT(signum == SIGSEGV && info->si_signo == SIGSEGV);
+
+    if (info->si_code == SEGV_ACCERR) {
+      // Get the address that the offending code tried to access.
+      uintptr_t address = uintptr_t(info->si_addr);
+
+      // If the faulting address is in one of our protected regions, we
+      // want to annotate the crash to make it stand out from the crowd.
+      if (sProtectedRegionsInit && sProtectedRegions.isProtected(address)) {
+        ReportCrashIfDebug(
+            "Hit MOZ_CRASH(Tried to access a protected region!)\n");
+        MOZ_CRASH_ANNOTATE("MOZ_CRASH(Tried to access a protected region!)");
+      }
+    }
+  }
+
+  // Forward to the previous handler which may be a debugger,
+  // the crash reporter or something else entirely.
+  if (sPrevSEGVHandler.sa_flags & SA_SIGINFO) {
+    sPrevSEGVHandler.sa_sigaction(signum, info, context);
+  } else if (sPrevSEGVHandler.sa_handler == SIG_DFL ||
+             sPrevSEGVHandler.sa_handler == SIG_IGN) {
+    sigaction(SIGSEGV, &sPrevSEGVHandler, nullptr);
+  } else {
+    sPrevSEGVHandler.sa_handler(signum);
+  }
+
+  // If we reach here, we're returning to let the default signal handler deal
+  // with the exception. This is technically undefined behavior, but
+  // everything seems to do it, and it removes us from the crash stack.
+}
+
+bool MemoryProtectionExceptionHandler::install() {
+  MOZ_ASSERT(!sExceptionHandlerInstalled);
+
+  // If the exception handler is disabled, report success anyway.
+  if (MemoryProtectionExceptionHandler::isDisabled()) {
+    return true;
+  }
+
+  // Install our new exception handler and save the previous one.
+  struct sigaction faultHandler = {};
+  faultHandler.sa_flags = SA_SIGINFO | SA_NODEFER | SA_ONSTACK;
+  faultHandler.sa_sigaction = UnixExceptionHandler;
+  sigemptyset(&faultHandler.sa_mask);
+  sExceptionHandlerInstalled =
+      !sigaction(SIGSEGV, &faultHandler, &sPrevSEGVHandler);
+
+  return sExceptionHandlerInstalled;
+}
+
+void MemoryProtectionExceptionHandler::uninstall() {
+  if (sExceptionHandlerInstalled) {
+    MOZ_ASSERT(!sHandlingException);
+
+    // Restore the previous exception handler.
+    MOZ_ALWAYS_FALSE(sigaction(SIGSEGV, &sPrevSEGVHandler, nullptr));
+
+    sExceptionHandlerInstalled = false;
+  }
+}
+
+#elif defined(XP_DARWIN)
+
+/*
+ * The fact that we need to be able to forward to other exception handlers
+ * makes this code much more complicated. The forwarding logic and the
+ * structures required to make it work are heavily based on the code at
+ * www.ravenbrook.com/project/mps/prototype/2013-06-24/machtest/machtest/main.c
+ */
+
+/* -------------------------------------------------------------------------- */
+/*                Begin Mach definitions and helper functions                 */
+/* -------------------------------------------------------------------------- */
+
+/*
+ * These are the message IDs associated with each exception type.
+ * We'll be using sIDRequest64, but we need the others for forwarding.
+ */
+static const mach_msg_id_t sIDRequest32 = 2401;
+static const mach_msg_id_t sIDRequestState32 = 2402;
+static const mach_msg_id_t sIDRequestStateIdentity32 = 2403;
+
+static const mach_msg_id_t sIDRequest64 = 2405;
+static const mach_msg_id_t sIDRequestState64 = 2406;
+static const mach_msg_id_t sIDRequestStateIdentity64 = 2407;
+
+/*
+ * Each message ID has an associated Mach message structure.
+ * We use the preprocessor to make defining them a little less arduous.
+ */
+#  define REQUEST_HEADER_FIELDS mach_msg_header_t header;
+
+#  define REQUEST_IDENTITY_FIELDS      \
+    mach_msg_body_t msgh_body;         \
+    mach_msg_port_descriptor_t thread; \
+    mach_msg_port_descriptor_t task;
+
+#  define REQUEST_GENERAL_FIELDS(bits) \
+    NDR_record_t NDR;                  \
+    exception_type_t exception;        \
+    mach_msg_type_number_t code_count; \
+    int##bits##_t code[2];
+
+#  define REQUEST_STATE_FIELDS              \
+    int flavor;                             \
+    mach_msg_type_number_t old_state_count; \
+    natural_t old_state[THREAD_STATE_MAX];
+
+#  define REQUEST_TRAILER_FIELDS mach_msg_trailer_t trailer;
+
+#  define EXCEPTION_REQUEST(bits)   \
+    struct ExceptionRequest##bits { \
+      REQUEST_HEADER_FIELDS         \
+      REQUEST_IDENTITY_FIELDS       \
+      REQUEST_GENERAL_FIELDS(bits)  \
+      REQUEST_TRAILER_FIELDS        \
+    };
+
+#  define EXCEPTION_REQUEST_STATE(bits)  \
+    struct ExceptionRequestState##bits { \
+      REQUEST_HEADER_FIELDS              \
+      REQUEST_GENERAL_FIELDS(bits)       \
+      REQUEST_STATE_FIELDS               \
+      REQUEST_TRAILER_FIELDS             \
+    };
+
+#  define EXCEPTION_REQUEST_STATE_IDENTITY(bits) \
+    struct ExceptionRequestStateIdentity##bits { \
+      REQUEST_HEADER_FIELDS                      \
+      REQUEST_IDENTITY_FIELDS                    \
+      REQUEST_GENERAL_FIELDS(bits)               \
+      REQUEST_STATE_FIELDS                       \
+      REQUEST_TRAILER_FIELDS                     \
+    };
+
+/* This is needed because not all fields are naturally aligned on 64-bit. */
+#  ifdef __MigPackStructs
+#    pragma pack(4)
+#  endif
+
+EXCEPTION_REQUEST(32)
+EXCEPTION_REQUEST(64)
+EXCEPTION_REQUEST_STATE(32)
+EXCEPTION_REQUEST_STATE(64)
+EXCEPTION_REQUEST_STATE_IDENTITY(32)
+EXCEPTION_REQUEST_STATE_IDENTITY(64)
+
+/* We use this as a common base when forwarding to the previous handler. */
+union ExceptionRequestUnion {
+  mach_msg_header_t header;
+  ExceptionRequest32 r32;
+  ExceptionRequest64 r64;
+  ExceptionRequestState32 rs32;
+  ExceptionRequestState64 rs64;
+  ExceptionRequestStateIdentity32 rsi32;
+  ExceptionRequestStateIdentity64 rsi64;
+};
+
+/* This isn't really a full Mach message, but it's all we need to send. */
+struct ExceptionReply {
+  mach_msg_header_t header;
+  NDR_record_t NDR;
+  kern_return_t RetCode;
+};
+
+#  ifdef __MigPackStructs
+#    pragma pack()
+#  endif
+
+#  undef EXCEPTION_REQUEST_STATE_IDENTITY
+#  undef EXCEPTION_REQUEST_STATE
+#  undef EXCEPTION_REQUEST
+#  undef REQUEST_STATE_FIELDS
+#  undef REQUEST_GENERAL_FIELDS
+#  undef REQUEST_IDENTITY_FIELDS
+#  undef REQUEST_HEADER_FIELDS
+
+/*
+ * The exception handler we're forwarding to may not have the same behavior
+ * or thread state flavor as what we're using. These macros help populate
+ * the fields of the message we're about to send to the previous handler.
+ */
+#  define COPY_REQUEST_COMMON(bits, id)                                  \
+    dst.header = src.header;                                             \
+    dst.header.msgh_id = id;                                             \
+    dst.header.msgh_size =                                               \
+        static_cast<mach_msg_size_t>(sizeof(dst) - sizeof(dst.trailer)); \
+    dst.NDR = src.NDR;                                                   \
+    dst.exception = src.exception;                                       \
+    dst.code_count = src.code_count;                                     \
+    dst.code[0] = int##bits##_t(src.code[0]);                            \
+    dst.code[1] = int##bits##_t(src.code[1]);
+
+#  define COPY_REQUEST_IDENTITY    \
+    dst.msgh_body = src.msgh_body; \
+    dst.thread = src.thread;       \
+    dst.task = src.task;
+
+#  define COPY_REQUEST_STATE(flavor, stateCount, state)                  \
+    mach_msg_size_t stateSize = stateCount * sizeof(natural_t);          \
+    dst.header.msgh_size =                                               \
+        static_cast<mach_msg_size_t>(sizeof(dst) - sizeof(dst.trailer) - \
+                                     sizeof(dst.old_state) + stateSize); \
+    dst.flavor = flavor;                                                 \
+    dst.old_state_count = stateCount;                                    \
+    memcpy(dst.old_state, state, stateSize);
+
+#  define COPY_EXCEPTION_REQUEST(bits)                                    \
+    static void CopyExceptionRequest##bits(ExceptionRequest64& src,       \
+                                           ExceptionRequest##bits& dst) { \
+      COPY_REQUEST_COMMON(bits, sIDRequest##bits)                         \
+      COPY_REQUEST_IDENTITY                                               \
+    }
+
+#  define COPY_EXCEPTION_REQUEST_STATE(bits)                             \
+    static void CopyExceptionRequestState##bits(                         \
+        ExceptionRequest64& src, ExceptionRequestState##bits& dst,       \
+        thread_state_flavor_t flavor, mach_msg_type_number_t stateCount, \
+        thread_state_t state) {                                          \
+      COPY_REQUEST_COMMON(bits, sIDRequestState##bits)                   \
+      COPY_REQUEST_STATE(flavor, stateCount, state)                      \
+    }
+
+#  define COPY_EXCEPTION_REQUEST_STATE_IDENTITY(bits)                      \
+    static void CopyExceptionRequestStateIdentity##bits(                   \
+        ExceptionRequest64& src, ExceptionRequestStateIdentity##bits& dst, \
+        thread_state_flavor_t flavor, mach_msg_type_number_t stateCount,   \
+        thread_state_t state) {                                            \
+      COPY_REQUEST_COMMON(bits, sIDRequestStateIdentity##bits)             \
+      COPY_REQUEST_IDENTITY                                                \
+      COPY_REQUEST_STATE(flavor, stateCount, state)                        \
+    }
+
+COPY_EXCEPTION_REQUEST(32)
+COPY_EXCEPTION_REQUEST_STATE(32)
+COPY_EXCEPTION_REQUEST_STATE_IDENTITY(32)
+COPY_EXCEPTION_REQUEST(64)
+COPY_EXCEPTION_REQUEST_STATE(64)
+COPY_EXCEPTION_REQUEST_STATE_IDENTITY(64)
+
+#  undef COPY_EXCEPTION_REQUEST_STATE_IDENTITY
+#  undef COPY_EXCEPTION_REQUEST_STATE
+#  undef COPY_EXCEPTION_REQUEST
+#  undef COPY_REQUEST_STATE
+#  undef COPY_REQUEST_IDENTITY
+#  undef COPY_REQUEST_COMMON
+
+/* -------------------------------------------------------------------------- */
+/*                 End Mach definitions and helper functions                  */
+/* -------------------------------------------------------------------------- */
+
+/* Every Mach exception handler is parameterized by these four properties. */
+struct MachExceptionParameters {
+  exception_mask_t mask;
+  mach_port_t port;
+  exception_behavior_t behavior;
+  thread_state_flavor_t flavor;
+};
+
+struct ExceptionHandlerState {
+  MachExceptionParameters current;
+  MachExceptionParameters previous;
+
+  /* Each Mach exception handler runs in its own thread. */
+  Thread handlerThread;
+};
+
+/* This choice of ID is arbitrary, but must not match our exception ID. */
+static const mach_msg_id_t sIDQuit = 42;
+
+static ExceptionHandlerState* sMachExceptionState = nullptr;
+
+/*
+ * The meat of our exception handler. This thread waits for an exception
+ * message, annotates the exception if needed, then forwards it to the
+ * previously installed handler (which will likely terminate the process).
+ */
+static void MachExceptionHandler() {
+  ThisThread::SetName("JS MachExceptionHandler");
+  kern_return_t ret;
+  MachExceptionParameters& current = sMachExceptionState->current;
+  MachExceptionParameters& previous = sMachExceptionState->previous;
+
+  // We use the simplest kind of 64-bit exception message here.
+  ExceptionRequest64 request = {};
+  request.header.msgh_local_port = current.port;
+  request.header.msgh_size = static_cast<mach_msg_size_t>(sizeof(request));
+  ret = mach_msg(&request.header, MACH_RCV_MSG, 0, request.header.msgh_size,
+                 current.port, MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL);
+
+  // Restore the previous handler. We're going to forward to it
+  // anyway, and if we crash while doing so we don't want to hang.
+  task_set_exception_ports(mach_task_self(), previous.mask, previous.port,
+                           previous.behavior, previous.flavor);
+
+  // If we failed even receiving the message, just give up.
+  if (ret != MACH_MSG_SUCCESS) {
+    MOZ_CRASH("MachExceptionHandler: mach_msg failed to receive a message!");
+  }
+
+  // Terminate the thread if we're shutting down.
+  if (request.header.msgh_id == sIDQuit) {
+    return;
+  }
+
+  // The only other valid message ID is the one associated with the
+  // EXCEPTION_DEFAULT | MACH_EXCEPTION_CODES behavior we chose.
+  if (request.header.msgh_id != sIDRequest64) {
+    MOZ_CRASH("MachExceptionHandler: Unexpected Message ID!");
+  }
+
+  // Make sure we can understand the exception we received.
+  if (request.exception != EXC_BAD_ACCESS || request.code_count != 2) {
+    MOZ_CRASH("MachExceptionHandler: Unexpected exception type!");
+  }
+
+  // Get the address that the offending code tried to access.
+  uintptr_t address = uintptr_t(request.code[1]);
+
+  // If the faulting address is inside one of our protected regions, we
+  // want to annotate the crash to make it stand out from the crowd.
+  if (sProtectedRegionsInit && sProtectedRegions.isProtected(address)) {
+    ReportCrashIfDebug("Hit MOZ_CRASH(Tried to access a protected region!)\n");
+    MOZ_CRASH_ANNOTATE("MOZ_CRASH(Tried to access a protected region!)");
+  }
+
+  // Forward to the previous handler which may be a debugger, the unix
+  // signal handler, the crash reporter or something else entirely.
+  if (previous.port != MACH_PORT_NULL) {
+    mach_msg_type_number_t stateCount;
+    thread_state_data_t state;
+    if ((uint32_t(previous.behavior) & ~MACH_EXCEPTION_CODES) !=
+        EXCEPTION_DEFAULT) {
+      // If the previous handler requested thread state, get it here.
+      stateCount = THREAD_STATE_MAX;
+      ret = thread_get_state(request.thread.name, previous.flavor, state,
+                             &stateCount);
+      if (ret != KERN_SUCCESS) {
+        MOZ_CRASH(
+            "MachExceptionHandler: Could not get the thread state to forward!");
+      }
+    }
+
+    // Depending on the behavior of the previous handler, the forwarded
+    // exception message will have a different set of fields.
+    // Of particular note is that exception handlers that lack
+    // MACH_EXCEPTION_CODES will get 32-bit fields even on 64-bit
+    // systems. It appears that OSX simply truncates these fields.
+    ExceptionRequestUnion forward;
+    switch (uint32_t(previous.behavior)) {
+      case EXCEPTION_DEFAULT:
+        CopyExceptionRequest32(request, forward.r32);
+        break;
+      case EXCEPTION_DEFAULT | MACH_EXCEPTION_CODES:
+        CopyExceptionRequest64(request, forward.r64);
+        break;
+      case EXCEPTION_STATE:
+        CopyExceptionRequestState32(request, forward.rs32, previous.flavor,
+                                    stateCount, state);
+        break;
+      case EXCEPTION_STATE | MACH_EXCEPTION_CODES:
+        CopyExceptionRequestState64(request, forward.rs64, previous.flavor,
+                                    stateCount, state);
+        break;
+      case EXCEPTION_STATE_IDENTITY:
+        CopyExceptionRequestStateIdentity32(request, forward.rsi32,
+                                            previous.flavor, stateCount, state);
+        break;
+      case EXCEPTION_STATE_IDENTITY | MACH_EXCEPTION_CODES:
+        CopyExceptionRequestStateIdentity64(request, forward.rsi64,
+                                            previous.flavor, stateCount, state);
+        break;
+      default:
+        MOZ_CRASH("MachExceptionHandler: Unknown previous handler behavior!");
+    }
+
+    // Forward the generated message to the old port. The local and remote
+    // port fields *and their rights* are swapped on arrival, so we need to
+    // swap them back first.
+    forward.header.msgh_bits =
+        (request.header.msgh_bits & ~MACH_MSGH_BITS_PORTS_MASK) |
+        MACH_MSGH_BITS(MACH_MSGH_BITS_LOCAL(request.header.msgh_bits),
+                       MACH_MSGH_BITS_REMOTE(request.header.msgh_bits));
+    forward.header.msgh_local_port = forward.header.msgh_remote_port;
+    forward.header.msgh_remote_port = previous.port;
+    ret = mach_msg(&forward.header, MACH_SEND_MSG, forward.header.msgh_size, 0,
+                   MACH_PORT_NULL, MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL);
+    if (ret != MACH_MSG_SUCCESS) {
+      MOZ_CRASH(
+          "MachExceptionHandler: Failed to forward to the previous handler!");
+    }
+  } else {
+    // There was no previous task-level exception handler, so defer to the
+    // host level one instead. We set the return code to KERN_FAILURE to
+    // indicate that we did not handle the exception.
+    // The reply message ID is always the request ID + 100.
+    ExceptionReply reply = {};
+    reply.header.msgh_bits =
+        MACH_MSGH_BITS(MACH_MSGH_BITS_REMOTE(request.header.msgh_bits), 0);
+    reply.header.msgh_size = static_cast<mach_msg_size_t>(sizeof(reply));
+    reply.header.msgh_remote_port = request.header.msgh_remote_port;
+    reply.header.msgh_local_port = MACH_PORT_NULL;
+    reply.header.msgh_id = request.header.msgh_id + 100;
+    reply.NDR = request.NDR;
+    reply.RetCode = KERN_FAILURE;
+    ret = mach_msg(&reply.header, MACH_SEND_MSG, reply.header.msgh_size, 0,
+                   MACH_PORT_NULL, MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL);
+    if (ret != MACH_MSG_SUCCESS) {
+      MOZ_CRASH("MachExceptionHandler: Failed to forward to the host level!");
+    }
+  }
+}
+
+static void TerminateMachExceptionHandlerThread() {
+  // Send a simple quit message to the exception handler thread.
+  mach_msg_header_t msg;
+  msg.msgh_bits = MACH_MSGH_BITS(MACH_MSG_TYPE_COPY_SEND, 0);
+  msg.msgh_size = static_cast<mach_msg_size_t>(sizeof(msg));
+  msg.msgh_remote_port = sMachExceptionState->current.port;
+  msg.msgh_local_port = MACH_PORT_NULL;
+  msg.msgh_reserved = 0;
+  msg.msgh_id = sIDQuit;
+  kern_return_t ret =
+      mach_msg(&msg, MACH_SEND_MSG, sizeof(msg), 0, MACH_PORT_NULL,
+               MACH_MSG_TIMEOUT_NONE, MACH_PORT_NULL);
+
+  if (ret == MACH_MSG_SUCCESS) {
+    sMachExceptionState->handlerThread.join();
+  } else {
+    MOZ_CRASH("MachExceptionHandler: Handler thread failed to terminate!");
+  }
+}
+
+bool MemoryProtectionExceptionHandler::install() {
+  MOZ_ASSERT(!sExceptionHandlerInstalled);
+  MOZ_ASSERT(!sMachExceptionState);
+
+  // If the exception handler is disabled, report success anyway.
+  if (MemoryProtectionExceptionHandler::isDisabled()) {
+    return true;
+  }
+
+  sMachExceptionState = js_new<ExceptionHandlerState>();
+  if (!sMachExceptionState) {
+    return false;
+  }
+
+  kern_return_t ret;
+  mach_port_t task = mach_task_self();
+
+  // Allocate a new exception port with receive rights.
+  sMachExceptionState->current = {};
+  MachExceptionParameters& current = sMachExceptionState->current;
+  ret = mach_port_allocate(task, MACH_PORT_RIGHT_RECEIVE, &current.port);
+  if (ret != KERN_SUCCESS) {
+    return false;
+  }
+
+  // Give the new port send rights as well.
+  ret = mach_port_insert_right(task, current.port, current.port,
+                               MACH_MSG_TYPE_MAKE_SEND);
+  if (ret != KERN_SUCCESS) {
+    mach_port_deallocate(task, current.port);
+    current = {};
+    return false;
+  }
+
+  // Start the thread that will receive the messages from our exception port.
+  if (!sMachExceptionState->handlerThread.init(MachExceptionHandler)) {
+    mach_port_deallocate(task, current.port);
+    current = {};
+    return false;
+  }
+
+  // Set the other properties of our new exception handler.
+  current.mask = EXC_MASK_BAD_ACCESS;
+  current.behavior =
+      exception_behavior_t(EXCEPTION_DEFAULT | MACH_EXCEPTION_CODES);
+  current.flavor = THREAD_STATE_NONE;
+
+  // Tell the task to use our exception handler, and save the previous one.
+  sMachExceptionState->previous = {};
+  MachExceptionParameters& previous = sMachExceptionState->previous;
+  mach_msg_type_number_t previousCount = 1;
+  ret = task_swap_exception_ports(
+      task, current.mask, current.port, current.behavior, current.flavor,
+      &previous.mask, &previousCount, &previous.port, &previous.behavior,
+      &previous.flavor);
+  if (ret != KERN_SUCCESS) {
+    TerminateMachExceptionHandlerThread();
+    mach_port_deallocate(task, current.port);
+    previous = {};
+    current = {};
+    return false;
+  }
+
+  // We should have info on the previous exception handler, even if it's null.
+  MOZ_ASSERT(previousCount == 1);
+
+  sExceptionHandlerInstalled = true;
+  return sExceptionHandlerInstalled;
+}
+
+void MemoryProtectionExceptionHandler::uninstall() {
+  if (sExceptionHandlerInstalled) {
+    MOZ_ASSERT(sMachExceptionState);
+
+    mach_port_t task = mach_task_self();
+
+    // Restore the previous exception handler.
+    MachExceptionParameters& previous = sMachExceptionState->previous;
+    task_set_exception_ports(task, previous.mask, previous.port,
+                             previous.behavior, previous.flavor);
+
+    TerminateMachExceptionHandlerThread();
+
+    // Release the Mach IPC port we used.
+    mach_port_deallocate(task, sMachExceptionState->current.port);
+
+    sMachExceptionState->current = {};
+    sMachExceptionState->previous = {};
+
+    js_delete(sMachExceptionState);
+    sMachExceptionState = nullptr;
+
+    sExceptionHandlerInstalled = false;
+  }
+}
+
+#else
+
+#  error "This platform is not supported!"
+
+#endif
+
+} /* namespace js */
diff --git a/js/src/ds/MemoryProtectionExceptionHandler.h b/js/src/ds/MemoryProtectionExceptionHandler.h
new file mode 100644
index 0000000000..c6ba7514ba
--- /dev/null
+++ b/js/src/ds/MemoryProtectionExceptionHandler.h
@@ -0,0 +1,44 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_MemoryProtectionExceptionHandler_h
+#define ds_MemoryProtectionExceptionHandler_h
+
+#include "jstypes.h"
+
+namespace js {
+
+/*
+ * This structure allows you to annotate crashes resulting from unauthorized
+ * access to protected memory in regions of interest, to make them stand out
+ * from other heap corruption crashes.
+ */
+
+struct MemoryProtectionExceptionHandler {
+  /* Installs the exception handler; called early during initialization. */
+  static bool install();
+
+  /* If the exception handler is disabled, it won't be installed. */
+  static bool isDisabled();
+
+  /*
+   * Marks a region of memory as important; if something tries to access this
+   * region in an unauthorized way (e.g. writing to read-only memory),
+   * the resulting crash will be annotated to stand out from other random
+   * heap corruption.
+   */
+  static void addRegion(void* addr, size_t size);
+
+  /* Removes a previously added region. */
+  static void removeRegion(void* addr);
+
+  /* Uninstalls the exception handler; called late during shutdown. */
+  static void uninstall();
+};
+
+} /* namespace js */
+
+#endif /* ds_MemoryProtectionExceptionHandler_h */
diff --git a/js/src/ds/Nestable.h b/js/src/ds/Nestable.h
new file mode 100644
index 0000000000..c27f7da534
--- /dev/null
+++ b/js/src/ds/Nestable.h
@@ -0,0 +1,63 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_Nestable_h
+#define ds_Nestable_h
+
+#include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
+
+namespace js {
+
+// A base class for nestable structures.
+template <typename Concrete>
+class MOZ_STACK_CLASS Nestable {
+  Concrete** stack_;
+  Concrete* enclosing_;
+
+ protected:
+  explicit Nestable(Concrete** stack) : stack_(stack), enclosing_(*stack) {
+    *stack_ = static_cast<Concrete*>(this);
+  }
+
+  // These method are protected. Some derived classes, such as ParseContext,
+  // do not expose the ability to walk the stack.
+  Concrete* enclosing() const { return enclosing_; }
+
+  template <typename Predicate /* (Concrete*) -> bool */>
+  static Concrete* findNearest(Concrete* it, Predicate predicate) {
+    while (it && !predicate(it)) {
+      it = it->enclosing();
+    }
+    return it;
+  }
+
+  template <typename T>
+  static T* findNearest(Concrete* it) {
+    while (it && !it->template is<T>()) {
+      it = it->enclosing();
+    }
+    return it ? &it->template as<T>() : nullptr;
+  }
+
+  template <typename T, typename Predicate /* (T*) -> bool */>
+  static T* findNearest(Concrete* it, Predicate predicate) {
+    while (it && (!it->template is<T>() || !predicate(&it->template as<T>()))) {
+      it = it->enclosing();
+    }
+    return it ? &it->template as<T>() : nullptr;
+  }
+
+ public:
+  ~Nestable() {
+    MOZ_ASSERT(*stack_ == static_cast<Concrete*>(this));
+    *stack_ = enclosing_;
+  }
+};
+
+}  // namespace js
+
+#endif /* ds_Nestable_h */
diff --git a/js/src/ds/OrderedHashTable.h b/js/src/ds/OrderedHashTable.h
new file mode 100644
index 0000000000..4044ee4d77
--- /dev/null
+++ b/js/src/ds/OrderedHashTable.h
@@ -0,0 +1,893 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_OrderedHashTable_h
+#define ds_OrderedHashTable_h
+
+/*
+ * Define two collection templates, js::OrderedHashMap and js::OrderedHashSet.
+ * They are like js::HashMap and js::HashSet except that:
+ *
+ *   - Iterating over an Ordered hash table visits the entries in the order in
+ *     which they were inserted. This means that unlike a HashMap, the behavior
+ *     of an OrderedHashMap is deterministic (as long as the HashPolicy methods
+ *     are effect-free and consistent); the hashing is a pure performance
+ *     optimization.
+ *
+ *   - Range objects over Ordered tables remain valid even when entries are
+ *     added or removed or the table is resized. (However in the case of
+ *     removing entries, note the warning on class Range below.)
+ *
+ *   - The API is a little different, so it's not a drop-in replacement.
+ *     In particular, the hash policy is a little different.
+ *     Also, the Ordered templates lack the Ptr and AddPtr types.
+ *
+ * Hash policies
+ *
+ * See the comment about "Hash policy" in HashTable.h for general features that
+ * hash policy classes must provide. Hash policies for OrderedHashMaps and Sets
+ * differ in that the hash() method takes an extra argument:
+ *     static js::HashNumber hash(Lookup, const HashCodeScrambler&);
+ * They must additionally provide a distinguished "empty" key value and the
+ * following static member functions:
+ *     bool isEmpty(const Key&);
+ *     void makeEmpty(Key*);
+ */
+
+#include "mozilla/HashFunctions.h"
+
+#include <utility>
+
+#include "js/HashTable.h"
+
+namespace js {
+
+namespace detail {
+
+/*
+ * detail::OrderedHashTable is the underlying data structure used to implement
+ * both OrderedHashMap and OrderedHashSet. Programs should use one of those two
+ * templates rather than OrderedHashTable.
+ */
+template <class T, class Ops, class AllocPolicy>
+class OrderedHashTable {
+ public:
+  using Key = typename Ops::KeyType;
+  using Lookup = typename Ops::Lookup;
+
+  struct Data {
+    T element;
+    Data* chain;
+
+    Data(const T& e, Data* c) : element(e), chain(c) {}
+    Data(T&& e, Data* c) : element(std::move(e)), chain(c) {}
+  };
+
+  class Range;
+  friend class Range;
+
+ private:
+  Data** hashTable;       // hash table (has hashBuckets() elements)
+  Data* data;             // data vector, an array of Data objects
+                          // data[0:dataLength] are constructed
+  uint32_t dataLength;    // number of constructed elements in data
+  uint32_t dataCapacity;  // size of data, in elements
+  uint32_t liveCount;     // dataLength less empty (removed) entries
+  uint32_t hashShift;     // multiplicative hash shift
+  Range* ranges;  // list of all live Ranges on this table in malloc memory
+  Range*
+      nurseryRanges;  // list of all live Ranges on this table in the GC nursery
+  AllocPolicy alloc;
+  mozilla::HashCodeScrambler hcs;  // don't reveal pointer hash codes
+
+  // TODO: This should be templated on a functor type and receive lambda
+  // arguments but this causes problems for the hazard analysis builds. See
+  // bug 1398213.
+  template <void (*f)(Range* range, uint32_t arg)>
+  void forEachRange(uint32_t arg = 0) {
+    Range* next;
+    for (Range* r = ranges; r; r = next) {
+      next = r->next;
+      f(r, arg);
+    }
+    for (Range* r = nurseryRanges; r; r = next) {
+      next = r->next;
+      f(r, arg);
+    }
+  }
+
+ public:
+  OrderedHashTable(AllocPolicy ap, mozilla::HashCodeScrambler hcs)
+      : hashTable(nullptr),
+        data(nullptr),
+        dataLength(0),
+        dataCapacity(0),
+        liveCount(0),
+        hashShift(0),
+        ranges(nullptr),
+        nurseryRanges(nullptr),
+        alloc(std::move(ap)),
+        hcs(hcs) {}
+
+  MOZ_MUST_USE bool init() {
+    MOZ_ASSERT(!hashTable, "init must be called at most once");
+
+    uint32_t buckets = initialBuckets();
+    Data** tableAlloc = alloc.template pod_malloc<Data*>(buckets);
+    if (!tableAlloc) {
+      return false;
+    }
+    for (uint32_t i = 0; i < buckets; i++) {
+      tableAlloc[i] = nullptr;
+    }
+
+    uint32_t capacity = uint32_t(buckets * fillFactor());
+    Data* dataAlloc = alloc.template pod_malloc<Data>(capacity);
+    if (!dataAlloc) {
+      alloc.free_(tableAlloc, buckets);
+      return false;
+    }
+
+    // clear() requires that members are assigned only after all allocation
+    // has succeeded, and that this->ranges is left untouched.
+    hashTable = tableAlloc;
+    data = dataAlloc;
+    dataLength = 0;
+    dataCapacity = capacity;
+    liveCount = 0;
+    hashShift = js::kHashNumberBits - initialBucketsLog2();
+    MOZ_ASSERT(hashBuckets() == buckets);
+    return true;
+  }
+
+  ~OrderedHashTable() {
+    forEachRange<Range::onTableDestroyed>();
+    if (hashTable) {
+      // |hashBuckets()| isn't valid when |hashTable| hasn't been created.
+      alloc.free_(hashTable, hashBuckets());
+    }
+    freeData(data, dataLength, dataCapacity);
+  }
+
+  /* Return the number of elements in the table. */
+  uint32_t count() const { return liveCount; }
+
+  /* True if any element matches l. */
+  bool has(const Lookup& l) const { return lookup(l) != nullptr; }
+
+  /* Return a pointer to the element, if any, that matches l, or nullptr. */
+  T* get(const Lookup& l) {
+    Data* e = lookup(l, prepareHash(l));
+    return e ? &e->element : nullptr;
+  }
+
+  /* Return a pointer to the element, if any, that matches l, or nullptr. */
+  const T* get(const Lookup& l) const {
+    return const_cast<OrderedHashTable*>(this)->get(l);
+  }
+
+  /*
+   * If the table already contains an entry that matches |element|,
+   * replace that entry with |element|. Otherwise add a new entry.
+   *
+   * On success, return true, whether there was already a matching element or
+   * not. On allocation failure, return false. If this returns false, it
+   * means the element was not added to the table.
+   */
+  template <typename ElementInput>
+  MOZ_MUST_USE bool put(ElementInput&& element) {
+    HashNumber h = prepareHash(Ops::getKey(element));
+    if (Data* e = lookup(Ops::getKey(element), h)) {
+      e->element = std::forward<ElementInput>(element);
+      return true;
+    }
+
+    if (dataLength == dataCapacity) {
+      // If the hashTable is more than 1/4 deleted data, simply rehash in
+      // place to free up some space. Otherwise, grow the table.
+      uint32_t newHashShift =
+          liveCount >= dataCapacity * 0.75 ? hashShift - 1 : hashShift;
+      if (!rehash(newHashShift)) {
+        return false;
+      }
+    }
+
+    h >>= hashShift;
+    liveCount++;
+    Data* e = &data[dataLength++];
+    new (e) Data(std::forward<ElementInput>(element), hashTable[h]);
+    hashTable[h] = e;
+    return true;
+  }
+
+  /*
+   * If the table contains an element matching l, remove it and set *foundp
+   * to true. Otherwise set *foundp to false.
+   *
+   * Return true on success, false if we tried to shrink the table and hit an
+   * allocation failure. Even if this returns false, *foundp is set correctly
+   * and the matching element was removed. Shrinking is an optimization and
+   * it's OK for it to fail.
+   */
+  bool remove(const Lookup& l, bool* foundp) {
+    // Note: This could be optimized so that removing the last entry,
+    // data[dataLength - 1], decrements dataLength. LIFO use cases would
+    // benefit.
+
+    // If a matching entry exists, empty it.
+    Data* e = lookup(l, prepareHash(l));
+    if (e == nullptr) {
+      *foundp = false;
+      return true;
+    }
+
+    *foundp = true;
+    liveCount--;
+    Ops::makeEmpty(&e->element);
+
+    // Update active Ranges.
+    uint32_t pos = e - data;
+    forEachRange<&Range::onRemove>(pos);
+
+    // If many entries have been removed, try to shrink the table.
+    if (hashBuckets() > initialBuckets() &&
+        liveCount < dataLength * minDataFill()) {
+      if (!rehash(hashShift + 1)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /*
+   * Remove all entries.
+   *
+   * Returns false on OOM, leaving the OrderedHashTable and any live Ranges
+   * in the old state.
+   *
+   * The effect on live Ranges is the same as removing all entries; in
+   * particular, those Ranges are still live and will see any entries added
+   * after a successful clear().
+   */
+  MOZ_MUST_USE bool clear() {
+    if (dataLength != 0) {
+      Data** oldHashTable = hashTable;
+      Data* oldData = data;
+      uint32_t oldHashBuckets = hashBuckets();
+      uint32_t oldDataLength = dataLength;
+      uint32_t oldDataCapacity = dataCapacity;
+
+      hashTable = nullptr;
+      if (!init()) {
+        // init() only mutates members on success; see comment above.
+        hashTable = oldHashTable;
+        return false;
+      }
+
+      alloc.free_(oldHashTable, oldHashBuckets);
+      freeData(oldData, oldDataLength, oldDataCapacity);
+      forEachRange<&Range::onClear>();
+    }
+
+    MOZ_ASSERT(hashTable);
+    MOZ_ASSERT(data);
+    MOZ_ASSERT(dataLength == 0);
+    MOZ_ASSERT(liveCount == 0);
+    return true;
+  }
+
+  /*
+   * Ranges are used to iterate over OrderedHashTables.
+   *
+   * Suppose 'Map' is some instance of OrderedHashMap, and 'map' is a Map.
+   * Then you can walk all the key-value pairs like this:
+   *
+   *     for (Map::Range r = map.all(); !r.empty(); r.popFront()) {
+   *         Map::Entry& pair = r.front();
+   *         ... do something with pair ...
+   *     }
+   *
+   * Ranges remain valid for the lifetime of the OrderedHashTable, even if
+   * entries are added or removed or the table is resized. Don't do anything
+   * to a Range, except destroy it, after the OrderedHashTable has been
+   * destroyed. (We support destroying the two objects in either order to
+   * humor the GC, bless its nondeterministic heart.)
+   *
+   * Warning: The behavior when the current front() entry is removed from the
+   * table is subtly different from js::HashTable<>::Enum::removeFront()!
+   * HashTable::Enum doesn't skip any entries when you removeFront() and then
+   * popFront(). OrderedHashTable::Range does! (This is useful for using a
+   * Range to implement JS Map.prototype.iterator.)
+   *
+   * The workaround is to call popFront() as soon as possible,
+   * before there's any possibility of modifying the table:
+   *
+   *     for (Map::Range r = map.all(); !r.empty(); ) {
+   *         Key key = r.front().key;         // this won't modify map
+   *         Value val = r.front().value;     // this won't modify map
+   *         r.popFront();
+   *         // ...do things that might modify map...
+   *     }
+   */
+  class Range {
+    friend class OrderedHashTable;
+
+    // Cannot be a reference since we need to be able to do
+    // |offsetof(Range, ht)|.
+    OrderedHashTable* ht;
+
+    /* The index of front() within ht->data. */
+    uint32_t i;
+
+    /*
+     * The number of nonempty entries in ht->data to the left of front().
+     * This is used when the table is resized or compacted.
+     */
+    uint32_t count;
+
+    /*
+     * Links in the doubly-linked list of active Ranges on ht.
+     *
+     * prevp points to the previous Range's .next field;
+     *   or to ht->ranges if this is the first Range in the list.
+     * next points to the next Range;
+     *   or nullptr if this is the last Range in the list.
+     *
+     * Invariant: *prevp == this.
+     */
+    Range** prevp;
+    Range* next;
+
+    /*
+     * Create a Range over all the entries in ht.
+     * (This is private on purpose. End users must use ht->all().)
+     */
+    Range(OrderedHashTable* ht, Range** listp)
+        : ht(ht), i(0), count(0), prevp(listp), next(*listp) {
+      *prevp = this;
+      if (next) {
+        next->prevp = &next;
+      }
+      seek();
+    }
+
+   public:
+    Range(const Range& other)
+        : ht(other.ht),
+          i(other.i),
+          count(other.count),
+          prevp(&ht->ranges),
+          next(ht->ranges) {
+      *prevp = this;
+      if (next) {
+        next->prevp = &next;
+      }
+    }
+
+    ~Range() {
+      *prevp = next;
+      if (next) {
+        next->prevp = prevp;
+      }
+    }
+
+   private:
+    // Prohibit copy assignment.
+    Range& operator=(const Range& other) = delete;
+
+    void seek() {
+      while (i < ht->dataLength &&
+             Ops::isEmpty(Ops::getKey(ht->data[i].element))) {
+        i++;
+      }
+    }
+
+    /*
+     * The hash table calls this when an entry is removed.
+     * j is the index of the removed entry.
+     */
+    void onRemove(uint32_t j) {
+      MOZ_ASSERT(valid());
+      if (j < i) {
+        count--;
+      }
+      if (j == i) {
+        seek();
+      }
+    }
+
+    /*
+     * The hash table calls this when the table is resized or compacted.
+     * Since |count| is the number of nonempty entries to the left of
+     * front(), discarding the empty entries will not affect count, and it
+     * will make i and count equal.
+     */
+    void onCompact() {
+      MOZ_ASSERT(valid());
+      i = count;
+    }
+
+    /* The hash table calls this when cleared. */
+    void onClear() {
+      MOZ_ASSERT(valid());
+      i = count = 0;
+    }
+
+    bool valid() const { return next != this; }
+
+    void onTableDestroyed() {
+      MOZ_ASSERT(valid());
+      prevp = &next;
+      next = this;
+    }
+
+   public:
+    bool empty() const {
+      MOZ_ASSERT(valid());
+      return i >= ht->dataLength;
+    }
+
+    /*
+     * Return the first element in the range. This must not be called if
+     * this->empty().
+     *
+     * Warning: Removing an entry from the table also removes it from any
+     * live Ranges, and a Range can become empty that way, rendering
+     * front() invalid. If in doubt, check empty() before calling front().
+     */
+    T& front() {
+      MOZ_ASSERT(valid());
+      MOZ_ASSERT(!empty());
+      return ht->data[i].element;
+    }
+
+    /*
+     * Remove the first element from this range.
+     * This must not be called if this->empty().
+     *
+     * Warning: Removing an entry from the table also removes it from any
+     * live Ranges, and a Range can become empty that way, rendering
+     * popFront() invalid. If in doubt, check empty() before calling
+     * popFront().
+     */
+    void popFront() {
+      MOZ_ASSERT(valid());
+      MOZ_ASSERT(!empty());
+      MOZ_ASSERT(!Ops::isEmpty(Ops::getKey(ht->data[i].element)));
+      count++;
+      i++;
+      seek();
+    }
+
+    /*
+     * Change the key of the front entry.
+     *
+     * This calls Ops::hash on both the current key and the new key.
+     * Ops::hash on the current key must return the same hash code as
+     * when the entry was added to the table.
+     */
+    void rekeyFront(const Key& k) {
+      MOZ_ASSERT(valid());
+      Data& entry = ht->data[i];
+      HashNumber oldHash =
+          ht->prepareHash(Ops::getKey(entry.element)) >> ht->hashShift;
+      HashNumber newHash = ht->prepareHash(k) >> ht->hashShift;
+      Ops::setKey(entry.element, k);
+      if (newHash != oldHash) {
+        // Remove this entry from its old hash chain. (If this crashes
+        // reading nullptr, it would mean we did not find this entry on
+        // the hash chain where we expected it. That probably means the
+        // key's hash code changed since it was inserted, breaking the
+        // hash code invariant.)
+        Data** ep = &ht->hashTable[oldHash];
+        while (*ep != &entry) {
+          ep = &(*ep)->chain;
+        }
+        *ep = entry.chain;
+
+        // Add it to the new hash chain. We could just insert it at the
+        // beginning of the chain. Instead, we do a bit of work to
+        // preserve the invariant that hash chains always go in reverse
+        // insertion order (descending memory order). No code currently
+        // depends on this invariant, so it's fine to kill it if
+        // needed.
+        ep = &ht->hashTable[newHash];
+        while (*ep && *ep > &entry) {
+          ep = &(*ep)->chain;
+        }
+        entry.chain = *ep;
+        *ep = &entry;
+      }
+    }
+
+    static size_t offsetOfHashTable() { return offsetof(Range, ht); }
+    static size_t offsetOfI() { return offsetof(Range, i); }
+    static size_t offsetOfCount() { return offsetof(Range, count); }
+    static size_t offsetOfPrevP() { return offsetof(Range, prevp); }
+    static size_t offsetOfNext() { return offsetof(Range, next); }
+
+    static void onTableDestroyed(Range* range, uint32_t arg) {
+      range->onTableDestroyed();
+    }
+    static void onRemove(Range* range, uint32_t arg) { range->onRemove(arg); }
+    static void onClear(Range* range, uint32_t arg) { range->onClear(); }
+    static void onCompact(Range* range, uint32_t arg) { range->onCompact(); }
+  };
+
+  Range all() { return Range(this, &ranges); }
+
+  /*
+   * Allocate a new Range, possibly in nursery memory. The buffer must be
+   * large enough to hold a Range object.
+   *
+   * All nursery-allocated ranges can be freed in one go by calling
+   * destroyNurseryRanges().
+   */
+  Range* createRange(void* buffer, bool inNursery) {
+    auto range = static_cast<Range*>(buffer);
+    new (range) Range(this, inNursery ? &nurseryRanges : &ranges);
+    return range;
+  }
+
+  void destroyNurseryRanges() { nurseryRanges = nullptr; }
+
+  /*
+   * Change the value of the given key.
+   *
+   * This calls Ops::hash on both the current key and the new key.
+   * Ops::hash on the current key must return the same hash code as
+   * when the entry was added to the table.
+   */
+  void rekeyOneEntry(const Key& current, const Key& newKey, const T& element) {
+    if (current == newKey) {
+      return;
+    }
+
+    Data* entry = lookup(current, prepareHash(current));
+    if (!entry) {
+      return;
+    }
+
+    HashNumber oldHash = prepareHash(current) >> hashShift;
+    HashNumber newHash = prepareHash(newKey) >> hashShift;
+
+    entry->element = element;
+
+    // Remove this entry from its old hash chain. (If this crashes
+    // reading nullptr, it would mean we did not find this entry on
+    // the hash chain where we expected it. That probably means the
+    // key's hash code changed since it was inserted, breaking the
+    // hash code invariant.)
+    Data** ep = &hashTable[oldHash];
+    while (*ep != entry) {
+      ep = &(*ep)->chain;
+    }
+    *ep = entry->chain;
+
+    // Add it to the new hash chain. We could just insert it at the
+    // beginning of the chain. Instead, we do a bit of work to
+    // preserve the invariant that hash chains always go in reverse
+    // insertion order (descending memory order). No code currently
+    // depends on this invariant, so it's fine to kill it if
+    // needed.
+    ep = &hashTable[newHash];
+    while (*ep && *ep > entry) {
+      ep = &(*ep)->chain;
+    }
+    entry->chain = *ep;
+    *ep = entry;
+  }
+
+  static size_t offsetOfDataLength() {
+    return offsetof(OrderedHashTable, dataLength);
+  }
+  static size_t offsetOfData() { return offsetof(OrderedHashTable, data); }
+  static constexpr size_t offsetOfDataElement() {
+    static_assert(offsetof(Data, element) == 0,
+                  "RangeFront and RangePopFront depend on offsetof(Data, "
+                  "element) being 0");
+    return offsetof(Data, element);
+  }
+  static constexpr size_t sizeofData() { return sizeof(Data); }
+
+ private:
+  /* Logarithm base 2 of the number of buckets in the hash table initially. */
+  static uint32_t initialBucketsLog2() { return 1; }
+  static uint32_t initialBuckets() { return 1 << initialBucketsLog2(); }
+
+  /*
+   * The maximum load factor (mean number of entries per bucket).
+   * It is an invariant that
+   *     dataCapacity == floor(hashBuckets() * fillFactor()).
+   *
+   * The fill factor should be between 2 and 4, and it should be chosen so that
+   * the fill factor times sizeof(Data) is close to but <= a power of 2.
+   * This fixed fill factor was chosen to make the size of the data
+   * array, in bytes, close to a power of two when sizeof(T) is 16.
+   */
+  static double fillFactor() { return 8.0 / 3.0; }
+
+  /*
+   * The minimum permitted value of (liveCount / dataLength).
+   * If that ratio drops below this value, we shrink the table.
+   */
+  static double minDataFill() { return 0.25; }
+
+ public:
+  HashNumber prepareHash(const Lookup& l) const {
+    return mozilla::ScrambleHashCode(Ops::hash(l, hcs));
+  }
+
+ private:
+  /* The size of hashTable, in elements. Always a power of two. */
+  uint32_t hashBuckets() const {
+    return 1 << (js::kHashNumberBits - hashShift);
+  }
+
+  static void destroyData(Data* data, uint32_t length) {
+    for (Data* p = data + length; p != data;) {
+      (--p)->~Data();
+    }
+  }
+
+  void freeData(Data* data, uint32_t length, uint32_t capacity) {
+    destroyData(data, length);
+    alloc.free_(data, capacity);
+  }
+
+  Data* lookup(const Lookup& l, HashNumber h) {
+    for (Data* e = hashTable[h >> hashShift]; e; e = e->chain) {
+      if (Ops::match(Ops::getKey(e->element), l)) {
+        return e;
+      }
+    }
+    return nullptr;
+  }
+
+  const Data* lookup(const Lookup& l) const {
+    return const_cast<OrderedHashTable*>(this)->lookup(l, prepareHash(l));
+  }
+
+  /* This is called after rehashing the table. */
+  void compacted() {
+    // If we had any empty entries, compacting may have moved live entries
+    // to the left within |data|. Notify all live Ranges of the change.
+    forEachRange<&Range::onCompact>();
+  }
+
+  /* Compact the entries in |data| and rehash them. */
+  void rehashInPlace() {
+    for (uint32_t i = 0, N = hashBuckets(); i < N; i++) {
+      hashTable[i] = nullptr;
+    }
+    Data* wp = data;
+    Data* end = data + dataLength;
+    for (Data* rp = data; rp != end; rp++) {
+      if (!Ops::isEmpty(Ops::getKey(rp->element))) {
+        HashNumber h = prepareHash(Ops::getKey(rp->element)) >> hashShift;
+        if (rp != wp) {
+          wp->element = std::move(rp->element);
+        }
+        wp->chain = hashTable[h];
+        hashTable[h] = wp;
+        wp++;
+      }
+    }
+    MOZ_ASSERT(wp == data + liveCount);
+
+    while (wp != end) {
+      (--end)->~Data();
+    }
+    dataLength = liveCount;
+    compacted();
+  }
+
+  /*
+   * Grow, shrink, or compact both |hashTable| and |data|.
+   *
+   * On success, this returns true, dataLength == liveCount, and there are no
+   * empty elements in data[0:dataLength]. On allocation failure, this
+   * leaves everything as it was and returns false.
+   */
+  MOZ_MUST_USE bool rehash(uint32_t newHashShift) {
+    // If the size of the table is not changing, rehash in place to avoid
+    // allocating memory.
+    if (newHashShift == hashShift) {
+      rehashInPlace();
+      return true;
+    }
+
+    size_t newHashBuckets = size_t(1) << (js::kHashNumberBits - newHashShift);
+    Data** newHashTable = alloc.template pod_malloc<Data*>(newHashBuckets);
+    if (!newHashTable) {
+      return false;
+    }
+    for (uint32_t i = 0; i < newHashBuckets; i++) {
+      newHashTable[i] = nullptr;
+    }
+
+    uint32_t newCapacity = uint32_t(newHashBuckets * fillFactor());
+    Data* newData = alloc.template pod_malloc<Data>(newCapacity);
+    if (!newData) {
+      alloc.free_(newHashTable, newHashBuckets);
+      return false;
+    }
+
+    Data* wp = newData;
+    Data* end = data + dataLength;
+    for (Data* p = data; p != end; p++) {
+      if (!Ops::isEmpty(Ops::getKey(p->element))) {
+        HashNumber h = prepareHash(Ops::getKey(p->element)) >> newHashShift;
+        new (wp) Data(std::move(p->element), newHashTable[h]);
+        newHashTable[h] = wp;
+        wp++;
+      }
+    }
+    MOZ_ASSERT(wp == newData + liveCount);
+
+    alloc.free_(hashTable, hashBuckets());
+    freeData(data, dataLength, dataCapacity);
+
+    hashTable = newHashTable;
+    data = newData;
+    dataLength = liveCount;
+    dataCapacity = newCapacity;
+    hashShift = newHashShift;
+    MOZ_ASSERT(hashBuckets() == newHashBuckets);
+
+    compacted();
+    return true;
+  }
+
+  // Not copyable.
+  OrderedHashTable& operator=(const OrderedHashTable&) = delete;
+  OrderedHashTable(const OrderedHashTable&) = delete;
+};
+
+}  // namespace detail
+
+template <class Key, class Value, class OrderedHashPolicy, class AllocPolicy>
+class OrderedHashMap {
+ public:
+  class Entry {
+    template <class, class, class>
+    friend class detail::OrderedHashTable;
+    void operator=(const Entry& rhs) {
+      const_cast<Key&>(key) = rhs.key;
+      value = rhs.value;
+    }
+
+    void operator=(Entry&& rhs) {
+      MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
+      const_cast<Key&>(key) = std::move(rhs.key);
+      value = std::move(rhs.value);
+    }
+
+   public:
+    Entry() : key(), value() {}
+    template <typename V>
+    Entry(const Key& k, V&& v) : key(k), value(std::forward<V>(v)) {}
+    Entry(Entry&& rhs) : key(std::move(rhs.key)), value(std::move(rhs.value)) {}
+
+    const Key key;
+    Value value;
+
+    static size_t offsetOfKey() { return offsetof(Entry, key); }
+    static size_t offsetOfValue() { return offsetof(Entry, value); }
+  };
+
+ private:
+  struct MapOps : OrderedHashPolicy {
+    using KeyType = Key;
+    static void makeEmpty(Entry* e) {
+      OrderedHashPolicy::makeEmpty(const_cast<Key*>(&e->key));
+
+      // Clear the value. Destroying it is another possibility, but that
+      // would complicate class Entry considerably.
+      e->value = Value();
+    }
+    static const Key& getKey(const Entry& e) { return e.key; }
+    static void setKey(Entry& e, const Key& k) { const_cast<Key&>(e.key) = k; }
+  };
+
+  typedef detail::OrderedHashTable<Entry, MapOps, AllocPolicy> Impl;
+  Impl impl;
+
+ public:
+  using Range = typename Impl::Range;
+
+  OrderedHashMap(AllocPolicy ap, mozilla::HashCodeScrambler hcs)
+      : impl(std::move(ap), hcs) {}
+  MOZ_MUST_USE bool init() { return impl.init(); }
+  uint32_t count() const { return impl.count(); }
+  bool has(const Key& key) const { return impl.has(key); }
+  Range all() { return impl.all(); }
+  const Entry* get(const Key& key) const { return impl.get(key); }
+  Entry* get(const Key& key) { return impl.get(key); }
+  bool remove(const Key& key, bool* foundp) { return impl.remove(key, foundp); }
+  MOZ_MUST_USE bool clear() { return impl.clear(); }
+
+  template <typename V>
+  MOZ_MUST_USE bool put(const Key& key, V&& value) {
+    return impl.put(Entry(key, std::forward<V>(value)));
+  }
+
+  HashNumber hash(const Key& key) const { return impl.prepareHash(key); }
+
+  void rekeyOneEntry(const Key& current, const Key& newKey) {
+    const Entry* e = get(current);
+    if (!e) {
+      return;
+    }
+    return impl.rekeyOneEntry(current, newKey, Entry(newKey, e->value));
+  }
+
+  Range* createRange(void* buffer, bool inNursery) {
+    return impl.createRange(buffer, inNursery);
+  }
+
+  void destroyNurseryRanges() { impl.destroyNurseryRanges(); }
+
+  static size_t offsetOfEntryKey() { return Entry::offsetOfKey(); }
+  static size_t offsetOfImplDataLength() { return Impl::offsetOfDataLength(); }
+  static size_t offsetOfImplData() { return Impl::offsetOfData(); }
+  static constexpr size_t offsetOfImplDataElement() {
+    return Impl::offsetOfDataElement();
+  }
+  static constexpr size_t sizeofImplData() { return Impl::sizeofData(); }
+};
+
+template <class T, class OrderedHashPolicy, class AllocPolicy>
+class OrderedHashSet {
+ private:
+  struct SetOps : OrderedHashPolicy {
+    using KeyType = const T;
+    static const T& getKey(const T& v) { return v; }
+    static void setKey(const T& e, const T& v) { const_cast<T&>(e) = v; }
+  };
+
+  typedef detail::OrderedHashTable<T, SetOps, AllocPolicy> Impl;
+  Impl impl;
+
+ public:
+  using Range = typename Impl::Range;
+
+  explicit OrderedHashSet(AllocPolicy ap, mozilla::HashCodeScrambler hcs)
+      : impl(std::move(ap), hcs) {}
+  MOZ_MUST_USE bool init() { return impl.init(); }
+  uint32_t count() const { return impl.count(); }
+  bool has(const T& value) const { return impl.has(value); }
+  Range all() { return impl.all(); }
+  MOZ_MUST_USE bool put(const T& value) { return impl.put(value); }
+  bool remove(const T& value, bool* foundp) {
+    return impl.remove(value, foundp);
+  }
+  MOZ_MUST_USE bool clear() { return impl.clear(); }
+
+  HashNumber hash(const T& value) const { return impl.prepareHash(value); }
+
+  void rekeyOneEntry(const T& current, const T& newKey) {
+    return impl.rekeyOneEntry(current, newKey, newKey);
+  }
+
+  Range* createRange(void* buffer, bool inNursery) {
+    return impl.createRange(buffer, inNursery);
+  }
+
+  void destroyNurseryRanges() { impl.destroyNurseryRanges(); }
+
+  static size_t offsetOfEntryKey() { return 0; }
+  static size_t offsetOfImplDataLength() { return Impl::offsetOfDataLength(); }
+  static size_t offsetOfImplData() { return Impl::offsetOfData(); }
+  static constexpr size_t offsetOfImplDataElement() {
+    return Impl::offsetOfDataElement();
+  }
+  static constexpr size_t sizeofImplData() { return Impl::sizeofData(); }
+};
+
+}  // namespace js
+
+#endif /* ds_OrderedHashTable_h */
diff --git a/js/src/ds/PageProtectingVector.h b/js/src/ds/PageProtectingVector.h
new file mode 100644
index 0000000000..f7c4911db2
--- /dev/null
+++ b/js/src/ds/PageProtectingVector.h
@@ -0,0 +1,502 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_PageProtectingVector_h
+#define ds_PageProtectingVector_h
+
+#include "mozilla/Atomics.h"
+#include "mozilla/IntegerPrintfMacros.h"
+#include "mozilla/PodOperations.h"
+#include "mozilla/Types.h"
+#include "mozilla/Vector.h"
+
+#include "ds/MemoryProtectionExceptionHandler.h"
+#include "gc/Memory.h"
+
+namespace js {
+
+/*
+ * PageProtectingVector is a vector that can only grow or be cleared, restricts
+ * access to memory pages that haven't been used yet, and marks all of its fully
+ * used memory pages as read-only. It can be used to detect heap corruption in
+ * important buffers, since anything that tries to write into its protected
+ * pages will crash. On Nightly and Aurora, these crashes will additionally be
+ * annotated with a moz crash reason using MemoryProtectionExceptionHandler.
+ *
+ * PageProtectingVector's protection is limited to full pages. If the front
+ * of its buffer is not aligned on a page boundary, elems preceding the first
+ * page boundary will not be protected. Similarly, the end of the buffer will
+ * not be fully protected unless it is aligned on a page boundary. Altogether,
+ * up to two pages of memory may not be protected.
+ */
+template <typename T, size_t MinInlineCapacity = 0,
+          class AllocPolicy = mozilla::MallocAllocPolicy,
+          bool ProtectUsed = true, bool ProtectUnused = true,
+          size_t InitialLowerBound = 0, bool PoisonUnused = true,
+          uint8_t PoisonPattern = 0xe3>
+class PageProtectingVector final {
+  mozilla::Vector<T, MinInlineCapacity, AllocPolicy> vector;
+
+  static constexpr size_t toShift(size_t v) {
+    return v <= 1 ? 0 : 1 + toShift(v >> 1);
+  }
+
+  static_assert(
+      (sizeof(T) & (sizeof(T) - 1)) == 0,
+      "For performance reasons, "
+      "PageProtectingVector only works with power-of-2 sized elements!");
+
+  static const size_t elemShift = toShift(sizeof(T));
+  static const size_t elemSize = 1 << elemShift;
+  static const size_t elemMask = elemSize - 1;
+
+  /* We hardcode the page size here to minimize administrative overhead. */
+  static const size_t pageShift = 12;
+  static const size_t pageSize = 1 << pageShift;
+  static const size_t pageMask = pageSize - 1;
+
+  /*
+   * The number of elements that can be added before we need to either adjust
+   * the active page or resize the buffer. If |elemsUntilTest < 0| we will
+   * take the slow paths in the append calls.
+   */
+  intptr_t elemsUntilTest;
+
+  /*
+   * The offset of the currently 'active' page - that is, the page that is
+   * currently being written to. If both used and unused bytes are protected,
+   * this will be the only (fully owned) page with read and write access.
+   */
+  size_t currPage;
+
+  /*
+   * The first fully owned page. This is the first page that can
+   * be protected, but it may not be the first *active* page.
+   */
+  size_t initPage;
+
+  /*
+   * The last fully owned page. This is the last page that can
+   * be protected, but it may not be the last *active* page.
+   */
+  size_t lastPage;
+
+  /*
+   * The size in elems that a buffer needs to be before its pages will be
+   * protected. This is intended to reduce churn for small vectors while
+   * still offering protection when they grow large enough.
+   */
+  size_t lowerBound;
+
+#ifdef DEBUG
+  bool regionUnprotected;
+#endif
+
+  bool usable;
+  bool enabled;
+  bool protectUsedEnabled;
+  bool protectUnusedEnabled;
+
+  MOZ_ALWAYS_INLINE void resetTest() {
+    MOZ_ASSERT(protectUsedEnabled || protectUnusedEnabled);
+    size_t nextPage =
+        (pageSize - (uintptr_t(begin() + length()) & pageMask)) >> elemShift;
+    size_t nextResize = capacity() - length();
+    if (MOZ_LIKELY(nextPage <= nextResize)) {
+      elemsUntilTest = intptr_t(nextPage);
+    } else {
+      elemsUntilTest = intptr_t(nextResize);
+    }
+  }
+
+  MOZ_ALWAYS_INLINE void setTestInitial() {
+    if (MOZ_LIKELY(!protectUsedEnabled && !protectUnusedEnabled)) {
+      elemsUntilTest = intptr_t(capacity() - length());
+    } else {
+      resetTest();
+    }
+  }
+
+  MOZ_ALWAYS_INLINE void resetForNewBuffer() {
+    initPage = (uintptr_t(begin() - 1) >> pageShift) + 1;
+    currPage = (uintptr_t(begin() + length()) >> pageShift);
+    lastPage = (uintptr_t(begin() + capacity()) >> pageShift) - 1;
+    protectUsedEnabled =
+        ProtectUsed && usable && enabled && initPage <= lastPage &&
+        (uintptr_t(begin()) & elemMask) == 0 && capacity() >= lowerBound;
+    protectUnusedEnabled =
+        ProtectUnused && usable && enabled && initPage <= lastPage &&
+        (uintptr_t(begin()) & elemMask) == 0 && capacity() >= lowerBound;
+    setTestInitial();
+  }
+
+  MOZ_ALWAYS_INLINE void poisonNewBuffer() {
+    if (!PoisonUnused) {
+      return;
+    }
+    T* addr = begin() + length();
+    size_t toPoison = (capacity() - length()) * sizeof(T);
+    memset(addr, PoisonPattern, toPoison);
+  }
+
+  MOZ_ALWAYS_INLINE void addExceptionHandler() {
+    if (MOZ_UNLIKELY(protectUsedEnabled || protectUnusedEnabled)) {
+      MemoryProtectionExceptionHandler::addRegion(begin(), capacity()
+                                                               << elemShift);
+    }
+  }
+
+  MOZ_ALWAYS_INLINE void removeExceptionHandler() {
+    if (MOZ_UNLIKELY(protectUsedEnabled || protectUnusedEnabled)) {
+      MemoryProtectionExceptionHandler::removeRegion(begin());
+    }
+  }
+
+  MOZ_ALWAYS_INLINE void protectUsed() {
+    if (MOZ_LIKELY(!protectUsedEnabled)) {
+      return;
+    }
+    if (MOZ_UNLIKELY(currPage <= initPage)) {
+      return;
+    }
+    T* addr = reinterpret_cast<T*>(initPage << pageShift);
+    size_t size = (currPage - initPage) << pageShift;
+    gc::MakePagesReadOnly(addr, size);
+  }
+
+  MOZ_ALWAYS_INLINE void unprotectUsed() {
+    if (MOZ_LIKELY(!protectUsedEnabled)) {
+      return;
+    }
+    if (MOZ_UNLIKELY(currPage <= initPage)) {
+      return;
+    }
+    T* addr = reinterpret_cast<T*>(initPage << pageShift);
+    size_t size = (currPage - initPage) << pageShift;
+    gc::UnprotectPages(addr, size);
+  }
+
+  MOZ_ALWAYS_INLINE void protectUnused() {
+    if (MOZ_LIKELY(!protectUnusedEnabled)) {
+      return;
+    }
+    if (MOZ_UNLIKELY(currPage >= lastPage)) {
+      return;
+    }
+    T* addr = reinterpret_cast<T*>((currPage + 1) << pageShift);
+    size_t size = (lastPage - currPage) << pageShift;
+    gc::ProtectPages(addr, size);
+  }
+
+  MOZ_ALWAYS_INLINE void unprotectUnused() {
+    if (MOZ_LIKELY(!protectUnusedEnabled)) {
+      return;
+    }
+    if (MOZ_UNLIKELY(currPage >= lastPage)) {
+      return;
+    }
+    T* addr = reinterpret_cast<T*>((currPage + 1) << pageShift);
+    size_t size = (lastPage - currPage) << pageShift;
+    gc::UnprotectPages(addr, size);
+  }
+
+  MOZ_ALWAYS_INLINE void protectNewBuffer() {
+    resetForNewBuffer();
+    addExceptionHandler();
+    poisonNewBuffer();
+    protectUsed();
+    protectUnused();
+  }
+
+  MOZ_ALWAYS_INLINE void unprotectOldBuffer() {
+    MOZ_ASSERT(!regionUnprotected);
+    unprotectUnused();
+    unprotectUsed();
+    removeExceptionHandler();
+  }
+
+  MOZ_ALWAYS_INLINE void protectUnusedPartial(size_t curr, size_t next) {
+    if (MOZ_LIKELY(!protectUnusedEnabled)) {
+      return;
+    }
+    if (MOZ_UNLIKELY(next > lastPage)) {
+      --next;
+    }
+    if (MOZ_UNLIKELY(next == curr)) {
+      return;
+    }
+    void* addr = reinterpret_cast<T*>((curr + 1) << pageShift);
+    size_t size = (next - curr) << pageShift;
+    gc::ProtectPages(addr, size);
+  }
+
+  MOZ_ALWAYS_INLINE void unprotectUnusedPartial(size_t curr, size_t next) {
+    if (MOZ_LIKELY(!protectUnusedEnabled)) {
+      return;
+    }
+    if (MOZ_UNLIKELY(next > lastPage)) {
+      --next;
+    }
+    if (MOZ_UNLIKELY(next == curr)) {
+      return;
+    }
+    void* addr = reinterpret_cast<T*>((curr + 1) << pageShift);
+    size_t size = (next - curr) << pageShift;
+    gc::UnprotectPages(addr, size);
+  }
+
+  MOZ_ALWAYS_INLINE void protectUsedPartial(size_t curr, size_t next) {
+    if (MOZ_LIKELY(!protectUsedEnabled)) {
+      return;
+    }
+    if (MOZ_UNLIKELY(curr < initPage)) {
+      ++curr;
+    }
+    if (MOZ_UNLIKELY(next == curr)) {
+      return;
+    }
+    void* addr = reinterpret_cast<T*>(curr << pageShift);
+    size_t size = (next - curr) << pageShift;
+    gc::MakePagesReadOnly(addr, size);
+  }
+
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool reserveNewBuffer(size_t size) {
+    unprotectOldBuffer();
+    bool ret = vector.reserve(size);
+    protectNewBuffer();
+    return ret;
+  }
+
+  template <typename U>
+  MOZ_ALWAYS_INLINE void infallibleAppendNewPage(const U* values, size_t size) {
+    size_t nextPage = uintptr_t(begin() + length() + size) >> pageShift;
+    MOZ_ASSERT(currPage < nextPage);
+    unprotectUnusedPartial(currPage, nextPage);
+    vector.infallibleAppend(values, size);
+    protectUsedPartial(currPage, nextPage);
+    currPage = nextPage;
+    resetTest();
+  }
+
+  template <typename U>
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool appendNewPage(const U* values,
+                                                    size_t size) {
+    size_t nextPage = uintptr_t(begin() + length() + size) >> pageShift;
+    MOZ_ASSERT(currPage < nextPage);
+    unprotectUnusedPartial(currPage, nextPage);
+    bool ret = vector.append(values, size);
+    if (MOZ_LIKELY(ret)) {
+      protectUsedPartial(currPage, nextPage);
+      currPage = nextPage;
+    } else {
+      protectUnusedPartial(currPage, nextPage);
+    }
+    resetTest();
+    return ret;
+  }
+
+  template <typename U>
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool appendNewBuffer(const U* values,
+                                                      size_t size) {
+    unprotectOldBuffer();
+    bool ret = vector.append(values, size);
+    protectNewBuffer();
+    return ret;
+  }
+
+  MOZ_NEVER_INLINE void unprotectRegionSlow(uintptr_t l, uintptr_t r);
+  MOZ_NEVER_INLINE void reprotectRegionSlow(uintptr_t l, uintptr_t r);
+
+  MOZ_NEVER_INLINE MOZ_MUST_USE bool reserveSlow(size_t size);
+
+  template <typename U>
+  MOZ_NEVER_INLINE void infallibleAppendSlow(const U* values, size_t size);
+
+  template <typename U>
+  MOZ_NEVER_INLINE MOZ_MUST_USE bool appendSlow(const U* values, size_t size);
+
+ public:
+  explicit PageProtectingVector(AllocPolicy policy = AllocPolicy())
+      : vector(std::move(policy)),
+        elemsUntilTest(0),
+        currPage(0),
+        initPage(0),
+        lastPage(0),
+        lowerBound(InitialLowerBound),
+#ifdef DEBUG
+        regionUnprotected(false),
+#endif
+        usable(true),
+        enabled(true),
+        protectUsedEnabled(false),
+        protectUnusedEnabled(false) {
+    if (gc::SystemPageSize() != pageSize) {
+      usable = false;
+    }
+    protectNewBuffer();
+  }
+
+  ~PageProtectingVector() { unprotectOldBuffer(); }
+
+  void disableProtection() {
+    MOZ_ASSERT(enabled);
+    unprotectOldBuffer();
+    enabled = false;
+    resetForNewBuffer();
+  }
+
+  void enableProtection() {
+    MOZ_ASSERT(!enabled);
+    enabled = true;
+    protectNewBuffer();
+  }
+
+  /*
+   * Sets the lower bound on the size, in elems, that this vector's underlying
+   * capacity has to be before its used pages will be protected.
+   */
+  void setLowerBoundForProtection(size_t elems) {
+    if (lowerBound != elems) {
+      unprotectOldBuffer();
+      lowerBound = elems;
+      protectNewBuffer();
+    }
+  }
+
+  /* Disable protection on the smallest containing region. */
+  MOZ_ALWAYS_INLINE void unprotectRegion(T* first, size_t size) {
+#ifdef DEBUG
+    regionUnprotected = true;
+#endif
+    if (MOZ_UNLIKELY(protectUsedEnabled)) {
+      uintptr_t l = uintptr_t(first) >> pageShift;
+      uintptr_t r = uintptr_t(first + size - 1) >> pageShift;
+      if (r >= initPage && l < currPage) {
+        unprotectRegionSlow(l, r);
+      }
+    }
+  }
+
+  /* Re-enable protection on the smallest containing region. */
+  MOZ_ALWAYS_INLINE void reprotectRegion(T* first, size_t size) {
+#ifdef DEBUG
+    regionUnprotected = false;
+#endif
+    if (MOZ_UNLIKELY(protectUsedEnabled)) {
+      uintptr_t l = uintptr_t(first) >> pageShift;
+      uintptr_t r = uintptr_t(first + size - 1) >> pageShift;
+      if (r >= initPage && l < currPage) {
+        reprotectRegionSlow(l, r);
+      }
+    }
+  }
+
+  MOZ_ALWAYS_INLINE size_t capacity() const { return vector.capacity(); }
+  MOZ_ALWAYS_INLINE size_t length() const { return vector.length(); }
+
+  MOZ_ALWAYS_INLINE T* begin() { return vector.begin(); }
+  MOZ_ALWAYS_INLINE const T* begin() const { return vector.begin(); }
+
+  void clear() {
+    unprotectOldBuffer();
+    vector.clear();
+    protectNewBuffer();
+  }
+
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool reserve(size_t size) {
+    if (MOZ_LIKELY(size <= capacity())) {
+      return vector.reserve(size);
+    }
+    return reserveSlow(size);
+  }
+
+  template <typename U>
+  MOZ_ALWAYS_INLINE void infallibleAppend(const U* values, size_t size) {
+    elemsUntilTest -= size;
+    if (MOZ_LIKELY(elemsUntilTest >= 0)) {
+      return vector.infallibleAppend(values, size);
+    }
+    infallibleAppendSlow(values, size);
+  }
+
+  template <typename U>
+  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool append(const U* values, size_t size) {
+    elemsUntilTest -= size;
+    if (MOZ_LIKELY(elemsUntilTest >= 0)) {
+      return vector.append(values, size);
+    }
+    return appendSlow(values, size);
+  }
+};
+
+template <typename T, size_t A, class B, bool C, bool D, size_t E, bool F,
+          uint8_t G>
+MOZ_NEVER_INLINE void
+PageProtectingVector<T, A, B, C, D, E, F, G>::unprotectRegionSlow(uintptr_t l,
+                                                                  uintptr_t r) {
+  if (l < initPage) {
+    l = initPage;
+  }
+  if (r >= currPage) {
+    r = currPage - 1;
+  }
+  T* addr = reinterpret_cast<T*>(l << pageShift);
+  size_t size = (r - l + 1) << pageShift;
+  gc::UnprotectPages(addr, size);
+}
+
+template <typename T, size_t A, class B, bool C, bool D, size_t E, bool F,
+          uint8_t G>
+MOZ_NEVER_INLINE void
+PageProtectingVector<T, A, B, C, D, E, F, G>::reprotectRegionSlow(uintptr_t l,
+                                                                  uintptr_t r) {
+  if (l < initPage) {
+    l = initPage;
+  }
+  if (r >= currPage) {
+    r = currPage - 1;
+  }
+  T* addr = reinterpret_cast<T*>(l << pageShift);
+  size_t size = (r - l + 1) << pageShift;
+  gc::MakePagesReadOnly(addr, size);
+}
+
+template <typename T, size_t A, class B, bool C, bool D, size_t E, bool F,
+          uint8_t G>
+MOZ_NEVER_INLINE MOZ_MUST_USE bool
+PageProtectingVector<T, A, B, C, D, E, F, G>::reserveSlow(size_t size) {
+  return reserveNewBuffer(size);
+}
+
+template <typename T, size_t A, class B, bool C, bool D, size_t E, bool F,
+          uint8_t G>
+template <typename U>
+MOZ_NEVER_INLINE void
+PageProtectingVector<T, A, B, C, D, E, F, G>::infallibleAppendSlow(
+    const U* values, size_t size) {
+  // Ensure that we're here because we reached a page
+  // boundary and not because of a buffer overflow.
+  MOZ_RELEASE_ASSERT(
+      MOZ_LIKELY(length() + size <= capacity()),
+      "About to overflow our AssemblerBuffer using infallibleAppend!");
+  infallibleAppendNewPage(values, size);
+}
+
+template <typename T, size_t A, class B, bool C, bool D, size_t E, bool F,
+          uint8_t G>
+template <typename U>
+MOZ_NEVER_INLINE MOZ_MUST_USE bool
+PageProtectingVector<T, A, B, C, D, E, F, G>::appendSlow(const U* values,
+                                                         size_t size) {
+  if (MOZ_LIKELY(length() + size <= capacity())) {
+    return appendNewPage(values, size);
+  }
+  return appendNewBuffer(values, size);
+}
+
+} /* namespace js */
+
+#endif /* ds_PageProtectingVector_h */
diff --git a/js/src/ds/PriorityQueue.h b/js/src/ds/PriorityQueue.h
new file mode 100644
index 0000000000..439c2075a4
--- /dev/null
+++ b/js/src/ds/PriorityQueue.h
@@ -0,0 +1,125 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_PriorityQueue_h
+#define ds_PriorityQueue_h
+
+#include "js/Vector.h"
+
+namespace js {
+
+/*
+ * Class which represents a heap based priority queue using a vector.
+ * Inserting elements and removing the highest priority one are both O(log n).
+ *
+ * Template parameters are the same as for Vector, with the addition that P
+ * must have a static priority(const T&) method which returns higher numbers
+ * for higher priority elements.
+ */
+template <class T, class P, size_t MinInlineCapacity = 0,
+          class AllocPolicy = TempAllocPolicy>
+class PriorityQueue {
+  Vector<T, MinInlineCapacity, AllocPolicy> heap;
+
+  PriorityQueue(const PriorityQueue&) = delete;
+  PriorityQueue& operator=(const PriorityQueue&) = delete;
+
+ public:
+  explicit PriorityQueue(AllocPolicy ap = AllocPolicy())
+      : heap(std::move(ap)) {}
+
+  MOZ_MUST_USE bool reserve(size_t capacity) { return heap.reserve(capacity); }
+
+  size_t length() const { return heap.length(); }
+
+  bool empty() const { return heap.empty(); }
+
+  T removeHighest() {
+    T highest = heap[0];
+    T last = heap.popCopy();
+    if (!heap.empty()) {
+      heap[0] = last;
+      siftDown(0);
+    }
+    return highest;
+  }
+
+  MOZ_MUST_USE bool insert(const T& v) {
+    if (!heap.append(v)) {
+      return false;
+    }
+    siftUp(heap.length() - 1);
+    return true;
+  }
+
+  void infallibleInsert(const T& v) {
+    heap.infallibleAppend(v);
+    siftUp(heap.length() - 1);
+  }
+
+ private:
+  /*
+   * Elements of the vector encode a binary tree:
+   *
+   *      0
+   *    1   2
+   *   3 4 5 6
+   *
+   * The children of element N are (2N + 1) and (2N + 2).
+   * The parent of element N is (N - 1) / 2.
+   *
+   * Each element has higher priority than its children.
+   */
+
+  void siftDown(size_t n) {
+    while (true) {
+      size_t left = n * 2 + 1;
+      size_t right = n * 2 + 2;
+
+      if (left < heap.length()) {
+        if (right < heap.length()) {
+          if (P::priority(heap[n]) < P::priority(heap[right]) &&
+              P::priority(heap[left]) < P::priority(heap[right])) {
+            swap(n, right);
+            n = right;
+            continue;
+          }
+        }
+
+        if (P::priority(heap[n]) < P::priority(heap[left])) {
+          swap(n, left);
+          n = left;
+          continue;
+        }
+      }
+
+      break;
+    }
+  }
+
+  void siftUp(size_t n) {
+    while (n > 0) {
+      size_t parent = (n - 1) / 2;
+
+      if (P::priority(heap[parent]) > P::priority(heap[n])) {
+        break;
+      }
+
+      swap(n, parent);
+      n = parent;
+    }
+  }
+
+  void swap(size_t a, size_t b) {
+    T tmp = heap[a];
+    heap[a] = heap[b];
+    heap[b] = tmp;
+  }
+};
+
+} /* namespace js */
+
+#endif /* ds_PriorityQueue_h */
diff --git a/js/src/ds/Sort.h b/js/src/ds/Sort.h
new file mode 100644
index 0000000000..7841adf7e4
--- /dev/null
+++ b/js/src/ds/Sort.h
@@ -0,0 +1,146 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_Sort_h
+#define ds_Sort_h
+
+#include "jstypes.h"
+
+namespace js {
+
+namespace detail {
+
+template <typename T>
+MOZ_ALWAYS_INLINE void CopyNonEmptyArray(T* dst, const T* src, size_t nelems) {
+  MOZ_ASSERT(nelems != 0);
+  const T* end = src + nelems;
+  do {
+    *dst++ = *src++;
+  } while (src != end);
+}
+
+/* Helper function for MergeSort. */
+template <typename T, typename Comparator>
+MOZ_ALWAYS_INLINE bool MergeArrayRuns(T* dst, const T* src, size_t run1,
+                                      size_t run2, Comparator c) {
+  MOZ_ASSERT(run1 >= 1);
+  MOZ_ASSERT(run2 >= 1);
+
+  /* Copy runs already in sorted order. */
+  const T* b = src + run1;
+  bool lessOrEqual;
+  if (!c(b[-1], b[0], &lessOrEqual)) {
+    return false;
+  }
+
+  if (!lessOrEqual) {
+    /* Runs are not already sorted, merge them. */
+    for (const T* a = src;;) {
+      if (!c(*a, *b, &lessOrEqual)) {
+        return false;
+      }
+      if (lessOrEqual) {
+        *dst++ = *a++;
+        if (!--run1) {
+          src = b;
+          break;
+        }
+      } else {
+        *dst++ = *b++;
+        if (!--run2) {
+          src = a;
+          break;
+        }
+      }
+    }
+  }
+  CopyNonEmptyArray(dst, src, run1 + run2);
+  return true;
+}
+
+} /* namespace detail */
+
+/*
+ * Sort the array using the merge sort algorithm. The scratch should point to
+ * a temporary storage that can hold nelems elements.
+ *
+ * The comparator must provide the () operator with the following signature:
+ *
+ *     bool operator()(const T& a, const T& a, bool* lessOrEqualp);
+ *
+ * It should return true on success and set *lessOrEqualp to the result of
+ * a <= b operation. If it returns false, the sort terminates immediately with
+ * the false result. In this case the content of the array and scratch is
+ * arbitrary.
+ *
+ * Note: The merge sort algorithm is a stable sort, preserving relative ordering
+ * of entries that compare equal. This makes it a useful substitute for
+ * |std::stable_sort|, which can't be used in SpiderMonkey because it internally
+ * allocates memory without using SpiderMonkey's allocator.
+ */
+template <typename T, typename Comparator>
+MOZ_MUST_USE bool MergeSort(T* array, size_t nelems, T* scratch, Comparator c) {
+  const size_t INS_SORT_LIMIT = 3;
+
+  if (nelems <= 1) {
+    return true;
+  }
+
+  /*
+   * Apply insertion sort to small chunks to reduce the number of merge
+   * passes needed.
+   */
+  for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) {
+    size_t hi = lo + INS_SORT_LIMIT;
+    if (hi >= nelems) {
+      hi = nelems;
+    }
+    for (size_t i = lo + 1; i != hi; i++) {
+      for (size_t j = i;;) {
+        bool lessOrEqual;
+        if (!c(array[j - 1], array[j], &lessOrEqual)) {
+          return false;
+        }
+        if (lessOrEqual) {
+          break;
+        }
+        T tmp = array[j - 1];
+        array[j - 1] = array[j];
+        array[j] = tmp;
+        if (--j == lo) {
+          break;
+        }
+      }
+    }
+  }
+
+  T* vec1 = array;
+  T* vec2 = scratch;
+  for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) {
+    for (size_t lo = 0; lo < nelems; lo += 2 * run) {
+      size_t hi = lo + run;
+      if (hi >= nelems) {
+        detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo);
+        break;
+      }
+      size_t run2 = (run <= nelems - hi) ? run : nelems - hi;
+      if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c)) {
+        return false;
+      }
+    }
+    T* swap = vec1;
+    vec1 = vec2;
+    vec2 = swap;
+  }
+  if (vec1 == scratch) {
+    detail::CopyNonEmptyArray(array, scratch, nelems);
+  }
+  return true;
+}
+
+} /* namespace js */
+
+#endif /* ds_Sort_h */
diff --git a/js/src/ds/SplayTree.h b/js/src/ds/SplayTree.h
new file mode 100644
index 0000000000..ae4c1ca3d3
--- /dev/null
+++ b/js/src/ds/SplayTree.h
@@ -0,0 +1,354 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 ds_SplayTree_h
+#define ds_SplayTree_h
+
+#include "ds/LifoAlloc.h"
+
+namespace js {
+
+/*
+ * Class which represents a splay tree with nodes allocated from a LifoAlloc.
+ * Splay trees are balanced binary search trees for which search, insert and
+ * remove are all amortized O(log n).
+ *
+ * T indicates the type of tree elements, C must have a static
+ * compare(const T&, const T&) method ordering the elements. As for LifoAlloc
+ * objects, T objects stored in the tree will not be explicitly destroyed.
+ */
+template <class T, class C>
+class SplayTree {
+  struct Node {
+    T item;
+    Node* left;
+    Node* right;
+    Node* parent;
+
+    explicit Node(const T& item)
+        : item(item), left(nullptr), right(nullptr), parent(nullptr) {}
+  };
+
+  LifoAlloc* alloc;
+  Node* root;
+  Node* freeList;
+
+#ifdef DEBUG
+  bool enableCheckCoherency;
+#endif
+
+  SplayTree(const SplayTree&) = delete;
+  SplayTree& operator=(const SplayTree&) = delete;
+
+ public:
+  explicit SplayTree(LifoAlloc* alloc = nullptr)
+      : alloc(alloc),
+        root(nullptr),
+        freeList(nullptr)
+#ifdef DEBUG
+        ,
+        enableCheckCoherency(true)
+#endif
+  {
+  }
+
+  void setAllocator(LifoAlloc* alloc) { this->alloc = alloc; }
+
+  void disableCheckCoherency() {
+#ifdef DEBUG
+    enableCheckCoherency = false;
+#endif
+  }
+
+  bool empty() const { return !root; }
+
+  T* maybeLookup(const T& v) {
+    if (!root) {
+      return nullptr;
+    }
+    Node* last = lookup(v);
+    return (C::compare(v, last->item) == 0) ? &(last->item) : nullptr;
+  }
+
+  bool contains(const T& v, T* res) {
+    if (!root) {
+      return false;
+    }
+    Node* last = lookup(v);
+    splay(last);
+    checkCoherency();
+    if (C::compare(v, last->item) == 0) {
+      *res = last->item;
+      return true;
+    }
+    return false;
+  }
+
+  MOZ_MUST_USE bool insert(const T& v) {
+    Node* element = allocateNode(v);
+    if (!element) {
+      return false;
+    }
+
+    if (!root) {
+      root = element;
+      return true;
+    }
+    Node* last = lookup(v);
+    int cmp = C::compare(v, last->item);
+
+    // Don't tolerate duplicate elements.
+    MOZ_DIAGNOSTIC_ASSERT(cmp);
+
+    Node*& parentPointer = (cmp < 0) ? last->left : last->right;
+    MOZ_ASSERT(!parentPointer);
+    parentPointer = element;
+    element->parent = last;
+
+    splay(element);
+    checkCoherency();
+    return true;
+  }
+
+  void remove(const T& v) {
+    Node* last = lookup(v);
+    MOZ_ASSERT(last && C::compare(v, last->item) == 0);
+
+    splay(last);
+    MOZ_ASSERT(last == root);
+
+    // Find another node which can be swapped in for the root: either the
+    // rightmost child of the root's left, or the leftmost child of the
+    // root's right.
+    Node* swap;
+    Node* swapChild;
+    if (root->left) {
+      swap = root->left;
+      while (swap->right) {
+        swap = swap->right;
+      }
+      swapChild = swap->left;
+    } else if (root->right) {
+      swap = root->right;
+      while (swap->left) {
+        swap = swap->left;
+      }
+      swapChild = swap->right;
+    } else {
+      freeNode(root);
+      root = nullptr;
+      return;
+    }
+
+    // The selected node has at most one child, in swapChild. Detach it
+    // from the subtree by replacing it with that child.
+    if (swap == swap->parent->left) {
+      swap->parent->left = swapChild;
+    } else {
+      swap->parent->right = swapChild;
+    }
+    if (swapChild) {
+      swapChild->parent = swap->parent;
+    }
+
+    root->item = swap->item;
+    freeNode(swap);
+
+    checkCoherency();
+  }
+
+  template <class Op>
+  void forEach(Op op) {
+    forEachInner<Op>(op, root);
+  }
+
+ private:
+  Node* lookup(const T& v) {
+    MOZ_ASSERT(root);
+    Node* node = root;
+    Node* parent;
+    do {
+      parent = node;
+      int c = C::compare(v, node->item);
+      if (c == 0) {
+        return node;
+      } else if (c < 0) {
+        node = node->left;
+      } else {
+        node = node->right;
+      }
+    } while (node);
+    return parent;
+  }
+
+  Node* allocateNode(const T& v) {
+    Node* node = freeList;
+    if (node) {
+      freeList = node->left;
+      new (node) Node(v);
+      return node;
+    }
+    return alloc->new_<Node>(v);
+  }
+
+  void freeNode(Node* node) {
+    node->left = freeList;
+    freeList = node;
+  }
+
+  void splay(Node* node) {
+    // Rotate the element until it is at the root of the tree. Performing
+    // the rotations in this fashion preserves the amortized balancing of
+    // the tree.
+    MOZ_ASSERT(node);
+    while (node != root) {
+      Node* parent = node->parent;
+      if (parent == root) {
+        // Zig rotation.
+        rotate(node);
+        MOZ_ASSERT(node == root);
+        return;
+      }
+      Node* grandparent = parent->parent;
+      if ((parent->left == node) == (grandparent->left == parent)) {
+        // Zig-zig rotation.
+        rotate(parent);
+        rotate(node);
+      } else {
+        // Zig-zag rotation.
+        rotate(node);
+        rotate(node);
+      }
+    }
+  }
+
+  void rotate(Node* node) {
+    // Rearrange nodes so that node becomes the parent of its current
+    // parent, while preserving the sortedness of the tree.
+    Node* parent = node->parent;
+    if (parent->left == node) {
+      //     x          y
+      //   y  c  ==>  a  x
+      //  a b           b c
+      parent->left = node->right;
+      if (node->right) {
+        node->right->parent = parent;
+      }
+      node->right = parent;
+    } else {
+      MOZ_ASSERT(parent->right == node);
+      //   x             y
+      //  a  y   ==>   x  c
+      //    b c       a b
+      parent->right = node->left;
+      if (node->left) {
+        node->left->parent = parent;
+      }
+      node->left = parent;
+    }
+    node->parent = parent->parent;
+    parent->parent = node;
+    if (Node* grandparent = node->parent) {
+      if (grandparent->left == parent) {
+        grandparent->left = node;
+      } else {
+        grandparent->right = node;
+      }
+    } else {
+      root = node;
+    }
+  }
+
+  template <class Op>
+  void forEachInner(Op op, Node* node) {
+    if (!node) {
+      return;
+    }
+
+    forEachInner<Op>(op, node->left);
+    op(node->item);
+    forEachInner<Op>(op, node->right);
+  }
+
+  void checkCoherency() const {
+#ifdef DEBUG
+    if (!enableCheckCoherency) {
+      return;
+    }
+    if (!root) {
+      return;
+    }
+    MOZ_ASSERT(root->parent == nullptr);
+    const Node* node = root;
+    const Node* minimum = nullptr;
+    MOZ_ASSERT_IF(node->left, node->left->parent == node);
+    MOZ_ASSERT_IF(node->right, node->right->parent == node);
+
+    // This is doing a depth-first search and check that the values are
+    // ordered properly.
+    while (true) {
+      // Go to the left-most child.
+      while (node->left) {
+        MOZ_ASSERT_IF(node->left, node->left->parent == node);
+        MOZ_ASSERT_IF(node->right, node->right->parent == node);
+        node = node->left;
+      }
+
+      MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
+      minimum = node;
+
+      if (node->right) {
+        // Go once to the right and try again.
+        MOZ_ASSERT_IF(node->left, node->left->parent == node);
+        MOZ_ASSERT_IF(node->right, node->right->parent == node);
+        node = node->right;
+      } else {
+        // We reached a leaf node, move to the first branch to the right of
+        // our current left-most sub-tree.
+        MOZ_ASSERT(!node->left && !node->right);
+        const Node* prev = nullptr;
+
+        // Visit the parent node, to find the right branch which we have
+        // not visited yet. Either we are coming back from the right
+        // branch, or we are coming back from the left branch with no
+        // right branch to visit.
+        while (node->parent) {
+          prev = node;
+          node = node->parent;
+
+          // If we came back from the left branch, visit the value.
+          if (node->left == prev) {
+            MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
+            minimum = node;
+          }
+
+          if (node->right != prev && node->right != nullptr) {
+            break;
+          }
+        }
+
+        if (!node->parent) {
+          MOZ_ASSERT(node == root);
+          // We reached the root node either because we came back from
+          // the right hand side, or because the root node had a
+          // single child.
+          if (node->right == prev || node->right == nullptr) {
+            return;
+          }
+        }
+
+        // Go to the right node which we have not visited yet.
+        MOZ_ASSERT(node->right != prev && node->right != nullptr);
+        node = node->right;
+      }
+    }
+#endif
+  }
+};
+
+} /* namespace js */
+
+#endif /* ds_SplayTree_h */
diff --git a/js/src/ds/TraceableFifo.h b/js/src/ds/TraceableFifo.h
new file mode 100644
index 0000000000..a904610276
--- /dev/null
+++ b/js/src/ds/TraceableFifo.h
@@ -0,0 +1,93 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 js_TraceableFifo_h
+#define js_TraceableFifo_h
+
+#include "ds/Fifo.h"
+#include "js/RootingAPI.h"
+#include "js/TracingAPI.h"
+
+namespace js {
+
+// A TraceableFifo is a Fifo with an additional trace method that knows how to
+// visit all of the items stored in the Fifo. For Fifos that contain GC things,
+// this is usually more convenient than manually iterating and marking the
+// contents.
+//
+// Most types of GC pointers as keys and values can be traced with no extra
+// infrastructure. For structs and non-gc-pointer members, ensure that there is
+// a specialization of GCPolicy<T> with an appropriate trace method available
+// to handle the custom type. Generic helpers can be found in
+// js/public/TracingAPI.h. Generic helpers can be found in
+// js/public/TracingAPI.h.
+//
+// Note that although this Fifo's trace will deal correctly with moved items, it
+// does not itself know when to barrier or trace items. To function properly it
+// must either be used with Rooted, or barriered and traced manually.
+template <typename T, size_t MinInlineCapacity = 0,
+          typename AllocPolicy = TempAllocPolicy>
+class TraceableFifo : public js::Fifo<T, MinInlineCapacity, AllocPolicy> {
+  using Base = js::Fifo<T, MinInlineCapacity, AllocPolicy>;
+
+ public:
+  explicit TraceableFifo(AllocPolicy alloc = AllocPolicy())
+      : Base(std::move(alloc)) {}
+
+  TraceableFifo(TraceableFifo&& rhs) : Base(std::move(rhs)) {}
+  TraceableFifo& operator=(TraceableFifo&& rhs) = default;
+
+  TraceableFifo(const TraceableFifo&) = delete;
+  TraceableFifo& operator=(const TraceableFifo&) = delete;
+
+  void trace(JSTracer* trc) {
+    for (size_t i = 0; i < this->front_.length(); ++i) {
+      JS::GCPolicy<T>::trace(trc, &this->front_[i], "fifo element");
+    }
+    for (size_t i = 0; i < this->rear_.length(); ++i) {
+      JS::GCPolicy<T>::trace(trc, &this->rear_[i], "fifo element");
+    }
+  }
+};
+
+template <typename Wrapper, typename T, size_t Capacity, typename AllocPolicy>
+class WrappedPtrOperations<TraceableFifo<T, Capacity, AllocPolicy>, Wrapper> {
+  using TF = TraceableFifo<T, Capacity, AllocPolicy>;
+  const TF& fifo() const { return static_cast<const Wrapper*>(this)->get(); }
+
+ public:
+  size_t length() const { return fifo().length(); }
+  bool empty() const { return fifo().empty(); }
+  const T& front() const { return fifo().front(); }
+};
+
+template <typename Wrapper, typename T, size_t Capacity, typename AllocPolicy>
+class MutableWrappedPtrOperations<TraceableFifo<T, Capacity, AllocPolicy>,
+                                  Wrapper>
+    : public WrappedPtrOperations<TraceableFifo<T, Capacity, AllocPolicy>,
+                                  Wrapper> {
+  using TF = TraceableFifo<T, Capacity, AllocPolicy>;
+  TF& fifo() { return static_cast<Wrapper*>(this)->get(); }
+
+ public:
+  T& front() { return fifo().front(); }
+
+  template <typename U>
+  bool pushBack(U&& u) {
+    return fifo().pushBack(std::forward<U>(u));
+  }
+  template <typename... Args>
+  bool emplaceBack(Args&&... args) {
+    return fifo().emplaceBack(std::forward<Args...>(args...));
+  }
+
+  void popFront() { fifo().popFront(); }
+  void clear() { fifo().clear(); }
+};
+
+}  // namespace js
+
+#endif  // js_TraceableFifo_h