Revert "Imported WebKit commit 0dc6cd75e1d4836eaffbb520be96fac4847cc9d2 (http://svn.webkit.org/repository/webkit/trunk@131300)"

This reverts commit 5466563f4b5b6b86523e3f89bb7f77e5b5270c78.

Caused OOM issues on some CI machines :(

1 files changed, 328 insertions, 586 deletions

diff --git a/Source/JavaScriptCore/runtime/JSArray.cpp b/Source/JavaScriptCore/runtime/JSArray.cpp
index 7028c3b95..8398ae77d 100644
--- a/Source/JavaScriptCore/runtime/JSArray.cpp
+++ b/Source/JavaScriptCore/runtime/JSArray.cpp
@@ -44,6 +44,8 @@ using namespace WTF;
 
 namespace JSC {
 
+
+ASSERT_CLASS_FITS_IN_CELL(JSArray);
 ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
 
 const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
@@ -243,8 +245,8 @@ void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, Pro
     JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
 }
 
-// This method makes room in the vector, but leaves the new space for count slots uncleared.
-bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, bool addToFront, unsigned count)
+// This method makes room in the vector, but leaves the new space uncleared.
+bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
 {
     ArrayStorage* storage = ensureArrayStorage(globalData);
     Butterfly* butterfly = storage->butterfly();
@@ -252,7 +254,7 @@ bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, bool addToFront, un
     unsigned propertySize = structure()->outOfLineSize();
 
     // If not, we should have handled this on the fast path.
-    ASSERT(!addToFront || count > storage->m_indexBias);
+    ASSERT(count > storage->m_indexBias);
 
     // Step 1:
     // Gather 4 key metrics:
@@ -276,7 +278,7 @@ bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, bool addToFront, un
     unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);
 
     // Step 2:
-    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
+    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing on.
 
     void* newAllocBase = 0;
     unsigned newStorageCapacity;
@@ -295,48 +297,36 @@ bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, bool addToFront, un
     // Work out where we're going to move things to.
 
     // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
-    // If we're adding to the end, we'll add all the new space to the end.
     // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
     // If it did, we calculate the amount that will remain based on an atomic decay - leave the
     // vector with half the post-capacity it had previously.
     unsigned postCapacity = 0;
-    if (!addToFront)
-        postCapacity = max(newStorageCapacity - requiredVectorLength, count);
-    else if (length < storage->vectorLength()) {
+    if (length < storage->vectorLength()) {
         // Atomic decay, + the post-capacity cannot be greater than what is available.
         postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
         // If we're moving contents within the same allocation, the post-capacity is being reduced.
         ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length);
     }
-
+    
     unsigned newVectorLength = requiredVectorLength + postCapacity;
     unsigned newIndexBias = newStorageCapacity - newVectorLength;
 
     Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
-
-    if (addToFront) {
-        ASSERT(count + usedVectorLength <= newVectorLength);
-        memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
-        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
-    } else if ((newAllocBase != butterfly->base(structure())) || (newIndexBias != storage->m_indexBias)) {
-        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
-        memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);
-
-        WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector;
-        for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
-            newVector[i].clear();
-    }
-
+    
+    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));
+    
     newButterfly->arrayStorage()->setVectorLength(newVectorLength);
     newButterfly->arrayStorage()->m_indexBias = newIndexBias;
-
+    
     m_butterfly = newButterfly;
 
     return true;
 }
 
-bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
+bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
 {
+    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
     unsigned length = storage->length();
 
     // If the length is read only then we enter sparse mode, so should enter the following 'if'.
@@ -353,7 +343,7 @@ bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, boo
             keys.reserveCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
             SparseArrayValueMap::const_iterator end = map->end();
             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
-                unsigned index = static_cast<unsigned>(it->key);
+                unsigned index = static_cast<unsigned>(it->first);
                 if (index < length && index >= newLength)
                     keys.append(index);
             }
@@ -368,7 +358,7 @@ bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, boo
                     unsigned index = keys[--i];
                     SparseArrayValueMap::iterator it = map->find(index);
                     ASSERT(it != map->notFound());
