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

style/invalidation/element/
invalidation_map.rs
