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::element_state::{DocumentState, ElementState}; 9 use crate::selector_map::{MaybeCaseInsensitiveHashMap, PrecomputedHashMap, SelectorMap, SelectorMapEntry}; 10 use crate::selector_parser::SelectorImpl; 11 use crate::{Atom, LocalName, Namespace}; 12 use fallible::FallibleVec; 13 use hashglobe::FailedAllocationError; 14 use selectors::attr::NamespaceConstraint; 15 use selectors::parser::{Combinator, Component}; 16 use selectors::parser::{Selector, SelectorIter}; 17 use selectors::visitor::SelectorVisitor; 18 use smallvec::SmallVec; 19 20 /// Mapping between (partial) CompoundSelectors (and the combinator to their 21 /// right) and the states and attributes they depend on. 22 /// 23 /// In general, for all selectors in all applicable stylesheets of the form: 24 /// 25 /// |a _ b _ c _ d _ e| 26 /// 27 /// Where: 28 /// * |b| and |d| are simple selectors that depend on state (like :hover) or 29 /// attributes (like [attr...], .foo, or #foo). 30 /// * |a|, |c|, and |e| are arbitrary simple selectors that do not depend on 31 /// state or attributes. 32 /// 33 /// We generate a Dependency for both |a _ b:X _| and |a _ b:X _ c _ d:Y _|, 34 /// even though those selectors may not appear on their own in any stylesheet. 35 /// This allows us to quickly scan through the dependency sites of all style 36 /// rules and determine the maximum effect that a given state or attributef 37 /// change may have on the style of elements in the document. 38 #[derive(Clone, Debug, MallocSizeOf)] 39 pub struct Dependency { 40 /// The dependency selector. 41 #[cfg_attr( 42 feature = "gecko", 43 ignore_malloc_size_of = "CssRules have primary refs, we measure there" 44 )] 45 #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")] 46 pub selector: Selector<SelectorImpl>, 47 48 /// The offset into the selector that we should match on. 49 pub selector_offset: usize, 50 51 /// The parent dependency for an ancestor selector. For example, consider 52 /// the following: 53 /// 54 /// .foo .bar:where(.baz span) .qux 55 /// ^ ^ ^ 56 /// A B C 57 /// 58 /// We'd generate: 59 /// 60 /// * One dependency for .qux (offset: 0, parent: None) 61 /// * One dependency for .baz pointing to B with parent being a 62 /// dependency pointing to C. 63 /// * One dependency from .bar pointing to C (parent: None) 64 /// * One dependency from .foo pointing to A (parent: None) 65 /// 66 pub parent: Option<Box<Dependency>>, 67 } 68 69 /// The kind of elements down the tree this dependency may affect. 70 #[derive(Debug, Eq, PartialEq)] 71 pub enum DependencyInvalidationKind { 72 /// This dependency may affect the element that changed itself. 73 Element, 74 /// This dependency affects the style of the element itself, and also the 75 /// style of its descendants. 76 /// 77 /// TODO(emilio): Each time this feels more of a hack for eager pseudos... 78 ElementAndDescendants, 79 /// This dependency may affect descendants down the tree. 80 Descendants, 81 /// This dependency may affect siblings to the right of the element that 82 /// changed. 83 Siblings, 84 /// This dependency may affect slotted elements of the element that changed. 85 SlottedElements, 86 /// This dependency may affect parts of the element that changed. 87 Parts, 88 } 89 90 impl Dependency { 91 /// Creates a dummy dependency to invalidate the whole selector. 92 /// 93 /// This is necessary because document state invalidation wants to 94 /// invalidate all elements in the document. 95 /// 96 /// The offset is such as that Invalidation::new(self) returns a zero 97 /// offset. That is, it points to a virtual "combinator" outside of the 98 /// selector, so calling combinator() on such a dependency will panic. for_full_selector_invalidation(selector: Selector<SelectorImpl>) -> Self99 pub fn for_full_selector_invalidation(selector: Selector<SelectorImpl>) -> Self { 100 Self { 101 selector_offset: selector.len() + 1, 102 selector, 103 parent: None, 104 } 105 } 106 107 /// Returns the combinator to the right of the partial selector this 108 /// dependency represents. 109 /// 110 /// TODO(emilio): Consider storing inline if it helps cache locality? combinator(&self) -> Option<Combinator>111 pub fn combinator(&self) -> Option<Combinator> { 112 if self.selector_offset == 0 { 113 return None; 114 } 115 116 Some( 117 self.selector 118 .combinator_at_match_order(self.selector_offset - 1), 119 ) 120 } 121 122 /// The kind of invalidation that this would generate. invalidation_kind(&self) -> DependencyInvalidationKind123 pub fn invalidation_kind(&self) -> DependencyInvalidationKind { 124 match self.combinator() { 125 None => DependencyInvalidationKind::Element, 126 Some(Combinator::Child) | Some(Combinator::Descendant) => { 127 DependencyInvalidationKind::Descendants 128 }, 129 Some(Combinator::LaterSibling) | Some(Combinator::NextSibling) => { 130 DependencyInvalidationKind::Siblings 131 }, 132 // TODO(emilio): We could look at the selector itself to see if it's 133 // an eager pseudo, and return only Descendants here if not. 134 Some(Combinator::PseudoElement) => DependencyInvalidationKind::ElementAndDescendants, 135 Some(Combinator::SlotAssignment) => DependencyInvalidationKind::SlottedElements, 136 Some(Combinator::Part) => DependencyInvalidationKind::Parts, 137 } 138 } 139 } 140 141 impl SelectorMapEntry for Dependency { selector(&self) -> SelectorIter<SelectorImpl>142 fn selector(&self) -> SelectorIter<SelectorImpl> { 143 self.selector.iter_from(self.selector_offset) 144 } 145 } 146 147 /// The same, but for state selectors, which can track more exactly what state 148 /// do they track. 149 #[derive(Clone, Debug, MallocSizeOf)] 150 pub struct StateDependency { 151 /// The other dependency fields. 152 pub dep: Dependency, 153 /// The state this dependency is affected by. 154 pub state: ElementState, 155 } 156 157 impl SelectorMapEntry for StateDependency { selector(&self) -> SelectorIter<SelectorImpl>158 fn selector(&self) -> SelectorIter<SelectorImpl> { 159 self.dep.selector() 160 } 161 } 162 163 /// The same, but for document state selectors. 164 #[derive(Clone, Debug, MallocSizeOf)] 165 pub struct DocumentStateDependency { 166 /// We track `Dependency` even though we don't need to track an offset, 167 /// since when it changes it changes for the whole document anyway. 168 #[cfg_attr( 169 feature = "gecko", 170 ignore_malloc_size_of = "CssRules have primary refs, we measure there" 171 )] 172 #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")] 173 pub dependency: Dependency, 174 /// The state this dependency is affected by. 175 pub state: DocumentState, 176 } 177 178 /// A map where we store invalidations. 179 /// 180 /// This is slightly different to a SelectorMap, in the sense of that the same 181 /// selector may appear multiple times. 182 /// 183 /// In particular, we want to lookup as few things as possible to get the fewer 184 /// selectors the better, so this looks up by id, class, or looks at the list of 185 /// state/other attribute affecting selectors. 186 #[derive(Debug, MallocSizeOf)] 187 pub struct InvalidationMap { 188 /// A map from a given class name to all the selectors with that class 189 /// selector. 190 pub class_to_selector: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>, 191 /// A map from a given id to all the selectors with that ID in the 192 /// stylesheets currently applying to the document. 193 pub id_to_selector: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>, 194 /// A map of all the state dependencies. 195 pub state_affecting_selectors: SelectorMap<StateDependency>, 196 /// A list of document state dependencies in the rules we represent. 197 pub document_state_selectors: Vec<DocumentStateDependency>, 198 /// A map of other attribute affecting selectors. 199 pub other_attribute_affecting_selectors: PrecomputedHashMap<Atom, SmallVec<[Dependency; 1]>>, 200 } 201 202 impl InvalidationMap { 203 /// Creates an empty `InvalidationMap`. new() -> Self204 pub fn new() -> Self { 205 Self { 206 class_to_selector: MaybeCaseInsensitiveHashMap::new(), 207 id_to_selector: MaybeCaseInsensitiveHashMap::new(), 208 state_affecting_selectors: SelectorMap::new(), 209 document_state_selectors: Vec::new(), 210 other_attribute_affecting_selectors: PrecomputedHashMap::default(), 211 } 212 } 213 214 /// Returns the number of dependencies stored in the invalidation map. len(&self) -> usize215 pub fn len(&self) -> usize { 216 self.state_affecting_selectors.len() + 217 self.document_state_selectors.len() + 218 self.other_attribute_affecting_selectors 219 .iter() 220 .fold(0, |accum, (_, ref v)| accum + v.len()) + 221 self.id_to_selector 222 .iter() 223 .fold(0, |accum, (_, ref v)| accum + v.len()) + 224 self.class_to_selector 225 .iter() 226 .fold(0, |accum, (_, ref v)| accum + v.len()) 227 } 228 229 /// Clears this map, leaving it empty. clear(&mut self)230 pub fn clear(&mut self) { 231 self.class_to_selector.clear(); 232 self.id_to_selector.clear(); 233 self.state_affecting_selectors.clear(); 234 self.document_state_selectors.clear(); 235 self.other_attribute_affecting_selectors.clear(); 236 } 237 238 /// Adds a selector to this `InvalidationMap`. Returns Err(..) to 239 /// signify OOM. note_selector( &mut self, selector: &Selector<SelectorImpl>, quirks_mode: QuirksMode, ) -> Result<(), FailedAllocationError>240 pub fn note_selector( 241 &mut self, 242 selector: &Selector<SelectorImpl>, 243 quirks_mode: QuirksMode, 244 ) -> Result<(), FailedAllocationError> { 245 debug!("InvalidationMap::note_selector({:?})", selector); 246 247 let mut document_state = DocumentState::empty(); 248 249 { 250 let mut parent_stack = SmallVec::new(); 251 let mut alloc_error = None; 252 let mut collector = SelectorDependencyCollector { 253 map: self, 254 document_state: &mut document_state, 255 selector, 256 parent_selectors: &mut parent_stack, 257 quirks_mode, 258 compound_state: PerCompoundState::new(0), 259 alloc_error: &mut alloc_error, 260 }; 261 262 let visit_result = collector.visit_whole_selector(); 263 debug_assert_eq!(!visit_result, alloc_error.is_some()); 264 if let Some(alloc_error) = alloc_error { 265 return Err(alloc_error); 266 } 267 } 268 269 if !document_state.is_empty() { 270 let dep = DocumentStateDependency { 271 state: document_state, 272 dependency: Dependency::for_full_selector_invalidation(selector.clone()), 273 }; 274 self.document_state_selectors.try_push(dep)?; 275 } 276 277 Ok(()) 278 } 279 } 280 281 struct PerCompoundState { 282 /// The offset at which our compound starts. 283 offset: usize, 284 285 /// The state this compound selector is affected by. 286 element_state: ElementState, 287 } 288 289 impl PerCompoundState { new(offset: usize) -> Self290 fn new(offset: usize) -> Self { 291 Self { 292 offset, 293 element_state: ElementState::empty(), 294 } 295 } 296 } 297 298 /// A struct that collects invalidations for a given compound selector. 299 struct SelectorDependencyCollector<'a> { 300 map: &'a mut InvalidationMap, 301 302 /// The document this _complex_ selector is affected by. 303 /// 304 /// We don't need to track state per compound selector, since it's global 305 /// state and it changes for everything. 306 document_state: &'a mut DocumentState, 307 308 /// The current selector and offset we're iterating. 309 selector: &'a Selector<SelectorImpl>, 310 311 /// The stack of parent selectors that we have, and at which offset of the 312 /// sequence. 313 /// 314 /// This starts empty. It grows when we find nested :is and :where selector 315 /// lists. 316 parent_selectors: &'a mut SmallVec<[(Selector<SelectorImpl>, usize); 5]>, 317 318 /// The quirks mode of the document where we're inserting dependencies. 319 quirks_mode: QuirksMode, 320 321 /// State relevant to a given compound selector. 322 compound_state: PerCompoundState, 323 324 /// The allocation error, if we OOM. 325 alloc_error: &'a mut Option<FailedAllocationError>, 326 } 327 328 impl<'a> SelectorDependencyCollector<'a> { visit_whole_selector(&mut self) -> bool329 fn visit_whole_selector(&mut self) -> bool { 330 let iter = self.selector.iter(); 331 self.visit_whole_selector_from(iter, 0) 332 } 333 visit_whole_selector_from(&mut self, mut iter: SelectorIter<SelectorImpl>, mut index: usize) -> bool334 fn visit_whole_selector_from(&mut self, mut iter: SelectorIter<SelectorImpl>, mut index: usize) -> bool { 335 loop { 336 // Reset the compound state. 337 self.compound_state = PerCompoundState::new(index); 338 339 // Visit all the simple selectors in this sequence. 340 for ss in &mut iter { 341 if !ss.visit(self) { 342 return false; 343 } 344 index += 1; // Account for the simple selector. 345 } 346 347 if !self.compound_state.element_state.is_empty() { 348 let dependency = self.dependency(); 349 let result = self.map.state_affecting_selectors.insert( 350 StateDependency { 351 dep: dependency, 352 state: self.compound_state.element_state, 353 }, 354 self.quirks_mode, 355 ); 356 if let Err(alloc_error) = result { 357 *self.alloc_error = Some(alloc_error); 358 return false; 359 } 360 } 361 362 let combinator = iter.next_sequence(); 363 if combinator.is_none() { 364 return true; 365 } 366 index += 1; // account for the combinator 367 } 368 } 369 add_attr_dependency(&mut self, name: LocalName) -> bool370 fn add_attr_dependency(&mut self, name: LocalName) -> bool { 371 let dependency = self.dependency(); 372 373 let map = &mut self.map.other_attribute_affecting_selectors; 374 let entry = match map.try_entry(name) { 375 Ok(entry) => entry, 376 Err(err) => { 377 *self.alloc_error = Some(err); 378 return false; 379 }, 380 }; 381 382 match entry.or_insert_with(SmallVec::new).try_push(dependency) { 383 Ok(..) => true, 384 Err(err) => { 385 *self.alloc_error = Some(err); 386 return false; 387 } 388 } 389 } 390 dependency(&self) -> Dependency391 fn dependency(&self) -> Dependency { 392 let mut parent = None; 393 394 // TODO(emilio): Maybe we should refcount the parent dependencies, or 395 // cache them or something. 396 for &(ref selector, ref selector_offset) in self.parent_selectors.iter() { 397 debug_assert_ne!( 398 self.compound_state.offset, 399 0, 400 "Shouldn't bother creating nested dependencies for the rightmost compound", 401 ); 402 let new_parent = Dependency { 403 selector: selector.clone(), 404 selector_offset: *selector_offset, 405 parent, 406 }; 407 parent = Some(Box::new(new_parent)); 408 } 409 410 Dependency { 411 selector: self.selector.clone(), 412 selector_offset: self.compound_state.offset, 413 parent, 414 } 415 } 416 } 417 418 impl<'a> SelectorVisitor for SelectorDependencyCollector<'a> { 419 type Impl = SelectorImpl; 420 visit_selector_list(&mut self, list: &[Selector<SelectorImpl>]) -> bool421 fn visit_selector_list(&mut self, list: &[Selector<SelectorImpl>]) -> bool { 422 for selector in list { 423 // Here we cheat a bit: We can visit the rightmost compound with 424 // the "outer" visitor, and it'd be fine. This reduces the amount of 425 // state and attribute invalidations, and we need to check the outer 426 // selector to the left anyway to avoid over-invalidation, so it 427 // avoids matching it twice uselessly. 428 let mut iter = selector.iter(); 429 let mut index = 0; 430 431 for ss in &mut iter { 432 if !ss.visit(self) { 433 return false; 434 } 435 index += 1; 436 } 437 438 let combinator = iter.next_sequence(); 439 if combinator.is_none() { 440 continue; 441 } 442 443 index += 1; // account for the combinator. 444 445 self.parent_selectors.push((self.selector.clone(), self.compound_state.offset)); 446 let mut nested = SelectorDependencyCollector { 447 map: &mut *self.map, 448 document_state: &mut *self.document_state, 449 selector, 450 parent_selectors: &mut *self.parent_selectors, 451 quirks_mode: self.quirks_mode, 452 compound_state: PerCompoundState::new(index), 453 alloc_error: &mut *self.alloc_error, 454 }; 455 if !nested.visit_whole_selector_from(iter, index) { 456 return false; 457 } 458 self.parent_selectors.pop(); 459 } 460 true 461 } 462 visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool463 fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool { 464 #[cfg(feature = "gecko")] 465 use crate::selector_parser::NonTSPseudoClass; 466 467 match *s { 468 Component::ID(ref atom) | Component::Class(ref atom) => { 469 let dependency = self.dependency(); 470 let map = match *s { 471 Component::ID(..) => &mut self.map.id_to_selector, 472 Component::Class(..) => &mut self.map.class_to_selector, 473 _ => unreachable!(), 474 }; 475 let entry = match map.try_entry(atom.clone(), self.quirks_mode) { 476 Ok(entry) => entry, 477 Err(err) => { 478 *self.alloc_error = Some(err); 479 return false; 480 }, 481 }; 482 match entry.or_insert_with(SmallVec::new).try_push(dependency) { 483 Ok(..) => true, 484 Err(err) => { 485 *self.alloc_error = Some(err); 486 return false; 487 } 488 } 489 }, 490 Component::NonTSPseudoClass(ref pc) => { 491 self.compound_state.element_state |= match *pc { 492 #[cfg(feature = "gecko")] 493 NonTSPseudoClass::Dir(ref dir) => dir.element_state(), 494 _ => pc.state_flag(), 495 }; 496 *self.document_state |= pc.document_state_flag(); 497 498 let attr_name = match *pc { 499 #[cfg(feature = "gecko")] 500 NonTSPseudoClass::MozTableBorderNonzero => local_name!("border"), 501 #[cfg(feature = "gecko")] 502 NonTSPseudoClass::MozBrowserFrame => local_name!("mozbrowser"), 503 NonTSPseudoClass::Lang(..) => local_name!("lang"), 504 _ => return true, 505 }; 506 507 self.add_attr_dependency(attr_name) 508 }, 509 _ => true, 510 } 511 } 512 visit_attribute_selector( &mut self, _: &NamespaceConstraint<&Namespace>, local_name: &LocalName, local_name_lower: &LocalName, ) -> bool513 fn visit_attribute_selector( 514 &mut self, 515 _: &NamespaceConstraint<&Namespace>, 516 local_name: &LocalName, 517 local_name_lower: &LocalName, 518 ) -> bool { 519 if !self.add_attr_dependency(local_name.clone()) { 520 return false; 521 } 522 523 if local_name != local_name_lower && !self.add_attr_dependency(local_name_lower.clone()) { 524 return false; 525 } 526 527 true 528 } 529 } 530