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::context::QuirksMode;
8use crate::derives::*;
9use crate::selector_map::{
10    MaybeCaseInsensitiveHashMap, PrecomputedHashMap, SelectorMap, SelectorMapEntry,
11};
12use crate::selector_parser::{NonTSPseudoClass, SelectorImpl};
13use crate::values::AtomIdent;
14use crate::AllocErr;
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.clone(), collector)?;
627    if local_name != local_name_lower {
628        add_attr_dependency(local_name_lower.clone(), 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 entry = map.try_entry(atom.0.clone(), quirks_mode)?;
646    let vec = entry.or_insert_with(SmallVec::new);
647    vec.try_reserve(1)?;
648    vec.push(dependency);
649    Ok(())
650}
651
652fn on_scope<C: Collector>(collector: &mut C) -> Result<(), AllocErr> {
653    let new_dependency = collector.dependency();
654    let this_scope_dependencies = collector.this_scope_dependencies();
655
656    this_scope_dependencies
657        .get_or_insert(Vec::new())
658        .push(new_dependency);
659
660    Ok(())
661}
662
663fn add_attr_dependency<C: Collector>(name: LocalName, collector: &mut C) -> Result<(), AllocErr> {
664    let dependency = collector.dependency();
665    let map = collector.attribute_map();
666    add_local_name(name, dependency, map)
667}
668
669fn add_custom_state_dependency<C: Collector>(
670    name: AtomIdent,
671    collector: &mut C,
672) -> Result<(), AllocErr> {
673    let dependency = collector.dependency();
674    let map = collector.custom_state_map();
675    map.try_reserve(1)?;
676    let vec = map.entry(name).or_default();
677    vec.try_reserve(1)?;
678    vec.push(dependency);
679    Ok(())
680}
681
682fn add_local_name(
683    name: LocalName,
684    dependency: Dependency,
685    map: &mut LocalNameDependencyMap,
686) -> Result<(), AllocErr> {
687    map.try_reserve(1)?;
688    let vec = map.entry(name).or_default();
689    vec.try_reserve(1)?;
690    vec.push(dependency);
691    Ok(())
692}
693
694fn on_pseudo_class<C: Collector>(pc: &NonTSPseudoClass, collector: &mut C) -> Result<(), AllocErr> {
695    collector.update_states(pc.state_flag(), pc.document_state_flag());
696
697    let attr_name = match *pc {
698        #[cfg(feature = "gecko")]
699        NonTSPseudoClass::MozTableBorderNonzero => local_name!("border"),
700        #[cfg(feature = "gecko")]
701        NonTSPseudoClass::MozSelectListBox => {
702            // This depends on two attributes.
703            add_attr_dependency(local_name!("multiple"), collector)?;
704            return add_attr_dependency(local_name!("size"), collector);
705        },
706        NonTSPseudoClass::Lang(..) => local_name!("lang"),
707        NonTSPseudoClass::CustomState(ref name) => {
708            return add_custom_state_dependency(name.0.clone(), collector);
709        },
710        _ => return Ok(()),
711    };
712
713    add_attr_dependency(attr_name, collector)
714}
715
716fn add_pseudo_class_dependency<C: Collector>(
717    element_state: ElementState,
718    quirks_mode: QuirksMode,
719    collector: &mut C,
720) -> Result<(), AllocErr> {
721    if element_state.is_empty() {
722        return Ok(());
723    }
724    let dependency = collector.dependency();
725    collector.state_map().insert(
726        StateDependency {
727            dep: dependency,
728            state: element_state,
729        },
730        quirks_mode,
731    )
732}
733
734/// Visit all the simple selectors in the iter compound
735/// and return the number of simple selectors visited.
736/// We need to return a tuple because we need to keep
737/// track of two things:
738/// 1) Should the traversal continue and
739/// 2) What the offset of the compound state is.
740fn visit_all_in_iter_compound<T: SelectorVisitor<Impl = SelectorImpl>>(
741    visitor: &mut T,
742    iter: &mut SelectorIter<'_, SelectorImpl>,
743) -> (bool, usize) {
744    let mut index = 0;
745    for ss in iter {
746        if !ss.visit(visitor) {
747            return (false, index);
748        }
749        index += 1;
750    }
751    (true, index)
752}
753
754type NextSelectors = SmallVec<[NextDependencyEntry; 5]>;
755
756/// A struct that collects invalidations for a given compound selector.
757struct SelectorDependencyCollector<'a, 'b, 'c> {
758    map: &'a mut InvalidationMap,
759    relative_selector_invalidation_map: &'a mut InvalidationMap,
760    additional_relative_selector_invalidation_map:
761        &'a mut AdditionalRelativeSelectorInvalidationMap,
762
763    /// The document this _complex_ selector is affected by.
764    ///
765    /// We don't need to track state per compound selector, since it's global
766    /// state and it changes for everything.
767    document_state: &'a mut DocumentState,
768
769    /// The current selector and offset we're iterating.
770    selector: &'a Selector<SelectorImpl>,
771
772    /// The stack of next selectors that we have, and at which offset of the
773    /// sequence.
774    ///
775    /// This starts empty. It grows when we find nested :is and :where selector
776    /// lists. The dependency field is cached and reference counted.
777    next_selectors: &'a mut NextSelectors,
778
779    /// The quirks mode of the document where we're inserting dependencies.
780    quirks_mode: QuirksMode,
781
782    /// State relevant to a given compound selector.
783    compound_state: PerCompoundState,
784
785    /// Additional state to keep track of for collecting nested inner selectors of relative selectors
786    /// Holds the next relative selector dependency and the state given to a relative selector.
787    relative_inner_collector: Option<RelativeSelectorInnerCollectorState<'b>>,
788
789    scope_dependencies: &'a mut ScopeSelectorCollectorState<'c>,
790
791    /// The allocation error, if we OOM.
792    alloc_error: &'a mut Option<AllocErr>,
793}
794
795fn next_dependency(
796    next_selector: &mut NextSelectors,
797    next_outer_dependency: Option<&ThinArc<(), Dependency>>,
798    next_scope_dependencies: Option<&ThinArc<(), Dependency>>,
799    scope_kind: Option<ScopeDependencyInvalidationKind>,
800) -> Option<ThinArc<(), Dependency>> {
801    if next_selector.is_empty() {
802        return match next_outer_dependency {
803            Some(..) => next_outer_dependency.cloned(),
804            None => next_scope_dependencies.cloned(),
805        };
806    }
807
808    fn dependencies_from(
809        entries: &mut [NextDependencyEntry],
810        next_outer_dependency: &Option<&ThinArc<(), Dependency>>,
811        next_scope_dependencies: &Option<&ThinArc<(), Dependency>>,
812        scope_kind: Option<ScopeDependencyInvalidationKind>,
813    ) -> Option<ThinArc<(), Dependency>> {
814        if entries.is_empty() {
815            return next_scope_dependencies.cloned();
816        }
817
818        let last_index = entries.len() - 1;
819        let (previous, last) = entries.split_at_mut(last_index);
820        let last = &mut last[0];
821        let selector = &last.selector;
822        let selector_offset = last.offset;
823
824        let dependency = Dependency {
825            selector: selector.clone(),
826            selector_offset,
827            next: dependencies_from(
828                previous,
829                next_outer_dependency,
830                next_scope_dependencies,
831                scope_kind,
832            ),
833            kind: get_non_relative_invalidation_kind(
834                selector,
835                selector_offset,
836                next_scope_dependencies
837                    .is_some()
838                    .then_some(scope_kind)
839                    .flatten(),
840            ),
841        };
842
843        Some(
844            last.cached_dependency
845                .get_or_insert_with(|| ThinArc::from_header_and_iter((), [dependency].into_iter()))
846                .clone(),
847        )
848    }
849
850    dependencies_from(
851        next_selector,
852        &next_outer_dependency,
853        &next_scope_dependencies,
854        scope_kind,
855    )
856}
857
858impl<'a, 'b, 'c> Collector for SelectorDependencyCollector<'a, 'b, 'c> {
859    fn dependency(&mut self) -> Dependency {
860        let optional_dependency = self
861            .relative_inner_collector
862            .as_ref()
863            .map(|collector| collector.next_dependency);
864
865        let offset = self.compound_state.offset;
866
867        let scope_dependencies = self.inner_scope_dependencies();
868
869        let next = next_dependency(
870            self.next_selectors,
871            optional_dependency,
872            scope_dependencies.as_ref(),
873            self.scope_dependencies.scope_kind,
874        );
875
876        Dependency {
877            selector: self.selector.clone(),
878            selector_offset: offset,
879            next,
880            kind: get_non_relative_invalidation_kind(
881                self.selector,
882                offset,
883                scope_dependencies
884                    .is_some()
885                    .then_some(self.scope_dependencies.scope_kind)
886                    .flatten(),
887            ),
888        }
889    }
890
891    fn id_map(&mut self) -> &mut IdOrClassDependencyMap {
892        if self.relative_inner_collector.is_none() {
893            &mut self.map.id_to_selector
894        } else {
895            &mut self.relative_selector_invalidation_map.id_to_selector
896        }
897    }
898
899    fn class_map(&mut self) -> &mut IdOrClassDependencyMap {
900        if self.relative_inner_collector.is_none() {
901            &mut self.map.class_to_selector
902        } else {
903            &mut self.relative_selector_invalidation_map.class_to_selector
904        }
905    }
906
907    fn state_map(&mut self) -> &mut StateDependencyMap {
908        if self.relative_inner_collector.is_none() {
909            &mut self.map.state_affecting_selectors
910        } else {
911            &mut self
912                .relative_selector_invalidation_map
913                .state_affecting_selectors
914        }
915    }
916
917    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap {
918        if self.relative_inner_collector.is_none() {
919            &mut self.map.other_attribute_affecting_selectors
920        } else {
921            &mut self
922                .relative_selector_invalidation_map
923                .other_attribute_affecting_selectors
924        }
925    }
926
927    fn inner_scope_dependencies(&self) -> Option<ThinArc<(), Dependency>> {
928        self.scope_dependencies.inner_dependencies.clone()
929    }
930
931    fn this_scope_dependencies(&mut self) -> &mut Option<Vec<Dependency>> {
932        &mut self.scope_dependencies.this_dependencies
933    }
934
935    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState) {
936        self.compound_state.element_state |= element_state;
937        *self.document_state |= document_state;
938    }
939
940    fn custom_state_map(&mut self) -> &mut CustomStateDependencyMap {
941        if self.relative_inner_collector.is_none() {
942            &mut self.map.custom_state_affecting_selectors
943        } else {
944            &mut self
945                .relative_selector_invalidation_map
946                .custom_state_affecting_selectors
947        }
948    }
949
950    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
951        debug_assert!(
952            self.relative_inner_collector.is_some(),
953            "Asking for relative selector invalidation outside of relative selector"
954        );
955        &mut self
956            .additional_relative_selector_invalidation_map
957            .type_to_selector
958    }
959
960    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
961        debug_assert!(
962            self.relative_inner_collector.is_some(),
963            "Asking for relative selector invalidation outside of relative selector"
964        );
965        &mut self
966            .additional_relative_selector_invalidation_map
967            .ts_state_to_selector
968    }
969
970    fn any_vec(&mut self) -> &mut AnyDependencyMap {
971        debug_assert!(
972            self.relative_inner_collector.is_some(),
973            "Asking for relative selector invalidation outside of relative selector"
974        );
975        &mut self
976            .additional_relative_selector_invalidation_map
977            .any_to_selector
978    }
979}
980
981impl<'a, 'b, 'c> SelectorDependencyCollector<'a, 'b, 'c> {
982    fn visit_whole_selector(&mut self) -> bool {
983        let iter = self.selector.iter();
984        self.visit_whole_selector_from(iter, 0)
985    }
986
987    fn visit_whole_selector_from(
988        &mut self,
989        mut iter: SelectorIter<SelectorImpl>,
990        mut index: usize,
991    ) -> bool {
992        loop {
993            // Reset the compound state.
994            self.compound_state = PerCompoundState::new(index);
995            if let Some(state) = self.relative_inner_collector.as_mut() {
996                state.relative_compound_state = RelativeSelectorCompoundStateAttributes::new();
997            }
998
999            // Visit all the simple selectors in this sequence.
1000            let (keep_traversing, index_offset) = visit_all_in_iter_compound(self, &mut iter);
1001
1002            if !keep_traversing {
1003                return false;
1004            }
1005
1006            index += index_offset;
1007
1008            if let Err(err) = add_pseudo_class_dependency(
1009                self.compound_state.element_state,
1010                self.quirks_mode,
1011                self,
1012            ) {
1013                *self.alloc_error = Some(err);
1014                return false;
1015            }
1016
1017            if let Some(state) = self
1018                .relative_inner_collector
1019                .as_ref()
1020                .map(|state| state.relative_compound_state)
1021            {
1022                if let Err(err) =
1023                    add_ts_pseudo_class_dependency(state.ts_state, self.quirks_mode, self)
1024                {
1025                    *self.alloc_error = Some(err);
1026                    return false;
1027                }
1028
1029                if !state.added_entry {
1030                    // Not great - we didn't add any uniquely identifiable information.
1031                    if let Err(err) =
1032                        add_non_unique_info(self.selector, self.compound_state.offset, self)
1033                    {
1034                        *self.alloc_error = Some(err);
1035                        return false;
1036                    }
1037                }
1038            }
1039
1040            let combinator = iter.next_sequence();
1041            if combinator.is_none() {
1042                return true;
1043            }
1044            index += 1; // account for the combinator
1045        }
1046    }
1047}
1048
1049impl<'a, 'b, 'c> SelectorVisitor for SelectorDependencyCollector<'a, 'b, 'c> {
1050    type Impl = SelectorImpl;
1051
1052    fn visit_selector_list(
1053        &mut self,
1054        _list_kind: SelectorListKind,
1055        list: &[Selector<SelectorImpl>],
1056    ) -> bool {
1057        let next_relative_dependency = self
1058            .relative_inner_collector
1059            .is_some()
1060            .then(|| ThinArc::from_header_and_iter((), std::iter::once(self.dependency())));
1061        for selector in list {
1062            // Here we cheat a bit: We can visit the rightmost compound with
1063            // the "outer" visitor, and it'd be fine. This reduces the amount of
1064            // state and attribute invalidations, and we need to check the outer
1065            // selector to the left anyway to avoid over-invalidation, so it
1066            // avoids matching it twice uselessly.
1067            let mut iter = selector.iter();
1068            let saved_added_entry = self
1069                .relative_inner_collector
1070                .as_ref()
1071                .map(|state| state.relative_compound_state.added_entry);
1072
1073            let (keep_traversing, mut index) = visit_all_in_iter_compound(self, &mut iter);
1074
1075            if !keep_traversing {
1076                return false;
1077            }
1078
1079            if let Some(state) = self.relative_inner_collector.as_mut() {
1080                state.relative_compound_state.added_entry = saved_added_entry.unwrap_or_default();
1081            }
1082            let combinator = iter.next_sequence();
1083            if combinator.is_none() {
1084                continue;
1085            }
1086
1087            index += 1; // account for the combinator.
1088
1089            let offset = self.compound_state.offset;
1090
1091            if self.relative_inner_collector.is_none() {
1092                self.next_selectors.push(NextDependencyEntry {
1093                    selector: self.selector.clone(),
1094                    offset,
1095                    cached_dependency: None,
1096                });
1097            }
1098            debug_assert!(
1099                next_relative_dependency.is_some() == self.relative_inner_collector.is_some(),
1100                "Next relative dependency and relative inner collector must be Some/None at the same time!"
1101            );
1102            let mut nested = SelectorDependencyCollector {
1103                map: &mut *self.map,
1104                relative_selector_invalidation_map: &mut *self.relative_selector_invalidation_map,
1105                additional_relative_selector_invalidation_map: &mut *self
1106                    .additional_relative_selector_invalidation_map,
1107                document_state: &mut *self.document_state,
1108                selector,
1109                next_selectors: &mut *self.next_selectors,
1110                quirks_mode: self.quirks_mode,
1111                compound_state: PerCompoundState::new(index),
1112                relative_inner_collector: next_relative_dependency.as_ref().map(
1113                    |next_dependency| RelativeSelectorInnerCollectorState {
1114                        next_dependency,
1115                        relative_compound_state: RelativeSelectorCompoundStateAttributes::new(),
1116                    },
1117                ),
1118                scope_dependencies: self.scope_dependencies,
1119                alloc_error: &mut *self.alloc_error,
1120            };
1121            if !nested.visit_whole_selector_from(iter, index) {
1122                return false;
1123            }
1124            self.next_selectors.pop();
1125        }
1126        true
1127    }
1128
1129    fn visit_relative_selector_list(
1130        &mut self,
1131        list: &[selectors::parser::RelativeSelector<Self::Impl>],
1132    ) -> bool {
1133        // Ignore nested relative selectors. This can happen as a result of nesting.
1134        if self.relative_inner_collector.is_some() {
1135            return true;
1136        }
1137
1138        self.additional_relative_selector_invalidation_map.used = true;
1139        for relative_selector in list {
1140            // We can't cheat here like we do with other selector lists - the rightmost
1141            // compound of a relative selector is not the subject of the invalidation.
1142            self.next_selectors.push(NextDependencyEntry {
1143                selector: self.selector.clone(),
1144                offset: self.compound_state.offset,
1145                cached_dependency: None,
1146            });
1147            let mut nested = RelativeSelectorDependencyCollector {
1148                map: &mut *self.map,
1149                relative_selector_invalidation_map: &mut *self.relative_selector_invalidation_map,
1150                additional_relative_selector_invalidation_map: &mut *self
1151                    .additional_relative_selector_invalidation_map,
1152                document_state: &mut *self.document_state,
1153                selector: relative_selector,
1154                combinator_count: RelativeSelectorCombinatorCount::new(relative_selector),
1155                next_selectors: &mut *self.next_selectors,
1156                quirks_mode: self.quirks_mode,
1157                compound_state: PerCompoundState::new(0),
1158                compound_state_attributes: RelativeSelectorCompoundStateAttributes::new(),
1159                scope_dependencies: self.scope_dependencies,
1160                alloc_error: &mut *self.alloc_error,
1161            };
1162            if !nested.visit_whole_selector() {
1163                return false;
1164            }
1165            self.next_selectors.pop();
1166        }
1167        true
1168    }
1169
1170    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
1171        match on_simple_selector(s, self.quirks_mode, self) {
1172            Ok(result) => {
1173                if let ComponentVisitResult::Handled(state) = result {
1174                    if let Some(inner_collector_state) = self.relative_inner_collector.as_mut() {
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                }
1182                true
1183            },
1184            Err(err) => {
1185                *self.alloc_error = Some(err);
1186                false
1187            },
1188        }
1189    }
1190
1191    fn visit_attribute_selector(
1192        &mut self,
1193        _: &NamespaceConstraint<&Namespace>,
1194        local_name: &LocalName,
1195        local_name_lower: &LocalName,
1196    ) -> bool {
1197        if let Some(state) = self.relative_inner_collector.as_mut() {
1198            state.relative_compound_state.added_entry = true;
1199        }
1200        if let Err(err) = on_attribute(local_name, local_name_lower, self) {
1201            *self.alloc_error = Some(err);
1202            return false;
1203        }
1204        true
1205    }
1206}
1207
1208#[derive(Clone, Copy)]
1209struct RelativeSelectorCompoundStateAttributes {
1210    ts_state: TSStateForInvalidation,
1211    added_entry: bool,
1212}
1213
1214impl RelativeSelectorCompoundStateAttributes {
1215    fn new() -> Self {
1216        Self {
1217            ts_state: TSStateForInvalidation::empty(),
1218            added_entry: false,
1219        }
1220    }
1221}
1222
1223/// A struct that collects invalidations for a given compound selector.
1224struct RelativeSelectorDependencyCollector<'a, 'b> {
1225    map: &'a mut InvalidationMap,
1226    relative_selector_invalidation_map: &'a mut InvalidationMap,
1227    additional_relative_selector_invalidation_map:
1228        &'a mut AdditionalRelativeSelectorInvalidationMap,
1229
1230    /// The document this _complex_ selector is affected by.
1231    ///
1232    /// We don't need to track state per compound selector, since it's global
1233    /// state and it changes for everything.
1234    document_state: &'a mut DocumentState,
1235
1236    /// The current inner relative selector and offset we're iterating.
1237    selector: &'a RelativeSelector<SelectorImpl>,
1238    /// Running combinator for this inner relative selector.
1239    combinator_count: RelativeSelectorCombinatorCount,
1240
1241    /// The stack of next selectors that we have, and at which offset of the
1242    /// sequence.
1243    ///
1244    /// This starts empty. It grows when we find nested :is and :where selector
1245    /// lists. The dependency field is cached and reference counted.
1246    next_selectors: &'a mut NextSelectors,
1247
1248    /// The quirks mode of the document where we're inserting dependencies.
1249    quirks_mode: QuirksMode,
1250
1251    /// State relevant to a given compound selector.
1252    compound_state: PerCompoundState,
1253
1254    /// Attributes relevant to the relative compound selector state.
1255    compound_state_attributes: RelativeSelectorCompoundStateAttributes,
1256
1257    scope_dependencies: &'a mut ScopeSelectorCollectorState<'b>,
1258
1259    /// The allocation error, if we OOM.
1260    alloc_error: &'a mut Option<AllocErr>,
1261}
1262
1263fn add_non_unique_info<C: Collector>(
1264    selector: &Selector<SelectorImpl>,
1265    offset: usize,
1266    collector: &mut C,
1267) -> Result<(), AllocErr> {
1268    // Go through this compound again.
1269    for ss in selector.iter_from(offset) {
1270        if let Component::LocalName(name) = ss {
1271            let dependency = collector.dependency();
1272            add_local_name(name.name.clone(), dependency, collector.type_map())?;
1273            if name.name != name.lower_name {
1274                let dependency = collector.dependency();
1275                add_local_name(name.lower_name.clone(), dependency, collector.type_map())?;
1276            }
1277            return Ok(());
1278        };
1279    }
1280    // Ouch. Add one for *.
1281    collector.any_vec().try_reserve(1)?;
1282    let dependency = collector.dependency();
1283    collector.any_vec().push(dependency);
1284    Ok(())
1285}
1286
1287fn add_ts_pseudo_class_dependency<C: Collector>(
1288    state: TSStateForInvalidation,
1289    quirks_mode: QuirksMode,
1290    collector: &mut C,
1291) -> Result<(), AllocErr> {
1292    if state.is_empty() {
1293        return Ok(());
1294    }
1295    let dependency = collector.dependency();
1296    collector.ts_state_map().insert(
1297        TSStateDependency {
1298            dep: dependency,
1299            state,
1300        },
1301        quirks_mode,
1302    )
1303}
1304
1305impl<'a, 'b> RelativeSelectorDependencyCollector<'a, 'b> {
1306    fn visit_whole_selector(&mut self) -> bool {
1307        let mut iter = self.selector.selector.iter_skip_relative_selector_anchor();
1308        let mut index = 0;
1309
1310        self.additional_relative_selector_invalidation_map
1311            .needs_ancestors_traversal |= match self.selector.match_hint {
1312            RelativeSelectorMatchHint::InNextSiblingSubtree
1313            | RelativeSelectorMatchHint::InSiblingSubtree
1314            | RelativeSelectorMatchHint::InSubtree => true,
1315            _ => false,
1316        };
1317        loop {
1318            // Reset the compound state.
1319            self.compound_state = PerCompoundState::new(index);
1320
1321            let (keep_traversing, index_offset) = visit_all_in_iter_compound(self, &mut iter);
1322
1323            if !keep_traversing {
1324                return false;
1325            }
1326
1327            index += index_offset;
1328
1329            if let Err(err) = add_pseudo_class_dependency(
1330                self.compound_state.element_state,
1331                self.quirks_mode,
1332                self,
1333            ) {
1334                *self.alloc_error = Some(err);
1335                return false;
1336            }
1337
1338            if let Err(err) = add_ts_pseudo_class_dependency(
1339                self.compound_state_attributes.ts_state,
1340                self.quirks_mode,
1341                self,
1342            ) {
1343                *self.alloc_error = Some(err);
1344                return false;
1345            }
1346
1347            if !self.compound_state_attributes.added_entry {
1348                // Not great - we didn't add any uniquely identifiable information.
1349                if let Err(err) =
1350                    add_non_unique_info(&self.selector.selector, self.compound_state.offset, self)
1351                {
1352                    *self.alloc_error = Some(err);
1353                    return false;
1354                }
1355            }
1356
1357            let combinator = iter.next_sequence();
1358            if let Some(c) = combinator {
1359                match c {
1360                    Combinator::Child | Combinator::Descendant => {
1361                        self.combinator_count.child_or_descendants -= 1
1362                    },
1363                    Combinator::NextSibling | Combinator::LaterSibling => {
1364                        self.combinator_count.adjacent_or_next_siblings -= 1
1365                    },
1366                    Combinator::Part | Combinator::PseudoElement | Combinator::SlotAssignment => (),
1367                }
1368            } else {
1369                return true;
1370            }
1371            index += 1; // account for the combinator
1372        }
1373    }
1374}
1375
1376impl<'a, 'b> Collector for RelativeSelectorDependencyCollector<'a, 'b> {
1377    fn dependency(&mut self) -> Dependency {
1378        let scope_dependencies = self.inner_scope_dependencies();
1379        let scope_kind = self.scope_dependencies.scope_kind;
1380
1381        let next = next_dependency(
1382            self.next_selectors,
1383            None,
1384            scope_dependencies.as_ref(),
1385            scope_kind,
1386        );
1387        debug_assert!(
1388            next.as_ref().is_some_and(|d| !matches!(
1389                d.slice()[0].kind,
1390                DependencyInvalidationKind::Relative(_)
1391            )),
1392            "Duplicate relative dependency?"
1393        );
1394        debug_assert!(
1395            next.as_ref().is_some_and(|d| !d.slice().is_empty()),
1396            "Empty dependency?"
1397        );
1398
1399        Dependency {
1400            selector: self.selector.selector.clone(),
1401            selector_offset: self.compound_state.offset,
1402            kind: DependencyInvalidationKind::Relative(
1403                match self.combinator_count.get_match_hint() {
1404                    RelativeSelectorMatchHint::InChild => {
1405                        RelativeDependencyInvalidationKind::Parent
1406                    },
1407                    RelativeSelectorMatchHint::InSubtree => {
1408                        RelativeDependencyInvalidationKind::Ancestors
1409                    },
1410                    RelativeSelectorMatchHint::InNextSibling => {
1411                        RelativeDependencyInvalidationKind::PrevSibling
1412                    },
1413                    RelativeSelectorMatchHint::InSibling => {
1414                        RelativeDependencyInvalidationKind::EarlierSibling
1415                    },
1416                    RelativeSelectorMatchHint::InNextSiblingSubtree => {
1417                        RelativeDependencyInvalidationKind::AncestorPrevSibling
1418                    },
1419                    RelativeSelectorMatchHint::InSiblingSubtree => {
1420                        RelativeDependencyInvalidationKind::AncestorEarlierSibling
1421                    },
1422                },
1423            ),
1424            next,
1425        }
1426    }
1427
1428    fn id_map(&mut self) -> &mut IdOrClassDependencyMap {
1429        &mut self.relative_selector_invalidation_map.id_to_selector
1430    }
1431
1432    fn class_map(&mut self) -> &mut IdOrClassDependencyMap {
1433        &mut self.relative_selector_invalidation_map.class_to_selector
1434    }
1435
1436    fn state_map(&mut self) -> &mut StateDependencyMap {
1437        &mut self
1438            .relative_selector_invalidation_map
1439            .state_affecting_selectors
1440    }
1441
1442    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap {
1443        &mut self
1444            .relative_selector_invalidation_map
1445            .other_attribute_affecting_selectors
1446    }
1447
1448    fn custom_state_map(&mut self) -> &mut CustomStateDependencyMap {
1449        &mut self
1450            .relative_selector_invalidation_map
1451            .custom_state_affecting_selectors
1452    }
1453
1454    fn inner_scope_dependencies(&self) -> Option<ThinArc<(), Dependency>> {
1455        self.scope_dependencies.inner_dependencies.clone()
1456    }
1457
1458    fn this_scope_dependencies(&mut self) -> &mut Option<Vec<Dependency>> {
1459        &mut self.scope_dependencies.this_dependencies
1460    }
1461
1462    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState) {
1463        self.compound_state.element_state |= element_state;
1464        *self.document_state |= document_state;
1465    }
1466
1467    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
1468        &mut self
1469            .additional_relative_selector_invalidation_map
1470            .type_to_selector
1471    }
1472
1473    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
1474        &mut self
1475            .additional_relative_selector_invalidation_map
1476            .ts_state_to_selector
1477    }
1478
1479    fn any_vec(&mut self) -> &mut AnyDependencyMap {
1480        &mut self
1481            .additional_relative_selector_invalidation_map
1482            .any_to_selector
1483    }
1484}
1485
1486enum ComponentVisitResult {
1487    /// This component is not relevant for building up the invalidation map.
1488    IsIrrelevant,
1489    /// This component has been added to the invalidation map. Any additional
1490    /// tree-structural pseudo-class dependency is also included, if required.
1491    Handled(TSStateForInvalidation),
1492}
1493
1494#[inline(always)]
1495fn on_simple_selector<C: Collector>(
1496    s: &Component<SelectorImpl>,
1497    quirks_mode: QuirksMode,
1498    collector: &mut C,
1499) -> Result<ComponentVisitResult, AllocErr> {
1500    match *s {
1501        Component::ID(..) | Component::Class(..) => {
1502            on_id_or_class(s, quirks_mode, collector)?;
1503            Ok(ComponentVisitResult::Handled(
1504                TSStateForInvalidation::empty(),
1505            ))
1506        },
1507        Component::ImplicitScope | Component::Scope => {
1508            on_scope(collector)?;
1509            Ok(ComponentVisitResult::Handled(
1510                TSStateForInvalidation::empty(),
1511            ))
1512        },
1513        Component::NonTSPseudoClass(ref pc) => {
1514            on_pseudo_class(pc, collector)?;
1515            Ok(ComponentVisitResult::Handled(
1516                TSStateForInvalidation::empty(),
1517            ))
1518        },
1519        Component::Empty => Ok(ComponentVisitResult::Handled(TSStateForInvalidation::EMPTY)),
1520        Component::Nth(data) => {
1521            let kind = if data.is_simple_edge() {
1522                if data.ty.is_from_end() {
1523                    TSStateForInvalidation::NTH_EDGE_LAST
1524                } else {
1525                    TSStateForInvalidation::NTH_EDGE_FIRST
1526                }
1527            } else {
1528                TSStateForInvalidation::NTH
1529            };
1530            Ok(ComponentVisitResult::Handled(kind))
1531        },
1532        Component::RelativeSelectorAnchor => unreachable!("Should not visit this far"),
1533        _ => Ok(ComponentVisitResult::IsIrrelevant),
1534    }
1535}
1536
1537impl<'a, 'b> SelectorVisitor for RelativeSelectorDependencyCollector<'a, 'b> {
1538    type Impl = SelectorImpl;
1539
1540    fn visit_selector_list(
1541        &mut self,
1542        _list_kind: SelectorListKind,
1543        list: &[Selector<SelectorImpl>],
1544    ) -> bool {
1545        let mut next_stack = NextSelectors::new();
1546        let next_dependency = ThinArc::from_header_and_iter((), [self.dependency()].into_iter());
1547        for selector in list {
1548            let mut iter = selector.iter();
1549            let saved_added_entry = self.compound_state_attributes.added_entry;
1550
1551            let (keep_traversing, mut index) = visit_all_in_iter_compound(self, &mut iter);
1552
1553            if !keep_traversing {
1554                return false;
1555            }
1556
1557            let combinator = iter.next_sequence();
1558
1559            // We want to preserve added_entry, to handle all DOM manipulations
1560            // correctly. For example, given `.anchor:has(:not(.foo))`, and a
1561            // DOM tree `.anchor > .foo`, insertion of _any_ element without
1562            // `.foo` as `.anchor`'s child must trigger an invalidation.
1563            self.compound_state_attributes.added_entry = saved_added_entry;
1564            if combinator.is_none() {
1565                continue;
1566            }
1567
1568            index += 1; // account for the combinator.
1569
1570            let mut nested = SelectorDependencyCollector {
1571                map: &mut *self.map,
1572                relative_selector_invalidation_map: &mut *self.relative_selector_invalidation_map,
1573                additional_relative_selector_invalidation_map: self
1574                    .additional_relative_selector_invalidation_map,
1575                document_state: &mut *self.document_state,
1576                selector,
1577                next_selectors: &mut next_stack,
1578                quirks_mode: self.quirks_mode,
1579                compound_state: PerCompoundState::new(index),
1580                relative_inner_collector: Some(RelativeSelectorInnerCollectorState {
1581                    next_dependency: &next_dependency,
1582                    relative_compound_state: RelativeSelectorCompoundStateAttributes::new(),
1583                }),
1584                scope_dependencies: self.scope_dependencies,
1585                alloc_error: &mut *self.alloc_error,
1586            };
1587            if !nested.visit_whole_selector_from(iter, index) {
1588                return false;
1589            }
1590        }
1591        true
1592    }
1593
1594    fn visit_relative_selector_list(
1595        &mut self,
1596        _list: &[selectors::parser::RelativeSelector<Self::Impl>],
1597    ) -> bool {
1598        // Ignore nested relative selectors. These can happen as a result of nesting.
1599        true
1600    }
1601
1602    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
1603        match on_simple_selector(s, self.quirks_mode, self) {
1604            Ok(result) => {
1605                if let ComponentVisitResult::Handled(state) = result {
1606                    self.compound_state_attributes.added_entry = true;
1607                    self.compound_state_attributes.ts_state.insert(state);
1608                }
1609                true
1610            },
1611            Err(err) => {
1612                *self.alloc_error = Some(err);
1613                false
1614            },
1615        }
1616    }
1617
1618    fn visit_attribute_selector(
1619        &mut self,
1620        _: &NamespaceConstraint<&Namespace>,
1621        local_name: &LocalName,
1622        local_name_lower: &LocalName,
1623    ) -> bool {
1624        self.compound_state_attributes.added_entry = true;
1625        if let Err(err) = on_attribute(local_name, local_name_lower, self) {
1626            *self.alloc_error = Some(err);
1627            return false;
1628        }
1629        true
1630    }
1631}
style/invalidation/element/invalidation_map.rs

style/invalidation/element/
invalidation_map.rs
