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