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/. */
6
7 #include "builtin/Array-inl.h"
8
9 #include "mozilla/CheckedInt.h"
10 #include "mozilla/DebugOnly.h"
11 #include "mozilla/MathAlgorithms.h"
12 #include "mozilla/Maybe.h"
13 #include "mozilla/TextUtils.h"
14
15 #include <algorithm>
16 #include <iterator>
17
18 #include "jsapi.h"
19 #include "jsfriendapi.h"
20 #include "jsnum.h"
21 #include "jstypes.h"
22
23 #include "ds/Sort.h"
24 #include "gc/Allocator.h"
25 #include "jit/InlinableNatives.h"
26 #include "js/Class.h"
27 #include "js/Conversions.h"
28 #include "js/experimental/JitInfo.h" // JSJitGetterOp, JSJitInfo
29 #include "js/friend/ErrorMessages.h" // js::GetErrorMessage, JSMSG_*
30 #include "js/friend/StackLimits.h" // js::AutoCheckRecursionLimit
31 #include "js/PropertySpec.h"
32 #include "util/Poison.h"
33 #include "util/StringBuffer.h"
34 #include "util/Text.h"
35 #include "vm/ArgumentsObject.h"
36 #include "vm/Interpreter.h"
37 #include "vm/Iteration.h"
38 #include "vm/JSAtom.h"
39 #include "vm/JSContext.h"
40 #include "vm/JSFunction.h"
41 #include "vm/JSObject.h"
42 #include "vm/PlainObject.h" // js::PlainObject
43 #include "vm/SelfHosting.h"
44 #include "vm/Shape.h"
45 #include "vm/ToSource.h" // js::ValueToSource
46 #include "vm/TypedArrayObject.h"
47 #include "vm/WellKnownAtom.h" // js_*_str
48 #include "vm/WrapperObject.h"
49
50 #include "vm/ArgumentsObject-inl.h"
51 #include "vm/ArrayObject-inl.h"
52 #include "vm/Caches-inl.h"
53 #include "vm/GeckoProfiler-inl.h"
54 #include "vm/Interpreter-inl.h"
55 #include "vm/IsGivenTypeObject-inl.h"
56 #include "vm/JSAtom-inl.h"
57 #include "vm/NativeObject-inl.h"
58
59 using namespace js;
60
61 using mozilla::Abs;
62 using mozilla::CeilingLog2;
63 using mozilla::CheckedInt;
64 using mozilla::DebugOnly;
65 using mozilla::IsAsciiDigit;
66 using mozilla::Maybe;
67
68 using JS::AutoCheckCannotGC;
69 using JS::IsArrayAnswer;
70 using JS::ToUint32;
71
IsArray(JSContext * cx,HandleObject obj,IsArrayAnswer * answer)72 bool JS::IsArray(JSContext* cx, HandleObject obj, IsArrayAnswer* answer) {
73 if (obj->is<ArrayObject>()) {
74 *answer = IsArrayAnswer::Array;
75 return true;
76 }
77
78 if (obj->is<ProxyObject>()) {
79 return Proxy::isArray(cx, obj, answer);
80 }
81
82 *answer = IsArrayAnswer::NotArray;
83 return true;
84 }
85
IsArray(JSContext * cx,HandleObject obj,bool * isArray)86 bool JS::IsArray(JSContext* cx, HandleObject obj, bool* isArray) {
87 IsArrayAnswer answer;
88 if (!IsArray(cx, obj, &answer)) {
89 return false;
90 }
91
92 if (answer == IsArrayAnswer::RevokedProxy) {
93 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
94 JSMSG_PROXY_REVOKED);
95 return false;
96 }
97
98 *isArray = answer == IsArrayAnswer::Array;
99 return true;
100 }
101
IsArrayFromJit(JSContext * cx,HandleObject obj,bool * isArray)102 bool js::IsArrayFromJit(JSContext* cx, HandleObject obj, bool* isArray) {
103 return JS::IsArray(cx, obj, isArray);
104 }
105
106 // ES2017 7.1.15 ToLength.
ToLength(JSContext * cx,HandleValue v,uint64_t * out)107 bool js::ToLength(JSContext* cx, HandleValue v, uint64_t* out) {
108 if (v.isInt32()) {
109 int32_t i = v.toInt32();
110 *out = i < 0 ? 0 : i;
111 return true;
112 }
113
114 double d;
115 if (v.isDouble()) {
116 d = v.toDouble();
117 } else {
118 if (!ToNumber(cx, v, &d)) {
119 return false;
120 }
121 }
122
123 d = JS::ToInteger(d);
124 if (d <= 0.0) {
125 *out = 0;
126 } else {
127 *out = uint64_t(std::min(d, DOUBLE_INTEGRAL_PRECISION_LIMIT - 1));
128 }
129 return true;
130 }
131
GetLengthProperty(JSContext * cx,HandleObject obj,uint64_t * lengthp)132 bool js::GetLengthProperty(JSContext* cx, HandleObject obj, uint64_t* lengthp) {
133 if (obj->is<ArrayObject>()) {
134 *lengthp = obj->as<ArrayObject>().length();
135 return true;
136 }
137
138 if (obj->is<ArgumentsObject>()) {
139 ArgumentsObject& argsobj = obj->as<ArgumentsObject>();
140 if (!argsobj.hasOverriddenLength()) {
141 *lengthp = argsobj.initialLength();
142 return true;
143 }
144 }
145
146 RootedValue value(cx);
147 if (!GetProperty(cx, obj, obj, cx->names().length, &value)) {
148 return false;
149 }
150
151 return ToLength(cx, value, lengthp);
152 }
153
154 // Fast path for array functions where the object is expected to be an array.
GetLengthPropertyInlined(JSContext * cx,HandleObject obj,uint64_t * lengthp)155 static MOZ_ALWAYS_INLINE bool GetLengthPropertyInlined(JSContext* cx,
156 HandleObject obj,
157 uint64_t* lengthp) {
158 if (obj->is<ArrayObject>()) {
159 *lengthp = obj->as<ArrayObject>().length();
160 return true;
161 }
162
163 return GetLengthProperty(cx, obj, lengthp);
164 }
165
166 /*
167 * Determine if the id represents an array index.
168 *
169 * An id is an array index according to ECMA by (15.4):
170 *
171 * "Array objects give special treatment to a certain class of property names.
172 * A property name P (in the form of a string value) is an array index if and
173 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
174 * to 2^32-1."
175 *
176 * This means the largest allowed index is actually 2^32-2 (4294967294).
177 *
178 * In our implementation, it would be sufficient to check for id.isInt32()
179 * except that by using signed 31-bit integers we miss the top half of the
180 * valid range. This function checks the string representation itself; note
181 * that calling a standard conversion routine might allow strings such as
182 * "08" or "4.0" as array indices, which they are not.
183 *
184 */
StringIsArrayIndex(JSLinearString * str,uint32_t * indexp)185 JS_PUBLIC_API bool js::StringIsArrayIndex(JSLinearString* str,
186 uint32_t* indexp) {
187 if (!str->isIndex(indexp)) {
188 return false;
189 }
190 MOZ_ASSERT(*indexp <= MAX_ARRAY_INDEX);
191 return true;
192 }
193
StringIsArrayIndex(const char16_t * str,uint32_t length,uint32_t * indexp)194 JS_PUBLIC_API bool js::StringIsArrayIndex(const char16_t* str, uint32_t length,
195 uint32_t* indexp) {
196 if (length == 0 || length > UINT32_CHAR_BUFFER_LENGTH) {
197 return false;
198 }
199 if (!mozilla::IsAsciiDigit(str[0])) {
200 return false;
201 }
202 if (!CheckStringIsIndex(str, length, indexp)) {
203 return false;
204 }
205 MOZ_ASSERT(*indexp <= MAX_ARRAY_INDEX);
206 return true;
207 }
208
209 template <typename T>
210 static bool ToId(JSContext* cx, T index, MutableHandleId id);
211
212 template <>
ToId(JSContext * cx,uint32_t index,MutableHandleId id)213 bool ToId(JSContext* cx, uint32_t index, MutableHandleId id) {
214 return IndexToId(cx, index, id);
215 }
216
217 template <>
ToId(JSContext * cx,uint64_t index,MutableHandleId id)218 bool ToId(JSContext* cx, uint64_t index, MutableHandleId id) {
219 MOZ_ASSERT(index < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));
220
221 if (index == uint32_t(index)) {
222 return IndexToId(cx, uint32_t(index), id);
223 }
224
225 Value tmp = DoubleValue(index);
226 return PrimitiveValueToId<CanGC>(cx, HandleValue::fromMarkedLocation(&tmp),
227 id);
228 }
229
230 /*
231 * If the property at the given index exists, get its value into |vp| and set
232 * |*hole| to false. Otherwise set |*hole| to true and |vp| to Undefined.
233 */
234 template <typename T>
HasAndGetElement(JSContext * cx,HandleObject obj,HandleObject receiver,T index,bool * hole,MutableHandleValue vp)235 static bool HasAndGetElement(JSContext* cx, HandleObject obj,
236 HandleObject receiver, T index, bool* hole,
237 MutableHandleValue vp) {
238 if (obj->is<NativeObject>()) {
239 NativeObject* nobj = &obj->as<NativeObject>();
240 if (index < nobj->getDenseInitializedLength()) {
241 vp.set(nobj->getDenseElement(size_t(index)));
242 if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
243 *hole = false;
244 return true;
245 }
246 }
247 if (nobj->is<ArgumentsObject>() && index <= UINT32_MAX) {
248 if (nobj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
249 *hole = false;
250 return true;
251 }
252 }
253 }
254
255 RootedId id(cx);
256 if (!ToId(cx, index, &id)) {
257 return false;
258 }
259
260 bool found;
261 if (!HasProperty(cx, obj, id, &found)) {
262 return false;
263 }
264
265 if (found) {
266 if (!GetProperty(cx, obj, receiver, id, vp)) {
267 return false;
268 }
269 } else {
270 vp.setUndefined();
271 }
272 *hole = !found;
273 return true;
274 }
275
276 template <typename T>
HasAndGetElement(JSContext * cx,HandleObject obj,T index,bool * hole,MutableHandleValue vp)277 static inline bool HasAndGetElement(JSContext* cx, HandleObject obj, T index,
278 bool* hole, MutableHandleValue vp) {
279 return HasAndGetElement(cx, obj, obj, index, hole, vp);
280 }
281
append(JSContext * cx,HandleValue v)282 bool ElementAdder::append(JSContext* cx, HandleValue v) {
283 MOZ_ASSERT(index_ < length_);
284 if (resObj_) {
285 NativeObject* resObj = &resObj_->as<NativeObject>();
286 DenseElementResult result =
287 resObj->setOrExtendDenseElements(cx, index_, v.address(), 1);
288 if (result == DenseElementResult::Failure) {
289 return false;
290 }
291 if (result == DenseElementResult::Incomplete) {
292 if (!DefineDataElement(cx, resObj_, index_, v)) {
293 return false;
294 }
295 }
296 } else {
297 vp_[index_] = v;
298 }
299 index_++;
300 return true;
301 }
302
appendHole()303 void ElementAdder::appendHole() {
304 MOZ_ASSERT(getBehavior_ == ElementAdder::CheckHasElemPreserveHoles);
305 MOZ_ASSERT(index_ < length_);
306 if (!resObj_) {
307 vp_[index_].setMagic(JS_ELEMENTS_HOLE);
308 }
309 index_++;
310 }
311
GetElementsWithAdder(JSContext * cx,HandleObject obj,HandleObject receiver,uint32_t begin,uint32_t end,ElementAdder * adder)312 bool js::GetElementsWithAdder(JSContext* cx, HandleObject obj,
313 HandleObject receiver, uint32_t begin,
314 uint32_t end, ElementAdder* adder) {
315 MOZ_ASSERT(begin <= end);
316
317 RootedValue val(cx);
318 for (uint32_t i = begin; i < end; i++) {
319 if (adder->getBehavior() == ElementAdder::CheckHasElemPreserveHoles) {
320 bool hole;
321 if (!HasAndGetElement(cx, obj, receiver, i, &hole, &val)) {
322 return false;
323 }
324 if (hole) {
325 adder->appendHole();
326 continue;
327 }
328 } else {
329 MOZ_ASSERT(adder->getBehavior() == ElementAdder::GetElement);
330 if (!GetElement(cx, obj, receiver, i, &val)) {
331 return false;
332 }
333 }
334 if (!adder->append(cx, val)) {
335 return false;
336 }
337 }
338
339 return true;
340 }
341
IsPackedArrayOrNoExtraIndexedProperties(JSObject * obj,uint64_t length)342 static inline bool IsPackedArrayOrNoExtraIndexedProperties(JSObject* obj,
343 uint64_t length) {
344 return (IsPackedArray(obj) && obj->as<ArrayObject>().length() == length) ||
345 !ObjectMayHaveExtraIndexedProperties(obj);
346 }
347
GetDenseElements(NativeObject * aobj,uint32_t length,Value * vp)348 static bool GetDenseElements(NativeObject* aobj, uint32_t length, Value* vp) {
349 MOZ_ASSERT(IsPackedArrayOrNoExtraIndexedProperties(aobj, length));
350
351 if (length > aobj->getDenseInitializedLength()) {
352 return false;
353 }
354
355 for (size_t i = 0; i < length; i++) {
356 vp[i] = aobj->getDenseElement(i);
357
358 // No other indexed properties so hole => undefined.
359 if (vp[i].isMagic(JS_ELEMENTS_HOLE)) {
360 vp[i] = UndefinedValue();
361 }
362 }
363
364 return true;
365 }
366
GetElements(JSContext * cx,HandleObject aobj,uint32_t length,Value * vp)367 bool js::GetElements(JSContext* cx, HandleObject aobj, uint32_t length,
368 Value* vp) {
369 if (IsPackedArrayOrNoExtraIndexedProperties(aobj, length)) {
370 if (GetDenseElements(&aobj->as<NativeObject>(), length, vp)) {
371 return true;
372 }
373 }
374
375 if (aobj->is<ArgumentsObject>()) {
376 ArgumentsObject& argsobj = aobj->as<ArgumentsObject>();
377 if (!argsobj.hasOverriddenLength()) {
378 if (argsobj.maybeGetElements(0, length, vp)) {
379 return true;
380 }
381 }
382 }
383
384 if (aobj->is<TypedArrayObject>()) {
385 Handle<TypedArrayObject*> typedArray = aobj.as<TypedArrayObject>();
386 if (typedArray->length() == length) {
387 return TypedArrayObject::getElements(cx, typedArray, vp);
388 }
389 }
390
391 if (js::GetElementsOp op = aobj->getOpsGetElements()) {
392 ElementAdder adder(cx, vp, length, ElementAdder::GetElement);
393 return op(cx, aobj, 0, length, &adder);
394 }
395
396 for (uint32_t i = 0; i < length; i++) {
397 if (!GetElement(cx, aobj, aobj, i,
398 MutableHandleValue::fromMarkedLocation(&vp[i]))) {
399 return false;
400 }
401 }
402
403 return true;
404 }
405
GetArrayElement(JSContext * cx,HandleObject obj,uint64_t index,MutableHandleValue vp)406 static inline bool GetArrayElement(JSContext* cx, HandleObject obj,
407 uint64_t index, MutableHandleValue vp) {
408 if (obj->is<NativeObject>()) {
409 NativeObject* nobj = &obj->as<NativeObject>();
410 if (index < nobj->getDenseInitializedLength()) {
411 vp.set(nobj->getDenseElement(size_t(index)));
412 if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
413 return true;
414 }
415 }
416
417 if (nobj->is<ArgumentsObject>() && index <= UINT32_MAX) {
418 if (nobj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
419 return true;
420 }
421 }
422 }
423
424 RootedId id(cx);
425 if (!ToId(cx, index, &id)) {
426 return false;
427 }
428 return GetProperty(cx, obj, obj, id, vp);
429 }
430
DefineArrayElement(JSContext * cx,HandleObject obj,uint64_t index,HandleValue value)431 static inline bool DefineArrayElement(JSContext* cx, HandleObject obj,
432 uint64_t index, HandleValue value) {
433 RootedId id(cx);
434 if (!ToId(cx, index, &id)) {
435 return false;
436 }
437 return DefineDataProperty(cx, obj, id, value);
438 }
439
440 // Set the value of the property at the given index to v.
SetArrayElement(JSContext * cx,HandleObject obj,uint64_t index,HandleValue v)441 static inline bool SetArrayElement(JSContext* cx, HandleObject obj,
442 uint64_t index, HandleValue v) {
443 RootedId id(cx);
444 if (!ToId(cx, index, &id)) {
445 return false;
446 }
447
448 return SetProperty(cx, obj, id, v);
449 }
450
451 /*
452 * Attempt to delete the element |index| from |obj| as if by
453 * |obj.[[Delete]](index)|.
454 *
455 * If an error occurs while attempting to delete the element (that is, the call
456 * to [[Delete]] threw), return false.
457 *
458 * Otherwise call result.succeed() or result.fail() to indicate whether the
459 * deletion attempt succeeded (that is, whether the call to [[Delete]] returned
460 * true or false). (Deletes generally fail only when the property is
461 * non-configurable, but proxies may implement different semantics.)
462 */
DeleteArrayElement(JSContext * cx,HandleObject obj,uint64_t index,ObjectOpResult & result)463 static bool DeleteArrayElement(JSContext* cx, HandleObject obj, uint64_t index,
464 ObjectOpResult& result) {
465 if (obj->is<ArrayObject>() && !obj->as<NativeObject>().isIndexed() &&
466 !obj->as<NativeObject>().denseElementsAreSealed()) {
467 ArrayObject* aobj = &obj->as<ArrayObject>();
468 if (index <= UINT32_MAX) {
469 uint32_t idx = uint32_t(index);
470 if (idx < aobj->getDenseInitializedLength()) {
471 if (idx + 1 == aobj->getDenseInitializedLength()) {
472 aobj->setDenseInitializedLengthMaybeNonExtensible(cx, idx);
473 } else {
474 aobj->setDenseElementHole(idx);
475 }
476 if (!SuppressDeletedElement(cx, obj, idx)) {
477 return false;
478 }
479 }
480 }
481
482 return result.succeed();
483 }
484
485 RootedId id(cx);
486 if (!ToId(cx, index, &id)) {
487 return false;
488 }
489 return DeleteProperty(cx, obj, id, result);
490 }
491
492 /* ES6 draft rev 32 (2 Febr 2015) 7.3.7 */
DeletePropertyOrThrow(JSContext * cx,HandleObject obj,uint64_t index)493 static bool DeletePropertyOrThrow(JSContext* cx, HandleObject obj,
494 uint64_t index) {
495 ObjectOpResult success;
496 if (!DeleteArrayElement(cx, obj, index, success)) {
497 return false;
498 }
499 if (!success) {
500 RootedId id(cx);
501 if (!ToId(cx, index, &id)) {
502 return false;
503 }
504 return success.reportError(cx, obj, id);
505 }
506 return true;
507 }
508
DeletePropertiesOrThrow(JSContext * cx,HandleObject obj,uint64_t len,uint64_t finalLength)509 static bool DeletePropertiesOrThrow(JSContext* cx, HandleObject obj,
510 uint64_t len, uint64_t finalLength) {
511 if (obj->is<ArrayObject>() && !obj->as<NativeObject>().isIndexed() &&
512 !obj->as<NativeObject>().denseElementsAreSealed()) {
513 if (len <= UINT32_MAX) {
514 // Skip forward to the initialized elements of this array.
515 len = std::min(uint32_t(len),
516 obj->as<ArrayObject>().getDenseInitializedLength());
517 }
518 }
519
520 for (uint64_t k = len; k > finalLength; k--) {
521 if (!CheckForInterrupt(cx)) {
522 return false;
523 }
524
525 if (!DeletePropertyOrThrow(cx, obj, k - 1)) {
526 return false;
527 }
528 }
529 return true;
530 }
531
SetArrayLengthProperty(JSContext * cx,HandleArrayObject obj,HandleValue value)532 static bool SetArrayLengthProperty(JSContext* cx, HandleArrayObject obj,
533 HandleValue value) {
534 RootedId id(cx, NameToId(cx->names().length));
535 ObjectOpResult result;
536 if (obj->lengthIsWritable()) {
537 Rooted<PropertyDescriptor> desc(
538 cx, PropertyDescriptor::Data(value, JS::PropertyAttribute::Writable));
539 if (!ArraySetLength(cx, obj, id, desc, result)) {
540 return false;
541 }
542 } else {
543 MOZ_ALWAYS_TRUE(result.fail(JSMSG_READ_ONLY));
544 }
545 return result.checkStrict(cx, obj, id);
546 }
547
SetLengthProperty(JSContext * cx,HandleObject obj,uint64_t length)548 static bool SetLengthProperty(JSContext* cx, HandleObject obj,
549 uint64_t length) {
550 MOZ_ASSERT(length < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));
551
552 RootedValue v(cx, NumberValue(length));
553 if (obj->is<ArrayObject>()) {
554 return SetArrayLengthProperty(cx, obj.as<ArrayObject>(), v);
555 }
556 return SetProperty(cx, obj, cx->names().length, v);
557 }
558
SetLengthProperty(JSContext * cx,HandleObject obj,uint32_t length)559 bool js::SetLengthProperty(JSContext* cx, HandleObject obj, uint32_t length) {
560 RootedValue v(cx, NumberValue(length));
561 if (obj->is<ArrayObject>()) {
562 return SetArrayLengthProperty(cx, obj.as<ArrayObject>(), v);
563 }
564 return SetProperty(cx, obj, cx->names().length, v);
565 }
566
ArrayLengthGetter(JSContext * cx,HandleObject obj,HandleId id,MutableHandleValue vp)567 bool js::ArrayLengthGetter(JSContext* cx, HandleObject obj, HandleId id,
568 MutableHandleValue vp) {
569 MOZ_ASSERT(id == NameToId(cx->names().length));
570
571 vp.setNumber(obj->as<ArrayObject>().length());
572 return true;
573 }
574
ArrayLengthSetter(JSContext * cx,HandleObject obj,HandleId id,HandleValue v,ObjectOpResult & result)575 bool js::ArrayLengthSetter(JSContext* cx, HandleObject obj, HandleId id,
576 HandleValue v, ObjectOpResult& result) {
577 MOZ_ASSERT(id == NameToId(cx->names().length));
578
579 HandleArrayObject arr = obj.as<ArrayObject>();
580 MOZ_ASSERT(arr->lengthIsWritable(),
581 "setter shouldn't be called if property is non-writable");
582
583 Rooted<PropertyDescriptor> desc(
584 cx, PropertyDescriptor::Data(v, JS::PropertyAttribute::Writable));
585 return ArraySetLength(cx, arr, id, desc, result);
586 }
587
588 struct ReverseIndexComparator {
operator ()ReverseIndexComparator589 bool operator()(const uint32_t& a, const uint32_t& b, bool* lessOrEqualp) {
590 MOZ_ASSERT(a != b, "how'd we get duplicate indexes?");
591 *lessOrEqualp = b <= a;
592 return true;
593 }
594 };
595
596 /* ES6 draft rev 34 (2015 Feb 20) 9.4.2.4 ArraySetLength */
ArraySetLength(JSContext * cx,Handle<ArrayObject * > arr,HandleId id,Handle<PropertyDescriptor> desc,ObjectOpResult & result)597 bool js::ArraySetLength(JSContext* cx, Handle<ArrayObject*> arr, HandleId id,
598 Handle<PropertyDescriptor> desc,
599 ObjectOpResult& result) {
600 MOZ_ASSERT(id == NameToId(cx->names().length));
601 MOZ_ASSERT(desc.isDataDescriptor() || desc.isGenericDescriptor());
602
603 // Step 1.
604 uint32_t newLen;
605 if (!desc.hasValue()) {
606 // The spec has us calling OrdinaryDefineOwnProperty if
607 // Desc.[[Value]] is absent, but our implementation is so different that
608 // this is impossible. Instead, set newLen to the current length and
609 // proceed to step 9.
610 newLen = arr->length();
611 } else {
612 // Step 2 is irrelevant in our implementation.
613
614 // Step 3.
615 if (!ToUint32(cx, desc.value(), &newLen)) {
616 return false;
617 }
618
619 // Step 4.
620 double d;
621 if (!ToNumber(cx, desc.value(), &d)) {
622 return false;
623 }
624
625 // Step 5.
626 if (d != newLen) {
627 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
628 JSMSG_BAD_ARRAY_LENGTH);
629 return false;
630 }
631
632 // Steps 6-8 are irrelevant in our implementation.
633 }
634
635 // Steps 9-11.
636 bool lengthIsWritable = arr->lengthIsWritable();
637 #ifdef DEBUG
638 {
639 mozilla::Maybe<PropertyInfo> lengthProp = arr->lookupPure(id);
640 MOZ_ASSERT(lengthProp.isSome());
641 MOZ_ASSERT(lengthProp->writable() == lengthIsWritable);
642 }
643 #endif
644 uint32_t oldLen = arr->length();
645
646 // Part of steps 1.a, 12.a, and 16: Fail if we're being asked to change
647 // enumerability or configurability, or otherwise break the object
648 // invariants. (ES6 checks these by calling OrdinaryDefineOwnProperty, but
649 // in SM, the array length property is hardly ordinary.)
650 if ((desc.hasConfigurable() && desc.configurable()) ||
651 (desc.hasEnumerable() && desc.enumerable()) ||
652 (!lengthIsWritable && desc.hasWritable() && desc.writable())) {
653 return result.fail(JSMSG_CANT_REDEFINE_PROP);
654 }
655
656 // Steps 12-13 for arrays with non-writable length.
657 if (!lengthIsWritable) {
658 if (newLen == oldLen) {
659 return result.succeed();
660 }
661
662 return result.fail(JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
663 }
664
665 // Step 19.
666 bool succeeded = true;
667 do {
668 // The initialized length and capacity of an array only need updating
669 // when non-hole elements are added or removed, which doesn't happen
670 // when array length stays the same or increases.
671 if (newLen >= oldLen) {
672 break;
673 }
674
675 // Attempt to propagate dense-element optimization tricks, if possible,
676 // and avoid the generic (and accordingly slow) deletion code below.
677 // We can only do this if there are only densely-indexed elements.
678 // Once there's a sparse indexed element, there's no good way to know,
679 // save by enumerating all the properties to find it. But we *have* to
680 // know in case that sparse indexed element is non-configurable, as
681 // that element must prevent any deletions below it. Bug 586842 should
682 // fix this inefficiency by moving indexed storage to be entirely
683 // separate from non-indexed storage.
684 // A second reason for this optimization to be invalid is an active
685 // for..in iteration over the array. Keys deleted before being reached
686 // during the iteration must not be visited, and suppressing them here
687 // would be too costly.
688 // This optimization is also invalid when there are sealed
689 // (non-configurable) elements.
690 if (!arr->isIndexed() && !arr->denseElementsMaybeInIteration() &&
691 !arr->denseElementsAreSealed()) {
692 uint32_t oldCapacity = arr->getDenseCapacity();
693 uint32_t oldInitializedLength = arr->getDenseInitializedLength();
694 MOZ_ASSERT(oldCapacity >= oldInitializedLength);
695 if (oldInitializedLength > newLen) {
696 arr->setDenseInitializedLengthMaybeNonExtensible(cx, newLen);
697 }
698 if (oldCapacity > newLen) {
699 if (arr->isExtensible()) {
700 arr->shrinkElements(cx, newLen);
701 } else {
702 MOZ_ASSERT(arr->getDenseInitializedLength() ==
703 arr->getDenseCapacity());
704 }
705 }
706
707 // We've done the work of deleting any dense elements needing
708 // deletion, and there are no sparse elements. Thus we can skip
709 // straight to defining the length.
710 break;
711 }
712
713 // Step 15.
714 //
715 // Attempt to delete all elements above the new length, from greatest
716 // to least. If any of these deletions fails, we're supposed to define
717 // the length to one greater than the index that couldn't be deleted,
718 // *with the property attributes specified*. This might convert the
719 // length to be not the value specified, yet non-writable. (You may be
720 // forgiven for thinking these are interesting semantics.) Example:
721 //
722 // var arr =
723 // Object.defineProperty([0, 1, 2, 3], 1, { writable: false });
724 // Object.defineProperty(arr, "length",
725 // { value: 0, writable: false });
726 //
727 // will convert |arr| to an array of non-writable length two, then
728 // throw a TypeError.
729 //
730 // We implement this behavior, in the relevant lops below, by setting
731 // |succeeded| to false. Then we exit the loop, define the length
732 // appropriately, and only then throw a TypeError, if necessary.
733 uint32_t gap = oldLen - newLen;
734 const uint32_t RemoveElementsFastLimit = 1 << 24;
735 if (gap < RemoveElementsFastLimit) {
736 // If we're removing a relatively small number of elements, just do
737 // it exactly by the spec.
738 while (newLen < oldLen) {
739 // Step 15a.
740 oldLen--;
741
742 // Steps 15b-d.
743 ObjectOpResult deleteSucceeded;
744 if (!DeleteElement(cx, arr, oldLen, deleteSucceeded)) {
745 return false;
746 }
747 if (!deleteSucceeded) {
748 newLen = oldLen + 1;
749 succeeded = false;
750 break;
751 }
752 }
753 } else {
754 // If we're removing a large number of elements from an array
755 // that's probably sparse, try a different tack. Get all the own
756 // property names, sift out the indexes in the deletion range into
757 // a vector, sort the vector greatest to least, then delete the
758 // indexes greatest to least using that vector. See bug 322135.
759 //
760 // This heuristic's kind of a huge guess -- "large number of
761 // elements" and "probably sparse" are completely unprincipled
762 // predictions. In the long run, bug 586842 will support the right
763 // fix: store sparse elements in a sorted data structure that
764 // permits fast in-reverse-order traversal and concurrent removals.
765
766 Vector<uint32_t> indexes(cx);
767 {
768 RootedIdVector props(cx);
769 if (!GetPropertyKeys(cx, arr, JSITER_OWNONLY | JSITER_HIDDEN, &props)) {
770 return false;
771 }
772
773 for (size_t i = 0; i < props.length(); i++) {
774 if (!CheckForInterrupt(cx)) {
775 return false;
776 }
777
778 uint32_t index;
779 if (!IdIsIndex(props[i], &index)) {
780 continue;
781 }
782
783 if (index >= newLen && index < oldLen) {
784 if (!indexes.append(index)) {
785 return false;
786 }
787 }
788 }
789 }
790
791 uint32_t count = indexes.length();
792 {
793 // We should use radix sort to be O(n), but this is uncommon
794 // enough that we'll punt til someone complains.
795 Vector<uint32_t> scratch(cx);
796 if (!scratch.resize(count)) {
797 return false;
798 }
799 MOZ_ALWAYS_TRUE(MergeSort(indexes.begin(), count, scratch.begin(),
800 ReverseIndexComparator()));
801 }
802
803 uint32_t index = UINT32_MAX;
804 for (uint32_t i = 0; i < count; i++) {
805 MOZ_ASSERT(indexes[i] < index, "indexes should never repeat");
806 index = indexes[i];
807
808 // Steps 15b-d.
809 ObjectOpResult deleteSucceeded;
810 if (!DeleteElement(cx, arr, index, deleteSucceeded)) {
811 return false;
812 }
813 if (!deleteSucceeded) {
814 newLen = index + 1;
815 succeeded = false;
816 break;
817 }
818 }
819 }
820 } while (false);
821
822 // Update array length. Technically we should have been doing this
823 // throughout the loop, in step 19.d.iii.
824 arr->setLength(newLen);
825
826 // Step 20.
827 if (desc.hasWritable() && !desc.writable()) {
828 Maybe<PropertyInfo> lengthProp = arr->lookup(cx, id);
829 MOZ_ASSERT(lengthProp.isSome());
830 MOZ_ASSERT(lengthProp->isCustomDataProperty());
831 PropertyFlags flags = lengthProp->flags();
832 flags.clearFlag(PropertyFlag::Writable);
833 if (!NativeObject::changeCustomDataPropAttributes(cx, arr, id, flags)) {
834 return false;
835 }
836 }
837
838 // All operations past here until the |!succeeded| code must be infallible,
839 // so that all element fields remain properly synchronized.
840
841 // Trim the initialized length, if needed, to preserve the <= length
842 // invariant. (Capacity was already reduced during element deletion, if
843 // necessary.)
844 ObjectElements* header = arr->getElementsHeader();
845 header->initializedLength = std::min(header->initializedLength, newLen);
846
847 if (!arr->isExtensible()) {
848 arr->shrinkCapacityToInitializedLength(cx);
849 }
850
851 if (desc.hasWritable() && !desc.writable()) {
852 arr->setNonWritableLength(cx);
853 }
854
855 if (!succeeded) {
856 return result.fail(JSMSG_CANT_TRUNCATE_ARRAY);
857 }
858
859 return result.succeed();
860 }
861
array_addProperty(JSContext * cx,HandleObject obj,HandleId id,HandleValue v)862 static bool array_addProperty(JSContext* cx, HandleObject obj, HandleId id,
863 HandleValue v) {
864 ArrayObject* arr = &obj->as<ArrayObject>();
865
866 uint32_t index;
867 if (!IdIsIndex(id, &index)) {
868 return true;
869 }
870
871 uint32_t length = arr->length();
872 if (index >= length) {
873 MOZ_ASSERT(arr->lengthIsWritable(),
874 "how'd this element get added if length is non-writable?");
875 arr->setLength(index + 1);
876 }
877 return true;
878 }
879
ObjectMayHaveExtraIndexedOwnProperties(JSObject * obj)880 static inline bool ObjectMayHaveExtraIndexedOwnProperties(JSObject* obj) {
881 if (!obj->is<NativeObject>()) {
882 return true;
883 }
884
885 if (obj->as<NativeObject>().isIndexed()) {
886 return true;
887 }
888
889 if (obj->is<TypedArrayObject>()) {
890 return true;
891 }
892
893 return ClassMayResolveId(*obj->runtimeFromAnyThread()->commonNames,
894 obj->getClass(), INT_TO_JSID(0), obj);
895 }
896
897 /*
898 * Whether obj may have indexed properties anywhere besides its dense
899 * elements. This includes other indexed properties in its shape hierarchy, and
900 * indexed properties or elements along its prototype chain.
901 */
ObjectMayHaveExtraIndexedProperties(JSObject * obj)902 bool js::ObjectMayHaveExtraIndexedProperties(JSObject* obj) {
903 MOZ_ASSERT_IF(obj->hasDynamicPrototype(), !obj->is<NativeObject>());
904
905 if (ObjectMayHaveExtraIndexedOwnProperties(obj)) {
906 return true;
907 }
908
909 do {
910 MOZ_ASSERT(obj->hasStaticPrototype(),
911 "dynamic-prototype objects must be non-native, ergo must "
912 "have failed ObjectMayHaveExtraIndexedOwnProperties");
913
914 obj = obj->staticPrototype();
915 if (!obj) {
916 return false; // no extra indexed properties found
917 }
918
919 if (ObjectMayHaveExtraIndexedOwnProperties(obj)) {
920 return true;
921 }
922 if (obj->as<NativeObject>().getDenseInitializedLength() != 0) {
923 return true;
924 }
925 } while (true);
926 }
927
AddLengthProperty(JSContext * cx,HandleArrayObject obj)928 static bool AddLengthProperty(JSContext* cx, HandleArrayObject obj) {
929 // Add the 'length' property for a newly created array.
930
931 MOZ_ASSERT(obj->empty());
932
933 RootedId lengthId(cx, NameToId(cx->names().length));
934 constexpr PropertyFlags flags = {PropertyFlag::CustomDataProperty,
935 PropertyFlag::Writable};
936 return NativeObject::addCustomDataProperty(cx, obj, lengthId, flags);
937 }
938
IsArrayConstructor(const JSObject * obj)939 static bool IsArrayConstructor(const JSObject* obj) {
940 // Note: this also returns true for cross-realm Array constructors in the
941 // same compartment.
942 return IsNativeFunction(obj, ArrayConstructor);
943 }
944
IsArrayConstructor(const Value & v)945 static bool IsArrayConstructor(const Value& v) {
946 return v.isObject() && IsArrayConstructor(&v.toObject());
947 }
948
IsCrossRealmArrayConstructor(JSContext * cx,JSObject * obj,bool * result)949 bool js::IsCrossRealmArrayConstructor(JSContext* cx, JSObject* obj,
950 bool* result) {
951 if (obj->is<WrapperObject>()) {
952 obj = CheckedUnwrapDynamic(obj, cx);
953 if (!obj) {
954 ReportAccessDenied(cx);
955 return false;
956 }
957 }
958
959 *result =
960 IsArrayConstructor(obj) && obj->as<JSFunction>().realm() != cx->realm();
961 return true;
962 }
963
IsArraySpecies(JSContext * cx,HandleObject origArray)964 static MOZ_ALWAYS_INLINE bool IsArraySpecies(JSContext* cx,
965 HandleObject origArray) {
966 if (MOZ_UNLIKELY(origArray->is<ProxyObject>())) {
967 if (origArray->getClass()->isDOMClass()) {
968 #ifdef DEBUG
969 // We assume DOM proxies never return true for IsArray.
970 IsArrayAnswer answer;
971 MOZ_ASSERT(Proxy::isArray(cx, origArray, &answer));
972 MOZ_ASSERT(answer == IsArrayAnswer::NotArray);
973 #endif
974 return true;
975 }
976 return false;
977 }
978
979 // 9.4.2.3 Step 4. Non-array objects always use the default constructor.
980 if (!origArray->is<ArrayObject>()) {
981 return true;
982 }
983
984 if (cx->realm()->arraySpeciesLookup.tryOptimizeArray(
985 cx, &origArray->as<ArrayObject>())) {
986 return true;
987 }
988
989 Value ctor;
990 if (!GetPropertyPure(cx, origArray, NameToId(cx->names().constructor),
991 &ctor)) {
992 return false;
993 }
994
995 if (!IsArrayConstructor(ctor)) {
996 return ctor.isUndefined();
997 }
998
999 // 9.4.2.3 Step 6.c. Use the current realm's constructor if |ctor| is a
1000 // cross-realm Array constructor.
1001 if (cx->realm() != ctor.toObject().as<JSFunction>().realm()) {
1002 return true;
1003 }
1004
1005 jsid speciesId = SYMBOL_TO_JSID(cx->wellKnownSymbols().species);
1006 JSFunction* getter;
1007 if (!GetGetterPure(cx, &ctor.toObject(), speciesId, &getter)) {
1008 return false;
1009 }
1010
1011 if (!getter) {
1012 return false;
1013 }
1014
1015 return IsSelfHostedFunctionWithName(getter, cx->names().ArraySpecies);
1016 }
1017
ArraySpeciesCreate(JSContext * cx,HandleObject origArray,uint64_t length,MutableHandleObject arr)1018 static bool ArraySpeciesCreate(JSContext* cx, HandleObject origArray,
1019 uint64_t length, MutableHandleObject arr) {
1020 MOZ_ASSERT(length < DOUBLE_INTEGRAL_PRECISION_LIMIT);
1021
1022 FixedInvokeArgs<2> args(cx);
1023
1024 args[0].setObject(*origArray);
1025 args[1].set(NumberValue(length));
1026
1027 RootedValue rval(cx);
1028 if (!CallSelfHostedFunction(cx, cx->names().ArraySpeciesCreate,
1029 UndefinedHandleValue, args, &rval)) {
1030 return false;
1031 }
1032
1033 MOZ_ASSERT(rval.isObject());
1034 arr.set(&rval.toObject());
1035 return true;
1036 }
1037
ArrayToSource(JSContext * cx,HandleObject obj)1038 JSString* js::ArrayToSource(JSContext* cx, HandleObject obj) {
1039 AutoCycleDetector detector(cx, obj);
1040 if (!detector.init()) {
1041 return nullptr;
1042 }
1043
1044 JSStringBuilder sb(cx);
1045
1046 if (detector.foundCycle()) {
1047 if (!sb.append("[]")) {
1048 return nullptr;
1049 }
1050 return sb.finishString();
1051 }
1052
1053 if (!sb.append('[')) {
1054 return nullptr;
1055 }
1056
1057 uint64_t length;
1058 if (!GetLengthPropertyInlined(cx, obj, &length)) {
1059 return nullptr;
1060 }
1061
1062 RootedValue elt(cx);
1063 for (uint64_t index = 0; index < length; index++) {
1064 bool hole;
1065 if (!CheckForInterrupt(cx) ||
1066 !HasAndGetElement(cx, obj, index, &hole, &elt)) {
1067 return nullptr;
1068 }
1069
1070 /* Get element's character string. */
1071 JSString* str;
1072 if (hole) {
1073 str = cx->runtime()->emptyString;
1074 } else {
1075 str = ValueToSource(cx, elt);
1076 if (!str) {
1077 return nullptr;
1078 }
1079 }
1080
1081 /* Append element to buffer. */
1082 if (!sb.append(str)) {
1083 return nullptr;
1084 }
1085 if (index + 1 != length) {
1086 if (!sb.append(", ")) {
1087 return nullptr;
1088 }
1089 } else if (hole) {
1090 if (!sb.append(',')) {
1091 return nullptr;
1092 }
1093 }
1094 }
1095
1096 /* Finalize the buffer. */
1097 if (!sb.append(']')) {
1098 return nullptr;
1099 }
1100
1101 return sb.finishString();
1102 }
1103
array_toSource(JSContext * cx,unsigned argc,Value * vp)1104 static bool array_toSource(JSContext* cx, unsigned argc, Value* vp) {
1105 AutoCheckRecursionLimit recursion(cx);
1106 if (!recursion.check(cx)) {
1107 return false;
1108 }
1109
1110 CallArgs args = CallArgsFromVp(argc, vp);
1111
1112 if (!args.thisv().isObject()) {
1113 ReportIncompatible(cx, args);
1114 return false;
1115 }
1116
1117 Rooted<JSObject*> obj(cx, &args.thisv().toObject());
1118
1119 JSString* str = ArrayToSource(cx, obj);
1120 if (!str) {
1121 return false;
1122 }
1123
1124 args.rval().setString(str);
1125 return true;
1126 }
1127
1128 struct EmptySeparatorOp {
operator ()EmptySeparatorOp1129 bool operator()(JSContext*, StringBuffer& sb) { return true; }
1130 };
1131
1132 template <typename CharT>
1133 struct CharSeparatorOp {
1134 const CharT sep;
CharSeparatorOpCharSeparatorOp1135 explicit CharSeparatorOp(CharT sep) : sep(sep) {}
operator ()CharSeparatorOp1136 bool operator()(JSContext*, StringBuffer& sb) { return sb.append(sep); }
1137 };
1138
1139 struct StringSeparatorOp {
1140 HandleLinearString sep;
1141
StringSeparatorOpStringSeparatorOp1142 explicit StringSeparatorOp(HandleLinearString sep) : sep(sep) {}
1143
operator ()StringSeparatorOp1144 bool operator()(JSContext* cx, StringBuffer& sb) { return sb.append(sep); }
1145 };
1146
1147 template <typename SeparatorOp>
ArrayJoinDenseKernel(JSContext * cx,SeparatorOp sepOp,HandleNativeObject obj,uint64_t length,StringBuffer & sb,uint32_t * numProcessed)1148 static bool ArrayJoinDenseKernel(JSContext* cx, SeparatorOp sepOp,
1149 HandleNativeObject obj, uint64_t length,
1150 StringBuffer& sb, uint32_t* numProcessed) {
1151 // This loop handles all elements up to initializedLength. If
1152 // length > initLength we rely on the second loop to add the
1153 // other elements.
1154 MOZ_ASSERT(*numProcessed == 0);
1155 uint64_t initLength =
1156 std::min<uint64_t>(obj->getDenseInitializedLength(), length);
1157 MOZ_ASSERT(initLength <= UINT32_MAX,
1158 "initialized length shouldn't exceed UINT32_MAX");
1159 uint32_t initLengthClamped = uint32_t(initLength);
1160 while (*numProcessed < initLengthClamped) {
1161 if (!CheckForInterrupt(cx)) {
1162 return false;
1163 }
1164
1165 // Step 7.b.
1166 Value elem = obj->getDenseElement(*numProcessed);
1167
1168 // Steps 7.c-d.
1169 if (elem.isString()) {
1170 if (!sb.append(elem.toString())) {
1171 return false;
1172 }
1173 } else if (elem.isNumber()) {
1174 if (!NumberValueToStringBuffer(cx, elem, sb)) {
1175 return false;
1176 }
1177 } else if (elem.isBoolean()) {
1178 if (!BooleanToStringBuffer(elem.toBoolean(), sb)) {
1179 return false;
1180 }
1181 } else if (elem.isObject() || elem.isSymbol()) {
1182 /*
1183 * Object stringifying could modify the initialized length or make
1184 * the array sparse. Delegate it to a separate loop to keep this
1185 * one tight.
1186 *
1187 * Symbol stringifying is a TypeError, so into the slow path
1188 * with those as well.
1189 */
1190 break;
1191 } else if (elem.isBigInt()) {
1192 // ToString(bigint) doesn't access bigint.toString or
1193 // anything like that, so it can't mutate the array we're
1194 // walking through, so it *could* be handled here. We don't
1195 // do so yet for reasons of initial-implementation economy.
1196 break;
1197 } else {
1198 MOZ_ASSERT(elem.isMagic(JS_ELEMENTS_HOLE) || elem.isNullOrUndefined());
1199 }
1200
1201 // Steps 7.a, 7.e.
1202 if (++(*numProcessed) != length && !sepOp(cx, sb)) {
1203 return false;
1204 }
1205 }
1206
1207 return true;
1208 }
1209
1210 template <typename SeparatorOp>
ArrayJoinKernel(JSContext * cx,SeparatorOp sepOp,HandleObject obj,uint64_t length,StringBuffer & sb)1211 static bool ArrayJoinKernel(JSContext* cx, SeparatorOp sepOp, HandleObject obj,
1212 uint64_t length, StringBuffer& sb) {
1213 // Step 6.
1214 uint32_t numProcessed = 0;
1215
1216 if (IsPackedArrayOrNoExtraIndexedProperties(obj, length)) {
1217 if (!ArrayJoinDenseKernel<SeparatorOp>(cx, sepOp, obj.as<NativeObject>(),
1218 length, sb, &numProcessed)) {
1219 return false;
1220 }
1221 }
1222
1223 // Step 7.
1224 if (numProcessed != length) {
1225 RootedValue v(cx);
1226 for (uint64_t i = numProcessed; i < length;) {
1227 if (!CheckForInterrupt(cx)) {
1228 return false;
1229 }
1230
1231 // Step 7.b.
1232 if (!GetArrayElement(cx, obj, i, &v)) {
1233 return false;
1234 }
1235
1236 // Steps 7.c-d.
1237 if (!v.isNullOrUndefined()) {
1238 if (!ValueToStringBuffer(cx, v, sb)) {
1239 return false;
1240 }
1241 }
1242
1243 // Steps 7.a, 7.e.
1244 if (++i != length && !sepOp(cx, sb)) {
1245 return false;
1246 }
1247 }
1248 }
1249
1250 return true;
1251 }
1252
1253 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
1254 // 22.1.3.13 Array.prototype.join ( separator )
array_join(JSContext * cx,unsigned argc,Value * vp)1255 bool js::array_join(JSContext* cx, unsigned argc, Value* vp) {
1256 AutoCheckRecursionLimit recursion(cx);
1257 if (!recursion.check(cx)) {
1258 return false;
1259 }
1260
1261 AutoGeckoProfilerEntry pseudoFrame(
1262 cx, "Array.prototype.join", JS::ProfilingCategoryPair::JS,
1263 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
1264 CallArgs args = CallArgsFromVp(argc, vp);
1265
1266 // Step 1.
1267 RootedObject obj(cx, ToObject(cx, args.thisv()));
1268 if (!obj) {
1269 return false;
1270 }
1271
1272 AutoCycleDetector detector(cx, obj);
1273 if (!detector.init()) {
1274 return false;
1275 }
1276
1277 if (detector.foundCycle()) {
1278 args.rval().setString(cx->names().empty);
1279 return true;
1280 }
1281
1282 // Step 2.
1283 uint64_t length;
1284 if (!GetLengthPropertyInlined(cx, obj, &length)) {
1285 return false;
1286 }
1287
1288 // Steps 3-4.
1289 RootedLinearString sepstr(cx);
1290 if (args.hasDefined(0)) {
1291 JSString* s = ToString<CanGC>(cx, args[0]);
1292 if (!s) {
1293 return false;
1294 }
1295 sepstr = s->ensureLinear(cx);
1296 if (!sepstr) {
1297 return false;
1298 }
1299 } else {
1300 sepstr = cx->names().comma;
1301 }
1302
1303 // Steps 5-8 (When the length is zero, directly return the empty string).
1304 if (length == 0) {
1305 args.rval().setString(cx->emptyString());
1306 return true;
1307 }
1308
1309 // An optimized version of a special case of steps 5-8: when length==1 and
1310 // the 0th element is a string, ToString() of that element is a no-op and
1311 // so it can be immediately returned as the result.
1312 if (length == 1 && obj->is<NativeObject>()) {
1313 NativeObject* nobj = &obj->as<NativeObject>();
1314 if (nobj->getDenseInitializedLength() == 1) {
1315 Value elem0 = nobj->getDenseElement(0);
1316 if (elem0.isString()) {
1317 args.rval().set(elem0);
1318 return true;
1319 }
1320 }
1321 }
1322
1323 // Step 5.
1324 JSStringBuilder sb(cx);
1325 if (sepstr->hasTwoByteChars() && !sb.ensureTwoByteChars()) {
1326 return false;
1327 }
1328
1329 // The separator will be added |length - 1| times, reserve space for that
1330 // so that we don't have to unnecessarily grow the buffer.
1331 size_t seplen = sepstr->length();
1332 if (seplen > 0) {
1333 if (length > UINT32_MAX) {
1334 ReportAllocationOverflow(cx);
1335 return false;
1336 }
1337 CheckedInt<uint32_t> res =
1338 CheckedInt<uint32_t>(seplen) * (uint32_t(length) - 1);
1339 if (!res.isValid()) {
1340 ReportAllocationOverflow(cx);
1341 return false;
1342 }
1343
1344 if (!sb.reserve(res.value())) {
1345 return false;
1346 }
1347 }
1348
1349 // Various optimized versions of steps 6-7.
1350 if (seplen == 0) {
1351 EmptySeparatorOp op;
1352 if (!ArrayJoinKernel(cx, op, obj, length, sb)) {
1353 return false;
1354 }
1355 } else if (seplen == 1) {
1356 char16_t c = sepstr->latin1OrTwoByteChar(0);
1357 if (c <= JSString::MAX_LATIN1_CHAR) {
1358 CharSeparatorOp<Latin1Char> op(c);
1359 if (!ArrayJoinKernel(cx, op, obj, length, sb)) {
1360 return false;
1361 }
1362 } else {
1363 CharSeparatorOp<char16_t> op(c);
1364 if (!ArrayJoinKernel(cx, op, obj, length, sb)) {
1365 return false;
1366 }
1367 }
1368 } else {
1369 StringSeparatorOp op(sepstr);
1370 if (!ArrayJoinKernel(cx, op, obj, length, sb)) {
1371 return false;
1372 }
1373 }
1374
1375 // Step 8.
1376 JSString* str = sb.finishString();
1377 if (!str) {
1378 return false;
1379 }
1380
1381 args.rval().setString(str);
1382 return true;
1383 }
1384
1385 // ES2017 draft rev f8a9be8ea4bd97237d176907a1e3080dce20c68f
1386 // 22.1.3.27 Array.prototype.toLocaleString ([ reserved1 [ , reserved2 ] ])
1387 // ES2017 Intl draft rev 78bbe7d1095f5ff3760ac4017ed366026e4cb276
1388 // 13.4.1 Array.prototype.toLocaleString ([ locales [ , options ]])
array_toLocaleString(JSContext * cx,unsigned argc,Value * vp)1389 static bool array_toLocaleString(JSContext* cx, unsigned argc, Value* vp) {
1390 AutoCheckRecursionLimit recursion(cx);
1391 if (!recursion.check(cx)) {
1392 return false;
1393 }
1394
1395 CallArgs args = CallArgsFromVp(argc, vp);
1396
1397 // Step 1
1398 RootedObject obj(cx, ToObject(cx, args.thisv()));
1399 if (!obj) {
1400 return false;
1401 }
1402
1403 // Avoid calling into self-hosted code if the array is empty.
1404 if (obj->is<ArrayObject>() && obj->as<ArrayObject>().length() == 0) {
1405 args.rval().setString(cx->names().empty);
1406 return true;
1407 }
1408
1409 AutoCycleDetector detector(cx, obj);
1410 if (!detector.init()) {
1411 return false;
1412 }
1413
1414 if (detector.foundCycle()) {
1415 args.rval().setString(cx->names().empty);
1416 return true;
1417 }
1418
1419 FixedInvokeArgs<2> args2(cx);
1420
1421 args2[0].set(args.get(0));
1422 args2[1].set(args.get(1));
1423
1424 // Steps 2-10.
1425 RootedValue thisv(cx, ObjectValue(*obj));
1426 return CallSelfHostedFunction(cx, cx->names().ArrayToLocaleString, thisv,
1427 args2, args.rval());
1428 }
1429
1430 /* vector must point to rooted memory. */
SetArrayElements(JSContext * cx,HandleObject obj,uint64_t start,uint32_t count,const Value * vector)1431 static bool SetArrayElements(JSContext* cx, HandleObject obj, uint64_t start,
1432 uint32_t count, const Value* vector) {
1433 MOZ_ASSERT(count <= MAX_ARRAY_INDEX);
1434 MOZ_ASSERT(start + count < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));
1435
1436 if (count == 0) {
1437 return true;
1438 }
1439
1440 if (!ObjectMayHaveExtraIndexedProperties(obj) && start <= UINT32_MAX) {
1441 NativeObject* nobj = &obj->as<NativeObject>();
1442 DenseElementResult result =
1443 nobj->setOrExtendDenseElements(cx, uint32_t(start), vector, count);
1444 if (result != DenseElementResult::Incomplete) {
1445 return result == DenseElementResult::Success;
1446 }
1447 }
1448
1449 RootedId id(cx);
1450 const Value* end = vector + count;
1451 while (vector < end) {
1452 if (!CheckForInterrupt(cx)) {
1453 return false;
1454 }
1455
1456 if (!ToId(cx, start++, &id)) {
1457 return false;
1458 }
1459
1460 if (!SetProperty(cx, obj, id, HandleValue::fromMarkedLocation(vector++))) {
1461 return false;
1462 }
1463 }
1464
1465 return true;
1466 }
1467
ArrayReverseDenseKernel(JSContext * cx,HandleNativeObject obj,uint32_t length)1468 static DenseElementResult ArrayReverseDenseKernel(JSContext* cx,
1469 HandleNativeObject obj,
1470 uint32_t length) {
1471 MOZ_ASSERT(length > 1);
1472
1473 // If there are no elements, we're done.
1474 if (obj->getDenseInitializedLength() == 0) {
1475 return DenseElementResult::Success;
1476 }
1477
1478 if (!obj->isExtensible()) {
1479 return DenseElementResult::Incomplete;
1480 }
1481
1482 if (!IsPackedArray(obj)) {
1483 /*
1484 * It's actually surprisingly complicated to reverse an array due
1485 * to the orthogonality of array length and array capacity while
1486 * handling leading and trailing holes correctly. Reversing seems
1487 * less likely to be a common operation than other array
1488 * mass-mutation methods, so for now just take a probably-small
1489 * memory hit (in the absence of too many holes in the array at
1490 * its start) and ensure that the capacity is sufficient to hold
1491 * all the elements in the array if it were full.
1492 */
1493 DenseElementResult result = obj->ensureDenseElements(cx, length, 0);
1494 if (result != DenseElementResult::Success) {
1495 return result;
1496 }
1497
1498 /* Fill out the array's initialized length to its proper length. */
1499 obj->ensureDenseInitializedLength(length, 0);
1500 }
1501
1502 if (!obj->denseElementsMaybeInIteration() &&
1503 !cx->zone()->needsIncrementalBarrier()) {
1504 obj->reverseDenseElementsNoPreBarrier(length);
1505 return DenseElementResult::Success;
1506 }
1507
1508 auto setElementMaybeHole = [](JSContext* cx, HandleNativeObject obj,
1509 uint32_t index, const Value& val) {
1510 if (MOZ_LIKELY(!val.isMagic(JS_ELEMENTS_HOLE))) {
1511 obj->setDenseElement(index, val);
1512 return true;
1513 }
1514
1515 obj->setDenseElementHole(index);
1516 return SuppressDeletedProperty(cx, obj, INT_TO_JSID(index));
1517 };
1518
1519 RootedValue origlo(cx), orighi(cx);
1520
1521 uint32_t lo = 0, hi = length - 1;
1522 for (; lo < hi; lo++, hi--) {
1523 origlo = obj->getDenseElement(lo);
1524 orighi = obj->getDenseElement(hi);
1525 if (!setElementMaybeHole(cx, obj, lo, orighi)) {
1526 return DenseElementResult::Failure;
1527 }
1528 if (!setElementMaybeHole(cx, obj, hi, origlo)) {
1529 return DenseElementResult::Failure;
1530 }
1531 }
1532
1533 return DenseElementResult::Success;
1534 }
1535
1536 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
1537 // 22.1.3.21 Array.prototype.reverse ( )
array_reverse(JSContext * cx,unsigned argc,Value * vp)1538 static bool array_reverse(JSContext* cx, unsigned argc, Value* vp) {
1539 AutoGeckoProfilerEntry pseudoFrame(
1540 cx, "Array.prototype.reverse", JS::ProfilingCategoryPair::JS,
1541 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
1542 CallArgs args = CallArgsFromVp(argc, vp);
1543
1544 // Step 1.
1545 RootedObject obj(cx, ToObject(cx, args.thisv()));
1546 if (!obj) {
1547 return false;
1548 }
1549
1550 // Step 2.
1551 uint64_t len;
1552 if (!GetLengthPropertyInlined(cx, obj, &len)) {
1553 return false;
1554 }
1555
1556 // An empty array or an array with length 1 is already reversed.
1557 if (len <= 1) {
1558 args.rval().setObject(*obj);
1559 return true;
1560 }
1561
1562 if (IsPackedArrayOrNoExtraIndexedProperties(obj, len) && len <= UINT32_MAX) {
1563 DenseElementResult result =
1564 ArrayReverseDenseKernel(cx, obj.as<NativeObject>(), uint32_t(len));
1565 if (result != DenseElementResult::Incomplete) {
1566 /*
1567 * Per ECMA-262, don't update the length of the array, even if the new
1568 * array has trailing holes (and thus the original array began with
1569 * holes).
1570 */
1571 args.rval().setObject(*obj);
1572 return result == DenseElementResult::Success;
1573 }
1574 }
1575
1576 // Steps 3-5.
1577 RootedValue lowval(cx), hival(cx);
1578 for (uint64_t i = 0, half = len / 2; i < half; i++) {
1579 bool hole, hole2;
1580 if (!CheckForInterrupt(cx) ||
1581 !HasAndGetElement(cx, obj, i, &hole, &lowval) ||
1582 !HasAndGetElement(cx, obj, len - i - 1, &hole2, &hival)) {
1583 return false;
1584 }
1585
1586 if (!hole && !hole2) {
1587 if (!SetArrayElement(cx, obj, i, hival)) {
1588 return false;
1589 }
1590 if (!SetArrayElement(cx, obj, len - i - 1, lowval)) {
1591 return false;
1592 }
1593 } else if (hole && !hole2) {
1594 if (!SetArrayElement(cx, obj, i, hival)) {
1595 return false;
1596 }
1597 if (!DeletePropertyOrThrow(cx, obj, len - i - 1)) {
1598 return false;
1599 }
1600 } else if (!hole && hole2) {
1601 if (!DeletePropertyOrThrow(cx, obj, i)) {
1602 return false;
1603 }
1604 if (!SetArrayElement(cx, obj, len - i - 1, lowval)) {
1605 return false;
1606 }
1607 } else {
1608 // No action required.
1609 }
1610 }
1611
1612 // Step 6.
1613 args.rval().setObject(*obj);
1614 return true;
1615 }
1616
CompareStringValues(JSContext * cx,const Value & a,const Value & b,bool * lessOrEqualp)1617 static inline bool CompareStringValues(JSContext* cx, const Value& a,
1618 const Value& b, bool* lessOrEqualp) {
1619 if (!CheckForInterrupt(cx)) {
1620 return false;
1621 }
1622
1623 JSString* astr = a.toString();
1624 JSString* bstr = b.toString();
1625 int32_t result;
1626 if (!CompareStrings(cx, astr, bstr, &result)) {
1627 return false;
1628 }
1629
1630 *lessOrEqualp = (result <= 0);
1631 return true;
1632 }
1633
1634 static const uint64_t powersOf10[] = {
1635 1, 10, 100, 1000, 10000, 100000,
1636 1000000, 10000000, 100000000, 1000000000, 1000000000000ULL};
1637
NumDigitsBase10(uint32_t n)1638 static inline unsigned NumDigitsBase10(uint32_t n) {
1639 /*
1640 * This is just floor_log10(n) + 1
1641 * Algorithm taken from
1642 * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
1643 */
1644 uint32_t log2 = CeilingLog2(n);
1645 uint32_t t = log2 * 1233 >> 12;
1646 return t - (n < powersOf10[t]) + 1;
1647 }
1648
CompareLexicographicInt32(const Value & a,const Value & b,bool * lessOrEqualp)1649 static inline bool CompareLexicographicInt32(const Value& a, const Value& b,
1650 bool* lessOrEqualp) {
1651 int32_t aint = a.toInt32();
1652 int32_t bint = b.toInt32();
1653
1654 /*
1655 * If both numbers are equal ... trivial
1656 * If only one of both is negative --> arithmetic comparison as char code
1657 * of '-' is always less than any other digit
1658 * If both numbers are negative convert them to positive and continue
1659 * handling ...
1660 */
1661 if (aint == bint) {
1662 *lessOrEqualp = true;
1663 } else if ((aint < 0) && (bint >= 0)) {
1664 *lessOrEqualp = true;
1665 } else if ((aint >= 0) && (bint < 0)) {
1666 *lessOrEqualp = false;
1667 } else {
1668 uint32_t auint = Abs(aint);
1669 uint32_t buint = Abs(bint);
1670
1671 /*
1672 * ... get number of digits of both integers.
1673 * If they have the same number of digits --> arithmetic comparison.
1674 * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
1675 * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
1676 */
1677 unsigned digitsa = NumDigitsBase10(auint);
1678 unsigned digitsb = NumDigitsBase10(buint);
1679 if (digitsa == digitsb) {
1680 *lessOrEqualp = (auint <= buint);
1681 } else if (digitsa > digitsb) {
1682 MOZ_ASSERT((digitsa - digitsb) < std::size(powersOf10));
1683 *lessOrEqualp =
1684 (uint64_t(auint) < uint64_t(buint) * powersOf10[digitsa - digitsb]);
1685 } else { /* if (digitsb > digitsa) */
1686 MOZ_ASSERT((digitsb - digitsa) < std::size(powersOf10));
1687 *lessOrEqualp =
1688 (uint64_t(auint) * powersOf10[digitsb - digitsa] <= uint64_t(buint));
1689 }
1690 }
1691
1692 return true;
1693 }
1694
1695 template <typename Char1, typename Char2>
CompareSubStringValues(JSContext * cx,const Char1 * s1,size_t len1,const Char2 * s2,size_t len2,bool * lessOrEqualp)1696 static inline bool CompareSubStringValues(JSContext* cx, const Char1* s1,
1697 size_t len1, const Char2* s2,
1698 size_t len2, bool* lessOrEqualp) {
1699 if (!CheckForInterrupt(cx)) {
1700 return false;
1701 }
1702
1703 if (!s1 || !s2) {
1704 return false;
1705 }
1706
1707 int32_t result = CompareChars(s1, len1, s2, len2);
1708 *lessOrEqualp = (result <= 0);
1709 return true;
1710 }
1711
1712 namespace {
1713
1714 struct SortComparatorStrings {
1715 JSContext* const cx;
1716
SortComparatorStrings__anon71f97aa40211::SortComparatorStrings1717 explicit SortComparatorStrings(JSContext* cx) : cx(cx) {}
1718
operator ()__anon71f97aa40211::SortComparatorStrings1719 bool operator()(const Value& a, const Value& b, bool* lessOrEqualp) {
1720 return CompareStringValues(cx, a, b, lessOrEqualp);
1721 }
1722 };
1723
1724 struct SortComparatorLexicographicInt32 {
operator ()__anon71f97aa40211::SortComparatorLexicographicInt321725 bool operator()(const Value& a, const Value& b, bool* lessOrEqualp) {
1726 return CompareLexicographicInt32(a, b, lessOrEqualp);
1727 }
1728 };
1729
1730 struct StringifiedElement {
1731 size_t charsBegin;
1732 size_t charsEnd;
1733 size_t elementIndex;
1734 };
1735
1736 struct SortComparatorStringifiedElements {
1737 JSContext* const cx;
1738 const StringBuffer& sb;
1739
SortComparatorStringifiedElements__anon71f97aa40211::SortComparatorStringifiedElements1740 SortComparatorStringifiedElements(JSContext* cx, const StringBuffer& sb)
1741 : cx(cx), sb(sb) {}
1742
operator ()__anon71f97aa40211::SortComparatorStringifiedElements1743 bool operator()(const StringifiedElement& a, const StringifiedElement& b,
1744 bool* lessOrEqualp) {
1745 size_t lenA = a.charsEnd - a.charsBegin;
1746 size_t lenB = b.charsEnd - b.charsBegin;
1747
1748 if (sb.isUnderlyingBufferLatin1()) {
1749 return CompareSubStringValues(cx, sb.rawLatin1Begin() + a.charsBegin,
1750 lenA, sb.rawLatin1Begin() + b.charsBegin,
1751 lenB, lessOrEqualp);
1752 }
1753
1754 return CompareSubStringValues(cx, sb.rawTwoByteBegin() + a.charsBegin, lenA,
1755 sb.rawTwoByteBegin() + b.charsBegin, lenB,
1756 lessOrEqualp);
1757 }
1758 };
1759
1760 struct NumericElement {
1761 double dv;
1762 size_t elementIndex;
1763 };
1764
ComparatorNumericLeftMinusRight(const NumericElement & a,const NumericElement & b,bool * lessOrEqualp)1765 static bool ComparatorNumericLeftMinusRight(const NumericElement& a,
1766 const NumericElement& b,
1767 bool* lessOrEqualp) {
1768 *lessOrEqualp = (a.dv <= b.dv);
1769 return true;
1770 }
1771
ComparatorNumericRightMinusLeft(const NumericElement & a,const NumericElement & b,bool * lessOrEqualp)1772 static bool ComparatorNumericRightMinusLeft(const NumericElement& a,
1773 const NumericElement& b,
1774 bool* lessOrEqualp) {
1775 *lessOrEqualp = (b.dv <= a.dv);
1776 return true;
1777 }
1778
1779 using ComparatorNumeric = bool (*)(const NumericElement&, const NumericElement&,
1780 bool*);
1781
1782 static const ComparatorNumeric SortComparatorNumerics[] = {
1783 nullptr, nullptr, ComparatorNumericLeftMinusRight,
1784 ComparatorNumericRightMinusLeft};
1785
ComparatorInt32LeftMinusRight(const Value & a,const Value & b,bool * lessOrEqualp)1786 static bool ComparatorInt32LeftMinusRight(const Value& a, const Value& b,
1787 bool* lessOrEqualp) {
1788 *lessOrEqualp = (a.toInt32() <= b.toInt32());
1789 return true;
1790 }
1791
ComparatorInt32RightMinusLeft(const Value & a,const Value & b,bool * lessOrEqualp)1792 static bool ComparatorInt32RightMinusLeft(const Value& a, const Value& b,
1793 bool* lessOrEqualp) {
1794 *lessOrEqualp = (b.toInt32() <= a.toInt32());
1795 return true;
1796 }
1797
1798 using ComparatorInt32 = bool (*)(const Value&, const Value&, bool*);
1799
1800 static const ComparatorInt32 SortComparatorInt32s[] = {
1801 nullptr, nullptr, ComparatorInt32LeftMinusRight,
1802 ComparatorInt32RightMinusLeft};
1803
1804 // Note: Values for this enum must match up with SortComparatorNumerics
1805 // and SortComparatorInt32s.
1806 enum ComparatorMatchResult {
1807 Match_Failure = 0,
1808 Match_None,
1809 Match_LeftMinusRight,
1810 Match_RightMinusLeft
1811 };
1812
1813 } // namespace
1814
1815 /*
1816 * Specialize behavior for comparator functions with particular common bytecode
1817 * patterns: namely, |return x - y| and |return y - x|.
1818 */
MatchNumericComparator(JSContext * cx,JSObject * obj)1819 static ComparatorMatchResult MatchNumericComparator(JSContext* cx,
1820 JSObject* obj) {
1821 if (!obj->is<JSFunction>()) {
1822 return Match_None;
1823 }
1824
1825 RootedFunction fun(cx, &obj->as<JSFunction>());
1826 if (!fun->isInterpreted() || fun->isClassConstructor()) {
1827 return Match_None;
1828 }
1829
1830 JSScript* script = JSFunction::getOrCreateScript(cx, fun);
1831 if (!script) {
1832 return Match_Failure;
1833 }
1834
1835 jsbytecode* pc = script->code();
1836
1837 uint16_t arg0, arg1;
1838 if (JSOp(*pc) != JSOp::GetArg) {
1839 return Match_None;
1840 }
1841 arg0 = GET_ARGNO(pc);
1842 pc += JSOpLength_GetArg;
1843
1844 if (JSOp(*pc) != JSOp::GetArg) {
1845 return Match_None;
1846 }
1847 arg1 = GET_ARGNO(pc);
1848 pc += JSOpLength_GetArg;
1849
1850 if (JSOp(*pc) != JSOp::Sub) {
1851 return Match_None;
1852 }
1853 pc += JSOpLength_Sub;
1854
1855 if (JSOp(*pc) != JSOp::Return) {
1856 return Match_None;
1857 }
1858
1859 if (arg0 == 0 && arg1 == 1) {
1860 return Match_LeftMinusRight;
1861 }
1862
1863 if (arg0 == 1 && arg1 == 0) {
1864 return Match_RightMinusLeft;
1865 }
1866
1867 return Match_None;
1868 }
1869
1870 template <typename K, typename C>
MergeSortByKey(K keys,size_t len,K scratch,C comparator,MutableHandle<GCVector<Value>> vec)1871 static inline bool MergeSortByKey(K keys, size_t len, K scratch, C comparator,
1872 MutableHandle<GCVector<Value>> vec) {
1873 MOZ_ASSERT(vec.length() >= len);
1874
1875 /* Sort keys. */
1876 if (!MergeSort(keys, len, scratch, comparator)) {
1877 return false;
1878 }
1879
1880 /*
1881 * Reorder vec by keys in-place, going element by element. When an out-of-
1882 * place element is encountered, move that element to its proper position,
1883 * displacing whatever element was at *that* point to its proper position,
1884 * and so on until an element must be moved to the current position.
1885 *
1886 * At each outer iteration all elements up to |i| are sorted. If
1887 * necessary each inner iteration moves some number of unsorted elements
1888 * (including |i|) directly to sorted position. Thus on completion |*vec|
1889 * is sorted, and out-of-position elements have moved once. Complexity is
1890 * Θ(len) + O(len) == O(2*len), with each element visited at most twice.
1891 */
1892 for (size_t i = 0; i < len; i++) {
1893 size_t j = keys[i].elementIndex;
1894 if (i == j) {
1895 continue; // fixed point
1896 }
1897
1898 MOZ_ASSERT(j > i, "Everything less than |i| should be in the right place!");
1899 Value tv = vec[j];
1900 do {
1901 size_t k = keys[j].elementIndex;
1902 keys[j].elementIndex = j;
1903 vec[j].set(vec[k]);
1904 j = k;
1905 } while (j != i);
1906
1907 // We could assert the loop invariant that |i == keys[i].elementIndex|
1908 // here if we synced |keys[i].elementIndex|. But doing so would render
1909 // the assertion vacuous, so don't bother, even in debug builds.
1910 vec[i].set(tv);
1911 }
1912
1913 return true;
1914 }
1915
1916 /*
1917 * Sort Values as strings.
1918 *
1919 * To minimize #conversions, SortLexicographically() first converts all Values
1920 * to strings at once, then sorts the elements by these cached strings.
1921 */
SortLexicographically(JSContext * cx,MutableHandle<GCVector<Value>> vec,size_t len)1922 static bool SortLexicographically(JSContext* cx,
1923 MutableHandle<GCVector<Value>> vec,
1924 size_t len) {
1925 MOZ_ASSERT(vec.length() >= len);
1926
1927 StringBuffer sb(cx);
1928 Vector<StringifiedElement, 0, TempAllocPolicy> strElements(cx);
1929
1930 /* MergeSort uses the upper half as scratch space. */
1931 if (!strElements.resize(2 * len)) {
1932 return false;
1933 }
1934
1935 /* Convert Values to strings. */
1936 size_t cursor = 0;
1937 for (size_t i = 0; i < len; i++) {
1938 if (!CheckForInterrupt(cx)) {
1939 return false;
1940 }
1941
1942 if (!ValueToStringBuffer(cx, vec[i], sb)) {
1943 return false;
1944 }
1945
1946 strElements[i] = {cursor, sb.length(), i};
1947 cursor = sb.length();
1948 }
1949
1950 /* Sort Values in vec alphabetically. */
1951 return MergeSortByKey(strElements.begin(), len, strElements.begin() + len,
1952 SortComparatorStringifiedElements(cx, sb), vec);
1953 }
1954
1955 /*
1956 * Sort Values as numbers.
1957 *
1958 * To minimize #conversions, SortNumerically first converts all Values to
1959 * numerics at once, then sorts the elements by these cached numerics.
1960 */
SortNumerically(JSContext * cx,MutableHandle<GCVector<Value>> vec,size_t len,ComparatorMatchResult comp)1961 static bool SortNumerically(JSContext* cx, MutableHandle<GCVector<Value>> vec,
1962 size_t len, ComparatorMatchResult comp) {
1963 MOZ_ASSERT(vec.length() >= len);
1964
1965 Vector<NumericElement, 0, TempAllocPolicy> numElements(cx);
1966
1967 /* MergeSort uses the upper half as scratch space. */
1968 if (!numElements.resize(2 * len)) {
1969 return false;
1970 }
1971
1972 /* Convert Values to numerics. */
1973 for (size_t i = 0; i < len; i++) {
1974 if (!CheckForInterrupt(cx)) {
1975 return false;
1976 }
1977
1978 double dv;
1979 if (!ToNumber(cx, vec[i], &dv)) {
1980 return false;
1981 }
1982
1983 numElements[i] = {dv, i};
1984 }
1985
1986 /* Sort Values in vec numerically. */
1987 return MergeSortByKey(numElements.begin(), len, numElements.begin() + len,
1988 SortComparatorNumerics[comp], vec);
1989 }
1990
FillWithUndefined(JSContext * cx,HandleObject obj,uint32_t start,uint32_t count)1991 static bool FillWithUndefined(JSContext* cx, HandleObject obj, uint32_t start,
1992 uint32_t count) {
1993 MOZ_ASSERT(start < start + count,
1994 "count > 0 and start + count doesn't overflow");
1995
1996 do {
1997 if (ObjectMayHaveExtraIndexedProperties(obj)) {
1998 break;
1999 }
2000
2001 NativeObject* nobj = &obj->as<NativeObject>();
2002 if (!nobj->isExtensible()) {
2003 break;
2004 }
2005
2006 if (obj->is<ArrayObject>() && !obj->as<ArrayObject>().lengthIsWritable() &&
2007 start + count >= obj->as<ArrayObject>().length()) {
2008 break;
2009 }
2010
2011 DenseElementResult result = nobj->ensureDenseElements(cx, start, count);
2012 if (result != DenseElementResult::Success) {
2013 if (result == DenseElementResult::Failure) {
2014 return false;
2015 }
2016 MOZ_ASSERT(result == DenseElementResult::Incomplete);
2017 break;
2018 }
2019
2020 if (obj->is<ArrayObject>() &&
2021 start + count >= obj->as<ArrayObject>().length()) {
2022 obj->as<ArrayObject>().setLength(start + count);
2023 }
2024
2025 for (uint32_t i = 0; i < count; i++) {
2026 nobj->setDenseElement(start + i, UndefinedHandleValue);
2027 }
2028
2029 return true;
2030 } while (false);
2031
2032 for (uint32_t i = 0; i < count; i++) {
2033 if (!CheckForInterrupt(cx) ||
2034 !SetArrayElement(cx, obj, start + i, UndefinedHandleValue)) {
2035 return false;
2036 }
2037 }
2038
2039 return true;
2040 }
2041
intrinsic_ArrayNativeSort(JSContext * cx,unsigned argc,Value * vp)2042 bool js::intrinsic_ArrayNativeSort(JSContext* cx, unsigned argc, Value* vp) {
2043 // This function is called from the self-hosted Array.prototype.sort
2044 // implementation. It returns |true| if the array was sorted, otherwise it
2045 // returns |false| to notify the self-hosted code to perform the sorting.
2046 CallArgs args = CallArgsFromVp(argc, vp);
2047 MOZ_ASSERT(args.length() == 1);
2048
2049 HandleValue fval = args[0];
2050 MOZ_ASSERT(fval.isUndefined() || IsCallable(fval));
2051
2052 ComparatorMatchResult comp;
2053 if (fval.isObject()) {
2054 comp = MatchNumericComparator(cx, &fval.toObject());
2055 if (comp == Match_Failure) {
2056 return false;
2057 }
2058
2059 if (comp == Match_None) {
2060 // Non-optimized user supplied comparators perform much better when
2061 // called from within a self-hosted sorting function.
2062 args.rval().setBoolean(false);
2063 return true;
2064 }
2065 } else {
2066 comp = Match_None;
2067 }
2068
2069 RootedObject obj(cx, &args.thisv().toObject());
2070
2071 uint64_t length;
2072 if (!GetLengthPropertyInlined(cx, obj, &length)) {
2073 return false;
2074 }
2075 if (length < 2) {
2076 /* [] and [a] remain unchanged when sorted. */
2077 args.rval().setBoolean(true);
2078 return true;
2079 }
2080
2081 if (length > UINT32_MAX) {
2082 ReportAllocationOverflow(cx);
2083 return false;
2084 }
2085 uint32_t len = uint32_t(length);
2086
2087 /*
2088 * We need a temporary array of 2 * len Value to hold the array elements
2089 * and the scratch space for merge sort. Check that its size does not
2090 * overflow size_t, which would allow for indexing beyond the end of the
2091 * malloc'd vector.
2092 */
2093 #if JS_BITS_PER_WORD == 32
2094 if (size_t(len) > size_t(-1) / (2 * sizeof(Value))) {
2095 ReportAllocationOverflow(cx);
2096 return false;
2097 }
2098 #endif
2099
2100 size_t n, undefs;
2101 {
2102 Rooted<GCVector<Value>> vec(cx, GCVector<Value>(cx));
2103 if (!vec.reserve(2 * size_t(len))) {
2104 return false;
2105 }
2106
2107 /*
2108 * By ECMA 262, 15.4.4.11, a property that does not exist (which we
2109 * call a "hole") is always greater than an existing property with
2110 * value undefined and that is always greater than any other property.
2111 * Thus to sort holes and undefs we simply count them, sort the rest
2112 * of elements, append undefs after them and then make holes after
2113 * undefs.
2114 */
2115 undefs = 0;
2116 bool allStrings = true;
2117 bool allInts = true;
2118 RootedValue v(cx);
2119 if (IsPackedArray(obj)) {
2120 HandleArrayObject array = obj.as<ArrayObject>();
2121
2122 for (uint32_t i = 0; i < len; i++) {
2123 if (!CheckForInterrupt(cx)) {
2124 return false;
2125 }
2126
2127 v.set(array->getDenseElement(i));
2128 MOZ_ASSERT(!v.isMagic(JS_ELEMENTS_HOLE));
2129 if (v.isUndefined()) {
2130 ++undefs;
2131 continue;
2132 }
2133 vec.infallibleAppend(v);
2134 allStrings = allStrings && v.isString();
2135 allInts = allInts && v.isInt32();
2136 }
2137 } else {
2138 for (uint32_t i = 0; i < len; i++) {
2139 if (!CheckForInterrupt(cx)) {
2140 return false;
2141 }
2142
2143 bool hole;
2144 if (!HasAndGetElement(cx, obj, i, &hole, &v)) {
2145 return false;
2146 }
2147 if (hole) {
2148 continue;
2149 }
2150 if (v.isUndefined()) {
2151 ++undefs;
2152 continue;
2153 }
2154 vec.infallibleAppend(v);
2155 allStrings = allStrings && v.isString();
2156 allInts = allInts && v.isInt32();
2157 }
2158 }
2159
2160 /*
2161 * If the array only contains holes, we're done. But if it contains
2162 * undefs, those must be sorted to the front of the array.
2163 */
2164 n = vec.length();
2165 if (n == 0 && undefs == 0) {
2166 args.rval().setBoolean(true);
2167 return true;
2168 }
2169
2170 /* Here len == n + undefs + number_of_holes. */
2171 if (comp == Match_None) {
2172 /*
2173 * Sort using the default comparator converting all elements to
2174 * strings.
2175 */
2176 if (allStrings) {
2177 MOZ_ALWAYS_TRUE(vec.resize(n * 2));
2178 if (!MergeSort(vec.begin(), n, vec.begin() + n,
2179 SortComparatorStrings(cx))) {
2180 return false;
2181 }
2182 } else if (allInts) {
2183 MOZ_ALWAYS_TRUE(vec.resize(n * 2));
2184 if (!MergeSort(vec.begin(), n, vec.begin() + n,
2185 SortComparatorLexicographicInt32())) {
2186 return false;
2187 }
2188 } else {
2189 if (!SortLexicographically(cx, &vec, n)) {
2190 return false;
2191 }
2192 }
2193 } else {
2194 if (allInts) {
2195 MOZ_ALWAYS_TRUE(vec.resize(n * 2));
2196 if (!MergeSort(vec.begin(), n, vec.begin() + n,
2197 SortComparatorInt32s[comp])) {
2198 return false;
2199 }
2200 } else {
2201 if (!SortNumerically(cx, &vec, n, comp)) {
2202 return false;
2203 }
2204 }
2205 }
2206
2207 if (!SetArrayElements(cx, obj, 0, uint32_t(n), vec.begin())) {
2208 return false;
2209 }
2210 }
2211
2212 /* Set undefs that sorted after the rest of elements. */
2213 if (undefs > 0) {
2214 if (!FillWithUndefined(cx, obj, n, undefs)) {
2215 return false;
2216 }
2217 n += undefs;
2218 }
2219
2220 /* Re-create any holes that sorted to the end of the array. */
2221 for (uint32_t i = n; i < len; i++) {
2222 if (!CheckForInterrupt(cx) || !DeletePropertyOrThrow(cx, obj, i)) {
2223 return false;
2224 }
2225 }
2226 args.rval().setBoolean(true);
2227 return true;
2228 }
2229
NewbornArrayPush(JSContext * cx,HandleObject obj,const Value & v)2230 bool js::NewbornArrayPush(JSContext* cx, HandleObject obj, const Value& v) {
2231 HandleArrayObject arr = obj.as<ArrayObject>();
2232
2233 MOZ_ASSERT(!v.isMagic());
2234 MOZ_ASSERT(arr->lengthIsWritable());
2235
2236 uint32_t length = arr->length();
2237 MOZ_ASSERT(length <= arr->getDenseCapacity());
2238
2239 if (!arr->ensureElements(cx, length + 1)) {
2240 return false;
2241 }
2242
2243 arr->setDenseInitializedLength(length + 1);
2244 arr->setLength(length + 1);
2245 arr->initDenseElement(length, v);
2246 return true;
2247 }
2248
2249 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2250 // 22.1.3.18 Array.prototype.push ( ...items )
array_push(JSContext * cx,unsigned argc,Value * vp)2251 bool js::array_push(JSContext* cx, unsigned argc, Value* vp) {
2252 AutoGeckoProfilerEntry pseudoFrame(
2253 cx, "Array.prototype.push", JS::ProfilingCategoryPair::JS,
2254 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
2255 CallArgs args = CallArgsFromVp(argc, vp);
2256
2257 // Step 1.
2258 RootedObject obj(cx, ToObject(cx, args.thisv()));
2259 if (!obj) {
2260 return false;
2261 }
2262
2263 // Step 2.
2264 uint64_t length;
2265 if (!GetLengthPropertyInlined(cx, obj, &length)) {
2266 return false;
2267 }
2268
2269 if (!ObjectMayHaveExtraIndexedProperties(obj) && length <= UINT32_MAX) {
2270 DenseElementResult result =
2271 obj->as<NativeObject>().setOrExtendDenseElements(
2272 cx, uint32_t(length), args.array(), args.length());
2273 if (result != DenseElementResult::Incomplete) {
2274 if (result == DenseElementResult::Failure) {
2275 return false;
2276 }
2277
2278 uint32_t newlength = uint32_t(length) + args.length();
2279 args.rval().setNumber(newlength);
2280
2281 // setOrExtendDenseElements takes care of updating the length for
2282 // arrays. Handle updates to the length of non-arrays here.
2283 if (!obj->is<ArrayObject>()) {
2284 MOZ_ASSERT(obj->is<NativeObject>());
2285 return SetLengthProperty(cx, obj, newlength);
2286 }
2287
2288 return true;
2289 }
2290 }
2291
2292 // Step 5.
2293 uint64_t newlength = length + args.length();
2294 if (newlength >= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT)) {
2295 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2296 JSMSG_TOO_LONG_ARRAY);
2297 return false;
2298 }
2299
2300 // Steps 3-6.
2301 if (!SetArrayElements(cx, obj, length, args.length(), args.array())) {
2302 return false;
2303 }
2304
2305 // Steps 7-8.
2306 args.rval().setNumber(double(newlength));
2307 return SetLengthProperty(cx, obj, newlength);
2308 }
2309
2310 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2311 // 22.1.3.17 Array.prototype.pop ( )
array_pop(JSContext * cx,unsigned argc,Value * vp)2312 bool js::array_pop(JSContext* cx, unsigned argc, Value* vp) {
2313 AutoGeckoProfilerEntry pseudoFrame(
2314 cx, "Array.prototype.pop", JS::ProfilingCategoryPair::JS,
2315 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
2316 CallArgs args = CallArgsFromVp(argc, vp);
2317
2318 // Step 1.
2319 RootedObject obj(cx, ToObject(cx, args.thisv()));
2320 if (!obj) {
2321 return false;
2322 }
2323
2324 // Step 2.
2325 uint64_t index;
2326 if (!GetLengthPropertyInlined(cx, obj, &index)) {
2327 return false;
2328 }
2329
2330 // Steps 3-4.
2331 if (index == 0) {
2332 // Step 3.b.
2333 args.rval().setUndefined();
2334 } else {
2335 // Steps 4.a-b.
2336 index--;
2337
2338 // Steps 4.c, 4.f.
2339 if (!GetArrayElement(cx, obj, index, args.rval())) {
2340 return false;
2341 }
2342
2343 // Steps 4.d.
2344 if (!DeletePropertyOrThrow(cx, obj, index)) {
2345 return false;
2346 }
2347 }
2348
2349 // Steps 3.a, 4.e.
2350 return SetLengthProperty(cx, obj, index);
2351 }
2352
ArrayShiftMoveElements(ArrayObject * arr)2353 void js::ArrayShiftMoveElements(ArrayObject* arr) {
2354 AutoUnsafeCallWithABI unsafe;
2355 MOZ_ASSERT(arr->isExtensible());
2356 MOZ_ASSERT(arr->lengthIsWritable());
2357 MOZ_ASSERT(IsPackedArray(arr));
2358 MOZ_ASSERT(!arr->denseElementsHaveMaybeInIterationFlag());
2359
2360 size_t initlen = arr->getDenseInitializedLength();
2361 MOZ_ASSERT(initlen > 0);
2362
2363 if (!arr->tryShiftDenseElements(1)) {
2364 arr->moveDenseElements(0, 1, initlen - 1);
2365 }
2366 }
2367
SetInitializedLength(JSContext * cx,NativeObject * obj,size_t initlen)2368 static inline void SetInitializedLength(JSContext* cx, NativeObject* obj,
2369 size_t initlen) {
2370 MOZ_ASSERT(obj->isExtensible());
2371
2372 size_t oldInitlen = obj->getDenseInitializedLength();
2373 obj->setDenseInitializedLength(initlen);
2374 if (initlen < oldInitlen) {
2375 obj->shrinkElements(cx, initlen);
2376 }
2377 }
2378
ArrayShiftDenseKernel(JSContext * cx,HandleObject obj,MutableHandleValue rval)2379 static DenseElementResult ArrayShiftDenseKernel(JSContext* cx, HandleObject obj,
2380 MutableHandleValue rval) {
2381 if (!IsPackedArray(obj) && ObjectMayHaveExtraIndexedProperties(obj)) {
2382 return DenseElementResult::Incomplete;
2383 }
2384
2385 HandleNativeObject nobj = obj.as<NativeObject>();
2386 if (nobj->denseElementsMaybeInIteration()) {
2387 return DenseElementResult::Incomplete;
2388 }
2389
2390 if (!nobj->isExtensible()) {
2391 return DenseElementResult::Incomplete;
2392 }
2393
2394 size_t initlen = nobj->getDenseInitializedLength();
2395 if (initlen == 0) {
2396 return DenseElementResult::Incomplete;
2397 }
2398
2399 rval.set(nobj->getDenseElement(0));
2400 if (rval.isMagic(JS_ELEMENTS_HOLE)) {
2401 rval.setUndefined();
2402 }
2403
2404 if (nobj->tryShiftDenseElements(1)) {
2405 return DenseElementResult::Success;
2406 }
2407
2408 nobj->moveDenseElements(0, 1, initlen - 1);
2409
2410 SetInitializedLength(cx, nobj, initlen - 1);
2411 return DenseElementResult::Success;
2412 }
2413
2414 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2415 // 22.1.3.22 Array.prototype.shift ( )
array_shift(JSContext * cx,unsigned argc,Value * vp)2416 bool js::array_shift(JSContext* cx, unsigned argc, Value* vp) {
2417 AutoGeckoProfilerEntry pseudoFrame(
2418 cx, "Array.prototype.shift", JS::ProfilingCategoryPair::JS,
2419 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
2420 CallArgs args = CallArgsFromVp(argc, vp);
2421
2422 // Step 1.
2423 RootedObject obj(cx, ToObject(cx, args.thisv()));
2424 if (!obj) {
2425 return false;
2426 }
2427
2428 // Step 2.
2429 uint64_t len;
2430 if (!GetLengthPropertyInlined(cx, obj, &len)) {
2431 return false;
2432 }
2433
2434 // Step 3.
2435 if (len == 0) {
2436 // Step 3.a.
2437 if (!SetLengthProperty(cx, obj, uint32_t(0))) {
2438 return false;
2439 }
2440
2441 // Step 3.b.
2442 args.rval().setUndefined();
2443 return true;
2444 }
2445
2446 uint64_t newlen = len - 1;
2447
2448 /* Fast paths. */
2449 uint64_t startIndex;
2450 DenseElementResult result = ArrayShiftDenseKernel(cx, obj, args.rval());
2451 if (result != DenseElementResult::Incomplete) {
2452 if (result == DenseElementResult::Failure) {
2453 return false;
2454 }
2455
2456 if (len <= UINT32_MAX) {
2457 return SetLengthProperty(cx, obj, newlen);
2458 }
2459
2460 startIndex = UINT32_MAX - 1;
2461 } else {
2462 // Steps 4, 9.
2463 if (!GetElement(cx, obj, 0, args.rval())) {
2464 return false;
2465 }
2466
2467 startIndex = 0;
2468 }
2469
2470 // Steps 5-6.
2471 RootedValue value(cx);
2472 for (uint64_t i = startIndex; i < newlen; i++) {
2473 if (!CheckForInterrupt(cx)) {
2474 return false;
2475 }
2476 bool hole;
2477 if (!HasAndGetElement(cx, obj, i + 1, &hole, &value)) {
2478 return false;
2479 }
2480 if (hole) {
2481 if (!DeletePropertyOrThrow(cx, obj, i)) {
2482 return false;
2483 }
2484 } else {
2485 if (!SetArrayElement(cx, obj, i, value)) {
2486 return false;
2487 }
2488 }
2489 }
2490
2491 // Step 7.
2492 if (!DeletePropertyOrThrow(cx, obj, newlen)) {
2493 return false;
2494 }
2495
2496 // Step 8.
2497 return SetLengthProperty(cx, obj, newlen);
2498 }
2499
2500 // ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
2501 // 22.1.3.29 Array.prototype.unshift ( ...items )
array_unshift(JSContext * cx,unsigned argc,Value * vp)2502 static bool array_unshift(JSContext* cx, unsigned argc, Value* vp) {
2503 AutoGeckoProfilerEntry pseudoFrame(
2504 cx, "Array.prototype.unshift", JS::ProfilingCategoryPair::JS,
2505 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
2506 CallArgs args = CallArgsFromVp(argc, vp);
2507
2508 // Step 1.
2509 RootedObject obj(cx, ToObject(cx, args.thisv()));
2510 if (!obj) {
2511 return false;
2512 }
2513
2514 // Step 2.
2515 uint64_t length;
2516 if (!GetLengthPropertyInlined(cx, obj, &length)) {
2517 return false;
2518 }
2519
2520 // Steps 3-4.
2521 if (args.length() > 0) {
2522 bool optimized = false;
2523 do {
2524 if (length > UINT32_MAX) {
2525 break;
2526 }
2527 if (ObjectMayHaveExtraIndexedProperties(obj)) {
2528 break;
2529 }
2530 NativeObject* nobj = &obj->as<NativeObject>();
2531 if (nobj->denseElementsMaybeInIteration()) {
2532 break;
2533 }
2534 if (!nobj->isExtensible()) {
2535 break;
2536 }
2537 if (nobj->is<ArrayObject>() &&
2538 !nobj->as<ArrayObject>().lengthIsWritable()) {
2539 break;
2540 }
2541 if (!nobj->tryUnshiftDenseElements(args.length())) {
2542 DenseElementResult result =
2543 nobj->ensureDenseElements(cx, uint32_t(length), args.length());
2544 if (result != DenseElementResult::Success) {
2545 if (result == DenseElementResult::Failure) {
2546 return false;
2547 }
2548 MOZ_ASSERT(result == DenseElementResult::Incomplete);
2549 break;
2550 }
2551 if (length > 0) {
2552 nobj->moveDenseElements(args.length(), 0, uint32_t(length));
2553 }
2554 }
2555 for (uint32_t i = 0; i < args.length(); i++) {
2556 nobj->setDenseElement(i, args[i]);
2557 }
2558 optimized = true;
2559 } while (false);
2560
2561 if (!optimized) {
2562 if (length > 0) {
2563 uint64_t last = length;
2564 uint64_t upperIndex = last + args.length();
2565
2566 // Step 4.a.
2567 if (upperIndex >= uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT)) {
2568 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2569 JSMSG_TOO_LONG_ARRAY);
2570 return false;
2571 }
2572
2573 // Steps 4.b-c.
2574 RootedValue value(cx);
2575 do {
2576 --last;
2577 --upperIndex;
2578 if (!CheckForInterrupt(cx)) {
2579 return false;
2580 }
2581 bool hole;
2582 if (!HasAndGetElement(cx, obj, last, &hole, &value)) {
2583 return false;
2584 }
2585 if (hole) {
2586 if (!DeletePropertyOrThrow(cx, obj, upperIndex)) {
2587 return false;
2588 }
2589 } else {
2590 if (!SetArrayElement(cx, obj, upperIndex, value)) {
2591 return false;
2592 }
2593 }
2594 } while (last != 0);
2595 }
2596
2597 // Steps 4.d-f.
2598 /* Copy from args to the bottom of the array. */
2599 if (!SetArrayElements(cx, obj, 0, args.length(), args.array())) {
2600 return false;
2601 }
2602 }
2603 }
2604
2605 // Step 5.
2606 uint64_t newlength = length + args.length();
2607 if (!SetLengthProperty(cx, obj, newlength)) {
2608 return false;
2609 }
2610
2611 // Step 6.
2612 /* Follow Perl by returning the new array length. */
2613 args.rval().setNumber(double(newlength));
2614 return true;
2615 }
2616
2617 enum class ArrayAccess { Read, Write };
2618
2619 /*
2620 * Returns true if this is a dense array whose properties ending at |endIndex|
2621 * (exclusive) may be accessed (get, set, delete) directly through its
2622 * contiguous vector of elements without fear of getters, setters, etc. along
2623 * the prototype chain, or of enumerators requiring notification of
2624 * modifications.
2625 */
2626 template <ArrayAccess Access>
CanOptimizeForDenseStorage(HandleObject arr,uint64_t endIndex)2627 static bool CanOptimizeForDenseStorage(HandleObject arr, uint64_t endIndex) {
2628 /* If the desired properties overflow dense storage, we can't optimize. */
2629 if (endIndex > UINT32_MAX) {
2630 return false;
2631 }
2632
2633 if (Access == ArrayAccess::Read) {
2634 /*
2635 * Dense storage read access is possible for any packed array as long
2636 * as we only access properties within the initialized length. In all
2637 * other cases we need to ensure there are no other indexed properties
2638 * on this object or on the prototype chain. Callers are required to
2639 * clamp the read length, so it doesn't exceed the initialized length.
2640 */
2641 if (IsPackedArray(arr) &&
2642 endIndex <= arr->as<ArrayObject>().getDenseInitializedLength()) {
2643 return true;
2644 }
2645 return !ObjectMayHaveExtraIndexedProperties(arr);
2646 }
2647
2648 /* There's no optimizing possible if it's not an array. */
2649 if (!arr->is<ArrayObject>()) {
2650 return false;
2651 }
2652
2653 /* If the length is non-writable, always pick the slow path */
2654 if (!arr->as<ArrayObject>().lengthIsWritable()) {
2655 return false;
2656 }
2657
2658 /* Also pick the slow path if the object is non-extensible. */
2659 if (!arr->as<ArrayObject>().isExtensible()) {
2660 return false;
2661 }
2662
2663 /* Also pick the slow path if the object is being iterated over. */
2664 if (arr->as<ArrayObject>().denseElementsMaybeInIteration()) {
2665 return false;
2666 }
2667
2668 /* Or we attempt to write to indices outside the initialized length. */
2669 if (endIndex > arr->as<ArrayObject>().getDenseInitializedLength()) {
2670 return false;
2671 }
2672
2673 /*
2674 * Now watch out for getters and setters along the prototype chain or in
2675 * other indexed properties on the object. Packed arrays don't have any
2676 * other indexed properties by definition.
2677 */
2678 return IsPackedArray(arr) || !ObjectMayHaveExtraIndexedProperties(arr);
2679 }
2680
CopyDenseArrayElements(JSContext * cx,HandleNativeObject obj,uint32_t begin,uint32_t count)2681 static ArrayObject* CopyDenseArrayElements(JSContext* cx,
2682 HandleNativeObject obj,
2683 uint32_t begin, uint32_t count) {
2684 size_t initlen = obj->getDenseInitializedLength();
2685 MOZ_ASSERT(initlen <= UINT32_MAX,
2686 "initialized length shouldn't exceed UINT32_MAX");
2687 uint32_t newlength = 0;
2688 if (initlen > begin) {
2689 newlength = std::min<uint32_t>(initlen - begin, count);
2690 }
2691
2692 ArrayObject* narr = NewDenseFullyAllocatedArray(cx, newlength);
2693 if (!narr) {
2694 return nullptr;
2695 }
2696
2697 MOZ_ASSERT(count >= narr->length());
2698 narr->setLength(count);
2699
2700 if (newlength > 0) {
2701 narr->initDenseElements(obj, begin, newlength);
2702 }
2703
2704 return narr;
2705 }
2706
CopyArrayElements(JSContext * cx,HandleObject obj,uint64_t begin,uint64_t count,HandleArrayObject result)2707 static bool CopyArrayElements(JSContext* cx, HandleObject obj, uint64_t begin,
2708 uint64_t count, HandleArrayObject result) {
2709 MOZ_ASSERT(result->length() == count);
2710
2711 uint64_t startIndex = 0;
2712 RootedValue value(cx);
2713
2714 // Use dense storage for new indexed properties where possible.
2715 {
2716 uint32_t index = 0;
2717 uint32_t limit = std::min<uint32_t>(count, JSID_INT_MAX);
2718 for (; index < limit; index++) {
2719 bool hole;
2720 if (!CheckForInterrupt(cx) ||
2721 !HasAndGetElement(cx, obj, begin + index, &hole, &value)) {
2722 return false;
2723 }
2724
2725 if (!hole) {
2726 DenseElementResult edResult = result->ensureDenseElements(cx, index, 1);
2727 if (edResult != DenseElementResult::Success) {
2728 if (edResult == DenseElementResult::Failure) {
2729 return false;
2730 }
2731
2732 MOZ_ASSERT(edResult == DenseElementResult::Incomplete);
2733 if (!DefineDataElement(cx, result, index, value)) {
2734 return false;
2735 }
2736
2737 break;
2738 }
2739 result->setDenseElement(index, value);
2740 }
2741 }
2742 startIndex = index + 1;
2743 }
2744
2745 // Copy any remaining elements.
2746 for (uint64_t i = startIndex; i < count; i++) {
2747 bool hole;
2748 if (!CheckForInterrupt(cx) ||
2749 !HasAndGetElement(cx, obj, begin + i, &hole, &value)) {
2750 return false;
2751 }
2752
2753 if (!hole && !DefineArrayElement(cx, result, i, value)) {
2754 return false;
2755 }
2756 }
2757 return true;
2758 }
2759
array_splice_impl(JSContext * cx,unsigned argc,Value * vp,bool returnValueIsUsed)2760 static bool array_splice_impl(JSContext* cx, unsigned argc, Value* vp,
2761 bool returnValueIsUsed) {
2762 AutoGeckoProfilerEntry pseudoFrame(
2763 cx, "Array.prototype.splice", JS::ProfilingCategoryPair::JS,
2764 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
2765 CallArgs args = CallArgsFromVp(argc, vp);
2766
2767 /* Step 1. */
2768 RootedObject obj(cx, ToObject(cx, args.thisv()));
2769 if (!obj) {
2770 return false;
2771 }
2772
2773 /* Step 2. */
2774 uint64_t len;
2775 if (!GetLengthPropertyInlined(cx, obj, &len)) {
2776 return false;
2777 }
2778
2779 /* Step 3. */
2780 double relativeStart;
2781 if (!ToInteger(cx, args.get(0), &relativeStart)) {
2782 return false;
2783 }
2784
2785 /* Step 4. */
2786 uint64_t actualStart;
2787 if (relativeStart < 0) {
2788 actualStart = std::max(len + relativeStart, 0.0);
2789 } else {
2790 actualStart = std::min(relativeStart, double(len));
2791 }
2792
2793 /* Step 5. */
2794 uint64_t actualDeleteCount;
2795 if (args.length() == 0) {
2796 /* Step 5.b. */
2797 actualDeleteCount = 0;
2798 } else if (args.length() == 1) {
2799 /* Step 6.b. */
2800 actualDeleteCount = len - actualStart;
2801 } else {
2802 /* Steps 7.b. */
2803 double deleteCountDouble;
2804 if (!ToInteger(cx, args[1], &deleteCountDouble)) {
2805 return false;
2806 }
2807
2808 /* Step 7.c. */
2809 actualDeleteCount =
2810 std::min(std::max(deleteCountDouble, 0.0), double(len - actualStart));
2811
2812 /* Step 8. */
2813 uint32_t insertCount = args.length() - 2;
2814 if (len + insertCount - actualDeleteCount >=
2815 DOUBLE_INTEGRAL_PRECISION_LIMIT) {
2816 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2817 JSMSG_TOO_LONG_ARRAY);
2818 return false;
2819 }
2820 }
2821
2822 MOZ_ASSERT(actualStart + actualDeleteCount <= len);
2823
2824 RootedObject arr(cx);
2825 if (IsArraySpecies(cx, obj)) {
2826 if (actualDeleteCount > UINT32_MAX) {
2827 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2828 JSMSG_BAD_ARRAY_LENGTH);
2829 return false;
2830 }
2831 uint32_t count = uint32_t(actualDeleteCount);
2832
2833 if (CanOptimizeForDenseStorage<ArrayAccess::Read>(obj,
2834 actualStart + count)) {
2835 MOZ_ASSERT(actualStart <= UINT32_MAX,
2836 "if actualStart + count <= UINT32_MAX, then actualStart <= "
2837 "UINT32_MAX");
2838 if (returnValueIsUsed) {
2839 /* Steps 9-12. */
2840 arr = CopyDenseArrayElements(cx, obj.as<NativeObject>(),
2841 uint32_t(actualStart), count);
2842 if (!arr) {
2843 return false;
2844 }
2845 }
2846 } else {
2847 /* Step 9. */
2848 arr = NewDenseFullyAllocatedArray(cx, count);
2849 if (!arr) {
2850 return false;
2851 }
2852
2853 /* Steps 10-11. */
2854 if (!CopyArrayElements(cx, obj, actualStart, count,
2855 arr.as<ArrayObject>())) {
2856 return false;
2857 }
2858
2859 /* Step 12 (implicit). */
2860 }
2861 } else {
2862 /* Steps 9. */
2863 if (!ArraySpeciesCreate(cx, obj, actualDeleteCount, &arr)) {
2864 return false;
2865 }
2866
2867 /* Steps 10, 11, 11.d. */
2868 RootedValue fromValue(cx);
2869 for (uint64_t k = 0; k < actualDeleteCount; k++) {
2870 /* Step 11.a (implicit). */
2871
2872 if (!CheckForInterrupt(cx)) {
2873 return false;
2874 }
2875
2876 /* Steps 11.b, 11.c.i. */
2877 bool hole;
2878 if (!HasAndGetElement(cx, obj, actualStart + k, &hole, &fromValue)) {
2879 return false;
2880 }
2881
2882 /* Step 11.c. */
2883 if (!hole) {
2884 /* Step 11.c.ii. */
2885 if (!DefineArrayElement(cx, arr, k, fromValue)) {
2886 return false;
2887 }
2888 }
2889 }
2890
2891 /* Step 12. */
2892 if (!SetLengthProperty(cx, arr, actualDeleteCount)) {
2893 return false;
2894 }
2895 }
2896
2897 /* Step 14. */
2898 uint32_t itemCount = (args.length() >= 2) ? (args.length() - 2) : 0;
2899 uint64_t finalLength = len - actualDeleteCount + itemCount;
2900
2901 if (itemCount < actualDeleteCount) {
2902 /* Step 15: the array is being shrunk. */
2903 uint64_t sourceIndex = actualStart + actualDeleteCount;
2904 uint64_t targetIndex = actualStart + itemCount;
2905
2906 if (CanOptimizeForDenseStorage<ArrayAccess::Write>(obj, len)) {
2907 MOZ_ASSERT(sourceIndex <= len && targetIndex <= len && len <= UINT32_MAX,
2908 "sourceIndex and targetIndex are uint32 array indices");
2909 MOZ_ASSERT(finalLength < len, "finalLength is strictly less than len");
2910 MOZ_ASSERT(obj->is<NativeObject>());
2911
2912 /* Steps 15.a-b. */
2913 HandleArrayObject arr = obj.as<ArrayObject>();
2914 if (targetIndex != 0 || !arr->tryShiftDenseElements(sourceIndex)) {
2915 arr->moveDenseElements(uint32_t(targetIndex), uint32_t(sourceIndex),
2916 uint32_t(len - sourceIndex));
2917 }
2918
2919 /* Steps 15.c-d. */
2920 SetInitializedLength(cx, arr, finalLength);
2921 } else {
2922 /*
2923 * This is all very slow if the length is very large. We don't yet
2924 * have the ability to iterate in sorted order, so we just do the
2925 * pessimistic thing and let CheckForInterrupt handle the
2926 * fallout.
2927 */
2928
2929 /* Steps 15.a-b. */
2930 RootedValue fromValue(cx);
2931 for (uint64_t from = sourceIndex, to = targetIndex; from < len;
2932 from++, to++) {
2933 /* Steps 15.b.i-ii (implicit). */
2934
2935 if (!CheckForInterrupt(cx)) {
2936 return false;
2937 }
2938
2939 /* Steps 15.b.iii, 15.b.iv.1. */
2940 bool hole;
2941 if (!HasAndGetElement(cx, obj, from, &hole, &fromValue)) {
2942 return false;
2943 }
2944
2945 /* Steps 15.b.iv. */
2946 if (hole) {
2947 /* Steps 15.b.v.1. */
2948 if (!DeletePropertyOrThrow(cx, obj, to)) {
2949 return false;
2950 }
2951 } else {
2952 /* Step 15.b.iv.2. */
2953 if (!SetArrayElement(cx, obj, to, fromValue)) {
2954 return false;
2955 }
2956 }
2957 }
2958
2959 /* Steps 15.c-d. */
2960 if (!DeletePropertiesOrThrow(cx, obj, len, finalLength)) {
2961 return false;
2962 }
2963 }
2964 } else if (itemCount > actualDeleteCount) {
2965 MOZ_ASSERT(actualDeleteCount <= UINT32_MAX);
2966 uint32_t deleteCount = uint32_t(actualDeleteCount);
2967
2968 /* Step 16. */
2969
2970 // Fast path for when we can simply extend and move the dense elements.
2971 auto extendElements = [len, itemCount, deleteCount](JSContext* cx,
2972 HandleObject obj) {
2973 if (!obj->is<ArrayObject>()) {
2974 return DenseElementResult::Incomplete;
2975 }
2976 if (len > UINT32_MAX) {
2977 return DenseElementResult::Incomplete;
2978 }
2979
2980 // Ensure there are no getters/setters or other extra indexed properties.
2981 if (ObjectMayHaveExtraIndexedProperties(obj)) {
2982 return DenseElementResult::Incomplete;
2983 }
2984
2985 // Watch out for arrays with non-writable length or non-extensible arrays.
2986 // In these cases `splice` may have to throw an exception so we let the
2987 // slow path handle it. We also have to ensure we maintain the
2988 // |capacity <= initializedLength| invariant for such objects. See
2989 // NativeObject::shrinkCapacityToInitializedLength.
2990 HandleArrayObject arr = obj.as<ArrayObject>();
2991 if (!arr->lengthIsWritable() || !arr->isExtensible()) {
2992 return DenseElementResult::Incomplete;
2993 }
2994
2995 // Also use the slow path if there might be an active for-in iterator so
2996 // that we don't have to worry about suppressing deleted properties.
2997 if (arr->denseElementsMaybeInIteration()) {
2998 return DenseElementResult::Incomplete;
2999 }
3000
3001 return arr->ensureDenseElements(cx, uint32_t(len),
3002 itemCount - deleteCount);
3003 };
3004
3005 DenseElementResult res = extendElements(cx, obj);
3006 if (res == DenseElementResult::Failure) {
3007 return false;
3008 }
3009 if (res == DenseElementResult::Success) {
3010 MOZ_ASSERT(finalLength <= UINT32_MAX);
3011 MOZ_ASSERT((actualStart + actualDeleteCount) <= len && len <= UINT32_MAX,
3012 "start and deleteCount are uint32 array indices");
3013 MOZ_ASSERT(actualStart + itemCount <= UINT32_MAX,
3014 "can't overflow because |len - actualDeleteCount + itemCount "
3015 "<= UINT32_MAX| "
3016 "and |actualStart <= len - actualDeleteCount| are both true");
3017 uint32_t start = uint32_t(actualStart);
3018 uint32_t length = uint32_t(len);
3019
3020 HandleArrayObject arr = obj.as<ArrayObject>();
3021 arr->moveDenseElements(start + itemCount, start + deleteCount,
3022 length - (start + deleteCount));
3023
3024 /* Steps 16.a-b. */
3025 SetInitializedLength(cx, arr, finalLength);
3026 } else {
3027 MOZ_ASSERT(res == DenseElementResult::Incomplete);
3028
3029 RootedValue fromValue(cx);
3030 for (uint64_t k = len - actualDeleteCount; k > actualStart; k--) {
3031 if (!CheckForInterrupt(cx)) {
3032 return false;
3033 }
3034
3035 /* Step 16.b.i. */
3036 uint64_t from = k + actualDeleteCount - 1;
3037
3038 /* Step 16.b.ii. */
3039 uint64_t to = k + itemCount - 1;
3040
3041 /* Steps 16.b.iii, 16.b.iv.1. */
3042 bool hole;
3043 if (!HasAndGetElement(cx, obj, from, &hole, &fromValue)) {
3044 return false;
3045 }
3046
3047 /* Steps 16.b.iv. */
3048 if (hole) {
3049 /* Step 16.b.v.1. */
3050 if (!DeletePropertyOrThrow(cx, obj, to)) {
3051 return false;
3052 }
3053 } else {
3054 /* Step 16.b.iv.2. */
3055 if (!SetArrayElement(cx, obj, to, fromValue)) {
3056 return false;
3057 }
3058 }
3059 }
3060 }
3061 }
3062
3063 /* Step 13 (reordered). */
3064 Value* items = args.array() + 2;
3065
3066 /* Steps 17-18. */
3067 if (!SetArrayElements(cx, obj, actualStart, itemCount, items)) {
3068 return false;
3069 }
3070
3071 /* Step 19. */
3072 if (!SetLengthProperty(cx, obj, finalLength)) {
3073 return false;
3074 }
3075
3076 /* Step 20. */
3077 if (returnValueIsUsed) {
3078 args.rval().setObject(*arr);
3079 }
3080
3081 return true;
3082 }
3083
3084 /* ES 2016 draft Mar 25, 2016 22.1.3.26. */
array_splice(JSContext * cx,unsigned argc,Value * vp)3085 static bool array_splice(JSContext* cx, unsigned argc, Value* vp) {
3086 return array_splice_impl(cx, argc, vp, true);
3087 }
3088
array_splice_noRetVal(JSContext * cx,unsigned argc,Value * vp)3089 static bool array_splice_noRetVal(JSContext* cx, unsigned argc, Value* vp) {
3090 return array_splice_impl(cx, argc, vp, false);
3091 }
3092
3093 struct SortComparatorIndexes {
operator ()SortComparatorIndexes3094 bool operator()(uint32_t a, uint32_t b, bool* lessOrEqualp) {
3095 *lessOrEqualp = (a <= b);
3096 return true;
3097 }
3098 };
3099
3100 // Returns all indexed properties in the range [begin, end) found on |obj| or
3101 // its proto chain. This function does not handle proxies, objects with
3102 // resolve/lookupProperty hooks or indexed getters, as those can introduce
3103 // new properties. In those cases, *success is set to |false|.
GetIndexedPropertiesInRange(JSContext * cx,HandleObject obj,uint64_t begin,uint64_t end,Vector<uint32_t> & indexes,bool * success)3104 static bool GetIndexedPropertiesInRange(JSContext* cx, HandleObject obj,
3105 uint64_t begin, uint64_t end,
3106 Vector<uint32_t>& indexes,
3107 bool* success) {
3108 *success = false;
3109
3110 // TODO: Add IdIsIndex with support for large indices.
3111 if (end > UINT32_MAX) {
3112 return true;
3113 }
3114 MOZ_ASSERT(begin <= UINT32_MAX);
3115
3116 // First, look for proxies or class hooks that can introduce extra
3117 // properties.
3118 JSObject* pobj = obj;
3119 do {
3120 if (!pobj->is<NativeObject>() || pobj->getClass()->getResolve() ||
3121 pobj->getOpsLookupProperty()) {
3122 return true;
3123 }
3124 } while ((pobj = pobj->staticPrototype()));
3125
3126 // Collect indexed property names.
3127 pobj = obj;
3128 do {
3129 // Append dense elements.
3130 NativeObject* nativeObj = &pobj->as<NativeObject>();
3131 uint32_t initLen = nativeObj->getDenseInitializedLength();
3132 for (uint32_t i = begin; i < initLen && i < end; i++) {
3133 if (nativeObj->getDenseElement(i).isMagic(JS_ELEMENTS_HOLE)) {
3134 continue;
3135 }
3136 if (!indexes.append(i)) {
3137 return false;
3138 }
3139 }
3140
3141 // Append typed array elements.
3142 if (nativeObj->is<TypedArrayObject>()) {
3143 size_t len = nativeObj->as<TypedArrayObject>().length();
3144 for (uint32_t i = begin; i < len && i < end; i++) {
3145 if (!indexes.append(i)) {
3146 return false;
3147 }
3148 }
3149 }
3150
3151 // Append sparse elements.
3152 if (nativeObj->isIndexed()) {
3153 ShapePropertyIter<NoGC> iter(nativeObj->shape());
3154 for (; !iter.done(); iter++) {
3155 jsid id = iter->key();
3156 uint32_t i;
3157 if (!IdIsIndex(id, &i)) {
3158 continue;
3159 }
3160
3161 if (!(begin <= i && i < end)) {
3162 continue;
3163 }
3164
3165 // Watch out for getters, they can add new properties.
3166 if (!iter->isDataProperty()) {
3167 return true;
3168 }
3169
3170 if (!indexes.append(i)) {
3171 return false;
3172 }
3173 }
3174 }
3175 } while ((pobj = pobj->staticPrototype()));
3176
3177 // Sort the indexes.
3178 Vector<uint32_t> tmp(cx);
3179 size_t n = indexes.length();
3180 if (!tmp.resize(n)) {
3181 return false;
3182 }
3183 if (!MergeSort(indexes.begin(), n, tmp.begin(), SortComparatorIndexes())) {
3184 return false;
3185 }
3186
3187 // Remove duplicates.
3188 if (!indexes.empty()) {
3189 uint32_t last = 0;
3190 for (size_t i = 1, len = indexes.length(); i < len; i++) {
3191 uint32_t elem = indexes[i];
3192 if (indexes[last] != elem) {
3193 last++;
3194 indexes[last] = elem;
3195 }
3196 }
3197 if (!indexes.resize(last + 1)) {
3198 return false;
3199 }
3200 }
3201
3202 *success = true;
3203 return true;
3204 }
3205
SliceSparse(JSContext * cx,HandleObject obj,uint64_t begin,uint64_t end,HandleArrayObject result)3206 static bool SliceSparse(JSContext* cx, HandleObject obj, uint64_t begin,
3207 uint64_t end, HandleArrayObject result) {
3208 MOZ_ASSERT(begin <= end);
3209
3210 Vector<uint32_t> indexes(cx);
3211 bool success;
3212 if (!GetIndexedPropertiesInRange(cx, obj, begin, end, indexes, &success)) {
3213 return false;
3214 }
3215
3216 if (!success) {
3217 return CopyArrayElements(cx, obj, begin, end - begin, result);
3218 }
3219
3220 MOZ_ASSERT(end <= UINT32_MAX,
3221 "indices larger than UINT32_MAX should be rejected by "
3222 "GetIndexedPropertiesInRange");
3223
3224 RootedValue value(cx);
3225 for (uint32_t index : indexes) {
3226 MOZ_ASSERT(begin <= index && index < end);
3227
3228 bool hole;
3229 if (!HasAndGetElement(cx, obj, index, &hole, &value)) {
3230 return false;
3231 }
3232
3233 if (!hole &&
3234 !DefineDataElement(cx, result, index - uint32_t(begin), value)) {
3235 return false;
3236 }
3237 }
3238
3239 return true;
3240 }
3241
SliceArguments(JSContext * cx,Handle<ArgumentsObject * > argsobj,uint32_t begin,uint32_t count)3242 static JSObject* SliceArguments(JSContext* cx, Handle<ArgumentsObject*> argsobj,
3243 uint32_t begin, uint32_t count) {
3244 MOZ_ASSERT(!argsobj->hasOverriddenLength() &&
3245 !argsobj->isAnyElementDeleted());
3246 MOZ_ASSERT(begin + count <= argsobj->initialLength());
3247
3248 ArrayObject* result = NewDenseFullyAllocatedArray(cx, count);
3249 if (!result) {
3250 return nullptr;
3251 }
3252 result->setDenseInitializedLength(count);
3253
3254 for (uint32_t index = 0; index < count; index++) {
3255 const Value& v = argsobj->element(begin + index);
3256 result->initDenseElement(index, v);
3257 }
3258 return result;
3259 }
3260
3261 template <typename T, typename ArrayLength>
NormalizeSliceTerm(T value,ArrayLength length)3262 static inline ArrayLength NormalizeSliceTerm(T value, ArrayLength length) {
3263 if (value < 0) {
3264 value += length;
3265 if (value < 0) {
3266 return 0;
3267 }
3268 } else if (double(value) > double(length)) {
3269 return length;
3270 }
3271 return ArrayLength(value);
3272 }
3273
ArraySliceOrdinary(JSContext * cx,HandleObject obj,uint64_t begin,uint64_t end,MutableHandleValue rval)3274 static bool ArraySliceOrdinary(JSContext* cx, HandleObject obj, uint64_t begin,
3275 uint64_t end, MutableHandleValue rval) {
3276 if (begin > end) {
3277 begin = end;
3278 }
3279
3280 if ((end - begin) > UINT32_MAX) {
3281 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3282 JSMSG_BAD_ARRAY_LENGTH);
3283 return false;
3284 }
3285 uint32_t count = uint32_t(end - begin);
3286
3287 if (CanOptimizeForDenseStorage<ArrayAccess::Read>(obj, end)) {
3288 MOZ_ASSERT(begin <= UINT32_MAX,
3289 "if end <= UINT32_MAX, then begin <= UINT32_MAX");
3290 JSObject* narr = CopyDenseArrayElements(cx, obj.as<NativeObject>(),
3291 uint32_t(begin), count);
3292 if (!narr) {
3293 return false;
3294 }
3295
3296 rval.setObject(*narr);
3297 return true;
3298 }
3299
3300 if (obj->is<ArgumentsObject>()) {
3301 Handle<ArgumentsObject*> argsobj = obj.as<ArgumentsObject>();
3302 if (!argsobj->hasOverriddenLength() && !argsobj->isAnyElementDeleted()) {
3303 MOZ_ASSERT(begin <= UINT32_MAX, "begin is limited by |argsobj|'s length");
3304 JSObject* narr = SliceArguments(cx, argsobj, uint32_t(begin), count);
3305 if (!narr) {
3306 return false;
3307 }
3308
3309 rval.setObject(*narr);
3310 return true;
3311 }
3312 }
3313
3314 RootedArrayObject narr(cx, NewDensePartlyAllocatedArray(cx, count));
3315 if (!narr) {
3316 return false;
3317 }
3318
3319 if (end <= UINT32_MAX) {
3320 if (js::GetElementsOp op = obj->getOpsGetElements()) {
3321 ElementAdder adder(cx, narr, count,
3322 ElementAdder::CheckHasElemPreserveHoles);
3323 if (!op(cx, obj, uint32_t(begin), uint32_t(end), &adder)) {
3324 return false;
3325 }
3326
3327 rval.setObject(*narr);
3328 return true;
3329 }
3330 }
3331
3332 if (obj->is<NativeObject>() && obj->as<NativeObject>().isIndexed() &&
3333 count > 1000) {
3334 if (!SliceSparse(cx, obj, begin, end, narr)) {
3335 return false;
3336 }
3337 } else {
3338 if (!CopyArrayElements(cx, obj, begin, count, narr)) {
3339 return false;
3340 }
3341 }
3342
3343 rval.setObject(*narr);
3344 return true;
3345 }
3346
3347 /* ES 2016 draft Mar 25, 2016 22.1.3.23. */
array_slice(JSContext * cx,unsigned argc,Value * vp)3348 bool js::array_slice(JSContext* cx, unsigned argc, Value* vp) {
3349 AutoGeckoProfilerEntry pseudoFrame(
3350 cx, "Array.prototype.slice", JS::ProfilingCategoryPair::JS,
3351 uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
3352 CallArgs args = CallArgsFromVp(argc, vp);
3353
3354 /* Step 1. */
3355 RootedObject obj(cx, ToObject(cx, args.thisv()));
3356 if (!obj) {
3357 return false;
3358 }
3359
3360 /* Step 2. */
3361 uint64_t length;
3362 if (!GetLengthPropertyInlined(cx, obj, &length)) {
3363 return false;
3364 }
3365
3366 uint64_t k = 0;
3367 uint64_t final = length;
3368 if (args.length() > 0) {
3369 double d;
3370 /* Step 3. */
3371 if (!ToInteger(cx, args[0], &d)) {
3372 return false;
3373 }
3374
3375 /* Step 4. */
3376 k = NormalizeSliceTerm(d, length);
3377
3378 if (args.hasDefined(1)) {
3379 /* Step 5. */
3380 if (!ToInteger(cx, args[1], &d)) {
3381 return false;
3382 }
3383
3384 /* Step 6. */
3385 final = NormalizeSliceTerm(d, length);
3386 }
3387 }
3388
3389 if (IsArraySpecies(cx, obj)) {
3390 /* Steps 7-12: Optimized for ordinary array. */
3391 return ArraySliceOrdinary(cx, obj, k, final, args.rval());
3392 }
3393
3394 /* Step 7. */
3395 uint64_t count = final > k ? final - k : 0;
3396
3397 /* Step 8. */
3398 RootedObject arr(cx);
3399 if (!ArraySpeciesCreate(cx, obj, count, &arr)) {
3400 return false;
3401 }
3402
3403 /* Step 9. */
3404 uint64_t n = 0;
3405
3406 /* Step 10. */
3407 RootedValue kValue(cx);
3408 while (k < final) {
3409 if (!CheckForInterrupt(cx)) {
3410 return false;
3411 }
3412
3413 /* Steps 10.a-b, and 10.c.i. */
3414 bool kNotPresent;
3415 if (!HasAndGetElement(cx, obj, k, &kNotPresent, &kValue)) {
3416 return false;
3417 }
3418
3419 /* Step 10.c. */
3420 if (!kNotPresent) {
3421 /* Steps 10.c.ii. */
3422 if (!DefineArrayElement(cx, arr, n, kValue)) {
3423 return false;
3424 }
3425 }
3426 /* Step 10.d. */
3427 k++;
3428
3429 /* Step 10.e. */
3430 n++;
3431 }
3432
3433 /* Step 11. */
3434 if (!SetLengthProperty(cx, arr, n)) {
3435 return false;
3436 }
3437
3438 /* Step 12. */
3439 args.rval().setObject(*arr);
3440 return true;
3441 }
3442
ArraySliceDenseKernel(JSContext * cx,ArrayObject * arr,int32_t beginArg,int32_t endArg,ArrayObject * result)3443 static bool ArraySliceDenseKernel(JSContext* cx, ArrayObject* arr,
3444 int32_t beginArg, int32_t endArg,
3445 ArrayObject* result) {
3446 uint32_t length = arr->length();
3447
3448 uint32_t begin = NormalizeSliceTerm(beginArg, length);
3449 uint32_t end = NormalizeSliceTerm(endArg, length);
3450
3451 if (begin > end) {
3452 begin = end;
3453 }
3454
3455 uint32_t count = end - begin;
3456 size_t initlen = arr->getDenseInitializedLength();
3457 if (initlen > begin) {
3458 uint32_t newlength = std::min<uint32_t>(initlen - begin, count);
3459 if (newlength > 0) {
3460 if (!result->ensureElements(cx, newlength)) {
3461 return false;
3462 }
3463 result->initDenseElements(arr, begin, newlength);
3464 }
3465 }
3466
3467 MOZ_ASSERT(count >= result->length());
3468 result->setLength(count);
3469
3470 return true;
3471 }
3472
ArraySliceDense(JSContext * cx,HandleObject obj,int32_t begin,int32_t end,HandleObject result)3473 JSObject* js::ArraySliceDense(JSContext* cx, HandleObject obj, int32_t begin,
3474 int32_t end, HandleObject result) {
3475 MOZ_ASSERT(IsPackedArray(obj));
3476
3477 if (result && IsArraySpecies(cx, obj)) {
3478 if (!ArraySliceDenseKernel(cx, &obj->as<ArrayObject>(), begin, end,
3479 &result->as<ArrayObject>())) {
3480 return nullptr;
3481 }
3482 return result;
3483 }
3484
3485 // Slower path if the JIT wasn't able to allocate an object inline.
3486 JS::RootedValueArray<4> argv(cx);
3487 argv[0].setUndefined();
3488 argv[1].setObject(*obj);
3489 argv[2].setInt32(begin);
3490 argv[3].setInt32(end);
3491 if (!array_slice(cx, 2, argv.begin())) {
3492 return nullptr;
3493 }
3494 return &argv[0].toObject();
3495 }
3496
array_isArray(JSContext * cx,unsigned argc,Value * vp)3497 static bool array_isArray(JSContext* cx, unsigned argc, Value* vp) {
3498 CallArgs args = CallArgsFromVp(argc, vp);
3499 bool isArray = false;
3500 if (args.get(0).isObject()) {
3501 RootedObject obj(cx, &args[0].toObject());
3502 if (!IsArray(cx, obj, &isArray)) {
3503 return false;
3504 }
3505 }
3506 args.rval().setBoolean(isArray);
3507 return true;
3508 }
3509
ArrayFromCallArgs(JSContext * cx,CallArgs & args,HandleObject proto=nullptr)3510 static bool ArrayFromCallArgs(JSContext* cx, CallArgs& args,
3511 HandleObject proto = nullptr) {
3512 ArrayObject* obj =
3513 NewDenseCopiedArray(cx, args.length(), args.array(), proto);
3514 if (!obj) {
3515 return false;
3516 }
3517
3518 args.rval().setObject(*obj);
3519 return true;
3520 }
3521
array_of(JSContext * cx,unsigned argc,Value * vp)3522 static bool array_of(JSContext* cx, unsigned argc, Value* vp) {
3523 CallArgs args = CallArgsFromVp(argc, vp);
3524
3525 bool isArrayConstructor =
3526 IsArrayConstructor(args.thisv()) &&
3527 args.thisv().toObject().nonCCWRealm() == cx->realm();
3528
3529 if (isArrayConstructor || !IsConstructor(args.thisv())) {
3530 // isArrayConstructor will usually be true in practice. This is the most
3531 // common path.
3532 return ArrayFromCallArgs(cx, args);
3533 }
3534
3535 // Step 4.
3536 RootedObject obj(cx);
3537 {
3538 FixedConstructArgs<1> cargs(cx);
3539
3540 cargs[0].setNumber(args.length());
3541
3542 if (!Construct(cx, args.thisv(), cargs, args.thisv(), &obj)) {
3543 return false;
3544 }
3545 }
3546
3547 // Step 8.
3548 for (unsigned k = 0; k < args.length(); k++) {
3549 if (!DefineDataElement(cx, obj, k, args[k])) {
3550 return false;
3551 }
3552 }
3553
3554 // Steps 9-10.
3555 if (!SetLengthProperty(cx, obj, args.length())) {
3556 return false;
3557 }
3558
3559 // Step 11.
3560 args.rval().setObject(*obj);
3561 return true;
3562 }
3563
3564 static const JSJitInfo array_splice_info = {
3565 {(JSJitGetterOp)array_splice_noRetVal},
3566 {0}, /* unused */
3567 {0}, /* unused */
3568 JSJitInfo::IgnoresReturnValueNative,
3569 JSJitInfo::AliasEverything,
3570 JSVAL_TYPE_UNDEFINED,
3571 };
3572
3573 static const JSFunctionSpec array_methods[] = {
3574 JS_FN(js_toSource_str, array_toSource, 0, 0),
3575 JS_SELF_HOSTED_FN(js_toString_str, "ArrayToString", 0, 0),
3576 JS_FN(js_toLocaleString_str, array_toLocaleString, 0, 0),
3577
3578 /* Perl-ish methods. */
3579 JS_INLINABLE_FN("join", array_join, 1, 0, ArrayJoin),
3580 JS_FN("reverse", array_reverse, 0, 0),
3581 JS_SELF_HOSTED_FN("sort", "ArraySort", 1, 0),
3582 JS_INLINABLE_FN("push", array_push, 1, 0, ArrayPush),
3583 JS_INLINABLE_FN("pop", array_pop, 0, 0, ArrayPop),
3584 JS_INLINABLE_FN("shift", array_shift, 0, 0, ArrayShift),
3585 JS_FN("unshift", array_unshift, 1, 0),
3586 JS_FNINFO("splice", array_splice, &array_splice_info, 2, 0),
3587
3588 /* Pythonic sequence methods. */
3589 JS_SELF_HOSTED_FN("concat", "ArrayConcat", 1, 0),
3590 JS_INLINABLE_FN("slice", array_slice, 2, 0, ArraySlice),
3591
3592 JS_SELF_HOSTED_FN("lastIndexOf", "ArrayLastIndexOf", 1, 0),
3593 JS_SELF_HOSTED_FN("indexOf", "ArrayIndexOf", 1, 0),
3594 JS_SELF_HOSTED_FN("forEach", "ArrayForEach", 1, 0),
3595 JS_SELF_HOSTED_FN("map", "ArrayMap", 1, 0),
3596 JS_SELF_HOSTED_FN("filter", "ArrayFilter", 1, 0),
3597 JS_SELF_HOSTED_FN("reduce", "ArrayReduce", 1, 0),
3598 JS_SELF_HOSTED_FN("reduceRight", "ArrayReduceRight", 1, 0),
3599 JS_SELF_HOSTED_FN("some", "ArraySome", 1, 0),
3600 JS_SELF_HOSTED_FN("every", "ArrayEvery", 1, 0),
3601
3602 /* ES6 additions */
3603 JS_SELF_HOSTED_FN("find", "ArrayFind", 1, 0),
3604 JS_SELF_HOSTED_FN("findIndex", "ArrayFindIndex", 1, 0),
3605 JS_SELF_HOSTED_FN("copyWithin", "ArrayCopyWithin", 3, 0),
3606
3607 JS_SELF_HOSTED_FN("fill", "ArrayFill", 3, 0),
3608
3609 JS_SELF_HOSTED_SYM_FN(iterator, "$ArrayValues", 0, 0),
3610 JS_SELF_HOSTED_FN("entries", "ArrayEntries", 0, 0),
3611 JS_SELF_HOSTED_FN("keys", "ArrayKeys", 0, 0),
3612 JS_SELF_HOSTED_FN("values", "$ArrayValues", 0, 0),
3613
3614 /* ES7 additions */
3615 JS_SELF_HOSTED_FN("includes", "ArrayIncludes", 2, 0),
3616
3617 /* ES2020 */
3618 JS_SELF_HOSTED_FN("flatMap", "ArrayFlatMap", 1, 0),
3619 JS_SELF_HOSTED_FN("flat", "ArrayFlat", 0, 0),
3620
3621 /* Proposal */
3622 JS_SELF_HOSTED_FN("at", "ArrayAt", 1, 0),
3623
3624 JS_FS_END};
3625
3626 static const JSFunctionSpec array_static_methods[] = {
3627 JS_INLINABLE_FN("isArray", array_isArray, 1, 0, ArrayIsArray),
3628 JS_SELF_HOSTED_FN("from", "ArrayFrom", 3, 0), JS_FN("of", array_of, 0, 0),
3629
3630 JS_FS_END};
3631
3632 const JSPropertySpec array_static_props[] = {
3633 JS_SELF_HOSTED_SYM_GET(species, "$ArraySpecies", 0), JS_PS_END};
3634
ArrayConstructorImpl(JSContext * cx,CallArgs & args,bool isConstructor)3635 static inline bool ArrayConstructorImpl(JSContext* cx, CallArgs& args,
3636 bool isConstructor) {
3637 RootedObject proto(cx);
3638 if (isConstructor) {
3639 if (!GetPrototypeFromBuiltinConstructor(cx, args, JSProto_Array, &proto)) {
3640 return false;
3641 }
3642 } else {
3643 // We're emulating |new Array(n)| with |std_Array(n)| in self-hosted JS,
3644 // and the proto should be %ArrayPrototype% regardless of the callee.
3645 proto = GlobalObject::getOrCreateArrayPrototype(cx, cx->global());
3646 if (!proto) {
3647 return false;
3648 }
3649 }
3650
3651 if (args.length() != 1 || !args[0].isNumber()) {
3652 return ArrayFromCallArgs(cx, args, proto);
3653 }
3654
3655 uint32_t length;
3656 if (args[0].isInt32()) {
3657 int32_t i = args[0].toInt32();
3658 if (i < 0) {
3659 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3660 JSMSG_BAD_ARRAY_LENGTH);
3661 return false;
3662 }
3663 length = uint32_t(i);
3664 } else {
3665 double d = args[0].toDouble();
3666 length = ToUint32(d);
3667 if (d != double(length)) {
3668 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3669 JSMSG_BAD_ARRAY_LENGTH);
3670 return false;
3671 }
3672 }
3673
3674 ArrayObject* obj = NewDensePartlyAllocatedArray(cx, length, proto);
3675 if (!obj) {
3676 return false;
3677 }
3678
3679 args.rval().setObject(*obj);
3680 return true;
3681 }
3682
3683 /* ES5 15.4.2 */
ArrayConstructor(JSContext * cx,unsigned argc,Value * vp)3684 bool js::ArrayConstructor(JSContext* cx, unsigned argc, Value* vp) {
3685 CallArgs args = CallArgsFromVp(argc, vp);
3686 return ArrayConstructorImpl(cx, args, /* isConstructor = */ true);
3687 }
3688
array_construct(JSContext * cx,unsigned argc,Value * vp)3689 bool js::array_construct(JSContext* cx, unsigned argc, Value* vp) {
3690 CallArgs args = CallArgsFromVp(argc, vp);
3691 MOZ_ASSERT(!args.isConstructing());
3692 MOZ_ASSERT(args.length() == 1);
3693 MOZ_ASSERT(args[0].isNumber());
3694 return ArrayConstructorImpl(cx, args, /* isConstructor = */ false);
3695 }
3696
ArrayConstructorOneArg(JSContext * cx,HandleArrayObject templateObject,int32_t lengthInt)3697 ArrayObject* js::ArrayConstructorOneArg(JSContext* cx,
3698 HandleArrayObject templateObject,
3699 int32_t lengthInt) {
3700 // JIT code can call this with a template object from a different realm when
3701 // calling another realm's Array constructor.
3702 Maybe<AutoRealm> ar;
3703 if (cx->realm() != templateObject->realm()) {
3704 MOZ_ASSERT(cx->compartment() == templateObject->compartment());
3705 ar.emplace(cx, templateObject);
3706 }
3707
3708 if (lengthInt < 0) {
3709 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3710 JSMSG_BAD_ARRAY_LENGTH);
3711 return nullptr;
3712 }
3713
3714 uint32_t length = uint32_t(lengthInt);
3715 ArrayObject* res = NewDensePartlyAllocatedArray(cx, length);
3716 MOZ_ASSERT_IF(res, res->realm() == templateObject->realm());
3717 return res;
3718 }
3719
CreateArrayPrototype(JSContext * cx,JSProtoKey key)3720 static JSObject* CreateArrayPrototype(JSContext* cx, JSProtoKey key) {
3721 MOZ_ASSERT(key == JSProto_Array);
3722 RootedObject proto(
3723 cx, GlobalObject::getOrCreateObjectPrototype(cx, cx->global()));
3724 if (!proto) {
3725 return nullptr;
3726 }
3727
3728 RootedShape shape(cx, SharedShape::getInitialShape(
3729 cx, &ArrayObject::class_, cx->realm(),
3730 TaggedProto(proto), gc::AllocKind::OBJECT0));
3731 if (!shape) {
3732 return nullptr;
3733 }
3734
3735 AutoSetNewObjectMetadata metadata(cx);
3736 RootedArrayObject arrayProto(
3737 cx, ArrayObject::createArray(cx, gc::AllocKind::OBJECT4, gc::TenuredHeap,
3738 shape, 0, metadata));
3739 if (!arrayProto || !AddLengthProperty(cx, arrayProto)) {
3740 return nullptr;
3741 }
3742
3743 return arrayProto;
3744 }
3745
array_proto_finish(JSContext * cx,JS::HandleObject ctor,JS::HandleObject proto)3746 static bool array_proto_finish(JSContext* cx, JS::HandleObject ctor,
3747 JS::HandleObject proto) {
3748 // Add Array.prototype[@@unscopables]. ECMA-262 draft (2016 Mar 19) 22.1.3.32.
3749 RootedObject unscopables(
3750 cx, NewTenuredObjectWithGivenProto<PlainObject>(cx, nullptr));
3751 if (!unscopables) {
3752 return false;
3753 }
3754
3755 RootedValue value(cx, BooleanValue(true));
3756 if (!DefineDataProperty(cx, unscopables, cx->names().at, value) ||
3757 !DefineDataProperty(cx, unscopables, cx->names().copyWithin, value) ||
3758 !DefineDataProperty(cx, unscopables, cx->names().entries, value) ||
3759 !DefineDataProperty(cx, unscopables, cx->names().fill, value) ||
3760 !DefineDataProperty(cx, unscopables, cx->names().find, value) ||
3761 !DefineDataProperty(cx, unscopables, cx->names().findIndex, value) ||
3762 !DefineDataProperty(cx, unscopables, cx->names().flat, value) ||
3763 !DefineDataProperty(cx, unscopables, cx->names().flatMap, value) ||
3764 !DefineDataProperty(cx, unscopables, cx->names().includes, value) ||
3765 !DefineDataProperty(cx, unscopables, cx->names().keys, value) ||
3766 !DefineDataProperty(cx, unscopables, cx->names().values, value)) {
3767 return false;
3768 }
3769
3770 RootedId id(cx, SYMBOL_TO_JSID(
3771 cx->wellKnownSymbols().get(JS::SymbolCode::unscopables)));
3772 value.setObject(*unscopables);
3773 return DefineDataProperty(cx, proto, id, value, JSPROP_READONLY);
3774 }
3775
3776 static const JSClassOps ArrayObjectClassOps = {
3777 array_addProperty, // addProperty
3778 nullptr, // delProperty
3779 nullptr, // enumerate
3780 nullptr, // newEnumerate
3781 nullptr, // resolve
3782 nullptr, // mayResolve
3783 nullptr, // finalize
3784 nullptr, // call
3785 nullptr, // hasInstance
3786 nullptr, // construct
3787 nullptr, // trace
3788 };
3789
3790 static const ClassSpec ArrayObjectClassSpec = {
3791 GenericCreateConstructor<ArrayConstructor, 1, gc::AllocKind::FUNCTION,
3792 &jit::JitInfo_Array>,
3793 CreateArrayPrototype,
3794 array_static_methods,
3795 array_static_props,
3796 array_methods,
3797 nullptr,
3798 array_proto_finish};
3799
3800 const JSClass ArrayObject::class_ = {
3801 "Array",
3802 JSCLASS_HAS_CACHED_PROTO(JSProto_Array) | JSCLASS_DELAY_METADATA_BUILDER,
3803 &ArrayObjectClassOps, &ArrayObjectClassSpec};
3804
3805 /*
3806 * Array allocation functions.
3807 */
3808
EnsureNewArrayElements(JSContext * cx,ArrayObject * obj,uint32_t length)3809 static inline bool EnsureNewArrayElements(JSContext* cx, ArrayObject* obj,
3810 uint32_t length) {
3811 /*
3812 * If ensureElements creates dynamically allocated slots, then having
3813 * fixedSlots is a waste.
3814 */
3815 DebugOnly<uint32_t> cap = obj->getDenseCapacity();
3816
3817 if (!obj->ensureElements(cx, length)) {
3818 return false;
3819 }
3820
3821 MOZ_ASSERT_IF(cap, !obj->hasDynamicElements());
3822
3823 return true;
3824 }
3825
3826 template <uint32_t maxLength>
NewArray(JSContext * cx,uint32_t length,HandleObject protoArg,NewObjectKind newKind,gc::AllocSite * site=nullptr)3827 static MOZ_ALWAYS_INLINE ArrayObject* NewArray(JSContext* cx, uint32_t length,
3828 HandleObject protoArg,
3829 NewObjectKind newKind,
3830 gc::AllocSite* site = nullptr) {
3831 gc::AllocKind allocKind = GuessArrayGCKind(length);
3832 MOZ_ASSERT(CanChangeToBackgroundAllocKind(allocKind, &ArrayObject::class_));
3833 allocKind = ForegroundToBackgroundAllocKind(allocKind);
3834
3835 RootedObject proto(cx, protoArg);
3836 if (!proto) {
3837 proto = GlobalObject::getOrCreateArrayPrototype(cx, cx->global());
3838 if (!proto) {
3839 return nullptr;
3840 }
3841 }
3842
3843 Rooted<TaggedProto> taggedProto(cx, TaggedProto(proto));
3844 bool isCachable = NewObjectWithTaggedProtoIsCachable(cx, taggedProto, newKind,
3845 &ArrayObject::class_);
3846 if (isCachable) {
3847 NewObjectCache& cache = cx->caches().newObjectCache;
3848 NewObjectCache::EntryIndex entry = -1;
3849 if (cache.lookupProto(&ArrayObject::class_, proto, allocKind, &entry)) {
3850 gc::InitialHeap heap =
3851 GetInitialHeap(newKind, &ArrayObject::class_, site);
3852 AutoSetNewObjectMetadata metadata(cx);
3853 JSObject* obj = cache.newObjectFromHit(cx, entry, heap, site);
3854 if (obj) {
3855 /* Fixup the elements pointer and length, which may be incorrect. */
3856 ArrayObject* arr = &obj->as<ArrayObject>();
3857 arr->setFixedElements();
3858 arr->setLength(length);
3859 if (maxLength > 0 &&
3860 !EnsureNewArrayElements(cx, arr, std::min(maxLength, length))) {
3861 return nullptr;
3862 }
3863 return arr;
3864 }
3865 }
3866 }
3867
3868 /*
3869 * Get a shape with zero fixed slots, regardless of the size class.
3870 * See JSObject::createArray.
3871 */
3872 RootedShape shape(cx, SharedShape::getInitialShape(
3873 cx, &ArrayObject::class_, cx->realm(),
3874 TaggedProto(proto), gc::AllocKind::OBJECT0));
3875 if (!shape) {
3876 return nullptr;
3877 }
3878
3879 AutoSetNewObjectMetadata metadata(cx);
3880 RootedArrayObject arr(
3881 cx,
3882 ArrayObject::createArray(
3883 cx, allocKind, GetInitialHeap(newKind, &ArrayObject::class_, site),
3884 shape, length, metadata));
3885 if (!arr) {
3886 return nullptr;
3887 }
3888
3889 if (arr->empty()) {
3890 if (!AddLengthProperty(cx, arr)) {
3891 return nullptr;
3892 }
3893 shape = arr->shape();
3894 SharedShape::insertInitialShape(cx, shape);
3895 if (proto == cx->global()->maybeGetArrayPrototype()) {
3896 cx->global()->setArrayShape(shape);
3897 }
3898 }
3899
3900 if (isCachable) {
3901 NewObjectCache& cache = cx->caches().newObjectCache;
3902 NewObjectCache::EntryIndex entry = -1;
3903 cache.lookupProto(&ArrayObject::class_, proto, allocKind, &entry);
3904 cache.fillProto(entry, &ArrayObject::class_, taggedProto, allocKind, arr);
3905 }
3906
3907 if (maxLength > 0 &&
3908 !EnsureNewArrayElements(cx, arr, std::min(maxLength, length))) {
3909 return nullptr;
3910 }
3911
3912 probes::CreateObject(cx, arr);
3913 return arr;
3914 }
3915
NewDenseEmptyArray(JSContext * cx,HandleObject proto)3916 ArrayObject* js::NewDenseEmptyArray(JSContext* cx,
3917 HandleObject proto /* = nullptr */) {
3918 return NewArray<0>(cx, 0, proto, GenericObject);
3919 }
3920
NewTenuredDenseEmptyArray(JSContext * cx,HandleObject proto)3921 ArrayObject* js::NewTenuredDenseEmptyArray(JSContext* cx,
3922 HandleObject proto /* = nullptr */) {
3923 return NewArray<0>(cx, 0, proto, TenuredObject);
3924 }
3925
NewDenseFullyAllocatedArray(JSContext * cx,uint32_t length,HandleObject proto,NewObjectKind newKind,gc::AllocSite * site)3926 ArrayObject* js::NewDenseFullyAllocatedArray(
3927 JSContext* cx, uint32_t length, HandleObject proto /* = nullptr */,
3928 NewObjectKind newKind /* = GenericObject */,
3929 gc::AllocSite* site /* = nullptr */) {
3930 return NewArray<UINT32_MAX>(cx, length, proto, newKind, site);
3931 }
3932
NewDensePartlyAllocatedArray(JSContext * cx,uint32_t length,HandleObject proto,NewObjectKind newKind)3933 ArrayObject* js::NewDensePartlyAllocatedArray(
3934 JSContext* cx, uint32_t length, HandleObject proto /* = nullptr */,
3935 NewObjectKind newKind /* = GenericObject */) {
3936 return NewArray<ArrayObject::EagerAllocationMaxLength>(cx, length, proto,
3937 newKind);
3938 }
3939
NewDenseUnallocatedArray(JSContext * cx,uint32_t length,HandleObject proto,NewObjectKind newKind)3940 ArrayObject* js::NewDenseUnallocatedArray(
3941 JSContext* cx, uint32_t length, HandleObject proto /* = nullptr */,
3942 NewObjectKind newKind /* = GenericObject */) {
3943 return NewArray<0>(cx, length, proto, newKind);
3944 }
3945
3946 // values must point at already-rooted Value objects
NewDenseCopiedArray(JSContext * cx,uint32_t length,const Value * values,HandleObject proto,NewObjectKind newKind)3947 ArrayObject* js::NewDenseCopiedArray(
3948 JSContext* cx, uint32_t length, const Value* values,
3949 HandleObject proto /* = nullptr */,
3950 NewObjectKind newKind /* = GenericObject */) {
3951 ArrayObject* arr = NewArray<UINT32_MAX>(cx, length, proto, newKind);
3952 if (!arr) {
3953 return nullptr;
3954 }
3955
3956 MOZ_ASSERT(arr->getDenseCapacity() >= length);
3957 MOZ_ASSERT(arr->getDenseInitializedLength() == 0);
3958
3959 if (values) {
3960 arr->initDenseElements(values, length);
3961 }
3962
3963 return arr;
3964 }
3965
NewDenseFullyAllocatedArrayWithTemplate(JSContext * cx,uint32_t length,ArrayObject * templateObject)3966 ArrayObject* js::NewDenseFullyAllocatedArrayWithTemplate(
3967 JSContext* cx, uint32_t length, ArrayObject* templateObject) {
3968 AutoSetNewObjectMetadata metadata(cx);
3969 gc::AllocKind allocKind = GuessArrayGCKind(length);
3970 MOZ_ASSERT(CanChangeToBackgroundAllocKind(allocKind, &ArrayObject::class_));
3971 allocKind = ForegroundToBackgroundAllocKind(allocKind);
3972
3973 RootedShape shape(cx, templateObject->shape());
3974
3975 gc::InitialHeap heap = GetInitialHeap(GenericObject, &ArrayObject::class_);
3976 Rooted<ArrayObject*> arr(
3977 cx,
3978 ArrayObject::createArray(cx, allocKind, heap, shape, length, metadata));
3979 if (!arr) {
3980 return nullptr;
3981 }
3982
3983 if (!EnsureNewArrayElements(cx, arr, length)) {
3984 return nullptr;
3985 }
3986
3987 probes::CreateObject(cx, arr);
3988
3989 return arr;
3990 }
3991
3992 // TODO(no-TI): clean up.
NewArrayWithShape(JSContext * cx,uint32_t length,HandleShape shape)3993 ArrayObject* js::NewArrayWithShape(JSContext* cx, uint32_t length,
3994 HandleShape shape) {
3995 // Ion can call this with a shape from a different realm when calling
3996 // another realm's Array constructor.
3997 Maybe<AutoRealm> ar;
3998 if (cx->realm() != shape->realm()) {
3999 MOZ_ASSERT(cx->compartment() == shape->compartment());
4000 ar.emplace(cx, shape);
4001 }
4002
4003 return NewDenseFullyAllocatedArray(cx, length);
4004 }
4005
4006 #ifdef DEBUG
ArrayInfo(JSContext * cx,unsigned argc,Value * vp)4007 bool js::ArrayInfo(JSContext* cx, unsigned argc, Value* vp) {
4008 CallArgs args = CallArgsFromVp(argc, vp);
4009 RootedObject obj(cx);
4010
4011 for (unsigned i = 0; i < args.length(); i++) {
4012 HandleValue arg = args[i];
4013
4014 UniqueChars bytes =
4015 DecompileValueGenerator(cx, JSDVG_SEARCH_STACK, arg, nullptr);
4016 if (!bytes) {
4017 return false;
4018 }
4019 if (arg.isPrimitive() || !(obj = arg.toObjectOrNull())->is<ArrayObject>()) {
4020 fprintf(stderr, "%s: not array\n", bytes.get());
4021 continue;
4022 }
4023 fprintf(stderr, "%s: (len %u", bytes.get(),
4024 obj->as<ArrayObject>().length());
4025 fprintf(stderr, ", capacity %u", obj->as<ArrayObject>().getDenseCapacity());
4026 fputs(")\n", stderr);
4027 }
4028
4029 args.rval().setUndefined();
4030 return true;
4031 }
4032 #endif
4033
initialize(JSContext * cx)4034 void js::ArraySpeciesLookup::initialize(JSContext* cx) {
4035 MOZ_ASSERT(state_ == State::Uninitialized);
4036
4037 // Get the canonical Array.prototype.
4038 NativeObject* arrayProto = cx->global()->maybeGetArrayPrototype();
4039
4040 // Leave the cache uninitialized if the Array class itself is not yet
4041 // initialized.
4042 if (!arrayProto) {
4043 return;
4044 }
4045
4046 // Get the canonical Array constructor.
4047 const Value& arrayCtorValue = cx->global()->getConstructor(JSProto_Array);
4048 MOZ_ASSERT(arrayCtorValue.isObject(),
4049 "The Array constructor is initialized iff Array.prototype is "
4050 "initialized");
4051 JSFunction* arrayCtor = &arrayCtorValue.toObject().as<JSFunction>();
4052
4053 // Shortcut returns below means Array[@@species] will never be
4054 // optimizable, set to disabled now, and clear it later when we succeed.
4055 state_ = State::Disabled;
4056
4057 // Look up Array.prototype[@@iterator] and ensure it's a data property.
4058 Maybe<PropertyInfo> ctorProp =
4059 arrayProto->lookup(cx, NameToId(cx->names().constructor));
4060 if (ctorProp.isNothing() || !ctorProp->isDataProperty()) {
4061 return;
4062 }
4063
4064 // Get the referred value, and ensure it holds the canonical Array
4065 // constructor.
4066 JSFunction* ctorFun;
4067 if (!IsFunctionObject(arrayProto->getSlot(ctorProp->slot()), &ctorFun)) {
4068 return;
4069 }
4070 if (ctorFun != arrayCtor) {
4071 return;
4072 }
4073
4074 // Look up the '@@species' value on Array
4075 Maybe<PropertyInfo> speciesProp =
4076 arrayCtor->lookup(cx, SYMBOL_TO_JSID(cx->wellKnownSymbols().species));
4077 if (speciesProp.isNothing() || !arrayCtor->hasGetter(*speciesProp)) {
4078 return;
4079 }
4080
4081 // Get the referred value, ensure it holds the canonical Array[@@species]
4082 // function.
4083 uint32_t speciesGetterSlot = speciesProp->slot();
4084 JSObject* speciesGetter = arrayCtor->getGetter(speciesGetterSlot);
4085 if (!speciesGetter || !speciesGetter->is<JSFunction>()) {
4086 return;
4087 }
4088 JSFunction* speciesFun = &speciesGetter->as<JSFunction>();
4089 if (!IsSelfHostedFunctionWithName(speciesFun, cx->names().ArraySpecies)) {
4090 return;
4091 }
4092
4093 // Store raw pointers below. This is okay to do here, because all objects
4094 // are in the tenured heap.
4095 MOZ_ASSERT(!IsInsideNursery(arrayProto));
4096 MOZ_ASSERT(!IsInsideNursery(arrayCtor));
4097 MOZ_ASSERT(!IsInsideNursery(arrayCtor->shape()));
4098 MOZ_ASSERT(!IsInsideNursery(speciesFun));
4099 MOZ_ASSERT(!IsInsideNursery(arrayProto->shape()));
4100
4101 state_ = State::Initialized;
4102 arrayProto_ = arrayProto;
4103 arrayConstructor_ = arrayCtor;
4104 arrayConstructorShape_ = arrayCtor->shape();
4105 arraySpeciesGetterSlot_ = speciesGetterSlot;
4106 canonicalSpeciesFunc_ = speciesFun;
4107 arrayProtoShape_ = arrayProto->shape();
4108 arrayProtoConstructorSlot_ = ctorProp->slot();
4109 }
4110
reset()4111 void js::ArraySpeciesLookup::reset() {
4112 AlwaysPoison(this, JS_RESET_VALUE_PATTERN, sizeof(*this),
4113 MemCheckKind::MakeUndefined);
4114 state_ = State::Uninitialized;
4115 }
4116
isArrayStateStillSane()4117 bool js::ArraySpeciesLookup::isArrayStateStillSane() {
4118 MOZ_ASSERT(state_ == State::Initialized);
4119
4120 // Ensure that Array.prototype still has the expected shape.
4121 if (arrayProto_->shape() != arrayProtoShape_) {
4122 return false;
4123 }
4124
4125 // Ensure that Array.prototype.constructor contains the canonical Array
4126 // constructor function.
4127 if (arrayProto_->getSlot(arrayProtoConstructorSlot_) !=
4128 ObjectValue(*arrayConstructor_)) {
4129 return false;
4130 }
4131
4132 // Ensure that Array still has the expected shape.
4133 if (arrayConstructor_->shape() != arrayConstructorShape_) {
4134 return false;
4135 }
4136
4137 // Ensure the species getter contains the canonical @@species function.
4138 JSObject* getter = arrayConstructor_->getGetter(arraySpeciesGetterSlot_);
4139 return getter == canonicalSpeciesFunc_;
4140 }
4141
tryOptimizeArray(JSContext * cx,ArrayObject * array)4142 bool js::ArraySpeciesLookup::tryOptimizeArray(JSContext* cx,
4143 ArrayObject* array) {
4144 if (state_ == State::Uninitialized) {
4145 // If the cache is not initialized, initialize it.
4146 initialize(cx);
4147 } else if (state_ == State::Initialized && !isArrayStateStillSane()) {
4148 // Otherwise, if the array state is no longer sane, reinitialize.
4149 reset();
4150 initialize(cx);
4151 }
4152
4153 // If the cache is disabled or still uninitialized, don't bother trying to
4154 // optimize.
4155 if (state_ != State::Initialized) {
4156 return false;
4157 }
4158
4159 // By the time we get here, we should have a sane array state.
4160 MOZ_ASSERT(isArrayStateStillSane());
4161
4162 // Ensure |array|'s prototype is the actual Array.prototype.
4163 if (array->staticPrototype() != arrayProto_) {
4164 return false;
4165 }
4166
4167 // Ensure |array| doesn't define any own properties besides its
4168 // non-deletable "length" property. This serves as a quick check to make
4169 // sure |array| doesn't define an own "constructor" property which may
4170 // shadow Array.prototype.constructor.
4171 ShapePropertyIter<NoGC> iter(array->shape());
4172 MOZ_ASSERT(!iter.done(), "Array must have at least one property");
4173 DebugOnly<PropertyKey> key = iter->key();
4174 iter++;
4175 if (!iter.done()) {
4176 return false;
4177 }
4178
4179 MOZ_ASSERT(key.inspect().isAtom(cx->names().length));
4180 return true;
4181 }
4182
NewArrayObject(JSContext * cx,const HandleValueArray & contents)4183 JS_PUBLIC_API JSObject* JS::NewArrayObject(JSContext* cx,
4184 const HandleValueArray& contents) {
4185 MOZ_ASSERT(!cx->zone()->isAtomsZone());
4186 AssertHeapIsIdle();
4187 CHECK_THREAD(cx);
4188 cx->check(contents);
4189
4190 return NewDenseCopiedArray(cx, contents.length(), contents.begin());
4191 }
4192
NewArrayObject(JSContext * cx,size_t length)4193 JS_PUBLIC_API JSObject* JS::NewArrayObject(JSContext* cx, size_t length) {
4194 MOZ_ASSERT(!cx->zone()->isAtomsZone());
4195 AssertHeapIsIdle();
4196 CHECK_THREAD(cx);
4197
4198 return NewDenseFullyAllocatedArray(cx, length);
4199 }
4200
IsArrayObject(JSContext * cx,Handle<JSObject * > obj,bool * isArray)4201 JS_PUBLIC_API bool JS::IsArrayObject(JSContext* cx, Handle<JSObject*> obj,
4202 bool* isArray) {
4203 return IsGivenTypeObject(cx, obj, ESClass::Array, isArray);
4204 }
4205
IsArrayObject(JSContext * cx,Handle<Value> value,bool * isArray)4206 JS_PUBLIC_API bool JS::IsArrayObject(JSContext* cx, Handle<Value> value,
4207 bool* isArray) {
4208 if (!value.isObject()) {
4209 *isArray = false;
4210 return true;
4211 }
4212
4213 Rooted<JSObject*> obj(cx, &value.toObject());
4214 return IsArrayObject(cx, obj, isArray);
4215 }
4216
GetArrayLength(JSContext * cx,Handle<JSObject * > obj,uint32_t * lengthp)4217 JS_PUBLIC_API bool JS::GetArrayLength(JSContext* cx, Handle<JSObject*> obj,
4218 uint32_t* lengthp) {
4219 AssertHeapIsIdle();
4220 CHECK_THREAD(cx);
4221 cx->check(obj);
4222
4223 uint64_t len = 0;
4224 if (!GetLengthProperty(cx, obj, &len)) {
4225 return false;
4226 }
4227
4228 if (len > UINT32_MAX) {
4229 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
4230 JSMSG_BAD_ARRAY_LENGTH);
4231 return false;
4232 }
4233
4234 *lengthp = uint32_t(len);
4235 return true;
4236 }
4237
SetArrayLength(JSContext * cx,Handle<JSObject * > obj,uint32_t length)4238 JS_PUBLIC_API bool JS::SetArrayLength(JSContext* cx, Handle<JSObject*> obj,
4239 uint32_t length) {
4240 AssertHeapIsIdle();
4241 CHECK_THREAD(cx);
4242 cx->check(obj);
4243
4244 return SetLengthProperty(cx, obj, length);
4245 }
4246