servo: Merge #19781 - Optimize selector matching for some common cases (from upsuper:matching-opt); r=emilio
authorXidorn Quan <me@upsuper.org>
Tue, 16 Jan 2018 16:47:29 -0600
changeset 399548 f15b8a999a451caf5ac225f6c522beadc509c605
parent 399547 bd1e3857b5bac3dc710521a5eb7377a1168b56ac
child 399549 aee6cb0464d79fe892e526fc566e2f96629da61c
push id58174
push userservo-vcs-sync@mozilla.com
push dateTue, 16 Jan 2018 23:47:13 +0000
treeherderautoland@f15b8a999a45 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio
milestone59.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 #19781 - Optimize selector matching for some common cases (from upsuper:matching-opt); r=emilio This is the "better way" I mentioned in #19774, which seems to actually improve the score of dromaeo_css on talos. Source-Repo: https://github.com/servo/servo Source-Revision: 525758ea5ef67148c28acae9404916691e9a960c
servo/components/selectors/matching.rs
servo/components/style/invalidation/element/invalidator.rs
--- a/servo/components/selectors/matching.rs
+++ b/servo/components/selectors/matching.rs
@@ -3,16 +3,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use attr::{ParsedAttrSelectorOperation, AttrSelectorOperation, NamespaceConstraint};
 use bloom::{BLOOM_HASH_MASK, BloomFilter};
 use nth_index_cache::NthIndexCacheInner;
 use parser::{AncestorHashes, Combinator, Component, LocalName};
 use parser::{Selector, SelectorImpl, SelectorIter, SelectorList};
 use std::borrow::Borrow;
+use std::iter;
 use tree::Element;
 
 pub use context::*;
 
 // The bloom filter for descendant CSS selectors will have a <1% false
 // positive rate until it has this many selectors in it, then it will
 // rapidly increase.
 pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
@@ -217,17 +218,17 @@ pub enum CompoundSelectorMatchingResult 
 
 /// Matches a compound selector belonging to `selector`, starting at offset
 /// `from_offset`, matching left to right.
 ///
 /// Requires that `from_offset` points to a `Combinator`.
 ///
 /// NOTE(emilio): This doesn't allow to match in the leftmost sequence of the
 /// complex selector, but it happens to be the case we don't need it.
-pub fn matches_compound_selector<E>(
+pub fn matches_compound_selector_from<E>(
     selector: &Selector<E::Impl>,
     mut from_offset: usize,
     context: &mut MatchingContext<E::Impl>,
     element: &E,
 ) -> CompoundSelectorMatchingResult
 where
     E: Element
 {
@@ -421,41 +422,31 @@ fn matches_complex_selector_internal<E, 
     rightmost: Rightmost,
 ) -> SelectorMatchingResult
 where
     E: Element,
     F: FnMut(&E, ElementSelectorFlags),
 {
     debug!("Matching complex selector {:?} for {:?}", selector_iter, element);
 
-    let matches_all_simple_selectors = {
-        let matches_hover_and_active_quirk =
-            matches_hover_and_active_quirk(&selector_iter, context, rightmost);
-        let mut local_context =
-            LocalMatchingContext {
-                shared: context,
-                visited_handling,
-                matches_hover_and_active_quirk,
-            };
-        selector_iter.all(|simple| {
-            matches_simple_selector(
-                simple,
-                element,
-                &mut local_context,
-                flags_setter,
-            )
-        })
-    };
+    let matches_compound_selector = matches_compound_selector(
+        &mut selector_iter,
+        element,
+        context,
+        visited_handling,
+        flags_setter,
+        rightmost
+    );
 
     let combinator = selector_iter.next_sequence();
     if combinator.map_or(false, |c| c.is_sibling()) {
         flags_setter(element, ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS);
     }
 
-    if !matches_all_simple_selectors {
+    if !matches_compound_selector {
         return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
     }
 
     let combinator = match combinator {
         None => return SelectorMatchingResult::Matched,
         Some(c) => c,
     };
 
@@ -536,18 +527,94 @@ where
             } else {
                 visited_handling
             };
 
         next_element = next_element_for_combinator(&element, combinator);
     }
 }
 
