Adding upstream version 86.0.1.upstream/86.0.1upstream

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

1 files changed, 2224 insertions, 0 deletions

diff --git a/js/src/vm/Shape.cpp b/js/src/vm/Shape.cpp
new file mode 100644
index 0000000000..406af24c3a
--- /dev/null
+++ b/js/src/vm/Shape.cpp
@@ -0,0 +1,2224 @@
+/* -*- 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/. */
+
+/* JS symbol tables. */
+
+#include "vm/Shape-inl.h"
+
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/PodOperations.h"
+
+#include "gc/FreeOp.h"
+#include "gc/HashUtil.h"
+#include "gc/Policy.h"
+#include "gc/PublicIterators.h"
+#include "js/HashTable.h"
+#include "js/UniquePtr.h"
+#include "util/Text.h"
+#include "vm/JSAtom.h"
+#include "vm/JSContext.h"
+#include "vm/JSObject.h"
+
+#include "vm/Caches-inl.h"
+#include "vm/JSContext-inl.h"
+#include "vm/JSObject-inl.h"
+#include "vm/NativeObject-inl.h"
+#include "vm/Realm-inl.h"
+
+using namespace js;
+
+using mozilla::CeilingLog2Size;
+using mozilla::PodZero;
+
+using JS::AutoCheckCannotGC;
+
+Shape* const ShapeTable::Entry::SHAPE_REMOVED =
+    (Shape*)ShapeTable::Entry::SHAPE_COLLISION;
+
+bool ShapeIC::init(JSContext* cx) {
+  size_ = MAX_SIZE;
+  entries_.reset(cx->pod_calloc<Entry>(size_));
+  return (!entries_) ? false : true;
+}
+
+bool ShapeTable::init(JSContext* cx, Shape* lastProp) {
+  uint32_t sizeLog2 = CeilingLog2Size(entryCount_);
+  uint32_t size = Bit(sizeLog2);
+  if (entryCount_ >= size - (size >> 2)) {
+    sizeLog2++;
+  }
+  if (sizeLog2 < MIN_SIZE_LOG2) {
+    sizeLog2 = MIN_SIZE_LOG2;
+  }
+
+  size = Bit(sizeLog2);
+  entries_.reset(cx->pod_calloc<Entry>(size));
+  if (!entries_) {
+    return false;
+  }
+
+  MOZ_ASSERT(sizeLog2 <= HASH_BITS);
+  hashShift_ = HASH_BITS - sizeLog2;
+
+  for (Shape::Range<NoGC> r(lastProp); !r.empty(); r.popFront()) {
+    Shape& shape = r.front();
+    Entry& entry = searchUnchecked<MaybeAdding::Adding>(shape.propid());
+
+    /*
+     * Beware duplicate args and arg vs. var conflicts: the youngest shape
+     * (nearest to lastProp) must win. See bug 600067.
+     */
+    if (!entry.shape()) {
+      entry.setPreservingCollision(&shape);
+    }
+  }
+
+  MOZ_ASSERT(capacity() == size);
+  MOZ_ASSERT(size >= MIN_SIZE);
+  MOZ_ASSERT(!needsToGrow());
+  return true;
+}
+
+void Shape::removeFromDictionary(NativeObject* obj) {
+  MOZ_ASSERT(inDictionary());
+  MOZ_ASSERT(obj->inDictionaryMode());
+  MOZ_ASSERT(!dictNext.isNone());
+
+  MOZ_ASSERT(obj->shape()->inDictionary());
+  MOZ_ASSERT(obj->shape()->dictNext.toObject() == obj);
+
+  if (parent) {
+    parent->setDictionaryNextPtr(dictNext);
+  }
+  *dictNext.prevPtr() = parent;
+  clearDictionaryNextPtr();
+
+  obj->shape()->clearCachedBigEnoughForShapeTable();
+}
+
+void Shape::insertIntoDictionaryBefore(DictionaryShapeLink next) {
+  // Don't assert inDictionaryMode() here because we may be called from
+  // NativeObject::toDictionaryMode via Shape::initDictionaryShape.
+  MOZ_ASSERT(inDictionary());
+  MOZ_ASSERT(dictNext.isNone());
+
+  Shape* prev = *next.prevPtr();
+
+#ifdef DEBUG
+  if (prev) {
+    MOZ_ASSERT(prev->inDictionary());
+    MOZ_ASSERT(prev->dictNext == next);
+    MOZ_ASSERT(zone() == prev->zone());
+  }
+#endif
+
+  setParent(prev);
+  if (parent) {
+    parent->setNextDictionaryShape(this);
+  }
+
+  setDictionaryNextPtr(next);
+  *dictNext.prevPtr() = this;
+}
+
+bool Shape::makeOwnBaseShape(JSContext* cx) {
+  MOZ_ASSERT(!base()->isOwned());
+  MOZ_ASSERT(cx->zone() == zone());
+
+  BaseShape* nbase = Allocate<BaseShape, NoGC>(cx);
+  if (!nbase) {
+    return false;
+  }
+
+  new (nbase) BaseShape(StackBaseShape(this));
+  nbase->setOwned(base()->toUnowned());
+
+  setBase(nbase);
+
+  return true;
+}
+
+void Shape::handoffTableTo(Shape* shape) {
+  MOZ_ASSERT(inDictionary() && shape->inDictionary());
+
+  if (this == shape) {
+    return;
+  }
+
+  MOZ_ASSERT(base()->isOwned() && !shape->base()->isOwned());
+
+  BaseShape* nbase = base();
+
+  setBase(nbase->baseUnowned());
+  nbase->adoptUnowned(shape->base()->toUnowned());
+
+  shape->setBase(nbase);
+}
+
+/* static */
+bool Shape::hashify(JSContext* cx, Shape* shape) {
+  MOZ_ASSERT(!shape->hasTable());
+
+  if (!shape->ensureOwnBaseShape(cx)) {
+    return false;
+  }
+
+  UniquePtr<ShapeTable> table =
+      cx->make_unique<ShapeTable>(shape->entryCount());
+  if (!table) {
+    return false;
+  }
+
+  if (!table->init(cx, shape)) {
+    return false;
+  }
+
+  BaseShape* base = shape->base();
+  base->maybePurgeCache(cx->defaultFreeOp());
+  base->setTable(table.release());
+  // TODO: The contents of ShapeTable is not currently tracked, only the object
+  // itself.
+  AddCellMemory(base, sizeof(ShapeTable), MemoryUse::ShapeCache);
+  return true;
+}
+
+void ShapeCachePtr::maybePurgeCache(JSFreeOp* fop, BaseShape* base) {
+  if (isTable()) {
+    ShapeTable* table = getTablePointer();
+    if (table->freeList() == SHAPE_INVALID_SLOT) {
+      fop->delete_(base, getTablePointer(), MemoryUse::ShapeCache);
+      p = 0;
+    }
+  } else if (isIC()) {
+    fop->delete_<ShapeIC>(base, getICPointer(), MemoryUse::ShapeCache);
+    p = 0;
+  }
+}
+
+/* static */
+bool Shape::cachify(JSContext* cx, Shape* shape) {
+  MOZ_ASSERT(!shape->hasTable() && !shape->hasIC());
+
+  if (!shape->ensureOwnBaseShape(cx)) {
+    return false;
+  }
+
+  UniquePtr<ShapeIC> ic = cx->make_unique<ShapeIC>();
+  if (!ic) {
+    return false;
+  }
+
+  if (!ic->init(cx)) {
+    return false;
+  }
+
+  shape->base()->setIC(ic.release());
+  AddCellMemory(shape->base(), sizeof(ShapeIC), MemoryUse::ShapeCache);
+  return true;
+}
+
+bool ShapeTable::change(JSContext* cx, int log2Delta) {
+  MOZ_ASSERT(entries_);
+  MOZ_ASSERT(-1 <= log2Delta && log2Delta <= 1);
+
+  /*
+   * Grow, shrink, or compress by changing this->entries_.
+   */
+  uint32_t oldLog2 = HASH_BITS - hashShift_;
+  uint32_t newLog2 = oldLog2 + log2Delta;
+  uint32_t oldSize = Bit(oldLog2);
+  uint32_t newSize = Bit(newLog2);
+  Entry* newTable = cx->maybe_pod_calloc<Entry>(newSize);
+  if (!newTable) {
+    return false;
+  }
+
+  /* Now that we have newTable allocated, update members. */
+  MOZ_ASSERT(newLog2 <= HASH_BITS);
+  hashShift_ = HASH_BITS - newLog2;
+  removedCount_ = 0;
+  Entry* oldTable = entries_.release();
+  entries_.reset(newTable);
+
+  /* Copy only live entries, leaving removed and free ones behind. */
+  AutoCheckCannotGC nogc;
+  for (Entry* oldEntry = oldTable; oldSize != 0; oldEntry++) {
+    if (Shape* shape = oldEntry->shape()) {
+      Entry& entry = search<MaybeAdding::Adding>(shape->propid(), nogc);
+      MOZ_ASSERT(entry.isFree());
+      entry.setShape(shape);
+    }
+    oldSize--;
+  }
+
+  MOZ_ASSERT(capacity() == newSize);
+
+  /* Finally, free the old entries storage. */
+  js_free(oldTable);
+  return true;
+}
+
+bool ShapeTable::grow(JSContext* cx) {
+  MOZ_ASSERT(needsToGrow());
+
+  uint32_t size = capacity();
+  int delta = removedCount_ < (size >> 2);
+
+  MOZ_ASSERT(entryCount_ + removedCount_ <= size - 1);
+
+  if (!change(cx, delta)) {
+    if (entryCount_ + removedCount_ == size - 1) {
+      ReportOutOfMemory(cx);
+      return false;
+    }
+  }
+
+  return true;
+}
+
+void ShapeCachePtr::trace(JSTracer* trc) {
+  if (isIC()) {
+    getICPointer()->trace(trc);
+  } else if (isTable()) {
+    getTablePointer()->trace(trc);
+  }
+}
+
+void ShapeIC::trace(JSTracer* trc) {
+  for (size_t i = 0; i < entryCount(); i++) {
+    Entry& entry = entries_[i];
+    if (entry.shape_) {
+      TraceManuallyBarrieredEdge(trc, &entry.shape_, "ShapeIC shape");
+    }
+  }
+}
+
+void ShapeTable::trace(JSTracer* trc) {
+  for (size_t i = 0; i < capacity(); i++) {
+    Entry& entry = getEntry(i);
+    Shape* shape = entry.shape();
+    if (shape) {
+      TraceManuallyBarrieredEdge(trc, &shape, "ShapeTable shape");
+      if (shape != entry.shape()) {
+        entry.setPreservingCollision(shape);
+      }
+    }
+  }
+}
+
+inline void ShapeCachePtr::destroy(JSFreeOp* fop, BaseShape* base) {
+  if (isTable()) {
+    fop->delete_(base, getTablePointer(), MemoryUse::ShapeCache);
+  } else if (isIC()) {
+    fop->delete_(base, getICPointer(), MemoryUse::ShapeCache);
+  }
+  p = 0;
+}
+
+#ifdef JSGC_HASH_TABLE_CHECKS
+
+void ShapeCachePtr::checkAfterMovingGC() {
+  if (isIC()) {
+    getICPointer()->checkAfterMovingGC();
+  } else if (isTable()) {
+    getTablePointer()->checkAfterMovingGC();
+  }
+}
+
+void ShapeIC::checkAfterMovingGC() {
+  for (size_t i = 0; i < entryCount(); i++) {
+    Entry& entry = entries_[i];
+    Shape* shape = entry.shape_;
+    if (shape) {
+      CheckGCThingAfterMovingGC(shape);
+    }
+  }
+}
+
+void ShapeTable::checkAfterMovingGC() {
+  for (size_t i = 0; i < capacity(); i++) {
+    Entry& entry = getEntry(i);
+    Shape* shape = entry.shape();
+    if (shape) {
+      CheckGCThingAfterMovingGC(shape);
+    }
+  }
+}
+
+#endif
+
+/* static */
+Shape* Shape::replaceLastProperty(JSContext* cx, StackBaseShape& base,
+                                  TaggedProto proto, HandleShape shape) {
+  MOZ_ASSERT(!shape->inDictionary());
+
+  if (!shape->parent) {
+    /* Treat as resetting the initial property of the shape hierarchy. */
+    gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots());
+    return EmptyShape::getInitialShape(
+        cx, base.clasp, proto, kind, base.flags & BaseShape::OBJECT_FLAG_MASK);
+  }
+
+  UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
+  if (!nbase) {
+    return nullptr;
+  }
+
+  Rooted<StackShape> child(cx, StackShape(shape));
+  child.setBase(nbase);
+
+  return cx->zone()->propertyTree().getChild(cx, shape->parent, child);
+}
+
+/*
+ * Get or create a property-tree or dictionary child property of |parent|,
+ * which must be lastProperty() if inDictionaryMode(), else parent must be
+ * one of lastProperty() or lastProperty()->parent.
+ */
+/* static */ MOZ_ALWAYS_INLINE Shape* NativeObject::getChildDataProperty(
+    JSContext* cx, HandleNativeObject obj, HandleShape parent,
+    MutableHandle<StackShape> child) {
+  MOZ_ASSERT(child.isDataProperty());
+
+  if (child.hasMissingSlot()) {
+    uint32_t slot;
+    if (obj->inDictionaryMode()) {
+      if (!allocDictionarySlot(cx, obj, &slot)) {
+        return nullptr;
+      }
+    } else {
+      slot = obj->slotSpan();
+      MOZ_ASSERT(slot >= JSSLOT_FREE(obj->getClass()));
+      // Objects with many properties are converted to dictionary
+      // mode, so we can't overflow SHAPE_MAXIMUM_SLOT here.
+      MOZ_ASSERT(slot <
+                 JSSLOT_FREE(obj->getClass()) + PropertyTree::MAX_HEIGHT);
+      MOZ_ASSERT(slot < SHAPE_MAXIMUM_SLOT);
+    }
+    child.setSlot(slot);
+  } else {
+    /*
+     * Slots can only be allocated out of order on objects in
+     * dictionary mode.  Otherwise the child's slot must be after the
+     * parent's slot (if it has one), because slot number determines
+     * slot span for objects with that shape.  Usually child slot
+     * *immediately* follows parent slot, but there may be a slot gap
+     * when the object uses some -- but not all -- of its reserved
+     * slots to store properties.
+     */
+    MOZ_ASSERT(obj->inDictionaryMode() || parent->hasMissingSlot() ||
+               child.slot() == parent->maybeSlot() + 1 ||
+               (parent->maybeSlot() + 1 < JSSLOT_FREE(obj->getClass()) &&
+                child.slot() == JSSLOT_FREE(obj->getClass())));
+  }
+
+  if (obj->inDictionaryMode()) {
+    MOZ_ASSERT(parent == obj->lastProperty());
+    Shape* shape = Allocate<Shape>(cx);
+    if (!shape) {
+      return nullptr;
+    }
+    if (child.slot() >= obj->slotSpan()) {
+      if (!obj->ensureSlotsForDictionaryObject(cx, child.slot() + 1)) {
+        new (shape) Shape(obj->lastProperty()->base()->unowned(), 0);
+        return nullptr;
+      }
+    }
+    shape->initDictionaryShape(child, obj->numFixedSlots(),
+                               DictionaryShapeLink(obj));
+    return shape;
+  }
+
+  Shape* shape = cx->zone()->propertyTree().inlinedGetChild(cx, parent, child);
+  if (!shape) {
+    return nullptr;
+  }
+
+  MOZ_ASSERT(shape->parent == parent);
+  MOZ_ASSERT_IF(parent != obj->lastProperty(),
+                parent == obj->lastProperty()->parent);
+
+  if (!obj->setLastProperty(cx, shape)) {
+    return nullptr;
+  }
+  return shape;
+}
+
+/* static */ MOZ_ALWAYS_INLINE Shape* NativeObject::getChildAccessorProperty(
+    JSContext* cx, HandleNativeObject obj, HandleShape parent,
+    MutableHandle<StackShape> child) {
+  MOZ_ASSERT(!child.isDataProperty());
+
+  // Accessor properties have no slot, but slot_ will reflect that of parent.
+  child.setSlot(parent->maybeSlot());
+
+  if (obj->inDictionaryMode()) {
+    MOZ_ASSERT(parent == obj->lastProperty());
+    Shape* shape = Allocate<AccessorShape>(cx);
+    if (!shape) {
+      return nullptr;
+    }
+    shape->initDictionaryShape(child, obj->numFixedSlots(),
+                               DictionaryShapeLink(obj));
+    return shape;
+  }
+
+  Shape* shape = cx->zone()->propertyTree().inlinedGetChild(cx, parent, child);
+  if (!shape) {
+    return nullptr;
+  }
+
+  MOZ_ASSERT(shape->parent == parent);
+  MOZ_ASSERT_IF(parent != obj->lastProperty(),
+                parent == obj->lastProperty()->parent);
+
+  if (!obj->setLastProperty(cx, shape)) {
+    return nullptr;
+  }
+  return shape;
+}
+
+/* static */
+bool js::NativeObject::toDictionaryMode(JSContext* cx, HandleNativeObject obj) {
+  MOZ_ASSERT(!obj->inDictionaryMode());
+  MOZ_ASSERT(cx->isInsideCurrentCompartment(obj));
+
+  uint32_t span = obj->slotSpan();
+
+  // Clone the shapes into a new dictionary list. Don't update the last
+  // property of this object until done, otherwise a GC triggered while
+  // creating the dictionary will get the wrong slot span for this object.
+  RootedShape root(cx);
+  RootedShape dictionaryShape(cx);
+
+  RootedShape shape(cx, obj->lastProperty());
+  while (shape) {
+    MOZ_ASSERT(!shape->inDictionary());
+
+    Shape* dprop = shape->isAccessorShape() ? Allocate<AccessorShape>(cx)
+                                            : Allocate<Shape>(cx);
+    if (!dprop) {
+      ReportOutOfMemory(cx);
+      return false;
+    }
+
+    DictionaryShapeLink next;
+    if (dictionaryShape) {
+      next.setShape(dictionaryShape);
+    }
+    StackShape child(shape);
+    dprop->initDictionaryShape(child, obj->numFixedSlots(), next);
+
+    if (!dictionaryShape) {
+      root = dprop;
+    }
+
+    MOZ_ASSERT(!dprop->hasTable());
+    dictionaryShape = dprop;
+    shape = shape->previous();
+  }
+
+  if (!Shape::hashify(cx, root)) {
+    ReportOutOfMemory(cx);
+    return false;
+  }
+
+  if (IsInsideNursery(obj) &&
+      !cx->nursery().queueDictionaryModeObjectToSweep(obj)) {
+    ReportOutOfMemory(cx);
+    return false;
+  }
+
+  MOZ_ASSERT(root->dictNext.isNone());
+  root->setDictionaryObject(obj);
+  obj->setShape(root);
+
+  MOZ_ASSERT(obj->inDictionaryMode());
+  obj->setDictionaryModeSlotSpan(span);
+
+  return true;
+}
+
+static bool ShouldConvertToDictionary(NativeObject* obj) {
+  /*
+   * Use a lower limit if this object is likely a hashmap (SETELEM was used
+   * to set properties).
+   */
+  if (obj->hadElementsAccess()) {
+    return obj->lastProperty()->entryCount() >=
+           PropertyTree::MAX_HEIGHT_WITH_ELEMENTS_ACCESS;
+  }
+  return obj->lastProperty()->entryCount() >= PropertyTree::MAX_HEIGHT;
+}
+
+static MOZ_ALWAYS_INLINE UnownedBaseShape* GetBaseShapeForNewShape(
+    JSContext* cx, HandleShape last, HandleId id) {
+  uint32_t index;
+  bool indexed = IdIsIndex(id, &index);
+  bool interestingSymbol =
+      JSID_IS_SYMBOL(id) && JSID_TO_SYMBOL(id)->isInterestingSymbol();
+
+  if (MOZ_LIKELY(!indexed && !interestingSymbol)) {
+    return last->base()->unowned();
+  }
+
+  StackBaseShape base(last->base());
+  if (indexed) {
+    base.flags |= BaseShape::INDEXED;
+  } else if (interestingSymbol) {
+    base.flags |= BaseShape::HAS_INTERESTING_SYMBOL;
+  }
+  return BaseShape::getUnowned(cx, base);
+}
+
+namespace js {
+
+class MOZ_RAII AutoCheckShapeConsistency {
+#ifdef DEBUG
+  HandleNativeObject obj_;
+#endif
+
+ public:
+  explicit AutoCheckShapeConsistency(HandleNativeObject obj)
+#ifdef DEBUG
+      : obj_(obj)
+#endif
+  {
+  }
+
+#ifdef DEBUG
+  ~AutoCheckShapeConsistency() { obj_->checkShapeConsistency(); }
+#endif
+};
+
+}  // namespace js
+
+/* static */ MOZ_ALWAYS_INLINE bool
+NativeObject::maybeConvertToOrGrowDictionaryForAdd(
+    JSContext* cx, HandleNativeObject obj, HandleId id, ShapeTable** table,
+    ShapeTable::Entry** entry, const AutoKeepShapeCaches& keep) {
+  MOZ_ASSERT(!!*table == !!*entry);
+
+  // The code below deals with either converting obj to dictionary mode or
+  // growing an object that's already in dictionary mode.
+  if (!obj->inDictionaryMode()) {
+    if (!ShouldConvertToDictionary(obj)) {
+      return true;
+    }
+    if (!toDictionaryMode(cx, obj)) {
+      return false;
+    }
+    *table = obj->lastProperty()->maybeTable(keep);
+  } else {
+    if (!(*table)->needsToGrow()) {
+      return true;
+    }
+    if (!(*table)->grow(cx)) {
+      return false;
+    }
+  }
+
+  *entry = &(*table)->search<MaybeAdding::Adding>(id, keep);
+  MOZ_ASSERT(!(*entry)->shape());
+  return true;
+}
+
+MOZ_ALWAYS_INLINE void Shape::updateDictionaryTable(
+    ShapeTable* table, ShapeTable::Entry* entry,
+    const AutoKeepShapeCaches& keep) {
+  MOZ_ASSERT(table);
+  MOZ_ASSERT(entry);
+  MOZ_ASSERT(inDictionary());
+
+  // Store this Shape in the table entry.
+  entry->setPreservingCollision(this);
+  table->incEntryCount();
+
+  // Pass the table along to the new last property, namely *this.
+  MOZ_ASSERT(parent->maybeTable(keep) == table);
+  parent->handoffTableTo(this);
+}
+
+static void AssertValidPropertyOp(NativeObject* obj, GetterOp getter,
+                                  SetterOp setter, unsigned attrs) {
+  // We only support PropertyOp accessors on ArrayObject and ArgumentsObject
+  // and we don't want to add more of these properties (bug 1404885).
+
+#ifdef DEBUG
+  if ((getter && !(attrs & JSPROP_GETTER)) ||
+      (setter && !(attrs & JSPROP_SETTER))) {
+    MOZ_ASSERT(obj->is<ArrayObject>() || obj->is<ArgumentsObject>());
+  }
+#endif
+}
+
+/* static */
+Shape* NativeObject::addAccessorPropertyInternal(
+    JSContext* cx, HandleNativeObject obj, HandleId id, GetterOp getter,
+    SetterOp setter, unsigned attrs, ShapeTable* table,
+    ShapeTable::Entry* entry, const AutoKeepShapeCaches& keep) {
+  AutoCheckShapeConsistency check(obj);
+  AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
+
+  AssertValidPropertyOp(obj, getter, setter, attrs);
+
+  if (!maybeConvertToOrGrowDictionaryForAdd(cx, obj, id, &table, &entry,
+                                            keep)) {
+    return nullptr;
+  }
+
+  // Find or create a property tree node labeled by our arguments.
+  RootedShape shape(cx);
+  {
+    RootedShape last(cx, obj->lastProperty());
+    Rooted<UnownedBaseShape*> nbase(cx, GetBaseShapeForNewShape(cx, last, id));
+    if (!nbase) {
+      return nullptr;
+    }
+
+    Rooted<StackShape> child(cx,
+                             StackShape(nbase, id, SHAPE_INVALID_SLOT, attrs));
+    child.updateGetterSetter(getter, setter);
+    shape = getChildAccessorProperty(cx, obj, last, &child);
+    if (!shape) {
+      return nullptr;
+    }
+  }
+
+  MOZ_ASSERT(shape == obj->lastProperty());
+
+  if (table) {
+    shape->updateDictionaryTable(table, entry, keep);
+  }
+
+  return shape;
+}
+
+/* static */
+Shape* NativeObject::addDataPropertyInternal(JSContext* cx,
+                                             HandleNativeObject obj,
+                                             HandleId id, uint32_t slot,
+                                             unsigned attrs, ShapeTable* table,
+                                             ShapeTable::Entry* entry,
+                                             const AutoKeepShapeCaches& keep) {
+  AutoCheckShapeConsistency check(obj);
+
+  // The slot, if any, must be a reserved slot.
+  MOZ_ASSERT(slot == SHAPE_INVALID_SLOT ||
+             slot < JSCLASS_RESERVED_SLOTS(obj->getClass()));
+
+  if (!maybeConvertToOrGrowDictionaryForAdd(cx, obj, id, &table, &entry,
+                                            keep)) {
+    return nullptr;
+  }
+
+  // Find or create a property tree node labeled by our arguments.
+  RootedShape shape(cx);
+  {
+    RootedShape last(cx, obj->lastProperty());
+    Rooted<UnownedBaseShape*> nbase(cx, GetBaseShapeForNewShape(cx, last, id));
+    if (!nbase) {
+      return nullptr;
+    }
+
+    Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs));
+    shape = getChildDataProperty(cx, obj, last, &child);
+    if (!shape) {
+      return nullptr;
+    }
+  }
+
+  MOZ_ASSERT(shape == obj->lastProperty());
+
+  if (table) {
+    shape->updateDictionaryTable(table, entry, keep);
+  }
+
+  return shape;
+}
+
+static MOZ_ALWAYS_INLINE Shape* PropertyTreeReadBarrier(JSContext* cx,
+                                                        Shape* parent,
+                                                        Shape* shape) {
+  JS::Zone* zone = shape->zone();
+  if (zone->needsIncrementalBarrier()) {
+    // We need a read barrier for the shape tree, since these are weak
+    // pointers.
+    Shape* tmp = shape;
+    TraceManuallyBarrieredEdge(zone->barrierTracer(), &tmp, "read barrier");
+    MOZ_ASSERT(tmp == shape);
+    return shape;
+  }
+
+  if (MOZ_LIKELY(!zone->isGCSweepingOrCompacting() ||
+                 !IsAboutToBeFinalizedUnbarriered(&shape))) {
+    if (shape->isMarkedGray()) {
+      UnmarkGrayShapeRecursively(shape);
+    }
+    return shape;
+  }
+
+  // The shape we've found is unreachable and due to be finalized, so
+  // remove our weak reference to it and don't use it.
+  MOZ_ASSERT(parent->isMarkedAny());
+  parent->removeChild(cx->defaultFreeOp(), shape);
+
+  return nullptr;
+}
+
+/* static */
+Shape* NativeObject::addEnumerableDataProperty(JSContext* cx,
+                                               HandleNativeObject obj,
+                                               HandleId id) {
+  // Like addProperty(Internal), but optimized for the common case of adding a
+  // new enumerable data property.
+
+  AutoCheckShapeConsistency check(obj);
+
+  // Fast path for non-dictionary shapes with a single child.
+  do {
+    AutoCheckCannotGC nogc;
+
+    Shape* lastProperty = obj->lastProperty();
+    if (lastProperty->inDictionary()) {
+      break;
+    }
+
+    ShapeChildren* childp = &lastProperty->children;
+    if (!childp->isSingleShape()) {
+      break;
+    }
+
+    Shape* child = childp->toSingleShape();
+    MOZ_ASSERT(!child->inDictionary());
+
+    if (child->propidRaw() != id || child->isAccessorShape() ||
+        child->attributes() != JSPROP_ENUMERATE ||
+        child->base()->unowned() != lastProperty->base()->unowned()) {
+      break;
+    }
+
+    MOZ_ASSERT(child->isDataProperty());
+
+    child = PropertyTreeReadBarrier(cx, lastProperty, child);
+    if (!child) {
+      break;
+    }
+
+    if (!obj->setLastProperty(cx, child)) {
+      return nullptr;
+    }
+    return child;
+  } while (0);
+
+  AutoKeepShapeCaches keep(cx);
+  ShapeTable* table = nullptr;
+  ShapeTable::Entry* entry = nullptr;
+
+  if (!obj->inDictionaryMode()) {
+    if (MOZ_UNLIKELY(ShouldConvertToDictionary(obj))) {
+      if (!toDictionaryMode(cx, obj)) {
+        return nullptr;
+      }
+      table = obj->lastProperty()->maybeTable(keep);
+      entry = &table->search<MaybeAdding::Adding>(id, keep);
+    }
+  } else {
+    table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
+    if (!table) {
+      return nullptr;
+    }
+    if (table->needsToGrow()) {
+      if (!table->grow(cx)) {
+        return nullptr;
+      }
+    }
+    entry = &table->search<MaybeAdding::Adding>(id, keep);
+    MOZ_ASSERT(!entry->shape());
+  }
+
+  MOZ_ASSERT(!!table == !!entry);
+
+  /* Find or create a property tree node labeled by our arguments. */
+  RootedShape last(cx, obj->lastProperty());
+  UnownedBaseShape* nbase = GetBaseShapeForNewShape(cx, last, id);
+  if (!nbase) {
+    return nullptr;
+  }
+
+  Shape* shape;
+  if (obj->inDictionaryMode()) {
+    uint32_t slot;
+    if (!allocDictionarySlot(cx, obj, &slot)) {
+      return nullptr;
+    }
+
+    Rooted<StackShape> child(cx, StackShape(nbase, id, slot, JSPROP_ENUMERATE));
+
+    MOZ_ASSERT(last == obj->lastProperty());
+    shape = Allocate<Shape>(cx);
+    if (!shape) {
+      return nullptr;
+    }
+    if (slot >= obj->slotSpan()) {
+      if (MOZ_UNLIKELY(!obj->ensureSlotsForDictionaryObject(cx, slot + 1))) {
+        new (shape) Shape(obj->lastProperty()->base()->unowned(), 0);
+        return nullptr;
+      }
+    }
+    shape->initDictionaryShape(child, obj->numFixedSlots(),
+                               DictionaryShapeLink(obj));
+  } else {
+    uint32_t slot = obj->slotSpan();
+    MOZ_ASSERT(slot >= JSSLOT_FREE(obj->getClass()));
+    // Objects with many properties are converted to dictionary
+    // mode, so we can't overflow SHAPE_MAXIMUM_SLOT here.
+    MOZ_ASSERT(slot < JSSLOT_FREE(obj->getClass()) + PropertyTree::MAX_HEIGHT);
+    MOZ_ASSERT(slot < SHAPE_MAXIMUM_SLOT);
+
+    Rooted<StackShape> child(cx, StackShape(nbase, id, slot, JSPROP_ENUMERATE));
+    shape = cx->zone()->propertyTree().inlinedGetChild(cx, last, child);
+    if (!shape) {
+      return nullptr;
+    }
+    if (!obj->setLastProperty(cx, shape)) {
+      return nullptr;
+    }
+  }
+
+  MOZ_ASSERT(shape == obj->lastProperty());
+
+  if (table) {
+    shape->updateDictionaryTable(table, entry, keep);
+  }
+
+  return shape;
+}
+
+/*
+ * Assert some invariants that should hold when changing properties. It's the
+ * responsibility of the callers to ensure these hold.
+ */
+static void AssertCanChangeAttrs(Shape* shape, unsigned attrs) {
+#ifdef DEBUG
+  if (shape->configurable()) {
+    return;
+  }
+
+  /* A permanent property must stay permanent. */
+  MOZ_ASSERT(attrs & JSPROP_PERMANENT);
+
+  /* Reject attempts to remove a slot from the permanent data property. */
+  MOZ_ASSERT_IF(shape->isDataProperty(),
+                !(attrs & (JSPROP_GETTER | JSPROP_SETTER)));
+#endif
+}
+
+static void AssertValidArrayIndex(NativeObject* obj, jsid id) {
+#ifdef DEBUG
+  if (obj->is<ArrayObject>()) {
+    ArrayObject* arr = &obj->as<ArrayObject>();
+    uint32_t index;
+    if (IdIsIndex(id, &index)) {
+      MOZ_ASSERT(index < arr->length() || arr->lengthIsWritable());
+    }
+  }
+#endif
+}
+
+/* static */
+bool NativeObject::maybeToDictionaryModeForPut(JSContext* cx,
+                                               HandleNativeObject obj,
+                                               MutableHandleShape shape) {
+  // Overwriting a non-last property requires switching to dictionary mode.
+  // The shape tree is shared immutable, and we can't removeProperty and then
+  // addAccessorPropertyInternal because a failure under add would lose data.
+
+  if (shape == obj->lastProperty() || obj->inDictionaryMode()) {
+    return true;
+  }
+
+  if (!toDictionaryMode(cx, obj)) {
+    return false;
+  }
+
+  AutoCheckCannotGC nogc;
+  ShapeTable* table = obj->lastProperty()->maybeTable(nogc);
+  MOZ_ASSERT(table);
+  shape.set(
+      table->search<MaybeAdding::NotAdding>(shape->propid(), nogc).shape());
+  return true;
+}
+
+/* static */
+Shape* NativeObject::putDataProperty(JSContext* cx, HandleNativeObject obj,
+                                     HandleId id, unsigned attrs) {
+  MOZ_ASSERT(!JSID_IS_VOID(id));
+
+  AutoCheckShapeConsistency check(obj);
+  AssertValidArrayIndex(obj, id);
+
+  // Search for id in order to claim its entry if table has been allocated.
+  AutoKeepShapeCaches keep(cx);
+  RootedShape shape(cx);
+  {
+    ShapeTable* table;
+    ShapeTable::Entry* entry;
+    if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep,
+                                            shape.address(), &table, &entry)) {
+      return nullptr;
+    }
+
+    if (!shape) {
+      MOZ_ASSERT(
+          obj->isExtensible() ||
+              (JSID_IS_INT(id) && obj->containsDenseElement(JSID_TO_INT(id))),
+          "Can't add new property to non-extensible object");
+      return addDataPropertyInternal(cx, obj, id, SHAPE_INVALID_SLOT, attrs,
+                                     table, entry, keep);
+    }
+
+    // Property exists: search must have returned a valid entry.
+    MOZ_ASSERT_IF(entry, !entry->isRemoved());
+  }
+
+  AssertCanChangeAttrs(shape, attrs);
+
+  // If the caller wants to allocate a slot, but doesn't care which slot,
+  // copy the existing shape's slot into slot so we can match shape, if all
+  // other members match.
+  bool hadSlot = shape->isDataProperty();
+  uint32_t oldSlot = shape->maybeSlot();
+  uint32_t slot = hadSlot ? oldSlot : SHAPE_INVALID_SLOT;
+
+  Rooted<UnownedBaseShape*> nbase(cx);
+  {
+    RootedShape shape(cx, obj->lastProperty());
+    nbase = GetBaseShapeForNewShape(cx, shape, id);
+    if (!nbase) {
+      return nullptr;
+    }
+  }
+
+  // Now that we've possibly preserved slot, check whether all members match.
+  // If so, this is a redundant "put" and we can return without more work.
+  if (shape->matchesParamsAfterId(nbase, slot, attrs, nullptr, nullptr)) {
+    return shape;
+  }
+
+  if (!maybeToDictionaryModeForPut(cx, obj, &shape)) {
+    return nullptr;
+  }
+
+  MOZ_ASSERT_IF(shape->isDataProperty(), shape->slot() == slot);
+
+  if (obj->inDictionaryMode()) {
+    // Updating some property in a dictionary-mode object. Create a new
+    // shape for the existing property, and also generate a new shape for
+    // the last property of the dictionary (unless the modified property
+    // is also the last property).
+    bool updateLast = (shape == obj->lastProperty());
+    shape = NativeObject::replaceWithNewEquivalentShape(
+        cx, obj, shape, nullptr,
+        /* accessorShape = */ false);
+    if (!shape) {
+      return nullptr;
+    }
+    if (!updateLast && !NativeObject::generateOwnShape(cx, obj)) {
+      return nullptr;
+    }
+
+    if (slot == SHAPE_INVALID_SLOT) {
+      if (!allocDictionarySlot(cx, obj, &slot)) {
+        return nullptr;
+      }
+    }
+
+    if (updateLast) {
+      shape->base()->adoptUnowned(nbase);
+    } else {
+      shape->setBase(nbase);
+    }
+
+    shape->setSlot(slot);
+    shape->attrs = uint8_t(attrs);
+    shape->immutableFlags &= ~Shape::ACCESSOR_SHAPE;
+    shape->immutableFlags |= Shape::IN_DICTIONARY;
+  } else {
+    // Updating the last property in a non-dictionary-mode object. Find an
+    // alternate shared child of the last property's previous shape.
+
+    MOZ_ASSERT(shape == obj->lastProperty());
+
+    // Find or create a property tree node labeled by our arguments.
+    Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs));
+    RootedShape parent(cx, shape->parent);
+    shape = getChildDataProperty(cx, obj, parent, &child);
+    if (!shape) {
+      return nullptr;
+    }
+  }
+
+  MOZ_ASSERT(shape->isDataProperty());
+  return shape;
+}
+
+/* static */
+Shape* NativeObject::putAccessorProperty(JSContext* cx, HandleNativeObject obj,
+                                         HandleId id, GetterOp getter,
+                                         SetterOp setter, unsigned attrs) {
+  MOZ_ASSERT(!JSID_IS_VOID(id));
+
+  AutoCheckShapeConsistency check(obj);
+  AssertValidArrayIndex(obj, id);
+  AssertValidPropertyOp(obj, getter, setter, attrs);
+
+  AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
+
+  // Search for id in order to claim its entry if table has been allocated.
+  AutoKeepShapeCaches keep(cx);
+  RootedShape shape(cx);
+  {
+    ShapeTable* table;
+    ShapeTable::Entry* entry;
+    if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep,
+                                            shape.address(), &table, &entry)) {
+      return nullptr;
+    }
+
+    if (!shape) {
+      MOZ_ASSERT(
+          obj->isExtensible() ||
+              (JSID_IS_INT(id) && obj->containsDenseElement(JSID_TO_INT(id))),
+          "Can't add new property to non-extensible object");
+      return addAccessorPropertyInternal(cx, obj, id, getter, setter, attrs,
+                                         table, entry, keep);
+    }
+
+    // Property exists: search must have returned a valid entry.
+    MOZ_ASSERT_IF(entry, !entry->isRemoved());
+  }
+
+  AssertCanChangeAttrs(shape, attrs);
+
+  bool hadSlot = shape->isDataProperty();
+  uint32_t oldSlot = shape->maybeSlot();
+
+  Rooted<UnownedBaseShape*> nbase(cx);
+  {
+    RootedShape shape(cx, obj->lastProperty());
+    nbase = GetBaseShapeForNewShape(cx, shape, id);
+    if (!nbase) {
+      return nullptr;
+    }
+  }
+
+  // Check whether all members match. If so, this is a redundant "put" and we
+  // can return without more work.
+  if (shape->matchesParamsAfterId(nbase, SHAPE_INVALID_SLOT, attrs, getter,
+                                  setter)) {
+    return shape;
+  }
+
+  if (!maybeToDictionaryModeForPut(cx, obj, &shape)) {
+    return nullptr;
+  }
+
+  if (obj->inDictionaryMode()) {
+    // Updating some property in a dictionary-mode object. Create a new
+    // shape for the existing property, and also generate a new shape for
+    // the last property of the dictionary (unless the modified property
+    // is also the last property).
+    bool updateLast = (shape == obj->lastProperty());
+    shape =
+        NativeObject::replaceWithNewEquivalentShape(cx, obj, shape, nullptr,
+                                                    /* accessorShape = */ true);
+    if (!shape) {
+      return nullptr;
+    }
+    if (!updateLast && !NativeObject::generateOwnShape(cx, obj)) {
+      return nullptr;
+    }
+
+    if (updateLast) {
+      shape->base()->adoptUnowned(nbase);
+    } else {
+      shape->setBase(nbase);
+    }
+
+    shape->setSlot(SHAPE_INVALID_SLOT);
+    shape->attrs = uint8_t(attrs);
+    shape->immutableFlags |= Shape::IN_DICTIONARY | Shape::ACCESSOR_SHAPE;
+
+    AccessorShape& accShape = shape->asAccessorShape();
+    accShape.rawGetter = getter;
+    accShape.rawSetter = setter;
+    GetterSetterPostWriteBarrier(&accShape);
+  } else {
+    // Updating the last property in a non-dictionary-mode object. Find an
+    // alternate shared child of the last property's previous shape.
+
+    MOZ_ASSERT(shape == obj->lastProperty());
+
+    // Find or create a property tree node labeled by our arguments.
+    Rooted<StackShape> child(cx,
+                             StackShape(nbase, id, SHAPE_INVALID_SLOT, attrs));
+    child.updateGetterSetter(getter, setter);
+    RootedShape parent(cx, shape->parent);
+    shape = getChildAccessorProperty(cx, obj, parent, &child);
+    if (!shape) {
+      return nullptr;
+    }
+  }
+
+  // Can't fail now, so free the previous incarnation's slot. But we do not
+  // need to free oldSlot (and must not, as trying to will botch an assertion
+  // in NativeObject::freeSlot) if the new last property (shape here) has a
+  // slotSpan that does not cover it.
+  if (hadSlot && oldSlot < obj->slotSpan()) {
+    obj->freeSlot(cx, oldSlot);
+  }
+
+  MOZ_ASSERT(!shape->isDataProperty());
+  return shape;
+}
+
+/* static */
+Shape* NativeObject::changeProperty(JSContext* cx, HandleNativeObject obj,
+                                    HandleShape shape, unsigned attrs,
+                                    GetterOp getter, SetterOp setter) {
+  MOZ_ASSERT(obj->containsPure(shape));
+
+  AutoCheckShapeConsistency check(obj);
+
+  /* Allow only shared (slotless) => unshared (slotful) transition. */
+#ifdef DEBUG
+  bool needSlot = Shape::isDataProperty(attrs, getter, setter);
+  MOZ_ASSERT_IF(shape->isDataProperty() != needSlot, needSlot);
+#endif
+
+  AssertCanChangeAttrs(shape, attrs);
+
+  if (shape->attrs == attrs && shape->getter() == getter &&
+      shape->setter() == setter) {
+    return shape;
+  }
+
+  RootedId propid(cx, shape->propid());
+  return putAccessorProperty(cx, obj, propid, getter, setter, attrs);
+}
+
+/* static */
+bool NativeObject::removeProperty(JSContext* cx, HandleNativeObject obj,
+                                  jsid id_) {
+  RootedId id(cx, id_);
+
+  AutoKeepShapeCaches keep(cx);
+  ShapeTable* table;
+  ShapeTable::Entry* entry;
+  RootedShape shape(cx);
+  if (!Shape::search(cx, obj->lastProperty(), id, keep, shape.address(), &table,
+                     &entry)) {
+    return false;
+  }
+
+  if (!shape) {
+    return true;
+  }
+
+  /*
+   * If shape is not the last property added, or the last property cannot
+   * be removed, switch to dictionary mode.
+   */
+  if (!obj->inDictionaryMode() &&
+      (shape != obj->lastProperty() || !obj->canRemoveLastProperty())) {
+    if (!toDictionaryMode(cx, obj)) {
+      return false;
+    }
+    table = obj->lastProperty()->maybeTable(keep);
+    MOZ_ASSERT(table);
+    entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
+    shape = entry->shape();
+  }
+
+  /*
+   * If in dictionary mode, get a new shape for the last property after the
+   * removal. We need a fresh shape for all dictionary deletions, even of
+   * the last property. Otherwise, a shape could replay and caches might
+   * return deleted DictionaryShapes! See bug 595365. Do this before changing
+   * the object or table, so the remaining removal is infallible.
+   */
+  RootedShape spare(cx);
+  if (obj->inDictionaryMode()) {
+    /* For simplicity, always allocate an accessor shape for now. */
+    spare = Allocate<AccessorShape>(cx);
+    if (!spare) {
+      return false;
+    }
+    new (spare) Shape(shape->base()->unowned(), 0);
+    if (shape == obj->lastProperty()) {
+      /*
+       * Get an up to date unowned base shape for the new last property
+       * when removing the dictionary's last property. Information in
+       * base shapes for non-last properties may be out of sync with the
+       * object's state.
+       */
+      RootedShape previous(cx, obj->lastProperty()->parent);
+      StackBaseShape base(obj->lastProperty()->base());
+      BaseShape* nbase = BaseShape::getUnowned(cx, base);
+      if (!nbase) {
+        return false;
+      }
+      previous->setBase(nbase);
+    }
+  }
+
+  /* If shape has a slot, free its slot number. */
+  if (shape->isDataProperty()) {
+    obj->freeSlot(cx, shape->slot());
+  }
+
+  /*
+   * A dictionary-mode object owns mutable, unique shapes on a non-circular
+   * doubly linked list, hashed by lastProperty()->table. So we can edit the
+   * list and hash in place.
+   */
+  if (obj->inDictionaryMode()) {
+    MOZ_ASSERT(obj->lastProperty()->maybeTable(keep) == table);
+
+    if (entry->hadCollision()) {
+      entry->setRemoved();
+      table->decEntryCount();
+      table->incRemovedCount();
+    } else {
+      entry->setFree();
+      table->decEntryCount();
+
+#ifdef DEBUG
+      /*
+       * Check the consistency of the table but limit the number of
+       * checks not to alter significantly the complexity of the
+       * delete in debug builds, see bug 534493.
+       */
+      Shape* aprop = obj->lastProperty();
+      for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent) {
+        MOZ_ASSERT_IF(aprop != shape, obj->contains(cx, aprop));
+      }
+#endif
+    }
+
+    {
+      /* Remove shape from its non-circular doubly linked list. */
+      Shape* oldLastProp = obj->lastProperty();
+      shape->removeFromDictionary(obj);
+
+      /* Hand off table from the old to new last property. */
+      oldLastProp->handoffTableTo(obj->lastProperty());
+    }
+
+    /* Generate a new shape for the object, infallibly. */
+    MOZ_ALWAYS_TRUE(NativeObject::generateOwnShape(cx, obj, spare));
+
+    /* Consider shrinking table if its load factor is <= .25. */
+    uint32_t size = table->capacity();
+    if (size > ShapeTable::MIN_SIZE && table->entryCount() <= size >> 2) {
+      (void)table->change(cx, -1);
+    }
+  } else {
+    /*
+     * Non-dictionary-mode shape tables are shared immutables, so all we
+     * need do is retract the last property and we'll either get or else
+     * lazily make via a later hashify the exact table for the new property
+     * lineage.
+     */
+    MOZ_ASSERT(shape == obj->lastProperty());
+    obj->removeLastProperty(cx);
+  }
+
+  obj->checkShapeConsistency();
+  return true;
+}
+
+/* static */
+Shape* NativeObject::replaceWithNewEquivalentShape(JSContext* cx,
+                                                   HandleNativeObject obj,
+                                                   Shape* oldShape,
+                                                   Shape* newShape,
+                                                   bool accessorShape) {
+  MOZ_ASSERT(cx->isInsideCurrentZone(oldShape));
+  MOZ_ASSERT_IF(oldShape != obj->lastProperty(),
+                obj->inDictionaryMode() &&
+                    obj->lookup(cx, oldShape->propidRef()) == oldShape);
+
+  if (!obj->inDictionaryMode()) {
+    RootedShape newRoot(cx, newShape);
+    if (!toDictionaryMode(cx, obj)) {
+      return nullptr;
+    }
+    oldShape = obj->lastProperty();
+    newShape = newRoot;
+  }
+
+  if (!newShape) {
+    RootedShape oldRoot(cx, oldShape);
+    newShape = (oldShape->isAccessorShape() || accessorShape)
+                   ? Allocate<AccessorShape>(cx)
+                   : Allocate<Shape>(cx);
+    if (!newShape) {
+      return nullptr;
+    }
+    new (newShape) Shape(oldRoot->base()->unowned(), 0);
+    oldShape = oldRoot;
+  }
+
+  AutoCheckCannotGC nogc;
+  ShapeTable* table = obj->lastProperty()->ensureTableForDictionary(cx, nogc);
+  if (!table) {
+    return nullptr;
+  }
+
+  ShapeTable::Entry* entry =
+      oldShape->isEmptyShape()
+          ? nullptr
+          : &table->search<MaybeAdding::NotAdding>(oldShape->propidRef(), nogc);
+
+  /*
+   * Splice the new shape into the same position as the old shape, preserving
+   * enumeration order (see bug 601399).
+   */
+  StackShape nshape(oldShape);
+  newShape->initDictionaryShape(nshape, obj->numFixedSlots(),
+                                oldShape->dictNext);
+
+  MOZ_ASSERT(newShape->parent == oldShape);
+  oldShape->removeFromDictionary(obj);
+
+  if (newShape == obj->lastProperty()) {
+    oldShape->handoffTableTo(newShape);
+  }
+
+  if (entry) {
+    entry->setPreservingCollision(newShape);
+  }
+  return newShape;
+}
+
+/* static */
+bool JSObject::setFlags(JSContext* cx, HandleObject obj, BaseShape::Flag flags,
+                        GenerateShape generateShape) {
+  MOZ_ASSERT(cx->compartment() == obj->compartment());
+
+  if (obj->hasAllFlags(flags)) {
+    return true;
+  }
+
+  Shape* existingShape = obj->shape();
+  if (!existingShape) {
+    return false;
+  }
+
+  if (obj->isNative() && obj->as<NativeObject>().inDictionaryMode()) {
+    if (generateShape == GENERATE_SHAPE) {
+      if (!NativeObject::generateOwnShape(cx, obj.as<NativeObject>())) {
+        return false;
+      }
+    }
+    StackBaseShape base(obj->as<NativeObject>().lastProperty());
+    base.flags |= flags;
+    UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
+    if (!nbase) {
+      return false;
+    }
+
+    obj->as<NativeObject>().lastProperty()->base()->adoptUnowned(nbase);
+    return true;
+  }
+
+  Shape* newShape =
+      Shape::setObjectFlags(cx, flags, obj->taggedProto(), existingShape);
+  if (!newShape) {
+    return false;
+  }
+
+  obj->as<JSObject>().setShape(newShape);
+  return true;
+}
+
+/* static */
+bool NativeObject::clearFlag(JSContext* cx, HandleNativeObject obj,
+                             BaseShape::Flag flag) {
+  MOZ_ASSERT(obj->lastProperty()->getObjectFlags() & flag);
+
+  if (!obj->inDictionaryMode()) {
+    if (!toDictionaryMode(cx, obj)) {
+      return false;
+    }
+  }
+
+  StackBaseShape base(obj->lastProperty());
+  base.flags &= ~flag;
+  UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
+  if (!nbase) {
+    return false;
+  }
+
+  obj->lastProperty()->base()->adoptUnowned(nbase);
+  return true;
+}
+
+/* static */
+Shape* Shape::setObjectFlags(JSContext* cx, BaseShape::Flag flags,
+                             TaggedProto proto, Shape* last) {
+  if ((last->getObjectFlags() & flags) == flags) {
+    return last;
+  }
+
+  StackBaseShape base(last);
+  base.flags |= flags;
+
+  RootedShape lastRoot(cx, last);
+  return replaceLastProperty(cx, base, proto, lastRoot);
+}
+
+inline BaseShape::BaseShape(const StackBaseShape& base)
+    : TenuredCellWithNonGCPointer(base.clasp),
+      flags(base.flags),
+      unowned_(nullptr) {}
+
+/* static */
+void BaseShape::copyFromUnowned(BaseShape& dest, UnownedBaseShape& src) {
+  dest.setHeaderPtr(src.clasp());
+  dest.unowned_ = &src;
+  dest.flags = src.flags | OWNED_SHAPE;
+}
+
+inline void BaseShape::adoptUnowned(UnownedBaseShape* other) {
+  // This is a base shape owned by a dictionary object, update it to reflect the
+  // unowned base shape of a new last property.
+  MOZ_ASSERT(isOwned());
+
+  BaseShape::copyFromUnowned(*this, *other);
+
+  assertConsistency();
+}
+
+/* static */
+UnownedBaseShape* BaseShape::getUnowned(JSContext* cx, StackBaseShape& base) {
+  auto& table = cx->zone()->baseShapes();
+
+  auto p = MakeDependentAddPtr(cx, table, base);
+  if (p) {
+    return *p;
+  }
+
+  BaseShape* nbase_ = Allocate<BaseShape>(cx);
+  if (!nbase_) {
+    return nullptr;
+  }
+
+  new (nbase_) BaseShape(base);
+
+  UnownedBaseShape* nbase = static_cast<UnownedBaseShape*>(nbase_);
+
+  if (!p.add(cx, table, base, nbase)) {
+    return nullptr;
+  }
+
+  return nbase;
+}
+
+void BaseShape::assertConsistency() {
+#ifdef DEBUG
+  if (isOwned()) {
+    UnownedBaseShape* unowned = baseUnowned();
+    MOZ_ASSERT(getObjectFlags() == unowned->getObjectFlags());
+  }
+#endif
+}
+
+void BaseShape::traceChildren(JSTracer* trc) {
+  traceChildrenSkipShapeCache(trc);
+  traceShapeCache(trc);
+}
+
+void BaseShape::traceChildrenSkipShapeCache(JSTracer* trc) {
+  if (isOwned()) {
+    TraceEdge(trc, &unowned_, "base");
+  }
+
+  assertConsistency();
+}
+
+void BaseShape::traceShapeCache(JSTracer* trc) {
+  AutoCheckCannotGC nogc;
+  cache_.trace(trc);
+}
+
+#ifdef DEBUG
+bool BaseShape::canSkipMarkingShapeCache(Shape* lastShape) {
+  // Check that every shape in the shape table will be marked by marking
+  // |lastShape|.
+  AutoCheckCannotGC nogc;
+  ShapeCachePtr cache = getCache(nogc);
+  if (!cache.isTable()) {
+    return true;
+  }
+
+  uint32_t count = 0;
+  for (Shape::Range<NoGC> r(lastShape); !r.empty(); r.popFront()) {
+    Shape* shape = &r.front();
+    ShapeTable::Entry& entry =
+        cache.getTablePointer()->search<MaybeAdding::NotAdding>(shape->propid(),
+                                                                nogc);
+    if (entry.isLive()) {
+      count++;
+    }
+  }
+
+  return count == cache.getTablePointer()->entryCount();
+}
+#endif
+
+#ifdef JSGC_HASH_TABLE_CHECKS
+
+void Zone::checkBaseShapeTableAfterMovingGC() {
+  for (auto r = baseShapes().all(); !r.empty(); r.popFront()) {
+    UnownedBaseShape* base = r.front().unbarrieredGet();
+    CheckGCThingAfterMovingGC(base);
+
+    BaseShapeSet::Ptr ptr = baseShapes().lookup(base);
+    MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &r.front());
+  }
+}
+
+#endif  // JSGC_HASH_TABLE_CHECKS
+
+void BaseShape::finalize(JSFreeOp* fop) {
+  if (cache_.isInitialized()) {
+    cache_.destroy(fop, this);
+  }
+}
+
+inline InitialShapeEntry::InitialShapeEntry() : shape(nullptr), proto() {}
+
+inline InitialShapeEntry::InitialShapeEntry(Shape* shape,
+                                            const TaggedProto& proto)
+    : shape(shape), proto(proto) {}
+
+#ifdef JSGC_HASH_TABLE_CHECKS
+
+void Zone::checkInitialShapesTableAfterMovingGC() {
+  /*
+   * Assert that the postbarriers have worked and that nothing is left in
+   * initialShapes that points into the nursery, and that the hash table
+   * entries are discoverable.
+   */
+  for (auto r = initialShapes().all(); !r.empty(); r.popFront()) {
+    InitialShapeEntry entry = r.front();
+    TaggedProto proto = entry.proto.unbarrieredGet();
+    Shape* shape = entry.shape.unbarrieredGet();
+
+    CheckGCThingAfterMovingGC(shape);
+    if (proto.isObject()) {
+      CheckGCThingAfterMovingGC(proto.toObject());
+    }
+
+    using Lookup = InitialShapeEntry::Lookup;
+    Lookup lookup(shape->getObjectClass(), proto, shape->numFixedSlots(),
+                  shape->getObjectFlags());
+    InitialShapeSet::Ptr ptr = initialShapes().lookup(lookup);
+    MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &r.front());
+  }
+}
+
+#endif  // JSGC_HASH_TABLE_CHECKS
+
+Shape* EmptyShape::new_(JSContext* cx, Handle<UnownedBaseShape*> base,
+                        uint32_t nfixed) {
+  Shape* shape = Allocate<Shape>(cx);
+  if (!shape) {
+    ReportOutOfMemory(cx);
+    return nullptr;
+  }
+
+  new (shape) EmptyShape(base, nfixed);
+  return shape;
+}
+
+MOZ_ALWAYS_INLINE HashNumber ShapeHasher::hash(const Lookup& l) {
+  return l.hash();
+}
+
+MOZ_ALWAYS_INLINE bool ShapeHasher::match(const Key k, const Lookup& l) {
+  return k->matches(l);
+}
+
+static ShapeSet* MakeShapeSet(Shape* child1, Shape* child2) {
+  auto hash = MakeUnique<ShapeSet>();
+  if (!hash || !hash->reserve(2)) {
+    return nullptr;
+  }
+
+  hash->putNewInfallible(StackShape(child1), child1);
+  hash->putNewInfallible(StackShape(child2), child2);
+  return hash.release();
+}
+
+bool PropertyTree::insertChild(JSContext* cx, Shape* parent, Shape* child) {
+  MOZ_ASSERT(!parent->inDictionary());
+  MOZ_ASSERT(!child->parent);
+  MOZ_ASSERT(!child->inDictionary());
+  MOZ_ASSERT(child->zone() == parent->zone());
+  MOZ_ASSERT(cx->zone() == zone_);
+
+  ShapeChildren* childp = &parent->children;
+
+  if (childp->isNone()) {
+    child->setParent(parent);
+    childp->setSingleShape(child);
+    return true;
+  }
+
+  if (childp->isSingleShape()) {
+    Shape* shape = childp->toSingleShape();
+    MOZ_ASSERT(shape != child);
+    MOZ_ASSERT(!shape->matches(child));
+
+    ShapeSet* hash = MakeShapeSet(shape, child);
+    if (!hash) {
+      ReportOutOfMemory(cx);
+      return false;
+    }
+    childp->setShapeSet(hash);
+    AddCellMemory(parent, sizeof(ShapeSet), MemoryUse::ShapeChildren);
+    child->setParent(parent);
+    return true;
+  }
+
+  if (!childp->toShapeSet()->putNew(StackShape(child), child)) {
+    ReportOutOfMemory(cx);
+    return false;
+  }
+
+  child->setParent(parent);
+  return true;
+}
+
+void Shape::removeChild(JSFreeOp* fop, Shape* child) {
+  MOZ_ASSERT(!child->inDictionary());
+  MOZ_ASSERT(child->parent == this);
+
+  ShapeChildren* childp = &children;
+
+  if (childp->isSingleShape()) {
+    MOZ_ASSERT(childp->toSingleShape() == child);
+    childp->setNone();
+    child->parent = nullptr;
+    return;
+  }
+
+  // There must be at least two shapes in a set otherwise
+  // childp->isSingleShape() should be true.
+  ShapeSet* set = childp->toShapeSet();
+  MOZ_ASSERT(set->count() >= 2);
+
+#ifdef DEBUG
+  size_t oldCount = set->count();
+#endif
+
+  set->remove(StackShape(child));
+  child->parent = nullptr;
+
+  MOZ_ASSERT(set->count() == oldCount - 1);
+
+  if (set->count() == 1) {
+    // Convert from set form back to single shape form.
+    ShapeSet::Range r = set->all();
+    Shape* otherChild = r.front();
+    MOZ_ASSERT((r.popFront(), r.empty()));  // No more elements!
+    childp->setSingleShape(otherChild);
+    fop->delete_(this, set, MemoryUse::ShapeChildren);
+  }
+}
+
+MOZ_ALWAYS_INLINE Shape* PropertyTree::inlinedGetChild(
+    JSContext* cx, Shape* parent, Handle<StackShape> childSpec) {
+  MOZ_ASSERT(parent);
+
+  Shape* existingShape = nullptr;
+
+  /*
+   * The property tree has extremely low fan-out below its root in
+   * popular embeddings with real-world workloads. Patterns such as
+   * defining closures that capture a constructor's environment as
+   * getters or setters on the new object that is passed in as
+   * |this| can significantly increase fan-out below the property
+   * tree root -- see bug 335700 for details.
+   */
+  ShapeChildren* childp = &parent->children;
+  if (childp->isSingleShape()) {
+    Shape* child = childp->toSingleShape();
+    if (child->matches(childSpec)) {
+      existingShape = child;
+    }
+  } else if (childp->isShapeSet()) {
+    if (ShapeSet::Ptr p = childp->toShapeSet()->lookup(childSpec)) {
+      existingShape = *p;
+    }
+  } else {
+    /* If childp->isNone(), we always insert. */
+  }
+
+  if (existingShape) {
+    existingShape = PropertyTreeReadBarrier(cx, parent, existingShape);
+    if (existingShape) {
+      return existingShape;
+    }
+  }
+
+  RootedShape parentRoot(cx, parent);
+  Shape* shape = Shape::new_(cx, childSpec, parentRoot->numFixedSlots());
+  if (!shape) {
+    return nullptr;
+  }
+
+  if (!insertChild(cx, parentRoot, shape)) {
+    return nullptr;
+  }
+
+  return shape;
+}
+
+Shape* PropertyTree::getChild(JSContext* cx, Shape* parent,
+                              Handle<StackShape> child) {
+  return inlinedGetChild(cx, parent, child);
+}
+
+void Shape::sweep(JSFreeOp* fop) {
+  /*
+   * We detach the child from the parent if the parent is reachable.
+   *
+   * This test depends on shape arenas not being freed until after we finish
+   * incrementally sweeping them. If that were not the case the parent pointer
+   * could point to a marked cell that had been deallocated and then
+   * reallocated, since allocating a cell in a zone that is being marked will
+   * set the mark bit for that cell.
+   */
+
+  MOZ_ASSERT(zone()->isGCSweeping());
+  MOZ_ASSERT_IF(parent, parent->zone() == zone());
+
+  if (parent && parent->isMarkedAny()) {
+    if (inDictionary()) {
+      if (parent->dictNext == DictionaryShapeLink(this)) {
+        parent->dictNext.setNone();
+      }
+    } else {
+      parent->removeChild(fop, this);
+    }
+  }
+}
+
+void Shape::finalize(JSFreeOp* fop) {
+  if (!inDictionary() && children.isShapeSet()) {
+    fop->delete_(this, children.toShapeSet(), MemoryUse::ShapeChildren);
+  }
+}
+
+void Shape::fixupDictionaryShapeAfterMovingGC() {
+  if (dictNext.isShape()) {
+    Shape* shape = dictNext.toShape();
+    if (gc::IsForwarded(shape)) {
+      dictNext.setShape(gc::Forwarded(shape));
+    }
+  } else if (dictNext.isObject()) {
+    JSObject* obj = dictNext.toObject();
+    if (gc::IsForwarded(obj)) {
+      dictNext.setObject(gc::Forwarded(obj));
+    }
+  } else {
+    MOZ_ASSERT(dictNext.isNone());
+  }
+}
+
+void Shape::fixupShapeTreeAfterMovingGC() {
+  if (children.isNone()) {
+    return;
+  }
+
+  if (children.isSingleShape()) {
+    if (gc::IsForwarded(children.toSingleShape())) {
+      children.setSingleShape(gc::Forwarded(children.toSingleShape()));
+    }
+    return;
+  }
+
+  MOZ_ASSERT(children.isShapeSet());
+  ShapeSet* set = children.toShapeSet();
+  for (ShapeSet::Enum e(*set); !e.empty(); e.popFront()) {
+    Shape* key = MaybeForwarded(e.front());
+    BaseShape* base = MaybeForwarded(key->base());
+    UnownedBaseShape* unowned = MaybeForwarded(base->unowned());
+
+    GetterOp getter = key->getter();
+    if (key->hasGetterObject()) {
+      getter = GetterOp(MaybeForwarded(key->getterObject()));
+    }
+
+    SetterOp setter = key->setter();
+    if (key->hasSetterObject()) {
+      setter = SetterOp(MaybeForwarded(key->setterObject()));
+    }
+
+    StackShape lookup(unowned, const_cast<Shape*>(key)->propidRef(),
+                      key->immutableFlags & Shape::SLOT_MASK, key->attrs);
+    lookup.updateGetterSetter(getter, setter);
+    e.rekeyFront(lookup, key);
+  }
+}
+
+void Shape::fixupAfterMovingGC() {
+  if (inDictionary()) {
+    fixupDictionaryShapeAfterMovingGC();
+  } else {
+    fixupShapeTreeAfterMovingGC();
+  }
+}
+
+void NurseryShapesRef::trace(JSTracer* trc) {
+  auto& shapes = zone_->nurseryShapes();
+  for (auto shape : shapes) {
+    shape->fixupGetterSetterForBarrier(trc);
+  }
+  shapes.clearAndFree();
+}
+
+void Shape::fixupGetterSetterForBarrier(JSTracer* trc) {
+  if (!hasGetterValue() && !hasSetterValue()) {
+    return;
+  }
+
+  JSObject* priorGetter = asAccessorShape().getterObj;
+  JSObject* priorSetter = asAccessorShape().setterObj;
+  if (!priorGetter && !priorSetter) {
+    return;
+  }
+
+  JSObject* postGetter = priorGetter;
+  JSObject* postSetter = priorSetter;
+  if (priorGetter) {
+    TraceManuallyBarrieredEdge(trc, &postGetter, "getterObj");
+  }
+  if (priorSetter) {
+    TraceManuallyBarrieredEdge(trc, &postSetter, "setterObj");
+  }
+  if (priorGetter == postGetter && priorSetter == postSetter) {
+    return;
+  }
+
+  if (parent && !parent->inDictionary() && parent->children.isShapeSet()) {
+    // Relocating the getterObj or setterObj will have changed our location in
+    // our parent's ShapeSet, so take care to update it. We must do this before
+    // we update the shape itself, since the shape is used to match the original
+    // entry in the hash set.
+
+    StackShape original(this);
+    StackShape updated(this);
+    updated.rawGetter = reinterpret_cast<GetterOp>(postGetter);
+    updated.rawSetter = reinterpret_cast<SetterOp>(postSetter);
+
+    ShapeSet* set = parent->children.toShapeSet();
+    MOZ_ALWAYS_TRUE(set->rekeyAs(original, updated, this));
+  }
+
+  asAccessorShape().getterObj = postGetter;
+  asAccessorShape().setterObj = postSetter;
+
+  MOZ_ASSERT_IF(
+      parent && !parent->inDictionary() && parent->children.isShapeSet(),
+      parent->children.toShapeSet()->has(StackShape(this)));
+}
+
+#ifdef DEBUG
+
+void ShapeChildren::checkHasChild(Shape* child) const {
+  if (isSingleShape()) {
+    MOZ_ASSERT(toSingleShape() == child);
+  } else {
+    MOZ_ASSERT(isShapeSet());
+    ShapeSet* set = toShapeSet();
+    ShapeSet::Ptr ptr = set->lookup(StackShape(child));
+    MOZ_ASSERT(*ptr == child);
+  }
+}
+
+void Shape::dump(js::GenericPrinter& out) const {
+  jsid propid = this->propid();
+
+  MOZ_ASSERT(!JSID_IS_VOID(propid));
+
+  if (JSID_IS_INT(propid)) {
+    out.printf("[%ld]", (long)JSID_TO_INT(propid));
+  } else if (JSID_IS_ATOM(propid)) {
+    if (JSLinearString* str = JSID_TO_ATOM(propid)) {
+      EscapedStringPrinter(out, str, '"');
+    } else {
+      out.put("<error>");
+    }
+  } else {
+    MOZ_ASSERT(JSID_IS_SYMBOL(propid));
+    JSID_TO_SYMBOL(propid)->dump(out);
+  }
+
+  out.printf(" g/s %p/%p slot %d attrs %x ",
+             JS_FUNC_TO_DATA_PTR(void*, getter()),
+             JS_FUNC_TO_DATA_PTR(void*, setter()),
+             isDataProperty() ? int32_t(slot()) : -1, attrs);
+
+  if (attrs) {
+    int first = 1;
+    out.putChar('(');
+#  define DUMP_ATTR(name, display) \
+    if (attrs & JSPROP_##name) out.put(&(" " #display)[first]), first = 0
+    DUMP_ATTR(ENUMERATE, enumerate);
+    DUMP_ATTR(READONLY, readonly);
+    DUMP_ATTR(PERMANENT, permanent);
+    DUMP_ATTR(GETTER, getter);
+    DUMP_ATTR(SETTER, setter);
+#  undef DUMP_ATTR
+    out.putChar(')');
+  }
+
+  out.printf("immutableFlags %x ", immutableFlags);
+  if (immutableFlags) {
+    int first = 1;
+    out.putChar('(');
+#  define DUMP_FLAG(name, display) \
+    if (immutableFlags & name) out.put(&(" " #display)[first]), first = 0
+    DUMP_FLAG(IN_DICTIONARY, in_dictionary);
+#  undef DUMP_FLAG
+    out.putChar(')');
+  }
+}
+
+void Shape::dump() const {
+  Fprinter out(stderr);
+  dump(out);
+}
+
+void Shape::dumpSubtree(int level, js::GenericPrinter& out) const {
+  if (!parent) {
+    MOZ_ASSERT(level == 0);
+    MOZ_ASSERT(JSID_IS_EMPTY(propid_));
+    out.printf("class %s emptyShape\n", getObjectClass()->name);
+  } else {
+    out.printf("%*sid ", level, "");
+    dump(out);
+  }
+
+  if (!children.isNone()) {
+    ++level;
+    if (children.isSingleShape()) {
+      Shape* child = children.toSingleShape();
+      MOZ_ASSERT(child->parent == this);
+      child->dumpSubtree(level, out);
+    } else {
+      const ShapeSet& set = *children.toShapeSet();
+      for (ShapeSet::Range range = set.all(); !range.empty();
+           range.popFront()) {
+        Shape* child = range.front();
+
+        MOZ_ASSERT(child->parent == this);
+        child->dumpSubtree(level, out);
+      }
+    }
+  }
+}
+
+#endif
+
+/* static */
+Shape* EmptyShape::getInitialShape(JSContext* cx, const JSClass* clasp,
+                                   TaggedProto proto, size_t nfixed,
+                                   uint32_t objectFlags) {
+  MOZ_ASSERT_IF(proto.isObject(),
+                cx->isInsideCurrentCompartment(proto.toObject()));
+
+  auto& table = cx->zone()->initialShapes();
+
+  using Lookup = InitialShapeEntry::Lookup;
+  auto protoPointer =
+      MakeDependentAddPtr(cx, table, Lookup(clasp, proto, nfixed, objectFlags));
+  if (protoPointer) {
+    return protoPointer->shape;
+  }
+
+  Rooted<TaggedProto> protoRoot(cx, proto);
+  StackBaseShape base(clasp, objectFlags);
+  Rooted<UnownedBaseShape*> nbase(cx, BaseShape::getUnowned(cx, base));
+  if (!nbase) {
+    return nullptr;
+  }
+
+  RootedShape shape(cx, EmptyShape::new_(cx, nbase, nfixed));
+  if (!shape) {
+    return nullptr;
+  }
+
+  Lookup lookup(clasp, protoRoot, nfixed, objectFlags);
+  if (!protoPointer.add(cx, table, lookup,
+                        InitialShapeEntry(shape, protoRoot))) {
+    return nullptr;
+  }
+
+  return shape;
+}
+
+/* static */
+Shape* EmptyShape::getInitialShape(JSContext* cx, const JSClass* clasp,
+                                   TaggedProto proto, gc::AllocKind kind,
+                                   uint32_t objectFlags) {
+  return getInitialShape(cx, clasp, proto, GetGCKindSlots(kind, clasp),
+                         objectFlags);
+}
+
+void NewObjectCache::invalidateEntriesForShape(JSContext* cx, HandleShape shape,
+                                               HandleObject proto) {
+  const JSClass* clasp = shape->getObjectClass();
+
+  gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots());
+  if (CanChangeToBackgroundAllocKind(kind, clasp)) {
+    kind = ForegroundToBackgroundAllocKind(kind);
+  }
+
+  RootedObjectGroup group(
+      cx, ObjectGroup::defaultNewGroup(cx, clasp, TaggedProto(proto)));
+  if (!group) {
+    purge();
+    cx->recoverFromOutOfMemory();
+    return;
+  }
+
+  EntryIndex entry;
+  for (RealmsInZoneIter realm(shape->zone()); !realm.done(); realm.next()) {
+    if (GlobalObject* global = realm->unsafeUnbarrieredMaybeGlobal()) {
+      if (lookupGlobal(clasp, global, kind, &entry)) {
+        PodZero(&entries[entry]);
+      }
+    }
+  }
+  if (!proto->is<GlobalObject>() && lookupProto(clasp, proto, kind, &entry)) {
+    PodZero(&entries[entry]);
+  }
+  if (lookupGroup(group, kind, &entry)) {
+    PodZero(&entries[entry]);
+  }
+}
+
+/* static */
+void EmptyShape::insertInitialShape(JSContext* cx, HandleShape shape,
+                                    HandleObject proto) {
+  using Lookup = InitialShapeEntry::Lookup;
+  Lookup lookup(shape->getObjectClass(), TaggedProto(proto),
+                shape->numFixedSlots(), shape->getObjectFlags());
+
+  InitialShapeSet::Ptr p = cx->zone()->initialShapes().lookup(lookup);
+  MOZ_ASSERT(p);
+
+  InitialShapeEntry& entry = const_cast<InitialShapeEntry&>(*p);
+
+  // The metadata callback can end up causing redundant changes of the initial
+  // shape.
+  if (entry.shape == shape) {
+    return;
+  }
+
+  // The new shape had better be rooted at the old one.
+#ifdef DEBUG
+  Shape* nshape = shape;
+  while (!nshape->isEmptyShape()) {
+    nshape = nshape->previous();
+  }
+  MOZ_ASSERT(nshape == entry.shape);
+#endif
+
+  entry.shape = WeakHeapPtrShape(shape);
+
+  /*
+   * This affects the shape that will be produced by the various NewObject
+   * methods, so clear any cache entry referring to the old shape. This is
+   * not required for correctness: the NewObject must always check for a
+   * nativeEmpty() result and generate the appropriate properties if found.
+   * Clearing the cache entry avoids this duplicate regeneration.
+   *
+   * Clearing is not necessary when this context is running off
+   * thread, as it will not use the new object cache for allocations.
+   */
+  if (!cx->isHelperThreadContext()) {
+    cx->caches().newObjectCache.invalidateEntriesForShape(cx, shape, proto);
+  }
+}
+
+void Zone::fixupInitialShapeTable() {
+  for (InitialShapeSet::Enum e(initialShapes()); !e.empty(); e.popFront()) {
+    // The shape may have been moved, but we can update that in place.
+    Shape* shape = e.front().shape.unbarrieredGet();
+    if (IsForwarded(shape)) {
+      shape = Forwarded(shape);
+      e.mutableFront().shape.set(shape);
+    }
+    shape->updateBaseShapeAfterMovingGC();
+
+    // If the prototype has moved we have to rekey the entry.
+    InitialShapeEntry entry = e.front();
+    // Use unbarrieredGet() to prevent triggering read barrier while collecting.
+    const TaggedProto& proto = entry.proto.unbarrieredGet();
+    if (proto.isObject() && IsForwarded(proto.toObject())) {
+      entry.proto = TaggedProto(Forwarded(proto.toObject()));
+      using Lookup = InitialShapeEntry::Lookup;
+      Lookup relookup(shape->getObjectClass(), proto, shape->numFixedSlots(),
+                      shape->getObjectFlags());
+      e.rekeyFront(relookup, entry);
+    }
+  }
+}
+
+void AutoRooterGetterSetter::Inner::trace(JSTracer* trc) {
+  if ((attrs & JSPROP_GETTER) && *pgetter) {
+    TraceRoot(trc, (JSObject**)pgetter, "AutoRooterGetterSetter getter");
+  }
+  if ((attrs & JSPROP_SETTER) && *psetter) {
+    TraceRoot(trc, (JSObject**)psetter, "AutoRooterGetterSetter setter");
+  }
+}
+
+JS::ubi::Node::Size JS::ubi::Concrete<js::Shape>::size(
+    mozilla::MallocSizeOf mallocSizeOf) const {
+  Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind());
+
+  AutoCheckCannotGC nogc;
+  if (ShapeTable* table = get().maybeTable(nogc)) {
+    size += table->sizeOfIncludingThis(mallocSizeOf);
+  }
+
+  if (!get().inDictionary() && get().children.isShapeSet()) {
+    size +=
+        get().children.toShapeSet()->shallowSizeOfIncludingThis(mallocSizeOf);
+  }
+
+  return size;
+}
+
+JS::ubi::Node::Size JS::ubi::Concrete<js::BaseShape>::size(
+    mozilla::MallocSizeOf mallocSizeOf) const {
+  return js::gc::Arena::thingSize(get().asTenured().getAllocKind());
+}
+
+void PropertyResult::trace(JSTracer* trc) {
+  if (isNativeProperty()) {
+    TraceRoot(trc, &shape_, "PropertyResult::shape_");
+  }
+}