style: Implement a more fine-grained invalidation method.

This commit also removes the old restyle_hints module and splits it into
multiple modules under components/style/invalidation/element/.

The basic approach is to walk down the tree using compound selectors as needed,
in order to do as little selector-matching as possible.

Bug: 1368240
MozReview-Commit-ID: 2YO8fKFygZI

18 files changed, 1673 insertions, 1455 deletions

diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index 2b8ac715203..39c617c8099 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -131,7 +131,7 @@ use std::rc::Rc;
 use std::time::{Duration, Instant};
 use style::attr::AttrValue;
 use style::context::{QuirksMode, ReflowGoal};
-use style::restyle_hints::{RestyleHint, RESTYLE_STYLE_ATTRIBUTE};
+use style::invalidation::element::restyle_hints::{RestyleHint, RESTYLE_SELF, RESTYLE_STYLE_ATTRIBUTE};
 use style::selector_parser::{RestyleDamage, Snapshot};
 use style::shared_lock::SharedRwLock as StyleSharedRwLock;
 use style::str::{HTML_SPACE_CHARACTERS, split_html_space_chars, str_join};
@@ -2376,14 +2376,14 @@ impl Document {
             entry.snapshot = Some(Snapshot::new(el.html_element_in_html_document()));
         }
         if attr.local_name() == &local_name!("style") {
-            entry.hint.insert(RestyleHint::for_replacements(RESTYLE_STYLE_ATTRIBUTE));
+            entry.hint.insert(RESTYLE_STYLE_ATTRIBUTE);
         }
 
         // FIXME(emilio): This should become something like
         // element.is_attribute_mapped(attr.local_name()).
         if attr.local_name() == &local_name!("width") ||
            attr.local_name() == &local_name!("height") {
-            entry.hint.insert(RestyleHint::for_self());
+            entry.hint.insert(RESTYLE_SELF);
         }
 
         let mut snapshot = entry.snapshot.as_mut().unwrap();
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index ebeef51de89..7e01bc66764 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -102,9 +102,9 @@ use style::applicable_declarations::ApplicableDeclarationBlock;
 use style::attr::{AttrValue, LengthOrPercentageOrAuto};
 use style::context::{QuirksMode, ReflowGoal};
 use style::element_state::*;
+use style::invalidation::element::restyle_hints::RESTYLE_SELF;
 use style::properties::{Importance, PropertyDeclaration, PropertyDeclarationBlock, parse_style_attribute};
 use style::properties::longhands::{self, background_image, border_spacing, font_family, font_size, overflow_x};
-use style::restyle_hints::RestyleHint;
 use style::rule_tree::CascadeLevel;
 use style::selector_parser::{NonTSPseudoClass, PseudoElement, RestyleDamage, SelectorImpl, SelectorParser};
 use style::selector_parser::extended_filtering;
