Optimized querySelector(All) when selector contains #id.

Optimized querySelector(All) when selector contains #id.

There existed an optimization that did an element lookup for an id if the
leftmost part of the selector was an id selector. Without this change, these
queries would do an id lookup:

querySelector("#id"), querySelector("#id.class")

while these wouldn't:

querySelector(".class#id"), querySelector("[name=x]#id")

This change modifies the element lookup to include the latter two.

More importantly, it also extends the optimization for id selectors to limit
traversal of the dom-tree to the sub-tree rooted at the element with an id
matching the rightmost id selector in the whole selector. For id selectors
appearing left of adjacent combinators, the traversal needs to be rooted at
the parent of the element with the given id.

Examples:

querySelector("#id span") - traversal from the id element.
querySelector("#id + div span") - traversal from the parent of the id element.

This fix should make this:

querySelector("#id span")

as fast as:

getElementById("id").querySelector("span")

BUG=240188
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=150417

[haraken, 2013-05-14 00:32:58]

The approach looks good to me, although I'm not sure of detailed implementation
of findTraverseRoot().

tasak, morrita-san: could you take a look at findTraverseRoot()?

https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
File PerformanceTests/Parser/query-selector-id-deep.html (right):

https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
PerformanceTests/Parser/query-selector-id-deep.html:24: var res =
document.querySelector("#foo998 h1");

Instead of modifying existing perf tests, I'd prefer adding a new perf test for
this change.

https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
File PerformanceTests/Parser/query-selector-id-last.html (right):

https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
PerformanceTests/Parser/query-selector-id-last.html:22: var res =
document.querySelector("#foo999 > h1");

Ditto.

https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
File Source/core/dom/SelectorQuery.cpp (right):

https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
Source/core/dom/SelectorQuery.cpp:149: if (!traverseRoot)

You can put this above the findTraverseRoot() line.

https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
Source/core/dom/SelectorQuery.cpp:153: Element* element =
toElement(traverseRoot);

Don't you need to check if traverseRoot is an Element?

[Hajime Morrita, 2013-05-14 00:51:39]

https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
File Source/core/dom/SelectorQuery.cpp (right):

https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
Source/core/dom/SelectorQuery.cpp:107: bool
SelectorDataList::findTraverseRoot(Node*& rootNode) const
Using in-out parameter is almost bad idea.
This could be cleaner by, for example, returning a struct or a pair which
indicates the result.

[tasak, 2013-05-14 04:30:14]

I looked at the patch from the viewpoint of ::-webkit-distributed and custom
pseudo.

So, findTraverseRoot looks fine, because:

- currently ::-webkit-distributed doesn't work correctly when used in
querySelector or querySelectorAll.

- custom pseudo is disallowed in querySelector or querySelectorAll.

[rune, 2013-05-14 08:51:04]

On 2013/05/14 00:32:58, haraken wrote:
> The approach looks good to me, although I'm not sure of detailed
implementation
> of findTraverseRoot().
> 
> tasak, morrita-san: could you take a look at findTraverseRoot()?
> 
>
https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
> File PerformanceTests/Parser/query-selector-id-deep.html (right):
> 
>
https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
> PerformanceTests/Parser/query-selector-id-deep.html:24: var res =
> document.querySelector("#foo998 h1");
> 
> Instead of modifying existing perf tests, I'd prefer adding a new perf test
for
> this change.

I've added two new files/tests, not modified any, although they're based on
existing ones.

>
https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
> File PerformanceTests/Parser/query-selector-id-last.html (right):
> 
>
https://codereview.chromium.org/14581013/diff/1/PerformanceTests/Parser/query...
> PerformanceTests/Parser/query-selector-id-last.html:22: var res =
> document.querySelector("#foo999 > h1");
> 
> Ditto.

See above.

>
https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
> File Source/core/dom/SelectorQuery.cpp (right):
> 
>
https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
> Source/core/dom/SelectorQuery.cpp:149: if (!traverseRoot)
> 
> You can put this above the findTraverseRoot() line.

It's testing the output of the in-out traverseRoot parameter, so that wouldn't
be be correct. I'm don't think traverseRoot/rootNode can ever be 0 before the
call to findTraverseRoot().

>
https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
> Source/core/dom/SelectorQuery.cpp:153: Element* element =
> toElement(traverseRoot);
> 
> Don't you need to check if traverseRoot is an Element?

It should always be an Element when matching a single node, and currently, when
true is returned from findTraverseRoot, traverseRoot is either 0 or an Element
returned from getElementById().

I can add an assert and an if-test for robustness before toElement() is called:

ASSERT(traverseRoot->isElement());
if (!traverseRoot->isElement())
    return;

and also rename matchSingleNode to matchSingleElement for clarity. How does that
sound?

[rune, 2013-05-14 10:44:33]

On 2013/05/14 00:51:39, morrita1 wrote:
>
https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
> File Source/core/dom/SelectorQuery.cpp (right):
> 
>
https://codereview.chromium.org/14581013/diff/1/Source/core/dom/SelectorQuery...
> Source/core/dom/SelectorQuery.cpp:107: bool
> SelectorDataList::findTraverseRoot(Node*& rootNode) const
> Using in-out parameter is almost bad idea.
> This could be cleaner by, for example, returning a struct or a pair which
> indicates the result.

Fixed in Patch Set 2.

[rune, 2013-05-14 10:46:34]

I think I've addressed the issues from patch set 1.

[haraken, 2013-05-14 12:50:33]

LGTM, but please wait for review from tasak@.

tasak: r?

https://codereview.chromium.org/14581013/diff/8001/Source/core/dom/SelectorQu...
File Source/core/dom/SelectorQuery.cpp (right):

https://codereview.chromium.org/14581013/diff/8001/Source/core/dom/SelectorQu...
Source/core/dom/SelectorQuery.cpp:107: std::pair<bool, Node*>
SelectorDataList::findTraverseRoot(Node* rootNode) const

Let's add a comment about what the return values mean.

https://codereview.chromium.org/14581013/diff/8001/Source/core/dom/SelectorQu...
Source/core/dom/SelectorQuery.cpp:154: if (!traverseRootNode->isElementNode())

You can remove this if statement, because it shouldn't happen.

[rune, 2013-05-14 14:01:54]

On 2013/05/14 12:50:33, haraken wrote:
> LGTM, but please wait for review from tasak@.
> 
> tasak: r?
> 
>
https://codereview.chromium.org/14581013/diff/8001/Source/core/dom/SelectorQu...
> File Source/core/dom/SelectorQuery.cpp (right):
> 
>
https://codereview.chromium.org/14581013/diff/8001/Source/core/dom/SelectorQu...
> Source/core/dom/SelectorQuery.cpp:107: std::pair<bool, Node*>
> SelectorDataList::findTraverseRoot(Node* rootNode) const
> 
> Let's add a comment about what the return values mean.

Done.

>
https://codereview.chromium.org/14581013/diff/8001/Source/core/dom/SelectorQu...
> Source/core/dom/SelectorQuery.cpp:154: if (!traverseRootNode->isElementNode())
> 
> You can remove this if statement, because it shouldn't happen.

Done.

[tasak, 2013-05-15 07:14:19]

lgtm

[commit-bot: I haz the power, 2013-05-15 07:15:48]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rune@opera.com/14581013/16001

[commit-bot: I haz the power, 2013-05-15 13:52:18]

Change committed as 150417