Imported WebKit commit cf4f8fc6f19b0629f51860cb2d4b25e139d07e00 (http://svn.webkit.org/repository/webkit/trunk@131592)

New snapshot that includes the build fixes for Mac OS X 10.6 and earlier as well
as the previously cherry-picked changes

1 files changed, 586 insertions, 328 deletions

diff --git a/Source/JavaScriptCore/runtime/JSArray.cpp b/Source/JavaScriptCore/runtime/JSArray.cpp
index 8398ae77d..7028c3b95 100644
--- a/Source/JavaScriptCore/runtime/JSArray.cpp
+++ b/Source/JavaScriptCore/runtime/JSArray.cpp
@@ -44,8 +44,6 @@ 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)};
@@ -245,8 +243,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 uncleared.
-bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
+// 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)
 {
     ArrayStorage* storage = ensureArrayStorage(globalData);
     Butterfly* butterfly = storage->butterfly();
@@ -254,7 +252,7 @@ bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
     unsigned propertySize = structure()->outOfLineSize();
 
     // If not, we should have handled this on the fast path.
-    ASSERT(count > storage->m_indexBias);
+    ASSERT(!addToFront || count > storage->m_indexBias);
 
     // Step 1:
     // Gather 4 key metrics:
@@ -278,7 +276,7 @@ bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
     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 on.
+    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
 
     void* newAllocBase = 0;
     unsigned newStorageCapacity;
@@ -297,36 +295,48 @@ bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
     // 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 (length < storage->vectorLength()) {
+    if (!addToFront)
+        postCapacity = max(newStorageCapacity - requiredVectorLength, count);
+    else if (length < storage->vectorLength()) {
         // Atomic decay, + the post-capacity cannot be greater than what is available.
         postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
         // If we're moving contents within the same allocation, the post-capacity is being reduced.
         ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length);
     }
-    
+
     unsigned newVectorLength = requiredVectorLength + postCapacity;
     unsigned newIndexBias = newStorageCapacity - newVectorLength;
 
     Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
-    
-    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));
-    
+
+    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();
+    }
+
     newButterfly->arrayStorage()->setVectorLength(newVectorLength);
     newButterfly->arrayStorage()->m_indexBias = newIndexBias;
-    
+
     m_butterfly = newButterfly;
 
     return true;
 }
 
-bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
+bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
 {
-    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'.
@@ -343,7 +353,7 @@ bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException
             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->first);
+                unsigned index = static_cast<unsigned>(it->key);
                 if (index < length && index >= newLength)
                     keys.append(index);
             }
@@ -358,7 +368,7 @@ bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException
                     unsigned index = keys[--i];
                     SparseArrayValueMap::iterator it = map->find(index);
                     ASSERT(it != map->notFound());
-                    if (it->second.attributes & DontDelete) {
+                    if (it->value.attributes & DontDelete) {
                         storage->setLength(index + 1);
                         return reject(exec, throwException, "Unable to delete property.");
                     }
@@ -389,12 +399,71 @@ bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException
     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();
     
@@ -418,26 +487,28 @@ JSValue JSArray::pop(ExecState* exec)
                 return element;
             }
         }
-
-        // 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;
+        break;
     }
         
     default:
-        ASSERT_NOT_REACHED();
+        CRASH();
         return JSValue();
     }
+    
+    unsigned index = getArrayLength() - 1;
+    // Let element be the result of calling the [[Get]] internal method of O with argument indx.
+    JSValue element = get(exec, index);
+    if (exec->hadException())
+        return jsUndefined();
+    // Call the [[Delete]] internal method of O with arguments indx and true.
+    if (!deletePropertyByIndex(this, exec, index)) {
+        throwTypeError(exec, "Unable to delete property.");
+        return jsUndefined();
+    }
+    // Call the [[Put]] internal method of O with arguments "length", indx, and true.
+    setLength(exec, index, true);
+    // Return element.
+    return element;
 }
 
 // Push & putIndex are almost identical, with two small differences.
@@ -451,6 +522,26 @@ 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)) {
@@ -492,59 +583,139 @@ void JSArray::push(ExecState* exec, JSValue value)
     }
 }
 
-bool JSArray::shiftCount(ExecState* exec, unsigned count)
+bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage)
 {
-    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())
+    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType()))
         return false;
 
     if (!oldLength)
         return true;
     
+    unsigned length = oldLength - count;
+    
     storage->m_numValuesInVector -= count;
-    storage->setLength(oldLength - count);
+    storage->setLength(length);
     
     unsigned vectorLength = storage->vectorLength();
