Fix max length check in ArrayPrototype.js' concatSlowPath().
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSArray.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003-2017 Apple Inc. All rights reserved.
4  *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
5  *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
6  *
7  *  This library is free software; you can redistribute it and/or
8  *  modify it under the terms of the GNU Lesser General Public
9  *  License as published by the Free Software Foundation; either
10  *  version 2 of the License, or (at your option) any later version.
11  *
12  *  This library is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  *  Lesser General Public License for more details.
16  *
17  *  You should have received a copy of the GNU Lesser General Public
18  *  License along with this library; if not, write to the Free Software
19  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
20  *
21  */
22
23 #include "config.h"
24 #include "JSArray.h"
25
26 #include "ArrayPrototype.h"
27 #include "ButterflyInlines.h"
28 #include "CodeBlock.h"
29 #include "Error.h"
30 #include "GetterSetter.h"
31 #include "IndexingHeaderInlines.h"
32 #include "JSArrayInlines.h"
33 #include "JSCInlines.h"
34 #include "PropertyNameArray.h"
35 #include "TypeError.h"
36 #include <wtf/Assertions.h>
37
38 using namespace std;
39 using namespace WTF;
40
41 namespace JSC {
42
43 static const char* const LengthExceededTheMaximumArrayLengthError = "Length exceeded the maximum array length";
44
45 STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray);
46
47 const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, CREATE_METHOD_TABLE(JSArray)};
48
49 Butterfly* createArrayButterflyInDictionaryIndexingMode(
50     VM& vm, JSCell* intendedOwner, unsigned initialLength)
51 {
52     Butterfly* butterfly = Butterfly::create(
53         vm, intendedOwner, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0));
54     ArrayStorage* storage = butterfly->arrayStorage();
55     storage->setLength(initialLength);
56     storage->setVectorLength(0);
57     storage->m_indexBias = 0;
58     storage->m_sparseMap.clear();
59     storage->m_numValuesInVector = 0;
60     return butterfly;
61 }
62
63 JSArray* JSArray::tryCreateForInitializationPrivate(VM& vm, GCDeferralContext* deferralContext, Structure* structure, unsigned initialLength)
64 {
65     if (initialLength > MAX_STORAGE_VECTOR_LENGTH)
66         return 0;
67
68     unsigned outOfLineStorage = structure->outOfLineCapacity();
69
70     Butterfly* butterfly;
71     IndexingType indexingType = structure->indexingType();
72     if (LIKELY(!hasAnyArrayStorage(indexingType))) {
73         ASSERT(
74             hasUndecided(indexingType)
75             || hasInt32(indexingType)
76             || hasDouble(indexingType)
77             || hasContiguous(indexingType));
78
79         unsigned vectorLength = Butterfly::optimalContiguousVectorLength(structure, initialLength);
80         void* temp = vm.auxiliarySpace.tryAllocate(deferralContext, Butterfly::totalSize(0, outOfLineStorage, true, vectorLength * sizeof(EncodedJSValue)));
81         if (!temp)
82             return nullptr;
83         butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
84         butterfly->setVectorLength(vectorLength);
85         butterfly->setPublicLength(initialLength);
86         if (hasDouble(indexingType)) {
87             for (unsigned i = initialLength; i < vectorLength; ++i)
88                 butterfly->contiguousDouble()[i] = PNaN;
89         } else {
90             for (unsigned i = initialLength; i < vectorLength; ++i)
91                 butterfly->contiguous()[i].clear();
92         }
93     } else {
94         unsigned vectorLength = ArrayStorage::optimalVectorLength(0, structure, initialLength);
95         void* temp = vm.auxiliarySpace.tryAllocate(deferralContext, Butterfly::totalSize(0, outOfLineStorage, true, ArrayStorage::sizeFor(vectorLength)));
96         if (!temp)
97             return nullptr;
98         butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
99         *butterfly->indexingHeader() = indexingHeaderForArrayStorage(initialLength, vectorLength);
100         ArrayStorage* storage = butterfly->arrayStorage();
101         storage->m_indexBias = 0;
102         storage->m_sparseMap.clear();
103         storage->m_numValuesInVector = initialLength;
104         for (unsigned i = initialLength; i < vectorLength; ++i)
105             storage->m_vector[i].clear();
106     }
107
108     return createWithButterfly(vm, deferralContext, structure, butterfly);
109 }
110
111 void JSArray::setLengthWritable(ExecState* exec, bool writable)
112 {
113     ASSERT(isLengthWritable() || !writable);
114     if (!isLengthWritable() || writable)
115         return;
116
117     enterDictionaryIndexingMode(exec->vm());
118
119     SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
120     ASSERT(map);
121     map->setLengthIsReadOnly();
122 }
123
124 // Defined in ES5.1 15.4.5.1
125 bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)
126 {
127     VM& vm = exec->vm();
128     auto scope = DECLARE_THROW_SCOPE(vm);
129
130     JSArray* array = jsCast<JSArray*>(object);
131
132     // 3. If P is "length", then
133     if (propertyName == vm.propertyNames->length) {
134         // All paths through length definition call the default [[DefineOwnProperty]], hence:
135         // from ES5.1 8.12.9 7.a.
136         if (descriptor.configurablePresent() && descriptor.configurable())
137             return typeError(exec, scope, throwException, ASCIILiteral(UnconfigurablePropertyChangeConfigurabilityError));
138         // from ES5.1 8.12.9 7.b.
139         if (descriptor.enumerablePresent() && descriptor.enumerable())
140             return typeError(exec, scope, throwException, ASCIILiteral(UnconfigurablePropertyChangeEnumerabilityError));
141
142         // a. If the [[Value]] field of Desc is absent, then
143         // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
144         if (descriptor.isAccessorDescriptor())
145             return typeError(exec, scope, throwException, ASCIILiteral(UnconfigurablePropertyChangeAccessMechanismError));
146         // from ES5.1 8.12.9 10.a.
147         if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
148             return typeError(exec, scope, throwException, ASCIILiteral(UnconfigurablePropertyChangeWritabilityError));
149         // This descriptor is either just making length read-only, or changing nothing!
150         if (!descriptor.value()) {
151             if (descriptor.writablePresent())
152                 array->setLengthWritable(exec, descriptor.writable());
153             return true;
154         }
155         
156         // b. Let newLenDesc be a copy of Desc.
157         // c. Let newLen be ToUint32(Desc.[[Value]]).
158         unsigned newLen = descriptor.value().toUInt32(exec);
159         // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
160         if (newLen != descriptor.value().toNumber(exec)) {
161             JSC::throwException(exec, scope, createRangeError(exec, ASCIILiteral("Invalid array length")));
162             return false;
163         }
164
165         // Based on SameValue check in 8.12.9, this is always okay.
166         // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case.
167         if (newLen == array->length()) {
168             if (descriptor.writablePresent())
169                 array->setLengthWritable(exec, descriptor.writable());
170             return true;
171         }
172
173         // e. Set newLenDesc.[[Value] to newLen.
174         // f. If newLen >= oldLen, then
175         // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
176         // g. Reject if oldLenDesc.[[Writable]] is false.
177         if (!array->isLengthWritable())
178             return typeError(exec, scope, throwException, ASCIILiteral(ReadonlyPropertyChangeError));
179         
180         // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
181         // i. Else,
182         // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
183         // i.ii. Let newWritable be false.
184         // i.iii. Set newLenDesc.[[Writable] to true.
185         // j. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
186         // k. If succeeded is false, return false.
187         // l. While newLen < oldLen repeat,
188         // l.i. Set oldLen to oldLen – 1.
189         // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
190         // l.iii. If deleteSucceeded is false, then
191         bool success = array->setLength(exec, newLen, throwException);
192         ASSERT(!scope.exception() || !success);
193         if (!success) {
194             // 1. Set newLenDesc.[[Value] to oldLen+1.
195             // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
196             // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
197             // 4. Reject.
198             if (descriptor.writablePresent())
199                 array->setLengthWritable(exec, descriptor.writable());
200             return false;
201         }
202
203         // m. If newWritable is false, then
204         // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
205         //    Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
206         //    return true.
207         if (descriptor.writablePresent())
208             array->setLengthWritable(exec, descriptor.writable());
209         // n. Return true.
210         return true;
211     }
212
213     // 4. Else if P is an array index (15.4), then
214     // a. Let index be ToUint32(P).
215     if (std::optional<uint32_t> optionalIndex = parseIndex(propertyName)) {
216         // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
217         uint32_t index = optionalIndex.value();
218         // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case.
219         if (index >= array->length() && !array->isLengthWritable())
220             return typeError(exec, scope, throwException, ASCIILiteral("Attempting to define numeric property on array with non-writable length property."));
221         // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments.
222         // d. Reject if succeeded is false.
223         // e. If index >= oldLen
224         // e.i. Set oldLenDesc.[[Value]] to index + 1.
225         // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true.
226         // f. Return true.
227         scope.release();
228         return array->defineOwnIndexedProperty(exec, index, descriptor, throwException);
229     }
230
231     scope.release();
232     return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
233 }
234
235 bool JSArray::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
236 {
237     JSArray* thisObject = jsCast<JSArray*>(object);
238     if (propertyName == exec->propertyNames().length) {
239         unsigned attributes = thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly;
240         slot.setValue(thisObject, attributes, jsNumber(thisObject->length()));
241         return true;
242     }
243
244     return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
245 }
246
247 // ECMA 15.4.5.1
248 bool JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
249 {
250     VM& vm = exec->vm();
251     auto scope = DECLARE_THROW_SCOPE(vm);
252
253     JSArray* thisObject = jsCast<JSArray*>(cell);
254
255     if (UNLIKELY(isThisValueAltered(slot, thisObject))) {
256         scope.release();
257         return ordinarySetSlow(exec, thisObject, propertyName, value, slot.thisValue(), slot.isStrictMode());
258     }
259
260     if (propertyName == exec->propertyNames().length) {
261         unsigned newLength = value.toUInt32(exec);
262         RETURN_IF_EXCEPTION(scope, false);
263         if (value.toNumber(exec) != static_cast<double>(newLength)) {
264             throwException(exec, scope, createRangeError(exec, ASCIILiteral("Invalid array length")));
265             return false;
266         }
267         scope.release();
268         return thisObject->setLength(exec, newLength, slot.isStrictMode());
269     }
270
271     scope.release();
272     return JSObject::put(thisObject, exec, propertyName, value, slot);
273 }
274
275 bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
276 {
277     JSArray* thisObject = jsCast<JSArray*>(cell);
278
279     if (propertyName == exec->propertyNames().length)
280         return false;
281
282     return JSObject::deleteProperty(thisObject, exec, propertyName);
283 }
284
285 static int compareKeysForQSort(const void* a, const void* b)
286 {
287     unsigned da = *static_cast<const unsigned*>(a);
288     unsigned db = *static_cast<const unsigned*>(b);
289     return (da > db) - (da < db);
290 }
291
292 void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
293 {
294     JSArray* thisObject = jsCast<JSArray*>(object);
295
296     if (mode.includeDontEnumProperties())
297         propertyNames.add(exec->propertyNames().length);
298
299     JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
300 }
301
302 // This method makes room in the vector, but leaves the new space for count slots uncleared.
303 bool JSArray::unshiftCountSlowCase(const AbstractLocker&, VM& vm, DeferGC&, bool addToFront, unsigned count)
304 {
305     ArrayStorage* storage = ensureArrayStorage(vm);
306     Butterfly* butterfly = storage->butterfly();
307     Structure* structure = this->structure(vm);
308     unsigned propertyCapacity = structure->outOfLineCapacity();
309     unsigned propertySize = structure->outOfLineSize();
310     
311     // If not, we should have handled this on the fast path.
312     ASSERT(!addToFront || count > storage->m_indexBias);
313
314     // Step 1:
315     // Gather 4 key metrics:
316     //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
317     //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
318     //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
319     //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
320
321     unsigned length = storage->length();
322     unsigned oldVectorLength = storage->vectorLength();
323     unsigned usedVectorLength = min(oldVectorLength, length);
324     ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
325     // Check that required vector length is possible, in an overflow-safe fashion.
326     if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
327         return false;
328     unsigned requiredVectorLength = usedVectorLength + count;
329     ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
330     // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
331     ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
332     unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
333     // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
334     // FIXME: This code should be fixed to avoid internal fragmentation. It's not super high
335     // priority since increaseVectorLength() will "fix" any mistakes we make, but it would be cool
336     // to get this right eventually.
337     unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_ARRAY_STORAGE_VECTOR_LEN, requiredVectorLength) << 1);
338
339     // Step 2:
340     // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
341
342     void* newAllocBase = 0;
343     unsigned newStorageCapacity;
344     bool allocatedNewStorage;
345     // If the current storage array is sufficiently large (but not too large!) then just keep using it.
346     if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
347         newAllocBase = butterfly->base(structure);
348         newStorageCapacity = currentCapacity;
349         allocatedNewStorage = false;
350     } else {
351         size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
352         newAllocBase = vm.auxiliarySpace.tryAllocate(newSize);
353         if (!newAllocBase)
354             return false;
355         newStorageCapacity = desiredCapacity;
356         allocatedNewStorage = true;
357     }
358
359     // Step 3:
360     // Work out where we're going to move things to.
361
362     // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
363     // If we're adding to the end, we'll add all the new space to the end.
364     // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
365     // If it did, we calculate the amount that will remain based on an atomic decay - leave the
366     // vector with half the post-capacity it had previously.
367     unsigned postCapacity = 0;
368     if (!addToFront)
369         postCapacity = max(newStorageCapacity - requiredVectorLength, count);
370     else if (length < storage->vectorLength()) {
371         // Atomic decay, + the post-capacity cannot be greater than what is available.
372         postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
373         // If we're moving contents within the same allocation, the post-capacity is being reduced.
374         ASSERT(newAllocBase != butterfly->base(structure) || postCapacity < storage->vectorLength() - length);
375     }
376
377     unsigned newVectorLength = requiredVectorLength + postCapacity;
378     unsigned newIndexBias = newStorageCapacity - newVectorLength;
379
380     Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
381
382     if (addToFront) {
383         ASSERT(count + usedVectorLength <= newVectorLength);
384         memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
385         memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
386         
387         if (allocatedNewStorage) {
388             // We will set the vectorLength to newVectorLength. We populated requiredVectorLength
389             // (usedVectorLength + count), which is less. Clear the difference.
390             for (unsigned i = requiredVectorLength; i < newVectorLength; ++i)
391                 newButterfly->arrayStorage()->m_vector[i].clear();
392         }
393     } else if ((newAllocBase != butterfly->base(structure)) || (newIndexBias != storage->m_indexBias)) {
394         memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
395         memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);
396         
397         for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
398             newButterfly->arrayStorage()->m_vector[i].clear();
399     }
400
401     newButterfly->arrayStorage()->setVectorLength(newVectorLength);
402     newButterfly->arrayStorage()->m_indexBias = newIndexBias;
403     
404     setButterfly(vm, newButterfly);
405
406     return true;
407 }
408
409 bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
410 {
411     VM& vm = exec->vm();
412     auto scope = DECLARE_THROW_SCOPE(vm);
413
414     unsigned length = storage->length();
415     
416     // If the length is read only then we enter sparse mode, so should enter the following 'if'.
417     ASSERT(isLengthWritable() || storage->m_sparseMap);
418
419     if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
420         // Fail if the length is not writable.
421         if (map->lengthIsReadOnly())
422             return typeError(exec, scope, throwException, ASCIILiteral(ReadonlyPropertyWriteError));
423
424         if (newLength < length) {
425             // Copy any keys we might be interested in into a vector.
426             Vector<unsigned, 0, UnsafeVectorOverflow> keys;
427             keys.reserveInitialCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
428             SparseArrayValueMap::const_iterator end = map->end();
429             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
430                 unsigned index = static_cast<unsigned>(it->key);
431                 if (index < length && index >= newLength)
432                     keys.append(index);
433             }
434
435             // Check if the array is in sparse mode. If so there may be non-configurable
436             // properties, so we have to perform deletion with caution, if not we can
437             // delete values in any order.
438             if (map->sparseMode()) {
439                 qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
440                 unsigned i = keys.size();
441                 while (i) {
442                     unsigned index = keys[--i];
443                     SparseArrayValueMap::iterator it = map->find(index);
444                     ASSERT(it != map->notFound());
445                     if (it->value.attributes & DontDelete) {
446                         storage->setLength(index + 1);
447                         return typeError(exec, scope, throwException, ASCIILiteral(UnableToDeletePropertyError));
448                     }
449                     map->remove(it);
450                 }
451             } else {
452                 for (unsigned i = 0; i < keys.size(); ++i)
453                     map->remove(keys[i]);
454                 if (map->isEmpty())
455                     deallocateSparseIndexMap();
456             }
457         }
458     }
459
460     if (newLength < length) {
461         // Delete properties from the vector.
462         unsigned usedVectorLength = min(length, storage->vectorLength());
463         for (unsigned i = newLength; i < usedVectorLength; ++i) {
464             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
465             bool hadValue = !!valueSlot;
466             valueSlot.clear();
467             storage->m_numValuesInVector -= hadValue;
468         }
469     }
470
471     storage->setLength(newLength);
472
473     return true;
474 }
475
476 bool JSArray::appendMemcpy(ExecState* exec, VM& vm, unsigned startIndex, JSC::JSArray* otherArray)
477 {
478     auto scope = DECLARE_THROW_SCOPE(vm);
479
480     if (!canFastCopy(vm, otherArray))
481         return false;
482
483     IndexingType type = indexingType();
484     IndexingType copyType = mergeIndexingTypeForCopying(otherArray->indexingType());
485     if (type == ArrayWithUndecided && copyType != NonArray) {
486         if (copyType == ArrayWithInt32)
487             convertUndecidedToInt32(vm);
488         else if (copyType == ArrayWithDouble)
489             convertUndecidedToDouble(vm);
490         else if (copyType == ArrayWithContiguous)
491             convertUndecidedToContiguous(vm);
492         else {
493             ASSERT(copyType == ArrayWithUndecided);
494             return true;
495         }
496     } else if (type != copyType)
497         return false;
498
499     unsigned otherLength = otherArray->length();
500     Checked<unsigned, RecordOverflow> checkedNewLength = startIndex;
501     checkedNewLength += otherLength;
502
503     unsigned newLength;
504     if (checkedNewLength.safeGet(newLength) == CheckedState::DidOverflow) {
505         throwException(exec, scope, createRangeError(exec, ASCIILiteral(LengthExceededTheMaximumArrayLengthError)));
506         return false;
507     }
508
509     if (newLength >= MIN_SPARSE_ARRAY_INDEX)
510         return false;
511
512     if (!ensureLength(vm, newLength)) {
513         throwOutOfMemoryError(exec, scope);
514         return false;
515     }
516     ASSERT(copyType == indexingType());
517
518     if (type == ArrayWithDouble)
519         memcpy(butterfly()->contiguousDouble().data() + startIndex, otherArray->butterfly()->contiguousDouble().data(), sizeof(JSValue) * otherLength);
520     else
521         memcpy(butterfly()->contiguous().data() + startIndex, otherArray->butterfly()->contiguous().data(), sizeof(JSValue) * otherLength);
522
523     return true;
524 }
525
526 bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
527 {
528     VM& vm = exec->vm();
529     auto scope = DECLARE_THROW_SCOPE(vm);
530
531     Butterfly* butterfly = m_butterfly.get();
532     switch (indexingType()) {
533     case ArrayClass:
534         if (!newLength)
535             return true;
536         if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
537             scope.release();
538             return setLengthWithArrayStorage(
539                 exec, newLength, throwException,
540                 ensureArrayStorage(vm));
541         }
542         createInitialUndecided(vm, newLength);
543         return true;
544         
545     case ArrayWithUndecided:
546     case ArrayWithInt32:
547     case ArrayWithDouble:
548     case ArrayWithContiguous: {
549         if (newLength == butterfly->publicLength())
550             return true;
551         if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
552             || (newLength >= MIN_SPARSE_ARRAY_INDEX
553                 && !isDenseEnoughForVector(newLength, countElements()))) {
554             scope.release();
555             return setLengthWithArrayStorage(
556                 exec, newLength, throwException,
557                 ensureArrayStorage(vm));
558         }
559         if (newLength > butterfly->publicLength()) {
560             if (!ensureLength(vm, newLength)) {
561                 throwOutOfMemoryError(exec, scope);
562                 return false;
563             }
564             return true;
565         }
566
567         unsigned lengthToClear = butterfly->publicLength() - newLength;
568         unsigned costToAllocateNewButterfly = 64; // a heuristic.
569         if (lengthToClear > newLength && lengthToClear > costToAllocateNewButterfly) {
570             reallocateAndShrinkButterfly(vm, newLength);
571             return true;
572         }
573
574         if (indexingType() == ArrayWithDouble) {
575             for (unsigned i = butterfly->publicLength(); i-- > newLength;)
576                 butterfly->contiguousDouble()[i] = PNaN;
577         } else {
578             for (unsigned i = butterfly->publicLength(); i-- > newLength;)
579                 butterfly->contiguous()[i].clear();
580         }
581         butterfly->setPublicLength(newLength);
582         return true;
583     }
584         
585     case ArrayWithArrayStorage:
586     case ArrayWithSlowPutArrayStorage:
587         scope.release();
588         return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
589         
590     default:
591         CRASH();
592         return false;
593     }
594 }
595
596 JSValue JSArray::pop(ExecState* exec)
597 {
598     VM& vm = exec->vm();
599     auto scope = DECLARE_THROW_SCOPE(vm);
600
601     Butterfly* butterfly = m_butterfly.get();
602     
603     switch (indexingType()) {
604     case ArrayClass:
605         return jsUndefined();
606         
607     case ArrayWithUndecided:
608         if (!butterfly->publicLength())
609             return jsUndefined();
610         // We have nothing but holes. So, drop down to the slow version.
611         break;
612         
613     case ArrayWithInt32:
614     case ArrayWithContiguous: {
615         unsigned length = butterfly->publicLength();
616         
617         if (!length--)
618             return jsUndefined();
619         
620         RELEASE_ASSERT(length < butterfly->vectorLength());
621         JSValue value = butterfly->contiguous()[length].get();
622         if (value) {
623             butterfly->contiguous()[length].clear();
624             butterfly->setPublicLength(length);
625             return value;
626         }
627         break;
628     }
629         
630     case ArrayWithDouble: {
631         unsigned length = butterfly->publicLength();
632         
633         if (!length--)
634             return jsUndefined();
635         
636         RELEASE_ASSERT(length < butterfly->vectorLength());
637         double value = butterfly->contiguousDouble()[length];
638         if (value == value) {
639             butterfly->contiguousDouble()[length] = PNaN;
640             butterfly->setPublicLength(length);
641             return JSValue(JSValue::EncodeAsDouble, value);
642         }
643         break;
644     }
645         
646     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
647         ArrayStorage* storage = butterfly->arrayStorage();
648     
649         unsigned length = storage->length();
650         if (!length) {
651             if (!isLengthWritable())
652                 throwTypeError(exec, scope, ASCIILiteral(ReadonlyPropertyWriteError));
653             return jsUndefined();
654         }
655
656         unsigned index = length - 1;
657         if (index < storage->vectorLength()) {
658             WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
659             if (valueSlot) {
660                 --storage->m_numValuesInVector;
661                 JSValue element = valueSlot.get();
662                 valueSlot.clear();
663             
664                 RELEASE_ASSERT(isLengthWritable());
665                 storage->setLength(index);
666                 return element;
667             }
668         }
669         break;
670     }
671         
672     default:
673         CRASH();
674         return JSValue();
675     }
676     
677     unsigned index = getArrayLength() - 1;
678     // Let element be the result of calling the [[Get]] internal method of O with argument indx.
679     JSValue element = get(exec, index);
680     RETURN_IF_EXCEPTION(scope, JSValue());
681     // Call the [[Delete]] internal method of O with arguments indx and true.
682     bool success = deletePropertyByIndex(this, exec, index);
683     RETURN_IF_EXCEPTION(scope, JSValue());
684     if (!success) {
685         throwTypeError(exec, scope, ASCIILiteral(UnableToDeletePropertyError));
686         return jsUndefined();
687     }
688     // Call the [[Put]] internal method of O with arguments "length", indx, and true.
689     scope.release();
690     setLength(exec, index, true);
691     // Return element.
692     return element;
693 }
694
695 // Push & putIndex are almost identical, with two small differences.
696 //  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
697 //  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
698 void JSArray::push(ExecState* exec, JSValue value)
699 {
700     VM& vm = exec->vm();
701     auto scope = DECLARE_THROW_SCOPE(vm);
702
703     Butterfly* butterfly = m_butterfly.get();
704     
705     switch (indexingType()) {
706     case ArrayClass: {
707         createInitialUndecided(vm, 0);
708         FALLTHROUGH;
709     }
710         
711     case ArrayWithUndecided: {
712         convertUndecidedForValue(vm, value);
713         scope.release();
714         push(exec, value);
715         return;
716     }
717         
718     case ArrayWithInt32: {
719         if (!value.isInt32()) {
720             convertInt32ForValue(vm, value);
721             scope.release();
722             push(exec, value);
723             return;
724         }
725
726         unsigned length = butterfly->publicLength();
727         ASSERT(length <= butterfly->vectorLength());
728         if (length < butterfly->vectorLength()) {
729             butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value);
730             butterfly->setPublicLength(length + 1);
731             return;
732         }
733         
734         if (UNLIKELY(length > MAX_ARRAY_INDEX)) {
735             methodTable(vm)->putByIndex(this, exec, length, value, true);
736             if (!scope.exception())
737                 throwException(exec, scope, createRangeError(exec, ASCIILiteral(LengthExceededTheMaximumArrayLengthError)));
738             return;
739         }
740
741         scope.release();
742         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
743         return;
744     }
745
746     case ArrayWithContiguous: {
747         unsigned length = butterfly->publicLength();
748         ASSERT(length <= butterfly->vectorLength());
749         if (length < butterfly->vectorLength()) {
750             butterfly->contiguous()[length].set(vm, this, value);
751             butterfly->setPublicLength(length + 1);
752             return;
753         }
754         
755         if (UNLIKELY(length > MAX_ARRAY_INDEX)) {
756             methodTable(vm)->putByIndex(this, exec, length, value, true);
757             if (!scope.exception())
758                 throwException(exec, scope, createRangeError(exec, ASCIILiteral(LengthExceededTheMaximumArrayLengthError)));
759             return;
760         }
761
762         scope.release();
763         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value);
764         return;
765     }
766         
767     case ArrayWithDouble: {
768         if (!value.isNumber()) {
769             convertDoubleToContiguous(vm);
770             scope.release();
771             push(exec, value);
772             return;
773         }
774         double valueAsDouble = value.asNumber();
775         if (valueAsDouble != valueAsDouble) {
776             convertDoubleToContiguous(vm);
777             scope.release();
778             push(exec, value);
779             return;
780         }
781
782         unsigned length = butterfly->publicLength();
783         ASSERT(length <= butterfly->vectorLength());
784         if (length < butterfly->vectorLength()) {
785             butterfly->contiguousDouble()[length] = valueAsDouble;
786             butterfly->setPublicLength(length + 1);
787             return;
788         }
789         
790         if (UNLIKELY(length > MAX_ARRAY_INDEX)) {
791             methodTable(vm)->putByIndex(this, exec, length, value, true);
792             if (!scope.exception())
793                 throwException(exec, scope, createRangeError(exec, ASCIILiteral(LengthExceededTheMaximumArrayLengthError)));
794             return;
795         }
796
797         scope.release();
798         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value);
799         return;
800     }
801         
802     case ArrayWithSlowPutArrayStorage: {
803         unsigned oldLength = length();
804         bool putResult = false;
805         if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true, putResult)) {
806             if (!scope.exception() && oldLength < 0xFFFFFFFFu) {
807                 scope.release();
808                 setLength(exec, oldLength + 1, true);
809             }
810             return;
811         }
812         FALLTHROUGH;
813     }
814         
815     case ArrayWithArrayStorage: {
816         ArrayStorage* storage = butterfly->arrayStorage();
817
818         // Fast case - push within vector, always update m_length & m_numValuesInVector.
819         unsigned length = storage->length();
820         if (length < storage->vectorLength()) {
821             storage->m_vector[length].set(vm, this, value);
822             storage->setLength(length + 1);
823             ++storage->m_numValuesInVector;
824             return;
825         }
826
827         // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
828         if (UNLIKELY(storage->length() > MAX_ARRAY_INDEX)) {
829             methodTable(vm)->putByIndex(this, exec, storage->length(), value, true);
830             // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
831             if (!scope.exception())
832                 throwException(exec, scope, createRangeError(exec, ASCIILiteral(LengthExceededTheMaximumArrayLengthError)));
833             return;
834         }
835
836         // Handled the same as putIndex.
837         scope.release();
838         putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
839         return;
840     }
841         
842     default:
843         RELEASE_ASSERT_NOT_REACHED();
844     }
845 }
846
847 JSArray* JSArray::fastSlice(ExecState& exec, unsigned startIndex, unsigned count)
848 {
849     auto arrayType = indexingType();
850     switch (arrayType) {
851     case ArrayWithDouble:
852     case ArrayWithInt32:
853     case ArrayWithContiguous: {
854         VM& vm = exec.vm();
855         if (count >= MIN_SPARSE_ARRAY_INDEX || structure(vm)->holesMustForwardToPrototype(vm))
856             return nullptr;
857
858         Structure* resultStructure = exec.lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(arrayType);
859         JSArray* resultArray = JSArray::tryCreateForInitializationPrivate(vm, resultStructure, count);
860         if (!resultArray)
861             return nullptr;
862
863         auto& resultButterfly = *resultArray->butterfly();
864         if (arrayType == ArrayWithDouble)
865             memcpy(resultButterfly.contiguousDouble().data(), m_butterfly.get()->contiguousDouble().data() + startIndex, sizeof(JSValue) * count);
866         else
867             memcpy(resultButterfly.contiguous().data(), m_butterfly.get()->contiguous().data() + startIndex, sizeof(JSValue) * count);
868         resultButterfly.setPublicLength(count);
869
870         return resultArray;
871     }
872     default:
873         return nullptr;
874     }
875 }
876
877 bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage)
878 {
879     unsigned oldLength = storage->length();
880     RELEASE_ASSERT(count <= oldLength);
881     
882     // If the array contains holes or is otherwise in an abnormal state,
883     // use the generic algorithm in ArrayPrototype.
884     if ((storage->hasHoles() && this->structure(vm)->holesMustForwardToPrototype(vm)) 
885         || hasSparseMap() 
886         || shouldUseSlowPut(indexingType())) {
887         return false;
888     }
889
890     if (!oldLength)
891         return true;
892     
893     unsigned length = oldLength - count;
894     
895     storage->m_numValuesInVector -= count;
896     storage->setLength(length);
897     
898     unsigned vectorLength = storage->vectorLength();
899     if (!vectorLength)
900         return true;
901     
902     if (startIndex >= vectorLength)
903         return true;
904     
905     DisallowGC disallowGC;
906     auto locker = holdLock(*this);
907     
908     if (startIndex + count > vectorLength)
909         count = vectorLength - startIndex;
910     
911     unsigned usedVectorLength = min(vectorLength, oldLength);
912     
913     unsigned numElementsBeforeShiftRegion = startIndex;
914     unsigned firstIndexAfterShiftRegion = startIndex + count;
915     unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
916     ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
917
918     // The point of this comparison seems to be to minimize the amount of elements that have to 
919     // be moved during a shift operation.
920     if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
921         // The number of elements before the shift region is less than the number of elements
922         // after the shift region, so we move the elements before to the right.
923         if (numElementsBeforeShiftRegion) {
924             RELEASE_ASSERT(count + startIndex <= vectorLength);
925             if (storage->hasHoles()) {
926                 for (unsigned i = startIndex; i-- > 0;) {
927                     unsigned destinationIndex = count + i;
928                     JSValue source = storage->m_vector[i].get();
929                     JSValue dest = storage->m_vector[destinationIndex].get();
930                     // Any time we overwrite a hole we know we overcounted the number of values we removed 
931                     // when we subtracted count from m_numValuesInVector above.
932                     if (!dest && destinationIndex >= firstIndexAfterShiftRegion)
933                         storage->m_numValuesInVector++;
934                     storage->m_vector[count + i].setWithoutWriteBarrier(source);
935                 }
936             } else {
937                 memmove(storage->m_vector + count,
938                     storage->m_vector,
939                     sizeof(JSValue) * startIndex);
940             }
941         }
942         // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
943         // the start of the Butterfly, which needs to point at the first indexed property in the used
944         // portion of the vector.
945         Butterfly* butterfly = m_butterfly.get()->shift(structure(), count);
946         setButterfly(vm, butterfly);
947         storage = butterfly->arrayStorage();
948         storage->m_indexBias += count;
949
950         // Since we're consuming part of the vector by moving its beginning to the left,
951         // we need to modify the vector length appropriately.
952         storage->setVectorLength(vectorLength - count);
953     } else {
954         // The number of elements before the shift region is greater than or equal to the number 
955         // of elements after the shift region, so we move the elements after the shift region to the left.
956         if (storage->hasHoles()) {
957             for (unsigned i = 0; i < numElementsAfterShiftRegion; ++i) {
958                 unsigned destinationIndex = startIndex + i;
959                 JSValue source = storage->m_vector[firstIndexAfterShiftRegion + i].get();
960                 JSValue dest = storage->m_vector[destinationIndex].get();
961                 // Any time we overwrite a hole we know we overcounted the number of values we removed 
962                 // when we subtracted count from m_numValuesInVector above.
963                 if (!dest && destinationIndex < firstIndexAfterShiftRegion)
964                     storage->m_numValuesInVector++;
965                 storage->m_vector[startIndex + i].setWithoutWriteBarrier(source);
966             }
967         } else {
968             memmove(storage->m_vector + startIndex,
969                 storage->m_vector + firstIndexAfterShiftRegion,
970                 sizeof(JSValue) * numElementsAfterShiftRegion);
971         }
972         // Clear the slots of the elements we just moved.
973         unsigned startOfEmptyVectorTail = usedVectorLength - count;
974         for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i)
975             storage->m_vector[i].clear();
976         // We don't modify the index bias or the Butterfly pointer in this case because we're not changing 
977         // the start of the Butterfly, which needs to point at the first indexed property in the used 
978         // portion of the vector. We also don't modify the vector length because we're not actually changing
979         // its length; we're just using less of it.
980     }
981     
982     return true;
983 }
984
985 bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count)
986 {
987     VM& vm = exec->vm();
988     RELEASE_ASSERT(count > 0);
989
990     Butterfly* butterfly = m_butterfly.get();
991     
992     switch (indexingType()) {
993     case ArrayClass:
994         return true;
995         
996     case ArrayWithUndecided:
997         // Don't handle this because it's confusing and it shouldn't come up.
998         return false;
999         
1000     case ArrayWithInt32:
1001     case ArrayWithContiguous: {
1002         unsigned oldLength = butterfly->publicLength();
1003         RELEASE_ASSERT(count <= oldLength);
1004         
1005         // We may have to walk the entire array to do the shift. We're willing to do
1006         // so only if it's not horribly slow.
1007         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
1008             return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
1009
1010         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
1011         // is totally not fine, since we might have to read from the proto chain.
1012         // We have to check for holes before we start moving things around so that we don't get halfway 
1013         // through shifting and then realize we should have been in ArrayStorage mode.
1014         unsigned end = oldLength - count;
1015         if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
1016             for (unsigned i = startIndex; i < end; ++i) {
1017                 JSValue v = butterfly->contiguous()[i + count].get();
1018                 if (UNLIKELY(!v)) {
1019                     startIndex = i;
1020                     return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
1021                 }
1022                 butterfly->contiguous()[i].setWithoutWriteBarrier(v);
1023             }
1024         } else {
1025             memmove(butterfly->contiguous().data() + startIndex, 
1026                 butterfly->contiguous().data() + startIndex + count, 
1027                 sizeof(JSValue) * (end - startIndex));
1028         }
1029
1030         for (unsigned i = end; i < oldLength; ++i)
1031             butterfly->contiguous()[i].clear();
1032         
1033         butterfly->setPublicLength(oldLength - count);
1034
1035         // Our memmoving of values around in the array could have concealed some of them from
1036         // the collector. Let's make sure that the collector scans this object again.
1037         vm.heap.writeBarrier(this);
1038         
1039         return true;
1040     }
1041         
1042     case ArrayWithDouble: {
1043         unsigned oldLength = butterfly->publicLength();
1044         RELEASE_ASSERT(count <= oldLength);
1045         
1046         // We may have to walk the entire array to do the shift. We're willing to do
1047         // so only if it's not horribly slow.
1048         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
1049             return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
1050
1051         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
1052         // is totally not fine, since we might have to read from the proto chain.
1053         // We have to check for holes before we start moving things around so that we don't get halfway 
1054         // through shifting and then realize we should have been in ArrayStorage mode.
1055         unsigned end = oldLength - count;
1056         if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
1057             for (unsigned i = startIndex; i < end; ++i) {
1058                 double v = butterfly->contiguousDouble()[i + count];
1059                 if (UNLIKELY(v != v)) {
1060                     startIndex = i;
1061                     return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
1062                 }
1063                 butterfly->contiguousDouble()[i] = v;
1064             }
1065         } else {
1066             memmove(butterfly->contiguousDouble().data() + startIndex,
1067                 butterfly->contiguousDouble().data() + startIndex + count,
1068                 sizeof(JSValue) * (end - startIndex));
1069         }
1070         for (unsigned i = end; i < oldLength; ++i)
1071             butterfly->contiguousDouble()[i] = PNaN;
1072         
1073         butterfly->setPublicLength(oldLength - count);
1074         return true;
1075     }
1076         
1077     case ArrayWithArrayStorage:
1078     case ArrayWithSlowPutArrayStorage:
1079         return shiftCountWithArrayStorage(vm, startIndex, count, arrayStorage());
1080         
1081     default:
1082         CRASH();
1083         return false;
1084     }
1085 }
1086
1087 // Returns true if the unshift can be handled, false to fallback.    
1088 bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
1089 {
1090     VM& vm = exec->vm();
1091     auto scope = DECLARE_THROW_SCOPE(vm);
1092
1093     unsigned length = storage->length();
1094
1095     RELEASE_ASSERT(startIndex <= length);
1096
1097     // If the array contains holes or is otherwise in an abnormal state,
1098     // use the generic algorithm in ArrayPrototype.
1099     if (storage->hasHoles() || storage->inSparseMode() || shouldUseSlowPut(indexingType()))
1100         return false;
1101
1102     bool moveFront = !startIndex || startIndex < length / 2;
1103
1104     unsigned vectorLength = storage->vectorLength();
1105
1106     // Need to have GC deferred around the unshiftCountSlowCase(), since that leaves the butterfly in
1107     // a weird state: some parts of it will be left uninitialized, which we will fill in here.
1108     DeferGC deferGC(vm.heap);
1109     auto locker = holdLock(*this);
1110     
1111     if (moveFront && storage->m_indexBias >= count) {
1112         Butterfly* newButterfly = storage->butterfly()->unshift(structure(), count);
1113         storage = newButterfly->arrayStorage();
1114         storage->m_indexBias -= count;
1115         storage->setVectorLength(vectorLength + count);
1116         setButterfly(vm, newButterfly);
1117     } else if (!moveFront && vectorLength - length >= count)
1118         storage = storage->butterfly()->arrayStorage();
1119     else if (unshiftCountSlowCase(locker, vm, deferGC, moveFront, count))
1120         storage = arrayStorage();
1121     else {
1122         throwOutOfMemoryError(exec, scope);
1123         return true;
1124     }
1125
1126     WriteBarrier<Unknown>* vector = storage->m_vector;
1127
1128     if (startIndex) {
1129         if (moveFront)
1130             memmove(vector, vector + count, startIndex * sizeof(JSValue));
1131         else if (length - startIndex)
1132             memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
1133     }
1134
1135     for (unsigned i = 0; i < count; i++)
1136         vector[i + startIndex].clear();
1137     
1138     return true;
1139 }
1140
1141 bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
1142 {
1143     VM& vm = exec->vm();
1144     auto scope = DECLARE_THROW_SCOPE(vm);
1145
1146     Butterfly* butterfly = m_butterfly.get();
1147     
1148     switch (indexingType()) {
1149     case ArrayClass:
1150     case ArrayWithUndecided:
1151         // We could handle this. But it shouldn't ever come up, so we won't.
1152         return false;
1153
1154     case ArrayWithInt32:
1155     case ArrayWithContiguous: {
1156         unsigned oldLength = butterfly->publicLength();
1157         
1158         // We may have to walk the entire array to do the unshift. We're willing to do so
1159         // only if it's not horribly slow.
1160         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX) {
1161             scope.release();
1162             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1163         }
1164         
1165         if (!ensureLength(vm, oldLength + count)) {
1166             throwOutOfMemoryError(exec, scope);
1167             return false;
1168         }
1169         butterfly = m_butterfly.get();
1170
1171         // We have to check for holes before we start moving things around so that we don't get halfway 
1172         // through shifting and then realize we should have been in ArrayStorage mode.
1173         for (unsigned i = oldLength; i-- > startIndex;) {
1174             JSValue v = butterfly->contiguous()[i].get();
1175             if (UNLIKELY(!v)) {
1176                 scope.release();
1177                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1178             }
1179         }
1180
1181         for (unsigned i = oldLength; i-- > startIndex;) {
1182             JSValue v = butterfly->contiguous()[i].get();
1183             ASSERT(v);
1184             butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
1185         }
1186         
1187         // Our memmoving of values around in the array could have concealed some of them from
1188         // the collector. Let's make sure that the collector scans this object again.
1189         vm.heap.writeBarrier(this);
1190         
1191         // NOTE: we're leaving being garbage in the part of the array that we shifted out
1192         // of. This is fine because the caller is required to store over that area, and
1193         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
1194         // as storing over an existing element.
1195         
1196         return true;
1197     }
1198         
1199     case ArrayWithDouble: {
1200         unsigned oldLength = butterfly->publicLength();
1201         
1202         // We may have to walk the entire array to do the unshift. We're willing to do so
1203         // only if it's not horribly slow.
1204         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX) {
1205             scope.release();
1206             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1207         }
1208         
1209         if (!ensureLength(vm, oldLength + count)) {
1210             throwOutOfMemoryError(exec, scope);
1211             return false;
1212         }
1213         butterfly = m_butterfly.get();
1214         
1215         // We have to check for holes before we start moving things around so that we don't get halfway 
1216         // through shifting and then realize we should have been in ArrayStorage mode.
1217         for (unsigned i = oldLength; i-- > startIndex;) {
1218             double v = butterfly->contiguousDouble()[i];
1219             if (UNLIKELY(v != v)) {
1220                 scope.release();
1221                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1222             }
1223         }
1224
1225         for (unsigned i = oldLength; i-- > startIndex;) {
1226             double v = butterfly->contiguousDouble()[i];
1227             ASSERT(v == v);
1228             butterfly->contiguousDouble()[i + count] = v;
1229         }
1230         
1231         // NOTE: we're leaving being garbage in the part of the array that we shifted out
1232         // of. This is fine because the caller is required to store over that area, and
1233         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
1234         // as storing over an existing element.
1235         
1236         return true;
1237     }
1238         
1239     case ArrayWithArrayStorage:
1240     case ArrayWithSlowPutArrayStorage:
1241         scope.release();
1242         return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
1243         
1244     default:
1245         CRASH();
1246         return false;
1247     }
1248 }
1249
1250 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
1251 {
1252     unsigned i = 0;
1253     unsigned vectorEnd;
1254     WriteBarrier<Unknown>* vector;
1255
1256     Butterfly* butterfly = m_butterfly.get();
1257     
1258     switch (indexingType()) {
1259     case ArrayClass:
1260         return;
1261         
1262     case ArrayWithUndecided: {
1263         vector = 0;
1264         vectorEnd = 0;
1265         break;
1266     }
1267         
1268     case ArrayWithInt32:
1269     case ArrayWithContiguous: {
1270         vectorEnd = butterfly->publicLength();
1271         vector = butterfly->contiguous().data();
1272         break;
1273     }
1274         
1275     case ArrayWithDouble: {
1276         vector = 0;
1277         vectorEnd = 0;
1278         for (; i < butterfly->publicLength(); ++i) {
1279             double v = butterfly->contiguousDouble()[i];
1280             if (v != v)
1281                 break;
1282             args.append(JSValue(JSValue::EncodeAsDouble, v));
1283         }
1284         break;
1285     }
1286     
1287     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1288         ArrayStorage* storage = butterfly->arrayStorage();
1289         
1290         vector = storage->m_vector;
1291         vectorEnd = min(storage->length(), storage->vectorLength());
1292         break;
1293     }
1294         
1295     default:
1296         CRASH();
1297 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1298         vector = 0;
1299         vectorEnd = 0;
1300         break;
1301 #endif
1302     }
1303     
1304     for (; i < vectorEnd; ++i) {
1305         WriteBarrier<Unknown>& v = vector[i];
1306         if (!v)
1307             break;
1308         args.append(v.get());
1309     }
1310
1311     // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case.
1312     for (; i < length(); ++i)
1313         args.append(get(exec, i));
1314 }
1315
1316 void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest, unsigned offset, unsigned length)
1317 {
1318     VM& vm = exec->vm();
1319     auto scope = DECLARE_THROW_SCOPE(vm);
1320
1321     unsigned i = offset;
1322     WriteBarrier<Unknown>* vector;
1323     unsigned vectorEnd;
1324     length += offset; // We like to think of the length as being our length, rather than the output length.
1325
1326     // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case.
1327     ASSERT(length == this->length());
1328
1329     Butterfly* butterfly = m_butterfly.get();
1330     switch (indexingType()) {
1331     case ArrayClass:
1332         return;
1333         
1334     case ArrayWithUndecided: {
1335         vector = 0;
1336         vectorEnd = 0;
1337         break;
1338     }
1339         
1340     case ArrayWithInt32:
1341     case ArrayWithContiguous: {
1342         vector = butterfly->contiguous().data();
1343         vectorEnd = butterfly->publicLength();
1344         break;
1345     }
1346         
1347     case ArrayWithDouble: {
1348         vector = 0;
1349         vectorEnd = 0;
1350         for (; i < butterfly->publicLength(); ++i) {
1351             ASSERT(i < butterfly->vectorLength());
1352             double v = butterfly->contiguousDouble()[i];
1353             if (v != v)
1354                 break;
1355             exec->r(firstElementDest + i - offset) = JSValue(JSValue::EncodeAsDouble, v);
1356         }
1357         break;
1358     }
1359         
1360     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1361         ArrayStorage* storage = butterfly->arrayStorage();
1362         vector = storage->m_vector;
1363         vectorEnd = min(length, storage->vectorLength());
1364         break;
1365     }
1366         
1367     default:
1368         CRASH();
1369 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1370         vector = 0;
1371         vectorEnd = 0;
1372         break;
1373 #endif
1374     }
1375     
1376     for (; i < vectorEnd; ++i) {
1377         WriteBarrier<Unknown>& v = vector[i];
1378         if (!v)
1379             break;
1380         exec->r(firstElementDest + i - offset) = v.get();
1381     }
1382     
1383     for (; i < length; ++i) {
1384         exec->r(firstElementDest + i - offset) = get(exec, i);
1385         RETURN_IF_EXCEPTION(scope, void());
1386     }
1387 }
1388
1389 } // namespace JSC