1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #include "builtin/Array-inl.h"
9 #include "mozilla/CheckedInt.h"
10 #include "mozilla/DebugOnly.h"
11 #include "mozilla/MathAlgorithms.h"
12 #include "mozilla/Maybe.h"
13 #include "mozilla/ScopeExit.h"
14 #include "mozilla/SIMD.h"
15 #include "mozilla/TextUtils.h"
21 #include "jsfriendapi.h"
25 #include "builtin/SelfHostingDefines.h"
27 #include "jit/InlinableNatives.h"
28 #include "jit/TrampolineNatives.h"
30 #include "js/Conversions.h"
31 #include "js/experimental/JitInfo.h" // JSJitGetterOp, JSJitInfo
32 #include "js/friend/ErrorMessages.h" // js::GetErrorMessage, JSMSG_*
33 #include "js/PropertySpec.h"
34 #include "util/Poison.h"
35 #include "util/StringBuffer.h"
36 #include "util/Text.h"
37 #include "vm/ArgumentsObject.h"
38 #include "vm/EqualityOperations.h"
39 #include "vm/Interpreter.h"
40 #include "vm/Iteration.h"
41 #include "vm/JSContext.h"
42 #include "vm/JSFunction.h"
43 #include "vm/JSObject.h"
44 #include "vm/PlainObject.h" // js::PlainObject
45 #include "vm/SelfHosting.h"
47 #include "vm/StringType.h"
48 #include "vm/ToSource.h" // js::ValueToSource
49 #include "vm/TypedArrayObject.h"
50 #include "vm/WrapperObject.h"
51 #ifdef ENABLE_RECORD_TUPLE
52 # include "vm/TupleType.h"
55 #include "builtin/Sorting-inl.h"
56 #include "vm/ArgumentsObject-inl.h"
57 #include "vm/ArrayObject-inl.h"
58 #include "vm/GeckoProfiler-inl.h"
59 #include "vm/IsGivenTypeObject-inl.h"
60 #include "vm/JSAtomUtils-inl.h" // PrimitiveValueToId, IndexToId
61 #include "vm/NativeObject-inl.h"
66 using mozilla::CeilingLog2
;
67 using mozilla::CheckedInt
;
68 using mozilla::DebugOnly
;
69 using mozilla::IsAsciiDigit
;
73 using JS::AutoCheckCannotGC
;
74 using JS::IsArrayAnswer
;
77 bool js::ObjectMayHaveExtraIndexedOwnProperties(JSObject
* obj
) {
78 if (!obj
->is
<NativeObject
>()) {
82 if (obj
->as
<NativeObject
>().isIndexed()) {
86 if (obj
->is
<TypedArrayObject
>()) {
90 return ClassMayResolveId(*obj
->runtimeFromAnyThread()->commonNames
,
91 obj
->getClass(), PropertyKey::Int(0), obj
);
94 bool js::PrototypeMayHaveIndexedProperties(NativeObject
* obj
) {
96 MOZ_ASSERT(obj
->hasStaticPrototype(),
97 "dynamic-prototype objects must be non-native");
99 JSObject
* proto
= obj
->staticPrototype();
101 return false; // no extra indexed properties found
104 if (ObjectMayHaveExtraIndexedOwnProperties(proto
)) {
107 obj
= &proto
->as
<NativeObject
>();
108 if (obj
->getDenseInitializedLength() != 0) {
115 * Whether obj may have indexed properties anywhere besides its dense
116 * elements. This includes other indexed properties in its shape hierarchy, and
117 * indexed properties or elements along its prototype chain.
119 bool js::ObjectMayHaveExtraIndexedProperties(JSObject
* obj
) {
120 MOZ_ASSERT_IF(obj
->hasDynamicPrototype(), !obj
->is
<NativeObject
>());
122 if (ObjectMayHaveExtraIndexedOwnProperties(obj
)) {
126 return PrototypeMayHaveIndexedProperties(&obj
->as
<NativeObject
>());
129 bool JS::IsArray(JSContext
* cx
, HandleObject obj
, IsArrayAnswer
* answer
) {
130 if (obj
->is
<ArrayObject
>()) {
131 *answer
= IsArrayAnswer::Array
;
135 if (obj
->is
<ProxyObject
>()) {
136 return Proxy::isArray(cx
, obj
, answer
);
139 *answer
= IsArrayAnswer::NotArray
;
143 bool JS::IsArray(JSContext
* cx
, HandleObject obj
, bool* isArray
) {
144 IsArrayAnswer answer
;
145 if (!IsArray(cx
, obj
, &answer
)) {
149 if (answer
== IsArrayAnswer::RevokedProxy
) {
150 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
151 JSMSG_PROXY_REVOKED
);
155 *isArray
= answer
== IsArrayAnswer::Array
;
159 bool js::IsArrayFromJit(JSContext
* cx
, HandleObject obj
, bool* isArray
) {
160 return JS::IsArray(cx
, obj
, isArray
);
163 // ES2017 7.1.15 ToLength.
164 bool js::ToLength(JSContext
* cx
, HandleValue v
, uint64_t* out
) {
166 int32_t i
= v
.toInt32();
167 *out
= i
< 0 ? 0 : i
;
175 if (!ToNumber(cx
, v
, &d
)) {
180 d
= JS::ToInteger(d
);
184 *out
= uint64_t(std::min(d
, DOUBLE_INTEGRAL_PRECISION_LIMIT
- 1));
189 bool js::GetLengthProperty(JSContext
* cx
, HandleObject obj
, uint64_t* lengthp
) {
190 if (obj
->is
<ArrayObject
>()) {
191 *lengthp
= obj
->as
<ArrayObject
>().length();
195 if (obj
->is
<ArgumentsObject
>()) {
196 ArgumentsObject
& argsobj
= obj
->as
<ArgumentsObject
>();
197 if (!argsobj
.hasOverriddenLength()) {
198 *lengthp
= argsobj
.initialLength();
203 RootedValue
value(cx
);
204 if (!GetProperty(cx
, obj
, obj
, cx
->names().length
, &value
)) {
208 return ToLength(cx
, value
, lengthp
);
211 // Fast path for array functions where the object is expected to be an array.
212 static MOZ_ALWAYS_INLINE
bool GetLengthPropertyInlined(JSContext
* cx
,
215 if (obj
->is
<ArrayObject
>()) {
216 *lengthp
= obj
->as
<ArrayObject
>().length();
220 return GetLengthProperty(cx
, obj
, lengthp
);
224 * Determine if the id represents an array index.
226 * An id is an array index according to ECMA by (15.4):
228 * "Array objects give special treatment to a certain class of property names.
229 * A property name P (in the form of a string value) is an array index if and
230 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
233 * This means the largest allowed index is actually 2^32-2 (4294967294).
235 * In our implementation, it would be sufficient to check for id.isInt32()
236 * except that by using signed 31-bit integers we miss the top half of the
237 * valid range. This function checks the string representation itself; note
238 * that calling a standard conversion routine might allow strings such as
239 * "08" or "4.0" as array indices, which they are not.
242 JS_PUBLIC_API
bool js::StringIsArrayIndex(const JSLinearString
* str
,
244 if (!str
->isIndex(indexp
)) {
247 MOZ_ASSERT(*indexp
<= MAX_ARRAY_INDEX
);
251 JS_PUBLIC_API
bool js::StringIsArrayIndex(const char16_t
* str
, uint32_t length
,
253 if (length
== 0 || length
> UINT32_CHAR_BUFFER_LENGTH
) {
256 if (!mozilla::IsAsciiDigit(str
[0])) {
259 if (!CheckStringIsIndex(str
, length
, indexp
)) {
262 MOZ_ASSERT(*indexp
<= MAX_ARRAY_INDEX
);
266 template <typename T
>
267 static bool ToId(JSContext
* cx
, T index
, MutableHandleId id
);
270 bool ToId(JSContext
* cx
, uint32_t index
, MutableHandleId id
) {
271 return IndexToId(cx
, index
, id
);
275 bool ToId(JSContext
* cx
, uint64_t index
, MutableHandleId id
) {
276 MOZ_ASSERT(index
< uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
));
278 if (index
== uint32_t(index
)) {
279 return IndexToId(cx
, uint32_t(index
), id
);
282 Value tmp
= DoubleValue(index
);
283 return PrimitiveValueToId
<CanGC
>(cx
, HandleValue::fromMarkedLocation(&tmp
),
288 * If the property at the given index exists, get its value into |vp| and set
289 * |*hole| to false. Otherwise set |*hole| to true and |vp| to Undefined.
291 template <typename T
>
292 static bool HasAndGetElement(JSContext
* cx
, HandleObject obj
,
293 HandleObject receiver
, T index
, bool* hole
,
294 MutableHandleValue vp
) {
295 if (obj
->is
<NativeObject
>()) {
296 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
297 if (index
< nobj
->getDenseInitializedLength()) {
298 vp
.set(nobj
->getDenseElement(size_t(index
)));
299 if (!vp
.isMagic(JS_ELEMENTS_HOLE
)) {
304 if (nobj
->is
<ArgumentsObject
>() && index
<= UINT32_MAX
) {
305 if (nobj
->as
<ArgumentsObject
>().maybeGetElement(uint32_t(index
), vp
)) {
313 if (!ToId(cx
, index
, &id
)) {
318 if (!HasProperty(cx
, obj
, id
, &found
)) {
323 if (!GetProperty(cx
, obj
, receiver
, id
, vp
)) {
333 template <typename T
>
334 static inline bool HasAndGetElement(JSContext
* cx
, HandleObject obj
, T index
,
335 bool* hole
, MutableHandleValue vp
) {
336 return HasAndGetElement(cx
, obj
, obj
, index
, hole
, vp
);
339 bool ElementAdder::append(JSContext
* cx
, HandleValue v
) {
340 MOZ_ASSERT(index_
< length_
);
342 NativeObject
* resObj
= &resObj_
->as
<NativeObject
>();
343 DenseElementResult result
=
344 resObj
->setOrExtendDenseElements(cx
, index_
, v
.address(), 1);
345 if (result
== DenseElementResult::Failure
) {
348 if (result
== DenseElementResult::Incomplete
) {
349 if (!DefineDataElement(cx
, resObj_
, index_
, v
)) {
360 void ElementAdder::appendHole() {
361 MOZ_ASSERT(getBehavior_
== ElementAdder::CheckHasElemPreserveHoles
);
362 MOZ_ASSERT(index_
< length_
);
364 vp_
[index_
].setMagic(JS_ELEMENTS_HOLE
);
369 bool js::GetElementsWithAdder(JSContext
* cx
, HandleObject obj
,
370 HandleObject receiver
, uint32_t begin
,
371 uint32_t end
, ElementAdder
* adder
) {
372 MOZ_ASSERT(begin
<= end
);
375 for (uint32_t i
= begin
; i
< end
; i
++) {
376 if (adder
->getBehavior() == ElementAdder::CheckHasElemPreserveHoles
) {
378 if (!HasAndGetElement(cx
, obj
, receiver
, i
, &hole
, &val
)) {
386 MOZ_ASSERT(adder
->getBehavior() == ElementAdder::GetElement
);
387 if (!GetElement(cx
, obj
, receiver
, i
, &val
)) {
391 if (!adder
->append(cx
, val
)) {
399 static inline bool IsPackedArrayOrNoExtraIndexedProperties(JSObject
* obj
,
401 return (IsPackedArray(obj
) && obj
->as
<ArrayObject
>().length() == length
) ||
402 !ObjectMayHaveExtraIndexedProperties(obj
);
405 static bool GetDenseElements(NativeObject
* aobj
, uint32_t length
, Value
* vp
) {
406 MOZ_ASSERT(IsPackedArrayOrNoExtraIndexedProperties(aobj
, length
));
408 if (length
> aobj
->getDenseInitializedLength()) {
412 for (size_t i
= 0; i
< length
; i
++) {
413 vp
[i
] = aobj
->getDenseElement(i
);
415 // No other indexed properties so hole => undefined.
416 if (vp
[i
].isMagic(JS_ELEMENTS_HOLE
)) {
417 vp
[i
] = UndefinedValue();
424 bool js::GetElements(JSContext
* cx
, HandleObject aobj
, uint32_t length
,
426 if (IsPackedArrayOrNoExtraIndexedProperties(aobj
, length
)) {
427 if (GetDenseElements(&aobj
->as
<NativeObject
>(), length
, vp
)) {
432 if (aobj
->is
<ArgumentsObject
>()) {
433 ArgumentsObject
& argsobj
= aobj
->as
<ArgumentsObject
>();
434 if (!argsobj
.hasOverriddenLength()) {
435 if (argsobj
.maybeGetElements(0, length
, vp
)) {
441 if (aobj
->is
<TypedArrayObject
>()) {
442 Handle
<TypedArrayObject
*> typedArray
= aobj
.as
<TypedArrayObject
>();
443 if (typedArray
->length().valueOr(0) == length
) {
444 return TypedArrayObject::getElements(cx
, typedArray
, length
, vp
);
448 if (js::GetElementsOp op
= aobj
->getOpsGetElements()) {
449 ElementAdder
adder(cx
, vp
, length
, ElementAdder::GetElement
);
450 return op(cx
, aobj
, 0, length
, &adder
);
453 for (uint32_t i
= 0; i
< length
; i
++) {
454 if (!GetElement(cx
, aobj
, aobj
, i
,
455 MutableHandleValue::fromMarkedLocation(&vp
[i
]))) {
463 static inline bool GetArrayElement(JSContext
* cx
, HandleObject obj
,
464 uint64_t index
, MutableHandleValue vp
) {
465 if (obj
->is
<NativeObject
>()) {
466 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
467 if (index
< nobj
->getDenseInitializedLength()) {
468 vp
.set(nobj
->getDenseElement(size_t(index
)));
469 if (!vp
.isMagic(JS_ELEMENTS_HOLE
)) {
474 if (nobj
->is
<ArgumentsObject
>() && index
<= UINT32_MAX
) {
475 if (nobj
->as
<ArgumentsObject
>().maybeGetElement(uint32_t(index
), vp
)) {
482 if (!ToId(cx
, index
, &id
)) {
485 return GetProperty(cx
, obj
, obj
, id
, vp
);
488 static inline bool DefineArrayElement(JSContext
* cx
, HandleObject obj
,
489 uint64_t index
, HandleValue value
) {
491 if (!ToId(cx
, index
, &id
)) {
494 return DefineDataProperty(cx
, obj
, id
, value
);
497 // Set the value of the property at the given index to v.
498 static inline bool SetArrayElement(JSContext
* cx
, HandleObject obj
,
499 uint64_t index
, HandleValue v
) {
501 if (!ToId(cx
, index
, &id
)) {
505 return SetProperty(cx
, obj
, id
, v
);
509 * Attempt to delete the element |index| from |obj| as if by
510 * |obj.[[Delete]](index)|.
512 * If an error occurs while attempting to delete the element (that is, the call
513 * to [[Delete]] threw), return false.
515 * Otherwise call result.succeed() or result.fail() to indicate whether the
516 * deletion attempt succeeded (that is, whether the call to [[Delete]] returned
517 * true or false). (Deletes generally fail only when the property is
518 * non-configurable, but proxies may implement different semantics.)
520 static bool DeleteArrayElement(JSContext
* cx
, HandleObject obj
, uint64_t index
,
521 ObjectOpResult
& result
) {
522 if (obj
->is
<ArrayObject
>() && !obj
->as
<NativeObject
>().isIndexed() &&
523 !obj
->as
<NativeObject
>().denseElementsAreSealed()) {
524 ArrayObject
* aobj
= &obj
->as
<ArrayObject
>();
525 if (index
<= UINT32_MAX
) {
526 uint32_t idx
= uint32_t(index
);
527 if (idx
< aobj
->getDenseInitializedLength()) {
528 if (idx
+ 1 == aobj
->getDenseInitializedLength()) {
529 aobj
->setDenseInitializedLengthMaybeNonExtensible(cx
, idx
);
531 aobj
->setDenseElementHole(idx
);
533 if (!SuppressDeletedElement(cx
, obj
, idx
)) {
539 return result
.succeed();
543 if (!ToId(cx
, index
, &id
)) {
546 return DeleteProperty(cx
, obj
, id
, result
);
549 /* ES6 draft rev 32 (2 Febr 2015) 7.3.7 */
550 static bool DeletePropertyOrThrow(JSContext
* cx
, HandleObject obj
,
552 ObjectOpResult success
;
553 if (!DeleteArrayElement(cx
, obj
, index
, success
)) {
558 if (!ToId(cx
, index
, &id
)) {
561 return success
.reportError(cx
, obj
, id
);
566 static bool DeletePropertiesOrThrow(JSContext
* cx
, HandleObject obj
,
567 uint64_t len
, uint64_t finalLength
) {
568 if (obj
->is
<ArrayObject
>() && !obj
->as
<NativeObject
>().isIndexed() &&
569 !obj
->as
<NativeObject
>().denseElementsAreSealed()) {
570 if (len
<= UINT32_MAX
) {
571 // Skip forward to the initialized elements of this array.
572 len
= std::min(uint32_t(len
),
573 obj
->as
<ArrayObject
>().getDenseInitializedLength());
577 for (uint64_t k
= len
; k
> finalLength
; k
--) {
578 if (!CheckForInterrupt(cx
)) {
582 if (!DeletePropertyOrThrow(cx
, obj
, k
- 1)) {
589 static bool SetArrayLengthProperty(JSContext
* cx
, Handle
<ArrayObject
*> obj
,
591 RootedId
id(cx
, NameToId(cx
->names().length
));
592 ObjectOpResult result
;
593 if (obj
->lengthIsWritable()) {
594 Rooted
<PropertyDescriptor
> desc(
595 cx
, PropertyDescriptor::Data(value
, JS::PropertyAttribute::Writable
));
596 if (!ArraySetLength(cx
, obj
, id
, desc
, result
)) {
600 MOZ_ALWAYS_TRUE(result
.fail(JSMSG_READ_ONLY
));
602 return result
.checkStrict(cx
, obj
, id
);
605 static bool SetLengthProperty(JSContext
* cx
, HandleObject obj
,
607 MOZ_ASSERT(length
< uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
));
609 RootedValue
v(cx
, NumberValue(length
));
610 if (obj
->is
<ArrayObject
>()) {
611 return SetArrayLengthProperty(cx
, obj
.as
<ArrayObject
>(), v
);
613 return SetProperty(cx
, obj
, cx
->names().length
, v
);
616 bool js::SetLengthProperty(JSContext
* cx
, HandleObject obj
, uint32_t length
) {
617 RootedValue
v(cx
, NumberValue(length
));
618 if (obj
->is
<ArrayObject
>()) {
619 return SetArrayLengthProperty(cx
, obj
.as
<ArrayObject
>(), v
);
621 return SetProperty(cx
, obj
, cx
->names().length
, v
);
624 bool js::ArrayLengthGetter(JSContext
* cx
, HandleObject obj
, HandleId id
,
625 MutableHandleValue vp
) {
626 MOZ_ASSERT(id
== NameToId(cx
->names().length
));
628 vp
.setNumber(obj
->as
<ArrayObject
>().length());
632 bool js::ArrayLengthSetter(JSContext
* cx
, HandleObject obj
, HandleId id
,
633 HandleValue v
, ObjectOpResult
& result
) {
634 MOZ_ASSERT(id
== NameToId(cx
->names().length
));
636 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
637 MOZ_ASSERT(arr
->lengthIsWritable(),
638 "setter shouldn't be called if property is non-writable");
640 Rooted
<PropertyDescriptor
> desc(
641 cx
, PropertyDescriptor::Data(v
, JS::PropertyAttribute::Writable
));
642 return ArraySetLength(cx
, arr
, id
, desc
, result
);
645 struct ReverseIndexComparator
{
646 bool operator()(const uint32_t& a
, const uint32_t& b
, bool* lessOrEqualp
) {
647 MOZ_ASSERT(a
!= b
, "how'd we get duplicate indexes?");
648 *lessOrEqualp
= b
<= a
;
653 /* ES6 draft rev 34 (2015 Feb 20) 9.4.2.4 ArraySetLength */
654 bool js::ArraySetLength(JSContext
* cx
, Handle
<ArrayObject
*> arr
, HandleId id
,
655 Handle
<PropertyDescriptor
> desc
,
656 ObjectOpResult
& result
) {
657 MOZ_ASSERT(id
== NameToId(cx
->names().length
));
658 MOZ_ASSERT(desc
.isDataDescriptor() || desc
.isGenericDescriptor());
662 if (!desc
.hasValue()) {
663 // The spec has us calling OrdinaryDefineOwnProperty if
664 // Desc.[[Value]] is absent, but our implementation is so different that
665 // this is impossible. Instead, set newLen to the current length and
666 // proceed to step 9.
667 newLen
= arr
->length();
669 // Step 2 is irrelevant in our implementation.
672 if (!ToUint32(cx
, desc
.value(), &newLen
)) {
678 if (!ToNumber(cx
, desc
.value(), &d
)) {
684 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
685 JSMSG_BAD_ARRAY_LENGTH
);
689 // Steps 6-8 are irrelevant in our implementation.
693 bool lengthIsWritable
= arr
->lengthIsWritable();
696 mozilla::Maybe
<PropertyInfo
> lengthProp
= arr
->lookupPure(id
);
697 MOZ_ASSERT(lengthProp
.isSome());
698 MOZ_ASSERT(lengthProp
->writable() == lengthIsWritable
);
701 uint32_t oldLen
= arr
->length();
703 // Part of steps 1.a, 12.a, and 16: Fail if we're being asked to change
704 // enumerability or configurability, or otherwise break the object
705 // invariants. (ES6 checks these by calling OrdinaryDefineOwnProperty, but
706 // in SM, the array length property is hardly ordinary.)
707 if ((desc
.hasConfigurable() && desc
.configurable()) ||
708 (desc
.hasEnumerable() && desc
.enumerable()) ||
709 (!lengthIsWritable
&& desc
.hasWritable() && desc
.writable())) {
710 return result
.fail(JSMSG_CANT_REDEFINE_PROP
);
713 // Steps 12-13 for arrays with non-writable length.
714 if (!lengthIsWritable
) {
715 if (newLen
== oldLen
) {
716 return result
.succeed();
719 return result
.fail(JSMSG_CANT_REDEFINE_ARRAY_LENGTH
);
723 bool succeeded
= true;
725 // The initialized length and capacity of an array only need updating
726 // when non-hole elements are added or removed, which doesn't happen
727 // when array length stays the same or increases.
728 if (newLen
>= oldLen
) {
732 // Attempt to propagate dense-element optimization tricks, if possible,
733 // and avoid the generic (and accordingly slow) deletion code below.
734 // We can only do this if there are only densely-indexed elements.
735 // Once there's a sparse indexed element, there's no good way to know,
736 // save by enumerating all the properties to find it. But we *have* to
737 // know in case that sparse indexed element is non-configurable, as
738 // that element must prevent any deletions below it. Bug 586842 should
739 // fix this inefficiency by moving indexed storage to be entirely
740 // separate from non-indexed storage.
741 // A second reason for this optimization to be invalid is an active
742 // for..in iteration over the array. Keys deleted before being reached
743 // during the iteration must not be visited, and suppressing them here
744 // would be too costly.
745 // This optimization is also invalid when there are sealed
746 // (non-configurable) elements.
747 if (!arr
->isIndexed() && !arr
->denseElementsMaybeInIteration() &&
748 !arr
->denseElementsAreSealed()) {
749 uint32_t oldCapacity
= arr
->getDenseCapacity();
750 uint32_t oldInitializedLength
= arr
->getDenseInitializedLength();
751 MOZ_ASSERT(oldCapacity
>= oldInitializedLength
);
752 if (oldInitializedLength
> newLen
) {
753 arr
->setDenseInitializedLengthMaybeNonExtensible(cx
, newLen
);
755 if (oldCapacity
> newLen
) {
756 if (arr
->isExtensible()) {
757 arr
->shrinkElements(cx
, newLen
);
759 MOZ_ASSERT(arr
->getDenseInitializedLength() ==
760 arr
->getDenseCapacity());
764 // We've done the work of deleting any dense elements needing
765 // deletion, and there are no sparse elements. Thus we can skip
766 // straight to defining the length.
772 // Attempt to delete all elements above the new length, from greatest
773 // to least. If any of these deletions fails, we're supposed to define
774 // the length to one greater than the index that couldn't be deleted,
775 // *with the property attributes specified*. This might convert the
776 // length to be not the value specified, yet non-writable. (You may be
777 // forgiven for thinking these are interesting semantics.) Example:
780 // Object.defineProperty([0, 1, 2, 3], 1, { writable: false });
781 // Object.defineProperty(arr, "length",
782 // { value: 0, writable: false });
784 // will convert |arr| to an array of non-writable length two, then
785 // throw a TypeError.
787 // We implement this behavior, in the relevant lops below, by setting
788 // |succeeded| to false. Then we exit the loop, define the length
789 // appropriately, and only then throw a TypeError, if necessary.
790 uint32_t gap
= oldLen
- newLen
;
791 const uint32_t RemoveElementsFastLimit
= 1 << 24;
792 if (gap
< RemoveElementsFastLimit
) {
793 // If we're removing a relatively small number of elements, just do
794 // it exactly by the spec.
795 while (newLen
< oldLen
) {
800 ObjectOpResult deleteSucceeded
;
801 if (!DeleteElement(cx
, arr
, oldLen
, deleteSucceeded
)) {
804 if (!deleteSucceeded
) {
811 // If we're removing a large number of elements from an array
812 // that's probably sparse, try a different tack. Get all the own
813 // property names, sift out the indexes in the deletion range into
814 // a vector, sort the vector greatest to least, then delete the
815 // indexes greatest to least using that vector. See bug 322135.
817 // This heuristic's kind of a huge guess -- "large number of
818 // elements" and "probably sparse" are completely unprincipled
819 // predictions. In the long run, bug 586842 will support the right
820 // fix: store sparse elements in a sorted data structure that
821 // permits fast in-reverse-order traversal and concurrent removals.
823 Vector
<uint32_t> indexes(cx
);
825 RootedIdVector
props(cx
);
826 if (!GetPropertyKeys(cx
, arr
, JSITER_OWNONLY
| JSITER_HIDDEN
, &props
)) {
830 for (size_t i
= 0; i
< props
.length(); i
++) {
831 if (!CheckForInterrupt(cx
)) {
836 if (!IdIsIndex(props
[i
], &index
)) {
840 if (index
>= newLen
&& index
< oldLen
) {
841 if (!indexes
.append(index
)) {
848 uint32_t count
= indexes
.length();
850 // We should use radix sort to be O(n), but this is uncommon
851 // enough that we'll punt til someone complains.
852 Vector
<uint32_t> scratch(cx
);
853 if (!scratch
.resize(count
)) {
856 MOZ_ALWAYS_TRUE(MergeSort(indexes
.begin(), count
, scratch
.begin(),
857 ReverseIndexComparator()));
860 uint32_t index
= UINT32_MAX
;
861 for (uint32_t i
= 0; i
< count
; i
++) {
862 MOZ_ASSERT(indexes
[i
] < index
, "indexes should never repeat");
866 ObjectOpResult deleteSucceeded
;
867 if (!DeleteElement(cx
, arr
, index
, deleteSucceeded
)) {
870 if (!deleteSucceeded
) {
879 // Update array length. Technically we should have been doing this
880 // throughout the loop, in step 19.d.iii.
881 arr
->setLength(newLen
);
884 if (desc
.hasWritable() && !desc
.writable()) {
885 Maybe
<PropertyInfo
> lengthProp
= arr
->lookup(cx
, id
);
886 MOZ_ASSERT(lengthProp
.isSome());
887 MOZ_ASSERT(lengthProp
->isCustomDataProperty());
888 PropertyFlags flags
= lengthProp
->flags();
889 flags
.clearFlag(PropertyFlag::Writable
);
890 if (!NativeObject::changeCustomDataPropAttributes(cx
, arr
, id
, flags
)) {
895 // All operations past here until the |!succeeded| code must be infallible,
896 // so that all element fields remain properly synchronized.
898 // Trim the initialized length, if needed, to preserve the <= length
899 // invariant. (Capacity was already reduced during element deletion, if
901 ObjectElements
* header
= arr
->getElementsHeader();
902 header
->initializedLength
= std::min(header
->initializedLength
, newLen
);
904 if (!arr
->isExtensible()) {
905 arr
->shrinkCapacityToInitializedLength(cx
);
908 if (desc
.hasWritable() && !desc
.writable()) {
909 arr
->setNonWritableLength(cx
);
913 return result
.fail(JSMSG_CANT_TRUNCATE_ARRAY
);
916 return result
.succeed();
919 static bool array_addProperty(JSContext
* cx
, HandleObject obj
, HandleId id
,
921 ArrayObject
* arr
= &obj
->as
<ArrayObject
>();
924 if (!IdIsIndex(id
, &index
)) {
928 uint32_t length
= arr
->length();
929 if (index
>= length
) {
930 MOZ_ASSERT(arr
->lengthIsWritable(),
931 "how'd this element get added if length is non-writable?");
932 arr
->setLength(index
+ 1);
937 static SharedShape
* AddLengthProperty(JSContext
* cx
,
938 Handle
<SharedShape
*> shape
) {
939 // Add the 'length' property for a newly created array shape.
941 MOZ_ASSERT(shape
->propMapLength() == 0);
942 MOZ_ASSERT(shape
->getObjectClass() == &ArrayObject::class_
);
944 RootedId
lengthId(cx
, NameToId(cx
->names().length
));
945 constexpr PropertyFlags flags
= {PropertyFlag::CustomDataProperty
,
946 PropertyFlag::Writable
};
948 Rooted
<SharedPropMap
*> map(cx
, shape
->propMap());
949 uint32_t mapLength
= shape
->propMapLength();
950 ObjectFlags objectFlags
= shape
->objectFlags();
952 if (!SharedPropMap::addCustomDataProperty(cx
, &ArrayObject::class_
, &map
,
953 &mapLength
, lengthId
, flags
,
958 return SharedShape::getPropMapShape(cx
, shape
->base(), shape
->numFixedSlots(),
959 map
, mapLength
, objectFlags
);
962 bool js::IsArrayConstructor(const JSObject
* obj
) {
963 // Note: this also returns true for cross-realm Array constructors in the
965 return IsNativeFunction(obj
, ArrayConstructor
);
968 static bool IsArrayConstructor(const Value
& v
) {
969 return v
.isObject() && IsArrayConstructor(&v
.toObject());
972 bool js::IsCrossRealmArrayConstructor(JSContext
* cx
, JSObject
* obj
,
974 if (obj
->is
<WrapperObject
>()) {
975 obj
= CheckedUnwrapDynamic(obj
, cx
);
977 ReportAccessDenied(cx
);
983 IsArrayConstructor(obj
) && obj
->as
<JSFunction
>().realm() != cx
->realm();
987 // Returns true iff we know for -sure- that it is definitely safe to use the
988 // realm's array constructor.
990 // This function is conservative as it may return false for cases which
991 // ultimately do use the array constructor.
992 static MOZ_ALWAYS_INLINE
bool IsArraySpecies(JSContext
* cx
,
993 HandleObject origArray
) {
994 if (MOZ_UNLIKELY(origArray
->is
<ProxyObject
>())) {
995 if (origArray
->getClass()->isDOMClass()) {
997 // We assume DOM proxies never return true for IsArray.
998 IsArrayAnswer answer
;
999 MOZ_ASSERT(Proxy::isArray(cx
, origArray
, &answer
));
1000 MOZ_ASSERT(answer
== IsArrayAnswer::NotArray
);
1007 // 9.4.2.3 Step 4. Non-array objects always use the default constructor.
1008 if (!origArray
->is
<ArrayObject
>()) {
1012 if (cx
->realm()->arraySpeciesLookup
.tryOptimizeArray(
1013 cx
, &origArray
->as
<ArrayObject
>())) {
1018 if (!GetPropertyPure(cx
, origArray
, NameToId(cx
->names().constructor
),
1023 if (!IsArrayConstructor(ctor
)) {
1024 return ctor
.isUndefined();
1027 // 9.4.2.3 Step 6.c. Use the current realm's constructor if |ctor| is a
1028 // cross-realm Array constructor.
1029 if (cx
->realm() != ctor
.toObject().as
<JSFunction
>().realm()) {
1033 jsid speciesId
= PropertyKey::Symbol(cx
->wellKnownSymbols().species
);
1035 if (!GetGetterPure(cx
, &ctor
.toObject(), speciesId
, &getter
)) {
1043 return IsSelfHostedFunctionWithName(getter
, cx
->names().dollar_ArraySpecies_
);
1046 static bool ArraySpeciesCreate(JSContext
* cx
, HandleObject origArray
,
1047 uint64_t length
, MutableHandleObject arr
) {
1048 MOZ_ASSERT(length
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
1050 FixedInvokeArgs
<2> args(cx
);
1052 args
[0].setObject(*origArray
);
1053 args
[1].set(NumberValue(length
));
1055 RootedValue
rval(cx
);
1056 if (!CallSelfHostedFunction(cx
, cx
->names().ArraySpeciesCreate
,
1057 UndefinedHandleValue
, args
, &rval
)) {
1061 MOZ_ASSERT(rval
.isObject());
1062 arr
.set(&rval
.toObject());
1066 JSString
* js::ArrayToSource(JSContext
* cx
, HandleObject obj
) {
1067 AutoCycleDetector
detector(cx
, obj
);
1068 if (!detector
.init()) {
1072 JSStringBuilder
sb(cx
);
1074 if (detector
.foundCycle()) {
1075 if (!sb
.append("[]")) {
1078 return sb
.finishString();
1081 if (!sb
.append('[')) {
1086 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
1090 RootedValue
elt(cx
);
1091 for (uint64_t index
= 0; index
< length
; index
++) {
1093 if (!CheckForInterrupt(cx
) ||
1094 !HasAndGetElement(cx
, obj
, index
, &hole
, &elt
)) {
1098 /* Get element's character string. */
1101 str
= cx
->runtime()->emptyString
;
1103 str
= ValueToSource(cx
, elt
);
1109 /* Append element to buffer. */
1110 if (!sb
.append(str
)) {
1113 if (index
+ 1 != length
) {
1114 if (!sb
.append(", ")) {
1118 if (!sb
.append(',')) {
1124 /* Finalize the buffer. */
1125 if (!sb
.append(']')) {
1129 return sb
.finishString();
1132 static bool array_toSource(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1133 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "toSource");
1134 CallArgs args
= CallArgsFromVp(argc
, vp
);
1136 if (!args
.thisv().isObject()) {
1137 ReportIncompatible(cx
, args
);
1141 Rooted
<JSObject
*> obj(cx
, &args
.thisv().toObject());
1143 JSString
* str
= ArrayToSource(cx
, obj
);
1148 args
.rval().setString(str
);
1152 template <typename SeparatorOp
>
1153 static bool ArrayJoinDenseKernel(JSContext
* cx
, SeparatorOp sepOp
,
1154 Handle
<NativeObject
*> obj
, uint64_t length
,
1155 StringBuffer
& sb
, uint32_t* numProcessed
) {
1156 // This loop handles all elements up to initializedLength. If
1157 // length > initLength we rely on the second loop to add the
1159 MOZ_ASSERT(*numProcessed
== 0);
1160 uint64_t initLength
=
1161 std::min
<uint64_t>(obj
->getDenseInitializedLength(), length
);
1162 MOZ_ASSERT(initLength
<= UINT32_MAX
,
1163 "initialized length shouldn't exceed UINT32_MAX");
1164 uint32_t initLengthClamped
= uint32_t(initLength
);
1165 while (*numProcessed
< initLengthClamped
) {
1166 if (!CheckForInterrupt(cx
)) {
1171 Value elem
= obj
->getDenseElement(*numProcessed
);
1174 if (elem
.isString()) {
1175 if (!sb
.append(elem
.toString())) {
1178 } else if (elem
.isNumber()) {
1179 if (!NumberValueToStringBuffer(elem
, sb
)) {
1182 } else if (elem
.isBoolean()) {
1183 if (!BooleanToStringBuffer(elem
.toBoolean(), sb
)) {
1186 } else if (elem
.isObject() || elem
.isSymbol()) {
1188 * Object stringifying could modify the initialized length or make
1189 * the array sparse. Delegate it to a separate loop to keep this
1192 * Symbol stringifying is a TypeError, so into the slow path
1193 * with those as well.
1196 } else if (elem
.isBigInt()) {
1197 // ToString(bigint) doesn't access bigint.toString or
1198 // anything like that, so it can't mutate the array we're
1199 // walking through, so it *could* be handled here. We don't
1200 // do so yet for reasons of initial-implementation economy.
1203 MOZ_ASSERT(elem
.isMagic(JS_ELEMENTS_HOLE
) || elem
.isNullOrUndefined());
1207 if (++(*numProcessed
) != length
&& !sepOp(sb
)) {
1215 template <typename SeparatorOp
>
1216 static bool ArrayJoinKernel(JSContext
* cx
, SeparatorOp sepOp
, HandleObject obj
,
1217 uint64_t length
, StringBuffer
& sb
) {
1219 uint32_t numProcessed
= 0;
1221 if (IsPackedArrayOrNoExtraIndexedProperties(obj
, length
)) {
1222 if (!ArrayJoinDenseKernel
<SeparatorOp
>(cx
, sepOp
, obj
.as
<NativeObject
>(),
1223 length
, sb
, &numProcessed
)) {
1229 if (numProcessed
!= length
) {
1231 for (uint64_t i
= numProcessed
; i
< length
;) {
1232 if (!CheckForInterrupt(cx
)) {
1237 if (!GetArrayElement(cx
, obj
, i
, &v
)) {
1242 if (!v
.isNullOrUndefined()) {
1243 if (!ValueToStringBuffer(cx
, v
, sb
)) {
1249 if (++i
!= length
&& !sepOp(sb
)) {
1258 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
1259 // 22.1.3.13 Array.prototype.join ( separator )
1260 bool js::array_join(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1261 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "join");
1262 CallArgs args
= CallArgsFromVp(argc
, vp
);
1265 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
1270 AutoCycleDetector
detector(cx
, obj
);
1271 if (!detector
.init()) {
1275 if (detector
.foundCycle()) {
1276 args
.rval().setString(cx
->names().empty_
);
1282 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
1287 Rooted
<JSLinearString
*> sepstr(cx
);
1288 if (args
.hasDefined(0)) {
1289 JSString
* s
= ToString
<CanGC
>(cx
, args
[0]);
1293 sepstr
= s
->ensureLinear(cx
);
1298 sepstr
= cx
->names().comma_
;
1301 // Steps 5-8 (When the length is zero, directly return the empty string).
1303 args
.rval().setString(cx
->emptyString());
1307 // An optimized version of a special case of steps 5-8: when length==1 and
1308 // the 0th element is a string, ToString() of that element is a no-op and
1309 // so it can be immediately returned as the result.
1310 if (length
== 1 && obj
->is
<NativeObject
>()) {
1311 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
1312 if (nobj
->getDenseInitializedLength() == 1) {
1313 Value elem0
= nobj
->getDenseElement(0);
1314 if (elem0
.isString()) {
1315 args
.rval().set(elem0
);
1322 JSStringBuilder
sb(cx
);
1323 if (sepstr
->hasTwoByteChars() && !sb
.ensureTwoByteChars()) {
1327 // The separator will be added |length - 1| times, reserve space for that
1328 // so that we don't have to unnecessarily grow the buffer.
1329 size_t seplen
= sepstr
->length();
1331 if (length
> UINT32_MAX
) {
1332 ReportAllocationOverflow(cx
);
1335 CheckedInt
<uint32_t> res
=
1336 CheckedInt
<uint32_t>(seplen
) * (uint32_t(length
) - 1);
1337 if (!res
.isValid()) {
1338 ReportAllocationOverflow(cx
);
1342 if (!sb
.reserve(res
.value())) {
1347 // Various optimized versions of steps 6-7.
1349 auto sepOp
= [](StringBuffer
&) { return true; };
1350 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1353 } else if (seplen
== 1) {
1354 char16_t c
= sepstr
->latin1OrTwoByteChar(0);
1355 if (c
<= JSString::MAX_LATIN1_CHAR
) {
1356 Latin1Char l1char
= Latin1Char(c
);
1357 auto sepOp
= [l1char
](StringBuffer
& sb
) { return sb
.append(l1char
); };
1358 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1362 auto sepOp
= [c
](StringBuffer
& sb
) { return sb
.append(c
); };
1363 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1368 Handle
<JSLinearString
*> sepHandle
= sepstr
;
1369 auto sepOp
= [sepHandle
](StringBuffer
& sb
) { return sb
.append(sepHandle
); };
1370 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1376 JSString
* str
= sb
.finishString();
1381 args
.rval().setString(str
);
1385 // ES2017 draft rev f8a9be8ea4bd97237d176907a1e3080dce20c68f
1386 // 22.1.3.27 Array.prototype.toLocaleString ([ reserved1 [ , reserved2 ] ])
1387 // ES2017 Intl draft rev 78bbe7d1095f5ff3760ac4017ed366026e4cb276
1388 // 13.4.1 Array.prototype.toLocaleString ([ locales [ , options ]])
1389 static bool array_toLocaleString(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1390 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype",
1393 CallArgs args
= CallArgsFromVp(argc
, vp
);
1396 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
1401 // Avoid calling into self-hosted code if the array is empty.
1402 if (obj
->is
<ArrayObject
>() && obj
->as
<ArrayObject
>().length() == 0) {
1403 args
.rval().setString(cx
->names().empty_
);
1407 AutoCycleDetector
detector(cx
, obj
);
1408 if (!detector
.init()) {
1412 if (detector
.foundCycle()) {
1413 args
.rval().setString(cx
->names().empty_
);
1417 FixedInvokeArgs
<2> args2(cx
);
1419 args2
[0].set(args
.get(0));
1420 args2
[1].set(args
.get(1));
1423 RootedValue
thisv(cx
, ObjectValue(*obj
));
1424 return CallSelfHostedFunction(cx
, cx
->names().ArrayToLocaleString
, thisv
,
1425 args2
, args
.rval());
1428 /* vector must point to rooted memory. */
1429 static bool SetArrayElements(JSContext
* cx
, HandleObject obj
, uint64_t start
,
1430 uint32_t count
, const Value
* vector
) {
1431 MOZ_ASSERT(count
<= MAX_ARRAY_INDEX
);
1432 MOZ_ASSERT(start
+ count
< uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
));
1438 if (!ObjectMayHaveExtraIndexedProperties(obj
) && start
<= UINT32_MAX
) {
1439 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
1440 DenseElementResult result
=
1441 nobj
->setOrExtendDenseElements(cx
, uint32_t(start
), vector
, count
);
1442 if (result
!= DenseElementResult::Incomplete
) {
1443 return result
== DenseElementResult::Success
;
1448 const Value
* end
= vector
+ count
;
1449 while (vector
< end
) {
1450 if (!CheckForInterrupt(cx
)) {
1454 if (!ToId(cx
, start
++, &id
)) {
1458 if (!SetProperty(cx
, obj
, id
, HandleValue::fromMarkedLocation(vector
++))) {
1466 static DenseElementResult
ArrayReverseDenseKernel(JSContext
* cx
,
1467 Handle
<NativeObject
*> obj
,
1469 MOZ_ASSERT(length
> 1);
1471 // If there are no elements, we're done.
1472 if (obj
->getDenseInitializedLength() == 0) {
1473 return DenseElementResult::Success
;
1476 if (!obj
->isExtensible()) {
1477 return DenseElementResult::Incomplete
;
1480 if (!IsPackedArray(obj
)) {
1482 * It's actually surprisingly complicated to reverse an array due
1483 * to the orthogonality of array length and array capacity while
1484 * handling leading and trailing holes correctly. Reversing seems
1485 * less likely to be a common operation than other array
1486 * mass-mutation methods, so for now just take a probably-small
1487 * memory hit (in the absence of too many holes in the array at
1488 * its start) and ensure that the capacity is sufficient to hold
1489 * all the elements in the array if it were full.
1491 DenseElementResult result
= obj
->ensureDenseElements(cx
, length
, 0);
1492 if (result
!= DenseElementResult::Success
) {
1496 /* Fill out the array's initialized length to its proper length. */
1497 obj
->ensureDenseInitializedLength(length
, 0);
1500 if (!obj
->denseElementsMaybeInIteration() &&
1501 !cx
->zone()->needsIncrementalBarrier()) {
1502 obj
->reverseDenseElementsNoPreBarrier(length
);
1503 return DenseElementResult::Success
;
1506 auto setElementMaybeHole
= [](JSContext
* cx
, Handle
<NativeObject
*> obj
,
1507 uint32_t index
, const Value
& val
) {
1508 if (MOZ_LIKELY(!val
.isMagic(JS_ELEMENTS_HOLE
))) {
1509 obj
->setDenseElement(index
, val
);
1513 obj
->setDenseElementHole(index
);
1514 return SuppressDeletedProperty(cx
, obj
, PropertyKey::Int(index
));
1517 RootedValue
origlo(cx
), orighi(cx
);
1519 uint32_t lo
= 0, hi
= length
- 1;
1520 for (; lo
< hi
; lo
++, hi
--) {
1521 origlo
= obj
->getDenseElement(lo
);
1522 orighi
= obj
->getDenseElement(hi
);
1523 if (!setElementMaybeHole(cx
, obj
, lo
, orighi
)) {
1524 return DenseElementResult::Failure
;
1526 if (!setElementMaybeHole(cx
, obj
, hi
, origlo
)) {
1527 return DenseElementResult::Failure
;
1531 return DenseElementResult::Success
;
1534 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
1535 // 22.1.3.21 Array.prototype.reverse ( )
1536 static bool array_reverse(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1537 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "reverse");
1538 CallArgs args
= CallArgsFromVp(argc
, vp
);
1541 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
1548 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
1552 // An empty array or an array with length 1 is already reversed.
1554 args
.rval().setObject(*obj
);
1558 if (IsPackedArrayOrNoExtraIndexedProperties(obj
, len
) && len
<= UINT32_MAX
) {
1559 DenseElementResult result
=
1560 ArrayReverseDenseKernel(cx
, obj
.as
<NativeObject
>(), uint32_t(len
));
1561 if (result
!= DenseElementResult::Incomplete
) {
1563 * Per ECMA-262, don't update the length of the array, even if the new
1564 * array has trailing holes (and thus the original array began with
1567 args
.rval().setObject(*obj
);
1568 return result
== DenseElementResult::Success
;
1573 RootedValue
lowval(cx
), hival(cx
);
1574 for (uint64_t i
= 0, half
= len
/ 2; i
< half
; i
++) {
1576 if (!CheckForInterrupt(cx
) ||
1577 !HasAndGetElement(cx
, obj
, i
, &hole
, &lowval
) ||
1578 !HasAndGetElement(cx
, obj
, len
- i
- 1, &hole2
, &hival
)) {
1582 if (!hole
&& !hole2
) {
1583 if (!SetArrayElement(cx
, obj
, i
, hival
)) {
1586 if (!SetArrayElement(cx
, obj
, len
- i
- 1, lowval
)) {
1589 } else if (hole
&& !hole2
) {
1590 if (!SetArrayElement(cx
, obj
, i
, hival
)) {
1593 if (!DeletePropertyOrThrow(cx
, obj
, len
- i
- 1)) {
1596 } else if (!hole
&& hole2
) {
1597 if (!DeletePropertyOrThrow(cx
, obj
, i
)) {
1600 if (!SetArrayElement(cx
, obj
, len
- i
- 1, lowval
)) {
1604 // No action required.
1609 args
.rval().setObject(*obj
);
1613 static inline bool CompareStringValues(JSContext
* cx
, const Value
& a
,
1614 const Value
& b
, bool* lessOrEqualp
) {
1615 if (!CheckForInterrupt(cx
)) {
1619 JSString
* astr
= a
.toString();
1620 JSString
* bstr
= b
.toString();
1622 if (!CompareStrings(cx
, astr
, bstr
, &result
)) {
1626 *lessOrEqualp
= (result
<= 0);
1630 static const uint64_t powersOf10
[] = {
1631 1, 10, 100, 1000, 10000, 100000,
1632 1000000, 10000000, 100000000, 1000000000, 1000000000000ULL};
1634 static inline unsigned NumDigitsBase10(uint32_t n
) {
1636 * This is just floor_log10(n) + 1
1637 * Algorithm taken from
1638 * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
1640 uint32_t log2
= CeilingLog2(n
);
1641 uint32_t t
= log2
* 1233 >> 12;
1642 return t
- (n
< powersOf10
[t
]) + 1;
1645 static inline bool CompareLexicographicInt32(const Value
& a
, const Value
& b
,
1646 bool* lessOrEqualp
) {
1647 int32_t aint
= a
.toInt32();
1648 int32_t bint
= b
.toInt32();
1651 * If both numbers are equal ... trivial
1652 * If only one of both is negative --> arithmetic comparison as char code
1653 * of '-' is always less than any other digit
1654 * If both numbers are negative convert them to positive and continue
1658 *lessOrEqualp
= true;
1659 } else if ((aint
< 0) && (bint
>= 0)) {
1660 *lessOrEqualp
= true;
1661 } else if ((aint
>= 0) && (bint
< 0)) {
1662 *lessOrEqualp
= false;
1664 uint32_t auint
= Abs(aint
);
1665 uint32_t buint
= Abs(bint
);
1668 * ... get number of digits of both integers.
1669 * If they have the same number of digits --> arithmetic comparison.
1670 * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
1671 * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
1673 unsigned digitsa
= NumDigitsBase10(auint
);
1674 unsigned digitsb
= NumDigitsBase10(buint
);
1675 if (digitsa
== digitsb
) {
1676 *lessOrEqualp
= (auint
<= buint
);
1677 } else if (digitsa
> digitsb
) {
1678 MOZ_ASSERT((digitsa
- digitsb
) < std::size(powersOf10
));
1680 (uint64_t(auint
) < uint64_t(buint
) * powersOf10
[digitsa
- digitsb
]);
1681 } else { /* if (digitsb > digitsa) */
1682 MOZ_ASSERT((digitsb
- digitsa
) < std::size(powersOf10
));
1684 (uint64_t(auint
) * powersOf10
[digitsb
- digitsa
] <= uint64_t(buint
));
1691 template <typename Char1
, typename Char2
>
1692 static inline bool CompareSubStringValues(JSContext
* cx
, const Char1
* s1
,
1693 size_t len1
, const Char2
* s2
,
1694 size_t len2
, bool* lessOrEqualp
) {
1695 if (!CheckForInterrupt(cx
)) {
1703 int32_t result
= CompareChars(s1
, len1
, s2
, len2
);
1704 *lessOrEqualp
= (result
<= 0);
1710 struct SortComparatorStrings
{
1711 JSContext
* const cx
;
1713 explicit SortComparatorStrings(JSContext
* cx
) : cx(cx
) {}
1715 bool operator()(const Value
& a
, const Value
& b
, bool* lessOrEqualp
) {
1716 return CompareStringValues(cx
, a
, b
, lessOrEqualp
);
1720 struct SortComparatorLexicographicInt32
{
1721 bool operator()(const Value
& a
, const Value
& b
, bool* lessOrEqualp
) {
1722 return CompareLexicographicInt32(a
, b
, lessOrEqualp
);
1726 struct StringifiedElement
{
1729 size_t elementIndex
;
1732 struct SortComparatorStringifiedElements
{
1733 JSContext
* const cx
;
1734 const StringBuffer
& sb
;
1736 SortComparatorStringifiedElements(JSContext
* cx
, const StringBuffer
& sb
)
1739 bool operator()(const StringifiedElement
& a
, const StringifiedElement
& b
,
1740 bool* lessOrEqualp
) {
1741 size_t lenA
= a
.charsEnd
- a
.charsBegin
;
1742 size_t lenB
= b
.charsEnd
- b
.charsBegin
;
1744 if (sb
.isUnderlyingBufferLatin1()) {
1745 return CompareSubStringValues(cx
, sb
.rawLatin1Begin() + a
.charsBegin
,
1746 lenA
, sb
.rawLatin1Begin() + b
.charsBegin
,
1747 lenB
, lessOrEqualp
);
1750 return CompareSubStringValues(cx
, sb
.rawTwoByteBegin() + a
.charsBegin
, lenA
,
1751 sb
.rawTwoByteBegin() + b
.charsBegin
, lenB
,
1756 struct NumericElement
{
1758 size_t elementIndex
;
1761 static bool ComparatorNumericLeftMinusRight(const NumericElement
& a
,
1762 const NumericElement
& b
,
1763 bool* lessOrEqualp
) {
1764 *lessOrEqualp
= std::isunordered(a
.dv
, b
.dv
) || (a
.dv
<= b
.dv
);
1768 static bool ComparatorNumericRightMinusLeft(const NumericElement
& a
,
1769 const NumericElement
& b
,
1770 bool* lessOrEqualp
) {
1771 *lessOrEqualp
= std::isunordered(a
.dv
, b
.dv
) || (b
.dv
<= a
.dv
);
1775 using ComparatorNumeric
= bool (*)(const NumericElement
&, const NumericElement
&,
1778 static const ComparatorNumeric SortComparatorNumerics
[] = {
1779 nullptr, nullptr, ComparatorNumericLeftMinusRight
,
1780 ComparatorNumericRightMinusLeft
};
1782 static bool ComparatorInt32LeftMinusRight(const Value
& a
, const Value
& b
,
1783 bool* lessOrEqualp
) {
1784 *lessOrEqualp
= (a
.toInt32() <= b
.toInt32());
1788 static bool ComparatorInt32RightMinusLeft(const Value
& a
, const Value
& b
,
1789 bool* lessOrEqualp
) {
1790 *lessOrEqualp
= (b
.toInt32() <= a
.toInt32());
1794 using ComparatorInt32
= bool (*)(const Value
&, const Value
&, bool*);
1796 static const ComparatorInt32 SortComparatorInt32s
[] = {
1797 nullptr, nullptr, ComparatorInt32LeftMinusRight
,
1798 ComparatorInt32RightMinusLeft
};
1800 // Note: Values for this enum must match up with SortComparatorNumerics
1801 // and SortComparatorInt32s.
1802 enum ComparatorMatchResult
{
1805 Match_LeftMinusRight
,
1806 Match_RightMinusLeft
1812 * Specialize behavior for comparator functions with particular common bytecode
1813 * patterns: namely, |return x - y| and |return y - x|.
1815 static ComparatorMatchResult
MatchNumericComparator(JSContext
* cx
,
1817 if (!obj
->is
<JSFunction
>()) {
1821 RootedFunction
fun(cx
, &obj
->as
<JSFunction
>());
1822 if (!fun
->isInterpreted() || fun
->isClassConstructor()) {
1826 JSScript
* script
= JSFunction::getOrCreateScript(cx
, fun
);
1828 return Match_Failure
;
1831 jsbytecode
* pc
= script
->code();
1833 uint16_t arg0
, arg1
;
1834 if (JSOp(*pc
) != JSOp::GetArg
) {
1837 arg0
= GET_ARGNO(pc
);
1838 pc
+= JSOpLength_GetArg
;
1840 if (JSOp(*pc
) != JSOp::GetArg
) {
1843 arg1
= GET_ARGNO(pc
);
1844 pc
+= JSOpLength_GetArg
;
1846 if (JSOp(*pc
) != JSOp::Sub
) {
1849 pc
+= JSOpLength_Sub
;
1851 if (JSOp(*pc
) != JSOp::Return
) {
1855 if (arg0
== 0 && arg1
== 1) {
1856 return Match_LeftMinusRight
;
1859 if (arg0
== 1 && arg1
== 0) {
1860 return Match_RightMinusLeft
;
1866 template <typename K
, typename C
>
1867 static inline bool MergeSortByKey(K keys
, size_t len
, K scratch
, C comparator
,
1868 MutableHandle
<GCVector
<Value
>> vec
) {
1869 MOZ_ASSERT(vec
.length() >= len
);
1872 if (!MergeSort(keys
, len
, scratch
, comparator
)) {
1877 * Reorder vec by keys in-place, going element by element. When an out-of-
1878 * place element is encountered, move that element to its proper position,
1879 * displacing whatever element was at *that* point to its proper position,
1880 * and so on until an element must be moved to the current position.
1882 * At each outer iteration all elements up to |i| are sorted. If
1883 * necessary each inner iteration moves some number of unsorted elements
1884 * (including |i|) directly to sorted position. Thus on completion |*vec|
1885 * is sorted, and out-of-position elements have moved once. Complexity is
1886 * Θ(len) + O(len) == O(2*len), with each element visited at most twice.
1888 for (size_t i
= 0; i
< len
; i
++) {
1889 size_t j
= keys
[i
].elementIndex
;
1891 continue; // fixed point
1894 MOZ_ASSERT(j
> i
, "Everything less than |i| should be in the right place!");
1897 size_t k
= keys
[j
].elementIndex
;
1898 keys
[j
].elementIndex
= j
;
1903 // We could assert the loop invariant that |i == keys[i].elementIndex|
1904 // here if we synced |keys[i].elementIndex|. But doing so would render
1905 // the assertion vacuous, so don't bother, even in debug builds.
1913 * Sort Values as strings.
1915 * To minimize #conversions, SortLexicographically() first converts all Values
1916 * to strings at once, then sorts the elements by these cached strings.
1918 static bool SortLexicographically(JSContext
* cx
,
1919 MutableHandle
<GCVector
<Value
>> vec
,
1921 MOZ_ASSERT(vec
.length() >= len
);
1923 StringBuffer
sb(cx
);
1924 Vector
<StringifiedElement
, 0, TempAllocPolicy
> strElements(cx
);
1926 /* MergeSort uses the upper half as scratch space. */
1927 if (!strElements
.resize(2 * len
)) {
1931 /* Convert Values to strings. */
1933 for (size_t i
= 0; i
< len
; i
++) {
1934 if (!CheckForInterrupt(cx
)) {
1938 if (!ValueToStringBuffer(cx
, vec
[i
], sb
)) {
1942 strElements
[i
] = {cursor
, sb
.length(), i
};
1943 cursor
= sb
.length();
1946 /* Sort Values in vec alphabetically. */
1947 return MergeSortByKey(strElements
.begin(), len
, strElements
.begin() + len
,
1948 SortComparatorStringifiedElements(cx
, sb
), vec
);
1952 * Sort Values as numbers.
1954 * To minimize #conversions, SortNumerically first converts all Values to
1955 * numerics at once, then sorts the elements by these cached numerics.
1957 static bool SortNumerically(JSContext
* cx
, MutableHandle
<GCVector
<Value
>> vec
,
1958 size_t len
, ComparatorMatchResult comp
) {
1959 MOZ_ASSERT(vec
.length() >= len
);
1961 Vector
<NumericElement
, 0, TempAllocPolicy
> numElements(cx
);
1963 /* MergeSort uses the upper half as scratch space. */
1964 if (!numElements
.resize(2 * len
)) {
1968 /* Convert Values to numerics. */
1969 for (size_t i
= 0; i
< len
; i
++) {
1970 if (!CheckForInterrupt(cx
)) {
1975 if (!ToNumber(cx
, vec
[i
], &dv
)) {
1979 numElements
[i
] = {dv
, i
};
1982 /* Sort Values in vec numerically. */
1983 return MergeSortByKey(numElements
.begin(), len
, numElements
.begin() + len
,
1984 SortComparatorNumerics
[comp
], vec
);
1987 static bool FillWithUndefined(JSContext
* cx
, HandleObject obj
, uint32_t start
,
1989 MOZ_ASSERT(start
< start
+ count
,
1990 "count > 0 and start + count doesn't overflow");
1993 if (ObjectMayHaveExtraIndexedProperties(obj
)) {
1997 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
1998 if (!nobj
->isExtensible()) {
2002 if (obj
->is
<ArrayObject
>() && !obj
->as
<ArrayObject
>().lengthIsWritable() &&
2003 start
+ count
>= obj
->as
<ArrayObject
>().length()) {
2007 DenseElementResult result
= nobj
->ensureDenseElements(cx
, start
, count
);
2008 if (result
!= DenseElementResult::Success
) {
2009 if (result
== DenseElementResult::Failure
) {
2012 MOZ_ASSERT(result
== DenseElementResult::Incomplete
);
2016 if (obj
->is
<ArrayObject
>() &&
2017 start
+ count
>= obj
->as
<ArrayObject
>().length()) {
2018 obj
->as
<ArrayObject
>().setLength(start
+ count
);
2021 for (uint32_t i
= 0; i
< count
; i
++) {
2022 nobj
->setDenseElement(start
+ i
, UndefinedHandleValue
);
2028 for (uint32_t i
= 0; i
< count
; i
++) {
2029 if (!CheckForInterrupt(cx
) ||
2030 !SetArrayElement(cx
, obj
, start
+ i
, UndefinedHandleValue
)) {
2038 static bool ArraySortWithoutComparator(JSContext
* cx
, Handle
<JSObject
*> obj
,
2040 ComparatorMatchResult comp
) {
2041 MOZ_ASSERT(length
> 1);
2043 if (length
> UINT32_MAX
) {
2044 ReportAllocationOverflow(cx
);
2047 uint32_t len
= uint32_t(length
);
2050 * We need a temporary array of 2 * len Value to hold the array elements
2051 * and the scratch space for merge sort. Check that its size does not
2052 * overflow size_t, which would allow for indexing beyond the end of the
2055 #if JS_BITS_PER_WORD == 32
2056 if (size_t(len
) > size_t(-1) / (2 * sizeof(Value
))) {
2057 ReportAllocationOverflow(cx
);
2064 Rooted
<GCVector
<Value
>> vec(cx
, GCVector
<Value
>(cx
));
2065 if (!vec
.reserve(2 * size_t(len
))) {
2070 * By ECMA 262, 15.4.4.11, a property that does not exist (which we
2071 * call a "hole") is always greater than an existing property with
2072 * value undefined and that is always greater than any other property.
2073 * Thus to sort holes and undefs we simply count them, sort the rest
2074 * of elements, append undefs after them and then make holes after
2078 bool allStrings
= true;
2079 bool allInts
= true;
2081 if (IsPackedArray(obj
)) {
2082 Handle
<ArrayObject
*> array
= obj
.as
<ArrayObject
>();
2084 for (uint32_t i
= 0; i
< len
; i
++) {
2085 if (!CheckForInterrupt(cx
)) {
2089 v
.set(array
->getDenseElement(i
));
2090 MOZ_ASSERT(!v
.isMagic(JS_ELEMENTS_HOLE
));
2091 if (v
.isUndefined()) {
2095 vec
.infallibleAppend(v
);
2096 allStrings
= allStrings
&& v
.isString();
2097 allInts
= allInts
&& v
.isInt32();
2100 for (uint32_t i
= 0; i
< len
; i
++) {
2101 if (!CheckForInterrupt(cx
)) {
2106 if (!HasAndGetElement(cx
, obj
, i
, &hole
, &v
)) {
2112 if (v
.isUndefined()) {
2116 vec
.infallibleAppend(v
);
2117 allStrings
= allStrings
&& v
.isString();
2118 allInts
= allInts
&& v
.isInt32();
2123 * If the array only contains holes, we're done. But if it contains
2124 * undefs, those must be sorted to the front of the array.
2127 if (n
== 0 && undefs
== 0) {
2131 /* Here len == n + undefs + number_of_holes. */
2132 if (comp
== Match_None
) {
2134 * Sort using the default comparator converting all elements to
2138 MOZ_ALWAYS_TRUE(vec
.resize(n
* 2));
2139 if (!MergeSort(vec
.begin(), n
, vec
.begin() + n
,
2140 SortComparatorStrings(cx
))) {
2143 } else if (allInts
) {
2144 MOZ_ALWAYS_TRUE(vec
.resize(n
* 2));
2145 if (!MergeSort(vec
.begin(), n
, vec
.begin() + n
,
2146 SortComparatorLexicographicInt32())) {
2150 if (!SortLexicographically(cx
, &vec
, n
)) {
2156 MOZ_ALWAYS_TRUE(vec
.resize(n
* 2));
2157 if (!MergeSort(vec
.begin(), n
, vec
.begin() + n
,
2158 SortComparatorInt32s
[comp
])) {
2162 if (!SortNumerically(cx
, &vec
, n
, comp
)) {
2168 if (!SetArrayElements(cx
, obj
, 0, uint32_t(n
), vec
.begin())) {
2173 /* Set undefs that sorted after the rest of elements. */
2175 if (!FillWithUndefined(cx
, obj
, n
, undefs
)) {
2181 /* Re-create any holes that sorted to the end of the array. */
2182 for (uint32_t i
= n
; i
< len
; i
++) {
2183 if (!CheckForInterrupt(cx
) || !DeletePropertyOrThrow(cx
, obj
, i
)) {
2190 // This function handles sorting without a comparator function (or with a
2191 // trivial comparator function that we can pattern match) by calling
2192 // ArraySortWithoutComparator.
2194 // If there's a non-trivial comparator function, it initializes the
2195 // ArraySortData struct for ArraySortData::sortArrayWithComparator. This
2196 // function must be called next to perform the sorting.
2198 // This is separate from ArraySortData::sortArrayWithComparator because it lets
2199 // the compiler generate better code for ArraySortData::sortArrayWithComparator.
2201 // https://tc39.es/ecma262/#sec-array.prototype.sort
2202 // 23.1.3.30 Array.prototype.sort ( comparefn )
2203 static MOZ_ALWAYS_INLINE
bool ArraySortPrologue(JSContext
* cx
,
2204 Handle
<Value
> thisv
,
2205 Handle
<Value
> comparefn
,
2206 ArraySortData
* d
, bool* done
) {
2208 if (MOZ_UNLIKELY(!comparefn
.isUndefined() && !IsCallable(comparefn
))) {
2209 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_SORT_ARG
);
2214 Rooted
<JSObject
*> obj(cx
, ToObject(cx
, thisv
));
2221 if (MOZ_UNLIKELY(!GetLengthPropertyInlined(cx
, obj
, &length
))) {
2225 // Arrays with less than two elements remain unchanged when sorted.
2227 d
->setReturnValue(obj
);
2232 // Use a fast path if there's no comparator or if the comparator is a function
2233 // that we can pattern match.
2235 ComparatorMatchResult comp
= Match_None
;
2236 if (comparefn
.isObject()) {
2237 comp
= MatchNumericComparator(cx
, &comparefn
.toObject());
2238 if (comp
== Match_Failure
) {
2241 if (comp
== Match_None
) {
2242 // Pattern matching failed.
2246 if (!ArraySortWithoutComparator(cx
, obj
, length
, comp
)) {
2249 d
->setReturnValue(obj
);
2254 // Ensure length * 2 (used below) doesn't overflow UINT32_MAX.
2255 if (MOZ_UNLIKELY(length
> UINT32_MAX
/ 2)) {
2256 ReportAllocationOverflow(cx
);
2259 uint32_t len
= uint32_t(length
);
2261 // Merge sort requires extra scratch space.
2262 bool needsScratchSpace
= len
> ArraySortData::InsertionSortMaxLength
;
2264 Rooted
<ArraySortData::ValueVector
> vec(cx
);
2265 if (MOZ_UNLIKELY(!vec
.reserve(needsScratchSpace
? (2 * len
) : len
))) {
2266 ReportOutOfMemory(cx
);
2270 // Append elements to the vector. Skip holes.
2271 if (IsPackedArray(obj
)) {
2272 Handle
<ArrayObject
*> array
= obj
.as
<ArrayObject
>();
2273 const Value
* elements
= array
->getDenseElements();
2274 vec
.infallibleAppend(elements
, len
);
2277 for (uint32_t i
= 0; i
< len
; i
++) {
2278 if (!CheckForInterrupt(cx
)) {
2283 if (!HasAndGetElement(cx
, obj
, i
, &hole
, &v
)) {
2289 vec
.infallibleAppend(v
);
2291 // If there are only holes, the object is already sorted.
2293 d
->setReturnValue(obj
);
2299 uint32_t denseLen
= vec
.length();
2300 if (needsScratchSpace
) {
2301 MOZ_ALWAYS_TRUE(vec
.resize(denseLen
* 2));
2303 d
->init(obj
, &comparefn
.toObject(), std::move(vec
.get()), len
, denseLen
);
2305 // Continue in ArraySortData::sortArrayWithComparator.
2310 ArraySortResult
js::CallComparatorSlow(ArraySortData
* d
, const Value
& x
,
2312 JSContext
* cx
= d
->cx();
2313 FixedInvokeArgs
<2> callArgs(cx
);
2316 Rooted
<Value
> comparefn(cx
, ObjectValue(*d
->comparator()));
2317 Rooted
<Value
> rval(cx
);
2318 if (!js::Call(cx
, comparefn
, UndefinedHandleValue
, callArgs
, &rval
)) {
2319 return ArraySortResult::Failure
;
2321 d
->setComparatorReturnValue(rval
);
2322 return ArraySortResult::Done
;
2326 ArraySortResult
ArraySortData::sortArrayWithComparator(ArraySortData
* d
) {
2327 ArraySortResult result
= sortWithComparatorShared
<ArraySortKind::Array
>(d
);
2328 if (result
!= ArraySortResult::Done
) {
2332 // Copy elements to the array.
2333 JSContext
* cx
= d
->cx();
2334 Rooted
<JSObject
*> obj(cx
, d
->obj_
);
2335 if (!SetArrayElements(cx
, obj
, 0, d
->denseLen
, d
->list
)) {
2336 return ArraySortResult::Failure
;
2339 // Re-create any holes that sorted to the end of the array.
2340 for (uint32_t i
= d
->denseLen
; i
< d
->length
; i
++) {
2341 if (!CheckForInterrupt(cx
) || !DeletePropertyOrThrow(cx
, obj
, i
)) {
2342 return ArraySortResult::Failure
;
2346 d
->freeMallocData();
2347 d
->setReturnValue(obj
);
2348 return ArraySortResult::Done
;
2351 // https://tc39.es/ecma262/#sec-array.prototype.sort
2352 // 23.1.3.30 Array.prototype.sort ( comparefn )
2353 bool js::array_sort(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2354 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "sort");
2355 CallArgs args
= CallArgsFromVp(argc
, vp
);
2357 // If we have a comparator argument, use the JIT trampoline implementation
2358 // instead. This avoids a performance cliff (especially with large arrays)
2359 // because C++ => JIT calls are much slower than Trampoline => JIT calls.
2360 if (args
.hasDefined(0) && jit::IsBaselineInterpreterEnabled()) {
2361 return CallTrampolineNativeJitCode(cx
, jit::TrampolineNative::ArraySort
,
2365 Rooted
<ArraySortData
> data(cx
, cx
);
2367 // On all return paths other than ArraySortData::sortArrayWithComparator
2368 // returning Done, we call freeMallocData to not fail debug assertions. This
2369 // matches the JIT trampoline where we can't rely on C++ destructors.
2371 mozilla::MakeScopeExit([&]() { data
.get().freeMallocData(); });
2374 if (!ArraySortPrologue(cx
, args
.thisv(), args
.get(0), data
.address(),
2379 args
.rval().set(data
.get().returnValue());
2383 FixedInvokeArgs
<2> callArgs(cx
);
2384 Rooted
<Value
> rval(cx
);
2387 ArraySortResult res
=
2388 ArraySortData::sortArrayWithComparator(data
.address());
2390 case ArraySortResult::Failure
:
2393 case ArraySortResult::Done
:
2395 args
.rval().set(data
.get().returnValue());
2398 case ArraySortResult::CallJS
:
2399 case ArraySortResult::CallJSSameRealmNoRectifier
:
2400 MOZ_ASSERT(data
.get().comparatorThisValue().isUndefined());
2401 MOZ_ASSERT(&args
[0].toObject() == data
.get().comparator());
2402 callArgs
[0].set(data
.get().comparatorArg(0));
2403 callArgs
[1].set(data
.get().comparatorArg(1));
2404 if (!js::Call(cx
, args
[0], UndefinedHandleValue
, callArgs
, &rval
)) {
2407 data
.get().setComparatorReturnValue(rval
);
2413 ArraySortResult
js::ArraySortFromJit(JSContext
* cx
,
2414 jit::TrampolineNativeFrameLayout
* frame
) {
2415 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "sort");
2416 // Initialize the ArraySortData class stored in the trampoline frame.
2417 void* dataUninit
= frame
->getFrameData
<ArraySortData
>();
2418 auto* data
= new (dataUninit
) ArraySortData(cx
);
2420 Rooted
<Value
> thisv(cx
, frame
->thisv());
2421 Rooted
<Value
> comparefn(cx
);
2422 if (frame
->numActualArgs() > 0) {
2423 comparefn
= frame
->actualArgs()[0];
2427 if (!ArraySortPrologue(cx
, thisv
, comparefn
, data
, &done
)) {
2428 return ArraySortResult::Failure
;
2431 data
->freeMallocData();
2432 return ArraySortResult::Done
;
2435 return ArraySortData::sortArrayWithComparator(data
);
2438 void ArraySortData::trace(JSTracer
* trc
) {
2439 TraceNullableRoot(trc
, &comparator_
, "comparator_");
2440 TraceRoot(trc
, &thisv
, "thisv");
2441 TraceRoot(trc
, &callArgs
[0], "callArgs0");
2442 TraceRoot(trc
, &callArgs
[1], "callArgs1");
2444 TraceRoot(trc
, &item
, "item");
2445 TraceNullableRoot(trc
, &obj_
, "obj");
2448 bool js::NewbornArrayPush(JSContext
* cx
, HandleObject obj
, const Value
& v
) {
2449 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
2451 MOZ_ASSERT(!v
.isMagic());
2452 MOZ_ASSERT(arr
->lengthIsWritable());
2454 uint32_t length
= arr
->length();
2455 MOZ_ASSERT(length
<= arr
->getDenseCapacity());
2457 if (!arr
->ensureElements(cx
, length
+ 1)) {
2461 arr
->setDenseInitializedLength(length
+ 1);
2462 arr
->setLength(length
+ 1);
2463 arr
->initDenseElement(length
, v
);
2467 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2468 // 22.1.3.18 Array.prototype.push ( ...items )
2469 static bool array_push(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2470 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "push");
2471 CallArgs args
= CallArgsFromVp(argc
, vp
);
2474 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2481 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
2485 if (!ObjectMayHaveExtraIndexedProperties(obj
) && length
<= UINT32_MAX
) {
2486 DenseElementResult result
=
2487 obj
->as
<NativeObject
>().setOrExtendDenseElements(
2488 cx
, uint32_t(length
), args
.array(), args
.length());
2489 if (result
!= DenseElementResult::Incomplete
) {
2490 if (result
== DenseElementResult::Failure
) {
2494 uint32_t newlength
= uint32_t(length
) + args
.length();
2495 args
.rval().setNumber(newlength
);
2497 // setOrExtendDenseElements takes care of updating the length for
2498 // arrays. Handle updates to the length of non-arrays here.
2499 if (!obj
->is
<ArrayObject
>()) {
2500 MOZ_ASSERT(obj
->is
<NativeObject
>());
2501 return SetLengthProperty(cx
, obj
, newlength
);
2509 uint64_t newlength
= length
+ args
.length();
2510 if (newlength
>= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
)) {
2511 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
2512 JSMSG_TOO_LONG_ARRAY
);
2517 if (!SetArrayElements(cx
, obj
, length
, args
.length(), args
.array())) {
2522 args
.rval().setNumber(double(newlength
));
2523 return SetLengthProperty(cx
, obj
, newlength
);
2526 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2527 // 22.1.3.17 Array.prototype.pop ( )
2528 bool js::array_pop(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2529 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "pop");
2530 CallArgs args
= CallArgsFromVp(argc
, vp
);
2533 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2540 if (!GetLengthPropertyInlined(cx
, obj
, &index
)) {
2547 args
.rval().setUndefined();
2553 if (!GetArrayElement(cx
, obj
, index
, args
.rval())) {
2558 if (!DeletePropertyOrThrow(cx
, obj
, index
)) {
2564 return SetLengthProperty(cx
, obj
, index
);
2567 void js::ArrayShiftMoveElements(ArrayObject
* arr
) {
2568 AutoUnsafeCallWithABI unsafe
;
2569 MOZ_ASSERT(arr
->isExtensible());
2570 MOZ_ASSERT(arr
->lengthIsWritable());
2571 MOZ_ASSERT(IsPackedArray(arr
));
2572 MOZ_ASSERT(!arr
->denseElementsHaveMaybeInIterationFlag());
2574 size_t initlen
= arr
->getDenseInitializedLength();
2575 MOZ_ASSERT(initlen
> 0);
2577 if (!arr
->tryShiftDenseElements(1)) {
2578 arr
->moveDenseElements(0, 1, initlen
- 1);
2579 arr
->setDenseInitializedLength(initlen
- 1);
2582 MOZ_ASSERT(arr
->getDenseInitializedLength() == initlen
- 1);
2583 arr
->setLength(initlen
- 1);
2586 static inline void SetInitializedLength(JSContext
* cx
, NativeObject
* obj
,
2588 MOZ_ASSERT(obj
->isExtensible());
2590 size_t oldInitlen
= obj
->getDenseInitializedLength();
2591 obj
->setDenseInitializedLength(initlen
);
2592 if (initlen
< oldInitlen
) {
2593 obj
->shrinkElements(cx
, initlen
);
2597 static DenseElementResult
ArrayShiftDenseKernel(JSContext
* cx
, HandleObject obj
,
2598 MutableHandleValue rval
) {
2599 if (!IsPackedArray(obj
) && ObjectMayHaveExtraIndexedProperties(obj
)) {
2600 return DenseElementResult::Incomplete
;
2603 Handle
<NativeObject
*> nobj
= obj
.as
<NativeObject
>();
2604 if (nobj
->denseElementsMaybeInIteration()) {
2605 return DenseElementResult::Incomplete
;
2608 if (!nobj
->isExtensible()) {
2609 return DenseElementResult::Incomplete
;
2612 size_t initlen
= nobj
->getDenseInitializedLength();
2614 return DenseElementResult::Incomplete
;
2617 rval
.set(nobj
->getDenseElement(0));
2618 if (rval
.isMagic(JS_ELEMENTS_HOLE
)) {
2619 rval
.setUndefined();
2622 if (nobj
->tryShiftDenseElements(1)) {
2623 return DenseElementResult::Success
;
2626 nobj
->moveDenseElements(0, 1, initlen
- 1);
2628 SetInitializedLength(cx
, nobj
, initlen
- 1);
2629 return DenseElementResult::Success
;
2632 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2633 // 22.1.3.22 Array.prototype.shift ( )
2634 static bool array_shift(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2635 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "shift");
2636 CallArgs args
= CallArgsFromVp(argc
, vp
);
2639 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2646 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
2653 if (!SetLengthProperty(cx
, obj
, uint32_t(0))) {
2658 args
.rval().setUndefined();
2662 uint64_t newlen
= len
- 1;
2665 uint64_t startIndex
;
2666 DenseElementResult result
= ArrayShiftDenseKernel(cx
, obj
, args
.rval());
2667 if (result
!= DenseElementResult::Incomplete
) {
2668 if (result
== DenseElementResult::Failure
) {
2672 if (len
<= UINT32_MAX
) {
2673 return SetLengthProperty(cx
, obj
, newlen
);
2676 startIndex
= UINT32_MAX
- 1;
2679 if (!GetElement(cx
, obj
, 0, args
.rval())) {
2687 RootedValue
value(cx
);
2688 for (uint64_t i
= startIndex
; i
< newlen
; i
++) {
2689 if (!CheckForInterrupt(cx
)) {
2693 if (!HasAndGetElement(cx
, obj
, i
+ 1, &hole
, &value
)) {
2697 if (!DeletePropertyOrThrow(cx
, obj
, i
)) {
2701 if (!SetArrayElement(cx
, obj
, i
, value
)) {
2708 if (!DeletePropertyOrThrow(cx
, obj
, newlen
)) {
2713 return SetLengthProperty(cx
, obj
, newlen
);
2716 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2717 // 22.1.3.29 Array.prototype.unshift ( ...items )
2718 static bool array_unshift(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2719 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "unshift");
2720 CallArgs args
= CallArgsFromVp(argc
, vp
);
2723 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2730 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
2735 if (args
.length() > 0) {
2736 bool optimized
= false;
2738 if (length
> UINT32_MAX
) {
2741 if (ObjectMayHaveExtraIndexedProperties(obj
)) {
2744 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
2745 if (nobj
->denseElementsMaybeInIteration()) {
2748 if (!nobj
->isExtensible()) {
2751 if (nobj
->is
<ArrayObject
>() &&
2752 !nobj
->as
<ArrayObject
>().lengthIsWritable()) {
2755 if (!nobj
->tryUnshiftDenseElements(args
.length())) {
2756 DenseElementResult result
=
2757 nobj
->ensureDenseElements(cx
, uint32_t(length
), args
.length());
2758 if (result
!= DenseElementResult::Success
) {
2759 if (result
== DenseElementResult::Failure
) {
2762 MOZ_ASSERT(result
== DenseElementResult::Incomplete
);
2766 nobj
->moveDenseElements(args
.length(), 0, uint32_t(length
));
2769 for (uint32_t i
= 0; i
< args
.length(); i
++) {
2770 nobj
->setDenseElement(i
, args
[i
]);
2777 uint64_t last
= length
;
2778 uint64_t upperIndex
= last
+ args
.length();
2781 if (upperIndex
>= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
)) {
2782 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
2783 JSMSG_TOO_LONG_ARRAY
);
2788 RootedValue
value(cx
);
2792 if (!CheckForInterrupt(cx
)) {
2796 if (!HasAndGetElement(cx
, obj
, last
, &hole
, &value
)) {
2800 if (!DeletePropertyOrThrow(cx
, obj
, upperIndex
)) {
2804 if (!SetArrayElement(cx
, obj
, upperIndex
, value
)) {
2808 } while (last
!= 0);
2812 /* Copy from args to the bottom of the array. */
2813 if (!SetArrayElements(cx
, obj
, 0, args
.length(), args
.array())) {
2820 uint64_t newlength
= length
+ args
.length();
2821 if (!SetLengthProperty(cx
, obj
, newlength
)) {
2826 /* Follow Perl by returning the new array length. */
2827 args
.rval().setNumber(double(newlength
));
2831 enum class ArrayAccess
{ Read
, Write
};
2834 * Returns true if this is a dense array whose properties ending at |endIndex|
2835 * (exclusive) may be accessed (get, set, delete) directly through its
2836 * contiguous vector of elements without fear of getters, setters, etc. along
2837 * the prototype chain, or of enumerators requiring notification of
2840 template <ArrayAccess Access
>
2841 static bool CanOptimizeForDenseStorage(HandleObject arr
, uint64_t endIndex
) {
2842 /* If the desired properties overflow dense storage, we can't optimize. */
2843 if (endIndex
> UINT32_MAX
) {
2847 if (Access
== ArrayAccess::Read
) {
2849 * Dense storage read access is possible for any packed array as long
2850 * as we only access properties within the initialized length. In all
2851 * other cases we need to ensure there are no other indexed properties
2852 * on this object or on the prototype chain. Callers are required to
2853 * clamp the read length, so it doesn't exceed the initialized length.
2855 if (IsPackedArray(arr
) &&
2856 endIndex
<= arr
->as
<ArrayObject
>().getDenseInitializedLength()) {
2859 return !ObjectMayHaveExtraIndexedProperties(arr
);
2862 /* There's no optimizing possible if it's not an array. */
2863 if (!arr
->is
<ArrayObject
>()) {
2867 /* If the length is non-writable, always pick the slow path */
2868 if (!arr
->as
<ArrayObject
>().lengthIsWritable()) {
2872 /* Also pick the slow path if the object is non-extensible. */
2873 if (!arr
->as
<ArrayObject
>().isExtensible()) {
2877 /* Also pick the slow path if the object is being iterated over. */
2878 if (arr
->as
<ArrayObject
>().denseElementsMaybeInIteration()) {
2882 /* Or we attempt to write to indices outside the initialized length. */
2883 if (endIndex
> arr
->as
<ArrayObject
>().getDenseInitializedLength()) {
2888 * Now watch out for getters and setters along the prototype chain or in
2889 * other indexed properties on the object. Packed arrays don't have any
2890 * other indexed properties by definition.
2892 return IsPackedArray(arr
) || !ObjectMayHaveExtraIndexedProperties(arr
);
2895 static ArrayObject
* CopyDenseArrayElements(JSContext
* cx
,
2896 Handle
<NativeObject
*> obj
,
2897 uint32_t begin
, uint32_t count
) {
2898 size_t initlen
= obj
->getDenseInitializedLength();
2899 MOZ_ASSERT(initlen
<= UINT32_MAX
,
2900 "initialized length shouldn't exceed UINT32_MAX");
2901 uint32_t newlength
= 0;
2902 if (initlen
> begin
) {
2903 newlength
= std::min
<uint32_t>(initlen
- begin
, count
);
2906 ArrayObject
* narr
= NewDenseFullyAllocatedArray(cx
, newlength
);
2911 MOZ_ASSERT(count
>= narr
->length());
2912 narr
->setLength(count
);
2914 if (newlength
> 0) {
2915 narr
->initDenseElements(obj
, begin
, newlength
);
2921 static bool CopyArrayElements(JSContext
* cx
, HandleObject obj
, uint64_t begin
,
2922 uint64_t count
, Handle
<ArrayObject
*> result
) {
2923 MOZ_ASSERT(result
->length() == count
);
2925 uint64_t startIndex
= 0;
2926 RootedValue
value(cx
);
2928 // Use dense storage for new indexed properties where possible.
2931 uint32_t limit
= std::min
<uint32_t>(count
, PropertyKey::IntMax
);
2932 for (; index
< limit
; index
++) {
2934 if (!CheckForInterrupt(cx
) ||
2935 !HasAndGetElement(cx
, obj
, begin
+ index
, &hole
, &value
)) {
2940 DenseElementResult edResult
= result
->ensureDenseElements(cx
, index
, 1);
2941 if (edResult
!= DenseElementResult::Success
) {
2942 if (edResult
== DenseElementResult::Failure
) {
2946 MOZ_ASSERT(edResult
== DenseElementResult::Incomplete
);
2947 if (!DefineDataElement(cx
, result
, index
, value
)) {
2953 result
->setDenseElement(index
, value
);
2956 startIndex
= index
+ 1;
2959 // Copy any remaining elements.
2960 for (uint64_t i
= startIndex
; i
< count
; i
++) {
2962 if (!CheckForInterrupt(cx
) ||
2963 !HasAndGetElement(cx
, obj
, begin
+ i
, &hole
, &value
)) {
2967 if (!hole
&& !DefineArrayElement(cx
, result
, i
, value
)) {
2974 // Helpers for array_splice_impl() and array_to_spliced()
2976 // Initialize variables common to splice() and toSpliced():
2977 // - GetActualStart() returns the index at which to start deleting elements.
2978 // - GetItemCount() returns the number of new elements being added.
2979 // - GetActualDeleteCount() returns the number of elements being deleted.
2980 static bool GetActualStart(JSContext
* cx
, HandleValue start
, uint64_t len
,
2982 MOZ_ASSERT(len
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
2984 // Steps from proposal: https://github.com/tc39/proposal-change-array-by-copy
2985 // Array.prototype.toSpliced()
2987 // Step 3. Let relativeStart be ? ToIntegerOrInfinity(start).
2988 double relativeStart
;
2989 if (!ToInteger(cx
, start
, &relativeStart
)) {
2993 // Steps 4-5. If relativeStart is -∞, let actualStart be 0.
2994 // Else if relativeStart < 0, let actualStart be max(len + relativeStart, 0).
2995 if (relativeStart
< 0) {
2996 *result
= uint64_t(std::max(double(len
) + relativeStart
, 0.0));
2998 // Step 6. Else, let actualStart be min(relativeStart, len).
2999 *result
= uint64_t(std::min(relativeStart
, double(len
)));
3004 static uint32_t GetItemCount(const CallArgs
& args
) {
3005 if (args
.length() < 2) {
3008 return (args
.length() - 2);
3011 static bool GetActualDeleteCount(JSContext
* cx
, const CallArgs
& args
,
3012 HandleObject obj
, uint64_t len
,
3013 uint64_t actualStart
, uint32_t insertCount
,
3014 uint64_t* actualDeleteCount
) {
3015 MOZ_ASSERT(len
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
3016 MOZ_ASSERT(actualStart
<= len
);
3017 MOZ_ASSERT(insertCount
== GetItemCount(args
));
3019 // Steps from proposal: https://github.com/tc39/proposal-change-array-by-copy
3020 // Array.prototype.toSpliced()
3022 if (args
.length() < 1) {
3023 // Step 8. If start is not present, then let actualDeleteCount be 0.
3024 *actualDeleteCount
= 0;
3025 } else if (args
.length() < 2) {
3026 // Step 9. Else if deleteCount is not present, then let actualDeleteCount be
3027 // len - actualStart.
3028 *actualDeleteCount
= len
- actualStart
;
3030 // Step 10.a. Else, let dc be toIntegerOrInfinity(deleteCount).
3032 if (!ToInteger(cx
, args
.get(1), &deleteCount
)) {
3036 // Step 10.b. Let actualDeleteCount be the result of clamping dc between 0
3037 // and len - actualStart.
3038 *actualDeleteCount
= uint64_t(
3039 std::min(std::max(0.0, deleteCount
), double(len
- actualStart
)));
3040 MOZ_ASSERT(*actualDeleteCount
<= len
);
3042 // Step 11. Let newLen be len + insertCount - actualDeleteCount.
3043 // Step 12. If newLen > 2^53 - 1, throw a TypeError exception.
3044 if (len
+ uint64_t(insertCount
) - *actualDeleteCount
>=
3045 uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
)) {
3046 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3047 JSMSG_TOO_LONG_ARRAY
);
3051 MOZ_ASSERT(actualStart
+ *actualDeleteCount
<= len
);
3056 static bool array_splice_impl(JSContext
* cx
, unsigned argc
, Value
* vp
,
3057 bool returnValueIsUsed
) {
3058 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "splice");
3059 CallArgs args
= CallArgsFromVp(argc
, vp
);
3062 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
3069 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
3074 /* actualStart is the index after which elements will be
3075 deleted and/or new elements will be added */
3076 uint64_t actualStart
;
3077 if (!GetActualStart(cx
, args
.get(0), len
, &actualStart
)) {
3082 /* itemCount is the number of elements being added */
3083 uint32_t itemCount
= GetItemCount(args
);
3085 /* actualDeleteCount is the number of elements being deleted */
3086 uint64_t actualDeleteCount
;
3087 if (!GetActualDeleteCount(cx
, args
, obj
, len
, actualStart
, itemCount
,
3088 &actualDeleteCount
)) {
3092 RootedObject
arr(cx
);
3093 if (IsArraySpecies(cx
, obj
)) {
3094 if (actualDeleteCount
> UINT32_MAX
) {
3095 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3096 JSMSG_BAD_ARRAY_LENGTH
);
3099 uint32_t count
= uint32_t(actualDeleteCount
);
3101 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
,
3102 actualStart
+ count
)) {
3103 MOZ_ASSERT(actualStart
<= UINT32_MAX
,
3104 "if actualStart + count <= UINT32_MAX, then actualStart <= "
3106 if (returnValueIsUsed
) {
3108 arr
= CopyDenseArrayElements(cx
, obj
.as
<NativeObject
>(),
3109 uint32_t(actualStart
), count
);
3116 arr
= NewDenseFullyAllocatedArray(cx
, count
);
3122 if (!CopyArrayElements(cx
, obj
, actualStart
, count
,
3123 arr
.as
<ArrayObject
>())) {
3129 if (!ArraySpeciesCreate(cx
, obj
, actualDeleteCount
, &arr
)) {
3134 RootedValue
fromValue(cx
);
3135 for (uint64_t k
= 0; k
< actualDeleteCount
; k
++) {
3136 if (!CheckForInterrupt(cx
)) {
3140 /* Steps 13.b, 13.c.i. */
3142 if (!HasAndGetElement(cx
, obj
, actualStart
+ k
, &hole
, &fromValue
)) {
3149 if (!DefineArrayElement(cx
, arr
, k
, fromValue
)) {
3156 if (!SetLengthProperty(cx
, arr
, actualDeleteCount
)) {
3162 uint64_t finalLength
= len
- actualDeleteCount
+ itemCount
;
3164 if (itemCount
< actualDeleteCount
) {
3165 /* Step 16: the array is being shrunk. */
3166 uint64_t sourceIndex
= actualStart
+ actualDeleteCount
;
3167 uint64_t targetIndex
= actualStart
+ itemCount
;
3169 if (CanOptimizeForDenseStorage
<ArrayAccess::Write
>(obj
, len
)) {
3170 MOZ_ASSERT(sourceIndex
<= len
&& targetIndex
<= len
&& len
<= UINT32_MAX
,
3171 "sourceIndex and targetIndex are uint32 array indices");
3172 MOZ_ASSERT(finalLength
< len
, "finalLength is strictly less than len");
3173 MOZ_ASSERT(obj
->is
<NativeObject
>());
3176 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
3177 if (targetIndex
!= 0 || !arr
->tryShiftDenseElements(sourceIndex
)) {
3178 arr
->moveDenseElements(uint32_t(targetIndex
), uint32_t(sourceIndex
),
3179 uint32_t(len
- sourceIndex
));
3183 SetInitializedLength(cx
, arr
, finalLength
);
3186 * This is all very slow if the length is very large. We don't yet
3187 * have the ability to iterate in sorted order, so we just do the
3188 * pessimistic thing and let CheckForInterrupt handle the
3193 RootedValue
fromValue(cx
);
3194 for (uint64_t from
= sourceIndex
, to
= targetIndex
; from
< len
;
3196 /* Steps 15.b.i-ii (implicit). */
3198 if (!CheckForInterrupt(cx
)) {
3202 /* Steps 16.b.iii-v */
3204 if (!HasAndGetElement(cx
, obj
, from
, &hole
, &fromValue
)) {
3209 if (!DeletePropertyOrThrow(cx
, obj
, to
)) {
3213 if (!SetArrayElement(cx
, obj
, to
, fromValue
)) {
3220 if (!DeletePropertiesOrThrow(cx
, obj
, len
, finalLength
)) {
3224 } else if (itemCount
> actualDeleteCount
) {
3225 MOZ_ASSERT(actualDeleteCount
<= UINT32_MAX
);
3226 uint32_t deleteCount
= uint32_t(actualDeleteCount
);
3230 // Fast path for when we can simply extend and move the dense elements.
3231 auto extendElements
= [len
, itemCount
, deleteCount
](JSContext
* cx
,
3233 if (!obj
->is
<ArrayObject
>()) {
3234 return DenseElementResult::Incomplete
;
3236 if (len
> UINT32_MAX
) {
3237 return DenseElementResult::Incomplete
;
3240 // Ensure there are no getters/setters or other extra indexed properties.
3241 if (ObjectMayHaveExtraIndexedProperties(obj
)) {
3242 return DenseElementResult::Incomplete
;
3245 // Watch out for arrays with non-writable length or non-extensible arrays.
3246 // In these cases `splice` may have to throw an exception so we let the
3247 // slow path handle it. We also have to ensure we maintain the
3248 // |capacity <= initializedLength| invariant for such objects. See
3249 // NativeObject::shrinkCapacityToInitializedLength.
3250 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
3251 if (!arr
->lengthIsWritable() || !arr
->isExtensible()) {
3252 return DenseElementResult::Incomplete
;
3255 // Also use the slow path if there might be an active for-in iterator so
3256 // that we don't have to worry about suppressing deleted properties.
3257 if (arr
->denseElementsMaybeInIteration()) {
3258 return DenseElementResult::Incomplete
;
3261 return arr
->ensureDenseElements(cx
, uint32_t(len
),
3262 itemCount
- deleteCount
);
3265 DenseElementResult res
= extendElements(cx
, obj
);
3266 if (res
== DenseElementResult::Failure
) {
3269 if (res
== DenseElementResult::Success
) {
3270 MOZ_ASSERT(finalLength
<= UINT32_MAX
);
3271 MOZ_ASSERT((actualStart
+ actualDeleteCount
) <= len
&& len
<= UINT32_MAX
,
3272 "start and deleteCount are uint32 array indices");
3273 MOZ_ASSERT(actualStart
+ itemCount
<= UINT32_MAX
,
3274 "can't overflow because |len - actualDeleteCount + itemCount "
3276 "and |actualStart <= len - actualDeleteCount| are both true");
3277 uint32_t start
= uint32_t(actualStart
);
3278 uint32_t length
= uint32_t(len
);
3280 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
3281 arr
->moveDenseElements(start
+ itemCount
, start
+ deleteCount
,
3282 length
- (start
+ deleteCount
));
3285 SetInitializedLength(cx
, arr
, finalLength
);
3287 MOZ_ASSERT(res
== DenseElementResult::Incomplete
);
3289 RootedValue
fromValue(cx
);
3290 for (uint64_t k
= len
- actualDeleteCount
; k
> actualStart
; k
--) {
3291 if (!CheckForInterrupt(cx
)) {
3296 uint64_t from
= k
+ actualDeleteCount
- 1;
3299 uint64_t to
= k
+ itemCount
- 1;
3301 /* Steps 17.b.iii, 17.b.iv.1. */
3303 if (!HasAndGetElement(cx
, obj
, from
, &hole
, &fromValue
)) {
3307 /* Steps 17.b.iv. */
3309 /* Step 17.b.v.1. */
3310 if (!DeletePropertyOrThrow(cx
, obj
, to
)) {
3314 /* Step 17.b.iv.2. */
3315 if (!SetArrayElement(cx
, obj
, to
, fromValue
)) {
3323 Value
* items
= args
.array() + 2;
3326 if (!SetArrayElements(cx
, obj
, actualStart
, itemCount
, items
)) {
3331 if (!SetLengthProperty(cx
, obj
, finalLength
)) {
3336 if (returnValueIsUsed
) {
3337 args
.rval().setObject(*arr
);
3343 /* ES 2016 draft Mar 25, 2016 22.1.3.26. */
3344 static bool array_splice(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3345 return array_splice_impl(cx
, argc
, vp
, true);
3348 static bool array_splice_noRetVal(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3349 return array_splice_impl(cx
, argc
, vp
, false);
3352 static void CopyDenseElementsFillHoles(ArrayObject
* arr
, NativeObject
* nobj
,
3354 // Ensure |arr| is an empty array with sufficient capacity.
3355 MOZ_ASSERT(arr
->getDenseInitializedLength() == 0);
3356 MOZ_ASSERT(arr
->getDenseCapacity() >= length
);
3357 MOZ_ASSERT(length
> 0);
3359 uint32_t count
= std::min(nobj
->getDenseInitializedLength(), length
);
3362 if (nobj
->denseElementsArePacked()) {
3363 // Copy all dense elements when no holes are present.
3364 arr
->initDenseElements(nobj
, 0, count
);
3366 arr
->setDenseInitializedLength(count
);
3368 // Handle each element separately to filter out holes.
3369 for (uint32_t i
= 0; i
< count
; i
++) {
3370 Value val
= nobj
->getDenseElement(i
);
3371 if (val
.isMagic(JS_ELEMENTS_HOLE
)) {
3372 val
= UndefinedValue();
3374 arr
->initDenseElement(i
, val
);
3379 // Fill trailing holes with undefined.
3380 if (count
< length
) {
3381 arr
->setDenseInitializedLength(length
);
3383 for (uint32_t i
= count
; i
< length
; i
++) {
3384 arr
->initDenseElement(i
, UndefinedValue());
3388 // Ensure |length| elements have been copied and no holes are present.
3389 MOZ_ASSERT(arr
->getDenseInitializedLength() == length
);
3390 MOZ_ASSERT(arr
->denseElementsArePacked());
3393 // https://github.com/tc39/proposal-change-array-by-copy
3394 // Array.prototype.toSpliced()
3395 static bool array_toSpliced(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3396 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "toSpliced");
3397 CallArgs args
= CallArgsFromVp(argc
, vp
);
3399 // Step 1. Let O be ? ToObject(this value).
3400 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
3405 // Step 2. Let len be ? LengthOfArrayLike(O).
3407 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
3412 // |actualStart| is the index after which elements will be deleted and/or
3413 // new elements will be added
3414 uint64_t actualStart
;
3415 if (!GetActualStart(cx
, args
.get(0), len
, &actualStart
)) {
3418 MOZ_ASSERT(actualStart
<= len
);
3420 // Step 7. Let insertCount be the number of elements in items.
3421 uint32_t insertCount
= GetItemCount(args
);
3424 // actualDeleteCount is the number of elements being deleted
3425 uint64_t actualDeleteCount
;
3426 if (!GetActualDeleteCount(cx
, args
, obj
, len
, actualStart
, insertCount
,
3427 &actualDeleteCount
)) {
3430 MOZ_ASSERT(actualStart
+ actualDeleteCount
<= len
);
3432 // Step 11. Let newLen be len + insertCount - actualDeleteCount.
3433 uint64_t newLen
= len
+ insertCount
- actualDeleteCount
;
3435 // Step 12 handled by GetActualDeleteCount().
3436 MOZ_ASSERT(newLen
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
3437 MOZ_ASSERT(actualStart
<= newLen
,
3438 "if |actualStart + actualDeleteCount <= len| and "
3439 "|newLen = len + insertCount - actualDeleteCount|, then "
3440 "|actualStart <= newLen|");
3442 // ArrayCreate, step 1.
3443 if (newLen
> UINT32_MAX
) {
3444 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3445 JSMSG_BAD_ARRAY_LENGTH
);
3449 // Step 13. Let A be ? ArrayCreate(𝔽(newLen)).
3450 Rooted
<ArrayObject
*> arr(cx
,
3451 NewDensePartlyAllocatedArray(cx
, uint32_t(newLen
)));
3456 // Steps 14-19 optimized for dense elements.
3457 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
)) {
3458 MOZ_ASSERT(len
<= UINT32_MAX
);
3459 MOZ_ASSERT(actualDeleteCount
<= UINT32_MAX
,
3460 "if |actualStart + actualDeleteCount <= len| and "
3461 "|len <= UINT32_MAX|, then |actualDeleteCount <= UINT32_MAX|");
3463 uint32_t length
= uint32_t(len
);
3464 uint32_t newLength
= uint32_t(newLen
);
3465 uint32_t start
= uint32_t(actualStart
);
3466 uint32_t deleteCount
= uint32_t(actualDeleteCount
);
3468 auto nobj
= obj
.as
<NativeObject
>();
3470 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, newLength
);
3474 arr
->setLength(newLength
);
3476 // Below code doesn't handle the case when the storage has to grow,
3477 // therefore the capacity must fit for at least |newLength| elements.
3478 MOZ_ASSERT(arr
->getDenseCapacity() >= newLength
);
3480 if (deleteCount
== 0 && insertCount
== 0) {
3481 // Copy the array when we don't have to remove or insert any elements.
3482 if (newLength
> 0) {
3483 CopyDenseElementsFillHoles(arr
, nobj
, newLength
);
3486 // Copy nobj[0..start] to arr[0..start].
3488 CopyDenseElementsFillHoles(arr
, nobj
, start
);
3491 // Insert |items| into arr[start..(start + insertCount)].
3492 if (insertCount
> 0) {
3493 auto items
= HandleValueArray::subarray(args
, 2, insertCount
);
3495 // Prefer |initDenseElements| because it's faster.
3496 if (arr
->getDenseInitializedLength() == 0) {
3497 arr
->initDenseElements(items
.begin(), items
.length());
3499 arr
->ensureDenseInitializedLength(start
, items
.length());
3500 arr
->copyDenseElements(start
, items
.begin(), items
.length());
3504 uint32_t fromIndex
= start
+ deleteCount
;
3505 uint32_t toIndex
= start
+ insertCount
;
3506 MOZ_ASSERT((length
- fromIndex
) == (newLength
- toIndex
),
3507 "Copies all remaining elements to the end");
3509 // Copy nobj[(start + deleteCount)..length] to
3510 // arr[(start + insertCount)..newLength].
3511 if (fromIndex
< length
) {
3512 uint32_t end
= std::min(length
, nobj
->getDenseInitializedLength());
3513 if (fromIndex
< end
) {
3514 uint32_t count
= end
- fromIndex
;
3515 if (nobj
->denseElementsArePacked()) {
3516 // Copy all dense elements when no holes are present.
3517 const Value
* src
= nobj
->getDenseElements() + fromIndex
;
3518 arr
->ensureDenseInitializedLength(toIndex
, count
);
3519 arr
->copyDenseElements(toIndex
, src
, count
);
3523 arr
->setDenseInitializedLength(toIndex
+ count
);
3525 // Handle each element separately to filter out holes.
3526 for (uint32_t i
= 0; i
< count
; i
++) {
3527 Value val
= nobj
->getDenseElement(fromIndex
++);
3528 if (val
.isMagic(JS_ELEMENTS_HOLE
)) {
3529 val
= UndefinedValue();
3531 arr
->initDenseElement(toIndex
++, val
);
3536 arr
->setDenseInitializedLength(newLength
);
3538 // Fill trailing holes with undefined.
3539 while (fromIndex
< length
) {
3540 arr
->initDenseElement(toIndex
++, UndefinedValue());
3545 MOZ_ASSERT(fromIndex
== length
);
3546 MOZ_ASSERT(toIndex
== newLength
);
3549 // Ensure the result array is packed and has the correct length.
3550 MOZ_ASSERT(IsPackedArray(arr
));
3551 MOZ_ASSERT(arr
->length() == newLength
);
3553 args
.rval().setObject(*arr
);
3557 // Copy everything before start
3559 // Step 14. Let i be 0.
3562 // Step 15. Let r be actualStart + actualDeleteCount.
3563 uint64_t r
= actualStart
+ actualDeleteCount
;
3565 // Step 16. Repeat while i < actualStart,
3566 RootedValue
iValue(cx
);
3567 while (i
< uint32_t(actualStart
)) {
3568 if (!CheckForInterrupt(cx
)) {
3572 // Skip Step 16.a. Let Pi be ! ToString(𝔽(i)).
3574 // Step 16.b. Let iValue be ? Get(O, Pi).
3575 if (!GetArrayElement(cx
, obj
, i
, &iValue
)) {
3579 // Step 16.c. Perform ! CreateDataPropertyOrThrow(A, Pi, iValue).
3580 if (!DefineArrayElement(cx
, arr
, i
, iValue
)) {
3584 // Step 16.d. Set i to i + 1.
3588 // Result array now contains all elements before start.
3591 if (insertCount
> 0) {
3592 HandleValueArray items
= HandleValueArray::subarray(args
, 2, insertCount
);
3594 // Fast-path to copy all items in one go.
3595 DenseElementResult result
=
3596 arr
->setOrExtendDenseElements(cx
, i
, items
.begin(), items
.length());
3597 if (result
== DenseElementResult::Failure
) {
3601 if (result
== DenseElementResult::Success
) {
3602 i
+= items
.length();
3604 MOZ_ASSERT(result
== DenseElementResult::Incomplete
);
3606 // Step 17. For each element E of items, do
3607 for (size_t j
= 0; j
< items
.length(); j
++) {
3608 if (!CheckForInterrupt(cx
)) {
3612 // Skip Step 17.a. Let Pi be ! ToString(𝔽(i)).
3614 // Step 17.b. Perform ! CreateDataPropertyOrThrow(A, Pi, E).
3615 if (!DefineArrayElement(cx
, arr
, i
, items
[j
])) {
3619 // Step 17.c. Set i to i + 1.
3625 // Copy items after new items
3626 // Step 18. Repeat, while i < newLen,
3627 RootedValue
fromValue(cx
);
3628 while (i
< uint32_t(newLen
)) {
3629 if (!CheckForInterrupt(cx
)) {
3633 // Skip Step 18.a. Let Pi be ! ToString(𝔽(i)).
3634 // Skip Step 18.b. Let from be ! ToString(𝔽(r)).
3636 // Step 18.c. Let fromValue be ? Get(O, from). */
3637 if (!GetArrayElement(cx
, obj
, r
, &fromValue
)) {
3641 // Step 18.d. Perform ! CreateDataPropertyOrThrow(A, Pi, fromValue).
3642 if (!DefineArrayElement(cx
, arr
, i
, fromValue
)) {
3646 // Step 18.e. Set i to i + 1.
3649 // Step 18.f. Set r to r + 1.
3653 // Step 19. Return A.
3654 args
.rval().setObject(*arr
);
3658 // https://github.com/tc39/proposal-change-array-by-copy
3659 // Array.prototype.with()
3660 static bool array_with(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3661 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "with");
3662 CallArgs args
= CallArgsFromVp(argc
, vp
);
3664 // Step 1. Let O be ? ToObject(this value).
3665 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
3670 // Step 2. Let len be ? LengthOfArrayLike(O).
3672 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
3676 // Step 3. Let relativeIndex be ? ToIntegerOrInfinity(index).
3677 double relativeIndex
;
3678 if (!ToInteger(cx
, args
.get(0), &relativeIndex
)) {
3679 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_INDEX
);
3683 // Step 4. If relativeIndex >= 0, let actualIndex be relativeIndex.
3684 double actualIndex
= relativeIndex
;
3685 if (actualIndex
< 0) {
3686 // Step 5. Else, let actualIndex be len + relativeIndex.
3687 actualIndex
= double(len
) + actualIndex
;
3690 // Step 6. If actualIndex >= len or actualIndex < 0, throw a RangeError
3692 if (actualIndex
< 0 || actualIndex
>= double(len
)) {
3693 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_INDEX
);
3697 // ArrayCreate, step 1.
3698 if (len
> UINT32_MAX
) {
3699 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3700 JSMSG_BAD_ARRAY_LENGTH
);
3703 uint32_t length
= uint32_t(len
);
3705 MOZ_ASSERT(length
> 0);
3706 MOZ_ASSERT(0 <= actualIndex
&& actualIndex
< UINT32_MAX
);
3708 // Steps 7-10 optimized for dense elements.
3709 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, length
)) {
3710 auto nobj
= obj
.as
<NativeObject
>();
3712 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, length
);
3716 arr
->setLength(length
);
3718 CopyDenseElementsFillHoles(arr
, nobj
, length
);
3720 // Replace the value at |actualIndex|.
3721 arr
->setDenseElement(uint32_t(actualIndex
), args
.get(1));
3723 // Ensure the result array is packed and has the correct length.
3724 MOZ_ASSERT(IsPackedArray(arr
));
3725 MOZ_ASSERT(arr
->length() == length
);
3727 args
.rval().setObject(*arr
);
3731 // Step 7. Let A be ? ArrayCreate(𝔽(len)).
3732 RootedObject
arr(cx
, NewDensePartlyAllocatedArray(cx
, length
));
3737 // Steps 8-9. Let k be 0; Repeat, while k < len,
3738 RootedValue
fromValue(cx
);
3739 for (uint32_t k
= 0; k
< length
; k
++) {
3740 if (!CheckForInterrupt(cx
)) {
3744 // Skip Step 9.a. Let Pk be ! ToString(𝔽(k)).
3746 // Step 9.b. If k is actualIndex, let fromValue be value.
3747 if (k
== uint32_t(actualIndex
)) {
3748 fromValue
= args
.get(1);
3750 // Step 9.c. Else, let fromValue be ? Get(O, 𝔽(k)).
3751 if (!GetArrayElement(cx
, obj
, k
, &fromValue
)) {
3756 // Step 9.d. Perform ! CreateDataPropertyOrThrow(A, 𝔽(k), fromValue).
3757 if (!DefineArrayElement(cx
, arr
, k
, fromValue
)) {
3762 // Step 10. Return A.
3763 args
.rval().setObject(*arr
);
3767 struct SortComparatorIndexes
{
3768 bool operator()(uint32_t a
, uint32_t b
, bool* lessOrEqualp
) {
3769 *lessOrEqualp
= (a
<= b
);
3774 // Returns all indexed properties in the range [begin, end) found on |obj| or
3775 // its proto chain. This function does not handle proxies, objects with
3776 // resolve/lookupProperty hooks or indexed getters, as those can introduce
3777 // new properties. In those cases, *success is set to |false|.
3778 static bool GetIndexedPropertiesInRange(JSContext
* cx
, HandleObject obj
,
3779 uint64_t begin
, uint64_t end
,
3780 Vector
<uint32_t>& indexes
,
3784 // TODO: Add IdIsIndex with support for large indices.
3785 if (end
> UINT32_MAX
) {
3788 MOZ_ASSERT(begin
<= UINT32_MAX
);
3790 // First, look for proxies or class hooks that can introduce extra
3792 JSObject
* pobj
= obj
;
3794 if (!pobj
->is
<NativeObject
>() || pobj
->getClass()->getResolve() ||
3795 pobj
->getOpsLookupProperty()) {
3798 } while ((pobj
= pobj
->staticPrototype()));
3800 // Collect indexed property names.
3803 // Append dense elements.
3804 NativeObject
* nativeObj
= &pobj
->as
<NativeObject
>();
3805 uint32_t initLen
= nativeObj
->getDenseInitializedLength();
3806 for (uint32_t i
= begin
; i
< initLen
&& i
< end
; i
++) {
3807 if (nativeObj
->getDenseElement(i
).isMagic(JS_ELEMENTS_HOLE
)) {
3810 if (!indexes
.append(i
)) {
3815 // Append typed array elements.
3816 if (nativeObj
->is
<TypedArrayObject
>()) {
3817 size_t len
= nativeObj
->as
<TypedArrayObject
>().length().valueOr(0);
3818 for (uint32_t i
= begin
; i
< len
&& i
< end
; i
++) {
3819 if (!indexes
.append(i
)) {
3825 // Append sparse elements.
3826 if (nativeObj
->isIndexed()) {
3827 ShapePropertyIter
<NoGC
> iter(nativeObj
->shape());
3828 for (; !iter
.done(); iter
++) {
3829 jsid id
= iter
->key();
3831 if (!IdIsIndex(id
, &i
)) {
3835 if (!(begin
<= i
&& i
< end
)) {
3839 // Watch out for getters, they can add new properties.
3840 if (!iter
->isDataProperty()) {
3844 if (!indexes
.append(i
)) {
3849 } while ((pobj
= pobj
->staticPrototype()));
3851 // Sort the indexes.
3852 Vector
<uint32_t> tmp(cx
);
3853 size_t n
= indexes
.length();
3854 if (!tmp
.resize(n
)) {
3857 if (!MergeSort(indexes
.begin(), n
, tmp
.begin(), SortComparatorIndexes())) {
3861 // Remove duplicates.
3862 if (!indexes
.empty()) {
3864 for (size_t i
= 1, len
= indexes
.length(); i
< len
; i
++) {
3865 uint32_t elem
= indexes
[i
];
3866 if (indexes
[last
] != elem
) {
3868 indexes
[last
] = elem
;
3871 if (!indexes
.resize(last
+ 1)) {
3880 static bool SliceSparse(JSContext
* cx
, HandleObject obj
, uint64_t begin
,
3881 uint64_t end
, Handle
<ArrayObject
*> result
) {
3882 MOZ_ASSERT(begin
<= end
);
3884 Vector
<uint32_t> indexes(cx
);
3886 if (!GetIndexedPropertiesInRange(cx
, obj
, begin
, end
, indexes
, &success
)) {
3891 return CopyArrayElements(cx
, obj
, begin
, end
- begin
, result
);
3894 MOZ_ASSERT(end
<= UINT32_MAX
,
3895 "indices larger than UINT32_MAX should be rejected by "
3896 "GetIndexedPropertiesInRange");
3898 RootedValue
value(cx
);
3899 for (uint32_t index
: indexes
) {
3900 MOZ_ASSERT(begin
<= index
&& index
< end
);
3903 if (!HasAndGetElement(cx
, obj
, index
, &hole
, &value
)) {
3908 !DefineDataElement(cx
, result
, index
- uint32_t(begin
), value
)) {
3916 static JSObject
* SliceArguments(JSContext
* cx
, Handle
<ArgumentsObject
*> argsobj
,
3917 uint32_t begin
, uint32_t count
) {
3918 MOZ_ASSERT(!argsobj
->hasOverriddenLength() &&
3919 !argsobj
->hasOverriddenElement());
3920 MOZ_ASSERT(begin
+ count
<= argsobj
->initialLength());
3922 ArrayObject
* result
= NewDenseFullyAllocatedArray(cx
, count
);
3926 result
->setDenseInitializedLength(count
);
3928 for (uint32_t index
= 0; index
< count
; index
++) {
3929 const Value
& v
= argsobj
->element(begin
+ index
);
3930 result
->initDenseElement(index
, v
);
3935 template <typename T
, typename ArrayLength
>
3936 static inline ArrayLength
NormalizeSliceTerm(T value
, ArrayLength length
) {
3942 } else if (double(value
) > double(length
)) {
3945 return ArrayLength(value
);
3948 static bool ArraySliceOrdinary(JSContext
* cx
, HandleObject obj
, uint64_t begin
,
3949 uint64_t end
, MutableHandleValue rval
) {
3954 if ((end
- begin
) > UINT32_MAX
) {
3955 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3956 JSMSG_BAD_ARRAY_LENGTH
);
3959 uint32_t count
= uint32_t(end
- begin
);
3961 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, end
)) {
3962 MOZ_ASSERT(begin
<= UINT32_MAX
,
3963 "if end <= UINT32_MAX, then begin <= UINT32_MAX");
3964 JSObject
* narr
= CopyDenseArrayElements(cx
, obj
.as
<NativeObject
>(),
3965 uint32_t(begin
), count
);
3970 rval
.setObject(*narr
);
3974 if (obj
->is
<ArgumentsObject
>()) {
3975 Handle
<ArgumentsObject
*> argsobj
= obj
.as
<ArgumentsObject
>();
3976 if (!argsobj
->hasOverriddenLength() && !argsobj
->hasOverriddenElement()) {
3977 MOZ_ASSERT(begin
<= UINT32_MAX
, "begin is limited by |argsobj|'s length");
3978 JSObject
* narr
= SliceArguments(cx
, argsobj
, uint32_t(begin
), count
);
3983 rval
.setObject(*narr
);
3988 Rooted
<ArrayObject
*> narr(cx
, NewDensePartlyAllocatedArray(cx
, count
));
3993 if (end
<= UINT32_MAX
) {
3994 if (js::GetElementsOp op
= obj
->getOpsGetElements()) {
3995 ElementAdder
adder(cx
, narr
, count
,
3996 ElementAdder::CheckHasElemPreserveHoles
);
3997 if (!op(cx
, obj
, uint32_t(begin
), uint32_t(end
), &adder
)) {
4001 rval
.setObject(*narr
);
4006 if (obj
->is
<NativeObject
>() && obj
->as
<NativeObject
>().isIndexed() &&
4008 if (!SliceSparse(cx
, obj
, begin
, end
, narr
)) {
4012 if (!CopyArrayElements(cx
, obj
, begin
, count
, narr
)) {
4017 rval
.setObject(*narr
);
4021 /* ES 2016 draft Mar 25, 2016 22.1.3.23. */
4022 static bool array_slice(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4023 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "slice");
4024 CallArgs args
= CallArgsFromVp(argc
, vp
);
4027 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4034 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
4039 uint64_t final
= length
;
4040 if (args
.length() > 0) {
4043 if (!ToInteger(cx
, args
[0], &d
)) {
4048 k
= NormalizeSliceTerm(d
, length
);
4050 if (args
.hasDefined(1)) {
4052 if (!ToInteger(cx
, args
[1], &d
)) {
4057 final
= NormalizeSliceTerm(d
, length
);
4061 if (IsArraySpecies(cx
, obj
)) {
4062 /* Steps 7-12: Optimized for ordinary array. */
4063 return ArraySliceOrdinary(cx
, obj
, k
, final
, args
.rval());
4067 uint64_t count
= final
> k
? final
- k
: 0;
4070 RootedObject
arr(cx
);
4071 if (!ArraySpeciesCreate(cx
, obj
, count
, &arr
)) {
4079 RootedValue
kValue(cx
);
4081 if (!CheckForInterrupt(cx
)) {
4085 /* Steps 10.a-b, and 10.c.i. */
4087 if (!HasAndGetElement(cx
, obj
, k
, &kNotPresent
, &kValue
)) {
4093 /* Steps 10.c.ii. */
4094 if (!DefineArrayElement(cx
, arr
, n
, kValue
)) {
4106 if (!SetLengthProperty(cx
, arr
, n
)) {
4111 args
.rval().setObject(*arr
);
4115 static bool ArraySliceDenseKernel(JSContext
* cx
, ArrayObject
* arr
,
4116 int32_t beginArg
, int32_t endArg
,
4117 ArrayObject
* result
) {
4118 uint32_t length
= arr
->length();
4120 uint32_t begin
= NormalizeSliceTerm(beginArg
, length
);
4121 uint32_t end
= NormalizeSliceTerm(endArg
, length
);
4127 uint32_t count
= end
- begin
;
4128 size_t initlen
= arr
->getDenseInitializedLength();
4129 if (initlen
> begin
) {
4130 uint32_t newlength
= std::min
<uint32_t>(initlen
- begin
, count
);
4131 if (newlength
> 0) {
4132 if (!result
->ensureElements(cx
, newlength
)) {
4135 result
->initDenseElements(arr
, begin
, newlength
);
4139 MOZ_ASSERT(count
>= result
->length());
4140 result
->setLength(count
);
4145 JSObject
* js::ArraySliceDense(JSContext
* cx
, HandleObject obj
, int32_t begin
,
4146 int32_t end
, HandleObject result
) {
4147 MOZ_ASSERT(IsPackedArray(obj
));
4149 if (result
&& IsArraySpecies(cx
, obj
)) {
4150 if (!ArraySliceDenseKernel(cx
, &obj
->as
<ArrayObject
>(), begin
, end
,
4151 &result
->as
<ArrayObject
>())) {
4157 // Slower path if the JIT wasn't able to allocate an object inline.
4158 JS::RootedValueArray
<4> argv(cx
);
4159 argv
[0].setUndefined();
4160 argv
[1].setObject(*obj
);
4161 argv
[2].setInt32(begin
);
4162 argv
[3].setInt32(end
);
4163 if (!array_slice(cx
, 2, argv
.begin())) {
4166 return &argv
[0].toObject();
4169 JSObject
* js::ArgumentsSliceDense(JSContext
* cx
, HandleObject obj
,
4170 int32_t begin
, int32_t end
,
4171 HandleObject result
) {
4172 MOZ_ASSERT(obj
->is
<ArgumentsObject
>());
4173 MOZ_ASSERT(IsArraySpecies(cx
, obj
));
4175 Handle
<ArgumentsObject
*> argsobj
= obj
.as
<ArgumentsObject
>();
4176 MOZ_ASSERT(!argsobj
->hasOverriddenLength());
4177 MOZ_ASSERT(!argsobj
->hasOverriddenElement());
4179 uint32_t length
= argsobj
->initialLength();
4180 uint32_t actualBegin
= NormalizeSliceTerm(begin
, length
);
4181 uint32_t actualEnd
= NormalizeSliceTerm(end
, length
);
4183 if (actualBegin
> actualEnd
) {
4184 actualBegin
= actualEnd
;
4186 uint32_t count
= actualEnd
- actualBegin
;
4189 Handle
<ArrayObject
*> resArray
= result
.as
<ArrayObject
>();
4190 MOZ_ASSERT(resArray
->getDenseInitializedLength() == 0);
4191 MOZ_ASSERT(resArray
->length() == 0);
4194 if (!resArray
->ensureElements(cx
, count
)) {
4197 resArray
->setDenseInitializedLength(count
);
4198 resArray
->setLength(count
);
4200 for (uint32_t index
= 0; index
< count
; index
++) {
4201 const Value
& v
= argsobj
->element(actualBegin
+ index
);
4202 resArray
->initDenseElement(index
, v
);
4209 // Slower path if the JIT wasn't able to allocate an object inline.
4210 return SliceArguments(cx
, argsobj
, actualBegin
, count
);
4213 static bool array_isArray(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4214 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array", "isArray");
4215 CallArgs args
= CallArgsFromVp(argc
, vp
);
4217 bool isArray
= false;
4218 if (args
.get(0).isObject()) {
4219 RootedObject
obj(cx
, &args
[0].toObject());
4220 if (!IsArray(cx
, obj
, &isArray
)) {
4224 args
.rval().setBoolean(isArray
);
4228 static bool ArrayFromCallArgs(JSContext
* cx
, CallArgs
& args
,
4229 HandleObject proto
= nullptr) {
4231 NewDenseCopiedArrayWithProto(cx
, args
.length(), args
.array(), proto
);
4236 args
.rval().setObject(*obj
);
4240 static bool array_of(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4241 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array", "of");
4242 CallArgs args
= CallArgsFromVp(argc
, vp
);
4244 bool isArrayConstructor
=
4245 IsArrayConstructor(args
.thisv()) &&
4246 args
.thisv().toObject().nonCCWRealm() == cx
->realm();
4248 if (isArrayConstructor
|| !IsConstructor(args
.thisv())) {
4249 // isArrayConstructor will usually be true in practice. This is the most
4251 return ArrayFromCallArgs(cx
, args
);
4254 if (!ReportUsageCounter(cx
, nullptr, SUBCLASSING_ARRAY
,
4255 SUBCLASSING_TYPE_II
)) {
4260 RootedObject
obj(cx
);
4262 FixedConstructArgs
<1> cargs(cx
);
4264 cargs
[0].setNumber(args
.length());
4266 if (!Construct(cx
, args
.thisv(), cargs
, args
.thisv(), &obj
)) {
4272 for (unsigned k
= 0; k
< args
.length(); k
++) {
4273 if (!DefineDataElement(cx
, obj
, k
, args
[k
])) {
4279 if (!SetLengthProperty(cx
, obj
, args
.length())) {
4284 args
.rval().setObject(*obj
);
4288 static const JSJitInfo array_splice_info
= {
4289 {(JSJitGetterOp
)array_splice_noRetVal
},
4292 JSJitInfo::IgnoresReturnValueNative
,
4293 JSJitInfo::AliasEverything
,
4294 JSVAL_TYPE_UNDEFINED
,
4297 enum class SearchKind
{
4298 // Specializes SearchElementDense for Array.prototype.indexOf/lastIndexOf.
4299 // This means hole values are ignored and StrictlyEqual semantics are used.
4301 // Specializes SearchElementDense for Array.prototype.includes.
4302 // This means hole values are treated as |undefined| and SameValueZero
4303 // semantics are used.
4307 template <SearchKind Kind
, typename Iter
>
4308 static bool SearchElementDense(JSContext
* cx
, HandleValue val
, Iter iterator
,
4309 MutableHandleValue rval
) {
4310 // We assume here and in the iterator lambdas that nothing can trigger GC or
4311 // move dense elements.
4312 AutoCheckCannotGC nogc
;
4314 // Fast path for string values.
4315 if (val
.isString()) {
4316 JSLinearString
* str
= val
.toString()->ensureLinear(cx
);
4320 const uint32_t strLen
= str
->length();
4321 auto cmp
= [str
, strLen
](JSContext
* cx
, const Value
& element
, bool* equal
) {
4322 if (!element
.isString() || element
.toString()->length() != strLen
) {
4326 JSLinearString
* s
= element
.toString()->ensureLinear(cx
);
4330 *equal
= EqualStrings(str
, s
);
4333 return iterator(cx
, cmp
, rval
);
4336 // Fast path for numbers.
4337 if (val
.isNumber()) {
4338 double dval
= val
.toNumber();
4339 // For |includes|, two NaN values are considered equal, so we use a
4340 // different implementation for NaN.
4341 if (Kind
== SearchKind::Includes
&& std::isnan(dval
)) {
4342 auto cmp
= [](JSContext
*, const Value
& element
, bool* equal
) {
4343 *equal
= (element
.isDouble() && std::isnan(element
.toDouble()));
4346 return iterator(cx
, cmp
, rval
);
4348 auto cmp
= [dval
](JSContext
*, const Value
& element
, bool* equal
) {
4349 *equal
= (element
.isNumber() && element
.toNumber() == dval
);
4352 return iterator(cx
, cmp
, rval
);
4355 // Fast path for values where we can use a simple bitwise comparison.
4356 if (CanUseBitwiseCompareForStrictlyEqual(val
)) {
4357 // For |includes| we need to treat hole values as |undefined| so we use a
4358 // different path if searching for |undefined|.
4359 if (Kind
== SearchKind::Includes
&& val
.isUndefined()) {
4360 auto cmp
= [](JSContext
*, const Value
& element
, bool* equal
) {
4361 *equal
= (element
.isUndefined() || element
.isMagic(JS_ELEMENTS_HOLE
));
4364 return iterator(cx
, cmp
, rval
);
4366 uint64_t bits
= val
.asRawBits();
4367 auto cmp
= [bits
](JSContext
*, const Value
& element
, bool* equal
) {
4368 *equal
= (bits
== element
.asRawBits());
4371 return iterator(cx
, cmp
, rval
);
4374 MOZ_ASSERT(val
.isBigInt() ||
4375 IF_RECORD_TUPLE(val
.isExtendedPrimitive(), false));
4377 // Generic implementation for the remaining types.
4378 RootedValue
elementRoot(cx
);
4379 auto cmp
= [val
, &elementRoot
](JSContext
* cx
, const Value
& element
,
4381 if (MOZ_UNLIKELY(element
.isMagic(JS_ELEMENTS_HOLE
))) {
4382 // |includes| treats holes as |undefined|, but |undefined| is already
4383 // handled above. For |indexOf| we have to ignore holes.
4387 // Note: |includes| uses SameValueZero, but that checks for NaN and then
4388 // calls StrictlyEqual. Since we already handled NaN above, we can call
4389 // StrictlyEqual directly.
4390 MOZ_ASSERT(!val
.isNumber());
4391 elementRoot
= element
;
4392 return StrictlyEqual(cx
, val
, elementRoot
, equal
);
4394 return iterator(cx
, cmp
, rval
);
4397 // ES2020 draft rev dc1e21c454bd316810be1c0e7af0131a2d7f38e9
4398 // 22.1.3.14 Array.prototype.indexOf ( searchElement [ , fromIndex ] )
4399 bool js::array_indexOf(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4400 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "indexOf");
4401 CallArgs args
= CallArgsFromVp(argc
, vp
);
4404 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4411 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
4417 args
.rval().setInt32(-1);
4423 if (args
.length() > 1) {
4425 if (!ToInteger(cx
, args
[1], &n
)) {
4430 if (n
>= double(len
)) {
4431 args
.rval().setInt32(-1);
4439 double d
= double(len
) + n
;
4446 MOZ_ASSERT(k
< len
);
4448 HandleValue searchElement
= args
.get(0);
4450 // Steps 9 and 10 optimized for dense elements.
4451 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
)) {
4452 MOZ_ASSERT(len
<= UINT32_MAX
);
4454 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
4455 uint32_t start
= uint32_t(k
);
4457 std::min(nobj
->getDenseInitializedLength(), uint32_t(len
));
4458 const Value
* elements
= nobj
->getDenseElements();
4460 if (CanUseBitwiseCompareForStrictlyEqual(searchElement
) && length
> start
) {
4461 const uint64_t* elementsAsBits
=
4462 reinterpret_cast<const uint64_t*>(elements
);
4463 const uint64_t* res
= SIMD::memchr64(
4464 elementsAsBits
+ start
, searchElement
.asRawBits(), length
- start
);
4466 args
.rval().setInt32(static_cast<int32_t>(res
- elementsAsBits
));
4468 args
.rval().setInt32(-1);
4473 auto iterator
= [elements
, start
, length
](JSContext
* cx
, auto cmp
,
4474 MutableHandleValue rval
) {
4475 static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT
<= INT32_MAX
,
4476 "code assumes dense index fits in Int32Value");
4477 for (uint32_t i
= start
; i
< length
; i
++) {
4479 if (MOZ_UNLIKELY(!cmp(cx
, elements
[i
], &equal
))) {
4483 rval
.setInt32(int32_t(i
));
4490 return SearchElementDense
<SearchKind::IndexOf
>(cx
, searchElement
, iterator
,
4496 for (; k
< len
; k
++) {
4497 if (!CheckForInterrupt(cx
)) {
4502 if (!HasAndGetElement(cx
, obj
, k
, &hole
, &v
)) {
4510 if (!StrictlyEqual(cx
, v
, searchElement
, &equal
)) {
4514 args
.rval().setNumber(k
);
4520 args
.rval().setInt32(-1);
4524 // ES2020 draft rev dc1e21c454bd316810be1c0e7af0131a2d7f38e9
4525 // 22.1.3.17 Array.prototype.lastIndexOf ( searchElement [ , fromIndex ] )
4526 bool js::array_lastIndexOf(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4527 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "lastIndexOf");
4528 CallArgs args
= CallArgsFromVp(argc
, vp
);
4531 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4538 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
4544 args
.rval().setInt32(-1);
4549 uint64_t k
= len
- 1;
4550 if (args
.length() > 1) {
4552 if (!ToInteger(cx
, args
[1], &n
)) {
4558 double d
= double(len
) + n
;
4560 args
.rval().setInt32(-1);
4564 } else if (n
< double(k
)) {
4569 MOZ_ASSERT(k
< len
);
4571 HandleValue searchElement
= args
.get(0);
4573 // Steps 7 and 8 optimized for dense elements.
4574 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, k
+ 1)) {
4575 MOZ_ASSERT(k
<= UINT32_MAX
);
4577 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
4578 uint32_t initLen
= nobj
->getDenseInitializedLength();
4580 args
.rval().setInt32(-1);
4584 uint32_t end
= std::min(uint32_t(k
), initLen
- 1);
4585 const Value
* elements
= nobj
->getDenseElements();
4587 auto iterator
= [elements
, end
](JSContext
* cx
, auto cmp
,
4588 MutableHandleValue rval
) {
4589 static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT
<= INT32_MAX
,
4590 "code assumes dense index fits in int32_t");
4591 for (int32_t i
= int32_t(end
); i
>= 0; i
--) {
4593 if (MOZ_UNLIKELY(!cmp(cx
, elements
[i
], &equal
))) {
4597 rval
.setInt32(int32_t(i
));
4604 return SearchElementDense
<SearchKind::IndexOf
>(cx
, searchElement
, iterator
,
4610 for (int64_t i
= int64_t(k
); i
>= 0; i
--) {
4611 if (!CheckForInterrupt(cx
)) {
4616 if (!HasAndGetElement(cx
, obj
, uint64_t(i
), &hole
, &v
)) {
4624 if (!StrictlyEqual(cx
, v
, searchElement
, &equal
)) {
4628 args
.rval().setNumber(uint64_t(i
));
4634 args
.rval().setInt32(-1);
4638 // ES2020 draft rev dc1e21c454bd316810be1c0e7af0131a2d7f38e9
4639 // 22.1.3.13 Array.prototype.includes ( searchElement [ , fromIndex ] )
4640 bool js::array_includes(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4641 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "includes");
4642 CallArgs args
= CallArgsFromVp(argc
, vp
);
4645 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4652 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
4658 args
.rval().setBoolean(false);
4664 if (args
.length() > 1) {
4666 if (!ToInteger(cx
, args
[1], &n
)) {
4670 if (n
>= double(len
)) {
4671 args
.rval().setBoolean(false);
4679 double d
= double(len
) + n
;
4686 MOZ_ASSERT(k
< len
);
4688 HandleValue searchElement
= args
.get(0);
4690 // Steps 8 and 9 optimized for dense elements.
4691 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
)) {
4692 MOZ_ASSERT(len
<= UINT32_MAX
);
4694 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
4695 uint32_t start
= uint32_t(k
);
4697 std::min(nobj
->getDenseInitializedLength(), uint32_t(len
));
4698 const Value
* elements
= nobj
->getDenseElements();
4700 // Trailing holes are treated as |undefined|.
4701 if (uint32_t(len
) > length
&& searchElement
.isUndefined()) {
4702 // |undefined| is strictly equal only to |undefined|.
4703 args
.rval().setBoolean(true);
4707 // For |includes| we need to treat hole values as |undefined| so we use a
4708 // different path if searching for |undefined|.
4709 if (CanUseBitwiseCompareForStrictlyEqual(searchElement
) &&
4710 !searchElement
.isUndefined() && length
> start
) {
4711 if (SIMD::memchr64(reinterpret_cast<const uint64_t*>(elements
) + start
,
4712 searchElement
.asRawBits(), length
- start
)) {
4713 args
.rval().setBoolean(true);
4715 args
.rval().setBoolean(false);
4720 auto iterator
= [elements
, start
, length
](JSContext
* cx
, auto cmp
,
4721 MutableHandleValue rval
) {
4722 for (uint32_t i
= start
; i
< length
; i
++) {
4724 if (MOZ_UNLIKELY(!cmp(cx
, elements
[i
], &equal
))) {
4728 rval
.setBoolean(true);
4732 rval
.setBoolean(false);
4735 return SearchElementDense
<SearchKind::Includes
>(cx
, searchElement
, iterator
,
4741 for (; k
< len
; k
++) {
4742 if (!CheckForInterrupt(cx
)) {
4746 if (!GetArrayElement(cx
, obj
, k
, &v
)) {
4751 if (!SameValueZero(cx
, v
, searchElement
, &equal
)) {
4755 args
.rval().setBoolean(true);
4761 args
.rval().setBoolean(false);
4765 // ES2024 draft 23.1.3.2.1 IsConcatSpreadable
4766 static bool IsConcatSpreadable(JSContext
* cx
, HandleValue v
, bool* spreadable
) {
4768 if (!v
.isObject()) {
4769 *spreadable
= false;
4774 JS::Symbol
* sym
= cx
->wellKnownSymbols().isConcatSpreadable
;
4777 MaybeHasInterestingSymbolProperty(cx
, &v
.toObject(), sym
, &holder
))) {
4778 RootedValue
res(cx
);
4779 RootedObject
obj(cx
, holder
);
4780 Rooted
<PropertyKey
> key(cx
, PropertyKey::Symbol(sym
));
4781 if (!GetProperty(cx
, obj
, v
, key
, &res
)) {
4785 if (!res
.isUndefined()) {
4786 *spreadable
= ToBoolean(res
);
4792 if (MOZ_LIKELY(v
.toObject().is
<ArrayObject
>())) {
4796 RootedObject
obj(cx
, &v
.toObject());
4798 if (!JS::IsArray(cx
, obj
, &isArray
)) {
4801 *spreadable
= isArray
;
4805 // Returns true if the object may have an @@isConcatSpreadable property.
4806 static bool MaybeHasIsConcatSpreadable(JSContext
* cx
, JSObject
* obj
) {
4807 JS::Symbol
* sym
= cx
->wellKnownSymbols().isConcatSpreadable
;
4809 return MaybeHasInterestingSymbolProperty(cx
, obj
, sym
, &holder
);
4812 static bool TryOptimizePackedArrayConcat(JSContext
* cx
, CallArgs
& args
,
4813 Handle
<JSObject
*> obj
,
4815 // Fast path for the following cases:
4817 // (1) packedArray.concat(): copy the array's elements.
4818 // (2) packedArray.concat(packedArray): concatenate two packed arrays.
4819 // (3) packedArray.concat(value): copy and append a single non-array value.
4821 // These cases account for almost all calls to Array.prototype.concat in
4826 if (args
.length() > 1) {
4830 // The `this` object must be a packed array without @@isConcatSpreadable.
4831 // @@isConcatSpreadable is uncommon and requires a property lookup and more
4832 // complicated code, so we let the slow path handle it.
4833 if (!IsPackedArray(obj
)) {
4836 if (MaybeHasIsConcatSpreadable(cx
, obj
)) {
4840 Handle
<ArrayObject
*> thisArr
= obj
.as
<ArrayObject
>();
4841 uint32_t thisLen
= thisArr
->length();
4843 if (args
.length() == 0) {
4844 // Case (1). Copy the packed array.
4845 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, thisLen
);
4849 arr
->initDenseElements(thisArr
->getDenseElements(), thisLen
);
4850 args
.rval().setObject(*arr
);
4855 MOZ_ASSERT(args
.length() == 1);
4857 // If the argument is an object, it must not have an @@isConcatSpreadable
4859 if (args
[0].isObject() &&
4860 MaybeHasIsConcatSpreadable(cx
, &args
[0].toObject())) {
4864 MOZ_ASSERT_IF(args
[0].isObject(), args
[0].toObject().is
<NativeObject
>());
4866 // Case (3). Copy and append a single value if the argument is not an array.
4867 if (!args
[0].isObject() || !args
[0].toObject().is
<ArrayObject
>()) {
4868 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, thisLen
+ 1);
4872 arr
->initDenseElements(thisArr
->getDenseElements(), thisLen
);
4874 arr
->ensureDenseInitializedLength(thisLen
, 1);
4875 arr
->initDenseElement(thisLen
, args
[0]);
4877 args
.rval().setObject(*arr
);
4882 // Case (2). Concatenate two packed arrays.
4883 if (!IsPackedArray(&args
[0].toObject())) {
4887 uint32_t argLen
= args
[0].toObject().as
<ArrayObject
>().length();
4889 // Compute the array length. This can't overflow because both arrays are
4891 static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT
< INT32_MAX
);
4892 MOZ_ASSERT(thisLen
<= NativeObject::MAX_DENSE_ELEMENTS_COUNT
);
4893 MOZ_ASSERT(argLen
<= NativeObject::MAX_DENSE_ELEMENTS_COUNT
);
4894 uint32_t totalLen
= thisLen
+ argLen
;
4896 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, totalLen
);
4900 arr
->initDenseElements(thisArr
->getDenseElements(), thisLen
);
4902 ArrayObject
* argArr
= &args
[0].toObject().as
<ArrayObject
>();
4903 arr
->ensureDenseInitializedLength(thisLen
, argLen
);
4904 arr
->initDenseElementRange(thisLen
, argArr
, argLen
);
4906 args
.rval().setObject(*arr
);
4911 static bool array_concat(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4912 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "concat");
4913 CallArgs args
= CallArgsFromVp(argc
, vp
);
4916 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4921 bool isArraySpecies
= IsArraySpecies(cx
, obj
);
4923 // Fast path for the most common cases.
4924 if (isArraySpecies
) {
4926 if (!TryOptimizePackedArrayConcat(cx
, args
, obj
, &optimized
)) {
4935 RootedObject
arr(cx
);
4936 if (isArraySpecies
) {
4937 arr
= NewDenseEmptyArray(cx
);
4942 if (!ArraySpeciesCreate(cx
, obj
, 0, &arr
)) {
4950 // Step 4 (handled implicitly with nextArg and CallArgs).
4951 uint32_t nextArg
= 0;
4954 RootedValue
v(cx
, ObjectValue(*obj
));
4958 if (!IsConcatSpreadable(cx
, v
, &spreadable
)) {
4964 obj
= &v
.toObject();
4966 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
4971 if (n
+ len
> uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
) - 1) {
4972 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
4973 JSMSG_TOO_LONG_ARRAY
);
4982 // Try a fast path for copying dense elements directly.
4983 bool optimized
= false;
4984 if (len
> 0 && isArraySpecies
&&
4985 CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
) &&
4986 n
+ len
<= NativeObject::MAX_DENSE_ELEMENTS_COUNT
) {
4987 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
4988 ArrayObject
* resArr
= &arr
->as
<ArrayObject
>();
4990 std::min(uint32_t(len
), nobj
->getDenseInitializedLength());
4992 DenseElementResult res
= resArr
->ensureDenseElements(cx
, n
, count
);
4993 if (res
== DenseElementResult::Failure
) {
4996 if (res
== DenseElementResult::Success
) {
4997 resArr
->initDenseElementRange(n
, nobj
, count
);
5001 MOZ_ASSERT(res
== DenseElementResult::Incomplete
);
5008 if (!CheckForInterrupt(cx
)) {
5014 if (!HasAndGetElement(cx
, obj
, k
, &hole
, &v
)) {
5019 if (!DefineArrayElement(cx
, arr
, n
, v
)) {
5033 if (n
>= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
) - 1) {
5034 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5035 JSMSG_TOO_LONG_ARRAY
);
5040 if (!DefineArrayElement(cx
, arr
, n
, v
)) {
5048 // Move on to the next argument.
5049 if (nextArg
== args
.length()) {
5057 if (!SetLengthProperty(cx
, arr
, n
)) {
5062 args
.rval().setObject(*arr
);
5066 static const JSFunctionSpec array_methods
[] = {
5067 JS_FN("toSource", array_toSource
, 0, 0),
5068 JS_SELF_HOSTED_FN("toString", "ArrayToString", 0, 0),
5069 JS_FN("toLocaleString", array_toLocaleString
, 0, 0),
5071 /* Perl-ish methods. */
5072 JS_INLINABLE_FN("join", array_join
, 1, 0, ArrayJoin
),
5073 JS_FN("reverse", array_reverse
, 0, 0),
5074 JS_TRAMPOLINE_FN("sort", array_sort
, 1, 0, ArraySort
),
5075 JS_INLINABLE_FN("push", array_push
, 1, 0, ArrayPush
),
5076 JS_INLINABLE_FN("pop", array_pop
, 0, 0, ArrayPop
),
5077 JS_INLINABLE_FN("shift", array_shift
, 0, 0, ArrayShift
),
5078 JS_FN("unshift", array_unshift
, 1, 0),
5079 JS_FNINFO("splice", array_splice
, &array_splice_info
, 2, 0),
5081 /* Pythonic sequence methods. */
5082 JS_FN("concat", array_concat
, 1, 0),
5083 JS_INLINABLE_FN("slice", array_slice
, 2, 0, ArraySlice
),
5085 JS_FN("lastIndexOf", array_lastIndexOf
, 1, 0),
5086 JS_FN("indexOf", array_indexOf
, 1, 0),
5087 JS_SELF_HOSTED_FN("forEach", "ArrayForEach", 1, 0),
5088 JS_SELF_HOSTED_FN("map", "ArrayMap", 1, 0),
5089 JS_SELF_HOSTED_FN("filter", "ArrayFilter", 1, 0),
5090 JS_SELF_HOSTED_FN("reduce", "ArrayReduce", 1, 0),
5091 JS_SELF_HOSTED_FN("reduceRight", "ArrayReduceRight", 1, 0),
5092 JS_SELF_HOSTED_FN("some", "ArraySome", 1, 0),
5093 JS_SELF_HOSTED_FN("every", "ArrayEvery", 1, 0),
5096 JS_SELF_HOSTED_FN("find", "ArrayFind", 1, 0),
5097 JS_SELF_HOSTED_FN("findIndex", "ArrayFindIndex", 1, 0),
5098 JS_SELF_HOSTED_FN("copyWithin", "ArrayCopyWithin", 3, 0),
5100 JS_SELF_HOSTED_FN("fill", "ArrayFill", 3, 0),
5102 JS_SELF_HOSTED_SYM_FN(iterator
, "$ArrayValues", 0, 0),
5103 JS_SELF_HOSTED_FN("entries", "ArrayEntries", 0, 0),
5104 JS_SELF_HOSTED_FN("keys", "ArrayKeys", 0, 0),
5105 JS_SELF_HOSTED_FN("values", "$ArrayValues", 0, 0),
5108 JS_FN("includes", array_includes
, 1, 0),
5111 JS_SELF_HOSTED_FN("flatMap", "ArrayFlatMap", 1, 0),
5112 JS_SELF_HOSTED_FN("flat", "ArrayFlat", 0, 0),
5115 JS_SELF_HOSTED_FN("at", "ArrayAt", 1, 0),
5116 JS_SELF_HOSTED_FN("findLast", "ArrayFindLast", 1, 0),
5117 JS_SELF_HOSTED_FN("findLastIndex", "ArrayFindLastIndex", 1, 0),
5119 JS_SELF_HOSTED_FN("toReversed", "ArrayToReversed", 0, 0),
5120 JS_SELF_HOSTED_FN("toSorted", "ArrayToSorted", 1, 0),
5121 JS_FN("toSpliced", array_toSpliced
, 2, 0), JS_FN("with", array_with
, 2, 0),
5125 static const JSFunctionSpec array_static_methods
[] = {
5126 JS_INLINABLE_FN("isArray", array_isArray
, 1, 0, ArrayIsArray
),
5127 JS_SELF_HOSTED_FN("from", "ArrayFrom", 3, 0),
5128 JS_SELF_HOSTED_FN("fromAsync", "ArrayFromAsync", 3, 0),
5129 JS_FN("of", array_of
, 0, 0),
5133 const JSPropertySpec array_static_props
[] = {
5134 JS_SELF_HOSTED_SYM_GET(species
, "$ArraySpecies", 0), JS_PS_END
};
5136 static inline bool ArrayConstructorImpl(JSContext
* cx
, CallArgs
& args
,
5137 bool isConstructor
) {
5138 RootedObject
proto(cx
);
5139 if (isConstructor
) {
5140 if (!GetPrototypeFromBuiltinConstructor(cx
, args
, JSProto_Array
, &proto
)) {
5145 if (args
.length() != 1 || !args
[0].isNumber()) {
5146 return ArrayFromCallArgs(cx
, args
, proto
);
5150 if (args
[0].isInt32()) {
5151 int32_t i
= args
[0].toInt32();
5153 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5154 JSMSG_BAD_ARRAY_LENGTH
);
5157 length
= uint32_t(i
);
5159 double d
= args
[0].toDouble();
5160 length
= ToUint32(d
);
5161 if (d
!= double(length
)) {
5162 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5163 JSMSG_BAD_ARRAY_LENGTH
);
5168 ArrayObject
* obj
= NewDensePartlyAllocatedArrayWithProto(cx
, length
, proto
);
5173 args
.rval().setObject(*obj
);
5178 bool js::ArrayConstructor(JSContext
* cx
, unsigned argc
, Value
* vp
) {
5179 AutoJSConstructorProfilerEntry
pseudoFrame(cx
, "Array");
5180 CallArgs args
= CallArgsFromVp(argc
, vp
);
5181 return ArrayConstructorImpl(cx
, args
, /* isConstructor = */ true);
5184 bool js::array_construct(JSContext
* cx
, unsigned argc
, Value
* vp
) {
5185 AutoJSConstructorProfilerEntry
pseudoFrame(cx
, "Array");
5186 CallArgs args
= CallArgsFromVp(argc
, vp
);
5187 MOZ_ASSERT(!args
.isConstructing());
5188 MOZ_ASSERT(args
.length() == 1);
5189 MOZ_ASSERT(args
[0].isNumber());
5190 return ArrayConstructorImpl(cx
, args
, /* isConstructor = */ false);
5193 ArrayObject
* js::ArrayConstructorOneArg(JSContext
* cx
,
5194 Handle
<ArrayObject
*> templateObject
,
5195 int32_t lengthInt
) {
5196 // JIT code can call this with a template object from a different realm when
5197 // calling another realm's Array constructor.
5198 Maybe
<AutoRealm
> ar
;
5199 if (cx
->realm() != templateObject
->realm()) {
5200 MOZ_ASSERT(cx
->compartment() == templateObject
->compartment());
5201 ar
.emplace(cx
, templateObject
);
5204 if (lengthInt
< 0) {
5205 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5206 JSMSG_BAD_ARRAY_LENGTH
);
5210 uint32_t length
= uint32_t(lengthInt
);
5211 ArrayObject
* res
= NewDensePartlyAllocatedArray(cx
, length
);
5212 MOZ_ASSERT_IF(res
, res
->realm() == templateObject
->realm());
5217 * Array allocation functions.
5220 static inline bool EnsureNewArrayElements(JSContext
* cx
, ArrayObject
* obj
,
5223 * If ensureElements creates dynamically allocated slots, then having
5224 * fixedSlots is a waste.
5226 DebugOnly
<uint32_t> cap
= obj
->getDenseCapacity();
5228 if (!obj
->ensureElements(cx
, length
)) {
5232 MOZ_ASSERT_IF(cap
, !obj
->hasDynamicElements());
5237 template <uint32_t maxLength
>
5238 static MOZ_ALWAYS_INLINE ArrayObject
* NewArrayWithShape(
5239 JSContext
* cx
, Handle
<SharedShape
*> shape
, uint32_t length
,
5240 NewObjectKind newKind
, gc::AllocSite
* site
= nullptr) {
5241 // The shape must already have the |length| property defined on it.
5242 MOZ_ASSERT(shape
->propMapLength() == 1);
5243 MOZ_ASSERT(shape
->lastProperty().key() == NameToId(cx
->names().length
));
5245 gc::AllocKind allocKind
= GuessArrayGCKind(length
);
5246 MOZ_ASSERT(CanChangeToBackgroundAllocKind(allocKind
, &ArrayObject::class_
));
5247 allocKind
= ForegroundToBackgroundAllocKind(allocKind
);
5249 MOZ_ASSERT(shape
->slotSpan() == 0);
5250 constexpr uint32_t slotSpan
= 0;
5252 AutoSetNewObjectMetadata
metadata(cx
);
5253 ArrayObject
* arr
= ArrayObject::create(
5254 cx
, allocKind
, GetInitialHeap(newKind
, &ArrayObject::class_
, site
), shape
,
5255 length
, slotSpan
, metadata
);
5260 if (maxLength
> 0 &&
5261 !EnsureNewArrayElements(cx
, arr
, std::min(maxLength
, length
))) {
5265 probes::CreateObject(cx
, arr
);
5269 static SharedShape
* GetArrayShapeWithProto(JSContext
* cx
, HandleObject proto
) {
5270 // Get a shape with zero fixed slots, because arrays store the ObjectElements
5272 Rooted
<SharedShape
*> shape(
5273 cx
, SharedShape::getInitialShape(cx
, &ArrayObject::class_
, cx
->realm(),
5274 TaggedProto(proto
), /* nfixed = */ 0));
5279 // Add the |length| property and use the new shape as initial shape for new
5281 if (shape
->propMapLength() == 0) {
5282 shape
= AddLengthProperty(cx
, shape
);
5286 SharedShape::insertInitialShape(cx
, shape
);
5288 MOZ_ASSERT(shape
->propMapLength() == 1);
5289 MOZ_ASSERT(shape
->lastProperty().key() == NameToId(cx
->names().length
));
5295 SharedShape
* GlobalObject::createArrayShapeWithDefaultProto(JSContext
* cx
) {
5296 MOZ_ASSERT(!cx
->global()->data().arrayShapeWithDefaultProto
);
5298 RootedObject
proto(cx
,
5299 GlobalObject::getOrCreateArrayPrototype(cx
, cx
->global()));
5304 SharedShape
* shape
= GetArrayShapeWithProto(cx
, proto
);
5309 cx
->global()->data().arrayShapeWithDefaultProto
.init(shape
);
5313 template <uint32_t maxLength
>
5314 static MOZ_ALWAYS_INLINE ArrayObject
* NewArray(JSContext
* cx
, uint32_t length
,
5315 NewObjectKind newKind
,
5316 gc::AllocSite
* site
= nullptr) {
5317 Rooted
<SharedShape
*> shape(cx
,
5318 GlobalObject::getArrayShapeWithDefaultProto(cx
));
5323 return NewArrayWithShape
<maxLength
>(cx
, shape
, length
, newKind
, site
);
5326 template <uint32_t maxLength
>
5327 static MOZ_ALWAYS_INLINE ArrayObject
* NewArrayWithProto(JSContext
* cx
,
5330 NewObjectKind newKind
) {
5331 Rooted
<SharedShape
*> shape(cx
);
5332 if (!proto
|| proto
== cx
->global()->maybeGetArrayPrototype()) {
5333 shape
= GlobalObject::getArrayShapeWithDefaultProto(cx
);
5335 shape
= GetArrayShapeWithProto(cx
, proto
);
5341 return NewArrayWithShape
<maxLength
>(cx
, shape
, length
, newKind
, nullptr);
5344 static JSObject
* CreateArrayPrototype(JSContext
* cx
, JSProtoKey key
) {
5345 MOZ_ASSERT(key
== JSProto_Array
);
5346 RootedObject
proto(cx
, &cx
->global()->getObjectPrototype());
5347 return NewArrayWithProto
<0>(cx
, 0, proto
, TenuredObject
);
5350 static bool array_proto_finish(JSContext
* cx
, JS::HandleObject ctor
,
5351 JS::HandleObject proto
) {
5352 // Add Array.prototype[@@unscopables]. ECMA-262 draft (2016 Mar 19) 22.1.3.32.
5353 RootedObject
unscopables(cx
,
5354 NewPlainObjectWithProto(cx
, nullptr, TenuredObject
));
5359 RootedValue
value(cx
, BooleanValue(true));
5360 if (!DefineDataProperty(cx
, unscopables
, cx
->names().at
, value
) ||
5361 !DefineDataProperty(cx
, unscopables
, cx
->names().copyWithin
, value
) ||
5362 !DefineDataProperty(cx
, unscopables
, cx
->names().entries
, value
) ||
5363 !DefineDataProperty(cx
, unscopables
, cx
->names().fill
, value
) ||
5364 !DefineDataProperty(cx
, unscopables
, cx
->names().find
, value
) ||
5365 !DefineDataProperty(cx
, unscopables
, cx
->names().findIndex
, value
) ||
5366 !DefineDataProperty(cx
, unscopables
, cx
->names().findLast
, value
) ||
5367 !DefineDataProperty(cx
, unscopables
, cx
->names().findLastIndex
, value
) ||
5368 !DefineDataProperty(cx
, unscopables
, cx
->names().flat
, value
) ||
5369 !DefineDataProperty(cx
, unscopables
, cx
->names().flatMap
, value
) ||
5370 !DefineDataProperty(cx
, unscopables
, cx
->names().includes
, value
) ||
5371 !DefineDataProperty(cx
, unscopables
, cx
->names().keys
, value
) ||
5372 !DefineDataProperty(cx
, unscopables
, cx
->names().toReversed
, value
) ||
5373 !DefineDataProperty(cx
, unscopables
, cx
->names().toSorted
, value
) ||
5374 !DefineDataProperty(cx
, unscopables
, cx
->names().toSpliced
, value
) ||
5375 !DefineDataProperty(cx
, unscopables
, cx
->names().values
, value
)) {
5379 RootedId
id(cx
, PropertyKey::Symbol(cx
->wellKnownSymbols().unscopables
));
5380 value
.setObject(*unscopables
);
5381 if (!DefineDataProperty(cx
, proto
, id
, value
, JSPROP_READONLY
)) {
5385 // Mark Array prototype as having fuse property (@iterator for example).
5386 return JSObject::setHasFuseProperty(cx
, proto
);
5389 static const JSClassOps ArrayObjectClassOps
= {
5390 array_addProperty
, // addProperty
5391 nullptr, // delProperty
5392 nullptr, // enumerate
5393 nullptr, // newEnumerate
5395 nullptr, // mayResolve
5396 nullptr, // finalize
5398 nullptr, // construct
5402 static const ClassSpec ArrayObjectClassSpec
= {
5403 GenericCreateConstructor
<ArrayConstructor
, 1, gc::AllocKind::FUNCTION
,
5404 &jit::JitInfo_Array
>,
5405 CreateArrayPrototype
,
5406 array_static_methods
,
5410 array_proto_finish
};
5412 const JSClass
ArrayObject::class_
= {
5414 JSCLASS_HAS_CACHED_PROTO(JSProto_Array
) | JSCLASS_DELAY_METADATA_BUILDER
,
5415 &ArrayObjectClassOps
, &ArrayObjectClassSpec
};
5417 ArrayObject
* js::NewDenseEmptyArray(JSContext
* cx
) {
5418 return NewArray
<0>(cx
, 0, GenericObject
);
5421 ArrayObject
* js::NewTenuredDenseEmptyArray(JSContext
* cx
) {
5422 return NewArray
<0>(cx
, 0, TenuredObject
);
5425 ArrayObject
* js::NewDenseFullyAllocatedArray(
5426 JSContext
* cx
, uint32_t length
, NewObjectKind newKind
/* = GenericObject */,
5427 gc::AllocSite
* site
/* = nullptr */) {
5428 return NewArray
<UINT32_MAX
>(cx
, length
, newKind
, site
);
5431 ArrayObject
* js::NewDensePartlyAllocatedArray(
5432 JSContext
* cx
, uint32_t length
,
5433 NewObjectKind newKind
/* = GenericObject */) {
5434 return NewArray
<ArrayObject::EagerAllocationMaxLength
>(cx
, length
, newKind
);
5437 ArrayObject
* js::NewDensePartlyAllocatedArrayWithProto(JSContext
* cx
,
5439 HandleObject proto
) {
5440 return NewArrayWithProto
<ArrayObject::EagerAllocationMaxLength
>(
5441 cx
, length
, proto
, GenericObject
);
5444 ArrayObject
* js::NewDenseUnallocatedArray(
5445 JSContext
* cx
, uint32_t length
,
5446 NewObjectKind newKind
/* = GenericObject */) {
5447 return NewArray
<0>(cx
, length
, newKind
);
5450 // values must point at already-rooted Value objects
5451 ArrayObject
* js::NewDenseCopiedArray(
5452 JSContext
* cx
, uint32_t length
, const Value
* values
,
5453 NewObjectKind newKind
/* = GenericObject */) {
5454 ArrayObject
* arr
= NewArray
<UINT32_MAX
>(cx
, length
, newKind
);
5459 arr
->initDenseElements(values
, length
);
5463 // values must point at already-rooted Value objects
5464 ArrayObject
* js::NewDenseCopiedArray(
5465 JSContext
* cx
, uint32_t length
, JSLinearString
** values
,
5466 NewObjectKind newKind
/* = GenericObject */) {
5467 ArrayObject
* arr
= NewArray
<UINT32_MAX
>(cx
, length
, newKind
);
5472 arr
->initDenseElements(values
, length
);
5476 ArrayObject
* js::NewDenseCopiedArrayWithProto(JSContext
* cx
, uint32_t length
,
5477 const Value
* values
,
5478 HandleObject proto
) {
5480 NewArrayWithProto
<UINT32_MAX
>(cx
, length
, proto
, GenericObject
);
5485 arr
->initDenseElements(values
, length
);
5489 ArrayObject
* js::NewDenseFullyAllocatedArrayWithShape(
5490 JSContext
* cx
, uint32_t length
, Handle
<SharedShape
*> shape
) {
5491 AutoSetNewObjectMetadata
metadata(cx
);
5492 gc::AllocKind allocKind
= GuessArrayGCKind(length
);
5493 MOZ_ASSERT(CanChangeToBackgroundAllocKind(allocKind
, &ArrayObject::class_
));
5494 allocKind
= ForegroundToBackgroundAllocKind(allocKind
);
5496 gc::Heap heap
= GetInitialHeap(GenericObject
, &ArrayObject::class_
);
5497 ArrayObject
* arr
= ArrayObject::create(cx
, allocKind
, heap
, shape
, length
,
5498 shape
->slotSpan(), metadata
);
5503 if (!EnsureNewArrayElements(cx
, arr
, length
)) {
5507 probes::CreateObject(cx
, arr
);
5512 // TODO(no-TI): clean up.
5513 ArrayObject
* js::NewArrayWithShape(JSContext
* cx
, uint32_t length
,
5514 Handle
<Shape
*> shape
) {
5515 // Ion can call this with a shape from a different realm when calling
5516 // another realm's Array constructor.
5517 Maybe
<AutoRealm
> ar
;
5518 if (cx
->realm() != shape
->realm()) {
5519 MOZ_ASSERT(cx
->compartment() == shape
->compartment());
5520 ar
.emplace(cx
, shape
);
5523 return NewDenseFullyAllocatedArray(cx
, length
);
5527 bool js::ArrayInfo(JSContext
* cx
, unsigned argc
, Value
* vp
) {
5528 CallArgs args
= CallArgsFromVp(argc
, vp
);
5529 RootedObject
obj(cx
);
5531 for (unsigned i
= 0; i
< args
.length(); i
++) {
5532 HandleValue arg
= args
[i
];
5535 DecompileValueGenerator(cx
, JSDVG_SEARCH_STACK
, arg
, nullptr);
5539 if (arg
.isPrimitive() || !(obj
= arg
.toObjectOrNull())->is
<ArrayObject
>()) {
5540 fprintf(stderr
, "%s: not array\n", bytes
.get());
5543 fprintf(stderr
, "%s: (len %u", bytes
.get(),
5544 obj
->as
<ArrayObject
>().length());
5545 fprintf(stderr
, ", capacity %u", obj
->as
<ArrayObject
>().getDenseCapacity());
5546 fputs(")\n", stderr
);
5549 args
.rval().setUndefined();
5554 void js::ArraySpeciesLookup::initialize(JSContext
* cx
) {
5555 MOZ_ASSERT(state_
== State::Uninitialized
);
5557 // Get the canonical Array.prototype.
5558 NativeObject
* arrayProto
= cx
->global()->maybeGetArrayPrototype();
5560 // Leave the cache uninitialized if the Array class itself is not yet
5566 // Get the canonical Array constructor. The Array constructor must be
5567 // initialized if Array.prototype is initialized.
5568 JSObject
& arrayCtorObject
= cx
->global()->getConstructor(JSProto_Array
);
5569 JSFunction
* arrayCtor
= &arrayCtorObject
.as
<JSFunction
>();
5571 // Shortcut returns below means Array[@@species] will never be
5572 // optimizable, set to disabled now, and clear it later when we succeed.
5573 state_
= State::Disabled
;
5575 // Look up Array.prototype.constructor and ensure it's a data property.
5576 Maybe
<PropertyInfo
> ctorProp
=
5577 arrayProto
->lookup(cx
, NameToId(cx
->names().constructor
));
5578 if (ctorProp
.isNothing() || !ctorProp
->isDataProperty()) {
5582 // Get the referred value, and ensure it holds the canonical Array
5584 JSFunction
* ctorFun
;
5585 if (!IsFunctionObject(arrayProto
->getSlot(ctorProp
->slot()), &ctorFun
)) {
5588 if (ctorFun
!= arrayCtor
) {
5592 // Look up the '@@species' value on Array
5593 Maybe
<PropertyInfo
> speciesProp
= arrayCtor
->lookup(
5594 cx
, PropertyKey::Symbol(cx
->wellKnownSymbols().species
));
5595 if (speciesProp
.isNothing() || !arrayCtor
->hasGetter(*speciesProp
)) {
5599 // Get the referred value, ensure it holds the canonical Array[@@species]
5601 uint32_t speciesGetterSlot
= speciesProp
->slot();
5602 JSObject
* speciesGetter
= arrayCtor
->getGetter(speciesGetterSlot
);
5603 if (!speciesGetter
|| !speciesGetter
->is
<JSFunction
>()) {
5606 JSFunction
* speciesFun
= &speciesGetter
->as
<JSFunction
>();
5607 if (!IsSelfHostedFunctionWithName(speciesFun
,
5608 cx
->names().dollar_ArraySpecies_
)) {
5612 // Store raw pointers below. This is okay to do here, because all objects
5613 // are in the tenured heap.
5614 MOZ_ASSERT(!IsInsideNursery(arrayProto
));
5615 MOZ_ASSERT(!IsInsideNursery(arrayCtor
));
5616 MOZ_ASSERT(!IsInsideNursery(arrayCtor
->shape()));
5617 MOZ_ASSERT(!IsInsideNursery(speciesFun
));
5618 MOZ_ASSERT(!IsInsideNursery(arrayProto
->shape()));
5620 state_
= State::Initialized
;
5621 arrayProto_
= arrayProto
;
5622 arrayConstructor_
= arrayCtor
;
5623 arrayConstructorShape_
= arrayCtor
->shape();
5624 arraySpeciesGetterSlot_
= speciesGetterSlot
;
5625 canonicalSpeciesFunc_
= speciesFun
;
5626 arrayProtoShape_
= arrayProto
->shape();
5627 arrayProtoConstructorSlot_
= ctorProp
->slot();
5630 void js::ArraySpeciesLookup::reset() {
5631 AlwaysPoison(this, JS_RESET_VALUE_PATTERN
, sizeof(*this),
5632 MemCheckKind::MakeUndefined
);
5633 state_
= State::Uninitialized
;
5636 bool js::ArraySpeciesLookup::isArrayStateStillSane() {
5637 MOZ_ASSERT(state_
== State::Initialized
);
5639 // Ensure that Array.prototype still has the expected shape.
5640 if (arrayProto_
->shape() != arrayProtoShape_
) {
5644 // Ensure that Array.prototype.constructor contains the canonical Array
5645 // constructor function.
5646 if (arrayProto_
->getSlot(arrayProtoConstructorSlot_
) !=
5647 ObjectValue(*arrayConstructor_
)) {
5651 // Ensure that Array still has the expected shape.
5652 if (arrayConstructor_
->shape() != arrayConstructorShape_
) {
5656 // Ensure the species getter contains the canonical @@species function.
5657 JSObject
* getter
= arrayConstructor_
->getGetter(arraySpeciesGetterSlot_
);
5658 return getter
== canonicalSpeciesFunc_
;
5661 bool js::ArraySpeciesLookup::tryOptimizeArray(JSContext
* cx
,
5662 ArrayObject
* array
) {
5663 if (state_
== State::Uninitialized
) {
5664 // If the cache is not initialized, initialize it.
5666 } else if (state_
== State::Initialized
&& !isArrayStateStillSane()) {
5667 // Otherwise, if the array state is no longer sane, reinitialize.
5672 // If the cache is disabled or still uninitialized, don't bother trying to
5674 if (state_
!= State::Initialized
) {
5678 // By the time we get here, we should have a sane array state.
5679 MOZ_ASSERT(isArrayStateStillSane());
5681 // Ensure |array|'s prototype is the actual Array.prototype.
5682 if (array
->staticPrototype() != arrayProto_
) {
5686 // Ensure the array does not define an own "constructor" property which may
5687 // shadow `Array.prototype.constructor`.
5689 // Most arrays don't define any additional own properties beside their
5690 // "length" property. If "length" is the last property, it must be the only
5691 // property, because it's non-configurable.
5692 MOZ_ASSERT(array
->shape()->propMapLength() > 0);
5693 PropertyKey lengthKey
= NameToId(cx
->names().length
);
5694 if (MOZ_LIKELY(array
->getLastProperty().key() == lengthKey
)) {
5695 MOZ_ASSERT(array
->shape()->propMapLength() == 1, "Expected one property");
5699 // Fail if the array has an own "constructor" property.
5701 if (array
->shape()->lookup(cx
, NameToId(cx
->names().constructor
), &index
)) {
5708 JS_PUBLIC_API JSObject
* JS::NewArrayObject(JSContext
* cx
,
5709 const HandleValueArray
& contents
) {
5710 MOZ_ASSERT(!cx
->zone()->isAtomsZone());
5713 cx
->check(contents
);
5715 return NewDenseCopiedArray(cx
, contents
.length(), contents
.begin());
5718 JS_PUBLIC_API JSObject
* JS::NewArrayObject(JSContext
* cx
, size_t length
) {
5719 MOZ_ASSERT(!cx
->zone()->isAtomsZone());
5723 return NewDenseFullyAllocatedArray(cx
, length
);
5726 JS_PUBLIC_API
bool JS::IsArrayObject(JSContext
* cx
, Handle
<JSObject
*> obj
,
5728 return IsGivenTypeObject(cx
, obj
, ESClass::Array
, isArray
);
5731 JS_PUBLIC_API
bool JS::IsArrayObject(JSContext
* cx
, Handle
<Value
> value
,
5733 if (!value
.isObject()) {
5738 Rooted
<JSObject
*> obj(cx
, &value
.toObject());
5739 return IsArrayObject(cx
, obj
, isArray
);
5742 JS_PUBLIC_API
bool JS::GetArrayLength(JSContext
* cx
, Handle
<JSObject
*> obj
,
5743 uint32_t* lengthp
) {
5749 if (!GetLengthProperty(cx
, obj
, &len
)) {
5753 if (len
> UINT32_MAX
) {
5754 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5755 JSMSG_BAD_ARRAY_LENGTH
);
5759 *lengthp
= uint32_t(len
);
5763 JS_PUBLIC_API
bool JS::SetArrayLength(JSContext
* cx
, Handle
<JSObject
*> obj
,
5769 return SetLengthProperty(cx
, obj
, length
);
5772 ArrayObject
* js::NewArrayWithNullProto(JSContext
* cx
) {
5773 Rooted
<SharedShape
*> shape(cx
, GetArrayShapeWithProto(cx
, nullptr));
5778 uint32_t length
= 0;
5779 return ::NewArrayWithShape
<0>(cx
, shape
, length
, GenericObject
);