Changeset 216137 in webkit

Timestamp:

May 3, 2017 1:33:01 PM (7 years ago)

Author:

keith_miller@apple.com

Message:

Different behaviour with the .sort(callback) method (unlike Firefox & Chrome)
​https://bugs.webkit.org/show_bug.cgi?id=47825

Reviewed by Saam Barati.

JSTests:

• stress/sorting-boolean-result-comparator.js: Added.

(checkArray):

Source/JavaScriptCore:

This patch makes our sort function match the behavior of Firefox
and Chrome when the result of the comparison function is a
boolean. When we first switched to using merge sort, it regressed
JQuery sorting of DOM nodes by 30%. The regression was do to the
fact that JQuery was using compareDocumentPosition to compare the
locations of objects. Since one of the benchmarks would pass a
reverse sorted list to the sort function we would end up walking
the entire DOM to do comparisons. The solution to this was to
merge based on comparison(right, left) rather than
comparison(left, right). Although, in practice this does nothing
since sort could just as easily receive an already sorted list and
we're back in the same spot.

The downside of sorting with comparison(right, left) is that to
maintain stability when sorting, you only want to merge from right
when the comparison function returns a negative value. This is
where the problem with booleans comes in. Since booleans toNumber
false to 0 and true to 1 both values are "equal". This patch fixes
this by special casing boolean return values.

• builtins/ArrayPrototype.js:

(sort.merge):

LayoutTests:

Fix broken test.

• http/tests/inspector/worker/blob-script-with-cross-domain-imported-scripts-expected.txt:

Location:

trunk

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/stress/sorting-boolean-result-comparator.js (added)
• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/http/tests/inspector/worker/blob-script-with-cross-domain-imported-scripts-expected.txt (modified) (1 diff)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/builtins/ArrayPrototype.js (modified) (1 diff)

trunk/JSTests/ChangeLog

@@ +1 @@
+2017-05-03  Keith Miller  <keith_miller@apple.com>
+
+        Different behaviour with the .sort(callback) method (unlike Firefox & Chrome)
+        https://bugs.webkit.org/show_bug.cgi?id=47825
+
+        Reviewed by Saam Barati.
+
+        * stress/sorting-boolean-result-comparator.js: Added.
+        (checkArray):
+
 2017-05-02  David Kilzer  <ddkilzer@apple.com>
 

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2017-05-03  Keith Miller  <keith_miller@apple.com>
+
+        Different behaviour with the .sort(callback) method (unlike Firefox & Chrome)
+        https://bugs.webkit.org/show_bug.cgi?id=47825
+
+        Reviewed by Saam Barati.
+
+        Fix broken test.
+
+        * http/tests/inspector/worker/blob-script-with-cross-domain-imported-scripts-expected.txt:
+
 2017-05-03  Matt Lewis  <jlewis3@apple.com>
 

trunk/LayoutTests/http/tests/inspector/worker/blob-script-with-cross-domain-imported-scripts-expected.txt

@@ -9 +9 @@
 http://localhost:8000/inspector/worker/resources/worker-blob-import-script.js
 SCRIPTS:
-blob:<sanitized>
 http://localhost:8000/inspector/worker/resources/worker-blob-script.js
 http://localhost:8000/inspector/worker/resources/worker-blob-import-script.js
+blob:<sanitized>
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2017-05-03  Keith Miller  <keith_miller@apple.com>
+
+        Different behaviour with the .sort(callback) method (unlike Firefox & Chrome)
+        https://bugs.webkit.org/show_bug.cgi?id=47825
+
+        Reviewed by Saam Barati.
+
+        This patch makes our sort function match the behavior of Firefox
+        and Chrome when the result of the comparison function is a
+        boolean. When we first switched to using merge sort, it regressed
+        JQuery sorting of DOM nodes by 30%. The regression was do to the
+        fact that JQuery was using compareDocumentPosition to compare the
+        locations of objects. Since one of the benchmarks would pass a
+        reverse sorted list to the sort function we would end up walking
+        the entire DOM to do comparisons. The solution to this was to
+        merge based on comparison(right, left) rather than
+        comparison(left, right). Although, in practice this does nothing
+        since sort could just as easily receive an already sorted list and
+        we're back in the same spot.
+
+        The downside of sorting with comparison(right, left) is that to
+        maintain stability when sorting, you only want to merge from right
+        when the comparison function returns a negative value. This is
+        where the problem with booleans comes in. Since booleans toNumber
+        false to 0 and true to 1 both values are "equal". This patch fixes
+        this by special casing boolean return values.
+
+
+        * builtins/ArrayPrototype.js:
+        (sort.merge):
+
 2017-05-03  Andy VanWagoner  <thetalecrafter@gmail.com>
 

trunk/Source/JavaScriptCore/builtins/ArrayPrototype.js

@@ -544 +544 @@
         for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
             if (right < rightEnd) {
-                if (left >= leftEnd || comparator(src[right], src[left]) < 0) {
+                if (left >= leftEnd) {
                     dst[dstIndex] = src[right++];
                     continue;
                 }
+
+                let comparisonResult = comparator(src[right], src[left]);
+                if ((typeof comparisonResult === "boolean" && !comparisonResult) || comparisonResult < 0) {
+                    dst[dstIndex] = src[right++];
+                    continue;
+                }
+
             }