diff options
Diffstat (limited to 'components')
-rw-r--r-- | components/script/dom/element.rs | 4 | ||||
-rw-r--r-- | components/script/dom/node.rs | 4 | ||||
-rw-r--r-- | components/selectors/matching.rs | 22 | ||||
-rw-r--r-- | components/selectors/parser.rs | 81 | ||||
-rw-r--r-- | components/style/invalidation/stylesheets.rs | 4 | ||||
-rw-r--r-- | components/style/restyle_hints.rs | 47 | ||||
-rw-r--r-- | components/style/selector_map.rs | 30 | ||||
-rw-r--r-- | components/style/stylist.rs | 40 |
8 files changed, 153 insertions, 79 deletions
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs index be708113def..f875986edd2 100644 --- a/components/script/dom/element.rs +++ b/components/script/dom/element.rs @@ -2061,7 +2061,7 @@ impl ElementMethods for Element { Err(()) => Err(Error::Syntax), Ok(selectors) => { let mut ctx = MatchingContext::new(MatchingMode::Normal, None); - Ok(matches_selector_list(&selectors.0, &Root::from_ref(self), &mut ctx)) + Ok(matches_selector_list(&selectors, &Root::from_ref(self), &mut ctx)) } } } @@ -2080,7 +2080,7 @@ impl ElementMethods for Element { for element in root.inclusive_ancestors() { if let Some(element) = Root::downcast::<Element>(element) { let mut ctx = MatchingContext::new(MatchingMode::Normal, None); - if matches_selector_list(&selectors.0, &element, &mut ctx) { + if matches_selector_list(&selectors, &element, &mut ctx) { return Ok(Some(element)); } } diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs index cc817587eda..8dde9cc7b01 100644 --- a/components/script/dom/node.rs +++ b/components/script/dom/node.rs @@ -345,7 +345,7 @@ impl<'a> Iterator for QuerySelectorIterator { type Item = Root<Node>; fn next(&mut self) -> Option<Root<Node>> { - let selectors = &self.selectors.0; + let selectors = &self.selectors; // TODO(cgaebel): Is it worth it to build a bloom filter here // (instead of passing `None`)? Probably. @@ -722,7 +722,7 @@ impl Node { Ok(selectors) => { let mut ctx = MatchingContext::new(MatchingMode::Normal, None); Ok(self.traverse_preorder().filter_map(Root::downcast).find(|element| { - matches_selector_list(&selectors.0, element, &mut ctx) + matches_selector_list(&selectors, element, &mut ctx) })) } } diff --git a/components/selectors/matching.rs b/components/selectors/matching.rs index 444d24a7d1c..094da6b3ca7 100644 --- a/components/selectors/matching.rs +++ b/components/selectors/matching.rs @@ -4,8 +4,8 @@ use attr::{ParsedAttrSelectorOperation, AttrSelectorOperation, NamespaceConstraint}; use bloom::BloomFilter; -use parser::{Combinator, ComplexSelector, Component, LocalName}; -use parser::{Selector, SelectorInner, SelectorIter}; +use parser::{AncestorHashes, Combinator, ComplexSelector, Component, LocalName}; +use parser::{SelectorInner, SelectorIter, SelectorList}; use std::borrow::Borrow; use tree::Element; @@ -152,27 +152,29 @@ impl<'a> MatchingContext<'a> { } } -pub fn matches_selector_list<E>(selector_list: &[Selector<E::Impl>], +pub fn matches_selector_list<E>(selector_list: &SelectorList<E::Impl>, element: &E, context: &mut MatchingContext) -> bool where E: Element { - selector_list.iter().any(|selector| { - matches_selector(&selector.inner, + selector_list.0.iter().any(|selector_and_hashes| { + matches_selector(&selector_and_hashes.selector.inner, + &selector_and_hashes.hashes, element, context, &mut |_, _| {}) }) } -fn may_match<E>(sel: &SelectorInner<E::Impl>, +#[inline(always)] +fn may_match<E>(hashes: &AncestorHashes, bf: &BloomFilter) -> bool where E: Element, { // Check against the list of precomputed hashes. - for hash in sel.ancestor_hashes.iter() { + for hash in hashes.0.iter() { // If we hit the 0 sentinel hash, that means the rest are zero as well. if *hash == 0 { break; @@ -330,8 +332,10 @@ enum SelectorMatchingResult { NotMatchedGlobally, } -/// Matches an inner selector. +/// Matches a selector, fast-rejecting against a bloom filter. +#[inline(always)] pub fn matches_selector<E, F>(selector: &SelectorInner<E::Impl>, + hashes: &AncestorHashes, element: &E, context: &mut MatchingContext, flags_setter: &mut F) @@ -341,7 +345,7 @@ pub fn matches_selector<E, F>(selector: &SelectorInner<E::Impl>, { // Use the bloom filter to fast-reject. if let Some(filter) = context.bloom_filter { - if !may_match::<E>(&selector, filter) { + if !may_match::<E>(hashes, filter) { return false; } } diff --git a/components/selectors/parser.rs b/components/selectors/parser.rs index 296a57c6709..e083ecdab75 100644 --- a/components/selectors/parser.rs +++ b/components/selectors/parser.rs @@ -130,7 +130,27 @@ pub trait Parser { } #[derive(PartialEq, Eq, Clone, Debug)] -pub struct SelectorList<Impl: SelectorImpl>(pub Vec<Selector<Impl>>); +pub struct SelectorAndHashes<Impl: SelectorImpl> { + pub selector: Selector<Impl>, + pub hashes: AncestorHashes, +} + +impl<Impl: SelectorImpl> SelectorAndHashes<Impl> { + pub fn new(selector: Selector<Impl>) -> Self { + let hashes = AncestorHashes::new(&selector); + Self::new_with_hashes(selector, hashes) + } + + pub fn new_with_hashes(selector: Selector<Impl>, hashes: AncestorHashes) -> Self { + SelectorAndHashes { + selector: selector, + hashes: hashes, + } + } +} + +#[derive(PartialEq, Eq, Clone, Debug)] +pub struct SelectorList<Impl: SelectorImpl>(pub Vec<SelectorAndHashes<Impl>>); impl<Impl: SelectorImpl> SelectorList<Impl> { /// Parse a comma-separated list of Selectors. @@ -139,14 +159,41 @@ impl<Impl: SelectorImpl> SelectorList<Impl> { /// Return the Selectors or Err if there is an invalid selector. pub fn parse<P>(parser: &P, input: &mut CssParser) -> Result<Self, ()> where P: Parser<Impl=Impl> { - input.parse_comma_separated(|input| parse_selector(parser, input)) + input.parse_comma_separated(|input| parse_selector(parser, input).map(SelectorAndHashes::new)) .map(SelectorList) } } -/// Copied from Gecko, where it was noted to be unmeasured. +/// Copied from Gecko, who copied it from WebKit. Note that increasing the +/// number of hashes here will adversely affect the cache hit when fast- +/// rejecting long lists of Rules with inline hashes. const NUM_ANCESTOR_HASHES: usize = 4; +/// Ancestor hashes for the bloom filter. We precompute these and store them +/// inline with selectors to optimize cache performance during matching. +/// This matters a lot. +#[derive(Eq, PartialEq, Clone, Debug)] +pub struct AncestorHashes(pub [u32; NUM_ANCESTOR_HASHES]); + +impl AncestorHashes { + pub fn new<Impl: SelectorImpl>(c: &Selector<Impl>) -> Self { + let mut hashes = [0; NUM_ANCESTOR_HASHES]; + // Compute ancestor hashes for the bloom filter. + let mut hash_iter = c.inner.complex.iter_ancestors() + .map(|x| x.ancestor_hash()) + .filter(|x| x.is_some()) + .map(|x| x.unwrap()); + for i in 0..NUM_ANCESTOR_HASHES { + hashes[i] = match hash_iter.next() { + Some(x) => x, + None => break, + } + } + + AncestorHashes(hashes) + } +} + /// The cores parts of a selector used for matching. This exists to make that /// information accessibly separately from the specificity and pseudo-element /// information that lives on |Selector| proper. We may want to refactor things @@ -156,32 +203,12 @@ const NUM_ANCESTOR_HASHES: usize = 4; pub struct SelectorInner<Impl: SelectorImpl> { /// The selector data. pub complex: ComplexSelector<Impl>, - /// Ancestor hashes for the bloom filter. We precompute these and store - /// them inline to optimize cache performance during selector matching. - /// This matters a lot. - pub ancestor_hashes: [u32; NUM_ANCESTOR_HASHES], } impl<Impl: SelectorImpl> SelectorInner<Impl> { pub fn new(c: ComplexSelector<Impl>) -> Self { - let mut hashes = [0; NUM_ANCESTOR_HASHES]; - { - // Compute ancestor hashes for the bloom filter. - let mut hash_iter = c.iter_ancestors() - .map(|x| x.ancestor_hash()) - .filter(|x| x.is_some()) - .map(|x| x.unwrap()); - for i in 0..NUM_ANCESTOR_HASHES { - hashes[i] = match hash_iter.next() { - Some(x) => x, - None => break, - } - } - } - SelectorInner { complex: c, - ancestor_hashes: hashes, } } @@ -590,7 +617,7 @@ pub enum Component<Impl: SelectorImpl> { impl<Impl: SelectorImpl> Component<Impl> { /// Compute the ancestor hash to check against the bloom filter. - fn ancestor_hash(&self) -> Option<u32> { + pub fn ancestor_hash(&self) -> Option<u32> { match *self { Component::LocalName(LocalName { ref name, ref lower_name }) => { // Only insert the local-name into the filter if it's all lowercase. @@ -665,10 +692,10 @@ impl<Impl: SelectorImpl> ToCss for SelectorList<Impl> { let mut iter = self.0.iter(); let first = iter.next() .expect("Empty SelectorList, should contain at least one selector"); - first.to_css(dest)?; - for selector in iter { + first.selector.to_css(dest)?; + for selector_and_hashes in iter { dest.write_str(", ")?; - selector.to_css(dest)?; + selector_and_hashes.selector.to_css(dest)?; } Ok(()) } diff --git a/components/style/invalidation/stylesheets.rs b/components/style/invalidation/stylesheets.rs index 93f0d8783ad..adfb4b97a59 100644 --- a/components/style/invalidation/stylesheets.rs +++ b/components/style/invalidation/stylesheets.rs @@ -262,8 +262,8 @@ impl StylesheetInvalidationSet { match *rule { Style(ref lock) => { let style_rule = lock.read_with(guard); - for selector in &style_rule.selectors.0 { - self.collect_scopes(selector); + for selector_and_hashes in &style_rule.selectors.0 { + self.collect_scopes(&selector_and_hashes.selector); if self.fully_invalid { return; } diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs index acca66d6fdb..615445bef2a 100644 --- a/components/style/restyle_hints.rs +++ b/components/style/restyle_hints.rs @@ -22,7 +22,8 @@ use selectors::Element; use selectors::attr::{AttrSelectorOperation, NamespaceConstraint}; use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode}; use selectors::matching::{RelevantLinkStatus, VisitedHandlingMode, matches_selector}; -use selectors::parser::{Combinator, Component, Selector, SelectorInner, SelectorMethods}; +use selectors::parser::{AncestorHashes, Combinator, Component}; +use selectors::parser::{Selector, SelectorAndHashes, SelectorInner, SelectorMethods}; use selectors::visitor::SelectorVisitor; use smallvec::SmallVec; use std::cell::Cell; @@ -867,7 +868,9 @@ impl Sensitivities { #[cfg_attr(feature = "servo", derive(HeapSizeOf))] pub struct Dependency { #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")] - selector: SelectorInner<SelectorImpl>, + selector: Selector<SelectorImpl>, + #[cfg_attr(feature = "servo", ignore_heap_size_of = "No heap data")] + hashes: AncestorHashes, /// The hint associated with this dependency. pub hint: RestyleHint, /// The sensitivities associated with this dependency. @@ -875,9 +878,13 @@ pub struct Dependency { } impl SelectorMapEntry for Dependency { - fn selector(&self) -> &SelectorInner<SelectorImpl> { + fn selector(&self) -> &Selector<SelectorImpl> { &self.selector } + + fn hashes(&self) -> &AncestorHashes { + &self.hashes + } } /// The following visitor visits all the simple selectors for a given complex @@ -940,9 +947,9 @@ pub enum HintComputationContext<'a, E: 'a> impl DependencySet { /// Adds a selector to this `DependencySet`. - pub fn note_selector(&mut self, selector: &Selector<SelectorImpl>) { + pub fn note_selector(&mut self, selector_and_hashes: &SelectorAndHashes<SelectorImpl>) { let mut combinator = None; - let mut iter = selector.inner.complex.iter(); + let mut iter = selector_and_hashes.selector.inner.complex.iter(); let mut index = 0; let mut child_combinators_seen = 0; let mut saw_descendant_combinator = false; @@ -992,17 +999,25 @@ impl DependencySet { None => RestyleHint::for_self(), }; - let dep_selector = if sequence_start == 0 { + let (dep_selector, hashes) = if sequence_start == 0 { // Reuse the bloom hashes if this is the base selector. - selector.inner.clone() + (selector_and_hashes.selector.clone(), + selector_and_hashes.hashes.clone()) + } else { - SelectorInner::new(selector.inner.complex.slice_from(sequence_start)) + let inner = SelectorInner::new(selector_and_hashes.selector + .inner + .complex.slice_from(sequence_start)); + let selector = Selector { inner: inner }; + let hashes = AncestorHashes::new(&selector); + (selector, hashes) }; self.dependencies.insert(Dependency { sensitivities: visitor.sensitivities, hint: hint, selector: dep_selector, + hashes: hashes, }); } @@ -1130,14 +1145,18 @@ impl DependencySet { MatchingContext::new_for_visited(MatchingMode::Normal, None, VisitedHandlingMode::AllLinksUnvisited); let matched_then = - matches_selector(&dep.selector, &snapshot_el, + matches_selector(&dep.selector.inner, + &dep.hashes, + &snapshot_el, &mut then_context, &mut |_, _| {}); let mut now_context = MatchingContext::new_for_visited(MatchingMode::Normal, bloom_filter, VisitedHandlingMode::AllLinksUnvisited); let matches_now = - matches_selector(&dep.selector, el, + matches_selector(&dep.selector.inner, + &dep.hashes, + el, &mut now_context, &mut |_, _| {}); @@ -1162,12 +1181,16 @@ impl DependencySet { dep.sensitivities.states.intersects(IN_VISITED_OR_UNVISITED_STATE) { then_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited; let matched_then = - matches_selector(&dep.selector, &snapshot_el, + matches_selector(&dep.selector.inner, + &dep.hashes, + &snapshot_el, &mut then_context, &mut |_, _| {}); now_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited; let matches_now = - matches_selector(&dep.selector, el, + matches_selector(&dep.selector.inner, + &dep.hashes, + el, &mut now_context, &mut |_, _| {}); if matched_then != matches_now { diff --git a/components/style/selector_map.rs b/components/style/selector_map.rs index 846d7972811..4120f000704 100644 --- a/components/style/selector_map.rs +++ b/components/style/selector_map.rs @@ -12,7 +12,7 @@ use pdqsort::sort_by; use rule_tree::CascadeLevel; use selector_parser::SelectorImpl; use selectors::matching::{matches_selector, MatchingContext, ElementSelectorFlags}; -use selectors::parser::{Component, Combinator, SelectorInner}; +use selectors::parser::{AncestorHashes, Component, Combinator, Selector, SelectorAndHashes}; use selectors::parser::LocalName as LocalNameSelector; use smallvec::VecLike; use std::borrow::Borrow; @@ -22,13 +22,20 @@ use stylist::{ApplicableDeclarationBlock, Rule}; /// A trait to abstract over a given selector map entry. pub trait SelectorMapEntry : Sized + Clone { - /// Get the selector we should use to index in the selector map. - fn selector(&self) -> &SelectorInner<SelectorImpl>; + /// Gets the selector we should use to index in the selector map. + fn selector(&self) -> &Selector<SelectorImpl>; + + /// Gets the ancestor hashes associated with the selector. + fn hashes(&self) -> &AncestorHashes; } -impl SelectorMapEntry for SelectorInner<SelectorImpl> { - fn selector(&self) -> &SelectorInner<SelectorImpl> { - self +impl SelectorMapEntry for SelectorAndHashes<SelectorImpl> { + fn selector(&self) -> &Selector<SelectorImpl> { + &self.selector + } + + fn hashes(&self) -> &AncestorHashes { + &self.hashes } } @@ -225,6 +232,7 @@ impl SelectorMap<Rule> { { for rule in rules { if matches_selector(&rule.selector.inner, + &rule.hashes, element, context, flags_setter) { @@ -390,12 +398,12 @@ impl<T: SelectorMapEntry> SelectorMap<T> { /// /// Effectively, pseudo-elements are ignored, given only state pseudo-classes /// may appear before them. -fn find_from_right<F, R>(selector: &SelectorInner<SelectorImpl>, +fn find_from_right<F, R>(selector: &Selector<SelectorImpl>, mut f: F) -> Option<R> where F: FnMut(&Component<SelectorImpl>) -> Option<R>, { - let mut iter = selector.complex.iter(); + let mut iter = selector.inner.complex.iter(); for ss in &mut iter { if let Some(r) = f(ss) { return Some(r) @@ -414,7 +422,7 @@ fn find_from_right<F, R>(selector: &SelectorInner<SelectorImpl>, } /// Retrieve the first ID name in the selector, or None otherwise. -pub fn get_id_name(selector: &SelectorInner<SelectorImpl>) +pub fn get_id_name(selector: &Selector<SelectorImpl>) -> Option<Atom> { find_from_right(selector, |ss| { // TODO(pradeep): Implement case-sensitivity based on the @@ -427,7 +435,7 @@ pub fn get_id_name(selector: &SelectorInner<SelectorImpl>) } /// Retrieve the FIRST class name in the selector, or None otherwise. -pub fn get_class_name(selector: &SelectorInner<SelectorImpl>) +pub fn get_class_name(selector: &Selector<SelectorImpl>) -> Option<Atom> { find_from_right(selector, |ss| { // TODO(pradeep): Implement case-sensitivity based on the @@ -440,7 +448,7 @@ pub fn get_class_name(selector: &SelectorInner<SelectorImpl>) } /// Retrieve the name if it is a type selector, or None otherwise. -pub fn get_local_name(selector: &SelectorInner<SelectorImpl>) +pub fn get_local_name(selector: &Selector<SelectorImpl>) -> Option<LocalNameSelector<SelectorImpl>> { find_from_right(selector, |ss| { if let Component::LocalName(ref n) = *ss { diff --git a/components/style/stylist.rs b/components/style/stylist.rs index 5df0bf2717b..010d37e1e53 100644 --- a/components/style/stylist.rs +++ b/components/style/stylist.rs @@ -28,7 +28,8 @@ use selectors::attr::NamespaceConstraint; use selectors::bloom::BloomFilter; use selectors::matching::{ElementSelectorFlags, matches_selector, MatchingContext, MatchingMode}; use selectors::matching::AFFECTED_BY_PRESENTATIONAL_HINTS; -use selectors::parser::{Combinator, Component, Selector, SelectorInner, SelectorIter, SelectorMethods}; +use selectors::parser::{AncestorHashes, Combinator, Component, Selector, SelectorAndHashes}; +use selectors::parser::{SelectorIter, SelectorMethods}; use selectors::visitor::SelectorVisitor; use shared_lock::{Locked, SharedRwLockReadGuard, StylesheetGuards}; use sink::Push; @@ -159,7 +160,7 @@ pub struct Stylist { /// on state that is not otherwise visible to the cache, like attributes or /// tree-structural state like child index and pseudos). #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")] - selectors_for_cache_revalidation: SelectorMap<SelectorInner<SelectorImpl>>, + selectors_for_cache_revalidation: SelectorMap<SelectorAndHashes<SelectorImpl>>, /// The total number of selectors. num_selectors: usize, @@ -454,10 +455,10 @@ impl Stylist { CssRule::Style(ref locked) => { let style_rule = locked.read_with(&guard); self.num_declarations += style_rule.block.read_with(&guard).len(); - for selector in &style_rule.selectors.0 { + for selector_and_hashes in &style_rule.selectors.0 { self.num_selectors += 1; - let map = if let Some(pseudo) = selector.pseudo_element() { + let map = if let Some(pseudo) = selector_and_hashes.selector.pseudo_element() { self.pseudos_map .entry(pseudo.canonical()) .or_insert_with(PerPseudoElementSelectorMap::new) @@ -466,20 +467,21 @@ impl Stylist { self.element_map.borrow_for_origin(&stylesheet.origin) }; - map.insert(Rule::new(selector.clone(), + map.insert(Rule::new(selector_and_hashes.selector.clone(), + selector_and_hashes.hashes.clone(), locked.clone(), self.rules_source_order)); - self.dependencies.note_selector(selector); - if needs_revalidation(selector) { - self.selectors_for_cache_revalidation.insert(selector.inner.clone()); + self.dependencies.note_selector(selector_and_hashes); + if needs_revalidation(&selector_and_hashes.selector) { + self.selectors_for_cache_revalidation.insert(selector_and_hashes.clone()); } - selector.visit(&mut AttributeAndStateDependencyVisitor { + selector_and_hashes.selector.visit(&mut AttributeAndStateDependencyVisitor { attribute_dependencies: &mut self.attribute_dependencies, style_attribute_dependency: &mut self.style_attribute_dependency, state_dependencies: &mut self.state_dependencies, }); - selector.visit(&mut MappedIdVisitor { + selector_and_hashes.selector.visit(&mut MappedIdVisitor { mapped_ids: &mut self.mapped_ids, }); } @@ -1130,8 +1132,9 @@ impl Stylist { // the lookups, which means that the bitvecs are comparable. We verify // this in the caller by asserting that the bitvecs are same-length. let mut results = BitVec::new(); - self.selectors_for_cache_revalidation.lookup(*element, &mut |selector| { - results.push(matches_selector(selector, + self.selectors_for_cache_revalidation.lookup(*element, &mut |selector_and_hashes| { + results.push(matches_selector(&selector_and_hashes.selector.inner, + &selector_and_hashes.hashes, element, &mut matching_context, flags_setter)); @@ -1410,6 +1413,9 @@ pub struct Rule { /// can ruin performance when there are a lot of rules. #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")] pub selector: Selector<SelectorImpl>, + /// The ancestor hashes associated with the selector. + #[cfg_attr(feature = "servo", ignore_heap_size_of = "No heap data")] + pub hashes: AncestorHashes, /// The actual style rule. #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")] pub style_rule: Arc<Locked<StyleRule>>, @@ -1418,8 +1424,12 @@ pub struct Rule { } impl SelectorMapEntry for Rule { - fn selector(&self) -> &SelectorInner<SelectorImpl> { - &self.selector.inner + fn selector(&self) -> &Selector<SelectorImpl> { + &self.selector + } + + fn hashes(&self) -> &AncestorHashes { + &self.hashes } } @@ -1444,12 +1454,14 @@ impl Rule { /// Creates a new Rule. pub fn new(selector: Selector<SelectorImpl>, + hashes: AncestorHashes, style_rule: Arc<Locked<StyleRule>>, source_order: usize) -> Self { Rule { selector: selector, + hashes: hashes, style_rule: style_rule, source_order: source_order, } |