servo: Merge #15890 - selectors: Check the bloom filter at most once per complex selector (from emilio:bloom); r=heycam
authorEmilio Cobos Álvarez <emilio@crisal.io>
Mon, 20 Mar 2017 06:26:38 -0700
changeset 348425 aaa6a3933cc3515307c37c8d0dcf6846addf2c81
parent 348424 b08acf51cbd1141d26804f55371bcd900169e5ac
child 348426 0165092dfacd36994a0744c30d94356cd531ce02
push id39159
push userservo-vcs-sync@mozilla.com
push dateMon, 20 Mar 2017 15:24:23 +0000
treeherderautoland@aaa6a3933cc3 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersheycam
bugs15890
milestone55.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
servo: Merge #15890 - selectors: Check the bloom filter at most once per complex selector (from emilio:bloom); r=heycam Fixes https://github.com/servo/rust-selectors/issues/107 Source-Repo: https://github.com/servo/servo Source-Revision: 4fa40c77036c0635abb6a567146a101d11521cb0
servo/components/selectors/matching.rs
--- a/servo/components/selectors/matching.rs
+++ b/servo/components/selectors/matching.rs
@@ -107,31 +107,81 @@ pub fn matches<E>(selector_list: &[Selec
 {
     selector_list.iter().any(|selector| {
         selector.pseudo_element.is_none() &&
         matches_complex_selector(&*selector.complex_selector, element, parent_bf,
                                  &mut StyleRelations::empty(), &mut ElementSelectorFlags::empty())
     })
 }
 
+fn may_match<E>(mut selector: &ComplexSelector<E::Impl>,
+                bf: &BloomFilter)
+                -> bool
+    where E: Element,
+{
+    // See if the bloom filter can exclude any of the descendant selectors, and
+    // reject if we can.
+    loop {
+         match selector.next {
+             None => break,
+             Some((ref cs, Combinator::Descendant)) => selector = &**cs,
+             Some((ref cs, _)) => {
+                 selector = &**cs;
+                 continue;
+             }
+         };
+
+        for ss in selector.compound_selector.iter() {
+            match *ss {
+                SimpleSelector::LocalName(LocalName { ref name, ref lower_name })  => {
+                    if !bf.might_contain(name) &&
+                       !bf.might_contain(lower_name) {
+                       return false
+                    }
+                },
+                SimpleSelector::Namespace(ref namespace) => {
+                    if !bf.might_contain(&namespace.url) {
+                        return false
+                    }
+                },
+                SimpleSelector::ID(ref id) => {
+                    if !bf.might_contain(id) {
+                        return false
+                    }
+                },
+                SimpleSelector::Class(ref class) => {
+                    if !bf.might_contain(class) {
+                        return false
+                    }
+                },
+                _ => {},
+            }
+        }
+    }
+
+    // If we haven't proven otherwise, it may match.
+    true
+}
+
 /// Determines whether the given element matches the given complex selector.
-///
-/// NB: If you add support for any new kinds of selectors to this routine, be sure to set
-/// `shareable` to false unless you are willing to update the style sharing logic. Otherwise things
-/// will almost certainly break as elements will start mistakenly sharing styles. (See
-/// `can_share_style_with` in `servo/components/style/matching.rs`.)
 pub fn matches_complex_selector<E>(selector: &ComplexSelector<E::Impl>,
                                    element: &E,
                                    parent_bf: Option<&BloomFilter>,
                                    relations: &mut StyleRelations,
                                    flags: &mut ElementSelectorFlags)
                                    -> bool
     where E: Element
 {
-    match matches_complex_selector_internal(selector, element, parent_bf, relations, flags) {
+    if let Some(filter) = parent_bf {
+        if !may_match::<E>(selector, filter) {
+            return false;
+        }
+    }
+
+    match matches_complex_selector_internal(selector, element, relations, flags) {
         SelectorMatchingResult::Matched => {
             match selector.next {
                 Some((_, Combinator::NextSibling)) |
                 Some((_, Combinator::LaterSibling)) => *relations |= AFFECTED_BY_SIBLINGS,
                 _ => {}
             }
 
             true
@@ -185,91 +235,29 @@ pub fn matches_complex_selector<E>(selec
 #[derive(PartialEq, Eq, Copy, Clone)]
 enum SelectorMatchingResult {
     Matched,
     NotMatchedAndRestartFromClosestLaterSibling,
     NotMatchedAndRestartFromClosestDescendant,
     NotMatchedGlobally,
 }
 
-/// Quickly figures out whether or not the complex selector is worth doing more
-/// work on. If the simple selectors don't match, or there's a child selector
-/// that does not appear in the bloom parent bloom filter, we can exit early.
-fn can_fast_reject<E>(mut selector: &ComplexSelector<E::Impl>,
-                      element: &E,
-                      parent_bf: Option<&BloomFilter>,
-                      relations: &mut StyleRelations,
-                      flags: &mut ElementSelectorFlags)
-                      -> Option<SelectorMatchingResult>
-    where E: Element
-{
-    if !selector.compound_selector.iter().all(|simple_selector| {
-      matches_simple_selector(simple_selector, element, parent_bf, relations, flags) }) {
-        return Some(SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling);
-    }
-
-    let bf: &BloomFilter = match parent_bf {
-        None => return None,
-        Some(ref bf) => bf,
-    };
-
-    // See if the bloom filter can exclude any of the descendant selectors, and
-    // reject if we can.
-    loop {
-         match selector.next {
-             None => break,
-             Some((ref cs, Combinator::Descendant)) => selector = &**cs,
-             Some((ref cs, _)) => {
-                 selector = &**cs;
-                 continue;
-             }
-         };
-
-        for ss in selector.compound_selector.iter() {
-            match *ss {
-                SimpleSelector::LocalName(LocalName { ref name, ref lower_name })  => {
-                    if !bf.might_contain(name) &&
-                       !bf.might_contain(lower_name) {
-                        return Some(SelectorMatchingResult::NotMatchedGlobally);
-                    }
-                },
-                SimpleSelector::Namespace(ref namespace) => {
-                    if !bf.might_contain(&namespace.url) {
-                        return Some(SelectorMatchingResult::NotMatchedGlobally);
-                    }
-                },
-                SimpleSelector::ID(ref id) => {
-                    if !bf.might_contain(id) {
-                        return Some(SelectorMatchingResult::NotMatchedGlobally);
-                    }
-                },
-                SimpleSelector::Class(ref class) => {
-                    if !bf.might_contain(class) {
-                        return Some(SelectorMatchingResult::NotMatchedGlobally);
-                    }
-                },
-                _ => {},
-            }
-        }
-    }
-
-    // Can't fast reject.
-    None
-}
-
 fn matches_complex_selector_internal<E>(selector: &ComplexSelector<E::Impl>,
-                                         element: &E,
-                                         parent_bf: Option<&BloomFilter>,
-                                         relations: &mut StyleRelations,
-                                         flags: &mut ElementSelectorFlags)
-                                         -> SelectorMatchingResult
+                                        element: &E,
+                                        relations: &mut StyleRelations,
+                                        flags: &mut ElementSelectorFlags)
+                                        -> SelectorMatchingResult
      where E: Element
 {
-    if let Some(result) = can_fast_reject(selector, element, parent_bf, relations, flags) {
-        return result;
+    let matches_all_simple_selectors = selector.compound_selector.iter().all(|simple| {
+        matches_simple_selector(simple, element, relations, flags)
+    });
+
+    if !matches_all_simple_selectors {
+        return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
     }
 
     match selector.next {
         None => SelectorMatchingResult::Matched,
         Some((ref next_selector, combinator)) => {
             let (siblings, candidate_not_found) = match combinator {
                 Combinator::Child => (false, SelectorMatchingResult::NotMatchedGlobally),
                 Combinator::Descendant => (false, SelectorMatchingResult::NotMatchedGlobally),
@@ -282,20 +270,19 @@ fn matches_complex_selector_internal<E>(
                 element.parent_element()
             };
             loop {
                 let element = match next_element {
                     None => return candidate_not_found,
                     Some(next_element) => next_element,
                 };
                 let result = matches_complex_selector_internal(&**next_selector,
-                                                                &element,
-                                                                parent_bf,
-                                                                relations,
-                                                                flags);
+                                                               &element,
+                                                               relations,
+                                                               flags);
                 match (result, combinator) {
                     // Return the status immediately.
                     (SelectorMatchingResult::Matched, _) => return result,
                     (SelectorMatchingResult::NotMatchedGlobally, _) => return result,
 
                     // Upgrade the failure status to
                     // NotMatchedAndRestartFromClosestDescendant.
                     (_, Combinator::Child) => return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
@@ -327,17 +314,16 @@ fn matches_complex_selector_internal<E>(
     }
 }
 
 /// Determines whether the given element matches the given single selector.
 #[inline]
 fn matches_simple_selector<E>(
         selector: &SimpleSelector<E::Impl>,
         element: &E,
-        parent_bf: Option<&BloomFilter>,
         relations: &mut StyleRelations,
         flags: &mut ElementSelectorFlags)
         -> bool
     where E: Element
 {
     macro_rules! relation_if {
         ($ex:expr, $flag:ident) => {
             if $ex {
@@ -461,17 +447,20 @@ fn matches_simple_selector<E>(
         }
         SimpleSelector::OnlyOfType => {
             relation_if!(matches_generic_nth_child(element, 0, 1, true, false, flags) &&
                          matches_generic_nth_child(element, 0, 1, true, true, flags),
                          AFFECTED_BY_CHILD_INDEX)
         }
         SimpleSelector::Negation(ref negated) => {
             !negated.iter().all(|s| {
-                matches_complex_selector(s, element, parent_bf, relations, flags)
+                match matches_complex_selector_internal(s, element, relations, flags) {
+                    SelectorMatchingResult::Matched => true,
+                    _ => false,
+                }
             })
         }
     }
 }
 
 #[inline]
 fn matches_generic_nth_child<E>(element: &E,
                                 a: i32,