+#[inline]
+fn matches_local_name<E>(
+    element: &E,
+    local_name: &LocalName<E::Impl>
+) -> bool
+where
+    E: Element,
+{
+    let name = select_name(
+        element.is_html_element_in_html_document(),
+        &local_name.name,
+        &local_name.lower_name
+    ).borrow();
+    element.get_local_name() == name
+}
+
+/// Determines whether the given element matches the given compound selector.
+#[inline]
+fn matches_compound_selector<E, F>(
+    selector_iter: &mut SelectorIter<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    visited_handling: VisitedHandlingMode,
+    flags_setter: &mut F,
+    rightmost: Rightmost,
+) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    let matches_hover_and_active_quirk =
+        matches_hover_and_active_quirk(&selector_iter, context, rightmost);
+
+    // Handle some common cases first.
+    // We may want to get rid of this at some point if we can make the
+    // generic case fast enough.
+    let mut selector = selector_iter.next();
+    if let Some(&Component::LocalName(ref local_name)) = selector {
+        if !matches_local_name(element, local_name) {
+            return false;
+        }
+        selector = selector_iter.next();
+    }
+    let class_and_id_case_sensitivity = context.classes_and_ids_case_sensitivity();
+    if let Some(&Component::ID(ref id)) = selector {
+        if !element.has_id(id, class_and_id_case_sensitivity) {
+            return false;
+        }
+        selector = selector_iter.next();
+    }
+    while let Some(&Component::Class(ref class)) = selector {
+        if !element.has_class(class, class_and_id_case_sensitivity) {
+            return false;
+        }
+        selector = selector_iter.next();
+    }
+    let selector = match selector {
+        Some(s) => s,
+        None => return true,
+    };
+
+    let mut local_context =
+        LocalMatchingContext {
+            shared: context,
+            visited_handling,
+            matches_hover_and_active_quirk,
+        };
+    iter::once(selector).chain(selector_iter).all(|simple| {
+        matches_simple_selector(
+            simple,
+            element,
+            &mut local_context,
+            flags_setter,
+        )
+    })
+}
+
 /// Determines whether the given element matches the given single selector.
-#[inline]
 fn matches_simple_selector<E, F>(
     selector: &Component<E::Impl>,
     element: &E,
     context: &mut LocalMatchingContext<E::Impl>,
     flags_setter: &mut F,
 ) -> bool
 where
     E: Element,
@@ -566,19 +633,18 @@ where
                     flags_setter,
                 );
             context.shared.nesting_level -= 1;
             result
         }
         Component::PseudoElement(ref pseudo) => {
             element.match_pseudo_element(pseudo, context.shared)
         }
-        Component::LocalName(LocalName { ref name, ref lower_name }) => {
-            let is_html = element.is_html_element_in_html_document();
-            element.get_local_name() == select_name(is_html, name, lower_name).borrow()
+        Component::LocalName(ref local_name) => {
+            matches_local_name(element, local_name)
         }
         Component::ExplicitUniversalType |
         Component::ExplicitAnyNamespace => {
             true
         }
         Component::Namespace(_, ref url) |
         Component::DefaultNamespace(ref url) => {
             element.get_namespace() == url.borrow()
--- a/servo/components/style/invalidation/element/invalidator.rs
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -4,17 +4,17 @@
 
 //! The struct that takes care of encapsulating all the logic on where and how
 //! element styles need to be invalidated.
 
 use context::StackLimitChecker;
 use dom::{TElement, TNode};
 use selector_parser::SelectorImpl;
 use selectors::matching::{CompoundSelectorMatchingResult, MatchingContext};
-use selectors::matching::matches_compound_selector;
+use selectors::matching::matches_compound_selector_from;
 use selectors::parser::{Combinator, Component, Selector};
 use smallvec::SmallVec;
 use std::fmt;
 
 /// A trait to abstract the collection of invalidations for a given pass.
 pub trait InvalidationProcessor<'a, E>
 where
     E: TElement,
@@ -686,17 +686,17 @@ where
         invalidation: &Invalidation<'b>,
         descendant_invalidations: &mut DescendantInvalidationLists<'b>,
         sibling_invalidations: &mut InvalidationVector<'b>,
         invalidation_kind: InvalidationKind,
     ) -> SingleInvalidationResult {
         debug!("TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})",
                self.element, invalidation, invalidation_kind);
 
-        let matching_result = matches_compound_selector(
+        let matching_result = matches_compound_selector_from(
             &invalidation.selector,
             invalidation.offset,
             self.processor.matching_context(),
             &self.element
         );
 
         let mut invalidated_self = false;
         let mut matched = false;