michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef vm_Shape_h
michael@0: #define vm_Shape_h
michael@0: 
michael@0: #include "mozilla/Attributes.h"
michael@0: #include "mozilla/GuardObjects.h"
michael@0: #include "mozilla/MathAlgorithms.h"
michael@0: #include "mozilla/Maybe.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/TemplateLib.h"
michael@0: 
michael@0: #include "jsapi.h"
michael@0: #include "jsfriendapi.h"
michael@0: #include "jsinfer.h"
michael@0: #include "jspropertytree.h"
michael@0: #include "jstypes.h"
michael@0: #include "NamespaceImports.h"
michael@0: 
michael@0: #include "gc/Barrier.h"
michael@0: #include "gc/Heap.h"
michael@0: #include "gc/Marking.h"
michael@0: #include "gc/Rooting.h"
michael@0: #include "js/HashTable.h"
michael@0: #include "js/RootingAPI.h"
michael@0: 
michael@0: #ifdef _MSC_VER
michael@0: #pragma warning(push)
michael@0: #pragma warning(disable:4800)
michael@0: #pragma warning(push)
michael@0: #pragma warning(disable:4100) /* Silence unreferenced formal parameter warnings */
michael@0: #endif
michael@0: 
michael@0: /*
michael@0:  * In isolation, a Shape represents a property that exists in one or more
michael@0:  * objects; it has an id, flags, etc. (But it doesn't represent the property's
michael@0:  * value.)  However, Shapes are always stored in linked linear sequence of
michael@0:  * Shapes, called "shape lineages". Each shape lineage represents the layout of
michael@0:  * an entire object.
michael@0:  *
michael@0:  * Every JSObject has a pointer, |shape_|, accessible via lastProperty(), to
michael@0:  * the last Shape in a shape lineage, which identifies the property most
michael@0:  * recently added to the object.  This pointer permits fast object layout
michael@0:  * tests. The shape lineage order also dictates the enumeration order for the
michael@0:  * object; ECMA requires no particular order but this implementation has
michael@0:  * promised and delivered property definition order.
michael@0:  *
michael@0:  * Shape lineages occur in two kinds of data structure.
michael@0:  *
michael@0:  * 1. N-ary property trees. Each path from a non-root node to the root node in
michael@0:  *    a property tree is a shape lineage. Property trees permit full (or
michael@0:  *    partial) sharing of Shapes between objects that have fully (or partly)
michael@0:  *    identical layouts. The root is an EmptyShape whose identity is determined
michael@0:  *    by the object's class, compartment and prototype. These Shapes are shared
michael@0:  *    and immutable.
michael@0:  *
michael@0:  * 2. Dictionary mode lists. Shapes in such lists are said to be "in
michael@0:  *    dictionary mode", as are objects that point to such Shapes. These Shapes
michael@0:  *    are unshared, private to a single object, and immutable except for their
michael@0:  *    links in the dictionary list.
michael@0:  *
michael@0:  * All shape lineages are bi-directionally linked, via the |parent| and
michael@0:  * |kids|/|listp| members.
michael@0:  *
michael@0:  * Shape lineages start out life in the property tree. They can be converted
michael@0:  * (by copying) to dictionary mode lists in the following circumstances.
michael@0:  *
michael@0:  * 1. The shape lineage's size reaches MAX_HEIGHT. This reasonable limit avoids
michael@0:  *    potential worst cases involving shape lineage mutations.
michael@0:  *
michael@0:  * 2. A property represented by a non-last Shape in a shape lineage is removed
michael@0:  *    from an object. (In the last Shape case, obj->shape_ can be easily
michael@0:  *    adjusted to point to obj->shape_->parent.)  We originally tried lazy
michael@0:  *    forking of the property tree, but this blows up for delete/add
michael@0:  *    repetitions.
michael@0:  *
michael@0:  * 3. A property represented by a non-last Shape in a shape lineage has its
michael@0:  *    attributes modified.
michael@0:  *
michael@0:  * To find the Shape for a particular property of an object initially requires
michael@0:  * a linear search. But if the number of searches starting at any particular
michael@0:  * Shape in the property tree exceeds MAX_LINEAR_SEARCHES and the Shape's
michael@0:  * lineage has (excluding the EmptyShape) at least MIN_ENTRIES, we create an
michael@0:  * auxiliary hash table -- the ShapeTable -- that allows faster lookup.
michael@0:  * Furthermore, a ShapeTable is always created for dictionary mode lists,
michael@0:  * and it is attached to the last Shape in the lineage. Shape tables for
michael@0:  * property tree Shapes never change, but shape tables for dictionary mode
michael@0:  * Shapes can grow and shrink.
michael@0:  *
michael@0:  * There used to be a long, math-heavy comment here explaining why property
michael@0:  * trees are more space-efficient than alternatives.  This was removed in bug
michael@0:  * 631138; see that bug for the full details.
michael@0:  *
michael@0:  * Because many Shapes have similar data, there is actually a secondary type
michael@0:  * called a BaseShape that holds some of a Shape's data.  Many shapes can share
michael@0:  * a single BaseShape.
michael@0:  */
michael@0: 
michael@0: #define JSSLOT_FREE(clasp)  JSCLASS_RESERVED_SLOTS(clasp)
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: class Bindings;
michael@0: class Debugger;
michael@0: class Nursery;
michael@0: class ObjectImpl;
michael@0: class StaticBlockObject;
michael@0: 
michael@0: typedef JSPropertyOp         PropertyOp;
michael@0: typedef JSStrictPropertyOp   StrictPropertyOp;
michael@0: typedef JSPropertyDescriptor PropertyDescriptor;
michael@0: 
michael@0: /* Limit on the number of slotful properties in an object. */
michael@0: static const uint32_t SHAPE_INVALID_SLOT = JS_BIT(24) - 1;
michael@0: static const uint32_t SHAPE_MAXIMUM_SLOT = JS_BIT(24) - 2;
michael@0: 
michael@0: static inline PropertyOp
michael@0: CastAsPropertyOp(JSObject *object)
michael@0: {
michael@0:     return JS_DATA_TO_FUNC_PTR(PropertyOp, object);
michael@0: }
michael@0: 
michael@0: static inline StrictPropertyOp
michael@0: CastAsStrictPropertyOp(JSObject *object)
michael@0: {
michael@0:     return JS_DATA_TO_FUNC_PTR(StrictPropertyOp, object);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * A representation of ECMA-262 ed. 5's internal Property Descriptor data
michael@0:  * structure.
michael@0:  */
michael@0: struct PropDesc {
michael@0:   private:
michael@0:     /*
michael@0:      * Original object from which this descriptor derives, passed through for
michael@0:      * the benefit of proxies.  FIXME: Remove this when direct proxies happen.
michael@0:      */
michael@0:     Value pd_;
michael@0: 
michael@0:     Value value_, get_, set_;
michael@0: 
michael@0:     /* Property descriptor boolean fields. */
michael@0:     uint8_t attrs;
michael@0: 
michael@0:     /* Bits indicating which values are set. */
michael@0:     bool hasGet_ : 1;
michael@0:     bool hasSet_ : 1;
michael@0:     bool hasValue_ : 1;
michael@0:     bool hasWritable_ : 1;
michael@0:     bool hasEnumerable_ : 1;
michael@0:     bool hasConfigurable_ : 1;
michael@0: 
michael@0:     /* Or maybe this represents a property's absence, and it's undefined. */
michael@0:     bool isUndefined_ : 1;
michael@0: 
michael@0:     PropDesc(const Value &v)
michael@0:       : pd_(UndefinedValue()),
michael@0:         value_(v),
michael@0:         get_(UndefinedValue()), set_(UndefinedValue()),
michael@0:         attrs(0),
michael@0:         hasGet_(false), hasSet_(false),
michael@0:         hasValue_(true), hasWritable_(false), hasEnumerable_(false), hasConfigurable_(false),
michael@0:         isUndefined_(false)
michael@0:     {
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     friend class AutoPropDescRooter;
michael@0:     friend void JS::AutoGCRooter::trace(JSTracer *trc);
michael@0: 
michael@0:     enum Enumerability { Enumerable = true, NonEnumerable = false };
michael@0:     enum Configurability { Configurable = true, NonConfigurable = false };
michael@0:     enum Writability { Writable = true, NonWritable = false };
michael@0: 
michael@0:     PropDesc();
michael@0: 
michael@0:     static PropDesc undefined() { return PropDesc(); }
michael@0:     static PropDesc valueOnly(const Value &v) { return PropDesc(v); }
michael@0: 
michael@0:     PropDesc(const Value &v, Writability writable,
michael@0:              Enumerability enumerable, Configurability configurable)
michael@0:       : pd_(UndefinedValue()),
michael@0:         value_(v),
michael@0:         get_(UndefinedValue()), set_(UndefinedValue()),
michael@0:         attrs((writable ? 0 : JSPROP_READONLY) |
michael@0:               (enumerable ? JSPROP_ENUMERATE : 0) |
michael@0:               (configurable ? 0 : JSPROP_PERMANENT)),
michael@0:         hasGet_(false), hasSet_(false),
michael@0:         hasValue_(true), hasWritable_(true), hasEnumerable_(true), hasConfigurable_(true),
michael@0:         isUndefined_(false)
michael@0:     {}
michael@0: 
michael@0:     inline PropDesc(const Value &getter, const Value &setter,
michael@0:                     Enumerability enumerable, Configurability configurable);
michael@0: 
michael@0:     /*
michael@0:      * 8.10.5 ToPropertyDescriptor(Obj)
michael@0:      *
michael@0:      * If checkAccessors is false, skip steps 7.b and 8.b, which throw a
michael@0:      * TypeError if .get or .set is neither a callable object nor undefined.
michael@0:      *
michael@0:      * (DebuggerObject_defineProperty uses this: the .get and .set properties
michael@0:      * are expected to be Debugger.Object wrappers of functions, which are not
michael@0:      * themselves callable.)
michael@0:      */
michael@0:     bool initialize(JSContext *cx, const Value &v, bool checkAccessors = true);
michael@0: 
michael@0:     /*
michael@0:      * If IsGenericDescriptor(desc) or IsDataDescriptor(desc) is true, then if
michael@0:      * the value of an attribute field of desc, considered as a data
michael@0:      * descriptor, is absent, set it to its default value. Else if the value of
michael@0:      * an attribute field of desc, considered as an attribute descriptor, is
michael@0:      * absent, set it to its default value.
michael@0:      */
michael@0:     void complete();
michael@0: 
michael@0:     /*
michael@0:      * 8.10.4 FromPropertyDescriptor(Desc)
michael@0:      *
michael@0:      * initFromPropertyDescriptor sets pd to undefined and populates all the
michael@0:      * other fields of this PropDesc from desc.
michael@0:      *
michael@0:      * makeObject populates pd based on the other fields of *this, creating a
michael@0:      * new property descriptor JSObject and defining properties on it.
michael@0:      */
michael@0:     void initFromPropertyDescriptor(Handle<PropertyDescriptor> desc);
michael@0:     bool makeObject(JSContext *cx);
michael@0: 
michael@0:     void setUndefined() { isUndefined_ = true; }
michael@0: 
michael@0:     bool isUndefined() const { return isUndefined_; }
michael@0: 
michael@0:     bool hasGet() const { MOZ_ASSERT(!isUndefined()); return hasGet_; }
michael@0:     bool hasSet() const { MOZ_ASSERT(!isUndefined()); return hasSet_; }
michael@0:     bool hasValue() const { MOZ_ASSERT(!isUndefined()); return hasValue_; }
michael@0:     bool hasWritable() const { MOZ_ASSERT(!isUndefined()); return hasWritable_; }
michael@0:     bool hasEnumerable() const { MOZ_ASSERT(!isUndefined()); return hasEnumerable_; }
michael@0:     bool hasConfigurable() const { MOZ_ASSERT(!isUndefined()); return hasConfigurable_; }
michael@0: 
michael@0:     Value pd() const { MOZ_ASSERT(!isUndefined()); return pd_; }
michael@0:     void clearPd() { pd_ = UndefinedValue(); }
michael@0: 
michael@0:     uint8_t attributes() const { MOZ_ASSERT(!isUndefined()); return attrs; }
michael@0: 
michael@0:     /* 8.10.1 IsAccessorDescriptor(desc) */
michael@0:     bool isAccessorDescriptor() const {
michael@0:         return !isUndefined() && (hasGet() || hasSet());
michael@0:     }
michael@0: 
michael@0:     /* 8.10.2 IsDataDescriptor(desc) */
michael@0:     bool isDataDescriptor() const {
michael@0:         return !isUndefined() && (hasValue() || hasWritable());
michael@0:     }
michael@0: 
michael@0:     /* 8.10.3 IsGenericDescriptor(desc) */
michael@0:     bool isGenericDescriptor() const {
michael@0:         return !isUndefined() && !isAccessorDescriptor() && !isDataDescriptor();
michael@0:     }
michael@0: 
michael@0:     bool configurable() const {
michael@0:         MOZ_ASSERT(!isUndefined());
michael@0:         MOZ_ASSERT(hasConfigurable());
michael@0:         return (attrs & JSPROP_PERMANENT) == 0;
michael@0:     }
michael@0: 
michael@0:     bool enumerable() const {
michael@0:         MOZ_ASSERT(!isUndefined());
michael@0:         MOZ_ASSERT(hasEnumerable());
michael@0:         return (attrs & JSPROP_ENUMERATE) != 0;
michael@0:     }
michael@0: 
michael@0:     bool writable() const {
michael@0:         MOZ_ASSERT(!isUndefined());
michael@0:         MOZ_ASSERT(hasWritable());
michael@0:         return (attrs & JSPROP_READONLY) == 0;
michael@0:     }
michael@0: 
michael@0:     HandleValue value() const {
michael@0:         MOZ_ASSERT(hasValue());
michael@0:         return HandleValue::fromMarkedLocation(&value_);
michael@0:     }
michael@0: 
michael@0:     JSObject * getterObject() const {
michael@0:         MOZ_ASSERT(!isUndefined());
michael@0:         MOZ_ASSERT(hasGet());
michael@0:         return get_.isUndefined() ? nullptr : &get_.toObject();
michael@0:     }
michael@0:     JSObject * setterObject() const {
michael@0:         MOZ_ASSERT(!isUndefined());
michael@0:         MOZ_ASSERT(hasSet());
michael@0:         return set_.isUndefined() ? nullptr : &set_.toObject();
michael@0:     }
michael@0: 
michael@0:     HandleValue getterValue() const {
michael@0:         MOZ_ASSERT(!isUndefined());
michael@0:         MOZ_ASSERT(hasGet());
michael@0:         return HandleValue::fromMarkedLocation(&get_);
michael@0:     }
michael@0:     HandleValue setterValue() const {
michael@0:         MOZ_ASSERT(!isUndefined());
michael@0:         MOZ_ASSERT(hasSet());
michael@0:         return HandleValue::fromMarkedLocation(&set_);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Unfortunately the values produced by these methods are used such that
michael@0:      * we can't assert anything here.  :-(
michael@0:      */
michael@0:     PropertyOp getter() const {
michael@0:         return CastAsPropertyOp(get_.isUndefined() ? nullptr : &get_.toObject());
michael@0:     }
michael@0:     StrictPropertyOp setter() const {
michael@0:         return CastAsStrictPropertyOp(set_.isUndefined() ? nullptr : &set_.toObject());
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Throw a TypeError if a getter/setter is present and is neither callable
michael@0:      * nor undefined. These methods do exactly the type checks that are skipped
michael@0:      * by passing false as the checkAccessors parameter of initialize.
michael@0:      */
michael@0:     bool checkGetter(JSContext *cx);
michael@0:     bool checkSetter(JSContext *cx);
michael@0: 
michael@0:     bool unwrapDebuggerObjectsInto(JSContext *cx, Debugger *dbg, HandleObject obj,
michael@0:                                    PropDesc *unwrapped) const;
michael@0: 
michael@0:     bool wrapInto(JSContext *cx, HandleObject obj, const jsid &id, jsid *wrappedId,
michael@0:                   PropDesc *wrappedDesc) const;
michael@0: };
michael@0: 
michael@0: class AutoPropDescRooter : private JS::CustomAutoRooter
michael@0: {
michael@0:   public:
michael@0:     explicit AutoPropDescRooter(JSContext *cx
michael@0:                                 MOZ_GUARD_OBJECT_NOTIFIER_PARAM)
michael@0:       : CustomAutoRooter(cx)
michael@0:     {
michael@0:         MOZ_GUARD_OBJECT_NOTIFIER_INIT;
michael@0:     }
michael@0: 
michael@0:     PropDesc& getPropDesc() { return propDesc; }
michael@0: 
michael@0:     void initFromPropertyDescriptor(Handle<PropertyDescriptor> desc) {
michael@0:         propDesc.initFromPropertyDescriptor(desc);
michael@0:     }
michael@0: 
michael@0:     bool makeObject(JSContext *cx) {
michael@0:         return propDesc.makeObject(cx);
michael@0:     }
michael@0: 
michael@0:     void setUndefined() { propDesc.setUndefined(); }
michael@0:     bool isUndefined() const { return propDesc.isUndefined(); }
michael@0: 
michael@0:     bool hasGet() const { return propDesc.hasGet(); }
michael@0:     bool hasSet() const { return propDesc.hasSet(); }
michael@0:     bool hasValue() const { return propDesc.hasValue(); }
michael@0:     bool hasWritable() const { return propDesc.hasWritable(); }
michael@0:     bool hasEnumerable() const { return propDesc.hasEnumerable(); }
michael@0:     bool hasConfigurable() const { return propDesc.hasConfigurable(); }
michael@0: 
michael@0:     Value pd() const { return propDesc.pd(); }
michael@0:     void clearPd() { propDesc.clearPd(); }
michael@0: 
michael@0:     uint8_t attributes() const { return propDesc.attributes(); }
michael@0: 
michael@0:     bool isAccessorDescriptor() const { return propDesc.isAccessorDescriptor(); }
michael@0:     bool isDataDescriptor() const { return propDesc.isDataDescriptor(); }
michael@0:     bool isGenericDescriptor() const { return propDesc.isGenericDescriptor(); }
michael@0:     bool configurable() const { return propDesc.configurable(); }
michael@0:     bool enumerable() const { return propDesc.enumerable(); }
michael@0:     bool writable() const { return propDesc.writable(); }
michael@0: 
michael@0:     HandleValue value() const { return propDesc.value(); }
michael@0:     JSObject *getterObject() const { return propDesc.getterObject(); }
michael@0:     JSObject *setterObject() const { return propDesc.setterObject(); }
michael@0:     HandleValue getterValue() const { return propDesc.getterValue(); }
michael@0:     HandleValue setterValue() const { return propDesc.setterValue(); }
michael@0: 
michael@0:     PropertyOp getter() const { return propDesc.getter(); }
michael@0:     StrictPropertyOp setter() const { return propDesc.setter(); }
michael@0: 
michael@0:   private:
michael@0:     virtual void trace(JSTracer *trc);
michael@0: 
michael@0:     PropDesc propDesc;
michael@0:     MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * Shapes use multiplicative hashing, but specialized to
michael@0:  * minimize footprint.
michael@0:  */
michael@0: struct ShapeTable {
michael@0:     static const uint32_t HASH_BITS     = mozilla::tl::BitSize<HashNumber>::value;
michael@0:     static const uint32_t MIN_ENTRIES   = 7;
michael@0:     static const uint32_t MIN_SIZE_LOG2 = 4;
michael@0:     static const uint32_t MIN_SIZE      = JS_BIT(MIN_SIZE_LOG2);
michael@0: 
michael@0:     int             hashShift;          /* multiplicative hash shift */
michael@0: 
michael@0:     uint32_t        entryCount;         /* number of entries in table */
michael@0:     uint32_t        removedCount;       /* removed entry sentinels in table */
michael@0:     uint32_t        freelist;           /* SHAPE_INVALID_SLOT or head of slot
michael@0:                                            freelist in owning dictionary-mode
michael@0:                                            object */
michael@0:     js::Shape       **entries;          /* table of ptrs to shared tree nodes */
michael@0: 
michael@0:     ShapeTable(uint32_t nentries)
michael@0:       : hashShift(HASH_BITS - MIN_SIZE_LOG2),
michael@0:         entryCount(nentries),
michael@0:         removedCount(0),
michael@0:         freelist(SHAPE_INVALID_SLOT)
michael@0:     {
michael@0:         /* NB: entries is set by init, which must be called. */
michael@0:     }
michael@0: 
michael@0:     ~ShapeTable() {
michael@0:         js_free(entries);
michael@0:     }
michael@0: 
michael@0:     /* By definition, hashShift = HASH_BITS - log2(capacity). */
michael@0:     uint32_t capacity() const { return JS_BIT(HASH_BITS - hashShift); }
michael@0: 
michael@0:     /* Computes the size of the entries array for a given capacity. */
michael@0:     static size_t sizeOfEntries(size_t cap) { return cap * sizeof(Shape *); }
michael@0: 
michael@0:     /*
michael@0:      * This counts the ShapeTable object itself (which must be
michael@0:      * heap-allocated) and its |entries| array.
michael@0:      */
michael@0:     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
michael@0:         return mallocSizeOf(this) + mallocSizeOf(entries);
michael@0:     }
michael@0: 
michael@0:     /* Whether we need to grow.  We want to do this if the load factor is >= 0.75 */
michael@0:     bool needsToGrow() const {
michael@0:         uint32_t size = capacity();
michael@0:         return entryCount + removedCount >= size - (size >> 2);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Try to grow the table.  On failure, reports out of memory on cx
michael@0:      * and returns false.  This will make any extant pointers into the
michael@0:      * table invalid.  Don't call this unless needsToGrow() is true.
michael@0:      */
michael@0:     bool grow(ThreadSafeContext *cx);
michael@0: 
michael@0:     /*
michael@0:      * NB: init and change are fallible but do not report OOM, so callers can
michael@0:      * cope or ignore. They do however use the context's calloc_ method in
michael@0:      * order to update the malloc counter on success.
michael@0:      */
michael@0:     bool            init(ThreadSafeContext *cx, Shape *lastProp);
michael@0:     bool            change(int log2Delta, ThreadSafeContext *cx);
michael@0:     Shape           **search(jsid id, bool adding);
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * Reuse the API-only JSPROP_INDEX attribute to mean shadowability.
michael@0:  */
michael@0: #define JSPROP_SHADOWABLE       JSPROP_INDEX
michael@0: 
michael@0: /*
michael@0:  * Shapes encode information about both a property lineage *and* a particular
michael@0:  * property. This information is split across the Shape and the BaseShape
michael@0:  * at shape->base(). Both Shape and BaseShape can be either owned or unowned
michael@0:  * by, respectively, the Object or Shape referring to them.
michael@0:  *
michael@0:  * Owned Shapes are used in dictionary objects, and form a doubly linked list
michael@0:  * whose entries are all owned by that dictionary. Unowned Shapes are all in
michael@0:  * the property tree.
michael@0:  *
michael@0:  * Owned BaseShapes are used for shapes which have shape tables, including
michael@0:  * the last properties in all dictionaries. Unowned BaseShapes compactly store
michael@0:  * information common to many shapes. In a given compartment there is a single
michael@0:  * BaseShape for each combination of BaseShape information. This information
michael@0:  * is cloned in owned BaseShapes so that information can be quickly looked up
michael@0:  * for a given object or shape without regard to whether the base shape is
michael@0:  * owned or not.
michael@0:  *
michael@0:  * All combinations of owned/unowned Shapes/BaseShapes are possible:
michael@0:  *
michael@0:  * Owned Shape, Owned BaseShape:
michael@0:  *
michael@0:  *     Last property in a dictionary object. The BaseShape is transferred from
michael@0:  *     property to property as the object's last property changes.
michael@0:  *
michael@0:  * Owned Shape, Unowned BaseShape:
michael@0:  *
michael@0:  *     Property in a dictionary object other than the last one.
michael@0:  *
michael@0:  * Unowned Shape, Owned BaseShape:
michael@0:  *
michael@0:  *     Property in the property tree which has a shape table.
michael@0:  *
michael@0:  * Unowned Shape, Unowned BaseShape:
michael@0:  *
michael@0:  *     Property in the property tree which does not have a shape table.
michael@0:  *
michael@0:  * BaseShapes additionally encode some information about the referring object
michael@0:  * itself. This includes the object's class, parent and various flags that may
michael@0:  * be set for the object. Except for the class, this information is mutable and
michael@0:  * may change when the object has an established property lineage. On such
michael@0:  * changes the entire property lineage is not updated, but rather only the
michael@0:  * last property (and its base shape). This works because only the object's
michael@0:  * last property is used to query information about the object. Care must be
michael@0:  * taken to call JSObject::canRemoveLastProperty when unwinding an object to
michael@0:  * an earlier property, however.
michael@0:  */
michael@0: 
michael@0: class Shape;
michael@0: class UnownedBaseShape;
michael@0: struct StackBaseShape;
michael@0: 
michael@0: namespace gc {
michael@0: void MergeCompartments(JSCompartment *source, JSCompartment *target);
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: GetterSetterWriteBarrierPost(JSRuntime *rt, JSObject **objp)
michael@0: {
michael@0: #ifdef JSGC_GENERATIONAL
michael@0:     JS::shadow::Runtime *shadowRuntime = JS::shadow::Runtime::asShadowRuntime(rt);
michael@0:     shadowRuntime->gcStoreBufferPtr()->putRelocatableCell(reinterpret_cast<gc::Cell **>(objp));
michael@0: #endif
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: GetterSetterWriteBarrierPostRemove(JSRuntime *rt, JSObject **objp)
michael@0: {
michael@0: #ifdef JSGC_GENERATIONAL
michael@0:     JS::shadow::Runtime *shadowRuntime = JS::shadow::Runtime::asShadowRuntime(rt);
michael@0:     shadowRuntime->gcStoreBufferPtr()->removeRelocatableCell(reinterpret_cast<gc::Cell **>(objp));
michael@0: #endif
michael@0: }
michael@0: 
michael@0: class BaseShape : public gc::BarrieredCell<BaseShape>
michael@0: {
michael@0:   public:
michael@0:     friend class Shape;
michael@0:     friend struct StackBaseShape;
michael@0:     friend struct StackShape;
michael@0:     friend void gc::MergeCompartments(JSCompartment *source, JSCompartment *target);
michael@0: 
michael@0:     enum Flag {
michael@0:         /* Owned by the referring shape. */
michael@0:         OWNED_SHAPE        = 0x1,
michael@0: 
michael@0:         /* getterObj/setterObj are active in unions below. */
michael@0:         HAS_GETTER_OBJECT  = 0x2,
michael@0:         HAS_SETTER_OBJECT  = 0x4,
michael@0: 
michael@0:         /*
michael@0:          * Flags set which describe the referring object. Once set these cannot
michael@0:          * be unset (except during object densification of sparse indexes), and
michael@0:          * are transferred from shape to shape as the object's last property
michael@0:          * changes.
michael@0:          *
michael@0:          * If you add a new flag here, please add appropriate code to
michael@0:          * JSObject::dump to dump it as part of object representation.
michael@0:          */
michael@0: 
michael@0:         DELEGATE            =    0x8,
michael@0:         NOT_EXTENSIBLE      =   0x10,
michael@0:         INDEXED             =   0x20,
michael@0:         BOUND_FUNCTION      =   0x40,
michael@0:         VAROBJ              =   0x80,
michael@0:         WATCHED             =  0x100,
michael@0:         ITERATED_SINGLETON  =  0x200,
michael@0:         NEW_TYPE_UNKNOWN    =  0x400,
michael@0:         UNCACHEABLE_PROTO   =  0x800,
michael@0:         HAD_ELEMENTS_ACCESS = 0x1000,
michael@0: 
michael@0:         OBJECT_FLAG_MASK    = 0x1ff8
michael@0:     };
michael@0: 
michael@0:   private:
michael@0:     const Class         *clasp_;        /* Class of referring object. */
michael@0:     HeapPtrObject       parent;         /* Parent of referring object. */
michael@0:     HeapPtrObject       metadata;       /* Optional holder of metadata about
michael@0:                                          * the referring object. */
michael@0:     JSCompartment       *compartment_;  /* Compartment shape belongs to. */
michael@0:     uint32_t            flags;          /* Vector of above flags. */
michael@0:     uint32_t            slotSpan_;      /* Object slot span for BaseShapes at
michael@0:                                          * dictionary last properties. */
michael@0: 
michael@0:     union {
michael@0:         PropertyOp      rawGetter;      /* getter hook for shape */
michael@0:         JSObject        *getterObj;     /* user-defined callable "get" object or
michael@0:                                            null if shape->hasGetterValue() */
michael@0:     };
michael@0: 
michael@0:     union {
michael@0:         StrictPropertyOp rawSetter;     /* setter hook for shape */
michael@0:         JSObject        *setterObj;     /* user-defined callable "set" object or
michael@0:                                            null if shape->hasSetterValue() */
michael@0:     };
michael@0: 
michael@0:     /* For owned BaseShapes, the canonical unowned BaseShape. */
michael@0:     HeapPtr<UnownedBaseShape> unowned_;
michael@0: 
michael@0:     /* For owned BaseShapes, the shape's shape table. */
michael@0:     ShapeTable       *table_;
michael@0: 
michael@0:     BaseShape(const BaseShape &base) MOZ_DELETE;
michael@0: 
michael@0:   public:
michael@0:     void finalize(FreeOp *fop);
michael@0: 
michael@0:     BaseShape(JSCompartment *comp, const Class *clasp, JSObject *parent, JSObject *metadata,
michael@0:               uint32_t objectFlags)
michael@0:     {
michael@0:         JS_ASSERT(!(objectFlags & ~OBJECT_FLAG_MASK));
michael@0:         mozilla::PodZero(this);
michael@0:         this->clasp_ = clasp;
michael@0:         this->parent = parent;
michael@0:         this->metadata = metadata;
michael@0:         this->flags = objectFlags;
michael@0:         this->compartment_ = comp;
michael@0:     }
michael@0: 
michael@0:     BaseShape(JSCompartment *comp, const Class *clasp, JSObject *parent, JSObject *metadata,
michael@0:               uint32_t objectFlags, uint8_t attrs,
michael@0:               PropertyOp rawGetter, StrictPropertyOp rawSetter)
michael@0:     {
michael@0:         JS_ASSERT(!(objectFlags & ~OBJECT_FLAG_MASK));
michael@0:         mozilla::PodZero(this);
michael@0:         this->clasp_ = clasp;
michael@0:         this->parent = parent;
michael@0:         this->metadata = metadata;
michael@0:         this->flags = objectFlags;
michael@0:         this->rawGetter = rawGetter;
michael@0:         this->rawSetter = rawSetter;
michael@0:         if ((attrs & JSPROP_GETTER) && rawGetter) {
michael@0:             this->flags |= HAS_GETTER_OBJECT;
michael@0:             GetterSetterWriteBarrierPost(runtimeFromMainThread(), &this->getterObj);
michael@0:         }
michael@0:         if ((attrs & JSPROP_SETTER) && rawSetter) {
michael@0:             this->flags |= HAS_SETTER_OBJECT;
michael@0:             GetterSetterWriteBarrierPost(runtimeFromMainThread(), &this->setterObj);
michael@0:         }
michael@0:         this->compartment_ = comp;
michael@0:     }
michael@0: 
michael@0:     inline BaseShape(const StackBaseShape &base);
michael@0: 
michael@0:     /* Not defined: BaseShapes must not be stack allocated. */
michael@0:     ~BaseShape();
michael@0: 
michael@0:     BaseShape &operator=(const BaseShape &other) {
michael@0:         clasp_ = other.clasp_;
michael@0:         parent = other.parent;
michael@0:         metadata = other.metadata;
michael@0:         flags = other.flags;
michael@0:         slotSpan_ = other.slotSpan_;
michael@0:         if (flags & HAS_GETTER_OBJECT) {
michael@0:             getterObj = other.getterObj;
michael@0:             GetterSetterWriteBarrierPost(runtimeFromMainThread(), &getterObj);
michael@0:         } else {
michael@0:             if (rawGetter)
michael@0:                 GetterSetterWriteBarrierPostRemove(runtimeFromMainThread(), &getterObj);
michael@0:             rawGetter = other.rawGetter;
michael@0:         }
michael@0:         if (flags & HAS_SETTER_OBJECT) {
michael@0:             setterObj = other.setterObj;
michael@0:             GetterSetterWriteBarrierPost(runtimeFromMainThread(), &setterObj);
michael@0:         } else {
michael@0:             if (rawSetter)
michael@0:                 GetterSetterWriteBarrierPostRemove(runtimeFromMainThread(), &setterObj);
michael@0:             rawSetter = other.rawSetter;
michael@0:         }
michael@0:         compartment_ = other.compartment_;
michael@0:         return *this;
michael@0:     }
michael@0: 
michael@0:     const Class *clasp() const { return clasp_; }
michael@0: 
michael@0:     bool isOwned() const { return !!(flags & OWNED_SHAPE); }
michael@0: 
michael@0:     bool matchesGetterSetter(PropertyOp rawGetter, StrictPropertyOp rawSetter) const {
michael@0:         return rawGetter == this->rawGetter && rawSetter == this->rawSetter;
michael@0:     }
michael@0: 
michael@0:     inline void adoptUnowned(UnownedBaseShape *other);
michael@0: 
michael@0:     void setOwned(UnownedBaseShape *unowned) {
michael@0:         flags |= OWNED_SHAPE;
michael@0:         this->unowned_ = unowned;
michael@0:     }
michael@0: 
michael@0:     JSObject *getObjectParent() const { return parent; }
michael@0:     JSObject *getObjectMetadata() const { return metadata; }
michael@0:     uint32_t getObjectFlags() const { return flags & OBJECT_FLAG_MASK; }
michael@0: 
michael@0:     bool hasGetterObject() const { return !!(flags & HAS_GETTER_OBJECT); }
michael@0:     JSObject *getterObject() const { JS_ASSERT(hasGetterObject()); return getterObj; }
michael@0: 
michael@0:     bool hasSetterObject() const { return !!(flags & HAS_SETTER_OBJECT); }
michael@0:     JSObject *setterObject() const { JS_ASSERT(hasSetterObject()); return setterObj; }
michael@0: 
michael@0:     bool hasTable() const { JS_ASSERT_IF(table_, isOwned()); return table_ != nullptr; }
michael@0:     ShapeTable &table() const { JS_ASSERT(table_ && isOwned()); return *table_; }
michael@0:     void setTable(ShapeTable *table) { JS_ASSERT(isOwned()); table_ = table; }
michael@0: 
michael@0:     uint32_t slotSpan() const { JS_ASSERT(isOwned()); return slotSpan_; }
michael@0:     void setSlotSpan(uint32_t slotSpan) { JS_ASSERT(isOwned()); slotSpan_ = slotSpan; }
michael@0: 
michael@0:     JSCompartment *compartment() const { return compartment_; }
michael@0: 
michael@0:     /*
michael@0:      * Lookup base shapes from the compartment's baseShapes table, adding if
michael@0:      * not already found.
michael@0:      */
michael@0:     static UnownedBaseShape* getUnowned(ExclusiveContext *cx, StackBaseShape &base);
michael@0: 
michael@0:     /*
michael@0:      * Lookup base shapes from the compartment's baseShapes table, returning
michael@0:      * nullptr if not found.
michael@0:      */
michael@0:     static UnownedBaseShape *lookupUnowned(ThreadSafeContext *cx, const StackBaseShape &base);
michael@0: 
michael@0:     /* Get the canonical base shape. */
michael@0:     inline UnownedBaseShape* unowned();
michael@0: 
michael@0:     /* Get the canonical base shape for an owned one. */
michael@0:     inline UnownedBaseShape* baseUnowned();
michael@0: 
michael@0:     /* Get the canonical base shape for an unowned one (i.e. identity). */
michael@0:     inline UnownedBaseShape* toUnowned();
michael@0: 
michael@0:     /* Check that an owned base shape is consistent with its unowned base. */
michael@0:     void assertConsistency();
michael@0: 
michael@0:     /* For JIT usage */
michael@0:     static inline size_t offsetOfParent() { return offsetof(BaseShape, parent); }
michael@0:     static inline size_t offsetOfFlags() { return offsetof(BaseShape, flags); }
michael@0: 
michael@0:     static inline ThingRootKind rootKind() { return THING_ROOT_BASE_SHAPE; }
michael@0: 
michael@0:     void markChildren(JSTracer *trc) {
michael@0:         if (hasGetterObject())
michael@0:             gc::MarkObjectUnbarriered(trc, &getterObj, "getter");
michael@0: 
michael@0:         if (hasSetterObject())
michael@0:             gc::MarkObjectUnbarriered(trc, &setterObj, "setter");
michael@0: 
michael@0:         if (isOwned())
michael@0:             gc::MarkBaseShape(trc, &unowned_, "base");
michael@0: 
michael@0:         if (parent)
michael@0:             gc::MarkObject(trc, &parent, "parent");
michael@0: 
michael@0:         if (metadata)
michael@0:             gc::MarkObject(trc, &metadata, "metadata");
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     static void staticAsserts() {
michael@0:         JS_STATIC_ASSERT(offsetof(BaseShape, clasp_) == offsetof(js::shadow::BaseShape, clasp_));
michael@0:     }
michael@0: };
michael@0: 
michael@0: class UnownedBaseShape : public BaseShape {};
michael@0: 
michael@0: inline void
michael@0: BaseShape::adoptUnowned(UnownedBaseShape *other)
michael@0: {
michael@0:     // This is a base shape owned by a dictionary object, update it to reflect the
michael@0:     // unowned base shape of a new last property.
michael@0:     JS_ASSERT(isOwned());
michael@0: 
michael@0:     uint32_t span = slotSpan();
michael@0:     ShapeTable *table = &this->table();
michael@0: 
michael@0:     *this = *other;
michael@0:     setOwned(other);
michael@0:     setTable(table);
michael@0:     setSlotSpan(span);
michael@0: 
michael@0:     assertConsistency();
michael@0: }
michael@0: 
michael@0: UnownedBaseShape *
michael@0: BaseShape::unowned()
michael@0: {
michael@0:     return isOwned() ? baseUnowned() : toUnowned();
michael@0: }
michael@0: 
michael@0: UnownedBaseShape *
michael@0: BaseShape::toUnowned()
michael@0: {
michael@0:     JS_ASSERT(!isOwned() && !unowned_); return static_cast<UnownedBaseShape *>(this);
michael@0: }
michael@0: 
michael@0: UnownedBaseShape*
michael@0: BaseShape::baseUnowned()
michael@0: {
michael@0:     JS_ASSERT(isOwned() && unowned_); return unowned_;
michael@0: }
michael@0: 
michael@0: /* Entries for the per-compartment baseShapes set of unowned base shapes. */
michael@0: struct StackBaseShape
michael@0: {
michael@0:     typedef const StackBaseShape *Lookup;
michael@0: 
michael@0:     uint32_t flags;
michael@0:     const Class *clasp;
michael@0:     JSObject *parent;
michael@0:     JSObject *metadata;
michael@0:     PropertyOp rawGetter;
michael@0:     StrictPropertyOp rawSetter;
michael@0:     JSCompartment *compartment;
michael@0: 
michael@0:     explicit StackBaseShape(BaseShape *base)
michael@0:       : flags(base->flags & BaseShape::OBJECT_FLAG_MASK),
michael@0:         clasp(base->clasp_),
michael@0:         parent(base->parent),
michael@0:         metadata(base->metadata),
michael@0:         rawGetter(nullptr),
michael@0:         rawSetter(nullptr),
michael@0:         compartment(base->compartment())
michael@0:     {}
michael@0: 
michael@0:     inline StackBaseShape(ThreadSafeContext *cx, const Class *clasp,
michael@0:                           JSObject *parent, JSObject *metadata, uint32_t objectFlags);
michael@0:     inline StackBaseShape(Shape *shape);
michael@0: 
michael@0:     void updateGetterSetter(uint8_t attrs, PropertyOp rawGetter, StrictPropertyOp rawSetter) {
michael@0:         flags &= ~(BaseShape::HAS_GETTER_OBJECT | BaseShape::HAS_SETTER_OBJECT);
michael@0:         if ((attrs & JSPROP_GETTER) && rawGetter) {
michael@0:             JS_ASSERT(!IsPoisonedPtr(rawGetter));
michael@0:             flags |= BaseShape::HAS_GETTER_OBJECT;
michael@0:         }
michael@0:         if ((attrs & JSPROP_SETTER) && rawSetter) {
michael@0:             JS_ASSERT(!IsPoisonedPtr(rawSetter));
michael@0:             flags |= BaseShape::HAS_SETTER_OBJECT;
michael@0:         }
michael@0: 
michael@0:         this->rawGetter = rawGetter;
michael@0:         this->rawSetter = rawSetter;
michael@0:     }
michael@0: 
michael@0:     static inline HashNumber hash(const StackBaseShape *lookup);
michael@0:     static inline bool match(UnownedBaseShape *key, const StackBaseShape *lookup);
michael@0: 
michael@0:     // For RootedGeneric<StackBaseShape*>
michael@0:     static inline js::ThingRootKind rootKind() { return js::THING_ROOT_CUSTOM; }
michael@0:     void trace(JSTracer *trc);
michael@0: };
michael@0: 
michael@0: inline
michael@0: BaseShape::BaseShape(const StackBaseShape &base)
michael@0: {
michael@0:     mozilla::PodZero(this);
michael@0:     this->clasp_ = base.clasp;
michael@0:     this->parent = base.parent;
michael@0:     this->metadata = base.metadata;
michael@0:     this->flags = base.flags;
michael@0:     this->rawGetter = base.rawGetter;
michael@0:     this->rawSetter = base.rawSetter;
michael@0:     if ((base.flags & HAS_GETTER_OBJECT) && base.rawGetter)
michael@0:         GetterSetterWriteBarrierPost(runtimeFromMainThread(), &this->getterObj);
michael@0:     if ((base.flags & HAS_SETTER_OBJECT) && base.rawSetter)
michael@0:         GetterSetterWriteBarrierPost(runtimeFromMainThread(), &this->setterObj);
michael@0:     this->compartment_ = base.compartment;
michael@0: }
michael@0: 
michael@0: typedef HashSet<ReadBarriered<UnownedBaseShape>,
michael@0:                 StackBaseShape,
michael@0:                 SystemAllocPolicy> BaseShapeSet;
michael@0: 
michael@0: 
michael@0: class Shape : public gc::BarrieredCell<Shape>
michael@0: {
michael@0:     friend class ::JSObject;
michael@0:     friend class ::JSFunction;
michael@0:     friend class js::Bindings;
michael@0:     friend class js::Nursery;
michael@0:     friend class js::ObjectImpl;
michael@0:     friend class js::PropertyTree;
michael@0:     friend class js::StaticBlockObject;
michael@0:     friend struct js::StackShape;
michael@0:     friend struct js::StackBaseShape;
michael@0: 
michael@0:   protected:
michael@0:     HeapPtrBaseShape    base_;
michael@0:     EncapsulatedId      propid_;
michael@0: 
michael@0:     JS_ENUM_HEADER(SlotInfo, uint32_t)
michael@0:     {
michael@0:         /* Number of fixed slots in objects with this shape. */
michael@0:         // FIXED_SLOTS_MAX is the biggest count of fixed slots a Shape can store
michael@0:         FIXED_SLOTS_MAX        = 0x1f,
michael@0:         FIXED_SLOTS_SHIFT      = 27,
michael@0:         FIXED_SLOTS_MASK       = uint32_t(FIXED_SLOTS_MAX << FIXED_SLOTS_SHIFT),
michael@0: 
michael@0:         /*
michael@0:          * numLinearSearches starts at zero and is incremented initially on
michael@0:          * search() calls. Once numLinearSearches reaches LINEAR_SEARCHES_MAX,
michael@0:          * the table is created on the next search() call. The table can also
michael@0:          * be created when hashifying for dictionary mode.
michael@0:          */
michael@0:         LINEAR_SEARCHES_MAX    = 0x7,
michael@0:         LINEAR_SEARCHES_SHIFT  = 24,
michael@0:         LINEAR_SEARCHES_MASK   = LINEAR_SEARCHES_MAX << LINEAR_SEARCHES_SHIFT,
michael@0: 
michael@0:         /*
michael@0:          * Mask to get the index in object slots for shapes which hasSlot().
michael@0:          * For !hasSlot() shapes in the property tree with a parent, stores the
michael@0:          * parent's slot index (which may be invalid), and invalid for all
michael@0:          * other shapes.
michael@0:          */
michael@0:         SLOT_MASK              = JS_BIT(24) - 1
michael@0:     } JS_ENUM_FOOTER(SlotInfo);
michael@0: 
michael@0:     uint32_t            slotInfo;       /* mask of above info */
michael@0:     uint8_t             attrs;          /* attributes, see jsapi.h JSPROP_* */
michael@0:     uint8_t             flags;          /* flags, see below for defines */
michael@0: 
michael@0:     HeapPtrShape        parent;        /* parent node, reverse for..in order */
michael@0:     /* kids is valid when !inDictionary(), listp is valid when inDictionary(). */
michael@0:     union {
michael@0:         KidsPointer kids;       /* null, single child, or a tagged ptr
michael@0:                                    to many-kids data structure */
michael@0:         HeapPtrShape *listp;    /* dictionary list starting at shape_
michael@0:                                    has a double-indirect back pointer,
michael@0:                                    either to the next shape's parent if not
michael@0:                                    last, else to obj->shape_ */
michael@0:     };
michael@0: 
michael@0:     static inline Shape *search(ExclusiveContext *cx, Shape *start, jsid id,
michael@0:                                 Shape ***pspp, bool adding = false);
michael@0:     static inline Shape *searchThreadLocal(ThreadSafeContext *cx, Shape *start, jsid id,
michael@0:                                            Shape ***pspp, bool adding = false);
michael@0:     static inline Shape *searchNoHashify(Shape *start, jsid id);
michael@0: 
michael@0:     void removeFromDictionary(ObjectImpl *obj);
michael@0:     void insertIntoDictionary(HeapPtrShape *dictp);
michael@0: 
michael@0:     void initDictionaryShape(const StackShape &child, uint32_t nfixed, HeapPtrShape *dictp) {
michael@0:         new (this) Shape(child, nfixed);
michael@0:         this->flags |= IN_DICTIONARY;
michael@0: 
michael@0:         this->listp = nullptr;
michael@0:         insertIntoDictionary(dictp);
michael@0:     }
michael@0: 
michael@0:     /* Replace the base shape of the last shape in a non-dictionary lineage with base. */
michael@0:     static Shape *replaceLastProperty(ExclusiveContext *cx, StackBaseShape &base,
michael@0:                                       TaggedProto proto, HandleShape shape);
michael@0: 
michael@0:     /*
michael@0:      * This function is thread safe if every shape in the lineage of |shape|
michael@0:      * is thread local, which is the case when we clone the entire shape
michael@0:      * lineage in preparation for converting an object to dictionary mode.
michael@0:      */
michael@0:     static bool hashify(ThreadSafeContext *cx, Shape *shape);
michael@0:     void handoffTableTo(Shape *newShape);
michael@0: 
michael@0:     void setParent(Shape *p) {
michael@0:         JS_ASSERT_IF(p && !p->hasMissingSlot() && !inDictionary(),
michael@0:                      p->maybeSlot() <= maybeSlot());
michael@0:         JS_ASSERT_IF(p && !inDictionary(),
michael@0:                      hasSlot() == (p->maybeSlot() != maybeSlot()));
michael@0:         parent = p;
michael@0:     }
michael@0: 
michael@0:     bool ensureOwnBaseShape(ThreadSafeContext *cx) {
michael@0:         if (base()->isOwned())
michael@0:             return true;
michael@0:         return makeOwnBaseShape(cx);
michael@0:     }
michael@0: 
michael@0:     bool makeOwnBaseShape(ThreadSafeContext *cx);
michael@0: 
michael@0:   public:
michael@0:     bool hasTable() const { return base()->hasTable(); }
michael@0:     ShapeTable &table() const { return base()->table(); }
michael@0: 
michael@0:     void addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
michael@0:                                 size_t *propTableSize, size_t *kidsSize) const {
michael@0:         if (hasTable())
michael@0:             *propTableSize += table().sizeOfIncludingThis(mallocSizeOf);
michael@0: 
michael@0:         if (!inDictionary() && kids.isHash())
michael@0:             *kidsSize += kids.toHash()->sizeOfIncludingThis(mallocSizeOf);
michael@0:     }
michael@0: 
michael@0:     bool isNative() const {
michael@0:         JS_ASSERT(!(flags & NON_NATIVE) == getObjectClass()->isNative());
michael@0:         return !(flags & NON_NATIVE);
michael@0:     }
michael@0: 
michael@0:     const HeapPtrShape &previous() const { return parent; }
michael@0:     JSCompartment *compartment() const { return base()->compartment(); }
michael@0: 
michael@0:     template <AllowGC allowGC>
michael@0:     class Range {
michael@0:       protected:
michael@0:         friend class Shape;
michael@0: 
michael@0:         typename MaybeRooted<Shape*, allowGC>::RootType cursor;
michael@0: 
michael@0:       public:
michael@0:         Range(ExclusiveContext *cx, Shape *shape) : cursor(cx, shape) {
michael@0:             JS_STATIC_ASSERT(allowGC == CanGC);
michael@0:         }
michael@0: 
michael@0:         Range(Shape *shape) : cursor((ExclusiveContext *) nullptr, shape) {
michael@0:             JS_STATIC_ASSERT(allowGC == NoGC);
michael@0:         }
michael@0: 
michael@0:         bool empty() const {
michael@0:             return !cursor || cursor->isEmptyShape();
michael@0:         }
michael@0: 
michael@0:         Shape &front() const {
michael@0:             JS_ASSERT(!empty());
michael@0:             return *cursor;
michael@0:         }
michael@0: 
michael@0:         void popFront() {
michael@0:             JS_ASSERT(!empty());
michael@0:             cursor = cursor->parent;
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     const Class *getObjectClass() const {
michael@0:         return base()->clasp_;
michael@0:     }
michael@0:     JSObject *getObjectParent() const { return base()->parent; }
michael@0:     JSObject *getObjectMetadata() const { return base()->metadata; }
michael@0: 
michael@0:     static Shape *setObjectParent(ExclusiveContext *cx,
michael@0:                                   JSObject *obj, TaggedProto proto, Shape *last);
michael@0:     static Shape *setObjectMetadata(JSContext *cx,
michael@0:                                     JSObject *metadata, TaggedProto proto, Shape *last);
michael@0:     static Shape *setObjectFlag(ExclusiveContext *cx,
michael@0:                                 BaseShape::Flag flag, TaggedProto proto, Shape *last);
michael@0: 
michael@0:     uint32_t getObjectFlags() const { return base()->getObjectFlags(); }
michael@0:     bool hasObjectFlag(BaseShape::Flag flag) const {
michael@0:         JS_ASSERT(!(flag & ~BaseShape::OBJECT_FLAG_MASK));
michael@0:         return !!(base()->flags & flag);
michael@0:     }
michael@0: 
michael@0:   protected:
michael@0:     /*
michael@0:      * Implementation-private bits stored in shape->flags. See public: enum {}
michael@0:      * flags further below, which were allocated FCFS over time, so interleave
michael@0:      * with these bits.
michael@0:      */
michael@0:     enum {
michael@0:         /* Property is placeholder for a non-native class. */
michael@0:         NON_NATIVE      = 0x01,
michael@0: 
michael@0:         /* Property stored in per-object dictionary, not shared property tree. */
michael@0:         IN_DICTIONARY   = 0x02,
michael@0: 
michael@0:         UNUSED_BITS     = 0x3C
michael@0:     };
michael@0: 
michael@0:     /* Get a shape identical to this one, without parent/kids information. */
michael@0:     inline Shape(const StackShape &other, uint32_t nfixed);
michael@0: 
michael@0:     /* Used by EmptyShape (see jsscopeinlines.h). */
michael@0:     inline Shape(UnownedBaseShape *base, uint32_t nfixed);
michael@0: 
michael@0:     /* Copy constructor disabled, to avoid misuse of the above form. */
michael@0:     Shape(const Shape &other) MOZ_DELETE;
michael@0: 
michael@0:     /*
michael@0:      * Whether this shape has a valid slot value. This may be true even if
michael@0:      * !hasSlot() (see SlotInfo comment above), and may be false even if
michael@0:      * hasSlot() if the shape is being constructed and has not had a slot
michael@0:      * assigned yet. After construction, hasSlot() implies !hasMissingSlot().
michael@0:      */
michael@0:     bool hasMissingSlot() const { return maybeSlot() == SHAPE_INVALID_SLOT; }
michael@0: 
michael@0:   public:
michael@0:     bool inDictionary() const {
michael@0:         return (flags & IN_DICTIONARY) != 0;
michael@0:     }
michael@0: 
michael@0:     PropertyOp getter() const { return base()->rawGetter; }
michael@0:     bool hasDefaultGetter() const {return !base()->rawGetter; }
michael@0:     PropertyOp getterOp() const { JS_ASSERT(!hasGetterValue()); return base()->rawGetter; }
michael@0:     JSObject *getterObject() const { JS_ASSERT(hasGetterValue()); return base()->getterObj; }
michael@0: 
michael@0:     // Per ES5, decode null getterObj as the undefined value, which encodes as null.
michael@0:     Value getterValue() const {
michael@0:         JS_ASSERT(hasGetterValue());
michael@0:         return base()->getterObj ? ObjectValue(*base()->getterObj) : UndefinedValue();
michael@0:     }
michael@0: 
michael@0:     Value getterOrUndefined() const {
michael@0:         return (hasGetterValue() && base()->getterObj)
michael@0:                ? ObjectValue(*base()->getterObj)
michael@0:                : UndefinedValue();
michael@0:     }
michael@0: 
michael@0:     StrictPropertyOp setter() const { return base()->rawSetter; }
michael@0:     bool hasDefaultSetter() const  { return !base()->rawSetter; }
michael@0:     StrictPropertyOp setterOp() const { JS_ASSERT(!hasSetterValue()); return base()->rawSetter; }
michael@0:     JSObject *setterObject() const { JS_ASSERT(hasSetterValue()); return base()->setterObj; }
michael@0: 
michael@0:     // Per ES5, decode null setterObj as the undefined value, which encodes as null.
michael@0:     Value setterValue() const {
michael@0:         JS_ASSERT(hasSetterValue());
michael@0:         return base()->setterObj ? ObjectValue(*base()->setterObj) : UndefinedValue();
michael@0:     }
michael@0: 
michael@0:     Value setterOrUndefined() const {
michael@0:         return (hasSetterValue() && base()->setterObj)
michael@0:                ? ObjectValue(*base()->setterObj)
michael@0:                : UndefinedValue();
michael@0:     }
michael@0: 
michael@0:     void update(PropertyOp getter, StrictPropertyOp setter, uint8_t attrs);
michael@0: 
michael@0:     bool matches(const Shape *other) const {
michael@0:         return propid_.get() == other->propid_.get() &&
michael@0:                matchesParamsAfterId(other->base(), other->maybeSlot(), other->attrs, other->flags);
michael@0:     }
michael@0: 
michael@0:     inline bool matches(const StackShape &other) const;
michael@0: 
michael@0:     bool matchesParamsAfterId(BaseShape *base, uint32_t aslot, unsigned aattrs, unsigned aflags) const
michael@0:     {
michael@0:         return base->unowned() == this->base()->unowned() &&
michael@0:                maybeSlot() == aslot &&
michael@0:                attrs == aattrs;
michael@0:     }
michael@0: 
michael@0:     bool get(JSContext* cx, HandleObject receiver, JSObject *obj, JSObject *pobj, MutableHandleValue vp);
michael@0:     bool set(JSContext* cx, HandleObject obj, HandleObject receiver, bool strict, MutableHandleValue vp);
michael@0: 
michael@0:     BaseShape *base() const { return base_.get(); }
michael@0: 
michael@0:     bool hasSlot() const {
michael@0:         return (attrs & JSPROP_SHARED) == 0;
michael@0:     }
michael@0:     uint32_t slot() const { JS_ASSERT(hasSlot() && !hasMissingSlot()); return maybeSlot(); }
michael@0:     uint32_t maybeSlot() const {
michael@0:         return slotInfo & SLOT_MASK;
michael@0:     }
michael@0: 
michael@0:     bool isEmptyShape() const {
michael@0:         JS_ASSERT_IF(JSID_IS_EMPTY(propid_), hasMissingSlot());
michael@0:         return JSID_IS_EMPTY(propid_);
michael@0:     }
michael@0: 
michael@0:     uint32_t slotSpan(const Class *clasp) const {
michael@0:         JS_ASSERT(!inDictionary());
michael@0:         uint32_t free = JSSLOT_FREE(clasp);
michael@0:         return hasMissingSlot() ? free : Max(free, maybeSlot() + 1);
michael@0:     }
michael@0: 
michael@0:     uint32_t slotSpan() const {
michael@0:         return slotSpan(getObjectClass());
michael@0:     }
michael@0: 
michael@0:     void setSlot(uint32_t slot) {
michael@0:         JS_ASSERT(slot <= SHAPE_INVALID_SLOT);
michael@0:         slotInfo = slotInfo & ~Shape::SLOT_MASK;
michael@0:         slotInfo = slotInfo | slot;
michael@0:     }
michael@0: 
michael@0:     uint32_t numFixedSlots() const {
michael@0:         return slotInfo >> FIXED_SLOTS_SHIFT;
michael@0:     }
michael@0: 
michael@0:     void setNumFixedSlots(uint32_t nfixed) {
michael@0:         JS_ASSERT(nfixed < FIXED_SLOTS_MAX);
michael@0:         slotInfo = slotInfo & ~FIXED_SLOTS_MASK;
michael@0:         slotInfo = slotInfo | (nfixed << FIXED_SLOTS_SHIFT);
michael@0:     }
michael@0: 
michael@0:     uint32_t numLinearSearches() const {
michael@0:         return (slotInfo & LINEAR_SEARCHES_MASK) >> LINEAR_SEARCHES_SHIFT;
michael@0:     }
michael@0: 
michael@0:     void incrementNumLinearSearches() {
michael@0:         uint32_t count = numLinearSearches();
michael@0:         JS_ASSERT(count < LINEAR_SEARCHES_MAX);
michael@0:         slotInfo = slotInfo & ~LINEAR_SEARCHES_MASK;
michael@0:         slotInfo = slotInfo | ((count + 1) << LINEAR_SEARCHES_SHIFT);
michael@0:     }
michael@0: 
michael@0:     const EncapsulatedId &propid() const {
michael@0:         JS_ASSERT(!isEmptyShape());
michael@0:         JS_ASSERT(!JSID_IS_VOID(propid_));
michael@0:         return propid_;
michael@0:     }
michael@0:     EncapsulatedId &propidRef() { JS_ASSERT(!JSID_IS_VOID(propid_)); return propid_; }
michael@0:     jsid propidRaw() const {
michael@0:         // Return the actual jsid, not an internal reference.
michael@0:         return propid();
michael@0:     }
michael@0: 
michael@0:     uint8_t attributes() const { return attrs; }
michael@0:     bool configurable() const { return (attrs & JSPROP_PERMANENT) == 0; }
michael@0:     bool enumerable() const { return (attrs & JSPROP_ENUMERATE) != 0; }
michael@0:     bool writable() const {
michael@0:         return (attrs & JSPROP_READONLY) == 0;
michael@0:     }
michael@0:     bool hasGetterValue() const { return attrs & JSPROP_GETTER; }
michael@0:     bool hasSetterValue() const { return attrs & JSPROP_SETTER; }
michael@0: 
michael@0:     bool isDataDescriptor() const {
michael@0:         return (attrs & (JSPROP_SETTER | JSPROP_GETTER)) == 0;
michael@0:     }
michael@0:     bool isAccessorDescriptor() const {
michael@0:         return (attrs & (JSPROP_SETTER | JSPROP_GETTER)) != 0;
michael@0:     }
michael@0: 
michael@0:     PropDesc::Writability writability() const {
michael@0:         return (attrs & JSPROP_READONLY) ? PropDesc::NonWritable : PropDesc::Writable;
michael@0:     }
michael@0:     PropDesc::Enumerability enumerability() const {
michael@0:         return (attrs & JSPROP_ENUMERATE) ? PropDesc::Enumerable : PropDesc::NonEnumerable;
michael@0:     }
michael@0:     PropDesc::Configurability configurability() const {
michael@0:         return (attrs & JSPROP_PERMANENT) ? PropDesc::NonConfigurable : PropDesc::Configurable;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * For ES5 compatibility, we allow properties with PropertyOp-flavored
michael@0:      * setters to be shadowed when set. The "own" property thereby created in
michael@0:      * the directly referenced object will have the same getter and setter as
michael@0:      * the prototype property. See bug 552432.
michael@0:      */
michael@0:     bool shadowable() const {
michael@0:         JS_ASSERT_IF(isDataDescriptor(), writable());
michael@0:         return hasSlot() || (attrs & JSPROP_SHADOWABLE);
michael@0:     }
michael@0: 
michael@0:     uint32_t entryCount() {
michael@0:         if (hasTable())
michael@0:             return table().entryCount;
michael@0:         uint32_t count = 0;
michael@0:         for (Shape::Range<NoGC> r(this); !r.empty(); r.popFront())
michael@0:             ++count;
michael@0:         return count;
michael@0:     }
michael@0: 
michael@0:     bool isBigEnoughForAShapeTable() {
michael@0:         JS_ASSERT(!hasTable());
michael@0:         Shape *shape = this;
michael@0:         uint32_t count = 0;
michael@0:         for (Shape::Range<NoGC> r(shape); !r.empty(); r.popFront()) {
michael@0:             ++count;
michael@0:             if (count >= ShapeTable::MIN_ENTRIES)
michael@0:                 return true;
michael@0:         }
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     void dump(JSContext *cx, FILE *fp) const;
michael@0:     void dumpSubtree(JSContext *cx, int level, FILE *fp) const;
michael@0: #endif
michael@0: 
michael@0:     void sweep();
michael@0:     void finalize(FreeOp *fop);
michael@0:     void removeChild(Shape *child);
michael@0: 
michael@0:     static inline ThingRootKind rootKind() { return THING_ROOT_SHAPE; }
michael@0: 
michael@0:     void markChildren(JSTracer *trc) {
michael@0:         MarkBaseShape(trc, &base_, "base");
michael@0:         gc::MarkId(trc, &propidRef(), "propid");
michael@0:         if (parent)
michael@0:             MarkShape(trc, &parent, "parent");
michael@0:     }
michael@0: 
michael@0:     inline Shape *search(ExclusiveContext *cx, jsid id);
michael@0:     inline Shape *searchLinear(jsid id);
michael@0: 
michael@0:     /* For JIT usage */
michael@0:     static inline size_t offsetOfBase() { return offsetof(Shape, base_); }
michael@0: 
michael@0:   private:
michael@0:     static void staticAsserts() {
michael@0:         JS_STATIC_ASSERT(offsetof(Shape, base_) == offsetof(js::shadow::Shape, base));
michael@0:         JS_STATIC_ASSERT(offsetof(Shape, slotInfo) == offsetof(js::shadow::Shape, slotInfo));
michael@0:         JS_STATIC_ASSERT(FIXED_SLOTS_SHIFT == js::shadow::Shape::FIXED_SLOTS_SHIFT);
michael@0:         static_assert(js::shadow::Object::MAX_FIXED_SLOTS <= FIXED_SLOTS_MAX,
michael@0:                       "verify numFixedSlots() bitfield is big enough");
michael@0:     }
michael@0: };
michael@0: 
michael@0: inline
michael@0: StackBaseShape::StackBaseShape(Shape *shape)
michael@0:   : flags(shape->getObjectFlags()),
michael@0:     clasp(shape->getObjectClass()),
michael@0:     parent(shape->getObjectParent()),
michael@0:     metadata(shape->getObjectMetadata()),
michael@0:     compartment(shape->compartment())
michael@0: {
michael@0:     updateGetterSetter(shape->attrs, shape->getter(), shape->setter());
michael@0: }
michael@0: 
michael@0: class AutoRooterGetterSetter
michael@0: {
michael@0:     class Inner : private JS::CustomAutoRooter
michael@0:     {
michael@0:       public:
michael@0:         inline Inner(ThreadSafeContext *cx, uint8_t attrs,
michael@0:                      PropertyOp *pgetter_, StrictPropertyOp *psetter_);
michael@0: 
michael@0:       private:
michael@0:         virtual void trace(JSTracer *trc);
michael@0: 
michael@0:         uint8_t attrs;
michael@0:         PropertyOp *pgetter;
michael@0:         StrictPropertyOp *psetter;
michael@0:     };
michael@0: 
michael@0:   public:
michael@0:     inline AutoRooterGetterSetter(ThreadSafeContext *cx, uint8_t attrs,
michael@0:                                   PropertyOp *pgetter, StrictPropertyOp *psetter
michael@0:                                   MOZ_GUARD_OBJECT_NOTIFIER_PARAM);
michael@0: 
michael@0:   private:
michael@0:     mozilla::Maybe<Inner> inner;
michael@0:     MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER
michael@0: };
michael@0: 
michael@0: struct EmptyShape : public js::Shape
michael@0: {
michael@0:     EmptyShape(UnownedBaseShape *base, uint32_t nfixed)
michael@0:       : js::Shape(base, nfixed)
michael@0:     {
michael@0:         // Only empty shapes can be NON_NATIVE.
michael@0:         if (!getObjectClass()->isNative())
michael@0:             flags |= NON_NATIVE;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Lookup an initial shape matching the given parameters, creating an empty
michael@0:      * shape if none was found.
michael@0:      */
michael@0:     static Shape *getInitialShape(ExclusiveContext *cx, const Class *clasp,
michael@0:                                   TaggedProto proto, JSObject *metadata,
michael@0:                                   JSObject *parent, size_t nfixed, uint32_t objectFlags = 0);
michael@0:     static Shape *getInitialShape(ExclusiveContext *cx, const Class *clasp,
michael@0:                                   TaggedProto proto, JSObject *metadata,
michael@0:                                   JSObject *parent, gc::AllocKind kind, uint32_t objectFlags = 0);
michael@0: 
michael@0:     /*
michael@0:      * Reinsert an alternate initial shape, to be returned by future
michael@0:      * getInitialShape calls, until the new shape becomes unreachable in a GC
michael@0:      * and the table entry is purged.
michael@0:      */
michael@0:     static void insertInitialShape(ExclusiveContext *cx, HandleShape shape, HandleObject proto);
michael@0: 
michael@0:     /*
michael@0:      * Some object subclasses are allocated with a built-in set of properties.
michael@0:      * The first time such an object is created, these built-in properties must
michael@0:      * be set manually, to compute an initial shape.  Afterward, that initial
michael@0:      * shape can be reused for newly-created objects that use the subclass's
michael@0:      * standard prototype.  This method should be used in a post-allocation
michael@0:      * init method, to ensure that objects of such subclasses compute and cache
michael@0:      * the initial shape, if it hasn't already been computed.
michael@0:      */
michael@0:     template<class ObjectSubclass>
michael@0:     static inline bool
michael@0:     ensureInitialCustomShape(ExclusiveContext *cx, Handle<ObjectSubclass*> obj);
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * Entries for the per-compartment initialShapes set indexing initial shapes
michael@0:  * for objects in the compartment and the associated types.
michael@0:  */
michael@0: struct InitialShapeEntry
michael@0: {
michael@0:     /*
michael@0:      * Initial shape to give to the object. This is an empty shape, except for
michael@0:      * certain classes (e.g. String, RegExp) which may add certain baked-in
michael@0:      * properties.
michael@0:      */
michael@0:     ReadBarriered<Shape> shape;
michael@0: 
michael@0:     /*
michael@0:      * Matching prototype for the entry. The shape of an object determines its
michael@0:      * prototype, but the prototype cannot be determined from the shape itself.
michael@0:      */
michael@0:     TaggedProto proto;
michael@0: 
michael@0:     /* State used to determine a match on an initial shape. */
michael@0:     struct Lookup {
michael@0:         const Class *clasp;
michael@0:         TaggedProto hashProto;
michael@0:         TaggedProto matchProto;
michael@0:         JSObject *hashParent;
michael@0:         JSObject *matchParent;
michael@0:         JSObject *hashMetadata;
michael@0:         JSObject *matchMetadata;
michael@0:         uint32_t nfixed;
michael@0:         uint32_t baseFlags;
michael@0:         Lookup(const Class *clasp, TaggedProto proto, JSObject *parent, JSObject *metadata,
michael@0:                uint32_t nfixed, uint32_t baseFlags)
michael@0:           : clasp(clasp),
michael@0:             hashProto(proto), matchProto(proto),
michael@0:             hashParent(parent), matchParent(parent),
michael@0:             hashMetadata(metadata), matchMetadata(metadata),
michael@0:             nfixed(nfixed), baseFlags(baseFlags)
michael@0:         {}
michael@0: 
michael@0: #ifdef JSGC_GENERATIONAL
michael@0:         /*
michael@0:          * For use by generational GC post barriers. Look up an entry whose
michael@0:          * parent and metadata fields may have been moved, but was hashed with
michael@0:          * the original values.
michael@0:          */
michael@0:         Lookup(const Class *clasp, TaggedProto proto,
michael@0:                JSObject *hashParent, JSObject *matchParent,
michael@0:                JSObject *hashMetadata, JSObject *matchMetadata,
michael@0:                uint32_t nfixed, uint32_t baseFlags)
michael@0:           : clasp(clasp),
michael@0:             hashProto(proto), matchProto(proto),
michael@0:             hashParent(hashParent), matchParent(matchParent),
michael@0:             hashMetadata(hashMetadata), matchMetadata(matchMetadata),
michael@0:             nfixed(nfixed), baseFlags(baseFlags)
michael@0:         {}
michael@0: #endif
michael@0:     };
michael@0: 
michael@0:     inline InitialShapeEntry();
michael@0:     inline InitialShapeEntry(const ReadBarriered<Shape> &shape, TaggedProto proto);
michael@0: 
michael@0:     inline Lookup getLookup() const;
michael@0: 
michael@0:     static inline HashNumber hash(const Lookup &lookup);
michael@0:     static inline bool match(const InitialShapeEntry &key, const Lookup &lookup);
michael@0:     static void rekey(InitialShapeEntry &k, const InitialShapeEntry& newKey) { k = newKey; }
michael@0: };
michael@0: 
michael@0: typedef HashSet<InitialShapeEntry, InitialShapeEntry, SystemAllocPolicy> InitialShapeSet;
michael@0: 
michael@0: struct StackShape
michael@0: {
michael@0:     /* For performance, StackShape only roots when absolutely necessary. */
michael@0:     UnownedBaseShape *base;
michael@0:     jsid             propid;
michael@0:     uint32_t         slot_;
michael@0:     uint8_t          attrs;
michael@0:     uint8_t          flags;
michael@0: 
michael@0:     explicit StackShape(UnownedBaseShape *base, jsid propid, uint32_t slot,
michael@0:                         unsigned attrs, unsigned flags)
michael@0:       : base(base),
michael@0:         propid(propid),
michael@0:         slot_(slot),
michael@0:         attrs(uint8_t(attrs)),
michael@0:         flags(uint8_t(flags))
michael@0:     {
michael@0:         JS_ASSERT(base);
michael@0:         JS_ASSERT(!JSID_IS_VOID(propid));
michael@0:         JS_ASSERT(slot <= SHAPE_INVALID_SLOT);
michael@0:         JS_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
michael@0:     }
michael@0: 
michael@0:     StackShape(Shape *shape)
michael@0:       : base(shape->base()->unowned()),
michael@0:         propid(shape->propidRef()),
michael@0:         slot_(shape->maybeSlot()),
michael@0:         attrs(shape->attrs),
michael@0:         flags(shape->flags)
michael@0:     {}
michael@0: 
michael@0:     bool hasSlot() const { return (attrs & JSPROP_SHARED) == 0; }
michael@0:     bool hasMissingSlot() const { return maybeSlot() == SHAPE_INVALID_SLOT; }
michael@0: 
michael@0:     uint32_t slot() const { JS_ASSERT(hasSlot() && !hasMissingSlot()); return slot_; }
michael@0:     uint32_t maybeSlot() const { return slot_; }
michael@0: 
michael@0:     uint32_t slotSpan() const {
michael@0:         uint32_t free = JSSLOT_FREE(base->clasp_);
michael@0:         return hasMissingSlot() ? free : (maybeSlot() + 1);
michael@0:     }
michael@0: 
michael@0:     void setSlot(uint32_t slot) {
michael@0:         JS_ASSERT(slot <= SHAPE_INVALID_SLOT);
michael@0:         slot_ = slot;
michael@0:     }
michael@0: 
michael@0:     HashNumber hash() const {
michael@0:         HashNumber hash = uintptr_t(base);
michael@0: 
michael@0:         /* Accumulate from least to most random so the low bits are most random. */
michael@0:         hash = mozilla::RotateLeft(hash, 4) ^ attrs;
michael@0:         hash = mozilla::RotateLeft(hash, 4) ^ slot_;
michael@0:         hash = mozilla::RotateLeft(hash, 4) ^ JSID_BITS(propid);
michael@0:         return hash;
michael@0:     }
michael@0: 
michael@0:     // For RootedGeneric<StackShape*>
michael@0:     static inline js::ThingRootKind rootKind() { return js::THING_ROOT_CUSTOM; }
michael@0:     void trace(JSTracer *trc);
michael@0: };
michael@0: 
michael@0: } /* namespace js */
michael@0: 
michael@0: /* js::Shape pointer tag bit indicating a collision. */
michael@0: #define SHAPE_COLLISION                 (uintptr_t(1))
michael@0: #define SHAPE_REMOVED                   ((js::Shape *) SHAPE_COLLISION)
michael@0: 
michael@0: /* Functions to get and set shape pointer values and collision flags. */
michael@0: 
michael@0: inline bool
michael@0: SHAPE_IS_FREE(js::Shape *shape)
michael@0: {
michael@0:     return shape == nullptr;
michael@0: }
michael@0: 
michael@0: inline bool
michael@0: SHAPE_IS_REMOVED(js::Shape *shape)
michael@0: {
michael@0:     return shape == SHAPE_REMOVED;
michael@0: }
michael@0: 
michael@0: inline bool
michael@0: SHAPE_IS_LIVE(js::Shape *shape)
michael@0: {
michael@0:     return shape > SHAPE_REMOVED;
michael@0: }
michael@0: 
michael@0: inline void
michael@0: SHAPE_FLAG_COLLISION(js::Shape **spp, js::Shape *shape)
michael@0: {
michael@0:     *spp = reinterpret_cast<js::Shape*>(uintptr_t(shape) | SHAPE_COLLISION);
michael@0: }
michael@0: 
michael@0: inline bool
michael@0: SHAPE_HAD_COLLISION(js::Shape *shape)
michael@0: {
michael@0:     return uintptr_t(shape) & SHAPE_COLLISION;
michael@0: }
michael@0: 
michael@0: inline js::Shape *
michael@0: SHAPE_CLEAR_COLLISION(js::Shape *shape)
michael@0: {
michael@0:     return reinterpret_cast<js::Shape*>(uintptr_t(shape) & ~SHAPE_COLLISION);
michael@0: }
michael@0: 
michael@0: inline js::Shape *
michael@0: SHAPE_FETCH(js::Shape **spp)
michael@0: {
michael@0:     return SHAPE_CLEAR_COLLISION(*spp);
michael@0: }
michael@0: 
michael@0: inline void
michael@0: SHAPE_STORE_PRESERVING_COLLISION(js::Shape **spp, js::Shape *shape)
michael@0: {
michael@0:     *spp = reinterpret_cast<js::Shape*>(uintptr_t(shape) |
michael@0:                                         uintptr_t(SHAPE_HAD_COLLISION(*spp)));
michael@0: }
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: inline
michael@0: Shape::Shape(const StackShape &other, uint32_t nfixed)
michael@0:   : base_(other.base),
michael@0:     propid_(other.propid),
michael@0:     slotInfo(other.maybeSlot() | (nfixed << FIXED_SLOTS_SHIFT)),
michael@0:     attrs(other.attrs),
michael@0:     flags(other.flags),
michael@0:     parent(nullptr)
michael@0: {
michael@0:     JS_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
michael@0:     kids.setNull();
michael@0: }
michael@0: 
michael@0: inline
michael@0: Shape::Shape(UnownedBaseShape *base, uint32_t nfixed)
michael@0:   : base_(base),
michael@0:     propid_(JSID_EMPTY),
michael@0:     slotInfo(SHAPE_INVALID_SLOT | (nfixed << FIXED_SLOTS_SHIFT)),
michael@0:     attrs(JSPROP_SHARED),
michael@0:     flags(0),
michael@0:     parent(nullptr)
michael@0: {
michael@0:     JS_ASSERT(base);
michael@0:     kids.setNull();
michael@0: }
michael@0: 
michael@0: inline Shape *
michael@0: Shape::searchLinear(jsid id)
michael@0: {
michael@0:     /*
michael@0:      * Non-dictionary shapes can acquire a table at any point the main thread
michael@0:      * is operating on it, so other threads inspecting such shapes can't use
michael@0:      * their table without racing. This function can be called from any thread
michael@0:      * on any non-dictionary shape.
michael@0:      */
michael@0:     JS_ASSERT(!inDictionary());
michael@0: 
michael@0:     for (Shape *shape = this; shape; ) {
michael@0:         if (shape->propidRef() == id)
michael@0:             return shape;
michael@0:         shape = shape->parent;
michael@0:     }
michael@0: 
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Keep this function in sync with search. It neither hashifies the start
michael@0:  * shape nor increments linear search count.
michael@0:  */
michael@0: inline Shape *
michael@0: Shape::searchNoHashify(Shape *start, jsid id)
michael@0: {
michael@0:     /*
michael@0:      * If we have a table, search in the shape table, else do a linear
michael@0:      * search. We never hashify into a table in parallel.
michael@0:      */
michael@0:     if (start->hasTable()) {
michael@0:         Shape **spp = start->table().search(id, false);
michael@0:         return SHAPE_FETCH(spp);
michael@0:     }
michael@0: 
michael@0:     return start->searchLinear(id);
michael@0: }
michael@0: 
michael@0: inline bool
michael@0: Shape::matches(const StackShape &other) const
michael@0: {
michael@0:     return propid_.get() == other.propid &&
michael@0:            matchesParamsAfterId(other.base, other.slot_, other.attrs, other.flags);
michael@0: }
michael@0: 
michael@0: template<> struct RootKind<Shape *> : SpecificRootKind<Shape *, THING_ROOT_SHAPE> {};
michael@0: template<> struct RootKind<BaseShape *> : SpecificRootKind<BaseShape *, THING_ROOT_BASE_SHAPE> {};
michael@0: 
michael@0: // Property lookup hooks on objects are required to return a non-nullptr shape
michael@0: // to signify that the property has been found. For cases where the property is
michael@0: // not actually represented by a Shape, use a dummy value. This includes all
michael@0: // properties of non-native objects, and dense elements for native objects.
michael@0: // Use separate APIs for these two cases.
michael@0: 
michael@0: static inline void
michael@0: MarkNonNativePropertyFound(MutableHandleShape propp)
michael@0: {
michael@0:     propp.set(reinterpret_cast<Shape*>(1));
michael@0: }
michael@0: 
michael@0: template <AllowGC allowGC>
michael@0: static inline void
michael@0: MarkDenseOrTypedArrayElementFound(typename MaybeRooted<Shape*, allowGC>::MutableHandleType propp)
michael@0: {
michael@0:     propp.set(reinterpret_cast<Shape*>(1));
michael@0: }
michael@0: 
michael@0: static inline bool
michael@0: IsImplicitDenseOrTypedArrayElement(Shape *prop)
michael@0: {
michael@0:     return prop == reinterpret_cast<Shape*>(1);
michael@0: }
michael@0: 
michael@0: } // namespace js
michael@0: 
michael@0: #ifdef _MSC_VER
michael@0: #pragma warning(pop)
michael@0: #pragma warning(pop)
michael@0: #endif
michael@0: 
michael@0: namespace JS {
michael@0: template<> class AnchorPermitted<js::Shape *> { };
michael@0: template<> class AnchorPermitted<const js::Shape *> { };
michael@0: }
michael@0: 
michael@0: #endif /* vm_Shape_h */