servo: Merge #18496 - do a second pass on the style sharing cache after computing the rule node (from bholley:2ndpass); r=emilio
authorBobby Holley <bobbyholley@gmail.com>
Thu, 14 Sep 2017 00:07:52 -0500
changeset 430356 ff89cb83be0a2a1ba74099c839d4f796981dda67
parent 430355 5e5eab26b9dec16c05f70c351d78863f8cb23900
child 430357 14207baa622e2e51dbb524db59c10840438db82d
push id7761
push userjlund@mozilla.com
push dateFri, 15 Sep 2017 00:19:52 +0000
treeherdermozilla-beta@c38455951db4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio
bugs18496, 1397976
milestone57.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 #18496 - do a second pass on the style sharing cache after computing the rule node (from bholley:2ndpass); r=emilio https://bugzilla.mozilla.org/show_bug.cgi?id=1397976 Source-Repo: https://github.com/servo/servo Source-Revision: 298b1363ffd7e830a6ad28424421ead6628ac9b7
servo/components/style/context.rs
servo/components/style/data.rs
servo/components/style/matching.rs
servo/components/style/properties/properties.mako.rs
servo/components/style/sharing/checks.rs
servo/components/style/sharing/mod.rs
servo/components/style/style_resolver.rs
servo/components/style/traversal.rs
servo/ports/geckolib/glue.rs
--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -308,16 +308,19 @@ pub struct TraversalStatistics {
     /// The total number of elements traversed.
     pub elements_traversed: u32,
     /// The number of elements where has_styles() went from false to true.
     pub elements_styled: u32,
     /// The number of elements for which we performed selector matching.
     pub elements_matched: u32,
     /// The number of cache hits from the StyleSharingCache.
     pub styles_shared: u32,
+    /// The number of styles reused via rule node comparison from the
+    /// StyleSharingCache.
+    pub styles_reused: u32,
     /// The number of selectors in the stylist.
     pub selectors: u32,
     /// The number of revalidation selectors.
     pub revalidation_selectors: u32,
     /// The number of state/attr dependencies in the dependency set.
     pub dependency_selectors: u32,
     /// The number of declarations in the stylist.
     pub declarations: u32,
@@ -342,16 +345,17 @@ impl<'a> ops::Add for &'a TraversalStati
         debug_assert!(self.dependency_selectors == 0, "set at the end");
         debug_assert!(self.declarations == 0, "set at the end");
         debug_assert!(self.stylist_rebuilds == 0, "set at the end");
         TraversalStatistics {
             elements_traversed: self.elements_traversed + other.elements_traversed,
             elements_styled: self.elements_styled + other.elements_styled,
             elements_matched: self.elements_matched + other.elements_matched,
             styles_shared: self.styles_shared + other.styles_shared,
+            styles_reused: self.styles_reused + other.styles_reused,
             selectors: 0,
             revalidation_selectors: 0,
             dependency_selectors: 0,
             declarations: 0,
             stylist_rebuilds: 0,
             traversal_time_ms: 0.0,
             is_parallel: None,
             is_large: None,
@@ -369,16 +373,17 @@ impl fmt::Display for TraversalStatistic
             "parallel"
         } else {
             "sequential"
         })?;
         writeln!(f, "[PERF],elements_traversed,{}", self.elements_traversed)?;
         writeln!(f, "[PERF],elements_styled,{}", self.elements_styled)?;
         writeln!(f, "[PERF],elements_matched,{}", self.elements_matched)?;
         writeln!(f, "[PERF],styles_shared,{}", self.styles_shared)?;
+        writeln!(f, "[PERF],styles_reused,{}", self.styles_reused)?;
         writeln!(f, "[PERF],selectors,{}", self.selectors)?;
         writeln!(f, "[PERF],revalidation_selectors,{}", self.revalidation_selectors)?;
         writeln!(f, "[PERF],dependency_selectors,{}", self.dependency_selectors)?;
         writeln!(f, "[PERF],declarations,{}", self.declarations)?;
         writeln!(f, "[PERF],stylist_rebuilds,{}", self.stylist_rebuilds)?;
         writeln!(f, "[PERF],traversal_time_ms,{}", self.traversal_time_ms)?;
         writeln!(f, "[PERF] perf block end")
     }
--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -12,34 +12,44 @@ use invalidation::element::restyle_hints
 use malloc_size_of::MallocSizeOfOps;
 use properties::ComputedValues;
 use properties::longhands::display::computed_value as display;
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage};
 use servo_arc::Arc;
 use shared_lock::StylesheetGuards;
 use std::fmt;
+use std::mem;
 use std::ops::{Deref, DerefMut};
