style: Share CascadeData instances across ShadowRoots

This should be both a memory and speed win for pages using a lot of
Shadow DOM.

In order to make the cache properly work we need to start keying media query
results on the actual StyleSheetContents, as that's what we share on Gecko, but
that should all be fine.

Differential Revision: https://phabricator.services.mozilla.com/D107266

11 files changed, 175 insertions, 178 deletions

diff --git a/components/style/author_styles.rs b/components/style/author_styles.rs
index 58d9bda423a..dfd33711ed2 100644
--- a/components/style/author_styles.rs
+++ b/components/style/author_styles.rs
@@ -5,16 +5,16 @@
 //! A set of author stylesheets and their computed representation, such as the
 //! ones used for ShadowRoot.
 
-use crate::context::QuirksMode;
 use crate::dom::TElement;
 #[cfg(feature = "gecko")]
 use crate::gecko_bindings::sugar::ownership::{HasBoxFFI, HasFFI, HasSimpleFFI};
 use crate::invalidation::media_queries::ToMediaListKey;
-use crate::media_queries::Device;
 use crate::shared_lock::SharedRwLockReadGuard;
+use crate::stylist::Stylist;
 use crate::stylesheet_set::AuthorStylesheetSet;
 use crate::stylesheets::StylesheetInDocument;
 use crate::stylist::CascadeData;
+use servo_arc::Arc;
 
 /// A set of author stylesheets and their computed representation, such as the
 /// ones used for ShadowRoot.
@@ -27,7 +27,14 @@ where
     /// and all that stuff.
     pub stylesheets: AuthorStylesheetSet<S>,
     /// The actual cascade data computed from the stylesheets.
-    pub data: CascadeData,
+    #[ignore_malloc_size_of = "Measured as part of the stylist"]
+    pub data: Arc<CascadeData>,
+}
+
+lazy_static! {
+    static ref EMPTY_CASCADE_DATA: Arc<CascadeData> = {
+        Arc::new_leaked(CascadeData::new())
+    };
 }
 
 impl<S> AuthorStyles<S>
@@ -39,7 +46,7 @@ where
     pub fn new() -> Self {
         Self {
             stylesheets: AuthorStylesheetSet::new(),
-            data: CascadeData::new(),
+            data: EMPTY_CASCADE_DATA.clone(),
         }
     }
 
@@ -50,8 +57,7 @@ where
     #[inline]
     pub fn flush<E>(
         &mut self,
-        device: &Device,
-        quirks_mode: QuirksMode,
+        stylist: &mut Stylist,
         guard: &SharedRwLockReadGuard,
     ) where
         E: TElement,
@@ -61,10 +67,10 @@ where
             .stylesheets
             .flush::<E>(/* host = */ None, /* snapshot_map = */ None);
 
-        // Ignore OOM.
-        let _ = self
-            .data
-            .rebuild(device, quirks_mode, flusher.sheets, guard);
+        let result = stylist.rebuild_author_data(&self.data, flusher.sheets, guard);
+        if let Ok(Some(new_data)) = result {
+            self.data = new_data;
+        }
     }
 }
 
diff --git a/components/style/gecko/data.rs b/components/style/gecko/data.rs
index 0ce43bca46d..0689aa6c0c4 100644
--- a/components/style/gecko/data.rs
+++ b/components/style/gecko/data.rs
@@ -4,7 +4,6 @@
 
 //! Data needed to style a Gecko document.
 
-use crate::context::QuirksMode;
 use crate::dom::TElement;
 use crate::gecko_bindings::bindings;
 use crate::gecko_bindings::structs::{self, RawServoStyleSet, ServoStyleSetSizes};
@@ -15,7 +14,7 @@ use crate::media_queries::{Device, MediaList};
 use crate::properties::ComputedValues;
 use crate::selector_parser::SnapshotMap;
 use crate::shared_lock::{Locked, SharedRwLockReadGuard, StylesheetGuards};
-use crate::stylesheets::{CssRule, Origin, StylesheetContents, StylesheetInDocument};
+use crate::stylesheets::{StylesheetContents, StylesheetInDocument};
 use crate::stylist::Stylist;
 use atomic_refcell::{AtomicRef, AtomicRefCell, AtomicRefMut};
 use malloc_size_of::MallocSizeOfOps;
