/* -*- 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(JSContext* 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(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());

    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->isEmptyShape() && shape->isDataProperty(),
                  nbase->slotSpan() > shape->slot());

    this->base_ = nbase->baseUnowned();
    nbase->adoptUnowned(shape->base()->toUnowned());

    shape->base_ = nbase;
}

/* static */ bool
Shape::hashify(JSContext* 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;
}

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 = 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(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
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(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. */
        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->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;
    }

    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(), &obj->shape_);
        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;
        }

        GCPtrShape* listp = dictionaryShape ? &dictionaryShape->parent : nullptr;
        StackShape child(shape);
        dprop->initDictionaryShape(child, obj->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(obj) &&
        !cx->nursery().queueDictionaryModeObjectToSweep(obj))
    {
        ReportOutOfMemory(cx);
        return false;
    }

    MOZ_ASSERT(root->listp == nullptr);
    root->listp = &obj->shape_;
    obj->shape_ = root;

    MOZ_ASSERT(obj->inDictionaryMode());
    root->base()->setSlotSpan(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 AutoKeepShapeTables& 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 AutoKeepShapeTables& 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 */ Shape*
NativeObject::addAccessorPropertyInternal(JSContext* cx,
                                          HandleNativeObject obj, HandleId id,
                                          GetterOp getter, SetterOp setter, unsigned attrs,
                                          ShapeTable* table, ShapeTable::Entry* entry,
                                          const AutoKeepShapeTables& keep)
{
    AutoCheckShapeConsistency check(obj);
    AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);

    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 AutoKeepShapeTables& 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(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(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 kid.
    do {
        AutoCheckCannotGC nogc;

        Shape* lastProperty = obj->lastProperty();
        if (lastProperty->inDictionary())
            break;

        KidsPointer* kidp = &lastProperty->kids;
        if (!kidp->isShape())
            break;

        Shape* kid = kidp->toShape();
        MOZ_ASSERT(!kid->inDictionary());

        if (kid->propidRaw() != id ||
            kid->isAccessorShape() ||
            kid->attributes() != JSPROP_ENUMERATE ||
            kid->base()->unowned() != lastProperty->base()->unowned())
        {
            break;
        }

        MOZ_ASSERT(kid->isDataProperty());

        kid = PropertyTreeReadBarrier(lastProperty, kid);
        if (!kid)
            break;

        if (!obj->setLastProperty(cx, kid))
            return nullptr;
        return kid;
    } while (0);

    AutoKeepShapeTables 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->lastProperty()->base()->slotSpan()) {
            if (MOZ_UNLIKELY(!obj->setSlotSpan(cx, slot + 1))) {
                new (shape) Shape(obj->lastProperty()->base()->unowned(), 0);
                return nullptr;
            }
        }
        shape->initDictionaryShape(child, obj->numFixedSlots(), &obj->shape_);
    } 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;
}

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];

        UnownedBaseShape* nbase = GetBaseShapeForNewShape(cx, newShape, id);
        if (!nbase)
            return nullptr;

        Rooted<StackShape> child(cx, StackShape(nbase, id, i, JSPROP_ENUMERATE));
        newShape = cx->zone()->propertyTree().getChild(cx, newShape, child);
        if (!newShape)
            return nullptr;
    }

    return newShape;
}

/*
 * 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.
    AutoKeepShapeTables 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->nonProxyIsExtensible(),
                       "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->base_ = nbase;

        shape->setSlot(slot);
        shape->attrs = uint8_t(attrs);
        shape->flags = 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);

    AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);

    // Search for id in order to claim its entry if table has been allocated.
    AutoKeepShapeTables 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->nonProxyIsExtensible(),
                       "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->base_ = nbase;

        shape->setSlot(SHAPE_INVALID_SLOT);
        shape->attrs = uint8_t(attrs);
        shape->flags = Shape::IN_DICTIONARY | Shape::ACCESSOR_SHAPE;

        AccessorShape& accShape = shape->asAccessorShape();
        accShape.rawGetter = getter;
        accShape.rawSetter = setter;
        GetterSetterWriteBarrierPost(&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

    MarkTypePropertyNonData(cx, obj, shape->propid());

    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_);

    AutoKeepShapeTables 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->base_ = 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. */
        JS_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 */ void
NativeObject::clear(JSContext* 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));

    obj->checkShapeConsistency();
}

/* static */ bool
NativeObject::rollbackProperties(JSContext* 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 (!NativeObject::removeProperty(cx, obj, obj->lastProperty()->propid()))
            return false;
    }

    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->listp);

    MOZ_ASSERT(newShape->parent == oldShape);
    oldShape->removeFromDictionary(obj);

    if (newShape == obj->lastProperty())
        oldShape->handoffTableTo(newShape);

    if (entry)
        entry->setPreservingCollision(newShape);
    return newShape;
}

