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

Annotation of /trunk/js/jsarray.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 460 - (hide annotations)
Sat Sep 26 23:15:22 2009 UTC (12 years, 9 months ago) by siliconforks
File size: 111874 byte(s)
Upgrade to SpiderMonkey from Firefox 3.5.3.

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