@@ -69,16 +68,6 @@ impl GeckoStyleSheet {
     fn inner(&self) -> &StyleSheetInfo {
         unsafe { &*(self.raw().mInner as *const StyleSheetInfo) }
     }
-
-    /// Gets the StylesheetContents for this stylesheet.
-    pub fn contents(&self) -> &StylesheetContents {
-        debug_assert!(!self.inner().mContents.mRawPtr.is_null());
-        unsafe {
-            let contents =
-                (&**StylesheetContents::as_arc(&&*self.inner().mContents.mRawPtr)) as *const _;
-            &*contents
-        }
-    }
 }
 
 impl Drop for GeckoStyleSheet {
@@ -95,14 +84,6 @@ impl Clone for GeckoStyleSheet {
 }
 
 impl StylesheetInDocument for GeckoStyleSheet {
-    fn origin(&self, _guard: &SharedRwLockReadGuard) -> Origin {
-        self.contents().origin
-    }
-
-    fn quirks_mode(&self, _guard: &SharedRwLockReadGuard) -> QuirksMode {
-        self.contents().quirks_mode
-    }
-
     fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList> {
         use crate::gecko_bindings::structs::mozilla::dom::MediaList as DomMediaList;
         use std::mem;
@@ -120,13 +101,19 @@ impl StylesheetInDocument for GeckoStyleSheet {
 
     // All the stylesheets Servo knows about are enabled, because that state is
     // handled externally by Gecko.
+    #[inline]
     fn enabled(&self) -> bool {
         true
     }
 
     #[inline]
-    fn rules<'a, 'b: 'a>(&'a self, guard: &'b SharedRwLockReadGuard) -> &'a [CssRule] {
-        self.contents().rules(guard)
+    fn contents(&self) -> &StylesheetContents {
+        debug_assert!(!self.inner().mContents.mRawPtr.is_null());
+        unsafe {
+            let contents =
+                (&**StylesheetContents::as_arc(&&*self.inner().mContents.mRawPtr)) as *const _;
+            &*contents
+        }
     }
 }
 
diff --git a/components/style/invalidation/element/invalidation_map.rs b/components/style/invalidation/element/invalidation_map.rs
index 29e0962a897..a7c2b04df13 100644
--- a/components/style/invalidation/element/invalidation_map.rs
+++ b/components/style/invalidation/element/invalidation_map.rs
@@ -185,7 +185,7 @@ pub struct DocumentStateDependency {
 /// 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.
-#[derive(Debug, MallocSizeOf)]
+#[derive(Clone, Debug, MallocSizeOf)]
 pub struct InvalidationMap {
     /// A map from a given class name to all the selectors with that class
     /// selector.
diff --git a/components/style/invalidation/media_queries.rs b/components/style/invalidation/media_queries.rs
index 75149a02891..6928b29d3d9 100644
--- a/components/style/invalidation/media_queries.rs
+++ b/components/style/invalidation/media_queries.rs
@@ -8,7 +8,7 @@ use crate::context::QuirksMode;
 use crate::media_queries::Device;
 use crate::shared_lock::SharedRwLockReadGuard;
 use crate::stylesheets::{DocumentRule, ImportRule, MediaRule};
-use crate::stylesheets::{NestedRuleIterationCondition, Stylesheet, SupportsRule};
+use crate::stylesheets::{NestedRuleIterationCondition, StylesheetContents, SupportsRule};
 use fxhash::FxHashSet;
 
 /// A key for a given media query result.
@@ -43,13 +43,13 @@ pub trait ToMediaListKey: Sized {
     }
 }
 
-impl ToMediaListKey for Stylesheet {}
+impl ToMediaListKey for StylesheetContents {}
 impl ToMediaListKey for ImportRule {}
 impl ToMediaListKey for MediaRule {}
 
 /// A struct that holds the result of a media query evaluation pass for the
 /// media queries that evaluated successfully.
-#[derive(Debug, MallocSizeOf, PartialEq)]
+#[derive(Clone, Debug, MallocSizeOf, PartialEq)]
 pub struct EffectiveMediaQueryResults {
     /// The set of media lists that matched last time.
     set: FxHashSet<MediaListKey>,
diff --git a/components/style/selector_map.rs b/components/style/selector_map.rs
index 4ea8cc1a018..40806ed47af 100644
--- a/components/style/selector_map.rs
+++ b/components/style/selector_map.rs
@@ -94,7 +94,7 @@ pub trait SelectorMapEntry: Sized + Clone {
 /// * https://bugzilla.mozilla.org/show_bug.cgi?id=681755
 ///
 /// TODO: Tune the initial capacity of the HashMap
-#[derive(Debug, MallocSizeOf)]
+#[derive(Clone, Debug, MallocSizeOf)]
 pub struct SelectorMap<T: 'static> {
     /// Rules that have `:root` selectors.
     pub root: SmallVec<[T; 1]>,
@@ -615,7 +615,7 @@ fn find_bucket<'a>(
 }
 
 /// Wrapper for PrecomputedHashMap that does ASCII-case-insensitive lookup in quirks mode.
-#[derive(Debug, MallocSizeOf)]
+#[derive(Clone, Debug, MallocSizeOf)]
 pub struct MaybeCaseInsensitiveHashMap<K: PrecomputedHash + Hash + Eq, V: 'static>(
     PrecomputedHashMap<K, V>,
 );
diff --git a/components/style/selector_parser.rs b/components/style/selector_parser.rs
index e3841c15482..67d4d4f6981 100644
--- a/components/style/selector_parser.rs
+++ b/components/style/selector_parser.rs
@@ -108,7 +108,7 @@ pub enum PseudoElementCascadeType {
 }
 
 /// A per-pseudo map, from a given pseudo to a `T`.
-#[derive(MallocSizeOf)]
+#[derive(Clone, MallocSizeOf)]
 pub struct PerPseudoElementMap<T> {
     entries: [Option<T>; PSEUDO_COUNT],
 }
diff --git a/components/style/stylesheet_set.rs b/components/style/stylesheet_set.rs
index d392d1795ec..e2937e06e75 100644
--- a/components/style/stylesheet_set.rs
+++ b/components/style/stylesheet_set.rs
@@ -420,7 +420,7 @@ macro_rules! sheet_set_methods {
         ) {
             debug!(concat!($set_name, "::append_stylesheet"));
             self.collect_invalidations_for(device, &sheet, guard);
-            let collection = self.collection_for(&sheet, guard);
+            let collection = self.collection_for(&sheet);
             collection.append(sheet);
         }
 
@@ -435,7 +435,7 @@ macro_rules! sheet_set_methods {
             debug!(concat!($set_name, "::insert_stylesheet_before"));
             self.collect_invalidations_for(device, &sheet, guard);
 
-            let collection = self.collection_for(&sheet, guard);
+            let collection = self.collection_for(&sheet);
             collection.insert_before(sheet, &before_sheet);
         }
 
@@ -449,7 +449,7 @@ macro_rules! sheet_set_methods {
             debug!(concat!($set_name, "::remove_stylesheet"));
             self.collect_invalidations_for(device, &sheet, guard);
 
-            let collection = self.collection_for(&sheet, guard);
+            let collection = self.collection_for(&sheet);
             collection.remove(&sheet)
         }
 
@@ -499,7 +499,7 @@ macro_rules! sheet_set_methods {
                 RuleChangeKind::StyleRuleDeclarations => DataValidity::FullyInvalid,
             };
 
-            let collection = self.collection_for(&sheet, guard);
+            let collection = self.collection_for(&sheet);
             collection.set_data_validity_at_least(validity);
         }
     };
@@ -517,12 +517,8 @@ where
         }
     }
 
-    fn collection_for(
-        &mut self,
-        sheet: &S,
-        guard: &SharedRwLockReadGuard,
-    ) -> &mut SheetCollection<S> {
-        let origin = sheet.origin(guard);
+    fn collection_for(&mut self, sheet: &S) -> &mut SheetCollection<S> {
+        let origin = sheet.contents().origin;
         self.collections.borrow_mut_for_origin(&origin)
     }
 
@@ -670,11 +666,7 @@ where
         self.collection.len()
     }
 
-    fn collection_for(
-        &mut self,
-        _sheet: &S,
-        _guard: &SharedRwLockReadGuard,
-    ) -> &mut SheetCollection<S> {
+    fn collection_for(&mut self, _sheet: &S) -> &mut SheetCollection<S> {
         &mut self.collection
     }
 
diff --git a/components/style/stylesheets/import_rule.rs b/components/style/stylesheets/import_rule.rs
index 5efae0a3ee5..201513760b3 100644
--- a/components/style/stylesheets/import_rule.rs
+++ b/components/style/stylesheets/import_rule.rs
@@ -61,6 +61,19 @@ impl ImportSheet {
             ImportSheet::Pending(_) => None,
         }
     }
+
+    /// Returns the media list for this import rule.
+    pub fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList> {
+        self.as_sheet().and_then(|s| s.media(guard))
+    }
+
+    /// Returns the rule list for this import rule.
+    pub fn rules<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> &'a [CssRule] {
+        match self.as_sheet() {
+            Some(s) => s.rules(guard),
+            None => &[],
+        }
+    }
 }
 
 #[cfg(feature = "gecko")]
