Back to index

lightning-sunbird  0.9+nobinonly
jsscope.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  * vim: set ts=8 sw=4 et tw=78:
00003  *
00004  * ***** BEGIN LICENSE BLOCK *****
00005  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00006  *
00007  * The contents of this file are subject to the Mozilla Public License Version
00008  * 1.1 (the "License"); you may not use this file except in compliance with
00009  * the License. You may obtain a copy of the License at
00010  * http://www.mozilla.org/MPL/
00011  *
00012  * Software distributed under the License is distributed on an "AS IS" basis,
00013  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00014  * for the specific language governing rights and limitations under the
00015  * License.
00016  *
00017  * The Original Code is Mozilla Communicator client code, released
00018  * March 31, 1998.
00019  *
00020  * The Initial Developer of the Original Code is
00021  * Netscape Communications Corporation.
00022  * Portions created by the Initial Developer are Copyright (C) 1998
00023  * the Initial Developer. All Rights Reserved.
00024  *
00025  * Contributor(s):
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either of the GNU General Public License Version 2 or later (the "GPL"),
00029  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 /*
00042  * JS symbol tables.
00043  */
00044 #include "jsstddef.h"
00045 #include <stdlib.h>
00046 #include <string.h>
00047 #include "jstypes.h"
00048 #include "jsarena.h"
00049 #include "jsbit.h"
00050 #include "jsclist.h"
00051 #include "jsdhash.h"
00052 #include "jsutil.h" /* Added by JSIFY */
00053 #include "jsapi.h"
00054 #include "jsatom.h"
00055 #include "jscntxt.h"
00056 #include "jsdbgapi.h"
00057 #include "jslock.h"
00058 #include "jsnum.h"
00059 #include "jsscope.h"
00060 #include "jsstr.h"
00061 
00062 JSScope *
00063 js_GetMutableScope(JSContext *cx, JSObject *obj)
00064 {
00065     JSScope *scope, *newscope;
00066 
00067     scope = OBJ_SCOPE(obj);
00068     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
00069     if (scope->object == obj)
00070         return scope;
00071     newscope = js_NewScope(cx, 0, scope->map.ops, LOCKED_OBJ_GET_CLASS(obj),
00072                            obj);
00073     if (!newscope)
00074         return NULL;
00075     JS_LOCK_SCOPE(cx, newscope);
00076     obj->map = js_HoldObjectMap(cx, &newscope->map);
00077     scope = (JSScope *) js_DropObjectMap(cx, &scope->map, obj);
00078     JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope);
00079     return newscope;
00080 }
00081 
00082 /*
00083  * JSScope uses multiplicative hashing, _a la_ jsdhash.[ch], but specialized
00084  * to minimize footprint.  But if a scope has fewer than SCOPE_HASH_THRESHOLD
00085  * entries, we use linear search and avoid allocating scope->table.
00086  */
00087 #define SCOPE_HASH_THRESHOLD    6
00088 #define MIN_SCOPE_SIZE_LOG2     4
00089 #define MIN_SCOPE_SIZE          JS_BIT(MIN_SCOPE_SIZE_LOG2)
00090 #define SCOPE_TABLE_NBYTES(n)   ((n) * sizeof(JSScopeProperty *))
00091 
00092 static void
00093 InitMinimalScope(JSScope *scope)
00094 {
00095     scope->hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2;
00096     scope->entryCount = scope->removedCount = 0;
00097     scope->table = NULL;
00098     scope->lastProp = NULL;
00099 }
00100 
00101 static JSBool
00102 CreateScopeTable(JSContext *cx, JSScope *scope, JSBool report)
00103 {
00104     int sizeLog2;
00105     JSScopeProperty *sprop, **spp;
00106 
00107     JS_ASSERT(!scope->table);
00108     JS_ASSERT(scope->lastProp);
00109 
00110     if (scope->entryCount > SCOPE_HASH_THRESHOLD) {
00111         /*
00112          * Ouch: calloc failed at least once already -- let's try again,
00113          * overallocating to hold at least twice the current population.
00114          */
00115         sizeLog2 = JS_CeilingLog2(2 * scope->entryCount);
00116         scope->hashShift = JS_DHASH_BITS - sizeLog2;
00117     } else {
00118         JS_ASSERT(scope->hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2);
00119         sizeLog2 = MIN_SCOPE_SIZE_LOG2;
00120     }
00121 
00122     scope->table = (JSScopeProperty **)
00123         calloc(JS_BIT(sizeLog2), sizeof(JSScopeProperty *));
00124     if (!scope->table) {
00125         if (report)
00126             JS_ReportOutOfMemory(cx);
00127         return JS_FALSE;
00128     }
00129     js_UpdateMallocCounter(cx, JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
00130 
00131     scope->hashShift = JS_DHASH_BITS - sizeLog2;
00132     for (sprop = scope->lastProp; sprop; sprop = sprop->parent) {
00133         spp = js_SearchScope(scope, sprop->id, JS_TRUE);
00134         SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
00135     }
00136     return JS_TRUE;
00137 }
00138 
00139 JSScope *
00140 js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
00141             JSObject *obj)
00142 {
00143     JSScope *scope;
00144 
00145     scope = (JSScope *) JS_malloc(cx, sizeof(JSScope));
00146     if (!scope)
00147         return NULL;
00148 
00149     js_InitObjectMap(&scope->map, nrefs, ops, clasp);
00150     scope->object = obj;
00151     scope->flags = 0;
00152     InitMinimalScope(scope);
00153 
00154 #ifdef JS_THREADSAFE
00155     scope->ownercx = cx;
00156     memset(&scope->lock, 0, sizeof scope->lock);
00157 
00158     /*
00159      * Set u.link = NULL, not u.count = 0, in case the target architecture's
00160      * null pointer has a non-zero integer representation.
00161      */
00162     scope->u.link = NULL;
00163 
00164 #ifdef DEBUG
00165     scope->file[0] = scope->file[1] = scope->file[2] = scope->file[3] = NULL;
00166     scope->line[0] = scope->line[1] = scope->line[2] = scope->line[3] = 0;
00167 #endif
00168 #endif
00169 
00170     JS_RUNTIME_METER(cx->runtime, liveScopes);
00171     JS_RUNTIME_METER(cx->runtime, totalScopes);
00172     return scope;
00173 }
00174 
00175 #ifdef DEBUG_SCOPE_COUNT
00176 extern void
00177 js_unlog_scope(JSScope *scope);
00178 #endif
00179 
00180 void
00181 js_DestroyScope(JSContext *cx, JSScope *scope)
00182 {
00183 #ifdef DEBUG_SCOPE_COUNT
00184     js_unlog_scope(scope);
00185 #endif
00186 
00187 #ifdef JS_THREADSAFE
00188     /* Scope must be single-threaded at this point, so set scope->ownercx. */
00189     JS_ASSERT(scope->u.count == 0);
00190     scope->ownercx = cx;
00191     js_FinishLock(&scope->lock);
00192 #endif
00193     if (scope->table)
00194         JS_free(cx, scope->table);
00195 
00196 #ifdef DEBUG
00197     JS_LOCK_RUNTIME_VOID(cx->runtime,
00198                          cx->runtime->liveScopeProps -= scope->entryCount);
00199 #endif
00200     JS_RUNTIME_UNMETER(cx->runtime, liveScopes);
00201     JS_free(cx, scope);
00202 }
00203 
00204 #ifdef DUMP_SCOPE_STATS
00205 typedef struct JSScopeStats {
00206     jsrefcount          searches;
00207     jsrefcount          steps;
00208     jsrefcount          hits;
00209     jsrefcount          misses;
00210     jsrefcount          stepHits;
00211     jsrefcount          stepMisses;
00212     jsrefcount          adds;
00213     jsrefcount          redundantAdds;
00214     jsrefcount          addFailures;
00215     jsrefcount          changeFailures;
00216     jsrefcount          compresses;
00217     jsrefcount          grows;
00218     jsrefcount          removes;
00219     jsrefcount          removeFrees;
00220     jsrefcount          uselessRemoves;
00221     jsrefcount          shrinks;
00222 } JSScopeStats;
00223 
00224 JS_FRIEND_DATA(JSScopeStats) js_scope_stats;
00225 
00226 # define METER(x)       JS_ATOMIC_INCREMENT(&js_scope_stats.x)
00227 #else
00228 # define METER(x)       /* nothing */
00229 #endif
00230 
00231 /*
00232  * Double hashing needs the second hash code to be relatively prime to table
00233  * size, so we simply make hash2 odd.  The inputs to multiplicative hash are
00234  * the golden ratio, expressed as a fixed-point 32 bit fraction, and the int
00235  * property index or named property's atom number (observe that most objects
00236  * have either no indexed properties, or almost all indexed and a few names,
00237  * so collisions between index and atom number are unlikely).
00238  */
00239 #define SCOPE_HASH0(id)                 (HASH_ID(id) * JS_GOLDEN_RATIO)
00240 #define SCOPE_HASH1(hash0,shift)        ((hash0) >> (shift))
00241 #define SCOPE_HASH2(hash0,log2,shift)   ((((hash0) << (log2)) >> (shift)) | 1)
00242 
00243 JS_FRIEND_API(JSScopeProperty **)
00244 js_SearchScope(JSScope *scope, jsid id, JSBool adding)
00245 {
00246     JSHashNumber hash0, hash1, hash2;
00247     int hashShift, sizeLog2;
00248     JSScopeProperty *stored, *sprop, **spp, **firstRemoved;
00249     uint32 sizeMask;
00250 
00251     METER(searches);
00252     if (!scope->table) {
00253         /* Not enough properties to justify hashing: search from lastProp. */
00254         JS_ASSERT(!SCOPE_HAD_MIDDLE_DELETE(scope));
00255         for (spp = &scope->lastProp; (sprop = *spp); spp = &sprop->parent) {
00256             if (sprop->id == id) {
00257                 METER(hits);
00258                 return spp;
00259             }
00260         }
00261         METER(misses);
00262         return spp;
00263     }
00264 
00265     /* Compute the primary hash address. */
00266     hash0 = SCOPE_HASH0(id);
00267     hashShift = scope->hashShift;
00268     hash1 = SCOPE_HASH1(hash0, hashShift);
00269     spp = scope->table + hash1;
00270 
00271     /* Miss: return space for a new entry. */
00272     stored = *spp;
00273     if (SPROP_IS_FREE(stored)) {
00274         METER(misses);
00275         return spp;
00276     }
00277 
00278     /* Hit: return entry. */
00279     sprop = SPROP_CLEAR_COLLISION(stored);
00280     if (sprop && sprop->id == id) {
00281         METER(hits);
00282         return spp;
00283     }
00284 
00285     /* Collision: double hash. */
00286     sizeLog2 = JS_DHASH_BITS - hashShift;
00287     hash2 = SCOPE_HASH2(hash0, sizeLog2, hashShift);
00288     sizeMask = JS_BITMASK(sizeLog2);
00289 
00290     /* Save the first removed entry pointer so we can recycle it if adding. */
00291     if (SPROP_IS_REMOVED(stored)) {
00292         firstRemoved = spp;
00293     } else {
00294         firstRemoved = NULL;
00295         if (adding && !SPROP_HAD_COLLISION(stored))
00296             SPROP_FLAG_COLLISION(spp, sprop);
00297     }
00298 
00299     for (;;) {
00300         METER(steps);
00301         hash1 -= hash2;
00302         hash1 &= sizeMask;
00303         spp = scope->table + hash1;
00304 
00305         stored = *spp;
00306         if (SPROP_IS_FREE(stored)) {
00307             METER(stepMisses);
00308             return (adding && firstRemoved) ? firstRemoved : spp;
00309         }
00310 
00311         sprop = SPROP_CLEAR_COLLISION(stored);
00312         if (sprop && sprop->id == id) {
00313             METER(stepHits);
00314             return spp;
00315         }
00316 
00317         if (SPROP_IS_REMOVED(stored)) {
00318             if (!firstRemoved)
00319                 firstRemoved = spp;
00320         } else {
00321             if (adding && !SPROP_HAD_COLLISION(stored))
00322                 SPROP_FLAG_COLLISION(spp, sprop);
00323         }
00324     }
00325 
00326     /* NOTREACHED */
00327     return NULL;
00328 }
00329 
00330 static JSBool
00331 ChangeScope(JSContext *cx, JSScope *scope, int change)
00332 {
00333     int oldlog2, newlog2;
00334     uint32 oldsize, newsize, nbytes;
00335     JSScopeProperty **table, **oldtable, **spp, **oldspp, *sprop;
00336 
00337     /* Grow, shrink, or compress by changing scope->table. */
00338     oldlog2 = JS_DHASH_BITS - scope->hashShift;
00339     newlog2 = oldlog2 + change;
00340     oldsize = JS_BIT(oldlog2);
00341     newsize = JS_BIT(newlog2);
00342     nbytes = SCOPE_TABLE_NBYTES(newsize);
00343     table = (JSScopeProperty **) calloc(nbytes, 1);
00344     if (!table) {
00345         JS_ReportOutOfMemory(cx);
00346         return JS_FALSE;
00347     }
00348 
00349     /* Now that we have a new table allocated, update scope members. */
00350     scope->hashShift = JS_DHASH_BITS - newlog2;
00351     scope->removedCount = 0;
00352     oldtable = scope->table;
00353     scope->table = table;
00354 
00355     /* Treat the above calloc as a JS_malloc, to match CreateScopeTable. */
00356     cx->runtime->gcMallocBytes += nbytes;
00357 
00358     /* Copy only live entries, leaving removed and free ones behind. */
00359     for (oldspp = oldtable; oldsize != 0; oldspp++) {
00360         sprop = SPROP_FETCH(oldspp);
00361         if (sprop) {
00362             spp = js_SearchScope(scope, sprop->id, JS_TRUE);
00363             JS_ASSERT(SPROP_IS_FREE(*spp));
00364             *spp = sprop;
00365         }
00366         oldsize--;
00367     }
00368 
00369     /* Finally, free the old table storage. */
00370     JS_free(cx, oldtable);
00371     return JS_TRUE;
00372 }
00373 
00374 /*
00375  * Take care to exclude the mark and duplicate bits, in case we're called from
00376  * the GC, or we are searching for a property that has not yet been flagged as
00377  * a duplicate when making a duplicate formal parameter.
00378  */
00379 #define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_IS_DUPLICATE)
00380 
00381 JS_STATIC_DLL_CALLBACK(JSDHashNumber)
00382 js_HashScopeProperty(JSDHashTable *table, const void *key)
00383 {
00384     const JSScopeProperty *sprop = (const JSScopeProperty *)key;
00385     JSDHashNumber hash;
00386     JSPropertyOp gsop;
00387 
00388     /* Accumulate from least to most random so the low bits are most random. */
00389     hash = 0;
00390     gsop = sprop->getter;
00391     if (gsop)
00392         hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop;
00393     gsop = sprop->setter;
00394     if (gsop)
00395         hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop;
00396 
00397     hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4)
00398            ^ (sprop->flags & ~SPROP_FLAGS_NOT_MATCHED);
00399 
00400     hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->attrs;
00401     hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->shortid;
00402     hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->slot;
00403     hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->id;
00404     return hash;
00405 }
00406 
00407 #define SPROP_MATCH(sprop, child)                                             \
00408     SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter,  \
00409                        (child)->slot, (child)->attrs, (child)->flags,         \
00410                        (child)->shortid)
00411 
00412 #define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs,       \
00413                            aflags, ashortid)                                  \
00414     ((sprop)->id == (aid) &&                                                  \
00415      SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs,      \
00416                                  aflags, ashortid))
00417 
00418 #define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs,   \
00419                                     aflags, ashortid)                         \
00420     ((sprop)->getter == (agetter) &&                                          \
00421      (sprop)->setter == (asetter) &&                                          \
00422      (sprop)->slot == (aslot) &&                                              \
00423      (sprop)->attrs == (aattrs) &&                                            \
00424      (((sprop)->flags ^ (aflags)) & ~SPROP_FLAGS_NOT_MATCHED) == 0 &&         \
00425      (sprop)->shortid == (ashortid))
00426 
00427 JS_STATIC_DLL_CALLBACK(JSBool)
00428 js_MatchScopeProperty(JSDHashTable *table,
00429                       const JSDHashEntryHdr *hdr,
00430                       const void *key)
00431 {
00432     const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
00433     const JSScopeProperty *sprop = entry->child;
00434     const JSScopeProperty *kprop = (const JSScopeProperty *)key;
00435 
00436     return SPROP_MATCH(sprop, kprop);
00437 }
00438 
00439 static const JSDHashTableOps PropertyTreeHashOps = {
00440     JS_DHashAllocTable,
00441     JS_DHashFreeTable,
00442     JS_DHashGetKeyStub,
00443     js_HashScopeProperty,
00444     js_MatchScopeProperty,
00445     JS_DHashMoveEntryStub,
00446     JS_DHashClearEntryStub,
00447     JS_DHashFinalizeStub,
00448     NULL
00449 };
00450 
00451 /*
00452  * A property tree node on rt->propertyFreeList overlays the following prefix
00453  * struct on JSScopeProperty.
00454  */
00455 typedef struct FreeNode {
00456     jsid                id;
00457     JSScopeProperty     *next;
00458     JSScopeProperty     **prevp;
00459 } FreeNode;
00460 
00461 #define FREENODE(sprop) ((FreeNode *) (sprop))
00462 
00463 #define FREENODE_INSERT(list, sprop)                                          \
00464     JS_BEGIN_MACRO                                                            \
00465         FREENODE(sprop)->next = (list);                                       \
00466         FREENODE(sprop)->prevp = &(list);                                     \
00467         if (list)                                                             \
00468             FREENODE(list)->prevp = &FREENODE(sprop)->next;                   \
00469         (list) = (sprop);                                                     \
00470     JS_END_MACRO
00471 
00472 #define FREENODE_REMOVE(sprop)                                                \
00473     JS_BEGIN_MACRO                                                            \
00474         *FREENODE(sprop)->prevp = FREENODE(sprop)->next;                      \
00475         if (FREENODE(sprop)->next)                                            \
00476             FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp;  \
00477     JS_END_MACRO
00478 
00479 /* NB: Called with the runtime lock held. */
00480 static JSScopeProperty *
00481 NewScopeProperty(JSRuntime *rt)
00482 {
00483     JSScopeProperty *sprop;
00484 
00485     sprop = rt->propertyFreeList;
00486     if (sprop) {
00487         FREENODE_REMOVE(sprop);
00488     } else {
00489         JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *,
00490                                &rt->propertyArenaPool,
00491                                sizeof(JSScopeProperty));
00492         if (!sprop)
00493             return NULL;
00494     }
00495 
00496     JS_RUNTIME_METER(rt, livePropTreeNodes);
00497     JS_RUNTIME_METER(rt, totalPropTreeNodes);
00498     return sprop;
00499 }
00500 
00501 #define CHUNKY_KIDS_TAG         ((jsuword)1)
00502 #define KIDS_IS_CHUNKY(kids)    ((jsuword)(kids) & CHUNKY_KIDS_TAG)
00503 #define KIDS_TO_CHUNK(kids)     ((PropTreeKidsChunk *)                        \
00504                                  ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
00505 #define CHUNK_TO_KIDS(chunk)    ((JSScopeProperty *)                          \
00506                                  ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
00507 #define MAX_KIDS_PER_CHUNK      10
00508 
00509 typedef struct PropTreeKidsChunk PropTreeKidsChunk;
00510 
00511 struct PropTreeKidsChunk {
00512     JSScopeProperty     *kids[MAX_KIDS_PER_CHUNK];
00513     PropTreeKidsChunk   *next;
00514 };
00515 
00516 static PropTreeKidsChunk *
00517 NewPropTreeKidsChunk(JSRuntime *rt)
00518 {
00519     PropTreeKidsChunk *chunk;
00520 
00521     chunk = calloc(1, sizeof *chunk);
00522     if (!chunk)
00523         return NULL;
00524     JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
00525     JS_RUNTIME_METER(rt, propTreeKidsChunks);
00526     return chunk;
00527 }
00528 
00529 static void
00530 DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk)
00531 {
00532     JS_RUNTIME_UNMETER(rt, propTreeKidsChunks);
00533     free(chunk);
00534 }
00535 
00536 /* NB: Called with the runtime lock held. */
00537 static JSBool
00538 InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent,
00539                         JSScopeProperty *child, PropTreeKidsChunk *sweptChunk)
00540 {
00541     JSPropertyTreeEntry *entry;
00542     JSScopeProperty **childp, *kids, *sprop;
00543     PropTreeKidsChunk *chunk, **chunkp;
00544     uintN i;
00545 
00546     JS_ASSERT(!parent || child->parent != parent);
00547 
00548     if (!parent) {
00549         entry = (JSPropertyTreeEntry *)
00550             JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD);
00551         if (!entry)
00552             return JS_FALSE;
00553         childp = &entry->child;
00554         sprop = *childp;
00555         if (!sprop) {
00556             *childp = child;
00557         } else {
00558             /*
00559              * A "Duplicate child" case.
00560              *
00561              * We can't do away with child, as at least one live scope entry
00562              * still points at it.  What's more, that scope's lastProp chains
00563              * through an ancestor line to reach child, and js_Enumerate and
00564              * others count on this linkage.  We must leave child out of the
00565              * hash table, and not require it to be there when we eventually
00566              * GC it (see RemovePropertyTreeChild, below).
00567              *
00568              * It is necessary to leave the duplicate child out of the hash
00569              * table to preserve entry uniqueness.  It is safe to leave the
00570              * child out of the hash table (unlike the duplicate child cases
00571              * below), because the child's parent link will be null, which
00572              * can't dangle.
00573              */
00574             JS_ASSERT(sprop != child && SPROP_MATCH(sprop, child));
00575             JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
00576         }
00577     } else {
00578         childp = &parent->kids;
00579         kids = *childp;
00580         if (kids) {
00581             if (KIDS_IS_CHUNKY(kids)) {
00582                 chunk = KIDS_TO_CHUNK(kids);
00583                 do {
00584                     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
00585                         childp = &chunk->kids[i];
00586                         sprop = *childp;
00587                         if (!sprop)
00588                             goto insert;
00589 
00590                         JS_ASSERT(sprop != child);
00591                         if (SPROP_MATCH(sprop, child)) {
00592                             /*
00593                              * Duplicate child, see comment above.  In this
00594                              * case, we must let the duplicate be inserted at
00595                              * this level in the tree, so we keep iterating,
00596                              * looking for an empty slot in which to insert.
00597                              */
00598                             JS_ASSERT(sprop != child);
00599                             JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
00600                         }
00601                     }
00602                     chunkp = &chunk->next;
00603                 } while ((chunk = *chunkp) != NULL);
00604 
00605                 if (sweptChunk) {
00606                     chunk = sweptChunk;
00607                 } else {
00608                     chunk = NewPropTreeKidsChunk(rt);
00609                     if (!chunk)
00610                         return JS_FALSE;
00611                 }
00612                 *chunkp = chunk;
00613                 childp = &chunk->kids[0];
00614             } else {
00615                 sprop = kids;
00616                 JS_ASSERT(sprop != child);
00617                 if (SPROP_MATCH(sprop, child)) {
00618                     /*
00619                      * Duplicate child, see comment above.  Once again, we
00620                      * must let duplicates created by deletion pile up in a
00621                      * kids-chunk-list, in order to find them when sweeping
00622                      * and thereby avoid dangling parent pointers.
00623                      */
00624                     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
00625                 }
00626                 if (sweptChunk) {
00627                     chunk = sweptChunk;
00628                 } else {
00629                     chunk = NewPropTreeKidsChunk(rt);
00630                     if (!chunk)
00631                         return JS_FALSE;
00632                 }
00633                 parent->kids = CHUNK_TO_KIDS(chunk);
00634                 chunk->kids[0] = sprop;
00635                 childp = &chunk->kids[1];
00636             }
00637         }
00638     insert:
00639         *childp = child;
00640     }
00641 
00642     child->parent = parent;
00643     return JS_TRUE;
00644 }
00645 
00646 /* NB: Called with the runtime lock held. */
00647 static PropTreeKidsChunk *
00648 RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child)
00649 {
00650     JSPropertyTreeEntry *entry;
00651     JSScopeProperty *parent, *kids, *kid;
00652     PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk;
00653     uintN i, j;
00654 
00655     parent = child->parent;
00656     if (!parent) {
00657         /*
00658          * Don't remove child if it is not in rt->propertyTreeHash, but only
00659          * matches a root child in the table that has compatible members. See
00660          * the "Duplicate child" comments in InsertPropertyTreeChild, above.
00661          */
00662         entry = (JSPropertyTreeEntry *)
00663             JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_LOOKUP);
00664 
00665         if (entry->child == child)
00666             JS_DHashTableRawRemove(&rt->propertyTreeHash, &entry->hdr);
00667     } else {
00668         kids = parent->kids;
00669         if (KIDS_IS_CHUNKY(kids)) {
00670             list = chunk = KIDS_TO_CHUNK(kids);
00671             chunkp = &list;
00672 
00673             do {
00674                 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
00675                     if (chunk->kids[i] == child) {
00676                         lastChunk = chunk;
00677                         if (!lastChunk->next) {
00678                             j = i + 1;
00679                         } else {
00680                             j = 0;
00681                             do {
00682                                 chunkp = &lastChunk->next;
00683                                 lastChunk = *chunkp;
00684                             } while (lastChunk->next);
00685                         }
00686                         for (; j < MAX_KIDS_PER_CHUNK; j++) {
00687                             if (!lastChunk->kids[j])
00688                                 break;
00689                         }
00690                         --j;
00691                         if (chunk != lastChunk || j > i)
00692                             chunk->kids[i] = lastChunk->kids[j];
00693                         lastChunk->kids[j] = NULL;
00694                         if (j == 0) {
00695                             *chunkp = NULL;
00696                             if (!list)
00697                                 parent->kids = NULL;
00698                             return lastChunk;
00699                         }
00700                         return NULL;
00701                     }
00702                 }
00703 
00704                 chunkp = &chunk->next;
00705             } while ((chunk = *chunkp) != NULL);
00706         } else {
00707             kid = kids;
00708             if (kid == child)
00709                 parent->kids = NULL;
00710         }
00711     }
00712     return NULL;
00713 }
00714 
00715 /*
00716  * Called *without* the runtime lock held, this function acquires that lock
00717  * only when inserting a new child.  Thus there may be races to find or add
00718  * a node that result in duplicates.  We expect such races to be rare!
00719  */
00720 static JSScopeProperty *
00721 GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
00722                      JSScopeProperty *child)
00723 {
00724     JSRuntime *rt;
00725     JSPropertyTreeEntry *entry;
00726     JSScopeProperty *sprop;
00727     PropTreeKidsChunk *chunk;
00728     uintN i;
00729 
00730     rt = cx->runtime;
00731     if (!parent) {
00732         JS_LOCK_RUNTIME(rt);
00733 
00734         entry = (JSPropertyTreeEntry *)
00735             JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD);
00736         if (!entry)
00737             goto out_of_memory;
00738 
00739         sprop = entry->child;
00740         if (sprop)
00741             goto out;
00742     } else {
00743         /*
00744          * Because chunks are appended at the end and never deleted except by
00745          * the GC, we can search without taking the runtime lock.  We may miss
00746          * a matching sprop added by another thread, and make a duplicate one,
00747          * but that is an unlikely, therefore small, cost.  The property tree
00748          * has extremely low fan-out below its root in popular embeddings with
00749          * real-world workloads.
00750          *
00751          * If workload changes so as to increase fan-out significantly below
00752          * the property tree root, we'll want to add another tag bit stored in
00753          * parent->kids that indicates a JSDHashTable pointer.
00754          */
00755         entry = NULL;
00756         sprop = parent->kids;
00757         if (sprop) {
00758             if (KIDS_IS_CHUNKY(sprop)) {
00759                 chunk = KIDS_TO_CHUNK(sprop);
00760                 do {
00761                     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
00762                         sprop = chunk->kids[i];
00763                         if (!sprop)
00764                             goto not_found;
00765 
00766                         if (SPROP_MATCH(sprop, child))
00767                             return sprop;
00768                     }
00769                 } while ((chunk = chunk->next) != NULL);
00770             } else {
00771                 if (SPROP_MATCH(sprop, child))
00772                     return sprop;
00773             }
00774         }
00775 
00776     not_found:
00777         JS_LOCK_RUNTIME(rt);
00778     }
00779 
00780     sprop = NewScopeProperty(rt);
00781     if (!sprop)
00782         goto out_of_memory;
00783 
00784     sprop->id = child->id;
00785     sprop->getter = child->getter;
00786     sprop->setter = child->setter;
00787     sprop->slot = child->slot;
00788     sprop->attrs = child->attrs;
00789     sprop->flags = child->flags;
00790     sprop->shortid = child->shortid;
00791     sprop->parent = sprop->kids = NULL;
00792     if (!parent) {
00793         entry->child = sprop;
00794     } else {
00795         if (!InsertPropertyTreeChild(rt, parent, sprop, NULL))
00796             goto out_of_memory;
00797     }
00798 
00799 out:
00800     JS_UNLOCK_RUNTIME(rt);
00801     return sprop;
00802 
00803 out_of_memory:
00804     JS_UNLOCK_RUNTIME(rt);
00805     JS_ReportOutOfMemory(cx);
00806     return NULL;
00807 }
00808 
00809 #ifdef DEBUG_notbrendan
00810 #define CHECK_ANCESTOR_LINE(scope, sparse)                                    \
00811     JS_BEGIN_MACRO                                                            \
00812         if ((scope)->table) CheckAncestorLine(scope, sparse);                 \
00813     JS_END_MACRO
00814 
00815 static void
00816 CheckAncestorLine(JSScope *scope, JSBool sparse)
00817 {
00818     uint32 size;
00819     JSScopeProperty **spp, **start, **end, *ancestorLine, *sprop, *aprop;
00820     uint32 entryCount, ancestorCount;
00821 
00822     ancestorLine = SCOPE_LAST_PROP(scope);
00823     if (ancestorLine)
00824         JS_ASSERT(SCOPE_HAS_PROPERTY(scope, ancestorLine));
00825 
00826     entryCount = 0;
00827     size = SCOPE_CAPACITY(scope);
00828     start = scope->table;
00829     for (spp = start, end = start + size; spp < end; spp++) {
00830         sprop = SPROP_FETCH(spp);
00831         if (sprop) {
00832             entryCount++;
00833             for (aprop = ancestorLine; aprop; aprop = aprop->parent) {
00834                 if (aprop == sprop)
00835                     break;
00836             }
00837             JS_ASSERT(aprop);
00838         }
00839     }
00840     JS_ASSERT(entryCount == scope->entryCount);
00841 
00842     ancestorCount = 0;
00843     for (sprop = ancestorLine; sprop; sprop = sprop->parent) {
00844         if (SCOPE_HAD_MIDDLE_DELETE(scope) &&
00845             !SCOPE_HAS_PROPERTY(scope, sprop)) {
00846             JS_ASSERT(sparse || (sprop->flags & SPROP_IS_DUPLICATE));
00847             continue;
00848         }
00849         ancestorCount++;
00850     }
00851     JS_ASSERT(ancestorCount == scope->entryCount);
00852 }
00853 #else
00854 #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
00855 #endif
00856 
00857 static void
00858 ReportReadOnlyScope(JSContext *cx, JSScope *scope)
00859 {
00860     JSString *str;
00861 
00862     str = js_ValueToString(cx, OBJECT_TO_JSVAL(scope->object));
00863     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_READ_ONLY,
00864                          str
00865                          ? JS_GetStringBytes(str)
00866                          : LOCKED_OBJ_GET_CLASS(scope->object)->name);
00867 }
00868 
00869 JSScopeProperty *
00870 js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
00871                     JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
00872                     uintN attrs, uintN flags, intN shortid)
00873 {
00874     JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
00875     uint32 size, splen, i;
00876     int change;
00877     JSTempValueRooter tvr;
00878 
00879     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
00880     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
00881 
00882     /*
00883      * You can't add properties to a sealed scope.  But note well that you can
00884      * change property attributes in a sealed scope, even though that replaces
00885      * a JSScopeProperty * in the scope's hash table -- but no id is added, so
00886      * the scope remains sealed.
00887      */
00888     if (SCOPE_IS_SEALED(scope)) {
00889         ReportReadOnlyScope(cx, scope);
00890         return NULL;
00891     }
00892 
00893     /*
00894      * Normalize stub getter and setter values for faster is-stub testing in
00895      * the SPROP_CALL_[GS]ETTER macros.
00896      */
00897     if (getter == JS_PropertyStub)
00898         getter = NULL;
00899     if (setter == JS_PropertyStub)
00900         setter = NULL;
00901 
00902     /*
00903      * Search for id in order to claim its entry, allocating a property tree
00904      * node if one doesn't already exist for our parameters.
00905      */
00906     spp = js_SearchScope(scope, id, JS_TRUE);
00907     sprop = overwriting = SPROP_FETCH(spp);
00908     if (!sprop) {
00909         /* Check whether we need to grow, if the load factor is >= .75. */
00910         size = SCOPE_CAPACITY(scope);
00911         if (scope->entryCount + scope->removedCount >= size - (size >> 2)) {
00912             if (scope->removedCount >= size >> 2) {
00913                 METER(compresses);
00914                 change = 0;
00915             } else {
00916                 METER(grows);
00917                 change = 1;
00918             }
00919             if (!ChangeScope(cx, scope, change) &&
00920                 scope->entryCount + scope->removedCount == size - 1) {
00921                 METER(addFailures);
00922                 return NULL;
00923             }
00924             spp = js_SearchScope(scope, id, JS_TRUE);
00925             JS_ASSERT(!SPROP_FETCH(spp));
00926         }
00927     } else {
00928         /* Property exists: js_SearchScope must have returned a valid entry. */
00929         JS_ASSERT(!SPROP_IS_REMOVED(*spp));
00930 
00931         /*
00932          * If all property members match, this is a redundant add and we can
00933          * return early.  If the caller wants to allocate a slot, but doesn't
00934          * care which slot, copy sprop->slot into slot so we can match sprop,
00935          * if all other members match.
00936          */
00937         if (!(attrs & JSPROP_SHARED) &&
00938             slot == SPROP_INVALID_SLOT &&
00939             SPROP_HAS_VALID_SLOT(sprop, scope)) {
00940             slot = sprop->slot;
00941         }
00942         if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs,
00943                                         flags, shortid)) {
00944             METER(redundantAdds);
00945             return sprop;
00946         }
00947 
00948         /*
00949          * Duplicate formal parameters require us to leave the old property
00950          * on the ancestor line, so the decompiler can find it, even though
00951          * its entry in scope->table is overwritten to point at a new property
00952          * descending from the old one.  The SPROP_IS_DUPLICATE flag helps us
00953          * cope with the consequent disparity between ancestor line height and
00954          * scope->entryCount.
00955          */
00956         if (flags & SPROP_IS_DUPLICATE) {
00957             sprop->flags |= SPROP_IS_DUPLICATE;
00958         } else {
00959             /*
00960              * If we are clearing sprop to force an existing property to be
00961              * overwritten (apart from a duplicate formal parameter), we must
00962              * unlink it from the ancestor line at scope->lastProp, lazily if
00963              * sprop is not lastProp.  And we must remove the entry at *spp,
00964              * precisely so the lazy "middle delete" fixup code further below
00965              * won't find sprop in scope->table, in spite of sprop being on
00966              * the ancestor line.
00967              *
00968              * When we finally succeed in finding or creating a new sprop
00969              * and storing its pointer at *spp, we'll use the |overwriting|
00970              * local saved when we first looked up id to decide whether we're
00971              * indeed creating a new entry, or merely overwriting an existing
00972              * property.
00973              */
00974             if (sprop == SCOPE_LAST_PROP(scope)) {
00975                 do {
00976                     SCOPE_REMOVE_LAST_PROP(scope);
00977                     if (!SCOPE_HAD_MIDDLE_DELETE(scope))
00978                         break;
00979                     sprop = SCOPE_LAST_PROP(scope);
00980                 } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
00981             } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
00982                 /*
00983                  * If we have no hash table yet, we need one now.  The middle
00984                  * delete code is simple-minded that way!
00985                  */
00986                 if (!scope->table) {
00987                     if (!CreateScopeTable(cx, scope, JS_TRUE))
00988                         return NULL;
00989                     spp = js_SearchScope(scope, id, JS_TRUE);
00990                     sprop = overwriting = SPROP_FETCH(spp);
00991                 }
00992                 SCOPE_SET_MIDDLE_DELETE(scope);
00993             }
00994         }
00995 
00996         /*
00997          * If we fail later on trying to find or create a new sprop, we will
00998          * goto fail_overwrite and restore *spp from |overwriting|.  Note that
00999          * we don't bother to keep scope->removedCount in sync, because we'll
01000          * fix up *spp and scope->entryCount shortly, no matter how control
01001          * flow returns from this function.
01002          */
01003         if (scope->table)
01004             SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
01005         scope->entryCount--;
01006         CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01007         sprop = NULL;
01008     }
01009 
01010     if (!sprop) {
01011         /*
01012          * If properties were deleted from the middle of the list starting at
01013          * scope->lastProp, we may need to fork the property tree and squeeze
01014          * all deleted properties out of scope's ancestor line.  Otherwise we
01015          * risk adding a node with the same id as a "middle" node, violating
01016          * the rule that properties along an ancestor line have distinct ids
01017          * (unless flagged SPROP_IS_DUPLICATE).
01018          */
01019         if (SCOPE_HAD_MIDDLE_DELETE(scope)) {
01020             JS_ASSERT(scope->table);
01021             CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01022 
01023             splen = scope->entryCount;
01024             if (splen == 0) {
01025                 JS_ASSERT(scope->lastProp == NULL);
01026             } else {
01027                 /*
01028                  * Enumerate live entries in scope->table using a temporary
01029                  * vector, by walking the (possibly sparse, due to deletions)
01030                  * ancestor line from scope->lastProp.
01031                  */
01032                 spvec = (JSScopeProperty **)
01033                         JS_malloc(cx, SCOPE_TABLE_NBYTES(splen));
01034                 if (!spvec)
01035                     goto fail_overwrite;
01036                 i = splen;
01037                 sprop = SCOPE_LAST_PROP(scope);
01038                 JS_ASSERT(sprop);
01039                 do {
01040                     /*
01041                      * NB: test SCOPE_GET_PROPERTY, not SCOPE_HAS_PROPERTY --
01042                      * the latter insists that sprop->id maps to sprop, while
01043                      * the former simply tests whether sprop->id is bound in
01044                      * scope.  We must allow for duplicate formal parameters
01045                      * along the ancestor line, and fork them as needed.
01046                      */
01047                     if (!SCOPE_GET_PROPERTY(scope, sprop->id))
01048                         continue;
01049 
01050                     JS_ASSERT(sprop != overwriting);
01051                     if (i == 0) {
01052                         /*
01053                          * If our original splen estimate, scope->entryCount,
01054                          * is less than the ancestor line height, there must
01055                          * be duplicate formal parameters in this (function
01056                          * object) scope.  Count remaining ancestors in order
01057                          * to realloc spvec.
01058                          */
01059                         JSScopeProperty *tmp = sprop;
01060                         do {
01061                             if (SCOPE_GET_PROPERTY(scope, tmp->id))
01062                                 i++;
01063                         } while ((tmp = tmp->parent) != NULL);
01064                         spp2 = (JSScopeProperty **)
01065                              JS_realloc(cx, spvec, SCOPE_TABLE_NBYTES(splen+i));
01066                         if (!spp2) {
01067                             JS_free(cx, spvec);
01068                             goto fail_overwrite;
01069                         }
01070 
01071                         spvec = spp2;
01072                         memmove(spvec + i, spvec, SCOPE_TABLE_NBYTES(splen));
01073                         splen += i;
01074                     }
01075 
01076                     spvec[--i] = sprop;
01077                 } while ((sprop = sprop->parent) != NULL);
01078                 JS_ASSERT(i == 0);
01079 
01080                 /*
01081                  * Now loop forward through spvec, forking the property tree
01082                  * whenever we see a "parent gap" due to deletions from scope.
01083                  * NB: sprop is null on first entry to the loop body.
01084                  */
01085                 do {
01086                     if (spvec[i]->parent == sprop) {
01087                         sprop = spvec[i];
01088                     } else {
01089                         sprop = GetPropertyTreeChild(cx, sprop, spvec[i]);
01090                         if (!sprop) {
01091                             JS_free(cx, spvec);
01092                             goto fail_overwrite;
01093                         }
01094 
01095                         spp2 = js_SearchScope(scope, sprop->id, JS_FALSE);
01096                         JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
01097                         SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
01098                     }
01099                 } while (++i < splen);
01100                 JS_free(cx, spvec);
01101 
01102                 /*
01103                  * Now sprop points to the last property in scope, where the
01104                  * ancestor line from sprop to the root is dense w.r.t. scope:
01105                  * it contains no nodes not mapped by scope->table, apart from
01106                  * any stinking ECMA-mandated duplicate formal parameters.
01107                  */
01108                 scope->lastProp = sprop;
01109                 CHECK_ANCESTOR_LINE(scope, JS_FALSE);
01110                 JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
01111             }
01112 
01113             SCOPE_CLR_MIDDLE_DELETE(scope);
01114         }
01115 
01116         /*
01117          * Aliases share another property's slot, passed in the |slot| param.
01118          * Shared properties have no slot.  Unshared properties that do not
01119          * alias another property's slot get one here, but may lose it due to
01120          * a JS_ClearScope call.
01121          */
01122         if (!(flags & SPROP_IS_ALIAS)) {
01123             if (attrs & JSPROP_SHARED) {
01124                 slot = SPROP_INVALID_SLOT;
01125             } else {
01126                 /*
01127                  * We may have set slot from a nearly-matching sprop, above.
01128                  * If so, we're overwriting that nearly-matching sprop, so we
01129                  * can reuse its slot -- we don't need to allocate a new one.
01130                  * Callers should therefore pass SPROP_INVALID_SLOT for all
01131                  * non-alias, unshared property adds.
01132                  */
01133                 if (slot != SPROP_INVALID_SLOT)
01134                     JS_ASSERT(overwriting);
01135                 else if (!js_AllocSlot(cx, scope->object, &slot))
01136                     goto fail_overwrite;
01137             }
01138         }
01139 
01140         /*
01141          * Check for a watchpoint on a deleted property; if one exists, change
01142          * setter to js_watch_set.
01143          * XXXbe this could get expensive with lots of watchpoints...
01144          */
01145         if (!JS_CLIST_IS_EMPTY(&cx->runtime->watchPointList) &&
01146             js_FindWatchPoint(cx->runtime, scope, id)) {
01147             JS_PUSH_TEMP_ROOT_SPROP(cx, overwriting, &tvr);
01148             setter = js_WrapWatchedSetter(cx, id, attrs, setter);
01149             JS_POP_TEMP_ROOT(cx, &tvr);
01150             if (!setter)
01151                 goto fail_overwrite;
01152         }
01153 
01154         /* Find or create a property tree node labeled by our arguments. */
01155         child.id = id;
01156         child.getter = getter;
01157         child.setter = setter;
01158         child.slot = slot;
01159         child.attrs = attrs;
01160         child.flags = flags;
01161         child.shortid = shortid;
01162         sprop = GetPropertyTreeChild(cx, scope->lastProp, &child);
01163         if (!sprop)
01164             goto fail_overwrite;
01165 
01166         /* Store the tree node pointer in the table entry for id. */
01167         if (scope->table)
01168             SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
01169         scope->entryCount++;
01170         scope->lastProp = sprop;
01171         CHECK_ANCESTOR_LINE(scope, JS_FALSE);
01172         if (!overwriting) {
01173             JS_RUNTIME_METER(cx->runtime, liveScopeProps);
01174             JS_RUNTIME_METER(cx->runtime, totalScopeProps);
01175         }
01176 
01177         /*
01178          * If we reach the hashing threshold, try to allocate scope->table.
01179          * If we can't (a rare event, preceded by swapping to death on most
01180          * modern OSes), stick with linear search rather than whining about
01181          * this little set-back.  Therefore we must test !scope->table and
01182          * scope->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
01183          * entry count just reached the threshold.
01184          */
01185         if (!scope->table && scope->entryCount >= SCOPE_HASH_THRESHOLD)
01186             (void) CreateScopeTable(cx, scope, JS_FALSE);
01187     }
01188 
01189     METER(adds);
01190     return sprop;
01191 
01192 fail_overwrite:
01193     if (overwriting) {
01194         /*
01195          * We may or may not have forked overwriting out of scope's ancestor
01196          * line, so we must check (the alternative is to set a flag above, but
01197          * that hurts the common, non-error case).  If we did fork overwriting
01198          * out, we'll add it back at scope->lastProp.  This means enumeration
01199          * order can change due to a failure to overwrite an id.
01200          * XXXbe very minor incompatibility
01201          */
01202         for (sprop = SCOPE_LAST_PROP(scope); ; sprop = sprop->parent) {
01203             if (!sprop) {
01204                 sprop = SCOPE_LAST_PROP(scope);
01205                 if (overwriting->parent == sprop) {
01206                     scope->lastProp = overwriting;
01207                 } else {
01208                     sprop = GetPropertyTreeChild(cx, sprop, overwriting);
01209                     if (sprop) {
01210                         JS_ASSERT(sprop != overwriting);
01211                         scope->lastProp = sprop;
01212                     }
01213                     overwriting = sprop;
01214                 }
01215                 break;
01216             }
01217             if (sprop == overwriting)
01218                 break;
01219         }
01220         if (overwriting) {
01221             if (scope->table)
01222                 SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
01223             scope->entryCount++;
01224         }
01225         CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01226     }
01227     METER(addFailures);
01228     return NULL;
01229 }
01230 
01231 JSScopeProperty *
01232 js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
01233                             JSScopeProperty *sprop, uintN attrs, uintN mask,
01234                             JSPropertyOp getter, JSPropertyOp setter)
01235 {
01236     JSScopeProperty child, *newsprop, **spp;
01237 
01238     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01239 
01240     /* Allow only shared (slot-less) => unshared (slot-full) transition. */
01241     attrs |= sprop->attrs & mask;
01242     JS_ASSERT(!((attrs ^ sprop->attrs) & JSPROP_SHARED) ||
01243               !(attrs & JSPROP_SHARED));
01244     if (getter == JS_PropertyStub)
01245         getter = NULL;
01246     if (setter == JS_PropertyStub)
01247         setter = NULL;
01248     if (sprop->attrs == attrs &&
01249         sprop->getter == getter &&
01250         sprop->setter == setter) {
01251         return sprop;
01252     }
01253 
01254     child.id = sprop->id;
01255     child.getter = getter;
01256     child.setter = setter;
01257     child.slot = sprop->slot;
01258     child.attrs = attrs;
01259     child.flags = sprop->flags;
01260     child.shortid = sprop->shortid;
01261 
01262     if (SCOPE_LAST_PROP(scope) == sprop) {
01263         /*
01264          * Optimize the case where the last property added to scope is changed
01265          * to have a different attrs, getter, or setter.  In the last property
01266          * case, we need not fork the property tree.  But since we do not call
01267          * js_AddScopeProperty, we may need to allocate a new slot directly.
01268          */
01269         if ((sprop->attrs & JSPROP_SHARED) && !(attrs & JSPROP_SHARED)) {
01270             JS_ASSERT(child.slot == SPROP_INVALID_SLOT);
01271             if (!js_AllocSlot(cx, scope->object, &child.slot))
01272                 return NULL;
01273         }
01274 
01275         newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
01276         if (newsprop) {
01277             spp = js_SearchScope(scope, sprop->id, JS_FALSE);
01278             JS_ASSERT(SPROP_FETCH(spp) == sprop);
01279 
01280             if (scope->table)
01281                 SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
01282             scope->lastProp = newsprop;
01283             CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01284         }
01285     } else {
01286         /*
01287          * Let js_AddScopeProperty handle this |overwriting| case, including
01288          * the conservation of sprop->slot (if it's valid).  We must not call
01289          * js_RemoveScopeProperty here, it will free a valid sprop->slot and
01290          * js_AddScopeProperty won't re-allocate it.
01291          */
01292         newsprop = js_AddScopeProperty(cx, scope, child.id,
01293                                        child.getter, child.setter, child.slot,
01294                                        child.attrs, child.flags, child.shortid);
01295     }
01296 
01297 #ifdef DUMP_SCOPE_STATS
01298     if (!newsprop)
01299         METER(changeFailures);
01300 #endif
01301     return newsprop;
01302 }
01303 
01304 JSBool
01305 js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id)
01306 {
01307     JSScopeProperty **spp, *stored, *sprop;
01308     uint32 size;
01309 
01310     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
01311     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01312     if (SCOPE_IS_SEALED(scope)) {
01313         ReportReadOnlyScope(cx, scope);
01314         return JS_FALSE;
01315     }
01316     METER(removes);
01317 
01318     spp = js_SearchScope(scope, id, JS_FALSE);
01319     stored = *spp;
01320     sprop = SPROP_CLEAR_COLLISION(stored);
01321     if (!sprop) {
01322         METER(uselessRemoves);
01323         return JS_TRUE;
01324     }
01325 
01326     /* Convert from a list to a hash so we can handle "middle deletes". */
01327     if (!scope->table && sprop != scope->lastProp) {
01328         if (!CreateScopeTable(cx, scope, JS_TRUE))
01329             return JS_FALSE;
01330         spp = js_SearchScope(scope, id, JS_FALSE);
01331         stored = *spp;
01332         sprop = SPROP_CLEAR_COLLISION(stored);
01333     }
01334 
01335     /* First, if sprop is unshared and not cleared, free its slot number. */
01336     if (SPROP_HAS_VALID_SLOT(sprop, scope)) {
01337         js_FreeSlot(cx, scope->object, sprop->slot);
01338         JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
01339     }
01340 
01341     /* Next, remove id by setting its entry to a removed or free sentinel. */
01342     if (SPROP_HAD_COLLISION(stored)) {
01343         JS_ASSERT(scope->table);
01344         *spp = SPROP_REMOVED;
01345         scope->removedCount++;
01346     } else {
01347         METER(removeFrees);
01348         if (scope->table)
01349             *spp = NULL;
01350     }
01351     scope->entryCount--;
01352     JS_RUNTIME_UNMETER(cx->runtime, liveScopeProps);
01353 
01354     /* Update scope->lastProp directly, or set its deferred update flag. */
01355     if (sprop == SCOPE_LAST_PROP(scope)) {
01356         do {
01357             SCOPE_REMOVE_LAST_PROP(scope);
01358             if (!SCOPE_HAD_MIDDLE_DELETE(scope))
01359                 break;
01360             sprop = SCOPE_LAST_PROP(scope);
01361         } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
01362     } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
01363         SCOPE_SET_MIDDLE_DELETE(scope);
01364     }
01365     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01366 
01367     /* Last, consider shrinking scope's table if its load factor is <= .25. */
01368     size = SCOPE_CAPACITY(scope);
01369     if (size > MIN_SCOPE_SIZE && scope->entryCount <= size >> 2) {
01370         METER(shrinks);
01371         (void) ChangeScope(cx, scope, -1);
01372     }
01373 
01374     return JS_TRUE;
01375 }
01376 
01377 void
01378 js_ClearScope(JSContext *cx, JSScope *scope)
01379 {
01380     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
01381 #ifdef DEBUG
01382     JS_LOCK_RUNTIME_VOID(cx->runtime,
01383                          cx->runtime->liveScopeProps -= scope->entryCount);
01384 #endif
01385 
01386     if (scope->table)
01387         free(scope->table);
01388     SCOPE_CLR_MIDDLE_DELETE(scope);
01389     InitMinimalScope(scope);
01390     JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
01391 }
01392 
01393 void
01394 js_MarkId(JSContext *cx, jsid id)
01395 {
01396     if (JSID_IS_ATOM(id))
01397         GC_MARK_ATOM(cx, JSID_TO_ATOM(id));
01398     else if (JSID_IS_OBJECT(id))
01399         GC_MARK(cx, JSID_TO_OBJECT(id), "id");
01400     else
01401         JS_ASSERT(JSID_IS_INT(id));
01402 }
01403 
01404 #if defined GC_MARK_DEBUG || defined DUMP_SCOPE_STATS
01405 # include "jsprf.h"
01406 #endif
01407 
01408 void
01409 js_MarkScopeProperty(JSContext *cx, JSScopeProperty *sprop)
01410 {
01411     sprop->flags |= SPROP_MARK;
01412     MARK_ID(cx, sprop->id);
01413 
01414 #if JS_HAS_GETTER_SETTER
01415     if (sprop->attrs & (JSPROP_GETTER | JSPROP_SETTER)) {
01416 #ifdef GC_MARK_DEBUG
01417         char buf[64];
01418         char buf2[11];
01419         const char *id;
01420 
01421         if (JSID_IS_ATOM(sprop->id)) {
01422             JSAtom *atom = JSID_TO_ATOM(sprop->id);
01423 
01424             id = (atom && ATOM_IS_STRING(atom))
01425                  ? JS_GetStringBytes(ATOM_TO_STRING(atom))
01426                  : "unknown";
01427         } else if (JSID_IS_INT(sprop->id)) {
01428             JS_snprintf(buf2, sizeof buf2, "%d", JSID_TO_INT(sprop->id));
01429             id = buf2;
01430         } else {
01431             id = "<object>";
01432         }
01433 #endif
01434 
01435         if (sprop->attrs & JSPROP_GETTER) {
01436 #ifdef GC_MARK_DEBUG
01437             JS_snprintf(buf, sizeof buf, "%s %s",
01438                         id, js_getter_str);
01439 #endif
01440             GC_MARK(cx, JSVAL_TO_GCTHING((jsval) sprop->getter), buf);
01441         }
01442         if (sprop->attrs & JSPROP_SETTER) {
01443 #ifdef GC_MARK_DEBUG
01444             JS_snprintf(buf, sizeof buf, "%s %s",
01445                         id, js_setter_str);
01446 #endif
01447             GC_MARK(cx, JSVAL_TO_GCTHING((jsval) sprop->setter), buf);
01448         }
01449     }
01450 #endif /* JS_HAS_GETTER_SETTER */
01451 }
01452 
01453 #ifdef DUMP_SCOPE_STATS
01454 
01455 #include <stdio.h>
01456 #include <math.h>
01457 
01458 uint32 js_nkids_max;
01459 uint32 js_nkids_sum;
01460 double js_nkids_sqsum;
01461 uint32 js_nkids_hist[11];
01462 
01463 static void
01464 MeterKidCount(uintN nkids)
01465 {
01466     if (nkids) {
01467         js_nkids_sum += nkids;
01468         js_nkids_sqsum += (double)nkids * nkids;
01469         if (nkids > js_nkids_max)
01470             js_nkids_max = nkids;
01471     }
01472     js_nkids_hist[JS_MIN(nkids, 10)]++;
01473 }
01474 
01475 static void
01476 MeterPropertyTree(JSScopeProperty *node)
01477 {
01478     uintN i, nkids;
01479     JSScopeProperty *kids, *kid;
01480     PropTreeKidsChunk *chunk;
01481 
01482     nkids = 0;
01483     kids = node->kids;
01484     if (kids) {
01485         if (KIDS_IS_CHUNKY(kids)) {
01486             for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
01487                 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
01488                     kid = chunk->kids[i];
01489                     if (!kid)
01490                         break;
01491                     MeterPropertyTree(kid);
01492                     nkids++;
01493                 }
01494             }
01495         } else {
01496             MeterPropertyTree(kids);
01497             nkids = 1;
01498         }
01499     }
01500 
01501     MeterKidCount(nkids);
01502 }
01503 
01504 JS_STATIC_DLL_CALLBACK(JSDHashOperator)
01505 js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
01506                      void *arg)
01507 {
01508     JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
01509 
01510     MeterPropertyTree(entry->child);
01511     return JS_DHASH_NEXT;
01512 }
01513 
01514 static void
01515 DumpSubtree(JSScopeProperty *sprop, int level, FILE *fp)
01516 {
01517     char buf[10];
01518     JSScopeProperty *kids, *kid;
01519     PropTreeKidsChunk *chunk;
01520     uintN i;
01521 
01522     fprintf(fp, "%*sid %s g/s %p/%p slot %lu attrs %x flags %x shortid %d\n",
01523             level, "",
01524             JSID_IS_ATOM(sprop->id)
01525             ? JS_GetStringBytes(ATOM_TO_STRING(JSID_TO_ATOM(sprop->id)))
01526             : JSID_IS_OBJECT(sprop->id)
01527             ? js_ValueToPrintableString(cx, OBJECT_JSID_TO_JSVAL(sprop->id))
01528             : (JS_snprintf(buf, sizeof buf, "%ld", JSVAL_TO_INT(sprop->id)),
01529                buf)
01530             (void *) sprop->getter, (void *) sprop->setter,
01531             (unsigned long) sprop->slot, sprop->attrs, sprop->flags,
01532             sprop->shortid);
01533     kids = sprop->kids;
01534     if (kids) {
01535         ++level;
01536         if (KIDS_IS_CHUNKY(kids)) {
01537             chunk = KIDS_TO_CHUNK(kids);
01538             do {
01539                 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
01540                     kid = chunk->kids[i];
01541                     if (!kid)
01542                         break;
01543                     JS_ASSERT(kid->parent == sprop);
01544                     DumpSubtree(kid, level, fp);
01545                 }
01546             } while ((chunk = chunk->next) != NULL);
01547         } else {
01548             kid = kids;
01549             DumpSubtree(kid, level, fp);
01550         }
01551     }
01552 }
01553 
01554 #endif /* DUMP_SCOPE_STATS */
01555 
01556 void
01557 js_SweepScopeProperties(JSRuntime *rt)
01558 {
01559     JSArena **ap, *a;
01560     JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
01561     uintN liveCount;
01562     PropTreeKidsChunk *chunk, *nextChunk, *freeChunk;
01563     uintN i;
01564 
01565 #ifdef DUMP_SCOPE_STATS
01566     uint32 livePropCapacity = 0, totalLiveCount = 0;
01567     static FILE *logfp;
01568     if (!logfp)
01569         logfp = fopen("/tmp/proptree.stats", "a");
01570 
01571     MeterKidCount(rt->propertyTreeHash.entryCount);
01572     JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, NULL);
01573 
01574     {
01575         double mean = 0.0, var = 0.0, sigma = 0.0;
01576         double nodesum = rt->livePropTreeNodes;
01577         double kidsum = js_nkids_sum;
01578         if (nodesum > 0 && kidsum >= 0) {
01579             mean = kidsum / nodesum;
01580             var = nodesum * js_nkids_sqsum - kidsum * kidsum;
01581             if (var < 0.0 || nodesum <= 1)
01582                 var = 0.0;
01583             else
01584                 var /= nodesum * (nodesum - 1);
01585 
01586             /* Windows says sqrt(0.0) is "-1.#J" (?!) so we must test. */
01587             sigma = (var != 0.0) ? sqrt(var) : 0.0;
01588         }
01589 
01590         fprintf(logfp,
01591                 "props %u nodes %g beta %g meankids %g sigma %g max %u",
01592                 rt->liveScopeProps, nodesum, nodesum / rt->liveScopeProps,
01593                 mean, sigma, js_nkids_max);
01594     }
01595 
01596     fprintf(logfp, " histogram %u %u %u %u %u %u %u %u %u %u %u",
01597             js_nkids_hist[0], js_nkids_hist[1],
01598             js_nkids_hist[2], js_nkids_hist[3],
01599             js_nkids_hist[4], js_nkids_hist[5],
01600             js_nkids_hist[6], js_nkids_hist[7],
01601             js_nkids_hist[8], js_nkids_hist[9],
01602             js_nkids_hist[10]);
01603     js_nkids_sum = js_nkids_max = 0;
01604     js_nkids_sqsum = 0;
01605     memset(js_nkids_hist, 0, sizeof js_nkids_hist);
01606 #endif
01607 
01608     ap = &rt->propertyArenaPool.first.next;
01609     while ((a = *ap) != NULL) {
01610         limit = (JSScopeProperty *) a->avail;
01611         liveCount = 0;
01612         for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
01613             /* If the id is null, sprop is already on the freelist. */
01614             if (sprop->id == JSVAL_NULL)
01615                 continue;
01616 
01617             /* If the mark bit is set, sprop is alive, so we skip it. */
01618             if (sprop->flags & SPROP_MARK) {
01619                 sprop->flags &= ~SPROP_MARK;
01620                 liveCount++;
01621                 continue;
01622             }
01623 
01624             /* Ok, sprop is garbage to collect: unlink it from its parent. */
01625             freeChunk = RemovePropertyTreeChild(rt, sprop);
01626 
01627             /*
01628              * Take care to reparent all sprop's kids to their grandparent.
01629              * InsertPropertyTreeChild can potentially fail for two reasons:
01630              *
01631              * 1. If parent is null, insertion into the root property hash
01632              *    table may fail. We are forced to leave the kid out of the
01633              *    table (as can already happen with duplicates) but ensure
01634              *    that the kid's parent pointer is set to null.
01635              *
01636              * 2. If parent is non-null, allocation of a new KidsChunk can
01637              *    fail. To prevent this from happening, we allow sprops's own
01638              *    chunks to be reused by the grandparent, which removes the
01639              *    need for InsertPropertyTreeChild to malloc a new KidsChunk.
01640              *
01641              *    If sprop does not have chunky kids, then we rely on the
01642              *    RemovePropertyTreeChild call above (which removed sprop from
01643              *    its parent) either leaving one free entry, or else returning
01644              *    the now-unused chunk to us so we can reuse it.
01645              *
01646              * We also require the grandparent to have either no kids or else
01647              * chunky kids. A single non-chunky kid would force a new chunk to
01648              * be malloced in some cases (if sprop had a single non-chunky
01649              * kid, or a multiple of MAX_KIDS_PER_CHUNK kids). Note that
01650              * RemovePropertyTreeChild never converts a single-entry chunky
01651              * kid back to a non-chunky kid, so we are assured of correct
01652              * behaviour.
01653              */
01654             kids = sprop->kids;
01655             if (kids) {
01656                 sprop->kids = NULL;
01657                 parent = sprop->parent;
01658                 /* Validate that grandparent has no kids or chunky kids. */
01659                 JS_ASSERT(!parent || !parent->kids ||
01660                           KIDS_IS_CHUNKY(parent->kids));
01661                 if (KIDS_IS_CHUNKY(kids)) {
01662                     chunk = KIDS_TO_CHUNK(kids);
01663                     do {
01664                         nextChunk = chunk->next;
01665                         chunk->next = NULL;
01666                         for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
01667                             kid = chunk->kids[i];
01668                             if (!kid)
01669                                 break;
01670                             JS_ASSERT(kid->parent == sprop);
01671 
01672                             /*
01673                              * Clear a space in the kids array for possible
01674                              * re-use by InsertPropertyTreeChild.
01675                              */
01676                             chunk->kids[i] = NULL;
01677                             if (!InsertPropertyTreeChild(rt, parent, kid,
01678                                                          chunk)) {
01679                                 /*
01680                                  * This can happen only if we failed to add an
01681                                  * entry to the root property hash table.
01682                                  */
01683                                 JS_ASSERT(!parent);
01684                                 kid->parent = NULL;
01685                             }
01686                         }
01687                         if (!chunk->kids[0]) {
01688                             /* The chunk wasn't reused, so we must free it. */
01689                             DestroyPropTreeKidsChunk(rt, chunk);
01690                         }
01691                     } while ((chunk = nextChunk) != NULL);
01692                 } else {
01693                     kid = kids;
01694                     if (!InsertPropertyTreeChild(rt, parent, kid, freeChunk)) {
01695                         /*
01696                          * This can happen only if we failed to add an entry
01697                          * to the root property hash table.
01698                          */
01699                         JS_ASSERT(!parent);
01700                         kid->parent = NULL;
01701                     }
01702                 }
01703             }
01704 
01705             if (freeChunk && !freeChunk->kids[0]) {
01706                 /* The chunk wasn't reused, so we must free it. */
01707                 DestroyPropTreeKidsChunk(rt, freeChunk);
01708             }
01709 
01710             /* Clear id so we know (above) that sprop is on the freelist. */
01711             sprop->id = JSVAL_NULL;
01712             FREENODE_INSERT(rt->propertyFreeList, sprop);
01713             JS_RUNTIME_UNMETER(rt, livePropTreeNodes);
01714         }
01715 
01716         /* If a contains no live properties, return it to the malloc heap. */
01717         if (liveCount == 0) {
01718             for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
01719                 FREENODE_REMOVE(sprop);
01720             JS_ARENA_DESTROY(&rt->propertyArenaPool, a, ap);
01721         } else {
01722 #ifdef DUMP_SCOPE_STATS
01723             livePropCapacity += limit - (JSScopeProperty *) a->base;
01724             totalLiveCount += liveCount;
01725 #endif
01726             ap = &a->next;
01727         }
01728     }
01729 
01730 #ifdef DUMP_SCOPE_STATS
01731     fprintf(logfp, " arenautil %g%%\n",
01732             (totalLiveCount * 100.0) / livePropCapacity);
01733     fflush(logfp);
01734 #endif
01735 
01736 #ifdef DUMP_PROPERTY_TREE
01737     {
01738         FILE *dumpfp = fopen("/tmp/proptree.dump", "w");
01739         if (dumpfp) {
01740             JSPropertyTreeEntry *pte, *end;
01741 
01742             pte = (JSPropertyTreeEntry *) rt->propertyTreeHash.entryStore;
01743             end = pte + JS_DHASH_TABLE_SIZE(&rt->propertyTreeHash);
01744             while (pte < end) {
01745                 if (pte->child)
01746                     DumpSubtree(pte->child, 0, dumpfp);
01747                 pte++;
01748             }
01749             fclose(dumpfp);
01750         }
01751     }
01752 #endif
01753 }
01754 
01755 JSBool
01756 js_InitPropertyTree(JSRuntime *rt)
01757 {
01758     if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
01759                            sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
01760         rt->propertyTreeHash.ops = NULL;
01761         return JS_FALSE;
01762     }
01763     JS_InitArenaPool(&rt->propertyArenaPool, "properties",
01764                      256 * sizeof(JSScopeProperty), sizeof(void *));
01765     return JS_TRUE;
01766 }
01767 
01768 void
01769 js_FinishPropertyTree(JSRuntime *rt)
01770 {
01771     if (rt->propertyTreeHash.ops) {
01772         JS_DHashTableFinish(&rt->propertyTreeHash);
01773         rt->propertyTreeHash.ops = NULL;
01774     }
01775     JS_FinishArenaPool(&rt->propertyArenaPool);
01776 }