2010-12-09 Michael Saboff <msaboff@apple.com>
authormsaboff@apple.com <msaboff@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 9 Dec 2010 18:27:13 +0000 (18:27 +0000)
committermsaboff@apple.com <msaboff@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 9 Dec 2010 18:27:13 +0000 (18:27 +0000)
        Reviewed by Geoffrey Garen.

        Addressed the "FIXME" issues in array sort for toString() methods that
        mutate the array in either size or contents.  The change is to mark
        the temporary array contents so that they are not garbage collected
        and to make sure the array is large enough to hold the contents
        of the sorted temporary vector.
        https://bugs.webkit.org/show_bug.cgi?id=50718

        * runtime/Collector.cpp:
        (JSC::Heap::addTempSortVector):
        (JSC::Heap::removeTempSortVector):
        (JSC::Heap::markTempSortVectors):
        (JSC::Heap::markRoots):
        * runtime/Collector.h:
        * runtime/JSArray.cpp:
        (JSC::JSArray::sort):
        * runtime/JSValue.h:
2010-12-09  Michael Saboff  <msaboff@apple.com>

        Reviewed by Geoffrey Garen.

        New test to verify that arrays sort per the standard even it
        there is an override for toString() that modifies the array.
        https://bugs.webkit.org/show_bug.cgi?id=50718

        * fast/js/array-sort-modifying-tostring-expected.txt: Added.
        * fast/js/array-sort-modifying-tostring.html: Added.
        * fast/js/script-tests/array-sort-modifying-tostring.js: Added.
        (do_gc):
        (Item):
        (toString_Mutate):
        (test):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@73623 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JavaScriptCore/ChangeLog
JavaScriptCore/runtime/Collector.cpp
JavaScriptCore/runtime/Collector.h
JavaScriptCore/runtime/JSArray.cpp
JavaScriptCore/runtime/JSValue.h
LayoutTests/ChangeLog
LayoutTests/fast/js/array-sort-modifying-tostring-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/array-sort-modifying-tostring.html [new file with mode: 0644]
LayoutTests/fast/js/script-tests/array-sort-modifying-tostring.js [new file with mode: 0644]

index 4534441..c320d99 100644 (file)
@@ -1,5 +1,26 @@
 2010-12-09  Michael Saboff  <msaboff@apple.com>
 
 2010-12-09  Michael Saboff  <msaboff@apple.com>
 
+        Reviewed by Geoffrey Garen.
+
+        Addressed the "FIXME" issues in array sort for toString() methods that
+        mutate the array in either size or contents.  The change is to mark
+        the temporary array contents so that they are not garbage collected
+        and to make sure the array is large enough to hold the contents
+        of the sorted temporary vector.
+        https://bugs.webkit.org/show_bug.cgi?id=50718
+
+        * runtime/Collector.cpp:
+        (JSC::Heap::addTempSortVector):
+        (JSC::Heap::removeTempSortVector):
+        (JSC::Heap::markTempSortVectors):
+        (JSC::Heap::markRoots):
+        * runtime/Collector.h:
+        * runtime/JSArray.cpp:
+        (JSC::JSArray::sort):
+        * runtime/JSValue.h:
+
+2010-12-09  Michael Saboff  <msaboff@apple.com>
+
         Reviewed by Darin Adler.
 
         Changed setting of backtrack labels to not overwrite a prior
         Reviewed by Darin Adler.
 
         Changed setting of backtrack labels to not overwrite a prior
index 09a5fa9..f84f18c 100644 (file)
@@ -960,6 +960,33 @@ void Heap::markProtectedObjects(MarkStack& markStack)
     }
 }
 
     }
 }
 