@@ -85,69 +98,21 @@ impl DeepCloneWithLock for ImportSheet {
     }
 }
 
-#[cfg(feature = "gecko")]
-impl StylesheetInDocument for ImportSheet {
-    fn origin(&self, _guard: &SharedRwLockReadGuard) -> Origin {
-        match *self {
-            ImportSheet::Sheet(ref s) => s.contents().origin,
-            ImportSheet::Pending(ref p) => p.origin,
-        }
-    }
-
-    fn quirks_mode(&self, _guard: &SharedRwLockReadGuard) -> QuirksMode {
-        match *self {
-            ImportSheet::Sheet(ref s) => s.contents().quirks_mode,
-            ImportSheet::Pending(ref p) => p.quirks_mode,
-        }
-    }
-
-    fn enabled(&self) -> bool {
-        match *self {
-            ImportSheet::Sheet(ref s) => s.enabled(),
-            ImportSheet::Pending(_) => true,
-        }
-    }
-
-    fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList> {
-        match *self {
-            ImportSheet::Sheet(ref s) => s.media(guard),
-            ImportSheet::Pending(_) => None,
-        }
-    }
-
-    fn rules<'a, 'b: 'a>(&'a self, guard: &'b SharedRwLockReadGuard) -> &'a [CssRule] {
-        match *self {
-            ImportSheet::Sheet(ref s) => s.contents().rules(guard),
-            ImportSheet::Pending(_) => &[],
-        }
-    }
-}
-
 /// A sheet that is held from an import rule.
 #[cfg(feature = "servo")]
 #[derive(Debug)]
 pub struct ImportSheet(pub ::servo_arc::Arc<crate::stylesheets::Stylesheet>);
 
 #[cfg(feature = "servo")]
