Bug 6248

Created attachment 5296 [details] CSS3 nth-element testcase

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.

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

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.

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

Created attachment 8700 [details] Rudimentary nth-child patches These are from my KDE merge of about 12 months ago.

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

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

Created attachment 9149 [details] patch for dacarson this patch is just missing the test results

Created attachment 9150 [details] png expected from test case

Created attachment 9152 [details] Patch with test results Applied the patch and added test results for nickshanks

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.

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.

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

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.

Created attachment 12111 [details] Patch Updated patch with actually working nth-checking. Removed nth-last-* because they are unpredictable until dynamic updating has improved.

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.

Created attachment 16665 [details] Cleaned up patch A cleaned up version of the old patch that applies against r26593

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

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

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.

Created attachment 18324 [details] Yet another version

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

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

Created attachment 18347 [details] The patch continues Updated patch based on comments from Eric on IRC

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?

Created attachment 18432 [details] The patch strikes back A few more changes Eric suggested on IRC

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

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.

Yeah.

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.

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

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.

Fixed in r30069.