stylo: Make querySelector and querySelectorAll use stylo.

RESOLVED FIXED

Status

()

Core
CSS Parsing and Computation
P3
normal
RESOLVED FIXED
a month ago
19 days ago

People

(Reporter: emilio, Assigned: emilio)

Tracking

(Depends on: 1 bug, Blocks: 4 bugs, {leave-open})

unspecified
leave-open
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox57 wontfix)

Details

MozReview Requests

()

Submitter Diff Changes Open Issues Last Updated
Loading...
Error loading review requests:

Attachments

(15 attachments)

59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
59 bytes, text/x-review-board-request
Details | Review
59 bytes, text/x-review-board-request
heycam
: review+
Details | Review
59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
59 bytes, text/x-review-board-request
Details | Review
59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
59 bytes, text/x-review-board-request
Details | Review
59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
59 bytes, text/x-review-board-request
Details | Review
59 bytes, text/x-review-board-request
heycam
: review+
Details | Review
59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
59 bytes, text/x-review-board-request
xidorn
: review+
Details | Review
41 bytes, text/x-github-pull-request
Details | Review | Splinter Review
Comment hidden (empty)
(Assignee)

Comment 1

a month ago
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)
(Assignee)

Comment 2

a month ago
I'll post the patches for reference here, so you can try out and such.
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
(Assignee)

Updated

a month ago
See Also: → bug 1410663
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
(Assignee)

Comment 28

a month ago
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.
(Assignee)

Updated

a month ago
Summary: stylo: Make querySelector use stylo. → stylo: Make querySelector and querySelectorAll use stylo.
(Assignee)

Updated

a month ago
Attachment #8920845 - Flags: review?(cam)
Attachment #8920846 - Flags: review?(cam)
Attachment #8920847 - Flags: review?(cam)
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)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
(Assignee)

Comment 39

a month ago
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 41

a month ago
mozreview-review
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 42

a month ago
mozreview-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 43

a month ago
mozreview-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 44

a month ago
mozreview-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 45

a month ago
mozreview-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 46

a month ago
mozreview-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 47

a month ago
mozreview-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 48

a month ago
mozreview-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 49

a month ago
mozreview-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 50

a month ago
mozreview-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 51

a month ago
mozreview-review-reply
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 52

a month ago
mozreview-review
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 53

a month ago
mozreview-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 54

a month ago
mozreview-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. :-)
(Assignee)

Comment 56

a month ago
Created attachment 8920962 [details] [review]
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.
Blocks: 600554, 1027978
Blocks: 499198
Blocks: 988740
Blocks: 1134521
Blocks: 1165852
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.

Comment 60

a month ago
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
(Assignee)

Comment 61

a month ago
The other patches still need to land.
Keywords: leave-open

Updated

a month ago
status-firefox57: --- → wontfix
Priority: -- → P3
https://hg.mozilla.org/mozilla-central/rev/b43cc917edad
(Assignee)

Comment 63

a month ago
Some more groundwork to implement the optimizations for id selectors and such in https://github.com/servo/servo/pull/19024.
(Assignee)

Comment 64

25 days ago
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.
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
(Assignee)

Updated

25 days ago
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)
(Assignee)

Comment 79

25 days ago
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...
(Assignee)

Comment 93

25 days ago
(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.
(Assignee)

Comment 94

25 days ago
mozreview-review-reply
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.
(Assignee)

Updated

25 days ago
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+
(Assignee)

Comment 100

23 days ago
mozreview-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 hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
(Assignee)

Comment 115

23 days ago
mozreview-review-reply
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 hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
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+
(Assignee)

Comment 125

22 days ago
mozreview-review-reply
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.

Comment 126

21 days ago
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
https://hg.mozilla.org/mozilla-central/rev/2d930b3c9a7e
https://hg.mozilla.org/mozilla-central/rev/cea3b79ef85f
https://hg.mozilla.org/mozilla-central/rev/8b2b76c7fe9f
https://hg.mozilla.org/mozilla-central/rev/ab10dee67546
(Assignee)

Updated

19 days ago
Status: NEW → RESOLVED
Last Resolved: 19 days ago
Resolution: --- → FIXED
Depends on: 1414789
You need to log in before you can comment on or make changes to this bug.