Diff
Modified: trunk/LayoutTests/ChangeLog (182566 => 182567)
--- trunk/LayoutTests/ChangeLog 2015-04-08 21:12:44 UTC (rev 182566)
+++ trunk/LayoutTests/ChangeLog 2015-04-08 21:14:09 UTC (rev 182567)
@@ -1,3 +1,22 @@
+2015-04-08 Filip Pizlo <[email protected]>
+
+ 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 <[email protected]>
Block popups from content extensions.
Added: trunk/LayoutTests/js/regress/script-tests/sorting-benchmark.js (0 => 182567)
--- trunk/LayoutTests/js/regress/script-tests/sorting-benchmark.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/sorting-benchmark.js 2015-04-08 21:14:09 UTC (rev 182567)
@@ -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);
+ }
+ }
+ }
+})();
Added: trunk/LayoutTests/js/regress/sorting-benchmark-expected.txt (0 => 182567)
--- trunk/LayoutTests/js/regress/sorting-benchmark-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/sorting-benchmark-expected.txt 2015-04-08 21:14:09 UTC (rev 182567)
@@ -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
+
Added: trunk/LayoutTests/js/regress/sorting-benchmark.html (0 => 182567)
--- trunk/LayoutTests/js/regress/sorting-benchmark.html (rev 0)
+++ trunk/LayoutTests/js/regress/sorting-benchmark.html 2015-04-08 21:14:09 UTC (rev 182567)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Modified: trunk/Source/_javascript_Core/ChangeLog (182566 => 182567)
--- trunk/Source/_javascript_Core/ChangeLog 2015-04-08 21:12:44 UTC (rev 182566)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-04-08 21:14:09 UTC (rev 182567)
@@ -1,5 +1,18 @@
2015-04-08 Filip Pizlo <[email protected]>
+ 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 <[email protected]>
+
DFG::IntegerCheckCombiningPhase's wrap-around check shouldn't trigger C++ undef behavior on wrap-around
https://bugs.webkit.org/show_bug.cgi?id=143532
Modified: trunk/Source/_javascript_Core/runtime/JSArray.cpp (182566 => 182567)
--- trunk/Source/_javascript_Core/runtime/JSArray.cpp 2015-04-08 21:12:44 UTC (rev 182566)
+++ trunk/Source/_javascript_Core/runtime/JSArray.cpp 2015-04-08 21:14:09 UTC (rev 182567)
@@ -1091,15 +1091,16 @@
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 @@
return;
default:
- CRASH();
+ dataLog("Indexing type: ", indexingType(), "\n");
+ RELEASE_ASSERT_NOT_REACHED();
return;
}
}
Added: trunk/Source/_javascript_Core/tests/stress/sort-array-with-undecided.js (0 => 182567)
--- trunk/Source/_javascript_Core/tests/stress/sort-array-with-undecided.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/sort-array-with-undecided.js 2015-04-08 21:14:09 UTC (rev 182567)
@@ -0,0 +1 @@
+new Array(100).sort(function(a, b) { return a - b; });
