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