/[jscoverage]/trunk/js/jsscope.h
ViewVC logotype

Annotation of /trunk/js/jsscope.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 332 - (hide annotations)
Thu Oct 23 19:03:33 2008 UTC (12 years ago) by siliconforks
File MIME type: text/plain
File size: 20380 byte(s)
Add SpiderMonkey from Firefox 3.1b1.

The following directories and files were removed:
correct/, correct.js
liveconnect/
nanojit/
t/
v8/
vprof/
xpconnect/
all JavaScript files (Y.js, call.js, if.js, math-partial-sums.js, md5.js, perfect.js, trace-test.js, trace.js)


1 siliconforks 332 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2     * vim: set ts=8 sw=4 et tw=78:
3     *
4     * ***** BEGIN LICENSE BLOCK *****
5     * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6     *
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/
11     *
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
15     * License.
16     *
17     * The Original Code is Mozilla Communicator client code, released
18     * March 31, 1998.
19     *
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.
24     *
25     * Contributor(s):
26     *
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.
38     *
39     * ***** END LICENSE BLOCK ***** */
40    
41     #ifndef jsscope_h___
42     #define jsscope_h___
43     /*
44     * JS symbol tables.
45     */
46     #include "jstypes.h"
47     #include "jslock.h"
48     #include "jsobj.h"
49     #include "jsprvtd.h"
50     #include "jspubtd.h"
51    
52     JS_BEGIN_EXTERN_C
53    
54     /*
55     * Given P independent, non-unique properties each of size S words mapped by
56     * all scopes in a runtime, construct a property tree of N nodes each of size
57     * S+L words (L for tree linkage). A nominal L value is 2 for leftmost-child
58     * and right-sibling links. We hope that the N < P by enough that the space
59     * overhead of L, and the overhead of scope entries pointing at property tree
60     * nodes, is worth it.
61     *
62     * The tree construction goes as follows. If any empty scope in the runtime
63     * has a property X added to it, find or create a node under the tree root
64     * labeled X, and set scope->lastProp to point at that node. If any non-empty
65     * scope whose most recently added property is labeled Y has another property
66     * labeled Z added, find or create a node for Z under the node that was added
67     * for Y, and set scope->lastProp to point at that node.
68     *
69     * A property is labeled by its members' values: id, getter, setter, slot,
70     * attributes, tiny or short id, and a field telling for..in order. Note that
71     * labels are not unique in the tree, but they are unique among a node's kids
72     * (barring rare and benign multi-threaded race condition outcomes, see below)
73     * and along any ancestor line from the tree root to a given leaf node (except
74     * for the hard case of duplicate formal parameters to a function).
75     *
76     * Thus the root of the tree represents all empty scopes, and the first ply
77     * of the tree represents all scopes containing one property, etc. Each node
78     * in the tree can stand for any number of scopes having the same ordered set
79     * of properties, where that node was the last added to the scope. (We need
80     * not store the root of the tree as a node, and do not -- all we need are
81     * links to its kids.)
82     *
83     * Sidebar on for..in loop order: ECMA requires no particular order, but this
84     * implementation has promised and delivered property definition order, and
85     * compatibility is king. We could use an order number per property, which
86     * would require a sort in js_Enumerate, and an entry order generation number
87     * per scope. An order number beats a list, which should be doubly-linked for
88     * O(1) delete. An even better scheme is to use a parent link in the property
89     * tree, so that the ancestor line can be iterated from scope->lastProp when
90     * filling in a JSIdArray from back to front. This parent link also helps the
91     * GC to sweep properties iteratively.
92     *
93     * What if a property Y is deleted from a scope? If Y is the last property in
94     * the scope, we simply adjust the scope's lastProp member after we remove the
95     * scope's hash-table entry pointing at that property node. The parent link
96     * mentioned in the for..in sidebar above makes this adjustment O(1). But if
97     * Y comes between X and Z in the scope, then we might have to "fork" the tree
98     * at X, leaving X->Y->Z in case other scopes have those properties added in
99     * that order; and to finish the fork, we'd add a node labeled Z with the path
100     * X->Z, if it doesn't exist. This could lead to lots of extra nodes, and to
101     * O(n^2) growth when deleting lots of properties.
102     *
103     * Rather, for O(1) growth all around, we should share the path X->Y->Z among
104     * scopes having those three properties added in that order, and among scopes
105     * having only X->Z where Y was deleted. All such scopes have a lastProp that
106     * points to the Z child of Y. But a scope in which Y was deleted does not
107     * have a table entry for Y, and when iterating that scope by traversing the
108     * ancestor line from Z, we will have to test for a table entry for each node,
109     * skipping nodes that lack entries.
110     *
111     * What if we add Y again? X->Y->Z->Y is wrong and we'll enumerate Y twice.
112     * Therefore we must fork in such a case, if not earlier. Because delete is
113     * "bursty", we should not fork eagerly. Delaying a fork till we are at risk
114     * of adding Y after it was deleted already requires a flag in the JSScope, to
115     * wit, SCOPE_MIDDLE_DELETE.
116     *
117     * What about thread safety? If the property tree operations done by requests
118     * are find-node and insert-node, then the only hazard is duplicate insertion.
119     * This is harmless except for minor bloat. When all requests have ended or
120     * been suspended, the GC is free to sweep the tree after marking all nodes
121     * reachable from scopes, performing remove-node operations as needed.
122     *
123     * Is the property tree worth it compared to property storage in each table's
124     * entries? To decide, we must find the relation <> between the words used
125     * with a property tree and the words required without a tree.
126     *
127     * Model all scopes as one super-scope of capacity T entries (T a power of 2).
128     * Let alpha be the load factor of this double hash-table. With the property
129     * tree, each entry in the table is a word-sized pointer to a node that can be
130     * shared by many scopes. But all such pointers are overhead compared to the
131     * situation without the property tree, where the table stores property nodes
132     * directly, as entries each of size S words. With the property tree, we need
133     * L=2 extra words per node for siblings and kids pointers. Without the tree,
134     * (1-alpha)*S*T words are wasted on free or removed sentinel-entries required
135     * by double hashing.
136     *
137     * Therefore,
138     *
139     * (property tree) <> (no property tree)
140     * N*(S+L) + T <> S*T
141     * N*(S+L) + T <> P*S + (1-alpha)*S*T
142     * N*(S+L) + alpha*T + (1-alpha)*T <> P*S + (1-alpha)*S*T
143     *
144     * Note that P is alpha*T by definition, so
145     *
146     * N*(S+L) + P + (1-alpha)*T <> P*S + (1-alpha)*S*T
147     * N*(S+L) <> P*S - P + (1-alpha)*S*T - (1-alpha)*T
148     * N*(S+L) <> (P + (1-alpha)*T) * (S-1)
149     * N*(S+L) <> (P + (1-alpha)*P/alpha) * (S-1)
150     * N*(S+L) <> P * (1/alpha) * (S-1)
151     *
152     * Let N = P*beta for a compression ratio beta, beta <= 1:
153     *
154     * P*beta*(S+L) <> P * (1/alpha) * (S-1)
155     * beta*(S+L) <> (S-1)/alpha
156     * beta <> (S-1)/((S+L)*alpha)
157     *
158     * For S = 6 (32-bit architectures) and L = 2, the property tree wins iff
159     *
160     * beta < 5/(8*alpha)
161     *
162     * We ensure that alpha <= .75, so the property tree wins if beta < .83_. An
163     * average beta from recent Mozilla browser startups was around .6.
164     *
165     * Can we reduce L? Observe that the property tree degenerates into a list of
166     * lists if at most one property Y follows X in all scopes. In or near such a
167     * case, we waste a word on the right-sibling link outside of the root ply of
168     * the tree. Note also that the root ply tends to be large, so O(n^2) growth
169     * searching it is likely, indicating the need for hashing (but with increased
170     * thread safety costs).
171     *
172     * If only K out of N nodes in the property tree have more than one child, we
173     * could eliminate the sibling link and overlay a children list or hash-table
174     * pointer on the leftmost-child link (which would then be either null or an
175     * only-child link; the overlay could be tagged in the low bit of the pointer,
176     * or flagged elsewhere in the property tree node, although such a flag must
177     * not be considered when comparing node labels during tree search).
178     *
179     * For such a system, L = 1 + (K * averageChildrenTableSize) / N instead of 2.
180     * If K << N, L approaches 1 and the property tree wins if beta < .95.
181     *
182     * We observe that fan-out below the root ply of the property tree appears to
183     * have extremely low degree (see the MeterPropertyTree code that histograms
184     * child-counts in jsscope.c), so instead of a hash-table we use a linked list
185     * of child node pointer arrays ("kid chunks"). The details are isolated in
186     * jsscope.c; others must treat JSScopeProperty.kids as opaque. We leave it
187     * strongly typed for debug-ability of the common (null or one-kid) cases.
188     *
189     * One final twist (can you stand it?): the mean number of entries per scope
190     * in Mozilla is < 5, with a large standard deviation (~8). Instead of always
191     * allocating scope->table, we leave it null while initializing all the other
192     * scope members as if it were non-null and minimal-length. Until a property
193     * is added that crosses the threshold of 6 or more entries for hashing, or
194     * until a "middle delete" occurs, we use linear search from scope->lastProp
195     * to find a given id, and save on the space overhead of a hash table.
196     */
197    
198     struct JSScope {
199     JSObjectMap map; /* base class state */
200     #ifdef JS_THREADSAFE
201     JSTitle title; /* lock state */
202     #endif
203     JSObject *object; /* object that owns this scope */
204     uint32 shape; /* property cache shape identifier */
205     uint8 flags; /* flags, see below */
206     int8 hashShift; /* multiplicative hash shift */
207     uint16 spare; /* reserved */
208     uint32 entryCount; /* number of entries in table */
209     uint32 removedCount; /* removed entry sentinels in table */
210     JSScopeProperty **table; /* table of ptrs to shared tree nodes */
211     JSScopeProperty *lastProp; /* pointer to last property added */
212     };
213    
214     #ifdef JS_THREADSAFE
215     JS_STATIC_ASSERT(offsetof(JSScope, title) == sizeof(JSObjectMap));
216     #endif
217    
218     #define JS_IS_SCOPE_LOCKED(cx, scope) JS_IS_TITLE_LOCKED(cx, &(scope)->title)
219    
220     #define OBJ_SCOPE(obj) ((JSScope *)(obj)->map)
221     #define OBJ_SHAPE(obj) (OBJ_SCOPE(obj)->shape)
222    
223     #define SCOPE_MAKE_UNIQUE_SHAPE(cx,scope) \
224     ((scope)->shape = js_GenerateShape((cx), JS_FALSE))
225    
226     #define SCOPE_EXTEND_SHAPE(cx,scope,sprop) \
227     JS_BEGIN_MACRO \
228     if (!(scope)->lastProp || \
229     (scope)->shape == (scope)->lastProp->shape) { \
230     (scope)->shape = (sprop)->shape; \
231     } else { \
232     (scope)->shape = js_GenerateShape((cx), JS_FALSE); \
233     } \
234     JS_END_MACRO
235    
236     /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */
237     #define SCOPE_CAPACITY(scope) JS_BIT(JS_DHASH_BITS-(scope)->hashShift)
238    
239     /* Scope flags and some macros to hide them from other files than jsscope.c. */
240     #define SCOPE_MIDDLE_DELETE 0x0001
241     #define SCOPE_SEALED 0x0002
242     #define SCOPE_BRANDED 0x0004
243    
244     #define SCOPE_HAD_MIDDLE_DELETE(scope) ((scope)->flags & SCOPE_MIDDLE_DELETE)
245     #define SCOPE_SET_MIDDLE_DELETE(scope) ((scope)->flags |= SCOPE_MIDDLE_DELETE)
246     #define SCOPE_CLR_MIDDLE_DELETE(scope) ((scope)->flags &= ~SCOPE_MIDDLE_DELETE)
247    
248     #define SCOPE_IS_SEALED(scope) ((scope)->flags & SCOPE_SEALED)
249     #define SCOPE_SET_SEALED(scope) ((scope)->flags |= SCOPE_SEALED)
250     #if 0
251     /*
252     * Don't define this, it can't be done safely because JS_LOCK_OBJ will avoid
253     * taking the lock if the object owns its scope and the scope is sealed.
254     */
255     #undef SCOPE_CLR_SEALED(scope) ((scope)->flags &= ~SCOPE_SEALED)
256     #endif
257    
258     /*
259     * A branded scope's object contains plain old methods (function-valued
260     * properties without magic getters and setters), and its scope->shape
261     * evolves whenever a function value changes.
262     */
263     #define SCOPE_IS_BRANDED(scope) ((scope)->flags & SCOPE_BRANDED)
264     #define SCOPE_SET_BRANDED(scope) ((scope)->flags |= SCOPE_BRANDED)
265     #define SCOPE_CLR_BRANDED(scope) ((scope)->flags &= ~SCOPE_BRANDED)
266    
267     /*
268     * A little information hiding for scope->lastProp, in case it ever becomes
269     * a tagged pointer again.
270     */
271     #define SCOPE_LAST_PROP(scope) ((scope)->lastProp)
272     #define SCOPE_REMOVE_LAST_PROP(scope) ((scope)->lastProp = \
273     (scope)->lastProp->parent)
274    
275     struct JSScopeProperty {
276     jsid id; /* int-tagged jsval/untagged JSAtom* */
277     JSPropertyOp getter; /* getter and setter hooks or objects */
278     JSPropertyOp setter;
279     uint32 slot; /* abstract index in object slots */
280     uint8 attrs; /* attributes, see jsapi.h JSPROP_* */
281     uint8 flags; /* flags, see below for defines */
282     int16 shortid; /* tinyid, or local arg/var index */
283     JSScopeProperty *parent; /* parent node, reverse for..in order */
284     JSScopeProperty *kids; /* null, single child, or a tagged ptr
285     to many-kids data structure */
286     uint32 shape; /* property cache shape identifier */
287     };
288    
289     /* JSScopeProperty pointer tag bit indicating a collision. */
290     #define SPROP_COLLISION ((jsuword)1)
291     #define SPROP_REMOVED ((JSScopeProperty *) SPROP_COLLISION)
292    
293     /* Macros to get and set sprop pointer values and collision flags. */
294     #define SPROP_IS_FREE(sprop) ((sprop) == NULL)
295     #define SPROP_IS_REMOVED(sprop) ((sprop) == SPROP_REMOVED)
296     #define SPROP_IS_LIVE(sprop) ((sprop) > SPROP_REMOVED)
297     #define SPROP_FLAG_COLLISION(spp,sprop) (*(spp) = (JSScopeProperty *) \
298     ((jsuword)(sprop) | SPROP_COLLISION))
299     #define SPROP_HAD_COLLISION(sprop) ((jsuword)(sprop) & SPROP_COLLISION)
300     #define SPROP_FETCH(spp) SPROP_CLEAR_COLLISION(*(spp))
301    
302     #define SPROP_CLEAR_COLLISION(sprop) \
303     ((JSScopeProperty *) ((jsuword)(sprop) & ~SPROP_COLLISION))
304    
305     #define SPROP_STORE_PRESERVING_COLLISION(spp, sprop) \
306     (*(spp) = (JSScopeProperty *) ((jsuword)(sprop) \
307     | SPROP_HAD_COLLISION(*(spp))))
308    
309     /* Bits stored in sprop->flags. */
310     #define SPROP_MARK 0x01
311     #define SPROP_IS_ALIAS 0x02
312     #define SPROP_HAS_SHORTID 0x04
313     #define SPROP_FLAG_SHAPE_REGEN 0x08
314    
315     /*
316     * If SPROP_HAS_SHORTID is set in sprop->flags, we use sprop->shortid rather
317     * than id when calling sprop's getter or setter.
318     */
319     #define SPROP_USERID(sprop) \
320     (((sprop)->flags & SPROP_HAS_SHORTID) ? INT_TO_JSVAL((sprop)->shortid) \
321     : ID_TO_VALUE((sprop)->id))
322    
323     #define SPROP_INVALID_SLOT 0xffffffff
324    
325     #define SLOT_IN_SCOPE(slot,scope) ((slot) < (scope)->map.freeslot)
326     #define SPROP_HAS_VALID_SLOT(sprop,scope) SLOT_IN_SCOPE((sprop)->slot, scope)
327    
328     #define SPROP_HAS_STUB_GETTER(sprop) (!(sprop)->getter)
329     #define SPROP_HAS_STUB_SETTER(sprop) (!(sprop)->setter)
330    
331     /*
332     * NB: SPROP_GET must not be called if SPROP_HAS_STUB_GETTER(sprop).
333     */
334     #define SPROP_GET(cx,sprop,obj,obj2,vp) \
335     (((sprop)->attrs & JSPROP_GETTER) \
336     ? js_InternalGetOrSet(cx, obj, (sprop)->id, \
337     OBJECT_TO_JSVAL((sprop)->getter), JSACC_READ, \
338     0, 0, vp) \
339     : (sprop)->getter(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
340    
341     /*
342     * NB: SPROP_SET must not be called if (SPROP_HAS_STUB_SETTER(sprop) &&
343     * !(sprop->attrs & JSPROP_GETTER)).
344     */
345     #define SPROP_SET(cx,sprop,obj,obj2,vp) \
346     (((sprop)->attrs & JSPROP_SETTER) \
347     ? js_InternalGetOrSet(cx, obj, (sprop)->id, \
348     OBJECT_TO_JSVAL((sprop)->setter), JSACC_WRITE, \
349     1, vp, vp) \
350     : ((sprop)->attrs & JSPROP_GETTER) \
351     ? (JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, \
352     JSMSG_GETTER_ONLY, NULL), JS_FALSE) \
353     : (sprop)->setter(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
354    
355     /* Macro for common expression to test for shared permanent attributes. */
356     #define SPROP_IS_SHARED_PERMANENT(sprop) \
357     ((~(sprop)->attrs & (JSPROP_SHARED | JSPROP_PERMANENT)) == 0)
358    
359     extern JSScope *
360     js_GetMutableScope(JSContext *cx, JSObject *obj);
361    
362     extern JSScope *
363     js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
364     JSObject *obj);
365    
366     extern void
367     js_DestroyScope(JSContext *cx, JSScope *scope);
368    
369     extern JS_FRIEND_API(JSScopeProperty **)
370     js_SearchScope(JSScope *scope, jsid id, JSBool adding);
371    
372     #define SCOPE_GET_PROPERTY(scope, id) \
373     SPROP_FETCH(js_SearchScope(scope, id, JS_FALSE))
374    
375     #define SCOPE_HAS_PROPERTY(scope, sprop) \
376     (SCOPE_GET_PROPERTY(scope, (sprop)->id) == (sprop))
377    
378     extern JSScopeProperty *
379     js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
380     JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
381     uintN attrs, uintN flags, intN shortid);
382    
383     extern JSScopeProperty *
384     js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
385     JSScopeProperty *sprop, uintN attrs, uintN mask,
386     JSPropertyOp getter, JSPropertyOp setter);
387    
388     extern JSBool
389     js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id);
390    
391     extern void
392     js_ClearScope(JSContext *cx, JSScope *scope);
393    
394     /*
395     * These macros used to inline short code sequences, but they grew over time.
396     * We retain them for internal backward compatibility, and in case one or both
397     * ever shrink to inline-able size.
398     */
399     #define TRACE_ID(trc, id) js_TraceId(trc, id)
400     #define TRACE_SCOPE_PROPERTY(trc, sprop) js_TraceScopeProperty(trc, sprop)
401    
402     extern void
403     js_TraceId(JSTracer *trc, jsid id);
404    
405     extern void
406     js_TraceScopeProperty(JSTracer *trc, JSScopeProperty *sprop);
407    
408     extern void
409     js_SweepScopeProperties(JSContext *cx);
410    
411     extern JSBool
412     js_InitPropertyTree(JSRuntime *rt);
413    
414     extern void
415     js_FinishPropertyTree(JSRuntime *rt);
416    
417     JS_END_EXTERN_C
418    
419     #endif /* jsscope_h___ */

  ViewVC Help
Powered by ViewVC 1.1.24