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