1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set sw=4 ts=8 et tw=78:
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
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/
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
17 * The Original Code is Mozilla Communicator client code, released
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.
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.
39 * ***** END LICENSE BLOCK ***** */
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.
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
55 * In dense mode, holes in the array are represented by JSVAL_HOLE. The final
56 * slot in fslots (JSSLOT_ARRAY_LOOKUP_HOLDER) is used to store the single jsid
57 * "in use" by a lookupProperty caller.
59 * Arrays are converted to use js_SlowArrayClass when any of these conditions
61 * - the load factor (COUNT / capacity) is less than 0.25, and there are
62 * more than MIN_SPARSE_INDEX slots total
63 * - a property is set that is not indexed (and not "length"); or
64 * - a property is defined that has non-default property attributes.
66 * Dense arrays do not track property creation order, so unlike other native
67 * objects and slow arrays, enumerating an array does not necessarily visit the
68 * properties in the order they were created. We could instead maintain the
69 * scope to track property enumeration order, but still use the fast slot
70 * access. That would have the same memory cost as just using a
71 * js_SlowArrayClass, but have the same performance characteristics as a dense
72 * array for slot accesses, at some cost in code complexity.
78 #include "jsutil.h" /* Added by JSIFY */
84 #include "jsbuiltins.h"
86 #include "jsversion.h"
87 #include "jsdbgapi.h" /* for js_TraceWatchPoints */
97 #include "jsstaticcheck.h"
99 /* 2^32 - 1 as a number and a string */
100 #define MAXINDEX 4294967295u
101 #define MAXSTR "4294967295"
103 /* Small arrays are dense, no matter what. */
104 #define MIN_SPARSE_INDEX 256
106 #define INDEX_TOO_BIG(index) ((index) > JS_BIT(29) - 1)
107 #define INDEX_TOO_SPARSE(array, index) \
108 (INDEX_TOO_BIG(index) || \
109 ((index) > js_DenseArrayCapacity(array) && (index) >= MIN_SPARSE_INDEX && \
110 (index) > (uint32)((array)->fslots[JSSLOT_ARRAY_COUNT] + 1) * 4))
112 JS_STATIC_ASSERT(sizeof(JSScopeProperty
) > 4 * sizeof(jsval
));
114 #define ENSURE_SLOW_ARRAY(cx, obj) \
115 (OBJ_GET_CLASS(cx, obj) == &js_SlowArrayClass || js_MakeArraySlow(cx, obj))
118 * Determine if the id represents an array index or an XML property index.
120 * An id is an array index according to ECMA by (15.4):
122 * "Array objects give special treatment to a certain class of property names.
123 * A property name P (in the form of a string value) is an array index if and
124 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
127 * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
128 * except that by using signed 32-bit integers we miss the top half of the
129 * valid range. This function checks the string representation itself; note
130 * that calling a standard conversion routine might allow strings such as
131 * "08" or "4.0" as array indices, which they are not.
134 js_IdIsIndex(jsval id
, jsuint
*indexp
)
139 if (JSVAL_IS_INT(id
)) {
141 i
= JSVAL_TO_INT(id
);
148 /* NB: id should be a string, but jsxml.c may call us with an object id. */
149 if (!JSVAL_IS_STRING(id
))
152 str
= JSVAL_TO_STRING(id
);
153 cp
= JSSTRING_CHARS(str
);
154 if (JS7_ISDEC(*cp
) && JSSTRING_LENGTH(str
) < sizeof(MAXSTR
)) {
155 jsuint index
= JS7_UNDEC(*cp
++);
159 while (JS7_ISDEC(*cp
)) {
162 index
= 10*index
+ c
;
167 /* Ensure that all characters were consumed and we didn't overflow. */
169 (oldIndex
< (MAXINDEX
/ 10) ||
170 (oldIndex
== (MAXINDEX
/ 10) && c
< (MAXINDEX
% 10))))
180 ValueIsLength(JSContext
*cx
, jsval
* vp
)
186 if (JSVAL_IS_INT(*vp
)) {
187 i
= JSVAL_TO_INT(*vp
);
193 d
= js_ValueToNumber(cx
, vp
);
194 if (JSVAL_IS_NULL(*vp
))
197 if (JSDOUBLE_IS_NaN(d
))
200 if (d
!= (jsdouble
) length
)
205 JS_ReportErrorNumber(cx
, js_GetErrorMessage
, NULL
,
206 JSMSG_BAD_ARRAY_LENGTH
);
212 js_GetLengthProperty(JSContext
*cx
, JSObject
*obj
, jsuint
*lengthp
)
214 JSTempValueRooter tvr
;
219 if (OBJ_IS_ARRAY(cx
, obj
)) {
220 *lengthp
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
224 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
225 id
= ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
);
226 ok
= OBJ_GET_PROPERTY(cx
, obj
, id
, &tvr
.u
.value
);
228 if (JSVAL_IS_INT(tvr
.u
.value
)) {
229 i
= JSVAL_TO_INT(tvr
.u
.value
);
230 *lengthp
= (jsuint
)i
; /* jsuint cast does ToUint32 */
232 *lengthp
= js_ValueToECMAUint32(cx
, &tvr
.u
.value
);
233 ok
= !JSVAL_IS_NULL(tvr
.u
.value
);
236 JS_POP_TEMP_ROOT(cx
, &tvr
);
241 IndexToValue(JSContext
*cx
, jsdouble index
, jsval
*vp
)
243 return js_NewWeaklyRootedNumber(cx
, index
, vp
);
247 js_IndexToId(JSContext
*cx
, jsuint index
, jsid
*idp
)
251 if (index
<= JSVAL_INT_MAX
) {
252 *idp
= INT_TO_JSID(index
);
255 str
= js_NumberToString(cx
, index
);
258 return js_ValueToStringId(cx
, STRING_TO_JSVAL(str
), idp
);
262 BigIndexToId(JSContext
*cx
, JSObject
*obj
, jsuint index
, JSBool createAtom
,
265 jschar buf
[10], *start
;
268 JS_STATIC_ASSERT((jsuint
)-1 == 4294967295U);
270 JS_ASSERT(index
> JSVAL_INT_MAX
);
272 start
= JS_ARRAY_END(buf
);
275 *start
= (jschar
)('0' + index
% 10);
277 } while (index
!= 0);
280 * Skip the atomization if the class is known to store atoms corresponding
281 * to big indexes together with elements. In such case we know that the
282 * array does not have an element at the given index if its atom does not
283 * exist. Fast arrays (clasp == &js_ArrayClass) don't use atoms for
284 * any indexes, though it would be rare to see them have a big index
288 ((clasp
= OBJ_GET_CLASS(cx
, obj
)) == &js_SlowArrayClass
||
289 clasp
== &js_ArgumentsClass
||
290 clasp
== &js_ObjectClass
)) {
291 atom
= js_GetExistingStringAtom(cx
, start
, JS_ARRAY_END(buf
) - start
);
297 atom
= js_AtomizeChars(cx
, start
, JS_ARRAY_END(buf
) - start
, 0);
302 *idp
= ATOM_TO_JSID(atom
);
307 ResizeSlots(JSContext
*cx
, JSObject
*obj
, uint32 oldsize
, uint32 size
)
309 jsval
*slots
, *newslots
;
313 JS_free(cx
, obj
->dslots
- 1);
319 if (size
> ~(uint32
)0 / sizeof(jsval
)) {
320 js_ReportAllocationOverflow(cx
);
324 slots
= obj
->dslots
? obj
->dslots
- 1 : NULL
;
325 newslots
= (jsval
*) JS_realloc(cx
, slots
, sizeof (jsval
) * (size
+ 1));
329 obj
->dslots
= newslots
+ 1;
330 js_SetDenseArrayCapacity(obj
, size
);
332 for (slots
= obj
->dslots
+ oldsize
; slots
< obj
->dslots
+ size
; slots
++)
339 * When a dense array with CAPACITY_DOUBLING_MAX or fewer slots needs to grow,
340 * double its capacity, to push() N elements in amortized O(N) time.
342 * Above this limit, grow by 12.5% each time. Speed is still amortized O(N),
343 * with a higher constant factor, and we waste less space.
345 #define CAPACITY_DOUBLING_MAX (1024 * 1024)
348 * Round up all large allocations to a multiple of this (1MB), so as not to
349 * waste space if malloc gives us 1MB-sized chunks (as jemalloc does).
351 #define CAPACITY_CHUNK (1024 * 1024 / sizeof(jsval))
354 EnsureCapacity(JSContext
*cx
, JSObject
*obj
, uint32 capacity
)
356 uint32 oldsize
= js_DenseArrayCapacity(obj
);
358 if (capacity
> oldsize
) {
360 * If this overflows uint32, capacity is very large. nextsize will end
361 * up being less than capacity, the code below will thus disregard it,
362 * and ResizeSlots will fail.
364 * The way we use dslots[-1] forces a few +1s and -1s here. For
365 * example, (oldsize * 2 + 1) produces the sequence 7, 15, 31, 63, ...
366 * which makes the total allocation size (with dslots[-1]) a power
369 uint32 nextsize
= (oldsize
<= CAPACITY_DOUBLING_MAX
)
371 : oldsize
+ (oldsize
>> 3);
373 capacity
= JS_MAX(capacity
, nextsize
);
374 if (capacity
>= CAPACITY_CHUNK
)
375 capacity
= JS_ROUNDUP(capacity
+ 1, CAPACITY_CHUNK
) - 1; /* -1 for dslots[-1] */
376 else if (capacity
< ARRAY_CAPACITY_MIN
)
377 capacity
= ARRAY_CAPACITY_MIN
;
378 return ResizeSlots(cx
, obj
, oldsize
, capacity
);
384 ReallyBigIndexToId(JSContext
* cx
, jsdouble index
, jsid
* idp
)
386 JSAutoTempValueRooter
dval(cx
);
387 if (!js_NewDoubleInRootedValue(cx
, index
, dval
.addr()) ||
388 !js_ValueToStringId(cx
, dval
.value(), idp
)) {
395 IndexToId(JSContext
* cx
, JSObject
* obj
, jsdouble index
, JSBool
* hole
, jsid
* idp
,
396 JSBool createAtom
= JS_FALSE
)
398 if (index
<= JSVAL_INT_MAX
) {
399 *idp
= INT_TO_JSID(index
);
403 if (index
<= jsuint(-1)) {
404 if (!BigIndexToId(cx
, obj
, jsuint(index
), createAtom
, idp
))
406 if (hole
&& JSVAL_IS_VOID(*idp
))
411 return ReallyBigIndexToId(cx
, index
, idp
);
415 * If the property at the given index exists, get its value into location
416 * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
417 * to JSVAL_VOID. This function assumes that the location pointed by vp is
418 * properly rooted and can be used as GC-protected storage for temporaries.
421 GetArrayElement(JSContext
*cx
, JSObject
*obj
, jsdouble index
, JSBool
*hole
,
424 JS_ASSERT(index
>= 0);
425 if (OBJ_IS_DENSE_ARRAY(cx
, obj
) && index
< js_DenseArrayCapacity(obj
) &&
426 (*vp
= obj
->dslots
[jsuint(index
)]) != JSVAL_HOLE
) {
431 JSAutoTempIdRooter
idr(cx
);
434 if (!IndexToId(cx
, obj
, index
, hole
, idr
.addr()))
443 if (!OBJ_LOOKUP_PROPERTY(cx
, obj
, idr
.id(), &obj2
, &prop
))
449 OBJ_DROP_PROPERTY(cx
, obj2
, prop
);
450 if (!OBJ_GET_PROPERTY(cx
, obj
, idr
.id(), vp
))
458 * Set the value of the property at the given index to v assuming v is rooted.
461 SetArrayElement(JSContext
*cx
, JSObject
*obj
, jsdouble index
, jsval v
)
463 JS_ASSERT(index
>= 0);
465 if (OBJ_IS_DENSE_ARRAY(cx
, obj
)) {
466 /* Predicted/prefetched code should favor the remains-dense case. */
467 if (index
<= jsuint(-1)) {
468 jsuint idx
= jsuint(index
);
469 if (!INDEX_TOO_SPARSE(obj
, idx
)) {
470 JS_ASSERT(idx
+ 1 > idx
);
471 if (!EnsureCapacity(cx
, obj
, idx
+ 1))
473 if (index
>= uint32(obj
->fslots
[JSSLOT_ARRAY_LENGTH
]))
474 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = idx
+ 1;
475 if (obj
->dslots
[idx
] == JSVAL_HOLE
)
476 obj
->fslots
[JSSLOT_ARRAY_COUNT
]++;
477 obj
->dslots
[idx
] = v
;
482 if (!js_MakeArraySlow(cx
, obj
))
486 JSAutoTempIdRooter
idr(cx
);
488 if (!IndexToId(cx
, obj
, index
, NULL
, idr
.addr(), JS_TRUE
))
490 JS_ASSERT(!JSVAL_IS_VOID(idr
.id()));
492 return OBJ_SET_PROPERTY(cx
, obj
, idr
.id(), &v
);
496 DeleteArrayElement(JSContext
*cx
, JSObject
*obj
, jsdouble index
)
498 JS_ASSERT(index
>= 0);
499 if (OBJ_IS_DENSE_ARRAY(cx
, obj
)) {
500 if (index
<= jsuint(-1)) {
501 jsuint idx
= jsuint(index
);
502 if (!INDEX_TOO_SPARSE(obj
, idx
) && idx
< js_DenseArrayCapacity(obj
)) {
503 if (obj
->dslots
[idx
] != JSVAL_HOLE
)
504 obj
->fslots
[JSSLOT_ARRAY_COUNT
]--;
505 obj
->dslots
[idx
] = JSVAL_HOLE
;
512 JSAutoTempIdRooter
idr(cx
);
514 if (!IndexToId(cx
, obj
, index
, NULL
, idr
.addr()))
516 if (JSVAL_IS_VOID(idr
.id()))
520 return OBJ_DELETE_PROPERTY(cx
, obj
, idr
.id(), &junk
);
524 * When hole is true, delete the property at the given index. Otherwise set
525 * its value to v assuming v is rooted.
528 SetOrDeleteArrayElement(JSContext
*cx
, JSObject
*obj
, jsdouble index
,
529 JSBool hole
, jsval v
)
532 JS_ASSERT(JSVAL_IS_VOID(v
));
533 return DeleteArrayElement(cx
, obj
, index
);
535 return SetArrayElement(cx
, obj
, index
, v
);
539 js_SetLengthProperty(JSContext
*cx
, JSObject
*obj
, jsdouble length
)
544 if (!IndexToValue(cx
, length
, &v
))
546 id
= ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
);
547 return OBJ_SET_PROPERTY(cx
, obj
, id
, &v
);
551 js_HasLengthProperty(JSContext
*cx
, JSObject
*obj
, jsuint
*lengthp
)
553 JSErrorReporter older
;
554 JSTempValueRooter tvr
;
558 older
= JS_SetErrorReporter(cx
, NULL
);
559 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
560 id
= ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
);
561 ok
= OBJ_GET_PROPERTY(cx
, obj
, id
, &tvr
.u
.value
);
562 JS_SetErrorReporter(cx
, older
);
564 *lengthp
= ValueIsLength(cx
, &tvr
.u
.value
);
565 ok
= !JSVAL_IS_NULL(tvr
.u
.value
);
567 JS_POP_TEMP_ROOT(cx
, &tvr
);
572 js_IsArrayLike(JSContext
*cx
, JSObject
*obj
, JSBool
*answerp
, jsuint
*lengthp
)
576 clasp
= OBJ_GET_CLASS(cx
, obj
);
577 *answerp
= (clasp
== &js_ArgumentsClass
|| clasp
== &js_ArrayClass
||
578 clasp
== &js_SlowArrayClass
);
583 return js_GetLengthProperty(cx
, obj
, lengthp
);
587 * The 'length' property of all native Array instances is a shared permanent
588 * property of Array.prototype, so it appears to be a direct property of each
589 * array instance delegating to that Array.prototype. It accesses the private
590 * slot reserved by js_ArrayClass.
592 * Since SpiderMonkey supports cross-class prototype-based delegation, we have
593 * to be careful about the length getter and setter being called on an object
594 * not of Array class. For the getter, we search obj's prototype chain for the
595 * array that caused this getter to be invoked. In the setter case to overcome
596 * the JSPROP_SHARED attribute, we must define a shadowing length property.
599 array_length_getter(JSContext
*cx
, JSObject
*obj
, jsval id
, jsval
*vp
)
602 if (OBJ_IS_ARRAY(cx
, obj
))
603 return IndexToValue(cx
, obj
->fslots
[JSSLOT_ARRAY_LENGTH
], vp
);
604 } while ((obj
= OBJ_GET_PROTO(cx
, obj
)) != NULL
);
609 array_length_setter(JSContext
*cx
, JSObject
*obj
, jsval id
, jsval
*vp
)
611 jsuint newlen
, oldlen
, gap
, index
;
614 JSTempValueRooter tvr
;
617 if (!OBJ_IS_ARRAY(cx
, obj
)) {
618 jsid lengthId
= ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
);
620 return OBJ_DEFINE_PROPERTY(cx
, obj
, lengthId
, *vp
, NULL
, NULL
,
621 JSPROP_ENUMERATE
, NULL
);
624 newlen
= ValueIsLength(cx
, vp
);
625 if (JSVAL_IS_NULL(*vp
))
627 oldlen
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
629 if (oldlen
== newlen
)
632 if (!IndexToValue(cx
, newlen
, vp
))
635 if (oldlen
< newlen
) {
636 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = newlen
;
640 if (OBJ_IS_DENSE_ARRAY(cx
, obj
)) {
641 /* Don't reallocate if we're not actually shrinking our slots. */
642 jsuint oldsize
= js_DenseArrayCapacity(obj
);
643 if (oldsize
>= newlen
&& !ResizeSlots(cx
, obj
, oldsize
, newlen
))
645 } else if (oldlen
- newlen
< (1 << 24)) {
648 if (!JS_CHECK_OPERATION_LIMIT(cx
) ||
649 !DeleteArrayElement(cx
, obj
, oldlen
)) {
652 } while (oldlen
!= newlen
);
655 * We are going to remove a lot of indexes in a presumably sparse
656 * array. So instead of looping through indexes between newlen and
657 * oldlen, we iterate through all properties and remove those that
658 * correspond to indexes in the half-open range [newlen, oldlen). See
661 iter
= JS_NewPropertyIterator(cx
, obj
);
665 /* Protect iter against GC in OBJ_DELETE_PROPERTY. */
666 JS_PUSH_TEMP_ROOT_OBJECT(cx
, iter
, &tvr
);
667 gap
= oldlen
- newlen
;
669 ok
= (JS_CHECK_OPERATION_LIMIT(cx
) &&
670 JS_NextProperty(cx
, iter
, &id
));
673 if (JSVAL_IS_VOID(id
))
675 if (js_IdIsIndex(id
, &index
) && index
- newlen
< gap
) {
676 ok
= OBJ_DELETE_PROPERTY(cx
, obj
, id
, &junk
);
681 JS_POP_TEMP_ROOT(cx
, &tvr
);
686 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = newlen
;
691 array_lookupProperty(JSContext
*cx
, JSObject
*obj
, jsid id
, JSObject
**objp
,
695 union { JSProperty
*p
; jsval
*v
; } u
;
697 if (!OBJ_IS_DENSE_ARRAY(cx
, obj
))
698 return js_LookupProperty(cx
, obj
, id
, objp
, propp
);
701 * We have only indexed properties up to capacity (excepting holes), plus
702 * the length property. For all else, we delegate to the prototype.
704 if (id
!= ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
) &&
705 (!js_IdIsIndex(id
, &i
) ||
706 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] == 0 ||
707 i
>= js_DenseArrayCapacity(obj
) ||
708 obj
->dslots
[i
] == JSVAL_HOLE
))
710 JSObject
*proto
= STOBJ_GET_PROTO(obj
);
718 return OBJ_LOOKUP_PROPERTY(cx
, proto
, id
, objp
, propp
);
721 /* FIXME 417501: threadsafety: could race with a lookup on another thread.
722 * If we can only have a single lookup active per context, we could
723 * pigeonhole this on the context instead. */
724 JS_ASSERT(JSVAL_IS_VOID(obj
->fslots
[JSSLOT_ARRAY_LOOKUP_HOLDER
]));
725 obj
->fslots
[JSSLOT_ARRAY_LOOKUP_HOLDER
] = (jsval
) id
;
726 u
.v
= &(obj
->fslots
[JSSLOT_ARRAY_LOOKUP_HOLDER
]);
733 array_dropProperty(JSContext
*cx
, JSObject
*obj
, JSProperty
*prop
)
735 JS_ASSERT_IF(OBJ_IS_DENSE_ARRAY(cx
, obj
),
736 !JSVAL_IS_VOID(obj
->fslots
[JSSLOT_ARRAY_LOOKUP_HOLDER
]));
738 obj
->fslots
[JSSLOT_ARRAY_LOOKUP_HOLDER
] = JSVAL_VOID
;
743 js_GetDenseArrayElementValue(JSObject
*obj
, JSProperty
*prop
)
745 /* OBJ_IS_DENSE_ARRAY does not use the cx argument. */
746 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx
, obj
));
747 JS_ASSERT((void *) prop
==
748 (void *) &(obj
->fslots
[JSSLOT_ARRAY_LOOKUP_HOLDER
]));
749 JS_ASSERT((jsval
) prop
->id
== obj
->fslots
[JSSLOT_ARRAY_LOOKUP_HOLDER
]);
750 JS_ASSERT(JSVAL_IS_INT(prop
->id
));
752 jsint i
= JSID_TO_INT(prop
->id
);
754 jsval v
= obj
->dslots
[i
];
755 JS_ASSERT(v
!= JSVAL_HOLE
);
760 array_getProperty(JSContext
*cx
, JSObject
*obj
, jsid id
, jsval
*vp
)
764 if (id
== ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
))
765 return IndexToValue(cx
, obj
->fslots
[JSSLOT_ARRAY_LENGTH
], vp
);
767 if (id
== ATOM_TO_JSID(cx
->runtime
->atomState
.protoAtom
)) {
768 *vp
= STOBJ_GET_SLOT(obj
, JSSLOT_PROTO
);
772 if (!OBJ_IS_DENSE_ARRAY(cx
, obj
))
773 return js_GetProperty(cx
, obj
, id
, vp
);
775 if (!js_IdIsIndex(ID_TO_VALUE(id
), &i
) || i
>= js_DenseArrayCapacity(obj
) ||
776 obj
->dslots
[i
] == JSVAL_HOLE
) {
779 JSScopeProperty
*sprop
;
781 JSObject
*proto
= STOBJ_GET_PROTO(obj
);
788 if (js_LookupPropertyWithFlags(cx
, proto
, id
, cx
->resolveFlags
,
793 if (OBJ_IS_NATIVE(obj2
)) {
794 sprop
= (JSScopeProperty
*) prop
;
795 if (!js_NativeGet(cx
, obj
, obj2
, sprop
, vp
))
798 OBJ_DROP_PROPERTY(cx
, obj2
, prop
);
803 *vp
= obj
->dslots
[i
];
808 slowarray_addProperty(JSContext
*cx
, JSObject
*obj
, jsval id
, jsval
*vp
)
810 jsuint index
, length
;
812 if (!js_IdIsIndex(id
, &index
))
814 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
816 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = index
+ 1;
821 slowarray_trace(JSTracer
*trc
, JSObject
*obj
)
823 uint32 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
825 JS_ASSERT(STOBJ_GET_CLASS(obj
) == &js_SlowArrayClass
);
828 * Move JSSLOT_ARRAY_LENGTH aside to prevent the GC from treating
829 * untagged integer values as objects or strings.
831 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = JSVAL_VOID
;
832 js_TraceObject(trc
, obj
);
833 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = length
;
836 static JSObjectOps js_SlowArrayObjectOps
;
839 slowarray_getObjectOps(JSContext
*cx
, JSClass
*clasp
)
841 return &js_SlowArrayObjectOps
;
845 array_setProperty(JSContext
*cx
, JSObject
*obj
, jsid id
, jsval
*vp
)
849 if (id
== ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
))
850 return array_length_setter(cx
, obj
, id
, vp
);
852 if (!OBJ_IS_DENSE_ARRAY(cx
, obj
))
853 return js_SetProperty(cx
, obj
, id
, vp
);
855 if (!js_IdIsIndex(id
, &i
) || INDEX_TOO_SPARSE(obj
, i
)) {
856 if (!js_MakeArraySlow(cx
, obj
))
858 return js_SetProperty(cx
, obj
, id
, vp
);
861 if (!EnsureCapacity(cx
, obj
, i
+ 1))
864 if (i
>= (uint32
)obj
->fslots
[JSSLOT_ARRAY_LENGTH
])
865 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = i
+ 1;
866 if (obj
->dslots
[i
] == JSVAL_HOLE
)
867 obj
->fslots
[JSSLOT_ARRAY_COUNT
]++;
868 obj
->dslots
[i
] = *vp
;
873 js_PrototypeHasIndexedProperties(JSContext
*cx
, JSObject
*obj
)
876 * Walk up the prototype chain and see if this indexed element already
877 * exists. If we hit the end of the prototype chain, it's safe to set the
878 * element on the original object.
880 while ((obj
= JSVAL_TO_OBJECT(obj
->fslots
[JSSLOT_PROTO
])) != NULL
) {
882 * If the prototype is a non-native object (possibly a dense array), or
883 * a native object (possibly a slow array) that has indexed properties,
886 if (!OBJ_IS_NATIVE(obj
))
888 if (SCOPE_HAS_INDEXED_PROPERTIES(OBJ_SCOPE(obj
)))
896 js_Array_dense_setelem(JSContext
* cx
, JSObject
* obj
, jsint i
, jsval v
)
898 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx
, obj
));
901 * Let the interpreter worry about negative array indexes.
907 * If needed, grow the array as long it remains dense, otherwise fall off trace.
909 jsuint u
= jsuint(i
);
910 jsuint capacity
= js_DenseArrayCapacity(obj
);
911 if ((u
>= capacity
) && (INDEX_TOO_SPARSE(obj
, u
) || !EnsureCapacity(cx
, obj
, u
+ 1)))
914 if (obj
->dslots
[u
] == JSVAL_HOLE
) {
915 if (js_PrototypeHasIndexedProperties(cx
, obj
))
918 if (u
>= jsuint(obj
->fslots
[JSSLOT_ARRAY_LENGTH
]))
919 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = u
+ 1;
920 ++obj
->fslots
[JSSLOT_ARRAY_COUNT
];
929 array_defineProperty(JSContext
*cx
, JSObject
*obj
, jsid id
, jsval value
,
930 JSPropertyOp getter
, JSPropertyOp setter
, uintN attrs
,
936 if (id
== ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
))
939 isIndex
= js_IdIsIndex(ID_TO_VALUE(id
), &i
);
940 if (!isIndex
|| attrs
!= JSPROP_ENUMERATE
) {
941 if (!ENSURE_SLOW_ARRAY(cx
, obj
))
943 return js_DefineProperty(cx
, obj
, id
, value
, getter
, setter
, attrs
, propp
);
946 return array_setProperty(cx
, obj
, id
, &value
);
950 array_getAttributes(JSContext
*cx
, JSObject
*obj
, jsid id
, JSProperty
*prop
,
953 *attrsp
= id
== ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
)
954 ? JSPROP_PERMANENT
: JSPROP_ENUMERATE
;
959 array_setAttributes(JSContext
*cx
, JSObject
*obj
, jsid id
, JSProperty
*prop
,
962 JS_ReportErrorNumber(cx
, js_GetErrorMessage
, NULL
,
963 JSMSG_CANT_SET_ARRAY_ATTRS
);
968 array_deleteProperty(JSContext
*cx
, JSObject
*obj
, jsval id
, jsval
*rval
)
972 if (!OBJ_IS_DENSE_ARRAY(cx
, obj
))
973 return js_DeleteProperty(cx
, obj
, id
, rval
);
975 if (id
== ATOM_TO_JSID(cx
->runtime
->atomState
.lengthAtom
)) {
980 if (js_IdIsIndex(id
, &i
) && i
< js_DenseArrayCapacity(obj
) &&
981 obj
->dslots
[i
] != JSVAL_HOLE
) {
982 obj
->fslots
[JSSLOT_ARRAY_COUNT
]--;
983 obj
->dslots
[i
] = JSVAL_HOLE
;
991 * JSObjectOps.enumerate implementation.
993 * For a fast array, JSENUMERATE_INIT captures in the enumeration state both
994 * the length of the array and the bitmap indicating the positions of holes in
995 * the array. This ensures that adding or deleting array elements does not
996 * affect the sequence of indexes JSENUMERATE_NEXT returns.
998 * For a common case of an array without holes, to represent the state we pack
999 * the (nextEnumerationIndex, arrayLength) pair as a pseudo-boolean jsval.
1000 * This is possible when length <= PACKED_UINT_PAIR_BITS. For arrays with
1001 * greater length or holes we allocate the JSIndexIterState structure and
1002 * store it as an int-tagged private pointer jsval. For a slow array we
1003 * delegate the enumeration implementation to js_Enumerate in
1004 * slowarray_enumerate.
1006 * Array mutations can turn a fast array into a slow one after the enumeration
1007 * starts. When this happens, slowarray_enumerate receives a state created
1008 * when the array was fast. To distinguish such fast state from a slow state,
1009 * which is an int-tagged pointer that js_Enumerate creates, we set not one
1010 * but two lowest bits when tagging a JSIndexIterState pointer -- see
1011 * INDEX_ITER_TAG usage below. Thus, when slowarray_enumerate receives a state
1012 * tagged with JSVAL_BOOLEAN or with two lowest bits set, it knows that this
1013 * is a fast state so it calls array_enumerate to continue enumerating the
1014 * indexes present in the original fast array.
1017 #define PACKED_UINT_PAIR_BITS 14
1018 #define PACKED_UINT_PAIR_MASK JS_BITMASK(PACKED_UINT_PAIR_BITS)
1020 #define UINT_PAIR_TO_BOOLEAN_JSVAL(i,j) \
1021 (JS_ASSERT((uint32) (i) <= PACKED_UINT_PAIR_MASK), \
1022 JS_ASSERT((uint32) (j) <= PACKED_UINT_PAIR_MASK), \
1023 ((jsval) (i) << (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)) | \
1024 ((jsval) (j) << (JSVAL_TAGBITS)) | \
1025 (jsval) JSVAL_BOOLEAN)
1027 #define BOOLEAN_JSVAL_TO_UINT_PAIR(v,i,j) \
1028 (JS_ASSERT(JSVAL_TAG(v) == JSVAL_BOOLEAN), \
1029 (i) = (uint32) ((v) >> (PACKED_UINT_PAIR_BITS + JSVAL_TAGBITS)), \
1030 (j) = (uint32) ((v) >> JSVAL_TAGBITS) & PACKED_UINT_PAIR_MASK, \
1031 JS_ASSERT((i) <= PACKED_UINT_PAIR_MASK))
1033 JS_STATIC_ASSERT(PACKED_UINT_PAIR_BITS
* 2 + JSVAL_TAGBITS
<= JS_BITS_PER_WORD
);
1035 typedef struct JSIndexIterState
{
1041 * Variable-length bitmap representing array's holes. It must not be
1042 * accessed when hasHoles is false.
1047 #define INDEX_ITER_TAG 3
1049 JS_STATIC_ASSERT(JSVAL_INT
== 1);
1052 array_enumerate(JSContext
*cx
, JSObject
*obj
, JSIterateOp enum_op
,
1053 jsval
*statep
, jsid
*idp
)
1056 JSIndexIterState
*ii
;
1059 case JSENUMERATE_INIT
:
1060 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx
, obj
));
1061 capacity
= js_DenseArrayCapacity(obj
);
1063 *idp
= INT_TO_JSVAL(obj
->fslots
[JSSLOT_ARRAY_COUNT
]);
1065 for (i
= 0; i
!= capacity
; ++i
) {
1066 if (obj
->dslots
[i
] == JSVAL_HOLE
) {
1068 ii
= (JSIndexIterState
*)
1069 JS_malloc(cx
, offsetof(JSIndexIterState
, holes
) +
1070 JS_BITMAP_SIZE(capacity
));
1073 ii
->hasHoles
= JS_TRUE
;
1074 memset(ii
->holes
, 0, JS_BITMAP_SIZE(capacity
));
1076 JS_SET_BIT(ii
->holes
, i
);
1080 /* Array has no holes. */
1081 if (capacity
<= PACKED_UINT_PAIR_MASK
) {
1082 *statep
= UINT_PAIR_TO_BOOLEAN_JSVAL(0, capacity
);
1085 ii
= (JSIndexIterState
*)
1086 JS_malloc(cx
, offsetof(JSIndexIterState
, holes
));
1089 ii
->hasHoles
= JS_FALSE
;
1092 ii
->length
= capacity
;
1093 *statep
= (jsval
) ii
| INDEX_ITER_TAG
;
1094 JS_ASSERT(*statep
& JSVAL_INT
);
1097 case JSENUMERATE_NEXT
:
1098 if (JSVAL_TAG(*statep
) == JSVAL_BOOLEAN
) {
1099 BOOLEAN_JSVAL_TO_UINT_PAIR(*statep
, i
, capacity
);
1100 if (i
!= capacity
) {
1101 *idp
= INT_TO_JSID(i
);
1102 *statep
= UINT_PAIR_TO_BOOLEAN_JSVAL(i
+ 1, capacity
);
1106 JS_ASSERT((*statep
& INDEX_ITER_TAG
) == INDEX_ITER_TAG
);
1107 ii
= (JSIndexIterState
*) (*statep
& ~INDEX_ITER_TAG
);
1109 if (i
!= ii
->length
) {
1110 /* Skip holes if any. */
1112 while (JS_TEST_BIT(ii
->holes
, i
) && ++i
!= ii
->length
)
1115 if (i
!= ii
->length
) {
1117 return js_IndexToId(cx
, i
, idp
);
1123 case JSENUMERATE_DESTROY
:
1124 if (JSVAL_TAG(*statep
) != JSVAL_BOOLEAN
) {
1125 JS_ASSERT((*statep
& INDEX_ITER_TAG
) == INDEX_ITER_TAG
);
1126 ii
= (JSIndexIterState
*) (*statep
& ~INDEX_ITER_TAG
);
1129 *statep
= JSVAL_NULL
;
1136 slowarray_enumerate(JSContext
*cx
, JSObject
*obj
, JSIterateOp enum_op
,
1137 jsval
*statep
, jsid
*idp
)
1141 /* Are we continuing an enumeration that started when we were dense? */
1142 if (enum_op
!= JSENUMERATE_INIT
) {
1143 if (JSVAL_TAG(*statep
) == JSVAL_BOOLEAN
||
1144 (*statep
& INDEX_ITER_TAG
) == INDEX_ITER_TAG
) {
1145 return array_enumerate(cx
, obj
, enum_op
, statep
, idp
);
1147 JS_ASSERT((*statep
& INDEX_ITER_TAG
) == JSVAL_INT
);
1149 ok
= js_Enumerate(cx
, obj
, enum_op
, statep
, idp
);
1150 JS_ASSERT(*statep
== JSVAL_NULL
|| (*statep
& INDEX_ITER_TAG
) == JSVAL_INT
);
1155 array_finalize(JSContext
*cx
, JSObject
*obj
)
1158 JS_free(cx
, obj
->dslots
- 1);
1163 array_trace(JSTracer
*trc
, JSObject
*obj
)
1169 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx
, obj
));
1171 capacity
= js_DenseArrayCapacity(obj
);
1172 for (i
= 0; i
< capacity
; i
++) {
1174 if (JSVAL_IS_TRACEABLE(v
)) {
1175 JS_SET_TRACING_INDEX(trc
, "array_dslots", i
);
1176 JS_CallTracer(trc
, JSVAL_TO_TRACEABLE(v
), JSVAL_TRACE_KIND(v
));
1180 for (i
= JSSLOT_PROTO
; i
<= JSSLOT_PARENT
; ++i
) {
1181 v
= STOBJ_GET_SLOT(obj
, i
);
1182 if (JSVAL_IS_TRACEABLE(v
)) {
1183 JS_SET_TRACING_DETAILS(trc
, js_PrintObjectSlotName
, obj
, i
);
1184 JS_CallTracer(trc
, JSVAL_TO_TRACEABLE(v
), JSVAL_TRACE_KIND(v
));
1189 static JSObjectMap
*
1190 array_newObjectMap(JSContext
*cx
, jsrefcount nrefs
, JSObjectOps
*ops
,
1191 JSClass
*clasp
, JSObject
*obj
)
1194 extern JSClass js_ArrayClass
;
1195 extern JSObjectOps js_ArrayObjectOps
;
1197 JSObjectMap
*map
= (JSObjectMap
*) JS_malloc(cx
, sizeof(*map
));
1202 JS_ASSERT(ops
== &js_ArrayObjectOps
);
1204 JS_ASSERT(clasp
== &js_ArrayClass
);
1205 map
->freeslot
= JSSLOT_FREE(clasp
);
1211 array_destroyObjectMap(JSContext
*cx
, JSObjectMap
*map
)
1216 JSObjectOps js_ArrayObjectOps
= {
1217 array_newObjectMap
, array_destroyObjectMap
,
1218 array_lookupProperty
, array_defineProperty
,
1219 array_getProperty
, array_setProperty
,
1220 array_getAttributes
, array_setAttributes
,
1221 array_deleteProperty
, js_DefaultValue
,
1222 array_enumerate
, js_CheckAccess
,
1223 NULL
, array_dropProperty
,
1225 NULL
, js_HasInstance
,
1226 js_SetProtoOrParent
, js_SetProtoOrParent
,
1231 static JSObjectOps
*
1232 array_getObjectOps(JSContext
*cx
, JSClass
*clasp
)
1234 return &js_ArrayObjectOps
;
1237 JSClass js_ArrayClass
= {
1239 JSCLASS_HAS_PRIVATE
| JSCLASS_HAS_CACHED_PROTO(JSProto_Array
) |
1240 JSCLASS_HAS_RESERVED_SLOTS(1) | JSCLASS_NEW_ENUMERATE
,
1241 JS_PropertyStub
, JS_PropertyStub
, JS_PropertyStub
, JS_PropertyStub
,
1242 JS_EnumerateStub
, JS_ResolveStub
, js_TryValueOf
, array_finalize
,
1243 array_getObjectOps
, NULL
, NULL
, NULL
,
1244 NULL
, NULL
, NULL
, NULL
1247 JSClass js_SlowArrayClass
= {
1249 JSCLASS_HAS_PRIVATE
| JSCLASS_HAS_CACHED_PROTO(JSProto_Array
),
1250 slowarray_addProperty
, JS_PropertyStub
, JS_PropertyStub
, JS_PropertyStub
,
1251 JS_EnumerateStub
, JS_ResolveStub
, js_TryValueOf
, JS_FinalizeStub
,
1252 slowarray_getObjectOps
, NULL
, NULL
, NULL
,
1253 NULL
, NULL
, NULL
, NULL
1257 * Convert an array object from fast-and-dense to slow-and-flexible.
1260 js_MakeArraySlow(JSContext
*cx
, JSObject
*obj
)
1262 JSObjectMap
*map
, *oldmap
;
1265 JS_ASSERT(OBJ_GET_CLASS(cx
, obj
) == &js_ArrayClass
);
1267 /* Create a native scope. */
1268 map
= js_NewObjectMap(cx
, obj
->map
->nrefs
, &js_SlowArrayObjectOps
,
1269 &js_SlowArrayClass
, obj
);
1273 capacity
= js_DenseArrayCapacity(obj
);
1275 map
->freeslot
= STOBJ_NSLOTS(obj
) + JS_INITIAL_NSLOTS
;
1276 obj
->dslots
[-1] = JS_INITIAL_NSLOTS
+ capacity
;
1278 map
->freeslot
= STOBJ_NSLOTS(obj
);
1281 /* Create new properties pointing to existing values in dslots */
1282 for (i
= 0; i
< capacity
; i
++) {
1284 JSScopeProperty
*sprop
;
1286 if (!JS_ValueToId(cx
, INT_TO_JSVAL(i
), &id
))
1289 if (obj
->dslots
[i
] == JSVAL_HOLE
) {
1290 obj
->dslots
[i
] = JSVAL_VOID
;
1294 sprop
= js_AddScopeProperty(cx
, (JSScope
*)map
, id
, NULL
, NULL
,
1295 i
+ JS_INITIAL_NSLOTS
, JSPROP_ENUMERATE
,
1302 * Render our formerly-reserved count property GC-safe. If length fits in
1303 * a jsval, set our slow/sparse COUNT to the current length as a jsval, so
1304 * we can tell when only named properties have been added to a dense array
1305 * to make it slow-but-not-sparse.
1308 uint32 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
1309 obj
->fslots
[JSSLOT_ARRAY_COUNT
] = INT_FITS_IN_JSVAL(length
)
1310 ? INT_TO_JSVAL(length
)
1314 /* Make sure we preserve any flags borrowing bits in classword. */
1315 obj
->classword
^= (jsuword
) &js_ArrayClass
;
1316 obj
->classword
|= (jsuword
) &js_SlowArrayClass
;
1318 /* Swap in our new map. */
1321 array_destroyObjectMap(cx
, oldmap
);
1326 js_DestroyObjectMap(cx
, map
);
1330 enum ArrayToStringOp
{
1337 * When op is TO_STRING or TO_LOCALE_STRING sep indicates a separator to use
1338 * or "," when sep is NULL.
1339 * When op is TO_SOURCE sep must be NULL.
1342 array_join_sub(JSContext
*cx
, JSObject
*obj
, enum ArrayToStringOp op
,
1343 JSString
*sep
, jsval
*rval
)
1346 jsuint length
, index
;
1347 jschar
*chars
, *ochars
;
1348 size_t nchars
, growth
, seplen
, tmplen
, extratail
;
1349 const jschar
*sepstr
;
1354 JS_CHECK_RECURSION(cx
, return JS_FALSE
);
1356 ok
= js_GetLengthProperty(cx
, obj
, &length
);
1360 he
= js_EnterSharpObject(cx
, obj
, NULL
, &chars
);
1364 growth
= (size_t) -1;
1368 * We must check for the sharp bit and skip js_LeaveSharpObject when it is
1369 * set even when op is not TO_SOURCE. A script can overwrite the default
1370 * toSource implementation and trigger a call, for example, to the
1371 * toString method during serialization of the object graph (bug 369696).
1374 #if JS_HAS_SHARP_VARS
1375 nchars
= js_strlen(chars
);
1385 if (op
== TO_SOURCE
) {
1387 * Always allocate 2 extra chars for closing ']' and terminating 0
1388 * and then preallocate 1 + extratail to include starting '['.
1391 growth
= (1 + extratail
) * sizeof(jschar
);
1394 chars
= (jschar
*) malloc(growth
);
1399 nchars
= js_strlen(chars
);
1400 growth
+= nchars
* sizeof(jschar
);
1401 chars
= (jschar
*)realloc((ochars
= chars
), growth
);
1407 chars
[nchars
++] = '[';
1408 JS_ASSERT(sep
== NULL
);
1409 sepstr
= NULL
; /* indicates to use ", " as separator */
1413 * Free any sharp variable definition in chars. Normally, we would
1414 * MAKE_SHARP(he) so that only the first sharp variable annotation is
1415 * a definition, and all the rest are references, but in the current
1416 * case of (op != TO_SOURCE), we don't need chars at all.
1422 extratail
= 1; /* allocate extra char for terminating 0 */
1424 /* Return the empty string on a cycle as well as on empty join. */
1425 if (IS_BUSY(he
) || length
== 0) {
1426 js_LeaveSharpObject(cx
, NULL
);
1427 *rval
= JS_GetEmptyStringValue(cx
);
1431 /* Flag he as BUSY so we can distinguish a cycle from a join-point. */
1435 JSSTRING_CHARS_AND_LENGTH(sep
, sepstr
, seplen
);
1437 sepstr
= NULL
; /* indicates to use "," as separator */
1442 /* Use rval to locally root each element value as we loop and convert. */
1443 for (index
= 0; index
< length
; index
++) {
1444 ok
= (JS_CHECK_OPERATION_LIMIT(cx
) &&
1445 GetArrayElement(cx
, obj
, index
, &hole
, rval
));
1450 (JSVAL_IS_VOID(*rval
) || JSVAL_IS_NULL(*rval
)))) {
1451 str
= cx
->runtime
->emptyString
;
1453 if (op
== TO_LOCALE_STRING
) {
1456 atom
= cx
->runtime
->atomState
.toLocaleStringAtom
;
1457 ok
= js_ValueToObject(cx
, *rval
, &robj
);
1459 /* Re-use *rval to protect robj temporarily. */
1460 *rval
= OBJECT_TO_JSVAL(robj
);
1461 ok
= js_TryMethod(cx
, robj
, atom
, 0, NULL
, rval
);
1465 str
= js_ValueToString(cx
, *rval
);
1466 } else if (op
== TO_STRING
) {
1467 str
= js_ValueToString(cx
, *rval
);
1469 JS_ASSERT(op
== TO_SOURCE
);
1470 str
= js_ValueToSource(cx
, *rval
);
1479 * Do not append separator after the last element unless it is a hole
1480 * and we are in toSource. In that case we append single ",".
1482 if (index
+ 1 == length
)
1483 seplen
= (hole
&& op
== TO_SOURCE
) ? 1 : 0;
1485 /* Allocate 1 at end for closing bracket and zero. */
1486 tmplen
= JSSTRING_LENGTH(str
);
1487 growth
= nchars
+ tmplen
+ seplen
+ extratail
;
1488 if (nchars
> growth
|| tmplen
> growth
||
1489 growth
> (size_t)-1 / sizeof(jschar
)) {
1496 growth
*= sizeof(jschar
);
1498 chars
= (jschar
*) malloc(growth
);
1502 chars
= (jschar
*) realloc((ochars
= chars
), growth
);
1509 js_strncpy(&chars
[nchars
], JSSTRING_CHARS(str
), tmplen
);
1514 js_strncpy(&chars
[nchars
], sepstr
, seplen
);
1516 JS_ASSERT(seplen
== 1 || seplen
== 2);
1517 chars
[nchars
] = ',';
1519 chars
[nchars
+ 1] = ' ';
1526 if (op
== TO_SOURCE
) {
1528 chars
[nchars
++] = ']';
1532 js_LeaveSharpObject(cx
, NULL
);
1541 JS_ReportOutOfMemory(cx
);
1545 JS_ASSERT(growth
== (size_t)-1 || (nchars
+ 1) * sizeof(jschar
) == growth
);
1546 str
= js_NewString(cx
, chars
, nchars
);
1551 *rval
= STRING_TO_JSVAL(str
);
1557 array_toSource(JSContext
*cx
, uintN argc
, jsval
*vp
)
1561 obj
= JS_THIS_OBJECT(cx
, vp
);
1562 if (OBJ_GET_CLASS(cx
, obj
) != &js_SlowArrayClass
&&
1563 !JS_InstanceOf(cx
, obj
, &js_ArrayClass
, vp
+ 2)) {
1566 return array_join_sub(cx
, obj
, TO_SOURCE
, NULL
, vp
);
1571 array_toString(JSContext
*cx
, uintN argc
, jsval
*vp
)
1575 obj
= JS_THIS_OBJECT(cx
, vp
);
1576 if (OBJ_GET_CLASS(cx
, obj
) != &js_SlowArrayClass
&&
1577 !JS_InstanceOf(cx
, obj
, &js_ArrayClass
, vp
+ 2)) {
1580 return array_join_sub(cx
, obj
, TO_STRING
, NULL
, vp
);
1584 array_toLocaleString(JSContext
*cx
, uintN argc
, jsval
*vp
)
1588 obj
= JS_THIS_OBJECT(cx
, vp
);
1589 if (OBJ_GET_CLASS(cx
, obj
) != &js_SlowArrayClass
&&
1590 !JS_InstanceOf(cx
, obj
, &js_ArrayClass
, vp
+ 2)) {
1595 * Passing comma here as the separator. Need a way to get a
1596 * locale-specific version.
1598 return array_join_sub(cx
, obj
, TO_LOCALE_STRING
, NULL
, vp
);
1602 InitArrayElements(JSContext
*cx
, JSObject
*obj
, jsuint start
, jsuint count
, jsval
*vector
)
1604 JS_ASSERT(count
< MAXINDEX
);
1606 * Optimize for dense arrays so long as adding the given set of elements
1607 * wouldn't otherwise make the array slow.
1609 if (OBJ_IS_DENSE_ARRAY(cx
, obj
) && start
<= MAXINDEX
- count
&&
1610 !INDEX_TOO_BIG(start
+ count
)) {
1611 jsuint newlen
= start
+ count
;
1612 JS_ASSERT(jsdouble(start
) + count
== jsdouble(newlen
));
1613 if (!EnsureCapacity(cx
, obj
, newlen
))
1616 if (newlen
> uint32(obj
->fslots
[JSSLOT_ARRAY_LENGTH
]))
1617 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = newlen
;
1619 JS_ASSERT(count
< size_t(-1) / sizeof(jsval
));
1620 memcpy(obj
->dslots
+ start
, vector
, sizeof(jsval
) * count
);
1621 JS_ASSERT_IF(count
!= 0, obj
->dslots
[newlen
- 1] != JSVAL_HOLE
);
1625 jsval
* end
= vector
+ count
;
1626 while (vector
!= end
&& start
< MAXINDEX
) {
1627 if (!JS_CHECK_OPERATION_LIMIT(cx
) ||
1628 !SetArrayElement(cx
, obj
, start
++, *vector
++)) {
1636 /* Finish out any remaining elements past the max array index. */
1637 if (!ENSURE_SLOW_ARRAY(cx
, obj
))
1640 JS_ASSERT(start
== MAXINDEX
);
1641 jsval tmp
[2] = {JSVAL_NULL
, JSVAL_NULL
};
1642 jsdouble
* dp
= js_NewWeaklyRootedDouble(cx
, MAXINDEX
);
1645 tmp
[0] = DOUBLE_TO_JSVAL(dp
);
1646 JSAutoTempValueRooter(cx
, JS_ARRAY_LENGTH(tmp
), tmp
);
1647 JSAutoTempIdRooter
idr(cx
);
1650 if (!js_ValueToStringId(cx
, tmp
[0], idr
.addr()) ||
1651 !js_SetProperty(cx
, obj
, idr
.id(), &tmp
[1])) {
1655 } while (vector
!= end
);
1661 InitArrayObject(JSContext
*cx
, JSObject
*obj
, jsuint length
, jsval
*vector
,
1662 JSBool holey
= JS_FALSE
)
1664 JS_ASSERT(OBJ_IS_ARRAY(cx
, obj
));
1666 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = length
;
1669 if (!EnsureCapacity(cx
, obj
, length
))
1672 jsuint count
= length
;
1674 memcpy(obj
->dslots
, vector
, length
* sizeof (jsval
));
1676 for (jsuint i
= 0; i
< length
; i
++) {
1677 if (vector
[i
] == JSVAL_HOLE
)
1679 obj
->dslots
[i
] = vector
[i
];
1682 obj
->fslots
[JSSLOT_ARRAY_COUNT
] = count
;
1684 obj
->fslots
[JSSLOT_ARRAY_COUNT
] = 0;
1690 static JSString
* FASTCALL
1691 Array_p_join(JSContext
* cx
, JSObject
* obj
, JSString
*str
)
1693 JSAutoTempValueRooter
tvr(cx
);
1694 if (!array_join_sub(cx
, obj
, TO_STRING
, str
, tvr
.addr())) {
1695 cx
->builtinStatus
|= JSBUILTIN_ERROR
;
1698 return JSVAL_TO_STRING(tvr
.value());
1701 static JSString
* FASTCALL
1702 Array_p_toString(JSContext
* cx
, JSObject
* obj
)
1704 JSAutoTempValueRooter
tvr(cx
);
1705 if (!array_join_sub(cx
, obj
, TO_STRING
, NULL
, tvr
.addr())) {
1706 cx
->builtinStatus
|= JSBUILTIN_ERROR
;
1709 return JSVAL_TO_STRING(tvr
.value());
1714 * Perl-inspired join, reverse, and sort.
1717 array_join(JSContext
*cx
, uintN argc
, jsval
*vp
)
1722 if (argc
== 0 || JSVAL_IS_VOID(vp
[2])) {
1725 str
= js_ValueToString(cx
, vp
[2]);
1728 vp
[2] = STRING_TO_JSVAL(str
);
1730 obj
= JS_THIS_OBJECT(cx
, vp
);
1731 return obj
&& array_join_sub(cx
, obj
, TO_STRING
, str
, vp
);
1735 array_reverse(JSContext
*cx
, uintN argc
, jsval
*vp
)
1738 JSTempValueRooter tvr
;
1739 jsuint len
, half
, i
;
1740 JSBool ok
, hole
, hole2
;
1742 obj
= JS_THIS_OBJECT(cx
, vp
);
1743 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &len
))
1747 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
1749 for (i
= 0; i
< half
; i
++) {
1750 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
1751 GetArrayElement(cx
, obj
, i
, &hole
, &tvr
.u
.value
) &&
1752 GetArrayElement(cx
, obj
, len
- i
- 1, &hole2
, vp
) &&
1753 SetOrDeleteArrayElement(cx
, obj
, len
- i
- 1, hole
, tvr
.u
.value
) &&
1754 SetOrDeleteArrayElement(cx
, obj
, i
, hole2
, *vp
);
1758 JS_POP_TEMP_ROOT(cx
, &tvr
);
1760 *vp
= OBJECT_TO_JSVAL(obj
);
1764 typedef struct MSortArgs
{
1771 /* Helper function for js_MergeSort. */
1772 static JS_REQUIRES_STACK JSBool
1773 MergeArrays(MSortArgs
*msa
, void *src
, void *dest
, size_t run1
, size_t run2
)
1775 void *arg
, *a
, *b
, *c
;
1776 size_t elsize
, runtotal
;
1781 runtotal
= run1
+ run2
;
1783 elsize
= msa
->elsize
;
1786 fastcopy
= msa
->fastcopy
;
1788 #define CALL_CMP(a, b) \
1789 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1791 /* Copy runs already in sorted order. */
1792 b
= (char *)src
+ run1
* elsize
;
1793 a
= (char *)b
- elsize
;
1795 if (cmp_result
<= 0) {
1796 memcpy(dest
, src
, runtotal
* elsize
);
1800 #define COPY_ONE(p,q,n) \
1801 (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1805 for (; runtotal
!= 0; runtotal
--) {
1806 JSBool from_a
= run2
== 0;
1807 if (!from_a
&& run1
!= 0) {
1809 from_a
= cmp_result
<= 0;
1813 COPY_ONE(c
, a
, elsize
);
1815 a
= (char *)a
+ elsize
;
1817 COPY_ONE(c
, b
, elsize
);
1819 b
= (char *)b
+ elsize
;
1821 c
= (char *)c
+ elsize
;
1830 * This sort is stable, i.e. sequence of equal elements is preserved.
1831 * See also bug #224128.
1833 JS_REQUIRES_STACK JSBool
1834 js_MergeSort(void *src
, size_t nel
, size_t elsize
,
1835 JSComparator cmp
, void *arg
, void *tmp
)
1837 void *swap
, *vec1
, *vec2
;
1839 size_t i
, j
, lo
, hi
, run
;
1843 /* Avoid memcpy overhead for word-sized and word-aligned elements. */
1844 fastcopy
= (elsize
== sizeof(jsval
) &&
1845 (((jsuword
) src
| (jsuword
) tmp
) & JSVAL_ALIGN
) == 0);
1846 #define COPY_ONE(p,q,n) \
1847 (fastcopy ? (void)(*(jsval*)(p) = *(jsval*)(q)) : (void)memcpy(p, q, n))
1848 #define CALL_CMP(a, b) \
1849 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1850 #define INS_SORT_INT 4
1853 * Apply insertion sort to small chunks to reduce the number of merge
1856 for (lo
= 0; lo
< nel
; lo
+= INS_SORT_INT
) {
1857 hi
= lo
+ INS_SORT_INT
;
1860 for (i
= lo
+ 1; i
< hi
; i
++) {
1861 vec1
= (char *)src
+ i
* elsize
;
1862 vec2
= (char *)vec1
- elsize
;
1863 for (j
= i
; j
> lo
; j
--) {
1864 CALL_CMP(vec2
, vec1
);
1865 /* "<=" instead of "<" insures the sort is stable */
1866 if (cmp_result
<= 0) {
1870 /* Swap elements, using "tmp" as tmp storage */
1871 COPY_ONE(tmp
, vec2
, elsize
);
1872 COPY_ONE(vec2
, vec1
, elsize
);
1873 COPY_ONE(vec1
, tmp
, elsize
);
1875 vec2
= (char *)vec1
- elsize
;
1882 msa
.elsize
= elsize
;
1885 msa
.fastcopy
= fastcopy
;
1889 for (run
= INS_SORT_INT
; run
< nel
; run
*= 2) {
1890 for (lo
= 0; lo
< nel
; lo
+= 2 * run
) {
1893 memcpy((char *)vec2
+ lo
* elsize
, (char *)vec1
+ lo
* elsize
,
1894 (nel
- lo
) * elsize
);
1897 if (!MergeArrays(&msa
, (char *)vec1
+ lo
* elsize
,
1898 (char *)vec2
+ lo
* elsize
, run
,
1899 hi
+ run
> nel
? nel
- hi
: run
)) {
1908 memcpy(src
, tmp
, nel
* elsize
);
1913 typedef struct CompareArgs
{
1916 jsval
*elemroot
; /* stack needed for js_Invoke */
1919 static JS_REQUIRES_STACK JSBool
1920 sort_compare(void *arg
, const void *a
, const void *b
, int *result
)
1922 jsval av
= *(const jsval
*)a
, bv
= *(const jsval
*)b
;
1923 CompareArgs
*ca
= (CompareArgs
*) arg
;
1924 JSContext
*cx
= ca
->context
;
1925 jsval
*invokevp
, *sp
;
1929 * array_sort deals with holes and undefs on its own and they should not
1932 JS_ASSERT(!JSVAL_IS_VOID(av
));
1933 JS_ASSERT(!JSVAL_IS_VOID(bv
));
1935 if (!JS_CHECK_OPERATION_LIMIT(cx
))
1938 invokevp
= ca
->elemroot
;
1945 if (!js_Invoke(cx
, 2, invokevp
, 0))
1948 cmp
= js_ValueToNumber(cx
, invokevp
);
1949 if (JSVAL_IS_NULL(*invokevp
))
1952 /* Clamp cmp to -1, 0, 1. */
1954 if (!JSDOUBLE_IS_NaN(cmp
) && cmp
!= 0)
1955 *result
= cmp
> 0 ? 1 : -1;
1958 * XXX else report some kind of error here? ECMA talks about 'consistent
1959 * compare functions' that don't return NaN, but is silent about what the
1960 * result should be. So we currently ignore it.
1967 sort_compare_strings(void *arg
, const void *a
, const void *b
, int *result
)
1969 jsval av
= *(const jsval
*)a
, bv
= *(const jsval
*)b
;
1971 JS_ASSERT(JSVAL_IS_STRING(av
));
1972 JS_ASSERT(JSVAL_IS_STRING(bv
));
1973 if (!JS_CHECK_OPERATION_LIMIT((JSContext
*)arg
))
1976 *result
= (int) js_CompareStrings(JSVAL_TO_STRING(av
), JSVAL_TO_STRING(bv
));
1981 * The array_sort function below assumes JSVAL_NULL is zero in order to
1982 * perform initialization using memset. Other parts of SpiderMonkey likewise
1983 * "know" that JSVAL_NULL is zero; this static assertion covers all cases.
1985 JS_STATIC_ASSERT(JSVAL_NULL
== 0);
1987 static JS_REQUIRES_STACK JSBool
1988 array_sort(JSContext
*cx
, uintN argc
, jsval
*vp
)
1990 jsval
*argv
, fval
, *vec
, *mergesort_tmp
, v
;
1993 jsuint len
, newlen
, i
, undefs
;
1994 JSTempValueRooter tvr
;
2001 * Optimize the default compare function case if all of obj's elements
2002 * have values of type string.
2006 argv
= JS_ARGV(cx
, vp
);
2008 if (JSVAL_IS_PRIMITIVE(argv
[0])) {
2009 JS_ReportErrorNumber(cx
, js_GetErrorMessage
, NULL
,
2010 JSMSG_BAD_SORT_ARG
);
2013 fval
= argv
[0]; /* non-default compare function */
2018 obj
= JS_THIS_OBJECT(cx
, vp
);
2019 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &len
))
2022 *vp
= OBJECT_TO_JSVAL(obj
);
2027 * We need a temporary array of 2 * len jsvals to hold the array elements
2028 * and the scratch space for merge sort. Check that its size does not
2029 * overflow size_t, which would allow for indexing beyond the end of the
2032 #if JS_BITS_PER_WORD == 32
2033 if ((size_t)len
> ~(size_t)0 / (2 * sizeof(jsval
))) {
2034 js_ReportAllocationOverflow(cx
);
2038 vec
= (jsval
*) JS_malloc(cx
, 2 * (size_t) len
* sizeof(jsval
));
2043 * Initialize vec as a root. We will clear elements of vec one by
2044 * one while increasing tvr.count when we know that the property at
2045 * the corresponding index exists and its value must be rooted.
2047 * In this way when sorting a huge mostly sparse array we will not
2048 * access the tail of vec corresponding to properties that do not
2049 * exist, allowing OS to avoiding committing RAM. See bug 330812.
2051 * After this point control must flow through label out: to exit.
2053 JS_PUSH_TEMP_ROOT(cx
, 0, vec
, &tvr
);
2056 * By ECMA 262, 15.4.4.11, a property that does not exist (which we
2057 * call a "hole") is always greater than an existing property with
2058 * value undefined and that is always greater than any other property.
2059 * Thus to sort holes and undefs we simply count them, sort the rest
2060 * of elements, append undefs after them and then make holes after
2065 all_strings
= JS_TRUE
;
2066 for (i
= 0; i
< len
; i
++) {
2067 ok
= JS_CHECK_OPERATION_LIMIT(cx
);
2071 /* Clear vec[newlen] before including it in the rooted set. */
2072 vec
[newlen
] = JSVAL_NULL
;
2073 tvr
.count
= newlen
+ 1;
2074 ok
= GetArrayElement(cx
, obj
, i
, &hole
, &vec
[newlen
]);
2081 if (JSVAL_IS_VOID(vec
[newlen
])) {
2086 /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
2087 all_strings
&= JSVAL_IS_STRING(vec
[newlen
]);
2093 /* The array has only holes and undefs. */
2099 * The first newlen elements of vec are copied from the array object
2100 * (above). The remaining newlen positions are used as GC-rooted scratch
2101 * space for mergesort. We must clear the space before including it to
2102 * the root set covered by tvr.count. We assume JSVAL_NULL==0 to optimize
2103 * initialization using memset.
2105 mergesort_tmp
= vec
+ newlen
;
2106 memset(mergesort_tmp
, 0, newlen
* sizeof(jsval
));
2107 tvr
.count
= newlen
* 2;
2109 /* Here len == 2 * (newlen + undefs + number_of_holes). */
2110 if (fval
== JSVAL_NULL
) {
2112 * Sort using the default comparator converting all elements to
2116 elemsize
= sizeof(jsval
);
2119 * To avoid string conversion on each compare we do it only once
2120 * prior to sorting. But we also need the space for the original
2121 * values to recover the sorting result. To reuse
2122 * sort_compare_strings we move the original values to the odd
2123 * indexes in vec, put the string conversion results in the even
2124 * indexes and pass 2 * sizeof(jsval) as an element size to the
2125 * sorting function. In this way sort_compare_strings will only
2126 * see the string values when it casts the compare arguments as
2127 * pointers to jsval.
2129 * This requires doubling the temporary storage including the
2130 * scratch space for the merge sort. Since vec already contains
2131 * the rooted scratch space for newlen elements at the tail, we
2132 * can use it to rearrange and convert to strings first and try
2133 * realloc only when we know that we successfully converted all
2136 #if JS_BITS_PER_WORD == 32
2137 if ((size_t)newlen
> ~(size_t)0 / (4 * sizeof(jsval
))) {
2138 js_ReportAllocationOverflow(cx
);
2145 * Rearrange and string-convert the elements of the vector from
2146 * the tail here and, after sorting, move the results back
2147 * starting from the start to prevent overwrite the existing
2153 ok
= JS_CHECK_OPERATION_LIMIT(cx
);
2157 str
= js_ValueToString(cx
, v
);
2162 vec
[2 * i
] = STRING_TO_JSVAL(str
);
2166 JS_ASSERT(tvr
.u
.array
== vec
);
2167 vec
= (jsval
*) JS_realloc(cx
, vec
,
2168 4 * (size_t) newlen
* sizeof(jsval
));
2175 mergesort_tmp
= vec
+ 2 * newlen
;
2176 memset(mergesort_tmp
, 0, newlen
* 2 * sizeof(jsval
));
2177 tvr
.count
= newlen
* 4;
2178 elemsize
= 2 * sizeof(jsval
);
2180 ok
= js_MergeSort(vec
, (size_t) newlen
, elemsize
,
2181 sort_compare_strings
, cx
, mergesort_tmp
);
2186 * We want to make the following loop fast and to unroot the
2187 * cached results of toString invocations before the operation
2188 * callback has a chance to run the GC. For this reason we do
2189 * not call JS_CHECK_OPERATION_LIMIT in the loop.
2193 vec
[i
] = vec
[2 * i
+ 1];
2194 } while (++i
!= newlen
);
2201 ca
.elemroot
= js_AllocStack(cx
, 2 + 2, &mark
);
2206 ok
= js_MergeSort(vec
, (size_t) newlen
, sizeof(jsval
),
2207 sort_compare
, &ca
, mergesort_tmp
);
2208 js_FreeStack(cx
, mark
);
2214 * We no longer need to root the scratch space for the merge sort, so
2215 * unroot it now to make the job of a potential GC under InitArrayElements
2219 ok
= InitArrayElements(cx
, obj
, 0, newlen
, vec
);
2224 JS_POP_TEMP_ROOT(cx
, &tvr
);
2229 /* Set undefs that sorted after the rest of elements. */
2230 while (undefs
!= 0) {
2232 if (!JS_CHECK_OPERATION_LIMIT(cx
) ||
2233 !SetArrayElement(cx
, obj
, newlen
++, JSVAL_VOID
)) {
2238 /* Re-create any holes that sorted to the end of the array. */
2239 while (len
> newlen
) {
2240 if (!JS_CHECK_OPERATION_LIMIT(cx
) ||
2241 !DeleteArrayElement(cx
, obj
, --len
)) {
2245 *vp
= OBJECT_TO_JSVAL(obj
);
2250 * Perl-inspired push, pop, shift, unshift, and splice methods.
2253 array_push_slowly(JSContext
*cx
, JSObject
*obj
, uintN argc
, jsval
*argv
, jsval
*rval
)
2257 if (!js_GetLengthProperty(cx
, obj
, &length
))
2259 if (!InitArrayElements(cx
, obj
, length
, argc
, argv
))
2262 /* Per ECMA-262, return the new array length. */
2263 jsdouble newlength
= length
+ jsdouble(argc
);
2264 if (!IndexToValue(cx
, newlength
, rval
))
2266 return js_SetLengthProperty(cx
, obj
, newlength
);
2270 array_push1_dense(JSContext
* cx
, JSObject
* obj
, jsval v
, jsval
*rval
)
2272 uint32 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
2273 if (INDEX_TOO_SPARSE(obj
, length
)) {
2274 if (!js_MakeArraySlow(cx
, obj
))
2276 return array_push_slowly(cx
, obj
, 1, &v
, rval
);
2279 if (!EnsureCapacity(cx
, obj
, length
+ 1))
2281 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = length
+ 1;
2283 JS_ASSERT(obj
->dslots
[length
] == JSVAL_HOLE
);
2284 obj
->fslots
[JSSLOT_ARRAY_COUNT
]++;
2285 obj
->dslots
[length
] = v
;
2286 return IndexToValue(cx
, obj
->fslots
[JSSLOT_ARRAY_LENGTH
], rval
);
2290 js_ArrayCompPush(JSContext
*cx
, JSObject
*obj
, jsval v
)
2292 JS_ASSERT(OBJ_IS_DENSE_ARRAY(cx
, obj
));
2293 uint32_t length
= (uint32_t) obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
2294 JS_ASSERT(length
<= js_DenseArrayCapacity(obj
));
2296 if (length
== js_DenseArrayCapacity(obj
)) {
2297 if (length
>= ARRAY_INIT_LIMIT
) {
2298 JS_ReportErrorNumberUC(cx
, js_GetErrorMessage
, NULL
,
2299 JSMSG_ARRAY_INIT_TOO_BIG
);
2303 if (!EnsureCapacity(cx
, obj
, length
+ 1))
2306 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = length
+ 1;
2307 obj
->fslots
[JSSLOT_ARRAY_COUNT
]++;
2308 obj
->dslots
[length
] = v
;
2313 static jsval FASTCALL
2314 Array_p_push1(JSContext
* cx
, JSObject
* obj
, jsval v
)
2316 JSAutoTempValueRooter
tvr(cx
, v
);
2317 if (OBJ_IS_DENSE_ARRAY(cx
, obj
)
2318 ? array_push1_dense(cx
, obj
, v
, tvr
.addr())
2319 : array_push_slowly(cx
, obj
, 1, tvr
.addr(), tvr
.addr())) {
2322 cx
->builtinStatus
|= JSBUILTIN_ERROR
;
2328 array_push(JSContext
*cx
, uintN argc
, jsval
*vp
)
2332 /* Insist on one argument and obj of the expected class. */
2333 obj
= JS_THIS_OBJECT(cx
, vp
);
2336 if (argc
!= 1 || !OBJ_IS_DENSE_ARRAY(cx
, obj
))
2337 return array_push_slowly(cx
, obj
, argc
, vp
+ 2, vp
);
2339 return array_push1_dense(cx
, obj
, vp
[2], vp
);
2343 array_pop_slowly(JSContext
*cx
, JSObject
* obj
, jsval
*vp
)
2348 if (!js_GetLengthProperty(cx
, obj
, &index
))
2355 /* Get the to-be-deleted property's value into vp. */
2356 if (!GetArrayElement(cx
, obj
, index
, &hole
, vp
))
2358 if (!hole
&& !DeleteArrayElement(cx
, obj
, index
))
2361 return js_SetLengthProperty(cx
, obj
, index
);
2365 array_pop_dense(JSContext
*cx
, JSObject
* obj
, jsval
*vp
)
2370 index
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
2376 if (!GetArrayElement(cx
, obj
, index
, &hole
, vp
))
2378 if (!hole
&& !DeleteArrayElement(cx
, obj
, index
))
2380 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = index
;
2385 static jsval FASTCALL
2386 Array_p_pop(JSContext
* cx
, JSObject
* obj
)
2388 JSAutoTempValueRooter
tvr(cx
);
2389 if (OBJ_IS_DENSE_ARRAY(cx
, obj
)
2390 ? array_pop_dense(cx
, obj
, tvr
.addr())
2391 : array_pop_slowly(cx
, obj
, tvr
.addr())) {
2394 cx
->builtinStatus
|= JSBUILTIN_ERROR
;
2400 array_pop(JSContext
*cx
, uintN argc
, jsval
*vp
)
2404 obj
= JS_THIS_OBJECT(cx
, vp
);
2407 if (OBJ_IS_DENSE_ARRAY(cx
, obj
))
2408 return array_pop_dense(cx
, obj
, vp
);
2409 return array_pop_slowly(cx
, obj
, vp
);
2413 array_shift(JSContext
*cx
, uintN argc
, jsval
*vp
)
2418 JSTempValueRooter tvr
;
2420 obj
= JS_THIS_OBJECT(cx
, vp
);
2421 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &length
))
2428 /* Get the to-be-deleted property's value into vp ASAP. */
2429 if (!GetArrayElement(cx
, obj
, 0, &hole
, vp
))
2432 /* Slide down the array above the first element. */
2434 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
2435 for (i
= 0; i
!= length
; i
++) {
2436 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
2437 GetArrayElement(cx
, obj
, i
+ 1, &hole
, &tvr
.u
.value
) &&
2438 SetOrDeleteArrayElement(cx
, obj
, i
, hole
, tvr
.u
.value
);
2442 JS_POP_TEMP_ROOT(cx
, &tvr
);
2446 /* Delete the only or last element when it exist. */
2447 if (!hole
&& !DeleteArrayElement(cx
, obj
, length
))
2450 return js_SetLengthProperty(cx
, obj
, length
);
2454 array_unshift(JSContext
*cx
, uintN argc
, jsval
*vp
)
2460 JSTempValueRooter tvr
;
2461 jsdouble last
, newlen
;
2463 obj
= JS_THIS_OBJECT(cx
, vp
);
2464 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &length
))
2468 /* Slide up the array to make room for argc at the bottom. */
2469 argv
= JS_ARGV(cx
, vp
);
2473 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
2476 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
2477 GetArrayElement(cx
, obj
, last
, &hole
, &tvr
.u
.value
) &&
2478 SetOrDeleteArrayElement(cx
, obj
, last
+ argc
, hole
,
2482 } while (last
!= 0);
2483 JS_POP_TEMP_ROOT(cx
, &tvr
);
2488 /* Copy from argv to the bottom of the array. */
2489 if (!InitArrayElements(cx
, obj
, 0, argc
, argv
))
2493 if (!js_SetLengthProperty(cx
, obj
, newlen
))
2497 /* Follow Perl by returning the new array length. */
2498 return IndexToValue(cx
, newlen
, vp
);
2502 array_splice(JSContext
*cx
, uintN argc
, jsval
*vp
)
2506 jsuint length
, begin
, end
, count
, delta
, last
;
2510 JSTempValueRooter tvr
;
2513 * Create a new array value to return. Our ECMA v2 proposal specs
2514 * that splice always returns an array value, even when given no
2515 * arguments. We think this is best because it eliminates the need
2516 * for callers to do an extra test to handle the empty splice case.
2518 obj2
= js_NewArrayObject(cx
, 0, NULL
);
2521 *vp
= OBJECT_TO_JSVAL(obj2
);
2523 /* Nothing to do if no args. Otherwise get length. */
2526 argv
= JS_ARGV(cx
, vp
);
2527 obj
= JS_THIS_OBJECT(cx
, vp
);
2528 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &length
))
2531 /* Convert the first argument into a starting index. */
2532 d
= js_ValueToNumber(cx
, argv
);
2533 if (JSVAL_IS_NULL(*argv
))
2535 d
= js_DoubleToInteger(d
);
2540 } else if (d
> length
) {
2543 begin
= (jsuint
)d
; /* d has been clamped to uint32 */
2547 /* Convert the second argument from a count into a fencepost index. */
2548 delta
= length
- begin
;
2553 d
= js_ValueToNumber(cx
, argv
);
2554 if (JSVAL_IS_NULL(*argv
))
2556 d
= js_DoubleToInteger(d
);
2562 end
= begin
+ count
;
2567 MUST_FLOW_THROUGH("out");
2568 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
2570 /* If there are elements to remove, put them into the return value. */
2572 for (last
= begin
; last
< end
; last
++) {
2573 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
2574 GetArrayElement(cx
, obj
, last
, &hole
, &tvr
.u
.value
);
2578 /* Copy tvr.u.value to new array unless it's a hole. */
2580 ok
= SetArrayElement(cx
, obj2
, last
- begin
, tvr
.u
.value
);
2586 ok
= js_SetLengthProperty(cx
, obj2
, end
- begin
);
2591 /* Find the direction (up or down) to copy and make way for argv. */
2593 delta
= (jsuint
)argc
- count
;
2595 /* (uint) end could be 0, so can't use vanilla >= test */
2596 while (last
-- > end
) {
2597 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
2598 GetArrayElement(cx
, obj
, last
, &hole
, &tvr
.u
.value
) &&
2599 SetOrDeleteArrayElement(cx
, obj
, last
+ delta
, hole
,
2605 } else if (argc
< count
) {
2606 delta
= count
- (jsuint
)argc
;
2607 for (last
= end
; last
< length
; last
++) {
2608 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
2609 GetArrayElement(cx
, obj
, last
, &hole
, &tvr
.u
.value
) &&
2610 SetOrDeleteArrayElement(cx
, obj
, last
- delta
, hole
,
2618 /* Copy from argv into the hole to complete the splice. */
2619 ok
= InitArrayElements(cx
, obj
, begin
, argc
, argv
);
2623 /* Update length in case we deleted elements from the end. */
2624 ok
= js_SetLengthProperty(cx
, obj
, length
);
2627 JS_POP_TEMP_ROOT(cx
, &tvr
);
2632 * Python-esque sequence operations.
2635 array_concat(JSContext
*cx
, uintN argc
, jsval
*vp
)
2638 JSObject
*aobj
, *nobj
;
2639 jsuint length
, alength
, slot
;
2642 JSTempValueRooter tvr
;
2644 /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
2645 argv
= JS_ARGV(cx
, vp
) - 1;
2646 JS_ASSERT(JS_THIS_OBJECT(cx
, vp
) == JSVAL_TO_OBJECT(argv
[0]));
2648 /* Create a new Array object and root it using *vp. */
2649 aobj
= JS_THIS_OBJECT(cx
, vp
);
2650 if (OBJ_IS_DENSE_ARRAY(cx
, aobj
)) {
2652 * Clone aobj but pass the minimum of its length and capacity, to
2653 * handle a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In
2654 * such a case we'll pass 8 (not 3) due to ARRAY_CAPACITY_MIN, which
2655 * will cause nobj to be over-allocated to 16. But in the normal case
2656 * where length is <= capacity, nobj and aobj will have the same
2659 length
= aobj
->fslots
[JSSLOT_ARRAY_LENGTH
];
2660 jsuint capacity
= js_DenseArrayCapacity(aobj
);
2661 nobj
= js_NewArrayObject(cx
, JS_MIN(length
, capacity
), aobj
->dslots
,
2662 aobj
->fslots
[JSSLOT_ARRAY_COUNT
] !=
2666 nobj
->fslots
[JSSLOT_ARRAY_LENGTH
] = length
;
2667 *vp
= OBJECT_TO_JSVAL(nobj
);
2673 nobj
= js_NewArrayObject(cx
, 0, NULL
);
2676 *vp
= OBJECT_TO_JSVAL(nobj
);
2680 MUST_FLOW_THROUGH("out");
2681 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
2683 /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
2684 for (i
= 0; i
<= argc
; i
++) {
2685 ok
= JS_CHECK_OPERATION_LIMIT(cx
);
2689 if (!JSVAL_IS_PRIMITIVE(v
)) {
2692 aobj
= JSVAL_TO_OBJECT(v
);
2693 wobj
= js_GetWrappedObject(cx
, aobj
);
2694 if (OBJ_IS_ARRAY(cx
, wobj
)) {
2695 ok
= OBJ_GET_PROPERTY(cx
, aobj
,
2696 ATOM_TO_JSID(cx
->runtime
->atomState
2701 alength
= ValueIsLength(cx
, &tvr
.u
.value
);
2702 ok
= !JSVAL_IS_NULL(tvr
.u
.value
);
2705 for (slot
= 0; slot
< alength
; slot
++) {
2706 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
2707 GetArrayElement(cx
, aobj
, slot
, &hole
,
2713 * Per ECMA 262, 15.4.4.4, step 9, ignore non-existent
2717 ok
= SetArrayElement(cx
, nobj
, length
+ slot
,
2728 ok
= SetArrayElement(cx
, nobj
, length
, v
);
2734 ok
= js_SetLengthProperty(cx
, nobj
, length
);
2737 JS_POP_TEMP_ROOT(cx
, &tvr
);
2742 array_slice(JSContext
*cx
, uintN argc
, jsval
*vp
)
2745 JSObject
*nobj
, *obj
;
2746 jsuint length
, begin
, end
, slot
;
2749 JSTempValueRooter tvr
;
2751 argv
= JS_ARGV(cx
, vp
);
2753 obj
= JS_THIS_OBJECT(cx
, vp
);
2754 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &length
))
2760 d
= js_ValueToNumber(cx
, &argv
[0]);
2761 if (JSVAL_IS_NULL(argv
[0]))
2763 d
= js_DoubleToInteger(d
);
2768 } else if (d
> length
) {
2774 d
= js_ValueToNumber(cx
, &argv
[1]);
2775 if (JSVAL_IS_NULL(argv
[1]))
2777 d
= js_DoubleToInteger(d
);
2782 } else if (d
> length
) {
2792 if (OBJ_IS_DENSE_ARRAY(cx
, obj
) && end
<= js_DenseArrayCapacity(obj
)) {
2793 nobj
= js_NewArrayObject(cx
, end
- begin
, obj
->dslots
+ begin
,
2794 obj
->fslots
[JSSLOT_ARRAY_COUNT
] !=
2795 obj
->fslots
[JSSLOT_ARRAY_LENGTH
]);
2798 *vp
= OBJECT_TO_JSVAL(nobj
);
2802 /* Create a new Array object and root it using *vp. */
2803 nobj
= js_NewArrayObject(cx
, 0, NULL
);
2806 *vp
= OBJECT_TO_JSVAL(nobj
);
2808 MUST_FLOW_THROUGH("out");
2809 JS_PUSH_SINGLE_TEMP_ROOT(cx
, JSVAL_NULL
, &tvr
);
2811 for (slot
= begin
; slot
< end
; slot
++) {
2812 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
2813 GetArrayElement(cx
, obj
, slot
, &hole
, &tvr
.u
.value
);
2817 ok
= SetArrayElement(cx
, nobj
, slot
- begin
, tvr
.u
.value
);
2822 ok
= js_SetLengthProperty(cx
, nobj
, end
- begin
);
2825 JS_POP_TEMP_ROOT(cx
, &tvr
);
2829 #if JS_HAS_ARRAY_EXTRAS
2832 array_indexOfHelper(JSContext
*cx
, JSBool isLast
, uintN argc
, jsval
*vp
)
2835 jsuint length
, i
, stop
;
2840 obj
= JS_THIS_OBJECT(cx
, vp
);
2841 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &length
))
2847 i
= isLast
? length
- 1 : 0;
2848 tosearch
= (argc
!= 0) ? vp
[2] : JSVAL_VOID
;
2853 start
= js_ValueToNumber(cx
, &vp
[3]);
2854 if (JSVAL_IS_NULL(vp
[3]))
2856 start
= js_DoubleToInteger(start
);
2866 } else if (start
>= length
) {
2884 if (!JS_CHECK_OPERATION_LIMIT(cx
) ||
2885 !GetArrayElement(cx
, obj
, (jsuint
)i
, &hole
, vp
)) {
2888 if (!hole
&& js_StrictlyEqual(cx
, *vp
, tosearch
))
2889 return js_NewNumberInRootedValue(cx
, i
, vp
);
2896 *vp
= INT_TO_JSVAL(-1);
2901 array_indexOf(JSContext
*cx
, uintN argc
, jsval
*vp
)
2903 return array_indexOfHelper(cx
, JS_FALSE
, argc
, vp
);
2907 array_lastIndexOf(JSContext
*cx
, uintN argc
, jsval
*vp
)
2909 return array_indexOfHelper(cx
, JS_TRUE
, argc
, vp
);
2912 /* Order is important; extras that take a predicate funarg must follow MAP. */
2913 typedef enum ArrayExtraMode
{
2923 #define REDUCE_MODE(mode) ((mode) == REDUCE || (mode) == REDUCE_RIGHT)
2925 static JS_REQUIRES_STACK JSBool
2926 array_extra(JSContext
*cx
, ArrayExtraMode mode
, uintN argc
, jsval
*vp
)
2929 jsuint length
, newlen
;
2930 jsval
*argv
, *elemroot
, *invokevp
, *sp
;
2931 JSBool ok
, cond
, hole
;
2932 JSObject
*callable
, *thisp
, *newarr
;
2933 jsint start
, end
, step
, i
;
2936 obj
= JS_THIS_OBJECT(cx
, vp
);
2937 if (!obj
|| !js_GetLengthProperty(cx
, obj
, &length
))
2941 * First, get or compute our callee, so that we error out consistently
2942 * when passed a non-callable object.
2945 js_ReportMissingArg(cx
, vp
, 0);
2949 callable
= js_ValueToCallableObject(cx
, &argv
[0], JSV2F_SEARCH_STACK
);
2954 * Set our initial return condition, used for zero-length array cases
2955 * (and pre-size our map return to match our known length, for all cases).
2957 #ifdef __GNUC__ /* quell GCC overwarning */
2961 start
= 0, end
= length
, step
= 1;
2965 start
= length
- 1, end
= -1, step
= -1;
2968 if (length
== 0 && argc
== 1) {
2969 JS_ReportErrorNumber(cx
, js_GetErrorMessage
, NULL
,
2970 JSMSG_EMPTY_ARRAY_REDUCE
);
2977 if (!GetArrayElement(cx
, obj
, start
, &hole
, vp
))
2980 } while (hole
&& start
!= end
);
2982 if (hole
&& start
== end
) {
2983 JS_ReportErrorNumber(cx
, js_GetErrorMessage
, NULL
,
2984 JSMSG_EMPTY_ARRAY_REDUCE
);
2991 newlen
= (mode
== MAP
) ? length
: 0;
2992 newarr
= js_NewArrayObject(cx
, newlen
, NULL
);
2995 *vp
= OBJECT_TO_JSVAL(newarr
);
3011 if (argc
> 1 && !REDUCE_MODE(mode
)) {
3012 if (!js_ValueToObject(cx
, argv
[1], &thisp
))
3014 argv
[1] = OBJECT_TO_JSVAL(thisp
);
3020 * For all but REDUCE, we call with 3 args (value, index, array). REDUCE
3021 * requires 4 args (accum, value, index, array).
3023 argc
= 3 + REDUCE_MODE(mode
);
3024 elemroot
= js_AllocStack(cx
, 1 + 2 + argc
, &mark
);
3028 MUST_FLOW_THROUGH("out");
3030 invokevp
= elemroot
+ 1;
3032 for (i
= start
; i
!= end
; i
+= step
) {
3033 ok
= JS_CHECK_OPERATION_LIMIT(cx
) &&
3034 GetArrayElement(cx
, obj
, i
, &hole
, elemroot
);
3041 * Push callable and 'this', then args. We must do this for every
3042 * iteration around the loop since js_Invoke uses spbase[0] for return
3043 * value storage, while some native functions use spbase[1] for local
3047 *sp
++ = OBJECT_TO_JSVAL(callable
);
3048 *sp
++ = OBJECT_TO_JSVAL(thisp
);
3049 if (REDUCE_MODE(mode
))
3052 *sp
++ = INT_TO_JSVAL(i
);
3053 *sp
++ = OBJECT_TO_JSVAL(obj
);
3056 ok
= js_Invoke(cx
, argc
, invokevp
, 0);
3061 cond
= js_ValueToBoolean(*invokevp
);
3062 #ifdef __GNUC__ /* quell GCC overwarning */
3075 ok
= SetArrayElement(cx
, newarr
, i
, *invokevp
);
3082 /* The filter passed *elemroot, so push it onto our result. */
3083 ok
= SetArrayElement(cx
, newarr
, newlen
++, *elemroot
);
3103 js_FreeStack(cx
, mark
);
3104 if (ok
&& mode
== FILTER
)
3105 ok
= js_SetLengthProperty(cx
, newarr
, newlen
);
3109 static JS_REQUIRES_STACK JSBool
3110 array_forEach(JSContext
*cx
, uintN argc
, jsval
*vp
)
3112 return array_extra(cx
, FOREACH
, argc
, vp
);
3115 static JS_REQUIRES_STACK JSBool
3116 array_map(JSContext
*cx
, uintN argc
, jsval
*vp
)
3118 return array_extra(cx
, MAP
, argc
, vp
);
3121 static JS_REQUIRES_STACK JSBool
3122 array_reduce(JSContext
*cx
, uintN argc
, jsval
*vp
)
3124 return array_extra(cx
, REDUCE
, argc
, vp
);
3127 static JS_REQUIRES_STACK JSBool
3128 array_reduceRight(JSContext
*cx
, uintN argc
, jsval
*vp
)
3130 return array_extra(cx
, REDUCE_RIGHT
, argc
, vp
);
3133 static JS_REQUIRES_STACK JSBool
3134 array_filter(JSContext
*cx
, uintN argc
, jsval
*vp
)
3136 return array_extra(cx
, FILTER
, argc
, vp
);
3139 static JS_REQUIRES_STACK JSBool
3140 array_some(JSContext
*cx
, uintN argc
, jsval
*vp
)
3142 return array_extra(cx
, SOME
, argc
, vp
);
3145 static JS_REQUIRES_STACK JSBool
3146 array_every(JSContext
*cx
, uintN argc
, jsval
*vp
)
3148 return array_extra(cx
, EVERY
, argc
, vp
);
3152 static JSPropertySpec array_props
[] = {
3153 {js_length_str
, -1, JSPROP_SHARED
| JSPROP_PERMANENT
,
3154 array_length_getter
, array_length_setter
},
3158 JS_DEFINE_TRCINFO_1(array_toString
,
3159 (2, (static, STRING_FAIL
, Array_p_toString
, CONTEXT
, THIS
, 0, 0)))
3160 JS_DEFINE_TRCINFO_1(array_join
,
3161 (3, (static, STRING_FAIL
, Array_p_join
, CONTEXT
, THIS
, STRING
, 0, 0)))
3162 JS_DEFINE_TRCINFO_1(array_push
,
3163 (3, (static, JSVAL_FAIL
, Array_p_push1
, CONTEXT
, THIS
, JSVAL
, 0, 0)))
3164 JS_DEFINE_TRCINFO_1(array_pop
,
3165 (2, (static, JSVAL_FAIL
, Array_p_pop
, CONTEXT
, THIS
, 0, 0)))
3167 static JSFunctionSpec array_methods
[] = {
3169 JS_FN(js_toSource_str
, array_toSource
, 0,0),
3171 JS_TN(js_toString_str
, array_toString
, 0,0, array_toString_trcinfo
),
3172 JS_FN(js_toLocaleString_str
,array_toLocaleString
,0,0),
3174 /* Perl-ish methods. */
3175 JS_TN("join", array_join
, 1,JSFUN_GENERIC_NATIVE
, array_join_trcinfo
),
3176 JS_FN("reverse", array_reverse
, 0,JSFUN_GENERIC_NATIVE
),
3177 JS_FN("sort", array_sort
, 1,JSFUN_GENERIC_NATIVE
),
3178 JS_TN("push", array_push
, 1,JSFUN_GENERIC_NATIVE
, array_push_trcinfo
),
3179 JS_TN("pop", array_pop
, 0,JSFUN_GENERIC_NATIVE
, array_pop_trcinfo
),
3180 JS_FN("shift", array_shift
, 0,JSFUN_GENERIC_NATIVE
),
3181 JS_FN("unshift", array_unshift
, 1,JSFUN_GENERIC_NATIVE
),
3182 JS_FN("splice", array_splice
, 2,JSFUN_GENERIC_NATIVE
),
3184 /* Pythonic sequence methods. */
3185 JS_FN("concat", array_concat
, 1,JSFUN_GENERIC_NATIVE
),
3186 JS_FN("slice", array_slice
, 2,JSFUN_GENERIC_NATIVE
),
3188 #if JS_HAS_ARRAY_EXTRAS
3189 JS_FN("indexOf", array_indexOf
, 1,JSFUN_GENERIC_NATIVE
),
3190 JS_FN("lastIndexOf", array_lastIndexOf
, 1,JSFUN_GENERIC_NATIVE
),
3191 JS_FN("forEach", array_forEach
, 1,JSFUN_GENERIC_NATIVE
),
3192 JS_FN("map", array_map
, 1,JSFUN_GENERIC_NATIVE
),
3193 JS_FN("reduce", array_reduce
, 1,JSFUN_GENERIC_NATIVE
),
3194 JS_FN("reduceRight", array_reduceRight
, 1,JSFUN_GENERIC_NATIVE
),
3195 JS_FN("filter", array_filter
, 1,JSFUN_GENERIC_NATIVE
),
3196 JS_FN("some", array_some
, 1,JSFUN_GENERIC_NATIVE
),
3197 JS_FN("every", array_every
, 1,JSFUN_GENERIC_NATIVE
),
3204 js_Array(JSContext
*cx
, JSObject
*obj
, uintN argc
, jsval
*argv
, jsval
*rval
)
3209 /* If called without new, replace obj with a new Array object. */
3210 if (!JS_IsConstructing(cx
)) {
3211 obj
= js_NewObject(cx
, &js_ArrayClass
, NULL
, NULL
, 0);
3214 *rval
= OBJECT_TO_JSVAL(obj
);
3220 } else if (argc
> 1) {
3221 length
= (jsuint
) argc
;
3223 } else if (!JSVAL_IS_NUMBER(argv
[0])) {
3227 length
= ValueIsLength(cx
, &argv
[0]);
3228 if (JSVAL_IS_NULL(argv
[0]))
3232 return InitArrayObject(cx
, obj
, length
, vector
);
3235 JS_STATIC_ASSERT(JSSLOT_PRIVATE
== JSSLOT_ARRAY_LENGTH
);
3236 JS_STATIC_ASSERT(JSSLOT_ARRAY_LENGTH
+ 1 == JSSLOT_ARRAY_COUNT
);
3241 js_FastNewArray(JSContext
* cx
, JSObject
* proto
)
3243 JS_ASSERT(OBJ_IS_ARRAY(cx
, proto
));
3245 JS_ASSERT(JS_ON_TRACE(cx
));
3246 JSObject
* obj
= (JSObject
*) js_NewGCThing(cx
, GCX_OBJECT
, sizeof(JSObject
));
3250 JSClass
* clasp
= &js_ArrayClass
;
3251 obj
->classword
= jsuword(clasp
);
3253 obj
->fslots
[JSSLOT_PROTO
] = OBJECT_TO_JSVAL(proto
);
3254 obj
->fslots
[JSSLOT_PARENT
] = proto
->fslots
[JSSLOT_PARENT
];
3256 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = 0;
3257 obj
->fslots
[JSSLOT_ARRAY_COUNT
] = 0;
3258 for (unsigned i
= JSSLOT_ARRAY_COUNT
+ 1; i
!= JS_INITIAL_NSLOTS
; ++i
)
3259 obj
->fslots
[i
] = JSVAL_VOID
;
3261 JSObjectOps
* ops
= clasp
->getObjectOps(cx
, clasp
);
3262 obj
->map
= ops
->newObjectMap(cx
, 1, ops
, clasp
, obj
);
3270 js_FastNewArrayWithLength(JSContext
* cx
, JSObject
* proto
, uint32 i
)
3272 JS_ASSERT(JS_ON_TRACE(cx
));
3273 JSObject
* obj
= js_FastNewArray(cx
, proto
);
3275 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = i
;
3280 js_NewUninitializedArray(JSContext
* cx
, JSObject
* proto
, uint32 len
)
3282 JSObject
*obj
= js_FastNewArrayWithLength(cx
, proto
, len
);
3283 if (!obj
|| !ResizeSlots(cx
, obj
, 0, JS_MAX(len
, ARRAY_CAPACITY_MIN
)))
3288 #define ARRAY_CTOR_GUTS(exact_len, newslots_code) \
3289 JS_ASSERT(JS_ON_TRACE(cx)); \
3290 JSObject* obj = js_FastNewArray(cx, proto); \
3292 const uint32 len = ARRAY_CAPACITY_MIN; \
3293 jsval* newslots = (jsval*) JS_malloc(cx, sizeof (jsval) * (len + 1)); \
3295 obj->dslots = newslots + 1; \
3296 js_SetDenseArrayCapacity(obj, len); \
3298 while (++newslots < obj->dslots + len) \
3299 *newslots = JSVAL_HOLE; \
3300 obj->fslots[JSSLOT_ARRAY_LENGTH] = (exact_len); \
3307 js_Array_1str(JSContext
* cx
, JSObject
* proto
, JSString
*str
)
3309 ARRAY_CTOR_GUTS(1, *++newslots
= STRING_TO_JSVAL(str
);)
3312 #endif /* JS_TRACER */
3315 js_InitArrayClass(JSContext
*cx
, JSObject
*obj
)
3319 /* Initialize the ops structure used by slow arrays */
3320 memcpy(&js_SlowArrayObjectOps
, &js_ObjectOps
, sizeof(JSObjectOps
));
3321 js_SlowArrayObjectOps
.trace
= slowarray_trace
;
3322 js_SlowArrayObjectOps
.enumerate
= slowarray_enumerate
;
3323 js_SlowArrayObjectOps
.call
= NULL
;
3325 proto
= JS_InitClass(cx
, obj
, NULL
, &js_ArrayClass
, js_Array
, 1,
3326 array_props
, array_methods
, NULL
, NULL
);
3328 /* Initialize the Array prototype object so it gets a length property. */
3329 if (!proto
|| !InitArrayObject(cx
, proto
, 0, NULL
))
3335 js_NewArrayObject(JSContext
*cx
, jsuint length
, jsval
*vector
, JSBool holey
)
3337 JSTempValueRooter tvr
;
3340 obj
= js_NewObject(cx
, &js_ArrayClass
, NULL
, NULL
, 0);
3344 JS_PUSH_TEMP_ROOT_OBJECT(cx
, obj
, &tvr
);
3345 if (!InitArrayObject(cx
, obj
, length
, vector
, holey
))
3347 JS_POP_TEMP_ROOT(cx
, &tvr
);
3349 /* Set/clear newborn root, in case we lost it. */
3350 cx
->weakRoots
.newborn
[GCX_OBJECT
] = obj
;
3355 js_NewSlowArrayObject(JSContext
*cx
)
3357 JSObject
*obj
= js_NewObject(cx
, &js_SlowArrayClass
, NULL
, NULL
, 0);
3359 obj
->fslots
[JSSLOT_ARRAY_LENGTH
] = 0;
3365 js_ArrayInfo(JSContext
*cx
, JSObject
*obj
, uintN argc
, jsval
*argv
, jsval
*rval
)
3370 for (i
= 0; i
< argc
; i
++) {
3373 bytes
= js_DecompileValueGenerator(cx
, JSDVG_SEARCH_STACK
, argv
[i
],
3377 if (JSVAL_IS_PRIMITIVE(argv
[i
]) ||
3378 !OBJ_IS_ARRAY(cx
, (array
= JSVAL_TO_OBJECT(argv
[i
])))) {
3379 fprintf(stderr
, "%s: not array\n", bytes
);
3383 fprintf(stderr
, "%s: %s (len %lu", bytes
,
3384 OBJ_IS_DENSE_ARRAY(cx
, array
) ? "dense" : "sparse",
3385 array
->fslots
[JSSLOT_ARRAY_LENGTH
]);
3386 if (OBJ_IS_DENSE_ARRAY(cx
, array
)) {
3387 fprintf(stderr
, ", count %lu, capacity %lu",
3388 array
->fslots
[JSSLOT_ARRAY_COUNT
],
3389 js_DenseArrayCapacity(array
));
3391 fputs(")\n", stderr
);
3398 JS_FRIEND_API(JSBool
)
3399 js_ArrayToJSUint8Buffer(JSContext
*cx
, JSObject
*obj
, jsuint offset
, jsuint count
,
3404 if (!obj
|| !OBJ_IS_DENSE_ARRAY(cx
, obj
))
3407 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
3408 if (length
< offset
+ count
)
3415 for (uintN i
= offset
; i
< offset
+count
; i
++) {
3417 if (!JSVAL_IS_INT(v
) || (vi
= JSVAL_TO_INT(v
)) < 0)
3420 *dp
++ = (JSUint8
) vi
;
3426 JS_FRIEND_API(JSBool
)
3427 js_ArrayToJSUint16Buffer(JSContext
*cx
, JSObject
*obj
, jsuint offset
, jsuint count
,
3432 if (!obj
|| !OBJ_IS_DENSE_ARRAY(cx
, obj
))
3435 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
3436 if (length
< offset
+ count
)
3442 JSUint16
*dp
= dest
;
3443 for (uintN i
= offset
; i
< offset
+count
; i
++) {
3445 if (!JSVAL_IS_INT(v
) || (vi
= JSVAL_TO_INT(v
)) < 0)
3448 *dp
++ = (JSUint16
) vi
;
3454 JS_FRIEND_API(JSBool
)
3455 js_ArrayToJSUint32Buffer(JSContext
*cx
, JSObject
*obj
, jsuint offset
, jsuint count
,
3460 if (!obj
|| !OBJ_IS_DENSE_ARRAY(cx
, obj
))
3463 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
3464 if (length
< offset
+ count
)
3470 JSUint32
*dp
= dest
;
3471 for (uintN i
= offset
; i
< offset
+count
; i
++) {
3473 if (!JSVAL_IS_INT(v
) || (vi
= JSVAL_TO_INT(v
)) < 0)
3476 *dp
++ = (JSUint32
) vi
;
3482 JS_FRIEND_API(JSBool
)
3483 js_ArrayToJSInt8Buffer(JSContext
*cx
, JSObject
*obj
, jsuint offset
, jsuint count
,
3488 if (!obj
|| !OBJ_IS_DENSE_ARRAY(cx
, obj
))
3491 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
3492 if (length
< offset
+ count
)
3497 for (uintN i
= offset
; i
< offset
+count
; i
++) {
3499 if (!JSVAL_IS_INT(v
))
3502 *dp
++ = (JSInt8
) JSVAL_TO_INT(v
);
3508 JS_FRIEND_API(JSBool
)
3509 js_ArrayToJSInt16Buffer(JSContext
*cx
, JSObject
*obj
, jsuint offset
, jsuint count
,
3514 if (!obj
|| !OBJ_IS_DENSE_ARRAY(cx
, obj
))
3517 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
3518 if (length
< offset
+ count
)
3523 for (uintN i
= offset
; i
< offset
+count
; i
++) {
3525 if (!JSVAL_IS_INT(v
))
3528 *dp
++ = (JSInt16
) JSVAL_TO_INT(v
);
3534 JS_FRIEND_API(JSBool
)
3535 js_ArrayToJSInt32Buffer(JSContext
*cx
, JSObject
*obj
, jsuint offset
, jsuint count
,
3540 if (!obj
|| !OBJ_IS_DENSE_ARRAY(cx
, obj
))
3543 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
3544 if (length
< offset
+ count
)
3549 for (uintN i
= offset
; i
< offset
+count
; i
++) {
3551 if (!JSVAL_IS_INT(v
))
3554 *dp
++ = (JSInt32
) JSVAL_TO_INT(v
);
3560 JS_FRIEND_API(JSBool
)
3561 js_ArrayToJSDoubleBuffer(JSContext
*cx
, JSObject
*obj
, jsuint offset
, jsuint count
,
3566 if (!obj
|| !OBJ_IS_DENSE_ARRAY(cx
, obj
))
3569 length
= obj
->fslots
[JSSLOT_ARRAY_LENGTH
];
3570 if (length
< offset
+ count
)
3574 jsdouble
*dp
= dest
;
3575 for (uintN i
= offset
; i
< offset
+count
; i
++) {
3577 if (JSVAL_IS_INT(v
))
3578 *dp
++ = (jsdouble
) JSVAL_TO_INT(v
);
3579 else if (JSVAL_IS_DOUBLE(v
))
3580 *dp
++ = *(JSVAL_TO_DOUBLE(v
));
3588 JS_DEFINE_CALLINFO_4(extern, BOOL
, js_Array_dense_setelem
, CONTEXT
, OBJECT
, INT32
, JSVAL
, 0, 0)
3589 JS_DEFINE_CALLINFO_2(extern, OBJECT
, js_FastNewArray
, CONTEXT
, OBJECT
, 0, 0)
3590 JS_DEFINE_CALLINFO_3(extern, OBJECT
, js_NewUninitializedArray
, CONTEXT
, OBJECT
, UINT32
, 0, 0)
3591 JS_DEFINE_CALLINFO_3(extern, OBJECT
, js_FastNewArrayWithLength
, CONTEXT
, OBJECT
, UINT32
, 0, 0)
3592 JS_DEFINE_CALLINFO_3(extern, OBJECT
, js_Array_1str
, CONTEXT
, OBJECT
, STRING
, 0, 0)
3593 JS_DEFINE_CALLINFO_3(extern, BOOL
, js_ArrayCompPush
, CONTEXT
, OBJECT
, JSVAL
, 0, 0)