JSArray::sortNumeric should handle ArrayWithUndecided
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 8 Apr 2015 21:14:09 +0000 (21:14 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 8 Apr 2015 21:14:09 +0000 (21:14 +0000)
https://bugs.webkit.org/show_bug.cgi?id=143535

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

ArrayWithUndecided is what you get if you haven't stored anything into the array yet. We need to handle it.

* runtime/JSArray.cpp:
(JSC::JSArray::sortNumeric):
* tests/stress/sort-array-with-undecided.js: Added.

LayoutTests:

Upload the original test that first spotted this. Shortened it a bit so that it runs fast enough.

* js/regress/script-tests/sorting-benchmark.js: Added.
(log):
(bottom_up_merge_sort):
(aMinusB):
(verify):
(benchmark):
(makeArrays):
* js/regress/sorting-benchmark-expected.txt: Added.
* js/regress/sorting-benchmark.html: Added.

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

LayoutTests/ChangeLog
LayoutTests/js/regress/script-tests/sorting-benchmark.js [new file with mode: 0644]
LayoutTests/js/regress/sorting-benchmark-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/sorting-benchmark.html [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/JSArray.cpp
Source/JavaScriptCore/tests/stress/sort-array-with-undecided.js [new file with mode: 0644]

index 1d222b7ac01802639e659799948f567528f22a38..d996d06997fd9aa72dc7b3b1270d3332e1b68091 100644 (file)
@@ -1,3 +1,22 @@
+2015-04-08  Filip Pizlo  <fpizlo@apple.com>
+
+        JSArray::sortNumeric should handle ArrayWithUndecided
+        https://bugs.webkit.org/show_bug.cgi?id=143535
+
+        Reviewed by Geoffrey Garen.
+        
+        Upload the original test that first spotted this. Shortened it a bit so that it runs fast enough.
+
+        * js/regress/script-tests/sorting-benchmark.js: Added.
+        (log):
+        (bottom_up_merge_sort):
+        (aMinusB):
+        (verify):
+        (benchmark):
+        (makeArrays):
+        * js/regress/sorting-benchmark-expected.txt: Added.
+        * js/regress/sorting-benchmark.html: Added.
+
 2015-04-08  Alex Christensen  <achristensen@webkit.org>
 
         Block popups from content extensions.
diff --git a/LayoutTests/js/regress/script-tests/sorting-benchmark.js b/LayoutTests/js/regress/script-tests/sorting-benchmark.js
new file mode 100644 (file)
index 0000000..7d740d3
--- /dev/null
@@ -0,0 +1,160 @@
+function log(s)
+{
+}
+
+// FIXME: Clean up.
+// FIXME: Can't use global resolve or built-in functions by name.
+// FIXME: Rules about integer truncation.
+// FIXME: Need to support missing comparator.
+var bottom_up_merge_sort = (function () {
+       return function bottom_up_merge_sort(comparator)
+       {
+               var array = this;
+               var length = array.length;
+               var copy = [ ];
+
+               // Remove holes and undefineds.
+               var undefinedCount = 0;
+               for (var p in array) {
+                       var value = array[p];
+                       if (value === undefined) {
+                               ++undefinedCount;
+                               continue;
+                       }
+                       copy[copy.length] = value;
+               }
+
+               var n = copy.length;
+               var a = copy;
+               var b = array;
+
+               for (var width = 1; width < n; width = 2 * width) {
+                       for (var i = 0; i < n; i = i + 2 * width) {
+                               var iLeft = i;
+                               var iRight = Math.min(i + width, n);
+                               var iEnd = Math.min(i + 2 * width, n);
+                               var i0 = iLeft;
+                               var i1 = iRight;
+                               var j;
+
+                               for (j = iLeft; j < iEnd; j++) {
+                                       if (i0 < iRight && (i1 >= iEnd || comparator(a[i0], a[i1]) < 0)) {
+                                               b[j] = a[i0];
+                                               i0 = i0 + 1;
+                                       } else {
+                                               b[j] = a[i1];
+                                               i1 = i1 + 1;
+                                       }
+                               }
+                       }
+
+                       var tmp = a;
+                       a = b;
+                       b = tmp;
+               }
+
+           if (a != array) {
+                   for(var i = 0; i < a.length; i++)
+                       array[i] = a[i];
+           }
+
+               // Restore holes and undefineds. Result should be [ values..., undefines..., holes... ].
+               for (var i = 0; i < undefinedCount; ++i)
+                       array[array.length] = undefined;
+               array.length = length;
+       }
+})();
+
+function obfuscatedAMinusB(a, b)
+{
+       var A = a;
+       var B = b;
+       return A - B;
+}
+
+function aMinusB(a, b)
+{
+       return a - b;
+}
+
+var sortFunctions = [ Array.prototype.sort, bottom_up_merge_sort ];
+var comparators = [ aMinusB, obfuscatedAMinusB ];
+
+function verify(reference, array)
+{
+       for (var i in reference) {
+               if (array[i] !== reference[i]) {
+                       log("SORT FAIL:");
+                       log("reference: " + reference);
+                       log("array: " + array);
+                       return;
+               }
+       }
+
+       if (reference.length != array.length) {
+                       log("SORT FAIL:");
+                       log("reference.length: " + reference.length);
+                       log("array.length: " + array.length);
+       }
+}
+
+function benchmark(f, c, array)
+{
+       var start = new Date;
+       f.call(array, c);
+       var end = new Date;
+
+       // Our time resolution is not very good, so we round down small numbers to
+       // zero in order to show that they are not meaningful.
+       var result = end - start;
+       if (result < 2)
+               result = 0;
+
+       log(array.length / 1024 + "k:\t" + result + "ms");
+}
+
+function makeArrays()
+{
+       var arrays = [ ];
+       var min = 1024;
+       var max = 4 * 1024;
+       for (var count = min; count <= max; count *= 2) {
+               var array = [ ];
+               for (var i = 0; i < count; ++i)
+                       array[i] = Math.floor(Math.random() * count);
+               arrays.push(array);
+       }
+
+       arrays.push(new Array(max));
+
+       arrays.push((function() {
+               var a = [ ];
+               a[max - 1] = 1;
+               return a;
+       })());
+
+//     arrays.push((function() {
+//             var a = [ ];
+//             a[Math.pow(2, 21) - 1] = 1;
+//             return a;
+//     })());
+
+       return arrays;
+}
+
+(function main() {
+       var arrays = makeArrays();
+       for (var c of comparators) {
+               log("\n" + "===== " + c.name + " =====");
+
+               for (var f of sortFunctions) {
+                       log("\n" + f.name);
+
+                       for (var array of arrays) {
+                               var copy = array.slice();
+                               benchmark(f, c, copy);
+                               verify(Array.prototype.sort.call(array.slice(), c), copy);
+                       }
+               }
+       }
+})();
diff --git a/LayoutTests/js/regress/sorting-benchmark-expected.txt b/LayoutTests/js/regress/sorting-benchmark-expected.txt
new file mode 100644 (file)
index 0000000..eceb94d
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/sorting-benchmark
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/js/regress/sorting-benchmark.html b/LayoutTests/js/regress/sorting-benchmark.html
new file mode 100644 (file)
index 0000000..7e2fdce
--- /dev/null
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/sorting-benchmark.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
index b0c1fbf4832662c00cfcb70ab180d342ee27e210..bce72e6b36900622b60d81305fef6bc1989a86ab 100644 (file)
@@ -1,3 +1,16 @@
+2015-04-08  Filip Pizlo  <fpizlo@apple.com>
+
+        JSArray::sortNumeric should handle ArrayWithUndecided
+        https://bugs.webkit.org/show_bug.cgi?id=143535
+
+        Reviewed by Geoffrey Garen.
+        
+        ArrayWithUndecided is what you get if you haven't stored anything into the array yet. We need to handle it.
+
+        * runtime/JSArray.cpp:
+        (JSC::JSArray::sortNumeric):
+        * tests/stress/sort-array-with-undecided.js: Added.
+
 2015-04-08  Filip Pizlo  <fpizlo@apple.com>
 
         DFG::IntegerCheckCombiningPhase's wrap-around check shouldn't trigger C++ undef behavior on wrap-around
index 824f6b70acab9ead797a6f79c95f48198513cc46..76514d480ce7d02fd3cee0311814e162a3c79525 100644 (file)
@@ -1091,15 +1091,16 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal
 
     switch (indexingType()) {
     case ArrayClass:
+    case ArrayWithUndecided:
         return;
         
     case ArrayWithInt32:
         sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
-        break;
+        return;
         
     case ArrayWithDouble:
         sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
-        break;
+        return;
         
     case ArrayWithContiguous:
         sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
@@ -1110,7 +1111,8 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal
         return;
         
     default:
-        CRASH();
+        dataLog("Indexing type: ", indexingType(), "\n");
+        RELEASE_ASSERT_NOT_REACHED();
         return;
     }
 }
diff --git a/Source/JavaScriptCore/tests/stress/sort-array-with-undecided.js b/Source/JavaScriptCore/tests/stress/sort-array-with-undecided.js
new file mode 100644 (file)
index 0000000..4a00943
--- /dev/null
@@ -0,0 +1 @@
+new Array(100).sort(function(a, b) { return a - b; });