+use style_resolver::{PrimaryStyle, ResolvedElementStyles, ResolvedStyle};
 
 bitflags! {
+    /// Various flags stored on ElementData.
     #[derive(Default)]
-    flags ElementDataFlags: u8 {
+    pub flags ElementDataFlags: u8 {
         /// Whether the styles changed for this restyle.
         const WAS_RESTYLED = 1 << 0,
         /// Whether the last traversal of this element did not do
         /// any style computation. This is not true during the initial
         /// styling pass, nor is it true when we restyle (in which case
         /// WAS_RESTYLED is set).
         ///
         /// This bit always corresponds to the last time the element was
         /// traversed, so each traversal simply updates it with the appropriate
         /// value.
         const TRAVERSED_WITHOUT_STYLING = 1 << 1,
         /// Whether we reframed/reconstructed any ancestor or self.
         const ANCESTOR_WAS_RECONSTRUCTED = 1 << 2,
+        /// Whether the primary style of this element data was reused from another
+        /// element via a rule node comparison. This allows us to differentiate
+        /// between elements that shared styles because they met all the criteria
+        /// of the style sharing cache, compared to elements that reused style
+        /// structs via rule node identity. The former gives us stronger transitive
+        /// guarantees that allows us to apply the style sharing cache to cousins.
+        const PRIMARY_STYLE_REUSED_VIA_RULE_NODE = 1 << 3,
     }
 }
 
 /// A lazily-allocated list of styles for eagerly-cascaded pseudo-elements.
 ///
 /// We use an Arc so that sharing these styles via the style sharing cache does
 /// not require duplicate allocations. We leverage the copy-on-write semantics of
 /// Arc::make_mut(), which is free (i.e. does not require atomic RMU operations)
@@ -195,17 +205,17 @@ pub struct ElementData {
     /// afte restyling.
     pub damage: RestyleDamage,
 
     /// The restyle hint, which indicates whether selectors need to be rematched
     /// for this element, its children, and its descendants.
     pub hint: RestyleHint,
 
     /// Flags.
-    flags: ElementDataFlags,
+    pub flags: ElementDataFlags,
 }
 
 /// The kind of restyle that a single element should do.
 #[derive(Debug)]
 pub enum RestyleKind {
     /// We need to run selector matching plus re-cascade, that is, a full
     /// restyle.
     MatchAndCascade,
@@ -259,16 +269,40 @@ impl ElementData {
     }
 
     /// Returns true if this element has styles.
     #[inline]
     pub fn has_styles(&self) -> bool {
         self.styles.primary.is_some()
     }
 
+    /// Returns this element's styles as resolved styles to use for sharing.
+    pub fn share_styles(&self) -> ResolvedElementStyles {
+        ResolvedElementStyles {
+            primary: self.share_primary_style(),
+            pseudos: self.styles.pseudos.clone(),
+        }
+    }
+
+    /// Returns this element's primary style as a resolved style to use for sharing.
+    pub fn share_primary_style(&self) -> PrimaryStyle {
+        let primary_is_reused = self.flags.contains(PRIMARY_STYLE_REUSED_VIA_RULE_NODE);
+        PrimaryStyle(ResolvedStyle::new(self.styles.primary().clone(), primary_is_reused))
+    }
+
+    /// Sets a new set of styles, returning the old ones.
+    pub fn set_styles(&mut self, new_styles: ResolvedElementStyles) -> ElementStyles {
+        if new_styles.primary.0.reused_via_rule_node {
+            self.flags.insert(PRIMARY_STYLE_REUSED_VIA_RULE_NODE);
+        } else {
+            self.flags.remove(PRIMARY_STYLE_REUSED_VIA_RULE_NODE);
+        }
+        mem::replace(&mut self.styles, new_styles.into())
+    }
+
     /// Returns the kind of restyling that we're going to need to do on this
     /// element, based of the stored restyle hint.
     pub fn restyle_kind(
         &self,
         shared_context: &SharedStyleContext
     ) -> RestyleKind {
         if shared_context.traversal_flags.for_animation_only() {
             return self.restyle_kind_for_animation(shared_context);
@@ -417,16 +451,38 @@ impl ElementData {
     /// each bit individually.
     #[cfg(feature = "gecko")]
     pub fn skip_applying_damage(&self) -> bool { self.reconstructed_self_or_ancestor() }
 
     /// N/A in Servo.
     #[cfg(feature = "servo")]
     pub fn skip_applying_damage(&self) -> bool { false }
 
+    /// Returns whether it is safe to perform cousin sharing based on the ComputedValues
+    /// identity of the primary style in this ElementData. There are a few subtle things
+    /// to check.
+    ///
+    /// First, if a parent element was already styled and we traversed past it without
+    /// restyling it, that may be because our clever invalidation logic was able to prove
+    /// that the styles of that element would remain unchanged despite changes to the id
+    /// or class attributes. However, style sharing relies on the strong guarantee that all
+    /// the classes and ids up the respective parent chains are identical. As such, if we
+    /// skipped styling for one (or both) of the parents on this traversal, we can't share
+    /// styles across cousins. Note that this is a somewhat conservative check. We could
+    /// tighten it by having the invalidation logic explicitly flag elements for which it
+    /// ellided styling.
+    ///
+    /// Second, we want to only consider elements whose ComputedValues match due to a hit
+    /// in the style sharing cache, rather than due to the rule-node-based reuse that
+    /// happens later in the styling pipeline. The former gives us the stronger guarantees
+    /// we need for style sharing, the latter does not.
+    pub fn safe_for_cousin_sharing(&self) -> bool {
+        !self.flags.intersects(TRAVERSED_WITHOUT_STYLING | PRIMARY_STYLE_REUSED_VIA_RULE_NODE)
+    }
+
     /// Measures memory usage.
     #[cfg(feature = "gecko")]
     pub fn size_of_excluding_cvs(&self, ops: &mut MallocSizeOfOps) -> usize {
         let n = self.styles.size_of_excluding_cvs(ops);
 
         // We may measure more fields in the future if DMD says it's worth it.
 
         n
--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -3,26 +3,27 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! High-level interface to CSS selector matching.
 
 #![allow(unsafe_code)]
 #![deny(missing_docs)]
 
 use context::{ElementCascadeInputs, SelectorFlagsMap, SharedStyleContext, StyleContext};
-use data::{ElementData, ElementStyles};
+use data::ElementData;
 use dom::TElement;
 use invalidation::element::restyle_hints::{RESTYLE_CSS_ANIMATIONS, RESTYLE_CSS_TRANSITIONS};
 use invalidation::element::restyle_hints::{RESTYLE_SMIL, RESTYLE_STYLE_ATTRIBUTE};
 use invalidation::element::restyle_hints::RestyleHint;
 use properties::ComputedValues;
 use rule_tree::{CascadeLevel, StrongRuleNode};
 use selector_parser::{PseudoElement, RestyleDamage};
 use selectors::matching::ElementSelectorFlags;
 use servo_arc::{Arc, ArcBorrow};
+use style_resolver::ResolvedElementStyles;
 use traversal_flags;
 
 /// Represents the result of comparing an element's old and new style.
 #[derive(Debug)]
 pub struct StyleDifference {
     /// The resulting damage.
     pub damage: RestyleDamage,
 
@@ -151,17 +152,17 @@ trait PrivateMatchMethods: TElement {
                 visited_rules: primary_style.get_visited_style().and_then(|s| s.rules.clone()),
             };
 
         // Actually `PseudoElementResolution` doesn't really matter.
         let style =
             StyleResolverForElement::new(*self, context, RuleInclusion::All, PseudoElementResolution::IfApplicable)
                 .cascade_style_and_visited_with_default_parents(inputs);
 
-        Some(style)
+        Some(style.into())
     }
 
     #[cfg(feature = "gecko")]
     fn needs_animations_update(
         &self,
         context: &mut StyleContext<Self>,
         old_values: Option<&Arc<ComputedValues>>,
         new_values: &ComputedValues,
@@ -525,36 +526,33 @@ pub trait MatchMethods : TElement {
     }
 
     /// Updates the styles with the new ones, diffs them, and stores the restyle
     /// damage.
     fn finish_restyle(
         &self,
         context: &mut StyleContext<Self>,
         data: &mut ElementData,
-        mut new_styles: ElementStyles,
+        mut new_styles: ResolvedElementStyles,
         important_rules_changed: bool,
     ) -> ChildCascadeRequirement {
         use app_units::Au;
         use dom::TNode;
         use std::cmp;
-        use std::mem;
-
-        debug_assert!(new_styles.primary.is_some(), "How did that happen?");
 
         self.process_animations(
             context,
             &mut data.styles.primary,
-            &mut new_styles.primary.as_mut().unwrap(),
+            &mut new_styles.primary.0.style,
             data.hint,
             important_rules_changed,
         );
 
         // First of all, update the styles.
-        let old_styles = mem::replace(&mut data.styles, new_styles);
+        let old_styles = data.set_styles(new_styles);
 
         // Propagate the "can be fragmented" bit. It would be nice to
         // encapsulate this better.
         //
         // Note that this is technically not needed for pseudos since we already
         // do that when we resolve the non-pseudo style, but it doesn't hurt
         // anyway.
         if cfg!(feature = "servo") {
--- a/servo/components/style/properties/properties.mako.rs
+++ b/servo/components/style/properties/properties.mako.rs
@@ -1992,16 +1992,23 @@ pub struct ComputedValues {
     ///
     /// In Gecko the outer ComputedValues is actually a style context,
     /// whereas ComputedValuesInner is the core set of computed values.
     ///
     /// We maintain this distinction in servo to reduce the amount of special casing.
     inner: ComputedValuesInner,
 }
 
+impl ComputedValues {
+    /// Returns the visited rules, if applicable.
+    pub fn visited_rules(&self) -> Option<<&StrongRuleNode> {
+        self.visited_style.as_ref().and_then(|s| s.rules.as_ref())
+    }
+}
+
 #[cfg(feature = "servo")]
 impl ComputedValues {
     /// Create a new refcounted `ComputedValues`
     pub fn new(
         _: &Device,
         _: Option<<&ComputedValues>,
         _: Option<<&PseudoElement>,
         custom_properties: Option<Arc<::custom_properties::CustomPropertiesMap>>,
--- a/servo/components/style/sharing/checks.rs
+++ b/servo/components/style/sharing/checks.rs
@@ -5,54 +5,57 @@
 //! Different checks done during the style sharing process in order to determine
 //! quickly whether it's worth to share style, and whether two different
 //! elements can indeed share the same style.
 
 use Atom;
 use bloom::StyleBloom;
 use context::{SelectorFlagsMap, SharedStyleContext};
 use dom::TElement;
-use servo_arc::Arc;
 use sharing::{StyleSharingCandidate, StyleSharingTarget};
 
-/// Whether styles may be shared across the children of the given parent elements.
-/// This is used to share style across cousins.
-///
-/// Both elements need to be styled already.
-pub fn can_share_style_across_parents<E>(first: Option<E>, second: Option<E>) -> bool
+/// Determines whether a target and a candidate have compatible parents for sharing.
+pub fn parents_allow_sharing<E>(
+    target: &mut StyleSharingTarget<E>,
+    candidate: &mut StyleSharingCandidate<E>
+) -> bool
     where E: TElement,
 {
-    let (first, second) = match (first, second) {
-        (Some(f), Some(s)) => (f, s),
-        _ => return false,
-    };
+    // If the identity of the parent style isn't equal, we can't share. We check
+    // this first, because the result is cached.
+    if target.parent_style_identity() != candidate.parent_style_identity() {
+        return false;
+    }
 
-    debug_assert_ne!(first, second);
+    // Siblings can always share.
+    let parent = target.inheritance_parent().unwrap();
+    let candidate_parent = candidate.element.inheritance_parent().unwrap();
+    if parent == candidate_parent {
+        return true;
+    }
 
-    let first_data = first.borrow_data().unwrap();
-    let second_data = second.borrow_data().unwrap();
-
+    // Cousins are a bit more complicated.
+    //
     // If a parent element was already styled and we traversed past it without
     // restyling it, that may be because our clever invalidation logic was able
     // to prove that the styles of that element would remain unchanged despite
     // changes to the id or class attributes. However, style sharing relies in
     // the strong guarantee that all the classes and ids up the respective parent
     // chains are identical. As such, if we skipped styling for one (or both) of
     // the parents on this traversal, we can't share styles across cousins.
     //
     // This is a somewhat conservative check. We could tighten it by having the
     // invalidation logic explicitly flag elements for which it ellided styling.
-    if first_data.traversed_without_styling() || second_data.traversed_without_styling() {
+    let parent_data = parent.borrow_data().unwrap();
+    let candidate_parent_data = candidate_parent.borrow_data().unwrap();
+    if !parent_data.safe_for_cousin_sharing() || !candidate_parent_data.safe_for_cousin_sharing() {
         return false;
     }
 
-    let same_computed_values =
-        Arc::ptr_eq(first_data.styles.primary(), second_data.styles.primary());
-
-    same_computed_values
+    true
 }
 
 /// Whether two elements have the same same style attribute (by pointer identity).
 pub fn have_same_style_attribute<E>(
     target: &mut StyleSharingTarget<E>,
     candidate: &mut StyleSharingCandidate<E>
 ) -> bool
     where E: TElement,
--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -65,23 +65,23 @@
 //! elements makes sense.
 
 use Atom;
 use applicable_declarations::ApplicableDeclarationBlock;
 use atomic_refcell::{AtomicRefCell, AtomicRefMut};
 use bloom::StyleBloom;
 use cache::LRUCache;
 use context::{SelectorFlagsMap, SharedStyleContext, StyleContext};
-use data::ElementStyles;
 use dom::{TElement, SendElement};
 use matching::MatchMethods;
 use owning_ref::OwningHandle;
 use properties::ComputedValues;
+use rule_tree::StrongRuleNode;
 use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode};
-use servo_arc::Arc;
+use servo_arc::{Arc, NonZeroPtrMut};
 use smallbitvec::SmallBitVec;
 use smallvec::SmallVec;
 use std::marker::PhantomData;
 use std::mem;
 use std::ops::Deref;
 use stylist::Stylist;
 
 mod checks;
@@ -103,29 +103,44 @@ const SHARING_CACHE_BACKING_STORE_SIZE: 
 #[derive(Clone, Copy, PartialEq)]
 pub enum StyleSharingBehavior {
     /// Style sharing allowed.
     Allow,
     /// Style sharing disallowed.
     Disallow,
 }
 
+/// Opaque pointer type to compare ComputedValues identities.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct OpaqueComputedValues(NonZeroPtrMut<()>);
+impl OpaqueComputedValues {
+    fn from(cv: &ComputedValues) -> Self {
+        let p = NonZeroPtrMut::new(cv as *const ComputedValues as *const () as *mut ());
+        OpaqueComputedValues(p)
+    }
+
+    fn eq(&self, cv: &ComputedValues) -> bool { Self::from(cv) == *self }
+}
+
 /// Some data we want to avoid recomputing all the time while trying to share
 /// style.
 #[derive(Debug, Default)]
 pub struct ValidationData {
     /// The class list of this element.
     ///
     /// TODO(emilio): See if it's worth to sort them, or doing something else in
     /// a similar fashion as what Boris is doing for the ID attribute.
     class_list: Option<SmallVec<[Atom; 5]>>,
 
     /// The list of presentational attributes of the element.
     pres_hints: Option<SmallVec<[ApplicableDeclarationBlock; 5]>>,
 
+    /// The pointer identity of the parent ComputedValues.
+    parent_style_identity: Option<OpaqueComputedValues>,
+
     /// The cached result of matching this entry against the revalidation
     /// selectors.
     revalidation_match_results: Option<SmallBitVec>,
 }
 
 impl ValidationData {
     /// Move the cached data to a new instance, and return it.
     pub fn take(&mut self) -> Self {
@@ -162,16 +177,28 @@ impl ValidationData {
             if !class_list.spilled() {
                 class_list.sort_by(|a, b| a.get_hash().cmp(&b.get_hash()));
             }
             self.class_list = Some(class_list);
         }
         &*self.class_list.as_ref().unwrap()
     }
 
+    /// Get or compute the parent style identity.
+    pub fn parent_style_identity<E>(&mut self, el: E) -> OpaqueComputedValues
+        where E: TElement,
+    {
+        if self.parent_style_identity.is_none() {
+            let parent = el.inheritance_parent().unwrap();
+            self.parent_style_identity =
+                Some(OpaqueComputedValues::from(parent.borrow_data().unwrap().styles.primary()));
+        }
+        self.parent_style_identity.as_ref().unwrap().clone()
+    }
+
     /// Computes the revalidation results if needed, and returns it.
     /// Inline so we know at compile time what bloom_known_valid is.
     #[inline]
     fn revalidation_match_results<E, F>(
         &mut self,
         element: E,
         stylist: &Stylist,
         bloom: &StyleBloom<E>,
@@ -245,16 +272,21 @@ impl<E: TElement> StyleSharingCandidate<
         self.validation_data.class_list(self.element)
     }
 
     /// Get the pres hints of this candidate.
     fn pres_hints(&mut self) -> &[ApplicableDeclarationBlock] {
         self.validation_data.pres_hints(self.element)
     }
 
+    /// Get the parent style identity.
+    fn parent_style_identity(&mut self) -> OpaqueComputedValues {
+        self.validation_data.parent_style_identity(self.element)
+    }
+
     /// Compute the bit vector of revalidation selector match results
     /// for this candidate.
     fn revalidation_match_results(
         &mut self,
         stylist: &Stylist,
         bloom: &StyleBloom<E>,
     ) -> &SmallBitVec {
         self.validation_data.revalidation_match_results(
@@ -299,16 +331,21 @@ impl<E: TElement> StyleSharingTarget<E> 
         self.validation_data.class_list(self.element)
     }
 
     /// Get the pres hints of this candidate.
     fn pres_hints(&mut self) -> &[ApplicableDeclarationBlock] {
         self.validation_data.pres_hints(self.element)
     }
 
+    /// Get the parent style identity.
+    fn parent_style_identity(&mut self) -> OpaqueComputedValues {
+        self.validation_data.parent_style_identity(self.element)
+    }
+
     fn revalidation_match_results(
         &mut self,
         stylist: &Stylist,
         bloom: &StyleBloom<E>,
         selector_flags_map: &mut SelectorFlagsMap<E>
     ) -> &SmallBitVec {
         // It's important to set the selector flags. Otherwise, if we succeed in
         // sharing the style, we may not set the slow selector flags for the
@@ -337,17 +374,17 @@ impl<E: TElement> StyleSharingTarget<E> 
             /* bloom_known_valid = */ true,
             &mut set_selector_flags)
     }
 
     /// Attempts to share a style with another node.
     pub fn share_style_if_possible(
         &mut self,
         context: &mut StyleContext<E>,
-    ) -> Option<ElementStyles> {
+    ) -> Option<E> {
         let cache = &mut context.thread_local.sharing_cache;
         let shared_context = &context.shared;
         let selector_flags_map = &mut context.thread_local.selector_flags;
         let bloom_filter = &context.thread_local.bloom_filter;
 
         if cache.dom_depth != bloom_filter.matching_depth() {
             debug!("Can't share style, because DOM depth changed from {:?} to {:?}, element: {:?}",
                    cache.dom_depth, bloom_filter.matching_depth(), self.element);
@@ -388,24 +425,29 @@ impl<Candidate> SharingCacheBase<Candida
     }
 
     fn is_empty(&self) -> bool {
         self.entries.num_entries() == 0
     }
 }
 
 impl<E: TElement> SharingCache<E> {
-    fn insert(&mut self, el: E, validation_data_holder: &mut StyleSharingTarget<E>) {
-        self.entries.insert(StyleSharingCandidate {
-            element: el,
-            validation_data: validation_data_holder.take_validation_data(),
-        });
+    fn insert(
+        &mut self,
+        element: E,
+        validation_data_holder: Option<&mut StyleSharingTarget<E>>,
+    ) {
+        let validation_data = match validation_data_holder {
+            Some(v) => v.take_validation_data(),
+            None => ValidationData::default(),
+        };
+        self.entries.insert(StyleSharingCandidate { element, validation_data });
     }
 
-    fn lookup<F>(&mut self, mut is_match: F) -> Option<ElementStyles>
+    fn lookup<F>(&mut self, mut is_match: F) -> Option<E>
     where
         F: FnMut(&mut StyleSharingCandidate<E>) -> bool
     {
         let mut index = None;
         for (i, candidate) in self.entries.iter_mut().enumerate() {
             if is_match(candidate) {
                 index = Some(i);
                 break;
@@ -413,17 +455,17 @@ impl<E: TElement> SharingCache<E> {
         };
 
         match index {
             None => None,
             Some(i) => {
                 self.entries.touch(i);
                 let front = self.entries.front_mut().unwrap();
                 debug_assert!(is_match(front));
-                Some(front.element.borrow_data().unwrap().styles.clone())
+                Some(front.element)
             }
         }
     }
 }
 
 /// Style sharing caches are are large allocations, so we store them in thread-local
 /// storage such that they can be reused across style traversals. Ideally, we'd just
 /// stack-allocate these buffers with uninitialized memory, but right now rustc can't
@@ -502,17 +544,17 @@ impl<E: TElement> StyleSharingCache<E> {
     ///
     /// Fails if we know it should never be in the cache.
     ///
     /// NB: We pass a source for the validation data, rather than the data itself,
     /// to avoid memmoving at each function call. See rust issue #42763.
     pub fn insert_if_possible(&mut self,
                               element: &E,
                               style: &ComputedValues,
-                              validation_data_holder: &mut StyleSharingTarget<E>,
+                              validation_data_holder: Option<&mut StyleSharingTarget<E>>,
                               dom_depth: usize) {
         let parent = match element.traversal_parent() {
             Some(element) => element,
             None => {
                 debug!("Failing to insert to the cache: no parent element");
                 return;
             }
         };
@@ -570,24 +612,24 @@ impl<E: TElement> StyleSharingCache<E> {
 
     /// Attempts to share a style with another node.
     fn share_style_if_possible(
         &mut self,
         shared_context: &SharedStyleContext,
         selector_flags_map: &mut SelectorFlagsMap<E>,
         bloom_filter: &StyleBloom<E>,
         target: &mut StyleSharingTarget<E>,
-    ) -> Option<ElementStyles> {
+    ) -> Option<E> {
         if shared_context.options.disable_style_sharing_cache {
             debug!("{:?} Cannot share style: style sharing cache disabled",
                    target.element);
             return None;
         }
 
-        if target.traversal_parent().is_none() {
+        if target.inheritance_parent().is_none() {
             debug!("{:?} Cannot share style: element has no parent",
                    target.element);
             return None;
         }
 
         if target.is_native_anonymous() {
             debug!("{:?} Cannot share style: NAC", target.element);
             return None;
@@ -610,20 +652,17 @@ impl<E: TElement> StyleSharingCache<E> {
         shared: &SharedStyleContext,
         bloom: &StyleBloom<E>,
         selector_flags_map: &mut SelectorFlagsMap<E>
     ) -> bool {
         // Check that we have the same parent, or at least that the parents
         // share styles and permit sharing across their children. The latter
         // check allows us to share style between cousins if the parents
         // shared style.
-        let parent = target.traversal_parent();
-        let candidate_parent = candidate.element.traversal_parent();
-        if parent != candidate_parent &&
-           !checks::can_share_style_across_parents(parent, candidate_parent) {
+        if !checks::parents_allow_sharing(target, candidate) {
             trace!("Miss: Parent");
             return false;
         }
 
         if target.is_native_anonymous() {
             debug_assert!(!candidate.element.is_native_anonymous(),
                           "Why inserting NAC into the cache?");
             trace!("Miss: Native Anonymous Content");
@@ -694,9 +733,49 @@ impl<E: TElement> StyleSharingCache<E> {
         debug_assert!(target.has_current_styles_for_traversal(
             &candidate.element.borrow_data().unwrap(),
             shared.traversal_flags)
         );
         debug!("Sharing allowed between {:?} and {:?}", target.element, candidate.element);
 
         true
     }
+
+    /// Attempts to find an element in the cache with the given primary rule node and parent.
+    pub fn lookup_by_rules(
+        &mut self,
+        inherited: &ComputedValues,
+        rules: &StrongRuleNode,
+        visited_rules: Option<&StrongRuleNode>,
+        target: E,
+    ) -> Option<E> {
+        self.cache_mut().lookup(|candidate| {
+            if !candidate.parent_style_identity().eq(inherited) {
+                return false;
+            }
+            let data = candidate.element.borrow_data().unwrap();
+            let style = data.styles.primary();
+            if style.rules.as_ref() != Some(&rules) {
+                return false;
+            }
+            if style.visited_rules() != visited_rules {
+                return false;
+            }
+
+            // Rule nodes and styles are computed independent of the element's
+            // actual visitedness, but at the end of the cascade (in
+            // `adjust_for_visited`) we do store the visitedness as a flag in
+            // style.  (This is a subtle change from initial visited work that
+            // landed when computed values were fused, see
+            // https://bugzilla.mozilla.org/show_bug.cgi?id=1381635.)
+            // So at the moment, we need to additionally compare visitedness,
+            // since that is not accounted for by rule nodes alone.
+            // FIXME(jryans): This seems like it breaks the constant time
+            // requirements of visited, assuming we get a cache hit on only one
+            // of unvisited vs. visited.
+            if target.is_visited_link() != candidate.element.is_visited_link() {
+                return false;
+            }
+
+            true
+        })
+    }
 }
--- a/servo/components/style/style_resolver.rs
+++ b/servo/components/style/style_resolver.rs
@@ -44,20 +44,62 @@ where
     _marker: ::std::marker::PhantomData<&'le E>,
 }
 
 struct MatchingResults {
     rule_node: StrongRuleNode,
     relevant_link_found: bool,
 }
 
+/// A style returned from the resolver machinery.
+pub struct ResolvedStyle {
+    /// The style itself.
+    pub style: Arc<ComputedValues>,
+    /// Whether the style was reused from another element via the rule node.
+    pub reused_via_rule_node: bool,
+}
+
 /// The primary style of an element or an element-backed pseudo-element.
-pub struct PrimaryStyle {
-    /// The style per se.
-    pub style: Arc<ComputedValues>,
+pub struct PrimaryStyle(pub ResolvedStyle);
+
+/// A set of style returned from the resolver machinery.
+pub struct ResolvedElementStyles {
+    /// Primary style.
+    pub primary: PrimaryStyle,
+    /// Pseudo styles.
+    pub pseudos: EagerPseudoStyles,
+}
+
+impl ResolvedStyle {
+    /// Creates a new ResolvedStyle.
+    pub fn new(style: Arc<ComputedValues>, reused_via_rule_node: bool) -> Self {
+        ResolvedStyle { style, reused_via_rule_node }
+    }
+}
+
+impl PrimaryStyle {
+    /// Convenience accessor for the style.
+    pub fn style(&self) -> &ComputedValues {
+        &*self.0.style
+    }
+}
+
+impl From<ResolvedStyle> for Arc<ComputedValues> {
+    fn from(r: ResolvedStyle) -> Arc<ComputedValues> {
+        r.style
+    }
+}
+
+impl From<ResolvedElementStyles> for ElementStyles {
+    fn from(r: ResolvedElementStyles) -> ElementStyles {
+        ElementStyles {
+            primary: Some(r.primary.0.into()),
+            pseudos: r.pseudos,
+        }
+    }
 }
 
 fn with_default_parent_styles<E, F, R>(element: E, f: F) -> R
 where
     E: TElement,
     F: FnOnce(Option<&ComputedValues>, Option<&ComputedValues>) -> R,
 {
     let parent_el = element.inheritance_parent();
@@ -135,62 +177,46 @@ where
         let visited_rules = if relevant_link_found {
             let visited_matching_results =
                 self.match_primary(VisitedHandlingMode::RelevantLinkVisited);
             Some(visited_matching_results.rule_node)
         } else {
             None
         };
 
-        let mut visited_style = None;
-        let should_compute_visited_style =
-            relevant_link_found ||
-            parent_style.and_then(|s| s.get_visited_style()).is_some();
-
-        let pseudo = self.element.implemented_pseudo_element();
-        if should_compute_visited_style {
-            visited_style = Some(self.cascade_style(
-                visited_rules.as_ref().or(Some(&primary_results.rule_node)),
-                /* style_if_visited = */ None,
+        PrimaryStyle(
+            self.cascade_style_and_visited(
+                CascadeInputs {
+                    rules: Some(primary_results.rule_node),
+                    visited_rules,
+                },
                 parent_style,
                 layout_parent_style,
-                CascadeVisitedMode::Visited,
-                /* pseudo = */ pseudo.as_ref(),
-            ));
-        }
-        let style = self.cascade_style(
-            Some(&primary_results.rule_node),
-            visited_style,
-            parent_style,
-            layout_parent_style,
-            CascadeVisitedMode::Unvisited,
-            /* pseudo = */ pseudo.as_ref(),
-        );
-
-        PrimaryStyle { style, }
+                /* pseudo = */ None,
+            )
+        )
     }
 
-
     /// Resolve the style of a given element, and all its eager pseudo-elements.
     pub fn resolve_style(
         &mut self,
         parent_style: Option<&ComputedValues>,
         layout_parent_style: Option<&ComputedValues>,
-    ) -> ElementStyles {
+    ) -> ResolvedElementStyles {
         let primary_style =
             self.resolve_primary_style(parent_style, layout_parent_style);
 
         let mut pseudo_styles = EagerPseudoStyles::default();
 
         if self.element.implemented_pseudo_element().is_none() {
             let layout_parent_style_for_pseudo =
-                if primary_style.style.is_display_contents() {
+                if primary_style.style().is_display_contents() {
                     layout_parent_style
                 } else {
-                    Some(&*primary_style.style)
+                    Some(primary_style.style())
                 };
             SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
                 let pseudo_style = self.resolve_pseudo_style(
                     &pseudo,
                     &primary_style,
                     layout_parent_style_for_pseudo
                 );
 
@@ -199,162 +225,186 @@ where
                        eager_pseudo_is_definitely_not_generated(&pseudo, &style) {
                         return;
                     }
                     pseudo_styles.set(&pseudo, style);
                 }
             })
         }
 
-        ElementStyles {
-            // FIXME(emilio): Remove the Option<>.
-            primary: Some(primary_style.style),
+        ResolvedElementStyles {
+            primary: primary_style,
             pseudos: pseudo_styles,
         }
     }
 
     /// Resolve an element's styles with the default inheritance parent/layout
     /// parents.
-    pub fn resolve_style_with_default_parents(&mut self) -> ElementStyles {
+    pub fn resolve_style_with_default_parents(&mut self) -> ResolvedElementStyles {
         with_default_parent_styles(self.element, |parent_style, layout_parent_style| {
             self.resolve_style(parent_style, layout_parent_style)
         })
     }
 
     /// Cascade a set of rules, using the default parent for inheritance.
     pub fn cascade_style_and_visited_with_default_parents(
         &mut self,
         inputs: CascadeInputs,
-    ) -> Arc<ComputedValues> {
+    ) -> ResolvedStyle {
         with_default_parent_styles(self.element, |parent_style, layout_parent_style| {
             self.cascade_style_and_visited(
                 inputs,
                 parent_style,
                 layout_parent_style,
                 /* pseudo = */ None
             )
         })
     }
 
     fn cascade_style_and_visited(
         &mut self,
         inputs: CascadeInputs,
         parent_style: Option<&ComputedValues>,
         layout_parent_style: Option<&ComputedValues>,
         pseudo: Option<&PseudoElement>,
-    ) -> Arc<ComputedValues> {
+    ) -> ResolvedStyle {
+        // Before doing the cascade, check the sharing cache and see if we can reuse
+        // the style via rule node identity.
+        let may_reuse = pseudo.is_none() && !self.element.is_native_anonymous() &&
+                        parent_style.is_some() && inputs.rules.is_some();
+        if may_reuse {
+            let cached = self.context.thread_local.sharing_cache.lookup_by_rules(
+                parent_style.unwrap(),
+                inputs.rules.as_ref().unwrap(),
+                inputs.visited_rules.as_ref(),
+                self.element,
+            );
+            if let Some(el) = cached {
+                self.context.thread_local.statistics.styles_reused += 1;
+                let mut style = el.borrow_data().unwrap().share_primary_style().0;
+                style.reused_via_rule_node = true;
+                return style;
+            }
+        }
+
+        // No style to reuse. Cascade the style, starting with visited style
+        // if necessary.
         let mut style_if_visited = None;
         if parent_style.map_or(false, |s| s.get_visited_style().is_some()) ||
             inputs.visited_rules.is_some() {
             style_if_visited = Some(self.cascade_style(
                 inputs.visited_rules.as_ref().or(inputs.rules.as_ref()),
                 /* style_if_visited = */ None,
                 parent_style,
                 layout_parent_style,
                 CascadeVisitedMode::Visited,
                 pseudo,
             ));
         }
-        self.cascade_style(
-            inputs.rules.as_ref(),
-            style_if_visited,
-            parent_style,
-            layout_parent_style,
-            CascadeVisitedMode::Unvisited,
-            pseudo,
-        )
+
+        ResolvedStyle {
+            style: self.cascade_style(
+                inputs.rules.as_ref(),
+                style_if_visited,
+                parent_style,
+                layout_parent_style,
+                CascadeVisitedMode::Unvisited,
+                pseudo,
+            ),
+            reused_via_rule_node: false,
+        }
     }
 
     /// Cascade the element and pseudo-element styles with the default parents.
     pub fn cascade_styles_with_default_parents(
         &mut self,
         inputs: ElementCascadeInputs,
-    ) -> ElementStyles {
+    ) -> ResolvedElementStyles {
         with_default_parent_styles(self.element, move |parent_style, layout_parent_style| {
-            let primary_style = PrimaryStyle {
-                style: self.cascade_style_and_visited(
+            let primary_style = PrimaryStyle(
+                self.cascade_style_and_visited(
                    inputs.primary,
                    parent_style,
                    layout_parent_style,
                    /* pseudo = */ None,
-                ),
-            };
+                )
+            );
 
             let mut pseudo_styles = EagerPseudoStyles::default();
             if let Some(mut pseudo_array) = inputs.pseudos.into_array() {
                 let layout_parent_style_for_pseudo =
-                    if primary_style.style.is_display_contents() {
+                    if primary_style.style().is_display_contents() {
                         layout_parent_style
                     } else {
-                        Some(&*primary_style.style)
+                        Some(primary_style.style())
                     };
 
                 for (i, inputs) in pseudo_array.iter_mut().enumerate() {
                     if let Some(inputs) = inputs.take() {
                         let pseudo = PseudoElement::from_eager_index(i);
 
                         let style =
                             self.cascade_style_and_visited(
                                 inputs,
-                                Some(&*primary_style.style),
+                                Some(&*primary_style.style()),
                                 layout_parent_style_for_pseudo,
                                 Some(&pseudo),
                             );
 
                         if !matches!(self.pseudo_resolution, PseudoElementResolution::Force) &&
-                           eager_pseudo_is_definitely_not_generated(&pseudo, &style) {
+                           eager_pseudo_is_definitely_not_generated(&pseudo, &style.style) {
                             continue;
                         }
 
-                        pseudo_styles.set(&pseudo, style);
+                        pseudo_styles.set(&pseudo, style.style);
                     }
                 }
             }
 
-            ElementStyles {
-                primary: Some(primary_style.style),
+            ResolvedElementStyles {
+                primary: primary_style,
                 pseudos: pseudo_styles,
             }
         })
     }
 
     fn resolve_pseudo_style(
         &mut self,
         pseudo: &PseudoElement,
         originating_element_style: &PrimaryStyle,
         layout_parent_style: Option<&ComputedValues>,
     ) -> Option<Arc<ComputedValues>> {
         let rules = self.match_pseudo(
-            &originating_element_style.style,
+            originating_element_style.style(),
             pseudo,
             VisitedHandlingMode::AllLinksUnvisited
         );
         let rules = match rules {
             Some(rules) => rules,
             None => return None,
         };
 
         let mut visited_rules = None;
-        if originating_element_style.style.get_visited_style().is_some() {
+        if originating_element_style.style().get_visited_style().is_some() {
             visited_rules = self.match_pseudo(
-                &originating_element_style.style,
+                originating_element_style.style(),
                 pseudo,
                 VisitedHandlingMode::RelevantLinkVisited,
             );
         }
 
         Some(self.cascade_style_and_visited(
             CascadeInputs {
                 rules: Some(rules),
                 visited_rules
             },
-            Some(&originating_element_style.style),
+            Some(originating_element_style.style()),
             layout_parent_style,
             Some(pseudo),
-        ))
+        ).style)
     }
 
     fn match_primary(
         &mut self,
         visited_handling: VisitedHandlingMode,
     ) -> MatchingResults {
         debug!("Match primary for {:?}, visited: {:?}",
                self.element, visited_handling);
@@ -480,16 +530,22 @@ where
         &mut self,
         rules: Option<&StrongRuleNode>,
         style_if_visited: Option<Arc<ComputedValues>>,
         mut parent_style: Option<&ComputedValues>,
         layout_parent_style: Option<&ComputedValues>,
         cascade_visited: CascadeVisitedMode,
         pseudo: Option<&PseudoElement>,
     ) -> Arc<ComputedValues> {
+        debug_assert!(
+            self.element.implemented_pseudo_element().is_none() || pseudo.is_none(),
+            "Pseudo-elements can't have other pseudos!"
+        );
+        debug_assert!(pseudo.map_or(true, |p| p.is_eager()));
+
         let mut cascade_flags = CascadeFlags::empty();
 
         if self.element.skip_root_and_item_based_display_fixup() ||
            pseudo.map_or(false, |p| p.skip_item_based_display_fixup()) {
             cascade_flags.insert(SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP);
         }
 
         if pseudo.is_none() && self.element.is_link() {
--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -414,32 +414,32 @@ where
         // (but it does matter below!).
         let primary_style =
             StyleResolverForElement::new(*ancestor, context, rule_inclusion, PseudoElementResolution::IfApplicable)
                 .resolve_primary_style(
                     style.as_ref().map(|s| &**s),
                     layout_parent_style.as_ref().map(|s| &**s)
                 );
 
-        let is_display_contents = primary_style.style.is_display_contents();
+        let is_display_contents = primary_style.style().is_display_contents();
 
-        style = Some(primary_style.style);
+        style = Some(primary_style.0.into());
         if !is_display_contents {
             layout_parent_style = style.clone();
         }
 
         context.thread_local.bloom_filter.push(*ancestor);
     }
 
     context.thread_local.bloom_filter.assert_complete(element);
     StyleResolverForElement::new(element, context, rule_inclusion, PseudoElementResolution::Force)
         .resolve_style(
             style.as_ref().map(|s| &**s),
             layout_parent_style.as_ref().map(|s| &**s)
-        )
+        ).into()
 }
 
 /// Calculates the style for a single node.
 #[inline]
 #[allow(unsafe_code)]
 pub fn recalc_style_at<E, D, F>(
     traversal: &D,
     traversal_data: &PerLevelTraversalData,
@@ -641,28 +641,32 @@ where
                           "MatchAndCascade shouldn't be processed during \
                            animation-only traversal");
             // Ensure the bloom filter is up to date.
             context.thread_local.bloom_filter
                    .insert_parents_recovering(element,
                                               traversal_data.current_dom_depth);
 
             context.thread_local.bloom_filter.assert_complete(element);
+            debug_assert_eq!(
+                context.thread_local.bloom_filter.matching_depth(),
+                traversal_data.current_dom_depth
+            );
 
             // This is only relevant for animations as of right now.
             important_rules_changed = true;
 
             let mut target = StyleSharingTarget::new(element);
 
             // Now that our bloom filter is set up, try the style sharing
             // cache.
             match target.share_style_if_possible(context) {
-                Some(styles) => {
+                Some(shareable_element) => {
                     context.thread_local.statistics.styles_shared += 1;
-                    styles
+                    shareable_element.borrow_data().unwrap().share_styles()
                 }
                 None => {
                     context.thread_local.statistics.elements_matched += 1;
                     // Perform the matching and cascading.
                     let new_styles = {
                         let mut resolver =
                             StyleResolverForElement::new(
                                 element,
@@ -673,19 +677,19 @@ where
 
                         resolver.resolve_style_with_default_parents()
                     };
 
                     context.thread_local
                         .sharing_cache
                         .insert_if_possible(
                             &element,
-                            new_styles.primary(),
-                            &mut target,
-                            context.thread_local.bloom_filter.matching_depth(),
+                            new_styles.primary.style(),
+                            Some(&mut target),
+                            traversal_data.current_dom_depth,
                         );
 
                     new_styles
                 }
             }
         }
         CascadeWithReplacements(flags) => {
             // Skipping full matching, load cascade inputs from previous values.
@@ -704,25 +708,35 @@ where
 
             resolver.cascade_styles_with_default_parents(cascade_inputs)
         }
         CascadeOnly => {
             // Skipping full matching, load cascade inputs from previous values.
             let cascade_inputs =
                 ElementCascadeInputs::new_from_element_data(data);
 
-            let mut resolver =
-                StyleResolverForElement::new(
-                    element,
-                    context,
-                    RuleInclusion::All,
-                    PseudoElementResolution::IfApplicable
-                );
+            let new_styles = {
+                let mut resolver =
+                    StyleResolverForElement::new(
+                        element,
+                        context,
+                        RuleInclusion::All,
+                        PseudoElementResolution::IfApplicable
+                    );
 
-            resolver.cascade_styles_with_default_parents(cascade_inputs)
+                resolver.cascade_styles_with_default_parents(cascade_inputs)
+            };
+            context.thread_local.sharing_cache.insert_if_possible(
+                &element,
+                new_styles.primary.style(),
+                None,
+                traversal_data.current_dom_depth,
+            );
+
+            new_styles
         }
     };
 
     element.finish_restyle(
         context,
         data,
         new_styles,
         important_rules_changed
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -722,19 +722,21 @@ pub extern "C" fn Servo_StyleSet_GetBase
     // existing browsers don't appear to animate visited styles.
     let inputs =
         CascadeInputs {
             rules: Some(without_animations),
             visited_rules: None,
         };
 
     // Actually `PseudoElementResolution` doesn't matter.
-    StyleResolverForElement::new(element, &mut context, RuleInclusion::All, PseudoElementResolution::IfApplicable)
+    let style: Arc<ComputedValues> =
+        StyleResolverForElement::new(element, &mut context, RuleInclusion::All, PseudoElementResolution::IfApplicable)
         .cascade_style_and_visited_with_default_parents(inputs)
-        .into()
+        .into();
+    style.into()
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_ComputedValues_ExtractAnimationValue(computed_values: ServoStyleContextBorrowed,
                                                              property_id: nsCSSPropertyID)
                                                              -> RawServoAnimationValueStrong
 {
     let property = match AnimatableLonghand::from_nscsspropertyid(property_id) {