Bug 6248 - CSS3: implement nth-* selectors (Acid3 bug)
Summary: CSS3: implement nth-* selectors (Acid3 bug)
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 420+
Hardware: Mac OS X 10.4
: P2 Normal
Assignee: Dave Hyatt
URL: http://www.w3.org/TR/css3-selectors/#...
Keywords: HasReduction
: 10337 (view as bug list)
Depends on:
Blocks: Acid3 11390
  Show dependency treegraph
Reported: 2005-12-27 00:28 PST by Joost de Valk (AlthA)
Modified: 2008-02-07 12:16 PST (History)
12 users (show)

See Also:

CSS3 nth-element testcase (1.78 KB, text/html)
2005-12-27 01:34 PST, Joost de Valk (AlthA)
no flags Details
Rudimentary nth-child patches (889.85 KB, application/gzip)
2006-06-04 13:17 PDT, Nicholas Shanks
no flags Details
Updated patch (only supports odd and even) (7.20 KB, patch)
2006-07-01 14:49 PDT, Nicholas Shanks
no flags Details | Formatted Diff | Diff
patch for dacarson (9.97 KB, patch)
2006-07-02 12:44 PDT, Nicholas Shanks
no flags Details | Formatted Diff | Diff
png expected from test case (40.34 KB, image/png)
2006-07-02 13:07 PDT, David Carson
no flags Details
Patch with test results (68.06 KB, patch)
2006-07-02 13:16 PDT, David Carson
no flags Details | Formatted Diff | Diff
Patch for nth-child and nth-of-type (70.07 KB, patch)
2006-07-02 13:34 PDT, Nicholas Shanks
mjs: review-
Details | Formatted Diff | Diff
Patch (7.93 KB, patch)
2006-12-29 12:13 PST, Allan Sandfeld Jensen
mjs: review-
Details | Formatted Diff | Diff
Cleaned up patch (8.55 KB, patch)
2007-10-14 06:50 PDT, Andrew Wellington
eric: review-
Details | Formatted Diff | Diff
Yet another version (18.20 KB, patch)
2008-01-07 19:31 PST, Andrew Wellington
no flags Details | Formatted Diff | Diff
The patch continues (19.95 KB, patch)
2008-01-09 02:17 PST, Andrew Wellington
no flags Details | Formatted Diff | Diff
The patch strikes back (18.50 KB, patch)
2008-01-14 00:47 PST, Andrew Wellington
hyatt: review-
Details | Formatted Diff | Diff
Latest patch (23.09 KB, patch)
2008-02-06 13:54 PST, Dave Hyatt
eric: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Joost de Valk (AlthA) 2005-12-27 00:28:20 PST
This would allow for the nth tr-element of a table to be alternated in layout, allowing for odd and even as 
well. I will produce a testcase and attach it in a few minutes.
Comment 1 Joost de Valk (AlthA) 2005-12-27 01:34:31 PST
Created attachment 5296 [details]
CSS3 nth-element testcase
Comment 2 Eric Seidel (no email) 2005-12-27 01:56:28 PST
Investigating a bit for fun.  Looks like we'll have to augment parser.y to be able to understand the an+b 
syntax inside the functions nth-child, nth-child-of-type, etc.
Comment 3 Maks Orlovich 2005-12-27 12:29:51 PST
FYI, supported in KHTML (test mostly passes, except for the last <p> thing). I 
believe there were some other reports open about merging in of CSS3 selector 
support to your tree 
Comment 4 Nicholas Shanks 2006-06-04 07:20:52 PDT
I did a patch for this merging from the khtml tree 12 months ago but hyatt rejected their solution for :last-child which was very similar to this (added bytes to footprint), so I stopped working on it. I will see what the khtml tree does now and see if it's been improved. It would be nice if carewolf could give his thoughts.

I have three versions of patches if anyone wants to see them.
Comment 5 David Kilzer (:ddkilzer) 2006-06-04 07:34:05 PDT
(In reply to comment #4)
> I have three versions of patches if anyone wants to see them.

Post them for review! :)
Comment 6 Nicholas Shanks 2006-06-04 13:17:58 PDT
Created attachment 8700 [details]
Rudimentary nth-child patches

These are from my KDE merge of about 12 months ago.
Comment 7 Nicholas Shanks 2006-07-01 14:49:47 PDT
Created attachment 9127 [details]
Updated patch (only supports odd and even)

This patch doesn't have layout tests yet, and only does "odd" and "even" as I've not looked up how to convert the QString methods KHTML used for an+b yet. Posting here so that people who have a faster computer can compile it and tell me if it works. :-)
Comment 8 Nicholas Shanks 2006-07-02 01:11:08 PDT
Note: I updated to ToT, applied the changes and let it build overnight. The following KHTML-isms needs to be amended before applying the patch:

