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