X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/14957cd040308e3eeec43d26bae5d76da13fcd85..cb9aa2694aba0ae4f946ed34b8e0f6c99c1cfe44:/runtime/JSArray.cpp diff --git a/runtime/JSArray.cpp b/runtime/JSArray.cpp index 6bc3163..f4bc093 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 Apple Inc. All rights reserved. * Copyright (C) 2003 Peter Kelly (pmk@post.com) * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com) * @@ -24,854 +24,995 @@ #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 "Reject.h" #include #include #include -#include 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 - -// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate -// for an array that was created with a sepcified length (e.g. a = new Array(123)) -#define BASE_VECTOR_LEN 4U - -// The upper bound to the size we'll grow a zero length array when the first element -// is added. -#define FIRST_VECTOR_GROW 4U - -// 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::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0}; - -// We keep track of the size of the last array after it was grown. We use this -// as a simple heuristic for as the value to grow the next array from size 0. -// This value is capped by the constant FIRST_VECTOR_GROW defined above. -static unsigned lastArraySize = 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 bool isDenseEnoughForVector(unsigned length, unsigned numValues) -{ - return length / minDensityMultiplier <= numValues; -} - -#if !CHECK_ARRAY_CONSISTENCY - -inline void JSArray::checkConsistency(ConsistencyCheckType) -{ -} - -#endif - -JSArray::JSArray(VPtrStealingHackType) - : JSNonFinalObject(VPtrStealingHack) -{ -} - -JSArray::JSArray(JSGlobalData& globalData, Structure* structure) - : JSNonFinalObject(globalData, structure) -{ - ASSERT(inherits(&s_info)); - - unsigned initialCapacity = 0; - - m_storage = static_cast(fastZeroedMalloc(storageSize(initialCapacity))); - m_storage->m_allocBase = m_storage; - m_indexBias = 0; - m_vectorLength = initialCapacity; +STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray); - checkConsistency(); +const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)}; - Heap::heap(this)->reportExtraMemoryCost(storageSize(0)); -} - -JSArray::JSArray(JSGlobalData& globalData, Structure* structure, unsigned initialLength, ArrayCreationMode creationMode) - : JSNonFinalObject(globalData, structure) +Butterfly* createArrayButterflyInDictionaryIndexingMode( + VM& vm, JSCell* intendedOwner, unsigned initialLength) { - ASSERT(inherits(&s_info)); - - unsigned initialCapacity; - if (creationMode == CreateCompact) - initialCapacity = initialLength; - else - initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX); - - m_storage = static_cast(fastMalloc(storageSize(initialCapacity))); - m_storage->m_allocBase = m_storage; - m_storage->m_length = initialLength; - m_indexBias = 0; - m_vectorLength = initialCapacity; - m_storage->m_sparseValueMap = 0; - m_storage->subclassData = 0; - m_storage->reportedMapCapacity = 0; - - if (creationMode == CreateCompact) { -#if CHECK_ARRAY_CONSISTENCY - m_storage->m_inCompactInitialization = !!initialCapacity; -#endif - m_storage->m_length = 0; - m_storage->m_numValuesInVector = initialCapacity; - } else { -#if CHECK_ARRAY_CONSISTENCY - storage->m_inCompactInitialization = false; -#endif - m_storage->m_length = initialLength; - m_storage->m_numValuesInVector = 0; - WriteBarrier* vector = m_storage->m_vector; - for (size_t i = 0; i < initialCapacity; ++i) - vector[i].clear(); - } - - checkConsistency(); - - Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity)); + 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(JSGlobalData& globalData, Structure* structure, const ArgList& list) - : JSNonFinalObject(globalData, structure) +void JSArray::setLengthWritable(ExecState* exec, bool writable) { - ASSERT(inherits(&s_info)); - - unsigned initialCapacity = list.size(); - unsigned initialStorage; - - // If the ArgList is empty, allocate space for 3 entries. This value empirically - // works well for benchmarks. - if (!initialCapacity) - initialStorage = 3; - else - initialStorage = initialCapacity; - - m_storage = static_cast(fastMalloc(storageSize(initialStorage))); - m_storage->m_allocBase = m_storage; - m_indexBias = 0; - m_storage->m_length = initialCapacity; - m_vectorLength = initialStorage; - m_storage->m_numValuesInVector = initialCapacity; - m_storage->m_sparseValueMap = 0; - m_storage->subclassData = 0; - m_storage->reportedMapCapacity = 0; -#if CHECK_ARRAY_CONSISTENCY - m_storage->m_inCompactInitialization = false; -#endif - - size_t i = 0; - WriteBarrier* vector = m_storage->m_vector; - ArgList::const_iterator end = list.end(); - for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) - vector[i].set(globalData, this, *it); - for (; i < initialStorage; i++) - vector[i].clear(); - - checkConsistency(); - - Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage)); -} + 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->m_allocBase); + 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 value = storage->m_vector[i].get(); - if (value) { - slot.setValue(value); + // 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.setValue(it->second.get()); - 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, "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. + 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(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). + unsigned index = propertyName.asIndex(); + if (index != PropertyName::NotAnIndex) { + // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false. + 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(length()), DontDelete | DontEnum); + unsigned attributes = thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly; + slot.setValue(thisObject, attributes, jsNumber(thisObject->length())); return true; } - ArrayStorage* storage = m_storage; - - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(isArrayIndex); - if (isArrayIndex) { - if (i >= storage->m_length) - return false; - if (i < m_vectorLength) { - WriteBarrier& value = storage->m_vector[i]; - if (value) { - descriptor.setDescriptor(value.get(), 0); - 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()) { - descriptor.setDescriptor(it->second.get(), 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, createRangeError(exec, "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(); - - ArrayStorage* storage = m_storage; - - unsigned length = storage->m_length; - if (i >= length && i <= MAX_ARRAY_INDEX) { - length = i + 1; - storage->m_length = length; - } + JSArray* thisObject = jsCast(cell); - if (i < m_vectorLength) { - WriteBarrier& valueSlot = storage->m_vector[i]; - if (valueSlot) { - valueSlot.set(exec->globalData(), this, value); - checkConsistency(); - return; - } - valueSlot.set(exec->globalData(), this, value); - ++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; + unsigned da = *static_cast(a); + unsigned db = *static_cast(b); + return (da > db) - (da < db); +} - if (i >= MIN_SPARSE_ARRAY_INDEX) { - if (i > MAX_ARRAY_INDEX) { - PutPropertySlot slot; - put(exec, Identifier::from(exec, i), value, slot); - return; - } +void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode) +{ + JSArray* thisObject = jsCast(object); - // 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; - } + if (mode == IncludeDontEnumProperties) + propertyNames.add(exec->propertyNames().length); - WriteBarrier temp; - pair result = map->add(i, temp); - result.first->second.set(exec->globalData(), this, value); - if (!result.second) // pre-existing entry - return; + JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode); +} - size_t capacity = map->capacity(); - if (capacity != storage->reportedMapCapacity) { - Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue))); - storage->reportedMapCapacity = capacity; - } - return; - } +// 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) +{ + 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; + newStorageCapacity = desiredCapacity; } - // 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].set(exec->globalData(), this, value); - ++storage->m_numValuesInVector; - checkConsistency(); - } else - throwOutOfMemoryError(exec); - return; + // 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); } - // Decide how many values it would be best to move from the map. - unsigned newNumValuesInVector = storage->m_numValuesInVector + 1; - unsigned newVectorLength = getNewVectorLength(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 needLength = max(i + 1, storage->m_length); - unsigned proposedNewNumValuesInVector = newNumValuesInVector; - // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further. - while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) { - unsigned proposedNewVectorLength = getNewVectorLength(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; - } - } + unsigned newVectorLength = requiredVectorLength + postCapacity; + unsigned newIndexBias = newStorageCapacity - newVectorLength; - void* baseStorage = storage->m_allocBase; - - if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) { - throwOutOfMemoryError(exec); - return; - } + Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity); - m_storage = reinterpret_cast_ptr(static_cast(baseStorage) + m_indexBias * sizeof(JSValue)); - m_storage->m_allocBase = baseStorage; - storage = m_storage; - - unsigned vectorLength = m_vectorLength; - WriteBarrier* vector = storage->m_vector; + 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); - if (newNumValuesInVector == storage->m_numValuesInVector + 1) { - for (unsigned j = vectorLength; j < newVectorLength; ++j) - vector[j].clear(); - if (i > MIN_SPARSE_ARRAY_INDEX) - map->remove(i); - } else { - for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j) - vector[j].clear(); - JSGlobalData& globalData = exec->globalData(); - for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) - vector[j].set(globalData, this, map->take(j).get()); + WriteBarrier* newVector = newButterfly->arrayStorage()->m_vector; + for (unsigned i = requiredVectorLength; i < newVectorLength; i++) + newVector[i].clear(); } - ASSERT(i < newVectorLength); - - m_vectorLength = newVectorLength; - storage->m_numValuesInVector = newNumValuesInVector; - - storage->m_vector[i].set(exec->globalData(), this, value); - - checkConsistency(); - - Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); -} - -bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName) -{ - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(isArrayIndex); - if (isArrayIndex) - return deleteProperty(exec, i); - - if (propertyName == exec->propertyNames().length) - return false; + newButterfly->arrayStorage()->setVectorLength(newVectorLength); + newButterfly->arrayStorage()->m_indexBias = newIndexBias; + setButterflyWithoutChangingStructure(vm, newButterfly); - return JSObject::deleteProperty(exec, propertyName); + return true; } -bool JSArray::deleteProperty(ExecState* exec, unsigned i) +bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage) { - checkConsistency(); + 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); + } - ArrayStorage* storage = m_storage; - - if (i < m_vectorLength) { - WriteBarrier& valueSlot = storage->m_vector[i]; - if (!valueSlot) { - checkConsistency(); - return false; + // 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(); + } } - valueSlot.clear(); - --storage->m_numValuesInVector; - checkConsistency(); - return true; } - 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; - } + 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; } } - checkConsistency(); - - if (i > MAX_ARRAY_INDEX) - return deleteProperty(exec, Identifier::from(exec, i)); + storage->setLength(newLength); - return false; + return true; } -void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode) +bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException) { - // 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. - - ArrayStorage* storage = m_storage; - - 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)); - } - - 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)); + 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 (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; } - - if (mode == IncludeDontEnumProperties) - propertyNames.add(exec->propertyNames().length); - - JSObject::getOwnPropertyNames(exec, propertyNames, mode); } -ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength) +JSValue JSArray::pop(ExecState* exec) { - ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH); - - unsigned increasedLength; - unsigned maxInitLength = min(m_storage->m_length, 100000U); - - if (desiredLength < maxInitLength) - increasedLength = maxInitLength; - else if (!m_vectorLength) - increasedLength = max(desiredLength, lastArraySize); - else { - // Mathematically equivalent to: - // increasedLength = (newLength * 3 + 1) / 2; - // or: - // increasedLength = (unsigned)ceil(newLength * 1.5)); - // This form is not prone to internal overflow. - increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1); + 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(); + } - ASSERT(increasedLength >= desiredLength); - - lastArraySize = min(increasedLength, FIRST_VECTOR_GROW); - - return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH); + 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; + } + + 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, "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; } -bool JSArray::increaseVectorLength(unsigned newLength) +// 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) { - // 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 = getNewVectorLength(newLength); - void* baseStorage = storage->m_allocBase; + 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 (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) - return false; + 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, "Invalid array length")); + return; + } + + putByIndexBeyondVectorLengthWithoutAttributes(exec, length, value); + return; + } - storage = m_storage = reinterpret_cast_ptr(static_cast(baseStorage) + m_indexBias * sizeof(JSValue)); - m_storage->m_allocBase = baseStorage; + 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, "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; + } - WriteBarrier* vector = storage->m_vector; - for (unsigned i = vectorLength; i < newVectorLength; ++i) - vector[i].clear(); + 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; + } + + if (length > MAX_ARRAY_INDEX) { + methodTable(exec->vm())->putByIndex(this, exec, length, value, true); + if (!exec->hadException()) + exec->vm().throwException(exec, createRangeError(exec, "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; + } - m_vectorLength = newVectorLength; - - Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + // 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, "Invalid array length")); + return; + } - return true; + // Handled the same as putIndex. + putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage); + break; + } + + default: + RELEASE_ASSERT_NOT_REACHED(); + } } -bool JSArray::increaseVectorPrefixLength(unsigned newLength) +bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, 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 oldLength = storage->length(); + RELEASE_ASSERT(count <= oldLength); - unsigned vectorLength = m_vectorLength; - ASSERT(newLength > vectorLength); - ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); - unsigned newVectorLength = getNewVectorLength(newLength); - - void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias)); - if (!newBaseStorage) + // 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)) + || inSparseIndexingMode() + || shouldUseSlowPut(indexingType())) { return false; + } + + if (!oldLength) + return true; - m_indexBias += newVectorLength - newLength; + unsigned length = oldLength - count; - m_storage = reinterpret_cast_ptr(static_cast(newBaseStorage) + m_indexBias * sizeof(JSValue)); - - memcpy(m_storage, storage, storageSize(0)); - memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue)); + storage->m_numValuesInVector -= count; + storage->setLength(length); - m_storage->m_allocBase = newBaseStorage; - m_vectorLength = newLength; + unsigned vectorLength = storage->vectorLength(); + if (!vectorLength) + return true; - fastFree(storage->m_allocBase); - ASSERT(newLength > vectorLength); - unsigned delta = newLength - vectorLength; - for (unsigned i = 0; i < delta; i++) - m_storage->m_vector[i].clear(); - Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + if (startIndex >= vectorLength) + return true; - return true; -} + if (startIndex + count > vectorLength) + count = vectorLength - startIndex; - -void JSArray::setLength(unsigned newLength) -{ - ArrayStorage* storage = m_storage; + unsigned usedVectorLength = min(vectorLength, oldLength); -#if CHECK_ARRAY_CONSISTENCY - if (!storage->m_inCompactInitialization) - checkConsistency(); - else - storage->m_inCompactInitialization = false; -#endif - - unsigned length = storage->m_length; - - if (newLength < length) { - unsigned usedVectorLength = min(length, m_vectorLength); - for (unsigned i = newLength; i < usedVectorLength; ++i) { - WriteBarrier& valueSlot = storage->m_vector[i]; - bool hadValue = valueSlot; - valueSlot.clear(); - storage->m_numValuesInVector -= hadValue; - } - - 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); + 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); } - if (map->isEmpty()) { - delete map; - storage->m_sparseValueMap = 0; + } + // 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 { + 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. } - - storage->m_length = newLength; - - checkConsistency(); + + return true; } -JSValue JSArray::pop() +bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count) { - checkConsistency(); - - ArrayStorage* storage = m_storage; + VM& vm = exec->vm(); + RELEASE_ASSERT(count > 0); - unsigned length = storage->m_length; - if (!length) - return jsUndefined(); - - --length; - - JSValue result; + 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)); + } - if (length < m_vectorLength) { - WriteBarrier& valueSlot = storage->m_vector[length]; - if (valueSlot) { - --storage->m_numValuesInVector; - result = valueSlot.get(); - valueSlot.clear(); - } else - result = jsUndefined(); - } else { - result = jsUndefined(); - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - SparseArrayValueMap::iterator it = map->find(length); - if (it != map->end()) { - result = it->second.get(); - map->remove(it); - if (map->isEmpty()) { - delete map; - storage->m_sparseValueMap = 0; + 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 { + memmove(m_butterfly->contiguousDouble().data() + startIndex, + m_butterfly->contiguousDouble().data() + startIndex + count, + sizeof(JSValue) * (end - startIndex)); } + 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; + } +} + +// Returns true if the unshift can be handled, false to fallback. +bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage) +{ + unsigned length = storage->length(); - storage->m_length = length; + RELEASE_ASSERT(startIndex <= length); - checkConsistency(); + // 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; - return result; -} + bool moveFront = !startIndex || startIndex < length / 2; -void JSArray::push(ExecState* exec, JSValue value) -{ - checkConsistency(); - - ArrayStorage* storage = m_storage; + unsigned vectorLength = storage->vectorLength(); - if (storage->m_length < m_vectorLength) { - storage->m_vector[storage->m_length].set(exec->globalData(), this, value); - ++storage->m_numValuesInVector; - ++storage->m_length; - checkConsistency(); - return; + 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 true; } - if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) { - SparseArrayValueMap* map = storage->m_sparseValueMap; - if (!map || map->isEmpty()) { - if (increaseVectorLength(storage->m_length + 1)) { - storage = m_storage; - storage->m_vector[storage->m_length].set(exec->globalData(), this, value); - ++storage->m_numValuesInVector; - ++storage->m_length; - checkConsistency(); - return; - } - checkConsistency(); - throwOutOfMemoryError(exec); - return; - } + WriteBarrier* vector = storage->m_vector; + + 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)); } - putSlowCase(exec, storage->m_length++, value); + for (unsigned i = 0; i < count; i++) + vector[i + startIndex].clear(); + return true; } -void JSArray::shiftCount(ExecState* exec, int count) +bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count) { - ASSERT(count > 0); - - ArrayStorage* storage = m_storage; - - unsigned oldLength = storage->m_length; - - if (!oldLength) - return; - - if (oldLength != storage->m_numValuesInVector) { - // If m_length and m_numValuesInVector aren't the same, we have a sparse vector - // which means we need to go through each entry looking for the the "empty" - // slots and then fill them with possible properties. See ECMA spec. - // 15.4.4.9 steps 11 through 13. - for (unsigned i = count; i < oldLength; ++i) { - if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) { - PropertySlot slot(this); - JSValue p = prototype(); - if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot))) - put(exec, i, slot.getValue(exec, i)); - } - } - - storage = m_storage; // The put() above could have grown the vector and realloc'ed storage. + switch (indexingType()) { + case ArrayClass: + case ArrayWithUndecided: + // We could handle this. But it shouldn't ever come up, so we won't. + return false; - // Need to decrement numValuesInvector based on number of real entries - for (unsigned i = 0; i < (unsigned)count; ++i) - if ((i < m_vectorLength) && (storage->m_vector[i])) - --storage->m_numValuesInVector; - } else - storage->m_numValuesInVector -= count; - - storage->m_length -= count; - - if (m_vectorLength) { - count = min(m_vectorLength, (unsigned)count); + case ArrayWithInt32: + case ArrayWithContiguous: { + unsigned oldLength = m_butterfly->publicLength(); - m_vectorLength -= count; + // 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())); - if (m_vectorLength) { - char* newBaseStorage = reinterpret_cast(storage) + count * sizeof(JSValue); - memmove(newBaseStorage, storage, storageSize(0)); - m_storage = reinterpret_cast_ptr(newBaseStorage); + 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())); + } - m_indexBias += count; + 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; } -} - -void JSArray::unshiftCount(ExecState* exec, int count) -{ - ArrayStorage* storage = m_storage; - - ASSERT(m_indexBias >= 0); - ASSERT(count >= 0); - - unsigned length = storage->m_length; - - if (length != storage->m_numValuesInVector) { - // If m_length and m_numValuesInVector aren't the same, we have a sparse vector - // which means we need to go through each entry looking for the the "empty" - // slots and then fill them with possible properties. See ECMA spec. - // 15.4.4.13 steps 8 through 10. - for (unsigned i = 0; i < length; ++i) { - if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) { - PropertySlot slot(this); - JSValue p = prototype(); - if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot))) - put(exec, i, slot.getValue(exec, i)); - } + + 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())); } + + 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; } - - storage = m_storage; // The put() above could have grown the vector and realloc'ed storage. - - if (m_indexBias >= count) { - m_indexBias -= count; - char* newBaseStorage = reinterpret_cast(storage) - count * sizeof(JSValue); - memmove(newBaseStorage, storage, storageSize(0)); - m_storage = reinterpret_cast_ptr(newBaseStorage); - m_vectorLength += count; - } else if (!increaseVectorPrefixLength(m_vectorLength + count)) { - throwOutOfMemoryError(exec); - return; + + case ArrayWithArrayStorage: + case ArrayWithSlowPutArrayStorage: + return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage()); + + default: + CRASH(); + return false; } +} - WriteBarrier* vector = m_storage->m_vector; - for (int i = 0; i < count; i++) - vector[i].clear(); +static int compareNumbersForQSortWithInt32(const void* a, const void* b) +{ + int32_t ia = static_cast(a)->asInt32(); + int32_t ib = static_cast(b)->asInt32(); + return ia - ib; } -void JSArray::visitChildren(SlotVisitor& visitor) +static int compareNumbersForQSortWithDouble(const void* a, const void* b) { - ASSERT_GC_OBJECT_INHERITS(this, &s_info); - COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag); - ASSERT(structure()->typeInfo().overridesVisitChildren()); - visitChildrenDirect(visitor); + double da = *static_cast(a); + double db = *static_cast(b); + return (da > db) - (da < db); } static int compareNumbersForQSort(const void* a, const void* b) { - double da = static_cast(a)->uncheckedGetNumber(); - double db = static_cast(b)->uncheckedGetNumber(); + double da = static_cast(a)->asNumber(); + double db = static_cast(b)->asNumber(); return (da > db) - (da < db); } @@ -882,107 +1023,268 @@ static int compareByStringPairForQSort(const void* a, const void* b) return codePointCompare(va->second, vb->second); } -void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +template +void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) { - ArrayStorage* storage = m_storage; - - unsigned lengthNotIncludingUndefined = compactForSorting(); - if (storage->m_sparseValueMap) { + ASSERT(arrayIndexingType == ArrayWithInt32 || arrayIndexingType == ArrayWithDouble || arrayIndexingType == ArrayWithContiguous || arrayIndexingType == ArrayWithArrayStorage); + + unsigned lengthNotIncludingUndefined; + unsigned newRelevantLength; + compactForSorting( + lengthNotIncludingUndefined, + newRelevantLength); + + ContiguousJSValues data = indexingData(); + + if (arrayIndexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) { throwOutOfMemoryError(exec); return; } - + if (!lengthNotIncludingUndefined) return; - + bool allValuesAreNumbers = true; - size_t size = storage->m_numValuesInVector; - for (size_t i = 0; i < size; ++i) { - if (!storage->m_vector[i].isNumber()) { - allValuesAreNumbers = false; - break; + switch (arrayIndexingType) { + case ArrayWithInt32: + case ArrayWithDouble: + break; + + default: + for (size_t i = 0; i < newRelevantLength; ++i) { + if (!data[i].isNumber()) { + allValuesAreNumbers = false; + break; + } } + break; } - + 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(storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort); - - checkConsistency(SortConsistencyCheck); + int (*compare)(const void*, const void*); + switch (arrayIndexingType) { + case ArrayWithInt32: + compare = compareNumbersForQSortWithInt32; + break; + + case ArrayWithDouble: + compare = compareNumbersForQSortWithDouble; + ASSERT(sizeof(WriteBarrier) == sizeof(double)); + break; + + default: + compare = compareNumbersForQSort; + break; + } + ASSERT(data.length() >= newRelevantLength); + qsort(data.data(), newRelevantLength, sizeof(WriteBarrier), compare); + return; } -void JSArray::sort(ExecState* exec) +void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) { - ArrayStorage* storage = m_storage; + ASSERT(!inSparseIndexingMode()); - unsigned lengthNotIncludingUndefined = compactForSorting(); - if (storage->m_sparseValueMap) { - throwOutOfMemoryError(exec); + switch (indexingType()) { + case ArrayClass: + return; + + case ArrayWithInt32: + sortNumericVector(exec, compareFunction, callType, callData); + break; + + case ArrayWithDouble: + sortNumericVector(exec, compareFunction, callType, callData); + break; + + case ArrayWithContiguous: + sortNumericVector(exec, compareFunction, callType, callData); + return; + + case ArrayWithArrayStorage: + sortNumericVector(exec, compareFunction, callType, callData); + return; + + default: + CRASH(); return; } +} + +template struct ContiguousTypeAccessor { + typedef WriteBarrier Type; + static JSValue getAsValue(ContiguousData data, size_t i) { return data[i].get(); } + static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData data, size_t i, JSValue value) + { + data[i].set(vm, thisValue, value); + } + static void replaceDataReference(ContiguousData* outData, ContiguousJSValues inData) + { + *outData = inData; + } +}; - if (!lengthNotIncludingUndefined) +template <> struct ContiguousTypeAccessor { + typedef double Type; + static JSValue getAsValue(ContiguousData data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); } + static void setWithValue(VM&, JSArray*, ContiguousData data, size_t i, JSValue value) + { + data[i] = value.asNumber(); + } + static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData*, ContiguousJSValues) + { + RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort."); + } +}; + + +template +void JSArray::sortCompactedVector(ExecState* exec, ContiguousData data, unsigned relevantLength) +{ + if (!relevantLength) return; + + VM& vm = exec->vm(); // 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); + + Vector values(relevantLength); if (!values.begin()) { throwOutOfMemoryError(exec); return; } - + Heap::heap(this)->pushTempSortVector(&values); + + bool isSortingPrimitiveValues = true; - for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { - JSValue value = storage->m_vector[i].get(); + for (size_t i = 0; i < relevantLength; i++) { + JSValue value = ContiguousTypeAccessor::getAsValue(data, i); + ASSERT(arrayIndexingType != ArrayWithInt32 || value.isInt32()); ASSERT(!value.isUndefined()); values[i].first = value; + if (arrayIndexingType != ArrayWithDouble && arrayIndexingType != ArrayWithInt32) + isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive(); } - + // 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); - + + for (size_t i = 0; i < relevantLength; i++) + values[i].second = values[i].first.toWTFStringInline(exec); + if (exec->hadException()) { Heap::heap(this)->popTempSortVector(&values); return; } - + // 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); + if (isSortingPrimitiveValues) + qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); + else + 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 (storage->m_length < lengthNotIncludingUndefined) - storage->m_length = lengthNotIncludingUndefined; - - JSGlobalData& globalData = exec->globalData(); - for (size_t i = 0; i < lengthNotIncludingUndefined; i++) - storage->m_vector[i].set(globalData, this, values[i].first); + switch (arrayIndexingType) { + case ArrayWithInt32: + case ArrayWithDouble: + case ArrayWithContiguous: + ensureLength(vm, relevantLength); + break; + + case ArrayWithArrayStorage: + if (arrayStorage()->vectorLength() < relevantLength) { + increaseVectorLength(exec->vm(), relevantLength); + ContiguousTypeAccessor::replaceDataReference(&data, arrayStorage()->vector()); + } + if (arrayStorage()->length() < relevantLength) + arrayStorage()->setLength(relevantLength); + break; + + default: + CRASH(); + } + for (size_t i = 0; i < relevantLength; i++) + ContiguousTypeAccessor::setWithValue(vm, this, data, i, values[i].first); + Heap::heap(this)->popTempSortVector(&values); +} + +void JSArray::sort(ExecState* exec) +{ + ASSERT(!inSparseIndexingMode()); - checkConsistency(SortConsistencyCheck); + switch (indexingType()) { + case ArrayClass: + case ArrayWithUndecided: + return; + + case ArrayWithInt32: { + unsigned lengthNotIncludingUndefined; + unsigned newRelevantLength; + compactForSorting( + lengthNotIncludingUndefined, newRelevantLength); + + sortCompactedVector( + exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined); + return; + } + + case ArrayWithDouble: { + unsigned lengthNotIncludingUndefined; + unsigned newRelevantLength; + compactForSorting( + lengthNotIncludingUndefined, newRelevantLength); + + sortCompactedVector( + exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined); + return; + } + + case ArrayWithContiguous: { + unsigned lengthNotIncludingUndefined; + unsigned newRelevantLength; + compactForSorting( + lengthNotIncludingUndefined, newRelevantLength); + + sortCompactedVector( + exec, m_butterfly->contiguous(), lengthNotIncludingUndefined); + return; + } + + case ArrayWithArrayStorage: { + unsigned lengthNotIncludingUndefined; + unsigned newRelevantLength; + compactForSorting( + lengthNotIncludingUndefined, newRelevantLength); + ArrayStorage* storage = m_butterfly->arrayStorage(); + ASSERT(!storage->m_sparseMap); + + sortCompactedVector(exec, storage->vector(), lengthNotIncludingUndefined); + return; + } + + default: + RELEASE_ASSERT_NOT_REACHED(); + } } struct AVLTreeNodeForArrayCompare { @@ -1000,12 +1302,11 @@ struct AVLTreeAbstractorForArrayCompare { typedef JSValue key; typedef int32_t size; - Vector m_nodes; + 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; } @@ -1044,15 +1345,15 @@ struct AVLTreeAbstractorForArrayCompare { double compareResult; if (m_cachedCall) { - m_cachedCall->setThis(m_globalThisValue); + m_cachedCall->setThis(jsUndefined()); m_cachedCall->setArgument(0, va); m_cachedCall->setArgument(1, vb); - compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec)); + compareResult = m_cachedCall->call().toNumber(m_exec); } 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); + compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec); } return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. } @@ -1063,58 +1364,61 @@ struct AVLTreeAbstractorForArrayCompare { static handle null() { return 0x7FFFFFFF; } }; -void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +template +void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) { - checkConsistency(); - - ArrayStorage* storage = m_storage; - + ASSERT(!inSparseIndexingMode()); + ASSERT(arrayIndexingType == indexingType()); + // 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(storage->m_length <= static_cast(std::numeric_limits::max())); - if (storage->m_length > static_cast(std::numeric_limits::max())) + ASSERT(m_butterfly->publicLength() <= static_cast(std::numeric_limits::max())); + if (m_butterfly->publicLength() > static_cast(std::numeric_limits::max())) return; - - unsigned usedVectorLength = min(storage->m_length, m_vectorLength); - unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0); - + + unsigned usedVectorLength = relevantLength(); + unsigned nodeCount = usedVectorLength; + if (!nodeCount) return; - + 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.grow(nodeCount); - + if (callType == CallTypeJS) - tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2)); - + tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast(compareFunction), 2)); + if (!tree.abstractor().m_nodes.begin()) { throwOutOfMemoryError(exec); return; } - + // 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; - + // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree. for (; numDefined < usedVectorLength; ++numDefined) { - JSValue v = storage->m_vector[numDefined].get(); + if (numDefined >= m_butterfly->vectorLength()) + break; + JSValue v = getHolyIndexQuickly(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 = storage->m_vector[i].get(); + if (i >= m_butterfly->vectorLength()) + break; + JSValue v = getHolyIndexQuickly(i); if (v) { if (v.isUndefined()) ++numUndefined; @@ -1125,204 +1429,297 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, } } } - + 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 ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) { - throwOutOfMemoryError(exec); - return; - } - } - storage = m_storage; - - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { - tree.abstractor().m_nodes[numDefined].value = it->second.get(); - tree.insert(numDefined); - ++numDefined; - } - - delete map; - storage->m_sparseValueMap = 0; - } - - 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. - + // The array size may have changed. Figure out the new bounds. + unsigned newestUsedVectorLength = currentRelevantLength(); + + unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast(tree.abstractor().m_nodes.size())); + unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength); + unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength); + // Copy the values back into m_storage. AVLTree::Iterator iter; iter.start_iter_least(tree); - JSGlobalData& globalData = exec->globalData(); - for (unsigned i = 0; i < numDefined; ++i) { - storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value); + VM& vm = exec->vm(); + for (unsigned i = 0; i < elementsToExtractThreshold; ++i) { + ASSERT(i < butterfly()->vectorLength()); + if (indexingType() == ArrayWithDouble) + butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber(); + else + currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value); ++iter; } - // Put undefined values back in. - for (unsigned i = numDefined; i < newUsedVectorLength; ++i) - storage->m_vector[i].setUndefined(); + switch (indexingType()) { + case ArrayWithInt32: + case ArrayWithDouble: + ASSERT(elementsToExtractThreshold == undefinedElementsThreshold); + break; + + default: + for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) { + ASSERT(i < butterfly()->vectorLength()); + currentIndexingData()[i].setUndefined(); + } + } // Ensure that unused values in the vector are zeroed out. - for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - storage->m_vector[i].clear(); + for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) { + ASSERT(i < butterfly()->vectorLength()); + if (indexingType() == ArrayWithDouble) + butterfly()->contiguousDouble()[i] = PNaN; + else + currentIndexingData()[i].clear(); + } + + if (hasAnyArrayStorage(indexingType())) + arrayStorage()->m_numValuesInVector = newUsedVectorLength; +} + +void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +{ + ASSERT(!inSparseIndexingMode()); + + switch (indexingType()) { + case ArrayClass: + case ArrayWithUndecided: + return; + + case ArrayWithInt32: + sortVector(exec, compareFunction, callType, callData); + return; + + case ArrayWithDouble: + sortVector(exec, compareFunction, callType, callData); + return; - storage->m_numValuesInVector = newUsedVectorLength; + case ArrayWithContiguous: + sortVector(exec, compareFunction, callType, callData); + return; - checkConsistency(SortConsistencyCheck); + case ArrayWithArrayStorage: + sortVector(exec, compareFunction, callType, callData); + return; + + default: + RELEASE_ASSERT_NOT_REACHED(); + } } void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) { - ArrayStorage* storage = m_storage; - - WriteBarrier* vector = storage->m_vector; - unsigned vectorEnd = min(storage->m_length, m_vectorLength); unsigned i = 0; + unsigned vectorEnd; + WriteBarrier* vector; + + switch (indexingType()) { + case ArrayClass: + return; + + case ArrayWithUndecided: { + vector = 0; + vectorEnd = 0; + break; + } + + 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(); + vector = 0; + vectorEnd = 0; + break; + } + for (; i < vectorEnd; ++i) { WriteBarrier& v = vector[i]; if (!v) break; args.append(v.get()); } - - for (; i < storage->m_length; ++i) + + for (; i < length(); ++i) args.append(get(exec, i)); } -void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize) +void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t copyLength, int32_t firstVarArgOffset) { - ASSERT(m_storage->m_length >= maxSize); - UNUSED_PARAM(maxSize); - WriteBarrier* vector = m_storage->m_vector; - unsigned vectorEnd = min(maxSize, m_vectorLength); - unsigned i = 0; + unsigned i = firstVarArgOffset; + WriteBarrier* vector; + unsigned vectorEnd; + unsigned length = copyLength + firstVarArgOffset; + ASSERT(length == this->length()); + switch (indexingType()) { + case ArrayClass: + return; + + case ArrayWithUndecided: { + vector = 0; + vectorEnd = 0; + break; + } + + case ArrayWithInt32: + case ArrayWithContiguous: { + vector = m_butterfly->contiguous().data(); + vectorEnd = m_butterfly->publicLength(); + break; + } + + 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; + callFrame->setArgument(i - firstVarArgOffset, JSValue(JSValue::EncodeAsDouble, v)); + } + break; + } + + case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { + ArrayStorage* storage = m_butterfly->arrayStorage(); + vector = storage->m_vector; + vectorEnd = min(length, storage->vectorLength()); + break; + } + + default: + CRASH(); + vector = 0; + vectorEnd = 0; + break; + } + for (; i < vectorEnd; ++i) { WriteBarrier& v = vector[i]; if (!v) break; - buffer[i] = v.get(); + callFrame->setArgument(i - firstVarArgOffset, v.get()); } - - for (; i < maxSize; ++i) - buffer[i] = get(exec, i); + + for (; i < length; ++i) + callFrame->setArgument(i - firstVarArgOffset, get(exec, i)); } -unsigned JSArray::compactForSorting() +template +void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength) { - checkConsistency(); - - ArrayStorage* storage = m_storage; - - unsigned usedVectorLength = min(storage->m_length, m_vectorLength); + ASSERT(!inSparseIndexingMode()); + ASSERT(arrayIndexingType == indexingType()); - unsigned numDefined = 0; + unsigned myRelevantLength = relevantLength(); + + numDefined = 0; unsigned numUndefined = 0; - - for (; numDefined < usedVectorLength; ++numDefined) { - JSValue v = storage->m_vector[numDefined].get(); + + for (; numDefined < myRelevantLength; ++numDefined) { + ASSERT(numDefined < m_butterfly->vectorLength()); + if (arrayIndexingType == ArrayWithInt32) { + JSValue v = m_butterfly->contiguousInt32()[numDefined].get(); + if (!v) + break; + ASSERT(v.isInt32()); + continue; + } + if (arrayIndexingType == ArrayWithDouble) { + double v = m_butterfly->contiguousDouble()[numDefined]; + if (v != v) + break; + continue; + } + JSValue v = indexingData()[numDefined].get(); if (!v || v.isUndefined()) break; } - - for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValue v = storage->m_vector[i].get(); + + for (unsigned i = numDefined; i < myRelevantLength; ++i) { + ASSERT(i < m_butterfly->vectorLength()); + if (arrayIndexingType == ArrayWithInt32) { + JSValue v = m_butterfly->contiguousInt32()[i].get(); + if (!v) + continue; + ASSERT(v.isInt32()); + ASSERT(numDefined < m_butterfly->vectorLength()); + m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v); + continue; + } + if (arrayIndexingType == ArrayWithDouble) { + double v = m_butterfly->contiguousDouble()[i]; + if (v != v) + continue; + ASSERT(numDefined < m_butterfly->vectorLength()); + m_butterfly->contiguousDouble()[numDefined++] = v; + continue; + } + JSValue v = indexingData()[i].get(); if (v) { if (v.isUndefined()) ++numUndefined; - else - storage->m_vector[numDefined++].setWithoutWriteBarrier(v); - } - } - - 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; + else { + ASSERT(numDefined < m_butterfly->vectorLength()); + indexingData()[numDefined++].setWithoutWriteBarrier(v); + } } - - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.get()); - - delete map; - storage->m_sparseValueMap = 0; } - - for (unsigned i = numDefined; i < newUsedVectorLength; ++i) - storage->m_vector[i].setUndefined(); - for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - storage->m_vector[i].clear(); - - 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) -{ - ArrayStorage* storage = m_storage; - - ASSERT(storage); - if (type == SortConsistencyCheck) - ASSERT(!storage->m_sparseValueMap); - - unsigned numValuesInVector = 0; - for (unsigned i = 0; i < m_vectorLength; ++i) { - if (JSValue value = storage->m_vector[i]) { - ASSERT(i < storage->m_length); - if (type != DestructorConsistencyCheck) - value.isUndefined(); // Likely to crash if the object was deallocated. - ++numValuesInVector; - } else { - if (type == SortConsistencyCheck) - ASSERT(i >= storage->m_numValuesInVector); + + newRelevantLength = numDefined + numUndefined; + + if (hasAnyArrayStorage(arrayIndexingType)) + RELEASE_ASSERT(!arrayStorage()->m_sparseMap); + + switch (arrayIndexingType) { + case ArrayWithInt32: + case ArrayWithDouble: + RELEASE_ASSERT(numDefined == newRelevantLength); + break; + + default: + for (unsigned i = numDefined; i < newRelevantLength; ++i) { + ASSERT(i < m_butterfly->vectorLength()); + indexingData()[i].setUndefined(); } + break; } - ASSERT(numValuesInVector == storage->m_numValuesInVector); - ASSERT(numValuesInVector <= storage->m_length); - - if (storage->m_sparseValueMap) { - SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end(); - for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) { - unsigned index = it->first; - ASSERT(index < storage->m_length); - ASSERT(index >= storage->m_vectorLength); - ASSERT(index <= MAX_ARRAY_INDEX); - ASSERT(it->second); - if (type != DestructorConsistencyCheck) - it->second.isUndefined(); // Likely to crash if the object was deallocated. - } + for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) { + ASSERT(i < m_butterfly->vectorLength()); + if (arrayIndexingType == ArrayWithDouble) + m_butterfly->contiguousDouble()[i] = PNaN; + else + indexingData()[i].clear(); } -} -#endif + if (hasAnyArrayStorage(arrayIndexingType)) + arrayStorage()->m_numValuesInVector = newRelevantLength; +} } // namespace JSC