DOMString -> AtomicString
DOM::NodeImpl -> Node
Comment 9 Nicholas Shanks 2006-07-02 12:44:05 PDT
Created attachment 9149 [details]
patch for dacarson

this patch is just missing the test results
Comment 10 David Carson 2006-07-02 13:07:48 PDT
Created attachment 9150 [details]
png expected from test case
Comment 11 David Carson 2006-07-02 13:16:27 PDT
Created attachment 9152 [details]
Patch with test results

Applied the patch and added test results for nickshanks
Comment 12 Nicholas Shanks 2006-07-02 13:34:10 PDT
Created attachment 9153 [details]
Patch for nth-child and nth-of-type

Does not attempt to support (an+b) yet, nor have functional implementations of nth-last-* as we are awaiting a decision from hyatt on how to implement :last-child and related pseudo classes.

an+b support will come in another patch to be posted to this bug later in the week.
Comment 13 Maciej Stachowiak 2006-07-04 00:25:18 PDT
1) matchNth does string compares - seems like it would be better to parse the various nth selectors into a/b values up front, and then pass those to a match function.

2) matchNth only appears to support "odd" and "even". Not sure if it is worth landing such partial support for the various nth selectors. The reason it won't match anything for other cases is also pretty subtle - depends on b starting at 0 and the count being 1-based.

3) For statements like this there should be a space after the comma:
+                    if (matchNth(count,sel->argument))

4) For statements like this, count++ should be on a separate line in WebKit coding style:
+                        if (n->isElementNode()) count++;

5) There's no support at all for dynamic updating. I think it is important that for fancy new selectors, we handle dynamic updates properly. After all it would be pretty sad if reordering a table (e.g. via some kind of column sorting) messed up an alternating row pattern. Worse yet, nth-last-child and nth-last-of-type will give wrong results while in the middle of parsing, so the lack of dynamic updates could leave a broken style when the document is done loading.

6) The way the counting works here will result in N^2 if a single element has N children that could be affected by nth-* style. Seems pretty bad to me. I think it is possible to address this without trading off excessive amounts of space by simply keeping a cache on the side in the form of hashtables for nodes that could be parents of elements where nth-* selectors apply. It would be tricky to keep this up to date but you could at least track the current number of element children for the common case of appending while parsing.

Given these issues, I think the patch is too incomplete to land as-is, but it's a nice start.
Comment 14 Mark Rowe (bdash) 2006-08-11 14:46:45 PDT
*** Bug 10337 has been marked as a duplicate of this bug. ***
Comment 15 Allan Sandfeld Jensen 2006-12-29 10:22:50 PST
The most common selector ' ' also has n^2 worst case running time in WebKit. And all selectors in WebKit suffers from lack of dynamic support. (last-child, doesn't even work in the static case)

I have a patch in KHTML to implement dynamic correctness of selectors, but it is a much different task than implementing the selector itself. So I don't think that is a very good reason to stall this patch.

Parsing the nth-string once only is certainly an option, but it might make selectors use more memory in general.
Comment 16 Allan Sandfeld Jensen 2006-12-29 12:13:44 PST
Created attachment 12111 [details]

Updated patch with actually working nth-checking.

Removed nth-last-* because they are unpredictable until dynamic updating has improved.
Comment 17 Maciej Stachowiak 2007-01-28 14:34:11 PST
Sorry about the delay in reviewing this again. Here's my comments:

a) Looks like you addressed my previous comments 1 and 2. Thanks!

b) There are still some coding style guideline violations:
+                        if (n->isElementNode()) count++;
+                        if (n->isElementNode() && static_cast<Element*>(n)->tagName() == type) count++;

count++ should be on a separate line. Please fix these.

c) I think it is ok to address the N^2 scaling and dynamic update issues, since those are pretty non-obvious to get right.

r- for now for the coding style issues but I will r+ this if those are fixed.
Comment 18 Andrew Wellington 2007-10-14 06:50:26 PDT
Created attachment 16665 [details]
Cleaned up patch

A cleaned up version of the old patch that applies against r26593
Comment 19 Eric Seidel (no email) 2008-01-01 22:14:25 PST
Test 38 in Acid3 is hitting this bug (lack of :nth-child support)
Comment 20 Maciej Stachowiak 2008-01-04 23:51:59 PST
Acid3 also tests for this selector properly updating in response to dynamic changes, which this patch does not handle.
Comment 21 Eric Seidel (no email) 2008-01-06 20:49:31 PST
Comment on attachment 16665 [details]
Cleaned up patch

