Diff
Modified: trunk/LayoutTests/ChangeLog (130101 => 130102)
--- trunk/LayoutTests/ChangeLog 2012-10-02 00:14:18 UTC (rev 130101)
+++ trunk/LayoutTests/ChangeLog 2012-10-02 00:14:33 UTC (rev 130102)
@@ -1,3 +1,16 @@
+2012-10-01 Filip Pizlo <fpi...@apple.com>
+
+ Address a FIXME in JSArray::sort
+ https://bugs.webkit.org/show_bug.cgi?id=98080
+ <rdar://problem/12407844>
+
+ Reviewed by Oliver Hunt.
+
+ * fast/js/jsc-test-list:
+ * fast/js/script-tests/sort-with-side-effecting-comparisons.js: Added.
+ * fast/js/sort-with-side-effecting-comparisons-expected.txt: Added.
+ * fast/js/sort-with-side-effecting-comparisons.html: Added.
+
2012-10-01 Roger Fong <roger_f...@apple.com>
Unreviewed. Skipping flaky test on Windows: inspector/debugger/dynamic-script-tag.html.
Modified: trunk/LayoutTests/fast/js/jsc-test-list (130101 => 130102)
--- trunk/LayoutTests/fast/js/jsc-test-list 2012-10-02 00:14:18 UTC (rev 130101)
+++ trunk/LayoutTests/fast/js/jsc-test-list 2012-10-02 00:14:33 UTC (rev 130102)
@@ -297,6 +297,7 @@
fast/js/sort-non-numbers
fast/js/sort-randomly
fast/js/sort-stability
+fast/js/sort-with-side-effecting-comparisons
fast/js/sparse-array
fast/js/stack-overflow-arrity-catch
fast/js/stack-overflow-catch
Added: trunk/LayoutTests/fast/js/script-tests/sort-with-side-effecting-comparisons.js (0 => 130102)
--- trunk/LayoutTests/fast/js/script-tests/sort-with-side-effecting-comparisons.js (rev 0)
+++ trunk/LayoutTests/fast/js/script-tests/sort-with-side-effecting-comparisons.js 2012-10-02 00:14:33 UTC (rev 130102)
@@ -0,0 +1,21 @@
+description(
+"Checks that sorting an array with a side-effecting comparison function doesn't trigger assertions."
+);
+
+var array = [];
+
+for (var i = 0; i < 20000; ++i)
+ array.push(i);
+
+array.sort(function(a, b) {
+ array.shift();
+ if (a < b)
+ return -1;
+ if (a > b)
+ return 1;
+ return 0;
+});
+
+testPassed("It worked.");
+
+
Added: trunk/LayoutTests/fast/js/sort-with-side-effecting-comparisons-expected.txt (0 => 130102)
--- trunk/LayoutTests/fast/js/sort-with-side-effecting-comparisons-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/js/sort-with-side-effecting-comparisons-expected.txt 2012-10-02 00:14:33 UTC (rev 130102)
@@ -0,0 +1,10 @@
+Checks that sorting an array with a side-effecting comparison function doesn't trigger assertions.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS It worked.
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/fast/js/sort-with-side-effecting-comparisons.html (0 => 130102)
--- trunk/LayoutTests/fast/js/sort-with-side-effecting-comparisons.html (rev 0)
+++ trunk/LayoutTests/fast/js/sort-with-side-effecting-comparisons.html 2012-10-02 00:14:33 UTC (rev 130102)
@@ -0,0 +1,10 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+</body>
+</html>
Modified: trunk/Source/_javascript_Core/ChangeLog (130101 => 130102)
--- trunk/Source/_javascript_Core/ChangeLog 2012-10-02 00:14:18 UTC (rev 130101)
+++ trunk/Source/_javascript_Core/ChangeLog 2012-10-02 00:14:33 UTC (rev 130102)
@@ -1,3 +1,27 @@
+2012-10-01 Filip Pizlo <fpi...@apple.com>
+
+ Address a FIXME in JSArray::sort
+ https://bugs.webkit.org/show_bug.cgi?id=98080
+ <rdar://problem/12407844>
+
+ Reviewed by Oliver Hunt.
+
+ Get rid of fast sorting of sparse maps. I don't know that it's broken but I do know that we don't
+ have coverage for it. Then also address the FIXME in JSArray::sort regarding side-effecting
+ compare functions.
+
+ * runtime/ArrayPrototype.cpp:
+ (JSC::arrayProtoFuncSort):
+ * runtime/JSArray.cpp:
+ (JSC::JSArray::sortNumeric):
+ (JSC::JSArray::sort):
+ (JSC::JSArray::compactForSorting):
+ * runtime/JSArray.h:
+ (JSArray):
+ * runtime/JSObject.h:
+ (JSC::JSObject::hasSparseMap):
+ (JSObject):
+
2012-10-01 Jonathan Liu <net...@gmail.com>
Remove unused sys/mman.h include
Modified: trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp (130101 => 130102)
--- trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2012-10-02 00:14:18 UTC (rev 130101)
+++ trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2012-10-02 00:14:33 UTC (rev 130102)
@@ -655,7 +655,7 @@
CallData callData;
CallType callType = getCallData(function, callData);
- if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseIndexingMode() && !shouldUseSlowPut(thisObj->structure()->indexingType())) {
+ if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->hasSparseMap() && !shouldUseSlowPut(thisObj->structure()->indexingType())) {
if (isNumericCompareFunction(exec, callType, callData))
asArray(thisObj)->sortNumeric(exec, function, callType, callData);
else if (callType != CallTypeNone)
Modified: trunk/Source/_javascript_Core/runtime/JSArray.cpp (130101 => 130102)
--- trunk/Source/_javascript_Core/runtime/JSArray.cpp 2012-10-02 00:14:18 UTC (rev 130101)
+++ trunk/Source/_javascript_Core/runtime/JSArray.cpp 2012-10-02 00:14:33 UTC (rev 130102)
@@ -601,14 +601,11 @@
return;
case ArrayWithArrayStorage: {
- unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
+ unsigned lengthNotIncludingUndefined = compactForSorting();
ArrayStorage* storage = m_butterfly->arrayStorage();
+
+ ASSERT(!storage->m_sparseMap);
- if (storage->m_sparseMap.get()) {
- throwOutOfMemoryError(exec);
- return;
- }
-
if (!lengthNotIncludingUndefined)
return;
@@ -646,12 +643,9 @@
return;
case ArrayWithArrayStorage: {
- unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
+ unsigned lengthNotIncludingUndefined = compactForSorting();
ArrayStorage* storage = m_butterfly->arrayStorage();
- if (storage->m_sparseMap.get()) {
- throwOutOfMemoryError(exec);
- return;
- }
+ ASSERT(!storage->m_sparseMap);
if (!lengthNotIncludingUndefined)
return;
@@ -811,18 +805,17 @@
return;
case ArrayWithArrayStorage: {
- ArrayStorage* storage = m_butterfly->arrayStorage();
-
// 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()))
+ ASSERT(arrayStorage()->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+ if (arrayStorage()->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);
+ unsigned usedVectorLength = min(arrayStorage()->length(), arrayStorage()->vectorLength());
+ ASSERT(!arrayStorage()->m_sparseMap);
+ unsigned nodeCount = usedVectorLength;
if (!nodeCount)
return;
@@ -850,14 +843,18 @@
// 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 (numDefined > arrayStorage()->vectorLength())
+ break;
+ JSValue v = arrayStorage()->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 (i > arrayStorage()->vectorLength())
+ break;
+ JSValue v = arrayStorage()->m_vector[i].get();
if (v) {
if (v.isUndefined())
++numUndefined;
@@ -871,51 +868,34 @@
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();
- }
+ ASSERT(!arrayStorage()->m_sparseMap);
- ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
+ // The array size may have changed. Figure out the new bounds.
+ unsigned newestUsedVectorLength = min(arrayStorage()->length(), arrayStorage()->vectorLength());
- // 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);
+ for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
+ arrayStorage()->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)
- storage->m_vector[i].setUndefined();
-
+ for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i)
+ arrayStorage()->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();
+ for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i)
+ arrayStorage()->m_vector[i].clear();
- storage->m_numValuesInVector = newUsedVectorLength;
-
+ arrayStorage()->m_numValuesInVector = undefinedElementsThreshold;
+
return;
}
@@ -982,7 +962,7 @@
}
}
-unsigned JSArray::compactForSorting(JSGlobalData& globalData)
+unsigned JSArray::compactForSorting()
{
ASSERT(!inSparseIndexingMode());
@@ -1016,23 +996,7 @@
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();
- }
+ ASSERT(!storage->m_sparseMap);
for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
storage->m_vector[i].setUndefined();
Modified: trunk/Source/_javascript_Core/runtime/JSArray.h (130101 => 130102)
--- trunk/Source/_javascript_Core/runtime/JSArray.h 2012-10-02 00:14:18 UTC (rev 130101)
+++ trunk/Source/_javascript_Core/runtime/JSArray.h 2012-10-02 00:14:33 UTC (rev 130102)
@@ -103,7 +103,7 @@
bool unshiftCountSlowCase(JSGlobalData&, bool, unsigned);
- unsigned compactForSorting(JSGlobalData&);
+ unsigned compactForSorting();
};
inline Butterfly* createArrayButterfly(JSGlobalData& globalData, unsigned initialLength)
Modified: trunk/Source/_javascript_Core/runtime/JSObject.h (130101 => 130102)
--- trunk/Source/_javascript_Core/runtime/JSObject.h 2012-10-02 00:14:18 UTC (rev 130101)
+++ trunk/Source/_javascript_Core/runtime/JSObject.h 2012-10-02 00:14:33 UTC (rev 130102)
@@ -327,6 +327,19 @@
}
}
+ bool hasSparseMap()
+ {
+ switch (structure()->indexingType()) {
+ case ALL_BLANK_INDEXING_TYPES:
+ return false;
+ case ALL_ARRAY_STORAGE_INDEXING_TYPES:
+ return m_butterfly->arrayStorage()->m_sparseMap;
+ default:
+ ASSERT_NOT_REACHED();
+ return false;
+ }
+ }
+
bool inSparseIndexingMode()
{
switch (structure()->indexingType()) {