-                    if (it->value.attributes & DontDelete) {
+                    if (it->second.attributes & DontDelete) {
                         storage->setLength(index + 1);
                         return reject(exec, throwException, "Unable to delete property.");
                     }
@@ -399,71 +389,12 @@ bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, boo
     return true;
 }
 
-bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
-{
-    switch (structure()->indexingType()) {
-    case ArrayClass:
-        if (!newLength)
-            return true;
-        if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
-            return setLengthWithArrayStorage(
-                exec, newLength, throwException,
-                convertContiguousToArrayStorage(exec->globalData()));
-        }
-        createInitialContiguous(exec->globalData(), newLength);
-        return true;
-        
-    case ArrayWithContiguous:
-        if (newLength == m_butterfly->publicLength())
-            return true;
-        if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
-            || (newLength >= MIN_SPARSE_ARRAY_INDEX
-                && !isDenseEnoughForVector(newLength, countElementsInContiguous(m_butterfly)))) {
-            return setLengthWithArrayStorage(
-                exec, newLength, throwException,
-                convertContiguousToArrayStorage(exec->globalData()));
-        }
-        if (newLength > m_butterfly->publicLength()) {
-            ensureContiguousLength(exec->globalData(), newLength);
-            return true;
-        }
-        for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
-            m_butterfly->contiguous()[i].clear();
-        m_butterfly->setPublicLength(newLength);
-        return true;
-        
-    case ArrayWithArrayStorage:
-    case ArrayWithSlowPutArrayStorage:
-        return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
-        
-    default:
-        CRASH();
-        return false;
-    }
-}
-
 JSValue JSArray::pop(ExecState* exec)
 {
     switch (structure()->indexingType()) {
     case ArrayClass:
         return jsUndefined();
         
-    case ArrayWithContiguous: {
-        unsigned length = m_butterfly->publicLength();
-        
-        if (!length--)
-            return jsUndefined();
-        
-        ASSERT(length < m_butterfly->vectorLength());
-        JSValue value = m_butterfly->contiguous()[length].get();
-        if (value) {
-            m_butterfly->contiguous()[length].clear();
-            m_butterfly->setPublicLength(length);
-            return value;
-        }
-        break;
-    }
-        
     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
         ArrayStorage* storage = m_butterfly->arrayStorage();
     
@@ -487,28 +418,26 @@ JSValue JSArray::pop(ExecState* exec)
                 return element;
             }
         }
-        break;
+
+        // Let element be the result of calling the [[Get]] internal method of O with argument indx.
+        JSValue element = get(exec, index);
+        if (exec->hadException())
+            return jsUndefined();
+        // Call the [[Delete]] internal method of O with arguments indx and true.
+        if (!deletePropertyByIndex(this, exec, index)) {
+            throwTypeError(exec, "Unable to delete property.");
+            return jsUndefined();
+        }
+        // Call the [[Put]] internal method of O with arguments "length", indx, and true.
+        setLength(exec, index, true);
+        // Return element.
+        return element;
     }
         
     default:
-        CRASH();
+        ASSERT_NOT_REACHED();
         return JSValue();
     }
-    
-    unsigned index = getArrayLength() - 1;
-    // Let element be the result of calling the [[Get]] internal method of O with argument indx.
-    JSValue element = get(exec, index);
-    if (exec->hadException())
-        return jsUndefined();
-    // Call the [[Delete]] internal method of O with arguments indx and true.
-    if (!deletePropertyByIndex(this, exec, index)) {
-        throwTypeError(exec, "Unable to delete property.");
-        return jsUndefined();
-    }
-    // Call the [[Put]] internal method of O with arguments "length", indx, and true.
-    setLength(exec, index, true);
-    // Return element.
-    return element;
 }
 
 // Push & putIndex are almost identical, with two small differences.
@@ -522,26 +451,6 @@ void JSArray::push(ExecState* exec, JSValue value)
         break;
     }
         
