Add m-esr52 at 52.6.0

1 files changed, 1782 insertions, 0 deletions

diff --git a/js/src/vm/Shape.cpp b/js/src/vm/Shape.cpp
new file mode 100644
index 000000000..a64dc529a
--- /dev/null
+++ b/js/src/vm/Shape.cpp
@@ -0,0 +1,1782 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * 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/DebugOnly.h"
+#include "mozilla/MathAlgorithms.h"
+#include "mozilla/PodOperations.h"
+
+#include "jsatom.h"
+#include "jscntxt.h"
+#include "jshashutil.h"
+#include "jsobj.h"
+
+#include "gc/Policy.h"
+#include "js/HashTable.h"
+
+#include "jscntxtinlines.h"
+#include "jscompartmentinlines.h"
+#include "jsobjinlines.h"
+
+#include "vm/Caches-inl.h"
+#include "vm/NativeObject-inl.h"
+
+using namespace js;
+using namespace js::gc;
+
+using mozilla::CeilingLog2Size;
+using mozilla::DebugOnly;
+using mozilla::PodZero;
+using mozilla::RotateLeft;
+
+using JS::AutoCheckCannotGC;
+
+Shape* const ShapeTable::Entry::SHAPE_REMOVED = (Shape*)ShapeTable::Entry::SHAPE_COLLISION;
+
+bool
+ShapeTable::init(ExclusiveContext* cx, Shape* lastProp)
+{
+    uint32_t sizeLog2 = CeilingLog2Size(entryCount_);
+    uint32_t size = JS_BIT(sizeLog2);
+    if (entryCount_ >= size - (size >> 2))
+        sizeLog2++;
+    if (sizeLog2 < MIN_SIZE_LOG2)
+        sizeLog2 = MIN_SIZE_LOG2;
+
+    size = JS_BIT(sizeLog2);
+    entries_ = 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(listp);
+
+    MOZ_ASSERT(obj->shape_->inDictionary());
+    MOZ_ASSERT(obj->shape_->listp == &obj->shape_);
+
+    if (parent)
+        parent->listp = listp;
+    *listp = parent;
+    listp = nullptr;
+
+    obj->shape_->clearCachedBigEnoughForShapeTable();
+}
+
+void
+Shape::insertIntoDictionary(GCPtrShape* dictp)
+{
+    // Don't assert inDictionaryMode() here because we may be called from
+    // JSObject::toDictionaryMode via JSObject::newDictionaryShape.
+    MOZ_ASSERT(inDictionary());
+    MOZ_ASSERT(!listp);
+
+    MOZ_ASSERT_IF(*dictp, (*dictp)->inDictionary());
+    MOZ_ASSERT_IF(*dictp, (*dictp)->listp == dictp);
+    MOZ_ASSERT_IF(*dictp, zone() == (*dictp)->zone());
+
+    setParent(dictp->get());
+    if (parent)
+        parent->listp = &parent;
+    listp = (GCPtrShape*) dictp;
+    *dictp = this;
+}
+
+bool
+Shape::makeOwnBaseShape(ExclusiveContext* 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());
+
+    this->base_ = 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();
+
+    MOZ_ASSERT_IF(shape->hasSlot(), nbase->slotSpan() > shape->slot());
+
+    this->base_ = nbase->baseUnowned();
+    nbase->adoptUnowned(shape->base()->toUnowned());
+
+    shape->base_ = nbase;
+}
+
+/* static */ bool
+Shape::hashify(ExclusiveContext* cx, Shape* shape)
+{
+    MOZ_ASSERT(!shape->hasTable());
+
+    if (!shape->ensureOwnBaseShape(cx))
+        return false;
+
+    ShapeTable* table = cx->new_<ShapeTable>(shape->entryCount());
+    if (!table)
+        return false;
+
+    if (!table->init(cx, shape)) {
+        js_free(table);
+        return false;
+    }
+
+    shape->base()->setTable(table);
+    return true;
+}
+
+/*
+ * Double hashing needs the second hash code to be relatively prime to table
+ * size, so we simply make hash2 odd.
+ */
+static HashNumber
+Hash1(HashNumber hash0, uint32_t shift)
+{
+    return hash0 >> shift;
+}
+
+static HashNumber
+Hash2(HashNumber hash0, uint32_t log2, uint32_t shift)
+{
+    return ((hash0 << log2) >> shift) | 1;
+}
+
+template<MaybeAdding Adding>
+ShapeTable::Entry&
+ShapeTable::searchUnchecked(jsid id)
+{
+    MOZ_ASSERT(entries_);
+    MOZ_ASSERT(!JSID_IS_EMPTY(id));
+
+    /* Compute the primary hash address. */
+    HashNumber hash0 = HashId(id);
+    HashNumber hash1 = Hash1(hash0, hashShift_);
+    Entry* entry = &getEntry(hash1);
+
+    /* Miss: return space for a new entry. */
+    if (entry->isFree())
+        return *entry;
+
+    /* Hit: return entry. */
+    Shape* shape = entry->shape();
+    if (shape && shape->propidRaw() == id)
+        return *entry;
+
+    /* Collision: double hash. */
+    uint32_t sizeLog2 = HASH_BITS - hashShift_;
+    HashNumber hash2 = Hash2(hash0, sizeLog2, hashShift_);
+    uint32_t sizeMask = JS_BITMASK(sizeLog2);
+
+    /* Save the first removed entry pointer so we can recycle it if adding. */
+    Entry* firstRemoved;
+    if (Adding == MaybeAdding::Adding) {
+        if (entry->isRemoved()) {
+            firstRemoved = entry;
+        } else {
+            firstRemoved = nullptr;
+            if (!entry->hadCollision())
+                entry->flagCollision();
+        }
+    }
+
+#ifdef DEBUG
+    bool collisionFlag = true;
+    if (!entry->isRemoved())
+        collisionFlag = entry->hadCollision();
+#endif
+
+    while (true) {
+        hash1 -= hash2;
+        hash1 &= sizeMask;
+        entry = &getEntry(hash1);
+
+        if (entry->isFree())
+            return (Adding == MaybeAdding::Adding && firstRemoved) ? *firstRemoved : *entry;
+
+        shape = entry->shape();
+        if (shape && shape->propidRaw() == id) {
+            MOZ_ASSERT(collisionFlag);
+            return *entry;
+        }
+
+        if (Adding == MaybeAdding::Adding) {
+            if (entry->isRemoved()) {
+                if (!firstRemoved)
+                    firstRemoved = entry;
+            } else {
+                if (!entry->hadCollision())
+                    entry->flagCollision();
+            }
+        }
+
+#ifdef DEBUG
+        if (!entry->isRemoved())
+            collisionFlag &= entry->hadCollision();
+#endif
+    }
+
+    MOZ_CRASH("Shape::search failed to find an expected entry.");
+}
+
+template ShapeTable::Entry& ShapeTable::searchUnchecked<MaybeAdding::Adding>(jsid id);
+template ShapeTable::Entry& ShapeTable::searchUnchecked<MaybeAdding::NotAdding>(jsid id);
+
+bool
+ShapeTable::change(ExclusiveContext* 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 = JS_BIT(oldLog2);
+    uint32_t newSize = JS_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_;
+    entries_ = 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(ExclusiveContext* 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
+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);
+        }
+    }
+}
+
+#ifdef JSGC_HASH_TABLE_CHECKS
+
+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(ExclusiveContext* cx, StackBaseShape& base,
+                           TaggedProto proto, HandleShape shape)
+{
+    MOZ_ASSERT(!shape->inDictionary());
+
+    if (!shape->parent) {
+        /* Treat as resetting the initial property of the shape hierarchy. */
+        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 */ Shape*
+NativeObject::getChildPropertyOnDictionary(ExclusiveContext* cx, HandleNativeObject obj,
+                                           HandleShape parent, MutableHandle<StackShape> child)
+{
+    /*
+     * Shared properties have no slot, but slot_ will reflect that of parent.
+     * Unshared properties allocate a slot here but may lose it due to a
+     * JS_ClearScope call.
+     */
+    if (!child.hasSlot()) {
+        child.setSlot(parent->maybeSlot());
+    } else {
+        if (child.hasMissingSlot()) {
+            uint32_t slot;
+            if (!allocSlot(cx, obj, &slot))
+                return nullptr;
+            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())));
+        }
+    }
+
+    RootedShape shape(cx);
+
+    if (obj->inDictionaryMode()) {
+        MOZ_ASSERT(parent == obj->lastProperty());
+        shape = child.isAccessorShape() ? Allocate<AccessorShape>(cx) : Allocate<Shape>(cx);
+        if (!shape)
+            return nullptr;
+        if (child.hasSlot() && child.slot() >= obj->lastProperty()->base()->slotSpan()) {
+            if (!obj->setSlotSpan(cx, child.slot() + 1)) {
+                new (shape) Shape(obj->lastProperty()->base()->unowned(), 0);
+                return nullptr;
+            }
+        }
+        shape->initDictionaryShape(child, obj->numFixedSlots(), &obj->shape_);
+    }
+
+    return shape;
+}
+
+/* static */ Shape*
+NativeObject::getChildProperty(ExclusiveContext* cx,
+                               HandleNativeObject obj, HandleShape parent,
+                               MutableHandle<StackShape> child)
+{
+    Shape* shape = getChildPropertyOnDictionary(cx, obj, parent, child);
+
+    if (!obj->inDictionaryMode()) {
+        shape = cx->zone()->propertyTree.getChild(cx, parent, child);
+        if (!shape)
+            return nullptr;
+        //MOZ_ASSERT(shape->parent == parent);
+        //MOZ_ASSERT_IF(parent != lastProperty(), parent == lastProperty()->parent);
+        if (!obj->setLastProperty(cx, shape))
+            return nullptr;
+    }
+
+    return shape;
+}
+
+bool
+js::NativeObject::toDictionaryMode(ExclusiveContext* cx)
+{
+    MOZ_ASSERT(!inDictionaryMode());
+    MOZ_ASSERT(cx->isInsideCurrentCompartment(this));
+
+    uint32_t span = slotSpan();
+
+    Rooted<NativeObject*> self(cx, this);
+
+    // 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, lastProperty());
+    while (shape) {
+        MOZ_ASSERT(!shape->inDictionary());
+
+        Shape* dprop = shape->isAccessorShape() ? Allocate<AccessorShape>(cx) : Allocate<Shape>(cx);
+        if (!dprop) {
+            ReportOutOfMemory(cx);
+            return false;
+        }
+
+        GCPtrShape* listp = dictionaryShape ? &dictionaryShape->parent : nullptr;
+        StackShape child(shape);
+        dprop->initDictionaryShape(child, self->numFixedSlots(), listp);
+
+        if (!dictionaryShape)
+            root = dprop;
+
+        MOZ_ASSERT(!dprop->hasTable());
+        dictionaryShape = dprop;
+        shape = shape->previous();
+    }
+
+    if (!Shape::hashify(cx, root)) {
+        ReportOutOfMemory(cx);
+        return false;
+    }
+
+    if (IsInsideNursery(self) &&
+        !cx->asJSContext()->gc.nursery.queueDictionaryModeObjectToSweep(self))
+    {
+        ReportOutOfMemory(cx);
+        return false;
+    }
+
+    MOZ_ASSERT(root->listp == nullptr);
+    root->listp = &self->shape_;
+    self->shape_ = root;
+
+    MOZ_ASSERT(self->inDictionaryMode());
+    root->base()->setSlotSpan(span);
+
+    return true;
+}
+
+/* static */ Shape*
+NativeObject::addProperty(ExclusiveContext* cx, HandleNativeObject obj, HandleId id,
+                          GetterOp getter, SetterOp setter, uint32_t slot, unsigned attrs,
+                          unsigned flags, bool allowDictionary)
+{
+    MOZ_ASSERT(!JSID_IS_VOID(id));
+    MOZ_ASSERT(getter != JS_PropertyStub);
+    MOZ_ASSERT(setter != JS_StrictPropertyStub);
+
+    bool extensible;
+    if (!IsExtensible(cx, obj, &extensible))
+        return nullptr;
+    if (!extensible) {
+        if (cx->isJSContext())
+            obj->reportNotExtensible(cx->asJSContext());
+        return nullptr;
+    }
+
+    AutoKeepShapeTables keep(cx);
+    ShapeTable::Entry* entry = nullptr;
+    if (obj->inDictionaryMode()) {
+        ShapeTable* table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
+        if (!table)
+            return nullptr;
+        entry = &table->search<MaybeAdding::Adding>(id, keep);
+    }
+
+    return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags, entry,
+                               allowDictionary, keep);
+}
+
+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 */ Shape*
+NativeObject::addPropertyInternal(ExclusiveContext* cx,
+                                  HandleNativeObject obj, HandleId id,
+                                  GetterOp getter, SetterOp setter,
+                                  uint32_t slot, unsigned attrs,
+                                  unsigned flags, ShapeTable::Entry* entry,
+                                  bool allowDictionary, const AutoKeepShapeTables& keep)
+{
+    MOZ_ASSERT_IF(!allowDictionary, !obj->inDictionaryMode());
+    MOZ_ASSERT(getter != JS_PropertyStub);
+    MOZ_ASSERT(setter != JS_StrictPropertyStub);
+
+    AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
+
+    /*
+     * The code below deals with either converting obj to dictionary mode or
+     * growing an object that's already in dictionary mode. Either way,
+     * dictionray operations are safe if thread local.
+     */
+    ShapeTable* table = nullptr;
+    if (!obj->inDictionaryMode()) {
+        bool stableSlot =
+            (slot == SHAPE_INVALID_SLOT) ||
+            obj->lastProperty()->hasMissingSlot() ||
+            (slot == obj->lastProperty()->maybeSlot() + 1);
+        MOZ_ASSERT_IF(!allowDictionary, stableSlot);
+        if (allowDictionary &&
+            (!stableSlot || ShouldConvertToDictionary(obj)))
+        {
+            if (!obj->toDictionaryMode(cx))
+                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 shape(cx);
+    {
+        RootedShape last(cx, obj->lastProperty());
+
+        uint32_t index;
+        bool indexed = IdIsIndex(id, &index);
+
+        Rooted<UnownedBaseShape*> nbase(cx);
+        if (!indexed) {
+            nbase = last->base()->unowned();
+        } else {
+            StackBaseShape base(last->base());
+            base.flags |= BaseShape::INDEXED;
+            nbase = BaseShape::getUnowned(cx, base);
+            if (!nbase)
+                return nullptr;
+        }
+
+        Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs, flags));
+        child.updateGetterSetter(getter, setter);
+        shape = getChildProperty(cx, obj, last, &child);
+    }
+
+    if (shape) {
+        MOZ_ASSERT(shape == obj->lastProperty());
+
+        if (table) {
+            /* Store the tree node pointer in the table entry for id. */
+            entry->setPreservingCollision(shape);
+            table->incEntryCount();
+
+            /* Pass the table along to the new last property, namely shape. */
+            MOZ_ASSERT(shape->parent->maybeTable(keep) == table);
+            shape->parent->handoffTableTo(shape);
+        }
+
+        obj->checkShapeConsistency();
+        return shape;
+    }
+
+    obj->checkShapeConsistency();
+    return nullptr;
+}
+
+Shape*
+js::ReshapeForAllocKind(JSContext* cx, Shape* shape, TaggedProto proto,
+                                 gc::AllocKind allocKind)
+{
+    // Compute the number of fixed slots with the new allocation kind.
+    size_t nfixed = gc::GetGCKindSlots(allocKind, shape->getObjectClass());
+
+    // Get all the ids in the shape, in order.
+    js::AutoIdVector ids(cx);
+    {
+        for (unsigned i = 0; i < shape->slotSpan(); i++) {
+            if (!ids.append(JSID_VOID))
+                return nullptr;
+        }
+        Shape* nshape = shape;
+        while (!nshape->isEmptyShape()) {
+            ids[nshape->slot()].set(nshape->propid());
+            nshape = nshape->previous();
+        }
+    }
+
+    // Construct the new shape, without updating type information.
+    RootedId id(cx);
+    RootedShape newShape(cx, EmptyShape::getInitialShape(cx, shape->getObjectClass(),
+                                                         proto, nfixed, shape->getObjectFlags()));
+    if (!newShape)
+        return nullptr;
+
+    for (unsigned i = 0; i < ids.length(); i++) {
+        id = ids[i];
+
+        uint32_t index;
+        bool indexed = IdIsIndex(id, &index);
+
+        Rooted<UnownedBaseShape*> nbase(cx, newShape->base()->unowned());
+        if (indexed) {
+            StackBaseShape base(nbase);
+            base.flags |= BaseShape::INDEXED;
+            nbase = BaseShape::getUnowned(cx, base);
+            if (!nbase)
+                return nullptr;
+        }
+
+        Rooted<StackShape> child(cx, StackShape(nbase, id, i, JSPROP_ENUMERATE, 0));
+        newShape = cx->zone()->propertyTree.getChild(cx, newShape, child);
+        if (!newShape)
+            return nullptr;
+    }
+
+    return newShape;
+}
+
+/*
+ * Check and adjust the new attributes for the shape to make sure that our
+ * slot access optimizations are sound. It is responsibility of the callers to
+ * enforce all restrictions from ECMA-262 v5 8.12.9 [[DefineOwnProperty]].
+ */
+static inline bool
+CheckCanChangeAttrs(ExclusiveContext* cx, JSObject* obj, Shape* shape, unsigned* attrsp)
+{
+    if (shape->configurable())
+        return true;
+
+    /* A permanent property must stay permanent. */
+    *attrsp |= JSPROP_PERMANENT;
+
+    /* Reject attempts to remove a slot from the permanent data property. */
+    if (shape->isDataDescriptor() && shape->hasSlot() &&
+        (*attrsp & (JSPROP_GETTER | JSPROP_SETTER | JSPROP_SHARED)))
+    {
+        if (cx->isJSContext())
+            obj->reportNotConfigurable(cx->asJSContext(), shape->propid());
+        return false;
+    }
+
+    return true;
+}
+
+/* static */ Shape*
+NativeObject::putProperty(ExclusiveContext* cx, HandleNativeObject obj, HandleId id,
+                          GetterOp getter, SetterOp setter, uint32_t slot, unsigned attrs,
+                          unsigned flags)
+{
+    MOZ_ASSERT(!JSID_IS_VOID(id));
+    MOZ_ASSERT(getter != JS_PropertyStub);
+    MOZ_ASSERT(setter != JS_StrictPropertyStub);
+
+#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
+
+    AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
+
+    /*
+     * Search for id in order to claim its entry if table has been allocated.
+     *
+     * Note that we can only try to claim an entry in a table that is thread
+     * local. An object may be thread local *without* its shape being thread
+     * local. The only thread local objects that *also* have thread local
+     * shapes are dictionaries that were allocated/converted thread
+     * locally. Only for those objects we can try to claim an entry in its
+     * shape table.
+     */
+    AutoKeepShapeTables keep(cx);
+    ShapeTable::Entry* entry;
+    RootedShape shape(cx);
+    if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep,
+                                            shape.address(), &entry))
+    {
+        return nullptr;
+    }
+
+    if (!shape) {
+        /*
+         * You can't add properties to a non-extensible object, but you can change
+         * attributes of properties in such objects.
+         */
+        bool extensible;
+
+        if (!IsExtensible(cx, obj, &extensible))
+            return nullptr;
+
+        if (!extensible) {
+            if (cx->isJSContext())
+                obj->reportNotExtensible(cx->asJSContext());
+            return nullptr;
+        }
+
+        return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags,
+                                   entry, true, keep);
+    }
+
+    /* Property exists: search must have returned a valid entry. */
+    MOZ_ASSERT_IF(entry, !entry->isRemoved());
+
+    if (!CheckCanChangeAttrs(cx, obj, shape, &attrs))
+        return nullptr;
+
+    /*
+     * 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->hasSlot();
+    uint32_t oldSlot = shape->maybeSlot();
+    if (!(attrs & JSPROP_SHARED) && slot == SHAPE_INVALID_SLOT && hadSlot)
+        slot = oldSlot;
+
+    Rooted<UnownedBaseShape*> nbase(cx);
+    {
+        uint32_t index;
+        bool indexed = IdIsIndex(id, &index);
+        StackBaseShape base(obj->lastProperty()->base());
+        if (indexed)
+            base.flags |= BaseShape::INDEXED;
+        nbase = BaseShape::getUnowned(cx, base);
+        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, flags, getter, setter))
+        return shape;
+
+    /*
+     * Overwriting a non-last property requires switching to dictionary mode.
+     * The shape tree is shared immutable, and we can't removeProperty and then
+     * addPropertyInternal because a failure under add would lose data.
+     */
+    if (shape != obj->lastProperty() && !obj->inDictionaryMode()) {
+        if (!obj->toDictionaryMode(cx))
+            return nullptr;
+        ShapeTable* table = obj->lastProperty()->maybeTable(keep);
+        MOZ_ASSERT(table);
+        entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
+        shape = entry->shape();
+    }
+
+    MOZ_ASSERT_IF(shape->hasSlot() && !(attrs & JSPROP_SHARED), 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());
+        bool accessorShape = getter || setter || (attrs & (JSPROP_GETTER | JSPROP_SETTER));
+        shape = obj->replaceWithNewEquivalentShape(cx, shape, nullptr, accessorShape);
+        if (!shape)
+            return nullptr;
+        if (!updateLast && !obj->generateOwnShape(cx))
+            return nullptr;
+
+        /*
+         * FIXME bug 593129 -- slot allocation and NativeObject *this must move
+         * out of here!
+         */
+        if (slot == SHAPE_INVALID_SLOT && !(attrs & JSPROP_SHARED)) {
+            if (!allocSlot(cx, obj, &slot))
+                return nullptr;
+        }
+
+        if (updateLast)
+            shape->base()->adoptUnowned(nbase);
+        else
+            shape->base_ = nbase;
+
+        MOZ_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
+
+        shape->setSlot(slot);
+        shape->attrs = uint8_t(attrs);
+        shape->flags = flags | Shape::IN_DICTIONARY | (accessorShape ? Shape::ACCESSOR_SHAPE : 0);
+        if (shape->isAccessorShape()) {
+            AccessorShape& accShape = shape->asAccessorShape();
+            accShape.rawGetter = getter;
+            accShape.rawSetter = setter;
+            GetterSetterWriteBarrierPost(&accShape);
+        } else {
+            MOZ_ASSERT(!getter);
+            MOZ_ASSERT(!setter);
+        }
+    } else {
+        /*
+         * Updating the last property in a non-dictionary-mode object. Find an
+         * alternate shared child of the last property's previous shape.
+         */
+        StackBaseShape base(obj->lastProperty()->base());
+
+        UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
+        if (!nbase)
+            return nullptr;
+
+        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, flags));
+        child.updateGetterSetter(getter, setter);
+        RootedShape parent(cx, shape->parent);
+        Shape* newShape = getChildProperty(cx, obj, parent, &child);
+
+        if (!newShape) {
+            obj->checkShapeConsistency();
+            return nullptr;
+        }
+
+        shape = newShape;
+    }
+
+    /*
+     * Can't fail now, so free the previous incarnation's slot if the new shape
+     * has no slot. But we do not need to free oldSlot (and must not, as trying
+     * to will botch an assertion in JSObject::freeSlot) if the new last
+     * property (shape here) has a slotSpan that does not cover it.
+     */
+    if (hadSlot && !shape->hasSlot()) {
+        if (oldSlot < obj->slotSpan())
+            obj->freeSlot(cx, oldSlot);
+        /* Note: The optimization based on propertyRemovals is only relevant to the main thread. */
+        if (cx->isJSContext())
+            ++cx->asJSContext()->runtime()->propertyRemovals;
+    }
+
+    obj->checkShapeConsistency();
+
+    return shape;
+}
+
+/* static */ Shape*
+NativeObject::changeProperty(ExclusiveContext* cx, HandleNativeObject obj, HandleShape shape,
+                             unsigned attrs, GetterOp getter, SetterOp setter)
+{
+    MOZ_ASSERT(obj->containsPure(shape));
+    MOZ_ASSERT(getter != JS_PropertyStub);
+    MOZ_ASSERT(setter != JS_StrictPropertyStub);
+    MOZ_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
+
+    /* Allow only shared (slotless) => unshared (slotful) transition. */
+    MOZ_ASSERT(!((attrs ^ shape->attrs) & JSPROP_SHARED) ||
+               !(attrs & JSPROP_SHARED));
+
+    MarkTypePropertyNonData(cx, obj, shape->propid());
+
+    if (!CheckCanChangeAttrs(cx, obj, shape, &attrs))
+        return nullptr;
+
+    if (shape->attrs == attrs && shape->getter() == getter && shape->setter() == setter)
+        return shape;
+
+    /*
+     * Let JSObject::putProperty handle this |overwriting| case, including
+     * the conservation of shape->slot (if it's valid). We must not call
+     * removeProperty because it will free an allocated shape->slot, and
+     * putProperty won't re-allocate it.
+     */
+    RootedId propid(cx, shape->propid());
+    Shape* newShape = putProperty(cx, obj, propid, getter, setter,
+                                  shape->maybeSlot(), attrs, shape->flags);
+
+    obj->checkShapeConsistency();
+    return newShape;
+}
+
+bool
+NativeObject::removeProperty(ExclusiveContext* cx, jsid id_)
+{
+    RootedId id(cx, id_);
+    RootedNativeObject self(cx, this);
+
+    AutoKeepShapeTables keep(cx);
+    ShapeTable::Entry* entry;
+    RootedShape shape(cx);
+    if (!Shape::search(cx, lastProperty(), id, keep, shape.address(), &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 (!self->inDictionaryMode() && (shape != self->lastProperty() || !self->canRemoveLastProperty())) {
+        if (!self->toDictionaryMode(cx))
+            return false;
+        ShapeTable* table = self->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 (self->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 == self->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, self->lastProperty()->parent);
+            StackBaseShape base(self->lastProperty()->base());
+            BaseShape* nbase = BaseShape::getUnowned(cx, base);
+            if (!nbase)
+                return false;
+            previous->base_ = nbase;
+        }
+    }
+
+    /* If shape has a slot, free its slot number. */
+    if (shape->hasSlot()) {
+        self->freeSlot(cx, shape->slot());
+        if (cx->isJSContext())
+            ++cx->asJSContext()->runtime()->propertyRemovals;
+    }
+
+    /*
+     * 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 (self->inDictionaryMode()) {
+        ShapeTable* table = self->lastProperty()->maybeTable(keep);
+        MOZ_ASSERT(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 = self->lastProperty();
+            for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent)
+                MOZ_ASSERT_IF(aprop != shape, self->contains(cx, aprop));
+#endif
+        }
+
+        {
+            /* Remove shape from its non-circular doubly linked list. */
+            Shape* oldLastProp = self->lastProperty();
+            shape->removeFromDictionary(self);
+
+            /* Hand off table from the old to new last property. */
+            oldLastProp->handoffTableTo(self->lastProperty());
+        }
+
+        /* Generate a new shape for the object, infallibly. */
+        JS_ALWAYS_TRUE(self->generateOwnShape(cx, 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 == self->lastProperty());
+        self->removeLastProperty(cx);
+    }
+
+    self->checkShapeConsistency();
+    return true;
+}
+
+/* static */ void
+NativeObject::clear(ExclusiveContext* cx, HandleNativeObject obj)
+{
+    Shape* shape = obj->lastProperty();
+    MOZ_ASSERT(obj->inDictionaryMode() == shape->inDictionary());
+
+    while (shape->parent) {
+        shape = shape->parent;
+        MOZ_ASSERT(obj->inDictionaryMode() == shape->inDictionary());
+    }
+    MOZ_ASSERT(shape->isEmptyShape());
+
+    if (obj->inDictionaryMode())
+        shape->listp = &obj->shape_;
+
+    JS_ALWAYS_TRUE(obj->setLastProperty(cx, shape));
+
+    if (cx->isJSContext())
+        ++cx->asJSContext()->runtime()->propertyRemovals;
+    obj->checkShapeConsistency();
+}
+
+/* static */ bool
+NativeObject::rollbackProperties(ExclusiveContext* cx, HandleNativeObject obj, uint32_t slotSpan)
+{
+    /*
+     * Remove properties from this object until it has a matching slot span.
+     * The object cannot have escaped in a way which would prevent safe
+     * removal of the last properties.
+     */
+    MOZ_ASSERT(!obj->inDictionaryMode() && slotSpan <= obj->slotSpan());
+    while (true) {
+        if (obj->lastProperty()->isEmptyShape()) {
+            MOZ_ASSERT(slotSpan == 0);
+            break;
+        } else {
+            uint32_t slot = obj->lastProperty()->slot();
+            if (slot < slotSpan)
+                break;
+        }
+        if (!obj->removeProperty(cx, obj->lastProperty()->propid()))
+            return false;
+    }
+
+    return true;
+}
+
+Shape*
+NativeObject::replaceWithNewEquivalentShape(ExclusiveContext* cx, Shape* oldShape, Shape* newShape,
+                                            bool accessorShape)
+{
+    MOZ_ASSERT(cx->isInsideCurrentZone(oldShape));
+    MOZ_ASSERT_IF(oldShape != lastProperty(),
+                  inDictionaryMode() && lookup(cx, oldShape->propidRef()) == oldShape);
+
+    NativeObject* self = this;
+
+    if (!inDictionaryMode()) {
+        RootedNativeObject selfRoot(cx, self);
+        RootedShape newRoot(cx, newShape);
+        if (!toDictionaryMode(cx))
+            return nullptr;
+        oldShape = selfRoot->lastProperty();
+        self = selfRoot;
+        newShape = newRoot;
+    }
+
+    if (!newShape) {
+        RootedNativeObject selfRoot(cx, self);
+        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);
+        self = selfRoot;
+        oldShape = oldRoot;
+    }
+
+    AutoCheckCannotGC nogc;
+    ShapeTable* table = self->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, self->numFixedSlots(), oldShape->listp);
+
+    MOZ_ASSERT(newShape->parent == oldShape);
+    oldShape->removeFromDictionary(self);
+
+    if (newShape == self->lastProperty())
+        oldShape->handoffTableTo(newShape);
+
+    if (entry)
+        entry->setPreservingCollision(newShape);
+    return newShape;
+}
+
+bool
+NativeObject::shadowingShapeChange(ExclusiveContext* cx, const Shape& shape)
+{
+    return generateOwnShape(cx);
+}
+
+bool
+JSObject::setFlags(ExclusiveContext* cx, BaseShape::Flag flags, GenerateShape generateShape)
+{
+    if (hasAllFlags(flags))
+        return true;
+
+    RootedObject self(cx, this);
+
+    if (isNative() && as<NativeObject>().inDictionaryMode()) {
+        if (generateShape == GENERATE_SHAPE && !as<NativeObject>().generateOwnShape(cx))
+            return false;
+        StackBaseShape base(self->as<NativeObject>().lastProperty());
+        base.flags |= flags;
+        UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
+        if (!nbase)
+            return false;
+
+        self->as<NativeObject>().lastProperty()->base()->adoptUnowned(nbase);
+        return true;
+    }
+
+    Shape* existingShape = self->ensureShape(cx);
+    if (!existingShape)
+        return false;
+
+    Shape* newShape = Shape::setObjectFlags(cx, flags, self->taggedProto(), existingShape);
+    if (!newShape)
+        return false;
+
+    // The success of the |JSObject::ensureShape| call above means that |self|
+    // can be assumed to have a shape.
+    self->as<ShapedObject>().setShape(newShape);
+
+    return true;
+}
+
+bool
+NativeObject::clearFlag(ExclusiveContext* cx, BaseShape::Flag flag)
+{
+    MOZ_ASSERT(inDictionaryMode());
+
+    RootedNativeObject self(cx, &as<NativeObject>());
+    MOZ_ASSERT(self->lastProperty()->getObjectFlags() & flag);
+
+    StackBaseShape base(self->lastProperty());
+    base.flags &= ~flag;
+    UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
+    if (!nbase)
+        return false;
+
+    self->lastProperty()->base()->adoptUnowned(nbase);
+    return true;
+}
+
+/* static */ Shape*
+Shape::setObjectFlags(ExclusiveContext* 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);
+}
+
+/* static */ inline HashNumber
+StackBaseShape::hash(const Lookup& lookup)
+{
+    HashNumber hash = lookup.flags;
+    hash = RotateLeft(hash, 4) ^ (uintptr_t(lookup.clasp) >> 3);
+    return hash;
+}
+
+/* static */ inline bool
+StackBaseShape::match(ReadBarriered<UnownedBaseShape*> key, const Lookup& lookup)
+{
+    return key.unbarrieredGet()->flags == lookup.flags &&
+           key.unbarrieredGet()->clasp_ == lookup.clasp;
+}
+
+inline
+BaseShape::BaseShape(const StackBaseShape& base)
+  : clasp_(base.clasp),
+    flags(base.flags),
+    slotSpan_(0),
+    unowned_(nullptr),
+    table_(nullptr)
+{
+}
+
+/* static */ void
+BaseShape::copyFromUnowned(BaseShape& dest, UnownedBaseShape& src)
+{
+    dest.clasp_ = src.clasp_;
+    dest.slotSpan_ = src.slotSpan_;
+    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());
+
+    uint32_t span = slotSpan();
+
+    BaseShape::copyFromUnowned(*this, *other);
+    setSlotSpan(span);
+
+    assertConsistency();
+}
+
+/* static */ UnownedBaseShape*
+BaseShape::getUnowned(ExclusiveContext* cx, StackBaseShape& base)
+{
+    auto& table = cx->zone()->baseShapes;
+
+    if (!table.initialized() && !table.init()) {
+        ReportOutOfMemory(cx);
+        return nullptr;
+    }
+
+    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)
+{
+    traceChildrenSkipShapeTable(trc);
+    traceShapeTable(trc);
+}
+
+void
+BaseShape::traceChildrenSkipShapeTable(JSTracer* trc)
+{
+    if (isOwned())
+        TraceEdge(trc, &unowned_, "base");
+
+    assertConsistency();
+}
+
+void
+BaseShape::traceShapeTable(JSTracer* trc)
+{
+    AutoCheckCannotGC nogc;
+    if (ShapeTable* table = maybeTable(nogc))
+        table->trace(trc);
+}
+
+#ifdef DEBUG
+bool
+BaseShape::canSkipMarkingShapeTable(Shape* lastShape)
+{
+    // Check that every shape in the shape table will be marked by marking
+    // |lastShape|.
+
+    AutoCheckCannotGC nogc;
+    ShapeTable* table = maybeTable(nogc);
+    if (!table)
+        return true;
+
+    uint32_t count = 0;
+    for (Shape::Range<NoGC> r(lastShape); !r.empty(); r.popFront()) {
+        Shape* shape = &r.front();
+        ShapeTable::Entry& entry = table->search<MaybeAdding::NotAdding>(shape->propid(), nogc);
+        if (entry.isLive())
+            count++;
+    }
+
+    return count == table->entryCount();
+}
+#endif
+
+#ifdef JSGC_HASH_TABLE_CHECKS
+
+void
+Zone::checkBaseShapeTableAfterMovingGC()
+{
+    if (!baseShapes.initialized())
+        return;
+
+    for (decltype(baseShapes)::Enum e(baseShapes); !e.empty(); e.popFront()) {
+        UnownedBaseShape* base = e.front().unbarrieredGet();
+        CheckGCThingAfterMovingGC(base);
+
+        BaseShapeSet::Ptr ptr = baseShapes.lookup(base);
+        MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &e.front());
+    }
+}
+
+#endif // JSGC_HASH_TABLE_CHECKS
+
+void
+BaseShape::finalize(FreeOp* fop)
+{
+    if (table_) {
+        fop->delete_(table_);
+        table_ = nullptr;
+    }
+}
+
+inline
+InitialShapeEntry::InitialShapeEntry() : shape(nullptr), proto()
+{
+}
+
+inline
+InitialShapeEntry::InitialShapeEntry(Shape* shape, const Lookup::ShapeProto& proto)
+  : shape(shape), proto(proto)
+{
+}
+
+/* static */ inline HashNumber
+InitialShapeEntry::hash(const Lookup& lookup)
+{
+    return (RotateLeft(uintptr_t(lookup.clasp) >> 3, 4) ^ lookup.proto.hashCode()) +
+           lookup.nfixed;
+}
+
+/* static */ inline bool
+InitialShapeEntry::match(const InitialShapeEntry& key, const Lookup& lookup)
+{
+    const Shape* shape = key.shape.unbarrieredGet();
+    return lookup.clasp == shape->getObjectClass()
+        && lookup.nfixed == shape->numFixedSlots()
+        && lookup.baseFlags == shape->getObjectFlags()
+        && lookup.proto.match(key.proto);
+}
+
+#ifdef JSGC_HASH_TABLE_CHECKS
+
+void
+Zone::checkInitialShapesTableAfterMovingGC()
+{
+    if (!initialShapes.initialized())
+        return;
+
+    /*
+     * 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 (decltype(initialShapes)::Enum e(initialShapes); !e.empty(); e.popFront()) {
+        InitialShapeEntry entry = e.front();
+        JSProtoKey protoKey = entry.proto.key();
+        TaggedProto proto = entry.proto.proto().unbarrieredGet();
+        Shape* shape = entry.shape.unbarrieredGet();
+
+        CheckGCThingAfterMovingGC(shape);
+        if (proto.isObject())
+            CheckGCThingAfterMovingGC(proto.toObject());
+
+        using Lookup = InitialShapeEntry::Lookup;
+        Lookup lookup(shape->getObjectClass(),
+                      Lookup::ShapeProto(protoKey, proto),
+                      shape->numFixedSlots(),
+                      shape->getObjectFlags());
+        InitialShapeSet::Ptr ptr = initialShapes.lookup(lookup);
+        MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &e.front());
+    }
+}
+
+#endif // JSGC_HASH_TABLE_CHECKS
+
+Shape*
+EmptyShape::new_(ExclusiveContext* 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;
+}
+
+static bool
+IsOriginalProto(GlobalObject* global, JSProtoKey key, JSObject& proto)
+{
+    if (global->getPrototype(key) != ObjectValue(proto))
+        return false;
+
+    if (key == JSProto_Object) {
+        MOZ_ASSERT(proto.staticPrototypeIsImmutable(),
+                   "proto should be Object.prototype, whose prototype is "
+                   "immutable");
+        MOZ_ASSERT(proto.staticPrototype() == nullptr,
+                   "Object.prototype must have null prototype");
+        return true;
+    }
+
+    // Check that other prototypes still have Object.prototype as proto.
+    JSObject* protoProto = proto.staticPrototype();
+    if (!protoProto || global->getPrototype(JSProto_Object) != ObjectValue(*protoProto))
+        return false;
+
+    MOZ_ASSERT(protoProto->staticPrototypeIsImmutable(),
+               "protoProto should be Object.prototype, whose prototype is "
+               "immutable");
+    MOZ_ASSERT(protoProto->staticPrototype() == nullptr,
+               "Object.prototype must have null prototype");
+    return true;
+}
+
+static JSProtoKey
+GetInitialShapeProtoKey(TaggedProto proto, ExclusiveContext* cx)
+{
+    if (proto.isObject() && proto.toObject()->hasStaticPrototype()) {
+        GlobalObject* global = cx->global();
+        JSObject& obj = *proto.toObject();
+        MOZ_ASSERT(global == &obj.global());
+
+        if (IsOriginalProto(global, JSProto_Object, obj))
+            return JSProto_Object;
+        if (IsOriginalProto(global, JSProto_Function, obj))
+            return JSProto_Function;
+        if (IsOriginalProto(global, JSProto_Array, obj))
+            return JSProto_Array;
+        if (IsOriginalProto(global, JSProto_RegExp, obj))
+            return JSProto_RegExp;
+    }
+    return JSProto_LIMIT;
+}
+
+/* static */ Shape*
+EmptyShape::getInitialShape(ExclusiveContext* cx, const Class* clasp, TaggedProto proto,
+                            size_t nfixed, uint32_t objectFlags)
+{
+    MOZ_ASSERT_IF(proto.isObject(), cx->isInsideCurrentCompartment(proto.toObject()));
+
+    auto& table = cx->zone()->initialShapes;
+
+    if (!table.initialized() && !table.init()) {
+        ReportOutOfMemory(cx);
+        return nullptr;
+    }
+
+    using Lookup = InitialShapeEntry::Lookup;
+    auto protoPointer = MakeDependentAddPtr(cx, table,
+                                            Lookup(clasp, Lookup::ShapeProto(proto),
+                                                   nfixed, objectFlags));
+    if (protoPointer)
+        return protoPointer->shape;
+
+    // No entry for this proto. If the proto is one of a few common builtin
+    // prototypes, try to do a lookup based on the JSProtoKey, so we can share
+    // shapes across globals.
+    Rooted<TaggedProto> protoRoot(cx, proto);
+    Shape* shape = nullptr;
+    bool insertKey = false;
+    mozilla::Maybe<DependentAddPtr<decltype(cx->zone()->initialShapes)>> keyPointer;
+
+    JSProtoKey key = GetInitialShapeProtoKey(protoRoot, cx);
+    if (key != JSProto_LIMIT) {
+        keyPointer.emplace(MakeDependentAddPtr(cx, table,
+                                               Lookup(clasp, Lookup::ShapeProto(key),
+                                                      nfixed, objectFlags)));
+        if (keyPointer.ref()) {
+            shape = keyPointer.ref()->shape;
+            MOZ_ASSERT(shape);
+        } else {
+            insertKey = true;
+        }
+    }
+
+    if (!shape) {
+        StackBaseShape base(cx, clasp, objectFlags);
+        Rooted<UnownedBaseShape*> nbase(cx, BaseShape::getUnowned(cx, base));
+        if (!nbase)
+            return nullptr;
+
+        shape = EmptyShape::new_(cx, nbase, nfixed);
+        if (!shape)
+            return nullptr;
+    }
+
+    Lookup::ShapeProto shapeProto(protoRoot);
+    Lookup lookup(clasp, shapeProto, nfixed, objectFlags);
+    if (!protoPointer.add(cx, table, lookup, InitialShapeEntry(shape, shapeProto)))
+        return nullptr;
+
+    // Also add an entry based on the JSProtoKey, if needed.
+    if (insertKey) {
+        Lookup::ShapeProto shapeProto(key);
+        Lookup lookup(clasp, shapeProto, nfixed, objectFlags);
+        if (!keyPointer->add(cx, table, lookup, InitialShapeEntry(shape, shapeProto)))
+            return nullptr;
+    }
+
+    return shape;
+}
+
+/* static */ Shape*
+EmptyShape::getInitialShape(ExclusiveContext* cx, const Class* clasp, TaggedProto proto,
+                            AllocKind kind, uint32_t objectFlags)
+{
+    return getInitialShape(cx, clasp, proto, GetGCKindSlots(kind, clasp), objectFlags);
+}
+
+void
+NewObjectCache::invalidateEntriesForShape(JSContext* cx, HandleShape shape, HandleObject proto)
+{
+    const Class* clasp = shape->getObjectClass();
+
+    gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots());
+    if (CanBeFinalizedInBackground(kind, clasp))
+        kind = GetBackgroundAllocKind(kind);
+
+    RootedObjectGroup group(cx, ObjectGroup::defaultNewGroup(cx, clasp, TaggedProto(proto)));
+    if (!group) {
+        purge();
+        cx->recoverFromOutOfMemory();
+        return;
+    }
+
+    EntryIndex entry;
+    for (CompartmentsInZoneIter comp(shape->zone()); !comp.done(); comp.next()) {
+        if (GlobalObject* global = comp->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(ExclusiveContext* cx, HandleShape shape, HandleObject proto)
+{
+    using Lookup = InitialShapeEntry::Lookup;
+    Lookup lookup(shape->getObjectClass(), Lookup::ShapeProto(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 = ReadBarrieredShape(shape);
+
+    // For certain prototypes -- namely, those of various builtin classes,
+    // keyed by JSProtoKey |key| -- there are two entries: one for a lookup
+    // via |proto|, and one for a lookup via |key|.  If this is such a
+    // prototype, also update the alternate |key|-keyed shape.
+    JSProtoKey key = GetInitialShapeProtoKey(TaggedProto(proto), cx);
+    if (key != JSProto_LIMIT) {
+        Lookup lookup(shape->getObjectClass(), Lookup::ShapeProto(key),
+                      shape->numFixedSlots(), shape->getObjectFlags());
+        if (InitialShapeSet::Ptr p = cx->zone()->initialShapes.lookup(lookup)) {
+            InitialShapeEntry& entry = const_cast<InitialShapeEntry&>(*p);
+            if (entry.shape != shape)
+                entry.shape = ReadBarrieredShape(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 the main
+     * thread, as it will not use the new object cache for allocations.
+     */
+    if (cx->isJSContext()) {
+        JSContext* ncx = cx->asJSContext();
+        ncx->caches.newObjectCache.invalidateEntriesForShape(ncx, shape, proto);
+    }
+}
+
+void
+Zone::fixupInitialShapeTable()
+{
+    if (!initialShapes.initialized())
+        return;
+
+    for (decltype(initialShapes)::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();
+        if (entry.proto.proto().isObject() && IsForwarded(entry.proto.proto().toObject())) {
+            entry.proto.setProto(TaggedProto(Forwarded(entry.proto.proto().toObject())));
+            using Lookup = InitialShapeEntry::Lookup;
+            Lookup relookup(shape->getObjectClass(),
+                            Lookup::ShapeProto(entry.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().kids.isHash())
+        size += get().kids.toHash()->sizeOfIncludingThis(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());
+}