-impl StylesheetInDocument for ImportSheet {
-    fn origin(&self, guard: &SharedRwLockReadGuard) -> Origin {
-        self.0.origin(guard)
-    }
-
-    fn quirks_mode(&self, guard: &SharedRwLockReadGuard) -> QuirksMode {
-        self.0.quirks_mode(guard)
-    }
-
-    fn enabled(&self) -> bool {
-        self.0.enabled()
-    }
-
-    fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList> {
+impl ImportSheet {
+    /// Returns the media list for this import rule.
+    pub fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList> {
         self.0.media(guard)
     }
 
-    fn rules<'a, 'b: 'a>(&'a self, guard: &'b SharedRwLockReadGuard) -> &'a [CssRule] {
-        self.0.rules(guard)
+    /// Returns the rules for this import rule.
+    pub fn rules<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> &'a [CssRule] {
+        self.0.rules()
     }
 }
 
diff --git a/components/style/stylesheets/rules_iterator.rs b/components/style/stylesheets/rules_iterator.rs
index cc52a9550be..a7010ff066e 100644
--- a/components/style/stylesheets/rules_iterator.rs
+++ b/components/style/stylesheets/rules_iterator.rs
@@ -7,7 +7,6 @@
 use crate::context::QuirksMode;
 use crate::media_queries::Device;
 use crate::shared_lock::SharedRwLockReadGuard;
-use crate::stylesheets::StylesheetInDocument;
 use crate::stylesheets::{CssRule, DocumentRule, ImportRule, MediaRule, SupportsRule};
 use smallvec::SmallVec;
 use std::slice;
@@ -227,10 +226,13 @@ impl NestedRuleIterationCondition for EffectiveRules {
     fn process_import(
         guard: &SharedRwLockReadGuard,
         device: &Device,
-        _quirks_mode: QuirksMode,
+        quirks_mode: QuirksMode,
         rule: &ImportRule,
     ) -> bool {
-        rule.stylesheet.is_effective_for_device(device, guard)
+        match rule.stylesheet.media(guard) {
+            Some(m) => m.evaluate(device, quirks_mode),
+            None => true,
+        }
     }
 
     fn process_media(
diff --git a/components/style/stylesheets/stylesheet.rs b/components/style/stylesheets/stylesheet.rs
index 41c80c3cc66..2f7706a6979 100644
--- a/components/style/stylesheets/stylesheet.rs
+++ b/components/style/stylesheets/stylesheet.rs
@@ -4,7 +4,6 @@
 
 use crate::context::QuirksMode;
 use crate::error_reporting::{ContextualParseError, ParseErrorReporter};
-use crate::invalidation::media_queries::{MediaListKey, ToMediaListKey};
 use crate::media_queries::{Device, MediaList};
 use crate::parser::ParserContext;
 use crate::shared_lock::{DeepCloneParams, DeepCloneWithLock, Locked};
@@ -102,10 +101,10 @@ impl StylesheetContents {
 
         Self {
             rules: CssRules::new(rules, &shared_lock),
-            origin: origin,
+            origin,
             url_data: RwLock::new(url_data),
-            namespaces: namespaces,
-            quirks_mode: quirks_mode,
+            namespaces,
+            quirks_mode,
             source_map_url: RwLock::new(source_map_url),
             source_url: RwLock::new(source_url),
         }
@@ -218,12 +217,6 @@ macro_rules! rule_filter {
 
 /// A trait to represent a given stylesheet in a document.
 pub trait StylesheetInDocument: ::std::fmt::Debug {
-    /// Get the stylesheet origin.
-    fn origin(&self, guard: &SharedRwLockReadGuard) -> Origin;
-
-    /// Get the stylesheet quirks mode.
-    fn quirks_mode(&self, guard: &SharedRwLockReadGuard) -> QuirksMode;
-
     /// Get whether this stylesheet is enabled.
     fn enabled(&self) -> bool;
 
@@ -231,7 +224,12 @@ pub trait StylesheetInDocument: ::std::fmt::Debug {
     fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList>;
 
     /// Returns a reference to the list of rules in this stylesheet.
-    fn rules<'a, 'b: 'a>(&'a self, guard: &'b SharedRwLockReadGuard) -> &'a [CssRule];
+    fn rules<'a, 'b: 'a>(&'a self, guard: &'b SharedRwLockReadGuard) -> &'a [CssRule] {
+        self.contents().rules(guard)
+    }
+
+    /// Returns a reference to the contents of the stylesheet.
+    fn contents(&self) -> &StylesheetContents;
 
     /// Return an iterator using the condition `C`.
     #[inline]
@@ -243,18 +241,19 @@ pub trait StylesheetInDocument: ::std::fmt::Debug {
     where
         C: NestedRuleIterationCondition,
     {
+        let contents = self.contents();
         RulesIterator::new(
             device,
-            self.quirks_mode(guard),
+            contents.quirks_mode,
             guard,
-            self.rules(guard).iter(),
+            contents.rules(guard).iter(),
         )
     }
 
     /// Returns whether the style-sheet applies for the current device.
     fn is_effective_for_device(&self, device: &Device, guard: &SharedRwLockReadGuard) -> bool {
         match self.media(guard) {
-            Some(medialist) => medialist.evaluate(device, self.quirks_mode(guard)),
+            Some(medialist) => medialist.evaluate(device, self.contents().quirks_mode),
             None => true,
         }
     }
@@ -285,14 +284,6 @@ pub trait StylesheetInDocument: ::std::fmt::Debug {
 }
 
 impl StylesheetInDocument for Stylesheet {
-    fn origin(&self, _guard: &SharedRwLockReadGuard) -> Origin {
-        self.contents.origin
-    }
-
-    fn quirks_mode(&self, _guard: &SharedRwLockReadGuard) -> QuirksMode {
-        self.contents.quirks_mode
-    }
-
     fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList> {
         Some(self.media.read_with(guard))
     }
@@ -302,8 +293,8 @@ impl StylesheetInDocument for Stylesheet {
     }
 
     #[inline]
-    fn rules<'a, 'b: 'a>(&'a self, guard: &'b SharedRwLockReadGuard) -> &'a [CssRule] {
-        self.contents.rules(guard)
+    fn contents(&self) -> &StylesheetContents {
+        &self.contents
     }
 }
 
@@ -321,21 +312,7 @@ impl PartialEq for DocumentStyleSheet {
     }
 }
 
-impl ToMediaListKey for DocumentStyleSheet {
-    fn to_media_list_key(&self) -> MediaListKey {
-        self.0.to_media_list_key()
-    }
-}
-
 impl StylesheetInDocument for DocumentStyleSheet {
-    fn origin(&self, guard: &SharedRwLockReadGuard) -> Origin {
-        self.0.origin(guard)
-    }
-
-    fn quirks_mode(&self, guard: &SharedRwLockReadGuard) -> QuirksMode {
-        self.0.quirks_mode(guard)
-    }
-
     fn media<'a>(&'a self, guard: &'a SharedRwLockReadGuard) -> Option<&'a MediaList> {
         self.0.media(guard)
     }
@@ -345,8 +322,8 @@ impl StylesheetInDocument for DocumentStyleSheet {
     }
 
     #[inline]
-    fn rules<'a, 'b: 'a>(&'a self, guard: &'b SharedRwLockReadGuard) -> &'a [CssRule] {
-        self.0.rules(guard)
+    fn contents(&self) -> &StylesheetContents {
+        self.0.contents()
     }
 }
 
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index e2392cf5742..15783b54db0 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -11,7 +11,7 @@ use crate::element_state::{DocumentState, ElementState};
 #[cfg(feature = "gecko")]
 use crate::gecko_bindings::structs::{ServoStyleSetSizes, StyleRuleInclusion};
 use crate::invalidation::element::invalidation_map::InvalidationMap;
-use crate::invalidation::media_queries::{EffectiveMediaQueryResults, ToMediaListKey};
+use crate::invalidation::media_queries::EffectiveMediaQueryResults;
 use crate::invalidation::stylesheets::RuleChangeKind;
 use crate::media_queries::Device;
 use crate::properties::{self, CascadeMode, ComputedValues};
@@ -73,7 +73,7 @@ trait CascadeDataCacheEntry : Sized {
         old_entry: &Self,
     ) -> Result<Arc<Self>, FailedAllocationError>
     where
-        S: StylesheetInDocument + ToMediaListKey + PartialEq + 'static;
+        S: StylesheetInDocument + PartialEq + 'static;
     /// Measures heap memory usage.
     #[cfg(feature = "gecko")]
     fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes);
@@ -108,7 +108,7 @@ where
         old_entry: &Entry,
     ) -> Result<Option<Arc<Entry>>, FailedAllocationError>
     where
-        S: StylesheetInDocument + ToMediaListKey + PartialEq + 'static,
+        S: StylesheetInDocument + PartialEq + 'static,
     {
         debug!("StyleSheetCache::lookup({})", self.len());
 
@@ -122,9 +122,23 @@ where
         }
 
         for entry in &self.entries {
-            if entry.cascade_data().effective_media_query_results == key {
-                return Ok(Some(entry.clone()));
+            if std::ptr::eq(&**entry, old_entry) {
+                // Avoid reusing our old entry (this can happen if we get
+                // invalidated due to CSSOM mutations and our old stylesheet
+                // contents were already unique, for example). This old entry
+                // will be pruned from the cache with take_unused() afterwards.
+                continue;
+            }
+            if entry.cascade_data().effective_media_query_results != key {
+                continue;
+            }
+            if log_enabled!(log::Level::Debug) {
+                debug!("cache hit for:");
+                for sheet in collection.sheets() {
+                    debug!(" > {:?}", sheet);
+                }
             }
+            return Ok(Some(entry.clone()));
         }
 
         debug!("> Picking the slow path");
@@ -205,7 +219,7 @@ impl CascadeDataCacheEntry for UserAgentCascadeData {
         _old: &Self,
     ) -> Result<Arc<Self>, FailedAllocationError>
     where
-        S: StylesheetInDocument + ToMediaListKey + PartialEq + 'static
+        S: StylesheetInDocument + PartialEq + 'static
     {
         // TODO: Maybe we should support incremental rebuilds, though they seem
         // uncommon and rebuild() doesn't deal with
@@ -319,11 +333,13 @@ impl DocumentCascadeData {
         guards: &StylesheetGuards,
     ) -> Result<(), FailedAllocationError>
     where
-        S: StylesheetInDocument + ToMediaListKey + PartialEq + 'static,
+        S: StylesheetInDocument + PartialEq + 'static,
     {
         // First do UA sheets.
         {
             let origin_flusher = flusher.flush_origin(Origin::UserAgent);
+            // Dirty check is just a minor optimization (no need to grab the
+            // lock if nothing has changed).
             if origin_flusher.dirty() {
                 let mut ua_cache = UA_CASCADE_DATA_CACHE.lock().unwrap();
                 let new_data = ua_cache.lookup(
@@ -436,6 +452,9 @@ pub struct Stylist {
     /// The list of stylesheets.
     stylesheets: StylistStylesheetSet,
 
+    /// A cache of CascadeDatas for AuthorStylesheetSets (i.e., shadow DOM).
+    author_data_cache: CascadeDataCache<CascadeData>,
+
     /// If true, the quirks-mode stylesheet is applied.
     #[cfg_attr(feature = "servo", ignore_malloc_size_of = "defined in selectors")]
     quirks_mode: QuirksMode,
@@ -487,6 +506,7 @@ impl Stylist {
             device,
             quirks_mode,
             stylesheets: StylistStylesheetSet::new(),
+            author_data_cache: CascadeDataCache::new(),
             cascade_data: Default::default(),
             author_styles_enabled: AuthorStylesEnabled::Yes,
             rule_tree: RuleTree::new(),
@@ -512,6 +532,31 @@ impl Stylist {
         self.cascade_data.iter_origins()
     }
 
+    /// Does what the name says, to prevent author_data_cache to grow without
+    /// bound.
+    pub fn remove_unique_author_data_cache_entries(&mut self) {
+        self.author_data_cache.take_unused();
+    }
+
+    /// Rebuilds (if needed) the CascadeData given a sheet collection.
+    pub fn rebuild_author_data<S>(
+        &mut self,
+        old_data: &CascadeData,
+        collection: SheetCollectionFlusher<S>,
+        guard: &SharedRwLockReadGuard,
+    ) -> Result<Option<Arc<CascadeData>>, FailedAllocationError>
+    where
+        S: StylesheetInDocument + PartialEq + 'static,
+    {
+        self.author_data_cache.lookup(
+            &self.device,
+            self.quirks_mode,
+            collection,
+            guard,
+            old_data,
+        )
+    }
+
     /// Iterate over the extra data in origin order.
     #[inline]
     pub fn iter_extra_data_origins(&self) -> ExtraStyleDataIterator {
@@ -1420,6 +1465,7 @@ impl Stylist {
     #[cfg(feature = "gecko")]
     pub fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
         self.cascade_data.add_size_of(ops, sizes);
+        self.author_data_cache.add_size_of(ops, sizes);
         sizes.mRuleTree += self.rule_tree.size_of(ops);
 
         // We may measure other fields in the future if DMD says it's worth it.
@@ -1433,7 +1479,7 @@ impl Stylist {
 
 /// This struct holds data which users of Stylist may want to extract
 /// from stylesheets which can be done at the same time as updating.
-#[derive(Debug, Default)]
+#[derive(Clone, Debug, Default)]
 #[cfg_attr(feature = "servo", derive(MallocSizeOf))]
 pub struct ExtraStyleData {
     /// A list of effective font-face rules and their origin.
@@ -1454,11 +1500,6 @@ pub struct ExtraStyleData {
 }
 
 #[cfg(feature = "gecko")]
-unsafe impl Sync for ExtraStyleData {}
-#[cfg(feature = "gecko")]
-unsafe impl Send for ExtraStyleData {}
-
-#[cfg(feature = "gecko")]
 impl ExtraStyleData {
     /// Add the given @font-face rule.
     fn add_font_face(&mut self, rule: &Arc<Locked<FontFaceRule>>) {
@@ -1698,7 +1739,7 @@ impl<'a> SelectorVisitor for StylistSelectorVisitor<'a> {
 }
 
 /// A set of rules for element and pseudo-elements.
-#[derive(Debug, Default, MallocSizeOf)]
+#[derive(Clone, Debug, Default, MallocSizeOf)]
 struct GenericElementAndPseudoRules<Map> {
     /// Rules from stylesheets at this `CascadeData`'s origin.
     element_map: Map,
@@ -1777,7 +1818,7 @@ impl PartElementAndPseudoRules {
 ///
 /// FIXME(emilio): Consider renaming and splitting in `CascadeData` and
 /// `InvalidationData`? That'd make `clear_cascade_data()` clearer.
-#[derive(Debug, MallocSizeOf)]
+#[derive(Debug, Clone, MallocSizeOf)]
 pub struct CascadeData {
     /// The data coming from normal style rules that apply to elements at this
     /// cascade level.
@@ -1887,7 +1928,7 @@ impl CascadeData {
         guard: &SharedRwLockReadGuard,
     ) -> Result<(), FailedAllocationError>
     where
-        S: StylesheetInDocument + ToMediaListKey + PartialEq + 'static,
+        S: StylesheetInDocument + PartialEq + 'static,
     {
         if !collection.dirty() {
             return Ok(());
@@ -1990,14 +2031,14 @@ impl CascadeData {
         guard: &SharedRwLockReadGuard,
         results: &mut EffectiveMediaQueryResults,
     ) where
-        S: StylesheetInDocument + ToMediaListKey + 'static,
+        S: StylesheetInDocument + 'static,
     {
         if !stylesheet.enabled() || !stylesheet.is_effective_for_device(device, guard) {
             return;
         }
 
         debug!(" + {:?}", stylesheet);
-        results.saw_effective(stylesheet);
+        results.saw_effective(stylesheet.contents());
 
         for rule in stylesheet.effective_rules(device, guard) {
             match *rule {
@@ -2027,16 +2068,17 @@ impl CascadeData {
         mut precomputed_pseudo_element_decls: Option<&mut PrecomputedPseudoElementDeclarations>,
     ) -> Result<(), FailedAllocationError>
     where
-        S: StylesheetInDocument + ToMediaListKey + 'static,
+        S: StylesheetInDocument + 'static,
     {
         if !stylesheet.enabled() || !stylesheet.is_effective_for_device(device, guard) {
             return Ok(());
         }
 
-        let origin = stylesheet.origin(guard);
+        let contents = stylesheet.contents();
+        let origin = contents.origin;
 
         if rebuild_kind.should_rebuild_invalidation() {
-            self.effective_media_query_results.saw_effective(stylesheet);
+            self.effective_media_query_results.saw_effective(contents);
         }
 
         for rule in stylesheet.effective_rules(device, guard) {
@@ -2211,13 +2253,13 @@ impl CascadeData {
         quirks_mode: QuirksMode,
     ) -> bool
     where
-        S: StylesheetInDocument + ToMediaListKey + 'static,
+        S: StylesheetInDocument + 'static,
     {
         use crate::invalidation::media_queries::PotentiallyEffectiveMediaRules;
 
         let effective_now = stylesheet.is_effective_for_device(device, guard);
 
-        let effective_then = self.effective_media_query_results.was_effective(stylesheet);
+        let effective_then = self.effective_media_query_results.was_effective(stylesheet.contents());
 
         if effective_now != effective_then {
             debug!(
@@ -2252,9 +2294,10 @@ impl CascadeData {
                 },
                 CssRule::Import(ref lock) => {
                     let import_rule = lock.read_with(guard);
-                    let effective_now = import_rule
-                        .stylesheet
-                        .is_effective_for_device(&device, guard);
+                    let effective_now = match import_rule.stylesheet.media(guard) {
+                        Some(m) => m.evaluate(device, quirks_mode),
+                        None => true,
+                    };
                     let effective_then = self
                         .effective_media_query_results
                         .was_effective(import_rule);
@@ -2326,8 +2369,33 @@ impl CascadeData {
         self.selectors_for_cache_revalidation.clear();
         self.effective_media_query_results.clear();
     }
+}
+
+impl CascadeDataCacheEntry for CascadeData {
+    fn cascade_data(&self) -> &CascadeData {
+        self
+    }
+
+    fn rebuild<S>(
+        device: &Device,
+        quirks_mode: QuirksMode,
+        collection: SheetCollectionFlusher<S>,
+        guard: &SharedRwLockReadGuard,
+        old: &Self,
+    ) -> Result<Arc<Self>, FailedAllocationError>
+    where
+        S: StylesheetInDocument + PartialEq + 'static
+    {
+        debug_assert!(collection.dirty(), "We surely need to do something?");
+        // If we're doing a full rebuild anyways, don't bother cloning the data.
+        let mut updatable_entry = match collection.data_validity() {
+            DataValidity::Valid | DataValidity::CascadeInvalid => old.clone(),
+            DataValidity::FullyInvalid => Self::new(),
+        };
+        updatable_entry.rebuild(device, quirks_mode, collection, guard)?;
+        Ok(Arc::new(updatable_entry))
+    }
 
-    /// Measures heap usage.
     #[cfg(feature = "gecko")]
     fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
         self.normal_rules.add_size_of(ops, sizes);