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