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

style/invalidation/element/
invalidation_map.rs
