<!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>[183308] trunk</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/183308">183308</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2015-04-24 23:57:12 -0700 (Fri, 24 Apr 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Unreviewed, rolling out <a href="http://trac.webkit.org/projects/webkit/changeset/183288">r183288</a>.
https://bugs.webkit.org/show_bug.cgi?id=144189
Made js/sort-with-side-effecting-comparisons.html time out in
debug builds (Requested by ap on #webkit).
Reverted changeset:
"It shouldn't take 1846 lines of code and 5 FIXMEs to sort an
array."
https://bugs.webkit.org/show_bug.cgi?id=144013
http://trac.webkit.org/changeset/183288</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkLayoutTestsjsarrayholesexpectedtxt">trunk/LayoutTests/js/array-holes-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsarraysortsparseexpectedtxt">trunk/LayoutTests/js/array-sort-sparse-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjscomparefnsortstabilityexpectedtxt">trunk/LayoutTests/js/comparefn-sort-stability-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsdomarrayprototypepropertiesexpectedtxt">trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsscripttestsarrayholesjs">trunk/LayoutTests/js/script-tests/array-holes.js</a></li>
<li><a href="#trunkLayoutTestsjsscripttestsarraysortsparsejs">trunk/LayoutTests/js/script-tests/array-sort-sparse.js</a></li>
<li><a href="#trunkLayoutTestsjsscripttestscomparefnsortstabilityjs">trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCorebuiltinsArrayprototypejs">trunk/Source/JavaScriptCore/builtins/Array.prototype.js</a></li>
<li><a href="#trunkSourceJavaScriptCorebuiltinsBuiltinExecutablescpp">trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeCodeBlockh">trunk/Source/JavaScriptCore/bytecode/CodeBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockcpp">trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockh">trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorcpp">trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorh">trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecompilerNodesCodegencpp">trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapHeapcpp">trunk/Source/JavaScriptCore/heap/Heap.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreheapHeaph">trunk/Source/JavaScriptCore/heap/Heap.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreparserParsercpp">trunk/Source/JavaScriptCore/parser/Parser.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeArrayPrototypecpp">trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeCommonIdentifiersh">trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSArraycpp">trunk/Source/JavaScriptCore/runtime/JSArray.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSArrayh">trunk/Source/JavaScriptCore/runtime/JSArray.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSGlobalObjectcpp">trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeObjectConstructorcpp">trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFvcxprojWTFvcxproj">trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj</a></li>
<li><a href="#trunkSourceWTFWTFvcxprojWTFvcxprojfilters">trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfAVLTreeh">trunk/Source/WTF/wtf/AVLTree.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/ChangeLog 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2015-04-24 Commit Queue <commit-queue@webkit.org>
+
+ Unreviewed, rolling out r183288.
+ https://bugs.webkit.org/show_bug.cgi?id=144189
+
+ Made js/sort-with-side-effecting-comparisons.html time out in
+ debug builds (Requested by ap on #webkit).
+
+ Reverted changeset:
+
+ "It shouldn't take 1846 lines of code and 5 FIXMEs to sort an
+ array."
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+ http://trac.webkit.org/changeset/183288
+
</ins><span class="cx"> 2015-04-24 Myles C. Maxfield <mmaxfield@apple.com>
</span><span class="cx">
</span><span class="cx"> Implement parsing support for font-synthesis CSS property
</span></span></pre></div>
<a id="trunkLayoutTestsjsarrayholesexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/array-holes-expected.txt (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/array-holes-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/array-holes-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -36,7 +36,7 @@
</span><span class="cx"> PASS showHoles([0, , 2, 3].reverse()) is '[3, 2, peekaboo, 0]'
</span><span class="cx"> PASS a = [0, , 2, 3]; a.shift(); showHoles(a) is '[peekaboo, 2, 3]'
</span><span class="cx"> PASS showHoles([0, , 2, 3].slice(0, 3)) is '[0, peekaboo, 2]'
</span><del>-PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, peekaboo]'
</del><ins>+PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, hole]'
</ins><span class="cx"> PASS showHoles([0, undefined, 2, 3].sort()) is '[0, 2, 3, undefined]'
</span><span class="cx"> PASS a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a) is '[0, hole, 5, 6]'
</span><span class="cx"> PASS a = [0, , 2, 3]; a.unshift(4); showHoles(a) is '[4, 0, peekaboo, 2, 3]'
</span></span></pre></div>
<a id="trunkLayoutTestsjsarraysortsparseexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/array-sort-sparse-expected.txt (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/array-sort-sparse-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/array-sort-sparse-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -5,11 +5,6 @@
</span><span class="cx">
</span><span class="cx"> PASS testSort([,undefined,0,1]) is true
</span><span class="cx"> PASS testSort({length:4,1:undefined,2:0,3:1}) is true
</span><del>-PASS 0 in array is true
-PASS 1 in array is false
-PASS 0 in array is true
-PASS 1 in array is false
-PASS 2 in array is false
</del><span class="cx"> PASS successfullyParsed is true
</span><span class="cx">
</span><span class="cx"> TEST COMPLETE
</span></span></pre></div>
<a id="trunkLayoutTestsjscomparefnsortstabilityexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/comparefn-sort-stability-expected.txt (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/comparefn-sort-stability-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/comparefn-sort-stability-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -3,206 +3,14 @@
</span><span class="cx"> On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
</span><span class="cx">
</span><span class="cx">
</span><del>-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
</del><ins>+PASS arr[0] is sortArr[0]
+PASS arr[1] is sortArr[2]
+PASS arr[2] is sortArr[1]
+PASS arr[3] is sortArr[3]
+PASS arr[0] is sortArr[0]
+PASS arr[1] is sortArr[2]
+PASS arr[2] is sortArr[1]
+PASS arr[3] is sortArr[3]
</ins><span class="cx"> PASS successfullyParsed is true
</span><span class="cx">
</span><span class="cx"> TEST COMPLETE
</span></span></pre></div>
<a id="trunkLayoutTestsjsdomarrayprototypepropertiesexpectedtxt"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -12,7 +12,7 @@
</span><span class="cx"> PASS Array.prototype.reverse.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.reverse.call(undefined)').
</span><span class="cx"> PASS Array.prototype.shift.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.shift.call(undefined)').
</span><span class="cx"> PASS Array.prototype.slice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.slice.call(undefined, 0, 1)').
</span><del>-PASS Array.prototype.sort.call(undefined) threw exception TypeError: Array.prototype.sort requires that |this| not be undefined.
</del><ins>+PASS Array.prototype.sort.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.sort.call(undefined)').
</ins><span class="cx"> PASS Array.prototype.splice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.splice.call(undefined, 0, 1)').
</span><span class="cx"> PASS Array.prototype.unshift.call(undefined, {}) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.unshift.call(undefined, {})').
</span><span class="cx"> PASS Array.prototype.every.call(undefined, toString) threw exception TypeError: Array.prototype.every requires that |this| not be undefined.
</span></span></pre></div>
<a id="trunkLayoutTestsjsscripttestsarrayholesjs"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/script-tests/array-holes.js (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/script-tests/array-holes.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/script-tests/array-holes.js 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -87,7 +87,7 @@
</span><span class="cx"> shouldBe("showHoles([0, , 2, 3].reverse())", "'[3, 2, peekaboo, 0]'");
</span><span class="cx"> shouldBe("a = [0, , 2, 3]; a.shift(); showHoles(a)", "'[peekaboo, 2, 3]'");
</span><span class="cx"> shouldBe("showHoles([0, , 2, 3].slice(0, 3))", "'[0, peekaboo, 2]'");
</span><del>-shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, peekaboo]'");
</del><ins>+shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, hole]'");
</ins><span class="cx"> shouldBe("showHoles([0, undefined, 2, 3].sort())", "'[0, 2, 3, undefined]'");
</span><span class="cx"> shouldBe("a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a)", "'[0, hole, 5, 6]'");
</span><span class="cx"> shouldBe("a = [0, , 2, 3]; a.unshift(4); showHoles(a)", "'[4, 0, peekaboo, 2, 3]'");
</span></span></pre></div>
<a id="trunkLayoutTestsjsscripttestsarraysortsparsejs"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/script-tests/array-sort-sparse.js (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/script-tests/array-sort-sparse.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/script-tests/array-sort-sparse.js 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -10,14 +10,3 @@
</span><span class="cx">
</span><span class="cx"> shouldBeTrue("testSort([,undefined,0,1])");
</span><span class="cx"> shouldBeTrue("testSort({length:4,1:undefined,2:0,3:1})");
</span><del>-
-var array = [ , undefined ];
-array.sort();
-shouldBeTrue("0 in array");
-shouldBeFalse("1 in array");
-
-var array = [ , 1, , ];
-array.sort();
-shouldBeTrue("0 in array");
-shouldBeFalse("1 in array");
-shouldBeFalse("2 in array");
</del></span></pre></div>
<a id="trunkLayoutTestsjsscripttestscomparefnsortstabilityjs"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -2,25 +2,30 @@
</span><span class="cx"> "This tests that sort(compareFn) is a stable sort."
</span><span class="cx"> );
</span><span class="cx">
</span><del>-var count = 100;
</del><ins>+function clone(source, target) {
+ for (i = 0; i < source.length; i++) {
+ target[i] = source[i];
+ }
+}
</ins><span class="cx">
</span><del>-var ones = [];
-for (var i = 0; i < count; ++i)
- ones.push(new Number(1));
</del><ins>+var arr = [];
+arr[0] = new Number(1);
+arr[1] = new Number(2);
+arr[2] = new Number(1);
+arr[3] = new Number(2);
</ins><span class="cx">
</span><del>-var twos = [];
-for (var i = 0; i < count; ++i)
- twos.push(new Number(2));
</del><ins>+var sortArr = [];
+clone(arr, sortArr);
+sortArr.sort(function(a,b) { return a - b; });
</ins><span class="cx">
</span><del>-var array = [];
-for (var i = 0; i < count; ++i) {
- array.push(ones[i]);
- array.push(twos[i]);
-}
</del><ins>+shouldBe('arr[0]', 'sortArr[0]');
+shouldBe('arr[1]', 'sortArr[2]');
+shouldBe('arr[2]', 'sortArr[1]');
+shouldBe('arr[3]', 'sortArr[3]');
</ins><span class="cx">
</span><del>-array.sort(function(a,b) { return a - b; });
-for (var i = 0; i < count; ++i)
- shouldBe('array[i]', 'ones[i]');
-
-for (var i = 0; i < count; ++i)
- shouldBe('array[count + i]', 'twos[i]');
</del><ins>+// Just try again...
+sortArr.sort(function(a,b) { return a - b; });
+shouldBe('arr[0]', 'sortArr[0]');
+shouldBe('arr[1]', 'sortArr[2]');
+shouldBe('arr[2]', 'sortArr[1]');
+shouldBe('arr[3]', 'sortArr[3]');
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2015-04-24 Commit Queue <commit-queue@webkit.org>
+
+ Unreviewed, rolling out r183288.
+ https://bugs.webkit.org/show_bug.cgi?id=144189
+
+ Made js/sort-with-side-effecting-comparisons.html time out in
+ debug builds (Requested by ap on #webkit).
+
+ Reverted changeset:
+
+ "It shouldn't take 1846 lines of code and 5 FIXMEs to sort an
+ array."
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+ http://trac.webkit.org/changeset/183288
+
</ins><span class="cx"> 2015-04-24 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> CRASH in operationCreateDirectArgumentsDuringExit()
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebuiltinsArrayprototypejs"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/builtins/Array.prototype.js (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/builtins/Array.prototype.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/builtins/Array.prototype.js 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -277,185 +277,3 @@
</span><span class="cx"> }
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><del>-
-function sort(comparator)
-{
- "use strict";
-
- function min(a, b)
- {
- return a < b ? a : b;
- }
-
- function stringComparator(a, b)
- {
- var aString = @String(a);
- var bString = @String(b);
-
- var aLength = aString.length;
- var bLength = bString.length;
- var length = min(aLength, bLength);
-
- for (var i = 0; i < length; ++i) {
- var aCharCode = aString.@charCodeAt(i);
- var bCharCode = bString.@charCodeAt(i);
-
- if (aCharCode == bCharCode)
- continue;
-
- if (aCharCode < bCharCode)
- return -1;
-
- return 1;
- }
-
- if (aLength == bLength)
- return 0;
-
- if (aLength < bLength)
- return -1;
-
- return 1;
- }
-
- // Move undefineds and holes to the end of a sparse array. Result is [values..., undefineds..., holes...].
- function compactSparse(array, dst, src, length)
- {
- var values = [ ];
- var seen = { };
- var valueCount = 0;
- var undefinedCount = 0;
-
- // Clean up after the in-progress non-sparse compaction that failed.
- for (var i = dst; i < src; ++i)
- delete array[i];
-
- for (var object = array; object; object = @Object.@getPrototypeOf(object)) {
- var propertyNames = @Object.@getOwnPropertyNames(object);
- for (var i = 0; i < propertyNames.length; ++i) {
- var index = propertyNames[i];
- if (index < length) { // Exclude non-numeric properties and properties past length.
- if (seen[index]) // Exclude duplicates.
- continue;
- seen[index] = 1;
-
- var value = array[index];
- delete array[index];
-
- if (value === undefined) {
- ++undefinedCount;
- continue;
- }
-
- array[valueCount++] = value;
- }
- }
- }
-
- for (var i = valueCount; i < valueCount + undefinedCount; ++i)
- array[i] = undefined;
-
- return valueCount;
- }
-
- // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
- function compact(array, length)
- {
- var holeCount = 0;
-
- for (var dst = 0, src = 0; src < length; ++src) {
- if (!(src in array)) {
- ++holeCount;
- if (holeCount < 256)
- continue;
- return compactSparse(array, dst, src, length);
- }
-
- var value = array[src];
- if (value === undefined)
- continue;
- array[dst++] = value;
- }
-
- var valueCount = dst;
- var undefinedCount = length - valueCount - holeCount;
-
- for (var i = valueCount; i < valueCount + undefinedCount; ++i)
- array[i] = undefined;
-
- for (var i = valueCount + undefinedCount; i < length; ++i)
- delete array[i];
-
- return valueCount;
- }
-
- function merge(dst, src, srcIndex, srcEnd, width, comparator)
- {
- var left = srcIndex;
- var leftEnd = min(left + width, srcEnd);
- var right = leftEnd;
- var rightEnd = min(right + width, srcEnd);
-
- for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
- if (right < rightEnd) {
- if (left >= leftEnd || comparator(src[left], src[right]) > 0) {
- dst[dstIndex] = src[right++];
- continue;
- }
- }
-
- dst[dstIndex] = src[left++];
- }
- }
-
- function mergeSort(array, valueCount, comparator)
- {
- var buffer = [ ];
- buffer.length = valueCount;
-
- var dst = buffer;
- var src = array;
- for (var width = 1; width < valueCount; width *= 2) {
- for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
- merge(dst, src, srcIndex, valueCount, width, comparator);
-
- var tmp = src;
- src = dst;
- dst = tmp;
- }
-
- if (src != array) {
- for(var i = 0; i < valueCount; i++)
- array[i] = src[i];
- }
- }
-
- function comparatorSort(array, comparator)
- {
- var length = array.length >>> 0;
-
- // For compatibility with Firefox and Chrome, do nothing observable
- // to the target array if it has 0 or 1 sortable properties.
- if (length < 2)
- return;
-
- var valueCount = compact(array, length);
- mergeSort(array, valueCount, comparator);
- }
-
- if (this === null)
- throw new @TypeError("Array.prototype.sort requires that |this| not be null");
-
- if (this === undefined)
- throw new @TypeError("Array.prototype.sort requires that |this| not be undefined");
-
- if (typeof this == "string")
- throw new @TypeError("Attempted to assign to readonly property.");
-
- if (typeof comparator !== "function")
- comparator = stringComparator;
-
- var array = @Object(this);
- comparatorSort(array, comparator);
- return array;
-}
</del></span></pre></div>
<a id="trunkSourceJavaScriptCorebuiltinsBuiltinExecutablescpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/builtins/BuiltinExecutables.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -101,6 +101,7 @@
</span><span class="cx">
</span><span class="cx"> if (closedVariable == m_vm.propertyNames->undefinedKeyword.impl())
</span><span class="cx"> continue;
</span><ins>+ RELEASE_ASSERT(m_vm.propertyNames->isPrivateName(closedVariable.get()));
</ins><span class="cx"> }
</span><span class="cx"> body->overrideName(name);
</span><span class="cx"> UnlinkedFunctionExecutable* functionExecutable = UnlinkedFunctionExecutable::create(&m_vm, source, body, kind, WTF::move(sourceOverride));
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeCodeBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/CodeBlock.h (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/CodeBlock.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/bytecode/CodeBlock.h 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -249,6 +249,8 @@
</span><span class="cx"> return static_cast<Instruction*>(returnAddress) - instructions().begin();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ bool isNumericCompareFunction() { return m_unlinkedCode->isNumericCompareFunction(); }
+
</ins><span class="cx"> unsigned numberOfInstructions() const { return m_instructions.size(); }
</span><span class="cx"> RefCountedArray<Instruction>& instructions() { return m_instructions; }
</span><span class="cx"> const RefCountedArray<Instruction>& instructions() const { return m_instructions; }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -241,6 +241,7 @@
</span><span class="cx"> , m_globalObjectRegister(VirtualRegister())
</span><span class="cx"> , m_needsFullScopeChain(info.needsActivation())
</span><span class="cx"> , m_usesEval(info.usesEval())
</span><ins>+ , m_isNumericCompareFunction(false)
</ins><span class="cx"> , m_isStrictMode(info.isStrictMode())
</span><span class="cx"> , m_isConstructor(info.isConstructor())
</span><span class="cx"> , m_hasCapturedVariables(false)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeUnlinkedCodeBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -344,6 +344,9 @@
</span><span class="cx"> unsigned jumpTarget(int index) const { return m_jumpTargets[index]; }
</span><span class="cx"> unsigned lastJumpTarget() const { return m_jumpTargets.last(); }
</span><span class="cx">
</span><ins>+ void setIsNumericCompareFunction(bool isNumericCompareFunction) { m_isNumericCompareFunction = isNumericCompareFunction; }
+ bool isNumericCompareFunction() const { return m_isNumericCompareFunction; }
+
</ins><span class="cx"> bool isBuiltinFunction() const { return m_isBuiltinFunction; }
</span><span class="cx">
</span><span class="cx"> ConstructorKind constructorKind() const { return static_cast<ConstructorKind>(m_constructorKind); }
</span><span class="lines">@@ -533,6 +536,7 @@
</span><span class="cx">
</span><span class="cx"> unsigned m_needsFullScopeChain : 1;
</span><span class="cx"> unsigned m_usesEval : 1;
</span><ins>+ unsigned m_isNumericCompareFunction : 1;
</ins><span class="cx"> unsigned m_isStrictMode : 1;
</span><span class="cx"> unsigned m_isConstructor : 1;
</span><span class="cx"> unsigned m_hasCapturedVariables : 1;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -2603,6 +2603,11 @@
</span><span class="cx"> return newTemporary();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void BytecodeGenerator::setIsNumericCompareFunction(bool isNumericCompareFunction)
+{
+ m_codeBlock->setIsNumericCompareFunction(isNumericCompareFunction);
+}
+
</ins><span class="cx"> bool BytecodeGenerator::isArgumentNumber(const Identifier& ident, int argumentNumber)
</span><span class="cx"> {
</span><span class="cx"> RegisterID* registerID = variable(ident).local();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecompilerBytecodeGeneratorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -276,6 +276,8 @@
</span><span class="cx">
</span><span class="cx"> bool isArgumentNumber(const Identifier&, int);
</span><span class="cx">
</span><ins>+ void setIsNumericCompareFunction(bool isNumericCompareFunction);
+
</ins><span class="cx"> Variable variable(const Identifier&);
</span><span class="cx">
</span><span class="cx"> // Ignores the possibility of intervening scopes.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecompilerNodesCodegencpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -2821,6 +2821,22 @@
</span><span class="cx"> generator.emitReturn(r0);
</span><span class="cx"> return;
</span><span class="cx"> }
</span><ins>+
+ // If there is a return statment, and it is the only statement in the function, check if this is a numeric compare.
+ if (static_cast<BlockNode*>(singleStatement)->singleStatement()) {
+ ExpressionNode* returnValueExpression = returnNode->value();
+ if (returnValueExpression && returnValueExpression->isSubtract()) {
+ ExpressionNode* lhsExpression = static_cast<SubNode*>(returnValueExpression)->lhs();
+ ExpressionNode* rhsExpression = static_cast<SubNode*>(returnValueExpression)->rhs();
+ if (lhsExpression->isResolveNode()
+ && rhsExpression->isResolveNode()
+ && generator.isArgumentNumber(static_cast<ResolveNode*>(lhsExpression)->identifier(), 0)
+ && generator.isArgumentNumber(static_cast<ResolveNode*>(rhsExpression)->identifier(), 1)) {
+
+ generator.setIsNumericCompareFunction(true);
+ }
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // ------------------------------ FuncDeclNode ---------------------------------
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapHeapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/Heap.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/Heap.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/heap/Heap.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -481,6 +481,17 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Heap::pushTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>* tempVector)
+{
+ m_tempSortingVectors.append(tempVector);
+}
+
+void Heap::popTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>* tempVector)
+{
+ ASSERT_UNUSED(tempVector, tempVector == m_tempSortingVectors.last());
+ m_tempSortingVectors.removeLast();
+}
+
</ins><span class="cx"> void Heap::harvestWeakReferences()
</span><span class="cx"> {
</span><span class="cx"> m_slotVisitor.harvestWeakReferences();
</span><span class="lines">@@ -560,6 +571,7 @@
</span><span class="cx"> visitSmallStrings();
</span><span class="cx"> visitConservativeRoots(conservativeRoots);
</span><span class="cx"> visitProtectedObjects(heapRootVisitor);
</span><ins>+ visitTempSortVectors(heapRootVisitor);
</ins><span class="cx"> visitArgumentBuffers(heapRootVisitor);
</span><span class="cx"> visitException(heapRootVisitor);
</span><span class="cx"> visitStrongHandles(heapRootVisitor);
</span><span class="lines">@@ -698,6 +710,23 @@
</span><span class="cx"> m_slotVisitor.donateAndDrain();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Heap::visitTempSortVectors(HeapRootVisitor& heapRootVisitor)
+{
+ GCPHASE(VisitTempSortVectors);
+
+ for (auto* vector : m_tempSortingVectors) {
+ for (auto& valueStringPair : *vector) {
+ if (valueStringPair.first)
+ heapRootVisitor.visit(&valueStringPair.first);
+ }
+ }
+
+ if (Options::logGC() == GCLogging::Verbose)
+ dataLog("Temp Sort Vectors:\n", m_slotVisitor);
+
+ m_slotVisitor.donateAndDrain();
+}
+
</ins><span class="cx"> void Heap::visitArgumentBuffers(HeapRootVisitor& visitor)
</span><span class="cx"> {
</span><span class="cx"> GCPHASE(MarkingArgumentBuffers);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreheapHeaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/heap/Heap.h (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/heap/Heap.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/heap/Heap.h 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -75,6 +75,7 @@
</span><span class="cx">
</span><span class="cx"> static void* const zombifiedBits = reinterpret_cast<void*>(0xdeadbeef);
</span><span class="cx">
</span><ins>+typedef std::pair<JSValue, WTF::String> ValueStringPair;
</ins><span class="cx"> typedef HashCountedSet<JSCell*> ProtectCountSet;
</span><span class="cx"> typedef HashCountedSet<const char*> TypeCountSet;
</span><span class="cx">
</span><span class="lines">@@ -185,6 +186,9 @@
</span><span class="cx"> JS_EXPORT_PRIVATE std::unique_ptr<TypeCountSet> objectTypeCounts();
</span><span class="cx"> void showStatistics();
</span><span class="cx">
</span><ins>+ void pushTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
+ void popTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
+
</ins><span class="cx"> HashSet<MarkedArgumentBuffer*>& markListSet();
</span><span class="cx">
</span><span class="cx"> template<typename Functor> typename Functor::ReturnType forEachProtectedCell(Functor&);
</span><span class="lines">@@ -296,6 +300,7 @@
</span><span class="cx"> void visitCompilerWorklistWeakReferences();
</span><span class="cx"> void removeDeadCompilerWorklistEntries();
</span><span class="cx"> void visitProtectedObjects(HeapRootVisitor&);
</span><ins>+ void visitTempSortVectors(HeapRootVisitor&);
</ins><span class="cx"> void visitArgumentBuffers(HeapRootVisitor&);
</span><span class="cx"> void visitException(HeapRootVisitor&);
</span><span class="cx"> void visitStrongHandles(HeapRootVisitor&);
</span><span class="lines">@@ -366,6 +371,7 @@
</span><span class="cx"> HashSet<const JSCell*> m_copyingRememberedSet;
</span><span class="cx">
</span><span class="cx"> ProtectCountSet m_protectedValues;
</span><ins>+ Vector<Vector<ValueStringPair, 0, UnsafeVectorOverflow>*> m_tempSortingVectors;
</ins><span class="cx"> std::unique_ptr<HashSet<MarkedArgumentBuffer*>> m_markListSet;
</span><span class="cx">
</span><span class="cx"> MachineThreads m_machineThreads;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreparserParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/parser/Parser.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/parser/Parser.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/parser/Parser.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -288,6 +288,7 @@
</span><span class="cx"> features |= ModifiedArgumentsFeature;
</span><span class="cx"> Vector<RefPtr<StringImpl>> closedVariables;
</span><span class="cx"> if (m_parsingBuiltin) {
</span><ins>+ RELEASE_ASSERT(!capturedVariables.size());
</ins><span class="cx"> IdentifierSet usedVariables;
</span><span class="cx"> scope->getUsedVariables(usedVariables);
</span><span class="cx"> for (const auto& variable : usedVariables) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeArrayPrototypecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -54,6 +54,7 @@
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
</span><ins>+EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*);
</ins><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
</span><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
</span><span class="lines">@@ -69,6 +70,21 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="cx">
</span><ins>+static inline bool isNumericCompareFunction(ExecState* exec, JSValue function, CallType callType, const CallData& callData)
+{
+ if (callType != CallTypeJS)
+ return false;
+
+ FunctionExecutable* executable = callData.js.functionExecutable;
+ JSScope* scope = callData.js.scope;
+
+ JSObject* error = executable->prepareForExecution(exec, jsCast<JSFunction*>(function), scope, CodeForCall);
+ if (error)
+ return false;
+
+ return executable->codeBlockForCall()->isNumericCompareFunction();
+}
+
</ins><span class="cx"> // ------------------------------ ArrayPrototype ----------------------------
</span><span class="cx">
</span><span class="cx"> const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, &arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)};
</span><span class="lines">@@ -638,6 +654,155 @@
</span><span class="cx"> return JSValue();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+static bool attemptFastSort(ExecState* exec, JSObject* thisObj, JSValue function, CallData& callData, CallType& callType)
+{
+ if (thisObj->classInfo() != JSArray::info()
+ || asArray(thisObj)->hasSparseMap()
+ || shouldUseSlowPut(thisObj->indexingType()))
+ return false;
+
+ if (isNumericCompareFunction(exec, function, callType, callData))
+ asArray(thisObj)->sortNumeric(exec, function, callType, callData);
+ else if (callType != CallTypeNone)
+ asArray(thisObj)->sort(exec, function, callType, callData);
+ else
+ asArray(thisObj)->sort(exec);
+ return true;
+}
+
+static bool performSlowSort(ExecState* exec, JSObject* thisObj, unsigned length, JSValue function, CallData& callData, CallType& callType)
+{
+ // "Min" sort. Not the fastest, but definitely less code than heapsort
+ // or quicksort, and much less swapping than bubblesort/insertionsort.
+ for (unsigned i = 0; i < length - 1; ++i) {
+ JSValue iObj = getOrHole(thisObj, exec, i);
+ if (exec->hadException())
+ return false;
+ unsigned themin = i;
+ JSValue minObj = iObj;
+ for (unsigned j = i + 1; j < length; ++j) {
+ JSValue jObj = getOrHole(thisObj, exec, j);
+ if (exec->hadException())
+ return false;
+ double compareResult;
+ if (!jObj)
+ compareResult = 1;
+ else if (!minObj)
+ compareResult = -1;
+ else if (jObj.isUndefined())
+ compareResult = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
+ else if (minObj.isUndefined())
+ compareResult = -1;
+ else if (callType != CallTypeNone) {
+ MarkedArgumentBuffer l;
+ l.append(jObj);
+ l.append(minObj);
+ compareResult = call(exec, function, callType, callData, jsUndefined(), l).toNumber(exec);
+ } else
+ compareResult = codePointCompareLessThan(jObj.toWTFStringInline(exec), minObj.toWTFStringInline(exec)) ? -1 : 1;
+
+ if (compareResult < 0) {
+ themin = j;
+ minObj = jObj;
+ }
+ }
+ // Swap themin and i
+ if (themin > i) {
+ if (minObj) {
+ thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, minObj, true);
+ if (exec->hadException())
+ return false;
+ } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, i)) {
+ throwTypeError(exec, ASCIILiteral("Unable to delete property."));
+ return false;
+ }
+ if (iObj) {
+ thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, themin, iObj, true);
+ if (exec->hadException())
+ return false;
+ } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, themin)) {
+ throwTypeError(exec, ASCIILiteral("Unable to delete property."));
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec)
+{
+ JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
+ unsigned length = getLength(exec, thisObj);
+ if (!length || exec->hadException())
+ return JSValue::encode(thisObj);
+
+ JSValue function = exec->argument(0);
+ CallData callData;
+ CallType callType = getCallData(function, callData);
+
+ if (attemptFastSort(exec, thisObj, function, callData, callType))
+ return JSValue::encode(thisObj);
+
+ // Assume that for small-ish arrays, doing the slow sort directly is better.
+ if (length < 1000)
+ return performSlowSort(exec, thisObj, length, function, callData, callType) ? JSValue::encode(thisObj) : JSValue::encode(jsUndefined());
+
+ JSGlobalObject* globalObject = JSGlobalObject::create(
+ exec->vm(), JSGlobalObject::createStructure(exec->vm(), jsNull()));
+ JSArray* flatArray = constructEmptyArray(globalObject->globalExec(), nullptr);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+
+ PropertyNameArray nameArray(exec);
+ thisObj->methodTable(exec->vm())->getPropertyNames(thisObj, exec, nameArray, EnumerationMode(DontEnumPropertiesMode::Include));
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+
+ Vector<uint32_t, 0, UnsafeVectorOverflow> keys;
+ for (size_t i = 0; i < nameArray.size(); ++i) {
+ PropertyName name = nameArray[i];
+ Optional<uint32_t> optionalIndex = parseIndex(name);
+ if (!optionalIndex)
+ continue;
+
+ uint32_t index = optionalIndex.value();
+ JSValue value = getOrHole(thisObj, exec, index);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ if (!value)
+ continue;
+ keys.append(index);
+ flatArray->push(exec, value);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ }
+
+ if (!attemptFastSort(exec, flatArray, function, callData, callType)
+ && !performSlowSort(exec, flatArray, flatArray->length(), function, callData, callType))
+ return JSValue::encode(jsUndefined());
+
+ for (size_t i = 0; i < keys.size(); ++i) {
+ size_t index = keys[i];
+ if (index < flatArray->length())
+ continue;
+
+ if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, index)) {
+ throwTypeError(exec, ASCIILiteral("Unable to delete property."));
+ return JSValue::encode(jsUndefined());
+ }
+ }
+
+ for (size_t i = flatArray->length(); i--;) {
+ JSValue value = getOrHole(flatArray, exec, i);
+ RELEASE_ASSERT(value);
+ thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, value, true);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ }
+
+ return JSValue::encode(thisObj);
+}
+
</ins><span class="cx"> EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
</span><span class="cx"> {
</span><span class="cx"> // 15.4.4.12
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeCommonIdentifiersh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/runtime/CommonIdentifiers.h 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -269,12 +269,9 @@
</span><span class="cx"> macro(objectGetOwnPropertySymbols) \
</span><span class="cx"> macro(Number) \
</span><span class="cx"> macro(Array) \
</span><del>- macro(String) \
</del><span class="cx"> macro(abs) \
</span><span class="cx"> macro(floor) \
</span><span class="cx"> macro(isFinite) \
</span><del>- macro(getPrototypeOf) \
- macro(getOwnPropertyNames) \
</del><span class="cx"> macro(TypeError) \
</span><span class="cx"> macro(undefined) \
</span><span class="cx"> macro(BuiltinLog) \
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSArraycpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSArray.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSArray.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/runtime/JSArray.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -34,6 +34,7 @@
</span><span class="cx"> #include "JSCInlines.h"
</span><span class="cx"> #include "PropertyNameArray.h"
</span><span class="cx"> #include "Reject.h"
</span><ins>+#include <wtf/AVLTree.h>
</ins><span class="cx"> #include <wtf/Assertions.h>
</span><span class="cx">
</span><span class="cx"> using namespace std;
</span><span class="lines">@@ -993,6 +994,521 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+static int compareNumbersForQSortWithInt32(const void* a, const void* b)
+{
+ int32_t ia = static_cast<const JSValue*>(a)->asInt32();
+ int32_t ib = static_cast<const JSValue*>(b)->asInt32();
+ return ia - ib;
+}
+
+static int compareNumbersForQSortWithDouble(const void* a, const void* b)
+{
+ double da = *static_cast<const double*>(a);
+ double db = *static_cast<const double*>(b);
+ return (da > db) - (da < db);
+}
+
+static int compareNumbersForQSort(const void* a, const void* b)
+{
+ double da = static_cast<const JSValue*>(a)->asNumber();
+ double db = static_cast<const JSValue*>(b)->asNumber();
+ return (da > db) - (da < db);
+}
+
+static int compareByStringPairForQSort(const void* a, const void* b)
+{
+ const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
+ const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
+ return codePointCompare(va->second, vb->second);
+}
+
+template<IndexingType arrayIndexingType>
+void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(arrayIndexingType == ArrayWithInt32 || arrayIndexingType == ArrayWithDouble || arrayIndexingType == ArrayWithContiguous || arrayIndexingType == ArrayWithArrayStorage);
+
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<arrayIndexingType>(
+ lengthNotIncludingUndefined,
+ newRelevantLength);
+
+ ContiguousJSValues data = indexingData<arrayIndexingType>();
+
+ if (arrayIndexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
+ throwOutOfMemoryError(exec);
+ return;
+ }
+
+ if (!lengthNotIncludingUndefined)
+ return;
+
+ bool allValuesAreNumbers = true;
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ break;
+
+ default:
+ for (size_t i = 0; i < newRelevantLength; ++i) {
+ if (!data[i].isNumber()) {
+ allValuesAreNumbers = false;
+ break;
+ }
+ }
+ break;
+ }
+
+ if (!allValuesAreNumbers)
+ return sort(exec, compareFunction, callType, callData);
+
+ // For numeric comparison, which is fast, qsort is faster than mergesort. We
+ // also don't require mergesort's stability, since there's no user visible
+ // side-effect from swapping the order of equal primitive values.
+ int (*compare)(const void*, const void*);
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ compare = compareNumbersForQSortWithInt32;
+ break;
+
+ case ArrayWithDouble:
+ compare = compareNumbersForQSortWithDouble;
+ ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
+ break;
+
+ default:
+ compare = compareNumbersForQSort;
+ break;
+ }
+ ASSERT(data.length() >= newRelevantLength);
+ qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
+ return;
+}
+
+void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ return;
+
+ case ArrayWithInt32:
+ sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithDouble:
+ sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithContiguous:
+ sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithArrayStorage:
+ sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+ return;
+
+ default:
+ dataLog("Indexing type: ", indexingType(), "\n");
+ RELEASE_ASSERT_NOT_REACHED();
+ return;
+ }
+}
+
+template <IndexingType> struct ContiguousTypeAccessor {
+ typedef WriteBarrier<Unknown> Type;
+ static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); }
+ static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value)
+ {
+ data[i].set(vm, thisValue, value);
+ }
+ static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData)
+ {
+ *outData = inData;
+ }
+};
+
+template <> struct ContiguousTypeAccessor<ArrayWithDouble> {
+ typedef double Type;
+ static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); }
+ static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value)
+ {
+ data[i] = value.asNumber();
+ }
+ static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues)
+ {
+ RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort.");
+ }
+};
+
+
+template<IndexingType arrayIndexingType, typename StorageType>
+void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> data, unsigned relevantLength)
+{
+ if (!relevantLength)
+ return;
+
+ VM& vm = exec->vm();
+
+ // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
+ // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
+ // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
+ // random or otherwise changing results, effectively making compare function inconsistent.
+
+ Vector<ValueStringPair, 0, UnsafeVectorOverflow> values(relevantLength);
+ if (!values.begin()) {
+ throwOutOfMemoryError(exec);
+ return;
+ }
+
+ Heap::heap(this)->pushTempSortVector(&values);
+
+ bool isSortingPrimitiveValues = true;
+
+ for (size_t i = 0; i < relevantLength; i++) {
+ JSValue value = ContiguousTypeAccessor<arrayIndexingType>::getAsValue(data, i);
+ ASSERT(arrayIndexingType != ArrayWithInt32 || value.isInt32());
+ ASSERT(!value.isUndefined());
+ values[i].first = value;
+ if (arrayIndexingType != ArrayWithDouble && arrayIndexingType != ArrayWithInt32)
+ isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
+ }
+
+ // FIXME: The following loop continues to call toString on subsequent values even after
+ // a toString call raises an exception.
+
+ for (size_t i = 0; i < relevantLength; i++)
+ values[i].second = values[i].first.toWTFStringInline(exec);
+
+ if (exec->hadException()) {
+ Heap::heap(this)->popTempSortVector(&values);
+ return;
+ }
+
+ // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
+ // than O(N log N).
+
+#if HAVE(MERGESORT)
+ if (isSortingPrimitiveValues)
+ qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+ else
+ mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+#else
+ // FIXME: The qsort library function is likely to not be a stable sort.
+ // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
+ qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+#endif
+
+ // If the toString function changed the length of the array or vector storage,
+ // increase the length to handle the orignal number of actual values.
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ case ArrayWithContiguous:
+ ensureLength(vm, relevantLength);
+ break;
+
+ case ArrayWithArrayStorage:
+ if (arrayStorage()->vectorLength() < relevantLength) {
+ increaseVectorLength(exec->vm(), relevantLength);
+ ContiguousTypeAccessor<arrayIndexingType>::replaceDataReference(&data, arrayStorage()->vector());
+ }
+ if (arrayStorage()->length() < relevantLength)
+ arrayStorage()->setLength(relevantLength);
+ break;
+
+ default:
+ CRASH();
+ }
+
+ for (size_t i = 0; i < relevantLength; i++)
+ ContiguousTypeAccessor<arrayIndexingType>::setWithValue(vm, this, data, i, values[i].first);
+
+ Heap::heap(this)->popTempSortVector(&values);
+}
+
+void JSArray::sort(ExecState* exec)
+{
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ return;
+
+ case ArrayWithInt32: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithInt32>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithInt32>(
+ exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithDouble: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithDouble>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithDouble>(
+ exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithContiguous: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithContiguous>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithContiguous>(
+ exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithArrayStorage: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithArrayStorage>(
+ lengthNotIncludingUndefined, newRelevantLength);
+ ArrayStorage* storage = m_butterfly->arrayStorage();
+ ASSERT(!storage->m_sparseMap);
+
+ sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+}
+
+struct AVLTreeNodeForArrayCompare {
+ JSValue value;
+
+ // Child pointers. The high bit of gt is robbed and used as the
+ // balance factor sign. The high bit of lt is robbed and used as
+ // the magnitude of the balance factor.
+ int32_t gt;
+ int32_t lt;
+};
+
+struct AVLTreeAbstractorForArrayCompare {
+ typedef int32_t handle; // Handle is an index into m_nodes vector.
+ typedef JSValue key;
+ typedef int32_t size;
+
+ Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes;
+ ExecState* m_exec;
+ JSValue m_compareFunction;
+ CallType m_compareCallType;
+ const CallData* m_compareCallData;
+ std::unique_ptr<CachedCall> m_cachedCall;
+
+ handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
+ void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
+ handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
+ void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
+
+ int get_balance_factor(handle h)
+ {
+ if (m_nodes[h].gt & 0x80000000)
+ return -1;
+ return static_cast<unsigned>(m_nodes[h].lt) >> 31;
+ }
+
+ void set_balance_factor(handle h, int bf)
+ {
+ if (bf == 0) {
+ m_nodes[h].lt &= 0x7FFFFFFF;
+ m_nodes[h].gt &= 0x7FFFFFFF;
+ } else {
+ m_nodes[h].lt |= 0x80000000;
+ if (bf < 0)
+ m_nodes[h].gt |= 0x80000000;
+ else
+ m_nodes[h].gt &= 0x7FFFFFFF;
+ }
+ }
+
+ int compare_key_key(key va, key vb)
+ {
+ ASSERT(!va.isUndefined());
+ ASSERT(!vb.isUndefined());
+
+ if (m_exec->hadException())
+ return 1;
+
+ double compareResult;
+ if (m_cachedCall) {
+ m_cachedCall->setThis(jsUndefined());
+ m_cachedCall->setArgument(0, va);
+ m_cachedCall->setArgument(1, vb);
+ compareResult = m_cachedCall->call().toNumber(m_exec);
+ } else {
+ MarkedArgumentBuffer arguments;
+ arguments.append(va);
+ arguments.append(vb);
+ compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
+ }
+ return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
+ }
+
+ int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
+ int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
+
+ static handle null() { return 0x7FFFFFFF; }
+};
+
+template<IndexingType arrayIndexingType>
+void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(!inSparseIndexingMode());
+ ASSERT(arrayIndexingType == indexingType());
+
+ // FIXME: This ignores exceptions raised in the compare function or in toNumber.
+
+ // The maximum tree depth is compiled in - but the caller is clearly up to no good
+ // if a larger array is passed.
+ ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+ if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
+ return;
+
+ unsigned usedVectorLength = relevantLength<arrayIndexingType>();
+ unsigned nodeCount = usedVectorLength;
+
+ if (!nodeCount)
+ return;
+
+ AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
+ tree.abstractor().m_exec = exec;
+ tree.abstractor().m_compareFunction = compareFunction;
+ tree.abstractor().m_compareCallType = callType;
+ tree.abstractor().m_compareCallData = &callData;
+ tree.abstractor().m_nodes.grow(nodeCount);
+
+ if (callType == CallTypeJS)
+ tree.abstractor().m_cachedCall = std::make_unique<CachedCall>(exec, jsCast<JSFunction*>(compareFunction), 2);
+
+ if (!tree.abstractor().m_nodes.begin()) {
+ throwOutOfMemoryError(exec);
+ return;
+ }
+
+ // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
+ // right out from under us while we're building the tree here.
+
+ unsigned numDefined = 0;
+ unsigned numUndefined = 0;
+
+ // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
+ for (; numDefined < usedVectorLength; ++numDefined) {
+ if (numDefined >= m_butterfly->vectorLength())
+ break;
+ JSValue v = getHolyIndexQuickly(numDefined);
+ if (!v || v.isUndefined())
+ break;
+ tree.abstractor().m_nodes[numDefined].value = v;
+ tree.insert(numDefined);
+ }
+ for (unsigned i = numDefined; i < usedVectorLength; ++i) {
+ if (i >= m_butterfly->vectorLength())
+ break;
+ JSValue v = getHolyIndexQuickly(i);
+ if (v) {
+ if (v.isUndefined())
+ ++numUndefined;
+ else {
+ tree.abstractor().m_nodes[numDefined].value = v;
+ tree.insert(numDefined);
+ ++numDefined;
+ }
+ }
+ }
+
+ unsigned newUsedVectorLength = numDefined + numUndefined;
+
+ // The array size may have changed. Figure out the new bounds.
+ unsigned newestUsedVectorLength = currentRelevantLength();
+
+ unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
+ unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
+ unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
+
+ // Copy the values back into m_storage.
+ AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
+ iter.start_iter_least(tree);
+ VM& vm = exec->vm();
+ for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
+ ASSERT(i < butterfly()->vectorLength());
+ if (indexingType() == ArrayWithDouble)
+ butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
+ else
+ currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value);
+ ++iter;
+ }
+ // Put undefined values back in.
+ switch (indexingType()) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
+ break;
+
+ default:
+ for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) {
+ ASSERT(i < butterfly()->vectorLength());
+ currentIndexingData()[i].setUndefined();
+ }
+ }
+
+ // Ensure that unused values in the vector are zeroed out.
+ for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
+ ASSERT(i < butterfly()->vectorLength());
+ if (indexingType() == ArrayWithDouble)
+ butterfly()->contiguousDouble()[i] = PNaN;
+ else
+ currentIndexingData()[i].clear();
+ }
+
+ if (hasAnyArrayStorage(indexingType()))
+ arrayStorage()->m_numValuesInVector = newUsedVectorLength;
+}
+
+void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ return;
+
+ case ArrayWithInt32:
+ sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithDouble:
+ sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithContiguous:
+ sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithArrayStorage:
+ sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+ return;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+}
+
</ins><span class="cx"> void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
</span><span class="cx"> {
</span><span class="cx"> unsigned i = 0;
</span><span class="lines">@@ -1123,4 +1639,95 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template<IndexingType arrayIndexingType>
+void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
+{
+ ASSERT(!inSparseIndexingMode());
+ ASSERT(arrayIndexingType == indexingType());
+
+ unsigned myRelevantLength = relevantLength<arrayIndexingType>();
+
+ numDefined = 0;
+ unsigned numUndefined = 0;
+
+ for (; numDefined < myRelevantLength; ++numDefined) {
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ if (arrayIndexingType == ArrayWithInt32) {
+ JSValue v = m_butterfly->contiguousInt32()[numDefined].get();
+ if (!v)
+ break;
+ ASSERT(v.isInt32());
+ continue;
+ }
+ if (arrayIndexingType == ArrayWithDouble) {
+ double v = m_butterfly->contiguousDouble()[numDefined];
+ if (v != v)
+ break;
+ continue;
+ }
+ JSValue v = indexingData<arrayIndexingType>()[numDefined].get();
+ if (!v || v.isUndefined())
+ break;
+ }
+
+ for (unsigned i = numDefined; i < myRelevantLength; ++i) {
+ ASSERT(i < m_butterfly->vectorLength());
+ if (arrayIndexingType == ArrayWithInt32) {
+ JSValue v = m_butterfly->contiguousInt32()[i].get();
+ if (!v)
+ continue;
+ ASSERT(v.isInt32());
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v);
+ continue;
+ }
+ if (arrayIndexingType == ArrayWithDouble) {
+ double v = m_butterfly->contiguousDouble()[i];
+ if (v != v)
+ continue;
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ m_butterfly->contiguousDouble()[numDefined++] = v;
+ continue;
+ }
+ JSValue v = indexingData<arrayIndexingType>()[i].get();
+ if (v) {
+ if (v.isUndefined())
+ ++numUndefined;
+ else {
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ indexingData<arrayIndexingType>()[numDefined++].setWithoutWriteBarrier(v);
+ }
+ }
+ }
+
+ newRelevantLength = numDefined + numUndefined;
+
+ if (hasAnyArrayStorage(arrayIndexingType))
+ RELEASE_ASSERT(!arrayStorage()->m_sparseMap);
+
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ RELEASE_ASSERT(numDefined == newRelevantLength);
+ break;
+
+ default:
+ for (unsigned i = numDefined; i < newRelevantLength; ++i) {
+ ASSERT(i < m_butterfly->vectorLength());
+ indexingData<arrayIndexingType>()[i].setUndefined();
+ }
+ break;
+ }
+ for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
+ ASSERT(i < m_butterfly->vectorLength());
+ if (arrayIndexingType == ArrayWithDouble)
+ m_butterfly->contiguousDouble()[i] = PNaN;
+ else
+ indexingData<arrayIndexingType>()[i].clear();
+ }
+
+ if (hasAnyArrayStorage(arrayIndexingType))
+ arrayStorage()->m_numValuesInVector = newRelevantLength;
+}
+
</ins><span class="cx"> } // namespace JSC
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSArrayh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSArray.h (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSArray.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/runtime/JSArray.h 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -70,6 +70,10 @@
</span><span class="cx"> // OK to use on new arrays, but not if it might be a RegExpMatchArray.
</span><span class="cx"> JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
</span><span class="cx">
</span><ins>+ JS_EXPORT_PRIVATE void sort(ExecState*);
+ JS_EXPORT_PRIVATE void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
+ JS_EXPORT_PRIVATE void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
</ins><span class="cx"> JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
</span><span class="cx"> JS_EXPORT_PRIVATE JSValue pop(ExecState*);
</span><span class="cx">
</span><span class="lines">@@ -159,8 +163,20 @@
</span><span class="cx"> bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
</span><span class="cx"> bool unshiftCountSlowCase(VM&, bool, unsigned);
</span><span class="cx">
</span><ins>+ template<IndexingType indexingType>
+ void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
+ template<IndexingType indexingType, typename StorageType>
+ void sortCompactedVector(ExecState*, ContiguousData<StorageType>, unsigned relevantLength);
+
+ template<IndexingType indexingType>
+ void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
</ins><span class="cx"> bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
</span><span class="cx"> void setLengthWritable(ExecState*, bool writable);
</span><ins>+
+ template<IndexingType indexingType>
+ void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength);
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSGlobalObjectcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -445,11 +445,8 @@
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->BuiltinLogPrivateName, builtinLog, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->ArrayPrivateName, arrayConstructor, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->NumberPrivateName, numberConstructor, DontEnum | DontDelete | ReadOnly),
</span><del>- GlobalPropertyInfo(vm.propertyNames->StringPrivateName, stringConstructor, DontEnum | DontDelete | ReadOnly),
</del><span class="cx"> GlobalPropertyInfo(vm.propertyNames->absPrivateName, privateFuncAbs, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->floorPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
</span><del>- GlobalPropertyInfo(vm.propertyNames->getPrototypeOfPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
- GlobalPropertyInfo(vm.propertyNames->getOwnPropertyNamesPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
</del><span class="cx"> GlobalPropertyInfo(vm.propertyNames->isFinitePrivateName, privateFuncIsFinite, DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->arrayIterationKindKeyPrivateName, jsNumber(ArrayIterateKey), DontEnum | DontDelete | ReadOnly),
</span><span class="cx"> GlobalPropertyInfo(vm.propertyNames->arrayIterationKindValuePrivateName, jsNumber(ArrayIterateValue), DontEnum | DontDelete | ReadOnly),
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeObjectConstructorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -96,9 +96,6 @@
</span><span class="cx">
</span><span class="cx"> if (!globalObject->runtimeFlags().isSymbolDisabled())
</span><span class="cx"> JSC_NATIVE_FUNCTION("getOwnPropertySymbols", objectConstructorGetOwnPropertySymbols, DontEnum, 1);
</span><del>-
- JSC_NATIVE_FUNCTION(vm.propertyNames->getPrototypeOfPrivateName, objectConstructorGetPrototypeOf, DontEnum, 1);
- JSC_NATIVE_FUNCTION(vm.propertyNames->getOwnPropertyNamesPrivateName, objectConstructorGetOwnPropertyNames, DontEnum, 1);
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool ObjectConstructor::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot &slot)
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/ChangeLog 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2015-04-24 Commit Queue <commit-queue@webkit.org>
+
+ Unreviewed, rolling out r183288.
+ https://bugs.webkit.org/show_bug.cgi?id=144189
+
+ Made js/sort-with-side-effecting-comparisons.html time out in
+ debug builds (Requested by ap on #webkit).
+
+ Reverted changeset:
+
+ "It shouldn't take 1846 lines of code and 5 FIXMEs to sort an
+ array."
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+ http://trac.webkit.org/changeset/183288
+
</ins><span class="cx"> 2015-04-21 Geoffrey Garen <ggaren@apple.com>
</span><span class="cx">
</span><span class="cx"> It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
</span></span></pre></div>
<a id="trunkSourceWTFWTFvcxprojWTFvcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -163,6 +163,7 @@
</span><span class="cx"> <ClInclude Include="..\wtf\Assertions.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\Atomics.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\AutodrainedPool.h" />
</span><ins>+ <ClInclude Include="..\wtf\AVLTree.h" />
</ins><span class="cx"> <ClInclude Include="..\wtf\Bag.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\BagToHashMap.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\Bitmap.h" />
</span></span></pre></div>
<a id="trunkSourceWTFWTFvcxprojWTFvcxprojfilters"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -381,6 +381,9 @@
</span><span class="cx"> <ClInclude Include="..\wtf\Atomics.h">
</span><span class="cx"> <Filter>wtf</Filter>
</span><span class="cx"> </ClInclude>
</span><ins>+ <ClInclude Include="..\wtf\AVLTree.h">
+ <Filter>wtf</Filter>
+ </ClInclude>
</ins><span class="cx"> <ClInclude Include="..\wtf\Bitmap.h">
</span><span class="cx"> <Filter>wtf</Filter>
</span><span class="cx"> </ClInclude>
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -107,6 +107,7 @@
</span><span class="cx"> A8A47386151A825B004123FF /* Assertions.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A4725B151A825A004123FF /* Assertions.cpp */; };
</span><span class="cx"> A8A47387151A825B004123FF /* Assertions.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725C151A825A004123FF /* Assertions.h */; };
</span><span class="cx"> A8A47388151A825B004123FF /* Atomics.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725D151A825A004123FF /* Atomics.h */; };
</span><ins>+ A8A47389151A825B004123FF /* AVLTree.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725E151A825A004123FF /* AVLTree.h */; };
</ins><span class="cx"> A8A4738A151A825B004123FF /* Bitmap.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725F151A825A004123FF /* Bitmap.h */; };
</span><span class="cx"> A8A4738B151A825B004123FF /* BitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A47260151A825A004123FF /* BitVector.cpp */; };
</span><span class="cx"> A8A4738C151A825B004123FF /* BitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47261151A825A004123FF /* BitVector.h */; };
</span><span class="lines">@@ -391,6 +392,7 @@
</span><span class="cx"> A8A4725B151A825A004123FF /* Assertions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Assertions.cpp; sourceTree = "<group>"; };
</span><span class="cx"> A8A4725C151A825A004123FF /* Assertions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Assertions.h; sourceTree = "<group>"; };
</span><span class="cx"> A8A4725D151A825A004123FF /* Atomics.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Atomics.h; sourceTree = "<group>"; };
</span><ins>+ A8A4725E151A825A004123FF /* AVLTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AVLTree.h; sourceTree = "<group>"; };
</ins><span class="cx"> A8A4725F151A825A004123FF /* Bitmap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Bitmap.h; sourceTree = "<group>"; };
</span><span class="cx"> A8A47260151A825A004123FF /* BitVector.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BitVector.cpp; sourceTree = "<group>"; };
</span><span class="cx"> A8A47261151A825A004123FF /* BitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BitVector.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -694,6 +696,7 @@
</span><span class="cx"> A8A4725D151A825A004123FF /* Atomics.h */,
</span><span class="cx"> 1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
</span><span class="cx"> 1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
</span><ins>+ A8A4725E151A825A004123FF /* AVLTree.h */,
</ins><span class="cx"> 0FB14E18180FA218009B6B4D /* Bag.h */,
</span><span class="cx"> 0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
</span><span class="cx"> A8A4725F151A825A004123FF /* Bitmap.h */,
</span><span class="lines">@@ -1036,6 +1039,7 @@
</span><span class="cx"> A8A47438151A825B004123FF /* AtomicStringImpl.h in Headers */,
</span><span class="cx"> 9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */,
</span><span class="cx"> 1469419C16EAB10A0024E146 /* AutodrainedPool.h in Headers */,
</span><ins>+ A8A47389151A825B004123FF /* AVLTree.h in Headers */,
</ins><span class="cx"> 8134013915B092FD001FF0B8 /* Base64.h in Headers */,
</span><span class="cx"> A8A473A9151A825B004123FF /* bignum-dtoa.h in Headers */,
</span><span class="cx"> A8A473AB151A825B004123FF /* bignum.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfAVLTreeh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/AVLTree.h (0 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/AVLTree.h (rev 0)
+++ trunk/Source/WTF/wtf/AVLTree.h 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -0,0 +1,960 @@
</span><ins>+/*
+ * Copyright (C) 2008 Apple Inc. All rights reserved.
+ *
+ * Based on Abstract AVL Tree Template v1.5 by Walt Karas
+ * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of Apple Inc. ("Apple") nor the names of
+ * its contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef AVL_TREE_H_
+#define AVL_TREE_H_
+
+#include <array>
+#include <wtf/Assertions.h>
+
+namespace WTF {
+
+// Here is the reference class for BSet.
+//
+// class BSet
+// {
+// public:
+//
+// class ANY_bitref
+// {
+// public:
+// operator bool ();
+// void operator = (bool b);
+// };
+//
+// // Does not have to initialize bits.
+// BSet();
+//
+// // Must return a valid value for index when 0 <= index < maxDepth
+// ANY_bitref operator [] (unsigned index);
+//
+// // Set all bits to 1.
+// void set();
+//
+// // Set all bits to 0.
+// void reset();
+// };
+
+template<unsigned maxDepth>
+class AVLTreeDefaultBSet {
+public:
+ bool& operator[](unsigned i) { ASSERT_WITH_SECURITY_IMPLICATION(i < maxDepth); return m_data[i]; }
+ void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
+ void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }
+
+private:
+ std::array<bool, maxDepth> m_data;
+};
+
+// How to determine maxDepth:
+// d Minimum number of nodes
+// 2 2
+// 3 4
+// 4 7
+// 5 12
+// 6 20
+// 7 33
+// 8 54
+// 9 88
+// 10 143
+// 11 232
+// 12 376
+// 13 609
+// 14 986
+// 15 1,596
+// 16 2,583
+// 17 4,180
+// 18 6,764
+// 19 10,945
+// 20 17,710
+// 21 28,656
+// 22 46,367
+// 23 75,024
+// 24 121,392
+// 25 196,417
+// 26 317,810
+// 27 514,228
+// 28 832,039
+// 29 1,346,268
+// 30 2,178,308
+// 31 3,524,577
+// 32 5,702,886
+// 33 9,227,464
+// 34 14,930,351
+// 35 24,157,816
+// 36 39,088,168
+// 37 63,245,985
+// 38 102,334,154
+// 39 165,580,140
+// 40 267,914,295
+// 41 433,494,436
+// 42 701,408,732
+// 43 1,134,903,169
+// 44 1,836,311,902
+// 45 2,971,215,072
+//
+// E.g., if, in a particular instantiation, the maximum number of nodes in a tree instance is 1,000,000, the maximum depth should be 28.
+// You pick 28 because MN(28) is 832,039, which is less than or equal to 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000.
+
+template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth>>
+class AVLTree {
+public:
+
+ typedef typename Abstractor::key key;
+ typedef typename Abstractor::handle handle;
+ typedef typename Abstractor::size size;
+
+ enum SearchType {
+ EQUAL = 1,
+ LESS = 2,
+ GREATER = 4,
+ LESS_EQUAL = EQUAL | LESS,
+ GREATER_EQUAL = EQUAL | GREATER
+ };
+
+
+ Abstractor& abstractor() { return abs; }
+
+ inline handle insert(handle h);
+
+ inline handle search(key k, SearchType st = EQUAL);
+ inline handle search_least();
+ inline handle search_greatest();
+
+ inline handle remove(key k);
+
+ inline handle subst(handle new_node);
+
+ void purge() { abs.root = null(); }
+
+ bool is_empty() { return abs.root == null(); }
+
+ AVLTree() { abs.root = null(); }
+
+ class Iterator {
+ public:
+
+ // Initialize depth to invalid value, to indicate iterator is
+ // invalid. (Depth is zero-base.)
+ Iterator() { depth = ~0U; }
+
+ void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
+ {
+ // Mask of high bit in an int.
+ const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
+
+ // Save the tree that we're going to iterate through in a
+ // member variable.
+ tree_ = &tree;
+
+ int cmp, target_cmp;
+ handle h = tree_->abs.root;
+ unsigned d = 0;
+
+ depth = ~0U;
+
+ if (h == null())
+ // Tree is empty.
+ return;
+
+ if (st & LESS)
+ // Key can be greater than key of starting node.
+ target_cmp = 1;
+ else if (st & GREATER)
+ // Key can be less than key of starting node.
+ target_cmp = -1;
+ else
+ // Key must be same as key of starting node.
+ target_cmp = 0;
+
+ for (;;) {
+ cmp = cmp_k_n(k, h);
+ if (cmp == 0) {
+ if (st & EQUAL) {
+ // Equal node was sought and found as starting node.
+ depth = d;
+ break;
+ }
+ cmp = -target_cmp;
+ } else if (target_cmp != 0) {
+ if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
+ // cmp and target_cmp are both negative or both positive.
+ depth = d;
+ }
+ }
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ if (h == null())
+ break;
+ branch[d] = cmp > 0;
+ path_h[d++] = h;
+ }
+ }
+
+ void start_iter_least(AVLTree &tree)
+ {
+ tree_ = &tree;
+
+ handle h = tree_->abs.root;
+
+ depth = ~0U;
+
+ branch.reset();
+
+ while (h != null()) {
+ if (depth != ~0U)
+ path_h[depth] = h;
+ depth++;
+ h = get_lt(h);
+ }
+ }
+
+ void start_iter_greatest(AVLTree &tree)
+ {
+ tree_ = &tree;
+
+ handle h = tree_->abs.root;
+
+ depth = ~0U;
+
+ branch.set();
+
+ while (h != null()) {
+ if (depth != ~0U)
+ path_h[depth] = h;
+ depth++;
+ h = get_gt(h);
+ }
+ }
+
+ handle operator*()
+ {
+ if (depth == ~0U)
+ return null();
+
+ return depth == 0 ? tree_->abs.root : path_h[depth - 1];
+ }
+
+ void operator++()
+ {
+ if (depth != ~0U) {
+ handle h = get_gt(**this);
+ if (h == null()) {
+ do {
+ if (depth == 0) {
+ depth = ~0U;
+ break;
+ }
+ depth--;
+ } while (branch[depth]);
+ } else {
+ branch[depth] = true;
+ path_h[depth++] = h;
+ for (;;) {
+ h = get_lt(h);
+ if (h == null())
+ break;
+ branch[depth] = false;
+ path_h[depth++] = h;
+ }
+ }
+ }
+ }
+
+ void operator--()
+ {
+ if (depth != ~0U) {
+ handle h = get_lt(**this);
+ if (h == null())
+ do {
+ if (depth == 0) {
+ depth = ~0U;
+ break;
+ }
+ depth--;
+ } while (!branch[depth]);
+ else {
+ branch[depth] = false;
+ path_h[depth++] = h;
+ for (;;) {
+ h = get_gt(h);
+ if (h == null())
+ break;
+ branch[depth] = true;
+ path_h[depth++] = h;
+ }
+ }
+ }
+ }
+
+ void operator++(int) { ++(*this); }
+ void operator--(int) { --(*this); }
+
+ protected:
+
+ // Tree being iterated over.
+ AVLTree *tree_;
+
+ // Records a path into the tree. If branch[n] is true, indicates
+ // take greater branch from the nth node in the path, otherwise
+ // take the less branch. branch[0] gives branch from root, and
+ // so on.
+ BSet branch;
+
+ // Zero-based depth of path into tree.
+ unsigned depth;
+
+ // Handles of nodes in path from root to current node (returned by *).
+ handle path_h[maxDepth - 1];
+
+ int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
+ int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
+ handle get_lt(handle h) { return tree_->abs.get_less(h); }
+ handle get_gt(handle h) { return tree_->abs.get_greater(h); }
+ handle null() { return tree_->abs.null(); }
+ };
+
+ template<typename fwd_iter>
+ bool build(fwd_iter p, size num_nodes)
+ {
+ if (num_nodes == 0) {
+ abs.root = null();
+ return true;
+ }
+
+ // Gives path to subtree being built. If branch[N] is false, branch
+ // less from the node at depth N, if true branch greater.
+ BSet branch;
+
+ // If rem[N] is true, then for the current subtree at depth N, it's
+ // greater subtree has one more node than it's less subtree.
+ BSet rem;
+
+ // Depth of root node of current subtree.
+ unsigned depth = 0;
+
+ // Number of nodes in current subtree.
+ size num_sub = num_nodes;
+
+ // The algorithm relies on a stack of nodes whose less subtree has
+ // been built, but whose right subtree has not yet been built. The
+ // stack is implemented as linked list. The nodes are linked
+ // together by having the "greater" handle of a node set to the
+ // next node in the list. "less_parent" is the handle of the first
+ // node in the list.
+ handle less_parent = null();
+
+ // h is root of current subtree, child is one of its children.
+ handle h, child;
+
+ for (;;) {
+ while (num_sub > 2) {
+ // Subtract one for root of subtree.
+ num_sub--;
+ rem[depth] = !!(num_sub & 1);
+ branch[depth++] = false;
+ num_sub >>= 1;
+ }
+
+ if (num_sub == 2) {
+ // Build a subtree with two nodes, slanting to greater.
+ // I arbitrarily chose to always have the extra node in the
+ // greater subtree when there is an odd number of nodes to
+ // split between the two subtrees.
+
+ h = *p;
+ p++;
+ child = *p;
+ p++;
+ set_lt(child, null());
+ set_gt(child, null());
+ set_bf(child, 0);
+ set_gt(h, child);
+ set_lt(h, null());
+ set_bf(h, 1);
+ } else { // num_sub == 1
+ // Build a subtree with one node.
+
+ h = *p;
+ p++;
+ set_lt(h, null());
+ set_gt(h, null());
+ set_bf(h, 0);
+ }
+
+ while (depth) {
+ depth--;
+ if (!branch[depth])
+ // We've completed a less subtree.
+ break;
+
+ // We've completed a greater subtree, so attach it to
+ // its parent (that is less than it). We pop the parent
+ // off the stack of less parents.
+ child = h;
+ h = less_parent;
+ less_parent = get_gt(h);
+ set_gt(h, child);
+ // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
+ num_sub <<= 1;
+ num_sub += 1 - rem[depth];
+ if (num_sub & (num_sub - 1))
+ // num_sub is not a power of 2
+ set_bf(h, 0);
+ else
+ // num_sub is a power of 2
+ set_bf(h, 1);
+ }
+
+ if (num_sub == num_nodes)
+ // We've completed the full tree.
+ break;
+
+ // The subtree we've completed is the less subtree of the
+ // next node in the sequence.
+
+ child = h;
+ h = *p;
+ p++;
+ set_lt(h, child);
+
+ // Put h into stack of less parents.
+ set_gt(h, less_parent);
+ less_parent = h;
+
+ // Proceed to creating greater than subtree of h.
+ branch[depth] = true;
+ num_sub += rem[depth++];
+
+ } // end for (;;)
+
+ abs.root = h;
+
+ return true;
+ }
+
+protected:
+
+ friend class Iterator;
+
+ // Create a class whose sole purpose is to take advantage of
+ // the "empty member" optimization.
+ struct abs_plus_root : public Abstractor {
+ // The handle of the root element in the AVL tree.
+ handle root;
+ };
+
+ abs_plus_root abs;
+
+
+ handle get_lt(handle h) { return abs.get_less(h); }
+ void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
+
+ handle get_gt(handle h) { return abs.get_greater(h); }
+ void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
+
+ int get_bf(handle h) { return abs.get_balance_factor(h); }
+ void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
+
+ int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
+ int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }
+
+ handle null() { return abs.null(); }
+
+private:
+
+ // Balances subtree, returns handle of root node of subtree
+ // after balancing.
+ handle balance(handle bal_h)
+ {
+ handle deep_h;
+
+ // Either the "greater than" or the "less than" subtree of
+ // this node has to be 2 levels deeper (or else it wouldn't
+ // need balancing).
+
+ if (get_bf(bal_h) > 0) {
+ // "Greater than" subtree is deeper.
+
+ deep_h = get_gt(bal_h);
+
+ if (get_bf(deep_h) < 0) {
+ handle old_h = bal_h;
+ bal_h = get_lt(deep_h);
+
+ set_gt(old_h, get_lt(bal_h));
+ set_lt(deep_h, get_gt(bal_h));
+ set_lt(bal_h, old_h);
+ set_gt(bal_h, deep_h);
+
+ int bf = get_bf(bal_h);
+ if (bf != 0) {
+ if (bf > 0) {
+ set_bf(old_h, -1);
+ set_bf(deep_h, 0);
+ } else {
+ set_bf(deep_h, 1);
+ set_bf(old_h, 0);
+ }
+ set_bf(bal_h, 0);
+ } else {
+ set_bf(old_h, 0);
+ set_bf(deep_h, 0);
+ }
+ } else {
+ set_gt(bal_h, get_lt(deep_h));
+ set_lt(deep_h, bal_h);
+ if (get_bf(deep_h) == 0) {
+ set_bf(deep_h, -1);
+ set_bf(bal_h, 1);
+ } else {
+ set_bf(deep_h, 0);
+ set_bf(bal_h, 0);
+ }
+ bal_h = deep_h;
+ }
+ } else {
+ // "Less than" subtree is deeper.
+
+ deep_h = get_lt(bal_h);
+
+ if (get_bf(deep_h) > 0) {
+ handle old_h = bal_h;
+ bal_h = get_gt(deep_h);
+ set_lt(old_h, get_gt(bal_h));
+ set_gt(deep_h, get_lt(bal_h));
+ set_gt(bal_h, old_h);
+ set_lt(bal_h, deep_h);
+
+ int bf = get_bf(bal_h);
+ if (bf != 0) {
+ if (bf < 0) {
+ set_bf(old_h, 1);
+ set_bf(deep_h, 0);
+ } else {
+ set_bf(deep_h, -1);
+ set_bf(old_h, 0);
+ }
+ set_bf(bal_h, 0);
+ } else {
+ set_bf(old_h, 0);
+ set_bf(deep_h, 0);
+ }
+ } else {
+ set_lt(bal_h, get_gt(deep_h));
+ set_gt(deep_h, bal_h);
+ if (get_bf(deep_h) == 0) {
+ set_bf(deep_h, 1);
+ set_bf(bal_h, -1);
+ } else {
+ set_bf(deep_h, 0);
+ set_bf(bal_h, 0);
+ }
+ bal_h = deep_h;
+ }
+ }
+
+ return bal_h;
+ }
+
+};
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
+{
+ set_lt(h, null());
+ set_gt(h, null());
+ set_bf(h, 0);
+
+ if (abs.root == null())
+ abs.root = h;
+ else {
+ // Last unbalanced node encountered in search for insertion point.
+ handle unbal = null();
+ // Parent of last unbalanced node.
+ handle parent_unbal = null();
+ // Balance factor of last unbalanced node.
+ int unbal_bf;
+
+ // Zero-based depth in tree.
+ unsigned depth = 0, unbal_depth = 0;
+
+ // Records a path into the tree. If branch[n] is true, indicates
+ // take greater branch from the nth node in the path, otherwise
+ // take the less branch. branch[0] gives branch from root, and
+ // so on.
+ BSet branch;
+
+ handle hh = abs.root;
+ handle parent = null();
+ int cmp;
+
+ do {
+ if (get_bf(hh) != 0) {
+ unbal = hh;
+ parent_unbal = parent;
+ unbal_depth = depth;
+ }
+ cmp = cmp_n_n(h, hh);
+ if (cmp == 0)
+ // Duplicate key.
+ return hh;
+ parent = hh;
+ hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
+ branch[depth++] = cmp > 0;
+ } while (hh != null());
+
+ // Add node to insert as leaf of tree.
+ if (cmp < 0)
+ set_lt(parent, h);
+ else
+ set_gt(parent, h);
+
+ depth = unbal_depth;
+
+ if (unbal == null())
+ hh = abs.root;
+ else {
+ cmp = branch[depth++] ? 1 : -1;
+ unbal_bf = get_bf(unbal);
+ if (cmp < 0)
+ unbal_bf--;
+ else // cmp > 0
+ unbal_bf++;
+ hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
+ if ((unbal_bf != -2) && (unbal_bf != 2)) {
+ // No rebalancing of tree is necessary.
+ set_bf(unbal, unbal_bf);
+ unbal = null();
+ }
+ }
+
+ if (hh != null())
+ while (h != hh) {
+ cmp = branch[depth++] ? 1 : -1;
+ if (cmp < 0) {
+ set_bf(hh, -1);
+ hh = get_lt(hh);
+ } else { // cmp > 0
+ set_bf(hh, 1);
+ hh = get_gt(hh);
+ }
+ }
+
+ if (unbal != null()) {
+ unbal = balance(unbal);
+ if (parent_unbal == null())
+ abs.root = unbal;
+ else {
+ depth = unbal_depth - 1;
+ cmp = branch[depth] ? 1 : -1;
+ if (cmp < 0)
+ set_lt(parent_unbal, unbal);
+ else // cmp > 0
+ set_gt(parent_unbal, unbal);
+ }
+ }
+ }
+
+ return h;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
+{
+ const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
+
+ int cmp, target_cmp;
+ handle match_h = null();
+ handle h = abs.root;
+
+ if (st & LESS)
+ target_cmp = 1;
+ else if (st & GREATER)
+ target_cmp = -1;
+ else
+ target_cmp = 0;
+
+ while (h != null()) {
+ cmp = cmp_k_n(k, h);
+ if (cmp == 0) {
+ if (st & EQUAL) {
+ match_h = h;
+ break;
+ }
+ cmp = -target_cmp;
+ } else if (target_cmp != 0)
+ if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
+ // cmp and target_cmp are both positive or both negative.
+ match_h = h;
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ }
+
+ return match_h;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search_least()
+{
+ handle h = abs.root, parent = null();
+
+ while (h != null()) {
+ parent = h;
+ h = get_lt(h);
+ }
+
+ return parent;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
+{
+ handle h = abs.root, parent = null();
+
+ while (h != null()) {
+ parent = h;
+ h = get_gt(h);
+ }
+
+ return parent;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
+{
+ // Zero-based depth in tree.
+ unsigned depth = 0, rm_depth;
+
+ // Records a path into the tree. If branch[n] is true, indicates
+ // take greater branch from the nth node in the path, otherwise
+ // take the less branch. branch[0] gives branch from root, and
+ // so on.
+ BSet branch;
+
+ handle h = abs.root;
+ handle parent = null(), child;
+ int cmp, cmp_shortened_sub_with_path = 0;
+
+ for (;;) {
+ if (h == null())
+ // No node in tree with given key.
+ return null();
+ cmp = cmp_k_n(k, h);
+ if (cmp == 0)
+ // Found node to remove.
+ break;
+ parent = h;
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ branch[depth++] = cmp > 0;
+ cmp_shortened_sub_with_path = cmp;
+ }
+ handle rm = h;
+ handle parent_rm = parent;
+ rm_depth = depth;
+
+ // If the node to remove is not a leaf node, we need to get a
+ // leaf node, or a node with a single leaf as its child, to put
+ // in the place of the node to remove. We will get the greatest
+ // node in the less subtree (of the node to remove), or the least
+ // node in the greater subtree. We take the leaf node from the
+ // deeper subtree, if there is one.
+
+ if (get_bf(h) < 0) {
+ child = get_lt(h);
+ branch[depth] = false;
+ cmp = -1;
+ } else {
+ child = get_gt(h);
+ branch[depth] = true;
+ cmp = 1;
+ }
+ depth++;
+
+ if (child != null()) {
+ cmp = -cmp;
+ do {
+ parent = h;
+ h = child;
+ if (cmp < 0) {
+ child = get_lt(h);
+ branch[depth] = false;
+ } else {
+ child = get_gt(h);
+ branch[depth] = true;
+ }
+ depth++;
+ } while (child != null());
+
+ if (parent == rm)
+ // Only went through do loop once. Deleted node will be replaced
+ // in the tree structure by one of its immediate children.
+ cmp_shortened_sub_with_path = -cmp;
+ else
+ cmp_shortened_sub_with_path = cmp;
+
+ // Get the handle of the opposite child, which may not be null.
+ child = cmp > 0 ? get_lt(h) : get_gt(h);
+ }
+
+ if (parent == null())
+ // There were only 1 or 2 nodes in this tree.
+ abs.root = child;
+ else if (cmp_shortened_sub_with_path < 0)
+ set_lt(parent, child);
+ else
+ set_gt(parent, child);
+
+ // "path" is the parent of the subtree being eliminated or reduced
+ // from a depth of 2 to 1. If "path" is the node to be removed, we
+ // set path to the node we're about to poke into the position of the
+ // node to be removed.
+ handle path = parent == rm ? h : parent;
+
+ if (h != rm) {
+ // Poke in the replacement for the node to be removed.
+ set_lt(h, get_lt(rm));
+ set_gt(h, get_gt(rm));
+ set_bf(h, get_bf(rm));
+ if (parent_rm == null())
+ abs.root = h;
+ else {
+ depth = rm_depth - 1;
+ if (branch[depth])
+ set_gt(parent_rm, h);
+ else
+ set_lt(parent_rm, h);
+ }
+ }
+
+ if (path != null()) {
+ // Create a temporary linked list from the parent of the path node
+ // to the root node.
+ h = abs.root;
+ parent = null();
+ depth = 0;
+ while (h != path) {
+ if (branch[depth++]) {
+ child = get_gt(h);
+ set_gt(h, parent);
+ } else {
+ child = get_lt(h);
+ set_lt(h, parent);
+ }
+ parent = h;
+ h = child;
+ }
+
+ // Climb from the path node to the root node using the linked
+ // list, restoring the tree structure and rebalancing as necessary.
+ bool reduced_depth = true;
+ int bf;
+ cmp = cmp_shortened_sub_with_path;
+ for (;;) {
+ if (reduced_depth) {
+ bf = get_bf(h);
+ if (cmp < 0)
+ bf++;
+ else // cmp > 0
+ bf--;
+ if ((bf == -2) || (bf == 2)) {
+ h = balance(h);
+ bf = get_bf(h);
+ } else
+ set_bf(h, bf);
+ reduced_depth = (bf == 0);
+ }
+ if (parent == null())
+ break;
+ child = h;
+ h = parent;
+ cmp = branch[--depth] ? 1 : -1;
+ if (cmp < 0) {
+ parent = get_lt(h);
+ set_lt(h, child);
+ } else {
+ parent = get_gt(h);
+ set_gt(h, child);
+ }
+ }
+ abs.root = h;
+ }
+
+ return rm;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
+{
+ handle h = abs.root;
+ handle parent = null();
+ int cmp, last_cmp;
+
+ /* Search for node already in tree with same key. */
+ for (;;) {
+ if (h == null())
+ /* No node in tree with same key as new node. */
+ return null();
+ cmp = cmp_n_n(new_node, h);
+ if (cmp == 0)
+ /* Found the node to substitute new one for. */
+ break;
+ last_cmp = cmp;
+ parent = h;
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ }
+
+ /* Copy tree housekeeping fields from node in tree to new node. */
+ set_lt(new_node, get_lt(h));
+ set_gt(new_node, get_gt(h));
+ set_bf(new_node, get_bf(h));
+
+ if (parent == null())
+ /* New node is also new root. */
+ abs.root = new_node;
+ else {
+ /* Make parent point to new node. */
+ if (last_cmp < 0)
+ set_lt(parent, new_node);
+ else
+ set_gt(parent, new_node);
+ }
+
+ return h;
+}
+
+}
+
+#endif
</ins></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (183307 => 183308)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-04-25 06:57:12 UTC (rev 183308)
</span><span class="lines">@@ -1,5 +1,6 @@
</span><span class="cx"> set(WTF_HEADERS
</span><span class="cx"> ASCIICType.h
</span><ins>+ AVLTree.h
</ins><span class="cx"> Assertions.h
</span><span class="cx"> Atomics.h
</span><span class="cx"> Bag.h
</span></span></pre>
</div>
</div>
</body>
</html>