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