style/invalidation/element/
invalidator.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5//! The struct that takes care of encapsulating all the logic on where and how
6//! element styles need to be invalidated.
7
8use crate::context::StackLimitChecker;
9use crate::dom::{TElement, TNode, TShadowRoot};
10use crate::invalidation::element::invalidation_map::{
11    Dependency, DependencyInvalidationKind, NormalDependencyInvalidationKind,
12    RelativeDependencyInvalidationKind,
13};
14use selectors::matching::matches_compound_selector_from;
15use selectors::matching::{CompoundSelectorMatchingResult, MatchingContext};
16use selectors::parser::{Combinator, Component};
17use selectors::OpaqueElement;
18use smallvec::SmallVec;
19use std::fmt;
20use std::fmt::Write;
21
22struct SiblingInfo<E>
23where
24    E: TElement,
25{
26    affected: E,
27    prev_sibling: Option<E>,
28    next_sibling: Option<E>,
29}
30
31/// Traversal mapping for elements under consideration. It acts like a snapshot map,
32/// though this only "maps" one element at most.
33/// For general invalidations, this has no effect, especially since when
34/// DOM mutates, the mutation's effect should not escape the subtree being mutated.
35/// This is not the case for relative selectors, unfortunately, so we may end up
36/// traversing a portion of the DOM tree that mutated. In case the mutation is removal,
37/// its sibling relation is severed by the time the invalidation happens. This structure
38/// recovers that relation. Note - it assumes that there is only one element under this
39/// effect.
40pub struct SiblingTraversalMap<E>
41where
42    E: TElement,
43{
44    info: Option<SiblingInfo<E>>,
45}
46
47impl<E> Default for SiblingTraversalMap<E>
48where
49    E: TElement,
50{
51    fn default() -> Self {
52        Self { info: None }
53    }
54}
55
56impl<E> SiblingTraversalMap<E>
57where
58    E: TElement,
59{
60    /// Create a new traversal map with the affected element.
61    pub fn new(affected: E, prev_sibling: Option<E>, next_sibling: Option<E>) -> Self {
62        Self {
63            info: Some(SiblingInfo {
64                affected,
65                prev_sibling,
66                next_sibling,
67            }),
68        }
69    }
70
71    /// Get the element's previous sibling element.
72    pub fn next_sibling_for(&self, element: &E) -> Option<E> {
73        if let Some(ref info) = self.info {
74            if *element == info.affected {
75                return info.next_sibling;
76            }
77        }
78        element.next_sibling_element()
79    }
80
81    /// Get the element's previous sibling element.
82    pub fn prev_sibling_for(&self, element: &E) -> Option<E> {
83        if let Some(ref info) = self.info {
84            if *element == info.affected {
85                return info.prev_sibling;
86            }
87        }
88        element.prev_sibling_element()
89    }
90}
91
92/// A trait to abstract the collection of invalidations for a given pass.
93pub trait InvalidationProcessor<'a, 'b, E>
94where
95    E: TElement,
96{
97    /// Whether an invalidation that contains only a pseudo-element selector
98    /// like ::before or ::after triggers invalidation of the element that would
99    /// originate it.
100    fn invalidates_on_pseudo_element(&self) -> bool {
101        false
102    }
103
104    /// Whether the invalidation processor only cares about light-tree
105    /// descendants of a given element, that is, doesn't invalidate
106    /// pseudo-elements, NAC, shadow dom...
107    fn light_tree_only(&self) -> bool {
108        false
109    }
110
111    /// When a dependency from a :where or :is selector matches, it may still be
112    /// the case that we don't need to invalidate the full style. Consider the
113    /// case of:
114    ///
115    ///   div .foo:where(.bar *, .baz) .qux
116    ///
117    /// We can get to the `*` part after a .bar class change, but you only need
118    /// to restyle the element if it also matches .foo.
119    ///
120    /// Similarly, you only need to restyle .baz if the whole result of matching
121    /// the selector changes.
122    ///
123    /// This function is called to check the result of matching the "outer"
124    /// dependency that we generate for the parent of the `:where` selector,
125    /// that is, in the case above it should match
126    /// `div .foo:where(.bar *, .baz)`.
127    ///
128    /// Returning true unconditionally here is over-optimistic and may
129    /// over-invalidate.
130    fn check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool;
131
132    /// The matching context that should be used to process invalidations.
133    fn matching_context(&mut self) -> &mut MatchingContext<'b, E::Impl>;
134
135    /// The traversal map that should be used to process invalidations.
136    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E>;
137
138    /// Collect invalidations for a given element's descendants and siblings.
139    ///
140    /// Returns whether the element itself was invalidated.
141    fn collect_invalidations(
142        &mut self,
143        element: E,
144        self_invalidations: &mut InvalidationVector<'a>,
145        descendant_invalidations: &mut DescendantInvalidationLists<'a>,
146        sibling_invalidations: &mut InvalidationVector<'a>,
147    ) -> bool;
148
149    /// Returns whether the invalidation process should process the descendants
150    /// of the given element.
151    fn should_process_descendants(&mut self, element: E) -> bool;
152
153    /// Executes an arbitrary action when the recursion limit is exceded (if
154    /// any).
155    fn recursion_limit_exceeded(&mut self, element: E);
156
157    /// Executes an action when `Self` is invalidated.
158    fn invalidated_self(&mut self, element: E);
159
160    /// Executes an action when `sibling` is invalidated as a sibling of
161    /// `of`.
162    fn invalidated_sibling(&mut self, sibling: E, of: E);
163
164    /// Executes an action when any descendant of `Self` is invalidated.
165    fn invalidated_descendants(&mut self, element: E, child: E);
166
167    /// Executes an action when an element in a relative selector is reached.
168    /// Lets the dependency to be borrowed for further processing out of the
169    /// invalidation traversal.
170    fn found_relative_selector_invalidation(
171        &mut self,
172        _element: E,
173        _kind: RelativeDependencyInvalidationKind,
174        _relative_dependency: &'a Dependency,
175    ) {
176        debug_assert!(false, "Reached relative selector dependency");
177    }
178}
179
180/// Different invalidation lists for descendants.
181#[derive(Debug, Default)]
182pub struct DescendantInvalidationLists<'a> {
183    /// Invalidations for normal DOM children and pseudo-elements.
184    ///
185    /// TODO(emilio): Having a list of invalidations just for pseudo-elements
186    /// may save some work here and there.
187    pub dom_descendants: InvalidationVector<'a>,
188    /// Invalidations for slotted children of an element.
189    pub slotted_descendants: InvalidationVector<'a>,
190    /// Invalidations for ::part()s of an element.
191    pub parts: InvalidationVector<'a>,
192}
193
194impl<'a> DescendantInvalidationLists<'a> {
195    fn is_empty(&self) -> bool {
196        self.dom_descendants.is_empty()
197            && self.slotted_descendants.is_empty()
198            && self.parts.is_empty()
199    }
200}
201
202/// The struct that takes care of encapsulating all the logic on where and how
203/// element styles need to be invalidated.
204pub struct TreeStyleInvalidator<'a, 'b, 'c, E, P: 'a>
205where
206    'b: 'a,
207    E: TElement,
208    P: InvalidationProcessor<'b, 'c, E>,
209{
210    element: E,
211    stack_limit_checker: Option<&'a StackLimitChecker>,
212    processor: &'a mut P,
213    _marker: std::marker::PhantomData<(&'b (), &'c ())>,
214}
215
216/// A vector of invalidations, optimized for small invalidation sets.
217pub type InvalidationVector<'a> = SmallVec<[Invalidation<'a>; 10]>;
218
219/// The kind of descendant invalidation we're processing.
220#[derive(Clone, Copy, Debug, Eq, PartialEq)]
221enum DescendantInvalidationKind {
222    /// A DOM descendant invalidation.
223    Dom,
224    /// A ::slotted() descendant invalidation.
225    Slotted,
226    /// A ::part() descendant invalidation.
227    Part,
228}
229
230/// The kind of invalidation we're processing.
231///
232/// We can use this to avoid pushing invalidations of the same kind to our
233/// descendants or siblings.
234#[derive(Clone, Copy, Debug, Eq, PartialEq)]
235enum InvalidationKind {
236    Descendant(DescendantInvalidationKind),
237    Sibling,
238}
239
240/// An `Invalidation` is a complex selector that describes which elements,
241/// relative to a current element we are processing, must be restyled.
242#[derive(Clone)]
243pub struct Invalidation<'a> {
244    /// The dependency that generated this invalidation.
245    ///
246    /// Note that the offset inside the dependency is not really useful after
247    /// construction.
248    dependency: &'a Dependency,
249    /// The right shadow host from where the rule came from, if any.
250    ///
251    /// This is needed to ensure that we match the selector with the right
252    /// state, as whether some selectors like :host and ::part() match depends
253    /// on it.
254    scope: Option<OpaqueElement>,
255    /// The offset of the selector pointing to a compound selector.
256    ///
257    /// This order is a "parse order" offset, that is, zero is the leftmost part
258    /// of the selector written as parsed / serialized.
259    ///
260    /// It is initialized from the offset from `dependency`.
261    offset: usize,
262    /// Whether the invalidation was already matched by any previous sibling or
263    /// ancestor.
264    ///
265    /// If this is the case, we can avoid pushing invalidations generated by
266    /// this one if the generated invalidation is effective for all the siblings
267    /// or descendants after us.
268    matched_by_any_previous: bool,
269}
270
271impl<'a> Invalidation<'a> {
272    /// Create a new invalidation for matching a dependency.
273    pub fn new(dependency: &'a Dependency, scope: Option<OpaqueElement>) -> Self {
274        debug_assert!(
275            dependency.selector_offset == dependency.selector.len() + 1
276                || dependency.normal_invalidation_kind()
277                    != NormalDependencyInvalidationKind::Element,
278            "No point to this, if the dependency matched the element we should just invalidate it"
279        );
280        Self {
281            dependency,
282            scope,
283            // + 1 to go past the combinator.
284            offset: dependency.selector.len() + 1 - dependency.selector_offset,
285            matched_by_any_previous: false,
286        }
287    }
288
289    /// Whether this invalidation is effective for the next sibling or
290    /// descendant after us.
291    fn effective_for_next(&self) -> bool {
292        if self.offset == 0 {
293            return true;
294        }
295
296        // TODO(emilio): For pseudo-elements this should be mostly false, except
297        // for the weird pseudos in <input type="number">.
298        //
299        // We should be able to do better here!
300        match self
301            .dependency
302            .selector
303            .combinator_at_parse_order(self.offset - 1)
304        {
305            Combinator::Descendant | Combinator::LaterSibling | Combinator::PseudoElement => true,
306            Combinator::Part
307            | Combinator::SlotAssignment
308            | Combinator::NextSibling
309            | Combinator::Child => false,
310        }
311    }
312
313    fn kind(&self) -> InvalidationKind {
314        if self.offset == 0 {
315            return InvalidationKind::Descendant(DescendantInvalidationKind::Dom);
316        }
317
318        match self
319            .dependency
320            .selector
321            .combinator_at_parse_order(self.offset - 1)
322        {
323            Combinator::Child | Combinator::Descendant | Combinator::PseudoElement => {
324                InvalidationKind::Descendant(DescendantInvalidationKind::Dom)
325            },
326            Combinator::Part => InvalidationKind::Descendant(DescendantInvalidationKind::Part),
327            Combinator::SlotAssignment => {
328                InvalidationKind::Descendant(DescendantInvalidationKind::Slotted)
329            },
330            Combinator::NextSibling | Combinator::LaterSibling => InvalidationKind::Sibling,
331        }
332    }
333}
334
335impl<'a> fmt::Debug for Invalidation<'a> {
336    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
337        use cssparser::ToCss;
338
339        f.write_str("Invalidation(")?;
340        for component in self
341            .dependency
342            .selector
343            .iter_raw_parse_order_from(self.offset)
344        {
345            if matches!(*component, Component::Combinator(..)) {
346                break;
347            }
348            component.to_css(f)?;
349        }
350        f.write_char(')')
351    }
352}
353
354/// The result of processing a single invalidation for a given element.
355struct SingleInvalidationResult {
356    /// Whether the element itself was invalidated.
357    invalidated_self: bool,
358    /// Whether the invalidation matched, either invalidating the element or
359    /// generating another invalidation.
360    matched: bool,
361}
362
363/// The result of a whole invalidation process for a given element.
364pub struct InvalidationResult {
365    /// Whether the element itself was invalidated.
366    invalidated_self: bool,
367    /// Whether the element's descendants were invalidated.
368    invalidated_descendants: bool,
369    /// Whether the element's siblings were invalidated.
370    invalidated_siblings: bool,
371}
372
373impl InvalidationResult {
374    /// Create an emtpy result.
375    pub fn empty() -> Self {
376        Self {
377            invalidated_self: false,
378            invalidated_descendants: false,
379            invalidated_siblings: false,
380        }
381    }
382
383    /// Whether the invalidation has invalidate the element itself.
384    pub fn has_invalidated_self(&self) -> bool {
385        self.invalidated_self
386    }
387
388    /// Whether the invalidation has invalidate desendants.
389    pub fn has_invalidated_descendants(&self) -> bool {
390        self.invalidated_descendants
391    }
392
393    /// Whether the invalidation has invalidate siblings.
394    pub fn has_invalidated_siblings(&self) -> bool {
395        self.invalidated_siblings
396    }
397}
398
399impl<'a, 'b, 'c, E, P: 'a> TreeStyleInvalidator<'a, 'b, 'c, E, P>
400where
401    'b: 'a,
402    E: TElement,
403    P: InvalidationProcessor<'b, 'c, E>,
404{
405    /// Trivially constructs a new `TreeStyleInvalidator`.
406    pub fn new(
407        element: E,
408        stack_limit_checker: Option<&'a StackLimitChecker>,
409        processor: &'a mut P,
410    ) -> Self {
411        Self {
412            element,
413            stack_limit_checker,
414            processor,
415            _marker: std::marker::PhantomData,
416        }
417    }
418
419    /// Perform the invalidation pass.
420    pub fn invalidate(mut self) -> InvalidationResult {
421        debug!("StyleTreeInvalidator::invalidate({:?})", self.element);
422
423        let mut self_invalidations = InvalidationVector::new();
424        let mut descendant_invalidations = DescendantInvalidationLists::default();
425        let mut sibling_invalidations = InvalidationVector::new();
426
427        let mut invalidated_self = self.processor.collect_invalidations(
428            self.element,
429            &mut self_invalidations,
430            &mut descendant_invalidations,
431            &mut sibling_invalidations,
432        );
433
434        debug!("Collected invalidations (self: {}): ", invalidated_self);
435        debug!(
436            " > self: {}, {:?}",
437            self_invalidations.len(),
438            self_invalidations
439        );
440        debug!(" > descendants: {:?}", descendant_invalidations);
441        debug!(
442            " > siblings: {}, {:?}",
443            sibling_invalidations.len(),
444            sibling_invalidations
445        );
446
447        let invalidated_self_from_collection = invalidated_self;
448
449        invalidated_self |= self.process_descendant_invalidations(
450            &self_invalidations,
451            &mut descendant_invalidations,
452            &mut sibling_invalidations,
453            DescendantInvalidationKind::Dom,
454        );
455
456        if invalidated_self && !invalidated_self_from_collection {
457            self.processor.invalidated_self(self.element);
458        }
459
460        let invalidated_descendants = self.invalidate_descendants(&descendant_invalidations);
461        let invalidated_siblings = self.invalidate_siblings(&mut sibling_invalidations);
462
463        InvalidationResult {
464            invalidated_self,
465            invalidated_descendants,
466            invalidated_siblings,
467        }
468    }
469
470    /// Go through later DOM siblings, invalidating style as needed using the
471    /// `sibling_invalidations` list.
472    ///
473    /// Returns whether any sibling's style or any sibling descendant's style
474    /// was invalidated.
475    fn invalidate_siblings(&mut self, sibling_invalidations: &mut InvalidationVector<'b>) -> bool {
476        if sibling_invalidations.is_empty() {
477            return false;
478        }
479
480        let mut current = self
481            .processor
482            .sibling_traversal_map()
483            .next_sibling_for(&self.element);
484        let mut any_invalidated = false;
485
486        while let Some(sibling) = current {
487            let mut sibling_invalidator =
488                TreeStyleInvalidator::new(sibling, self.stack_limit_checker, self.processor);
489
490            let mut invalidations_for_descendants = DescendantInvalidationLists::default();
491            let invalidated_sibling = sibling_invalidator.process_sibling_invalidations(
492                &mut invalidations_for_descendants,
493                sibling_invalidations,
494            );
495
496            if invalidated_sibling {
497                sibling_invalidator
498                    .processor
499                    .invalidated_sibling(sibling, self.element);
500            }
501
502            any_invalidated |= invalidated_sibling;
503
504            any_invalidated |=
505                sibling_invalidator.invalidate_descendants(&invalidations_for_descendants);
506
507            if sibling_invalidations.is_empty() {
508                break;
509            }
510
511            current = self
512                .processor
513                .sibling_traversal_map()
514                .next_sibling_for(&sibling);
515        }
516
517        any_invalidated
518    }
519
520    fn invalidate_pseudo_element_or_nac(
521        &mut self,
522        child: E,
523        invalidations: &[Invalidation<'b>],
524    ) -> bool {
525        let mut sibling_invalidations = InvalidationVector::new();
526
527        let result = self.invalidate_child(
528            child,
529            invalidations,
530            &mut sibling_invalidations,
531            DescendantInvalidationKind::Dom,
532        );
533
534        // Roots of NAC subtrees can indeed generate sibling invalidations, but
535        // they can be just ignored, since they have no siblings.
536        //
537        // Note that we can end up testing selectors that wouldn't end up
538        // matching due to this being NAC, like those coming from document
539        // rules, but we overinvalidate instead of checking this.
540
541        result
542    }
543
544    /// Invalidate a child and recurse down invalidating its descendants if
545    /// needed.
546    fn invalidate_child(
547        &mut self,
548        child: E,
549        invalidations: &[Invalidation<'b>],
550        sibling_invalidations: &mut InvalidationVector<'b>,
551        descendant_invalidation_kind: DescendantInvalidationKind,
552    ) -> bool {
553        let mut invalidations_for_descendants = DescendantInvalidationLists::default();
554
555        let mut invalidated_child = false;
556        let invalidated_descendants = {
557            let mut child_invalidator =
558                TreeStyleInvalidator::new(child, self.stack_limit_checker, self.processor);
559
560            invalidated_child |= child_invalidator.process_sibling_invalidations(
561                &mut invalidations_for_descendants,
562                sibling_invalidations,
563            );
564
565            invalidated_child |= child_invalidator.process_descendant_invalidations(
566                invalidations,
567                &mut invalidations_for_descendants,
568                sibling_invalidations,
569                descendant_invalidation_kind,
570            );
571
572            if invalidated_child {
573                child_invalidator.processor.invalidated_self(child);
574            }
575
576            child_invalidator.invalidate_descendants(&invalidations_for_descendants)
577        };
578
579        // The child may not be a flattened tree child of the current element,
580        // but may be arbitrarily deep.
581        //
582        // Since we keep the traversal flags in terms of the flattened tree,
583        // we need to propagate it as appropriate.
584        if invalidated_child || invalidated_descendants {
585            self.processor.invalidated_descendants(self.element, child);
586        }
587
588        invalidated_child || invalidated_descendants
589    }
590
591    fn invalidate_nac(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
592        let mut any_nac_root = false;
593
594        let element = self.element;
595        element.each_anonymous_content_child(|nac| {
596            any_nac_root |= self.invalidate_pseudo_element_or_nac(nac, invalidations);
597        });
598
599        any_nac_root
600    }
601
602    // NB: It's important that this operates on DOM children, which is what
603    // selector-matching operates on.
604    fn invalidate_dom_descendants_of(
605        &mut self,
606        parent: E::ConcreteNode,
607        invalidations: &[Invalidation<'b>],
608    ) -> bool {
609        let mut any_descendant = false;
610
611        let mut sibling_invalidations = InvalidationVector::new();
612        for child in parent.dom_children() {
613            let child = match child.as_element() {
614                Some(e) => e,
615                None => continue,
616            };
617
618            any_descendant |= self.invalidate_child(
619                child,
620                invalidations,
621                &mut sibling_invalidations,
622                DescendantInvalidationKind::Dom,
623            );
624        }
625
626        any_descendant
627    }
628
629    fn invalidate_parts_in_shadow_tree(
630        &mut self,
631        shadow: <E::ConcreteNode as TNode>::ConcreteShadowRoot,
632        invalidations: &[Invalidation<'b>],
633    ) -> bool {
634        debug_assert!(!invalidations.is_empty());
635
636        let mut any = false;
637        let mut sibling_invalidations = InvalidationVector::new();
638
639        for node in shadow.as_node().dom_descendants() {
640            let element = match node.as_element() {
641                Some(e) => e,
642                None => continue,
643            };
644
645            if element.has_part_attr() {
646                any |= self.invalidate_child(
647                    element,
648                    invalidations,
649                    &mut sibling_invalidations,
650                    DescendantInvalidationKind::Part,
651                );
652                debug_assert!(
653                    sibling_invalidations.is_empty(),
654                    "::part() shouldn't have sibling combinators to the right, \
655                     this makes no sense! {:?}",
656                    sibling_invalidations
657                );
658            }
659
660            if let Some(shadow) = element.shadow_root() {
661                if element.exports_any_part() {
662                    any |= self.invalidate_parts_in_shadow_tree(shadow, invalidations)
663                }
664            }
665        }
666
667        any
668    }
669
670    fn invalidate_parts(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
671        if invalidations.is_empty() {
672            return false;
673        }
674
675        let shadow = match self.element.shadow_root() {
676            Some(s) => s,
677            None => return false,
678        };
679
680        self.invalidate_parts_in_shadow_tree(shadow, invalidations)
681    }
682
683    fn invalidate_slotted_elements(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
684        if invalidations.is_empty() {
685            return false;
686        }
687
688        let slot = self.element;
689        self.invalidate_slotted_elements_in_slot(slot, invalidations)
690    }
691
692    fn invalidate_slotted_elements_in_slot(
693        &mut self,
694        slot: E,
695        invalidations: &[Invalidation<'b>],
696    ) -> bool {
697        let mut any = false;
698
699        let mut sibling_invalidations = InvalidationVector::new();
700        for node in slot.slotted_nodes() {
701            let element = match node.as_element() {
702                Some(e) => e,
703                None => continue,
704            };
705
706            if element.is_html_slot_element() {
707                any |= self.invalidate_slotted_elements_in_slot(element, invalidations);
708            } else {
709                any |= self.invalidate_child(
710                    element,
711                    invalidations,
712                    &mut sibling_invalidations,
713                    DescendantInvalidationKind::Slotted,
714                );
715            }
716
717            debug_assert!(
718                sibling_invalidations.is_empty(),
719                "::slotted() shouldn't have sibling combinators to the right, \
720                 this makes no sense! {:?}",
721                sibling_invalidations
722            );
723        }
724
725        any
726    }
727
728    fn invalidate_non_slotted_descendants(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
729        if invalidations.is_empty() {
730            return false;
731        }
732
733        if self.processor.light_tree_only() {
734            let node = self.element.as_node();
735            return self.invalidate_dom_descendants_of(node, invalidations);
736        }
737
738        let mut any_descendant = false;
739
740        // NOTE(emilio): This is only needed for Shadow DOM to invalidate
741        // correctly on :host(..) changes. Instead of doing this, we could add
742        // a third kind of invalidation list that walks shadow root children,
743        // but it's not clear it's worth it.
744        //
745        // Also, it's needed as of right now for document state invalidation,
746        // where we rely on iterating every element that ends up in the composed
747        // doc, but we could fix that invalidating per subtree.
748        if let Some(root) = self.element.shadow_root() {
749            any_descendant |= self.invalidate_dom_descendants_of(root.as_node(), invalidations);
750        }
751
752        any_descendant |= self.invalidate_dom_descendants_of(self.element.as_node(), invalidations);
753
754        any_descendant |= self.invalidate_nac(invalidations);
755
756        any_descendant
757    }
758
759    /// Given the descendant invalidation lists, go through the current
760    /// element's descendants, and invalidate style on them.
761    fn invalidate_descendants(&mut self, invalidations: &DescendantInvalidationLists<'b>) -> bool {
762        if invalidations.is_empty() {
763            return false;
764        }
765
766        debug!(
767            "StyleTreeInvalidator::invalidate_descendants({:?})",
768            self.element
769        );
770        debug!(" > {:?}", invalidations);
771
772        let should_process = self.processor.should_process_descendants(self.element);
773
774        if !should_process {
775            return false;
776        }
777
778        if let Some(checker) = self.stack_limit_checker {
779            if checker.limit_exceeded() {
780                self.processor.recursion_limit_exceeded(self.element);
781                return true;
782            }
783        }
784
785        let mut any_descendant = false;
786
787        any_descendant |= self.invalidate_non_slotted_descendants(&invalidations.dom_descendants);
788        any_descendant |= self.invalidate_slotted_elements(&invalidations.slotted_descendants);
789        any_descendant |= self.invalidate_parts(&invalidations.parts);
790
791        any_descendant
792    }
793
794    /// Process the given sibling invalidations coming from our previous
795    /// sibling.
796    ///
797    /// The sibling invalidations are somewhat special because they can be
798    /// modified on the fly. New invalidations may be added and removed.
799    ///
800    /// In particular, all descendants get the same set of invalidations from
801    /// the parent, but the invalidations from a given sibling depend on the
802    /// ones we got from the previous one.
803    ///
804    /// Returns whether invalidated the current element's style.
805    fn process_sibling_invalidations(
806        &mut self,
807        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
808        sibling_invalidations: &mut InvalidationVector<'b>,
809    ) -> bool {
810        let mut i = 0;
811        let mut new_sibling_invalidations = InvalidationVector::new();
812        let mut invalidated_self = false;
813
814        while i < sibling_invalidations.len() {
815            let result = self.process_invalidation(
816                &sibling_invalidations[i],
817                descendant_invalidations,
818                &mut new_sibling_invalidations,
819                InvalidationKind::Sibling,
820            );
821
822            invalidated_self |= result.invalidated_self;
823            sibling_invalidations[i].matched_by_any_previous |= result.matched;
824            if sibling_invalidations[i].effective_for_next() {
825                i += 1;
826            } else {
827                sibling_invalidations.remove(i);
828            }
829        }
830
831        sibling_invalidations.extend(new_sibling_invalidations.drain(..));
832        invalidated_self
833    }
834
835    /// Process a given invalidation list coming from our parent,
836    /// adding to `descendant_invalidations` and `sibling_invalidations` as
837    /// needed.
838    ///
839    /// Returns whether our style was invalidated as a result.
840    fn process_descendant_invalidations(
841        &mut self,
842        invalidations: &[Invalidation<'b>],
843        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
844        sibling_invalidations: &mut InvalidationVector<'b>,
845        descendant_invalidation_kind: DescendantInvalidationKind,
846    ) -> bool {
847        let mut invalidated = false;
848
849        for invalidation in invalidations {
850            let result = self.process_invalidation(
851                invalidation,
852                descendant_invalidations,
853                sibling_invalidations,
854                InvalidationKind::Descendant(descendant_invalidation_kind),
855            );
856
857            invalidated |= result.invalidated_self;
858            if invalidation.effective_for_next() {
859                let mut invalidation = invalidation.clone();
860                invalidation.matched_by_any_previous |= result.matched;
861                debug_assert_eq!(
862                    descendant_invalidation_kind,
863                    DescendantInvalidationKind::Dom,
864                    "Slotted or part invalidations don't propagate."
865                );
866                descendant_invalidations.dom_descendants.push(invalidation);
867            }
868        }
869
870        invalidated
871    }
872
873    /// Processes a given invalidation, potentially invalidating the style of
874    /// the current element.
875    ///
876    /// Returns whether invalidated the style of the element, and whether the
877    /// invalidation should be effective to subsequent siblings or descendants
878    /// down in the tree.
879    fn process_invalidation(
880        &mut self,
881        invalidation: &Invalidation<'b>,
882        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
883        sibling_invalidations: &mut InvalidationVector<'b>,
884        invalidation_kind: InvalidationKind,
885    ) -> SingleInvalidationResult {
886        debug!(
887            "TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})",
888            self.element, invalidation, invalidation_kind
889        );
890
891        let matching_result = {
892            let context = self.processor.matching_context();
893            context.current_host = invalidation.scope;
894
895            matches_compound_selector_from(
896                &invalidation.dependency.selector,
897                invalidation.offset,
898                context,
899                &self.element,
900            )
901        };
902
903        let next_invalidation = match matching_result {
904            CompoundSelectorMatchingResult::NotMatched => {
905                return SingleInvalidationResult {
906                    invalidated_self: false,
907                    matched: false,
908                }
909            },
910            CompoundSelectorMatchingResult::FullyMatched => {
911                debug!(" > Invalidation matched completely");
912                // We matched completely. If we're an inner selector now we need
913                // to go outside our selector and carry on invalidating.
914                let mut cur_dependency = invalidation.dependency;
915                loop {
916                    cur_dependency = match cur_dependency.next {
917                        None => {
918                            return SingleInvalidationResult {
919                                invalidated_self: true,
920                                matched: true,
921                            }
922                        },
923                        Some(ref deps) => {
924                            let n = &deps.as_ref().slice()[0];
925                            let invalidation_kind = n.invalidation_kind();
926                            match invalidation_kind {
927                                DependencyInvalidationKind::FullSelector => unreachable!(),
928                                DependencyInvalidationKind::Normal(_) => n,
929                                DependencyInvalidationKind::Relative(kind) => {
930                                    self.processor.found_relative_selector_invalidation(
931                                        self.element,
932                                        kind,
933                                        n,
934                                    );
935                                    return SingleInvalidationResult {
936                                        invalidated_self: false,
937                                        matched: true,
938                                    };
939                                },
940                            }
941                        },
942                    };
943
944                    debug!(" > Checking outer dependency {:?}", cur_dependency);
945
946                    // The inner selector changed, now check if the full
947                    // previous part of the selector did, before keeping
948                    // checking for descendants.
949                    if !self
950                        .processor
951                        .check_outer_dependency(cur_dependency, self.element)
952                    {
953                        return SingleInvalidationResult {
954                            invalidated_self: false,
955                            matched: false,
956                        };
957                    }
958
959                    if cur_dependency.normal_invalidation_kind()
960                        == NormalDependencyInvalidationKind::Element
961                    {
962                        continue;
963                    }
964
965                    debug!(" > Generating invalidation");
966                    break Invalidation::new(cur_dependency, invalidation.scope);
967                }
968            },
969            CompoundSelectorMatchingResult::Matched {
970                next_combinator_offset,
971            } => Invalidation {
972                dependency: invalidation.dependency,
973                scope: invalidation.scope,
974                offset: next_combinator_offset + 1,
975                matched_by_any_previous: false,
976            },
977        };
978
979        debug_assert_ne!(
980            next_invalidation.offset, 0,
981            "Rightmost selectors shouldn't generate more invalidations",
982        );
983
984        let mut invalidated_self = false;
985        let next_combinator = next_invalidation
986            .dependency
987            .selector
988            .combinator_at_parse_order(next_invalidation.offset - 1);
989
990        if matches!(next_combinator, Combinator::PseudoElement)
991            && self.processor.invalidates_on_pseudo_element()
992        {
993            // We need to invalidate the element whenever pseudos change, for
994            // two reasons:
995            //
996            //  * Eager pseudo styles are stored as part of the originating
997            //    element's computed style.
998            //
999            //  * Lazy pseudo-styles might be cached on the originating
1000            //    element's pseudo-style cache.
1001            //
1002            // This could be more fine-grained (perhaps with a RESTYLE_PSEUDOS
1003            // hint?).
1004            //
1005            // Note that we'll also restyle the pseudo-element because it would
1006            // match this invalidation.
1007            //
1008            // FIXME: For non-element-backed pseudos this is still not quite
1009            // correct. For example for ::selection even though we invalidate
1010            // the style properly there's nothing that triggers a repaint
1011            // necessarily. Though this matches old Gecko behavior, and the
1012            // ::selection implementation needs to change significantly anyway
1013            // to implement https://github.com/w3c/csswg-drafts/issues/2474 for
1014            // example.
1015            invalidated_self = true;
1016        }
1017
1018        debug!(
1019            " > Invalidation matched, next: {:?}, ({:?})",
1020            next_invalidation, next_combinator
1021        );
1022
1023        let next_invalidation_kind = next_invalidation.kind();
1024
1025        // We can skip pushing under some circumstances, and we should
1026        // because otherwise the invalidation list could grow
1027        // exponentially.
1028        //
1029        //  * First of all, both invalidations need to be of the same
1030        //    kind. This is because of how we propagate them going to
1031        //    the right of the tree for sibling invalidations and going
1032        //    down the tree for children invalidations. A sibling
1033        //    invalidation that ends up generating a children
1034        //    invalidation ends up (correctly) in five different lists,
1035        //    not in the same list five different times.
1036        //
1037        //  * Then, the invalidation needs to be matched by a previous
1038        //    ancestor/sibling, in order to know that this invalidation
1039        //    has been generated already.
1040        //
1041        //  * Finally, the new invalidation needs to be
1042        //    `effective_for_next()`, in order for us to know that it is
1043        //    still in the list, since we remove the dependencies that
1044        //    aren't from the lists for our children / siblings.
1045        //
1046        // To go through an example, let's imagine we are processing a
1047        // dom subtree like:
1048        //
1049        //   <div><address><div><div/></div></address></div>
1050        //
1051        // And an invalidation list with a single invalidation like:
1052        //
1053        //   [div div div]
1054        //
1055        // When we process the invalidation list for the outer div, we
1056        // match it, and generate a `div div` invalidation, so for the
1057        // <address> child we have:
1058        //
1059        //   [div div div, div div]
1060        //
1061        // With the first of them marked as `matched`.
1062        //
1063        // When we process the <address> child, we don't match any of
1064        // them, so both invalidations go untouched to our children.
1065        //
1066        // When we process the second <div>, we match _both_
1067        // invalidations.
1068        //
1069        // However, when matching the first, we can tell it's been
1070        // matched, and not push the corresponding `div div`
1071        // invalidation, since we know it's necessarily already on the
1072        // list.
1073        //
1074        // Thus, without skipping the push, we'll arrive to the
1075        // innermost <div> with:
1076        //
1077        //   [div div div, div div, div div, div]
1078        //
1079        // While skipping it, we won't arrive here with duplicating
1080        // dependencies:
1081        //
1082        //   [div div div, div div, div]
1083        //
1084        let can_skip_pushing = next_invalidation_kind == invalidation_kind
1085            && invalidation.matched_by_any_previous
1086            && next_invalidation.effective_for_next();
1087
1088        if can_skip_pushing {
1089            debug!(
1090                " > Can avoid push, since the invalidation had \
1091                 already been matched before"
1092            );
1093        } else {
1094            match next_invalidation_kind {
1095                InvalidationKind::Descendant(DescendantInvalidationKind::Dom) => {
1096                    descendant_invalidations
1097                        .dom_descendants
1098                        .push(next_invalidation);
1099                },
1100                InvalidationKind::Descendant(DescendantInvalidationKind::Part) => {
1101                    descendant_invalidations.parts.push(next_invalidation);
1102                },
1103                InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) => {
1104                    descendant_invalidations
1105                        .slotted_descendants
1106                        .push(next_invalidation);
1107                },
1108                InvalidationKind::Sibling => {
1109                    sibling_invalidations.push(next_invalidation);
1110                },
1111            }
1112        }
1113
1114        SingleInvalidationResult {
1115            invalidated_self,
1116            matched: true,
1117        }
1118    }
1119}