![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to jsscope.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Synchronet] / sbbs / javascript / include / mozilla / js|
Return to jsscope.h CVS log | Up to [Synchronet] / sbbs / javascript / include / mozilla / js |
1.1 root 1: /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2: *
3: * The contents of this file are subject to the Netscape Public
4: * License Version 1.1 (the "License"); you may not use this file
5: * except in compliance with the License. You may obtain a copy of
6: * the License at http://www.mozilla.org/NPL/
7: *
8: * Software distributed under the License is distributed on an "AS
9: * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
10: * implied. See the License for the specific language governing
11: * rights and limitations under the License.
12: *
13: * The Original Code is Mozilla Communicator client code, released
14: * March 31, 1998.
15: *
16: * The Initial Developer of the Original Code is Netscape
17: * Communications Corporation. Portions created by Netscape are
18: * Copyright (C) 1998 Netscape Communications Corporation. All
19: * Rights Reserved.
20: *
21: * Contributor(s):
22: *
23: * Alternatively, the contents of this file may be used under the
24: * terms of the GNU Public License (the "GPL"), in which case the
25: * provisions of the GPL are applicable instead of those above.
26: * If you wish to allow use of your version of this file only
27: * under the terms of the GPL and not to allow others to use your
28: * version of this file under the NPL, indicate your decision by
29: * deleting the provisions above and replace them with the notice
30: * and other provisions required by the GPL. If you do not delete
31: * the provisions above, a recipient may use your version of this
32: * file under either the NPL or the GPL.
33: */
34:
35: #ifndef jsscope_h___
36: #define jsscope_h___
37: /*
38: * JS symbol tables.
39: */
40: #include "jstypes.h"
41: #include "jsobj.h"
42: #include "jsprvtd.h"
43: #include "jspubtd.h"
44:
45: #ifdef JS_THREADSAFE
46: # include "jslock.h"
47: #endif
48:
49: /*
50: * Given P independent, non-unique properties each of size S words mapped by
51: * all scopes in a runtime, construct a property tree of N nodes each of size
52: * S+L words (L for tree linkage). A nominal L value is 2 for leftmost-child
53: * and right-sibling links. We hope that the N < P by enough that the space
54: * overhead of L, and the overhead of scope entries pointing at property tree
55: * nodes, is worth it.
56: *
57: * The tree construction goes as follows. If any empty scope in the runtime
58: * has a property X added to it, find or create a node under the tree root
59: * labeled X, and set scope->lastProp to point at that node. If any non-empty
60: * scope whose most recently added property is labeled Y has another property
61: * labeled Z added, find or create a node for Z under the node that was added
62: * for Y, and set scope->lastProp to point at that node.
63: *
64: * A property is labeled by its members' values: id, getter, setter, slot,
65: * attributes, tiny or short id, and a field telling for..in order. Note that
66: * labels are not unique in the tree, but they are unique among a node's kids
67: * (barring rare and benign multi-threaded race condition outcomes, see below)
68: * and along any ancestor line from the tree root to a given leaf node (except
69: * for the hard case of duplicate formal parameters to a function).
70: *
71: * Thus the root of the tree represents all empty scopes, and the first ply
72: * of the tree represents all scopes containing one property, etc. Each node
73: * in the tree can stand for any number of scopes having the same ordered set
74: * of properties, where that node was the last added to the scope. (We need
75: * not store the root of the tree as a node, and do not -- all we need are
76: * links to its kids.)
77: *
78: * Sidebar on for..in loop order: ECMA requires no particular order, but this
79: * implementation has promised and delivered property definition order, and
80: * compatibility is king. We could use an order number per property, which
81: * would require a sort in js_Enumerate, and an entry order generation number
82: * per scope. An order number beats a list, which should be doubly-linked for
83: * O(1) delete. An even better scheme is to use a parent link in the property
84: * tree, so that the ancestor line can be iterated from scope->lastProp when
85: * filling in a JSIdArray from back to front. This parent link also helps the
86: * GC to sweep properties iteratively.
87: *
88: * What if a property Y is deleted from a scope? If Y is the last property in
89: * the scope, we simply adjust the scope's lastProp member after we remove the
90: * scope's hash-table entry pointing at that property node. The parent link
91: * mentioned in the for..in sidebar above makes this adjustment O(1). But if
92: * Y comes between X and Z in the scope, then we might have to "fork" the tree
93: * at X, leaving X->Y->Z in case other scopes have those properties added in
94: * that order; and to finish the fork, we'd add a node labeled Z with the path
95: * X->Z, if it doesn't exist. This could lead to lots of extra nodes, and to
96: * O(n^2) growth when deleting lots of properties.
97: *
98: * Rather, for O(1) growth all around, we should share the path X->Y->Z among
99: * scopes having those three properties added in that order, and among scopes
100: * having only X->Z where Y was deleted. All such scopes have a lastProp that
101: * points to the Z child of Y. But a scope in which Y was deleted does not
102: * have a table entry for Y, and when iterating that scope by traversing the
103: * ancestor line from Z, we will have to test for a table entry for each node,
104: * skipping nodes that lack entries.
105: *
106: * What if we add Y again? X->Y->Z->Y is wrong and we'll enumerate Y twice.
107: * Therefore we must fork in such a case, if not earlier. Because delete is
108: * "bursty", we should not fork eagerly. Delaying a fork till we are at risk
109: * of adding Y after it was deleted already requires a flag in the JSScope, to
110: * wit, SCOPE_MIDDLE_DELETE.
111: *
112: * What about thread safety? If the property tree operations done by requests
113: * are find-node and insert-node, then the only hazard is duplicate insertion.
114: * This is harmless except for minor bloat. When all requests have ended or
115: * been suspended, the GC is free to sweep the tree after marking all nodes
116: * reachable from scopes, performing remove-node operations as needed. Note
117: * also that the stable storage of the property nodes during active requests
118: * permits the property cache (see jsinterp.h) to dereference JSScopeProperty
119: * weak references safely.
120: *
121: * Is the property tree worth it compared to property storage in each table's
122: * entries? To decide, we must find the relation <> between the words used
123: * with a property tree and the words required without a tree.
124: *
125: * Model all scopes as one super-scope of capacity T entries (T a power of 2).
126: * Let alpha be the load factor of this double hash-table. With the property
127: * tree, each entry in the table is a word-sized pointer to a node that can be
128: * shared by many scopes. But all such pointers are overhead compared to the
129: * situation without the property tree, where the table stores property nodes
130: * directly, as entries each of size S words. With the property tree, we need
131: * L=2 extra words per node for siblings and kids pointers. Without the tree,
132: * (1-alpha)*S*T words are wasted on free or removed sentinel-entries required
133: * by double hashing.
134: *
135: * Therefore,
136: *
137: * (property tree) <> (no property tree)
138: * N*(S+L) + T <> S*T
139: * N*(S+L) + T <> P*S + (1-alpha)*S*T
140: * N*(S+L) + alpha*T + (1-alpha)*T <> P*S + (1-alpha)*S*T
141: *
142: * Note that P is alpha*T by definition, so
143: *
144: * N*(S+L) + P + (1-alpha)*T <> P*S + (1-alpha)*S*T
145: * N*(S+L) <> P*S - P + (1-alpha)*S*T - (1-alpha)*T
146: * N*(S+L) <> (P + (1-alpha)*T) * (S-1)
147: * N*(S+L) <> (P + (1-alpha)*P/alpha) * (S-1)
148: * N*(S+L) <> P * (1/alpha) * (S-1)
149: *
150: * Let N = P*beta for a compression ratio beta, beta <= 1:
151: *
152: * P*beta*(S+L) <> P * (1/alpha) * (S-1)
153: * beta*(S+L) <> (S-1)/alpha
154: * beta <> (S-1)/((S+L)*alpha)
155: *
156: * For S = 6 (32-bit architectures) and L = 2, the property tree wins iff
157: *
158: * beta < 5/(8*alpha)
159: *
160: * We ensure that alpha <= .75, so the property tree wins if beta < .83_. An
161: * average beta from recent Mozilla browser startups was around .6.
162: *
163: * Can we reduce L? Observe that the property tree degenerates into a list of
164: * lists if at most one property Y follows X in all scopes. In or near such a
165: * case, we waste a word on the right-sibling link outside of the root ply of
166: * the tree. Note also that the root ply tends to be large, so O(n^2) growth
167: * searching it is likely, indicating the need for hashing (but with increased
168: * thread safety costs).
169: *
170: * If only K out of N nodes in the property tree have more than one child, we
171: * could eliminate the sibling link and overlay a children list or hash-table
172: * pointer on the leftmost-child link (which would then be either null or an
173: * only-child link; the overlay could be tagged in the low bit of the pointer,
174: * or flagged elsewhere in the property tree node, although such a flag must
175: * not be considered when comparing node labels during tree search).
176: *
177: * For such a system, L = 1 + (K * averageChildrenTableSize) / N instead of 2.
178: * If K << N, L approaches 1 and the property tree wins if beta < .95.
179: *
180: * We observe that fan-out below the root ply of the property tree appears to
181: * have extremely low degree (see the MeterPropertyTree code that histograms
182: * child-counts in jsscope.c), so instead of a hash-table we use a linked list
183: * of child node pointer arrays ("kid chunks"). The details are isolated in
184: * jsscope.c; others must treat JSScopeProperty.kids as opaque. We leave it
185: * strongly typed for debug-ability of the common (null or one-kid) cases.
186: *
187: * One final twist (can you stand it?): the mean number of entries per scope
188: * in Mozilla is < 5, with a large standard deviation (~8). Instead of always
189: * allocating scope->table, we leave it null while initializing all the other
190: * scope members as if it were non-null and minimal-length. Until a property
191: * is added that crosses the threshold of 6 or more entries for hashing, or
192: * until a "middle delete" occurs, we use linear search from scope->lastProp
193: * to find a given id, and save on the space overhead of a hash table.
194: */
195:
196: struct JSScope {
197: JSObjectMap map; /* base class state */
198: JSObject *object; /* object that owns this scope */
199: uint16 flags; /* flags, see below */
200: int16 hashShift; /* multiplicative hash shift */
201: uint32 entryCount; /* number of entries in table */
202: uint32 removedCount; /* removed entry sentinels in table */
203: JSScopeProperty **table; /* table of ptrs to shared tree nodes */
204: JSScopeProperty *lastProp; /* pointer to last property added */
205: #ifdef JS_THREADSAFE
206: JSContext *ownercx; /* creating context, NULL if shared */
207: JSThinLock lock; /* binary semaphore protecting scope */
208: union { /* union lockful and lock-free state: */
209: jsrefcount count; /* lock entry count for reentrancy */
210: JSScope *link; /* next link in rt->scopeSharingTodo */
211: } u;
212: #ifdef DEBUG
213: const char *file[4]; /* file where lock was (re-)taken */
214: unsigned int line[4]; /* line where lock was (re-)taken */
215: #endif
216: #endif
217: };
218:
219: #define OBJ_SCOPE(obj) ((JSScope *)(obj)->map)
220:
221: /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */
222: #define SCOPE_CAPACITY(scope) JS_BIT(JS_DHASH_BITS-(scope)->hashShift)
223:
224: /* Scope flags and some macros to hide them from other files than jsscope.c. */
225: #define SCOPE_MIDDLE_DELETE 0x0001
226: #define SCOPE_SEALED 0x0002
227:
228: #define SCOPE_HAD_MIDDLE_DELETE(scope) ((scope)->flags & SCOPE_MIDDLE_DELETE)
229: #define SCOPE_SET_MIDDLE_DELETE(scope) ((scope)->flags |= SCOPE_MIDDLE_DELETE)
230: #define SCOPE_CLR_MIDDLE_DELETE(scope) ((scope)->flags &= ~SCOPE_MIDDLE_DELETE)
231:
232: #define SCOPE_IS_SEALED(scope) ((scope)->flags & SCOPE_SEALED)
233: #define SCOPE_SET_SEALED(scope) ((scope)->flags |= SCOPE_SEALED)
234: #define SCOPE_CLR_SEALED(scope) ((scope)->flags &= ~SCOPE_SEALED)
235:
236: /*
237: * A little information hiding for scope->lastProp, in case it ever becomes
238: * a tagged pointer again.
239: */
240: #define SCOPE_LAST_PROP(scope) ((scope)->lastProp)
241: #define SCOPE_REMOVE_LAST_PROP(scope) ((scope)->lastProp = \
242: (scope)->lastProp->parent)
243:
244: struct JSScopeProperty {
245: jsid id; /* int-tagged jsval/untagged JSAtom* */
246: JSPropertyOp getter; /* getter and setter hooks or objects */
247: JSPropertyOp setter;
248: uint32 slot; /* index in obj->slots vector */
249: uint8 attrs; /* attributes, see jsapi.h JSPROP_* */
250: uint8 flags; /* flags, see below for defines */
251: int16 shortid; /* tinyid, or local arg/var index */
252: JSScopeProperty *parent; /* parent node, reverse for..in order */
253: JSScopeProperty *kids; /* null, single child, or a tagged ptr
254: to many-kids data structure */
255: };
256:
257: /* JSScopeProperty pointer tag bit indicating a collision. */
258: #define SPROP_COLLISION ((jsuword)1)
259: #define SPROP_REMOVED ((JSScopeProperty *) SPROP_COLLISION)
260:
261: /* Macros to get and set sprop pointer values and collision flags. */
262: #define SPROP_IS_FREE(sprop) ((sprop) == NULL)
263: #define SPROP_IS_REMOVED(sprop) ((sprop) == SPROP_REMOVED)
264: #define SPROP_IS_LIVE(sprop) ((sprop) > SPROP_REMOVED)
265: #define SPROP_FLAG_COLLISION(spp,sprop) (*(spp) = (JSScopeProperty *) \
266: ((jsuword)(sprop) | SPROP_COLLISION))
267: #define SPROP_HAD_COLLISION(sprop) ((jsuword)(sprop) & SPROP_COLLISION)
268: #define SPROP_FETCH(spp) SPROP_CLEAR_COLLISION(*(spp))
269:
270: #define SPROP_CLEAR_COLLISION(sprop) \
271: ((JSScopeProperty *) ((jsuword)(sprop) & ~SPROP_COLLISION))
272:
273: #define SPROP_STORE_PRESERVING_COLLISION(spp, sprop) \
274: (*(spp) = (JSScopeProperty *) ((jsuword)(sprop) \
275: | SPROP_HAD_COLLISION(*(spp))))
276:
277: /* Bits stored in sprop->flags. */
278: #define SPROP_MARK 0x01
279: #define SPROP_IS_DUPLICATE 0x02
280: #define SPROP_IS_ALIAS 0x04
281: #define SPROP_HAS_SHORTID 0x08
282:
283: /*
284: * If SPROP_HAS_SHORTID is set in sprop->flags, we use sprop->shortid rather
285: * than id when calling sprop's getter or setter.
286: */
287: #define SPROP_USERID(sprop) \
288: (((sprop)->flags & SPROP_HAS_SHORTID) ? INT_TO_JSVAL((sprop)->shortid) \
289: : ID_TO_VALUE((sprop)->id))
290:
291: #define SPROP_INVALID_SLOT 0xffffffff
292:
293: #define SPROP_HAS_VALID_SLOT(sprop, scope) \
294: ((sprop)->slot < (scope)->map.freeslot)
295:
296: #define SPROP_CALL_GETTER(cx,sprop,getter,obj,obj2,vp) \
297: (!(getter) || \
298: (getter)(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
299: #define SPROP_CALL_SETTER(cx,sprop,setter,obj,obj2,vp) \
300: (!(setter) || \
301: (setter)(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
302:
303: #define SPROP_GET(cx,sprop,obj,obj2,vp) \
304: (((sprop)->attrs & JSPROP_GETTER) \
305: ? js_InternalGetOrSet(cx, obj, (sprop)->id, \
306: OBJECT_TO_JSVAL((sprop)->getter), JSACC_READ, \
307: 0, 0, vp) \
308: : SPROP_CALL_GETTER(cx, sprop, (sprop)->getter, obj, obj2, vp))
309:
310: #define SPROP_SET(cx,sprop,obj,obj2,vp) \
311: (((sprop)->attrs & JSPROP_SETTER) \
312: ? js_InternalGetOrSet(cx, obj, (sprop)->id, \
313: OBJECT_TO_JSVAL((sprop)->setter), JSACC_WRITE, \
314: 1, vp, vp) \
315: : ((sprop)->attrs & JSPROP_GETTER) \
316: ? (JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, \
317: JSMSG_GETTER_ONLY, NULL), JS_FALSE) \
318: : SPROP_CALL_SETTER(cx, sprop, (sprop)->setter, obj, obj2, vp))
319:
320: /* Macro for common expression to test for shared permanent attributes. */
321: #define SPROP_IS_SHARED_PERMANENT(sprop) \
322: ((~(sprop)->attrs & (JSPROP_SHARED | JSPROP_PERMANENT)) == 0)
323:
324: extern JSScope *
325: js_GetMutableScope(JSContext *cx, JSObject *obj);
326:
327: extern JSScope *
328: js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
329: JSObject *obj);
330:
331: extern void
332: js_DestroyScope(JSContext *cx, JSScope *scope);
333:
334: #define ID_TO_VALUE(id) (((id) & JSVAL_INT) ? id : ATOM_KEY((JSAtom *)(id)))
335: #define HASH_ID(id) (((id) & JSVAL_INT) \
336: ? (jsatomid) JSVAL_TO_INT(id) \
337: : ((JSAtom *)id)->number)
338:
339: extern JS_FRIEND_API(JSScopeProperty **)
340: js_SearchScope(JSScope *scope, jsid id, JSBool adding);
341:
342: #define SCOPE_GET_PROPERTY(scope, id) \
343: SPROP_FETCH(js_SearchScope(scope, id, JS_FALSE))
344:
345: #define SCOPE_HAS_PROPERTY(scope, sprop) \
346: (SCOPE_GET_PROPERTY(scope, (sprop)->id) == (sprop))
347:
348: extern JSScopeProperty *
349: js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
350: JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
351: uintN attrs, uintN flags, intN shortid);
352:
353: extern JSScopeProperty *
354: js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
355: JSScopeProperty *sprop, uintN attrs, uintN mask,
356: JSPropertyOp getter, JSPropertyOp setter);
357:
358: extern JSBool
359: js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id);
360:
361: extern void
362: js_ClearScope(JSContext *cx, JSScope *scope);
363:
364: #define MARK_SCOPE_PROPERTY(sprop) ((sprop)->flags |= SPROP_MARK)
365:
366: extern void
367: js_SweepScopeProperties(JSRuntime *rt);
368:
369: extern JSBool
370: js_InitPropertyTree(JSRuntime *rt);
371:
372: extern void
373: js_FinishPropertyTree(JSRuntime *rt);
374:
375: #endif /* jsscope_h___ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.