/* static */ bool
NativeObject::shadowingShapeChange(JSContext* cx, HandleNativeObject obj, const Shape& shape)
{
    return generateOwnShape(cx, obj);
}

/* static */ bool
JSObject::setFlags(JSContext* cx, HandleObject obj, BaseShape::Flag flags,
                   GenerateShape generateShape)
{
    if (obj->hasAllFlags(flags))
        return true;

    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* existingShape = obj->ensureShape(cx);
    if (!existingShape)
        return false;

    Shape* newShape = Shape::setObjectFlags(cx, flags, obj->taggedProto(), existingShape);
    if (!newShape)
        return false;

    // The success of the |JSObject::ensureShape| call above means that |obj|
    // can be assumed to have a shape.
    obj->as<ShapedObject>().setShape(newShape);

    return true;
}

/* static */ bool
NativeObject::clearFlag(JSContext* cx, HandleNativeObject obj, BaseShape::Flag flag)
{
    MOZ_ASSERT(obj->inDictionaryMode());

    MOZ_ASSERT(obj->lastProperty()->getObjectFlags() & flag);

    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)
  : 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(JSContext* 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 (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(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)
{
}

#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 (auto r = initialShapes().all(); !r.empty(); r.popFront()) {
        InitialShapeEntry entry = r.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 == &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 KidsHash*
HashChildren(Shape* kid1, Shape* kid2)
{
    KidsHash* hash = js_new<KidsHash>();
    if (!hash || !hash->init(2)) {
        js_delete(hash);
        return nullptr;
    }

    hash->putNewInfallible(StackShape(kid1), kid1);
    hash->putNewInfallible(StackShape(kid2), kid2);
    return hash;
}

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_);

    KidsPointer* kidp = &parent->kids;

    if (kidp->isNull()) {
        child->setParent(parent);
        kidp->setShape(child);
        return true;
    }

    if (kidp->isShape()) {
        Shape* shape = kidp->toShape();
        MOZ_ASSERT(shape != child);
        MOZ_ASSERT(!shape->matches(child));

        KidsHash* hash = HashChildren(shape, child);
        if (!hash) {
            ReportOutOfMemory(cx);
            return false;
        }
        kidp->setHash(hash);
        child->setParent(parent);
        return true;
    }

    if (!kidp->toHash()->putNew(StackShape(child), child)) {
        ReportOutOfMemory(cx);
        return false;
    }

    child->setParent(parent);
    return true;
}

void
Shape::removeChild(Shape* child)
{
    MOZ_ASSERT(!child->inDictionary());
    MOZ_ASSERT(child->parent == this);

    KidsPointer* kidp = &kids;

    if (kidp->isShape()) {
        MOZ_ASSERT(kidp->toShape() == child);
        kidp->setNull();
        child->parent = nullptr;
        return;
    }

    KidsHash* hash = kidp->toHash();
    MOZ_ASSERT(hash->count() >= 2);      /* otherwise kidp->isShape() should be true */

#ifdef DEBUG
    size_t oldCount = hash->count();
#endif

    hash->remove(StackShape(child));
    child->parent = nullptr;

    MOZ_ASSERT(hash->count() == oldCount - 1);

    if (hash->count() == 1) {
        /* Convert from HASH form back to SHAPE form. */
        KidsHash::Range r = hash->all();
        Shape* otherChild = r.front();
        MOZ_ASSERT((r.popFront(), r.empty()));    /* No more elements! */
        kidp->setShape(otherChild);
        js_delete(hash);
    }
}

