diff options
Diffstat (limited to 'Source/JavaScriptCore/runtime/JSArray.cpp')
| -rw-r--r-- | Source/JavaScriptCore/runtime/JSArray.cpp | 1322 |
1 files changed, 1322 insertions, 0 deletions
diff --git a/Source/JavaScriptCore/runtime/JSArray.cpp b/Source/JavaScriptCore/runtime/JSArray.cpp new file mode 100644 index 0000000..556a16e --- /dev/null +++ b/Source/JavaScriptCore/runtime/JSArray.cpp @@ -0,0 +1,1322 @@ +/* + * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) + * Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved. + * Copyright (C) 2003 Peter Kelly (pmk@post.com) + * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + */ + +#include "config.h" +#include "JSArray.h" + +#include "ArrayPrototype.h" +#include "CachedCall.h" +#include "Error.h" +#include "Executable.h" +#include "PropertyNameArray.h" +#include <wtf/AVLTree.h> +#include <wtf/Assertions.h> +#include <wtf/OwnPtr.h> +#include <Operations.h> + +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<unsigned>((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 <rdar://problem/5971391>. +#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::info = {"Array", 0, 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) + : JSObject(createStructure(jsNull())) +{ + unsigned initialCapacity = 0; + + m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity))); + m_storage->m_allocBase = m_storage; + m_indexBias = 0; + m_vectorLength = initialCapacity; + + checkConsistency(); + + // It's not safe to call Heap::heap(this) in order to report extra memory + // cost here, because the VPtrStealingHackType JSArray is not allocated on + // the heap. For the same reason, it's OK not to report extra cost. +} + +JSArray::JSArray(NonNullPassRefPtr<Structure> structure) + : JSObject(structure) +{ + unsigned initialCapacity = 0; + + m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity))); + m_storage->m_allocBase = m_storage; + m_indexBias = 0; + m_vectorLength = initialCapacity; + + checkConsistency(); + + Heap::heap(this)->reportExtraMemoryCost(storageSize(0)); +} + +JSArray::JSArray(NonNullPassRefPtr<Structure> structure, unsigned initialLength, ArrayCreationMode creationMode) + : JSObject(structure) +{ + unsigned initialCapacity; + if (creationMode == CreateCompact) + initialCapacity = initialLength; + else + initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX); + + m_storage = static_cast<ArrayStorage*>(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; + JSValue* vector = m_storage->m_vector; + for (size_t i = 0; i < initialCapacity; ++i) + vector[i] = JSValue(); + } + + checkConsistency(); + + Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity)); +} + +JSArray::JSArray(NonNullPassRefPtr<Structure> structure, const ArgList& list) + : JSObject(structure) +{ + 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<ArrayStorage*>(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; + JSValue* vector = m_storage->m_vector; + ArgList::const_iterator end = list.end(); + for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) + vector[i] = *it; + for (; i < initialStorage; i++) + vector[i] = JSValue(); + + checkConsistency(); + + Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage)); +} + +JSArray::~JSArray() +{ + ASSERT(vptr() == JSGlobalData::jsArrayVPtr); + checkConsistency(DestructorConsistencyCheck); + + delete m_storage->m_sparseValueMap; + fastFree(m_storage->m_allocBase); +} + +bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) +{ + ArrayStorage* storage = m_storage; + + if (i >= storage->m_length) { + if (i > MAX_ARRAY_INDEX) + return getOwnPropertySlot(exec, Identifier::from(exec, i), slot); + return false; + } + + if (i < m_vectorLength) { + JSValue& valueSlot = storage->m_vector[i]; + if (valueSlot) { + slot.setValueSlot(&valueSlot); + 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; + } + } + } + + return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot); +} + +bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot) +{ + if (propertyName == exec->propertyNames().length) { + slot.setValue(jsNumber(length())); + return true; + } + + bool isArrayIndex; + unsigned i = propertyName.toArrayIndex(isArrayIndex); + if (isArrayIndex) + return JSArray::getOwnPropertySlot(exec, i, slot); + + return JSObject::getOwnPropertySlot(exec, propertyName, slot); +} + +bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor) +{ + if (propertyName == exec->propertyNames().length) { + descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum); + 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) { + JSValue& value = storage->m_vector[i]; + if (value) { + descriptor.setDescriptor(value, 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, 0); + return true; + } + } + } + } + return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor); +} + +// ECMA 15.4.5.1 +void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot) +{ + bool isArrayIndex; + unsigned i = propertyName.toArrayIndex(isArrayIndex); + if (isArrayIndex) { + put(exec, i, value); + return; + } + + if (propertyName == exec->propertyNames().length) { + unsigned newLength = value.toUInt32(exec); + if (value.toNumber(exec) != static_cast<double>(newLength)) { + throwError(exec, createRangeError(exec, "Invalid array length.")); + return; + } + setLength(newLength); + return; + } + + JSObject::put(exec, propertyName, value, slot); +} + +void JSArray::put(ExecState* exec, unsigned i, JSValue value) +{ + checkConsistency(); + + ArrayStorage* storage = m_storage; + + unsigned length = storage->m_length; + if (i >= length && i <= MAX_ARRAY_INDEX) { + length = i + 1; + storage->m_length = length; + } + + if (i < m_vectorLength) { + JSValue& valueSlot = storage->m_vector[i]; + if (valueSlot) { + valueSlot = value; + checkConsistency(); + return; + } + valueSlot = value; + ++storage->m_numValuesInVector; + checkConsistency(); + return; + } + + putSlowCase(exec, i, value); +} + +NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value) +{ + 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<SparseArrayValueMap::iterator, bool> 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 = 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; + } + } + + void* baseStorage = storage->m_allocBase; + + if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) { + throwOutOfMemoryError(exec); + return; + } + + m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue)); + m_storage->m_allocBase = baseStorage; + storage = m_storage; + + unsigned vectorLength = m_vectorLength; + JSValue* vector = storage->m_vector; + + if (newNumValuesInVector == storage->m_numValuesInVector + 1) { + for (unsigned j = vectorLength; j < newVectorLength; ++j) + 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) + vector[j] = JSValue(); + for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) + vector[j] = map->take(j); + } + + ASSERT(i < newVectorLength); + + m_vectorLength = newVectorLength; + storage->m_numValuesInVector = newNumValuesInVector; + + storage->m_vector[i] = 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; + + return JSObject::deleteProperty(exec, propertyName); +} + +bool JSArray::deleteProperty(ExecState* exec, unsigned i) +{ + checkConsistency(); + + ArrayStorage* storage = m_storage; + + if (i < m_vectorLength) { + JSValue& valueSlot = storage->m_vector[i]; + if (!valueSlot) { + checkConsistency(); + return false; + } + valueSlot = JSValue(); + --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; + } + } + } + + checkConsistency(); + + if (i > MAX_ARRAY_INDEX) + return deleteProperty(exec, Identifier::from(exec, i)); + + 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. + + 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)); + } + + if (mode == IncludeDontEnumProperties) + propertyNames.add(exec->propertyNames().length); + + JSObject::getOwnPropertyNames(exec, propertyNames, mode); +} + +ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength) +{ + 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); + } + + ASSERT(increasedLength >= desiredLength); + + lastArraySize = min(increasedLength, FIRST_VECTOR_GROW); + + return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH); +} + +bool JSArray::increaseVectorLength(unsigned newLength) +{ + // 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; + + if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) + return false; + + storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue)); + m_storage->m_allocBase = baseStorage; + + JSValue* vector = storage->m_vector; + for (unsigned i = vectorLength; i < newVectorLength; ++i) + vector[i] = JSValue(); + + m_vectorLength = newVectorLength; + + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + + return true; +} + +bool JSArray::increaseVectorPrefixLength(unsigned newLength) +{ + // 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* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias)); + if (!newBaseStorage) + return false; + + m_indexBias += newVectorLength - newLength; + + m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(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)); + + m_storage->m_allocBase = newBaseStorage; + m_vectorLength = newLength; + + fastFree(storage->m_allocBase); + + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + + return true; +} + + +void JSArray::setLength(unsigned newLength) +{ + ArrayStorage* storage = m_storage; + +#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) { + JSValue& valueSlot = storage->m_vector[i]; + bool hadValue = valueSlot; + valueSlot = JSValue(); + 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); + } + if (map->isEmpty()) { + delete map; + storage->m_sparseValueMap = 0; + } + } + } + + storage->m_length = newLength; + + checkConsistency(); +} + +JSValue JSArray::pop() +{ + checkConsistency(); + + ArrayStorage* storage = m_storage; + + unsigned length = storage->m_length; + if (!length) + return jsUndefined(); + + --length; + + JSValue result; + + if (length < m_vectorLength) { + JSValue& valueSlot = storage->m_vector[length]; + if (valueSlot) { + --storage->m_numValuesInVector; + result = valueSlot; + valueSlot = JSValue(); + } 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; + map->remove(it); + if (map->isEmpty()) { + delete map; + storage->m_sparseValueMap = 0; + } + } + } + } + + storage->m_length = length; + + checkConsistency(); + + return result; +} + +void JSArray::push(ExecState* exec, JSValue value) +{ + checkConsistency(); + + ArrayStorage* storage = m_storage; + + if (storage->m_length < m_vectorLength) { + storage->m_vector[storage->m_length] = value; + ++storage->m_numValuesInVector; + ++storage->m_length; + checkConsistency(); + return; + } + + 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] = value; + ++storage->m_numValuesInVector; + ++storage->m_length; + checkConsistency(); + return; + } + checkConsistency(); + throwOutOfMemoryError(exec); + return; + } + } + + putSlowCase(exec, storage->m_length++, value); +} + +void JSArray::shiftCount(ExecState* exec, int 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. + + // 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); + + m_vectorLength -= count; + + if (m_vectorLength) { + char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue); + memmove(newBaseStorage, storage, storageSize(0)); + m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage); + + m_indexBias += count; + } + } +} + +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)); + } + } + } + + 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<char*>(storage) - count * sizeof(JSValue); + memmove(newBaseStorage, storage, storageSize(0)); + m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage); + m_vectorLength += count; + } else if (!increaseVectorPrefixLength(m_vectorLength + count)) { + throwOutOfMemoryError(exec); + return; + } + + JSValue* vector = m_storage->m_vector; + for (int i = 0; i < count; i++) + vector[i] = JSValue(); +} + +void JSArray::markChildren(MarkStack& markStack) +{ + markChildrenDirect(markStack); +} + +static int compareNumbersForQSort(const void* a, const void* b) +{ + double da = static_cast<const JSValue*>(a)->uncheckedGetNumber(); + double db = static_cast<const JSValue*>(b)->uncheckedGetNumber(); + return (da > db) - (da < db); +} + +static int compareByStringPairForQSort(const void* a, const void* b) +{ + const ValueStringPair* va = static_cast<const ValueStringPair*>(a); + const ValueStringPair* vb = static_cast<const ValueStringPair*>(b); + return codePointCompare(va->second, vb->second); +} + +void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +{ + ArrayStorage* storage = m_storage; + + unsigned lengthNotIncludingUndefined = compactForSorting(); + if (storage->m_sparseValueMap) { + 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; + } + } + + 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); +} + +void JSArray::sort(ExecState* exec) +{ + ArrayStorage* storage = m_storage; + + unsigned lengthNotIncludingUndefined = compactForSorting(); + if (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<ValueStringPair> values(lengthNotIncludingUndefined); + if (!values.begin()) { + throwOutOfMemoryError(exec); + return; + } + + Heap::heap(this)->pushTempSortVector(&values); + + for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { + JSValue value = storage->m_vector[i]; + ASSERT(!value.isUndefined()); + values[i].first = value; + } + + // 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()) + 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); +#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; + + for (size_t i = 0; i < lengthNotIncludingUndefined; i++) + storage->m_vector[i] = values[i].first; + + Heap::heap(this)->popTempSortVector(&values); + + checkConsistency(SortConsistencyCheck); +} + +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<AVLTreeNodeForArrayCompare> m_nodes; + ExecState* m_exec; + JSValue m_compareFunction; + CallType m_compareCallType; + const CallData* m_compareCallData; + JSValue m_globalThisValue; + OwnPtr<CachedCall> 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<unsigned>(m_nodes[h].lt) >> 31; + } + + void set_balance_factor(handle h, int bf) + { + if (bf == 0) { + m_nodes[h].lt &= 0x7FFFFFFF; + m_nodes[h].gt &= 0x7FFFFFFF; + } else { + m_nodes[h].lt |= 0x80000000; + if (bf < 0) + m_nodes[h].gt |= 0x80000000; + else + m_nodes[h].gt &= 0x7FFFFFFF; + } + } + + int compare_key_key(key va, key vb) + { + ASSERT(!va.isUndefined()); + ASSERT(!vb.isUndefined()); + + if (m_exec->hadException()) + return 1; + + 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)); + } 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); + } + return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. + } + + 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) +{ + checkConsistency(); + + ArrayStorage* storage = m_storage; + + // 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<unsigned>(std::numeric_limits<int>::max())); + if (storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max())) + return; + + unsigned usedVectorLength = min(storage->m_length, m_vectorLength); + unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0); + + if (!nodeCount) + return; + + AVLTree<AVLTreeAbstractorForArrayCompare, 44> 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)); + + 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]; + 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]; + if (v) { + if (v.isUndefined()) + ++numUndefined; + else { + tree.abstractor().m_nodes[numDefined].value = v; + tree.insert(numDefined); + ++numDefined; + } + } + } + + 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; + 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. + + // Copy the values back into m_storage. + AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter; + iter.start_iter_least(tree); + for (unsigned i = 0; i < numDefined; ++i) { + storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value; + ++iter; + } + + // Put undefined values back in. + for (unsigned i = numDefined; i < newUsedVectorLength; ++i) + storage->m_vector[i] = jsUndefined(); + + // Ensure that unused values in the vector are zeroed out. + for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) + storage->m_vector[i] = JSValue(); + + storage->m_numValuesInVector = newUsedVectorLength; + + checkConsistency(SortConsistencyCheck); +} + +void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) +{ + ArrayStorage* storage = m_storage; + + JSValue* vector = storage->m_vector; + unsigned vectorEnd = min(storage->m_length, m_vectorLength); + unsigned i = 0; + for (; i < vectorEnd; ++i) { + JSValue& v = vector[i]; + if (!v) + break; + args.append(v); + } + + for (; i < 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; + for (; i < vectorEnd; ++i) { + JSValue& v = vector[i]; + if (!v) + break; + buffer[i] = v; + } + + for (; i < maxSize; ++i) + buffer[i] = get(exec, i); +} + +unsigned JSArray::compactForSorting() +{ + checkConsistency(); + + ArrayStorage* storage = m_storage; + + unsigned usedVectorLength = min(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; + } + 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; + } + } + + 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; + } + + 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; + } + + 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) +{ + 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); + } + } + 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. + } + } +} + +#endif + +} // namespace JSC |