1use 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#[derive(Clone, Debug, MallocSizeOf)]
45pub struct Dependency {
46    #[ignore_malloc_size_of = "CssRules have primary refs, we measure there"]
48    pub selector: Selector<SelectorImpl>,
49
50    pub selector_offset: usize,
52
53    #[ignore_malloc_size_of = "Arc"]
72    pub next: Option<ThinArc<(), Dependency>>,
73
74    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#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
86pub enum NormalDependencyInvalidationKind {
87    Element,
89    ElementAndDescendants,
94    Descendants,
96    Siblings,
99    SlottedElements,
101    Parts,
103}
104
105#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
109pub enum RelativeDependencyInvalidationKind {
110    Ancestors,
112    Parent,
114    PrevSibling,
116    AncestorPrevSibling,
118    EarlierSibling,
120    AncestorEarlierSibling,
122}
123
124#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
126pub enum ScopeDependencyInvalidationKind {
127    ExplicitScope,
129    ImplicitScope,
131    ScopeEnd,
133}
134
135#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
137pub enum DependencyInvalidationKind {
138    FullSelector,
141    Normal(NormalDependencyInvalidationKind),
143    Relative(RelativeDependencyInvalidationKind),
145    Scope(ScopeDependencyInvalidationKind),
147}
148
149#[derive(Clone, Copy, Debug, MallocSizeOf)]
151pub enum GeneratedInvalidation<'a> {
152    Normal,
154    Scope(Option<&'a ThinArc<(), Dependency>>),
156}
157
158#[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    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    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    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    #[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    pub fn invalidation_kind(&self) -> DependencyInvalidationKind {
236        self.kind
237    }
238
239    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    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#[derive(Clone, Debug, MallocSizeOf)]
271pub struct StateDependency {
272    pub dep: Dependency,
274    pub state: ElementState,
276}
277
278impl SelectorMapEntry for StateDependency {
279    fn selector(&self) -> SelectorIter<'_, SelectorImpl> {
280        self.dep.selector()
281    }
282}
283
284#[derive(Clone, Debug, MallocSizeOf)]
286pub struct DocumentStateDependency {
287    #[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    pub state: DocumentState,
297}
298
299pub type IdOrClassDependencyMap = MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>;
301pub type StateDependencyMap = SelectorMap<StateDependency>;
303pub type LocalNameDependencyMap = PrecomputedHashMap<LocalName, SmallVec<[Dependency; 1]>>;
305pub type CustomStateDependencyMap = PrecomputedHashMap<AtomIdent, SmallVec<[Dependency; 1]>>;
307
308#[derive(Clone, Debug, MallocSizeOf)]
317pub struct InvalidationMap {
318    pub class_to_selector: IdOrClassDependencyMap,
321    pub id_to_selector: IdOrClassDependencyMap,
324    pub state_affecting_selectors: StateDependencyMap,
326    pub document_state_selectors: Vec<DocumentStateDependency>,
328    pub other_attribute_affecting_selectors: LocalNameDependencyMap,
330    pub custom_state_affecting_selectors: CustomStateDependencyMap,
332}
333
334#[derive(Clone, Copy, Debug, MallocSizeOf)]
340pub struct TSStateForInvalidation(u8);
341
342bitflags! {
343    impl TSStateForInvalidation : u8 {
344        const EMPTY = 1 << 0;
347        const NTH = 1 << 1;
349        const NTH_EDGE_FIRST = 1 << 2;
352        const NTH_EDGE_LAST = 1 << 3;
355    }
356}
357
358impl TSStateForInvalidation {
359    pub fn may_be_optimized(&self) -> bool {
362        (Self::EMPTY | Self::NTH_EDGE_FIRST | Self::NTH_EDGE_LAST).contains(*self)
363    }
364}
365
366#[derive(Clone, Debug, MallocSizeOf)]
368pub struct TSStateDependency {
369    pub dep: Dependency,
371    pub state: TSStateForInvalidation,
373}
374
375impl SelectorMapEntry for TSStateDependency {
376    fn selector(&self) -> SelectorIter<'_, SelectorImpl> {
377        self.dep.selector()
378    }
379}
380
381pub type TSStateDependencyMap = SelectorMap<TSStateDependency>;
383pub type AnyDependencyMap = SmallVec<[Dependency; 1]>;
385
386#[derive(Clone, Debug, MallocSizeOf)]
390pub struct AdditionalRelativeSelectorInvalidationMap {
391    pub ts_state_to_selector: TSStateDependencyMap,
393    pub type_to_selector: LocalNameDependencyMap,
395    pub any_to_selector: AnyDependencyMap,
397    pub used: bool,
399    pub needs_ancestors_traversal: bool,
401}
402
403impl AdditionalRelativeSelectorInvalidationMap {
404    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    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    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    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    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    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    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
484pub 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    offset: usize,
541
542    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_dependencies: &'a Option<ThinArc<(), Dependency>>,
568    this_dependencies: Option<Vec<Dependency>>,
570    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    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
592        unreachable!();
593    }
594
595    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
599        unreachable!();
600    }
601
602    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            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
721fn 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
743struct 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    document_state: &'a mut DocumentState,
755
756    selector: &'a Selector<SelectorImpl>,
758
759    next_selectors: &'a mut NextSelectors,
765
766    quirks_mode: QuirksMode,
768
769    compound_state: PerCompoundState,
771
772    relative_inner_collector: Option<RelativeSelectorInnerCollectorState<'b>>,
775
776    scope_dependencies: &'a mut ScopeSelectorCollectorState<'c>,
777
778    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            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            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                    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; }
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            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; 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        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            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
1210struct 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    document_state: &'a mut DocumentState,
1222
1223    selector: &'a RelativeSelector<SelectorImpl>,
1225    combinator_count: RelativeSelectorCombinatorCount,
1227
1228    next_selectors: &'a mut NextSelectors,
1234
1235    quirks_mode: QuirksMode,
1237
1238    compound_state: PerCompoundState,
1240
1241    compound_state_attributes: RelativeSelectorCompoundStateAttributes,
1243
1244    scope_dependencies: &'a mut ScopeSelectorCollectorState<'b>,
1245
1246    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    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    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            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                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; }
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    IsIrrelevant,
1483    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            self.compound_state_attributes.added_entry = saved_added_entry;
1558            if combinator.is_none() {
1559                continue;
1560            }
1561
1562            index += 1; 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        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}