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