Closed Bug 1410624 Opened 2 years ago Closed 2 years ago

stylo: Make querySelector and querySelectorAll use stylo.

Categories

(Core :: CSS Parsing and Computation, enhancement, P3)

enhancement

Tracking

()

RESOLVED FIXED
Tracking Status
firefox57 --- wontfix

People

(Reporter: emilio, Assigned: emilio)

References

(Blocks 4 open bugs)

Details

Attachments

(15 files)

59 bytes, text/x-review-board-request
xidorn
: review+
Details
59 bytes, text/x-review-board-request
xidorn
: review+
Details
59 bytes, text/x-review-board-request
xidorn
: review+
Details
59 bytes, text/x-review-board-request
bzbarsky
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
xidorn
: review+
Details
59 bytes, text/x-review-board-request
bzbarsky
: review+
Details
59 bytes, text/x-review-board-request
xidorn
: review+
Details
59 bytes, text/x-review-board-request
bzbarsky
: review+
Details
59 bytes, text/x-review-board-request
xidorn
: review+
Details
59 bytes, text/x-review-board-request
bzbarsky
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
xidorn
: review+
Details
59 bytes, text/x-review-board-request
xidorn
: review+
Details
41 bytes, text/x-github-pull-request
Details | Review
No description provided.
So, I plugged this in using the invalidator stuff, and the results were about as expected... Something like:

  https://github.com/servo/servo/compare/master...emilio:qs?expand=1

Makes some stuff much faster, but other slower.

Note that that code is not perfect in the sense that only stops invalidating when we go to the next level, not as soon as we find another node, but it works fine for a proof of concept.

In my testing, this makes us 4 to 5 times faster in the test I was targeting, like:

  https://webkit.org/blog-files/css-jit-introduction/html5-single-page-microbenchmark.html

Which is cute.

However, the real impact on perf depends heavily on selector / tree size. Plus, there's an annoying thing which I need to fix, which is:

  https://github.com/servo/servo/compare/master...emilio:qs?expand=1#diff-fc59945a4dc2fdb40cec1577640af16dR94

(Which is fixable, but slightly annoying)

So at this point is not 100% clear to me whether I should bother or not. So this is a call for: Are there any known real-world querySelector example where we care about perf?

I can also implement both, I guess, and see, but anyway, I'd rather ask first :)
Flags: needinfo?(cam)
Flags: needinfo?(bzbarsky)
I'll post the patches for reference here, so you can try out and such.
See Also: → 1410663
I think I'm happy with this. I want to do some more profiling / waiting for talos, but I may as well get this reviewed now.
Summary: stylo: Make querySelector use stylo. → stylo: Make querySelector and querySelectorAll use stylo.
Attachment #8920786 - Flags: review?(cam)
Attachment #8920787 - Flags: review?(cam)
Attachment #8920788 - Flags: review?(cam)
Attachment #8920814 - Flags: review?(cam)
Attachment #8920815 - Flags: review?(cam)
Attachment #8920842 - Flags: review?(cam)
Attachment #8920789 - Flags: review?(cam)
Attachment #8920790 - Flags: review?(cam)
Attachment #8920843 - Flags: review?(cam)
Attachment #8920844 - Flags: review?(cam)
Attachment #8920845 - Flags: review?(cam)
Attachment #8920846 - Flags: review?(cam)
Attachment #8920847 - Flags: review?(cam)
So, with this patches, this regresses dromaeo_css by 15 / 20%, with and without the invalidation stuff.

The invalidation stuff is a bit slower though.

After looking at the test, I think I know why.

For the "invalidation" vs "no invalidation" stuff, the test is testing nth-index selectors, and using the invalidation machinery something like div:nth-child(2) matches in the opposite direction, that is, first :nth-child, then <div>.

This makes our nth-index-cache suck a lot of time.