+void Heap::pushTempSortVector(Vector<ValueStringPair>* tempVector)
+{
+    m_tempSortingVectors.append(tempVector);
+}
+
+void Heap::popTempSortVector(Vector<ValueStringPair>* tempVector)
+{
+    ASSERT_UNUSED(tempVector, tempVector == m_tempSortingVectors.last());
+    m_tempSortingVectors.removeLast();
+}
+    
+void Heap::markTempSortVectors(MarkStack& markStack)
+{
+    typedef Vector<Vector<ValueStringPair>* > VectorOfValueStringVectors;
+
+    VectorOfValueStringVectors::iterator end = m_tempSortingVectors.end();
+    for (VectorOfValueStringVectors::iterator it = m_tempSortingVectors.begin(); it != end; ++it) {
+        Vector<ValueStringPair>* tempSortingVector = *it;
+
+        Vector<ValueStringPair>::iterator vectorEnd = tempSortingVector->end();
+        for (Vector<ValueStringPair>::iterator vectorIt = tempSortingVector->begin(); vectorIt != vectorEnd; ++vectorIt)
+            if (vectorIt->first)
+                markStack.append(vectorIt->first);
+        markStack.drain();
+    }
+}
+    
 void Heap::clearMarkBits()
 {
     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
 void Heap::clearMarkBits()
 {
     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
@@ -1047,6 +1074,9 @@ void Heap::markRoots()
 
     // Mark explicitly registered roots.
     markProtectedObjects(markStack);
 
     // Mark explicitly registered roots.
     markProtectedObjects(markStack);
+    
+    // Mark temporary vector for Array sorting
+    markTempSortVectors(markStack);
 
     // Mark misc. other roots.
     if (m_markListSet && m_markListSet->size())
 
     // Mark misc. other roots.
     if (m_markListSet && m_markListSet->size())
index dd26bc3..62f620e 100644 (file)
@@ -24,6 +24,7 @@
 
 #include "AlignedMemoryAllocator.h"
 #include "GCHandle.h"
 
 #include "AlignedMemoryAllocator.h"
 #include "GCHandle.h"
+#include "JSValue.h"
 #include <stddef.h>
 #include <string.h>
 #include <wtf/Bitmap.h>
 #include <stddef.h>
 #include <string.h>
 #include <wtf/Bitmap.h>
@@ -139,6 +140,9 @@ namespace JSC {
 
         void markConservatively(MarkStack&, void* start, void* end);
 
 
         void markConservatively(MarkStack&, void* start, void* end);
 
+        void pushTempSortVector(WTF::Vector<ValueStringPair>*);
+        void popTempSortVector(WTF::Vector<ValueStringPair>*);        
+
         HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; }
 
         JSGlobalData* globalData() const { return m_globalData; }
         HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; }
 
         JSGlobalData* globalData() const { return m_globalData; }
@@ -173,6 +177,7 @@ namespace JSC {
 
         void markRoots();
         void markProtectedObjects(MarkStack&);
 
         void markRoots();
         void markProtectedObjects(MarkStack&);
+        void markTempSortVectors(MarkStack&);
         void markCurrentThreadConservatively(MarkStack&);
         void markCurrentThreadConservativelyInternal(MarkStack&);
         void markOtherThreadConservatively(MarkStack&, Thread*);
         void markCurrentThreadConservatively(MarkStack&);
         void markCurrentThreadConservativelyInternal(MarkStack&);
         void markOtherThreadConservatively(MarkStack&, Thread*);
@@ -187,6 +192,7 @@ namespace JSC {
 
         ProtectCountSet m_protectedValues;
         WTF::Vector<AlignedMemory<WeakGCHandlePool::poolSize> > m_weakGCHandlePools;
 
         ProtectCountSet m_protectedValues;
         WTF::Vector<AlignedMemory<WeakGCHandlePool::poolSize> > m_weakGCHandlePools;
+        WTF::Vector<WTF::Vector<ValueStringPair>* > m_tempSortingVectors;
 
         HashSet<MarkedArgumentBuffer*>* m_markListSet;
 
 
         HashSet<MarkedArgumentBuffer*>* m_markListSet;
 
index b8b92f4..556a16e 100644 (file)
@@ -874,8 +874,6 @@ static int compareNumbersForQSort(const void* a, const void* b)
     return (da > db) - (da < db);
 }
 
     return (da > db) - (da < db);
 }
 
-typedef std::pair<JSValue, UString> ValueStringPair;
-
 static int compareByStringPairForQSort(const void* a, const void* b)
 {
     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
 static int compareByStringPairForQSort(const void* a, const void* b)
 {
     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
@@ -939,6 +937,8 @@ void JSArray::sort(ExecState* exec)
         throwOutOfMemoryError(exec);
         return;
     }
         throwOutOfMemoryError(exec);
         return;
     }
+    
+    Heap::heap(this)->pushTempSortVector(&values);
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
         JSValue value = storage->m_vector[i];
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
         JSValue value = storage->m_vector[i];
@@ -946,9 +946,6 @@ void JSArray::sort(ExecState* exec)
         values[i].first = value;
     }
 
         values[i].first = value;
     }
 
-    // FIXME: While calling these toString functions, the array could be mutated.
-    // In that case, objects pointed to by values in this vector might get garbage-collected!
-
     // FIXME: The following loop continues to call toString on subsequent values even after
     // a toString call raises an exception.
 
     // FIXME: The following loop continues to call toString on subsequent values even after
     // a toString call raises an exception.
 
@@ -969,12 +966,18 @@ void JSArray::sort(ExecState* exec)
     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif
 
     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif
 
-    // FIXME: If the toString function changed the length of the array, this might be
-    // modifying the vector incorrectly.
-
+    // If the toString function changed the length of the array or vector storage,
+    // increase the length to handle the orignal number of actual values.
+    if (m_vectorLength < lengthNotIncludingUndefined)
+        increaseVectorLength(lengthNotIncludingUndefined);
+    if (storage->m_length < lengthNotIncludingUndefined)
+        storage->m_length = lengthNotIncludingUndefined;
+        
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
         storage->m_vector[i] = values[i].first;
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
         storage->m_vector[i] = values[i].first;
 
