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"
26 #include "jit/InlinableNatives.h"
27 #include "jit/TrampolineNatives.h"
29 #include "js/Conversions.h"
30 #include "js/experimental/JitInfo.h" // JSJitGetterOp, JSJitInfo
31 #include "js/friend/ErrorMessages.h" // js::GetErrorMessage, JSMSG_*
32 #include "js/PropertySpec.h"
33 #include "util/Poison.h"
34 #include "util/StringBuffer.h"
35 #include "util/Text.h"
36 #include "vm/ArgumentsObject.h"
37 #include "vm/EqualityOperations.h"
38 #include "vm/Interpreter.h"
39 #include "vm/Iteration.h"
40 #include "vm/JSContext.h"
41 #include "vm/JSFunction.h"
42 #include "vm/JSObject.h"
43 #include "vm/PlainObject.h" // js::PlainObject
44 #include "vm/SelfHosting.h"
46 #include "vm/StringType.h"
47 #include "vm/ToSource.h" // js::ValueToSource
48 #include "vm/TypedArrayObject.h"
49 #include "vm/WrapperObject.h"
50 #ifdef ENABLE_RECORD_TUPLE
51 # include "vm/TupleType.h"
54 #include "vm/ArgumentsObject-inl.h"
55 #include "vm/ArrayObject-inl.h"
56 #include "vm/GeckoProfiler-inl.h"
57 #include "vm/IsGivenTypeObject-inl.h"
58 #include "vm/JSAtomUtils-inl.h" // PrimitiveValueToId, IndexToId
59 #include "vm/NativeObject-inl.h"
64 using mozilla::CeilingLog2
;
65 using mozilla::CheckedInt
;
66 using mozilla::DebugOnly
;
67 using mozilla::IsAsciiDigit
;
71 using JS::AutoCheckCannotGC
;
72 using JS::IsArrayAnswer
;
75 bool js::ObjectMayHaveExtraIndexedOwnProperties(JSObject
* obj
) {
76 if (!obj
->is
<NativeObject
>()) {
80 if (obj
->as
<NativeObject
>().isIndexed()) {
84 if (obj
->is
<TypedArrayObject
>()) {
88 return ClassMayResolveId(*obj
->runtimeFromAnyThread()->commonNames
,
89 obj
->getClass(), PropertyKey::Int(0), obj
);
92 bool js::PrototypeMayHaveIndexedProperties(NativeObject
* obj
) {
94 MOZ_ASSERT(obj
->hasStaticPrototype(),
95 "dynamic-prototype objects must be non-native");
97 JSObject
* proto
= obj
->staticPrototype();
99 return false; // no extra indexed properties found
102 if (ObjectMayHaveExtraIndexedOwnProperties(proto
)) {
105 obj
= &proto
->as
<NativeObject
>();
106 if (obj
->getDenseInitializedLength() != 0) {
113 * Whether obj may have indexed properties anywhere besides its dense
114 * elements. This includes other indexed properties in its shape hierarchy, and
115 * indexed properties or elements along its prototype chain.
117 bool js::ObjectMayHaveExtraIndexedProperties(JSObject
* obj
) {
118 MOZ_ASSERT_IF(obj
->hasDynamicPrototype(), !obj
->is
<NativeObject
>());
120 if (ObjectMayHaveExtraIndexedOwnProperties(obj
)) {
124 return PrototypeMayHaveIndexedProperties(&obj
->as
<NativeObject
>());
127 bool JS::IsArray(JSContext
* cx
, HandleObject obj
, IsArrayAnswer
* answer
) {
128 if (obj
->is
<ArrayObject
>()) {
129 *answer
= IsArrayAnswer::Array
;
133 if (obj
->is
<ProxyObject
>()) {
134 return Proxy::isArray(cx
, obj
, answer
);
137 *answer
= IsArrayAnswer::NotArray
;
141 bool JS::IsArray(JSContext
* cx
, HandleObject obj
, bool* isArray
) {
142 IsArrayAnswer answer
;
143 if (!IsArray(cx
, obj
, &answer
)) {
147 if (answer
== IsArrayAnswer::RevokedProxy
) {
148 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
149 JSMSG_PROXY_REVOKED
);
153 *isArray
= answer
== IsArrayAnswer::Array
;
157 bool js::IsArrayFromJit(JSContext
* cx
, HandleObject obj
, bool* isArray
) {
158 return JS::IsArray(cx
, obj
, isArray
);
161 // ES2017 7.1.15 ToLength.
162 bool js::ToLength(JSContext
* cx
, HandleValue v
, uint64_t* out
) {
164 int32_t i
= v
.toInt32();
165 *out
= i
< 0 ? 0 : i
;
173 if (!ToNumber(cx
, v
, &d
)) {
178 d
= JS::ToInteger(d
);
182 *out
= uint64_t(std::min(d
, DOUBLE_INTEGRAL_PRECISION_LIMIT
- 1));
187 bool js::GetLengthProperty(JSContext
* cx
, HandleObject obj
, uint64_t* lengthp
) {
188 if (obj
->is
<ArrayObject
>()) {
189 *lengthp
= obj
->as
<ArrayObject
>().length();
193 if (obj
->is
<ArgumentsObject
>()) {
194 ArgumentsObject
& argsobj
= obj
->as
<ArgumentsObject
>();
195 if (!argsobj
.hasOverriddenLength()) {
196 *lengthp
= argsobj
.initialLength();
201 RootedValue
value(cx
);
202 if (!GetProperty(cx
, obj
, obj
, cx
->names().length
, &value
)) {
206 return ToLength(cx
, value
, lengthp
);
209 // Fast path for array functions where the object is expected to be an array.
210 static MOZ_ALWAYS_INLINE
bool GetLengthPropertyInlined(JSContext
* cx
,
213 if (obj
->is
<ArrayObject
>()) {
214 *lengthp
= obj
->as
<ArrayObject
>().length();
218 return GetLengthProperty(cx
, obj
, lengthp
);
222 * Determine if the id represents an array index.
224 * An id is an array index according to ECMA by (15.4):
226 * "Array objects give special treatment to a certain class of property names.
227 * A property name P (in the form of a string value) is an array index if and
228 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
231 * This means the largest allowed index is actually 2^32-2 (4294967294).
233 * In our implementation, it would be sufficient to check for id.isInt32()
234 * except that by using signed 31-bit integers we miss the top half of the
235 * valid range. This function checks the string representation itself; note
236 * that calling a standard conversion routine might allow strings such as
237 * "08" or "4.0" as array indices, which they are not.
240 JS_PUBLIC_API
bool js::StringIsArrayIndex(JSLinearString
* str
,
242 if (!str
->isIndex(indexp
)) {
245 MOZ_ASSERT(*indexp
<= MAX_ARRAY_INDEX
);
249 JS_PUBLIC_API
bool js::StringIsArrayIndex(const char16_t
* str
, uint32_t length
,
251 if (length
== 0 || length
> UINT32_CHAR_BUFFER_LENGTH
) {
254 if (!mozilla::IsAsciiDigit(str
[0])) {
257 if (!CheckStringIsIndex(str
, length
, indexp
)) {
260 MOZ_ASSERT(*indexp
<= MAX_ARRAY_INDEX
);
264 template <typename T
>
265 static bool ToId(JSContext
* cx
, T index
, MutableHandleId id
);
268 bool ToId(JSContext
* cx
, uint32_t index
, MutableHandleId id
) {
269 return IndexToId(cx
, index
, id
);
273 bool ToId(JSContext
* cx
, uint64_t index
, MutableHandleId id
) {
274 MOZ_ASSERT(index
< uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
));
276 if (index
== uint32_t(index
)) {
277 return IndexToId(cx
, uint32_t(index
), id
);
280 Value tmp
= DoubleValue(index
);
281 return PrimitiveValueToId
<CanGC
>(cx
, HandleValue::fromMarkedLocation(&tmp
),
286 * If the property at the given index exists, get its value into |vp| and set
287 * |*hole| to false. Otherwise set |*hole| to true and |vp| to Undefined.
289 template <typename T
>
290 static bool HasAndGetElement(JSContext
* cx
, HandleObject obj
,
291 HandleObject receiver
, T index
, bool* hole
,
292 MutableHandleValue vp
) {
293 if (obj
->is
<NativeObject
>()) {
294 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
295 if (index
< nobj
->getDenseInitializedLength()) {
296 vp
.set(nobj
->getDenseElement(size_t(index
)));
297 if (!vp
.isMagic(JS_ELEMENTS_HOLE
)) {
302 if (nobj
->is
<ArgumentsObject
>() && index
<= UINT32_MAX
) {
303 if (nobj
->as
<ArgumentsObject
>().maybeGetElement(uint32_t(index
), vp
)) {
311 if (!ToId(cx
, index
, &id
)) {
316 if (!HasProperty(cx
, obj
, id
, &found
)) {
321 if (!GetProperty(cx
, obj
, receiver
, id
, vp
)) {
331 template <typename T
>
332 static inline bool HasAndGetElement(JSContext
* cx
, HandleObject obj
, T index
,
333 bool* hole
, MutableHandleValue vp
) {
334 return HasAndGetElement(cx
, obj
, obj
, index
, hole
, vp
);
337 bool ElementAdder::append(JSContext
* cx
, HandleValue v
) {
338 MOZ_ASSERT(index_
< length_
);
340 NativeObject
* resObj
= &resObj_
->as
<NativeObject
>();
341 DenseElementResult result
=
342 resObj
->setOrExtendDenseElements(cx
, index_
, v
.address(), 1);
343 if (result
== DenseElementResult::Failure
) {
346 if (result
== DenseElementResult::Incomplete
) {
347 if (!DefineDataElement(cx
, resObj_
, index_
, v
)) {
358 void ElementAdder::appendHole() {
359 MOZ_ASSERT(getBehavior_
== ElementAdder::CheckHasElemPreserveHoles
);
360 MOZ_ASSERT(index_
< length_
);
362 vp_
[index_
].setMagic(JS_ELEMENTS_HOLE
);
367 bool js::GetElementsWithAdder(JSContext
* cx
, HandleObject obj
,
368 HandleObject receiver
, uint32_t begin
,
369 uint32_t end
, ElementAdder
* adder
) {
370 MOZ_ASSERT(begin
<= end
);
373 for (uint32_t i
= begin
; i
< end
; i
++) {
374 if (adder
->getBehavior() == ElementAdder::CheckHasElemPreserveHoles
) {
376 if (!HasAndGetElement(cx
, obj
, receiver
, i
, &hole
, &val
)) {
384 MOZ_ASSERT(adder
->getBehavior() == ElementAdder::GetElement
);
385 if (!GetElement(cx
, obj
, receiver
, i
, &val
)) {
389 if (!adder
->append(cx
, val
)) {
397 static inline bool IsPackedArrayOrNoExtraIndexedProperties(JSObject
* obj
,
399 return (IsPackedArray(obj
) && obj
->as
<ArrayObject
>().length() == length
) ||
400 !ObjectMayHaveExtraIndexedProperties(obj
);
403 static bool GetDenseElements(NativeObject
* aobj
, uint32_t length
, Value
* vp
) {
404 MOZ_ASSERT(IsPackedArrayOrNoExtraIndexedProperties(aobj
, length
));
406 if (length
> aobj
->getDenseInitializedLength()) {
410 for (size_t i
= 0; i
< length
; i
++) {
411 vp
[i
] = aobj
->getDenseElement(i
);
413 // No other indexed properties so hole => undefined.
414 if (vp
[i
].isMagic(JS_ELEMENTS_HOLE
)) {
415 vp
[i
] = UndefinedValue();
422 bool js::GetElements(JSContext
* cx
, HandleObject aobj
, uint32_t length
,
424 if (IsPackedArrayOrNoExtraIndexedProperties(aobj
, length
)) {
425 if (GetDenseElements(&aobj
->as
<NativeObject
>(), length
, vp
)) {
430 if (aobj
->is
<ArgumentsObject
>()) {
431 ArgumentsObject
& argsobj
= aobj
->as
<ArgumentsObject
>();
432 if (!argsobj
.hasOverriddenLength()) {
433 if (argsobj
.maybeGetElements(0, length
, vp
)) {
439 if (aobj
->is
<TypedArrayObject
>()) {
440 Handle
<TypedArrayObject
*> typedArray
= aobj
.as
<TypedArrayObject
>();
441 if (typedArray
->length().valueOr(0) == length
) {
442 return TypedArrayObject::getElements(cx
, typedArray
, length
, vp
);
446 if (js::GetElementsOp op
= aobj
->getOpsGetElements()) {
447 ElementAdder
adder(cx
, vp
, length
, ElementAdder::GetElement
);
448 return op(cx
, aobj
, 0, length
, &adder
);
451 for (uint32_t i
= 0; i
< length
; i
++) {
452 if (!GetElement(cx
, aobj
, aobj
, i
,
453 MutableHandleValue::fromMarkedLocation(&vp
[i
]))) {
461 static inline bool GetArrayElement(JSContext
* cx
, HandleObject obj
,
462 uint64_t index
, MutableHandleValue vp
) {
463 if (obj
->is
<NativeObject
>()) {
464 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
465 if (index
< nobj
->getDenseInitializedLength()) {
466 vp
.set(nobj
->getDenseElement(size_t(index
)));
467 if (!vp
.isMagic(JS_ELEMENTS_HOLE
)) {
472 if (nobj
->is
<ArgumentsObject
>() && index
<= UINT32_MAX
) {
473 if (nobj
->as
<ArgumentsObject
>().maybeGetElement(uint32_t(index
), vp
)) {
480 if (!ToId(cx
, index
, &id
)) {
483 return GetProperty(cx
, obj
, obj
, id
, vp
);
486 static inline bool DefineArrayElement(JSContext
* cx
, HandleObject obj
,
487 uint64_t index
, HandleValue value
) {
489 if (!ToId(cx
, index
, &id
)) {
492 return DefineDataProperty(cx
, obj
, id
, value
);
495 // Set the value of the property at the given index to v.
496 static inline bool SetArrayElement(JSContext
* cx
, HandleObject obj
,
497 uint64_t index
, HandleValue v
) {
499 if (!ToId(cx
, index
, &id
)) {
503 return SetProperty(cx
, obj
, id
, v
);
507 * Attempt to delete the element |index| from |obj| as if by
508 * |obj.[[Delete]](index)|.
510 * If an error occurs while attempting to delete the element (that is, the call
511 * to [[Delete]] threw), return false.
513 * Otherwise call result.succeed() or result.fail() to indicate whether the
514 * deletion attempt succeeded (that is, whether the call to [[Delete]] returned
515 * true or false). (Deletes generally fail only when the property is
516 * non-configurable, but proxies may implement different semantics.)
518 static bool DeleteArrayElement(JSContext
* cx
, HandleObject obj
, uint64_t index
,
519 ObjectOpResult
& result
) {
520 if (obj
->is
<ArrayObject
>() && !obj
->as
<NativeObject
>().isIndexed() &&
521 !obj
->as
<NativeObject
>().denseElementsAreSealed()) {
522 ArrayObject
* aobj
= &obj
->as
<ArrayObject
>();
523 if (index
<= UINT32_MAX
) {
524 uint32_t idx
= uint32_t(index
);
525 if (idx
< aobj
->getDenseInitializedLength()) {
526 if (idx
+ 1 == aobj
->getDenseInitializedLength()) {
527 aobj
->setDenseInitializedLengthMaybeNonExtensible(cx
, idx
);
529 aobj
->setDenseElementHole(idx
);
531 if (!SuppressDeletedElement(cx
, obj
, idx
)) {
537 return result
.succeed();
541 if (!ToId(cx
, index
, &id
)) {
544 return DeleteProperty(cx
, obj
, id
, result
);
547 /* ES6 draft rev 32 (2 Febr 2015) 7.3.7 */
548 static bool DeletePropertyOrThrow(JSContext
* cx
, HandleObject obj
,
550 ObjectOpResult success
;
551 if (!DeleteArrayElement(cx
, obj
, index
, success
)) {
556 if (!ToId(cx
, index
, &id
)) {
559 return success
.reportError(cx
, obj
, id
);
564 static bool DeletePropertiesOrThrow(JSContext
* cx
, HandleObject obj
,
565 uint64_t len
, uint64_t finalLength
) {
566 if (obj
->is
<ArrayObject
>() && !obj
->as
<NativeObject
>().isIndexed() &&
567 !obj
->as
<NativeObject
>().denseElementsAreSealed()) {
568 if (len
<= UINT32_MAX
) {
569 // Skip forward to the initialized elements of this array.
570 len
= std::min(uint32_t(len
),
571 obj
->as
<ArrayObject
>().getDenseInitializedLength());
575 for (uint64_t k
= len
; k
> finalLength
; k
--) {
576 if (!CheckForInterrupt(cx
)) {
580 if (!DeletePropertyOrThrow(cx
, obj
, k
- 1)) {
587 static bool SetArrayLengthProperty(JSContext
* cx
, Handle
<ArrayObject
*> obj
,
589 RootedId
id(cx
, NameToId(cx
->names().length
));
590 ObjectOpResult result
;
591 if (obj
->lengthIsWritable()) {
592 Rooted
<PropertyDescriptor
> desc(
593 cx
, PropertyDescriptor::Data(value
, JS::PropertyAttribute::Writable
));
594 if (!ArraySetLength(cx
, obj
, id
, desc
, result
)) {
598 MOZ_ALWAYS_TRUE(result
.fail(JSMSG_READ_ONLY
));
600 return result
.checkStrict(cx
, obj
, id
);
603 static bool SetLengthProperty(JSContext
* cx
, HandleObject obj
,
605 MOZ_ASSERT(length
< uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
));
607 RootedValue
v(cx
, NumberValue(length
));
608 if (obj
->is
<ArrayObject
>()) {
609 return SetArrayLengthProperty(cx
, obj
.as
<ArrayObject
>(), v
);
611 return SetProperty(cx
, obj
, cx
->names().length
, v
);
614 bool js::SetLengthProperty(JSContext
* cx
, HandleObject obj
, uint32_t length
) {
615 RootedValue
v(cx
, NumberValue(length
));
616 if (obj
->is
<ArrayObject
>()) {
617 return SetArrayLengthProperty(cx
, obj
.as
<ArrayObject
>(), v
);
619 return SetProperty(cx
, obj
, cx
->names().length
, v
);
622 bool js::ArrayLengthGetter(JSContext
* cx
, HandleObject obj
, HandleId id
,
623 MutableHandleValue vp
) {
624 MOZ_ASSERT(id
== NameToId(cx
->names().length
));
626 vp
.setNumber(obj
->as
<ArrayObject
>().length());
630 bool js::ArrayLengthSetter(JSContext
* cx
, HandleObject obj
, HandleId id
,
631 HandleValue v
, ObjectOpResult
& result
) {
632 MOZ_ASSERT(id
== NameToId(cx
->names().length
));
634 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
635 MOZ_ASSERT(arr
->lengthIsWritable(),
636 "setter shouldn't be called if property is non-writable");
638 Rooted
<PropertyDescriptor
> desc(
639 cx
, PropertyDescriptor::Data(v
, JS::PropertyAttribute::Writable
));
640 return ArraySetLength(cx
, arr
, id
, desc
, result
);
643 struct ReverseIndexComparator
{
644 bool operator()(const uint32_t& a
, const uint32_t& b
, bool* lessOrEqualp
) {
645 MOZ_ASSERT(a
!= b
, "how'd we get duplicate indexes?");
646 *lessOrEqualp
= b
<= a
;
651 /* ES6 draft rev 34 (2015 Feb 20) 9.4.2.4 ArraySetLength */
652 bool js::ArraySetLength(JSContext
* cx
, Handle
<ArrayObject
*> arr
, HandleId id
,
653 Handle
<PropertyDescriptor
> desc
,
654 ObjectOpResult
& result
) {
655 MOZ_ASSERT(id
== NameToId(cx
->names().length
));
656 MOZ_ASSERT(desc
.isDataDescriptor() || desc
.isGenericDescriptor());
660 if (!desc
.hasValue()) {
661 // The spec has us calling OrdinaryDefineOwnProperty if
662 // Desc.[[Value]] is absent, but our implementation is so different that
663 // this is impossible. Instead, set newLen to the current length and
664 // proceed to step 9.
665 newLen
= arr
->length();
667 // Step 2 is irrelevant in our implementation.
670 if (!ToUint32(cx
, desc
.value(), &newLen
)) {
676 if (!ToNumber(cx
, desc
.value(), &d
)) {
682 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
683 JSMSG_BAD_ARRAY_LENGTH
);
687 // Steps 6-8 are irrelevant in our implementation.
691 bool lengthIsWritable
= arr
->lengthIsWritable();
694 mozilla::Maybe
<PropertyInfo
> lengthProp
= arr
->lookupPure(id
);
695 MOZ_ASSERT(lengthProp
.isSome());
696 MOZ_ASSERT(lengthProp
->writable() == lengthIsWritable
);
699 uint32_t oldLen
= arr
->length();
701 // Part of steps 1.a, 12.a, and 16: Fail if we're being asked to change
702 // enumerability or configurability, or otherwise break the object
703 // invariants. (ES6 checks these by calling OrdinaryDefineOwnProperty, but
704 // in SM, the array length property is hardly ordinary.)
705 if ((desc
.hasConfigurable() && desc
.configurable()) ||
706 (desc
.hasEnumerable() && desc
.enumerable()) ||
707 (!lengthIsWritable
&& desc
.hasWritable() && desc
.writable())) {
708 return result
.fail(JSMSG_CANT_REDEFINE_PROP
);
711 // Steps 12-13 for arrays with non-writable length.
712 if (!lengthIsWritable
) {
713 if (newLen
== oldLen
) {
714 return result
.succeed();
717 return result
.fail(JSMSG_CANT_REDEFINE_ARRAY_LENGTH
);
721 bool succeeded
= true;
723 // The initialized length and capacity of an array only need updating
724 // when non-hole elements are added or removed, which doesn't happen
725 // when array length stays the same or increases.
726 if (newLen
>= oldLen
) {
730 // Attempt to propagate dense-element optimization tricks, if possible,
731 // and avoid the generic (and accordingly slow) deletion code below.
732 // We can only do this if there are only densely-indexed elements.
733 // Once there's a sparse indexed element, there's no good way to know,
734 // save by enumerating all the properties to find it. But we *have* to
735 // know in case that sparse indexed element is non-configurable, as
736 // that element must prevent any deletions below it. Bug 586842 should
737 // fix this inefficiency by moving indexed storage to be entirely
738 // separate from non-indexed storage.
739 // A second reason for this optimization to be invalid is an active
740 // for..in iteration over the array. Keys deleted before being reached
741 // during the iteration must not be visited, and suppressing them here
742 // would be too costly.
743 // This optimization is also invalid when there are sealed
744 // (non-configurable) elements.
745 if (!arr
->isIndexed() && !arr
->denseElementsMaybeInIteration() &&
746 !arr
->denseElementsAreSealed()) {
747 uint32_t oldCapacity
= arr
->getDenseCapacity();
748 uint32_t oldInitializedLength
= arr
->getDenseInitializedLength();
749 MOZ_ASSERT(oldCapacity
>= oldInitializedLength
);
750 if (oldInitializedLength
> newLen
) {
751 arr
->setDenseInitializedLengthMaybeNonExtensible(cx
, newLen
);
753 if (oldCapacity
> newLen
) {
754 if (arr
->isExtensible()) {
755 arr
->shrinkElements(cx
, newLen
);
757 MOZ_ASSERT(arr
->getDenseInitializedLength() ==
758 arr
->getDenseCapacity());
762 // We've done the work of deleting any dense elements needing
763 // deletion, and there are no sparse elements. Thus we can skip
764 // straight to defining the length.
770 // Attempt to delete all elements above the new length, from greatest
771 // to least. If any of these deletions fails, we're supposed to define
772 // the length to one greater than the index that couldn't be deleted,
773 // *with the property attributes specified*. This might convert the
774 // length to be not the value specified, yet non-writable. (You may be
775 // forgiven for thinking these are interesting semantics.) Example:
778 // Object.defineProperty([0, 1, 2, 3], 1, { writable: false });
779 // Object.defineProperty(arr, "length",
780 // { value: 0, writable: false });
782 // will convert |arr| to an array of non-writable length two, then
783 // throw a TypeError.
785 // We implement this behavior, in the relevant lops below, by setting
786 // |succeeded| to false. Then we exit the loop, define the length
787 // appropriately, and only then throw a TypeError, if necessary.
788 uint32_t gap
= oldLen
- newLen
;
789 const uint32_t RemoveElementsFastLimit
= 1 << 24;
790 if (gap
< RemoveElementsFastLimit
) {
791 // If we're removing a relatively small number of elements, just do
792 // it exactly by the spec.
793 while (newLen
< oldLen
) {
798 ObjectOpResult deleteSucceeded
;
799 if (!DeleteElement(cx
, arr
, oldLen
, deleteSucceeded
)) {
802 if (!deleteSucceeded
) {
809 // If we're removing a large number of elements from an array
810 // that's probably sparse, try a different tack. Get all the own
811 // property names, sift out the indexes in the deletion range into
812 // a vector, sort the vector greatest to least, then delete the
813 // indexes greatest to least using that vector. See bug 322135.
815 // This heuristic's kind of a huge guess -- "large number of
816 // elements" and "probably sparse" are completely unprincipled
817 // predictions. In the long run, bug 586842 will support the right
818 // fix: store sparse elements in a sorted data structure that
819 // permits fast in-reverse-order traversal and concurrent removals.
821 Vector
<uint32_t> indexes(cx
);
823 RootedIdVector
props(cx
);
824 if (!GetPropertyKeys(cx
, arr
, JSITER_OWNONLY
| JSITER_HIDDEN
, &props
)) {
828 for (size_t i
= 0; i
< props
.length(); i
++) {
829 if (!CheckForInterrupt(cx
)) {
834 if (!IdIsIndex(props
[i
], &index
)) {
838 if (index
>= newLen
&& index
< oldLen
) {
839 if (!indexes
.append(index
)) {
846 uint32_t count
= indexes
.length();
848 // We should use radix sort to be O(n), but this is uncommon
849 // enough that we'll punt til someone complains.
850 Vector
<uint32_t> scratch(cx
);
851 if (!scratch
.resize(count
)) {
854 MOZ_ALWAYS_TRUE(MergeSort(indexes
.begin(), count
, scratch
.begin(),
855 ReverseIndexComparator()));
858 uint32_t index
= UINT32_MAX
;
859 for (uint32_t i
= 0; i
< count
; i
++) {
860 MOZ_ASSERT(indexes
[i
] < index
, "indexes should never repeat");
864 ObjectOpResult deleteSucceeded
;
865 if (!DeleteElement(cx
, arr
, index
, deleteSucceeded
)) {
868 if (!deleteSucceeded
) {
877 // Update array length. Technically we should have been doing this
878 // throughout the loop, in step 19.d.iii.
879 arr
->setLength(newLen
);
882 if (desc
.hasWritable() && !desc
.writable()) {
883 Maybe
<PropertyInfo
> lengthProp
= arr
->lookup(cx
, id
);
884 MOZ_ASSERT(lengthProp
.isSome());
885 MOZ_ASSERT(lengthProp
->isCustomDataProperty());
886 PropertyFlags flags
= lengthProp
->flags();
887 flags
.clearFlag(PropertyFlag::Writable
);
888 if (!NativeObject::changeCustomDataPropAttributes(cx
, arr
, id
, flags
)) {
893 // All operations past here until the |!succeeded| code must be infallible,
894 // so that all element fields remain properly synchronized.
896 // Trim the initialized length, if needed, to preserve the <= length
897 // invariant. (Capacity was already reduced during element deletion, if
899 ObjectElements
* header
= arr
->getElementsHeader();
900 header
->initializedLength
= std::min(header
->initializedLength
, newLen
);
902 if (!arr
->isExtensible()) {
903 arr
->shrinkCapacityToInitializedLength(cx
);
906 if (desc
.hasWritable() && !desc
.writable()) {
907 arr
->setNonWritableLength(cx
);
911 return result
.fail(JSMSG_CANT_TRUNCATE_ARRAY
);
914 return result
.succeed();
917 static bool array_addProperty(JSContext
* cx
, HandleObject obj
, HandleId id
,
919 ArrayObject
* arr
= &obj
->as
<ArrayObject
>();
922 if (!IdIsIndex(id
, &index
)) {
926 uint32_t length
= arr
->length();
927 if (index
>= length
) {
928 MOZ_ASSERT(arr
->lengthIsWritable(),
929 "how'd this element get added if length is non-writable?");
930 arr
->setLength(index
+ 1);
935 static SharedShape
* AddLengthProperty(JSContext
* cx
,
936 Handle
<SharedShape
*> shape
) {
937 // Add the 'length' property for a newly created array shape.
939 MOZ_ASSERT(shape
->propMapLength() == 0);
940 MOZ_ASSERT(shape
->getObjectClass() == &ArrayObject::class_
);
942 RootedId
lengthId(cx
, NameToId(cx
->names().length
));
943 constexpr PropertyFlags flags
= {PropertyFlag::CustomDataProperty
,
944 PropertyFlag::Writable
};
946 Rooted
<SharedPropMap
*> map(cx
, shape
->propMap());
947 uint32_t mapLength
= shape
->propMapLength();
948 ObjectFlags objectFlags
= shape
->objectFlags();
950 if (!SharedPropMap::addCustomDataProperty(cx
, &ArrayObject::class_
, &map
,
951 &mapLength
, lengthId
, flags
,
956 return SharedShape::getPropMapShape(cx
, shape
->base(), shape
->numFixedSlots(),
957 map
, mapLength
, objectFlags
);
960 static bool IsArrayConstructor(const JSObject
* obj
) {
961 // Note: this also returns true for cross-realm Array constructors in the
963 return IsNativeFunction(obj
, ArrayConstructor
);
966 static bool IsArrayConstructor(const Value
& v
) {
967 return v
.isObject() && IsArrayConstructor(&v
.toObject());
970 bool js::IsCrossRealmArrayConstructor(JSContext
* cx
, JSObject
* obj
,
972 if (obj
->is
<WrapperObject
>()) {
973 obj
= CheckedUnwrapDynamic(obj
, cx
);
975 ReportAccessDenied(cx
);
981 IsArrayConstructor(obj
) && obj
->as
<JSFunction
>().realm() != cx
->realm();
985 static MOZ_ALWAYS_INLINE
bool IsArraySpecies(JSContext
* cx
,
986 HandleObject origArray
) {
987 if (MOZ_UNLIKELY(origArray
->is
<ProxyObject
>())) {
988 if (origArray
->getClass()->isDOMClass()) {
990 // We assume DOM proxies never return true for IsArray.
991 IsArrayAnswer answer
;
992 MOZ_ASSERT(Proxy::isArray(cx
, origArray
, &answer
));
993 MOZ_ASSERT(answer
== IsArrayAnswer::NotArray
);
1000 // 9.4.2.3 Step 4. Non-array objects always use the default constructor.
1001 if (!origArray
->is
<ArrayObject
>()) {
1005 if (cx
->realm()->arraySpeciesLookup
.tryOptimizeArray(
1006 cx
, &origArray
->as
<ArrayObject
>())) {
1011 if (!GetPropertyPure(cx
, origArray
, NameToId(cx
->names().constructor
),
1016 if (!IsArrayConstructor(ctor
)) {
1017 return ctor
.isUndefined();
1020 // 9.4.2.3 Step 6.c. Use the current realm's constructor if |ctor| is a
1021 // cross-realm Array constructor.
1022 if (cx
->realm() != ctor
.toObject().as
<JSFunction
>().realm()) {
1026 jsid speciesId
= PropertyKey::Symbol(cx
->wellKnownSymbols().species
);
1028 if (!GetGetterPure(cx
, &ctor
.toObject(), speciesId
, &getter
)) {
1036 return IsSelfHostedFunctionWithName(getter
, cx
->names().dollar_ArraySpecies_
);
1039 static bool ArraySpeciesCreate(JSContext
* cx
, HandleObject origArray
,
1040 uint64_t length
, MutableHandleObject arr
) {
1041 MOZ_ASSERT(length
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
1043 FixedInvokeArgs
<2> args(cx
);
1045 args
[0].setObject(*origArray
);
1046 args
[1].set(NumberValue(length
));
1048 RootedValue
rval(cx
);
1049 if (!CallSelfHostedFunction(cx
, cx
->names().ArraySpeciesCreate
,
1050 UndefinedHandleValue
, args
, &rval
)) {
1054 MOZ_ASSERT(rval
.isObject());
1055 arr
.set(&rval
.toObject());
1059 JSString
* js::ArrayToSource(JSContext
* cx
, HandleObject obj
) {
1060 AutoCycleDetector
detector(cx
, obj
);
1061 if (!detector
.init()) {
1065 JSStringBuilder
sb(cx
);
1067 if (detector
.foundCycle()) {
1068 if (!sb
.append("[]")) {
1071 return sb
.finishString();
1074 if (!sb
.append('[')) {
1079 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
1083 RootedValue
elt(cx
);
1084 for (uint64_t index
= 0; index
< length
; index
++) {
1086 if (!CheckForInterrupt(cx
) ||
1087 !HasAndGetElement(cx
, obj
, index
, &hole
, &elt
)) {
1091 /* Get element's character string. */
1094 str
= cx
->runtime()->emptyString
;
1096 str
= ValueToSource(cx
, elt
);
1102 /* Append element to buffer. */
1103 if (!sb
.append(str
)) {
1106 if (index
+ 1 != length
) {
1107 if (!sb
.append(", ")) {
1111 if (!sb
.append(',')) {
1117 /* Finalize the buffer. */
1118 if (!sb
.append(']')) {
1122 return sb
.finishString();
1125 static bool array_toSource(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1126 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "toSource");
1127 CallArgs args
= CallArgsFromVp(argc
, vp
);
1129 if (!args
.thisv().isObject()) {
1130 ReportIncompatible(cx
, args
);
1134 Rooted
<JSObject
*> obj(cx
, &args
.thisv().toObject());
1136 JSString
* str
= ArrayToSource(cx
, obj
);
1141 args
.rval().setString(str
);
1145 template <typename SeparatorOp
>
1146 static bool ArrayJoinDenseKernel(JSContext
* cx
, SeparatorOp sepOp
,
1147 Handle
<NativeObject
*> obj
, uint64_t length
,
1148 StringBuffer
& sb
, uint32_t* numProcessed
) {
1149 // This loop handles all elements up to initializedLength. If
1150 // length > initLength we rely on the second loop to add the
1152 MOZ_ASSERT(*numProcessed
== 0);
1153 uint64_t initLength
=
1154 std::min
<uint64_t>(obj
->getDenseInitializedLength(), length
);
1155 MOZ_ASSERT(initLength
<= UINT32_MAX
,
1156 "initialized length shouldn't exceed UINT32_MAX");
1157 uint32_t initLengthClamped
= uint32_t(initLength
);
1158 while (*numProcessed
< initLengthClamped
) {
1159 if (!CheckForInterrupt(cx
)) {
1164 Value elem
= obj
->getDenseElement(*numProcessed
);
1167 if (elem
.isString()) {
1168 if (!sb
.append(elem
.toString())) {
1171 } else if (elem
.isNumber()) {
1172 if (!NumberValueToStringBuffer(elem
, sb
)) {
1175 } else if (elem
.isBoolean()) {
1176 if (!BooleanToStringBuffer(elem
.toBoolean(), sb
)) {
1179 } else if (elem
.isObject() || elem
.isSymbol()) {
1181 * Object stringifying could modify the initialized length or make
1182 * the array sparse. Delegate it to a separate loop to keep this
1185 * Symbol stringifying is a TypeError, so into the slow path
1186 * with those as well.
1189 } else if (elem
.isBigInt()) {
1190 // ToString(bigint) doesn't access bigint.toString or
1191 // anything like that, so it can't mutate the array we're
1192 // walking through, so it *could* be handled here. We don't
1193 // do so yet for reasons of initial-implementation economy.
1196 MOZ_ASSERT(elem
.isMagic(JS_ELEMENTS_HOLE
) || elem
.isNullOrUndefined());
1200 if (++(*numProcessed
) != length
&& !sepOp(sb
)) {
1208 template <typename SeparatorOp
>
1209 static bool ArrayJoinKernel(JSContext
* cx
, SeparatorOp sepOp
, HandleObject obj
,
1210 uint64_t length
, StringBuffer
& sb
) {
1212 uint32_t numProcessed
= 0;
1214 if (IsPackedArrayOrNoExtraIndexedProperties(obj
, length
)) {
1215 if (!ArrayJoinDenseKernel
<SeparatorOp
>(cx
, sepOp
, obj
.as
<NativeObject
>(),
1216 length
, sb
, &numProcessed
)) {
1222 if (numProcessed
!= length
) {
1224 for (uint64_t i
= numProcessed
; i
< length
;) {
1225 if (!CheckForInterrupt(cx
)) {
1230 if (!GetArrayElement(cx
, obj
, i
, &v
)) {
1235 if (!v
.isNullOrUndefined()) {
1236 if (!ValueToStringBuffer(cx
, v
, sb
)) {
1242 if (++i
!= length
&& !sepOp(sb
)) {
1251 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
1252 // 22.1.3.13 Array.prototype.join ( separator )
1253 bool js::array_join(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1254 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "join");
1255 CallArgs args
= CallArgsFromVp(argc
, vp
);
1258 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
1263 AutoCycleDetector
detector(cx
, obj
);
1264 if (!detector
.init()) {
1268 if (detector
.foundCycle()) {
1269 args
.rval().setString(cx
->names().empty_
);
1275 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
1280 Rooted
<JSLinearString
*> sepstr(cx
);
1281 if (args
.hasDefined(0)) {
1282 JSString
* s
= ToString
<CanGC
>(cx
, args
[0]);
1286 sepstr
= s
->ensureLinear(cx
);
1291 sepstr
= cx
->names().comma_
;
1294 // Steps 5-8 (When the length is zero, directly return the empty string).
1296 args
.rval().setString(cx
->emptyString());
1300 // An optimized version of a special case of steps 5-8: when length==1 and
1301 // the 0th element is a string, ToString() of that element is a no-op and
1302 // so it can be immediately returned as the result.
1303 if (length
== 1 && obj
->is
<NativeObject
>()) {
1304 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
1305 if (nobj
->getDenseInitializedLength() == 1) {
1306 Value elem0
= nobj
->getDenseElement(0);
1307 if (elem0
.isString()) {
1308 args
.rval().set(elem0
);
1315 JSStringBuilder
sb(cx
);
1316 if (sepstr
->hasTwoByteChars() && !sb
.ensureTwoByteChars()) {
1320 // The separator will be added |length - 1| times, reserve space for that
1321 // so that we don't have to unnecessarily grow the buffer.
1322 size_t seplen
= sepstr
->length();
1324 if (length
> UINT32_MAX
) {
1325 ReportAllocationOverflow(cx
);
1328 CheckedInt
<uint32_t> res
=
1329 CheckedInt
<uint32_t>(seplen
) * (uint32_t(length
) - 1);
1330 if (!res
.isValid()) {
1331 ReportAllocationOverflow(cx
);
1335 if (!sb
.reserve(res
.value())) {
1340 // Various optimized versions of steps 6-7.
1342 auto sepOp
= [](StringBuffer
&) { return true; };
1343 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1346 } else if (seplen
== 1) {
1347 char16_t c
= sepstr
->latin1OrTwoByteChar(0);
1348 if (c
<= JSString::MAX_LATIN1_CHAR
) {
1349 Latin1Char l1char
= Latin1Char(c
);
1350 auto sepOp
= [l1char
](StringBuffer
& sb
) { return sb
.append(l1char
); };
1351 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1355 auto sepOp
= [c
](StringBuffer
& sb
) { return sb
.append(c
); };
1356 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1361 Handle
<JSLinearString
*> sepHandle
= sepstr
;
1362 auto sepOp
= [sepHandle
](StringBuffer
& sb
) { return sb
.append(sepHandle
); };
1363 if (!ArrayJoinKernel(cx
, sepOp
, obj
, length
, sb
)) {
1369 JSString
* str
= sb
.finishString();
1374 args
.rval().setString(str
);
1378 // ES2017 draft rev f8a9be8ea4bd97237d176907a1e3080dce20c68f
1379 // 22.1.3.27 Array.prototype.toLocaleString ([ reserved1 [ , reserved2 ] ])
1380 // ES2017 Intl draft rev 78bbe7d1095f5ff3760ac4017ed366026e4cb276
1381 // 13.4.1 Array.prototype.toLocaleString ([ locales [ , options ]])
1382 static bool array_toLocaleString(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1383 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype",
1386 CallArgs args
= CallArgsFromVp(argc
, vp
);
1389 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
1394 // Avoid calling into self-hosted code if the array is empty.
1395 if (obj
->is
<ArrayObject
>() && obj
->as
<ArrayObject
>().length() == 0) {
1396 args
.rval().setString(cx
->names().empty_
);
1400 AutoCycleDetector
detector(cx
, obj
);
1401 if (!detector
.init()) {
1405 if (detector
.foundCycle()) {
1406 args
.rval().setString(cx
->names().empty_
);
1410 FixedInvokeArgs
<2> args2(cx
);
1412 args2
[0].set(args
.get(0));
1413 args2
[1].set(args
.get(1));
1416 RootedValue
thisv(cx
, ObjectValue(*obj
));
1417 return CallSelfHostedFunction(cx
, cx
->names().ArrayToLocaleString
, thisv
,
1418 args2
, args
.rval());
1421 /* vector must point to rooted memory. */
1422 static bool SetArrayElements(JSContext
* cx
, HandleObject obj
, uint64_t start
,
1423 uint32_t count
, const Value
* vector
) {
1424 MOZ_ASSERT(count
<= MAX_ARRAY_INDEX
);
1425 MOZ_ASSERT(start
+ count
< uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
));
1431 if (!ObjectMayHaveExtraIndexedProperties(obj
) && start
<= UINT32_MAX
) {
1432 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
1433 DenseElementResult result
=
1434 nobj
->setOrExtendDenseElements(cx
, uint32_t(start
), vector
, count
);
1435 if (result
!= DenseElementResult::Incomplete
) {
1436 return result
== DenseElementResult::Success
;
1441 const Value
* end
= vector
+ count
;
1442 while (vector
< end
) {
1443 if (!CheckForInterrupt(cx
)) {
1447 if (!ToId(cx
, start
++, &id
)) {
1451 if (!SetProperty(cx
, obj
, id
, HandleValue::fromMarkedLocation(vector
++))) {
1459 static DenseElementResult
ArrayReverseDenseKernel(JSContext
* cx
,
1460 Handle
<NativeObject
*> obj
,
1462 MOZ_ASSERT(length
> 1);
1464 // If there are no elements, we're done.
1465 if (obj
->getDenseInitializedLength() == 0) {
1466 return DenseElementResult::Success
;
1469 if (!obj
->isExtensible()) {
1470 return DenseElementResult::Incomplete
;
1473 if (!IsPackedArray(obj
)) {
1475 * It's actually surprisingly complicated to reverse an array due
1476 * to the orthogonality of array length and array capacity while
1477 * handling leading and trailing holes correctly. Reversing seems
1478 * less likely to be a common operation than other array
1479 * mass-mutation methods, so for now just take a probably-small
1480 * memory hit (in the absence of too many holes in the array at
1481 * its start) and ensure that the capacity is sufficient to hold
1482 * all the elements in the array if it were full.
1484 DenseElementResult result
= obj
->ensureDenseElements(cx
, length
, 0);
1485 if (result
!= DenseElementResult::Success
) {
1489 /* Fill out the array's initialized length to its proper length. */
1490 obj
->ensureDenseInitializedLength(length
, 0);
1493 if (!obj
->denseElementsMaybeInIteration() &&
1494 !cx
->zone()->needsIncrementalBarrier()) {
1495 obj
->reverseDenseElementsNoPreBarrier(length
);
1496 return DenseElementResult::Success
;
1499 auto setElementMaybeHole
= [](JSContext
* cx
, Handle
<NativeObject
*> obj
,
1500 uint32_t index
, const Value
& val
) {
1501 if (MOZ_LIKELY(!val
.isMagic(JS_ELEMENTS_HOLE
))) {
1502 obj
->setDenseElement(index
, val
);
1506 obj
->setDenseElementHole(index
);
1507 return SuppressDeletedProperty(cx
, obj
, PropertyKey::Int(index
));
1510 RootedValue
origlo(cx
), orighi(cx
);
1512 uint32_t lo
= 0, hi
= length
- 1;
1513 for (; lo
< hi
; lo
++, hi
--) {
1514 origlo
= obj
->getDenseElement(lo
);
1515 orighi
= obj
->getDenseElement(hi
);
1516 if (!setElementMaybeHole(cx
, obj
, lo
, orighi
)) {
1517 return DenseElementResult::Failure
;
1519 if (!setElementMaybeHole(cx
, obj
, hi
, origlo
)) {
1520 return DenseElementResult::Failure
;
1524 return DenseElementResult::Success
;
1527 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
1528 // 22.1.3.21 Array.prototype.reverse ( )
1529 static bool array_reverse(JSContext
* cx
, unsigned argc
, Value
* vp
) {
1530 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "reverse");
1531 CallArgs args
= CallArgsFromVp(argc
, vp
);
1534 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
1541 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
1545 // An empty array or an array with length 1 is already reversed.
1547 args
.rval().setObject(*obj
);
1551 if (IsPackedArrayOrNoExtraIndexedProperties(obj
, len
) && len
<= UINT32_MAX
) {
1552 DenseElementResult result
=
1553 ArrayReverseDenseKernel(cx
, obj
.as
<NativeObject
>(), uint32_t(len
));
1554 if (result
!= DenseElementResult::Incomplete
) {
1556 * Per ECMA-262, don't update the length of the array, even if the new
1557 * array has trailing holes (and thus the original array began with
1560 args
.rval().setObject(*obj
);
1561 return result
== DenseElementResult::Success
;
1566 RootedValue
lowval(cx
), hival(cx
);
1567 for (uint64_t i
= 0, half
= len
/ 2; i
< half
; i
++) {
1569 if (!CheckForInterrupt(cx
) ||
1570 !HasAndGetElement(cx
, obj
, i
, &hole
, &lowval
) ||
1571 !HasAndGetElement(cx
, obj
, len
- i
- 1, &hole2
, &hival
)) {
1575 if (!hole
&& !hole2
) {
1576 if (!SetArrayElement(cx
, obj
, i
, hival
)) {
1579 if (!SetArrayElement(cx
, obj
, len
- i
- 1, lowval
)) {
1582 } else if (hole
&& !hole2
) {
1583 if (!SetArrayElement(cx
, obj
, i
, hival
)) {
1586 if (!DeletePropertyOrThrow(cx
, obj
, len
- i
- 1)) {
1589 } else if (!hole
&& hole2
) {
1590 if (!DeletePropertyOrThrow(cx
, obj
, i
)) {
1593 if (!SetArrayElement(cx
, obj
, len
- i
- 1, lowval
)) {
1597 // No action required.
1602 args
.rval().setObject(*obj
);
1606 static inline bool CompareStringValues(JSContext
* cx
, const Value
& a
,
1607 const Value
& b
, bool* lessOrEqualp
) {
1608 if (!CheckForInterrupt(cx
)) {
1612 JSString
* astr
= a
.toString();
1613 JSString
* bstr
= b
.toString();
1615 if (!CompareStrings(cx
, astr
, bstr
, &result
)) {
1619 *lessOrEqualp
= (result
<= 0);
1623 static const uint64_t powersOf10
[] = {
1624 1, 10, 100, 1000, 10000, 100000,
1625 1000000, 10000000, 100000000, 1000000000, 1000000000000ULL};
1627 static inline unsigned NumDigitsBase10(uint32_t n
) {
1629 * This is just floor_log10(n) + 1
1630 * Algorithm taken from
1631 * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
1633 uint32_t log2
= CeilingLog2(n
);
1634 uint32_t t
= log2
* 1233 >> 12;
1635 return t
- (n
< powersOf10
[t
]) + 1;
1638 static inline bool CompareLexicographicInt32(const Value
& a
, const Value
& b
,
1639 bool* lessOrEqualp
) {
1640 int32_t aint
= a
.toInt32();
1641 int32_t bint
= b
.toInt32();
1644 * If both numbers are equal ... trivial
1645 * If only one of both is negative --> arithmetic comparison as char code
1646 * of '-' is always less than any other digit
1647 * If both numbers are negative convert them to positive and continue
1651 *lessOrEqualp
= true;
1652 } else if ((aint
< 0) && (bint
>= 0)) {
1653 *lessOrEqualp
= true;
1654 } else if ((aint
>= 0) && (bint
< 0)) {
1655 *lessOrEqualp
= false;
1657 uint32_t auint
= Abs(aint
);
1658 uint32_t buint
= Abs(bint
);
1661 * ... get number of digits of both integers.
1662 * If they have the same number of digits --> arithmetic comparison.
1663 * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
1664 * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
1666 unsigned digitsa
= NumDigitsBase10(auint
);
1667 unsigned digitsb
= NumDigitsBase10(buint
);
1668 if (digitsa
== digitsb
) {
1669 *lessOrEqualp
= (auint
<= buint
);
1670 } else if (digitsa
> digitsb
) {
1671 MOZ_ASSERT((digitsa
- digitsb
) < std::size(powersOf10
));
1673 (uint64_t(auint
) < uint64_t(buint
) * powersOf10
[digitsa
- digitsb
]);
1674 } else { /* if (digitsb > digitsa) */
1675 MOZ_ASSERT((digitsb
- digitsa
) < std::size(powersOf10
));
1677 (uint64_t(auint
) * powersOf10
[digitsb
- digitsa
] <= uint64_t(buint
));
1684 template <typename Char1
, typename Char2
>
1685 static inline bool CompareSubStringValues(JSContext
* cx
, const Char1
* s1
,
1686 size_t len1
, const Char2
* s2
,
1687 size_t len2
, bool* lessOrEqualp
) {
1688 if (!CheckForInterrupt(cx
)) {
1696 int32_t result
= CompareChars(s1
, len1
, s2
, len2
);
1697 *lessOrEqualp
= (result
<= 0);
1703 struct SortComparatorStrings
{
1704 JSContext
* const cx
;
1706 explicit SortComparatorStrings(JSContext
* cx
) : cx(cx
) {}
1708 bool operator()(const Value
& a
, const Value
& b
, bool* lessOrEqualp
) {
1709 return CompareStringValues(cx
, a
, b
, lessOrEqualp
);
1713 struct SortComparatorLexicographicInt32
{
1714 bool operator()(const Value
& a
, const Value
& b
, bool* lessOrEqualp
) {
1715 return CompareLexicographicInt32(a
, b
, lessOrEqualp
);
1719 struct StringifiedElement
{
1722 size_t elementIndex
;
1725 struct SortComparatorStringifiedElements
{
1726 JSContext
* const cx
;
1727 const StringBuffer
& sb
;
1729 SortComparatorStringifiedElements(JSContext
* cx
, const StringBuffer
& sb
)
1732 bool operator()(const StringifiedElement
& a
, const StringifiedElement
& b
,
1733 bool* lessOrEqualp
) {
1734 size_t lenA
= a
.charsEnd
- a
.charsBegin
;
1735 size_t lenB
= b
.charsEnd
- b
.charsBegin
;
1737 if (sb
.isUnderlyingBufferLatin1()) {
1738 return CompareSubStringValues(cx
, sb
.rawLatin1Begin() + a
.charsBegin
,
1739 lenA
, sb
.rawLatin1Begin() + b
.charsBegin
,
1740 lenB
, lessOrEqualp
);
1743 return CompareSubStringValues(cx
, sb
.rawTwoByteBegin() + a
.charsBegin
, lenA
,
1744 sb
.rawTwoByteBegin() + b
.charsBegin
, lenB
,
1749 struct NumericElement
{
1751 size_t elementIndex
;
1754 static bool ComparatorNumericLeftMinusRight(const NumericElement
& a
,
1755 const NumericElement
& b
,
1756 bool* lessOrEqualp
) {
1757 *lessOrEqualp
= std::isunordered(a
.dv
, b
.dv
) || (a
.dv
<= b
.dv
);
1761 static bool ComparatorNumericRightMinusLeft(const NumericElement
& a
,
1762 const NumericElement
& b
,
1763 bool* lessOrEqualp
) {
1764 *lessOrEqualp
= std::isunordered(a
.dv
, b
.dv
) || (b
.dv
<= a
.dv
);
1768 using ComparatorNumeric
= bool (*)(const NumericElement
&, const NumericElement
&,
1771 static const ComparatorNumeric SortComparatorNumerics
[] = {
1772 nullptr, nullptr, ComparatorNumericLeftMinusRight
,
1773 ComparatorNumericRightMinusLeft
};
1775 static bool ComparatorInt32LeftMinusRight(const Value
& a
, const Value
& b
,
1776 bool* lessOrEqualp
) {
1777 *lessOrEqualp
= (a
.toInt32() <= b
.toInt32());
1781 static bool ComparatorInt32RightMinusLeft(const Value
& a
, const Value
& b
,
1782 bool* lessOrEqualp
) {
1783 *lessOrEqualp
= (b
.toInt32() <= a
.toInt32());
1787 using ComparatorInt32
= bool (*)(const Value
&, const Value
&, bool*);
1789 static const ComparatorInt32 SortComparatorInt32s
[] = {
1790 nullptr, nullptr, ComparatorInt32LeftMinusRight
,
1791 ComparatorInt32RightMinusLeft
};
1793 // Note: Values for this enum must match up with SortComparatorNumerics
1794 // and SortComparatorInt32s.
1795 enum ComparatorMatchResult
{
1798 Match_LeftMinusRight
,
1799 Match_RightMinusLeft
1805 * Specialize behavior for comparator functions with particular common bytecode
1806 * patterns: namely, |return x - y| and |return y - x|.
1808 static ComparatorMatchResult
MatchNumericComparator(JSContext
* cx
,
1810 if (!obj
->is
<JSFunction
>()) {
1814 RootedFunction
fun(cx
, &obj
->as
<JSFunction
>());
1815 if (!fun
->isInterpreted() || fun
->isClassConstructor()) {
1819 JSScript
* script
= JSFunction::getOrCreateScript(cx
, fun
);
1821 return Match_Failure
;
1824 jsbytecode
* pc
= script
->code();
1826 uint16_t arg0
, arg1
;
1827 if (JSOp(*pc
) != JSOp::GetArg
) {
1830 arg0
= GET_ARGNO(pc
);
1831 pc
+= JSOpLength_GetArg
;
1833 if (JSOp(*pc
) != JSOp::GetArg
) {
1836 arg1
= GET_ARGNO(pc
);
1837 pc
+= JSOpLength_GetArg
;
1839 if (JSOp(*pc
) != JSOp::Sub
) {
1842 pc
+= JSOpLength_Sub
;
1844 if (JSOp(*pc
) != JSOp::Return
) {
1848 if (arg0
== 0 && arg1
== 1) {
1849 return Match_LeftMinusRight
;
1852 if (arg0
== 1 && arg1
== 0) {
1853 return Match_RightMinusLeft
;
1859 template <typename K
, typename C
>
1860 static inline bool MergeSortByKey(K keys
, size_t len
, K scratch
, C comparator
,
1861 MutableHandle
<GCVector
<Value
>> vec
) {
1862 MOZ_ASSERT(vec
.length() >= len
);
1865 if (!MergeSort(keys
, len
, scratch
, comparator
)) {
1870 * Reorder vec by keys in-place, going element by element. When an out-of-
1871 * place element is encountered, move that element to its proper position,
1872 * displacing whatever element was at *that* point to its proper position,
1873 * and so on until an element must be moved to the current position.
1875 * At each outer iteration all elements up to |i| are sorted. If
1876 * necessary each inner iteration moves some number of unsorted elements
1877 * (including |i|) directly to sorted position. Thus on completion |*vec|
1878 * is sorted, and out-of-position elements have moved once. Complexity is
1879 * Θ(len) + O(len) == O(2*len), with each element visited at most twice.
1881 for (size_t i
= 0; i
< len
; i
++) {
1882 size_t j
= keys
[i
].elementIndex
;
1884 continue; // fixed point
1887 MOZ_ASSERT(j
> i
, "Everything less than |i| should be in the right place!");
1890 size_t k
= keys
[j
].elementIndex
;
1891 keys
[j
].elementIndex
= j
;
1896 // We could assert the loop invariant that |i == keys[i].elementIndex|
1897 // here if we synced |keys[i].elementIndex|. But doing so would render
1898 // the assertion vacuous, so don't bother, even in debug builds.
1906 * Sort Values as strings.
1908 * To minimize #conversions, SortLexicographically() first converts all Values
1909 * to strings at once, then sorts the elements by these cached strings.
1911 static bool SortLexicographically(JSContext
* cx
,
1912 MutableHandle
<GCVector
<Value
>> vec
,
1914 MOZ_ASSERT(vec
.length() >= len
);
1916 StringBuffer
sb(cx
);
1917 Vector
<StringifiedElement
, 0, TempAllocPolicy
> strElements(cx
);
1919 /* MergeSort uses the upper half as scratch space. */
1920 if (!strElements
.resize(2 * len
)) {
1924 /* Convert Values to strings. */
1926 for (size_t i
= 0; i
< len
; i
++) {
1927 if (!CheckForInterrupt(cx
)) {
1931 if (!ValueToStringBuffer(cx
, vec
[i
], sb
)) {
1935 strElements
[i
] = {cursor
, sb
.length(), i
};
1936 cursor
= sb
.length();
1939 /* Sort Values in vec alphabetically. */
1940 return MergeSortByKey(strElements
.begin(), len
, strElements
.begin() + len
,
1941 SortComparatorStringifiedElements(cx
, sb
), vec
);
1945 * Sort Values as numbers.
1947 * To minimize #conversions, SortNumerically first converts all Values to
1948 * numerics at once, then sorts the elements by these cached numerics.
1950 static bool SortNumerically(JSContext
* cx
, MutableHandle
<GCVector
<Value
>> vec
,
1951 size_t len
, ComparatorMatchResult comp
) {
1952 MOZ_ASSERT(vec
.length() >= len
);
1954 Vector
<NumericElement
, 0, TempAllocPolicy
> numElements(cx
);
1956 /* MergeSort uses the upper half as scratch space. */
1957 if (!numElements
.resize(2 * len
)) {
1961 /* Convert Values to numerics. */
1962 for (size_t i
= 0; i
< len
; i
++) {
1963 if (!CheckForInterrupt(cx
)) {
1968 if (!ToNumber(cx
, vec
[i
], &dv
)) {
1972 numElements
[i
] = {dv
, i
};
1975 /* Sort Values in vec numerically. */
1976 return MergeSortByKey(numElements
.begin(), len
, numElements
.begin() + len
,
1977 SortComparatorNumerics
[comp
], vec
);
1980 static bool FillWithUndefined(JSContext
* cx
, HandleObject obj
, uint32_t start
,
1982 MOZ_ASSERT(start
< start
+ count
,
1983 "count > 0 and start + count doesn't overflow");
1986 if (ObjectMayHaveExtraIndexedProperties(obj
)) {
1990 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
1991 if (!nobj
->isExtensible()) {
1995 if (obj
->is
<ArrayObject
>() && !obj
->as
<ArrayObject
>().lengthIsWritable() &&
1996 start
+ count
>= obj
->as
<ArrayObject
>().length()) {
2000 DenseElementResult result
= nobj
->ensureDenseElements(cx
, start
, count
);
2001 if (result
!= DenseElementResult::Success
) {
2002 if (result
== DenseElementResult::Failure
) {
2005 MOZ_ASSERT(result
== DenseElementResult::Incomplete
);
2009 if (obj
->is
<ArrayObject
>() &&
2010 start
+ count
>= obj
->as
<ArrayObject
>().length()) {
2011 obj
->as
<ArrayObject
>().setLength(start
+ count
);
2014 for (uint32_t i
= 0; i
< count
; i
++) {
2015 nobj
->setDenseElement(start
+ i
, UndefinedHandleValue
);
2021 for (uint32_t i
= 0; i
< count
; i
++) {
2022 if (!CheckForInterrupt(cx
) ||
2023 !SetArrayElement(cx
, obj
, start
+ i
, UndefinedHandleValue
)) {
2031 static bool ArraySortWithoutComparator(JSContext
* cx
, Handle
<JSObject
*> obj
,
2033 ComparatorMatchResult comp
) {
2034 MOZ_ASSERT(length
> 1);
2036 if (length
> UINT32_MAX
) {
2037 ReportAllocationOverflow(cx
);
2040 uint32_t len
= uint32_t(length
);
2043 * We need a temporary array of 2 * len Value to hold the array elements
2044 * and the scratch space for merge sort. Check that its size does not
2045 * overflow size_t, which would allow for indexing beyond the end of the
2048 #if JS_BITS_PER_WORD == 32
2049 if (size_t(len
) > size_t(-1) / (2 * sizeof(Value
))) {
2050 ReportAllocationOverflow(cx
);
2057 Rooted
<GCVector
<Value
>> vec(cx
, GCVector
<Value
>(cx
));
2058 if (!vec
.reserve(2 * size_t(len
))) {
2063 * By ECMA 262, 15.4.4.11, a property that does not exist (which we
2064 * call a "hole") is always greater than an existing property with
2065 * value undefined and that is always greater than any other property.
2066 * Thus to sort holes and undefs we simply count them, sort the rest
2067 * of elements, append undefs after them and then make holes after
2071 bool allStrings
= true;
2072 bool allInts
= true;
2074 if (IsPackedArray(obj
)) {
2075 Handle
<ArrayObject
*> array
= obj
.as
<ArrayObject
>();
2077 for (uint32_t i
= 0; i
< len
; i
++) {
2078 if (!CheckForInterrupt(cx
)) {
2082 v
.set(array
->getDenseElement(i
));
2083 MOZ_ASSERT(!v
.isMagic(JS_ELEMENTS_HOLE
));
2084 if (v
.isUndefined()) {
2088 vec
.infallibleAppend(v
);
2089 allStrings
= allStrings
&& v
.isString();
2090 allInts
= allInts
&& v
.isInt32();
2093 for (uint32_t i
= 0; i
< len
; i
++) {
2094 if (!CheckForInterrupt(cx
)) {
2099 if (!HasAndGetElement(cx
, obj
, i
, &hole
, &v
)) {
2105 if (v
.isUndefined()) {
2109 vec
.infallibleAppend(v
);
2110 allStrings
= allStrings
&& v
.isString();
2111 allInts
= allInts
&& v
.isInt32();
2116 * If the array only contains holes, we're done. But if it contains
2117 * undefs, those must be sorted to the front of the array.
2120 if (n
== 0 && undefs
== 0) {
2124 /* Here len == n + undefs + number_of_holes. */
2125 if (comp
== Match_None
) {
2127 * Sort using the default comparator converting all elements to
2131 MOZ_ALWAYS_TRUE(vec
.resize(n
* 2));
2132 if (!MergeSort(vec
.begin(), n
, vec
.begin() + n
,
2133 SortComparatorStrings(cx
))) {
2136 } else if (allInts
) {
2137 MOZ_ALWAYS_TRUE(vec
.resize(n
* 2));
2138 if (!MergeSort(vec
.begin(), n
, vec
.begin() + n
,
2139 SortComparatorLexicographicInt32())) {
2143 if (!SortLexicographically(cx
, &vec
, n
)) {
2149 MOZ_ALWAYS_TRUE(vec
.resize(n
* 2));
2150 if (!MergeSort(vec
.begin(), n
, vec
.begin() + n
,
2151 SortComparatorInt32s
[comp
])) {
2155 if (!SortNumerically(cx
, &vec
, n
, comp
)) {
2161 if (!SetArrayElements(cx
, obj
, 0, uint32_t(n
), vec
.begin())) {
2166 /* Set undefs that sorted after the rest of elements. */
2168 if (!FillWithUndefined(cx
, obj
, n
, undefs
)) {
2174 /* Re-create any holes that sorted to the end of the array. */
2175 for (uint32_t i
= n
; i
< len
; i
++) {
2176 if (!CheckForInterrupt(cx
) || !DeletePropertyOrThrow(cx
, obj
, i
)) {
2183 void ArraySortData::init(JSObject
* obj
, JSObject
* comparator
, ValueVector
&& vec
,
2184 uint32_t length
, uint32_t denseLen
) {
2185 MOZ_ASSERT(!vec
.empty(), "must have items to sort");
2186 MOZ_ASSERT(denseLen
<= length
);
2189 comparator_
= comparator
;
2191 this->length
= length
;
2192 this->denseLen
= denseLen
;
2193 this->vec
= std::move(vec
);
2195 auto getComparatorKind
= [](JSContext
* cx
, JSObject
* comparator
) {
2196 if (!comparator
->is
<JSFunction
>()) {
2197 return ComparatorKind::Unoptimized
;
2199 JSFunction
* fun
= &comparator
->as
<JSFunction
>();
2200 if (!fun
->hasJitEntry() || fun
->isClassConstructor()) {
2201 return ComparatorKind::Unoptimized
;
2203 if (fun
->realm() == cx
->realm() && fun
->nargs() <= ComparatorActualArgs
) {
2204 return ComparatorKind::JSSameRealmNoRectifier
;
2206 return ComparatorKind::JS
;
2208 comparatorKind_
= getComparatorKind(cx(), comparator
);
2211 // This function handles sorting without a comparator function (or with a
2212 // trivial comparator function that we can pattern match) by calling
2213 // ArraySortWithoutComparator.
2215 // If there's a non-trivial comparator function, it initializes the
2216 // ArraySortData struct for ArraySortData::sortWithComparator. This function
2217 // must be called next to perform the sorting.
2219 // This is separate from ArraySortData::sortWithComparator because it lets the
2220 // compiler generate better code for ArraySortData::sortWithComparator.
2222 // https://tc39.es/ecma262/#sec-array.prototype.sort
2223 // 23.1.3.30 Array.prototype.sort ( comparefn )
2224 static MOZ_ALWAYS_INLINE
bool ArraySortPrologue(JSContext
* cx
,
2225 Handle
<Value
> thisv
,
2226 Handle
<Value
> comparefn
,
2227 ArraySortData
* d
, bool* done
) {
2229 if (MOZ_UNLIKELY(!comparefn
.isUndefined() && !IsCallable(comparefn
))) {
2230 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_SORT_ARG
);
2235 Rooted
<JSObject
*> obj(cx
, ToObject(cx
, thisv
));
2242 if (MOZ_UNLIKELY(!GetLengthPropertyInlined(cx
, obj
, &length
))) {
2246 // Arrays with less than two elements remain unchanged when sorted.
2248 d
->setReturnValue(obj
);
2253 // Use a fast path if there's no comparator or if the comparator is a function
2254 // that we can pattern match.
2256 ComparatorMatchResult comp
= Match_None
;
2257 if (comparefn
.isObject()) {
2258 comp
= MatchNumericComparator(cx
, &comparefn
.toObject());
2259 if (comp
== Match_Failure
) {
2262 if (comp
== Match_None
) {
2263 // Pattern matching failed.
2267 if (!ArraySortWithoutComparator(cx
, obj
, length
, comp
)) {
2270 d
->setReturnValue(obj
);
2275 // Ensure length * 2 (used below) doesn't overflow UINT32_MAX.
2276 if (MOZ_UNLIKELY(length
> UINT32_MAX
/ 2)) {
2277 ReportAllocationOverflow(cx
);
2280 uint32_t len
= uint32_t(length
);
2282 // Merge sort requires extra scratch space.
2283 bool needsScratchSpace
= len
>= ArraySortData::InsertionSortLimit
;
2285 Rooted
<ArraySortData::ValueVector
> vec(cx
);
2286 if (MOZ_UNLIKELY(!vec
.reserve(needsScratchSpace
? (2 * len
) : len
))) {
2287 ReportOutOfMemory(cx
);
2291 // Append elements to the vector. Skip holes.
2292 if (IsPackedArray(obj
)) {
2293 Handle
<ArrayObject
*> array
= obj
.as
<ArrayObject
>();
2294 const Value
* elements
= array
->getDenseElements();
2295 vec
.infallibleAppend(elements
, len
);
2298 for (uint32_t i
= 0; i
< len
; i
++) {
2299 if (!CheckForInterrupt(cx
)) {
2304 if (!HasAndGetElement(cx
, obj
, i
, &hole
, &v
)) {
2310 vec
.infallibleAppend(v
);
2312 // If there are only holes, the object is already sorted.
2314 d
->setReturnValue(obj
);
2320 uint32_t denseLen
= vec
.length();
2321 if (needsScratchSpace
) {
2322 MOZ_ALWAYS_TRUE(vec
.resize(denseLen
* 2));
2324 d
->init(obj
, &comparefn
.toObject(), std::move(vec
.get()), len
, denseLen
);
2326 // Continue in ArraySortData::sortWithComparator.
2331 static ArraySortResult
CallComparatorSlow(ArraySortData
* d
, const Value
& x
,
2333 JSContext
* cx
= d
->cx();
2334 FixedInvokeArgs
<2> callArgs(cx
);
2337 Rooted
<Value
> comparefn(cx
, ObjectValue(*d
->comparator()));
2338 Rooted
<Value
> rval(cx
);
2339 if (!js::Call(cx
, comparefn
, UndefinedHandleValue
, callArgs
, &rval
)) {
2340 return ArraySortResult::Failure
;
2342 d
->setComparatorReturnValue(rval
);
2343 return ArraySortResult::Done
;
2346 static MOZ_ALWAYS_INLINE ArraySortResult
2347 MaybeYieldToComparator(ArraySortData
* d
, const Value
& x
, const Value
& y
) {
2348 // https://tc39.es/ecma262/#sec-comparearrayelements
2349 // 23.1.3.30.2 CompareArrayElements ( x, y, comparefn )
2352 if (x
.isUndefined()) {
2353 d
->setComparatorReturnValue(Int32Value(y
.isUndefined() ? 0 : 1));
2354 return ArraySortResult::Done
;
2358 if (y
.isUndefined()) {
2359 d
->setComparatorReturnValue(Int32Value(-1));
2360 return ArraySortResult::Done
;
2363 // Step 4. Yield to the JIT trampoline (or js::array_sort) if the comparator
2364 // is a JS function we can call more efficiently from JIT code.
2365 auto kind
= d
->comparatorKind();
2366 if (MOZ_LIKELY(kind
!= ArraySortData::ComparatorKind::Unoptimized
)) {
2367 d
->setComparatorArgs(x
, y
);
2368 return (kind
== ArraySortData::ComparatorKind::JSSameRealmNoRectifier
)
2369 ? ArraySortResult::CallJSSameRealmNoRectifier
2370 : ArraySortResult::CallJS
;
2372 return CallComparatorSlow(d
, x
, y
);
2375 static MOZ_ALWAYS_INLINE
bool RvalIsLessOrEqual(ArraySortData
* data
,
2376 bool* lessOrEqual
) {
2377 // https://tc39.es/ecma262/#sec-comparearrayelements
2378 // 23.1.3.30.2 CompareArrayElements ( x, y, comparefn )
2380 // Fast path for int32 return values.
2381 Value rval
= data
->comparatorReturnValue();
2382 if (MOZ_LIKELY(rval
.isInt32())) {
2383 *lessOrEqual
= rval
.toInt32() <= 0;
2388 Rooted
<Value
> rvalRoot(data
->cx(), rval
);
2390 if (MOZ_UNLIKELY(!ToNumber(data
->cx(), rvalRoot
, &d
))) {
2395 *lessOrEqual
= std::isnan(d
) ? true : (d
<= 0);
2399 static void CopyValues(Value
* out
, const Value
* list
, uint32_t start
,
2401 for (uint32_t i
= start
; i
<= end
; i
++) {
2407 ArraySortResult
ArraySortData::sortWithComparator(ArraySortData
* d
) {
2408 JSContext
* cx
= d
->cx();
2411 // This function is like a generator that is called repeatedly from the JIT
2412 // trampoline or js::array_sort. Resume the sorting algorithm where we left
2413 // off before calling the comparator.
2415 case State::Initial
:
2417 case State::InsertionSortCall1
:
2418 goto insertion_sort_call1
;
2419 case State::InsertionSortCall2
:
2420 goto insertion_sort_call2
;
2421 case State::MergeSortCall1
:
2422 goto merge_sort_call1
;
2423 case State::MergeSortCall2
:
2424 goto merge_sort_call2
;
2427 d
->list
= vec
.begin();
2429 // Use insertion sort for small arrays.
2430 if (d
->denseLen
< InsertionSortLimit
) {
2431 for (d
->i
= 1; d
->i
< d
->denseLen
; d
->i
++) {
2432 d
->item
= vec
[d
->i
];
2436 ArraySortResult res
= MaybeYieldToComparator(d
, vec
[d
->j
], d
->item
);
2437 if (res
!= ArraySortResult::Done
) {
2438 d
->state
= State::InsertionSortCall1
;
2442 insertion_sort_call1
:
2444 if (!RvalIsLessOrEqual(d
, &lessOrEqual
)) {
2445 return ArraySortResult::Failure
;
2450 vec
[d
->j
+ 1] = vec
[d
->j
];
2451 } while (d
->j
-- > 0);
2452 vec
[d
->j
+ 1] = d
->item
;
2455 static constexpr size_t InitialWindowSize
= 4;
2457 // Use insertion sort for initial ranges.
2458 for (d
->start
= 0; d
->start
< d
->denseLen
- 1;
2459 d
->start
+= InitialWindowSize
) {
2461 std::min
<uint32_t>(d
->start
+ InitialWindowSize
- 1, d
->denseLen
- 1);
2462 for (d
->i
= d
->start
+ 1; d
->i
<= d
->end
; d
->i
++) {
2463 d
->item
= vec
[d
->i
];
2467 ArraySortResult res
= MaybeYieldToComparator(d
, vec
[d
->j
], d
->item
);
2468 if (res
!= ArraySortResult::Done
) {
2469 d
->state
= State::InsertionSortCall2
;
2473 insertion_sort_call2
:
2475 if (!RvalIsLessOrEqual(d
, &lessOrEqual
)) {
2476 return ArraySortResult::Failure
;
2481 vec
[d
->j
+ 1] = vec
[d
->j
];
2482 } while (d
->j
-- > d
->start
);
2483 vec
[d
->j
+ 1] = d
->item
;
2487 // Merge sort. Set d->out to scratch space initially.
2488 d
->out
= vec
.begin() + d
->denseLen
;
2489 for (d
->windowSize
= InitialWindowSize
; d
->windowSize
< d
->denseLen
;
2490 d
->windowSize
*= 2) {
2491 for (d
->start
= 0; d
->start
< d
->denseLen
;
2492 d
->start
+= 2 * d
->windowSize
) {
2493 // The midpoint between the two subarrays.
2494 d
->mid
= d
->start
+ d
->windowSize
- 1;
2496 // To keep from going over the edge.
2497 d
->end
= std::min
<uint32_t>(d
->start
+ 2 * d
->windowSize
- 1,
2500 // Merge comparator-sorted slices list[start..<=mid] and
2501 // list[mid+1..<=end], storing the merged sequence in out[start..<=end].
2503 // Skip lopsided runs to avoid doing useless work.
2504 if (d
->mid
>= d
->end
) {
2505 CopyValues(d
->out
, d
->list
, d
->start
, d
->end
);
2509 // Skip calling the comparator if the sub-list is already sorted.
2511 ArraySortResult res
=
2512 MaybeYieldToComparator(d
, d
->list
[d
->mid
], d
->list
[d
->mid
+ 1]);
2513 if (res
!= ArraySortResult::Done
) {
2514 d
->state
= State::MergeSortCall1
;
2520 if (!RvalIsLessOrEqual(d
, &lessOrEqual
)) {
2521 return ArraySortResult::Failure
;
2524 CopyValues(d
->out
, d
->list
, d
->start
, d
->end
);
2532 while (d
->i
<= d
->mid
&& d
->j
<= d
->end
) {
2534 ArraySortResult res
=
2535 MaybeYieldToComparator(d
, d
->list
[d
->i
], d
->list
[d
->j
]);
2536 if (res
!= ArraySortResult::Done
) {
2537 d
->state
= State::MergeSortCall2
;
2543 if (!RvalIsLessOrEqual(d
, &lessOrEqual
)) {
2544 return ArraySortResult::Failure
;
2546 d
->out
[d
->k
++] = lessOrEqual
? d
->list
[d
->i
++] : d
->list
[d
->j
++];
2549 // Empty out any remaining elements. Use local variables to let the
2550 // compiler generate more efficient code.
2551 Value
* out
= d
->out
;
2552 Value
* list
= d
->list
;
2554 uint32_t mid
= d
->mid
;
2555 uint32_t end
= d
->end
;
2556 for (uint32_t i
= d
->i
; i
<= mid
; i
++) {
2559 for (uint32_t j
= d
->j
; j
<= end
; j
++) {
2565 std::swap(d
->list
, d
->out
);
2569 // Copy elements to the array.
2570 Rooted
<JSObject
*> obj(cx
, d
->obj_
);
2571 if (!SetArrayElements(cx
, obj
, 0, d
->denseLen
, d
->list
)) {
2572 return ArraySortResult::Failure
;
2575 // Re-create any holes that sorted to the end of the array.
2576 for (uint32_t i
= d
->denseLen
; i
< d
->length
; i
++) {
2577 if (!CheckForInterrupt(cx
) || !DeletePropertyOrThrow(cx
, obj
, i
)) {
2578 return ArraySortResult::Failure
;
2582 d
->freeMallocData();
2583 d
->setReturnValue(obj
);
2584 return ArraySortResult::Done
;
2587 // https://tc39.es/ecma262/#sec-array.prototype.sort
2588 // 23.1.3.30 Array.prototype.sort ( comparefn )
2589 bool js::array_sort(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2590 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "sort");
2591 CallArgs args
= CallArgsFromVp(argc
, vp
);
2593 // If we have a comparator argument, use the JIT trampoline implementation
2594 // instead. This avoids a performance cliff (especially with large arrays)
2595 // because C++ => JIT calls are much slower than Trampoline => JIT calls.
2596 if (args
.hasDefined(0) && jit::IsBaselineInterpreterEnabled()) {
2597 return CallTrampolineNativeJitCode(cx
, jit::TrampolineNative::ArraySort
,
2601 Rooted
<ArraySortData
> data(cx
, cx
);
2603 // On all return paths other than ArraySortWithComparatorLoop returning Done,
2604 // we call freeMallocData to not fail debug assertions. This matches the JIT
2605 // trampoline where we can't rely on C++ destructors.
2607 mozilla::MakeScopeExit([&]() { data
.get().freeMallocData(); });
2610 if (!ArraySortPrologue(cx
, args
.thisv(), args
.get(0), data
.address(),
2615 args
.rval().set(data
.get().returnValue());
2619 FixedInvokeArgs
<2> callArgs(cx
);
2620 Rooted
<Value
> rval(cx
);
2623 ArraySortResult res
= ArraySortData::sortWithComparator(data
.address());
2625 case ArraySortResult::Failure
:
2628 case ArraySortResult::Done
:
2630 args
.rval().set(data
.get().returnValue());
2633 case ArraySortResult::CallJS
:
2634 case ArraySortResult::CallJSSameRealmNoRectifier
:
2635 MOZ_ASSERT(data
.get().comparatorThisValue().isUndefined());
2636 MOZ_ASSERT(&args
[0].toObject() == data
.get().comparator());
2637 callArgs
[0].set(data
.get().comparatorArg(0));
2638 callArgs
[1].set(data
.get().comparatorArg(1));
2639 if (!js::Call(cx
, args
[0], UndefinedHandleValue
, callArgs
, &rval
)) {
2642 data
.get().setComparatorReturnValue(rval
);
2648 ArraySortResult
js::ArraySortFromJit(JSContext
* cx
,
2649 jit::TrampolineNativeFrameLayout
* frame
) {
2650 // Initialize the ArraySortData class stored in the trampoline frame.
2651 void* dataUninit
= frame
->getFrameData
<ArraySortData
>();
2652 auto* data
= new (dataUninit
) ArraySortData(cx
);
2654 Rooted
<Value
> thisv(cx
, frame
->thisv());
2655 Rooted
<Value
> comparefn(cx
);
2656 if (frame
->numActualArgs() > 0) {
2657 comparefn
= frame
->actualArgs()[0];
2661 if (!ArraySortPrologue(cx
, thisv
, comparefn
, data
, &done
)) {
2662 return ArraySortResult::Failure
;
2665 data
->freeMallocData();
2666 return ArraySortResult::Done
;
2669 return ArraySortData::sortWithComparator(data
);
2672 ArraySortData::ArraySortData(JSContext
* cx
) : cx_(cx
) {
2674 cx_
->liveArraySortDataInstances
++;
2678 void ArraySortData::freeMallocData() {
2681 MOZ_ASSERT(cx_
->liveArraySortDataInstances
> 0);
2682 cx_
->liveArraySortDataInstances
--;
2686 void ArraySortData::trace(JSTracer
* trc
) {
2687 TraceNullableRoot(trc
, &comparator_
, "comparator_");
2688 TraceRoot(trc
, &thisv
, "thisv");
2689 TraceRoot(trc
, &callArgs
[0], "callArgs0");
2690 TraceRoot(trc
, &callArgs
[1], "callArgs1");
2692 TraceRoot(trc
, &item
, "item");
2693 TraceNullableRoot(trc
, &obj_
, "obj");
2696 bool js::NewbornArrayPush(JSContext
* cx
, HandleObject obj
, const Value
& v
) {
2697 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
2699 MOZ_ASSERT(!v
.isMagic());
2700 MOZ_ASSERT(arr
->lengthIsWritable());
2702 uint32_t length
= arr
->length();
2703 MOZ_ASSERT(length
<= arr
->getDenseCapacity());
2705 if (!arr
->ensureElements(cx
, length
+ 1)) {
2709 arr
->setDenseInitializedLength(length
+ 1);
2710 arr
->setLength(length
+ 1);
2711 arr
->initDenseElement(length
, v
);
2715 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2716 // 22.1.3.18 Array.prototype.push ( ...items )
2717 static bool array_push(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2718 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "push");
2719 CallArgs args
= CallArgsFromVp(argc
, vp
);
2722 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2729 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
2733 if (!ObjectMayHaveExtraIndexedProperties(obj
) && length
<= UINT32_MAX
) {
2734 DenseElementResult result
=
2735 obj
->as
<NativeObject
>().setOrExtendDenseElements(
2736 cx
, uint32_t(length
), args
.array(), args
.length());
2737 if (result
!= DenseElementResult::Incomplete
) {
2738 if (result
== DenseElementResult::Failure
) {
2742 uint32_t newlength
= uint32_t(length
) + args
.length();
2743 args
.rval().setNumber(newlength
);
2745 // setOrExtendDenseElements takes care of updating the length for
2746 // arrays. Handle updates to the length of non-arrays here.
2747 if (!obj
->is
<ArrayObject
>()) {
2748 MOZ_ASSERT(obj
->is
<NativeObject
>());
2749 return SetLengthProperty(cx
, obj
, newlength
);
2757 uint64_t newlength
= length
+ args
.length();
2758 if (newlength
>= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
)) {
2759 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
2760 JSMSG_TOO_LONG_ARRAY
);
2765 if (!SetArrayElements(cx
, obj
, length
, args
.length(), args
.array())) {
2770 args
.rval().setNumber(double(newlength
));
2771 return SetLengthProperty(cx
, obj
, newlength
);
2774 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2775 // 22.1.3.17 Array.prototype.pop ( )
2776 bool js::array_pop(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2777 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "pop");
2778 CallArgs args
= CallArgsFromVp(argc
, vp
);
2781 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2788 if (!GetLengthPropertyInlined(cx
, obj
, &index
)) {
2795 args
.rval().setUndefined();
2801 if (!GetArrayElement(cx
, obj
, index
, args
.rval())) {
2806 if (!DeletePropertyOrThrow(cx
, obj
, index
)) {
2812 return SetLengthProperty(cx
, obj
, index
);
2815 void js::ArrayShiftMoveElements(ArrayObject
* arr
) {
2816 AutoUnsafeCallWithABI unsafe
;
2817 MOZ_ASSERT(arr
->isExtensible());
2818 MOZ_ASSERT(arr
->lengthIsWritable());
2819 MOZ_ASSERT(IsPackedArray(arr
));
2820 MOZ_ASSERT(!arr
->denseElementsHaveMaybeInIterationFlag());
2822 size_t initlen
= arr
->getDenseInitializedLength();
2823 MOZ_ASSERT(initlen
> 0);
2825 if (!arr
->tryShiftDenseElements(1)) {
2826 arr
->moveDenseElements(0, 1, initlen
- 1);
2827 arr
->setDenseInitializedLength(initlen
- 1);
2830 MOZ_ASSERT(arr
->getDenseInitializedLength() == initlen
- 1);
2831 arr
->setLength(initlen
- 1);
2834 static inline void SetInitializedLength(JSContext
* cx
, NativeObject
* obj
,
2836 MOZ_ASSERT(obj
->isExtensible());
2838 size_t oldInitlen
= obj
->getDenseInitializedLength();
2839 obj
->setDenseInitializedLength(initlen
);
2840 if (initlen
< oldInitlen
) {
2841 obj
->shrinkElements(cx
, initlen
);
2845 static DenseElementResult
ArrayShiftDenseKernel(JSContext
* cx
, HandleObject obj
,
2846 MutableHandleValue rval
) {
2847 if (!IsPackedArray(obj
) && ObjectMayHaveExtraIndexedProperties(obj
)) {
2848 return DenseElementResult::Incomplete
;
2851 Handle
<NativeObject
*> nobj
= obj
.as
<NativeObject
>();
2852 if (nobj
->denseElementsMaybeInIteration()) {
2853 return DenseElementResult::Incomplete
;
2856 if (!nobj
->isExtensible()) {
2857 return DenseElementResult::Incomplete
;
2860 size_t initlen
= nobj
->getDenseInitializedLength();
2862 return DenseElementResult::Incomplete
;
2865 rval
.set(nobj
->getDenseElement(0));
2866 if (rval
.isMagic(JS_ELEMENTS_HOLE
)) {
2867 rval
.setUndefined();
2870 if (nobj
->tryShiftDenseElements(1)) {
2871 return DenseElementResult::Success
;
2874 nobj
->moveDenseElements(0, 1, initlen
- 1);
2876 SetInitializedLength(cx
, nobj
, initlen
- 1);
2877 return DenseElementResult::Success
;
2880 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2881 // 22.1.3.22 Array.prototype.shift ( )
2882 static bool array_shift(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2883 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "shift");
2884 CallArgs args
= CallArgsFromVp(argc
, vp
);
2887 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2894 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
2901 if (!SetLengthProperty(cx
, obj
, uint32_t(0))) {
2906 args
.rval().setUndefined();
2910 uint64_t newlen
= len
- 1;
2913 uint64_t startIndex
;
2914 DenseElementResult result
= ArrayShiftDenseKernel(cx
, obj
, args
.rval());
2915 if (result
!= DenseElementResult::Incomplete
) {
2916 if (result
== DenseElementResult::Failure
) {
2920 if (len
<= UINT32_MAX
) {
2921 return SetLengthProperty(cx
, obj
, newlen
);
2924 startIndex
= UINT32_MAX
- 1;
2927 if (!GetElement(cx
, obj
, 0, args
.rval())) {
2935 RootedValue
value(cx
);
2936 for (uint64_t i
= startIndex
; i
< newlen
; i
++) {
2937 if (!CheckForInterrupt(cx
)) {
2941 if (!HasAndGetElement(cx
, obj
, i
+ 1, &hole
, &value
)) {
2945 if (!DeletePropertyOrThrow(cx
, obj
, i
)) {
2949 if (!SetArrayElement(cx
, obj
, i
, value
)) {
2956 if (!DeletePropertyOrThrow(cx
, obj
, newlen
)) {
2961 return SetLengthProperty(cx
, obj
, newlen
);
2964 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2965 // 22.1.3.29 Array.prototype.unshift ( ...items )
2966 static bool array_unshift(JSContext
* cx
, unsigned argc
, Value
* vp
) {
2967 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "unshift");
2968 CallArgs args
= CallArgsFromVp(argc
, vp
);
2971 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
2978 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
2983 if (args
.length() > 0) {
2984 bool optimized
= false;
2986 if (length
> UINT32_MAX
) {
2989 if (ObjectMayHaveExtraIndexedProperties(obj
)) {
2992 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
2993 if (nobj
->denseElementsMaybeInIteration()) {
2996 if (!nobj
->isExtensible()) {
2999 if (nobj
->is
<ArrayObject
>() &&
3000 !nobj
->as
<ArrayObject
>().lengthIsWritable()) {
3003 if (!nobj
->tryUnshiftDenseElements(args
.length())) {
3004 DenseElementResult result
=
3005 nobj
->ensureDenseElements(cx
, uint32_t(length
), args
.length());
3006 if (result
!= DenseElementResult::Success
) {
3007 if (result
== DenseElementResult::Failure
) {
3010 MOZ_ASSERT(result
== DenseElementResult::Incomplete
);
3014 nobj
->moveDenseElements(args
.length(), 0, uint32_t(length
));
3017 for (uint32_t i
= 0; i
< args
.length(); i
++) {
3018 nobj
->setDenseElement(i
, args
[i
]);
3025 uint64_t last
= length
;
3026 uint64_t upperIndex
= last
+ args
.length();
3029 if (upperIndex
>= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
)) {
3030 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3031 JSMSG_TOO_LONG_ARRAY
);
3036 RootedValue
value(cx
);
3040 if (!CheckForInterrupt(cx
)) {
3044 if (!HasAndGetElement(cx
, obj
, last
, &hole
, &value
)) {
3048 if (!DeletePropertyOrThrow(cx
, obj
, upperIndex
)) {
3052 if (!SetArrayElement(cx
, obj
, upperIndex
, value
)) {
3056 } while (last
!= 0);
3060 /* Copy from args to the bottom of the array. */
3061 if (!SetArrayElements(cx
, obj
, 0, args
.length(), args
.array())) {
3068 uint64_t newlength
= length
+ args
.length();
3069 if (!SetLengthProperty(cx
, obj
, newlength
)) {
3074 /* Follow Perl by returning the new array length. */
3075 args
.rval().setNumber(double(newlength
));
3079 enum class ArrayAccess
{ Read
, Write
};
3082 * Returns true if this is a dense array whose properties ending at |endIndex|
3083 * (exclusive) may be accessed (get, set, delete) directly through its
3084 * contiguous vector of elements without fear of getters, setters, etc. along
3085 * the prototype chain, or of enumerators requiring notification of
3088 template <ArrayAccess Access
>
3089 static bool CanOptimizeForDenseStorage(HandleObject arr
, uint64_t endIndex
) {
3090 /* If the desired properties overflow dense storage, we can't optimize. */
3091 if (endIndex
> UINT32_MAX
) {
3095 if (Access
== ArrayAccess::Read
) {
3097 * Dense storage read access is possible for any packed array as long
3098 * as we only access properties within the initialized length. In all
3099 * other cases we need to ensure there are no other indexed properties
3100 * on this object or on the prototype chain. Callers are required to
3101 * clamp the read length, so it doesn't exceed the initialized length.
3103 if (IsPackedArray(arr
) &&
3104 endIndex
<= arr
->as
<ArrayObject
>().getDenseInitializedLength()) {
3107 return !ObjectMayHaveExtraIndexedProperties(arr
);
3110 /* There's no optimizing possible if it's not an array. */
3111 if (!arr
->is
<ArrayObject
>()) {
3115 /* If the length is non-writable, always pick the slow path */
3116 if (!arr
->as
<ArrayObject
>().lengthIsWritable()) {
3120 /* Also pick the slow path if the object is non-extensible. */
3121 if (!arr
->as
<ArrayObject
>().isExtensible()) {
3125 /* Also pick the slow path if the object is being iterated over. */
3126 if (arr
->as
<ArrayObject
>().denseElementsMaybeInIteration()) {
3130 /* Or we attempt to write to indices outside the initialized length. */
3131 if (endIndex
> arr
->as
<ArrayObject
>().getDenseInitializedLength()) {
3136 * Now watch out for getters and setters along the prototype chain or in
3137 * other indexed properties on the object. Packed arrays don't have any
3138 * other indexed properties by definition.
3140 return IsPackedArray(arr
) || !ObjectMayHaveExtraIndexedProperties(arr
);
3143 static ArrayObject
* CopyDenseArrayElements(JSContext
* cx
,
3144 Handle
<NativeObject
*> obj
,
3145 uint32_t begin
, uint32_t count
) {
3146 size_t initlen
= obj
->getDenseInitializedLength();
3147 MOZ_ASSERT(initlen
<= UINT32_MAX
,
3148 "initialized length shouldn't exceed UINT32_MAX");
3149 uint32_t newlength
= 0;
3150 if (initlen
> begin
) {
3151 newlength
= std::min
<uint32_t>(initlen
- begin
, count
);
3154 ArrayObject
* narr
= NewDenseFullyAllocatedArray(cx
, newlength
);
3159 MOZ_ASSERT(count
>= narr
->length());
3160 narr
->setLength(count
);
3162 if (newlength
> 0) {
3163 narr
->initDenseElements(obj
, begin
, newlength
);
3169 static bool CopyArrayElements(JSContext
* cx
, HandleObject obj
, uint64_t begin
,
3170 uint64_t count
, Handle
<ArrayObject
*> result
) {
3171 MOZ_ASSERT(result
->length() == count
);
3173 uint64_t startIndex
= 0;
3174 RootedValue
value(cx
);
3176 // Use dense storage for new indexed properties where possible.
3179 uint32_t limit
= std::min
<uint32_t>(count
, PropertyKey::IntMax
);
3180 for (; index
< limit
; index
++) {
3182 if (!CheckForInterrupt(cx
) ||
3183 !HasAndGetElement(cx
, obj
, begin
+ index
, &hole
, &value
)) {
3188 DenseElementResult edResult
= result
->ensureDenseElements(cx
, index
, 1);
3189 if (edResult
!= DenseElementResult::Success
) {
3190 if (edResult
== DenseElementResult::Failure
) {
3194 MOZ_ASSERT(edResult
== DenseElementResult::Incomplete
);
3195 if (!DefineDataElement(cx
, result
, index
, value
)) {
3201 result
->setDenseElement(index
, value
);
3204 startIndex
= index
+ 1;
3207 // Copy any remaining elements.
3208 for (uint64_t i
= startIndex
; i
< count
; i
++) {
3210 if (!CheckForInterrupt(cx
) ||
3211 !HasAndGetElement(cx
, obj
, begin
+ i
, &hole
, &value
)) {
3215 if (!hole
&& !DefineArrayElement(cx
, result
, i
, value
)) {
3222 // Helpers for array_splice_impl() and array_to_spliced()
3224 // Initialize variables common to splice() and toSpliced():
3225 // - GetActualStart() returns the index at which to start deleting elements.
3226 // - GetItemCount() returns the number of new elements being added.
3227 // - GetActualDeleteCount() returns the number of elements being deleted.
3228 static bool GetActualStart(JSContext
* cx
, HandleValue start
, uint64_t len
,
3230 MOZ_ASSERT(len
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
3232 // Steps from proposal: https://github.com/tc39/proposal-change-array-by-copy
3233 // Array.prototype.toSpliced()
3235 // Step 3. Let relativeStart be ? ToIntegerOrInfinity(start).
3236 double relativeStart
;
3237 if (!ToInteger(cx
, start
, &relativeStart
)) {
3241 // Steps 4-5. If relativeStart is -∞, let actualStart be 0.
3242 // Else if relativeStart < 0, let actualStart be max(len + relativeStart, 0).
3243 if (relativeStart
< 0) {
3244 *result
= uint64_t(std::max(double(len
) + relativeStart
, 0.0));
3246 // Step 6. Else, let actualStart be min(relativeStart, len).
3247 *result
= uint64_t(std::min(relativeStart
, double(len
)));
3252 static uint32_t GetItemCount(const CallArgs
& args
) {
3253 if (args
.length() < 2) {
3256 return (args
.length() - 2);
3259 static bool GetActualDeleteCount(JSContext
* cx
, const CallArgs
& args
,
3260 HandleObject obj
, uint64_t len
,
3261 uint64_t actualStart
, uint32_t insertCount
,
3262 uint64_t* actualDeleteCount
) {
3263 MOZ_ASSERT(len
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
3264 MOZ_ASSERT(actualStart
<= len
);
3265 MOZ_ASSERT(insertCount
== GetItemCount(args
));
3267 // Steps from proposal: https://github.com/tc39/proposal-change-array-by-copy
3268 // Array.prototype.toSpliced()
3270 if (args
.length() < 1) {
3271 // Step 8. If start is not present, then let actualDeleteCount be 0.
3272 *actualDeleteCount
= 0;
3273 } else if (args
.length() < 2) {
3274 // Step 9. Else if deleteCount is not present, then let actualDeleteCount be
3275 // len - actualStart.
3276 *actualDeleteCount
= len
- actualStart
;
3278 // Step 10.a. Else, let dc be toIntegerOrInfinity(deleteCount).
3280 if (!ToInteger(cx
, args
.get(1), &deleteCount
)) {
3284 // Step 10.b. Let actualDeleteCount be the result of clamping dc between 0
3285 // and len - actualStart.
3286 *actualDeleteCount
= uint64_t(
3287 std::min(std::max(0.0, deleteCount
), double(len
- actualStart
)));
3288 MOZ_ASSERT(*actualDeleteCount
<= len
);
3290 // Step 11. Let newLen be len + insertCount - actualDeleteCount.
3291 // Step 12. If newLen > 2^53 - 1, throw a TypeError exception.
3292 if (len
+ uint64_t(insertCount
) - *actualDeleteCount
>=
3293 uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
)) {
3294 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3295 JSMSG_TOO_LONG_ARRAY
);
3299 MOZ_ASSERT(actualStart
+ *actualDeleteCount
<= len
);
3304 static bool array_splice_impl(JSContext
* cx
, unsigned argc
, Value
* vp
,
3305 bool returnValueIsUsed
) {
3306 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "splice");
3307 CallArgs args
= CallArgsFromVp(argc
, vp
);
3310 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
3317 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
3322 /* actualStart is the index after which elements will be
3323 deleted and/or new elements will be added */
3324 uint64_t actualStart
;
3325 if (!GetActualStart(cx
, args
.get(0), len
, &actualStart
)) {
3330 /* itemCount is the number of elements being added */
3331 uint32_t itemCount
= GetItemCount(args
);
3333 /* actualDeleteCount is the number of elements being deleted */
3334 uint64_t actualDeleteCount
;
3335 if (!GetActualDeleteCount(cx
, args
, obj
, len
, actualStart
, itemCount
,
3336 &actualDeleteCount
)) {
3340 RootedObject
arr(cx
);
3341 if (IsArraySpecies(cx
, obj
)) {
3342 if (actualDeleteCount
> UINT32_MAX
) {
3343 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3344 JSMSG_BAD_ARRAY_LENGTH
);
3347 uint32_t count
= uint32_t(actualDeleteCount
);
3349 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
,
3350 actualStart
+ count
)) {
3351 MOZ_ASSERT(actualStart
<= UINT32_MAX
,
3352 "if actualStart + count <= UINT32_MAX, then actualStart <= "
3354 if (returnValueIsUsed
) {
3356 arr
= CopyDenseArrayElements(cx
, obj
.as
<NativeObject
>(),
3357 uint32_t(actualStart
), count
);
3364 arr
= NewDenseFullyAllocatedArray(cx
, count
);
3370 if (!CopyArrayElements(cx
, obj
, actualStart
, count
,
3371 arr
.as
<ArrayObject
>())) {
3377 if (!ArraySpeciesCreate(cx
, obj
, actualDeleteCount
, &arr
)) {
3382 RootedValue
fromValue(cx
);
3383 for (uint64_t k
= 0; k
< actualDeleteCount
; k
++) {
3384 if (!CheckForInterrupt(cx
)) {
3388 /* Steps 13.b, 13.c.i. */
3390 if (!HasAndGetElement(cx
, obj
, actualStart
+ k
, &hole
, &fromValue
)) {
3397 if (!DefineArrayElement(cx
, arr
, k
, fromValue
)) {
3404 if (!SetLengthProperty(cx
, arr
, actualDeleteCount
)) {
3410 uint64_t finalLength
= len
- actualDeleteCount
+ itemCount
;
3412 if (itemCount
< actualDeleteCount
) {
3413 /* Step 16: the array is being shrunk. */
3414 uint64_t sourceIndex
= actualStart
+ actualDeleteCount
;
3415 uint64_t targetIndex
= actualStart
+ itemCount
;
3417 if (CanOptimizeForDenseStorage
<ArrayAccess::Write
>(obj
, len
)) {
3418 MOZ_ASSERT(sourceIndex
<= len
&& targetIndex
<= len
&& len
<= UINT32_MAX
,
3419 "sourceIndex and targetIndex are uint32 array indices");
3420 MOZ_ASSERT(finalLength
< len
, "finalLength is strictly less than len");
3421 MOZ_ASSERT(obj
->is
<NativeObject
>());
3424 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
3425 if (targetIndex
!= 0 || !arr
->tryShiftDenseElements(sourceIndex
)) {
3426 arr
->moveDenseElements(uint32_t(targetIndex
), uint32_t(sourceIndex
),
3427 uint32_t(len
- sourceIndex
));
3431 SetInitializedLength(cx
, arr
, finalLength
);
3434 * This is all very slow if the length is very large. We don't yet
3435 * have the ability to iterate in sorted order, so we just do the
3436 * pessimistic thing and let CheckForInterrupt handle the
3441 RootedValue
fromValue(cx
);
3442 for (uint64_t from
= sourceIndex
, to
= targetIndex
; from
< len
;
3444 /* Steps 15.b.i-ii (implicit). */
3446 if (!CheckForInterrupt(cx
)) {
3450 /* Steps 16.b.iii-v */
3452 if (!HasAndGetElement(cx
, obj
, from
, &hole
, &fromValue
)) {
3457 if (!DeletePropertyOrThrow(cx
, obj
, to
)) {
3461 if (!SetArrayElement(cx
, obj
, to
, fromValue
)) {
3468 if (!DeletePropertiesOrThrow(cx
, obj
, len
, finalLength
)) {
3472 } else if (itemCount
> actualDeleteCount
) {
3473 MOZ_ASSERT(actualDeleteCount
<= UINT32_MAX
);
3474 uint32_t deleteCount
= uint32_t(actualDeleteCount
);
3478 // Fast path for when we can simply extend and move the dense elements.
3479 auto extendElements
= [len
, itemCount
, deleteCount
](JSContext
* cx
,
3481 if (!obj
->is
<ArrayObject
>()) {
3482 return DenseElementResult::Incomplete
;
3484 if (len
> UINT32_MAX
) {
3485 return DenseElementResult::Incomplete
;
3488 // Ensure there are no getters/setters or other extra indexed properties.
3489 if (ObjectMayHaveExtraIndexedProperties(obj
)) {
3490 return DenseElementResult::Incomplete
;
3493 // Watch out for arrays with non-writable length or non-extensible arrays.
3494 // In these cases `splice` may have to throw an exception so we let the
3495 // slow path handle it. We also have to ensure we maintain the
3496 // |capacity <= initializedLength| invariant for such objects. See
3497 // NativeObject::shrinkCapacityToInitializedLength.
3498 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
3499 if (!arr
->lengthIsWritable() || !arr
->isExtensible()) {
3500 return DenseElementResult::Incomplete
;
3503 // Also use the slow path if there might be an active for-in iterator so
3504 // that we don't have to worry about suppressing deleted properties.
3505 if (arr
->denseElementsMaybeInIteration()) {
3506 return DenseElementResult::Incomplete
;
3509 return arr
->ensureDenseElements(cx
, uint32_t(len
),
3510 itemCount
- deleteCount
);
3513 DenseElementResult res
= extendElements(cx
, obj
);
3514 if (res
== DenseElementResult::Failure
) {
3517 if (res
== DenseElementResult::Success
) {
3518 MOZ_ASSERT(finalLength
<= UINT32_MAX
);
3519 MOZ_ASSERT((actualStart
+ actualDeleteCount
) <= len
&& len
<= UINT32_MAX
,
3520 "start and deleteCount are uint32 array indices");
3521 MOZ_ASSERT(actualStart
+ itemCount
<= UINT32_MAX
,
3522 "can't overflow because |len - actualDeleteCount + itemCount "
3524 "and |actualStart <= len - actualDeleteCount| are both true");
3525 uint32_t start
= uint32_t(actualStart
);
3526 uint32_t length
= uint32_t(len
);
3528 Handle
<ArrayObject
*> arr
= obj
.as
<ArrayObject
>();
3529 arr
->moveDenseElements(start
+ itemCount
, start
+ deleteCount
,
3530 length
- (start
+ deleteCount
));
3533 SetInitializedLength(cx
, arr
, finalLength
);
3535 MOZ_ASSERT(res
== DenseElementResult::Incomplete
);
3537 RootedValue
fromValue(cx
);
3538 for (uint64_t k
= len
- actualDeleteCount
; k
> actualStart
; k
--) {
3539 if (!CheckForInterrupt(cx
)) {
3544 uint64_t from
= k
+ actualDeleteCount
- 1;
3547 uint64_t to
= k
+ itemCount
- 1;
3549 /* Steps 17.b.iii, 17.b.iv.1. */
3551 if (!HasAndGetElement(cx
, obj
, from
, &hole
, &fromValue
)) {
3555 /* Steps 17.b.iv. */
3557 /* Step 17.b.v.1. */
3558 if (!DeletePropertyOrThrow(cx
, obj
, to
)) {
3562 /* Step 17.b.iv.2. */
3563 if (!SetArrayElement(cx
, obj
, to
, fromValue
)) {
3571 Value
* items
= args
.array() + 2;
3574 if (!SetArrayElements(cx
, obj
, actualStart
, itemCount
, items
)) {
3579 if (!SetLengthProperty(cx
, obj
, finalLength
)) {
3584 if (returnValueIsUsed
) {
3585 args
.rval().setObject(*arr
);
3591 /* ES 2016 draft Mar 25, 2016 22.1.3.26. */
3592 static bool array_splice(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3593 return array_splice_impl(cx
, argc
, vp
, true);
3596 static bool array_splice_noRetVal(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3597 return array_splice_impl(cx
, argc
, vp
, false);
3600 static void CopyDenseElementsFillHoles(ArrayObject
* arr
, NativeObject
* nobj
,
3602 // Ensure |arr| is an empty array with sufficient capacity.
3603 MOZ_ASSERT(arr
->getDenseInitializedLength() == 0);
3604 MOZ_ASSERT(arr
->getDenseCapacity() >= length
);
3605 MOZ_ASSERT(length
> 0);
3607 uint32_t count
= std::min(nobj
->getDenseInitializedLength(), length
);
3610 if (nobj
->denseElementsArePacked()) {
3611 // Copy all dense elements when no holes are present.
3612 arr
->initDenseElements(nobj
, 0, count
);
3614 arr
->setDenseInitializedLength(count
);
3616 // Handle each element separately to filter out holes.
3617 for (uint32_t i
= 0; i
< count
; i
++) {
3618 Value val
= nobj
->getDenseElement(i
);
3619 if (val
.isMagic(JS_ELEMENTS_HOLE
)) {
3620 val
= UndefinedValue();
3622 arr
->initDenseElement(i
, val
);
3627 // Fill trailing holes with undefined.
3628 if (count
< length
) {
3629 arr
->setDenseInitializedLength(length
);
3631 for (uint32_t i
= count
; i
< length
; i
++) {
3632 arr
->initDenseElement(i
, UndefinedValue());
3636 // Ensure |length| elements have been copied and no holes are present.
3637 MOZ_ASSERT(arr
->getDenseInitializedLength() == length
);
3638 MOZ_ASSERT(arr
->denseElementsArePacked());
3641 // https://github.com/tc39/proposal-change-array-by-copy
3642 // Array.prototype.toSpliced()
3643 static bool array_toSpliced(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3644 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "toSpliced");
3645 CallArgs args
= CallArgsFromVp(argc
, vp
);
3647 // Step 1. Let O be ? ToObject(this value).
3648 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
3653 // Step 2. Let len be ? LengthOfArrayLike(O).
3655 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
3660 // |actualStart| is the index after which elements will be deleted and/or
3661 // new elements will be added
3662 uint64_t actualStart
;
3663 if (!GetActualStart(cx
, args
.get(0), len
, &actualStart
)) {
3666 MOZ_ASSERT(actualStart
<= len
);
3668 // Step 7. Let insertCount be the number of elements in items.
3669 uint32_t insertCount
= GetItemCount(args
);
3672 // actualDeleteCount is the number of elements being deleted
3673 uint64_t actualDeleteCount
;
3674 if (!GetActualDeleteCount(cx
, args
, obj
, len
, actualStart
, insertCount
,
3675 &actualDeleteCount
)) {
3678 MOZ_ASSERT(actualStart
+ actualDeleteCount
<= len
);
3680 // Step 11. Let newLen be len + insertCount - actualDeleteCount.
3681 uint64_t newLen
= len
+ insertCount
- actualDeleteCount
;
3683 // Step 12 handled by GetActualDeleteCount().
3684 MOZ_ASSERT(newLen
< DOUBLE_INTEGRAL_PRECISION_LIMIT
);
3685 MOZ_ASSERT(actualStart
<= newLen
,
3686 "if |actualStart + actualDeleteCount <= len| and "
3687 "|newLen = len + insertCount - actualDeleteCount|, then "
3688 "|actualStart <= newLen|");
3690 // ArrayCreate, step 1.
3691 if (newLen
> UINT32_MAX
) {
3692 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3693 JSMSG_BAD_ARRAY_LENGTH
);
3697 // Step 13. Let A be ? ArrayCreate(𝔽(newLen)).
3698 Rooted
<ArrayObject
*> arr(cx
,
3699 NewDensePartlyAllocatedArray(cx
, uint32_t(newLen
)));
3704 // Steps 14-19 optimized for dense elements.
3705 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
)) {
3706 MOZ_ASSERT(len
<= UINT32_MAX
);
3707 MOZ_ASSERT(actualDeleteCount
<= UINT32_MAX
,
3708 "if |actualStart + actualDeleteCount <= len| and "
3709 "|len <= UINT32_MAX|, then |actualDeleteCount <= UINT32_MAX|");
3711 uint32_t length
= uint32_t(len
);
3712 uint32_t newLength
= uint32_t(newLen
);
3713 uint32_t start
= uint32_t(actualStart
);
3714 uint32_t deleteCount
= uint32_t(actualDeleteCount
);
3716 auto nobj
= obj
.as
<NativeObject
>();
3718 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, newLength
);
3722 arr
->setLength(newLength
);
3724 // Below code doesn't handle the case when the storage has to grow,
3725 // therefore the capacity must fit for at least |newLength| elements.
3726 MOZ_ASSERT(arr
->getDenseCapacity() >= newLength
);
3728 if (deleteCount
== 0 && insertCount
== 0) {
3729 // Copy the array when we don't have to remove or insert any elements.
3730 if (newLength
> 0) {
3731 CopyDenseElementsFillHoles(arr
, nobj
, newLength
);
3734 // Copy nobj[0..start] to arr[0..start].
3736 CopyDenseElementsFillHoles(arr
, nobj
, start
);
3739 // Insert |items| into arr[start..(start + insertCount)].
3740 if (insertCount
> 0) {
3741 auto items
= HandleValueArray::subarray(args
, 2, insertCount
);
3743 // Prefer |initDenseElements| because it's faster.
3744 if (arr
->getDenseInitializedLength() == 0) {
3745 arr
->initDenseElements(items
.begin(), items
.length());
3747 arr
->ensureDenseInitializedLength(start
, items
.length());
3748 arr
->copyDenseElements(start
, items
.begin(), items
.length());
3752 uint32_t fromIndex
= start
+ deleteCount
;
3753 uint32_t toIndex
= start
+ insertCount
;
3754 MOZ_ASSERT((length
- fromIndex
) == (newLength
- toIndex
),
3755 "Copies all remaining elements to the end");
3757 // Copy nobj[(start + deleteCount)..length] to
3758 // arr[(start + insertCount)..newLength].
3759 if (fromIndex
< length
) {
3760 uint32_t end
= std::min(length
, nobj
->getDenseInitializedLength());
3761 if (fromIndex
< end
) {
3762 uint32_t count
= end
- fromIndex
;
3763 if (nobj
->denseElementsArePacked()) {
3764 // Copy all dense elements when no holes are present.
3765 const Value
* src
= nobj
->getDenseElements() + fromIndex
;
3766 arr
->ensureDenseInitializedLength(toIndex
, count
);
3767 arr
->copyDenseElements(toIndex
, src
, count
);
3771 arr
->setDenseInitializedLength(toIndex
+ count
);
3773 // Handle each element separately to filter out holes.
3774 for (uint32_t i
= 0; i
< count
; i
++) {
3775 Value val
= nobj
->getDenseElement(fromIndex
++);
3776 if (val
.isMagic(JS_ELEMENTS_HOLE
)) {
3777 val
= UndefinedValue();
3779 arr
->initDenseElement(toIndex
++, val
);
3784 arr
->setDenseInitializedLength(newLength
);
3786 // Fill trailing holes with undefined.
3787 while (fromIndex
< length
) {
3788 arr
->initDenseElement(toIndex
++, UndefinedValue());
3793 MOZ_ASSERT(fromIndex
== length
);
3794 MOZ_ASSERT(toIndex
== newLength
);
3797 // Ensure the result array is packed and has the correct length.
3798 MOZ_ASSERT(IsPackedArray(arr
));
3799 MOZ_ASSERT(arr
->length() == newLength
);
3801 args
.rval().setObject(*arr
);
3805 // Copy everything before start
3807 // Step 14. Let i be 0.
3810 // Step 15. Let r be actualStart + actualDeleteCount.
3811 uint64_t r
= actualStart
+ actualDeleteCount
;
3813 // Step 16. Repeat while i < actualStart,
3814 RootedValue
iValue(cx
);
3815 while (i
< uint32_t(actualStart
)) {
3816 if (!CheckForInterrupt(cx
)) {
3820 // Skip Step 16.a. Let Pi be ! ToString(𝔽(i)).
3822 // Step 16.b. Let iValue be ? Get(O, Pi).
3823 if (!GetArrayElement(cx
, obj
, i
, &iValue
)) {
3827 // Step 16.c. Perform ! CreateDataPropertyOrThrow(A, Pi, iValue).
3828 if (!DefineArrayElement(cx
, arr
, i
, iValue
)) {
3832 // Step 16.d. Set i to i + 1.
3836 // Result array now contains all elements before start.
3839 if (insertCount
> 0) {
3840 HandleValueArray items
= HandleValueArray::subarray(args
, 2, insertCount
);
3842 // Fast-path to copy all items in one go.
3843 DenseElementResult result
=
3844 arr
->setOrExtendDenseElements(cx
, i
, items
.begin(), items
.length());
3845 if (result
== DenseElementResult::Failure
) {
3849 if (result
== DenseElementResult::Success
) {
3850 i
+= items
.length();
3852 MOZ_ASSERT(result
== DenseElementResult::Incomplete
);
3854 // Step 17. For each element E of items, do
3855 for (size_t j
= 0; j
< items
.length(); j
++) {
3856 if (!CheckForInterrupt(cx
)) {
3860 // Skip Step 17.a. Let Pi be ! ToString(𝔽(i)).
3862 // Step 17.b. Perform ! CreateDataPropertyOrThrow(A, Pi, E).
3863 if (!DefineArrayElement(cx
, arr
, i
, items
[j
])) {
3867 // Step 17.c. Set i to i + 1.
3873 // Copy items after new items
3874 // Step 18. Repeat, while i < newLen,
3875 RootedValue
fromValue(cx
);
3876 while (i
< uint32_t(newLen
)) {
3877 if (!CheckForInterrupt(cx
)) {
3881 // Skip Step 18.a. Let Pi be ! ToString(𝔽(i)).
3882 // Skip Step 18.b. Let from be ! ToString(𝔽(r)).
3884 // Step 18.c. Let fromValue be ? Get(O, from). */
3885 if (!GetArrayElement(cx
, obj
, r
, &fromValue
)) {
3889 // Step 18.d. Perform ! CreateDataPropertyOrThrow(A, Pi, fromValue).
3890 if (!DefineArrayElement(cx
, arr
, i
, fromValue
)) {
3894 // Step 18.e. Set i to i + 1.
3897 // Step 18.f. Set r to r + 1.
3901 // Step 19. Return A.
3902 args
.rval().setObject(*arr
);
3906 // https://github.com/tc39/proposal-change-array-by-copy
3907 // Array.prototype.with()
3908 static bool array_with(JSContext
* cx
, unsigned argc
, Value
* vp
) {
3909 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "with");
3910 CallArgs args
= CallArgsFromVp(argc
, vp
);
3912 // Step 1. Let O be ? ToObject(this value).
3913 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
3918 // Step 2. Let len be ? LengthOfArrayLike(O).
3920 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
3924 // Step 3. Let relativeIndex be ? ToIntegerOrInfinity(index).
3925 double relativeIndex
;
3926 if (!ToInteger(cx
, args
.get(0), &relativeIndex
)) {
3927 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_INDEX
);
3931 // Step 4. If relativeIndex >= 0, let actualIndex be relativeIndex.
3932 double actualIndex
= relativeIndex
;
3933 if (actualIndex
< 0) {
3934 // Step 5. Else, let actualIndex be len + relativeIndex.
3935 actualIndex
= double(len
) + actualIndex
;
3938 // Step 6. If actualIndex >= len or actualIndex < 0, throw a RangeError
3940 if (actualIndex
< 0 || actualIndex
>= double(len
)) {
3941 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_INDEX
);
3945 // ArrayCreate, step 1.
3946 if (len
> UINT32_MAX
) {
3947 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3948 JSMSG_BAD_ARRAY_LENGTH
);
3951 uint32_t length
= uint32_t(len
);
3953 MOZ_ASSERT(length
> 0);
3954 MOZ_ASSERT(0 <= actualIndex
&& actualIndex
< UINT32_MAX
);
3956 // Steps 7-10 optimized for dense elements.
3957 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, length
)) {
3958 auto nobj
= obj
.as
<NativeObject
>();
3960 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, length
);
3964 arr
->setLength(length
);
3966 CopyDenseElementsFillHoles(arr
, nobj
, length
);
3968 // Replace the value at |actualIndex|.
3969 arr
->setDenseElement(uint32_t(actualIndex
), args
.get(1));
3971 // Ensure the result array is packed and has the correct length.
3972 MOZ_ASSERT(IsPackedArray(arr
));
3973 MOZ_ASSERT(arr
->length() == length
);
3975 args
.rval().setObject(*arr
);
3979 // Step 7. Let A be ? ArrayCreate(𝔽(len)).
3980 RootedObject
arr(cx
, NewDensePartlyAllocatedArray(cx
, length
));
3985 // Steps 8-9. Let k be 0; Repeat, while k < len,
3986 RootedValue
fromValue(cx
);
3987 for (uint32_t k
= 0; k
< length
; k
++) {
3988 if (!CheckForInterrupt(cx
)) {
3992 // Skip Step 9.a. Let Pk be ! ToString(𝔽(k)).
3994 // Step 9.b. If k is actualIndex, let fromValue be value.
3995 if (k
== uint32_t(actualIndex
)) {
3996 fromValue
= args
.get(1);
3998 // Step 9.c. Else, let fromValue be ? Get(O, 𝔽(k)).
3999 if (!GetArrayElement(cx
, obj
, k
, &fromValue
)) {
4004 // Step 9.d. Perform ! CreateDataPropertyOrThrow(A, 𝔽(k), fromValue).
4005 if (!DefineArrayElement(cx
, arr
, k
, fromValue
)) {
4010 // Step 10. Return A.
4011 args
.rval().setObject(*arr
);
4015 struct SortComparatorIndexes
{
4016 bool operator()(uint32_t a
, uint32_t b
, bool* lessOrEqualp
) {
4017 *lessOrEqualp
= (a
<= b
);
4022 // Returns all indexed properties in the range [begin, end) found on |obj| or
4023 // its proto chain. This function does not handle proxies, objects with
4024 // resolve/lookupProperty hooks or indexed getters, as those can introduce
4025 // new properties. In those cases, *success is set to |false|.
4026 static bool GetIndexedPropertiesInRange(JSContext
* cx
, HandleObject obj
,
4027 uint64_t begin
, uint64_t end
,
4028 Vector
<uint32_t>& indexes
,
4032 // TODO: Add IdIsIndex with support for large indices.
4033 if (end
> UINT32_MAX
) {
4036 MOZ_ASSERT(begin
<= UINT32_MAX
);
4038 // First, look for proxies or class hooks that can introduce extra
4040 JSObject
* pobj
= obj
;
4042 if (!pobj
->is
<NativeObject
>() || pobj
->getClass()->getResolve() ||
4043 pobj
->getOpsLookupProperty()) {
4046 } while ((pobj
= pobj
->staticPrototype()));
4048 // Collect indexed property names.
4051 // Append dense elements.
4052 NativeObject
* nativeObj
= &pobj
->as
<NativeObject
>();
4053 uint32_t initLen
= nativeObj
->getDenseInitializedLength();
4054 for (uint32_t i
= begin
; i
< initLen
&& i
< end
; i
++) {
4055 if (nativeObj
->getDenseElement(i
).isMagic(JS_ELEMENTS_HOLE
)) {
4058 if (!indexes
.append(i
)) {
4063 // Append typed array elements.
4064 if (nativeObj
->is
<TypedArrayObject
>()) {
4065 size_t len
= nativeObj
->as
<TypedArrayObject
>().length().valueOr(0);
4066 for (uint32_t i
= begin
; i
< len
&& i
< end
; i
++) {
4067 if (!indexes
.append(i
)) {
4073 // Append sparse elements.
4074 if (nativeObj
->isIndexed()) {
4075 ShapePropertyIter
<NoGC
> iter(nativeObj
->shape());
4076 for (; !iter
.done(); iter
++) {
4077 jsid id
= iter
->key();
4079 if (!IdIsIndex(id
, &i
)) {
4083 if (!(begin
<= i
&& i
< end
)) {
4087 // Watch out for getters, they can add new properties.
4088 if (!iter
->isDataProperty()) {
4092 if (!indexes
.append(i
)) {
4097 } while ((pobj
= pobj
->staticPrototype()));
4099 // Sort the indexes.
4100 Vector
<uint32_t> tmp(cx
);
4101 size_t n
= indexes
.length();
4102 if (!tmp
.resize(n
)) {
4105 if (!MergeSort(indexes
.begin(), n
, tmp
.begin(), SortComparatorIndexes())) {
4109 // Remove duplicates.
4110 if (!indexes
.empty()) {
4112 for (size_t i
= 1, len
= indexes
.length(); i
< len
; i
++) {
4113 uint32_t elem
= indexes
[i
];
4114 if (indexes
[last
] != elem
) {
4116 indexes
[last
] = elem
;
4119 if (!indexes
.resize(last
+ 1)) {
4128 static bool SliceSparse(JSContext
* cx
, HandleObject obj
, uint64_t begin
,
4129 uint64_t end
, Handle
<ArrayObject
*> result
) {
4130 MOZ_ASSERT(begin
<= end
);
4132 Vector
<uint32_t> indexes(cx
);
4134 if (!GetIndexedPropertiesInRange(cx
, obj
, begin
, end
, indexes
, &success
)) {
4139 return CopyArrayElements(cx
, obj
, begin
, end
- begin
, result
);
4142 MOZ_ASSERT(end
<= UINT32_MAX
,
4143 "indices larger than UINT32_MAX should be rejected by "
4144 "GetIndexedPropertiesInRange");
4146 RootedValue
value(cx
);
4147 for (uint32_t index
: indexes
) {
4148 MOZ_ASSERT(begin
<= index
&& index
< end
);
4151 if (!HasAndGetElement(cx
, obj
, index
, &hole
, &value
)) {
4156 !DefineDataElement(cx
, result
, index
- uint32_t(begin
), value
)) {
4164 static JSObject
* SliceArguments(JSContext
* cx
, Handle
<ArgumentsObject
*> argsobj
,
4165 uint32_t begin
, uint32_t count
) {
4166 MOZ_ASSERT(!argsobj
->hasOverriddenLength() &&
4167 !argsobj
->hasOverriddenElement());
4168 MOZ_ASSERT(begin
+ count
<= argsobj
->initialLength());
4170 ArrayObject
* result
= NewDenseFullyAllocatedArray(cx
, count
);
4174 result
->setDenseInitializedLength(count
);
4176 for (uint32_t index
= 0; index
< count
; index
++) {
4177 const Value
& v
= argsobj
->element(begin
+ index
);
4178 result
->initDenseElement(index
, v
);
4183 template <typename T
, typename ArrayLength
>
4184 static inline ArrayLength
NormalizeSliceTerm(T value
, ArrayLength length
) {
4190 } else if (double(value
) > double(length
)) {
4193 return ArrayLength(value
);
4196 static bool ArraySliceOrdinary(JSContext
* cx
, HandleObject obj
, uint64_t begin
,
4197 uint64_t end
, MutableHandleValue rval
) {
4202 if ((end
- begin
) > UINT32_MAX
) {
4203 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
4204 JSMSG_BAD_ARRAY_LENGTH
);
4207 uint32_t count
= uint32_t(end
- begin
);
4209 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, end
)) {
4210 MOZ_ASSERT(begin
<= UINT32_MAX
,
4211 "if end <= UINT32_MAX, then begin <= UINT32_MAX");
4212 JSObject
* narr
= CopyDenseArrayElements(cx
, obj
.as
<NativeObject
>(),
4213 uint32_t(begin
), count
);
4218 rval
.setObject(*narr
);
4222 if (obj
->is
<ArgumentsObject
>()) {
4223 Handle
<ArgumentsObject
*> argsobj
= obj
.as
<ArgumentsObject
>();
4224 if (!argsobj
->hasOverriddenLength() && !argsobj
->hasOverriddenElement()) {
4225 MOZ_ASSERT(begin
<= UINT32_MAX
, "begin is limited by |argsobj|'s length");
4226 JSObject
* narr
= SliceArguments(cx
, argsobj
, uint32_t(begin
), count
);
4231 rval
.setObject(*narr
);
4236 Rooted
<ArrayObject
*> narr(cx
, NewDensePartlyAllocatedArray(cx
, count
));
4241 if (end
<= UINT32_MAX
) {
4242 if (js::GetElementsOp op
= obj
->getOpsGetElements()) {
4243 ElementAdder
adder(cx
, narr
, count
,
4244 ElementAdder::CheckHasElemPreserveHoles
);
4245 if (!op(cx
, obj
, uint32_t(begin
), uint32_t(end
), &adder
)) {
4249 rval
.setObject(*narr
);
4254 if (obj
->is
<NativeObject
>() && obj
->as
<NativeObject
>().isIndexed() &&
4256 if (!SliceSparse(cx
, obj
, begin
, end
, narr
)) {
4260 if (!CopyArrayElements(cx
, obj
, begin
, count
, narr
)) {
4265 rval
.setObject(*narr
);
4269 /* ES 2016 draft Mar 25, 2016 22.1.3.23. */
4270 static bool array_slice(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4271 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "slice");
4272 CallArgs args
= CallArgsFromVp(argc
, vp
);
4275 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4282 if (!GetLengthPropertyInlined(cx
, obj
, &length
)) {
4287 uint64_t final
= length
;
4288 if (args
.length() > 0) {
4291 if (!ToInteger(cx
, args
[0], &d
)) {
4296 k
= NormalizeSliceTerm(d
, length
);
4298 if (args
.hasDefined(1)) {
4300 if (!ToInteger(cx
, args
[1], &d
)) {
4305 final
= NormalizeSliceTerm(d
, length
);
4309 if (IsArraySpecies(cx
, obj
)) {
4310 /* Steps 7-12: Optimized for ordinary array. */
4311 return ArraySliceOrdinary(cx
, obj
, k
, final
, args
.rval());
4315 uint64_t count
= final
> k
? final
- k
: 0;
4318 RootedObject
arr(cx
);
4319 if (!ArraySpeciesCreate(cx
, obj
, count
, &arr
)) {
4327 RootedValue
kValue(cx
);
4329 if (!CheckForInterrupt(cx
)) {
4333 /* Steps 10.a-b, and 10.c.i. */
4335 if (!HasAndGetElement(cx
, obj
, k
, &kNotPresent
, &kValue
)) {
4341 /* Steps 10.c.ii. */
4342 if (!DefineArrayElement(cx
, arr
, n
, kValue
)) {
4354 if (!SetLengthProperty(cx
, arr
, n
)) {
4359 args
.rval().setObject(*arr
);
4363 static bool ArraySliceDenseKernel(JSContext
* cx
, ArrayObject
* arr
,
4364 int32_t beginArg
, int32_t endArg
,
4365 ArrayObject
* result
) {
4366 uint32_t length
= arr
->length();
4368 uint32_t begin
= NormalizeSliceTerm(beginArg
, length
);
4369 uint32_t end
= NormalizeSliceTerm(endArg
, length
);
4375 uint32_t count
= end
- begin
;
4376 size_t initlen
= arr
->getDenseInitializedLength();
4377 if (initlen
> begin
) {
4378 uint32_t newlength
= std::min
<uint32_t>(initlen
- begin
, count
);
4379 if (newlength
> 0) {
4380 if (!result
->ensureElements(cx
, newlength
)) {
4383 result
->initDenseElements(arr
, begin
, newlength
);
4387 MOZ_ASSERT(count
>= result
->length());
4388 result
->setLength(count
);
4393 JSObject
* js::ArraySliceDense(JSContext
* cx
, HandleObject obj
, int32_t begin
,
4394 int32_t end
, HandleObject result
) {
4395 MOZ_ASSERT(IsPackedArray(obj
));
4397 if (result
&& IsArraySpecies(cx
, obj
)) {
4398 if (!ArraySliceDenseKernel(cx
, &obj
->as
<ArrayObject
>(), begin
, end
,
4399 &result
->as
<ArrayObject
>())) {
4405 // Slower path if the JIT wasn't able to allocate an object inline.
4406 JS::RootedValueArray
<4> argv(cx
);
4407 argv
[0].setUndefined();
4408 argv
[1].setObject(*obj
);
4409 argv
[2].setInt32(begin
);
4410 argv
[3].setInt32(end
);
4411 if (!array_slice(cx
, 2, argv
.begin())) {
4414 return &argv
[0].toObject();
4417 JSObject
* js::ArgumentsSliceDense(JSContext
* cx
, HandleObject obj
,
4418 int32_t begin
, int32_t end
,
4419 HandleObject result
) {
4420 MOZ_ASSERT(obj
->is
<ArgumentsObject
>());
4421 MOZ_ASSERT(IsArraySpecies(cx
, obj
));
4423 Handle
<ArgumentsObject
*> argsobj
= obj
.as
<ArgumentsObject
>();
4424 MOZ_ASSERT(!argsobj
->hasOverriddenLength());
4425 MOZ_ASSERT(!argsobj
->hasOverriddenElement());
4427 uint32_t length
= argsobj
->initialLength();
4428 uint32_t actualBegin
= NormalizeSliceTerm(begin
, length
);
4429 uint32_t actualEnd
= NormalizeSliceTerm(end
, length
);
4431 if (actualBegin
> actualEnd
) {
4432 actualBegin
= actualEnd
;
4434 uint32_t count
= actualEnd
- actualBegin
;
4437 Handle
<ArrayObject
*> resArray
= result
.as
<ArrayObject
>();
4438 MOZ_ASSERT(resArray
->getDenseInitializedLength() == 0);
4439 MOZ_ASSERT(resArray
->length() == 0);
4442 if (!resArray
->ensureElements(cx
, count
)) {
4445 resArray
->setDenseInitializedLength(count
);
4446 resArray
->setLength(count
);
4448 for (uint32_t index
= 0; index
< count
; index
++) {
4449 const Value
& v
= argsobj
->element(actualBegin
+ index
);
4450 resArray
->initDenseElement(index
, v
);
4457 // Slower path if the JIT wasn't able to allocate an object inline.
4458 return SliceArguments(cx
, argsobj
, actualBegin
, count
);
4461 static bool array_isArray(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4462 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array", "isArray");
4463 CallArgs args
= CallArgsFromVp(argc
, vp
);
4465 bool isArray
= false;
4466 if (args
.get(0).isObject()) {
4467 RootedObject
obj(cx
, &args
[0].toObject());
4468 if (!IsArray(cx
, obj
, &isArray
)) {
4472 args
.rval().setBoolean(isArray
);
4476 static bool ArrayFromCallArgs(JSContext
* cx
, CallArgs
& args
,
4477 HandleObject proto
= nullptr) {
4479 NewDenseCopiedArrayWithProto(cx
, args
.length(), args
.array(), proto
);
4484 args
.rval().setObject(*obj
);
4488 static bool array_of(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4489 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array", "of");
4490 CallArgs args
= CallArgsFromVp(argc
, vp
);
4492 bool isArrayConstructor
=
4493 IsArrayConstructor(args
.thisv()) &&
4494 args
.thisv().toObject().nonCCWRealm() == cx
->realm();
4496 if (isArrayConstructor
|| !IsConstructor(args
.thisv())) {
4497 // isArrayConstructor will usually be true in practice. This is the most
4499 return ArrayFromCallArgs(cx
, args
);
4503 RootedObject
obj(cx
);
4505 FixedConstructArgs
<1> cargs(cx
);
4507 cargs
[0].setNumber(args
.length());
4509 if (!Construct(cx
, args
.thisv(), cargs
, args
.thisv(), &obj
)) {
4515 for (unsigned k
= 0; k
< args
.length(); k
++) {
4516 if (!DefineDataElement(cx
, obj
, k
, args
[k
])) {
4522 if (!SetLengthProperty(cx
, obj
, args
.length())) {
4527 args
.rval().setObject(*obj
);
4531 static const JSJitInfo array_splice_info
= {
4532 {(JSJitGetterOp
)array_splice_noRetVal
},
4535 JSJitInfo::IgnoresReturnValueNative
,
4536 JSJitInfo::AliasEverything
,
4537 JSVAL_TYPE_UNDEFINED
,
4540 enum class SearchKind
{
4541 // Specializes SearchElementDense for Array.prototype.indexOf/lastIndexOf.
4542 // This means hole values are ignored and StrictlyEqual semantics are used.
4544 // Specializes SearchElementDense for Array.prototype.includes.
4545 // This means hole values are treated as |undefined| and SameValueZero
4546 // semantics are used.
4550 template <SearchKind Kind
, typename Iter
>
4551 static bool SearchElementDense(JSContext
* cx
, HandleValue val
, Iter iterator
,
4552 MutableHandleValue rval
) {
4553 // We assume here and in the iterator lambdas that nothing can trigger GC or
4554 // move dense elements.
4555 AutoCheckCannotGC nogc
;
4557 // Fast path for string values.
4558 if (val
.isString()) {
4559 JSLinearString
* str
= val
.toString()->ensureLinear(cx
);
4563 const uint32_t strLen
= str
->length();
4564 auto cmp
= [str
, strLen
](JSContext
* cx
, const Value
& element
, bool* equal
) {
4565 if (!element
.isString() || element
.toString()->length() != strLen
) {
4569 JSLinearString
* s
= element
.toString()->ensureLinear(cx
);
4573 *equal
= EqualStrings(str
, s
);
4576 return iterator(cx
, cmp
, rval
);
4579 // Fast path for numbers.
4580 if (val
.isNumber()) {
4581 double dval
= val
.toNumber();
4582 // For |includes|, two NaN values are considered equal, so we use a
4583 // different implementation for NaN.
4584 if (Kind
== SearchKind::Includes
&& std::isnan(dval
)) {
4585 auto cmp
= [](JSContext
*, const Value
& element
, bool* equal
) {
4586 *equal
= (element
.isDouble() && std::isnan(element
.toDouble()));
4589 return iterator(cx
, cmp
, rval
);
4591 auto cmp
= [dval
](JSContext
*, const Value
& element
, bool* equal
) {
4592 *equal
= (element
.isNumber() && element
.toNumber() == dval
);
4595 return iterator(cx
, cmp
, rval
);
4598 // Fast path for values where we can use a simple bitwise comparison.
4599 if (CanUseBitwiseCompareForStrictlyEqual(val
)) {
4600 // For |includes| we need to treat hole values as |undefined| so we use a
4601 // different path if searching for |undefined|.
4602 if (Kind
== SearchKind::Includes
&& val
.isUndefined()) {
4603 auto cmp
= [](JSContext
*, const Value
& element
, bool* equal
) {
4604 *equal
= (element
.isUndefined() || element
.isMagic(JS_ELEMENTS_HOLE
));
4607 return iterator(cx
, cmp
, rval
);
4609 uint64_t bits
= val
.asRawBits();
4610 auto cmp
= [bits
](JSContext
*, const Value
& element
, bool* equal
) {
4611 *equal
= (bits
== element
.asRawBits());
4614 return iterator(cx
, cmp
, rval
);
4617 MOZ_ASSERT(val
.isBigInt() ||
4618 IF_RECORD_TUPLE(val
.isExtendedPrimitive(), false));
4620 // Generic implementation for the remaining types.
4621 RootedValue
elementRoot(cx
);
4622 auto cmp
= [val
, &elementRoot
](JSContext
* cx
, const Value
& element
,
4624 if (MOZ_UNLIKELY(element
.isMagic(JS_ELEMENTS_HOLE
))) {
4625 // |includes| treats holes as |undefined|, but |undefined| is already
4626 // handled above. For |indexOf| we have to ignore holes.
4630 // Note: |includes| uses SameValueZero, but that checks for NaN and then
4631 // calls StrictlyEqual. Since we already handled NaN above, we can call
4632 // StrictlyEqual directly.
4633 MOZ_ASSERT(!val
.isNumber());
4634 elementRoot
= element
;
4635 return StrictlyEqual(cx
, val
, elementRoot
, equal
);
4637 return iterator(cx
, cmp
, rval
);
4640 // ES2020 draft rev dc1e21c454bd316810be1c0e7af0131a2d7f38e9
4641 // 22.1.3.14 Array.prototype.indexOf ( searchElement [ , fromIndex ] )
4642 bool js::array_indexOf(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4643 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "indexOf");
4644 CallArgs args
= CallArgsFromVp(argc
, vp
);
4647 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4654 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
4660 args
.rval().setInt32(-1);
4666 if (args
.length() > 1) {
4668 if (!ToInteger(cx
, args
[1], &n
)) {
4673 if (n
>= double(len
)) {
4674 args
.rval().setInt32(-1);
4682 double d
= double(len
) + n
;
4689 MOZ_ASSERT(k
< len
);
4691 HandleValue searchElement
= args
.get(0);
4693 // Steps 9 and 10 optimized for dense elements.
4694 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
)) {
4695 MOZ_ASSERT(len
<= UINT32_MAX
);
4697 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
4698 uint32_t start
= uint32_t(k
);
4700 std::min(nobj
->getDenseInitializedLength(), uint32_t(len
));
4701 const Value
* elements
= nobj
->getDenseElements();
4703 if (CanUseBitwiseCompareForStrictlyEqual(searchElement
) && length
> start
) {
4704 const uint64_t* elementsAsBits
=
4705 reinterpret_cast<const uint64_t*>(elements
);
4706 const uint64_t* res
= SIMD::memchr64(
4707 elementsAsBits
+ start
, searchElement
.asRawBits(), length
- start
);
4709 args
.rval().setInt32(static_cast<int32_t>(res
- elementsAsBits
));
4711 args
.rval().setInt32(-1);
4716 auto iterator
= [elements
, start
, length
](JSContext
* cx
, auto cmp
,
4717 MutableHandleValue rval
) {
4718 static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT
<= INT32_MAX
,
4719 "code assumes dense index fits in Int32Value");
4720 for (uint32_t i
= start
; i
< length
; i
++) {
4722 if (MOZ_UNLIKELY(!cmp(cx
, elements
[i
], &equal
))) {
4726 rval
.setInt32(int32_t(i
));
4733 return SearchElementDense
<SearchKind::IndexOf
>(cx
, searchElement
, iterator
,
4739 for (; k
< len
; k
++) {
4740 if (!CheckForInterrupt(cx
)) {
4745 if (!HasAndGetElement(cx
, obj
, k
, &hole
, &v
)) {
4753 if (!StrictlyEqual(cx
, v
, searchElement
, &equal
)) {
4757 args
.rval().setNumber(k
);
4763 args
.rval().setInt32(-1);
4767 // ES2020 draft rev dc1e21c454bd316810be1c0e7af0131a2d7f38e9
4768 // 22.1.3.17 Array.prototype.lastIndexOf ( searchElement [ , fromIndex ] )
4769 bool js::array_lastIndexOf(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4770 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "lastIndexOf");
4771 CallArgs args
= CallArgsFromVp(argc
, vp
);
4774 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4781 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
4787 args
.rval().setInt32(-1);
4792 uint64_t k
= len
- 1;
4793 if (args
.length() > 1) {
4795 if (!ToInteger(cx
, args
[1], &n
)) {
4801 double d
= double(len
) + n
;
4803 args
.rval().setInt32(-1);
4807 } else if (n
< double(k
)) {
4812 MOZ_ASSERT(k
< len
);
4814 HandleValue searchElement
= args
.get(0);
4816 // Steps 7 and 8 optimized for dense elements.
4817 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, k
+ 1)) {
4818 MOZ_ASSERT(k
<= UINT32_MAX
);
4820 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
4821 uint32_t initLen
= nobj
->getDenseInitializedLength();
4823 args
.rval().setInt32(-1);
4827 uint32_t end
= std::min(uint32_t(k
), initLen
- 1);
4828 const Value
* elements
= nobj
->getDenseElements();
4830 auto iterator
= [elements
, end
](JSContext
* cx
, auto cmp
,
4831 MutableHandleValue rval
) {
4832 static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT
<= INT32_MAX
,
4833 "code assumes dense index fits in int32_t");
4834 for (int32_t i
= int32_t(end
); i
>= 0; i
--) {
4836 if (MOZ_UNLIKELY(!cmp(cx
, elements
[i
], &equal
))) {
4840 rval
.setInt32(int32_t(i
));
4847 return SearchElementDense
<SearchKind::IndexOf
>(cx
, searchElement
, iterator
,
4853 for (int64_t i
= int64_t(k
); i
>= 0; i
--) {
4854 if (!CheckForInterrupt(cx
)) {
4859 if (!HasAndGetElement(cx
, obj
, uint64_t(i
), &hole
, &v
)) {
4867 if (!StrictlyEqual(cx
, v
, searchElement
, &equal
)) {
4871 args
.rval().setNumber(uint64_t(i
));
4877 args
.rval().setInt32(-1);
4881 // ES2020 draft rev dc1e21c454bd316810be1c0e7af0131a2d7f38e9
4882 // 22.1.3.13 Array.prototype.includes ( searchElement [ , fromIndex ] )
4883 bool js::array_includes(JSContext
* cx
, unsigned argc
, Value
* vp
) {
4884 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "includes");
4885 CallArgs args
= CallArgsFromVp(argc
, vp
);
4888 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
4895 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
4901 args
.rval().setBoolean(false);
4907 if (args
.length() > 1) {
4909 if (!ToInteger(cx
, args
[1], &n
)) {
4913 if (n
>= double(len
)) {
4914 args
.rval().setBoolean(false);
4922 double d
= double(len
) + n
;
4929 MOZ_ASSERT(k
< len
);
4931 HandleValue searchElement
= args
.get(0);
4933 // Steps 8 and 9 optimized for dense elements.
4934 if (CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
)) {
4935 MOZ_ASSERT(len
<= UINT32_MAX
);
4937 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
4938 uint32_t start
= uint32_t(k
);
4940 std::min(nobj
->getDenseInitializedLength(), uint32_t(len
));
4941 const Value
* elements
= nobj
->getDenseElements();
4943 // Trailing holes are treated as |undefined|.
4944 if (uint32_t(len
) > length
&& searchElement
.isUndefined()) {
4945 // |undefined| is strictly equal only to |undefined|.
4946 args
.rval().setBoolean(true);
4950 // For |includes| we need to treat hole values as |undefined| so we use a
4951 // different path if searching for |undefined|.
4952 if (CanUseBitwiseCompareForStrictlyEqual(searchElement
) &&
4953 !searchElement
.isUndefined() && length
> start
) {
4954 if (SIMD::memchr64(reinterpret_cast<const uint64_t*>(elements
) + start
,
4955 searchElement
.asRawBits(), length
- start
)) {
4956 args
.rval().setBoolean(true);
4958 args
.rval().setBoolean(false);
4963 auto iterator
= [elements
, start
, length
](JSContext
* cx
, auto cmp
,
4964 MutableHandleValue rval
) {
4965 for (uint32_t i
= start
; i
< length
; i
++) {
4967 if (MOZ_UNLIKELY(!cmp(cx
, elements
[i
], &equal
))) {
4971 rval
.setBoolean(true);
4975 rval
.setBoolean(false);
4978 return SearchElementDense
<SearchKind::Includes
>(cx
, searchElement
, iterator
,
4984 for (; k
< len
; k
++) {
4985 if (!CheckForInterrupt(cx
)) {
4989 if (!GetArrayElement(cx
, obj
, k
, &v
)) {
4994 if (!SameValueZero(cx
, v
, searchElement
, &equal
)) {
4998 args
.rval().setBoolean(true);
5004 args
.rval().setBoolean(false);
5008 // ES2024 draft 23.1.3.2.1 IsConcatSpreadable
5009 static bool IsConcatSpreadable(JSContext
* cx
, HandleValue v
, bool* spreadable
) {
5011 if (!v
.isObject()) {
5012 *spreadable
= false;
5017 JS::Symbol
* sym
= cx
->wellKnownSymbols().isConcatSpreadable
;
5020 MaybeHasInterestingSymbolProperty(cx
, &v
.toObject(), sym
, &holder
))) {
5021 RootedValue
res(cx
);
5022 RootedObject
obj(cx
, holder
);
5023 Rooted
<PropertyKey
> key(cx
, PropertyKey::Symbol(sym
));
5024 if (!GetProperty(cx
, obj
, v
, key
, &res
)) {
5028 if (!res
.isUndefined()) {
5029 *spreadable
= ToBoolean(res
);
5035 if (MOZ_LIKELY(v
.toObject().is
<ArrayObject
>())) {
5039 RootedObject
obj(cx
, &v
.toObject());
5041 if (!JS::IsArray(cx
, obj
, &isArray
)) {
5044 *spreadable
= isArray
;
5048 // Returns true if the object may have an @@isConcatSpreadable property.
5049 static bool MaybeHasIsConcatSpreadable(JSContext
* cx
, JSObject
* obj
) {
5050 JS::Symbol
* sym
= cx
->wellKnownSymbols().isConcatSpreadable
;
5052 return MaybeHasInterestingSymbolProperty(cx
, obj
, sym
, &holder
);
5055 static bool TryOptimizePackedArrayConcat(JSContext
* cx
, CallArgs
& args
,
5056 Handle
<JSObject
*> obj
,
5058 // Fast path for the following cases:
5060 // (1) packedArray.concat(): copy the array's elements.
5061 // (2) packedArray.concat(packedArray): concatenate two packed arrays.
5062 // (3) packedArray.concat(value): copy and append a single non-array value.
5064 // These cases account for almost all calls to Array.prototype.concat in
5069 if (args
.length() > 1) {
5073 // The `this` object must be a packed array without @@isConcatSpreadable.
5074 // @@isConcatSpreadable is uncommon and requires a property lookup and more
5075 // complicated code, so we let the slow path handle it.
5076 if (!IsPackedArray(obj
)) {
5079 if (MaybeHasIsConcatSpreadable(cx
, obj
)) {
5083 Handle
<ArrayObject
*> thisArr
= obj
.as
<ArrayObject
>();
5084 uint32_t thisLen
= thisArr
->length();
5086 if (args
.length() == 0) {
5087 // Case (1). Copy the packed array.
5088 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, thisLen
);
5092 arr
->initDenseElements(thisArr
->getDenseElements(), thisLen
);
5093 args
.rval().setObject(*arr
);
5098 MOZ_ASSERT(args
.length() == 1);
5100 // If the argument is an object, it must not have an @@isConcatSpreadable
5102 if (args
[0].isObject() &&
5103 MaybeHasIsConcatSpreadable(cx
, &args
[0].toObject())) {
5107 MOZ_ASSERT_IF(args
[0].isObject(), args
[0].toObject().is
<NativeObject
>());
5109 // Case (3). Copy and append a single value if the argument is not an array.
5110 if (!args
[0].isObject() || !args
[0].toObject().is
<ArrayObject
>()) {
5111 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, thisLen
+ 1);
5115 arr
->initDenseElements(thisArr
->getDenseElements(), thisLen
);
5117 arr
->ensureDenseInitializedLength(thisLen
, 1);
5118 arr
->initDenseElement(thisLen
, args
[0]);
5120 args
.rval().setObject(*arr
);
5125 // Case (2). Concatenate two packed arrays.
5126 if (!IsPackedArray(&args
[0].toObject())) {
5130 uint32_t argLen
= args
[0].toObject().as
<ArrayObject
>().length();
5132 // Compute the array length. This can't overflow because both arrays are
5134 static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT
< INT32_MAX
);
5135 MOZ_ASSERT(thisLen
<= NativeObject::MAX_DENSE_ELEMENTS_COUNT
);
5136 MOZ_ASSERT(argLen
<= NativeObject::MAX_DENSE_ELEMENTS_COUNT
);
5137 uint32_t totalLen
= thisLen
+ argLen
;
5139 ArrayObject
* arr
= NewDenseFullyAllocatedArray(cx
, totalLen
);
5143 arr
->initDenseElements(thisArr
->getDenseElements(), thisLen
);
5145 ArrayObject
* argArr
= &args
[0].toObject().as
<ArrayObject
>();
5146 arr
->ensureDenseInitializedLength(thisLen
, argLen
);
5147 arr
->initDenseElementRange(thisLen
, argArr
, argLen
);
5149 args
.rval().setObject(*arr
);
5154 static bool array_concat(JSContext
* cx
, unsigned argc
, Value
* vp
) {
5155 AutoJSMethodProfilerEntry
pseudoFrame(cx
, "Array.prototype", "concat");
5156 CallArgs args
= CallArgsFromVp(argc
, vp
);
5159 RootedObject
obj(cx
, ToObject(cx
, args
.thisv()));
5164 bool isArraySpecies
= IsArraySpecies(cx
, obj
);
5166 // Fast path for the most common cases.
5167 if (isArraySpecies
) {
5169 if (!TryOptimizePackedArrayConcat(cx
, args
, obj
, &optimized
)) {
5178 RootedObject
arr(cx
);
5179 if (isArraySpecies
) {
5180 arr
= NewDenseEmptyArray(cx
);
5185 if (!ArraySpeciesCreate(cx
, obj
, 0, &arr
)) {
5193 // Step 4 (handled implicitly with nextArg and CallArgs).
5194 uint32_t nextArg
= 0;
5197 RootedValue
v(cx
, ObjectValue(*obj
));
5201 if (!IsConcatSpreadable(cx
, v
, &spreadable
)) {
5207 obj
= &v
.toObject();
5209 if (!GetLengthPropertyInlined(cx
, obj
, &len
)) {
5214 if (n
+ len
> uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
) - 1) {
5215 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5216 JSMSG_TOO_LONG_ARRAY
);
5225 // Try a fast path for copying dense elements directly.
5226 bool optimized
= false;
5227 if (len
> 0 && isArraySpecies
&&
5228 CanOptimizeForDenseStorage
<ArrayAccess::Read
>(obj
, len
) &&
5229 n
+ len
<= NativeObject::MAX_DENSE_ELEMENTS_COUNT
) {
5230 NativeObject
* nobj
= &obj
->as
<NativeObject
>();
5231 ArrayObject
* resArr
= &arr
->as
<ArrayObject
>();
5233 std::min(uint32_t(len
), nobj
->getDenseInitializedLength());
5235 DenseElementResult res
= resArr
->ensureDenseElements(cx
, n
, count
);
5236 if (res
== DenseElementResult::Failure
) {
5239 if (res
== DenseElementResult::Success
) {
5240 resArr
->initDenseElementRange(n
, nobj
, count
);
5244 MOZ_ASSERT(res
== DenseElementResult::Incomplete
);
5251 if (!CheckForInterrupt(cx
)) {
5257 if (!HasAndGetElement(cx
, obj
, k
, &hole
, &v
)) {
5262 if (!DefineArrayElement(cx
, arr
, n
, v
)) {
5276 if (n
>= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
) - 1) {
5277 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5278 JSMSG_TOO_LONG_ARRAY
);
5283 if (!DefineArrayElement(cx
, arr
, n
, v
)) {
5291 // Move on to the next argument.
5292 if (nextArg
== args
.length()) {
5300 if (!SetLengthProperty(cx
, arr
, n
)) {
5305 args
.rval().setObject(*arr
);
5309 static const JSFunctionSpec array_methods
[] = {
5310 JS_FN("toSource", array_toSource
, 0, 0),
5311 JS_SELF_HOSTED_FN("toString", "ArrayToString", 0, 0),
5312 JS_FN("toLocaleString", array_toLocaleString
, 0, 0),
5314 /* Perl-ish methods. */
5315 JS_INLINABLE_FN("join", array_join
, 1, 0, ArrayJoin
),
5316 JS_FN("reverse", array_reverse
, 0, 0),
5317 JS_TRAMPOLINE_FN("sort", array_sort
, 1, 0, ArraySort
),
5318 JS_INLINABLE_FN("push", array_push
, 1, 0, ArrayPush
),
5319 JS_INLINABLE_FN("pop", array_pop
, 0, 0, ArrayPop
),
5320 JS_INLINABLE_FN("shift", array_shift
, 0, 0, ArrayShift
),
5321 JS_FN("unshift", array_unshift
, 1, 0),
5322 JS_FNINFO("splice", array_splice
, &array_splice_info
, 2, 0),
5324 /* Pythonic sequence methods. */
5325 JS_FN("concat", array_concat
, 1, 0),
5326 JS_INLINABLE_FN("slice", array_slice
, 2, 0, ArraySlice
),
5328 JS_FN("lastIndexOf", array_lastIndexOf
, 1, 0),
5329 JS_FN("indexOf", array_indexOf
, 1, 0),
5330 JS_SELF_HOSTED_FN("forEach", "ArrayForEach", 1, 0),
5331 JS_SELF_HOSTED_FN("map", "ArrayMap", 1, 0),
5332 JS_SELF_HOSTED_FN("filter", "ArrayFilter", 1, 0),
5333 JS_SELF_HOSTED_FN("reduce", "ArrayReduce", 1, 0),
5334 JS_SELF_HOSTED_FN("reduceRight", "ArrayReduceRight", 1, 0),
5335 JS_SELF_HOSTED_FN("some", "ArraySome", 1, 0),
5336 JS_SELF_HOSTED_FN("every", "ArrayEvery", 1, 0),
5339 JS_SELF_HOSTED_FN("find", "ArrayFind", 1, 0),
5340 JS_SELF_HOSTED_FN("findIndex", "ArrayFindIndex", 1, 0),
5341 JS_SELF_HOSTED_FN("copyWithin", "ArrayCopyWithin", 3, 0),
5343 JS_SELF_HOSTED_FN("fill", "ArrayFill", 3, 0),
5345 JS_SELF_HOSTED_SYM_FN(iterator
, "$ArrayValues", 0, 0),
5346 JS_SELF_HOSTED_FN("entries", "ArrayEntries", 0, 0),
5347 JS_SELF_HOSTED_FN("keys", "ArrayKeys", 0, 0),
5348 JS_SELF_HOSTED_FN("values", "$ArrayValues", 0, 0),
5351 JS_FN("includes", array_includes
, 1, 0),
5354 JS_SELF_HOSTED_FN("flatMap", "ArrayFlatMap", 1, 0),
5355 JS_SELF_HOSTED_FN("flat", "ArrayFlat", 0, 0),
5358 JS_SELF_HOSTED_FN("at", "ArrayAt", 1, 0),
5359 JS_SELF_HOSTED_FN("findLast", "ArrayFindLast", 1, 0),
5360 JS_SELF_HOSTED_FN("findLastIndex", "ArrayFindLastIndex", 1, 0),
5362 JS_SELF_HOSTED_FN("toReversed", "ArrayToReversed", 0, 0),
5363 JS_SELF_HOSTED_FN("toSorted", "ArrayToSorted", 1, 0),
5364 JS_FN("toSpliced", array_toSpliced
, 2, 0), JS_FN("with", array_with
, 2, 0),
5368 static const JSFunctionSpec array_static_methods
[] = {
5369 JS_INLINABLE_FN("isArray", array_isArray
, 1, 0, ArrayIsArray
),
5370 JS_SELF_HOSTED_FN("from", "ArrayFrom", 3, 0),
5371 JS_SELF_HOSTED_FN("fromAsync", "ArrayFromAsync", 3, 0),
5372 JS_FN("of", array_of
, 0, 0),
5376 const JSPropertySpec array_static_props
[] = {
5377 JS_SELF_HOSTED_SYM_GET(species
, "$ArraySpecies", 0), JS_PS_END
};
5379 static inline bool ArrayConstructorImpl(JSContext
* cx
, CallArgs
& args
,
5380 bool isConstructor
) {
5381 RootedObject
proto(cx
);
5382 if (isConstructor
) {
5383 if (!GetPrototypeFromBuiltinConstructor(cx
, args
, JSProto_Array
, &proto
)) {
5388 if (args
.length() != 1 || !args
[0].isNumber()) {
5389 return ArrayFromCallArgs(cx
, args
, proto
);
5393 if (args
[0].isInt32()) {
5394 int32_t i
= args
[0].toInt32();
5396 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5397 JSMSG_BAD_ARRAY_LENGTH
);
5400 length
= uint32_t(i
);
5402 double d
= args
[0].toDouble();
5403 length
= ToUint32(d
);
5404 if (d
!= double(length
)) {
5405 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5406 JSMSG_BAD_ARRAY_LENGTH
);
5411 ArrayObject
* obj
= NewDensePartlyAllocatedArrayWithProto(cx
, length
, proto
);
5416 args
.rval().setObject(*obj
);
5421 bool js::ArrayConstructor(JSContext
* cx
, unsigned argc
, Value
* vp
) {
5422 AutoJSConstructorProfilerEntry
pseudoFrame(cx
, "Array");
5423 CallArgs args
= CallArgsFromVp(argc
, vp
);
5424 return ArrayConstructorImpl(cx
, args
, /* isConstructor = */ true);
5427 bool js::array_construct(JSContext
* cx
, unsigned argc
, Value
* vp
) {
5428 AutoJSConstructorProfilerEntry
pseudoFrame(cx
, "Array");
5429 CallArgs args
= CallArgsFromVp(argc
, vp
);
5430 MOZ_ASSERT(!args
.isConstructing());
5431 MOZ_ASSERT(args
.length() == 1);
5432 MOZ_ASSERT(args
[0].isNumber());
5433 return ArrayConstructorImpl(cx
, args
, /* isConstructor = */ false);
5436 ArrayObject
* js::ArrayConstructorOneArg(JSContext
* cx
,
5437 Handle
<ArrayObject
*> templateObject
,
5438 int32_t lengthInt
) {
5439 // JIT code can call this with a template object from a different realm when
5440 // calling another realm's Array constructor.
5441 Maybe
<AutoRealm
> ar
;
5442 if (cx
->realm() != templateObject
->realm()) {
5443 MOZ_ASSERT(cx
->compartment() == templateObject
->compartment());
5444 ar
.emplace(cx
, templateObject
);
5447 if (lengthInt
< 0) {
5448 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5449 JSMSG_BAD_ARRAY_LENGTH
);
5453 uint32_t length
= uint32_t(lengthInt
);
5454 ArrayObject
* res
= NewDensePartlyAllocatedArray(cx
, length
);
5455 MOZ_ASSERT_IF(res
, res
->realm() == templateObject
->realm());
5460 * Array allocation functions.
5463 static inline bool EnsureNewArrayElements(JSContext
* cx
, ArrayObject
* obj
,
5466 * If ensureElements creates dynamically allocated slots, then having
5467 * fixedSlots is a waste.
5469 DebugOnly
<uint32_t> cap
= obj
->getDenseCapacity();
5471 if (!obj
->ensureElements(cx
, length
)) {
5475 MOZ_ASSERT_IF(cap
, !obj
->hasDynamicElements());
5480 template <uint32_t maxLength
>
5481 static MOZ_ALWAYS_INLINE ArrayObject
* NewArrayWithShape(
5482 JSContext
* cx
, Handle
<SharedShape
*> shape
, uint32_t length
,
5483 NewObjectKind newKind
, gc::AllocSite
* site
= nullptr) {
5484 // The shape must already have the |length| property defined on it.
5485 MOZ_ASSERT(shape
->propMapLength() == 1);
5486 MOZ_ASSERT(shape
->lastProperty().key() == NameToId(cx
->names().length
));
5488 gc::AllocKind allocKind
= GuessArrayGCKind(length
);
5489 MOZ_ASSERT(CanChangeToBackgroundAllocKind(allocKind
, &ArrayObject::class_
));
5490 allocKind
= ForegroundToBackgroundAllocKind(allocKind
);
5492 MOZ_ASSERT(shape
->slotSpan() == 0);
5493 constexpr uint32_t slotSpan
= 0;
5495 AutoSetNewObjectMetadata
metadata(cx
);
5496 ArrayObject
* arr
= ArrayObject::create(
5497 cx
, allocKind
, GetInitialHeap(newKind
, &ArrayObject::class_
, site
), shape
,
5498 length
, slotSpan
, metadata
);
5503 if (maxLength
> 0 &&
5504 !EnsureNewArrayElements(cx
, arr
, std::min(maxLength
, length
))) {
5508 probes::CreateObject(cx
, arr
);
5512 static SharedShape
* GetArrayShapeWithProto(JSContext
* cx
, HandleObject proto
) {
5513 // Get a shape with zero fixed slots, because arrays store the ObjectElements
5515 Rooted
<SharedShape
*> shape(
5516 cx
, SharedShape::getInitialShape(cx
, &ArrayObject::class_
, cx
->realm(),
5517 TaggedProto(proto
), /* nfixed = */ 0));
5522 // Add the |length| property and use the new shape as initial shape for new
5524 if (shape
->propMapLength() == 0) {
5525 shape
= AddLengthProperty(cx
, shape
);
5529 SharedShape::insertInitialShape(cx
, shape
);
5531 MOZ_ASSERT(shape
->propMapLength() == 1);
5532 MOZ_ASSERT(shape
->lastProperty().key() == NameToId(cx
->names().length
));
5538 SharedShape
* GlobalObject::createArrayShapeWithDefaultProto(JSContext
* cx
) {
5539 MOZ_ASSERT(!cx
->global()->data().arrayShapeWithDefaultProto
);
5541 RootedObject
proto(cx
,
5542 GlobalObject::getOrCreateArrayPrototype(cx
, cx
->global()));
5547 SharedShape
* shape
= GetArrayShapeWithProto(cx
, proto
);
5552 cx
->global()->data().arrayShapeWithDefaultProto
.init(shape
);
5556 template <uint32_t maxLength
>
5557 static MOZ_ALWAYS_INLINE ArrayObject
* NewArray(JSContext
* cx
, uint32_t length
,
5558 NewObjectKind newKind
,
5559 gc::AllocSite
* site
= nullptr) {
5560 Rooted
<SharedShape
*> shape(cx
,
5561 GlobalObject::getArrayShapeWithDefaultProto(cx
));
5566 return NewArrayWithShape
<maxLength
>(cx
, shape
, length
, newKind
, site
);
5569 template <uint32_t maxLength
>
5570 static MOZ_ALWAYS_INLINE ArrayObject
* NewArrayWithProto(JSContext
* cx
,
5573 NewObjectKind newKind
) {
5574 Rooted
<SharedShape
*> shape(cx
);
5575 if (!proto
|| proto
== cx
->global()->maybeGetArrayPrototype()) {
5576 shape
= GlobalObject::getArrayShapeWithDefaultProto(cx
);
5578 shape
= GetArrayShapeWithProto(cx
, proto
);
5584 return NewArrayWithShape
<maxLength
>(cx
, shape
, length
, newKind
, nullptr);
5587 static JSObject
* CreateArrayPrototype(JSContext
* cx
, JSProtoKey key
) {
5588 MOZ_ASSERT(key
== JSProto_Array
);
5589 RootedObject
proto(cx
, &cx
->global()->getObjectPrototype());
5590 return NewArrayWithProto
<0>(cx
, 0, proto
, TenuredObject
);
5593 static bool array_proto_finish(JSContext
* cx
, JS::HandleObject ctor
,
5594 JS::HandleObject proto
) {
5595 // Add Array.prototype[@@unscopables]. ECMA-262 draft (2016 Mar 19) 22.1.3.32.
5596 RootedObject
unscopables(cx
,
5597 NewPlainObjectWithProto(cx
, nullptr, TenuredObject
));
5602 RootedValue
value(cx
, BooleanValue(true));
5603 if (!DefineDataProperty(cx
, unscopables
, cx
->names().at
, value
) ||
5604 !DefineDataProperty(cx
, unscopables
, cx
->names().copyWithin
, value
) ||
5605 !DefineDataProperty(cx
, unscopables
, cx
->names().entries
, value
) ||
5606 !DefineDataProperty(cx
, unscopables
, cx
->names().fill
, value
) ||
5607 !DefineDataProperty(cx
, unscopables
, cx
->names().find
, value
) ||
5608 !DefineDataProperty(cx
, unscopables
, cx
->names().findIndex
, value
) ||
5609 !DefineDataProperty(cx
, unscopables
, cx
->names().findLast
, value
) ||
5610 !DefineDataProperty(cx
, unscopables
, cx
->names().findLastIndex
, value
) ||
5611 !DefineDataProperty(cx
, unscopables
, cx
->names().flat
, value
) ||
5612 !DefineDataProperty(cx
, unscopables
, cx
->names().flatMap
, value
) ||
5613 !DefineDataProperty(cx
, unscopables
, cx
->names().includes
, value
) ||
5614 !DefineDataProperty(cx
, unscopables
, cx
->names().keys
, value
) ||
5615 !DefineDataProperty(cx
, unscopables
, cx
->names().toReversed
, value
) ||
5616 !DefineDataProperty(cx
, unscopables
, cx
->names().toSorted
, value
) ||
5617 !DefineDataProperty(cx
, unscopables
, cx
->names().toSpliced
, value
) ||
5618 !DefineDataProperty(cx
, unscopables
, cx
->names().values
, value
)) {
5622 RootedId
id(cx
, PropertyKey::Symbol(cx
->wellKnownSymbols().unscopables
));
5623 value
.setObject(*unscopables
);
5624 if (!DefineDataProperty(cx
, proto
, id
, value
, JSPROP_READONLY
)) {
5628 // Mark Array prototype as having fuse property (@iterator for example).
5629 return JSObject::setHasFuseProperty(cx
, proto
);
5632 static const JSClassOps ArrayObjectClassOps
= {
5633 array_addProperty
, // addProperty
5634 nullptr, // delProperty
5635 nullptr, // enumerate
5636 nullptr, // newEnumerate
5638 nullptr, // mayResolve
5639 nullptr, // finalize
5641 nullptr, // construct
5645 static const ClassSpec ArrayObjectClassSpec
= {
5646 GenericCreateConstructor
<ArrayConstructor
, 1, gc::AllocKind::FUNCTION
,
5647 &jit::JitInfo_Array
>,
5648 CreateArrayPrototype
,
5649 array_static_methods
,
5653 array_proto_finish
};
5655 const JSClass
ArrayObject::class_
= {
5657 JSCLASS_HAS_CACHED_PROTO(JSProto_Array
) | JSCLASS_DELAY_METADATA_BUILDER
,
5658 &ArrayObjectClassOps
, &ArrayObjectClassSpec
};
5660 ArrayObject
* js::NewDenseEmptyArray(JSContext
* cx
) {
5661 return NewArray
<0>(cx
, 0, GenericObject
);
5664 ArrayObject
* js::NewTenuredDenseEmptyArray(JSContext
* cx
) {
5665 return NewArray
<0>(cx
, 0, TenuredObject
);
5668 ArrayObject
* js::NewDenseFullyAllocatedArray(
5669 JSContext
* cx
, uint32_t length
, NewObjectKind newKind
/* = GenericObject */,
5670 gc::AllocSite
* site
/* = nullptr */) {
5671 return NewArray
<UINT32_MAX
>(cx
, length
, newKind
, site
);
5674 ArrayObject
* js::NewDensePartlyAllocatedArray(
5675 JSContext
* cx
, uint32_t length
,
5676 NewObjectKind newKind
/* = GenericObject */) {
5677 return NewArray
<ArrayObject::EagerAllocationMaxLength
>(cx
, length
, newKind
);
5680 ArrayObject
* js::NewDensePartlyAllocatedArrayWithProto(JSContext
* cx
,
5682 HandleObject proto
) {
5683 return NewArrayWithProto
<ArrayObject::EagerAllocationMaxLength
>(
5684 cx
, length
, proto
, GenericObject
);
5687 ArrayObject
* js::NewDenseUnallocatedArray(
5688 JSContext
* cx
, uint32_t length
,
5689 NewObjectKind newKind
/* = GenericObject */) {
5690 return NewArray
<0>(cx
, length
, newKind
);
5693 // values must point at already-rooted Value objects
5694 ArrayObject
* js::NewDenseCopiedArray(
5695 JSContext
* cx
, uint32_t length
, const Value
* values
,
5696 NewObjectKind newKind
/* = GenericObject */) {
5697 ArrayObject
* arr
= NewArray
<UINT32_MAX
>(cx
, length
, newKind
);
5702 arr
->initDenseElements(values
, length
);
5706 // values must point at already-rooted Value objects
5707 ArrayObject
* js::NewDenseCopiedArray(
5708 JSContext
* cx
, uint32_t length
, JSLinearString
** values
,
5709 NewObjectKind newKind
/* = GenericObject */) {
5710 ArrayObject
* arr
= NewArray
<UINT32_MAX
>(cx
, length
, newKind
);
5715 arr
->initDenseElements(values
, length
);
5719 ArrayObject
* js::NewDenseCopiedArrayWithProto(JSContext
* cx
, uint32_t length
,
5720 const Value
* values
,
5721 HandleObject proto
) {
5723 NewArrayWithProto
<UINT32_MAX
>(cx
, length
, proto
, GenericObject
);
5728 arr
->initDenseElements(values
, length
);
5732 ArrayObject
* js::NewDenseFullyAllocatedArrayWithShape(
5733 JSContext
* cx
, uint32_t length
, Handle
<SharedShape
*> shape
) {
5734 AutoSetNewObjectMetadata
metadata(cx
);
5735 gc::AllocKind allocKind
= GuessArrayGCKind(length
);
5736 MOZ_ASSERT(CanChangeToBackgroundAllocKind(allocKind
, &ArrayObject::class_
));
5737 allocKind
= ForegroundToBackgroundAllocKind(allocKind
);
5739 gc::Heap heap
= GetInitialHeap(GenericObject
, &ArrayObject::class_
);
5740 ArrayObject
* arr
= ArrayObject::create(cx
, allocKind
, heap
, shape
, length
,
5741 shape
->slotSpan(), metadata
);
5746 if (!EnsureNewArrayElements(cx
, arr
, length
)) {
5750 probes::CreateObject(cx
, arr
);
5755 // TODO(no-TI): clean up.
5756 ArrayObject
* js::NewArrayWithShape(JSContext
* cx
, uint32_t length
,
5757 Handle
<Shape
*> shape
) {
5758 // Ion can call this with a shape from a different realm when calling
5759 // another realm's Array constructor.
5760 Maybe
<AutoRealm
> ar
;
5761 if (cx
->realm() != shape
->realm()) {
5762 MOZ_ASSERT(cx
->compartment() == shape
->compartment());
5763 ar
.emplace(cx
, shape
);
5766 return NewDenseFullyAllocatedArray(cx
, length
);
5770 bool js::ArrayInfo(JSContext
* cx
, unsigned argc
, Value
* vp
) {
5771 CallArgs args
= CallArgsFromVp(argc
, vp
);
5772 RootedObject
obj(cx
);
5774 for (unsigned i
= 0; i
< args
.length(); i
++) {
5775 HandleValue arg
= args
[i
];
5778 DecompileValueGenerator(cx
, JSDVG_SEARCH_STACK
, arg
, nullptr);
5782 if (arg
.isPrimitive() || !(obj
= arg
.toObjectOrNull())->is
<ArrayObject
>()) {
5783 fprintf(stderr
, "%s: not array\n", bytes
.get());
5786 fprintf(stderr
, "%s: (len %u", bytes
.get(),
5787 obj
->as
<ArrayObject
>().length());
5788 fprintf(stderr
, ", capacity %u", obj
->as
<ArrayObject
>().getDenseCapacity());
5789 fputs(")\n", stderr
);
5792 args
.rval().setUndefined();
5797 void js::ArraySpeciesLookup::initialize(JSContext
* cx
) {
5798 MOZ_ASSERT(state_
== State::Uninitialized
);
5800 // Get the canonical Array.prototype.
5801 NativeObject
* arrayProto
= cx
->global()->maybeGetArrayPrototype();
5803 // Leave the cache uninitialized if the Array class itself is not yet
5809 // Get the canonical Array constructor. The Array constructor must be
5810 // initialized if Array.prototype is initialized.
5811 JSObject
& arrayCtorObject
= cx
->global()->getConstructor(JSProto_Array
);
5812 JSFunction
* arrayCtor
= &arrayCtorObject
.as
<JSFunction
>();
5814 // Shortcut returns below means Array[@@species] will never be
5815 // optimizable, set to disabled now, and clear it later when we succeed.
5816 state_
= State::Disabled
;
5818 // Look up Array.prototype.constructor and ensure it's a data property.
5819 Maybe
<PropertyInfo
> ctorProp
=
5820 arrayProto
->lookup(cx
, NameToId(cx
->names().constructor
));
5821 if (ctorProp
.isNothing() || !ctorProp
->isDataProperty()) {
5825 // Get the referred value, and ensure it holds the canonical Array
5827 JSFunction
* ctorFun
;
5828 if (!IsFunctionObject(arrayProto
->getSlot(ctorProp
->slot()), &ctorFun
)) {
5831 if (ctorFun
!= arrayCtor
) {
5835 // Look up the '@@species' value on Array
5836 Maybe
<PropertyInfo
> speciesProp
= arrayCtor
->lookup(
5837 cx
, PropertyKey::Symbol(cx
->wellKnownSymbols().species
));
5838 if (speciesProp
.isNothing() || !arrayCtor
->hasGetter(*speciesProp
)) {
5842 // Get the referred value, ensure it holds the canonical Array[@@species]
5844 uint32_t speciesGetterSlot
= speciesProp
->slot();
5845 JSObject
* speciesGetter
= arrayCtor
->getGetter(speciesGetterSlot
);
5846 if (!speciesGetter
|| !speciesGetter
->is
<JSFunction
>()) {
5849 JSFunction
* speciesFun
= &speciesGetter
->as
<JSFunction
>();
5850 if (!IsSelfHostedFunctionWithName(speciesFun
,
5851 cx
->names().dollar_ArraySpecies_
)) {
5855 // Store raw pointers below. This is okay to do here, because all objects
5856 // are in the tenured heap.
5857 MOZ_ASSERT(!IsInsideNursery(arrayProto
));
5858 MOZ_ASSERT(!IsInsideNursery(arrayCtor
));
5859 MOZ_ASSERT(!IsInsideNursery(arrayCtor
->shape()));
5860 MOZ_ASSERT(!IsInsideNursery(speciesFun
));
5861 MOZ_ASSERT(!IsInsideNursery(arrayProto
->shape()));
5863 state_
= State::Initialized
;
5864 arrayProto_
= arrayProto
;
5865 arrayConstructor_
= arrayCtor
;
5866 arrayConstructorShape_
= arrayCtor
->shape();
5867 arraySpeciesGetterSlot_
= speciesGetterSlot
;
5868 canonicalSpeciesFunc_
= speciesFun
;
5869 arrayProtoShape_
= arrayProto
->shape();
5870 arrayProtoConstructorSlot_
= ctorProp
->slot();
5873 void js::ArraySpeciesLookup::reset() {
5874 AlwaysPoison(this, JS_RESET_VALUE_PATTERN
, sizeof(*this),
5875 MemCheckKind::MakeUndefined
);
5876 state_
= State::Uninitialized
;
5879 bool js::ArraySpeciesLookup::isArrayStateStillSane() {
5880 MOZ_ASSERT(state_
== State::Initialized
);
5882 // Ensure that Array.prototype still has the expected shape.
5883 if (arrayProto_
->shape() != arrayProtoShape_
) {
5887 // Ensure that Array.prototype.constructor contains the canonical Array
5888 // constructor function.
5889 if (arrayProto_
->getSlot(arrayProtoConstructorSlot_
) !=
5890 ObjectValue(*arrayConstructor_
)) {
5894 // Ensure that Array still has the expected shape.
5895 if (arrayConstructor_
->shape() != arrayConstructorShape_
) {
5899 // Ensure the species getter contains the canonical @@species function.
5900 JSObject
* getter
= arrayConstructor_
->getGetter(arraySpeciesGetterSlot_
);
5901 return getter
== canonicalSpeciesFunc_
;
5904 bool js::ArraySpeciesLookup::tryOptimizeArray(JSContext
* cx
,
5905 ArrayObject
* array
) {
5906 if (state_
== State::Uninitialized
) {
5907 // If the cache is not initialized, initialize it.
5909 } else if (state_
== State::Initialized
&& !isArrayStateStillSane()) {
5910 // Otherwise, if the array state is no longer sane, reinitialize.
5915 // If the cache is disabled or still uninitialized, don't bother trying to
5917 if (state_
!= State::Initialized
) {
5921 // By the time we get here, we should have a sane array state.
5922 MOZ_ASSERT(isArrayStateStillSane());
5924 // Ensure |array|'s prototype is the actual Array.prototype.
5925 if (array
->staticPrototype() != arrayProto_
) {
5929 // Ensure the array does not define an own "constructor" property which may
5930 // shadow `Array.prototype.constructor`.
5932 // Most arrays don't define any additional own properties beside their
5933 // "length" property. If "length" is the last property, it must be the only
5934 // property, because it's non-configurable.
5935 MOZ_ASSERT(array
->shape()->propMapLength() > 0);
5936 PropertyKey lengthKey
= NameToId(cx
->names().length
);
5937 if (MOZ_LIKELY(array
->getLastProperty().key() == lengthKey
)) {
5938 MOZ_ASSERT(array
->shape()->propMapLength() == 1, "Expected one property");
5942 // Fail if the array has an own "constructor" property.
5944 if (array
->shape()->lookup(cx
, NameToId(cx
->names().constructor
), &index
)) {
5951 JS_PUBLIC_API JSObject
* JS::NewArrayObject(JSContext
* cx
,
5952 const HandleValueArray
& contents
) {
5953 MOZ_ASSERT(!cx
->zone()->isAtomsZone());
5956 cx
->check(contents
);
5958 return NewDenseCopiedArray(cx
, contents
.length(), contents
.begin());
5961 JS_PUBLIC_API JSObject
* JS::NewArrayObject(JSContext
* cx
, size_t length
) {
5962 MOZ_ASSERT(!cx
->zone()->isAtomsZone());
5966 return NewDenseFullyAllocatedArray(cx
, length
);
5969 JS_PUBLIC_API
bool JS::IsArrayObject(JSContext
* cx
, Handle
<JSObject
*> obj
,
5971 return IsGivenTypeObject(cx
, obj
, ESClass::Array
, isArray
);
5974 JS_PUBLIC_API
bool JS::IsArrayObject(JSContext
* cx
, Handle
<Value
> value
,
5976 if (!value
.isObject()) {
5981 Rooted
<JSObject
*> obj(cx
, &value
.toObject());
5982 return IsArrayObject(cx
, obj
, isArray
);
5985 JS_PUBLIC_API
bool JS::GetArrayLength(JSContext
* cx
, Handle
<JSObject
*> obj
,
5986 uint32_t* lengthp
) {
5992 if (!GetLengthProperty(cx
, obj
, &len
)) {
5996 if (len
> UINT32_MAX
) {
5997 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
5998 JSMSG_BAD_ARRAY_LENGTH
);
6002 *lengthp
= uint32_t(len
);
6006 JS_PUBLIC_API
bool JS::SetArrayLength(JSContext
* cx
, Handle
<JSObject
*> obj
,
6012 return SetLengthProperty(cx
, obj
, length
);
6015 ArrayObject
* js::NewArrayWithNullProto(JSContext
* cx
) {
6016 Rooted
<SharedShape
*> shape(cx
, GetArrayShapeWithProto(cx
, nullptr));
6021 uint32_t length
= 0;
6022 return ::NewArrayWithShape
<0>(cx
, shape
, length
, GenericObject
);