diff options
Diffstat (limited to 'Source/JavaScriptCore/runtime/JSArray.cpp')
| -rw-r--r-- | Source/JavaScriptCore/runtime/JSArray.cpp | 1017 |
1 files changed, 747 insertions, 270 deletions
diff --git a/Source/JavaScriptCore/runtime/JSArray.cpp b/Source/JavaScriptCore/runtime/JSArray.cpp index afdbe0de7..9007b5f7d 100644 --- a/Source/JavaScriptCore/runtime/JSArray.cpp +++ b/Source/JavaScriptCore/runtime/JSArray.cpp @@ -1,6 +1,6 @@ /* * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) - * Copyright (C) 2003, 2007, 2008, 2009, 2012, 2013, 2015 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) * @@ -26,16 +26,18 @@ #include "ArrayPrototype.h" #include "ButterflyInlines.h" #include "CachedCall.h" -#include "CodeBlock.h" #include "CopiedSpace.h" +#include "CopiedSpaceInlines.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> using namespace std; using namespace WTF; @@ -44,7 +46,7 @@ namespace JSC { STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray); -const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, CREATE_METHOD_TABLE(JSArray)}; +const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)}; Butterfly* createArrayButterflyInDictionaryIndexingMode( VM& vm, JSCell* intendedOwner, unsigned initialLength) @@ -107,12 +109,11 @@ bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName 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, ASCIILiteral("Invalid array length"))); + exec->vm().throwException(exec, createRangeError(exec, "Invalid array length")); return false; } // Based on SameValue check in 8.12.9, this is always okay. - // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case. if (newLen == array->length()) { if (descriptor.writablePresent()) array->setLengthWritable(exec, descriptor.writable()); @@ -159,10 +160,9 @@ bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName // 4. Else if P is an array index (15.4), then // a. Let index be ToUint32(P). - if (Optional<uint32_t> optionalIndex = parseIndex(propertyName)) { + unsigned index = propertyName.asIndex(); + if (index != PropertyName::NotAnIndex) { // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false. - uint32_t index = optionalIndex.value(); - // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case. 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. @@ -228,7 +228,7 @@ void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, Pro { JSArray* thisObject = jsCast<JSArray*>(object); - if (mode.includeDontEnumProperties()) + if (mode == IncludeDontEnumProperties) propertyNames.add(exec->propertyNames().length); JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode); @@ -239,8 +239,8 @@ bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count) { ArrayStorage* storage = ensureArrayStorage(vm); Butterfly* butterfly = storage->butterfly(); - unsigned propertyCapacity = structure(vm)->outOfLineCapacity(); - unsigned propertySize = structure(vm)->outOfLineSize(); + unsigned propertyCapacity = structure()->outOfLineCapacity(); + unsigned propertySize = structure()->outOfLineSize(); // If not, we should have handled this on the fast path. ASSERT(!addToFront || count > storage->m_indexBias); @@ -274,7 +274,7 @@ bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count) 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)); + newAllocBase = butterfly->base(structure()); newStorageCapacity = currentCapacity; } else { size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity)); @@ -298,7 +298,7 @@ bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count) // 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); + ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length); } unsigned newVectorLength = requiredVectorLength + postCapacity; @@ -310,7 +310,7 @@ bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count) 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)) { + } else if ((newAllocBase != butterfly->base(structure())) || (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); @@ -379,7 +379,7 @@ bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, boo unsigned usedVectorLength = min(length, storage->vectorLength()); for (unsigned i = newLength; i < usedVectorLength; ++i) { WriteBarrier<Unknown>& valueSlot = storage->m_vector[i]; - bool hadValue = !!valueSlot; + bool hadValue = valueSlot; valueSlot.clear(); storage->m_numValuesInVector -= hadValue; } @@ -392,8 +392,7 @@ bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, boo bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException) { - Butterfly* butterfly = m_butterfly.get(this); - switch (indexingType()) { + switch (structure()->indexingType()) { case ArrayClass: if (!newLength) return true; @@ -408,8 +407,8 @@ bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException case ArrayWithUndecided: case ArrayWithInt32: case ArrayWithDouble: - case ArrayWithContiguous: { - if (newLength == butterfly->publicLength()) + 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 @@ -418,28 +417,19 @@ bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException exec, newLength, throwException, ensureArrayStorage(exec->vm())); } - if (newLength > butterfly->publicLength()) { + if (newLength > m_butterfly->publicLength()) { ensureLength(exec->vm(), newLength); return true; } - - unsigned lengthToClear = butterfly->publicLength() - newLength; - unsigned costToAllocateNewButterfly = 64; // a heuristic. - if (lengthToClear > newLength && lengthToClear > costToAllocateNewButterfly) { - reallocateAndShrinkButterfly(exec->vm(), newLength); - return true; - } - - if (indexingType() == ArrayWithDouble) { - for (unsigned i = butterfly->publicLength(); i-- > newLength;) - butterfly->contiguousDouble()[i] = PNaN; + if (structure()->indexingType() == ArrayWithDouble) { + for (unsigned i = m_butterfly->publicLength(); i-- > newLength;) + m_butterfly->contiguousDouble()[i] = QNaN; } else { - for (unsigned i = butterfly->publicLength(); i-- > newLength;) - butterfly->contiguous()[i].clear(); + for (unsigned i = m_butterfly->publicLength(); i-- > newLength;) + m_butterfly->contiguous()[i].clear(); } - butterfly->setPublicLength(newLength); + m_butterfly->setPublicLength(newLength); return true; - } case ArrayWithArrayStorage: case ArrayWithSlowPutArrayStorage: @@ -453,53 +443,51 @@ bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException JSValue JSArray::pop(ExecState* exec) { - Butterfly* butterfly = m_butterfly.get(this); - - switch (indexingType()) { + switch (structure()->indexingType()) { case ArrayClass: return jsUndefined(); case ArrayWithUndecided: - if (!butterfly->publicLength()) + 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 = butterfly->publicLength(); + unsigned length = m_butterfly->publicLength(); if (!length--) return jsUndefined(); - RELEASE_ASSERT(length < butterfly->vectorLength()); - JSValue value = butterfly->contiguous()[length].get(); + RELEASE_ASSERT(length < m_butterfly->vectorLength()); + JSValue value = m_butterfly->contiguous()[length].get(); if (value) { - butterfly->contiguous()[length].clear(); - butterfly->setPublicLength(length); + m_butterfly->contiguous()[length].clear(); + m_butterfly->setPublicLength(length); return value; } break; } case ArrayWithDouble: { - unsigned length = butterfly->publicLength(); + unsigned length = m_butterfly->publicLength(); if (!length--) return jsUndefined(); - RELEASE_ASSERT(length < butterfly->vectorLength()); - double value = butterfly->contiguousDouble()[length]; + RELEASE_ASSERT(length < m_butterfly->vectorLength()); + double value = m_butterfly->contiguousDouble()[length]; if (value == value) { - butterfly->contiguousDouble()[length] = PNaN; - butterfly->setPublicLength(length); + m_butterfly->contiguousDouble()[length] = QNaN; + m_butterfly->setPublicLength(length); return JSValue(JSValue::EncodeAsDouble, value); } break; } case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { - ArrayStorage* storage = butterfly->arrayStorage(); + ArrayStorage* storage = m_butterfly->arrayStorage(); unsigned length = storage->length(); if (!length) { @@ -536,7 +524,7 @@ JSValue JSArray::pop(ExecState* exec) return jsUndefined(); // Call the [[Delete]] internal method of O with arguments indx and true. if (!deletePropertyByIndex(this, exec, index)) { - throwTypeError(exec, ASCIILiteral("Unable to delete property.")); + throwTypeError(exec, "Unable to delete property."); return jsUndefined(); } // Call the [[Put]] internal method of O with arguments "length", indx, and true. @@ -550,9 +538,7 @@ JSValue JSArray::pop(ExecState* exec) // - pushing to an array of length 2^32-1 stores the property, but throws a range error. void JSArray::push(ExecState* exec, JSValue value) { - Butterfly* butterfly = m_butterfly.get(this); - - switch (indexingType()) { + switch (structure()->indexingType()) { case ArrayClass: { createInitialUndecided(exec->vm(), 0); FALLTHROUGH; @@ -571,18 +557,18 @@ void JSArray::push(ExecState* exec, JSValue value) return; } - unsigned length = butterfly->publicLength(); - ASSERT(length <= butterfly->vectorLength()); - if (length < butterfly->vectorLength()) { - butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value); - butterfly->setPublicLength(length + 1); + 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); + methodTable()->putByIndex(this, exec, length, value, true); if (!exec->hadException()) - exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + exec->vm().throwException(exec, createRangeError(exec, "Invalid array length")); return; } @@ -591,18 +577,18 @@ void JSArray::push(ExecState* exec, JSValue value) } case ArrayWithContiguous: { - unsigned length = butterfly->publicLength(); - ASSERT(length <= butterfly->vectorLength()); - if (length < butterfly->vectorLength()) { - butterfly->contiguous()[length].set(exec->vm(), this, value); - butterfly->setPublicLength(length + 1); + 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); + methodTable()->putByIndex(this, exec, length, value, true); if (!exec->hadException()) - exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + exec->vm().throwException(exec, createRangeError(exec, "Invalid array length")); return; } @@ -623,18 +609,18 @@ void JSArray::push(ExecState* exec, JSValue value) return; } - unsigned length = butterfly->publicLength(); - ASSERT(length <= butterfly->vectorLength()); - if (length < butterfly->vectorLength()) { - butterfly->contiguousDouble()[length] = valueAsDouble; - butterfly->setPublicLength(length + 1); + 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); + methodTable()->putByIndex(this, exec, length, value, true); if (!exec->hadException()) - exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); + exec->vm().throwException(exec, createRangeError(exec, "Invalid array length")); return; } @@ -653,7 +639,7 @@ void JSArray::push(ExecState* exec, JSValue value) } case ArrayWithArrayStorage: { - ArrayStorage* storage = butterfly->arrayStorage(); + ArrayStorage* storage = m_butterfly->arrayStorage(); // Fast case - push within vector, always update m_length & m_numValuesInVector. unsigned length = storage->length(); @@ -666,10 +652,10 @@ void JSArray::push(ExecState* exec, JSValue value) // 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); + methodTable()->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, ASCIILiteral("Invalid array length"))); + exec->vm().throwException(exec, createRangeError(exec, "Invalid array length")); return; } @@ -683,80 +669,15 @@ void JSArray::push(ExecState* exec, JSValue value) } } -JSArray* JSArray::fastSlice(ExecState& exec, unsigned startIndex, unsigned count) -{ - auto arrayType = indexingType(); - switch (arrayType) { - case ArrayWithDouble: - case ArrayWithInt32: - case ArrayWithContiguous: { - VM& vm = exec.vm(); - if (count >= MIN_SPARSE_ARRAY_INDEX || structure(vm)->holesMustForwardToPrototype(vm)) - return nullptr; - - Structure* resultStructure = exec.lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(arrayType); - JSArray* resultArray = JSArray::tryCreateUninitialized(vm, resultStructure, count); - if (!resultArray) - return nullptr; - - auto& resultButterfly = *resultArray->butterfly(); - if (arrayType == ArrayWithDouble) - memcpy(resultButterfly.contiguousDouble().data(), m_butterfly.get(this)->contiguousDouble().data() + startIndex, sizeof(JSValue) * count); - else - memcpy(resultButterfly.contiguous().data(), m_butterfly.get(this)->contiguous().data() + startIndex, sizeof(JSValue) * count); - resultButterfly.setPublicLength(count); - - return resultArray; - } - default: - return nullptr; - } -} - -EncodedJSValue JSArray::fastConcatWith(ExecState& exec, JSArray& otherArray) -{ - auto newArrayType = indexingType(); - - VM& vm = exec.vm(); - ASSERT(newArrayType == fastConcatType(vm, *this, otherArray)); - - unsigned thisArraySize = m_butterfly.get(this)->publicLength(); - unsigned otherArraySize = otherArray.m_butterfly.get(this)->publicLength(); - ASSERT(thisArraySize + otherArraySize < MIN_SPARSE_ARRAY_INDEX); - - Structure* resultStructure = exec.lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(newArrayType); - JSArray* resultArray = JSArray::tryCreateUninitialized(vm, resultStructure, thisArraySize + otherArraySize); - if (!resultArray) - return JSValue::encode(throwOutOfMemoryError(&exec)); - - auto& resultButterfly = *resultArray->butterfly(); - auto& otherButterfly = *otherArray.butterfly(); - if (newArrayType == ArrayWithDouble) { - auto buffer = resultButterfly.contiguousDouble().data(); - memcpy(buffer, m_butterfly.get(this)->contiguousDouble().data(), sizeof(JSValue) * thisArraySize); - memcpy(buffer + thisArraySize, otherButterfly.contiguousDouble().data(), sizeof(JSValue) * otherArraySize); - } else { - auto buffer = resultButterfly.contiguous().data(); - memcpy(buffer, m_butterfly.get(this)->contiguous().data(), sizeof(JSValue) * thisArraySize); - memcpy(buffer + thisArraySize, otherButterfly.contiguous().data(), sizeof(JSValue) * otherArraySize); - } - - resultButterfly.setPublicLength(thisArraySize + otherArraySize); - return JSValue::encode(resultArray); -} - -bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage) +bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage) { 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)) - || hasSparseMap() - || shouldUseSlowPut(indexingType())) { + if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType())) return false; - } if (!oldLength) return true; @@ -790,29 +711,16 @@ bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned c // 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); - } + 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. - Butterfly* butterfly = m_butterfly.get(this)->shift(structure(), count); - m_butterfly.setWithoutBarrier(butterfly); - storage = butterfly->arrayStorage(); + 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, @@ -821,22 +729,10 @@ bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned c } 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); - } + 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) @@ -850,14 +746,11 @@ bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned c return true; } -bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count) +bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count) { - VM& vm = exec->vm(); RELEASE_ASSERT(count > 0); - - Butterfly* butterfly = m_butterfly.get(this); - switch (indexingType()) { + switch (structure()->indexingType()) { case ArrayClass: return true; @@ -867,79 +760,78 @@ bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startInde case ArrayWithInt32: case ArrayWithContiguous: { - unsigned oldLength = butterfly->publicLength(); + 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)); + return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->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 = butterfly->contiguous()[i + count].get(); - if (UNLIKELY(!v)) { - startIndex = i; - return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm)); - } - butterfly->contiguous()[i].setWithoutWriteBarrier(v); - } - } else { - memmove(butterfly->contiguous().data() + startIndex, - butterfly->contiguous().data() + startIndex + count, - sizeof(JSValue) * (end - startIndex)); + for (unsigned i = startIndex; i < end; ++i) { + JSValue v = m_butterfly->contiguous()[i + count].get(); + if (UNLIKELY(!v)) + return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm())); } + for (unsigned i = startIndex; i < end; ++i) { + JSValue v = m_butterfly->contiguous()[i + count].get(); + ASSERT(v); + // No need for a barrier since we're just moving data around in the same vector. + // This is in line with our standing assumption that we won't have a deletion + // barrier. + m_butterfly->contiguous()[i].setWithoutWriteBarrier(v); + } for (unsigned i = end; i < oldLength; ++i) - butterfly->contiguous()[i].clear(); + m_butterfly->contiguous()[i].clear(); - butterfly->setPublicLength(oldLength - count); + m_butterfly->setPublicLength(oldLength - count); return true; } case ArrayWithDouble: { - unsigned oldLength = butterfly->publicLength(); + 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)); + return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->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 = butterfly->contiguousDouble()[i + count]; - if (UNLIKELY(v != v)) { - startIndex = i; - return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm)); - } - butterfly->contiguousDouble()[i] = v; - } - } else { - memmove(butterfly->contiguousDouble().data() + startIndex, - butterfly->contiguousDouble().data() + startIndex + count, - sizeof(JSValue) * (end - startIndex)); + for (unsigned i = startIndex; i < end; ++i) { + double v = m_butterfly->contiguousDouble()[i + count]; + if (UNLIKELY(v != v)) + return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm())); + } + + for (unsigned i = startIndex; i < end; ++i) { + double v = m_butterfly->contiguousDouble()[i + count]; + ASSERT(v == v); + // No need for a barrier since we're just moving data around in the same vector. + // This is in line with our standing assumption that we won't have a deletion + // barrier. + m_butterfly->contiguousDouble()[i] = v; } for (unsigned i = end; i < oldLength; ++i) - butterfly->contiguousDouble()[i] = PNaN; + m_butterfly->contiguousDouble()[i] = QNaN; - butterfly->setPublicLength(oldLength - count); + m_butterfly->setPublicLength(oldLength - count); return true; } case ArrayWithArrayStorage: case ArrayWithSlowPutArrayStorage: - return shiftCountWithArrayStorage(vm, startIndex, count, arrayStorage()); + return shiftCountWithArrayStorage(startIndex, count, arrayStorage()); default: CRASH(); @@ -956,7 +848,7 @@ bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, // 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())) + if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType())) return false; bool moveFront = !startIndex || startIndex < length / 2; @@ -994,9 +886,7 @@ bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count) { - Butterfly* butterfly = m_butterfly.get(this); - - switch (indexingType()) { + switch (structure()->indexingType()) { case ArrayClass: case ArrayWithUndecided: // We could handle this. But it shouldn't ever come up, so we won't. @@ -1004,7 +894,7 @@ bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startInd case ArrayWithInt32: case ArrayWithContiguous: { - unsigned oldLength = butterfly->publicLength(); + 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. @@ -1012,20 +902,19 @@ bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startInd return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); ensureLength(exec->vm(), oldLength + count); - butterfly = m_butterfly.get(this); // 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 = butterfly->contiguous()[i].get(); + JSValue v = m_butterfly->contiguous()[i].get(); if (UNLIKELY(!v)) return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); } for (unsigned i = oldLength; i-- > startIndex;) { - JSValue v = butterfly->contiguous()[i].get(); + JSValue v = m_butterfly->contiguous()[i].get(); ASSERT(v); - butterfly->contiguous()[i + count].setWithoutWriteBarrier(v); + m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v); } // NOTE: we're leaving being garbage in the part of the array that we shifted out @@ -1037,7 +926,7 @@ bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startInd } case ArrayWithDouble: { - unsigned oldLength = butterfly->publicLength(); + 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. @@ -1045,20 +934,19 @@ bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startInd return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); ensureLength(exec->vm(), oldLength + count); - butterfly = m_butterfly.get(this); // 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 = butterfly->contiguousDouble()[i]; + double v = m_butterfly->contiguousDouble()[i]; if (UNLIKELY(v != v)) return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); } for (unsigned i = oldLength; i-- > startIndex;) { - double v = butterfly->contiguousDouble()[i]; + double v = m_butterfly->contiguousDouble()[i]; ASSERT(v == v); - butterfly->contiguousDouble()[i + count] = v; + m_butterfly->contiguousDouble()[i + count] = v; } // NOTE: we're leaving being garbage in the part of the array that we shifted out @@ -1079,15 +967,526 @@ bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startInd } } +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; +} + +static int compareNumbersForQSortWithDouble(const void* a, const void* b) +{ + 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)->asNumber(); + double db = static_cast<const JSValue*>(b)->asNumber(); + return (da > db) - (da < db); +} + +static int compareByStringPairForQSort(const void* a, const void* b) +{ + const ValueStringPair* va = static_cast<const ValueStringPair*>(a); + const ValueStringPair* vb = static_cast<const ValueStringPair*>(b); + return codePointCompare(va->second, vb->second); +} + +template<IndexingType indexingType> +void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +{ + ASSERT(indexingType == ArrayWithInt32 || indexingType == ArrayWithDouble || indexingType == ArrayWithContiguous || indexingType == ArrayWithArrayStorage); + + unsigned lengthNotIncludingUndefined; + unsigned newRelevantLength; + compactForSorting<indexingType>( + lengthNotIncludingUndefined, + newRelevantLength); + + ContiguousJSValues data = indexingData<indexingType>(); + + if (indexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) { + throwOutOfMemoryError(exec); + return; + } + + if (!lengthNotIncludingUndefined) + return; + + bool allValuesAreNumbers = true; + switch (indexingType) { + 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. + int (*compare)(const void*, const void*); + switch (indexingType) { + 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::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +{ + ASSERT(!inSparseIndexingMode()); + + switch (structure()->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; + } +} + +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 indexingType, 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, 0, UnsafeVectorOverflow> values(relevantLength); + if (!values.begin()) { + throwOutOfMemoryError(exec); + return; + } + + Heap::heap(this)->pushTempSortVector(&values); + + bool isSortingPrimitiveValues = true; + + for (size_t i = 0; i < relevantLength; i++) { + JSValue value = ContiguousTypeAccessor<indexingType>::getAsValue(data, i); + ASSERT(indexingType != ArrayWithInt32 || value.isInt32()); + ASSERT(!value.isUndefined()); + values[i].first = value; + if (indexingType != ArrayWithDouble && indexingType != ArrayWithInt32) + isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive(); + } + + // FIXME: The following loop continues to call toString on subsequent values even after + // a toString call raises an exception. + + for (size_t i = 0; i < 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) + 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 (indexingType) { + case ArrayWithInt32: + case ArrayWithDouble: + case ArrayWithContiguous: + ensureLength(vm, relevantLength); + break; + + case ArrayWithArrayStorage: + if (arrayStorage()->vectorLength() < relevantLength) { + increaseVectorLength(exec->vm(), relevantLength); + ContiguousTypeAccessor<indexingType>::replaceDataReference(&data, arrayStorage()->vector()); + } + if (arrayStorage()->length() < relevantLength) + arrayStorage()->setLength(relevantLength); + break; + + default: + CRASH(); + } + + for (size_t i = 0; i < relevantLength; i++) + ContiguousTypeAccessor<indexingType>::setWithValue(vm, this, data, i, values[i].first); + + Heap::heap(this)->popTempSortVector(&values); +} + +void JSArray::sort(ExecState* exec) +{ + ASSERT(!inSparseIndexingMode()); + + switch (structure()->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 { + JSValue value; + + // Child pointers. The high bit of gt is robbed and used as the + // balance factor sign. The high bit of lt is robbed and used as + // the magnitude of the balance factor. + int32_t gt; + int32_t lt; +}; + +struct AVLTreeAbstractorForArrayCompare { + typedef int32_t handle; // Handle is an index into m_nodes vector. + typedef JSValue key; + typedef int32_t size; + + Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes; + ExecState* m_exec; + JSValue m_compareFunction; + CallType m_compareCallType; + const CallData* m_compareCallData; + OwnPtr<CachedCall> m_cachedCall; + + handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; } + void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; } + handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; } + void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; } + + int get_balance_factor(handle h) + { + if (m_nodes[h].gt & 0x80000000) + return -1; + return static_cast<unsigned>(m_nodes[h].lt) >> 31; + } + + void set_balance_factor(handle h, int bf) + { + if (bf == 0) { + m_nodes[h].lt &= 0x7FFFFFFF; + m_nodes[h].gt &= 0x7FFFFFFF; + } else { + m_nodes[h].lt |= 0x80000000; + if (bf < 0) + m_nodes[h].gt |= 0x80000000; + else + m_nodes[h].gt &= 0x7FFFFFFF; + } + } + + int compare_key_key(key va, key vb) + { + ASSERT(!va.isUndefined()); + ASSERT(!vb.isUndefined()); + + if (m_exec->hadException()) + return 1; + + double compareResult; + if (m_cachedCall) { + m_cachedCall->setThis(jsUndefined()); + m_cachedCall->setArgument(0, va); + m_cachedCall->setArgument(1, vb); + 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, jsUndefined(), arguments).toNumber(m_exec); + } + return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. + } + + int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); } + int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); } + + static handle null() { return 0x7FFFFFFF; } +}; + +template<IndexingType indexingType> +void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +{ + ASSERT(!inSparseIndexingMode()); + ASSERT(indexingType == structure()->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_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max())); + if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max())) + return; + + unsigned usedVectorLength = relevantLength<indexingType>(); + unsigned nodeCount = usedVectorLength; + + if (!nodeCount) + return; + + AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items + tree.abstractor().m_exec = exec; + tree.abstractor().m_compareFunction = compareFunction; + tree.abstractor().m_compareCallType = callType; + tree.abstractor().m_compareCallData = &callData; + tree.abstractor().m_nodes.grow(nodeCount); + + if (callType == CallTypeJS) + 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) { + 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) { + if (i >= m_butterfly->vectorLength()) + break; + JSValue v = getHolyIndexQuickly(i); + if (v) { + if (v.isUndefined()) + ++numUndefined; + else { + tree.abstractor().m_nodes[numDefined].value = v; + tree.insert(numDefined); + ++numDefined; + } + } + } + + unsigned newUsedVectorLength = numDefined + numUndefined; + + // 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); + VM& vm = exec->vm(); + for (unsigned i = 0; i < elementsToExtractThreshold; ++i) { + ASSERT(i < butterfly()->vectorLength()); + if (structure()->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. + switch (structure()->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 = undefinedElementsThreshold; i < clearElementsThreshold; ++i) { + ASSERT(i < butterfly()->vectorLength()); + if (structure()->indexingType() == ArrayWithDouble) + butterfly()->contiguousDouble()[i] = QNaN; + else + currentIndexingData()[i].clear(); + } + + if (hasArrayStorage(structure()->indexingType())) + arrayStorage()->m_numValuesInVector = newUsedVectorLength; +} + +void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +{ + ASSERT(!inSparseIndexingMode()); + + switch (structure()->indexingType()) { + case ArrayClass: + case ArrayWithUndecided: + return; + + case ArrayWithInt32: + sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData); + return; + + case ArrayWithDouble: + sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData); + return; + + 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) { unsigned i = 0; unsigned vectorEnd; WriteBarrier<Unknown>* vector; - - Butterfly* butterfly = m_butterfly.get(this); - switch (indexingType()) { + switch (structure()->indexingType()) { case ArrayClass: return; @@ -1099,16 +1498,16 @@ void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) case ArrayWithInt32: case ArrayWithContiguous: { - vectorEnd = butterfly->publicLength(); - vector = butterfly->contiguous().data(); + vectorEnd = m_butterfly->publicLength(); + vector = m_butterfly->contiguous().data(); break; } case ArrayWithDouble: { vector = 0; vectorEnd = 0; - for (; i < butterfly->publicLength(); ++i) { - double v = butterfly->contiguousDouble()[i]; + for (; i < m_butterfly->publicLength(); ++i) { + double v = butterfly()->contiguousDouble()[i]; if (v != v) break; args.append(JSValue(JSValue::EncodeAsDouble, v)); @@ -1117,7 +1516,7 @@ void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) } case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { - ArrayStorage* storage = butterfly->arrayStorage(); + ArrayStorage* storage = m_butterfly->arrayStorage(); vector = storage->m_vector; vectorEnd = min(storage->length(), storage->vectorLength()); @@ -1126,11 +1525,9 @@ void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) default: CRASH(); -#if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE) vector = 0; vectorEnd = 0; break; -#endif } for (; i < vectorEnd; ++i) { @@ -1139,25 +1536,19 @@ void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) break; args.append(v.get()); } - - // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case. + for (; i < length(); ++i) args.append(get(exec, i)); } -void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest, unsigned offset, unsigned length) +void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length) { - unsigned i = offset; + unsigned i = 0; WriteBarrier<Unknown>* vector; unsigned vectorEnd; - length += offset; // We like to think of the length as being our length, rather than the output length. - - // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case. - ASSERT(length == this->length()); - - Butterfly* butterfly = m_butterfly.get(this); - switch (indexingType()) { + ASSERT(length == this->length()); + switch (structure()->indexingType()) { case ArrayClass: return; @@ -1169,26 +1560,26 @@ void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest, case ArrayWithInt32: case ArrayWithContiguous: { - vector = butterfly->contiguous().data(); - vectorEnd = butterfly->publicLength(); + vector = m_butterfly->contiguous().data(); + vectorEnd = m_butterfly->publicLength(); break; } case ArrayWithDouble: { vector = 0; vectorEnd = 0; - for (; i < butterfly->publicLength(); ++i) { - ASSERT(i < butterfly->vectorLength()); - double v = butterfly->contiguousDouble()[i]; + for (; i < m_butterfly->publicLength(); ++i) { + ASSERT(i < butterfly()->vectorLength()); + double v = m_butterfly->contiguousDouble()[i]; if (v != v) break; - exec->r(firstElementDest + i - offset) = JSValue(JSValue::EncodeAsDouble, v); + callFrame->setArgument(i, JSValue(JSValue::EncodeAsDouble, v)); } break; } case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { - ArrayStorage* storage = butterfly->arrayStorage(); + ArrayStorage* storage = m_butterfly->arrayStorage(); vector = storage->m_vector; vectorEnd = min(length, storage->vectorLength()); break; @@ -1196,25 +1587,111 @@ void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest, default: CRASH(); -#if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE) vector = 0; vectorEnd = 0; break; -#endif } for (; i < vectorEnd; ++i) { WriteBarrier<Unknown>& v = vector[i]; if (!v) break; - exec->r(firstElementDest + i - offset) = v.get(); + callFrame->setArgument(i, v.get()); } - for (; i < length; ++i) { - exec->r(firstElementDest + i - offset) = get(exec, i); - if (UNLIKELY(exec->vm().exception())) - return; + for (; i < length; ++i) + callFrame->setArgument(i, get(exec, i)); +} + +template<IndexingType indexingType> +void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength) +{ + ASSERT(!inSparseIndexingMode()); + ASSERT(indexingType == structure()->indexingType()); + + unsigned myRelevantLength = relevantLength<indexingType>(); + + numDefined = 0; + unsigned numUndefined = 0; + + for (; numDefined < myRelevantLength; ++numDefined) { + ASSERT(numDefined < m_butterfly->vectorLength()); + if (indexingType == ArrayWithInt32) { + JSValue v = m_butterfly->contiguousInt32()[numDefined].get(); + if (!v) + break; + ASSERT(v.isInt32()); + continue; + } + if (indexingType == ArrayWithDouble) { + double v = m_butterfly->contiguousDouble()[numDefined]; + if (v != v) + break; + continue; + } + JSValue v = indexingData<indexingType>()[numDefined].get(); + if (!v || v.isUndefined()) + break; } + + for (unsigned i = numDefined; i < myRelevantLength; ++i) { + ASSERT(i < m_butterfly->vectorLength()); + if (indexingType == 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 (indexingType == 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<indexingType>()[i].get(); + if (v) { + if (v.isUndefined()) + ++numUndefined; + else { + ASSERT(numDefined < m_butterfly->vectorLength()); + indexingData<indexingType>()[numDefined++].setWithoutWriteBarrier(v); + } + } + } + + newRelevantLength = numDefined + numUndefined; + + if (hasArrayStorage(indexingType)) + RELEASE_ASSERT(!arrayStorage()->m_sparseMap); + + switch (indexingType) { + case ArrayWithInt32: + case ArrayWithDouble: + RELEASE_ASSERT(numDefined == newRelevantLength); + break; + + default: + for (unsigned i = numDefined; i < newRelevantLength; ++i) { + ASSERT(i < m_butterfly->vectorLength()); + indexingData<indexingType>()[i].setUndefined(); + } + break; + } + for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) { + ASSERT(i < m_butterfly->vectorLength()); + if (indexingType == ArrayWithDouble) + m_butterfly->contiguousDouble()[i] = QNaN; + else + indexingData<indexingType>()[i].clear(); + } + + if (hasArrayStorage(indexingType)) + arrayStorage()->m_numValuesInVector = newRelevantLength; } } // namespace JSC |