+    Heap::heap(this)->popTempSortVector(&values);
+    
     checkConsistency(SortConsistencyCheck);
 }
 
     checkConsistency(SortConsistencyCheck);
 }
 
index cad9662..dc54f40 100644 (file)
@@ -763,7 +763,8 @@ namespace JSC {
         return asValue() == jsNull();
     }
 #endif // USE(JSVALUE32_64)
         return asValue() == jsNull();
     }
 #endif // USE(JSVALUE32_64)
-
+    
+    typedef std::pair<JSValue, UString> ValueStringPair;
 } // namespace JSC
 
 #endif // JSValue_h
 } // namespace JSC
 
 #endif // JSValue_h
index f2d0801..f0d30de 100644 (file)
@@ -1,3 +1,19 @@
+2010-12-09  Michael Saboff  <msaboff@apple.com>
+
+        Reviewed by Geoffrey Garen.
+
+        New test to verify that arrays sort per the standard even it
+        there is an override for toString() that modifies the array.
+        https://bugs.webkit.org/show_bug.cgi?id=50718
+
+        * fast/js/array-sort-modifying-tostring-expected.txt: Added.
+        * fast/js/array-sort-modifying-tostring.html: Added.
+        * fast/js/script-tests/array-sort-modifying-tostring.js: Added.
+        (do_gc):
+        (Item):
+        (toString_Mutate):
+        (test):
+
 2010-12-09  Abhishek Arya  <inferno@chromium.org>
 
         Reviewed by Dimitri Glazkov.
 2010-12-09  Abhishek Arya  <inferno@chromium.org>
 
         Reviewed by Dimitri Glazkov.
diff --git a/LayoutTests/fast/js/array-sort-modifying-tostring-expected.txt b/LayoutTests/fast/js/array-sort-modifying-tostring-expected.txt
new file mode 100644 (file)
index 0000000..21ec761
--- /dev/null
@@ -0,0 +1,11 @@
+Test of array with toString() override that truncates array.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS Array length is unchanged.
+PASS Array values are correct.
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/array-sort-modifying-tostring.html b/LayoutTests/fast/js/array-sort-modifying-tostring.html
new file mode 100644 (file)
index 0000000..74b825c
--- /dev/null
@@ -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="script-tests/array-sort-modifying-tostring.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/js/script-tests/array-sort-modifying-tostring.js b/LayoutTests/fast/js/script-tests/array-sort-modifying-tostring.js
new file mode 100644 (file)
index 0000000..cccdce7
--- /dev/null
@@ -0,0 +1,77 @@
+description(
+"Test of array with toString() override that truncates array."
+);
+
+var maxSize = 2000;
+var keepSize = 100;
+var digits = 4;
+var countToDelete = maxSize - keepSize;
+
+var a = new Array(maxSize);
+
+function do_gc() {
+    if (window.GCController)
+        return GCController.collect();
+
+    for (var i = 0; i < 1000; i++)
+        new String(i);
+}
+
+function Item(val) {
+    this.value = val;
+}
+
+function toString_Mutate() {
+    a.splice(keepSize, countToDelete);
+    do_gc();
+    for (var i = keepSize; i < countToDelete; i++) {
+        delete a[i];
+    }
+
+    if ((this != undefined) && (this.value != undefined)) {
+        var s = this.value.toString();
+        if (s.length < digits)
+            s = ('0000' + s).slice(-digits);
+
+        return s;
+    } else
+        return "Undef";
+}
+
+function test() {
+    for (var i = 0; i < a.length; i++) {
+        a[i] = new Item(a.length - i - 1);
+        a[i].toString = toString_Mutate;
+    }
+    try {
+        a.sort();
+    if (a.length == maxSize)
+        testPassed("Array length is unchanged.");
+    else
+        testFailed("Array length should be " + maxSize + " but is " + a.length + ".");
+
+    var firstFailedValue = -1;
+
+    for (var i = 0; i < a.length; i++) {
+        if (a[i].value != i) {
+            firstFailedValue = i;
+            break;
+        }
+    }
+
+    if (firstFailedValue == -1)
+        testPassed("Array values are correct.");
+    else
+        testFailed("Array values are wrong, first bad value at index " + firstFailedValue + ", should be " + firstFailedValue + " was " + a[firstFailedValue].value + ".");
+    } catch(er) {
+        testFailed("Got exception processing sort()");
+    }
+
+    for (var i = 0; i < a.length; i++) {
+        a[i] = 0x42424242;
+    }
+}
+
+test();
+
+var successfullyParsed = true;