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