Diff
Modified: branches/safari-536.28-branch/LayoutTests/ChangeLog (135003 => 135004)
--- branches/safari-536.28-branch/LayoutTests/ChangeLog 2012-11-16 22:42:59 UTC (rev 135003)
+++ branches/safari-536.28-branch/LayoutTests/ChangeLog 2012-11-16 22:46:45 UTC (rev 135004)
@@ -1,3 +1,20 @@
+2012-11-16 Andy Estes <aes...@apple.com>
+
+ Merge r130102.
+
+ 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-11-16 Lucas Forschler <lforsch...@apple.com>
Merge r128088
Modified: branches/safari-536.28-branch/LayoutTests/fast/js/jsc-test-list (135003 => 135004)
--- branches/safari-536.28-branch/LayoutTests/fast/js/jsc-test-list 2012-11-16 22:42:59 UTC (rev 135003)
+++ branches/safari-536.28-branch/LayoutTests/fast/js/jsc-test-list 2012-11-16 22:46:45 UTC (rev 135004)
@@ -239,6 +239,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: branches/safari-536.28-branch/LayoutTests/fast/js/script-tests/sort-with-side-effecting-comparisons.js (0 => 135004)
--- branches/safari-536.28-branch/LayoutTests/fast/js/script-tests/sort-with-side-effecting-comparisons.js (rev 0)
+++ branches/safari-536.28-branch/LayoutTests/fast/js/script-tests/sort-with-side-effecting-comparisons.js 2012-11-16 22:46:45 UTC (rev 135004)
@@ -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: branches/safari-536.28-branch/LayoutTests/fast/js/sort-with-side-effecting-comparisons-expected.txt (0 => 135004)
--- branches/safari-536.28-branch/LayoutTests/fast/js/sort-with-side-effecting-comparisons-expected.txt (rev 0)
+++ branches/safari-536.28-branch/LayoutTests/fast/js/sort-with-side-effecting-comparisons-expected.txt 2012-11-16 22:46:45 UTC (rev 135004)
@@ -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: branches/safari-536.28-branch/LayoutTests/fast/js/sort-with-side-effecting-comparisons.html (0 => 135004)
--- branches/safari-536.28-branch/LayoutTests/fast/js/sort-with-side-effecting-comparisons.html (rev 0)
+++ branches/safari-536.28-branch/LayoutTests/fast/js/sort-with-side-effecting-comparisons.html 2012-11-16 22:46:45 UTC (rev 135004)
@@ -0,0 +1,10 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+</body>
+</html>
Modified: branches/safari-536.28-branch/Source/_javascript_Core/ChangeLog (135003 => 135004)
--- branches/safari-536.28-branch/Source/_javascript_Core/ChangeLog 2012-11-16 22:42:59 UTC (rev 135003)
+++ branches/safari-536.28-branch/Source/_javascript_Core/ChangeLog 2012-11-16 22:46:45 UTC (rev 135004)
@@ -1,3 +1,31 @@
+2012-11-16 Andy Estes <aes...@apple.com>
+
+ Merge r130102.
+
+ 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-11-14 Lucas Forschler <lforsch...@apple.com>
Merge fix for <rdar://problem/12691662>.
Modified: branches/safari-536.28-branch/Source/_javascript_Core/runtime/ArrayPrototype.cpp (135003 => 135004)
--- branches/safari-536.28-branch/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2012-11-16 22:42:59 UTC (rev 135003)
+++ branches/safari-536.28-branch/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2012-11-16 22:46:45 UTC (rev 135004)
@@ -634,7 +634,7 @@
CallData callData;
CallType callType = getCallData(function, callData);
- if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseMode()) {
+ if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->hasSparseMap()) {
if (isNumericCompareFunction(exec, callType, callData))
asArray(thisObj)->sortNumeric(exec, function, callType, callData);
else if (callType != CallTypeNone)
Modified: branches/safari-536.28-branch/Source/_javascript_Core/runtime/JSArray.cpp (135003 => 135004)
--- branches/safari-536.28-branch/Source/_javascript_Core/runtime/JSArray.cpp 2012-11-16 22:42:59 UTC (rev 135003)
+++ branches/safari-536.28-branch/Source/_javascript_Core/runtime/JSArray.cpp 2012-11-16 22:46:45 UTC (rev 135004)
@@ -1413,11 +1413,8 @@
ArrayStorage* storage = m_storage;
- unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
- if (m_sparseValueMap) {
- throwOutOfMemoryError(exec);
- return;
- }
+ unsigned lengthNotIncludingUndefined = compactForSorting();
+ ASSERT(!m_sparseValueMap);
if (!lengthNotIncludingUndefined)
return;
@@ -1446,11 +1443,8 @@
{
ASSERT(!inSparseMode());
- unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
- if (m_sparseValueMap) {
- throwOutOfMemoryError(exec);
- return;
- }
+ unsigned lengthNotIncludingUndefined = compactForSorting();
+ ASSERT(!m_sparseValueMap);
if (!lengthNotIncludingUndefined)
return;
@@ -1609,7 +1603,7 @@
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;
@@ -1637,6 +1631,8 @@
// 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;
@@ -1644,6 +1640,8 @@
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())
@@ -1658,49 +1656,33 @@
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;
- }
- }
+ ASSERT(!m_sparseValueMap);
- 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;
- }
+ // 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);
- deallocateSparseMap();
- }
-
- 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.
-
// 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.
- 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.
- for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
+ for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i)
m_storage->m_vector[i].clear();
- m_storage->m_numValuesInVector = newUsedVectorLength;
+ m_storage->m_numValuesInVector = undefinedElementsThreshold;
checkConsistency(SortConsistencyCheck);
}
@@ -1741,7 +1723,7 @@
callFrame->setArgument(i, get(exec, i));
}
-unsigned JSArray::compactForSorting(JSGlobalData& globalData)
+unsigned JSArray::compactForSorting()
{
ASSERT(!inSparseMode());
@@ -1772,24 +1754,8 @@
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;
+ ASSERT(!m_sparseValueMap);
- 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();
- }
-
for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
storage->m_vector[i].setUndefined();
for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
Modified: branches/safari-536.28-branch/Source/_javascript_Core/runtime/JSArray.h (135003 => 135004)
--- branches/safari-536.28-branch/Source/_javascript_Core/runtime/JSArray.h 2012-11-16 22:42:59 UTC (rev 135003)
+++ branches/safari-536.28-branch/Source/_javascript_Core/runtime/JSArray.h 2012-11-16 22:46:45 UTC (rev 135004)
@@ -250,6 +250,11 @@
m_storage->m_inCompactInitialization = false;
#endif
}
+
+ bool hasSparseMap()
+ {
+ return m_sparseValueMap;
+ }
bool inSparseMode()
{
@@ -312,7 +317,7 @@
bool increaseVectorLength(JSGlobalData&, unsigned newLength);
bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
- unsigned compactForSorting(JSGlobalData&);
+ unsigned compactForSorting();
enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);