Bug 117388

Summary: Add special tree walking for the single tag or class CSS query selectors
Product: WebKit Reporter: Benjamin Poulain <benjamin>
Component: New BugsAssignee: Benjamin Poulain <benjamin>
Status: RESOLVED FIXED    
Severity: Normal CC: allan.jensen, commit-queue, esprehn+autocc, glenn, macpherson, menard, rniwa
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch rniwa: review+

Description Benjamin Poulain 2013-06-09 18:50:40 PDT
Add special tree walking for the single tag or class CSS query selectors
Comment 1 Benjamin Poulain 2013-06-09 18:53:52 PDT
Created attachment 204132 [details]
Patch
Comment 2 Ryosuke Niwa 2013-06-09 20:11:35 PDT
Comment on attachment 204132 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=204132&action=review

> Source/WebCore/dom/SelectorQuery.cpp:228
>          const SelectorData& selectorData = m_selectors[0];

Maybe we should consider the case where we have multiple selectors as a special case instead?
It might also make sense to apply these optimizations to each selector even when we have multiple selectors.
e.g. #hello, #world shouldn't be doing a tree traversal if #hello and #world didn't have multiple matching elements.
Comment 3 Benjamin Poulain 2013-06-09 20:26:51 PDT
> Maybe we should consider the case where we have multiple selectors as a special case instead?
> It might also make sense to apply these optimizations to each selector even when we have multiple selectors.
> e.g. #hello, #world shouldn't be doing a tree traversal if #hello and #world didn't have multiple matching elements.

Since we need to preserve the order, we cannot apply the optimizations on each selector in the case of multiselector.

"#hello, #world", or "#hello a, #hello b" are interesting cases. We should look into that.
Comment 4 Ryosuke Niwa 2013-06-09 20:33:48 PDT
(In reply to comment #3)
> > Maybe we should consider the case where we have multiple selectors as a special case instead?
> > It might also make sense to apply these optimizations to each selector even when we have multiple selectors.
> > e.g. #hello, #world shouldn't be doing a tree traversal if #hello and #world didn't have multiple matching elements.
> 
> Since we need to preserve the order, we cannot apply the optimizations on each selector in the case of multiselector.
> 
> "#hello, #world", or "#hello a, #hello b" are interesting cases. We should look into that.

Suppose we have selectors #id_1, #id_2, #id_3, ... #id_n and each id_n resolves to exactly one element e_n, then we should be able to sort e_1, etc... e_n in O(k n log n) where k is the depth of the tree.
Comment 5 Benjamin Poulain 2013-06-10 01:04:19 PDT
Committed r151365: <http://trac.webkit.org/changeset/151365>