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 with high load factor. Array methods
46 * 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, accessible with
51 * getArrayLength(), setArrayLength().
52 * - The number of element slots (capacity), gettable with
53 * getDenseArrayCapacity().
55 * In dense mode, holes in the array are represented by
56 * MagicValue(JS_ARRAY_HOLE) invalid values.
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. The first
60 * case may occur when the user writes "new Array(100), in which case the
61 * length is 100 while the capacity remains 0 (indices below length and above
62 * capaicty must be treated as holes). See array_length_setter for another
63 * explanation of how the first case may occur.
65 * Arrays are converted to use js_SlowArrayClass when any of these conditions
67 * - there are more than MIN_SPARSE_INDEX slots total
68 * - the load factor (COUNT / capacity) is less than 0.25
69 * - a property is set that is not indexed (and not "length")
70 * - a property is defined that has non-default property attributes.
72 * Dense arrays do not track property creation order, so unlike other native
73 * objects and slow arrays, enumerating an array does not necessarily visit the
74 * properties in the order they were created. We could instead maintain the
75 * scope to track property enumeration order, but still use the fast slot
76 * access. That would have the same memory cost as just using a
77 * js_SlowArrayClass, but have the same performance characteristics as a dense
78 * array for slot accesses, at some cost in code complexity.
91 #include "jsbuiltins.h"
93 #include "jsversion.h"
103 #include "jsstaticcheck.h"
104 #include "jsvector.h"
105 #include "jswrapper.h"
107 #include "jsatominlines.h"
108 #include "jscntxtinlines.h"
109 #include "jsinterpinlines.h"
110 #include "jsobjinlines.h"
113 using namespace js::gc;
115 /* 2^32 - 1 as a number and a string */
116 #define MAXINDEX 4294967295u
117 #define MAXSTR "4294967295"
120 ENSURE_SLOW_ARRAY(JSContext *cx, JSObject *obj)
122 return obj->getClass() == &js_SlowArrayClass ||
123 obj->makeDenseArraySlow(cx);
127 * Determine if the id represents an array index or an XML property index.
129 * An id is an array index according to ECMA by (15.4):
131 * "Array objects give special treatment to a certain class of property names.
132 * A property name P (in the form of a string value) is an array index if and
133 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
136 * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
137 * except that by using signed 31-bit integers we miss the top half of the
138 * valid range. This function checks the string representation itself; note
139 * that calling a standard conversion routine might allow strings such as
140 * "08" or "4.0" as array indices, which they are not.
142 * 'id' is passed as a jsboxedword since the given id need not necessarily hold
143 * an atomized string.
146 js_StringIsIndex(JSLinearString *str, jsuint *indexp)
148 const jschar *cp = str->chars();
149 if (JS7_ISDEC(*cp) && str->length() < sizeof(MAXSTR)) {
150 jsuint index = JS7_UNDEC(*cp++);
154 while (JS7_ISDEC(*cp)) {
157 index = 10*index + c;
162 /* Ensure that all characters were consumed and we didn't overflow. */
164 (oldIndex < (MAXINDEX / 10) ||
165 (oldIndex == (MAXINDEX / 10) && c < (MAXINDEX % 10))))
175 ValueToLength(JSContext *cx, Value* vp, jsuint* plength)
178 int32_t i = vp->toInt32();
182 *plength = (jsuint)(i);
187 if (!ValueToNumber(cx, *vp, &d))
190 if (JSDOUBLE_IS_NaN(d))
195 if (d != (jsdouble) length)
203 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
204 JSMSG_BAD_ARRAY_LENGTH);
209 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
211 if (obj->isArray()) {
212 *lengthp = obj->getArrayLength();
216 if (obj->isArguments() && !obj->isArgsLengthOverridden()) {
217 *lengthp = obj->getArgsInitialLength();
221 AutoValueRooter tvr(cx);
222 if (!obj->getProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.lengthAtom), tvr.addr()))
225 if (tvr.value().isInt32()) {
226 *lengthp = jsuint(jsint(tvr.value().toInt32())); /* jsuint cast does ToUint32 */
230 JS_STATIC_ASSERT(sizeof(jsuint) == sizeof(uint32_t));
231 return ValueToECMAUint32(cx, tvr.value(), (uint32_t *)lengthp);
235 js_IndexToId(JSContext *cx, jsuint index, jsid *idp)
239 if (index <= JSID_INT_MAX) {
240 *idp = INT_TO_JSID(index);
243 str = js_NumberToString(cx, index);
246 return js_ValueToStringId(cx, StringValue(str), idp);
250 BigIndexToId(JSContext *cx, JSObject *obj, jsuint index, JSBool createAtom,
253 jschar buf[10], *start;
256 JS_STATIC_ASSERT((jsuint)-1 == 4294967295U);
258 JS_ASSERT(index > JSID_INT_MAX);
260 start = JS_ARRAY_END(buf);
263 *start = (jschar)('0' + index % 10);
265 } while (index != 0);
268 * Skip the atomization if the class is known to store atoms corresponding
269 * to big indexes together with elements. In such case we know that the
270 * array does not have an element at the given index if its atom does not
271 * exist. Fast arrays (clasp == &js_ArrayClass) don't use atoms for
272 * any indexes, though it would be rare to see them have a big index
276 ((clasp = obj->getClass()) == &js_SlowArrayClass ||
277 clasp == &js_ArgumentsClass ||
278 clasp == &js_ObjectClass)) {
279 atom = js_GetExistingStringAtom(cx, start, JS_ARRAY_END(buf) - start);
285 atom = js_AtomizeChars(cx, start, JS_ARRAY_END(buf) - start, 0);
290 *idp = ATOM_TO_JSID(atom);
295 JSObject::willBeSparseDenseArray(uintN requiredCapacity, uintN newElementsHint)
297 JS_ASSERT(isDenseArray());
298 JS_ASSERT(requiredCapacity > MIN_SPARSE_INDEX);
300 uintN cap = numSlots();
301 JS_ASSERT(requiredCapacity >= cap);
303 if (requiredCapacity >= JSObject::NSLOTS_LIMIT)
306 uintN minimalDenseCount = requiredCapacity / 4;
307 if (newElementsHint >= minimalDenseCount)
309 minimalDenseCount -= newElementsHint;
311 if (minimalDenseCount > cap)
314 Value *elems = getDenseArrayElements();
315 for (uintN i = 0; i < cap; i++) {
316 if (!elems[i].isMagic(JS_ARRAY_HOLE) && !--minimalDenseCount)
323 ReallyBigIndexToId(JSContext* cx, jsdouble index, jsid* idp)
325 return js_ValueToStringId(cx, DoubleValue(index), idp);
329 IndexToId(JSContext* cx, JSObject* obj, jsdouble index, JSBool* hole, jsid* idp,
330 JSBool createAtom = JS_FALSE)
332 if (index <= JSID_INT_MAX) {
333 *idp = INT_TO_JSID(int(index));
337 if (index <= jsuint(-1)) {
338 if (!BigIndexToId(cx, obj, jsuint(index), createAtom, idp))
340 if (hole && JSID_IS_VOID(*idp))
345 return ReallyBigIndexToId(cx, index, idp);
349 * If the property at the given index exists, get its value into location
350 * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
351 * to JSVAL_VOID. This function assumes that the location pointed by vp is
352 * properly rooted and can be used as GC-protected storage for temporaries.
355 GetElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole, Value *vp)
357 JS_ASSERT(index >= 0);
358 if (obj->isDenseArray() && index < obj->getDenseArrayCapacity() &&
359 !(*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
363 if (obj->isArguments() &&
364 index < obj->getArgsInitialLength() &&
365 !(*vp = obj->getArgsElement(uint32(index))).isMagic(JS_ARGS_HOLE)) {
367 JSStackFrame *fp = (JSStackFrame *)obj->getPrivate();
368 if (fp != JS_ARGUMENTS_OBJECT_ON_TRACE) {
370 *vp = fp->canonicalActualArg(index);
375 AutoIdRooter idr(cx);
378 if (!IndexToId(cx, obj, index, hole, idr.addr()))
387 if (!obj->lookupProperty(cx, idr.id(), &obj2, &prop))
393 if (!obj->getProperty(cx, idr.id(), vp))
403 GetElements(JSContext *cx, JSObject *aobj, jsuint length, Value *vp)
405 if (aobj->isDenseArray() && length <= aobj->getDenseArrayCapacity() &&
406 !js_PrototypeHasIndexedProperties(cx, aobj)) {
407 /* The prototype does not have indexed properties so hole = undefined */
408 Value *srcbeg = aobj->getDenseArrayElements();
409 Value *srcend = srcbeg + length;
410 for (Value *dst = vp, *src = srcbeg; src < srcend; ++dst, ++src)
411 *dst = src->isMagic(JS_ARRAY_HOLE) ? UndefinedValue() : *src;
412 } else if (aobj->isArguments() && !aobj->isArgsLengthOverridden() &&
413 !js_PrototypeHasIndexedProperties(cx, aobj)) {
415 * Two cases, two loops: note how in the case of an active stack frame
416 * backing aobj, even though we copy from fp->argv, we still must check
417 * aobj->getArgsElement(i) for a hole, to handle a delete on the
418 * corresponding arguments element. See args_delProperty.
420 if (JSStackFrame *fp = (JSStackFrame *) aobj->getPrivate()) {
421 JS_ASSERT(fp->numActualArgs() <= JS_ARGS_LENGTH_MAX);
422 fp->forEachCanonicalActualArg(CopyNonHoleArgsTo(aobj, vp));
424 Value *srcbeg = aobj->getArgsElements();
425 Value *srcend = srcbeg + length;
426 for (Value *dst = vp, *src = srcbeg; src < srcend; ++dst, ++src)
427 *dst = src->isMagic(JS_ARGS_HOLE) ? UndefinedValue() : *src;
430 for (uintN i = 0; i < length; i++) {
431 if (!aobj->getProperty(cx, INT_TO_JSID(jsint(i)), &vp[i]))
442 * Set the value of the property at the given index to v assuming v is rooted.
445 SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, const Value &v)
447 JS_ASSERT(index >= 0);
449 if (obj->isDenseArray()) {
450 /* Predicted/prefetched code should favor the remains-dense case. */
451 JSObject::EnsureDenseResult result = JSObject::ED_SPARSE;
453 if (index > jsuint(-1))
455 jsuint idx = jsuint(index);
456 result = obj->ensureDenseArrayElements(cx, idx, 1);
457 if (result != JSObject::ED_OK)
459 if (idx >= obj->getArrayLength())
460 obj->setArrayLength(idx + 1);
461 obj->setDenseArrayElement(idx, v);
465 if (result == JSObject::ED_FAILED)
467 JS_ASSERT(result == JSObject::ED_SPARSE);
468 if (!obj->makeDenseArraySlow(cx))
472 AutoIdRooter idr(cx);
474 if (!IndexToId(cx, obj, index, NULL, idr.addr(), JS_TRUE))
476 JS_ASSERT(!JSID_IS_VOID(idr.id()));
479 return obj->setProperty(cx, idr.id(), &tmp, true);
484 js_EnsureDenseArrayCapacity(JSContext *cx, JSObject *obj, jsint i)
487 Class *origObjClasp = obj->clasp;
489 jsuint u = jsuint(i);
490 JSBool ret = (obj->ensureDenseArrayElements(cx, u, 1) == JSObject::ED_OK);
492 /* Partially check the CallInfo's storeAccSet is correct. */
493 JS_ASSERT(obj->clasp == origObjClasp);
496 /* This function and its callees do not touch any object's .clasp field. */
497 JS_DEFINE_CALLINFO_3(extern, BOOL, js_EnsureDenseArrayCapacity, CONTEXT, OBJECT, INT32,
498 0, nanojit::ACCSET_STORE_ANY & ~tjit::ACCSET_OBJ_CLASP)
502 * Delete the element |index| from |obj|. If |strict|, do a strict
503 * deletion: throw if the property is not configurable.
505 * - Return 1 if the deletion succeeds (that is, ES5's [[Delete]] would
508 * - Return 0 if the deletion fails because the property is not
509 * configurable (that is, [[Delete]] would return false). Note that if
510 * |strict| is true we will throw, not return zero.
512 * - Return -1 if an exception occurs (that is, [[Delete]] would throw).
515 DeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index, bool strict)
517 JS_ASSERT(index >= 0);
518 if (obj->isDenseArray()) {
519 if (index <= jsuint(-1)) {
520 jsuint idx = jsuint(index);
521 if (idx < obj->getDenseArrayCapacity()) {
522 obj->setDenseArrayElement(idx, MagicValue(JS_ARRAY_HOLE));
523 if (!js_SuppressDeletedIndexProperties(cx, obj, idx, idx+1))
530 AutoIdRooter idr(cx);
532 if (!IndexToId(cx, obj, index, NULL, idr.addr()))
534 if (JSID_IS_VOID(idr.id()))
538 if (!obj->deleteProperty(cx, idr.id(), &v, strict))
540 return v.isTrue() ? 1 : 0;
544 * When hole is true, delete the property at the given index. Otherwise set
545 * its value to v assuming v is rooted.
548 SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsdouble index,
549 JSBool hole, const Value &v)
552 JS_ASSERT(v.isUndefined());
553 return DeleteArrayElement(cx, obj, index, true) >= 0;
555 return SetArrayElement(cx, obj, index, v);
559 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsdouble length)
565 id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
566 /* We don't support read-only array length yet. */
567 return obj->setProperty(cx, id, &v, false);
571 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
573 JSErrorReporter older = JS_SetErrorReporter(cx, NULL);
574 AutoValueRooter tvr(cx);
575 jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
576 JSBool ok = obj->getProperty(cx, id, tvr.addr());
577 JS_SetErrorReporter(cx, older);
581 if (!ValueToLength(cx, tvr.addr(), lengthp))
588 * Since SpiderMonkey supports cross-class prototype-based delegation, we have
589 * to be careful about the length getter and setter being called on an object
590 * not of Array class. For the getter, we search obj's prototype chain for the
591 * array that caused this getter to be invoked. In the setter case to overcome
592 * the JSPROP_SHARED attribute, we must define a shadowing length property.
595 array_length_getter(JSContext *cx, JSObject *obj, jsid id, Value *vp)
598 if (obj->isArray()) {
599 vp->setNumber(obj->getArrayLength());
602 } while ((obj = obj->getProto()) != NULL);
607 array_length_setter(JSContext *cx, JSObject *obj, jsid id, JSBool strict, Value *vp)
609 jsuint newlen, oldlen, gap, index;
612 if (!obj->isArray()) {
613 jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
615 return obj->defineProperty(cx, lengthId, *vp, NULL, NULL, JSPROP_ENUMERATE);
618 if (!ValueToLength(cx, vp, &newlen))
621 oldlen = obj->getArrayLength();
623 if (oldlen == newlen)
626 vp->setNumber(newlen);
627 if (oldlen < newlen) {
628 obj->setArrayLength(newlen);
632 if (obj->isDenseArray()) {
634 * Don't reallocate if we're not actually shrinking our slots. If we do
635 * shrink slots here, ensureDenseArrayElements will fill all slots to the
636 * right of newlen with JS_ARRAY_HOLE. This permits us to disregard
637 * length when reading from arrays as long we are within the capacity.
639 jsuint oldcap = obj->getDenseArrayCapacity();
641 obj->shrinkDenseArrayElements(cx, newlen);
642 obj->setArrayLength(newlen);
643 } else if (oldlen - newlen < (1 << 24)) {
646 if (!JS_CHECK_OPERATION_LIMIT(cx)) {
647 obj->setArrayLength(oldlen + 1);
650 int deletion = DeleteArrayElement(cx, obj, oldlen, strict);
652 obj->setArrayLength(oldlen + 1);
653 return deletion >= 0;
655 } while (oldlen != newlen);
656 obj->setArrayLength(newlen);
659 * We are going to remove a lot of indexes in a presumably sparse
660 * array. So instead of looping through indexes between newlen and
661 * oldlen, we iterate through all properties and remove those that
662 * correspond to indexes in the half-open range [newlen, oldlen). See
665 JSObject *iter = JS_NewPropertyIterator(cx, obj);
669 /* Protect iter against GC under JSObject::deleteProperty. */
670 AutoObjectRooter tvr(cx, iter);
672 gap = oldlen - newlen;
674 if (!JS_CHECK_OPERATION_LIMIT(cx) || !JS_NextProperty(cx, iter, &id))
676 if (JSID_IS_VOID(id))
678 if (js_IdIsIndex(id, &index) && index - newlen < gap &&
679 !obj->deleteProperty(cx, id, &junk, false)) {
683 obj->setArrayLength(newlen);
690 * We have only indexed properties up to capacity (excepting holes), plus the
691 * length property. For all else, we delegate to the prototype.
694 IsDenseArrayId(JSContext *cx, JSObject *obj, jsid id)
696 JS_ASSERT(obj->isDenseArray());
699 return JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom) ||
700 (js_IdIsIndex(id, &i) &&
701 obj->getArrayLength() != 0 &&
702 i < obj->getDenseArrayCapacity() &&
703 !obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE));
707 array_lookupProperty(JSContext *cx, JSObject *obj, jsid id, JSObject **objp,
710 if (!obj->isDenseArray())
711 return js_LookupProperty(cx, obj, id, objp, propp);
713 if (IsDenseArrayId(cx, obj, id)) {
714 *propp = (JSProperty *) 1; /* non-null to indicate found */
719 JSObject *proto = obj->getProto();
725 return proto->lookupProperty(cx, id, objp, propp);
729 js_GetDenseArrayElementValue(JSContext *cx, JSObject *obj, jsid id, Value *vp)
731 JS_ASSERT(obj->isDenseArray());
734 if (!js_IdIsIndex(id, &i)) {
735 JS_ASSERT(JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom));
736 vp->setNumber(obj->getArrayLength());
739 *vp = obj->getDenseArrayElement(i);
744 array_getProperty(JSContext *cx, JSObject *obj, JSObject *receiver, jsid id, Value *vp)
748 if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)) {
749 vp->setNumber(obj->getArrayLength());
753 if (JSID_IS_ATOM(id, cx->runtime->atomState.protoAtom)) {
754 vp->setObjectOrNull(obj->getProto());
758 if (!obj->isDenseArray())
759 return js_GetProperty(cx, obj, id, vp);
761 if (!js_IdIsIndex(id, &i) || i >= obj->getDenseArrayCapacity() ||
762 obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
767 JSObject *proto = obj->getProto();
774 if (js_LookupPropertyWithFlags(cx, proto, id, cx->resolveFlags,
778 if (prop && obj2->isNative()) {
779 shape = (const Shape *) prop;
780 if (!js_NativeGet(cx, obj, obj2, shape, JSGET_METHOD_BARRIER, vp))
786 *vp = obj->getDenseArrayElement(i);
791 slowarray_addProperty(JSContext *cx, JSObject *obj, jsid id, Value *vp)
793 jsuint index, length;
795 if (!js_IdIsIndex(id, &index))
797 length = obj->getArrayLength();
799 obj->setArrayLength(index + 1);
804 array_typeOf(JSContext *cx, JSObject *obj)
806 return JSTYPE_OBJECT;
810 array_setProperty(JSContext *cx, JSObject *obj, jsid id, Value *vp, JSBool strict)
814 if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
815 return array_length_setter(cx, obj, id, strict, vp);
817 if (!obj->isDenseArray())
818 return js_SetProperty(cx, obj, id, vp, strict);
821 if (!js_IdIsIndex(id, &i))
823 if (js_PrototypeHasIndexedProperties(cx, obj))
826 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, i, 1);
827 if (result != JSObject::ED_OK) {
828 if (result == JSObject::ED_FAILED)
830 JS_ASSERT(result == JSObject::ED_SPARSE);
834 if (i >= obj->getArrayLength())
835 obj->setArrayLength(i + 1);
836 obj->setDenseArrayElement(i, *vp);
840 if (!obj->makeDenseArraySlow(cx))
842 return js_SetProperty(cx, obj, id, vp, strict);
846 js_PrototypeHasIndexedProperties(JSContext *cx, JSObject *obj)
849 * Walk up the prototype chain and see if this indexed element already
850 * exists. If we hit the end of the prototype chain, it's safe to set the
851 * element on the original object.
853 while ((obj = obj->getProto()) != NULL) {
855 * If the prototype is a non-native object (possibly a dense array), or
856 * a native object (possibly a slow array) that has indexed properties,
859 if (!obj->isNative())
861 if (obj->isIndexed())
868 array_defineProperty(JSContext *cx, JSObject *obj, jsid id, const Value *value,
869 PropertyOp getter, StrictPropertyOp setter, uintN attrs)
871 if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
874 if (!obj->isDenseArray())
875 return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
878 uint32 i = 0; // init to shut GCC up
879 bool isIndex = js_IdIsIndex(id, &i);
880 if (!isIndex || attrs != JSPROP_ENUMERATE)
883 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, i, 1);
884 if (result != JSObject::ED_OK) {
885 if (result == JSObject::ED_FAILED)
887 JS_ASSERT(result == JSObject::ED_SPARSE);
891 if (i >= obj->getArrayLength())
892 obj->setArrayLength(i + 1);
893 obj->setDenseArrayElement(i, *value);
897 if (!obj->makeDenseArraySlow(cx))
899 return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
903 array_getAttributes(JSContext *cx, JSObject *obj, jsid id, uintN *attrsp)
905 *attrsp = JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)
906 ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
911 array_setAttributes(JSContext *cx, JSObject *obj, jsid id, uintN *attrsp)
913 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
914 JSMSG_CANT_SET_ARRAY_ATTRS);
919 array_deleteProperty(JSContext *cx, JSObject *obj, jsid id, Value *rval, JSBool strict)
923 if (!obj->isDenseArray())
924 return js_DeleteProperty(cx, obj, id, rval, strict);
926 if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)) {
927 rval->setBoolean(false);
931 if (js_IdIsIndex(id, &i) && i < obj->getDenseArrayCapacity())
932 obj->setDenseArrayElement(i, MagicValue(JS_ARRAY_HOLE));
934 if (!js_SuppressDeletedProperty(cx, obj, id))
937 rval->setBoolean(true);
942 array_trace(JSTracer *trc, JSObject *obj)
944 JS_ASSERT(obj->isDenseArray());
946 uint32 capacity = obj->getDenseArrayCapacity();
947 for (uint32 i = 0; i < capacity; i++)
948 MarkValue(trc, obj->getDenseArrayElement(i), "dense_array_elems");
952 array_fix(JSContext *cx, JSObject *obj, bool *success, AutoIdVector *props)
954 JS_ASSERT(obj->isDenseArray());
957 * We must slowify dense arrays; otherwise, we'd need to detect assignments to holes,
958 * since that is effectively adding a new property to the array.
960 if (!obj->makeDenseArraySlow(cx) ||
961 !GetPropertyNames(cx, obj, JSITER_HIDDEN | JSITER_OWNONLY, props))
968 Class js_ArrayClass = {
971 JSCLASS_HAS_PRIVATE |
972 JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
973 PropertyStub, /* addProperty */
974 PropertyStub, /* delProperty */
975 PropertyStub, /* getProperty */
976 StrictPropertyStub, /* setProperty */
981 NULL, /* reserved0 */
982 NULL, /* checkAccess */
984 NULL, /* construct */
985 NULL, /* xdrObject */
986 NULL, /* hasInstance */
990 array_lookupProperty,
991 array_defineProperty,
996 array_deleteProperty,
997 NULL, /* enumerate */
1001 NULL, /* thisObject */
1006 Class js_SlowArrayClass = {
1008 JSCLASS_HAS_PRIVATE |
1009 JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
1010 slowarray_addProperty,
1011 PropertyStub, /* delProperty */
1012 PropertyStub, /* getProperty */
1013 StrictPropertyStub, /* setProperty */
1020 AddLengthProperty(JSContext *cx, JSObject *obj)
1022 const jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
1023 JS_ASSERT(!obj->nativeLookup(lengthId));
1025 return obj->addProperty(cx, lengthId, array_length_getter, array_length_setter,
1026 SHAPE_INVALID_SLOT, JSPROP_PERMANENT | JSPROP_SHARED, 0, 0);
1030 * Convert an array object from fast-and-dense to slow-and-flexible.
1033 JSObject::makeDenseArraySlow(JSContext *cx)
1035 JS_ASSERT(isDenseArray());
1038 * Save old map now, before calling InitScopeForObject. We'll have to undo
1039 * on error. This is gross, but a better way is not obvious.
1041 JSObjectMap *oldMap = map;
1043 /* Create a native scope. */
1044 JSObject *arrayProto = getProto();
1045 js::gc::FinalizeKind kind = js::gc::FinalizeKind(arena()->header()->thingKind);
1046 if (!InitScopeForObject(cx, this, &js_SlowArrayClass, arrayProto, kind))
1049 uint32 capacity = getDenseArrayCapacity();
1052 * Begin with the length property to share more of the property tree.
1053 * The getter/setter here will directly access the object's private value.
1055 if (!AddLengthProperty(cx, this)) {
1061 * Create new properties pointing to existing elements. Pack the array to
1062 * remove holes, so that shapes use successive slots (as for other objects).
1065 for (uint32 i = 0; i < capacity; i++) {
1067 if (!ValueToId(cx, Int32Value(i), &id)) {
1072 if (getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE))
1075 setDenseArrayElement(next, getDenseArrayElement(i));
1077 if (!addDataProperty(cx, id, next, JSPROP_ENUMERATE)) {
1086 * Dense arrays with different numbers of slots but the same number of fixed
1087 * slots and the same non-hole indexes must use their fixed slots consistently.
1089 if (hasSlotsArray() && next <= numFixedSlots())
1090 revertToFixedSlots(cx);
1092 ClearValueRange(slots + next, this->capacity - next, false);
1095 * Finally, update class. If |this| is Array.prototype, then js_InitClass
1096 * will create an emptyShape whose class is &js_SlowArrayClass, to ensure
1097 * that delegating instances can share shapes in the tree rooted at the
1098 * proto's empty shape.
1100 clasp = &js_SlowArrayClass;
1104 /* Transfer ownership of buffer to returned string. */
1105 static inline JSBool
1106 BufferToString(JSContext *cx, StringBuffer &sb, Value *rval)
1108 JSString *str = sb.finishString();
1111 rval->setString(str);
1117 array_toSource(JSContext *cx, uintN argc, Value *vp)
1119 JS_CHECK_RECURSION(cx, return false);
1121 JSObject *obj = ToObject(cx, &vp[1]);
1124 if (!obj->isSlowArray() && !InstanceOf(cx, obj, &js_ArrayClass, vp + 2))
1127 /* Find joins or cycles in the reachable object graph. */
1129 JSHashEntry *he = js_EnterSharpObject(cx, obj, NULL, &sharpchars);
1132 bool initiallySharp = IS_SHARP(he);
1134 /* After this point, all paths exit through the 'out' label. */
1135 MUST_FLOW_THROUGH("out");
1139 * This object will take responsibility for the jschar buffer until the
1140 * buffer is transferred to the returned JSString.
1142 StringBuffer sb(cx);
1144 /* Cycles/joins are indicated by sharp objects. */
1145 #if JS_HAS_SHARP_VARS
1147 JS_ASSERT(sharpchars != 0);
1148 sb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1150 } else if (sharpchars) {
1152 sb.replaceRawBuffer(sharpchars, js_strlen(sharpchars));
1156 if (!sb.append("[]"))
1158 cx->free(sharpchars);
1163 if (!sb.append('['))
1167 if (!js_GetLengthProperty(cx, obj, &length))
1170 for (jsuint index = 0; index < length; index++) {
1171 /* Use vp to locally root each element value. */
1173 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1174 !GetElement(cx, obj, index, &hole, vp)) {
1178 /* Get element's character string. */
1181 str = cx->runtime->emptyString;
1183 str = js_ValueToSource(cx, *vp);
1189 const jschar *chars = str->getChars(cx);
1193 /* Append element to buffer. */
1194 if (!sb.append(chars, chars + str->length()))
1196 if (index + 1 != length) {
1197 if (!sb.append(", "))
1200 if (!sb.append(','))
1205 /* Finalize the buffer. */
1206 if (!sb.append(']'))
1210 if (!BufferToString(cx, sb, vp))
1216 if (!initiallySharp)
1217 js_LeaveSharpObject(cx, NULL);
1223 array_toString_sub(JSContext *cx, JSObject *obj, JSBool locale,
1224 JSString *sepstr, Value *rval)
1226 JS_CHECK_RECURSION(cx, return false);
1228 /* Get characters to use for the separator. */
1229 static const jschar comma = ',';
1233 seplen = sepstr->length();
1234 sep = sepstr->getChars(cx);
1243 * Use HashTable entry as the cycle indicator. On first visit, create the
1244 * entry, and, when leaving, remove the entry.
1246 BusyArraysMap::AddPtr hashp = cx->busyArrays.lookupForAdd(obj);
1249 /* Not in hash table, so not a cycle. */
1250 if (!cx->busyArrays.add(hashp, obj))
1252 genBefore = cx->busyArrays.generation();
1254 /* Cycle, so return empty string. */
1255 rval->setString(ATOM_TO_STRING(cx->runtime->atomState.emptyAtom));
1259 AutoObjectRooter tvr(cx, obj);
1261 /* After this point, all paths exit through the 'out' label. */
1262 MUST_FLOW_THROUGH("out");
1266 * This object will take responsibility for the jschar buffer until the
1267 * buffer is transferred to the returned JSString.
1269 StringBuffer sb(cx);
1272 if (!js_GetLengthProperty(cx, obj, &length))
1275 for (jsuint index = 0; index < length; index++) {
1276 /* Use rval to locally root each element value. */
1278 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1279 !GetElement(cx, obj, index, &hole, rval)) {
1283 /* Get element's character string. */
1284 if (!(hole || rval->isNullOrUndefined())) {
1286 /* Work on obj.toLocalString() instead. */
1289 if (!js_ValueToObjectOrNull(cx, *rval, &robj))
1291 rval->setObjectOrNull(robj);
1292 JSAtom *atom = cx->runtime->atomState.toLocaleStringAtom;
1293 if (!js_TryMethod(cx, robj, atom, 0, NULL, rval))
1297 if (!ValueToStringBuffer(cx, *rval, sb))
1301 /* Append the separator. */
1302 if (index + 1 != length) {
1303 if (!sb.append(sep, seplen))
1308 /* Finalize the buffer. */
1309 if (!BufferToString(cx, sb, rval))
1315 if (genBefore == cx->busyArrays.generation())
1316 cx->busyArrays.remove(hashp);
1318 cx->busyArrays.remove(obj);
1322 /* ES5 15.4.4.2. NB: The algorithm here differs from the one in ES3. */
1324 array_toString(JSContext *cx, uintN argc, Value *vp)
1326 JSObject *obj = ToObject(cx, &vp[1]);
1330 Value &join = vp[0];
1331 if (!obj->getProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.joinAtom), &join))
1334 if (!js_IsCallable(join)) {
1335 JSString *str = obj_toStringHelper(cx, obj);
1343 InvokeArgsGuard args;
1344 if (!cx->stack().pushInvokeArgs(cx, 0, &args))
1347 args.callee() = join;
1348 args.thisv().setObject(*obj);
1351 if (!Invoke(cx, args, 0))
1358 array_toLocaleString(JSContext *cx, uintN argc, Value *vp)
1360 JSObject *obj = ToObject(cx, &vp[1]);
1365 * Passing comma here as the separator. Need a way to get a
1366 * locale-specific version.
1368 return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
1372 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, Value *vector)
1374 JS_ASSERT(count < MAXINDEX);
1377 * Optimize for dense arrays so long as adding the given set of elements
1378 * wouldn't otherwise make the array slow.
1381 if (!obj->isDenseArray())
1383 if (js_PrototypeHasIndexedProperties(cx, obj))
1386 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, start, count);
1387 if (result != JSObject::ED_OK) {
1388 if (result == JSObject::ED_FAILED)
1390 JS_ASSERT(result == JSObject::ED_SPARSE);
1393 jsuint newlen = start + count;
1394 if (newlen > obj->getArrayLength())
1395 obj->setArrayLength(newlen);
1397 JS_ASSERT(count < uint32(-1) / sizeof(Value));
1398 memcpy(obj->getDenseArrayElements() + start, vector, sizeof(jsval) * count);
1399 JS_ASSERT_IF(count != 0, !obj->getDenseArrayElement(newlen - 1).isMagic(JS_ARRAY_HOLE));
1403 Value* end = vector + count;
1404 while (vector != end && start < MAXINDEX) {
1405 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1406 !SetArrayElement(cx, obj, start++, *vector++)) {
1414 /* Finish out any remaining elements past the max array index. */
1415 if (obj->isDenseArray() && !ENSURE_SLOW_ARRAY(cx, obj))
1418 JS_ASSERT(start == MAXINDEX);
1419 AutoValueRooter tvr(cx);
1420 AutoIdRooter idr(cx);
1421 Value idval = DoubleValue(MAXINDEX);
1423 *tvr.addr() = *vector++;
1424 if (!js_ValueToStringId(cx, idval, idr.addr()) ||
1425 !obj->setProperty(cx, idr.id(), tvr.addr(), true)) {
1428 idval.getDoubleRef() += 1;
1429 } while (vector != end);
1435 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, const Value *vector)
1437 JS_ASSERT(obj->isArray());
1439 JS_ASSERT(obj->isDenseArray());
1440 obj->setArrayLength(length);
1441 if (!vector || !length)
1444 /* Avoid ensureDenseArrayElements to skip sparse array checks there. */
1445 if (!obj->ensureSlots(cx, length))
1447 memcpy(obj->getDenseArrayElements(), vector, length * sizeof(Value));
1452 * Perl-inspired join, reverse, and sort.
1455 array_join(JSContext *cx, uintN argc, Value *vp)
1458 if (argc == 0 || vp[2].isUndefined()) {
1461 str = js_ValueToString(cx, vp[2]);
1464 vp[2].setString(str);
1466 JSObject *obj = ToObject(cx, &vp[1]);
1469 return array_toString_sub(cx, obj, JS_FALSE, str, vp);
1473 array_reverse(JSContext *cx, uintN argc, Value *vp)
1475 JSObject *obj = ToObject(cx, &vp[1]);
1480 if (!js_GetLengthProperty(cx, obj, &len))
1482 vp->setObject(*obj);
1485 if (!obj->isDenseArray())
1487 if (js_PrototypeHasIndexedProperties(cx, obj))
1490 /* An empty array or an array with no elements is already reversed. */
1491 if (len == 0 || obj->getDenseArrayCapacity() == 0)
1495 * It's actually surprisingly complicated to reverse an array due to the
1496 * orthogonality of array length and array capacity while handling
1497 * leading and trailing holes correctly. Reversing seems less likely to
1498 * be a common operation than other array mass-mutation methods, so for
1499 * now just take a probably-small memory hit (in the absence of too many
1500 * holes in the array at its start) and ensure that the capacity is
1501 * sufficient to hold all the elements in the array if it were full.
1503 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, len, 0);
1504 if (result != JSObject::ED_OK) {
1505 if (result == JSObject::ED_FAILED)
1507 JS_ASSERT(result == JSObject::ED_SPARSE);
1511 uint32 lo = 0, hi = len - 1;
1512 for (; lo < hi; lo++, hi--) {
1513 Value origlo = obj->getDenseArrayElement(lo);
1514 Value orighi = obj->getDenseArrayElement(hi);
1515 obj->setDenseArrayElement(lo, orighi);
1516 if (orighi.isMagic(JS_ARRAY_HOLE) &&
1517 !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(lo))) {
1520 obj->setDenseArrayElement(hi, origlo);
1521 if (origlo.isMagic(JS_ARRAY_HOLE) &&
1522 !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(hi))) {
1528 * Per ECMA-262, don't update the length of the array, even if the new
1529 * array has trailing holes (and thus the original array began with
1535 AutoValueRooter tvr(cx);
1536 for (jsuint i = 0, half = len / 2; i < half; i++) {
1538 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1539 !GetElement(cx, obj, i, &hole, tvr.addr()) ||
1540 !GetElement(cx, obj, len - i - 1, &hole2, vp) ||
1541 !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, tvr.value()) ||
1542 !SetOrDeleteArrayElement(cx, obj, i, hole2, *vp)) {
1546 vp->setObject(*obj);
1550 typedef struct MSortArgs {
1557 /* Helper function for js_MergeSort. */
1559 MergeArrays(MSortArgs *msa, void *src, void *dest, size_t run1, size_t run2)
1561 void *arg, *a, *b, *c;
1562 size_t elsize, runtotal;
1567 runtotal = run1 + run2;
1569 elsize = msa->elsize;
1572 isValue = msa->isValue;
1574 #define CALL_CMP(a, b) \
1575 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1577 /* Copy runs already in sorted order. */
1578 b = (char *)src + run1 * elsize;
1579 a = (char *)b - elsize;
1581 if (cmp_result <= 0) {
1582 memcpy(dest, src, runtotal * elsize);
1586 #define COPY_ONE(p,q,n) \
1587 (isValue ? (void)(*(Value*)p = *(Value*)q) : (void)memcpy(p, q, n))
1591 for (; runtotal != 0; runtotal--) {
1592 JSBool from_a = run2 == 0;
1593 if (!from_a && run1 != 0) {
1595 from_a = cmp_result <= 0;
1599 COPY_ONE(c, a, elsize);
1601 a = (char *)a + elsize;
1603 COPY_ONE(c, b, elsize);
1605 b = (char *)b + elsize;
1607 c = (char *)c + elsize;
1616 * This sort is stable, i.e. sequence of equal elements is preserved.
1617 * See also bug #224128.
1620 js_MergeSort(void *src, size_t nel, size_t elsize,
1621 JSComparator cmp, void *arg, void *tmp,
1622 JSMergeSortElemType elemType)
1624 void *swap, *vec1, *vec2;
1626 size_t i, j, lo, hi, run;
1629 JS_ASSERT_IF(JS_SORTING_VALUES, elsize == sizeof(Value));
1630 bool isValue = elemType == JS_SORTING_VALUES;
1632 /* Avoid memcpy overhead for word-sized and word-aligned elements. */
1633 #define COPY_ONE(p,q,n) \
1634 (isValue ? (void)(*(Value*)p = *(Value*)q) : (void)memcpy(p, q, n))
1635 #define CALL_CMP(a, b) \
1636 if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
1637 #define INS_SORT_INT 4
1640 * Apply insertion sort to small chunks to reduce the number of merge
1643 for (lo = 0; lo < nel; lo += INS_SORT_INT) {
1644 hi = lo + INS_SORT_INT;
1647 for (i = lo + 1; i < hi; i++) {
1648 vec1 = (char *)src + i * elsize;
1649 vec2 = (char *)vec1 - elsize;
1650 for (j = i; j > lo; j--) {
1651 CALL_CMP(vec2, vec1);
1652 /* "<=" instead of "<" insures the sort is stable */
1653 if (cmp_result <= 0) {
1657 /* Swap elements, using "tmp" as tmp storage */
1658 COPY_ONE(tmp, vec2, elsize);
1659 COPY_ONE(vec2, vec1, elsize);
1660 COPY_ONE(vec1, tmp, elsize);
1662 vec2 = (char *)vec1 - elsize;
1669 msa.elsize = elsize;
1672 msa.isValue = isValue;
1676 for (run = INS_SORT_INT; run < nel; run *= 2) {
1677 for (lo = 0; lo < nel; lo += 2 * run) {
1680 memcpy((char *)vec2 + lo * elsize, (char *)vec1 + lo * elsize,
1681 (nel - lo) * elsize);
1684 if (!MergeArrays(&msa, (char *)vec1 + lo * elsize,
1685 (char *)vec2 + lo * elsize, run,
1686 hi + run > nel ? nel - hi : run)) {
1695 memcpy(src, tmp, nel * elsize);
1703 InvokeSessionGuard session;
1705 CompareArgs(JSContext *cx)
1710 static JS_REQUIRES_STACK JSBool
1711 sort_compare(void *arg, const void *a, const void *b, int *result)
1713 const Value *av = (const Value *)a, *bv = (const Value *)b;
1714 CompareArgs *ca = (CompareArgs *) arg;
1715 JSContext *cx = ca->context;
1718 * array_sort deals with holes and undefs on its own and they should not
1721 JS_ASSERT(!av->isMagic() && !av->isUndefined());
1722 JS_ASSERT(!av->isMagic() && !bv->isUndefined());
1724 if (!JS_CHECK_OPERATION_LIMIT(cx))
1727 InvokeSessionGuard &session = ca->session;
1731 if (!session.invoke(cx))
1735 if (!ValueToNumber(cx, session.rval(), &cmp))
1738 /* Clamp cmp to -1, 0, 1. */
1740 if (!JSDOUBLE_IS_NaN(cmp) && cmp != 0)
1741 *result = cmp > 0 ? 1 : -1;
1744 * XXX else report some kind of error here? ECMA talks about 'consistent
1745 * compare functions' that don't return NaN, but is silent about what the
1746 * result should be. So we currently ignore it.
1752 typedef JSBool (JS_REQUIRES_STACK *JSRedComparator)(void*, const void*,
1753 const void*, int *);
1755 static inline JS_IGNORE_STACK JSComparator
1756 comparator_stack_cast(JSRedComparator func)
1762 sort_compare_strings(void *arg, const void *a, const void *b, int *result)
1764 JSContext *cx = (JSContext *)arg;
1765 JSString *astr = ((const Value *)a)->toString();
1766 JSString *bstr = ((const Value *)b)->toString();
1767 return JS_CHECK_OPERATION_LIMIT(cx) && CompareStrings(cx, astr, bstr, result);
1771 js::array_sort(JSContext *cx, uintN argc, Value *vp)
1773 jsuint len, newlen, i, undefs;
1777 Value *argv = JS_ARGV(cx, vp);
1779 if (argc > 0 && !argv[0].isUndefined()) {
1780 if (argv[0].isPrimitive()) {
1781 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_BAD_SORT_ARG);
1784 fval = argv[0]; /* non-default compare function */
1789 JSObject *obj = ToObject(cx, &vp[1]);
1792 if (!js_GetLengthProperty(cx, obj, &len))
1795 vp->setObject(*obj);
1800 * We need a temporary array of 2 * len Value to hold the array elements
1801 * and the scratch space for merge sort. Check that its size does not
1802 * overflow size_t, which would allow for indexing beyond the end of the
1805 #if JS_BITS_PER_WORD == 32
1806 if (size_t(len) > size_t(-1) / (2 * sizeof(Value))) {
1807 js_ReportAllocationOverflow(cx);
1813 * Initialize vec as a root. We will clear elements of vec one by
1814 * one while increasing the rooted amount of vec when we know that the
1815 * property at the corresponding index exists and its value must be rooted.
1817 * In this way when sorting a huge mostly sparse array we will not
1818 * access the tail of vec corresponding to properties that do not
1819 * exist, allowing OS to avoiding committing RAM. See bug 330812.
1822 Value *vec = (Value *) cx->malloc(2 * size_t(len) * sizeof(Value));
1826 DEFINE_LOCAL_CLASS_OF_STATIC_FUNCTION(AutoFreeVector) {
1827 JSContext *const cx;
1830 AutoFreeVector(JSContext *cx, Value *&vec) : cx(cx), vec(vec) { }
1836 AutoArrayRooter tvr(cx, 0, vec);
1839 * By ECMA 262, 15.4.4.11, a property that does not exist (which we
1840 * call a "hole") is always greater than an existing property with
1841 * value undefined and that is always greater than any other property.
1842 * Thus to sort holes and undefs we simply count them, sort the rest
1843 * of elements, append undefs after them and then make holes after
1848 bool allStrings = true;
1849 for (i = 0; i < len; i++) {
1850 if (!JS_CHECK_OPERATION_LIMIT(cx))
1853 /* Clear vec[newlen] before including it in the rooted set. */
1855 vec[newlen].setNull();
1856 tvr.changeLength(newlen + 1);
1857 if (!GetElement(cx, obj, i, &hole, &vec[newlen]))
1863 if (vec[newlen].isUndefined()) {
1868 allStrings = allStrings && vec[newlen].isString();
1874 vp->setObject(*obj);
1875 return true; /* The array has only holes and undefs. */
1879 * The first newlen elements of vec are copied from the array object
1880 * (above). The remaining newlen positions are used as GC-rooted scratch
1881 * space for mergesort. We must clear the space before including it to
1882 * the root set covered by tvr.count.
1884 Value *mergesort_tmp = vec + newlen;
1885 MakeRangeGCSafe(mergesort_tmp, newlen);
1886 tvr.changeLength(newlen * 2);
1888 /* Here len == 2 * (newlen + undefs + number_of_holes). */
1889 if (fval.isNull()) {
1891 * Sort using the default comparator converting all elements to
1895 elemsize = sizeof(Value);
1898 * To avoid string conversion on each compare we do it only once
1899 * prior to sorting. But we also need the space for the original
1900 * values to recover the sorting result. To reuse
1901 * sort_compare_strings we move the original values to the odd
1902 * indexes in vec, put the string conversion results in the even
1903 * indexes and pass 2 * sizeof(Value) as an element size to the
1904 * sorting function. In this way sort_compare_strings will only
1905 * see the string values when it casts the compare arguments as
1906 * pointers to Value.
1908 * This requires doubling the temporary storage including the
1909 * scratch space for the merge sort. Since vec already contains
1910 * the rooted scratch space for newlen elements at the tail, we
1911 * can use it to rearrange and convert to strings first and try
1912 * realloc only when we know that we successfully converted all
1915 #if JS_BITS_PER_WORD == 32
1916 if (size_t(newlen) > size_t(-1) / (4 * sizeof(Value))) {
1917 js_ReportAllocationOverflow(cx);
1923 * Rearrange and string-convert the elements of the vector from
1924 * the tail here and, after sorting, move the results back
1925 * starting from the start to prevent overwrite the existing
1931 if (!JS_CHECK_OPERATION_LIMIT(cx))
1933 const Value &v = vec[i];
1934 str = js_ValueToString(cx, v);
1937 // Copying v must come first, because the following line overwrites v
1940 vec[2 * i].setString(str);
1943 JS_ASSERT(tvr.array == vec);
1944 vec = (Value *) cx->realloc(vec, 4 * size_t(newlen) * sizeof(Value));
1946 vec = tvr.array; /* N.B. AutoFreeVector */
1949 mergesort_tmp = vec + 2 * newlen;
1950 MakeRangeGCSafe(mergesort_tmp, 2 * newlen);
1951 tvr.changeArray(vec, newlen * 4);
1952 elemsize = 2 * sizeof(Value);
1954 if (!js_MergeSort(vec, size_t(newlen), elemsize,
1955 sort_compare_strings, cx, mergesort_tmp,
1956 JS_SORTING_GENERIC)) {
1961 * We want to make the following loop fast and to unroot the
1962 * cached results of toString invocations before the operation
1963 * callback has a chance to run the GC. For this reason we do
1964 * not call JS_CHECK_OPERATION_LIMIT in the loop.
1968 vec[i] = vec[2 * i + 1];
1969 } while (++i != newlen);
1973 if (!ca.session.start(cx, fval, UndefinedValue(), 2))
1976 if (!js_MergeSort(vec, size_t(newlen), sizeof(Value),
1977 comparator_stack_cast(sort_compare),
1979 JS_SORTING_VALUES)) {
1985 * We no longer need to root the scratch space for the merge sort, so
1986 * unroot it now to make the job of a potential GC under
1987 * InitArrayElements easier.
1989 tvr.changeLength(newlen);
1990 if (!InitArrayElements(cx, obj, 0, newlen, vec))
1994 /* Set undefs that sorted after the rest of elements. */
1995 while (undefs != 0) {
1997 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
1998 !SetArrayElement(cx, obj, newlen++, UndefinedValue())) {
2003 /* Re-create any holes that sorted to the end of the array. */
2004 while (len > newlen) {
2005 if (!JS_CHECK_OPERATION_LIMIT(cx) || DeleteArrayElement(cx, obj, --len, true) < 0)
2008 vp->setObject(*obj);
2013 * Perl-inspired push, pop, shift, unshift, and splice methods.
2016 array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, Value *argv, Value *rval)
2020 if (!js_GetLengthProperty(cx, obj, &length))
2022 if (!InitArrayElements(cx, obj, length, argc, argv))
2025 /* Per ECMA-262, return the new array length. */
2026 jsdouble newlength = length + jsdouble(argc);
2027 rval->setNumber(newlength);
2028 return js_SetLengthProperty(cx, obj, newlength);
2032 array_push1_dense(JSContext* cx, JSObject* obj, const Value &v, Value *rval)
2034 uint32 length = obj->getArrayLength();
2036 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, 1);
2037 if (result != JSObject::ED_OK) {
2038 if (result == JSObject::ED_FAILED)
2040 JS_ASSERT(result == JSObject::ED_SPARSE);
2044 obj->setArrayLength(length + 1);
2046 JS_ASSERT(obj->getDenseArrayElement(length).isMagic(JS_ARRAY_HOLE));
2047 obj->setDenseArrayElement(length, v);
2048 rval->setNumber(obj->getArrayLength());
2052 if (!obj->makeDenseArraySlow(cx))
2055 return array_push_slowly(cx, obj, 1, &tmp, rval);
2058 JS_ALWAYS_INLINE JSBool
2059 ArrayCompPushImpl(JSContext *cx, JSObject *obj, const Value &v)
2061 uint32 length = obj->getArrayLength();
2062 if (obj->isSlowArray()) {
2063 /* This can happen in one evil case. See bug 630377. */
2065 return js_IndexToId(cx, length, &id) &&
2066 js_DefineProperty(cx, obj, id, &v, NULL, NULL, JSPROP_ENUMERATE);
2069 JS_ASSERT(obj->isDenseArray());
2070 JS_ASSERT(length <= obj->getDenseArrayCapacity());
2072 if (length == obj->getDenseArrayCapacity()) {
2073 if (length > JS_ARGS_LENGTH_MAX) {
2074 JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
2075 JSMSG_ARRAY_INIT_TOO_BIG);
2080 * An array comprehension cannot add holes to the array. So we can use
2081 * ensureSlots instead of ensureDenseArrayElements.
2083 if (!obj->ensureSlots(cx, length + 1))
2086 obj->setArrayLength(length + 1);
2087 obj->setDenseArrayElement(length, v);
2092 js_ArrayCompPush(JSContext *cx, JSObject *obj, const Value &vp)
2094 return ArrayCompPushImpl(cx, obj, vp);
2099 js_ArrayCompPush_tn(JSContext *cx, JSObject *obj, ValueArgType v)
2101 TraceMonitor *tm = JS_TRACE_MONITOR_ON_TRACE(cx);
2103 if (!ArrayCompPushImpl(cx, obj, ValueArgToConstRef(v))) {
2104 SetBuiltinError(tm);
2108 return WasBuiltinSuccessful(tm);
2110 JS_DEFINE_CALLINFO_3(extern, BOOL_FAIL, js_ArrayCompPush_tn, CONTEXT, OBJECT,
2111 VALUE, 0, nanojit::ACCSET_STORE_ANY)
2115 array_push(JSContext *cx, uintN argc, Value *vp)
2117 JSObject *obj = ToObject(cx, &vp[1]);
2121 /* Insist on one argument and obj of the expected class. */
2122 if (argc != 1 || !obj->isDenseArray())
2123 return array_push_slowly(cx, obj, argc, vp + 2, vp);
2125 return array_push1_dense(cx, obj, vp[2], vp);
2129 array_pop_slowly(JSContext *cx, JSObject* obj, Value *vp)
2134 if (!js_GetLengthProperty(cx, obj, &index))
2141 /* Get the to-be-deleted property's value into vp. */
2142 if (!GetElement(cx, obj, index, &hole, vp))
2144 if (!hole && DeleteArrayElement(cx, obj, index, true) < 0)
2147 return js_SetLengthProperty(cx, obj, index);
2151 array_pop_dense(JSContext *cx, JSObject* obj, Value *vp)
2156 index = obj->getArrayLength();
2162 if (!GetElement(cx, obj, index, &hole, vp))
2164 if (!hole && DeleteArrayElement(cx, obj, index, true) < 0)
2166 obj->setArrayLength(index);
2171 array_pop(JSContext *cx, uintN argc, Value *vp)
2173 JSObject *obj = ToObject(cx, &vp[1]);
2176 if (obj->isDenseArray())
2177 return array_pop_dense(cx, obj, vp);
2178 return array_pop_slowly(cx, obj, vp);
2182 array_shift(JSContext *cx, uintN argc, Value *vp)
2184 JSObject *obj = ToObject(cx, &vp[1]);
2189 if (!js_GetLengthProperty(cx, obj, &length))
2197 if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
2198 length < obj->getDenseArrayCapacity()) {
2199 *vp = obj->getDenseArrayElement(0);
2200 if (vp->isMagic(JS_ARRAY_HOLE))
2202 Value *elems = obj->getDenseArrayElements();
2203 memmove(elems, elems + 1, length * sizeof(jsval));
2204 obj->setDenseArrayElement(length, MagicValue(JS_ARRAY_HOLE));
2205 obj->setArrayLength(length);
2206 if (!js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(length)))
2211 /* Get the to-be-deleted property's value into vp ASAP. */
2213 if (!GetElement(cx, obj, 0, &hole, vp))
2216 /* Slide down the array above the first element. */
2217 AutoValueRooter tvr(cx);
2218 for (jsuint i = 0; i < length; i++) {
2219 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2220 !GetElement(cx, obj, i + 1, &hole, tvr.addr()) ||
2221 !SetOrDeleteArrayElement(cx, obj, i, hole, tvr.value())) {
2226 /* Delete the only or last element when it exists. */
2227 if (!hole && DeleteArrayElement(cx, obj, length, true) < 0)
2230 return js_SetLengthProperty(cx, obj, length);
2234 array_unshift(JSContext *cx, uintN argc, Value *vp)
2238 jsdouble last, newlen;
2240 JSObject *obj = ToObject(cx, &vp[1]);
2245 if (!js_GetLengthProperty(cx, obj, &length))
2249 /* Slide up the array to make room for argc at the bottom. */
2250 argv = JS_ARGV(cx, vp);
2252 bool optimized = false;
2254 if (!obj->isDenseArray())
2256 if (js_PrototypeHasIndexedProperties(cx, obj))
2258 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, argc);
2259 if (result != JSObject::ED_OK) {
2260 if (result == JSObject::ED_FAILED)
2262 JS_ASSERT(result == JSObject::ED_SPARSE);
2265 Value *elems = obj->getDenseArrayElements();
2266 memmove(elems + argc, elems, length * sizeof(jsval));
2267 for (uint32 i = 0; i < argc; i++)
2268 obj->setDenseArrayElement(i, MagicValue(JS_ARRAY_HOLE));
2274 jsdouble upperIndex = last + argc;
2275 AutoValueRooter tvr(cx);
2277 --last, --upperIndex;
2278 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2279 !GetElement(cx, obj, last, &hole, tvr.addr()) ||
2280 !SetOrDeleteArrayElement(cx, obj, upperIndex, hole, tvr.value())) {
2283 } while (last != 0);
2287 /* Copy from argv to the bottom of the array. */
2288 if (!InitArrayElements(cx, obj, 0, argc, argv))
2293 if (!js_SetLengthProperty(cx, obj, newlen))
2296 /* Follow Perl by returning the new array length. */
2297 vp->setNumber(newlen);
2302 array_splice(JSContext *cx, uintN argc, Value *vp)
2304 JSObject *obj = ToObject(cx, &vp[1]);
2308 jsuint length, begin, end, count, delta, last;
2311 /* Create a new array value to return. */
2312 JSObject *obj2 = NewDenseEmptyArray(cx);
2315 vp->setObject(*obj2);
2317 /* Nothing to do if no args. Otherwise get length. */
2320 Value *argv = JS_ARGV(cx, vp);
2321 if (!js_GetLengthProperty(cx, obj, &length))
2323 jsuint origlength = length;
2325 /* Convert the first argument into a starting index. */
2327 if (!ValueToNumber(cx, *argv, &d))
2329 d = js_DoubleToInteger(d);
2334 } else if (d > length) {
2337 begin = (jsuint)d; /* d has been clamped to uint32 */
2341 /* Convert the second argument from a count into a fencepost index. */
2342 delta = length - begin;
2347 if (!ValueToNumber(cx, *argv, &d))
2349 d = js_DoubleToInteger(d);
2355 end = begin + count;
2360 AutoValueRooter tvr(cx);
2362 /* If there are elements to remove, put them into the return value. */
2364 if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
2365 end <= obj->getDenseArrayCapacity()) {
2366 if (!InitArrayObject(cx, obj2, count, obj->getDenseArrayElements() + begin))
2369 for (last = begin; last < end; last++) {
2370 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2371 !GetElement(cx, obj, last, &hole, tvr.addr())) {
2375 /* Copy tvr.value() to the new array unless it's a hole. */
2376 if (!hole && !SetArrayElement(cx, obj2, last - begin, tvr.value()))
2380 if (!js_SetLengthProperty(cx, obj2, count))
2385 /* Find the direction (up or down) to copy and make way for argv. */
2387 delta = (jsuint)argc - count;
2389 bool optimized = false;
2391 if (!obj->isDenseArray())
2393 if (js_PrototypeHasIndexedProperties(cx, obj))
2395 if (length > obj->getDenseArrayCapacity())
2397 if (length != 0 && obj->getDenseArrayElement(length - 1).isMagic(JS_ARRAY_HOLE))
2399 JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, delta);
2400 if (result != JSObject::ED_OK) {
2401 if (result == JSObject::ED_FAILED)
2403 JS_ASSERT(result == JSObject::ED_SPARSE);
2406 Value *arraybeg = obj->getDenseArrayElements();
2407 Value *srcbeg = arraybeg + last - 1;
2408 Value *srcend = arraybeg + end - 1;
2409 Value *dstbeg = srcbeg + delta;
2410 for (Value *src = srcbeg, *dst = dstbeg; src > srcend; --src, --dst)
2413 obj->setArrayLength(obj->getArrayLength() + delta);
2418 /* (uint) end could be 0, so we can't use a vanilla >= test. */
2419 while (last-- > end) {
2420 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2421 !GetElement(cx, obj, last, &hole, tvr.addr()) ||
2422 !SetOrDeleteArrayElement(cx, obj, last + delta, hole, tvr.value())) {
2428 } else if (argc < count) {
2429 delta = count - (jsuint)argc;
2430 if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
2431 length <= obj->getDenseArrayCapacity()) {
2433 Value *arraybeg = obj->getDenseArrayElements();
2434 Value *srcbeg = arraybeg + end;
2435 Value *srcend = arraybeg + length;
2436 Value *dstbeg = srcbeg - delta;
2437 for (Value *src = srcbeg, *dst = dstbeg; src < srcend; ++src, ++dst)
2440 for (last = end; last < length; last++) {
2441 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2442 !GetElement(cx, obj, last, &hole, tvr.addr()) ||
2443 !SetOrDeleteArrayElement(cx, obj, last - delta, hole, tvr.value())) {
2451 if (length < origlength && !js_SuppressDeletedIndexProperties(cx, obj, length, origlength))
2455 * Copy from argv into the hole to complete the splice, and update length in
2456 * case we deleted elements from the end.
2458 return InitArrayElements(cx, obj, begin, argc, argv) &&
2459 js_SetLengthProperty(cx, obj, length);
2463 * Python-esque sequence operations.
2466 array_concat(JSContext *cx, uintN argc, Value *vp)
2468 /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
2469 Value *p = JS_ARGV(cx, vp) - 1;
2471 /* Create a new Array object and root it using *vp. */
2472 JSObject *aobj = ToObject(cx, &vp[1]);
2478 if (aobj->isDenseArray()) {
2480 * Clone aobj but pass the minimum of its length and capacity, to
2481 * handle a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In
2482 * the normal case where length is <= capacity, nobj and aobj will have
2483 * the same capacity.
2485 length = aobj->getArrayLength();
2486 jsuint capacity = aobj->getDenseArrayCapacity();
2487 nobj = NewDenseCopiedArray(cx, JS_MIN(length, capacity), aobj->getDenseArrayElements());
2490 nobj->setArrayLength(length);
2491 vp->setObject(*nobj);
2497 nobj = NewDenseEmptyArray(cx);
2500 vp->setObject(*nobj);
2504 AutoValueRooter tvr(cx);
2506 /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
2507 for (uintN i = 0; i <= argc; i++) {
2508 if (!JS_CHECK_OPERATION_LIMIT(cx))
2510 const Value &v = p[i];
2512 aobj = &v.toObject();
2513 if (aobj->isArray() ||
2514 (aobj->isWrapper() && JSWrapper::wrappedObject(aobj)->isArray())) {
2515 jsid id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
2516 if (!aobj->getProperty(cx, id, tvr.addr()))
2519 if (!ValueToLength(cx, tvr.addr(), &alength))
2521 for (jsuint slot = 0; slot < alength; slot++) {
2523 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2524 !GetElement(cx, aobj, slot, &hole, tvr.addr())) {
2529 * Per ECMA 262, 15.4.4.4, step 9, ignore nonexistent
2533 !SetArrayElement(cx, nobj, length+slot, tvr.value())) {
2542 if (!SetArrayElement(cx, nobj, length, v))
2547 return js_SetLengthProperty(cx, nobj, length);
2551 array_slice(JSContext *cx, uintN argc, Value *vp)
2555 jsuint length, begin, end, slot;
2558 argv = JS_ARGV(cx, vp);
2560 JSObject *obj = ToObject(cx, &vp[1]);
2564 if (!js_GetLengthProperty(cx, obj, &length))
2571 if (!ValueToNumber(cx, argv[0], &d))
2573 d = js_DoubleToInteger(d);
2578 } else if (d > length) {
2583 if (argc > 1 && !argv[1].isUndefined()) {
2584 if (!ValueToNumber(cx, argv[1], &d))
2586 d = js_DoubleToInteger(d);
2591 } else if (d > length) {
2601 if (obj->isDenseArray() && end <= obj->getDenseArrayCapacity() &&
2602 !js_PrototypeHasIndexedProperties(cx, obj)) {
2603 nobj = NewDenseCopiedArray(cx, end - begin, obj->getDenseArrayElements() + begin);
2606 vp->setObject(*nobj);
2610 /* Create a new Array object and root it using *vp. */
2611 nobj = NewDenseAllocatedArray(cx, end - begin);
2614 vp->setObject(*nobj);
2616 AutoValueRooter tvr(cx);
2617 for (slot = begin; slot < end; slot++) {
2618 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2619 !GetElement(cx, obj, slot, &hole, tvr.addr())) {
2622 if (!hole && !SetArrayElement(cx, nobj, slot - begin, tvr.value()))
2629 #if JS_HAS_ARRAY_EXTRAS
2632 array_indexOfHelper(JSContext *cx, JSBool isLast, uintN argc, Value *vp)
2634 jsuint length, i, stop;
2639 JSObject *obj = ToObject(cx, &vp[1]);
2642 if (!js_GetLengthProperty(cx, obj, &length))
2648 i = isLast ? length - 1 : 0;
2649 tosearch = (argc != 0) ? vp[2] : UndefinedValue();
2654 if (!ValueToNumber(cx, vp[3], &start))
2656 start = js_DoubleToInteger(start);
2666 } else if (start >= length) {
2684 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
2685 !GetElement(cx, obj, (jsuint)i, &hole, vp)) {
2690 if (!StrictlyEqual(cx, *vp, tosearch, &equal))
2708 array_indexOf(JSContext *cx, uintN argc, Value *vp)
2710 return array_indexOfHelper(cx, JS_FALSE, argc, vp);
2714 array_lastIndexOf(JSContext *cx, uintN argc, Value *vp)
2716 return array_indexOfHelper(cx, JS_TRUE, argc, vp);
2719 /* Order is important; extras that take a predicate funarg must follow MAP. */
2720 typedef enum ArrayExtraMode {
2730 #define REDUCE_MODE(mode) ((mode) == REDUCE || (mode) == REDUCE_RIGHT)
2733 array_extra(JSContext *cx, ArrayExtraMode mode, uintN argc, Value *vp)
2735 JSObject *obj = ToObject(cx, &vp[1]);
2740 if (!js_GetLengthProperty(cx, obj, &length))
2744 * First, get or compute our callee, so that we error out consistently
2745 * when passed a non-callable object.
2748 js_ReportMissingArg(cx, *vp, 0);
2751 Value *argv = vp + 2;
2752 JSObject *callable = js_ValueToCallableObject(cx, &argv[0], JSV2F_SEARCH_STACK);
2757 * Set our initial return condition, used for zero-length array cases
2758 * (and pre-size our map return to match our known length, for all cases).
2762 #ifdef __GNUC__ /* quell GCC overwarning */
2766 jsint start = 0, end = length, step = 1;
2770 start = length - 1, end = -1, step = -1;
2773 if (length == 0 && argc == 1) {
2774 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2775 JSMSG_EMPTY_ARRAY_REDUCE);
2783 if (!GetElement(cx, obj, start, &hole, vp))
2786 } while (hole && start != end);
2788 if (hole && start == end) {
2789 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
2790 JSMSG_EMPTY_ARRAY_REDUCE);
2797 newlen = (mode == MAP) ? length : 0;
2798 newarr = NewDenseAllocatedArray(cx, newlen);
2801 vp->setObject(*newarr);
2804 vp->setBoolean(false);
2807 vp->setBoolean(true);
2817 Value thisv = (argc > 1 && !REDUCE_MODE(mode)) ? argv[1] : UndefinedValue();
2820 * For all but REDUCE, we call with 3 args (value, index, array). REDUCE
2821 * requires 4 args (accum, value, index, array).
2823 argc = 3 + REDUCE_MODE(mode);
2825 InvokeSessionGuard session;
2826 if (!session.start(cx, ObjectValue(*callable), thisv, argc))
2829 MUST_FLOW_THROUGH("out");
2830 JSBool ok = JS_TRUE;
2833 Value objv = ObjectValue(*obj);
2834 AutoValueRooter tvr(cx);
2835 for (jsint i = start; i != end; i += step) {
2837 ok = JS_CHECK_OPERATION_LIMIT(cx) &&
2838 GetElement(cx, obj, i, &hole, tvr.addr());
2845 * Push callable and 'this', then args. We must do this for every
2846 * iteration around the loop since Invoke clobbers its arguments.
2849 if (REDUCE_MODE(mode))
2850 session[argi++] = *vp;
2851 session[argi++] = tvr.value();
2852 session[argi++] = Int32Value(i);
2853 session[argi] = objv;
2856 ok = session.invoke(cx);
2860 const Value &rval = session.rval();
2863 cond = js_ValueToBoolean(rval);
2864 #ifdef __GNUC__ /* quell GCC overwarning */
2877 ok = SetArrayElement(cx, newarr, i, rval);
2884 /* The element passed the filter, so push it onto our result. */
2885 ok = SetArrayElement(cx, newarr, newlen++, tvr.value());
2891 vp->setBoolean(true);
2897 vp->setBoolean(false);
2905 if (ok && mode == FILTER)
2906 ok = js_SetLengthProperty(cx, newarr, newlen);
2911 array_forEach(JSContext *cx, uintN argc, Value *vp)
2913 return array_extra(cx, FOREACH, argc, vp);
2917 array_map(JSContext *cx, uintN argc, Value *vp)
2919 return array_extra(cx, MAP, argc, vp);
2923 array_reduce(JSContext *cx, uintN argc, Value *vp)
2925 return array_extra(cx, REDUCE, argc, vp);
2929 array_reduceRight(JSContext *cx, uintN argc, Value *vp)
2931 return array_extra(cx, REDUCE_RIGHT, argc, vp);
2935 array_filter(JSContext *cx, uintN argc, Value *vp)
2937 return array_extra(cx, FILTER, argc, vp);
2941 array_some(JSContext *cx, uintN argc, Value *vp)
2943 return array_extra(cx, SOME, argc, vp);
2947 array_every(JSContext *cx, uintN argc, Value *vp)
2949 return array_extra(cx, EVERY, argc, vp);
2954 array_isArray(JSContext *cx, uintN argc, Value *vp)
2957 vp->setBoolean(argc > 0 &&
2959 ((obj = &vp[2].toObject())->isArray() ||
2960 (obj->isWrapper() && JSWrapper::wrappedObject(obj)->isArray())));
2964 static JSFunctionSpec array_methods[] = {
2966 JS_FN(js_toSource_str, array_toSource, 0,0),
2968 JS_FN(js_toString_str, array_toString, 0,0),
2969 JS_FN(js_toLocaleString_str,array_toLocaleString,0,0),
2971 /* Perl-ish methods. */
2972 JS_FN("join", array_join, 1,JSFUN_GENERIC_NATIVE),
2973 JS_FN("reverse", array_reverse, 0,JSFUN_GENERIC_NATIVE),
2974 JS_FN("sort", array_sort, 1,JSFUN_GENERIC_NATIVE),
2975 JS_FN("push", array_push, 1,JSFUN_GENERIC_NATIVE),
2976 JS_FN("pop", array_pop, 0,JSFUN_GENERIC_NATIVE),
2977 JS_FN("shift", array_shift, 0,JSFUN_GENERIC_NATIVE),
2978 JS_FN("unshift", array_unshift, 1,JSFUN_GENERIC_NATIVE),
2979 JS_FN("splice", array_splice, 2,JSFUN_GENERIC_NATIVE),
2981 /* Pythonic sequence methods. */
2982 JS_FN("concat", array_concat, 1,JSFUN_GENERIC_NATIVE),
2983 JS_FN("slice", array_slice, 2,JSFUN_GENERIC_NATIVE),
2985 #if JS_HAS_ARRAY_EXTRAS
2986 JS_FN("indexOf", array_indexOf, 1,JSFUN_GENERIC_NATIVE),
2987 JS_FN("lastIndexOf", array_lastIndexOf, 1,JSFUN_GENERIC_NATIVE),
2988 JS_FN("forEach", array_forEach, 1,JSFUN_GENERIC_NATIVE),
2989 JS_FN("map", array_map, 1,JSFUN_GENERIC_NATIVE),
2990 JS_FN("reduce", array_reduce, 1,JSFUN_GENERIC_NATIVE),
2991 JS_FN("reduceRight", array_reduceRight, 1,JSFUN_GENERIC_NATIVE),
2992 JS_FN("filter", array_filter, 1,JSFUN_GENERIC_NATIVE),
2993 JS_FN("some", array_some, 1,JSFUN_GENERIC_NATIVE),
2994 JS_FN("every", array_every, 1,JSFUN_GENERIC_NATIVE),
3000 static JSFunctionSpec array_static_methods[] = {
3001 JS_FN("isArray", array_isArray, 1,0),
3006 js_Array(JSContext *cx, uintN argc, Value *vp)
3011 obj = NewDenseEmptyArray(cx);
3012 } else if (argc > 1) {
3013 obj = NewDenseCopiedArray(cx, argc, vp + 2);
3014 } else if (!vp[2].isNumber()) {
3015 obj = NewDenseCopiedArray(cx, 1, vp + 2);
3018 if (!ValueToLength(cx, vp + 2, &length))
3020 obj = NewDenseUnallocatedArray(cx, length);
3025 vp->setObject(*obj);
3031 js_InitArrayClass(JSContext *cx, JSObject *obj)
3033 JSObject *proto = js_InitClass(cx, obj, NULL, &js_ArrayClass, js_Array, 1,
3034 NULL, array_methods, NULL, array_static_methods);
3039 * Assert that js_InitClass used the correct (slow array, not dense array)
3040 * class for proto's emptyShape class.
3042 JS_ASSERT(proto->emptyShapes && proto->emptyShapes[0]->getClass() == proto->getClass());
3044 proto->setArrayLength(0);
3049 * Array allocation functions.
3053 template<bool allocateCapacity>
3054 static JS_ALWAYS_INLINE JSObject *
3055 NewArray(JSContext *cx, jsuint length, JSObject *proto)
3057 JS_ASSERT_IF(proto, proto->isArray());
3059 gc::FinalizeKind kind = GuessObjectGCKind(length, true);
3060 JSObject *obj = detail::NewObject<WithProto::Class, false>(cx, &js_ArrayClass, proto, NULL, kind);
3064 obj->setArrayLength(length);
3066 if (allocateCapacity && !obj->ensureSlots(cx, length))
3072 JSObject * JS_FASTCALL
3073 NewDenseEmptyArray(JSContext *cx, JSObject *proto)
3075 return NewArray<false>(cx, 0, proto);
3078 JSObject * JS_FASTCALL
3079 NewDenseAllocatedArray(JSContext *cx, uint32 length, JSObject *proto)
3081 return NewArray<true>(cx, length, proto);
3084 JSObject * JS_FASTCALL
3085 NewDenseUnallocatedArray(JSContext *cx, uint32 length, JSObject *proto)
3087 return NewArray<false>(cx, length, proto);
3091 NewDenseCopiedArray(JSContext *cx, uintN length, Value *vp, JSObject *proto)
3093 JSObject* obj = NewArray<true>(cx, length, proto);
3097 JS_ASSERT(obj->getDenseArrayCapacity() >= length);
3100 memcpy(obj->getDenseArrayElements(), vp, length * sizeof(Value));
3106 JS_DEFINE_CALLINFO_2(extern, OBJECT, NewDenseEmptyArray, CONTEXT, OBJECT, 0,
3107 nanojit::ACCSET_STORE_ANY)
3108 JS_DEFINE_CALLINFO_3(extern, OBJECT, NewDenseAllocatedArray, CONTEXT, UINT32, OBJECT, 0,
3109 nanojit::ACCSET_STORE_ANY)
3110 JS_DEFINE_CALLINFO_3(extern, OBJECT, NewDenseUnallocatedArray, CONTEXT, UINT32, OBJECT, 0,
3111 nanojit::ACCSET_STORE_ANY)
3117 NewSlowEmptyArray(JSContext *cx)
3119 JSObject *obj = NewNonFunction<WithProto::Class>(cx, &js_SlowArrayClass, NULL, NULL);
3120 if (!obj || !AddLengthProperty(cx, obj))
3123 obj->setArrayLength(0);
3132 js_ArrayInfo(JSContext *cx, uintN argc, jsval *vp)
3137 for (i = 0; i < argc; i++) {
3138 Value arg = Valueify(JS_ARGV(cx, vp)[i]);
3140 char *bytes = DecompileValueGenerator(cx, JSDVG_SEARCH_STACK, arg, NULL);
3143 if (arg.isPrimitive() ||
3144 !(array = arg.toObjectOrNull())->isArray()) {
3145 fprintf(stderr, "%s: not array\n", bytes);
3149 fprintf(stderr, "%s: %s (len %u", bytes,
3150 array->isDenseArray() ? "dense" : "sparse",
3151 array->getArrayLength());
3152 if (array->isDenseArray()) {
3153 fprintf(stderr, ", capacity %u",
3154 array->getDenseArrayCapacity());
3156 fputs(")\n", stderr);
3160 JS_SET_RVAL(cx, vp, JSVAL_VOID);
3165 JS_FRIEND_API(JSBool)
3166 js_CoerceArrayToCanvasImageData(JSObject *obj, jsuint offset, jsuint count,
3171 if (!obj || !obj->isDenseArray())
3174 length = obj->getArrayLength();
3175 if (length < offset + count)
3179 for (uintN i = offset; i < offset+count; i++) {
3180 const Value &v = obj->getDenseArrayElement(i);
3182 jsint vi = v.toInt32();
3183 if (jsuint(vi) > 255)
3184 vi = (vi < 0) ? 0 : 255;
3185 *dp++ = JSUint8(vi);
3186 } else if (v.isDouble()) {
3187 jsdouble vd = v.toDouble();
3188 if (!(vd >= 0)) /* Not < so that NaN coerces to 0 */
3193 jsdouble toTruncate = vd + 0.5;
3194 JSUint8 val = JSUint8(toTruncate);
3197 * now val is rounded to nearest, ties rounded up. We want
3198 * rounded to nearest ties to even, so check whether we had a
3201 if (val == toTruncate) {
3203 * It was a tie (since adding 0.5 gave us the exact integer
3204 * we want). Since we rounded up, we either already have an
3205 * even number or we have an odd number but the number we
3206 * want is one less. So just unconditionally masking out the
3207 * ones bit should do the trick to get us the value we
3223 JS_FRIEND_API(JSBool)
3224 js_IsDensePrimitiveArray(JSObject *obj)
3226 if (!obj || !obj->isDenseArray())
3229 jsuint capacity = obj->getDenseArrayCapacity();
3230 for (jsuint i = 0; i < capacity; i++) {
3231 if (obj->getDenseArrayElement(i).isObject())
3238 JS_FRIEND_API(JSBool)
3239 js_CloneDensePrimitiveArray(JSContext *cx, JSObject *obj, JSObject **clone)
3242 if (!obj->isDenseArray()) {
3244 * This wasn't a dense array. Return JS_TRUE but a NULL clone to signal
3245 * that no exception was encountered.
3251 jsuint length = obj->getArrayLength();
3254 * Must use the minimum of original array's length and capacity, to handle
3255 * |a = [1,2,3]; a.length = 10000| "dense" cases efficiently. In the normal
3256 * case where length is <= capacity, the clone and original array will have
3257 * the same capacity.
3259 jsuint jsvalCount = JS_MIN(obj->getDenseArrayCapacity(), length);
3261 js::AutoValueVector vector(cx);
3262 if (!vector.reserve(jsvalCount))
3265 for (jsuint i = 0; i < jsvalCount; i++) {
3266 const Value &val = obj->getDenseArrayElement(i);
3268 if (val.isString()) {
3269 // Strings must be made immutable before being copied to a clone.
3270 if (!js_MakeStringImmutable(cx, val.toString()))
3272 } else if (val.isObject()) {
3274 * This wasn't an array of primitives. Return JS_TRUE but a null
3275 * clone to signal that no exception was encountered.
3284 *clone = NewDenseCopiedArray(cx, jsvalCount, vector.begin());
3288 /* The length will be set to the JS_MIN, above, but length might be larger. */
3289 (*clone)->setArrayLength(length);