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