JavaScriptCore-1097.13.tar.gz

[apple/javascriptcore.git] / runtime / JSArray.cpp

diff --git a/runtime/JSArray.cpp b/runtime/JSArray.cpp
index aa1b8b7d981cfc652f6921cd47982848b83f99a0..00e009e1333a27cabf5e45fcb22745343d4391aa 100644 (file)
--- a/runtime/JSArray.cpp
+++ b/runtime/JSArray.cpp
@@ -1310,6 +1310,7 @@ bool JSArray::shiftCount(ExecState*, unsigned count)
     ArrayStorage* storage = m_storage;
     
     unsigned oldLength = storage->m_length;
     ArrayStorage* storage = m_storage;
     
     unsigned oldLength = storage->m_length;

+    ASSERT(count <= oldLength);

     
     // If the array contains holes or is otherwise in an abnormal state,
     // use the generic algorithm in ArrayPrototype.
     
     // If the array contains holes or is otherwise in an abnormal state,
     // use the generic algorithm in ArrayPrototype.


@@ -1349,6 +1350,8 @@ bool JSArray::unshiftCount(ExecState* exec, unsigned count)
     if (length != storage->m_numValuesInVector || inSparseMode())
         return false;
 
     if (length != storage->m_numValuesInVector || inSparseMode())
         return false;
 

+    ASSERT(count <= length);
+

     if (m_indexBias >= count) {
         m_indexBias -= count;
         char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(WriteBarrier<Unknown>);
     if (m_indexBias >= count) {
         m_indexBias -= count;
         char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(WriteBarrier<Unknown>);


@@ -1412,11 +1415,8 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal
 
     ArrayStorage* storage = m_storage;
 
 
     ArrayStorage* storage = m_storage;
 

-    unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
-    if (m_sparseValueMap) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
+    unsigned lengthNotIncludingUndefined = compactForSorting();
+    ASSERT(!m_sparseValueMap);

 
     if (!lengthNotIncludingUndefined)
         return;
 
     if (!lengthNotIncludingUndefined)
         return;


@@ -1445,11 +1445,8 @@ void JSArray::sort(ExecState* exec)
 {
     ASSERT(!inSparseMode());
 
 {
     ASSERT(!inSparseMode());
 

-    unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
-    if (m_sparseValueMap) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
+    unsigned lengthNotIncludingUndefined = compactForSorting();
+    ASSERT(!m_sparseValueMap);

 
     if (!lengthNotIncludingUndefined)
         return;
 
     if (!lengthNotIncludingUndefined)
         return;


@@ -1608,7 +1605,7 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
         return;
 
     unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
         return;
 
     unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);

-    unsigned nodeCount = usedVectorLength + (m_sparseValueMap ? m_sparseValueMap->size() : 0);
+    unsigned nodeCount = usedVectorLength;

 
     if (!nodeCount)
         return;
 
     if (!nodeCount)
         return;


@@ -1636,6 +1633,8 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
 
     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
     for (; numDefined < usedVectorLength; ++numDefined) {
 
     // 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_vectorLength)
+            break;

         JSValue v = m_storage->m_vector[numDefined].get();
         if (!v || v.isUndefined())
             break;
         JSValue v = m_storage->m_vector[numDefined].get();
         if (!v || v.isUndefined())
             break;


@@ -1643,6 +1642,8 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
         tree.insert(numDefined);
     }
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
         tree.insert(numDefined);
     }
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {

+        if (i > m_vectorLength)
+            break;

         JSValue v = m_storage->m_vector[i].get();
         if (v) {
             if (v.isUndefined())
         JSValue v = m_storage->m_vector[i].get();
         if (v) {
             if (v.isUndefined())


@@ -1657,49 +1658,33 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
 
     unsigned newUsedVectorLength = numDefined + numUndefined;
 
 
     unsigned newUsedVectorLength = numDefined + numUndefined;
 

-    if (SparseArrayValueMap* map = m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_vectorLength) {
-            // Check that it is possible to allocate an array large enough to hold all the entries.
-            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(exec->globalData(), newUsedVectorLength)) {
-                throwOutOfMemoryError(exec);
-                return;
-            }
-        }
-
-        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;
-        }
-
-        deallocateSparseMap();
-    }
-
-    ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
+    ASSERT(!m_sparseValueMap);

 
 

-    // FIXME: If the compare function changed the length of the array, the following might be
-    // modifying the vector incorrectly.
+    // The array size may have changed.  Figure out the new bounds.
+    unsigned newestUsedVectorLength = min(m_storage->m_length, m_vectorLength);
+    
+    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();
 
     // 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) {
+    for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {

         m_storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
         ++iter;
     }
 
     // Put undefined values back in.
         m_storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
         ++iter;
     }
 
     // Put undefined values back in.

-    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
+    for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i)

         m_storage->m_vector[i].setUndefined();
 
     // Ensure that unused values in the vector are zeroed out.
         m_storage->m_vector[i].setUndefined();
 
     // Ensure that unused values in the vector are zeroed out.

-    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
+    for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i)

         m_storage->m_vector[i].clear();
 
         m_storage->m_vector[i].clear();
 

-    m_storage->m_numValuesInVector = newUsedVectorLength;
+    m_storage->m_numValuesInVector = undefinedElementsThreshold;

 
     checkConsistency(SortConsistencyCheck);
 }
 
     checkConsistency(SortConsistencyCheck);
 }


@@ -1740,7 +1725,7 @@ void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t le
         callFrame->setArgument(i, get(exec, i));
 }
 
         callFrame->setArgument(i, get(exec, i));
 }
 

-unsigned JSArray::compactForSorting(JSGlobalData& globalData)
+unsigned JSArray::compactForSorting()

 {
     ASSERT(!inSparseMode());
 
 {
     ASSERT(!inSparseMode());
 


@@ -1771,23 +1756,7 @@ unsigned JSArray::compactForSorting(JSGlobalData& globalData)
 
     unsigned newUsedVectorLength = numDefined + numUndefined;
 
 
     unsigned newUsedVectorLength = numDefined + numUndefined;
 

-    if (SparseArrayValueMap* map = m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_vectorLength) {
-            // Check that it is possible to allocate an array large enough to hold all the entries - if not,
-            // exception is thrown by caller.
-            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(globalData, newUsedVectorLength))
-                return 0;
-
-            storage = m_storage;
-        }
-
-        SparseArrayValueMap::const_iterator end = map->end();
-        for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
-            storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.getNonSparseMode());
-
-        deallocateSparseMap();
-    }
+    ASSERT(!m_sparseValueMap);

 
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
         storage->m_vector[i].setUndefined();
 
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
         storage->m_vector[i].setUndefined();