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;
