Source/JavaScriptCore/runtime/JSArray.cpp

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