Merge r34204.


git-svn-id: http://svn.webkit.org/repository/webkit/branches/Safari-3-1-branch@34473 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog
index 9f4d93c..6b59bd5 100644
--- a/JavaScriptCore/ChangeLog
+++ b/JavaScriptCore/ChangeLog
@@ -1,3 +1,21 @@
+2008-06-09  Mark Rowe  <mrowe@apple.com>
+
+        Merge r34204 to Safari-3-1-branch.
+
+    2008-05-29  Alexey Proskuryakov  <ap@webkit.org>
+
+        Reviewed by Darin.
+
+        https://bugs.webkit.org/show_bug.cgi?id=19294
+        <rdar://problem/5969062> A crash when iterating over a sparse array backwards.
+
+        * kjs/array_instance.cpp: Turned sparseArrayCutoff into a macro, so that using max() on it
+        doesn't cause a PIC branch.
+        (KJS::ArrayInstance::increaseVectorLength): Added a comment about this function not
+        preserving class invariants.
+        (KJS::ArrayInstance::put): Update m_storage after reallocation. Move values that fit to
+        the vector from the map in all code paths.
+
 2008-03-31  Mark Rowe  <mrowe@apple.com>
 
         Merge r31388 to Safari-3-1-branch.
diff --git a/JavaScriptCore/kjs/array_instance.cpp b/JavaScriptCore/kjs/array_instance.cpp
index 0578ed7..fec5c09 100644
--- a/JavaScriptCore/kjs/array_instance.cpp
+++ b/JavaScriptCore/kjs/array_instance.cpp
@@ -27,7 +27,7 @@
 #include "PropertyNameArray.h"
 #include <wtf/Assertions.h>
 
-using std::min;
+using namespace std;
 
 namespace KJS {
 
@@ -46,7 +46,9 @@
 // For all array indices under sparseArrayCutoff, we always use a vector.
 // When indices greater than sparseArrayCutoff are involved, we use a vector
 // as long as it is 1/8 full. If more sparse than that, we use a map.
-static const unsigned sparseArrayCutoff = 10000;
+// This value has to be a macro to be used in max() and min() without introducing
+// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
+#define sparseArrayCutoff 10000U
 static const unsigned minDensityMultiplier = 8;
 
 static const unsigned copyingSortCutoff = 50000;
@@ -228,7 +230,24 @@
         return;
     }
 
-    if (i < sparseArrayCutoff) {
+    SparseArrayValueMap* map = storage->m_sparseValueMap;
+
+    if (i >= sparseArrayCutoff) {
+        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
+        // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
+        if (!isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
+            if (!map) {
+                map = new SparseArrayValueMap;
+                storage->m_sparseValueMap = map;
+            }
+            map->set(i, value);
+            return;
+        }
+    }
+
+    // We have decided that we'll put the new item into the vector.
+    // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
+    if (!map || map->isEmpty()) {
         increaseVectorLength(i + 1);
         storage = m_storage;
         ++storage->m_numValuesInVector;
@@ -236,38 +255,18 @@
         return;
     }
 
-    SparseArrayValueMap* map = storage->m_sparseValueMap;
-    if (!map || map->isEmpty()) {
-        if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
-            increaseVectorLength(i + 1);
-            storage = m_storage;
-            ++storage->m_numValuesInVector;
-            storage->m_vector[i] = value;
-            return;
-        }
-        if (!map) {
-            map = new SparseArrayValueMap;
-            storage->m_sparseValueMap = map;
-        }
-        map->set(i, value);
-        return;
-    }
-
+    // Decide how many values it would be best to move from the map.
     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
-    if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
-        map->set(i, value);
-        return;
-    }
-
     unsigned newVectorLength = increasedVectorLength(i + 1);
-    for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
+    for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
         newNumValuesInVector += map->contains(j);