-    case ArrayWithContiguous: {
-        unsigned length = m_butterfly->publicLength();
-        ASSERT(length <= m_butterfly->vectorLength());
-        if (length < m_butterfly->vectorLength()) {
-            m_butterfly->contiguous()[length].set(exec->globalData(), this, value);
-            m_butterfly->setPublicLength(length + 1);
-            return;
-        }
-        
-        if (length > MAX_ARRAY_INDEX) {
-            methodTable()->putByIndex(this, exec, length, value, true);
-            if (!exec->hadException())
-                throwError(exec, createRangeError(exec, "Invalid array length"));
-            return;
-        }
-        
-        putByIndexBeyondVectorLengthContiguousWithoutAttributes(exec, length, value);
-        return;
-    }
-        
     case ArrayWithSlowPutArrayStorage: {
         unsigned oldLength = length();
         if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
@@ -583,139 +492,59 @@ void JSArray::push(ExecState* exec, JSValue value)
     }
 }
 
-bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage)
+bool JSArray::shiftCount(ExecState* exec, unsigned count)
 {
+    ASSERT(count > 0);
+    
+    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
+    
     unsigned oldLength = storage->length();
     ASSERT(count <= oldLength);
     
     // If the array contains holes or is otherwise in an abnormal state,
     // use the generic algorithm in ArrayPrototype.
-    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType()))
+    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode())
         return false;
 
     if (!oldLength)
         return true;
     
-    unsigned length = oldLength - count;
-    
     storage->m_numValuesInVector -= count;
-    storage->setLength(length);
+    storage->setLength(oldLength - count);
     
     unsigned vectorLength = storage->vectorLength();
-    if (!vectorLength)
-        return true;
-    
-    if (startIndex >= vectorLength)
-        return true;
-    
-    if (startIndex + count > vectorLength)
-        count = vectorLength - startIndex;
-    
-    unsigned usedVectorLength = min(vectorLength, oldLength);
-    
-    vectorLength -= count;
-    storage->setVectorLength(vectorLength);
-    
     if (vectorLength) {
-        if (startIndex < usedVectorLength - (startIndex + count)) {
-            if (startIndex) {
-                memmove(
-                    storage->m_vector + count,
-                    storage->m_vector,
-                    sizeof(JSValue) * startIndex);
-            }
+        count = min(vectorLength, (unsigned)count);
+        
+        vectorLength -= count;
+        storage->setVectorLength(vectorLength);
+        
+        if (vectorLength) {
             m_butterfly = m_butterfly->shift(structure(), count);
             storage = m_butterfly->arrayStorage();
             storage->m_indexBias += count;
-        } else {
-            memmove(
-                storage->m_vector + startIndex,
-                storage->m_vector + startIndex + count,
-                sizeof(JSValue) * (usedVectorLength - (startIndex + count)));
-            for (unsigned i = usedVectorLength - count; i < usedVectorLength; ++i)
-                storage->m_vector[i].clear();
         }
     }
     return true;
 }
 
-bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
-{
-    ASSERT(count > 0);
-    
-    switch (structure()->indexingType()) {
-    case ArrayClass:
-        return true;
-        
-    case ArrayWithContiguous: {
-        unsigned oldLength = m_butterfly->publicLength();
-        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(startIndex, count, convertContiguousToArrayStorage(exec->globalData()));
-        
-        unsigned end = oldLength - count;
-        for (unsigned i = startIndex; i < end; ++i) {
-            // 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.
-            JSValue v = m_butterfly->contiguous()[i + count].get();
-            if (UNLIKELY(!v)) {
-                // The purpose of this path is to ensure that we don't make the same
-                // mistake in the future: shiftCountWithArrayStorage() can't do anything
-                // about holes (at least for now), but it can detect them quickly. So
-                // we convert to array storage and then allow the array storage path to
-                // figure it out.
-                return shiftCountWithArrayStorage(startIndex, count, convertContiguousToArrayStorage(exec->globalData()));
-            }
-            // 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)
-            m_butterfly->contiguous()[i].clear();
-        
-        m_butterfly->setPublicLength(oldLength - count);
-        return true;
-    }
-        
-    case ArrayWithArrayStorage:
-    case ArrayWithSlowPutArrayStorage:
-        return shiftCountWithArrayStorage(startIndex, count, arrayStorage());
-        
-    default:
-        CRASH();
-        return false;
-    }
-}
-
 // Returns true if the unshift can be handled, false to fallback.    
-bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
+bool JSArray::unshiftCount(ExecState* exec, unsigned count)
 {
+    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
     unsigned length = storage->length();
 
-    ASSERT(startIndex <= length);
-
     // If the array contains holes or is otherwise in an abnormal state,
     // use the generic algorithm in ArrayPrototype.
-    if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType()))
+    if (length != storage->m_numValuesInVector || storage->inSparseMode())
         return false;
 
