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

Annotation of /trunk/js/jsscope.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 332 - (hide annotations)
Thu Oct 23 19:03:33 2008 UTC (11 years, 11 months ago) by siliconforks
File size: 67855 byte(s)
Add SpiderMonkey from Firefox 3.1b1.

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


1 siliconforks 332 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2     * vim: set ts=8 sw=4 et tw=78:
3     *
4     * ***** BEGIN LICENSE BLOCK *****
5     * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6     *
7     * The contents of this file are subject to the Mozilla Public License Version
8     * 1.1 (the "License"); you may not use this file except in compliance with
9     * the License. You may obtain a copy of the License at
10     * http://www.mozilla.org/MPL/
11     *
12     * Software distributed under the License is distributed on an "AS IS" basis,
13     * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14     * for the specific language governing rights and limitations under the
15     * License.
16     *
17     * The Original Code is Mozilla Communicator client code, released
18     * March 31, 1998.
19     *
20     * The Initial Developer of the Original Code is
21     * Netscape Communications Corporation.
22     * Portions created by the Initial Developer are Copyright (C) 1998
23     * the Initial Developer. All Rights Reserved.
24     *
25     * Contributor(s):
26     *
27     * Alternatively, the contents of this file may be used under the terms of
28     * either of the GNU General Public License Version 2 or later (the "GPL"),
29     * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30     * in which case the provisions of the GPL or the LGPL are applicable instead
31     * of those above. If you wish to allow use of your version of this file only
32     * under the terms of either the GPL or the LGPL, and not to allow others to
33     * use your version of this file under the terms of the MPL, indicate your
34     * decision by deleting the provisions above and replace them with the notice
35     * and other provisions required by the GPL or the LGPL. If you do not delete
36     * the provisions above, a recipient may use your version of this file under
37     * the terms of any one of the MPL, the GPL or the LGPL.
38     *
39     * ***** END LICENSE BLOCK ***** */
40    
41     /*
42     * JS symbol tables.
43     */
44     #include "jsstddef.h"
45     #include <stdlib.h>
46     #include <string.h>
47     #include "jstypes.h"
48     #include "jsarena.h"
49     #include "jsbit.h"
50     #include "jsclist.h"
51     #include "jsdhash.h"
52     #include "jsutil.h" /* Added by JSIFY */
53     #include "jsapi.h"
54     #include "jsatom.h"
55     #include "jscntxt.h"
56     #include "jsdbgapi.h"
57     #include "jslock.h"
58     #include "jsnum.h"
59     #include "jsscope.h"
60     #include "jsstr.h"
61    
62     JSScope *
63     js_GetMutableScope(JSContext *cx, JSObject *obj)
64     {
65     JSScope *scope, *newscope;
66     JSClass *clasp;
67     uint32 freeslot;
68    
69     scope = OBJ_SCOPE(obj);
70     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
71     if (scope->object == obj)
72     return scope;
73     newscope = js_NewScope(cx, 0, scope->map.ops, LOCKED_OBJ_GET_CLASS(obj),
74     obj);
75     if (!newscope)
76     return NULL;
77     JS_LOCK_SCOPE(cx, newscope);
78     obj->map = js_HoldObjectMap(cx, &newscope->map);
79     JS_ASSERT(newscope->map.freeslot == JSSLOT_FREE(STOBJ_GET_CLASS(obj)));
80     clasp = STOBJ_GET_CLASS(obj);
81     if (clasp->reserveSlots) {
82     freeslot = JSSLOT_FREE(clasp) + clasp->reserveSlots(cx, obj);
83     if (freeslot > STOBJ_NSLOTS(obj))
84     freeslot = STOBJ_NSLOTS(obj);
85     if (newscope->map.freeslot < freeslot)
86     newscope->map.freeslot = freeslot;
87     }
88     scope = (JSScope *) js_DropObjectMap(cx, &scope->map, obj);
89     JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope);
90     return newscope;
91     }
92    
93     /*
94     * JSScope uses multiplicative hashing, _a la_ jsdhash.[ch], but specialized
95     * to minimize footprint. But if a scope has fewer than SCOPE_HASH_THRESHOLD
96     * entries, we use linear search and avoid allocating scope->table.
97     */
98     #define SCOPE_HASH_THRESHOLD 6
99     #define MIN_SCOPE_SIZE_LOG2 4
100     #define MIN_SCOPE_SIZE JS_BIT(MIN_SCOPE_SIZE_LOG2)
101     #define SCOPE_TABLE_NBYTES(n) ((n) * sizeof(JSScopeProperty *))
102    
103     static void
104     InitMinimalScope(JSScope *scope)
105     {
106     scope->shape = 0;
107     scope->hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2;
108     scope->entryCount = scope->removedCount = 0;
109     scope->table = NULL;
110     scope->lastProp = NULL;
111     }
112    
113     static JSBool
114     CreateScopeTable(JSContext *cx, JSScope *scope, JSBool report)
115     {
116     int sizeLog2;
117     JSScopeProperty *sprop, **spp;
118    
119     JS_ASSERT(!scope->table);
120     JS_ASSERT(scope->lastProp);
121    
122     if (scope->entryCount > SCOPE_HASH_THRESHOLD) {
123     /*
124     * Either we're creating a table for a large scope that was populated
125     * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
126     * JSOP_SETPROP; or else calloc failed at least once already. In any
127     * event, let's try to grow, overallocating to hold at least twice the
128     * current population.
129     */
130     sizeLog2 = JS_CeilingLog2(2 * scope->entryCount);
131     scope->hashShift = JS_DHASH_BITS - sizeLog2;
132     } else {
133     JS_ASSERT(scope->hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2);
134     sizeLog2 = MIN_SCOPE_SIZE_LOG2;
135     }
136    
137     scope->table = (JSScopeProperty **)
138     calloc(JS_BIT(sizeLog2), sizeof(JSScopeProperty *));
139     if (!scope->table) {
140     if (report)
141     JS_ReportOutOfMemory(cx);
142     return JS_FALSE;
143     }
144     js_UpdateMallocCounter(cx, JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
145    
146     scope->hashShift = JS_DHASH_BITS - sizeLog2;
147     for (sprop = scope->lastProp; sprop; sprop = sprop->parent) {
148     spp = js_SearchScope(scope, sprop->id, JS_TRUE);
149     SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
150     }
151     return JS_TRUE;
152     }
153    
154     JSScope *
155     js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
156     JSObject *obj)
157     {
158     JSScope *scope;
159    
160     scope = (JSScope *) JS_malloc(cx, sizeof(JSScope));
161     if (!scope)
162     return NULL;
163    
164     js_InitObjectMap(&scope->map, nrefs, ops, clasp);
165     scope->object = obj;
166     scope->flags = 0;
167     InitMinimalScope(scope);
168    
169     #ifdef JS_THREADSAFE
170     js_InitTitle(cx, &scope->title);
171     #endif
172     JS_RUNTIME_METER(cx->runtime, liveScopes);
173     JS_RUNTIME_METER(cx->runtime, totalScopes);
174     return scope;
175     }
176    
177     #ifdef DEBUG_SCOPE_COUNT
178     extern void
179     js_unlog_scope(JSScope *scope);
180     #endif
181    
182     #if defined DEBUG || defined JS_DUMP_PROPTREE_STATS
183     # include "jsprf.h"
184     # define LIVE_SCOPE_METER(cx,expr) JS_LOCK_RUNTIME_VOID(cx->runtime,expr)
185     #else
186     # define LIVE_SCOPE_METER(cx,expr) /* nothing */
187     #endif
188    
189     void
190     js_DestroyScope(JSContext *cx, JSScope *scope)
191     {
192     #ifdef DEBUG_SCOPE_COUNT
193     js_unlog_scope(scope);
194     #endif
195    
196     #ifdef JS_THREADSAFE
197     js_FinishTitle(cx, &scope->title);
198     #endif
199     if (scope->table)
200     JS_free(cx, scope->table);
201    
202     LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= scope->entryCount);
203     JS_RUNTIME_UNMETER(cx->runtime, liveScopes);
204     JS_free(cx, scope);
205     }
206    
207     #ifdef JS_DUMP_PROPTREE_STATS
208     typedef struct JSScopeStats {
209     jsrefcount searches;
210     jsrefcount hits;
211     jsrefcount misses;
212     jsrefcount hashes;
213     jsrefcount steps;
214     jsrefcount stepHits;
215     jsrefcount stepMisses;
216     jsrefcount adds;
217     jsrefcount redundantAdds;
218     jsrefcount addFailures;
219     jsrefcount changeFailures;
220     jsrefcount compresses;
221     jsrefcount grows;
222     jsrefcount removes;
223     jsrefcount removeFrees;
224     jsrefcount uselessRemoves;
225     jsrefcount shrinks;
226     } JSScopeStats;
227    
228     JS_FRIEND_DATA(JSScopeStats) js_scope_stats = {0};
229    
230     # define METER(x) JS_ATOMIC_INCREMENT(&js_scope_stats.x)
231     #else
232     # define METER(x) /* nothing */
233     #endif
234    
235     JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4);
236     JS_STATIC_ASSERT(sizeof(jsid) == JS_BYTES_PER_WORD);
237    
238     #if JS_BYTES_PER_WORD == 4
239     # define HASH_ID(id) ((JSHashNumber)(id))
240     #elif JS_BYTES_PER_WORD == 8
241     # define HASH_ID(id) ((JSHashNumber)(id) ^ (JSHashNumber)((id) >> 32))
242     #else
243     # error "Unsupported configuration"
244     #endif
245    
246     /*
247     * Double hashing needs the second hash code to be relatively prime to table
248     * size, so we simply make hash2 odd. The inputs to multiplicative hash are
249     * the golden ratio, expressed as a fixed-point 32 bit fraction, and the id
250     * itself.
251     */
252     #define SCOPE_HASH0(id) (HASH_ID(id) * JS_GOLDEN_RATIO)
253     #define SCOPE_HASH1(hash0,shift) ((hash0) >> (shift))
254     #define SCOPE_HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
255    
256     JS_FRIEND_API(JSScopeProperty **)
257     js_SearchScope(JSScope *scope, jsid id, JSBool adding)
258     {
259     JSHashNumber hash0, hash1, hash2;
260     int hashShift, sizeLog2;
261     JSScopeProperty *stored, *sprop, **spp, **firstRemoved;
262     uint32 sizeMask;
263    
264     METER(searches);
265     if (!scope->table) {
266     /* Not enough properties to justify hashing: search from lastProp. */
267     JS_ASSERT(!SCOPE_HAD_MIDDLE_DELETE(scope));
268     for (spp = &scope->lastProp; (sprop = *spp); spp = &sprop->parent) {
269     if (sprop->id == id) {
270     METER(hits);
271     return spp;
272     }
273     }
274     METER(misses);
275     return spp;
276     }
277    
278     /* Compute the primary hash address. */
279     METER(hashes);
280     hash0 = SCOPE_HASH0(id);
281     hashShift = scope->hashShift;
282     hash1 = SCOPE_HASH1(hash0, hashShift);
283     spp = scope->table + hash1;
284    
285     /* Miss: return space for a new entry. */
286     stored = *spp;
287     if (SPROP_IS_FREE(stored)) {
288     METER(misses);
289     return spp;
290     }
291    
292     /* Hit: return entry. */
293     sprop = SPROP_CLEAR_COLLISION(stored);
294     if (sprop && sprop->id == id) {
295     METER(hits);
296     return spp;
297     }
298    
299     /* Collision: double hash. */
300     sizeLog2 = JS_DHASH_BITS - hashShift;
301     hash2 = SCOPE_HASH2(hash0, sizeLog2, hashShift);
302     sizeMask = JS_BITMASK(sizeLog2);
303    
304     /* Save the first removed entry pointer so we can recycle it if adding. */
305     if (SPROP_IS_REMOVED(stored)) {
306     firstRemoved = spp;
307     } else {
308     firstRemoved = NULL;
309     if (adding && !SPROP_HAD_COLLISION(stored))
310     SPROP_FLAG_COLLISION(spp, sprop);
311     }
312    
313     for (;;) {
314     METER(steps);
315     hash1 -= hash2;
316     hash1 &= sizeMask;
317     spp = scope->table + hash1;
318    
319     stored = *spp;
320     if (SPROP_IS_FREE(stored)) {
321     METER(stepMisses);
322     return (adding && firstRemoved) ? firstRemoved : spp;
323     }
324    
325     sprop = SPROP_CLEAR_COLLISION(stored);
326     if (sprop && sprop->id == id) {
327     METER(stepHits);
328     return spp;
329     }
330    
331     if (SPROP_IS_REMOVED(stored)) {
332     if (!firstRemoved)
333     firstRemoved = spp;
334     } else {
335     if (adding && !SPROP_HAD_COLLISION(stored))
336     SPROP_FLAG_COLLISION(spp, sprop);
337     }
338     }
339    
340     /* NOTREACHED */
341     return NULL;
342     }
343    
344     static JSBool
345     ChangeScope(JSContext *cx, JSScope *scope, int change)
346     {
347     int oldlog2, newlog2;
348     uint32 oldsize, newsize, nbytes;
349     JSScopeProperty **table, **oldtable, **spp, **oldspp, *sprop;
350    
351     if (!scope->table)
352     return CreateScopeTable(cx, scope, JS_TRUE);
353    
354     /* Grow, shrink, or compress by changing scope->table. */
355     oldlog2 = JS_DHASH_BITS - scope->hashShift;
356     newlog2 = oldlog2 + change;
357     oldsize = JS_BIT(oldlog2);
358     newsize = JS_BIT(newlog2);
359     nbytes = SCOPE_TABLE_NBYTES(newsize);
360     table = (JSScopeProperty **) calloc(nbytes, 1);
361     if (!table) {
362     JS_ReportOutOfMemory(cx);
363     return JS_FALSE;
364     }
365    
366     /* Now that we have a new table allocated, update scope members. */
367     scope->hashShift = JS_DHASH_BITS - newlog2;
368     scope->removedCount = 0;
369     oldtable = scope->table;
370     scope->table = table;
371    
372     /* Treat the above calloc as a JS_malloc, to match CreateScopeTable. */
373     cx->runtime->gcMallocBytes += nbytes;
374    
375     /* Copy only live entries, leaving removed and free ones behind. */
376     for (oldspp = oldtable; oldsize != 0; oldspp++) {
377     sprop = SPROP_FETCH(oldspp);
378     if (sprop) {
379     spp = js_SearchScope(scope, sprop->id, JS_TRUE);
380     JS_ASSERT(SPROP_IS_FREE(*spp));
381     *spp = sprop;
382     }
383     oldsize--;
384     }
385    
386     /* Finally, free the old table storage. */
387     JS_free(cx, oldtable);
388     return JS_TRUE;
389     }
390    
391     /*
392     * Take care to exclude the mark bits in case we're called from the GC.
393     */
394     #define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_FLAG_SHAPE_REGEN)
395    
396     static JSDHashNumber
397     js_HashScopeProperty(JSDHashTable *table, const void *key)
398     {
399     const JSScopeProperty *sprop = (const JSScopeProperty *)key;
400     JSDHashNumber hash;
401     JSPropertyOp gsop;
402    
403     /* Accumulate from least to most random so the low bits are most random. */
404     hash = 0;
405     gsop = sprop->getter;
406     if (gsop)
407     hash = JS_ROTATE_LEFT32(hash, 4) ^ (jsword)gsop;
408     gsop = sprop->setter;
409     if (gsop)
410     hash = JS_ROTATE_LEFT32(hash, 4) ^ (jsword)gsop;
411    
412     hash = JS_ROTATE_LEFT32(hash, 4)
413     ^ (sprop->flags & ~SPROP_FLAGS_NOT_MATCHED);
414    
415     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->attrs;
416     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->shortid;
417     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->slot;
418     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->id;
419     return hash;
420     }
421    
422     #define SPROP_MATCH(sprop, child) \
423     SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter, \
424     (child)->slot, (child)->attrs, (child)->flags, \
425     (child)->shortid)
426    
427     #define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs, \
428     aflags, ashortid) \
429     ((sprop)->id == (aid) && \
430     SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
431     aflags, ashortid))
432    
433     #define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
434     aflags, ashortid) \
435     ((sprop)->getter == (agetter) && \
436     (sprop)->setter == (asetter) && \
437     (sprop)->slot == (aslot) && \
438     (sprop)->attrs == (aattrs) && \
439     (((sprop)->flags ^ (aflags)) & ~SPROP_FLAGS_NOT_MATCHED) == 0 && \
440     (sprop)->shortid == (ashortid))
441    
442     static JSBool
443     js_MatchScopeProperty(JSDHashTable *table,
444     const JSDHashEntryHdr *hdr,
445     const void *key)
446     {
447     const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
448     const JSScopeProperty *sprop = entry->child;
449     const JSScopeProperty *kprop = (const JSScopeProperty *)key;
450    
451     return SPROP_MATCH(sprop, kprop);
452     }
453    
454     static const JSDHashTableOps PropertyTreeHashOps = {
455     JS_DHashAllocTable,
456     JS_DHashFreeTable,
457     js_HashScopeProperty,
458     js_MatchScopeProperty,
459     JS_DHashMoveEntryStub,
460     JS_DHashClearEntryStub,
461     JS_DHashFinalizeStub,
462     NULL
463     };
464    
465     /*
466     * A property tree node on rt->propertyFreeList overlays the following prefix
467     * struct on JSScopeProperty.
468     */
469     typedef struct FreeNode {
470     jsid id;
471     JSScopeProperty *next;
472     JSScopeProperty **prevp;
473     } FreeNode;
474    
475     #define FREENODE(sprop) ((FreeNode *) (sprop))
476    
477     #define FREENODE_INSERT(list, sprop) \
478     JS_BEGIN_MACRO \
479     FREENODE(sprop)->next = (list); \
480     FREENODE(sprop)->prevp = &(list); \
481     if (list) \
482     FREENODE(list)->prevp = &FREENODE(sprop)->next; \
483     (list) = (sprop); \
484     JS_END_MACRO
485    
486     #define FREENODE_REMOVE(sprop) \
487     JS_BEGIN_MACRO \
488     *FREENODE(sprop)->prevp = FREENODE(sprop)->next; \
489     if (FREENODE(sprop)->next) \
490     FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp; \
491     JS_END_MACRO
492    
493     /* NB: Called with rt->gcLock held. */
494     static JSScopeProperty *
495     NewScopeProperty(JSRuntime *rt)
496     {
497     JSScopeProperty *sprop;
498    
499     sprop = rt->propertyFreeList;
500     if (sprop) {
501     FREENODE_REMOVE(sprop);
502     } else {
503     JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *,
504     &rt->propertyArenaPool,
505     sizeof(JSScopeProperty));
506     if (!sprop)
507     return NULL;
508     }
509    
510     JS_RUNTIME_METER(rt, livePropTreeNodes);
511     JS_RUNTIME_METER(rt, totalPropTreeNodes);
512     return sprop;
513     }
514    
515     #define CHUNKY_KIDS_TAG ((jsuword)1)
516     #define KIDS_IS_CHUNKY(kids) ((jsuword)(kids) & CHUNKY_KIDS_TAG)
517     #define KIDS_TO_CHUNK(kids) ((PropTreeKidsChunk *) \
518     ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
519     #define CHUNK_TO_KIDS(chunk) ((JSScopeProperty *) \
520     ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
521     #define MAX_KIDS_PER_CHUNK 10
522     #define CHUNK_HASH_THRESHOLD 30
523    
524     typedef struct PropTreeKidsChunk PropTreeKidsChunk;
525    
526     struct PropTreeKidsChunk {
527     JSScopeProperty *kids[MAX_KIDS_PER_CHUNK];
528     JSDHashTable *table;
529     PropTreeKidsChunk *next;
530     };
531    
532     static PropTreeKidsChunk *
533     NewPropTreeKidsChunk(JSRuntime *rt)
534     {
535     PropTreeKidsChunk *chunk;
536    
537     chunk = (PropTreeKidsChunk *) calloc(1, sizeof *chunk);
538     if (!chunk)
539     return NULL;
540     JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
541     JS_RUNTIME_METER(rt, propTreeKidsChunks);
542     return chunk;
543     }
544    
545     static void
546     DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk)
547     {
548     JS_RUNTIME_UNMETER(rt, propTreeKidsChunks);
549     if (chunk->table)
550     JS_DHashTableDestroy(chunk->table);
551     free(chunk);
552     }
553    
554     /* NB: Called with rt->gcLock held. */
555     static JSBool
556     InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent,
557     JSScopeProperty *child, PropTreeKidsChunk *sweptChunk)
558     {
559     JSDHashTable *table;
560     JSPropertyTreeEntry *entry;
561     JSScopeProperty **childp, *kids, *sprop;
562     PropTreeKidsChunk *chunk, **chunkp;
563     uintN i;
564    
565     JS_ASSERT(!parent || child->parent != parent);
566    
567     if (!parent) {
568     table = &rt->propertyTreeHash;
569     entry = (JSPropertyTreeEntry *)
570     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
571     if (!entry)
572     return JS_FALSE;
573     childp = &entry->child;
574     sprop = *childp;
575     if (!sprop) {
576     *childp = child;
577     } else {
578     /*
579     * A "Duplicate child" case.
580     *
581     * We can't do away with child, as at least one live scope entry
582     * still points at it. What's more, that scope's lastProp chains
583     * through an ancestor line to reach child, and js_Enumerate and
584     * others count on this linkage. We must leave child out of the
585     * hash table, and not require it to be there when we eventually
586     * GC it (see RemovePropertyTreeChild, below).
587     *
588     * It is necessary to leave the duplicate child out of the hash
589     * table to preserve entry uniqueness. It is safe to leave the
590     * child out of the hash table (unlike the duplicate child cases
591     * below), because the child's parent link will be null, which
592     * can't dangle.
593     */
594     JS_ASSERT(sprop != child && SPROP_MATCH(sprop, child));
595     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
596     }
597     } else {
598     childp = &parent->kids;
599     kids = *childp;
600     if (kids) {
601     if (KIDS_IS_CHUNKY(kids)) {
602     chunk = KIDS_TO_CHUNK(kids);
603    
604     table = chunk->table;
605     if (table) {
606     entry = (JSPropertyTreeEntry *)
607     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
608     if (!entry)
609     return JS_FALSE;
610     if (!entry->child) {
611     entry->child = child;
612     while (chunk->next)
613     chunk = chunk->next;
614     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
615     childp = &chunk->kids[i];
616     sprop = *childp;
617     if (!sprop)
618     goto insert;
619     }
620     chunkp = &chunk->next;
621     goto new_chunk;
622     }
623     }
624    
625     do {
626     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
627     childp = &chunk->kids[i];
628     sprop = *childp;
629     if (!sprop)
630     goto insert;
631    
632     JS_ASSERT(sprop != child);
633     if (SPROP_MATCH(sprop, child)) {
634     /*
635     * Duplicate child, see comment above. In this
636     * case, we must let the duplicate be inserted at
637     * this level in the tree, so we keep iterating,
638     * looking for an empty slot in which to insert.
639     */
640     JS_ASSERT(sprop != child);
641     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
642     }
643     }
644     chunkp = &chunk->next;
645     } while ((chunk = *chunkp) != NULL);
646    
647     new_chunk:
648     if (sweptChunk) {
649     chunk = sweptChunk;
650     } else {
651     chunk = NewPropTreeKidsChunk(rt);
652     if (!chunk)
653     return JS_FALSE;
654     }
655     *chunkp = chunk;
656     childp = &chunk->kids[0];
657     } else {
658     sprop = kids;
659     JS_ASSERT(sprop != child);
660     if (SPROP_MATCH(sprop, child)) {
661     /*
662     * Duplicate child, see comment above. Once again, we
663     * must let duplicates created by deletion pile up in a
664     * kids-chunk-list, in order to find them when sweeping
665     * and thereby avoid dangling parent pointers.
666     */
667     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
668     }
669     if (sweptChunk) {
670     chunk = sweptChunk;
671     } else {
672     chunk = NewPropTreeKidsChunk(rt);
673     if (!chunk)
674     return JS_FALSE;
675     }
676     parent->kids = CHUNK_TO_KIDS(chunk);
677     chunk->kids[0] = sprop;
678     childp = &chunk->kids[1];
679     }
680     }
681     insert:
682     *childp = child;
683     }
684    
685     child->parent = parent;
686     return JS_TRUE;
687     }
688    
689     /* NB: Called with rt->gcLock held. */
690     static PropTreeKidsChunk *
691     RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child)
692     {
693     PropTreeKidsChunk *freeChunk;
694     JSScopeProperty *parent, *kids, *kid;
695     JSDHashTable *table;
696     PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk;
697     uintN i, j;
698     JSPropertyTreeEntry *entry;
699    
700     freeChunk = NULL;
701     parent = child->parent;
702     if (!parent) {
703     /*
704     * Don't remove child if it is not in rt->propertyTreeHash, but only
705     * matches a root child in the table that has compatible members. See
706     * the "Duplicate child" comments in InsertPropertyTreeChild, above.
707     */
708     table = &rt->propertyTreeHash;
709     } else {
710     kids = parent->kids;
711     if (KIDS_IS_CHUNKY(kids)) {
712     list = chunk = KIDS_TO_CHUNK(kids);
713     chunkp = &list;
714     table = chunk->table;
715    
716     do {
717     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
718     if (chunk->kids[i] == child) {
719     lastChunk = chunk;
720     if (!lastChunk->next) {
721     j = i + 1;
722     } else {
723     j = 0;
724     do {
725     chunkp = &lastChunk->next;
726     lastChunk = *chunkp;
727     } while (lastChunk->next);
728     }
729     for (; j < MAX_KIDS_PER_CHUNK; j++) {
730     if (!lastChunk->kids[j])
731     break;
732     }
733     --j;
734     if (chunk != lastChunk || j > i)
735     chunk->kids[i] = lastChunk->kids[j];
736     lastChunk->kids[j] = NULL;
737     if (j == 0) {
738     *chunkp = NULL;
739     if (!list)
740     parent->kids = NULL;
741     freeChunk = lastChunk;
742     }
743     goto out;
744     }
745     }
746    
747     chunkp = &chunk->next;
748     } while ((chunk = *chunkp) != NULL);
749     } else {
750     table = NULL;
751     kid = kids;
752     if (kid == child)
753     parent->kids = NULL;
754     }
755     }
756    
757     out:
758     if (table) {
759     entry = (JSPropertyTreeEntry *)
760     JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
761    
762     if (entry->child == child)
763     JS_DHashTableRawRemove(table, &entry->hdr);
764     }
765     return freeChunk;
766     }
767    
768     static JSDHashTable *
769     HashChunks(PropTreeKidsChunk *chunk, uintN n)
770     {
771     JSDHashTable *table;
772     uintN i;
773     JSScopeProperty *sprop;
774     JSPropertyTreeEntry *entry;
775    
776     table = JS_NewDHashTable(&PropertyTreeHashOps, NULL,
777     sizeof(JSPropertyTreeEntry),
778     JS_DHASH_DEFAULT_CAPACITY(n + 1));
779     if (!table)
780     return NULL;
781     do {
782     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
783     sprop = chunk->kids[i];
784     if (!sprop)
785     break;
786     entry = (JSPropertyTreeEntry *)
787     JS_DHashTableOperate(table, sprop, JS_DHASH_ADD);
788     entry->child = sprop;
789     }
790     } while ((chunk = chunk->next) != NULL);
791     return table;
792     }
793    
794     /*
795     * Called without cx->runtime->gcLock held. This function acquires that lock
796     * only when inserting a new child. Thus there may be races to find or add a
797     * node that result in duplicates. We expect such races to be rare!
798     *
799     * We use rt->gcLock, not rt->rtLock, to allow the GC potentially to nest here
800     * under js_GenerateShape.
801     */
802     static JSScopeProperty *
803     GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
804     JSScopeProperty *child)
805     {
806     JSRuntime *rt;
807     JSDHashTable *table;
808     JSPropertyTreeEntry *entry;
809     JSScopeProperty *sprop;
810     PropTreeKidsChunk *chunk;
811     uintN i, n;
812    
813     rt = cx->runtime;
814     if (!parent) {
815     JS_LOCK_GC(rt);
816    
817     table = &rt->propertyTreeHash;
818     entry = (JSPropertyTreeEntry *)
819     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
820     if (!entry)
821     goto out_of_memory;
822    
823     sprop = entry->child;
824     if (sprop)
825     goto out;
826     } else {
827     /*
828     * Because chunks are appended at the end and never deleted except by
829     * the GC, we can search without taking the runtime's GC lock. We may
830     * miss a matching sprop added by another thread, and make a duplicate
831     * one, but that is an unlikely, therefore small, cost. The property
832     * tree has extremely low fan-out below its root in popular embeddings
833     * with real-world workloads.
834     *
835     * Patterns such as defining closures that capture a constructor's
836     * environment as getters or setters on the new object that is passed
837     * in as |this| can significantly increase fan-out below the property
838     * tree root -- see bug 335700 for details.
839     */
840     entry = NULL;
841     sprop = parent->kids;
842     if (sprop) {
843     if (KIDS_IS_CHUNKY(sprop)) {
844     chunk = KIDS_TO_CHUNK(sprop);
845    
846     table = chunk->table;
847     if (table) {
848     JS_LOCK_GC(rt);
849     entry = (JSPropertyTreeEntry *)
850     JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
851     sprop = entry->child;
852     if (sprop) {
853     JS_UNLOCK_GC(rt);
854     return sprop;
855     }
856     goto locked_not_found;
857     }
858    
859     n = 0;
860     do {
861     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
862     sprop = chunk->kids[i];
863     if (!sprop) {
864     n += i;
865     if (n >= CHUNK_HASH_THRESHOLD) {
866     chunk = KIDS_TO_CHUNK(parent->kids);
867     if (!chunk->table) {
868     table = HashChunks(chunk, n);
869     JS_LOCK_GC(rt);
870     if (!table)
871     goto out_of_memory;
872     if (chunk->table)
873     JS_DHashTableDestroy(table);
874     else
875     chunk->table = table;
876     goto locked_not_found;
877     }
878     }
879     goto not_found;
880     }
881    
882     if (SPROP_MATCH(sprop, child))
883     return sprop;
884     }
885     n += MAX_KIDS_PER_CHUNK;
886     } while ((chunk = chunk->next) != NULL);
887     } else {
888     if (SPROP_MATCH(sprop, child))
889     return sprop;
890     }
891     }
892    
893     not_found:
894     JS_LOCK_GC(rt);
895     }
896    
897     locked_not_found:
898     sprop = NewScopeProperty(rt);
899     if (!sprop)
900     goto out_of_memory;
901    
902     sprop->id = child->id;
903     sprop->getter = child->getter;
904     sprop->setter = child->setter;
905     sprop->slot = child->slot;
906     sprop->attrs = child->attrs;
907     sprop->flags = child->flags;
908     sprop->shortid = child->shortid;
909     sprop->parent = sprop->kids = NULL;
910     sprop->shape = js_GenerateShape(cx, JS_TRUE);
911    
912     if (!parent) {
913     entry->child = sprop;
914     } else {
915     if (!InsertPropertyTreeChild(rt, parent, sprop, NULL))
916     goto out_of_memory;
917     }
918    
919     out:
920     JS_UNLOCK_GC(rt);
921     return sprop;
922    
923     out_of_memory:
924     JS_UNLOCK_GC(rt);
925     JS_ReportOutOfMemory(cx);
926     return NULL;
927     }
928    
929     #ifdef DEBUG_notbrendan
930     #define CHECK_ANCESTOR_LINE(scope, sparse) \
931     JS_BEGIN_MACRO \
932     if ((scope)->table) CheckAncestorLine(scope, sparse); \
933     JS_END_MACRO
934    
935     static void
936     CheckAncestorLine(JSScope *scope, JSBool sparse)
937     {
938     uint32 size;
939     JSScopeProperty **spp, **start, **end, *ancestorLine, *sprop, *aprop;
940     uint32 entryCount, ancestorCount;
941    
942     ancestorLine = SCOPE_LAST_PROP(scope);
943     if (ancestorLine)
944     JS_ASSERT(SCOPE_HAS_PROPERTY(scope, ancestorLine));
945    
946     entryCount = 0;
947     size = SCOPE_CAPACITY(scope);
948     start = scope->table;
949     for (spp = start, end = start + size; spp < end; spp++) {
950     sprop = SPROP_FETCH(spp);
951     if (sprop) {
952     entryCount++;
953     for (aprop = ancestorLine; aprop; aprop = aprop->parent) {
954     if (aprop == sprop)
955     break;
956     }
957     JS_ASSERT(aprop);
958     }
959     }
960     JS_ASSERT(entryCount == scope->entryCount);
961    
962     ancestorCount = 0;
963     for (sprop = ancestorLine; sprop; sprop = sprop->parent) {
964     if (SCOPE_HAD_MIDDLE_DELETE(scope) &&
965     !SCOPE_HAS_PROPERTY(scope, sprop)) {
966     JS_ASSERT(sparse);
967     continue;
968     }
969     ancestorCount++;
970     }
971     JS_ASSERT(ancestorCount == scope->entryCount);
972     }
973     #else
974     #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
975     #endif
976    
977     static void
978     ReportReadOnlyScope(JSContext *cx, JSScope *scope)
979     {
980     JSString *str;
981     const char *bytes;
982    
983     str = js_ValueToString(cx, OBJECT_TO_JSVAL(scope->object));
984     if (!str)
985     return;
986     bytes = js_GetStringBytes(cx, str);
987     if (!bytes)
988     return;
989     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_READ_ONLY, bytes);
990     }
991    
992     JSScopeProperty *
993     js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
994     JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
995     uintN attrs, uintN flags, intN shortid)
996     {
997     JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
998     uint32 size, splen, i;
999     int change;
1000     JSTempValueRooter tvr;
1001    
1002     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
1003     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1004    
1005     /*
1006     * You can't add properties to a sealed scope. But note well that you can
1007     * change property attributes in a sealed scope, even though that replaces
1008     * a JSScopeProperty * in the scope's hash table -- but no id is added, so
1009     * the scope remains sealed.
1010     */
1011     if (SCOPE_IS_SEALED(scope)) {
1012     ReportReadOnlyScope(cx, scope);
1013     return NULL;
1014     }
1015    
1016     /*
1017     * Normalize stub getter and setter values for faster is-stub testing in
1018     * the SPROP_CALL_[GS]ETTER macros.
1019     */
1020     if (getter == JS_PropertyStub)
1021     getter = NULL;
1022     if (setter == JS_PropertyStub)
1023     setter = NULL;
1024    
1025     /*
1026     * Search for id in order to claim its entry, allocating a property tree
1027     * node if one doesn't already exist for our parameters.
1028     */
1029     spp = js_SearchScope(scope, id, JS_TRUE);
1030     sprop = overwriting = SPROP_FETCH(spp);
1031     if (!sprop) {
1032     JS_COUNT_OPERATION(cx, JSOW_NEW_PROPERTY);
1033    
1034     /* Check whether we need to grow, if the load factor is >= .75. */
1035     size = SCOPE_CAPACITY(scope);
1036     if (scope->entryCount + scope->removedCount >= size - (size >> 2)) {
1037     if (scope->removedCount >= size >> 2) {
1038     METER(compresses);
1039     change = 0;
1040     } else {
1041     METER(grows);
1042     change = 1;
1043     }
1044     if (!ChangeScope(cx, scope, change) &&
1045     scope->entryCount + scope->removedCount == size - 1) {
1046     METER(addFailures);
1047     return NULL;
1048     }
1049     spp = js_SearchScope(scope, id, JS_TRUE);
1050     JS_ASSERT(!SPROP_FETCH(spp));
1051     }
1052     } else {
1053     /* Property exists: js_SearchScope must have returned a valid entry. */
1054     JS_ASSERT(!SPROP_IS_REMOVED(*spp));
1055    
1056     /*
1057     * If all property members match, this is a redundant add and we can
1058     * return early. If the caller wants to allocate a slot, but doesn't
1059     * care which slot, copy sprop->slot into slot so we can match sprop,
1060     * if all other members match.
1061     */
1062     if (!(attrs & JSPROP_SHARED) &&
1063     slot == SPROP_INVALID_SLOT &&
1064     SPROP_HAS_VALID_SLOT(sprop, scope)) {
1065     slot = sprop->slot;
1066     }
1067     if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs,
1068     flags, shortid)) {
1069     METER(redundantAdds);
1070     return sprop;
1071     }
1072    
1073     /*
1074     * If we are clearing sprop to force an existing property to be
1075     * overwritten (apart from a duplicate formal parameter), we must
1076     * unlink it from the ancestor line at scope->lastProp, lazily if
1077     * sprop is not lastProp. And we must remove the entry at *spp,
1078     * precisely so the lazy "middle delete" fixup code further below
1079     * won't find sprop in scope->table, in spite of sprop being on
1080     * the ancestor line.
1081     *
1082     * When we finally succeed in finding or creating a new sprop
1083     * and storing its pointer at *spp, we'll use the |overwriting|
1084     * local saved when we first looked up id to decide whether we're
1085     * indeed creating a new entry, or merely overwriting an existing
1086     * property.
1087     */
1088     if (sprop == SCOPE_LAST_PROP(scope)) {
1089     do {
1090     SCOPE_REMOVE_LAST_PROP(scope);
1091     if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1092     break;
1093     sprop = SCOPE_LAST_PROP(scope);
1094     } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
1095     } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
1096     /*
1097     * If we have no hash table yet, we need one now. The middle
1098     * delete code is simple-minded that way!
1099     */
1100     if (!scope->table) {
1101     if (!CreateScopeTable(cx, scope, JS_TRUE))
1102     return NULL;
1103     spp = js_SearchScope(scope, id, JS_TRUE);
1104     sprop = overwriting = SPROP_FETCH(spp);
1105     }
1106     SCOPE_SET_MIDDLE_DELETE(scope);
1107     }
1108     SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1109    
1110     /*
1111     * If we fail later on trying to find or create a new sprop, we will
1112     * goto fail_overwrite and restore *spp from |overwriting|. Note that
1113     * we don't bother to keep scope->removedCount in sync, because we'll
1114     * fix up *spp and scope->entryCount shortly, no matter how control
1115     * flow returns from this function.
1116     */
1117     if (scope->table)
1118     SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
1119     scope->entryCount--;
1120     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1121     sprop = NULL;
1122     }
1123    
1124     if (!sprop) {
1125     /*
1126     * If properties were deleted from the middle of the list starting at
1127     * scope->lastProp, we may need to fork the property tree and squeeze
1128     * all deleted properties out of scope's ancestor line. Otherwise we
1129     * risk adding a node with the same id as a "middle" node, violating
1130     * the rule that properties along an ancestor line have distinct ids.
1131     */
1132     if (SCOPE_HAD_MIDDLE_DELETE(scope)) {
1133     JS_ASSERT(scope->table);
1134     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1135    
1136     splen = scope->entryCount;
1137     if (splen == 0) {
1138     JS_ASSERT(scope->lastProp == NULL);
1139     } else {
1140     /*
1141     * Enumerate live entries in scope->table using a temporary
1142     * vector, by walking the (possibly sparse, due to deletions)
1143     * ancestor line from scope->lastProp.
1144     */
1145     spvec = (JSScopeProperty **)
1146     JS_malloc(cx, SCOPE_TABLE_NBYTES(splen));
1147     if (!spvec)
1148     goto fail_overwrite;
1149     i = splen;
1150     sprop = SCOPE_LAST_PROP(scope);
1151     JS_ASSERT(sprop);
1152     do {
1153     /*
1154     * NB: test SCOPE_GET_PROPERTY, not SCOPE_HAS_PROPERTY --
1155     * the latter insists that sprop->id maps to sprop, while
1156     * the former simply tests whether sprop->id is bound in
1157     * scope. We must allow for duplicate formal parameters
1158     * along the ancestor line, and fork them as needed.
1159     */
1160     if (!SCOPE_GET_PROPERTY(scope, sprop->id))
1161     continue;
1162    
1163     JS_ASSERT(sprop != overwriting);
1164     if (i == 0) {
1165     /*
1166     * If our original splen estimate, scope->entryCount,
1167     * is less than the ancestor line height, there must
1168     * be duplicate formal parameters in this (function
1169     * object) scope. Count remaining ancestors in order
1170     * to realloc spvec.
1171     */
1172     JSScopeProperty *tmp = sprop;
1173     do {
1174     if (SCOPE_GET_PROPERTY(scope, tmp->id))
1175     i++;
1176     } while ((tmp = tmp->parent) != NULL);
1177     spp2 = (JSScopeProperty **)
1178     JS_realloc(cx, spvec, SCOPE_TABLE_NBYTES(splen+i));
1179     if (!spp2) {
1180     JS_free(cx, spvec);
1181     goto fail_overwrite;
1182     }
1183    
1184     spvec = spp2;
1185     memmove(spvec + i, spvec, SCOPE_TABLE_NBYTES(splen));
1186     splen += i;
1187     }
1188    
1189     spvec[--i] = sprop;
1190     } while ((sprop = sprop->parent) != NULL);
1191     JS_ASSERT(i == 0);
1192    
1193     /*
1194     * Now loop forward through spvec, forking the property tree
1195     * whenever we see a "parent gap" due to deletions from scope.
1196     * NB: sprop is null on first entry to the loop body.
1197     */
1198     do {
1199     if (spvec[i]->parent == sprop) {
1200     sprop = spvec[i];
1201     } else {
1202     sprop = GetPropertyTreeChild(cx, sprop, spvec[i]);
1203     if (!sprop) {
1204     JS_free(cx, spvec);
1205     goto fail_overwrite;
1206     }
1207    
1208     spp2 = js_SearchScope(scope, sprop->id, JS_FALSE);
1209     JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
1210     SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
1211     }
1212     } while (++i < splen);
1213     JS_free(cx, spvec);
1214    
1215     /*
1216     * Now sprop points to the last property in scope, where the
1217     * ancestor line from sprop to the root is dense w.r.t. scope:
1218     * it contains no nodes not mapped by scope->table, apart from
1219     * any stinking ECMA-mandated duplicate formal parameters.
1220     */
1221     scope->lastProp = sprop;
1222     CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1223     JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
1224     }
1225    
1226     SCOPE_CLR_MIDDLE_DELETE(scope);
1227     }
1228    
1229     /*
1230     * Aliases share another property's slot, passed in the |slot| param.
1231     * Shared properties have no slot. Unshared properties that do not
1232     * alias another property's slot get one here, but may lose it due to
1233     * a JS_ClearScope call.
1234     */
1235     if (!(flags & SPROP_IS_ALIAS)) {
1236     if (attrs & JSPROP_SHARED) {
1237     slot = SPROP_INVALID_SLOT;
1238     } else {
1239     /*
1240     * We may have set slot from a nearly-matching sprop, above.
1241     * If so, we're overwriting that nearly-matching sprop, so we
1242     * can reuse its slot -- we don't need to allocate a new one.
1243     * Similarly, we use a specific slot if provided by the caller.
1244     */
1245     if (slot == SPROP_INVALID_SLOT &&
1246     !js_AllocSlot(cx, scope->object, &slot)) {
1247     goto fail_overwrite;
1248     }
1249     }
1250     }
1251    
1252     /*
1253     * Check for a watchpoint on a deleted property; if one exists, change
1254     * setter to js_watch_set.
1255     * XXXbe this could get expensive with lots of watchpoints...
1256     */
1257     if (!JS_CLIST_IS_EMPTY(&cx->runtime->watchPointList) &&
1258     js_FindWatchPoint(cx->runtime, scope, id)) {
1259     JS_PUSH_TEMP_ROOT_SPROP(cx, overwriting, &tvr);
1260     setter = js_WrapWatchedSetter(cx, id, attrs, setter);
1261     JS_POP_TEMP_ROOT(cx, &tvr);
1262     if (!setter)
1263     goto fail_overwrite;
1264     }
1265    
1266     /* Find or create a property tree node labeled by our arguments. */
1267     child.id = id;
1268     child.getter = getter;
1269     child.setter = setter;
1270     child.slot = slot;
1271     child.attrs = attrs;
1272     child.flags = flags;
1273     child.shortid = shortid;
1274     sprop = GetPropertyTreeChild(cx, scope->lastProp, &child);
1275     if (!sprop)
1276     goto fail_overwrite;
1277    
1278     /*
1279     * The scope's shape defaults to its last property's shape, but may
1280     * be regenerated later as the scope diverges (from the property cache
1281     * point of view) from the structural type associated with sprop.
1282     */
1283     SCOPE_EXTEND_SHAPE(cx, scope, sprop);
1284    
1285     /* Store the tree node pointer in the table entry for id. */
1286     if (scope->table)
1287     SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
1288     scope->entryCount++;
1289     scope->lastProp = sprop;
1290     CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1291     #ifdef DEBUG
1292     if (!overwriting) {
1293     LIVE_SCOPE_METER(cx, ++cx->runtime->liveScopeProps);
1294     JS_RUNTIME_METER(cx->runtime, totalScopeProps);
1295     }
1296     #endif
1297    
1298     /*
1299     * If we reach the hashing threshold, try to allocate scope->table.
1300     * If we can't (a rare event, preceded by swapping to death on most
1301     * modern OSes), stick with linear search rather than whining about
1302     * this little set-back. Therefore we must test !scope->table and
1303     * scope->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1304     * entry count just reached the threshold.
1305     */
1306     if (!scope->table && scope->entryCount >= SCOPE_HASH_THRESHOLD)
1307     (void) CreateScopeTable(cx, scope, JS_FALSE);
1308     }
1309    
1310     METER(adds);
1311     return sprop;
1312    
1313     fail_overwrite:
1314     if (overwriting) {
1315     /*
1316     * We may or may not have forked overwriting out of scope's ancestor
1317     * line, so we must check (the alternative is to set a flag above, but
1318     * that hurts the common, non-error case). If we did fork overwriting
1319     * out, we'll add it back at scope->lastProp. This means enumeration
1320     * order can change due to a failure to overwrite an id.
1321     * XXXbe very minor incompatibility
1322     */
1323     for (sprop = SCOPE_LAST_PROP(scope); ; sprop = sprop->parent) {
1324     if (!sprop) {
1325     sprop = SCOPE_LAST_PROP(scope);
1326     if (overwriting->parent == sprop) {
1327     scope->lastProp = overwriting;
1328     } else {
1329     sprop = GetPropertyTreeChild(cx, sprop, overwriting);
1330     if (sprop) {
1331     JS_ASSERT(sprop != overwriting);
1332     scope->lastProp = sprop;
1333     }
1334     overwriting = sprop;
1335     }
1336     break;
1337     }
1338     if (sprop == overwriting)
1339     break;
1340     }
1341     if (overwriting) {
1342     if (scope->table)
1343     SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
1344     scope->entryCount++;
1345     }
1346     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1347     }
1348     METER(addFailures);
1349     return NULL;
1350     }
1351    
1352     JSScopeProperty *
1353     js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
1354     JSScopeProperty *sprop, uintN attrs, uintN mask,
1355     JSPropertyOp getter, JSPropertyOp setter)
1356     {
1357     JSScopeProperty child, *newsprop, **spp;
1358    
1359     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1360    
1361     /* Allow only shared (slot-less) => unshared (slot-full) transition. */
1362     attrs |= sprop->attrs & mask;
1363     JS_ASSERT(!((attrs ^ sprop->attrs) & JSPROP_SHARED) ||
1364     !(attrs & JSPROP_SHARED));
1365     if (getter == JS_PropertyStub)
1366     getter = NULL;
1367     if (setter == JS_PropertyStub)
1368     setter = NULL;
1369     if (sprop->attrs == attrs &&
1370     sprop->getter == getter &&
1371     sprop->setter == setter) {
1372     return sprop;
1373     }
1374    
1375     child.id = sprop->id;
1376     child.getter = getter;
1377     child.setter = setter;
1378     child.slot = sprop->slot;
1379     child.attrs = attrs;
1380     child.flags = sprop->flags;
1381     child.shortid = sprop->shortid;
1382    
1383     if (SCOPE_LAST_PROP(scope) == sprop) {
1384     /*
1385     * Optimize the case where the last property added to scope is changed
1386     * to have a different attrs, getter, or setter. In the last property
1387     * case, we need not fork the property tree. But since we do not call
1388     * js_AddScopeProperty, we may need to allocate a new slot directly.
1389     */
1390     if ((sprop->attrs & JSPROP_SHARED) && !(attrs & JSPROP_SHARED)) {
1391     JS_ASSERT(child.slot == SPROP_INVALID_SLOT);
1392     if (!js_AllocSlot(cx, scope->object, &child.slot))
1393     return NULL;
1394     }
1395    
1396     newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
1397     if (newsprop) {
1398     spp = js_SearchScope(scope, sprop->id, JS_FALSE);
1399     JS_ASSERT(SPROP_FETCH(spp) == sprop);
1400    
1401     if (scope->table)
1402     SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
1403     scope->lastProp = newsprop;
1404     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1405     }
1406     } else {
1407     /*
1408     * Let js_AddScopeProperty handle this |overwriting| case, including
1409     * the conservation of sprop->slot (if it's valid). We must not call
1410     * js_RemoveScopeProperty here, it will free a valid sprop->slot and
1411     * js_AddScopeProperty won't re-allocate it.
1412     */
1413     newsprop = js_AddScopeProperty(cx, scope, child.id,
1414     child.getter, child.setter, child.slot,
1415     child.attrs, child.flags, child.shortid);
1416     }
1417    
1418     if (newsprop) {
1419     if (scope->shape == sprop->shape)
1420     scope->shape = newsprop->shape;
1421     else
1422     SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1423     }
1424     #ifdef JS_DUMP_PROPTREE_STATS
1425     else
1426     METER(changeFailures);
1427     #endif
1428     return newsprop;
1429     }
1430    
1431     JSBool
1432     js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id)
1433     {
1434     JSScopeProperty **spp, *stored, *sprop;
1435     uint32 size;
1436    
1437     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
1438     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1439     if (SCOPE_IS_SEALED(scope)) {
1440     ReportReadOnlyScope(cx, scope);
1441     return JS_FALSE;
1442     }
1443     METER(removes);
1444    
1445     spp = js_SearchScope(scope, id, JS_FALSE);
1446     stored = *spp;
1447     sprop = SPROP_CLEAR_COLLISION(stored);
1448     if (!sprop) {
1449     METER(uselessRemoves);
1450     return JS_TRUE;
1451     }
1452    
1453     /* Convert from a list to a hash so we can handle "middle deletes". */
1454     if (!scope->table && sprop != scope->lastProp) {
1455     if (!CreateScopeTable(cx, scope, JS_TRUE))
1456     return JS_FALSE;
1457     spp = js_SearchScope(scope, id, JS_FALSE);
1458     stored = *spp;
1459     sprop = SPROP_CLEAR_COLLISION(stored);
1460     }
1461    
1462     /* First, if sprop is unshared and not cleared, free its slot number. */
1463     if (SPROP_HAS_VALID_SLOT(sprop, scope)) {
1464     js_FreeSlot(cx, scope->object, sprop->slot);
1465     JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1466     }
1467    
1468     /* Next, remove id by setting its entry to a removed or free sentinel. */
1469     if (SPROP_HAD_COLLISION(stored)) {
1470     JS_ASSERT(scope->table);
1471     *spp = SPROP_REMOVED;
1472     scope->removedCount++;
1473     } else {
1474     METER(removeFrees);
1475     if (scope->table)
1476     *spp = NULL;
1477     }
1478     scope->entryCount--;
1479     LIVE_SCOPE_METER(cx, --cx->runtime->liveScopeProps);
1480    
1481     /* Update scope->lastProp directly, or set its deferred update flag. */
1482     if (sprop == SCOPE_LAST_PROP(scope)) {
1483     do {
1484     SCOPE_REMOVE_LAST_PROP(scope);
1485     if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1486     break;
1487     sprop = SCOPE_LAST_PROP(scope);
1488     } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
1489     } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
1490     SCOPE_SET_MIDDLE_DELETE(scope);
1491     }
1492     SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1493     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1494    
1495     /* Last, consider shrinking scope's table if its load factor is <= .25. */
1496     size = SCOPE_CAPACITY(scope);
1497     if (size > MIN_SCOPE_SIZE && scope->entryCount <= size >> 2) {
1498     METER(shrinks);
1499     (void) ChangeScope(cx, scope, -1);
1500     }
1501    
1502     return JS_TRUE;
1503     }
1504    
1505     void
1506     js_ClearScope(JSContext *cx, JSScope *scope)
1507     {
1508     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1509     LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= scope->entryCount);
1510    
1511     if (scope->table)
1512     free(scope->table);
1513     SCOPE_CLR_MIDDLE_DELETE(scope);
1514     InitMinimalScope(scope);
1515     JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1516     }
1517    
1518     void
1519     js_TraceId(JSTracer *trc, jsid id)
1520     {
1521     jsval v;
1522    
1523     v = ID_TO_VALUE(id);
1524     JS_CALL_VALUE_TRACER(trc, v, "id");
1525     }
1526    
1527     #ifdef DEBUG
1528     static void
1529     PrintPropertyGetterOrSetter(JSTracer *trc, char *buf, size_t bufsize)
1530     {
1531     JSScopeProperty *sprop;
1532     jsid id;
1533     size_t n;
1534     const char *name;
1535    
1536     JS_ASSERT(trc->debugPrinter == PrintPropertyGetterOrSetter);
1537     sprop = (JSScopeProperty *)trc->debugPrintArg;
1538     id = sprop->id;
1539     name = trc->debugPrintIndex ? js_setter_str : js_getter_str;
1540    
1541     if (JSID_IS_ATOM(id)) {
1542     n = js_PutEscapedString(buf, bufsize - 1,
1543     ATOM_TO_STRING(JSID_TO_ATOM(id)), 0);
1544     if (n < bufsize - 1)
1545     JS_snprintf(buf + n, bufsize - n, " %s", name);
1546     } else if (JSID_IS_INT(sprop->id)) {
1547     JS_snprintf(buf, bufsize, "%d %s", JSID_TO_INT(id), name);
1548     } else {
1549     JS_snprintf(buf, bufsize, "<object> %s", name);
1550     }
1551     }
1552     #endif
1553    
1554    
1555     void
1556     js_TraceScopeProperty(JSTracer *trc, JSScopeProperty *sprop)
1557     {
1558     if (IS_GC_MARKING_TRACER(trc))
1559     sprop->flags |= SPROP_MARK;
1560     TRACE_ID(trc, sprop->id);
1561    
1562     #if JS_HAS_GETTER_SETTER
1563     if (sprop->attrs & (JSPROP_GETTER | JSPROP_SETTER)) {
1564     if (sprop->attrs & JSPROP_GETTER) {
1565     JS_ASSERT(JSVAL_IS_OBJECT((jsval) sprop->getter));
1566     JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, sprop, 0);
1567     JS_CallTracer(trc, JSVAL_TO_OBJECT((jsval) sprop->getter),
1568     JSTRACE_OBJECT);
1569     }
1570     if (sprop->attrs & JSPROP_SETTER) {
1571     JS_ASSERT(JSVAL_IS_OBJECT((jsval) sprop->setter));
1572     JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, sprop, 1);
1573     JS_CallTracer(trc, JSVAL_TO_OBJECT((jsval) sprop->setter),
1574     JSTRACE_OBJECT);
1575     }
1576     }
1577     #endif /* JS_HAS_GETTER_SETTER */
1578     }
1579    
1580     #ifdef JS_DUMP_PROPTREE_STATS
1581    
1582     #include <stdio.h>
1583    
1584     static void
1585     MeterKidCount(JSBasicStats *bs, uintN nkids)
1586     {
1587     JS_BASIC_STATS_ACCUM(bs, nkids);
1588     bs->hist[JS_MIN(nkids, 10)]++;
1589     }
1590    
1591     static void
1592     MeterPropertyTree(JSBasicStats *bs, JSScopeProperty *node)
1593     {
1594     uintN i, nkids;
1595     JSScopeProperty *kids, *kid;
1596     PropTreeKidsChunk *chunk;
1597    
1598     nkids = 0;
1599     kids = node->kids;
1600     if (kids) {
1601     if (KIDS_IS_CHUNKY(kids)) {
1602     for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
1603     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1604     kid = chunk->kids[i];
1605     if (!kid)
1606     break;
1607     MeterPropertyTree(bs, kid);
1608     nkids++;
1609     }
1610     }
1611     } else {
1612     MeterPropertyTree(bs, kids);
1613     nkids = 1;
1614     }
1615     }
1616    
1617     MeterKidCount(bs, nkids);
1618     }
1619    
1620     static JSDHashOperator
1621     js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
1622     void *arg)
1623     {
1624     JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
1625     JSBasicStats *bs = (JSBasicStats *)arg;
1626    
1627     MeterPropertyTree(bs, entry->child);
1628     return JS_DHASH_NEXT;
1629     }
1630    
1631     static void
1632     DumpSubtree(JSContext *cx, JSScopeProperty *sprop, int level, FILE *fp)
1633     {
1634     jsval v;
1635     JSString *str;
1636     JSScopeProperty *kids, *kid;
1637     PropTreeKidsChunk *chunk;
1638     uintN i;
1639    
1640     fprintf(fp, "%*sid ", level, "");
1641     v = ID_TO_VALUE(sprop->id);
1642     if (JSID_IS_INT(sprop->id)) {
1643     fprintf(fp, "%d", JSVAL_TO_INT(v));
1644     } else {
1645     if (JSID_IS_ATOM(sprop->id)) {
1646     str = JSVAL_TO_STRING(v);
1647     } else {
1648     JS_ASSERT(JSID_IS_OBJECT(sprop->id));
1649     str = js_ValueToString(cx, v);
1650     fputs("object ", fp);
1651     }
1652     if (!str)
1653     fputs("<error>", fp);
1654     else
1655     js_FileEscapedString(fp, str, '"');
1656     }
1657    
1658     fprintf(fp, " g/s %p/%p slot %u attrs %x flags %x shortid %d\n",
1659     (void *) sprop->getter, (void *) sprop->setter, sprop->slot,
1660     sprop->attrs, sprop->flags, sprop->shortid);
1661     kids = sprop->kids;
1662     if (kids) {
1663     ++level;
1664     if (KIDS_IS_CHUNKY(kids)) {
1665     chunk = KIDS_TO_CHUNK(kids);
1666     do {
1667     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1668     kid = chunk->kids[i];
1669     if (!kid)
1670     break;
1671     JS_ASSERT(kid->parent == sprop);
1672     DumpSubtree(cx, kid, level, fp);
1673     }
1674     } while ((chunk = chunk->next) != NULL);
1675     } else {
1676     kid = kids;
1677     DumpSubtree(cx, kid, level, fp);
1678     }
1679     }
1680     }
1681    
1682     #endif /* JS_DUMP_PROPTREE_STATS */
1683    
1684     void
1685     js_SweepScopeProperties(JSContext *cx)
1686     {
1687     JSRuntime *rt = cx->runtime;
1688     JSArena **ap, *a;
1689     JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
1690     uintN liveCount;
1691     PropTreeKidsChunk *chunk, *nextChunk, *freeChunk;
1692     uintN i;
1693    
1694     #ifdef JS_DUMP_PROPTREE_STATS
1695     JSBasicStats bs;
1696     uint32 livePropCapacity = 0, totalLiveCount = 0;
1697     static FILE *logfp;
1698     if (!logfp)
1699     logfp = fopen("/tmp/proptree.stats", "w");
1700    
1701     JS_BASIC_STATS_INIT(&bs);
1702     MeterKidCount(&bs, rt->propertyTreeHash.entryCount);
1703     JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, &bs);
1704    
1705     {
1706     double props, nodes, mean, sigma;
1707    
1708     props = rt->liveScopePropsPreSweep;
1709     nodes = rt->livePropTreeNodes;
1710     JS_ASSERT(nodes == bs.sum);
1711     mean = JS_MeanAndStdDevBS(&bs, &sigma);
1712    
1713     fprintf(logfp,
1714     "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
1715     props, nodes, nodes / props, mean, sigma, bs.max);
1716     }
1717    
1718     JS_DumpHistogram(&bs, logfp);
1719     #endif
1720    
1721     ap = &rt->propertyArenaPool.first.next;
1722     while ((a = *ap) != NULL) {
1723     limit = (JSScopeProperty *) a->avail;
1724     liveCount = 0;
1725     for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
1726     /* If the id is null, sprop is already on the freelist. */
1727     if (sprop->id == JSVAL_NULL)
1728     continue;
1729    
1730     /*
1731     * If the mark bit is set, sprop is alive, so clear the mark bit
1732     * and continue the while loop.
1733     *
1734     * Regenerate sprop->shape if it hasn't already been refreshed
1735     * during the mark phase, when live scopes' lastProp members are
1736     * followed to update both scope->shape and lastProp->shape.
1737     */
1738     if (sprop->flags & SPROP_MARK) {
1739     sprop->flags &= ~SPROP_MARK;
1740     if (sprop->flags & SPROP_FLAG_SHAPE_REGEN) {
1741     sprop->flags &= ~SPROP_FLAG_SHAPE_REGEN;
1742     } else {
1743     sprop->shape = ++cx->runtime->shapeGen;
1744     JS_ASSERT(sprop->shape != 0);
1745     }
1746     liveCount++;
1747     continue;
1748     }
1749    
1750     /* Ok, sprop is garbage to collect: unlink it from its parent. */
1751     freeChunk = RemovePropertyTreeChild(rt, sprop);
1752    
1753     /*
1754     * Take care to reparent all sprop's kids to their grandparent.
1755     * InsertPropertyTreeChild can potentially fail for two reasons:
1756     *
1757     * 1. If parent is null, insertion into the root property hash
1758     * table may fail. We are forced to leave the kid out of the
1759     * table (as can already happen with duplicates) but ensure
1760     * that the kid's parent pointer is set to null.
1761     *
1762     * 2. If parent is non-null, allocation of a new KidsChunk can
1763     * fail. To prevent this from happening, we allow sprops's own
1764     * chunks to be reused by the grandparent, which removes the
1765     * need for InsertPropertyTreeChild to malloc a new KidsChunk.
1766     *
1767     * If sprop does not have chunky kids, then we rely on the
1768     * RemovePropertyTreeChild call above (which removed sprop from
1769     * its parent) either leaving one free entry, or else returning
1770     * the now-unused chunk to us so we can reuse it.
1771     *
1772     * We also require the grandparent to have either no kids or else
1773     * chunky kids. A single non-chunky kid would force a new chunk to
1774     * be malloced in some cases (if sprop had a single non-chunky
1775     * kid, or a multiple of MAX_KIDS_PER_CHUNK kids). Note that
1776     * RemovePropertyTreeChild never converts a single-entry chunky
1777     * kid back to a non-chunky kid, so we are assured of correct
1778     * behaviour.
1779     */
1780     kids = sprop->kids;
1781     if (kids) {
1782     sprop->kids = NULL;
1783     parent = sprop->parent;
1784    
1785     /* Assert that grandparent has no kids or chunky kids. */
1786     JS_ASSERT(!parent || !parent->kids ||
1787     KIDS_IS_CHUNKY(parent->kids));
1788     if (KIDS_IS_CHUNKY(kids)) {
1789     chunk = KIDS_TO_CHUNK(kids);
1790     do {
1791     nextChunk = chunk->next;
1792     chunk->next = NULL;
1793     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1794     kid = chunk->kids[i];
1795     if (!kid)
1796     break;
1797     JS_ASSERT(kid->parent == sprop);
1798    
1799     /*
1800     * Clear a space in the kids array for possible
1801     * re-use by InsertPropertyTreeChild.
1802     */
1803     chunk->kids[i] = NULL;
1804     if (!InsertPropertyTreeChild(rt, parent, kid,
1805     chunk)) {
1806     /*
1807     * This can happen only if we failed to add an
1808     * entry to the root property hash table.
1809     */
1810     JS_ASSERT(!parent);
1811     kid->parent = NULL;
1812     }
1813     }
1814     if (!chunk->kids[0]) {
1815     /* The chunk wasn't reused, so we must free it. */
1816     DestroyPropTreeKidsChunk(rt, chunk);
1817     }
1818     } while ((chunk = nextChunk) != NULL);
1819     } else {
1820     kid = kids;
1821     if (!InsertPropertyTreeChild(rt, parent, kid, freeChunk)) {
1822     /*
1823     * This can happen only if we failed to add an entry
1824     * to the root property hash table.
1825     */
1826     JS_ASSERT(!parent);
1827     kid->parent = NULL;
1828     }
1829     }
1830     }
1831    
1832     if (freeChunk && !freeChunk->kids[0]) {
1833     /* The chunk wasn't reused, so we must free it. */
1834     DestroyPropTreeKidsChunk(rt, freeChunk);
1835     }
1836    
1837     /* Clear id so we know (above) that sprop is on the freelist. */
1838     sprop->id = JSVAL_NULL;
1839     FREENODE_INSERT(rt->propertyFreeList, sprop);
1840     JS_RUNTIME_UNMETER(rt, livePropTreeNodes);
1841     }
1842    
1843     /* If a contains no live properties, return it to the malloc heap. */
1844     if (liveCount == 0) {
1845     for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
1846     FREENODE_REMOVE(sprop);
1847     JS_ARENA_DESTROY(&rt->propertyArenaPool, a, ap);
1848     } else {
1849     #ifdef JS_DUMP_PROPTREE_STATS
1850     livePropCapacity += limit - (JSScopeProperty *) a->base;
1851     totalLiveCount += liveCount;
1852     #endif
1853     ap = &a->next;
1854     }
1855     }
1856    
1857     #ifdef JS_DUMP_PROPTREE_STATS
1858     fprintf(logfp, "arenautil %g%%\n",
1859     (totalLiveCount && livePropCapacity)
1860     ? (totalLiveCount * 100.0) / livePropCapacity
1861     : 0.0);
1862    
1863     #define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
1864    
1865     fprintf(logfp, "Scope search stats:\n"
1866     " searches: %6u\n"
1867     " hits: %6u %5.2f%% of searches\n"
1868     " misses: %6u %5.2f%%\n"
1869     " hashes: %6u %5.2f%%\n"
1870     " steps: %6u %5.2f%% %5.2f%% of hashes\n"
1871     " stepHits: %6u %5.2f%% %5.2f%%\n"
1872     " stepMisses: %6u %5.2f%% %5.2f%%\n"
1873     " adds: %6u\n"
1874     " redundantAdds: %6u\n"
1875     " addFailures: %6u\n"
1876     " changeFailures: %6u\n"
1877     " compresses: %6u\n"
1878     " grows: %6u\n"
1879     " removes: %6u\n"
1880     " removeFrees: %6u\n"
1881     " uselessRemoves: %6u\n"
1882     " shrinks: %6u\n",
1883     js_scope_stats.searches,
1884     js_scope_stats.hits, RATE(hits, searches),
1885     js_scope_stats.misses, RATE(misses, searches),
1886     js_scope_stats.hashes, RATE(hashes, searches),
1887     js_scope_stats.steps, RATE(steps, searches), RATE(steps, hashes),
1888     js_scope_stats.stepHits,
1889     RATE(stepHits, searches), RATE(stepHits, hashes),
1890     js_scope_stats.stepMisses,
1891     RATE(stepMisses, searches), RATE(stepMisses, hashes),
1892     js_scope_stats.adds,
1893     js_scope_stats.redundantAdds,
1894     js_scope_stats.addFailures,
1895     js_scope_stats.changeFailures,
1896     js_scope_stats.compresses,
1897     js_scope_stats.grows,
1898     js_scope_stats.removes,
1899     js_scope_stats.removeFrees,
1900     js_scope_stats.uselessRemoves,
1901     js_scope_stats.shrinks);
1902    
1903     #undef RATE
1904    
1905     fflush(logfp);
1906     #endif
1907    
1908     #ifdef DUMP_PROPERTY_TREE
1909     {
1910     FILE *dumpfp = fopen("/tmp/proptree.dump", "w");
1911     if (dumpfp) {
1912     JSPropertyTreeEntry *pte, *end;
1913    
1914     pte = (JSPropertyTreeEntry *) rt->propertyTreeHash.entryStore;
1915     end = pte + JS_DHASH_TABLE_SIZE(&rt->propertyTreeHash);
1916     while (pte < end) {
1917     if (pte->child)
1918     DumpSubtree(cx, pte->child, 0, dumpfp);
1919     pte++;
1920     }
1921     fclose(dumpfp);
1922     }
1923     }
1924     #endif
1925     }
1926    
1927     JSBool
1928     js_InitPropertyTree(JSRuntime *rt)
1929     {
1930     if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
1931     sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
1932     rt->propertyTreeHash.ops = NULL;
1933     return JS_FALSE;
1934     }
1935     JS_INIT_ARENA_POOL(&rt->propertyArenaPool, "properties",
1936     256 * sizeof(JSScopeProperty), sizeof(void *), NULL);
1937     return JS_TRUE;
1938     }
1939    
1940     void
1941     js_FinishPropertyTree(JSRuntime *rt)
1942     {
1943     if (rt->propertyTreeHash.ops) {
1944     JS_DHashTableFinish(&rt->propertyTreeHash);
1945     rt->propertyTreeHash.ops = NULL;
1946     }
1947     JS_FinishArenaPool(&rt->propertyArenaPool);
1948     }

  ViewVC Help
Powered by ViewVC 1.1.24