Source/JavaScriptCore/runtime/JSArray.cpp

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