-    bool moveFront = !startIndex || startIndex < length / 2;
-
-    unsigned vectorLength = storage->vectorLength();
-
-    if (moveFront && storage->m_indexBias >= count) {
+    if (storage->m_indexBias >= count) {
         m_butterfly = storage->butterfly()->unshift(structure(), count);
         storage = m_butterfly->arrayStorage();
         storage->m_indexBias -= count;
-        storage->setVectorLength(vectorLength + count);
-    } else if (!moveFront && vectorLength - length >= count)
-        storage = storage->butterfly()->arrayStorage();
-    else if (unshiftCountSlowCase(exec->globalData(), moveFront, count))
+        storage->setVectorLength(storage->vectorLength() + count);
+    } else if (unshiftCountSlowCase(exec->globalData(), count))
         storage = arrayStorage();
     else {
         throwOutOfMemoryError(exec);
@@ -723,61 +552,11 @@ bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex,
     }
 
     WriteBarrier<Unknown>* vector = storage->m_vector;
-
-    if (startIndex) {
-        if (moveFront)
-            memmove(vector, vector + count, startIndex * sizeof(JSValue));
-        else if (length - startIndex)
-            memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
-    }
-
     for (unsigned i = 0; i < count; i++)
-        vector[i + startIndex].clear();
+        vector[i].clear();
     return true;
 }
 
-bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
-{
-    switch (structure()->indexingType()) {
-    case ArrayClass:
-        // We could handle this. But it shouldn't ever come up, so we won't.
-        return false;
-        
-    case ArrayWithContiguous: {
-        unsigned oldLength = m_butterfly->publicLength();
-        
-        // We may have to walk the entire array to do the unshift. We're willing to do so
-        // only if it's not horribly slow.
-        if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
-            return unshiftCountWithArrayStorage(exec, startIndex, count, convertContiguousToArrayStorage(exec->globalData()));
-        
-        ensureContiguousLength(exec->globalData(), oldLength + count);
-        
-        for (unsigned i = oldLength; i-- > startIndex;) {
-            JSValue v = m_butterfly->contiguous()[i].get();
-            if (UNLIKELY(!v))
-                return unshiftCountWithArrayStorage(exec, startIndex, count, convertContiguousToArrayStorage(exec->globalData()));
-            m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
-        }
-        
-        // NOTE: we're leaving being garbage in the part of the array that we shifted out
-        // of. This is fine because the caller is required to store over that area, and
-        // in contiguous mode storing into a hole is guaranteed to behave exactly the same
-        // as storing over an existing element.
-        
-        return true;
-    }
-        
-    case ArrayWithArrayStorage:
-    case ArrayWithSlowPutArrayStorage:
-        return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
-        
-    default:
-        CRASH();
-        return false;
-    }
-}
-
 static int compareNumbersForQSort(const void* a, const void* b)
 {
     double da = static_cast<const JSValue*>(a)->asNumber();
@@ -792,45 +571,6 @@ static int compareByStringPairForQSort(const void* a, const void* b)
     return codePointCompare(va->second, vb->second);
 }
 
