michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jsarray.h"
michael@0: 
michael@0: #include "mozilla/ArrayUtils.h"
michael@0: #include "mozilla/DebugOnly.h"
michael@0: #include "mozilla/FloatingPoint.h"
michael@0: #include "mozilla/MathAlgorithms.h"
michael@0: 
michael@0: #include "jsapi.h"
michael@0: #include "jsatom.h"
michael@0: #include "jscntxt.h"
michael@0: #include "jsfriendapi.h"
michael@0: #include "jsfun.h"
michael@0: #include "jsiter.h"
michael@0: #include "jsnum.h"
michael@0: #include "jsobj.h"
michael@0: #include "jstypes.h"
michael@0: #include "jsutil.h"
michael@0: 
michael@0: #include "ds/Sort.h"
michael@0: #include "gc/Heap.h"
michael@0: #include "vm/ArgumentsObject.h"
michael@0: #include "vm/ForkJoin.h"
michael@0: #include "vm/Interpreter.h"
michael@0: #include "vm/NumericConversions.h"
michael@0: #include "vm/Shape.h"
michael@0: #include "vm/StringBuffer.h"
michael@0: 
michael@0: #include "jsatominlines.h"
michael@0: 
michael@0: #include "vm/ArgumentsObject-inl.h"
michael@0: #include "vm/ArrayObject-inl.h"
michael@0: #include "vm/Interpreter-inl.h"
michael@0: #include "vm/Runtime-inl.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::gc;
michael@0: using namespace js::types;
michael@0: 
michael@0: using mozilla::Abs;
michael@0: using mozilla::ArrayLength;
michael@0: using mozilla::CeilingLog2;
michael@0: using mozilla::DebugOnly;
michael@0: using mozilla::IsNaN;
michael@0: using mozilla::PointerRangeSize;
michael@0: 
michael@0: bool
michael@0: js::GetLengthProperty(JSContext *cx, HandleObject obj, uint32_t *lengthp)
michael@0: {
michael@0:     if (obj->is<ArrayObject>()) {
michael@0:         *lengthp = obj->as<ArrayObject>().length();
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (obj->is<ArgumentsObject>()) {
michael@0:         ArgumentsObject &argsobj = obj->as<ArgumentsObject>();
michael@0:         if (!argsobj.hasOverriddenLength()) {
michael@0:             *lengthp = argsobj.initialLength();
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     RootedValue value(cx);
michael@0:     if (!JSObject::getProperty(cx, obj, obj, cx->names().length, &value))
michael@0:         return false;
michael@0: 
michael@0:     if (value.isInt32()) {
michael@0:         *lengthp = uint32_t(value.toInt32()); // uint32_t cast does ToUint32
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     return ToUint32(cx, value, lengthp);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Determine if the id represents an array index.
michael@0:  *
michael@0:  * An id is an array index according to ECMA by (15.4):
michael@0:  *
michael@0:  * "Array objects give special treatment to a certain class of property names.
michael@0:  * A property name P (in the form of a string value) is an array index if and
michael@0:  * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
michael@0:  * to 2^32-1."
michael@0:  *
michael@0:  * This means the largest allowed index is actually 2^32-2 (4294967294).
michael@0:  *
michael@0:  * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
michael@0:  * except that by using signed 31-bit integers we miss the top half of the
michael@0:  * valid range. This function checks the string representation itself; note
michael@0:  * that calling a standard conversion routine might allow strings such as
michael@0:  * "08" or "4.0" as array indices, which they are not.
michael@0:  *
michael@0:  */
michael@0: JS_FRIEND_API(bool)
michael@0: js::StringIsArrayIndex(JSLinearString *str, uint32_t *indexp)
michael@0: {
michael@0:     const jschar *s = str->chars();
michael@0:     uint32_t length = str->length();
michael@0:     const jschar *end = s + length;
michael@0: 
michael@0:     if (length == 0 || length > (sizeof("4294967294") - 1) || !JS7_ISDEC(*s))
michael@0:         return false;
michael@0: 
michael@0:     uint32_t c = 0, previous = 0;
michael@0:     uint32_t index = JS7_UNDEC(*s++);
michael@0: 
michael@0:     /* Don't allow leading zeros. */
michael@0:     if (index == 0 && s != end)
michael@0:         return false;
michael@0: 
michael@0:     for (; s < end; s++) {
michael@0:         if (!JS7_ISDEC(*s))
michael@0:             return false;
michael@0: 
michael@0:         previous = index;
michael@0:         c = JS7_UNDEC(*s);
michael@0:         index = 10 * index + c;
michael@0:     }
michael@0: 
michael@0:     /* Make sure we didn't overflow. */
michael@0:     if (previous < (MAX_ARRAY_INDEX / 10) || (previous == (MAX_ARRAY_INDEX / 10) &&
michael@0:         c <= (MAX_ARRAY_INDEX % 10))) {
michael@0:         JS_ASSERT(index <= MAX_ARRAY_INDEX);
michael@0:         *indexp = index;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: ToId(JSContext *cx, double index, MutableHandleId id)
michael@0: {
michael@0:     if (index == uint32_t(index))
michael@0:         return IndexToId(cx, uint32_t(index), id);
michael@0: 
michael@0:     Value tmp = DoubleValue(index);
michael@0:     return ValueToId<CanGC>(cx, HandleValue::fromMarkedLocation(&tmp), id);
michael@0: }
michael@0: 
michael@0: static bool
michael@0: ToId(JSContext *cx, uint32_t index, MutableHandleId id)
michael@0: {
michael@0:     return IndexToId(cx, index, id);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * If the property at the given index exists, get its value into location
michael@0:  * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
michael@0:  * to JSVAL_VOID. This function assumes that the location pointed by vp is
michael@0:  * properly rooted and can be used as GC-protected storage for temporaries.
michael@0:  */
michael@0: template<typename IndexType>
michael@0: static inline bool
michael@0: DoGetElement(JSContext *cx, HandleObject obj, HandleObject receiver,
michael@0:              IndexType index, bool *hole, MutableHandleValue vp)
michael@0: {
michael@0:     RootedId id(cx);
michael@0:     if (!ToId(cx, index, &id))
michael@0:         return false;
michael@0: 
michael@0:     RootedObject obj2(cx);
michael@0:     RootedShape prop(cx);
michael@0:     if (!JSObject::lookupGeneric(cx, obj, id, &obj2, &prop))
michael@0:         return false;
michael@0: 
michael@0:     if (!prop) {
michael@0:         vp.setUndefined();
michael@0:         *hole = true;
michael@0:     } else {
michael@0:         if (!JSObject::getGeneric(cx, obj, receiver, id, vp))
michael@0:             return false;
michael@0:         *hole = false;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: template<typename IndexType>
michael@0: static void
michael@0: AssertGreaterThanZero(IndexType index)
michael@0: {
michael@0:     JS_ASSERT(index >= 0);
michael@0:     JS_ASSERT(index == floor(index));
michael@0: }
michael@0: 
michael@0: template<>
michael@0: void
michael@0: AssertGreaterThanZero(uint32_t index)
michael@0: {
michael@0: }
michael@0: 
michael@0: template<typename IndexType>
michael@0: static bool
michael@0: GetElement(JSContext *cx, HandleObject obj, HandleObject receiver,
michael@0:            IndexType index, bool *hole, MutableHandleValue vp)
michael@0: {
michael@0:     AssertGreaterThanZero(index);
michael@0:     if (obj->isNative() && index < obj->getDenseInitializedLength()) {
michael@0:         vp.set(obj->getDenseElement(uint32_t(index)));
michael@0:         if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
michael@0:             *hole = false;
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0:     if (obj->is<ArgumentsObject>()) {
michael@0:         if (obj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
michael@0:             *hole = false;
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return DoGetElement(cx, obj, receiver, index, hole, vp);
michael@0: }
michael@0: 
michael@0: template<typename IndexType>
michael@0: static inline bool
michael@0: GetElement(JSContext *cx, HandleObject obj, IndexType index, bool *hole, MutableHandleValue vp)
michael@0: {
michael@0:     return GetElement(cx, obj, obj, index, hole, vp);
michael@0: }
michael@0: 
michael@0: static bool
michael@0: GetElementsSlow(JSContext *cx, HandleObject aobj, uint32_t length, Value *vp)
michael@0: {
michael@0:     for (uint32_t i = 0; i < length; i++) {
michael@0:         if (!JSObject::getElement(cx, aobj, aobj, i, MutableHandleValue::fromMarkedLocation(&vp[i])))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: js::GetElements(JSContext *cx, HandleObject aobj, uint32_t length, Value *vp)
michael@0: {
michael@0:     if (aobj->is<ArrayObject>() && length <= aobj->getDenseInitializedLength() &&
michael@0:         !ObjectMayHaveExtraIndexedProperties(aobj))
michael@0:     {
michael@0:         /* No other indexed properties so hole = undefined */
michael@0:         const Value *srcbeg = aobj->getDenseElements();
michael@0:         const Value *srcend = srcbeg + length;
michael@0:         const Value *src = srcbeg;
michael@0:         for (Value *dst = vp; src < srcend; ++dst, ++src)
michael@0:             *dst = src->isMagic(JS_ELEMENTS_HOLE) ? UndefinedValue() : *src;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (aobj->is<ArgumentsObject>()) {
michael@0:         ArgumentsObject &argsobj = aobj->as<ArgumentsObject>();
michael@0:         if (!argsobj.hasOverriddenLength()) {
michael@0:             if (argsobj.maybeGetElements(0, length, vp))
michael@0:                 return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return GetElementsSlow(cx, aobj, length, vp);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Set the value of the property at the given index to v assuming v is rooted.
michael@0:  */
michael@0: static bool
michael@0: SetArrayElement(JSContext *cx, HandleObject obj, double index, HandleValue v)
michael@0: {
michael@0:     JS_ASSERT(index >= 0);
michael@0: 
michael@0:     if (obj->is<ArrayObject>() && !obj->isIndexed()) {
michael@0:         Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0:         /* Predicted/prefetched code should favor the remains-dense case. */
michael@0:         JSObject::EnsureDenseResult result = JSObject::ED_SPARSE;
michael@0:         do {
michael@0:             if (index > uint32_t(-1))
michael@0:                 break;
michael@0:             uint32_t idx = uint32_t(index);
michael@0:             if (idx >= arr->length() && !arr->lengthIsWritable()) {
michael@0:                 JS_ReportErrorFlagsAndNumber(cx, JSREPORT_ERROR, js_GetErrorMessage, nullptr,
michael@0:                                              JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
michael@0:                 return false;
michael@0:             }
michael@0:             result = arr->ensureDenseElements(cx, idx, 1);
michael@0:             if (result != JSObject::ED_OK)
michael@0:                 break;
michael@0:             if (idx >= arr->length())
michael@0:                 arr->setLengthInt32(idx + 1);
michael@0:             arr->setDenseElementWithType(cx, idx, v);
michael@0:             return true;
michael@0:         } while (false);
michael@0: 
michael@0:         if (result == JSObject::ED_FAILED)
michael@0:             return false;
michael@0:         JS_ASSERT(result == JSObject::ED_SPARSE);
michael@0:     }
michael@0: 
michael@0:     RootedId id(cx);
michael@0:     if (!ToId(cx, index, &id))
michael@0:         return false;
michael@0: 
michael@0:     RootedValue tmp(cx, v);
michael@0:     return JSObject::setGeneric(cx, obj, obj, id, &tmp, true);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Attempt to delete the element |index| from |obj| as if by
michael@0:  * |obj.[[Delete]](index)|.
michael@0:  *
michael@0:  * If an error occurs while attempting to delete the element (that is, the call
michael@0:  * to [[Delete]] threw), return false.
michael@0:  *
michael@0:  * Otherwise set *succeeded to indicate whether the deletion attempt succeeded
michael@0:  * (that is, whether the call to [[Delete]] returned true or false).  (Deletes
michael@0:  * generally fail only when the property is non-configurable, but proxies may
michael@0:  * implement different semantics.)
michael@0:  */
michael@0: static bool
michael@0: DeleteArrayElement(JSContext *cx, HandleObject obj, double index, bool *succeeded)
michael@0: {
michael@0:     JS_ASSERT(index >= 0);
michael@0:     JS_ASSERT(floor(index) == index);
michael@0: 
michael@0:     if (obj->is<ArrayObject>() && !obj->isIndexed()) {
michael@0:         if (index <= UINT32_MAX) {
michael@0:             uint32_t idx = uint32_t(index);
michael@0:             if (idx < obj->getDenseInitializedLength()) {
michael@0:                 obj->markDenseElementsNotPacked(cx);
michael@0:                 obj->setDenseElement(idx, MagicValue(JS_ELEMENTS_HOLE));
michael@0:                 if (!js_SuppressDeletedElement(cx, obj, idx))
michael@0:                     return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         *succeeded = true;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (index <= UINT32_MAX)
michael@0:         return JSObject::deleteElement(cx, obj, uint32_t(index), succeeded);
michael@0: 
michael@0:     return JSObject::deleteByValue(cx, obj, DoubleValue(index), succeeded);
michael@0: }
michael@0: 
michael@0: /* ES6 20130308 draft 9.3.5 */
michael@0: static bool
michael@0: DeletePropertyOrThrow(JSContext *cx, HandleObject obj, double index)
michael@0: {
michael@0:     bool succeeded;
michael@0:     if (!DeleteArrayElement(cx, obj, index, &succeeded))
michael@0:         return false;
michael@0:     if (succeeded)
michael@0:         return true;
michael@0: 
michael@0:     RootedId id(cx);
michael@0:     RootedValue indexv(cx, NumberValue(index));
michael@0:     if (!ValueToId<CanGC>(cx, indexv, &id))
michael@0:         return false;
michael@0:     return obj->reportNotConfigurable(cx, id, JSREPORT_ERROR);
michael@0: }
michael@0: 
michael@0: bool
michael@0: js::SetLengthProperty(JSContext *cx, HandleObject obj, double length)
michael@0: {
michael@0:     RootedValue v(cx, NumberValue(length));
michael@0:     return JSObject::setProperty(cx, obj, obj, cx->names().length, &v, true);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Since SpiderMonkey supports cross-class prototype-based delegation, we have
michael@0:  * to be careful about the length getter and setter being called on an object
michael@0:  * not of Array class. For the getter, we search obj's prototype chain for the
michael@0:  * array that caused this getter to be invoked. In the setter case to overcome
michael@0:  * the JSPROP_SHARED attribute, we must define a shadowing length property.
michael@0:  */
michael@0: static bool
michael@0: array_length_getter(JSContext *cx, HandleObject obj_, HandleId id, MutableHandleValue vp)
michael@0: {
michael@0:     RootedObject obj(cx, obj_);
michael@0:     do {
michael@0:         if (obj->is<ArrayObject>()) {
michael@0:             vp.setNumber(obj->as<ArrayObject>().length());
michael@0:             return true;
michael@0:         }
michael@0:         if (!JSObject::getProto(cx, obj, &obj))
michael@0:             return false;
michael@0:     } while (obj);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_length_setter(JSContext *cx, HandleObject obj, HandleId id, bool strict, MutableHandleValue vp)
michael@0: {
michael@0:     if (!obj->is<ArrayObject>()) {
michael@0:         return JSObject::defineProperty(cx, obj, cx->names().length, vp,
michael@0:                                         nullptr, nullptr, JSPROP_ENUMERATE);
michael@0:     }
michael@0: 
michael@0:     Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0:     MOZ_ASSERT(arr->lengthIsWritable(),
michael@0:                "setter shouldn't be called if property is non-writable");
michael@0:     return ArraySetLength<SequentialExecution>(cx, arr, id, JSPROP_PERMANENT, vp, strict);
michael@0: }
michael@0: 
michael@0: struct ReverseIndexComparator
michael@0: {
michael@0:     bool operator()(const uint32_t& a, const uint32_t& b, bool *lessOrEqualp) {
michael@0:         MOZ_ASSERT(a != b, "how'd we get duplicate indexes?");
michael@0:         *lessOrEqualp = b <= a;
michael@0:         return true;
michael@0:     }
michael@0: };
michael@0: 
michael@0: template <ExecutionMode mode>
michael@0: bool
michael@0: js::CanonicalizeArrayLengthValue(typename ExecutionModeTraits<mode>::ContextType cx,
michael@0:                                  HandleValue v, uint32_t *newLen)
michael@0: {
michael@0:     double d;
michael@0: 
michael@0:     if (mode == ParallelExecution) {
michael@0:         if (v.isObject())
michael@0:             return false;
michael@0: 
michael@0:         if (!NonObjectToUint32(cx, v, newLen))
michael@0:             return false;
michael@0: 
michael@0:         if (!NonObjectToNumber(cx, v, &d))
michael@0:             return false;
michael@0:     } else {
michael@0:         if (!ToUint32(cx->asJSContext(), v, newLen))
michael@0:             return false;
michael@0: 
michael@0:         if (!ToNumber(cx->asJSContext(), v, &d))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     if (d == *newLen)
michael@0:         return true;
michael@0: 
michael@0:     if (cx->isJSContext())
michael@0:         JS_ReportErrorNumber(cx->asJSContext(), js_GetErrorMessage, nullptr,
michael@0:                              JSMSG_BAD_ARRAY_LENGTH);
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: template bool
michael@0: js::CanonicalizeArrayLengthValue<SequentialExecution>(JSContext *cx,
michael@0:                                                       HandleValue v, uint32_t *newLen);
michael@0: template bool
michael@0: js::CanonicalizeArrayLengthValue<ParallelExecution>(ForkJoinContext *cx,
michael@0:                                                     HandleValue v, uint32_t *newLen);
michael@0: 
michael@0: /* ES6 20130308 draft 8.4.2.4 ArraySetLength */
michael@0: template <ExecutionMode mode>
michael@0: bool
michael@0: js::ArraySetLength(typename ExecutionModeTraits<mode>::ContextType cxArg,
michael@0:                    Handle<ArrayObject*> arr, HandleId id,
michael@0:                    unsigned attrs, HandleValue value, bool setterIsStrict)
michael@0: {
michael@0:     MOZ_ASSERT(cxArg->isThreadLocal(arr));
michael@0:     MOZ_ASSERT(id == NameToId(cxArg->names().length));
michael@0: 
michael@0:     /* Steps 1-2 are irrelevant in our implementation. */
michael@0: 
michael@0:     /* Steps 3-5. */
michael@0:     uint32_t newLen;
michael@0:     if (!CanonicalizeArrayLengthValue<mode>(cxArg, value, &newLen))
michael@0:         return false;
michael@0: 
michael@0:     // Abort if we're being asked to change enumerability or configurability.
michael@0:     // (The length property of arrays is non-configurable, so such attempts
michael@0:     // must fail.)  This behavior is spread throughout the ArraySetLength spec
michael@0:     // algorithm, but we only need check it once as our array implementation
michael@0:     // is internally so different from the spec algorithm.  (ES5 and ES6 define
michael@0:     // behavior by delegating to the default define-own-property algorithm --
michael@0:     // OrdinaryDefineOwnProperty in ES6, the default [[DefineOwnProperty]] in
michael@0:     // ES5 -- but we reimplement all the conflict-detection bits ourselves here
michael@0:     // so that we can use a customized length representation.)
michael@0:     if (!(attrs & JSPROP_PERMANENT) || (attrs & JSPROP_ENUMERATE)) {
michael@0:         if (!setterIsStrict)
michael@0:             return true;
michael@0:         // Bail for strict mode in parallel execution, as we need to go back
michael@0:         // to sequential mode to throw the error.
michael@0:         if (mode == ParallelExecution)
michael@0:             return false;
michael@0:         return Throw(cxArg->asJSContext(), id, JSMSG_CANT_REDEFINE_PROP);
michael@0:     }
michael@0: 
michael@0:     /* Steps 6-7. */
michael@0:     bool lengthIsWritable = arr->lengthIsWritable();
michael@0: #ifdef DEBUG
michael@0:     {
michael@0:         RootedShape lengthShape(cxArg, arr->nativeLookupPure(id));
michael@0:         MOZ_ASSERT(lengthShape);
michael@0:         MOZ_ASSERT(lengthShape->writable() == lengthIsWritable);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     uint32_t oldLen = arr->length();
michael@0: 
michael@0:     /* Steps 8-9 for arrays with non-writable length. */
michael@0:     if (!lengthIsWritable) {
michael@0:         if (newLen == oldLen)
michael@0:             return true;
michael@0: 
michael@0:         if (!cxArg->isJSContext())
michael@0:             return false;
michael@0: 
michael@0:         if (setterIsStrict) {
michael@0:             return JS_ReportErrorFlagsAndNumber(cxArg->asJSContext(),
michael@0:                                                 JSREPORT_ERROR, js_GetErrorMessage, nullptr,
michael@0:                                                 JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
michael@0:         }
michael@0: 
michael@0:         return JSObject::reportReadOnly(cxArg->asJSContext(), id,
michael@0:                                         JSREPORT_STRICT | JSREPORT_WARNING);
michael@0:     }
michael@0: 
michael@0:     /* Step 8. */
michael@0:     bool succeeded = true;
michael@0:     do {
michael@0:         // The initialized length and capacity of an array only need updating
michael@0:         // when non-hole elements are added or removed, which doesn't happen
michael@0:         // when array length stays the same or increases.
michael@0:         if (newLen >= oldLen)
michael@0:             break;
michael@0: 
michael@0:         // Attempt to propagate dense-element optimization tricks, if possible,
michael@0:         // and avoid the generic (and accordingly slow) deletion code below.
michael@0:         // We can only do this if there are only densely-indexed elements.
michael@0:         // Once there's a sparse indexed element, there's no good way to know,
michael@0:         // save by enumerating all the properties to find it.  But we *have* to
michael@0:         // know in case that sparse indexed element is non-configurable, as
michael@0:         // that element must prevent any deletions below it.  Bug 586842 should
michael@0:         // fix this inefficiency by moving indexed storage to be entirely
michael@0:         // separate from non-indexed storage.
michael@0:         if (!arr->isIndexed()) {
michael@0:             uint32_t oldCapacity = arr->getDenseCapacity();
michael@0:             uint32_t oldInitializedLength = arr->getDenseInitializedLength();
michael@0:             MOZ_ASSERT(oldCapacity >= oldInitializedLength);
michael@0:             if (oldInitializedLength > newLen)
michael@0:                 arr->setDenseInitializedLength(newLen);
michael@0:             if (oldCapacity > newLen)
michael@0:                 arr->shrinkElements(cxArg, newLen);
michael@0: 
michael@0:             // We've done the work of deleting any dense elements needing
michael@0:             // deletion, and there are no sparse elements.  Thus we can skip
michael@0:             // straight to defining the length.
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         // Bail from parallel execution if need to perform step 15, which is
michael@0:         // unsafe and isn't a common case.
michael@0:         if (mode == ParallelExecution)
michael@0:             return false;
michael@0: 
michael@0:         JSContext *cx = cxArg->asJSContext();
michael@0: 
michael@0:         // Step 15.
michael@0:         //
michael@0:         // Attempt to delete all elements above the new length, from greatest
michael@0:         // to least.  If any of these deletions fails, we're supposed to define
michael@0:         // the length to one greater than the index that couldn't be deleted,
michael@0:         // *with the property attributes specified*.  This might convert the
michael@0:         // length to be not the value specified, yet non-writable.  (You may be
michael@0:         // forgiven for thinking these are interesting semantics.)  Example:
michael@0:         //
michael@0:         //   var arr =
michael@0:         //     Object.defineProperty([0, 1, 2, 3], 1, { writable: false });
michael@0:         //   Object.defineProperty(arr, "length",
michael@0:         //                         { value: 0, writable: false });
michael@0:         //
michael@0:         // will convert |arr| to an array of non-writable length two, then
michael@0:         // throw a TypeError.
michael@0:         //
michael@0:         // We implement this behavior, in the relevant lops below, by setting
michael@0:         // |succeeded| to false.  Then we exit the loop, define the length
michael@0:         // appropriately, and only then throw a TypeError, if necessary.
michael@0:         uint32_t gap = oldLen - newLen;
michael@0:         const uint32_t RemoveElementsFastLimit = 1 << 24;
michael@0:         if (gap < RemoveElementsFastLimit) {
michael@0:             // If we're removing a relatively small number of elements, just do
michael@0:             // it exactly by the spec.
michael@0:             while (newLen < oldLen) {
michael@0:                 /* Step 15a. */
michael@0:                 oldLen--;
michael@0: 
michael@0:                 /* Steps 15b-d. */
michael@0:                 bool deleteSucceeded;
michael@0:                 if (!JSObject::deleteElement(cx, arr, oldLen, &deleteSucceeded))
michael@0:                     return false;
michael@0:                 if (!deleteSucceeded) {
michael@0:                     newLen = oldLen + 1;
michael@0:                     succeeded = false;
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0:         } else {
michael@0:             // If we're removing a large number of elements from an array
michael@0:             // that's probably sparse, try a different tack.  Get all the own
michael@0:             // property names, sift out the indexes in the deletion range into
michael@0:             // a vector, sort the vector greatest to least, then delete the
michael@0:             // indexes greatest to least using that vector.  See bug 322135.
michael@0:             //
michael@0:             // This heuristic's kind of a huge guess -- "large number of
michael@0:             // elements" and "probably sparse" are completely unprincipled
michael@0:             // predictions.  In the long run, bug 586842 will support the right
michael@0:             // fix: store sparse elements in a sorted data structure that
michael@0:             // permits fast in-reverse-order traversal and concurrent removals.
michael@0: 
michael@0:             Vector<uint32_t> indexes(cx);
michael@0:             {
michael@0:                 AutoIdVector props(cx);
michael@0:                 if (!GetPropertyNames(cx, arr, JSITER_OWNONLY | JSITER_HIDDEN, &props))
michael@0:                     return false;
michael@0: 
michael@0:                 for (size_t i = 0; i < props.length(); i++) {
michael@0:                     if (!CheckForInterrupt(cx))
michael@0:                         return false;
michael@0: 
michael@0:                     uint32_t index;
michael@0:                     if (!js_IdIsIndex(props[i], &index))
michael@0:                         continue;
michael@0: 
michael@0:                     if (index >= newLen && index < oldLen) {
michael@0:                         if (!indexes.append(index))
michael@0:                             return false;
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             uint32_t count = indexes.length();
michael@0:             {
michael@0:                 // We should use radix sort to be O(n), but this is uncommon
michael@0:                 // enough that we'll punt til someone complains.
michael@0:                 Vector<uint32_t> scratch(cx);
michael@0:                 if (!scratch.resize(count))
michael@0:                     return false;
michael@0:                 MOZ_ALWAYS_TRUE(MergeSort(indexes.begin(), count, scratch.begin(),
michael@0:                                           ReverseIndexComparator()));
michael@0:             }
michael@0: 
michael@0:             uint32_t index = UINT32_MAX;
michael@0:             for (uint32_t i = 0; i < count; i++) {
michael@0:                 MOZ_ASSERT(indexes[i] < index, "indexes should never repeat");
michael@0:                 index = indexes[i];
michael@0: 
michael@0:                 /* Steps 15b-d. */
michael@0:                 bool deleteSucceeded;
michael@0:                 if (!JSObject::deleteElement(cx, arr, index, &deleteSucceeded))
michael@0:                     return false;
michael@0:                 if (!deleteSucceeded) {
michael@0:                     newLen = index + 1;
michael@0:                     succeeded = false;
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     } while (false);
michael@0: 
michael@0:     /* Steps 12, 16. */
michael@0: 
michael@0:     // Yes, we totally drop a non-stub getter/setter from a defineProperty
michael@0:     // API call on the floor here.  Given that getter/setter will go away in
michael@0:     // the long run, with accessors replacing them both internally and at the
michael@0:     // API level, just run with this.
michael@0:     RootedShape lengthShape(cxArg, mode == ParallelExecution
michael@0:                             ? arr->nativeLookupPure(id)
michael@0:                             : arr->nativeLookup(cxArg->asJSContext(), id));
michael@0:     if (!JSObject::changeProperty<mode>(cxArg, arr, lengthShape, attrs,
michael@0:                                         JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_SHARED,
michael@0:                                         array_length_getter, array_length_setter))
michael@0:     {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     if (mode == ParallelExecution) {
michael@0:         // Overflowing int32 requires changing TI state.
michael@0:         if (newLen > INT32_MAX)
michael@0:             return false;
michael@0:         arr->setLengthInt32(newLen);
michael@0:     } else {
michael@0:         JSContext *cx = cxArg->asJSContext();
michael@0:         arr->setLength(cx, newLen);
michael@0:     }
michael@0: 
michael@0: 
michael@0:     // All operations past here until the |!succeeded| code must be infallible,
michael@0:     // so that all element fields remain properly synchronized.
michael@0: 
michael@0:     // Trim the initialized length, if needed, to preserve the <= length
michael@0:     // invariant.  (Capacity was already reduced during element deletion, if
michael@0:     // necessary.)
michael@0:     ObjectElements *header = arr->getElementsHeader();
michael@0:     header->initializedLength = Min(header->initializedLength, newLen);
michael@0: 
michael@0:     if (attrs & JSPROP_READONLY) {
michael@0:         header->setNonwritableArrayLength();
michael@0: 
michael@0:         // When an array's length becomes non-writable, writes to indexes
michael@0:         // greater than or equal to the length don't change the array.  We
michael@0:         // handle this with a check for non-writable length in most places.
michael@0:         // But in JIT code every check counts -- so we piggyback the check on
michael@0:         // the already-required range check for |index < capacity| by making
michael@0:         // capacity of arrays with non-writable length never exceed the length.
michael@0:         if (arr->getDenseCapacity() > newLen) {
michael@0:             arr->shrinkElements(cxArg, newLen);
michael@0:             arr->getElementsHeader()->capacity = newLen;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (setterIsStrict && !succeeded) {
michael@0:         // We can't have arrived here under ParallelExecution, as we have
michael@0:         // returned from the function before step 15 above.
michael@0:         JSContext *cx = cxArg->asJSContext();
michael@0:         RootedId elementId(cx);
michael@0:         if (!IndexToId(cx, newLen - 1, &elementId))
michael@0:             return false;
michael@0:         return arr->reportNotConfigurable(cx, elementId);
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: template bool
michael@0: js::ArraySetLength<SequentialExecution>(JSContext *cx, Handle<ArrayObject*> arr,
michael@0:                                         HandleId id, unsigned attrs, HandleValue value,
michael@0:                                         bool setterIsStrict);
michael@0: template bool
michael@0: js::ArraySetLength<ParallelExecution>(ForkJoinContext *cx, Handle<ArrayObject*> arr,
michael@0:                                       HandleId id, unsigned attrs, HandleValue value,
michael@0:                                       bool setterIsStrict);
michael@0: 
michael@0: bool
michael@0: js::WouldDefinePastNonwritableLength(ThreadSafeContext *cx,
michael@0:                                      HandleObject obj, uint32_t index, bool strict,
michael@0:                                      bool *definesPast)
michael@0: {
michael@0:     if (!obj->is<ArrayObject>()) {
michael@0:         *definesPast = false;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0:     uint32_t length = arr->length();
michael@0:     if (index < length) {
michael@0:         *definesPast = false;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (arr->lengthIsWritable()) {
michael@0:         *definesPast = false;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     *definesPast = true;
michael@0: 
michael@0:     // Error in strict mode code or warn with strict option.
michael@0:     unsigned flags = strict ? JSREPORT_ERROR : (JSREPORT_STRICT | JSREPORT_WARNING);
michael@0:     if (cx->isForkJoinContext())
michael@0:         return cx->asForkJoinContext()->reportError(ParallelBailoutUnsupportedVM, flags);
michael@0: 
michael@0:     if (!cx->isJSContext())
michael@0:         return true;
michael@0: 
michael@0:     JSContext *ncx = cx->asJSContext();
michael@0: 
michael@0:     if (!strict && !ncx->options().extraWarnings())
michael@0:         return true;
michael@0: 
michael@0:     // XXX include the index and maybe array length in the error message
michael@0:     return JS_ReportErrorFlagsAndNumber(ncx, flags, js_GetErrorMessage, nullptr,
michael@0:                                         JSMSG_CANT_DEFINE_PAST_ARRAY_LENGTH);
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_addProperty(JSContext *cx, HandleObject obj, HandleId id, MutableHandleValue vp)
michael@0: {
michael@0:     Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0: 
michael@0:     uint32_t index;
michael@0:     if (!js_IdIsIndex(id, &index))
michael@0:         return true;
michael@0: 
michael@0:     uint32_t length = arr->length();
michael@0:     if (index >= length) {
michael@0:         MOZ_ASSERT(arr->lengthIsWritable(),
michael@0:                    "how'd this element get added if length is non-writable?");
michael@0:         arr->setLength(cx, index + 1);
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: js::ObjectMayHaveExtraIndexedProperties(JSObject *obj)
michael@0: {
michael@0:     /*
michael@0:      * Whether obj may have indexed properties anywhere besides its dense
michael@0:      * elements. This includes other indexed properties in its shape hierarchy,
michael@0:      * and indexed properties or elements along its prototype chain.
michael@0:      */
michael@0: 
michael@0:     JS_ASSERT(obj->isNative());
michael@0: 
michael@0:     if (obj->isIndexed())
michael@0:         return true;
michael@0: 
michael@0:     /*
michael@0:      * Walk up the prototype chain and see if this indexed element already
michael@0:      * exists. If we hit the end of the prototype chain, it's safe to set the
michael@0:      * element on the original object.
michael@0:      */
michael@0:     while ((obj = obj->getProto()) != nullptr) {
michael@0:         /*
michael@0:          * If the prototype is a non-native object (possibly a dense array), or
michael@0:          * a native object (possibly a slow array) that has indexed properties,
michael@0:          * return true.
michael@0:          */
michael@0:         if (!obj->isNative())
michael@0:             return true;
michael@0:         if (obj->isIndexed())
michael@0:             return true;
michael@0:         if (obj->getDenseInitializedLength() > 0)
michael@0:             return true;
michael@0:         if (obj->is<TypedArrayObject>())
michael@0:             return true;
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: const Class ArrayObject::class_ = {
michael@0:     "Array",
michael@0:     JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
michael@0:     array_addProperty,
michael@0:     JS_DeletePropertyStub,   /* delProperty */
michael@0:     JS_PropertyStub,         /* getProperty */
michael@0:     JS_StrictPropertyStub,   /* setProperty */
michael@0:     JS_EnumerateStub,
michael@0:     JS_ResolveStub,
michael@0:     JS_ConvertStub,
michael@0:     nullptr,
michael@0:     nullptr,        /* call        */
michael@0:     nullptr,        /* hasInstance */
michael@0:     nullptr,        /* construct   */
michael@0:     nullptr         /* trace       */
michael@0: };
michael@0: 
michael@0: static bool
michael@0: AddLengthProperty(ExclusiveContext *cx, HandleObject obj)
michael@0: {
michael@0:     /*
michael@0:      * Add the 'length' property for a newly created array,
michael@0:      * and update the elements to be an empty array owned by the object.
michael@0:      * The shared emptyObjectElements singleton cannot be used for slow arrays,
michael@0:      * as accesses to 'length' will use the elements header.
michael@0:      */
michael@0: 
michael@0:     RootedId lengthId(cx, NameToId(cx->names().length));
michael@0:     JS_ASSERT(!obj->nativeLookup(cx, lengthId));
michael@0: 
michael@0:     return JSObject::addProperty(cx, obj, lengthId, array_length_getter, array_length_setter,
michael@0:                                  SHAPE_INVALID_SLOT, JSPROP_PERMANENT | JSPROP_SHARED, 0,
michael@0:                                  /* allowDictionary = */ false);
michael@0: }
michael@0: 
michael@0: #if JS_HAS_TOSOURCE
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: IsArray(HandleValue v)
michael@0: {
michael@0:     return v.isObject() && v.toObject().is<ArrayObject>();
michael@0: }
michael@0: 
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: array_toSource_impl(JSContext *cx, CallArgs args)
michael@0: {
michael@0:     JS_ASSERT(IsArray(args.thisv()));
michael@0: 
michael@0:     Rooted<JSObject*> obj(cx, &args.thisv().toObject());
michael@0:     RootedValue elt(cx);
michael@0: 
michael@0:     AutoCycleDetector detector(cx, obj);
michael@0:     if (!detector.init())
michael@0:         return false;
michael@0: 
michael@0:     StringBuffer sb(cx);
michael@0: 
michael@0:     if (detector.foundCycle()) {
michael@0:         if (!sb.append("[]"))
michael@0:             return false;
michael@0:         goto make_string;
michael@0:     }
michael@0: 
michael@0:     if (!sb.append('['))
michael@0:         return false;
michael@0: 
michael@0:     uint32_t length;
michael@0:     if (!GetLengthProperty(cx, obj, &length))
michael@0:         return false;
michael@0: 
michael@0:     for (uint32_t index = 0; index < length; index++) {
michael@0:         bool hole;
michael@0:         if (!CheckForInterrupt(cx) ||
michael@0:             !GetElement(cx, obj, index, &hole, &elt)) {
michael@0:             return false;
michael@0:         }
michael@0: 
michael@0:         /* Get element's character string. */
michael@0:         JSString *str;
michael@0:         if (hole) {
michael@0:             str = cx->runtime()->emptyString;
michael@0:         } else {
michael@0:             str = ValueToSource(cx, elt);
michael@0:             if (!str)
michael@0:                 return false;
michael@0:         }
michael@0: 
michael@0:         /* Append element to buffer. */
michael@0:         if (!sb.append(str))
michael@0:             return false;
michael@0:         if (index + 1 != length) {
michael@0:             if (!sb.append(", "))
michael@0:                 return false;
michael@0:         } else if (hole) {
michael@0:             if (!sb.append(','))
michael@0:                 return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Finalize the buffer. */
michael@0:     if (!sb.append(']'))
michael@0:         return false;
michael@0: 
michael@0:   make_string:
michael@0:     JSString *str = sb.finishString();
michael@0:     if (!str)
michael@0:         return false;
michael@0: 
michael@0:     args.rval().setString(str);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_toSource(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     JS_CHECK_RECURSION(cx, return false);
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     return CallNonGenericMethod<IsArray, array_toSource_impl>(cx, args);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: struct EmptySeparatorOp
michael@0: {
michael@0:     bool operator()(JSContext *, StringBuffer &sb) { return true; }
michael@0: };
michael@0: 
michael@0: struct CharSeparatorOp
michael@0: {
michael@0:     jschar sep;
michael@0:     CharSeparatorOp(jschar sep) : sep(sep) {};
michael@0:     bool operator()(JSContext *, StringBuffer &sb) { return sb.append(sep); }
michael@0: };
michael@0: 
michael@0: struct StringSeparatorOp
michael@0: {
michael@0:     const jschar *sepchars;
michael@0:     size_t seplen;
michael@0: 
michael@0:     StringSeparatorOp(const jschar *sepchars, size_t seplen)
michael@0:       : sepchars(sepchars), seplen(seplen) {};
michael@0: 
michael@0:     bool operator()(JSContext *cx, StringBuffer &sb) {
michael@0:         return sb.append(sepchars, seplen);
michael@0:     }
michael@0: };
michael@0: 
michael@0: template <bool Locale, typename SeparatorOp>
michael@0: static bool
michael@0: ArrayJoinKernel(JSContext *cx, SeparatorOp sepOp, HandleObject obj, uint32_t length,
michael@0:                StringBuffer &sb)
michael@0: {
michael@0:     uint32_t i = 0;
michael@0: 
michael@0:     if (!Locale && obj->is<ArrayObject>() && !ObjectMayHaveExtraIndexedProperties(obj)) {
michael@0:         // This loop handles all elements up to initializedLength. If
michael@0:         // length > initLength we rely on the second loop to add the
michael@0:         // other elements.
michael@0:         uint32_t initLength = obj->getDenseInitializedLength();
michael@0:         while (i < initLength) {
michael@0:             if (!CheckForInterrupt(cx))
michael@0:                 return false;
michael@0: 
michael@0:             const Value &elem = obj->getDenseElement(i);
michael@0: 
michael@0:             if (elem.isString()) {
michael@0:                 if (!sb.append(elem.toString()))
michael@0:                     return false;
michael@0:             } else if (elem.isNumber()) {
michael@0:                 if (!NumberValueToStringBuffer(cx, elem, sb))
michael@0:                     return false;
michael@0:             } else if (elem.isBoolean()) {
michael@0:                 if (!BooleanToStringBuffer(elem.toBoolean(), sb))
michael@0:                     return false;
michael@0:             } else if (elem.isObject()) {
michael@0:                 /*
michael@0:                  * Object stringifying could modify the initialized length or make
michael@0:                  * the array sparse. Delegate it to a separate loop to keep this
michael@0:                  * one tight.
michael@0:                  */
michael@0:                 break;
michael@0:             } else {
michael@0:                 JS_ASSERT(elem.isMagic(JS_ELEMENTS_HOLE) || elem.isNullOrUndefined());
michael@0:             }
michael@0: 
michael@0:             if (++i != length && !sepOp(cx, sb))
michael@0:                 return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (i != length) {
michael@0:         RootedValue v(cx);
michael@0:         while (i < length) {
michael@0:             if (!CheckForInterrupt(cx))
michael@0:                 return false;
michael@0: 
michael@0:             bool hole;
michael@0:             if (!GetElement(cx, obj, i, &hole, &v))
michael@0:                 return false;
michael@0:             if (!hole && !v.isNullOrUndefined()) {
michael@0:                 if (Locale) {
michael@0:                     JSObject *robj = ToObject(cx, v);
michael@0:                     if (!robj)
michael@0:                         return false;
michael@0:                     RootedId id(cx, NameToId(cx->names().toLocaleString));
michael@0:                     if (!robj->callMethod(cx, id, 0, nullptr, &v))
michael@0:                         return false;
michael@0:                 }
michael@0:                 if (!ValueToStringBuffer(cx, v, sb))
michael@0:                     return false;
michael@0:             }
michael@0: 
michael@0:             if (++i != length && !sepOp(cx, sb))
michael@0:                 return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: template <bool Locale>
michael@0: static bool
michael@0: ArrayJoin(JSContext *cx, CallArgs &args)
michael@0: {
michael@0:     // This method is shared by Array.prototype.join and
michael@0:     // Array.prototype.toLocaleString. The steps in ES5 are nearly the same, so
michael@0:     // the annotations in this function apply to both toLocaleString and join.
michael@0: 
michael@0:     // Step 1
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     AutoCycleDetector detector(cx, obj);
michael@0:     if (!detector.init())
michael@0:         return false;
michael@0: 
michael@0:     if (detector.foundCycle()) {
michael@0:         args.rval().setString(cx->names().empty);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // Steps 2 and 3
michael@0:     uint32_t length;
michael@0:     if (!GetLengthProperty(cx, obj, &length))
michael@0:         return false;
michael@0: 
michael@0:     // Steps 4 and 5
michael@0:     RootedString sepstr(cx, nullptr);
michael@0:     const jschar *sepchars;
michael@0:     size_t seplen;
michael@0:     if (!Locale && args.hasDefined(0)) {
michael@0:         sepstr = ToString<CanGC>(cx, args[0]);
michael@0:         if (!sepstr)
michael@0:             return false;
michael@0:         sepchars = sepstr->getChars(cx);
michael@0:         if (!sepchars)
michael@0:             return false;
michael@0:         seplen = sepstr->length();
michael@0:     } else {
michael@0:         HandlePropertyName comma = cx->names().comma;
michael@0:         sepstr = comma;
michael@0:         sepchars = comma->chars();
michael@0:         seplen = comma->length();
michael@0:     }
michael@0: 
michael@0:     JS::Anchor<JSString*> anchor(sepstr);
michael@0: 
michael@0:     // Step 6 is implicit in the loops below.
michael@0: 
michael@0:     // An optimized version of a special case of steps 7-11: when length==1 and
michael@0:     // the 0th element is a string, ToString() of that element is a no-op and
michael@0:     // so it can be immediately returned as the result.
michael@0:     if (length == 1 && !Locale && obj->is<ArrayObject>() &&
michael@0:         obj->getDenseInitializedLength() == 1)
michael@0:     {
michael@0:         const Value &elem0 = obj->getDenseElement(0);
michael@0:         if (elem0.isString()) {
michael@0:             args.rval().setString(elem0.toString());
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     StringBuffer sb(cx);
michael@0: 
michael@0:     // The separator will be added |length - 1| times, reserve space for that
michael@0:     // so that we don't have to unnecessarily grow the buffer.
michael@0:     if (length > 0 && !sb.reserve(seplen * (length - 1)))
michael@0:         return false;
michael@0: 
michael@0:     // Various optimized versions of steps 7-10.
michael@0:     if (seplen == 0) {
michael@0:         EmptySeparatorOp op;
michael@0:         if (!ArrayJoinKernel<Locale>(cx, op, obj, length, sb))
michael@0:             return false;
michael@0:     } else if (seplen == 1) {
michael@0:         CharSeparatorOp op(sepchars[0]);
michael@0:         if (!ArrayJoinKernel<Locale>(cx, op, obj, length, sb))
michael@0:             return false;
michael@0:     } else {
michael@0:         StringSeparatorOp op(sepchars, seplen);
michael@0:         if (!ArrayJoinKernel<Locale>(cx, op, obj, length, sb))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // Step 11
michael@0:     JSString *str = sb.finishString();
michael@0:     if (!str)
michael@0:         return false;
michael@0:     args.rval().setString(str);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /* ES5 15.4.4.2. NB: The algorithm here differs from the one in ES3. */
michael@0: static bool
michael@0: array_toString(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     JS_CHECK_RECURSION(cx, return false);
michael@0: 
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     RootedValue join(cx, args.calleev());
michael@0:     if (!JSObject::getProperty(cx, obj, obj, cx->names().join, &join))
michael@0:         return false;
michael@0: 
michael@0:     if (!js_IsCallable(join)) {
michael@0:         JSString *str = JS_BasicObjectToString(cx, obj);
michael@0:         if (!str)
michael@0:             return false;
michael@0:         args.rval().setString(str);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     InvokeArgs args2(cx);
michael@0:     if (!args2.init(0))
michael@0:         return false;
michael@0: 
michael@0:     args2.setCallee(join);
michael@0:     args2.setThis(ObjectValue(*obj));
michael@0: 
michael@0:     /* Do the call. */
michael@0:     if (!Invoke(cx, args2))
michael@0:         return false;
michael@0:     args.rval().set(args2.rval());
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /* ES5 15.4.4.3 */
michael@0: static bool
michael@0: array_toLocaleString(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     JS_CHECK_RECURSION(cx, return false);
michael@0: 
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     return ArrayJoin<true>(cx, args);
michael@0: }
michael@0: 
michael@0: /* ES5 15.4.4.5 */
michael@0: static bool
michael@0: array_join(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     JS_CHECK_RECURSION(cx, return false);
michael@0: 
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     return ArrayJoin<false>(cx, args);
michael@0: }
michael@0: 
michael@0: static inline bool
michael@0: InitArrayTypes(JSContext *cx, TypeObject *type, const Value *vector, unsigned count)
michael@0: {
michael@0:     if (!type->unknownProperties()) {
michael@0:         AutoEnterAnalysis enter(cx);
michael@0: 
michael@0:         HeapTypeSet *types = type->getProperty(cx, JSID_VOID);
michael@0:         if (!types)
michael@0:             return false;
michael@0: 
michael@0:         for (unsigned i = 0; i < count; i++) {
michael@0:             if (vector[i].isMagic(JS_ELEMENTS_HOLE))
michael@0:                 continue;
michael@0:             Type valtype = GetValueType(vector[i]);
michael@0:             types->addType(cx, valtype);
michael@0:         }
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: enum ShouldUpdateTypes
michael@0: {
michael@0:     UpdateTypes = true,
michael@0:     DontUpdateTypes = false
michael@0: };
michael@0: 
michael@0: /* vector must point to rooted memory. */
michael@0: static bool
michael@0: InitArrayElements(JSContext *cx, HandleObject obj, uint32_t start, uint32_t count, const Value *vector, ShouldUpdateTypes updateTypes)
michael@0: {
michael@0:     JS_ASSERT(count <= MAX_ARRAY_INDEX);
michael@0: 
michael@0:     if (count == 0)
michael@0:         return true;
michael@0: 
michael@0:     types::TypeObject *type = obj->getType(cx);
michael@0:     if (!type)
michael@0:         return false;
michael@0:     if (updateTypes && !InitArrayTypes(cx, type, vector, count))
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * Optimize for dense arrays so long as adding the given set of elements
michael@0:      * wouldn't otherwise make the array slow or exceed a non-writable array
michael@0:      * length.
michael@0:      */
michael@0:     do {
michael@0:         if (!obj->is<ArrayObject>())
michael@0:             break;
michael@0:         if (ObjectMayHaveExtraIndexedProperties(obj))
michael@0:             break;
michael@0: 
michael@0:         if (obj->shouldConvertDoubleElements())
michael@0:             break;
michael@0: 
michael@0:         Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0: 
michael@0:         if (!arr->lengthIsWritable() && start + count > arr->length())
michael@0:             break;
michael@0: 
michael@0:         JSObject::EnsureDenseResult result = arr->ensureDenseElements(cx, start, count);
michael@0:         if (result != JSObject::ED_OK) {
michael@0:             if (result == JSObject::ED_FAILED)
michael@0:                 return false;
michael@0:             JS_ASSERT(result == JSObject::ED_SPARSE);
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         uint32_t newlen = start + count;
michael@0:         if (newlen > arr->length())
michael@0:             arr->setLengthInt32(newlen);
michael@0: 
michael@0:         JS_ASSERT(count < UINT32_MAX / sizeof(Value));
michael@0:         arr->copyDenseElements(start, vector, count);
michael@0:         JS_ASSERT_IF(count != 0, !arr->getDenseElement(newlen - 1).isMagic(JS_ELEMENTS_HOLE));
michael@0:         return true;
michael@0:     } while (false);
michael@0: 
michael@0:     const Value* end = vector + count;
michael@0:     while (vector < end && start <= MAX_ARRAY_INDEX) {
michael@0:         if (!CheckForInterrupt(cx) ||
michael@0:             !SetArrayElement(cx, obj, start++, HandleValue::fromMarkedLocation(vector++))) {
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (vector == end)
michael@0:         return true;
michael@0: 
michael@0:     JS_ASSERT(start == MAX_ARRAY_INDEX + 1);
michael@0:     RootedValue value(cx);
michael@0:     RootedId id(cx);
michael@0:     RootedValue indexv(cx);
michael@0:     double index = MAX_ARRAY_INDEX + 1;
michael@0:     do {
michael@0:         value = *vector++;
michael@0:         indexv = DoubleValue(index);
michael@0:         if (!ValueToId<CanGC>(cx, indexv, &id) ||
michael@0:             !JSObject::setGeneric(cx, obj, obj, id, &value, true))
michael@0:         {
michael@0:             return false;
michael@0:         }
michael@0:         index += 1;
michael@0:     } while (vector != end);
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_reverse(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     uint32_t len;
michael@0:     if (!GetLengthProperty(cx, obj, &len))
michael@0:         return false;
michael@0: 
michael@0:     do {
michael@0:         if (!obj->is<ArrayObject>())
michael@0:             break;
michael@0:         if (ObjectMayHaveExtraIndexedProperties(obj))
michael@0:             break;
michael@0: 
michael@0:         /* An empty array or an array with no elements is already reversed. */
michael@0:         if (len == 0 || obj->getDenseCapacity() == 0) {
michael@0:             args.rval().setObject(*obj);
michael@0:             return true;
michael@0:         }
michael@0: 
michael@0:         /*
michael@0:          * It's actually surprisingly complicated to reverse an array due to the
michael@0:          * orthogonality of array length and array capacity while handling
michael@0:          * leading and trailing holes correctly.  Reversing seems less likely to
michael@0:          * be a common operation than other array mass-mutation methods, so for
michael@0:          * now just take a probably-small memory hit (in the absence of too many
michael@0:          * holes in the array at its start) and ensure that the capacity is
michael@0:          * sufficient to hold all the elements in the array if it were full.
michael@0:          */
michael@0:         JSObject::EnsureDenseResult result = obj->ensureDenseElements(cx, len, 0);
michael@0:         if (result != JSObject::ED_OK) {
michael@0:             if (result == JSObject::ED_FAILED)
michael@0:                 return false;
michael@0:             JS_ASSERT(result == JSObject::ED_SPARSE);
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         /* Fill out the array's initialized length to its proper length. */
michael@0:         obj->ensureDenseInitializedLength(cx, len, 0);
michael@0: 
michael@0:         RootedValue origlo(cx), orighi(cx);
michael@0: 
michael@0:         uint32_t lo = 0, hi = len - 1;
michael@0:         for (; lo < hi; lo++, hi--) {
michael@0:             origlo = obj->getDenseElement(lo);
michael@0:             orighi = obj->getDenseElement(hi);
michael@0:             obj->setDenseElement(lo, orighi);
michael@0:             if (orighi.isMagic(JS_ELEMENTS_HOLE) &&
michael@0:                 !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(lo))) {
michael@0:                 return false;
michael@0:             }
michael@0:             obj->setDenseElement(hi, origlo);
michael@0:             if (origlo.isMagic(JS_ELEMENTS_HOLE) &&
michael@0:                 !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(hi))) {
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         /*
michael@0:          * Per ECMA-262, don't update the length of the array, even if the new
michael@0:          * array has trailing holes (and thus the original array began with
michael@0:          * holes).
michael@0:          */
michael@0:         args.rval().setObject(*obj);
michael@0:         return true;
michael@0:     } while (false);
michael@0: 
michael@0:     RootedValue lowval(cx), hival(cx);
michael@0:     for (uint32_t i = 0, half = len / 2; i < half; i++) {
michael@0:         bool hole, hole2;
michael@0:         if (!CheckForInterrupt(cx) ||
michael@0:             !GetElement(cx, obj, i, &hole, &lowval) ||
michael@0:             !GetElement(cx, obj, len - i - 1, &hole2, &hival))
michael@0:         {
michael@0:             return false;
michael@0:         }
michael@0: 
michael@0:         if (!hole && !hole2) {
michael@0:             if (!SetArrayElement(cx, obj, i, hival))
michael@0:                 return false;
michael@0:             if (!SetArrayElement(cx, obj, len - i - 1, lowval))
michael@0:                 return false;
michael@0:         } else if (hole && !hole2) {
michael@0:             if (!SetArrayElement(cx, obj, i, hival))
michael@0:                 return false;
michael@0:             if (!DeletePropertyOrThrow(cx, obj, len - i - 1))
michael@0:                 return false;
michael@0:         } else if (!hole && hole2) {
michael@0:             if (!DeletePropertyOrThrow(cx, obj, i))
michael@0:                 return false;
michael@0:             if (!SetArrayElement(cx, obj, len - i - 1, lowval))
michael@0:                 return false;
michael@0:         } else {
michael@0:             // No action required.
michael@0:         }
michael@0:     }
michael@0:     args.rval().setObject(*obj);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: namespace {
michael@0: 
michael@0: inline bool
michael@0: CompareStringValues(JSContext *cx, const Value &a, const Value &b, bool *lessOrEqualp)
michael@0: {
michael@0:     if (!CheckForInterrupt(cx))
michael@0:         return false;
michael@0: 
michael@0:     JSString *astr = a.toString();
michael@0:     JSString *bstr = b.toString();
michael@0:     int32_t result;
michael@0:     if (!CompareStrings(cx, astr, bstr, &result))
michael@0:         return false;
michael@0: 
michael@0:     *lessOrEqualp = (result <= 0);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static const uint64_t powersOf10[] = {
michael@0:     1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 1000000000000ULL
michael@0: };
michael@0: 
michael@0: static inline unsigned
michael@0: NumDigitsBase10(uint32_t n)
michael@0: {
michael@0:     /*
michael@0:      * This is just floor_log10(n) + 1
michael@0:      * Algorithm taken from
michael@0:      * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
michael@0:      */
michael@0:     uint32_t log2 = CeilingLog2(n);
michael@0:     uint32_t t = log2 * 1233 >> 12;
michael@0:     return t - (n < powersOf10[t]) + 1;
michael@0: }
michael@0: 
michael@0: static inline bool
michael@0: CompareLexicographicInt32(const Value &a, const Value &b, bool *lessOrEqualp)
michael@0: {
michael@0:     int32_t aint = a.toInt32();
michael@0:     int32_t bint = b.toInt32();
michael@0: 
michael@0:     /*
michael@0:      * If both numbers are equal ... trivial
michael@0:      * If only one of both is negative --> arithmetic comparison as char code
michael@0:      * of '-' is always less than any other digit
michael@0:      * If both numbers are negative convert them to positive and continue
michael@0:      * handling ...
michael@0:      */
michael@0:     if (aint == bint) {
michael@0:         *lessOrEqualp = true;
michael@0:     } else if ((aint < 0) && (bint >= 0)) {
michael@0:         *lessOrEqualp = true;
michael@0:     } else if ((aint >= 0) && (bint < 0)) {
michael@0:         *lessOrEqualp = false;
michael@0:     } else {
michael@0:         uint32_t auint = Abs(aint);
michael@0:         uint32_t buint = Abs(bint);
michael@0: 
michael@0:         /*
michael@0:          *  ... get number of digits of both integers.
michael@0:          * If they have the same number of digits --> arithmetic comparison.
michael@0:          * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
michael@0:          * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
michael@0:          */
michael@0:         unsigned digitsa = NumDigitsBase10(auint);
michael@0:         unsigned digitsb = NumDigitsBase10(buint);
michael@0:         if (digitsa == digitsb) {
michael@0:             *lessOrEqualp = (auint <= buint);
michael@0:         } else if (digitsa > digitsb) {
michael@0:             JS_ASSERT((digitsa - digitsb) < ArrayLength(powersOf10));
michael@0:             *lessOrEqualp = (uint64_t(auint) < uint64_t(buint) * powersOf10[digitsa - digitsb]);
michael@0:         } else { /* if (digitsb > digitsa) */
michael@0:             JS_ASSERT((digitsb - digitsa) < ArrayLength(powersOf10));
michael@0:             *lessOrEqualp = (uint64_t(auint) * powersOf10[digitsb - digitsa] <= uint64_t(buint));
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static inline bool
michael@0: CompareSubStringValues(JSContext *cx, const jschar *s1, size_t l1,
michael@0:                        const jschar *s2, size_t l2, bool *lessOrEqualp)
michael@0: {
michael@0:     if (!CheckForInterrupt(cx))
michael@0:         return false;
michael@0: 
michael@0:     if (!s1 || !s2)
michael@0:         return false;
michael@0: 
michael@0:     int32_t result = CompareChars(s1, l1, s2, l2);
michael@0:     *lessOrEqualp = (result <= 0);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: struct SortComparatorStrings
michael@0: {
michael@0:     JSContext   *const cx;
michael@0: 
michael@0:     SortComparatorStrings(JSContext *cx)
michael@0:       : cx(cx) {}
michael@0: 
michael@0:     bool operator()(const Value &a, const Value &b, bool *lessOrEqualp) {
michael@0:         return CompareStringValues(cx, a, b, lessOrEqualp);
michael@0:     }
michael@0: };
michael@0: 
michael@0: struct SortComparatorLexicographicInt32
michael@0: {
michael@0:     bool operator()(const Value &a, const Value &b, bool *lessOrEqualp) {
michael@0:         return CompareLexicographicInt32(a, b, lessOrEqualp);
michael@0:     }
michael@0: };
michael@0: 
michael@0: struct StringifiedElement
michael@0: {
michael@0:     size_t charsBegin;
michael@0:     size_t charsEnd;
michael@0:     size_t elementIndex;
michael@0: };
michael@0: 
michael@0: struct SortComparatorStringifiedElements
michael@0: {
michael@0:     JSContext           *const cx;
michael@0:     const StringBuffer  &sb;
michael@0: 
michael@0:     SortComparatorStringifiedElements(JSContext *cx, const StringBuffer &sb)
michael@0:       : cx(cx), sb(sb) {}
michael@0: 
michael@0:     bool operator()(const StringifiedElement &a, const StringifiedElement &b, bool *lessOrEqualp) {
michael@0:         return CompareSubStringValues(cx, sb.begin() + a.charsBegin, a.charsEnd - a.charsBegin,
michael@0:                                       sb.begin() + b.charsBegin, b.charsEnd - b.charsBegin,
michael@0:                                       lessOrEqualp);
michael@0:     }
michael@0: };
michael@0: 
michael@0: struct SortComparatorFunction
michael@0: {
michael@0:     JSContext          *const cx;
michael@0:     const Value        &fval;
michael@0:     FastInvokeGuard    &fig;
michael@0: 
michael@0:     SortComparatorFunction(JSContext *cx, const Value &fval, FastInvokeGuard &fig)
michael@0:       : cx(cx), fval(fval), fig(fig) { }
michael@0: 
michael@0:     bool operator()(const Value &a, const Value &b, bool *lessOrEqualp);
michael@0: };
michael@0: 
michael@0: bool
michael@0: SortComparatorFunction::operator()(const Value &a, const Value &b, bool *lessOrEqualp)
michael@0: {
michael@0:     /*
michael@0:      * array_sort deals with holes and undefs on its own and they should not
michael@0:      * come here.
michael@0:      */
michael@0:     JS_ASSERT(!a.isMagic() && !a.isUndefined());
michael@0:     JS_ASSERT(!a.isMagic() && !b.isUndefined());
michael@0: 
michael@0:     if (!CheckForInterrupt(cx))
michael@0:         return false;
michael@0: 
michael@0:     InvokeArgs &args = fig.args();
michael@0:     if (!args.init(2))
michael@0:         return false;
michael@0: 
michael@0:     args.setCallee(fval);
michael@0:     args.setThis(UndefinedValue());
michael@0:     args[0].set(a);
michael@0:     args[1].set(b);
michael@0: 
michael@0:     if (!fig.invoke(cx))
michael@0:         return false;
michael@0: 
michael@0:     double cmp;
michael@0:     if (!ToNumber(cx, args.rval(), &cmp))
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * XXX eport some kind of error here if cmp is NaN? ECMA talks about
michael@0:      * 'consistent compare functions' that don't return NaN, but is silent
michael@0:      * about what the result should be. So we currently ignore it.
michael@0:      */
michael@0:     *lessOrEqualp = (IsNaN(cmp) || cmp <= 0);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: struct NumericElement
michael@0: {
michael@0:     double dv;
michael@0:     size_t elementIndex;
michael@0: };
michael@0: 
michael@0: bool
michael@0: ComparatorNumericLeftMinusRight(const NumericElement &a, const NumericElement &b,
michael@0:                                 bool *lessOrEqualp)
michael@0: {
michael@0:     *lessOrEqualp = (a.dv <= b.dv);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: ComparatorNumericRightMinusLeft(const NumericElement &a, const NumericElement &b,
michael@0:                                 bool *lessOrEqualp)
michael@0: {
michael@0:     *lessOrEqualp = (b.dv <= a.dv);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: typedef bool (*ComparatorNumeric)(const NumericElement &a, const NumericElement &b,
michael@0:                                   bool *lessOrEqualp);
michael@0: 
michael@0: ComparatorNumeric SortComparatorNumerics[] = {
michael@0:     nullptr,
michael@0:     nullptr,
michael@0:     ComparatorNumericLeftMinusRight,
michael@0:     ComparatorNumericRightMinusLeft
michael@0: };
michael@0: 
michael@0: bool
michael@0: ComparatorInt32LeftMinusRight(const Value &a, const Value &b, bool *lessOrEqualp)
michael@0: {
michael@0:     *lessOrEqualp = (a.toInt32() <= b.toInt32());
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: ComparatorInt32RightMinusLeft(const Value &a, const Value &b, bool *lessOrEqualp)
michael@0: {
michael@0:     *lessOrEqualp = (b.toInt32() <= a.toInt32());
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: typedef bool (*ComparatorInt32)(const Value &a, const Value &b, bool *lessOrEqualp);
michael@0: 
michael@0: ComparatorInt32 SortComparatorInt32s[] = {
michael@0:     nullptr,
michael@0:     nullptr,
michael@0:     ComparatorInt32LeftMinusRight,
michael@0:     ComparatorInt32RightMinusLeft
michael@0: };
michael@0: 
michael@0: // Note: Values for this enum must match up with SortComparatorNumerics
michael@0: // and SortComparatorInt32s.
michael@0: enum ComparatorMatchResult {
michael@0:     Match_Failure = 0,
michael@0:     Match_None,
michael@0:     Match_LeftMinusRight,
michael@0:     Match_RightMinusLeft
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * Specialize behavior for comparator functions with particular common bytecode
michael@0:  * patterns: namely, |return x - y| and |return y - x|.
michael@0:  */
michael@0: ComparatorMatchResult
michael@0: MatchNumericComparator(JSContext *cx, const Value &v)
michael@0: {
michael@0:     if (!v.isObject())
michael@0:         return Match_None;
michael@0: 
michael@0:     JSObject &obj = v.toObject();
michael@0:     if (!obj.is<JSFunction>())
michael@0:         return Match_None;
michael@0: 
michael@0:     JSFunction *fun = &obj.as<JSFunction>();
michael@0:     if (!fun->isInterpreted())
michael@0:         return Match_None;
michael@0: 
michael@0:     JSScript *script = fun->getOrCreateScript(cx);
michael@0:     if (!script)
michael@0:         return Match_Failure;
michael@0: 
michael@0:     jsbytecode *pc = script->code();
michael@0: 
michael@0:     uint16_t arg0, arg1;
michael@0:     if (JSOp(*pc) != JSOP_GETARG)
michael@0:         return Match_None;
michael@0:     arg0 = GET_ARGNO(pc);
michael@0:     pc += JSOP_GETARG_LENGTH;
michael@0: 
michael@0:     if (JSOp(*pc) != JSOP_GETARG)
michael@0:         return Match_None;
michael@0:     arg1 = GET_ARGNO(pc);
michael@0:     pc += JSOP_GETARG_LENGTH;
michael@0: 
michael@0:     if (JSOp(*pc) != JSOP_SUB)
michael@0:         return Match_None;
michael@0:     pc += JSOP_SUB_LENGTH;
michael@0: 
michael@0:     if (JSOp(*pc) != JSOP_RETURN)
michael@0:         return Match_None;
michael@0: 
michael@0:     if (arg0 == 0 && arg1 == 1)
michael@0:         return Match_LeftMinusRight;
michael@0: 
michael@0:     if (arg0 == 1 && arg1 == 0)
michael@0:         return Match_RightMinusLeft;
michael@0: 
michael@0:     return Match_None;
michael@0: }
michael@0: 
michael@0: template<typename K, typename C>
michael@0: static inline bool
michael@0: MergeSortByKey(K keys, size_t len, K scratch, C comparator, AutoValueVector *vec)
michael@0: {
michael@0:     MOZ_ASSERT(vec->length() >= len);
michael@0: 
michael@0:     /* Sort keys. */
michael@0:     if (!MergeSort(keys, len, scratch, comparator))
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * Reorder vec by keys in-place, going element by element.  When an out-of-
michael@0:      * place element is encountered, move that element to its proper position,
michael@0:      * displacing whatever element was at *that* point to its proper position,
michael@0:      * and so on until an element must be moved to the current position.
michael@0:      *
michael@0:      * At each outer iteration all elements up to |i| are sorted.  If
michael@0:      * necessary each inner iteration moves some number of unsorted elements
michael@0:      * (including |i|) directly to sorted position.  Thus on completion |*vec|
michael@0:      * is sorted, and out-of-position elements have moved once.  Complexity is
michael@0:      * Θ(len) + O(len) == O(2*len), with each element visited at most twice.
michael@0:      */
michael@0:     for (size_t i = 0; i < len; i++) {
michael@0:         size_t j = keys[i].elementIndex;
michael@0:         if (i == j)
michael@0:             continue; // fixed point
michael@0: 
michael@0:         MOZ_ASSERT(j > i, "Everything less than |i| should be in the right place!");
michael@0:         Value tv = (*vec)[j];
michael@0:         do {
michael@0:             size_t k = keys[j].elementIndex;
michael@0:             keys[j].elementIndex = j;
michael@0:             (*vec)[j] = (*vec)[k];
michael@0:             j = k;
michael@0:         } while (j != i);
michael@0: 
michael@0:         // We could assert the loop invariant that |i == keys[i].elementIndex|
michael@0:         // here if we synced |keys[i].elementIndex|.  But doing so would render
michael@0:         // the assertion vacuous, so don't bother, even in debug builds.
michael@0:         (*vec)[i] = tv;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Sort Values as strings.
michael@0:  *
michael@0:  * To minimize #conversions, SortLexicographically() first converts all Values
michael@0:  * to strings at once, then sorts the elements by these cached strings.
michael@0:  */
michael@0: bool
michael@0: SortLexicographically(JSContext *cx, AutoValueVector *vec, size_t len)
michael@0: {
michael@0:     JS_ASSERT(vec->length() >= len);
michael@0: 
michael@0:     StringBuffer sb(cx);
michael@0:     Vector<StringifiedElement, 0, TempAllocPolicy> strElements(cx);
michael@0: 
michael@0:     /* MergeSort uses the upper half as scratch space. */
michael@0:     if (!strElements.reserve(2 * len))
michael@0:         return false;
michael@0: 
michael@0:     /* Convert Values to strings. */
michael@0:     size_t cursor = 0;
michael@0:     for (size_t i = 0; i < len; i++) {
michael@0:         if (!CheckForInterrupt(cx))
michael@0:             return false;
michael@0: 
michael@0:         if (!ValueToStringBuffer(cx, (*vec)[i], sb))
michael@0:             return false;
michael@0: 
michael@0:         StringifiedElement el = { cursor, sb.length(), i };
michael@0:         strElements.infallibleAppend(el);
michael@0:         cursor = sb.length();
michael@0:     }
michael@0: 
michael@0:     /* Resize strElements so we can perform MergeSort. */
michael@0:     JS_ALWAYS_TRUE(strElements.resize(2 * len));
michael@0: 
michael@0:     /* Sort Values in vec alphabetically. */
michael@0:     return MergeSortByKey(strElements.begin(), len, strElements.begin() + len,
michael@0:                           SortComparatorStringifiedElements(cx, sb), vec);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Sort Values as numbers.
michael@0:  *
michael@0:  * To minimize #conversions, SortNumerically first converts all Values to
michael@0:  * numerics at once, then sorts the elements by these cached numerics.
michael@0:  */
michael@0: bool
michael@0: SortNumerically(JSContext *cx, AutoValueVector *vec, size_t len, ComparatorMatchResult comp)
michael@0: {
michael@0:     JS_ASSERT(vec->length() >= len);
michael@0: 
michael@0:     Vector<NumericElement, 0, TempAllocPolicy> numElements(cx);
michael@0: 
michael@0:     /* MergeSort uses the upper half as scratch space. */
michael@0:     if (!numElements.reserve(2 * len))
michael@0:         return false;
michael@0: 
michael@0:     /* Convert Values to numerics. */
michael@0:     for (size_t i = 0; i < len; i++) {
michael@0:         if (!CheckForInterrupt(cx))
michael@0:             return false;
michael@0: 
michael@0:         double dv;
michael@0:         if (!ToNumber(cx, vec->handleAt(i), &dv))
michael@0:             return false;
michael@0: 
michael@0:         NumericElement el = { dv, i };
michael@0:         numElements.infallibleAppend(el);
michael@0:     }
michael@0: 
michael@0:     /* Resize strElements so we can perform MergeSort. */
michael@0:     JS_ALWAYS_TRUE(numElements.resize(2 * len));
michael@0: 
michael@0:     /* Sort Values in vec numerically. */
michael@0:     return MergeSortByKey(numElements.begin(), len, numElements.begin() + len,
michael@0:                           SortComparatorNumerics[comp], vec);
michael@0: }
michael@0: 
michael@0: } /* namespace anonymous */
michael@0: 
michael@0: bool
michael@0: js::array_sort(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     RootedValue fvalRoot(cx);
michael@0:     Value &fval = fvalRoot.get();
michael@0: 
michael@0:     if (args.hasDefined(0)) {
michael@0:         if (args[0].isPrimitive()) {
michael@0:             JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_BAD_SORT_ARG);
michael@0:             return false;
michael@0:         }
michael@0:         fval = args[0];     /* non-default compare function */
michael@0:     } else {
michael@0:         fval.setNull();
michael@0:     }
michael@0: 
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     uint32_t len;
michael@0:     if (!GetLengthProperty(cx, obj, &len))
michael@0:         return false;
michael@0:     if (len < 2) {
michael@0:         /* [] and [a] remain unchanged when sorted. */
michael@0:         args.rval().setObject(*obj);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * We need a temporary array of 2 * len Value to hold the array elements
michael@0:      * and the scratch space for merge sort. Check that its size does not
michael@0:      * overflow size_t, which would allow for indexing beyond the end of the
michael@0:      * malloc'd vector.
michael@0:      */
michael@0: #if JS_BITS_PER_WORD == 32
michael@0:     if (size_t(len) > size_t(-1) / (2 * sizeof(Value))) {
michael@0:         js_ReportAllocationOverflow(cx);
michael@0:         return false;
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     /*
michael@0:      * Initialize vec as a root. We will clear elements of vec one by
michael@0:      * one while increasing the rooted amount of vec when we know that the
michael@0:      * property at the corresponding index exists and its value must be rooted.
michael@0:      *
michael@0:      * In this way when sorting a huge mostly sparse array we will not
michael@0:      * access the tail of vec corresponding to properties that do not
michael@0:      * exist, allowing OS to avoiding committing RAM. See bug 330812.
michael@0:      */
michael@0:     size_t n, undefs;
michael@0:     {
michael@0:         AutoValueVector vec(cx);
michael@0:         if (!vec.reserve(2 * size_t(len)))
michael@0:             return false;
michael@0: 
michael@0:         /*
michael@0:          * By ECMA 262, 15.4.4.11, a property that does not exist (which we
michael@0:          * call a "hole") is always greater than an existing property with
michael@0:          * value undefined and that is always greater than any other property.
michael@0:          * Thus to sort holes and undefs we simply count them, sort the rest
michael@0:          * of elements, append undefs after them and then make holes after
michael@0:          * undefs.
michael@0:          */
michael@0:         undefs = 0;
michael@0:         bool allStrings = true;
michael@0:         bool allInts = true;
michael@0:         RootedValue v(cx);
michael@0:         for (uint32_t i = 0; i < len; i++) {
michael@0:             if (!CheckForInterrupt(cx))
michael@0:                 return false;
michael@0: 
michael@0:             /* Clear vec[newlen] before including it in the rooted set. */
michael@0:             bool hole;
michael@0:             if (!GetElement(cx, obj, i, &hole, &v))
michael@0:                 return false;
michael@0:             if (hole)
michael@0:                 continue;
michael@0:             if (v.isUndefined()) {
michael@0:                 ++undefs;
michael@0:                 continue;
michael@0:             }
michael@0:             vec.infallibleAppend(v);
michael@0:             allStrings = allStrings && v.isString();
michael@0:             allInts = allInts && v.isInt32();
michael@0:         }
michael@0: 
michael@0: 
michael@0:         /*
michael@0:          * If the array only contains holes, we're done.  But if it contains
michael@0:          * undefs, those must be sorted to the front of the array.
michael@0:          */
michael@0:         n = vec.length();
michael@0:         if (n == 0 && undefs == 0) {
michael@0:             args.rval().setObject(*obj);
michael@0:             return true;
michael@0:         }
michael@0: 
michael@0:         /* Here len == n + undefs + number_of_holes. */
michael@0:         if (fval.isNull()) {
michael@0:             /*
michael@0:              * Sort using the default comparator converting all elements to
michael@0:              * strings.
michael@0:              */
michael@0:             if (allStrings) {
michael@0:                 JS_ALWAYS_TRUE(vec.resize(n * 2));
michael@0:                 if (!MergeSort(vec.begin(), n, vec.begin() + n, SortComparatorStrings(cx)))
michael@0:                     return false;
michael@0:             } else if (allInts) {
michael@0:                 JS_ALWAYS_TRUE(vec.resize(n * 2));
michael@0:                 if (!MergeSort(vec.begin(), n, vec.begin() + n,
michael@0:                                SortComparatorLexicographicInt32())) {
michael@0:                     return false;
michael@0:                 }
michael@0:             } else {
michael@0:                 if (!SortLexicographically(cx, &vec, n))
michael@0:                     return false;
michael@0:             }
michael@0:         } else {
michael@0:             ComparatorMatchResult comp = MatchNumericComparator(cx, fval);
michael@0:             if (comp == Match_Failure)
michael@0:                 return false;
michael@0: 
michael@0:             if (comp != Match_None) {
michael@0:                 if (allInts) {
michael@0:                     JS_ALWAYS_TRUE(vec.resize(n * 2));
michael@0:                     if (!MergeSort(vec.begin(), n, vec.begin() + n, SortComparatorInt32s[comp]))
michael@0:                         return false;
michael@0:                 } else {
michael@0:                     if (!SortNumerically(cx, &vec, n, comp))
michael@0:                         return false;
michael@0:                 }
michael@0:             } else {
michael@0:                 FastInvokeGuard fig(cx, fval);
michael@0:                 MOZ_ASSERT(!InParallelSection(),
michael@0:                            "Array.sort() can't currently be used from parallel code");
michael@0:                 JS_ALWAYS_TRUE(vec.resize(n * 2));
michael@0:                 if (!MergeSort(vec.begin(), n, vec.begin() + n,
michael@0:                                SortComparatorFunction(cx, fval, fig)))
michael@0:                 {
michael@0:                     return false;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (!InitArrayElements(cx, obj, 0, uint32_t(n), vec.begin(), DontUpdateTypes))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     /* Set undefs that sorted after the rest of elements. */
michael@0:     while (undefs != 0) {
michael@0:         --undefs;
michael@0:         if (!CheckForInterrupt(cx) || !SetArrayElement(cx, obj, n++, UndefinedHandleValue))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     /* Re-create any holes that sorted to the end of the array. */
michael@0:     while (len > n) {
michael@0:         if (!CheckForInterrupt(cx) || !DeletePropertyOrThrow(cx, obj, --len))
michael@0:             return false;
michael@0:     }
michael@0:     args.rval().setObject(*obj);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: js::NewbornArrayPush(JSContext *cx, HandleObject obj, const Value &v)
michael@0: {
michael@0:     Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0: 
michael@0:     JS_ASSERT(!v.isMagic());
michael@0:     JS_ASSERT(arr->lengthIsWritable());
michael@0: 
michael@0:     uint32_t length = arr->length();
michael@0:     JS_ASSERT(length <= arr->getDenseCapacity());
michael@0: 
michael@0:     if (!arr->ensureElements(cx, length + 1))
michael@0:         return false;
michael@0: 
michael@0:     arr->setDenseInitializedLength(length + 1);
michael@0:     arr->setLengthInt32(length + 1);
michael@0:     arr->initDenseElementWithType(cx, length, v);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /* ES5 15.4.4.7 */
michael@0: bool
michael@0: js::array_push(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     /* Step 1. */
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     /* Steps 2-3. */
michael@0:     uint32_t length;
michael@0:     if (!GetLengthProperty(cx, obj, &length))
michael@0:         return false;
michael@0: 
michael@0:     /* Fast path for native objects with dense elements. */
michael@0:     do {
michael@0:         if (!obj->isNative() || obj->is<TypedArrayObject>())
michael@0:             break;
michael@0: 
michael@0:         if (obj->is<ArrayObject>() && !obj->as<ArrayObject>().lengthIsWritable())
michael@0:             break;
michael@0: 
michael@0:         if (ObjectMayHaveExtraIndexedProperties(obj))
michael@0:             break;
michael@0: 
michael@0:         uint32_t argCount = args.length();
michael@0:         JSObject::EnsureDenseResult result = obj->ensureDenseElements(cx, length, argCount);
michael@0:         if (result == JSObject::ED_FAILED)
michael@0:             return false;
michael@0: 
michael@0:         if (result == JSObject::ED_OK) {
michael@0:             for (uint32_t i = 0, index = length; i < argCount; index++, i++)
michael@0:                 obj->setDenseElementWithType(cx, index, args[i]);
michael@0:             uint32_t newlength = length + argCount;
michael@0:             args.rval().setNumber(newlength);
michael@0:             if (obj->is<ArrayObject>()) {
michael@0:                 obj->as<ArrayObject>().setLengthInt32(newlength);
michael@0:                 return true;
michael@0:             }
michael@0:             return SetLengthProperty(cx, obj, newlength);
michael@0:         }
michael@0: 
michael@0:         MOZ_ASSERT(result == JSObject::ED_SPARSE);
michael@0:     } while (false);
michael@0: 
michael@0:     /* Steps 4-5. */
michael@0:     if (!InitArrayElements(cx, obj, length, args.length(), args.array(), UpdateTypes))
michael@0:         return false;
michael@0: 
michael@0:     /* Steps 6-7. */
michael@0:     double newlength = length + double(args.length());
michael@0:     args.rval().setNumber(newlength);
michael@0:     return SetLengthProperty(cx, obj, newlength);
michael@0: }
michael@0: 
michael@0: /* ES6 20130308 draft 15.4.4.6. */
michael@0: bool
michael@0: js::array_pop(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     /* Step 1. */
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     /* Steps 2-3. */
michael@0:     uint32_t index;
michael@0:     if (!GetLengthProperty(cx, obj, &index))
michael@0:         return false;
michael@0: 
michael@0:     /* Steps 4-5. */
michael@0:     if (index == 0) {
michael@0:         /* Step 4b. */
michael@0:         args.rval().setUndefined();
michael@0:     } else {
michael@0:         /* Step 5a. */
michael@0:         index--;
michael@0: 
michael@0:         /* Step 5b, 5e. */
michael@0:         bool hole;
michael@0:         if (!GetElement(cx, obj, index, &hole, args.rval()))
michael@0:             return false;
michael@0: 
michael@0:         /* Step 5c. */
michael@0:         if (!hole && !DeletePropertyOrThrow(cx, obj, index))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // If this was an array, then there are no elements above the one we just
michael@0:     // deleted (if we deleted an element).  Thus we can shrink the dense
michael@0:     // initialized length accordingly.  (This is fine even if the array length
michael@0:     // is non-writable: length-changing occurs after element-deletion effects.)
michael@0:     // Don't do anything if this isn't an array, as any deletion above has no
michael@0:     // effect on any elements after the "last" one indicated by the "length"
michael@0:     // property.
michael@0:     if (obj->is<ArrayObject>() && obj->getDenseInitializedLength() > index)
michael@0:         obj->setDenseInitializedLength(index);
michael@0: 
michael@0:     /* Steps 4a, 5d. */
michael@0:     return SetLengthProperty(cx, obj, index);
michael@0: }
michael@0: 
michael@0: void
michael@0: js::ArrayShiftMoveElements(JSObject *obj)
michael@0: {
michael@0:     JS_ASSERT(obj->is<ArrayObject>());
michael@0:     JS_ASSERT(obj->as<ArrayObject>().lengthIsWritable());
michael@0: 
michael@0:     /*
michael@0:      * At this point the length and initialized length have already been
michael@0:      * decremented and the result fetched, so just shift the array elements
michael@0:      * themselves.
michael@0:      */
michael@0:     uint32_t initlen = obj->getDenseInitializedLength();
michael@0:     obj->moveDenseElementsNoPreBarrier(0, 1, initlen);
michael@0: }
michael@0: 
michael@0: /* ES5 15.4.4.9 */
michael@0: bool
michael@0: js::array_shift(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     /* Step 1. */
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     /* Steps 2-3. */
michael@0:     uint32_t len;
michael@0:     if (!GetLengthProperty(cx, obj, &len))
michael@0:         return false;
michael@0: 
michael@0:     /* Step 4. */
michael@0:     if (len == 0) {
michael@0:         /* Step 4a. */
michael@0:         if (!SetLengthProperty(cx, obj, 0))
michael@0:             return false;
michael@0: 
michael@0:         /* Step 4b. */
michael@0:         args.rval().setUndefined();
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     uint32_t newlen = len - 1;
michael@0: 
michael@0:     /* Fast paths. */
michael@0:     if (obj->is<ArrayObject>() &&
michael@0:         obj->getDenseInitializedLength() > 0 &&
michael@0:         newlen < obj->getDenseCapacity() &&
michael@0:         !ObjectMayHaveExtraIndexedProperties(obj))
michael@0:     {
michael@0:         args.rval().set(obj->getDenseElement(0));
michael@0:         if (args.rval().isMagic(JS_ELEMENTS_HOLE))
michael@0:             args.rval().setUndefined();
michael@0: 
michael@0:         obj->moveDenseElements(0, 1, obj->getDenseInitializedLength() - 1);
michael@0:         obj->setDenseInitializedLength(obj->getDenseInitializedLength() - 1);
michael@0: 
michael@0:         if (!SetLengthProperty(cx, obj, newlen))
michael@0:             return false;
michael@0: 
michael@0:         return js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(newlen));
michael@0:     }
michael@0: 
michael@0:     /* Steps 5, 10. */
michael@0:     bool hole;
michael@0:     if (!GetElement(cx, obj, uint32_t(0), &hole, args.rval()))
michael@0:         return false;
michael@0: 
michael@0:     /* Steps 6-7. */
michael@0:     RootedValue value(cx);
michael@0:     for (uint32_t i = 0; i < newlen; i++) {
michael@0:         if (!CheckForInterrupt(cx))
michael@0:             return false;
michael@0:         if (!GetElement(cx, obj, i + 1, &hole, &value))
michael@0:             return false;
michael@0:         if (hole) {
michael@0:             if (!DeletePropertyOrThrow(cx, obj, i))
michael@0:                 return false;
michael@0:         } else {
michael@0:             if (!SetArrayElement(cx, obj, i, value))
michael@0:                 return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Step 8. */
michael@0:     if (!DeletePropertyOrThrow(cx, obj, newlen))
michael@0:         return false;
michael@0: 
michael@0:     /* Step 9. */
michael@0:     return SetLengthProperty(cx, obj, newlen);
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_unshift(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     uint32_t length;
michael@0:     if (!GetLengthProperty(cx, obj, &length))
michael@0:         return false;
michael@0: 
michael@0:     double newlen = length;
michael@0:     if (args.length() > 0) {
michael@0:         /* Slide up the array to make room for all args at the bottom. */
michael@0:         if (length > 0) {
michael@0:             bool optimized = false;
michael@0:             do {
michael@0:                 if (!obj->is<ArrayObject>())
michael@0:                     break;
michael@0:                 if (ObjectMayHaveExtraIndexedProperties(obj))
michael@0:                     break;
michael@0:                 if (!obj->as<ArrayObject>().lengthIsWritable())
michael@0:                     break;
michael@0:                 JSObject::EnsureDenseResult result = obj->ensureDenseElements(cx, length, args.length());
michael@0:                 if (result != JSObject::ED_OK) {
michael@0:                     if (result == JSObject::ED_FAILED)
michael@0:                         return false;
michael@0:                     JS_ASSERT(result == JSObject::ED_SPARSE);
michael@0:                     break;
michael@0:                 }
michael@0:                 obj->moveDenseElements(args.length(), 0, length);
michael@0:                 for (uint32_t i = 0; i < args.length(); i++)
michael@0:                     obj->setDenseElement(i, MagicValue(JS_ELEMENTS_HOLE));
michael@0:                 optimized = true;
michael@0:             } while (false);
michael@0: 
michael@0:             if (!optimized) {
michael@0:                 double last = length;
michael@0:                 double upperIndex = last + args.length();
michael@0:                 RootedValue value(cx);
michael@0:                 do {
michael@0:                     --last, --upperIndex;
michael@0:                     bool hole;
michael@0:                     if (!CheckForInterrupt(cx))
michael@0:                         return false;
michael@0:                     if (!GetElement(cx, obj, last, &hole, &value))
michael@0:                         return false;
michael@0:                     if (hole) {
michael@0:                         if (!DeletePropertyOrThrow(cx, obj, upperIndex))
michael@0:                             return false;
michael@0:                     } else {
michael@0:                         if (!SetArrayElement(cx, obj, upperIndex, value))
michael@0:                             return false;
michael@0:                     }
michael@0:                 } while (last != 0);
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         /* Copy from args to the bottom of the array. */
michael@0:         if (!InitArrayElements(cx, obj, 0, args.length(), args.array(), UpdateTypes))
michael@0:             return false;
michael@0: 
michael@0:         newlen += args.length();
michael@0:     }
michael@0:     if (!SetLengthProperty(cx, obj, newlen))
michael@0:         return false;
michael@0: 
michael@0:     /* Follow Perl by returning the new array length. */
michael@0:     args.rval().setNumber(newlen);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: TryReuseArrayType(JSObject *obj, ArrayObject *narr)
michael@0: {
michael@0:     /*
michael@0:      * Try to change the type of a newly created array narr to the same type
michael@0:      * as obj. This can only be performed if the original object is an array
michael@0:      * and has the same prototype.
michael@0:      */
michael@0:     JS_ASSERT(narr->getProto()->hasNewType(&ArrayObject::class_, narr->type()));
michael@0: 
michael@0:     if (obj->is<ArrayObject>() && !obj->hasSingletonType() && obj->getProto() == narr->getProto())
michael@0:         narr->setType(obj->type());
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Returns true if this is a dense array whose |count| properties starting from
michael@0:  * |startingIndex| may be accessed (get, set, delete) directly through its
michael@0:  * contiguous vector of elements without fear of getters, setters, etc. along
michael@0:  * the prototype chain, or of enumerators requiring notification of
michael@0:  * modifications.
michael@0:  */
michael@0: static inline bool
michael@0: CanOptimizeForDenseStorage(HandleObject arr, uint32_t startingIndex, uint32_t count, JSContext *cx)
michael@0: {
michael@0:     /* If the desired properties overflow dense storage, we can't optimize. */
michael@0:     if (UINT32_MAX - startingIndex < count)
michael@0:         return false;
michael@0: 
michael@0:     /* There's no optimizing possible if it's not an array. */
michael@0:     if (!arr->is<ArrayObject>())
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * Don't optimize if the array might be in the midst of iteration.  We
michael@0:      * rely on this to be able to safely move dense array elements around with
michael@0:      * just a memmove (see JSObject::moveDenseArrayElements), without worrying
michael@0:      * about updating any in-progress enumerators for properties implicitly
michael@0:      * deleted if a hole is moved from one location to another location not yet
michael@0:      * visited.  See bug 690622.
michael@0:      *
michael@0:      * Another potential wrinkle: what if the enumeration is happening on an
michael@0:      * object which merely has |arr| on its prototype chain?  It turns out this
michael@0:      * case can't happen, because any dense array used as the prototype of
michael@0:      * another object is first slowified, for type inference's sake.
michael@0:      */
michael@0:     types::TypeObject *arrType = arr->getType(cx);
michael@0:     if (MOZ_UNLIKELY(!arrType || arrType->hasAllFlags(OBJECT_FLAG_ITERATED)))
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * Now watch out for getters and setters along the prototype chain or in
michael@0:      * other indexed properties on the object.  (Note that non-writable length
michael@0:      * is subsumed by the initializedLength comparison.)
michael@0:      */
michael@0:     return !ObjectMayHaveExtraIndexedProperties(arr) &&
michael@0:            startingIndex + count <= arr->getDenseInitializedLength();
michael@0: }
michael@0: 
michael@0: /* ES5 15.4.4.12. */
michael@0: bool
michael@0: js::array_splice(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     return array_splice_impl(cx, argc, vp, true);
michael@0: }
michael@0: 
michael@0: bool
michael@0: js::array_splice_impl(JSContext *cx, unsigned argc, Value *vp, bool returnValueIsUsed)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     /* Step 1. */
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     /* Steps 3-4. */
michael@0:     uint32_t len;
michael@0:     if (!GetLengthProperty(cx, obj, &len))
michael@0:         return false;
michael@0: 
michael@0:     /* Step 5. */
michael@0:     double relativeStart;
michael@0:     if (!ToInteger(cx, args.get(0), &relativeStart))
michael@0:         return false;
michael@0: 
michael@0:     /* Step 6. */
michael@0:     uint32_t actualStart;
michael@0:     if (relativeStart < 0)
michael@0:         actualStart = Max(len + relativeStart, 0.0);
michael@0:     else
michael@0:         actualStart = Min(relativeStart, double(len));
michael@0: 
michael@0:     /* Step 7. */
michael@0:     uint32_t actualDeleteCount;
michael@0:     if (args.length() != 1) {
michael@0:         double deleteCountDouble;
michael@0:         RootedValue cnt(cx, args.length() >= 2 ? args[1] : Int32Value(0));
michael@0:         if (!ToInteger(cx, cnt, &deleteCountDouble))
michael@0:             return false;
michael@0:         actualDeleteCount = Min(Max(deleteCountDouble, 0.0), double(len - actualStart));
michael@0:     } else {
michael@0:         /*
michael@0:          * Non-standard: if start was specified but deleteCount was omitted,
michael@0:          * delete to the end of the array.  See bug 668024 for discussion.
michael@0:          */
michael@0:         actualDeleteCount = len - actualStart;
michael@0:     }
michael@0: 
michael@0:     JS_ASSERT(len - actualStart >= actualDeleteCount);
michael@0: 
michael@0:     /* Steps 2, 8-9. */
michael@0:     Rooted<ArrayObject*> arr(cx);
michael@0:     if (CanOptimizeForDenseStorage(obj, actualStart, actualDeleteCount, cx)) {
michael@0:         if (returnValueIsUsed) {
michael@0:             arr = NewDenseCopiedArray(cx, actualDeleteCount, obj, actualStart);
michael@0:             if (!arr)
michael@0:                 return false;
michael@0:             TryReuseArrayType(obj, arr);
michael@0:         }
michael@0:     } else {
michael@0:         arr = NewDenseAllocatedArray(cx, actualDeleteCount);
michael@0:         if (!arr)
michael@0:             return false;
michael@0:         TryReuseArrayType(obj, arr);
michael@0: 
michael@0:         RootedValue fromValue(cx);
michael@0:         for (uint32_t k = 0; k < actualDeleteCount; k++) {
michael@0:             bool hole;
michael@0:             if (!CheckForInterrupt(cx) ||
michael@0:                 !GetElement(cx, obj, actualStart + k, &hole, &fromValue) ||
michael@0:                 (!hole && !JSObject::defineElement(cx, arr, k, fromValue)))
michael@0:             {
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Step 11. */
michael@0:     uint32_t itemCount = (args.length() >= 2) ? (args.length() - 2) : 0;
michael@0: 
michael@0:     if (itemCount < actualDeleteCount) {
michael@0:         /* Step 12: the array is being shrunk. */
michael@0:         uint32_t sourceIndex = actualStart + actualDeleteCount;
michael@0:         uint32_t targetIndex = actualStart + itemCount;
michael@0:         uint32_t finalLength = len - actualDeleteCount + itemCount;
michael@0: 
michael@0:         if (CanOptimizeForDenseStorage(obj, 0, len, cx)) {
michael@0:             /* Steps 12(a)-(b). */
michael@0:             obj->moveDenseElements(targetIndex, sourceIndex, len - sourceIndex);
michael@0: 
michael@0:             /*
michael@0:              * Update the initialized length. Do so before shrinking so that we
michael@0:              * can apply the write barrier to the old slots.
michael@0:              */
michael@0:             obj->setDenseInitializedLength(finalLength);
michael@0: 
michael@0:             /* Steps 12(c)-(d). */
michael@0:             obj->shrinkElements(cx, finalLength);
michael@0:         } else {
michael@0:             /*
michael@0:              * This is all very slow if the length is very large. We don't yet
michael@0:              * have the ability to iterate in sorted order, so we just do the
michael@0:              * pessimistic thing and let CheckForInterrupt handle the
michael@0:              * fallout.
michael@0:              */
michael@0: 
michael@0:             /* Steps 12(a)-(b). */
michael@0:             RootedValue fromValue(cx);
michael@0:             for (uint32_t from = sourceIndex, to = targetIndex; from < len; from++, to++) {
michael@0:                 if (!CheckForInterrupt(cx))
michael@0:                     return false;
michael@0: 
michael@0:                 bool hole;
michael@0:                 if (!GetElement(cx, obj, from, &hole, &fromValue))
michael@0:                     return false;
michael@0:                 if (hole) {
michael@0:                     if (!DeletePropertyOrThrow(cx, obj, to))
michael@0:                         return false;
michael@0:                 } else {
michael@0:                     if (!SetArrayElement(cx, obj, to, fromValue))
michael@0:                         return false;
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             /* Steps 12(c)-(d). */
michael@0:             for (uint32_t k = len; k > finalLength; k--) {
michael@0:                 if (!DeletePropertyOrThrow(cx, obj, k - 1))
michael@0:                     return false;
michael@0:             }
michael@0:         }
michael@0:     } else if (itemCount > actualDeleteCount) {
michael@0:         /* Step 13. */
michael@0: 
michael@0:         /*
michael@0:          * Optimize only if the array is already dense and we can extend it to
michael@0:          * its new length.  It would be wrong to extend the elements here for a
michael@0:          * number of reasons.
michael@0:          *
michael@0:          * First, this could cause us to fall into the fast-path below.  This
michael@0:          * would cause elements to be moved into places past the non-writable
michael@0:          * length.  And when the dense initialized length is updated, that'll
michael@0:          * cause the |in| operator to think that those elements actually exist,
michael@0:          * even though, properly, setting them must fail.
michael@0:          *
michael@0:          * Second, extending the elements here will trigger assertions inside
michael@0:          * ensureDenseElements that the elements aren't being extended past the
michael@0:          * length of a non-writable array.  This is because extending elements
michael@0:          * will extend capacity -- which might extend them past a non-writable
michael@0:          * length, violating the |capacity <= length| invariant for such
michael@0:          * arrays.  And that would make the various JITted fast-path method
michael@0:          * implementations of [].push, [].unshift, and so on wrong.
michael@0:          *
michael@0:          * If the array length is non-writable, this method *will* throw.  For
michael@0:          * simplicity, have the slow-path code do it.  (Also note that the slow
michael@0:          * path may validly *not* throw -- if all the elements being moved are
michael@0:          * holes.)
michael@0:          */
michael@0:         if (obj->is<ArrayObject>()) {
michael@0:             Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0:             if (arr->lengthIsWritable()) {
michael@0:                 JSObject::EnsureDenseResult res =
michael@0:                     arr->ensureDenseElements(cx, arr->length(), itemCount - actualDeleteCount);
michael@0:                 if (res == JSObject::ED_FAILED)
michael@0:                     return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (CanOptimizeForDenseStorage(obj, len, itemCount - actualDeleteCount, cx)) {
michael@0:             obj->moveDenseElements(actualStart + itemCount,
michael@0:                                    actualStart + actualDeleteCount,
michael@0:                                    len - (actualStart + actualDeleteCount));
michael@0:             obj->setDenseInitializedLength(len + itemCount - actualDeleteCount);
michael@0:         } else {
michael@0:             RootedValue fromValue(cx);
michael@0:             for (double k = len - actualDeleteCount; k > actualStart; k--) {
michael@0:                 if (!CheckForInterrupt(cx))
michael@0:                     return false;
michael@0: 
michael@0:                 double from = k + actualDeleteCount - 1;
michael@0:                 double to = k + itemCount - 1;
michael@0: 
michael@0:                 bool hole;
michael@0:                 if (!GetElement(cx, obj, from, &hole, &fromValue))
michael@0:                     return false;
michael@0: 
michael@0:                 if (hole) {
michael@0:                     if (!DeletePropertyOrThrow(cx, obj, to))
michael@0:                         return false;
michael@0:                 } else {
michael@0:                     if (!SetArrayElement(cx, obj, to, fromValue))
michael@0:                         return false;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Step 10. */
michael@0:     Value *items = args.array() + 2;
michael@0: 
michael@0:     /* Steps 14-15. */
michael@0:     for (uint32_t k = actualStart, i = 0; i < itemCount; i++, k++) {
michael@0:         if (!SetArrayElement(cx, obj, k, HandleValue::fromMarkedLocation(&items[i])))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     /* Step 16. */
michael@0:     double finalLength = double(len) - actualDeleteCount + itemCount;
michael@0:     if (!SetLengthProperty(cx, obj, finalLength))
michael@0:         return false;
michael@0: 
michael@0:     /* Step 17. */
michael@0:     if (returnValueIsUsed)
michael@0:         args.rval().setObject(*arr);
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: #ifdef JS_ION
michael@0: bool
michael@0: js::array_concat_dense(JSContext *cx, Handle<ArrayObject*> arr1, Handle<ArrayObject*> arr2,
michael@0:                        Handle<ArrayObject*> result)
michael@0: {
michael@0:     uint32_t initlen1 = arr1->getDenseInitializedLength();
michael@0:     JS_ASSERT(initlen1 == arr1->length());
michael@0: 
michael@0:     uint32_t initlen2 = arr2->getDenseInitializedLength();
michael@0:     JS_ASSERT(initlen2 == arr2->length());
michael@0: 
michael@0:     /* No overflow here due to nelements limit. */
michael@0:     uint32_t len = initlen1 + initlen2;
michael@0: 
michael@0:     if (!result->ensureElements(cx, len))
michael@0:         return false;
michael@0: 
michael@0:     JS_ASSERT(!result->getDenseInitializedLength());
michael@0:     result->setDenseInitializedLength(len);
michael@0: 
michael@0:     result->initDenseElements(0, arr1->getDenseElements(), initlen1);
michael@0:     result->initDenseElements(initlen1, arr2->getDenseElements(), initlen2);
michael@0:     result->setLengthInt32(len);
michael@0:     return true;
michael@0: }
michael@0: #endif /* JS_ION */
michael@0: 
michael@0: /*
michael@0:  * Python-esque sequence operations.
michael@0:  */
michael@0: bool
michael@0: js::array_concat(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
michael@0:     Value *p = args.array() - 1;
michael@0: 
michael@0:     /* Create a new Array object and root it using *vp. */
michael@0:     RootedObject aobj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!aobj)
michael@0:         return false;
michael@0: 
michael@0:     Rooted<ArrayObject*> narr(cx);
michael@0:     uint32_t length;
michael@0:     if (aobj->is<ArrayObject>() && !aobj->isIndexed()) {
michael@0:         length = aobj->as<ArrayObject>().length();
michael@0:         uint32_t initlen = aobj->getDenseInitializedLength();
michael@0:         narr = NewDenseCopiedArray(cx, initlen, aobj, 0);
michael@0:         if (!narr)
michael@0:             return false;
michael@0:         TryReuseArrayType(aobj, narr);
michael@0:         narr->setLength(cx, length);
michael@0:         args.rval().setObject(*narr);
michael@0:         if (argc == 0)
michael@0:             return true;
michael@0:         argc--;
michael@0:         p++;
michael@0:     } else {
michael@0:         narr = NewDenseEmptyArray(cx);
michael@0:         if (!narr)
michael@0:             return false;
michael@0:         args.rval().setObject(*narr);
michael@0:         length = 0;
michael@0:     }
michael@0: 
michael@0:     /* Loop over [0, argc] to concat args into narr, expanding all Arrays. */
michael@0:     for (unsigned i = 0; i <= argc; i++) {
michael@0:         if (!CheckForInterrupt(cx))
michael@0:             return false;
michael@0:         HandleValue v = HandleValue::fromMarkedLocation(&p[i]);
michael@0:         if (v.isObject()) {
michael@0:             RootedObject obj(cx, &v.toObject());
michael@0:             if (ObjectClassIs(obj, ESClass_Array, cx)) {
michael@0:                 uint32_t alength;
michael@0:                 if (!GetLengthProperty(cx, obj, &alength))
michael@0:                     return false;
michael@0:                 RootedValue tmp(cx);
michael@0:                 for (uint32_t slot = 0; slot < alength; slot++) {
michael@0:                     bool hole;
michael@0:                     if (!CheckForInterrupt(cx) || !GetElement(cx, obj, slot, &hole, &tmp))
michael@0:                         return false;
michael@0: 
michael@0:                     /*
michael@0:                      * Per ECMA 262, 15.4.4.4, step 9, ignore nonexistent
michael@0:                      * properties.
michael@0:                      */
michael@0:                     if (!hole && !SetArrayElement(cx, narr, length + slot, tmp))
michael@0:                         return false;
michael@0:                 }
michael@0:                 length += alength;
michael@0:                 continue;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (!SetArrayElement(cx, narr, length, v))
michael@0:             return false;
michael@0:         length++;
michael@0:     }
michael@0: 
michael@0:     return SetLengthProperty(cx, narr, length);
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_slice(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     uint32_t length;
michael@0:     if (!GetLengthProperty(cx, obj, &length))
michael@0:         return false;
michael@0: 
michael@0:     uint32_t begin = 0;
michael@0:     uint32_t end = length;
michael@0:     if (args.length() > 0) {
michael@0:         double d;
michael@0:         if (!ToInteger(cx, args[0], &d))
michael@0:             return false;
michael@0:         if (d < 0) {
michael@0:             d += length;
michael@0:             if (d < 0)
michael@0:                 d = 0;
michael@0:         } else if (d > length) {
michael@0:             d = length;
michael@0:         }
michael@0:         begin = (uint32_t)d;
michael@0: 
michael@0:         if (args.hasDefined(1)) {
michael@0:             if (!ToInteger(cx, args[1], &d))
michael@0:                 return false;
michael@0:             if (d < 0) {
michael@0:                 d += length;
michael@0:                 if (d < 0)
michael@0:                     d = 0;
michael@0:             } else if (d > length) {
michael@0:                 d = length;
michael@0:             }
michael@0:             end = (uint32_t)d;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (begin > end)
michael@0:         begin = end;
michael@0: 
michael@0:     Rooted<ArrayObject*> narr(cx);
michael@0:     narr = NewDenseAllocatedArray(cx, end - begin);
michael@0:     if (!narr)
michael@0:         return false;
michael@0:     TryReuseArrayType(obj, narr);
michael@0: 
michael@0:     if (obj->is<ArrayObject>() && !ObjectMayHaveExtraIndexedProperties(obj)) {
michael@0:         if (obj->getDenseInitializedLength() > begin) {
michael@0:             uint32_t numSourceElements = obj->getDenseInitializedLength() - begin;
michael@0:             uint32_t initLength = Min(numSourceElements, end - begin);
michael@0:             narr->setDenseInitializedLength(initLength);
michael@0:             narr->initDenseElements(0, &obj->getDenseElement(begin), initLength);
michael@0:         }
michael@0:         args.rval().setObject(*narr);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (js::SliceOp op = obj->getOps()->slice) {
michael@0:         // Ensure that we have dense elements, so that DOM can use js::UnsafeDefineElement.
michael@0:         JSObject::EnsureDenseResult result = narr->ensureDenseElements(cx, 0, end - begin);
michael@0:         if (result == JSObject::ED_FAILED)
michael@0:              return false;
michael@0: 
michael@0:         if (result == JSObject::ED_OK) {
michael@0:             if (!op(cx, obj, begin, end, narr))
michael@0:                 return false;
michael@0: 
michael@0:             args.rval().setObject(*narr);
michael@0:             return true;
michael@0:         }
michael@0: 
michael@0:         // Fallthrough
michael@0:         JS_ASSERT(result == JSObject::ED_SPARSE);
michael@0:     }
michael@0: 
michael@0: 
michael@0:     if (!SliceSlowly(cx, obj, obj, begin, end, narr))
michael@0:         return false;
michael@0: 
michael@0:     args.rval().setObject(*narr);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: JS_FRIEND_API(bool)
michael@0: js::SliceSlowly(JSContext* cx, HandleObject obj, HandleObject receiver,
michael@0:                 uint32_t begin, uint32_t end, HandleObject result)
michael@0: {
michael@0:     RootedValue value(cx);
michael@0:     for (uint32_t slot = begin; slot < end; slot++) {
michael@0:         bool hole;
michael@0:         if (!CheckForInterrupt(cx) ||
michael@0:             !GetElement(cx, obj, receiver, slot, &hole, &value))
michael@0:         {
michael@0:             return false;
michael@0:         }
michael@0:         if (!hole && !JSObject::defineElement(cx, result, slot - begin, value))
michael@0:             return false;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /* ES5 15.4.4.20. */
michael@0: static bool
michael@0: array_filter(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     /* Step 1. */
michael@0:     RootedObject obj(cx, ToObject(cx, args.thisv()));
michael@0:     if (!obj)
michael@0:         return false;
michael@0: 
michael@0:     /* Step 2-3. */
michael@0:     uint32_t len;
michael@0:     if (!GetLengthProperty(cx, obj, &len))
michael@0:         return false;
michael@0: 
michael@0:     /* Step 4. */
michael@0:     if (args.length() == 0) {
michael@0:         js_ReportMissingArg(cx, args.calleev(), 0);
michael@0:         return false;
michael@0:     }
michael@0:     RootedObject callable(cx, ValueToCallable(cx, args[0], args.length() - 1));
michael@0:     if (!callable)
michael@0:         return false;
michael@0: 
michael@0:     /* Step 5. */
michael@0:     RootedValue thisv(cx, args.length() >= 2 ? args[1] : UndefinedValue());
michael@0: 
michael@0:     /* Step 6. */
michael@0:     RootedObject arr(cx, NewDenseAllocatedArray(cx, 0));
michael@0:     if (!arr)
michael@0:         return false;
michael@0:     TypeObject *newtype = GetTypeCallerInitObject(cx, JSProto_Array);
michael@0:     if (!newtype)
michael@0:         return false;
michael@0:     arr->setType(newtype);
michael@0: 
michael@0:     /* Step 7. */
michael@0:     uint32_t k = 0;
michael@0: 
michael@0:     /* Step 8. */
michael@0:     uint32_t to = 0;
michael@0: 
michael@0:     /* Step 9. */
michael@0:     JS_ASSERT(!InParallelSection());
michael@0:     FastInvokeGuard fig(cx, ObjectValue(*callable));
michael@0:     InvokeArgs &args2 = fig.args();
michael@0:     RootedValue kValue(cx);
michael@0:     while (k < len) {
michael@0:         if (!CheckForInterrupt(cx))
michael@0:             return false;
michael@0: 
michael@0:         /* Step a, b, and c.i. */
michael@0:         bool kNotPresent;
michael@0:         if (!GetElement(cx, obj, k, &kNotPresent, &kValue))
michael@0:             return false;
michael@0: 
michael@0:         /* Step c.ii-iii. */
michael@0:         if (!kNotPresent) {
michael@0:             if (!args2.init(3))
michael@0:                 return false;
michael@0:             args2.setCallee(ObjectValue(*callable));
michael@0:             args2.setThis(thisv);
michael@0:             args2[0].set(kValue);
michael@0:             args2[1].setNumber(k);
michael@0:             args2[2].setObject(*obj);
michael@0:             if (!fig.invoke(cx))
michael@0:                 return false;
michael@0: 
michael@0:             if (ToBoolean(args2.rval())) {
michael@0:                 if (!SetArrayElement(cx, arr, to, kValue))
michael@0:                     return false;
michael@0:                 to++;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         /* Step d. */
michael@0:         k++;
michael@0:     }
michael@0: 
michael@0:     /* Step 10. */
michael@0:     args.rval().setObject(*arr);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_isArray(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     bool isArray = args.length() > 0 && IsObjectWithClass(args[0], ESClass_Array, cx);
michael@0:     args.rval().setBoolean(isArray);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: IsArrayConstructor(const Value &v)
michael@0: {
michael@0:     // This must only return true if v is *the* Array constructor for the
michael@0:     // current compartment; we rely on the fact that any other Array
michael@0:     // constructor would be represented as a wrapper.
michael@0:     return v.isObject() &&
michael@0:            v.toObject().is<JSFunction>() &&
michael@0:            v.toObject().as<JSFunction>().isNative() &&
michael@0:            v.toObject().as<JSFunction>().native() == js_Array;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: ArrayFromCallArgs(JSContext *cx, RootedTypeObject &type, CallArgs &args)
michael@0: {
michael@0:     if (!InitArrayTypes(cx, type, args.array(), args.length()))
michael@0:         return false;
michael@0:     JSObject *obj = (args.length() == 0)
michael@0:         ? NewDenseEmptyArray(cx)
michael@0:         : NewDenseCopiedArray(cx, args.length(), args.array());
michael@0:     if (!obj)
michael@0:         return false;
michael@0:     obj->setType(type);
michael@0:     args.rval().setObject(*obj);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: array_of(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0: 
michael@0:     if (IsArrayConstructor(args.thisv()) || !IsConstructor(args.thisv())) {
michael@0:         // IsArrayConstructor(this) will usually be true in practice. This is
michael@0:         // the most common path.
michael@0:         RootedTypeObject type(cx, GetTypeCallerInitObject(cx, JSProto_Array));
michael@0:         if (!type)
michael@0:             return false;
michael@0:         return ArrayFromCallArgs(cx, type, args);
michael@0:     }
michael@0: 
michael@0:     // Step 4.
michael@0:     RootedObject obj(cx);
michael@0:     {
michael@0:         RootedValue v(cx);
michael@0:         Value argv[1] = {NumberValue(args.length())};
michael@0:         if (!InvokeConstructor(cx, args.thisv(), 1, argv, v.address()))
michael@0:             return false;
michael@0:         obj = ToObject(cx, v);
michael@0:         if (!obj)
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // Step 8.
michael@0:     for (unsigned k = 0; k < args.length(); k++) {
michael@0:         if (!JSObject::defineElement(cx, obj, k, args[k]))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // Steps 9-10.
michael@0:     RootedValue v(cx, NumberValue(args.length()));
michael@0:     if (!JSObject::setProperty(cx, obj, obj, cx->names().length, &v, true))
michael@0:         return false;
michael@0: 
michael@0:     // Step 11.
michael@0:     args.rval().setObject(*obj);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: #define GENERIC JSFUN_GENERIC_NATIVE
michael@0: 
michael@0: static const JSFunctionSpec array_methods[] = {
michael@0: #if JS_HAS_TOSOURCE
michael@0:     JS_FN(js_toSource_str,      array_toSource,     0,0),
michael@0: #endif
michael@0:     JS_FN(js_toString_str,      array_toString,     0,0),
michael@0:     JS_FN(js_toLocaleString_str,array_toLocaleString,0,0),
michael@0: 
michael@0:     /* Perl-ish methods. */
michael@0:     JS_FN("join",               array_join,         1,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("reverse",            array_reverse,      0,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("sort",               array_sort,         1,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("push",               array_push,         1,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("pop",                array_pop,          0,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("shift",              array_shift,        0,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("unshift",            array_unshift,      1,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("splice",             array_splice,       2,JSFUN_GENERIC_NATIVE),
michael@0: 
michael@0:     /* Pythonic sequence methods. */
michael@0:     JS_FN("concat",             array_concat,       1,JSFUN_GENERIC_NATIVE),
michael@0:     JS_FN("slice",              array_slice,        2,JSFUN_GENERIC_NATIVE),
michael@0: 
michael@0:     JS_SELF_HOSTED_FN("lastIndexOf", "ArrayLastIndexOf", 1,0),
michael@0:     JS_SELF_HOSTED_FN("indexOf",     "ArrayIndexOf",     1,0),
michael@0:     JS_SELF_HOSTED_FN("forEach",     "ArrayForEach",     1,0),
michael@0:     JS_SELF_HOSTED_FN("map",         "ArrayMap",         1,0),
michael@0:     JS_SELF_HOSTED_FN("reduce",      "ArrayReduce",      1,0),
michael@0:     JS_SELF_HOSTED_FN("reduceRight", "ArrayReduceRight", 1,0),
michael@0:     JS_FN("filter",             array_filter,       1,JSFUN_GENERIC_NATIVE),
michael@0:     JS_SELF_HOSTED_FN("some",        "ArraySome",        1,0),
michael@0:     JS_SELF_HOSTED_FN("every",       "ArrayEvery",       1,0),
michael@0: 
michael@0: #ifdef ENABLE_PARALLEL_JS
michael@0:     /* Parallelizable and pure methods. */
michael@0:     JS_SELF_HOSTED_FN("mapPar",      "ArrayMapPar",      2,0),
michael@0:     JS_SELF_HOSTED_FN("reducePar",   "ArrayReducePar",   2,0),
michael@0:     JS_SELF_HOSTED_FN("scanPar",     "ArrayScanPar",     2,0),
michael@0:     JS_SELF_HOSTED_FN("scatterPar",  "ArrayScatterPar",  5,0),
michael@0:     JS_SELF_HOSTED_FN("filterPar",   "ArrayFilterPar",   2,0),
michael@0: #endif
michael@0: 
michael@0:     /* ES6 additions */
michael@0:     JS_SELF_HOSTED_FN("find",        "ArrayFind",        1,0),
michael@0:     JS_SELF_HOSTED_FN("findIndex",   "ArrayFindIndex",   1,0),
michael@0: 
michael@0:     JS_SELF_HOSTED_FN("fill",        "ArrayFill",        3,0),
michael@0: 
michael@0:     JS_SELF_HOSTED_FN("@@iterator",  "ArrayValues",      0,0),
michael@0:     JS_SELF_HOSTED_FN("entries",     "ArrayEntries",     0,0),
michael@0:     JS_SELF_HOSTED_FN("keys",        "ArrayKeys",        0,0),
michael@0:     JS_FS_END
michael@0: };
michael@0: 
michael@0: static const JSFunctionSpec array_static_methods[] = {
michael@0:     JS_FN("isArray",            array_isArray,      1,0),
michael@0:     JS_SELF_HOSTED_FN("lastIndexOf", "ArrayStaticLastIndexOf", 2,0),
michael@0:     JS_SELF_HOSTED_FN("indexOf",     "ArrayStaticIndexOf", 2,0),
michael@0:     JS_SELF_HOSTED_FN("forEach",     "ArrayStaticForEach", 2,0),
michael@0:     JS_SELF_HOSTED_FN("map",         "ArrayStaticMap",   2,0),
michael@0:     JS_SELF_HOSTED_FN("every",       "ArrayStaticEvery", 2,0),
michael@0:     JS_SELF_HOSTED_FN("some",        "ArrayStaticSome",  2,0),
michael@0:     JS_SELF_HOSTED_FN("reduce",      "ArrayStaticReduce", 2,0),
michael@0:     JS_SELF_HOSTED_FN("reduceRight", "ArrayStaticReduceRight", 2,0),
michael@0:     JS_FN("of",                 array_of,           0,0),
michael@0: 
michael@0: #ifdef ENABLE_PARALLEL_JS
michael@0:     JS_SELF_HOSTED_FN("build",       "ArrayStaticBuild", 2,0),
michael@0:     /* Parallelizable and pure static methods. */
michael@0:     JS_SELF_HOSTED_FN("buildPar",    "ArrayStaticBuildPar", 3,0),
michael@0: #endif
michael@0: 
michael@0:     JS_FS_END
michael@0: };
michael@0: 
michael@0: /* ES5 15.4.2 */
michael@0: bool
michael@0: js_Array(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     RootedTypeObject type(cx, GetTypeCallerInitObject(cx, JSProto_Array));
michael@0:     if (!type)
michael@0:         return false;
michael@0: 
michael@0:     if (args.length() != 1 || !args[0].isNumber())
michael@0:         return ArrayFromCallArgs(cx, type, args);
michael@0: 
michael@0:     uint32_t length;
michael@0:     if (args[0].isInt32()) {
michael@0:         int32_t i = args[0].toInt32();
michael@0:         if (i < 0) {
michael@0:             JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
michael@0:             return false;
michael@0:         }
michael@0:         length = uint32_t(i);
michael@0:     } else {
michael@0:         double d = args[0].toDouble();
michael@0:         length = ToUint32(d);
michael@0:         if (d != double(length)) {
michael@0:             JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Allocate dense elements eagerly for small arrays, to avoid reallocating
michael@0:      * elements when filling the array.
michael@0:      */
michael@0:     RootedObject obj(cx);
michael@0:     obj = (length <= ArrayObject::EagerAllocationMaxLength)
michael@0:           ? NewDenseAllocatedArray(cx, length)
michael@0:           : NewDenseUnallocatedArray(cx, length);
michael@0:     if (!obj)
michael@0:         return false;
michael@0:     Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
michael@0: 
michael@0:     arr->setType(type);
michael@0: 
michael@0:     /* If the length calculation overflowed, make sure that is marked for the new type. */
michael@0:     if (arr->length() > INT32_MAX)
michael@0:         arr->setLength(cx, arr->length());
michael@0: 
michael@0:     args.rval().setObject(*arr);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: JSObject *
michael@0: js_InitArrayClass(JSContext *cx, HandleObject obj)
michael@0: {
michael@0:     JS_ASSERT(obj->isNative());
michael@0: 
michael@0:     Rooted<GlobalObject*> global(cx, &obj->as<GlobalObject>());
michael@0: 
michael@0:     RootedObject proto(cx, global->getOrCreateObjectPrototype(cx));
michael@0:     if (!proto)
michael@0:         return nullptr;
michael@0: 
michael@0:     RootedTypeObject type(cx, cx->getNewType(&ArrayObject::class_, proto.get()));
michael@0:     if (!type)
michael@0:         return nullptr;
michael@0: 
michael@0:     JSObject *metadata = nullptr;
michael@0:     if (!NewObjectMetadata(cx, &metadata))
michael@0:         return nullptr;
michael@0: 
michael@0:     RootedShape shape(cx, EmptyShape::getInitialShape(cx, &ArrayObject::class_, TaggedProto(proto),
michael@0:                                                       proto->getParent(), metadata,
michael@0:                                                       gc::FINALIZE_OBJECT0));
michael@0:     if (!shape)
michael@0:         return nullptr;
michael@0: 
michael@0:     RootedObject arrayProto(cx, JSObject::createArray(cx, gc::FINALIZE_OBJECT4, gc::TenuredHeap, shape, type, 0));
michael@0:     if (!arrayProto || !JSObject::setSingletonType(cx, arrayProto) || !AddLengthProperty(cx, arrayProto))
michael@0:         return nullptr;
michael@0: 
michael@0:     RootedFunction ctor(cx);
michael@0:     ctor = global->createConstructor(cx, js_Array, cx->names().Array, 1);
michael@0:     if (!ctor)
michael@0:         return nullptr;
michael@0: 
michael@0:     /*
michael@0:      * The default 'new' type of Array.prototype is required by type inference
michael@0:      * to have unknown properties, to simplify handling of e.g. heterogenous
michael@0:      * arrays in JSON and script literals and allows setDenseArrayElement to
michael@0:      * be used without updating the indexed type set for such default arrays.
michael@0:      */
michael@0:     if (!JSObject::setNewTypeUnknown(cx, &ArrayObject::class_, arrayProto))
michael@0:         return nullptr;
michael@0: 
michael@0:     if (!LinkConstructorAndPrototype(cx, ctor, arrayProto))
michael@0:         return nullptr;
michael@0: 
michael@0:     if (!DefinePropertiesAndBrand(cx, arrayProto, nullptr, array_methods) ||
michael@0:         !DefinePropertiesAndBrand(cx, ctor, nullptr, array_static_methods))
michael@0:     {
michael@0:         return nullptr;
michael@0:     }
michael@0: 
michael@0:     if (!GlobalObject::initBuiltinConstructor(cx, global, JSProto_Array, ctor, arrayProto))
michael@0:         return nullptr;
michael@0: 
michael@0:     return arrayProto;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Array allocation functions.
michael@0:  */
michael@0: 
michael@0: static inline bool
michael@0: EnsureNewArrayElements(ExclusiveContext *cx, JSObject *obj, uint32_t length)
michael@0: {
michael@0:     /*
michael@0:      * If ensureElements creates dynamically allocated slots, then having
michael@0:      * fixedSlots is a waste.
michael@0:      */
michael@0:     DebugOnly<uint32_t> cap = obj->getDenseCapacity();
michael@0: 
michael@0:     if (!obj->ensureElements(cx, length))
michael@0:         return false;
michael@0: 
michael@0:     JS_ASSERT_IF(cap, !obj->hasDynamicElements());
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: template<bool allocateCapacity>
michael@0: static MOZ_ALWAYS_INLINE ArrayObject *
michael@0: NewArray(ExclusiveContext *cxArg, uint32_t length,
michael@0:          JSObject *protoArg, NewObjectKind newKind = GenericObject)
michael@0: {
michael@0:     gc::AllocKind allocKind = GuessArrayGCKind(length);
michael@0:     JS_ASSERT(CanBeFinalizedInBackground(allocKind, &ArrayObject::class_));
michael@0:     allocKind = GetBackgroundAllocKind(allocKind);
michael@0: 
michael@0:     NewObjectCache::EntryIndex entry = -1;
michael@0:     if (JSContext *cx = cxArg->maybeJSContext()) {
michael@0:         NewObjectCache &cache = cx->runtime()->newObjectCache;
michael@0:         if (newKind == GenericObject &&
michael@0:             !cx->compartment()->hasObjectMetadataCallback() &&
michael@0:             cache.lookupGlobal(&ArrayObject::class_, cx->global(), allocKind, &entry))
michael@0:         {
michael@0:             gc::InitialHeap heap = GetInitialHeap(newKind, &ArrayObject::class_);
michael@0:             JSObject *obj = cache.newObjectFromHit<NoGC>(cx, entry, heap);
michael@0:             if (obj) {
michael@0:                 /* Fixup the elements pointer and length, which may be incorrect. */
michael@0:                 ArrayObject *arr = &obj->as<ArrayObject>();
michael@0:                 arr->setFixedElements();
michael@0:                 arr->setLength(cx, length);
michael@0:                 if (allocateCapacity && !EnsureNewArrayElements(cx, arr, length))
michael@0:                     return nullptr;
michael@0:                 return arr;
michael@0:             } else {
michael@0:                 RootedObject proto(cxArg, protoArg);
michael@0:                 obj = cache.newObjectFromHit<CanGC>(cx, entry, heap);
michael@0:                 JS_ASSERT(!obj);
michael@0:                 protoArg = proto;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     RootedObject proto(cxArg, protoArg);
michael@0:     if (protoArg)
michael@0:         JS::PoisonPtr(&protoArg);
michael@0: 
michael@0:     if (!proto && !GetBuiltinPrototype(cxArg, JSProto_Array, &proto))
michael@0:         return nullptr;
michael@0: 
michael@0:     RootedTypeObject type(cxArg, cxArg->getNewType(&ArrayObject::class_, proto.get()));
michael@0:     if (!type)
michael@0:         return nullptr;
michael@0: 
michael@0:     JSObject *metadata = nullptr;
michael@0:     if (!NewObjectMetadata(cxArg, &metadata))
michael@0:         return nullptr;
michael@0: 
michael@0:     /*
michael@0:      * Get a shape with zero fixed slots, regardless of the size class.
michael@0:      * See JSObject::createArray.
michael@0:      */
michael@0:     RootedShape shape(cxArg, EmptyShape::getInitialShape(cxArg, &ArrayObject::class_,
michael@0:                                                          TaggedProto(proto), cxArg->global(),
michael@0:                                                          metadata, gc::FINALIZE_OBJECT0));
michael@0:     if (!shape)
michael@0:         return nullptr;
michael@0: 
michael@0:     Rooted<ArrayObject*> arr(cxArg, JSObject::createArray(cxArg, allocKind,
michael@0:                                                           GetInitialHeap(newKind, &ArrayObject::class_),
michael@0:                                                           shape, type, length));
michael@0:     if (!arr)
michael@0:         return nullptr;
michael@0: 
michael@0:     if (shape->isEmptyShape()) {
michael@0:         if (!AddLengthProperty(cxArg, arr))
michael@0:             return nullptr;
michael@0:         shape = arr->lastProperty();
michael@0:         EmptyShape::insertInitialShape(cxArg, shape, proto);
michael@0:     }
michael@0: 
michael@0:     if (newKind == SingletonObject && !JSObject::setSingletonType(cxArg, arr))
michael@0:         return nullptr;
michael@0: 
michael@0:     if (entry != -1) {
michael@0:         cxArg->asJSContext()->runtime()->newObjectCache.fillGlobal(entry, &ArrayObject::class_,
michael@0:                                                                    cxArg->global(), allocKind, arr);
michael@0:     }
michael@0: 
michael@0:     if (allocateCapacity && !EnsureNewArrayElements(cxArg, arr, length))
michael@0:         return nullptr;
michael@0: 
michael@0:     probes::CreateObject(cxArg, arr);
michael@0:     return arr;
michael@0: }
michael@0: 
michael@0: ArrayObject * JS_FASTCALL
michael@0: js::NewDenseEmptyArray(JSContext *cx, JSObject *proto /* = nullptr */,
michael@0:                        NewObjectKind newKind /* = GenericObject */)
michael@0: {
michael@0:     return NewArray<false>(cx, 0, proto, newKind);
michael@0: }
michael@0: 
michael@0: ArrayObject * JS_FASTCALL
michael@0: js::NewDenseAllocatedArray(ExclusiveContext *cx, uint32_t length, JSObject *proto /* = nullptr */,
michael@0:                            NewObjectKind newKind /* = GenericObject */)
michael@0: {
michael@0:     return NewArray<true>(cx, length, proto, newKind);
michael@0: }
michael@0: 
michael@0: ArrayObject * JS_FASTCALL
michael@0: js::NewDenseUnallocatedArray(ExclusiveContext *cx, uint32_t length, JSObject *proto /* = nullptr */,
michael@0:                              NewObjectKind newKind /* = GenericObject */)
michael@0: {
michael@0:     return NewArray<false>(cx, length, proto, newKind);
michael@0: }
michael@0: 
michael@0: ArrayObject *
michael@0: js::NewDenseCopiedArray(JSContext *cx, uint32_t length, HandleObject src, uint32_t elementOffset,
michael@0:                         JSObject *proto /* = nullptr */)
michael@0: {
michael@0:     JS_ASSERT(!src->isIndexed());
michael@0: 
michael@0:     ArrayObject* arr = NewArray<true>(cx, length, proto);
michael@0:     if (!arr)
michael@0:         return nullptr;
michael@0: 
michael@0:     JS_ASSERT(arr->getDenseCapacity() >= length);
michael@0: 
michael@0:     const Value* vp = src->getDenseElements() + elementOffset;
michael@0:     arr->setDenseInitializedLength(vp ? length : 0);
michael@0: 
michael@0:     if (vp)
michael@0:         arr->initDenseElements(0, vp, length);
michael@0: 
michael@0:     return arr;
michael@0: }
michael@0: 
michael@0: // values must point at already-rooted Value objects
michael@0: ArrayObject *
michael@0: js::NewDenseCopiedArray(JSContext *cx, uint32_t length, const Value *values,
michael@0:                         JSObject *proto /* = nullptr */, NewObjectKind newKind /* = GenericObject */)
michael@0: {
michael@0:     ArrayObject* arr = NewArray<true>(cx, length, proto);
michael@0:     if (!arr)
michael@0:         return nullptr;
michael@0: 
michael@0:     JS_ASSERT(arr->getDenseCapacity() >= length);
michael@0: 
michael@0:     arr->setDenseInitializedLength(values ? length : 0);
michael@0: 
michael@0:     if (values)
michael@0:         arr->initDenseElements(0, values, length);
michael@0: 
michael@0:     return arr;
michael@0: }
michael@0: 
michael@0: ArrayObject *
michael@0: js::NewDenseAllocatedArrayWithTemplate(JSContext *cx, uint32_t length, JSObject *templateObject)
michael@0: {
michael@0:     gc::AllocKind allocKind = GuessArrayGCKind(length);
michael@0:     JS_ASSERT(CanBeFinalizedInBackground(allocKind, &ArrayObject::class_));
michael@0:     allocKind = GetBackgroundAllocKind(allocKind);
michael@0: 
michael@0:     RootedTypeObject type(cx, templateObject->type());
michael@0:     if (!type)
michael@0:         return nullptr;
michael@0: 
michael@0:     RootedShape shape(cx, templateObject->lastProperty());
michael@0:     if (!shape)
michael@0:         return nullptr;
michael@0: 
michael@0:     gc::InitialHeap heap = GetInitialHeap(GenericObject, &ArrayObject::class_);
michael@0:     Rooted<ArrayObject *> arr(cx, JSObject::createArray(cx, allocKind, heap, shape, type, length));
michael@0:     if (!arr)
michael@0:         return nullptr;
michael@0: 
michael@0:     if (!EnsureNewArrayElements(cx, arr, length))
michael@0:         return nullptr;
michael@0: 
michael@0:     probes::CreateObject(cx, arr);
michael@0: 
michael@0:     return arr;
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: bool
michael@0: js_ArrayInfo(JSContext *cx, unsigned argc, Value *vp)
michael@0: {
michael@0:     CallArgs args = CallArgsFromVp(argc, vp);
michael@0:     JSObject *obj;
michael@0: 
michael@0:     for (unsigned i = 0; i < args.length(); i++) {
michael@0:         RootedValue arg(cx, args[i]);
michael@0: 
michael@0:         char *bytes = DecompileValueGenerator(cx, JSDVG_SEARCH_STACK, arg, NullPtr());
michael@0:         if (!bytes)
michael@0:             return false;
michael@0:         if (arg.isPrimitive() ||
michael@0:             !(obj = arg.toObjectOrNull())->is<ArrayObject>()) {
michael@0:             fprintf(stderr, "%s: not array\n", bytes);
michael@0:             js_free(bytes);
michael@0:             continue;
michael@0:         }
michael@0:         fprintf(stderr, "%s: (len %u", bytes, obj->as<ArrayObject>().length());
michael@0:         fprintf(stderr, ", capacity %u", obj->getDenseCapacity());
michael@0:         fputs(")\n", stderr);
michael@0:         js_free(bytes);
michael@0:     }
michael@0: 
michael@0:     args.rval().setUndefined();
michael@0:     return true;
michael@0: }
michael@0: #endif