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

Annotation of /trunk/js/jsarray.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 507 - (hide annotations)
Sun Jan 10 07:23:34 2010 UTC (12 years, 5 months ago) by siliconforks
File size: 110776 byte(s)
Update SpiderMonkey from Firefox 3.6rc1.

1 siliconforks 507 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 siliconforks 332 * vim: set sw=4 ts=8 et tw=78:
3     *
4     * ***** BEGIN LICENSE BLOCK *****
5     * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6     *
7     * The contents of this file are subject to the Mozilla Public License Version
8     * 1.1 (the "License"); you may not use this file except in compliance with
9     * the License. You may obtain a copy of the License at
10     * http://www.mozilla.org/MPL/
11     *
12     * Software distributed under the License is distributed on an "AS IS" basis,
13     * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14     * for the specific language governing rights and limitations under the
15     * License.
16     *
17     * The Original Code is Mozilla Communicator client code, released
18     * March 31, 1998.
19     *
20     * The Initial Developer of the Original Code is
21     * Netscape Communications Corporation.
22     * Portions created by the Initial Developer are Copyright (C) 1998
23     * the Initial Developer. All Rights Reserved.
24     *
25     * Contributor(s):
26     *
27     * Alternatively, the contents of this file may be used under the terms of
28     * either of the GNU General Public License Version 2 or later (the "GPL"),
29     * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30     * in which case the provisions of the GPL or the LGPL are applicable instead
31     * of those above. If you wish to allow use of your version of this file only
32     * under the terms of either the GPL or the LGPL, and not to allow others to
33     * use your version of this file under the terms of the MPL, indicate your
34     * decision by deleting the provisions above and replace them with the notice
35     * and other provisions required by the GPL or the LGPL. If you do not delete
36     * the provisions above, a recipient may use your version of this file under
37     * the terms of any one of the MPL, the GPL or the LGPL.
38     *
39     * ***** END LICENSE BLOCK ***** */
40    
41     /*
42     * JS array class.
43     *
44 siliconforks 460 * Array objects begin as "dense" arrays, optimized for index-only property
45 siliconforks 332 * access over a vector of slots (obj->dslots) with high load factor. Array
46     * methods optimize for denseness by testing that the object's class is
47     * &js_ArrayClass, and can then directly manipulate the slots for efficiency.
48     *
49     * We track these pieces of metadata for arrays in dense mode:
50     * - the array's length property as a uint32, in JSSLOT_ARRAY_LENGTH,
51     * - the number of indices that are filled (non-holes), in JSSLOT_ARRAY_COUNT,
52 siliconforks 460 * - the net number of slots starting at dslots (capacity), in dslots[-1] if
53 siliconforks 332 * dslots is non-NULL.
54     *
55     * In dense mode, holes in the array are represented by JSVAL_HOLE. The final
56 siliconforks 460 * slot in fslots is unused.
57 siliconforks 332 *
58 siliconforks 460 * NB: the capacity and length of a dense array are entirely unrelated! The
59     * length may be greater than, less than, or equal to the capacity. See
60     * array_length_setter for an explanation of how the first, most surprising
61     * case may occur.
62     *
63 siliconforks 332 * Arrays are converted to use js_SlowArrayClass when any of these conditions
64     * are met:
65 siliconforks 460 * - the load factor (COUNT / capacity) is less than 0.25, and there are
66 siliconforks 332 * more than MIN_SPARSE_INDEX slots total
67 siliconforks 460 * - a property is set that is not indexed (and not "length"); or
68     * - a property is defined that has non-default property attributes.
69 siliconforks 332 *
70 siliconforks 460 * Dense arrays do not track property creation order, so unlike other native
71     * objects and slow arrays, enumerating an array does not necessarily visit the
72     * properties in the order they were created. We could instead maintain the
73     * scope to track property enumeration order, but still use the fast slot
74     * access. That would have the same memory cost as just using a
75     * js_SlowArrayClass, but have the same performance characteristics as a dense
76     * array for slot accesses, at some cost in code complexity.
77 siliconforks 332 */
78     #include <stdlib.h>
79     #include <string.h>
80     #include "jstypes.h"
81 siliconforks 507 #include "jsstdint.h"
82 siliconforks 332 #include "jsutil.h" /* Added by JSIFY */
83     #include "jsapi.h"
84     #include "jsarray.h"
85     #include "jsatom.h"
86     #include "jsbit.h"
87     #include "jsbool.h"
88 siliconforks 507 #include "jstracer.h"
89 siliconforks 399 #include "jsbuiltins.h"
90 siliconforks 332 #include "jscntxt.h"
91     #include "jsversion.h"
92     #include "jsdbgapi.h" /* for js_TraceWatchPoints */
93     #include "jsdtoa.h"
94     #include "jsfun.h"
95     #include "jsgc.h"
96     #include "jsinterp.h"
97     #include "jslock.h"
98     #include "jsnum.h"
99     #include "jsobj.h"
100     #include "jsscope.h"
101     #include "jsstr.h"
102     #include "jsstaticcheck.h"
103 siliconforks 507 #include "jsvector.h"
104 siliconforks 332
105 siliconforks 507 #include "jsatominlines.h"
106    
107 siliconforks 332 /* 2^32 - 1 as a number and a string */
108     #define MAXINDEX 4294967295u
109     #define MAXSTR "4294967295"
110    
111     /* Small arrays are dense, no matter what. */
112 siliconforks 460 #define MIN_SPARSE_INDEX 256
113 siliconforks 332
114 siliconforks 460 static inline bool
115     INDEX_TOO_BIG(jsuint index)
116     {
117     return index > JS_BIT(29) - 1;
118     }
119    
120 siliconforks 332 #define INDEX_TOO_SPARSE(array, index) \
121     (INDEX_TOO_BIG(index) || \
122 siliconforks 460 ((index) > js_DenseArrayCapacity(array) && (index) >= MIN_SPARSE_INDEX && \
123 siliconforks 332 (index) > (uint32)((array)->fslots[JSSLOT_ARRAY_COUNT] + 1) * 4))
124    
125     JS_STATIC_ASSERT(sizeof(JSScopeProperty) > 4 * sizeof(jsval));
126    
127     #define ENSURE_SLOW_ARRAY(cx, obj) \
128     (OBJ_GET_CLASS(cx, obj) == &js_SlowArrayClass || js_MakeArraySlow(cx, obj))
129    
130     /*
131     * Determine if the id represents an array index or an XML property index.
132     *
133     * An id is an array index according to ECMA by (15.4):
134     *
135     * "Array objects give special treatment to a certain class of property names.
136     * A property name P (in the form of a string value) is an array index if and
137     * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
138     * to 2^32-1."
139     *
140     * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
141     * except that by using signed 32-bit integers we miss the top half of the
142     * valid range. This function checks the string representation itself; note
143     * that calling a standard conversion routine might allow strings such as
144     * "08" or "4.0" as array indices, which they are not.
145     */
146     JSBool
147     js_IdIsIndex(jsval id, jsuint *indexp)
148     {
149     JSString *str;
150     jschar *cp;
151    
152     if (JSVAL_IS_INT(id)) {
153     jsint i;
154     i = JSVAL_TO_INT(id);
155     if (i < 0)
156     return JS_FALSE;
157     *indexp = (jsuint)i;
158     return JS_TRUE;
159     }
160    
161     /* NB: id should be a string, but jsxml.c may call us with an object id. */
162     if (!JSVAL_IS_STRING(id))
163     return JS_FALSE;
164    
165     str = JSVAL_TO_STRING(id);
166 siliconforks 507 cp = str->chars();
167     if (JS7_ISDEC(*cp) && str->length() < sizeof(MAXSTR)) {
168 siliconforks 332 jsuint index = JS7_UNDEC(*cp++);
169     jsuint oldIndex = 0;
170     jsuint c = 0;
171     if (index != 0) {
172     while (JS7_ISDEC(*cp)) {
173     oldIndex = index;
174     c = JS7_UNDEC(*cp);
175     index = 10*index + c;
176     cp++;
177     }
178     }
179    
180     /* Ensure that all characters were consumed and we didn't overflow. */
181     if (*cp == 0 &&
182     (oldIndex < (MAXINDEX / 10) ||
183     (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
184     {
185     *indexp = index;
186     return JS_TRUE;
187     }
188     }
189     return JS_FALSE;
190     }
191    
192     static jsuint
193     ValueIsLength(JSContext *cx, jsval* vp)
194     {
195     jsint i;
196     jsdouble d;
197     jsuint length;
198    
199     if (JSVAL_IS_INT(*vp)) {
200     i = JSVAL_TO_INT(*vp);
201     if (i < 0)
202     goto error;
203     return (jsuint) i;
204     }
205    
206     d = js_ValueToNumber(cx, vp);
207     if (JSVAL_IS_NULL(*vp))
208     goto error;
209    
210     if (JSDOUBLE_IS_NaN(d))
211     goto error;
212     length = (jsuint) d;
213     if (d != (jsdouble) length)
214     goto error;
215     return length;
216    
217     error:
218     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
219     JSMSG_BAD_ARRAY_LENGTH);
220     *vp = JSVAL_NULL;
221     return 0;
222     }
223    
224     JSBool
225     js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
226     {
227     if (OBJ_IS_ARRAY(cx, obj)) {
228     *lengthp = obj->fslots[JSSLOT_ARRAY_LENGTH];
229     return JS_TRUE;
230     }
231    
232 siliconforks 507 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
233     if (!obj->getProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.lengthAtom), tvr.addr()))
234     return JS_FALSE;
235    
236     if (JSVAL_IS_INT(tvr.value())) {
237     *lengthp = jsuint(jsint(JSVAL_TO_INT(tvr.value()))); /* jsuint cast does ToUint32 */
238     return JS_TRUE;
239 siliconforks 332 }
240 siliconforks 507
241     *lengthp = js_ValueToECMAUint32(cx, tvr.addr());
242     return !JSVAL_IS_NULL(tvr.value());
243 siliconforks 332 }
244    
245     static JSBool
246 siliconforks 460 IndexToValue(JSContext *cx, jsdouble index, jsval *vp)
247 siliconforks 332 {
248 siliconforks 460 return js_NewWeaklyRootedNumber(cx, index, vp);
249 siliconforks 332 }
250    
251     JSBool JS_FASTCALL
252     js_IndexToId(JSContext *cx, jsuint index, jsid *idp)
253     {
254     JSString *str;
255    
256     if (index <= JSVAL_INT_MAX) {
257     *idp = INT_TO_JSID(index);
258     return JS_TRUE;
259     }
260     str = js_NumberToString(cx, index);
261     if (!str)
262     return JS_FALSE;
263     return js_ValueToStringId(cx, STRING_TO_JSVAL(str), idp);
264     }
265    
266     static JSBool
267     BigIndexToId(JSContext *cx, JSObject *obj, jsuint index, JSBool createAtom,
268     jsid *idp)
269     {
270     jschar buf[10], *start;
271     JSClass *clasp;
272     JSAtom *atom;
273     JS_STATIC_ASSERT((jsuint)-1 == 4294967295U);
274    
275     JS_ASSERT(index > JSVAL_INT_MAX);
276    
277     start = JS_ARRAY_END(buf);
278     do {
279     --start;
280     *start = (jschar)('0' + index % 10);
281     index /= 10;
282     } while (index != 0);
283    
284     /*
285     * Skip the atomization if the class is known to store atoms corresponding
286     * to big indexes together with elements. In such case we know that the
287     * array does not have an element at the given index if its atom does not
288     * exist. Fast arrays (clasp == &js_ArrayClass) don't use atoms for
289     * any indexes, though it would be rare to see them have a big index
290     * in any case.
291     */
292     if (!createAtom &&
293     ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_SlowArrayClass ||
294     clasp == &js_ArgumentsClass ||
295     clasp == &js_ObjectClass)) {
296     atom = js_GetExistingStringAtom(cx, start, JS_ARRAY_END(buf) - start);
297     if (!atom) {
298     *idp = JSVAL_VOID;
299     return JS_TRUE;
300     }
301     } else {
302     atom = js_AtomizeChars(cx, start, JS_ARRAY_END(buf) - start, 0);
303     if (!atom)
304     return JS_FALSE;
305     }
306    
307     *idp = ATOM_TO_JSID(atom);
308     return JS_TRUE;
309     }
310    
311     static JSBool
312 siliconforks 507 ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 newlen,
313     bool initializeAllSlots = true)
314 siliconforks 332 {
315     jsval *slots, *newslots;
316    
317 siliconforks 507 if (newlen == 0) {
318 siliconforks 332 if (obj->dslots) {
319 siliconforks 507 cx->free(obj->dslots - 1);
320 siliconforks 332 obj->dslots = NULL;
321     }
322     return JS_TRUE;
323     }
324    
325 siliconforks 507 if (newlen > MAX_DSLOTS_LENGTH) {
326 siliconforks 332 js_ReportAllocationOverflow(cx);
327     return JS_FALSE;
328     }
329    
330     slots = obj->dslots ? obj->dslots - 1 : NULL;
331 siliconforks 507 newslots = (jsval *) cx->realloc(slots, (size_t(newlen) + 1) * sizeof(jsval));
332 siliconforks 332 if (!newslots)
333     return JS_FALSE;
334    
335     obj->dslots = newslots + 1;
336 siliconforks 507 js_SetDenseArrayCapacity(obj, newlen);
337 siliconforks 332
338 siliconforks 507 if (initializeAllSlots) {
339     for (slots = obj->dslots + oldlen; slots < obj->dslots + newlen; slots++)
340     *slots = JSVAL_HOLE;
341     }
342 siliconforks 332
343     return JS_TRUE;
344     }
345    
346 siliconforks 460 /*
347     * When a dense array with CAPACITY_DOUBLING_MAX or fewer slots needs to grow,
348     * double its capacity, to push() N elements in amortized O(N) time.
349     *
350     * Above this limit, grow by 12.5% each time. Speed is still amortized O(N),
351     * with a higher constant factor, and we waste less space.
352     */
353     #define CAPACITY_DOUBLING_MAX (1024 * 1024)
354    
355     /*
356     * Round up all large allocations to a multiple of this (1MB), so as not to
357     * waste space if malloc gives us 1MB-sized chunks (as jemalloc does).
358     */
359     #define CAPACITY_CHUNK (1024 * 1024 / sizeof(jsval))
360    
361 siliconforks 332 static JSBool
362 siliconforks 507 EnsureCapacity(JSContext *cx, JSObject *obj, uint32 newcap,
363     bool initializeAllSlots = true)
364 siliconforks 332 {
365 siliconforks 507 uint32 oldcap = js_DenseArrayCapacity(obj);
366 siliconforks 332
367 siliconforks 507 if (newcap > oldcap) {
368 siliconforks 460 /*
369 siliconforks 507 * If this overflows uint32, newcap is very large. nextsize will end
370     * up being less than newcap, the code below will thus disregard it,
371 siliconforks 460 * and ResizeSlots will fail.
372     *
373     * The way we use dslots[-1] forces a few +1s and -1s here. For
374 siliconforks 507 * example, (oldcap * 2 + 1) produces the sequence 7, 15, 31, 63, ...
375 siliconforks 460 * which makes the total allocation size (with dslots[-1]) a power
376     * of two.
377     */
378 siliconforks 507 uint32 nextsize = (oldcap <= CAPACITY_DOUBLING_MAX)
379     ? oldcap * 2 + 1
380     : oldcap + (oldcap >> 3);
381 siliconforks 460
382 siliconforks 507 uint32 actualCapacity = JS_MAX(newcap, nextsize);
383     if (actualCapacity >= CAPACITY_CHUNK)
384     actualCapacity = JS_ROUNDUP(actualCapacity + 1, CAPACITY_CHUNK) - 1; /* -1 for dslots[-1] */
385     else if (actualCapacity < ARRAY_CAPACITY_MIN)
386     actualCapacity = ARRAY_CAPACITY_MIN;
387     if (!ResizeSlots(cx, obj, oldcap, actualCapacity, initializeAllSlots))
388     return JS_FALSE;
389     if (!initializeAllSlots) {
390     /*
391     * Initialize the slots caller didn't actually ask for.
392     */
393     for (jsval *slots = obj->dslots + newcap;
394     slots < obj->dslots + actualCapacity;
395     slots++) {
396     *slots = JSVAL_HOLE;
397     }
398     }
399 siliconforks 332 }
400     return JS_TRUE;
401     }
402    
403 siliconforks 460 static bool
404     ReallyBigIndexToId(JSContext* cx, jsdouble index, jsid* idp)
405     {
406     JSAutoTempValueRooter dval(cx);
407     if (!js_NewDoubleInRootedValue(cx, index, dval.addr()) ||
408     !js_ValueToStringId(cx, dval.value(), idp)) {
409     return JS_FALSE;
410     }
411     return JS_TRUE;
412     }
413    
414     static bool
415     IndexToId(JSContext* cx, JSObject* obj, jsdouble index, JSBool* hole, jsid* idp,
416     JSBool createAtom = JS_FALSE)
417     {
418     if (index <= JSVAL_INT_MAX) {
419     *idp = INT_TO_JSID(index);
420     return JS_TRUE;
421     }
422    
423     if (index <= jsuint(-1)) {
424     if (!BigIndexToId(cx, obj, jsuint(index), createAtom, idp))
425     return JS_FALSE;
426     if (hole && JSVAL_IS_VOID(*idp))
427     *hole = JS_TRUE;
428     return JS_TRUE;
429     }
430    
431     return ReallyBigIndexToId(cx, index, idp);
432     }
433    
434 siliconforks 332 /*
435     * If the property at the given index exists, get its value into location
436     * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
437     * to JSVAL_VOID. This function assumes that the location pointed by vp is
438     * properly rooted and can be used as GC-protected storage for temporaries.
439     */
440     static JSBool
441 siliconforks 460 GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
442 siliconforks 332 jsval *vp)
443     {
444 siliconforks 460 JS_ASSERT(index >= 0);
445     if (OBJ_IS_DENSE_ARRAY(cx, obj) && index < js_DenseArrayCapacity(obj) &&
446     (*vp = obj->dslots[jsuint(index)]) != JSVAL_HOLE) {
447 siliconforks 332 *hole = JS_FALSE;
448     return JS_TRUE;
449     }
450    
451 siliconforks 460 JSAutoTempIdRooter idr(cx);
452    
453     *hole = JS_FALSE;
454     if (!IndexToId(cx, obj, index, hole, idr.addr()))
455     return JS_FALSE;
456     if (*hole) {
457     *vp = JSVAL_VOID;
458     return JS_TRUE;
459 siliconforks 332 }
460    
461 siliconforks 460 JSObject *obj2;
462     JSProperty *prop;
463 siliconforks 507 if (!obj->lookupProperty(cx, idr.id(), &obj2, &prop))
464 siliconforks 332 return JS_FALSE;
465     if (!prop) {
466     *hole = JS_TRUE;
467     *vp = JSVAL_VOID;
468     } else {
469 siliconforks 507 obj2->dropProperty(cx, prop);
470     if (!obj->getProperty(cx, idr.id(), vp))
471 siliconforks 332 return JS_FALSE;
472     *hole = JS_FALSE;
473     }
474     return JS_TRUE;
475     }
476    
477     /*
478     * Set the value of the property at the given index to v assuming v is rooted.
479     */
480     static JSBool
481 siliconforks 460 SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, jsval v)
482 siliconforks 332 {
483 siliconforks 460 JS_ASSERT(index >= 0);
484 siliconforks 332
485     if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
486 siliconforks 460 /* Predicted/prefetched code should favor the remains-dense case. */
487     if (index <= jsuint(-1)) {
488     jsuint idx = jsuint(index);
489     if (!INDEX_TOO_SPARSE(obj, idx)) {
490     JS_ASSERT(idx + 1 > idx);
491     if (!EnsureCapacity(cx, obj, idx + 1))
492     return JS_FALSE;
493     if (idx >= uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
494     obj->fslots[JSSLOT_ARRAY_LENGTH] = idx + 1;
495     if (obj->dslots[idx] == JSVAL_HOLE)
496     obj->fslots[JSSLOT_ARRAY_COUNT]++;
497     obj->dslots[idx] = v;
498     return JS_TRUE;
499     }
500 siliconforks 332 }
501    
502     if (!js_MakeArraySlow(cx, obj))
503     return JS_FALSE;
504     }
505    
506 siliconforks 460 JSAutoTempIdRooter idr(cx);
507    
508     if (!IndexToId(cx, obj, index, NULL, idr.addr(), JS_TRUE))
509     return JS_FALSE;
510     JS_ASSERT(!JSVAL_IS_VOID(idr.id()));
511    
512 siliconforks 507 return obj->setProperty(cx, idr.id(), &v);
513 siliconforks 332 }
514    
515     static JSBool
516 siliconforks 460 DeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index)
517 siliconforks 332 {
518 siliconforks 460 JS_ASSERT(index >= 0);
519 siliconforks 332 if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
520 siliconforks 460 if (index <= jsuint(-1)) {
521     jsuint idx = jsuint(index);
522     if (!INDEX_TOO_SPARSE(obj, idx) && idx < js_DenseArrayCapacity(obj)) {
523     if (obj->dslots[idx] != JSVAL_HOLE)
524     obj->fslots[JSSLOT_ARRAY_COUNT]--;
525     obj->dslots[idx] = JSVAL_HOLE;
526     return JS_TRUE;
527     }
528 siliconforks 332 }
529     return JS_TRUE;
530     }
531    
532 siliconforks 460 JSAutoTempIdRooter idr(cx);
533    
534     if (!IndexToId(cx, obj, index, NULL, idr.addr()))
535     return JS_FALSE;
536     if (JSVAL_IS_VOID(idr.id()))
537     return JS_TRUE;
538    
539     jsval junk;
540 siliconforks 507 return obj->deleteProperty(cx, idr.id(), &junk);
541 siliconforks 332 }
542    
543     /*
544     * When hole is true, delete the property at the given index. Otherwise set
545     * its value to v assuming v is rooted.
546     */
547     static JSBool
548 siliconforks 460 SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index,
549 siliconforks 332 JSBool hole, jsval v)
550     {
551     if (hole) {
552     JS_ASSERT(JSVAL_IS_VOID(v));
553     return DeleteArrayElement(cx, obj, index);
554     }
555     return SetArrayElement(cx, obj, index, v);
556     }
557    
558     JSBool
559 siliconforks 460 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsdouble length)
560 siliconforks 332 {
561     jsval v;
562     jsid id;
563    
564     if (!IndexToValue(cx, length, &v))
565     return JS_FALSE;
566     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
567 siliconforks 507 return obj->setProperty(cx, id, &v);
568 siliconforks 332 }
569    
570     JSBool
571     js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
572     {
573 siliconforks 507 JSErrorReporter older = JS_SetErrorReporter(cx, NULL);
574     JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
575     jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
576     JSBool ok = obj->getProperty(cx, id, tvr.addr());
577     JS_SetErrorReporter(cx, older);
578     if (!ok)
579     return false;
580 siliconforks 332
581 siliconforks 507 *lengthp = ValueIsLength(cx, tvr.addr());
582     return !JSVAL_IS_NULL(tvr.value());
583 siliconforks 332 }
584    
585     JSBool
586     js_IsArrayLike(JSContext *cx, JSObject *obj, JSBool *answerp, jsuint *lengthp)
587     {
588     JSClass *clasp;
589    
590 siliconforks 507 clasp = OBJ_GET_CLASS(cx, js_GetWrappedObject(cx, obj));
591 siliconforks 332 *answerp = (clasp == &js_ArgumentsClass || clasp == &js_ArrayClass ||
592     clasp == &js_SlowArrayClass);
593     if (!*answerp) {
594     *lengthp = 0;
595     return JS_TRUE;
596     }
597     return js_GetLengthProperty(cx, obj, lengthp);
598     }
599    
600     /*
601     * The 'length' property of all native Array instances is a shared permanent
602     * property of Array.prototype, so it appears to be a direct property of each
603     * array instance delegating to that Array.prototype. It accesses the private
604     * slot reserved by js_ArrayClass.
605     *
606     * Since SpiderMonkey supports cross-class prototype-based delegation, we have
607     * to be careful about the length getter and setter being called on an object
608     * not of Array class. For the getter, we search obj's prototype chain for the
609     * array that caused this getter to be invoked. In the setter case to overcome
610     * the JSPROP_SHARED attribute, we must define a shadowing length property.
611     */
612     static JSBool
613     array_length_getter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
614     {
615     do {
616     if (OBJ_IS_ARRAY(cx, obj))
617     return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
618     } while ((obj = OBJ_GET_PROTO(cx, obj)) != NULL);
619     return JS_TRUE;
620     }
621    
622     static JSBool
623     array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
624     {
625     jsuint newlen, oldlen, gap, index;
626     jsval junk;
627     JSObject *iter;
628     JSTempValueRooter tvr;
629     JSBool ok;
630    
631     if (!OBJ_IS_ARRAY(cx, obj)) {
632     jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
633    
634 siliconforks 507 return obj->defineProperty(cx, lengthId, *vp, NULL, NULL, JSPROP_ENUMERATE);
635 siliconforks 332 }
636    
637     newlen = ValueIsLength(cx, vp);
638     if (JSVAL_IS_NULL(*vp))
639     return JS_FALSE;
640     oldlen = obj->fslots[JSSLOT_ARRAY_LENGTH];
641    
642     if (oldlen == newlen)
643     return JS_TRUE;
644    
645     if (!IndexToValue(cx, newlen, vp))
646     return JS_FALSE;
647    
648     if (oldlen < newlen) {
649     obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
650     return JS_TRUE;
651     }
652    
653     if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
654 siliconforks 460 /* Don't reallocate if we're not actually shrinking our slots. */
655 siliconforks 507 jsuint capacity = js_DenseArrayCapacity(obj);
656     if (capacity > newlen && !ResizeSlots(cx, obj, capacity, newlen))
657 siliconforks 332 return JS_FALSE;
658     } else if (oldlen - newlen < (1 << 24)) {
659     do {
660     --oldlen;
661 siliconforks 460 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
662 siliconforks 332 !DeleteArrayElement(cx, obj, oldlen)) {
663     return JS_FALSE;
664     }
665     } while (oldlen != newlen);
666     } else {
667     /*
668     * We are going to remove a lot of indexes in a presumably sparse
669     * array. So instead of looping through indexes between newlen and
670     * oldlen, we iterate through all properties and remove those that
671     * correspond to indexes in the half-open range [newlen, oldlen). See
672     * bug 322135.
673     */
674     iter = JS_NewPropertyIterator(cx, obj);
675     if (!iter)
676     return JS_FALSE;
677    
678 siliconforks 507 /* Protect iter against GC under JSObject::deleteProperty. */
679 siliconforks 332 JS_PUSH_TEMP_ROOT_OBJECT(cx, iter, &tvr);
680     gap = oldlen - newlen;
681     for (;;) {
682 siliconforks 460 ok = (JS_CHECK_OPERATION_LIMIT(cx) &&
683 siliconforks 332 JS_NextProperty(cx, iter, &id));
684     if (!ok)
685     break;
686     if (JSVAL_IS_VOID(id))
687     break;
688     if (js_IdIsIndex(id, &index) && index - newlen < gap) {
689 siliconforks 507 ok = obj->deleteProperty(cx, id, &junk);
690 siliconforks 332 if (!ok)
691     break;
692     }
693     }
694     JS_POP_TEMP_ROOT(cx, &tvr);
695     if (!ok)
696     return JS_FALSE;
697     }
698    
699     obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
700     return JS_TRUE;
701     }
702    
703 siliconforks 460 /*
704     * We have only indexed properties up to capacity (excepting holes), plus the
705     * length property. For all else, we delegate to the prototype.
706     */
707     static inline bool
708     IsDenseArrayId(JSContext *cx, JSObject *obj, jsid id)
709     {
710     JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
711    
712     uint32 i;
713     return id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom) ||
714     (js_IdIsIndex(id, &i) &&
715     obj->fslots[JSSLOT_ARRAY_LENGTH] != 0 &&
716     i < js_DenseArrayCapacity(obj) &&
717     obj->dslots[i] != JSVAL_HOLE);
718     }
719    
720 siliconforks 332 static JSBool
721     array_lookupProperty(JSContext *cx, JSObject *obj, jsid id, JSObject **objp,
722     JSProperty **propp)
723     {
724     if (!OBJ_IS_DENSE_ARRAY(cx, obj))
725     return js_LookupProperty(cx, obj, id, objp, propp);
726    
727 siliconforks 460 if (IsDenseArrayId(cx, obj, id)) {
728     *propp = (JSProperty *) id;
729     *objp = obj;
730     return JS_TRUE;
731     }
732 siliconforks 332
733 siliconforks 460 JSObject *proto = STOBJ_GET_PROTO(obj);
734     if (!proto) {
735     *objp = NULL;
736     *propp = NULL;
737     return JS_TRUE;
738 siliconforks 332 }
739 siliconforks 507 return proto->lookupProperty(cx, id, objp, propp);
740 siliconforks 332 }
741    
742     static void
743     array_dropProperty(JSContext *cx, JSObject *obj, JSProperty *prop)
744     {
745 siliconforks 460 JS_ASSERT(IsDenseArrayId(cx, obj, (jsid) prop));
746 siliconforks 332 }
747    
748 siliconforks 460 JSBool
749     js_GetDenseArrayElementValue(JSContext *cx, JSObject *obj, JSProperty *prop,
750     jsval *vp)
751     {
752     jsid id = (jsid) prop;
753     JS_ASSERT(IsDenseArrayId(cx, obj, id));
754    
755     uint32 i;
756     if (!js_IdIsIndex(id, &i)) {
757     JS_ASSERT(id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom));
758     return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
759     }
760     *vp = obj->dslots[i];
761     return JS_TRUE;
762     }
763    
764 siliconforks 332 static JSBool
765     array_getProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
766     {
767     uint32 i;
768    
769     if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
770     return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
771    
772     if (id == ATOM_TO_JSID(cx->runtime->atomState.protoAtom)) {
773 siliconforks 507 *vp = OBJECT_TO_JSVAL(obj->getProto());
774 siliconforks 332 return JS_TRUE;
775     }
776    
777     if (!OBJ_IS_DENSE_ARRAY(cx, obj))
778     return js_GetProperty(cx, obj, id, vp);
779    
780 siliconforks 460 if (!js_IdIsIndex(ID_TO_VALUE(id), &i) || i >= js_DenseArrayCapacity(obj) ||
781 siliconforks 332 obj->dslots[i] == JSVAL_HOLE) {
782     JSObject *obj2;
783     JSProperty *prop;
784     JSScopeProperty *sprop;
785    
786     JSObject *proto = STOBJ_GET_PROTO(obj);
787     if (!proto) {
788     *vp = JSVAL_VOID;
789     return JS_TRUE;
790     }
791    
792     *vp = JSVAL_VOID;
793     if (js_LookupPropertyWithFlags(cx, proto, id, cx->resolveFlags,
794     &obj2, &prop) < 0)
795     return JS_FALSE;
796    
797     if (prop) {
798     if (OBJ_IS_NATIVE(obj2)) {
799     sprop = (JSScopeProperty *) prop;
800     if (!js_NativeGet(cx, obj, obj2, sprop, vp))
801     return JS_FALSE;
802     }
803 siliconforks 507 obj2->dropProperty(cx, prop);
804 siliconforks 332 }
805     return JS_TRUE;
806     }
807    
808     *vp = obj->dslots[i];
809     return JS_TRUE;
810     }
811    
812     static JSBool
813     slowarray_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
814     {
815     jsuint index, length;
816    
817     if (!js_IdIsIndex(id, &index))
818     return JS_TRUE;
819     length = obj->fslots[JSSLOT_ARRAY_LENGTH];
820     if (index >= length)
821     obj->fslots[JSSLOT_ARRAY_LENGTH] = index + 1;
822     return JS_TRUE;
823     }
824    
825     static void
826     slowarray_trace(JSTracer *trc, JSObject *obj)
827     {
828     uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
829    
830     JS_ASSERT(STOBJ_GET_CLASS(obj) == &js_SlowArrayClass);
831    
832     /*
833     * Move JSSLOT_ARRAY_LENGTH aside to prevent the GC from treating
834     * untagged integer values as objects or strings.
835     */
836     obj->fslots[JSSLOT_ARRAY_LENGTH] = JSVAL_VOID;
837     js_TraceObject(trc, obj);
838     obj->fslots[JSSLOT_ARRAY_LENGTH] = length;
839     }
840    
841     static JSObjectOps js_SlowArrayObjectOps;
842    
843     static JSObjectOps *
844     slowarray_getObjectOps(JSContext *cx, JSClass *clasp)
845     {
846     return &js_SlowArrayObjectOps;
847     }
848    
849     static JSBool
850     array_setProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
851     {
852     uint32 i;
853    
854     if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
855     return array_length_setter(cx, obj, id, vp);
856    
857     if (!OBJ_IS_DENSE_ARRAY(cx, obj))
858     return js_SetProperty(cx, obj, id, vp);
859    
860     if (!js_IdIsIndex(id, &i) || INDEX_TOO_SPARSE(obj, i)) {
861     if (!js_MakeArraySlow(cx, obj))
862     return JS_FALSE;
863     return js_SetProperty(cx, obj, id, vp);
864     }
865    
866 siliconforks 460 if (!EnsureCapacity(cx, obj, i + 1))
867 siliconforks 332 return JS_FALSE;
868    
869     if (i >= (uint32)obj->fslots[JSSLOT_ARRAY_LENGTH])
870     obj->fslots[JSSLOT_ARRAY_LENGTH] = i + 1;
871     if (obj->dslots[i] == JSVAL_HOLE)
872     obj->fslots[JSSLOT_ARRAY_COUNT]++;
873     obj->dslots[i] = *vp;
874     return JS_TRUE;
875     }
876    
877 siliconforks 460 JSBool
878     js_PrototypeHasIndexedProperties(JSContext *cx, JSObject *obj)
879     {
880     /*
881     * Walk up the prototype chain and see if this indexed element already
882     * exists. If we hit the end of the prototype chain, it's safe to set the
883     * element on the original object.
884     */
885 siliconforks 507 while ((obj = obj->getProto()) != NULL) {
886 siliconforks 460 /*
887     * If the prototype is a non-native object (possibly a dense array), or
888     * a native object (possibly a slow array) that has indexed properties,
889     * return true.
890     */
891     if (!OBJ_IS_NATIVE(obj))
892     return JS_TRUE;
893 siliconforks 507 if (OBJ_SCOPE(obj)->hadIndexedProperties())
894 siliconforks 460 return JS_TRUE;
895     }
896     return JS_FALSE;
897     }
898    
899 siliconforks 399 #ifdef JS_TRACER
900 siliconforks 507
901     static inline JSBool FASTCALL
902     dense_grow(JSContext* cx, JSObject* obj, jsint i, jsval v)
903 siliconforks 399 {
904 siliconforks 460 /*
905     * Let the interpreter worry about negative array indexes.
906     */
907 siliconforks 507 JS_ASSERT((MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) == (sizeof(jsval) != sizeof(uint32)));
908     if (MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) {
909 siliconforks 460 /*
910     * Have to check for negative values bleeding through on 64-bit machines only,
911     * since we can't allocate large enough arrays for this on 32-bit machines.
912     */
913     if (i < 0)
914     return JS_FALSE;
915     }
916    
917     /*
918     * If needed, grow the array as long it remains dense, otherwise fall off trace.
919     */
920     jsuint u = jsuint(i);
921     jsuint capacity = js_DenseArrayCapacity(obj);
922     if ((u >= capacity) && (INDEX_TOO_SPARSE(obj, u) || !EnsureCapacity(cx, obj, u + 1)))
923     return JS_FALSE;
924    
925     if (obj->dslots[u] == JSVAL_HOLE) {
926     if (js_PrototypeHasIndexedProperties(cx, obj))
927     return JS_FALSE;
928    
929     if (u >= jsuint(obj->fslots[JSSLOT_ARRAY_LENGTH]))
930     obj->fslots[JSSLOT_ARRAY_LENGTH] = u + 1;
931     ++obj->fslots[JSSLOT_ARRAY_COUNT];
932     }
933    
934     obj->dslots[u] = v;
935     return JS_TRUE;
936 siliconforks 399 }
937 siliconforks 507
938    
939     JSBool FASTCALL
940     js_Array_dense_setelem(JSContext* cx, JSObject* obj, jsint i, jsval v)
941     {
942     JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
943     return dense_grow(cx, obj, i, v);
944     }
945     JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem, CONTEXT, OBJECT, INT32, JSVAL, 0, 0)
946    
947     JSBool FASTCALL
948     js_Array_dense_setelem_int(JSContext* cx, JSObject* obj, jsint i, int32 j)
949     {
950     JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
951    
952     jsval v;
953     if (JS_LIKELY(INT_FITS_IN_JSVAL(j))) {
954     v = INT_TO_JSVAL(j);
955     } else {
956     jsdouble d = (jsdouble)j;
957     if (!js_NewDoubleInRootedValue(cx, d, &v))
958     return JS_FALSE;
959     }
960    
961     return dense_grow(cx, obj, i, v);
962     }
963     JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_int, CONTEXT, OBJECT, INT32, INT32, 0, 0)
964    
965     JSBool FASTCALL
966     js_Array_dense_setelem_double(JSContext* cx, JSObject* obj, jsint i, jsdouble d)
967     {
968     JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
969    
970     jsval v;
971     jsint j;
972    
973     if (JS_LIKELY(JSDOUBLE_IS_INT(d, j) && INT_FITS_IN_JSVAL(j))) {
974     v = INT_TO_JSVAL(j);
975     } else {
976     if (!js_NewDoubleInRootedValue(cx, d, &v))
977     return JS_FALSE;
978     }
979    
980     return dense_grow(cx, obj, i, v);
981     }
982     JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_double, CONTEXT, OBJECT, INT32, DOUBLE, 0, 0)
983 siliconforks 399 #endif
984    
985 siliconforks 332 static JSBool
986     array_defineProperty(JSContext *cx, JSObject *obj, jsid id, jsval value,
987 siliconforks 507 JSPropertyOp getter, JSPropertyOp setter, uintN attrs)
988 siliconforks 332 {
989     uint32 i;
990 siliconforks 399 JSBool isIndex;
991 siliconforks 332
992     if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
993     return JS_TRUE;
994    
995 siliconforks 399 isIndex = js_IdIsIndex(ID_TO_VALUE(id), &i);
996 siliconforks 507 if (!isIndex || attrs != JSPROP_ENUMERATE || !OBJ_IS_DENSE_ARRAY(cx, obj) || INDEX_TOO_SPARSE(obj, i)) {
997 siliconforks 332 if (!ENSURE_SLOW_ARRAY(cx, obj))
998     return JS_FALSE;
999 siliconforks 507 return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
1000 siliconforks 332 }
1001    
1002     return array_setProperty(cx, obj, id, &value);
1003     }
1004    
1005     static JSBool
1006     array_getAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
1007     uintN *attrsp)
1008     {
1009     *attrsp = id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)
1010     ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
1011     return JS_TRUE;
1012     }
1013    
1014     static JSBool
1015     array_setAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
1016     uintN *attrsp)
1017     {
1018     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
1019     JSMSG_CANT_SET_ARRAY_ATTRS);
1020     return JS_FALSE;
1021     }
1022    
1023     static JSBool
1024     array_deleteProperty(JSContext *cx, JSObject *obj, jsval id, jsval *rval)
1025     {
1026     uint32 i;
1027    
1028     if (!OBJ_IS_DENSE_ARRAY(cx, obj))
1029     return js_DeleteProperty(cx, obj, id, rval);
1030    
1031     if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) {
1032     *rval = JSVAL_FALSE;
1033     return JS_TRUE;
1034     }
1035    
1036 siliconforks 460 if (js_IdIsIndex(id, &i) && i < js_DenseArrayCapacity(obj) &&
1037 siliconforks 332 obj->dslots[i] != JSVAL_HOLE) {
1038     obj->fslots[JSSLOT_ARRAY_COUNT]--;
1039     obj->dslots[i] = JSVAL_HOLE;
1040     }
1041    
1042     *rval = JSVAL_TRUE;
1043     return JS_TRUE;
1044     }
1045    
1046     /*
1047     * JSObjectOps.enumerate implementation.
1048     *
1049     * For a fast array, JSENUMERATE_INIT captures in the enumeration state both
1050     * the length of the array and the bitmap indicating the positions of holes in
1051     * the array. This ensures that adding or deleting array elements does not
1052     * affect the sequence of indexes JSENUMERATE_NEXT returns.
1053     *
1054     * For a common case of an array without holes, to represent the state we pack
1055     * the (nextEnumerationIndex, arrayLength) pair as a pseudo-boolean jsval.
1056     * This is possible when length <= PACKED_UINT_PAIR_BITS. For arrays with
1057     * greater length or holes we allocate the JSIndexIterState structure and
1058     * store it as an int-tagged private pointer jsval. For a slow array we
1059     * delegate the enumeration implementation to js_Enumerate in
1060     * slowarray_enumerate.
1061     *
1062     * Array mutations can turn a fast array into a slow one after the enumeration
1063     * starts. When this happens, slowarray_enumerate receives a state created
1064     * when the array was fast. To distinguish such fast state from a slow state,
1065     * which is an int-tagged pointer that js_Enumerate creates, we set not one
1066     * but two lowest bits when tagging a JSIndexIterState pointer -- see
1067     * INDEX_ITER_TAG usage below. Thus, when slowarray_enumerate receives a state
1068 siliconforks 507 * tagged with JSVAL_SPECIAL or with two lowest bits set, it knows that this
1069 siliconforks 332 * is a fast state so it calls array_enumerate to continue enumerating the
1070     * indexes present in the original fast array.
1071     */
1072    
1073     #define PACKED_UINT_PAIR_BITS 14
1074     #define PACKED_UINT_PAIR_MASK JS_BITMASK(PACKED_UINT_PAIR_BITS)
1075    
1076 siliconforks 507 #define UINT_PAIR_TO_SPECIAL_JSVAL(i,j) \
1077 siliconforks 332 (JS_ASSERT((uint32) (i) <= PACKED_UINT_PAIR_MASK), \
1078     JS_ASSERT((uint32) (j) <= PACKED_UINT_PAIR_MASK), \
1079     ((jsval) (i) << (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)) | \
1080     ((jsval) (j) << (JSVAL_TAGBITS)) | \
1081 siliconforks 507 (jsval) JSVAL_SPECIAL)
1082 siliconforks 332
1083 siliconforks 507 #define SPECIAL_JSVAL_TO_UINT_PAIR(v,i,j) \
1084     (JS_ASSERT(JSVAL_IS_SPECIAL(v)), \
1085 siliconforks 332 (i) = (uint32) ((v) >> (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)), \
1086     (j) = (uint32) ((v) >> JSVAL_TAGBITS) & PACKED_UINT_PAIR_MASK, \
1087     JS_ASSERT((i) <= PACKED_UINT_PAIR_MASK))
1088    
1089     JS_STATIC_ASSERT(PACKED_UINT_PAIR_BITS * 2 + JSVAL_TAGBITS <= JS_BITS_PER_WORD);
1090    
1091     typedef struct JSIndexIterState {
1092     uint32 index;
1093     uint32 length;
1094     JSBool hasHoles;
1095    
1096     /*
1097     * Variable-length bitmap representing array's holes. It must not be
1098     * accessed when hasHoles is false.
1099     */
1100     jsbitmap holes[1];
1101     } JSIndexIterState;
1102    
1103     #define INDEX_ITER_TAG 3
1104    
1105     JS_STATIC_ASSERT(JSVAL_INT == 1);
1106    
1107     static JSBool
1108     array_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
1109     jsval *statep, jsid *idp)
1110     {
1111 siliconforks 460 uint32 capacity, i;
1112 siliconforks 332 JSIndexIterState *ii;
1113    
1114     switch (enum_op) {
1115     case JSENUMERATE_INIT:
1116     JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
1117 siliconforks 460 capacity = js_DenseArrayCapacity(obj);
1118 siliconforks 332 if (idp)
1119     *idp = INT_TO_JSVAL(obj->fslots[JSSLOT_ARRAY_COUNT]);
1120     ii = NULL;
1121 siliconforks 460 for (i = 0; i != capacity; ++i) {
1122 siliconforks 332 if (obj->dslots[i] == JSVAL_HOLE) {
1123     if (!ii) {
1124     ii = (JSIndexIterState *)
1125 siliconforks 507 cx->malloc(offsetof(JSIndexIterState, holes) +
1126 siliconforks 460 JS_BITMAP_SIZE(capacity));
1127 siliconforks 332 if (!ii)
1128     return JS_FALSE;
1129     ii->hasHoles = JS_TRUE;
1130 siliconforks 460 memset(ii->holes, 0, JS_BITMAP_SIZE(capacity));
1131 siliconforks 332 }
1132     JS_SET_BIT(ii->holes, i);
1133     }
1134     }
1135     if (!ii) {
1136     /* Array has no holes. */
1137 siliconforks 460 if (capacity <= PACKED_UINT_PAIR_MASK) {
1138 siliconforks 507 *statep = UINT_PAIR_TO_SPECIAL_JSVAL(0, capacity);
1139 siliconforks 332 break;
1140     }
1141     ii = (JSIndexIterState *)
1142 siliconforks 507 cx->malloc(offsetof(JSIndexIterState, holes));
1143 siliconforks 332 if (!ii)
1144     return JS_FALSE;
1145     ii->hasHoles = JS_FALSE;
1146     }
1147     ii->index = 0;
1148 siliconforks 460 ii->length = capacity;
1149 siliconforks 332 *statep = (jsval) ii | INDEX_ITER_TAG;
1150     JS_ASSERT(*statep & JSVAL_INT);
1151     break;
1152    
1153     case JSENUMERATE_NEXT:
1154 siliconforks 507 if (JSVAL_IS_SPECIAL(*statep)) {
1155     SPECIAL_JSVAL_TO_UINT_PAIR(*statep, i, capacity);
1156 siliconforks 460 if (i != capacity) {
1157 siliconforks 332 *idp = INT_TO_JSID(i);
1158 siliconforks 507 *statep = UINT_PAIR_TO_SPECIAL_JSVAL(i + 1, capacity);
1159 siliconforks 332 break;
1160     }
1161     } else {
1162     JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
1163     ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
1164     i = ii->index;
1165     if (i != ii->length) {
1166     /* Skip holes if any. */
1167     if (ii->hasHoles) {
1168     while (JS_TEST_BIT(ii->holes, i) && ++i != ii->length)
1169     continue;
1170     }
1171     if (i != ii->length) {
1172     ii->index = i + 1;
1173     return js_IndexToId(cx, i, idp);
1174     }
1175     }
1176     }
1177     /* FALL THROUGH */
1178    
1179     case JSENUMERATE_DESTROY:
1180 siliconforks 507 if (!JSVAL_IS_SPECIAL(*statep)) {
1181 siliconforks 332 JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
1182     ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
1183 siliconforks 507 cx->free(ii);
1184 siliconforks 332 }
1185     *statep = JSVAL_NULL;
1186     break;
1187     }
1188     return JS_TRUE;
1189     }
1190    
1191     static JSBool
1192     slowarray_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
1193     jsval *statep, jsid *idp)
1194     {
1195     JSBool ok;
1196    
1197     /* Are we continuing an enumeration that started when we were dense? */
1198     if (enum_op != JSENUMERATE_INIT) {
1199 siliconforks 507 if (JSVAL_IS_SPECIAL(*statep) ||
1200 siliconforks 332 (*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG) {
1201     return array_enumerate(cx, obj, enum_op, statep, idp);
1202     }
1203     JS_ASSERT((*statep & INDEX_ITER_TAG) == JSVAL_INT);
1204     }
1205     ok = js_Enumerate(cx, obj, enum_op, statep, idp);
1206     JS_ASSERT(*statep == JSVAL_NULL || (*statep & INDEX_ITER_TAG) == JSVAL_INT);
1207     return ok;
1208     }
1209    
1210     static void
1211     array_finalize(JSContext *cx, JSObject *obj)
1212     {
1213     if (obj->dslots)
1214 siliconforks 507 cx->free(obj->dslots - 1);
1215 siliconforks 332 obj->dslots = NULL;
1216     }
1217    
1218     static void
1219     array_trace(JSTracer *trc, JSObject *obj)
1220     {
1221 siliconforks 460 uint32 capacity;
1222 siliconforks 332 size_t i;
1223     jsval v;
1224    
1225 siliconforks 507 JS_ASSERT(js_IsDenseArray(obj));
1226     obj->traceProtoAndParent(trc);
1227 siliconforks 332
1228 siliconforks 460 capacity = js_DenseArrayCapacity(obj);
1229     for (i = 0; i < capacity; i++) {
1230 siliconforks 332 v = obj->dslots[i];
1231     if (JSVAL_IS_TRACEABLE(v)) {
1232     JS_SET_TRACING_INDEX(trc, "array_dslots", i);
1233     JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
1234     }
1235     }
1236     }
1237    
1238 siliconforks 460 extern JSObjectOps js_ArrayObjectOps;
1239 siliconforks 332
1240 siliconforks 507 static const JSObjectMap SharedArrayMap(&js_ArrayObjectOps, JSObjectMap::SHAPELESS);
1241 siliconforks 332
1242     JSObjectOps js_ArrayObjectOps = {
1243 siliconforks 460 &SharedArrayMap,
1244 siliconforks 332 array_lookupProperty, array_defineProperty,
1245     array_getProperty, array_setProperty,
1246     array_getAttributes, array_setAttributes,
1247     array_deleteProperty, js_DefaultValue,
1248     array_enumerate, js_CheckAccess,
1249     NULL, array_dropProperty,
1250     NULL, NULL,
1251 siliconforks 460 js_HasInstance, array_trace,
1252     NULL
1253 siliconforks 332 };
1254    
1255     static JSObjectOps *
1256     array_getObjectOps(JSContext *cx, JSClass *clasp)
1257     {
1258     return &js_ArrayObjectOps;
1259     }
1260    
1261     JSClass js_ArrayClass = {
1262     "Array",
1263 siliconforks 507 JSCLASS_HAS_RESERVED_SLOTS(2) |
1264     JSCLASS_HAS_CACHED_PROTO(JSProto_Array) |
1265     JSCLASS_NEW_ENUMERATE,
1266 siliconforks 332 JS_PropertyStub, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
1267     JS_EnumerateStub, JS_ResolveStub, js_TryValueOf, array_finalize,
1268     array_getObjectOps, NULL, NULL, NULL,
1269     NULL, NULL, NULL, NULL
1270     };
1271    
1272     JSClass js_SlowArrayClass = {
1273     "Array",
1274 siliconforks 507 JSCLASS_HAS_RESERVED_SLOTS(1) |
1275     JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
1276 siliconforks 332 slowarray_addProperty, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
1277 siliconforks 507 JS_EnumerateStub, JS_ResolveStub, js_TryValueOf, NULL,
1278 siliconforks 332 slowarray_getObjectOps, NULL, NULL, NULL,
1279     NULL, NULL, NULL, NULL
1280     };
1281    
1282     /*
1283     * Convert an array object from fast-and-dense to slow-and-flexible.
1284     */
1285     JSBool
1286     js_MakeArraySlow(JSContext *cx, JSObject *obj)
1287     {
1288 siliconforks 507 JS_ASSERT(obj->getClass() == &js_ArrayClass);
1289 siliconforks 332
1290 siliconforks 507 /*
1291     * Create a native scope. All slow arrays other than Array.prototype get
1292     * the same initial shape.
1293     */
1294     uint32 emptyShape;
1295     JSObject *arrayProto = obj->getProto();
1296     if (arrayProto->getClass() == &js_ObjectClass) {
1297     /* obj is Array.prototype. */
1298     emptyShape = js_GenerateShape(cx, false);
1299     } else {
1300     /* arrayProto is Array.prototype. */
1301     JS_ASSERT(arrayProto->getClass() == &js_SlowArrayClass);
1302     emptyShape = OBJ_SCOPE(arrayProto)->emptyScope->shape;
1303     }
1304     JSScope *scope = JSScope::create(cx, &js_SlowArrayObjectOps, &js_SlowArrayClass, obj,
1305     emptyShape);
1306 siliconforks 460 if (!scope)
1307 siliconforks 332 return JS_FALSE;
1308    
1309 siliconforks 460 uint32 capacity = js_DenseArrayCapacity(obj);
1310     if (capacity) {
1311     scope->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
1312     obj->dslots[-1] = JS_INITIAL_NSLOTS + capacity;
1313 siliconforks 332 } else {
1314 siliconforks 460 scope->freeslot = STOBJ_NSLOTS(obj);
1315 siliconforks 332 }
1316    
1317     /* Create new properties pointing to existing values in dslots */
1318 siliconforks 460 for (uint32 i = 0; i < capacity; i++) {
1319 siliconforks 332 jsid id;
1320     JSScopeProperty *sprop;
1321    
1322     if (!JS_ValueToId(cx, INT_TO_JSVAL(i), &id))
1323     goto out_bad;
1324    
1325     if (obj->dslots[i] == JSVAL_HOLE) {
1326     obj->dslots[i] = JSVAL_VOID;
1327     continue;
1328     }
1329    
1330 siliconforks 507 sprop = scope->add(cx, id, NULL, NULL, i + JS_INITIAL_NSLOTS,
1331     JSPROP_ENUMERATE, 0, 0);
1332 siliconforks 332 if (!sprop)
1333     goto out_bad;
1334     }
1335    
1336     /*
1337     * Render our formerly-reserved count property GC-safe. If length fits in
1338     * a jsval, set our slow/sparse COUNT to the current length as a jsval, so
1339     * we can tell when only named properties have been added to a dense array
1340     * to make it slow-but-not-sparse.
1341     */
1342 siliconforks 460 {
1343     uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
1344     obj->fslots[JSSLOT_ARRAY_COUNT] = INT_FITS_IN_JSVAL(length)
1345     ? INT_TO_JSVAL(length)
1346     : JSVAL_VOID;
1347     }
1348 siliconforks 332
1349     /* Make sure we preserve any flags borrowing bits in classword. */
1350     obj->classword ^= (jsuword) &js_ArrayClass;
1351     obj->classword |= (jsuword) &js_SlowArrayClass;
1352    
1353 siliconforks 507 obj->map = scope;
1354 siliconforks 332 return JS_TRUE;
1355    
1356 siliconforks 460 out_bad:
1357 siliconforks 507 JSScope::destroy(cx, scope);
1358 siliconforks 332 return JS_FALSE;
1359     }
1360    
1361 siliconforks 507 /* Transfer ownership of buffer to returned string. */
1362     static inline JSBool
1363     BufferToString(JSContext *cx, JSCharBuffer &cb, jsval *rval)
1364     {
1365     JSString *str = js_NewStringFromCharBuffer(cx, cb);
1366     if (!str)
1367     return false;
1368     *rval = STRING_TO_JSVAL(str);
1369     return true;
1370     }
1371 siliconforks 399
1372 siliconforks 507 #if JS_HAS_TOSOURCE
1373 siliconforks 399 static JSBool
1374 siliconforks 507 array_toSource(JSContext *cx, uintN argc, jsval *vp)
1375 siliconforks 332 {
1376 siliconforks 507 JS_CHECK_RECURSION(cx, return false);
1377 siliconforks 332
1378 siliconforks 507 JSObject *obj = JS_THIS_OBJECT(cx, vp);
1379     if (!obj ||
1380     (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1381     !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1382     return false;
1383     }
1384 siliconforks 332
1385 siliconforks 507 /* Find joins or cycles in the reachable object graph. */
1386     jschar *sharpchars;
1387     JSHashEntry *he = js_EnterSharpObject(cx, obj, NULL, &sharpchars);
1388 siliconforks 332 if (!he)
1389 siliconforks 507 return false;
1390     bool initiallySharp = IS_SHARP(he);
1391 siliconforks 332
1392 siliconforks 507 /* After this point, all paths exit through the 'out' label. */
1393     MUST_FLOW_THROUGH("out");
1394     bool ok = false;
1395    
1396 siliconforks 460 /*
1397 siliconforks 507 * This object will take responsibility for the jschar buffer until the
1398     * buffer is transferred to the returned JSString.
1399 siliconforks 460 */
1400 siliconforks 507 JSCharBuffer cb(cx);
1401    
1402     /* Cycles/joins are indicated by sharp objects. */
1403     #if JS_HAS_SHARP_VARS
1404 siliconforks 460 if (IS_SHARP(he)) {
1405 siliconforks 507 JS_ASSERT(sharpchars != 0);
1406     cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1407     goto make_string;
1408     } else if (sharpchars) {
1409     MAKE_SHARP(he);
1410     cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1411     }
1412 siliconforks 332 #else
1413 siliconforks 507 if (IS_SHARP(he)) {
1414     if (!js_AppendLiteral(cb, "[]"))
1415     goto out;
1416     cx->free(sharpchars);
1417 siliconforks 460 goto make_string;
1418     }
1419 siliconforks 507 #endif
1420 siliconforks 332
1421 siliconforks 507 if (!cb.append('['))
1422     goto out;
1423    
1424     jsuint length;
1425     if (!js_GetLengthProperty(cx, obj, &length))
1426     goto out;
1427    
1428     for (jsuint index = 0; index < length; index++) {
1429     /* Use vp to locally root each element value. */
1430     JSBool hole;
1431     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1432     !GetArrayElement(cx, obj, index, &hole, vp)) {
1433     goto out;
1434     }
1435    
1436     /* Get element's character string. */
1437     JSString *str;
1438     if (hole) {
1439     str = cx->runtime->emptyString;
1440 siliconforks 332 } else {
1441 siliconforks 507 str = js_ValueToSource(cx, *vp);
1442     if (!str)
1443     goto out;
1444 siliconforks 332 }
1445 siliconforks 507 *vp = STRING_TO_JSVAL(str);
1446     const jschar *chars;
1447     size_t charlen;
1448     str->getCharsAndLength(chars, charlen);
1449 siliconforks 332
1450 siliconforks 507 /* Append element to buffer. */
1451     if (!cb.append(chars, charlen))
1452     goto out;
1453     if (index + 1 != length) {
1454     if (!js_AppendLiteral(cb, ", "))
1455     goto out;
1456     } else if (hole) {
1457     if (!cb.append(','))
1458     goto out;
1459 siliconforks 332 }
1460 siliconforks 507 }
1461 siliconforks 332
1462 siliconforks 507 /* Finalize the buffer. */
1463     if (!cb.append(']'))
1464     goto out;
1465 siliconforks 332
1466 siliconforks 507 make_string:
1467     if (!BufferToString(cx, cb, vp))
1468     goto out;
1469    
1470     ok = true;
1471    
1472     out:
1473     if (!initiallySharp)
1474     js_LeaveSharpObject(cx, NULL);
1475     return ok;
1476     }
1477     #endif
1478    
1479     static JSHashNumber
1480     js_hash_array(const void *key)
1481     {
1482     return (JSHashNumber)JS_PTR_TO_UINT32(key) >> JSVAL_TAGBITS;
1483     }
1484    
1485     bool
1486     js_InitContextBusyArrayTable(JSContext *cx)
1487     {
1488     cx->busyArrayTable = JS_NewHashTable(4, js_hash_array, JS_CompareValues,
1489     JS_CompareValues, NULL, NULL);
1490     return cx->busyArrayTable != NULL;
1491     }
1492    
1493     static JSBool
1494     array_toString_sub(JSContext *cx, JSObject *obj, JSBool locale,
1495     JSString *sepstr, jsval *rval)
1496     {
1497     JS_CHECK_RECURSION(cx, return false);
1498    
1499     /*
1500     * This hash table is shared between toString invocations and must be empty
1501     * after the root invocation completes.
1502     */
1503     JSHashTable *table = cx->busyArrayTable;
1504    
1505     /*
1506     * Use HashTable entry as the cycle indicator. On first visit, create the
1507     * entry, and, when leaving, remove the entry.
1508     */
1509     JSHashNumber hash = js_hash_array(obj);
1510     JSHashEntry **hep = JS_HashTableRawLookup(table, hash, obj);
1511     JSHashEntry *he = *hep;
1512     if (!he) {
1513     /* Not in hash table, so not a cycle. */
1514     he = JS_HashTableRawAdd(table, hep, hash, obj, NULL);
1515     if (!he) {
1516     JS_ReportOutOfMemory(cx);
1517     return false;
1518 siliconforks 332 }
1519 siliconforks 507 } else {
1520     /* Cycle, so return empty string. */
1521     *rval = ATOM_KEY(cx->runtime->atomState.emptyAtom);
1522     return true;
1523 siliconforks 332 }
1524    
1525 siliconforks 507 JSAutoTempValueRooter tvr(cx, obj);
1526 siliconforks 332
1527 siliconforks 507 /* After this point, all paths exit through the 'out' label. */
1528     MUST_FLOW_THROUGH("out");
1529     bool ok = false;
1530 siliconforks 332
1531 siliconforks 507 /* Get characters to use for the separator. */
1532     static const jschar comma = ',';
1533     const jschar *sep;
1534     size_t seplen;
1535     if (sepstr) {
1536     sepstr->getCharsAndLength(sep, seplen);
1537     } else {
1538     sep = &comma;
1539     seplen = 1;
1540     }
1541 siliconforks 332
1542 siliconforks 507 /*
1543     * This object will take responsibility for the jschar buffer until the
1544     * buffer is transferred to the returned JSString.
1545     */
1546     JSCharBuffer cb(cx);
1547    
1548     jsuint length;
1549     if (!js_GetLengthProperty(cx, obj, &length))
1550     goto out;
1551    
1552     for (jsuint index = 0; index < length; index++) {
1553     /* Use rval to locally root each element value. */
1554     JSBool hole;
1555     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1556     !GetArrayElement(cx, obj, index, &hole, rval)) {
1557     goto out;
1558 siliconforks 332 }
1559    
1560 siliconforks 507 /* Get element's character string. */
1561     if (!(hole || JSVAL_IS_VOID(*rval) || JSVAL_IS_NULL(*rval))) {
1562     if (locale) {
1563     /* Work on obj.toLocalString() instead. */
1564     JSObject *robj;
1565 siliconforks 332
1566 siliconforks 507 if (!js_ValueToObject(cx, *rval, &robj))
1567     goto out;
1568     *rval = OBJECT_TO_JSVAL(robj);
1569     JSAtom *atom = cx->runtime->atomState.toLocaleStringAtom;
1570     if (!js_TryMethod(cx, robj, atom, 0, NULL, rval))
1571     goto out;
1572 siliconforks 332 }
1573 siliconforks 507
1574     if (!js_ValueToCharBuffer(cx, *rval, cb))
1575     goto out;
1576 siliconforks 332 }
1577    
1578 siliconforks 507 /* Append the separator. */
1579     if (index + 1 != length) {
1580     if (!cb.append(sep, seplen))
1581     goto out;
1582     }
1583 siliconforks 332 }
1584    
1585 siliconforks 507 /* Finalize the buffer. */
1586     if (!BufferToString(cx, cb, rval))
1587     goto out;
1588 siliconforks 332
1589 siliconforks 507 ok = true;
1590 siliconforks 332
1591 siliconforks 507 out:
1592     /*
1593     * It is possible that 'hep' may have been invalidated by subsequent
1594     * RawAdd/Remove. Hence, 'RawRemove' must not be used.
1595     */
1596     JS_HashTableRemove(table, obj);
1597     return ok;
1598 siliconforks 332 }
1599    
1600     static JSBool
1601     array_toString(JSContext *cx, uintN argc, jsval *vp)
1602     {
1603     JSObject *obj;
1604    
1605     obj = JS_THIS_OBJECT(cx, vp);
1606 siliconforks 507 if (!obj ||
1607     (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1608     !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1609 siliconforks 332 return JS_FALSE;
1610     }
1611 siliconforks 507
1612     return array_toString_sub(cx, obj, JS_FALSE, NULL, vp);
1613 siliconforks 332 }
1614    
1615     static JSBool
1616     array_toLocaleString(JSContext *cx, uintN argc, jsval *vp)
1617     {
1618     JSObject *obj;
1619    
1620     obj = JS_THIS_OBJECT(cx, vp);
1621 siliconforks 507 if (!obj ||
1622     (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1623     !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1624 siliconforks 332 return JS_FALSE;
1625     }
1626    
1627     /*
1628     * Passing comma here as the separator. Need a way to get a
1629     * locale-specific version.
1630     */
1631 siliconforks 507 return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
1632 siliconforks 332 }
1633    
1634 siliconforks 460 enum TargetElementsType {
1635     TargetElementsAllHoles,
1636     TargetElementsMayContainValues
1637     };
1638    
1639     enum SourceVectorType {
1640     SourceVectorAllValues,
1641     SourceVectorMayContainHoles
1642     };
1643    
1644 siliconforks 332 static JSBool
1645 siliconforks 460 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, jsval *vector,
1646     TargetElementsType targetType, SourceVectorType vectorType)
1647 siliconforks 332 {
1648 siliconforks 460 JS_ASSERT(count < MAXINDEX);
1649    
1650     /*
1651     * Optimize for dense arrays so long as adding the given set of elements
1652     * wouldn't otherwise make the array slow.
1653     */
1654     if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
1655     start <= MAXINDEX - count && !INDEX_TOO_BIG(start + count)) {
1656    
1657     #ifdef DEBUG_jwalden
1658     {
1659     /* Verify that overwriteType and writeType were accurate. */
1660     JSAutoTempIdRooter idr(cx, JSVAL_ZERO);
1661     for (jsuint i = 0; i < count; i++) {
1662     JS_ASSERT_IF(vectorType == SourceVectorAllValues, vector[i] != JSVAL_HOLE);
1663    
1664     jsdouble index = jsdouble(start) + i;
1665     if (targetType == TargetElementsAllHoles && index < jsuint(-1)) {
1666     JS_ASSERT(ReallyBigIndexToId(cx, index, idr.addr()));
1667     JSObject* obj2;
1668     JSProperty* prop;
1669 siliconforks 507 JS_ASSERT(obj->lookupProperty(cx, idr.id(), &obj2, &prop));
1670 siliconforks 460 JS_ASSERT(!prop);
1671     }
1672     }
1673     }
1674     #endif
1675    
1676     jsuint newlen = start + count;
1677     JS_ASSERT(jsdouble(start) + count == jsdouble(newlen));
1678     if (!EnsureCapacity(cx, obj, newlen))
1679 siliconforks 332 return JS_FALSE;
1680    
1681 siliconforks 460 if (newlen > uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
1682     obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
1683 siliconforks 332
1684 siliconforks 460 JS_ASSERT(count < size_t(-1) / sizeof(jsval));
1685     if (targetType == TargetElementsMayContainValues) {
1686     jsuint valueCount = 0;
1687     for (jsuint i = 0; i < count; i++) {
1688     if (obj->dslots[start + i] != JSVAL_HOLE)
1689     valueCount++;
1690     }
1691     JS_ASSERT(uint32(obj->fslots[JSSLOT_ARRAY_COUNT]) >= valueCount);
1692     obj->fslots[JSSLOT_ARRAY_COUNT] -= valueCount;
1693     }
1694     memcpy(obj->dslots + start, vector, sizeof(jsval) * count);
1695     if (vectorType == SourceVectorAllValues) {
1696     obj->fslots[JSSLOT_ARRAY_COUNT] += count;
1697     } else {
1698     jsuint valueCount = 0;
1699     for (jsuint i = 0; i < count; i++) {
1700     if (obj->dslots[start + i] != JSVAL_HOLE)
1701     valueCount++;
1702     }
1703     obj->fslots[JSSLOT_ARRAY_COUNT] += valueCount;
1704     }
1705     JS_ASSERT_IF(count != 0, obj->dslots[newlen - 1] != JSVAL_HOLE);
1706 siliconforks 332 return JS_TRUE;
1707     }
1708    
1709 siliconforks 460 jsval* end = vector + count;
1710     while (vector != end && start < MAXINDEX) {
1711     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1712 siliconforks 332 !SetArrayElement(cx, obj, start++, *vector++)) {
1713     return JS_FALSE;
1714     }
1715     }
1716 siliconforks 460
1717     if (vector == end)
1718     return JS_TRUE;
1719    
1720     /* Finish out any remaining elements past the max array index. */
1721     if (OBJ_IS_DENSE_ARRAY(cx, obj) && !ENSURE_SLOW_ARRAY(cx, obj))
1722     return JS_FALSE;
1723    
1724     JS_ASSERT(start == MAXINDEX);
1725     jsval tmp[2] = {JSVAL_NULL, JSVAL_NULL};
1726     jsdouble* dp = js_NewWeaklyRootedDouble(cx, MAXINDEX);
1727     if (!dp)
1728     return JS_FALSE;
1729     tmp[0] = DOUBLE_TO_JSVAL(dp);
1730 siliconforks 507 JSAutoTempValueRooter tvr(cx, JS_ARRAY_LENGTH(tmp), tmp);
1731 siliconforks 460 JSAutoTempIdRooter idr(cx);
1732     do {
1733     tmp[1] = *vector++;
1734     if (!js_ValueToStringId(cx, tmp[0], idr.addr()) ||
1735 siliconforks 507 !obj->setProperty(cx, idr.id(), &tmp[1])) {
1736 siliconforks 460 return JS_FALSE;
1737     }
1738     *dp += 1;
1739     } while (vector != end);
1740    
1741 siliconforks 332 return JS_TRUE;
1742     }
1743    
1744     static JSBool
1745     InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector,
1746     JSBool holey = JS_FALSE)
1747     {
1748     JS_ASSERT(OBJ_IS_ARRAY(cx, obj));
1749    
1750     obj->fslots[JSSLOT_ARRAY_LENGTH] = length;
1751    
1752     if (vector) {
1753 siliconforks 460 if (!EnsureCapacity(cx, obj, length))
1754 siliconforks 332 return JS_FALSE;
1755    
1756     jsuint count = length;
1757     if (!holey) {
1758     memcpy(obj->dslots, vector, length * sizeof (jsval));
1759     } else {
1760     for (jsuint i = 0; i < length; i++) {
1761     if (vector[i] == JSVAL_HOLE)
1762     --count;
1763     obj->dslots[i] = vector[i];
1764     }
1765     }
1766     obj->fslots[JSSLOT_ARRAY_COUNT] = count;
1767     } else {
1768     obj->fslots[JSSLOT_ARRAY_COUNT] = 0;
1769     }
1770     return JS_TRUE;
1771     }
1772    
1773 siliconforks 399 #ifdef JS_TRACER
1774     static JSString* FASTCALL
1775     Array_p_join(JSContext* cx, JSObject* obj, JSString *str)
1776     {
1777 siliconforks 460 JSAutoTempValueRooter tvr(cx);
1778 siliconforks 507 if (!array_toString_sub(cx, obj, JS_FALSE, str, tvr.addr())) {
1779 siliconforks 460 js_SetBuiltinError(cx);
1780 siliconforks 399 return NULL;
1781 siliconforks 460 }
1782     return JSVAL_TO_STRING(tvr.value());
1783 siliconforks 399 }
1784    
1785     static JSString* FASTCALL
1786     Array_p_toString(JSContext* cx, JSObject* obj)
1787     {
1788 siliconforks 460 JSAutoTempValueRooter tvr(cx);
1789 siliconforks 507 if (!array_toString_sub(cx, obj, JS_FALSE, NULL, tvr.addr())) {
1790 siliconforks 460 js_SetBuiltinError(cx);
1791 siliconforks 399 return NULL;
1792 siliconforks 460 }
1793     return JSVAL_TO_STRING(tvr.value());
1794 siliconforks 399 }
1795     #endif
1796    
1797 siliconforks 332 /*
1798     * Perl-inspired join, reverse, and sort.
1799     */
1800 siliconforks 399 static JSBool
1801     array_join(JSContext *cx, uintN argc, jsval *vp)
1802 siliconforks 332 {
1803     JSString *str;
1804     JSObject *obj;
1805    
1806     if (argc == 0 || JSVAL_IS_VOID(vp[2])) {
1807     str = NULL;
1808     } else {
1809     str = js_ValueToString(cx, vp[2]);
1810     if (!str)
1811     return JS_FALSE;
1812     vp[2] = STRING_TO_JSVAL(str);
1813     }
1814     obj = JS_THIS_OBJECT(cx, vp);
1815 siliconforks 507 return obj && array_toString_sub(cx, obj, JS_FALSE, str, vp);
1816 siliconforks 332 }
1817    
1818     static JSBool
1819     array_reverse(JSContext *cx, uintN argc, jsval *vp)
1820     {
1821 siliconforks 507 jsuint len;
1822     JSObject *obj = JS_THIS_OBJECT(cx, vp);
1823 siliconforks 332 if (!obj || !js_GetLengthProperty(cx, obj, &len))
1824     return JS_FALSE;
1825 siliconforks 460 *vp = OBJECT_TO_JSVAL(obj);
1826 siliconforks 332
1827 siliconforks 460 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj)) {
1828     /* An empty array or an array with no elements is already reversed. */
1829     if (len == 0 || !obj->dslots)
1830     return JS_TRUE;
1831    
1832     /*
1833     * It's actually surprisingly complicated to reverse an array due to the
1834     * orthogonality of array length and array capacity while handling
1835     * leading and trailing holes correctly. Reversing seems less likely to
1836     * be a common operation than other array mass-mutation methods, so for
1837     * now just take a probably-small memory hit (in the absence of too many
1838     * holes in the array at its start) and ensure that the capacity is
1839     * sufficient to hold all the elements in the array if it were full.
1840     */
1841     if (!EnsureCapacity(cx, obj, len))
1842     return JS_FALSE;
1843    
1844     jsval* lo = &obj->dslots[0];
1845     jsval* hi = &obj->dslots[len - 1];
1846     for (; lo < hi; lo++, hi--) {
1847     jsval tmp = *lo;
1848     *lo = *hi;
1849     *hi = tmp;
1850     }
1851    
1852     /*
1853     * Per ECMA-262, don't update the length of the array, even if the new
1854     * array has trailing holes (and thus the original array began with
1855     * holes).
1856     */
1857     return JS_TRUE;
1858     }
1859    
1860 siliconforks 507 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
1861     for (jsuint i = 0, half = len / 2; i < half; i++) {
1862     JSBool hole, hole2;
1863     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1864     !GetArrayElement(cx, obj, i, &hole, tvr.addr()) ||
1865     !GetArrayElement(cx, obj, len - i - 1, &hole2, vp) ||
1866     !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, tvr.value()) ||
1867     !SetOrDeleteArrayElement(cx, obj, i, hole2, *vp)) {
1868     return false;
1869     }
1870 siliconforks 332 }
1871     *vp = OBJECT_TO_JSVAL(obj);
1872 siliconforks 507 return true;
1873 siliconforks 332 }
1874    
1875     typedef struct MSortArgs {
1876     size_t elsize;
1877     JSComparator cmp;
1878     void *arg;
1879     JSBool fastcopy;
1880     } MSortArgs;
1881    
1882     /* Helper function for js_MergeSort. */
1883 siliconforks 507 static JSBool
1884 siliconforks 332 MergeArrays(MSortArgs *msa, void *src, void *dest, size_t run1, size_t run2)
1885     {
1886     void *arg, *a, *b, *c;
1887     size_t elsize, runtotal;
1888     int cmp_result;
1889     JSComparator cmp;
1890     JSBool fastcopy;
1891    
1892     runtotal = run1 + run2;
1893    
1894     elsize = msa->elsize;
1895     cmp = msa->cmp;
1896     arg = msa->arg;
1897     fastcopy = msa->fastcopy;
1898    
1899     #define CALL_CMP(a, b) \
1900     if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1901    
1902     /* Copy runs already in sorted order. */
1903     b = (char *)src + run1 * elsize;
1904     a = (char *)b - elsize;
1905     CALL_CMP(a, b);
1906     if (cmp_result <= 0) {
1907     memcpy(dest, src, runtotal * elsize);
1908     return JS_TRUE;
1909     }
1910    
1911     #define COPY_ONE(p,q,n) \
1912     (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1913    
1914     a = src;
1915     c = dest;
1916     for (; runtotal != 0; runtotal--) {
1917     JSBool from_a = run2 == 0;
1918     if (!from_a && run1 != 0) {
1919     CALL_CMP(a,b);
1920     from_a = cmp_result <= 0;
1921     }
1922    
1923     if (from_a) {
1924     COPY_ONE(c, a, elsize);
1925     run1--;
1926     a = (char *)a + elsize;
1927     } else {
1928     COPY_ONE(c, b, elsize);
1929     run2--;
1930     b = (char *)b + elsize;
1931     }
1932     c = (char *)c + elsize;
1933     }
1934     #undef COPY_ONE
1935     #undef CALL_CMP
1936    
1937     return JS_TRUE;
1938     }
1939    
1940     /*
1941     * This sort is stable, i.e. sequence of equal elements is preserved.
1942     * See also bug #224128.
1943     */
1944 siliconforks 507 JSBool
1945 siliconforks 332 js_MergeSort(void *src, size_t nel, size_t elsize,
1946     JSComparator cmp, void *arg, void *tmp)
1947     {
1948     void *swap, *vec1, *vec2;
1949     MSortArgs msa;
1950     size_t i, j, lo, hi, run;
1951     JSBool fastcopy;
1952     int cmp_result;
1953    
1954     /* Avoid memcpy overhead for word-sized and word-aligned elements. */
1955     fastcopy = (elsize == sizeof(jsval) &&
1956     (((jsuword) src | (jsuword) tmp) & JSVAL_ALIGN) == 0);
1957     #define COPY_ONE(p,q,n) \
1958     (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1959     #define CALL_CMP(a, b) \
1960     if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1961     #define INS_SORT_INT 4
1962    
1963     /*
1964     * Apply insertion sort to small chunks to reduce the number of merge
1965     * passes needed.
1966     */
1967     for (lo = 0; lo < nel; lo += INS_SORT_INT) {
1968     hi = lo + INS_SORT_INT;
1969     if (hi >= nel)
1970     hi = nel;
1971     for (i = lo + 1; i < hi; i++) {
1972     vec1 = (char *)src + i * elsize;
1973     vec2 = (char *)vec1 - elsize;
1974     for (j = i; j > lo; j--) {
1975     CALL_CMP(vec2, vec1);
1976     /* "<=" instead of "<" insures the sort is stable */
1977     if (cmp_result <= 0) {
1978     break;
1979     }
1980    
1981     /* Swap elements, using "tmp" as tmp storage */
1982     COPY_ONE(tmp, vec2, elsize);
1983     COPY_ONE(vec2, vec1, elsize);
1984     COPY_ONE(vec1, tmp, elsize);
1985     vec1 = vec2;
1986     vec2 = (char *)vec1 - elsize;
1987     }
1988     }
1989     }
1990     #undef CALL_CMP
1991     #undef COPY_ONE
1992    
1993     msa.elsize = elsize;
1994     msa.cmp = cmp;
1995     msa.arg = arg;
1996     msa.fastcopy = fastcopy;
1997    
1998     vec1 = src;
1999     vec2 = tmp;
2000     for (run = INS_SORT_INT; run < nel; run *= 2) {
2001     for (lo = 0; lo < nel; lo += 2 * run) {
2002     hi = lo + run;
2003     if (hi >= nel) {
2004     memcpy((char *)vec2 + lo * elsize, (char *)vec1 + lo * elsize,
2005     (nel - lo) * elsize);
2006     break;
2007     }
2008     if (!MergeArrays(&msa, (char *)vec1 + lo * elsize,
2009     (char *)vec2 + lo * elsize, run,
2010     hi + run > nel ? nel - hi : run)) {
2011     return JS_FALSE;
2012     }
2013     }
2014     swap = vec1;
2015     vec1 = vec2;
2016     vec2 = swap;
2017     }
2018     if (src != vec1)
2019     memcpy(src, tmp, nel * elsize);
2020    
2021     return JS_TRUE;
2022     }
2023    
2024     typedef struct CompareArgs {
2025     JSContext *context;
2026     jsval fval;
2027     jsval *elemroot; /* stack needed for js_Invoke */
2028     } CompareArgs;
2029    
2030 siliconforks 460 static JS_REQUIRES_STACK JSBool
2031 siliconforks 332 sort_compare(void *arg, const void *a, const void *b, int *result)
2032     {
2033     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
2034     CompareArgs *ca = (CompareArgs *) arg;
2035     JSContext *cx = ca->context;
2036     jsval *invokevp, *sp;
2037     jsdouble cmp;
2038    
2039     /**
2040     * array_sort deals with holes and undefs on its own and they should not
2041     * come here.
2042     */
2043     JS_ASSERT(!JSVAL_IS_VOID(av));
2044     JS_ASSERT(!JSVAL_IS_VOID(bv));
2045    
2046 siliconforks 460 if (!JS_CHECK_OPERATION_LIMIT(cx))
2047 siliconforks 332 return JS_FALSE;
2048    
2049     invokevp = ca->elemroot;
2050     sp = invokevp;
2051     *sp++ = ca->fval;
2052     *sp++ = JSVAL_NULL;
2053     *sp++ = av;
2054     *sp++ = bv;
2055    
2056     if (!js_Invoke(cx, 2, invokevp, 0))
2057     return JS_FALSE;
2058    
2059     cmp = js_ValueToNumber(cx, invokevp);
2060     if (JSVAL_IS_NULL(*invokevp))
2061     return JS_FALSE;
2062    
2063     /* Clamp cmp to -1, 0, 1. */
2064     *result = 0;
2065     if (!JSDOUBLE_IS_NaN(cmp) && cmp != 0)
2066     *result = cmp > 0 ? 1 : -1;
2067    
2068     /*
2069     * XXX else report some kind of error here? ECMA talks about 'consistent
2070     * compare functions' that don't return NaN, but is silent about what the
2071     * result should be. So we currently ignore it.
2072     */
2073    
2074     return JS_TRUE;
2075     }
2076    
2077 siliconforks 507 typedef JSBool (JS_REQUIRES_STACK *JSRedComparator)(void*, const void*,
2078     const void*, int *);
2079    
2080     static inline JS_IGNORE_STACK JSComparator
2081     comparator_stack_cast(JSRedComparator func)
2082     {
2083     return func;
2084     }
2085    
2086 siliconforks 332 static int
2087     sort_compare_strings(void *arg, const void *a, const void *b, int *result)
2088     {
2089     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
2090    
2091     JS_ASSERT(JSVAL_IS_STRING(av));
2092     JS_ASSERT(JSVAL_IS_STRING(bv));
2093 siliconforks 460 if (!JS_CHECK_OPERATION_LIMIT((JSContext *)arg))
2094 siliconforks 332 return JS_FALSE;
2095    
2096     *result = (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
2097     return JS_TRUE;
2098     }
2099    
2100     /*
2101     * The array_sort function below assumes JSVAL_NULL is zero in order to
2102     * perform initialization using memset. Other parts of SpiderMonkey likewise
2103     * "know" that JSVAL_NULL is zero; this static assertion covers all cases.
2104     */
2105     JS_STATIC_ASSERT(JSVAL_NULL == 0);
2106    
2107 siliconforks 507 static JSBool
2108 siliconforks 332 array_sort(JSContext *cx, uintN argc, jsval *vp)
2109     {
2110     jsval *argv, fval, *vec, *mergesort_tmp, v;
2111     JSObject *obj;
2112     CompareArgs ca;
2113     jsuint len, newlen, i, undefs;
2114     JSTempValueRooter tvr;
2115     JSBool hole;
2116 siliconforks 460 JSBool ok;
2117 siliconforks 332 size_t elemsize;
2118     JSString *str;
2119    
2120     /*
2121     * Optimize the default compare function case if all of obj's elements
2122     * have values of type string.
2123     */
2124     JSBool all_strings;
2125    
2126     argv = JS_ARGV(cx, vp);
2127     if (argc > 0) {
2128     if (JSVAL_IS_PRIMITIVE(argv[0])) {
2129     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2130     JSMSG_BAD_SORT_ARG);
2131     return JS_FALSE;
2132     }
2133     fval = argv[0]; /* non-default compare function */
2134     } else {
2135     fval = JSVAL_NULL;
2136     }
2137    
2138     obj = JS_THIS_OBJECT(cx, vp);
2139     if (!obj || !js_GetLengthProperty(cx, obj, &len))
2140     return JS_FALSE;
2141     if (len == 0) {
2142     *vp = OBJECT_TO_JSVAL(obj);
2143     return JS_TRUE;
2144     }
2145    
2146     /*
2147     * We need a temporary array of 2 * len jsvals to hold the array elements
2148     * and the scratch space for merge sort. Check that its size does not
2149     * overflow size_t, which would allow for indexing beyond the end of the
2150     * malloc'd vector.
2151     */
2152     #if JS_BITS_PER_WORD == 32
2153     if ((size_t)len > ~(size_t)0 / (2 * sizeof(jsval))) {
2154     js_ReportAllocationOverflow(cx);
2155     return JS_FALSE;
2156     }
2157     #endif
2158 siliconforks 507 vec = (jsval *) cx->malloc(2 * (size_t) len * sizeof(jsval));
2159 siliconforks 332 if (!vec)
2160     return JS_FALSE;
2161    
2162     /*
2163     * Initialize vec as a root. We will clear elements of vec one by
2164     * one while increasing tvr.count when we know that the property at
2165     * the corresponding index exists and its value must be rooted.
2166     *
2167     * In this way when sorting a huge mostly sparse array we will not
2168     * access the tail of vec corresponding to properties that do not
2169     * exist, allowing OS to avoiding committing RAM. See bug 330812.
2170     *
2171     * After this point control must flow through label out: to exit.
2172     */
2173     JS_PUSH_TEMP_ROOT(cx, 0, vec, &tvr);
2174    
2175     /*
2176     * By ECMA 262, 15.4.4.11, a property that does not exist (which we
2177     * call a "hole") is always greater than an existing property with
2178     * value undefined and that is always greater than any other property.
2179     * Thus to sort holes and undefs we simply count them, sort the rest
2180     * of elements, append undefs after them and then make holes after
2181     * undefs.
2182     */
2183     undefs = 0;
2184     newlen = 0;
2185     all_strings = JS_TRUE;
2186     for (i = 0; i < len; i++) {
2187 siliconforks 460 ok = JS_CHECK_OPERATION_LIMIT(cx);
2188 siliconforks 332 if (!ok)
2189     goto out;
2190    
2191     /* Clear vec[newlen] before including it in the rooted set. */
2192     vec[newlen] = JSVAL_NULL;
2193     tvr.count = newlen + 1;
2194     ok = GetArrayElement(cx, obj, i, &hole, &vec[newlen]);
2195     if (!ok)
2196     goto out;
2197    
2198     if (hole)
2199     continue;
2200    
2201     if (JSVAL_IS_VOID(vec[newlen])) {
2202     ++undefs;
2203     continue;
2204     }
2205    
2206     /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
2207     all_strings &= JSVAL_IS_STRING(vec[newlen]);
2208    
2209     ++newlen;
2210     }
2211    
2212     if (newlen == 0) {
2213     /* The array has only holes and undefs. */
2214     ok = JS_TRUE;
2215     goto out;
2216     }
2217    
2218     /*
2219     * The first newlen elements of vec are copied from the array object
2220     * (above). The remaining newlen positions are used as GC-rooted scratch
2221     * space for mergesort. We must clear the space before including it to
2222     * the root set covered by tvr.count. We assume JSVAL_NULL==0 to optimize
2223     * initialization using memset.
2224     */
2225     mergesort_tmp = vec + newlen;
2226     memset(mergesort_tmp, 0, newlen * sizeof(jsval));
2227     tvr.count = newlen * 2;
2228    
2229     /* Here len == 2 * (newlen + undefs + number_of_holes). */
2230     if (fval == JSVAL_NULL) {
2231     /*
2232     * Sort using the default comparator converting all elements to
2233     * strings.
2234     */
2235     if (all_strings) {
2236     elemsize = sizeof(jsval);
2237     } else {
2238     /*
2239     * To avoid string conversion on each compare we do it only once
2240     * prior to sorting. But we also need the space for the original
2241     * values to recover the sorting result. To reuse
2242     * sort_compare_strings we move the original values to the odd
2243     * indexes in vec, put the string conversion results in the even
2244     * indexes and pass 2 * sizeof(jsval) as an element size to the
2245     * sorting function. In this way sort_compare_strings will only
2246     * see the string values when it casts the compare arguments as
2247     * pointers to jsval.
2248     *
2249     * This requires doubling the temporary storage including the
2250     * scratch space for the merge sort. Since vec already contains
2251     * the rooted scratch space for newlen elements at the tail, we
2252     * can use it to rearrange and convert to strings first and try
2253     * realloc only when we know that we successfully converted all
2254     * the elements.
2255     */
2256     #if JS_BITS_PER_WORD == 32
2257     if ((size_t)newlen > ~(size_t)0 / (4 * sizeof(jsval))) {
2258     js_ReportAllocationOverflow(cx);
2259     ok = JS_FALSE;
2260     goto out;
2261     }
2262     #endif
2263    
2264     /*
2265     * Rearrange and string-convert the elements of the vector from
2266     * the tail here and, after sorting, move the results back
2267     * starting from the start to prevent overwrite the existing
2268     * elements.
2269     */
2270     i = newlen;
2271     do {
2272     --i;
2273 siliconforks 460 ok = JS_CHECK_OPERATION_LIMIT(cx);
2274 siliconforks 332 if (!ok)
2275     goto out;
2276     v = vec[i];
2277     str = js_ValueToString(cx, v);
2278     if (!str) {
2279     ok = JS_FALSE;
2280     goto out;
2281     }
2282     vec[2 * i] = STRING_TO_JSVAL(str);
2283     vec[2 * i + 1] = v;
2284     } while (i != 0);
2285    
2286     JS_ASSERT(tvr.u.array == vec);
2287 siliconforks 507 vec = (jsval *) cx->realloc(vec,
2288     4 * (size_t) newlen * sizeof(jsval));
2289 siliconforks 332 if (!vec) {
2290     vec = tvr.u.array;
2291     ok = JS_FALSE;
2292     goto out;
2293     }
2294     tvr.u.array = vec;
2295     mergesort_tmp = vec + 2 * newlen;
2296     memset(mergesort_tmp, 0, newlen * 2 * sizeof(jsval));
2297     tvr.count = newlen * 4;
2298     elemsize = 2 * sizeof(jsval);
2299     }
2300     ok = js_MergeSort(vec, (size_t) newlen, elemsize,
2301     sort_compare_strings, cx, mergesort_tmp);
2302     if (!ok)
2303     goto out;
2304     if (!all_strings) {
2305     /*
2306     * We want to make the following loop fast and to unroot the
2307     * cached results of toString invocations before the operation
2308     * callback has a chance to run the GC. For this reason we do
2309     * not call JS_CHECK_OPERATION_LIMIT in the loop.
2310     */
2311     i = 0;
2312     do {
2313     vec[i] = vec[2 * i + 1];
2314     } while (++i != newlen);
2315     }
2316     } else {
2317     void *mark;
2318    
2319 siliconforks 507 js_LeaveTrace(cx);
2320    
2321 siliconforks 332 ca.context = cx;
2322     ca.fval = fval;
2323     ca.elemroot = js_AllocStack(cx, 2 + 2, &mark);
2324     if (!ca.elemroot) {
2325     ok = JS_FALSE;
2326     goto out;
2327     }
2328     ok = js_MergeSort(vec, (size_t) newlen, sizeof(jsval),
2329 siliconforks 507 comparator_stack_cast(sort_compare),
2330     &ca, mergesort_tmp);
2331 siliconforks 332 js_FreeStack(cx, mark);
2332     if (!ok)
2333     goto out;
2334     }
2335    
2336     /*
2337     * We no longer need to root the scratch space for the merge sort, so
2338     * unroot it now to make the job of a potential GC under InitArrayElements
2339     * easier.
2340     */
2341     tvr.count = newlen;
2342 siliconforks 460 ok = InitArrayElements(cx, obj, 0, newlen, vec, TargetElementsMayContainValues,
2343     SourceVectorAllValues);
2344 siliconforks 332 if (!ok)
2345     goto out;
2346    
2347     out:
2348     JS_POP_TEMP_ROOT(cx, &tvr);
2349 siliconforks 507 cx->free(vec);
2350 siliconforks 332 if (!ok)
2351     return JS_FALSE;
2352    
2353     /* Set undefs that sorted after the rest of elements. */
2354     while (undefs != 0) {
2355     --undefs;
2356 siliconforks 460 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2357 siliconforks 332 !SetArrayElement(cx, obj, newlen++, JSVAL_VOID)) {
2358     return JS_FALSE;
2359     }
2360     }
2361    
2362     /* Re-create any holes that sorted to the end of the array. */
2363     while (len > newlen) {
2364 siliconforks 460 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2365 siliconforks 332 !DeleteArrayElement(cx, obj, --len)) {
2366     return JS_FALSE;
2367     }
2368     }
2369     *vp = OBJECT_TO_JSVAL(obj);
2370     return JS_TRUE;
2371     }
2372    
2373     /*
2374     * Perl-inspired push, pop, shift, unshift, and splice methods.
2375     */
2376 siliconforks 399 static JSBool
2377     array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2378 siliconforks 332 {
2379 siliconforks 460 jsuint length;
2380 siliconforks 332
2381     if (!js_GetLengthProperty(cx, obj, &length))
2382     return JS_FALSE;
2383 siliconforks 460 if (!InitArrayElements(cx, obj, length, argc, argv, TargetElementsMayContainValues,
2384     SourceVectorAllValues)) {
2385 siliconforks 332 return JS_FALSE;
2386 siliconforks 460 }
2387 siliconforks 332
2388     /* Per ECMA-262, return the new array length. */
2389 siliconforks 460 jsdouble newlength = length + jsdouble(argc);
2390 siliconforks 332 if (!IndexToValue(cx, newlength, rval))
2391     return JS_FALSE;
2392     return js_SetLengthProperty(cx, obj, newlength);
2393     }
2394    
2395 siliconforks 399 static JSBool
2396     array_push1_dense(JSContext* cx, JSObject* obj, jsval v, jsval *rval)
2397 siliconforks 332 {
2398     uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
2399     if (INDEX_TOO_SPARSE(obj, length)) {
2400     if (!js_MakeArraySlow(cx, obj))
2401     return JS_FALSE;
2402 siliconforks 399 return array_push_slowly(cx, obj, 1, &v, rval);
2403 siliconforks 332 }
2404    
2405 siliconforks 460 if (!EnsureCapacity(cx, obj, length + 1))
2406 siliconforks 332 return JS_FALSE;
2407     obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
2408    
2409     JS_ASSERT(obj->dslots[length] == JSVAL_HOLE);
2410     obj->fslots[JSSLOT_ARRAY_COUNT]++;
2411     obj->dslots[length] = v;
2412     return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], rval);
2413     }
2414    
2415 siliconforks 460 JSBool JS_FASTCALL
2416     js_ArrayCompPush(JSContext *cx, JSObject *obj, jsval v)
2417     {
2418     JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
2419     uint32_t length = (uint32_t) obj->fslots[JSSLOT_ARRAY_LENGTH];
2420     JS_ASSERT(length <= js_DenseArrayCapacity(obj));
2421    
2422     if (length == js_DenseArrayCapacity(obj)) {
2423 siliconforks 507 if (length > JS_ARGS_LENGTH_MAX) {
2424 siliconforks 460 JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
2425     JSMSG_ARRAY_INIT_TOO_BIG);
2426     return JS_FALSE;
2427     }
2428    
2429     if (!EnsureCapacity(cx, obj, length + 1))
2430     return JS_FALSE;
2431     }
2432     obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
2433     obj->fslots[JSSLOT_ARRAY_COUNT]++;
2434     obj->dslots[length] = v;
2435     return JS_TRUE;
2436     }
2437 siliconforks 507 JS_DEFINE_CALLINFO_3(extern, BOOL, js_ArrayCompPush, CONTEXT, OBJECT, JSVAL, 0, 0)
2438 siliconforks 460
2439 siliconforks 399 #ifdef JS_TRACER
2440     static jsval FASTCALL
2441     Array_p_push1(JSContext* cx, JSObject* obj, jsval v)
2442 siliconforks 332 {
2443 siliconforks 460 JSAutoTempValueRooter tvr(cx, v);
2444     if (OBJ_IS_DENSE_ARRAY(cx, obj)
2445     ? array_push1_dense(cx, obj, v, tvr.addr())
2446     : array_push_slowly(cx, obj, 1, tvr.addr(), tvr.addr())) {
2447     return tvr.value();
2448 siliconforks 399 }
2449 siliconforks 460 js_SetBuiltinError(cx);
2450     return JSVAL_VOID;
2451 siliconforks 399 }
2452     #endif
2453    
2454     static JSBool
2455     array_push(JSContext *cx, uintN argc, jsval *vp)
2456     {
2457 siliconforks 332 JSObject *obj;
2458    
2459     /* Insist on one argument and obj of the expected class. */
2460     obj = JS_THIS_OBJECT(cx, vp);
2461     if (!obj)
2462     return JS_FALSE;
2463     if (argc != 1 || !OBJ_IS_DENSE_ARRAY(cx, obj))
2464 siliconforks 399 return array_push_slowly(cx, obj, argc, vp + 2, vp);
2465 siliconforks 332
2466 siliconforks 399 return array_push1_dense(cx, obj, vp[2], vp);
2467 siliconforks 332 }
2468    
2469 siliconforks 399 static JSBool
2470     array_pop_slowly(JSContext *cx, JSObject* obj, jsval *vp)
2471 siliconforks 332 {
2472     jsuint index;
2473     JSBool hole;
2474    
2475     if (!js_GetLengthProperty(cx, obj, &index))
2476     return JS_FALSE;
2477     if (index == 0) {
2478     *vp = JSVAL_VOID;
2479     } else {
2480     index--;
2481    
2482     /* Get the to-be-deleted property's value into vp. */
2483     if (!GetArrayElement(cx, obj, index, &hole, vp))
2484     return JS_FALSE;
2485     if (!hole && !DeleteArrayElement(cx, obj, index))
2486     return JS_FALSE;
2487     }
2488     return js_SetLengthProperty(cx, obj, index);
2489     }
2490    
2491 siliconforks 399 static JSBool
2492     array_pop_dense(JSContext *cx, JSObject* obj, jsval *vp)
2493 siliconforks 332 {
2494     jsuint index;
2495     JSBool hole;
2496    
2497     index = obj->fslots[JSSLOT_ARRAY_LENGTH];
2498     if (index == 0) {
2499     *vp = JSVAL_VOID;
2500     return JS_TRUE;
2501     }
2502     index--;
2503     if (!GetArrayElement(cx, obj, index, &hole, vp))
2504     return JS_FALSE;
2505     if (!hole && !DeleteArrayElement(cx, obj, index))
2506     return JS_FALSE;
2507     obj->fslots[JSSLOT_ARRAY_LENGTH] = index;
2508     return JS_TRUE;
2509     }
2510    
2511 siliconforks 399 #ifdef JS_TRACER
2512     static jsval FASTCALL
2513     Array_p_pop(JSContext* cx, JSObject* obj)
2514 siliconforks 332 {
2515 siliconforks 460