--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -26,17 +26,17 @@ use selectors::matching::{ElementSelecto
 use selectors::sink::Push;
 use servo_arc::{Arc, ArcBorrow};
 use shared_lock::Locked;
 use std::fmt;
 #[cfg(feature = "gecko")] use hash::FnvHashMap;
 use std::fmt::Debug;
 use std::hash::Hash;
 use std::ops::Deref;
-use stylist::{StyleRuleCascadeData, Stylist};
+use stylist::{CascadeData, Stylist};
 use traversal_flags::TraversalFlags;
 
 /// An opaque handle to a node, which, unlike UnsafeNode, cannot be transformed
 /// back into a non-opaque representation. The only safe operation that can be
 /// performed on this node is to compare it to another opaque handle or to another
 /// OpaqueNode.
 ///
 /// Layout and Graphics use this to safely represent nodes for comparison purposes.
@@ -776,36 +776,34 @@ pub trait TElement
 
     /// Executes the callback for each applicable style rule data which isn't
     /// the main document's data (which stores UA / author rules).
     ///
     /// Returns whether normal document author rules should apply.
     fn each_applicable_non_document_style_rule_data<'a, F>(&self, mut f: F) -> bool
     where
         Self: 'a,
-        F: FnMut(AtomicRef<'a, StyleRuleCascadeData>, QuirksMode),
+        F: FnMut(AtomicRef<'a, CascadeData>, QuirksMode),
     {
         let cut_off_inheritance = self.each_xbl_stylist(|stylist| {
             let quirks_mode = stylist.quirks_mode();
             f(
-                AtomicRef::map(stylist, |stylist| stylist.normal_author_cascade_data()),
+                AtomicRef::map(stylist, |stylist| stylist.author_cascade_data()),
                 quirks_mode,
             )
         });
 
         let mut current = self.assigned_slot();
         while let Some(slot) = current {
             slot.each_xbl_stylist(|stylist| {
                 let quirks_mode = stylist.quirks_mode();
-                if stylist.slotted_author_cascade_data().is_some() {
-                    f(
-                        AtomicRef::map(stylist, |stylist| stylist.slotted_author_cascade_data().unwrap()),
-                        quirks_mode,
-                    )
-                }
+                f(
+                    AtomicRef::map(stylist, |stylist| stylist.author_cascade_data()),
+                    quirks_mode,
+                )
             });
 
             current = slot.assigned_slot();
         }
 
         cut_off_inheritance
     }
 

--- a/servo/components/style/invalidation/element/document_state.rs
+++ b/servo/components/style/invalidation/element/document_state.rs
@@ -5,38 +5,38 @@
 //! An invalidation processor for style changes due to document state changes.
 
 use dom::TElement;
 use element_state::DocumentState;
 use invalidation::element::invalidator::{DescendantInvalidationLists, InvalidationVector};
 use invalidation::element::invalidator::{Invalidation, InvalidationProcessor};
 use invalidation::element::state_and_attributes;
 use selectors::matching::{MatchingContext, MatchingMode, QuirksMode, VisitedHandlingMode};
-use stylist::StyleRuleCascadeData;
+use stylist::CascadeData;
 
 /// A struct holding the members necessary to invalidate document state
 /// selectors.
 pub struct InvalidationMatchingData {
     /// The document state that has changed, which makes it always match.
     pub document_state: DocumentState,
 }
 
 /// An invalidation processor for style changes due to state and attribute
 /// changes.
 pub struct DocumentStateInvalidationProcessor<'a, E: TElement> {
-    rules: &'a StyleRuleCascadeData,
+    rules: &'a CascadeData,
     matching_context: MatchingContext<'a, E::Impl>,
     document_states_changed: DocumentState,
 }
 
 impl<'a, E: TElement> DocumentStateInvalidationProcessor<'a, E> {
     /// Creates a new DocumentStateInvalidationProcessor.
     #[inline]
     pub fn new(
-        rules: &'a StyleRuleCascadeData,
+        rules: &'a CascadeData,
         document_states_changed: DocumentState,
         quirks_mode: QuirksMode,
     ) -> Self {
         let mut matching_context = MatchingContext::new_for_visited(
             MatchingMode::Normal,
             None,
             None,
             VisitedHandlingMode::AllLinksVisitedAndUnvisited,

--- a/servo/components/style/invalidation/element/state_and_attributes.rs
+++ b/servo/components/style/invalidation/element/state_and_attributes.rs
@@ -19,17 +19,17 @@ use invalidation::element::restyle_hints
 use selector_map::SelectorMap;
 use selector_parser::Snapshot;
 use selectors::NthIndexCache;
 use selectors::attr::CaseSensitivity;
 use selectors::matching::{MatchingContext, MatchingMode, VisitedHandlingMode};
 use selectors::matching::matches_selector;
 use smallvec::SmallVec;
 use stylesheets::origin::{Origin, OriginSet};
-use stylist::StyleRuleCascadeData;
+use stylist::CascadeData;
 
 #[derive(Debug, PartialEq)]
 enum VisitedDependent {
     Yes,
     No,
 }
 
 /// The collector implementation.
@@ -52,28 +52,28 @@ where
     sibling_invalidations: &'a mut InvalidationVector<'selectors>,
     invalidates_self: bool,
 }
 
 /// 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>,
-    shadow_rule_datas: &'a [(AtomicRef<'b, StyleRuleCascadeData>, QuirksMode)],
+    shadow_rule_datas: &'a [(AtomicRef<'b, CascadeData>, QuirksMode)],
     cut_off_inheritance: bool,
     element: E,
     data: &'a mut ElementData,
     matching_context: MatchingContext<'a, E::Impl>,
 }
 
 impl<'a, 'b: 'a, E: TElement> StateAndAttrInvalidationProcessor<'a, 'b, E> {
     /// Creates a new StateAndAttrInvalidationProcessor.
     pub fn new(
         shared_context: &'a SharedStyleContext<'b>,
-        shadow_rule_datas: &'a [(AtomicRef<'b, StyleRuleCascadeData>, QuirksMode)],
+        shadow_rule_datas: &'a [(AtomicRef<'b, CascadeData>, QuirksMode)],
         cut_off_inheritance: bool,
         element: E,
         data: &'a mut ElementData,
         nth_index_cache: &'a mut NthIndexCache,
     ) -> Self {
         let matching_context = MatchingContext::new_for_visited(
             MatchingMode::Normal,
             None,
@@ -250,21 +250,21 @@ where
             };
 
             let document_origins = if self.cut_off_inheritance {
                 Origin::UserAgent.into()
             } else {
                 OriginSet::all()
             };
 
-            self.shared_context.stylist.each_normal_rule_cascade_data(|cascade_data, origin| {
+            for (cascade_data, origin) in self.shared_context.stylist.iter_origins() {
                 if document_origins.contains(origin.into()) {
                     collector.collect_dependencies_in_invalidation_map(cascade_data.invalidation_map());
                 }
-            });
+            }
 
             for &(ref data, quirks_mode) in self.shadow_rule_datas {
                 // FIXME(emilio): Replace with assert / remove when we figure
                 // out what to do with the quirks mode mismatches
                 // (that is, when bug 1406875 is properly fixed).
                 collector.quirks_mode = quirks_mode;
                 collector.collect_dependencies_in_invalidation_map(data.invalidation_map());
             }

--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -183,17 +183,18 @@ struct DocumentCascadeData {
         ignore_malloc_size_of = "Arc, owned by UserAgentCascadeDataCache"
     )]
     user_agent: Arc<UserAgentCascadeData>,
     user: CascadeData,
     author: CascadeData,
     per_origin: PerOrigin<()>,
 }
 
