X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/b80e619319b1def83d1e8b4f84042b661be1be7f..refs/heads/master:/runtime/JSArray.cpp diff --git a/runtime/JSArray.cpp b/runtime/JSArray.cpp index eb778ed..2c5a19a 100644 --- a/runtime/JSArray.cpp +++ b/runtime/JSArray.cpp @@ -1,6 +1,6 @@ /* * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) - * Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved. + * Copyright (C) 2003, 2007, 2008, 2009, 2012, 2013, 2015 Apple Inc. All rights reserved. * Copyright (C) 2003 Peter Kelly (pmk@post.com) * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com) * @@ -24,1056 +24,1180 @@ #include "JSArray.h" #include "ArrayPrototype.h" +#include "ButterflyInlines.h" #include "CachedCall.h" +#include "CopiedSpace.h" #include "Error.h" #include "Executable.h" +#include "GetterSetter.h" +#include "IndexingHeaderInlines.h" +#include "JSCInlines.h" #include "PropertyNameArray.h" -#include +#include "Reject.h" #include -#include -#include - -#define CHECK_ARRAY_CONSISTENCY 0 using namespace std; using namespace WTF; namespace JSC { -ASSERT_CLASS_FITS_IN_CELL(JSArray); - -// Overview of JSArray -// -// Properties of JSArray objects may be stored in one of three locations: -// * The regular JSObject property map. -// * A storage vector. -// * A sparse map of array entries. -// -// Properties with non-numeric identifiers, with identifiers that are not representable -// as an unsigned integer, or where the value is greater than MAX_ARRAY_INDEX -// (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit -// integer) are not considered array indices and will be stored in the JSObject property map. -// -// All properties with a numeric identifer, representable as an unsigned integer i, -// where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the -// storage vector or the sparse map. An array index i will be handled in the following -// fashion: -// -// * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector. -// * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either -// be stored in the storage vector or in the sparse array, depending on the density of -// data that would be stored in the vector (a vector being used where at least -// (1 / minDensityMultiplier) of the entries would be populated). -// * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored -// in the sparse array. - -// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize -// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage -// size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(JSValue)) + -// (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t). -#define MAX_STORAGE_VECTOR_LENGTH static_cast((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue)) - -// These values have to be macros to be used in max() and min() without introducing -// a PIC branch in Mach-O binaries, see . -#define MIN_SPARSE_ARRAY_INDEX 10000U -#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1) -// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer. -#define MAX_ARRAY_INDEX 0xFFFFFFFEU - -// Our policy for when to use a vector and when to use a sparse map. -// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector. -// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector -// as long as it is 1/8 full. If more sparse than that, we use a map. -static const unsigned minDensityMultiplier = 8; - -const ClassInfo JSArray::info = {"Array", 0, 0, 0}; - -static inline size_t storageSize(unsigned vectorLength) -{ - ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH); - - // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH) - // - as asserted above - the following calculation cannot overflow. - size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue)); - // Assertion to detect integer overflow in previous calculation (should not be possible, provided that - // MAX_STORAGE_VECTOR_LENGTH is correctly defined). - ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue)))); - - return size; -} - -static inline unsigned increasedVectorLength(unsigned newLength) -{ - ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH); - - // Mathematically equivalent to: - // increasedLength = (newLength * 3 + 1) / 2; - // or: - // increasedLength = (unsigned)ceil(newLength * 1.5)); - // This form is not prone to internal overflow. - unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1); - ASSERT(increasedLength >= newLength); - - return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH); -} - -static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues) -{ - return length / minDensityMultiplier <= numValues; -} - -#if !CHECK_ARRAY_CONSISTENCY +STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray); -inline void JSArray::checkConsistency(ConsistencyCheckType) -{ -} - -#endif - -JSArray::JSArray(NonNullPassRefPtr structure) - : JSObject(structure) -{ - unsigned initialCapacity = 0; - - m_storage = static_cast(fastZeroedMalloc(storageSize(initialCapacity))); - m_vectorLength = initialCapacity; +const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, CREATE_METHOD_TABLE(JSArray)}; - checkConsistency(); -} - -JSArray::JSArray(NonNullPassRefPtr structure, unsigned initialLength) - : JSObject(structure) +Butterfly* createArrayButterflyInDictionaryIndexingMode( + VM& vm, JSCell* intendedOwner, unsigned initialLength) { - unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX); - - m_storage = static_cast(fastMalloc(storageSize(initialCapacity))); - m_storage->m_length = initialLength; - m_vectorLength = initialCapacity; - m_storage->m_numValuesInVector = 0; - m_storage->m_sparseValueMap = 0; - m_storage->subclassData = 0; - m_storage->reportedMapCapacity = 0; - - JSValue* vector = m_storage->m_vector; - for (size_t i = 0; i < initialCapacity; ++i) - vector[i] = JSValue(); - - checkConsistency(); - - Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue)); + Butterfly* butterfly = Butterfly::create( + vm, intendedOwner, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0)); + ArrayStorage* storage = butterfly->arrayStorage(); + storage->setLength(initialLength); + storage->setVectorLength(0); + storage->m_indexBias = 0; + storage->m_sparseMap.clear(); + storage->m_numValuesInVector = 0; + return butterfly; } -JSArray::JSArray(NonNullPassRefPtr structure, const ArgList& list) - : JSObject(structure) +void JSArray::setLengthWritable(ExecState* exec, bool writable) { - unsigned initialCapacity = list.size(); - - m_storage = static_cast(fastMalloc(storageSize(initialCapacity))); - m_storage->m_length = initialCapacity; - m_vectorLength = initialCapacity; - m_storage->m_numValuesInVector = initialCapacity; - m_storage->m_sparseValueMap = 0; - m_storage->subclassData = 0; - m_storage->reportedMapCapacity = 0; - - size_t i = 0; - ArgList::const_iterator end = list.end(); - for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) - m_storage->m_vector[i] = *it; - - checkConsistency(); - - Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity)); -} + ASSERT(isLengthWritable() || !writable); + if (!isLengthWritable() || writable) + return; -JSArray::~JSArray() -{ - ASSERT(vptr() == JSGlobalData::jsArrayVPtr); - checkConsistency(DestructorConsistencyCheck); + enterDictionaryIndexingMode(exec->vm()); - delete m_storage->m_sparseValueMap; - fastFree(m_storage); + SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get(); + ASSERT(map); + map->setLengthIsReadOnly(); } -bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) +// Defined in ES5.1 15.4.5.1 +bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException) { - ArrayStorage* storage = m_storage; - - if (i >= storage->m_length) { - if (i > MAX_ARRAY_INDEX) - return getOwnPropertySlot(exec, Identifier::from(exec, i), slot); - return false; - } + JSArray* array = jsCast(object); - if (i < m_vectorLength) { - JSValue& valueSlot = storage->m_vector[i]; - if (valueSlot) { - slot.setValueSlot(&valueSlot); + // 3. If P is "length", then + if (propertyName == exec->propertyNames().length) { + // All paths through length definition call the default [[DefineOwnProperty]], hence: + // from ES5.1 8.12.9 7.a. + if (descriptor.configurablePresent() && descriptor.configurable()) + return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property."); + // from ES5.1 8.12.9 7.b. + if (descriptor.enumerablePresent() && descriptor.enumerable()) + return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property."); + + // a. If the [[Value]] field of Desc is absent, then + // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments. + if (descriptor.isAccessorDescriptor()) + return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property."); + // from ES5.1 8.12.9 10.a. + if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable()) + return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property."); + // This descriptor is either just making length read-only, or changing nothing! + if (!descriptor.value()) { + if (descriptor.writablePresent()) + array->setLengthWritable(exec, descriptor.writable()); return true; } - } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - if (i >= MIN_SPARSE_ARRAY_INDEX) { - SparseArrayValueMap::iterator it = map->find(i); - if (it != map->end()) { - slot.setValueSlot(&it->second); - return true; - } + + // b. Let newLenDesc be a copy of Desc. + // c. Let newLen be ToUint32(Desc.[[Value]]). + unsigned newLen = descriptor.value().toUInt32(exec); + // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception. + if (newLen != descriptor.value().toNumber(exec)) { + exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + return false; } - } - return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot); -} + // Based on SameValue check in 8.12.9, this is always okay. + // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case. + if (newLen == array->length()) { + if (descriptor.writablePresent()) + array->setLengthWritable(exec, descriptor.writable()); + return true; + } -bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot) -{ - if (propertyName == exec->propertyNames().length) { - slot.setValue(jsNumber(exec, length())); + // e. Set newLenDesc.[[Value] to newLen. + // f. If newLen >= oldLen, then + // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments. + // g. Reject if oldLenDesc.[[Writable]] is false. + if (!array->isLengthWritable()) + return reject(exec, throwException, "Attempting to change value of a readonly property."); + + // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true. + // i. Else, + // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted. + // i.ii. Let newWritable be false. + // i.iii. Set newLenDesc.[[Writable] to true. + // 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. + // k. If succeeded is false, return false. + // l. While newLen < oldLen repeat, + // l.i. Set oldLen to oldLen – 1. + // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments. + // l.iii. If deleteSucceeded is false, then + if (!array->setLength(exec, newLen, throwException)) { + // 1. Set newLenDesc.[[Value] to oldLen+1. + // 2. If newWritable is false, set newLenDesc.[[Writable] to false. + // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments. + // 4. Reject. + if (descriptor.writablePresent()) + array->setLengthWritable(exec, descriptor.writable()); + return false; + } + + // m. If newWritable is false, then + // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", + // Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always + // return true. + if (descriptor.writablePresent()) + array->setLengthWritable(exec, descriptor.writable()); + // n. Return true. return true; } - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); - if (isArrayIndex) - return JSArray::getOwnPropertySlot(exec, i, slot); + // 4. Else if P is an array index (15.4), then + // a. Let index be ToUint32(P). + if (Optional optionalIndex = parseIndex(propertyName)) { + // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false. + uint32_t index = optionalIndex.value(); + // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case. + if (index >= array->length() && !array->isLengthWritable()) + return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property."); + // 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. + // d. Reject if succeeded is false. + // e. If index >= oldLen + // e.i. Set oldLenDesc.[[Value]] to index + 1. + // 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. + // f. Return true. + return array->defineOwnIndexedProperty(exec, index, descriptor, throwException); + } - return JSObject::getOwnPropertySlot(exec, propertyName, slot); + return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException); } -bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor) +bool JSArray::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot) { + JSArray* thisObject = jsCast(object); if (propertyName == exec->propertyNames().length) { - descriptor.setDescriptor(jsNumber(exec, length()), DontDelete | DontEnum); + unsigned attributes = thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly; + slot.setValue(thisObject, attributes, jsNumber(thisObject->length())); return true; } - - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); - if (isArrayIndex) { - if (i >= m_storage->m_length) - return false; - if (i < m_vectorLength) { - JSValue& value = m_storage->m_vector[i]; - if (value) { - descriptor.setDescriptor(value, 0); - return true; - } - } else if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) { - if (i >= MIN_SPARSE_ARRAY_INDEX) { - SparseArrayValueMap::iterator it = map->find(i); - if (it != map->end()) { - descriptor.setDescriptor(it->second, 0); - return true; - } - } - } - } - return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor); + + return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot); } // ECMA 15.4.5.1 -void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot) +void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot) { - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); - if (isArrayIndex) { - put(exec, i, value); - return; - } + JSArray* thisObject = jsCast(cell); if (propertyName == exec->propertyNames().length) { unsigned newLength = value.toUInt32(exec); if (value.toNumber(exec) != static_cast(newLength)) { - throwError(exec, RangeError, "Invalid array length."); + exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); return; } - setLength(newLength); + thisObject->setLength(exec, newLength, slot.isStrictMode()); return; } - JSObject::put(exec, propertyName, value, slot); + JSObject::put(thisObject, exec, propertyName, value, slot); } -void JSArray::put(ExecState* exec, unsigned i, JSValue value) +bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName) { - checkConsistency(); + JSArray* thisObject = jsCast(cell); - unsigned length = m_storage->m_length; - if (i >= length && i <= MAX_ARRAY_INDEX) { - length = i + 1; - m_storage->m_length = length; - } - - if (i < m_vectorLength) { - JSValue& valueSlot = m_storage->m_vector[i]; - if (valueSlot) { - valueSlot = value; - checkConsistency(); - return; - } - valueSlot = value; - ++m_storage->m_numValuesInVector; - checkConsistency(); - return; - } + if (propertyName == exec->propertyNames().length) + return false; - putSlowCase(exec, i, value); + return JSObject::deleteProperty(thisObject, exec, propertyName); } -NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value) +static int compareKeysForQSort(const void* a, const void* b) { - ArrayStorage* storage = m_storage; - SparseArrayValueMap* map = storage->m_sparseValueMap; - - if (i >= MIN_SPARSE_ARRAY_INDEX) { - if (i > MAX_ARRAY_INDEX) { - PutPropertySlot slot; - put(exec, Identifier::from(exec, i), value, slot); - return; - } - - // We miss some cases where we could compact the storage, such as a large array that is being filled from the end - // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster. - if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) { - if (!map) { - map = new SparseArrayValueMap; - storage->m_sparseValueMap = map; - } - - pair result = map->add(i, value); - if (!result.second) { // pre-existing entry - result.first->second = value; - return; - } - - size_t capacity = map->capacity(); - if (capacity != storage->reportedMapCapacity) { - Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue))); - storage->reportedMapCapacity = capacity; - } - return; - } - } - - // We have decided that we'll put the new item into the vector. - // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it. - if (!map || map->isEmpty()) { - if (increaseVectorLength(i + 1)) { - storage = m_storage; - storage->m_vector[i] = value; - ++storage->m_numValuesInVector; - checkConsistency(); - } else - throwOutOfMemoryError(exec); - return; - } - - // Decide how many values it would be best to move from the map. - unsigned newNumValuesInVector = storage->m_numValuesInVector + 1; - unsigned newVectorLength = increasedVectorLength(i + 1); - for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) - newNumValuesInVector += map->contains(j); - if (i >= MIN_SPARSE_ARRAY_INDEX) - newNumValuesInVector -= map->contains(i); - if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) { - unsigned proposedNewNumValuesInVector = newNumValuesInVector; - // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further. - while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) { - unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1); - for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j) - proposedNewNumValuesInVector += map->contains(j); - if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector)) - break; - newVectorLength = proposedNewVectorLength; - newNumValuesInVector = proposedNewNumValuesInVector; - } - } - - if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) { - throwOutOfMemoryError(exec); - return; - } - - unsigned vectorLength = m_vectorLength; - - if (newNumValuesInVector == storage->m_numValuesInVector + 1) { - for (unsigned j = vectorLength; j < newVectorLength; ++j) - storage->m_vector[j] = JSValue(); - if (i > MIN_SPARSE_ARRAY_INDEX) - map->remove(i); - } else { - for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j) - storage->m_vector[j] = JSValue(); - for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) - storage->m_vector[j] = map->take(j); - } - - storage->m_vector[i] = value; - - m_vectorLength = newVectorLength; - storage->m_numValuesInVector = newNumValuesInVector; - - m_storage = storage; - - checkConsistency(); - - Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + unsigned da = *static_cast(a); + unsigned db = *static_cast(b); + return (da > db) - (da < db); } -bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName) +void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode) { - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); - if (isArrayIndex) - return deleteProperty(exec, i); + JSArray* thisObject = jsCast(object); - if (propertyName == exec->propertyNames().length) - return false; + if (mode.includeDontEnumProperties()) + propertyNames.add(exec->propertyNames().length); - return JSObject::deleteProperty(exec, propertyName); + JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode); } -bool JSArray::deleteProperty(ExecState* exec, unsigned i) +// This method makes room in the vector, but leaves the new space for count slots uncleared. +bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count) { - checkConsistency(); - - ArrayStorage* storage = m_storage; - - if (i < m_vectorLength) { - JSValue& valueSlot = storage->m_vector[i]; - if (!valueSlot) { - checkConsistency(); + ArrayStorage* storage = ensureArrayStorage(vm); + Butterfly* butterfly = storage->butterfly(); + unsigned propertyCapacity = structure(vm)->outOfLineCapacity(); + unsigned propertySize = structure(vm)->outOfLineSize(); + + // If not, we should have handled this on the fast path. + ASSERT(!addToFront || count > storage->m_indexBias); + + // Step 1: + // Gather 4 key metrics: + // * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors). + // * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more. + // * currentCapacity - what is the current size of the vector, including any pre-capacity. + // * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength. + + unsigned length = storage->length(); + unsigned usedVectorLength = min(storage->vectorLength(), length); + ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH); + // Check that required vector length is possible, in an overflow-safe fashion. + if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength) + return false; + unsigned requiredVectorLength = usedVectorLength + count; + ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH); + // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH. + ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias); + unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias; + // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH. + unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1); + + // Step 2: + // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one. + + DeferGC deferGC(vm.heap); + void* newAllocBase = 0; + unsigned newStorageCapacity; + // If the current storage array is sufficiently large (but not too large!) then just keep using it. + if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) { + newAllocBase = butterfly->base(structure(vm)); + newStorageCapacity = currentCapacity; + } else { + size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity)); + if (!vm.heap.tryAllocateStorage(this, newSize, &newAllocBase)) return false; - } - valueSlot = JSValue(); - --storage->m_numValuesInVector; - checkConsistency(); - return true; + newStorageCapacity = desiredCapacity; } - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - if (i >= MIN_SPARSE_ARRAY_INDEX) { - SparseArrayValueMap::iterator it = map->find(i); - if (it != map->end()) { - map->remove(it); - checkConsistency(); - return true; - } - } + // Step 3: + // Work out where we're going to move things to. + + // Determine how much of the vector to use as pre-capacity, and how much as post-capacity. + // If we're adding to the end, we'll add all the new space to the end. + // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any. + // If it did, we calculate the amount that will remain based on an atomic decay - leave the + // vector with half the post-capacity it had previously. + unsigned postCapacity = 0; + if (!addToFront) + postCapacity = max(newStorageCapacity - requiredVectorLength, count); + else if (length < storage->vectorLength()) { + // Atomic decay, + the post-capacity cannot be greater than what is available. + postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength); + // If we're moving contents within the same allocation, the post-capacity is being reduced. + ASSERT(newAllocBase != butterfly->base(structure(vm)) || postCapacity < storage->vectorLength() - length); } - checkConsistency(); - - if (i > MAX_ARRAY_INDEX) - return deleteProperty(exec, Identifier::from(exec, i)); + unsigned newVectorLength = requiredVectorLength + postCapacity; + unsigned newIndexBias = newStorageCapacity - newVectorLength; - return false; -} - -void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode) -{ - // FIXME: Filling PropertyNameArray with an identifier for every integer - // is incredibly inefficient for large arrays. We need a different approach, - // which almost certainly means a different structure for PropertyNameArray. + Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity); - ArrayStorage* storage = m_storage; + if (addToFront) { + ASSERT(count + usedVectorLength <= newVectorLength); + memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength); + memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0)); + } else if ((newAllocBase != butterfly->base(structure(vm))) || (newIndexBias != storage->m_indexBias)) { + memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0)); + memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength); - unsigned usedVectorLength = min(storage->m_length, m_vectorLength); - for (unsigned i = 0; i < usedVectorLength; ++i) { - if (storage->m_vector[i]) - propertyNames.add(Identifier::from(exec, i)); + WriteBarrier* newVector = newButterfly->arrayStorage()->m_vector; + for (unsigned i = requiredVectorLength; i < newVectorLength; i++) + newVector[i].clear(); } - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - propertyNames.add(Identifier::from(exec, it->first)); - } + newButterfly->arrayStorage()->setVectorLength(newVectorLength); + newButterfly->arrayStorage()->m_indexBias = newIndexBias; + setButterflyWithoutChangingStructure(vm, newButterfly); - if (mode == IncludeDontEnumProperties) - propertyNames.add(exec->propertyNames().length); - - JSObject::getOwnPropertyNames(exec, propertyNames, mode); + return true; } -bool JSArray::increaseVectorLength(unsigned newLength) +bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage) { - // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map - // to the vector. Callers have to account for that, because they can do it more efficiently. - - ArrayStorage* storage = m_storage; - - unsigned vectorLength = m_vectorLength; - ASSERT(newLength > vectorLength); - ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); - unsigned newVectorLength = increasedVectorLength(newLength); - - if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) - return false; - - m_vectorLength = newVectorLength; + unsigned length = storage->length(); + + // If the length is read only then we enter sparse mode, so should enter the following 'if'. + ASSERT(isLengthWritable() || storage->m_sparseMap); + + if (SparseArrayValueMap* map = storage->m_sparseMap.get()) { + // Fail if the length is not writable. + if (map->lengthIsReadOnly()) + return reject(exec, throwException, StrictModeReadonlyPropertyWriteError); + + if (newLength < length) { + // Copy any keys we might be interested in into a vector. + Vector keys; + keys.reserveInitialCapacity(min(map->size(), static_cast(length - newLength))); + SparseArrayValueMap::const_iterator end = map->end(); + for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) { + unsigned index = static_cast(it->key); + if (index < length && index >= newLength) + keys.append(index); + } - for (unsigned i = vectorLength; i < newVectorLength; ++i) - storage->m_vector[i] = JSValue(); + // Check if the array is in sparse mode. If so there may be non-configurable + // properties, so we have to perform deletion with caution, if not we can + // delete values in any order. + if (map->sparseMode()) { + qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort); + unsigned i = keys.size(); + while (i) { + unsigned index = keys[--i]; + SparseArrayValueMap::iterator it = map->find(index); + ASSERT(it != map->notFound()); + if (it->value.attributes & DontDelete) { + storage->setLength(index + 1); + return reject(exec, throwException, "Unable to delete property."); + } + map->remove(it); + } + } else { + for (unsigned i = 0; i < keys.size(); ++i) + map->remove(keys[i]); + if (map->isEmpty()) + deallocateSparseIndexMap(); + } + } + } - m_storage = storage; + if (newLength < length) { + // Delete properties from the vector. + unsigned usedVectorLength = min(length, storage->vectorLength()); + for (unsigned i = newLength; i < usedVectorLength; ++i) { + WriteBarrier& valueSlot = storage->m_vector[i]; + bool hadValue = !!valueSlot; + valueSlot.clear(); + storage->m_numValuesInVector -= hadValue; + } + } - Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + storage->setLength(newLength); return true; } -void JSArray::setLength(unsigned newLength) +bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException) { - checkConsistency(); - - ArrayStorage* storage = m_storage; - - unsigned length = m_storage->m_length; + switch (indexingType()) { + case ArrayClass: + if (!newLength) + return true; + if (newLength >= MIN_SPARSE_ARRAY_INDEX) { + return setLengthWithArrayStorage( + exec, newLength, throwException, + convertContiguousToArrayStorage(exec->vm())); + } + createInitialUndecided(exec->vm(), newLength); + return true; + + case ArrayWithUndecided: + case ArrayWithInt32: + case ArrayWithDouble: + case ArrayWithContiguous: { + if (newLength == m_butterfly->publicLength()) + return true; + if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push. + || (newLength >= MIN_SPARSE_ARRAY_INDEX + && !isDenseEnoughForVector(newLength, countElements()))) { + return setLengthWithArrayStorage( + exec, newLength, throwException, + ensureArrayStorage(exec->vm())); + } + if (newLength > m_butterfly->publicLength()) { + ensureLength(exec->vm(), newLength); + return true; + } - if (newLength < length) { - unsigned usedVectorLength = min(length, m_vectorLength); - for (unsigned i = newLength; i < usedVectorLength; ++i) { - JSValue& valueSlot = storage->m_vector[i]; - bool hadValue = valueSlot; - valueSlot = JSValue(); - storage->m_numValuesInVector -= hadValue; + unsigned lengthToClear = m_butterfly->publicLength() - newLength; + unsigned costToAllocateNewButterfly = 64; // a heuristic. + if (lengthToClear > newLength && lengthToClear > costToAllocateNewButterfly) { + reallocateAndShrinkButterfly(exec->vm(), newLength); + return true; } - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - SparseArrayValueMap copy = *map; - SparseArrayValueMap::iterator end = copy.end(); - for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) { - if (it->first >= newLength) - map->remove(it->first); - } - if (map->isEmpty()) { - delete map; - storage->m_sparseValueMap = 0; - } + if (indexingType() == ArrayWithDouble) { + for (unsigned i = m_butterfly->publicLength(); i-- > newLength;) + m_butterfly->contiguousDouble()[i] = PNaN; + } else { + for (unsigned i = m_butterfly->publicLength(); i-- > newLength;) + m_butterfly->contiguous()[i].clear(); } + m_butterfly->setPublicLength(newLength); + return true; + } + + case ArrayWithArrayStorage: + case ArrayWithSlowPutArrayStorage: + return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage()); + + default: + CRASH(); + return false; } - - m_storage->m_length = newLength; - - checkConsistency(); } -JSValue JSArray::pop() +JSValue JSArray::pop(ExecState* exec) { - checkConsistency(); - - unsigned length = m_storage->m_length; - if (!length) + switch (indexingType()) { + case ArrayClass: return jsUndefined(); + + case ArrayWithUndecided: + if (!m_butterfly->publicLength()) + return jsUndefined(); + // We have nothing but holes. So, drop down to the slow version. + break; + + case ArrayWithInt32: + case ArrayWithContiguous: { + unsigned length = m_butterfly->publicLength(); + + if (!length--) + return jsUndefined(); + + RELEASE_ASSERT(length < m_butterfly->vectorLength()); + JSValue value = m_butterfly->contiguous()[length].get(); + if (value) { + m_butterfly->contiguous()[length].clear(); + m_butterfly->setPublicLength(length); + return value; + } + break; + } + + case ArrayWithDouble: { + unsigned length = m_butterfly->publicLength(); + + if (!length--) + return jsUndefined(); + + RELEASE_ASSERT(length < m_butterfly->vectorLength()); + double value = m_butterfly->contiguousDouble()[length]; + if (value == value) { + m_butterfly->contiguousDouble()[length] = PNaN; + m_butterfly->setPublicLength(length); + return JSValue(JSValue::EncodeAsDouble, value); + } + break; + } + + case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { + ArrayStorage* storage = m_butterfly->arrayStorage(); + + unsigned length = storage->length(); + if (!length) { + if (!isLengthWritable()) + throwTypeError(exec, StrictModeReadonlyPropertyWriteError); + return jsUndefined(); + } - --length; - - JSValue result; - - if (length < m_vectorLength) { - JSValue& valueSlot = m_storage->m_vector[length]; - if (valueSlot) { - --m_storage->m_numValuesInVector; - result = valueSlot; - valueSlot = JSValue(); - } else - result = jsUndefined(); - } else { - result = jsUndefined(); - if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) { - SparseArrayValueMap::iterator it = map->find(length); - if (it != map->end()) { - result = it->second; - map->remove(it); - if (map->isEmpty()) { - delete map; - m_storage->m_sparseValueMap = 0; - } + unsigned index = length - 1; + if (index < storage->vectorLength()) { + WriteBarrier& valueSlot = storage->m_vector[index]; + if (valueSlot) { + --storage->m_numValuesInVector; + JSValue element = valueSlot.get(); + valueSlot.clear(); + + RELEASE_ASSERT(isLengthWritable()); + storage->setLength(index); + return element; } } + break; } - - m_storage->m_length = length; - - checkConsistency(); - - return result; + + default: + CRASH(); + return JSValue(); + } + + unsigned index = getArrayLength() - 1; + // Let element be the result of calling the [[Get]] internal method of O with argument indx. + JSValue element = get(exec, index); + if (exec->hadException()) + return jsUndefined(); + // Call the [[Delete]] internal method of O with arguments indx and true. + if (!deletePropertyByIndex(this, exec, index)) { + throwTypeError(exec, ASCIILiteral("Unable to delete property.")); + return jsUndefined(); + } + // Call the [[Put]] internal method of O with arguments "length", indx, and true. + setLength(exec, index, true); + // Return element. + return element; } +// Push & putIndex are almost identical, with two small differences. +// - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector. +// - pushing to an array of length 2^32-1 stores the property, but throws a range error. void JSArray::push(ExecState* exec, JSValue value) { - checkConsistency(); - - if (m_storage->m_length < m_vectorLength) { - m_storage->m_vector[m_storage->m_length] = value; - ++m_storage->m_numValuesInVector; - ++m_storage->m_length; - checkConsistency(); + switch (indexingType()) { + case ArrayClass: { + createInitialUndecided(exec->vm(), 0); + FALLTHROUGH; + } + + case ArrayWithUndecided: { + convertUndecidedForValue(exec->vm(), value); + push(exec, value); return; } + + case ArrayWithInt32: { + if (!value.isInt32()) { + convertInt32ForValue(exec->vm(), value); + push(exec, value); + return; + } - if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) { - SparseArrayValueMap* map = m_storage->m_sparseValueMap; - if (!map || map->isEmpty()) { - if (increaseVectorLength(m_storage->m_length + 1)) { - m_storage->m_vector[m_storage->m_length] = value; - ++m_storage->m_numValuesInVector; - ++m_storage->m_length; - checkConsistency(); - return; - } - checkConsistency(); - throwOutOfMemoryError(exec); + unsigned length = m_butterfly->publicLength(); + ASSERT(length <= m_butterfly->vectorLength()); + if (length < m_butterfly->vectorLength()) { + m_butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value); + m_butterfly->setPublicLength(length + 1); return; } + + if (length > MAX_ARRAY_INDEX) { + methodTable(exec->vm())->putByIndex(this, exec, length, value, true); + if (!exec->hadException()) + exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + return; + } + + putByIndexBeyondVectorLengthWithoutAttributes(exec, length, value); + return; } - putSlowCase(exec, m_storage->m_length++, value); -} - -void JSArray::markChildren(MarkStack& markStack) -{ - markChildrenDirect(markStack); -} - -static int compareNumbersForQSort(const void* a, const void* b) -{ - double da = static_cast(a)->uncheckedGetNumber(); - double db = static_cast(b)->uncheckedGetNumber(); - return (da > db) - (da < db); -} - -static int compareByStringPairForQSort(const void* a, const void* b) -{ - const ValueStringPair* va = static_cast(a); - const ValueStringPair* vb = static_cast(b); - return compare(va->second, vb->second); -} - -void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) -{ - unsigned lengthNotIncludingUndefined = compactForSorting(); - if (m_storage->m_sparseValueMap) { - throwOutOfMemoryError(exec); + case ArrayWithContiguous: { + unsigned length = m_butterfly->publicLength(); + ASSERT(length <= m_butterfly->vectorLength()); + if (length < m_butterfly->vectorLength()) { + m_butterfly->contiguous()[length].set(exec->vm(), this, value); + m_butterfly->setPublicLength(length + 1); + return; + } + + if (length > MAX_ARRAY_INDEX) { + methodTable(exec->vm())->putByIndex(this, exec, length, value, true); + if (!exec->hadException()) + exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + return; + } + + putByIndexBeyondVectorLengthWithoutAttributes(exec, length, value); return; } + + case ArrayWithDouble: { + if (!value.isNumber()) { + convertDoubleToContiguous(exec->vm()); + push(exec, value); + return; + } + double valueAsDouble = value.asNumber(); + if (valueAsDouble != valueAsDouble) { + convertDoubleToContiguous(exec->vm()); + push(exec, value); + return; + } - if (!lengthNotIncludingUndefined) - return; + unsigned length = m_butterfly->publicLength(); + ASSERT(length <= m_butterfly->vectorLength()); + if (length < m_butterfly->vectorLength()) { + m_butterfly->contiguousDouble()[length] = valueAsDouble; + m_butterfly->setPublicLength(length + 1); + return; + } - bool allValuesAreNumbers = true; - size_t size = m_storage->m_numValuesInVector; - for (size_t i = 0; i < size; ++i) { - if (!m_storage->m_vector[i].isNumber()) { - allValuesAreNumbers = false; - break; + if (length > MAX_ARRAY_INDEX) { + methodTable(exec->vm())->putByIndex(this, exec, length, value, true); + if (!exec->hadException()) + exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + return; } + + putByIndexBeyondVectorLengthWithoutAttributes(exec, length, value); + break; } + + case ArrayWithSlowPutArrayStorage: { + unsigned oldLength = length(); + if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) { + if (!exec->hadException() && oldLength < 0xFFFFFFFFu) + setLength(exec, oldLength + 1, true); + return; + } + FALLTHROUGH; + } + + case ArrayWithArrayStorage: { + ArrayStorage* storage = m_butterfly->arrayStorage(); + + // Fast case - push within vector, always update m_length & m_numValuesInVector. + unsigned length = storage->length(); + if (length < storage->vectorLength()) { + storage->m_vector[length].set(exec->vm(), this, value); + storage->setLength(length + 1); + ++storage->m_numValuesInVector; + return; + } - if (!allValuesAreNumbers) - return sort(exec, compareFunction, callType, callData); - - // For numeric comparison, which is fast, qsort is faster than mergesort. We - // also don't require mergesort's stability, since there's no user visible - // side-effect from swapping the order of equal primitive values. - qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort); + // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error. + if (storage->length() > MAX_ARRAY_INDEX) { + methodTable(exec->vm())->putByIndex(this, exec, storage->length(), value, true); + // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d. + if (!exec->hadException()) + exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + return; + } - checkConsistency(SortConsistencyCheck); + // Handled the same as putIndex. + putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage); + break; + } + + default: + RELEASE_ASSERT_NOT_REACHED(); + } } -void JSArray::sort(ExecState* exec) +JSArray* JSArray::fastSlice(ExecState& exec, unsigned startIndex, unsigned count) { - unsigned lengthNotIncludingUndefined = compactForSorting(); - if (m_storage->m_sparseValueMap) { - throwOutOfMemoryError(exec); - return; - } - - if (!lengthNotIncludingUndefined) - return; - - // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that. - // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary - // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return - // random or otherwise changing results, effectively making compare function inconsistent. - - Vector values(lengthNotIncludingUndefined); - if (!values.begin()) { - throwOutOfMemoryError(exec); - return; + auto arrayType = indexingType(); + switch (arrayType) { + case ArrayWithDouble: + case ArrayWithInt32: + case ArrayWithContiguous: { + VM& vm = exec.vm(); + if (count >= MIN_SPARSE_ARRAY_INDEX || structure(vm)->holesMustForwardToPrototype(vm)) + return nullptr; + + Structure* resultStructure = exec.lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(arrayType); + JSArray* resultArray = JSArray::tryCreateUninitialized(vm, resultStructure, count); + if (!resultArray) + return nullptr; + + auto& resultButterfly = *resultArray->butterfly(); + if (arrayType == ArrayWithDouble) + memcpy(resultButterfly.contiguousDouble().data(), m_butterfly->contiguousDouble().data() + startIndex, sizeof(JSValue) * count); + else + memcpy(resultButterfly.contiguous().data(), m_butterfly->contiguous().data() + startIndex, sizeof(JSValue) * count); + resultButterfly.setPublicLength(count); + + return resultArray; } - - Heap::heap(this)->pushTempSortVector(&values); - - for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { - JSValue value = m_storage->m_vector[i]; - ASSERT(!value.isUndefined()); - values[i].first = value; + default: + return nullptr; } +} - // FIXME: The following loop continues to call toString on subsequent values even after - // a toString call raises an exception. - - for (size_t i = 0; i < lengthNotIncludingUndefined; i++) - values[i].second = values[i].first.toString(exec); - - if (exec->hadException()) { - Heap::heap(this)->popTempSortVector(&values); - return; +EncodedJSValue JSArray::fastConcatWith(ExecState& exec, JSArray& otherArray) +{ + auto newArrayType = indexingType(); + + VM& vm = exec.vm(); + ASSERT(newArrayType == fastConcatType(vm, *this, otherArray)); + + unsigned thisArraySize = m_butterfly->publicLength(); + unsigned otherArraySize = otherArray.m_butterfly->publicLength(); + ASSERT(thisArraySize + otherArraySize < MIN_SPARSE_ARRAY_INDEX); + + Structure* resultStructure = exec.lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(newArrayType); + JSArray* resultArray = JSArray::tryCreateUninitialized(vm, resultStructure, thisArraySize + otherArraySize); + if (!resultArray) + return JSValue::encode(throwOutOfMemoryError(&exec)); + + auto& resultButterfly = *resultArray->butterfly(); + auto& otherButterfly = *otherArray.butterfly(); + if (newArrayType == ArrayWithDouble) { + auto buffer = resultButterfly.contiguousDouble().data(); + memcpy(buffer, m_butterfly->contiguousDouble().data(), sizeof(JSValue) * thisArraySize); + memcpy(buffer + thisArraySize, otherButterfly.contiguousDouble().data(), sizeof(JSValue) * otherArraySize); + } else { + auto buffer = resultButterfly.contiguous().data(); + memcpy(buffer, m_butterfly->contiguous().data(), sizeof(JSValue) * thisArraySize); + memcpy(buffer + thisArraySize, otherButterfly.contiguous().data(), sizeof(JSValue) * otherArraySize); } - // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather - // than O(N log N). - -#if HAVE(MERGESORT) - mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); -#else - // FIXME: The qsort library function is likely to not be a stable sort. - // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort. - qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); -#endif - - // If the toString function changed the length of the array or vector storage, - // increase the length to handle the orignal number of actual values. - if (m_vectorLength < lengthNotIncludingUndefined) - increaseVectorLength(lengthNotIncludingUndefined); - if (m_storage->m_length < lengthNotIncludingUndefined) - m_storage->m_length = lengthNotIncludingUndefined; - - for (size_t i = 0; i < lengthNotIncludingUndefined; i++) - m_storage->m_vector[i] = values[i].first; - - Heap::heap(this)->popTempSortVector(&values); - - checkConsistency(SortConsistencyCheck); + resultButterfly.setPublicLength(thisArraySize + otherArraySize); + return JSValue::encode(resultArray); } -struct AVLTreeNodeForArrayCompare { - JSValue value; - - // Child pointers. The high bit of gt is robbed and used as the - // balance factor sign. The high bit of lt is robbed and used as - // the magnitude of the balance factor. - int32_t gt; - int32_t lt; -}; - -struct AVLTreeAbstractorForArrayCompare { - typedef int32_t handle; // Handle is an index into m_nodes vector. - typedef JSValue key; - typedef int32_t size; - - Vector m_nodes; - ExecState* m_exec; - JSValue m_compareFunction; - CallType m_compareCallType; - const CallData* m_compareCallData; - JSValue m_globalThisValue; - OwnPtr m_cachedCall; - - handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; } - void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; } - handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; } - void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; } - - int get_balance_factor(handle h) - { - if (m_nodes[h].gt & 0x80000000) - return -1; - return static_cast(m_nodes[h].lt) >> 31; +bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage) +{ + unsigned oldLength = storage->length(); + RELEASE_ASSERT(count <= oldLength); + + // If the array contains holes or is otherwise in an abnormal state, + // use the generic algorithm in ArrayPrototype. + if ((storage->hasHoles() && this->structure(vm)->holesMustForwardToPrototype(vm)) + || hasSparseMap() + || shouldUseSlowPut(indexingType())) { + return false; } - void set_balance_factor(handle h, int bf) - { - if (bf == 0) { - m_nodes[h].lt &= 0x7FFFFFFF; - m_nodes[h].gt &= 0x7FFFFFFF; + if (!oldLength) + return true; + + unsigned length = oldLength - count; + + storage->m_numValuesInVector -= count; + storage->setLength(length); + + unsigned vectorLength = storage->vectorLength(); + if (!vectorLength) + return true; + + if (startIndex >= vectorLength) + return true; + + if (startIndex + count > vectorLength) + count = vectorLength - startIndex; + + unsigned usedVectorLength = min(vectorLength, oldLength); + + unsigned numElementsBeforeShiftRegion = startIndex; + unsigned firstIndexAfterShiftRegion = startIndex + count; + unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion; + ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength); + + // The point of this comparison seems to be to minimize the amount of elements that have to + // be moved during a shift operation. + if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) { + // The number of elements before the shift region is less than the number of elements + // after the shift region, so we move the elements before to the right. + if (numElementsBeforeShiftRegion) { + RELEASE_ASSERT(count + startIndex <= vectorLength); + if (storage->hasHoles()) { + for (unsigned i = startIndex; i-- > 0;) { + unsigned destinationIndex = count + i; + JSValue source = storage->m_vector[i].get(); + JSValue dest = storage->m_vector[destinationIndex].get(); + // Any time we overwrite a hole we know we overcounted the number of values we removed + // when we subtracted count from m_numValuesInVector above. + if (!dest && destinationIndex >= firstIndexAfterShiftRegion) + storage->m_numValuesInVector++; + storage->m_vector[count + i].setWithoutWriteBarrier(source); + } + } else { + memmove(storage->m_vector + count, + storage->m_vector, + sizeof(JSValue) * startIndex); + } + } + // Adjust the Butterfly and the index bias. We only need to do this here because we're changing + // the start of the Butterfly, which needs to point at the first indexed property in the used + // portion of the vector. + m_butterfly.setWithoutWriteBarrier(m_butterfly->shift(structure(), count)); + storage = m_butterfly->arrayStorage(); + storage->m_indexBias += count; + + // Since we're consuming part of the vector by moving its beginning to the left, + // we need to modify the vector length appropriately. + storage->setVectorLength(vectorLength - count); + } else { + // The number of elements before the shift region is greater than or equal to the number + // of elements after the shift region, so we move the elements after the shift region to the left. + if (storage->hasHoles()) { + for (unsigned i = 0; i < numElementsAfterShiftRegion; ++i) { + unsigned destinationIndex = startIndex + i; + JSValue source = storage->m_vector[firstIndexAfterShiftRegion + i].get(); + JSValue dest = storage->m_vector[destinationIndex].get(); + // Any time we overwrite a hole we know we overcounted the number of values we removed + // when we subtracted count from m_numValuesInVector above. + if (!dest && destinationIndex < firstIndexAfterShiftRegion) + storage->m_numValuesInVector++; + storage->m_vector[startIndex + i].setWithoutWriteBarrier(source); + } } else { - m_nodes[h].lt |= 0x80000000; - if (bf < 0) - m_nodes[h].gt |= 0x80000000; - else - m_nodes[h].gt &= 0x7FFFFFFF; + memmove(storage->m_vector + startIndex, + storage->m_vector + firstIndexAfterShiftRegion, + sizeof(JSValue) * numElementsAfterShiftRegion); } + // Clear the slots of the elements we just moved. + unsigned startOfEmptyVectorTail = usedVectorLength - count; + for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i) + storage->m_vector[i].clear(); + // We don't modify the index bias or the Butterfly pointer in this case because we're not changing + // the start of the Butterfly, which needs to point at the first indexed property in the used + // portion of the vector. We also don't modify the vector length because we're not actually changing + // its length; we're just using less of it. } + + return true; +} - int compare_key_key(key va, key vb) - { - ASSERT(!va.isUndefined()); - ASSERT(!vb.isUndefined()); - - if (m_exec->hadException()) - return 1; +bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count) +{ + VM& vm = exec->vm(); + RELEASE_ASSERT(count > 0); + + switch (indexingType()) { + case ArrayClass: + return true; + + case ArrayWithUndecided: + // Don't handle this because it's confusing and it shouldn't come up. + return false; + + case ArrayWithInt32: + case ArrayWithContiguous: { + unsigned oldLength = m_butterfly->publicLength(); + RELEASE_ASSERT(count <= oldLength); + + // We may have to walk the entire array to do the shift. We're willing to do + // so only if it's not horribly slow. + if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX) + return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm)); + + // Storing to a hole is fine since we're still having a good time. But reading from a hole + // is totally not fine, since we might have to read from the proto chain. + // We have to check for holes before we start moving things around so that we don't get halfway + // through shifting and then realize we should have been in ArrayStorage mode. + unsigned end = oldLength - count; + if (this->structure(vm)->holesMustForwardToPrototype(vm)) { + for (unsigned i = startIndex; i < end; ++i) { + JSValue v = m_butterfly->contiguous()[i + count].get(); + if (UNLIKELY(!v)) { + startIndex = i; + return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm)); + } + m_butterfly->contiguous()[i].setWithoutWriteBarrier(v); + } + } else { + memmove(m_butterfly->contiguous().data() + startIndex, + m_butterfly->contiguous().data() + startIndex + count, + sizeof(JSValue) * (end - startIndex)); + } - double compareResult; - if (m_cachedCall) { - m_cachedCall->setThis(m_globalThisValue); - m_cachedCall->setArgument(0, va); - m_cachedCall->setArgument(1, vb); - compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec)); + for (unsigned i = end; i < oldLength; ++i) + m_butterfly->contiguous()[i].clear(); + + m_butterfly->setPublicLength(oldLength - count); + return true; + } + + case ArrayWithDouble: { + unsigned oldLength = m_butterfly->publicLength(); + RELEASE_ASSERT(count <= oldLength); + + // We may have to walk the entire array to do the shift. We're willing to do + // so only if it's not horribly slow. + if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX) + return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm)); + + // Storing to a hole is fine since we're still having a good time. But reading from a hole + // is totally not fine, since we might have to read from the proto chain. + // We have to check for holes before we start moving things around so that we don't get halfway + // through shifting and then realize we should have been in ArrayStorage mode. + unsigned end = oldLength - count; + if (this->structure(vm)->holesMustForwardToPrototype(vm)) { + for (unsigned i = startIndex; i < end; ++i) { + double v = m_butterfly->contiguousDouble()[i + count]; + if (UNLIKELY(v != v)) { + startIndex = i; + return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm)); + } + m_butterfly->contiguousDouble()[i] = v; + } } else { - MarkedArgumentBuffer arguments; - arguments.append(va); - arguments.append(vb); - compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec); + memmove(m_butterfly->contiguousDouble().data() + startIndex, + m_butterfly->contiguousDouble().data() + startIndex + count, + sizeof(JSValue) * (end - startIndex)); } - return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. + for (unsigned i = end; i < oldLength; ++i) + m_butterfly->contiguousDouble()[i] = PNaN; + + m_butterfly->setPublicLength(oldLength - count); + return true; } + + case ArrayWithArrayStorage: + case ArrayWithSlowPutArrayStorage: + return shiftCountWithArrayStorage(vm, startIndex, count, arrayStorage()); + + default: + CRASH(); + return false; + } +} - int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); } - int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); } - - static handle null() { return 0x7FFFFFFF; } -}; - -void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +// Returns true if the unshift can be handled, false to fallback. +bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage) { - checkConsistency(); - - // FIXME: This ignores exceptions raised in the compare function or in toNumber. - - // The maximum tree depth is compiled in - but the caller is clearly up to no good - // if a larger array is passed. - ASSERT(m_storage->m_length <= static_cast(std::numeric_limits::max())); - if (m_storage->m_length > static_cast(std::numeric_limits::max())) - return; - - if (!m_storage->m_length) - return; - - unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength); + unsigned length = storage->length(); - AVLTree tree; // Depth 44 is enough for 2^31 items - tree.abstractor().m_exec = exec; - tree.abstractor().m_compareFunction = compareFunction; - tree.abstractor().m_compareCallType = callType; - tree.abstractor().m_compareCallData = &callData; - tree.abstractor().m_globalThisValue = exec->globalThisValue(); - tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0)); + RELEASE_ASSERT(startIndex <= length); - if (callType == CallTypeJS) - tree.abstractor().m_cachedCall.set(new CachedCall(exec, asFunction(compareFunction), 2, exec->exceptionSlot())); + // If the array contains holes or is otherwise in an abnormal state, + // use the generic algorithm in ArrayPrototype. + if (storage->hasHoles() || storage->inSparseMode() || shouldUseSlowPut(indexingType())) + return false; - if (!tree.abstractor().m_nodes.begin()) { + bool moveFront = !startIndex || startIndex < length / 2; + + unsigned vectorLength = storage->vectorLength(); + + if (moveFront && storage->m_indexBias >= count) { + Butterfly* newButterfly = storage->butterfly()->unshift(structure(), count); + storage = newButterfly->arrayStorage(); + storage->m_indexBias -= count; + storage->setVectorLength(vectorLength + count); + setButterflyWithoutChangingStructure(exec->vm(), newButterfly); + } else if (!moveFront && vectorLength - length >= count) + storage = storage->butterfly()->arrayStorage(); + else if (unshiftCountSlowCase(exec->vm(), moveFront, count)) + storage = arrayStorage(); + else { throwOutOfMemoryError(exec); - return; + return true; } - // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified - // right out from under us while we're building the tree here. - - unsigned numDefined = 0; - unsigned numUndefined = 0; + WriteBarrier* vector = storage->m_vector; - // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree. - for (; numDefined < usedVectorLength; ++numDefined) { - JSValue v = m_storage->m_vector[numDefined]; - if (!v || v.isUndefined()) - break; - tree.abstractor().m_nodes[numDefined].value = v; - tree.insert(numDefined); - } - for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValue v = m_storage->m_vector[i]; - if (v) { - if (v.isUndefined()) - ++numUndefined; - else { - tree.abstractor().m_nodes[numDefined].value = v; - tree.insert(numDefined); - ++numDefined; - } - } + if (startIndex) { + if (moveFront) + memmove(vector, vector + count, startIndex * sizeof(JSValue)); + else if (length - startIndex) + memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue)); } - unsigned newUsedVectorLength = numDefined + numUndefined; + for (unsigned i = 0; i < count; i++) + vector[i + startIndex].clear(); + return true; +} - if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) { - newUsedVectorLength += map->size(); - if (newUsedVectorLength > m_vectorLength) { - // Check that it is possible to allocate an array large enough to hold all the entries. - if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) { - throwOutOfMemoryError(exec); - return; - } - } +bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count) +{ + switch (indexingType()) { + case ArrayClass: + case ArrayWithUndecided: + // We could handle this. But it shouldn't ever come up, so we won't. + return false; - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { - tree.abstractor().m_nodes[numDefined].value = it->second; - tree.insert(numDefined); - ++numDefined; + case ArrayWithInt32: + case ArrayWithContiguous: { + unsigned oldLength = m_butterfly->publicLength(); + + // We may have to walk the entire array to do the unshift. We're willing to do so + // only if it's not horribly slow. + if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX) + return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); + + ensureLength(exec->vm(), oldLength + count); + + // We have to check for holes before we start moving things around so that we don't get halfway + // through shifting and then realize we should have been in ArrayStorage mode. + for (unsigned i = oldLength; i-- > startIndex;) { + JSValue v = m_butterfly->contiguous()[i].get(); + if (UNLIKELY(!v)) + return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); } - delete map; - m_storage->m_sparseValueMap = 0; + for (unsigned i = oldLength; i-- > startIndex;) { + JSValue v = m_butterfly->contiguous()[i].get(); + ASSERT(v); + m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v); + } + + // NOTE: we're leaving being garbage in the part of the array that we shifted out + // of. This is fine because the caller is required to store over that area, and + // in contiguous mode storing into a hole is guaranteed to behave exactly the same + // as storing over an existing element. + + return true; } + + case ArrayWithDouble: { + unsigned oldLength = m_butterfly->publicLength(); + + // We may have to walk the entire array to do the unshift. We're willing to do so + // only if it's not horribly slow. + if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX) + return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); + + ensureLength(exec->vm(), oldLength + count); + + // We have to check for holes before we start moving things around so that we don't get halfway + // through shifting and then realize we should have been in ArrayStorage mode. + for (unsigned i = oldLength; i-- > startIndex;) { + double v = m_butterfly->contiguousDouble()[i]; + if (UNLIKELY(v != v)) + return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); + } - ASSERT(tree.abstractor().m_nodes.size() >= numDefined); - - // FIXME: If the compare function changed the length of the array, the following might be - // modifying the vector incorrectly. - - // Copy the values back into m_storage. - AVLTree::Iterator iter; - iter.start_iter_least(tree); - for (unsigned i = 0; i < numDefined; ++i) { - m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value; - ++iter; + for (unsigned i = oldLength; i-- > startIndex;) { + double v = m_butterfly->contiguousDouble()[i]; + ASSERT(v == v); + m_butterfly->contiguousDouble()[i + count] = v; + } + + // NOTE: we're leaving being garbage in the part of the array that we shifted out + // of. This is fine because the caller is required to store over that area, and + // in contiguous mode storing into a hole is guaranteed to behave exactly the same + // as storing over an existing element. + + return true; + } + + case ArrayWithArrayStorage: + case ArrayWithSlowPutArrayStorage: + return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage()); + + default: + CRASH(); + return false; } - - // Put undefined values back in. - for (unsigned i = numDefined; i < newUsedVectorLength; ++i) - m_storage->m_vector[i] = jsUndefined(); - - // Ensure that unused values in the vector are zeroed out. - for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - m_storage->m_vector[i] = JSValue(); - - m_storage->m_numValuesInVector = newUsedVectorLength; - - checkConsistency(SortConsistencyCheck); } void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) { - JSValue* vector = m_storage->m_vector; - unsigned vectorEnd = min(m_storage->m_length, m_vectorLength); unsigned i = 0; - for (; i < vectorEnd; ++i) { - JSValue& v = vector[i]; - if (!v) - break; - args.append(v); + unsigned vectorEnd; + WriteBarrier* vector; + + switch (indexingType()) { + case ArrayClass: + return; + + case ArrayWithUndecided: { + vector = 0; + vectorEnd = 0; + break; } - - for (; i < m_storage->m_length; ++i) - args.append(get(exec, i)); -} - -void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize) -{ - ASSERT(m_storage->m_length >= maxSize); - UNUSED_PARAM(maxSize); - JSValue* vector = m_storage->m_vector; - unsigned vectorEnd = min(maxSize, m_vectorLength); - unsigned i = 0; + + case ArrayWithInt32: + case ArrayWithContiguous: { + vectorEnd = m_butterfly->publicLength(); + vector = m_butterfly->contiguous().data(); + break; + } + + case ArrayWithDouble: { + vector = 0; + vectorEnd = 0; + for (; i < m_butterfly->publicLength(); ++i) { + double v = butterfly()->contiguousDouble()[i]; + if (v != v) + break; + args.append(JSValue(JSValue::EncodeAsDouble, v)); + } + break; + } + + case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { + ArrayStorage* storage = m_butterfly->arrayStorage(); + + vector = storage->m_vector; + vectorEnd = min(storage->length(), storage->vectorLength()); + break; + } + + default: + CRASH(); +#if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE) + vector = 0; + vectorEnd = 0; + break; +#endif + } + for (; i < vectorEnd; ++i) { - JSValue& v = vector[i]; + WriteBarrier& v = vector[i]; if (!v) break; - buffer[i] = v; + args.append(v.get()); } - for (; i < maxSize; ++i) - buffer[i] = get(exec, i); + // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case. + for (; i < length(); ++i) + args.append(get(exec, i)); } -unsigned JSArray::compactForSorting() +void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest, unsigned offset, unsigned length) { - checkConsistency(); + unsigned i = offset; + WriteBarrier* vector; + unsigned vectorEnd; + length += offset; // We like to think of the length as being our length, rather than the output length. - ArrayStorage* storage = m_storage; + // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case. + ASSERT(length == this->length()); - unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength); - - unsigned numDefined = 0; - unsigned numUndefined = 0; - - for (; numDefined < usedVectorLength; ++numDefined) { - JSValue v = storage->m_vector[numDefined]; - if (!v || v.isUndefined()) - break; + switch (indexingType()) { + case ArrayClass: + return; + + case ArrayWithUndecided: { + vector = 0; + vectorEnd = 0; + break; } - for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValue v = storage->m_vector[i]; - if (v) { - if (v.isUndefined()) - ++numUndefined; - else - storage->m_vector[numDefined++] = v; - } + + case ArrayWithInt32: + case ArrayWithContiguous: { + vector = m_butterfly->contiguous().data(); + vectorEnd = m_butterfly->publicLength(); + break; } - - unsigned newUsedVectorLength = numDefined + numUndefined; - - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - newUsedVectorLength += map->size(); - if (newUsedVectorLength > m_vectorLength) { - // Check that it is possible to allocate an array large enough to hold all the entries - if not, - // exception is thrown by caller. - if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) - return 0; - storage = m_storage; + + case ArrayWithDouble: { + vector = 0; + vectorEnd = 0; + for (; i < m_butterfly->publicLength(); ++i) { + ASSERT(i < butterfly()->vectorLength()); + double v = m_butterfly->contiguousDouble()[i]; + if (v != v) + break; + exec->r(firstElementDest + i - offset) = JSValue(JSValue::EncodeAsDouble, v); } - - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - storage->m_vector[numDefined++] = it->second; - - delete map; - storage->m_sparseValueMap = 0; + break; } - - for (unsigned i = numDefined; i < newUsedVectorLength; ++i) - storage->m_vector[i] = jsUndefined(); - for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - storage->m_vector[i] = JSValue(); - - storage->m_numValuesInVector = newUsedVectorLength; - - checkConsistency(SortConsistencyCheck); - - return numDefined; -} - -void* JSArray::subclassData() const -{ - return m_storage->subclassData; -} - -void JSArray::setSubclassData(void* d) -{ - m_storage->subclassData = d; -} - -#if CHECK_ARRAY_CONSISTENCY - -void JSArray::checkConsistency(ConsistencyCheckType type) -{ - ASSERT(m_storage); - if (type == SortConsistencyCheck) - ASSERT(!m_storage->m_sparseValueMap); - - unsigned numValuesInVector = 0; - for (unsigned i = 0; i < m_vectorLength; ++i) { - if (JSValue value = m_storage->m_vector[i]) { - ASSERT(i < m_storage->m_length); - if (type != DestructorConsistencyCheck) - value->type(); // Likely to crash if the object was deallocated. - ++numValuesInVector; - } else { - if (type == SortConsistencyCheck) - ASSERT(i >= m_storage->m_numValuesInVector); - } + + case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { + ArrayStorage* storage = m_butterfly->arrayStorage(); + vector = storage->m_vector; + vectorEnd = min(length, storage->vectorLength()); + break; } - ASSERT(numValuesInVector == m_storage->m_numValuesInVector); - ASSERT(numValuesInVector <= m_storage->m_length); - - if (m_storage->m_sparseValueMap) { - SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end(); - for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) { - unsigned index = it->first; - ASSERT(index < m_storage->m_length); - ASSERT(index >= m_vectorLength); - ASSERT(index <= MAX_ARRAY_INDEX); - ASSERT(it->second); - if (type != DestructorConsistencyCheck) - it->second->type(); // Likely to crash if the object was deallocated. - } + + default: + CRASH(); +#if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE) + vector = 0; + vectorEnd = 0; + break; +#endif + } + + for (; i < vectorEnd; ++i) { + WriteBarrier& v = vector[i]; + if (!v) + break; + exec->r(firstElementDest + i - offset) = v.get(); + } + + for (; i < length; ++i) { + exec->r(firstElementDest + i - offset) = get(exec, i); + if (UNLIKELY(exec->vm().exception())) + return; } } -#endif - } // namespace JSC