Bug 1640843 - Finer grained invalidation for attribute changes. r=heycam
authorEmilio Cobos Álvarez <emilio@crisal.io>
Wed, 27 May 2020 09:17:47 +0000
changeset 532346 636b70578d73752e1d1a39acb9fadf641a86b779
parent 532345 7206207af8c4a14e959d05df93995d27873f21b6
child 532347 abfad4bc648f9669b84dda2dc87a729d49dcb45f
push id37454
push userccoroiu@mozilla.com
push dateWed, 27 May 2020 16:14:31 +0000
treeherdermozilla-central@a1dd9afbfdf5 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersheycam
bugs1640843
milestone78.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
Bug 1640843 - Finer grained invalidation for attribute changes. r=heycam This should help out quite a bit with uBO, which has lots of very general attribute selectors. We invalidate per attribute name rather than using a SelectorMap, which prevents matching for attribute selectors that can't have changed. The idea is that this should be generally cheaper, though there are cases where this would be a slight pesimization. For example, if there's an attribute selector like: my-specific-element[my-attribute] { /* ... */ } And you change `my-attribute` in an element that isn't a `my-specific-element`, before that the SelectorMap would've prevented us from selector-matching completely. Now we'd still run selector-matching for that (though the matching would be pretty cheap). However I think this should speed up things generally, let's see what the perf tests think before landing this though. Differential Revision: https://phabricator.services.mozilla.com/D76825
layout/style/ServoElementSnapshot.cpp
layout/style/ServoElementSnapshot.h
servo/components/style/gecko/selector_parser.rs
servo/components/style/gecko/snapshot.rs
servo/components/style/invalidation/element/invalidation_map.rs
servo/components/style/invalidation/element/state_and_attributes.rs
servo/components/style/servo/selector_parser.rs
--- a/layout/style/ServoElementSnapshot.cpp
+++ b/layout/style/ServoElementSnapshot.cpp
@@ -13,18 +13,17 @@
 namespace mozilla {
 
 ServoElementSnapshot::ServoElementSnapshot(const Element& aElement)
     : mState(0),
       mContains(Flags(0)),
       mIsTableBorderNonzero(false),
       mIsMozBrowserFrame(false),
       mClassAttributeChanged(false),
-      mIdAttributeChanged(false),
-      mOtherAttributeChanged(false) {
+      mIdAttributeChanged(false) {
   MOZ_COUNT_CTOR(ServoElementSnapshot);
   MOZ_ASSERT(NS_IsMainThread());
   mIsInChromeDocument = nsContentUtils::IsChromeDoc(aElement.OwnerDoc());
   mSupportsLangAttr = aElement.SupportsLangAttr();
 }
 
 void ServoElementSnapshot::AddOtherPseudoClassState(const Element& aElement) {
   if (HasOtherPseudoClassState()) {
--- a/layout/style/ServoElementSnapshot.h
+++ b/layout/style/ServoElementSnapshot.h
@@ -143,41 +143,47 @@ class ServoElementSnapshot {
   }
 
  private:
   // TODO: Profile, a 1 or 2 element AutoTArray could be worth it, given we know
   // we're dealing with attribute changes when we take snapshots of attributes,
   // though it can be wasted space if we deal with a lot of state-only
   // snapshots.
   nsTArray<AttrArray::InternalAttr> mAttrs;
+  nsTArray<RefPtr<nsAtom>> mChangedAttrNames;
   nsAttrValue mClass;
   ServoStateType mState;
   Flags mContains;
   bool mIsInChromeDocument : 1;
   bool mSupportsLangAttr : 1;
   bool mIsTableBorderNonzero : 1;
   bool mIsMozBrowserFrame : 1;
   bool mClassAttributeChanged : 1;
   bool mIdAttributeChanged : 1;
-  bool mOtherAttributeChanged : 1;
 };
 
 inline void ServoElementSnapshot::AddAttrs(const Element& aElement,
                                            int32_t aNameSpaceID,
                                            nsAtom* aAttribute) {
   if (aNameSpaceID == kNameSpaceID_None) {
     if (aAttribute == nsGkAtoms::_class) {
+      if (mClassAttributeChanged) {
+        return;
+      }
       mClassAttributeChanged = true;
     } else if (aAttribute == nsGkAtoms::id) {
+      if (mIdAttributeChanged) {
+        return;
+      }
       mIdAttributeChanged = true;
-    } else {
-      mOtherAttributeChanged = true;
     }
-  } else {
-    mOtherAttributeChanged = true;
+  }
+
+  if (!mChangedAttrNames.Contains(aAttribute)) {
+    mChangedAttrNames.AppendElement(aAttribute);
   }
 
   if (HasAttrs()) {
     return;
   }
 
   uint32_t attrCount = aElement.GetAttrCount();
   mAttrs.SetCapacity(attrCount);
--- a/servo/components/style/gecko/selector_parser.rs
+++ b/servo/components/style/gecko/selector_parser.rs
@@ -224,27 +224,16 @@ impl NonTSPseudoClass {
                       NonTSPseudoClass::MozLocaleDir(_) |
                       NonTSPseudoClass::MozWindowInactive |
                       // Similar for the document themes.
                       NonTSPseudoClass::MozLWTheme |
                       NonTSPseudoClass::MozLWThemeBrightText |
                       NonTSPseudoClass::MozLWThemeDarkText
             )
     }
-
-    /// Returns true if the evaluation of the pseudo-class depends on the
-    /// element's attributes.
-    pub fn is_attr_based(&self) -> bool {
-        matches!(
-            *self,
-            NonTSPseudoClass::MozTableBorderNonzero |
-                NonTSPseudoClass::MozBrowserFrame |
-                NonTSPseudoClass::Lang(..)
-        )
-    }
 }
 
 impl ::selectors::parser::NonTSPseudoClass for NonTSPseudoClass {
     type Impl = SelectorImpl;
 
     #[inline]
     fn is_active_or_hover(&self) -> bool {
         matches!(*self, NonTSPseudoClass::Active | NonTSPseudoClass::Hover)
--- a/servo/components/style/gecko/snapshot.rs
+++ b/servo/components/style/gecko/snapshot.rs
@@ -65,21 +65,25 @@ impl GeckoElementSnapshot {
     }
 
     /// Returns true if the snapshot recorded a class attribute change.
     #[inline]
     pub fn class_changed(&self) -> bool {
         self.mClassAttributeChanged()
     }
 
-    /// Returns true if the snapshot recorded an attribute change which isn't a
-    /// class / id
+    /// Executes the callback once for each attribute that changed.
     #[inline]
-    pub fn other_attr_changed(&self) -> bool {
-        self.mOtherAttributeChanged()
+    pub fn each_attr_changed<F>(&self, mut callback: F)
+    where
+        F: FnMut(&Atom),
+    {
+        for attr in self.mChangedAttrNames.iter() {
+            unsafe { Atom::with(attr.mRawPtr, &mut callback) }
+        }
     }
 
     /// selectors::Element::attr_matches
     pub fn attr_matches(
         &self,
         ns: &NamespaceConstraint<&Namespace>,
         local_name: &Atom,
         operation: &AttrSelectorOperation<&Atom>,
--- a/servo/components/style/invalidation/element/invalidation_map.rs
+++ b/servo/components/style/invalidation/element/invalidation_map.rs
@@ -1,20 +1,20 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
 
 //! Code for invalidations due to state or attribute changes.
 
 use crate::context::QuirksMode;
 use crate::element_state::{DocumentState, ElementState};
-use crate::selector_map::{MaybeCaseInsensitiveHashMap, SelectorMap, SelectorMapEntry};
+use crate::selector_map::{MaybeCaseInsensitiveHashMap, PrecomputedHashMap, SelectorMap, SelectorMapEntry};
 use crate::selector_parser::SelectorImpl;
 use crate::{Atom, LocalName, Namespace};
-use fallible::FallibleVec;
+use fallible::{FallibleVec, FallibleHashMap};
 use hashbrown::CollectionAllocErr;
 use selectors::attr::NamespaceConstraint;
 use selectors::parser::{Combinator, Component};
 use selectors::parser::{Selector, SelectorIter};
 use selectors::visitor::SelectorVisitor;
 use smallvec::SmallVec;
 
 /// Mapping between (partial) CompoundSelectors (and the combinator to their
@@ -170,29 +170,16 @@ pub struct DocumentStateDependency {
         ignore_malloc_size_of = "CssRules have primary refs, we measure there"
     )]
     #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")]
     pub dependency: Dependency,
     /// The state this dependency is affected by.
     pub state: DocumentState,
 }
 
-bitflags! {
-    /// A set of flags that denote whether any invalidations have occurred
-    /// for a particular attribute selector.
-    #[derive(MallocSizeOf)]
-    #[repr(C)]
-    pub struct InvalidationMapFlags : u8 {
-        /// Whether [class] or such is used.
-        const HAS_CLASS_ATTR_SELECTOR = 1 << 0;
-        /// Whether [id] or such is used.
-        const HAS_ID_ATTR_SELECTOR = 1 << 1;
-    }
-}
-
 /// A map where we store invalidations.
 ///
 /// This is slightly different to a SelectorMap, in the sense of that the same
 /// selector may appear multiple times.
 ///
 /// In particular, we want to lookup as few things as possible to get the fewer
 /// selectors the better, so this looks up by id, class, or looks at the list of
 /// state/other attribute affecting selectors.
@@ -204,56 +191,53 @@ pub struct InvalidationMap {
     /// A map from a given id to all the selectors with that ID in the
     /// stylesheets currently applying to the document.
     pub id_to_selector: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>,
     /// A map of all the state dependencies.
     pub state_affecting_selectors: SelectorMap<StateDependency>,
     /// A list of document state dependencies in the rules we represent.
     pub document_state_selectors: Vec<DocumentStateDependency>,
     /// A map of other attribute affecting selectors.
-    pub other_attribute_affecting_selectors: SelectorMap<Dependency>,
-    /// A set of flags that contain whether various special attributes are used
-    /// in this invalidation map.
-    pub flags: InvalidationMapFlags,
+    pub other_attribute_affecting_selectors: PrecomputedHashMap<Atom, SmallVec<[Dependency; 1]>>,
 }
 
 impl InvalidationMap {
     /// Creates an empty `InvalidationMap`.
     pub fn new() -> Self {
         Self {
             class_to_selector: MaybeCaseInsensitiveHashMap::new(),
             id_to_selector: MaybeCaseInsensitiveHashMap::new(),
             state_affecting_selectors: SelectorMap::new(),
             document_state_selectors: Vec::new(),
-            other_attribute_affecting_selectors: SelectorMap::new(),
-            flags: InvalidationMapFlags::empty(),
+            other_attribute_affecting_selectors: PrecomputedHashMap::default(),
         }
     }
 
     /// Returns the number of dependencies stored in the invalidation map.
     pub fn len(&self) -> usize {
         self.state_affecting_selectors.len() +
             self.document_state_selectors.len() +
-            self.other_attribute_affecting_selectors.len() +
+            self.other_attribute_affecting_selectors
+                .iter()
+                .fold(0, |accum, (_, ref v)| accum + v.len()) +
             self.id_to_selector
                 .iter()
                 .fold(0, |accum, (_, ref v)| accum + v.len()) +
             self.class_to_selector
                 .iter()
                 .fold(0, |accum, (_, ref v)| accum + v.len())
     }
 
     /// Clears this map, leaving it empty.
     pub fn clear(&mut self) {
         self.class_to_selector.clear();
         self.id_to_selector.clear();
         self.state_affecting_selectors.clear();
         self.document_state_selectors.clear();
         self.other_attribute_affecting_selectors.clear();
-        self.flags = InvalidationMapFlags::empty();
     }
 
     /// Adds a selector to this `InvalidationMap`.  Returns Err(..) to
     /// signify OOM.
     pub fn note_selector(
         &mut self,
         selector: &Selector<SelectorImpl>,
         quirks_mode: QuirksMode,
@@ -295,27 +279,23 @@ impl InvalidationMap {
 }
 
 struct PerCompoundState {
     /// The offset at which our compound starts.
     offset: usize,
 
     /// The state this compound selector is affected by.
     element_state: ElementState,
-
-    /// Whether we've added a generic attribute dependency for this selector.
-    added_attr_dependency: bool,
 }
 
 impl PerCompoundState {
     fn new(offset: usize) -> Self {
         Self {
             offset,
             element_state: ElementState::empty(),
-            added_attr_dependency: false,
         }
     }
 }
 
 /// A struct that collects invalidations for a given compound selector.
 struct SelectorDependencyCollector<'a> {
     map: &'a mut InvalidationMap,
 
@@ -382,30 +362,35 @@ impl<'a> SelectorDependencyCollector<'a>
             let combinator = iter.next_sequence();
             if combinator.is_none() {
                 return true;
             }
             index += 1; // account for the combinator
         }
     }
 
-    fn add_attr_dependency(&mut self) -> bool {
-        debug_assert!(!self.compound_state.added_attr_dependency);
-        self.compound_state.added_attr_dependency = true;
-
+    fn add_attr_dependency(&mut self, name: LocalName) -> bool {
         let dependency = self.dependency();
-        let result = self.map.other_attribute_affecting_selectors.insert(
-            dependency,
-            self.quirks_mode,
-        );
-        if let Err(alloc_error) = result {
-            *self.alloc_error = Some(alloc_error);
-            return false;
+
+        let map = &mut self.map.other_attribute_affecting_selectors;
+        let entry = match map.try_entry(name) {
+            Ok(entry) => entry,
+            Err(err) => {
+                *self.alloc_error = Some(err);
+                return false;
+            },
+        };
+
+        match entry.or_insert_with(SmallVec::new).try_push(dependency) {
+            Ok(..) => true,
+            Err(err) => {
+                *self.alloc_error = Some(err);
+                return false;
+            }
         }
-        true
     }
 
     fn dependency(&self) -> Dependency {
         let mut parent = None;
 
         // TODO(emilio): Maybe we should refcount the parent dependencies, or
         // cache them or something.
         for &(ref selector, ref selector_offset) in self.parent_selectors.iter() {
@@ -489,54 +474,56 @@ impl<'a> SelectorVisitor for SelectorDep
                 };
                 let entry = match map.try_entry(atom.clone(), self.quirks_mode) {
                     Ok(entry) => entry,
                     Err(err) => {
                         *self.alloc_error = Some(err);
                         return false;
                     },
                 };
-                entry.or_insert_with(SmallVec::new).try_push(dependency).is_ok()
+                match entry.or_insert_with(SmallVec::new).try_push(dependency) {
+                    Ok(..) => true,
+                    Err(err) => {
+                        *self.alloc_error = Some(err);
+                        return false;
+                    }
+                }
             },
             Component::NonTSPseudoClass(ref pc) => {
                 self.compound_state.element_state |= match *pc {
                     #[cfg(feature = "gecko")]
                     NonTSPseudoClass::Dir(ref dir) => dir.element_state(),
                     _ => pc.state_flag(),
                 };
                 *self.document_state |= pc.document_state_flag();
 
-                if !self.compound_state.added_attr_dependency && pc.is_attr_based() {
-                    self.add_attr_dependency()
-                } else {
-                    true
-                }
+                let attr_name = match *pc {
+                    #[cfg(feature = "gecko")]
+                    NonTSPseudoClass::MozTableBorderNonzero => local_name!("border"),
+                    #[cfg(feature = "gecko")]
+                    NonTSPseudoClass::MozBrowserFrame => local_name!("mozbrowser"),
+                    NonTSPseudoClass::Lang(..) => local_name!("lang"),
+                    _ => return true,
+                };
+
+                self.add_attr_dependency(attr_name)
             },
             _ => true,
         }
     }
 
     fn visit_attribute_selector(
         &mut self,
-        constraint: &NamespaceConstraint<&Namespace>,
-        _local_name: &LocalName,
+        _: &NamespaceConstraint<&Namespace>,
+        local_name: &LocalName,
         local_name_lower: &LocalName,
     ) -> bool {
-        let may_match_in_no_namespace = match *constraint {
-            NamespaceConstraint::Any => true,
-            NamespaceConstraint::Specific(ref ns) => ns.is_empty(),
-        };
-
-        if may_match_in_no_namespace {
-            if *local_name_lower == local_name!("id") {
-                self.map.flags.insert(InvalidationMapFlags::HAS_ID_ATTR_SELECTOR)
-            } else if *local_name_lower == local_name!("class") {
-                self.map.flags.insert(InvalidationMapFlags::HAS_CLASS_ATTR_SELECTOR)
-            }
+        if !self.add_attr_dependency(local_name.clone()) {
+            return false;
         }
 
-        if !self.compound_state.added_attr_dependency {
-            self.add_attr_dependency()
-        } else {
-            true
+        if local_name != local_name_lower && !self.add_attr_dependency(local_name_lower.clone()) {
+            return false;
         }
+
+        true
     }
 }
--- a/servo/components/style/invalidation/element/state_and_attributes.rs
+++ b/servo/components/style/invalidation/element/state_and_attributes.rs
@@ -37,17 +37,16 @@ where
     removed_id: Option<&'a WeakAtom>,
     added_id: Option<&'a WeakAtom>,
     classes_removed: &'a SmallVec<[Atom; 8]>,
     classes_added: &'a SmallVec<[Atom; 8]>,
     state_changes: ElementState,
     descendant_invalidations: &'a mut DescendantInvalidationLists<'selectors>,
     sibling_invalidations: &'a mut InvalidationVector<'selectors>,
     invalidates_self: bool,
-    attr_selector_flags: InvalidationMapFlags,
 }
 
 /// An invalidation processor for style changes due to state and attribute
 /// changes.
 pub struct StateAndAttrInvalidationProcessor<'a, 'b: 'a, E: TElement> {
     shared_context: &'a SharedStyleContext<'b>,
     element: E,
     data: &'a mut ElementData,
@@ -192,18 +191,16 @@ where
 
         let state_changes = wrapper.state_changes();
         let snapshot = wrapper.snapshot().expect("has_snapshot lied");
 
         if !snapshot.has_attrs() && state_changes.is_empty() {
             return false;
         }
 
-        let mut attr_selector_flags = InvalidationMapFlags::empty();
-
         // If we the visited state changed, we force a restyle here. Matching
         // doesn't depend on the actual visited state at all, so we can't look
         // at matching results to decide what to do for this case.
         //
         // TODO(emilio): This piece of code should be removed when
         // layout.css.always-repaint-on-unvisited is true, since we cannot get
         // into this situation in that case.
         if state_changes.contains(ElementState::IN_VISITED_OR_UNVISITED_STATE) {
@@ -211,17 +208,16 @@ where
             // We can't just return here because there may also be attribute
             // changes as well that imply additional hints for siblings.
             self.data.hint.insert(RestyleHint::restyle_subtree());
         }
 
         let mut classes_removed = SmallVec::<[Atom; 8]>::new();
         let mut classes_added = SmallVec::<[Atom; 8]>::new();
         if snapshot.class_changed() {
-            attr_selector_flags.insert(InvalidationMapFlags::HAS_CLASS_ATTR_SELECTOR);
             // TODO(emilio): Do this more efficiently!
             snapshot.each_class(|c| {
                 if !element.has_class(c, CaseSensitivity::CaseSensitive) {
                     classes_removed.push(c.clone())
                 }
             });
 
             element.each_class(|c| {
@@ -229,44 +225,42 @@ where
                     classes_added.push(c.clone())
                 }
             })
         }
 
         let mut id_removed = None;
         let mut id_added = None;
         if snapshot.id_changed() {
-            attr_selector_flags.insert(InvalidationMapFlags::HAS_ID_ATTR_SELECTOR);
             let old_id = snapshot.id_attr();
             let current_id = element.id();
 
             if old_id != current_id {
                 id_removed = old_id;
                 id_added = current_id;
             }
         }
 
         if log_enabled!(::log::Level::Debug) {
-            debug!(
-                "Collecting changes for: {:?}, flags {:?}",
-                element, attr_selector_flags
-            );
+            debug!("Collecting changes for: {:?}", element);
             if !state_changes.is_empty() {
                 debug!(" > state: {:?}", state_changes);
             }
             if snapshot.id_changed() {
                 debug!(" > id changed: +{:?} -{:?}", id_added, id_removed);
             }
             if snapshot.class_changed() {
                 debug!(
                     " > class changed: +{:?} -{:?}",
                     classes_added, classes_removed
                 );
             }
-            if snapshot.other_attr_changed() {
+            let mut attributes_changed = false;
+            snapshot.each_attr_changed(|_| { attributes_changed = true; });
+            if attributes_changed {
                 debug!(
                     " > attributes changed, old: {}",
                     snapshot.debug_list_attributes()
                 )
             }
         }
 
         let lookup_element = if element.implemented_pseudo_element().is_some() {
@@ -291,17 +285,16 @@ where
                 matching_context: &mut self.matching_context,
                 removed_id: id_removed,
                 added_id: id_added,
                 classes_removed: &classes_removed,
                 classes_added: &classes_added,
                 descendant_invalidations,
                 sibling_invalidations,
                 invalidates_self: false,
-                attr_selector_flags,
             };
 
             let document_origins = if !matches_document_author_rules {
                 OriginSet::ORIGIN_USER_AGENT | OriginSet::ORIGIN_USER
             } else {
                 OriginSet::all()
             };
 
@@ -401,42 +394,30 @@ where
         for class in self.classes_added.iter().chain(self.classes_removed.iter()) {
             if let Some(deps) = map.class_to_selector.get(class, quirks_mode) {
                 for dep in deps {
                     self.scan_dependency(dep);
                 }
             }
         }
 
-        let should_examine_attribute_selector_map =
-            self.snapshot.other_attr_changed() || map.flags.intersects(self.attr_selector_flags);
-
-        if should_examine_attribute_selector_map {
-            self.collect_dependencies_in_map(&map.other_attribute_affecting_selectors)
-        }
+        self.snapshot.each_attr_changed(|attribute| {
+            if let Some(deps) = map.other_attribute_affecting_selectors.get(attribute) {
+                for dep in deps {
+                    self.scan_dependency(dep);
+                }
+            }
+        });
 
         let state_changes = self.state_changes;
         if !state_changes.is_empty() {
             self.collect_state_dependencies(&map.state_affecting_selectors, state_changes)
         }
     }
 
-    fn collect_dependencies_in_map(&mut self, map: &'selectors SelectorMap<Dependency>) {
-        map.lookup_with_additional(
-            self.lookup_element,
-            self.matching_context.quirks_mode(),
-            self.removed_id,
-            self.classes_removed,
-            |dependency| {
-                self.scan_dependency(dependency);
-                true
-            },
-        );
-    }
-
     fn collect_state_dependencies(
         &mut self,
         map: &'selectors SelectorMap<StateDependency>,
         state_changes: ElementState,
     ) {
         map.lookup_with_additional(
             self.lookup_element,
             self.matching_context.quirks_mode(),
--- a/servo/components/style/servo/selector_parser.rs
+++ b/servo/components/style/servo/selector_parser.rs
@@ -386,22 +386,16 @@ impl NonTSPseudoClass {
     pub fn document_state_flag(&self) -> DocumentState {
         DocumentState::empty()
     }
 
     /// Returns true if the given pseudoclass should trigger style sharing cache revalidation.
     pub fn needs_cache_revalidation(&self) -> bool {
         self.state_flag().is_empty()
     }
-
-    /// Returns true if the evaluation of the pseudo-class depends on the
-    /// element's attributes.
-    pub fn is_attr_based(&self) -> bool {
-        matches!(*self, NonTSPseudoClass::Lang(..))
-    }
 }
 
 /// The abstract struct we implement the selector parser implementation on top
 /// of.
 #[derive(Clone, Debug, PartialEq)]
 #[cfg_attr(feature = "servo", derive(MallocSizeOf))]
 pub struct SelectorImpl;