-template<IndexingType indexingType>
-void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
-    ASSERT(indexingType == ArrayWithContiguous || indexingType == ArrayWithArrayStorage);
-    
-    unsigned lengthNotIncludingUndefined;
-    unsigned newRelevantLength;
-    compactForSorting<indexingType>(
-        lengthNotIncludingUndefined,
-        newRelevantLength);
-    
-    WriteBarrier<Unknown>* data = indexingData<indexingType>();
-    
-    if (indexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
-    
-    if (!lengthNotIncludingUndefined)
-        return;
-    
-    bool allValuesAreNumbers = true;
-    for (size_t i = 0; i < newRelevantLength; ++i) {
-        if (!data[i].isNumber()) {
-            allValuesAreNumbers = false;
-            break;
-        }
-    }
-    
-    if (!allValuesAreNumbers)
-        return sort(exec, compareFunction, callType, callData);
-    
-    // For numeric comparison, which is fast, qsort is faster than mergesort. We
-    // also don't require mergesort's stability, since there's no user visible
-    // side-effect from swapping the order of equal primitive values.
-    qsort(data, newRelevantLength, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
-    return;
-}
-
 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 {
     ASSERT(!inSparseIndexingMode());
@@ -839,98 +579,41 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal
     case ArrayClass:
         return;
         
-    case ArrayWithContiguous:
-        sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
-        return;
-
-    case ArrayWithArrayStorage:
-        sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
-        return;
-        
-    default:
-        CRASH();
-        return;
-    }
-}
-
-template<IndexingType indexingType>
-void JSArray::sortCompactedVector(ExecState* exec, WriteBarrier<Unknown>* begin, unsigned relevantLength)
-{
-    if (!relevantLength)
-        return;
-    
-    JSGlobalData& globalData = exec->globalData();
-
-    // 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.
+    case ArrayWithArrayStorage: {
+        unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
+        ArrayStorage* storage = m_butterfly->arrayStorage();
         
-    Vector<ValueStringPair> values(relevantLength);
-    if (!values.begin()) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
+        if (storage->m_sparseMap.get()) {
+            throwOutOfMemoryError(exec);
+            return;
+        }
         
-    Heap::heap(this)->pushTempSortVector(&values);
+        if (!lengthNotIncludingUndefined)
+            return;
         
-    bool isSortingPrimitiveValues = true;
-    for (size_t i = 0; i < relevantLength; i++) {
-        JSValue value = begin[i].get();
-        ASSERT(!value.isUndefined());
-        values[i].first = value;
-        isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
-    }
+        bool allValuesAreNumbers = true;
+        size_t size = storage->m_numValuesInVector;
+        for (size_t i = 0; i < size; ++i) {
+            if (!storage->m_vector[i].isNumber()) {
+                allValuesAreNumbers = false;
+                break;
+            }
+        }
         
-    // FIXME: The following loop continues to call toString on subsequent values even after
-    // a toString call raises an exception.
+        if (!allValuesAreNumbers)
+            return sort(exec, compareFunction, callType, callData);
         
-    for (size_t i = 0; i < relevantLength; i++)
-        values[i].second = values[i].first.toWTFStringInline(exec);
+        // For numeric comparison, which is fast, qsort is faster than mergesort. We
+        // also don't require mergesort's stability, since there's no user visible
+        // side-effect from swapping the order of equal primitive values.
+        qsort(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
         
-    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 ArrayWithContiguous:
-        ensureContiguousLength(globalData, relevantLength);
-        break;
-        
-    case ArrayWithArrayStorage:
-        if (arrayStorage()->vectorLength() < relevantLength) {
-            increaseVectorLength(exec->globalData(), relevantLength);
-            begin = arrayStorage()->m_vector;
-        }
-        if (arrayStorage()->length() < relevantLength)
-            arrayStorage()->setLength(relevantLength);
-        break;
-        
     default:
-        CRASH();
+        ASSERT_NOT_REACHED();
     }
-
-    for (size_t i = 0; i < relevantLength; i++)
-        begin[i].set(globalData, this, values[i].first);
-    
-    Heap::heap(this)->popTempSortVector(&values);
 }
 
 void JSArray::sort(ExecState* exec)
@@ -941,27 +624,78 @@ void JSArray::sort(ExecState* exec)
     case ArrayClass:
         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);
