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

Contents of /trunk/js/jsarray.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

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 <stdlib.h>
79 #include <string.h>
80 #include "jstypes.h"
81 #include "jsstdint.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 "jstracer.h"
89 #include "jsbuiltins.h"
90 #include "jscntxt.h"
91 #include "jsversion.h"
92 #include "jsdbgapi.h" /* for js_TraceWatchPoints */
93 #include "jsdtoa.h"
94 #include "jsfun.h"
95 #include "jsgc.h"
96 #include "jsinterp.h"
97 #include "jslock.h"
98 #include "jsnum.h"
99 #include "jsobj.h"
100 #include "jsscope.h"
101 #include "jsstr.h"
102 #include "jsstaticcheck.h"
103 #include "jsvector.h"
104
105 #include "jsatominlines.h"
106
107 /* 2^32 - 1 as a number and a string */
108 #define MAXINDEX 4294967295u
109 #define MAXSTR "4294967295"
110
111 /* Small arrays are dense, no matter what. */
112 #define MIN_SPARSE_INDEX 256
113
114 static inline bool
115 INDEX_TOO_BIG(jsuint index)
116 {
117 return index > JS_BIT(29) - 1;
118 }
119
120 #define INDEX_TOO_SPARSE(array, index) \
121 (INDEX_TOO_BIG(index) || \
122 ((index) > js_DenseArrayCapacity(array) && (index) >= MIN_SPARSE_INDEX && \
123 (index) > (uint32)((array)->fslots[JSSLOT_ARRAY_COUNT] + 1) * 4))
124
125 JS_STATIC_ASSERT(sizeof(JSScopeProperty) > 4 * sizeof(jsval));
126
127 #define ENSURE_SLOW_ARRAY(cx, obj) \
128 (OBJ_GET_CLASS(cx, obj) == &js_SlowArrayClass || js_MakeArraySlow(cx, obj))
129
130 /*
131 * Determine if the id represents an array index or an XML property index.
132 *
133 * An id is an array index according to ECMA by (15.4):
134 *
135 * "Array objects give special treatment to a certain class of property names.
136 * A property name P (in the form of a string value) is an array index if and
137 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
138 * to 2^32-1."
139 *
140 * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
141 * except that by using signed 32-bit integers we miss the top half of the
142 * valid range. This function checks the string representation itself; note
143 * that calling a standard conversion routine might allow strings such as
144 * "08" or "4.0" as array indices, which they are not.
145 */
146 JSBool
147 js_IdIsIndex(jsval id, jsuint *indexp)
148 {
149 JSString *str;
150 jschar *cp;
151
152 if (JSVAL_IS_INT(id)) {
153 jsint i;
154 i = JSVAL_TO_INT(id);
155 if (i < 0)
156 return JS_FALSE;
157 *indexp = (jsuint)i;
158 return JS_TRUE;
159 }
160
161 /* NB: id should be a string, but jsxml.c may call us with an object id. */
162 if (!JSVAL_IS_STRING(id))
163 return JS_FALSE;
164
165 str = JSVAL_TO_STRING(id);
166 cp = str->chars();
167 if (JS7_ISDEC(*cp) && str->length() < sizeof(MAXSTR)) {
168 jsuint index = JS7_UNDEC(*cp++);
169 jsuint oldIndex = 0;
170 jsuint c = 0;
171 if (index != 0) {
172 while (JS7_ISDEC(*cp)) {
173 oldIndex = index;
174 c = JS7_UNDEC(*cp);
175 index = 10*index + c;
176 cp++;
177 }
178 }
179
180 /* Ensure that all characters were consumed and we didn't overflow. */
181 if (*cp == 0 &&
182 (oldIndex < (MAXINDEX / 10) ||
183 (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
184 {
185 *indexp = index;
186 return JS_TRUE;
187 }
188 }
189 return JS_FALSE;
190 }
191
192 static jsuint
193 ValueIsLength(JSContext *cx, jsval* vp)
194 {
195 jsint i;
196 jsdouble d;
197 jsuint length;
198
199 if (JSVAL_IS_INT(*vp)) {
200 i = JSVAL_TO_INT(*vp);
201 if (i < 0)
202 goto error;
203 return (jsuint) i;
204 }
205
206 d = js_ValueToNumber(cx, vp);
207 if (JSVAL_IS_NULL(*vp))
208 goto error;
209
210 if (JSDOUBLE_IS_NaN(d))
211 goto error;
212 length = (jsuint) d;
213 if (d != (jsdouble) length)
214 goto error;
215 return length;
216
217 error:
218 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
219 JSMSG_BAD_ARRAY_LENGTH);
220 *vp = JSVAL_NULL;
221 return 0;
222 }
223
224 JSBool
225 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
226 {
227 if (OBJ_IS_ARRAY(cx, obj)) {
228 *lengthp = obj->fslots[JSSLOT_ARRAY_LENGTH];
229 return JS_TRUE;
230 }
231
232 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
233 if (!obj->getProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.lengthAtom), tvr.addr()))
234 return JS_FALSE;
235
236 if (JSVAL_IS_INT(tvr.value())) {
237 *lengthp = jsuint(jsint(JSVAL_TO_INT(tvr.value()))); /* jsuint cast does ToUint32 */
238 return JS_TRUE;
239 }
240
241 *lengthp = js_ValueToECMAUint32(cx, tvr.addr());
242 return !JSVAL_IS_NULL(tvr.value());
243 }
244
245 static JSBool
246 IndexToValue(JSContext *cx, jsdouble index, jsval *vp)
247 {
248 return js_NewWeaklyRootedNumber(cx, index, vp);
249 }
250
251 JSBool JS_FASTCALL
252 js_IndexToId(JSContext *cx, jsuint index, jsid *idp)
253 {
254 JSString *str;
255
256 if (index <= JSVAL_INT_MAX) {
257 *idp = INT_TO_JSID(index);
258 return JS_TRUE;
259 }
260 str = js_NumberToString(cx, index);
261 if (!str)
262 return JS_FALSE;
263 return js_ValueToStringId(cx, STRING_TO_JSVAL(str), idp);
264 }
265
266 static JSBool
267 BigIndexToId(JSContext *cx, JSObject *obj, jsuint index, JSBool createAtom,
268 jsid *idp)
269 {
270 jschar buf[10], *start;
271 JSClass *clasp;
272 JSAtom *atom;
273 JS_STATIC_ASSERT((jsuint)-1 == 4294967295U);
274
275 JS_ASSERT(index > JSVAL_INT_MAX);
276
277 start = JS_ARRAY_END(buf);
278 do {
279 --start;
280 *start = (jschar)('0' + index % 10);
281 index /= 10;
282 } while (index != 0);
283
284 /*
285 * Skip the atomization if the class is known to store atoms corresponding
286 * to big indexes together with elements. In such case we know that the
287 * array does not have an element at the given index if its atom does not
288 * exist. Fast arrays (clasp == &js_ArrayClass) don't use atoms for
289 * any indexes, though it would be rare to see them have a big index
290 * in any case.
291 */
292 if (!createAtom &&
293 ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_SlowArrayClass ||
294 clasp == &js_ArgumentsClass ||
295 clasp == &js_ObjectClass)) {
296 atom = js_GetExistingStringAtom(cx, start, JS_ARRAY_END(buf) - start);
297 if (!atom) {
298 *idp = JSVAL_VOID;
299 return JS_TRUE;
300 }
301 } else {
302 atom = js_AtomizeChars(cx, start, JS_ARRAY_END(buf) - start, 0);
303 if (!atom)
304 return JS_FALSE;
305 }
306
307 *idp = ATOM_TO_JSID(atom);
308 return JS_TRUE;
309 }
310
311 static JSBool
312 ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 newlen,
313 bool initializeAllSlots = true)
314 {
315 jsval *slots, *newslots;
316
317 if (newlen == 0) {
318 if (obj->dslots) {
319 cx->free(obj->dslots - 1);
320 obj->dslots = NULL;
321 }
322 return JS_TRUE;
323 }
324
325 if (newlen > MAX_DSLOTS_LENGTH) {
326 js_ReportAllocationOverflow(cx);
327 return JS_FALSE;
328 }
329
330 slots = obj->dslots ? obj->dslots - 1 : NULL;
331 newslots = (jsval *) cx->realloc(slots, (size_t(newlen) + 1) * sizeof(jsval));
332 if (!newslots)
333 return JS_FALSE;
334
335 obj->dslots = newslots + 1;
336 js_SetDenseArrayCapacity(obj, newlen);
337
338 if (initializeAllSlots) {
339 for (slots = obj->dslots + oldlen; slots < obj->dslots + newlen; slots++)
340 *slots = JSVAL_HOLE;
341 }
342
343 return JS_TRUE;
344 }
345
346 /*
347 * When a dense array with CAPACITY_DOUBLING_MAX or fewer slots needs to grow,
348 * double its capacity, to push() N elements in amortized O(N) time.
349 *
350 * Above this limit, grow by 12.5% each time. Speed is still amortized O(N),
351 * with a higher constant factor, and we waste less space.
352 */
353 #define CAPACITY_DOUBLING_MAX (1024 * 1024)
354
355 /*
356 * Round up all large allocations to a multiple of this (1MB), so as not to
357 * waste space if malloc gives us 1MB-sized chunks (as jemalloc does).
358 */
359 #define CAPACITY_CHUNK (1024 * 1024 / sizeof(jsval))
360
361 static JSBool
362 EnsureCapacity(JSContext *cx, JSObject *obj, uint32 newcap,
363 bool initializeAllSlots = true)
364 {
365 uint32 oldcap = js_DenseArrayCapacity(obj);
366
367 if (newcap > oldcap) {
368 /*
369 * If this overflows uint32, newcap is very large. nextsize will end
370 * up being less than newcap, the code below will thus disregard it,
371 * and ResizeSlots will fail.
372 *
373 * The way we use dslots[-1] forces a few +1s and -1s here. For
374 * example, (oldcap * 2 + 1) produces the sequence 7, 15, 31, 63, ...
375 * which makes the total allocation size (with dslots[-1]) a power
376 * of two.
377 */
378 uint32 nextsize = (oldcap <= CAPACITY_DOUBLING_MAX)
379 ? oldcap * 2 + 1
380 : oldcap + (oldcap >> 3);
381
382 uint32 actualCapacity = JS_MAX(newcap, nextsize);
383 if (actualCapacity >= CAPACITY_CHUNK)
384 actualCapacity = JS_ROUNDUP(actualCapacity + 1, CAPACITY_CHUNK) - 1; /* -1 for dslots[-1] */
385 else if (actualCapacity < ARRAY_CAPACITY_MIN)
386 actualCapacity = ARRAY_CAPACITY_MIN;
387 if (!ResizeSlots(cx, obj, oldcap, actualCapacity, initializeAllSlots))
388 return JS_FALSE;
389 if (!initializeAllSlots) {
390 /*
391 * Initialize the slots caller didn't actually ask for.
392 */
393 for (jsval *slots = obj->dslots + newcap;
394 slots < obj->dslots + actualCapacity;
395 slots++) {
396 *slots = JSVAL_HOLE;
397 }
398 }
399 }
400 return JS_TRUE;
401 }
402
403 static bool
404 ReallyBigIndexToId(JSContext* cx, jsdouble index, jsid* idp)
405 {
406 JSAutoTempValueRooter dval(cx);
407 if (!js_NewDoubleInRootedValue(cx, index, dval.addr()) ||
408 !js_ValueToStringId(cx, dval.value(), idp)) {
409 return JS_FALSE;
410 }
411 return JS_TRUE;
412 }
413
414 static bool
415 IndexToId(JSContext* cx, JSObject* obj, jsdouble index, JSBool* hole, jsid* idp,
416 JSBool createAtom = JS_FALSE)
417 {
418 if (index <= JSVAL_INT_MAX) {
419 *idp = INT_TO_JSID(index);
420 return JS_TRUE;
421 }
422
423 if (index <= jsuint(-1)) {
424 if (!BigIndexToId(cx, obj, jsuint(index), createAtom, idp))
425 return JS_FALSE;
426 if (hole && JSVAL_IS_VOID(*idp))
427 *hole = JS_TRUE;
428 return JS_TRUE;
429 }
430
431 return ReallyBigIndexToId(cx, index, idp);
432 }
433
434 /*
435 * If the property at the given index exists, get its value into location
436 * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
437 * to JSVAL_VOID. This function assumes that the location pointed by vp is
438 * properly rooted and can be used as GC-protected storage for temporaries.
439 */
440 static JSBool
441 GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
442 jsval *vp)
443 {
444 JS_ASSERT(index >= 0);
445 if (OBJ_IS_DENSE_ARRAY(cx, obj) && index < js_DenseArrayCapacity(obj) &&
446 (*vp = obj->dslots[jsuint(index)]) != JSVAL_HOLE) {
447 *hole = JS_FALSE;
448 return JS_TRUE;
449 }
450
451 JSAutoTempIdRooter idr(cx);
452
453 *hole = JS_FALSE;
454 if (!IndexToId(cx, obj, index, hole, idr.addr()))
455 return JS_FALSE;
456 if (*hole) {
457 *vp = JSVAL_VOID;
458 return JS_TRUE;
459 }
460
461 JSObject *obj2;
462 JSProperty *prop;
463 if (!obj->lookupProperty(cx, idr.id(), &obj2, &prop))
464 return JS_FALSE;
465 if (!prop) {
466 *hole = JS_TRUE;
467 *vp = JSVAL_VOID;
468 } else {
469 obj2->dropProperty(cx, prop);
470 if (!obj->getProperty(cx, idr.id(), vp))
471 return JS_FALSE;
472 *hole = JS_FALSE;
473 }
474 return JS_TRUE;
475 }
476
477 /*
478 * Set the value of the property at the given index to v assuming v is rooted.
479 */
480 static JSBool
481 SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, jsval v)
482 {
483 JS_ASSERT(index >= 0);
484
485 if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
486 /* Predicted/prefetched code should favor the remains-dense case. */
487 if (index <= jsuint(-1)) {
488 jsuint idx = jsuint(index);
489 if (!INDEX_TOO_SPARSE(obj, idx)) {
490 JS_ASSERT(idx + 1 > idx);
491 if (!EnsureCapacity(cx, obj, idx + 1))
492 return JS_FALSE;
493 if (idx >= uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
494 obj->fslots[JSSLOT_ARRAY_LENGTH] = idx + 1;
495 if (obj->dslots[idx] == JSVAL_HOLE)
496 obj->fslots[JSSLOT_ARRAY_COUNT]++;
497 obj->dslots[idx] = v;
498 return JS_TRUE;
499 }
500 }
501
502 if (!js_MakeArraySlow(cx, obj))
503 return JS_FALSE;
504 }
505
506 JSAutoTempIdRooter idr(cx);
507
508 if (!IndexToId(cx, obj, index, NULL, idr.addr(), JS_TRUE))
509 return JS_FALSE;
510 JS_ASSERT(!JSVAL_IS_VOID(idr.id()));
511
512 return obj->setProperty(cx, idr.id(), &v);
513 }
514
515 static JSBool
516 DeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index)
517 {
518 JS_ASSERT(index >= 0);
519 if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
520 if (index <= jsuint(-1)) {
521 jsuint idx = jsuint(index);
522 if (!INDEX_TOO_SPARSE(obj, idx) && idx < js_DenseArrayCapacity(obj)) {
523 if (obj->dslots[idx] != JSVAL_HOLE)
524 obj->fslots[JSSLOT_ARRAY_COUNT]--;
525 obj->dslots[idx] = JSVAL_HOLE;
526 return JS_TRUE;
527 }
528 }
529 return JS_TRUE;
530 }
531
532 JSAutoTempIdRooter idr(cx);
533
534 if (!IndexToId(cx, obj, index, NULL, idr.addr()))
535 return JS_FALSE;
536 if (JSVAL_IS_VOID(idr.id()))
537 return JS_TRUE;
538
539 jsval junk;
540 return obj->deleteProperty(cx, idr.id(), &junk);
541 }
542
543 /*
544 * When hole is true, delete the property at the given index. Otherwise set
545 * its value to v assuming v is rooted.
546 */
547 static JSBool
548 SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index,
549 JSBool hole, jsval v)
550 {
551 if (hole) {
552 JS_ASSERT(JSVAL_IS_VOID(v));
553 return DeleteArrayElement(cx, obj, index);
554 }
555 return SetArrayElement(cx, obj, index, v);
556 }
557
558 JSBool
559 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsdouble length)
560 {
561 jsval v;
562 jsid id;
563
564 if (!IndexToValue(cx, length, &v))
565 return JS_FALSE;
566 id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
567 return obj->setProperty(cx, id, &v);
568 }
569
570 JSBool
571 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
572 {
573 JSErrorReporter older = JS_SetErrorReporter(cx, NULL);
574 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
575 jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
576 JSBool ok = obj->getProperty(cx, id, tvr.addr());
577 JS_SetErrorReporter(cx, older);
578 if (!ok)
579 return false;
580
581 *lengthp = ValueIsLength(cx, tvr.addr());
582 return !JSVAL_IS_NULL(tvr.value());
583 }
584
585 JSBool
586 js_IsArrayLike(JSContext *cx, JSObject *obj, JSBool *answerp, jsuint *lengthp)
587 {
588 JSClass *clasp;
589
590 clasp = OBJ_GET_CLASS(cx, js_GetWrappedObject(cx, obj));
591 *answerp = (clasp == &js_ArgumentsClass || clasp == &js_ArrayClass ||
592 clasp == &js_SlowArrayClass);
593 if (!*answerp) {
594 *lengthp = 0;
595 return JS_TRUE;
596 }
597 return js_GetLengthProperty(cx, obj, lengthp);
598 }
599
600 /*
601 * The 'length' property of all native Array instances is a shared permanent
602 * property of Array.prototype, so it appears to be a direct property of each
603 * array instance delegating to that Array.prototype. It accesses the private
604 * slot reserved by js_ArrayClass.
605 *
606 * Since SpiderMonkey supports cross-class prototype-based delegation, we have
607 * to be careful about the length getter and setter being called on an object
608 * not of Array class. For the getter, we search obj's prototype chain for the
609 * array that caused this getter to be invoked. In the setter case to overcome
610 * the JSPROP_SHARED attribute, we must define a shadowing length property.
611 */
612 static JSBool
613 array_length_getter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
614 {
615 do {
616 if (OBJ_IS_ARRAY(cx, obj))
617 return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
618 } while ((obj = OBJ_GET_PROTO(cx, obj)) != NULL);
619 return JS_TRUE;
620 }
621
622 static JSBool
623 array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
624 {
625 jsuint newlen, oldlen, gap, index;
626 jsval junk;
627 JSObject *iter;
628 JSTempValueRooter tvr;
629 JSBool ok;
630
631 if (!OBJ_IS_ARRAY(cx, obj)) {
632 jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
633
634 return obj->defineProperty(cx, lengthId, *vp, NULL, NULL, JSPROP_ENUMERATE);
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 capacity = js_DenseArrayCapacity(obj);
656 if (capacity > newlen && !ResizeSlots(cx, obj, capacity, 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 under JSObject::deleteProperty. */
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->deleteProperty(cx, 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 proto->lookupProperty(cx, 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 = OBJECT_TO_JSVAL(obj->getProto());
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 obj2->dropProperty(cx, 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 = obj->getProto()) != 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 (OBJ_SCOPE(obj)->hadIndexedProperties())
894 return JS_TRUE;
895 }
896 return JS_FALSE;
897 }
898
899 #ifdef JS_TRACER
900
901 static inline JSBool FASTCALL
902 dense_grow(JSContext* cx, JSObject* obj, jsint i, jsval v)
903 {
904 /*
905 * Let the interpreter worry about negative array indexes.
906 */
907 JS_ASSERT((MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) == (sizeof(jsval) != sizeof(uint32)));
908 if (MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) {
909 /*
910 * Have to check for negative values bleeding through on 64-bit machines only,
911 * since we can't allocate large enough arrays for this on 32-bit machines.
912 */
913 if (i < 0)
914 return JS_FALSE;
915 }
916
917 /*
918 * If needed, grow the array as long it remains dense, otherwise fall off trace.
919 */
920 jsuint u = jsuint(i);
921 jsuint capacity = js_DenseArrayCapacity(obj);
922 if ((u >= capacity) && (INDEX_TOO_SPARSE(obj, u) || !EnsureCapacity(cx, obj, u + 1)))
923 return JS_FALSE;
924
925 if (obj->dslots[u] == JSVAL_HOLE) {
926 if (js_PrototypeHasIndexedProperties(cx, obj))
927 return JS_FALSE;
928
929 if (u >= jsuint(obj->fslots[JSSLOT_ARRAY_LENGTH]))
930 obj->fslots[JSSLOT_ARRAY_LENGTH] = u + 1;
931 ++obj->fslots[JSSLOT_ARRAY_COUNT];
932 }
933
934 obj->dslots[u] = v;
935 return JS_TRUE;
936 }
937
938
939 JSBool FASTCALL
940 js_Array_dense_setelem(JSContext* cx, JSObject* obj, jsint i, jsval v)
941 {
942 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
943 return dense_grow(cx, obj, i, v);
944 }
945 JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem, CONTEXT, OBJECT, INT32, JSVAL, 0, 0)
946
947 JSBool FASTCALL
948 js_Array_dense_setelem_int(JSContext* cx, JSObject* obj, jsint i, int32 j)
949 {
950 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
951
952 jsval v;
953 if (JS_LIKELY(INT_FITS_IN_JSVAL(j))) {
954 v = INT_TO_JSVAL(j);
955 } else {
956 jsdouble d = (jsdouble)j;
957 if (!js_NewDoubleInRootedValue(cx, d, &v))
958 return JS_FALSE;
959 }
960
961 return dense_grow(cx, obj, i, v);
962 }
963 JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_int, CONTEXT, OBJECT, INT32, INT32, 0, 0)
964
965 JSBool FASTCALL
966 js_Array_dense_setelem_double(JSContext* cx, JSObject* obj, jsint i, jsdouble d)
967 {
968 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
969
970 jsval v;
971 jsint j;
972
973 if (JS_LIKELY(JSDOUBLE_IS_INT(d, j) && INT_FITS_IN_JSVAL(j))) {
974 v = INT_TO_JSVAL(j);
975 } else {
976 if (!js_NewDoubleInRootedValue(cx, d, &v))
977 return JS_FALSE;
978 }
979
980 return dense_grow(cx, obj, i, v);
981 }
982 JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_double, CONTEXT, OBJECT, INT32, DOUBLE, 0, 0)
983 #endif
984
985 static JSBool
986 array_defineProperty(JSContext *cx, JSObject *obj, jsid id, jsval value,
987 JSPropertyOp getter, JSPropertyOp setter, uintN attrs)
988 {
989 uint32 i;
990 JSBool isIndex;
991
992 if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
993 return JS_TRUE;
994
995 isIndex = js_IdIsIndex(ID_TO_VALUE(id), &i);
996 if (!isIndex || attrs != JSPROP_ENUMERATE || !OBJ_IS_DENSE_ARRAY(cx, obj) || INDEX_TOO_SPARSE(obj, i)) {
997 if (!ENSURE_SLOW_ARRAY(cx, obj))
998 return JS_FALSE;
999 return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
1000 }
1001
1002 return array_setProperty(cx, obj, id, &value);
1003 }
1004
1005 static JSBool
1006 array_getAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
1007 uintN *attrsp)
1008 {
1009 *attrsp = id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)
1010 ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
1011 return JS_TRUE;
1012 }
1013
1014 static JSBool
1015 array_setAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
1016 uintN *attrsp)
1017 {
1018 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
1019 JSMSG_CANT_SET_ARRAY_ATTRS);
1020 return JS_FALSE;
1021 }
1022
1023 static JSBool
1024 array_deleteProperty(JSContext *cx, JSObject *obj, jsval id, jsval *rval)
1025 {
1026 uint32 i;
1027
1028 if (!OBJ_IS_DENSE_ARRAY(cx, obj))
1029 return js_DeleteProperty(cx, obj, id, rval);
1030
1031 if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) {
1032 *rval = JSVAL_FALSE;
1033 return JS_TRUE;
1034 }
1035
1036 if (js_IdIsIndex(id, &i) && i < js_DenseArrayCapacity(obj) &&
1037 obj->dslots[i] != JSVAL_HOLE) {
1038 obj->fslots[JSSLOT_ARRAY_COUNT]--;
1039 obj->dslots[i] = JSVAL_HOLE;
1040 }
1041
1042 *rval = JSVAL_TRUE;
1043 return JS_TRUE;
1044 }
1045
1046 /*
1047 * JSObjectOps.enumerate implementation.
1048 *
1049 * For a fast array, JSENUMERATE_INIT captures in the enumeration state both
1050 * the length of the array and the bitmap indicating the positions of holes in
1051 * the array. This ensures that adding or deleting array elements does not
1052 * affect the sequence of indexes JSENUMERATE_NEXT returns.
1053 *
1054 * For a common case of an array without holes, to represent the state we pack
1055 * the (nextEnumerationIndex, arrayLength) pair as a pseudo-boolean jsval.
1056 * This is possible when length <= PACKED_UINT_PAIR_BITS. For arrays with
1057 * greater length or holes we allocate the JSIndexIterState structure and
1058 * store it as an int-tagged private pointer jsval. For a slow array we
1059 * delegate the enumeration implementation to js_Enumerate in
1060 * slowarray_enumerate.
1061 *
1062 * Array mutations can turn a fast array into a slow one after the enumeration
1063 * starts. When this happens, slowarray_enumerate receives a state created
1064 * when the array was fast. To distinguish such fast state from a slow state,
1065 * which is an int-tagged pointer that js_Enumerate creates, we set not one
1066 * but two lowest bits when tagging a JSIndexIterState pointer -- see
1067 * INDEX_ITER_TAG usage below. Thus, when slowarray_enumerate receives a state
1068 * tagged with JSVAL_SPECIAL or with two lowest bits set, it knows that this
1069 * is a fast state so it calls array_enumerate to continue enumerating the
1070 * indexes present in the original fast array.
1071 */
1072
1073 #define PACKED_UINT_PAIR_BITS 14
1074 #define PACKED_UINT_PAIR_MASK JS_BITMASK(PACKED_UINT_PAIR_BITS)
1075
1076 #define UINT_PAIR_TO_SPECIAL_JSVAL(i,j) \
1077 (JS_ASSERT((uint32) (i) <= PACKED_UINT_PAIR_MASK), \
1078 JS_ASSERT((uint32) (j) <= PACKED_UINT_PAIR_MASK), \
1079 ((jsval) (i) << (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)) | \
1080 ((jsval) (j) << (JSVAL_TAGBITS)) | \
1081 (jsval) JSVAL_SPECIAL)
1082
1083 #define SPECIAL_JSVAL_TO_UINT_PAIR(v,i,j) \
1084 (JS_ASSERT(JSVAL_IS_SPECIAL(v)), \
1085 (i) = (uint32) ((v) >> (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)), \
1086 (j) = (uint32) ((v) >> JSVAL_TAGBITS) & PACKED_UINT_PAIR_MASK, \
1087 JS_ASSERT((i) <= PACKED_UINT_PAIR_MASK))
1088
1089 JS_STATIC_ASSERT(PACKED_UINT_PAIR_BITS * 2 + JSVAL_TAGBITS <= JS_BITS_PER_WORD);
1090
1091 typedef struct JSIndexIterState {
1092 uint32 index;
1093 uint32 length;
1094 JSBool hasHoles;
1095
1096 /*
1097 * Variable-length bitmap representing array's holes. It must not be
1098 * accessed when hasHoles is false.
1099 */
1100 jsbitmap holes[1];
1101 } JSIndexIterState;
1102
1103 #define INDEX_ITER_TAG 3
1104
1105 JS_STATIC_ASSERT(JSVAL_INT == 1);
1106
1107 static JSBool
1108 array_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
1109 jsval *statep, jsid *idp)
1110 {
1111 uint32 capacity, i;
1112 JSIndexIterState *ii;
1113
1114 switch (enum_op) {
1115 case JSENUMERATE_INIT:
1116 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
1117 capacity = js_DenseArrayCapacity(obj);
1118 if (idp)
1119 *idp = INT_TO_JSVAL(obj->fslots[JSSLOT_ARRAY_COUNT]);
1120 ii = NULL;
1121 for (i = 0; i != capacity; ++i) {
1122 if (obj->dslots[i] == JSVAL_HOLE) {
1123 if (!ii) {
1124 ii = (JSIndexIterState *)
1125 cx->malloc(offsetof(JSIndexIterState, holes) +
1126 JS_BITMAP_SIZE(capacity));
1127 if (!ii)
1128 return JS_FALSE;
1129 ii->hasHoles = JS_TRUE;
1130 memset(ii->holes, 0, JS_BITMAP_SIZE(capacity));
1131 }
1132 JS_SET_BIT(ii->holes, i);
1133 }
1134 }
1135 if (!ii) {
1136 /* Array has no holes. */
1137 if (capacity <= PACKED_UINT_PAIR_MASK) {
1138 *statep = UINT_PAIR_TO_SPECIAL_JSVAL(0, capacity);
1139 break;
1140 }
1141 ii = (JSIndexIterState *)
1142 cx->malloc(offsetof(JSIndexIterState, holes));
1143 if (!ii)
1144 return JS_FALSE;
1145 ii->hasHoles = JS_FALSE;
1146 }
1147 ii->index = 0;
1148 ii->length = capacity;
1149 *statep = (jsval) ii | INDEX_ITER_TAG;
1150 JS_ASSERT(*statep & JSVAL_INT);
1151 break;
1152
1153 case JSENUMERATE_NEXT:
1154 if (JSVAL_IS_SPECIAL(*statep)) {
1155 SPECIAL_JSVAL_TO_UINT_PAIR(*statep, i, capacity);
1156 if (i != capacity) {
1157 *idp = INT_TO_JSID(i);
1158 *statep = UINT_PAIR_TO_SPECIAL_JSVAL(i + 1, capacity);
1159 break;
1160 }
1161 } else {
1162 JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
1163 ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
1164 i = ii->index;
1165 if (i != ii->length) {
1166 /* Skip holes if any. */
1167 if (ii->hasHoles) {
1168 while (JS_TEST_BIT(ii->holes, i) && ++i != ii->length)
1169 continue;
1170 }
1171 if (i != ii->length) {
1172 ii->index = i + 1;
1173 return js_IndexToId(cx, i, idp);
1174 }
1175 }
1176 }
1177 /* FALL THROUGH */
1178
1179 case JSENUMERATE_DESTROY:
1180 if (!JSVAL_IS_SPECIAL(*statep)) {
1181 JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
1182 ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
1183 cx->free(ii);
1184 }
1185 *statep = JSVAL_NULL;
1186 break;
1187 }
1188 return JS_TRUE;
1189 }
1190
1191 static JSBool
1192 slowarray_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
1193 jsval *statep, jsid *idp)
1194 {
1195 JSBool ok;
1196
1197 /* Are we continuing an enumeration that started when we were dense? */
1198 if (enum_op != JSENUMERATE_INIT) {
1199 if (JSVAL_IS_SPECIAL(*statep) ||
1200 (*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG) {
1201 return array_enumerate(cx, obj, enum_op, statep, idp);
1202 }
1203 JS_ASSERT((*statep & INDEX_ITER_TAG) == JSVAL_INT);
1204 }
1205 ok = js_Enumerate(cx, obj, enum_op, statep, idp);
1206 JS_ASSERT(*statep == JSVAL_NULL || (*statep & INDEX_ITER_TAG) == JSVAL_INT);
1207 return ok;
1208 }
1209
1210 static void
1211 array_finalize(JSContext *cx, JSObject *obj)
1212 {
1213 if (obj->dslots)
1214 cx->free(obj->dslots - 1);
1215 obj->dslots = NULL;
1216 }
1217
1218 static void
1219 array_trace(JSTracer *trc, JSObject *obj)
1220 {
1221 uint32 capacity;
1222 size_t i;
1223 jsval v;
1224
1225 JS_ASSERT(js_IsDenseArray(obj));
1226 obj->traceProtoAndParent(trc);
1227
1228 capacity = js_DenseArrayCapacity(obj);
1229 for (i = 0; i < capacity; i++) {
1230 v = obj->dslots[i];
1231 if (JSVAL_IS_TRACEABLE(v)) {
1232 JS_SET_TRACING_INDEX(trc, "array_dslots", i);
1233 JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
1234 }
1235 }
1236 }
1237
1238 extern JSObjectOps js_ArrayObjectOps;
1239
1240 static const JSObjectMap SharedArrayMap(&js_ArrayObjectOps, JSObjectMap::SHAPELESS);
1241
1242 JSObjectOps js_ArrayObjectOps = {
1243 &SharedArrayMap,
1244 array_lookupProperty, array_defineProperty,
1245 array_getProperty, array_setProperty,
1246 array_getAttributes, array_setAttributes,
1247 array_deleteProperty, js_DefaultValue,
1248 array_enumerate, js_CheckAccess,
1249 NULL, array_dropProperty,
1250 NULL, NULL,
1251 js_HasInstance, array_trace,
1252 NULL
1253 };
1254
1255 static JSObjectOps *
1256 array_getObjectOps(JSContext *cx, JSClass *clasp)
1257 {
1258 return &js_ArrayObjectOps;
1259 }
1260
1261 JSClass js_ArrayClass = {
1262 "Array",
1263 JSCLASS_HAS_RESERVED_SLOTS(2) |
1264 JSCLASS_HAS_CACHED_PROTO(JSProto_Array) |
1265 JSCLASS_NEW_ENUMERATE,
1266 JS_PropertyStub, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
1267 JS_EnumerateStub, JS_ResolveStub, js_TryValueOf, array_finalize,
1268 array_getObjectOps, NULL, NULL, NULL,
1269 NULL, NULL, NULL, NULL
1270 };
1271
1272 JSClass js_SlowArrayClass = {
1273 "Array",
1274 JSCLASS_HAS_RESERVED_SLOTS(1) |
1275 JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
1276 slowarray_addProperty, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
1277 JS_EnumerateStub, JS_ResolveStub, js_TryValueOf, NULL,
1278 slowarray_getObjectOps, NULL, NULL, NULL,
1279 NULL, NULL, NULL, NULL
1280 };
1281
1282 /*
1283 * Convert an array object from fast-and-dense to slow-and-flexible.
1284 */
1285 JSBool
1286 js_MakeArraySlow(JSContext *cx, JSObject *obj)
1287 {
1288 JS_ASSERT(obj->getClass() == &js_ArrayClass);
1289
1290 /*
1291 * Create a native scope. All slow arrays other than Array.prototype get
1292 * the same initial shape.
1293 */
1294 uint32 emptyShape;
1295 JSObject *arrayProto = obj->getProto();
1296 if (arrayProto->getClass() == &js_ObjectClass) {
1297 /* obj is Array.prototype. */
1298 emptyShape = js_GenerateShape(cx, false);
1299 } else {
1300 /* arrayProto is Array.prototype. */
1301 JS_ASSERT(arrayProto->getClass() == &js_SlowArrayClass);
1302 emptyShape = OBJ_SCOPE(arrayProto)->emptyScope->shape;
1303 }
1304 JSScope *scope = JSScope::create(cx, &js_SlowArrayObjectOps, &js_SlowArrayClass, obj,
1305 emptyShape);
1306 if (!scope)
1307 return JS_FALSE;
1308
1309 uint32 capacity = js_DenseArrayCapacity(obj);
1310 if (capacity) {
1311 scope->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
1312 obj->dslots[-1] = JS_INITIAL_NSLOTS + capacity;
1313 } else {
1314 scope->freeslot = STOBJ_NSLOTS(obj);
1315 }
1316
1317 /* Create new properties pointing to existing values in dslots */
1318 for (uint32 i = 0; i < capacity; i++) {
1319 jsid id;
1320 JSScopeProperty *sprop;
1321
1322 if (!JS_ValueToId(cx, INT_TO_JSVAL(i), &id))
1323 goto out_bad;
1324
1325 if (obj->dslots[i] == JSVAL_HOLE) {
1326 obj->dslots[i] = JSVAL_VOID;
1327 continue;
1328 }
1329
1330 sprop = scope->add(cx, id, NULL, NULL, i + JS_INITIAL_NSLOTS,
1331 JSPROP_ENUMERATE, 0, 0);
1332 if (!sprop)
1333 goto out_bad;
1334 }
1335
1336 /*
1337 * Render our formerly-reserved count property GC-safe. If length fits in
1338 * a jsval, set our slow/sparse COUNT to the current length as a jsval, so
1339 * we can tell when only named properties have been added to a dense array
1340 * to make it slow-but-not-sparse.
1341 */
1342 {
1343 uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
1344 obj->fslots[JSSLOT_ARRAY_COUNT] = INT_FITS_IN_JSVAL(length)
1345 ? INT_TO_JSVAL(length)
1346 : JSVAL_VOID;
1347 }
1348
1349 /* Make sure we preserve any flags borrowing bits in classword. */
1350 obj->classword ^= (jsuword) &js_ArrayClass;
1351 obj->classword |= (jsuword) &js_SlowArrayClass;
1352
1353 obj->map = scope;
1354 return JS_TRUE;
1355
1356 out_bad:
1357 JSScope::destroy(cx, scope);
1358 return JS_FALSE;
1359 }
1360
1361 /* Transfer ownership of buffer to returned string. */
1362 static inline JSBool
1363 BufferToString(JSContext *cx, JSCharBuffer &cb, jsval *rval)
1364 {
1365 JSString *str = js_NewStringFromCharBuffer(cx, cb);
1366 if (!str)
1367 return false;
1368 *rval = STRING_TO_JSVAL(str);
1369 return true;
1370 }
1371
1372 #if JS_HAS_TOSOURCE
1373 static JSBool
1374 array_toSource(JSContext *cx, uintN argc, jsval *vp)
1375 {
1376 JS_CHECK_RECURSION(cx, return false);
1377
1378 JSObject *obj = JS_THIS_OBJECT(cx, vp);
1379 if (!obj ||
1380 (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1381 !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1382 return false;
1383 }
1384
1385 /* Find joins or cycles in the reachable object graph. */
1386 jschar *sharpchars;
1387 JSHashEntry *he = js_EnterSharpObject(cx, obj, NULL, &sharpchars);
1388 if (!he)
1389 return false;
1390 bool initiallySharp = IS_SHARP(he);
1391
1392 /* After this point, all paths exit through the 'out' label. */
1393 MUST_FLOW_THROUGH("out");
1394 bool ok = false;
1395
1396 /*
1397 * This object will take responsibility for the jschar buffer until the
1398 * buffer is transferred to the returned JSString.
1399 */
1400 JSCharBuffer cb(cx);
1401
1402 /* Cycles/joins are indicated by sharp objects. */
1403 #if JS_HAS_SHARP_VARS
1404 if (IS_SHARP(he)) {
1405 JS_ASSERT(sharpchars != 0);
1406 cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1407 goto make_string;
1408 } else if (sharpchars) {
1409 MAKE_SHARP(he);
1410 cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1411 }
1412 #else
1413 if (IS_SHARP(he)) {
1414 if (!js_AppendLiteral(cb, "[]"))
1415 goto out;
1416 cx->free(sharpchars);
1417 goto make_string;
1418 }
1419 #endif
1420
1421 if (!cb.append('['))
1422 goto out;
1423
1424 jsuint length;
1425 if (!js_GetLengthProperty(cx, obj, &length))
1426 goto out;
1427
1428 for (jsuint index = 0; index < length; index++) {
1429 /* Use vp to locally root each element value. */
1430 JSBool hole;
1431 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1432 !GetArrayElement(cx, obj, index, &hole, vp)) {
1433 goto out;
1434 }
1435
1436 /* Get element's character string. */
1437 JSString *str;
1438 if (hole) {
1439 str = cx->runtime->emptyString;
1440 } else {
1441 str = js_ValueToSource(cx, *vp);
1442 if (!str)
1443 goto out;
1444 }
1445 *vp = STRING_TO_JSVAL(str);
1446 const jschar *chars;
1447 size_t charlen;
1448 str->getCharsAndLength(chars, charlen);
1449
1450 /* Append element to buffer. */
1451 if (!cb.append(chars, charlen))
1452 goto out;
1453 if (index + 1 != length) {
1454 if (!js_AppendLiteral(cb, ", "))
1455 goto out;
1456 } else if (hole) {
1457 if (!cb.append(','))
1458 goto out;
1459 }
1460 }
1461
1462 /* Finalize the buffer. */
1463 if (!cb.append(']'))
1464 goto out;
1465
1466 make_string:
1467 if (!BufferToString(cx, cb, vp))
1468 goto out;
1469
1470 ok = true;
1471
1472 out:
1473 if (!initiallySharp)
1474 js_LeaveSharpObject(cx, NULL);
1475 return ok;
1476 }
1477 #endif
1478
1479 static JSHashNumber
1480 js_hash_array(const void *key)
1481 {
1482 return (JSHashNumber)JS_PTR_TO_UINT32(key) >> JSVAL_TAGBITS;
1483 }
1484
1485 bool
1486 js_InitContextBusyArrayTable(JSContext *cx)
1487 {
1488 cx->busyArrayTable = JS_NewHashTable(4, js_hash_array, JS_CompareValues,
1489 JS_CompareValues, NULL, NULL);
1490 return cx->busyArrayTable != NULL;
1491 }
1492
1493 static JSBool
1494 array_toString_sub(JSContext *cx, JSObject *obj, JSBool locale,
1495 JSString *sepstr, jsval *rval)
1496 {
1497 JS_CHECK_RECURSION(cx, return false);
1498
1499 /*
1500 * This hash table is shared between toString invocations and must be empty
1501 * after the root invocation completes.
1502 */
1503 JSHashTable *table = cx->busyArrayTable;
1504
1505 /*
1506 * Use HashTable entry as the cycle indicator. On first visit, create the
1507 * entry, and, when leaving, remove the entry.
1508 */
1509 JSHashNumber hash = js_hash_array(obj);
1510 JSHashEntry **hep = JS_HashTableRawLookup(table, hash, obj);
1511 JSHashEntry *he = *hep;
1512 if (!he) {
1513 /* Not in hash table, so not a cycle. */
1514 he = JS_HashTableRawAdd(table, hep, hash, obj, NULL);
1515 if (!he) {
1516 JS_ReportOutOfMemory(cx);
1517 return false;
1518 }
1519 } else {
1520 /* Cycle, so return empty string. */
1521 *rval = ATOM_KEY(cx->runtime->atomState.emptyAtom);
1522 return true;
1523 }
1524
1525 JSAutoTempValueRooter tvr(cx, obj);
1526
1527 /* After this point, all paths exit through the 'out' label. */
1528 MUST_FLOW_THROUGH("out");
1529 bool ok = false;
1530
1531 /* Get characters to use for the separator. */
1532 static const jschar comma = ',';
1533 const jschar *sep;
1534 size_t seplen;
1535 if (sepstr) {
1536 sepstr->getCharsAndLength(sep, seplen);
1537 } else {
1538 sep = &comma;
1539 seplen = 1;
1540 }
1541
1542 /*
1543 * This object will take responsibility for the jschar buffer until the
1544 * buffer is transferred to the returned JSString.
1545 */
1546 JSCharBuffer cb(cx);
1547
1548 jsuint length;
1549 if (!js_GetLengthProperty(cx, obj, &length))
1550 goto out;
1551
1552 for (jsuint index = 0; index < length; index++) {
1553 /* Use rval to locally root each element value. */
1554 JSBool hole;
1555 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1556 !GetArrayElement(cx, obj, index, &hole, rval)) {
1557 goto out;
1558 }
1559
1560 /* Get element's character string. */
1561 if (!(hole || JSVAL_IS_VOID(*rval) || JSVAL_IS_NULL(*rval))) {
1562 if (locale) {
1563 /* Work on obj.toLocalString() instead. */
1564 JSObject *robj;
1565
1566 if (!js_ValueToObject(cx, *rval, &robj))
1567 goto out;
1568 *rval = OBJECT_TO_JSVAL(robj);
1569 JSAtom *atom = cx->runtime->atomState.toLocaleStringAtom;
1570 if (!js_TryMethod(cx, robj, atom, 0, NULL, rval))
1571 goto out;
1572 }
1573
1574 if (!js_ValueToCharBuffer(cx, *rval, cb))
1575 goto out;
1576 }
1577
1578 /* Append the separator. */
1579 if (index + 1 != length) {
1580 if (!cb.append(sep, seplen))
1581 goto out;
1582 }
1583 }
1584
1585 /* Finalize the buffer. */
1586 if (!BufferToString(cx, cb, rval))
1587 goto out;
1588
1589 ok = true;
1590
1591 out:
1592 /*
1593 * It is possible that 'hep' may have been invalidated by subsequent
1594 * RawAdd/Remove. Hence, 'RawRemove' must not be used.
1595 */
1596 JS_HashTableRemove(table, obj);
1597 return ok;
1598 }
1599
1600 static JSBool
1601 array_toString(JSContext *cx, uintN argc, jsval *vp)
1602 {
1603 JSObject *obj;
1604
1605 obj = JS_THIS_OBJECT(cx, vp);
1606 if (!obj ||
1607 (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1608 !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1609 return JS_FALSE;
1610 }
1611
1612 return array_toString_sub(cx, obj, JS_FALSE, NULL, vp);
1613 }
1614
1615 static JSBool
1616 array_toLocaleString(JSContext *cx, uintN argc, jsval *vp)
1617 {
1618 JSObject *obj;
1619
1620 obj = JS_THIS_OBJECT(cx, vp);
1621 if (!obj ||
1622 (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1623 !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1624 return JS_FALSE;
1625 }
1626
1627 /*
1628 * Passing comma here as the separator. Need a way to get a
1629 * locale-specific version.
1630 */
1631 return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
1632 }
1633
1634 enum TargetElementsType {
1635 TargetElementsAllHoles,
1636 TargetElementsMayContainValues
1637 };
1638
1639 enum SourceVectorType {
1640 SourceVectorAllValues,
1641 SourceVectorMayContainHoles
1642 };
1643
1644 static JSBool
1645 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, jsval *vector,
1646 TargetElementsType targetType, SourceVectorType vectorType)
1647 {
1648 JS_ASSERT(count < MAXINDEX);
1649
1650 /*
1651 * Optimize for dense arrays so long as adding the given set of elements
1652 * wouldn't otherwise make the array slow.
1653 */
1654 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
1655 start <= MAXINDEX - count && !INDEX_TOO_BIG(start + count)) {
1656
1657 #ifdef DEBUG_jwalden
1658 {
1659 /* Verify that overwriteType and writeType were accurate. */
1660 JSAutoTempIdRooter idr(cx, JSVAL_ZERO);
1661 for (jsuint i = 0; i < count; i++) {
1662 JS_ASSERT_IF(vectorType == SourceVectorAllValues, vector[i] != JSVAL_HOLE);
1663
1664 jsdouble index = jsdouble(start) + i;
1665 if (targetType == TargetElementsAllHoles && index < jsuint(-1)) {
1666 JS_ASSERT(ReallyBigIndexToId(cx, index, idr.addr()));
1667 JSObject* obj2;
1668 JSProperty* prop;
1669 JS_ASSERT(obj->lookupProperty(cx, idr.id(), &obj2, &prop));
1670 JS_ASSERT(!prop);
1671 }
1672 }
1673 }
1674 #endif
1675
1676 jsuint newlen = start + count;
1677 JS_ASSERT(jsdouble(start) + count == jsdouble(newlen));
1678 if (!EnsureCapacity(cx, obj, newlen))
1679 return JS_FALSE;
1680
1681 if (newlen > uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
1682 obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
1683
1684 JS_ASSERT(count < size_t(-1) / sizeof(jsval));
1685 if (targetType == TargetElementsMayContainValues) {
1686 jsuint valueCount = 0;
1687 for (jsuint i = 0; i < count; i++) {
1688 if (obj->dslots[start + i] != JSVAL_HOLE)
1689 valueCount++;
1690 }
1691 JS_ASSERT(uint32(obj->fslots[JSSLOT_ARRAY_COUNT]) >= valueCount);
1692 obj->fslots[JSSLOT_ARRAY_COUNT] -= valueCount;
1693 }
1694 memcpy(obj->dslots + start, vector, sizeof(jsval) * count);
1695 if (vectorType == SourceVectorAllValues) {
1696 obj->fslots[JSSLOT_ARRAY_COUNT] += count;
1697 } else {
1698 jsuint valueCount = 0;
1699 for (jsuint i = 0; i < count; i++) {
1700 if (obj->dslots[start + i] != JSVAL_HOLE)
1701 valueCount++;
1702 }
1703 obj->fslots[JSSLOT_ARRAY_COUNT] += valueCount;
1704 }
1705 JS_ASSERT_IF(count != 0, obj->dslots[newlen - 1] != JSVAL_HOLE);
1706 return JS_TRUE;
1707 }
1708
1709 jsval* end = vector + count;
1710 while (vector != end && start < MAXINDEX) {
1711 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1712 !SetArrayElement(cx, obj, start++, *vector++)) {
1713 return JS_FALSE;
1714 }
1715 }
1716
1717 if (vector == end)
1718 return JS_TRUE;
1719
1720 /* Finish out any remaining elements past the max array index. */
1721 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !ENSURE_SLOW_ARRAY(cx, obj))
1722 return JS_FALSE;
1723
1724 JS_ASSERT(start == MAXINDEX);
1725 jsval tmp[2] = {JSVAL_NULL, JSVAL_NULL};
1726 jsdouble* dp = js_NewWeaklyRootedDouble(cx, MAXINDEX);
1727 if (!dp)
1728 return JS_FALSE;
1729 tmp[0] = DOUBLE_TO_JSVAL(dp);
1730 JSAutoTempValueRooter tvr(cx, JS_ARRAY_LENGTH(tmp), tmp);
1731 JSAutoTempIdRooter idr(cx);
1732 do {
1733 tmp[1] = *vector++;
1734 if (!js_ValueToStringId(cx, tmp[0], idr.addr()) ||
1735 !obj->setProperty(cx, idr.id(), &tmp[1])) {
1736 return JS_FALSE;
1737 }
1738 *dp += 1;
1739 } while (vector != end);
1740
1741 return JS_TRUE;
1742 }
1743
1744 static JSBool
1745 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector,
1746 JSBool holey = JS_FALSE)
1747 {
1748 JS_ASSERT(OBJ_IS_ARRAY(cx, obj));
1749
1750 obj->fslots[JSSLOT_ARRAY_LENGTH] = length;
1751
1752 if (vector) {
1753 if (!EnsureCapacity(cx, obj, length))
1754 return JS_FALSE;
1755
1756 jsuint count = length;
1757 if (!holey) {
1758 memcpy(obj->dslots, vector, length * sizeof (jsval));
1759 } else {
1760 for (jsuint i = 0; i < length; i++) {
1761 if (vector[i] == JSVAL_HOLE)
1762 --count;
1763 obj->dslots[i] = vector[i];
1764 }
1765 }
1766 obj->fslots[JSSLOT_ARRAY_COUNT] = count;
1767 } else {
1768 obj->fslots[JSSLOT_ARRAY_COUNT] = 0;
1769 }
1770 return JS_TRUE;
1771 }
1772
1773 #ifdef JS_TRACER
1774 static JSString* FASTCALL
1775 Array_p_join(JSContext* cx, JSObject* obj, JSString *str)
1776 {
1777 JSAutoTempValueRooter tvr(cx);
1778 if (!array_toString_sub(cx, obj, JS_FALSE, str, tvr.addr())) {
1779 js_SetBuiltinError(cx);
1780 return NULL;
1781 }
1782 return JSVAL_TO_STRING(tvr.value());
1783 }
1784
1785 static JSString* FASTCALL
1786 Array_p_toString(JSContext* cx, JSObject* obj)
1787 {
1788 JSAutoTempValueRooter tvr(cx);
1789 if (!array_toString_sub(cx, obj, JS_FALSE, NULL, tvr.addr())) {
1790 js_SetBuiltinError(cx);
1791 return NULL;
1792 }
1793 return JSVAL_TO_STRING(tvr.value());
1794 }
1795 #endif
1796
1797 /*
1798 * Perl-inspired join, reverse, and sort.
1799 */
1800 static JSBool
1801 array_join(JSContext *cx, uintN argc, jsval *vp)
1802 {
1803 JSString *str;
1804 JSObject *obj;
1805
1806 if (argc == 0 || JSVAL_IS_VOID(vp[2])) {
1807 str = NULL;
1808 } else {
1809 str = js_ValueToString(cx, vp[2]);
1810 if (!str)
1811 return JS_FALSE;
1812 vp[2] = STRING_TO_JSVAL(str);
1813 }
1814 obj = JS_THIS_OBJECT(cx, vp);
1815 return obj && array_toString_sub(cx, obj, JS_FALSE, str, vp);
1816 }
1817
1818 static JSBool
1819 array_reverse(JSContext *cx, uintN argc, jsval *vp)
1820 {
1821 jsuint len;
1822 JSObject *obj = JS_THIS_OBJECT(cx, vp);
1823 if (!obj || !js_GetLengthProperty(cx, obj, &len))
1824 return JS_FALSE;
1825 *vp = OBJECT_TO_JSVAL(obj);
1826
1827 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj)) {
1828 /* An empty array or an array with no elements is already reversed. */
1829 if (len == 0 || !obj->dslots)
1830 return JS_TRUE;
1831
1832 /*
1833 * It's actually surprisingly complicated to reverse an array due to the
1834 * orthogonality of array length and array capacity while handling
1835 * leading and trailing holes correctly. Reversing seems less likely to
1836 * be a common operation than other array mass-mutation methods, so for
1837 * now just take a probably-small memory hit (in the absence of too many
1838 * holes in the array at its start) and ensure that the capacity is
1839 * sufficient to hold all the elements in the array if it were full.
1840 */
1841 if (!EnsureCapacity(cx, obj, len))
1842 return JS_FALSE;
1843
1844 jsval* lo = &obj->dslots[0];
1845 jsval* hi = &obj->dslots[len - 1];
1846 for (; lo < hi; lo++, hi--) {
1847 jsval tmp = *lo;
1848 *lo = *hi;
1849 *hi = tmp;
1850 }
1851
1852 /*
1853 * Per ECMA-262, don't update the length of the array, even if the new
1854 * array has trailing holes (and thus the original array began with
1855 * holes).
1856 */
1857 return JS_TRUE;
1858 }
1859
1860 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
1861 for (jsuint i = 0, half = len / 2; i < half; i++) {
1862 JSBool hole, hole2;
1863 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1864 !GetArrayElement(cx, obj, i, &hole, tvr.addr()) ||
1865 !GetArrayElement(cx, obj, len - i - 1, &hole2, vp) ||
1866 !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, tvr.value()) ||
1867 !SetOrDeleteArrayElement(cx, obj, i, hole2, *vp)) {
1868 return false;
1869 }
1870 }
1871 *vp = OBJECT_TO_JSVAL(obj);
1872 return true;
1873 }
1874
1875 typedef struct MSortArgs {
1876 size_t elsize;
1877 JSComparator cmp;
1878 void *arg;
1879 JSBool fastcopy;
1880 } MSortArgs;
1881
1882 /* Helper function for js_MergeSort. */
1883 static JSBool
1884 MergeArrays(MSortArgs *msa, void *src, void *dest, size_t run1, size_t run2)
1885 {
1886 void *arg, *a, *b, *c;
1887 size_t elsize, runtotal;
1888 int cmp_result;
1889 JSComparator cmp;
1890 JSBool fastcopy;
1891
1892 runtotal = run1 + run2;
1893
1894 elsize = msa->elsize;
1895 cmp = msa->cmp;
1896 arg = msa->arg;
1897 fastcopy = msa->fastcopy;
1898
1899 #define CALL_CMP(a, b) \
1900 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1901
1902 /* Copy runs already in sorted order. */
1903 b = (char *)src + run1 * elsize;
1904 a = (char *)b - elsize;
1905 CALL_CMP(a, b);
1906 if (cmp_result <= 0) {
1907 memcpy(dest, src, runtotal * elsize);
1908 return JS_TRUE;
1909 }
1910
1911 #define COPY_ONE(p,q,n) \
1912 (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1913
1914 a = src;
1915 c = dest;
1916 for (; runtotal != 0; runtotal--) {
1917 JSBool from_a = run2 == 0;
1918 if (!from_a && run1 != 0) {
1919 CALL_CMP(a,b);
1920 from_a = cmp_result <= 0;
1921 }
1922
1923 if (from_a) {
1924 COPY_ONE(c, a, elsize);
1925 run1--;
1926 a = (char *)a + elsize;
1927 } else {
1928 COPY_ONE(c, b, elsize);
1929 run2--;
1930 b = (char *)b + elsize;
1931 }
1932 c = (char *)c + elsize;
1933 }
1934 #undef COPY_ONE
1935 #undef CALL_CMP
1936
1937 return JS_TRUE;
1938 }
1939
1940 /*
1941 * This sort is stable, i.e. sequence of equal elements is preserved.
1942 * See also bug #224128.
1943 */
1944 JSBool
1945 js_MergeSort(void *src, size_t nel, size_t elsize,
1946 JSComparator cmp, void *arg, void *tmp)
1947 {
1948 void *swap, *vec1, *vec2;
1949 MSortArgs msa;
1950 size_t i, j, lo, hi, run;
1951 JSBool fastcopy;
1952 int cmp_result;
1953
1954 /* Avoid memcpy overhead for word-sized and word-aligned elements. */
1955 fastcopy = (elsize == sizeof(jsval) &&
1956 (((jsuword) src | (jsuword) tmp) & JSVAL_ALIGN) == 0);
1957 #define COPY_ONE(p,q,n) \
1958 (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1959 #define CALL_CMP(a, b) \
1960 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1961 #define INS_SORT_INT 4
1962
1963 /*
1964 * Apply insertion sort to small chunks to reduce the number of merge
1965 * passes needed.
1966 */
1967 for (lo = 0; lo < nel; lo += INS_SORT_INT) {
1968 hi = lo + INS_SORT_INT;
1969 if (hi >= nel)
1970 hi = nel;
1971 for (i = lo + 1; i < hi; i++) {
1972 vec1 = (char *)src + i * elsize;
1973 vec2 = (char *)vec1 - elsize;
1974 for (j = i; j > lo; j--) {
1975 CALL_CMP(vec2, vec1);
1976 /* "<=" instead of "<" insures the sort is stable */
1977 if (cmp_result <= 0) {
1978 break;
1979 }
1980
1981 /* Swap elements, using "tmp" as tmp storage */
1982 COPY_ONE(tmp, vec2, elsize);
1983 COPY_ONE(vec2, vec1, elsize);
1984 COPY_ONE(vec1, tmp, elsize);
1985 vec1 = vec2;
1986 vec2 = (char *)vec1 - elsize;
1987 }
1988 }
1989 }
1990 #undef CALL_CMP
1991 #undef COPY_ONE
1992
1993 msa.elsize = elsize;
1994 msa.cmp = cmp;
1995 msa.arg = arg;
1996 msa.fastcopy = fastcopy;
1997
1998 vec1 = src;
1999 vec2 = tmp;
2000 for (run = INS_SORT_INT; run < nel; run *= 2) {
2001 for (lo = 0; lo < nel; lo += 2 * run) {
2002 hi = lo + run;
2003 if (hi >= nel) {
2004 memcpy((char *)vec2 + lo * elsize, (char *)vec1 + lo * elsize,
2005 (nel - lo) * elsize);
2006 break;
2007 }
2008 if (!MergeArrays(&msa, (char *)vec1 + lo * elsize,
2009 (char *)vec2 + lo * elsize, run,
2010 hi + run > nel ? nel - hi : run)) {
2011 return JS_FALSE;
2012 }
2013 }
2014 swap = vec1;
2015 vec1 = vec2;
2016 vec2 = swap;
2017 }
2018 if (src != vec1)
2019 memcpy(src, tmp, nel * elsize);
2020
2021 return JS_TRUE;
2022 }
2023
2024 typedef struct CompareArgs {
2025 JSContext *context;
2026 jsval fval;
2027 jsval *elemroot; /* stack needed for js_Invoke */
2028 } CompareArgs;
2029
2030 static JS_REQUIRES_STACK JSBool
2031 sort_compare(void *arg, const void *a, const void *b, int *result)
2032 {
2033 jsval av = *(const jsval *)a, bv = *(const jsval *)b;
2034 CompareArgs *ca = (CompareArgs *) arg;
2035 JSContext *cx = ca->context;
2036 jsval *invokevp, *sp;
2037 jsdouble cmp;
2038
2039 /**
2040 * array_sort deals with holes and undefs on its own and they should not
2041 * come here.
2042 */
2043 JS_ASSERT(!JSVAL_IS_VOID(av));
2044 JS_ASSERT(!JSVAL_IS_VOID(bv));
2045
2046 if (!JS_CHECK_OPERATION_LIMIT(cx))
2047 return JS_FALSE;
2048
2049 invokevp = ca->elemroot;
2050 sp = invokevp;
2051 *sp++ = ca->fval;
2052 *sp++ = JSVAL_NULL;
2053 *sp++ = av;
2054 *sp++ = bv;
2055
2056 if (!js_Invoke(cx, 2, invokevp, 0))
2057 return JS_FALSE;
2058
2059 cmp = js_ValueToNumber(cx, invokevp);
2060 if (JSVAL_IS_NULL(*invokevp))
2061 return JS_FALSE;
2062
2063 /* Clamp cmp to -1, 0, 1. */
2064 *result = 0;
2065 if (!JSDOUBLE_IS_NaN(cmp) && cmp != 0)
2066 *result = cmp > 0 ? 1 : -1;
2067
2068 /*
2069 * XXX else report some kind of error here? ECMA talks about 'consistent
2070 * compare functions' that don't return NaN, but is silent about what the
2071 * result should be. So we currently ignore it.
2072 */
2073
2074 return JS_TRUE;
2075 }
2076
2077 typedef JSBool (JS_REQUIRES_STACK *JSRedComparator)(void*, const void*,
2078 const void*, int *);
2079
2080 static inline JS_IGNORE_STACK JSComparator
2081 comparator_stack_cast(JSRedComparator func)
2082 {
2083 return func;
2084 }
2085
2086 static int
2087 sort_compare_strings(void *arg, const void *a, const void *b, int *result)
2088 {
2089 jsval av = *(const jsval *)a, bv = *(const jsval *)b;
2090
2091 JS_ASSERT(JSVAL_IS_STRING(av));
2092 JS_ASSERT(JSVAL_IS_STRING(bv));
2093 if (!JS_CHECK_OPERATION_LIMIT((JSContext *)arg))
2094 return JS_FALSE;
2095
2096 *result = (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
2097 return JS_TRUE;
2098 }
2099
2100 /*
2101 * The array_sort function below assumes JSVAL_NULL is zero in order to
2102 * perform initialization using memset. Other parts of SpiderMonkey likewise
2103 * "know" that JSVAL_NULL is zero; this static assertion covers all cases.
2104 */
2105 JS_STATIC_ASSERT(JSVAL_NULL == 0);
2106
2107 static JSBool
2108 array_sort(JSContext *cx, uintN argc, jsval *vp)
2109 {
2110 jsval *argv, fval, *vec, *mergesort_tmp, v;
2111 JSObject *obj;
2112 CompareArgs ca;
2113 jsuint len, newlen, i, undefs;
2114 JSTempValueRooter tvr;
2115 JSBool hole;
2116 JSBool ok;
2117 size_t elemsize;
2118 JSString *str;
2119
2120 /*
2121 * Optimize the default compare function case if all of obj's elements
2122 * have values of type string.
2123 */
2124 JSBool all_strings;
2125
2126 argv = JS_ARGV(cx, vp);
2127 if (argc > 0) {
2128 if (JSVAL_IS_PRIMITIVE(argv[0])) {
2129 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2130 JSMSG_BAD_SORT_ARG);
2131 return JS_FALSE;
2132 }
2133 fval = argv[0]; /* non-default compare function */
2134 } else {
2135 fval = JSVAL_NULL;
2136 }
2137
2138 obj = JS_THIS_OBJECT(cx, vp);
2139 if (!obj || !js_GetLengthProperty(cx, obj, &len))
2140 return JS_FALSE;
2141 if (len == 0) {
2142 *vp = OBJECT_TO_JSVAL(obj);
2143 return JS_TRUE;
2144 }
2145
2146 /*
2147 * We need a temporary array of 2 * len jsvals to hold the array elements
2148 * and the scratch space for merge sort. Check that its size does not
2149 * overflow size_t, which would allow for indexing beyond the end of the
2150 * malloc'd vector.
2151 */
2152 #if JS_BITS_PER_WORD == 32
2153 if ((size_t)len > ~(size_t)0 / (2 * sizeof(jsval))) {
2154 js_ReportAllocationOverflow(cx);
2155 return JS_FALSE;
2156 }
2157 #endif
2158 vec = (jsval *) cx->malloc(2 * (size_t) len * sizeof(jsval));
2159 if (!vec)
2160 return JS_FALSE;
2161
2162 /*
2163 * Initialize vec as a root. We will clear elements of vec one by
2164 * one while increasing tvr.count when we know that the property at
2165 * the corresponding index exists and its value must be rooted.
2166 *
2167 * In this way when sorting a huge mostly sparse array we will not
2168 * access the tail of vec corresponding to properties that do not
2169 * exist, allowing OS to avoiding committing RAM. See bug 330812.
2170 *
2171 * After this point control must flow through label out: to exit.
2172 */
2173 JS_PUSH_TEMP_ROOT(cx, 0, vec, &tvr);
2174
2175 /*
2176 * By ECMA 262, 15.4.4.11, a property that does not exist (which we
2177 * call a "hole") is always greater than an existing property with
2178 * value undefined and that is always greater than any other property.
2179 * Thus to sort holes and undefs we simply count them, sort the rest
2180 * of elements, append undefs after them and then make holes after
2181 * undefs.
2182 */
2183 undefs = 0;
2184 newlen = 0;
2185 all_strings = JS_TRUE;
2186 for (i = 0; i < len; i++) {
2187 ok = JS_CHECK_OPERATION_LIMIT(cx);
2188 if (!ok)
2189 goto out;
2190
2191 /* Clear vec[newlen] before including it in the rooted set. */
2192 vec[newlen] = JSVAL_NULL;
2193 tvr.count = newlen + 1;
2194 ok = GetArrayElement(cx, obj, i, &hole, &vec[newlen]);
2195 if (!ok)
2196 goto out;
2197
2198 if (hole)
2199 continue;
2200
2201 if (JSVAL_IS_VOID(vec[newlen])) {
2202 ++undefs;
2203 continue;
2204 }
2205
2206 /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
2207 all_strings &= JSVAL_IS_STRING(vec[newlen]);
2208
2209 ++newlen;
2210 }
2211
2212 if (newlen == 0) {
2213 /* The array has only holes and undefs. */
2214 ok = JS_TRUE;
2215 goto out;
2216 }
2217
2218 /*
2219 * The first newlen elements of vec are copied from the array object
2220 * (above). The remaining newlen positions are used as GC-rooted scratch
2221 * space for mergesort. We must clear the space before including it to
2222 * the root set covered by tvr.count. We assume JSVAL_NULL==0 to optimize
2223 * initialization using memset.
2224 */
2225 mergesort_tmp = vec + newlen;
2226 memset(mergesort_tmp, 0, newlen * sizeof(jsval));
2227 tvr.count = newlen * 2;
2228
2229 /* Here len == 2 * (newlen + undefs + number_of_holes). */
2230 if (fval == JSVAL_NULL) {
2231 /*
2232 * Sort using the default comparator converting all elements to
2233 * strings.
2234 */
2235 if (all_strings) {
2236 elemsize = sizeof(jsval);
2237 } else {
2238 /*
2239 * To avoid string conversion on each compare we do it only once
2240 * prior to sorting. But we also need the space for the original
2241 * values to recover the sorting result. To reuse
2242 * sort_compare_strings we move the original values to the odd
2243 * indexes in vec, put the string conversion results in the even
2244 * indexes and pass 2 * sizeof(jsval) as an element size to the
2245 * sorting function. In this way sort_compare_strings will only
2246 * see the string values when it casts the compare arguments as
2247 * pointers to jsval.
2248 *
2249 * This requires doubling the temporary storage including the
2250 * scratch space for the merge sort. Since vec already contains
2251 * the rooted scratch space for newlen elements at the tail, we
2252 * can use it to rearrange and convert to strings first and try
2253 * realloc only when we know that we successfully converted all
2254 * the elements.
2255 */
2256 #if JS_BITS_PER_WORD == 32
2257 if ((size_t)newlen > ~(size_t)0 / (4 * sizeof(jsval))) {
2258 js_ReportAllocationOverflow(cx);
2259 ok = JS_FALSE;
2260 goto out;
2261 }
2262 #endif
2263
2264 /*
2265 * Rearrange and string-convert the elements of the vector from
2266 * the tail here and, after sorting, move the results back
2267 * starting from the start to prevent overwrite the existing
2268 * elements.
2269 */
2270 i = newlen;
2271 do {
2272 --i;
2273 ok = JS_CHECK_OPERATION_LIMIT(cx);
2274 if (!ok)
2275 goto out;
2276 v = vec[i];
2277 str = js_ValueToString(cx, v);
2278 if (!str) {
2279 ok = JS_FALSE;
2280 goto out;
2281 }
2282 vec[2 * i] = STRING_TO_JSVAL(str);
2283 vec[2 * i + 1] = v;
2284 } while (i != 0);
2285
2286 JS_ASSERT(tvr.u.array == vec);
2287 vec = (jsval *) cx->realloc(vec,
2288 4 * (size_t) newlen * sizeof(jsval));
2289 if (!vec) {
2290 vec = tvr.u.array;
2291 ok = JS_FALSE;
2292 goto out;
2293 }
2294 tvr.u.array = vec;
2295 mergesort_tmp = vec + 2 * newlen;
2296 memset(mergesort_tmp, 0, newlen * 2 * sizeof(jsval));
2297 tvr.count = newlen * 4;
2298 elemsize = 2 * sizeof(jsval);
2299 }
2300 ok = js_MergeSort(vec, (size_t) newlen, elemsize,
2301 sort_compare_strings, cx, mergesort_tmp);
2302 if (!ok)
2303 goto out;
2304 if (!all_strings) {
2305 /*
2306 * We want to make the following loop fast and to unroot the
2307 * cached results of toString invocations before the operation
2308 * callback has a chance to run the GC. For this reason we do
2309 * not call JS_CHECK_OPERATION_LIMIT in the loop.
2310 */
2311 i = 0;
2312 do {
2313 vec[i] = vec[2 * i + 1];
2314 } while (++i != newlen);
2315 }
2316 } else {
2317 void *mark;
2318
2319 js_LeaveTrace(cx);
2320
2321 ca.context = cx;
2322 ca.fval = fval;
2323 ca.elemroot = js_AllocStack(cx, 2 + 2, &mark);
2324 if (!ca.elemroot) {
2325 ok = JS_FALSE;
2326 goto out;
2327 }
2328 ok = js_MergeSort(vec, (size_t) newlen, sizeof(jsval),
2329 comparator_stack_cast(sort_compare),
2330 &ca, mergesort_tmp);
2331 js_FreeStack(cx, mark);
2332 if (!ok)
2333 goto out;
2334 }
2335
2336 /*
2337 * We no longer need to root the scratch space for the merge sort, so
2338 * unroot it now to make the job of a potential GC under InitArrayElements
2339 * easier.
2340 */
2341 tvr.count = newlen;
2342 ok = InitArrayElements(cx, obj, 0, newlen, vec, TargetElementsMayContainValues,
2343 SourceVectorAllValues);
2344 if (!ok)
2345 goto out;
2346
2347 out:
2348 JS_POP_TEMP_ROOT(cx, &tvr);
2349 cx->free(vec);
2350 if (!ok)
2351 return JS_FALSE;
2352
2353 /* Set undefs that sorted after the rest of elements. */
2354 while (undefs != 0) {
2355 --undefs;
2356 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2357 !SetArrayElement(cx, obj, newlen++, JSVAL_VOID)) {
2358 return JS_FALSE;
2359 }
2360 }
2361
2362 /* Re-create any holes that sorted to the end of the array. */
2363 while (len > newlen) {
2364 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2365 !DeleteArrayElement(cx, obj, --len)) {
2366 return JS_FALSE;
2367 }
2368 }
2369 *vp = OBJECT_TO_JSVAL(obj);
2370 return JS_TRUE;
2371 }
2372
2373 /*
2374 * Perl-inspired push, pop, shift, unshift, and splice methods.
2375 */
2376 static JSBool
2377 array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2378 {
2379 jsuint length;
2380
2381 if (!js_GetLengthProperty(cx, obj, &length))
2382 return JS_FALSE;
2383 if (!InitArrayElements(cx, obj, length, argc, argv, TargetElementsMayContainValues,
2384 SourceVectorAllValues)) {
2385 return JS_FALSE;
2386 }
2387
2388 /* Per ECMA-262, return the new array length. */
2389 jsdouble newlength = length + jsdouble(argc);
2390 if (!IndexToValue(cx, newlength, rval))
2391 return JS_FALSE;
2392 return js_SetLengthProperty(cx, obj, newlength);
2393 }
2394
2395 static JSBool
2396 array_push1_dense(JSContext* cx, JSObject* obj, jsval v, jsval *rval)
2397 {
2398 uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
2399 if (INDEX_TOO_SPARSE(obj, length)) {
2400 if (!js_MakeArraySlow(cx, obj))
2401 return JS_FALSE;
2402 return array_push_slowly(cx, obj, 1, &v, rval);
2403 }
2404
2405 if (!EnsureCapacity(cx, obj, length + 1))
2406 return JS_FALSE;
2407 obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
2408
2409 JS_ASSERT(obj->dslots[length] == JSVAL_HOLE);
2410 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2411 obj->dslots[length] = v;
2412 return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], rval);
2413 }
2414
2415 JSBool JS_FASTCALL
2416 js_ArrayCompPush(JSContext *cx, JSObject *obj, jsval v)
2417 {
2418 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
2419 uint32_t length = (uint32_t) obj->fslots[JSSLOT_ARRAY_LENGTH];
2420 JS_ASSERT(length <= js_DenseArrayCapacity(obj));
2421
2422 if (length == js_DenseArrayCapacity(obj)) {
2423 if (length > JS_ARGS_LENGTH_MAX) {
2424 JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
2425 JSMSG_ARRAY_INIT_TOO_BIG);
2426 return JS_FALSE;
2427 }
2428
2429 if (!EnsureCapacity(cx, obj, length + 1))
2430 return JS_FALSE;
2431 }
2432 obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
2433 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2434 obj->dslots[length] = v;
2435 return JS_TRUE;
2436 }
2437 JS_DEFINE_CALLINFO_3(extern, BOOL, js_ArrayCompPush, CONTEXT, OBJECT, JSVAL, 0, 0)
2438
2439 #ifdef JS_TRACER
2440 static jsval FASTCALL
2441 Array_p_push1(JSContext* cx, JSObject* obj, jsval v)
2442 {
2443 JSAutoTempValueRooter tvr(cx, v);
2444 if (OBJ_IS_DENSE_ARRAY(cx, obj)
2445 ? array_push1_dense(cx, obj, v, tvr.addr())
2446 : array_push_slowly(cx, obj, 1, tvr.addr(), tvr.addr())) {
2447 return tvr.value();
2448 }
2449 js_SetBuiltinError(cx);
2450 return JSVAL_VOID;
2451 }
2452 #endif
2453
2454 static JSBool
2455 array_push(JSContext *cx, uintN argc, jsval *vp)
2456 {
2457 JSObject *obj;
2458
2459 /* Insist on one argument and obj of the expected class. */
2460 obj = JS_THIS_OBJECT(cx, vp);
2461 if (!obj)
2462 return JS_FALSE;
2463 if (argc != 1 || !OBJ_IS_DENSE_ARRAY(cx, obj))
2464 return array_push_slowly(cx, obj, argc, vp + 2, vp);
2465
2466 return array_push1_dense(cx, obj, vp[2], vp);
2467 }
2468
2469 static JSBool
2470 array_pop_slowly(JSContext *cx, JSObject* obj, jsval *vp)
2471 {
2472 jsuint index;
2473 JSBool hole;
2474
2475 if (!js_GetLengthProperty(cx, obj, &index))
2476 return JS_FALSE;
2477 if (index == 0) {
2478 *vp = JSVAL_VOID;
2479 } else {
2480 index--;
2481
2482 /* Get the to-be-deleted property's value into vp. */
2483 if (!GetArrayElement(cx, obj, index, &hole, vp))
2484 return JS_FALSE;
2485 if (!hole && !DeleteArrayElement(cx, obj, index))
2486 return JS_FALSE;
2487 }
2488 return js_SetLengthProperty(cx, obj, index);
2489 }
2490
2491 static JSBool
2492 array_pop_dense(JSContext *cx, JSObject* obj, jsval *vp)
2493 {
2494 jsuint index;
2495 JSBool hole;
2496
2497 index = obj->fslots[JSSLOT_ARRAY_LENGTH];
2498 if (index == 0) {
2499 *vp = JSVAL_VOID;
2500 return JS_TRUE;
2501 }
2502 index--;
2503 if (!GetArrayElement(cx, obj, index, &hole, vp))
2504 return JS_FALSE;
2505 if (!hole && !DeleteArrayElement(cx, obj, index))
2506 return JS_FALSE;
2507 obj->fslots[JSSLOT_ARRAY_LENGTH] = index;
2508 return JS_TRUE;
2509 }
2510
2511 #ifdef JS_TRACER
2512 static jsval FASTCALL
2513 Array_p_pop(JSContext* cx, JSObject* obj)
2514 {
2515 JSAutoTempValueRooter tvr(cx);
2516 if (OBJ_IS_DENSE_ARRAY(cx, obj)
2517 ? array_pop_dense(cx, obj, tvr.addr())
2518 : array_pop_slowly(cx, obj, tvr.addr())) {
2519 return tvr.value();
2520 }
2521 js_SetBuiltinError(cx);
2522 return JSVAL_VOID;
2523 }
2524 #endif
2525
2526 static JSBool
2527 array_pop(JSContext *cx, uintN argc, jsval *vp)
2528 {
2529 JSObject *obj;
2530
2531 obj = JS_THIS_OBJECT(cx, vp);
2532 if (!obj)
2533 return JS_FALSE;
2534 if (OBJ_IS_DENSE_ARRAY(cx, obj))
2535 return array_pop_dense(cx, obj, vp);
2536 return array_pop_slowly(cx, obj, vp);
2537 }
2538
2539 static JSBool
2540 array_shift(JSContext *cx, uintN argc, jsval *vp)
2541 {
2542 JSObject *obj;
2543 jsuint length, i;
2544 JSBool hole;
2545
2546 obj = JS_THIS_OBJECT(cx, vp);
2547 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2548 return JS_FALSE;
2549 if (length == 0) {
2550 *vp = JSVAL_VOID;
2551 } else {
2552 length--;
2553
2554 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2555 length < js_DenseArrayCapacity(obj)) {
2556 if (JS_LIKELY(obj->dslots != NULL)) {
2557 *vp = obj->dslots[0];
2558 if (*vp == JSVAL_HOLE)
2559 *vp = JSVAL_VOID;
2560 else
2561 obj->fslots[JSSLOT_ARRAY_COUNT]--;
2562 memmove(obj->dslots, obj->dslots + 1, length * sizeof(jsval));
2563 obj->dslots[length] = JSVAL_HOLE;
2564 } else {
2565 /*
2566 * We don't need to modify the indexed properties of an empty array
2567 * with an explicitly set non-zero length when shift() is called on
2568 * it, but note fallthrough to reduce the length by one.
2569 */
2570 JS_ASSERT(obj->fslots[JSSLOT_ARRAY_COUNT] == 0);
2571 *vp = JSVAL_VOID;
2572 }
2573 } else {
2574 /* Get the to-be-deleted property's value into vp ASAP. */
2575 if (!GetArrayElement(cx, obj, 0, &hole, vp))
2576 return JS_FALSE;
2577
2578 /* Slide down the array above the first element. */
2579 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2580 for (i = 0; i != length; i++) {
2581 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2582 !GetArrayElement(cx, obj, i + 1, &hole, tvr.addr()) ||
2583 !SetOrDeleteArrayElement(cx, obj, i, hole, tvr.value())) {
2584 return JS_FALSE;
2585 }
2586 }
2587
2588 /* Delete the only or last element when it exists. */
2589 if (!hole && !DeleteArrayElement(cx, obj, length))
2590 return JS_FALSE;
2591 }
2592 }
2593 return js_SetLengthProperty(cx, obj, length);
2594 }
2595
2596 static JSBool
2597 array_unshift(JSContext *cx, uintN argc, jsval *vp)
2598 {
2599 JSObject *obj;
2600 jsval *argv;
2601 jsuint length;
2602 JSBool hole;
2603 jsdouble last, newlen;
2604
2605 obj = JS_THIS_OBJECT(cx, vp);
2606 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2607 return JS_FALSE;
2608 newlen = length;
2609 if (argc > 0) {
2610 /* Slide up the array to make room for argc at the bottom. */
2611 argv = JS_ARGV(cx, vp);
2612 if (length > 0) {
2613 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2614 !INDEX_TOO_SPARSE(obj, newlen + argc)) {
2615 JS_ASSERT(newlen + argc == length + argc);
2616 if (!EnsureCapacity(cx, obj, length + argc))
2617 return JS_FALSE;
2618 memmove(obj->dslots + argc, obj->dslots, length * sizeof(jsval));
2619 for (uint32 i = 0; i < argc; i++)
2620 obj->dslots[i] = JSVAL_HOLE;
2621 } else {
2622 last = length;
2623 jsdouble upperIndex = last + argc;
2624 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2625 do {
2626 --last, --upperIndex;
2627 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2628 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2629 !SetOrDeleteArrayElement(cx, obj, upperIndex, hole, tvr.value())) {
2630 return JS_FALSE;
2631 }
2632 } while (last != 0);
2633 }
2634 }
2635
2636 /* Copy from argv to the bottom of the array. */
2637 if (!InitArrayElements(cx, obj, 0, argc, argv, TargetElementsAllHoles, SourceVectorAllValues))
2638 return JS_FALSE;
2639
2640 newlen += argc;
2641 if (!js_SetLengthProperty(cx, obj, newlen))
2642 return JS_FALSE;
2643 }
2644
2645 /* Follow Perl by returning the new array length. */
2646 return IndexToValue(cx, newlen, vp);
2647 }
2648
2649 static JSBool
2650 array_splice(JSContext *cx, uintN argc, jsval *vp)
2651 {
2652 jsval *argv;
2653 JSObject *obj;
2654 jsuint length, begin, end, count, delta, last;
2655 jsdouble d;
2656 JSBool hole;
2657 JSObject *obj2;
2658
2659 /*
2660 * Create a new array value to return. Our ECMA v2 proposal specs
2661 * that splice always returns an array value, even when given no
2662 * arguments. We think this is best because it eliminates the need
2663 * for callers to do an extra test to handle the empty splice case.
2664 */
2665 obj2 = js_NewArrayObject(cx, 0, NULL);
2666 if (!obj2)
2667 return JS_FALSE;
2668 *vp = OBJECT_TO_JSVAL(obj2);
2669
2670 /* Nothing to do if no args. Otherwise get length. */
2671 if (argc == 0)
2672 return JS_TRUE;
2673 argv = JS_ARGV(cx, vp);
2674 obj = JS_THIS_OBJECT(cx, vp);
2675 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2676 return JS_FALSE;
2677
2678 /* Convert the first argument into a starting index. */
2679 d = js_ValueToNumber(cx, argv);
2680 if (JSVAL_IS_NULL(*argv))
2681 return JS_FALSE;
2682 d = js_DoubleToInteger(d);
2683 if (d < 0) {
2684 d += length;
2685 if (d < 0)
2686 d = 0;
2687 } else if (d > length) {
2688 d = length;
2689 }
2690 begin = (jsuint)d; /* d has been clamped to uint32 */
2691 argc--;
2692 argv++;
2693
2694 /* Convert the second argument from a count into a fencepost index. */
2695 delta = length - begin;
2696 if (argc == 0) {
2697 count = delta;
2698 end = length;
2699 } else {
2700 d = js_ValueToNumber(cx, argv);
2701 if (JSVAL_IS_NULL(*argv))
2702 return JS_FALSE;
2703 d = js_DoubleToInteger(d);
2704 if (d < 0)
2705 d = 0;
2706 else if (d > delta)
2707 d = delta;
2708 count = (jsuint)d;
2709 end = begin + count;
2710 argc--;
2711 argv++;
2712 }
2713
2714 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2715
2716 /* If there are elements to remove, put them into the return value. */
2717 if (count > 0) {
2718 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2719 !js_PrototypeHasIndexedProperties(cx, obj2) &&
2720 end <= js_DenseArrayCapacity(obj)) {
2721 if (!InitArrayObject(cx, obj2, count, obj->dslots + begin,
2722 obj->fslots[JSSLOT_ARRAY_COUNT] !=
2723 obj->fslots[JSSLOT_ARRAY_LENGTH])) {
2724 return JS_FALSE;
2725 }
2726 } else {
2727 for (last = begin; last < end; last++) {
2728 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2729 !GetArrayElement(cx, obj, last, &hole, tvr.addr())) {
2730 return JS_FALSE;
2731 }
2732
2733 /* Copy tvr.value() to the new array unless it's a hole. */
2734 if (!hole && !SetArrayElement(cx, obj2, last - begin, tvr.value()))
2735 return JS_FALSE;
2736 }
2737
2738 if (!js_SetLengthProperty(cx, obj2, count))
2739 return JS_FALSE;
2740 }
2741 }
2742
2743 /* Find the direction (up or down) to copy and make way for argv. */
2744 if (argc > count) {
2745 delta = (jsuint)argc - count;
2746 last = length;
2747 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2748 length <= js_DenseArrayCapacity(obj) &&
2749 (length == 0 || obj->dslots[length - 1] != JSVAL_HOLE)) {
2750 if (!EnsureCapacity(cx, obj, length + delta))
2751 return JS_FALSE;
2752 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2753 while (last-- > end) {
2754 jsval srcval = obj->dslots[last];
2755 jsval* dest = &obj->dslots[last + delta];
2756 if (*dest == JSVAL_HOLE && srcval != JSVAL_HOLE)
2757 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2758 *dest = srcval;
2759 }
2760 obj->fslots[JSSLOT_ARRAY_LENGTH] += delta;
2761 } else {
2762 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2763 while (last-- > end) {
2764 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2765 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2766 !SetOrDeleteArrayElement(cx, obj, last + delta, hole, tvr.value())) {
2767 return JS_FALSE;
2768 }
2769 }
2770 }
2771 length += delta;
2772 } else if (argc < count) {
2773 delta = count - (jsuint)argc;
2774 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2775 length <= js_DenseArrayCapacity(obj)) {
2776 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2777 for (last = end; last < length; last++) {
2778 jsval srcval = obj->dslots[last];
2779 jsval* dest = &obj->dslots[last - delta];
2780 if (*dest == JSVAL_HOLE && srcval != JSVAL_HOLE)
2781 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2782 *dest = srcval;
2783 }
2784 } else {
2785 for (last = end; last < length; last++) {
2786 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2787 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2788 !SetOrDeleteArrayElement(cx, obj, last - delta, hole, tvr.value())) {
2789 return JS_FALSE;
2790 }
2791 }
2792 }
2793 length -= delta;
2794 }
2795
2796 /*
2797 * Copy from argv into the hole to complete the splice, and update length in
2798 * case we deleted elements from the end.
2799 */
2800 return InitArrayElements(cx, obj, begin, argc, argv, TargetElementsMayContainValues,
2801 SourceVectorAllValues) &&
2802 js_SetLengthProperty(cx, obj, length);
2803 }
2804
2805 /*
2806 * Python-esque sequence operations.
2807 */
2808 static JSBool
2809 array_concat(JSContext *cx, uintN argc, jsval *vp)
2810 {
2811 jsval *argv, v;
2812 JSObject *aobj, *nobj;
2813 jsuint length, alength, slot;
2814 uintN i;
2815 JSBool hole;
2816
2817 /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
2818 argv = JS_ARGV(cx, vp) - 1;
2819 JS_ASSERT(JS_THIS_OBJECT(cx, vp) == JSVAL_TO_OBJECT(argv[0]));
2820
2821 /* Create a new Array object and root it using *vp. */
2822 aobj = JS_THIS_OBJECT(cx, vp);
2823 if (OBJ_IS_DENSE_ARRAY(cx, aobj)) {
2824 /*
2825 * Clone aobj but pass the minimum of its length and capacity, to
2826 * handle a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In
2827 * such a case we'll pass 8 (not 3) due to ARRAY_CAPACITY_MIN, which
2828 * will cause nobj to be over-allocated to 16. But in the normal case
2829 * where length is <= capacity, nobj and aobj will have the same
2830 * capacity.
2831 */
2832 length = aobj->fslots[JSSLOT_ARRAY_LENGTH];
2833 jsuint capacity = js_DenseArrayCapacity(aobj);
2834 nobj = js_NewArrayObject(cx, JS_MIN(length, capacity), aobj->dslots,
2835 aobj->fslots[JSSLOT_ARRAY_COUNT] !=
2836 (jsval) length);
2837 if (!nobj)
2838 return JS_FALSE;
2839 nobj->fslots[JSSLOT_ARRAY_LENGTH] = length;
2840 *vp = OBJECT_TO_JSVAL(nobj);
2841 if (argc == 0)
2842 return JS_TRUE;
2843 argc--;
2844 argv++;
2845 } else {
2846 nobj = js_NewArrayObject(cx, 0, NULL);
2847 if (!nobj)
2848 return JS_FALSE;
2849 *vp = OBJECT_TO_JSVAL(nobj);
2850 length = 0;
2851 }
2852
2853 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2854
2855 /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
2856 for (i = 0; i <= argc; i++) {
2857 if (!JS_CHECK_OPERATION_LIMIT(cx))
2858 return false;
2859 v = argv[i];
2860 if (!JSVAL_IS_PRIMITIVE(v)) {
2861 JSObject *wobj;
2862
2863 aobj = JSVAL_TO_OBJECT(v);
2864 wobj = js_GetWrappedObject(cx, aobj);
2865 if (OBJ_IS_ARRAY(cx, wobj)) {
2866 jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
2867 if (!aobj->getProperty(cx, id, tvr.addr()))
2868 return false;
2869 alength = ValueIsLength(cx, tvr.addr());
2870 if (JSVAL_IS_NULL(tvr.value()))
2871 return false;
2872 for (slot = 0; slot < alength; slot++) {
2873 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2874 !GetArrayElement(cx, aobj, slot, &hole, tvr.addr())) {
2875 return false;
2876 }
2877
2878 /*
2879 * Per ECMA 262, 15.4.4.4, step 9, ignore non-existent
2880 * properties.
2881 */
2882 if (!hole &&
2883 !SetArrayElement(cx, nobj, length+slot, tvr.value())) {
2884 return false;
2885 }
2886 }
2887 length += alength;
2888 continue;
2889 }
2890 }
2891
2892 if (!SetArrayElement(cx, nobj, length, v))
2893 return false;
2894 length++;
2895 }
2896
2897 return js_SetLengthProperty(cx, nobj, length);
2898 }
2899
2900 static JSBool
2901 array_slice(JSContext *cx, uintN argc, jsval *vp)
2902 {
2903 jsval *argv;
2904 JSObject *nobj, *obj;
2905 jsuint length, begin, end, slot;
2906 jsdouble d;
2907 JSBool hole;
2908
2909 argv = JS_ARGV(cx, vp);
2910
2911 obj = JS_THIS_OBJECT(cx, vp);
2912 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2913 return JS_FALSE;
2914 begin = 0;
2915 end = length;
2916
2917 if (argc > 0) {
2918 d = js_ValueToNumber(cx, &argv[0]);
2919 if (JSVAL_IS_NULL(argv[0]))
2920 return JS_FALSE;
2921 d = js_DoubleToInteger(d);
2922 if (d < 0) {
2923 d += length;
2924 if (d < 0)
2925 d = 0;
2926 } else if (d > length) {
2927 d = length;
2928 }
2929 begin = (jsuint)d;
2930
2931 if (argc > 1) {
2932 d = js_ValueToNumber(cx, &argv[1]);
2933 if (JSVAL_IS_NULL(argv[1]))
2934 return JS_FALSE;
2935 d = js_DoubleToInteger(d);
2936 if (d < 0) {
2937 d += length;
2938 if (d < 0)
2939 d = 0;
2940 } else if (d > length) {
2941 d = length;
2942 }
2943 end = (jsuint)d;
2944 }
2945 }
2946
2947 if (begin > end)
2948 begin = end;
2949
2950 if (OBJ_IS_DENSE_ARRAY(cx, obj) && end <= js_DenseArrayCapacity(obj) &&
2951 !js_PrototypeHasIndexedProperties(cx, obj)) {
2952 nobj = js_NewArrayObject(cx, end - begin, obj->dslots + begin,
2953 obj->fslots[JSSLOT_ARRAY_COUNT] !=
2954 obj->fslots[JSSLOT_ARRAY_LENGTH]);
2955 if (!nobj)
2956 return JS_FALSE;
2957 *vp = OBJECT_TO_JSVAL(nobj);
2958 return JS_TRUE;
2959 }
2960
2961 /* Create a new Array object and root it using *vp. */
2962 nobj = js_NewArrayObject(cx, 0, NULL);
2963 if (!nobj)
2964 return JS_FALSE;
2965 *vp = OBJECT_TO_JSVAL(nobj);
2966
2967 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2968 for (slot = begin; slot < end; slot++) {
2969 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2970 !GetArrayElement(cx, obj, slot, &hole, tvr.addr())) {
2971 return JS_FALSE;
2972 }
2973 if (!hole && !SetArrayElement(cx, nobj, slot - begin, tvr.value()))
2974 return JS_FALSE;
2975 }
2976
2977 return js_SetLengthProperty(cx, nobj, end - begin);
2978 }
2979
2980 #if JS_HAS_ARRAY_EXTRAS
2981
2982 static JSBool
2983 array_indexOfHelper(JSContext *cx, JSBool isLast, uintN argc, jsval *vp)
2984 {
2985 JSObject *obj;
2986 jsuint length, i, stop;
2987 jsval tosearch;
2988 jsint direction;
2989 JSBool hole;
2990
2991 obj = JS_THIS_OBJECT(cx, vp);
2992 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2993 return JS_FALSE;
2994 if (length == 0)
2995 goto not_found;
2996
2997 if (argc <= 1) {
2998 i = isLast ? length - 1 : 0;
2999 tosearch = (argc != 0) ? vp[2] : JSVAL_VOID;
3000 } else {
3001 jsdouble start;
3002
3003 tosearch = vp[2];
3004 start = js_ValueToNumber(cx, &vp[3]);
3005 if (JSVAL_IS_NULL(vp[3]))
3006 return JS_FALSE;
3007 start = js_DoubleToInteger(start);
3008 if (start < 0) {
3009 start += length;
3010 if (start < 0) {
3011 if (isLast)
3012 goto not_found;
3013 i = 0;
3014 } else {
3015 i = (jsuint)start;
3016 }
3017 } else if (start >= length) {
3018 if (!isLast)
3019 goto not_found;
3020 i = length - 1;
3021 } else {
3022 i = (jsuint)start;
3023 }
3024 }
3025
3026 if (isLast) {
3027 stop = 0;
3028 direction = -1;
3029 } else {
3030 stop = length - 1;
3031 direction = 1;
3032 }
3033
3034 for (;;) {
3035 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
3036 !GetArrayElement(cx, obj, (jsuint)i, &hole, vp)) {
3037 return JS_FALSE;
3038 }
3039 if (!hole && js_StrictlyEqual(cx, *vp, tosearch))
3040 return js_NewNumberInRootedValue(cx, i, vp);
3041 if (i == stop)
3042 goto not_found;
3043 i += direction;
3044 }
3045
3046 not_found:
3047 *vp = INT_TO_JSVAL(-1);
3048 return JS_TRUE;
3049 }
3050
3051 static JSBool
3052 array_indexOf(JSContext *cx, uintN argc, jsval *vp)
3053 {
3054 return array_indexOfHelper(cx, JS_FALSE, argc, vp);
3055 }
3056
3057 static JSBool
3058 array_lastIndexOf(JSContext *cx, uintN argc, jsval *vp)
3059 {
3060 return array_indexOfHelper(cx, JS_TRUE, argc, vp);
3061 }
3062
3063 /* Order is important; extras that take a predicate funarg must follow MAP. */
3064 typedef enum ArrayExtraMode {
3065 FOREACH,
3066 REDUCE,
3067 REDUCE_RIGHT,
3068 MAP,
3069 FILTER,
3070 SOME,
3071 EVERY
3072 } ArrayExtraMode;
3073
3074 #define REDUCE_MODE(mode) ((mode) == REDUCE || (mode) == REDUCE_RIGHT)
3075
3076 static JSBool
3077 array_extra(JSContext *cx, ArrayExtraMode mode, uintN argc, jsval *vp)
3078 {
3079 JSObject *obj;
3080 jsuint length, newlen;
3081 jsval *argv, *elemroot, *invokevp, *sp;
3082 JSBool ok, cond, hole;
3083 JSObject *callable, *thisp, *newarr;
3084 jsint start, end, step, i;
3085 void *mark;
3086
3087 obj = JS_THIS_OBJECT(cx, vp);
3088 if (!obj || !js_GetLengthProperty(cx, obj, &length))
3089 return JS_FALSE;
3090
3091 /*
3092 * First, get or compute our callee, so that we error out consistently
3093 * when passed a non-callable object.
3094 */
3095 if (argc == 0) {
3096 js_ReportMissingArg(cx, vp, 0);
3097 return JS_FALSE;
3098 }
3099 argv = vp + 2;
3100 callable = js_ValueToCallableObject(cx, &argv[0], JSV2F_SEARCH_STACK);
3101 if (!callable)
3102 return JS_FALSE;
3103
3104 /*
3105 * Set our initial return condition, used for zero-length array cases
3106 * (and pre-size our map return to match our known length, for all cases).
3107 */
3108 #ifdef __GNUC__ /* quell GCC overwarning */
3109 newlen = 0;
3110 newarr = NULL;
3111 #endif
3112 start = 0, end = length, step = 1;
3113
3114 switch (mode) {
3115 case REDUCE_RIGHT:
3116 start = length - 1, end = -1, step = -1;
3117 /* FALL THROUGH */
3118 case REDUCE:
3119 if (length == 0 && argc == 1) {
3120 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3121 JSMSG_EMPTY_ARRAY_REDUCE);
3122 return JS_FALSE;
3123 }
3124 if (argc >= 2) {
3125 *vp = argv[1];
3126 } else {
3127 do {
3128 if (!GetArrayElement(cx, obj, start, &hole, vp))
3129 return JS_FALSE;
3130 start += step;
3131 } while (hole && start != end);
3132
3133 if (hole && start == end) {
3134 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3135 JSMSG_EMPTY_ARRAY_REDUCE);
3136 return JS_FALSE;
3137 }
3138 }
3139 break;
3140 case MAP:
3141 case FILTER:
3142 newlen = (mode == MAP) ? length : 0;
3143 newarr = js_NewArrayObject(cx, newlen, NULL);
3144 if (!newarr)
3145 return JS_FALSE;
3146 *vp = OBJECT_TO_JSVAL(newarr);
3147 break;
3148 case SOME:
3149 *vp = JSVAL_FALSE;
3150 break;
3151 case EVERY:
3152 *vp = JSVAL_TRUE;
3153 break;
3154 case FOREACH:
3155 *vp = JSVAL_VOID;
3156 break;
3157 }
3158
3159 if (length == 0)
3160 return JS_TRUE;
3161
3162 if (argc > 1 && !REDUCE_MODE(mode)) {
3163 if (!js_ValueToObject(cx, argv[1], &thisp))
3164 return JS_FALSE;
3165 argv[1] = OBJECT_TO_JSVAL(thisp);
3166 } else {
3167 thisp = NULL;
3168 }
3169
3170 /*
3171 * For all but REDUCE, we call with 3 args (value, index, array). REDUCE
3172 * requires 4 args (accum, value, index, array).
3173 */
3174 js_LeaveTrace(cx);
3175 argc = 3 + REDUCE_MODE(mode);
3176 elemroot = js_AllocStack(cx, 1 + 2 + argc, &mark);
3177 if (!elemroot)
3178 return JS_FALSE;
3179
3180 MUST_FLOW_THROUGH("out");
3181 ok = JS_TRUE;
3182 invokevp = elemroot + 1;
3183
3184 for (i = start; i != end; i += step) {
3185 ok = JS_CHECK_OPERATION_LIMIT(cx) &&
3186 GetArrayElement(cx, obj, i, &hole, elemroot);
3187 if (!ok)
3188 goto out;
3189 if (hole)
3190 continue;
3191
3192 /*
3193 * Push callable and 'this', then args. We must do this for every
3194 * iteration around the loop since js_Invoke uses spbase[0] for return
3195 * value storage, while some native functions use spbase[1] for local
3196 * rooting.
3197 */
3198 sp = invokevp;
3199 *sp++ = OBJECT_TO_JSVAL(callable);
3200 *sp++ = OBJECT_TO_JSVAL(thisp);
3201 if (REDUCE_MODE(mode))
3202 *sp++ = *vp;
3203 *sp++ = *elemroot;
3204 *sp++ = INT_TO_JSVAL(i);
3205 *sp++ = OBJECT_TO_JSVAL(obj);
3206
3207 /* Do the call. */
3208 ok = js_Invoke(cx, argc, invokevp, 0);
3209 if (!ok)
3210 break;
3211
3212 if (mode > MAP)
3213 cond = js_ValueToBoolean(*invokevp);
3214 #ifdef __GNUC__ /* quell GCC overwarning */
3215 else
3216 cond = JS_FALSE;
3217 #endif
3218
3219 switch (mode) {
3220 case FOREACH:
3221 break;
3222 case REDUCE:
3223 case REDUCE_RIGHT:
3224 *vp = *invokevp;
3225 break;
3226 case MAP:
3227 ok = SetArrayElement(cx, newarr, i, *invokevp);
3228 if (!ok)
3229 goto out;
3230 break;
3231 case FILTER:
3232 if (!cond)
3233 break;
3234 /* The filter passed *elemroot, so push it onto our result. */
3235 ok = SetArrayElement(cx, newarr, newlen++, *elemroot);
3236 if (!ok)
3237 goto out;
3238 break;
3239 case SOME:
3240 if (cond) {
3241 *vp = JSVAL_TRUE;
3242 goto out;
3243 }
3244 break;
3245 case EVERY:
3246 if (!cond) {
3247 *vp = JSVAL_FALSE;
3248 goto out;
3249 }
3250 break;
3251 }
3252 }
3253
3254 out:
3255 js_FreeStack(cx, mark);
3256 if (ok && mode == FILTER)
3257 ok = js_SetLengthProperty(cx, newarr, newlen);
3258 return ok;
3259 }
3260
3261 static JSBool
3262 array_forEach(JSContext *cx, uintN argc, jsval *vp)
3263 {
3264 return array_extra(cx, FOREACH, argc, vp);
3265 }
3266
3267 static JSBool
3268 array_map(JSContext *cx, uintN argc, jsval *vp)
3269 {
3270