summaryrefslogtreecommitdiffstats
path: root/js/src/jsarray.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jsarray.cpp')
-rw-r--r--js/src/jsarray.cpp3798
1 files changed, 3798 insertions, 0 deletions
diff --git a/js/src/jsarray.cpp b/js/src/jsarray.cpp
new file mode 100644
index 000000000..9cbeff6a2
--- /dev/null
+++ b/js/src/jsarray.cpp
@@ -0,0 +1,3798 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "jsarray.h"
+
+#include "mozilla/ArrayUtils.h"
+#include "mozilla/CheckedInt.h"
+#include "mozilla/DebugOnly.h"
+#include "mozilla/FloatingPoint.h"
+#include "mozilla/MathAlgorithms.h"
+
+#include <algorithm>
+
+#include "jsapi.h"
+#include "jsatom.h"
+#include "jscntxt.h"
+#include "jsfriendapi.h"
+#include "jsfun.h"
+#include "jsiter.h"
+#include "jsnum.h"
+#include "jsobj.h"
+#include "jstypes.h"
+#include "jsutil.h"
+
+#include "ds/Sort.h"
+#include "gc/Heap.h"
+#include "jit/InlinableNatives.h"
+#include "js/Class.h"
+#include "js/Conversions.h"
+#include "vm/ArgumentsObject.h"
+#include "vm/Interpreter.h"
+#include "vm/SelfHosting.h"
+#include "vm/Shape.h"
+#include "vm/StringBuffer.h"
+#include "vm/TypedArrayCommon.h"
+#include "vm/WrapperObject.h"
+
+#include "jsatominlines.h"
+
+#include "vm/ArgumentsObject-inl.h"
+#include "vm/ArrayObject-inl.h"
+#include "vm/Caches-inl.h"
+#include "vm/Interpreter-inl.h"
+#include "vm/NativeObject-inl.h"
+#include "vm/UnboxedObject-inl.h"
+
+using namespace js;
+using namespace js::gc;
+
+using mozilla::Abs;
+using mozilla::ArrayLength;
+using mozilla::CeilingLog2;
+using mozilla::CheckedInt;
+using mozilla::DebugOnly;
+using mozilla::IsNaN;
+
+using JS::AutoCheckCannotGC;
+using JS::IsArrayAnswer;
+using JS::ToUint32;
+
+bool
+JS::IsArray(JSContext* cx, HandleObject obj, IsArrayAnswer* answer)
+{
+ if (obj->is<ArrayObject>() || obj->is<UnboxedArrayObject>()) {
+ *answer = IsArrayAnswer::Array;
+ return true;
+ }
+
+ if (obj->is<ProxyObject>())
+ return Proxy::isArray(cx, obj, answer);
+
+ *answer = IsArrayAnswer::NotArray;
+ return true;
+}
+
+bool
+JS::IsArray(JSContext* cx, HandleObject obj, bool* isArray)
+{
+ IsArrayAnswer answer;
+ if (!IsArray(cx, obj, &answer))
+ return false;
+
+ if (answer == IsArrayAnswer::RevokedProxy) {
+ JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_PROXY_REVOKED);
+ return false;
+ }
+
+ *isArray = answer == IsArrayAnswer::Array;
+ return true;
+}
+
+bool
+js::GetLengthProperty(JSContext* cx, HandleObject obj, uint32_t* lengthp)
+{
+ if (obj->is<ArrayObject>()) {
+ *lengthp = obj->as<ArrayObject>().length();
+ return true;
+ }
+
+ if (obj->is<UnboxedArrayObject>()) {
+ *lengthp = obj->as<UnboxedArrayObject>().length();
+ return true;
+ }
+
+ if (obj->is<ArgumentsObject>()) {
+ ArgumentsObject& argsobj = obj->as<ArgumentsObject>();
+ if (!argsobj.hasOverriddenLength()) {
+ *lengthp = argsobj.initialLength();
+ return true;
+ }
+ }
+
+ RootedValue value(cx);
+ if (!GetProperty(cx, obj, obj, cx->names().length, &value))
+ return false;
+
+ bool overflow;
+ if (!ToLengthClamped(cx, value, lengthp, &overflow)) {
+ if (!overflow)
+ return false;
+ *lengthp = UINT32_MAX;
+ }
+ return true;
+}
+
+/*
+ * Determine if the id represents an array index.
+ *
+ * An id is an array index according to ECMA by (15.4):
+ *
+ * "Array objects give special treatment to a certain class of property names.
+ * A property name P (in the form of a string value) is an array index if and
+ * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
+ * to 2^32-1."
+ *
+ * This means the largest allowed index is actually 2^32-2 (4294967294).
+ *
+ * In our implementation, it would be sufficient to check for id.isInt32()
+ * except that by using signed 31-bit integers we miss the top half of the
+ * valid range. This function checks the string representation itself; note
+ * that calling a standard conversion routine might allow strings such as
+ * "08" or "4.0" as array indices, which they are not.
+ *
+ */
+template <typename CharT>
+static bool
+StringIsArrayIndex(const CharT* s, uint32_t length, uint32_t* indexp)
+{
+ const CharT* end = s + length;
+
+ if (length == 0 || length > (sizeof("4294967294") - 1) || !JS7_ISDEC(*s))
+ return false;
+
+ uint32_t c = 0, previous = 0;
+ uint32_t index = JS7_UNDEC(*s++);
+
+ /* Don't allow leading zeros. */
+ if (index == 0 && s != end)
+ return false;
+
+ for (; s < end; s++) {
+ if (!JS7_ISDEC(*s))
+ return false;
+
+ previous = index;
+ c = JS7_UNDEC(*s);
+ index = 10 * index + c;
+ }
+
+ /* Make sure we didn't overflow. */
+ if (previous < (MAX_ARRAY_INDEX / 10) || (previous == (MAX_ARRAY_INDEX / 10) &&
+ c <= (MAX_ARRAY_INDEX % 10))) {
+ MOZ_ASSERT(index <= MAX_ARRAY_INDEX);
+ *indexp = index;
+ return true;
+ }
+
+ return false;
+}
+
+JS_FRIEND_API(bool)
+js::StringIsArrayIndex(JSLinearString* str, uint32_t* indexp)
+{
+ AutoCheckCannotGC nogc;
+ return str->hasLatin1Chars()
+ ? ::StringIsArrayIndex(str->latin1Chars(nogc), str->length(), indexp)
+ : ::StringIsArrayIndex(str->twoByteChars(nogc), str->length(), indexp);
+}
+
+static bool
+ToId(JSContext* cx, double index, MutableHandleId id)
+{
+ if (index == uint32_t(index))
+ return IndexToId(cx, uint32_t(index), id);
+
+ Value tmp = DoubleValue(index);
+ return ValueToId<CanGC>(cx, HandleValue::fromMarkedLocation(&tmp), id);
+}
+
+static bool
+ToId(JSContext* cx, uint32_t index, MutableHandleId id)
+{
+ return IndexToId(cx, index, id);
+}
+
+/*
+ * If the property at the given index exists, get its value into location
+ * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
+ * to JSVAL_VOID. This function assumes that the location pointed by vp is
+ * properly rooted and can be used as GC-protected storage for temporaries.
+ */
+template <typename IndexType>
+static inline bool
+DoGetElement(JSContext* cx, HandleObject obj, HandleObject receiver,
+ IndexType index, bool* hole, MutableHandleValue vp)
+{
+ RootedId id(cx);
+ if (!ToId(cx, index, &id))
+ return false;
+
+ bool found;
+ if (!HasProperty(cx, obj, id, &found))
+ return false;
+
+ if (found) {
+ if (!GetProperty(cx, obj, receiver, id, vp))
+ return false;
+ } else {
+ vp.setUndefined();
+ }
+ *hole = !found;
+ return true;
+}
+
+template <typename IndexType>
+static void
+AssertGreaterThanZero(IndexType index)
+{
+ MOZ_ASSERT(index >= 0);
+ MOZ_ASSERT(index == floor(index));
+}
+
+template<>
+void
+AssertGreaterThanZero(uint32_t index)
+{
+}
+
+static bool
+GetElement(JSContext* cx, HandleObject obj, HandleObject receiver,
+ uint32_t index, bool* hole, MutableHandleValue vp)
+{
+ AssertGreaterThanZero(index);
+ if (index < GetAnyBoxedOrUnboxedInitializedLength(obj)) {
+ vp.set(GetAnyBoxedOrUnboxedDenseElement(obj, uint32_t(index)));
+ if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
+ *hole = false;
+ return true;
+ }
+ }
+ if (obj->is<ArgumentsObject>()) {
+ if (obj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
+ *hole = false;
+ return true;
+ }
+ }
+
+ return DoGetElement(cx, obj, receiver, index, hole, vp);
+}
+
+template <typename IndexType>
+static inline bool
+GetElement(JSContext* cx, HandleObject obj, IndexType index, bool* hole, MutableHandleValue vp)
+{
+ return GetElement(cx, obj, obj, index, hole, vp);
+}
+
+bool
+ElementAdder::append(JSContext* cx, HandleValue v)
+{
+ MOZ_ASSERT(index_ < length_);
+ if (resObj_) {
+ DenseElementResult result =
+ SetOrExtendAnyBoxedOrUnboxedDenseElements(cx, resObj_, index_, v.address(), 1);
+ if (result == DenseElementResult::Failure)
+ return false;
+ if (result == DenseElementResult::Incomplete) {
+ if (!DefineElement(cx, resObj_, index_, v))
+ return false;
+ }
+ } else {
+ vp_[index_] = v;
+ }
+ index_++;
+ return true;
+}
+
+void
+ElementAdder::appendHole()
+{
+ MOZ_ASSERT(getBehavior_ == ElementAdder::CheckHasElemPreserveHoles);
+ MOZ_ASSERT(index_ < length_);
+ if (!resObj_)
+ vp_[index_].setMagic(JS_ELEMENTS_HOLE);
+ index_++;
+}
+
+bool
+js::GetElementsWithAdder(JSContext* cx, HandleObject obj, HandleObject receiver,
+ uint32_t begin, uint32_t end, ElementAdder* adder)
+{
+ MOZ_ASSERT(begin <= end);
+
+ RootedValue val(cx);
+ for (uint32_t i = begin; i < end; i++) {
+ if (adder->getBehavior() == ElementAdder::CheckHasElemPreserveHoles) {
+ bool hole;
+ if (!GetElement(cx, obj, receiver, i, &hole, &val))
+ return false;
+ if (hole) {
+ adder->appendHole();
+ continue;
+ }
+ } else {
+ MOZ_ASSERT(adder->getBehavior() == ElementAdder::GetElement);
+ if (!GetElement(cx, obj, receiver, i, &val))
+ return false;
+ }
+ if (!adder->append(cx, val))
+ return false;
+ }
+
+ return true;
+}
+
+template <JSValueType Type>
+DenseElementResult
+GetBoxedOrUnboxedDenseElements(JSObject* aobj, uint32_t length, Value* vp)
+{
+ MOZ_ASSERT(!ObjectMayHaveExtraIndexedProperties(aobj));
+
+ if (length > GetBoxedOrUnboxedInitializedLength<Type>(aobj))
+ return DenseElementResult::Incomplete;
+
+ for (size_t i = 0; i < length; i++) {
+ vp[i] = GetBoxedOrUnboxedDenseElement<Type>(aobj, i);
+
+ // No other indexed properties so hole => undefined.
+ if (vp[i].isMagic(JS_ELEMENTS_HOLE))
+ vp[i] = UndefinedValue();
+ }
+
+ return DenseElementResult::Success;
+}
+
+DefineBoxedOrUnboxedFunctor3(GetBoxedOrUnboxedDenseElements,
+ JSObject*, uint32_t, Value*);
+
+bool
+js::GetElements(JSContext* cx, HandleObject aobj, uint32_t length, Value* vp)
+{
+ if (!ObjectMayHaveExtraIndexedProperties(aobj)) {
+ GetBoxedOrUnboxedDenseElementsFunctor functor(aobj, length, vp);
+ DenseElementResult result = CallBoxedOrUnboxedSpecialization(functor, aobj);
+ if (result != DenseElementResult::Incomplete)
+ return result == DenseElementResult::Success;
+ }
+
+ if (aobj->is<ArgumentsObject>()) {
+ ArgumentsObject& argsobj = aobj->as<ArgumentsObject>();
+ if (!argsobj.hasOverriddenLength()) {
+ if (argsobj.maybeGetElements(0, length, vp))
+ return true;
+ }
+ }
+
+ if (js::GetElementsOp op = aobj->getOpsGetElements()) {
+ ElementAdder adder(cx, vp, length, ElementAdder::GetElement);
+ return op(cx, aobj, 0, length, &adder);
+ }
+
+ for (uint32_t i = 0; i < length; i++) {
+ if (!GetElement(cx, aobj, aobj, i, MutableHandleValue::fromMarkedLocation(&vp[i])))
+ return false;
+ }
+
+ return true;
+}
+
+// Set the value of the property at the given index to v. The behavior of this
+// function is currently incoherent and it sometimes defines the property
+// instead. See bug 1163091.
+static bool
+SetArrayElement(JSContext* cx, HandleObject obj, double index, HandleValue v)
+{
+ MOZ_ASSERT(index >= 0);
+
+ if ((obj->is<ArrayObject>() || obj->is<UnboxedArrayObject>()) && !obj->isIndexed() && index <= UINT32_MAX) {
+ DenseElementResult result =
+ SetOrExtendAnyBoxedOrUnboxedDenseElements(cx, obj, uint32_t(index), v.address(), 1);
+ if (result != DenseElementResult::Incomplete)
+ return result == DenseElementResult::Success;
+ }
+
+ RootedId id(cx);
+ if (!ToId(cx, index, &id))
+ return false;
+
+ return SetProperty(cx, obj, id, v);
+}
+
+/*
+ * Attempt to delete the element |index| from |obj| as if by
+ * |obj.[[Delete]](index)|.
+ *
+ * If an error occurs while attempting to delete the element (that is, the call
+ * to [[Delete]] threw), return false.
+ *
+ * Otherwise call result.succeed() or result.fail() to indicate whether the
+ * deletion attempt succeeded (that is, whether the call to [[Delete]] returned
+ * true or false). (Deletes generally fail only when the property is
+ * non-configurable, but proxies may implement different semantics.)
+ */
+static bool
+DeleteArrayElement(JSContext* cx, HandleObject obj, double index, ObjectOpResult& result)
+{
+ MOZ_ASSERT(index >= 0);
+ MOZ_ASSERT(floor(index) == index);
+
+ if (obj->is<ArrayObject>() && !obj->isIndexed() &&
+ !obj->as<NativeObject>().denseElementsAreFrozen())
+ {
+ ArrayObject* aobj = &obj->as<ArrayObject>();
+ if (index <= UINT32_MAX) {
+ uint32_t idx = uint32_t(index);
+ if (idx < aobj->getDenseInitializedLength()) {
+ if (!aobj->maybeCopyElementsForWrite(cx))
+ return false;
+ if (idx+1 == aobj->getDenseInitializedLength()) {
+ aobj->setDenseInitializedLength(idx);
+ } else {
+ aobj->markDenseElementsNotPacked(cx);
+ aobj->setDenseElement(idx, MagicValue(JS_ELEMENTS_HOLE));
+ }
+ if (!SuppressDeletedElement(cx, obj, idx))
+ return false;
+ }
+ }
+
+ return result.succeed();
+ }
+
+ RootedId id(cx);
+ if (!ToId(cx, index, &id))
+ return false;
+ return DeleteProperty(cx, obj, id, result);
+}
+
+/* ES6 draft rev 32 (2 Febr 2015) 7.3.7 */
+static bool
+DeletePropertyOrThrow(JSContext* cx, HandleObject obj, double index)
+{
+ ObjectOpResult success;
+ if (!DeleteArrayElement(cx, obj, index, success))
+ return false;
+ if (!success) {
+ RootedId id(cx);
+ RootedValue indexv(cx, NumberValue(index));
+ if (!ValueToId<CanGC>(cx, indexv, &id))
+ return false;
+ return success.reportError(cx, obj, id);
+ }
+ return true;
+}
+
+bool
+js::SetLengthProperty(JSContext* cx, HandleObject obj, double length)
+{
+ RootedValue v(cx, NumberValue(length));
+ return SetProperty(cx, obj, cx->names().length, v);
+}
+
+static bool
+array_length_getter(JSContext* cx, HandleObject obj, HandleId id, MutableHandleValue vp)
+{
+ vp.setNumber(obj->as<ArrayObject>().length());
+ return true;
+}
+
+static bool
+array_length_setter(JSContext* cx, HandleObject obj, HandleId id, MutableHandleValue vp,
+ ObjectOpResult& result)
+{
+ if (!obj->is<ArrayObject>()) {
+ // This array .length property was found on the prototype
+ // chain. Ideally the setter should not have been called, but since
+ // we're here, do an impression of SetPropertyByDefining.
+ const Class* clasp = obj->getClass();
+ return DefineProperty(cx, obj, cx->names().length, vp,
+ clasp->getGetProperty(), clasp->getSetProperty(),
+ JSPROP_ENUMERATE, result);
+ }
+
+ Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
+ MOZ_ASSERT(arr->lengthIsWritable(),
+ "setter shouldn't be called if property is non-writable");
+
+ return ArraySetLength(cx, arr, id, JSPROP_PERMANENT, vp, result);
+}
+
+struct ReverseIndexComparator
+{
+ bool operator()(const uint32_t& a, const uint32_t& b, bool* lessOrEqualp) {
+ MOZ_ASSERT(a != b, "how'd we get duplicate indexes?");
+ *lessOrEqualp = b <= a;
+ return true;
+ }
+};
+
+bool
+js::CanonicalizeArrayLengthValue(JSContext* cx, HandleValue v, uint32_t* newLen)
+{
+ double d;
+
+ if (!ToUint32(cx, v, newLen))
+ return false;
+
+ if (!ToNumber(cx, v, &d))
+ return false;
+
+ if (d == *newLen)
+ return true;
+
+ JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
+ return false;
+}
+
+/* ES6 draft rev 34 (2015 Feb 20) 9.4.2.4 ArraySetLength */
+bool
+js::ArraySetLength(JSContext* cx, Handle<ArrayObject*> arr, HandleId id,
+ unsigned attrs, HandleValue value, ObjectOpResult& result)
+{
+ MOZ_ASSERT(id == NameToId(cx->names().length));
+
+ if (!arr->maybeCopyElementsForWrite(cx))
+ return false;
+
+ // Step 1.
+ uint32_t newLen;
+ if (attrs & JSPROP_IGNORE_VALUE) {
+ // The spec has us calling OrdinaryDefineOwnProperty if
+ // Desc.[[Value]] is absent, but our implementation is so different that
+ // this is impossible. Instead, set newLen to the current length and
+ // proceed to step 9.
+ newLen = arr->length();
+ } else {
+ // Step 2 is irrelevant in our implementation.
+
+ // Steps 3-7.
+ MOZ_ASSERT_IF(attrs & JSPROP_IGNORE_VALUE, value.isUndefined());
+ if (!CanonicalizeArrayLengthValue(cx, value, &newLen))
+ return false;
+
+ // Step 8 is irrelevant in our implementation.
+ }
+
+ // Steps 9-11.
+ bool lengthIsWritable = arr->lengthIsWritable();
+#ifdef DEBUG
+ {
+ RootedShape lengthShape(cx, arr->lookupPure(id));
+ MOZ_ASSERT(lengthShape);
+ MOZ_ASSERT(lengthShape->writable() == lengthIsWritable);
+ }
+#endif
+ uint32_t oldLen = arr->length();
+
+ // Part of steps 1.a, 12.a, and 16: Fail if we're being asked to change
+ // enumerability or configurability, or otherwise break the object
+ // invariants. (ES6 checks these by calling OrdinaryDefineOwnProperty, but
+ // in SM, the array length property is hardly ordinary.)
+ if ((attrs & (JSPROP_PERMANENT | JSPROP_IGNORE_PERMANENT)) == 0 ||
+ (attrs & (JSPROP_ENUMERATE | JSPROP_IGNORE_ENUMERATE)) == JSPROP_ENUMERATE ||
+ (attrs & (JSPROP_GETTER | JSPROP_SETTER)) != 0 ||
+ (!lengthIsWritable && (attrs & (JSPROP_READONLY | JSPROP_IGNORE_READONLY)) == 0))
+ {
+ return result.fail(JSMSG_CANT_REDEFINE_PROP);
+ }
+
+ // Steps 12-13 for arrays with non-writable length.
+ if (!lengthIsWritable) {
+ if (newLen == oldLen)
+ return result.succeed();
+
+ return result.fail(JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
+ }
+
+ // Step 19.
+ bool succeeded = true;
+ do {
+ // The initialized length and capacity of an array only need updating
+ // when non-hole elements are added or removed, which doesn't happen
+ // when array length stays the same or increases.
+ if (newLen >= oldLen)
+ break;
+
+ // Attempt to propagate dense-element optimization tricks, if possible,
+ // and avoid the generic (and accordingly slow) deletion code below.
+ // We can only do this if there are only densely-indexed elements.
+ // Once there's a sparse indexed element, there's no good way to know,
+ // save by enumerating all the properties to find it. But we *have* to
+ // know in case that sparse indexed element is non-configurable, as
+ // that element must prevent any deletions below it. Bug 586842 should
+ // fix this inefficiency by moving indexed storage to be entirely
+ // separate from non-indexed storage.
+ // A second reason for this optimization to be invalid is an active
+ // for..in iteration over the array. Keys deleted before being reached
+ // during the iteration must not be visited, and suppressing them here
+ // would be too costly.
+ ObjectGroup* arrGroup = arr->getGroup(cx);
+ if (MOZ_UNLIKELY(!arrGroup))
+ return false;
+ if (!arr->isIndexed() && !MOZ_UNLIKELY(arrGroup->hasAllFlags(OBJECT_FLAG_ITERATED))) {
+ if (!arr->maybeCopyElementsForWrite(cx))
+ return false;
+
+ uint32_t oldCapacity = arr->getDenseCapacity();
+ uint32_t oldInitializedLength = arr->getDenseInitializedLength();
+ MOZ_ASSERT(oldCapacity >= oldInitializedLength);
+ if (oldInitializedLength > newLen)
+ arr->setDenseInitializedLength(newLen);
+ if (oldCapacity > newLen)
+ arr->shrinkElements(cx, newLen);
+
+ // We've done the work of deleting any dense elements needing
+ // deletion, and there are no sparse elements. Thus we can skip
+ // straight to defining the length.
+ break;
+ }
+
+ // Step 15.
+ //
+ // Attempt to delete all elements above the new length, from greatest
+ // to least. If any of these deletions fails, we're supposed to define
+ // the length to one greater than the index that couldn't be deleted,
+ // *with the property attributes specified*. This might convert the
+ // length to be not the value specified, yet non-writable. (You may be
+ // forgiven for thinking these are interesting semantics.) Example:
+ //
+ // var arr =
+ // Object.defineProperty([0, 1, 2, 3], 1, { writable: false });
+ // Object.defineProperty(arr, "length",
+ // { value: 0, writable: false });
+ //
+ // will convert |arr| to an array of non-writable length two, then
+ // throw a TypeError.
+ //
+ // We implement this behavior, in the relevant lops below, by setting
+ // |succeeded| to false. Then we exit the loop, define the length
+ // appropriately, and only then throw a TypeError, if necessary.
+ uint32_t gap = oldLen - newLen;
+ const uint32_t RemoveElementsFastLimit = 1 << 24;
+ if (gap < RemoveElementsFastLimit) {
+ // If we're removing a relatively small number of elements, just do
+ // it exactly by the spec.
+ while (newLen < oldLen) {
+ // Step 15a.
+ oldLen--;
+
+ // Steps 15b-d.
+ ObjectOpResult deleteSucceeded;
+ if (!DeleteElement(cx, arr, oldLen, deleteSucceeded))
+ return false;
+ if (!deleteSucceeded) {
+ newLen = oldLen + 1;
+ succeeded = false;
+ break;
+ }
+ }
+ } else {
+ // If we're removing a large number of elements from an array
+ // that's probably sparse, try a different tack. Get all the own
+ // property names, sift out the indexes in the deletion range into
+ // a vector, sort the vector greatest to least, then delete the
+ // indexes greatest to least using that vector. See bug 322135.
+ //
+ // This heuristic's kind of a huge guess -- "large number of
+ // elements" and "probably sparse" are completely unprincipled
+ // predictions. In the long run, bug 586842 will support the right
+ // fix: store sparse elements in a sorted data structure that
+ // permits fast in-reverse-order traversal and concurrent removals.
+
+ Vector<uint32_t> indexes(cx);
+ {
+ AutoIdVector props(cx);
+ if (!GetPropertyKeys(cx, arr, JSITER_OWNONLY | JSITER_HIDDEN, &props))
+ return false;
+
+ for (size_t i = 0; i < props.length(); i++) {
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ uint32_t index;
+ if (!IdIsIndex(props[i], &index))
+ continue;
+
+ if (index >= newLen && index < oldLen) {
+ if (!indexes.append(index))
+ return false;
+ }
+ }
+ }
+
+ uint32_t count = indexes.length();
+ {
+ // We should use radix sort to be O(n), but this is uncommon
+ // enough that we'll punt til someone complains.
+ Vector<uint32_t> scratch(cx);
+ if (!scratch.resize(count))
+ return false;
+ MOZ_ALWAYS_TRUE(MergeSort(indexes.begin(), count, scratch.begin(),
+ ReverseIndexComparator()));
+ }
+
+ uint32_t index = UINT32_MAX;
+ for (uint32_t i = 0; i < count; i++) {
+ MOZ_ASSERT(indexes[i] < index, "indexes should never repeat");
+ index = indexes[i];
+
+ // Steps 15b-d.
+ ObjectOpResult deleteSucceeded;
+ if (!DeleteElement(cx, arr, index, deleteSucceeded))
+ return false;
+ if (!deleteSucceeded) {
+ newLen = index + 1;
+ succeeded = false;
+ break;
+ }
+ }
+ }
+ } while (false);
+
+ // Update array length. Technically we should have been doing this
+ // throughout the loop, in step 19.d.iii.
+ arr->setLength(cx, newLen);
+
+ // Step 20.
+ if (attrs & JSPROP_READONLY) {
+ // Yes, we totally drop a non-stub getter/setter from a defineProperty
+ // API call on the floor here. Given that getter/setter will go away in
+ // the long run, with accessors replacing them both internally and at the
+ // API level, just run with this.
+ RootedShape lengthShape(cx, arr->lookup(cx, id));
+ if (!NativeObject::changeProperty(cx, arr, lengthShape,
+ lengthShape->attributes() | JSPROP_READONLY,
+ array_length_getter, array_length_setter))
+ {
+ return false;
+ }
+ }
+
+ // All operations past here until the |!succeeded| code must be infallible,
+ // so that all element fields remain properly synchronized.
+
+ // Trim the initialized length, if needed, to preserve the <= length
+ // invariant. (Capacity was already reduced during element deletion, if
+ // necessary.)
+ ObjectElements* header = arr->getElementsHeader();
+ header->initializedLength = Min(header->initializedLength, newLen);
+
+ if (attrs & JSPROP_READONLY) {
+ header->setNonwritableArrayLength();
+
+ // When an array's length becomes non-writable, writes to indexes
+ // greater than or equal to the length don't change the array. We
+ // handle this with a check for non-writable length in most places.
+ // But in JIT code every check counts -- so we piggyback the check on
+ // the already-required range check for |index < capacity| by making
+ // capacity of arrays with non-writable length never exceed the length.
+ if (arr->getDenseCapacity() > newLen) {
+ arr->shrinkElements(cx, newLen);
+ arr->getElementsHeader()->capacity = newLen;
+ }
+ }
+
+ if (!succeeded)
+ return result.fail(JSMSG_CANT_TRUNCATE_ARRAY);
+
+ return result.succeed();
+}
+
+bool
+js::WouldDefinePastNonwritableLength(HandleNativeObject obj, uint32_t index)
+{
+ if (!obj->is<ArrayObject>())
+ return false;
+
+ ArrayObject* arr = &obj->as<ArrayObject>();
+ return !arr->lengthIsWritable() && index >= arr->length();
+}
+
+static bool
+array_addProperty(JSContext* cx, HandleObject obj, HandleId id, HandleValue v)
+{
+ Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
+
+ uint32_t index;
+ if (!IdIsIndex(id, &index))
+ return true;
+
+ uint32_t length = arr->length();
+ if (index >= length) {
+ MOZ_ASSERT(arr->lengthIsWritable(),
+ "how'd this element get added if length is non-writable?");
+ arr->setLength(cx, index + 1);
+ }
+ return true;
+}
+
+static inline bool
+ObjectMayHaveExtraIndexedOwnProperties(JSObject* obj)
+{
+ return (!obj->isNative() && !obj->is<UnboxedArrayObject>()) ||
+ obj->isIndexed() ||
+ obj->is<TypedArrayObject>() ||
+ ClassMayResolveId(*obj->runtimeFromAnyThread()->commonNames,
+ obj->getClass(), INT_TO_JSID(0), obj);
+}
+
+/*
+ * Whether obj may have indexed properties anywhere besides its dense
+ * elements. This includes other indexed properties in its shape hierarchy, and
+ * indexed properties or elements along its prototype chain.
+ */
+bool
+js::ObjectMayHaveExtraIndexedProperties(JSObject* obj)
+{
+ MOZ_ASSERT_IF(obj->hasDynamicPrototype(), !obj->isNative());
+
+ if (ObjectMayHaveExtraIndexedOwnProperties(obj))
+ return true;
+
+ do {
+ MOZ_ASSERT(obj->hasStaticPrototype(),
+ "dynamic-prototype objects must be non-native, ergo must "
+ "have failed ObjectMayHaveExtraIndexedOwnProperties");
+
+ obj = obj->staticPrototype();
+ if (!obj)
+ return false; // no extra indexed properties found
+
+ if (ObjectMayHaveExtraIndexedOwnProperties(obj))
+ return true;
+ if (GetAnyBoxedOrUnboxedInitializedLength(obj) != 0)
+ return true;
+ } while (true);
+}
+
+static bool
+AddLengthProperty(ExclusiveContext* cx, HandleArrayObject obj)
+{
+ /*
+ * Add the 'length' property for a newly created array,
+ * and update the elements to be an empty array owned by the object.
+ * The shared emptyObjectElements singleton cannot be used for slow arrays,
+ * as accesses to 'length' will use the elements header.
+ */
+
+ RootedId lengthId(cx, NameToId(cx->names().length));
+ MOZ_ASSERT(!obj->lookup(cx, lengthId));
+
+ return NativeObject::addProperty(cx, obj, lengthId, array_length_getter, array_length_setter,
+ SHAPE_INVALID_SLOT,
+ JSPROP_PERMANENT | JSPROP_SHARED | JSPROP_SHADOWABLE,
+ 0, /* allowDictionary = */ false);
+}
+
+static bool
+IsArrayConstructor(const JSObject* obj)
+{
+ // This must only return true if v is *the* Array constructor for the
+ // current compartment; we rely on the fact that any other Array
+ // constructor would be represented as a wrapper.
+ return obj->is<JSFunction>() &&
+ obj->as<JSFunction>().isNative() &&
+ obj->as<JSFunction>().native() == ArrayConstructor;
+}
+
+static bool
+IsArrayConstructor(const Value& v)
+{
+ return v.isObject() && IsArrayConstructor(&v.toObject());
+}
+
+bool
+js::IsWrappedArrayConstructor(JSContext* cx, const Value& v, bool* result)
+{
+ if (!v.isObject()) {
+ *result = false;
+ return true;
+ }
+ if (v.toObject().is<WrapperObject>()) {
+ JSObject* obj = CheckedUnwrap(&v.toObject());
+ if (!obj) {
+ JS_ReportErrorASCII(cx, "Permission denied to access object");
+ return false;
+ }
+
+ *result = IsArrayConstructor(obj);
+ } else {
+ *result = false;
+ }
+ return true;
+}
+
+static bool
+IsArraySpecies(JSContext* cx, HandleObject origArray)
+{
+ RootedValue ctor(cx);
+ if (!GetPropertyPure(cx, origArray, NameToId(cx->names().constructor), ctor.address()))
+ return false;
+
+ if (!IsArrayConstructor(ctor))
+ return false;
+
+ RootedObject ctorObj(cx, &ctor.toObject());
+ RootedId speciesId(cx, SYMBOL_TO_JSID(cx->wellKnownSymbols().species));
+ JSFunction* getter;
+ if (!GetGetterPure(cx, ctorObj, speciesId, &getter))
+ return false;
+
+ if (!getter)
+ return false;
+
+ return IsSelfHostedFunctionWithName(getter, cx->names().ArraySpecies);
+}
+
+static bool
+ArraySpeciesCreate(JSContext* cx, HandleObject origArray, uint32_t length, MutableHandleObject arr)
+{
+ RootedId createId(cx, NameToId(cx->names().ArraySpeciesCreate));
+ RootedFunction create(cx, JS::GetSelfHostedFunction(cx, "ArraySpeciesCreate", createId, 2));
+ if (!create)
+ return false;
+
+ FixedInvokeArgs<2> args(cx);
+
+ args[0].setObject(*origArray);
+ args[1].set(NumberValue(length));
+
+ RootedValue callee(cx, ObjectValue(*create));
+ RootedValue rval(cx);
+ if (!Call(cx, callee, UndefinedHandleValue, args, &rval))
+ return false;
+
+ MOZ_ASSERT(rval.isObject());
+ arr.set(&rval.toObject());
+ return true;
+}
+
+#if JS_HAS_TOSOURCE
+
+static bool
+array_toSource(JSContext* cx, unsigned argc, Value* vp)
+{
+ JS_CHECK_RECURSION(cx, return false);
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ if (!args.thisv().isObject()) {
+ ReportIncompatible(cx, args);
+ return false;
+ }
+
+ Rooted<JSObject*> obj(cx, &args.thisv().toObject());
+ RootedValue elt(cx);
+
+ AutoCycleDetector detector(cx, obj);
+ if (!detector.init())
+ return false;
+
+ StringBuffer sb(cx);
+
+ if (detector.foundCycle()) {
+ if (!sb.append("[]"))
+ return false;
+ goto make_string;
+ }
+
+ if (!sb.append('['))
+ return false;
+
+ uint32_t length;
+ if (!GetLengthProperty(cx, obj, &length))
+ return false;
+
+ for (uint32_t index = 0; index < length; index++) {
+ bool hole;
+ if (!CheckForInterrupt(cx) ||
+ !GetElement(cx, obj, index, &hole, &elt)) {
+ return false;
+ }
+
+ /* Get element's character string. */
+ JSString* str;
+ if (hole) {
+ str = cx->runtime()->emptyString;
+ } else {
+ str = ValueToSource(cx, elt);
+ if (!str)
+ return false;
+ }
+
+ /* Append element to buffer. */
+ if (!sb.append(str))
+ return false;
+ if (index + 1 != length) {
+ if (!sb.append(", "))
+ return false;
+ } else if (hole) {
+ if (!sb.append(','))
+ return false;
+ }
+ }
+
+ /* Finalize the buffer. */
+ if (!sb.append(']'))
+ return false;
+
+ make_string:
+ JSString* str = sb.finishString();
+ if (!str)
+ return false;
+
+ args.rval().setString(str);
+ return true;
+}
+
+#endif
+
+struct EmptySeparatorOp
+{
+ bool operator()(JSContext*, StringBuffer& sb) { return true; }
+};
+
+template <typename CharT>
+struct CharSeparatorOp
+{
+ const CharT sep;
+ explicit CharSeparatorOp(CharT sep) : sep(sep) {}
+ bool operator()(JSContext*, StringBuffer& sb) { return sb.append(sep); }
+};
+
+struct StringSeparatorOp
+{
+ HandleLinearString sep;
+
+ explicit StringSeparatorOp(HandleLinearString sep) : sep(sep) {}
+
+ bool operator()(JSContext* cx, StringBuffer& sb) {
+ return sb.append(sep);
+ }
+};
+
+template <typename SeparatorOp, JSValueType Type>
+static DenseElementResult
+ArrayJoinDenseKernel(JSContext* cx, SeparatorOp sepOp, HandleObject obj, uint32_t length,
+ StringBuffer& sb, uint32_t* numProcessed)
+{
+ // This loop handles all elements up to initializedLength. If
+ // length > initLength we rely on the second loop to add the
+ // other elements.
+ MOZ_ASSERT(*numProcessed == 0);
+ uint32_t initLength = Min<uint32_t>(GetBoxedOrUnboxedInitializedLength<Type>(obj), length);
+ while (*numProcessed < initLength) {
+ if (!CheckForInterrupt(cx))
+ return DenseElementResult::Failure;
+
+ Value elem = GetBoxedOrUnboxedDenseElement<Type>(obj, *numProcessed);
+
+ if (elem.isString()) {
+ if (!sb.append(elem.toString()))
+ return DenseElementResult::Failure;
+ } else if (elem.isNumber()) {
+ if (!NumberValueToStringBuffer(cx, elem, sb))
+ return DenseElementResult::Failure;
+ } else if (elem.isBoolean()) {
+ if (!BooleanToStringBuffer(elem.toBoolean(), sb))
+ return DenseElementResult::Failure;
+ } else if (elem.isObject() || elem.isSymbol()) {
+ /*
+ * Object stringifying could modify the initialized length or make
+ * the array sparse. Delegate it to a separate loop to keep this
+ * one tight.
+ *
+ * Symbol stringifying is a TypeError, so into the slow path
+ * with those as well.
+ */
+ break;
+ } else {
+ MOZ_ASSERT(elem.isMagic(JS_ELEMENTS_HOLE) || elem.isNullOrUndefined());
+ }
+
+ if (++(*numProcessed) != length && !sepOp(cx, sb))
+ return DenseElementResult::Failure;
+ }
+
+ return DenseElementResult::Incomplete;
+}
+
+template <typename SeparatorOp>
+struct ArrayJoinDenseKernelFunctor {
+ JSContext* cx;
+ SeparatorOp sepOp;
+ HandleObject obj;
+ uint32_t length;
+ StringBuffer& sb;
+ uint32_t* numProcessed;
+
+ ArrayJoinDenseKernelFunctor(JSContext* cx, SeparatorOp sepOp, HandleObject obj,
+ uint32_t length, StringBuffer& sb, uint32_t* numProcessed)
+ : cx(cx), sepOp(sepOp), obj(obj), length(length), sb(sb), numProcessed(numProcessed)
+ {}
+
+ template <JSValueType Type>
+ DenseElementResult operator()() {
+ return ArrayJoinDenseKernel<SeparatorOp, Type>(cx, sepOp, obj, length, sb, numProcessed);
+ }
+};
+
+template <typename SeparatorOp>
+static bool
+ArrayJoinKernel(JSContext* cx, SeparatorOp sepOp, HandleObject obj, uint32_t length,
+ StringBuffer& sb)
+{
+ uint32_t i = 0;
+
+ if (!ObjectMayHaveExtraIndexedProperties(obj)) {
+ ArrayJoinDenseKernelFunctor<SeparatorOp> functor(cx, sepOp, obj, length, sb, &i);
+ DenseElementResult result = CallBoxedOrUnboxedSpecialization(functor, obj);
+ if (result == DenseElementResult::Failure)
+ return false;
+ }
+
+ if (i != length) {
+ RootedValue v(cx);
+ while (i < length) {
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ bool hole;
+ if (!GetElement(cx, obj, i, &hole, &v))
+ return false;
+ if (!hole && !v.isNullOrUndefined()) {
+ if (!ValueToStringBuffer(cx, v, sb))
+ return false;
+ }
+
+ if (++i != length && !sepOp(cx, sb))
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/* ES5 15.4.4.5 */
+bool
+js::array_join(JSContext* cx, unsigned argc, Value* vp)
+{
+ JS_CHECK_RECURSION(cx, return false);
+
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.join");
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ // Step 1
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ AutoCycleDetector detector(cx, obj);
+ if (!detector.init())
+ return false;
+
+ if (detector.foundCycle()) {
+ args.rval().setString(cx->names().empty);
+ return true;
+ }
+
+ // Steps 2 and 3
+ uint32_t length;
+ if (!GetLengthProperty(cx, obj, &length))
+ return false;
+
+ // Steps 4 and 5
+ RootedLinearString sepstr(cx);
+ if (args.hasDefined(0)) {
+ JSString *s = ToString<CanGC>(cx, args[0]);
+ if (!s)
+ return false;
+ sepstr = s->ensureLinear(cx);
+ if (!sepstr)
+ return false;
+ } else {
+ sepstr = cx->names().comma;
+ }
+
+ // Step 6 is implicit in the loops below.
+
+ // An optimized version of a special case of steps 7-11: when length==1 and
+ // the 0th element is a string, ToString() of that element is a no-op and
+ // so it can be immediately returned as the result.
+ if (length == 1 && GetAnyBoxedOrUnboxedInitializedLength(obj) == 1) {
+ Value elem0 = GetAnyBoxedOrUnboxedDenseElement(obj, 0);
+ if (elem0.isString()) {
+ args.rval().set(elem0);
+ return true;
+ }
+ }
+
+ StringBuffer sb(cx);
+ if (sepstr->hasTwoByteChars() && !sb.ensureTwoByteChars())
+ return false;
+
+ // The separator will be added |length - 1| times, reserve space for that
+ // so that we don't have to unnecessarily grow the buffer.
+ size_t seplen = sepstr->length();
+ CheckedInt<uint32_t> res = CheckedInt<uint32_t>(seplen) * (length - 1);
+ if (length > 0 && !res.isValid()) {
+ ReportAllocationOverflow(cx);
+ return false;
+ }
+
+ if (length > 0 && !sb.reserve(res.value()))
+ return false;
+
+ // Various optimized versions of steps 7-10.
+ if (seplen == 0) {
+ EmptySeparatorOp op;
+ if (!ArrayJoinKernel(cx, op, obj, length, sb))
+ return false;
+ } else if (seplen == 1) {
+ char16_t c = sepstr->latin1OrTwoByteChar(0);
+ if (c <= JSString::MAX_LATIN1_CHAR) {
+ CharSeparatorOp<Latin1Char> op(c);
+ if (!ArrayJoinKernel(cx, op, obj, length, sb))
+ return false;
+ } else {
+ CharSeparatorOp<char16_t> op(c);
+ if (!ArrayJoinKernel(cx, op, obj, length, sb))
+ return false;
+ }
+ } else {
+ StringSeparatorOp op(sepstr);
+ if (!ArrayJoinKernel(cx, op, obj, length, sb))
+ return false;
+ }
+
+ // Step 11
+ JSString *str = sb.finishString();
+ if (!str)
+ return false;
+
+ args.rval().setString(str);
+ return true;
+}
+
+// ES2017 draft rev f8a9be8ea4bd97237d176907a1e3080dce20c68f
+// 22.1.3.27 Array.prototype.toLocaleString ([ reserved1 [ , reserved2 ] ])
+// ES2017 Intl draft rev 78bbe7d1095f5ff3760ac4017ed366026e4cb276
+// 13.4.1 Array.prototype.toLocaleString ([ locales [ , options ]])
+static bool
+array_toLocaleString(JSContext* cx, unsigned argc, Value* vp)
+{
+ JS_CHECK_RECURSION(cx, return false);
+
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ // Step 1
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ // Avoid calling into self-hosted code if the array is empty.
+ if (obj->is<ArrayObject>() && obj->as<ArrayObject>().length() == 0) {
+ args.rval().setString(cx->names().empty);
+ return true;
+ }
+ if (obj->is<UnboxedArrayObject>() && obj->as<UnboxedArrayObject>().length() == 0) {
+ args.rval().setString(cx->names().empty);
+ return true;
+ }
+
+ AutoCycleDetector detector(cx, obj);
+ if (!detector.init())
+ return false;
+
+ if (detector.foundCycle()) {
+ args.rval().setString(cx->names().empty);
+ return true;
+ }
+
+ FixedInvokeArgs<2> args2(cx);
+
+ args2[0].set(args.get(0));
+ args2[1].set(args.get(1));
+
+ // Steps 2-10.
+ RootedValue thisv(cx, ObjectValue(*obj));
+ return CallSelfHostedFunction(cx, cx->names().ArrayToLocaleString, thisv, args2, args.rval());
+}
+
+/* vector must point to rooted memory. */
+static bool
+InitArrayElements(JSContext* cx, HandleObject obj, uint32_t start,
+ uint32_t count, const Value* vector,
+ ShouldUpdateTypes updateTypes = ShouldUpdateTypes::Update)
+{
+ MOZ_ASSERT(count <= MAX_ARRAY_INDEX);
+
+ if (count == 0)
+ return true;
+
+ ObjectGroup* group = obj->getGroup(cx);
+ if (!group)
+ return false;
+
+ if (!ObjectMayHaveExtraIndexedProperties(obj)) {
+ DenseElementResult result =
+ SetOrExtendAnyBoxedOrUnboxedDenseElements(cx, obj, start, vector, count, updateTypes);
+ if (result != DenseElementResult::Incomplete)
+ return result == DenseElementResult::Success;
+ }
+
+ const Value* end = vector + count;
+ while (vector < end && start <= MAX_ARRAY_INDEX) {
+ if (!CheckForInterrupt(cx) ||
+ !SetArrayElement(cx, obj, start++, HandleValue::fromMarkedLocation(vector++))) {
+ return false;
+ }
+ }
+
+ if (vector == end)
+ return true;
+
+ MOZ_ASSERT(start == MAX_ARRAY_INDEX + 1);
+ RootedValue value(cx);
+ RootedId id(cx);
+ RootedValue indexv(cx);
+ double index = MAX_ARRAY_INDEX + 1;
+ do {
+ value = *vector++;
+ indexv = DoubleValue(index);
+ if (!ValueToId<CanGC>(cx, indexv, &id))
+ return false;
+ if (!SetProperty(cx, obj, id, value))
+ return false;
+ index += 1;
+ } while (vector != end);
+
+ return true;
+}
+
+template <JSValueType Type>
+DenseElementResult
+ArrayReverseDenseKernel(JSContext* cx, HandleObject obj, uint32_t length)
+{
+ /* An empty array or an array with no elements is already reversed. */
+ if (length == 0 || GetBoxedOrUnboxedInitializedLength<Type>(obj) == 0)
+ return DenseElementResult::Success;
+
+ if (Type == JSVAL_TYPE_MAGIC) {
+ if (obj->as<NativeObject>().denseElementsAreFrozen())
+ return DenseElementResult::Incomplete;
+
+ /*
+ * It's actually surprisingly complicated to reverse an array due to the
+ * orthogonality of array length and array capacity while handling
+ * leading and trailing holes correctly. Reversing seems less likely to
+ * be a common operation than other array mass-mutation methods, so for
+ * now just take a probably-small memory hit (in the absence of too many
+ * holes in the array at its start) and ensure that the capacity is
+ * sufficient to hold all the elements in the array if it were full.
+ */
+ DenseElementResult result = obj->as<NativeObject>().ensureDenseElements(cx, length, 0);
+ if (result != DenseElementResult::Success)
+ return result;
+
+ /* Fill out the array's initialized length to its proper length. */
+ obj->as<NativeObject>().ensureDenseInitializedLength(cx, length, 0);
+ } else {
+ // Unboxed arrays can only be reversed here if their initialized length
+ // matches their actual length. Otherwise the reversal will place holes
+ // at the beginning of the array, which we don't support.
+ if (length != obj->as<UnboxedArrayObject>().initializedLength())
+ return DenseElementResult::Incomplete;
+ }
+
+ RootedValue origlo(cx), orighi(cx);
+
+ uint32_t lo = 0, hi = length - 1;
+ for (; lo < hi; lo++, hi--) {
+ origlo = GetBoxedOrUnboxedDenseElement<Type>(obj, lo);
+ orighi = GetBoxedOrUnboxedDenseElement<Type>(obj, hi);
+ SetBoxedOrUnboxedDenseElementNoTypeChange<Type>(obj, lo, orighi);
+ if (orighi.isMagic(JS_ELEMENTS_HOLE) &&
+ !SuppressDeletedProperty(cx, obj, INT_TO_JSID(lo)))
+ {
+ return DenseElementResult::Failure;
+ }
+ SetBoxedOrUnboxedDenseElementNoTypeChange<Type>(obj, hi, origlo);
+ if (origlo.isMagic(JS_ELEMENTS_HOLE) &&
+ !SuppressDeletedProperty(cx, obj, INT_TO_JSID(hi)))
+ {
+ return DenseElementResult::Failure;
+ }
+ }
+
+ return DenseElementResult::Success;
+}
+
+DefineBoxedOrUnboxedFunctor3(ArrayReverseDenseKernel,
+ JSContext*, HandleObject, uint32_t);
+
+bool
+js::array_reverse(JSContext* cx, unsigned argc, Value* vp)
+{
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.reverse");
+ CallArgs args = CallArgsFromVp(argc, vp);
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ uint32_t len;
+ if (!GetLengthProperty(cx, obj, &len))
+ return false;
+
+ if (!ObjectMayHaveExtraIndexedProperties(obj)) {
+ ArrayReverseDenseKernelFunctor functor(cx, obj, len);
+ DenseElementResult result = CallBoxedOrUnboxedSpecialization(functor, obj);
+ if (result != DenseElementResult::Incomplete) {
+ /*
+ * Per ECMA-262, don't update the length of the array, even if the new
+ * array has trailing holes (and thus the original array began with
+ * holes).
+ */
+ args.rval().setObject(*obj);
+ return result == DenseElementResult::Success;
+ }
+ }
+
+ RootedValue lowval(cx), hival(cx);
+ for (uint32_t i = 0, half = len / 2; i < half; i++) {
+ bool hole, hole2;
+ if (!CheckForInterrupt(cx) ||
+ !GetElement(cx, obj, i, &hole, &lowval) ||
+ !GetElement(cx, obj, len - i - 1, &hole2, &hival))
+ {
+ return false;
+ }
+
+ if (!hole && !hole2) {
+ if (!SetArrayElement(cx, obj, i, hival))
+ return false;
+ if (!SetArrayElement(cx, obj, len - i - 1, lowval))
+ return false;
+ } else if (hole && !hole2) {
+ if (!SetArrayElement(cx, obj, i, hival))
+ return false;
+ if (!DeletePropertyOrThrow(cx, obj, len - i - 1))
+ return false;
+ } else if (!hole && hole2) {
+ if (!DeletePropertyOrThrow(cx, obj, i))
+ return false;
+ if (!SetArrayElement(cx, obj, len - i - 1, lowval))
+ return false;
+ } else {
+ // No action required.
+ }
+ }
+ args.rval().setObject(*obj);
+ return true;
+}
+
+static inline bool
+CompareStringValues(JSContext* cx, const Value& a, const Value& b, bool* lessOrEqualp)
+{
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ JSString* astr = a.toString();
+ JSString* bstr = b.toString();
+ int32_t result;
+ if (!CompareStrings(cx, astr, bstr, &result))
+ return false;
+
+ *lessOrEqualp = (result <= 0);
+ return true;
+}
+
+static const uint64_t powersOf10[] = {
+ 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 1000000000000ULL
+};
+
+static inline unsigned
+NumDigitsBase10(uint32_t n)
+{
+ /*
+ * This is just floor_log10(n) + 1
+ * Algorithm taken from
+ * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
+ */
+ uint32_t log2 = CeilingLog2(n);
+ uint32_t t = log2 * 1233 >> 12;
+ return t - (n < powersOf10[t]) + 1;
+}
+
+static inline bool
+CompareLexicographicInt32(const Value& a, const Value& b, bool* lessOrEqualp)
+{
+ int32_t aint = a.toInt32();
+ int32_t bint = b.toInt32();
+
+ /*
+ * If both numbers are equal ... trivial
+ * If only one of both is negative --> arithmetic comparison as char code
+ * of '-' is always less than any other digit
+ * If both numbers are negative convert them to positive and continue
+ * handling ...
+ */
+ if (aint == bint) {
+ *lessOrEqualp = true;
+ } else if ((aint < 0) && (bint >= 0)) {
+ *lessOrEqualp = true;
+ } else if ((aint >= 0) && (bint < 0)) {
+ *lessOrEqualp = false;
+ } else {
+ uint32_t auint = Abs(aint);
+ uint32_t buint = Abs(bint);
+
+ /*
+ * ... get number of digits of both integers.
+ * If they have the same number of digits --> arithmetic comparison.
+ * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
+ * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
+ */
+ unsigned digitsa = NumDigitsBase10(auint);
+ unsigned digitsb = NumDigitsBase10(buint);
+ if (digitsa == digitsb) {
+ *lessOrEqualp = (auint <= buint);
+ } else if (digitsa > digitsb) {
+ MOZ_ASSERT((digitsa - digitsb) < ArrayLength(powersOf10));
+ *lessOrEqualp = (uint64_t(auint) < uint64_t(buint) * powersOf10[digitsa - digitsb]);
+ } else { /* if (digitsb > digitsa) */
+ MOZ_ASSERT((digitsb - digitsa) < ArrayLength(powersOf10));
+ *lessOrEqualp = (uint64_t(auint) * powersOf10[digitsb - digitsa] <= uint64_t(buint));
+ }
+ }
+
+ return true;
+}
+
+template <typename Char1, typename Char2>
+static inline bool
+CompareSubStringValues(JSContext* cx, const Char1* s1, size_t len1, const Char2* s2, size_t len2,
+ bool* lessOrEqualp)
+{
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ if (!s1 || !s2)
+ return false;
+
+ int32_t result = CompareChars(s1, len1, s2, len2);
+ *lessOrEqualp = (result <= 0);
+ return true;
+}
+
+namespace {
+
+struct SortComparatorStrings
+{
+ JSContext* const cx;
+
+ explicit SortComparatorStrings(JSContext* cx)
+ : cx(cx) {}
+
+ bool operator()(const Value& a, const Value& b, bool* lessOrEqualp) {
+ return CompareStringValues(cx, a, b, lessOrEqualp);
+ }
+};
+
+struct SortComparatorLexicographicInt32
+{
+ bool operator()(const Value& a, const Value& b, bool* lessOrEqualp) {
+ return CompareLexicographicInt32(a, b, lessOrEqualp);
+ }
+};
+
+struct StringifiedElement
+{
+ size_t charsBegin;
+ size_t charsEnd;
+ size_t elementIndex;
+};
+
+struct SortComparatorStringifiedElements
+{
+ JSContext* const cx;
+ const StringBuffer& sb;
+
+ SortComparatorStringifiedElements(JSContext* cx, const StringBuffer& sb)
+ : cx(cx), sb(sb) {}
+
+ bool operator()(const StringifiedElement& a, const StringifiedElement& b, bool* lessOrEqualp) {
+ size_t lenA = a.charsEnd - a.charsBegin;
+ size_t lenB = b.charsEnd - b.charsBegin;
+
+ if (sb.isUnderlyingBufferLatin1()) {
+ return CompareSubStringValues(cx, sb.rawLatin1Begin() + a.charsBegin, lenA,
+ sb.rawLatin1Begin() + b.charsBegin, lenB,
+ lessOrEqualp);
+ }
+
+ return CompareSubStringValues(cx, sb.rawTwoByteBegin() + a.charsBegin, lenA,
+ sb.rawTwoByteBegin() + b.charsBegin, lenB,
+ lessOrEqualp);
+ }
+};
+
+struct NumericElement
+{
+ double dv;
+ size_t elementIndex;
+};
+
+static bool
+ComparatorNumericLeftMinusRight(const NumericElement& a, const NumericElement& b,
+ bool* lessOrEqualp)
+{
+ *lessOrEqualp = (a.dv <= b.dv);
+ return true;
+}
+
+static bool
+ComparatorNumericRightMinusLeft(const NumericElement& a, const NumericElement& b,
+ bool* lessOrEqualp)
+{
+ *lessOrEqualp = (b.dv <= a.dv);
+ return true;
+}
+
+typedef bool (*ComparatorNumeric)(const NumericElement& a, const NumericElement& b,
+ bool* lessOrEqualp);
+
+static const ComparatorNumeric SortComparatorNumerics[] = {
+ nullptr,
+ nullptr,
+ ComparatorNumericLeftMinusRight,
+ ComparatorNumericRightMinusLeft
+};
+
+static bool
+ComparatorInt32LeftMinusRight(const Value& a, const Value& b, bool* lessOrEqualp)
+{
+ *lessOrEqualp = (a.toInt32() <= b.toInt32());
+ return true;
+}
+
+static bool
+ComparatorInt32RightMinusLeft(const Value& a, const Value& b, bool* lessOrEqualp)
+{
+ *lessOrEqualp = (b.toInt32() <= a.toInt32());
+ return true;
+}
+
+typedef bool (*ComparatorInt32)(const Value& a, const Value& b, bool* lessOrEqualp);
+
+static const ComparatorInt32 SortComparatorInt32s[] = {
+ nullptr,
+ nullptr,
+ ComparatorInt32LeftMinusRight,
+ ComparatorInt32RightMinusLeft
+};
+
+// Note: Values for this enum must match up with SortComparatorNumerics
+// and SortComparatorInt32s.
+enum ComparatorMatchResult {
+ Match_Failure = 0,
+ Match_None,
+ Match_LeftMinusRight,
+ Match_RightMinusLeft
+};
+
+} // namespace
+
+
+/*
+ * Specialize behavior for comparator functions with particular common bytecode
+ * patterns: namely, |return x - y| and |return y - x|.
+ */
+static ComparatorMatchResult
+MatchNumericComparator(JSContext* cx, const Value& v)
+{
+ if (!v.isObject())
+ return Match_None;
+
+ JSObject& obj = v.toObject();
+ if (!obj.is<JSFunction>())
+ return Match_None;
+
+ JSFunction* fun = &obj.as<JSFunction>();
+ if (!fun->isInterpreted() || fun->isClassConstructor())
+ return Match_None;
+
+ JSScript* script = fun->getOrCreateScript(cx);
+ if (!script)
+ return Match_Failure;
+
+ jsbytecode* pc = script->code();
+
+ uint16_t arg0, arg1;
+ if (JSOp(*pc) != JSOP_GETARG)
+ return Match_None;
+ arg0 = GET_ARGNO(pc);
+ pc += JSOP_GETARG_LENGTH;
+
+ if (JSOp(*pc) != JSOP_GETARG)
+ return Match_None;
+ arg1 = GET_ARGNO(pc);
+ pc += JSOP_GETARG_LENGTH;
+
+ if (JSOp(*pc) != JSOP_SUB)
+ return Match_None;
+ pc += JSOP_SUB_LENGTH;
+
+ if (JSOp(*pc) != JSOP_RETURN)
+ return Match_None;
+
+ if (arg0 == 0 && arg1 == 1)
+ return Match_LeftMinusRight;
+
+ if (arg0 == 1 && arg1 == 0)
+ return Match_RightMinusLeft;
+
+ return Match_None;
+}
+
+template <typename K, typename C>
+static inline bool
+MergeSortByKey(K keys, size_t len, K scratch, C comparator, MutableHandle<GCVector<Value>> vec)
+{
+ MOZ_ASSERT(vec.length() >= len);
+
+ /* Sort keys. */
+ if (!MergeSort(keys, len, scratch, comparator))
+ return false;
+
+ /*
+ * Reorder vec by keys in-place, going element by element. When an out-of-
+ * place element is encountered, move that element to its proper position,
+ * displacing whatever element was at *that* point to its proper position,
+ * and so on until an element must be moved to the current position.
+ *
+ * At each outer iteration all elements up to |i| are sorted. If
+ * necessary each inner iteration moves some number of unsorted elements
+ * (including |i|) directly to sorted position. Thus on completion |*vec|
+ * is sorted, and out-of-position elements have moved once. Complexity is
+ * Θ(len) + O(len) == O(2*len), with each element visited at most twice.
+ */
+ for (size_t i = 0; i < len; i++) {
+ size_t j = keys[i].elementIndex;
+ if (i == j)
+ continue; // fixed point
+
+ MOZ_ASSERT(j > i, "Everything less than |i| should be in the right place!");
+ Value tv = vec[j];
+ do {
+ size_t k = keys[j].elementIndex;
+ keys[j].elementIndex = j;
+ vec[j].set(vec[k]);
+ j = k;
+ } while (j != i);
+
+ // We could assert the loop invariant that |i == keys[i].elementIndex|
+ // here if we synced |keys[i].elementIndex|. But doing so would render
+ // the assertion vacuous, so don't bother, even in debug builds.
+ vec[i].set(tv);
+ }
+
+ return true;
+}
+
+/*
+ * Sort Values as strings.
+ *
+ * To minimize #conversions, SortLexicographically() first converts all Values
+ * to strings at once, then sorts the elements by these cached strings.
+ */
+static bool
+SortLexicographically(JSContext* cx, MutableHandle<GCVector<Value>> vec, size_t len)
+{
+ MOZ_ASSERT(vec.length() >= len);
+
+ StringBuffer sb(cx);
+ Vector<StringifiedElement, 0, TempAllocPolicy> strElements(cx);
+
+ /* MergeSort uses the upper half as scratch space. */
+ if (!strElements.resize(2 * len))
+ return false;
+
+ /* Convert Values to strings. */
+ size_t cursor = 0;
+ for (size_t i = 0; i < len; i++) {
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ if (!ValueToStringBuffer(cx, vec[i], sb))
+ return false;
+
+ strElements[i] = { cursor, sb.length(), i };
+ cursor = sb.length();
+ }
+
+ /* Sort Values in vec alphabetically. */
+ return MergeSortByKey(strElements.begin(), len, strElements.begin() + len,
+ SortComparatorStringifiedElements(cx, sb), vec);
+}
+
+/*
+ * Sort Values as numbers.
+ *
+ * To minimize #conversions, SortNumerically first converts all Values to
+ * numerics at once, then sorts the elements by these cached numerics.
+ */
+static bool
+SortNumerically(JSContext* cx, MutableHandle<GCVector<Value>> vec, size_t len,
+ ComparatorMatchResult comp)
+{
+ MOZ_ASSERT(vec.length() >= len);
+
+ Vector<NumericElement, 0, TempAllocPolicy> numElements(cx);
+
+ /* MergeSort uses the upper half as scratch space. */
+ if (!numElements.resize(2 * len))
+ return false;
+
+ /* Convert Values to numerics. */
+ for (size_t i = 0; i < len; i++) {
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ double dv;
+ if (!ToNumber(cx, vec[i], &dv))
+ return false;
+
+ numElements[i] = { dv, i };
+ }
+
+ /* Sort Values in vec numerically. */
+ return MergeSortByKey(numElements.begin(), len, numElements.begin() + len,
+ SortComparatorNumerics[comp], vec);
+}
+
+bool
+js::array_sort(JSContext* cx, unsigned argc, Value* vp)
+{
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ RootedValue fval(cx);
+
+ if (args.hasDefined(0)) {
+ if (args[0].isPrimitive()) {
+ JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_SORT_ARG);
+ return false;
+ }
+ fval = args[0]; /* non-default compare function */
+ } else {
+ fval.setNull();
+ }
+
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ ComparatorMatchResult comp = MatchNumericComparator(cx, fval);
+ if (comp == Match_Failure)
+ return false;
+
+ if (!fval.isNull() && comp == Match_None) {
+ /*
+ * Non-optimized user supplied comparators perform much better when
+ * called from within a self-hosted sorting function.
+ */
+ RootedAtom selfHostedSortAtom(cx, Atomize(cx, "ArraySort", 9));
+ RootedPropertyName selfHostedSortName(cx, selfHostedSortAtom->asPropertyName());
+ RootedValue selfHostedSortValue(cx);
+
+ if (!GlobalObject::getIntrinsicValue(cx, cx->global(), selfHostedSortName,
+ &selfHostedSortValue)) {
+ return false;
+ }
+
+ MOZ_ASSERT(selfHostedSortValue.isObject());
+ MOZ_ASSERT(selfHostedSortValue.toObject().is<JSFunction>());
+
+ return Call(cx, selfHostedSortValue, args.thisv(), fval, args.rval());
+ }
+
+ uint32_t len;
+ if (!GetLengthProperty(cx, obj, &len))
+ return false;
+ if (len < 2) {
+ /* [] and [a] remain unchanged when sorted. */
+ args.rval().setObject(*obj);
+ return true;
+ }
+
+ /*
+ * We need a temporary array of 2 * len Value to hold the array elements
+ * and the scratch space for merge sort. Check that its size does not
+ * overflow size_t, which would allow for indexing beyond the end of the
+ * malloc'd vector.
+ */
+#if JS_BITS_PER_WORD == 32
+ if (size_t(len) > size_t(-1) / (2 * sizeof(Value))) {
+ ReportAllocationOverflow(cx);
+ return false;
+ }
+#endif
+
+ /*
+ * Initialize vec as a root. We will clear elements of vec one by
+ * one while increasing the rooted amount of vec when we know that the
+ * property at the corresponding index exists and its value must be rooted.
+ *
+ * In this way when sorting a huge mostly sparse array we will not
+ * access the tail of vec corresponding to properties that do not
+ * exist, allowing OS to avoiding committing RAM. See bug 330812.
+ */
+ size_t n, undefs;
+ {
+ Rooted<GCVector<Value>> vec(cx, GCVector<Value>(cx));
+ if (!vec.reserve(2 * size_t(len)))
+ return false;
+
+ /*
+ * By ECMA 262, 15.4.4.11, a property that does not exist (which we
+ * call a "hole") is always greater than an existing property with
+ * value undefined and that is always greater than any other property.
+ * Thus to sort holes and undefs we simply count them, sort the rest
+ * of elements, append undefs after them and then make holes after
+ * undefs.
+ */
+ undefs = 0;
+ bool allStrings = true;
+ bool allInts = true;
+ bool extraIndexed = ObjectMayHaveExtraIndexedProperties(obj);
+ RootedValue v(cx);
+ for (uint32_t i = 0; i < len; i++) {
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ /* Clear vec[newlen] before including it in the rooted set. */
+ bool hole;
+ if (!GetElement(cx, obj, i, &hole, &v))
+ return false;
+ if (hole)
+ continue;
+ if (v.isUndefined()) {
+ ++undefs;
+ continue;
+ }
+ vec.infallibleAppend(v);
+ allStrings = allStrings && v.isString();
+ allInts = allInts && v.isInt32();
+ }
+
+
+ /*
+ * If the array only contains holes, we're done. But if it contains
+ * undefs, those must be sorted to the front of the array.
+ */
+ n = vec.length();
+ if (n == 0 && undefs == 0) {
+ args.rval().setObject(*obj);
+ return true;
+ }
+
+ /* Here len == n + undefs + number_of_holes. */
+ if (fval.isNull()) {
+ /*
+ * Sort using the default comparator converting all elements to
+ * strings.
+ */
+ if (allStrings) {
+ JS_ALWAYS_TRUE(vec.resize(n * 2));
+ if (!MergeSort(vec.begin(), n, vec.begin() + n, SortComparatorStrings(cx)))
+ return false;
+ } else if (allInts) {
+ JS_ALWAYS_TRUE(vec.resize(n * 2));
+ if (!MergeSort(vec.begin(), n, vec.begin() + n,
+ SortComparatorLexicographicInt32())) {
+ return false;
+ }
+ } else {
+ if (!SortLexicographically(cx, &vec, n))
+ return false;
+ }
+ } else {
+ if (allInts) {
+ JS_ALWAYS_TRUE(vec.resize(n * 2));
+ if (!MergeSort(vec.begin(), n, vec.begin() + n, SortComparatorInt32s[comp]))
+ return false;
+ } else {
+ if (!SortNumerically(cx, &vec, n, comp))
+ return false;
+ }
+ }
+
+ ShouldUpdateTypes updateTypes = !extraIndexed && (allStrings || allInts)
+ ? ShouldUpdateTypes::DontUpdate
+ : ShouldUpdateTypes::Update;
+ if (!InitArrayElements(cx, obj, 0, uint32_t(n), vec.begin(), updateTypes))
+ return false;
+ }
+
+ /* Set undefs that sorted after the rest of elements. */
+ while (undefs != 0) {
+ --undefs;
+ if (!CheckForInterrupt(cx) || !SetArrayElement(cx, obj, n++, UndefinedHandleValue))
+ return false;
+ }
+
+ /* Re-create any holes that sorted to the end of the array. */
+ while (len > n) {
+ if (!CheckForInterrupt(cx) || !DeletePropertyOrThrow(cx, obj, --len))
+ return false;
+ }
+ args.rval().setObject(*obj);
+ return true;
+}
+
+bool
+js::NewbornArrayPush(JSContext* cx, HandleObject obj, const Value& v)
+{
+ Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
+
+ MOZ_ASSERT(!v.isMagic());
+ MOZ_ASSERT(arr->lengthIsWritable());
+
+ uint32_t length = arr->length();
+ MOZ_ASSERT(length <= arr->getDenseCapacity());
+
+ if (!arr->ensureElements(cx, length + 1))
+ return false;
+
+ arr->setDenseInitializedLength(length + 1);
+ arr->setLengthInt32(length + 1);
+ arr->initDenseElementWithType(cx, length, v);
+ return true;
+}
+
+/* ES5 15.4.4.7 */
+bool
+js::array_push(JSContext* cx, unsigned argc, Value* vp)
+{
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.push");
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ /* Step 1. */
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ /* Steps 2-3. */
+ uint32_t length;
+ if (!GetLengthProperty(cx, obj, &length))
+ return false;
+
+ if (!ObjectMayHaveExtraIndexedProperties(obj)) {
+ DenseElementResult result =
+ SetOrExtendAnyBoxedOrUnboxedDenseElements(cx, obj, length,
+ args.array(), args.length());
+ if (result != DenseElementResult::Incomplete) {
+ if (result == DenseElementResult::Failure)
+ return false;
+
+ uint32_t newlength = length + args.length();
+ args.rval().setNumber(newlength);
+
+ // SetOrExtendAnyBoxedOrUnboxedDenseElements takes care of updating the
+ // length for boxed and unboxed arrays. Handle updates to the length of
+ // non-arrays here.
+ bool isArray;
+ if (!IsArray(cx, obj, &isArray))
+ return false;
+
+ if (!isArray)
+ return SetLengthProperty(cx, obj, newlength);
+
+ return true;
+ }
+ }
+
+ /* Steps 4-5. */
+ if (!InitArrayElements(cx, obj, length, args.length(), args.array()))
+ return false;
+
+ /* Steps 6-7. */
+ double newlength = length + double(args.length());
+ args.rval().setNumber(newlength);
+ return SetLengthProperty(cx, obj, newlength);
+}
+
+/* ES6 20130308 draft 15.4.4.6. */
+bool
+js::array_pop(JSContext* cx, unsigned argc, Value* vp)
+{
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.pop");
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ /* Step 1. */
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ /* Steps 2-3. */
+ uint32_t index;
+ if (!GetLengthProperty(cx, obj, &index))
+ return false;
+
+ /* Steps 4-5. */
+ if (index == 0) {
+ /* Step 4b. */
+ args.rval().setUndefined();
+ } else {
+ /* Step 5a. */
+ index--;
+
+ /* Step 5b, 5e. */
+ bool hole;
+ if (!GetElement(cx, obj, index, &hole, args.rval()))
+ return false;
+
+ /* Step 5c. */
+ if (!hole && !DeletePropertyOrThrow(cx, obj, index))
+ return false;
+ }
+
+ /* Steps 4a, 5d. */
+ return SetLengthProperty(cx, obj, index);
+}
+
+template <JSValueType Type>
+static inline DenseElementResult
+ShiftMoveBoxedOrUnboxedDenseElements(JSObject* obj)
+{
+ MOZ_ASSERT(HasBoxedOrUnboxedDenseElements<Type>(obj));
+
+ /*
+ * At this point the length and initialized length have already been
+ * decremented and the result fetched, so just shift the array elements
+ * themselves.
+ */
+ size_t initlen = GetBoxedOrUnboxedInitializedLength<Type>(obj);
+ if (Type == JSVAL_TYPE_MAGIC) {
+ obj->as<NativeObject>().moveDenseElementsNoPreBarrier(0, 1, initlen);
+ } else {
+ uint8_t* data = obj->as<UnboxedArrayObject>().elements();
+ size_t elementSize = UnboxedTypeSize(Type);
+ memmove(data, data + elementSize, initlen * elementSize);
+ }
+
+ return DenseElementResult::Success;
+}
+
+DefineBoxedOrUnboxedFunctor1(ShiftMoveBoxedOrUnboxedDenseElements, JSObject*);
+
+void
+js::ArrayShiftMoveElements(JSObject* obj)
+{
+ MOZ_ASSERT_IF(obj->is<ArrayObject>(), obj->as<ArrayObject>().lengthIsWritable());
+
+ ShiftMoveBoxedOrUnboxedDenseElementsFunctor functor(obj);
+ JS_ALWAYS_TRUE(CallBoxedOrUnboxedSpecialization(functor, obj) == DenseElementResult::Success);
+}
+
+template <JSValueType Type>
+DenseElementResult
+ArrayShiftDenseKernel(JSContext* cx, HandleObject obj, MutableHandleValue rval)
+{
+ if (ObjectMayHaveExtraIndexedProperties(obj))
+ return DenseElementResult::Incomplete;
+
+ RootedObjectGroup group(cx, obj->getGroup(cx));
+ if (MOZ_UNLIKELY(!group))
+ return DenseElementResult::Failure;
+
+ if (MOZ_UNLIKELY(group->hasAllFlags(OBJECT_FLAG_ITERATED)))
+ return DenseElementResult::Incomplete;
+
+ size_t initlen = GetBoxedOrUnboxedInitializedLength<Type>(obj);
+ if (initlen == 0)
+ return DenseElementResult::Incomplete;
+
+ rval.set(GetBoxedOrUnboxedDenseElement<Type>(obj, 0));
+ if (rval.isMagic(JS_ELEMENTS_HOLE))
+ rval.setUndefined();
+
+ DenseElementResult result = MoveBoxedOrUnboxedDenseElements<Type>(cx, obj, 0, 1, initlen - 1);
+ if (result != DenseElementResult::Success)
+ return result;
+
+ SetBoxedOrUnboxedInitializedLength<Type>(cx, obj, initlen - 1);
+ return DenseElementResult::Success;
+}
+
+DefineBoxedOrUnboxedFunctor3(ArrayShiftDenseKernel,
+ JSContext*, HandleObject, MutableHandleValue);
+
+/* ES5 15.4.4.9 */
+bool
+js::array_shift(JSContext* cx, unsigned argc, Value* vp)
+{
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.shift");
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ /* Step 1. */
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ /* Steps 2-3. */
+ uint32_t len;
+ if (!GetLengthProperty(cx, obj, &len))
+ return false;
+
+ /* Step 4. */
+ if (len == 0) {
+ /* Step 4a. */
+ if (!SetLengthProperty(cx, obj, 0))
+ return false;
+
+ /* Step 4b. */
+ args.rval().setUndefined();
+ return true;
+ }
+
+ uint32_t newlen = len - 1;
+
+ /* Fast paths. */
+ ArrayShiftDenseKernelFunctor functor(cx, obj, args.rval());
+ DenseElementResult result = CallBoxedOrUnboxedSpecialization(functor, obj);
+ if (result != DenseElementResult::Incomplete) {
+ if (result == DenseElementResult::Failure)
+ return false;
+
+ return SetLengthProperty(cx, obj, newlen);
+ }
+
+ /* Steps 5, 10. */
+ bool hole;
+ if (!GetElement(cx, obj, uint32_t(0), &hole, args.rval()))
+ return false;
+
+ /* Steps 6-7. */
+ RootedValue value(cx);
+ for (uint32_t i = 0; i < newlen; i++) {
+ if (!CheckForInterrupt(cx))
+ return false;
+ if (!GetElement(cx, obj, i + 1, &hole, &value))
+ return false;
+ if (hole) {
+ if (!DeletePropertyOrThrow(cx, obj, i))
+ return false;
+ } else {
+ if (!SetArrayElement(cx, obj, i, value))
+ return false;
+ }
+ }
+
+ /* Step 8. */
+ if (!DeletePropertyOrThrow(cx, obj, newlen))
+ return false;
+
+ /* Step 9. */
+ return SetLengthProperty(cx, obj, newlen);
+}
+
+bool
+js::array_unshift(JSContext* cx, unsigned argc, Value* vp)
+{
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.unshift");
+ CallArgs args = CallArgsFromVp(argc, vp);
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ uint32_t length;
+ if (!GetLengthProperty(cx, obj, &length))
+ return false;
+
+ double newlen = length;
+ if (args.length() > 0) {
+ /* Slide up the array to make room for all args at the bottom. */
+ if (length > 0) {
+ // Only include a fast path for boxed arrays. Unboxed arrays can'nt
+ // be optimized here because unshifting temporarily places holes at
+ // the start of the array.
+ bool optimized = false;
+ do {
+ if (!obj->is<ArrayObject>())
+ break;
+ if (ObjectMayHaveExtraIndexedProperties(obj))
+ break;
+ ArrayObject* aobj = &obj->as<ArrayObject>();
+ if (!aobj->lengthIsWritable())
+ break;
+ DenseElementResult result = aobj->ensureDenseElements(cx, length, args.length());
+ if (result != DenseElementResult::Success) {
+ if (result == DenseElementResult::Failure)
+ return false;
+ MOZ_ASSERT(result == DenseElementResult::Incomplete);
+ break;
+ }
+ aobj->moveDenseElements(args.length(), 0, length);
+ for (uint32_t i = 0; i < args.length(); i++)
+ aobj->setDenseElement(i, MagicValue(JS_ELEMENTS_HOLE));
+ optimized = true;
+ } while (false);
+
+ if (!optimized) {
+ double last = length;
+ double upperIndex = last + args.length();
+ RootedValue value(cx);
+ do {
+ --last, --upperIndex;
+ bool hole;
+ if (!CheckForInterrupt(cx))
+ return false;
+ if (!GetElement(cx, obj, last, &hole, &value))
+ return false;
+ if (hole) {
+ if (!DeletePropertyOrThrow(cx, obj, upperIndex))
+ return false;
+ } else {
+ if (!SetArrayElement(cx, obj, upperIndex, value))
+ return false;
+ }
+ } while (last != 0);
+ }
+ }
+
+ /* Copy from args to the bottom of the array. */
+ if (!InitArrayElements(cx, obj, 0, args.length(), args.array()))
+ return false;
+
+ newlen += args.length();
+ }
+ if (!SetLengthProperty(cx, obj, newlen))
+ return false;
+
+ /* Follow Perl by returning the new array length. */
+ args.rval().setNumber(newlen);
+ return true;
+}
+
+/*
+ * Returns true if this is a dense or unboxed array whose |count| properties
+ * starting from |startingIndex| may be accessed (get, set, delete) directly
+ * through its contiguous vector of elements without fear of getters, setters,
+ * etc. along the prototype chain, or of enumerators requiring notification of
+ * modifications.
+ */
+static inline bool
+CanOptimizeForDenseStorage(HandleObject arr, uint32_t startingIndex, uint32_t count, JSContext* cx)
+{
+ /* If the desired properties overflow dense storage, we can't optimize. */
+ if (UINT32_MAX - startingIndex < count)
+ return false;
+
+ /* There's no optimizing possible if it's not an array. */
+ if (!arr->is<ArrayObject>() && !arr->is<UnboxedArrayObject>())
+ return false;
+
+ /* If it's a frozen array, always pick the slow path */
+ if (arr->is<ArrayObject>() && arr->as<ArrayObject>().denseElementsAreFrozen())
+ return false;
+
+ /*
+ * Don't optimize if the array might be in the midst of iteration. We
+ * rely on this to be able to safely move dense array elements around with
+ * just a memmove (see NativeObject::moveDenseArrayElements), without worrying
+ * about updating any in-progress enumerators for properties implicitly
+ * deleted if a hole is moved from one location to another location not yet
+ * visited. See bug 690622.
+ */
+ ObjectGroup* arrGroup = arr->getGroup(cx);
+ if (!arrGroup) {
+ cx->recoverFromOutOfMemory();
+ return false;
+ }
+ if (MOZ_UNLIKELY(arrGroup->hasAllFlags(OBJECT_FLAG_ITERATED)))
+ return false;
+
+ /*
+ * Another potential wrinkle: what if the enumeration is happening on an
+ * object which merely has |arr| on its prototype chain?
+ */
+ if (arr->isDelegate())
+ return false;
+
+ /*
+ * Now watch out for getters and setters along the prototype chain or in
+ * other indexed properties on the object. (Note that non-writable length
+ * is subsumed by the initializedLength comparison.)
+ */
+ return !ObjectMayHaveExtraIndexedProperties(arr) &&
+ startingIndex + count <= GetAnyBoxedOrUnboxedInitializedLength(arr);
+}
+
+/* ES 2016 draft Mar 25, 2016 22.1.3.26. */
+bool
+js::array_splice(JSContext* cx, unsigned argc, Value* vp)
+{
+ return array_splice_impl(cx, argc, vp, true);
+}
+
+static inline bool
+ArraySpliceCopy(JSContext* cx, HandleObject arr, HandleObject obj,
+ uint32_t actualStart, uint32_t actualDeleteCount)
+{
+ /* Steps 14, 15, 15.e. */
+ RootedValue fromValue(cx);
+ for (uint32_t k = 0; k < actualDeleteCount; k++) {
+ /* Step 15.a (implicit). */
+
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ /* Steps 15.b-c, 15.d.i-ii. */
+ bool hole;
+ if (!GetElement(cx, obj, actualStart + k, &hole, &fromValue))
+ return false;
+
+ /* Step 15.d. */
+ if (!hole) {
+ /* Step 15.d.iii-iv. */
+ if (!DefineElement(cx, arr, k, fromValue))
+ return false;
+ }
+ }
+
+ /* Steps 16-17. */
+ return SetLengthProperty(cx, arr, actualDeleteCount);
+}
+
+bool
+js::array_splice_impl(JSContext* cx, unsigned argc, Value* vp, bool returnValueIsUsed)
+{
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.splice");
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ /* Step 1. */
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ /* Step 2. */
+ uint32_t len;
+ if (!GetLengthProperty(cx, obj, &len))
+ return false;
+
+ /* Step 3. */
+ double relativeStart;
+ if (!ToInteger(cx, args.get(0), &relativeStart))
+ return false;
+
+ /* Step 4. */
+ uint32_t actualStart;
+ if (relativeStart < 0)
+ actualStart = Max(len + relativeStart, 0.0);
+ else
+ actualStart = Min(relativeStart, double(len));
+
+ /* Step 5. */
+ uint32_t actualDeleteCount;
+ if (args.length() == 0) {
+ /* Step 5.b. */
+ actualDeleteCount = 0;
+ } else if (args.length() == 1) {
+ /* Step 6.b. */
+ actualDeleteCount = len - actualStart;
+ } else {
+ /* Steps 7.b. */
+ double deleteCountDouble;
+ RootedValue cnt(cx, args[1]);
+ if (!ToInteger(cx, cnt, &deleteCountDouble))
+ return false;
+
+ /* Step 7.c. */
+ actualDeleteCount = Min(Max(deleteCountDouble, 0.0), double(len - actualStart));
+ }
+
+ /* Step 8 (implicit). */
+
+ MOZ_ASSERT(len - actualStart >= actualDeleteCount);
+
+ RootedObject arr(cx);
+ if (IsArraySpecies(cx, obj)) {
+ if (CanOptimizeForDenseStorage(obj, actualStart, actualDeleteCount, cx)) {
+ if (returnValueIsUsed) {
+ /* Step 9. */
+ arr = NewFullyAllocatedArrayTryReuseGroup(cx, obj, actualDeleteCount);
+ if (!arr)
+ return false;
+
+ /* Steps 10-11. */
+ DebugOnly<DenseElementResult> result =
+ CopyAnyBoxedOrUnboxedDenseElements(cx, arr, obj, 0, actualStart, actualDeleteCount);
+ MOZ_ASSERT(result.value == DenseElementResult::Success);
+
+ /* Step 12 (implicit). */
+ }
+ } else {
+ /* Step 9. */
+ arr = NewFullyAllocatedArrayTryReuseGroup(cx, obj, actualDeleteCount);
+ if (!arr)
+ return false;
+
+ /* Steps 10-12. */
+ if (!ArraySpliceCopy(cx, arr, obj, actualStart, actualDeleteCount))
+ return false;
+ }
+ } else {
+ /* Steps 9. */
+ if (!ArraySpeciesCreate(cx, obj, actualDeleteCount, &arr))
+ return false;
+
+ /* Steps 10-12. */
+ if (!ArraySpliceCopy(cx, arr, obj, actualStart, actualDeleteCount))
+ return false;
+ }
+
+ /* Step 14. */
+ uint32_t itemCount = (args.length() >= 2) ? (args.length() - 2) : 0;
+
+ if (itemCount < actualDeleteCount) {
+ /* Step 15: the array is being shrunk. */
+ uint32_t sourceIndex = actualStart + actualDeleteCount;
+ uint32_t targetIndex = actualStart + itemCount;
+ uint32_t finalLength = len - actualDeleteCount + itemCount;
+
+ if (CanOptimizeForDenseStorage(obj, 0, len, cx)) {
+ /* Steps 15.a-b. */
+ DenseElementResult result =
+ MoveAnyBoxedOrUnboxedDenseElements(cx, obj, targetIndex, sourceIndex,
+ len - sourceIndex);
+ MOZ_ASSERT(result != DenseElementResult::Incomplete);
+ if (result == DenseElementResult::Failure)
+ return false;
+
+ /* Steps 15.c-d. */
+ SetAnyBoxedOrUnboxedInitializedLength(cx, obj, finalLength);
+ } else {
+ /*
+ * This is all very slow if the length is very large. We don't yet
+ * have the ability to iterate in sorted order, so we just do the
+ * pessimistic thing and let CheckForInterrupt handle the
+ * fallout.
+ */
+
+ /* Steps 15.a-b. */
+ RootedValue fromValue(cx);
+ for (uint32_t from = sourceIndex, to = targetIndex; from < len; from++, to++) {
+ /* Steps 15.b.i-ii (implicit). */
+
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ /* Steps 15.b.iii, 15.b.iv.1. */
+ bool hole;
+ if (!GetElement(cx, obj, from, &hole, &fromValue))
+ return false;
+
+ /* Steps 15.b.iv. */
+ if (hole) {
+ /* Steps 15.b.v.1. */
+ if (!DeletePropertyOrThrow(cx, obj, to))
+ return false;
+ } else {
+ /* Step 15.b.iv.2. */
+ if (!SetArrayElement(cx, obj, to, fromValue))
+ return false;
+ }
+ }
+
+ /* Steps 15.c-d. */
+ for (uint32_t k = len; k > finalLength; k--) {
+ /* Steps 15.d.i-ii. */
+ if (!DeletePropertyOrThrow(cx, obj, k - 1))
+ return false;
+ }
+ }
+ } else if (itemCount > actualDeleteCount) {
+ /* Step 16. */
+
+ /*
+ * Optimize only if the array is already dense and we can extend it to
+ * its new length. It would be wrong to extend the elements here for a
+ * number of reasons.
+ *
+ * First, this could cause us to fall into the fast-path below. This
+ * would cause elements to be moved into places past the non-writable
+ * length. And when the dense initialized length is updated, that'll
+ * cause the |in| operator to think that those elements actually exist,
+ * even though, properly, setting them must fail.
+ *
+ * Second, extending the elements here will trigger assertions inside
+ * ensureDenseElements that the elements aren't being extended past the
+ * length of a non-writable array. This is because extending elements
+ * will extend capacity -- which might extend them past a non-writable
+ * length, violating the |capacity <= length| invariant for such
+ * arrays. And that would make the various JITted fast-path method
+ * implementations of [].push, [].unshift, and so on wrong.
+ *
+ * If the array length is non-writable, this method *will* throw. For
+ * simplicity, have the slow-path code do it. (Also note that the slow
+ * path may validly *not* throw -- if all the elements being moved are
+ * holes.)
+ */
+ if (obj->is<ArrayObject>()) {
+ Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
+ if (arr->lengthIsWritable()) {
+ DenseElementResult result =
+ arr->ensureDenseElements(cx, len, itemCount - actualDeleteCount);
+ if (result == DenseElementResult::Failure)
+ return false;
+ }
+ }
+
+ if (CanOptimizeForDenseStorage(obj, len, itemCount - actualDeleteCount, cx)) {
+ DenseElementResult result =
+ MoveAnyBoxedOrUnboxedDenseElements(cx, obj, actualStart + itemCount,
+ actualStart + actualDeleteCount,
+ len - (actualStart + actualDeleteCount));
+ MOZ_ASSERT(result != DenseElementResult::Incomplete);
+ if (result == DenseElementResult::Failure)
+ return false;
+
+ /* Steps 16.a-b. */
+ SetAnyBoxedOrUnboxedInitializedLength(cx, obj, len + itemCount - actualDeleteCount);
+ } else {
+ RootedValue fromValue(cx);
+ for (double k = len - actualDeleteCount; k > actualStart; k--) {
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ /* Step 16.b.i. */
+ double from = k + actualDeleteCount - 1;
+
+ /* Step 16.b.ii. */
+ double to = k + itemCount - 1;
+
+ /* Steps 16.b.iii, 16.b.iv.1. */
+ bool hole;
+ if (!GetElement(cx, obj, from, &hole, &fromValue))
+ return false;
+
+ /* Steps 16.b.iv. */
+ if (hole) {
+ /* Step 16.b.v.1. */
+ if (!DeletePropertyOrThrow(cx, obj, to))
+ return false;
+ } else {
+ /* Step 16.b.iv.2. */
+ if (!SetArrayElement(cx, obj, to, fromValue))
+ return false;
+ }
+ }
+ }
+ }
+
+ /* Step 13 (reordered). */
+ Value* items = args.array() + 2;
+
+ /* Steps 17-18. */
+ for (uint32_t k = actualStart, i = 0; i < itemCount; i++, k++) {
+ /* Step 18.a (implicit). */
+
+ /* Step 18.b. */
+ if (!SetArrayElement(cx, obj, k, HandleValue::fromMarkedLocation(&items[i])))
+ return false;
+ }
+
+ /* Step 19. */
+ double finalLength = double(len) - actualDeleteCount + itemCount;
+ if (!SetLengthProperty(cx, obj, finalLength))
+ return false;
+
+ /* Step 20. */
+ if (returnValueIsUsed)
+ args.rval().setObject(*arr);
+
+ return true;
+}
+
+struct SortComparatorIndexes
+{
+ bool operator()(uint32_t a, uint32_t b, bool* lessOrEqualp) {
+ *lessOrEqualp = (a <= b);
+ return true;
+ }
+};
+
+// Returns all indexed properties in the range [begin, end) found on |obj| or
+// its proto chain. This function does not handle proxies, objects with
+// resolve/lookupProperty hooks or indexed getters, as those can introduce
+// new properties. In those cases, *success is set to |false|.
+static bool
+GetIndexedPropertiesInRange(JSContext* cx, HandleObject obj, uint32_t begin, uint32_t end,
+ Vector<uint32_t>& indexes, bool* success)
+{
+ *success = false;
+
+ // First, look for proxies or class hooks that can introduce extra
+ // properties.
+ JSObject* pobj = obj;
+ do {
+ if (!pobj->isNative() || pobj->getClass()->getResolve() || pobj->getOpsLookupProperty())
+ return true;
+ } while ((pobj = pobj->staticPrototype()));
+
+ // Collect indexed property names.
+ pobj = obj;
+ do {
+ // Append dense elements.
+ NativeObject* nativeObj = &pobj->as<NativeObject>();
+ uint32_t initLen = nativeObj->getDenseInitializedLength();
+ for (uint32_t i = begin; i < initLen && i < end; i++) {
+ if (nativeObj->getDenseElement(i).isMagic(JS_ELEMENTS_HOLE))
+ continue;
+ if (!indexes.append(i))
+ return false;
+ }
+
+ // Append typed array elements.
+ if (pobj->is<TypedArrayObject>()) {
+ uint32_t len = pobj->as<TypedArrayObject>().length();
+ for (uint32_t i = begin; i < len && i < end; i++) {
+ if (!indexes.append(i))
+ return false;
+ }
+ }
+
+ // Append sparse elements.
+ if (pobj->isIndexed()) {
+ Shape::Range<NoGC> r(pobj->as<NativeObject>().lastProperty());
+ for (; !r.empty(); r.popFront()) {
+ Shape& shape = r.front();
+ jsid id = shape.propid();
+ if (!JSID_IS_INT(id))
+ continue;
+
+ uint32_t i = uint32_t(JSID_TO_INT(id));
+ if (!(begin <= i && i < end))
+ continue;
+
+ // Watch out for getters, they can add new properties.
+ if (!shape.hasDefaultGetter())
+ return true;
+
+ if (!indexes.append(i))
+ return false;
+ }
+ }
+ } while ((pobj = pobj->staticPrototype()));
+
+ // Sort the indexes.
+ Vector<uint32_t> tmp(cx);
+ size_t n = indexes.length();
+ if (!tmp.resize(n))
+ return false;
+ if (!MergeSort(indexes.begin(), n, tmp.begin(), SortComparatorIndexes()))
+ return false;
+
+ // Remove duplicates.
+ if (!indexes.empty()) {
+ uint32_t last = 0;
+ for (size_t i = 1, len = indexes.length(); i < len; i++) {
+ uint32_t elem = indexes[i];
+ if (indexes[last] != elem) {
+ last++;
+ indexes[last] = elem;
+ }
+ }
+ if (!indexes.resize(last + 1))
+ return false;
+ }
+
+ *success = true;
+ return true;
+}
+
+static bool
+SliceSlowly(JSContext* cx, HandleObject obj, HandleObject receiver,
+ uint32_t begin, uint32_t end, HandleObject result)
+{
+ RootedValue value(cx);
+ for (uint32_t slot = begin; slot < end; slot++) {
+ bool hole;
+ if (!CheckForInterrupt(cx) ||
+ !GetElement(cx, obj, receiver, slot, &hole, &value))
+ {
+ return false;
+ }
+ if (!hole && !DefineElement(cx, result, slot - begin, value))
+ return false;
+ }
+ return true;
+}
+
+static bool
+SliceSparse(JSContext* cx, HandleObject obj, uint32_t begin, uint32_t end, HandleObject result)
+{
+ MOZ_ASSERT(begin <= end);
+
+ Vector<uint32_t> indexes(cx);
+ bool success;
+ if (!GetIndexedPropertiesInRange(cx, obj, begin, end, indexes, &success))
+ return false;
+
+ if (!success)
+ return SliceSlowly(cx, obj, obj, begin, end, result);
+
+ RootedValue value(cx);
+ for (size_t i = 0, len = indexes.length(); i < len; i++) {
+ uint32_t index = indexes[i];
+ MOZ_ASSERT(begin <= index && index < end);
+
+ bool hole;
+ if (!GetElement(cx, obj, obj, index, &hole, &value))
+ return false;
+
+ if (!hole && !DefineElement(cx, result, index - begin, value))
+ return false;
+ }
+
+ return true;
+}
+
+template <typename T>
+static inline uint32_t
+NormalizeSliceTerm(T value, uint32_t length)
+{
+ if (value < 0) {
+ value += length;
+ if (value < 0)
+ return 0;
+ } else if (double(value) > double(length)) {
+ return length;
+ }
+ return uint32_t(value);
+}
+
+static bool
+ArraySliceOrdinary(JSContext* cx, HandleObject obj, uint32_t length, uint32_t begin, uint32_t end,
+ MutableHandleObject arr)
+{
+ if (begin > end)
+ begin = end;
+
+ if (!ObjectMayHaveExtraIndexedProperties(obj)) {
+ size_t initlen = GetAnyBoxedOrUnboxedInitializedLength(obj);
+ size_t count = 0;
+ if (initlen > begin)
+ count = Min<size_t>(initlen - begin, end - begin);
+
+ RootedObject narr(cx, NewFullyAllocatedArrayTryReuseGroup(cx, obj, count));
+ if (!narr)
+ return false;
+ SetAnyBoxedOrUnboxedArrayLength(cx, narr, end - begin);
+
+ if (count) {
+ DebugOnly<DenseElementResult> result =
+ CopyAnyBoxedOrUnboxedDenseElements(cx, narr, obj, 0, begin, count);
+ MOZ_ASSERT(result.value == DenseElementResult::Success);
+ }
+ arr.set(narr);
+ return true;
+ }
+
+ RootedObject narr(cx, NewPartlyAllocatedArrayTryReuseGroup(cx, obj, end - begin));
+ if (!narr)
+ return false;
+
+ if (js::GetElementsOp op = obj->getOpsGetElements()) {
+ ElementAdder adder(cx, narr, end - begin, ElementAdder::CheckHasElemPreserveHoles);
+ if (!op(cx, obj, begin, end, &adder))
+ return false;
+
+ arr.set(narr);
+ return true;
+ }
+
+ if (obj->isNative() && obj->isIndexed() && end - begin > 1000) {
+ if (!SliceSparse(cx, obj, begin, end, narr))
+ return false;
+ } else {
+ if (!SliceSlowly(cx, obj, obj, begin, end, narr))
+ return false;
+ }
+
+ arr.set(narr);
+ return true;
+}
+
+/* ES 2016 draft Mar 25, 2016 22.1.3.23. */
+bool
+js::array_slice(JSContext* cx, unsigned argc, Value* vp)
+{
+ AutoSPSEntry pseudoFrame(cx->runtime(), "Array.prototype.slice");
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ /* Step 1. */
+ RootedObject obj(cx, ToObject(cx, args.thisv()));
+ if (!obj)
+ return false;
+
+ /* Step 2. */
+ uint32_t length;
+ if (!GetLengthProperty(cx, obj, &length))
+ return false;
+
+ uint32_t k = 0;
+ uint32_t final = length;
+ if (args.length() > 0) {
+ double d;
+ /* Step 3. */
+ if (!ToInteger(cx, args[0], &d))
+ return false;
+
+ /* Step 4. */
+ k = NormalizeSliceTerm(d, length);
+
+ if (args.hasDefined(1)) {
+ /* Step 5. */
+ if (!ToInteger(cx, args[1], &d))
+ return false;
+
+ /* Step 6. */
+ final = NormalizeSliceTerm(d, length);
+ }
+ }
+
+ /* Step 7. */
+ uint32_t count = final > k ? final - k : 0;
+
+ RootedObject arr(cx);
+ if (IsArraySpecies(cx, obj)) {
+ /* Steps 8-11: Optimized for ordinary array. */
+ if (!ArraySliceOrdinary(cx, obj, length, k, final, &arr))
+ return false;
+
+ /* Step 12. */
+ args.rval().setObject(*arr);
+ return true;
+ }
+
+ /* Step 8. */
+ if (!ArraySpeciesCreate(cx, obj, count, &arr))
+ return false;
+
+ /* Step 9. */
+ uint32_t n = 0;
+
+ /* Step 10. */
+ RootedValue kValue(cx);
+ while (k < final) {
+ if (!CheckForInterrupt(cx))
+ return false;
+
+ /* Steps 10.a-b, and 10.c.i. */
+ bool kNotPresent;
+ if (!GetElement(cx, obj, k, &kNotPresent, &kValue))
+ return false;
+
+ /* Step 10.c. */
+ if (!kNotPresent) {
+ /* Steps 10.c.ii. */
+ if (!DefineElement(cx, arr, n, kValue))
+ return false;
+ }
+ /* Step 10.d. */
+ k++;
+
+ /* Step 10.e. */
+ n++;
+ }
+
+ /* Step 11. */
+ if (!SetLengthProperty(cx, arr, n))
+ return false;
+
+ /* Step 12. */
+ args.rval().setObject(*arr);
+ return true;
+}
+
+template <JSValueType Type>
+DenseElementResult
+ArraySliceDenseKernel(JSContext* cx, JSObject* obj, int32_t beginArg, int32_t endArg, JSObject* result)
+{
+ int32_t length = GetAnyBoxedOrUnboxedArrayLength(obj);
+
+ uint32_t begin = NormalizeSliceTerm(beginArg, length);
+ uint32_t end = NormalizeSliceTerm(endArg, length);
+
+ if (begin > end)
+ begin = end;
+
+ size_t initlen = GetBoxedOrUnboxedInitializedLength<Type>(obj);
+ if (initlen > begin) {
+ size_t count = Min<size_t>(initlen - begin, end - begin);
+ if (count) {
+ DenseElementResult rv = EnsureBoxedOrUnboxedDenseElements<Type>(cx, result, count);
+ if (rv != DenseElementResult::Success)
+ return rv;
+ CopyBoxedOrUnboxedDenseElements<Type, Type>(cx, result, obj, 0, begin, count);
+ }
+ }
+
+ SetAnyBoxedOrUnboxedArrayLength(cx, result, end - begin);
+ return DenseElementResult::Success;
+}
+
+DefineBoxedOrUnboxedFunctor5(ArraySliceDenseKernel,
+ JSContext*, JSObject*, int32_t, int32_t, JSObject*);
+
+JSObject*
+js::array_slice_dense(JSContext* cx, HandleObject obj, int32_t begin, int32_t end,
+ HandleObject result)
+{
+ if (result && IsArraySpecies(cx, obj)) {
+ ArraySliceDenseKernelFunctor functor(cx, obj, begin, end, result);
+ DenseElementResult rv = CallBoxedOrUnboxedSpecialization(functor, result);
+ MOZ_ASSERT(rv != DenseElementResult::Incomplete);
+ return rv == DenseElementResult::Success ? result : nullptr;
+ }
+
+ // Slower path if the JIT wasn't able to allocate an object inline.
+ JS::AutoValueArray<4> argv(cx);
+ argv[0].setUndefined();
+ argv[1].setObject(*obj);
+ argv[2].setInt32(begin);
+ argv[3].setInt32(end);
+ if (!array_slice(cx, 2, argv.begin()))
+ return nullptr;
+ return &argv[0].toObject();
+}
+
+static bool
+array_isArray(JSContext* cx, unsigned argc, Value* vp)
+{
+ CallArgs args = CallArgsFromVp(argc, vp);
+ bool isArray = false;
+ if (args.get(0).isObject()) {
+ RootedObject obj(cx, &args[0].toObject());
+ if (!IsArray(cx, obj, &isArray))
+ return false;
+ }
+ args.rval().setBoolean(isArray);
+ return true;
+}
+
+static bool
+ArrayFromCallArgs(JSContext* cx, CallArgs& args, HandleObject proto = nullptr)
+{
+ JSObject* obj = NewCopiedArrayForCallingAllocationSite(cx, args.array(), args.length(), proto);
+ if (!obj)
+ return false;
+
+ args.rval().setObject(*obj);
+ return true;
+}
+
+static bool
+array_of(JSContext* cx, unsigned argc, Value* vp)
+{
+ CallArgs args = CallArgsFromVp(argc, vp);
+
+ if (IsArrayConstructor(args.thisv()) || !IsConstructor(args.thisv())) {
+ // IsArrayConstructor(this) will usually be true in practice. This is
+ // the most common path.
+ return ArrayFromCallArgs(cx, args);
+ }
+
+ // Step 4.
+ RootedObject obj(cx);
+ {
+ FixedConstructArgs<1> cargs(cx);
+
+ cargs[0].setNumber(args.length());
+
+ if (!Construct(cx, args.thisv(), cargs, args.thisv(), &obj))
+ return false;
+ }
+
+ // Step 8.
+ for (unsigned k = 0; k < args.length(); k++) {
+ if (!DefineElement(cx, obj, k, args[k]))
+ return false;
+ }
+
+ // Steps 9-10.
+ if (!SetLengthProperty(cx, obj, args.length()))
+ return false;
+
+ // Step 11.
+ args.rval().setObject(*obj);
+ return true;
+}
+
+static const JSFunctionSpec array_methods[] = {
+#if JS_HAS_TOSOURCE
+ JS_FN(js_toSource_str, array_toSource, 0,0),
+#endif
+ JS_SELF_HOSTED_FN(js_toString_str, "ArrayToString", 0,0),
+ JS_FN(js_toLocaleString_str, array_toLocaleString, 0,0),
+
+ /* Perl-ish methods. */
+ JS_INLINABLE_FN("join", array_join, 1,0, ArrayJoin),
+ JS_FN("reverse", array_reverse, 0,0),
+ JS_FN("sort", array_sort, 1,0),
+ JS_INLINABLE_FN("push", array_push, 1,0, ArrayPush),
+ JS_INLINABLE_FN("pop", array_pop, 0,0, ArrayPop),
+ JS_INLINABLE_FN("shift", array_shift, 0,0, ArrayShift),
+ JS_FN("unshift", array_unshift, 1,0),
+ JS_INLINABLE_FN("splice", array_splice, 2,0, ArraySplice),
+
+ /* Pythonic sequence methods. */
+ JS_SELF_HOSTED_FN("concat", "ArrayConcat", 1,0),
+ JS_INLINABLE_FN("slice", array_slice, 2,0, ArraySlice),
+
+ JS_SELF_HOSTED_FN("lastIndexOf", "ArrayLastIndexOf", 1,0),
+ JS_SELF_HOSTED_FN("indexOf", "ArrayIndexOf", 1,0),
+ JS_SELF_HOSTED_FN("forEach", "ArrayForEach", 1,0),
+ JS_SELF_HOSTED_FN("map", "ArrayMap", 1,0),
+ JS_SELF_HOSTED_FN("filter", "ArrayFilter", 1,0),
+ JS_SELF_HOSTED_FN("reduce", "ArrayReduce", 1,0),
+ JS_SELF_HOSTED_FN("reduceRight", "ArrayReduceRight", 1,0),
+ JS_SELF_HOSTED_FN("some", "ArraySome", 1,0),
+ JS_SELF_HOSTED_FN("every", "ArrayEvery", 1,0),
+
+ /* ES6 additions */
+ JS_SELF_HOSTED_FN("find", "ArrayFind", 1,0),
+ JS_SELF_HOSTED_FN("findIndex", "ArrayFindIndex", 1,0),
+ JS_SELF_HOSTED_FN("copyWithin", "ArrayCopyWithin", 3,0),
+
+ JS_SELF_HOSTED_FN("fill", "ArrayFill", 3,0),
+
+ JS_SELF_HOSTED_SYM_FN(iterator, "ArrayValues", 0,0),
+ JS_SELF_HOSTED_FN("entries", "ArrayEntries", 0,0),
+ JS_SELF_HOSTED_FN("keys", "ArrayKeys", 0,0),
+#ifdef NIGHTLY_BUILD
+ JS_SELF_HOSTED_FN("values", "ArrayValues", 0,0),
+#endif
+
+ /* ES7 additions */
+ JS_SELF_HOSTED_FN("includes", "ArrayIncludes", 2,0),
+ JS_FS_END
+};
+
+static const JSFunctionSpec array_static_methods[] = {
+ JS_INLINABLE_FN("isArray", array_isArray, 1,0, ArrayIsArray),
+ JS_SELF_HOSTED_FN("concat", "ArrayStaticConcat", 2,0),
+ JS_SELF_HOSTED_FN("lastIndexOf", "ArrayStaticLastIndexOf", 2,0),
+ JS_SELF_HOSTED_FN("indexOf", "ArrayStaticIndexOf", 2,0),
+ JS_SELF_HOSTED_FN("forEach", "ArrayStaticForEach", 2,0),
+ JS_SELF_HOSTED_FN("map", "ArrayStaticMap", 2,0),
+ JS_SELF_HOSTED_FN("filter", "ArrayStaticFilter", 2,0),
+ JS_SELF_HOSTED_FN("every", "ArrayStaticEvery", 2,0),
+ JS_SELF_HOSTED_FN("some", "ArrayStaticSome", 2,0),
+ JS_SELF_HOSTED_FN("reduce", "ArrayStaticReduce", 2,0),
+ JS_SELF_HOSTED_FN("reduceRight", "ArrayStaticReduceRight", 2,0),
+ JS_SELF_HOSTED_FN("join", "ArrayStaticJoin", 2,0),
+ JS_SELF_HOSTED_FN("reverse", "ArrayStaticReverse", 1,0),
+ JS_SELF_HOSTED_FN("sort", "ArrayStaticSort", 2,0),
+ JS_SELF_HOSTED_FN("push", "ArrayStaticPush", 2,0),
+ JS_SELF_HOSTED_FN("pop", "ArrayStaticPop", 1,0),
+ JS_SELF_HOSTED_FN("shift", "ArrayStaticShift", 1,0),
+ JS_SELF_HOSTED_FN("unshift", "ArrayStaticUnshift", 2,0),
+ JS_SELF_HOSTED_FN("splice", "ArrayStaticSplice", 3,0),
+ JS_SELF_HOSTED_FN("slice", "ArrayStaticSlice", 3,0),
+ JS_SELF_HOSTED_FN("from", "ArrayFrom", 3,0),
+ JS_FN("of", array_of, 0,0),
+
+ JS_FS_END
+};
+
+const JSPropertySpec array_static_props[] = {
+ JS_SELF_HOSTED_SYM_GET(species, "ArraySpecies", 0),
+ JS_PS_END
+};
+
+static inline bool
+ArrayConstructorImpl(JSContext* cx, CallArgs& args, bool isConstructor)
+{
+ RootedObject proto(cx);
+ if (isConstructor) {
+ if (!GetPrototypeFromCallableConstructor(cx, args, &proto))
+ return false;
+ } else {
+ // We're emulating |new Array(n)| with |std_Array(n)| in self-hosted JS,
+ // and the proto should be %ArrayPrototype% regardless of the callee.
+ proto = GlobalObject::getOrCreateArrayPrototype(cx, cx->global());
+ if (!proto)
+ return false;
+ }
+
+ if (args.length() != 1 || !args[0].isNumber())
+ return ArrayFromCallArgs(cx, args, proto);
+
+ uint32_t length;
+ if (args[0].isInt32()) {
+ int32_t i = args[0].toInt32();
+ if (i < 0) {
+ JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
+ return false;
+ }
+ length = uint32_t(i);
+ } else {
+ double d = args[0].toDouble();
+ length = ToUint32(d);
+ if (d != double(length)) {
+ JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
+ return false;
+ }
+ }
+
+ JSObject* obj = NewPartlyAllocatedArrayForCallingAllocationSite(cx, length, proto);
+ if (!obj)
+ return false;
+
+ args.rval().setObject(*obj);
+ return true;
+}
+
+/* ES5 15.4.2 */
+bool
+js::ArrayConstructor(JSContext* cx, unsigned argc, Value* vp)
+{
+ CallArgs args = CallArgsFromVp(argc, vp);
+ return ArrayConstructorImpl(cx, args, /* isConstructor = */ true);
+}
+
+bool
+js::array_construct(JSContext* cx, unsigned argc, Value* vp)
+{
+ CallArgs args = CallArgsFromVp(argc, vp);
+ MOZ_ASSERT(!args.isConstructing());
+ MOZ_ASSERT(args.length() == 1);
+ MOZ_ASSERT(args[0].isNumber());
+ return ArrayConstructorImpl(cx, args, /* isConstructor = */ false);
+}
+
+JSObject*
+js::ArrayConstructorOneArg(JSContext* cx, HandleObjectGroup group, int32_t lengthInt)
+{
+ if (lengthInt < 0) {
+ JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
+ return nullptr;
+ }
+
+ uint32_t length = uint32_t(lengthInt);
+ return NewPartlyAllocatedArrayTryUseGroup(cx, group, length);
+}
+
+static JSObject*
+CreateArrayPrototype(JSContext* cx, JSProtoKey key)
+{
+ MOZ_ASSERT(key == JSProto_Array);
+ RootedObject proto(cx, cx->global()->getOrCreateObjectPrototype(cx));
+ if (!proto)
+ return nullptr;
+
+ RootedObjectGroup group(cx, ObjectGroup::defaultNewGroup(cx, &ArrayObject::class_,
+ TaggedProto(proto)));
+ if (!group)
+ return nullptr;
+
+ RootedShape shape(cx, EmptyShape::getInitialShape(cx, &ArrayObject::class_, TaggedProto(proto),
+ gc::AllocKind::OBJECT0));
+ if (!shape)
+ return nullptr;
+
+ AutoSetNewObjectMetadata metadata(cx);
+ RootedArrayObject arrayProto(cx, ArrayObject::createArray(cx, gc::AllocKind::OBJECT4,
+ gc::TenuredHeap, shape, group, 0,
+ metadata));
+ if (!arrayProto ||
+ !JSObject::setSingleton(cx, arrayProto) ||
+ !arrayProto->setDelegate(cx) ||
+ !AddLengthProperty(cx, arrayProto))
+ {
+ return nullptr;
+ }
+
+ /*
+ * The default 'new' group of Array.prototype is required by type inference
+ * to have unknown properties, to simplify handling of e.g. heterogenous
+ * arrays in JSON and script literals and allows setDenseArrayElement to
+ * be used without updating the indexed type set for such default arrays.
+ */
+ if (!JSObject::setNewGroupUnknown(cx, &ArrayObject::class_, arrayProto))
+ return nullptr;
+
+ return arrayProto;
+}
+
+static bool
+array_proto_finish(JSContext* cx, JS::HandleObject ctor, JS::HandleObject proto)
+{
+ // Add Array.prototype[@@unscopables]. ECMA-262 draft (2016 Mar 19) 22.1.3.32.
+ RootedObject unscopables(cx, NewObjectWithGivenProto<PlainObject>(cx, nullptr, TenuredObject));
+ if (!unscopables)
+ return false;
+
+ RootedValue value(cx, BooleanValue(true));
+ if (!DefineProperty(cx, unscopables, cx->names().copyWithin, value) ||
+ !DefineProperty(cx, unscopables, cx->names().entries, value) ||
+ !DefineProperty(cx, unscopables, cx->names().fill, value) ||
+ !DefineProperty(cx, unscopables, cx->names().find, value) ||
+ !DefineProperty(cx, unscopables, cx->names().findIndex, value) ||
+ !DefineProperty(cx, unscopables, cx->names().includes, value) ||
+ !DefineProperty(cx, unscopables, cx->names().keys, value) ||
+ !DefineProperty(cx, unscopables, cx->names().values, value))
+ {
+ return false;
+ }
+
+ RootedId id(cx, SYMBOL_TO_JSID(cx->wellKnownSymbols().get(JS::SymbolCode::unscopables)));
+ value.setObject(*unscopables);
+ return DefineProperty(cx, proto, id, value, nullptr, nullptr, JSPROP_READONLY);
+}
+
+static const ClassOps ArrayObjectClassOps = {
+ array_addProperty,
+ nullptr, /* delProperty */
+ nullptr, /* getProperty */
+ nullptr, /* setProperty */
+ nullptr, /* enumerate */
+ nullptr, /* resolve */
+ nullptr, /* mayResolve */
+ nullptr, /* finalize */
+ nullptr, /* call */
+ nullptr, /* hasInstance */
+ nullptr, /* construct */
+ nullptr, /* trace */
+};
+
+static const ClassSpec ArrayObjectClassSpec = {
+ GenericCreateConstructor<ArrayConstructor, 1, AllocKind::FUNCTION, &jit::JitInfo_Array>,
+ CreateArrayPrototype,
+ array_static_methods,
+ array_static_props,
+ array_methods,
+ nullptr,
+ array_proto_finish
+};
+
+const Class ArrayObject::class_ = {
+ "Array",
+ JSCLASS_HAS_CACHED_PROTO(JSProto_Array) | JSCLASS_DELAY_METADATA_BUILDER,
+ &ArrayObjectClassOps,
+ &ArrayObjectClassSpec
+};
+
+/*
+ * Array allocation functions.
+ */
+
+static inline bool
+EnsureNewArrayElements(ExclusiveContext* cx, ArrayObject* obj, uint32_t length)
+{
+ /*
+ * If ensureElements creates dynamically allocated slots, then having
+ * fixedSlots is a waste.
+ */
+ DebugOnly<uint32_t> cap = obj->getDenseCapacity();
+
+ if (!obj->ensureElements(cx, length))
+ return false;
+
+ MOZ_ASSERT_IF(cap, !obj->hasDynamicElements());
+
+ return true;
+}
+
+template <uint32_t maxLength>
+static MOZ_ALWAYS_INLINE ArrayObject*
+NewArray(ExclusiveContext* cxArg, uint32_t length,
+ HandleObject protoArg, NewObjectKind newKind = GenericObject)
+{
+ gc::AllocKind allocKind = GuessArrayGCKind(length);
+ MOZ_ASSERT(CanBeFinalizedInBackground(allocKind, &ArrayObject::class_));
+ allocKind = GetBackgroundAllocKind(allocKind);
+
+ RootedObject proto(cxArg, protoArg);
+ if (!proto && !GetBuiltinPrototype(cxArg, JSProto_Array, &proto))
+ return nullptr;
+
+ Rooted<TaggedProto> taggedProto(cxArg, TaggedProto(proto));
+ bool isCachable = NewObjectWithTaggedProtoIsCachable(cxArg, taggedProto, newKind, &ArrayObject::class_);
+ if (isCachable) {
+ JSContext* cx = cxArg->asJSContext();
+ NewObjectCache& cache = cx->caches.newObjectCache;
+ NewObjectCache::EntryIndex entry = -1;
+ if (cache.lookupProto(&ArrayObject::class_, proto, allocKind, &entry)) {
+ gc::InitialHeap heap = GetInitialHeap(newKind, &ArrayObject::class_);
+ AutoSetNewObjectMetadata metadata(cx);
+ JSObject* obj = cache.newObjectFromHit(cx, entry, heap);
+ if (obj) {
+ /* Fixup the elements pointer and length, which may be incorrect. */
+ ArrayObject* arr = &obj->as<ArrayObject>();
+ arr->setFixedElements();
+ arr->setLength(cx, length);
+ if (maxLength > 0 &&
+ !EnsureNewArrayElements(cx, arr, std::min(maxLength, length)))
+ {
+ return nullptr;
+ }
+ return arr;
+ }
+ }
+ }
+
+ RootedObjectGroup group(cxArg, ObjectGroup::defaultNewGroup(cxArg, &ArrayObject::class_,
+ TaggedProto(proto)));
+ if (!group)
+ return nullptr;
+
+ /*
+ * Get a shape with zero fixed slots, regardless of the size class.
+ * See JSObject::createArray.
+ */
+ RootedShape shape(cxArg, EmptyShape::getInitialShape(cxArg, &ArrayObject::class_,
+ TaggedProto(proto),
+ gc::AllocKind::OBJECT0));
+ if (!shape)
+ return nullptr;
+
+ AutoSetNewObjectMetadata metadata(cxArg);
+ RootedArrayObject arr(cxArg, ArrayObject::createArray(cxArg, allocKind,
+ GetInitialHeap(newKind, &ArrayObject::class_),
+ shape, group, length, metadata));
+ if (!arr)
+ return nullptr;
+
+ if (shape->isEmptyShape()) {
+ if (!AddLengthProperty(cxArg, arr))
+ return nullptr;
+ shape = arr->lastProperty();
+ EmptyShape::insertInitialShape(cxArg, shape, proto);
+ }
+
+ if (newKind == SingletonObject && !JSObject::setSingleton(cxArg, arr))
+ return nullptr;
+
+ if (isCachable) {
+ NewObjectCache& cache = cxArg->asJSContext()->caches.newObjectCache;
+ NewObjectCache::EntryIndex entry = -1;
+ cache.lookupProto(&ArrayObject::class_, proto, allocKind, &entry);
+ cache.fillProto(entry, &ArrayObject::class_, taggedProto, allocKind, arr);
+ }
+
+ if (maxLength > 0 && !EnsureNewArrayElements(cxArg, arr, std::min(maxLength, length)))
+ return nullptr;
+
+ probes::CreateObject(cxArg, arr);
+ return arr;
+}
+
+ArrayObject * JS_FASTCALL
+js::NewDenseEmptyArray(JSContext* cx, HandleObject proto /* = nullptr */,
+ NewObjectKind newKind /* = GenericObject */)
+{
+ return NewArray<0>(cx, 0, proto, newKind);
+}
+
+ArrayObject * JS_FASTCALL
+js::NewDenseFullyAllocatedArray(ExclusiveContext* cx, uint32_t length,
+ HandleObject proto /* = nullptr */,
+ NewObjectKind newKind /* = GenericObject */)
+{
+ return NewArray<UINT32_MAX>(cx, length, proto, newKind);
+}
+
+ArrayObject * JS_FASTCALL
+js::NewDensePartlyAllocatedArray(ExclusiveContext* cx, uint32_t length,
+ HandleObject proto /* = nullptr */,
+ NewObjectKind newKind /* = GenericObject */)
+{
+ return NewArray<ArrayObject::EagerAllocationMaxLength>(cx, length, proto, newKind);
+}
+
+ArrayObject * JS_FASTCALL
+js::NewDenseUnallocatedArray(ExclusiveContext* cx, uint32_t length,
+ HandleObject proto /* = nullptr */,
+ NewObjectKind newKind /* = GenericObject */)
+{
+ return NewArray<0>(cx, length, proto, newKind);
+}
+
+// values must point at already-rooted Value objects
+ArrayObject*
+js::NewDenseCopiedArray(ExclusiveContext* cx, uint32_t length, const Value* values,
+ HandleObject proto /* = nullptr */,
+ NewObjectKind newKind /* = GenericObject */)
+{
+ ArrayObject* arr = NewArray<UINT32_MAX>(cx, length, proto, newKind);
+ if (!arr)
+ return nullptr;
+
+ MOZ_ASSERT(arr->getDenseCapacity() >= length);
+
+ arr->setDenseInitializedLength(values ? length : 0);
+
+ if (values)
+ arr->initDenseElements(0, values, length);
+
+ return arr;
+}
+
+ArrayObject*
+js::NewDenseFullyAllocatedArrayWithTemplate(JSContext* cx, uint32_t length, JSObject* templateObject)
+{
+ AutoSetNewObjectMetadata metadata(cx);
+ gc::AllocKind allocKind = GuessArrayGCKind(length);
+ MOZ_ASSERT(CanBeFinalizedInBackground(allocKind, &ArrayObject::class_));
+ allocKind = GetBackgroundAllocKind(allocKind);
+
+ RootedObjectGroup group(cx, templateObject->group());
+ RootedShape shape(cx, templateObject->as<ArrayObject>().lastProperty());
+
+ gc::InitialHeap heap = GetInitialHeap(GenericObject, &ArrayObject::class_);
+ Rooted<ArrayObject*> arr(cx, ArrayObject::createArray(cx, allocKind,
+ heap, shape, group, length, metadata));
+ if (!arr)
+ return nullptr;
+
+ if (!EnsureNewArrayElements(cx, arr, length))
+ return nullptr;
+
+ probes::CreateObject(cx, arr);
+
+ return arr;
+}
+
+JSObject*
+js::NewDenseCopyOnWriteArray(JSContext* cx, HandleArrayObject templateObject, gc::InitialHeap heap)
+{
+ MOZ_ASSERT(!gc::IsInsideNursery(templateObject));
+
+ ArrayObject* arr = ArrayObject::createCopyOnWriteArray(cx, heap, templateObject);
+ if (!arr)
+ return nullptr;
+
+ probes::CreateObject(cx, arr);
+ return arr;
+}
+
+// Return a new boxed or unboxed array with the specified length and allocated
+// capacity (up to maxLength), using the specified group if possible. If the
+// specified group cannot be used, ensure that the created array at least has
+// the given [[Prototype]].
+template <uint32_t maxLength>
+static inline JSObject*
+NewArrayTryUseGroup(ExclusiveContext* cx, HandleObjectGroup group, size_t length,
+ NewObjectKind newKind = GenericObject)
+{
+ MOZ_ASSERT(newKind != SingletonObject);
+
+ if (group->maybePreliminaryObjects())
+ group->maybePreliminaryObjects()->maybeAnalyze(cx, group);
+
+ if (group->shouldPreTenure() || group->maybePreliminaryObjects())
+ newKind = TenuredObject;
+
+ RootedObject proto(cx, group->proto().toObject());
+ if (group->maybeUnboxedLayout()) {
+ if (length > UnboxedArrayObject::MaximumCapacity)
+ return NewArray<maxLength>(cx, length, proto, newKind);
+ return UnboxedArrayObject::create(cx, group, length, newKind, maxLength);
+ }
+
+ ArrayObject* res = NewArray<maxLength>(cx, length, proto, newKind);
+ if (!res)
+ return nullptr;
+
+ res->setGroup(group);
+
+ // If the length calculation overflowed, make sure that is marked for the
+ // new group.
+ if (res->length() > INT32_MAX)
+ res->setLength(cx, res->length());
+
+ if (PreliminaryObjectArray* preliminaryObjects = group->maybePreliminaryObjects())
+ preliminaryObjects->registerNewObject(res);
+
+ return res;
+}
+
+JSObject*
+js::NewFullyAllocatedArrayTryUseGroup(ExclusiveContext* cx, HandleObjectGroup group, size_t length,
+ NewObjectKind newKind)
+{
+ return NewArrayTryUseGroup<UINT32_MAX>(cx, group, length, newKind);
+}
+
+JSObject*
+js::NewPartlyAllocatedArrayTryUseGroup(ExclusiveContext* cx, HandleObjectGroup group, size_t length)
+{
+ return NewArrayTryUseGroup<ArrayObject::EagerAllocationMaxLength>(cx, group, length);
+}
+
+// Return a new array with the default prototype and specified allocated
+// capacity and length. If possible, try to reuse the group of the input
+// object. The resulting array will either reuse the input object's group or
+// will have unknown property types. Additionally, the result will have the
+// same boxed/unboxed elements representation as the input object, unless
+// |length| is larger than the input object's initialized length (in which case
+// UnboxedArrayObject::MaximumCapacity might be exceeded).
+template <uint32_t maxLength>
+static inline JSObject*
+NewArrayTryReuseGroup(JSContext* cx, JSObject* obj, size_t length,
+ NewObjectKind newKind = GenericObject)
+{
+ if (!obj->is<ArrayObject>() && !obj->is<UnboxedArrayObject>())
+ return NewArray<maxLength>(cx, length, nullptr, newKind);
+
+ if (obj->staticPrototype() != cx->global()->maybeGetArrayPrototype())
+ return NewArray<maxLength>(cx, length, nullptr, newKind);
+
+ RootedObjectGroup group(cx, obj->getGroup(cx));
+ if (!group)
+ return nullptr;
+
+ return NewArrayTryUseGroup<maxLength>(cx, group, length, newKind);
+}
+
+JSObject*
+js::NewFullyAllocatedArrayTryReuseGroup(JSContext* cx, JSObject* obj, size_t length,
+ NewObjectKind newKind)
+{
+ return NewArrayTryReuseGroup<UINT32_MAX>(cx, obj, length, newKind);
+}
+
+JSObject*
+js::NewPartlyAllocatedArrayTryReuseGroup(JSContext* cx, JSObject* obj, size_t length)
+{
+ return NewArrayTryReuseGroup<ArrayObject::EagerAllocationMaxLength>(cx, obj, length);
+}
+
+JSObject*
+js::NewFullyAllocatedArrayForCallingAllocationSite(JSContext* cx, size_t length,
+ NewObjectKind newKind)
+{
+ RootedObjectGroup group(cx, ObjectGroup::callingAllocationSiteGroup(cx, JSProto_Array));
+ if (!group)
+ return nullptr;
+ return NewArrayTryUseGroup<UINT32_MAX>(cx, group, length, newKind);
+}
+
+JSObject*
+js::NewPartlyAllocatedArrayForCallingAllocationSite(JSContext* cx, size_t length, HandleObject proto)
+{
+ RootedObjectGroup group(cx, ObjectGroup::callingAllocationSiteGroup(cx, JSProto_Array, proto));
+ if (!group)
+ return nullptr;
+ return NewArrayTryUseGroup<ArrayObject::EagerAllocationMaxLength>(cx, group, length);
+}
+
+bool
+js::MaybeAnalyzeBeforeCreatingLargeArray(ExclusiveContext* cx, HandleObjectGroup group,
+ const Value* vp, size_t length)
+{
+ static const size_t EagerPreliminaryObjectAnalysisThreshold = 800;
+
+ // Force analysis to see if an unboxed array can be used when making a
+ // sufficiently large array, to avoid excessive analysis and copying later
+ // on. If this is the first array of its group that is being created, first
+ // make a dummy array with the initial elements of the array we are about
+ // to make, so there is some basis for the unboxed array analysis.
+ if (length > EagerPreliminaryObjectAnalysisThreshold) {
+ if (PreliminaryObjectArrayWithTemplate* objects = group->maybePreliminaryObjects()) {
+ if (objects->empty()) {
+ size_t nlength = Min<size_t>(length, 100);
+ JSObject* obj = NewFullyAllocatedArrayTryUseGroup(cx, group, nlength);
+ if (!obj)
+ return false;
+ DebugOnly<DenseElementResult> result =
+ SetOrExtendAnyBoxedOrUnboxedDenseElements(cx, obj, 0, vp, nlength,
+ ShouldUpdateTypes::Update);
+ MOZ_ASSERT(result.value == DenseElementResult::Success);
+ }
+ objects->maybeAnalyze(cx, group, /* forceAnalyze = */ true);
+ }
+ }
+ return true;
+}
+
+JSObject*
+js::NewCopiedArrayTryUseGroup(ExclusiveContext* cx, HandleObjectGroup group,
+ const Value* vp, size_t length, NewObjectKind newKind,
+ ShouldUpdateTypes updateTypes)
+{
+ if (!MaybeAnalyzeBeforeCreatingLargeArray(cx, group, vp, length))
+ return nullptr;
+
+ JSObject* obj = NewFullyAllocatedArrayTryUseGroup(cx, group, length, newKind);
+ if (!obj)
+ return nullptr;
+
+ DenseElementResult result =
+ SetOrExtendAnyBoxedOrUnboxedDenseElements(cx, obj, 0, vp, length, updateTypes);
+ if (result == DenseElementResult::Failure)
+ return nullptr;
+ if (result == DenseElementResult::Success)
+ return obj;
+
+ MOZ_ASSERT(obj->is<UnboxedArrayObject>());
+ if (!UnboxedArrayObject::convertToNative(cx->asJSContext(), obj))
+ return nullptr;
+
+ result = SetOrExtendBoxedOrUnboxedDenseElements<JSVAL_TYPE_MAGIC>(cx, obj, 0, vp, length,
+ updateTypes);
+ MOZ_ASSERT(result != DenseElementResult::Incomplete);
+ if (result == DenseElementResult::Failure)
+ return nullptr;
+
+ return obj;
+}
+
+JSObject*
+js::NewCopiedArrayForCallingAllocationSite(JSContext* cx, const Value* vp, size_t length,
+ HandleObject proto /* = nullptr */)
+{
+ RootedObjectGroup group(cx, ObjectGroup::callingAllocationSiteGroup(cx, JSProto_Array, proto));
+ if (!group)
+ return nullptr;
+ return NewCopiedArrayTryUseGroup(cx, group, vp, length);
+}
+
+bool
+js::NewValuePair(JSContext* cx, const Value& val1, const Value& val2, MutableHandleValue rval)
+{
+ JS::AutoValueArray<2> vec(cx);
+ vec[0].set(val1);
+ vec[1].set(val2);
+
+ JSObject* aobj = js::NewDenseCopiedArray(cx, 2, vec.begin());
+ if (!aobj)
+ return false;
+ rval.setObject(*aobj);
+ return true;
+}
+
+#ifdef DEBUG
+bool
+js::ArrayInfo(JSContext* cx, unsigned argc, Value* vp)
+{
+ CallArgs args = CallArgsFromVp(argc, vp);
+ RootedObject obj(cx);
+
+ for (unsigned i = 0; i < args.length(); i++) {
+ HandleValue arg = args[i];
+
+ UniqueChars bytes = DecompileValueGenerator(cx, JSDVG_SEARCH_STACK, arg, nullptr);
+ if (!bytes)
+ return false;
+ if (arg.isPrimitive() ||
+ !(obj = arg.toObjectOrNull())->is<ArrayObject>()) {
+ fprintf(stderr, "%s: not array\n", bytes.get());
+ continue;
+ }
+ fprintf(stderr, "%s: (len %u", bytes.get(), obj->as<ArrayObject>().length());
+ fprintf(stderr, ", capacity %u", obj->as<ArrayObject>().getDenseCapacity());
+ fputs(")\n", stderr);
+ }
+
+ args.rval().setUndefined();
+ return true;
+}
+#endif