+        unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
         ArrayStorage* storage = m_butterfly->arrayStorage();
-        ASSERT(!storage->m_sparseMap);
+        if (storage->m_sparseMap.get()) {
+            throwOutOfMemoryError(exec);
+            return;
+        }
+        
+        if (!lengthNotIncludingUndefined)
+            return;
+        
+        // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
+        // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
+        // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
+        // random or otherwise changing results, effectively making compare function inconsistent.
+        
+        Vector<ValueStringPair> values(lengthNotIncludingUndefined);
+        if (!values.begin()) {
+            throwOutOfMemoryError(exec);
+            return;
+        }
+        
+        Heap::heap(this)->pushTempSortVector(&values);
+        
+        bool isSortingPrimitiveValues = true;
+        for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
+            JSValue value = storage->m_vector[i].get();
+            ASSERT(!value.isUndefined());
+            values[i].first = value;
+            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 < lengthNotIncludingUndefined; 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.
+        if (storage->vectorLength() < lengthNotIncludingUndefined) {
+            increaseVectorLength(exec->globalData(), lengthNotIncludingUndefined);
+            storage = m_butterfly->arrayStorage();
+        }
+        if (storage->length() < lengthNotIncludingUndefined)
+            storage->setLength(lengthNotIncludingUndefined);
+        
+        JSGlobalData& globalData = exec->globalData();
+        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
+            storage->m_vector[i].set(globalData, this, values[i].first);
+        
+        Heap::heap(this)->popTempSortVector(&values);
         
-        sortCompactedVector<ArrayWithArrayStorage>(
-            exec, storage->m_vector, lengthNotIncludingUndefined);
         return;
     }
         
@@ -1047,116 +781,122 @@ struct AVLTreeAbstractorForArrayCompare {
     static handle null() { return 0x7FFFFFFF; }
 };
 
-template<IndexingType indexingType>
-void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+void JSArray::sort(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()))
+    switch (structure()->indexingType()) {
+    case ArrayClass:
         return;
         
-    unsigned usedVectorLength = relevantLength<indexingType>();
-    unsigned nodeCount = usedVectorLength;
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
         
-    if (!nodeCount)
-        return;
+        // FIXME: This ignores exceptions raised in the compare function or in toNumber.
         
-    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);
+        // The maximum tree depth is compiled in - but the caller is clearly up to no good
+        // if a larger array is passed.
+        ASSERT(storage->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+        if (storage->length() > static_cast<unsigned>(std::numeric_limits<int>::max()))
+            return;
         
-    if (callType == CallTypeJS)
-        tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
+        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
+        unsigned nodeCount = usedVectorLength + (storage->m_sparseMap ? storage->m_sparseMap->size() : 0);
         
-    if (!tree.abstractor().m_nodes.begin()) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
+        if (!nodeCount)
+            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 = indexingData<indexingType>()[numDefined].get();
-        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 = indexingData<indexingType>()[i].get();
-        if (v) {
-            if (v.isUndefined())
-                ++numUndefined;
-            else {
-                tree.abstractor().m_nodes[numDefined].value = v;
+        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) {
+            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 = storage->m_vector[i].get();
+            if (v) {
+                if (v.isUndefined())
+                    ++numUndefined;
+                else {
+                    tree.abstractor().m_nodes[numDefined].value = v;
+                    tree.insert(numDefined);
+                    ++numDefined;
+                }
+            }
+        }
+        
+        unsigned newUsedVectorLength = numDefined + numUndefined;
+        
+        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            newUsedVectorLength += map->size();
+            if (newUsedVectorLength > storage->vectorLength()) {
+                // Check that it is possible to allocate an array large enough to hold all the entries.
+                if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(exec->globalData(), newUsedVectorLength)) {
+                    throwOutOfMemoryError(exec);
+                    return;
+                }
+                storage = m_butterfly->arrayStorage();
+            }
+            
+            SparseArrayValueMap::const_iterator end = map->end();
+            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
+                tree.abstractor().m_nodes[numDefined].value = it->second.getNonSparseMode();
                 tree.insert(numDefined);
                 ++numDefined;
             }
