<!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>[167218] 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/167218">167218</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2014-04-14 01:42:53 -0700 (Mon, 14 Apr 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>CSS JIT: compile the :nth-child() pseudo class
https://bugs.webkit.org/show_bug.cgi?id=131602
Reviewed by Andreas Kling.
Source/WebCore:
Tests: fast/selectors/nth-child-bounds.html
fast/selectors/nth-child-with-backtracking.html
Compile the :nth-child() pseudo class function + some related clean up.
* css/CSSSelector.cpp:
(WebCore::CSSSelector::nthA):
(WebCore::CSSSelector::nthB):
Expose the parsed value of an+b filters. Those values are used to compile
the selector.
(WebCore::CSSSelector::RareData::parseNth):
While working on the patch, I discovered some severe issues with the parsing of large
values of a and/or b. The problem comes from the way the CSS parser handle the values:
the values are parsed as a double then converted to an AtomicString for CSSSelector.
There are many problems related to large values but we never got bug reports because
they are very uncommon. Fixing those problem would require changing the parser.
Here, CSSSelector::RareData::parseNth() is hardened a little bit to avoid absurd values
of a and b.
* css/CSSSelector.h:
* cssjit/RegisterAllocator.h:
It looks like I forgot RDX in the list of register. Add it now since it is required
for SelectorCodeGenerator::modulo().
* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::addPseudoType):
(WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
(WebCore::SelectorCompiler::SelectorCodeGenerator::modulo):
(WebCore::SelectorCompiler::SelectorCodeGenerator::moduloIsZero):
There is no modulo() operation exposed on the macro assemblers. This is a basic
implementation on top of idiv for x86_64.
Since idiv works exclusively with RAX and RDX, most of the code is about getting
those registers efficiently.
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
(WebCore::SelectorCompiler::setElementChildIndex):
(WebCore::SelectorCompiler::setElementChildIndexAndUpdateStyle):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsNthChild):
This is pretty much a straightforward implementation of :nth-child().
The first part counts the number of previous elements.
The second part updates the tree if this is style resolution.
The last part compares the number of previous siblings to an+b to find if the filter matches.
The only part that diverges from SelectorChecker is how childIndex is used. Instead of testing it
at every iteration, only the first iteration handle the cache.
* dom/ElementRareData.h:
(WebCore::ElementRareData::childIndexMemoryOffset):
* dom/Node.h:
(WebCore::Node::rareDataMemoryOffset):
(WebCore::Node::flagHasRareData):
* rendering/style/RenderStyle.h:
LayoutTests:
Add a couple of test for the new code:
-nth-child-with-backtracking tests the register pressure with backtracking.
-nth-child-bounds tests invalid selectors do not cause problems.
* fast/selectors/nth-child-bounds-expected.txt: Added.
* fast/selectors/nth-child-bounds.html: Added.
* fast/selectors/nth-child-with-backtracking-expected.txt: Added.
* fast/selectors/nth-child-with-backtracking.html: Added.
* http/tests/security/video-poster-cross-origin-crash.html:
Now that CSSSelector filters out ridiculously bad values, the pseudo class in this test
was no longer executed.
The particular value of nth-child is irrelevant for this test, all it needs it the tree marking
while not matching.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkLayoutTestshttptestssecurityvideopostercrossorigincrashhtml">trunk/LayoutTests/http/tests/security/video-poster-cross-origin-crash.html</a></li>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecssCSSSelectorcpp">trunk/Source/WebCore/css/CSSSelector.cpp</a></li>
<li><a href="#trunkSourceWebCorecssCSSSelectorh">trunk/Source/WebCore/css/CSSSelector.h</a></li>
<li><a href="#trunkSourceWebCorecssjitRegisterAllocatorh">trunk/Source/WebCore/cssjit/RegisterAllocator.h</a></li>
<li><a href="#trunkSourceWebCorecssjitSelectorCompilercpp">trunk/Source/WebCore/cssjit/SelectorCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCoredomElementRareDatah">trunk/Source/WebCore/dom/ElementRareData.h</a></li>
<li><a href="#trunkSourceWebCoredomNodeh">trunk/Source/WebCore/dom/Node.h</a></li>
<li><a href="#trunkSourceWebCorerenderingstyleRenderStyleh">trunk/Source/WebCore/rendering/style/RenderStyle.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsfastselectorsnthchildboundsexpectedtxt">trunk/LayoutTests/fast/selectors/nth-child-bounds-expected.txt</a></li>
<li><a href="#trunkLayoutTestsfastselectorsnthchildboundshtml">trunk/LayoutTests/fast/selectors/nth-child-bounds.html</a></li>
<li><a href="#trunkLayoutTestsfastselectorsnthchildwithbacktrackingexpectedtxt">trunk/LayoutTests/fast/selectors/nth-child-with-backtracking-expected.txt</a></li>
<li><a href="#trunkLayoutTestsfastselectorsnthchildwithbacktrackinghtml">trunk/LayoutTests/fast/selectors/nth-child-with-backtracking.html</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/LayoutTests/ChangeLog 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -1,3 +1,25 @@
</span><ins>+2014-04-14 Benjamin Poulain <benjamin@webkit.org>
+
+ CSS JIT: compile the :nth-child() pseudo class
+ https://bugs.webkit.org/show_bug.cgi?id=131602
+
+ Reviewed by Andreas Kling.
+
+ Add a couple of test for the new code:
+ -nth-child-with-backtracking tests the register pressure with backtracking.
+ -nth-child-bounds tests invalid selectors do not cause problems.
+
+ * fast/selectors/nth-child-bounds-expected.txt: Added.
+ * fast/selectors/nth-child-bounds.html: Added.
+ * fast/selectors/nth-child-with-backtracking-expected.txt: Added.
+ * fast/selectors/nth-child-with-backtracking.html: Added.
+
+ * http/tests/security/video-poster-cross-origin-crash.html:
+ Now that CSSSelector filters out ridiculously bad values, the pseudo class in this test
+ was no longer executed.
+ The particular value of nth-child is irrelevant for this test, all it needs it the tree marking
+ while not matching.
+
</ins><span class="cx"> 2014-04-14 Mihnea Ovidenie <mihnea@adobe.com>
</span><span class="cx">
</span><span class="cx"> [CSS Regions] Hit testing doesn't work in video
</span></span></pre></div>
<a id="trunkLayoutTestsfastselectorsnthchildboundsexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/nth-child-bounds-expected.txt (0 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/nth-child-bounds-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/selectors/nth-child-bounds-expected.txt 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -0,0 +1,35 @@
</span><ins>+Test the boundary values of the :nth-child() selector.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS document.querySelectorAll("li:nth-child(0n+0)").length is 0
+PASS document.querySelectorAll("li:nth-child(-0n+0)").length is 0
+PASS document.querySelectorAll("li:nth-child(0n-0)").length is 0
+PASS document.querySelectorAll("li:nth-child(-0n-0)").length is 0
+PASS document.querySelectorAll("li:nth-child(-0n)").length is 0
+PASS document.querySelectorAll("li:nth-child(0)").length is 0
+PASS document.querySelectorAll("li:nth-child(-0)").length is 0
+PASS document.querySelectorAll("li:nth-child(-1)").length is 0
+PASS document.querySelectorAll("li:nth-child(2147483647n+2147483647)").length is 0
+PASS document.querySelectorAll("li:nth-child(2147483647n)").length is 0
+PASS document.querySelectorAll("li:nth-child(2147483647)").length is 0
+PASS document.querySelectorAll("li:nth-child(-2147483648n)").length is 0
+PASS document.querySelectorAll("li:nth-child(-2147483648)").length is 0
+PASS document.querySelectorAll("li:nth-child(2147483647n-2147483648)").length is 0
+PASS document.querySelectorAll("li:nth-child(-2147483648n+2147483647)").length is 0
+PASS document.querySelectorAll("li:nth-child(2147483648n+2147483648)").length is 0
+PASS document.querySelectorAll("li:nth-child(2147483648n)").length is 0
+PASS document.querySelectorAll("li:nth-child(2147483648)").length is 0
+PASS document.querySelectorAll("li:nth-child(3147483647n+3147483647)").length is 0
+PASS document.querySelectorAll("li:nth-child(3147483647n)").length is 0
+PASS document.querySelectorAll("li:nth-child(3147483647)").length is 0
+PASS document.querySelectorAll("li:nth-child(-2147483649n-2147483649)").length is 0
+PASS document.querySelectorAll("li:nth-child(-2147483649n)").length is 0
+PASS document.querySelectorAll("li:nth-child(-2147483649)").length is 0
+PASS allItems.length is 20
+PASS coloredCount is 0
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsfastselectorsnthchildboundshtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/nth-child-bounds.html (0 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/nth-child-bounds.html (rev 0)
+++ trunk/LayoutTests/fast/selectors/nth-child-bounds.html 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -0,0 +1,161 @@
</span><ins>+<!doctype html>
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+<style>
+/* The element count starts at 1, no count <= 1 can match anything */
+li:nth-child(0n+0) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-0n+0) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(0n-0) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-0n-0) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(0n) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-0n) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(0) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-0) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-1) {
+ background-color:rgb(1, 2, 3);
+}
+
+/* IntMax (2147483647) and IntMin (-2147483647). The tree is not big enough to match any of those. */
+li:nth-child(2147483647n+2147483647) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(2147483647n) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(2147483647) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-2147483648n-2147483648) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-2147483648n) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-2147483648) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(2147483647n-2147483648) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-2147483648n+2147483647) {
+ background-color:rgb(1, 2, 3);
+}
+
+/* Values too large/small for int32 */
+li:nth-child(2147483648n+2147483648) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(2147483648n) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(2147483648) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(3147483647n+3147483647) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(3147483647n) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(3147483647) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-2147483649n-2147483649) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-2147483649n) {
+ background-color:rgb(1, 2, 3);
+}
+li:nth-child(-2147483649) {
+ background-color:rgb(1, 2, 3);
+}
+
+</style>
+</head>
+<body>
+<div style="display:none">
+ <ul id=targetTree>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ <li></li>
+ </ul>
+</div>
+</body>
+<script>
+description('Test the boundary values of the :nth-child() selector.');
+
+shouldBe('document.querySelectorAll("li:nth-child(0n+0)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-0n+0)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(0n-0)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-0n-0)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-0n)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(0)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-0)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-1)").length', '0');
+
+shouldBe('document.querySelectorAll("li:nth-child(2147483647n+2147483647)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(2147483647n)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(2147483647)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-2147483648n)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-2147483648)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(2147483647n-2147483648)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-2147483648n+2147483647)").length', '0');
+
+shouldBe('document.querySelectorAll("li:nth-child(2147483648n+2147483648)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(2147483648n)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(2147483648)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(3147483647n+3147483647)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(3147483647n)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(3147483647)").length', '0');
+
+shouldBe('document.querySelectorAll("li:nth-child(-2147483649n-2147483649)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-2147483649n)").length', '0');
+shouldBe('document.querySelectorAll("li:nth-child(-2147483649)").length', '0');
+
+var allItems = document.querySelectorAll('li');
+var coloredCount = 0;
+for (var i = 0; i < allItems.length; ++i) {
+ if (getComputedStyle(allItems[i]).backgroundColor === 'rgb(1, 2, 3)')
+ coloredCount++;
+}
+
+shouldBe('allItems.length', '20');
+shouldBe('coloredCount', '0');
+
+</script>
+<script src="../../resources/js-test-post.js"></script>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestsfastselectorsnthchildwithbacktrackingexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/nth-child-with-backtracking-expected.txt (0 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/nth-child-with-backtracking-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/selectors/nth-child-with-backtracking-expected.txt 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -0,0 +1,15 @@
</span><ins>+Test nth-child inside deep backtracking.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS document.querySelectorAll("li+li+:nth-child(-5n+7)+li+li+li~li+li+li~li").length is 7
+PASS allItems.length is 20
+PASS coloredItems is 7
+PASS document.querySelectorAll("ul>[foo=bar]:nth-child(-3n+3)+li+li+li~li+li+li~li>span.first>span.second a").length is 11
+PASS allLinks.length is 20
+PASS backgroundColoredCount is 11
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsfastselectorsnthchildwithbacktrackinghtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/fast/selectors/nth-child-with-backtracking.html (0 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/fast/selectors/nth-child-with-backtracking.html (rev 0)
+++ trunk/LayoutTests/fast/selectors/nth-child-with-backtracking.html 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -0,0 +1,68 @@
</span><ins>+<!doctype html>
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+<style>
+li+li+:nth-child(-5n+7)+li+li+li~li+li+li~li {
+ color:rgb(4, 5, 6);
+}
+ul>[foo=bar]:nth-child(-3n+3)+li+li+li~li+li+li~li>span.first>span.second a {
+ background-color:rgb(1,2,3);
+}
+</style>
+</head>
+<body>
+<div>
+ <ul style="display:none">
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ <li foo=bar><span class="first"><span class="second"><span><a href="http://www.webkit.org">WebKit!</a></span></span></span></li>
+ </ul>
+</div>
+</body>
+<script>
+
+description('Test nth-child inside deep backtracking.');
+
+// Nth-child inside two adjacent backtracking chains.
+shouldBe('document.querySelectorAll("li+li+:nth-child(-5n+7)+li+li+li~li+li+li~li").length', '7');
+var allItems = document.querySelectorAll('li');
+shouldBe('allItems.length', '20');
+var coloredItems = 0;
+for (var i = 0; i < allItems.length; ++i) {
+ if (getComputedStyle(allItems[i]).color === 'rgb(4, 5, 6)')
+ coloredItems++;
+}
+shouldBe('coloredItems', '7');
+
+// Nth-child inside two adjacent backtracking chains, inside one descendant backtracking chain.
+shouldBe('document.querySelectorAll("ul>[foo=bar]:nth-child(-3n+3)+li+li+li~li+li+li~li>span.first>span.second a").length', '11');
+var allLinks = document.querySelectorAll('a');
+shouldBe('allLinks.length', '20');
+var backgroundColoredCount = 0;
+for (var i = 0; i < allLinks.length; ++i) {
+ if (getComputedStyle(allLinks[i]).backgroundColor === 'rgb(1, 2, 3)')
+ backgroundColoredCount++;
+}
+shouldBe('backgroundColoredCount', '11');
+
+</script>
+<script src="../../resources/js-test-post.js"></script>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestshttptestssecurityvideopostercrossorigincrashhtml"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/http/tests/security/video-poster-cross-origin-crash.html (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/http/tests/security/video-poster-cross-origin-crash.html 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/LayoutTests/http/tests/security/video-poster-cross-origin-crash.html 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> <sub id=tCF1></sub>>>><button hidden=false id=tCF7>><video crossorigin="" poster="http://localhost:8080/misc/resources/compass.jpg">><style>
</span><del>-.c29:nth-child(1814762996n + 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999) { -webkit-locale: "zh_CN";</style><script>
</del><ins>+.c29:nth-child(n + 2) { -webkit-locale: "zh_CN";</style><script>
</ins><span class="cx"> if (window.testRunner) {
</span><span class="cx"> testRunner.dumpAsText();
</span><span class="cx"> testRunner.waitUntilDone();
</span></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/ChangeLog 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -1,3 +1,67 @@
</span><ins>+2014-04-14 Benjamin Poulain <benjamin@webkit.org>
+
+ CSS JIT: compile the :nth-child() pseudo class
+ https://bugs.webkit.org/show_bug.cgi?id=131602
+
+ Reviewed by Andreas Kling.
+
+ Tests: fast/selectors/nth-child-bounds.html
+ fast/selectors/nth-child-with-backtracking.html
+
+ Compile the :nth-child() pseudo class function + some related clean up.
+
+ * css/CSSSelector.cpp:
+ (WebCore::CSSSelector::nthA):
+ (WebCore::CSSSelector::nthB):
+ Expose the parsed value of an+b filters. Those values are used to compile
+ the selector.
+
+ (WebCore::CSSSelector::RareData::parseNth):
+ While working on the patch, I discovered some severe issues with the parsing of large
+ values of a and/or b. The problem comes from the way the CSS parser handle the values:
+ the values are parsed as a double then converted to an AtomicString for CSSSelector.
+
+ There are many problems related to large values but we never got bug reports because
+ they are very uncommon. Fixing those problem would require changing the parser.
+
+ Here, CSSSelector::RareData::parseNth() is hardened a little bit to avoid absurd values
+ of a and b.
+
+ * css/CSSSelector.h:
+ * cssjit/RegisterAllocator.h:
+ It looks like I forgot RDX in the list of register. Add it now since it is required
+ for SelectorCodeGenerator::modulo().
+
+ * cssjit/SelectorCompiler.cpp:
+ (WebCore::SelectorCompiler::addPseudoType):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::modulo):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::moduloIsZero):
+ There is no modulo() operation exposed on the macro assemblers. This is a basic
+ implementation on top of idiv for x86_64.
+
+ Since idiv works exclusively with RAX and RDX, most of the code is about getting
+ those registers efficiently.
+
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
+ (WebCore::SelectorCompiler::setElementChildIndex):
+ (WebCore::SelectorCompiler::setElementChildIndexAndUpdateStyle):
+ (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsNthChild):
+ This is pretty much a straightforward implementation of :nth-child().
+ The first part counts the number of previous elements.
+ The second part updates the tree if this is style resolution.
+ The last part compares the number of previous siblings to an+b to find if the filter matches.
+
+ The only part that diverges from SelectorChecker is how childIndex is used. Instead of testing it
+ at every iteration, only the first iteration handle the cache.
+
+ * dom/ElementRareData.h:
+ (WebCore::ElementRareData::childIndexMemoryOffset):
+ * dom/Node.h:
+ (WebCore::Node::rareDataMemoryOffset):
+ (WebCore::Node::flagHasRareData):
+ * rendering/style/RenderStyle.h:
+
</ins><span class="cx"> 2014-04-14 Tim Horton <timothy_horton@apple.com>
</span><span class="cx">
</span><span class="cx"> Support setting a background color on page overlays
</span></span></pre></div>
<a id="trunkSourceWebCorecssCSSSelectorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/CSSSelector.cpp (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/css/CSSSelector.cpp 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/css/CSSSelector.cpp 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -581,6 +581,20 @@
</span><span class="cx"> return m_data.m_rareData->matchNth(count);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+int CSSSelector::nthA() const
+{
+ ASSERT(m_hasRareData);
+ ASSERT(m_parsedNth);
+ return m_data.m_rareData->m_a;
+}
+
+int CSSSelector::nthB() const
+{
+ ASSERT(m_hasRareData);
+ ASSERT(m_parsedNth);
+ return m_data.m_rareData->m_b;
+}
+
</ins><span class="cx"> CSSSelector::RareData::RareData(PassRefPtr<AtomicStringImpl> value)
</span><span class="cx"> : m_value(value.leakRef())
</span><span class="cx"> , m_a(0)
</span><span class="lines">@@ -618,23 +632,42 @@
</span><span class="cx"> if (argument[0] == '-') {
</span><span class="cx"> if (n == 1)
</span><span class="cx"> m_a = -1; // -n == -1n
</span><del>- else
- m_a = argument.substring(0, n).toInt();
</del><ins>+ else {
+ bool ok;
+ m_a = argument.substringSharingImpl(0, n).toIntStrict(&ok);
+ if (!ok)
+ return false;
+ }
</ins><span class="cx"> } else if (!n)
</span><span class="cx"> m_a = 1; // n == 1n
</span><del>- else
- m_a = argument.substring(0, n).toInt();
</del><ins>+ else {
+ bool ok;
+ m_a = argument.substringSharingImpl(0, n).toIntStrict(&ok);
+ if (!ok)
+ return false;
+ }
</ins><span class="cx">
</span><span class="cx"> size_t p = argument.find('+', n);
</span><del>- if (p != notFound)
- m_b = argument.substring(p + 1, argument.length() - p - 1).toInt();
- else {
</del><ins>+ if (p != notFound) {
+ bool ok;
+ m_b = argument.substringSharingImpl(p + 1, argument.length() - p - 1).toIntStrict(&ok);
+ if (!ok)
+ return false;
+ } else {
</ins><span class="cx"> p = argument.find('-', n);
</span><del>- if (p != notFound)
- m_b = -argument.substring(p + 1, argument.length() - p - 1).toInt();
</del><ins>+ if (p != notFound) {
+ bool ok;
+ m_b = -argument.substringSharingImpl(p + 1, argument.length() - p - 1).toIntStrict(&ok);
+ if (!ok)
+ return false;
+ }
</ins><span class="cx"> }
</span><del>- } else
- m_b = argument.toInt();
</del><ins>+ } else {
+ bool ok;
+ m_b = argument.toIntStrict(&ok);
+ if (!ok)
+ return false;
+ }
</ins><span class="cx"> }
</span><span class="cx"> return true;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecssCSSSelectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/CSSSelector.h (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/css/CSSSelector.h 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/css/CSSSelector.h 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -217,6 +217,8 @@
</span><span class="cx">
</span><span class="cx"> bool parseNth() const;
</span><span class="cx"> bool matchNth(int count) const;
</span><ins>+ int nthA() const;
+ int nthB() const;
</ins><span class="cx">
</span><span class="cx"> PseudoElementType pseudoElementType() const { ASSERT(m_match == PseudoElement); return static_cast<PseudoElementType>(m_pseudoType); }
</span><span class="cx"> PagePseudoClassType pagePseudoClassType() const { ASSERT(m_match == PagePseudoClass); return static_cast<PagePseudoClassType>(m_pseudoType); }
</span></span></pre></div>
<a id="trunkSourceWebCorecssjitRegisterAllocatorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/cssjit/RegisterAllocator.h (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/cssjit/RegisterAllocator.h 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/cssjit/RegisterAllocator.h 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -39,6 +39,7 @@
</span><span class="cx"> static const JSC::MacroAssembler::RegisterID callerSavedRegisters[] = {
</span><span class="cx"> JSC::X86Registers::eax,
</span><span class="cx"> JSC::X86Registers::ecx,
</span><ins>+ JSC::X86Registers::edx,
</ins><span class="cx"> JSC::X86Registers::esi,
</span><span class="cx"> JSC::X86Registers::edi,
</span><span class="cx"> JSC::X86Registers::r8,
</span></span></pre></div>
<a id="trunkSourceWebCorecssjitSelectorCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/cssjit/SelectorCompiler.cpp (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -31,6 +31,7 @@
</span><span class="cx"> #include "CSSSelector.h"
</span><span class="cx"> #include "Element.h"
</span><span class="cx"> #include "ElementData.h"
</span><ins>+#include "ElementRareData.h"
</ins><span class="cx"> #include "FunctionCall.h"
</span><span class="cx"> #include "HTMLDocument.h"
</span><span class="cx"> #include "HTMLNames.h"
</span><span class="lines">@@ -131,6 +132,7 @@
</span><span class="cx"> HashSet<unsigned> pseudoClasses;
</span><span class="cx"> Vector<JSC::FunctionPtr> unoptimizedPseudoClasses;
</span><span class="cx"> Vector<AttributeMatchingInfo> attributes;
</span><ins>+ Vector<std::pair<int, int>> nthChildfilters;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> typedef JSC::MacroAssembler Assembler;
</span><span class="lines">@@ -189,9 +191,12 @@
</span><span class="cx"> void generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch);
</span><span class="cx"> void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames);
</span><span class="cx"> void generateElementIsLink(Assembler::JumpList& failureCases);
</span><ins>+ void generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment&);
</ins><span class="cx">
</span><span class="cx"> // Helpers.
</span><span class="cx"> Assembler::Jump jumpIfNotResolvingStyle(Assembler::RegisterID checkingContextRegister);
</span><ins>+ Assembler::Jump modulo(JSC::MacroAssembler::ResultCondition, Assembler::RegisterID inputDividend, int divisor);
+ void moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor);
</ins><span class="cx">
</span><span class="cx"> Assembler m_assembler;
</span><span class="cx"> RegisterAllocator m_registerAllocator;
</span><span class="lines">@@ -251,80 +256,102 @@
</span><span class="cx"> return std::max(a, b);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-static inline FunctionType addPseudoType(CSSSelector::PseudoType type, SelectorFragment& pseudoClasses, SelectorContext selectorContext)
</del><ins>+static inline FunctionType addPseudoType(const CSSSelector& selector, SelectorFragment& fragment, SelectorContext selectorContext)
</ins><span class="cx"> {
</span><ins>+ CSSSelector::PseudoType type = selector.pseudoType();
</ins><span class="cx"> switch (type) {
</span><span class="cx"> // Unoptimized pseudo selector. They are just function call to a simple testing function.
</span><span class="cx"> case CSSSelector::PseudoAutofill:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoChecked:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoDefault:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoDisabled:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoEnabled:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoFocus:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoIndeterminate:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoInvalid:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoOptional:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoReadOnly:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoReadWrite:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoRequired:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoValid:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> #if ENABLE(FULLSCREEN_API)
</span><span class="cx"> case CSSSelector::PseudoFullScreen:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> #endif
</span><span class="cx"> #if ENABLE(VIDEO_TRACK)
</span><span class="cx"> case CSSSelector::PseudoFuture:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> case CSSSelector::PseudoPast:
</span><del>- pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
</del><ins>+ fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> // Optimized pseudo selectors.
</span><span class="cx"> case CSSSelector::PseudoAnyLink:
</span><del>- pseudoClasses.pseudoClasses.add(CSSSelector::PseudoLink);
</del><ins>+ fragment.pseudoClasses.add(CSSSelector::PseudoLink);
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx">
</span><span class="cx"> case CSSSelector::PseudoLink:
</span><del>- pseudoClasses.pseudoClasses.add(type);
</del><ins>+ fragment.pseudoClasses.add(type);
</ins><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx">
</span><span class="cx"> case CSSSelector::PseudoFirstChild:
</span><span class="cx"> case CSSSelector::PseudoLastChild:
</span><span class="cx"> case CSSSelector::PseudoOnlyChild:
</span><del>- pseudoClasses.pseudoClasses.add(type);
</del><ins>+ fragment.pseudoClasses.add(type);
</ins><span class="cx"> if (selectorContext == SelectorContext::QuerySelector)
</span><span class="cx"> return FunctionType::SimpleSelectorChecker;
</span><span class="cx"> return FunctionType::SelectorCheckerWithCheckingContext;
</span><span class="cx">
</span><ins>+ case CSSSelector::PseudoNthChild:
+ {
+ if (!selector.parseNth())
+ return FunctionType::CannotMatchAnything;
+
+ int a = selector.nthA();
+ int b = selector.nthB();
+
+ // The element count is always positive.
+ if (a <= 0 && b < 1)
+ return FunctionType::CannotMatchAnything;
+
+ // Anything modulo 1 is zero. Unless b restrict the range, this does not filter anything out.
+ if (a == 1 && (!b || (b == 1)))
+ return FunctionType::SimpleSelectorChecker;
+
+ fragment.nthChildfilters.append(std::pair<int, int>(a, b));
+ if (selectorContext == SelectorContext::QuerySelector)
+ return FunctionType::SimpleSelectorChecker;
+ return FunctionType::SelectorCheckerWithCheckingContext;
+ }
</ins><span class="cx"> default:
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="lines">@@ -367,7 +394,7 @@
</span><span class="cx"> fragment.classNames.append(selector->value().impl());
</span><span class="cx"> break;
</span><span class="cx"> case CSSSelector::PseudoClass:
</span><del>- m_functionType = mostRestrictiveFunctionType(m_functionType, addPseudoType(selector->pseudoType(), fragment, m_selectorContext));
</del><ins>+ m_functionType = mostRestrictiveFunctionType(m_functionType, addPseudoType(*selector, fragment, m_selectorContext));
</ins><span class="cx"> if (m_functionType == FunctionType::CannotCompile || m_functionType == FunctionType::CannotMatchAnything)
</span><span class="cx"> return;
</span><span class="cx"> break;
</span><span class="lines">@@ -897,6 +924,111 @@
</span><span class="cx"> return m_assembler.branch8(Assembler::NotEqual, Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, resolvingMode)), Assembler::TrustedImm32(SelectorChecker::ResolvingStyle));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+// The value in inputDividend is destroyed by the modulo operation.
+Assembler::Jump SelectorCodeGenerator::modulo(Assembler::ResultCondition condition, Assembler::RegisterID inputDividend, int divisor)
+{
+ RELEASE_ASSERT(divisor);
+#if CPU(X86_64)
+ // idiv takes RAX + an arbitrary register, and return RAX + RDX. Most of this code is about doing
+ // an efficient allocation of those registers. If a register is already in use and is not the inputDividend,
+ // we first try to copy it to a temporary register, it that is not possible we fall back to the stack.
+ enum class RegisterAllocationType {
+ External,
+ AllocatedLocally,
+ CopiedToTemporary,
+ PushedToStack
+ };
+
+ // 1) Get RAX and RDX.
+ // If they are already used, push them to the stack.
+ Assembler::RegisterID dividend = JSC::X86Registers::eax;
+ RegisterAllocationType dividendAllocation = RegisterAllocationType::External;
+ StackAllocator::StackReference temporaryDividendStackReference;
+ Assembler::RegisterID temporaryDividendCopy = InvalidGPRReg;
+ if (inputDividend != dividend) {
+ bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
+ if (registerIsInUse) {
+ if (m_registerAllocator.availableRegisterCount()) {
+ temporaryDividendCopy = m_registerAllocator.allocateRegister();
+ m_assembler.move(dividend, temporaryDividendCopy);
+ dividendAllocation = RegisterAllocationType::CopiedToTemporary;
+ } else {
+ temporaryDividendStackReference = m_stackAllocator.push(dividend);
+ dividendAllocation = RegisterAllocationType::PushedToStack;
+ }
+ } else {
+ m_registerAllocator.allocateRegister(dividend);
+ dividendAllocation = RegisterAllocationType::AllocatedLocally;
+ }
+ m_assembler.move(inputDividend, dividend);
+ }
+
+ Assembler::RegisterID remainder = JSC::X86Registers::edx;
+ RegisterAllocationType remainderAllocation = RegisterAllocationType::External;
+ StackAllocator::StackReference temporaryRemainderStackReference;
+ Assembler::RegisterID temporaryRemainderCopy = InvalidGPRReg;
+ if (inputDividend != remainder) {
+ bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
+ if (registerIsInUse) {
+ if (m_registerAllocator.availableRegisterCount()) {
+ temporaryRemainderCopy = m_registerAllocator.allocateRegister();
+ m_assembler.move(remainder, temporaryRemainderCopy);
+ remainderAllocation = RegisterAllocationType::CopiedToTemporary;
+ } else {
+ temporaryRemainderStackReference = m_stackAllocator.push(remainder);
+ remainderAllocation = RegisterAllocationType::PushedToStack;
+ }
+ } else {
+ m_registerAllocator.allocateRegister(remainder);
+ remainderAllocation = RegisterAllocationType::AllocatedLocally;
+ }
+ }
+ m_assembler.m_assembler.cdq();
+
+ // 2) Perform the division with idiv.
+ {
+ LocalRegister divisorRegister(m_registerAllocator);
+ m_assembler.move(Assembler::TrustedImm64(divisor), divisorRegister);
+ m_assembler.m_assembler.idivl_r(divisorRegister);
+ m_assembler.test32(remainder);
+ }
+
+ // 3) Return RAX and RDX.
+ if (remainderAllocation == RegisterAllocationType::AllocatedLocally)
+ m_registerAllocator.deallocateRegister(remainder);
+ else if (remainderAllocation == RegisterAllocationType::CopiedToTemporary) {
+ m_assembler.move(temporaryRemainderCopy, remainder);
+ m_registerAllocator.deallocateRegister(temporaryRemainderCopy);
+ } else if (remainderAllocation == RegisterAllocationType::PushedToStack)
+ m_stackAllocator.pop(temporaryRemainderStackReference, remainder);
+
+ if (dividendAllocation == RegisterAllocationType::AllocatedLocally)
+ m_registerAllocator.deallocateRegister(dividend);
+ else if (dividendAllocation == RegisterAllocationType::CopiedToTemporary) {
+ m_assembler.move(temporaryDividendCopy, dividend);
+ m_registerAllocator.deallocateRegister(temporaryDividendCopy);
+ } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
+ m_stackAllocator.pop(temporaryDividendStackReference, dividend);
+
+ // 4) Branch on the test.
+ return m_assembler.branch(condition);
+#else
+#error Modulo is not implemented for this architecture.
+#endif
+}
+
+void SelectorCodeGenerator::moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor)
+{
+ if (divisor == 1 || divisor == -1)
+ return;
+ if (divisor == 2 || divisor == -2) {
+ failureCases.append(m_assembler.branchTest32(Assembler::NonZero, inputDividend, Assembler::TrustedImm32(1)));
+ return;
+ }
+
+ failureCases.append(modulo(Assembler::NonZero, inputDividend, divisor));
+}
+
</ins><span class="cx"> static void setNodeFlag(Assembler& assembler, Assembler::RegisterID elementAddress, int32_t flag)
</span><span class="cx"> {
</span><span class="cx"> assembler.or32(Assembler::TrustedImm32(flag), Assembler::Address(elementAddress, Node::nodeFlagsMemoryOffset()));
</span><span class="lines">@@ -1042,6 +1174,8 @@
</span><span class="cx"> generateElementIsFirstChild(failureCases, fragment);
</span><span class="cx"> if (fragment.pseudoClasses.contains(CSSSelector::PseudoLastChild))
</span><span class="cx"> generateElementIsLastChild(failureCases, fragment);
</span><ins>+ if (!fragment.nthChildfilters.isEmpty())
+ generateElementIsNthChild(failureCases, fragment);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
</span><span class="lines">@@ -1777,6 +1911,124 @@
</span><span class="cx"> failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink())));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+static void setElementChildIndex(Element* element, int index)
+{
+ element->setChildIndex(index);
+}
+
+static void setElementChildIndexAndUpdateStyle(Element* element, int index)
+{
+ element->setChildIndex(index);
+ if (RenderStyle* childStyle = element->renderStyle())
+ childStyle->setUnique();
+}
+
+void SelectorCodeGenerator::generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
+{
+ Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
+ generateWalkToParentElement(failureCases, parentElement);
+
+ // Setup the counter at 1.
+ LocalRegister elementCounter(m_registerAllocator);
+ m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
+
+ // Loop over the previous adjacent elements and increment the counter.
+ {
+ LocalRegister previousSibling(m_registerAllocator);
+ m_assembler.move(elementAddressRegister, previousSibling);
+
+ // Getting the child index is very efficient when it works. When there is no child index,
+ // querying at every iteration is very inefficient. We solve this by only testing the child
+ // index on the first direct adjacent.
+ Assembler::JumpList noMoreSiblingsCases;
+
+ Assembler::JumpList noCachedChildIndexCases;
+ generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
+ noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(previousSibling, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagHasRareData())));
+ {
+ LocalRegister elementRareData(m_registerAllocator);
+ m_assembler.loadPtr(Assembler::Address(previousSibling, Node::rareDataMemoryOffset()), elementRareData);
+ LocalRegister cachedChildIndex(m_registerAllocator);
+ m_assembler.load16(Assembler::Address(elementRareData, ElementRareData::childIndexMemoryOffset()), cachedChildIndex);
+ noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, cachedChildIndex));
+ m_assembler.add32(cachedChildIndex, elementCounter);
+ noMoreSiblingsCases.append(m_assembler.jump());
+ }
+ noCachedChildIndexCases.link(&m_assembler);
+ m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
+
+ Assembler::Label loopStart = m_assembler.label();
+ generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
+ m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
+ m_assembler.jump().linkTo(loopStart, &m_assembler);
+ noMoreSiblingsCases.link(&m_assembler);
+ }
+
+ // Tree marking when doing style resolution.
+ if (m_selectorContext != SelectorContext::QuerySelector) {
+ LocalRegister checkingContext(m_registerAllocator);
+ Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
+
+ m_registerAllocator.deallocateRegister(parentElement);
+ FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
+ functionCall.setFunctionAddress(Element::setChildrenAffectedByForwardPositionalRules);
+ functionCall.setOneArgument(parentElement);
+ functionCall.call();
+
+ if (fragment.relationToRightFragment == FragmentRelation::Rightmost) {
+ LocalRegister childStyle(m_registerAllocator);
+ m_assembler.loadPtr(Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, elementStyle)), childStyle);
+
+ LocalRegister flags(m_registerAllocator);
+ Assembler::Address flagAddress(childStyle, RenderStyle::noninheritedFlagsMemoryOffset() + RenderStyle::NonInheritedFlags::flagsMemoryOffset());
+ m_assembler.load64(flagAddress, flags);
+ LocalRegister isUniqueFlagImmediate(m_registerAllocator);
+ m_assembler.move(Assembler::TrustedImm64(RenderStyle::NonInheritedFlags::flagIsUnique()), isUniqueFlagImmediate);
+ m_assembler.or64(isUniqueFlagImmediate, flags);
+ m_assembler.store64(flags, flagAddress);
+
+ Assembler::RegisterID elementAddress = elementAddressRegister;
+ FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
+ functionCall.setFunctionAddress(setElementChildIndex);
+ functionCall.setTwoArguments(elementAddress, elementCounter);
+ functionCall.call();
+ } else {
+ Assembler::RegisterID elementAddress = elementAddressRegister;
+ FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
+ functionCall.setFunctionAddress(setElementChildIndexAndUpdateStyle);
+ functionCall.setTwoArguments(elementAddress, elementCounter);
+ functionCall.call();
+ }
+
+ notResolvingStyle.link(&m_assembler);
+ }
+
+ // Test every the nth-child filter.
+ for (const auto& slot : fragment.nthChildfilters) {
+ int a = slot.first;
+ int b = slot.second;
+
+ if (!a)
+ failureCases.append(m_assembler.branch32(Assembler::NotEqual, Assembler::TrustedImm32(b), elementCounter));
+ else if (a > 0) {
+ if (a == 2 && b == 1) {
+ // This is the common case 2n+1 (or "odd"), we can test for odd values without doing the arithmetic.
+ failureCases.append(m_assembler.branchTest32(Assembler::Zero, elementCounter, Assembler::TrustedImm32(1)));
+ } else {
+ if (b)
+ failureCases.append(m_assembler.branchSub32(Assembler::Signed, Assembler::TrustedImm32(b), elementCounter));
+ moduloIsZero(failureCases, elementCounter, a);
+ }
+ } else {
+ LocalRegister bRegister(m_registerAllocator);
+ m_assembler.move(Assembler::TrustedImm32(b), bRegister);
+
+ failureCases.append(m_assembler.branchSub32(Assembler::Signed, elementCounter, bRegister));
+ moduloIsZero(failureCases, bRegister, a);
+ }
+ }
+}
+
</ins><span class="cx"> }; // namespace SelectorCompiler.
</span><span class="cx"> }; // namespace WebCore.
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCoredomElementRareDatah"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/dom/ElementRareData.h (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/dom/ElementRareData.h 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/dom/ElementRareData.h 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -82,8 +82,10 @@
</span><span class="cx"> void setChildrenAffectedByForwardPositionalRules(bool value) { m_childrenAffectedByForwardPositionalRules = value; }
</span><span class="cx"> bool childrenAffectedByBackwardPositionalRules() const { return m_childrenAffectedByBackwardPositionalRules; }
</span><span class="cx"> void setChildrenAffectedByBackwardPositionalRules(bool value) { m_childrenAffectedByBackwardPositionalRules = value; }
</span><ins>+
</ins><span class="cx"> unsigned childIndex() const { return m_childIndex; }
</span><span class="cx"> void setChildIndex(unsigned index) { m_childIndex = index; }
</span><ins>+ static ptrdiff_t childIndexMemoryOffset() { return OBJECT_OFFSETOF(ElementRareData, m_childIndex); }
</ins><span class="cx">
</span><span class="cx"> void clearShadowRoot() { m_shadowRoot = nullptr; }
</span><span class="cx"> ShadowRoot* shadowRoot() const { return m_shadowRoot.get(); }
</span></span></pre></div>
<a id="trunkSourceWebCoredomNodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/dom/Node.h (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/dom/Node.h 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/dom/Node.h 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -571,9 +571,11 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CSS_SELECTOR_JIT)
</span><span class="cx"> static ptrdiff_t nodeFlagsMemoryOffset() { return OBJECT_OFFSETOF(Node, m_nodeFlags); }
</span><ins>+ static ptrdiff_t rareDataMemoryOffset() { return OBJECT_OFFSETOF(Node, m_data.m_rareData); }
</ins><span class="cx"> static int32_t flagIsElement() { return IsElementFlag; }
</span><span class="cx"> static int32_t flagIsHTML() { return IsHTMLFlag; }
</span><span class="cx"> static int32_t flagIsLink() { return IsLinkFlag; }
</span><ins>+ static int32_t flagHasRareData() { return HasRareDataFlag; }
</ins><span class="cx"> static int32_t flagIsParsingChildrenFinished() { return IsParsingChildrenFinishedFlag; }
</span><span class="cx"> static int32_t flagChildrenAffectedByFirstChildRulesFlag() { return ChildrenAffectedByFirstChildRulesFlag; }
</span><span class="cx"> static int32_t flagChildrenAffectedByLastChildRulesFlag() { return ChildrenAffectedByLastChildRulesFlag; }
</span></span></pre></div>
<a id="trunkSourceWebCorerenderingstyleRenderStyleh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/rendering/style/RenderStyle.h (167217 => 167218)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/rendering/style/RenderStyle.h 2014-04-14 08:29:35 UTC (rev 167217)
+++ trunk/Source/WebCore/rendering/style/RenderStyle.h 2014-04-14 08:42:53 UTC (rev 167218)
</span><span class="lines">@@ -278,6 +278,7 @@
</span><span class="cx"> static ETableLayout initialTableLayout() { return TAUTO; }
</span><span class="cx">
</span><span class="cx"> static ptrdiff_t flagsMemoryOffset() { return OBJECT_OFFSETOF(NonInheritedFlags, m_flags); }
</span><ins>+ static uint64_t flagIsUnique() { return oneBitMask << isUniqueOffset; }
</ins><span class="cx"> static uint64_t setFirstChildStateFlags() { return flagFirstChildState() | flagIsUnique(); }
</span><span class="cx"> static uint64_t setLastChildStateFlags() { return flagLastChildState() | flagIsUnique(); }
</span><span class="cx"> private:
</span><span class="lines">@@ -306,7 +307,6 @@
</span><span class="cx"> return static_cast<unsigned>((m_flags >> offset) & positionIndependentMask);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- static uint64_t flagIsUnique() { return oneBitMask << isUniqueOffset; }
</del><span class="cx"> static uint64_t flagFirstChildState() { return oneBitMask << firstChildStateOffset; }
</span><span class="cx"> static uint64_t flagLastChildState() { return oneBitMask << lastChildStateOffset; }
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>