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