+            
+            deallocateSparseIndexMap();
         }
-    }
         
-    unsigned newUsedVectorLength = numDefined + numUndefined;
+        ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
         
-    // The array size may have changed. Figure out the new bounds.
-    unsigned newestUsedVectorLength = relevantLength<indexingType>();
+        // FIXME: If the compare function changed the length of the array, the following might be
+        // modifying the vector incorrectly.
         
-    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);
+        JSGlobalData& globalData = exec->globalData();
+        for (unsigned i = 0; i < numDefined; ++i) {
+            storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
+            ++iter;
+        }
         
-    // Copy the values back into m_storage.
-    AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
-    iter.start_iter_least(tree);
-    JSGlobalData& globalData = exec->globalData();
-    for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
-        indexingData<indexingType>()[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
-        ++iter;
-    }
-    // Put undefined values back in.
-    for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i)
-        indexingData<indexingType>()[i].setUndefined();
-
-    // Ensure that unused values in the vector are zeroed out.
-    for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i)
-        indexingData<indexingType>()[i].clear();
-    
-    if (hasArrayStorage(indexingType))
-        arrayStorage()->m_numValuesInVector = newUsedVectorLength;
-}
-
-void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
-{
-    ASSERT(!inSparseIndexingMode());
-    
-    switch (structure()->indexingType()) {
-    case ArrayClass:
-        return;
+        // Put undefined values back in.
+        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
+            storage->m_vector[i].setUndefined();
+        
+        // Ensure that unused values in the vector are zeroed out.
+        for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
+            storage->m_vector[i].clear();
+        
+        storage->m_numValuesInVector = newUsedVectorLength;
         
-    case ArrayWithContiguous:
-        sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
-        return;
-
-    case ArrayWithArrayStorage:
-        sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
         return;
+    }
         
     default:
         ASSERT_NOT_REACHED();
@@ -1165,127 +905,129 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
 
 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 {
-    unsigned i = 0;
-    unsigned vectorEnd;
-    WriteBarrier<Unknown>* vector;
-    
     switch (structure()->indexingType()) {
     case ArrayClass:
         return;
-        
-    case ArrayWithContiguous: {
-        vectorEnd = m_butterfly->publicLength();
-        vector = m_butterfly->contiguous();
-        break;
-    }
     
     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
         ArrayStorage* storage = m_butterfly->arrayStorage();
         
-        vector = storage->m_vector;
-        vectorEnd = min(storage->length(), storage->vectorLength());
-        break;
+        WriteBarrier<Unknown>* vector = storage->m_vector;
+        unsigned vectorEnd = min(storage->length(), storage->vectorLength());
+        unsigned i = 0;
+        for (; i < vectorEnd; ++i) {
+            WriteBarrier<Unknown>& v = vector[i];
+            if (!v)
+                break;
+            args.append(v.get());
+        }
+        
+        for (; i < storage->length(); ++i)
+            args.append(get(exec, i));
+        return;
     }
         
     default:
-        CRASH();
-        vector = 0;
-        vectorEnd = 0;
-        break;
-    }
-    
-    for (; i < vectorEnd; ++i) {
-        WriteBarrier<Unknown>& v = vector[i];
-        if (!v)
-            break;
-        args.append(v.get());
+        ASSERT_NOT_REACHED();
     }
-    
-    for (; i < length(); ++i)
-        args.append(get(exec, i));
 }
 
 void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
 {
-    unsigned i = 0;
-    WriteBarrier<Unknown>* vector;
-    unsigned vectorEnd;
-    
     ASSERT(length == this->length());
     switch (structure()->indexingType()) {
     case ArrayClass:
         return;
         
-    case ArrayWithContiguous: {
-        vector = m_butterfly->contiguous();
-        vectorEnd = m_butterfly->publicLength();
-        break;
-    }
-        
     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
         ArrayStorage* storage = m_butterfly->arrayStorage();
-        vector = storage->m_vector;
-        vectorEnd = min(length, storage->vectorLength());
-        break;
+        unsigned i = 0;
+        WriteBarrier<Unknown>* vector = storage->m_vector;
+        unsigned vectorEnd = min(length, storage->vectorLength());
+        for (; i < vectorEnd; ++i) {
+            WriteBarrier<Unknown>& v = vector[i];
+            if (!v)
+                break;
+            callFrame->setArgument(i, v.get());
+        }
+        
+        for (; i < length; ++i)
+            callFrame->setArgument(i, get(exec, i));
+        return;
     }
         
     default:
-        CRASH();
-        vector = 0;
-        vectorEnd = 0;
-        break;
-    }
-    
-    for (; i < vectorEnd; ++i) {
-        WriteBarrier<Unknown>& v = vector[i];
-        if (!v)
-            break;
-        callFrame->setArgument(i, v.get());
+        ASSERT_NOT_REACHED();
     }
