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

Contents of /trunk/js/jsarray.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

1 /* -*- 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 * Array objects begin as "dense" arrays, optimized for index-only property
45 * 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 * - the net number of slots starting at dslots (capacity), in dslots[-1] if
53 * dslots is non-NULL.
54 *
55 * In dense mode, holes in the array are represented by JSVAL_HOLE. The final
56 * slot in fslots is unused.
57 *
58 * 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 * Arrays are converted to use js_SlowArrayClass when any of these conditions
64 * are met:
65 * - the load factor (COUNT / capacity) is less than 0.25, and there are
66 * more than MIN_SPARSE_INDEX slots total
67 * - a property is set that is not indexed (and not "length"); or
68 * - a property is defined that has non-default property attributes.
69 *
70 * 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 */
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 #include "jsbuiltins.h"
89 #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 #define MIN_SPARSE_INDEX 256
109
110 static inline bool
111 INDEX_TOO_BIG(jsuint index)
112 {
113 return index > JS_BIT(29) - 1;
114 }
115
116 #define INDEX_TOO_SPARSE(array, index) \
117 (INDEX_TOO_BIG(index) || \
118 ((index) > js_DenseArrayCapacity(array) && (index) >= MIN_SPARSE_INDEX && \
119 (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 IndexToValue(JSContext *cx, jsdouble index, jsval *vp)
251 {
252 return js_NewWeaklyRootedNumber(cx, index, vp);
253 }
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 ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldsize, uint32 size)
317 {
318 jsval *slots, *newslots;
319
320 if (size == 0) {
321 if (obj->dslots) {
322 JS_free(cx, obj->dslots - 1);
323 obj->dslots = NULL;
324 }
325 return JS_TRUE;
326 }
327
328 /*
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 js_ReportAllocationOverflow(cx);
334 return JS_FALSE;
335 }
336
337 slots = obj->dslots ? obj->dslots - 1 : NULL;
338 newslots = (jsval *) JS_realloc(cx, slots, (size + 1) * sizeof(jsval));
339 if (!newslots)
340 return JS_FALSE;
341
342 obj->dslots = newslots + 1;
343 js_SetDenseArrayCapacity(obj, size);
344
345 for (slots = obj->dslots + oldsize; slots < obj->dslots + size; slots++)
346 *slots = JSVAL_HOLE;
347
348 return JS_TRUE;
349 }
350
351 /*
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 static JSBool
367 EnsureCapacity(JSContext *cx, JSObject *obj, uint32 capacity)
368 {
369 uint32 oldsize = js_DenseArrayCapacity(obj);
370
371 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 }
393 return JS_TRUE;
394 }
395
396 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 /*
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 GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
435 jsval *vp)
436 {
437 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 *hole = JS_FALSE;
441 return JS_TRUE;
442 }
443
444 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 }
453
454 JSObject *obj2;
455 JSProperty *prop;
456 if (!OBJ_LOOKUP_PROPERTY(cx, obj, idr.id(), &obj2, &prop))
457 return JS_FALSE;
458 if (!prop) {
459 *hole = JS_TRUE;
460 *vp = JSVAL_VOID;
461 } else {
462 OBJ_DROP_PROPERTY(cx, obj2, prop);
463 if (!OBJ_GET_PROPERTY(cx, obj, idr.id(), vp))
464 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 SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, jsval v)
475 {
476 JS_ASSERT(index >= 0);
477
478 if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
479 /* 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 }
494
495 if (!js_MakeArraySlow(cx, obj))
496 return JS_FALSE;
497 }
498
499 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 }
507
508 static JSBool
509 DeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index)
510 {
511 JS_ASSERT(index >= 0);
512 if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
513 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 }
522 return JS_TRUE;
523 }
524
525 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 }
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 SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index,
542 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 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsdouble length)
553 {
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 /* 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 return JS_FALSE;
658 } else if (oldlen - newlen < (1 << 24)) {
659 do {
660 --oldlen;
661 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
662 !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 ok = (JS_CHECK_OPERATION_LIMIT(cx) &&
683 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 /*
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 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 if (IsDenseArrayId(cx, obj, id)) {
728 *propp = (JSProperty *) id;
729 *objp = obj;
730 return JS_TRUE;
731 }
732
733 JSObject *proto = STOBJ_GET_PROTO(obj);
734 if (!proto) {
735 *objp = NULL;
736 *propp = NULL;
737 return JS_TRUE;
738 }
739 return OBJ_LOOKUP_PROPERTY(cx, proto, id, objp, propp);
740 }
741
742 static void
743 array_dropProperty(JSContext *cx, JSObject *obj, JSProperty *prop)
744 {
745 JS_ASSERT(IsDenseArrayId(cx, obj, (jsid) prop));
746 }
747
748 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 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 if (!js_IdIsIndex(ID_TO_VALUE(id), &i) || i >= js_DenseArrayCapacity(obj) ||
781 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 if (!EnsureCapacity(cx, obj, i + 1))
867 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 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 #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 /*
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 }
938 #endif
939
940 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 JSBool isIndex;
947
948 if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
949 return JS_TRUE;
950
951 isIndex = js_IdIsIndex(ID_TO_VALUE(id), &i);
952 if (!isIndex || attrs != JSPROP_ENUMERATE) {
953 if (!ENSURE_SLOW_ARRAY(cx, obj))
954 return JS_FALSE;
955 return js_DefineProperty(cx, obj, id, value, getter, setter, attrs, propp);
956 }
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 if (js_IdIsIndex(id, &i) && i < js_DenseArrayCapacity(obj) &&
993 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 uint32 capacity, i;
1068 JSIndexIterState *ii;
1069
1070 switch (enum_op) {
1071 case JSENUMERATE_INIT:
1072 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
1073 capacity = js_DenseArrayCapacity(obj);
1074 if (idp)
1075 *idp = INT_TO_JSVAL(obj->fslots[JSSLOT_ARRAY_COUNT]);
1076 ii = NULL;
1077 for (i = 0; i != capacity; ++i) {
1078 if (obj->dslots[i] == JSVAL_HOLE) {
1079 if (!ii) {
1080 ii = (JSIndexIterState *)
1081 JS_malloc(cx, offsetof(JSIndexIterState, holes) +
1082 JS_BITMAP_SIZE(capacity));
1083 if (!ii)
1084 return JS_FALSE;
1085 ii->hasHoles = JS_TRUE;
1086 memset(ii->holes, 0, JS_BITMAP_SIZE(capacity));
1087 }
1088 JS_SET_BIT(ii->holes, i);
1089 }
1090 }
1091 if (!ii) {
1092 /* Array has no holes. */
1093 if (capacity <= PACKED_UINT_PAIR_MASK) {
1094 *statep = UINT_PAIR_TO_BOOLEAN_JSVAL(0, capacity);
1095 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 ii->length = capacity;
1105 *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 BOOLEAN_JSVAL_TO_UINT_PAIR(*statep, i, capacity);
1112 if (i != capacity) {
1113 *idp = INT_TO_JSID(i);
1114 *statep = UINT_PAIR_TO_BOOLEAN_JSVAL(i + 1, capacity);
1115 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 uint32 capacity;
1178 size_t i;
1179 jsval v;
1180
1181 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
1182
1183 capacity = js_DenseArrayCapacity(obj);
1184 for (i = 0; i < capacity; i++) {
1185 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 extern JSObjectOps js_ArrayObjectOps;
1202
1203 static const JSObjectMap SharedArrayMap = { &js_ArrayObjectOps };
1204
1205 JSObjectOps js_ArrayObjectOps = {
1206 &SharedArrayMap,
1207 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 js_HasInstance, array_trace,
1215 NULL, NULL,
1216 NULL
1217 };
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 JSScope *scope = js_NewScope(cx, &js_SlowArrayObjectOps,
1254 &js_SlowArrayClass, obj);
1255 if (!scope)
1256 return JS_FALSE;
1257
1258 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 } else {
1263 scope->freeslot = STOBJ_NSLOTS(obj);
1264 }
1265
1266 /* Create new properties pointing to existing values in dslots */
1267 for (uint32 i = 0; i < capacity; i++) {
1268 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 sprop = js_AddScopeProperty(cx, scope, id, NULL, NULL,
1280 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 {
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
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 obj->map = &scope->map;
1304 return JS_TRUE;
1305
1306 out_bad:
1307 js_DestroyScope(cx, scope);
1308 return JS_FALSE;
1309 }
1310
1311 enum ArrayToStringOp {
1312 TO_STRING,
1313 TO_LOCALE_STRING,
1314 TO_SOURCE
1315 };
1316
1317 /*
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 static JSBool
1323 array_join_sub(JSContext *cx, JSObject *obj, enum ArrayToStringOp op,
1324 JSString *sep, jsval *rval)
1325 {
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 /*
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 #if JS_HAS_SHARP_VARS
1356 nchars = js_strlen(chars);
1357 #else
1358 chars[0] = '[';
1359 chars[1] = ']';
1360 chars[2] = 0;
1361 nchars = 2;
1362 #endif
1363 goto make_string;
1364 }
1365
1366 if (op == TO_SOURCE) {
1367 /*
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 ok = (JS_CHECK_OPERATION_LIMIT(cx) &&
1426 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 return array_join_sub(cx, obj, TO_SOURCE, NULL, vp);
1548 }
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 return array_join_sub(cx, obj, TO_STRING, NULL, vp);
1562 }
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 return array_join_sub(cx, obj, TO_LOCALE_STRING, NULL, vp);
1580 }
1581
1582 enum TargetElementsType {
1583 TargetElementsAllHoles,
1584 TargetElementsMayContainValues
1585 };
1586
1587 enum SourceVectorType {
1588 SourceVectorAllValues,
1589 SourceVectorMayContainHoles
1590 };
1591
1592 static JSBool
1593 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, jsval *vector,
1594 TargetElementsType targetType, SourceVectorType vectorType)
1595 {
1596 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 return JS_FALSE;
1628
1629 if (newlen > uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
1630 obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
1631
1632 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 return JS_TRUE;
1655 }
1656
1657 jsval* end = vector + count;
1658 while (vector != end && start < MAXINDEX) {
1659 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1660 !SetArrayElement(cx, obj, start++, *vector++)) {
1661 return JS_FALSE;
1662 }
1663 }
1664
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 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 if (!EnsureCapacity(cx, obj, length))
1702 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 #ifdef JS_TRACER
1722 static JSString* FASTCALL
1723 Array_p_join(JSContext* cx, JSObject* obj, JSString *str)
1724 {
1725 JSAutoTempValueRooter tvr(cx);
1726 if (!array_join_sub(cx, obj, TO_STRING, str, tvr.addr())) {
1727 js_SetBuiltinError(cx);
1728 return NULL;
1729 }
1730 return JSVAL_TO_STRING(tvr.value());
1731 }
1732
1733 static JSString* FASTCALL
1734 Array_p_toString(JSContext* cx, JSObject* obj)
1735 {
1736 JSAutoTempValueRooter tvr(cx);
1737 if (!array_join_sub(cx, obj, TO_STRING, NULL, tvr.addr())) {
1738 js_SetBuiltinError(cx);
1739 return NULL;
1740 }
1741 return JSVAL_TO_STRING(tvr.value());
1742 }
1743 #endif
1744
1745 /*
1746 * Perl-inspired join, reverse, and sort.
1747 */
1748 static JSBool
1749 array_join(JSContext *cx, uintN argc, jsval *vp)
1750 {
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 return obj && array_join_sub(cx, obj, TO_STRING, str, vp);
1764 }
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 *vp = OBJECT_TO_JSVAL(obj);
1778
1779 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 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 ok = JS_CHECK_OPERATION_LIMIT(cx) &&
1817 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 static JS_REQUIRES_STACK JSBool
1839 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 JS_REQUIRES_STACK JSBool
1900 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 static JS_REQUIRES_STACK JSBool
1986 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 if (!JS_CHECK_OPERATION_LIMIT(cx))
2002 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 if (!JS_CHECK_OPERATION_LIMIT((JSContext *)arg))
2040 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 static JS_REQUIRES_STACK JSBool
2054 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 JSBool ok;
2063 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 ok = JS_CHECK_OPERATION_LIMIT(cx);
2134 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 ok = JS_CHECK_OPERATION_LIMIT(cx);
2220 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 ok = InitArrayElements(cx, obj, 0, newlen, vec, TargetElementsMayContainValues,
2286 SourceVectorAllValues);
2287 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 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2300 !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 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2308 !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 static JSBool
2320 array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2321 {
2322 jsuint length;
2323
2324 if (!js_GetLengthProperty(cx, obj, &length))
2325 return JS_FALSE;
2326 if (!InitArrayElements(cx, obj, length, argc, argv, TargetElementsMayContainValues,
2327 SourceVectorAllValues)) {
2328 return JS_FALSE;
2329 }
2330
2331 /* Per ECMA-262, return the new array length. */
2332 jsdouble newlength = length + jsdouble(argc);
2333 if (!IndexToValue(cx, newlength, rval))
2334 return JS_FALSE;
2335 return js_SetLengthProperty(cx, obj, newlength);
2336 }
2337
2338 static JSBool
2339 array_push1_dense(JSContext* cx, JSObject* obj, jsval v, jsval *rval)
2340 {
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 return array_push_slowly(cx, obj, 1, &v, rval);
2346 }
2347
2348 if (!EnsureCapacity(cx, obj, length + 1))
2349 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 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 #ifdef JS_TRACER
2382 static jsval FASTCALL
2383 Array_p_push1(JSContext* cx, JSObject* obj, jsval v)
2384 {
2385 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 }
2391 js_SetBuiltinError(cx);
2392 return JSVAL_VOID;
2393 }
2394 #endif
2395
2396 static JSBool
2397 array_push(JSContext *cx, uintN argc, jsval *vp)
2398 {
2399 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 return array_push_slowly(cx, obj, argc, vp + 2, vp);
2407
2408 return array_push1_dense(cx, obj, vp[2], vp);
2409 }
2410
2411 static JSBool
2412 array_pop_slowly(JSContext *cx, JSObject* obj, jsval *vp)
2413 {
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 static JSBool
2434 array_pop_dense(JSContext *cx, JSObject* obj, jsval *vp)
2435 {
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 #ifdef JS_TRACER
2454 static jsval FASTCALL
2455 Array_p_pop(JSContext* cx, JSObject* obj)
2456 {
2457 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 }
2463 js_SetBuiltinError(cx);
2464 return JSVAL_VOID;
2465 }
2466 #endif
2467
2468 static JSBool
2469 array_pop(JSContext *cx, uintN argc, jsval *vp)
2470 {
2471 JSObject *obj;
2472
2473 obj = JS_THIS_OBJECT(cx, vp);
2474 if (!obj)
2475 return JS_FALSE;
2476 if (OBJ_IS_DENSE_ARRAY(cx, obj))
2477 return array_pop_dense(cx, obj, vp);
2478 return array_pop_slowly(cx, obj, vp);
2479 }
2480
2481 static JSBool
2482 array_shift(JSContext *cx, uintN argc, jsval *vp)
2483 {
2484 JSObject *obj;
2485 jsuint length, i;
2486 JSBool hole;
2487
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 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
2520 /* 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 }
2534 }
2535 return js_SetLengthProperty(cx, obj, length);
2536 }
2537
2538 static JSBool
2539 array_unshift(JSContext *cx, uintN argc, jsval *vp)
2540 {
2541 JSObject *obj;
2542 jsval *argv;
2543 jsuint length;
2544 JSBool hole;
2545 jsdouble last, newlen;
2546
2547 obj = JS_THIS_OBJECT(cx, vp);
2548 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2549 return JS_FALSE;
2550 newlen = length;
2551 if (argc > 0) {
2552 /* Slide up the array to make room for argc at the bottom. */
2553 argv = JS_ARGV(cx, vp);
2554 if (length > 0) {
2555 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2556 !INDEX_TOO_SPARSE(obj, newlen + argc)) {
2557 JS_ASSERT(newlen + argc == length + argc);
2558 if (!EnsureCapacity(cx, obj, length + argc))
2559 return JS_FALSE;
2560 memmove(obj->dslots + argc, obj->dslots, length * sizeof(jsval));
2561 for (uint32 i = 0; i < argc; i++)
2562 obj->dslots[i] = JSVAL_HOLE;
2563 } else {
2564 last = length;
2565 jsdouble upperIndex = last + argc;
2566 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2567 do {
2568 --last, --upperIndex;
2569 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2570 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2571 !SetOrDeleteArrayElement(cx, obj, upperIndex, hole, tvr.value())) {
2572 return JS_FALSE;
2573 }
2574 } while (last != 0);
2575 }
2576 }
2577
2578 /* Copy from argv to the bottom of the array. */
2579 if (!InitArrayElements(cx, obj, 0, argc, argv, TargetElementsAllHoles, SourceVectorAllValues))
2580 return JS_FALSE;
2581
2582 newlen += argc;
2583 if (!js_SetLengthProperty(cx, obj, newlen))
2584 return JS_FALSE;
2585 }
2586
2587 /* Follow Perl by returning the new array length. */
2588 return IndexToValue(cx, newlen, vp);
2589 }
2590
2591 static JSBool
2592 array_splice(JSContext *cx, uintN argc, jsval *vp)
2593 {
2594 jsval *argv;
2595 JSObject *obj;
2596 jsuint length, begin, end, count, delta, last;
2597 jsdouble d;
2598 JSBool hole;
2599 JSObject *obj2;
2600
2601 /*
2602 * Create a new array value to return. Our ECMA v2 proposal specs
2603 * that splice always returns an array value, even when given no
2604 * arguments. We think this is best because it eliminates the need
2605 * for callers to do an extra test to handle the empty splice case.
2606 */
2607 obj2 = js_NewArrayObject(cx, 0, NULL);
2608 if (!obj2)
2609 return JS_FALSE;
2610 *vp = OBJECT_TO_JSVAL(obj2);
2611
2612 /* Nothing to do if no args. Otherwise get length. */
2613 if (argc == 0)
2614 return JS_TRUE;
2615 argv = JS_ARGV(cx, vp);
2616 obj = JS_THIS_OBJECT(cx, vp);
2617 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2618 return JS_FALSE;
2619
2620 /* Convert the first argument into a starting index. */
2621 d = js_ValueToNumber(cx, argv);
2622 if (JSVAL_IS_NULL(*argv))
2623 return JS_FALSE;
2624 d = js_DoubleToInteger(d);
2625 if (d < 0) {
2626 d += length;
2627 if (d < 0)
2628 d = 0;
2629 } else if (d > length) {
2630 d = length;
2631 }
2632 begin = (jsuint)d; /* d has been clamped to uint32 */
2633 argc--;
2634 argv++;
2635
2636 /* Convert the second argument from a count into a fencepost index. */
2637 delta = length - begin;
2638 if (argc == 0) {
2639 count = delta;
2640 end = length;
2641 } else {
2642 d = js_ValueToNumber(cx, argv);
2643 if (JSVAL_IS_NULL(*argv))
2644 return JS_FALSE;
2645 d = js_DoubleToInteger(d);
2646 if (d < 0)
2647 d = 0;
2648 else if (d > delta)
2649 d = delta;
2650 count = (jsuint)d;
2651 end = begin + count;
2652 argc--;
2653 argv++;
2654 }
2655
2656 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2657
2658 /* If there are elements to remove, put them into the return value. */
2659 if (count > 0) {
2660 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2661 !js_PrototypeHasIndexedProperties(cx, obj2) &&
2662 end <= js_DenseArrayCapacity(obj)) {
2663 if (!InitArrayObject(cx, obj2, count, obj->dslots + begin,
2664 obj->fslots[JSSLOT_ARRAY_COUNT] !=
2665 obj->fslots[JSSLOT_ARRAY_LENGTH])) {
2666 return JS_FALSE;
2667 }
2668 } else {
2669 for (last = begin; last < end; last++) {
2670 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2671 !GetArrayElement(cx, obj, last, &hole, tvr.addr())) {
2672 return JS_FALSE;
2673 }
2674
2675 /* Copy tvr.value() to the new array unless it's a hole. */
2676 if (!hole && !SetArrayElement(cx, obj2, last - begin, tvr.value()))
2677 return JS_FALSE;
2678 }
2679
2680 if (!js_SetLengthProperty(cx, obj2, count))
2681 return JS_FALSE;
2682 }
2683 }
2684
2685 /* Find the direction (up or down) to copy and make way for argv. */
2686 if (argc > count) {
2687 delta = (jsuint)argc - count;
2688 last = length;
2689 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2690 length <= js_DenseArrayCapacity(obj) &&
2691 (length == 0 || obj->dslots[length - 1] != JSVAL_HOLE)) {
2692 if (!EnsureCapacity(cx, obj, length + delta))
2693 return JS_FALSE;
2694 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2695 while (last-- > end) {
2696 jsval srcval = obj->dslots[last];
2697 jsval* dest = &obj->dslots[last + delta];
2698 if (*dest == JSVAL_HOLE && srcval != JSVAL_HOLE)
2699 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2700 *dest = srcval;
2701 }
2702 obj->fslots[JSSLOT_ARRAY_LENGTH] += delta;
2703 } else {
2704 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2705 while (last-- > end) {
2706 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2707 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2708 !SetOrDeleteArrayElement(cx, obj, last + delta, hole, tvr.value())) {
2709 return JS_FALSE;
2710 }
2711 }
2712 }
2713 length += delta;
2714 } else if (argc < count) {
2715 delta = count - (jsuint)argc;
2716 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2717 length <= js_DenseArrayCapacity(obj)) {
2718 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2719 for (last = end; last < length; last++) {
2720 jsval srcval = obj->dslots[last];
2721 jsval* dest = &obj->dslots[last - delta];
2722 if (*dest == JSVAL_HOLE && srcval != JSVAL_HOLE)
2723 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2724 *dest = srcval;
2725 }
2726 } else {
2727 for (last = end; last < length; last++) {
2728 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2729 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2730 !SetOrDeleteArrayElement(cx, obj, last - delta, hole, tvr.value())) {
2731 return JS_FALSE;
2732 }
2733 }
2734 }
2735 length -= delta;
2736 }
2737
2738 /*
2739 * Copy from argv into the hole to complete the splice, and update length in
2740 * case we deleted elements from the end.
2741 */
2742 return InitArrayElements(cx, obj, begin, argc, argv, TargetElementsMayContainValues,
2743 SourceVectorAllValues) &&
2744 js_SetLengthProperty(cx, obj, length);
2745 }
2746
2747 /*
2748 * Python-esque sequence operations.
2749 */
2750 static JSBool
2751 array_concat(JSContext *cx, uintN argc, jsval *vp)
2752 {
2753 jsval *argv, v;
2754 JSObject *aobj, *nobj;
2755 jsuint length, alength, slot;
2756 uintN i;
2757 JSBool hole, ok;
2758 JSTempValueRooter tvr;
2759
2760 /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
2761 argv = JS_ARGV(cx, vp) - 1;
2762 JS_ASSERT(JS_THIS_OBJECT(cx, vp) == JSVAL_TO_OBJECT(argv[0]));
2763
2764 /* Create a new Array object and root it using *vp. */
2765 aobj = JS_THIS_OBJECT(cx, vp);
2766 if (OBJ_IS_DENSE_ARRAY(cx, aobj)) {
2767 /*
2768 * Clone aobj but pass the minimum of its length and capacity, to
2769 * handle a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In
2770 * such a case we'll pass 8 (not 3) due to ARRAY_CAPACITY_MIN, which
2771 * will cause nobj to be over-allocated to 16. But in the normal case
2772 * where length is <= capacity, nobj and aobj will have the same
2773 * capacity.
2774 */
2775 length = aobj->fslots[JSSLOT_ARRAY_LENGTH];
2776 jsuint capacity = js_DenseArrayCapacity(aobj);
2777 nobj = js_NewArrayObject(cx, JS_MIN(length, capacity), aobj->dslots,
2778 aobj->fslots[JSSLOT_ARRAY_COUNT] !=
2779 (jsval) length);
2780 if (!nobj)
2781 return JS_FALSE;
2782 nobj->fslots[JSSLOT_ARRAY_LENGTH] = length;
2783 *vp = OBJECT_TO_JSVAL(nobj);
2784 if (argc == 0)
2785 return JS_TRUE;
2786 argc--;
2787 argv++;
2788 } else {
2789 nobj = js_NewArrayObject(cx, 0, NULL);
2790 if (!nobj)
2791 return JS_FALSE;
2792 *vp = OBJECT_TO_JSVAL(nobj);
2793 length = 0;
2794 }
2795
2796 MUST_FLOW_THROUGH("out");
2797 JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
2798
2799 /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
2800 for (i = 0; i <= argc; i++) {
2801 ok = JS_CHECK_OPERATION_LIMIT(cx);
2802 if (!ok)
2803 goto out;
2804 v = argv[i];
2805 if (!JSVAL_IS_PRIMITIVE(v)) {
2806 JSObject *wobj;
2807
2808 aobj = JSVAL_TO_OBJECT(v);
2809 wobj = js_GetWrappedObject(cx, aobj);
2810 if (OBJ_IS_ARRAY(cx, wobj)) {
2811 ok = OBJ_GET_PROPERTY(cx, aobj,
2812 ATOM_TO_JSID(cx->runtime->atomState
2813 .lengthAtom),
2814 &tvr.u.value);
2815 if (!ok)
2816 goto out;
2817 alength = ValueIsLength(cx, &tvr.u.value);
2818 ok = !JSVAL_IS_NULL(tvr.u.value);
2819 if (!ok)
2820 goto out;
2821 for (slot = 0; slot < alength; slot++) {
2822 ok = JS_CHECK_OPERATION_LIMIT(cx) &&
2823 GetArrayElement(cx, aobj, slot, &hole,
2824 &tvr.u.value);
2825 if (!ok)
2826 goto out;
2827
2828 /*
2829 * Per ECMA 262, 15.4.4.4, step 9, ignore non-existent
2830 * properties.
2831 */
2832 if (!hole) {
2833 ok = SetArrayElement(cx, nobj, length + slot,
2834 tvr.u.value);
2835 if (!ok)
2836 goto out;
2837 }
2838 }
2839 length += alength;
2840 continue;
2841 }
2842 }
2843
2844 ok = SetArrayElement(cx, nobj, length, v);
2845 if (!ok)
2846 goto out;
2847 length++;
2848 }
2849
2850 ok = js_SetLengthProperty(cx, nobj, length);
2851
2852 out:
2853 JS_POP_TEMP_ROOT(cx, &tvr);
2854 return ok;
2855 }
2856
2857 static JSBool
2858 array_slice(JSContext *cx, uintN argc, jsval *vp)
2859 {
2860 jsval *argv;
2861 JSObject *nobj, *obj;
2862 jsuint length, begin, end, slot;
2863 jsdouble d;
2864 JSBool hole;
2865
2866 argv = JS_ARGV(cx, vp);
2867
2868 obj = JS_THIS_OBJECT(cx, vp);
2869 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2870 return JS_FALSE;
2871 begin = 0;
2872 end = length;
2873
2874 if (argc > 0) {
2875 d = js_ValueToNumber(cx, &argv[0]);
2876 if (JSVAL_IS_NULL(argv[0]))
2877 return JS_FALSE;
2878 d = js_DoubleToInteger(d);
2879 if (d < 0) {
2880 d += length;
2881 if (d < 0)
2882 d = 0;
2883 } else if (d > length) {
2884 d = length;
2885 }
2886 begin = (jsuint)d;
2887
2888 if (argc > 1) {
2889 d = js_ValueToNumber(cx, &argv[1]);
2890 if (JSVAL_IS_NULL(argv[1]))
2891 return JS_FALSE;
2892 d = js_DoubleToInteger(d);
2893 if (d < 0) {
2894 d += length;
2895 if (d < 0)
2896 d = 0;
2897 } else if (d > length) {
2898 d = length;
2899 }
2900 end = (jsuint)d;
2901 }
2902 }
2903
2904 if (begin > end)
2905 begin = end;
2906
2907 if (OBJ_IS_DENSE_ARRAY(cx, obj) && end <= js_DenseArrayCapacity(obj) &&
2908 !js_PrototypeHasIndexedProperties(cx, obj)) {
2909 nobj = js_NewArrayObject(cx, end - begin, obj->dslots + begin,
2910 obj->fslots[JSSLOT_ARRAY_COUNT] !=
2911 obj->fslots[JSSLOT_ARRAY_LENGTH]);
2912 if (!nobj)
2913 return JS_FALSE;
2914 *vp = OBJECT_TO_JSVAL(nobj);
2915 return JS_TRUE;
2916 }
2917
2918 /* Create a new Array object and root it using *vp. */
2919 nobj = js_NewArrayObject(cx, 0, NULL);
2920 if (!nobj)
2921 return JS_FALSE;
2922 *vp = OBJECT_TO_JSVAL(nobj);
2923
2924 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2925 for (slot = begin; slot < end; slot++) {
2926 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2927 !GetArrayElement(cx, obj, slot, &hole, tvr.addr())) {
2928 return JS_FALSE;
2929 }
2930 if (!hole && !SetArrayElement(cx, nobj, slot - begin, tvr.value()))
2931 return JS_FALSE;
2932 }
2933
2934 return js_SetLengthProperty(cx, nobj, end - begin);
2935 }
2936
2937 #if JS_HAS_ARRAY_EXTRAS
2938
2939 static JSBool
2940 array_indexOfHelper(JSContext *cx, JSBool isLast, uintN argc, jsval *vp)
2941 {
2942 JSObject *obj;
2943 jsuint length, i, stop;
2944 jsval tosearch;
2945 jsint direction;
2946 JSBool hole;
2947
2948 obj = JS_THIS_OBJECT(cx, vp);
2949 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2950 return JS_FALSE;
2951 if (length == 0)
2952 goto not_found;
2953
2954 if (argc <= 1) {
2955 i = isLast ? length - 1 : 0;
2956 tosearch = (argc != 0) ? vp[2] : JSVAL_VOID;
2957 } else {
2958 jsdouble start;
2959
2960 tosearch = vp[2];
2961 start = js_ValueToNumber(cx, &vp[3]);
2962 if (JSVAL_IS_NULL(vp[3]))
2963 return JS_FALSE;
2964 start = js_DoubleToInteger(start);
2965 if (start < 0) {
2966 start += length;
2967 if (start < 0) {
2968 if (isLast)
2969 goto not_found;
2970 i = 0;
2971 } else {
2972 i = (jsuint)start;
2973 }
2974 } else if (start >= length) {
2975 if (!isLast)
2976 goto not_found;
2977 i = length - 1;
2978 } else {
2979 i = (jsuint)start;
2980 }
2981 }
2982
2983 if (isLast) {
2984 stop = 0;
2985 direction = -1;
2986 } else {
2987 stop = length - 1;
2988 direction = 1;
2989 }
2990
2991 for (;;) {
2992 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2993 !GetArrayElement(cx, obj, (jsuint)i, &hole, vp)) {
2994 return JS_FALSE;
2995 }
2996 if (!hole && js_StrictlyEqual(cx, *vp, tosearch))
2997 return js_NewNumberInRootedValue(cx, i, vp);
2998 if (i == stop)
2999 goto not_found;
3000 i += direction;
3001 }
3002
3003 not_found:
3004 *vp = INT_TO_JSVAL(-1);
3005 return JS_TRUE;
3006 }
3007
3008 static JSBool
3009 array_indexOf(JSContext *cx, uintN argc, jsval *vp)
3010 {
3011 return array_indexOfHelper(cx, JS_FALSE, argc, vp);
3012 }
3013
3014 static JSBool
3015 array_lastIndexOf(JSContext *cx, uintN argc, jsval *vp)
3016 {
3017 return array_indexOfHelper(cx, JS_TRUE, argc, vp);
3018 }
3019
3020 /* Order is important; extras that take a predicate funarg must follow MAP. */
3021 typedef enum ArrayExtraMode {
3022 FOREACH,
3023 REDUCE,
3024 REDUCE_RIGHT,
3025 MAP,
3026 FILTER,
3027 SOME,
3028 EVERY
3029 } ArrayExtraMode;
3030
3031 #define REDUCE_MODE(mode) ((mode) == REDUCE || (mode) == REDUCE_RIGHT)
3032
3033 static JS_REQUIRES_STACK JSBool
3034 array_extra(JSContext *cx, ArrayExtraMode mode, uintN argc, jsval *vp)
3035 {
3036 JSObject *obj;
3037 jsuint length, newlen;
3038 jsval *argv, *elemroot, *invokevp, *sp;
3039 JSBool ok, cond, hole;
3040 JSObject *callable, *thisp, *newarr;
3041 jsint start, end, step, i;
3042 void *mark;
3043
3044 obj = JS_THIS_OBJECT(cx, vp);
3045 if (!obj || !js_GetLengthProperty(cx, obj, &length))
3046 return JS_FALSE;
3047
3048 /*
3049 * First, get or compute our callee, so that we error out consistently
3050 * when passed a non-callable object.
3051 */
3052 if (argc == 0) {
3053 js_ReportMissingArg(cx, vp, 0);
3054 return JS_FALSE;
3055 }
3056 argv = vp + 2;
3057 callable = js_ValueToCallableObject(cx, &argv[0], JSV2F_SEARCH_STACK);
3058 if (!callable)
3059 return JS_FALSE;
3060
3061 /*
3062 * Set our initial return condition, used for zero-length array cases
3063 * (and pre-size our map return to match our known length, for all cases).
3064 */
3065 #ifdef __GNUC__ /* quell GCC overwarning */
3066 newlen = 0;
3067 newarr = NULL;
3068 #endif
3069 start = 0, end = length, step = 1;
3070
3071 switch (mode) {
3072 case REDUCE_RIGHT:
3073 start = length - 1, end = -1, step = -1;
3074 /* FALL THROUGH */
3075 case REDUCE:
3076 if (length == 0 && argc == 1) {
3077 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3078 JSMSG_EMPTY_ARRAY_REDUCE);
3079 return JS_FALSE;
3080 }
3081 if (argc >= 2) {
3082 *vp = argv[1];
3083 } else {
3084 do {
3085 if (!GetArrayElement(cx, obj, start, &hole, vp))
3086 return JS_FALSE;
3087 start += step;
3088 } while (hole && start != end);
3089
3090 if (hole && start == end) {
3091 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3092 JSMSG_EMPTY_ARRAY_REDUCE);
3093 return JS_FALSE;
3094 }
3095 }
3096 break;
3097 case MAP:
3098 case FILTER:
3099 newlen = (mode == MAP) ? length : 0;
3100 newarr = js_NewArrayObject(cx, newlen, NULL);
3101 if (!newarr)
3102 return JS_FALSE;
3103 *vp = OBJECT_TO_JSVAL(newarr);
3104 break;
3105 case SOME:
3106 *vp = JSVAL_FALSE;
3107 break;
3108 case EVERY:
3109 *vp = JSVAL_TRUE;
3110 break;
3111 case FOREACH:
3112 *vp = JSVAL_VOID;
3113 break;
3114 }
3115
3116 if (length == 0)
3117 return JS_TRUE;
3118
3119 if (argc > 1 && !REDUCE_MODE(mode)) {
3120 if (!js_ValueToObject(cx, argv[1], &thisp))
3121 return JS_FALSE;
3122 argv[1] = OBJECT_TO_JSVAL(thisp);
3123 } else {
3124 thisp = NULL;
3125 }
3126
3127 /*
3128 * For all but REDUCE, we call with 3 args (value, index, array). REDUCE
3129 * requires 4 args (accum, value, index, array).
3130 */
3131 argc = 3 + REDUCE_MODE(mode);
3132 elemroot = js_AllocStack(cx, 1 + 2 + argc, &mark);
3133 if (!elemroot)
3134 return JS_FALSE;
3135
3136 MUST_FLOW_THROUGH("out");
3137 ok = JS_TRUE;
3138 invokevp = elemroot + 1;
3139
3140 for (i = start; i != end; i += step) {
3141 ok = JS_CHECK_OPERATION_LIMIT(cx) &&
3142 GetArrayElement(cx, obj, i, &hole, elemroot);
3143 if (!ok)
3144 goto out;
3145 if (hole)
3146 continue;
3147
3148 /*
3149 * Push callable and 'this', then args. We must do this for every
3150 * iteration around the loop since js_Invoke uses spbase[0] for return
3151 * value storage, while some native functions use spbase[1] for local
3152 * rooting.
3153 */
3154 sp = invokevp;
3155 *sp++ = OBJECT_TO_JSVAL(callable);
3156 *sp++ = OBJECT_TO_JSVAL(thisp);
3157 if (REDUCE_MODE(mode))
3158 *sp++ = *vp;
3159 *sp++ = *elemroot;
3160 *sp++ = INT_TO_JSVAL(i);
3161 *sp++ = OBJECT_TO_JSVAL(obj);
3162
3163 /* Do the call. */
3164 ok = js_Invoke(cx, argc, invokevp, 0);
3165 if (!ok)
3166 break;
3167
3168 if (mode > MAP)
3169 cond = js_ValueToBoolean(*invokevp);
3170 #ifdef __GNUC__ /* quell GCC overwarning */
3171 else
3172 cond = JS_FALSE;
3173 #endif
3174
3175 switch (mode) {
3176 case FOREACH:
3177 break;
3178 case REDUCE:
3179 case REDUCE_RIGHT:
3180 *vp = *invokevp;
3181 break;
3182 case MAP:
3183 ok = SetArrayElement(cx, newarr, i, *invokevp);
3184 if (!ok)
3185 goto out;
3186 break;
3187 case FILTER:
3188 if (!cond)
3189 break;
3190 /* The filter passed *elemroot, so push it onto our result. */
3191 ok = SetArrayElement(cx, newarr, newlen++, *elemroot);
3192 if (!ok)
3193 goto out;
3194 break;
3195 case SOME:
3196 if (cond) {
3197 *vp = JSVAL_TRUE;
3198 goto out;
3199 }
3200 break;
3201 case EVERY:
3202 if (!cond) {
3203 *vp = JSVAL_FALSE;
3204 goto out;
3205 }
3206 break;
3207 }
3208 }
3209
3210 out:
3211 js_FreeStack(cx, mark);
3212 if (ok && mode == FILTER)
3213 ok = js_SetLengthProperty(cx, newarr, newlen);
3214 return ok;
3215 }
3216
3217 static JS_REQUIRES_STACK JSBool
3218 array_forEach(JSContext *cx, uintN argc, jsval *vp)
3219 {
3220 return array_extra(cx, FOREACH, argc, vp);
3221 }
3222
3223 static JS_REQUIRES_STACK JSBool
3224 array_map(JSContext *cx, uintN argc, jsval *vp)
3225 {
3226 return array_extra(cx, MAP, argc, vp);
3227 }
3228
3229 static JS_REQUIRES_STACK JSBool
3230 array_reduce(JSContext *cx, uintN argc, jsval *vp)
3231 {
3232 return array_extra(cx, REDUCE, argc, vp);
3233 }
3234
3235 static JS_REQUIRES_STACK JSBool
3236 array_reduceRight(JSContext *cx, uintN argc, jsval *vp)
3237 {
3238 return array_extra(cx, REDUCE_RIGHT, argc, vp);
3239 }
3240
3241 static JS_REQUIRES_STACK JSBool
3242 array_filter(JSContext *cx, uintN argc, jsval *vp)
3243 {
3244 return array_extra(cx, FILTER, argc, vp);
3245 }
3246
3247 static JS_REQUIRES_STACK JSBool
3248 array_some(JSContext *cx, uintN argc, jsval *vp)
3249 {
3250 return array_extra(cx, SOME, argc, vp);
3251 }
3252
3253 static JS_REQUIRES_STACK JSBool
3254 array_every(JSContext *cx, uintN argc, jsval *vp)
3255 {
3256 return array_extra(cx, EVERY, argc, vp);
3257 }
3258 #endif
3259
3260 static JSPropertySpec array_props[] = {
3261 {js_length_str, -1, JSPROP_SHARED | JSPROP_PERMANENT,
3262 array_length_getter, array_length_setter},
3263 {0,0,0,0,0}
3264 };
3265
3266