style/invalidation/element/
invalidation_map.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//! Code for invalidations due to state or attribute changes.
6
7use crate::AllocErr;
8use crate::context::QuirksMode;
9use crate::derives::*;
10use crate::selector_map::{
11    MaybeCaseInsensitiveHashMap, PrecomputedHashMap, SelectorMap, SelectorMapEntry,
12};
13use crate::selector_parser::{NonTSPseudoClass, SelectorImpl};
14use crate::values::AtomIdent;
15use crate::{Atom, LocalName, Namespace, ShrinkIfNeeded};
16use dom::{DocumentState, ElementState};
17use selectors::attr::NamespaceConstraint;
18use selectors::parser::{
19    Combinator, Component, RelativeSelector, RelativeSelectorCombinatorCount,
20    RelativeSelectorMatchHint,
21};
22use selectors::parser::{Selector, SelectorIter};
23use selectors::visitor::{SelectorListKind, SelectorVisitor};
24use servo_arc::ThinArc;
25use smallvec::SmallVec;
26
27/// Mapping between (partial) CompoundSelectors (and the combinator to their
28/// right) and the states and attributes they depend on.
29///
30/// In general, for all selectors in all applicable stylesheets of the form:
31///
32/// |a _ b _ c _ d _ e|
33///
34/// Where:
35///   * |b| and |d| are simple selectors that depend on state (like :hover) or
36///     attributes (like [attr...], .foo, or #foo).
37///   * |a|, |c|, and |e| are arbitrary simple selectors that do not depend on
38///     state or attributes.
39///
40/// We generate a Dependency for both |a _ b:X _| and |a _ b:X _ c _ d:Y _|,
41/// even though those selectors may not appear on their own in any stylesheet.
42/// This allows us to quickly scan through the dependency sites of all style
43/// rules and determine the maximum effect that a given state or attribute
44/// change may have on the style of elements in the document.
45#[derive(Clone, Debug, MallocSizeOf)]
46pub struct Dependency {
47    /// The dependency selector.
48    #[ignore_malloc_size_of = "CssRules have primary refs, we measure there"]
49    pub selector: Selector<SelectorImpl>,
50
51    /// The offset into the selector that we should match on.
52    pub selector_offset: usize,
53
54    /// The next dependency for a selector chain. For example, consider
55    /// the following:
56    ///
57    ///     .foo .bar:where(.baz span) .qux
58    ///         ^               ^     ^
59    ///         A               B     C
60    ///
61    ///  We'd generate:
62    ///
63    ///    * One dependency for .qux (offset: 0, next: None)
64    ///    * One dependency for .baz pointing to B with next being a
65    ///      dependency pointing to C.
66    ///    * One dependency from .bar pointing to C (next: None)
67    ///    * One dependency from .foo pointing to A (next: None)
68    ///
69    /// Scope blocks can add multiple next entries: e.g. With
70    /// @scope (.a) { .b {/*...*/ } .c { /*...*/ }}
71    /// .a's Dependency would have two entries, for .b and .c.
72    #[ignore_malloc_size_of = "Arc"]
73    pub next: Option<ThinArc<(), Dependency>>,
74
75    /// What kind of selector invalidation this generates.
76    kind: DependencyInvalidationKind,
77}
78
79impl SelectorMapEntry for Dependency {
80    fn selector(&self) -> SelectorIter<'_, SelectorImpl> {
81        self.selector.iter_from(self.selector_offset)
82    }
83}
84
85/// The kind of elements down the tree this dependency may affect.
86#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
87pub enum NormalDependencyInvalidationKind {
88    /// This dependency may affect the element that changed itself.
89    Element,
90    /// This dependency affects the style of the element itself, and also the
91    /// style of its descendants.
92    ///
93    /// TODO(emilio): Each time this feels more of a hack for eager pseudos...
94    ElementAndDescendants,
95    /// This dependency may affect descendants down the tree.
96    Descendants,
97    /// This dependency may affect siblings to the right of the element that
98    /// changed.
99    Siblings,
100    /// This dependency may affect slotted elements of the element that changed.
101    SlottedElements,
102    /// This dependency may affect parts of the element that changed.
103    Parts,
104}
105
106/// The kind of elements up the tree this relative selector dependency may
107/// affect. Because this travels upwards, it's not viable for parallel subtree
108/// traversal, and is handled separately.
109#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
110pub enum RelativeDependencyInvalidationKind {
111    /// This dependency may affect relative selector anchors for ancestors.
112    Ancestors,
113    /// This dependency may affect a relative selector anchor for the parent.
114    Parent,
115    /// This dependency may affect a relative selector anchor for the previous sibling.
116    PrevSibling,
117    /// This dependency may affect relative selector anchors for ancestors' previous siblings.
118    AncestorPrevSibling,
119    /// This dependency may affect relative selector anchors for earlier siblings.
120    EarlierSibling,
121    /// This dependency may affect relative selector anchors for ancestors' earlier siblings.
122    AncestorEarlierSibling,
123}
124
125/// The kind of invalidation the subject of this dependency triggers.
126#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
127pub enum ScopeDependencyInvalidationKind {
128    /// This dependency's subject is an explicit scope root
129    ExplicitScope,
130    /// This dependency's subject is an implicit scope root
131    ImplicitScope,
132    /// This dependency's subject is an end scope condition
133    ScopeEnd,
134}
135
136/// Invalidation kind merging normal and relative dependencies.
137#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
138pub enum DependencyInvalidationKind {
139    /// This dependency is for full selector invalidation.
140    /// It is assuumed that there will be no next dependency to look for.
141    FullSelector,
142    /// This dependency is a normal dependency.
143    Normal(NormalDependencyInvalidationKind),
144    /// This dependency is a relative dependency.
145    Relative(RelativeDependencyInvalidationKind),
146    /// This dependency is a scope dependency.
147    Scope(ScopeDependencyInvalidationKind),
148}
149
150/// The type of invalidation a non-relative selector can generate.
151#[derive(Clone, Copy, Debug, MallocSizeOf)]
152pub enum GeneratedInvalidation<'a> {
153    /// Generates a normal invalidation.
154    Normal,
155    /// Generates a scope invalidation.
156    Scope(Option<&'a ThinArc<(), Dependency>>),
157}
158
159/// Return the type of normal invalidation given a selector & an offset.
160#[inline(always)]
161fn get_non_relative_invalidation_kind(
162    selector: &Selector<SelectorImpl>,
163    selector_offset: usize,
164    scope_kind: Option<ScopeDependencyInvalidationKind>,
165) -> DependencyInvalidationKind {
166    if let Some(kind) = scope_kind {
167        return DependencyInvalidationKind::Scope(kind);
168    }
169    if selector_offset == 0 {
170        return DependencyInvalidationKind::Normal(NormalDependencyInvalidationKind::Element);
171    }
172    let combinator = selector.combinator_at_match_order(selector_offset - 1);
173    DependencyInvalidationKind::Normal(match combinator {
174        Combinator::Child | Combinator::Descendant => NormalDependencyInvalidationKind::Descendants,
175        Combinator::LaterSibling | Combinator::NextSibling => {
176            NormalDependencyInvalidationKind::Siblings
177        },
178        Combinator::PseudoElement => NormalDependencyInvalidationKind::ElementAndDescendants,
179        Combinator::SlotAssignment => NormalDependencyInvalidationKind::SlottedElements,
180        Combinator::Part => NormalDependencyInvalidationKind::Parts,
181    })
182}
183
184impl Dependency {
185    /// Generate a new dependency
186    pub fn new(
187        selector: Selector<SelectorImpl>,
188        selector_offset: usize,
189        next: Option<ThinArc<(), Dependency>>,
190        kind: DependencyInvalidationKind,
191    ) -> Self {
192        Self {
193            selector,
194            selector_offset,
195            next,
196            kind,
197        }
198    }
199    /// Creates a dummy dependency to invalidate the whole selector.
200    ///
201    /// This is necessary because document state invalidation wants to
202    /// invalidate all elements in the document.
203    ///
204    /// The offset is such as that Invalidation::new(self) returns a zero
205    /// offset. That is, it points to a virtual "combinator" outside of the
206    /// selector, so calling combinator() on such a dependency will panic.
207    pub fn for_full_selector_invalidation(selector: Selector<SelectorImpl>) -> Self {
208        Self {
209            selector_offset: selector.len() + 1,
210            selector,
211            next: None,
212            kind: DependencyInvalidationKind::FullSelector,
213        }
214    }
215
216    /// The kind of normal invalidation that this would generate. The dependency
217    /// in question must be a normal dependency.
218    pub fn normal_invalidation_kind(&self) -> NormalDependencyInvalidationKind {
219        if let DependencyInvalidationKind::Normal(kind) = self.kind {
220            return kind;
221        }
222        unreachable!("Querying normal invalidation kind on non-normal dependency.");
223    }
224
225    /// The kind of relative invalidation that this would generate. The dependency
226    /// in question must be a relative dependency.
227    #[inline(always)]
228    pub fn relative_invalidation_kind(&self) -> RelativeDependencyInvalidationKind {
229        if let DependencyInvalidationKind::Relative(kind) = self.kind {
230            return kind;
231        }
232        unreachable!("Querying relative invalidation kind on non-relative dependency.");
233    }
234
235    /// The kind of invalidation that this would generate.
236    pub fn invalidation_kind(&self) -> DependencyInvalidationKind {
237        self.kind
238    }
239
240    /// Is the combinator to the right of this dependency's compound selector
241    /// the next sibling combinator? This matters for insertion/removal in between
242    /// two elements connected through next sibling, e.g. `.foo:has(> .a + .b)`
243    /// where an element gets inserted between `.a` and `.b`.
244    pub fn right_combinator_is_next_sibling(&self) -> bool {
245        if self.selector_offset == 0 {
246            return false;
247        }
248        matches!(
249            self.selector
250                .combinator_at_match_order(self.selector_offset - 1),
251            Combinator::NextSibling
252        )
253    }
254
255    /// Is this dependency's compound selector a single compound in `:has`
256    /// with the next sibling relative combinator i.e. `:has(> .foo)`?
257    /// This matters for insertion between an anchor and an element
258    /// connected through next sibling, e.g. `.a:has(> .b)`.
259    pub fn dependency_is_relative_with_single_next_sibling(&self) -> bool {
260        match self.invalidation_kind() {
261            DependencyInvalidationKind::Relative(kind) => {
262                kind == RelativeDependencyInvalidationKind::PrevSibling
263            },
264            _ => false,
265        }
266    }
267}
268
269/// The same, but for state selectors, which can track more exactly what state
270/// do they track.
271#[derive(Clone, Debug, MallocSizeOf)]
272pub struct StateDependency {
273    /// The other dependency fields.
274    pub dep: Dependency,
275    /// The state this dependency is affected by.
276    pub state: ElementState,
277}
278
279impl SelectorMapEntry for StateDependency {
280    fn selector(&self) -> SelectorIter<'_, SelectorImpl> {
281        self.dep.selector()
282    }
283}
284
285/// The same, but for document state selectors.
286#[derive(Clone, Debug, MallocSizeOf)]
287pub struct DocumentStateDependency {
288    /// We track `Dependency` even though we don't need to track an offset,
289    /// since when it changes it changes for the whole document anyway.
290    #[cfg_attr(
291        feature = "gecko",
292        ignore_malloc_size_of = "CssRules have primary refs, we measure there"
293    )]
294    #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")]
295    pub dependency: Dependency,
296    /// The state this dependency is affected by.
297    pub state: DocumentState,
298}
299
300/// Dependency mapping for classes or IDs.
301pub type IdOrClassDependencyMap = MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>;
302/// Dependency mapping for non-tree-strctural pseudo-class states.
303pub type StateDependencyMap = SelectorMap<StateDependency>;
304/// Dependency mapping for local names.
305pub type LocalNameDependencyMap = PrecomputedHashMap<LocalName, SmallVec<[Dependency; 1]>>;
306/// Dependency mapping for customstates
307pub type CustomStateDependencyMap = PrecomputedHashMap<AtomIdent, SmallVec<[Dependency; 1]>>;
308
309/// A map where we store invalidations.
310///
311/// This is slightly different to a SelectorMap, in the sense of that the same
312/// selector may appear multiple times.
313///
314/// In particular, we want to lookup as few things as possible to get the fewer
315/// selectors the better, so this looks up by id, class, or looks at the list of
316/// state/other attribute affecting selectors.
317#[derive(Clone, Debug, MallocSizeOf)]
318pub struct InvalidationMap {
319    /// A map from a given class name to all the selectors with that class
320    /// selector.
321    pub class_to_selector: IdOrClassDependencyMap,
322    /// A map from a given id to all the selectors with that ID in the
323    /// stylesheets currently applying to the document.
324    pub id_to_selector: IdOrClassDependencyMap,
325    /// A map of all the state dependencies.
326    pub state_affecting_selectors: StateDependencyMap,
327    /// A list of document state dependencies in the rules we represent.
328    pub document_state_selectors: Vec<DocumentStateDependency>,
329    /// A map of other attribute affecting selectors.
330    pub other_attribute_affecting_selectors: LocalNameDependencyMap,
331    /// A map of CSS custom states
332    pub custom_state_affecting_selectors: CustomStateDependencyMap,
333}
334
335/// Tree-structural pseudoclasses that we care about for (Relative selector) invalidation.
336/// Specifically, we need to store information on ones that don't generate the inner selector.
337/// Given the nature of these selectors:
338/// * These are only relevant during DOM mutation invalidations
339/// * Some invalidations may be optimized away.
340#[derive(Clone, Copy, Debug, MallocSizeOf)]
341pub struct TSStateForInvalidation(u8);
342
343bitflags! {
344    impl TSStateForInvalidation : u8 {
345        /// :empty. This only needs to be considered for DOM mutation, and for
346        /// elements that do not have any children.
347        const EMPTY = 1 << 0;
348        /// :nth and related selectors, without of.
349        const NTH = 1 << 1;
350        /// :first-child. This only needs to be considered for DOM mutation, and
351        /// for elements that have no previous sibling.
352        const NTH_EDGE_FIRST = 1 << 2;
353        /// :last-child. This only needs to be considered for DOM mutation,
354        /// and for elements have no next sibling.
355        const NTH_EDGE_LAST = 1 << 3;
356    }
357}
358
359impl TSStateForInvalidation {
360    /// Return true if this state invalidation could be skipped (As per comment
361    /// in the definition of this bitflags)
362    pub fn may_be_optimized(&self) -> bool {
363        (Self::EMPTY | Self::NTH_EDGE_FIRST | Self::NTH_EDGE_LAST).contains(*self)
364    }
365}
366
367/// Dependency for tree-structural pseudo-classes.
368#[derive(Clone, Debug, MallocSizeOf)]
369pub struct TSStateDependency {
370    /// The other dependency fields.
371    pub dep: Dependency,
372    /// The state this dependency is affected by.
373    pub state: TSStateForInvalidation,
374}
375
376impl SelectorMapEntry for TSStateDependency {
377    fn selector(&self) -> SelectorIter<'_, SelectorImpl> {
378        self.dep.selector()
379    }
380}
381
382/// Dependency mapping for tree-structural pseudo-class states.
383pub type TSStateDependencyMap = SelectorMap<TSStateDependency>;
384/// Dependency mapping for * selectors.
385pub type AnyDependencyMap = SmallVec<[Dependency; 1]>;
386
387/// A map to store invalidation dependencies specific to relative selectors.
388/// This keeps a lot more data than the usual map, because any change can generate
389/// upward traversals that need to be handled separately.
390#[derive(Clone, Debug, MallocSizeOf)]
391pub struct AdditionalRelativeSelectorInvalidationMap {
392    /// A map for a given tree-structural pseudo-class to all the relative selector dependencies with that type.
393    pub ts_state_to_selector: TSStateDependencyMap,
394    /// A map from a given type name to all the relative selector dependencies with that type.
395    pub type_to_selector: LocalNameDependencyMap,
396    /// All relative selector dependencies that specify `*`.
397    pub any_to_selector: AnyDependencyMap,
398    /// Flag indicating if any relative selector is used.
399    pub used: bool,
400    /// Flag indicating if invalidating a relative selector requires ancestor traversal.
401    pub needs_ancestors_traversal: bool,
402}
403
404impl Default for AdditionalRelativeSelectorInvalidationMap {
405    fn default() -> Self {
406        Self::new()
407    }
408}
409
410impl AdditionalRelativeSelectorInvalidationMap {
411    /// Creates an empty `InvalidationMap`.
412    pub fn new() -> Self {
413        Self {
414            ts_state_to_selector: TSStateDependencyMap::default(),
415            type_to_selector: LocalNameDependencyMap::default(),
416            any_to_selector: SmallVec::default(),
417            used: false,
418            needs_ancestors_traversal: false,
419        }
420    }
421
422    /// Clears this map, leaving it empty.
423    pub fn clear(&mut self) {
424        self.ts_state_to_selector.clear();
425        self.type_to_selector.clear();
426        self.any_to_selector.clear();
427    }
428
429    /// Shrink the capacity of hash maps if needed.
430    pub fn shrink_if_needed(&mut self) {
431        self.ts_state_to_selector.shrink_if_needed();
432        self.type_to_selector.shrink_if_needed();
433    }
434}
435
436impl Default for InvalidationMap {
437    fn default() -> Self {
438        Self::new()
439    }
440}
441
442impl InvalidationMap {
443    /// Creates an empty `InvalidationMap`.
444    pub fn new() -> Self {
445        Self {
446            class_to_selector: IdOrClassDependencyMap::new(),
447            id_to_selector: IdOrClassDependencyMap::new(),
448            state_affecting_selectors: StateDependencyMap::new(),
449            document_state_selectors: Vec::new(),
450            other_attribute_affecting_selectors: LocalNameDependencyMap::default(),
451            custom_state_affecting_selectors: CustomStateDependencyMap::default(),
452        }
453    }
454
455    /// Returns the number of dependencies stored in the invalidation map.
456    pub fn len(&self) -> usize {
457        self.state_affecting_selectors.len()
458            + self.document_state_selectors.len()
459            + self
460                .other_attribute_affecting_selectors
461                .iter()
462                .fold(0, |accum, (_, v)| accum + v.len())
463            + self
464                .id_to_selector
465                .iter()
466                .fold(0, |accum, (_, v)| accum + v.len())
467            + self
468                .class_to_selector
469                .iter()
470                .fold(0, |accum, (_, v)| accum + v.len())
471            + self
472                .custom_state_affecting_selectors
473                .iter()
474                .fold(0, |accum, (_, v)| accum + v.len())
475    }
476
477    /// Clears this map, leaving it empty.
478    pub fn clear(&mut self) {
479        self.class_to_selector.clear();
480        self.id_to_selector.clear();
481        self.state_affecting_selectors.clear();
482        self.document_state_selectors.clear();
483        self.other_attribute_affecting_selectors.clear();
484        self.custom_state_affecting_selectors.clear();
485    }
486
487    /// Shrink the capacity of hash maps if needed.
488    pub fn shrink_if_needed(&mut self) {
489        self.class_to_selector.shrink_if_needed();
490        self.id_to_selector.shrink_if_needed();
491        self.state_affecting_selectors.shrink_if_needed();
492        self.other_attribute_affecting_selectors.shrink_if_needed();
493        self.custom_state_affecting_selectors.shrink_if_needed();
494    }
495}
496
497/// Adds a selector to the given `InvalidationMap`. Returns Err(..) to signify OOM.
498pub fn note_selector_for_invalidation(
499    selector: &Selector<SelectorImpl>,
500    quirks_mode: QuirksMode,
501    map: &mut InvalidationMap,
502    relative_selector_invalidation_map: &mut InvalidationMap,
503    additional_relative_selector_invalidation_map: &mut AdditionalRelativeSelectorInvalidationMap,
504    inner_scope_dependencies: Option<&ThinArc<(), Dependency>>,
505    scope_kind: Option<ScopeDependencyInvalidationKind>,
506) -> Result<Option<Vec<Dependency>>, AllocErr> {
507    let next_dependency = Dependency::for_full_selector_invalidation(selector.clone());
508    let mut document_state = DocumentState::empty();
509    let mut scope_dependencies = ScopeSelectorCollectorState {
510        inner_dependencies: &inner_scope_dependencies.cloned(),
511        this_dependencies: None,
512        scope_kind,
513    };
514
515    {
516        let mut next_stack = NextSelectors::new();
517        let mut alloc_error = None;
518        let mut collector = SelectorDependencyCollector {
519            map,
520            relative_selector_invalidation_map,
521            additional_relative_selector_invalidation_map,
522            document_state: &mut document_state,
523            selector,
524            next_selectors: &mut next_stack,
525            quirks_mode,
526            compound_state: PerCompoundState::new(0),
527            relative_inner_collector: None,
528            scope_dependencies: &mut scope_dependencies,
529            alloc_error: &mut alloc_error,
530        };
531
532        let visit_result = collector.visit_whole_selector();
533
534        debug_assert_eq!(!visit_result, alloc_error.is_some());
535        if let Some(alloc_error) = alloc_error {
536            return Err(alloc_error);
537        }
538    }
539
540    if !document_state.is_empty() {
541        let dep = DocumentStateDependency {
542            state: document_state,
543            dependency: next_dependency,
544        };
545        map.document_state_selectors.try_reserve(1)?;
546        map.document_state_selectors.push(dep);
547    }
548    Ok(scope_dependencies.this_dependencies)
549}
550
551struct PerCompoundState {
552    /// The offset at which our compound starts.
553    offset: usize,
554
555    /// The state this compound selector is affected by.
556    element_state: ElementState,
557}
558
559impl PerCompoundState {
560    fn new(offset: usize) -> Self {
561        Self {
562            offset,
563            element_state: ElementState::empty(),
564        }
565    }
566}
567
568struct NextDependencyEntry {
569    selector: Selector<SelectorImpl>,
570    offset: usize,
571    cached_dependency: Option<ThinArc<(), Dependency>>,
572}
573
574struct RelativeSelectorInnerCollectorState<'a> {
575    next_dependency: &'a ThinArc<(), Dependency>,
576    relative_compound_state: RelativeSelectorCompoundStateAttributes,
577}
578struct ScopeSelectorCollectorState<'a> {
579    // Inner scope dependencies this scope selector need to point to
580    inner_dependencies: &'a Option<ThinArc<(), Dependency>>,
581    // Scope dependencies added by this scope selector
582    this_dependencies: Option<Vec<Dependency>>,
583    // Whether this dependency is scope start, end, or other.
584    scope_kind: Option<ScopeDependencyInvalidationKind>,
585}
586
587trait Collector {
588    fn dependency(&mut self) -> Dependency;
589    fn id_map(&mut self) -> &mut IdOrClassDependencyMap;
590    fn class_map(&mut self) -> &mut IdOrClassDependencyMap;
591    fn state_map(&mut self) -> &mut StateDependencyMap;
592    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap;
593    fn custom_state_map(&mut self) -> &mut CustomStateDependencyMap;
594    fn inner_scope_dependencies(&self) -> Option<ThinArc<(), Dependency>>;
595    fn this_scope_dependencies(&mut self) -> &mut Option<Vec<Dependency>>;
596    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState);
597
598    // In normal invalidations, type-based dependencies don't need to be explicitly tracked;
599    // elements don't change their types, and mutations cause invalidations to go descendant
600    // (Where they are about to be styled anyway), and/or later-sibling direction (Where they
601    // siblings after inserted/removed elements get restyled anyway).
602    // However, for relative selectors, a DOM mutation can affect and arbitrary ancestor and/or
603    // earlier siblings, so we need to keep track of them.
604    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
605        unreachable!();
606    }
607
608    // Tree-structural pseudo-selectors generally invalidates in a well-defined way, which are
609    // handled by RestyleManager. However, for relative selectors, as with type invalidations,
610    // the direction of invalidation becomes arbitrary, so we need to keep track of them.
611    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
612        unreachable!();
613    }
614
615    // Same story as type invalidation maps.
616    fn any_vec(&mut self) -> &mut AnyDependencyMap {
617        unreachable!();
618    }
619}
620
621fn on_attribute<C: Collector>(
622    local_name: &LocalName,
623    local_name_lower: &LocalName,
624    collector: &mut C,
625) -> Result<(), AllocErr> {
626    add_attr_dependency(local_name, collector)?;
627    if local_name != local_name_lower {
628        add_attr_dependency(local_name_lower, collector)?;
629    }
630    Ok(())
631}
632
633fn on_id_or_class<C: Collector>(
634    s: &Component<SelectorImpl>,
635    quirks_mode: QuirksMode,
636    collector: &mut C,
637) -> Result<(), AllocErr> {
638    let dependency = collector.dependency();
639
640    let (atom, map) = match *s {
641        Component::ID(ref atom) => (atom, collector.id_map()),
642        Component::Class(ref atom) => (atom, collector.class_map()),
643        _ => unreachable!(),
644    };
645    let vec = map.try_get_or_insert_with(&atom.0, quirks_mode, SmallVec::new)?;
646    vec.try_reserve(1)?;
647    vec.push(dependency);
648    Ok(())
649}
650
651fn on_scope<C: Collector>(collector: &mut C) -> Result<(), AllocErr> {
652    let new_dependency = collector.dependency();
653    let this_scope_dependencies = collector.this_scope_dependencies();
654
655    this_scope_dependencies
656        .get_or_insert(Vec::new())
657        .push(new_dependency);
658
659    Ok(())
660}
661
662fn add_attr_dependency<C: Collector>(name: &LocalName, collector: &mut C) -> Result<(), AllocErr> {
663    let dependency = collector.dependency();
664    let map = collector.attribute_map();
665    add_local_name(name, dependency, map)
666}
667
668fn add_custom_state_dependency<C: Collector>(
669    name: &AtomIdent,
670    collector: &mut C,
671) -> Result<(), AllocErr> {
672    let dependency = collector.dependency();
673    let map = collector.custom_state_map();
674    map.try_reserve(1)?;
675    let vec = map.entry_ref(name).or_default();
676    vec.try_reserve(1)?;
677    vec.push(dependency);
678    Ok(())
679}
680
681fn add_local_name(
682    name: &LocalName,
683    dependency: Dependency,
684    map: &mut LocalNameDependencyMap,
685) -> Result<(), AllocErr> {
686    map.try_reserve(1)?;
687    let vec = map.entry_ref(name).or_default();
688    vec.try_reserve(1)?;
689    vec.push(dependency);
690    Ok(())
691}
692
693fn on_pseudo_class<C: Collector>(pc: &NonTSPseudoClass, collector: &mut C) -> Result<(), AllocErr> {
694    collector.update_states(pc.state_flag(), pc.document_state_flag());
695
696    let attr_name = match *pc {
697        #[cfg(feature = "gecko")]
698        NonTSPseudoClass::MozTableBorderNonzero => local_name!("border"),
699        #[cfg(feature = "gecko")]
700        NonTSPseudoClass::MozSelectListBox => {
701            // This depends on two attributes.
702            add_attr_dependency(&local_name!("multiple"), collector)?;
703            return add_attr_dependency(&local_name!("size"), collector);
704        },
705        NonTSPseudoClass::Lang(..) => local_name!("lang"),
706        NonTSPseudoClass::CustomState(ref name) => {
707            return add_custom_state_dependency(&name.0, collector);
708        },
709        _ => return Ok(()),
710    };
711
712    add_attr_dependency(&attr_name, collector)
713}
714
715fn add_pseudo_class_dependency<C: Collector>(
716    element_state: ElementState,
717    quirks_mode: QuirksMode,
718    collector: &mut C,
719) -> Result<(), AllocErr> {
720    if element_state.is_empty() {
721        return Ok(());
722    }
723    let dependency = collector.dependency();
724    collector.state_map().insert(
725        StateDependency {
726            dep: dependency,
727            state: element_state,
728        },
729        quirks_mode,
730    )
731}
732
733/// Visit all the simple selectors in the iter compound
734/// and return the number of simple selectors visited.
735/// We need to return a tuple because we need to keep
736/// track of two things:
737/// 1) Should the traversal continue and
738/// 2) What the offset of the compound state is.
739fn visit_all_in_iter_compound<T: SelectorVisitor<Impl = SelectorImpl>>(
740    visitor: &mut T,
741    iter: &mut SelectorIter<'_, SelectorImpl>,
742) -> (bool, usize) {
743    let mut index = 0;
744    for ss in iter {
745        if !ss.visit(visitor) {
746            return (false, index);
747        }
748        index += 1;
749    }
750    (true, index)
751}
752
753type NextSelectors = SmallVec<[NextDependencyEntry; 5]>;
754
755/// A struct that collects invalidations for a given compound selector.
756struct SelectorDependencyCollector<'a, 'b, 'c> {
757    map: &'a mut InvalidationMap,
758    relative_selector_invalidation_map: &'a mut InvalidationMap,
759    additional_relative_selector_invalidation_map:
760        &'a mut AdditionalRelativeSelectorInvalidationMap,
761
762    /// The document this _complex_ selector is affected by.
763    ///
764    /// We don't need to track state per compound selector, since it's global
765    /// state and it changes for everything.
766    document_state: &'a mut DocumentState,
767
768    /// The current selector and offset we're iterating.
769    selector: &'a Selector<SelectorImpl>,
770
771    /// The stack of next selectors that we have, and at which offset of the
772    /// sequence.
773    ///
774    /// This starts empty. It grows when we find nested :is and :where selector
775    /// lists. The dependency field is cached and reference counted.
776    next_selectors: &'a mut NextSelectors,
777
778    /// The quirks mode of the document where we're inserting dependencies.
779    quirks_mode: QuirksMode,
780
781    /// State relevant to a given compound selector.
782    compound_state: PerCompoundState,
783
784    /// Additional state to keep track of for collecting nested inner selectors of relative selectors
785    /// Holds the next relative selector dependency and the state given to a relative selector.
786    relative_inner_collector: Option<RelativeSelectorInnerCollectorState<'b>>,
787
788    scope_dependencies: &'a mut ScopeSelectorCollectorState<'c>,
789
790    /// The allocation error, if we OOM.
791    alloc_error: &'a mut Option<AllocErr>,
792}
793
794fn next_dependency(
795    next_selector: &mut NextSelectors,
796    next_outer_dependency: Option<&ThinArc<(), Dependency>>,
797    next_scope_dependencies: Option<&ThinArc<(), Dependency>>,
798    scope_kind: Option<ScopeDependencyInvalidationKind>,
799) -> Option<ThinArc<(), Dependency>> {
800    if next_selector.is_empty() {
801        return match next_outer_dependency {
802            Some(..) => next_outer_dependency.cloned(),
803            None => next_scope_dependencies.cloned(),
804        };
805    }
806
807    fn dependencies_from(
808        entries: &mut [NextDependencyEntry],
809        next_outer_dependency: &Option<&ThinArc<(), Dependency>>,
810        next_scope_dependencies: &Option<&ThinArc<(), Dependency>>,
811        scope_kind: Option<ScopeDependencyInvalidationKind>,
812    ) -> Option<ThinArc<(), Dependency>> {
813        if entries.is_empty() {
814            return next_scope_dependencies.cloned();
815        }
816
817        let last_index = entries.len() - 1;
818        let (previous, last) = entries.split_at_mut(last_index);
819        let last = &mut last[0];
820        let selector = &last.selector;
821        let selector_offset = last.offset;
822
823        let dependency = Dependency {
824            selector: selector.clone(),
825            selector_offset,
826            next: dependencies_from(
827                previous,
828                next_outer_dependency,
829                next_scope_dependencies,
830                scope_kind,
831            ),
832            kind: get_non_relative_invalidation_kind(
833                selector,
834                selector_offset,
835                next_scope_dependencies
836                    .is_some()
837                    .then_some(scope_kind)
838                    .flatten(),
839            ),
840        };
841
842        Some(
843            last.cached_dependency
844                .get_or_insert_with(|| ThinArc::from_header_and_iter((), [dependency].into_iter()))
845                .clone(),
846        )
847    }
848
849    dependencies_from(
850        next_selector,
851        &next_outer_dependency,
852        &next_scope_dependencies,
853        scope_kind,
854    )
855}
856
857impl<'a, 'b, 'c> Collector for SelectorDependencyCollector<'a, 'b, 'c> {
858    fn dependency(&mut self) -> Dependency {
859        let optional_dependency = self
860            .relative_inner_collector
861            .as_ref()
862            .map(|collector| collector.next_dependency);
863
864        let offset = self.compound_state.offset;
865
866        let scope_dependencies = self.inner_scope_dependencies();
867
868        let next = next_dependency(
869            self.next_selectors,
870            optional_dependency,
871            scope_dependencies.as_ref(),
872            self.scope_dependencies.scope_kind,
873        );
874
875        Dependency {
876            selector: self.selector.clone(),
877            selector_offset: offset,
878            next,
879            kind: get_non_relative_invalidation_kind(
880                self.selector,
881                offset,
882                scope_dependencies
883                    .is_some()
884                    .then_some(self.scope_dependencies.scope_kind)
885                    .flatten(),
886            ),
887        }
888    }
889
890    fn id_map(&mut self) -> &mut IdOrClassDependencyMap {
891        if self.relative_inner_collector.is_none() {
892            &mut self.map.id_to_selector
893        } else {
894            &mut self.relative_selector_invalidation_map.id_to_selector
895        }
896    }
897
898    fn class_map(&mut self) -> &mut IdOrClassDependencyMap {
899        if self.relative_inner_collector.is_none() {
900            &mut self.map.class_to_selector
901        } else {
902            &mut self.relative_selector_invalidation_map.class_to_selector
903        }
904    }
905
906    fn state_map(&mut self) -> &mut StateDependencyMap {
907        if self.relative_inner_collector.is_none() {
908            &mut self.map.state_affecting_selectors
909        } else {
910            &mut self
911                .relative_selector_invalidation_map
912                .state_affecting_selectors
913        }
914    }
915
916    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap {
917        if self.relative_inner_collector.is_none() {
918            &mut self.map.other_attribute_affecting_selectors
919        } else {
920            &mut self
921                .relative_selector_invalidation_map
922                .other_attribute_affecting_selectors
923        }
924    }
925
926    fn inner_scope_dependencies(&self) -> Option<ThinArc<(), Dependency>> {
927        self.scope_dependencies.inner_dependencies.clone()
928    }
929
930    fn this_scope_dependencies(&mut self) -> &mut Option<Vec<Dependency>> {
931        &mut self.scope_dependencies.this_dependencies
932    }
933
934    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState) {
935        self.compound_state.element_state |= element_state;
936        *self.document_state |= document_state;
937    }
938
939    fn custom_state_map(&mut self) -> &mut CustomStateDependencyMap {
940        if self.relative_inner_collector.is_none() {
941            &mut self.map.custom_state_affecting_selectors
942        } else {
943            &mut self
944                .relative_selector_invalidation_map
945                .custom_state_affecting_selectors
946        }
947    }
948
949    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
950        debug_assert!(
951            self.relative_inner_collector.is_some(),
952            "Asking for relative selector invalidation outside of relative selector"
953        );
954        &mut self
955            .additional_relative_selector_invalidation_map
956            .type_to_selector
957    }
958
959    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
960        debug_assert!(
961            self.relative_inner_collector.is_some(),
962            "Asking for relative selector invalidation outside of relative selector"
963        );
964        &mut self
965            .additional_relative_selector_invalidation_map
966            .ts_state_to_selector
967    }
968
969    fn any_vec(&mut self) -> &mut AnyDependencyMap {
970        debug_assert!(
971            self.relative_inner_collector.is_some(),
972            "Asking for relative selector invalidation outside of relative selector"
973        );
974        &mut self
975            .additional_relative_selector_invalidation_map
976            .any_to_selector
977    }
978}
979
980impl<'a, 'b, 'c> SelectorDependencyCollector<'a, 'b, 'c> {
981    fn visit_whole_selector(&mut self) -> bool {
982        let iter = self.selector.iter();
983        self.visit_whole_selector_from(iter, 0)
984    }
985
986    fn visit_whole_selector_from(
987        &mut self,
988        mut iter: SelectorIter<SelectorImpl>,
989        mut index: usize,
990    ) -> bool {
991        loop {
992            // Reset the compound state.
993            self.compound_state = PerCompoundState::new(index);
994            if let Some(state) = self.relative_inner_collector.as_mut() {
995                state.relative_compound_state = RelativeSelectorCompoundStateAttributes::new();
996            }
997
998            // Visit all the simple selectors in this sequence.
999            let (keep_traversing, index_offset) = visit_all_in_iter_compound(self, &mut iter);
1000
1001            if !keep_traversing {
1002                return false;
1003            }
1004
1005            index += index_offset;
1006
1007            if let Err(err) = add_pseudo_class_dependency(
1008                self.compound_state.element_state,
1009                self.quirks_mode,
1010                self,
1011            ) {
1012                *self.alloc_error = Some(err);
1013                return false;
1014            }
1015
1016            if let Some(state) = self
1017                .relative_inner_collector
1018                .as_ref()
1019                .map(|state| state.relative_compound_state)
1020            {
1021                if let Err(err) =
1022                    add_ts_pseudo_class_dependency(state.ts_state, self.quirks_mode, self)
1023                {
1024                    *self.alloc_error = Some(err);
1025                    return false;
1026                }
1027
1028                if !state.added_entry {
1029                    // Not great - we didn't add any uniquely identifiable information.
1030                    if let Err(err) =
1031                        add_non_unique_info(self.selector, self.compound_state.offset, self)
1032                    {
1033                        *self.alloc_error = Some(err);
1034                        return false;
1035                    }
1036                }
1037            }
1038
1039            let combinator = iter.next_sequence();
1040            if combinator.is_none() {
1041                return true;
1042            }
1043            index += 1; // account for the combinator
1044        }
1045    }
1046}
1047
1048impl<'a, 'b, 'c> SelectorVisitor for SelectorDependencyCollector<'a, 'b, 'c> {
1049    type Impl = SelectorImpl;
1050
1051    fn visit_selector_list(
1052        &mut self,
1053        _list_kind: SelectorListKind,
1054        list: &[Selector<SelectorImpl>],
1055    ) -> bool {
1056        let next_relative_dependency = self
1057            .relative_inner_collector
1058            .is_some()
1059            .then(|| ThinArc::from_header_and_iter((), std::iter::once(self.dependency())));
1060        for selector in list {
1061            // Here we cheat a bit: We can visit the rightmost compound with
1062            // the "outer" visitor, and it'd be fine. This reduces the amount of
1063            // state and attribute invalidations, and we need to check the outer
1064            // selector to the left anyway to avoid over-invalidation, so it
1065            // avoids matching it twice uselessly.
1066            let mut iter = selector.iter();
1067            let saved_added_entry = self
1068                .relative_inner_collector
1069                .as_ref()
1070                .map(|state| state.relative_compound_state.added_entry);
1071
1072            let (keep_traversing, mut index) = visit_all_in_iter_compound(self, &mut iter);
1073
1074            if !keep_traversing {
1075                return false;
1076            }
1077
1078            if let Some(state) = self.relative_inner_collector.as_mut() {
1079                state.relative_compound_state.added_entry = saved_added_entry.unwrap_or_default();
1080            }
1081            let combinator = iter.next_sequence();
1082            if combinator.is_none() {
1083                continue;
1084            }
1085
1086            index += 1; // account for the combinator.
1087
1088            let offset = self.compound_state.offset;
1089
1090            if self.relative_inner_collector.is_none() {
1091                self.next_selectors.push(NextDependencyEntry {
1092                    selector: self.selector.clone(),
1093                    offset,
1094                    cached_dependency: None,
1095                });
1096            }
1097            debug_assert!(
1098                next_relative_dependency.is_some() == self.relative_inner_collector.is_some(),
1099                "Next relative dependency and relative inner collector must be Some/None at the same time!"
1100            );
1101            let mut nested = SelectorDependencyCollector {
1102                map: &mut *self.map,
1103                relative_selector_invalidation_map: &mut *self.relative_selector_invalidation_map,
1104                additional_relative_selector_invalidation_map: &mut *self
1105                    .additional_relative_selector_invalidation_map,
1106                document_state: &mut *self.document_state,
1107                selector,
1108                next_selectors: &mut *self.next_selectors,
1109                quirks_mode: self.quirks_mode,
1110                compound_state: PerCompoundState::new(index),
1111                relative_inner_collector: next_relative_dependency.as_ref().map(
1112                    |next_dependency| RelativeSelectorInnerCollectorState {
1113                        next_dependency,
1114                        relative_compound_state: RelativeSelectorCompoundStateAttributes::new(),
1115                    },
1116                ),
1117                scope_dependencies: self.scope_dependencies,
1118                alloc_error: &mut *self.alloc_error,
1119            };
1120            if !nested.visit_whole_selector_from(iter, index) {
1121                return false;
1122            }
1123            self.next_selectors.pop();
1124        }
1125        true
1126    }
1127
1128    fn visit_relative_selector_list(
1129        &mut self,
1130        list: &[selectors::parser::RelativeSelector<Self::Impl>],
1131    ) -> bool {
1132        // Ignore nested relative selectors. This can happen as a result of nesting.
1133        if self.relative_inner_collector.is_some() {
1134            return true;
1135        }
1136
1137        self.additional_relative_selector_invalidation_map.used = true;
1138        for relative_selector in list {
1139            // We can't cheat here like we do with other selector lists - the rightmost
1140            // compound of a relative selector is not the subject of the invalidation.
1141            self.next_selectors.push(NextDependencyEntry {
1142                selector: self.selector.clone(),
1143                offset: self.compound_state.offset,
1144                cached_dependency: None,
1145            });
1146            let mut nested = RelativeSelectorDependencyCollector {
1147                map: &mut *self.map,
1148                relative_selector_invalidation_map: &mut *self.relative_selector_invalidation_map,
1149                additional_relative_selector_invalidation_map: &mut *self
1150                    .additional_relative_selector_invalidation_map,
1151                document_state: &mut *self.document_state,
1152                selector: relative_selector,
1153                combinator_count: RelativeSelectorCombinatorCount::new(relative_selector),
1154                next_selectors: &mut *self.next_selectors,
1155                quirks_mode: self.quirks_mode,
1156                compound_state: PerCompoundState::new(0),
1157                compound_state_attributes: RelativeSelectorCompoundStateAttributes::new(),
1158                scope_dependencies: self.scope_dependencies,
1159                alloc_error: &mut *self.alloc_error,
1160            };
1161            if !nested.visit_whole_selector() {
1162                return false;
1163            }
1164            self.next_selectors.pop();
1165        }
1166        true
1167    }
1168
1169    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
1170        match on_simple_selector(s, self.quirks_mode, self) {
1171            Ok(result) => {
1172                if let ComponentVisitResult::Handled(state) = result
1173                    && let Some(inner_collector_state) = self.relative_inner_collector.as_mut()
1174                {
1175                    inner_collector_state.relative_compound_state.added_entry = true;
1176                    inner_collector_state
1177                        .relative_compound_state
1178                        .ts_state
1179                        .insert(state);
1180                }
1181                true
1182            },
1183            Err(err) => {
1184                *self.alloc_error = Some(err);
1185                false
1186            },
1187        }
1188    }
1189
1190    fn visit_attribute_selector(
1191        &mut self,
1192        _: &NamespaceConstraint<&Namespace>,
1193        local_name: &LocalName,
1194        local_name_lower: &LocalName,
1195    ) -> bool {
1196        if let Some(state) = self.relative_inner_collector.as_mut() {
1197            state.relative_compound_state.added_entry = true;
1198        }
1199        if let Err(err) = on_attribute(local_name, local_name_lower, self) {
1200            *self.alloc_error = Some(err);
1201            return false;
1202        }
1203        true
1204    }
1205}
1206
1207#[derive(Clone, Copy)]
1208struct RelativeSelectorCompoundStateAttributes {
1209    ts_state: TSStateForInvalidation,
1210    added_entry: bool,
1211}
1212
1213impl RelativeSelectorCompoundStateAttributes {
1214    fn new() -> Self {
1215        Self {
1216            ts_state: TSStateForInvalidation::empty(),
1217            added_entry: false,
1218        }
1219    }
1220}
1221
1222/// A struct that collects invalidations for a given compound selector.
1223struct RelativeSelectorDependencyCollector<'a, 'b> {
1224    map: &'a mut InvalidationMap,
1225    relative_selector_invalidation_map: &'a mut InvalidationMap,
1226    additional_relative_selector_invalidation_map:
1227        &'a mut AdditionalRelativeSelectorInvalidationMap,
1228
1229    /// The document this _complex_ selector is affected by.
1230    ///
1231    /// We don't need to track state per compound selector, since it's global
1232    /// state and it changes for everything.
1233    document_state: &'a mut DocumentState,
1234
1235    /// The current inner relative selector and offset we're iterating.
1236    selector: &'a RelativeSelector<SelectorImpl>,
1237    /// Running combinator for this inner relative selector.
1238    combinator_count: RelativeSelectorCombinatorCount,
1239
1240    /// The stack of next selectors that we have, and at which offset of the
1241    /// sequence.
1242    ///
1243    /// This starts empty. It grows when we find nested :is and :where selector
1244    /// lists. The dependency field is cached and reference counted.
1245    next_selectors: &'a mut NextSelectors,
1246
1247    /// The quirks mode of the document where we're inserting dependencies.
1248    quirks_mode: QuirksMode,
1249
1250    /// State relevant to a given compound selector.
1251    compound_state: PerCompoundState,
1252
1253    /// Attributes relevant to the relative compound selector state.
1254    compound_state_attributes: RelativeSelectorCompoundStateAttributes,
1255
1256    scope_dependencies: &'a mut ScopeSelectorCollectorState<'b>,
1257
1258    /// The allocation error, if we OOM.
1259    alloc_error: &'a mut Option<AllocErr>,
1260}
1261
1262fn add_non_unique_info<C: Collector>(
1263    selector: &Selector<SelectorImpl>,
1264    offset: usize,
1265    collector: &mut C,
1266) -> Result<(), AllocErr> {
1267    // Go through this compound again.
1268    for ss in selector.iter_from(offset) {
1269        if let Component::LocalName(name) = ss {
1270            let dependency = collector.dependency();
1271            add_local_name(&name.name, dependency, collector.type_map())?;
1272            if name.name != name.lower_name {
1273                let dependency = collector.dependency();
1274                add_local_name(&name.lower_name, dependency, collector.type_map())?;
1275            }
1276            return Ok(());
1277        };
1278    }
1279    // Ouch. Add one for *.
1280    collector.any_vec().try_reserve(1)?;
1281    let dependency = collector.dependency();
1282    collector.any_vec().push(dependency);
1283    Ok(())
1284}
1285
1286fn add_ts_pseudo_class_dependency<C: Collector>(
1287    state: TSStateForInvalidation,
1288    quirks_mode: QuirksMode,
1289    collector: &mut C,
1290) -> Result<(), AllocErr> {
1291    if state.is_empty() {
1292        return Ok(());
1293    }
1294    let dependency = collector.dependency();
1295    collector.ts_state_map().insert(
1296        TSStateDependency {
1297            dep: dependency,
1298            state,
1299        },
1300        quirks_mode,
1301    )
1302}
1303
1304impl<'a, 'b> RelativeSelectorDependencyCollector<'a, 'b> {
1305    fn visit_whole_selector(&mut self) -> bool {
1306        let mut iter = self.selector.selector.iter_skip_relative_selector_anchor();
1307        let mut index = 0;
1308
1309        self.additional_relative_selector_invalidation_map
1310            .needs_ancestors_traversal |= match self.selector.match_hint {
1311            RelativeSelectorMatchHint::InNextSiblingSubtree
1312            | RelativeSelectorMatchHint::InSiblingSubtree
1313            | RelativeSelectorMatchHint::InSubtree => true,
1314            _ => false,
1315        };
1316        loop {
1317            // Reset the compound state.
1318            self.compound_state = PerCompoundState::new(index);
1319
1320            let (keep_traversing, index_offset) = visit_all_in_iter_compound(self, &mut iter);
1321
1322            if !keep_traversing {
1323                return false;
1324            }
1325
1326            index += index_offset;
1327
1328            if let Err(err) = add_pseudo_class_dependency(
1329                self.compound_state.element_state,
1330                self.quirks_mode,
1331                self,
1332            ) {
1333                *self.alloc_error = Some(err);
1334                return false;
1335            }
1336
1337            if let Err(err) = add_ts_pseudo_class_dependency(
1338                self.compound_state_attributes.ts_state,
1339                self.quirks_mode,
1340                self,
1341            ) {
1342                *self.alloc_error = Some(err);
1343                return false;
1344            }
1345
1346            if !self.compound_state_attributes.added_entry {
1347                // Not great - we didn't add any uniquely identifiable information.
1348                if let Err(err) =
1349                    add_non_unique_info(&self.selector.selector, self.compound_state.offset, self)
1350                {
1351                    *self.alloc_error = Some(err);
1352                    return false;
1353                }
1354            }
1355
1356            let combinator = iter.next_sequence();
1357            if let Some(c) = combinator {
1358                match c {
1359                    Combinator::Child | Combinator::Descendant => {
1360                        self.combinator_count.child_or_descendants -= 1
1361                    },
1362                    Combinator::NextSibling | Combinator::LaterSibling => {
1363                        self.combinator_count.adjacent_or_next_siblings -= 1
1364                    },
1365                    Combinator::Part | Combinator::PseudoElement | Combinator::SlotAssignment => (),
1366                }
1367            } else {
1368                return true;
1369            }
1370            index += 1; // account for the combinator
1371        }
1372    }
1373}
1374
1375impl<'a, 'b> Collector for RelativeSelectorDependencyCollector<'a, 'b> {
1376    fn dependency(&mut self) -> Dependency {
1377        let scope_dependencies = self.inner_scope_dependencies();
1378        let scope_kind = self.scope_dependencies.scope_kind;
1379
1380        let next = next_dependency(
1381            self.next_selectors,
1382            None,
1383            scope_dependencies.as_ref(),
1384            scope_kind,
1385        );
1386        debug_assert!(
1387            next.as_ref().is_some_and(|d| !matches!(
1388                d.slice()[0].kind,
1389                DependencyInvalidationKind::Relative(_)
1390            )),
1391            "Duplicate relative dependency?"
1392        );
1393        debug_assert!(
1394            next.as_ref().is_some_and(|d| !d.slice().is_empty()),
1395            "Empty dependency?"
1396        );
1397
1398        Dependency {
1399            selector: self.selector.selector.clone(),
1400            selector_offset: self.compound_state.offset,
1401            kind: DependencyInvalidationKind::Relative(
1402                match self.combinator_count.get_match_hint() {
1403                    RelativeSelectorMatchHint::InChild => {
1404                        RelativeDependencyInvalidationKind::Parent
1405                    },
1406                    RelativeSelectorMatchHint::InSubtree => {
1407                        RelativeDependencyInvalidationKind::Ancestors
1408                    },
1409                    RelativeSelectorMatchHint::InNextSibling => {
1410                        RelativeDependencyInvalidationKind::PrevSibling
1411                    },
1412                    RelativeSelectorMatchHint::InSibling => {
1413                        RelativeDependencyInvalidationKind::EarlierSibling
1414                    },
1415                    RelativeSelectorMatchHint::InNextSiblingSubtree => {
1416                        RelativeDependencyInvalidationKind::AncestorPrevSibling
1417                    },
1418                    RelativeSelectorMatchHint::InSiblingSubtree => {
1419                        RelativeDependencyInvalidationKind::AncestorEarlierSibling
1420                    },
1421                },
1422            ),
1423            next,
1424        }
1425    }
1426
1427    fn id_map(&mut self) -> &mut IdOrClassDependencyMap {
1428        &mut self.relative_selector_invalidation_map.id_to_selector
1429    }
1430
1431    fn class_map(&mut self) -> &mut IdOrClassDependencyMap {
1432        &mut self.relative_selector_invalidation_map.class_to_selector
1433    }
1434
1435    fn state_map(&mut self) -> &mut StateDependencyMap {
1436        &mut self
1437            .relative_selector_invalidation_map
1438            .state_affecting_selectors
1439    }
1440
1441    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap {
1442        &mut self
1443            .relative_selector_invalidation_map
1444            .other_attribute_affecting_selectors
1445    }
1446
1447    fn custom_state_map(&mut self) -> &mut CustomStateDependencyMap {
1448        &mut self
1449            .relative_selector_invalidation_map
1450            .custom_state_affecting_selectors
1451    }
1452
1453    fn inner_scope_dependencies(&self) -> Option<ThinArc<(), Dependency>> {
1454        self.scope_dependencies.inner_dependencies.clone()
1455    }
1456
1457    fn this_scope_dependencies(&mut self) -> &mut Option<Vec<Dependency>> {
1458        &mut self.scope_dependencies.this_dependencies
1459    }
1460
1461    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState) {
1462        self.compound_state.element_state |= element_state;
1463        *self.document_state |= document_state;
1464    }
1465
1466    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
1467        &mut self
1468            .additional_relative_selector_invalidation_map
1469            .type_to_selector
1470    }
1471
1472    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
1473        &mut self
1474            .additional_relative_selector_invalidation_map
1475            .ts_state_to_selector
1476    }
1477
1478    fn any_vec(&mut self) -> &mut AnyDependencyMap {
1479        &mut self
1480            .additional_relative_selector_invalidation_map
1481            .any_to_selector
1482    }
1483}
1484
1485enum ComponentVisitResult {
1486    /// This component is not relevant for building up the invalidation map.
1487    IsIrrelevant,
1488    /// This component has been added to the invalidation map. Any additional
1489    /// tree-structural pseudo-class dependency is also included, if required.
1490    Handled(TSStateForInvalidation),
1491}
1492
1493#[inline(always)]
1494fn on_simple_selector<C: Collector>(
1495    s: &Component<SelectorImpl>,
1496    quirks_mode: QuirksMode,
1497    collector: &mut C,
1498) -> Result<ComponentVisitResult, AllocErr> {
1499    match *s {
1500        Component::ID(..) | Component::Class(..) => {
1501            on_id_or_class(s, quirks_mode, collector)?;
1502            Ok(ComponentVisitResult::Handled(
1503                TSStateForInvalidation::empty(),
1504            ))
1505        },
1506        Component::ImplicitScope | Component::Scope => {
1507            on_scope(collector)?;
1508            Ok(ComponentVisitResult::Handled(
1509                TSStateForInvalidation::empty(),
1510            ))
1511        },
1512        Component::NonTSPseudoClass(ref pc) => {
1513            on_pseudo_class(pc, collector)?;
1514            Ok(ComponentVisitResult::Handled(
1515                TSStateForInvalidation::empty(),
1516            ))
1517        },
1518        Component::Empty => Ok(ComponentVisitResult::Handled(TSStateForInvalidation::EMPTY)),
1519        Component::Nth(data) => {
1520            let kind = if data.is_simple_edge() {
1521                if data.ty.is_from_end() {
1522                    TSStateForInvalidation::NTH_EDGE_LAST
1523                } else {
1524                    TSStateForInvalidation::NTH_EDGE_FIRST
1525                }
1526            } else {
1527                TSStateForInvalidation::NTH
1528            };
1529            Ok(ComponentVisitResult::Handled(kind))
1530        },
1531        Component::RelativeSelectorAnchor => unreachable!("Should not visit this far"),
1532        _ => Ok(ComponentVisitResult::IsIrrelevant),
1533    }
1534}
1535
1536impl<'a, 'b> SelectorVisitor for RelativeSelectorDependencyCollector<'a, 'b> {
1537    type Impl = SelectorImpl;
1538
1539    fn visit_selector_list(
1540        &mut self,
1541        _list_kind: SelectorListKind,
1542        list: &[Selector<SelectorImpl>],
1543    ) -> bool {
1544        let mut next_stack = NextSelectors::new();
1545        let next_dependency = ThinArc::from_header_and_iter((), [self.dependency()].into_iter());
1546        for selector in list {
1547            let mut iter = selector.iter();
1548            let saved_added_entry = self.compound_state_attributes.added_entry;
1549
1550            let (keep_traversing, mut index) = visit_all_in_iter_compound(self, &mut iter);
1551
1552            if !keep_traversing {
1553                return false;
1554            }
1555
1556            let combinator = iter.next_sequence();
1557
1558            // We want to preserve added_entry, to handle all DOM manipulations
1559            // correctly. For example, given `.anchor:has(:not(.foo))`, and a
1560            // DOM tree `.anchor > .foo`, insertion of _any_ element without
1561            // `.foo` as `.anchor`'s child must trigger an invalidation.
1562            self.compound_state_attributes.added_entry = saved_added_entry;
1563            if combinator.is_none() {
1564                continue;
1565            }
1566
1567            index += 1; // account for the combinator.
1568
1569            let mut nested = SelectorDependencyCollector {
1570                map: &mut *self.map,
1571                relative_selector_invalidation_map: &mut *self.relative_selector_invalidation_map,
1572                additional_relative_selector_invalidation_map: self
1573                    .additional_relative_selector_invalidation_map,
1574                document_state: &mut *self.document_state,
1575                selector,
1576                next_selectors: &mut next_stack,
1577                quirks_mode: self.quirks_mode,
1578                compound_state: PerCompoundState::new(index),
1579                relative_inner_collector: Some(RelativeSelectorInnerCollectorState {
1580                    next_dependency: &next_dependency,
1581                    relative_compound_state: RelativeSelectorCompoundStateAttributes::new(),
1582                }),
1583                scope_dependencies: self.scope_dependencies,
1584                alloc_error: &mut *self.alloc_error,
1585            };
1586            if !nested.visit_whole_selector_from(iter, index) {
1587                return false;
1588            }
1589        }
1590        true
1591    }
1592
1593    fn visit_relative_selector_list(
1594        &mut self,
1595        _list: &[selectors::parser::RelativeSelector<Self::Impl>],
1596    ) -> bool {
1597        // Ignore nested relative selectors. These can happen as a result of nesting.
1598        true
1599    }
1600
1601    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
1602        match on_simple_selector(s, self.quirks_mode, self) {
1603            Ok(result) => {
1604                if let ComponentVisitResult::Handled(state) = result {
1605                    self.compound_state_attributes.added_entry = true;
1606                    self.compound_state_attributes.ts_state.insert(state);
1607                }
1608                true
1609            },
1610            Err(err) => {
1611                *self.alloc_error = Some(err);
1612                false
1613            },
1614        }
1615    }
1616
1617    fn visit_attribute_selector(
1618        &mut self,
1619        _: &NamespaceConstraint<&Namespace>,
1620        local_name: &LocalName,
1621        local_name_lower: &LocalName,
1622    ) -> bool {
1623        self.compound_state_attributes.added_entry = true;
1624        if let Err(err) = on_attribute(local_name, local_name_lower, self) {
1625            *self.alloc_error = Some(err);
1626            return false;
1627        }
1628        true
1629    }
1630}
style/invalidation/element/invalidation_map.rs

style/invalidation/element/
invalidation_map.rs