-    
-    for (; i < length; ++i)
-        callFrame->setArgument(i, get(exec, i));
 }
 
-template<IndexingType indexingType>
-void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
+unsigned JSArray::compactForSorting(JSGlobalData& globalData)
 {
     ASSERT(!inSparseIndexingMode());
-    ASSERT(indexingType == structure()->indexingType());
 
-    unsigned myRelevantLength = relevantLength<indexingType>();
-    
-    numDefined = 0;
-    unsigned numUndefined = 0;
+    switch (structure()->indexingType()) {
+    case ArrayClass:
+        return 0;
+
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
         
-    for (; numDefined < myRelevantLength; ++numDefined) {
-        JSValue v = indexingData<indexingType>()[numDefined].get();
-        if (!v || v.isUndefined())
-            break;
-    }
+        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
         
-    for (unsigned i = numDefined; i < myRelevantLength; ++i) {
-        JSValue v = indexingData<indexingType>()[i].get();
-        if (v) {
-            if (v.isUndefined())
-                ++numUndefined;
-            else
-                indexingData<indexingType>()[numDefined++].setWithoutWriteBarrier(v);
+        unsigned numDefined = 0;
+        unsigned numUndefined = 0;
+        
+        for (; numDefined < usedVectorLength; ++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].get();
+            if (v) {
+                if (v.isUndefined())
+                    ++numUndefined;
+                else
+                    storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
+            }
+        }
+        
+        unsigned newUsedVectorLength = numDefined + numUndefined;
+        
+        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            newUsedVectorLength += map->size();
+            if (newUsedVectorLength > storage->vectorLength()) {
+                // Check that it is possible to allocate an array large enough to hold all the entries - if not,
+                // exception is thrown by caller.
+                if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(globalData, newUsedVectorLength))
+                    return 0;
+                
+                storage = m_butterfly->arrayStorage();
+            }
+            
+            SparseArrayValueMap::const_iterator end = map->end();
+            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
+                storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.getNonSparseMode());
+            
+            deallocateSparseIndexMap();
+        }
+        
+        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
+            storage->m_vector[i].setUndefined();
+        for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
+            storage->m_vector[i].clear();
+        
+        storage->m_numValuesInVector = newUsedVectorLength;
+        
+        return numDefined;
     }
         
-    newRelevantLength = numDefined + numUndefined;
-    
-    if (hasArrayStorage(indexingType))
-        ASSERT(!arrayStorage()->m_sparseMap);
-    
-    for (unsigned i = numDefined; i < newRelevantLength; ++i)
-        indexingData<indexingType>()[i].setUndefined();
-    for (unsigned i = newRelevantLength; i < myRelevantLength; ++i)
-        indexingData<indexingType>()[i].clear();
-
-    if (hasArrayStorage(indexingType))
-        arrayStorage()->m_numValuesInVector = newRelevantLength;
+    default:
+        ASSERT_NOT_REACHED();
+        return 0;
+    }
 }
 
+
 } // namespace JSC