-    newNumValuesInVector -= map->contains(i);
+    if (i >= sparseArrayCutoff)
+        newNumValuesInVector -= map->contains(i);
     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
         while (true) {
             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
-            for (unsigned j = newVectorLength; j < proposedNewVectorLength; ++j)
+            for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j)
                 proposedNewNumValuesInVector += map->contains(j);
             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                 break;
@@ -282,9 +281,12 @@
     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
         for (unsigned j = vectorLength; j < newVectorLength; ++j)
             storage->m_vector[j] = 0;
-        map->remove(i);
+        if (i > sparseArrayCutoff)
+            map->remove(i);
     } else {
-        for (unsigned j = vectorLength; j < newVectorLength; ++j)
+        for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j)
+            storage->m_vector[j] = 0;
+        for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
             storage->m_vector[j] = map->take(j);
     }
 
@@ -292,6 +294,8 @@
 
     m_vectorLength = newVectorLength;
     storage->m_numValuesInVector = newNumValuesInVector;
+
+    m_storage = storage;
 }
 
 bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName)
@@ -359,6 +363,9 @@
 
 void ArrayInstance::increaseVectorLength(unsigned newLength)
 {
+    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
+    // to the vector. Callers have to account for that, because they can do it more efficiently.
+
     ArrayStorage* storage = m_storage;
 
     unsigned vectorLength = m_vectorLength;
diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
index 0fa43f1..212c49e 100644
--- a/LayoutTests/ChangeLog
+++ b/LayoutTests/ChangeLog
@@ -1,3 +1,18 @@
+2008-06-09  Mark Rowe  <mrowe@apple.com>
+
+        Merge r34204 to Safari-3-1-branch.
+
+    2008-05-29  Alexey Proskuryakov  <ap@webkit.org>
+
+        Reviewed by Darin.
+
+        https://bugs.webkit.org/show_bug.cgi?id=19294
+        <rdar://problem/5969062> A crash when iterating over a sparse array backwards.
+
+        * fast/js/array-iterate-backwards-expected.txt: Added.
+        * fast/js/array-iterate-backwards.html: Added.
+        * fast/js/resources/array-iterate-backwards.js: Added.
+
 2008-03-31  Mark Rowe  <mrowe@apple.com>
 
         Merge r31388 to Safari-3-1-branch.
diff --git a/LayoutTests/fast/js/array-iterate-backwards-expected.txt b/LayoutTests/fast/js/array-iterate-backwards-expected.txt
new file mode 100644
index 0000000..7d48695
--- /dev/null
+++ b/LayoutTests/fast/js/array-iterate-backwards-expected.txt
@@ -0,0 +1,12 @@
+This test checks that iterating a large array backwards works correctly.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS verify(32768) is true
+PASS verify(65536) is true
+PASS verify(120000) is true
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/array-iterate-backwards.html b/LayoutTests/fast/js/array-iterate-backwards.html
new file mode 100644
index 0000000..b2299d0
--- /dev/null
+++ b/LayoutTests/fast/js/array-iterate-backwards.html
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/array-iterate-backwards.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/js/resources/array-iterate-backwards.js b/LayoutTests/fast/js/resources/array-iterate-backwards.js
new file mode 100644
index 0000000..631e208
--- /dev/null
+++ b/LayoutTests/fast/js/resources/array-iterate-backwards.js
@@ -0,0 +1,34 @@
+description(
+"This test checks that iterating a large array backwards works correctly."
+);
+
+var bytes = new Array();
+
+function prepare(nbytes) {
+    var i = nbytes - 1;
+    while (i >= 0) {
+        bytes[i] = new Number(i);
+        i -= 1;
+    }
+}
+
+function verify(nbytes) {
+    var i = nbytes - 1;
+    while (i >= 0) {
+        if (bytes[i] != i)
+            return false;
+        i -= 1;
+    }
+    return true;
+}
+
+prepare(32768);
+shouldBeTrue('verify(32768)');
+
+prepare(65536);
+shouldBeTrue('verify(65536)');
+
+prepare(120000);
+shouldBeTrue('verify(120000)');
+
+successfullyParsed = true;