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

Contents of /trunk/js/jsarray.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 585 - (show annotations)
Sun Sep 12 15:13:23 2010 UTC (9 years ago) by siliconforks
File size: 110714 byte(s)
Update to SpiderMonkey from Firefox 3.6.9.

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
740 JSAutoTempValueRooter root(cx, proto);
741 return proto->lookupProperty(cx, id, objp, propp);
742 }
743
744 static void
745 array_dropProperty(JSContext *cx, JSObject *obj, JSProperty *prop)
746 {
747 JS_ASSERT(IsDenseArrayId(cx, obj, (jsid) prop));
748 }
749
750 JSBool
751 js_GetDenseArrayElementValue(JSContext *cx, JSObject *obj, JSProperty *prop,
752 jsval *vp)
753 {
754 jsid id = (jsid) prop;
755 JS_ASSERT(IsDenseArrayId(cx, obj, id));
756
757 uint32 i;
758 if (!js_IdIsIndex(id, &i)) {
759 JS_ASSERT(id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom));
760 return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
761 }
762 *vp = obj->dslots[i];
763 return JS_TRUE;
764 }
765
766 static JSBool
767 array_getProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
768 {
769 uint32 i;
770
771 if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
772 return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], vp);
773
774 if (id == ATOM_TO_JSID(cx->runtime->atomState.protoAtom)) {
775 *vp = OBJECT_TO_JSVAL(obj->getProto());
776 return JS_TRUE;
777 }
778
779 if (!OBJ_IS_DENSE_ARRAY(cx, obj))
780 return js_GetProperty(cx, obj, id, vp);
781
782 if (!js_IdIsIndex(ID_TO_VALUE(id), &i) || i >= js_DenseArrayCapacity(obj) ||
783 obj->dslots[i] == JSVAL_HOLE) {
784 JSObject *obj2;
785 JSProperty *prop;
786 JSScopeProperty *sprop;
787
788 JSObject *proto = STOBJ_GET_PROTO(obj);
789 if (!proto) {
790 *vp = JSVAL_VOID;
791 return JS_TRUE;
792 }
793
794 *vp = JSVAL_VOID;
795 if (js_LookupPropertyWithFlags(cx, proto, id, cx->resolveFlags,
796 &obj2, &prop) < 0)
797 return JS_FALSE;
798
799 if (prop) {
800 if (OBJ_IS_NATIVE(obj2)) {
801 sprop = (JSScopeProperty *) prop;
802 if (!js_NativeGet(cx, obj, obj2, sprop, vp))
803 return JS_FALSE;
804 }
805 obj2->dropProperty(cx, prop);
806 }
807 return JS_TRUE;
808 }
809
810 *vp = obj->dslots[i];
811 return JS_TRUE;
812 }
813
814 static JSBool
815 slowarray_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
816 {
817 jsuint index, length;
818
819 if (!js_IdIsIndex(id, &index))
820 return JS_TRUE;
821 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
822 if (index >= length)
823 obj->fslots[JSSLOT_ARRAY_LENGTH] = index + 1;
824 return JS_TRUE;
825 }
826
827 static JSObjectOps js_SlowArrayObjectOps;
828
829 static JSObjectOps *
830 slowarray_getObjectOps(JSContext *cx, JSClass *clasp)
831 {
832 return &js_SlowArrayObjectOps;
833 }
834
835 static JSBool
836 array_setProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
837 {
838 uint32 i;
839
840 if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
841 return array_length_setter(cx, obj, id, vp);
842
843 if (!OBJ_IS_DENSE_ARRAY(cx, obj))
844 return js_SetProperty(cx, obj, id, vp);
845
846 if (!js_IdIsIndex(id, &i) || INDEX_TOO_SPARSE(obj, i)) {
847 if (!js_MakeArraySlow(cx, obj))
848 return JS_FALSE;
849 return js_SetProperty(cx, obj, id, vp);
850 }
851
852 if (!EnsureCapacity(cx, obj, i + 1))
853 return JS_FALSE;
854
855 if (i >= (uint32)obj->fslots[JSSLOT_ARRAY_LENGTH])
856 obj->fslots[JSSLOT_ARRAY_LENGTH] = i + 1;
857 if (obj->dslots[i] == JSVAL_HOLE)
858 obj->fslots[JSSLOT_ARRAY_COUNT]++;
859 obj->dslots[i] = *vp;
860 return JS_TRUE;
861 }
862
863 JSBool
864 js_PrototypeHasIndexedProperties(JSContext *cx, JSObject *obj)
865 {
866 /*
867 * Walk up the prototype chain and see if this indexed element already
868 * exists. If we hit the end of the prototype chain, it's safe to set the
869 * element on the original object.
870 */
871 while ((obj = obj->getProto()) != NULL) {
872 /*
873 * If the prototype is a non-native object (possibly a dense array), or
874 * a native object (possibly a slow array) that has indexed properties,
875 * return true.
876 */
877 if (!OBJ_IS_NATIVE(obj))
878 return JS_TRUE;
879 if (OBJ_SCOPE(obj)->hadIndexedProperties())
880 return JS_TRUE;
881 }
882 return JS_FALSE;
883 }
884
885 #ifdef JS_TRACER
886
887 static inline JSBool FASTCALL
888 dense_grow(JSContext* cx, JSObject* obj, jsint i, jsval v)
889 {
890 /*
891 * Let the interpreter worry about negative array indexes.
892 */
893 JS_ASSERT((MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) == (sizeof(jsval) != sizeof(uint32)));
894 if (MAX_DSLOTS_LENGTH > MAX_DSLOTS_LENGTH32) {
895 /*
896 * Have to check for negative values bleeding through on 64-bit machines only,
897 * since we can't allocate large enough arrays for this on 32-bit machines.
898 */
899 if (i < 0)
900 return JS_FALSE;
901 }
902
903 /*
904 * If needed, grow the array as long it remains dense, otherwise fall off trace.
905 */
906 jsuint u = jsuint(i);
907 jsuint capacity = js_DenseArrayCapacity(obj);
908 if ((u >= capacity) && (INDEX_TOO_SPARSE(obj, u) || !EnsureCapacity(cx, obj, u + 1)))
909 return JS_FALSE;
910
911 if (obj->dslots[u] == JSVAL_HOLE) {
912 if (js_PrototypeHasIndexedProperties(cx, obj))
913 return JS_FALSE;
914
915 if (u >= jsuint(obj->fslots[JSSLOT_ARRAY_LENGTH]))
916 obj->fslots[JSSLOT_ARRAY_LENGTH] = u + 1;
917 ++obj->fslots[JSSLOT_ARRAY_COUNT];
918 }
919
920 obj->dslots[u] = v;
921 return JS_TRUE;
922 }
923
924
925 JSBool FASTCALL
926 js_Array_dense_setelem(JSContext* cx, JSObject* obj, jsint i, jsval v)
927 {
928 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
929 return dense_grow(cx, obj, i, v);
930 }
931 JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem, CONTEXT, OBJECT, INT32, JSVAL, 0, 0)
932
933 JSBool FASTCALL
934 js_Array_dense_setelem_int(JSContext* cx, JSObject* obj, jsint i, int32 j)
935 {
936 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
937
938 jsval v;
939 if (JS_LIKELY(INT_FITS_IN_JSVAL(j))) {
940 v = INT_TO_JSVAL(j);
941 } else {
942 jsdouble d = (jsdouble)j;
943 if (!js_NewDoubleInRootedValue(cx, d, &v))
944 return JS_FALSE;
945 }
946
947 return dense_grow(cx, obj, i, v);
948 }
949 JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_int, CONTEXT, OBJECT, INT32, INT32, 0, 0)
950
951 JSBool FASTCALL
952 js_Array_dense_setelem_double(JSContext* cx, JSObject* obj, jsint i, jsdouble d)
953 {
954 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
955
956 jsval v;
957 jsint j;
958
959 if (JS_LIKELY(JSDOUBLE_IS_INT(d, j) && INT_FITS_IN_JSVAL(j))) {
960 v = INT_TO_JSVAL(j);
961 } else {
962 if (!js_NewDoubleInRootedValue(cx, d, &v))
963 return JS_FALSE;
964 }
965
966 return dense_grow(cx, obj, i, v);
967 }
968 JS_DEFINE_CALLINFO_4(extern, BOOL, js_Array_dense_setelem_double, CONTEXT, OBJECT, INT32, DOUBLE, 0, 0)
969 #endif
970
971 static JSBool
972 array_defineProperty(JSContext *cx, JSObject *obj, jsid id, jsval value,
973 JSPropertyOp getter, JSPropertyOp setter, uintN attrs)
974 {
975 uint32 i;
976 JSBool isIndex;
977
978 if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
979 return JS_TRUE;
980
981 isIndex = js_IdIsIndex(ID_TO_VALUE(id), &i);
982 if (!isIndex || attrs != JSPROP_ENUMERATE || !OBJ_IS_DENSE_ARRAY(cx, obj) || INDEX_TOO_SPARSE(obj, i)) {
983 if (!ENSURE_SLOW_ARRAY(cx, obj))
984 return JS_FALSE;
985 return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
986 }
987
988 return array_setProperty(cx, obj, id, &value);
989 }
990
991 static JSBool
992 array_getAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
993 uintN *attrsp)
994 {
995 *attrsp = id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)
996 ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
997 return JS_TRUE;
998 }
999
1000 static JSBool
1001 array_setAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
1002 uintN *attrsp)
1003 {
1004 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
1005 JSMSG_CANT_SET_ARRAY_ATTRS);
1006 return JS_FALSE;
1007 }
1008
1009 static JSBool
1010 array_deleteProperty(JSContext *cx, JSObject *obj, jsval id, jsval *rval)
1011 {
1012 uint32 i;
1013
1014 if (!OBJ_IS_DENSE_ARRAY(cx, obj))
1015 return js_DeleteProperty(cx, obj, id, rval);
1016
1017 if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) {
1018 *rval = JSVAL_FALSE;
1019 return JS_TRUE;
1020 }
1021
1022 if (js_IdIsIndex(id, &i) && i < js_DenseArrayCapacity(obj) &&
1023 obj->dslots[i] != JSVAL_HOLE) {
1024 obj->fslots[JSSLOT_ARRAY_COUNT]--;
1025 obj->dslots[i] = JSVAL_HOLE;
1026 }
1027
1028 *rval = JSVAL_TRUE;
1029 return JS_TRUE;
1030 }
1031
1032 /*
1033 * JSObjectOps.enumerate implementation.
1034 *
1035 * For a fast array, JSENUMERATE_INIT captures in the enumeration state both
1036 * the length of the array and the bitmap indicating the positions of holes in
1037 * the array. This ensures that adding or deleting array elements does not
1038 * affect the sequence of indexes JSENUMERATE_NEXT returns.
1039 *
1040 * For a common case of an array without holes, to represent the state we pack
1041 * the (nextEnumerationIndex, arrayLength) pair as a pseudo-boolean jsval.
1042 * This is possible when length <= PACKED_UINT_PAIR_BITS. For arrays with
1043 * greater length or holes we allocate the JSIndexIterState structure and
1044 * store it as an int-tagged private pointer jsval. For a slow array we
1045 * delegate the enumeration implementation to js_Enumerate in
1046 * slowarray_enumerate.
1047 *
1048 * Array mutations can turn a fast array into a slow one after the enumeration
1049 * starts. When this happens, slowarray_enumerate receives a state created
1050 * when the array was fast. To distinguish such fast state from a slow state,
1051 * which is an int-tagged pointer that js_Enumerate creates, we set not one
1052 * but two lowest bits when tagging a JSIndexIterState pointer -- see
1053 * INDEX_ITER_TAG usage below. Thus, when slowarray_enumerate receives a state
1054 * tagged with JSVAL_SPECIAL or with two lowest bits set, it knows that this
1055 * is a fast state so it calls array_enumerate to continue enumerating the
1056 * indexes present in the original fast array.
1057 */
1058
1059 #define PACKED_UINT_PAIR_BITS 14
1060 #define PACKED_UINT_PAIR_MASK JS_BITMASK(PACKED_UINT_PAIR_BITS)
1061
1062 #define UINT_PAIR_TO_SPECIAL_JSVAL(i,j) \
1063 (JS_ASSERT((uint32) (i) <= PACKED_UINT_PAIR_MASK), \
1064 JS_ASSERT((uint32) (j) <= PACKED_UINT_PAIR_MASK), \
1065 ((jsval) (i) << (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)) | \
1066 ((jsval) (j) << (JSVAL_TAGBITS)) | \
1067 (jsval) JSVAL_SPECIAL)
1068
1069 #define SPECIAL_JSVAL_TO_UINT_PAIR(v,i,j) \
1070 (JS_ASSERT(JSVAL_IS_SPECIAL(v)), \
1071 (i) = (uint32) ((v) >> (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)), \
1072 (j) = (uint32) ((v) >> JSVAL_TAGBITS) & PACKED_UINT_PAIR_MASK, \
1073 JS_ASSERT((i) <= PACKED_UINT_PAIR_MASK))
1074
1075 JS_STATIC_ASSERT(PACKED_UINT_PAIR_BITS * 2 + JSVAL_TAGBITS <= JS_BITS_PER_WORD);
1076
1077 typedef struct JSIndexIterState {
1078 uint32 index;
1079 uint32 length;
1080 JSBool hasHoles;
1081
1082 /*
1083 * Variable-length bitmap representing array's holes. It must not be
1084 * accessed when hasHoles is false.
1085 */
1086 jsbitmap holes[1];
1087 } JSIndexIterState;
1088
1089 #define INDEX_ITER_TAG 3
1090
1091 JS_STATIC_ASSERT(JSVAL_INT == 1);
1092
1093 static JSBool
1094 array_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
1095 jsval *statep, jsid *idp)
1096 {
1097 uint32 capacity, i;
1098 JSIndexIterState *ii;
1099
1100 switch (enum_op) {
1101 case JSENUMERATE_INIT:
1102 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
1103 capacity = js_DenseArrayCapacity(obj);
1104 if (idp)
1105 *idp = INT_TO_JSVAL(obj->fslots[JSSLOT_ARRAY_COUNT]);
1106 ii = NULL;
1107 for (i = 0; i != capacity; ++i) {
1108 if (obj->dslots[i] == JSVAL_HOLE) {
1109 if (!ii) {
1110 ii = (JSIndexIterState *)
1111 cx->malloc(offsetof(JSIndexIterState, holes) +
1112 JS_BITMAP_SIZE(capacity));
1113 if (!ii)
1114 return JS_FALSE;
1115 ii->hasHoles = JS_TRUE;
1116 memset(ii->holes, 0, JS_BITMAP_SIZE(capacity));
1117 }
1118 JS_SET_BIT(ii->holes, i);
1119 }
1120 }
1121 if (!ii) {
1122 /* Array has no holes. */
1123 if (capacity <= PACKED_UINT_PAIR_MASK) {
1124 *statep = UINT_PAIR_TO_SPECIAL_JSVAL(0, capacity);
1125 break;
1126 }
1127 ii = (JSIndexIterState *)
1128 cx->malloc(offsetof(JSIndexIterState, holes));
1129 if (!ii)
1130 return JS_FALSE;
1131 ii->hasHoles = JS_FALSE;
1132 }
1133 ii->index = 0;
1134 ii->length = capacity;
1135 *statep = (jsval) ii | INDEX_ITER_TAG;
1136 JS_ASSERT(*statep & JSVAL_INT);
1137 break;
1138
1139 case JSENUMERATE_NEXT:
1140 if (JSVAL_IS_SPECIAL(*statep)) {
1141 SPECIAL_JSVAL_TO_UINT_PAIR(*statep, i, capacity);
1142 if (i != capacity) {
1143 *idp = INT_TO_JSID(i);
1144 *statep = UINT_PAIR_TO_SPECIAL_JSVAL(i + 1, capacity);
1145 break;
1146 }
1147 } else {
1148 JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
1149 ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
1150 i = ii->index;
1151 if (i != ii->length) {
1152 /* Skip holes if any. */
1153 if (ii->hasHoles) {
1154 while (JS_TEST_BIT(ii->holes, i) && ++i != ii->length)
1155 continue;
1156 }
1157 if (i != ii->length) {
1158 ii->index = i + 1;
1159 return js_IndexToId(cx, i, idp);
1160 }
1161 }
1162 }
1163 /* FALL THROUGH */
1164
1165 case JSENUMERATE_DESTROY:
1166 if (!JSVAL_IS_SPECIAL(*statep)) {
1167 JS_ASSERT((*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG);
1168 ii = (JSIndexIterState *) (*statep & ~INDEX_ITER_TAG);
1169 cx->free(ii);
1170 }
1171 *statep = JSVAL_NULL;
1172 break;
1173 }
1174 return JS_TRUE;
1175 }
1176
1177 static JSBool
1178 slowarray_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
1179 jsval *statep, jsid *idp)
1180 {
1181 JSBool ok;
1182
1183 /* Are we continuing an enumeration that started when we were dense? */
1184 if (enum_op != JSENUMERATE_INIT) {
1185 if (JSVAL_IS_SPECIAL(*statep) ||
1186 (*statep & INDEX_ITER_TAG) == INDEX_ITER_TAG) {
1187 return array_enumerate(cx, obj, enum_op, statep, idp);
1188 }
1189 JS_ASSERT((*statep & INDEX_ITER_TAG) == JSVAL_INT);
1190 }
1191 ok = js_Enumerate(cx, obj, enum_op, statep, idp);
1192 JS_ASSERT(*statep == JSVAL_NULL || (*statep & INDEX_ITER_TAG) == JSVAL_INT);
1193 return ok;
1194 }
1195
1196 static void
1197 array_finalize(JSContext *cx, JSObject *obj)
1198 {
1199 if (obj->dslots)
1200 cx->free(obj->dslots - 1);
1201 obj->dslots = NULL;
1202 }
1203
1204 static void
1205 array_trace(JSTracer *trc, JSObject *obj)
1206 {
1207 uint32 capacity;
1208 size_t i;
1209 jsval v;
1210
1211 JS_ASSERT(js_IsDenseArray(obj));
1212 obj->traceProtoAndParent(trc);
1213
1214 capacity = js_DenseArrayCapacity(obj);
1215 for (i = 0; i < capacity; i++) {
1216 v = obj->dslots[i];
1217 if (JSVAL_IS_TRACEABLE(v)) {
1218 JS_SET_TRACING_INDEX(trc, "array_dslots", i);
1219 JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
1220 }
1221 }
1222 }
1223
1224 extern JSObjectOps js_ArrayObjectOps;
1225
1226 static const JSObjectMap SharedArrayMap(&js_ArrayObjectOps, JSObjectMap::SHAPELESS);
1227
1228 JSObjectOps js_ArrayObjectOps = {
1229 &SharedArrayMap,
1230 array_lookupProperty, array_defineProperty,
1231 array_getProperty, array_setProperty,
1232 array_getAttributes, array_setAttributes,
1233 array_deleteProperty, js_DefaultValue,
1234 array_enumerate, js_CheckAccess,
1235 NULL, array_dropProperty,
1236 NULL, NULL,
1237 js_HasInstance, array_trace,
1238 NULL
1239 };
1240
1241 static JSObjectOps *
1242 array_getObjectOps(JSContext *cx, JSClass *clasp)
1243 {
1244 return &js_ArrayObjectOps;
1245 }
1246
1247 JSClass js_ArrayClass = {
1248 "Array",
1249 JSCLASS_HAS_RESERVED_SLOTS(2) |
1250 JSCLASS_HAS_CACHED_PROTO(JSProto_Array) |
1251 JSCLASS_NEW_ENUMERATE,
1252 JS_PropertyStub, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
1253 JS_EnumerateStub, JS_ResolveStub, js_TryValueOf, array_finalize,
1254 array_getObjectOps, NULL, NULL, NULL,
1255 NULL, NULL, NULL, NULL
1256 };
1257
1258 JSClass js_SlowArrayClass = {
1259 "Array",
1260 JSCLASS_HAS_PRIVATE |
1261 JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
1262 slowarray_addProperty, JS_PropertyStub, JS_PropertyStub, JS_PropertyStub,
1263 JS_EnumerateStub, JS_ResolveStub, js_TryValueOf, NULL,
1264 slowarray_getObjectOps, NULL, NULL, NULL,
1265 NULL, NULL, NULL, NULL
1266 };
1267
1268 /*
1269 * Convert an array object from fast-and-dense to slow-and-flexible.
1270 */
1271 JSBool
1272 js_MakeArraySlow(JSContext *cx, JSObject *obj)
1273 {
1274 JS_ASSERT(obj->getClass() == &js_ArrayClass);
1275
1276 /*
1277 * Create a native scope. All slow arrays other than Array.prototype get
1278 * the same initial shape.
1279 */
1280 uint32 emptyShape;
1281 JSObject *arrayProto = obj->getProto();
1282 if (arrayProto->getClass() == &js_ObjectClass) {
1283 /* obj is Array.prototype. */
1284 emptyShape = js_GenerateShape(cx, false);
1285 } else {
1286 /* arrayProto is Array.prototype. */
1287 JS_ASSERT(arrayProto->getClass() == &js_SlowArrayClass);
1288 emptyShape = OBJ_SCOPE(arrayProto)->emptyScope->shape;
1289 }
1290 JSScope *scope = JSScope::create(cx, &js_SlowArrayObjectOps, &js_SlowArrayClass, obj,
1291 emptyShape);
1292 if (!scope)
1293 return JS_FALSE;
1294
1295 uint32 capacity = js_DenseArrayCapacity(obj);
1296 if (capacity) {
1297 scope->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
1298 obj->dslots[-1] = JS_INITIAL_NSLOTS + capacity;
1299 } else {
1300 scope->freeslot = STOBJ_NSLOTS(obj);
1301 }
1302
1303 /* Create new properties pointing to existing values in dslots */
1304 for (uint32 i = 0; i < capacity; i++) {
1305 jsid id;
1306 JSScopeProperty *sprop;
1307
1308 if (!JS_ValueToId(cx, INT_TO_JSVAL(i), &id))
1309 goto out_bad;
1310
1311 if (obj->dslots[i] == JSVAL_HOLE) {
1312 obj->dslots[i] = JSVAL_VOID;
1313 continue;
1314 }
1315
1316 sprop = scope->add(cx, id, NULL, NULL, i + JS_INITIAL_NSLOTS,
1317 JSPROP_ENUMERATE, 0, 0);
1318 if (!sprop)
1319 goto out_bad;
1320 }
1321
1322 /*
1323 * Render our formerly-reserved count property GC-safe. If length fits in
1324 * a jsval, set our slow/sparse COUNT to the current length as a jsval, so
1325 * we can tell when only named properties have been added to a dense array
1326 * to make it slow-but-not-sparse.
1327 *
1328 * We do not need to make the length slot GC-safe as this slot is private
1329 * where the implementation can store an arbitrary value.
1330 */
1331 {
1332 JS_STATIC_ASSERT(JSSLOT_ARRAY_LENGTH == JSSLOT_PRIVATE);
1333 JS_ASSERT(js_SlowArrayClass.flags & JSCLASS_HAS_PRIVATE);
1334 uint32 length = uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]);
1335 obj->fslots[JSSLOT_ARRAY_COUNT] = INT_FITS_IN_JSVAL(length)
1336 ? INT_TO_JSVAL(length)
1337 : JSVAL_VOID;
1338 }
1339
1340 /* Make sure we preserve any flags borrowing bits in classword. */
1341 obj->classword ^= (jsuword) &js_ArrayClass;
1342 obj->classword |= (jsuword) &js_SlowArrayClass;
1343
1344 obj->map = scope;
1345 return JS_TRUE;
1346
1347 out_bad:
1348 JSScope::destroy(cx, scope);
1349 return JS_FALSE;
1350 }
1351
1352 /* Transfer ownership of buffer to returned string. */
1353 static inline JSBool
1354 BufferToString(JSContext *cx, JSCharBuffer &cb, jsval *rval)
1355 {
1356 JSString *str = js_NewStringFromCharBuffer(cx, cb);
1357 if (!str)
1358 return false;
1359 *rval = STRING_TO_JSVAL(str);
1360 return true;
1361 }
1362
1363 #if JS_HAS_TOSOURCE
1364 static JSBool
1365 array_toSource(JSContext *cx, uintN argc, jsval *vp)
1366 {
1367 JS_CHECK_RECURSION(cx, return false);
1368
1369 JSObject *obj = JS_THIS_OBJECT(cx, vp);
1370 if (!obj ||
1371 (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1372 !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1373 return false;
1374 }
1375
1376 /* Find joins or cycles in the reachable object graph. */
1377 jschar *sharpchars;
1378 JSHashEntry *he = js_EnterSharpObject(cx, obj, NULL, &sharpchars);
1379 if (!he)
1380 return false;
1381 bool initiallySharp = IS_SHARP(he);
1382
1383 /* After this point, all paths exit through the 'out' label. */
1384 MUST_FLOW_THROUGH("out");
1385 bool ok = false;
1386
1387 /*
1388 * This object will take responsibility for the jschar buffer until the
1389 * buffer is transferred to the returned JSString.
1390 */
1391 JSCharBuffer cb(cx);
1392
1393 /* Cycles/joins are indicated by sharp objects. */
1394 #if JS_HAS_SHARP_VARS
1395 if (IS_SHARP(he)) {
1396 JS_ASSERT(sharpchars != 0);
1397 cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1398 goto make_string;
1399 } else if (sharpchars) {
1400 MAKE_SHARP(he);
1401 cb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1402 }
1403 #else
1404 if (IS_SHARP(he)) {
1405 if (!js_AppendLiteral(cb, "[]"))
1406 goto out;
1407 cx->free(sharpchars);
1408 goto make_string;
1409 }
1410 #endif
1411
1412 if (!cb.append('['))
1413 goto out;
1414
1415 jsuint length;
1416 if (!js_GetLengthProperty(cx, obj, &length))
1417 goto out;
1418
1419 for (jsuint index = 0; index < length; index++) {
1420 /* Use vp to locally root each element value. */
1421 JSBool hole;
1422 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1423 !GetArrayElement(cx, obj, index, &hole, vp)) {
1424 goto out;
1425 }
1426
1427 /* Get element's character string. */
1428 JSString *str;
1429 if (hole) {
1430 str = cx->runtime->emptyString;
1431 } else {
1432 str = js_ValueToSource(cx, *vp);
1433 if (!str)
1434 goto out;
1435 }
1436 *vp = STRING_TO_JSVAL(str);
1437 const jschar *chars;
1438 size_t charlen;
1439 str->getCharsAndLength(chars, charlen);
1440
1441 /* Append element to buffer. */
1442 if (!cb.append(chars, charlen))
1443 goto out;
1444 if (index + 1 != length) {
1445 if (!js_AppendLiteral(cb, ", "))
1446 goto out;
1447 } else if (hole) {
1448 if (!cb.append(','))
1449 goto out;
1450 }
1451 }
1452
1453 /* Finalize the buffer. */
1454 if (!cb.append(']'))
1455 goto out;
1456
1457 make_string:
1458 if (!BufferToString(cx, cb, vp))
1459 goto out;
1460
1461 ok = true;
1462
1463 out:
1464 if (!initiallySharp)
1465 js_LeaveSharpObject(cx, NULL);
1466 return ok;
1467 }
1468 #endif
1469
1470 static JSHashNumber
1471 js_hash_array(const void *key)
1472 {
1473 return (JSHashNumber)JS_PTR_TO_UINT32(key) >> JSVAL_TAGBITS;
1474 }
1475
1476 bool
1477 js_InitContextBusyArrayTable(JSContext *cx)
1478 {
1479 cx->busyArrayTable = JS_NewHashTable(4, js_hash_array, JS_CompareValues,
1480 JS_CompareValues, NULL, NULL);
1481 return cx->busyArrayTable != NULL;
1482 }
1483
1484 static JSBool
1485 array_toString_sub(JSContext *cx, JSObject *obj, JSBool locale,
1486 JSString *sepstr, jsval *rval)
1487 {
1488 JS_CHECK_RECURSION(cx, return false);
1489
1490 /*
1491 * This hash table is shared between toString invocations and must be empty
1492 * after the root invocation completes.
1493 */
1494 JSHashTable *table = cx->busyArrayTable;
1495
1496 /*
1497 * Use HashTable entry as the cycle indicator. On first visit, create the
1498 * entry, and, when leaving, remove the entry.
1499 */
1500 JSHashNumber hash = js_hash_array(obj);
1501 JSHashEntry **hep = JS_HashTableRawLookup(table, hash, obj);
1502 JSHashEntry *he = *hep;
1503 if (!he) {
1504 /* Not in hash table, so not a cycle. */
1505 he = JS_HashTableRawAdd(table, hep, hash, obj, NULL);
1506 if (!he) {
1507 JS_ReportOutOfMemory(cx);
1508 return false;
1509 }
1510 } else {
1511 /* Cycle, so return empty string. */
1512 *rval = ATOM_KEY(cx->runtime->atomState.emptyAtom);
1513 return true;
1514 }
1515
1516 JSAutoTempValueRooter tvr(cx, obj);
1517
1518 /* After this point, all paths exit through the 'out' label. */
1519 MUST_FLOW_THROUGH("out");
1520 bool ok = false;
1521
1522 /* Get characters to use for the separator. */
1523 static const jschar comma = ',';
1524 const jschar *sep;
1525 size_t seplen;
1526 if (sepstr) {
1527 sepstr->getCharsAndLength(sep, seplen);
1528 } else {
1529 sep = &comma;
1530 seplen = 1;
1531 }
1532
1533 /*
1534 * This object will take responsibility for the jschar buffer until the
1535 * buffer is transferred to the returned JSString.
1536 */
1537 JSCharBuffer cb(cx);
1538
1539 jsuint length;
1540 if (!js_GetLengthProperty(cx, obj, &length))
1541 goto out;
1542
1543 for (jsuint index = 0; index < length; index++) {
1544 /* Use rval to locally root each element value. */
1545 JSBool hole;
1546 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1547 !GetArrayElement(cx, obj, index, &hole, rval)) {
1548 goto out;
1549 }
1550
1551 /* Get element's character string. */
1552 if (!(hole || JSVAL_IS_VOID(*rval) || JSVAL_IS_NULL(*rval))) {
1553 if (locale) {
1554 /* Work on obj.toLocalString() instead. */
1555 JSObject *robj;
1556
1557 if (!js_ValueToObject(cx, *rval, &robj))
1558 goto out;
1559 *rval = OBJECT_TO_JSVAL(robj);
1560 JSAtom *atom = cx->runtime->atomState.toLocaleStringAtom;
1561 if (!js_TryMethod(cx, robj, atom, 0, NULL, rval))
1562 goto out;
1563 }
1564
1565 if (!js_ValueToCharBuffer(cx, *rval, cb))
1566 goto out;
1567 }
1568
1569 /* Append the separator. */
1570 if (index + 1 != length) {
1571 if (!cb.append(sep, seplen))
1572 goto out;
1573 }
1574 }
1575
1576 /* Finalize the buffer. */
1577 if (!BufferToString(cx, cb, rval))
1578 goto out;
1579
1580 ok = true;
1581
1582 out:
1583 /*
1584 * It is possible that 'hep' may have been invalidated by subsequent
1585 * RawAdd/Remove. Hence, 'RawRemove' must not be used.
1586 */
1587 JS_HashTableRemove(table, obj);
1588 return ok;
1589 }
1590
1591 static JSBool
1592 array_toString(JSContext *cx, uintN argc, jsval *vp)
1593 {
1594 JSObject *obj;
1595
1596 obj = JS_THIS_OBJECT(cx, vp);
1597 if (!obj ||
1598 (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1599 !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1600 return JS_FALSE;
1601 }
1602
1603 return array_toString_sub(cx, obj, JS_FALSE, NULL, vp);
1604 }
1605
1606 static JSBool
1607 array_toLocaleString(JSContext *cx, uintN argc, jsval *vp)
1608 {
1609 JSObject *obj;
1610
1611 obj = JS_THIS_OBJECT(cx, vp);
1612 if (!obj ||
1613 (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
1614 !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))) {
1615 return JS_FALSE;
1616 }
1617
1618 /*
1619 * Passing comma here as the separator. Need a way to get a
1620 * locale-specific version.
1621 */
1622 return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
1623 }
1624
1625 enum TargetElementsType {
1626 TargetElementsAllHoles,
1627 TargetElementsMayContainValues
1628 };
1629
1630 enum SourceVectorType {
1631 SourceVectorAllValues,
1632 SourceVectorMayContainHoles
1633 };
1634
1635 static JSBool
1636 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, jsval *vector,
1637 TargetElementsType targetType, SourceVectorType vectorType)
1638 {
1639 JS_ASSERT(count < MAXINDEX);
1640
1641 /*
1642 * Optimize for dense arrays so long as adding the given set of elements
1643 * wouldn't otherwise make the array slow.
1644 */
1645 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
1646 start <= MAXINDEX - count && !INDEX_TOO_BIG(start + count)) {
1647
1648 #ifdef DEBUG_jwalden
1649 {
1650 /* Verify that overwriteType and writeType were accurate. */
1651 JSAutoTempIdRooter idr(cx, JSVAL_ZERO);
1652 for (jsuint i = 0; i < count; i++) {
1653 JS_ASSERT_IF(vectorType == SourceVectorAllValues, vector[i] != JSVAL_HOLE);
1654
1655 jsdouble index = jsdouble(start) + i;
1656 if (targetType == TargetElementsAllHoles && index < jsuint(-1)) {
1657 JS_ASSERT(ReallyBigIndexToId(cx, index, idr.addr()));
1658 JSObject* obj2;
1659 JSProperty* prop;
1660 JS_ASSERT(obj->lookupProperty(cx, idr.id(), &obj2, &prop));
1661 JS_ASSERT(!prop);
1662 }
1663 }
1664 }
1665 #endif
1666
1667 jsuint newlen = start + count;
1668 JS_ASSERT(jsdouble(start) + count == jsdouble(newlen));
1669 if (!EnsureCapacity(cx, obj, newlen))
1670 return JS_FALSE;
1671
1672 if (newlen > uint32(obj->fslots[JSSLOT_ARRAY_LENGTH]))
1673 obj->fslots[JSSLOT_ARRAY_LENGTH] = newlen;
1674
1675 JS_ASSERT(count < size_t(-1) / sizeof(jsval));
1676 if (targetType == TargetElementsMayContainValues) {
1677 jsuint valueCount = 0;
1678 for (jsuint i = 0; i < count; i++) {
1679 if (obj->dslots[start + i] != JSVAL_HOLE)
1680 valueCount++;
1681 }
1682 JS_ASSERT(uint32(obj->fslots[JSSLOT_ARRAY_COUNT]) >= valueCount);
1683 obj->fslots[JSSLOT_ARRAY_COUNT] -= valueCount;
1684 }
1685 memcpy(obj->dslots + start, vector, sizeof(jsval) * count);
1686 if (vectorType == SourceVectorAllValues) {
1687 obj->fslots[JSSLOT_ARRAY_COUNT] += count;
1688 } else {
1689 jsuint valueCount = 0;
1690 for (jsuint i = 0; i < count; i++) {
1691 if (obj->dslots[start + i] != JSVAL_HOLE)
1692 valueCount++;
1693 }
1694 obj->fslots[JSSLOT_ARRAY_COUNT] += valueCount;
1695 }
1696 JS_ASSERT_IF(count != 0, obj->dslots[newlen - 1] != JSVAL_HOLE);
1697 return JS_TRUE;
1698 }
1699
1700 jsval* end = vector + count;
1701 while (vector != end && start < MAXINDEX) {
1702 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1703 !SetArrayElement(cx, obj, start++, *vector++)) {
1704 return JS_FALSE;
1705 }
1706 }
1707
1708 if (vector == end)
1709 return JS_TRUE;
1710
1711 /* Finish out any remaining elements past the max array index. */
1712 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !ENSURE_SLOW_ARRAY(cx, obj))
1713 return JS_FALSE;
1714
1715 JS_ASSERT(start == MAXINDEX);
1716 jsval tmp[2] = {JSVAL_NULL, JSVAL_NULL};
1717 jsdouble* dp = js_NewWeaklyRootedDouble(cx, MAXINDEX);
1718 if (!dp)
1719 return JS_FALSE;
1720 tmp[0] = DOUBLE_TO_JSVAL(dp);
1721 JSAutoTempValueRooter tvr(cx, JS_ARRAY_LENGTH(tmp), tmp);
1722 JSAutoTempIdRooter idr(cx);
1723 do {
1724 tmp[1] = *vector++;
1725 if (!js_ValueToStringId(cx, tmp[0], idr.addr()) ||
1726 !obj->setProperty(cx, idr.id(), &tmp[1])) {
1727 return JS_FALSE;
1728 }
1729 *dp += 1;
1730 } while (vector != end);
1731
1732 return JS_TRUE;
1733 }
1734
1735 static JSBool
1736 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector,
1737 JSBool holey = JS_FALSE)
1738 {
1739 JS_ASSERT(OBJ_IS_ARRAY(cx, obj));
1740
1741 obj->fslots[JSSLOT_ARRAY_LENGTH] = length;
1742
1743 if (vector) {
1744 if (!EnsureCapacity(cx, obj, length))
1745 return JS_FALSE;
1746
1747 jsuint count = length;
1748 if (!holey) {
1749 memcpy(obj->dslots, vector, length * sizeof (jsval));
1750 } else {
1751 for (jsuint i = 0; i < length; i++) {
1752 if (vector[i] == JSVAL_HOLE)
1753 --count;
1754 obj->dslots[i] = vector[i];
1755 }
1756 }
1757 obj->fslots[JSSLOT_ARRAY_COUNT] = count;
1758 } else {
1759 obj->fslots[JSSLOT_ARRAY_COUNT] = 0;
1760 }
1761 return JS_TRUE;
1762 }
1763
1764 #ifdef JS_TRACER
1765 static JSString* FASTCALL
1766 Array_p_join(JSContext* cx, JSObject* obj, JSString *str)
1767 {
1768 JSAutoTempValueRooter tvr(cx);
1769 if (!array_toString_sub(cx, obj, JS_FALSE, str, tvr.addr())) {
1770 js_SetBuiltinError(cx);
1771 return NULL;
1772 }
1773 return JSVAL_TO_STRING(tvr.value());
1774 }
1775
1776 static JSString* FASTCALL
1777 Array_p_toString(JSContext* cx, JSObject* obj)
1778 {
1779 JSAutoTempValueRooter tvr(cx);
1780 if (!array_toString_sub(cx, obj, JS_FALSE, NULL, tvr.addr())) {
1781 js_SetBuiltinError(cx);
1782 return NULL;
1783 }
1784 return JSVAL_TO_STRING(tvr.value());
1785 }
1786 #endif
1787
1788 /*
1789 * Perl-inspired join, reverse, and sort.
1790 */
1791 static JSBool
1792 array_join(JSContext *cx, uintN argc, jsval *vp)
1793 {
1794 JSString *str;
1795 JSObject *obj;
1796
1797 if (argc == 0 || JSVAL_IS_VOID(vp[2])) {
1798 str = NULL;
1799 } else {
1800 str = js_ValueToString(cx, vp[2]);
1801 if (!str)
1802 return JS_FALSE;
1803 vp[2] = STRING_TO_JSVAL(str);
1804 }
1805 obj = JS_THIS_OBJECT(cx, vp);
1806 return obj && array_toString_sub(cx, obj, JS_FALSE, str, vp);
1807 }
1808
1809 static JSBool
1810 array_reverse(JSContext *cx, uintN argc, jsval *vp)
1811 {
1812 jsuint len;
1813 JSObject *obj = JS_THIS_OBJECT(cx, vp);
1814 if (!obj || !js_GetLengthProperty(cx, obj, &len))
1815 return JS_FALSE;
1816 *vp = OBJECT_TO_JSVAL(obj);
1817
1818 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj)) {
1819 /* An empty array or an array with no elements is already reversed. */
1820 if (len == 0 || !obj->dslots)
1821 return JS_TRUE;
1822
1823 /*
1824 * It's actually surprisingly complicated to reverse an array due to the
1825 * orthogonality of array length and array capacity while handling
1826 * leading and trailing holes correctly. Reversing seems less likely to
1827 * be a common operation than other array mass-mutation methods, so for
1828 * now just take a probably-small memory hit (in the absence of too many
1829 * holes in the array at its start) and ensure that the capacity is
1830 * sufficient to hold all the elements in the array if it were full.
1831 */
1832 if (!EnsureCapacity(cx, obj, len))
1833 return JS_FALSE;
1834
1835 jsval* lo = &obj->dslots[0];
1836 jsval* hi = &obj->dslots[len - 1];
1837 for (; lo < hi; lo++, hi--) {
1838 jsval tmp = *lo;
1839 *lo = *hi;
1840 *hi = tmp;
1841 }
1842
1843 /*
1844 * Per ECMA-262, don't update the length of the array, even if the new
1845 * array has trailing holes (and thus the original array began with
1846 * holes).
1847 */
1848 return JS_TRUE;
1849 }
1850
1851 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
1852 for (jsuint i = 0, half = len / 2; i < half; i++) {
1853 JSBool hole, hole2;
1854 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1855 !GetArrayElement(cx, obj, i, &hole, tvr.addr()) ||
1856 !GetArrayElement(cx, obj, len - i - 1, &hole2, vp) ||
1857 !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, tvr.value()) ||
1858 !SetOrDeleteArrayElement(cx, obj, i, hole2, *vp)) {
1859 return false;
1860 }
1861 }
1862 *vp = OBJECT_TO_JSVAL(obj);
1863 return true;
1864 }
1865
1866 typedef struct MSortArgs {
1867 size_t elsize;
1868 JSComparator cmp;
1869 void *arg;
1870 JSBool fastcopy;
1871 } MSortArgs;
1872
1873 /* Helper function for js_MergeSort. */
1874 static JSBool
1875 MergeArrays(MSortArgs *msa, void *src, void *dest, size_t run1, size_t run2)
1876 {
1877 void *arg, *a, *b, *c;
1878 size_t elsize, runtotal;
1879 int cmp_result;
1880 JSComparator cmp;
1881 JSBool fastcopy;
1882
1883 runtotal = run1 + run2;
1884
1885 elsize = msa->elsize;
1886 cmp = msa->cmp;
1887 arg = msa->arg;
1888 fastcopy = msa->fastcopy;
1889
1890 #define CALL_CMP(a, b) \
1891 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1892
1893 /* Copy runs already in sorted order. */
1894 b = (char *)src + run1 * elsize;
1895 a = (char *)b - elsize;
1896 CALL_CMP(a, b);
1897 if (cmp_result <= 0) {
1898 memcpy(dest, src, runtotal * elsize);
1899 return JS_TRUE;
1900 }
1901
1902 #define COPY_ONE(p,q,n) \
1903 (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1904
1905 a = src;
1906 c = dest;
1907 for (; runtotal != 0; runtotal--) {
1908 JSBool from_a = run2 == 0;
1909 if (!from_a && run1 != 0) {
1910 CALL_CMP(a,b);
1911 from_a = cmp_result <= 0;
1912 }
1913
1914 if (from_a) {
1915 COPY_ONE(c, a, elsize);
1916 run1--;
1917 a = (char *)a + elsize;
1918 } else {
1919 COPY_ONE(c, b, elsize);
1920 run2--;
1921 b = (char *)b + elsize;
1922 }
1923 c = (char *)c + elsize;
1924 }
1925 #undef COPY_ONE
1926 #undef CALL_CMP
1927
1928 return JS_TRUE;
1929 }
1930
1931 /*
1932 * This sort is stable, i.e. sequence of equal elements is preserved.
1933 * See also bug #224128.
1934 */
1935 JSBool
1936 js_MergeSort(void *src, size_t nel, size_t elsize,
1937 JSComparator cmp, void *arg, void *tmp)
1938 {
1939 void *swap, *vec1, *vec2;
1940 MSortArgs msa;
1941 size_t i, j, lo, hi, run;
1942 JSBool fastcopy;
1943 int cmp_result;
1944
1945 /* Avoid memcpy overhead for word-sized and word-aligned elements. */
1946 fastcopy = (elsize == sizeof(jsval) &&
1947 (((jsuword) src | (jsuword) tmp) & JSVAL_ALIGN) == 0);
1948 #define COPY_ONE(p,q,n) \
1949 (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1950 #define CALL_CMP(a, b) \
1951 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1952 #define INS_SORT_INT 4
1953
1954 /*
1955 * Apply insertion sort to small chunks to reduce the number of merge
1956 * passes needed.
1957 */
1958 for (lo = 0; lo < nel; lo += INS_SORT_INT) {
1959 hi = lo + INS_SORT_INT;
1960 if (hi >= nel)
1961 hi = nel;
1962 for (i = lo + 1; i < hi; i++) {
1963 vec1 = (char *)src + i * elsize;
1964 vec2 = (char *)vec1 - elsize;
1965 for (j = i; j > lo; j--) {
1966 CALL_CMP(vec2, vec1);
1967 /* "<=" instead of "<" insures the sort is stable */
1968 if (cmp_result <= 0) {
1969 break;
1970 }
1971
1972 /* Swap elements, using "tmp" as tmp storage */
1973 COPY_ONE(tmp, vec2, elsize);
1974 COPY_ONE(vec2, vec1, elsize);
1975 COPY_ONE(vec1, tmp, elsize);
1976 vec1 = vec2;
1977 vec2 = (char *)vec1 - elsize;
1978 }
1979 }
1980 }
1981 #undef CALL_CMP
1982 #undef COPY_ONE
1983
1984 msa.elsize = elsize;
1985 msa.cmp = cmp;
1986 msa.arg = arg;
1987 msa.fastcopy = fastcopy;
1988
1989 vec1 = src;
1990 vec2 = tmp;
1991 for (run = INS_SORT_INT; run < nel; run *= 2) {
1992 for (lo = 0; lo < nel; lo += 2 * run) {
1993 hi = lo + run;
1994 if (hi >= nel) {
1995 memcpy((char *)vec2 + lo * elsize, (char *)vec1 + lo * elsize,
1996 (nel - lo) * elsize);
1997 break;
1998 }
1999 if (!MergeArrays(&msa, (char *)vec1 + lo * elsize,
2000 (char *)vec2 + lo * elsize, run,
2001 hi + run > nel ? nel - hi : run)) {
2002 return JS_FALSE;
2003 }
2004 }
2005 swap = vec1;
2006 vec1 = vec2;
2007 vec2 = swap;
2008 }
2009 if (src != vec1)
2010 memcpy(src, tmp, nel * elsize);
2011
2012 return JS_TRUE;
2013 }
2014
2015 typedef struct CompareArgs {
2016 JSContext *context;
2017 jsval fval;
2018 jsval *elemroot; /* stack needed for js_Invoke */
2019 } CompareArgs;
2020
2021 static JS_REQUIRES_STACK JSBool
2022 sort_compare(void *arg, const void *a, const void *b, int *result)
2023 {
2024 jsval av = *(const jsval *)a, bv = *(const jsval *)b;
2025 CompareArgs *ca = (CompareArgs *) arg;
2026 JSContext *cx = ca->context;
2027 jsval *invokevp, *sp;
2028 jsdouble cmp;
2029
2030 /**
2031 * array_sort deals with holes and undefs on its own and they should not
2032 * come here.
2033 */
2034 JS_ASSERT(!JSVAL_IS_VOID(av));
2035 JS_ASSERT(!JSVAL_IS_VOID(bv));
2036
2037 if (!JS_CHECK_OPERATION_LIMIT(cx))
2038 return JS_FALSE;
2039
2040 invokevp = ca->elemroot;
2041 sp = invokevp;
2042 *sp++ = ca->fval;
2043 *sp++ = JSVAL_NULL;
2044 *sp++ = av;
2045 *sp++ = bv;
2046
2047 if (!js_Invoke(cx, 2, invokevp, 0))
2048 return JS_FALSE;
2049
2050 cmp = js_ValueToNumber(cx, invokevp);
2051 if (JSVAL_IS_NULL(*invokevp))
2052 return JS_FALSE;
2053
2054 /* Clamp cmp to -1, 0, 1. */
2055 *result = 0;
2056 if (!JSDOUBLE_IS_NaN(cmp) && cmp != 0)
2057 *result = cmp > 0 ? 1 : -1;
2058
2059 /*
2060 * XXX else report some kind of error here? ECMA talks about 'consistent
2061 * compare functions' that don't return NaN, but is silent about what the
2062 * result should be. So we currently ignore it.
2063 */
2064
2065 return JS_TRUE;
2066 }
2067
2068 typedef JSBool (JS_REQUIRES_STACK *JSRedComparator)(void*, const void*,
2069 const void*, int *);
2070
2071 static inline JS_IGNORE_STACK JSComparator
2072 comparator_stack_cast(JSRedComparator func)
2073 {
2074 return func;
2075 }
2076
2077 static int
2078 sort_compare_strings(void *arg, const void *a, const void *b, int *result)
2079 {
2080 jsval av = *(const jsval *)a, bv = *(const jsval *)b;
2081
2082 JS_ASSERT(JSVAL_IS_STRING(av));
2083 JS_ASSERT(JSVAL_IS_STRING(bv));
2084 if (!JS_CHECK_OPERATION_LIMIT((JSContext *)arg))
2085 return JS_FALSE;
2086
2087 *result = (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
2088 return JS_TRUE;
2089 }
2090
2091 /*
2092 * The array_sort function below assumes JSVAL_NULL is zero in order to
2093 * perform initialization using memset. Other parts of SpiderMonkey likewise
2094 * "know" that JSVAL_NULL is zero; this static assertion covers all cases.
2095 */
2096 JS_STATIC_ASSERT(JSVAL_NULL == 0);
2097
2098 static JSBool
2099 array_sort(JSContext *cx, uintN argc, jsval *vp)
2100 {
2101 jsval *argv, fval, *vec, *mergesort_tmp, v;
2102 JSObject *obj;
2103 CompareArgs ca;
2104 jsuint len, newlen, i, undefs;
2105 JSTempValueRooter tvr;
2106 JSBool hole;
2107 JSBool ok;
2108 size_t elemsize;
2109 JSString *str;
2110
2111 /*
2112 * Optimize the default compare function case if all of obj's elements
2113 * have values of type string.
2114 */
2115 JSBool all_strings;
2116
2117 argv = JS_ARGV(cx, vp);
2118 if (argc > 0) {
2119 if (JSVAL_IS_PRIMITIVE(argv[0])) {
2120 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2121 JSMSG_BAD_SORT_ARG);
2122 return JS_FALSE;
2123 }
2124 fval = argv[0]; /* non-default compare function */
2125 } else {
2126 fval = JSVAL_NULL;
2127 }
2128
2129 obj = JS_THIS_OBJECT(cx, vp);
2130 if (!obj || !js_GetLengthProperty(cx, obj, &len))
2131 return JS_FALSE;
2132 if (len == 0) {
2133 *vp = OBJECT_TO_JSVAL(obj);
2134 return JS_TRUE;
2135 }
2136
2137 /*
2138 * We need a temporary array of 2 * len jsvals to hold the array elements
2139 * and the scratch space for merge sort. Check that its size does not
2140 * overflow size_t, which would allow for indexing beyond the end of the
2141 * malloc'd vector.
2142 */
2143 #if JS_BITS_PER_WORD == 32
2144 if ((size_t)len > ~(size_t)0 / (2 * sizeof(jsval))) {
2145 js_ReportAllocationOverflow(cx);
2146 return JS_FALSE;
2147 }
2148 #endif
2149 vec = (jsval *) cx->malloc(2 * (size_t) len * sizeof(jsval));
2150 if (!vec)
2151 return JS_FALSE;
2152
2153 /*
2154 * Initialize vec as a root. We will clear elements of vec one by
2155 * one while increasing tvr.count when we know that the property at
2156 * the corresponding index exists and its value must be rooted.
2157 *
2158 * In this way when sorting a huge mostly sparse array we will not
2159 * access the tail of vec corresponding to properties that do not
2160 * exist, allowing OS to avoiding committing RAM. See bug 330812.
2161 *
2162 * After this point control must flow through label out: to exit.
2163 */
2164 JS_PUSH_TEMP_ROOT(cx, 0, vec, &tvr);
2165
2166 /*
2167 * By ECMA 262, 15.4.4.11, a property that does not exist (which we
2168 * call a "hole") is always greater than an existing property with
2169 * value undefined and that is always greater than any other property.
2170 * Thus to sort holes and undefs we simply count them, sort the rest
2171 * of elements, append undefs after them and then make holes after
2172 * undefs.
2173 */
2174 undefs = 0;
2175 newlen = 0;
2176 all_strings = JS_TRUE;
2177 for (i = 0; i < len; i++) {
2178 ok = JS_CHECK_OPERATION_LIMIT(cx);
2179 if (!ok)
2180 goto out;
2181
2182 /* Clear vec[newlen] before including it in the rooted set. */
2183 vec[newlen] = JSVAL_NULL;
2184 tvr.count = newlen + 1;
2185 ok = GetArrayElement(cx, obj, i, &hole, &vec[newlen]);
2186 if (!ok)
2187 goto out;
2188
2189 if (hole)
2190 continue;
2191
2192 if (JSVAL_IS_VOID(vec[newlen])) {
2193 ++undefs;
2194 continue;
2195 }
2196
2197 /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
2198 all_strings &= JSVAL_IS_STRING(vec[newlen]);
2199
2200 ++newlen;
2201 }
2202
2203 if (newlen == 0) {
2204 /* The array has only holes and undefs. */
2205 ok = JS_TRUE;
2206 goto out;
2207 }
2208
2209 /*
2210 * The first newlen elements of vec are copied from the array object
2211 * (above). The remaining newlen positions are used as GC-rooted scratch
2212 * space for mergesort. We must clear the space before including it to
2213 * the root set covered by tvr.count. We assume JSVAL_NULL==0 to optimize
2214 * initialization using memset.
2215 */
2216 mergesort_tmp = vec + newlen;
2217 memset(mergesort_tmp, 0, newlen * sizeof(jsval));
2218 tvr.count = newlen * 2;
2219
2220 /* Here len == 2 * (newlen + undefs + number_of_holes). */
2221 if (fval == JSVAL_NULL) {
2222 /*
2223 * Sort using the default comparator converting all elements to
2224 * strings.
2225 */
2226 if (all_strings) {
2227 elemsize = sizeof(jsval);
2228 } else {
2229 /*
2230 * To avoid string conversion on each compare we do it only once
2231 * prior to sorting. But we also need the space for the original
2232 * values to recover the sorting result. To reuse
2233 * sort_compare_strings we move the original values to the odd
2234 * indexes in vec, put the string conversion results in the even
2235 * indexes and pass 2 * sizeof(jsval) as an element size to the
2236 * sorting function. In this way sort_compare_strings will only
2237 * see the string values when it casts the compare arguments as
2238 * pointers to jsval.
2239 *
2240 * This requires doubling the temporary storage including the
2241 * scratch space for the merge sort. Since vec already contains
2242 * the rooted scratch space for newlen elements at the tail, we
2243 * can use it to rearrange and convert to strings first and try
2244 * realloc only when we know that we successfully converted all
2245 * the elements.
2246 */
2247 #if JS_BITS_PER_WORD == 32
2248 if ((size_t)newlen > ~(size_t)0 / (4 * sizeof(jsval))) {
2249 js_ReportAllocationOverflow(cx);
2250 ok = JS_FALSE;
2251 goto out;
2252 }
2253 #endif
2254
2255 /*
2256 * Rearrange and string-convert the elements of the vector from
2257 * the tail here and, after sorting, move the results back
2258 * starting from the start to prevent overwrite the existing
2259 * elements.
2260 */
2261 i = newlen;
2262 do {
2263 --i;
2264 ok = JS_CHECK_OPERATION_LIMIT(cx);
2265 if (!ok)
2266 goto out;
2267 v = vec[i];
2268 str = js_ValueToString(cx, v);
2269 if (!str) {
2270 ok = JS_FALSE;
2271 goto out;
2272 }
2273 vec[2 * i] = STRING_TO_JSVAL(str);
2274 vec[2 * i + 1] = v;
2275 } while (i != 0);
2276
2277 JS_ASSERT(tvr.u.array == vec);
2278 vec = (jsval *) cx->realloc(vec,
2279 4 * (size_t) newlen * sizeof(jsval));
2280 if (!vec) {
2281 vec = tvr.u.array;
2282 ok = JS_FALSE;
2283 goto out;
2284 }
2285 tvr.u.array = vec;
2286 mergesort_tmp = vec + 2 * newlen;
2287 memset(mergesort_tmp, 0, newlen * 2 * sizeof(jsval));
2288 tvr.count = newlen * 4;
2289 elemsize = 2 * sizeof(jsval);
2290 }
2291 ok = js_MergeSort(vec, (size_t) newlen, elemsize,
2292 sort_compare_strings, cx, mergesort_tmp);
2293 if (!ok)
2294 goto out;
2295 if (!all_strings) {
2296 /*
2297 * We want to make the following loop fast and to unroot the
2298 * cached results of toString invocations before the operation
2299 * callback has a chance to run the GC. For this reason we do
2300 * not call JS_CHECK_OPERATION_LIMIT in the loop.
2301 */
2302 i = 0;
2303 do {
2304 vec[i] = vec[2 * i + 1];
2305 } while (++i != newlen);
2306 }
2307 } else {
2308 void *mark;
2309
2310 js_LeaveTrace(cx);
2311
2312 ca.context = cx;
2313 ca.fval = fval;
2314 ca.elemroot = js_AllocStack(cx, 2 + 2, &mark);
2315 if (!ca.elemroot) {
2316 ok = JS_FALSE;
2317 goto out;
2318 }
2319 ok = js_MergeSort(vec, (size_t) newlen, sizeof(jsval),
2320 comparator_stack_cast(sort_compare),
2321 &ca, mergesort_tmp);
2322 js_FreeStack(cx, mark);
2323 if (!ok)
2324 goto out;
2325 }
2326
2327 /*
2328 * We no longer need to root the scratch space for the merge sort, so
2329 * unroot it now to make the job of a potential GC under InitArrayElements
2330 * easier.
2331 */
2332 tvr.count = newlen;
2333 ok = InitArrayElements(cx, obj, 0, newlen, vec, TargetElementsMayContainValues,
2334 SourceVectorAllValues);
2335 if (!ok)
2336 goto out;
2337
2338 out:
2339 JS_POP_TEMP_ROOT(cx, &tvr);
2340 cx->free(vec);
2341 if (!ok)
2342 return JS_FALSE;
2343
2344 /* Set undefs that sorted after the rest of elements. */
2345 while (undefs != 0) {
2346 --undefs;
2347 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2348 !SetArrayElement(cx, obj, newlen++, JSVAL_VOID)) {
2349 return JS_FALSE;
2350 }
2351 }
2352
2353 /* Re-create any holes that sorted to the end of the array. */
2354 while (len > newlen) {
2355 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2356 !DeleteArrayElement(cx, obj, --len)) {
2357 return JS_FALSE;
2358 }
2359 }
2360 *vp = OBJECT_TO_JSVAL(obj);
2361 return JS_TRUE;
2362 }
2363
2364 /*
2365 * Perl-inspired push, pop, shift, unshift, and splice methods.
2366 */
2367 static JSBool
2368 array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
2369 {
2370 jsuint length;
2371
2372 if (!js_GetLengthProperty(cx, obj, &length))
2373 return JS_FALSE;
2374 if (!InitArrayElements(cx, obj, length, argc, argv, TargetElementsMayContainValues,
2375 SourceVectorAllValues)) {
2376 return JS_FALSE;
2377 }
2378
2379 /* Per ECMA-262, return the new array length. */
2380 jsdouble newlength = length + jsdouble(argc);
2381 if (!IndexToValue(cx, newlength, rval))
2382 return JS_FALSE;
2383 return js_SetLengthProperty(cx, obj, newlength);
2384 }
2385
2386 static JSBool
2387 array_push1_dense(JSContext* cx, JSObject* obj, jsval v, jsval *rval)
2388 {
2389 uint32 length = obj->fslots[JSSLOT_ARRAY_LENGTH];
2390 if (INDEX_TOO_SPARSE(obj, length)) {
2391 if (!js_MakeArraySlow(cx, obj))
2392 return JS_FALSE;
2393 return array_push_slowly(cx, obj, 1, &v, rval);
2394 }
2395
2396 if (!EnsureCapacity(cx, obj, length + 1))
2397 return JS_FALSE;
2398 obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
2399
2400 JS_ASSERT(obj->dslots[length] == JSVAL_HOLE);
2401 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2402 obj->dslots[length] = v;
2403 return IndexToValue(cx, obj->fslots[JSSLOT_ARRAY_LENGTH], rval);
2404 }
2405
2406 JSBool JS_FASTCALL
2407 js_ArrayCompPush(JSContext *cx, JSObject *obj, jsval v)
2408 {
2409 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx, obj));
2410 uint32_t length = (uint32_t) obj->fslots[JSSLOT_ARRAY_LENGTH];
2411 JS_ASSERT(length <= js_DenseArrayCapacity(obj));
2412
2413 if (length == js_DenseArrayCapacity(obj)) {
2414 if (length > JS_ARGS_LENGTH_MAX) {
2415 JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
2416 JSMSG_ARRAY_INIT_TOO_BIG);
2417 return JS_FALSE;
2418 }
2419
2420 if (!EnsureCapacity(cx, obj, length + 1))
2421 return JS_FALSE;
2422 }
2423 obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
2424 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2425 obj->dslots[length] = v;
2426 return JS_TRUE;
2427 }
2428 JS_DEFINE_CALLINFO_3(extern, BOOL, js_ArrayCompPush, CONTEXT, OBJECT, JSVAL, 0, 0)
2429
2430 #ifdef JS_TRACER
2431 static jsval FASTCALL
2432 Array_p_push1(JSContext* cx, JSObject* obj, jsval v)
2433 {
2434 JSAutoTempValueRooter tvr(cx, v);
2435 if (OBJ_IS_DENSE_ARRAY(cx, obj)
2436 ? array_push1_dense(cx, obj, v, tvr.addr())
2437 : array_push_slowly(cx, obj, 1, tvr.addr(), tvr.addr())) {
2438 return tvr.value();
2439 }
2440 js_SetBuiltinError(cx);
2441 return JSVAL_VOID;
2442 }
2443 #endif
2444
2445 static JSBool
2446 array_push(JSContext *cx, uintN argc, jsval *vp)
2447 {
2448 JSObject *obj;
2449
2450 /* Insist on one argument and obj of the expected class. */
2451 obj = JS_THIS_OBJECT(cx, vp);
2452 if (!obj)
2453 return JS_FALSE;
2454 if (argc != 1 || !OBJ_IS_DENSE_ARRAY(cx, obj))
2455 return array_push_slowly(cx, obj, argc, vp + 2, vp);
2456
2457 return array_push1_dense(cx, obj, vp[2], vp);
2458 }
2459
2460 static JSBool
2461 array_pop_slowly(JSContext *cx, JSObject* obj, jsval *vp)
2462 {
2463 jsuint index;
2464 JSBool hole;
2465
2466 if (!js_GetLengthProperty(cx, obj, &index))
2467 return JS_FALSE;
2468 if (index == 0) {
2469 *vp = JSVAL_VOID;
2470 } else {
2471 index--;
2472
2473 /* Get the to-be-deleted property's value into vp. */
2474 if (!GetArrayElement(cx, obj, index, &hole, vp))
2475 return JS_FALSE;
2476 if (!hole && !DeleteArrayElement(cx, obj, index))
2477 return JS_FALSE;
2478 }
2479 return js_SetLengthProperty(cx, obj, index);
2480 }
2481
2482 static JSBool
2483 array_pop_dense(JSContext *cx, JSObject* obj, jsval *vp)
2484 {
2485 jsuint index;
2486 JSBool hole;
2487
2488 index = obj->fslots[JSSLOT_ARRAY_LENGTH];
2489 if (index == 0) {
2490 *vp = JSVAL_VOID;
2491 return JS_TRUE;
2492 }
2493 index--;
2494 if (!GetArrayElement(cx, obj, index, &hole, vp))
2495 return JS_FALSE;
2496 if (!hole && !DeleteArrayElement(cx, obj, index))
2497 return JS_FALSE;
2498 obj->fslots[JSSLOT_ARRAY_LENGTH] = index;
2499 return JS_TRUE;
2500 }
2501
2502 #ifdef JS_TRACER
2503 static jsval FASTCALL
2504 Array_p_pop(JSContext* cx, JSObject* obj)
2505 {
2506 JSAutoTempValueRooter tvr(cx);
2507 if (OBJ_IS_DENSE_ARRAY(cx, obj)
2508 ? array_pop_dense(cx, obj, tvr.addr())
2509 : array_pop_slowly(cx, obj, tvr.addr())) {
2510 return tvr.value();
2511 }
2512 js_SetBuiltinError(cx);
2513 return JSVAL_VOID;
2514 }
2515 #endif
2516
2517 static JSBool
2518 array_pop(JSContext *cx, uintN argc, jsval *vp)
2519 {
2520 JSObject *obj;
2521
2522 obj = JS_THIS_OBJECT(cx, vp);
2523 if (!obj)
2524 return JS_FALSE;
2525 if (OBJ_IS_DENSE_ARRAY(cx, obj))
2526 return array_pop_dense(cx, obj, vp);
2527 return array_pop_slowly(cx, obj, vp);
2528 }
2529
2530 static JSBool
2531 array_shift(JSContext *cx, uintN argc, jsval *vp)
2532 {
2533 JSObject *obj;
2534 jsuint length, i;
2535 JSBool hole;
2536
2537 obj = JS_THIS_OBJECT(cx, vp);
2538 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2539 return JS_FALSE;
2540 if (length == 0) {
2541 *vp = JSVAL_VOID;
2542 } else {
2543 length--;
2544
2545 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2546 length < js_DenseArrayCapacity(obj)) {
2547 if (JS_LIKELY(obj->dslots != NULL)) {
2548 *vp = obj->dslots[0];
2549 if (*vp == JSVAL_HOLE)
2550 *vp = JSVAL_VOID;
2551 else
2552 obj->fslots[JSSLOT_ARRAY_COUNT]--;
2553 memmove(obj->dslots, obj->dslots + 1, length * sizeof(jsval));
2554 obj->dslots[length] = JSVAL_HOLE;
2555 } else {
2556 /*
2557 * We don't need to modify the indexed properties of an empty array
2558 * with an explicitly set non-zero length when shift() is called on
2559 * it, but note fallthrough to reduce the length by one.
2560 */
2561 JS_ASSERT(obj->fslots[JSSLOT_ARRAY_COUNT] == 0);
2562 *vp = JSVAL_VOID;
2563 }
2564 } else {
2565 /* Get the to-be-deleted property's value into vp ASAP. */
2566 if (!GetArrayElement(cx, obj, 0, &hole, vp))
2567 return JS_FALSE;
2568
2569 /* Slide down the array above the first element. */
2570 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2571 for (i = 0; i != length; i++) {
2572 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2573 !GetArrayElement(cx, obj, i + 1, &hole, tvr.addr()) ||
2574 !SetOrDeleteArrayElement(cx, obj, i, hole, tvr.value())) {
2575 return JS_FALSE;
2576 }
2577 }
2578
2579 /* Delete the only or last element when it exists. */
2580 if (!hole && !DeleteArrayElement(cx, obj, length))
2581 return JS_FALSE;
2582 }
2583 }
2584 return js_SetLengthProperty(cx, obj, length);
2585 }
2586
2587 static JSBool
2588 array_unshift(JSContext *cx, uintN argc, jsval *vp)
2589 {
2590 JSObject *obj;
2591 jsval *argv;
2592 jsuint length;
2593 JSBool hole;
2594 jsdouble last, newlen;
2595
2596 obj = JS_THIS_OBJECT(cx, vp);
2597 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2598 return JS_FALSE;
2599 newlen = length;
2600 if (argc > 0) {
2601 /* Slide up the array to make room for argc at the bottom. */
2602 argv = JS_ARGV(cx, vp);
2603 if (length > 0) {
2604 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2605 !INDEX_TOO_SPARSE(obj, newlen + argc)) {
2606 JS_ASSERT(newlen + argc == length + argc);
2607 if (!EnsureCapacity(cx, obj, length + argc))
2608 return JS_FALSE;
2609 memmove(obj->dslots + argc, obj->dslots, length * sizeof(jsval));
2610 for (uint32 i = 0; i < argc; i++)
2611 obj->dslots[i] = JSVAL_HOLE;
2612 } else {
2613 last = length;
2614 jsdouble upperIndex = last + argc;
2615 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2616 do {
2617 --last, --upperIndex;
2618 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2619 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2620 !SetOrDeleteArrayElement(cx, obj, upperIndex, hole, tvr.value())) {
2621 return JS_FALSE;
2622 }
2623 } while (last != 0);
2624 }
2625 }
2626
2627 /* Copy from argv to the bottom of the array. */
2628 if (!InitArrayElements(cx, obj, 0, argc, argv, TargetElementsAllHoles, SourceVectorAllValues))
2629 return JS_FALSE;
2630
2631 newlen += argc;
2632 if (!js_SetLengthProperty(cx, obj, newlen))
2633 return JS_FALSE;
2634 }
2635
2636 /* Follow Perl by returning the new array length. */
2637 return IndexToValue(cx, newlen, vp);
2638 }
2639
2640 static JSBool
2641 array_splice(JSContext *cx, uintN argc, jsval *vp)
2642 {
2643 jsval *argv;
2644 JSObject *obj;
2645 jsuint length, begin, end, count, delta, last;
2646 jsdouble d;
2647 JSBool hole;
2648 JSObject *obj2;
2649
2650 /*
2651 * Create a new array value to return. Our ECMA v2 proposal specs
2652 * that splice always returns an array value, even when given no
2653 * arguments. We think this is best because it eliminates the need
2654 * for callers to do an extra test to handle the empty splice case.
2655 */
2656 obj2 = js_NewArrayObject(cx, 0, NULL);
2657 if (!obj2)
2658 return JS_FALSE;
2659 *vp = OBJECT_TO_JSVAL(obj2);
2660
2661 /* Nothing to do if no args. Otherwise get length. */
2662 if (argc == 0)
2663 return JS_TRUE;
2664 argv = JS_ARGV(cx, vp);
2665 obj = JS_THIS_OBJECT(cx, vp);
2666 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2667 return JS_FALSE;
2668
2669 /* Convert the first argument into a starting index. */
2670 d = js_ValueToNumber(cx, argv);
2671 if (JSVAL_IS_NULL(*argv))
2672 return JS_FALSE;
2673 d = js_DoubleToInteger(d);
2674 if (d < 0) {
2675 d += length;
2676 if (d < 0)
2677 d = 0;
2678 } else if (d > length) {
2679 d = length;
2680 }
2681 begin = (jsuint)d; /* d has been clamped to uint32 */
2682 argc--;
2683 argv++;
2684
2685 /* Convert the second argument from a count into a fencepost index. */
2686 delta = length - begin;
2687 if (argc == 0) {
2688 count = delta;
2689 end = length;
2690 } else {
2691 d = js_ValueToNumber(cx, argv);
2692 if (JSVAL_IS_NULL(*argv))
2693 return JS_FALSE;
2694 d = js_DoubleToInteger(d);
2695 if (d < 0)
2696 d = 0;
2697 else if (d > delta)
2698 d = delta;
2699 count = (jsuint)d;
2700 end = begin + count;
2701 argc--;
2702 argv++;
2703 }
2704
2705 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2706
2707 /* If there are elements to remove, put them into the return value. */
2708 if (count > 0) {
2709 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2710 !js_PrototypeHasIndexedProperties(cx, obj2) &&
2711 end <= js_DenseArrayCapacity(obj)) {
2712 if (!InitArrayObject(cx, obj2, count, obj->dslots + begin,
2713 obj->fslots[JSSLOT_ARRAY_COUNT] !=
2714 obj->fslots[JSSLOT_ARRAY_LENGTH])) {
2715 return JS_FALSE;
2716 }
2717 } else {
2718 for (last = begin; last < end; last++) {
2719 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2720 !GetArrayElement(cx, obj, last, &hole, tvr.addr())) {
2721 return JS_FALSE;
2722 }
2723
2724 /* Copy tvr.value() to the new array unless it's a hole. */
2725 if (!hole && !SetArrayElement(cx, obj2, last - begin, tvr.value()))
2726 return JS_FALSE;
2727 }
2728
2729 if (!js_SetLengthProperty(cx, obj2, count))
2730 return JS_FALSE;
2731 }
2732 }
2733
2734 /* Find the direction (up or down) to copy and make way for argv. */
2735 if (argc > count) {
2736 delta = (jsuint)argc - count;
2737 last = length;
2738 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2739 length <= js_DenseArrayCapacity(obj) &&
2740 (length == 0 || obj->dslots[length - 1] != JSVAL_HOLE)) {
2741 if (!EnsureCapacity(cx, obj, length + delta))
2742 return JS_FALSE;
2743 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2744 while (last-- > end) {
2745 jsval srcval = obj->dslots[last];
2746 jsval* dest = &obj->dslots[last + delta];
2747 if (*dest == JSVAL_HOLE && srcval != JSVAL_HOLE)
2748 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2749 *dest = srcval;
2750 }
2751 obj->fslots[JSSLOT_ARRAY_LENGTH] += delta;
2752 } else {
2753 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2754 while (last-- > end) {
2755 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2756 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2757 !SetOrDeleteArrayElement(cx, obj, last + delta, hole, tvr.value())) {
2758 return JS_FALSE;
2759 }
2760 }
2761 }
2762 length += delta;
2763 } else if (argc < count) {
2764 delta = count - (jsuint)argc;
2765 if (OBJ_IS_DENSE_ARRAY(cx, obj) && !js_PrototypeHasIndexedProperties(cx, obj) &&
2766 length <= js_DenseArrayCapacity(obj)) {
2767 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2768 for (last = end; last < length; last++) {
2769 jsval srcval = obj->dslots[last];
2770 jsval* dest = &obj->dslots[last - delta];
2771 if (*dest == JSVAL_HOLE && srcval != JSVAL_HOLE)
2772 obj->fslots[JSSLOT_ARRAY_COUNT]++;
2773 *dest = srcval;
2774 }
2775 } else {
2776 for (last = end; last < length; last++) {
2777 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2778 !GetArrayElement(cx, obj, last, &hole, tvr.addr()) ||
2779 !SetOrDeleteArrayElement(cx, obj, last - delta, hole, tvr.value())) {
2780 return JS_FALSE;
2781 }
2782 }
2783 }
2784 length -= delta;
2785 }
2786
2787 /*
2788 * Copy from argv into the hole to complete the splice, and update length in
2789 * case we deleted elements from the end.
2790 */
2791 return InitArrayElements(cx, obj, begin, argc, argv, TargetElementsMayContainValues,
2792 SourceVectorAllValues) &&
2793 js_SetLengthProperty(cx, obj, length);
2794 }
2795
2796 /*
2797 * Python-esque sequence operations.
2798 */
2799 static JSBool
2800 array_concat(JSContext *cx, uintN argc, jsval *vp)
2801 {
2802 jsval *argv, v;
2803 JSObject *aobj, *nobj;
2804 jsuint length, alength, slot;
2805 uintN i;
2806 JSBool hole;
2807
2808 /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
2809 argv = JS_ARGV(cx, vp) - 1;
2810 JS_ASSERT(JS_THIS_OBJECT(cx, vp) == JSVAL_TO_OBJECT(argv[0]));
2811
2812 /* Create a new Array object and root it using *vp. */
2813 aobj = JS_THIS_OBJECT(cx, vp);
2814 if (OBJ_IS_DENSE_ARRAY(cx, aobj)) {
2815 /*
2816 * Clone aobj but pass the minimum of its length and capacity, to
2817 * handle a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In
2818 * such a case we'll pass 8 (not 3) due to ARRAY_CAPACITY_MIN, which
2819 * will cause nobj to be over-allocated to 16. But in the normal case
2820 * where length is <= capacity, nobj and aobj will have the same
2821 * capacity.
2822 */
2823 length = aobj->fslots[JSSLOT_ARRAY_LENGTH];
2824 jsuint capacity = js_DenseArrayCapacity(aobj);
2825 nobj = js_NewArrayObject(cx, JS_MIN(length, capacity), aobj->dslots,
2826 aobj->fslots[JSSLOT_ARRAY_COUNT] !=
2827 (jsval) length);
2828 if (!nobj)
2829 return JS_FALSE;
2830 nobj->fslots[JSSLOT_ARRAY_LENGTH] = length;
2831 *vp = OBJECT_TO_JSVAL(nobj);
2832 if (argc == 0)
2833 return JS_TRUE;
2834 argc--;
2835 argv++;
2836 } else {
2837 nobj = js_NewArrayObject(cx, 0, NULL);
2838 if (!nobj)
2839 return JS_FALSE;
2840 *vp = OBJECT_TO_JSVAL(nobj);
2841 length = 0;
2842 }
2843
2844 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2845
2846 /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
2847 for (i = 0; i <= argc; i++) {
2848 if (!JS_CHECK_OPERATION_LIMIT(cx))
2849 return false;
2850 v = argv[i];
2851 if (!JSVAL_IS_PRIMITIVE(v)) {
2852 JSObject *wobj;
2853
2854 aobj = JSVAL_TO_OBJECT(v);
2855 wobj = js_GetWrappedObject(cx, aobj);
2856 if (OBJ_IS_ARRAY(cx, wobj)) {
2857 jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
2858 if (!aobj->getProperty(cx, id, tvr.addr()))
2859 return false;
2860 alength = ValueIsLength(cx, tvr.addr());
2861 if (JSVAL_IS_NULL(tvr.value()))
2862 return false;
2863 for (slot = 0; slot < alength; slot++) {
2864 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2865 !GetArrayElement(cx, aobj, slot, &hole, tvr.addr())) {
2866 return false;
2867 }
2868
2869 /*
2870 * Per ECMA 262, 15.4.4.4, step 9, ignore non-existent
2871 * properties.
2872 */
2873 if (!hole &&
2874 !SetArrayElement(cx, nobj, length+slot, tvr.value())) {
2875 return false;
2876 }
2877 }
2878 length += alength;
2879 continue;
2880 }
2881 }
2882
2883 if (!SetArrayElement(cx, nobj, length, v))
2884 return false;
2885 length++;
2886 }
2887
2888 return js_SetLengthProperty(cx, nobj, length);
2889 }
2890
2891 static JSBool
2892 array_slice(JSContext *cx, uintN argc, jsval *vp)
2893 {
2894 jsval *argv;
2895 JSObject *nobj, *obj;
2896 jsuint length, begin, end, slot;
2897 jsdouble d;
2898 JSBool hole;
2899
2900 argv = JS_ARGV(cx, vp);
2901
2902 obj = JS_THIS_OBJECT(cx, vp);
2903 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2904 return JS_FALSE;
2905 begin = 0;
2906 end = length;
2907
2908 if (argc > 0) {
2909 d = js_ValueToNumber(cx, &argv[0]);
2910 if (JSVAL_IS_NULL(argv[0]))
2911 return JS_FALSE;
2912 d = js_DoubleToInteger(d);
2913 if (d < 0) {
2914 d += length;
2915 if (d < 0)
2916 d = 0;
2917 } else if (d > length) {
2918 d = length;
2919 }
2920 begin = (jsuint)d;
2921
2922 if (argc > 1) {
2923 d = js_ValueToNumber(cx, &argv[1]);
2924 if (JSVAL_IS_NULL(argv[1]))
2925 return JS_FALSE;
2926 d = js_DoubleToInteger(d);
2927 if (d < 0) {
2928 d += length;
2929 if (d < 0)
2930 d = 0;
2931 } else if (d > length) {
2932 d = length;
2933 }
2934 end = (jsuint)d;
2935 }
2936 }
2937
2938 if (begin > end)
2939 begin = end;
2940
2941 if (OBJ_IS_DENSE_ARRAY(cx, obj) && end <= js_DenseArrayCapacity(obj) &&
2942 !js_PrototypeHasIndexedProperties(cx, obj)) {
2943 nobj = js_NewArrayObject(cx, end - begin, obj->dslots + begin,
2944 obj->fslots[JSSLOT_ARRAY_COUNT] !=
2945 obj->fslots[JSSLOT_ARRAY_LENGTH]);
2946 if (!nobj)
2947 return JS_FALSE;
2948 *vp = OBJECT_TO_JSVAL(nobj);
2949 return JS_TRUE;
2950 }
2951
2952 /* Create a new Array object and root it using *vp. */
2953 nobj = js_NewArrayObject(cx, 0, NULL);
2954 if (!nobj)
2955 return JS_FALSE;
2956 *vp = OBJECT_TO_JSVAL(nobj);
2957
2958 JSAutoTempValueRooter tvr(cx, JSVAL_NULL);
2959 for (slot = begin; slot < end; slot++) {
2960 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2961 !GetArrayElement(cx, obj, slot, &hole, tvr.addr())) {
2962 return JS_FALSE;
2963 }
2964 if (!hole && !SetArrayElement(cx, nobj, slot - begin, tvr.value()))
2965 return JS_FALSE;
2966 }
2967
2968 return js_SetLengthProperty(cx, nobj, end - begin);
2969 }
2970
2971 #if JS_HAS_ARRAY_EXTRAS
2972
2973 static JSBool
2974 array_indexOfHelper(JSContext *cx, JSBool isLast, uintN argc, jsval *vp)
2975 {
2976 JSObject *obj;
2977 jsuint length, i, stop;
2978 jsval tosearch;
2979 jsint direction;
2980 JSBool hole;
2981
2982 obj = JS_THIS_OBJECT(cx, vp);
2983 if (!obj || !js_GetLengthProperty(cx, obj, &length))
2984 return JS_FALSE;
2985 if (length == 0)
2986 goto not_found;
2987
2988 if (argc <= 1) {
2989 i = isLast ? length - 1 : 0;
2990 tosearch = (argc != 0) ? vp[2] : JSVAL_VOID;
2991 } else {
2992 jsdouble start;
2993
2994 tosearch = vp[2];
2995 start = js_ValueToNumber(cx, &vp[3]);
2996 if (JSVAL_IS_NULL(vp[3]))
2997 return JS_FALSE;
2998 start = js_DoubleToInteger(start);
2999 if (start < 0) {
3000 start += length;
3001 if (start < 0) {
3002 if (isLast)
3003 goto not_found;
3004 i = 0;
3005 } else {
3006 i = (jsuint)start;
3007 }
3008 } else if (start >= length) {
3009 if (!isLast)
3010 goto not_found;
3011 i = length - 1;
3012 } else {
3013 i = (jsuint)start;
3014 }
3015 }
3016
3017 if (isLast) {
3018 stop = 0;
3019 direction = -1;
3020 } else {
3021 stop = length - 1;
3022 direction = 1;
3023 }
3024
3025 for (;;) {
3026 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
3027 !GetArrayElement(cx, obj, (jsuint)i, &hole, vp)) {
3028 return JS_FALSE;
3029 }
3030 if (!hole && js_StrictlyEqual(cx, *vp, tosearch))
3031 return js_NewNumberInRootedValue(cx, i, vp);
3032 if (i == stop)
3033 goto not_found;
3034 i += direction;
3035 }
3036
3037 not_found:
3038 *vp = INT_TO_JSVAL(-1);
3039 return JS_TRUE;
3040 }
3041
3042 static JSBool
3043 array_indexOf(JSContext *cx, uintN argc, jsval *vp)
3044 {
3045 return array_indexOfHelper(cx, JS_FALSE, argc, vp);
3046 }
3047
3048 static JSBool
3049 array_lastIndexOf(JSContext *cx, uintN argc, jsval *vp)
3050 {
3051 return array_indexOfHelper(cx, JS_TRUE, argc, vp);
3052 }
3053
3054 /* Order is important; extras that take a predicate funarg must follow MAP. */
3055 typedef enum ArrayExtraMode {
3056 FOREACH,
3057 REDUCE,
3058 REDUCE_RIGHT,
3059 MAP,
3060 FILTER,
3061 SOME,
3062 EVERY
3063 } ArrayExtraMode;
3064
3065 #define REDUCE_MODE(mode) ((mode) == REDUCE || (mode) == REDUCE_RIGHT)
3066
3067 static JSBool
3068 array_extra(JSContext *cx, ArrayExtraMode mode, uintN argc, jsval *vp)
3069 {
3070 JSObject *obj;
3071 jsuint length, newlen;
3072 jsval *argv, *elemroot, *invokevp, *sp;
3073 JSBool ok, cond, hole;
3074 JSObject *callable, *thisp, *newarr;
3075 jsint start, end, step, i;
3076 void *mark;
3077
3078 obj = JS_THIS_OBJECT(cx, vp);
3079 if (!obj || !js_GetLengthProperty(cx, obj, &length))
3080 return JS_FALSE;
3081
3082 /*
3083 * First, get or compute our callee, so that we error out consistently
3084 * when passed a non-callable object.
3085 */
3086 if (argc == 0) {
3087 js_ReportMissingArg(cx, vp, 0);
3088 return JS_FALSE;
3089 }
3090 argv = vp + 2;
3091 callable = js_ValueToCallableObject(cx, &argv[0], JSV2F_SEARCH_STACK);
3092 if (!callable)
3093 return JS_FALSE;
3094
3095 /*
3096 * Set our initial return condition, used for zero-length array cases
3097 * (and pre-size our map return to match our known length, for all cases).
3098 */
3099 #ifdef __GNUC__ /* quell GCC overwarning */
3100 newlen = 0;
3101 newarr = NULL;
3102 #endif
3103 start = 0, end = length, step = 1;
3104
3105 switch (mode) {
3106 case REDUCE_RIGHT:
3107 start = length - 1, end = -1, step = -1;
3108 /* FALL THROUGH */
3109 case REDUCE:
3110 if (length == 0 && argc == 1) {
3111 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3112 JSMSG_EMPTY_ARRAY_REDUCE);
3113 return JS_FALSE;
3114 }
3115 if (argc >= 2) {
3116 *vp = argv[1];
3117 } else {
3118 do {
3119 if (!GetArrayElement(cx, obj, start, &hole, vp))
3120 return JS_FALSE;
3121 start += step;
3122 } while (hole && start != end);
3123
3124 if (hole && start == end) {
3125 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3126 JSMSG_EMPTY_ARRAY_REDUCE);
3127 return JS_FALSE;
3128 }
3129 }
3130 break;
3131 case MAP:
3132 case FILTER:
3133 newlen = (mode == MAP) ? length : 0;
3134 newarr = js_NewArrayObject(cx, newlen, NULL);
3135 if (!newarr)
3136 return JS_FALSE;
3137 *vp = OBJECT_TO_JSVAL(newarr);
3138 break;
3139 case SOME:
3140 *vp = JSVAL_FALSE;
3141 break;
3142 case EVERY:
3143 *vp = JSVAL_TRUE;
3144 break;
3145 case FOREACH:
3146 *vp = JSVAL_VOID;
3147 break;
3148 }
3149
3150 if (length == 0)
3151 return JS_TRUE;
3152
3153 if (argc > 1 && !REDUCE_MODE(mode)) {
3154 if (!js_ValueToObject(cx, argv[1], &thisp))
3155 return JS_FALSE;
3156 argv[1] = OBJECT_TO_JSVAL(thisp);
3157 } else {
3158 thisp = NULL;
3159 }
3160
3161 /*
3162 * For all but REDUCE, we call with 3 args (value, index, array). REDUCE
3163 * requires 4 args (accum, value, index, array).
3164 */
3165 js_LeaveTrace(cx);
3166 argc = 3 + REDUCE_MODE(mode);
3167 elemroot = js_AllocStack(cx, 1 + 2 + argc, &mark);
3168 if (!elemroot)
3169 return JS_FALSE;
3170
3171 MUST_FLOW_THROUGH("out");
3172 ok = JS_TRUE;
3173 invokevp = elemroot + 1;
3174
3175 for (i = start; i != end; i += step) {
3176 ok = JS_CHECK_OPERATION_LIMIT(cx) &&
3177 GetArrayElement(cx, obj, i, &hole, elemroot);
3178 if (!ok)
3179 goto out;
3180 if (hole)
3181 continue;
3182
3183 /*
3184 * Push callable and 'this', then args. We must do this for every
3185 * iteration around the loop since js_Invoke uses spbase[0] for return
3186 * value storage, while some native functions use spbase[1] for local
3187 * rooting.
3188 */
3189 sp = invokevp;
3190 *sp++ = OBJECT_TO_JSVAL(callable);
3191 *sp++ = OBJECT_TO_JSVAL(thisp);
3192 if (REDUCE_MODE(mode))
3193 *sp++ = *vp;
3194 *sp++ = *elemroot;
3195 *sp++ = INT_TO_JSVAL(i);
3196 *sp++ = OBJECT_TO_JSVAL(obj);
3197
3198 /* Do the call. */
3199 ok = js_Invoke(cx, argc, invokevp, 0);
3200 if (!ok)
3201 break;
3202
3203 if (mode > MAP)
3204 cond = js_ValueToBoolean(*invokevp);
3205 #ifdef __GNUC__ /* quell GCC overwarning */
3206 else
3207 cond = JS_FALSE;
3208 #endif
3209
3210 switch (mode) {
3211 case FOREACH:
3212 break;
3213 case REDUCE:
3214 case REDUCE_RIGHT:
3215 *vp = *invokevp;
3216 break;
3217 case MAP:
3218 ok = SetArrayElement(cx, newarr, i, *invokevp);
3219 if (!ok)
3220 goto out;
3221 break;
3222 case FILTER:
3223 if (!cond)
3224 break;
3225 /* The filter passed *elemroot, so push it onto our result. */
3226 ok = SetArrayElement(cx, newarr, newlen++, *elemroot);
3227 if (!ok)
3228 goto out;
3229 break;
3230 case SOME:
3231 if (cond) {
3232 *vp = JSVAL_TRUE;
3233 goto out;
3234 }
3235 break;
3236 case EVERY:
3237 if (!cond) {
3238 *vp = JSVAL_FALSE;
3239 goto out;
3240 }
3241 break;
3242 }
3243 }
3244
3245 out:
3246 js_FreeStack(cx, mark);
3247 if (ok && mode == FILTER)
3248 ok = js_SetLengthProperty(cx, newarr, newlen);
3249 return ok;
3250 }
3251
3252 static JSBool
3253 array_forEach(JSContext *cx, uintN argc, jsval *vp)
3254 {
3255 return array_extra(cx, FOREACH, argc, vp);
3256 }
3257
3258 static JSBool
3259 array_map(JSContext *cx, uintN argc, jsval *vp)
3260 {
3261 return array_extra(cx, MAP, argc, vp);
3262 }
3263
3264 static JSBool
3265 array_reduce(JSContext *cx, uintN argc, jsval *vp)
3266 {
3267 return array_extra(cx, REDUCE, argc, vp);
3268 }
3269
3270 static JSBo