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