invalidator.rs (53957B)
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 //! The struct that takes care of encapsulating all the logic on where and how 6 //! element styles need to be invalidated. 7 8 use crate::context::StackLimitChecker; 9 use crate::dom::{TElement, TNode, TShadowRoot}; 10 use crate::invalidation::element::invalidation_map::{ 11 Dependency, DependencyInvalidationKind, NormalDependencyInvalidationKind, 12 RelativeDependencyInvalidationKind, ScopeDependencyInvalidationKind, 13 }; 14 use selectors::matching::matches_compound_selector_from; 15 use selectors::matching::{CompoundSelectorMatchingResult, MatchingContext}; 16 use selectors::parser::{Combinator, Component, Selector, SelectorVisitor}; 17 use selectors::{OpaqueElement, SelectorImpl}; 18 use smallvec::{smallvec, SmallVec}; 19 use std::fmt; 20 use std::fmt::Write; 21 22 struct SiblingInfo<E> 23 where 24 E: TElement, 25 { 26 affected: E, 27 prev_sibling: Option<E>, 28 next_sibling: Option<E>, 29 } 30 31 /// Traversal mapping for elements under consideration. It acts like a snapshot map, 32 /// though this only "maps" one element at most. 33 /// For general invalidations, this has no effect, especially since when 34 /// DOM mutates, the mutation's effect should not escape the subtree being mutated. 35 /// This is not the case for relative selectors, unfortunately, so we may end up 36 /// traversing a portion of the DOM tree that mutated. In case the mutation is removal, 37 /// its sibling relation is severed by the time the invalidation happens. This structure 38 /// recovers that relation. Note - it assumes that there is only one element under this 39 /// effect. 40 pub struct SiblingTraversalMap<E> 41 where 42 E: TElement, 43 { 44 info: Option<SiblingInfo<E>>, 45 } 46 47 impl<E> Default for SiblingTraversalMap<E> 48 where 49 E: TElement, 50 { 51 fn default() -> Self { 52 Self { info: None } 53 } 54 } 55 56 impl<E> SiblingTraversalMap<E> 57 where 58 E: TElement, 59 { 60 /// Create a new traversal map with the affected element. 61 pub fn new(affected: E, prev_sibling: Option<E>, next_sibling: Option<E>) -> Self { 62 Self { 63 info: Some(SiblingInfo { 64 affected, 65 prev_sibling, 66 next_sibling, 67 }), 68 } 69 } 70 71 /// Get the element's previous sibling element. 72 pub fn next_sibling_for(&self, element: &E) -> Option<E> { 73 if let Some(ref info) = self.info { 74 if *element == info.affected { 75 return info.next_sibling; 76 } 77 } 78 element.next_sibling_element() 79 } 80 81 /// Get the element's previous sibling element. 82 pub fn prev_sibling_for(&self, element: &E) -> Option<E> { 83 if let Some(ref info) = self.info { 84 if *element == info.affected { 85 return info.prev_sibling; 86 } 87 } 88 element.prev_sibling_element() 89 } 90 } 91 92 /// A trait to abstract the collection of invalidations for a given pass. 93 pub trait InvalidationProcessor<'a, 'b, E> 94 where 95 E: TElement, 96 { 97 /// Whether an invalidation that contains only a pseudo-element selector 98 /// like ::before or ::after triggers invalidation of the element that would 99 /// originate it. 100 fn invalidates_on_pseudo_element(&self) -> bool { 101 false 102 } 103 104 /// Whether the invalidation processor only cares about light-tree 105 /// descendants of a given element, that is, doesn't invalidate 106 /// pseudo-elements, NAC, shadow dom... 107 fn light_tree_only(&self) -> bool { 108 false 109 } 110 111 /// When a dependency from a :where or :is selector matches, it may still be 112 /// the case that we don't need to invalidate the full style. Consider the 113 /// case of: 114 /// 115 /// div .foo:where(.bar *, .baz) .qux 116 /// 117 /// We can get to the `*` part after a .bar class change, but you only need 118 /// to restyle the element if it also matches .foo. 119 /// 120 /// Similarly, you only need to restyle .baz if the whole result of matching 121 /// the selector changes. 122 /// 123 /// This function is called to check the result of matching the "outer" 124 /// dependency that we generate for the parent of the `:where` selector, 125 /// that is, in the case above it should match 126 /// `div .foo:where(.bar *, .baz)`. 127 /// 128 /// `scope` is set to `Some()` if this dependency follows a scope invalidation 129 /// Matching context should be adjusted accordingly with `nest_for_scope`. 130 /// 131 /// Returning true unconditionally here is over-optimistic and may 132 /// over-invalidate. 133 fn check_outer_dependency( 134 &mut self, 135 dependency: &Dependency, 136 element: E, 137 scope: Option<OpaqueElement>, 138 ) -> bool; 139 140 /// The matching context that should be used to process invalidations. 141 fn matching_context(&mut self) -> &mut MatchingContext<'b, E::Impl>; 142 143 /// The traversal map that should be used to process invalidations. 144 fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E>; 145 146 /// Collect invalidations for a given element's descendants and siblings. 147 /// 148 /// Returns whether the element itself was invalidated. 149 fn collect_invalidations( 150 &mut self, 151 element: E, 152 self_invalidations: &mut InvalidationVector<'a>, 153 descendant_invalidations: &mut DescendantInvalidationLists<'a>, 154 sibling_invalidations: &mut InvalidationVector<'a>, 155 ) -> bool; 156 157 /// Returns whether the invalidation process should process the descendants 158 /// of the given element. 159 fn should_process_descendants(&mut self, element: E) -> bool; 160 161 /// Executes an arbitrary action when the recursion limit is exceded (if 162 /// any). 163 fn recursion_limit_exceeded(&mut self, element: E); 164 165 /// Executes an action when `Self` is invalidated. 166 fn invalidated_self(&mut self, element: E); 167 168 /// Executes an action when `sibling` is invalidated as a sibling of 169 /// `of`. 170 fn invalidated_sibling(&mut self, sibling: E, of: E); 171 172 /// Executes an action when any descendant of `Self` is invalidated. 173 fn invalidated_descendants(&mut self, element: E, child: E); 174 175 /// Executes an action when an element in a relative selector is reached. 176 /// Lets the dependency to be borrowed for further processing out of the 177 /// invalidation traversal. 178 fn found_relative_selector_invalidation( 179 &mut self, 180 _element: E, 181 _kind: RelativeDependencyInvalidationKind, 182 _relative_dependency: &'a Dependency, 183 ) { 184 debug_assert!(false, "Reached relative selector dependency"); 185 } 186 } 187 188 /// Different invalidation lists for descendants. 189 #[derive(Debug, Default)] 190 pub struct DescendantInvalidationLists<'a> { 191 /// Invalidations for normal DOM children and pseudo-elements. 192 /// 193 /// TODO(emilio): Having a list of invalidations just for pseudo-elements 194 /// may save some work here and there. 195 pub dom_descendants: InvalidationVector<'a>, 196 /// Invalidations for slotted children of an element. 197 pub slotted_descendants: InvalidationVector<'a>, 198 /// Invalidations for ::part()s of an element. 199 pub parts: InvalidationVector<'a>, 200 } 201 202 impl<'a> DescendantInvalidationLists<'a> { 203 fn is_empty(&self) -> bool { 204 self.dom_descendants.is_empty() 205 && self.slotted_descendants.is_empty() 206 && self.parts.is_empty() 207 } 208 } 209 210 /// The struct that takes care of encapsulating all the logic on where and how 211 /// element styles need to be invalidated. 212 pub struct TreeStyleInvalidator<'a, 'b, 'c, E, P: 'a> 213 where 214 'b: 'a, 215 E: TElement, 216 P: InvalidationProcessor<'b, 'c, E>, 217 { 218 element: E, 219 stack_limit_checker: Option<&'a StackLimitChecker>, 220 processor: &'a mut P, 221 _marker: std::marker::PhantomData<(&'b (), &'c ())>, 222 } 223 224 /// A vector of invalidations, optimized for small invalidation sets. 225 pub type InvalidationVector<'a> = SmallVec<[Invalidation<'a>; 10]>; 226 227 /// The kind of descendant invalidation we're processing. 228 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 229 enum DescendantInvalidationKind { 230 /// A DOM descendant invalidation. 231 Dom, 232 /// A ::slotted() descendant invalidation. 233 Slotted, 234 /// A ::part() descendant invalidation. 235 Part, 236 } 237 238 /// The kind of invalidation we're processing. 239 /// 240 /// We can use this to avoid pushing invalidations of the same kind to our 241 /// descendants or siblings. 242 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 243 enum InvalidationKind { 244 Descendant(DescendantInvalidationKind), 245 Sibling, 246 } 247 248 /// The kind of traversal an invalidation requires. 249 pub enum InvalidationAddOverride { 250 /// This invalidation should be added to descendant invalidation 251 Descendant, 252 /// This invalidation should be added to sibling invalidations 253 Sibling, 254 } 255 256 /// An `Invalidation` is a complex selector that describes which elements, 257 /// relative to a current element we are processing, must be restyled. 258 #[derive(Clone)] 259 pub struct Invalidation<'a> { 260 /// The dependency that generated this invalidation. 261 /// 262 /// Note that the offset inside the dependency is not really useful after 263 /// construction. 264 dependency: &'a Dependency, 265 /// The right shadow host from where the rule came from, if any. 266 /// 267 /// This is needed to ensure that we match the selector with the right 268 /// state, as whether some selectors like :host and ::part() match depends 269 /// on it. 270 host: Option<OpaqueElement>, 271 /// The scope element from which this rule comes from, if any. 272 scope: Option<OpaqueElement>, 273 /// The offset of the selector pointing to a compound selector. 274 /// 275 /// This order is a "parse order" offset, that is, zero is the leftmost part 276 /// of the selector written as parsed / serialized. 277 /// 278 /// It is initialized from the offset from `dependency`. 279 offset: usize, 280 /// Whether the invalidation was already matched by any previous sibling or 281 /// ancestor. 282 /// 283 /// If this is the case, we can avoid pushing invalidations generated by 284 /// this one if the generated invalidation is effective for all the siblings 285 /// or descendants after us. 286 matched_by_any_previous: bool, 287 /// Whether this incalidation should always be pushed to next invalidations. 288 /// 289 /// This is useful for overriding invalidations we would otherwise skip. 290 /// e.g @scope(.a){:not(:scope)} where we would need the :not(:scope) 291 /// invalidation to traverse down for all children of the scope root 292 always_effective_for_next_descendant: bool, 293 } 294 295 impl<'a> Invalidation<'a> { 296 /// Create a new invalidation for matching a dependency. 297 pub fn new( 298 dependency: &'a Dependency, 299 host: Option<OpaqueElement>, 300 scope: Option<OpaqueElement>, 301 ) -> Self { 302 debug_assert!( 303 dependency.selector_offset == dependency.selector.len() + 1 304 || dependency.invalidation_kind() 305 != DependencyInvalidationKind::Normal( 306 NormalDependencyInvalidationKind::Element 307 ), 308 "No point to this, if the dependency matched the element we should just invalidate it" 309 ); 310 Self { 311 dependency, 312 host, 313 scope, 314 // + 1 to go past the combinator. 315 offset: dependency.selector.len() + 1 - dependency.selector_offset, 316 matched_by_any_previous: false, 317 always_effective_for_next_descendant: false, 318 } 319 } 320 321 /// Create a new invalidation for matching a dependency from the selector's subject. 322 /// Using this should be avoided whenever possible as it overinvalidates. 323 /// Only use it when it's not possible to match the selector in order due to 324 /// invalidations that don't necessarily start at the pointed compound, such as 325 /// what happens in note_scope_dependency_force_at_subject. 326 pub fn new_subject_invalidation( 327 dependency: &'a Dependency, 328 host: Option<OpaqueElement>, 329 scope: Option<OpaqueElement>, 330 ) -> Self { 331 let mut compound_offset = 0; 332 for s in dependency.selector.iter_raw_match_order() { 333 if s.is_combinator() { 334 break; 335 } 336 compound_offset += 1; 337 } 338 339 Self { 340 dependency, 341 host, 342 scope, 343 offset: dependency.selector.len() - compound_offset, 344 matched_by_any_previous: false, 345 always_effective_for_next_descendant: true, 346 } 347 } 348 349 /// Create a new invalidation for matching a dependency that should always check 350 /// its next descendants. It tends to overinvalidate less than new_subject_invalidation 351 /// but it should also be avoided whenever possible. Specifically used when crossing 352 /// into implicit scope invalidation. 353 pub fn new_always_effective_for_next_descendant( 354 dependency: &'a Dependency, 355 host: Option<OpaqueElement>, 356 scope: Option<OpaqueElement>, 357 ) -> Self { 358 if dependency.selector.is_rightmost(dependency.selector_offset) { 359 return Self::new_subject_invalidation(dependency, host, scope); 360 } 361 362 Self { 363 dependency, 364 host, 365 scope, 366 // + 1 to go past the combinator. 367 offset: dependency.selector.len() + 1 - dependency.selector_offset, 368 matched_by_any_previous: false, 369 always_effective_for_next_descendant: true, 370 } 371 } 372 373 /// Return the combinator to the right of the currently invalidating compound 374 /// Useful for determining whether this invalidation should be pushed to 375 /// sibling or descendant invalidations. 376 pub fn combinator_to_right(&self) -> Combinator { 377 debug_assert_ne!(self.dependency.selector_offset, 0); 378 self.dependency 379 .selector 380 .combinator_at_match_order(self.dependency.selector.len() - self.offset) 381 } 382 383 /// Whether this invalidation is effective for the next sibling or 384 /// descendant after us. 385 fn effective_for_next(&self) -> bool { 386 if self.offset == 0 || self.always_effective_for_next_descendant { 387 return true; 388 } 389 390 // TODO(emilio): For pseudo-elements this should be mostly false, except 391 // for the weird pseudos in <input type="number">. 392 // 393 // We should be able to do better here! 394 match self 395 .dependency 396 .selector 397 .combinator_at_parse_order(self.offset - 1) 398 { 399 Combinator::Descendant | Combinator::LaterSibling | Combinator::PseudoElement => true, 400 Combinator::Part 401 | Combinator::SlotAssignment 402 | Combinator::NextSibling 403 | Combinator::Child => false, 404 } 405 } 406 407 fn kind(&self) -> InvalidationKind { 408 if self.offset == 0 { 409 return InvalidationKind::Descendant(DescendantInvalidationKind::Dom); 410 } 411 412 match self 413 .dependency 414 .selector 415 .combinator_at_parse_order(self.offset - 1) 416 { 417 Combinator::Child | Combinator::Descendant | Combinator::PseudoElement => { 418 InvalidationKind::Descendant(DescendantInvalidationKind::Dom) 419 }, 420 Combinator::Part => InvalidationKind::Descendant(DescendantInvalidationKind::Part), 421 Combinator::SlotAssignment => { 422 InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) 423 }, 424 Combinator::NextSibling | Combinator::LaterSibling => InvalidationKind::Sibling, 425 } 426 } 427 } 428 429 /// A struct that visits a selector and determines if there is a `:scope` 430 /// component nested withing a negation. eg. :not(:scope) 431 struct NegationScopeVisitor { 432 /// Have we found a negation list yet 433 in_negation: bool, 434 /// Have we found a :scope inside a negation yet 435 found_scope_in_negation: bool, 436 } 437 438 impl NegationScopeVisitor { 439 /// Create a new NegationScopeVisitor 440 fn new() -> Self { 441 Self { 442 in_negation: false, 443 found_scope_in_negation: false, 444 } 445 } 446 447 fn traverse_selector( 448 mut self, 449 selector: &Selector<<NegationScopeVisitor as SelectorVisitor>::Impl>, 450 ) -> bool { 451 selector.visit(&mut self); 452 self.found_scope_in_negation 453 } 454 455 /// Traverse all the next dependencies in an outer dependency until we reach 456 /// 1. :not(* :scope *) 457 /// 2. a scope or relative dependency 458 /// 3. the end of the chain of dependencies 459 /// Return whether or not we encountered :not(* :scope *) 460 fn traverse_dependency(mut self, dependency: &Dependency) -> bool { 461 if dependency.next.is_none() 462 || !matches!( 463 dependency.invalidation_kind(), 464 DependencyInvalidationKind::Normal(..) 465 ) 466 { 467 dependency.selector.visit(&mut self); 468 return self.found_scope_in_negation; 469 } 470 471 let nested_visitor = Self { 472 in_negation: self.in_negation, 473 found_scope_in_negation: false, 474 }; 475 dependency.selector.visit(&mut self); 476 // Has to be normal dependency and next.is_some() 477 nested_visitor.traverse_dependency(&dependency.next.as_ref().unwrap().slice()[0]) 478 } 479 } 480 481 impl SelectorVisitor for NegationScopeVisitor { 482 type Impl = crate::selector_parser::SelectorImpl; 483 484 fn visit_attribute_selector( 485 &mut self, 486 _namespace: &selectors::attr::NamespaceConstraint< 487 &<Self::Impl as SelectorImpl>::NamespaceUrl, 488 >, 489 _local_name: &<Self::Impl as SelectorImpl>::LocalName, 490 _local_name_lower: &<Self::Impl as SelectorImpl>::LocalName, 491 ) -> bool { 492 true 493 } 494 495 fn visit_simple_selector(&mut self, component: &Component<Self::Impl>) -> bool { 496 if self.in_negation { 497 match component { 498 Component::Scope => { 499 self.found_scope_in_negation = true; 500 }, 501 _ => {}, 502 } 503 } 504 true 505 } 506 507 fn visit_relative_selector_list( 508 &mut self, 509 _list: &[selectors::parser::RelativeSelector<Self::Impl>], 510 ) -> bool { 511 true 512 } 513 514 fn visit_selector_list( 515 &mut self, 516 list_kind: selectors::visitor::SelectorListKind, 517 list: &[selectors::parser::Selector<Self::Impl>], 518 ) -> bool { 519 for nested in list { 520 let nested_visitor = Self { 521 in_negation: list_kind.in_negation(), 522 found_scope_in_negation: false, 523 }; 524 525 self.found_scope_in_negation |= nested_visitor.traverse_selector(nested); 526 } 527 true 528 } 529 530 fn visit_complex_selector(&mut self, _combinator_to_right: Option<Combinator>) -> bool { 531 true 532 } 533 } 534 535 /// Determines if we can find a selector in the form of :not(:scope) 536 /// anywhere down the chain of dependencies. 537 pub fn any_next_has_scope_in_negation(dependency: &Dependency) -> bool { 538 let next = match dependency.next.as_ref() { 539 None => return false, 540 Some(l) => l, 541 }; 542 543 next.slice().iter().any(|dep| { 544 let visitor = NegationScopeVisitor::new(); 545 visitor.traverse_dependency(dep) 546 }) 547 } 548 549 impl<'a> fmt::Debug for Invalidation<'a> { 550 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 551 use cssparser::ToCss; 552 553 f.write_str("Invalidation(")?; 554 for component in self 555 .dependency 556 .selector 557 .iter_raw_parse_order_from(self.offset) 558 { 559 if matches!(*component, Component::Combinator(..)) { 560 break; 561 } 562 component.to_css(f)?; 563 } 564 f.write_char(')') 565 } 566 } 567 568 /// The result of processing a single invalidation for a given element. 569 struct ProcessInvalidationResult { 570 /// Whether the element itself was invalidated. 571 invalidated_self: bool, 572 /// Whether the invalidation matched, either invalidating the element or 573 /// generating another invalidation. 574 matched: bool, 575 } 576 577 /// The result of a whole invalidation process for a given element. 578 pub struct InvalidationResult { 579 /// Whether the element itself was invalidated. 580 invalidated_self: bool, 581 /// Whether the element's descendants were invalidated. 582 invalidated_descendants: bool, 583 /// Whether the element's siblings were invalidated. 584 invalidated_siblings: bool, 585 } 586 587 impl InvalidationResult { 588 /// Create an emtpy result. 589 pub fn empty() -> Self { 590 Self { 591 invalidated_self: false, 592 invalidated_descendants: false, 593 invalidated_siblings: false, 594 } 595 } 596 597 /// Whether the invalidation has invalidate the element itself. 598 pub fn has_invalidated_self(&self) -> bool { 599 self.invalidated_self 600 } 601 602 /// Whether the invalidation has invalidate desendants. 603 pub fn has_invalidated_descendants(&self) -> bool { 604 self.invalidated_descendants 605 } 606 607 /// Whether the invalidation has invalidate siblings. 608 pub fn has_invalidated_siblings(&self) -> bool { 609 self.invalidated_siblings 610 } 611 } 612 613 impl<'a, 'b, 'c, E, P: 'a> TreeStyleInvalidator<'a, 'b, 'c, E, P> 614 where 615 'b: 'a, 616 E: TElement, 617 P: InvalidationProcessor<'b, 'c, E>, 618 { 619 /// Trivially constructs a new `TreeStyleInvalidator`. 620 pub fn new( 621 element: E, 622 stack_limit_checker: Option<&'a StackLimitChecker>, 623 processor: &'a mut P, 624 ) -> Self { 625 Self { 626 element, 627 stack_limit_checker, 628 processor, 629 _marker: std::marker::PhantomData, 630 } 631 } 632 633 /// Perform the invalidation pass. 634 pub fn invalidate(mut self) -> InvalidationResult { 635 debug!("StyleTreeInvalidator::invalidate({:?})", self.element); 636 637 let mut self_invalidations = InvalidationVector::new(); 638 let mut descendant_invalidations = DescendantInvalidationLists::default(); 639 let mut sibling_invalidations = InvalidationVector::new(); 640 641 let mut invalidated_self = self.processor.collect_invalidations( 642 self.element, 643 &mut self_invalidations, 644 &mut descendant_invalidations, 645 &mut sibling_invalidations, 646 ); 647 648 debug!("Collected invalidations (self: {}): ", invalidated_self); 649 debug!( 650 " > self: {}, {:?}", 651 self_invalidations.len(), 652 self_invalidations 653 ); 654 debug!(" > descendants: {:?}", descendant_invalidations); 655 debug!( 656 " > siblings: {}, {:?}", 657 sibling_invalidations.len(), 658 sibling_invalidations 659 ); 660 661 let invalidated_self_from_collection = invalidated_self; 662 663 invalidated_self |= self.process_descendant_invalidations( 664 &self_invalidations, 665 &mut descendant_invalidations, 666 &mut sibling_invalidations, 667 DescendantInvalidationKind::Dom, 668 ); 669 670 if invalidated_self && !invalidated_self_from_collection { 671 self.processor.invalidated_self(self.element); 672 } 673 674 let invalidated_descendants = self.invalidate_descendants(&descendant_invalidations); 675 let invalidated_siblings = self.invalidate_siblings(&mut sibling_invalidations); 676 677 InvalidationResult { 678 invalidated_self, 679 invalidated_descendants, 680 invalidated_siblings, 681 } 682 } 683 684 /// Go through later DOM siblings, invalidating style as needed using the 685 /// `sibling_invalidations` list. 686 /// 687 /// Returns whether any sibling's style or any sibling descendant's style 688 /// was invalidated. 689 fn invalidate_siblings(&mut self, sibling_invalidations: &mut InvalidationVector<'b>) -> bool { 690 if sibling_invalidations.is_empty() { 691 return false; 692 } 693 694 let mut current = self 695 .processor 696 .sibling_traversal_map() 697 .next_sibling_for(&self.element); 698 let mut any_invalidated = false; 699 700 while let Some(sibling) = current { 701 let mut sibling_invalidator = 702 TreeStyleInvalidator::new(sibling, self.stack_limit_checker, self.processor); 703 704 let mut invalidations_for_descendants = DescendantInvalidationLists::default(); 705 let invalidated_sibling = sibling_invalidator.process_sibling_invalidations( 706 &mut invalidations_for_descendants, 707 sibling_invalidations, 708 ); 709 710 if invalidated_sibling { 711 sibling_invalidator 712 .processor 713 .invalidated_sibling(sibling, self.element); 714 } 715 716 any_invalidated |= invalidated_sibling; 717 718 any_invalidated |= 719 sibling_invalidator.invalidate_descendants(&invalidations_for_descendants); 720 721 if sibling_invalidations.is_empty() { 722 break; 723 } 724 725 current = self 726 .processor 727 .sibling_traversal_map() 728 .next_sibling_for(&sibling); 729 } 730 731 any_invalidated 732 } 733 734 fn invalidate_pseudo_element_or_nac( 735 &mut self, 736 child: E, 737 invalidations: &[Invalidation<'b>], 738 ) -> bool { 739 let mut sibling_invalidations = InvalidationVector::new(); 740 741 let result = self.invalidate_child( 742 child, 743 invalidations, 744 &mut sibling_invalidations, 745 DescendantInvalidationKind::Dom, 746 ); 747 748 // Roots of NAC subtrees can indeed generate sibling invalidations, but 749 // they can be just ignored, since they have no siblings. 750 // 751 // Note that we can end up testing selectors that wouldn't end up 752 // matching due to this being NAC, like those coming from document 753 // rules, but we overinvalidate instead of checking this. 754 755 result 756 } 757 758 /// Invalidate a child and recurse down invalidating its descendants if 759 /// needed. 760 fn invalidate_child( 761 &mut self, 762 child: E, 763 invalidations: &[Invalidation<'b>], 764 sibling_invalidations: &mut InvalidationVector<'b>, 765 descendant_invalidation_kind: DescendantInvalidationKind, 766 ) -> bool { 767 let mut invalidations_for_descendants = DescendantInvalidationLists::default(); 768 769 let mut invalidated_child = false; 770 let invalidated_descendants = { 771 let mut child_invalidator = 772 TreeStyleInvalidator::new(child, self.stack_limit_checker, self.processor); 773 774 invalidated_child |= child_invalidator.process_sibling_invalidations( 775 &mut invalidations_for_descendants, 776 sibling_invalidations, 777 ); 778 779 invalidated_child |= child_invalidator.process_descendant_invalidations( 780 invalidations, 781 &mut invalidations_for_descendants, 782 sibling_invalidations, 783 descendant_invalidation_kind, 784 ); 785 786 if invalidated_child { 787 child_invalidator.processor.invalidated_self(child); 788 } 789 790 child_invalidator.invalidate_descendants(&invalidations_for_descendants) 791 }; 792 793 // The child may not be a flattened tree child of the current element, 794 // but may be arbitrarily deep. 795 // 796 // Since we keep the traversal flags in terms of the flattened tree, 797 // we need to propagate it as appropriate. 798 if invalidated_child || invalidated_descendants { 799 self.processor.invalidated_descendants(self.element, child); 800 } 801 802 invalidated_child || invalidated_descendants 803 } 804 805 fn invalidate_nac(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 806 let mut any_nac_root = false; 807 808 let element = self.element; 809 element.each_anonymous_content_child(|nac| { 810 any_nac_root |= self.invalidate_pseudo_element_or_nac(nac, invalidations); 811 }); 812 813 any_nac_root 814 } 815 816 // NB: It's important that this operates on DOM children, which is what 817 // selector-matching operates on. 818 fn invalidate_dom_descendants_of( 819 &mut self, 820 parent: E::ConcreteNode, 821 invalidations: &[Invalidation<'b>], 822 ) -> bool { 823 let mut any_descendant = false; 824 825 let mut sibling_invalidations = InvalidationVector::new(); 826 for child in parent.dom_children() { 827 let child = match child.as_element() { 828 Some(e) => e, 829 None => continue, 830 }; 831 832 any_descendant |= self.invalidate_child( 833 child, 834 invalidations, 835 &mut sibling_invalidations, 836 DescendantInvalidationKind::Dom, 837 ); 838 } 839 840 any_descendant 841 } 842 843 fn invalidate_parts_in_shadow_tree( 844 &mut self, 845 shadow: <E::ConcreteNode as TNode>::ConcreteShadowRoot, 846 invalidations: &[Invalidation<'b>], 847 ) -> bool { 848 debug_assert!(!invalidations.is_empty()); 849 850 let mut any = false; 851 let mut sibling_invalidations = InvalidationVector::new(); 852 853 for node in shadow.as_node().dom_descendants() { 854 let element = match node.as_element() { 855 Some(e) => e, 856 None => continue, 857 }; 858 859 if element.has_part_attr() { 860 any |= self.invalidate_child( 861 element, 862 invalidations, 863 &mut sibling_invalidations, 864 DescendantInvalidationKind::Part, 865 ); 866 debug_assert!( 867 sibling_invalidations.is_empty(), 868 "::part() shouldn't have sibling combinators to the right, \ 869 this makes no sense! {:?}", 870 sibling_invalidations 871 ); 872 } 873 874 if let Some(shadow) = element.shadow_root() { 875 if element.exports_any_part() { 876 any |= self.invalidate_parts_in_shadow_tree(shadow, invalidations) 877 } 878 } 879 } 880 881 any 882 } 883 884 fn invalidate_parts(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 885 if invalidations.is_empty() { 886 return false; 887 } 888 889 let shadow = match self.element.shadow_root() { 890 Some(s) => s, 891 None => return false, 892 }; 893 894 self.invalidate_parts_in_shadow_tree(shadow, invalidations) 895 } 896 897 fn invalidate_slotted_elements(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 898 if invalidations.is_empty() { 899 return false; 900 } 901 902 let slot = self.element; 903 self.invalidate_slotted_elements_in_slot(slot, invalidations) 904 } 905 906 fn invalidate_slotted_elements_in_slot( 907 &mut self, 908 slot: E, 909 invalidations: &[Invalidation<'b>], 910 ) -> bool { 911 let mut any = false; 912 913 let mut sibling_invalidations = InvalidationVector::new(); 914 for node in slot.slotted_nodes() { 915 let element = match node.as_element() { 916 Some(e) => e, 917 None => continue, 918 }; 919 920 if element.is_html_slot_element() { 921 any |= self.invalidate_slotted_elements_in_slot(element, invalidations); 922 } else { 923 any |= self.invalidate_child( 924 element, 925 invalidations, 926 &mut sibling_invalidations, 927 DescendantInvalidationKind::Slotted, 928 ); 929 } 930 931 debug_assert!( 932 sibling_invalidations.is_empty(), 933 "::slotted() shouldn't have sibling combinators to the right, \ 934 this makes no sense! {:?}", 935 sibling_invalidations 936 ); 937 } 938 939 any 940 } 941 942 fn invalidate_non_slotted_descendants(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 943 if invalidations.is_empty() { 944 return false; 945 } 946 947 if self.processor.light_tree_only() { 948 let node = self.element.as_node(); 949 return self.invalidate_dom_descendants_of(node, invalidations); 950 } 951 952 let mut any_descendant = false; 953 954 // NOTE(emilio): This is only needed for Shadow DOM to invalidate 955 // correctly on :host(..) changes. Instead of doing this, we could add 956 // a third kind of invalidation list that walks shadow root children, 957 // but it's not clear it's worth it. 958 // 959 // Also, it's needed as of right now for document state invalidation, 960 // where we rely on iterating every element that ends up in the composed 961 // doc, but we could fix that invalidating per subtree. 962 if let Some(root) = self.element.shadow_root() { 963 any_descendant |= self.invalidate_dom_descendants_of(root.as_node(), invalidations); 964 } 965 966 any_descendant |= self.invalidate_dom_descendants_of(self.element.as_node(), invalidations); 967 968 any_descendant |= self.invalidate_nac(invalidations); 969 970 any_descendant 971 } 972 973 /// Given the descendant invalidation lists, go through the current 974 /// element's descendants, and invalidate style on them. 975 fn invalidate_descendants(&mut self, invalidations: &DescendantInvalidationLists<'b>) -> bool { 976 if invalidations.is_empty() { 977 return false; 978 } 979 980 debug!( 981 "StyleTreeInvalidator::invalidate_descendants({:?})", 982 self.element 983 ); 984 debug!(" > {:?}", invalidations); 985 986 let should_process = self.processor.should_process_descendants(self.element); 987 988 if !should_process { 989 return false; 990 } 991 992 if let Some(checker) = self.stack_limit_checker { 993 if checker.limit_exceeded() { 994 self.processor.recursion_limit_exceeded(self.element); 995 return true; 996 } 997 } 998 999 let mut any_descendant = false; 1000 1001 any_descendant |= self.invalidate_non_slotted_descendants(&invalidations.dom_descendants); 1002 any_descendant |= self.invalidate_slotted_elements(&invalidations.slotted_descendants); 1003 any_descendant |= self.invalidate_parts(&invalidations.parts); 1004 1005 any_descendant 1006 } 1007 1008 /// Process the given sibling invalidations coming from our previous 1009 /// sibling. 1010 /// 1011 /// The sibling invalidations are somewhat special because they can be 1012 /// modified on the fly. New invalidations may be added and removed. 1013 /// 1014 /// In particular, all descendants get the same set of invalidations from 1015 /// the parent, but the invalidations from a given sibling depend on the 1016 /// ones we got from the previous one. 1017 /// 1018 /// Returns whether invalidated the current element's style. 1019 fn process_sibling_invalidations( 1020 &mut self, 1021 descendant_invalidations: &mut DescendantInvalidationLists<'b>, 1022 sibling_invalidations: &mut InvalidationVector<'b>, 1023 ) -> bool { 1024 let mut i = 0; 1025 let mut new_sibling_invalidations = InvalidationVector::new(); 1026 let mut invalidated_self = false; 1027 1028 while i < sibling_invalidations.len() { 1029 let result = self.process_invalidation( 1030 &sibling_invalidations[i], 1031 descendant_invalidations, 1032 &mut new_sibling_invalidations, 1033 InvalidationKind::Sibling, 1034 ); 1035 1036 invalidated_self |= result.invalidated_self; 1037 sibling_invalidations[i].matched_by_any_previous |= result.matched; 1038 if sibling_invalidations[i].effective_for_next() { 1039 i += 1; 1040 } else { 1041 sibling_invalidations.remove(i); 1042 } 1043 } 1044 1045 sibling_invalidations.extend(new_sibling_invalidations.drain(..)); 1046 invalidated_self 1047 } 1048 1049 /// Process a given invalidation list coming from our parent, 1050 /// adding to `descendant_invalidations` and `sibling_invalidations` as 1051 /// needed. 1052 /// 1053 /// Returns whether our style was invalidated as a result. 1054 fn process_descendant_invalidations( 1055 &mut self, 1056 invalidations: &[Invalidation<'b>], 1057 descendant_invalidations: &mut DescendantInvalidationLists<'b>, 1058 sibling_invalidations: &mut InvalidationVector<'b>, 1059 descendant_invalidation_kind: DescendantInvalidationKind, 1060 ) -> bool { 1061 let mut invalidated = false; 1062 1063 for invalidation in invalidations { 1064 let result = self.process_invalidation( 1065 invalidation, 1066 descendant_invalidations, 1067 sibling_invalidations, 1068 InvalidationKind::Descendant(descendant_invalidation_kind), 1069 ); 1070 1071 invalidated |= result.invalidated_self; 1072 if invalidation.effective_for_next() { 1073 let mut invalidation = invalidation.clone(); 1074 invalidation.matched_by_any_previous |= result.matched; 1075 debug_assert_eq!( 1076 descendant_invalidation_kind, 1077 DescendantInvalidationKind::Dom, 1078 "Slotted or part invalidations don't propagate." 1079 ); 1080 descendant_invalidations.dom_descendants.push(invalidation); 1081 } 1082 } 1083 1084 invalidated 1085 } 1086 1087 #[inline(always)] 1088 fn handle_fully_matched( 1089 &mut self, 1090 invalidation: &Invalidation<'b>, 1091 ) -> (ProcessInvalidationResult, SmallVec<[Invalidation<'b>; 1]>) { 1092 debug!(" > Invalidation matched completely"); 1093 // We matched completely. If we're an inner selector now we need 1094 // to go outside our selector and carry on invalidating. 1095 let mut to_process: SmallVec<[&Dependency; 1]> = SmallVec::from([invalidation.dependency]); 1096 let mut next_invalidations: SmallVec<[Invalidation; 1]> = SmallVec::new(); 1097 let mut result = ProcessInvalidationResult { 1098 invalidated_self: false, 1099 matched: false, 1100 }; 1101 1102 while !to_process.is_empty() { 1103 let mut next_dependencies: SmallVec<[&Dependency; 1]> = SmallVec::new(); 1104 1105 while let Some(dependency) = to_process.pop() { 1106 if let DependencyInvalidationKind::Scope(scope_kind) = 1107 dependency.invalidation_kind() 1108 { 1109 if scope_kind == ScopeDependencyInvalidationKind::ImplicitScope { 1110 if let Some(ref deps) = dependency.next { 1111 for dep in deps.as_ref().slice() { 1112 let invalidation = 1113 Invalidation::new_always_effective_for_next_descendant( 1114 dep, 1115 invalidation.host, 1116 invalidation.scope, 1117 ); 1118 next_invalidations.push(invalidation); 1119 } 1120 } 1121 continue; 1122 } 1123 1124 let force_add = any_next_has_scope_in_negation(dependency); 1125 if scope_kind == ScopeDependencyInvalidationKind::ScopeEnd || force_add { 1126 let invalidations = note_scope_dependency_force_at_subject( 1127 dependency, 1128 invalidation.host, 1129 invalidation.scope, 1130 force_add, 1131 ); 1132 1133 next_invalidations.extend(invalidations); 1134 1135 continue; 1136 } 1137 } 1138 1139 match dependency.next { 1140 None => { 1141 result.invalidated_self = true; 1142 result.matched = true; 1143 }, 1144 Some(ref deps) => { 1145 for n in deps.as_ref().slice() { 1146 let invalidation_kind = n.invalidation_kind(); 1147 match invalidation_kind { 1148 DependencyInvalidationKind::FullSelector => unreachable!(), 1149 DependencyInvalidationKind::Normal(_) => next_dependencies.push(n), 1150 //TODO(descalente, bug 1934061): Add specific handling for implicit scopes. 1151 DependencyInvalidationKind::Scope(_) => { 1152 next_dependencies.push(n); 1153 }, 1154 DependencyInvalidationKind::Relative(kind) => { 1155 self.processor.found_relative_selector_invalidation( 1156 self.element, 1157 kind, 1158 n, 1159 ); 1160 result.matched = true; 1161 }, 1162 } 1163 } 1164 }, 1165 }; 1166 } 1167 1168 for cur_dependency in next_dependencies.as_ref() { 1169 let scope = matches!( 1170 invalidation.dependency.invalidation_kind(), 1171 DependencyInvalidationKind::Scope(_) 1172 ) 1173 .then(|| self.element.opaque()); 1174 debug!(" > Checking outer dependency {:?}", cur_dependency); 1175 1176 // The inner selector changed, now check if the full 1177 // previous part of the selector did, before keeping 1178 // checking for descendants. 1179 if !self 1180 .processor 1181 .check_outer_dependency(cur_dependency, self.element, scope) 1182 { 1183 // Dependency is not relevant, do not note it down 1184 continue; 1185 } 1186 1187 let invalidation_kind = cur_dependency.invalidation_kind(); 1188 if matches!( 1189 invalidation_kind, 1190 DependencyInvalidationKind::Normal(NormalDependencyInvalidationKind::Element) 1191 ) || (matches!(invalidation_kind, DependencyInvalidationKind::Scope(_)) 1192 && cur_dependency 1193 .selector 1194 .is_rightmost(cur_dependency.selector_offset)) 1195 { 1196 // Add to dependency stack to process its next dependencies. 1197 to_process.push(cur_dependency); 1198 continue; 1199 } 1200 1201 debug!(" > Generating invalidation"); 1202 next_invalidations.push(Invalidation::new( 1203 cur_dependency, 1204 invalidation.host, 1205 scope, 1206 )); 1207 } 1208 } 1209 return (result, next_invalidations); 1210 } 1211 1212 /// Processes a given invalidation, potentially invalidating the style of 1213 /// the current element. 1214 /// 1215 /// Returns whether invalidated the style of the element, and whether the 1216 /// invalidation should be effective to subsequent siblings or descendants 1217 /// down in the tree. 1218 fn process_invalidation( 1219 &mut self, 1220 invalidation: &Invalidation<'b>, 1221 descendant_invalidations: &mut DescendantInvalidationLists<'b>, 1222 sibling_invalidations: &mut InvalidationVector<'b>, 1223 invalidation_kind: InvalidationKind, 1224 ) -> ProcessInvalidationResult { 1225 debug!( 1226 "TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})", 1227 self.element, invalidation, invalidation_kind 1228 ); 1229 1230 let matching_result = { 1231 let context = self.processor.matching_context(); 1232 context.current_host = invalidation.host; 1233 1234 context.nest_for_scope_condition(invalidation.scope, |ctx| { 1235 matches_compound_selector_from( 1236 &invalidation.dependency.selector, 1237 invalidation.offset, 1238 ctx, 1239 &self.element, 1240 ) 1241 }) 1242 }; 1243 1244 let (mut result, next_invalidations) = match matching_result { 1245 CompoundSelectorMatchingResult::NotMatched => { 1246 return ProcessInvalidationResult { 1247 invalidated_self: false, 1248 matched: false, 1249 } 1250 }, 1251 CompoundSelectorMatchingResult::FullyMatched => self.handle_fully_matched(invalidation), 1252 CompoundSelectorMatchingResult::Matched { 1253 next_combinator_offset, 1254 } => ( 1255 ProcessInvalidationResult { 1256 invalidated_self: false, 1257 matched: true, 1258 }, 1259 smallvec![Invalidation { 1260 dependency: invalidation.dependency, 1261 host: invalidation.host, 1262 scope: invalidation.scope, 1263 offset: next_combinator_offset + 1, 1264 matched_by_any_previous: false, 1265 always_effective_for_next_descendant: invalidation 1266 .always_effective_for_next_descendant, 1267 }], 1268 ), 1269 }; 1270 1271 for next_invalidation in next_invalidations { 1272 let next_invalidation_kind = if next_invalidation.always_effective_for_next_descendant { 1273 InvalidationKind::Descendant(DescendantInvalidationKind::Dom) 1274 } else { 1275 debug_assert_ne!( 1276 next_invalidation.offset, 0, 1277 "Rightmost selectors shouldn't generate more invalidations", 1278 ); 1279 1280 let next_combinator = next_invalidation 1281 .dependency 1282 .selector 1283 .combinator_at_parse_order(next_invalidation.offset - 1); 1284 1285 if matches!(next_combinator, Combinator::PseudoElement) 1286 && self.processor.invalidates_on_pseudo_element() 1287 { 1288 // We need to invalidate the element whenever pseudos change, for 1289 // two reasons: 1290 // 1291 // * Eager pseudo styles are stored as part of the originating 1292 // element's computed style. 1293 // 1294 // * Lazy pseudo-styles might be cached on the originating 1295 // element's pseudo-style cache. 1296 // 1297 // This could be more fine-grained (perhaps with a RESTYLE_PSEUDOS 1298 // hint?). 1299 // 1300 // Note that we'll also restyle the pseudo-element because it would 1301 // match this invalidation. 1302 // 1303 // FIXME: For non-element-backed pseudos this is still not quite 1304 // correct. For example for ::selection even though we invalidate 1305 // the style properly there's nothing that triggers a repaint 1306 // necessarily. Though this matches old Gecko behavior, and the 1307 // ::selection implementation needs to change significantly anyway 1308 // to implement https://github.com/w3c/csswg-drafts/issues/2474 for 1309 // example. 1310 result.invalidated_self = true; 1311 } 1312 1313 debug!( 1314 " > Invalidation matched, next: {:?}, ({:?})", 1315 next_invalidation, next_combinator 1316 ); 1317 1318 next_invalidation.kind() 1319 }; 1320 1321 // We can skip pushing under some circumstances, and we should 1322 // because otherwise the invalidation list could grow 1323 // exponentially. 1324 // 1325 // * First of all, both invalidations need to be of the same 1326 // kind. This is because of how we propagate them going to 1327 // the right of the tree for sibling invalidations and going 1328 // down the tree for children invalidations. A sibling 1329 // invalidation that ends up generating a children 1330 // invalidation ends up (correctly) in five different lists, 1331 // not in the same list five different times. 1332 // 1333 // * Then, the invalidation needs to be matched by a previous 1334 // ancestor/sibling, in order to know that this invalidation 1335 // has been generated already. 1336 // 1337 // * Finally, the new invalidation needs to be 1338 // `effective_for_next()`, in order for us to know that it is 1339 // still in the list, since we remove the dependencies that 1340 // aren't from the lists for our children / siblings. 1341 // 1342 // To go through an example, let's imagine we are processing a 1343 // dom subtree like: 1344 // 1345 // <div><address><div><div/></div></address></div> 1346 // 1347 // And an invalidation list with a single invalidation like: 1348 // 1349 // [div div div] 1350 // 1351 // When we process the invalidation list for the outer div, we 1352 // match it, and generate a `div div` invalidation, so for the 1353 // <address> child we have: 1354 // 1355 // [div div div, div div] 1356 // 1357 // With the first of them marked as `matched`. 1358 // 1359 // When we process the <address> child, we don't match any of 1360 // them, so both invalidations go untouched to our children. 1361 // 1362 // When we process the second <div>, we match _both_ 1363 // invalidations. 1364 // 1365 // However, when matching the first, we can tell it's been 1366 // matched, and not push the corresponding `div div` 1367 // invalidation, since we know it's necessarily already on the 1368 // list. 1369 // 1370 // Thus, without skipping the push, we'll arrive to the 1371 // innermost <div> with: 1372 // 1373 // [div div div, div div, div div, div] 1374 // 1375 // While skipping it, we won't arrive here with duplicating 1376 // dependencies: 1377 // 1378 // [div div div, div div, div] 1379 // 1380 let can_skip_pushing = next_invalidation_kind == invalidation_kind 1381 && invalidation.matched_by_any_previous 1382 && next_invalidation.effective_for_next(); 1383 1384 if can_skip_pushing { 1385 debug!( 1386 " > Can avoid push, since the invalidation had \ 1387 already been matched before" 1388 ); 1389 } else { 1390 match next_invalidation_kind { 1391 InvalidationKind::Descendant(DescendantInvalidationKind::Dom) => { 1392 descendant_invalidations 1393 .dom_descendants 1394 .push(next_invalidation); 1395 }, 1396 InvalidationKind::Descendant(DescendantInvalidationKind::Part) => { 1397 descendant_invalidations.parts.push(next_invalidation); 1398 }, 1399 InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) => { 1400 descendant_invalidations 1401 .slotted_descendants 1402 .push(next_invalidation); 1403 }, 1404 InvalidationKind::Sibling => { 1405 sibling_invalidations.push(next_invalidation); 1406 }, 1407 } 1408 } 1409 } 1410 1411 result 1412 } 1413 } 1414 1415 /// Note the child dependencies of a scope end selector 1416 /// This is necessary because the scope end selector is not bound to :scope 1417 /// 1418 /// e.g @scope to (.b) {:scope .a .c {...}} 1419 /// in the case of the following: 1420 /// <div class=a><div id=x class=b><div class=c></div></div></div> 1421 /// 1422 /// If we toggle class "b" in x, we would have to go up to find .a 1423 /// if we wanted to invalidate correctly. However, this is costly. 1424 /// Instead we just invalidate to the subject of the selector .c 1425 pub fn note_scope_dependency_force_at_subject<'selectors>( 1426 dependency: &'selectors Dependency, 1427 current_host: Option<OpaqueElement>, 1428 scope: Option<OpaqueElement>, 1429 traversed_non_subject: bool, 1430 ) -> Vec<Invalidation<'selectors>> { 1431 let mut invalidations: Vec<Invalidation> = Vec::new(); 1432 if let Some(next) = dependency.next.as_ref() { 1433 for dep in next.slice() { 1434 if dep.selector.is_rightmost(dep.selector_offset) && !traversed_non_subject { 1435 continue; 1436 } 1437 1438 // Follow the normal dependencies as far as we can, leaving 1439 // other kinds to their own invalidation mechanisms elsewhere 1440 if dep.next.is_some() 1441 && matches!( 1442 dep.invalidation_kind(), 1443 DependencyInvalidationKind::Normal(_) 1444 ) 1445 { 1446 invalidations.extend(note_scope_dependency_force_at_subject( 1447 dep, 1448 current_host, 1449 scope, 1450 // Force add from now on because we 1451 // passed through a non-subject compound 1452 true, 1453 )); 1454 } else { 1455 let invalidation = Invalidation::new_subject_invalidation(dep, current_host, scope); 1456 1457 invalidations.push(invalidation); 1458 } 1459 } 1460 } 1461 invalidations 1462 }