8be274a24b8e2798abe6158c69ba2b3d71acc285
[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 "Reject.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 == exec->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 reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
137         // from ES5.1 8.12.9 7.b.
138         if (descriptor.enumerablePresent() && descriptor.enumerable())
139             return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
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 reject(exec, throwException, UnconfigurablePropertyChangeAccessMechanismError);
145         // from ES5.1 8.12.9 10.a.
146         if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
147             return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
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 reject(exec, throwException, "Attempting to change value of a readonly property.");
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 reject(exec, throwException, "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     unsigned length = storage->length();
402     
403     // If the length is read only then we enter sparse mode, so should enter the following 'if'.
404     ASSERT(isLengthWritable() || storage->m_sparseMap);
405
406     if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
407         // Fail if the length is not writable.
408         if (map->lengthIsReadOnly())
409             return reject(exec, throwException, ReadonlyPropertyWriteError);
410
411         if (newLength < length) {
412             // Copy any keys we might be interested in into a vector.
413             Vector<unsigned, 0, UnsafeVectorOverflow> keys;
414             keys.reserveInitialCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
415             SparseArrayValueMap::const_iterator end = map->end();
416             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
417                 unsigned index = static_cast<unsigned>(it->key);
418                 if (index < length && index >= newLength)
419                     keys.append(index);
420             }
421
422             // Check if the array is in sparse mode. If so there may be non-configurable
423             // properties, so we have to perform deletion with caution, if not we can
424             // delete values in any order.
425             if (map->sparseMode()) {
426                 qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
427                 unsigned i = keys.size();
428                 while (i) {
429                     unsigned index = keys[--i];
430                     SparseArrayValueMap::iterator it = map->find(index);
431                     ASSERT(it != map->notFound());
432                     if (it->value.attributes & DontDelete) {
433                         storage->setLength(index + 1);
434                         return reject(exec, throwException, "Unable to delete property.");
435                     }
436                     map->remove(it);
437                 }
438             } else {
439                 for (unsigned i = 0; i < keys.size(); ++i)
440                     map->remove(keys[i]);
441                 if (map->isEmpty())
442                     deallocateSparseIndexMap();
443             }
444         }
445     }
446
447     if (newLength < length) {
448         // Delete properties from the vector.
449         unsigned usedVectorLength = min(length, storage->vectorLength());
450         for (unsigned i = newLength; i < usedVectorLength; ++i) {
451             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
452             bool hadValue = !!valueSlot;
453             valueSlot.clear();
454             storage->m_numValuesInVector -= hadValue;
455         }
456     }
457
458     storage->setLength(newLength);
459
460     return true;
461 }
462
463 bool JSArray::appendMemcpy(ExecState* exec, VM& vm, unsigned startIndex, JSC::JSArray* otherArray)
464 {
465     auto scope = DECLARE_THROW_SCOPE(vm);
466
467     if (!canFastCopy(vm, otherArray))
468         return false;
469
470     IndexingType type = indexingType();
471     IndexingType copyType = mergeIndexingTypeForCopying(otherArray->indexingType());
472     if (type == ArrayWithUndecided && copyType != NonArray) {
473         if (copyType == ArrayWithInt32)
474             convertUndecidedToInt32(vm);
475         else if (copyType == ArrayWithDouble)
476             convertUndecidedToDouble(vm);
477         else if (copyType == ArrayWithContiguous)
478             convertUndecidedToContiguous(vm);
479         else {
480             ASSERT(copyType == ArrayWithUndecided);
481             return true;
482         }
483     } else if (type != copyType)
484         return false;
485
486     unsigned otherLength = otherArray->length();
487     unsigned newLength = startIndex + otherLength;
488     if (newLength >= MIN_SPARSE_ARRAY_INDEX)
489         return false;
490
491     if (!ensureLength(vm, newLength)) {
492         throwOutOfMemoryError(exec, scope);
493         return false;
494     }
495     ASSERT(copyType == indexingType());
496
497     if (type == ArrayWithDouble)
498         memcpy(butterfly()->contiguousDouble().data() + startIndex, otherArray->butterfly()->contiguousDouble().data(), sizeof(JSValue) * otherLength);
499     else
500         memcpy(butterfly()->contiguous().data() + startIndex, otherArray->butterfly()->contiguous().data(), sizeof(JSValue) * otherLength);
501
502     return true;
503 }
504
505 bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
506 {
507     VM& vm = exec->vm();
508     auto scope = DECLARE_THROW_SCOPE(vm);
509
510     Butterfly* butterfly = m_butterfly.get();
511     switch (indexingType()) {
512     case ArrayClass:
513         if (!newLength)
514             return true;
515         if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
516             return setLengthWithArrayStorage(
517                 exec, newLength, throwException,
518                 ensureArrayStorage(vm));
519         }
520         createInitialUndecided(vm, newLength);
521         return true;
522         
523     case ArrayWithUndecided:
524     case ArrayWithInt32:
525     case ArrayWithDouble:
526     case ArrayWithContiguous: {
527         if (newLength == butterfly->publicLength())
528             return true;
529         if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
530             || (newLength >= MIN_SPARSE_ARRAY_INDEX
531                 && !isDenseEnoughForVector(newLength, countElements()))) {
532             return setLengthWithArrayStorage(
533                 exec, newLength, throwException,
534                 ensureArrayStorage(vm));
535         }
536         if (newLength > butterfly->publicLength()) {
537             if (!ensureLength(vm, newLength)) {
538                 throwOutOfMemoryError(exec, scope);
539                 return false;
540             }
541             return true;
542         }
543
544         unsigned lengthToClear = butterfly->publicLength() - newLength;
545         unsigned costToAllocateNewButterfly = 64; // a heuristic.
546         if (lengthToClear > newLength && lengthToClear > costToAllocateNewButterfly) {
547             reallocateAndShrinkButterfly(vm, newLength);
548             return true;
549         }
550
551         if (indexingType() == ArrayWithDouble) {
552             for (unsigned i = butterfly->publicLength(); i-- > newLength;)
553                 butterfly->contiguousDouble()[i] = PNaN;
554         } else {
555             for (unsigned i = butterfly->publicLength(); i-- > newLength;)
556                 butterfly->contiguous()[i].clear();
557         }
558         butterfly->setPublicLength(newLength);
559         return true;
560     }
561         
562     case ArrayWithArrayStorage:
563     case ArrayWithSlowPutArrayStorage:
564         return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
565         
566     default:
567         CRASH();
568         return false;
569     }
570 }
571
572 JSValue JSArray::pop(ExecState* exec)
573 {
574     VM& vm = exec->vm();
575     auto scope = DECLARE_THROW_SCOPE(vm);
576
577     Butterfly* butterfly = m_butterfly.get();
578     
579     switch (indexingType()) {
580     case ArrayClass:
581         return jsUndefined();
582         
583     case ArrayWithUndecided:
584         if (!butterfly->publicLength())
585             return jsUndefined();
586         // We have nothing but holes. So, drop down to the slow version.
587         break;
588         
589     case ArrayWithInt32:
590     case ArrayWithContiguous: {
591         unsigned length = butterfly->publicLength();
592         
593         if (!length--)
594             return jsUndefined();
595         
596         RELEASE_ASSERT(length < butterfly->vectorLength());
597         JSValue value = butterfly->contiguous()[length].get();
598         if (value) {
599             butterfly->contiguous()[length].clear();
600             butterfly->setPublicLength(length);
601             return value;
602         }
603         break;
604     }
605         
606     case ArrayWithDouble: {
607         unsigned length = butterfly->publicLength();
608         
609         if (!length--)
610             return jsUndefined();
611         
612         RELEASE_ASSERT(length < butterfly->vectorLength());
613         double value = butterfly->contiguousDouble()[length];
614         if (value == value) {
615             butterfly->contiguousDouble()[length] = PNaN;
616             butterfly->setPublicLength(length);
617             return JSValue(JSValue::EncodeAsDouble, value);
618         }
619         break;
620     }
621         
622     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
623         ArrayStorage* storage = butterfly->arrayStorage();
624     
625         unsigned length = storage->length();
626         if (!length) {
627             if (!isLengthWritable())
628                 throwTypeError(exec, scope, ReadonlyPropertyWriteError);
629             return jsUndefined();
630         }
631
632         unsigned index = length - 1;
633         if (index < storage->vectorLength()) {
634             WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
635             if (valueSlot) {
636                 --storage->m_numValuesInVector;
637                 JSValue element = valueSlot.get();
638                 valueSlot.clear();
639             
640                 RELEASE_ASSERT(isLengthWritable());
641                 storage->setLength(index);
642                 return element;
643             }
644         }
645         break;
646     }
647         
648     default:
649         CRASH();
650         return JSValue();
651     }
652     
653     unsigned index = getArrayLength() - 1;
654     // Let element be the result of calling the [[Get]] internal method of O with argument indx.
655     JSValue element = get(exec, index);
656     RETURN_IF_EXCEPTION(scope, JSValue());
657     // Call the [[Delete]] internal method of O with arguments indx and true.
658     if (!deletePropertyByIndex(this, exec, index)) {
659         throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
660         return jsUndefined();
661     }
662     // Call the [[Put]] internal method of O with arguments "length", indx, and true.
663     setLength(exec, index, true);
664     // Return element.
665     return element;
666 }
667
668 // Push & putIndex are almost identical, with two small differences.
669 //  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
670 //  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
671 void JSArray::push(ExecState* exec, JSValue value)
672 {
673     VM& vm = exec->vm();
674     auto scope = DECLARE_THROW_SCOPE(vm);
675
676     Butterfly* butterfly = m_butterfly.get();
677     
678     switch (indexingType()) {
679     case ArrayClass: {
680         createInitialUndecided(vm, 0);
681         FALLTHROUGH;
682     }
683         
684     case ArrayWithUndecided: {
685         convertUndecidedForValue(vm, value);
686         push(exec, value);
687         return;
688     }
689         
690     case ArrayWithInt32: {
691         if (!value.isInt32()) {
692             convertInt32ForValue(vm, value);
693             push(exec, value);
694             return;
695         }
696
697         unsigned length = butterfly->publicLength();
698         ASSERT(length <= butterfly->vectorLength());
699         if (length < butterfly->vectorLength()) {
700             butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value);
701             butterfly->setPublicLength(length + 1);
702             return;
703         }
704         
705         if (length > MAX_ARRAY_INDEX) {
706             methodTable(vm)->putByIndex(this, exec, length, value, true);
707             if (!scope.exception())
708                 throwException(exec, scope, createRangeError(exec, ASCIILiteral("Invalid array length")));
709             return;
710         }
711         
712         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
713         return;
714     }
715
716     case ArrayWithContiguous: {
717         unsigned length = butterfly->publicLength();
718         ASSERT(length <= butterfly->vectorLength());
719         if (length < butterfly->vectorLength()) {
720             butterfly->contiguous()[length].set(vm, this, value);
721             butterfly->setPublicLength(length + 1);
722             return;
723         }
724         
725         if (length > MAX_ARRAY_INDEX) {
726             methodTable(vm)->putByIndex(this, exec, length, value, true);
727             if (!scope.exception())
728                 throwException(exec, scope, createRangeError(exec, ASCIILiteral("Invalid array length")));
729             return;
730         }
731         
732         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value);
733         return;
734     }
735         
736     case ArrayWithDouble: {
737         if (!value.isNumber()) {
738             convertDoubleToContiguous(vm);
739             push(exec, value);
740             return;
741         }
742         double valueAsDouble = value.asNumber();
743         if (valueAsDouble != valueAsDouble) {
744             convertDoubleToContiguous(vm);
745             push(exec, value);
746             return;
747         }
748
749         unsigned length = butterfly->publicLength();
750         ASSERT(length <= butterfly->vectorLength());
751         if (length < butterfly->vectorLength()) {
752             butterfly->contiguousDouble()[length] = valueAsDouble;
753             butterfly->setPublicLength(length + 1);
754             return;
755         }
756         
757         if (length > MAX_ARRAY_INDEX) {
758             methodTable(vm)->putByIndex(this, exec, length, value, true);
759             if (!scope.exception())
760                 throwException(exec, scope, createRangeError(exec, ASCIILiteral("Invalid array length")));
761             return;
762         }
763         
764         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value);
765         break;
766     }
767         
768     case ArrayWithSlowPutArrayStorage: {
769         unsigned oldLength = length();
770         bool putResult = false;
771         if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true, putResult)) {
772             if (!scope.exception() && oldLength < 0xFFFFFFFFu)
773                 setLength(exec, oldLength + 1, true);
774             return;
775         }
776         FALLTHROUGH;
777     }
778         
779     case ArrayWithArrayStorage: {
780         ArrayStorage* storage = butterfly->arrayStorage();
781
782         // Fast case - push within vector, always update m_length & m_numValuesInVector.
783         unsigned length = storage->length();
784         if (length < storage->vectorLength()) {
785             storage->m_vector[length].set(vm, this, value);
786             storage->setLength(length + 1);
787             ++storage->m_numValuesInVector;
788             return;
789         }
790
791         // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
792         if (storage->length() > MAX_ARRAY_INDEX) {
793             methodTable(vm)->putByIndex(this, exec, storage->length(), value, true);
794             // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
795             if (!scope.exception())
796                 throwException(exec, scope, createRangeError(exec, ASCIILiteral("Invalid array length")));
797             return;
798         }
799
800         // Handled the same as putIndex.
801         putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
802         break;
803     }
804         
805     default:
806         RELEASE_ASSERT_NOT_REACHED();
807     }
808 }
809
810 JSArray* JSArray::fastSlice(ExecState& exec, unsigned startIndex, unsigned count)
811 {
812     auto arrayType = indexingType();
813     switch (arrayType) {
814     case ArrayWithDouble:
815     case ArrayWithInt32:
816     case ArrayWithContiguous: {
817         VM& vm = exec.vm();
818         if (count >= MIN_SPARSE_ARRAY_INDEX || structure(vm)->holesMustForwardToPrototype(vm))
819             return nullptr;
820
821         Structure* resultStructure = exec.lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(arrayType);
822         JSArray* resultArray = JSArray::tryCreateUninitialized(vm, resultStructure, count);
823         if (!resultArray)
824             return nullptr;
825
826         auto& resultButterfly = *resultArray->butterfly();
827         if (arrayType == ArrayWithDouble)
828             memcpy(resultButterfly.contiguousDouble().data(), m_butterfly.get()->contiguousDouble().data() + startIndex, sizeof(JSValue) * count);
829         else
830             memcpy(resultButterfly.contiguous().data(), m_butterfly.get()->contiguous().data() + startIndex, sizeof(JSValue) * count);
831         resultButterfly.setPublicLength(count);
832
833         return resultArray;
834     }
835     default:
836         return nullptr;
837     }
838 }
839
840 bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage)
841 {
842     unsigned oldLength = storage->length();
843     RELEASE_ASSERT(count <= oldLength);
844     
845     // If the array contains holes or is otherwise in an abnormal state,
846     // use the generic algorithm in ArrayPrototype.
847     if ((storage->hasHoles() && this->structure(vm)->holesMustForwardToPrototype(vm)) 
848         || hasSparseMap() 
849         || shouldUseSlowPut(indexingType())) {
850         return false;
851     }
852
853     if (!oldLength)
854         return true;
855     
856     unsigned length = oldLength - count;
857     
858     storage->m_numValuesInVector -= count;
859     storage->setLength(length);
860     
861     unsigned vectorLength = storage->vectorLength();
862     if (!vectorLength)
863         return true;
864     
865     if (startIndex >= vectorLength)
866         return true;
867     
868     if (startIndex + count > vectorLength)
869         count = vectorLength - startIndex;
870     
871     unsigned usedVectorLength = min(vectorLength, oldLength);
872     
873     unsigned numElementsBeforeShiftRegion = startIndex;
874     unsigned firstIndexAfterShiftRegion = startIndex + count;
875     unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
876     ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
877
878     // The point of this comparison seems to be to minimize the amount of elements that have to 
879     // be moved during a shift operation.
880     if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
881         // The number of elements before the shift region is less than the number of elements
882         // after the shift region, so we move the elements before to the right.
883         if (numElementsBeforeShiftRegion) {
884             RELEASE_ASSERT(count + startIndex <= vectorLength);
885             if (storage->hasHoles()) {
886                 for (unsigned i = startIndex; i-- > 0;) {
887                     unsigned destinationIndex = count + i;
888                     JSValue source = storage->m_vector[i].get();
889                     JSValue dest = storage->m_vector[destinationIndex].get();
890                     // Any time we overwrite a hole we know we overcounted the number of values we removed 
891                     // when we subtracted count from m_numValuesInVector above.
892                     if (!dest && destinationIndex >= firstIndexAfterShiftRegion)
893                         storage->m_numValuesInVector++;
894                     storage->m_vector[count + i].setWithoutWriteBarrier(source);
895                 }
896             } else {
897                 memmove(storage->m_vector + count,
898                     storage->m_vector,
899                     sizeof(JSValue) * startIndex);
900             }
901         }
902         // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
903         // the start of the Butterfly, which needs to point at the first indexed property in the used
904         // portion of the vector.
905         Butterfly* butterfly = m_butterfly.get()->shift(structure(), count);
906         m_butterfly.setWithoutBarrier(butterfly);
907         storage = butterfly->arrayStorage();
908         storage->m_indexBias += count;
909
910         // Since we're consuming part of the vector by moving its beginning to the left,
911         // we need to modify the vector length appropriately.
912         storage->setVectorLength(vectorLength - count);
913     } else {
914         // The number of elements before the shift region is greater than or equal to the number 
915         // of elements after the shift region, so we move the elements after the shift region to the left.
916         if (storage->hasHoles()) {
917             for (unsigned i = 0; i < numElementsAfterShiftRegion; ++i) {
918                 unsigned destinationIndex = startIndex + i;
919                 JSValue source = storage->m_vector[firstIndexAfterShiftRegion + i].get();
920                 JSValue dest = storage->m_vector[destinationIndex].get();
921                 // Any time we overwrite a hole we know we overcounted the number of values we removed 
922                 // when we subtracted count from m_numValuesInVector above.
923                 if (!dest && destinationIndex < firstIndexAfterShiftRegion)
924                     storage->m_numValuesInVector++;
925                 storage->m_vector[startIndex + i].setWithoutWriteBarrier(source);
926             }
927         } else {
928             memmove(storage->m_vector + startIndex,
929                 storage->m_vector + firstIndexAfterShiftRegion,
930                 sizeof(JSValue) * numElementsAfterShiftRegion);
931         }
932         // Clear the slots of the elements we just moved.
933         unsigned startOfEmptyVectorTail = usedVectorLength - count;
934         for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i)
935             storage->m_vector[i].clear();
936         // We don't modify the index bias or the Butterfly pointer in this case because we're not changing 
937         // the start of the Butterfly, which needs to point at the first indexed property in the used 
938         // portion of the vector. We also don't modify the vector length because we're not actually changing
939         // its length; we're just using less of it.
940     }
941     
942     return true;
943 }
944
945 bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count)
946 {
947     VM& vm = exec->vm();
948     RELEASE_ASSERT(count > 0);
949
950     Butterfly* butterfly = m_butterfly.get();
951     
952     switch (indexingType()) {
953     case ArrayClass:
954         return true;
955         
956     case ArrayWithUndecided:
957         // Don't handle this because it's confusing and it shouldn't come up.
958         return false;
959         
960     case ArrayWithInt32:
961     case ArrayWithContiguous: {
962         unsigned oldLength = butterfly->publicLength();
963         RELEASE_ASSERT(count <= oldLength);
964         
965         // We may have to walk the entire array to do the shift. We're willing to do
966         // so only if it's not horribly slow.
967         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
968             return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
969
970         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
971         // is totally not fine, since we might have to read from the proto chain.
972         // We have to check for holes before we start moving things around so that we don't get halfway 
973         // through shifting and then realize we should have been in ArrayStorage mode.
974         unsigned end = oldLength - count;
975         if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
976             for (unsigned i = startIndex; i < end; ++i) {
977                 JSValue v = butterfly->contiguous()[i + count].get();
978                 if (UNLIKELY(!v)) {
979                     startIndex = i;
980                     return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
981                 }
982                 butterfly->contiguous()[i].setWithoutWriteBarrier(v);
983             }
984         } else {
985             memmove(butterfly->contiguous().data() + startIndex, 
986                 butterfly->contiguous().data() + startIndex + count, 
987                 sizeof(JSValue) * (end - startIndex));
988         }
989
990         for (unsigned i = end; i < oldLength; ++i)
991             butterfly->contiguous()[i].clear();
992         
993         butterfly->setPublicLength(oldLength - count);
994         return true;
995     }
996         
997     case ArrayWithDouble: {
998         unsigned oldLength = butterfly->publicLength();
999         RELEASE_ASSERT(count <= oldLength);
1000         
1001         // We may have to walk the entire array to do the shift. We're willing to do
1002         // so only if it's not horribly slow.
1003         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
1004             return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
1005
1006         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
1007         // is totally not fine, since we might have to read from the proto chain.
1008         // We have to check for holes before we start moving things around so that we don't get halfway 
1009         // through shifting and then realize we should have been in ArrayStorage mode.
1010         unsigned end = oldLength - count;
1011         if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
1012             for (unsigned i = startIndex; i < end; ++i) {
1013                 double v = butterfly->contiguousDouble()[i + count];
1014                 if (UNLIKELY(v != v)) {
1015                     startIndex = i;
1016                     return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
1017                 }
1018                 butterfly->contiguousDouble()[i] = v;
1019             }
1020         } else {
1021             memmove(butterfly->contiguousDouble().data() + startIndex,
1022                 butterfly->contiguousDouble().data() + startIndex + count,
1023                 sizeof(JSValue) * (end - startIndex));
1024         }
1025         for (unsigned i = end; i < oldLength; ++i)
1026             butterfly->contiguousDouble()[i] = PNaN;
1027         
1028         butterfly->setPublicLength(oldLength - count);
1029         return true;
1030     }
1031         
1032     case ArrayWithArrayStorage:
1033     case ArrayWithSlowPutArrayStorage:
1034         return shiftCountWithArrayStorage(vm, startIndex, count, arrayStorage());
1035         
1036     default:
1037         CRASH();
1038         return false;
1039     }
1040 }
1041
1042 // Returns true if the unshift can be handled, false to fallback.    
1043 bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
1044 {
1045     VM& vm = exec->vm();
1046     auto scope = DECLARE_THROW_SCOPE(vm);
1047
1048     unsigned length = storage->length();
1049
1050     RELEASE_ASSERT(startIndex <= length);
1051
1052     // If the array contains holes or is otherwise in an abnormal state,
1053     // use the generic algorithm in ArrayPrototype.
1054     if (storage->hasHoles() || storage->inSparseMode() || shouldUseSlowPut(indexingType()))
1055         return false;
1056
1057     bool moveFront = !startIndex || startIndex < length / 2;
1058
1059     unsigned vectorLength = storage->vectorLength();
1060
1061     // Need to have GC deferred around the unshiftCountSlowCase(), since that leaves the butterfly in
1062     // a weird state: some parts of it will be left uninitialized, which we will fill in here.
1063     DeferGC deferGC(vm.heap);
1064     
1065     if (moveFront && storage->m_indexBias >= count) {
1066         Butterfly* newButterfly = storage->butterfly()->unshift(structure(), count);
1067         storage = newButterfly->arrayStorage();
1068         storage->m_indexBias -= count;
1069         storage->setVectorLength(vectorLength + count);
1070         setButterflyWithoutChangingStructure(vm, newButterfly);
1071     } else if (!moveFront && vectorLength - length >= count)
1072         storage = storage->butterfly()->arrayStorage();
1073     else if (unshiftCountSlowCase(vm, deferGC, moveFront, count))
1074         storage = arrayStorage();
1075     else {
1076         throwOutOfMemoryError(exec, scope);
1077         return true;
1078     }
1079
1080     WriteBarrier<Unknown>* vector = storage->m_vector;
1081
1082     if (startIndex) {
1083         if (moveFront)
1084             memmove(vector, vector + count, startIndex * sizeof(JSValue));
1085         else if (length - startIndex)
1086             memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
1087     }
1088
1089     for (unsigned i = 0; i < count; i++)
1090         vector[i + startIndex].clear();
1091     return true;
1092 }
1093
1094 bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
1095 {
1096     VM& vm = exec->vm();
1097     auto scope = DECLARE_THROW_SCOPE(vm);
1098
1099     Butterfly* butterfly = m_butterfly.get();
1100     
1101     switch (indexingType()) {
1102     case ArrayClass:
1103     case ArrayWithUndecided:
1104         // We could handle this. But it shouldn't ever come up, so we won't.
1105         return false;
1106
1107     case ArrayWithInt32:
1108     case ArrayWithContiguous: {
1109         unsigned oldLength = butterfly->publicLength();
1110         
1111         // We may have to walk the entire array to do the unshift. We're willing to do so
1112         // only if it's not horribly slow.
1113         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
1114             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1115         
1116         if (!ensureLength(vm, oldLength + count)) {
1117             throwOutOfMemoryError(exec, scope);
1118             return false;
1119         }
1120         butterfly = m_butterfly.get();
1121
1122         // We have to check for holes before we start moving things around so that we don't get halfway 
1123         // through shifting and then realize we should have been in ArrayStorage mode.
1124         for (unsigned i = oldLength; i-- > startIndex;) {
1125             JSValue v = butterfly->contiguous()[i].get();
1126             if (UNLIKELY(!v))
1127                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1128         }
1129
1130         for (unsigned i = oldLength; i-- > startIndex;) {
1131             JSValue v = butterfly->contiguous()[i].get();
1132             ASSERT(v);
1133             butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
1134         }
1135         
1136         // NOTE: we're leaving being garbage in the part of the array that we shifted out
1137         // of. This is fine because the caller is required to store over that area, and
1138         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
1139         // as storing over an existing element.
1140         
1141         return true;
1142     }
1143         
1144     case ArrayWithDouble: {
1145         unsigned oldLength = butterfly->publicLength();
1146         
1147         // We may have to walk the entire array to do the unshift. We're willing to do so
1148         // only if it's not horribly slow.
1149         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
1150             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1151         
1152         if (!ensureLength(vm, oldLength + count)) {
1153             throwOutOfMemoryError(exec, scope);
1154             return false;
1155         }
1156         butterfly = m_butterfly.get();
1157         
1158         // We have to check for holes before we start moving things around so that we don't get halfway 
1159         // through shifting and then realize we should have been in ArrayStorage mode.
1160         for (unsigned i = oldLength; i-- > startIndex;) {
1161             double v = butterfly->contiguousDouble()[i];
1162             if (UNLIKELY(v != v))
1163                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(vm));
1164         }
1165
1166         for (unsigned i = oldLength; i-- > startIndex;) {
1167             double v = butterfly->contiguousDouble()[i];
1168             ASSERT(v == v);
1169             butterfly->contiguousDouble()[i + count] = v;
1170         }
1171         
1172         // NOTE: we're leaving being garbage in the part of the array that we shifted out
1173         // of. This is fine because the caller is required to store over that area, and
1174         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
1175         // as storing over an existing element.
1176         
1177         return true;
1178     }
1179         
1180     case ArrayWithArrayStorage:
1181     case ArrayWithSlowPutArrayStorage:
1182         return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
1183         
1184     default:
1185         CRASH();
1186         return false;
1187     }
1188 }
1189
1190 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
1191 {
1192     unsigned i = 0;
1193     unsigned vectorEnd;
1194     WriteBarrier<Unknown>* vector;
1195
1196     Butterfly* butterfly = m_butterfly.get();
1197     
1198     switch (indexingType()) {
1199     case ArrayClass:
1200         return;
1201         
1202     case ArrayWithUndecided: {
1203         vector = 0;
1204         vectorEnd = 0;
1205         break;
1206     }
1207         
1208     case ArrayWithInt32:
1209     case ArrayWithContiguous: {
1210         vectorEnd = butterfly->publicLength();
1211         vector = butterfly->contiguous().data();
1212         break;
1213     }
1214         
1215     case ArrayWithDouble: {
1216         vector = 0;
1217         vectorEnd = 0;
1218         for (; i < butterfly->publicLength(); ++i) {
1219             double v = butterfly->contiguousDouble()[i];
1220             if (v != v)
1221                 break;
1222             args.append(JSValue(JSValue::EncodeAsDouble, v));
1223         }
1224         break;
1225     }
1226     
1227     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1228         ArrayStorage* storage = butterfly->arrayStorage();
1229         
1230         vector = storage->m_vector;
1231         vectorEnd = min(storage->length(), storage->vectorLength());
1232         break;
1233     }
1234         
1235     default:
1236         CRASH();
1237 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1238         vector = 0;
1239         vectorEnd = 0;
1240         break;
1241 #endif
1242     }
1243     
1244     for (; i < vectorEnd; ++i) {
1245         WriteBarrier<Unknown>& v = vector[i];
1246         if (!v)
1247             break;
1248         args.append(v.get());
1249     }
1250
1251     // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case.
1252     for (; i < length(); ++i)
1253         args.append(get(exec, i));
1254 }
1255
1256 void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest, unsigned offset, unsigned length)
1257 {
1258     VM& vm = exec->vm();
1259     auto scope = DECLARE_THROW_SCOPE(vm);
1260
1261     unsigned i = offset;
1262     WriteBarrier<Unknown>* vector;
1263     unsigned vectorEnd;
1264     length += offset; // We like to think of the length as being our length, rather than the output length.
1265
1266     // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case.
1267     ASSERT(length == this->length());
1268
1269     Butterfly* butterfly = m_butterfly.get();
1270     switch (indexingType()) {
1271     case ArrayClass:
1272         return;
1273         
1274     case ArrayWithUndecided: {
1275         vector = 0;
1276         vectorEnd = 0;
1277         break;
1278     }
1279         
1280     case ArrayWithInt32:
1281     case ArrayWithContiguous: {
1282         vector = butterfly->contiguous().data();
1283         vectorEnd = butterfly->publicLength();
1284         break;
1285     }
1286         
1287     case ArrayWithDouble: {
1288         vector = 0;
1289         vectorEnd = 0;
1290         for (; i < butterfly->publicLength(); ++i) {
1291             ASSERT(i < butterfly->vectorLength());
1292             double v = butterfly->contiguousDouble()[i];
1293             if (v != v)
1294                 break;
1295             exec->r(firstElementDest + i - offset) = JSValue(JSValue::EncodeAsDouble, v);
1296         }
1297         break;
1298     }
1299         
1300     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1301         ArrayStorage* storage = butterfly->arrayStorage();
1302         vector = storage->m_vector;
1303         vectorEnd = min(length, storage->vectorLength());
1304         break;
1305     }
1306         
1307     default:
1308         CRASH();
1309 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1310         vector = 0;
1311         vectorEnd = 0;
1312         break;
1313 #endif
1314     }
1315     
1316     for (; i < vectorEnd; ++i) {
1317         WriteBarrier<Unknown>& v = vector[i];
1318         if (!v)
1319             break;
1320         exec->r(firstElementDest + i - offset) = v.get();
1321     }
1322     
1323     for (; i < length; ++i) {
1324         exec->r(firstElementDest + i - offset) = get(exec, i);
1325         RETURN_IF_EXCEPTION(scope, void());
1326     }
1327 }
1328
1329 } // namespace JSC