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::{Dependency, DependencyInvalidationKind}; 11 use selectors::matching::matches_compound_selector_from; 12 use selectors::matching::{CompoundSelectorMatchingResult, MatchingContext}; 13 use selectors::parser::{Combinator, Component}; 14 use selectors::OpaqueElement; 15 use smallvec::SmallVec; 16 use std::fmt; 17 18 /// A trait to abstract the collection of invalidations for a given pass. 19 pub trait InvalidationProcessor<'a, E> 20 where 21 E: TElement, 22 { 23 /// Whether an invalidation that contains only an eager pseudo-element 24 /// selector like ::before or ::after triggers invalidation of the element 25 /// that would originate it. invalidates_on_eager_pseudo_element(&self) -> bool26 fn invalidates_on_eager_pseudo_element(&self) -> bool { 27 false 28 } 29 30 /// Whether the invalidation processor only cares about light-tree 31 /// descendants of a given element, that is, doesn't invalidate 32 /// pseudo-elements, NAC, shadow dom... light_tree_only(&self) -> bool33 fn light_tree_only(&self) -> bool { 34 false 35 } 36 37 /// When a dependency from a :where or :is selector matches, it may still be 38 /// the case that we don't need to invalidate the full style. Consider the 39 /// case of: 40 /// 41 /// div .foo:where(.bar *, .baz) .qux 42 /// 43 /// We can get to the `*` part after a .bar class change, but you only need 44 /// to restyle the element if it also matches .foo. 45 /// 46 /// Similarly, you only need to restyle .baz if the whole result of matching 47 /// the selector changes. 48 /// 49 /// This function is called to check the result of matching the "outer" 50 /// dependency that we generate for the parent of the `:where` selector, 51 /// that is, in the case above it should match 52 /// `div .foo:where(.bar *, .baz)`. 53 /// 54 /// Returning true unconditionally here is over-optimistic and may 55 /// over-invalidate. check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool56 fn check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool; 57 58 /// The matching context that should be used to process invalidations. matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl>59 fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl>; 60 61 /// Collect invalidations for a given element's descendants and siblings. 62 /// 63 /// Returns whether the element itself was invalidated. collect_invalidations( &mut self, element: E, self_invalidations: &mut InvalidationVector<'a>, descendant_invalidations: &mut DescendantInvalidationLists<'a>, sibling_invalidations: &mut InvalidationVector<'a>, ) -> bool64 fn collect_invalidations( 65 &mut self, 66 element: E, 67 self_invalidations: &mut InvalidationVector<'a>, 68 descendant_invalidations: &mut DescendantInvalidationLists<'a>, 69 sibling_invalidations: &mut InvalidationVector<'a>, 70 ) -> bool; 71 72 /// Returns whether the invalidation process should process the descendants 73 /// of the given element. should_process_descendants(&mut self, element: E) -> bool74 fn should_process_descendants(&mut self, element: E) -> bool; 75 76 /// Executes an arbitrary action when the recursion limit is exceded (if 77 /// any). recursion_limit_exceeded(&mut self, element: E)78 fn recursion_limit_exceeded(&mut self, element: E); 79 80 /// Executes an action when `Self` is invalidated. invalidated_self(&mut self, element: E)81 fn invalidated_self(&mut self, element: E); 82 83 /// Executes an action when any descendant of `Self` is invalidated. invalidated_descendants(&mut self, element: E, child: E)84 fn invalidated_descendants(&mut self, element: E, child: E); 85 } 86 87 /// Different invalidation lists for descendants. 88 #[derive(Debug, Default)] 89 pub struct DescendantInvalidationLists<'a> { 90 /// Invalidations for normal DOM children and pseudo-elements. 91 /// 92 /// TODO(emilio): Having a list of invalidations just for pseudo-elements 93 /// may save some work here and there. 94 pub dom_descendants: InvalidationVector<'a>, 95 /// Invalidations for slotted children of an element. 96 pub slotted_descendants: InvalidationVector<'a>, 97 /// Invalidations for ::part()s of an element. 98 pub parts: InvalidationVector<'a>, 99 } 100 101 impl<'a> DescendantInvalidationLists<'a> { is_empty(&self) -> bool102 fn is_empty(&self) -> bool { 103 self.dom_descendants.is_empty() && 104 self.slotted_descendants.is_empty() && 105 self.parts.is_empty() 106 } 107 } 108 109 /// The struct that takes care of encapsulating all the logic on where and how 110 /// element styles need to be invalidated. 111 pub struct TreeStyleInvalidator<'a, 'b, E, P: 'a> 112 where 113 'b: 'a, 114 E: TElement, 115 P: InvalidationProcessor<'b, E>, 116 { 117 element: E, 118 stack_limit_checker: Option<&'a StackLimitChecker>, 119 processor: &'a mut P, 120 _marker: ::std::marker::PhantomData<&'b ()>, 121 } 122 123 /// A vector of invalidations, optimized for small invalidation sets. 124 pub type InvalidationVector<'a> = SmallVec<[Invalidation<'a>; 10]>; 125 126 /// The kind of descendant invalidation we're processing. 127 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 128 enum DescendantInvalidationKind { 129 /// A DOM descendant invalidation. 130 Dom, 131 /// A ::slotted() descendant invalidation. 132 Slotted, 133 /// A ::part() descendant invalidation. 134 Part, 135 } 136 137 /// The kind of invalidation we're processing. 138 /// 139 /// We can use this to avoid pushing invalidations of the same kind to our 140 /// descendants or siblings. 141 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 142 enum InvalidationKind { 143 Descendant(DescendantInvalidationKind), 144 Sibling, 145 } 146 147 /// An `Invalidation` is a complex selector that describes which elements, 148 /// relative to a current element we are processing, must be restyled. 149 #[derive(Clone)] 150 pub struct Invalidation<'a> { 151 /// The dependency that generated this invalidation. 152 /// 153 /// Note that the offset inside the dependency is not really useful after 154 /// construction. 155 dependency: &'a Dependency, 156 /// The right shadow host from where the rule came from, if any. 157 /// 158 /// This is needed to ensure that we match the selector with the right 159 /// state, as whether some selectors like :host and ::part() match depends 160 /// on it. 161 scope: Option<OpaqueElement>, 162 /// The offset of the selector pointing to a compound selector. 163 /// 164 /// This order is a "parse order" offset, that is, zero is the leftmost part 165 /// of the selector written as parsed / serialized. 166 /// 167 /// It is initialized from the offset from `dependency`. 168 offset: usize, 169 /// Whether the invalidation was already matched by any previous sibling or 170 /// ancestor. 171 /// 172 /// If this is the case, we can avoid pushing invalidations generated by 173 /// this one if the generated invalidation is effective for all the siblings 174 /// or descendants after us. 175 matched_by_any_previous: bool, 176 } 177 178 impl<'a> Invalidation<'a> { 179 /// Create a new invalidation for matching a dependency. new( dependency: &'a Dependency, scope: Option<OpaqueElement>, ) -> Self180 pub fn new( 181 dependency: &'a Dependency, 182 scope: Option<OpaqueElement>, 183 ) -> Self { 184 debug_assert!( 185 dependency.selector_offset == dependency.selector.len() + 1 || 186 dependency.invalidation_kind() != DependencyInvalidationKind::Element, 187 "No point to this, if the dependency matched the element we should just invalidate it" 188 ); 189 Self { 190 dependency, 191 scope, 192 // + 1 to go past the combinator. 193 offset: dependency.selector.len() + 1 - dependency.selector_offset, 194 matched_by_any_previous: false, 195 } 196 } 197 198 /// Whether this invalidation is effective for the next sibling or 199 /// descendant after us. effective_for_next(&self) -> bool200 fn effective_for_next(&self) -> bool { 201 if self.offset == 0 { 202 return true; 203 } 204 205 // TODO(emilio): For pseudo-elements this should be mostly false, except 206 // for the weird pseudos in <input type="number">. 207 // 208 // We should be able to do better here! 209 match self.dependency.selector.combinator_at_parse_order(self.offset - 1) { 210 Combinator::Descendant | Combinator::LaterSibling | Combinator::PseudoElement => true, 211 Combinator::Part | 212 Combinator::SlotAssignment | 213 Combinator::NextSibling | 214 Combinator::Child => false, 215 } 216 } 217 kind(&self) -> InvalidationKind218 fn kind(&self) -> InvalidationKind { 219 if self.offset == 0 { 220 return InvalidationKind::Descendant(DescendantInvalidationKind::Dom); 221 } 222 223 match self.dependency.selector.combinator_at_parse_order(self.offset - 1) { 224 Combinator::Child | Combinator::Descendant | Combinator::PseudoElement => { 225 InvalidationKind::Descendant(DescendantInvalidationKind::Dom) 226 }, 227 Combinator::Part => InvalidationKind::Descendant(DescendantInvalidationKind::Part), 228 Combinator::SlotAssignment => { 229 InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) 230 }, 231 Combinator::NextSibling | Combinator::LaterSibling => InvalidationKind::Sibling, 232 } 233 } 234 } 235 236 impl<'a> fmt::Debug for Invalidation<'a> { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result237 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 238 use cssparser::ToCss; 239 240 f.write_str("Invalidation(")?; 241 for component in self.dependency.selector.iter_raw_parse_order_from(self.offset) { 242 if matches!(*component, Component::Combinator(..)) { 243 break; 244 } 245 component.to_css(f)?; 246 } 247 f.write_str(")") 248 } 249 } 250 251 /// The result of processing a single invalidation for a given element. 252 struct SingleInvalidationResult { 253 /// Whether the element itself was invalidated. 254 invalidated_self: bool, 255 /// Whether the invalidation matched, either invalidating the element or 256 /// generating another invalidation. 257 matched: bool, 258 } 259 260 /// The result of a whole invalidation process for a given element. 261 pub struct InvalidationResult { 262 /// Whether the element itself was invalidated. 263 invalidated_self: bool, 264 /// Whether the element's descendants were invalidated. 265 invalidated_descendants: bool, 266 /// Whether the element's siblings were invalidated. 267 invalidated_siblings: bool, 268 } 269 270 impl InvalidationResult { 271 /// Create an emtpy result. empty() -> Self272 pub fn empty() -> Self { 273 Self { 274 invalidated_self: false, 275 invalidated_descendants: false, 276 invalidated_siblings: false, 277 } 278 } 279 280 /// Whether the invalidation has invalidate the element itself. has_invalidated_self(&self) -> bool281 pub fn has_invalidated_self(&self) -> bool { 282 self.invalidated_self 283 } 284 285 /// Whether the invalidation has invalidate desendants. has_invalidated_descendants(&self) -> bool286 pub fn has_invalidated_descendants(&self) -> bool { 287 self.invalidated_descendants 288 } 289 290 /// Whether the invalidation has invalidate siblings. has_invalidated_siblings(&self) -> bool291 pub fn has_invalidated_siblings(&self) -> bool { 292 self.invalidated_siblings 293 } 294 } 295 296 impl<'a, 'b, E, P: 'a> TreeStyleInvalidator<'a, 'b, E, P> 297 where 298 'b: 'a, 299 E: TElement, 300 P: InvalidationProcessor<'b, E>, 301 { 302 /// Trivially constructs a new `TreeStyleInvalidator`. new( element: E, stack_limit_checker: Option<&'a StackLimitChecker>, processor: &'a mut P, ) -> Self303 pub fn new( 304 element: E, 305 stack_limit_checker: Option<&'a StackLimitChecker>, 306 processor: &'a mut P, 307 ) -> Self { 308 Self { 309 element, 310 stack_limit_checker, 311 processor, 312 _marker: ::std::marker::PhantomData, 313 } 314 } 315 316 /// Perform the invalidation pass. invalidate(mut self) -> InvalidationResult317 pub fn invalidate(mut self) -> InvalidationResult { 318 debug!("StyleTreeInvalidator::invalidate({:?})", self.element); 319 320 let mut self_invalidations = InvalidationVector::new(); 321 let mut descendant_invalidations = DescendantInvalidationLists::default(); 322 let mut sibling_invalidations = InvalidationVector::new(); 323 324 let mut invalidated_self = self.processor.collect_invalidations( 325 self.element, 326 &mut self_invalidations, 327 &mut descendant_invalidations, 328 &mut sibling_invalidations, 329 ); 330 331 debug!("Collected invalidations (self: {}): ", invalidated_self); 332 debug!( 333 " > self: {}, {:?}", 334 self_invalidations.len(), 335 self_invalidations 336 ); 337 debug!(" > descendants: {:?}", descendant_invalidations); 338 debug!( 339 " > siblings: {}, {:?}", 340 sibling_invalidations.len(), 341 sibling_invalidations 342 ); 343 344 let invalidated_self_from_collection = invalidated_self; 345 346 invalidated_self |= self.process_descendant_invalidations( 347 &self_invalidations, 348 &mut descendant_invalidations, 349 &mut sibling_invalidations, 350 DescendantInvalidationKind::Dom, 351 ); 352 353 if invalidated_self && !invalidated_self_from_collection { 354 self.processor.invalidated_self(self.element); 355 } 356 357 let invalidated_descendants = self.invalidate_descendants(&descendant_invalidations); 358 let invalidated_siblings = self.invalidate_siblings(&mut sibling_invalidations); 359 360 InvalidationResult { 361 invalidated_self, 362 invalidated_descendants, 363 invalidated_siblings, 364 } 365 } 366 367 /// Go through later DOM siblings, invalidating style as needed using the 368 /// `sibling_invalidations` list. 369 /// 370 /// Returns whether any sibling's style or any sibling descendant's style 371 /// was invalidated. invalidate_siblings(&mut self, sibling_invalidations: &mut InvalidationVector<'b>) -> bool372 fn invalidate_siblings(&mut self, sibling_invalidations: &mut InvalidationVector<'b>) -> bool { 373 if sibling_invalidations.is_empty() { 374 return false; 375 } 376 377 let mut current = self.element.next_sibling_element(); 378 let mut any_invalidated = false; 379 380 while let Some(sibling) = current { 381 let mut sibling_invalidator = 382 TreeStyleInvalidator::new(sibling, self.stack_limit_checker, self.processor); 383 384 let mut invalidations_for_descendants = DescendantInvalidationLists::default(); 385 let invalidated_sibling = sibling_invalidator.process_sibling_invalidations( 386 &mut invalidations_for_descendants, 387 sibling_invalidations, 388 ); 389 390 if invalidated_sibling { 391 sibling_invalidator.processor.invalidated_self(sibling); 392 } 393 394 any_invalidated |= invalidated_sibling; 395 396 any_invalidated |= 397 sibling_invalidator.invalidate_descendants(&invalidations_for_descendants); 398 399 if sibling_invalidations.is_empty() { 400 break; 401 } 402 403 current = sibling.next_sibling_element(); 404 } 405 406 any_invalidated 407 } 408 invalidate_pseudo_element_or_nac( &mut self, child: E, invalidations: &[Invalidation<'b>], ) -> bool409 fn invalidate_pseudo_element_or_nac( 410 &mut self, 411 child: E, 412 invalidations: &[Invalidation<'b>], 413 ) -> bool { 414 let mut sibling_invalidations = InvalidationVector::new(); 415 416 let result = self.invalidate_child( 417 child, 418 invalidations, 419 &mut sibling_invalidations, 420 DescendantInvalidationKind::Dom, 421 ); 422 423 // Roots of NAC subtrees can indeed generate sibling invalidations, but 424 // they can be just ignored, since they have no siblings. 425 // 426 // Note that we can end up testing selectors that wouldn't end up 427 // matching due to this being NAC, like those coming from document 428 // rules, but we overinvalidate instead of checking this. 429 430 result 431 } 432 433 /// Invalidate a child and recurse down invalidating its descendants if 434 /// needed. invalidate_child( &mut self, child: E, invalidations: &[Invalidation<'b>], sibling_invalidations: &mut InvalidationVector<'b>, descendant_invalidation_kind: DescendantInvalidationKind, ) -> bool435 fn invalidate_child( 436 &mut self, 437 child: E, 438 invalidations: &[Invalidation<'b>], 439 sibling_invalidations: &mut InvalidationVector<'b>, 440 descendant_invalidation_kind: DescendantInvalidationKind, 441 ) -> bool { 442 let mut invalidations_for_descendants = DescendantInvalidationLists::default(); 443 444 let mut invalidated_child = false; 445 let invalidated_descendants = { 446 let mut child_invalidator = 447 TreeStyleInvalidator::new(child, self.stack_limit_checker, self.processor); 448 449 invalidated_child |= child_invalidator.process_sibling_invalidations( 450 &mut invalidations_for_descendants, 451 sibling_invalidations, 452 ); 453 454 invalidated_child |= child_invalidator.process_descendant_invalidations( 455 invalidations, 456 &mut invalidations_for_descendants, 457 sibling_invalidations, 458 descendant_invalidation_kind, 459 ); 460 461 if invalidated_child { 462 child_invalidator.processor.invalidated_self(child); 463 } 464 465 child_invalidator.invalidate_descendants(&invalidations_for_descendants) 466 }; 467 468 // The child may not be a flattened tree child of the current element, 469 // but may be arbitrarily deep. 470 // 471 // Since we keep the traversal flags in terms of the flattened tree, 472 // we need to propagate it as appropriate. 473 if invalidated_child || invalidated_descendants { 474 self.processor.invalidated_descendants(self.element, child); 475 } 476 477 invalidated_child || invalidated_descendants 478 } 479 invalidate_nac(&mut self, invalidations: &[Invalidation<'b>]) -> bool480 fn invalidate_nac(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 481 let mut any_nac_root = false; 482 483 let element = self.element; 484 element.each_anonymous_content_child(|nac| { 485 any_nac_root |= self.invalidate_pseudo_element_or_nac(nac, invalidations); 486 }); 487 488 any_nac_root 489 } 490 491 // NB: It's important that this operates on DOM children, which is what 492 // selector-matching operates on. invalidate_dom_descendants_of( &mut self, parent: E::ConcreteNode, invalidations: &[Invalidation<'b>], ) -> bool493 fn invalidate_dom_descendants_of( 494 &mut self, 495 parent: E::ConcreteNode, 496 invalidations: &[Invalidation<'b>], 497 ) -> bool { 498 let mut any_descendant = false; 499 500 let mut sibling_invalidations = InvalidationVector::new(); 501 for child in parent.dom_children() { 502 let child = match child.as_element() { 503 Some(e) => e, 504 None => continue, 505 }; 506 507 any_descendant |= self.invalidate_child( 508 child, 509 invalidations, 510 &mut sibling_invalidations, 511 DescendantInvalidationKind::Dom, 512 ); 513 } 514 515 any_descendant 516 } 517 invalidate_parts_in_shadow_tree( &mut self, shadow: <E::ConcreteNode as TNode>::ConcreteShadowRoot, invalidations: &[Invalidation<'b>], ) -> bool518 fn invalidate_parts_in_shadow_tree( 519 &mut self, 520 shadow: <E::ConcreteNode as TNode>::ConcreteShadowRoot, 521 invalidations: &[Invalidation<'b>], 522 ) -> bool { 523 debug_assert!(!invalidations.is_empty()); 524 525 let mut any = false; 526 let mut sibling_invalidations = InvalidationVector::new(); 527 528 for node in shadow.as_node().dom_descendants() { 529 let element = match node.as_element() { 530 Some(e) => e, 531 None => continue, 532 }; 533 534 if element.has_part_attr() { 535 any |= self.invalidate_child( 536 element, 537 invalidations, 538 &mut sibling_invalidations, 539 DescendantInvalidationKind::Part, 540 ); 541 debug_assert!( 542 sibling_invalidations.is_empty(), 543 "::part() shouldn't have sibling combinators to the right, \ 544 this makes no sense! {:?}", 545 sibling_invalidations 546 ); 547 } 548 549 if let Some(shadow) = element.shadow_root() { 550 if element.exports_any_part() { 551 any |= self.invalidate_parts_in_shadow_tree(shadow, invalidations) 552 } 553 } 554 } 555 556 any 557 } 558 invalidate_parts(&mut self, invalidations: &[Invalidation<'b>]) -> bool559 fn invalidate_parts(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 560 if invalidations.is_empty() { 561 return false; 562 } 563 564 let shadow = match self.element.shadow_root() { 565 Some(s) => s, 566 None => return false, 567 }; 568 569 self.invalidate_parts_in_shadow_tree(shadow, invalidations) 570 } 571 invalidate_slotted_elements(&mut self, invalidations: &[Invalidation<'b>]) -> bool572 fn invalidate_slotted_elements(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 573 if invalidations.is_empty() { 574 return false; 575 } 576 577 let slot = self.element; 578 self.invalidate_slotted_elements_in_slot(slot, invalidations) 579 } 580 invalidate_slotted_elements_in_slot( &mut self, slot: E, invalidations: &[Invalidation<'b>], ) -> bool581 fn invalidate_slotted_elements_in_slot( 582 &mut self, 583 slot: E, 584 invalidations: &[Invalidation<'b>], 585 ) -> bool { 586 let mut any = false; 587 588 let mut sibling_invalidations = InvalidationVector::new(); 589 for node in slot.slotted_nodes() { 590 let element = match node.as_element() { 591 Some(e) => e, 592 None => continue, 593 }; 594 595 if element.is_html_slot_element() { 596 any |= self.invalidate_slotted_elements_in_slot(element, invalidations); 597 } else { 598 any |= self.invalidate_child( 599 element, 600 invalidations, 601 &mut sibling_invalidations, 602 DescendantInvalidationKind::Slotted, 603 ); 604 } 605 606 debug_assert!( 607 sibling_invalidations.is_empty(), 608 "::slotted() shouldn't have sibling combinators to the right, \ 609 this makes no sense! {:?}", 610 sibling_invalidations 611 ); 612 } 613 614 any 615 } 616 invalidate_non_slotted_descendants(&mut self, invalidations: &[Invalidation<'b>]) -> bool617 fn invalidate_non_slotted_descendants(&mut self, invalidations: &[Invalidation<'b>]) -> bool { 618 if invalidations.is_empty() { 619 return false; 620 } 621 622 if self.processor.light_tree_only() { 623 let node = self.element.as_node(); 624 return self.invalidate_dom_descendants_of(node, invalidations); 625 } 626 627 let mut any_descendant = false; 628 629 // NOTE(emilio): This is only needed for Shadow DOM to invalidate 630 // correctly on :host(..) changes. Instead of doing this, we could add 631 // a third kind of invalidation list that walks shadow root children, 632 // but it's not clear it's worth it. 633 // 634 // Also, it's needed as of right now for document state invalidation, 635 // where we rely on iterating every element that ends up in the composed 636 // doc, but we could fix that invalidating per subtree. 637 if let Some(root) = self.element.shadow_root() { 638 any_descendant |= self.invalidate_dom_descendants_of(root.as_node(), invalidations); 639 } 640 641 if let Some(marker) = self.element.marker_pseudo_element() { 642 any_descendant |= self.invalidate_pseudo_element_or_nac(marker, invalidations); 643 } 644 645 if let Some(before) = self.element.before_pseudo_element() { 646 any_descendant |= self.invalidate_pseudo_element_or_nac(before, invalidations); 647 } 648 649 let node = self.element.as_node(); 650 any_descendant |= self.invalidate_dom_descendants_of(node, invalidations); 651 652 if let Some(after) = self.element.after_pseudo_element() { 653 any_descendant |= self.invalidate_pseudo_element_or_nac(after, invalidations); 654 } 655 656 any_descendant |= self.invalidate_nac(invalidations); 657 658 any_descendant 659 } 660 661 /// Given the descendant invalidation lists, go through the current 662 /// element's descendants, and invalidate style on them. invalidate_descendants(&mut self, invalidations: &DescendantInvalidationLists<'b>) -> bool663 fn invalidate_descendants(&mut self, invalidations: &DescendantInvalidationLists<'b>) -> bool { 664 if invalidations.is_empty() { 665 return false; 666 } 667 668 debug!( 669 "StyleTreeInvalidator::invalidate_descendants({:?})", 670 self.element 671 ); 672 debug!(" > {:?}", invalidations); 673 674 let should_process = self.processor.should_process_descendants(self.element); 675 676 if !should_process { 677 return false; 678 } 679 680 if let Some(checker) = self.stack_limit_checker { 681 if checker.limit_exceeded() { 682 self.processor.recursion_limit_exceeded(self.element); 683 return true; 684 } 685 } 686 687 let mut any_descendant = false; 688 689 any_descendant |= self.invalidate_non_slotted_descendants(&invalidations.dom_descendants); 690 any_descendant |= self.invalidate_slotted_elements(&invalidations.slotted_descendants); 691 any_descendant |= self.invalidate_parts(&invalidations.parts); 692 693 any_descendant 694 } 695 696 /// Process the given sibling invalidations coming from our previous 697 /// sibling. 698 /// 699 /// The sibling invalidations are somewhat special because they can be 700 /// modified on the fly. New invalidations may be added and removed. 701 /// 702 /// In particular, all descendants get the same set of invalidations from 703 /// the parent, but the invalidations from a given sibling depend on the 704 /// ones we got from the previous one. 705 /// 706 /// Returns whether invalidated the current element's style. process_sibling_invalidations( &mut self, descendant_invalidations: &mut DescendantInvalidationLists<'b>, sibling_invalidations: &mut InvalidationVector<'b>, ) -> bool707 fn process_sibling_invalidations( 708 &mut self, 709 descendant_invalidations: &mut DescendantInvalidationLists<'b>, 710 sibling_invalidations: &mut InvalidationVector<'b>, 711 ) -> bool { 712 let mut i = 0; 713 let mut new_sibling_invalidations = InvalidationVector::new(); 714 let mut invalidated_self = false; 715 716 while i < sibling_invalidations.len() { 717 let result = self.process_invalidation( 718 &sibling_invalidations[i], 719 descendant_invalidations, 720 &mut new_sibling_invalidations, 721 InvalidationKind::Sibling, 722 ); 723 724 invalidated_self |= result.invalidated_self; 725 sibling_invalidations[i].matched_by_any_previous |= result.matched; 726 if sibling_invalidations[i].effective_for_next() { 727 i += 1; 728 } else { 729 sibling_invalidations.remove(i); 730 } 731 } 732 733 sibling_invalidations.extend(new_sibling_invalidations.drain(..)); 734 invalidated_self 735 } 736 737 /// Process a given invalidation list coming from our parent, 738 /// adding to `descendant_invalidations` and `sibling_invalidations` as 739 /// needed. 740 /// 741 /// Returns whether our style was invalidated as a result. process_descendant_invalidations( &mut self, invalidations: &[Invalidation<'b>], descendant_invalidations: &mut DescendantInvalidationLists<'b>, sibling_invalidations: &mut InvalidationVector<'b>, descendant_invalidation_kind: DescendantInvalidationKind, ) -> bool742 fn process_descendant_invalidations( 743 &mut self, 744 invalidations: &[Invalidation<'b>], 745 descendant_invalidations: &mut DescendantInvalidationLists<'b>, 746 sibling_invalidations: &mut InvalidationVector<'b>, 747 descendant_invalidation_kind: DescendantInvalidationKind, 748 ) -> bool { 749 let mut invalidated = false; 750 751 for invalidation in invalidations { 752 let result = self.process_invalidation( 753 invalidation, 754 descendant_invalidations, 755 sibling_invalidations, 756 InvalidationKind::Descendant(descendant_invalidation_kind), 757 ); 758 759 invalidated |= result.invalidated_self; 760 if invalidation.effective_for_next() { 761 let mut invalidation = invalidation.clone(); 762 invalidation.matched_by_any_previous |= result.matched; 763 debug_assert_eq!( 764 descendant_invalidation_kind, 765 DescendantInvalidationKind::Dom, 766 "Slotted or part invalidations don't propagate." 767 ); 768 descendant_invalidations.dom_descendants.push(invalidation); 769 } 770 } 771 772 invalidated 773 } 774 775 /// Processes a given invalidation, potentially invalidating the style of 776 /// the current element. 777 /// 778 /// Returns whether invalidated the style of the element, and whether the 779 /// invalidation should be effective to subsequent siblings or descendants 780 /// down in the tree. process_invalidation( &mut self, invalidation: &Invalidation<'b>, descendant_invalidations: &mut DescendantInvalidationLists<'b>, sibling_invalidations: &mut InvalidationVector<'b>, invalidation_kind: InvalidationKind, ) -> SingleInvalidationResult781 fn process_invalidation( 782 &mut self, 783 invalidation: &Invalidation<'b>, 784 descendant_invalidations: &mut DescendantInvalidationLists<'b>, 785 sibling_invalidations: &mut InvalidationVector<'b>, 786 invalidation_kind: InvalidationKind, 787 ) -> SingleInvalidationResult { 788 debug!( 789 "TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})", 790 self.element, invalidation, invalidation_kind 791 ); 792 793 let matching_result = { 794 let context = self.processor.matching_context(); 795 context.current_host = invalidation.scope; 796 797 matches_compound_selector_from( 798 &invalidation.dependency.selector, 799 invalidation.offset, 800 context, 801 &self.element, 802 ) 803 }; 804 805 let next_invalidation = match matching_result { 806 CompoundSelectorMatchingResult::NotMatched => { 807 return SingleInvalidationResult { 808 invalidated_self: false, 809 matched: false, 810 } 811 }, 812 CompoundSelectorMatchingResult::FullyMatched => { 813 debug!(" > Invalidation matched completely"); 814 // We matched completely. If we're an inner selector now we need 815 // to go outside our selector and carry on invalidating. 816 let mut cur_dependency = invalidation.dependency; 817 loop { 818 cur_dependency = match cur_dependency.parent { 819 None => return SingleInvalidationResult { 820 invalidated_self: true, 821 matched: true, 822 }, 823 Some(ref p) => &**p, 824 }; 825 826 debug!(" > Checking outer dependency {:?}", cur_dependency); 827 828 // The inner selector changed, now check if the full 829 // previous part of the selector did, before keeping 830 // checking for descendants. 831 if !self.processor.check_outer_dependency(cur_dependency, self.element) { 832 return SingleInvalidationResult { 833 invalidated_self: false, 834 matched: false, 835 } 836 } 837 838 if cur_dependency.invalidation_kind() == DependencyInvalidationKind::Element { 839 continue; 840 } 841 842 debug!(" > Generating invalidation"); 843 break Invalidation::new(cur_dependency, invalidation.scope) 844 } 845 }, 846 CompoundSelectorMatchingResult::Matched { 847 next_combinator_offset, 848 } => { 849 Invalidation { 850 dependency: invalidation.dependency, 851 scope: invalidation.scope, 852 offset: next_combinator_offset + 1, 853 matched_by_any_previous: false, 854 } 855 }, 856 }; 857 858 debug_assert_ne!( 859 next_invalidation.offset, 860 0, 861 "Rightmost selectors shouldn't generate more invalidations", 862 ); 863 864 let mut invalidated_self = false; 865 let next_combinator = next_invalidation 866 .dependency 867 .selector 868 .combinator_at_parse_order(next_invalidation.offset - 1); 869 870 if matches!(next_combinator, Combinator::PseudoElement) { 871 // This will usually be the very next component, except for 872 // the fact that we store compound selectors the other way 873 // around, so there could also be state pseudo-classes. 874 let pseudo = next_invalidation 875 .dependency 876 .selector 877 .iter_raw_parse_order_from(next_invalidation.offset) 878 .flat_map(|c| { 879 if let Component::PseudoElement(ref pseudo) = *c { 880 return Some(pseudo); 881 } 882 883 // TODO: Would be nice to make this a diagnostic_assert! of 884 // sorts. 885 debug_assert!( 886 c.maybe_allowed_after_pseudo_element(), 887 "Someone seriously messed up selector parsing: \ 888 {:?} at offset {:?}: {:?}", 889 next_invalidation.dependency, next_invalidation.offset, c, 890 ); 891 892 None 893 }) 894 .next() 895 .unwrap(); 896 897 // FIXME(emilio): This is not ideal, and could not be 898 // accurate if we ever have stateful element-backed eager 899 // pseudos. 900 // 901 // Ideally, we'd just remove element-backed eager pseudos 902 // altogether, given they work fine without it. Only gotcha 903 // is that we wouldn't style them in parallel, which may or 904 // may not be an issue. 905 // 906 // Also, this could be more fine grained now (perhaps a 907 // RESTYLE_PSEUDOS hint?). 908 // 909 // Note that we'll also restyle the pseudo-element because 910 // it would match this invalidation. 911 if self.processor.invalidates_on_eager_pseudo_element() { 912 if pseudo.is_eager() { 913 invalidated_self = true; 914 } 915 // If we start or stop matching some marker rules, and 916 // don't have a marker, then we need to restyle the 917 // element to potentially create one. 918 // 919 // Same caveats as for other eager pseudos apply, this 920 // could be more fine-grained. 921 if pseudo.is_marker() && self.element.marker_pseudo_element().is_none() { 922 invalidated_self = true; 923 } 924 925 // FIXME: ::selection doesn't generate elements, so the 926 // regular invalidation doesn't work for it. We store 927 // the cached selection style holding off the originating 928 // element, so we need to restyle it in order to invalidate 929 // it. This is still not quite correct, since nothing 930 // triggers a repaint necessarily, but matches old Gecko 931 // behavior, and the ::selection implementation needs to 932 // change significantly anyway to implement 933 // https://github.com/w3c/csswg-drafts/issues/2474. 934 if pseudo.is_selection() { 935 invalidated_self = true; 936 } 937 } 938 } 939 940 debug!( 941 " > Invalidation matched, next: {:?}, ({:?})", 942 next_invalidation, next_combinator 943 ); 944 945 let next_invalidation_kind = next_invalidation.kind(); 946 947 // We can skip pushing under some circumstances, and we should 948 // because otherwise the invalidation list could grow 949 // exponentially. 950 // 951 // * First of all, both invalidations need to be of the same 952 // kind. This is because of how we propagate them going to 953 // the right of the tree for sibling invalidations and going 954 // down the tree for children invalidations. A sibling 955 // invalidation that ends up generating a children 956 // invalidation ends up (correctly) in five different lists, 957 // not in the same list five different times. 958 // 959 // * Then, the invalidation needs to be matched by a previous 960 // ancestor/sibling, in order to know that this invalidation 961 // has been generated already. 962 // 963 // * Finally, the new invalidation needs to be 964 // `effective_for_next()`, in order for us to know that it is 965 // still in the list, since we remove the dependencies that 966 // aren't from the lists for our children / siblings. 967 // 968 // To go through an example, let's imagine we are processing a 969 // dom subtree like: 970 // 971 // <div><address><div><div/></div></address></div> 972 // 973 // And an invalidation list with a single invalidation like: 974 // 975 // [div div div] 976 // 977 // When we process the invalidation list for the outer div, we 978 // match it, and generate a `div div` invalidation, so for the 979 // <address> child we have: 980 // 981 // [div div div, div div] 982 // 983 // With the first of them marked as `matched`. 984 // 985 // When we process the <address> child, we don't match any of 986 // them, so both invalidations go untouched to our children. 987 // 988 // When we process the second <div>, we match _both_ 989 // invalidations. 990 // 991 // However, when matching the first, we can tell it's been 992 // matched, and not push the corresponding `div div` 993 // invalidation, since we know it's necessarily already on the 994 // list. 995 // 996 // Thus, without skipping the push, we'll arrive to the 997 // innermost <div> with: 998 // 999 // [div div div, div div, div div, div] 1000 // 1001 // While skipping it, we won't arrive here with duplicating 1002 // dependencies: 1003 // 1004 // [div div div, div div, div] 1005 // 1006 let can_skip_pushing = next_invalidation_kind == invalidation_kind && 1007 invalidation.matched_by_any_previous && 1008 next_invalidation.effective_for_next(); 1009 1010 if can_skip_pushing { 1011 debug!( 1012 " > Can avoid push, since the invalidation had \ 1013 already been matched before" 1014 ); 1015 } else { 1016 match next_invalidation_kind { 1017 InvalidationKind::Descendant(DescendantInvalidationKind::Dom) => { 1018 descendant_invalidations 1019 .dom_descendants 1020 .push(next_invalidation); 1021 }, 1022 InvalidationKind::Descendant(DescendantInvalidationKind::Part) => { 1023 descendant_invalidations.parts.push(next_invalidation); 1024 }, 1025 InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) => { 1026 descendant_invalidations 1027 .slotted_descendants 1028 .push(next_invalidation); 1029 }, 1030 InvalidationKind::Sibling => { 1031 sibling_invalidations.push(next_invalidation); 1032 }, 1033 } 1034 } 1035 1036 SingleInvalidationResult { 1037 invalidated_self, 1038 matched: true, 1039 } 1040 } 1041 } 1042