@@ -253,7 +253,7 @@ impl Element {
 
         // FIXME(bholley): I think we should probably only do this for
         // NodeStyleDamaged, but I'm preserving existing behavior.
-        restyle.hint.insert(RestyleHint::for_self());
+        restyle.hint.insert(RESTYLE_SELF);
 
         if damage == NodeDamage::OtherNodeDamage {
             restyle.damage = RestyleDamage::rebuild_and_reflow();
diff --git a/components/style/context.rs b/components/style/context.rs
index 4526ba82aa8..c63f20e92d5 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -250,7 +250,8 @@ impl TraversalStatistics {
         self.traversal_time_ms = (time::precise_time_s() - start) * 1000.0;
         self.selectors = traversal.shared_context().stylist.num_selectors() as u32;
         self.revalidation_selectors = traversal.shared_context().stylist.num_revalidation_selectors() as u32;
-        self.dependency_selectors = traversal.shared_context().stylist.num_dependencies() as u32;
+        self.dependency_selectors =
+            traversal.shared_context().stylist.invalidation_map().len() as u32;
         self.declarations = traversal.shared_context().stylist.num_declarations() as u32;
         self.stylist_rebuilds = traversal.shared_context().stylist.num_rebuilds() as u32;
     }
diff --git a/components/style/data.rs b/components/style/data.rs
index c66417f4a59..ffb2ea4578c 100644
--- a/components/style/data.rs
+++ b/components/style/data.rs
@@ -7,9 +7,9 @@
 use arrayvec::ArrayVec;
 use context::SharedStyleContext;
 use dom::TElement;
+use invalidation::element::restyle_hints::RestyleHint;
 use properties::{AnimationRules, ComputedValues, PropertyDeclarationBlock};
 use properties::longhands::display::computed_value as display;
-use restyle_hints::{CascadeHint, HintComputationContext, RestyleReplacements, RestyleHint};
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage};
 use selectors::matching::VisitedHandlingMode;
@@ -345,8 +345,10 @@ impl ElementStyles {
 ///
 /// We wrap it in a newtype to force the encapsulation of the complexity of
 /// handling the correct invalidations in this file.
-#[derive(Clone, Debug)]
-pub struct StoredRestyleHint(RestyleHint);
+///
+/// TODO(emilio): This will probably be a non-issue in a bit.
+#[derive(Clone, Copy, Debug)]
+pub struct StoredRestyleHint(pub RestyleHint);
 
 impl StoredRestyleHint {
     /// Propagates this restyle hint to a child element.
@@ -378,14 +380,7 @@ impl StoredRestyleHint {
     /// Creates a restyle hint that forces the whole subtree to be restyled,
     /// including the element.
     pub fn subtree() -> Self {
-        StoredRestyleHint(RestyleHint::subtree())
-    }
-
-    /// Creates a restyle hint that forces the element and all its later
-    /// siblings to have their whole subtrees restyled, including the elements
-    /// themselves.
-    pub fn subtree_and_later_siblings() -> Self {
-        StoredRestyleHint(RestyleHint::subtree_and_later_siblings())
+        StoredRestyleHint(RestyleHint::restyle_subtree())
     }
 
     /// Creates a restyle hint that indicates the element must be recascaded.
@@ -398,12 +393,6 @@ impl StoredRestyleHint {
         self.0.affects_self()
     }
 
-    /// Returns true if the hint indicates that our sibling's style may be
-    /// invalidated.
-    pub fn has_sibling_invalidations(&self) -> bool {
-        self.0.affects_later_siblings()
-    }
-
     /// Whether the restyle hint is empty (nothing requires to be restyled).
     pub fn is_empty(&self) -> bool {
         self.0.is_empty()
@@ -416,12 +405,7 @@ impl StoredRestyleHint {
 
     /// Contains whether the whole subtree is invalid.
     pub fn contains_subtree(&self) -> bool {
-        self.0.contains(&RestyleHint::subtree())
-    }
-
-    /// Insert another restyle hint, effectively resulting in the union of both.
-    pub fn insert_from(&mut self, other: &Self) {
-        self.0.insert_from(&other.0)
+        self.0.contains(RestyleHint::restyle_subtree())
     }
 
     /// Returns true if the hint has animation-only restyle.
@@ -434,16 +418,11 @@ impl StoredRestyleHint {
     pub fn has_recascade_self(&self) -> bool {
         self.0.has_recascade_self()
     }
-
-    /// Insert the specified `CascadeHint`.
-    pub fn insert_cascade_hint(&mut self, cascade_hint: CascadeHint) {
-        self.0.insert_cascade_hint(cascade_hint);
-    }
 }
 
 impl Default for StoredRestyleHint {
     fn default() -> Self {
-        StoredRestyleHint::empty()
+        Self::empty()
     }
 }
 
@@ -483,11 +462,6 @@ impl RestyleData {
         self.hint.has_self_invalidations()
     }
 
-    /// Returns true if this RestyleData might invalidate sibling styles.
-    pub fn has_sibling_invalidations(&self) -> bool {
-        self.hint.has_sibling_invalidations()
-    }
-
     /// Returns damage handled.
     #[cfg(feature = "gecko")]
     pub fn damage_handled(&self) -> RestyleDamage {
@@ -533,66 +507,41 @@ pub enum RestyleKind {
     MatchAndCascade,
     /// We need to recascade with some replacement rule, such as the style
     /// attribute, or animation rules.
-    CascadeWithReplacements(RestyleReplacements),
+    CascadeWithReplacements(RestyleHint),
     /// We only need to recascade, for example, because only inherited
     /// properties in the parent changed.
     CascadeOnly,
 }
 
 impl ElementData {
-    /// Computes the final restyle hint for this element, potentially allocating
-    /// a `RestyleData` if we need to.
-    ///
-    /// This expands the snapshot (if any) into a restyle hint, and handles
-    /// explicit sibling restyle hints from the stored restyle hint.
-    ///
-    /// Returns true if later siblings must be restyled.
-    pub fn compute_final_hint<'a, E: TElement>(
+    /// Invalidates style for this element, its descendants, and later siblings,
+    /// based on the snapshot of the element that we took when attributes or
+    /// state changed.
+    pub fn invalidate_style_if_needed<'a, E: TElement>(
         &mut self,
         element: E,
-        shared_context: &SharedStyleContext,
-        hint_context: HintComputationContext<'a, E>)
-        -> bool
+        shared_context: &SharedStyleContext)
     {
-        debug!("compute_final_hint: {:?}, {:?}",
-               element,
-               shared_context.traversal_flags);
+        use invalidation::element::invalidator::TreeStyleInvalidator;
 
-        let mut hint = match self.get_restyle() {
-            Some(r) => r.hint.0.clone(),
-            None => RestyleHint::empty(),
-        };
-
-        debug!("compute_final_hint: {:?}, has_snapshot: {}, handled_snapshot: {}, \
-                pseudo: {:?}",
+        debug!("invalidate_style_if_needed: {:?}, flags: {:?}, has_snapshot: {}, \
+                handled_snapshot: {}, pseudo: {:?}",
                 element,
+                shared_context.traversal_flags,
                 element.has_snapshot(),
                 element.handled_snapshot(),
                 element.implemented_pseudo_element());
 
         if element.has_snapshot() && !element.handled_snapshot() {
-            let snapshot_hint =
-                shared_context.stylist.compute_restyle_hint(&element,
-                                                            shared_context,
-                                                            hint_context);
-            hint.insert(snapshot_hint);
+            let invalidator = TreeStyleInvalidator::new(
+                element,
+                Some(self),
+                shared_context,
+            );
+            invalidator.invalidate();
             unsafe { element.set_handled_snapshot() }
             debug_assert!(element.handled_snapshot());
         }
-
-        let empty_hint = hint.is_empty();
-
-        // If the hint includes a directive for later siblings, strip it out and
-        // notify the caller to modify the base hint for future siblings.
-        let later_siblings = hint.remove_later_siblings_hint();
-
-        // Insert the hint, overriding the previous hint. This effectively takes
-        // care of removing the later siblings restyle hint.
-        if !empty_hint {
-            self.ensure_restyle().hint = hint.into();
-        }
-
-        later_siblings
     }
 
 
@@ -626,13 +575,13 @@ impl ElementData {
         debug_assert!(self.restyle.is_some());
         let restyle_data = self.restyle.as_ref().unwrap();
 
-        let hint = &restyle_data.hint.0;
+        let hint = restyle_data.hint.0;
         if hint.match_self() {
             return RestyleKind::MatchAndCascade;
         }
 
         if hint.has_replacements() {
-            return RestyleKind::CascadeWithReplacements(hint.replacements);
+            return RestyleKind::CascadeWithReplacements(hint & RestyleHint::replacements());
         }
 
         debug_assert!(hint.has_recascade_self(), "We definitely need to do something!");
diff --git a/components/style/gecko/snapshot.rs b/components/style/gecko/snapshot.rs
index a96c5471156..f8368d2ae43 100644
--- a/components/style/gecko/snapshot.rs
+++ b/components/style/gecko/snapshot.rs
@@ -13,7 +13,7 @@ use gecko_bindings::bindings;
 use gecko_bindings::structs::ServoElementSnapshot;
 use gecko_bindings::structs::ServoElementSnapshotFlags as Flags;
 use gecko_bindings::structs::ServoElementSnapshotTable;
-use restyle_hints::ElementSnapshot;
+use invalidation::element::element_wrapper::ElementSnapshot;
 use selectors::attr::{AttrSelectorOperation, AttrSelectorOperator, CaseSensitivity, NamespaceConstraint};
 use string_cache::{Atom, Namespace};
 
diff --git a/components/style/invalidation/element/element_wrapper.rs b/components/style/invalidation/element/element_wrapper.rs
new file mode 100644
index 00000000000..2bb2c3857dc
--- /dev/null
+++ b/components/style/invalidation/element/element_wrapper.rs
@@ -0,0 +1,341 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! A wrapper over an element and a snapshot, that allows us to selector-match
+//! against a past state of the element.
+
+use {Atom, CaseSensitivityExt, LocalName, Namespace};
+use dom::TElement;
+use element_state::ElementState;
+use selector_parser::{NonTSPseudoClass, PseudoElement, SelectorImpl, Snapshot, SnapshotMap, AttrValue};
+use selectors::Element;
+use selectors::attr::{AttrSelectorOperation, CaseSensitivity, NamespaceConstraint};
+use selectors::matching::{ElementSelectorFlags, LocalMatchingContext, MatchingContext};
+use selectors::matching::RelevantLinkStatus;
+use std::cell::Cell;
+use std::fmt;
+
+/// In order to compute restyle hints, we perform a selector match against a
+/// list of partial selectors whose rightmost simple selector may be sensitive
+/// to the thing being changed. We do this matching twice, once for the element
+/// as it exists now and once for the element as it existed at the time of the
+/// last restyle. If the results of the selector match differ, that means that
+/// the given partial selector is sensitive to the change, and we compute a
+/// restyle hint based on its combinator.
+///
+/// In order to run selector matching against the old element state, we generate
+/// a wrapper for the element which claims to have the old state. This is the
+/// ElementWrapper logic below.
+///
+/// Gecko does this differently for element states, and passes a mask called
+/// mStateMask, which indicates the states that need to be ignored during
+/// selector matching. This saves an ElementWrapper allocation and an additional
+/// selector match call at the expense of additional complexity inside the
+/// selector matching logic. This only works for boolean states though, so we
+/// still need to take the ElementWrapper approach for attribute-dependent
+/// style. So we do it the same both ways for now to reduce complexity, but it's
+/// worth measuring the performance impact (if any) of the mStateMask approach.
+pub trait ElementSnapshot : Sized {
+    /// The state of the snapshot, if any.
+    fn state(&self) -> Option<ElementState>;
+
+    /// If this snapshot contains attribute information.
+    fn has_attrs(&self) -> bool;
+
+    /// The ID attribute per this snapshot. Should only be called if
+    /// `has_attrs()` returns true.
+    fn id_attr(&self) -> Option<Atom>;
+
+    /// Whether this snapshot contains the class `name`. Should only be called
+    /// if `has_attrs()` returns true.
+    fn has_class(&self, name: &Atom, case_sensitivity: CaseSensitivity) -> bool;
+
+    /// A callback that should be called for each class of the snapshot. Should
+    /// only be called if `has_attrs()` returns true.
+    fn each_class<F>(&self, F)
+        where F: FnMut(&Atom);
+
+    /// The `xml:lang=""` or `lang=""` attribute value per this snapshot.
+    fn lang_attr(&self) -> Option<AttrValue>;
+}
+
+/// A simple wrapper over an element and a snapshot, that allows us to
+/// selector-match against a past state of the element.
+#[derive(Clone)]
+pub struct ElementWrapper<'a, E>
+    where E: TElement,
+{
+    element: E,
+    cached_snapshot: Cell<Option<&'a Snapshot>>,
+    snapshot_map: &'a SnapshotMap,
+}
+
+impl<'a, E> ElementWrapper<'a, E>
+    where E: TElement,
+{
+    /// Trivially constructs an `ElementWrapper`.
+    pub fn new(el: E, snapshot_map: &'a SnapshotMap) -> Self {
+        ElementWrapper {
+            element: el,
+            cached_snapshot: Cell::new(None),
+            snapshot_map: snapshot_map,
+        }
+    }
+
+    /// Gets the snapshot associated with this element, if any.
+    pub fn snapshot(&self) -> Option<&'a Snapshot> {
+        if !self.element.has_snapshot() {
+            return None;
+        }
+
+        if let Some(s) = self.cached_snapshot.get() {
+            return Some(s);
+        }
+
+        let snapshot = self.snapshot_map.get(&self.element);
+        debug_assert!(snapshot.is_some(), "has_snapshot lied!");
+
+        self.cached_snapshot.set(snapshot);
+
+        snapshot
+    }
+
+    /// Returns the states that have changed since the element was snapshotted.
+    pub fn state_changes(&self) -> ElementState {
+        let snapshot = match self.snapshot() {
+            Some(s) => s,
+            None => return ElementState::empty(),
+        };
+
+        match snapshot.state() {
+            Some(state) => state ^ self.element.get_state(),
+            None => ElementState::empty(),
+        }
+    }
+
+    /// Returns the value of the `xml:lang=""` (or, if appropriate, `lang=""`)
+    /// attribute from this element's snapshot or the closest ancestor
+    /// element snapshot with the attribute specified.
+    fn get_lang(&self) -> Option<AttrValue> {
+        let mut current = self.clone();
+        loop {
+            let lang = match self.snapshot() {
+                Some(snapshot) if snapshot.has_attrs() => snapshot.lang_attr(),
+                _ => current.element.lang_attr(),
+            };
+            if lang.is_some() {
+                return lang;
+            }
+            match current.parent_element() {
+                Some(parent) => current = parent,
+                None => return None,
+            }
+        }
+    }
+}
+
+impl<'a, E> fmt::Debug for ElementWrapper<'a, E>
+    where E: TElement,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        // Ignore other fields for now, can change later if needed.
+        self.element.fmt(f)
+    }
+}
+
+impl<'a, E> Element for ElementWrapper<'a, E>
+    where E: TElement,
+{
+    type Impl = SelectorImpl;
+
+    fn match_non_ts_pseudo_class<F>(&self,
+                                    pseudo_class: &NonTSPseudoClass,
+                                    context: &mut LocalMatchingContext<Self::Impl>,
+                                    relevant_link: &RelevantLinkStatus,
+                                    _setter: &mut F)
+                                    -> bool
+        where F: FnMut(&Self, ElementSelectorFlags),
+    {
+        // Some pseudo-classes need special handling to evaluate them against
+        // the snapshot.
+        match *pseudo_class {
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::MozAny(ref selectors) => {
+                use selectors::matching::matches_complex_selector;
+                return selectors.iter().any(|s| {
+                    matches_complex_selector(s.iter(), self, context, _setter)
+                })
+            }
+
+            // :dir is implemented in terms of state flags, but which state flag
+            // it maps to depends on the argument to :dir.  That means we can't
+            // just add its state flags to the NonTSPseudoClass, because if we
+            // added all of them there, and tested via intersects() here, we'd
+            // get incorrect behavior for :not(:dir()) cases.
+            //
+            // FIXME(bz): How can I set this up so once Servo adds :dir()
+            // support we don't forget to update this code?
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::Dir(ref s) => {
+                use invalidation::element::invalidation_map::dir_selector_to_state;
+                let selector_flag = dir_selector_to_state(s);
+                if selector_flag.is_empty() {
+                    // :dir() with some random argument; does not match.
+                    return false;
+                }
+                let state = match self.snapshot().and_then(|s| s.state()) {
+                    Some(snapshot_state) => snapshot_state,
+                    None => self.element.get_state(),
+                };
+                return state.contains(selector_flag);
+            }
+
+            // For :link and :visited, we don't actually want to test the element
+            // state directly.  Instead, we use the `relevant_link` to determine if
+            // they match.
+            NonTSPseudoClass::Link => {
+                return relevant_link.is_unvisited(self, context.shared);
+            }
+            NonTSPseudoClass::Visited => {
+                return relevant_link.is_visited(self, context.shared);
+            }
+
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::MozTableBorderNonzero => {
+                if let Some(snapshot) = self.snapshot() {
+                    if snapshot.has_other_pseudo_class_state() {
+                        return snapshot.mIsTableBorderNonzero();
+                    }
+                }
+            }
+
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::MozBrowserFrame => {
+                if let Some(snapshot) = self.snapshot() {
+                    if snapshot.has_other_pseudo_class_state() {
+                        return snapshot.mIsMozBrowserFrame();
+                    }
+                }
+            }
+
+            // :lang() needs to match using the closest ancestor xml:lang="" or
+            // lang="" attribtue from snapshots.
+            NonTSPseudoClass::Lang(ref lang_arg) => {
+                return self.element.match_element_lang(Some(self.get_lang()), lang_arg);
+            }
+
+            _ => {}
+        }
+
+        let flag = pseudo_class.state_flag();
+        if flag.is_empty() {
+            return self.element.match_non_ts_pseudo_class(pseudo_class,
+                                                          context,
+                                                          relevant_link,
+                                                          &mut |_, _| {})
+        }
+        match self.snapshot().and_then(|s| s.state()) {
+            Some(snapshot_state) => snapshot_state.intersects(flag),
+            None => {
+                self.element.match_non_ts_pseudo_class(pseudo_class,
+                                                       context,
+                                                       relevant_link,
+                                                       &mut |_, _| {})
+            }
+        }
+    }
+
+    fn match_pseudo_element(&self,
+                            pseudo_element: &PseudoElement,
+                            context: &mut MatchingContext)
+                            -> bool
+    {
+        self.element.match_pseudo_element(pseudo_element, context)
+    }
+
+    fn is_link(&self) -> bool {
+        self.element.is_link()
+    }
+
+    fn parent_element(&self) -> Option<Self> {
+        self.element.parent_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+
+    fn first_child_element(&self) -> Option<Self> {
+        self.element.first_child_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+
+    fn last_child_element(&self) -> Option<Self> {
+        self.element.last_child_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+
+    fn prev_sibling_element(&self) -> Option<Self> {
+        self.element.prev_sibling_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+
+    fn next_sibling_element(&self) -> Option<Self> {
+        self.element.next_sibling_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+
+    fn is_html_element_in_html_document(&self) -> bool {
+        self.element.is_html_element_in_html_document()
+    }
+
+    fn get_local_name(&self) -> &<Self::Impl as ::selectors::SelectorImpl>::BorrowedLocalName {
+        self.element.get_local_name()
+    }
+
+    fn get_namespace(&self) -> &<Self::Impl as ::selectors::SelectorImpl>::BorrowedNamespaceUrl {
+        self.element.get_namespace()
+    }
+
+    fn attr_matches(&self,
+                    ns: &NamespaceConstraint<&Namespace>,
+                    local_name: &LocalName,
+                    operation: &AttrSelectorOperation<&AttrValue>)
+                    -> bool {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => {
+                snapshot.attr_matches(ns, local_name, operation)
+            }
+            _ => self.element.attr_matches(ns, local_name, operation)
+        }
+    }
+
+    fn has_id(&self, id: &Atom, case_sensitivity: CaseSensitivity) -> bool {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => {
+                snapshot.id_attr().map_or(false, |atom| case_sensitivity.eq_atom(&atom, id))
+            }
+            _ => self.element.has_id(id, case_sensitivity)
+        }
+    }
+
+    fn has_class(&self, name: &Atom, case_sensitivity: CaseSensitivity) -> bool {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => {
+                snapshot.has_class(name, case_sensitivity)
+            }
+            _ => self.element.has_class(name, case_sensitivity)
+        }
+    }
+
+    fn is_empty(&self) -> bool {
+        self.element.is_empty()
+    }
+
+    fn is_root(&self) -> bool {
+        self.element.is_root()
+    }
+
+    fn pseudo_element_originating_element(&self) -> Option<Self> {
+        self.element.closest_non_native_anonymous_ancestor()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+}
diff --git a/components/style/invalidation/element/invalidation_map.rs b/components/style/invalidation/element/invalidation_map.rs
new file mode 100644
index 00000000000..8e4dfebec99
--- /dev/null
+++ b/components/style/invalidation/element/invalidation_map.rs
@@ -0,0 +1,402 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Code for invalidations due to state or attribute changes.
+
+use {Atom, LocalName, Namespace};
+use context::QuirksMode;
+use element_state::ElementState;
+use selector_map::{MaybeCaseInsensitiveHashMap, SelectorMap, SelectorMapEntry};
+use selector_parser::SelectorImpl;
+use selectors::attr::NamespaceConstraint;
+use selectors::parser::{AncestorHashes, Combinator, Component};
+use selectors::parser::{Selector, SelectorAndHashes, SelectorIter, SelectorMethods};
+use selectors::visitor::SelectorVisitor;
+use smallvec::SmallVec;
+
+#[cfg(feature = "gecko")]
+/// Gets the element state relevant to the given `:dir` pseudo-class selector.
+pub fn dir_selector_to_state(s: &[u16]) -> ElementState {
+    use element_state::{IN_LTR_STATE, IN_RTL_STATE};
+
+    // Jump through some hoops to deal with our Box<[u16]> thing.
+    const LTR: [u16; 4] = [b'l' as u16, b't' as u16, b'r' as u16, 0];
+    const RTL: [u16; 4] = [b'r' as u16, b't' as u16, b'l' as u16, 0];
+
+    if LTR == *s {
+        IN_LTR_STATE
+    } else if RTL == *s {
+        IN_RTL_STATE
+    } else {
+        // :dir(something-random) is a valid selector, but shouldn't
+        // match anything.
+        ElementState::empty()
+    }
+}
+
+/// Mapping between (partial) CompoundSelectors (and the combinator to their
+/// right) and the states and attributes they depend on.
+///
+/// In general, for all selectors in all applicable stylesheets of the form:
+///
+/// |a _ b _ c _ d _ e|
+///
+/// Where:
+///   * |b| and |d| are simple selectors that depend on state (like :hover) or
+///     attributes (like [attr...], .foo, or #foo).
+///   * |a|, |c|, and |e| are arbitrary simple selectors that do not depend on
+///     state or attributes.
+///
+/// We generate a Dependency for both |a _ b:X _| and |a _ b:X _ c _ d:Y _|,
+/// even though those selectors may not appear on their own in any stylesheet.
+/// This allows us to quickly scan through the dependency sites of all style
+/// rules and determine the maximum effect that a given state or attribute
+/// change may have on the style of elements in the document.
+#[derive(Clone, Debug)]
+#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
+pub struct Dependency {
+    /// The dependency selector.
+    #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
+    pub selector: Selector<SelectorImpl>,
+    /// The ancestor hashes associated with the above selector at the given
+    /// offset.
+    #[cfg_attr(feature = "servo", ignore_heap_size_of = "No heap data")]
+    pub hashes: AncestorHashes,
+    /// The offset into the selector that we should match on.
+    pub selector_offset: usize,
+}
+
+impl Dependency {
+    /// Returns the combinator to the right of the partial selector this
+    /// dependency represents.
+    ///
+    /// TODO(emilio): Consider storing inline if it helps cache locality?
+    pub fn combinator(&self) -> Option<Combinator> {
+        if self.selector_offset == 0 {
+            return None;
+        }
+
+        Some(self.selector.combinator_at(self.selector_offset))
+    }
+
+    /// Whether this dependency affects the style of the element.
+    ///
+    /// NOTE(emilio): pseudo-elements need to be here to account for eager
+    /// pseudos, since they just grab the style from the originating element.
+    ///
+    /// TODO(emilio): We could look at the selector itself to see if it's an
+    /// eager pseudo, and return false here if not.
+    pub fn affects_self(&self) -> bool {
+        matches!(self.combinator(), None | Some(Combinator::PseudoElement))
+    }
+
+    /// Whether this dependency may affect style of any of our descendants.
+    pub fn affects_descendants(&self) -> bool {
+        matches!(self.combinator(), Some(Combinator::PseudoElement) |
+                                    Some(Combinator::Child) |
+                                    Some(Combinator::Descendant))
+    }
+
+    /// Whether this dependency may affect style of any of our later siblings.
+    pub fn affects_later_siblings(&self) -> bool {
+        matches!(self.combinator(), Some(Combinator::NextSibling) |
+                                    Some(Combinator::LaterSibling))
+    }
+}
+
+impl SelectorMapEntry for Dependency {
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.selector.iter_from(self.selector_offset)
+    }
+
+    fn hashes(&self) -> &AncestorHashes {
+        &self.hashes
+    }
+}
+
+/// The same, but for state selectors, which can track more exactly what state
+/// do they track.
+#[derive(Clone)]
+#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
+pub struct StateDependency {
+    /// The other dependency fields.
+    pub dep: Dependency,
+    /// The state this dependency is affected by.
+    pub state: ElementState,
+}
+
+impl SelectorMapEntry for StateDependency {
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.dep.selector.iter_from(self.dep.selector_offset)
+    }
+
+    fn hashes(&self) -> &AncestorHashes {
+        &self.dep.hashes
+    }
+}
+
+/// A map where we store invalidations.
+///
+/// This is slightly different to a SelectorMap, in the sense of that the same
+/// selector may appear multiple times.
+///
+/// In particular, we want to lookup as few things as possible to get the fewer
+/// selectors the better, so this looks up by id, class, or looks at the list of
+/// state/other attribute affecting selectors.
+#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
+pub struct InvalidationMap {
+    /// A map from a given class name to all the selectors with that class
+    /// selector.
+    pub class_to_selector: MaybeCaseInsensitiveHashMap<Atom, SelectorMap<Dependency>>,
+    /// A map from a given id to all the selectors with that ID in the
+    /// stylesheets currently applying to the document.
+    pub id_to_selector: MaybeCaseInsensitiveHashMap<Atom, SelectorMap<Dependency>>,
+    /// A map of all the state dependencies.
+    pub state_affecting_selectors: SelectorMap<StateDependency>,
+    /// A map of other attribute affecting selectors.
+    pub other_attribute_affecting_selectors: SelectorMap<Dependency>,
+    /// Whether there are attribute rules of the form `[class~="foo"]` that may
+    /// match. In that case, we need to look at
+    /// `other_attribute_affecting_selectors` too even if only the `class` has
+    /// changed.
+    pub has_class_attribute_selectors: bool,
+    /// Whether there are attribute rules of the form `[id|="foo"]` that may
+    /// match. In that case, we need to look at
+    /// `other_attribute_affecting_selectors` too even if only the `id` has
+    /// changed.
+    pub has_id_attribute_selectors: bool,
+}
+
+impl InvalidationMap {
+    /// Creates an empty `InvalidationMap`.
+    pub fn new() -> Self {
+        Self {
+            class_to_selector: MaybeCaseInsensitiveHashMap::new(),
+            id_to_selector: MaybeCaseInsensitiveHashMap::new(),
+            state_affecting_selectors: SelectorMap::new(),
+            other_attribute_affecting_selectors: SelectorMap::new(),
+            has_class_attribute_selectors: false,
+            has_id_attribute_selectors: false,
+        }
+    }
+
+    /// Returns the number of dependencies stored in the invalidation map.
+    pub fn len(&self) -> usize {
+        self.state_affecting_selectors.len() +
+        self.other_attribute_affecting_selectors.len() +
+        self.id_to_selector.iter().fold(0, |accum, (_, ref v)| {
+            accum + v.len()
+        }) +
+        self.class_to_selector.iter().fold(0, |accum, (_, ref v)| {
+            accum + v.len()
+        })
+    }
+
+    /// Adds a selector to this `InvalidationMap`.
+    pub fn note_selector(
+        &mut self,
+        selector_and_hashes: &SelectorAndHashes<SelectorImpl>,
+        quirks_mode: QuirksMode)
+    {
+        self.collect_invalidations_for(selector_and_hashes, quirks_mode)
+    }
+
+    /// Clears this map, leaving it empty.
+    pub fn clear(&mut self) {
+        self.class_to_selector.clear();
+        self.id_to_selector.clear();
+        self.state_affecting_selectors = SelectorMap::new();
+        self.other_attribute_affecting_selectors = SelectorMap::new();
+        self.has_id_attribute_selectors = false;
+        self.has_class_attribute_selectors = false;
+    }
+
+    fn collect_invalidations_for(
+        &mut self,
+        selector_and_hashes: &SelectorAndHashes<SelectorImpl>,
+        quirks_mode: QuirksMode)
+    {
+        debug!("InvalidationMap::collect_invalidations_for({:?})",
+               selector_and_hashes.selector);
+
+        let mut iter = selector_and_hashes.selector.iter();
+        let mut combinator;
+        let mut index = 0;
+
+        loop {
+            let sequence_start = index;
+
+            let mut compound_visitor = CompoundSelectorDependencyCollector {
+                classes: SmallVec::new(),
+                ids: SmallVec::new(),
+                state: ElementState::empty(),
+                other_attributes: false,
+                has_id_attribute_selectors: false,
+                has_class_attribute_selectors: false,
+            };
+
+            // Visit all the simple selectors in this sequence.
+            //
+            // Note that this works because we can't have combinators nested
+            // inside simple selectors (i.e. in :not() or :-moz-any()).
+            //
+            // If we ever support that we'll need to visit nested complex
+            // selectors as well, in order to mark them as affecting descendants
+            // at least.
+            for ss in &mut iter {
+                ss.visit(&mut compound_visitor);
+                index += 1; // Account for the simple selector.
+            }
+
+            // Reuse the bloom hashes if this is the base selector. Otherwise,
+            // rebuild them.
+            let mut hashes = None;
+
+            let mut get_hashes = || -> AncestorHashes {
+                if hashes.is_none() {
+                    hashes = Some(if sequence_start == 0 {
+                        selector_and_hashes.hashes.clone()
+                    } else {
+                        let seq_iter = selector_and_hashes.selector.iter_from(sequence_start);
+                        AncestorHashes::from_iter(seq_iter)
+                    });
+                }
+                hashes.clone().unwrap()
+            };
+
+            self.has_id_attribute_selectors |= compound_visitor.has_id_attribute_selectors;
+            self.has_class_attribute_selectors |= compound_visitor.has_class_attribute_selectors;
+
+            for class in compound_visitor.classes {
+                self.class_to_selector
+                    .entry(class, quirks_mode)
+                    .or_insert_with(SelectorMap::new)
+                    .insert(Dependency {
+                        selector: selector_and_hashes.selector.clone(),
+                        selector_offset: sequence_start,
+                        hashes: get_hashes(),
+                    }, quirks_mode);
+            }
+
+            for id in compound_visitor.ids {
+                self.id_to_selector
+                    .entry(id, quirks_mode)
+                    .or_insert_with(SelectorMap::new)
+                    .insert(Dependency {
+                        selector: selector_and_hashes.selector.clone(),
+                        selector_offset: sequence_start,
+                        hashes: get_hashes(),
+                    }, quirks_mode);
+            }
+
+            if !compound_visitor.state.is_empty() {
+                self.state_affecting_selectors
+                    .insert(StateDependency {
+                        dep: Dependency {
+                            selector: selector_and_hashes.selector.clone(),
+                            selector_offset: sequence_start,
+                            hashes: get_hashes(),
+                        },
+                        state: compound_visitor.state,
+                    }, quirks_mode);
+            }
+
+            if compound_visitor.other_attributes {
+                self.other_attribute_affecting_selectors
+                    .insert(Dependency {
+                        selector: selector_and_hashes.selector.clone(),
+                        selector_offset: sequence_start,
+                        hashes: get_hashes(),
+                    }, quirks_mode);
+            }
+
+            combinator = iter.next_sequence();
+            if combinator.is_none() {
+                break;
+            }
+
+            index += 1; // Account for the combinator.
+        }
+    }
+}
+
+/// A struct that collects invalidations for a given compound selector.
+struct CompoundSelectorDependencyCollector {
+    /// The state this compound selector is affected by.
+    state: ElementState,
+
+    /// The classes this compound selector is affected by.
+    ///
+    /// NB: This will be often a single class, but could be multiple in
+    /// presence of :not, :-moz-any, .foo.bar.baz, etc.
+    classes: SmallVec<[Atom; 5]>,
+
+    /// The IDs this compound selector is affected by.
+    ///
+    /// NB: This will be almost always a single id, but could be multiple in
+    /// presence of :not, :-moz-any, #foo#bar, etc.
+    ids: SmallVec<[Atom; 5]>,
+
+    /// Whether it affects other attribute-dependent selectors that aren't ID or
+    /// class selectors (NB: We still set this to true in presence of [class] or
+    /// [id] attribute selectors).
+    other_attributes: bool,
+
+    /// Whether there were attribute selectors with the id attribute.
+    has_id_attribute_selectors: bool,
+
+    /// Whether there were attribute selectors with the class attribute.
+    has_class_attribute_selectors: bool,
+}
+
+impl SelectorVisitor for CompoundSelectorDependencyCollector {
+    type Impl = SelectorImpl;
+
+    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
+        #[cfg(feature = "gecko")]
+        use selector_parser::NonTSPseudoClass;
+
+        match *s {
+            Component::ID(ref id) => {
+                self.ids.push(id.clone());
+            }
+            Component::Class(ref class) => {
+                self.classes.push(class.clone());
+            }
+            Component::NonTSPseudoClass(ref pc) => {
+                self.other_attributes |= pc.is_attr_based();
+                self.state |= match *pc {
+                    #[cfg(feature = "gecko")]
+                    NonTSPseudoClass::Dir(ref s) => {
+                        dir_selector_to_state(s)
+                    }
+                    _ => pc.state_flag(),
+                };
+            }
+            _ => {}
+        }
+
+        true
+    }
+
+    fn visit_attribute_selector(
+        &mut self,
+        constraint: &NamespaceConstraint<&Namespace>,
+        _local_name: &LocalName,
+        local_name_lower: &LocalName,
+    ) -> bool {
+        self.other_attributes = true;
+        let may_match_in_no_namespace = match *constraint {
+            NamespaceConstraint::Any => true,
+            NamespaceConstraint::Specific(ref ns) => ns.is_empty(),
+        };
+
+        if may_match_in_no_namespace {
+            self.has_id_attribute_selectors |= *local_name_lower == local_name!("id");
+            self.has_class_attribute_selectors |= *local_name_lower == local_name!("class");
+        }
+
+        true
+    }
+}
diff --git a/components/style/invalidation/element/invalidator.rs b/components/style/invalidation/element/invalidator.rs
new file mode 100644
index 00000000000..b15ef1eb592
--- /dev/null
+++ b/components/style/invalidation/element/invalidator.rs
@@ -0,0 +1,601 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! The struct that takes care of encapsulating all the logic on where and how
+//! element styles need to be invalidated.
+
+use Atom;
+use context::SharedStyleContext;
+use data::ElementData;
+use dom::{TElement, TNode};
+use element_state::ElementState;
+use invalidation::element::element_wrapper::{ElementSnapshot, ElementWrapper};
+use invalidation::element::invalidation_map::*;
+use invalidation::element::restyle_hints::*;
+use selector_map::SelectorMap;
+use selector_parser::SelectorImpl;
+use selectors::attr::CaseSensitivity;
+use selectors::matching::{MatchingContext, MatchingMode, VisitedHandlingMode};
+use selectors::matching::{matches_selector, matches_compound_selector};
+use selectors::matching::CompoundSelectorMatchingResult;
+use selectors::parser::{Combinator, Component, Selector};
+use smallvec::SmallVec;
+use std::fmt;
+
+/// The struct that takes care of encapsulating all the logic on where and how
+/// element styles need to be invalidated.
+pub struct TreeStyleInvalidator<'a, 'b: 'a, E>
+    where E: TElement,
+{
+    element: E,
+    data: Option<&'a mut ElementData>,
+    shared_context: &'a SharedStyleContext<'b>,
+}
+
+type InvalidationVector = SmallVec<[Invalidation; 10]>;
+
+/// An `Invalidation` is a complex selector that describes which elements,
+/// relative to a current element we are processing, must be restyled.
+///
+/// When `offset` points to the right-most compound selector in `selector`,
+/// then the Invalidation `represents` the fact that the current element
+/// must be restyled if the compound selector matches.  Otherwise, if
+/// describes which descendants (or later siblings) must be restyled.
+#[derive(Clone)]
+struct Invalidation {
+    selector: Selector<SelectorImpl>,
+    offset: usize,
+}
+
+impl fmt::Debug for Invalidation {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use cssparser::ToCss;
+
+        f.write_str("Invalidation(")?;
+        for component in self.selector.iter_raw_rev_from(self.offset - 1) {
+            if matches!(*component, Component::Combinator(..)) {
+                break;
+            }
+            component.to_css(f)?;
+        }
+        f.write_str(")")
+    }
+}
+
+/// The result of processing a single invalidation for a given element.
+struct InvalidationResult {
+    /// Whether the element itself was invalidated.
+    invalidated_self: bool,
+    /// Whether the invalidation we've processed is effective for the next
+    /// sibling or descendant after us.
+    effective_for_next: bool,
+}
+
+impl<'a, 'b: 'a, E> TreeStyleInvalidator<'a, 'b, E>
+    where E: TElement,
+{
+    /// Trivially constructs a new `TreeStyleInvalidator`.
+    pub fn new(
+        element: E,
+        data: Option<&'a mut ElementData>,
+        shared_context: &'a SharedStyleContext<'b>,
+    ) -> Self {
+        Self {
+            element: element,
+            data: data,
+            shared_context: shared_context,
+        }
+    }
+
+    /// Perform the invalidation pass.
+    pub fn invalidate(mut self) {
+        debug!("StyleTreeInvalidator::invalidate({:?})", self.element);
+        debug_assert!(self.element.has_snapshot(), "Why bothering?");
+        debug_assert!(self.data.is_some(), "How exactly?");
+
+        let shared_context = self.shared_context;
+
+        let wrapper =
+            ElementWrapper::new(self.element, shared_context.snapshot_map);
+        let state_changes = wrapper.state_changes();
+        let snapshot = wrapper.snapshot().expect("has_snapshot lied");
+
+        if !snapshot.has_attrs() && state_changes.is_empty() {
+            return;
+        }
+
+        let mut classes_removed = SmallVec::<[Atom; 8]>::new();
+        let mut classes_added = SmallVec::<[Atom; 8]>::new();
+        if snapshot.class_changed() {
+            // TODO(emilio): Do this more efficiently!
+            snapshot.each_class(|c| {
+                if !self.element.has_class(c, CaseSensitivity::CaseSensitive) {
+                    classes_removed.push(c.clone())
+                }
+            });
+
+            self.element.each_class(|c| {
+                if !snapshot.has_class(c, CaseSensitivity::CaseSensitive) {
+                    classes_added.push(c.clone())
+                }
+            })
+        }
+
+        let mut id_removed = None;
+        let mut id_added = None;
+        if snapshot.id_changed() {
+            let old_id = snapshot.id_attr();
+            let current_id = self.element.get_id();
+
+            if old_id != current_id {
+                id_removed = old_id;
+                id_added = current_id;
+            }
+        }
+
+        let lookup_element =
+            if self.element.implemented_pseudo_element().is_some() {
+                self.element.pseudo_element_originating_element().unwrap()
+            } else {
+                self.element
+            };
+
+        let mut descendant_invalidations = InvalidationVector::new();
+        let mut sibling_invalidations = InvalidationVector::new();
+        let invalidated_self = {
+            let mut collector = InvalidationCollector {
+                wrapper: wrapper,
+                element: self.element,
+                shared_context: self.shared_context,
+                lookup_element: lookup_element,
+                removed_id: id_removed.as_ref(),
+                classes_removed: &classes_removed,
+                descendant_invalidations: &mut descendant_invalidations,
+                sibling_invalidations: &mut sibling_invalidations,
+                invalidates_self: false,
+            };
+
+            let map = shared_context.stylist.invalidation_map();
+
+            if let Some(ref id) = id_removed {
+                if let Some(deps) = map.id_to_selector.get(id, shared_context.quirks_mode) {
+                    collector.collect_dependencies_in_map(deps)
+                }
+            }
+
+            if let Some(ref id) = id_added {
+                if let Some(deps) = map.id_to_selector.get(id, shared_context.quirks_mode) {
+                    collector.collect_dependencies_in_map(deps)
+                }
+            }
+
+            for class in classes_added.iter().chain(classes_removed.iter()) {
+                if let Some(deps) = map.class_to_selector.get(class, shared_context.quirks_mode) {
+                    collector.collect_dependencies_in_map(deps)
+                }
+            }
+
+            let should_examine_attribute_selector_map =
+                snapshot.other_attr_changed() ||
+                (snapshot.class_changed() && map.has_class_attribute_selectors) ||
+                (snapshot.id_changed() && map.has_id_attribute_selectors);
+
+            if should_examine_attribute_selector_map {
+                collector.collect_dependencies_in_map(
+                    &map.other_attribute_affecting_selectors
+                )
+            }
+
+            if !state_changes.is_empty() {
+                collector.collect_state_dependencies(
+                    &map.state_affecting_selectors,
+                    state_changes,
+                )
+            }
+
+            collector.invalidates_self
+        };
+
+        if invalidated_self {
+            if let Some(ref mut data) = self.data {
+                data.ensure_restyle().hint.insert(RESTYLE_SELF.into());
+            }
+        }
+
+        debug!("Collected invalidations (self: {}): ", invalidated_self);
+        debug!(" > descendants: {:?}", descendant_invalidations);
+        debug!(" > siblings: {:?}", sibling_invalidations);
+        self.invalidate_descendants(&descendant_invalidations);
+        self.invalidate_siblings(&mut sibling_invalidations);
+    }
+
+    /// Go through later DOM siblings, invalidating style as needed using the
+    /// `sibling_invalidations` list.
+    ///
+    /// Returns whether any sibling's style or any sibling descendant's style
+    /// was invalidated.
+    fn invalidate_siblings(
+        &mut self,
+        sibling_invalidations: &mut InvalidationVector,
+    ) -> bool {
+        if sibling_invalidations.is_empty() {
+            return false;
+        }
+
+        let mut current = self.element.next_sibling_element();
+        let mut any_invalidated = false;
+
+        while let Some(sibling) = current {
+            let mut sibling_data = sibling.get_data().map(|d| d.borrow_mut());
+            let sibling_data = sibling_data.as_mut().map(|d| &mut **d);
+
+            let mut sibling_invalidator = TreeStyleInvalidator::new(
+                sibling,
+                sibling_data,
+                self.shared_context
+            );
+
+            let mut invalidations_for_descendants = InvalidationVector::new();
+            any_invalidated |=
+                sibling_invalidator.process_sibling_invalidations(
+                    &mut invalidations_for_descendants,
+                    sibling_invalidations,
+                );
+
+            any_invalidated |=
+                sibling_invalidator.invalidate_descendants(
+                    &invalidations_for_descendants
+                );
+
+            if sibling_invalidations.is_empty() {
+                break;
+            }
+
+            current = sibling.next_sibling_element();
+        }
+
+        any_invalidated
+    }
+
+    /// Given a descendant invalidation list, go through the current element's
+    /// descendants, and invalidate style on them.
+    fn invalidate_descendants(
+        &mut self,
+        invalidations: &InvalidationVector,
+    ) -> bool {
+        if invalidations.is_empty() {
+            return false;
+        }
+
+        debug!("StyleTreeInvalidator::invalidate_descendants({:?})",
+               self.element);
+        debug!(" > {:?}", invalidations);
+
+        match self.data {
+            None => return false,
+            Some(ref data) => {
+                if let Some(restyle) = data.get_restyle() {
+                    if restyle.hint.contains_subtree() {
+                        return false;
+                    }
+                }
+            }
+        }
+
+        let mut sibling_invalidations = InvalidationVector::new();
+
+        let mut any_children = false;
+        for child in self.element.as_node().traversal_children() {
+            let child = match child.as_element() {
+                Some(e) => e,
+                None => continue,
+            };
+
+            let mut child_data = child.get_data().map(|d| d.borrow_mut());
+            let child_data = child_data.as_mut().map(|d| &mut **d);
+
+            let mut child_invalidator = TreeStyleInvalidator::new(
+                child,
+                child_data,
+                self.shared_context
+            );
+
+            let mut invalidations_for_descendants = InvalidationVector::new();
+            any_children |= child_invalidator.process_sibling_invalidations(
+                &mut invalidations_for_descendants,
+                &mut sibling_invalidations,
+            );
+
+            any_children |= child_invalidator.process_descendant_invalidations(
+                invalidations,
+                &mut invalidations_for_descendants,
+                &mut sibling_invalidations,
+            );
+
+            any_children |= child_invalidator.invalidate_descendants(
+                &invalidations_for_descendants
+            );
+        }
+
+        if any_children {
+            unsafe { self.element.set_dirty_descendants() };
+        }
+
+        any_children
+    }
+
+    /// Process the given sibling invalidations coming from our previous
+    /// sibling.
+    ///
+    /// The sibling invalidations are somewhat special because they can be
+    /// modified on the fly. New invalidations may be added and removed.
+    ///
+    /// In particular, all descendants get the same set of invalidations from
+    /// the parent, but the invalidations from a given sibling depend on the
+    /// ones we got from the previous one.
+    ///
+    /// Returns whether invalidated the current element's style.
+    fn process_sibling_invalidations(
+        &mut self,
+        descendant_invalidations: &mut InvalidationVector,
+        sibling_invalidations: &mut InvalidationVector,
+    ) -> bool {
+        let mut i = 0;
+        let mut new_sibling_invalidations = InvalidationVector::new();
+        let mut invalidated_self = false;
+
+        while i < sibling_invalidations.len() {
+            let result = self.process_invalidation(
+                &sibling_invalidations[i],
+                descendant_invalidations,
+                &mut new_sibling_invalidations
+            );
+
+            invalidated_self |= result.invalidated_self;
+            if !result.effective_for_next {
+                sibling_invalidations.remove(i);
+            } else {
+                i += 1;
+            }
+        }
+
+        sibling_invalidations.extend(new_sibling_invalidations.into_iter());
+        invalidated_self
+    }
+
+    /// Process a given invalidation list coming from our parent,
+    /// adding to `descendant_invalidations` and `sibling_invalidations` as
+    /// needed.
+    ///
+    /// Returns whether our style was invalidated as a result.
+    fn process_descendant_invalidations(
+        &mut self,
+        invalidations: &InvalidationVector,
+        descendant_invalidations: &mut InvalidationVector,
+        sibling_invalidations: &mut InvalidationVector,
+    ) -> bool {
+        let mut invalidated = false;
+
+        for invalidation in invalidations {
+            let result = self.process_invalidation(
+                invalidation,
+                descendant_invalidations,
+                sibling_invalidations,
+            );
+
+            invalidated |= result.invalidated_self;
+            if result.effective_for_next {
+                descendant_invalidations.push(invalidation.clone());
+            }
+        }
+
+        invalidated
+    }
+
+    /// Processes a given invalidation, potentially invalidating the style of
+    /// the current element.
+    ///
+    /// Returns whether invalidated the style of the element, and whether the
+    /// invalidation should be effective to subsequent siblings or descendants
+    /// down in the tree.
+    fn process_invalidation(
+        &mut self,
+        invalidation: &Invalidation,
+        descendant_invalidations: &mut InvalidationVector,
+        sibling_invalidations: &mut InvalidationVector
+    ) -> InvalidationResult {
+        debug!("TreeStyleInvalidator::process_invalidation({:?}, {:?})",
+               self.element, invalidation);
+
+        let mut context = MatchingContext::new(MatchingMode::Normal, None,
+                                               self.shared_context.quirks_mode);
+        let matching_result = matches_compound_selector(
+            &invalidation.selector,
+            invalidation.offset,
+            &mut context,
+            &self.element
+        );
+
+        let mut invalidated_self = false;
+        match matching_result {
+            CompoundSelectorMatchingResult::Matched { next_combinator_offset: 0 } => {
+                if let Some(ref mut data) = self.data {
+                    data.ensure_restyle().hint.insert(RESTYLE_SELF.into());
+                    invalidated_self = true;
+                }
+            }
+            CompoundSelectorMatchingResult::Matched { next_combinator_offset } => {
+                let next_combinator =
+                    invalidation.selector.combinator_at(next_combinator_offset);
+
+                if next_combinator.is_ancestor() {
+                    descendant_invalidations.push(Invalidation {
+                        selector: invalidation.selector.clone(),
+                        offset: next_combinator_offset,
+                    })
+                } else {
+                    sibling_invalidations.push(Invalidation {
+                        selector: invalidation.selector.clone(),
+                        offset: next_combinator_offset,
+                    })
+                }
+            }
+            CompoundSelectorMatchingResult::NotMatched => {}
+        }
+
+        // TODO(emilio): For pseudo-elements this should be mostly false, except
+        // for the weird pseudos in <input type="number">.
+        //
+        // We should be able to do better here!
+        let effective_for_next =
+            match invalidation.selector.combinator_at(invalidation.offset) {
+                Combinator::NextSibling |
+                Combinator::Child => false,
+                _ => true,
+            };
+
+        InvalidationResult {
+            invalidated_self: invalidated_self,
+            effective_for_next: effective_for_next,
+        }
+    }
+}
+
+struct InvalidationCollector<'a, 'b: 'a, E>
+    where E: TElement,
+{
+    element: E,
+    wrapper: ElementWrapper<'b, E>,
+    shared_context: &'a SharedStyleContext<'b>,
+    lookup_element: E,
+    removed_id: Option<&'a Atom>,
+    classes_removed: &'a SmallVec<[Atom; 8]>,
+    descendant_invalidations: &'a mut InvalidationVector,
+    sibling_invalidations: &'a mut InvalidationVector,
+    invalidates_self: bool,
+}
+
+impl<'a, 'b: 'a, E> InvalidationCollector<'a, 'b, E>
+    where E: TElement,
+{
+    fn collect_dependencies_in_map(
+        &mut self,
+        map: &SelectorMap<Dependency>,
+    ) {
+        map.lookup_with_additional(
+            self.lookup_element,
+            self.shared_context.quirks_mode,
+            self.removed_id,
+            self.classes_removed,
+            &mut |dependency| {
+                self.scan_dependency(dependency);
+                true
+            },
+        );
+    }
+    fn collect_state_dependencies(
+        &mut self,
+        map: &SelectorMap<StateDependency>,
+        state_changes: ElementState,
+    ) {
+        map.lookup_with_additional(
+            self.lookup_element,
+            self.shared_context.quirks_mode,
+            self.removed_id,
+            self.classes_removed,
+            &mut |dependency| {
+                if !dependency.state.intersects(state_changes) {
+                    return true;
+                }
+                self.scan_dependency(&dependency.dep);
+                true
+            },
+        );
+    }
+
+    fn scan_dependency(&mut self, dependency: &Dependency) {
+        debug!("TreeStyleInvalidator::scan_dependency({:?}, {:?}, {})",
+               self.element,
+               dependency,
+               is_visited_dependent);
+
+        if !self.dependency_may_be_relevant(dependency) {
+            return;
+        }
+
+        // TODO(emilio): Add a bloom filter here?
+        //
+        // If we decide to do so, we can't use the bloom filter for snapshots,
+        // given that arbitrary elements in the parent chain may have mutated
+        // their id's/classes, which means that they won't be in the filter, and
+        // as such we may fast-reject selectors incorrectly.
+        //
+        // We may be able to improve this if we record as we go down the tree
+        // whether any parent had a snapshot, and whether those snapshots were
+        // taken due to an element class/id change, but it's not clear it'd be
+        // worth it.
+        let mut now_context =
+            MatchingContext::new_for_visited(MatchingMode::Normal, None,
+                                             VisitedHandlingMode::AllLinksUnvisited,
+                                             self.shared_context.quirks_mode);
+        let mut then_context =
+            MatchingContext::new_for_visited(MatchingMode::Normal, None,
+                                             VisitedHandlingMode::AllLinksUnvisited,
+                                             self.shared_context.quirks_mode);
+
+        let matched_then =
+            matches_selector(&dependency.selector,
+                             dependency.selector_offset,
+                             &dependency.hashes,
+                             &self.wrapper,
+                             &mut then_context,
+                             &mut |_, _| {});
+        let matches_now =
+            matches_selector(&dependency.selector,
+                             dependency.selector_offset,
+                             &dependency.hashes,
+                             &self.element,
+                             &mut now_context,
+                             &mut |_, _| {});
+
+        // Check for mismatches in both the match result and also the status
+        // of whether a relevant link was found.
+        if matched_then != matches_now ||
+           then_context.relevant_link_found != now_context.relevant_link_found {
+            self.note_dependency(dependency);
+        }
+    }
+
+    fn note_dependency(&mut self, dependency: &Dependency) {
+        if dependency.affects_self() {
+            self.invalidates_self = true;
+        }
+
+        if dependency.affects_descendants() {
+            debug_assert_ne!(dependency.selector_offset, 0);
+            debug_assert!(!dependency.affects_later_siblings());
+            self.descendant_invalidations.push(Invalidation {
+                selector: dependency.selector.clone(),
+                offset: dependency.selector_offset,
+            });
+        } else if dependency.affects_later_siblings() {
+            debug_assert_ne!(dependency.selector_offset, 0);
+            self.sibling_invalidations.push(Invalidation {
+                selector: dependency.selector.clone(),
+                offset: dependency.selector_offset,
+            });
+        }
+    }
+
+    /// Returns whether `dependency` may cause us to invalidate the style of
+    /// more elements than what we've already invalidated.
+    fn dependency_may_be_relevant(&self, dependency: &Dependency) -> bool {
+        if dependency.affects_descendants() || dependency.affects_later_siblings() {
+            return true;
+        }
+
+        debug_assert!(dependency.affects_self());
+        !self.invalidates_self
+    }
+}
diff --git a/components/style/invalidation/element/mod.rs b/components/style/invalidation/element/mod.rs
new file mode 100644
index 00000000000..61aae2ffcd2
--- /dev/null
+++ b/components/style/invalidation/element/mod.rs
@@ -0,0 +1,10 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Invalidation of element styles due to attribute or style changes.
+
+pub mod element_wrapper;
+pub mod invalidation_map;
+pub mod invalidator;
+pub mod restyle_hints;
diff --git a/components/style/invalidation/element/restyle_hints.rs b/components/style/invalidation/element/restyle_hints.rs
new file mode 100644
index 00000000000..786c267f203
--- /dev/null
+++ b/components/style/invalidation/element/restyle_hints.rs
@@ -0,0 +1,212 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Restyle hints: an optimization to avoid unnecessarily matching selectors.
+
+#[cfg(feature = "gecko")]
+use gecko_bindings::structs::nsRestyleHint;
+
+bitflags! {
+    /// The kind of restyle we need to do for a given element.
+    pub flags RestyleHint: u8 {
+        /// Do a selector match of the element.
+        const RESTYLE_SELF = 1 << 0,
+
+        /// Do a selector match of the element's descendants.
+        const RESTYLE_DESCENDANTS = 1 << 1,
+
+        /// Recascade the current element.
+        const RECASCADE_SELF = 1 << 2,
+
+        /// Recascade all descendant elements.
+        const RECASCADE_DESCENDANTS = 1 << 3,
+
+        /// Replace the style data coming from CSS transitions without updating
+        /// any other style data. This hint is only processed in animation-only
+        /// traversal which is prior to normal traversal.
+        const RESTYLE_CSS_TRANSITIONS = 1 << 4,
+
+        /// Replace the style data coming from CSS animations without updating
+        /// any other style data. This hint is only processed in animation-only
+        /// traversal which is prior to normal traversal.
+        const RESTYLE_CSS_ANIMATIONS = 1 << 5,
+
+        /// Don't re-run selector-matching on the element, only the style
+        /// attribute has changed, and this change didn't have any other
+        /// dependencies.
+        const RESTYLE_STYLE_ATTRIBUTE = 1 << 6,
+
+        /// Replace the style data coming from SMIL animations without updating
+        /// any other style data. This hint is only processed in animation-only
+        /// traversal which is prior to normal traversal.
+        const RESTYLE_SMIL = 1 << 7,
+    }
+}
+
+impl RestyleHint {
+    /// Creates a new `RestyleHint` indicating that the current element and all
+    /// its descendants must be fully restyled.
+    pub fn restyle_subtree() -> Self {
+        RESTYLE_SELF | RESTYLE_DESCENDANTS
+    }
+
+    /// Creates a new `RestyleHint` indicating that the current element and all
+    /// its descendants must be recascaded.
+    pub fn recascade_subtree() -> Self {
+        RECASCADE_SELF | RECASCADE_DESCENDANTS
+    }
+
+    /// Returns a new `CascadeHint` appropriate for children of the current
+    /// element.
+    pub fn propagate_for_non_animation_restyle(&self) -> Self {
+        if self.contains(RESTYLE_DESCENDANTS) {
+            return Self::restyle_subtree()
+        }
+        if self.contains(RECASCADE_DESCENDANTS) {
+            return Self::recascade_subtree()
+        }
+        Self::empty()
+    }
+
+    /// Creates a new `RestyleHint` that indicates the element must be
+    /// recascaded.
+    pub fn recascade_self() -> Self {
+        RECASCADE_SELF
+    }
+
+    /// Returns a hint that contains all the replacement hints.
+    pub fn replacements() -> Self {
+        RESTYLE_STYLE_ATTRIBUTE | Self::for_animations()
+    }
+
+    /// The replacements for the animation cascade levels.
+    #[inline]
+    pub fn for_animations() -> Self {
+        RESTYLE_SMIL | RESTYLE_CSS_ANIMATIONS | RESTYLE_CSS_TRANSITIONS
+    }
+
+    /// Returns whether the hint specifies that some work must be performed on
+    /// the current element.
+    #[inline]
+    pub fn affects_self(&self) -> bool {
+        self.intersects(RESTYLE_SELF | RECASCADE_SELF | Self::replacements())
+    }
+
+    /// Returns whether the hint specifies that the currently element must be
+    /// recascaded.
+    pub fn has_recascade_self(&self) -> bool {
+        self.contains(RECASCADE_SELF)
+    }
+
+    /// Returns whether the hint specifies that an animation cascade level must
+    /// be replaced.
+    #[inline]
+    pub fn has_animation_hint(&self) -> bool {
+        self.intersects(Self::for_animations())
+    }
+
+    /// Returns whether the hint specifies some restyle work other than an
+    /// animation cascade level replacement.
+    #[inline]
+    pub fn has_non_animation_hint(&self) -> bool {
+        !(*self & !Self::for_animations()).is_empty()
+    }
+
+    /// Returns whether the hint specifies that selector matching must be re-run
+    /// for the element.
+    #[inline]
+    pub fn match_self(&self) -> bool {
+        self.intersects(RESTYLE_SELF)
+    }
+
+    /// Returns whether the hint specifies that some cascade levels must be
+    /// replaced.
+    #[inline]
+    pub fn has_replacements(&self) -> bool {
+        self.intersects(Self::replacements())
+    }
+
+    /// Removes all of the animation-related hints.
+    #[inline]
+    pub fn remove_animation_hints(&mut self) {
+        self.remove(Self::for_animations());
+
+        // While RECASCADE_SELF is not animation-specific, we only ever add and
+        // process it during traversal.  If we are here, removing animation
+        // hints, then we are in an animation-only traversal, and we know that
+        // any RECASCADE_SELF flag must have been set due to changes in
+        // inherited values after restyling for animations, and thus we want to
+        // remove it so that we don't later try to restyle the element during a
+        // normal restyle.  (We could have separate RECASCADE_SELF_NORMAL and
+        // RECASCADE_SELF_ANIMATIONS flags to make it clear, but this isn't
+        // currently necessary.)
+        self.remove(RECASCADE_SELF);
+    }
+}
+
+#[cfg(feature = "gecko")]
+impl From<nsRestyleHint> for RestyleHint {
+    fn from(raw: nsRestyleHint) -> Self {
+        use gecko_bindings::structs::nsRestyleHint_eRestyle_ForceDescendants as eRestyle_ForceDescendants;
+        use gecko_bindings::structs::nsRestyleHint_eRestyle_LaterSiblings as eRestyle_LaterSiblings;
+        use gecko_bindings::structs::nsRestyleHint_eRestyle_Self as eRestyle_Self;
+        use gecko_bindings::structs::nsRestyleHint_eRestyle_SomeDescendants as eRestyle_SomeDescendants;
+        use gecko_bindings::structs::nsRestyleHint_eRestyle_Subtree as eRestyle_Subtree;
+
+        let mut hint = RestyleHint::empty();
+
+        debug_assert!(raw.0 & eRestyle_LaterSiblings.0 == 0,
+                      "Handle later siblings manually if necessary plz.");
+
+        if (raw.0 & (eRestyle_Self.0 | eRestyle_Subtree.0)) != 0 {
+            hint.insert(RESTYLE_SELF);
+        }
+
+        if (raw.0 & (eRestyle_Subtree.0 | eRestyle_SomeDescendants.0)) != 0 {
+            hint.insert(RESTYLE_DESCENDANTS);
+        }
+
+        if (raw.0 & eRestyle_ForceDescendants.0) != 0 {
+            hint.insert(RECASCADE_DESCENDANTS);
+        }
+
+        hint.insert(RestyleHint::from_bits_truncate(raw.0 as u8));
+
+        hint
+    }
+}
+
+#[cfg(feature = "servo")]
+impl ::heapsize::HeapSizeOf for RestyleHint {
+    fn heap_size_of_children(&self) -> usize { 0 }
+}
+
+/// Asserts that all replacement hints have a matching nsRestyleHint value.
+#[cfg(feature = "gecko")]
+#[inline]
+pub fn assert_restyle_hints_match() {
+    use gecko_bindings::structs;
+
+    macro_rules! check_restyle_hints {
+        ( $( $a:ident => $b:ident ),*, ) => {
+            if cfg!(debug_assertions) {
+                let mut replacements = RestyleHint::replacements();
+                $(
+                    assert_eq!(structs::$a.0 as usize, $b.bits() as usize, stringify!($b));
+                    replacements.remove($b);
+                )*
+                assert_eq!(replacements, RestyleHint::empty(),
+                           "all RestyleHint replacement bits should have an \
+                            assertion");
+            }
+        }
+    }
+
+    check_restyle_hints! {
+        nsRestyleHint_eRestyle_CSSTransitions => RESTYLE_CSS_TRANSITIONS,
+        nsRestyleHint_eRestyle_CSSAnimations => RESTYLE_CSS_ANIMATIONS,
+        nsRestyleHint_eRestyle_StyleAttribute => RESTYLE_STYLE_ATTRIBUTE,
+        nsRestyleHint_eRestyle_StyleAttribute_Animations => RESTYLE_SMIL,
+    }
+}
diff --git a/components/style/invalidation/mod.rs b/components/style/invalidation/mod.rs
index 4b7f9c3cd65..211c39ad2b4 100644
--- a/components/style/invalidation/mod.rs
+++ b/components/style/invalidation/mod.rs
@@ -4,5 +4,6 @@
 
 //! Different bits of code related to invalidating style.
 
+pub mod element;
 pub mod media_queries;
 pub mod stylesheets;
diff --git a/components/style/lib.rs b/components/style/lib.rs
index 7c5945e3d79..192ee3f242f 100644
--- a/components/style/lib.rs
+++ b/components/style/lib.rs
@@ -117,7 +117,6 @@ pub mod matching;
 pub mod media_queries;
 pub mod parallel;
 pub mod parser;
-pub mod restyle_hints;
 pub mod rule_tree;
 pub mod scoped_tls;
 pub mod selector_map;
diff --git a/components/style/matching.rs b/components/style/matching.rs
index d93eec27026..1d57956efc5 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -13,13 +13,14 @@ use context::{SelectorFlagsMap, SharedStyleContext, StyleContext};
 use data::{ComputedStyle, ElementData, RestyleData};
 use dom::{TElement, TNode};
 use font_metrics::FontMetricsProvider;
+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 log::LogLevel::Trace;
 use properties::{ALLOW_SET_ROOT_FONT_SIZE, SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP};
 use properties::{AnimationRules, CascadeFlags, ComputedValues};
 use properties::{VISITED_DEPENDENT_ONLY, cascade};
 use properties::longhands::display::computed_value as display;
-use restyle_hints::{RESTYLE_CSS_ANIMATIONS, RESTYLE_CSS_TRANSITIONS, RestyleReplacements};
-use restyle_hints::{RESTYLE_STYLE_ATTRIBUTE, RESTYLE_SMIL};
 use rule_tree::{CascadeLevel, StrongRuleNode};
 use selector_parser::{PseudoElement, RestyleDamage, SelectorImpl};
 use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode, StyleRelations};
@@ -1276,11 +1277,12 @@ pub trait MatchMethods : TElement {
     /// the rule tree.
     ///
     /// Returns true if an !important rule was replaced.
-    fn replace_rules(&self,
-                     replacements: RestyleReplacements,
-                     context: &StyleContext<Self>,
-                     data: &mut ElementData)
-                     -> bool {
+    fn replace_rules(
+        &self,
+        replacements: RestyleHint,
+        context: &StyleContext<Self>,
+        data: &mut ElementData
+    ) -> bool {
         let mut result = false;
         result |= self.replace_rules_internal(replacements, context, data,
                                               CascadeVisitedMode::Unvisited);
@@ -1295,15 +1297,19 @@ pub trait MatchMethods : TElement {
     /// the rule tree, for a specific visited mode.
     ///
     /// Returns true if an !important rule was replaced.
-    fn replace_rules_internal(&self,
-                              replacements: RestyleReplacements,
-                              context: &StyleContext<Self>,
-                              data: &mut ElementData,
-                              cascade_visited: CascadeVisitedMode)
-                              -> bool {
+    fn replace_rules_internal(
+        &self,
+        replacements: RestyleHint,
+        context: &StyleContext<Self>,
+        data: &mut ElementData,
+        cascade_visited: CascadeVisitedMode
+    ) -> bool {
         use properties::PropertyDeclarationBlock;
         use shared_lock::Locked;
 
+        debug_assert!(replacements.intersects(RestyleHint::replacements()) &&
+                      (replacements & !RestyleHint::replacements()).is_empty());
+
         let element_styles = &mut data.styles_mut();
         let primary_rules = match cascade_visited.get_rules_mut(&mut element_styles.primary) {
             Some(r) => r,
@@ -1344,7 +1350,7 @@ pub trait MatchMethods : TElement {
         //
         // Non-animation restyle hints will be processed in a subsequent
         // normal traversal.
-        if replacements.intersects(RestyleReplacements::for_animations()) {
+        if replacements.intersects(RestyleHint::for_animations()) {
             debug_assert!(context.shared.traversal_flags.for_animation_only());
 
             if replacements.contains(RESTYLE_SMIL) {
diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs
deleted file mode 100644
index 0bdfdd4039b..00000000000
--- a/components/style/restyle_hints.rs
+++ /dev/null
@@ -1,1276 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-//! Restyle hints: an optimization to avoid unnecessarily matching selectors.
-
-#![deny(missing_docs)]
-
-use Atom;
-use CaseSensitivityExt;
-use LocalName;
-use Namespace;
-use context::{SharedStyleContext, ThreadLocalStyleContext, QuirksMode};
-use dom::TElement;
-use element_state::*;
-#[cfg(feature = "gecko")]
-use gecko_bindings::structs::nsRestyleHint;
-#[cfg(feature = "servo")]
-use heapsize::HeapSizeOf;
-use selector_map::{SelectorMap, SelectorMapEntry};
-use selector_parser::{NonTSPseudoClass, PseudoElement, SelectorImpl, Snapshot, SnapshotMap, AttrValue};
-use selectors::Element;
-use selectors::attr::{AttrSelectorOperation, NamespaceConstraint, CaseSensitivity};
-use selectors::matching::{ElementSelectorFlags, LocalMatchingContext, MatchingContext, MatchingMode};
-use selectors::matching::{RelevantLinkStatus, VisitedHandlingMode, matches_selector};
-use selectors::parser::{AncestorHashes, Combinator, Component};
-use selectors::parser::{Selector, SelectorAndHashes, SelectorIter, SelectorMethods};
-use selectors::visitor::SelectorVisitor;
-use smallvec::SmallVec;
-use std::cell::Cell;
-use std::clone::Clone;
-use std::cmp;
-use std::fmt;
-
-/// When the ElementState of an element (like IN_HOVER_STATE) changes,
-/// certain pseudo-classes (like :hover) may require us to restyle that
-/// element, its siblings, and/or its descendants. Similarly, when various
-/// attributes of an element change, we may also need to restyle things with
-/// id, class, and attribute selectors. Doing this conservatively is
-/// expensive, and so we use RestyleHints to short-circuit work we know is
-/// unnecessary.
-#[derive(Debug, Clone, PartialEq)]
-pub struct RestyleHint {
-    /// Depths at which selector matching must be re-run.
-    match_under_self: RestyleDepths,
-
-    /// Rerun selector matching on all later siblings of the element and all
-    /// of their descendants.
-    match_later_siblings: bool,
-
-    /// Whether the current element and/or all descendants must be recascade.
-    recascade: CascadeHint,
-
-    /// Levels of the cascade whose rule nodes should be recomputed and
-    /// replaced.
-    pub replacements: RestyleReplacements,
-}
-
-bitflags! {
-    /// Cascade levels that can be updated for an element by simply replacing
-    /// their rule node.
-    ///
-    /// Note that the bit values here must be kept in sync with the Gecko
-    /// nsRestyleHint values.  If you add more bits with matching values,
-    /// please add assertions to assert_restyle_hints_match below.
-    pub flags RestyleReplacements: u8 {
-        /// Replace the style data coming from CSS transitions without updating
-        /// any other style data. This hint is only processed in animation-only
-        /// traversal which is prior to normal traversal.
-        const RESTYLE_CSS_TRANSITIONS = 0x10,
-
-        /// Replace the style data coming from CSS animations without updating
-        /// any other style data. This hint is only processed in animation-only
-        /// traversal which is prior to normal traversal.
-        const RESTYLE_CSS_ANIMATIONS = 0x20,
-
-        /// Don't re-run selector-matching on the element, only the style
-        /// attribute has changed, and this change didn't have any other
-        /// dependencies.
-        const RESTYLE_STYLE_ATTRIBUTE = 0x40,
-
-        /// Replace the style data coming from SMIL animations without updating
-        /// any other style data. This hint is only processed in animation-only
-        /// traversal which is prior to normal traversal.
-        const RESTYLE_SMIL = 0x80,
-    }
-}
-
-/// Eight bit wide bitfield representing depths of a DOM subtree's descendants,
-/// used to represent which elements must have selector matching re-run on them.
-///
-/// The least significant bit indicates that selector matching must be re-run
-/// for the element itself, the second least significant bit for the element's
-/// children, the third its grandchildren, and so on.  If the most significant
-/// bit it set, it indicates that that selector matching must be re-run for
-/// elements at that depth and all of their descendants.
-#[derive(Debug, Clone, Copy, PartialEq)]
-struct RestyleDepths(u8);
-
-impl RestyleDepths {
-    /// Returns a `RestyleDepths` representing no element depths.
-    fn empty() -> Self {
-        RestyleDepths(0)
-    }
-
-    /// Returns a `RestyleDepths` representing the current element depth.
-    fn for_self() -> Self {
-        RestyleDepths(0x01)
-    }
-
-    /// Returns a `RestyleDepths` representing the depths of all descendants of
-    /// the current element.
-    fn for_descendants() -> Self {
-        RestyleDepths(0xfe)
-    }
-
-    /// Returns a `RestyleDepths` representing the current element depth and the
-    /// depths of all the current element's descendants.
-    fn for_self_and_descendants() -> Self {
-        RestyleDepths(0xff)
-    }
-
-    /// Returns a `RestyleDepths` representing the specified depth, where zero
-    /// is the current element depth, one is its children's depths, etc.
-    fn for_depth(depth: u32) -> Self {
-        RestyleDepths(1u8 << cmp::min(depth, 7))
-    }
-
-    /// Returns whether this `RestyleDepths` represents the current element
-    /// depth and the depths of all the current element's descendants.
-    fn is_self_and_descendants(&self) -> bool {
-        self.0 == 0xff
-    }
-
-    /// Returns whether this `RestyleDepths` includes any element depth.
-    fn is_any(&self) -> bool {
-        self.0 != 0
-    }
-
-    /// Returns whether this `RestyleDepths` includes the current element depth.
-    fn has_self(&self) -> bool {
-        (self.0 & 0x01) != 0
-    }
-
-    /// Returns a new `RestyleDepths` with all depth values represented by this
-    /// `RestyleDepths` reduced by one.
-    fn propagate(&self) -> Self {
-        RestyleDepths((self.0 >> 1) | (self.0 & 0x80))
-    }
-
-    /// Returns a new `RestyleDepths` that represents the union of the depths
-    /// from `self` and `other`.
-    fn insert(&mut self, other: RestyleDepths) {
-        self.0 |= other.0;
-    }
-
-    /// Returns whether this `RestyleDepths` includes all depths represented
-    /// by `other`.
-    fn contains(&self, other: RestyleDepths) -> bool {
-        (self.0 & other.0) == other.0
-    }
-}
-
-bitflags! {
-    /// Flags representing whether the current element or its descendants
-    /// must be recascaded.
-    ///
-    /// FIXME(bholley): This should eventually become more fine-grained.
-    pub flags CascadeHint: u8 {
-        /// Recascade the current element.
-        const RECASCADE_SELF = 0x01,
-        /// Recascade all descendant elements.
-        const RECASCADE_DESCENDANTS = 0x02,
-    }
-}
-
-impl CascadeHint {
-    /// Creates a new `CascadeHint` indicating that the current element and all
-    /// its descendants must be recascaded.
-    fn subtree() -> CascadeHint {
-        RECASCADE_SELF | RECASCADE_DESCENDANTS
-    }
-
-    /// Returns a new `CascadeHint` appropriate for children of the current
-    /// element.
-    fn propagate(&self) -> Self {
-        if self.contains(RECASCADE_DESCENDANTS) {
-            CascadeHint::subtree()
-        } else {
-            CascadeHint::empty()
-        }
-    }
-}
-
-/// Asserts that all RestyleReplacements have a matching nsRestyleHint value.
-#[cfg(feature = "gecko")]
-#[inline]
-pub fn assert_restyle_hints_match() {
-    use gecko_bindings::structs;
-
-    macro_rules! check_restyle_hints {
-        ( $( $a:ident => $b:ident ),*, ) => {
-            if cfg!(debug_assertions) {
-                let mut replacements = RestyleReplacements::all();
-                $(
-                    assert_eq!(structs::$a.0 as usize, $b.bits() as usize, stringify!($b));
-                    replacements.remove($b);
-                )*
-                assert_eq!(replacements, RestyleReplacements::empty(),
-                           "all RestyleReplacements bits should have an assertion");
-            }
-        }
-    }
-
-    check_restyle_hints! {
-        nsRestyleHint_eRestyle_CSSTransitions => RESTYLE_CSS_TRANSITIONS,
-        nsRestyleHint_eRestyle_CSSAnimations => RESTYLE_CSS_ANIMATIONS,
-        nsRestyleHint_eRestyle_StyleAttribute => RESTYLE_STYLE_ATTRIBUTE,
-        nsRestyleHint_eRestyle_StyleAttribute_Animations => RESTYLE_SMIL,
-    }
-}
-
-impl RestyleHint {
-    /// Creates a new, empty `RestyleHint`, which represents no restyling work
-    /// needs to be done.
-    #[inline]
-    pub fn empty() -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::empty(),
-            match_later_siblings: false,
-            recascade: CascadeHint::empty(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates selector matching must be
-    /// re-run on the element.
-    #[inline]
-    pub fn for_self() -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::for_self(),
-            match_later_siblings: false,
-            recascade: CascadeHint::empty(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates selector matching must be
-    /// re-run on all of the element's descendants.
-    #[inline]
-    pub fn descendants() -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::for_descendants(),
-            match_later_siblings: false,
-            recascade: CascadeHint::empty(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates selector matching must be
-    /// re-run on the descendants of element at the specified depth, where 0
-    /// indicates the element itself, 1 is its children, 2 its grandchildren,
-    /// etc.
-    #[inline]
-    pub fn descendants_at_depth(depth: u32) -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::for_depth(depth),
-            match_later_siblings: false,
-            recascade: CascadeHint::empty(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates selector matching must be
-    /// re-run on all of the element's later siblings and their descendants.
-    #[inline]
-    pub fn later_siblings() -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::empty(),
-            match_later_siblings: true,
-            recascade: CascadeHint::empty(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates selector matching must be
-    /// re-run on the element and all of its descendants.
-    #[inline]
-    pub fn subtree() -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::for_self_and_descendants(),
-            match_later_siblings: false,
-            recascade: CascadeHint::empty(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates selector matching must be
-    /// re-run on the element, its descendants, its later siblings, and
-    /// their descendants.
-    #[inline]
-    pub fn subtree_and_later_siblings() -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::for_self_and_descendants(),
-            match_later_siblings: true,
-            recascade: CascadeHint::empty(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates the specified rule node
-    /// replacements must be performed on the element.
-    #[inline]
-    pub fn for_replacements(replacements: RestyleReplacements) -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::empty(),
-            match_later_siblings: false,
-            recascade: CascadeHint::empty(),
-            replacements: replacements,
-        }
-    }
-
-    /// Creates a new `RestyleHint` that indicates the element must be
-    /// recascaded.
-    pub fn recascade_self() -> Self {
-        RestyleHint {
-            match_under_self: RestyleDepths::empty(),
-            match_later_siblings: false,
-            recascade: RECASCADE_SELF,
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Returns whether this `RestyleHint` represents no needed restyle work.
-    #[inline]
-    pub fn is_empty(&self) -> bool {
-        *self == RestyleHint::empty()
-    }
-
-    /// Returns whether this `RestyleHint` represents the maximum possible
-    /// restyle work, and thus any `insert()` calls will have no effect.
-    #[inline]
-    pub fn is_maximum(&self) -> bool {
-        self.match_under_self.is_self_and_descendants() &&
-            self.match_later_siblings &&
-            self.recascade.is_all() &&
-            self.replacements.is_all()
-    }
-
-    /// Returns whether the hint specifies that some work must be performed on
-    /// the current element.
-    #[inline]
-    pub fn affects_self(&self) -> bool {
-        self.match_self() || self.has_recascade_self() || !self.replacements.is_empty()
-    }
-
-    /// Returns whether the hint specifies that the currently element must be
-    /// recascaded.
-    pub fn has_recascade_self(&self) -> bool {
-        self.recascade.contains(RECASCADE_SELF)
-    }
-
-    /// Returns whether the hint specifies that later siblings must be restyled.
-    #[inline]
-    pub fn affects_later_siblings(&self) -> bool {
-        self.match_later_siblings
-    }
-
-    /// Returns whether the hint specifies that an animation cascade level must
-    /// be replaced.
-    #[inline]
-    pub fn has_animation_hint(&self) -> bool {
-        self.replacements.intersects(RestyleReplacements::for_animations())
-    }
-
-    /// Returns whether the hint specifies some restyle work other than an
-    /// animation cascade level replacement.
-    #[inline]
-    pub fn has_non_animation_hint(&self) -> bool {
-        self.match_under_self.is_any() || self.match_later_siblings ||
-            !self.recascade.is_empty() ||
-            self.replacements.contains(RESTYLE_STYLE_ATTRIBUTE)
-    }
-
-    /// Returns whether the hint specifies that selector matching must be re-run
-    /// for the element.
-    #[inline]
-    pub fn match_self(&self) -> bool {
-        self.match_under_self.has_self()
-    }
-
-    /// Returns whether the hint specifies that some cascade levels must be
-    /// replaced.
-    #[inline]
-    pub fn has_replacements(&self) -> bool {
-        !self.replacements.is_empty()
-    }
-
-    /// Returns a new `RestyleHint` appropriate for children of the current
-    /// element.
-    #[inline]
-    pub fn propagate_for_non_animation_restyle(&self) -> Self {
-        RestyleHint {
-            match_under_self: self.match_under_self.propagate(),
-            match_later_siblings: false,
-            recascade: self.recascade.propagate(),
-            replacements: RestyleReplacements::empty(),
-        }
-    }
-
-    /// Removes all of the animation-related hints.
-    #[inline]
-    pub fn remove_animation_hints(&mut self) {
-        self.replacements.remove(RestyleReplacements::for_animations());
-
-        // While RECASCADE_SELF is not animation-specific, we only ever add and
-        // process it during traversal.  If we are here, removing animation
-        // hints, then we are in an animation-only traversal, and we know that
-        // any RECASCADE_SELF flag must have been set due to changes in
-        // inherited values after restyling for animations, and thus we
-        // want to remove it so that we don't later try to restyle the element
-        // during a normal restyle.  (We could have separate
-        // RECASCADE_SELF_NORMAL and RECASCADE_SELF_ANIMATIONS flags to make it
-        // clear, but this isn't currently necessary.)
-        self.recascade.remove(RECASCADE_SELF);
-    }
-
-    /// Removes the later siblings hint, and returns whether it was present.
-    pub fn remove_later_siblings_hint(&mut self) -> bool {
-        let later_siblings = self.match_later_siblings;
-        self.match_later_siblings = false;
-        later_siblings
-    }
-
-    /// Unions the specified `RestyleHint` into this one.
-    #[inline]
-    pub fn insert_from(&mut self, other: &Self) {
-        self.match_under_self.insert(other.match_under_self);
-        self.match_later_siblings |= other.match_later_siblings;
-        self.recascade.insert(other.recascade);
-        self.replacements.insert(other.replacements);
-    }
-
-    /// Unions the specified `RestyleHint` into this one.
-    #[inline]
-    pub fn insert(&mut self, other: Self) {
-        // A later patch should make it worthwhile to have an insert() function
-        // that consumes its argument.
-        self.insert_from(&other)
-    }
-
-    /// Inserts the specified `CascadeHint`.
-    #[inline]
-    pub fn insert_cascade_hint(&mut self, cascade_hint: CascadeHint) {
-        self.recascade.insert(cascade_hint);
-    }
-
-    /// Returns whether this `RestyleHint` represents at least as much restyle
-    /// work as the specified one.
-    #[inline]
-    pub fn contains(&self, other: &Self) -> bool {
-        self.match_under_self.contains(other.match_under_self) &&
-        (self.match_later_siblings & other.match_later_siblings) == other.match_later_siblings &&
-        self.recascade.contains(other.recascade) &&
-        self.replacements.contains(other.replacements)
-    }
-}
-
-impl RestyleReplacements {
-    /// The replacements for the animation cascade levels.
-    #[inline]
-    pub fn for_animations() -> Self {
-        RESTYLE_SMIL | RESTYLE_CSS_ANIMATIONS | RESTYLE_CSS_TRANSITIONS
-    }
-}
-
-#[cfg(feature = "gecko")]
-impl From<nsRestyleHint> for RestyleReplacements {
-    fn from(raw: nsRestyleHint) -> Self {
-        Self::from_bits_truncate(raw.0 as u8)
-    }
-}
-
-#[cfg(feature = "gecko")]
-impl From<nsRestyleHint> for RestyleHint {
-    fn from(raw: nsRestyleHint) -> Self {
-        use gecko_bindings::structs::nsRestyleHint_eRestyle_ForceDescendants as eRestyle_ForceDescendants;
-        use gecko_bindings::structs::nsRestyleHint_eRestyle_LaterSiblings as eRestyle_LaterSiblings;
-        use gecko_bindings::structs::nsRestyleHint_eRestyle_Self as eRestyle_Self;
-        use gecko_bindings::structs::nsRestyleHint_eRestyle_SomeDescendants as eRestyle_SomeDescendants;
-        use gecko_bindings::structs::nsRestyleHint_eRestyle_Subtree as eRestyle_Subtree;
-
-        let mut match_under_self = RestyleDepths::empty();
-        if (raw.0 & (eRestyle_Self.0 | eRestyle_Subtree.0)) != 0 {
-            match_under_self.insert(RestyleDepths::for_self());
-        }
-        if (raw.0 & (eRestyle_Subtree.0 | eRestyle_SomeDescendants.0)) != 0 {
-            match_under_self.insert(RestyleDepths::for_descendants());
-        }
-
-        let mut recascade = CascadeHint::empty();
-        if (raw.0 & eRestyle_ForceDescendants.0) != 0 {
-            recascade.insert(CascadeHint::subtree())
-        }
-
-        RestyleHint {
-            match_under_self: match_under_self,
-            match_later_siblings: (raw.0 & eRestyle_LaterSiblings.0) != 0,
-            recascade: recascade,
-            replacements: raw.into(),
-        }
-    }
-}
-
-#[cfg(feature = "servo")]
-impl HeapSizeOf for RestyleHint {
-    fn heap_size_of_children(&self) -> usize { 0 }
-}
-
-/// In order to compute restyle hints, we perform a selector match against a
-/// list of partial selectors whose rightmost simple selector may be sensitive
-/// to the thing being changed. We do this matching twice, once for the element
-/// as it exists now and once for the element as it existed at the time of the
-/// last restyle. If the results of the selector match differ, that means that
-/// the given partial selector is sensitive to the change, and we compute a
-/// restyle hint based on its combinator.
-///
-/// In order to run selector matching against the old element state, we generate
-/// a wrapper for the element which claims to have the old state. This is the
-/// ElementWrapper logic below.
-///
-/// Gecko does this differently for element states, and passes a mask called
-/// mStateMask, which indicates the states that need to be ignored during
-/// selector matching. This saves an ElementWrapper allocation and an additional
-/// selector match call at the expense of additional complexity inside the
-/// selector matching logic. This only works for boolean states though, so we
-/// still need to take the ElementWrapper approach for attribute-dependent
-/// style. So we do it the same both ways for now to reduce complexity, but it's
-/// worth measuring the performance impact (if any) of the mStateMask approach.
-pub trait ElementSnapshot : Sized {
-    /// The state of the snapshot, if any.
-    fn state(&self) -> Option<ElementState>;
-
-    /// If this snapshot contains attribute information.
-    fn has_attrs(&self) -> bool;
-
-    /// The ID attribute per this snapshot. Should only be called if
-    /// `has_attrs()` returns true.
-    fn id_attr(&self) -> Option<Atom>;
-
-    /// Whether this snapshot contains the class `name`. Should only be called
-    /// if `has_attrs()` returns true.
-    fn has_class(&self, name: &Atom, case_sensitivity: CaseSensitivity) -> bool;
-
-    /// A callback that should be called for each class of the snapshot. Should
-    /// only be called if `has_attrs()` returns true.
-    fn each_class<F>(&self, F)
-        where F: FnMut(&Atom);
-
-    /// The `xml:lang=""` or `lang=""` attribute value per this snapshot.
-    fn lang_attr(&self) -> Option<AttrValue>;
-}
-
-#[derive(Clone)]
-struct ElementWrapper<'a, E>
-    where E: TElement,
-{
-    element: E,
-    cached_snapshot: Cell<Option<&'a Snapshot>>,
-    snapshot_map: &'a SnapshotMap,
-}
-
-impl<'a, E> ElementWrapper<'a, E>
-    where E: TElement,
-{
-    /// Trivially constructs an `ElementWrapper`.
-    fn new(el: E, snapshot_map: &'a SnapshotMap) -> Self {
-        ElementWrapper {
-            element: el,
-            cached_snapshot: Cell::new(None),
-            snapshot_map: snapshot_map,
-        }
-    }
-
-    /// Gets the snapshot associated with this element, if any.
-    fn snapshot(&self) -> Option<&'a Snapshot> {
-        if !self.element.has_snapshot() {
-            return None;
-        }
-
-        if let Some(s) = self.cached_snapshot.get() {
-            return Some(s);
-        }
-
-        let snapshot = self.snapshot_map.get(&self.element);
-        debug_assert!(snapshot.is_some(), "has_snapshot lied!");
-
-        self.cached_snapshot.set(snapshot);
-
-        snapshot
-    }
-
-    fn state_changes(&self) -> ElementState {
-        let snapshot = match self.snapshot() {
-            Some(s) => s,
-            None => return ElementState::empty(),
-        };
-
-        match snapshot.state() {
-            Some(state) => state ^ self.element.get_state(),
-            None => ElementState::empty(),
-        }
-    }
-
-    /// Returns the value of the `xml:lang=""` (or, if appropriate, `lang=""`)
-    /// attribute from this element's snapshot or the closest ancestor
-    /// element snapshot with the attribute specified.
-    fn get_lang(&self) -> Option<AttrValue> {
-        let mut current = self.clone();
-        loop {
-            let lang = match self.snapshot() {
-                Some(snapshot) if snapshot.has_attrs() => snapshot.lang_attr(),
-                _ => current.element.lang_attr(),
-            };
-            if lang.is_some() {
-                return lang;
-            }
-            match current.parent_element() {
-                Some(parent) => current = parent,
-                None => return None,
-            }
-        }
-    }
-}
-
-impl<'a, E> fmt::Debug for ElementWrapper<'a, E>
-    where E: TElement,
-{
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        // Ignore other fields for now, can change later if needed.
-        self.element.fmt(f)
-    }
-}
-
-#[cfg(feature = "gecko")]
-fn dir_selector_to_state(s: &[u16]) -> ElementState {
-    // Jump through some hoops to deal with our Box<[u16]> thing.
-    const LTR: [u16; 4] = [b'l' as u16, b't' as u16, b'r' as u16, 0];
-    const RTL: [u16; 4] = [b'r' as u16, b't' as u16, b'l' as u16, 0];
-    if LTR == *s {
-        IN_LTR_STATE
-    } else if RTL == *s {
-        IN_RTL_STATE
-    } else {
-        // :dir(something-random) is a valid selector, but shouldn't
-        // match anything.
-        ElementState::empty()
-    }
-}
-
-impl<'a, E> Element for ElementWrapper<'a, E>
-    where E: TElement,
-{
-    type Impl = SelectorImpl;
-
-    fn match_non_ts_pseudo_class<F>(&self,
-                                    pseudo_class: &NonTSPseudoClass,
-                                    context: &mut LocalMatchingContext<Self::Impl>,
-                                    relevant_link: &RelevantLinkStatus,
-                                    _setter: &mut F)
-                                    -> bool
-        where F: FnMut(&Self, ElementSelectorFlags),
-    {
-        // Some pseudo-classes need special handling to evaluate them against
-        // the snapshot.
-        match *pseudo_class {
-            #[cfg(feature = "gecko")]
-            NonTSPseudoClass::MozAny(ref selectors) => {
-                use selectors::matching::matches_complex_selector;
-                return selectors.iter().any(|s| {
-                    matches_complex_selector(s, 0, self, context, _setter)
-                })
-            }
-
-            // :dir is implemented in terms of state flags, but which state flag
-            // it maps to depends on the argument to :dir.  That means we can't
-            // just add its state flags to the NonTSPseudoClass, because if we
-            // added all of them there, and tested via intersects() here, we'd
-            // get incorrect behavior for :not(:dir()) cases.
-            //
-            // FIXME(bz): How can I set this up so once Servo adds :dir()
-            // support we don't forget to update this code?
-            #[cfg(feature = "gecko")]
-            NonTSPseudoClass::Dir(ref s) => {
-                let selector_flag = dir_selector_to_state(s);
-                if selector_flag.is_empty() {
-                    // :dir() with some random argument; does not match.
-                    return false;
-                }
-                let state = match self.snapshot().and_then(|s| s.state()) {
-                    Some(snapshot_state) => snapshot_state,
-                    None => self.element.get_state(),
-                };
-                return state.contains(selector_flag);
-            }
-
-            // For :link and :visited, we don't actually want to test the element
-            // state directly.  Instead, we use the `relevant_link` to determine if
-            // they match.
-            NonTSPseudoClass::Link => {
-                return relevant_link.is_unvisited(self, context.shared);
-            }
-            NonTSPseudoClass::Visited => {
-                return relevant_link.is_visited(self, context.shared);
-            }
-
-            #[cfg(feature = "gecko")]
-            NonTSPseudoClass::MozTableBorderNonzero => {
-                if let Some(snapshot) = self.snapshot() {
-                    if snapshot.has_other_pseudo_class_state() {
-                        return snapshot.mIsTableBorderNonzero();
-                    }
-                }
-            }
-
-            #[cfg(feature = "gecko")]
-            NonTSPseudoClass::MozBrowserFrame => {
-                if let Some(snapshot) = self.snapshot() {
-                    if snapshot.has_other_pseudo_class_state() {
-                        return snapshot.mIsMozBrowserFrame();
-                    }
-                }
-            }
-
-            // :lang() needs to match using the closest ancestor xml:lang="" or
-            // lang="" attribtue from snapshots.
-            NonTSPseudoClass::Lang(ref lang_arg) => {
-                return self.element.match_element_lang(Some(self.get_lang()), lang_arg);
-            }
-
-            _ => {}
-        }
-
-        let flag = pseudo_class.state_flag();
-        if flag.is_empty() {
-            return self.element.match_non_ts_pseudo_class(pseudo_class,
-                                                          context,
-                                                          relevant_link,
-                                                          &mut |_, _| {})
-        }
-        match self.snapshot().and_then(|s| s.state()) {
-            Some(snapshot_state) => snapshot_state.intersects(flag),
-            None => {
-                self.element.match_non_ts_pseudo_class(pseudo_class,
-                                                       context,
-                                                       relevant_link,
-                                                       &mut |_, _| {})
-            }
-        }
-    }
-
-    fn match_pseudo_element(&self,
-                            pseudo_element: &PseudoElement,
-                            context: &mut MatchingContext)
-                            -> bool
-    {
-        self.element.match_pseudo_element(pseudo_element, context)
-    }
-
-    fn is_link(&self) -> bool {
-        self.element.is_link()
-    }
-
-    fn parent_element(&self) -> Option<Self> {
-        self.element.parent_element()
-            .map(|e| ElementWrapper::new(e, self.snapshot_map))
-    }
-
-    fn first_child_element(&self) -> Option<Self> {
-        self.element.first_child_element()
-            .map(|e| ElementWrapper::new(e, self.snapshot_map))
-    }
-
-    fn last_child_element(&self) -> Option<Self> {
-        self.element.last_child_element()
-            .map(|e| ElementWrapper::new(e, self.snapshot_map))
-    }
-
-    fn prev_sibling_element(&self) -> Option<Self> {
-        self.element.prev_sibling_element()
-            .map(|e| ElementWrapper::new(e, self.snapshot_map))
-    }
-
-    fn next_sibling_element(&self) -> Option<Self> {
-        self.element.next_sibling_element()
-            .map(|e| ElementWrapper::new(e, self.snapshot_map))
-    }
-
-    fn is_html_element_in_html_document(&self) -> bool {
-        self.element.is_html_element_in_html_document()
-    }
-
-    fn get_local_name(&self) -> &<Self::Impl as ::selectors::SelectorImpl>::BorrowedLocalName {
-        self.element.get_local_name()
-    }
-
-    fn get_namespace(&self) -> &<Self::Impl as ::selectors::SelectorImpl>::BorrowedNamespaceUrl {
-        self.element.get_namespace()
-    }
-
-    fn attr_matches(&self,
-                    ns: &NamespaceConstraint<&Namespace>,
-                    local_name: &LocalName,
-                    operation: &AttrSelectorOperation<&AttrValue>)
-                    -> bool {
-        match self.snapshot() {
-            Some(snapshot) if snapshot.has_attrs() => {
-                snapshot.attr_matches(ns, local_name, operation)
-            }
-            _ => self.element.attr_matches(ns, local_name, operation)
-        }
-    }
-
-    fn has_id(&self, id: &Atom, case_sensitivity: CaseSensitivity) -> bool {
-        match self.snapshot() {
-            Some(snapshot) if snapshot.has_attrs() => {
-                snapshot.id_attr().map_or(false, |atom| case_sensitivity.eq_atom(&atom, id))
-            }
-            _ => self.element.has_id(id, case_sensitivity)
-        }
-    }
-
-    fn has_class(&self, name: &Atom, case_sensitivity: CaseSensitivity) -> bool {
-        match self.snapshot() {
-            Some(snapshot) if snapshot.has_attrs() => {
-                snapshot.has_class(name, case_sensitivity)
-            }
-            _ => self.element.has_class(name, case_sensitivity)
-        }
-    }
-
-    fn is_empty(&self) -> bool {
-        self.element.is_empty()
-    }
-
-    fn is_root(&self) -> bool {
-        self.element.is_root()
-    }
-
-    fn pseudo_element_originating_element(&self) -> Option<Self> {
-        self.element.closest_non_native_anonymous_ancestor()
-            .map(|e| ElementWrapper::new(e, self.snapshot_map))
-    }
-}
-
-fn selector_to_state(sel: &Component<SelectorImpl>) -> ElementState {
-    match *sel {
-        // FIXME(bz): How can I set this up so once Servo adds :dir() support we
-        // don't forget to update this code?
-        #[cfg(feature = "gecko")]
-        Component::NonTSPseudoClass(NonTSPseudoClass::Dir(ref s)) => dir_selector_to_state(s),
-        Component::NonTSPseudoClass(ref pc) => pc.state_flag(),
-        _ => ElementState::empty(),
-    }
-}
-
-fn is_attr_based_selector(sel: &Component<SelectorImpl>) -> bool {
-    match *sel {
-        Component::ID(_) |
-        Component::Class(_) |
-        Component::AttributeInNoNamespaceExists { .. } |
-        Component::AttributeInNoNamespace { .. } |
-        Component::AttributeOther(_) => true,
-        Component::NonTSPseudoClass(ref pc) => pc.is_attr_based(),
-        _ => false,
-    }
-}
-
-#[derive(Clone, Debug)]
-#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
-/// The characteristics that a selector is sensitive to.
-pub struct Sensitivities {
-    /// The states which the selector is sensitive to.
-    pub states: ElementState,
-    /// Whether the selector is sensitive to attributes.
-    pub attrs: bool,
-}
-
-impl Sensitivities {
-    fn is_empty(&self) -> bool {
-        self.states.is_empty() && !self.attrs
-    }
-
-    fn new() -> Sensitivities {
-        Sensitivities {
-            states: ElementState::empty(),
-            attrs: false,
-        }
-    }
-
-    fn sensitive_to(&self, attrs: bool, states: ElementState) -> bool {
-        (attrs && self.attrs) || self.states.intersects(states)
-    }
-}
-
-/// Mapping between (partial) CompoundSelectors (and the combinator to their
-/// right) and the states and attributes they depend on.
-///
-/// In general, for all selectors in all applicable stylesheets of the form:
-///
-/// |a _ b _ c _ d _ e|
-///
-/// Where:
-///   * |b| and |d| are simple selectors that depend on state (like :hover) or
-///     attributes (like [attr...], .foo, or #foo).
-///   * |a|, |c|, and |e| are arbitrary simple selectors that do not depend on
-///     state or attributes.
-///
-/// We generate a Dependency for both |a _ b:X _| and |a _ b:X _ c _ d:Y _|,
-/// even though those selectors may not appear on their own in any stylesheet.
-/// This allows us to quickly scan through the dependency sites of all style
-/// rules and determine the maximum effect that a given state or attribute
-/// change may have on the style of elements in the document.
-#[derive(Clone, Debug)]
-#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
-pub struct Dependency {
-    /// The dependency selector.
-    #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
-    selector: Selector<SelectorImpl>,
-    /// The offset into the selector that we should match on.
-    selector_offset: usize,
-    /// The ancestor hashes associated with the above selector at the given
-    /// offset.
-    #[cfg_attr(feature = "servo", ignore_heap_size_of = "No heap data")]
-    hashes: AncestorHashes,
-    /// The hint associated with this dependency.
-    pub hint: RestyleHint,
-    /// The sensitivities associated with this dependency.
-    pub sensitivities: Sensitivities,
-}
-
-impl SelectorMapEntry for Dependency {
-    fn selector(&self) -> SelectorIter<SelectorImpl> {
-        self.selector.iter_from(self.selector_offset)
-    }
-
-    fn hashes(&self) -> &AncestorHashes {
-        &self.hashes
-    }
-}
-
-/// The following visitor visits all the simple selectors for a given complex
-/// selector, taking care of :not and :any combinators, collecting whether any
-/// of them is sensitive to attribute or state changes.
-struct SensitivitiesVisitor {
-    sensitivities: Sensitivities,
-}
-
-impl SelectorVisitor for SensitivitiesVisitor {
-    type Impl = SelectorImpl;
-    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
-        self.sensitivities.states.insert(selector_to_state(s));
-        self.sensitivities.attrs |= is_attr_based_selector(s);
-        true
-    }
-}
-
-/// A set of dependencies for a given stylist.
-///
-/// Note that we can have many dependencies, often more than the total number
-/// of selectors given that we can get multiple partial selectors for a given
-/// selector. As such, we want all the usual optimizations, including the
-/// SelectorMap and the bloom filter.
-#[derive(Debug)]
-#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
-pub struct DependencySet {
-    /// This is for all other normal element's selectors/selector parts.
-    dependencies: SelectorMap<Dependency>,
-}
-
-/// The data that we need to compute a given restyle hint.
-pub enum HintComputationContext<'a, E: 'a>
-    where E: TElement,
-{
-    /// The data we need to compute a restyle hint for the root of the
-    /// traversal.
-    ///
-    /// We don't bother with the bloom filter there for multiple reasons:
-    ///
-    ///  * The root of the traversal uses to be the root of the document, so we
-    ///    don't gain much using a bloom filter.
-    ///
-    ///  * The chances that a non-root-element root of the traversal has a
-    ///    snapshot is quite low.
-    Root,
-
-    /// The data we need to compute a restyle hint for a child.
-    ///
-    /// This needs a full-blown style context in order to get the selector
-    /// filters up-to-date, and the dom depth in order to insert into the filter
-    /// properly if needed.
-    Child {
-        /// The thread-local context, that holds the bloom filter alive.
-        local_context: &'a mut ThreadLocalStyleContext<E>,
-        /// The dom depth of this element.
-        dom_depth: usize,
-    }
-}
-
-impl DependencySet {
-    /// Adds a selector to this `DependencySet`.
-    pub fn note_selector(&mut self, selector_and_hashes: &SelectorAndHashes<SelectorImpl>,
-                         quirks_mode: QuirksMode) {
-        let mut combinator = None;
-        let mut iter = selector_and_hashes.selector.iter();
-        let mut index = 0;
-        let mut child_combinators_seen = 0;
-        let mut saw_descendant_combinator = false;
-
-        loop {
-            let sequence_start = index;
-            let mut visitor = SensitivitiesVisitor {
-                sensitivities: Sensitivities::new()
-            };
-
-            // Visit all the simple selectors in this sequence.
-            //
-            // Note that this works because we can't have combinators nested
-            // inside simple selectors (i.e. in :not() or :-moz-any()). If we
-            // ever support that we'll need to visit complex selectors as well.
-            for ss in &mut iter {
-                ss.visit(&mut visitor);
-                index += 1; // Account for the simple selector.
-            }
-
-            // Keep track of how many child combinators we've encountered,
-            // and whether we've encountered a descendant combinator at all.
-            match combinator {
-                Some(Combinator::Child) => child_combinators_seen += 1,
-                Some(Combinator::Descendant) => saw_descendant_combinator = true,
-                _ => {}
-            }
-
-            // If we found a sensitivity, add an entry in the dependency set.
-            if !visitor.sensitivities.is_empty() {
-                // Compute a RestyleHint given the current combinator and the
-                // tracked number of child combinators and presence of a
-                // descendant combinator.
-                let hint = match combinator {
-                    // NB: RestyleHint::subtree() and not
-                    // RestyleHint::descendants() is needed to handle properly
-                    // eager pseudos, otherwise we may leave a stale style on
-                    // the parent.
-                    Some(Combinator::PseudoElement) => RestyleHint::subtree(),
-                    Some(Combinator::Child) if !saw_descendant_combinator => {
-                        RestyleHint::descendants_at_depth(child_combinators_seen)
-                    }
-                    Some(Combinator::Child) |
-                    Some(Combinator::Descendant) => RestyleHint::descendants(),
-                    Some(Combinator::NextSibling) |
-                    Some(Combinator::LaterSibling) => RestyleHint::later_siblings(),
-                    None => RestyleHint::for_self(),
-                };
-
-                // Reuse the bloom hashes if this is the base selector. Otherwise,
-                // rebuild them.
-                let hashes = if sequence_start == 0 {
-                    selector_and_hashes.hashes.clone()
-                } else {
-                    let seq_iter = selector_and_hashes.selector.iter_from(sequence_start);
-                    AncestorHashes::from_iter(seq_iter)
-                };
-
-                self.dependencies.insert(Dependency {
-                    sensitivities: visitor.sensitivities,
-                    hint: hint,
-                    selector: selector_and_hashes.selector.clone(),
-                    selector_offset: sequence_start,
-                    hashes: hashes,
-                }, quirks_mode);
-            }
-
-            combinator = iter.next_sequence();
-            if combinator.is_none() {
-                break;
-            }
-
-            index += 1; // Account for the combinator.
-        }
-    }
-
-    /// Create an empty `DependencySet`.
-    pub fn new() -> Self {
-        DependencySet {
-            dependencies: SelectorMap::new(),
-        }
-    }
-
-    /// Return the total number of dependencies that this set contains.
-    pub fn len(&self) -> usize {
-        self.dependencies.len()
-    }
-
-    /// Clear this dependency set.
-    pub fn clear(&mut self) {
-        self.dependencies = SelectorMap::new();
-    }
-
-    /// Compute a restyle hint given an element and a snapshot, per the rules
-    /// explained in the rest of the documentation.
-    pub fn compute_hint<'a, E>(
-        &self,
-        el: &E,
-        shared_context: &SharedStyleContext,
-        hint_context: HintComputationContext<'a, E>)
-        -> RestyleHint
-        where E: TElement,
-    {
-        debug_assert!(el.has_snapshot(), "Shouldn't be here!");
-        let snapshot_el =
-            ElementWrapper::new(*el, shared_context.snapshot_map);
-        let snapshot =
-            snapshot_el.snapshot().expect("has_snapshot lied so badly");
-
-        let state_changes = snapshot_el.state_changes();
-        let attrs_changed = snapshot.has_attrs();
-        if state_changes.is_empty() && !attrs_changed {
-            return RestyleHint::empty();
-        }
-
-        let mut hint = RestyleHint::empty();
-
-        // If we are sensitive to visitedness and the visited state changed, we
-        // force a restyle here. Matching doesn't depend on the actual visited
-        // state at all, so we can't look at matching results to decide what to
-        // do for this case.
-        if state_changes.intersects(IN_VISITED_OR_UNVISITED_STATE) {
-            trace!(" > visitedness change, force subtree restyle");
-            // We can't just return here because there may also be attribute
-            // changes as well that imply additional hints.
-            hint = RestyleHint::subtree();
-        }
-
-        // Compute whether the snapshot has any different id or class attributes
-        // from the element. If it does, we need to pass those to the lookup, so
-        // that we get all the possible applicable selectors from the rulehash.
-        let mut additional_id = None;
-        let mut additional_classes = SmallVec::<[Atom; 8]>::new();
-        if attrs_changed {
-            let id = snapshot.id_attr();
-            if id.is_some() && id != el.get_id() {
-                additional_id = id;
-            }
-
-            snapshot.each_class(|c| {
-                if !el.has_class(c, CaseSensitivity::CaseSensitive) {
-                    additional_classes.push(c.clone())
-                }
-            });
-        }
-
-        let bloom_filter = match hint_context {
-            HintComputationContext::Root => None,
-            HintComputationContext::Child { mut local_context, dom_depth } => {
-                local_context
-                    .bloom_filter
-                    .insert_parents_recovering(*el, dom_depth);
-                local_context.bloom_filter.assert_complete(*el);
-                Some(local_context.bloom_filter.filter())
-            }
-        };
-
-        let lookup_element = if el.implemented_pseudo_element().is_some() {
-            el.closest_non_native_anonymous_ancestor().unwrap()
-        } else {
-            *el
-        };
-
-        self.dependencies.lookup_with_additional(
-            lookup_element, shared_context.quirks_mode, additional_id, &additional_classes,
-            &mut |dep| {
-            trace!("scanning dependency: {:?}", dep);
-
-            if !dep.sensitivities.sensitive_to(attrs_changed,
-                                               state_changes) {
-                trace!(" > non-sensitive");
-                return true;
-            }
-
-            if hint.contains(&dep.hint) {
-                trace!(" > hint was already there");
-                return true;
-            }
-
-            // NOTE(emilio): We can't use the bloom filter for snapshots, given
-            // that arbitrary elements in the parent chain may have mutated
-            // their id's/classes, which means that they won't be in the
-            // filter, and as such we may fast-reject selectors incorrectly.
-            //
-            // We may be able to improve this if we record as we go down the
-            // tree whether any parent had a snapshot, and whether those
-            // snapshots were taken due to an element class/id change, but it's
-            // not clear we _need_ it right now.
-            let mut then_context =
-                MatchingContext::new_for_visited(MatchingMode::Normal, None,
-                                                 VisitedHandlingMode::AllLinksUnvisited,
-                                                 shared_context.quirks_mode);
-            let matched_then =
-                matches_selector(&dep.selector,
-                                 dep.selector_offset,
-                                 &dep.hashes,
-                                 &snapshot_el,
-                                 &mut then_context,
-                                 &mut |_, _| {});
-            let mut now_context =
-                MatchingContext::new_for_visited(MatchingMode::Normal, bloom_filter,
-                                                 VisitedHandlingMode::AllLinksUnvisited,
-                                                 shared_context.quirks_mode);
-            let matches_now =
-                matches_selector(&dep.selector,
-                                 dep.selector_offset,
-                                 &dep.hashes,
-                                 el,
-                                 &mut now_context,
-                                 &mut |_, _| {});
-
-            // Check for mismatches in both the match result and also the status
-            // of whether a relevant link was found.
-            if matched_then != matches_now ||
-               then_context.relevant_link_found != now_context.relevant_link_found {
-                hint.insert_from(&dep.hint);
-                return !hint.is_maximum()
-            }
-
-            // If there is a relevant link, then we also matched in visited
-            // mode.  Match again in this mode to ensure this also matches.
-            // Note that we never actually match directly against the element's
-            // true visited state at all, since that would expose us to timing
-            // attacks.  The matching process only considers the relevant link
-            // state and visited handling mode when deciding if visited
-            // matches.  Instead, we are rematching here in case there is some
-            // :visited selector whose matching result changed for some _other_
-            // element state or attribute.
-            if now_context.relevant_link_found &&
-               dep.sensitivities.states.intersects(IN_VISITED_OR_UNVISITED_STATE) {
-                then_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
-                let matched_then =
-                    matches_selector(&dep.selector,
-                                     dep.selector_offset,
-                                     &dep.hashes,
-                                     &snapshot_el,
-                                     &mut then_context,
-                                     &mut |_, _| {});
-                now_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
-                let matches_now =
-                    matches_selector(&dep.selector,
-                                     dep.selector_offset,
-                                     &dep.hashes,
-                                     el,
-                                     &mut now_context,
-                                     &mut |_, _| {});
-                if matched_then != matches_now {
-                    hint.insert_from(&dep.hint);
-                    return !hint.is_maximum()
-                }
-            }
-
-            !hint.is_maximum()
-        });
-
-        debug!("Calculated restyle hint: {:?} for {:?}. (State={:?}, {} Deps)",
-               hint, el, el.get_state(), self.len());
-
-        hint
-    }
-}
diff --git a/components/style/selector_map.rs b/components/style/selector_map.rs
index 9788860ebaa..48d25231b25 100644
--- a/components/style/selector_map.rs
+++ b/components/style/selector_map.rs
@@ -331,7 +331,7 @@ impl<T: SelectorMapEntry> SelectorMap<T> {
     pub fn lookup_with_additional<E, F>(&self,
                                         element: E,
                                         quirks_mode: QuirksMode,
-                                        additional_id: Option<Atom>,
+                                        additional_id: Option<&Atom>,
                                         additional_classes: &[Atom],
                                         f: &mut F)
                                         -> bool
@@ -345,7 +345,7 @@ impl<T: SelectorMapEntry> SelectorMap<T> {
 
         // Check the additional id.
         if let Some(id) = additional_id {
-            if let Some(v) = self.id_hash.get(&id, quirks_mode) {
+            if let Some(v) = self.id_hash.get(id, quirks_mode) {
                 for entry in v.iter() {
                     if !f(&entry) {
                         return false;
@@ -468,6 +468,16 @@ impl<V> MaybeCaseInsensitiveHashMap<Atom, V> {
         self.0.entry(key)
     }
 
+    /// HashMap::iter
+    pub fn iter(&self) -> hash_map::Iter<Atom, V> {
+        self.0.iter()
+    }
+
+    /// HashMap::clear
+    pub fn clear(&mut self) {
+        self.0.clear()
+    }
+
     /// HashMap::get
     pub fn get(&self, key: &Atom, quirks_mode: QuirksMode) -> Option<&V> {
         if quirks_mode == QuirksMode::Quirks {
diff --git a/components/style/servo/selector_parser.rs b/components/style/servo/selector_parser.rs
index 76e3aea3eba..652daa5417c 100644
--- a/components/style/servo/selector_parser.rs
+++ b/components/style/servo/selector_parser.rs
@@ -12,7 +12,7 @@ use cssparser::{Parser as CssParser, ToCss, serialize_identifier};
 use dom::{OpaqueNode, TElement, TNode};
 use element_state::ElementState;
 use fnv::FnvHashMap;
-use restyle_hints::ElementSnapshot;
+use invalidation::element::element_wrapper::ElementSnapshot;
 use selector_parser::{AttrValue as SelectorAttrValue, ElementExt, PseudoElementCascadeType, SelectorParser};
 use selectors::Element;
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint, CaseSensitivity};
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index 1a2aa59096f..ab0dd3fa031 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -7,7 +7,7 @@
 use {Atom, LocalName, Namespace};
 use applicable_declarations::{ApplicableDeclarationBlock, ApplicableDeclarationList};
 use bit_vec::BitVec;
-use context::{QuirksMode, SharedStyleContext};
+use context::QuirksMode;
 use data::ComputedStyle;
 use dom::TElement;
 use element_state::ElementState;
@@ -15,13 +15,13 @@ use error_reporting::create_error_reporter;
 use font_metrics::FontMetricsProvider;
 #[cfg(feature = "gecko")]
 use gecko_bindings::structs::{nsIAtom, StyleRuleInclusion};
+use invalidation::element::invalidation_map::InvalidationMap;
 use invalidation::media_queries::EffectiveMediaQueryResults;
 use media_queries::Device;
 use properties::{self, CascadeFlags, ComputedValues};
 use properties::{AnimationRules, PropertyDeclarationBlock};
 #[cfg(feature = "servo")]
 use properties::INHERIT_ALL;
-use restyle_hints::{HintComputationContext, DependencySet, RestyleHint};
 use rule_tree::{CascadeLevel, RuleTree, StrongRuleNode, StyleSource};
 use selector_map::{SelectorMap, SelectorMapEntry};
 use selector_parser::{SelectorImpl, PseudoElement};
@@ -116,8 +116,8 @@ pub struct Stylist {
     /// style rule appears in a stylesheet, needed to sort them by source order.
     rules_source_order: u32,
 
-    /// Selector dependencies used to compute restyle hints.
-    dependencies: DependencySet,
+    /// The invalidation map for this document.
+    invalidation_map: InvalidationMap,
 
     /// The attribute local names that appear in attribute selectors.  Used
     /// to avoid taking element snapshots when an irrelevant attribute changes.
@@ -249,7 +249,7 @@ impl Stylist {
             precomputed_pseudo_element_decls: Default::default(),
             rules_source_order: 0,
             rule_tree: RuleTree::new(),
-            dependencies: DependencySet::new(),
+            invalidation_map: InvalidationMap::new(),
             attribute_dependencies: BloomFilter::new(),
             style_attribute_dependency: false,
             state_dependencies: ElementState::empty(),
@@ -284,16 +284,16 @@ impl Stylist {
         self.num_rebuilds
     }
 
-    /// Returns the number of dependencies in the DependencySet.
-    pub fn num_dependencies(&self) -> usize {
-        self.dependencies.len()
-    }
-
     /// Returns the number of revalidation_selectors.
     pub fn num_revalidation_selectors(&self) -> usize {
         self.selectors_for_cache_revalidation.len()
     }
 
+    /// Gets a reference to the invalidation map.
+    pub fn invalidation_map(&self) -> &InvalidationMap {
+        &self.invalidation_map
+    }
+
     /// Clear the stylist's state, effectively resetting it to more or less
     /// the state Stylist::new creates.
     ///
@@ -324,7 +324,7 @@ impl Stylist {
         self.precomputed_pseudo_element_decls = Default::default();
         self.rules_source_order = 0;
         // We want to keep rule_tree around across stylist rebuilds.
-        self.dependencies.clear();
+        self.invalidation_map.clear();
         self.attribute_dependencies.clear();
         self.style_attribute_dependency = false;
         self.state_dependencies = ElementState::empty();
@@ -484,7 +484,7 @@ impl Stylist {
                                       self.rules_source_order),
                             self.quirks_mode);
 
-                        self.dependencies.note_selector(selector_and_hashes, self.quirks_mode);
+                        self.invalidation_map.note_selector(selector_and_hashes, self.quirks_mode);
                         if needs_revalidation(&selector_and_hashes.selector) {
                             self.selectors_for_cache_revalidation.insert(
                                 RevalidationSelectorAndHashes::new(&selector_and_hashes),
@@ -1198,19 +1198,6 @@ impl Stylist {
         results
     }
 
-    /// Given an element, and a snapshot table that represents a previous state
-    /// of the tree, compute the appropriate restyle hint, that is, the kind of
-    /// restyle we need to do.
-    pub fn compute_restyle_hint<'a, E>(&self,
-                                       element: &E,
-                                       shared_context: &SharedStyleContext,
-                                       context: HintComputationContext<'a, E>)
-                                       -> RestyleHint
-        where E: TElement,
-    {
-        self.dependencies.compute_hint(element, shared_context, context)
-    }
-
     /// Computes styles for a given declaration with parent_style.
     pub fn compute_for_declarations(&self,
                                     guards: &StylesheetGuards,
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index 32a525d4b45..1aa6415a1a2 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -8,9 +8,8 @@ use atomic_refcell::AtomicRefCell;
 use context::{SharedStyleContext, StyleContext, ThreadLocalStyleContext};
 use data::{ElementData, ElementStyles, StoredRestyleHint};
 use dom::{DirtyDescendants, NodeInfo, OpaqueNode, TElement, TNode};
+use invalidation::element::restyle_hints::{RECASCADE_SELF, RECASCADE_DESCENDANTS, RestyleHint};
 use matching::{ChildCascadeRequirement, MatchMethods};
-use restyle_hints::{CascadeHint, HintComputationContext, RECASCADE_SELF};
-use restyle_hints::{RECASCADE_DESCENDANTS, RestyleHint};
 use selector_parser::RestyleDamage;
 use sharing::{StyleSharingBehavior, StyleSharingTarget};
 #[cfg(feature = "servo")] use servo_config::opts;
@@ -242,24 +241,11 @@ pub trait DomTraversal<E: TElement> : Sync {
             };
         }
 
-        // Expand the snapshot, if any. This is normally handled by the parent, so
-        // we need a special case for the root.
-        //
-        // Expanding snapshots here may create a LATER_SIBLINGS restyle hint, which
-        // we propagate to the next sibling element.
+        // Look at whether there has been any attribute or state change, and
+        // invalidate our style, and the one of our siblings and descendants as
+        // needed.
         if let Some(mut data) = root.mutate_data() {
-            let later_siblings =
-                data.compute_final_hint(root,
-                                        shared_context,
-                                        HintComputationContext::Root);
-            if later_siblings {
-                if let Some(next) = root.next_sibling_element() {
-                    if let Some(mut next_data) = next.mutate_data() {
-                        let hint = StoredRestyleHint::subtree_and_later_siblings();
-                        next_data.ensure_restyle().hint.insert(hint);
-                    }
-                }
-            }
+            data.invalidate_style_if_needed(root, shared_context);
         }
 
         PreTraverseToken {
@@ -668,12 +654,9 @@ pub fn recalc_style_at<E, D>(traversal: &D,
     context.thread_local.statistics.elements_traversed += 1;
     debug_assert!(!element.has_snapshot() || element.handled_snapshot(),
                   "Should've handled snapshots here already");
-    debug_assert!(data.get_restyle().map_or(true, |r| {
-        !r.has_sibling_invalidations()
-    }), "Should've computed the final hint and handled later_siblings already");
 
     let compute_self = !element.has_current_styles(data);
-    let mut cascade_hint = CascadeHint::empty();
+    let mut hint = RestyleHint::empty();
 
     debug!("recalc_style_at: {:?} (compute_self={:?}, dirty_descendants={:?}, data={:?})",
            element, compute_self, element.has_dirty_descendants(), data);
@@ -682,10 +665,10 @@ pub fn recalc_style_at<E, D>(traversal: &D,
     if compute_self {
         match compute_style(traversal, traversal_data, context, element, data) {
             ChildCascadeRequirement::MustCascadeChildren => {
-                cascade_hint |= RECASCADE_SELF;
+                hint |= RECASCADE_SELF;
             }
             ChildCascadeRequirement::MustCascadeDescendants => {
-                cascade_hint |= RECASCADE_SELF | RECASCADE_DESCENDANTS;
+                hint |= RECASCADE_SELF | RECASCADE_DESCENDANTS;
             }
             ChildCascadeRequirement::CanSkipCascade => {}
         };
@@ -693,7 +676,7 @@ pub fn recalc_style_at<E, D>(traversal: &D,
         // We must always cascade native anonymous subtrees, since they inherit styles
         // from their first non-NAC ancestor.
         if element.is_native_anonymous() {
-            cascade_hint |= RECASCADE_SELF;
+            hint |= RECASCADE_SELF;
         }
 
         // If we're restyling this element to display:none, throw away all style
@@ -720,11 +703,11 @@ pub fn recalc_style_at<E, D>(traversal: &D,
 
     // FIXME(bholley): Need to handle explicitly-inherited reset properties
     // somewhere.
-    propagated_hint.insert_cascade_hint(cascade_hint);
+    propagated_hint.insert(hint.into());
 
-    trace!("propagated_hint={:?}, cascade_hint={:?}, \
+    trace!("propagated_hint={:?} \
             is_display_none={:?}, implementing_pseudo={:?}",
-           propagated_hint, cascade_hint,
+           propagated_hint,
            data.styles().is_display_none(),
            element.implemented_pseudo_element());
     debug_assert!(element.has_current_styles(data) ||
@@ -739,7 +722,8 @@ pub fn recalc_style_at<E, D>(traversal: &D,
             element.has_dirty_descendants()
         };
 
-    // Preprocess children, propagating restyle hints and handling sibling relationships.
+    // Preprocess children, propagating restyle hints and handling sibling
+    // relationships.
     if traversal.should_traverse_children(&mut context.thread_local,
                                           element,
                                           &data,
@@ -751,7 +735,6 @@ pub fn recalc_style_at<E, D>(traversal: &D,
         });
 
         preprocess_children::<E, D>(context,
-                                    traversal_data,
                                     element,
                                     propagated_hint,
                                     damage_handled);
@@ -853,9 +836,8 @@ fn compute_style<E, D>(_traversal: &D,
 }
 
 fn preprocess_children<E, D>(context: &mut StyleContext<E>,
-                             parent_traversal_data: &PerLevelTraversalData,
                              element: E,
-                             mut propagated_hint: StoredRestyleHint,
+                             propagated_hint: StoredRestyleHint,
                              damage_handled: RestyleDamage)
     where E: TElement,
           D: DomTraversal<E>,
@@ -878,39 +860,32 @@ fn preprocess_children<E, D>(context: &mut StyleContext<E>,
             continue;
         }
 
-        // Handle element snapshots and sibling restyle hints.
+        // Handle element snapshots and invalidation of descendants and siblings
+        // as needed.
         //
         // NB: This will be a no-op if there's no restyle data and no snapshot.
-        let later_siblings =
-            child_data.compute_final_hint(child,
-                                          &context.shared,
-                                          HintComputationContext::Child {
-                                              local_context: &mut context.thread_local,
-                                              dom_depth: parent_traversal_data.current_dom_depth + 1,
-                                          });
-
-        trace!(" > {:?} -> {:?} + {:?}, pseudo: {:?}, later_siblings: {:?}",
+        child_data.invalidate_style_if_needed(child, &context.shared);
+
+        trace!(" > {:?} -> {:?} + {:?}, pseudo: {:?}",
                child,
                child_data.get_restyle().map(|r| &r.hint),
                propagated_hint,
-               child.implemented_pseudo_element(),
-               later_siblings);
+               child.implemented_pseudo_element());
 
         // If the child doesn't have pre-existing RestyleData and we don't have
         // any reason to create one, avoid the useless allocation and move on to
         // the next child.
-        if propagated_hint.is_empty() && damage_handled.is_empty() && !child_data.has_restyle() {
+        if propagated_hint.is_empty() &&
+            damage_handled.is_empty() &&
+            !child_data.has_restyle() {
             continue;
         }
 
         let mut restyle_data = child_data.ensure_restyle();
 
-        // Propagate the parent and sibling restyle hint.
-        restyle_data.hint.insert_from(&propagated_hint);
-
-        if later_siblings {
-            propagated_hint.insert(RestyleHint::subtree().into());
-        }
+        // Propagate the parent restyle hint, that may make us restyle the whole
+        // subtree.
+        restyle_data.hint.insert(propagated_hint);
 
         // Store the damage already handled by ancestors.
         restyle_data.set_damage_handled(damage_handled);