-struct DocumentCascadeDataIter<'a> {
+/// An iterator over the cascade data of a given document.
+pub struct DocumentCascadeDataIter<'a> {
     iter: PerOriginIter<'a, ()>,
     cascade_data: &'a DocumentCascadeData,
 }
 
 impl<'a> Iterator for DocumentCascadeDataIter<'a> {
     type Item = (&'a CascadeData, Origin);
 
     fn next(&mut self) -> Option<Self::Item> {
@@ -431,16 +432,28 @@ impl Stylist {
             quirks_mode,
             stylesheets: StylistStylesheetSet::new(),
             cascade_data: Default::default(),
             rule_tree: RuleTree::new(),
             num_rebuilds: 0,
         }
     }
 
+    /// Returns the cascade data for the author level.
+    #[inline]
+    pub fn author_cascade_data(&self) -> &CascadeData {
+        &self.cascade_data.author
+    }
+
+    /// Iterate through all the cascade datas from the document.
+    #[inline]
+    pub fn iter_origins(&self) -> DocumentCascadeDataIter {
+        self.cascade_data.iter_origins()
+    }
+
     /// Iterate over the extra data in origin order.
     #[inline]
     pub fn iter_extra_data_origins(&self) -> ExtraStyleDataIterator {
         ExtraStyleDataIterator(self.cascade_data.iter_origins())
     }
 
     /// Iterate over the extra data in reverse origin order.
     #[inline]
@@ -461,40 +474,32 @@ impl Stylist {
     /// Returns the number of times the stylist has been rebuilt.
     pub fn num_rebuilds(&self) -> usize {
         self.num_rebuilds
     }
 
     /// Returns the number of revalidation_selectors.
     pub fn num_revalidation_selectors(&self) -> usize {
         self.cascade_data.iter_origins()
-            .map(|(data, _)| {
-                data.normal_rule_data.selectors_for_cache_revalidation.len() +
-                data.slotted_rule_data.as_ref().map_or(0, |d| {
-                    d.selectors_for_cache_revalidation.len()
-                })
-            }).sum()
+            .map(|(data, _)| data.selectors_for_cache_revalidation.len())
+            .sum()
     }
 
     /// Returns the number of entries in invalidation maps.
     pub fn num_invalidations(&self) -> usize {
         self.cascade_data.iter_origins()
-            .map(|(data, _)| {
-                data.normal_rule_data.invalidation_map.len() +
-                data.slotted_rule_data.as_ref().map_or(0, |d| d.invalidation_map.len())
-            }).sum()
+            .map(|(data, _)| data.invalidation_map.len())
+            .sum()
     }
 
     /// Returns whether the given DocumentState bit is relied upon by a selector
     /// of some rule.
     pub fn has_document_state_dependency(&self, state: DocumentState) -> bool {
         self.cascade_data.iter_origins()
-            .any(|(d, _)| {
-                d.normal_rule_data.has_document_state_dependency(state)
-            })
+            .any(|(d, _)| d.document_state_dependencies.intersects(state))
     }
 
     /// Flush the list of stylesheets if they changed, ensuring the stylist is
     /// up-to-date.
     pub fn flush<E>(
         &mut self,
         guards: &StylesheetGuards,
         document_element: Option<E>,
@@ -600,49 +605,39 @@ impl Stylist {
         self.stylesheets.prepend_stylesheet(Some(&self.device), sheet, guard)
     }
 
     /// Remove a given stylesheet to the current set.
     pub fn remove_stylesheet(&mut self, sheet: StylistSheet, guard: &SharedRwLockReadGuard) {
         self.stylesheets.remove_stylesheet(Some(&self.device), sheet, guard)
     }
 
-    /// Executes `f` on each of the normal rule cascade datas in this styleset.
-    pub fn each_normal_rule_cascade_data<'a, F>(&'a self, mut f: F)
-    where
-        F: FnMut(&'a StyleRuleCascadeData, Origin),
-    {
-        for (data, origin) in self.cascade_data.iter_origins() {
-            f(&data.normal_rule_data, origin);
-        }
-    }
-
     /// Returns whether for any of the applicable style rule data a given
     /// condition is true.
     pub fn any_applicable_rule_data<E, F>(&self, element: E, mut f: F) -> bool
     where
         E: TElement,
-        F: FnMut(&StyleRuleCascadeData, QuirksMode) -> bool,
+        F: FnMut(&CascadeData, QuirksMode) -> bool,
     {
-        if f(&self.cascade_data.user_agent.cascade_data.normal_rule_data, self.quirks_mode()) {
+        if f(&self.cascade_data.user_agent.cascade_data, self.quirks_mode()) {
             return true;
         }
 
         let mut maybe = false;
 
         let cut_off = element.each_applicable_non_document_style_rule_data(|data, quirks_mode| {
             maybe = maybe || f(&*data, quirks_mode);
         });
 
         if maybe || cut_off {
             return maybe;
         }
 
-        f(&self.cascade_data.author.normal_rule_data, self.quirks_mode()) ||
-        f(&self.cascade_data.user.normal_rule_data, self.quirks_mode())
+        f(&self.cascade_data.author, self.quirks_mode()) ||
+        f(&self.cascade_data.user, self.quirks_mode())
     }
 
     /// Computes the style for a given "precomputed" pseudo-element, taking the
     /// universal rules and applying them.
     ///
     /// If `inherit_all` is true, then all properties are inherited from the
     /// parent; otherwise, non-inherited properties are reset to their initial
     /// values. The flow constructor uses this flag when constructing anonymous
@@ -1441,28 +1436,16 @@ impl Stylist {
         }
 
         let hash = id.get_hash();
         self.any_applicable_rule_data(element, |data, _| {
             data.mapped_ids.might_contain_hash(hash)
         })
     }
 
-    /// Returns the cascade data for the normal rules.
-    #[inline]
-    pub fn normal_author_cascade_data(&self) -> &StyleRuleCascadeData {
-        &self.cascade_data.author.normal_rule_data
-    }
-
-    /// Returns the cascade data for the slotted rules in this scope, if any.
-    #[inline]
-    pub fn slotted_author_cascade_data(&self) -> Option<&StyleRuleCascadeData> {
-        self.cascade_data.author.slotted_rule_data.as_ref().map(|d| &**d)
-    }
-
     /// Returns the registered `@keyframes` animation for the specified name.
     ///
     /// FIXME(emilio): This needs to account for the element rules.
     #[inline]
     pub fn get_animation(&self, name: &Atom) -> Option<&KeyframesAnimation> {
         self.cascade_data
             .iter_origins()
             .filter_map(|(d, _)| d.animations.get(name))
@@ -1493,17 +1476,17 @@ impl Stylist {
 
         // Note that, by the time we're revalidating, we're guaranteed that the
         // candidate and the entry have the same id, classes, and local name.
         // This means we're guaranteed to get the same rulehash buckets for all
         // the lookups, which means that the bitvecs are comparable. We verify
         // this in the caller by asserting that the bitvecs are same-length.
         let mut results = SmallBitVec::new();
         for (data, _) in self.cascade_data.iter_origins() {
-            data.normal_rule_data.selectors_for_cache_revalidation.lookup(
+            data.selectors_for_cache_revalidation.lookup(
                 element,
                 self.quirks_mode,
                 |selector_and_hashes| {
                     results.push(matches_selector(
                         &selector_and_hashes.selector,
                         selector_and_hashes.selector_offset,
                         Some(&selector_and_hashes.hashes),
                         &element,
@@ -1913,17 +1896,17 @@ impl ElementAndPseudoRules {
     }
 
     fn clear(&mut self) {
         self.element_map.clear();
         self.pseudos_map.clear();
     }
 
     #[inline]
-    fn borrow_for_pseudo(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
+    fn rules(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
         match pseudo {
             Some(pseudo) => self.pseudos_map.get(&pseudo.canonical()).map(|p| &**p),
             None => Some(&self.element_map),
         }
     }
 
     /// Measures heap usage.
     #[cfg(feature = "gecko")]
@@ -1933,22 +1916,36 @@ impl ElementAndPseudoRules {
         for elem in self.pseudos_map.iter() {
             if let Some(ref elem) = *elem {
                 sizes.mElementAndPseudosMaps += <Box<_> as MallocSizeOf>::size_of(elem, ops);
             }
         }
     }
 }
 
-/// Cascade data generated from style rules.
-#[derive(Debug)]
+/// Data resulting from performing the CSS cascade that is specific to a given
+/// origin.
+///
+/// FIXME(emilio): Consider renaming and splitting in `CascadeData` and
+/// `InvalidationData`? That'd make `clear_cascade_data()` clearer.
 #[cfg_attr(feature = "servo", derive(MallocSizeOf))]
-pub struct StyleRuleCascadeData {
-    /// The actual style rules.
-    rules: ElementAndPseudoRules,
+#[derive(Debug)]
+pub struct CascadeData {
+    /// The data coming from normal style rules that apply to elements at this
+    /// cascade level.
+    normal_rules: ElementAndPseudoRules,
+
+    /// The data coming from ::slotted() pseudo-element rules.
+    ///
+    /// We need to store them separately because an element needs to match
+    /// ::slotted() pseudo-element rules in different shadow roots.
+    ///
+    /// In particular, we need to go through all the style data in all the
+    /// containing style scopes starting from the closest assigned slot.
+    slotted_rules: Option<Box<ElementAndPseudoRules>>,
 
     /// The invalidation map for these rules.
     invalidation_map: InvalidationMap,
 
     /// The attribute local names that appear in attribute selectors.  Used
     /// to avoid taking element snapshots when an irrelevant attribute changes.
     /// (We don't bother storing the namespace, since namespaced attributes
     /// are rare.)
@@ -1980,152 +1977,16 @@ pub struct StyleRuleCascadeData {
     #[cfg_attr(feature = "servo", ignore_malloc_size_of = "just an array")]
     mapped_ids: NonCountingBloomFilter,
 
     /// Selectors that require explicit cache revalidation (i.e. which depend
     /// on state that is not otherwise visible to the cache, like attributes or
     /// tree-structural state like child index and pseudos).
     #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")]
     selectors_for_cache_revalidation: SelectorMap<RevalidationSelectorAndHashes>,
-}
-
-impl StyleRuleCascadeData {
-    #[inline(always)]
-    fn insert(
-        &mut self,
-        rule: Rule,
-        pseudo_element: Option<&PseudoElement>,
-        quirks_mode: QuirksMode,
-        rebuild_kind: SheetRebuildKind,
-    ) -> Result<(), FailedAllocationError> {
-        if rebuild_kind.should_rebuild_invalidation() {
-            self.invalidation_map.note_selector(&rule.selector, quirks_mode)?;
-            let mut visitor = StylistSelectorVisitor {
-                needs_revalidation: false,
-                passed_rightmost_selector: false,
-                attribute_dependencies: &mut self.attribute_dependencies,
-                style_attribute_dependency: &mut self.style_attribute_dependency,
-                state_dependencies: &mut self.state_dependencies,
-                document_state_dependencies: &mut self.document_state_dependencies,
-                mapped_ids: &mut self.mapped_ids,
-            };
-
-            rule.selector.visit(&mut visitor);
-
-            if visitor.needs_revalidation {
-                self.selectors_for_cache_revalidation.insert(
-                    RevalidationSelectorAndHashes::new(
-                        rule.selector.clone(),
-                        rule.hashes.clone(),
-                    ),
-                    quirks_mode
-                )?;
-            }
-        }
-
-        self.rules.insert(rule, pseudo_element, quirks_mode)
-    }
-
-    /// Returns the invalidation map.
-    #[inline]
-    pub fn invalidation_map(&self) -> &InvalidationMap {
-        &self.invalidation_map
-    }
-
-    #[cfg(feature = "gecko")]
-    fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
-        self.rules.add_size_of(ops, sizes);
-        sizes.mInvalidationMap += self.invalidation_map.size_of(ops);
-        sizes.mRevalidationSelectors += self.selectors_for_cache_revalidation.size_of(ops);
-    }
-
-    fn clear_cascade_data(&mut self) {
-        self.rules.clear();
-    }
-
-    fn clear(&mut self) {
-        self.clear_cascade_data();
-        self.invalidation_map.clear();
-        self.attribute_dependencies.clear();
-        self.style_attribute_dependency = false;
-        self.state_dependencies = ElementState::empty();
-        self.document_state_dependencies = DocumentState::empty();
-        self.mapped_ids.clear();
-        self.selectors_for_cache_revalidation.clear();
-    }
-
-    /// Returns whether the given attribute might appear in an attribute
-    /// selector of some rule.
-    #[inline]
-    pub fn might_have_attribute_dependency(
-        &self,
-        local_name: &LocalName,
-    ) -> bool {
-        if *local_name == local_name!("style") {
-            return self.style_attribute_dependency
-        }
-
-        self.attribute_dependencies.might_contain_hash(local_name.get_hash())
-    }
-
-    /// Returns whether the given ElementState bit is relied upon by a selector
-    /// of some rule.
-    #[inline]
-    pub fn has_state_dependency(&self, state: ElementState) -> bool {
-        self.state_dependencies.intersects(state)
-    }
-
-    /// Returns whether the given DocumentState bit is relied upon by a selector
-    /// of some rule in the stylist.
-    #[inline]
-    fn has_document_state_dependency(&self, state: DocumentState) -> bool {
-        self.document_state_dependencies.intersects(state)
-    }
-}
-
-impl StyleRuleCascadeData {
-    fn new() -> Self {
-        Self {
-            rules: ElementAndPseudoRules::default(),
-            invalidation_map: InvalidationMap::new(),
-            attribute_dependencies: NonCountingBloomFilter::new(),
-            style_attribute_dependency: false,
-            state_dependencies: ElementState::empty(),
-            document_state_dependencies: DocumentState::empty(),
-            mapped_ids: NonCountingBloomFilter::new(),
-            selectors_for_cache_revalidation: SelectorMap::new(),
-        }
-    }
-
-    #[inline]
-    fn rules(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
-        self.rules.borrow_for_pseudo(pseudo)
-    }
-}
-
-/// Data resulting from performing the CSS cascade that is specific to a given
-/// origin.
-///
-/// FIXME(emilio): Consider renaming and splitting in `CascadeData` and
-/// `InvalidationData`? That'd make `clear_cascade_data()` clearer.
-#[cfg_attr(feature = "servo", derive(MallocSizeOf))]
-#[derive(Debug)]
-struct CascadeData {
-    /// The data coming from normal style rules that apply to elements at this
-    /// cascade level.
-    normal_rule_data: StyleRuleCascadeData,
-
-    /// The data coming from ::slotted() pseudo-element rules.
-    ///
-    /// We need to store them separately because an element needs to match
-    /// ::slotted() pseudo-element rules in different shadow roots.
-    ///
-    /// In particular, we need to go through all the style data in all the
-    /// containing style scopes starting from the closest assigned slot.
-    slotted_rule_data: Option<Box<StyleRuleCascadeData>>,
 
     /// A map with all the animations at this `CascadeData`'s origin, indexed
     /// by name.
     animations: PrecomputedHashMap<Atom, KeyframesAnimation>,
 
     /// Effective media query results cached from the last rebuild.
     effective_media_query_results: EffectiveMediaQueryResults,
 
@@ -2141,35 +2002,67 @@ struct CascadeData {
 
     /// The total number of declarations.
     num_declarations: usize,
 }
 
 impl CascadeData {
     fn new() -> Self {
         Self {
-            normal_rule_data: StyleRuleCascadeData::new(),
-            slotted_rule_data: None,
+            normal_rules: ElementAndPseudoRules::default(),
+            slotted_rules: None,
+            invalidation_map: InvalidationMap::new(),
+            attribute_dependencies: NonCountingBloomFilter::new(),
+            style_attribute_dependency: false,
+            state_dependencies: ElementState::empty(),
+            document_state_dependencies: DocumentState::empty(),
+            mapped_ids: NonCountingBloomFilter::new(),
+            selectors_for_cache_revalidation: SelectorMap::new(),
             animations: Default::default(),
             extra_data: ExtraStyleData::default(),
             effective_media_query_results: EffectiveMediaQueryResults::new(),
             rules_source_order: 0,
             num_selectors: 0,
             num_declarations: 0,
         }
     }
 
+    /// Returns the invalidation map.
+    pub fn invalidation_map(&self) -> &InvalidationMap {
+        &self.invalidation_map
+    }
+
+    /// Returns whether the given ElementState bit is relied upon by a selector
+    /// of some rule.
+    #[inline]
+    pub fn has_state_dependency(&self, state: ElementState) -> bool {
+        self.state_dependencies.intersects(state)
+    }
+
+    /// Returns whether the given attribute might appear in an attribute
+    /// selector of some rule.
+    #[inline]
+    pub fn might_have_attribute_dependency(
+        &self,
+        local_name: &LocalName,
+    ) -> bool {
+        if *local_name == local_name!("style") {
+            return self.style_attribute_dependency
+        }
+
+        self.attribute_dependencies.might_contain_hash(local_name.get_hash())
+    }
     #[inline]
     fn normal_rules(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
-        self.normal_rule_data.rules(pseudo)
+        self.normal_rules.rules(pseudo)
     }
 
     #[inline]
     fn slotted_rules(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
-        self.slotted_rule_data.as_ref().and_then(|d| d.rules(pseudo))
+        self.slotted_rules.as_ref().and_then(|d| d.rules(pseudo))
     }
 
     /// Collects all the applicable media query results into `results`.
     ///
     /// This duplicates part of the logic in `add_stylesheet`, which is
     /// a bit unfortunate.
     ///
     /// FIXME(emilio): With a bit of smartness in
@@ -2265,30 +2158,53 @@ impl CascadeData {
 
                         let rule = Rule::new(
                             selector.clone(),
                             hashes,
                             locked.clone(),
                             self.rules_source_order
                         );
 
-                        let style_rule_cascade_data = if selector.is_slotted() {
-                            if self.slotted_rule_data.is_none() {
-                                self.slotted_rule_data = Some(Box::new(StyleRuleCascadeData::new()));
+                        if rebuild_kind.should_rebuild_invalidation() {
+                            self.invalidation_map.note_selector(&rule.selector, quirks_mode)?;
+                            let mut visitor = StylistSelectorVisitor {
+                                needs_revalidation: false,
+                                passed_rightmost_selector: false,
+                                attribute_dependencies: &mut self.attribute_dependencies,
+                                style_attribute_dependency: &mut self.style_attribute_dependency,
+                                state_dependencies: &mut self.state_dependencies,
+                                document_state_dependencies: &mut self.document_state_dependencies,
+                                mapped_ids: &mut self.mapped_ids,
+                            };
+
+                            rule.selector.visit(&mut visitor);
+
+                            if visitor.needs_revalidation {
+                                self.selectors_for_cache_revalidation.insert(
+                                    RevalidationSelectorAndHashes::new(
+                                        rule.selector.clone(),
+                                        rule.hashes.clone(),
+                                    ),
+                                    quirks_mode
+                                )?;
                             }
-                            self.slotted_rule_data.as_mut().unwrap()
+                        }
+
+                        let rules = if selector.is_slotted() {
+                            self.slotted_rules.get_or_insert_with(|| {
+                                Box::new(Default::default())
+                            })
                         } else {
-                            &mut self.normal_rule_data
+                            &mut self.normal_rules
                         };
 
-                        style_rule_cascade_data.insert(
+                        rules.insert(
                             rule,
                             pseudo_element,
                             quirks_mode,
-                            rebuild_kind,
                         )?;
                     }
                     self.rules_source_order += 1;
                 }
                 CssRule::Import(ref lock) => {
                     if rebuild_kind.should_rebuild_invalidation() {
                         let import_rule = lock.read_with(guard);
                         self.effective_media_query_results
@@ -2431,43 +2347,48 @@ impl CascadeData {
             }
         }
 
         true
     }
 
     /// Clears the cascade data, but not the invalidation data.
     fn clear_cascade_data(&mut self) {
-        self.normal_rule_data.clear_cascade_data();
-        if let Some(ref mut slotted_rule_data) = self.slotted_rule_data {
-            slotted_rule_data.clear_cascade_data();
+        self.normal_rules.clear();
+        if let Some(ref mut slotted_rules) = self.slotted_rules {
+            slotted_rules.clear();
         }
         self.animations.clear();
         self.extra_data.clear();
         self.rules_source_order = 0;
         self.num_selectors = 0;
         self.num_declarations = 0;
     }
 
     fn clear(&mut self) {
         self.clear_cascade_data();
-        self.normal_rule_data.clear();
-        if let Some(ref mut slotted_rule_data) = self.slotted_rule_data {
-            slotted_rule_data.clear();
-        }
+        self.invalidation_map.clear();
+        self.attribute_dependencies.clear();
+        self.style_attribute_dependency = false;
+        self.state_dependencies = ElementState::empty();
+        self.document_state_dependencies = DocumentState::empty();
+        self.mapped_ids.clear();
+        self.selectors_for_cache_revalidation.clear();
         self.effective_media_query_results.clear();
     }
 
     /// Measures heap usage.
     #[cfg(feature = "gecko")]
     fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
-        self.normal_rule_data.add_size_of(ops, sizes);
-        if let Some(ref slotted_rules) = self.slotted_rule_data {
+        self.normal_rules.add_size_of(ops, sizes);
+        if let Some(ref slotted_rules) = self.slotted_rules {
             slotted_rules.add_size_of(ops, sizes);
         }
+        sizes.mInvalidationMap += self.invalidation_map.size_of(ops);
+        sizes.mRevalidationSelectors += self.selectors_for_cache_revalidation.size_of(ops);
         sizes.mOther += self.animations.size_of(ops);
         sizes.mOther += self.effective_media_query_results.size_of(ops);
         sizes.mOther += self.extra_data.size_of(ops);
     }
 }
 
 impl Default for CascadeData {
     fn default() -> Self {

--- a/testing/web-platform/meta/MANIFEST.json
+++ b/testing/web-platform/meta/MANIFEST.json
@@ -301420,16 +301420,22 @@
     ]
    ],
    "css/css-scoping/shadow-cascade-order-001.html": [
     [
      "/css/css-scoping/shadow-cascade-order-001.html",
      {}
     ]
    ],
+   "css/css-scoping/slotted-invalidation.html": [
+    [
+     "/css/css-scoping/slotted-invalidation.html",
+     {}
+    ]
+   ],
    "css/css-scoping/slotted-parsing.html": [
     [
      "/css/css-scoping/slotted-parsing.html",
      {}
     ]
    ],
    "css/css-scroll-anchoring/abspos-containing-block-outside-scroller.html": [
     [
@@ -374155,35 +374161,43 @@
      {
       "timeout": "long"
      }
     ]
    ],
    "webdriver/tests/state/get_element_attribute.py": [
     [
      "/webdriver/tests/state/get_element_attribute.py",
-     {}
+     {
+      "timeout": "long"
+     }
     ]
    ],
    "webdriver/tests/state/get_element_property.py": [
     [
      "/webdriver/tests/state/get_element_property.py",
-     {}
+     {
+      "timeout": "long"
+     }
     ]
    ],
    "webdriver/tests/state/get_element_tag_name.py": [
     [
      "/webdriver/tests/state/get_element_tag_name.py",
-     {}
+     {
+      "timeout": "long"
+     }
     ]
    ],
    "webdriver/tests/state/is_element_selected.py": [
     [
      "/webdriver/tests/state/is_element_selected.py",
-     {}
+     {
+      "timeout": "long"
+     }
     ]
    ],
    "webdriver/tests/state/text/get_text.py": [
     [
      "/webdriver/tests/state/text/get_text.py",
      {}
     ]
    ],
@@ -488191,16 +488205,20 @@
   "css/css-scoping/reference/green-box.html": [
    "a736f68dc602c0fccab56ec5cc6234cb3298c88d",
    "support"
   ],
   "css/css-scoping/shadow-cascade-order-001.html": [
    "46913ea7e47811b11be898de5c3bd0a330ea6637",
    "testharness"
   ],
+  "css/css-scoping/slotted-invalidation.html": [
+   "92dadd5f67eb4305008db8429674f71c1a972763",
+   "testharness"
+  ],
   "css/css-scoping/slotted-parsing.html": [
    "6bac5b15011d7177a40f7ca3e3c5f7e410643920",
    "testharness"
   ],
   "css/css-scoping/slotted-with-pseudo-element-ref.html": [
    "48561a3dff973b7ad1bfa9702461e50fd4a67c2d",
    "support"
   ],
@@ -523824,17 +523842,17 @@
    "9a4881ad5825e2c4e967226f537e4e5ae281c2fb",
    "reftest"
   ],
   "custom-elements/CustomElementRegistry.html": [
    "d1661ab1734f7d1a252030aeac7e9842a7a4cb3b",
    "testharness"
   ],
   "custom-elements/Document-createElement.html": [
-   "fb10e851deb193aed700c8ab6790c216766cc362",
+   "14960ee9498f6ff23c1c94d3351a8ef383e60067",
    "testharness"
   ],
   "custom-elements/HTMLElement-constructor.html": [
    "64522527ef425b90c704b20b000c8feef0d1ca25",
    "testharness"
   ],
   "custom-elements/OWNERS": [
    "9f6553b67cad3b479d3beb678653db4e712ed227",
@@ -523884,17 +523902,17 @@
    "b338f193a803ea679bbf0e041f71daf1e6d703f6",
    "testharness"
   ],
   "custom-elements/parser/parser-constructs-custom-element-synchronously.html": [
    "dc0ca4a066d9a05362a81b263594965763919e46",
    "testharness"
   ],
   "custom-elements/parser/parser-constructs-custom-elements-with-is.html": [
-   "7a7df7aab092906b5a753c0d122b971aff01517a",
+   "17145d44113ea88688060c6cfd10d162cd97e28b",
    "testharness"
   ],
   "custom-elements/parser/parser-constructs-custom-elements.html": [
    "228d4a90d57dc942692becc6f126ec9130b3a4e0",
    "testharness"
   ],
   "custom-elements/parser/parser-fallsback-to-unknown-element.html": [
    "2fbbd742bfdc3ab63c5d5f01160830451fe620d2",
@@ -531220,17 +531238,17 @@
    "99a355c63562aded2e2b252d989de332e8c12a0d",
    "testharness"
   ],
   "html/browsers/browsing-the-web/scroll-to-fragid/scroll-frag-percent-encoded.html": [
    "ac172eb5c05ee24b8e3059cbc68851729f1be943",
    "testharness"
   ],
   "html/browsers/browsing-the-web/scroll-to-fragid/scroll-to-anchor-name.html": [
-   "8de758988400b4b1acad6bb4c94069b4d0167c20",
+   "9bc91bc9bb368e8bf42810ed8aed936a6c9d581a",
    "testharness"
   ],
   "html/browsers/browsing-the-web/scroll-to-fragid/scroll-to-id-top.html": [
    "4a4da96ba43bd45b6723b852277c9169b56ec2e1",
    "testharness"
   ],
   "html/browsers/browsing-the-web/scroll-to-fragid/scroll-to-top.html": [
    "2dabab8b5505e7934c0977f1cf0975d4600981d5",
@@ -568216,17 +568234,17 @@
    "4aaa0b1995643f4e18c47d1947476a1a67fe997d",
    "testharness"
   ],
   "service-workers/service-worker/fetch-request-xhr.https.html": [
    "b30618dfe4c10370865229cbe9606cce8ed42040",
    "testharness"
   ],
   "service-workers/service-worker/fetch-response-taint.https.html": [
-   "217383b4dddcc6f984c4cc7cd5f99e1f9b86cdd1",
+   "154a52255d0aae9a99879389afba6214b803b08d",
    "testharness"
   ],
   "service-workers/service-worker/fetch-response-xhr.https.html": [
    "6b68ad7251c3daef1cd2bde8660f01c3e47b711f",
    "testharness"
   ],
   "service-workers/service-worker/fetch-waits-for-activate.https.html": [
    "04eeedc3f074aff32281a438acda62b7a6d86e2d",
@@ -569556,17 +569574,17 @@
    "40ec7850c61a3ee7578f055d3eef87293cfad482",
    "testharness"
   ],
   "service-workers/service-worker/windowclient-navigate.https.html": [
    "828d8d920459541a37e747ac01376fdcac51ffb3",
    "testharness"
   ],
   "service-workers/service-worker/worker-interception.https.html": [
-   "2c5e8cb2b7be6d394aaa1400158d3f14895909f3",
+   "41f7e5e8da2c305370fddad83518cd0fa57547eb",
    "testharness"
   ],
   "service-workers/specgen.json": [
    "0d98c8249e25cd4c7a4d88f722cfe8f235fb7a66",
    "support"
   ],
   "service-workers/stub-3.1-service-worker-obj.html": [
    "26e7afb8569cc3c997c6338dc86bfbe7232a8c0e",
@@ -577016,29 +577034,29 @@
    "8a124f80e6e7732a651a80da3f6cdf8e2ed99e3e",
    "wdspec"
   ],
   "webdriver/tests/state/__init__.py": [
    "da39a3ee5e6b4b0d3255bfef95601890afd80709",
    "support"
   ],
   "webdriver/tests/state/get_element_attribute.py": [
-   "75620b583be6495d9b7b5d65c57cbda217cd2e01",
+   "1fcd451313d40a0b0a84ced63596d032ffc97f2a",
    "wdspec"
   ],
   "webdriver/tests/state/get_element_property.py": [
-   "042f184dd54153fe5ff46e886ddcf27ffe4bae6d",
+   "c0fdf271eebb7dcef16a37a897362ed48eec2df1",
    "wdspec"
   ],
   "webdriver/tests/state/get_element_tag_name.py": [
-   "0887f71ceb4b4959989ee9f589707624f46e0ce3",
+   "ce749e286bd030083fcac15dd75c49caf032f990",
    "wdspec"
   ],
   "webdriver/tests/state/is_element_selected.py": [
-   "fb7825918c186d97abe69c4ab06fea1ed62f5387",
+   "f52c565da22038a41db7344cbcfa2a6a101cc61d",
    "wdspec"
   ],
   "webdriver/tests/state/text/__init__.py": [
    "da39a3ee5e6b4b0d3255bfef95601890afd80709",
    "support"
   ],
   "webdriver/tests/state/text/get_text.py": [
    "570274d59020c4d8d0b8ecd604660ee7d710a165",

new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/css/css-scoping/slotted-invalidation.html
@@ -0,0 +1,39 @@
+<!doctype html>
+<title>CSS Test: Style invalidation for ::slotted()</title>
+<script src="/resources/testharness.js"></script>
+<script src="/resources/testharnessreport.js"></script>
+<link rel="author" title="Rune Lillesveen" href="mailto:futhark@chromium.org">
+<link rel="author" title="Emilio Cobos Álvarez" href="mailto:emilio@crisal.io">
+<link rel="help" href="https://drafts.csswg.org/css-scoping/#slotted-pseudo">
+<div id="host">
+  <div>
+    <span></span>
+    <span></span>
+  </div>
+  <div id="slotted">
+    <span></span>
+    <span></span>
+  </div>
+  <div>
+    <span></span>
+    <span></span>
+  </div>
+</div>
+<script>
+test(function() {
+  var root = host.attachShadow({"mode":"open"});
+  root.innerHTML = '<style>.outer ::slotted(#slotted) { background-color: red } .outer .inner::slotted(#slotted) { background-color: green }</style><div id="outer"><slot id="inner"></slot></div>';
+
+  assert_equals(window.getComputedStyle(slotted).backgroundColor, "rgba(0, 0, 0, 0)");
+
+  host.offsetTop;
+
+  root.querySelector("#outer").className = "outer";
+  assert_equals(window.getComputedStyle(slotted).backgroundColor, "rgb(255, 0, 0)");
+
+  host.offsetTop;
+
+  root.querySelector("#inner").className = "inner";
+  assert_equals(window.getComputedStyle(slotted).backgroundColor, "rgb(0, 128, 0)");
+})
+</script>