+    if (!vectorLength)
+        return true;
+    
+    if (startIndex >= vectorLength)
+        return true;
+    
+    if (startIndex + count > vectorLength)
+        count = vectorLength - startIndex;
+    
+    unsigned usedVectorLength = min(vectorLength, oldLength);
+    
+    vectorLength -= count;
+    storage->setVectorLength(vectorLength);
+    
     if (vectorLength) {
-        count = min(vectorLength, (unsigned)count);
-        
-        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);
+            }
             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::unshiftCount(ExecState* exec, unsigned count)
+bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
 {
-    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())
+    if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType()))
         return false;
 
-    if (storage->m_indexBias >= count) {
+    bool moveFront = !startIndex || startIndex < length / 2;
+
+    unsigned vectorLength = storage->vectorLength();
+
+    if (moveFront && storage->m_indexBias >= count) {
         m_butterfly = storage->butterfly()->unshift(structure(), count);
         storage = m_butterfly->arrayStorage();
         storage->m_indexBias -= count;
-        storage->setVectorLength(storage->vectorLength() + count);
-    } else if (unshiftCountSlowCase(exec->globalData(), count))
+        storage->setVectorLength(vectorLength + count);
+    } else if (!moveFront && vectorLength - length >= count)
+        storage = storage->butterfly()->arrayStorage();
+    else if (unshiftCountSlowCase(exec->globalData(), moveFront, count))
         storage = arrayStorage();
     else {
         throwOutOfMemoryError(exec);
@@ -552,11 +723,61 @@ bool JSArray::unshiftCount(ExecState* exec, unsigned count)
     }
 
     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].clear();
+        vector[i + startIndex].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();
@@ -571,6 +792,45 @@ 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());
@@ -579,123 +839,129 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal
     case ArrayClass:
         return;
         
-    case ArrayWithArrayStorage: {
-        unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
-        ArrayStorage* storage = m_butterfly->arrayStorage();
-        
-        if (storage->m_sparseMap.get()) {
-            throwOutOfMemoryError(exec);
-            return;
-        }
-        
-        if (!lengthNotIncludingUndefined)
-            return;
-        
-        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;
-            }
-        }
-        
-        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(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
-        
+    case ArrayWithContiguous:
+        sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+        return;
+
+    case ArrayWithArrayStorage:
+        sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
         return;
-    }
         
     default:
-        ASSERT_NOT_REACHED();
+        CRASH();
+        return;
     }
 }
 
-void JSArray::sort(ExecState* exec)
+template<IndexingType indexingType>
+void JSArray::sortCompactedVector(ExecState* exec, WriteBarrier<Unknown>* begin, unsigned relevantLength)
 {
-    ASSERT(!inSparseIndexingMode());
-    
-    switch (structure()->indexingType()) {
-    case ArrayClass:
+    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();
-        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;
-        }
+    Vector<ValueStringPair> values(relevantLength);
+    if (!values.begin()) {
+        throwOutOfMemoryError(exec);
+        return;
+    }
         
-        Heap::heap(this)->pushTempSortVector(&values);
+    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();
-        }
+    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();
+    }
         
-        // FIXME: The following loop continues to call toString on subsequent values even after
-        // a toString call raises an exception.
+    // 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);
+    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;
-        }
+    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).
+    // 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.
+    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;
         
-        // 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();
+    case ArrayWithArrayStorage:
+        if (arrayStorage()->vectorLength() < relevantLength) {
+            increaseVectorLength(exec->globalData(), relevantLength);
+            begin = arrayStorage()->m_vector;
         }