MOZ_ALWAYS_INLINE Shape*
PropertyTree::inlinedGetChild(JSContext* cx, Shape* parent, Handle<StackShape> child)
{
    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.
     */
    KidsPointer* kidp = &parent->kids;
    if (kidp->isShape()) {
        Shape* kid = kidp->toShape();
        if (kid->matches(child))
            existingShape = kid;
    } else if (kidp->isHash()) {
        if (KidsHash::Ptr p = kidp->toHash()->lookup(child))
            existingShape = *p;
    } else {
        /* If kidp->isNull(), we always insert. */
    }

    if (existingShape) {
        existingShape = PropertyTreeReadBarrier(parent, existingShape);
        if (existingShape)
            return existingShape;
    }

    RootedShape parentRoot(cx, parent);
    Shape* shape = Shape::new_(cx, child, 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()
{
    /*
     * 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.
     */
    if (parent && parent->isMarkedAny()) {
        if (inDictionary()) {
            if (parent->listp == &parent)
                parent->listp = nullptr;
        } else {
            parent->removeChild(this);
        }
    }
}

void
Shape::finalize(FreeOp* fop)
{
    if (!inDictionary() && kids.isHash())
        fop->delete_(kids.toHash());
}

void
Shape::fixupDictionaryShapeAfterMovingGC()
{
    if (!listp)
        return;

    // The listp field either points to the parent field of the next shape in
    // the list if there is one.  Otherwise if this shape is the last in the
    // list then it points to the shape_ field of the object the list is for.
    // We can tell which it is because the base shape is owned if this is the
    // last property and not otherwise.
    bool listpPointsIntoShape = !MaybeForwarded(base())->isOwned();

#ifdef DEBUG
    // Check that we got this right by interrogating the arena.
    // We use a fake cell pointer for this: it might not point to the beginning
    // of a cell, but will point into the right arena and will have the right
    // alignment.
    Cell* cell = reinterpret_cast<Cell*>(uintptr_t(listp) & ~CellAlignMask);
    AllocKind kind = TenuredCell::fromPointer(cell)->getAllocKind();
    MOZ_ASSERT_IF(listpPointsIntoShape, IsShapeAllocKind(kind));
    MOZ_ASSERT_IF(!listpPointsIntoShape, IsObjectAllocKind(kind));
#endif

    if (listpPointsIntoShape) {
        // listp points to the parent field of the next shape.
        Shape* next = reinterpret_cast<Shape*>(uintptr_t(listp) - offsetof(Shape, parent));
        if (gc::IsForwarded(next))
            listp = &gc::Forwarded(next)->parent;
    } else {
        // listp points to the shape_ field of an object.
        JSObject* last = reinterpret_cast<JSObject*>(uintptr_t(listp) - ShapedObject::offsetOfShape());
        if (gc::IsForwarded(last))
            listp = &gc::Forwarded(last)->as<NativeObject>().shape_;
    }
}

void
Shape::fixupShapeTreeAfterMovingGC()
{
    if (kids.isNull())
        return;

    if (kids.isShape()) {
        if (gc::IsForwarded(kids.toShape()))
            kids.setShape(gc::Forwarded(kids.toShape()));
        return;
    }

    MOZ_ASSERT(kids.isHash());
    KidsHash* kh = kids.toHash();
    for (KidsHash::Enum e(*kh); !e.empty(); e.popFront()) {
        Shape* key = e.front();
        if (IsForwarded(key))
            key = Forwarded(key);

        BaseShape* base = key->base();
        if (IsForwarded(base))
            base = Forwarded(base);
        UnownedBaseShape* unowned = base->unowned();
        if (IsForwarded(unowned))
            unowned = Forwarded(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->slotInfo & 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->kids.isHash()) {
        // Relocating the getterObj or setterObj will have changed our location
        // in our parent's KidsHash, 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);

        KidsHash* kh = parent->kids.toHash();
        MOZ_ALWAYS_TRUE(kh->rekeyAs(original, updated, this));
    }

    asAccessorShape().getterObj = postGetter;
    asAccessorShape().setterObj = postSetter;

    MOZ_ASSERT_IF(parent && !parent->inDictionary() && parent->kids.isHash(),
                  parent->kids.toHash()->has(StackShape(this)));
}

#ifdef DEBUG

void
KidsPointer::checkConsistency(Shape* aKid) const
{
    if (isShape()) {
        MOZ_ASSERT(toShape() == aKid);
    } else {
        MOZ_ASSERT(isHash());
        KidsHash* hash = toHash();
        KidsHash::Ptr ptr = hash->lookup(StackShape(aKid));
        MOZ_ASSERT(*ptr == aKid);
    }
}

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() ? 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("flags %x ", flags);
    if (flags) {
        int first = 1;
        out.putChar('(');
#define DUMP_FLAG(name, display) if (flags & 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 (!kids.isNull()) {
        ++level;
        if (kids.isShape()) {
            Shape* kid = kids.toShape();
            MOZ_ASSERT(kid->parent == this);
            kid->dumpSubtree(level, out);
        } else {
            const KidsHash& hash = *kids.toHash();
            for (KidsHash::Range range = hash.all(); !range.empty(); range.popFront()) {
                Shape* kid = range.front();

                MOZ_ASSERT(kid->parent == this);
                kid->dumpSubtree(level, out);
            }
        }
    }
}

#endif

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, JSContext* 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(JSContext* 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<InitialShapeSet>> 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(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(JSContext* 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(JSContext* 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
     * thread, as it will not use the new object cache for allocations.
     */
    if (!cx->helperThread())
        cx->caches().newObjectCache.invalidateEntriesForShape(cx, shape, proto);
}

void
Zone::fixupInitialShapeTable()
{
    if (!initialShapes().initialized())
        return;

    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();
        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());
}

void
PropertyResult::trace(JSTracer* trc)
{
    if (isNativeProperty())
        TraceRoot(trc, &shape_, "PropertyResult::shape_");
}