Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* 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
#include "builtin/Array-inl.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/Maybe.h"
#include "mozilla/SIMD.h"
#include "mozilla/TextUtils.h"
#include <algorithm>
#include <cmath>
#include <iterator>
#include "jsfriendapi.h"
#include "jsnum.h"
#include "jstypes.h"
#include "ds/Sort.h"
#include "gc/Allocator.h"
#include "jit/InlinableNatives.h"
#include "js/Class.h"
#include "js/Conversions.h"
#include "js/experimental/JitInfo.h" // JSJitGetterOp, JSJitInfo
#include "js/friend/ErrorMessages.h" // js::GetErrorMessage, JSMSG_*
#include "js/PropertySpec.h"
#include "util/Poison.h"
#include "util/StringBuffer.h"
#include "util/Text.h"
#include "vm/ArgumentsObject.h"
#include "vm/EqualityOperations.h"
#include "vm/Interpreter.h"
#include "vm/Iteration.h"
#include "vm/JSContext.h"
#include "vm/JSFunction.h"
#include "vm/JSObject.h"
#include "vm/PlainObject.h" // js::PlainObject
#include "vm/SelfHosting.h"
#include "vm/Shape.h"
#include "vm/StringType.h"
#include "vm/ToSource.h" // js::ValueToSource
#include "vm/TypedArrayObject.h"
#include "vm/WrapperObject.h"
#ifdef ENABLE_RECORD_TUPLE
# include "vm/TupleType.h"
#endif
#include "vm/ArgumentsObject-inl.h"
#include "vm/ArrayObject-inl.h"
#include "vm/GeckoProfiler-inl.h"
#include "vm/IsGivenTypeObject-inl.h"
#include "vm/JSAtomUtils-inl.h" // PrimitiveValueToId, IndexToId
#include "vm/NativeObject-inl.h"
using namespace js;
using mozilla::Abs;
using mozilla::CeilingLog2;
using mozilla::CheckedInt;
using mozilla::DebugOnly;
using mozilla::IsAsciiDigit;
using mozilla::Maybe;
using mozilla::SIMD;
using JS::AutoCheckCannotGC;
using JS::IsArrayAnswer;
using JS::ToUint32;
bool js::ObjectMayHaveExtraIndexedOwnProperties(JSObject* obj) {
if (!obj->is<NativeObject>()) {
return true;
}
if (obj->as<NativeObject>().isIndexed()) {
return true;
}
if (obj->is<TypedArrayObject>()) {
return true;
}
return ClassMayResolveId(*obj->runtimeFromAnyThread()->commonNames,
obj->getClass(), PropertyKey::Int(0), obj);
}
bool js::PrototypeMayHaveIndexedProperties(NativeObject* obj) {
do {
MOZ_ASSERT(obj->hasStaticPrototype(),
"dynamic-prototype objects must be non-native");
JSObject* proto = obj->staticPrototype();
if (!proto) {
return false; // no extra indexed properties found
}
if (ObjectMayHaveExtraIndexedOwnProperties(proto)) {
return true;
}
obj = &proto->as<NativeObject>();
if (obj->getDenseInitializedLength() != 0) {
return true;
}
} while (true);
}
/*
* 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->is<NativeObject>());
if (ObjectMayHaveExtraIndexedOwnProperties(obj)) {
return true;
}
return PrototypeMayHaveIndexedProperties(&obj->as<NativeObject>());
}
bool JS::IsArray(JSContext* cx, HandleObject obj, IsArrayAnswer* answer) {
if (obj->is<ArrayObject>()) {
*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::IsArrayFromJit(JSContext* cx, HandleObject obj, bool* isArray) {
return JS::IsArray(cx, obj, isArray);
}
// ES2017 7.1.15 ToLength.
bool js::ToLength(JSContext* cx, HandleValue v, uint64_t* out) {
if (v.isInt32()) {
int32_t i = v.toInt32();
*out = i < 0 ? 0 : i;
return true;
}
double d;
if (v.isDouble()) {
d = v.toDouble();
} else {
if (!ToNumber(cx, v, &d)) {
return false;
}
}
d = JS::ToInteger(d);
if (d <= 0.0) {
*out = 0;
} else {
*out = uint64_t(std::min(d, DOUBLE_INTEGRAL_PRECISION_LIMIT - 1));
}
return true;
}
bool js::GetLengthProperty(JSContext* cx, HandleObject obj, uint64_t* lengthp) {
if (obj->is<ArrayObject>()) {
*lengthp = obj->as<ArrayObject>().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;
}
return ToLength(cx, value, lengthp);
}
// Fast path for array functions where the object is expected to be an array.
static MOZ_ALWAYS_INLINE bool GetLengthPropertyInlined(JSContext* cx,
HandleObject obj,
uint64_t* lengthp) {
if (obj->is<ArrayObject>()) {
*lengthp = obj->as<ArrayObject>().length();
return true;
}
return GetLengthProperty(cx, obj, lengthp);
}
/*
* 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.
*
*/
JS_PUBLIC_API bool js::StringIsArrayIndex(JSLinearString* str,
uint32_t* indexp) {
if (!str->isIndex(indexp)) {
return false;
}
MOZ_ASSERT(*indexp <= MAX_ARRAY_INDEX);
return true;
}
JS_PUBLIC_API bool js::StringIsArrayIndex(const char16_t* str, uint32_t length,
uint32_t* indexp) {
if (length == 0 || length > UINT32_CHAR_BUFFER_LENGTH) {
return false;
}
if (!mozilla::IsAsciiDigit(str[0])) {
return false;
}
if (!CheckStringIsIndex(str, length, indexp)) {
return false;
}
MOZ_ASSERT(*indexp <= MAX_ARRAY_INDEX);
return true;
}
template <typename T>
static bool ToId(JSContext* cx, T index, MutableHandleId id);
template <>
bool ToId(JSContext* cx, uint32_t index, MutableHandleId id) {
return IndexToId(cx, index, id);
}
template <>
bool ToId(JSContext* cx, uint64_t index, MutableHandleId id) {
MOZ_ASSERT(index < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));
if (index == uint32_t(index)) {
return IndexToId(cx, uint32_t(index), id);
}
Value tmp = DoubleValue(index);
return PrimitiveValueToId<CanGC>(cx, HandleValue::fromMarkedLocation(&tmp),
id);
}
/*
* If the property at the given index exists, get its value into |vp| and set
* |*hole| to false. Otherwise set |*hole| to true and |vp| to Undefined.
*/
template <typename T>
static bool HasAndGetElement(JSContext* cx, HandleObject obj,
HandleObject receiver, T index, bool* hole,
MutableHandleValue vp) {
if (obj->is<NativeObject>()) {
NativeObject* nobj = &obj->as<NativeObject>();
if (index < nobj->getDenseInitializedLength()) {
vp.set(nobj->getDenseElement(size_t(index)));
if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
*hole = false;
return true;
}
}
if (nobj->is<ArgumentsObject>() && index <= UINT32_MAX) {
if (nobj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
*hole = false;
return true;
}
}
}
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 T>
static inline bool HasAndGetElement(JSContext* cx, HandleObject obj, T index,
bool* hole, MutableHandleValue vp) {
return HasAndGetElement(cx, obj, obj, index, hole, vp);
}
bool ElementAdder::append(JSContext* cx, HandleValue v) {
MOZ_ASSERT(index_ < length_);
if (resObj_) {
NativeObject* resObj = &resObj_->as<NativeObject>();
DenseElementResult result =
resObj->setOrExtendDenseElements(cx, index_, v.address(), 1);
if (result == DenseElementResult::Failure) {
return false;
}
if (result == DenseElementResult::Incomplete) {
if (!DefineDataElement(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 (!HasAndGetElement(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;
}
static inline bool IsPackedArrayOrNoExtraIndexedProperties(JSObject* obj,
uint64_t length) {
return (IsPackedArray(obj) && obj->as<ArrayObject>().length() == length) ||
!ObjectMayHaveExtraIndexedProperties(obj);
}
static bool GetDenseElements(NativeObject* aobj, uint32_t length, Value* vp) {
MOZ_ASSERT(IsPackedArrayOrNoExtraIndexedProperties(aobj, length));
if (length > aobj->getDenseInitializedLength()) {
return false;
}
for (size_t i = 0; i < length; i++) {
vp[i] = aobj->getDenseElement(i);
// No other indexed properties so hole => undefined.
if (vp[i].isMagic(JS_ELEMENTS_HOLE)) {
vp[i] = UndefinedValue();
}
}
return true;
}
bool js::GetElements(JSContext* cx, HandleObject aobj, uint32_t length,
Value* vp) {
if (IsPackedArrayOrNoExtraIndexedProperties(aobj, length)) {
if (GetDenseElements(&aobj->as<NativeObject>(), length, vp)) {
return true;
}
}
if (aobj->is<ArgumentsObject>()) {
ArgumentsObject& argsobj = aobj->as<ArgumentsObject>();
if (!argsobj.hasOverriddenLength()) {
if (argsobj.maybeGetElements(0, length, vp)) {
return true;
}
}
}
if (aobj->is<TypedArrayObject>()) {
Handle<TypedArrayObject*> typedArray = aobj.as<TypedArrayObject>();
if (typedArray->length() == length) {
return TypedArrayObject::getElements(cx, typedArray, vp);
}
}
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;
}
static inline bool GetArrayElement(JSContext* cx, HandleObject obj,
uint64_t index, MutableHandleValue vp) {
if (obj->is<NativeObject>()) {
NativeObject* nobj = &obj->as<NativeObject>();
if (index < nobj->getDenseInitializedLength()) {
vp.set(nobj->getDenseElement(size_t(index)));
if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
return true;
}
}
if (nobj->is<ArgumentsObject>() && index <= UINT32_MAX) {
if (nobj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
return true;
}
}
}
RootedId id(cx);
if (!ToId(cx, index, &id)) {
return false;
}
return GetProperty(cx, obj, obj, id, vp);
}
static inline bool DefineArrayElement(JSContext* cx, HandleObject obj,
uint64_t index, HandleValue value) {
RootedId id(cx);
if (!ToId(cx, index, &id)) {
return false;
}
return DefineDataProperty(cx, obj, id, value);
}
// Set the value of the property at the given index to v.
static inline bool SetArrayElement(JSContext* cx, HandleObject obj,
uint64_t index, HandleValue v) {
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, uint64_t index,
ObjectOpResult& result) {
if (obj->is<ArrayObject>() && !obj->as<NativeObject>().isIndexed() &&
!obj->as<NativeObject>().denseElementsAreSealed()) {
ArrayObject* aobj = &obj->as<ArrayObject>();
if (index <= UINT32_MAX) {
uint32_t idx = uint32_t(index);
if (idx < aobj->getDenseInitializedLength()) {
if (idx + 1 == aobj->getDenseInitializedLength()) {
aobj->setDenseInitializedLengthMaybeNonExtensible(cx, idx);
} else {
aobj->setDenseElementHole(idx);
}
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,
uint64_t index) {
ObjectOpResult success;
if (!DeleteArrayElement(cx, obj, index, success)) {
return false;
}
if (!success) {
RootedId id(cx);
if (!ToId(cx, index, &id)) {
return false;
}
return success.reportError(cx, obj, id);
}
return true;
}
static bool DeletePropertiesOrThrow(JSContext* cx, HandleObject obj,
uint64_t len, uint64_t finalLength) {
if (obj->is<ArrayObject>() && !obj->as<NativeObject>().isIndexed() &&
!obj->as<NativeObject>().denseElementsAreSealed()) {
if (len <= UINT32_MAX) {
// Skip forward to the initialized elements of this array.
len = std::min(uint32_t(len),
obj->as<ArrayObject>().getDenseInitializedLength());
}
}
for (uint64_t k = len; k > finalLength; k--) {
if (!CheckForInterrupt(cx)) {
return false;
}
if (!DeletePropertyOrThrow(cx, obj, k - 1)) {
return false;
}
}
return true;
}
static bool SetArrayLengthProperty(JSContext* cx, Handle<ArrayObject*> obj,
HandleValue value) {
RootedId id(cx, NameToId(cx->names().length));
ObjectOpResult result;
if (obj->lengthIsWritable()) {
Rooted<PropertyDescriptor> desc(
cx, PropertyDescriptor::Data(value, JS::PropertyAttribute::Writable));
if (!ArraySetLength(cx, obj, id, desc, result)) {
return false;
}
} else {
MOZ_ALWAYS_TRUE(result.fail(JSMSG_READ_ONLY));
}
return result.checkStrict(cx, obj, id);
}
static bool SetLengthProperty(JSContext* cx, HandleObject obj,
uint64_t length) {
MOZ_ASSERT(length < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));
RootedValue v(cx, NumberValue(length));
if (obj->is<ArrayObject>()) {
return SetArrayLengthProperty(cx, obj.as<ArrayObject>(), v);
}
return SetProperty(cx, obj, cx->names().length, v);
}
bool js::SetLengthProperty(JSContext* cx, HandleObject obj, uint32_t length) {
RootedValue v(cx, NumberValue(length));
if (obj->is<ArrayObject>()) {
return SetArrayLengthProperty(cx, obj.as<ArrayObject>(), v);
}
return SetProperty(cx, obj, cx->names().length, v);
}
bool js::ArrayLengthGetter(JSContext* cx, HandleObject obj, HandleId id,
MutableHandleValue vp) {
MOZ_ASSERT(id == NameToId(cx->names().length));
vp.setNumber(obj->as<ArrayObject>().length());
return true;
}
bool js::ArrayLengthSetter(JSContext* cx, HandleObject obj, HandleId id,
HandleValue v, ObjectOpResult& result) {
MOZ_ASSERT(id == NameToId(cx->names().length));
Handle<ArrayObject*> arr = obj.as<ArrayObject>();
MOZ_ASSERT(arr->lengthIsWritable(),
"setter shouldn't be called if property is non-writable");
Rooted<PropertyDescriptor> desc(
cx, PropertyDescriptor::Data(v, JS::PropertyAttribute::Writable));
return ArraySetLength(cx, arr, id, desc, 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;
}
};
/* ES6 draft rev 34 (2015 Feb 20) 9.4.2.4 ArraySetLength */
bool js::ArraySetLength(JSContext* cx, Handle<ArrayObject*> arr, HandleId id,
Handle<PropertyDescriptor> desc,
ObjectOpResult& result) {
MOZ_ASSERT(id == NameToId(cx->names().length));
MOZ_ASSERT(desc.isDataDescriptor() || desc.isGenericDescriptor());
// Step 1.
uint32_t newLen;
if (!desc.hasValue()) {
// 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.
// Step 3.
if (!ToUint32(cx, desc.value(), &newLen)) {
return false;
}
// Step 4.
double d;
if (!ToNumber(cx, desc.value(), &d)) {
return false;
}
// Step 5.
if (d != newLen) {
JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
JSMSG_BAD_ARRAY_LENGTH);
return false;
}
// Steps 6-8 are irrelevant in our implementation.
}
// Steps 9-11.
bool lengthIsWritable = arr->lengthIsWritable();
#ifdef DEBUG
{
mozilla::Maybe<PropertyInfo> lengthProp = arr->lookupPure(id);
MOZ_ASSERT(lengthProp.isSome());
MOZ_ASSERT(lengthProp->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 ((desc.hasConfigurable() && desc.configurable()) ||
(desc.hasEnumerable() && desc.enumerable()) ||
(!lengthIsWritable && desc.hasWritable() && desc.writable())) {
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
// 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.
// This optimization is also invalid when there are sealed
// (non-configurable) elements.
if (!arr->isIndexed() && !arr->denseElementsMaybeInIteration() &&
!arr->denseElementsAreSealed()) {
uint32_t oldCapacity = arr->getDenseCapacity();
uint32_t oldInitializedLength = arr->getDenseInitializedLength();
MOZ_ASSERT(oldCapacity >= oldInitializedLength);
if (oldInitializedLength > newLen) {
arr->setDenseInitializedLengthMaybeNonExtensible(cx, newLen);
}
if (oldCapacity > newLen) {
if (arr->isExtensible()) {
arr->shrinkElements(cx, newLen);
} else {
MOZ_ASSERT(arr->getDenseInitializedLength() ==
arr->getDenseCapacity());
}
}
// 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
//
// This heuristic's kind of a huge guess -- "large number of
// elements" and "probably sparse" are completely unprincipled
// fix: store sparse elements in a sorted data structure that
// permits fast in-reverse-order traversal and concurrent removals.
Vector<uint32_t> indexes(cx);
{
RootedIdVector 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(newLen);
// Step 20.
if (desc.hasWritable() && !desc.writable()) {
Maybe<PropertyInfo> lengthProp = arr->lookup(cx, id);
MOZ_ASSERT(lengthProp.isSome());
MOZ_ASSERT(lengthProp->isCustomDataProperty());
PropertyFlags flags = lengthProp->flags();
flags.clearFlag(PropertyFlag::Writable);
if (!NativeObject::changeCustomDataPropAttributes(cx, arr, id, flags)) {
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 = std::min(header->initializedLength, newLen);
if (!arr->isExtensible()) {
arr->shrinkCapacityToInitializedLength(cx);
}
if (desc.hasWritable() && !desc.writable()) {
arr->setNonWritableLength(cx);
}
if (!succeeded) {
return result.fail(JSMSG_CANT_TRUNCATE_ARRAY);
}
return result.succeed();
}
static bool array_addProperty(JSContext* cx, HandleObject obj, HandleId id,
HandleValue v) {
ArrayObject* arr = &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(index + 1);
}
return true;
}
static SharedShape* AddLengthProperty(JSContext* cx,
Handle<SharedShape*> shape) {
// Add the 'length' property for a newly created array shape.
MOZ_ASSERT(shape->propMapLength() == 0);
MOZ_ASSERT(shape->getObjectClass() == &ArrayObject::class_);
RootedId lengthId(cx, NameToId(cx->names().length));
constexpr PropertyFlags flags = {PropertyFlag::CustomDataProperty,
PropertyFlag::Writable};
Rooted<SharedPropMap*> map(cx, shape->propMap());
uint32_t mapLength = shape->propMapLength();
ObjectFlags objectFlags = shape->objectFlags();
if (!SharedPropMap::addCustomDataProperty(cx, &ArrayObject::class_, &map,
&mapLength, lengthId, flags,
&objectFlags)) {
return nullptr;
}
return SharedShape::getPropMapShape(cx, shape->base(), shape->numFixedSlots(),
map, mapLength, objectFlags);
}
static bool IsArrayConstructor(const JSObject* obj) {
// Note: this also returns true for cross-realm Array constructors in the
// same compartment.
return IsNativeFunction(obj, ArrayConstructor);
}
static bool IsArrayConstructor(const Value& v) {
return v.isObject() && IsArrayConstructor(&v.toObject());
}
bool js::IsCrossRealmArrayConstructor(JSContext* cx, JSObject* obj,
bool* result) {
if (obj->is<WrapperObject>()) {
obj = CheckedUnwrapDynamic(obj, cx);
if (!obj) {
ReportAccessDenied(cx);
return false;
}
}
*result =
IsArrayConstructor(obj) && obj->as<JSFunction>().realm() != cx->realm();
return true;
}
static MOZ_ALWAYS_INLINE bool IsArraySpecies(JSContext* cx,
HandleObject origArray) {
if (MOZ_UNLIKELY(origArray->is<ProxyObject>())) {
if (origArray->getClass()->isDOMClass()) {
#ifdef DEBUG
// We assume DOM proxies never return true for IsArray.
IsArrayAnswer answer;
MOZ_ASSERT(Proxy::isArray(cx, origArray, &answer));
MOZ_ASSERT(answer == IsArrayAnswer::NotArray);
#endif
return true;
}
return false;
}
// 9.4.2.3 Step 4. Non-array objects always use the default constructor.
if (!origArray->is<ArrayObject>()) {
return true;
}
if (cx->realm()->arraySpeciesLookup.tryOptimizeArray(
cx, &origArray->as<ArrayObject>())) {
return true;
}
Value ctor;
if (!GetPropertyPure(cx, origArray, NameToId(cx->names().constructor),
&ctor)) {
return false;
}
if (!IsArrayConstructor(ctor)) {
return ctor.isUndefined();
}
// 9.4.2.3 Step 6.c. Use the current realm's constructor if |ctor| is a
// cross-realm Array constructor.
if (cx->realm() != ctor.toObject().as<JSFunction>().realm()) {
return true;
}
jsid speciesId = PropertyKey::Symbol(cx->wellKnownSymbols().species);
JSFunction* getter;
if (!GetGetterPure(cx, &ctor.toObject(), speciesId, &getter)) {
return false;
}
if (!getter) {
return false;
}
return IsSelfHostedFunctionWithName(getter, cx->names().dollar_ArraySpecies_);
}
static bool ArraySpeciesCreate(JSContext* cx, HandleObject origArray,
uint64_t length, MutableHandleObject arr) {
MOZ_ASSERT(length < DOUBLE_INTEGRAL_PRECISION_LIMIT);
FixedInvokeArgs<2> args(cx);
args[0].setObject(*origArray);
args[1].set(NumberValue(length));
RootedValue rval(cx);
if (!CallSelfHostedFunction(cx, cx->names().ArraySpeciesCreate,
UndefinedHandleValue, args, &rval)) {
return false;
}
MOZ_ASSERT(rval.isObject());
arr.set(&rval.toObject());
return true;
}
JSString* js::ArrayToSource(JSContext* cx, HandleObject obj) {
AutoCycleDetector detector(cx, obj);
if (!detector.init()) {
return nullptr;
}
JSStringBuilder sb(cx);
if (detector.foundCycle()) {
if (!sb.append("[]")) {
return nullptr;
}
return sb.finishString();
}
if (!sb.append('[')) {
return nullptr;
}
uint64_t length;
if (!GetLengthPropertyInlined(cx, obj, &length)) {
return nullptr;
}
RootedValue elt(cx);
for (uint64_t index = 0; index < length; index++) {
bool hole;
if (!CheckForInterrupt(cx) ||
!HasAndGetElement(cx, obj, index, &hole, &elt)) {
return nullptr;
}
/* Get element's character string. */
JSString* str;
if (hole) {
str = cx->runtime()->emptyString;
} else {
str = ValueToSource(cx, elt);
if (!str) {
return nullptr;
}
}
/* Append element to buffer. */
if (!sb.append(str)) {
return nullptr;
}
if (index + 1 != length) {
if (!sb.append(", ")) {
return nullptr;
}
} else if (hole) {
if (!sb.append(',')) {
return nullptr;
}
}
}
/* Finalize the buffer. */
if (!sb.append(']')) {
return nullptr;
}
return sb.finishString();
}
static bool array_toSource(JSContext* cx, unsigned argc, Value* vp) {
AutoJSMethodProfilerEntry pseudoFrame(cx, "Array.prototype", "toSource");
CallArgs args = CallArgsFromVp(argc, vp);
if (!args.thisv().isObject()) {
ReportIncompatible(cx, args);
return false;
}
Rooted<JSObject*> obj(cx, &args.thisv().toObject());
JSString* str = ArrayToSource(cx, obj);
if (!str) {
return false;
}
args.rval().setString(str);
return true;
}
template <typename SeparatorOp>
static bool ArrayJoinDenseKernel(JSContext* cx, SeparatorOp sepOp,
Handle<NativeObject*> obj, uint64_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);
uint64_t initLength =
std::min<uint64_t>(obj->getDenseInitializedLength(), length);
MOZ_ASSERT(initLength <= UINT32_MAX,
"initialized length shouldn't exceed UINT32_MAX");
uint32_t initLengthClamped = uint32_t(initLength);
while (*numProcessed < initLengthClamped) {
if (!CheckForInterrupt(cx)) {
return false;
}
// Step 7.b.
Value elem = obj->getDenseElement(*numProcessed);
// Steps 7.c-d.
if (elem.isString()) {
if (!sb.append(elem.toString())) {
return false;
}
} else if (elem.isNumber()) {
if (!NumberValueToStringBuffer(elem, sb)) {
return false;
}
} else if (elem.isBoolean()) {
if (!BooleanToStringBuffer(elem.toBoolean(), sb)) {
return false;
}
} 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 if (elem.isBigInt()) {
// ToString(bigint) doesn't access bigint.toString or
// anything like that, so it can't mutate the array we're
// walking through, so it *could* be handled here. We don't
// do so yet for reasons of initial-implementation economy.
break;
} else {
MOZ_ASSERT(elem.isMagic(JS_ELEMENTS_HOLE) || elem.isNullOrUndefined());
}
// Steps 7.a, 7.e.
if (++(*numProcessed) != length && !sepOp(sb)) {
return false;
}
}
return true;
}
template <typename SeparatorOp>
static bool ArrayJoinKernel(JSContext* cx, SeparatorOp sepOp, HandleObject obj,
uint64_t length, StringBuffer& sb) {
// Step 6.
uint32_t numProcessed = 0;
if (IsPackedArrayOrNoExtraIndexedProperties(obj, length)) {
if (!ArrayJoinDenseKernel<SeparatorOp>(cx, sepOp, obj.as<NativeObject>(),
length, sb, &numProcessed)) {
return false;
}
}
// Step 7.
if (numProcessed != length) {
RootedValue v(cx);
for (uint64_t i = numProcessed; i < length;) {
if (!CheckForInterrupt(cx)) {
return false;
}
// Step 7.b.
if (!GetArrayElement(cx, obj, i, &v)) {
return false;
}
// Steps 7.c-d.
if (!v.isNullOrUndefined()) {
if (!ValueToStringBuffer(cx, v, sb)) {
return false;
}
}
// Steps 7.a, 7.e.
if (++i != length && !sepOp(sb)) {
return false;
}
}
}
return true;
}
// ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
// 22.1.3.13 Array.prototype.join ( separator )
bool js::array_join(JSContext* cx, unsigned argc, Value* vp) {
AutoJSMethodProfilerEntry pseudoFrame(cx, "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;
}
// Step 2.
uint64_t length;
if (!GetLengthPropertyInlined(cx, obj, &length)) {
return false;
}
// Steps 3-4.
Rooted<JSLinearString*> 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_;
}
// Steps 5-8 (When the length is zero, directly return the empty string).
if (length == 0) {
args.rval().setString(cx->emptyString());
return true;
}
// An optimized version of a special case of steps 5-8: 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 && obj->is<NativeObject>()) {
NativeObject* nobj = &obj->as<NativeObject>();
if (nobj->getDenseInitializedLength() == 1) {
Value elem0 = nobj->getDenseElement(0);
if (elem0.isString()) {
args.rval().set(elem0);
return true;
}
}
}
// Step 5.
JSStringBuilder 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();
if (seplen > 0) {
if (length > UINT32_MAX) {
ReportAllocationOverflow(cx);
return false;
}
CheckedInt<uint32_t> res =
CheckedInt<uint32_t>(seplen) * (uint32_t(length) - 1);
if (!res.isValid()) {
ReportAllocationOverflow(cx);
return false;
}
if (!sb.reserve(res.value())) {
return false;
}
}
// Various optimized versions of steps 6-7.
if (seplen == 0) {
auto sepOp = [](StringBuffer&) { return true; };
if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
return false;
}
} else if (seplen == 1) {
char16_t c = sepstr->latin1OrTwoByteChar(0);
if (c <= JSString::MAX_LATIN1_CHAR) {
Latin1Char l1char = Latin1Char(c);
auto sepOp = [l1char](StringBuffer& sb) { return sb.append(l1char); };
if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
return false;
}
} else {
auto sepOp = [c](StringBuffer& sb) { return sb.append(c); };
if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
return false;
}
}
} else {
Handle<JSLinearString*> sepHandle = sepstr;
auto sepOp = [sepHandle](StringBuffer& sb) { return sb.append(sepHandle); };
if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
return false;
}
}
// Step 8.
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) {
AutoJSMethodProfilerEntry pseudoFrame(cx, "Array.prototype",
"toLocaleString");
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;
}
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 SetArrayElements(JSContext* cx, HandleObject obj, uint64_t start,
uint32_t count, const Value* vector) {
MOZ_ASSERT(count <= MAX_ARRAY_INDEX);
MOZ_ASSERT(start + count < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));
if (count == 0) {
return true;
}
if (!ObjectMayHaveExtraIndexedProperties(obj) && start <= UINT32_MAX) {
NativeObject* nobj = &obj->as<NativeObject>();
DenseElementResult result =
nobj->setOrExtendDenseElements(cx, uint32_t(start), vector, count);
if (result != DenseElementResult::Incomplete) {
return result == DenseElementResult::Success;
}
}
RootedId id(cx);
const Value* end = vector + count;
while (vector < end) {
if (!CheckForInterrupt(cx)) {
return false;
}
if (!ToId(cx, start++, &id)) {
return false;
}
if (!SetProperty(cx, obj, id, HandleValue::fromMarkedLocation(vector++))) {
return false;
}
}
return true;
}
static DenseElementResult ArrayReverseDenseKernel(JSContext* cx,
Handle<NativeObject*> obj,
uint32_t length) {
MOZ_ASSERT(length > 1);
// If there are no elements, we're done.
if (obj->getDenseInitializedLength() == 0) {
return DenseElementResult::Success;
}
if (!obj->isExtensible()) {
return DenseElementResult::Incomplete;
}
if (!IsPackedArray(obj)) {
/*
* 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->ensureDenseElements(cx, length, 0);
if (result != DenseElementResult::Success) {
return result;
}
/* Fill out the array's initialized length to its proper length. */
obj->ensureDenseInitializedLength(length, 0);
}
if (!obj->denseElementsMaybeInIteration() &&
!cx->zone()->needsIncrementalBarrier()) {
obj->reverseDenseElementsNoPreBarrier(length);
return DenseElementResult::Success;
}
auto setElementMaybeHole = [](JSContext* cx, Handle<NativeObject*> obj,
uint32_t index, const Value& val) {
if (MOZ_LIKELY(!val.isMagic(JS_ELEMENTS_HOLE))) {
obj->setDenseElement(index, val);
return true;
}
obj->setDenseElementHole(index);
return SuppressDeletedProperty(cx, obj, PropertyKey::Int(index));
};
RootedValue origlo(cx), orighi(cx);
uint32_t lo = 0, hi = length - 1;
for (; lo < hi; lo++, hi--) {
origlo = obj->getDenseElement(lo);
orighi = obj->getDenseElement(hi);
if (!setElementMaybeHole(cx, obj, lo, orighi)) {
return DenseElementResult::Failure;
}
if (!setElementMaybeHole(cx, obj, hi, origlo)) {
return DenseElementResult::Failure;
}
}
return DenseElementResult::Success;
}
// ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
// 22.1.3.21 Array.prototype.reverse ( )
static bool array_reverse(JSContext* cx, unsigned argc, Value* vp) {
AutoJSMethodProfilerEntry pseudoFrame(cx, "Array.prototype", "reverse");
CallArgs args = CallArgsFromVp(argc, vp);
// Step 1.
RootedObject obj(cx, ToObject(cx, args.thisv()));
if (!obj) {
return false;
}
// Step 2.
uint64_t len;
if (!GetLengthPropertyInlined(cx, obj, &len)) {
return false;
}
// An empty array or an array with length 1 is already reversed.
if (len <= 1) {
args.rval().setObject(*obj);
return true;
}
if (IsPackedArrayOrNoExtraIndexedProperties(obj, len) && len <= UINT32_MAX) {
DenseElementResult result =
ArrayReverseDenseKernel(cx, obj.as<NativeObject>(), uint32_t(len));
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;
}
}
// Steps 3-5.
RootedValue lowval(cx), hival(cx);
for (uint64_t i = 0, half = len / 2; i < half; i++) {
bool hole, hole2;