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