1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sw=4 et tw=99:
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
7 * The contents of this file are subject to the Mozilla Public License Version
8 * 1.1 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14 * for the specific language governing rights and limitations under the
17 * The Original Code is Mozilla Communicator client code, released
20 * The Initial Developer of the Original Code is
21 * Netscape Communications Corporation.
22 * Portions created by the Initial Developer are Copyright (C) 1998
23 * the Initial Developer. All Rights Reserved.
27 * Alternatively, the contents of this file may be used under the terms of
28 * either of the GNU General Public License Version 2 or later (the "GPL"),
29 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30 * in which case the provisions of the GPL or the LGPL are applicable instead
31 * of those above. If you wish to allow use of your version of this file only
32 * under the terms of either the GPL or the LGPL, and not to allow others to
33 * use your version of this file under the terms of the MPL, indicate your
34 * decision by deleting the provisions above and replace them with the notice
35 * and other provisions required by the GPL or the LGPL. If you do not delete
36 * the provisions above, a recipient may use your version of this file under
37 * the terms of any one of the MPL, the GPL or the LGPL.
39 * ***** END LICENSE BLOCK ***** */
53 #include "jscompartment.h"
54 #include "jshashtable.h"
58 #include "jspropertytree.h"
59 #include "jsstrinlines.h"
63 #pragma warning(disable:4800)
65 #pragma warning(disable:4100) /* Silence unreferenced formal parameter warnings */
69 * Given P independent, non-unique properties each of size S words mapped by
70 * all scopes in a runtime, construct a property tree of N nodes each of size
71 * S+L words (L for tree linkage). A nominal L value is 2 for leftmost-child
72 * and right-sibling links. We hope that the N < P by enough that the space
73 * overhead of L, and the overhead of scope entries pointing at property tree
76 * The tree construction goes as follows. If any empty scope in the runtime
77 * has a property X added to it, find or create a node under the tree root
78 * labeled X, and set obj->lastProp to point at that node. If any non-empty
79 * scope whose most recently added property is labeled Y has another property
80 * labeled Z added, find or create a node for Z under the node that was added
81 * for Y, and set obj->lastProp to point at that node.
83 * A property is labeled by its members' values: id, getter, setter, slot,
84 * attributes, tiny or short id, and a field telling for..in order. Note that
85 * labels are not unique in the tree, but they are unique among a node's kids
86 * (barring rare and benign multi-threaded race condition outcomes, see below)
87 * and along any ancestor line from the tree root to a given leaf node (except
88 * for the hard case of duplicate formal parameters to a function).
90 * Thus the root of the tree represents all empty scopes, and the first ply
91 * of the tree represents all scopes containing one property, etc. Each node
92 * in the tree can stand for any number of scopes having the same ordered set
93 * of properties, where that node was the last added to the scope. (We need
94 * not store the root of the tree as a node, and do not -- all we need are
97 * Sidebar on for..in loop order: ECMA requires no particular order, but this
98 * implementation has promised and delivered property definition order, and
99 * compatibility is king. We could use an order number per property, which
100 * would require a sort in js_Enumerate, and an entry order generation number
101 * per scope. An order number beats a list, which should be doubly-linked for
102 * O(1) delete. An even better scheme is to use a parent link in the property
103 * tree, so that the ancestor line can be iterated from obj->lastProp when
104 * filling in a JSIdArray from back to front. This parent link also helps the
105 * GC to sweep properties iteratively.
107 * What if a property Y is deleted from a scope? If Y is the last property in
108 * the scope, we simply adjust the scope's lastProp member after we remove the
109 * scope's hash-table entry pointing at that property node. The parent link
110 * mentioned in the for..in sidebar above makes this adjustment O(1). But if
111 * Y comes between X and Z in the scope, then we might have to "fork" the tree
112 * at X, leaving X->Y->Z in case other scopes have those properties added in
113 * that order; and to finish the fork, we'd add a node labeled Z with the path
114 * X->Z, if it doesn't exist. This could lead to lots of extra nodes, and to
115 * O(n^2) growth when deleting lots of properties.
117 * Rather, for O(1) growth all around, we should share the path X->Y->Z among
118 * scopes having those three properties added in that order, and among scopes
119 * having only X->Z where Y was deleted. All such scopes have a lastProp that
120 * points to the Z child of Y. But a scope in which Y was deleted does not
121 * have a table entry for Y, and when iterating that scope by traversing the
122 * ancestor line from Z, we will have to test for a table entry for each node,
123 * skipping nodes that lack entries.
125 * What if we add Y again? X->Y->Z->Y is wrong and we'll enumerate Y twice.
126 * Therefore we must fork in such a case if not earlier, or do something else.
127 * We used to fork on the theory that set after delete is rare, but the Web is
128 * a harsh mistress, and we now convert the scope to a "dictionary" on first
129 * delete, to avoid O(n^2) growth in the property tree.
131 * What about thread safety? If the property tree operations done by requests
132 * are find-node and insert-node, then the only hazard is duplicate insertion.
133 * This is harmless except for minor bloat. When all requests have ended or
134 * been suspended, the GC is free to sweep the tree after marking all nodes
135 * reachable from scopes, performing remove-node operations as needed.
137 * Is the property tree worth it compared to property storage in each table's
138 * entries? To decide, we must find the relation <> between the words used
139 * with a property tree and the words required without a tree.
141 * Model all scopes as one super-scope of capacity T entries (T a power of 2).
142 * Let alpha be the load factor of this double hash-table. With the property
143 * tree, each entry in the table is a word-sized pointer to a node that can be
144 * shared by many scopes. But all such pointers are overhead compared to the
145 * situation without the property tree, where the table stores property nodes
146 * directly, as entries each of size S words. With the property tree, we need
147 * L=2 extra words per node for siblings and kids pointers. Without the tree,
148 * (1-alpha)*S*T words are wasted on free or removed sentinel-entries required
153 * (property tree) <> (no property tree)
155 * N*(S+L) + T <> P*S + (1-alpha)*S*T
156 * N*(S+L) + alpha*T + (1-alpha)*T <> P*S + (1-alpha)*S*T
158 * Note that P is alpha*T by definition, so
160 * N*(S+L) + P + (1-alpha)*T <> P*S + (1-alpha)*S*T
161 * N*(S+L) <> P*S - P + (1-alpha)*S*T - (1-alpha)*T
162 * N*(S+L) <> (P + (1-alpha)*T) * (S-1)
163 * N*(S+L) <> (P + (1-alpha)*P/alpha) * (S-1)
164 * N*(S+L) <> P * (1/alpha) * (S-1)
166 * Let N = P*beta for a compression ratio beta, beta <= 1:
168 * P*beta*(S+L) <> P * (1/alpha) * (S-1)
169 * beta*(S+L) <> (S-1)/alpha
170 * beta <> (S-1)/((S+L)*alpha)
172 * For S = 6 (32-bit architectures) and L = 2, the property tree wins iff
176 * We ensure that alpha <= .75, so the property tree wins if beta < .83_. An
177 * average beta from recent Mozilla browser startups was around .6.
179 * Can we reduce L? Observe that the property tree degenerates into a list of
180 * lists if at most one property Y follows X in all scopes. In or near such a
181 * case, we waste a word on the right-sibling link outside of the root ply of
182 * the tree. Note also that the root ply tends to be large, so O(n^2) growth
183 * searching it is likely, indicating the need for hashing (but with increased
184 * thread safety costs).
186 * If only K out of N nodes in the property tree have more than one child, we
187 * could eliminate the sibling link and overlay a children list or hash-table
188 * pointer on the leftmost-child link (which would then be either null or an
189 * only-child link; the overlay could be tagged in the low bit of the pointer,
190 * or flagged elsewhere in the property tree node, although such a flag must
191 * not be considered when comparing node labels during tree search).
193 * For such a system, L = 1 + (K * averageChildrenTableSize) / N instead of 2.
194 * If K << N, L approaches 1 and the property tree wins if beta < .95.
196 * We observe that fan-out below the root ply of the property tree appears to
197 * have extremely low degree (see the MeterPropertyTree code that histograms
198 * child-counts in jsscope.c), so instead of a hash-table we use a linked list
199 * of child node pointer arrays ("kid chunks"). The details are isolated in
200 * jspropertytree.h/.cpp; others must treat js::Shape.kids as opaque.
202 * One final twist (can you stand it?): the vast majority (~95% or more) of
203 * scopes are looked up fewer than three times; in these cases, initializing
204 * scope->table isn't worth it. So instead of always allocating scope->table,
205 * we leave it null while initializing all the other scope members as if it
206 * were non-null and minimal-length. Until a scope is searched
207 * HASH_MIN_SEARCHES times, we use linear search from obj->lastProp to find a
208 * given id, and save on the time and space overhead of creating a hash table.
211 #define SHAPE_INVALID_SLOT 0xffffffff
216 * Shapes use multiplicative hashing, _a la_ jsdhash.[ch], but specialized to
217 * minimize footprint. But if a Shape lineage has been searched fewer than
218 * HASH_MIN_SEARCHES times, we use linear search and avoid allocating
221 struct PropertyTable
{
222 static const uint32 HASH_MIN_SEARCHES
= 7;
223 static const uint32 MIN_SIZE_LOG2
= 4;
224 static const uint32 MIN_SIZE
= JS_BIT(MIN_SIZE_LOG2
);
226 int hashShift
; /* multiplicative hash shift */
228 uint32 entryCount
; /* number of entries in table */
229 uint32 removedCount
; /* removed entry sentinels in table */
230 uint32 freelist
; /* SHAPE_INVALID_SLOT or head of slot
231 freelist in owning dictionary-mode
233 js::Shape
**entries
; /* table of ptrs to shared tree nodes */
235 PropertyTable(uint32 nentries
)
236 : hashShift(JS_DHASH_BITS
- MIN_SIZE_LOG2
),
237 entryCount(nentries
),
239 freelist(SHAPE_INVALID_SLOT
)
241 /* NB: entries is set by init, which must be called. */
248 /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */
249 uint32
capacity() const { return JS_BIT(JS_DHASH_BITS
- hashShift
); }
251 /* Whether we need to grow. We want to do this if the load factor is >= 0.75 */
252 bool needsToGrow() const {
253 uint32 size
= capacity();
254 return entryCount
+ removedCount
>= size
- (size
>> 2);
258 * Try to grow the table. On failure, reports out of memory on cx
259 * and returns false. This will make any extant pointers into the
260 * table invalid. Don't call this unless needsToGrow() is true.
262 bool grow(JSContext
*cx
);
265 * NB: init and change are fallible but do not report OOM, so callers can
266 * cope or ignore. They do however use JSRuntime's calloc method in order
267 * to update the malloc counter on success.
269 bool init(JSRuntime
*rt
, js::Shape
*lastProp
);
270 bool change(int log2Delta
, JSContext
*cx
);
271 js::Shape
**search(jsid id
, bool adding
);
282 static inline PropertyOp
283 CastAsPropertyOp(js::Class
*clasp
)
285 return JS_DATA_TO_FUNC_PTR(PropertyOp
, clasp
);
289 * Reuse the API-only JSPROP_INDEX attribute to mean shadowability.
291 #define JSPROP_SHADOWABLE JSPROP_INDEX
293 struct Shape
: public JSObjectMap
295 friend struct ::JSObject
;
296 friend struct ::JSFunction
;
297 friend class js::PropertyTree
;
298 friend class js::Bindings
;
299 friend bool IsShapeAboutToBeFinalized(JSContext
*cx
, const js::Shape
*shape
);
302 mutable uint32 numSearches
; /* Only updated until it reaches HASH_MIN_SEARCHES. */
303 mutable js::PropertyTable
*table
;
306 inline void freeTable(JSContext
*cx
);
308 static bool initRuntimeState(JSContext
*cx
);
309 static void finishRuntimeState(JSContext
*cx
);
312 EMPTY_ARGUMENTS_SHAPE
= 1,
313 EMPTY_BLOCK_SHAPE
= 2,
314 EMPTY_CALL_SHAPE
= 3,
315 EMPTY_DECL_ENV_SHAPE
= 4,
316 EMPTY_ENUMERATOR_SHAPE
= 5,
317 EMPTY_WITH_SHAPE
= 6,
318 LAST_RESERVED_SHAPE
= 6
325 js::PropertyOp rawGetter
; /* getter and setter hooks or objects */
326 JSObject
*getterObj
; /* user-defined callable "get" object or
327 null if shape->hasGetterValue(); or
328 joined function object if METHOD flag
330 js::Class
*clasp
; /* prototype class for empty scope */
334 js::PropertyOp rawSetter
; /* getter is JSObject* and setter is 0
335 if shape->isMethod() */
336 JSObject
*setterObj
; /* user-defined callable "set" object or
337 null if shape->hasSetterValue() */
341 uint32 slot
; /* abstract index in object slots */
343 uint8 attrs
; /* attributes, see jsapi.h JSPROP_* */
344 mutable uint8 flags
; /* flags, see below for defines */
346 int16 shortid
; /* tinyid, or local arg/var index */
349 mutable js::Shape
*parent
; /* parent node, reverse for..in order */
351 mutable js::KidsPointer kids
; /* null, single child, or a tagged ptr
352 to many-kids data structure */
353 mutable js::Shape
**listp
; /* dictionary list starting at lastProp
354 has a double-indirect back pointer,
355 either to shape->parent if not last,
356 else to obj->lastProp */
359 static inline js::Shape
**search(JSRuntime
*rt
, js::Shape
**startp
, jsid id
,
360 bool adding
= false);
361 static js::Shape
*newDictionaryShape(JSContext
*cx
, const js::Shape
&child
, js::Shape
**listp
);
362 static js::Shape
*newDictionaryList(JSContext
*cx
, js::Shape
**listp
);
363 static js::Shape
*newDictionaryShapeForAddProperty(JSContext
*cx
, jsid id
,
364 PropertyOp getter
, PropertyOp setter
,
365 uint32 slot
, uintN attrs
,
366 uintN flags
, intN shortid
);
368 inline void removeFromDictionary(JSObject
*obj
) const;
369 inline void insertIntoDictionary(js::Shape
**dictp
);
371 js::Shape
*getChild(JSContext
*cx
, const js::Shape
&child
, js::Shape
**listp
);
373 bool hashify(JSRuntime
*rt
);
375 void setTable(js::PropertyTable
*t
) const {
376 JS_ASSERT_IF(t
&& t
->freelist
!= SHAPE_INVALID_SLOT
, t
->freelist
< slotSpan
);
381 * Setter for parent. The challenge is to maintain JSObjectMap::slotSpan in
382 * the face of arbitrary slot order.
384 * By induction, an empty shape has a slotSpan member correctly computed as
385 * JSCLASS_FREE(clasp) -- see EmptyShape's constructor in jsscopeinlines.h.
386 * This is the basis case, where p is null.
388 * Any child shape, whether in a shape tree or in a dictionary list, must
389 * have a slotSpan either one greater than its slot value (if the child's
390 * slot is SHAPE_INVALID_SLOT, this will yield 0; the static assertion
391 * below enforces this), or equal to its parent p's slotSpan, whichever is
392 * greater. This is the inductive step.
394 * If we maintained shape paths such that parent slot was always one less
395 * than child slot, possibly with an exception for SHAPE_INVALID_SLOT slot
396 * values where we would use another way of computing slotSpan based on the
397 * PropertyTable (as JSC does), then we would not need to store slotSpan in
398 * Shape (to be precise, in its base struct, JSobjectMap).
400 * But we currently scramble slots along shape paths due to resolve-based
401 * creation of shapes mapping reserved slots, and we do not have the needed
402 * PropertyTable machinery to use as an alternative when parent slot is not
403 * one less than child slot. This machinery is neither simple nor free, as
404 * it must involve creating a table for any slot-less transition and then
405 * pinning the table to its shape.
407 * Use of 'delete' can scramble slots along the shape lineage too, although
408 * it always switches the target object to dictionary mode, so the cost of
409 * a pinned table is less onerous.
411 * Note that allocating a uint32 slotSpan member in JSObjectMap takes no
412 * net extra space on 64-bit targets (it packs with shape). And on 32-bit
413 * targets, adding slotSpan to JSObjectMap takes no gross extra space,
414 * because Shape rounds up to an even number of 32-bit words (required for
415 * GC-thing and js::Value allocation in any event) on 32-bit targets.
417 * So in terms of space, we can afford to maintain both slotSpan and slot,
418 * but it might be better if we eliminated slotSpan using slot combined
419 * with an auxiliary mechanism based on table.
421 void setParent(js::Shape
*p
) {
422 JS_STATIC_ASSERT(uint32(SHAPE_INVALID_SLOT
) == ~uint32(0));
424 slotSpan
= JS_MAX(p
->slotSpan
, slot
+ 1);
425 JS_ASSERT(slotSpan
< JSObject::NSLOTS_LIMIT
);
429 void insertFree(js::Shape
**freep
) {
431 memset(this, JS_FREE_PATTERN
, sizeof *this);
436 parent
->listp
= &parent
;
442 JS_ASSERT(JSID_IS_VOID(id
));
445 parent
->listp
= listp
;
449 const js::Shape
*previous() const {
461 Range(const Shape
*shape
) : cursor(shape
) { }
464 JS_ASSERT_IF(!cursor
->parent
, JSID_IS_EMPTY(cursor
->id
));
465 return !cursor
->parent
;
468 const Shape
&front() const {
475 cursor
= cursor
->parent
;
485 * Implementation-private bits stored in shape->flags. See public: enum {}
486 * flags further below, which were allocated FCFS over time, so interleave
496 * Set during a shape-regenerating GC if the shape has already been
501 /* Property stored in per-object dictionary, not shared property tree. */
502 IN_DICTIONARY
= 0x08,
504 /* Prevent unwanted mutation of shared Bindings::lastBinding nodes. */
508 Shape(jsid id
, js::PropertyOp getter
, js::PropertyOp setter
, uint32 slot
, uintN attrs
,
509 uintN flags
, intN shortid
, uint32 shape
= INVALID_SHAPE
, uint32 slotSpan
= 0);
511 /* Used by EmptyShape (see jsscopeinlines.h). */
512 Shape(JSContext
*cx
, Class
*aclasp
);
514 bool marked() const { return (flags
& MARK
) != 0; }
515 void mark() const { flags
|= MARK
; }
516 void clearMark() { flags
&= ~MARK
; }
518 bool hasRegenFlag() const { return (flags
& SHAPE_REGEN
) != 0; }
519 void setRegenFlag() { flags
|= SHAPE_REGEN
; }
520 void clearRegenFlag() { flags
&= ~SHAPE_REGEN
; }
522 bool inDictionary() const { return (flags
& IN_DICTIONARY
) != 0; }
523 bool frozen() const { return (flags
& FROZEN
) != 0; }
524 void setFrozen() { flags
|= FROZEN
; }
526 bool isEmptyShape() const { JS_ASSERT_IF(!parent
, JSID_IS_EMPTY(id
)); return !parent
; }
529 /* Public bits stored in shape->flags. */
534 PUBLIC_FLAGS
= ALIAS
| HAS_SHORTID
| METHOD
537 uintN
getFlags() const { return flags
& PUBLIC_FLAGS
; }
538 bool isAlias() const { return (flags
& ALIAS
) != 0; }
539 bool hasShortID() const { return (flags
& HAS_SHORTID
) != 0; }
540 bool isMethod() const { return (flags
& METHOD
) != 0; }
542 JSObject
&methodObject() const { JS_ASSERT(isMethod()); return *getterObj
; }
544 js::PropertyOp
getter() const { return rawGetter
; }
545 bool hasDefaultGetter() const { return !rawGetter
; }
546 js::PropertyOp
getterOp() const { JS_ASSERT(!hasGetterValue()); return rawGetter
; }
547 JSObject
*getterObject() const { JS_ASSERT(hasGetterValue()); return getterObj
; }
549 // Per ES5, decode null getterObj as the undefined value, which encodes as null.
550 js::Value
getterValue() const {
551 JS_ASSERT(hasGetterValue());
552 return getterObj
? js::ObjectValue(*getterObj
) : js::UndefinedValue();
555 js::Value
getterOrUndefined() const {
556 return hasGetterValue() && getterObj
? js::ObjectValue(*getterObj
) : js::UndefinedValue();
559 js::PropertyOp
setter() const { return rawSetter
; }
560 bool hasDefaultSetter() const { return !rawSetter
; }
561 js::PropertyOp
setterOp() const { JS_ASSERT(!hasSetterValue()); return rawSetter
; }
562 JSObject
*setterObject() const { JS_ASSERT(hasSetterValue()); return setterObj
; }
564 // Per ES5, decode null setterObj as the undefined value, which encodes as null.
565 js::Value
setterValue() const {
566 JS_ASSERT(hasSetterValue());
567 return setterObj
? js::ObjectValue(*setterObj
) : js::UndefinedValue();
570 js::Value
setterOrUndefined() const {
571 return hasSetterValue() && setterObj
? js::ObjectValue(*setterObj
) : js::UndefinedValue();
574 inline JSDHashNumber
hash() const;
575 inline bool matches(const js::Shape
*p
) const;
576 inline bool matchesParamsAfterId(js::PropertyOp agetter
, js::PropertyOp asetter
,
577 uint32 aslot
, uintN aattrs
, uintN aflags
,
578 intN ashortid
) const;
580 bool get(JSContext
* cx
, JSObject
*receiver
, JSObject
*obj
, JSObject
*pobj
, js::Value
* vp
) const;
581 bool set(JSContext
* cx
, JSObject
*obj
, js::Value
* vp
) const;
583 inline bool isSharedPermanent() const;
585 void trace(JSTracer
*trc
) const;
587 bool hasSlot() const { return (attrs
& JSPROP_SHARED
) == 0; }
589 uint8
attributes() const { return attrs
; }
590 bool configurable() const { return (attrs
& JSPROP_PERMANENT
) == 0; }
591 bool enumerable() const { return (attrs
& JSPROP_ENUMERATE
) != 0; }
592 bool writable() const {
593 // JS_ASSERT(isDataDescriptor());
594 return (attrs
& JSPROP_READONLY
) == 0;
596 bool hasGetterValue() const { return attrs
& JSPROP_GETTER
; }
597 bool hasSetterValue() const { return attrs
& JSPROP_SETTER
; }
599 bool hasDefaultGetterOrIsMethod() const {
600 return hasDefaultGetter() || isMethod();
603 bool isDataDescriptor() const {
604 return (attrs
& (JSPROP_SETTER
| JSPROP_GETTER
)) == 0;
606 bool isAccessorDescriptor() const {
607 return (attrs
& (JSPROP_SETTER
| JSPROP_GETTER
)) != 0;
611 * For ES5 compatibility, we allow properties with JSPropertyOp-flavored
612 * setters to be shadowed when set. The "own" property thereby created in
613 * the directly referenced object will have the same getter and setter as
614 * the prototype property. See bug 552432.
616 bool shadowable() const {
617 JS_ASSERT_IF(isDataDescriptor(), writable());
618 return hasSlot() || (attrs
& JSPROP_SHADOWABLE
);
621 uint32
entryCount() const {
623 return table
->entryCount
;
625 const js::Shape
*shape
= this;
627 for (js::Shape::Range r
= shape
->all(); !r
.empty(); r
.popFront())
633 void dump(JSContext
*cx
, FILE *fp
) const;
634 void dumpSubtree(JSContext
*cx
, int level
, FILE *fp
) const;
638 struct EmptyShape
: public js::Shape
640 EmptyShape(JSContext
*cx
, js::Class
*aclasp
);
642 js::Class
*getClass() const { return clasp
; };
644 static EmptyShape
*create(JSContext
*cx
, js::Class
*clasp
) {
645 js::Shape
*eprop
= JS_PROPERTY_TREE(cx
).newShape(cx
);
648 return new (eprop
) EmptyShape(cx
, clasp
);
654 /* js::Shape pointer tag bit indicating a collision. */
655 #define SHAPE_COLLISION (jsuword(1))
656 #define SHAPE_REMOVED ((js::Shape *) SHAPE_COLLISION)
658 /* Macros to get and set shape pointer values and collision flags. */
659 #define SHAPE_IS_FREE(shape) ((shape) == NULL)
660 #define SHAPE_IS_REMOVED(shape) ((shape) == SHAPE_REMOVED)
661 #define SHAPE_IS_LIVE(shape) ((shape) > SHAPE_REMOVED)
662 #define SHAPE_FLAG_COLLISION(spp,shape) (*(spp) = (js::Shape *) \
663 (jsuword(shape) | SHAPE_COLLISION))
664 #define SHAPE_HAD_COLLISION(shape) (jsuword(shape) & SHAPE_COLLISION)
665 #define SHAPE_FETCH(spp) SHAPE_CLEAR_COLLISION(*(spp))
667 #define SHAPE_CLEAR_COLLISION(shape) \
668 ((js::Shape *) (jsuword(shape) & ~SHAPE_COLLISION))
670 #define SHAPE_STORE_PRESERVING_COLLISION(spp, shape) \
671 (*(spp) = (js::Shape *) (jsuword(shape) | SHAPE_HAD_COLLISION(*(spp))))
674 JSObject::nativeSearch(jsid id
, bool adding
)
676 return js::Shape::search(compartment()->rt
, &lastProp
, id
, adding
);
679 inline const js::Shape
*
680 JSObject::nativeLookup(jsid id
)
682 JS_ASSERT(isNative());
683 return SHAPE_FETCH(nativeSearch(id
));
687 JSObject::nativeContains(jsid id
)
689 return nativeLookup(id
) != NULL
;
693 JSObject::nativeContains(const js::Shape
&shape
)
695 return nativeLookup(shape
.id
) == &shape
;
698 inline const js::Shape
*
699 JSObject::lastProperty() const
701 JS_ASSERT(isNative());
702 JS_ASSERT(!JSID_IS_VOID(lastProp
->id
));
707 JSObject::nativeEmpty() const
709 return lastProperty()->isEmptyShape();
713 JSObject::inDictionaryMode() const
715 return lastProperty()->inDictionary();
719 JSObject::propertyCount() const
721 return lastProperty()->entryCount();
725 JSObject::hasPropertyTable() const
727 return !!lastProperty()->table
;
731 * FIXME: shape must not be null, should use a reference here and other places.
734 JSObject::setLastProperty(const js::Shape
*shape
)
736 JS_ASSERT(!inDictionaryMode());
737 JS_ASSERT(!JSID_IS_VOID(shape
->id
));
738 JS_ASSERT_IF(lastProp
, !JSID_IS_VOID(lastProp
->id
));
740 lastProp
= const_cast<js::Shape
*>(shape
);
744 JSObject::removeLastProperty()
746 JS_ASSERT(!inDictionaryMode());
747 JS_ASSERT(!JSID_IS_VOID(lastProp
->parent
->id
));
749 lastProp
= lastProp
->parent
;
755 Shape::removeFromDictionary(JSObject
*obj
) const
757 JS_ASSERT(!frozen());
758 JS_ASSERT(inDictionary());
759 JS_ASSERT(obj
->inDictionaryMode());
761 JS_ASSERT(!JSID_IS_VOID(id
));
763 JS_ASSERT(obj
->lastProp
->inDictionary());
764 JS_ASSERT(obj
->lastProp
->listp
== &obj
->lastProp
);
765 JS_ASSERT_IF(obj
->lastProp
!= this, !JSID_IS_VOID(obj
->lastProp
->id
));
766 JS_ASSERT_IF(obj
->lastProp
->parent
, !JSID_IS_VOID(obj
->lastProp
->parent
->id
));
769 parent
->listp
= listp
;
775 Shape::insertIntoDictionary(js::Shape
**dictp
)
778 * Don't assert inDictionaryMode() here because we may be called from
779 * JSObject::toDictionaryMode via JSObject::newDictionaryShape.
781 JS_ASSERT(inDictionary());
783 JS_ASSERT(!JSID_IS_VOID(id
));
785 JS_ASSERT_IF(*dictp
, !(*dictp
)->frozen());
786 JS_ASSERT_IF(*dictp
, (*dictp
)->inDictionary());
787 JS_ASSERT_IF(*dictp
, (*dictp
)->listp
== dictp
);
788 JS_ASSERT_IF(*dictp
, !JSID_IS_VOID((*dictp
)->id
));
792 parent
->listp
= &parent
;
800 * If SHORTID is set in shape->flags, we use shape->shortid rather
801 * than id when calling shape's getter or setter.
803 #define SHAPE_USERID(shape) \
804 ((shape)->hasShortID() ? INT_TO_JSID((shape)->shortid) \
807 #ifndef JS_THREADSAFE
808 # define js_GenerateShape(cx, gcLocked) js_GenerateShape (cx)
812 js_GenerateShape(JSContext
*cx
, bool gcLocked
);
815 struct JSScopeStats
{
821 jsrefcount hashMisses
;
824 jsrefcount stepMisses
;
825 jsrefcount initSearches
;
826 jsrefcount changeSearches
;
827 jsrefcount tableAllocFails
;
828 jsrefcount toDictFails
;
829 jsrefcount wrapWatchFails
;
833 jsrefcount redundantPuts
;
836 jsrefcount changePuts
;
837 jsrefcount changeFails
;
838 jsrefcount compresses
;
841 jsrefcount removeFrees
;
842 jsrefcount uselessRemoves
;
846 extern JS_FRIEND_DATA(JSScopeStats
) js_scope_stats
;
848 # define METER(x) JS_ATOMIC_INCREMENT(&js_scope_stats.x)
850 # define METER(x) /* nothing */
855 JS_ALWAYS_INLINE
js::Shape
**
856 Shape::search(JSRuntime
*rt
, js::Shape
**startp
, jsid id
, bool adding
)
858 js::Shape
*start
= *startp
;
861 (start
->numSearches
>= PropertyTable::HASH_MIN_SEARCHES
&& start
->hashify(rt
)))
863 return start
->table
->search(id
, adding
);
867 * Not enough searches done so far to justify hashing: search linearly
870 * We don't use a Range here, or stop at null parent (the empty shape
871 * at the end), to avoid an extra load per iteration just to save a
872 * load and id test at the end (when missing).
874 JS_ASSERT(!start
->table
);
875 start
->numSearches
++;
878 for (spp
= startp
; js::Shape
*shape
= *spp
; spp
= &shape
->parent
) {
879 if (shape
->id
== id
) {
891 Shape::isSharedPermanent() const
893 return (~attrs
& (JSPROP_SHARED
| JSPROP_PERMANENT
)) == 0;
903 #endif /* jsscope_h___ */