X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/b80e619319b1def83d1e8b4f84042b661be1be7f..1df5f87f1309a8daa30dabdee855f48ae40d14ab:/runtime/JSArray.cpp?ds=inline diff --git a/runtime/JSArray.cpp b/runtime/JSArray.cpp index eb778ed..473ba1d 100644 --- a/runtime/JSArray.cpp +++ b/runtime/JSArray.cpp @@ -33,8 +33,6 @@ #include #include -#define CHECK_ARRAY_CONSISTENCY 0 - using namespace std; using namespace WTF; @@ -80,17 +78,31 @@ 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 // 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}; +const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0}; + +// We keep track of the size of the last array after it was grown. We use this +// as a simple heuristic for as the value to grow the next array from size 0. +// This value is capped by the constant FIRST_VECTOR_GROW defined above. +static unsigned lastArraySize = 0; static inline size_t storageSize(unsigned vectorLength) { - ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH); + if (vectorLength > MAX_STORAGE_VECTOR_LENGTH) + CRASH(); // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH) // - as asserted above - the following calculation cannot overflow. @@ -102,21 +114,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; @@ -130,60 +127,109 @@ inline void JSArray::checkConsistency(ConsistencyCheckType) #endif -JSArray::JSArray(NonNullPassRefPtr structure) - : JSObject(structure) +JSArray::JSArray(VPtrStealingHackType) + : JSNonFinalObject(VPtrStealingHack) { +} + +JSArray::JSArray(JSGlobalData& globalData, Structure* structure) + : JSNonFinalObject(globalData, structure) +{ + ASSERT(inherits(&s_info)); + unsigned initialCapacity = 0; m_storage = static_cast(fastZeroedMalloc(storageSize(initialCapacity))); + m_storage->m_allocBase = m_storage; + m_indexBias = 0; m_vectorLength = initialCapacity; checkConsistency(); + + Heap::heap(this)->reportExtraMemoryCost(storageSize(0)); } -JSArray::JSArray(NonNullPassRefPtr structure, unsigned initialLength) - : JSObject(structure) +JSArray::JSArray(JSGlobalData& globalData, Structure* structure, unsigned initialLength, ArrayCreationMode creationMode) + : JSNonFinalObject(globalData, structure) { - unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX); + ASSERT(inherits(&s_info)); + unsigned initialCapacity; + if (creationMode == CreateCompact) + initialCapacity = initialLength; + else + initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX); + m_storage = static_cast(fastMalloc(storageSize(initialCapacity))); + m_storage->m_allocBase = m_storage; m_storage->m_length = initialLength; + m_indexBias = 0; m_vectorLength = initialCapacity; - m_storage->m_numValuesInVector = 0; m_storage->m_sparseValueMap = 0; m_storage->subclassData = 0; m_storage->reportedMapCapacity = 0; - JSValue* vector = m_storage->m_vector; - for (size_t i = 0; i < initialCapacity; ++i) - vector[i] = JSValue(); + if (creationMode == CreateCompact) { +#if CHECK_ARRAY_CONSISTENCY + m_storage->m_inCompactInitialization = !!initialCapacity; +#endif + m_storage->m_length = 0; + m_storage->m_numValuesInVector = initialCapacity; + } else { +#if CHECK_ARRAY_CONSISTENCY + storage->m_inCompactInitialization = false; +#endif + m_storage->m_length = initialLength; + m_storage->m_numValuesInVector = 0; + WriteBarrier* vector = m_storage->m_vector; + for (size_t i = 0; i < initialCapacity; ++i) + vector[i].clear(); + } checkConsistency(); - - Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue)); + + Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity)); } -JSArray::JSArray(NonNullPassRefPtr structure, const ArgList& list) - : JSObject(structure) +JSArray::JSArray(JSGlobalData& globalData, Structure* structure, const ArgList& list) + : JSNonFinalObject(globalData, structure) { - unsigned initialCapacity = list.size(); + ASSERT(inherits(&s_info)); - m_storage = static_cast(fastMalloc(storageSize(initialCapacity))); + unsigned initialCapacity = list.size(); + unsigned initialStorage; + + // If the ArgList is empty, allocate space for 3 entries. This value empirically + // works well for benchmarks. + if (!initialCapacity) + initialStorage = 3; + else + initialStorage = initialCapacity; + + m_storage = static_cast(fastMalloc(storageSize(initialStorage))); + m_storage->m_allocBase = m_storage; + m_indexBias = 0; m_storage->m_length = initialCapacity; - m_vectorLength = initialCapacity; + m_vectorLength = initialStorage; m_storage->m_numValuesInVector = initialCapacity; m_storage->m_sparseValueMap = 0; m_storage->subclassData = 0; m_storage->reportedMapCapacity = 0; +#if CHECK_ARRAY_CONSISTENCY + m_storage->m_inCompactInitialization = false; +#endif size_t i = 0; + WriteBarrier* vector = m_storage->m_vector; ArgList::const_iterator end = list.end(); for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) - m_storage->m_vector[i] = *it; + vector[i].set(globalData, this, *it); + for (; i < initialStorage; i++) + vector[i].clear(); checkConsistency(); - Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity)); + Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage)); } JSArray::~JSArray() @@ -192,13 +238,13 @@ JSArray::~JSArray() checkConsistency(DestructorConsistencyCheck); delete m_storage->m_sparseValueMap; - fastFree(m_storage); + fastFree(m_storage->m_allocBase); } bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) { ArrayStorage* storage = m_storage; - + if (i >= storage->m_length) { if (i > MAX_ARRAY_INDEX) return getOwnPropertySlot(exec, Identifier::from(exec, i), slot); @@ -206,16 +252,16 @@ bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot } if (i < m_vectorLength) { - JSValue& valueSlot = storage->m_vector[i]; - if (valueSlot) { - slot.setValueSlot(&valueSlot); + JSValue value = storage->m_vector[i].get(); + if (value) { + slot.setValue(value); 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); + slot.setValue(it->second.get()); return true; } } @@ -227,12 +273,12 @@ bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot) { if (propertyName == exec->propertyNames().length) { - slot.setValue(jsNumber(exec, length())); + slot.setValue(jsNumber(length())); return true; } bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); + unsigned i = propertyName.toArrayIndex(isArrayIndex); if (isArrayIndex) return JSArray::getOwnPropertySlot(exec, i, slot); @@ -242,26 +288,28 @@ bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor) { if (propertyName == exec->propertyNames().length) { - descriptor.setDescriptor(jsNumber(exec, length()), DontDelete | DontEnum); + descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum); return true; } + + ArrayStorage* storage = m_storage; bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&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]; + WriteBarrier& value = storage->m_vector[i]; if (value) { - descriptor.setDescriptor(value, 0); + descriptor.setDescriptor(value.get(), 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()) { - descriptor.setDescriptor(it->second, 0); + descriptor.setDescriptor(it->second.get(), 0); return true; } } @@ -274,7 +322,7 @@ bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& proper void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot) { bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); + unsigned i = propertyName.toArrayIndex(isArrayIndex); if (isArrayIndex) { put(exec, i, value); return; @@ -283,7 +331,7 @@ void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value if (propertyName == exec->propertyNames().length) { unsigned newLength = value.toUInt32(exec); if (value.toNumber(exec) != static_cast(newLength)) { - throwError(exec, RangeError, "Invalid array length."); + throwError(exec, createRangeError(exec, "Invalid array length.")); return; } setLength(newLength); @@ -297,21 +345,23 @@ void JSArray::put(ExecState* exec, unsigned i, JSValue value) { checkConsistency(); - unsigned length = m_storage->m_length; + ArrayStorage* storage = m_storage; + + 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]; + WriteBarrier& valueSlot = storage->m_vector[i]; if (valueSlot) { - valueSlot = value; + valueSlot.set(exec->globalData(), this, value); checkConsistency(); return; } - valueSlot = value; - ++m_storage->m_numValuesInVector; + valueSlot.set(exec->globalData(), this, value); + ++storage->m_numValuesInVector; checkConsistency(); return; } @@ -322,6 +372,7 @@ void JSArray::put(ExecState* exec, unsigned i, JSValue value) NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value) { ArrayStorage* storage = m_storage; + SparseArrayValueMap* map = storage->m_sparseValueMap; if (i >= MIN_SPARSE_ARRAY_INDEX) { @@ -339,11 +390,11 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu storage->m_sparseValueMap = map; } - pair result = map->add(i, value); - if (!result.second) { // pre-existing entry - result.first->second = value; + WriteBarrier temp; + pair result = map->add(i, temp); + result.first->second.set(exec->globalData(), this, value); + if (!result.second) // pre-existing entry return; - } size_t capacity = map->capacity(); if (capacity != storage->reportedMapCapacity) { @@ -359,7 +410,7 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu if (!map || map->isEmpty()) { if (increaseVectorLength(i + 1)) { storage = m_storage; - storage->m_vector[i] = value; + storage->m_vector[i].set(exec->globalData(), this, value); ++storage->m_numValuesInVector; checkConsistency(); } else @@ -369,16 +420,17 @@ 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) newNumValuesInVector -= map->contains(i); if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) { + unsigned needLength = max(i + 1, storage->m_length); unsigned proposedNewNumValuesInVector = newNumValuesInVector; // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further. - while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) { - unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1); + while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) { + unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1); for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j) proposedNewNumValuesInVector += map->contains(j); if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector)) @@ -388,31 +440,40 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu } } - if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) { + void* baseStorage = storage->m_allocBase; + + if ((unsigned)m_indexBias > (MAX_STORAGE_VECTOR_LENGTH - newVectorLength) + || !tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) { throwOutOfMemoryError(exec); return; } + m_storage = reinterpret_cast_ptr(static_cast(baseStorage) + m_indexBias * sizeof(JSValue)); + m_storage->m_allocBase = baseStorage; + storage = m_storage; + unsigned vectorLength = m_vectorLength; + WriteBarrier* vector = storage->m_vector; if (newNumValuesInVector == storage->m_numValuesInVector + 1) { for (unsigned j = vectorLength; j < newVectorLength; ++j) - storage->m_vector[j] = JSValue(); + vector[j].clear(); if (i > MIN_SPARSE_ARRAY_INDEX) map->remove(i); } else { for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j) - storage->m_vector[j] = JSValue(); + vector[j].clear(); + JSGlobalData& globalData = exec->globalData(); for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) - storage->m_vector[j] = map->take(j); + vector[j].set(globalData, this, map->take(j).get()); } - storage->m_vector[i] = value; + ASSERT(i < newVectorLength); m_vectorLength = newVectorLength; storage->m_numValuesInVector = newNumValuesInVector; - m_storage = storage; + storage->m_vector[i].set(exec->globalData(), this, value); checkConsistency(); @@ -422,7 +483,7 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName) { bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); + unsigned i = propertyName.toArrayIndex(isArrayIndex); if (isArrayIndex) return deleteProperty(exec, i); @@ -437,14 +498,14 @@ bool JSArray::deleteProperty(ExecState* exec, unsigned i) checkConsistency(); ArrayStorage* storage = m_storage; - + if (i < m_vectorLength) { - JSValue& valueSlot = storage->m_vector[i]; + WriteBarrier& valueSlot = storage->m_vector[i]; if (!valueSlot) { checkConsistency(); return false; } - valueSlot = JSValue(); + valueSlot.clear(); --storage->m_numValuesInVector; checkConsistency(); return true; @@ -476,7 +537,7 @@ void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNa // which almost certainly means a different structure for PropertyNameArray. ArrayStorage* storage = m_storage; - + unsigned usedVectorLength = min(storage->m_length, m_vectorLength); for (unsigned i = 0; i < usedVectorLength; ++i) { if (storage->m_vector[i]) @@ -495,6 +556,33 @@ 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 maxInitLength = min(m_storage->m_length, 100000U); + + if (desiredLength < maxInitLength) + increasedLength = maxInitLength; + else if (!m_vectorLength) + increasedLength = max(desiredLength, lastArraySize); + else { + // Mathematically equivalent to: + // increasedLength = (newLength * 3 + 1) / 2; + // or: + // increasedLength = (unsigned)ceil(newLength * 1.5)); + // This form is not prone to internal overflow. + increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1); + } + + ASSERT(increasedLength >= desiredLength); + + lastArraySize = min(increasedLength, FIRST_VECTOR_GROW); + + return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH); +} + bool JSArray::increaseVectorLength(unsigned newLength) { // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map @@ -505,37 +593,85 @@ bool JSArray::increaseVectorLength(unsigned newLength) unsigned vectorLength = m_vectorLength; ASSERT(newLength > vectorLength); ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); - unsigned newVectorLength = increasedVectorLength(newLength); + unsigned newVectorLength = getNewVectorLength(newLength); + void* baseStorage = storage->m_allocBase; - if (!tryFastRealloc(storage, storageSize(newVectorLength)).getValue(storage)) + if ((unsigned)m_indexBias > (MAX_STORAGE_VECTOR_LENGTH - newVectorLength) + || !tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) return false; - m_vectorLength = newVectorLength; + storage = m_storage = reinterpret_cast_ptr(static_cast(baseStorage) + m_indexBias * sizeof(JSValue)); + m_storage->m_allocBase = baseStorage; + WriteBarrier* vector = storage->m_vector; for (unsigned i = vectorLength; i < newVectorLength; ++i) - storage->m_vector[i] = JSValue(); - - m_storage = storage; + vector[i].clear(); + m_vectorLength = newVectorLength; + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); return true; } -void JSArray::setLength(unsigned newLength) +bool JSArray::increaseVectorPrefixLength(unsigned newLength) { - checkConsistency(); + // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map + // to the vector. Callers have to account for that, because they can do it more efficiently. + + ArrayStorage* storage = m_storage; + + unsigned vectorLength = m_vectorLength; + ASSERT(newLength > vectorLength); + ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); + unsigned newVectorLength = getNewVectorLength(newLength); + + if ((unsigned)m_indexBias > (MAX_STORAGE_VECTOR_LENGTH - newVectorLength)) + return false; + void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias)); + if (!newBaseStorage) + return false; + + m_indexBias += newVectorLength - newLength; + + m_storage = reinterpret_cast_ptr(static_cast(newBaseStorage) + m_indexBias * sizeof(JSValue)); + + memcpy(m_storage, storage, storageSize(0)); + memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue)); + + m_storage->m_allocBase = newBaseStorage; + m_vectorLength = newLength; + + fastFree(storage->m_allocBase); + ASSERT(newLength > vectorLength); + unsigned delta = newLength - vectorLength; + for (unsigned i = 0; i < delta; i++) + m_storage->m_vector[i].clear(); + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + + return true; +} + +void JSArray::setLength(unsigned newLength) +{ ArrayStorage* storage = m_storage; + +#if CHECK_ARRAY_CONSISTENCY + if (!storage->m_inCompactInitialization) + checkConsistency(); + else + storage->m_inCompactInitialization = false; +#endif - unsigned length = m_storage->m_length; + 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]; + WriteBarrier& valueSlot = storage->m_vector[i]; bool hadValue = valueSlot; - valueSlot = JSValue(); + valueSlot.clear(); storage->m_numValuesInVector -= hadValue; } @@ -553,7 +689,7 @@ void JSArray::setLength(unsigned newLength) } } - m_storage->m_length = newLength; + storage->m_length = newLength; checkConsistency(); } @@ -562,7 +698,9 @@ JSValue JSArray::pop() { checkConsistency(); - unsigned length = m_storage->m_length; + ArrayStorage* storage = m_storage; + + unsigned length = storage->m_length; if (!length) return jsUndefined(); @@ -571,29 +709,29 @@ JSValue JSArray::pop() JSValue result; if (length < m_vectorLength) { - JSValue& valueSlot = m_storage->m_vector[length]; + WriteBarrier& valueSlot = storage->m_vector[length]; if (valueSlot) { - --m_storage->m_numValuesInVector; - result = valueSlot; - valueSlot = JSValue(); + --storage->m_numValuesInVector; + result = valueSlot.get(); + valueSlot.clear(); } 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; + result = it->second.get(); 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(); @@ -603,22 +741,25 @@ JSValue JSArray::pop() void JSArray::push(ExecState* exec, JSValue value) { checkConsistency(); + + ArrayStorage* storage = m_storage; - 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) { + storage->m_vector[storage->m_length].set(exec->globalData(), this, 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 = m_storage; + storage->m_vector[storage->m_length].set(exec->globalData(), this, value); + ++storage->m_numValuesInVector; + ++storage->m_length; checkConsistency(); return; } @@ -628,12 +769,109 @@ void JSArray::push(ExecState* exec, JSValue value) } } - putSlowCase(exec, m_storage->m_length++, value); + putSlowCase(exec, storage->m_length++, value); } -void JSArray::markChildren(MarkStack& markStack) +void JSArray::shiftCount(ExecState* exec, int count) { - markChildrenDirect(markStack); + ASSERT(count > 0); + + ArrayStorage* storage = m_storage; + + unsigned oldLength = storage->m_length; + + if (!oldLength) + return; + + if (oldLength != storage->m_numValuesInVector) { + // If m_length and m_numValuesInVector aren't the same, we have a sparse vector + // which means we need to go through each entry looking for the the "empty" + // slots and then fill them with possible properties. See ECMA spec. + // 15.4.4.9 steps 11 through 13. + for (unsigned i = count; i < oldLength; ++i) { + if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) { + PropertySlot slot(this); + JSValue p = prototype(); + if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot))) + put(exec, i, slot.getValue(exec, i)); + } + } + + storage = m_storage; // The put() above could have grown the vector and realloc'ed storage. + + // Need to decrement numValuesInvector based on number of real entries + for (unsigned i = 0; i < (unsigned)count; ++i) + if ((i < m_vectorLength) && (storage->m_vector[i])) + --storage->m_numValuesInVector; + } else + storage->m_numValuesInVector -= count; + + storage->m_length -= count; + + if (m_vectorLength) { + count = min(m_vectorLength, (unsigned)count); + + m_vectorLength -= count; + + if (m_vectorLength) { + char* newBaseStorage = reinterpret_cast(storage) + count * sizeof(JSValue); + memmove(newBaseStorage, storage, storageSize(0)); + m_storage = reinterpret_cast_ptr(newBaseStorage); + + m_indexBias += count; + } + } +} + +void JSArray::unshiftCount(ExecState* exec, int count) +{ + ArrayStorage* storage = m_storage; + + ASSERT(m_indexBias >= 0); + ASSERT(count >= 0); + + unsigned length = storage->m_length; + + if (length != storage->m_numValuesInVector) { + // If m_length and m_numValuesInVector aren't the same, we have a sparse vector + // which means we need to go through each entry looking for the the "empty" + // slots and then fill them with possible properties. See ECMA spec. + // 15.4.4.13 steps 8 through 10. + for (unsigned i = 0; i < length; ++i) { + if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) { + PropertySlot slot(this); + JSValue p = prototype(); + if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot))) + put(exec, i, slot.getValue(exec, i)); + } + } + } + + storage = m_storage; // The put() above could have grown the vector and realloc'ed storage. + + if (m_indexBias >= count) { + m_indexBias -= count; + char* newBaseStorage = reinterpret_cast(storage) - count * sizeof(JSValue); + memmove(newBaseStorage, storage, storageSize(0)); + m_storage = reinterpret_cast_ptr(newBaseStorage); + m_vectorLength += count; + } else if ((unsigned)count > (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) + || !increaseVectorPrefixLength(m_vectorLength + count)) { + throwOutOfMemoryError(exec); + return; + } + + WriteBarrier* vector = m_storage->m_vector; + for (int i = 0; i < count; i++) + vector[i].clear(); +} + +void JSArray::visitChildren(SlotVisitor& visitor) +{ + ASSERT_GC_OBJECT_INHERITS(this, &s_info); + COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag); + ASSERT(structure()->typeInfo().overridesVisitChildren()); + visitChildrenDirect(visitor); } static int compareNumbersForQSort(const void* a, const void* b) @@ -647,13 +885,15 @@ static int compareByStringPairForQSort(const void* a, const void* b) { const ValueStringPair* va = static_cast(a); const ValueStringPair* vb = static_cast(b); - return compare(va->second, vb->second); + return codePointCompare(va->second, vb->second); } void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) { + ArrayStorage* storage = m_storage; + unsigned lengthNotIncludingUndefined = compactForSorting(); - if (m_storage->m_sparseValueMap) { + if (storage->m_sparseValueMap) { throwOutOfMemoryError(exec); return; } @@ -662,9 +902,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 (!storage->m_vector[i].isNumber()) { allValuesAreNumbers = false; break; } @@ -676,15 +916,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(storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort); checkConsistency(SortConsistencyCheck); } void JSArray::sort(ExecState* exec) { + ArrayStorage* storage = m_storage; + unsigned lengthNotIncludingUndefined = compactForSorting(); - if (m_storage->m_sparseValueMap) { + if (storage->m_sparseValueMap) { throwOutOfMemoryError(exec); return; } @@ -706,7 +948,7 @@ void JSArray::sort(ExecState* exec) Heap::heap(this)->pushTempSortVector(&values); for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { - JSValue value = m_storage->m_vector[i]; + JSValue value = storage->m_vector[i].get(); ASSERT(!value.isUndefined()); values[i].first = value; } @@ -737,11 +979,12 @@ void JSArray::sort(ExecState* exec) // increase the length to handle the orignal number of actual values. if (m_vectorLength < lengthNotIncludingUndefined) increaseVectorLength(lengthNotIncludingUndefined); - if (m_storage->m_length < lengthNotIncludingUndefined) - m_storage->m_length = lengthNotIncludingUndefined; - + if (storage->m_length < lengthNotIncludingUndefined) + storage->m_length = lengthNotIncludingUndefined; + + JSGlobalData& globalData = exec->globalData(); for (size_t i = 0; i < lengthNotIncludingUndefined; i++) - m_storage->m_vector[i] = values[i].first; + storage->m_vector[i].set(globalData, this, values[i].first); Heap::heap(this)->popTempSortVector(&values); @@ -830,18 +1073,21 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, { checkConsistency(); + ArrayStorage* storage = m_storage; + // FIXME: This ignores exceptions raised in the compare function or in toNumber. // The maximum tree depth is compiled in - but the caller is clearly up to no good // if a larger array is passed. - ASSERT(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) - return; + unsigned usedVectorLength = min(storage->m_length, m_vectorLength); + unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0); - unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength); + if (!nodeCount) + return; AVLTree tree; // Depth 44 is enough for 2^31 items tree.abstractor().m_exec = exec; @@ -849,10 +1095,10 @@ 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.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, asFunction(compareFunction), 2)); if (!tree.abstractor().m_nodes.begin()) { throwOutOfMemoryError(exec); @@ -867,14 +1113,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 = storage->m_vector[numDefined].get(); 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 = storage->m_vector[i].get(); if (v) { if (v.isUndefined()) ++numUndefined; @@ -888,7 +1134,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. @@ -897,16 +1143,18 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, return; } } + + storage = m_storage; SparseArrayValueMap::iterator end = map->end(); for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { - tree.abstractor().m_nodes[numDefined].value = it->second; + tree.abstractor().m_nodes[numDefined].value = it->second.get(); tree.insert(numDefined); ++numDefined; } delete map; - m_storage->m_sparseValueMap = 0; + storage->m_sparseValueMap = 0; } ASSERT(tree.abstractor().m_nodes.size() >= numDefined); @@ -917,37 +1165,40 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, // Copy the values back into m_storage. AVLTree::Iterator iter; iter.start_iter_least(tree); + JSGlobalData& globalData = exec->globalData(); for (unsigned i = 0; i < numDefined; ++i) { - m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value; + storage->m_vector[i].set(globalData, 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(); + storage->m_vector[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(); + storage->m_vector[i].clear(); - 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 = m_storage; + + WriteBarrier* vector = storage->m_vector; + unsigned vectorEnd = min(storage->m_length, m_vectorLength); unsigned i = 0; for (; i < vectorEnd; ++i) { - JSValue& v = vector[i]; + WriteBarrier& v = vector[i]; if (!v) break; - args.append(v); + args.append(v.get()); } - for (; i < m_storage->m_length; ++i) + for (; i < storage->m_length; ++i) args.append(get(exec, i)); } @@ -955,14 +1206,14 @@ void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSiz { ASSERT(m_storage->m_length >= maxSize); UNUSED_PARAM(maxSize); - JSValue* vector = m_storage->m_vector; + WriteBarrier* vector = m_storage->m_vector; unsigned vectorEnd = min(maxSize, m_vectorLength); unsigned i = 0; for (; i < vectorEnd; ++i) { - JSValue& v = vector[i]; + WriteBarrier& v = vector[i]; if (!v) break; - buffer[i] = v; + buffer[i] = v.get(); } for (; i < maxSize; ++i) @@ -975,23 +1226,24 @@ unsigned JSArray::compactForSorting() ArrayStorage* storage = m_storage; - 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 = storage->m_vector[numDefined].get(); if (!v || v.isUndefined()) break; } + for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValue v = storage->m_vector[i]; + JSValue v = storage->m_vector[i].get(); if (v) { if (v.isUndefined()) ++numUndefined; else - storage->m_vector[numDefined++] = v; + storage->m_vector[numDefined++].setWithoutWriteBarrier(v); } } @@ -1004,21 +1256,22 @@ unsigned JSArray::compactForSorting() // exception is thrown by caller. if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) return 0; + storage = m_storage; } SparseArrayValueMap::iterator end = map->end(); for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - storage->m_vector[numDefined++] = it->second; + storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.get()); delete map; storage->m_sparseValueMap = 0; } for (unsigned i = numDefined; i < newUsedVectorLength; ++i) - storage->m_vector[i] = jsUndefined(); + storage->m_vector[i].setUndefined(); for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - storage->m_vector[i] = JSValue(); + storage->m_vector[i].clear(); storage->m_numValuesInVector = newUsedVectorLength; @@ -1041,35 +1294,37 @@ void JSArray::setSubclassData(void* d) void JSArray::checkConsistency(ConsistencyCheckType type) { - ASSERT(m_storage); + ArrayStorage* storage = m_storage; + + 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 = storage->m_vector[i]) { + ASSERT(i < storage->m_length); if (type != DestructorConsistencyCheck) - value->type(); // Likely to crash if the object was deallocated. + 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 >= m_vectorLength); + ASSERT(index < storage->m_length); + ASSERT(index >= storage->m_vectorLength); ASSERT(index <= MAX_ARRAY_INDEX); ASSERT(it->second); if (type != DestructorConsistencyCheck) - it->second->type(); // Likely to crash if the object was deallocated. + it->second.isUndefined(); // Likely to crash if the object was deallocated. } } }