Bug 3428 - CSS2/3: Descendant and indirect adjacent selectors don't backtrack properly
Summary: CSS2/3: Descendant and indirect adjacent selectors don't backtrack properly
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 412
Hardware: Mac OS X 10.4
: P2 Normal
Assignee: Dave Hyatt
Depends on:
Reported: 2005-06-10 22:49 PDT by Dave Hyatt
Modified: 2007-10-11 18:27 PDT (History)
6 users (show)

See Also:

Test showing the problem (works in Firefox) (367 bytes, text/html)
2005-06-10 22:56 PDT, Dave Hyatt
no flags Details
Another test case (works with firefox / opera PC) (279 bytes, text/html)
2005-09-27 01:26 PDT, Evgeni Popov
no flags Details
Quick patch (10.16 KB, patch)
2007-08-13 05:56 PDT, Allan Sandfeld Jensen
no flags Details | Formatted Diff | Diff
Patch (17.16 KB, patch)
2007-08-15 07:54 PDT, Allan Sandfeld Jensen
allan.jensen: review-
Details | Formatted Diff | Diff
New patch (15.90 KB, patch)
2007-08-16 06:00 PDT, Allan Sandfeld Jensen
mjs: review+
Details | Formatted Diff | Diff
Updated patch (17.17 KB, patch)
2007-09-17 06:04 PDT, Allan Sandfeld Jensen
eric: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Dave Hyatt 2005-06-10 22:49:40 PDT
Both the descendant and indirect adjacent selectors do not backtrack properly.  It's possible for the 
element on the left to match the selector but then to fail the match later on as you continue to move to 
the left looking at other selectors.  When this happens WebKit just fails to match the rule, but instead you 
need to backtrack and keep trying more elements.

Should be fixable by splitting out the code to match these selectors into functions and getting some 
recursion in there. :)

We will need to test performance once the change is made, since making the descendant selector behave 
properly could have a negative performance impact.
Comment 1 Dave Hyatt 2005-06-10 22:56:39 PDT
Created attachment 2243 [details]
Test showing the problem (works in Firefox)
Comment 2 Evgeni Popov 2005-09-27 01:26:41 PDT
Created attachment 4059 [details]
Another test case (works with firefox / opera PC)
Comment 3 Allan Sandfeld Jensen 2005-11-27 05:53:58 PST
The same bug is tracked in KDE as http://bugs.kde.org/show_bug.cgi?id=101115 
Comment 4 Allan Sandfeld Jensen 2007-08-13 05:56:39 PDT
Created attachment 15952 [details]
Quick patch

Here is a quick patch that fixes this bug isolated. 

The patch is not ready for review yet, but I will submit it later as part of a larger patch that fixes several serious issues in WebKit's CSS Selector implementation.
Comment 5 Allan Sandfeld Jensen 2007-08-15 07:54:24 PDT
Created attachment 15980 [details]

A more complete patch. It cleans up minor crud in the CSS selector handling, but stays clear of any major changes. 

I decided a larger patch probably wasn't suitable at this time.
Comment 6 Allan Sandfeld Jensen 2007-08-15 08:08:55 PDT
Comment on attachment 15980 [details]

forget it, it fails a few regression-tests, now that I got the tests working.
Comment 7 Allan Sandfeld Jensen 2007-08-16 06:00:51 PDT
Created attachment 15995 [details]
New patch

Updated patch. I had missed how you handled pseudostyles differently.

I still get regression-failures, but I assume now that the rest are normal for the WebKitQt build.
Comment 8 Dave Hyatt 2007-08-19 21:01:02 PDT
Comment on attachment 15995 [details]
New patch

This looks ok.  What did you mean when you said that there are still failures?  Are there tests we need to worry about (or do they just need to be fixed because they pass now)?
Comment 9 Allan Sandfeld Jensen 2007-08-19 23:06:24 PDT
I have around 100 test that fails with small stuff like varying heights. I didn't read all of them. I assume that most are just the difference between Mac and Qt versions, but some are likely to be improvements too. I am still working on getting the tests to run properly.
Comment 10 Cameron Zwarich (cpst) 2007-08-28 21:35:11 PDT
The only two failures I get on the Mac are fast/js/function-decompilation-operators.html and http/tests/security/cross-frame-access-protocol-explicit.html. I doubt these are failing due to the patch.
Comment 11 Maciej Stachowiak 2007-08-31 18:28:52 PDT
Comment on attachment 15995 [details]
New patch

Given Cameron's comment and hyatt's previous comment, r=me for the feature-branch. We may need to roll feature branch forward for this to apply cleanly.
Comment 12 Allan Sandfeld Jensen 2007-09-17 06:04:33 PDT
Created attachment 16305 [details]
Updated patch

This updated patch fixes a possible performance regression I thought would never occur in the wild.

The regression occured on a very deep tree with similar nested nodes, and a 3 or more part descent selector that matched these nodes. Unfortunately I found a case with "XHTML served as HTML" this week that did just that, because a lot of elements were never closed.
Comment 13 Eric Seidel (no email) 2007-10-11 13:27:32 PDT
Just curious what the status here is.  Did you mean to mark that patch for review?
Comment 14 Allan Sandfeld Jensen 2007-10-11 13:34:00 PDT
The old patch was approved. This new patch is just a speed-up. 
Comment 15 Eric Seidel (no email) 2007-10-11 13:55:28 PDT
Comment on attachment 16305 [details]
Updated patch

I know mjs already reviewed the old one, but I figured I should at least look before landing.  Still looks sane.  r=me.
Comment 16 Eric Seidel (no email) 2007-10-11 18:27:18 PDT
Landed on feature-branch.