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