<!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>[168236] 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/168236">168236</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2014-05-03 20:25:56 -0700 (Sat, 03 May 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>CSS JIT: optimize direct / indirect adjacent's traversal backtracking
https://bugs.webkit.org/show_bug.cgi?id=132319
Patch by Yusuke Suzuki <utatane.tea@gmail.com> on 2014-05-03
Reviewed by Benjamin Poulain.
Source/WebCore:
Since adjacent backtracking stack reference is pre-allocated
in prologue in http://trac.webkit.org/changeset/166834,
clearing stack phase is not needed. So we can drop
JumpToClearAdjacentTail from backtracking action and simplify
backtracking handling.
And optimize direct / indirect adjacent's traversal backtracking by
using appropriate backtracking height.
When solving adjacent traversal backtracking action,
1) When there's no descendant relation on the right, traversal
failure becomes global failure.
2) When `tagNameMatchedBacktrackingStartHeightFromDescendant` ==
`heightFromDescendant` + 1, the descendant backtracking starts with
the parent of the current element. So we can use the current element
and the backtracking action is JumpToDescendantTreeWalkerEntryPoint.
3) Otherwise, currently we take the conservative approach,
JumpToDescendantTail.
NOTE:
And if `hasDescendantRelationOnTheRight` is true and there's no child
fragment on the right, the backtracking element register is not
effective. So we should ensure that fragment doesn't use the
backtracking element register. Such a fragment fulfills the following
conditions. 1. tagNameMatchedBacktrackingStartHeightFromDescendant is
always 1 (tagNames.size(), that contains only descendant fragment) 2.
heightFromDescendant is always 0 (-- See
computeBacktrackingHeightFromDescendant implementation) Therefore such
a fragment's action always becomes
JumpToDescendantTreeWalkerEntryPoint. So we can ensure that the
backtracking element register is not used.
Test: fast/selectors/backtracking-adjacent.html
* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::solveDescendantBacktrackingActionForChild):
(WebCore::SelectorCompiler::solveAdjacentTraversalBacktrackingAction):
(WebCore::SelectorCompiler::solveBacktrackingAction):
(WebCore::SelectorCompiler::SelectorCodeGenerator::computeBacktrackingInformation):
(WebCore::SelectorCompiler::SelectorCodeGenerator::linkFailures):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateAdjacentBacktrackingTail):
(WebCore::SelectorCompiler::isAfterChildRelation): Deleted.
LayoutTests:
* fast/selectors/backtracking-adjacent-expected.txt: Added.
* fast/selectors/backtracking-adjacent.html: Added.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecssjitSelectorCompilercpp">trunk/Source/WebCore/cssjit/SelectorCompiler.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsfastselectorsbacktrackingadjacentexpectedtxt">trunk/LayoutTests/fast/selectors/backtracking-adjacent-expected.txt</a></li>
<li><a href="#trunkLayoutTestsfastselectorsbacktrackingadjacenthtml">trunk/LayoutTests/fast/selectors/backtracking-adjacent.html</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (168235 => 168236)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2014-05-04 03:22:04 UTC (rev 168235)
+++ trunk/LayoutTests/ChangeLog 2014-05-04 03:25:56 UTC (rev 168236)
</span><span class="lines">@@ -1,3 +1,13 @@
</span><ins>+2014-05-03 Yusuke Suzuki <utatane.tea@gmail.com>
+
+ CSS JIT: optimize direct / indirect adjacent's traversal backtracking
+ https://bugs.webkit.org/show_bug.cgi?id=132319
+
+ Reviewed by Benjamin Poulain.
+
+ * fast/selectors/backtracking-adjacent-expected.txt: Added.
+ * fast/selectors/backtracking-adjacent.html: Added.
+
</ins><span class="cx"> 2014-05-03 Andreas Kling <akling@apple.com>
</span><span class="cx">
</span><span class="cx"> Invalidate scrollbars when custom scrollbar style changes dynamically.
</span></span></pre></div>
<a id="trunkLayoutTestsfastselectorsbacktrackingadjacentexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/backtracking-adjacent-expected.txt (0 => 168236)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/backtracking-adjacent-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/selectors/backtracking-adjacent-expected.txt 2014-05-04 03:25:56 UTC (rev 168236)
</span><span class="lines">@@ -0,0 +1,51 @@
</span><ins>+The backtracking from adjacent combinators
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+Backtracking without tail, succeeded without backtracking
+PASS getComputedStyle(document.getElementById("target1")).backgroundColor is "rgb(1, 2, 3)"
+Backtracking without tail without indirect adjacent, failed and restart.
+PASS getComputedStyle(document.getElementById("target2")).backgroundColor is "rgb(1, 2, 3)"
+Backtracking without tail, 2 direct adjacents without indirect adjacent, failed and restart backtracking.
+PASS getComputedStyle(document.getElementById("target3")).backgroundColor is "rgb(4, 5, 6)"
+Backtracking without tail, indirect adjacent.
+PASS getComputedStyle(document.getElementById("target4")).backgroundColor is "rgb(7, 8, 9)"
+Backtracking from direct adjacent without tail. Matches.
+PASS getComputedStyle(document.getElementById("target6.1")).backgroundColor is "rgb(10, 11, 12)"
+Backtracking from direct adjacent tag matching without tail. Fails.
+PASS getComputedStyle(document.getElementById("target6.2")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from direct adjacent traversal without tail. Fails.
+PASS getComputedStyle(document.getElementById("target6.3")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking without tail. And fails.
+PASS getComputedStyle(document.getElementById("target7")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking without tail. And Matches.
+PASS getComputedStyle(document.getElementById("target8")).backgroundColor is "rgb(13, 14, 15)"
+Backtracking from direct adjacent with tail. And fails.
+PASS getComputedStyle(document.getElementById("target9")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from direct adjacent with tail. And Matches.
+PASS getComputedStyle(document.getElementById("target10")).backgroundColor is "rgb(16, 17, 18)"
+Backtracking from indirect adjacent with tail. And fails.
+PASS getComputedStyle(document.getElementById("target11")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from indirect adjacent with tail. And Matches.
+PASS getComputedStyle(document.getElementById("target12")).backgroundColor is "rgb(19, 20, 21)"
+Backtracking from indirect adjacent without tail. Matches.
+PASS getComputedStyle(document.getElementById("target13.1")).backgroundColor is "rgb(22, 23, 24)"
+Backtracking from indirect adjacent tag matching without tail. Fails.
+PASS getComputedStyle(document.getElementById("target13.2")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from indirect adjacent traversal without tail. Fails.
+PASS getComputedStyle(document.getElementById("target13.3")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from indirect adjacent without tail. Matches.
+PASS getComputedStyle(document.getElementById("target14.1")).backgroundColor is "rgb(25, 26, 27)"
+Backtracking from indirect adjacent tag matching without tail. Fails.
+PASS getComputedStyle(document.getElementById("target14.2")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from indirect adjacent traversal without tail. Fails.
+PASS getComputedStyle(document.getElementById("target14.3")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from direct adjacent with tail. And fails.
+PASS getComputedStyle(document.getElementById("target15")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking from direct adjacent with tail. And Matches.
+PASS getComputedStyle(document.getElementById("target16")).backgroundColor is "rgb(28, 29, 30)"
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsfastselectorsbacktrackingadjacenthtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/backtracking-adjacent.html (0 => 168236)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/backtracking-adjacent.html (rev 0)
+++ trunk/LayoutTests/fast/selectors/backtracking-adjacent.html 2014-05-04 03:25:56 UTC (rev 168236)
</span><span class="lines">@@ -0,0 +1,390 @@
</span><ins>+<!doctype html>
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+<style>
+span.target {
+ background-color:rgb(0,0,0);
+}
+a + b span.target {
+ background-color:rgb(1,2,3);
+}
+c + c + d span.target {
+ background-color:rgb(4,5,6);
+}
+e + f ~ g span.target {
+ background-color:rgb(7,8,9);
+}
+h + span.target {
+ background-color:rgb(10,11,12);
+}
+j+j+j~j>k span.target {
+ background-color:rgb(13,14,15);
+}
+m l+l+l+l~m>m>m span.target {
+ background-color:rgb(16,17,18);
+}
+n o~n>n>n span.target {
+ background-color:rgb(19,20,21);
+}
+p ~ span.target {
+ background-color:rgb(22,23,24);
+}
+q ~ r span.target {
+ background-color:rgb(25,26,27);
+}
+s t+t+t+s>s>s span.target {
+ background-color:rgb(28,29,30);
+}
+</style>
+</head>
+<body>
+<div style="display:none">
+ <!-- a + b span.target -->
+ <target1>
+ <a></a>
+ <b>
+ <span class="target" id="target1"></span>
+ </b>
+ </target1>
+
+ <!-- a + b span.target -->
+ <target2>
+ <a></a>
+ <b>
+ <b></b> <!-- Fail here and restart backtracking. -->
+ <b>
+ <span class="target" id="target2"></span>
+ </b>
+ </b>
+ </target2>
+
+ <!-- c + c + d span.target -->
+ <target3>
+ <c></c>
+ <c></c>
+ <d>
+ <c></c>
+ <b></b> <!-- Fail here and restart backtracking with the parent of the current element. -->
+ <d>
+ <b></b> <!-- Fail here and restart backtracking with the parent of the current element. -->
+ <c></c>
+ <d>
+ <span class="target" id="target3"></span>
+ </d>
+ </d>
+ </d>
+ </target3>
+
+ <!-- e + f ~ g span.target -->
+ <target4>
+ <d></d>
+ <e></e>
+ <f></f>
+ <d></d>
+ <d></d>
+ <g>
+ <d></d> <!-- Fail here and restart backtracking indirect adjacent matching. -->
+ <f></f>
+ <g>
+ <span class="target" id="target4"></span>
+ </g>
+ </g>
+ </target4>
+
+ <!-- h + span.target -->
+ <target6>
+ <h></h>
+ <span class="target" id="target6.1"></span>
+ </target6>
+
+ <!-- h + span.target -->
+ <target6>
+ <a></a>
+ <span class="target" id="target6.2"></span>
+ </target6>
+
+ <!-- h + span.target -->
+ <target6>
+ <span class="target" id="target6.3"></span>
+ </target6>
+
+ <!-- j+j+j~j>k span.target -->
+ <target7>
+ <d></d> <!-- Fail here. -->
+ <j></j>
+ <j></j>
+ <j></j>
+ <k>
+ <span class="target" id="target7"></span>
+ </k>
+ </target7>
+
+ <!-- j+j+j~j>k span.target -->
+ <target8>
+ <j></j> <!-- Match here. -->
+ <j></j>
+ <j></j>
+ <j></j>
+ <d></d> <!-- Fail here. -->
+ <j></j>
+ <j></j>
+ <j>
+ <k>
+ <span class="target" id="target8"></span>
+ </k>
+ </j>
+ </target8>
+
+ <!-- m l+l+l+l~m>m>m span.target -->
+ <target9>
+ <m>
+ <l></l> <!-- Fail here -->
+ <l></l>
+ <l></l>
+ <m>
+ <a></a> <!-- Fail here and backtrack with the tail -->
+ <l></l>
+ <l></l>
+ <a></a> <!-- Fail here -->
+ <l></l>
+ <m>
+ <m>
+ <m>
+ <span class="target" id="target9"></span>
+ </m>
+ </m>
+ </m>
+ </m>
+ </m>
+ </target9>
+
+ <!-- m l+l+l+l~m>m>m span.target -->
+ <target10>
+ <m>
+ <l></l> <!-- Match here -->
+ <l></l>
+ <l></l>
+ <l></l>
+ <m>
+ <a></a> <!-- Fail here and backtrack with the tail -->
+ <l></l>
+ <l></l>
+ <a></a> <!-- Fail here -->
+ <l></l>
+ <m>
+ <m>
+ <m>
+ <span class="target" id="target10"></span>
+ </m>
+ </m>
+ </m>
+ </m>
+ </m>
+ </target10>
+
+ <!-- n o~n>n>n span.target -->
+ <target11>
+ <n>
+ <a></a> <!-- Fail here -->
+ <n>
+ <a></a> <!-- Fail here and backtrack with the tail -->
+ <a></a> <!-- Fail here -->
+ <n>
+ <n>
+ <n>
+ <span class="target" id="target11"></span>
+ </n>
+ </n>
+ </n>
+ </n>
+ </n>
+ </target11>
+
+ <!-- n o~n>n>n span.target -->
+ <target12>
+ <n>
+ <o></o> <!-- Match here -->
+ <a></a> <!-- Fail here -->
+ <n>
+ <a></a> <!-- Fail here and backtrack with the tail -->
+ <a></a> <!-- Fail here -->
+ <n>
+ <n>
+ <n>
+ <span class="target" id="target12"></span>
+ </n>
+ </n>
+ </n>
+ </n>
+ </n>
+ </target12>
+
+ <!-- p ~ span.target -->
+ <target13>
+ <p></p> <!-- Match here -->
+ <span class="target" id="target13.1"></span>
+ </target13>
+
+ <!-- p ~ span.target -->
+ <target13>
+ <a></a> <!-- Fail here -->
+ <span class="target" id="target13.2"></span>
+ </target13>
+
+ <!-- p ~ span.target -->
+ <target13>
+ <!-- Fail here -->
+ <span class="target" id="target13.3"></span>
+ </target13>
+
+ <!-- q ~ r span.target -->
+ <target14>
+ <q></q> <!-- Match here -->
+ <a></a>
+ <r>
+ <a></a> <!-- Fail here -->
+ <r>
+ <span class="target" id="target14.1"></span>
+ </r>
+ </r>
+ </target14>
+
+ <!-- q ~ r span.target -->
+ <target14>
+ <!-- Fail here -->
+ <r>
+ <a></a> <!-- Fail here -->
+ <r>
+ <span class="target" id="target14.2"></span>
+ </r>
+ </r>
+ </target14>
+
+ <!-- q ~ r span.target -->
+ <target14>
+ <!-- Fail here -->
+ <r>
+ <!-- Fail here -->
+ <r>
+ <span class="target" id="target14.3"></span>
+ </r>
+ </r>
+ </target14>
+
+ <!-- s t+t+t+s>s>s span.target -->
+ <target15>
+ <s>
+ <!-- Fail here and backtrack with the tail -->
+ <t></t>
+ <t></t>
+ <s>
+ <a></a> <!-- Fail here and backtrack with the tail -->
+ <t></t>
+ <t></t>
+ <s>
+ <s>
+ <s>
+ <span class="target" id="target15"></span>
+ </s>
+ </s>
+ </s>
+ </s>
+ </s>
+ </target15>
+
+ <!-- s t+t+t+s>s>s span.target -->
+ <target16>
+ <s>
+ <t></t> <!-- Match here -->
+ <t></t>
+ <t></t>
+ <s>
+ <!-- Fail here and backtrack with the tail -->
+ <t></t>
+ <t></t>
+ <s>
+ <a></a> <!-- Fail here and backtrack with the tail -->
+ <t></t>
+ <t></t>
+ <s>
+ <s>
+ <s>
+ <span class="target" id="target16"></span>
+ </s>
+ </s>
+ </s>
+ </s>
+ </s>
+ </s>
+ </target16>
+</div>
+</body>
+<script>
+description('The backtracking from adjacent combinators');
+
+debug("Backtracking without tail, succeeded without backtracking");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target1")).backgroundColor', 'rgb(1, 2, 3)');
+
+debug("Backtracking without tail without indirect adjacent, failed and restart.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target2")).backgroundColor', 'rgb(1, 2, 3)');
+
+debug("Backtracking without tail, 2 direct adjacents without indirect adjacent, failed and restart backtracking.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target3")).backgroundColor', 'rgb(4, 5, 6)');
+
+debug("Backtracking without tail, indirect adjacent.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target4")).backgroundColor', 'rgb(7, 8, 9)');
+
+debug("Backtracking from direct adjacent without tail. Matches.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target6.1")).backgroundColor', 'rgb(10, 11, 12)');
+
+debug("Backtracking from direct adjacent tag matching without tail. Fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target6.2")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from direct adjacent traversal without tail. Fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target6.3")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking without tail. And fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target7")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking without tail. And Matches.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target8")).backgroundColor', 'rgb(13, 14, 15)');
+
+debug("Backtracking from direct adjacent with tail. And fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target9")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from direct adjacent with tail. And Matches.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target10")).backgroundColor', 'rgb(16, 17, 18)');
+
+debug("Backtracking from indirect adjacent with tail. And fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target11")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from indirect adjacent with tail. And Matches.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target12")).backgroundColor', 'rgb(19, 20, 21)');
+
+debug("Backtracking from indirect adjacent without tail. Matches.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target13.1")).backgroundColor', 'rgb(22, 23, 24)');
+
+debug("Backtracking from indirect adjacent tag matching without tail. Fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target13.2")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from indirect adjacent traversal without tail. Fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target13.3")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from indirect adjacent without tail. Matches.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target14.1")).backgroundColor', 'rgb(25, 26, 27)');
+
+debug("Backtracking from indirect adjacent tag matching without tail. Fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target14.2")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from indirect adjacent traversal without tail. Fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target14.3")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from direct adjacent with tail. And fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target15")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking from direct adjacent with tail. And Matches.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target16")).backgroundColor', 'rgb(28, 29, 30)');
+</script>
+<script src="../../resources/js-test-post.js"></script>
+</html>
</ins></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (168235 => 168236)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2014-05-04 03:22:04 UTC (rev 168235)
+++ trunk/Source/WebCore/ChangeLog 2014-05-04 03:25:56 UTC (rev 168236)
</span><span class="lines">@@ -1,3 +1,52 @@
</span><ins>+2014-05-03 Yusuke Suzuki <utatane.tea@gmail.com>
+
+ CSS JIT: optimize direct / indirect adjacent's traversal backtracking
+ https://bugs.webkit.org/show_bug.cgi?id=132319
+
+ Reviewed by Benjamin Poulain.
+
+ Since adjacent backtracking stack reference is pre-allocated
+ in prologue in http://trac.webkit.org/changeset/166834,
+ clearing stack phase is not needed. So we can drop
+ JumpToClearAdjacentTail from backtracking action and simplify
+ backtracking handling.
+ And optimize direct / indirect adjacent's traversal backtracking by
+ using appropriate backtracking height.
+
+ When solving adjacent traversal backtracking action,
+ 1) When there's no descendant relation on the right, traversal
+ failure becomes global failure.
+ 2) When `tagNameMatchedBacktrackingStartHeightFromDescendant` ==
+ `heightFromDescendant` + 1, the descendant backtracking starts with
+ the parent of the current element. So we can use the current element
+ and the backtracking action is JumpToDescendantTreeWalkerEntryPoint.
+ 3) Otherwise, currently we take the conservative approach,
+ JumpToDescendantTail.
+
+ NOTE:
+ And if `hasDescendantRelationOnTheRight` is true and there's no child
+ fragment on the right, the backtracking element register is not
+ effective. So we should ensure that fragment doesn't use the
+ backtracking element register. Such a fragment fulfills the following
+ conditions. 1. tagNameMatchedBacktrackingStartHeightFromDescendant is
+ always 1 (tagNames.size(), that contains only descendant fragment) 2.
+ heightFromDescendant is always 0 (-- See
+ computeBacktrackingHeightFromDescendant implementation) Therefore such
+ a fragment's action always becomes
+ JumpToDescendantTreeWalkerEntryPoint. So we can ensure that the
+ backtracking element register is not used.
+
+ Test: fast/selectors/backtracking-adjacent.html
+
+ * cssjit/SelectorCompiler.cpp:
+ (WebCore::SelectorCompiler::solveDescendantBacktrackingActionForChild):
+ (WebCore::SelectorCompiler::solveAdjacentTraversalBacktrackingAction):
+ (WebCore::SelectorCompiler::solveBacktrackingAction):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::computeBacktrackingInformation):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::linkFailures):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateAdjacentBacktrackingTail):
+ (WebCore::SelectorCompiler::isAfterChildRelation): Deleted.
+
</ins><span class="cx"> 2014-05-03 Andreas Kling <akling@apple.com>
</span><span class="cx">
</span><span class="cx"> Clear the JSString cache when under memory pressure.
</span></span></pre></div>
<a id="trunkSourceWebCorecssjitSelectorCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/cssjit/SelectorCompiler.cpp (168235 => 168236)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-05-04 03:22:04 UTC (rev 168235)
+++ trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-05-04 03:25:56 UTC (rev 168236)
</span><span class="lines">@@ -65,8 +65,7 @@
</span><span class="cx"> JumpToIndirectAdjacentEntryPoint,
</span><span class="cx"> JumpToDescendantTreeWalkerEntryPoint,
</span><span class="cx"> JumpToDescendantTail,
</span><del>- JumpToDirectAdjacentTail,
- JumpToClearAdjacentTail
</del><ins>+ JumpToDirectAdjacentTail
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> struct BacktrackingFlag {
</span><span class="lines">@@ -241,7 +240,6 @@
</span><span class="cx"> Assembler::JumpList m_descendantBacktrackingFailureCases;
</span><span class="cx"> StackAllocator::StackReference m_adjacentBacktrackingStart;
</span><span class="cx"> Assembler::JumpList m_adjacentBacktrackingFailureCases;
</span><del>- Assembler::JumpList m_clearAdjacentBacktrackingFailureCases;
</del><span class="cx">
</span><span class="cx"> #if CSS_SELECTOR_JIT_DEBUGGING
</span><span class="cx"> const CSSSelector* m_originalSelector;
</span><span class="lines">@@ -592,13 +590,8 @@
</span><span class="cx"> return adjacentPositionSinceIndirectAdjacentTreeWalk == 1;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static inline bool isAfterChildRelation(unsigned ancestorPositionSinceDescendantRelation)
</del><ins>+static inline BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
</ins><span class="cx"> {
</span><del>- return ancestorPositionSinceDescendantRelation > 0;
-}
-
-static BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
-{
</del><span class="cx"> // If height is invalid (e.g. There's no tag name).
</span><span class="cx"> if (backtrackingStartHeightFromDescendant == invalidHeight)
</span><span class="cx"> return BacktrackingAction::NoBacktracking;
</span><span class="lines">@@ -614,8 +607,19 @@
</span><span class="cx"> return BacktrackingAction::JumpToDescendantTail;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, unsigned ancestorPositionSinceDescendantRelation, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
</del><ins>+static inline BacktrackingAction solveAdjacentTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)
</ins><span class="cx"> {
</span><ins>+ if (!hasDescendantRelationOnTheRight)
+ return BacktrackingAction::NoBacktracking;
+
+ if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
+ return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
+
+ return BacktrackingAction::JumpToDescendantTail;
+}
+
+static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
+{
</ins><span class="cx"> switch (fragment.relationToRightFragment) {
</span><span class="cx"> case FragmentRelation::Rightmost:
</span><span class="cx"> case FragmentRelation::Descendant:
</span><span class="lines">@@ -630,20 +634,7 @@
</span><span class="cx"> case FragmentRelation::DirectAdjacent:
</span><span class="cx"> // Failure on traversal implies no other sibling traversal can match. Matching should resume at the
</span><span class="cx"> // nearest ancestor/descendant traversal.
</span><del>- if (hasDescendantRelationOnTheRight) {
- if (!isAfterChildRelation(ancestorPositionSinceDescendantRelation))
- fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
- else {
- if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain || isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
- fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
- else
- fragment.traversalBacktrackingAction = BacktrackingAction::JumpToClearAdjacentTail;
- }
- } else {
- // If we are in a direct adjacent chain with backtracking, we need to clear the backtracking register on the stack.
- if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain && !isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
- fragment.traversalBacktrackingAction = BacktrackingAction::JumpToClearAdjacentTail;
- }
</del><ins>+ fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
</ins><span class="cx">
</span><span class="cx"> // If the rightmost relation is a indirect adjacent, matching sould resume from there.
</span><span class="cx"> // Otherwise, we resume from the latest ancestor/descendant if any.
</span><span class="lines">@@ -656,24 +647,15 @@
</span><span class="cx"> fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
</span><span class="cx"> }
</span><span class="cx"> } else if (hasDescendantRelationOnTheRight) {
</span><del>- if (isAfterChildRelation(ancestorPositionSinceDescendantRelation)) {
- fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
- fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
- } else {
- fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
- fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
- }
</del><ins>+ // Since we resume from the latest ancestor/descendant, the action is the same as the traversal action.
+ fragment.matchingTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
+ fragment.matchingPostTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
</ins><span class="cx"> }
</span><span class="cx"> break;
</span><span class="cx"> case FragmentRelation::IndirectAdjacent:
</span><span class="cx"> // Failure on traversal implies no other sibling matching will succeed. Matching can resume
</span><span class="cx"> // from the latest ancestor/descendant.
</span><del>- if (hasDescendantRelationOnTheRight) {
- if (isAfterChildRelation(ancestorPositionSinceDescendantRelation))
- fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
- else
- fragment.traversalBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
- }
</del><ins>+ fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -830,7 +812,7 @@
</span><span class="cx"> dataLogF("Computing fragment[%d] backtracking height %u. NotMatched %u / Matched %u\n", i, fragment.heightFromDescendant, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
</del><ins>+ solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
</ins><span class="cx">
</span><span class="cx"> needsAdjacentTail |= requiresAdjacentTail(fragment);
</span><span class="cx"> needsDescendantTail |= requiresDescendantTail(fragment);
</span><span class="lines">@@ -1303,9 +1285,6 @@
</span><span class="cx"> case BacktrackingAction::JumpToDirectAdjacentTail:
</span><span class="cx"> m_adjacentBacktrackingFailureCases.append(localFailureCases);
</span><span class="cx"> break;
</span><del>- case BacktrackingAction::JumpToClearAdjacentTail:
- m_clearAdjacentBacktrackingFailureCases.append(localFailureCases);
- break;
</del><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -1317,9 +1296,6 @@
</span><span class="cx"> unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
</span><span class="cx"> m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToAdjacentBacktrackingStart), elementAddressRegister);
</span><span class="cx"> m_assembler.jump(m_indirectAdjacentEntryPoint);
</span><del>-
- // Total failure tail.
- m_clearAdjacentBacktrackingFailureCases.link(&m_assembler);
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void SelectorCodeGenerator::generateDescendantBacktrackingTail()
</span></span></pre>
</div>
</div>
</body>
</html>