<!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>[167920] 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/167920">167920</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2014-04-28 18:58:38 -0700 (Mon, 28 Apr 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>CSS JIT: backtracking with current / parent element for child
https://bugs.webkit.org/show_bug.cgi?id=132057
Patch by Yusuke Suzuki <utatane.tea@gmail.com> on 2014-04-28
Reviewed by Benjamin Poulain.
Calculate appropriate backtracking start height from the closest
descendant. And at first, we use it for a simple optimization.
1. When backtracking start height equals to current height, we
can simply jump to a descendant element check phase.
2. When backtracking start height equals to current height + 1, we
can simply jump to a descendant element traversing phase.
We can apply this optimization to fragments with adjacent combinators.
But, in the meantime, we start to implement it for a fragment with
child combinator.
Source/WebCore:
* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::SelectorFragment::SelectorFragment):
(WebCore::SelectorCompiler::TagNamePattern::TagNamePattern):
(WebCore::SelectorCompiler::solveDescendantBacktrackingActionForChild):
(WebCore::SelectorCompiler::solveBacktrackingAction):
(WebCore::SelectorCompiler::equalTagNames):
(WebCore::SelectorCompiler::equalTagNamePatterns):
(WebCore::SelectorCompiler::computeBacktrackingStartHeightFromDescendant):
(WebCore::SelectorCompiler::computeBacktrackingHeightFromDescendant):
(WebCore::SelectorCompiler::requiresAdjacentTail):
(WebCore::SelectorCompiler::requiresDescendantTail):
(WebCore::SelectorCompiler::SelectorCodeGenerator::computeBacktrackingInformation):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateSelectorChecker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentNode):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentElement):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateParentElementTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateAncestorTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateDirectAdjacentTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateIndirectAdjacentTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
LayoutTests:
* fast/selectors/backtracking-child-combinator-with-tail-expected.txt: Added.
* fast/selectors/backtracking-child-combinator-with-tail.html: Added.
* fast/selectors/backtracking-child-combinator-without-tail-expected.txt: Added.
* fast/selectors/backtracking-child-combinator-without-tail.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="#trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithtailexpectedtxt">trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail-expected.txt</a></li>
<li><a href="#trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithtailhtml">trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail.html</a></li>
<li><a href="#trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithouttailexpectedtxt">trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail-expected.txt</a></li>
<li><a href="#trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithouttailhtml">trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail.html</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (167919 => 167920)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog        2014-04-29 01:54:21 UTC (rev 167919)
+++ trunk/LayoutTests/ChangeLog        2014-04-29 01:58:38 UTC (rev 167920)
</span><span class="lines">@@ -1,3 +1,27 @@
</span><ins>+2014-04-28 Yusuke Suzuki <utatane.tea@gmail.com>
+
+ CSS JIT: backtracking with current / parent element for child
+ https://bugs.webkit.org/show_bug.cgi?id=132057
+
+ Reviewed by Benjamin Poulain.
+
+ Calculate appropriate backtracking start height from the closest
+ descendant. And at first, we use it for a simple optimization.
+
+ 1. When backtracking start height equals to current height, we
+ can simply jump to a descendant element check phase.
+ 2. When backtracking start height equals to current height + 1, we
+ can simply jump to a descendant element traversing phase.
+
+ We can apply this optimization to fragments with adjacent combinators.
+ But, in the meantime, we start to implement it for a fragment with
+ child combinator.
+
+ * fast/selectors/backtracking-child-combinator-with-tail-expected.txt: Added.
+ * fast/selectors/backtracking-child-combinator-with-tail.html: Added.
+ * fast/selectors/backtracking-child-combinator-without-tail-expected.txt: Added.
+ * fast/selectors/backtracking-child-combinator-without-tail.html: Added.
+
</ins><span class="cx"> 2014-04-28 Ryuan Choi <ryuan.choi@samsung.com>
</span><span class="cx">
</span><span class="cx"> Unreviewed EFL gardening.
</span></span></pre></div>
<a id="trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithtailexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail-expected.txt (0 => 167920)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail-expected.txt         (rev 0)
+++ trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail-expected.txt        2014-04-29 01:58:38 UTC (rev 167920)
</span><span class="lines">@@ -0,0 +1,17 @@
</span><ins>+The backtracking child combinator with tail cases
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+Backtracking with tail, tag name matching failed. Restart with the backtracking start element.
+PASS getComputedStyle(document.getElementById("target1")).backgroundColor is "rgb(1, 2, 3)"
+Backtracking with tail, tag name matching failed. Restart with the backtracking start element. And fails.
+PASS getComputedStyle(document.getElementById("target2")).backgroundColor is "rgb(0, 0, 0)"
+Backtracking with tail, others matching failed. Restart with the backtracking start element.
+PASS getComputedStyle(document.getElementById("target3")).backgroundColor is "rgb(4, 5, 6)"
+Backtracking with tail, others matching failed. Restart with the backtracking start element. And fails.
+PASS getComputedStyle(document.getElementById("target4")).backgroundColor is "rgb(0, 0, 0)"
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithtailhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail.html (0 => 167920)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail.html         (rev 0)
+++ trunk/LayoutTests/fast/selectors/backtracking-child-combinator-with-tail.html        2014-04-29 01:58:38 UTC (rev 167920)
</span><span class="lines">@@ -0,0 +1,112 @@
</span><ins>+<!doctype html>
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+<style>
+/* default */
+span.target {
+ background-color:rgb(0,0,0);
+}
+a > b > b > b span.target {
+ background-color:rgb(1,2,3);
+}
+c.ok > c > c > c span.target {
+ background-color:rgb(4,5,6);
+}
+</style>
+</head>
+<body>
+<div style="display:none">
+ <a>
+ <!-- selector "a" fails here and start normal backtracking (with tail) !-->
+ <b>
+ <!-- selector "a" fails here and start normal backtracking (with tail) !-->
+ <b>
+ <b>
+ <b>
+ <b>
+ <b>
+ <span class="target" id="target1"></span>
+ </b>
+ </b>
+ </b>
+ </b>
+ </b>
+ </b>
+ </a>
+
+ <!-- selector "a" fails here and start normal backtracking (with tail). And fails. !-->
+ <b>
+ <!-- selector "a" fails here and start normal backtracking (with tail) !-->
+ <b>
+ <!-- selector "a" fails here and start normal backtracking (with tail) !-->
+ <b>
+ <b>
+ <b>
+ <b>
+ <b>
+ <span class="target" id="target2"></span>
+ </b>
+ </b>
+ </b>
+ </b>
+ </b>
+ </b>
+ </b>
+
+ <c class="ok">
+ <!-- selector "c.ok" fails here and start normal backtracking (with tail) !-->
+ <c class="ng">
+ <!-- selector "c.ok" fails here and start normal backtracking (with tail) !-->
+ <c class="ng">
+ <c>
+ <c>
+ <c>
+ <c>
+ <span class="target" id="target3"></span>
+ </c>
+ </c>
+ </c>
+ </c>
+ </c>
+ </c>
+ </c>
+
+ <!-- selector "c.ok" fails here and start normal backtracking (with tail). And fails. !-->
+ <c class="ng">
+ <!-- selector "c.ok" fails here and start normal backtracking (with tail) !-->
+ <c class="ng">
+ <!-- selector "c.ok" fails here and start normal backtracking (with tail) !-->
+ <c class="ng">
+ <c>
+ <c>
+ <c>
+ <c>
+ <span class="target" id="target4"></span>
+ </c>
+ </c>
+ </c>
+ </c>
+ </c>
+ </c>
+ </c>
+</div>
+</body>
+<script>
+description('The backtracking child combinator with tail cases');
+
+debug("Backtracking with tail, tag name matching failed. Restart with the backtracking start element.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target1")).backgroundColor', 'rgb(1, 2, 3)');
+
+debug("Backtracking with tail, tag name matching failed. Restart with the backtracking start element. And fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target2")).backgroundColor', 'rgb(0, 0, 0)');
+
+debug("Backtracking with tail, others matching failed. Restart with the backtracking start element.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target3")).backgroundColor', 'rgb(4, 5, 6)');
+
+debug("Backtracking with tail, others matching failed. Restart with the backtracking start element. And fails.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target4")).backgroundColor', 'rgb(0, 0, 0)');
+</script>
+<script src="../../resources/js-test-post.js"></script>
+</html>
+
</ins></span></pre></div>
<a id="trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithouttailexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail-expected.txt (0 => 167920)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail-expected.txt         (rev 0)
+++ trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail-expected.txt        2014-04-29 01:58:38 UTC (rev 167920)
</span><span class="lines">@@ -0,0 +1,23 @@
</span><ins>+The backtracking child combinator without tail cases
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+Backtracking immediately with the current element, tag name matching failed. Restart with the current element
+PASS getComputedStyle(document.getElementById("target1")).backgroundColor is "rgb(1, 2, 3)"
+Backtracking immediately with the current element, others matching failed. Restart with the parent of the current element.(with parent check)
+PASS getComputedStyle(document.getElementById("target2")).backgroundColor is "rgb(4, 5, 6)"
+Backtracking immediately with the current element. Restart with the current element.
+PASS getComputedStyle(document.getElementById("target3")).backgroundColor is "rgb(4, 5, 6)"
+Backtracking immediately with the current element. Restart with the current element.
+PASS getComputedStyle(document.getElementById("target4")).backgroundColor is "rgb(7, 8, 9)"
+Backtracking immediately with the current element. Restart with the parent of the current element.
+PASS getComputedStyle(document.getElementById("target5")).backgroundColor is "rgb(10, 11, 12)"
+Backtracking immediately with the current element (selector doesn't has tag name). Restart with the current element.
+PASS getComputedStyle(document.getElementById("target6")).backgroundColor is "rgb(13, 14, 15)"
+Backtracking immediately with the current element (there's no tail). Restart with the current element.
+PASS getComputedStyle(document.getElementById("target7")).backgroundColor is "rgb(16, 17, 18)"
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsfastselectorsbacktrackingchildcombinatorwithouttailhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail.html (0 => 167920)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail.html         (rev 0)
+++ trunk/LayoutTests/fast/selectors/backtracking-child-combinator-without-tail.html        2014-04-29 01:58:38 UTC (rev 167920)
</span><span class="lines">@@ -0,0 +1,161 @@
</span><ins>+<!doctype html>
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+<style>
+/* default */
+span.target {
+ background-color:rgb(0,0,0);
+}
+a > b > c span.target {
+ background-color:rgb(1,2,3);
+}
+d.ok > e > f span.target {
+ background-color:rgb(4,5,6);
+}
+g.ok > h > g span.target {
+ background-color:rgb(7,8,9);
+}
+i > j > j > j > j span.target {
+ background-color:rgb(10,11,12);
+}
+.ok > k > l span.target {
+ background-color:rgb(13,14,15);
+}
+.ok > l span.target {
+ background-color:rgb(16,17,18);
+}
+</style>
+</head>
+<body>
+<div style="display:none">
+ <a>
+ <b>
+ <!-- selector "a" fails here and start descendant backtracking with this element !-->
+ <c>
+ <b>
+ <c>
+ <span class="target" id="target1"></span>
+ </c>
+ </b>
+ </c>
+ </b>
+ </a>
+
+ <d class="ok">
+ <e>
+ <f>
+ <!-- selector "d.ok" fails here and start descendant backtracking with parent of this element !-->
+ <d class="ng">
+ <e>
+ <f>
+ <span class="target" id="target2"></span>
+ </f>
+ </e>
+ </d>
+ </f>
+ </e>
+ </d>
+
+ <d class="ok">
+ <e>
+ <!-- selector "d.ok" fails here and start descendant backtracking with this element !-->
+ <f class="ng">
+ <e>
+ <f>
+ <span class="target" id="target3"></span>
+ </f>
+ </e>
+ </f>
+ </e>
+ </d>
+
+ <g class="ok">
+ <h>
+ <!-- selector "g.ok" fails here and start descendant backtracking with this element (since tag name is g) !-->
+ <g class="ng">
+ <h>
+ <g>
+ <span class="target" id="target4"></span>
+ </g>
+ </h>
+ </g>
+ </h>
+ </g>
+
+ <i>
+ <j>
+ <j>
+ <j>
+ <j>
+ <!-- selector "i" fails here and start descendant backtracking with the parent of this element (since tag name "c") !-->
+ <c>
+ <j>
+ <j>
+ <j>
+ <j>
+ <span class="target" id="target5"></span>
+ </j>
+ </j>
+ </j>
+ </j>
+ </c>
+ </j>
+ </j>
+ </j>
+ </j>
+ </i>
+
+ <k class="ok">
+ <k>
+ <!-- selector ".ok" fails here and start descendant backtracking with this element !-->
+ <l class="ng">
+ <k>
+ <l>
+ <span class="target" id="target6"></span>
+ </l>
+ </k>
+ </l>
+ </k>
+ </k>
+
+ <k class="ok">
+ <!-- selector ".ok" fails here and start descendant backtracking with this element !-->
+ <l>
+ <!-- selector ".ok" fails here and start descendant backtracking with this element !-->
+ <l class="ng">
+ <l>
+ <span class="target" id="target7"></span>
+ </l>
+ </l>
+ </l>
+ </k>
+</div>
+</body>
+<script>
+description('The backtracking child combinator without tail cases');
+
+debug("Backtracking immediately with the current element, tag name matching failed. Restart with the current element");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target1")).backgroundColor', 'rgb(1, 2, 3)');
+
+debug("Backtracking immediately with the current element, others matching failed. Restart with the parent of the current element.(with parent check)");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target2")).backgroundColor', 'rgb(4, 5, 6)');
+
+debug("Backtracking immediately with the current element. Restart with the current element.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target3")).backgroundColor', 'rgb(4, 5, 6)');
+
+debug("Backtracking immediately with the current element. Restart with the current element.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target4")).backgroundColor', 'rgb(7, 8, 9)');
+
+debug("Backtracking immediately with the current element. Restart with the parent of the current element.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target5")).backgroundColor', 'rgb(10, 11, 12)');
+
+debug("Backtracking immediately with the current element (selector doesn't has tag name). Restart with the current element.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target6")).backgroundColor', 'rgb(13, 14, 15)');
+
+debug("Backtracking immediately with the current element (there's no tail). Restart with the current element.");
+shouldBeEqualToString('getComputedStyle(document.getElementById("target7")).backgroundColor', 'rgb(16, 17, 18)');
+</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 (167919 => 167920)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog        2014-04-29 01:54:21 UTC (rev 167919)
+++ trunk/Source/WebCore/ChangeLog        2014-04-29 01:58:38 UTC (rev 167920)
</span><span class="lines">@@ -1,3 +1,43 @@
</span><ins>+2014-04-28 Yusuke Suzuki <utatane.tea@gmail.com>
+
+ CSS JIT: backtracking with current / parent element for child
+ https://bugs.webkit.org/show_bug.cgi?id=132057
+
+ Reviewed by Benjamin Poulain.
+
+ Calculate appropriate backtracking start height from the closest
+ descendant. And at first, we use it for a simple optimization.
+
+ 1. When backtracking start height equals to current height, we
+ can simply jump to a descendant element check phase.
+ 2. When backtracking start height equals to current height + 1, we
+ can simply jump to a descendant element traversing phase.
+
+ We can apply this optimization to fragments with adjacent combinators.
+ But, in the meantime, we start to implement it for a fragment with
+ child combinator.
+
+ * cssjit/SelectorCompiler.cpp:
+ (WebCore::SelectorCompiler::SelectorFragment::SelectorFragment):
+ (WebCore::SelectorCompiler::TagNamePattern::TagNamePattern):
+ (WebCore::SelectorCompiler::solveDescendantBacktrackingActionForChild):
+ (WebCore::SelectorCompiler::solveBacktrackingAction):
+ (WebCore::SelectorCompiler::equalTagNames):
+ (WebCore::SelectorCompiler::equalTagNamePatterns):
+ (WebCore::SelectorCompiler::computeBacktrackingStartHeightFromDescendant):
+ (WebCore::SelectorCompiler::computeBacktrackingHeightFromDescendant):
+ (WebCore::SelectorCompiler::requiresAdjacentTail):
+ (WebCore::SelectorCompiler::requiresDescendantTail):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::computeBacktrackingInformation):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateSelectorChecker):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentNode):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentElement):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateParentElementTreeWalker):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateAncestorTreeWalker):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateDirectAdjacentTreeWalker):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateIndirectAdjacentTreeWalker):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
+
</ins><span class="cx"> 2014-04-28 Benjamin Poulain <bpoulain@apple.com>
</span><span class="cx">
</span><span class="cx"> [iOS][WK2] Restore the scroll position and scale from the HistoryItem (mostly)
</span></span></pre></div>
<a id="trunkSourceWebCorecssjitSelectorCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/cssjit/SelectorCompiler.cpp (167919 => 167920)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/cssjit/SelectorCompiler.cpp        2014-04-29 01:54:21 UTC (rev 167919)
+++ trunk/Source/WebCore/cssjit/SelectorCompiler.cpp        2014-04-29 01:58:38 UTC (rev 167920)
</span><span class="lines">@@ -1,5 +1,6 @@
</span><span class="cx"> /*
</span><span class="cx"> * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
</span><ins>+ * Copyright (C) 2014 Yusuke Suzuki <utatane.tea@gmail.com>
</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">@@ -47,6 +48,7 @@
</span><span class="cx"> #include <JavaScriptCore/LinkBuffer.h>
</span><span class="cx"> #include <JavaScriptCore/MacroAssembler.h>
</span><span class="cx"> #include <JavaScriptCore/VM.h>
</span><ins>+#include <limits>
</ins><span class="cx"> #include <wtf/HashMap.h>
</span><span class="cx"> #include <wtf/HashSet.h>
</span><span class="cx"> #include <wtf/Vector.h>
</span><span class="lines">@@ -110,11 +112,17 @@
</span><span class="cx"> bool m_canDefaultToCaseSensitiveValueMatch;
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+static const unsigned invalidHeight = std::numeric_limits<unsigned>::max();
+
</ins><span class="cx"> struct SelectorFragment {
</span><span class="cx"> SelectorFragment()
</span><span class="cx"> : traversalBacktrackingAction(BacktrackingAction::NoBacktracking)
</span><del>- , matchingBacktrackingAction(BacktrackingAction::NoBacktracking)
</del><ins>+ , matchingTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
+ , matchingPostTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
</ins><span class="cx"> , backtrackingFlags(0)
</span><ins>+ , tagNameMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
+ , tagNameNotMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
+ , heightFromDescendant(0)
</ins><span class="cx"> , tagName(nullptr)
</span><span class="cx"> , id(nullptr)
</span><span class="cx"> {
</span><span class="lines">@@ -123,8 +131,12 @@
</span><span class="cx"> FragmentRelation relationToRightFragment;
</span><span class="cx">
</span><span class="cx"> BacktrackingAction traversalBacktrackingAction;
</span><del>- BacktrackingAction matchingBacktrackingAction;
</del><ins>+ BacktrackingAction matchingTagNameBacktrackingAction;
+ BacktrackingAction matchingPostTagNameBacktrackingAction;
</ins><span class="cx"> unsigned char backtrackingFlags;
</span><ins>+ unsigned tagNameMatchedBacktrackingStartHeightFromDescendant;
+ unsigned tagNameNotMatchedBacktrackingStartHeightFromDescendant;
+ unsigned heightFromDescendant;
</ins><span class="cx">
</span><span class="cx"> const QualifiedName* tagName;
</span><span class="cx"> const AtomicString* id;
</span><span class="lines">@@ -135,8 +147,19 @@
</span><span class="cx"> Vector<std::pair<int, int>> nthChildfilters;
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+struct TagNamePattern {
+ TagNamePattern()
+ : tagName(nullptr)
+ , inverted(false)
+ {
+ }
+ const QualifiedName* tagName;
+ bool inverted;
+};
+
</ins><span class="cx"> typedef JSC::MacroAssembler Assembler;
</span><span class="cx"> typedef Vector<SelectorFragment, 8> SelectorFragmentList;
</span><ins>+typedef Vector<TagNamePattern, 8> TagNameList;
</ins><span class="cx">
</span><span class="cx"> class SelectorCodeGenerator {
</span><span class="cx"> public:
</span><span class="lines">@@ -152,6 +175,7 @@
</span><span class="cx"> void generateSelectorChecker();
</span><span class="cx">
</span><span class="cx"> // Element relations tree walker.
</span><ins>+ void generateWalkToParentNode(Assembler::RegisterID targetRegister);
</ins><span class="cx"> void generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister);
</span><span class="cx"> void generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
</span><span class="cx"> void generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
</span><span class="lines">@@ -170,7 +194,7 @@
</span><span class="cx"> void generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
</span><span class="cx">
</span><span class="cx"> // Element properties matchers.
</span><del>- void generateElementMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
</del><ins>+ void generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment&);
</ins><span class="cx"> void generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
</span><span class="cx"> void generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
</span><span class="cx"> Assembler::JumpList jumpIfNoPreviousAdjacentElement();
</span><span class="lines">@@ -573,6 +597,23 @@
</span><span class="cx"> return ancestorPositionSinceDescendantRelation > 0;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+static BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
+{
+ // If height is invalid (e.g. There's no tag name).
+ if (backtrackingStartHeightFromDescendant == invalidHeight)
+ return BacktrackingAction::NoBacktracking;
+
+ // Start backtracking from the current element.
+ if (backtrackingStartHeightFromDescendant == fragment.heightFromDescendant)
+ return BacktrackingAction::JumpToDescendantEntryPoint;
+
+ // Start backtracking from the parent of current element.
+ if (backtrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
+ return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
+
+ return BacktrackingAction::JumpToDescendantTail;
+}
+
</ins><span class="cx"> static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, unsigned ancestorPositionSinceDescendantRelation, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
</span><span class="cx"> {
</span><span class="cx"> switch (fragment.relationToRightFragment) {
</span><span class="lines">@@ -582,10 +623,8 @@
</span><span class="cx"> case FragmentRelation::Child:
</span><span class="cx"> // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
</span><span class="cx"> if (hasDescendantRelationOnTheRight) {
</span><del>- if (isFirstAncestor(ancestorPositionSinceDescendantRelation))
- fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantEntryPoint;
- else
- fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
</del><ins>+ fragment.matchingTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant);
+ fragment.matchingPostTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
</ins><span class="cx"> }
</span><span class="cx"> break;
</span><span class="cx"> case FragmentRelation::DirectAdjacent:
</span><span class="lines">@@ -609,15 +648,21 @@
</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="cx"> if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
</span><del>- if (isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
- fragment.matchingBacktrackingAction = BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
- else
- fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
</del><ins>+ if (isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
+ fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
+ fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
+ } else {
+ fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
+ fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
+ }
</ins><span class="cx"> } else if (hasDescendantRelationOnTheRight) {
</span><del>- if (isAfterChildRelation(ancestorPositionSinceDescendantRelation))
- fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
- else
- fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
</del><ins>+ if (isAfterChildRelation(ancestorPositionSinceDescendantRelation)) {
+ fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
+ fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
+ } else {
+ fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
+ fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
+ }
</ins><span class="cx"> }
</span><span class="cx"> break;
</span><span class="cx"> case FragmentRelation::IndirectAdjacent:
</span><span class="lines">@@ -633,15 +678,131 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+enum class TagNameEquality {
+ StrictlyNotEqual,
+ MaybeEqual,
+ StrictlyEqual
+};
+
+static inline TagNameEquality equalTagNames(const QualifiedName* lhs, const QualifiedName* rhs)
+{
+ if (!lhs || *lhs == anyQName())
+ return TagNameEquality::MaybeEqual;
+
+ if (!rhs || *rhs == anyQName())
+ return TagNameEquality::MaybeEqual;
+
+ ASSERT(lhs && rhs);
+
+ const AtomicString& lhsLocalName = lhs->localName();
+ const AtomicString& rhsLocalName = rhs->localName();
+ if (lhsLocalName != starAtom && rhsLocalName != starAtom) {
+ if (lhsLocalName != rhsLocalName)
+ return TagNameEquality::StrictlyNotEqual;
+ return TagNameEquality::StrictlyEqual;
+ }
+
+ const AtomicString& lhsNamespaceURI = lhs->namespaceURI();
+ const AtomicString& rhsNamespaceURI = rhs->namespaceURI();
+ if (lhsNamespaceURI != starAtom && rhsNamespaceURI != starAtom) {
+ if (lhsNamespaceURI != rhsNamespaceURI)
+ return TagNameEquality::StrictlyNotEqual;
+ return TagNameEquality::StrictlyEqual;
+ }
+
+ return TagNameEquality::MaybeEqual;
+}
+
+static inline bool equalTagNamePatterns(const TagNamePattern& lhs, const QualifiedName* rhs)
+{
+ TagNameEquality result = equalTagNames(lhs.tagName, rhs);
+ if (result == TagNameEquality::MaybeEqual)
+ return true;
+
+ // If both rhs & lhs have actual localName (or NamespaceURI),
+ // TagNameEquality result becomes StrictlyEqual or StrictlyNotEqual Since inverted lhs never matches on rhs.
+ bool equal = result == TagNameEquality::StrictlyEqual;
+ if (lhs.inverted)
+ return !equal;
+ return equal;
+}
+
+// Find the largest matching prefix from already known tagNames.
+// And by using this, compute an appropriate height of backtracking start element from the closest descendant.
+static inline unsigned computeBacktrackingStartHeightFromDescendant(const TagNameList& tagNames)
+{
+ RELEASE_ASSERT(!tagNames.isEmpty());
+
+ unsigned largestPrefixSize = tagNames.size();
+ while (--largestPrefixSize) {
+ unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
+ bool matched = true;
+ // Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
+ for (unsigned i = 0; i < largestPrefixSize; ++i) {
+ unsigned lastIndex = tagNames.size() - 1;
+ unsigned currentIndex = lastIndex - i;
+ if (!equalTagNamePatterns(tagNames[currentIndex], tagNames[currentIndex - offsetToLargestPrefix].tagName)) {
+ matched = false;
+ break;
+ }
+ }
+ if (matched)
+ return offsetToLargestPrefix;
+ }
+ return tagNames.size();
+}
+
+static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNames, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragmentInDescendantBacktrackingChain)
+{
+ if (!hasDescendantRelationOnTheRight)
+ return;
+
+ if (fragment.relationToRightFragment == FragmentRelation::Descendant) {
+ tagNames.clear();
+
+ TagNamePattern pattern;
+ pattern.tagName = fragment.tagName;
+ tagNames.append(pattern);
+ fragment.heightFromDescendant = 0;
+ previousChildFragmentInDescendantBacktrackingChain = nullptr;
+ } else if (fragment.relationToRightFragment == FragmentRelation::Child) {
+ TagNamePattern pattern;
+ pattern.tagName = fragment.tagName;
+ tagNames.append(pattern);
+
+ if (pattern.tagName) {
+ // Compute height from descendant in the case that tagName is not matched.
+ tagNames.last().inverted = true;
+ fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames);
+ }
+
+ // Compute height from descendant in the case that tagName is matched.
+ tagNames.last().inverted = false;
+ fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames);
+ fragment.heightFromDescendant = tagNames.size() - 1;
+ previousChildFragmentInDescendantBacktrackingChain = &fragment;
+ } else {
+ if (previousChildFragmentInDescendantBacktrackingChain) {
+ fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInDescendantBacktrackingChain->tagNameNotMatchedBacktrackingStartHeightFromDescendant;
+ fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInDescendantBacktrackingChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
+ fragment.heightFromDescendant = previousChildFragmentInDescendantBacktrackingChain->heightFromDescendant;
+ } else {
+ fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = tagNames.size();
+ fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = tagNames.size();
+ fragment.heightFromDescendant = 0;
+ }
+ }
+}
+
</ins><span class="cx"> static bool requiresAdjacentTail(const SelectorFragment& fragment)
</span><span class="cx"> {
</span><span class="cx"> ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
</span><del>- return fragment.matchingBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
</del><ins>+ return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> static bool requiresDescendantTail(const SelectorFragment& fragment)
</span><span class="cx"> {
</span><del>- return fragment.matchingBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
</del><ins>+ return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void SelectorCodeGenerator::computeBacktrackingInformation()
</span><span class="lines">@@ -653,12 +814,22 @@
</span><span class="cx">
</span><span class="cx"> bool needsAdjacentTail = false;
</span><span class="cx"> bool needsDescendantTail = false;
</span><ins>+ unsigned saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
</ins><span class="cx">
</span><ins>+ TagNameList tagNames;
+ const SelectorFragment* previousChildFragmentInDescendantBacktrackingChain = nullptr;
+
</ins><span class="cx"> for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
</span><span class="cx"> SelectorFragment& fragment = m_selectorFragments[i];
</span><span class="cx">
</span><span class="cx"> updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
</span><span class="cx">
</span><ins>+ computeBacktrackingHeightFromDescendant(fragment, tagNames, hasDescendantRelationOnTheRight, previousChildFragmentInDescendantBacktrackingChain);
+
+#if CSS_SELECTOR_JIT_DEBUGGING
+ dataLogF("Computing fragment[%d] backtracking height %u. NotMatched %u / Matched %u\n", i, fragment.heightFromDescendant, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
+#endif
+
</ins><span class="cx"> solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
</span><span class="cx">
</span><span class="cx"> needsAdjacentTail |= requiresAdjacentTail(fragment);
</span><span class="lines">@@ -672,8 +843,10 @@
</span><span class="cx"> fragment.backtrackingFlags |= BacktrackingFlag::DescendantEntryPoint;
</span><span class="cx"> if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
</span><span class="cx"> fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
</span><del>- if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation))
- fragment.backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
</del><ins>+ if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation)) {
+ ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
+ saveDescendantBacktrackingStartFragmentIndex = i;
+ }
</ins><span class="cx"> if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
</span><span class="cx"> fragment.backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
</span><span class="cx"> m_needsAdjacentBacktrackingStart = true;
</span><span class="lines">@@ -683,9 +856,16 @@
</span><span class="cx"> fragment.backtrackingFlags |= BacktrackingFlag::DirectAdjacentTail;
</span><span class="cx"> needsAdjacentTail = false;
</span><span class="cx"> }
</span><del>- if (fragment.relationToLeftFragment == FragmentRelation::Descendant && needsDescendantTail) {
- fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
- needsDescendantTail = false;
</del><ins>+ if (fragment.relationToLeftFragment == FragmentRelation::Descendant) {
+ if (needsDescendantTail) {
+ ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
+ fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
+ m_selectorFragments[saveDescendantBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
+ needsDescendantTail = false;
+ for (unsigned j = saveDescendantBacktrackingStartFragmentIndex; j <= i; ++j)
+ m_selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;
+ }
+ saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -714,7 +894,7 @@
</span><span class="cx"> const SelectorFragment& fragment = m_selectorFragments[i];
</span><span class="cx"> switch (fragment.relationToRightFragment) {
</span><span class="cx"> case FragmentRelation::Rightmost:
</span><del>- generateElementMatching(failureCases, fragment);
</del><ins>+ generateElementMatching(failureCases, failureCases, fragment);
</ins><span class="cx"> break;
</span><span class="cx"> case FragmentRelation::Descendant:
</span><span class="cx"> generateAncestorTreeWalker(failureCases, fragment);
</span><span class="lines">@@ -788,12 +968,17 @@
</span><span class="cx"> return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsElement()));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void SelectorCodeGenerator::generateWalkToParentNode(Assembler::RegisterID targetRegister)
+{
+ m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
+}
+
</ins><span class="cx"> void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
</span><span class="cx"> {
</span><span class="cx"> // ContainerNode* parent = parentNode()
</span><span class="cx"> // if (!parent || !parent->isElementNode())
</span><span class="cx"> // failure
</span><del>- m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
</del><ins>+ generateWalkToParentNode(targetRegister);
</ins><span class="cx"> failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
</span><span class="cx"> failureCases.append(testIsElementFlagOnNode(Assembler::Zero, m_assembler, targetRegister));
</span><span class="cx"> }
</span><span class="lines">@@ -804,9 +989,11 @@
</span><span class="cx"> generateWalkToParentElement(traversalFailureCases, elementAddressRegister);
</span><span class="cx"> linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
</span><span class="cx">
</span><del>- Assembler::JumpList matchingFailureCases;
- generateElementMatching(matchingFailureCases, fragment);
- linkFailures(failureCases, fragment.matchingBacktrackingAction, matchingFailureCases);
</del><ins>+ Assembler::JumpList matchingTagNameFailureCases;
+ Assembler::JumpList matchingPostTagNameFailureCases;
+ generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
+ linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
+ linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
</ins><span class="cx">
</span><span class="cx"> if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
</span><span class="cx"> m_descendantBacktrackingStart = m_registerAllocator.allocateRegister();
</span><span class="lines">@@ -827,9 +1014,9 @@
</span><span class="cx"> if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
</span><span class="cx"> m_descendantEntryPoint = m_assembler.label();
</span><span class="cx">
</span><del>- Assembler::JumpList tagMatchingLocalFailureCases;
- generateElementMatching(tagMatchingLocalFailureCases, fragment);
- tagMatchingLocalFailureCases.linkTo(loopStart, &m_assembler);
</del><ins>+ Assembler::JumpList matchingFailureCases;
+ generateElementMatching(matchingFailureCases, matchingFailureCases, fragment);
+ matchingFailureCases.linkTo(loopStart, &m_assembler);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline void SelectorCodeGenerator::generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
</span><span class="lines">@@ -884,9 +1071,11 @@
</span><span class="cx">
</span><span class="cx"> generateWalkToPreviousAdjacent(failureCases, fragment);
</span><span class="cx">
</span><del>- Assembler::JumpList matchingFailureCases;
- generateElementMatching(matchingFailureCases, fragment);
- linkFailures(failureCases, fragment.matchingBacktrackingAction, matchingFailureCases);
</del><ins>+ Assembler::JumpList matchingTagNameFailureCases;
+ Assembler::JumpList matchingPostTagNameFailureCases;
+ generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
+ linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
+ linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
</ins><span class="cx">
</span><span class="cx"> if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart) {
</span><span class="cx"> unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
</span><span class="lines">@@ -906,7 +1095,7 @@
</span><span class="cx"> m_indirectAdjacentEntryPoint = m_assembler.label();
</span><span class="cx">
</span><span class="cx"> Assembler::JumpList localFailureCases;
</span><del>- generateElementMatching(localFailureCases, fragment);
</del><ins>+ generateElementMatching(localFailureCases, localFailureCases, fragment);
</ins><span class="cx"> localFailureCases.linkTo(loopStart, &m_assembler);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -1161,33 +1350,33 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
</del><ins>+void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment& fragment)
</ins><span class="cx"> {
</span><ins>+ if (fragment.tagName)
+ generateElementHasTagName(matchingTagNameFailureCases, *(fragment.tagName));
+
</ins><span class="cx"> if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLink))
</span><del>- generateElementIsLink(failureCases);
</del><ins>+ generateElementIsLink(matchingPostTagNameFailureCases);
</ins><span class="cx">
</span><span class="cx"> if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassRoot))
</span><del>- generateElementIsRoot(failureCases);
</del><ins>+ generateElementIsRoot(matchingPostTagNameFailureCases);
</ins><span class="cx">
</span><span class="cx"> if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassTarget))
</span><del>- generateElementIsTarget(failureCases);
</del><ins>+ generateElementIsTarget(matchingPostTagNameFailureCases);
</ins><span class="cx">
</span><del>- if (fragment.tagName)
- generateElementHasTagName(failureCases, *(fragment.tagName));
-
</del><span class="cx"> for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
</span><del>- generateElementFunctionCallTest(failureCases, fragment.unoptimizedPseudoClasses[i]);
</del><ins>+ generateElementFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClasses[i]);
</ins><span class="cx">
</span><del>- generateElementDataMatching(failureCases, fragment);
</del><ins>+ generateElementDataMatching(matchingPostTagNameFailureCases, fragment);
</ins><span class="cx">
</span><span class="cx"> if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassOnlyChild))
</span><del>- generateElementIsOnlyChild(failureCases, fragment);
</del><ins>+ generateElementIsOnlyChild(matchingPostTagNameFailureCases, fragment);
</ins><span class="cx"> if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFirstChild))
</span><del>- generateElementIsFirstChild(failureCases, fragment);
</del><ins>+ generateElementIsFirstChild(matchingPostTagNameFailureCases, fragment);
</ins><span class="cx"> if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLastChild))
</span><del>- generateElementIsLastChild(failureCases, fragment);
</del><ins>+ generateElementIsLastChild(matchingPostTagNameFailureCases, fragment);
</ins><span class="cx"> if (!fragment.nthChildfilters.isEmpty())
</span><del>- generateElementIsNthChild(failureCases, fragment);
</del><ins>+ generateElementIsNthChild(matchingPostTagNameFailureCases, fragment);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
</span></span></pre>
</div>
</div>
</body>
</html>