The change in general looks fine.  The patch needs a style refresh and changelog.

             WebCore::Document *doc = p->document();
             if (doc)

should probably just be if (p->document())

+        } else {
+            b = nth.toInt();
+        }

No else after return:
+        else
+            return (b - count) % (-a) == 0;

+static bool matchNth(int count, int a, int b)
actually has a bunch of style issues (a == 0), several else blocks after returns.  no need for if (a < 0), etc.

I've changed my mind.  I think it's OK to get this basic functionality landed, and file a second bug to track making it dynamic.

r- for the style issues.
Comment 22 Andrew Wellington 2008-01-07 19:31:33 PST
Created attachment 18324 [details]
Yet another version
Comment 23 Nicholas Shanks 2008-01-08 04:28:29 PST
minor niggle. the AtomicString statics in CSSSelector.cpp are not in alphabetical order
Comment 24 Eric Seidel (no email) 2008-01-09 01:33:19 PST
Returning this to "unassigned".  Others are working on this bug now.
Comment 25 Andrew Wellington 2008-01-09 02:17:58 PST
Created attachment 18347 [details]
The patch continues

Updated patch based on comments from Eric on IRC
Comment 26 Darin Adler 2008-01-11 18:43:04 PST
Comment on attachment 18347 [details]
The patch continues

There's a double ChangeLog in this patch.

+// a helper function for checking nth-arguments
+static bool matchNth(int count, int a, int b)
+    if (!a)
+        return count == b;
+    else if (a > 0) {
+        if (count < b)
+            return false;
+        return (count - b) % a == 0;
+    } else {
+        if (count > b)
+            return false;
+        return (b - count) % (-a) == 0;
+    }

We normally don't do else after return.

+                    Node* n = e->previousSibling();
+                    while (n) {
+                        if (n->isElementNode())
+                            count++;
+                        n = n->previousSibling();
+                    }

This would be easier to read as a for loop.

+                    Node* n = e->previousSibling();
+                    while (n) {
+                        if (n->isElementNode() && static_cast<Element*>(n)->tagName() == type)
+                            count++;
+                        n = n->previousSibling();
+                    }

And this too.

But why is it good to have a static-only version of these? Can't we implement the real thing?
Comment 27 Andrew Wellington 2008-01-14 00:47:56 PST
Created attachment 18432 [details]
The patch strikes back

A few more changes Eric suggested on IRC
Comment 28 Dave Hyatt 2008-02-02 11:54:35 PST
I'm going to take this over once I finish only-child/only-of-type.

Comment 29 Dave Hyatt 2008-02-02 12:09:50 PST
Comment on attachment 18432 [details]
The patch strikes back

As loathe as I am to increase memory footprint, I think we should cache indices in RenderStyles.  If we don't, nth-child is O(n^2) just to match a single child list.
Comment 30 mitz 2008-02-02 12:32:02 PST
In most cases where style is resolved you are in the process of iterating over children anyway so maybe you can just keep the indices (and the language) on the stack.
Comment 31 Dave Hyatt 2008-02-02 14:40:03 PST

Comment 32 Dave Hyatt 2008-02-06 13:54:12 PST
Created attachment 18969 [details]
Latest patch

I have made the following changes from the previous patch:

(1) Use setChildrenAffectedByPositionalRules so that all the selectors work dynamically when the DOM changes.
(2) Annotated the selectors that are slow with FIXMEs.
(3) Fixed a bug in parseNth that caused the b values to be incorrect in some cases (e.g., n+2).
(4) Added support for nth-last-child and nth-last-of-type.
(5) Cache m_childIndex in RenderStyles to make nth-child fast.

My goal here is to really make the common selectors (first-child, empty, only-child, last-child, nth-child) fast.  The -of-type selectors and the nth-last-child selector remain very slow, but they won't be used in practice I expect.
Comment 34 Eric Seidel (no email) 2008-02-06 16:54:35 PST
Comment on attachment 18969 [details]
Latest patch

if (n->isElementNode() && static_cast<Element*>(n)->tagName() == type)
can just be:
(in a couple places)

matchNth should use the return-early style that we use throughout the rest of WebKit:
static bool matchNth(int count, int a, int b)
    if (!a)
        return count == b;
    if (a > 0) {
        if (count < b)
            return false;
        return (count - b) % a == 0;
    if (count > b)
        return false;
    return (b - count) % (-a) == 0;

Overall this looks fine.
Comment 35 Dave Hyatt 2008-02-07 12:16:21 PST
Fixed in r30069.