-        if (storage->length() < lengthNotIncludingUndefined)
-            storage->setLength(lengthNotIncludingUndefined);
+        if (arrayStorage()->length() < relevantLength)
+            arrayStorage()->setLength(relevantLength);
+        break;
+        
+    default:
+        CRASH();
+    }
+
+    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)
+{
+    ASSERT(!inSparseIndexingMode());
+    
+    switch (structure()->indexingType()) {
+    case ArrayClass:
+        return;
         
-        JSGlobalData& globalData = exec->globalData();
-        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
-            storage->m_vector[i].set(globalData, this, values[i].first);
+    case ArrayWithContiguous: {
+        unsigned lengthNotIncludingUndefined;
+        unsigned newRelevantLength;
+        compactForSorting<ArrayWithContiguous>(
+            lengthNotIncludingUndefined, newRelevantLength);
         
-        Heap::heap(this)->popTempSortVector(&values);
+        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->m_vector, lengthNotIncludingUndefined);
         return;
     }
         
@@ -781,122 +1047,116 @@ struct AVLTreeAbstractorForArrayCompare {
     static handle null() { return 0x7FFFFFFF; }
 };
 
-void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+template<IndexingType indexingType>
+void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 {
     ASSERT(!inSparseIndexingMode());
+    ASSERT(indexingType == structure()->indexingType());
     
-    switch (structure()->indexingType()) {
-    case ArrayClass:
-        return;
-        
-    case ArrayWithArrayStorage: {
-        ArrayStorage* storage = m_butterfly->arrayStorage();
-        
-        // FIXME: This ignores exceptions raised in the compare function or in toNumber.
+    // 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(storage->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
-        if (storage->length() > static_cast<unsigned>(std::numeric_limits<int>::max()))
-            return;
-        
-        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
-        unsigned nodeCount = usedVectorLength + (storage->m_sparseMap ? storage->m_sparseMap->size() : 0);
-        
-        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);
+    // 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;
         
-        if (callType == CallTypeJS)
-            tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
+    unsigned usedVectorLength = relevantLength<indexingType>();
+    unsigned nodeCount = usedVectorLength;
         
-        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.
+    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);
         
-        unsigned numDefined = 0;
-        unsigned numUndefined = 0;
+    if (callType == CallTypeJS)
+        tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
         
-        // 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 (!tree.abstractor().m_nodes.begin()) {
+        throwOutOfMemoryError(exec);
+        return;
+    }
         
-        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();
+    // 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;
                 tree.insert(numDefined);
                 ++numDefined;
             }
-            
-            deallocateSparseIndexMap();
         }
+    }
         
-        ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
-        
-        // FIXME: If the compare function changed the length of the array, the following might be
-        // modifying the vector incorrectly.
+    unsigned newUsedVectorLength = numDefined + numUndefined;
         
-        // 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;
-        }
+    // The array size may have changed. Figure out the new bounds.
+    unsigned newestUsedVectorLength = relevantLength<indexingType>();
         
-        // Put undefined values back in.
-        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-            storage->m_vector[i].setUndefined();
+    unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
+    unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
+    unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
         
-        // 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;
+    // 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;
         
+    case ArrayWithContiguous:
+        sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+        return;
+
+    case ArrayWithArrayStorage:
+        sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
         return;
-    }
         
     default:
         ASSERT_NOT_REACHED();
@@ -905,129 +1165,127 @@ 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();
         
-        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;
+        vector = storage->m_vector;
+        vectorEnd = min(storage->length(), storage->vectorLength());
+        break;
     }
         
     default:
-        ASSERT_NOT_REACHED();
+        CRASH();
+        vector = 0;
+        vectorEnd = 0;
+        break;
     }
+    
+    for (; i < vectorEnd; ++i) {
+        WriteBarrier<Unknown>& v = vector[i];
+        if (!v)
+            break;
+        args.append(v.get());
+    }
+    
+    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();
-        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;
+        vector = storage->m_vector;
+        vectorEnd = min(length, storage->vectorLength());
+        break;
     }
         
     default:
-        ASSERT_NOT_REACHED();
+        CRASH();
+        vector = 0;
+        vectorEnd = 0;
+        break;
+    }
+    
+    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));
 }
 
-unsigned JSArray::compactForSorting(JSGlobalData& globalData)
+template<IndexingType indexingType>
+void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
 {
     ASSERT(!inSparseIndexingMode());
+    ASSERT(indexingType == structure()->indexingType());
 
-    switch (structure()->indexingType()) {
-    case ArrayClass:
-        return 0;
-
-    case ArrayWithArrayStorage: {
-        ArrayStorage* storage = m_butterfly->arrayStorage();
-        
-        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
-        
-        unsigned numDefined = 0;
-        unsigned numUndefined = 0;
-        
-        for (; numDefined < usedVectorLength; ++numDefined) {
-            JSValue v = storage->m_vector[numDefined].get();
-            if (!v || v.isUndefined())
-                break;
-        }
+    unsigned myRelevantLength = relevantLength<indexingType>();
+    
+    numDefined = 0;
+    unsigned numUndefined = 0;
         
-        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);
-            }
-        }
+    for (; numDefined < myRelevantLength; ++numDefined) {
+        JSValue v = indexingData<indexingType>()[numDefined].get();
+        if (!v || v.isUndefined())
+            break;
+    }
         
-        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 < myRelevantLength; ++i) {
+        JSValue v = indexingData<indexingType>()[i].get();
+        if (v) {
+            if (v.isUndefined())
+                ++numUndefined;
+            else
+                indexingData<indexingType>()[numDefined++].setWithoutWriteBarrier(v);
         }
-        
-        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;
     }
         
-    default:
-        ASSERT_NOT_REACHED();
-        return 0;
-    }
-}
+    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;
+}
 
 } // namespace JSC