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