Bug 6248 – CSS3: implement nth-* selectors (Acid3 bug)

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Joost de Valk (AlthA)]

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.

[Joost de Valk (AlthA)]

Created attachment 5296 [details]
CSS3 nth-element testcase

[Eric Seidel (no email)]

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.

[Maks Orlovich]

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 

[Nicholas Shanks]

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.

[David Kilzer (:ddkilzer)]

(In reply to comment #4)
> I have three versions of patches if anyone wants to see them.

Post them for review! :)

[Nicholas Shanks]

Created attachment 8700 [details]
Rudimentary nth-child patches

These are from my KDE merge of about 12 months ago.

[Nicholas Shanks]

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. :-)

[Nicholas Shanks]

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

[Nicholas Shanks]

Created attachment 9149 [details]
patch for dacarson

this patch is just missing the test results

[David Carson]

Created attachment 9150 [details]
png expected from test case

[David Carson]

Created attachment 9152 [details]
Patch with test results

Applied the patch and added test results for nickshanks

[Nicholas Shanks]

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.

[Maciej Stachowiak]

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.

[Mark Rowe (bdash)]

*** Bug 10337 has been marked as a duplicate of this bug. ***

[Allan Sandfeld Jensen]

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.

[Allan Sandfeld Jensen]

Created attachment 12111 [details]
Patch

Updated patch with actually working nth-checking.

Removed nth-last-* because they are unpredictable until dynamic updating has improved.

[Maciej Stachowiak]

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.

[Andrew Wellington]

Created attachment 16665 [details]
Cleaned up patch

A cleaned up version of the old patch that applies against r26593

[Eric Seidel (no email)]

Test 38 in Acid3 is hitting this bug (lack of :nth-child support)

[Maciej Stachowiak]

Acid3 also tests for this selector properly updating in response to dynamic changes, which this patch does not handle.

[Eric Seidel (no email)]

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)
                doc->setUsesSiblingRules(true);

should probably just be if (p->document())
  p->document()->setUsesSiblingRules(true);

Style:
+        } 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.

[Andrew Wellington]

Created attachment 18324 [details]
Yet another version

[Nicholas Shanks]

minor niggle. the AtomicString statics in CSSSelector.cpp are not in alphabetical order

[Eric Seidel (no email)]

Returning this to "unassigned".  Others are working on this bug now.

[Andrew Wellington]

Created attachment 18347 [details]
The patch continues

Updated patch based on comments from Eric on IRC

[Darin Adler]

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?

[Andrew Wellington]

Created attachment 18432 [details]
The patch strikes back

A few more changes Eric suggested on IRC

[Dave Hyatt]

I'm going to take this over once I finish only-child/only-of-type.

[Dave Hyatt]

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.

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.

[Dave Hyatt]

Yeah.

[Dave Hyatt]

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.

[Robert Blaut]

I suggest to include also these tests as layout tests:
http://www.css3.info/selectors-test/test-nthchild.html
http://www.css3.info/selectors-test/test-nthlastchild.html
http://www.css3.info/selectors-test/test-nthtype.html
http://www.css3.info/selectors-test/test-nthlasttype.html

[Eric Seidel (no email)]

Comment on attachment 18969 [details]
Latest patch

if (n->isElementNode() && static_cast<Element*>(n)->tagName() == type)
can just be:
n->hasTagName(type)
(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.

[Dave Hyatt]

Fixed in r30069.