Source/JavaScriptCore/runtime/JSArray.cpp

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