The other difference I think is that we don't optimize selectors like "#footer #foo", while Gecko does. This is (in spirit) a similar optimization to what Blink does and I described above, so I may as well implement both.
Since I won't have much time for reviewing after today for a few weeks, I'll assume that the fixes for comment 39 will be additional patches on top of this series.  So I'll review these, but I'll also defer to bz on what real world querySelector cases we need to care about, since I don't really know.
Flags: needinfo?(cam)
Comment on attachment 8920786 [details]
style: Add a Document::elements_with_id API.

https://reviewboard.mozilla.org/r/191780/#review197034

Heh, yes this does look like a patch I had locally at one point. :-)
Attachment #8920786 - Flags: review?(cam) → review+
Comment on attachment 8920787 [details]
style: Move the single simple selector optimizations to a different function.

https://reviewboard.mozilla.org/r/191782/#review197036
Attachment #8920787 - Flags: review?(cam) → review+
Comment on attachment 8920788 [details]
style: Introduce TNode::is_in_document.

https://reviewboard.mozilla.org/r/191784/#review197038
Attachment #8920788 - Flags: review?(cam) → review+
Comment on attachment 8920814 [details]
style: Add a fast path for querySelector/All with a single id selector using the doc ID table.

https://reviewboard.mozilla.org/r/191794/#review197042
Attachment #8920814 - Flags: review?(cam) → review+
Comment on attachment 8920815 [details]
style: Optimize all ids in the rightmost compound selector.

https://reviewboard.mozilla.org/r/191796/#review197048
Attachment #8920815 - Flags: review?(cam) → review+
Comment on attachment 8920842 [details]
style: Extract a bit better the logic for finding elements with an ID under a subtree.

https://reviewboard.mozilla.org/r/191828/#review197050
Attachment #8920842 - Flags: review?(cam) → review+
Comment on attachment 8920789 [details]
style: Add a query-selector fast path for #id foo.

https://reviewboard.mozilla.org/r/191786/#review197054

I guess "invalidator" is now not really an accurate name for what the code does, since we use it for non-invalidation purposes.  Not sure I have a good suggestion though.
Attachment #8920789 - Flags: review?(cam) → review+
Comment on attachment 8920790 [details]
Bug 1410624: style: Hook QuerySelector into stylo.

https://reviewboard.mozilla.org/r/191788/#review197056

::: layout/style/ServoBindingList.h:143
(Diff revision 4)
> +SERVO_BINDING_FUNC(Servo_SelectorList_QueryAll, void,
> +                   RawGeckoNodeBorrowed, RawServoSelectorListBorrowed,
> +                   void* content_list)

This should move into a later patch.

::: servo/ports/geckolib/glue.rs:1635
(Diff revision 4)
> +
> +    result.first()

Maybe assert in here that result has at most one element in it?
Attachment #8920790 - Flags: review?(cam) → review+
Comment on attachment 8920843 [details]
style: Bump the selector lenght heuristic.

https://reviewboard.mozilla.org/r/191830/#review197060
Attachment #8920843 - Flags: review?(cam) → review+
Comment on attachment 8920844 [details]
style: Remove some unneeded indirections in the invalidation code.

https://reviewboard.mozilla.org/r/191832/#review197062

