Bug 117388 – Add special tree walking for the single tag or class CSS query selectors

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Benjamin Poulain]

Add special tree walking for the single tag or class CSS query selectors

[Benjamin Poulain]

Created attachment 204132 [details]
Patch

[Ryosuke Niwa]

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.

[Benjamin Poulain]

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

[Ryosuke Niwa]

(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.

[Benjamin Poulain]

Committed r151365: <http://trac.webkit.org/changeset/151365>