From db14019a23d96bc8a444b6576a5da8bd1cfbc8b0 Mon Sep 17 00:00:00 2001 From: Steve Block Date: Wed, 4 Aug 2010 11:41:34 +0100 Subject: Merge WebKit at r64523 : Initial merge by git. Change-Id: Ibb796c6802e757b1d9b40f58205cfbe4da95fcd4 --- JavaScriptCore/runtime/ArrayPrototype.cpp | 64 ++-- JavaScriptCore/runtime/Collector.h | 12 +- JavaScriptCore/runtime/JSArray.cpp | 484 +++++++++++++++++++++--------- JavaScriptCore/runtime/JSArray.h | 54 +++- 4 files changed, 420 insertions(+), 194 deletions(-) (limited to 'JavaScriptCore/runtime') diff --git a/JavaScriptCore/runtime/ArrayPrototype.cpp b/JavaScriptCore/runtime/ArrayPrototype.cpp index e79c46d..fa6eb99 100644 --- a/JavaScriptCore/runtime/ArrayPrototype.cpp +++ b/JavaScriptCore/runtime/ArrayPrototype.cpp @@ -424,13 +424,17 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec) result = jsUndefined(); } else { result = thisObj->get(exec, 0); - for (unsigned k = 1; k < length; k++) { - if (JSValue obj = getProperty(exec, thisObj, k)) - thisObj->put(exec, k - 1, obj); - else - thisObj->deleteProperty(exec, k - 1); + if (isJSArray(&exec->globalData(), thisObj)) + ((JSArray *)thisObj)->shiftCount(exec, 1); + else { + for (unsigned k = 1; k < length; k++) { + if (JSValue obj = getProperty(exec, thisObj, k)) + thisObj->put(exec, k - 1, obj); + else + thisObj->deleteProperty(exec, k - 1); + } + thisObj->deleteProperty(exec, length - 1); } - thisObj->deleteProperty(exec, length - 1); putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length - 1)); } return JSValue::encode(result); @@ -578,20 +582,28 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec) unsigned additionalArgs = std::max(exec->argumentCount() - 2, 0); if (additionalArgs != deleteCount) { if (additionalArgs < deleteCount) { - for (unsigned k = begin; k < length - deleteCount; ++k) { - if (JSValue v = getProperty(exec, thisObj, k + deleteCount)) - thisObj->put(exec, k + additionalArgs, v); - else - thisObj->deleteProperty(exec, k + additionalArgs); + if ((!begin) && (isJSArray(&exec->globalData(), thisObj))) + ((JSArray *)thisObj)->shiftCount(exec, deleteCount - additionalArgs); + else { + for (unsigned k = begin; k < length - deleteCount; ++k) { + if (JSValue v = getProperty(exec, thisObj, k + deleteCount)) + thisObj->put(exec, k + additionalArgs, v); + else + thisObj->deleteProperty(exec, k + additionalArgs); + } + for (unsigned k = length; k > length - deleteCount + additionalArgs; --k) + thisObj->deleteProperty(exec, k - 1); } - for (unsigned k = length; k > length - deleteCount + additionalArgs; --k) - thisObj->deleteProperty(exec, k - 1); } else { - for (unsigned k = length - deleteCount; k > begin; --k) { - if (JSValue obj = getProperty(exec, thisObj, k + deleteCount - 1)) - thisObj->put(exec, k + additionalArgs - 1, obj); - else - thisObj->deleteProperty(exec, k + additionalArgs - 1); + if ((!begin) && (isJSArray(&exec->globalData(), thisObj))) + ((JSArray *)thisObj)->unshiftCount(exec, additionalArgs - deleteCount); + else { + for (unsigned k = length - deleteCount; k > begin; --k) { + if (JSValue obj = getProperty(exec, thisObj, k + deleteCount - 1)) + thisObj->put(exec, k + additionalArgs - 1, obj); + else + thisObj->deleteProperty(exec, k + additionalArgs - 1); + } } } } @@ -610,12 +622,16 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec) // 15.4.4.13 unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec); unsigned nrArgs = exec->argumentCount(); - if (nrArgs) { - for (unsigned k = length; k > 0; --k) { - if (JSValue v = getProperty(exec, thisObj, k - 1)) - thisObj->put(exec, k + nrArgs - 1, v); - else - thisObj->deleteProperty(exec, k + nrArgs - 1); + if ((nrArgs) && (length)) { + if (isJSArray(&exec->globalData(), thisObj)) + ((JSArray *)thisObj)->unshiftCount(exec, nrArgs); + else { + for (unsigned k = length; k > 0; --k) { + if (JSValue v = getProperty(exec, thisObj, k - 1)) + thisObj->put(exec, k + nrArgs - 1, v); + else + thisObj->deleteProperty(exec, k + nrArgs - 1); + } } } for (unsigned k = 0; k < nrArgs; ++k) diff --git a/JavaScriptCore/runtime/Collector.h b/JavaScriptCore/runtime/Collector.h index f5bf113..1dc9445 100644 --- a/JavaScriptCore/runtime/Collector.h +++ b/JavaScriptCore/runtime/Collector.h @@ -185,16 +185,6 @@ namespace JSC { }; // tunable parameters - template struct CellSize; - - // cell size needs to be a power of two for certain optimizations in collector.cpp -#if USE(JSVALUE32) - template<> struct CellSize { static const size_t m_value = 32; }; -#else - template<> struct CellSize { static const size_t m_value = 64; }; -#endif - template<> struct CellSize { static const size_t m_value = 64; }; - #if OS(WINCE) || OS(SYMBIAN) const size_t BLOCK_SIZE = 64 * 1024; // 64k #else @@ -204,7 +194,7 @@ namespace JSC { // derived constants const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1; const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK; - const size_t MINIMUM_CELL_SIZE = CellSize::m_value; + const size_t MINIMUM_CELL_SIZE = 64; const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0); const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double); const size_t SMALL_CELL_SIZE = CELL_SIZE / 2; diff --git a/JavaScriptCore/runtime/JSArray.cpp b/JavaScriptCore/runtime/JSArray.cpp index 56603a3..99e1a10 100644 --- a/JavaScriptCore/runtime/JSArray.cpp +++ b/JavaScriptCore/runtime/JSArray.cpp @@ -78,6 +78,14 @@ ASSERT_CLASS_FITS_IN_CELL(JSArray); // 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 @@ -86,6 +94,11 @@ 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); @@ -100,21 +113,6 @@ static inline size_t storageSize(unsigned vectorLength) return size; } -static inline unsigned increasedVectorLength(unsigned newLength) -{ - ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH); - - // Mathematically equivalent to: - // increasedLength = (newLength * 3 + 1) / 2; - // or: - // increasedLength = (unsigned)ceil(newLength * 1.5)); - // This form is not prone to internal overflow. - unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1); - ASSERT(increasedLength >= newLength); - - return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH); -} - static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues) { return length / minDensityMultiplier <= numValues; @@ -133,7 +131,9 @@ JSArray::JSArray(NonNullPassRefPtr structure) { unsigned initialCapacity = 0; - m_storage = static_cast(fastZeroedMalloc(storageSize(initialCapacity))); + ArrayStorage* storage = static_cast(fastZeroedMalloc(storageSize(initialCapacity))); + m_indexBias = 0; + setArrayStorage(storage); m_vectorLength = initialCapacity; checkConsistency(); @@ -146,33 +146,36 @@ JSArray::JSArray(NonNullPassRefPtr structure, unsigned initialLength, if (creationMode == CreateCompact) initialCapacity = initialLength; else - initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX); - - m_storage = static_cast(fastMalloc(storageSize(initialCapacity))); + initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX); + + ArrayStorage* storage = static_cast(fastMalloc(storageSize(initialCapacity))); + storage->m_length = initialLength; + m_indexBias = 0; m_vectorLength = initialCapacity; - m_storage->m_sparseValueMap = 0; - m_storage->subclassData = 0; - m_storage->reportedMapCapacity = 0; + setArrayStorage(storage); + storage->m_sparseValueMap = 0; + storage->subclassData = 0; + storage->reportedMapCapacity = 0; if (creationMode == CreateCompact) { #if CHECK_ARRAY_CONSISTENCY - m_storage->m_inCompactInitialization = !!initialCapacity; + storage->m_inCompactInitialization = !!initialCapacity; #endif - m_storage->m_length = 0; - m_storage->m_numValuesInVector = initialCapacity; + storage->m_length = 0; + storage->m_numValuesInVector = initialCapacity; } else { #if CHECK_ARRAY_CONSISTENCY - m_storage->m_inCompactInitialization = false; + storage->m_inCompactInitialization = false; #endif - m_storage->m_length = initialLength; - m_storage->m_numValuesInVector = 0; - JSValue* vector = m_storage->m_vector; + storage->m_length = initialLength; + storage->m_numValuesInVector = 0; + JSValue* vector = m_vector; for (size_t i = 0; i < initialCapacity; ++i) vector[i] = JSValue(); } checkConsistency(); - + Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue)); } @@ -181,21 +184,24 @@ JSArray::JSArray(NonNullPassRefPtr structure, const ArgList& list) { unsigned initialCapacity = list.size(); - m_storage = static_cast(fastMalloc(storageSize(initialCapacity))); - m_storage->m_length = initialCapacity; + ArrayStorage* storage = static_cast(fastMalloc(storageSize(initialCapacity))); + m_indexBias = 0; + storage->m_length = initialCapacity; m_vectorLength = initialCapacity; - m_storage->m_numValuesInVector = initialCapacity; - m_storage->m_sparseValueMap = 0; - m_storage->subclassData = 0; - m_storage->reportedMapCapacity = 0; + storage->m_numValuesInVector = initialCapacity; + storage->m_sparseValueMap = 0; + storage->subclassData = 0; + storage->reportedMapCapacity = 0; #if CHECK_ARRAY_CONSISTENCY - m_storage->m_inCompactInitialization = false; + storage->m_inCompactInitialization = false; #endif + setArrayStorage(storage); size_t i = 0; + JSValue* vector = m_vector; ArgList::const_iterator end = list.end(); for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) - m_storage->m_vector[i] = *it; + vector[i] = *it; checkConsistency(); @@ -207,14 +213,16 @@ JSArray::~JSArray() ASSERT(vptr() == JSGlobalData::jsArrayVPtr); checkConsistency(DestructorConsistencyCheck); - delete m_storage->m_sparseValueMap; - fastFree(m_storage); + ArrayStorage* storage = arrayStorage(); + delete storage->m_sparseValueMap; + char* realStorage = reinterpret_cast(storage) - (m_indexBias * sizeof(JSValue)); + fastFree(realStorage); } bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) { - ArrayStorage* storage = m_storage; - + ArrayStorage* storage = arrayStorage(); + if (i >= storage->m_length) { if (i > MAX_ARRAY_INDEX) return getOwnPropertySlot(exec, Identifier::from(exec, i), slot); @@ -222,7 +230,7 @@ bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot } if (i < m_vectorLength) { - JSValue& valueSlot = storage->m_vector[i]; + JSValue& valueSlot = m_vector[i]; if (valueSlot) { slot.setValueSlot(&valueSlot); return true; @@ -261,19 +269,21 @@ bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& proper descriptor.setDescriptor(jsNumber(exec, length()), DontDelete | DontEnum); return true; } + + ArrayStorage* storage = arrayStorage(); bool isArrayIndex; unsigned i = propertyName.toArrayIndex(&isArrayIndex); if (isArrayIndex) { - if (i >= m_storage->m_length) + if (i >= storage->m_length) return false; if (i < m_vectorLength) { - JSValue& value = m_storage->m_vector[i]; + JSValue& value = m_vector[i]; if (value) { descriptor.setDescriptor(value, 0); return true; } - } else if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) { + } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) { if (i >= MIN_SPARSE_ARRAY_INDEX) { SparseArrayValueMap::iterator it = map->find(i); if (it != map->end()) { @@ -313,21 +323,23 @@ void JSArray::put(ExecState* exec, unsigned i, JSValue value) { checkConsistency(); - unsigned length = m_storage->m_length; + ArrayStorage* storage = arrayStorage(); + + unsigned length = storage->m_length; if (i >= length && i <= MAX_ARRAY_INDEX) { length = i + 1; - m_storage->m_length = length; + storage->m_length = length; } if (i < m_vectorLength) { - JSValue& valueSlot = m_storage->m_vector[i]; + JSValue& valueSlot = m_vector[i]; if (valueSlot) { valueSlot = value; checkConsistency(); return; } valueSlot = value; - ++m_storage->m_numValuesInVector; + ++storage->m_numValuesInVector; checkConsistency(); return; } @@ -337,7 +349,8 @@ void JSArray::put(ExecState* exec, unsigned i, JSValue value) NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value) { - ArrayStorage* storage = m_storage; + ArrayStorage* storage = arrayStorage(); + SparseArrayValueMap* map = storage->m_sparseValueMap; if (i >= MIN_SPARSE_ARRAY_INDEX) { @@ -374,9 +387,8 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu // 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; + m_vector[i] = value; + ++arrayStorage()->m_numValuesInVector; checkConsistency(); } else throwOutOfMemoryError(exec); @@ -385,7 +397,7 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu // Decide how many values it would be best to move from the map. unsigned newNumValuesInVector = storage->m_numValuesInVector + 1; - unsigned newVectorLength = increasedVectorLength(i + 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) @@ -394,7 +406,7 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu 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); + 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)) @@ -404,31 +416,37 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu } } - if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) { + int baseBias = m_indexBias * sizeof(JSValue); + char* baseStorage = reinterpret_cast(storage - baseBias); + + if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) { throwOutOfMemoryError(exec); return; } + storage = reinterpret_cast(baseStorage + baseBias); + setArrayStorage(storage); + unsigned vectorLength = m_vectorLength; if (newNumValuesInVector == storage->m_numValuesInVector + 1) { for (unsigned j = vectorLength; j < newVectorLength; ++j) - storage->m_vector[j] = JSValue(); + 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(); + m_vector[j] = JSValue(); for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) - storage->m_vector[j] = map->take(j); + m_vector[j] = map->take(j); } - storage->m_vector[i] = value; + ASSERT(i < newVectorLength); m_vectorLength = newVectorLength; storage->m_numValuesInVector = newNumValuesInVector; - m_storage = storage; + m_vector[i] = value; checkConsistency(); @@ -452,10 +470,10 @@ bool JSArray::deleteProperty(ExecState* exec, unsigned i) { checkConsistency(); - ArrayStorage* storage = m_storage; - + ArrayStorage* storage = arrayStorage(); + if (i < m_vectorLength) { - JSValue& valueSlot = storage->m_vector[i]; + JSValue& valueSlot = m_vector[i]; if (!valueSlot) { checkConsistency(); return false; @@ -491,11 +509,11 @@ void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNa // is incredibly inefficient for large arrays. We need a different approach, // which almost certainly means a different structure for PropertyNameArray. - ArrayStorage* storage = m_storage; - + ArrayStorage* storage = arrayStorage(); + unsigned usedVectorLength = min(storage->m_length, m_vectorLength); for (unsigned i = 0; i < usedVectorLength; ++i) { - if (storage->m_vector[i]) + if (m_vector[i]) propertyNames.add(Identifier::from(exec, i)); } @@ -511,32 +529,101 @@ void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNa JSObject::getOwnPropertyNames(exec, propertyNames, mode); } +ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength) +{ + ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH); + + unsigned increasedLength; + unsigned length = arrayStorage()->m_length; + + if (desiredLength < length) + increasedLength = length; + 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; + ArrayStorage* storage = arrayStorage(); unsigned vectorLength = m_vectorLength; ASSERT(newLength > vectorLength); ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); - unsigned newVectorLength = increasedVectorLength(newLength); + unsigned newVectorLength = getNewVectorLength(newLength); + int baseBias = m_indexBias * sizeof(JSValue); + char* baseStorage = reinterpret_cast(storage) - baseBias; - if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) + if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) return false; + + storage = reinterpret_cast(baseStorage + baseBias); + setArrayStorage(storage); + + JSValue* vector = m_vector; + for (unsigned i = vectorLength; i < newVectorLength; ++i) + vector[i] = JSValue(); m_vectorLength = newVectorLength; + + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); - for (unsigned i = vectorLength; i < newVectorLength; ++i) - storage->m_vector[i] = JSValue(); + return true; +} - m_storage = storage; +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 = arrayStorage(); + ArrayStorage* newStorage; + + unsigned vectorLength = m_vectorLength; + ASSERT(newLength > vectorLength); + ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); + unsigned newVectorLength = getNewVectorLength(newLength); + char* baseStorage = reinterpret_cast(storage) - (m_indexBias * sizeof(JSValue)); + + char* newBaseStorage = reinterpret_cast(fastMalloc(storageSize(newVectorLength + m_indexBias))); + if (!newBaseStorage) + return false; + + m_indexBias += newVectorLength - newLength; + int newStorageOffset = m_indexBias * sizeof(JSValue); + + newStorage = reinterpret_cast(newBaseStorage + newStorageOffset); + + memcpy(newStorage, storage, storageSize(0)); + memcpy(&newStorage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], storage->m_length * sizeof(JSValue)); + + m_vectorLength = newLength; + + fastFree(baseStorage); + setArrayStorage(newStorage); + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); - + return true; } + void JSArray::setLength(unsigned newLength) { @@ -547,14 +634,14 @@ void JSArray::setLength(unsigned newLength) m_storage->m_inCompactInitialization = false; #endif - ArrayStorage* storage = m_storage; - - unsigned length = m_storage->m_length; + ArrayStorage* storage = arrayStorage(); + + 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]; + JSValue& valueSlot = m_vector[i]; bool hadValue = valueSlot; valueSlot = JSValue(); storage->m_numValuesInVector -= hadValue; @@ -574,7 +661,7 @@ void JSArray::setLength(unsigned newLength) } } - m_storage->m_length = newLength; + storage->m_length = newLength; checkConsistency(); } @@ -583,7 +670,9 @@ JSValue JSArray::pop() { checkConsistency(); - unsigned length = m_storage->m_length; + ArrayStorage* storage = arrayStorage(); + + unsigned length = storage->m_length; if (!length) return jsUndefined(); @@ -592,29 +681,29 @@ JSValue JSArray::pop() JSValue result; if (length < m_vectorLength) { - JSValue& valueSlot = m_storage->m_vector[length]; + JSValue& valueSlot = m_vector[length]; if (valueSlot) { - --m_storage->m_numValuesInVector; + --storage->m_numValuesInVector; result = valueSlot; valueSlot = JSValue(); } else result = jsUndefined(); } else { result = jsUndefined(); - if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) { + 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; - m_storage->m_sparseValueMap = 0; + storage->m_sparseValueMap = 0; } } } } - m_storage->m_length = length; + storage->m_length = length; checkConsistency(); @@ -624,22 +713,25 @@ JSValue JSArray::pop() void JSArray::push(ExecState* exec, JSValue value) { checkConsistency(); + + ArrayStorage* storage = arrayStorage(); - if (m_storage->m_length < m_vectorLength) { - m_storage->m_vector[m_storage->m_length] = value; - ++m_storage->m_numValuesInVector; - ++m_storage->m_length; + if (storage->m_length < m_vectorLength) { + m_vector[storage->m_length] = value; + ++storage->m_numValuesInVector; + ++storage->m_length; checkConsistency(); return; } - if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) { - SparseArrayValueMap* map = m_storage->m_sparseValueMap; + if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) { + SparseArrayValueMap* map = 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; + if (increaseVectorLength(storage->m_length + 1)) { + storage = arrayStorage(); + m_vector[storage->m_length] = value; + ++storage->m_numValuesInVector; + ++storage->m_length; checkConsistency(); return; } @@ -649,7 +741,98 @@ void JSArray::push(ExecState* exec, JSValue value) } } - putSlowCase(exec, m_storage->m_length++, value); + putSlowCase(exec, storage->m_length++, value); +} + +void JSArray::shiftCount(ExecState* exec, int count) +{ + ASSERT(count > 0); + + ArrayStorage* storage = arrayStorage(); + + 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_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 = arrayStorage(); // 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) && (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(storage) + count * sizeof(JSValue); + memmove(newBaseStorage, storage, storageSize(0)); + storage = reinterpret_cast(newBaseStorage); + + m_indexBias += count; + setArrayStorage(storage); + } + } +} + +void JSArray::unshiftCount(ExecState* exec, int count) +{ + ArrayStorage* storage = arrayStorage(); + + 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_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 = arrayStorage(); // The put() above could have grown the vector and realloc'ed storage. + + if (m_indexBias >= count) { + m_indexBias -= count; + char* newBaseStorage = reinterpret_cast(storage) - count * sizeof(JSValue); + memmove(newBaseStorage, storage, storageSize(0)); + storage = reinterpret_cast(newBaseStorage); + setArrayStorage(storage); + m_vectorLength += count; + } else if ((!m_indexBias) && (!increaseVectorPrefixLength(m_vectorLength + count))) { + throwOutOfMemoryError(exec); + return; + } } void JSArray::markChildren(MarkStack& markStack) @@ -675,8 +858,10 @@ static int compareByStringPairForQSort(const void* a, const void* b) void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) { + ArrayStorage* storage = arrayStorage(); + unsigned lengthNotIncludingUndefined = compactForSorting(); - if (m_storage->m_sparseValueMap) { + if (storage->m_sparseValueMap) { throwOutOfMemoryError(exec); return; } @@ -685,9 +870,9 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal return; bool allValuesAreNumbers = true; - size_t size = m_storage->m_numValuesInVector; + size_t size = storage->m_numValuesInVector; for (size_t i = 0; i < size; ++i) { - if (!m_storage->m_vector[i].isNumber()) { + if (!m_vector[i].isNumber()) { allValuesAreNumbers = false; break; } @@ -699,15 +884,17 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal // 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); + qsort(m_vector, size, sizeof(JSValue), compareNumbersForQSort); checkConsistency(SortConsistencyCheck); } void JSArray::sort(ExecState* exec) { + ArrayStorage* storage = arrayStorage(); + unsigned lengthNotIncludingUndefined = compactForSorting(); - if (m_storage->m_sparseValueMap) { + if (storage->m_sparseValueMap) { throwOutOfMemoryError(exec); return; } @@ -727,7 +914,7 @@ void JSArray::sort(ExecState* exec) } for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { - JSValue value = m_storage->m_vector[i]; + JSValue value = m_vector[i]; ASSERT(!value.isUndefined()); values[i].first = value; } @@ -759,7 +946,7 @@ void JSArray::sort(ExecState* exec) // modifying the vector incorrectly. for (size_t i = 0; i < lengthNotIncludingUndefined; i++) - m_storage->m_vector[i] = values[i].first; + m_vector[i] = values[i].first; checkConsistency(SortConsistencyCheck); } @@ -846,18 +1033,20 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, { checkConsistency(); + ArrayStorage* storage = arrayStorage(); + // FIXME: This ignores exceptions raised in the compare function or in toNumber. // The maximum tree depth is compiled in - but the caller is clearly up to no good // if a larger array is passed. - ASSERT(m_storage->m_length <= static_cast(std::numeric_limits::max())); - if (m_storage->m_length > static_cast(std::numeric_limits::max())) + ASSERT(storage->m_length <= static_cast(std::numeric_limits::max())); + if (storage->m_length > static_cast(std::numeric_limits::max())) return; - if (!m_storage->m_length) + if (!storage->m_length) return; - unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength); + unsigned usedVectorLength = min(storage->m_length, m_vectorLength); AVLTree tree; // Depth 44 is enough for 2^31 items tree.abstractor().m_exec = exec; @@ -865,7 +1054,7 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, 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.resize(usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0)); if (callType == CallTypeJS) tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2, exec->exceptionSlot())); @@ -883,14 +1072,14 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, // 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]; + JSValue v = m_vector[numDefined]; if (!v || v.isUndefined()) break; tree.abstractor().m_nodes[numDefined].value = v; tree.insert(numDefined); } for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValue v = m_storage->m_vector[i]; + JSValue v = m_vector[i]; if (v) { if (v.isUndefined()) ++numUndefined; @@ -904,7 +1093,7 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, unsigned newUsedVectorLength = numDefined + numUndefined; - if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) { + 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. @@ -913,6 +1102,8 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, return; } } + + storage = arrayStorage(); SparseArrayValueMap::iterator end = map->end(); for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { @@ -922,7 +1113,7 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, } delete map; - m_storage->m_sparseValueMap = 0; + storage->m_sparseValueMap = 0; } ASSERT(tree.abstractor().m_nodes.size() >= numDefined); @@ -934,27 +1125,29 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, AVLTree::Iterator iter; iter.start_iter_least(tree); for (unsigned i = 0; i < numDefined; ++i) { - m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value; + m_vector[i] = 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(); + m_vector[i] = jsUndefined(); // Ensure that unused values in the vector are zeroed out. for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - m_storage->m_vector[i] = JSValue(); + m_vector[i] = JSValue(); - m_storage->m_numValuesInVector = newUsedVectorLength; + storage->m_numValuesInVector = newUsedVectorLength; checkConsistency(SortConsistencyCheck); } void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) { - JSValue* vector = m_storage->m_vector; - unsigned vectorEnd = min(m_storage->m_length, m_vectorLength); + ArrayStorage* storage = arrayStorage(); + + JSValue* vector = storage->m_vector; + unsigned vectorEnd = min(storage->m_length, m_vectorLength); unsigned i = 0; for (; i < vectorEnd; ++i) { JSValue& v = vector[i]; @@ -963,15 +1156,15 @@ void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) args.append(v); } - for (; i < m_storage->m_length; ++i) + 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); + ASSERT(arrayStorage()->m_length >= maxSize); UNUSED_PARAM(maxSize); - JSValue* vector = m_storage->m_vector; + JSValue* vector = m_vector; unsigned vectorEnd = min(maxSize, m_vectorLength); unsigned i = 0; for (; i < vectorEnd; ++i) { @@ -989,25 +1182,25 @@ unsigned JSArray::compactForSorting() { checkConsistency(); - ArrayStorage* storage = m_storage; + ArrayStorage* storage = arrayStorage(); - unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength); + unsigned usedVectorLength = min(storage->m_length, m_vectorLength); unsigned numDefined = 0; unsigned numUndefined = 0; for (; numDefined < usedVectorLength; ++numDefined) { - JSValue v = storage->m_vector[numDefined]; + JSValue v = m_vector[numDefined]; if (!v || v.isUndefined()) break; } for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValue v = storage->m_vector[i]; + JSValue v = m_vector[i]; if (v) { if (v.isUndefined()) ++numUndefined; else - storage->m_vector[numDefined++] = v; + m_vector[numDefined++] = v; } } @@ -1020,21 +1213,22 @@ unsigned JSArray::compactForSorting() // exception is thrown by caller. if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) return 0; - storage = m_storage; + + storage = arrayStorage(); } SparseArrayValueMap::iterator end = map->end(); for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - storage->m_vector[numDefined++] = it->second; + m_vector[numDefined++] = it->second; delete map; storage->m_sparseValueMap = 0; } for (unsigned i = numDefined; i < newUsedVectorLength; ++i) - storage->m_vector[i] = jsUndefined(); + m_vector[i] = jsUndefined(); for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - storage->m_vector[i] = JSValue(); + m_vector[i] = JSValue(); storage->m_numValuesInVector = newUsedVectorLength; @@ -1045,42 +1239,44 @@ unsigned JSArray::compactForSorting() void* JSArray::subclassData() const { - return m_storage->subclassData; + return arrayStorage()->subclassData; } void JSArray::setSubclassData(void* d) { - m_storage->subclassData = d; + arrayStorage()->subclassData = d; } #if CHECK_ARRAY_CONSISTENCY void JSArray::checkConsistency(ConsistencyCheckType type) { - ASSERT(m_storage); + ArrayStorage* storage = arrayStorage(); + + ASSERT(storage); if (type == SortConsistencyCheck) - ASSERT(!m_storage->m_sparseValueMap); + ASSERT(!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 (JSValue value = 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 >= m_storage->m_numValuesInVector); + ASSERT(i >= storage->m_numValuesInVector); } } - ASSERT(numValuesInVector == m_storage->m_numValuesInVector); - ASSERT(numValuesInVector <= m_storage->m_length); + ASSERT(numValuesInVector == storage->m_numValuesInVector); + ASSERT(numValuesInVector <= 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) { + 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 < m_storage->m_length); + ASSERT(index < storage->m_length); ASSERT(index >= m_vectorLength); ASSERT(index <= MAX_ARRAY_INDEX); ASSERT(it->second); diff --git a/JavaScriptCore/runtime/JSArray.h b/JavaScriptCore/runtime/JSArray.h index b6dd7cc..a7ce328 100644 --- a/JavaScriptCore/runtime/JSArray.h +++ b/JavaScriptCore/runtime/JSArray.h @@ -29,8 +29,13 @@ namespace JSC { typedef HashMap SparseArrayValueMap; + // This struct holds the actual data values of an array. A JSArray object points to it's contained ArrayStorage + // struct by pointing to m_vector. To access the contained ArrayStorage struct, use the getStorage() and + // setStorage() methods. It is important to note that there may be space before the ArrayStorage that + // is used to quick unshift / shift operation. The actual allocated pointer is available by using: + // getStorage() - m_indexBias * sizeof(JSValue) struct ArrayStorage { - unsigned m_length; + unsigned m_length; // The "length" property on the array unsigned m_numValuesInVector; SparseArrayValueMap* m_sparseValueMap; void* subclassData; // A JSArray subclass can use this to fill the vector lazily. @@ -67,8 +72,8 @@ namespace JSC { virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem. static JS_EXPORTDATA const ClassInfo info; - - unsigned length() const { return m_storage->m_length; } + + unsigned length() const { return arrayStorage()->m_length; } void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray. void sort(ExecState*); @@ -78,33 +83,39 @@ namespace JSC { void push(ExecState*, JSValue); JSValue pop(); - bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; } + void shiftCount(ExecState*, int count); + void unshiftCount(ExecState*, int count); + + bool canGetIndex(unsigned i) { return i < m_vectorLength && m_vector[i]; } JSValue getIndex(unsigned i) { ASSERT(canGetIndex(i)); - return m_storage->m_vector[i]; + return m_vector[i]; } bool canSetIndex(unsigned i) { return i < m_vectorLength; } void setIndex(unsigned i, JSValue v) { ASSERT(canSetIndex(i)); - JSValue& x = m_storage->m_vector[i]; + + JSValue& x = m_vector[i]; if (!x) { - ++m_storage->m_numValuesInVector; - if (i >= m_storage->m_length) - m_storage->m_length = i + 1; + ArrayStorage *storage = arrayStorage(); + ++storage->m_numValuesInVector; + if (i >= storage->m_length) + storage->m_length = i + 1; } x = v; } - + void uncheckedSetIndex(unsigned i, JSValue v) { ASSERT(canSetIndex(i)); + ArrayStorage *storage = arrayStorage(); #if CHECK_ARRAY_CONSISTENCY - ASSERT(m_storage->m_inCompactInitialization); + ASSERT(storage->m_inCompactInitialization); #endif - m_storage->m_vector[i] = v; + storage->m_vector[i] = v; } void fillArgList(ExecState*, MarkedArgumentBuffer&); @@ -127,6 +138,16 @@ namespace JSC { void* subclassData() const; void setSubclassData(void*); + + inline ArrayStorage *arrayStorage() const + { + return reinterpret_cast(reinterpret_cast(m_vector) - (sizeof(ArrayStorage) - sizeof(JSValue))); + } + + inline void setArrayStorage(ArrayStorage *storage) + { + m_vector = &storage->m_vector[0]; + } private: virtual const ClassInfo* classInfo() const { return &info; } @@ -134,15 +155,18 @@ namespace JSC { bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&); void putSlowCase(ExecState*, unsigned propertyName, JSValue); + unsigned getNewVectorLength(unsigned desiredLength); bool increaseVectorLength(unsigned newLength); + bool increaseVectorPrefixLength(unsigned newLength); unsigned compactForSorting(); enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck }; void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck); - unsigned m_vectorLength; - ArrayStorage* m_storage; + unsigned m_vectorLength; // The valid length of m_vector + int m_indexBias; // The number of JSValue sized blocks before ArrayStorage. + JSValue* m_vector; // Copy of ArrayStorage.m_vector. Used for quick vector access and to materialize ArrayStorage ptr. }; JSArray* asArray(JSValue); @@ -168,7 +192,7 @@ namespace JSC { { JSObject::markChildrenDirect(markStack); - ArrayStorage* storage = m_storage; + ArrayStorage* storage = arrayStorage(); unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength); markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues); -- cgit v1.1