::: servo/components/style/dom_apis.rs:237
(Diff revision 2)
> +    }
> +}
> +
>  /// <https://dom.spec.whatwg.org/#dom-parentnode-queryselector>
> -pub fn query_selector<E: TElement>(
> +pub fn query_selector<E, Q>(
>      root: E::ConcreteNode,

Elsewhere we call this the scope.  Should we call it that here too?
Attachment #8920844 - Flags: review?(cam) → review+
Comment on attachment 8920790 [details]
Bug 1410624: style: Hook QuerySelector into stylo.

https://reviewboard.mozilla.org/r/191788/#review197056

> Maybe assert in here that result has at most one element in it?

Don't worry, I see the specialization of the output type later makes this unnecessary.
Comment on attachment 8920845 [details]
Allow disabling invalidation-based querySelector from C++

https://reviewboard.mozilla.org/r/191834/#review197068

::: servo/components/style/dom_apis.rs:257
(Diff revision 2)
> +        Component::ID(ref id) => {
> +            let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
> +            collect_all_elements::<E, Q, _>(root, results, |element| {
> +                element.has_id(id, case_sensitivity)
> +            })
> +        }

Add a comment here to say we might want to somehow re-use Gecko's ID table on the document to look this up directly?
Attachment #8920845 - Flags: review?(cam) → review+
Comment on attachment 8920846 [details]
Bug 1410624: Integrate QuerySelectorAll in Gecko.

https://reviewboard.mozilla.org/r/191836/#review197074

::: layout/style/ServoBindings.cpp:2865
(Diff revision 2)
> +  nsSimpleContentList* aList,
> +  const Element** aElements,
> +  size_t aLength)
> +{
> +  MOZ_ASSERT(aElements);
> +  MOZ_ASSERT(aLength);

Assert aList too?  Also, if the reason for asserting aLength is just so we ensure we don't bother calling this function when we found no matching elements, please use a message like "Avoid calling this with no elements".

But actually I don't think it's a big deal and would probably just drop the assertion on aLength.
Attachment #8920846 - Flags: review?(cam) → review+
Comment on attachment 8920847 [details]
style: Inline DomDescendants.

https://reviewboard.mozilla.org/r/191838/#review197076
Attachment #8920847 - Flags: review?(cam) → review+
Thanks for the nicely split up patches. :-)
Attached file Servo bits
> Are there any known real-world querySelector example where we care about perf?

Well, jQuery's $(whatever) bits, right?  How "real-world" do you want?  For example, is "speedometer" actually real-world enough?  ;)

What about the ublock origin case that came up recently?
Flags: needinfo?(bzbarsky)
Comment on attachment 8920846 [details]
Bug 1410624: Integrate QuerySelectorAll in Gecko.

https://reviewboard.mozilla.org/r/191836/#review197354

::: layout/style/ServoBindings.cpp:2867
(Diff revision 2)
> +  size_t aLength)
> +{
> +  MOZ_ASSERT(aElements);
> +  MOZ_ASSERT(aLength);
> +
> +  for (size_t i = 0; i < aLength; ++i) {

We should SetCapacity(aLength) here to avoid reallocations.
Comment on attachment 8920845 [details]
Allow disabling invalidation-based querySelector from C++

https://reviewboard.mozilla.org/r/191834/#review197360

::: servo/components/style/dom_apis.rs:258
(Diff revision 2)
> +    match *component {
> +        Component::ExplicitUniversalType => {
> +            collect_all_elements::<E, Q, _>(root, results, |_| true)
> +        }
> +        Component::ID(ref id) => {
> +            let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();

Gecko has a much faster (probably) fast-path here for non-quirks-mode documents, that uses the fact that we already maintain a list of all elements with a given id.  Might be worth adding here.
Pushed by ecoal95@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/b43cc917edad
Add some declarations and bindings so the build isn't busted when servo-vcs-sync goes back alive. r=me,heycam
The other patches still need to land.
Keywords: leave-open
Priority: -- → P3
Some more groundwork to implement the optimizations for id selectors and such in https://github.com/servo/servo/pull/19024.
Just for the record, http://dromaeo.com/?id=269340,269341,269343,269346 is the performance numbers I'm looking at.

First of all is without querySelector / qSA being implemented by Servo. Second is with most of the patches here. Third is enabling invalidation, four is force-inlining selector_list_matches and matches_complex_selector_internal.

I'll still look into improving it tomorrow, but I think I want to prevent most of it from bitrotting.
Attachment #8920786 - Flags: review?(xidorn+moz)
Attachment #8920787 - Flags: review?(xidorn+moz)
Attachment #8920788 - Flags: review?(xidorn+moz)
Attachment #8920814 - Flags: review?(xidorn+moz)
Attachment #8920815 - Flags: review?(xidorn+moz)
Attachment #8920842 - Flags: review?(xidorn+moz)
Attachment #8920789 - Flags: review?(xidorn+moz)
Attachment #8920843 - Flags: review?(xidorn+moz)
Attachment #8920844 - Flags: review?(xidorn+moz)
Attachment #8920845 - Flags: review?(xidorn+moz)
Attachment #8920847 - Flags: review?(xidorn+moz)
Attachment #8920869 - Flags: review?(xidorn+moz)
Mozreview is as usual super-broken. Modulo the first two patches, they have no reviewer yet.

Xidorn, feel free to forward to bz if there's any patch that you're not confident reviewing. Also, it's probably worth to look at Gecko's FindMatchingElements here for a bunch of stuff[1].

[1]: http://searchfox.org/mozilla-central/rev/1c4901d060e3953e41088c038b62a0c026c1e1fb/dom/base/nsINode.cpp#2861
Comment on attachment 8920846 [details]
Bug 1410624: Integrate QuerySelectorAll in Gecko.

https://reviewboard.mozilla.org/r/191836/#review199796
Attachment #8920846 - Flags: review+
Comment on attachment 8920790 [details]
Bug 1410624: style: Hook QuerySelector into stylo.

https://reviewboard.mozilla.org/r/191788/#review197056

> Don't worry, I see the specialization of the output type later makes this unnecessary.

The assertion should probably be put in `QueryFirst::append_element`.
Comment on attachment 8920790 [details]
Bug 1410624: style: Hook QuerySelector into stylo.

https://reviewboard.mozilla.org/r/191788/#review199802
Attachment #8920790 - Flags: review+
Comment on attachment 8920786 [details]
style: Add a Document::elements_with_id API.

https://reviewboard.mozilla.org/r/191780/#review199816

::: servo/components/style/gecko/wrapper.rs:123
(Diff revision 4)
> +            // NOTE(emilio): We rely on the in-memory representation of
> +            // GeckoElement<'ld> and *mut RawGeckoElement being the same.
> +            Ok(mem::transmute(elements))

This is unsound. [1] Can we add some kind of static assertion somewhere to ensure this?

[1] https://play.rust-lang.org/?gist=de787c903fa962746d7f6990a2cd40af&version=stable
Attachment #8920786 - Flags: review?(xidorn+moz) → review+
Comment on attachment 8920787 [details]
style: Move the single simple selector optimizations to a different function.

https://reviewboard.mozilla.org/r/191782/#review199818
Attachment #8920787 - Flags: review?(xidorn+moz) → review+
Comment on attachment 8920788 [details]
style: Introduce TNode::is_in_document.

https://reviewboard.mozilla.org/r/191784/#review199820

::: servo/components/style/dom.rs:194
(Diff revision 4)
> +    /// Returns whether the node is attached to a document.
> +    fn is_in_document(&self) -> bool;

I wonder don't you need to implement this for Servo as well?
Attachment #8920788 - Flags: review?(xidorn+moz) → review+
Comment on attachment 8920814 [details]
style: Add a fast path for querySelector/All with a single id selector using the doc ID table.

https://reviewboard.mozilla.org/r/191794/#review199824
Attachment #8920814 - Flags: review?(xidorn+moz) → review+
Attachment #8920815 - Flags: review?(xidorn+moz) → review?(bzbarsky)
Comment on attachment 8920842 [details]
style: Extract a bit better the logic for finding elements with an ID under a subtree.

https://reviewboard.mozilla.org/r/191828/#review199866

::: servo/components/style/dom_apis.rs:245
(Diff revision 3)
>      false
>  }
>  
> -fn find_elements_with_id<E, Q, F>(
> +/// Execute `callback` on each element with a given `id` under `root`.
> +///
> +/// If `callback` returns false, iteration will stop immediately.

Ah, I really hope we have Python / JavaScript style `yield` in Rust...
Attachment #8920842 - Flags: review?(xidorn+moz) → review+
Comment on attachment 8920844 [details]
style: Remove some unneeded indirections in the invalidation code.

https://reviewboard.mozilla.org/r/191832/#review199884
Attachment #8920844 - Flags: review?(xidorn+moz) → review+
Comment on attachment 8920847 [details]
style: Inline DomDescendants.

https://reviewboard.mozilla.org/r/191838/#review199888

I'm not really convinced that this is something meaningful. IIRC, the compiler can inline things automatically when it thinks it should when functions are in the same crate, and `#[inline]` is generally more useful when some public function needs to be invoked outside the current crate.

In this case, all callsites of the functions are in the style crate, so I suspect how much value the additional `#[inline]` attribute would really gain... But I guess it doesn't harm anything either, so I'm fine with it.
Attachment #8920847 - Flags: review?(xidorn+moz) → review+
Comment on attachment 8920869 [details]
style: Inline a bunch of stuff, fixup indentation of a couple things.

https://reviewboard.mozilla.org/r/191840/#review199890

`matches_selector_list` and `matches_complex_selector` seems nontrivial, especially the latter. Does it really help a lot making it worth manually forcing them to be inlined? Any number showing it makes any significant difference on performance?
Attachment #8920869 - Flags: review?(xidorn+moz)
Attachment #8920789 - Flags: review?(xidorn+moz) → review?(bzbarsky)
Attachment #8920843 - Flags: review?(xidorn+moz) → review?(bzbarsky)
Attachment #8920845 - Flags: review?(xidorn+moz)
(In reply to Emilio Cobos Álvarez [:emilio] from comment #79)
> Mozreview is as usual super-broken. Modulo the first two patches, they have
> no reviewer yet.

I guess this is because you are reusing the "MozReview-Commit-ID" somehow. New patches should have new unique "MozReview-Commit-ID" so that MozReview can correctly recognize them as new ones, rather than a revised version of previous patch.
Oh actually, you didn't have MozReview-Commit-ID in previous version of the patches... And git doesn't have hg's obsolescence feature, so MozReview cannot understand what's happening to the patches...
(In reply to Xidorn Quan [:xidorn] UTC+10 (less responsive Nov 5 ~ Dec 16) from comment #90)
> Comment on attachment 8920869 [details]
> style: Inline a bunch of stuff, fixup indentation of a couple things.
> 
> https://reviewboard.mozilla.org/r/191840/#review199890
> 
> `matches_selector_list` and `matches_complex_selector` seems nontrivial,
> especially the latter. Does it really help a lot making it worth manually
> forcing them to be inlined? Any number showing it makes any significant
> difference on performance?

See the measurements over comment 64. That's the result of inlining these two functions.

In particular, the function calls needed to reject a selector without inlining those are 4:

  matches_selector_list -> matches_complex_selector -> matches_complex_selector_internal -> matches_simple_selector

While in Gecko, it's only:

  SelectorListMatches -> SelectorMatches

Inlining the first two functions makes it comparable, and is the difference between the second and the fourth run in comment 64.
Comment on attachment 8920786 [details]
style: Add a Document::elements_with_id API.

https://reviewboard.mozilla.org/r/191780/#review199816

> This is unsound. [1] Can we add some kind of static assertion somewhere to ensure this?
> 
> [1] https://play.rust-lang.org/?gist=de787c903fa962746d7f6990a2cd40af&version=stable

I mean, it is sound, given it holds. But yeah, I'll add a static assertion.
Attachment #8920869 - Flags: review?(xidorn+moz)
Comment on attachment 8920869 [details]
style: Inline a bunch of stuff, fixup indentation of a couple things.

https://reviewboard.mozilla.org/r/191840/#review199934
Attachment #8920869 - Flags: review?(xidorn+moz) → review+
(In reply to Emilio Cobos Álvarez [:emilio] from comment #93)
> Inlining the first two functions makes it comparable, and is the difference
> between the second and the fourth run in comment 64.

Hmmm... it's still a lot slower, though...
Comment on attachment 8920789 [details]
style: Add a query-selector fast path for #id foo.

https://reviewboard.mozilla.org/r/191786/#review200764

::: servo/components/style/dom_apis.rs:247
(Diff revision 5)
>          current = n.parent_node();
>      }
>      false
>  }
>  
> -/// Execute `callback` on each element with a given `id` under `root`.
> +/// Fast path for iterating over every element with a given id in the document.

This needs to say something about how "root" is relevant...

::: servo/components/style/dom_apis.rs:285
(Diff revision 5)
>      E: TElement,
>      Q: SelectorQuery<E>,
>      F: FnMut(E) -> bool,
>  {
> -    each_element_with_id_under::<E, _>(root, id, quirks_mode, |element| {
> -        if !filter(element) {
> +    let doc = root.owner_doc();
> +    let elements = match fast_elements_with_id(&doc, root, id, quirks_mode) {

So I'm not sure what I think of passing the root through here just so we can check its in-document flag...

Seems to me like the element_is_descendant_of check should basically live wherever it is the root-is-in-document check lives.  Having them separated like this is pretty confusing.

::: servo/components/style/dom_apis.rs:434
(Diff revision 5)
> +                    if elements.is_empty() {
> +                        return Ok(());
> +                    }
> +
> +                    if elements.len() > 1 {
> +                        continue;

This could use documentation explaining why.  For querySelector, why would you care whether there is more than one, exactly?  Seems odd to me...

::: servo/components/style/dom_apis.rs:439
(Diff revision 5)
> +                        continue;
> +                    }
> +
> +                    let element = elements[0];
> +                    if !element_is_descendant_of(element, root) {
> +                        continue;

Likewise, document.
Attachment #8920789 - Flags: review?(bzbarsky) → review-
Comment on attachment 8920815 [details]
style: Optimize all ids in the rightmost compound selector.

https://reviewboard.mozilla.org/r/191796/#review200766

::: servo/components/style/dom_apis.rs:422
(Diff revision 4)
> +                None => return Err(()),
> +                Some(c) => c,
> +            };
> +
> +            if next_combinator.is_sibling() {
> +                for _ in &mut iter {}

I don't understand what this code is trying to do.  Please document it.

In fact, I'm not sure why this function bothers to walk "iter" at all once we hit a combinator.
Attachment #8920815 - Flags: review?(bzbarsky) → review-
Comment on attachment 8920843 [details]
style: Bump the selector lenght heuristic.

https://reviewboard.mozilla.org/r/191830/#review200768

::: commit-message-a65a1:1
(Diff revision 3)
> +style: Bump the selector lenght heuristic.

"length"

::: commit-message-a65a1:3
(Diff revision 3)
> +style: Bump the selector lenght heuristic.
> +
> +A selector with combinators has to have length > 2 (a component, a combinator,

This should probably be a comment in the code...
Attachment #8920843 - Flags: review?(bzbarsky) → review+
Comment on attachment 8920815 [details]
style: Optimize all ids in the rightmost compound selector.

https://reviewboard.mozilla.org/r/191796/#review200772

::: servo/components/style/dom_apis.rs:422
(Diff revision 4)
> +                None => return Err(()),
> +                Some(c) => c,
> +            };
> +
> +            if next_combinator.is_sibling() {
> +                for _ in &mut iter {}

This is just so I could write the iteration code once, and not rework it again in the next patch (that's why I left the TODO comment).

This combinator dance only applies for the next patch really, but basically the point is that we only want to look at selectors that guarantee that the elements we're looking for are in those element's subtree (that is, not affected by sibling combinators).

Will write some comments tomorrow.
Comment on attachment 8920789 [details]
style: Add a query-selector fast path for #id foo.

https://reviewboard.mozilla.org/r/191786/#review200764

> So I'm not sure what I think of passing the root through here just so we can check its in-document flag...
> 
> Seems to me like the element_is_descendant_of check should basically live wherever it is the root-is-in-document check lives.  Having them separated like this is pretty confusing.

Yeah, agree. But not passing the root made the code much more branchy. So I instead shamelessly renamed it to `fast_connected_elements_with_id` so it made sense :)

> This could use documentation explaining why.  For querySelector, why would you care whether there is more than one, exactly?  Seems odd to me...

Right, we already depend on the document order...
Comment on attachment 8920815 [details]
style: Optimize all ids in the rightmost compound selector.

https://reviewboard.mozilla.org/r/191796/#review201234

::: servo/components/style/dom_apis.rs:389
(Diff revision 5)
> +
> +        for component in &mut iter {
> +            match *component {
> +                Component::ID(ref id) => {
> +                    if combinator.is_none() {
> +                        // In the rightmost compound, just find descednants of

"descendants"

::: servo/components/style/dom_apis.rs:425
(Diff revision 5)
> +
> +            // We don't want to scan stuff affected by sibling combinators,
> +            // given we scan the subtree of elements with a given id (and we
> +            // don't want to care about scanning the siblings' subtrees).
> +            if next_combinator.is_sibling() {
> +                for _ in &mut iter {}

Maybe add an explicit "advance to the next combinator" comment?  That would make this a lot clearer.
Attachment #8920815 - Flags: review?(bzbarsky) → review+
Comment on attachment 8920789 [details]
style: Add a query-selector fast path for #id foo.

https://reviewboard.mozilla.org/r/191786/#review201184

::: servo/components/style/dom_apis.rs:248
(Diff revision 7)
>      }
>      false
>  }
>  
> -/// Execute `callback` on each element with a given `id` under `root`.
> -///
> +/// Fast path for iterating over every element with a given id in the document
> +/// connected to `root`.

Maybe "that root is connected to"?

::: servo/components/style/dom_apis.rs:437
(Diff revision 7)
> +                    if elements.is_empty() {
> +                        return Ok(());
> +                    }
> +
> +                    // Results need to be in document order. Let's not bother
> +                    // reordering or deduplicating nodes.

"... or deduplicating nodes, which we would have to do if one element with the given id were a descendant of another element with the given id."

or so, right?  That's the only case in which we have a problem.  Otherwise, the elements with the given id are already in document order, so we could just walk their descendants and all that.  The problem is that the descendant subtrees can overlap in this one case, no?

::: servo/components/style/dom_apis.rs:448
(Diff revision 7)
> +                        // If the element is not an actual descendant of the
> +                        // root, even though it's connected, we may end up
> +                        // finding stuff outside of the scope of `root`, which
> +                        // we don't really want.
> +                        if !element_is_descendant_of(element, root) {
> +                            continue 'component_loop;

This needs a comment explaining why we're skipping all the way along component_loop, not just to the next element.  Maybe the comment before this if block should say:

    // If the element is not a descendant of the root, then it may have descendants that match our selector that _are_ descendants of the root, and other descendants that match our selector that are _not_.  So we can't just walk over the element's descendants and match the selector against all of them, nor can we skip looking at this element's descendants.  Give up on trying to optimize based on this id and keep walking our selector.
Attachment #8920789 - Flags: review?(bzbarsky) → review+
Comment on attachment 8920845 [details]
Allow disabling invalidation-based querySelector from C++

https://reviewboard.mozilla.org/r/191834/#review201238
Attachment #8920845 - Flags: review?(bzbarsky) → review+
Comment on attachment 8920789 [details]
style: Add a query-selector fast path for #id foo.

https://reviewboard.mozilla.org/r/191786/#review201184

> "... or deduplicating nodes, which we would have to do if one element with the given id were a descendant of another element with the given id."
> 
> or so, right?  That's the only case in which we have a problem.  Otherwise, the elements with the given id are already in document order, so we could just walk their descendants and all that.  The problem is that the descendant subtrees can overlap in this one case, no?

Right.
Pushed by ecoal95@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/2d930b3c9a7e
Integrate QuerySelectorAll in Gecko. r=heycam
https://hg.mozilla.org/integration/autoland/rev/cea3b79ef85f
style: Hook QuerySelector into stylo. r=heycam
https://hg.mozilla.org/integration/autoland/rev/8b2b76c7fe9f
Add a Document::elements_with_id API. r=xidorn
https://hg.mozilla.org/integration/autoland/rev/ab10dee67546
Allow disabling invalidation-based querySelector from C++. r=bz
Status: NEW → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Depends on: 1414789
Removing leave-open keyword from resolved bugs, per :sylvestre.
Keywords: leave-open
You need to log in before you can comment on or make changes to this bug.