Use the information of Document::idmap for selector matching

[tetsuharuohzeki]

We have the table to cache the position of all id-ed elements in DOM Tree as Document::idmap.

In other browsers, they also have same information and use it for optimize ID selector matching.
So we should use it.

[JIoJIaJIu]

i take it, please

[JIoJIaJIu]

it was done? https://github.com/servo/servo/blob/master/components/script/dom/document.rs#L665

[Ms2ger]

@SimonSapin?

[SimonSapin]

I imagine how this would help selectors API (where for a selector and a document we find elements), but not for stylesheets (where for a given element we find style rules that match). @saneyuki, do you know how it’s used in other browsers?

@JIoJIaJIu, line 665 now is in the middle of fn click_event_filter_by_disabled_state. I assume you meant to link to something else? When viewing code on GitHub, you can press the y key on your keyboard to go to an URL for the same thing but with a commit hash instead of a branch name in the URL.

[Ms2ger]

That link was to the getElementById implementation.

[JIoJIaJIu]

thank you for tip @SimonSapin

servo/components/script/dom/document.rs

Line 843 in 154427c

fn GetElementById(self, id: DOMString) -> Option<Temporary<Element>> {

[tetsuharuohzeki]

@SimonSapin

Other browsers use the id information in DOM tree as fast path for selector matching if it provides id selector. They try to match id selector at first. It fallback down the later path if the fast path failed.

Gecko & Blink have some fast path. but I feel their path are primitive.

WebKit does the most aggressive optimization for selector matching including about id selector.
Today, WebKit's fast path is for selector JIT mainly. But their some optimization are not only for selector JIT.

I don't know how much of their path is used from non-JIT one now and how we can implement some of them without JIT approach...
(As an aside, @Constellation knows the implementation details of them very very much, he might answer more details if we ask some their tricks).

Gecko

• https://github.com/mozilla/gecko-dev/blob/3ef3c9721e03a175fa595ecbc16c6bb68b56f5fd/dom/base/nsINode.cpp#L2468
• https://github.com/mozilla/gecko-dev/blob/3ef3c9721e03a175fa595ecbc16c6bb68b56f5fd/dom/base/nsINode.cpp#L2529

Blink

• http://mxr.mozilla.org/chromium/source/src/third_party/WebKit/Source/core/dom/SelectorQuery.cpp#426

WebKit

• https://github.com/WebKit/webkit/blob/ec10594da63404c04175eced7b8301bce2cd8098/Source/WebCore/dom/SelectorQuery.cpp#L214
• https://github.com/WebKit/webkit/blob/ec10594da63404c04175eced7b8301bce2cd8098/Source/WebCore/dom/SelectorQuery.cpp#L243

And I heard from @Constellation that WebKit used to have non-JIT fast path more but they removed them because Selector JIT beat non-JIT fast path.