1		/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2		*
3		* ***** BEGIN LICENSE BLOCK *****
4		* Version: MPL 1.1/GPL 2.0/LGPL 2.1
5		*
6		* The contents of this file are subject to the Mozilla Public License Version
7		* 1.1 (the "License"); you may not use this file except in compliance with
8		* the License. You may obtain a copy of the License at
9		* http://www.mozilla.org/MPL/
10		*
11		* Software distributed under the License is distributed on an "AS IS" basis,
12		* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13		* for the specific language governing rights and limitations under the
14		* License.
15		*
16		* The Original Code is Mozilla Communicator client code, released
17		* March 31, 1998.
18		*
19		* The Initial Developer of the Original Code is
20		* Netscape Communications Corporation.
21		* Portions created by the Initial Developer are Copyright (C) 1998
22		* the Initial Developer. All Rights Reserved.
23		*
24		* Contributor(s):
25		*
26		* Alternatively, the contents of this file may be used under the terms of
27		* either of the GNU General Public License Version 2 or later (the "GPL"),
28		* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29		* in which case the provisions of the GPL or the LGPL are applicable instead
30		* of those above. If you wish to allow use of your version of this file only
31		* under the terms of either the GPL or the LGPL, and not to allow others to
32		* use your version of this file under the terms of the MPL, indicate your
33		* decision by deleting the provisions above and replace them with the notice
34		* and other provisions required by the GPL or the LGPL. If you do not delete
35		* the provisions above, a recipient may use your version of this file under
36		* the terms of any one of the MPL, the GPL or the LGPL.
37		*
38		* ***** END LICENSE BLOCK ***** */
39
40		/*
41		* JS symbol tables.
42		*/
43		#include "jsstddef.h"
44		#include <stdlib.h>
45		#include <string.h>
46		#include "jstypes.h"
47		#include "jsarena.h"
48		#include "jsbit.h"
49		#include "jsclist.h"
50		#include "jsdhash.h"
51		#include "jsutil.h" /* Added by JSIFY */
52		#include "jsapi.h"
53		#include "jsatom.h"
54		#include "jscntxt.h"
55		#include "jsdbgapi.h"
56		#include "jslock.h"
57		#include "jsnum.h"
58		#include "jsscope.h"
59		#include "jsstr.h"
60
61		JSScope *
62		js_GetMutableScope(JSContext *cx, JSObject *obj)
63	1228629	{
64	1228629	JSScope *scope, *newscope;
65
66	1228629	scope = OBJ_SCOPE(obj);
67	1228629	JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
68	1228629	if (scope->object == obj)
69	1123732	return scope;
70	104897	newscope = js_NewScope(cx, 0, scope->map.ops, LOCKED_OBJ_GET_CLASS(obj),
71		obj);
72	104897	if (!newscope)
73	0	return NULL;
74	104897	JS_LOCK_SCOPE(cx, newscope);
75	104897	obj->map = js_HoldObjectMap(cx, &newscope->map);
76	104897	scope = (JSScope *) js_DropObjectMap(cx, &scope->map, obj);
77	104897	JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope);
78	104897	return newscope;
79		}
80
81		/*
82		* JSScope uses multiplicative hashing, _a la_ jsdhash.[ch], but specialized
83		* to minimize footprint.  But if a scope has fewer than SCOPE_HASH_THRESHOLD
84		* entries, we use linear search and avoid allocating scope->table.
85		*/
86		#define SCOPE_HASH_THRESHOLD    6
87		#define MIN_SCOPE_SIZE_LOG2     4
88		#define MIN_SCOPE_SIZE          JS_BIT(MIN_SCOPE_SIZE_LOG2)
89		#define SCOPE_TABLE_NBYTES(n)   ((n) * sizeof(JSScopeProperty *))
90
91		static void
92		InitMinimalScope(JSScope *scope)
93	151049	{
94	151049	scope->hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2;
95	151049	scope->entryCount = scope->removedCount = 0;
96	151049	scope->table = NULL;
97	151049	scope->lastProp = NULL;
98		}
99
100		static JSBool
101		CreateScopeTable(JSScope *scope)
102	67235	{
103	67235	int sizeLog2;
104	67235	JSScopeProperty *sprop, **spp;
105
106	67235	JS_ASSERT(!scope->table);
107	67235	JS_ASSERT(scope->lastProp);
108
109	67235	if (scope->entryCount > SCOPE_HASH_THRESHOLD) {
110		/*
111		* Ouch: calloc failed at least once already -- let's try again,
112		* overallocating to hold at least twice the current population.
113		*/
114	0	sizeLog2 = JS_CeilingLog2(2 * scope->entryCount);
115	0	scope->hashShift = JS_DHASH_BITS - sizeLog2;
116		} else {
117	67235	JS_ASSERT(scope->hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2);
118	67235	sizeLog2 = MIN_SCOPE_SIZE_LOG2;
119		}
120
121	67235	scope->table = (JSScopeProperty **)
122		calloc(JS_BIT(sizeLog2), sizeof(JSScopeProperty *));
123	67235	if (!scope->table)
124	0	return JS_FALSE;
125
126	67235	scope->hashShift = JS_DHASH_BITS - sizeLog2;
127	470679	for (sprop = scope->lastProp; sprop; sprop = sprop->parent) {
128	403444	spp = js_SearchScope(scope, sprop->id, JS_TRUE);
129	403444	SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
130		}
131	67235	return JS_TRUE;
132		}
133
134		JSScope *
135		js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
136		JSObject *obj)
137	151049	{
138	151049	JSScope *scope;
139
140	151049	scope = (JSScope *) JS_malloc(cx, sizeof(JSScope));
141	151049	if (!scope)
142	0	return NULL;
143
144	151049	js_InitObjectMap(&scope->map, nrefs, ops, clasp);
145	151049	scope->object = obj;
146	151049	scope->flags = 0;
147	151049	InitMinimalScope(scope);
148
149		#ifdef JS_THREADSAFE
150		scope->ownercx = cx;
151		memset(&scope->lock, 0, sizeof scope->lock);
152
153		/*
154		* Set u.link = NULL, not u.count = 0, in case the target architecture's
155		* null pointer has a non-zero integer representation.
156		*/
157		scope->u.link = NULL;
158
159		#ifdef DEBUG
160		scope->file[0] = scope->file[1] = scope->file[2] = scope->file[3] = NULL;
161		scope->line[0] = scope->line[1] = scope->line[2] = scope->line[3] = 0;
162		#endif
163		#endif
164
165		JS_RUNTIME_METER(cx->runtime, liveScopes);
166		JS_RUNTIME_METER(cx->runtime, totalScopes);
167	151049	return scope;
168		}
169
170		#ifdef DEBUG_SCOPE_COUNT
171		extern void
172		js_unlog_scope(JSScope *scope);
173		#endif
174
175		void
176		js_DestroyScope(JSContext *cx, JSScope *scope)
177	151049	{
178		#ifdef DEBUG_SCOPE_COUNT
179		js_unlog_scope(scope);
180		#endif
181
182		#ifdef JS_THREADSAFE
183		/* Scope must be single-threaded at this point, so set scope->ownercx. */
184		JS_ASSERT(scope->u.count == 0);
185		scope->ownercx = cx;
186		js_FinishLock(&scope->lock);
187		#endif
188	151049	if (scope->table)
189	67235	JS_free(cx, scope->table);
190
191		#ifdef DEBUG
192		JS_LOCK_RUNTIME_VOID(cx->runtime,
193		cx->runtime->liveScopeProps -= scope->entryCount);
194		#endif
195		JS_RUNTIME_UNMETER(cx->runtime, liveScopes);
196	151049	JS_free(cx, scope);
197		}
198
199		#ifdef DEBUG_brendan
200		typedef struct JSScopeStats {
201		jsrefcount          searches;
202		jsrefcount          steps;
203		jsrefcount          hits;
204		jsrefcount          misses;
205		jsrefcount          stepHits;
206		jsrefcount          stepMisses;
207		jsrefcount          adds;
208		jsrefcount          redundantAdds;
209		jsrefcount          addFailures;
210		jsrefcount          changeFailures;
211		jsrefcount          compresses;
212		jsrefcount          grows;
213		jsrefcount          removes;
214		jsrefcount          removeFrees;
215		jsrefcount          uselessRemoves;
216		jsrefcount          shrinks;
217		} JSScopeStats;
218
219		JS_FRIEND_DATA(JSScopeStats) js_scope_stats;
220
221		# define METER(x)       JS_ATOMIC_INCREMENT(&js_scope_stats.x)
222		#else
223		# define METER(x)       /* nothing */
224		#endif
225
226		/*
227		* Double hashing needs the second hash code to be relatively prime to table
228		* size, so we simply make hash2 odd.  The inputs to multiplicative hash are
229		* the golden ratio, expressed as a fixed-point 32 bit fraction, and the int
230		* property index or named property's atom number (observe that most objects
231		* have either no indexed properties, or almost all indexed and a few names,
232		* so collisions between index and atom number are unlikely).
233		*/
234		#define SCOPE_HASH0(id)                 (HASH_ID(id) * JS_GOLDEN_RATIO)
235		#define SCOPE_HASH1(hash0,shift)        ((hash0) >> (shift))
236		#define SCOPE_HASH2(hash0,log2,shift)   ((((hash0) << (log2)) >> (shift)) | 1)
237
238		JS_FRIEND_API(JSScopeProperty **)
239		js_SearchScope(JSScope *scope, jsid id, JSBool adding)
240	4536283	{
241	4536283	JSHashNumber hash0, hash1, hash2;
242	4536283	int hashShift, sizeLog2;
243	4536283	JSScopeProperty *stored, *sprop, **spp, **firstRemoved;
244	4536283	uint32 sizeMask;
245
246		METER(searches);
247	4536283	if (!scope->table) {
248		/* Not enough properties to justify hashing: search from lastProp. */
249	1152025	JS_ASSERT(!SCOPE_HAD_MIDDLE_DELETE(scope));
250	3191787	for (spp = &scope->lastProp; (sprop = *spp); spp = &sprop->parent) {
251	2485472	if (sprop->id == id) {
252		METER(hits);
253	445710	return spp;
254		}
255		}
256		METER(misses);
257	706315	return spp;
258		}
259
260		/* Compute the primary hash address. */
261	3384258	hash0 = SCOPE_HASH0(id);
262	3384258	hashShift = scope->hashShift;
263	3384258	hash1 = SCOPE_HASH1(hash0, hashShift);
264	3384258	spp = scope->table + hash1;
265
266		/* Miss: return space for a new entry. */
267	3384258	stored = *spp;
268	3384258	if (SPROP_IS_FREE(stored)) {
269		METER(misses);
270	1878908	return spp;
271		}
272
273		/* Hit: return entry. */
274	1505350	sprop = SPROP_CLEAR_COLLISION(stored);
275	1505350	if (sprop && sprop->id == id) {
276		METER(hits);
277	789967	return spp;
278		}
279
280		/* Collision: double hash. */
281	715383	sizeLog2 = JS_DHASH_BITS - hashShift;
282	715383	hash2 = SCOPE_HASH2(hash0, sizeLog2, hashShift);
283	715383	sizeMask = JS_BITMASK(sizeLog2);
284
285		/* Save the first removed entry pointer so we can recycle it if adding. */
286	715383	if (SPROP_IS_REMOVED(stored)) {
287	0	firstRemoved = spp;
288		} else {
289	715383	firstRemoved = NULL;
290	715383	if (adding && !SPROP_HAD_COLLISION(stored))
291	272464	SPROP_FLAG_COLLISION(spp, sprop);
292		}
293
294	1253761	for (;;) {
295		METER(steps);
296	1114946	hash1 -= hash2;
297	1114946	hash1 &= sizeMask;
298	1114946	spp = scope->table + hash1;
299
300	1114946	stored = *spp;
301	1114946	if (SPROP_IS_FREE(stored)) {
302		METER(stepMisses);
303	665138	return (adding && firstRemoved) ? firstRemoved : spp;
304		}
305
306	449808	sprop = SPROP_CLEAR_COLLISION(stored);
307	449808	if (sprop && sprop->id == id) {
308		METER(stepHits);
309	50245	return spp;
310		}
311
312	399563	if (SPROP_IS_REMOVED(stored)) {
313	0	if (!firstRemoved)
314	0	firstRemoved = spp;
315		} else {
316	399563	if (adding && !SPROP_HAD_COLLISION(stored))
317	138815	SPROP_FLAG_COLLISION(spp, sprop);
318		}
319		}
320
321		/* NOTREACHED */
322	4536283	return NULL;
323		}
324
325		static JSBool
326		ChangeScope(JSContext *cx, JSScope *scope, int change)
327	49965	{
328	49965	int oldlog2, newlog2;
329	49965	uint32 oldsize, newsize, nbytes;
330	49965	JSScopeProperty **table, **oldtable, **spp, **oldspp, *sprop;
331
332		/* Grow, shrink, or compress by changing scope->table. */
333	49965	oldlog2 = JS_DHASH_BITS - scope->hashShift;
334	49965	newlog2 = oldlog2 + change;
335	49965	oldsize = JS_BIT(oldlog2);
336	49965	newsize = JS_BIT(newlog2);
337	49965	nbytes = SCOPE_TABLE_NBYTES(newsize);
338	49965	table = (JSScopeProperty **) calloc(nbytes, 1);
339	49965	if (!table) {
340	0	JS_ReportOutOfMemory(cx);
341	0	return JS_FALSE;
342		}
343
344		/* Now that we have a new table allocated, update scope members. */
345	49965	scope->hashShift = JS_DHASH_BITS - newlog2;
346	49965	scope->removedCount = 0;
347	49965	oldtable = scope->table;
348	49965	scope->table = table;
349
350		/* Copy only live entries, leaving removed and free ones behind. */
351	867821	for (oldspp = oldtable; oldsize != 0; oldspp++) {
352	817856	sprop = SPROP_FETCH(oldspp);
353	817856	if (sprop) {
354	613392	spp = js_SearchScope(scope, sprop->id, JS_TRUE);
355	613392	JS_ASSERT(SPROP_IS_FREE(*spp));
356	613392	*spp = sprop;
357		}
358	817856	oldsize--;
359		}
360
361		/* Finally, free the old table storage. */
362	49965	JS_free(cx, oldtable);
363	49965	return JS_TRUE;
364		}
365
366		/*
367		* Take care to exclude the mark and duplicate bits, in case we're called from
368		* the GC, or we are searching for a property that has not yet been flagged as
369		* a duplicate when making a duplicate formal parameter.
370		*/
371		#define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_IS_DUPLICATE)
372
373		JS_STATIC_DLL_CALLBACK(JSDHashNumber)
374		js_HashScopeProperty(JSDHashTable *table, const void *key)
375	152552	{
376	152552	const JSScopeProperty *sprop = (const JSScopeProperty *)key;
377	152552	JSDHashNumber hash;
378	152552	JSPropertyOp gsop;
379
380		/* Accumulate from least to most random so the low bits are most random. */
381	152552	hash = 0;
382	152552	gsop = sprop->getter;
383	152552	if (gsop)
384	120243	hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop;
385	152552	gsop = sprop->setter;
386	152552	if (gsop)
387	57514	hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop;
388
389	152552	hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4)
390		^ (sprop->flags & ~SPROP_FLAGS_NOT_MATCHED);
391
392	152552	hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->attrs;
393	152552	hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->shortid;
394	152552	hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->slot;
395	152552	hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->id;
396	152552	return hash;
397		}
398
399		#define SPROP_MATCH(sprop, child)                                             \
400		SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter,  \
401		(child)->slot, (child)->attrs, (child)->flags,         \
402		(child)->shortid)
403
404		#define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs,       \
405		aflags, ashortid)                                  \
406		((sprop)->id == (aid) &&                                                  \
407		SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs,      \
408		aflags, ashortid))
409
410		#define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs,   \
411		aflags, ashortid)                         \
412		((sprop)->getter == (agetter) &&                                          \
413		(sprop)->setter == (asetter) &&                                          \
414		(sprop)->slot == (aslot) &&                                              \
415		(sprop)->attrs == (aattrs) &&                                            \
416		(((sprop)->flags ^ (aflags)) & ~SPROP_FLAGS_NOT_MATCHED) == 0 &&         \
417		(sprop)->shortid == (ashortid))
418
419		JS_STATIC_DLL_CALLBACK(JSBool)
420		js_MatchScopeProperty(JSDHashTable *table,
421		const JSDHashEntryHdr *hdr,
422		const void *key)
423	129359	{
424	129359	const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
425	129359	const JSScopeProperty *sprop = entry->child;
426	129359	const JSScopeProperty *kprop = (const JSScopeProperty *)key;
427
428	129359	return SPROP_MATCH(sprop, kprop);
429		}
430
431		static const JSDHashTableOps PropertyTreeHashOps = {
432		JS_DHashAllocTable,
433		JS_DHashFreeTable,
434		JS_DHashGetKeyStub,
435		js_HashScopeProperty,
436		js_MatchScopeProperty,
437		JS_DHashMoveEntryStub,
438		JS_DHashClearEntryStub,
439		JS_DHashFinalizeStub,
440		NULL
441		};
442
443		/*
444		* A property tree node on rt->propertyFreeList overlays the following prefix
445		* struct on JSScopeProperty.
446		*/
447		typedef struct FreeNode {
448		jsid                id;
449		JSScopeProperty     *next;
450		JSScopeProperty     **prevp;
451		} FreeNode;
452
453		#define FREENODE(sprop) ((FreeNode *) (sprop))
454
455		#define FREENODE_INSERT(list, sprop)                                          \
456		JS_BEGIN_MACRO                                                            \
457		FREENODE(sprop)->next = (list);                                       \
458		FREENODE(sprop)->prevp = &(list);                                     \
459		if (list)                                                             \
460		FREENODE(list)->prevp = &FREENODE(sprop)->next;                   \
461		(list) = (sprop);                                                     \
462		JS_END_MACRO
463
464		#define FREENODE_REMOVE(sprop)                                                \
465		JS_BEGIN_MACRO                                                            \
466		*FREENODE(sprop)->prevp = FREENODE(sprop)->next;                      \
467		if (FREENODE(sprop)->next)                                            \
468		FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp;  \
469		JS_END_MACRO
470
471		/* NB: Called with the runtime lock held. */
472		static JSScopeProperty *
473		NewScopeProperty(JSRuntime *rt)
474	24265	{
475	24265	JSScopeProperty *sprop;
476
477	24265	sprop = rt->propertyFreeList;
478	24265	if (sprop) {
479	0	FREENODE_REMOVE(sprop);
480		} else {
481	24265	JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *,
482		&rt->propertyArenaPool,
483		sizeof(JSScopeProperty));
484	24265	if (!sprop)
485	0	return NULL;
486		}
487
488		JS_RUNTIME_METER(rt, livePropTreeNodes);
489		JS_RUNTIME_METER(rt, totalPropTreeNodes);
490	24265	return sprop;
491		}
492
493		#define CHUNKY_KIDS_TAG         ((jsuword)1)
494		#define KIDS_IS_CHUNKY(kids)    ((jsuword)(kids) & CHUNKY_KIDS_TAG)
495		#define KIDS_TO_CHUNK(kids)     ((PropTreeKidsChunk *)                        \
496		((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
497		#define CHUNK_TO_KIDS(chunk)    ((JSScopeProperty *)                          \
498		((jsuword)(chunk) | CHUNKY_KIDS_TAG))
499		#define MAX_KIDS_PER_CHUNK      10
500
501		typedef struct PropTreeKidsChunk PropTreeKidsChunk;
502
503		struct PropTreeKidsChunk {
504		JSScopeProperty     *kids[MAX_KIDS_PER_CHUNK];
505		PropTreeKidsChunk   *next;
506		};
507
508		static PropTreeKidsChunk *
509		NewPropTreeKidsChunk(JSRuntime *rt)
510	519	{
511	519	PropTreeKidsChunk *chunk;
512
513	519	chunk = calloc(1, sizeof *chunk);
514	519	if (!chunk)
515	0	return NULL;
516	519	JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
517		JS_RUNTIME_METER(rt, propTreeKidsChunks);
518	519	return chunk;
519		}
520
521		static void
522		DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk)
523	519	{
524		JS_RUNTIME_UNMETER(rt, propTreeKidsChunks);
525	519	free(chunk);
526		}
527
528		/* NB: Called with the runtime lock held. */
529		static JSBool
530		InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent,
531		JSScopeProperty *child)
532	46313	{
533	46313	JSPropertyTreeEntry *entry;
534	46313	JSScopeProperty **childp, *kids, *sprop;
535	46313	PropTreeKidsChunk *chunk, **chunkp;
536	46313	uintN i;
537
538	46313	JS_ASSERT(!parent || child->parent != parent);
539
540	46313	if (!parent) {
541	22294	entry = (JSPropertyTreeEntry *)
542		JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD);
543	22294	if (!entry)
544	0	return JS_FALSE;
545	22294	childp = &entry->child;
546	22294	sprop = *childp;
547	22294	if (!sprop) {
548	22209	*childp = child;
549		} else {
550		/*
551		* A "Duplicate child" case.
552		*
553		* We can't do away with child, as at least one live scope entry
554		* still points at it.  What's more, that scope's lastProp chains
555		* through an ancestor line to reach child, and js_Enumerate and
556		* others count on this linkage.  We must leave child out of the
557		* hash table, and not require it to be there when we eventually
558		* GC it (see RemovePropertyTreeChild, below).
559		*
560		* It is necessary to leave the duplicate child out of the hash
561		* table to preserve entry uniqueness.  It is safe to leave the
562		* child out of the hash table (unlike the duplicate child cases
563		* below), because the child's parent link will be null, which
564		* can't dangle.
565		*/
566	24019	JS_ASSERT(sprop != child && SPROP_MATCH(sprop, child));
567		JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
568		}
569		} else {
570	24019	childp = &parent->kids;
571	24019	kids = *childp;
572	24019	if (kids) {
573	1791	if (KIDS_IS_CHUNKY(kids)) {
574	1376	chunk = KIDS_TO_CHUNK(kids);
575	2767	do {
576	23776	for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
577	22281	childp = &chunk->kids[i];
578	22281	sprop = *childp;
579	22281	if (!sprop)
580	1272	goto insert;
581
582	21009	JS_ASSERT(sprop != child);
583	21009	if (SPROP_MATCH(sprop, child)) {
584		/*
585		* Duplicate child, see comment above.  In this
586		* case, we must let the duplicate be inserted at
587		* this level in the tree, so we keep iterating,
588		* looking for an empty slot in which to insert.
589		*/
590	21009	JS_ASSERT(sprop != child);
591		JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
592		}
593		}
594	1495	chunkp = &chunk->next;
595	1495	} while ((chunk = *chunkp) != NULL);
596
597	104	chunk = NewPropTreeKidsChunk(rt);
598	104	if (!chunk)
599	0	return JS_FALSE;
600	104	*chunkp = chunk;
601	104	childp = &chunk->kids[0];
602		} else {
603	415	sprop = kids;
604	415	JS_ASSERT(sprop != child);
605	415	if (SPROP_MATCH(sprop, child)) {
606		/*
607		* Duplicate child, see comment above.  Once again, we
608		* must let duplicates created by deletion pile up in a
609		* kids-chunk-list, in order to find them when sweeping
610		* and thereby avoid dangling parent pointers.
611		*/
612		JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
613		}
614
615	415	chunk = NewPropTreeKidsChunk(rt);
616	415	if (!chunk)
617	0	return JS_FALSE;
618	415	parent->kids = CHUNK_TO_KIDS(chunk);
619	415	chunk->kids[0] = sprop;
620	415	childp = &chunk->kids[1];
621		}
622		}
623		insert:
624	24019	*childp = child;
625		}
626
627	46313	child->parent = parent;
628	46313	return JS_TRUE;
629		}
630
631		/* NB: Called with the runtime lock held. */
632		static void
633		RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child)
634	24265	{
635	24265	JSPropertyTreeEntry *entry;
636	24265	JSScopeProperty *parent, *kids, *kid;
637	24265	PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk;
638	24265	uintN i, j;
639
640	24265	parent = child->parent;
641	24265	if (!parent) {
642		/*
643		* Don't remove child if it is not in rt->propertyTreeHash, but only
644		* matches a root child in the table that has compatible members. See
645		* the "Duplicate child" comments in InsertPropertyTreeChild, above.
646		*/
647	23275	entry = (JSPropertyTreeEntry *)
648		JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_LOOKUP);
649
650	23275	if (entry->child == child)
651	23190	JS_DHashTableRawRemove(&rt->propertyTreeHash, &entry->hdr);
652		} else {
653	990	kids = parent->kids;
654	990	if (KIDS_IS_CHUNKY(kids)) {
655	969	list = chunk = KIDS_TO_CHUNK(kids);
656	969	chunkp = &list;
657
658	2108	do {
659	17967	for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
660	16828	if (chunk->kids[i] == child) {
661	969	lastChunk = chunk;
662	969	if (!lastChunk->next) {
663	759	j = i + 1;
664		} else {
665	210	j = 0;
666	329	do {
667	329	chunkp = &lastChunk->next;
668	329	lastChunk = *chunkp;
669	329	} while (lastChunk->next);
670		}
671	3777	for (; j < MAX_KIDS_PER_CHUNK; j++) {
672	2264	if (!lastChunk->kids[j])
673	860	break;
674		}
675	969	--j;
676	969	if (chunk != lastChunk || j > i)
677	369	chunk->kids[i] = lastChunk->kids[j];
678	969	lastChunk->kids[j] = NULL;
679	969	if (j == 0) {
680	84	*chunkp = NULL;
681	84	if (!list)
682	2	parent->kids = NULL;
683	84	DestroyPropTreeKidsChunk(rt, lastChunk);
684		}
685	84	return;
686		}
687		}
688
689	1139	chunkp = &chunk->next;
690	1139	} while ((chunk = *chunkp) != NULL);
691		} else {
692	21	kid = kids;
693	21	if (kid == child)
694	21	parent->kids = NULL;
695		}
696		}
697		}
698
699		/*
700		* Called *without* the runtime lock held, this function acquires that lock
701		* only when inserting a new child.  Thus there may be races to find or add
702		* a node that result in duplicates.  We expect such races to be rare!
703		*/
704		static JSScopeProperty *
705		GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
706		JSScopeProperty *child)
707	1215821	{
708	1215821	JSRuntime *rt;
709	1215821	JSPropertyTreeEntry *entry;
710	1215821	JSScopeProperty *sprop;
711	1215821	PropTreeKidsChunk *chunk;
712	1215821	uintN i;
713
714	1215821	rt = cx->runtime;
715	1215821	if (!parent) {
716	106983	JS_LOCK_RUNTIME(rt);
717
718	106983	entry = (JSPropertyTreeEntry *)
719		JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD);
720	106983	if (!entry)
721	0	goto out_of_memory;
722
723	106983	sprop = entry->child;
724	106983	if (sprop)
725	106002	goto out;
726		} else {
727		/*
728		* Because chunks are appended at the end and never deleted except by
729		* the GC, we can search without taking the runtime lock.  We may miss
730		* a matching sprop added by another thread, and make a duplicate one,
731		* but that is an unlikely, therefore small, cost.  The property tree
732		* has extremely low fan-out below its root in popular embeddings with
733		* real-world workloads.
734		*
735		* If workload changes so as to increase fan-out significantly below
736		* the property tree root, we'll want to add another tag bit stored in
737		* parent->kids that indicates a JSDHashTable pointer.
738		*/
739	1108838	entry = NULL;
740	1108838	sprop = parent->kids;
741	1108838	if (sprop) {
742	1086624	if (KIDS_IS_CHUNKY(sprop)) {
743	38917	chunk = KIDS_TO_CHUNK(sprop);
744	45121	do {
745	214758	for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
746	208510	sprop = chunk->kids[i];
747	208510	if (!sprop)
748	612	goto not_found;
749
750	207898	if (SPROP_MATCH(sprop, child))
751	38261	return sprop;
752		}
753	6248	} while ((chunk = chunk->next) != NULL);
754		} else {
755	1047707	if (SPROP_MATCH(sprop, child))
756	1047293	return sprop;
757		}
758		}
759
760		not_found:
761	24265	JS_LOCK_RUNTIME(rt);
762		}
763
764	24265	sprop = NewScopeProperty(rt);
765	24265	if (!sprop)
766	0	goto out_of_memory;
767
768	24265	sprop->id = child->id;
769	24265	sprop->getter = child->getter;
770	24265	sprop->setter = child->setter;
771	24265	sprop->slot = child->slot;
772	24265	sprop->attrs = child->attrs;
773	24265	sprop->flags = child->flags;
774	24265	sprop->shortid = child->shortid;
775	24265	sprop->parent = sprop->kids = NULL;
776	24265	if (!parent) {
777	981	entry->child = sprop;
778		} else {
779	23284	if (!InsertPropertyTreeChild(rt, parent, sprop))
780	0	goto out_of_memory;
781		}
782
783		out:
784	130267	JS_UNLOCK_RUNTIME(rt);
785	130267	return sprop;
786
787		out_of_memory:
788	0	JS_UNLOCK_RUNTIME(rt);
789	0	JS_ReportOutOfMemory(cx);
790	0	return NULL;
791		}
792
793		#ifdef DEBUG_notbrendan
794		#define CHECK_ANCESTOR_LINE(scope, sparse)                                    \
795		JS_BEGIN_MACRO                                                            \
796		if ((scope)->table) CheckAncestorLine(scope, sparse);                 \
797		JS_END_MACRO
798
799		static void
800		CheckAncestorLine(JSScope *scope, JSBool sparse)
801		{
802		uint32 size;
803		JSScopeProperty **spp, **start, **end, *ancestorLine, *sprop, *aprop;
804		uint32 entryCount, ancestorCount;
805
806		ancestorLine = SCOPE_LAST_PROP(scope);
807		if (ancestorLine)
808		JS_ASSERT(SCOPE_HAS_PROPERTY(scope, ancestorLine));
809
810		entryCount = 0;
811		size = SCOPE_CAPACITY(scope);
812		start = scope->table;
813		for (spp = start, end = start + size; spp < end; spp++) {
814		sprop = SPROP_FETCH(spp);
815		if (sprop) {
816		entryCount++;
817		for (aprop = ancestorLine; aprop; aprop = aprop->parent) {
818		if (aprop == sprop)
819		break;
820		}
821		JS_ASSERT(aprop);
822		}
823		}
824		JS_ASSERT(entryCount == scope->entryCount);
825
826		ancestorCount = 0;
827		for (sprop = ancestorLine; sprop; sprop = sprop->parent) {
828		if (SCOPE_HAD_MIDDLE_DELETE(scope) &&
829		!SCOPE_HAS_PROPERTY(scope, sprop)) {
830		JS_ASSERT(sparse || (sprop->flags & SPROP_IS_DUPLICATE));
831		continue;
832		}
833		ancestorCount++;
834		}
835		JS_ASSERT(ancestorCount == scope->entryCount);
836		}
837		#else
838		#define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
839		#endif
840
841		static void
842		ReportReadOnlyScope(JSContext *cx, JSScope *scope)
843	0	{
844	0	JSString *str;
845
846	0	str = js_ValueToString(cx, OBJECT_TO_JSVAL(scope->object));
847	0	JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_READ_ONLY,
848		str
849		? JS_GetStringBytes(str)
850		: LOCKED_OBJ_GET_CLASS(scope->object)->name);
851		}
852
853		JSScopeProperty *
854		js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
855		JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
856		uintN attrs, uintN flags, intN shortid)
857	1224579	{
858	1224579	JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
859	1224579	uint32 size, splen, i;
860	1224579	int change;
861
862	1224579	JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
863		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
864
865		/*
866		* You can't add properties to a sealed scope.  But note well that you can
867		* change property attributes in a sealed scope, even though that replaces
868		* a JSScopeProperty * in the scope's hash table -- but no id is added, so
869		* the scope remains sealed.
870		*/
871	1224579	if (SCOPE_IS_SEALED(scope)) {
872	0	ReportReadOnlyScope(cx, scope);
873	0	return NULL;
874		}
875
876		/*
877		* Normalize stub getter and setter values for faster is-stub testing in
878		* the SPROP_CALL_[GS]ETTER macros.
879		*/
880	1224579	if (getter == JS_PropertyStub)
881	147607	getter = NULL;
882	1224579	if (setter == JS_PropertyStub)
883	1154587	setter = NULL;
884
885		/*
886		* Search for id in order to claim its entry, allocating a property tree
887		* node if one doesn't already exist for our parameters.
888		*/
889	1224579	spp = js_SearchScope(scope, id, JS_TRUE);
890	1224579	sprop = overwriting = SPROP_FETCH(spp);
891	1224579	if (!sprop) {
892		/* Check whether we need to grow, if the load factor is >= .75. */
893	1215787	size = SCOPE_CAPACITY(scope);
894	1215787	if (scope->entryCount + scope->removedCount >= size - (size >> 2)) {
895	49965	if (scope->removedCount >= size >> 2) {
896		METER(compresses);
897	0	change = 0;
898		} else {
899		METER(grows);
900	49965	change = 1;
901		}
902	49965	if (!ChangeScope(cx, scope, change) &&
903		scope->entryCount + scope->removedCount == size - 1) {
904		METER(addFailures);
905	0	return NULL;
906		}
907	49965	spp = js_SearchScope(scope, id, JS_TRUE);
908	49965	JS_ASSERT(!SPROP_FETCH(spp));
909		}
910		} else {
911		/* Property exists: js_SearchScope must have returned a valid entry. */
912	8792	JS_ASSERT(!SPROP_IS_REMOVED(*spp));
913
914		/*
915		* If all property members match, this is a redundant add and we can
916		* return early.  If the caller wants to allocate a slot, but doesn't
917		* care which slot, copy sprop->slot into slot so we can match sprop,
918		* if all other members match.
919		*/
920	8792	if (!(attrs & JSPROP_SHARED) &&
921		slot == SPROP_INVALID_SLOT &&
922		SPROP_HAS_VALID_SLOT(sprop, scope)) {
923	8758	slot = sprop->slot;
924		}
925	8792	if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs,
926		flags, shortid)) {
927		METER(redundantAdds);
928	8758	return sprop;
929		}
930
931		/*
932		* Duplicate formal parameters require us to leave the old property
933		* on the ancestor line, so the decompiler can find it, even though
934		* its entry in scope->table is overwritten to point at a new property
935		* descending from the old one.  The SPROP_IS_DUPLICATE flag helps us
936		* cope with the consequent disparity between ancestor line height and
937		* scope->entryCount.
938		*/
939	34	if (flags & SPROP_IS_DUPLICATE) {
940	34	sprop->flags |= SPROP_IS_DUPLICATE;
941		} else {
942		/*
943		* If we are clearing sprop to force an existing property to be
944		* overwritten (apart from a duplicate formal parameter), we must
945		* unlink it from the ancestor line at scope->lastProp, lazily if
946		* sprop is not lastProp.  And we must remove the entry at *spp,
947		* precisely so the lazy "middle delete" fixup code further below
948		* won't find sprop in scope->table, in spite of sprop being on
949		* the ancestor line.
950		*
951		* When we finally succeed in finding or creating a new sprop
952		* and storing its pointer at *spp, we'll use the |overwriting|
953		* local saved when we first looked up id to decide whether we're
954		* indeed creating a new entry, or merely overwriting an existing
955		* property.
956		*/
957	0	if (sprop == SCOPE_LAST_PROP(scope)) {
958	0	do {
959	0	SCOPE_REMOVE_LAST_PROP(scope);
960	0	if (!SCOPE_HAD_MIDDLE_DELETE(scope))
961	0	break;
962	0	sprop = SCOPE_LAST_PROP(scope);
963	0	} while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
964	0	} else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
965		/*
966		* If we have no hash table yet, we need one now.  The middle
967		* delete code is simple-minded that way!
968		*/
969	0	if (!scope->table) {
970	0	if (!CreateScopeTable(scope)) {
971	0	JS_ReportOutOfMemory(cx);
972	0	return NULL;
973		}
974	0	spp = js_SearchScope(scope, id, JS_TRUE);
975	0	sprop = overwriting = SPROP_FETCH(spp);
976		}
977	0	SCOPE_SET_MIDDLE_DELETE(scope);
978		}
979		}
980
981		/*
982		* If we fail later on trying to find or create a new sprop, we will
983		* goto fail_overwrite and restore *spp from |overwriting|.  Note that
984		* we don't bother to keep scope->removedCount in sync, because we'll
985		* fix up *spp and scope->entryCount shortly, no matter how control
986		* flow returns from this function.
987		*/
988	34	if (scope->table)
989	0	SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
990	34	scope->entryCount--;
991		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
992	34	sprop = NULL;
993		}
994
995	1215821	if (!sprop) {
996		/*
997		* If properties were deleted from the middle of the list starting at
998		* scope->lastProp, we may need to fork the property tree and squeeze
999		* all deleted properties out of scope's ancestor line.  Otherwise we
1000		* risk adding a node with the same id as a "middle" node, violating
1001		* the rule that properties along an ancestor line have distinct ids
1002		* (unless flagged SPROP_IS_DUPLICATE).
1003		*/
1004	1215821	if (SCOPE_HAD_MIDDLE_DELETE(scope)) {
1005	0	JS_ASSERT(scope->table);
1006		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1007
1008	0	splen = scope->entryCount;
1009	0	if (splen == 0) {
1010	0	JS_ASSERT(scope->lastProp == NULL);
1011		} else {
1012		/*
1013		* Enumerate live entries in scope->table using a temporary
1014		* vector, by walking the (possibly sparse, due to deletions)
1015		* ancestor line from scope->lastProp.
1016		*/
1017	0	spvec = (JSScopeProperty **)
1018		JS_malloc(cx, SCOPE_TABLE_NBYTES(splen));
1019	0	if (!spvec)
1020	0	goto fail_overwrite;
1021	0	i = splen;
1022	0	sprop = SCOPE_LAST_PROP(scope);
1023	0	JS_ASSERT(sprop);
1024	0	do {
1025		/*
1026		* NB: test SCOPE_GET_PROPERTY, not SCOPE_HAS_PROPERTY --
1027		* the latter insists that sprop->id maps to sprop, while
1028		* the former simply tests whether sprop->id is bound in
1029		* scope.  We must allow for duplicate formal parameters
1030		* along the ancestor line, and fork them as needed.
1031		*/
1032	0	if (!SCOPE_GET_PROPERTY(scope, sprop->id))
1033	0	continue;
1034
1035	0	JS_ASSERT(sprop != overwriting);
1036	0	if (i == 0) {
1037		/*
1038		* If our original splen estimate, scope->entryCount,
1039		* is less than the ancestor line height, there must
1040		* be duplicate formal parameters in this (function
1041		* object) scope.  Count remaining ancestors in order
1042		* to realloc spvec.
1043		*/
1044	0	JSScopeProperty *tmp = sprop;
1045	0	do {
1046	0	if (SCOPE_GET_PROPERTY(scope, tmp->id))
1047	0	i++;
1048	0	} while ((tmp = tmp->parent) != NULL);
1049	0	spp2 = (JSScopeProperty **)
1050		JS_realloc(cx, spvec, SCOPE_TABLE_NBYTES(splen+i));
1051	0	if (!spp2) {
1052	0	JS_free(cx, spvec);
1053	0	goto fail_overwrite;
1054		}
1055
1056	0	spvec = spp2;
1057	0	memmove(spvec + i, spvec, SCOPE_TABLE_NBYTES(splen));
1058	0	splen += i;
1059		}
1060
1061	0	spvec[--i] = sprop;
1062	0	} while ((sprop = sprop->parent) != NULL);
1063	0	JS_ASSERT(i == 0);
1064
1065		/*
1066		* Now loop forward through spvec, forking the property tree
1067		* whenever we see a "parent gap" due to deletions from scope.
1068		* NB: sprop is null on first entry to the loop body.
1069		*/
1070	0	do {
1071	0	if (spvec[i]->parent == sprop) {
1072	0	sprop = spvec[i];
1073		} else {
1074	0	sprop = GetPropertyTreeChild(cx, sprop, spvec[i]);
1075	0	if (!sprop) {
1076	0	JS_free(cx, spvec);
1077	0	goto fail_overwrite;
1078		}
1079
1080	0	spp2 = js_SearchScope(scope, sprop->id, JS_FALSE);
1081	0	JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
1082	0	SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
1083		}
1084	0	} while (++i < splen);
1085	0	JS_free(cx, spvec);
1086
1087		/*
1088		* Now sprop points to the last property in scope, where the
1089		* ancestor line from sprop to the root is dense w.r.t. scope:
1090		* it contains no nodes not mapped by scope->table, apart from
1091		* any stinking ECMA-mandated duplicate formal parameters.
1092		*/
1093	0	scope->lastProp = sprop;
1094		CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1095		JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
1096		}
1097
1098	0	SCOPE_CLR_MIDDLE_DELETE(scope);
1099		}
1100
1101		/*
1102		* Aliases share another property's slot, passed in the |slot| param.
1103		* Shared properties have no slot.  Unshared properties that do not
1104		* alias another property's slot get one here, but may lose it due to
1105		* a JS_ClearScope call.
1106		*/
1107	1215821	if (!(flags & SPROP_IS_ALIAS)) {
1108	1215702	if (attrs & JSPROP_SHARED) {
1109	23052	slot = SPROP_INVALID_SLOT;
1110		} else {
1111		/*
1112		* We may have set slot from a nearly-matching sprop, above.
1113		* If so, we're overwriting that nearly-matching sprop, so we
1114		* can reuse its slot -- we don't need to allocate a new one.
1115		* Callers should therefore pass SPROP_INVALID_SLOT for all
1116		* non-alias, unshared property adds.
1117		*/
1118	1192650	if (slot != SPROP_INVALID_SLOT)
1119	0	JS_ASSERT(overwriting);
1120	1192650	else if (!js_AllocSlot(cx, scope->object, &slot))
1121	0	goto fail_overwrite;
1122		}
1123		}
1124
1125		/*
1126		* Check for a watchpoint on a deleted property; if one exists, change
1127		* setter to js_watch_set.
1128		* XXXbe this could get expensive with lots of watchpoints...
1129		*/
1130	1215821	if (!JS_CLIST_IS_EMPTY(&cx->runtime->watchPointList) &&
1131		js_FindWatchPoint(cx->runtime, scope, id)) {
1132	0	setter = js_WrapWatchedSetter(cx, id, attrs, setter);
1133	0	if (!setter)
1134	0	goto fail_overwrite;
1135		}
1136
1137		/* Find or create a property tree node labeled by our arguments. */
1138	1215821	child.id = id;
1139	1215821	child.getter = getter;
1140	1215821	child.setter = setter;
1141	1215821	child.slot = slot;
1142	1215821	child.attrs = attrs;
1143	1215821	child.flags = flags;
1144	1215821	child.shortid = shortid;
1145	1215821	sprop = GetPropertyTreeChild(cx, scope->lastProp, &child);
1146	1215821	if (!sprop)
1147	0	goto fail_overwrite;
1148
1149		/* Store the tree node pointer in the table entry for id. */
1150	1215821	if (scope->table)
1151	730648	SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
1152	1215821	scope->entryCount++;
1153	1215821	scope->lastProp = sprop;
1154		CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1155	1215821	if (!overwriting) {
1156		JS_RUNTIME_METER(cx->runtime, liveScopeProps);
1157		JS_RUNTIME_METER(cx->runtime, totalScopeProps);
1158		}
1159
1160		/*
1161		* If we reach the hashing threshold, try to allocate scope->table.
1162		* If we can't (a rare event, preceded by swapping to death on most
1163		* modern OSes), stick with linear search rather than whining about
1164		* this little set-back.  Therefore we must test !scope->table and
1165		* scope->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1166		* entry count just reached the threshold.
1167		*/
1168	1215821	if (!scope->table && scope->entryCount >= SCOPE_HASH_THRESHOLD)
1169	67235	(void) CreateScopeTable(scope);
1170		}
1171
1172		METER(adds);
1173	1215821	return sprop;
1174
1175		fail_overwrite:
1176	0	if (overwriting) {
1177		/*
1178		* We may or may not have forked overwriting out of scope's ancestor
1179		* line, so we must check (the alternative is to set a flag above, but
1180		* that hurts the common, non-error case).  If we did fork overwriting
1181		* out, we'll add it back at scope->lastProp.  This means enumeration
1182		* order can change due to a failure to overwrite an id.
1183		* XXXbe very minor incompatibility
1184		*/
1185	0	for (sprop = SCOPE_LAST_PROP(scope); ; sprop = sprop->parent) {
1186	0	if (!sprop) {
1187	0	sprop = SCOPE_LAST_PROP(scope);
1188	0	if (overwriting->parent == sprop) {
1189	0	scope->lastProp = overwriting;
1190		} else {
1191	0	sprop = GetPropertyTreeChild(cx, sprop, overwriting);
1192	0	if (sprop) {
1193	0	JS_ASSERT(sprop != overwriting);
1194	0	scope->lastProp = sprop;
1195		}
1196	0	overwriting = sprop;
1197		}
1198	0	break;
1199		}
1200	0	if (sprop == overwriting)
1201	0	break;
1202		}
1203	0	if (overwriting) {
1204	0	if (scope->table)
1205	0	SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
1206	0	scope->entryCount++;
1207		}
1208		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1209		}
1210		METER(addFailures);
1211	0	return NULL;
1212		}
1213
1214		JSScopeProperty *
1215		js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
1216		JSScopeProperty *sprop, uintN attrs, uintN mask,
1217		JSPropertyOp getter, JSPropertyOp setter)
1218	4050	{
1219	4050	JSScopeProperty child, *newsprop, **spp;
1220
1221		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1222
1223		/* Allow only shared (slot-less) => unshared (slot-full) transition. */
1224	4050	attrs |= sprop->attrs & mask;
1225	4050	JS_ASSERT(!((attrs ^ sprop->attrs) & JSPROP_SHARED) ||
1226		!(attrs & JSPROP_SHARED));
1227	4050	if (getter == JS_PropertyStub)
1228	2792	getter = NULL;
1229	4050	if (setter == JS_PropertyStub)
1230	2792	setter = NULL;
1231	4050	if (sprop->attrs == attrs &&
1232		sprop->getter == getter &&
1233		sprop->setter == setter) {
1234	4050	return sprop;
1235		}
1236
1237	0	child.id = sprop->id;
1238	0	child.getter = getter;
1239	0	child.setter = setter;
1240	0	child.slot = sprop->slot;
1241	0	child.attrs = attrs;
1242	0	child.flags = sprop->flags;
1243	0	child.shortid = sprop->shortid;
1244
1245	0	if (SCOPE_LAST_PROP(scope) == sprop) {
1246		/*
1247		* Optimize the case where the last property added to scope is changed
1248		* to have a different attrs, getter, or setter.  In the last property
1249		* case, we need not fork the property tree.  But since we do not call
1250		* js_AddScopeProperty, we may need to allocate a new slot directly.
1251		*/
1252	0	if ((sprop->attrs & JSPROP_SHARED) && !(attrs & JSPROP_SHARED)) {
1253	0	JS_ASSERT(child.slot == SPROP_INVALID_SLOT);
1254	0	if (!js_AllocSlot(cx, scope->object, &child.slot))
1255	0	return NULL;
1256		}
1257
1258	0	newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
1259	0	if (newsprop) {
1260	0	spp = js_SearchScope(scope, sprop->id, JS_FALSE);
1261	0	JS_ASSERT(SPROP_FETCH(spp) == sprop);
1262
1263	0	if (scope->table)
1264	0	SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
1265	0	scope->lastProp = newsprop;
1266		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1267		}
1268		} else {
1269		/*
1270		* Let js_AddScopeProperty handle this |overwriting| case, including
1271		* the conservation of sprop->slot (if it's valid).  We must not call
1272		* js_RemoveScopeProperty here, it will free a valid sprop->slot and
1273		* js_AddScopeProperty won't re-allocate it.
1274		*/
1275	0	newsprop = js_AddScopeProperty(cx, scope, child.id,
1276		child.getter, child.setter, child.slot,
1277		child.attrs, child.flags, child.shortid);
1278		}
1279
1280		#ifdef DEBUG_brendan
1281		if (!newsprop)
1282		METER(changeFailures);
1283		#endif
1284	0	return newsprop;
1285		}
1286
1287		JSBool
1288		js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id)
1289	0	{
1290	0	JSScopeProperty **spp, *stored, *sprop;
1291	0	uint32 size;
1292
1293	0	JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
1294		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1295	0	if (SCOPE_IS_SEALED(scope)) {
1296	0	ReportReadOnlyScope(cx, scope);
1297	0	return JS_FALSE;
1298		}
1299		METER(removes);
1300
1301	0	spp = js_SearchScope(scope, id, JS_FALSE);
1302	0	stored = *spp;
1303	0	sprop = SPROP_CLEAR_COLLISION(stored);
1304	0	if (!sprop) {
1305		METER(uselessRemoves);
1306	0	return JS_TRUE;
1307		}
1308
1309		/* Convert from a list to a hash so we can handle "middle deletes". */
1310	0	if (!scope->table && sprop != scope->lastProp) {
1311	0	if (!CreateScopeTable(scope)) {
1312	0	JS_ReportOutOfMemory(cx);
1313	0	return JS_FALSE;
1314		}
1315	0	spp = js_SearchScope(scope, id, JS_FALSE);
1316	0	stored = *spp;
1317	0	sprop = SPROP_CLEAR_COLLISION(stored);
1318		}
1319
1320		/* First, if sprop is unshared and not cleared, free its slot number. */
1321	0	if (SPROP_HAS_VALID_SLOT(sprop, scope))
1322	0	js_FreeSlot(cx, scope->object, sprop->slot);
1323
1324		/* Next, remove id by setting its entry to a removed or free sentinel. */
1325	0	if (SPROP_HAD_COLLISION(stored)) {
1326	0	JS_ASSERT(scope->table);
1327	0	*spp = SPROP_REMOVED;
1328	0	scope->removedCount++;
1329		} else {
1330		METER(removeFrees);
1331	0	if (scope->table)
1332	0	*spp = NULL;
1333		}
1334	0	scope->entryCount--;
1335		JS_RUNTIME_UNMETER(cx->runtime, liveScopeProps);
1336
1337		/* Update scope->lastProp directly, or set its deferred update flag. */
1338	0	if (sprop == SCOPE_LAST_PROP(scope)) {
1339	0	do {
1340	0	SCOPE_REMOVE_LAST_PROP(scope);
1341	0	if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1342	0	break;
1343	0	sprop = SCOPE_LAST_PROP(scope);
1344	0	} while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
1345	0	} else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
1346	0	SCOPE_SET_MIDDLE_DELETE(scope);
1347		}
1348		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1349
1350		/* Last, consider shrinking scope's table if its load factor is <= .25. */
1351	0	size = SCOPE_CAPACITY(scope);
1352	0	if (size > MIN_SCOPE_SIZE && scope->entryCount <= size >> 2) {
1353		METER(shrinks);
1354	0	(void) ChangeScope(cx, scope, -1);
1355		}
1356
1357	0	return JS_TRUE;
1358		}
1359
1360		void
1361		js_ClearScope(JSContext *cx, JSScope *scope)
1362	0	{
1363		CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1364		#ifdef DEBUG
1365		JS_LOCK_RUNTIME_VOID(cx->runtime,
1366		cx->runtime->liveScopeProps -= scope->entryCount);
1367		#endif
1368
1369	0	if (scope->table)
1370	0	free(scope->table);
1371	0	SCOPE_CLR_MIDDLE_DELETE(scope);
1372	0	InitMinimalScope(scope);
1373		}
1374
1375		#ifdef DEBUG_brendan
1376
1377		#include <stdio.h>
1378		#include <math.h>
1379
1380		uint32 js_nkids_max;
1381		uint32 js_nkids_sum;
1382		double js_nkids_sqsum;
1383		uint32 js_nkids_hist[11];
1384
1385		static void
1386		MeterKidCount(uintN nkids)
1387		{
1388		if (nkids) {
1389		js_nkids_sum += nkids;
1390		js_nkids_sqsum += (double)nkids * nkids;
1391		if (nkids > js_nkids_max)
1392		js_nkids_max = nkids;
1393		}
1394		js_nkids_hist[JS_MIN(nkids, 10)]++;
1395		}
1396
1397		static void
1398		MeterPropertyTree(JSScopeProperty *node)
1399		{
1400		uintN i, nkids;
1401		JSScopeProperty *kids, *kid;
1402		PropTreeKidsChunk *chunk;
1403
1404		nkids = 0;
1405		kids = node->kids;
1406		if (kids) {
1407		if (KIDS_IS_CHUNKY(kids)) {
1408		for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
1409		for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1410		kid = chunk->kids[i];
1411		if (!kid)
1412		break;
1413		MeterPropertyTree(kid);
1414		nkids++;
1415		}
1416		}
1417		} else {
1418		MeterPropertyTree(kids);
1419		nkids = 1;
1420		}
1421		}
1422
1423		MeterKidCount(nkids);
1424		}
1425
1426		JS_STATIC_DLL_CALLBACK(JSDHashOperator)
1427		js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
1428		void *arg)
1429		{
1430		JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
1431
1432		MeterPropertyTree(entry->child);
1433		return JS_DHASH_NEXT;
1434		}
1435
1436		#endif /* DEBUG_brendan */
1437
1438		void
1439		js_SweepScopeProperties(JSRuntime *rt)
1440	34	{
1441	34	JSArena **ap, *a;
1442	34	JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
1443	34	uintN liveCount;
1444	34	PropTreeKidsChunk *chunk, *nextChunk;
1445	34	uintN i;
1446
1447		#ifdef DEBUG_brendan
1448		uint32 livePropCapacity = 0, totalLiveCount = 0;
1449		static FILE *logfp;
1450		if (!logfp)
1451		logfp = fopen("/tmp/proptree.stats", "a");
1452
1453		MeterKidCount(rt->propertyTreeHash.entryCount);
1454		JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, NULL);
1455
1456		{
1457		double mean = 0., var = 0., sigma = 0.;
1458		double nodesum = rt->livePropTreeNodes;
1459		double kidsum = js_nkids_sum;
1460		if (nodesum > 0 && kidsum >= 0) {
1461		mean = kidsum / nodesum;
1462		var = nodesum * js_nkids_sqsum - kidsum * kidsum;
1463		if (var < 0.0 || nodesum <= 1)
1464		var = 0.0;
1465		else
1466		var /= nodesum * (nodesum - 1);
1467
1468		/* Windows says sqrt(0.0) is "-1.#J" (?!) so we must test. */
1469		sigma = (var != 0.) ? sqrt(var) : 0.;
1470		}
1471
1472		fprintf(logfp,
1473		"props %u nodes %g beta %g meankids %g sigma %g max %u",
1474		rt->liveScopeProps, nodesum, nodesum / rt->liveScopeProps,
1475		mean, sigma, js_nkids_max);
1476		}
1477
1478		fprintf(logfp, " histogram %u %u %u %u %u %u %u %u %u %u %u",
1479		js_nkids_hist[0], js_nkids_hist[1],
1480		js_nkids_hist[2], js_nkids_hist[3],
1481		js_nkids_hist[4], js_nkids_hist[5],
1482		js_nkids_hist[6], js_nkids_hist[7],
1483		js_nkids_hist[8], js_nkids_hist[9],
1484		js_nkids_hist[10]);
1485		js_nkids_sum = js_nkids_max = 0;
1486		js_nkids_sqsum = 0;
1487		memset(js_nkids_hist, 0, sizeof js_nkids_hist);
1488		#endif
1489
1490	34	ap = &rt->propertyArenaPool.first.next;
1491	236	while ((a = *ap) != NULL) {
1492	202	limit = (JSScopeProperty *) a->avail;
1493	202	liveCount = 0;
1494	48732	for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
1495		/* If the id is null, sprop is already on the freelist. */
1496	48530	if (sprop->id == JSVAL_NULL)
1497	1028	continue;
1498
1499		/* If the mark bit is set, sprop is alive, so we skip it. */
1500	47502	if (sprop->flags & SPROP_MARK) {
1501	23237	sprop->flags &= ~SPROP_MARK;
1502	23237	liveCount++;
1503	23237	continue;
1504		}
1505
1506		/* Ok, sprop is garbage to collect: unlink it from its parent. */
1507	24265	RemovePropertyTreeChild(rt, sprop);
1508
1509		/* Take care to reparent all sprop's kids to their grandparent. */
1510	24265	kids = sprop->kids;
1511	24265	if (kids) {
1512	22205	sprop->kids = NULL;
1513	22205	parent = sprop->parent;
1514	22205	if (KIDS_IS_CHUNKY(kids)) {
1515	413	chunk = KIDS_TO_CHUNK(kids);
1516	435	do {
1517	1672	for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1518	1649	kid = chunk->kids[i];
1519	1649	if (!kid)
1520	412	break;
1521	1237	JS_ASSERT(kid->parent == sprop);
1522	1237	InsertPropertyTreeChild(rt, parent, kid);
1523		}
1524	435	nextChunk = chunk->next;
1525	435	DestroyPropTreeKidsChunk(rt, chunk);
1526	435	} while ((chunk = nextChunk) != NULL);
1527		} else {
1528	21792	kid = kids;
1529	21792	InsertPropertyTreeChild(rt, parent, kid);
1530		}
1531		}
1532
1533		/* Clear id so we know (above) that sprop is on the freelist. */
1534	24265	sprop->id = JSVAL_NULL;
1535	24265	FREENODE_INSERT(rt->propertyFreeList, sprop);
1536		JS_RUNTIME_UNMETER(rt, livePropTreeNodes);
1537		}
1538
1539		/* If a contains no live properties, return it to the malloc heap. */
1540	202	if (liveCount == 0) {
1541	24366	for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
1542	24265	FREENODE_REMOVE(sprop);
1543	101	JS_ARENA_DESTROY(&rt->propertyArenaPool, a, ap);
1544		} else {
1545		#ifdef DEBUG_brendan
1546		livePropCapacity += limit - (JSScopeProperty *) a->base;
1547		totalLiveCount += liveCount;
1548		#endif
1549	101	ap = &a->next;
1550		}
1551		}
1552
1553		#ifdef DEBUG_brendan
1554		fprintf(logfp, " arenautil %g%%\n",
1555		(totalLiveCount * 100.) / livePropCapacity);
1556		fflush(logfp);
1557		#endif
1558		}
1559
1560		JSBool
1561		js_InitPropertyTree(JSRuntime *rt)
1562	17	{
1563	17	if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
1564		sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
1565	0	rt->propertyTreeHash.ops = NULL;
1566	0	return JS_FALSE;
1567		}
1568	17	JS_InitArenaPool(&rt->propertyArenaPool, "properties",
1569		256 * sizeof(JSScopeProperty), sizeof(void *));
1570	17	return JS_TRUE;
1571		}
1572
1573		void
1574		js_FinishPropertyTree(JSRuntime *rt)
1575	17	{
1576	17	if (rt->propertyTreeHash.ops) {
1577	17	JS_DHashTableFinish(&rt->propertyTreeHash);
1578	17	rt->propertyTreeHash.ops = NULL;
1579		}
1580	17	JS_FinishArenaPool(&rt->propertyArenaPool);