/*
* 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)
*
#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 <wtf/AVLTree.h>
#include <wtf/Assertions.h>
#include <wtf/OwnPtr.h>
-#include <Operations.h>
-
-#define CHECK_ARRAY_CONSISTENCY 0
using namespace std;
using namespace WTF;
namespace JSC {
-ASSERT_CLASS_FITS_IN_CELL(JSArray);
-
-// Overview of JSArray
-//
-// Properties of JSArray objects may be stored in one of three locations:
-// * The regular JSObject property map.
-// * A storage vector.
-// * A sparse map of array entries.
-//
-// Properties with non-numeric identifiers, with identifiers that are not representable
-// as an unsigned integer, or where the value is greater than MAX_ARRAY_INDEX
-// (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
-// integer) are not considered array indices and will be stored in the JSObject property map.
-//
-// All properties with a numeric identifer, representable as an unsigned integer i,
-// where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
-// storage vector or the sparse map. An array index i will be handled in the following
-// fashion:
-//
-// * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
-// * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
-// be stored in the storage vector or in the sparse array, depending on the density of
-// data that would be stored in the vector (a vector being used where at least
-// (1 / minDensityMultiplier) of the entries would be populated).
-// * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
-// in the sparse array.
-
-// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
-// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
-// size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(JSValue)) +
-// (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
-#define MAX_STORAGE_VECTOR_LENGTH static_cast<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
-
-// Our policy for when to use a vector and when to use a sparse map.
-// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
-// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
-// as long as it is 1/8 full. If more sparse than that, we use a map.
-static const unsigned minDensityMultiplier = 8;
-
-const ClassInfo JSArray::info = {"Array", 0, 0, 0};
-
-static inline size_t storageSize(unsigned vectorLength)
-{
- ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
+STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray);
- // 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))));
+const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
- return size;
+Butterfly* createArrayButterflyInDictionaryIndexingMode(
+ VM& vm, JSCell* intendedOwner, unsigned initialLength)
+{
+ 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;
}
-static inline unsigned increasedVectorLength(unsigned newLength)
+void JSArray::setLengthWritable(ExecState* exec, bool writable)
{
- ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);
+ ASSERT(isLengthWritable() || !writable);
+ if (!isLengthWritable() || writable)
+ return;
- // Mathematically equivalent to:
- // increasedLength = (newLength * 3 + 1) / 2;
- // or:
- // increasedLength = (unsigned)ceil(newLength * 1.5));
- // This form is not prone to internal overflow.
- unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1);
- ASSERT(increasedLength >= newLength);
+ enterDictionaryIndexingMode(exec->vm());
- return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
+ SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
+ ASSERT(map);
+ map->setLengthIsReadOnly();
}
-static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
+// Defined in ES5.1 15.4.5.1
+bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)
{
- return length / minDensityMultiplier <= numValues;
-}
+ JSArray* array = jsCast<JSArray*>(object);
-#if !CHECK_ARRAY_CONSISTENCY
+ // 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;
+ }
+
+ // 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;
+ }
-inline void JSArray::checkConsistency(ConsistencyCheckType)
-{
-}
+ // 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;
+ }
-#endif
+ // 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;
+ }
-JSArray::JSArray(NonNullPassRefPtr<Structure> structure)
- : JSObject(structure)
-{
- unsigned initialCapacity = 0;
+ // 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;
+ }
- m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
- m_vectorLength = initialCapacity;
+ // 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);
+ }
- checkConsistency();
+ return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
}
-JSArray::JSArray(NonNullPassRefPtr<Structure> structure, unsigned initialLength)
- : JSObject(structure)
+bool JSArray::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
{
- unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
+ JSArray* thisObject = jsCast<JSArray*>(object);
+ if (propertyName == exec->propertyNames().length) {
+ unsigned attributes = thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly;
+ slot.setValue(thisObject, attributes, jsNumber(thisObject->length()));
+ return true;
+ }
- m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
- m_storage->m_length = initialLength;
- m_vectorLength = initialCapacity;
- m_storage->m_numValuesInVector = 0;
- m_storage->m_sparseValueMap = 0;
- m_storage->lazyCreationData = 0;
- m_storage->reportedMapCapacity = 0;
+ return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
+}
- JSValue* vector = m_storage->m_vector;
- for (size_t i = 0; i < initialCapacity; ++i)
- vector[i] = JSValue();
+// ECMA 15.4.5.1
+void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
+{
+ JSArray* thisObject = jsCast<JSArray*>(cell);
- checkConsistency();
+ if (propertyName == exec->propertyNames().length) {
+ unsigned newLength = value.toUInt32(exec);
+ if (value.toNumber(exec) != static_cast<double>(newLength)) {
+ exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
+ return;
+ }
+ thisObject->setLength(exec, newLength, slot.isStrictMode());
+ return;
+ }
- Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));
+ JSObject::put(thisObject, exec, propertyName, value, slot);
}
-JSArray::JSArray(NonNullPassRefPtr<Structure> structure, const ArgList& list)
- : JSObject(structure)
+bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
{
- unsigned initialCapacity = list.size();
+ JSArray* thisObject = jsCast<JSArray*>(cell);
- m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
- m_storage->m_length = initialCapacity;
- m_vectorLength = initialCapacity;
- m_storage->m_numValuesInVector = initialCapacity;
- m_storage->m_sparseValueMap = 0;
- m_storage->lazyCreationData = 0;
- m_storage->reportedMapCapacity = 0;
-
- size_t i = 0;
- ArgList::const_iterator end = list.end();
- for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
- m_storage->m_vector[i] = *it;
+ if (propertyName == exec->propertyNames().length)
+ return false;
- checkConsistency();
+ return JSObject::deleteProperty(thisObject, exec, propertyName);
+}
- Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
+static int compareKeysForQSort(const void* a, const void* b)
+{
+ unsigned da = *static_cast<const unsigned*>(a);
+ unsigned db = *static_cast<const unsigned*>(b);
+ return (da > db) - (da < db);
}
-JSArray::~JSArray()
+void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
{
- ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
- checkConsistency(DestructorConsistencyCheck);
+ JSArray* thisObject = jsCast<JSArray*>(object);
+
+ if (mode == IncludeDontEnumProperties)
+ propertyNames.add(exec->propertyNames().length);
- delete m_storage->m_sparseValueMap;
- fastFree(m_storage);
+ JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
}
-bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
+// 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 = m_storage;
-
- if (i >= storage->m_length) {
- if (i > MAX_ARRAY_INDEX)
- return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
+ 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;
}
- 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;
- }
- }
+ // 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);
}
- return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
-}
+ unsigned newVectorLength = requiredVectorLength + postCapacity;
+ unsigned newIndexBias = newStorageCapacity - newVectorLength;
-bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
-{
- if (propertyName == exec->propertyNames().length) {
- slot.setValue(jsNumber(exec, length()));
- return true;
+ Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
+
+ 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);
+
+ WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector;
+ for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
+ newVector[i].clear();
}
- bool isArrayIndex;
- unsigned i = propertyName.toArrayIndex(&isArrayIndex);
- if (isArrayIndex)
- return JSArray::getOwnPropertySlot(exec, i, slot);
+ newButterfly->arrayStorage()->setVectorLength(newVectorLength);
+ newButterfly->arrayStorage()->m_indexBias = newIndexBias;
+ setButterflyWithoutChangingStructure(vm, newButterfly);
- return JSObject::getOwnPropertySlot(exec, propertyName, slot);
+ return true;
}
-bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
+bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
{
- if (propertyName == exec->propertyNames().length) {
- descriptor.setDescriptor(jsNumber(exec, length()), DontDelete | DontEnum);
- return true;
- }
-
- bool isArrayIndex;
- unsigned i = propertyName.toArrayIndex(&isArrayIndex);
- if (isArrayIndex) {
- if (i >= m_storage->m_length)
- return false;
- if (i < m_vectorLength) {
- JSValue& value = m_storage->m_vector[i];
- if (value) {
- descriptor.setDescriptor(value, 0);
- return true;
+ 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<unsigned, 0, UnsafeVectorOverflow> keys;
+ keys.reserveInitialCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
+ SparseArrayValueMap::const_iterator end = map->end();
+ for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
+ unsigned index = static_cast<unsigned>(it->key);
+ if (index < length && index >= newLength)
+ keys.append(index);
}
- } else if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
- if (i >= MIN_SPARSE_ARRAY_INDEX) {
- SparseArrayValueMap::iterator it = map->find(i);
- if (it != map->end()) {
- descriptor.setDescriptor(it->second, 0);
- return true;
+
+ // 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();
}
}
}
- 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, RangeError, "Invalid array length.");
- return;
+ if (newLength < length) {
+ // Delete properties from the vector.
+ unsigned usedVectorLength = min(length, storage->vectorLength());
+ for (unsigned i = newLength; i < usedVectorLength; ++i) {
+ WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
+ bool hadValue = valueSlot;
+ valueSlot.clear();
+ storage->m_numValuesInVector -= hadValue;
}
- setLength(newLength);
- return;
}
- JSObject::put(exec, propertyName, value, slot);
+ storage->setLength(newLength);
+
+ return true;
}
-void JSArray::put(ExecState* exec, unsigned i, JSValue value)
+bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
{
- checkConsistency();
-
- unsigned length = m_storage->m_length;
- if (i >= length && i <= MAX_ARRAY_INDEX) {
- length = i + 1;
- m_storage->m_length = length;
+ switch (indexingType()) {
+ case ArrayClass:
+ if (!newLength)
+ return true;
+ if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
+ return setLengthWithArrayStorage(
+ exec, newLength, throwException,
+ convertContiguousToArrayStorage(exec->vm()));
+ }
+ createInitialUndecided(exec->vm(), newLength);
+ return true;
+
+ case ArrayWithUndecided:
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ case ArrayWithContiguous:
+ if (newLength == m_butterfly->publicLength())
+ return true;
+ if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
+ || (newLength >= MIN_SPARSE_ARRAY_INDEX
+ && !isDenseEnoughForVector(newLength, countElements()))) {
+ return setLengthWithArrayStorage(
+ exec, newLength, throwException,
+ ensureArrayStorage(exec->vm()));
+ }
+ if (newLength > m_butterfly->publicLength()) {
+ ensureLength(exec->vm(), newLength);
+ return true;
+ }
+ if (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 (i < m_vectorLength) {
- JSValue& valueSlot = m_storage->m_vector[i];
- if (valueSlot) {
- valueSlot = value;
- checkConsistency();
- return;
+JSValue JSArray::pop(ExecState* exec)
+{
+ 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;
}
- valueSlot = value;
- ++m_storage->m_numValuesInVector;
- checkConsistency();
- return;
+ 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();
+ }
- putSlowCase(exec, i, value);
+ unsigned index = length - 1;
+ if (index < storage->vectorLength()) {
+ WriteBarrier<Unknown>& 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;
}
-NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
+// 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)
{
- 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);
+ 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;
}
- // 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;
- }
+ 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<Int32Shape>(exec, length, value);
+ 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);
+ 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<ContiguousShape>(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;
+ }
- // Decide how many values it would be best to move from the map.
- unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
- unsigned newVectorLength = increasedVectorLength(i + 1);
- for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
- newNumValuesInVector += map->contains(j);
- if (i >= MIN_SPARSE_ARRAY_INDEX)
- newNumValuesInVector -= map->contains(i);
- if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
- unsigned proposedNewNumValuesInVector = newNumValuesInVector;
- // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
- while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {
- unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
- for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
- proposedNewNumValuesInVector += map->contains(j);
- if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
- break;
- newVectorLength = proposedNewVectorLength;
- newNumValuesInVector = proposedNewNumValuesInVector;
+ 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<DoubleShape>(exec, length, value);
+ break;
}
-
- if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) {
- throwOutOfMemoryError(exec);
- return;
+
+ 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;
+ }
- unsigned vectorLength = m_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;
+ }
- if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
- for (unsigned j = vectorLength; j < newVectorLength; ++j)
- storage->m_vector[j] = JSValue();
- if (i > MIN_SPARSE_ARRAY_INDEX)
- map->remove(i);
- } else {
- for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
- storage->m_vector[j] = JSValue();
- for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
- storage->m_vector[j] = map->take(j);
+ // Handled the same as putIndex.
+ putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
+ break;
+ }
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
}
-
- storage->m_vector[i] = value;
-
- m_vectorLength = newVectorLength;
- storage->m_numValuesInVector = newNumValuesInVector;
-
- m_storage = storage;
-
- checkConsistency();
-
- Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
}
-bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
+bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage)
{
- bool isArrayIndex;
- unsigned i = propertyName.toArrayIndex(&isArrayIndex);
- if (isArrayIndex)
- return deleteProperty(exec, i);
-
- if (propertyName == exec->propertyNames().length)
+ unsigned oldLength = storage->length();
+ RELEASE_ASSERT(count <= oldLength);
+
+ // If the array contains holes or is otherwise in an abnormal state,
+ // use the generic algorithm in ArrayPrototype.
+ if ((storage->hasHoles() && this->structure(vm)->holesMustForwardToPrototype(vm))
+ || inSparseIndexingMode()
+ || shouldUseSlowPut(indexingType())) {
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;
+ if (!oldLength)
+ return true;
+
+ unsigned length = oldLength - count;
+
+ storage->m_numValuesInVector -= count;
+ storage->setLength(length);
+
+ unsigned vectorLength = storage->vectorLength();
+ if (!vectorLength)
+ return true;
+
+ if (startIndex >= vectorLength)
+ return true;
+
+ if (startIndex + count > vectorLength)
+ count = vectorLength - startIndex;
+
+ unsigned usedVectorLength = min(vectorLength, oldLength);
+
+ unsigned numElementsBeforeShiftRegion = startIndex;
+ unsigned firstIndexAfterShiftRegion = startIndex + count;
+ unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
+ ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
+
+ // The point of this comparison seems to be to minimize the amount of elements that have to
+ // be moved during a shift operation.
+ if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
+ // The number of elements before the shift region is less than the number of elements
+ // after the shift region, so we move the elements before to the right.
+ if (numElementsBeforeShiftRegion) {
+ RELEASE_ASSERT(count + startIndex <= vectorLength);
+ if (storage->hasHoles()) {
+ for (unsigned i = startIndex; i-- > 0;) {
+ unsigned destinationIndex = count + i;
+ JSValue source = storage->m_vector[i].get();
+ JSValue dest = storage->m_vector[destinationIndex].get();
+ // Any time we overwrite a hole we know we overcounted the number of values we removed
+ // when we subtracted count from m_numValuesInVector above.
+ if (!dest && destinationIndex >= firstIndexAfterShiftRegion)
+ storage->m_numValuesInVector++;
+ storage->m_vector[count + i].setWithoutWriteBarrier(source);
+ }
+ } else {
+ memmove(storage->m_vector + count,
+ storage->m_vector,
+ sizeof(JSValue) * startIndex);
}
}
+ // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
+ // the start of the Butterfly, which needs to point at the first indexed property in the used
+ // portion of the vector.
+ m_butterfly.setWithoutWriteBarrier(m_butterfly->shift(structure(), count));
+ storage = m_butterfly->arrayStorage();
+ storage->m_indexBias += count;
+
+ // Since we're consuming part of the vector by moving its beginning to the left,
+ // we need to modify the vector length appropriately.
+ storage->setVectorLength(vectorLength - count);
+ } else {
+ // The number of elements before the shift region is greater than or equal to the number
+ // of elements after the shift region, so we move the elements after the shift region to the left.
+ if (storage->hasHoles()) {
+ for (unsigned i = 0; i < numElementsAfterShiftRegion; ++i) {
+ unsigned destinationIndex = startIndex + i;
+ JSValue source = storage->m_vector[firstIndexAfterShiftRegion + i].get();
+ JSValue dest = storage->m_vector[destinationIndex].get();
+ // Any time we overwrite a hole we know we overcounted the number of values we removed
+ // when we subtracted count from m_numValuesInVector above.
+ if (!dest && destinationIndex < firstIndexAfterShiftRegion)
+ storage->m_numValuesInVector++;
+ storage->m_vector[startIndex + i].setWithoutWriteBarrier(source);
+ }
+ } else {
+ 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.
}
-
- checkConsistency();
-
- if (i > MAX_ARRAY_INDEX)
- return deleteProperty(exec, Identifier::from(exec, i));
-
- return false;
+
+ return true;
}
-void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count)
{
- // 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;
+ VM& vm = exec->vm();
+ RELEASE_ASSERT(count > 0);
+
+ switch (indexingType()) {
+ case ArrayClass:
+ return true;
+
+ case ArrayWithUndecided:
+ // Don't handle this because it's confusing and it shouldn't come up.
+ return false;
+
+ case ArrayWithInt32:
+ case ArrayWithContiguous: {
+ unsigned oldLength = m_butterfly->publicLength();
+ RELEASE_ASSERT(count <= oldLength);
+
+ // We may have to walk the entire array to do the shift. We're willing to do
+ // so only if it's not horribly slow.
+ if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
+ return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
+
+ // Storing to a hole is fine since we're still having a good time. But reading from a hole
+ // is totally not fine, since we might have to read from the proto chain.
+ // We have to check for holes before we start moving things around so that we don't get halfway
+ // through shifting and then realize we should have been in ArrayStorage mode.
+ unsigned end = oldLength - count;
+ if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
+ for (unsigned i = startIndex; i < end; ++i) {
+ JSValue v = m_butterfly->contiguous()[i + count].get();
+ if (UNLIKELY(!v)) {
+ startIndex = i;
+ return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
+ }
+ m_butterfly->contiguous()[i].setWithoutWriteBarrier(v);
+ }
+ } else {
+ memmove(m_butterfly->contiguous().data() + startIndex,
+ m_butterfly->contiguous().data() + startIndex + count,
+ sizeof(JSValue) * (end - startIndex));
+ }
- 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));
+ for (unsigned i = end; i < oldLength; ++i)
+ m_butterfly->contiguous()[i].clear();
+
+ m_butterfly->setPublicLength(oldLength - count);
+ return true;
}
-
- 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));
+
+ 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;
}
-
- if (mode == IncludeDontEnumProperties)
- propertyNames.add(exec->propertyNames().length);
-
- JSObject::getOwnPropertyNames(exec, propertyNames, mode);
}
-bool JSArray::increaseVectorLength(unsigned newLength)
+// Returns true if the unshift can be handled, false to fallback.
+bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, 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.
+ unsigned length = storage->length();
- ArrayStorage* storage = m_storage;
+ RELEASE_ASSERT(startIndex <= length);
- unsigned vectorLength = m_vectorLength;
- ASSERT(newLength > vectorLength);
- ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
- unsigned newVectorLength = increasedVectorLength(newLength);
-
- if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage))
+ // 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;
- m_vectorLength = newVectorLength;
-
- for (unsigned i = vectorLength; i < newVectorLength; ++i)
- storage->m_vector[i] = JSValue();
+ bool moveFront = !startIndex || startIndex < length / 2;
+
+ unsigned vectorLength = storage->vectorLength();
+
+ if (moveFront && storage->m_indexBias >= count) {
+ Butterfly* newButterfly = storage->butterfly()->unshift(structure(), count);
+ storage = newButterfly->arrayStorage();
+ storage->m_indexBias -= count;
+ storage->setVectorLength(vectorLength + count);
+ setButterflyWithoutChangingStructure(exec->vm(), newButterfly);
+ } else if (!moveFront && vectorLength - length >= count)
+ storage = storage->butterfly()->arrayStorage();
+ else if (unshiftCountSlowCase(exec->vm(), moveFront, count))
+ storage = arrayStorage();
+ else {
+ throwOutOfMemoryError(exec);
+ return true;
+ }
- m_storage = storage;
+ WriteBarrier<Unknown>* vector = storage->m_vector;
- Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
+ 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));
+ }
+ for (unsigned i = 0; i < count; i++)
+ vector[i + startIndex].clear();
return true;
}
-void JSArray::setLength(unsigned newLength)
+bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
{
- checkConsistency();
-
- ArrayStorage* storage = m_storage;
-
- unsigned length = m_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;
- }
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ // We could handle this. But it shouldn't ever come up, so we won't.
+ return false;
- 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;
- }
+ case ArrayWithInt32:
+ case ArrayWithContiguous: {
+ unsigned oldLength = m_butterfly->publicLength();
+
+ // We may have to walk the entire array to do the unshift. We're willing to do so
+ // only if it's not horribly slow.
+ if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
+ return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
+
+ ensureLength(exec->vm(), oldLength + count);
+
+ // We have to check for holes before we start moving things around so that we don't get halfway
+ // through shifting and then realize we should have been in ArrayStorage mode.
+ for (unsigned i = oldLength; i-- > startIndex;) {
+ JSValue v = m_butterfly->contiguous()[i].get();
+ if (UNLIKELY(!v))
+ return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
}
- }
-
- m_storage->m_length = newLength;
-
- checkConsistency();
-}
-
-JSValue JSArray::pop()
-{
- checkConsistency();
-
- unsigned length = m_storage->m_length;
- if (!length)
- return jsUndefined();
- --length;
-
- JSValue result;
-
- if (length < m_vectorLength) {
- JSValue& valueSlot = m_storage->m_vector[length];
- if (valueSlot) {
- --m_storage->m_numValuesInVector;
- result = valueSlot;
- valueSlot = JSValue();
- } else
- result = jsUndefined();
- } else {
- result = jsUndefined();
- if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
- SparseArrayValueMap::iterator it = map->find(length);
- if (it != map->end()) {
- result = it->second;
- map->remove(it);
- if (map->isEmpty()) {
- delete map;
- m_storage->m_sparseValueMap = 0;
- }
- }
+ for (unsigned i = oldLength; i-- > startIndex;) {
+ JSValue v = m_butterfly->contiguous()[i].get();
+ ASSERT(v);
+ m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
}
+
+ // NOTE: we're leaving being garbage in the part of the array that we shifted out
+ // of. This is fine because the caller is required to store over that area, and
+ // in contiguous mode storing into a hole is guaranteed to behave exactly the same
+ // as storing over an existing element.
+
+ return true;
}
+
+ case ArrayWithDouble: {
+ unsigned oldLength = m_butterfly->publicLength();
+
+ // We may have to walk the entire array to do the unshift. We're willing to do so
+ // only if it's not horribly slow.
+ if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
+ return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
+
+ ensureLength(exec->vm(), oldLength + count);
+
+ // We have to check for holes before we start moving things around so that we don't get halfway
+ // through shifting and then realize we should have been in ArrayStorage mode.
+ for (unsigned i = oldLength; i-- > startIndex;) {
+ double v = m_butterfly->contiguousDouble()[i];
+ if (UNLIKELY(v != v))
+ return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
+ }
- m_storage->m_length = length;
-
- checkConsistency();
-
- return result;
-}
-
-void JSArray::push(ExecState* exec, JSValue value)
-{
- checkConsistency();
-
- if (m_storage->m_length < m_vectorLength) {
- m_storage->m_vector[m_storage->m_length] = value;
- ++m_storage->m_numValuesInVector;
- ++m_storage->m_length;
- checkConsistency();
- return;
- }
-
- if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
- SparseArrayValueMap* map = m_storage->m_sparseValueMap;
- if (!map || map->isEmpty()) {
- if (increaseVectorLength(m_storage->m_length + 1)) {
- m_storage->m_vector[m_storage->m_length] = value;
- ++m_storage->m_numValuesInVector;
- ++m_storage->m_length;
- checkConsistency();
- return;
- }
- checkConsistency();
- throwOutOfMemoryError(exec);
- return;
+ for (unsigned i = oldLength; i-- > startIndex;) {
+ double v = m_butterfly->contiguousDouble()[i];
+ ASSERT(v == v);
+ m_butterfly->contiguousDouble()[i + count] = v;
}
+
+ // NOTE: we're leaving being garbage in the part of the array that we shifted out
+ // of. This is fine because the caller is required to store over that area, and
+ // in contiguous mode storing into a hole is guaranteed to behave exactly the same
+ // as storing over an existing element.
+
+ return true;
+ }
+
+ case ArrayWithArrayStorage:
+ case ArrayWithSlowPutArrayStorage:
+ return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
+
+ default:
+ CRASH();
+ return false;
}
+}
- putSlowCase(exec, m_storage->m_length++, value);
+static int compareNumbersForQSortWithInt32(const void* a, const void* b)
+{
+ int32_t ia = static_cast<const JSValue*>(a)->asInt32();
+ int32_t ib = static_cast<const JSValue*>(b)->asInt32();
+ return ia - ib;
}
-void JSArray::markChildren(MarkStack& markStack)
+static int compareNumbersForQSortWithDouble(const void* a, const void* b)
{
- markChildrenDirect(markStack);
+ double da = *static_cast<const double*>(a);
+ double db = *static_cast<const double*>(b);
+ return (da > db) - (da < db);
}
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();
+ double da = static_cast<const JSValue*>(a)->asNumber();
+ double db = static_cast<const JSValue*>(b)->asNumber();
return (da > db) - (da < db);
}
-typedef std::pair<JSValue, UString> ValueStringPair;
-
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 compare(va->second, vb->second);
+ return codePointCompare(va->second, vb->second);
}
-void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+template<IndexingType arrayIndexingType>
+void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
{
- unsigned lengthNotIncludingUndefined = compactForSorting();
- if (m_storage->m_sparseValueMap) {
+ ASSERT(arrayIndexingType == ArrayWithInt32 || arrayIndexingType == ArrayWithDouble || arrayIndexingType == ArrayWithContiguous || arrayIndexingType == ArrayWithArrayStorage);
+
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<arrayIndexingType>(
+ lengthNotIncludingUndefined,
+ newRelevantLength);
+
+ ContiguousJSValues data = indexingData<arrayIndexingType>();
+
+ if (arrayIndexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
throwOutOfMemoryError(exec);
return;
}
-
+
if (!lengthNotIncludingUndefined)
return;
-
+
bool allValuesAreNumbers = true;
- size_t size = m_storage->m_numValuesInVector;
- for (size_t i = 0; i < size; ++i) {
- if (!m_storage->m_vector[i].isNumber()) {
- allValuesAreNumbers = false;
- break;
+ 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(m_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<Unknown>) == sizeof(double));
+ break;
+
+ default:
+ compare = compareNumbersForQSort;
+ break;
+ }
+ ASSERT(data.length() >= newRelevantLength);
+ qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
+ return;
}
-void JSArray::sort(ExecState* exec)
+void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
{
- unsigned lengthNotIncludingUndefined = compactForSorting();
- if (m_storage->m_sparseValueMap) {
- throwOutOfMemoryError(exec);
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ return;
+
+ case ArrayWithInt32:
+ sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
+ break;
+
+ case ArrayWithDouble:
+ sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+ break;
+
+ case ArrayWithContiguous:
+ sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithArrayStorage:
+ sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+ return;
+
+ default:
+ CRASH();
return;
}
+}
- if (!lengthNotIncludingUndefined)
+template <IndexingType> struct ContiguousTypeAccessor {
+ typedef WriteBarrier<Unknown> Type;
+ static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); }
+ static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value)
+ {
+ data[i].set(vm, thisValue, value);
+ }
+ static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData)
+ {
+ *outData = inData;
+ }
+};
+
+template <> struct ContiguousTypeAccessor<ArrayWithDouble> {
+ typedef double Type;
+ static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); }
+ static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value)
+ {
+ data[i] = value.asNumber();
+ }
+ static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues)
+ {
+ RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort.");
+ }
+};
+
+
+template<IndexingType arrayIndexingType, typename StorageType>
+void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> 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<ValueStringPair> values(lengthNotIncludingUndefined);
+
+ Vector<ValueStringPair, 0, UnsafeVectorOverflow> 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 = m_storage->m_vector[i];
+ for (size_t i = 0; i < relevantLength; i++) {
+ JSValue value = ContiguousTypeAccessor<arrayIndexingType>::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: While calling these toString functions, the array could be mutated.
- // In that case, objects pointed to by values in this vector might get garbage-collected!
-
+
// 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())
+
+ 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.
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ case ArrayWithContiguous:
+ ensureLength(vm, relevantLength);
+ break;
+
+ case ArrayWithArrayStorage:
+ if (arrayStorage()->vectorLength() < relevantLength) {
+ increaseVectorLength(exec->vm(), relevantLength);
+ ContiguousTypeAccessor<arrayIndexingType>::replaceDataReference(&data, arrayStorage()->vector());
+ }
+ if (arrayStorage()->length() < relevantLength)
+ arrayStorage()->setLength(relevantLength);
+ break;
+
+ default:
+ CRASH();
+ }
- // FIXME: If the toString function changed the length of the array, this might be
- // modifying the vector incorrectly.
-
- for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
- m_storage->m_vector[i] = values[i].first;
+ for (size_t i = 0; i < relevantLength; i++)
+ ContiguousTypeAccessor<arrayIndexingType>::setWithValue(vm, this, data, i, values[i].first);
+
+ Heap::heap(this)->popTempSortVector(&values);
+}
- checkConsistency(SortConsistencyCheck);
+void JSArray::sort(ExecState* exec)
+{
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ return;
+
+ case ArrayWithInt32: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithInt32>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithInt32>(
+ exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithDouble: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithDouble>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithDouble>(
+ exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithContiguous: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithContiguous>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithContiguous>(
+ exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithArrayStorage: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithArrayStorage>(
+ lengthNotIncludingUndefined, newRelevantLength);
+ ArrayStorage* storage = m_butterfly->arrayStorage();
+ ASSERT(!storage->m_sparseMap);
+
+ sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
}
struct AVLTreeNodeForArrayCompare {
typedef JSValue key;
typedef int32_t size;
- Vector<AVLTreeNodeForArrayCompare> m_nodes;
+ Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> 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; }
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.
}
static handle null() { return 0x7FFFFFFF; }
};
-void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+template<IndexingType arrayIndexingType>
+void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
{
- checkConsistency();
-
+ 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(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
- if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
+ ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+ if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
return;
-
- if (!m_storage->m_length)
+
+ unsigned usedVectorLength = relevantLength<arrayIndexingType>();
+ unsigned nodeCount = usedVectorLength;
+
+ if (!nodeCount)
return;
-
- unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
-
+
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.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
-
+ tree.abstractor().m_nodes.grow(nodeCount);
+
if (callType == CallTypeJS)
- tree.abstractor().m_cachedCall.set(new CachedCall(exec, asFunction(compareFunction), 2, exec->exceptionSlot()));
-
+ tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(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 = m_storage->m_vector[numDefined];
+ 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 = m_storage->m_vector[i];
+ if (i >= m_butterfly->vectorLength())
+ break;
+ JSValue v = getHolyIndexQuickly(i);
if (v) {
if (v.isUndefined())
++numUndefined;
}
}
}
-
+
unsigned newUsedVectorLength = numDefined + numUndefined;
-
- if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
- newUsedVectorLength += map->size();
- if (newUsedVectorLength > m_vectorLength) {
- // Check that it is possible to allocate an array large enough to hold all the entries.
- if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
- throwOutOfMemoryError(exec);
- return;
- }
- }
-
- 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;
- m_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<unsigned>(tree.abstractor().m_nodes.size()));
+ unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
+ unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
+
// Copy the values back into m_storage.
AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
iter.start_iter_least(tree);
- for (unsigned i = 0; i < numDefined; ++i) {
- m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
+ 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)
- m_storage->m_vector[i] = jsUndefined();
+ 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)
- m_storage->m_vector[i] = JSValue();
+ 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;
+}
- m_storage->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<ArrayWithInt32>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithDouble:
+ sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+ return;
- checkConsistency(SortConsistencyCheck);
+ case ArrayWithContiguous:
+ sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithArrayStorage:
+ sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+ return;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
}
void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
{
- JSValue* vector = m_storage->m_vector;
- unsigned vectorEnd = min(m_storage->m_length, m_vectorLength);
unsigned i = 0;
+ unsigned vectorEnd;
+ WriteBarrier<Unknown>* 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) {
- JSValue& v = vector[i];
+ WriteBarrier<Unknown>& v = vector[i];
if (!v)
break;
- args.append(v);
+ args.append(v.get());
}
-
- for (; i < m_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);
- JSValue* vector = m_storage->m_vector;
- unsigned vectorEnd = min(m_storage->m_length, m_vectorLength);
- unsigned i = 0;
+ unsigned i = firstVarArgOffset;
+ WriteBarrier<Unknown>* 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) {
- JSValue& v = vector[i];
+ WriteBarrier<Unknown>& v = vector[i];
if (!v)
break;
- buffer[i] = v;
+ callFrame->setArgument(i - firstVarArgOffset, v.get());
}
-
- for (; i < m_storage->m_length; ++i)
- buffer[i] = get(exec, i);
+
+ for (; i < length; ++i)
+ callFrame->setArgument(i - firstVarArgOffset, get(exec, i));
}
-unsigned JSArray::compactForSorting()
+template<IndexingType arrayIndexingType>
+void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
{
- checkConsistency();
+ ASSERT(!inSparseIndexingMode());
+ ASSERT(arrayIndexingType == indexingType());
- ArrayStorage* storage = m_storage;
-
- unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
-
- unsigned numDefined = 0;
+ unsigned myRelevantLength = relevantLength<arrayIndexingType>();
+
+ numDefined = 0;
unsigned numUndefined = 0;
-
- for (; numDefined < usedVectorLength; ++numDefined) {
- JSValue v = storage->m_vector[numDefined];
+
+ 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<arrayIndexingType>()[numDefined].get();
if (!v || v.isUndefined())
break;
}
- for (unsigned i = numDefined; i < usedVectorLength; ++i) {
- JSValue v = storage->m_vector[i];
+
+ 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<arrayIndexingType>()[i].get();
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;
+ else {
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ indexingData<arrayIndexingType>()[numDefined++].setWithoutWriteBarrier(v);
+ }
}
-
- SparseArrayValueMap::iterator end = map->end();
- for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
- storage->m_vector[numDefined++] = it->second;
-
- delete map;
- storage->m_sparseValueMap = 0;
}
-
- 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::lazyCreationData()
-{
- return m_storage->lazyCreationData;
-}
-
-void JSArray::setLazyCreationData(void* d)
-{
- m_storage->lazyCreationData = d;
-}
-
-#if CHECK_ARRAY_CONSISTENCY
-
-void JSArray::checkConsistency(ConsistencyCheckType type)
-{
- ASSERT(m_storage);
- if (type == SortConsistencyCheck)
- ASSERT(!m_storage->m_sparseValueMap);
-
- unsigned numValuesInVector = 0;
- for (unsigned i = 0; i < m_vectorLength; ++i) {
- if (JSValue value = m_storage->m_vector[i]) {
- ASSERT(i < m_storage->m_length);
- if (type != DestructorConsistencyCheck)
- value->type(); // Likely to crash if the object was deallocated.
- ++numValuesInVector;
- } else {
- if (type == SortConsistencyCheck)
- ASSERT(i >= m_storage->m_numValuesInVector);
+
+ 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<arrayIndexingType>()[i].setUndefined();
}
+ break;
}
- ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
- ASSERT(numValuesInVector <= m_storage->m_length);
-
- if (m_storage->m_sparseValueMap) {
- SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
- for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
- unsigned index = it->first;
- ASSERT(index < m_storage->m_length);
- ASSERT(index >= m_vectorLength);
- ASSERT(index <= MAX_ARRAY_INDEX);
- ASSERT(it->second);
- if (type != DestructorConsistencyCheck)
- it->second->type(); // Likely to crash if the object was deallocated.
- }
+ for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
+ ASSERT(i < m_butterfly->vectorLength());
+ if (arrayIndexingType == ArrayWithDouble)
+ m_butterfly->contiguousDouble()[i] = PNaN;
+ else
+ indexingData<arrayIndexingType>()[i].clear();
}
-}
-#endif
+ if (hasAnyArrayStorage(arrayIndexingType))
+ arrayStorage()->m_numValuesInVector = newRelevantLength;
+}
} // namespace JSC
projects / apple / javascriptcore.git / blobdiff