<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[182720] releases/WebKitGTK/webkit-2.8</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/182720">182720</a></dd>
<dt>Author</dt> <dd>carlosgc@webkit.org</dd>
<dt>Date</dt> <dd>2015-04-13 05:47:17 -0700 (Mon, 13 Apr 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Merge <a href="http://trac.webkit.org/projects/webkit/changeset/182567">r182567</a> - JSArray::sortNumeric should handle ArrayWithUndecided
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.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#releasesWebKitGTKwebkit28LayoutTestsChangeLog">releases/WebKitGTK/webkit-2.8/LayoutTests/ChangeLog</a></li>
<li><a href="#releasesWebKitGTKwebkit28SourceJavaScriptCoreChangeLog">releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#releasesWebKitGTKwebkit28SourceJavaScriptCoreruntimeJSArraycpp">releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/runtime/JSArray.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#releasesWebKitGTKwebkit28LayoutTestsjsregressscripttestssortingbenchmarkjs">releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/script-tests/sorting-benchmark.js</a></li>
<li><a href="#releasesWebKitGTKwebkit28LayoutTestsjsregresssortingbenchmarkexpectedtxt">releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark-expected.txt</a></li>
<li><a href="#releasesWebKitGTKwebkit28LayoutTestsjsregresssortingbenchmarkhtml">releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark.html</a></li>
<li><a href="#releasesWebKitGTKwebkit28SourceJavaScriptCoretestsstresssortarraywithundecidedjs">releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/tests/stress/sort-array-with-undecided.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="releasesWebKitGTKwebkit28LayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.8/LayoutTests/ChangeLog (182719 => 182720)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/LayoutTests/ChangeLog 2015-04-13 12:43:01 UTC (rev 182719)
+++ releases/WebKitGTK/webkit-2.8/LayoutTests/ChangeLog 2015-04-13 12:47:17 UTC (rev 182720)
</span><span class="lines">@@ -1,3 +1,22 @@
</span><ins>+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.
+
</ins><span class="cx"> 2015-04-08 Bem Jones-Bey <bjonesbe@adobe.com>
</span><span class="cx">
</span><span class="cx"> [CSS Shapes] Properly handle negative reference box widths and center coordinates
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit28LayoutTestsjsregressscripttestssortingbenchmarkjs"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/script-tests/sorting-benchmark.js (0 => 182720)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/script-tests/sorting-benchmark.js (rev 0)
+++ releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/script-tests/sorting-benchmark.js 2015-04-13 12:47:17 UTC (rev 182720)
</span><span class="lines">@@ -0,0 +1,160 @@
</span><ins>+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);
+ }
+ }
+ }
+})();
</ins></span></pre></div>
<a id="releasesWebKitGTKwebkit28LayoutTestsjsregresssortingbenchmarkexpectedtxt"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark-expected.txt (0 => 182720)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark-expected.txt (rev 0)
+++ releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark-expected.txt 2015-04-13 12:47:17 UTC (rev 182720)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+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
+
</ins></span></pre></div>
<a id="releasesWebKitGTKwebkit28LayoutTestsjsregresssortingbenchmarkhtml"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark.html (0 => 182720)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark.html (rev 0)
+++ releases/WebKitGTK/webkit-2.8/LayoutTests/js/regress/sorting-benchmark.html 2015-04-13 12:47:17 UTC (rev 182720)
</span><span class="lines">@@ -0,0 +1,12 @@
</span><ins>+<!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>
</ins></span></pre></div>
<a id="releasesWebKitGTKwebkit28SourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/ChangeLog (182719 => 182720)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/ChangeLog 2015-04-13 12:43:01 UTC (rev 182719)
+++ releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/ChangeLog 2015-04-13 12:47:17 UTC (rev 182720)
</span><span class="lines">@@ -1,5 +1,18 @@
</span><span class="cx"> 2015-04-08 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ 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>
+
</ins><span class="cx"> DFG::IntegerCheckCombiningPhase's wrap-around check shouldn't trigger C++ undef behavior on wrap-around
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=143532
</span><span class="cx">
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit28SourceJavaScriptCoreruntimeJSArraycpp"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/runtime/JSArray.cpp (182719 => 182720)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/runtime/JSArray.cpp 2015-04-13 12:43:01 UTC (rev 182719)
+++ releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/runtime/JSArray.cpp 2015-04-13 12:47:17 UTC (rev 182720)
</span><span class="lines">@@ -1091,15 +1091,16 @@
</span><span class="cx">
</span><span class="cx"> switch (indexingType()) {
</span><span class="cx"> case ArrayClass:
</span><ins>+ case ArrayWithUndecided:
</ins><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> case ArrayWithInt32:
</span><span class="cx"> sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
</span><del>- break;
</del><ins>+ return;
</ins><span class="cx">
</span><span class="cx"> case ArrayWithDouble:
</span><span class="cx"> sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
</span><del>- break;
</del><ins>+ return;
</ins><span class="cx">
</span><span class="cx"> case ArrayWithContiguous:
</span><span class="cx"> sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
</span><span class="lines">@@ -1110,7 +1111,8 @@
</span><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> default:
</span><del>- CRASH();
</del><ins>+ dataLog("Indexing type: ", indexingType(), "\n");
+ RELEASE_ASSERT_NOT_REACHED();
</ins><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit28SourceJavaScriptCoretestsstresssortarraywithundecidedjs"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/tests/stress/sort-array-with-undecided.js (0 => 182720)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/tests/stress/sort-array-with-undecided.js (rev 0)
+++ releases/WebKitGTK/webkit-2.8/Source/JavaScriptCore/tests/stress/sort-array-with-undecided.js 2015-04-13 12:47:17 UTC (rev 182720)
</span><span class="lines">@@ -0,0 +1 @@
</span><ins>+new Array(100).sort(function(a, b) { return a - b; });
</ins></span></pre>
</div>
</div>
</body>
</html>