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