servo: Merge #17292 - style: Implement a more fine-grained invalidation method (from emilio:better-style-invalidation); r=heycam
authorEmilio Cobos Álvarez <emilio@crisal.io>
Tue, 13 Jun 2017 04:56:09 -0700
changeset 414759 bdc22078e9f81f0a21d9e04522f52b96ed528b1e
parent 414758 e6783f75565efe00788e7821fdca7388677510f8
child 414760 8e206f279b44325c925a4d049e1cc0830d56da8b
push id1517
push userjlorenzo@mozilla.com
push dateThu, 14 Sep 2017 16:50:54 +0000
treeherdermozilla-release@3b41fd564418 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersheycam
milestone56.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
servo: Merge #17292 - style: Implement a more fine-grained invalidation method (from emilio:better-style-invalidation); r=heycam Source-Repo: https://github.com/servo/servo Source-Revision: 07f6e114850896eae2fd206351808fb31cceaaf0
servo/components/script/dom/document.rs
servo/components/script/dom/element.rs
servo/components/selectors/context.rs
servo/components/selectors/matching.rs
servo/components/selectors/parser.rs
servo/components/style/context.rs
servo/components/style/data.rs
servo/components/style/gecko/generated/structs_debug.rs
servo/components/style/gecko/generated/structs_release.rs
servo/components/style/gecko/snapshot.rs
servo/components/style/gecko/wrapper.rs
servo/components/style/invalidation/element/element_wrapper.rs
servo/components/style/invalidation/element/invalidation_map.rs
servo/components/style/invalidation/element/invalidator.rs
servo/components/style/invalidation/element/mod.rs
servo/components/style/invalidation/element/restyle_hints.rs
servo/components/style/invalidation/mod.rs
servo/components/style/invalidation/stylesheets.rs
servo/components/style/lib.rs
servo/components/style/matching.rs
servo/components/style/restyle_hints.rs
servo/components/style/selector_map.rs
servo/components/style/servo/selector_parser.rs
servo/components/style/stylist.rs
servo/components/style/traversal.rs
servo/ports/geckolib/glue.rs
servo/tests/unit/style/lib.rs
servo/tests/unit/style/restyle_hints.rs
--- a/servo/components/script/dom/document.rs
+++ b/servo/components/script/dom/document.rs
@@ -126,17 +126,17 @@ use std::collections::{HashMap, HashSet,
 use std::collections::hash_map::Entry::{Occupied, Vacant};
 use std::default::Default;
 use std::iter::once;
 use std::mem;
 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};
 use style::stylearc::Arc;
 use style::stylesheets::Stylesheet;
 use task_source::TaskSource;
 use time;
 use timers::OneshotTimerCallback;
@@ -2371,27 +2371,34 @@ impl Document {
         // I'm getting rid of the whole hashtable soon anyway, since all it does
         // right now is populate the element restyle data in layout, and we
         // could in theory do it in the DOM I think.
         let mut entry = self.ensure_pending_restyle(el);
         if entry.snapshot.is_none() {
             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();
+        if attr.local_name() == &local_name!("id") {
+            snapshot.id_changed = true;
+        } else if attr.local_name() == &local_name!("class") {
+            snapshot.class_changed = true;
+        } else {
+            snapshot.other_attributes_changed = true;
+        }
         if snapshot.attrs.is_none() {
             let attrs = el.attrs()
                           .iter()
                           .map(|attr| (attr.identifier().clone(), attr.value().clone()))
                           .collect();
             snapshot.attrs = Some(attrs);
         }
     }
--- a/servo/components/script/dom/element.rs
+++ b/servo/components/script/dom/element.rs
@@ -97,19 +97,19 @@ use std::convert::TryFrom;
 use std::default::Default;
 use std::fmt;
 use std::rc::Rc;
 use style::CaseSensitivityExt;
 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;
 use style::shared_lock::{SharedRwLock, Locked};
 use style::sink::Push;
 use style::stylearc::Arc;
 use style::thread_state;
 use style::values::{CSSFloat, Either};
@@ -248,17 +248,17 @@ impl Element {
     }
 
     pub fn restyle(&self, damage: NodeDamage) {
         let doc = self.node.owner_doc();
         let mut restyle = doc.ensure_pending_restyle(self);
 
         // 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();
         }
     }
 
     // https://drafts.csswg.org/cssom-view/#css-layout-box
     // Elements that have a computed value of the display property
--- a/servo/components/selectors/context.rs
+++ b/servo/components/selectors/context.rs
@@ -43,16 +43,22 @@ pub enum MatchingMode {
     ForStatelessPseudoElement,
 }
 
 /// The mode to use when matching unvisited and visited links.
 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
 pub enum VisitedHandlingMode {
     /// All links are matched as if they are unvisted.
     AllLinksUnvisited,
+    /// All links are matched as if they are visited and unvisited (both :link
+    /// and :visited match).
+    ///
+    /// This is intended to be used from invalidation code, to be conservative
+    /// about whether we need to restyle a link.
+    AllLinksVisitedAndUnvisited,
     /// A element's "relevant link" is the element being matched if it is a link
     /// or the nearest ancestor link. The relevant link is matched as though it
     /// is visited, and all other links are matched as if they are unvisited.
     RelevantLinkVisited,
 }
 
 /// Which quirks mode is this document in.
 ///
--- a/servo/components/selectors/matching.rs
+++ b/servo/components/selectors/matching.rs
@@ -248,16 +248,20 @@ impl RelevantLinkStatus {
     /// relevant links as visited.
     pub fn is_visited<E>(&self, element: &E, context: &MatchingContext) -> bool
         where E: Element,
     {
         if !element.is_link() {
             return false
         }
 
+        if context.visited_handling == VisitedHandlingMode::AllLinksVisitedAndUnvisited {
+            return true;
+        }
+
         // Non-relevant links are always unvisited.
         if *self != RelevantLinkStatus::Found {
             return false
         }
 
         context.visited_handling == VisitedHandlingMode::RelevantLinkVisited
     }
 
@@ -269,16 +273,20 @@ impl RelevantLinkStatus {
     /// relevant links).
     pub fn is_unvisited<E>(&self, element: &E, context: &MatchingContext) -> bool
         where E: Element,
     {
         if !element.is_link() {
             return false
         }
 
+        if context.visited_handling == VisitedHandlingMode::AllLinksVisitedAndUnvisited {
+            return true;
+        }
+
         // Non-relevant links are always unvisited.
         if *self != RelevantLinkStatus::Found {
             return true
         }
 
         context.visited_handling == VisitedHandlingMode::AllLinksUnvisited
     }
 }
@@ -330,19 +338,19 @@ enum SelectorMatchingResult {
     Matched,
     NotMatchedAndRestartFromClosestLaterSibling,
     NotMatchedAndRestartFromClosestDescendant,
     NotMatchedGlobally,
 }
 
 /// Matches a selector, fast-rejecting against a bloom filter.
 ///
-/// We accept an offset to allow consumers to represent and match against partial
-/// selectors (indexed from the right). We use this API design, rather than
-/// having the callers pass a SelectorIter, because creating a SelectorIter
+/// We accept an offset to allow consumers to represent and match against
+/// partial selectors (indexed from the right). We use this API design, rather
+/// than having the callers pass a SelectorIter, because creating a SelectorIter
 /// requires dereferencing the selector to get the length, which adds an
 /// unncessary cache miss for cases when we can fast-reject with AncestorHashes
 /// (which the caller can store inline with the selector pointer).
 #[inline(always)]
 pub fn matches_selector<E, F>(selector: &Selector<E::Impl>,
                               offset: usize,
                               hashes: &AncestorHashes,
                               element: &E,
@@ -355,35 +363,91 @@ pub fn matches_selector<E, F>(selector: 
     // Use the bloom filter to fast-reject.
     if let Some(filter) = context.bloom_filter {
         if !may_match::<E>(hashes, filter) {
             return false;
         }
     }
 
     let mut local_context = LocalMatchingContext::new(context, selector);
-    matches_complex_selector(&selector, offset, element, &mut local_context, flags_setter)
+    let iter = if offset == 0 {
+        selector.iter()
+    } else {
+        selector.iter_from(offset)
+    };
+    matches_complex_selector(iter, element, &mut local_context, flags_setter)
+}
+
+/// Whether a compound selector matched, and whether it was the rightmost
+/// selector inside the complex selector.
+pub enum CompoundSelectorMatchingResult {
+    /// The compound selector matched, and the next combinator offset is
+    /// `next_combinator_offset`.
+    ///
+    /// If the next combinator offset is zero, it means that it's the rightmost
+    /// selector.
+    Matched { next_combinator_offset: usize, },
+    /// The selector didn't match.
+    NotMatched,
+}
+
+/// Matches a compound selector belonging to `selector`, starting at offset
+/// `from_offset`, matching left to right.
+///
+/// Requires that `from_offset` points to a `Combinator`.
+///
+/// NOTE(emilio): This doesn't allow to match in the leftmost sequence of the
+/// complex selector, but it happens to be the case we don't need it.
+pub fn matches_compound_selector<E>(
+    selector: &Selector<E::Impl>,
+    mut from_offset: usize,
+    context: &mut MatchingContext,
+    element: &E,
+) -> CompoundSelectorMatchingResult
+where
+    E: Element
+{
+    if cfg!(debug_assertions) {
+        selector.combinator_at(from_offset); // This asserts.
+    }
+
+    let mut local_context = LocalMatchingContext::new(context, selector);
+    for component in selector.iter_raw_rev_from(from_offset - 1) {
+        if matches!(*component, Component::Combinator(..)) {
+            return CompoundSelectorMatchingResult::Matched {
+                next_combinator_offset: from_offset - 1,
+            }
+        }
+
+        if !matches_simple_selector(
+            component,
+            element,
+            &mut local_context,
+            &RelevantLinkStatus::NotLooking,
+            &mut |_, _| {}) {
+            return CompoundSelectorMatchingResult::NotMatched;
+        }
+
+        from_offset -= 1;
+    }
+
+    return CompoundSelectorMatchingResult::Matched {
+        next_combinator_offset: 0,
+    }
 }
 
 /// Matches a complex selector.
-pub fn matches_complex_selector<E, F>(complex_selector: &Selector<E::Impl>,
-                                      offset: usize,
+pub fn matches_complex_selector<E, F>(mut iter: SelectorIter<E::Impl>,
                                       element: &E,
                                       mut context: &mut LocalMatchingContext<E::Impl>,
                                       flags_setter: &mut F)
                                       -> bool
     where E: Element,
           F: FnMut(&E, ElementSelectorFlags),
 {
-    let mut iter = if offset == 0 {
-        complex_selector.iter()
-    } else {
-        complex_selector.iter_from(offset)
-    };
-
     if cfg!(debug_assertions) {
         if context.shared.matching_mode == MatchingMode::ForStatelessPseudoElement {
             assert!(iter.clone().any(|c| {
                 matches!(*c, Component::PseudoElement(..))
             }));
         }
     }
 
--- a/servo/components/selectors/parser.rs
+++ b/servo/components/selectors/parser.rs
@@ -444,28 +444,46 @@ impl<Impl: SelectorImpl> Selector<Impl> 
         // Note: selectors are stored left-to-right but logical order is right-to-left.
         let iter = self.0.slice[..(self.len() - offset)].iter().rev();
         SelectorIter {
             iter: iter,
             next_combinator: None,
         }
     }
 
-    /// Returns an iterator over the entire sequence of simple selectors and combinators,
-    /// from right to left.
+    /// Returns the combinator at index `index`, or panics if the component is
+    /// not a combinator.
+    pub fn combinator_at(&self, index: usize) -> Combinator {
+        match self.0.slice[self.0.slice.len() - index] {
+            Component::Combinator(c) => c,
+            ref other => {
+                panic!("Not a combinator: {:?}, {:?}, index: {}",
+                       other, self, index)
+            }
+        }
+    }
+
+    /// Returns an iterator over the entire sequence of simple selectors and
+    /// combinators, from right to left.
     pub fn iter_raw(&self) -> Rev<slice::Iter<Component<Impl>>> {
         self.iter_raw_rev().rev()
     }
 
-    /// Returns an iterator over the entire sequence of simple selectors and combinators,
-    /// from left to right.
+    /// Returns an iterator over the entire sequence of simple selectors and
+    /// combinators, from left to right.
     pub fn iter_raw_rev(&self) -> slice::Iter<Component<Impl>> {
         self.0.slice.iter()
     }
 
+    /// Returns an iterator over the sequence of simple selectors and
+    /// combinators after `offset`, from left to right.
+    pub fn iter_raw_rev_from(&self, offset: usize) -> slice::Iter<Component<Impl>> {
+        self.0.slice[(self.0.slice.len() - offset)..].iter()
+    }
+
     /// Creates a Selector from a vec of Components. Used in tests.
     pub fn from_vec(vec: Vec<Component<Impl>>, specificity_and_flags: u32) -> Self {
         let header = HeaderWithLength::new(SpecificityAndFlags(specificity_and_flags), vec.len());
         Selector(Arc::into_thin(Arc::from_header_and_iter(header, vec.into_iter())))
     }
 
     /// Returns count of simple selectors and combinators in the Selector.
     pub fn len(&self) -> usize {
--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -245,17 +245,18 @@ impl TraversalStatistics {
     pub fn finish<E, D>(&mut self, traversal: &D, start: f64)
         where E: TElement,
               D: DomTraversal<E>,
     {
         self.is_parallel = Some(traversal.is_parallel());
         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;
     }
 
     /// Returns whether this traversal is 'large' in order to avoid console spam
     /// from lots of tiny traversals.
     pub fn is_large_traversal(&self) -> bool {
         self.elements_traversed >= 50
--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -2,19 +2,19 @@
  * 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/. */
 
 //! Per-node data used in style calculation.
 
 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;
 use shared_lock::{Locked, StylesheetGuards};
 use std::fmt;
 use stylearc::Arc;
 use traversal::TraversalFlags;
 
@@ -263,16 +263,20 @@ impl EagerPseudoStyles {
     ///
     /// Returns true if the pseudo-element is new.
     pub fn add_rules(&mut self,
                      pseudo: &PseudoElement,
                      visited_handling: VisitedHandlingMode,
                      rules: StrongRuleNode)
                      -> bool {
         match visited_handling {
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                unreachable!("We should never try to selector match with \
+                             AllLinksVisitedAndUnvisited");
+            },
             VisitedHandlingMode::AllLinksUnvisited => {
                 self.add_unvisited_rules(&pseudo, rules)
             },
             VisitedHandlingMode::RelevantLinkVisited => {
                 self.add_visited_rules(&pseudo, rules)
             },
         }
     }
@@ -281,16 +285,20 @@ impl EagerPseudoStyles {
     /// exist. The type of rule node depends on the visited mode.
     ///
     /// Returns true if the psuedo-element was removed.
     pub fn remove_rules(&mut self,
                         pseudo: &PseudoElement,
                         visited_handling: VisitedHandlingMode)
                         -> bool {
         match visited_handling {
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                unreachable!("We should never try to selector match with \
+                             AllLinksVisitedAndUnvisited");
+            },
             VisitedHandlingMode::AllLinksUnvisited => {
                 self.remove_unvisited_rules(&pseudo)
             },
             VisitedHandlingMode::RelevantLinkVisited => {
                 self.remove_visited_rules(&pseudo)
             },
         }
     }
@@ -340,18 +348,20 @@ impl ElementStyles {
         self.primary.values().get_box().clone_display() == display::T::none
     }
 }
 
 /// Restyle hint for storing on ElementData.
 ///
 /// 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.
     pub fn propagate(&mut self, traversal_flags: &TraversalFlags) -> Self {
         use std::mem;
 
         // In the middle of an animation only restyle, we don't need to
         // propagate any restyle hints, and we need to remove ourselves.
@@ -373,82 +383,59 @@ impl StoredRestyleHint {
     /// Creates an empty `StoredRestyleHint`.
     pub fn empty() -> Self {
         StoredRestyleHint(RestyleHint::empty())
     }
 
     /// 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.
     pub fn recascade_self() -> Self {
         StoredRestyleHint(RestyleHint::recascade_self())
     }
 
     /// Returns true if the hint indicates that our style may be invalidated.
     pub fn has_self_invalidations(&self) -> bool {
         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()
     }
 
     /// Insert another restyle hint, effectively resulting in the union of both.
     pub fn insert(&mut self, other: Self) {
         self.0.insert(other.0)
     }
 
     /// 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.
     pub fn has_animation_hint(&self) -> bool {
         self.0.has_animation_hint()
     }
 
     /// Returns true if the hint indicates the current element must be
     /// recascaded.
     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()
     }
 }
 
 impl From<RestyleHint> for StoredRestyleHint {
     fn from(hint: RestyleHint) -> Self {
         StoredRestyleHint(hint)
     }
 }
@@ -478,21 +465,16 @@ pub struct RestyleData {
 }
 
 impl RestyleData {
     /// Returns true if this RestyleData might invalidate the current style.
     pub fn has_invalidations(&self) -> bool {
         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 {
         self.damage_handled
     }
 
     /// Returns damage handled (always empty for servo).
     #[cfg(feature = "servo")]
@@ -528,76 +510,51 @@ pub struct ElementData {
 
 /// The kind of restyle that a single element should do.
 pub enum RestyleKind {
     /// We need to run selector matching plus re-cascade, that is, a full
     /// restyle.
     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
     }
 
 
     /// Trivially construct an ElementData.
     pub fn new(existing: Option<ElementStyles>) -> Self {
         ElementData {
             styles: existing,
             restyle: None,
@@ -621,23 +578,23 @@ impl ElementData {
                       "Should've stopped earlier");
         if !self.has_styles() {
             return RestyleKind::MatchAndCascade;
         }
 
         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!");
         return RestyleKind::CascadeOnly;
     }
 
     /// Gets the element styles, if any.
     pub fn get_styles(&self) -> Option<&ElementStyles> {
--- a/servo/components/style/gecko/generated/structs_debug.rs
+++ b/servo/components/style/gecko/generated/structs_debug.rs
@@ -9230,41 +9230,116 @@ pub mod root {
                 let mut unit_field_val: u8 =
                     unsafe { ::std::mem::transmute(self._bitfield_1) };
                 unit_field_val &= !mask;
                 unit_field_val |= (val << 4usize) & mask;
                 self._bitfield_1 =
                     unsafe { ::std::mem::transmute(unit_field_val) };
             }
             #[inline]
+            pub fn mClassAttributeChanged(&self) -> bool {
+                let mask = 32usize as u8;
+                let unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                let val = (unit_field_val & mask) >> 5usize;
+                unsafe { ::std::mem::transmute(val as u8) }
+            }
+            #[inline]
+            pub fn set_mClassAttributeChanged(&mut self, val: bool) {
+                let mask = 32usize as u8;
+                let val = val as u8 as u8;
+                let mut unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                unit_field_val &= !mask;
+                unit_field_val |= (val << 5usize) & mask;
+                self._bitfield_1 =
+                    unsafe { ::std::mem::transmute(unit_field_val) };
+            }
+            #[inline]
+            pub fn mIdAttributeChanged(&self) -> bool {
+                let mask = 64usize as u8;
+                let unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                let val = (unit_field_val & mask) >> 6usize;
+                unsafe { ::std::mem::transmute(val as u8) }
+            }
+            #[inline]
+            pub fn set_mIdAttributeChanged(&mut self, val: bool) {
+                let mask = 64usize as u8;
+                let val = val as u8 as u8;
+                let mut unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                unit_field_val &= !mask;
+                unit_field_val |= (val << 6usize) & mask;
+                self._bitfield_1 =
+                    unsafe { ::std::mem::transmute(unit_field_val) };
+            }
+            #[inline]
+            pub fn mOtherAttributeChanged(&self) -> bool {
+                let mask = 128usize as u8;
+                let unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                let val = (unit_field_val & mask) >> 7usize;
+                unsafe { ::std::mem::transmute(val as u8) }
+            }
+            #[inline]
+            pub fn set_mOtherAttributeChanged(&mut self, val: bool) {
+                let mask = 128usize as u8;
+                let val = val as u8 as u8;
+                let mut unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                unit_field_val &= !mask;
+                unit_field_val |= (val << 7usize) & mask;
+                self._bitfield_1 =
+                    unsafe { ::std::mem::transmute(unit_field_val) };
+            }
+            #[inline]
             pub fn new_bitfield_1(mIsHTMLElementInHTMLDocument: bool,
                                   mIsInChromeDocument: bool,
                                   mSupportsLangAttr: bool,
                                   mIsTableBorderNonzero: bool,
-                                  mIsMozBrowserFrame: bool) -> u8 {
+                                  mIsMozBrowserFrame: bool,
+                                  mClassAttributeChanged: bool,
+                                  mIdAttributeChanged: bool,
+                                  mOtherAttributeChanged: bool) -> u8 {
                 ({
                      ({
                           ({
                                ({
-                                    ({ 0 } |
-                                         ((mIsHTMLElementInHTMLDocument as u8
-                                               as u8) << 0usize) &
-                                             (1usize as u8))
+                                    ({
+                                         ({
+                                              ({
+                                                   ({ 0 } |
+                                                        ((mIsHTMLElementInHTMLDocument
+                                                              as u8 as u8) <<
+                                                             0usize) &
+                                                            (1usize as u8))
+                                               } |
+                                                   ((mIsInChromeDocument as u8
+                                                         as u8) << 1usize) &
+                                                       (2usize as u8))
+                                          } |
+                                              ((mSupportsLangAttr as u8 as u8)
+                                                   << 2usize) &
+                                                  (4usize as u8))
+                                     } |
+                                         ((mIsTableBorderNonzero as u8 as u8)
+                                              << 3usize) & (8usize as u8))
                                 } |
-                                    ((mIsInChromeDocument as u8 as u8) <<
-                                         1usize) & (2usize as u8))
+                                    ((mIsMozBrowserFrame as u8 as u8) <<
+                                         4usize) & (16usize as u8))
                            } |
-                               ((mSupportsLangAttr as u8 as u8) << 2usize) &
-                                   (4usize as u8))
+                               ((mClassAttributeChanged as u8 as u8) <<
+                                    5usize) & (32usize as u8))
                       } |
-                          ((mIsTableBorderNonzero as u8 as u8) << 3usize) &
-                              (8usize as u8))
+                          ((mIdAttributeChanged as u8 as u8) << 6usize) &
+                              (64usize as u8))
                  } |
-                     ((mIsMozBrowserFrame as u8 as u8) << 4usize) &
-                         (16usize as u8))
+                     ((mOtherAttributeChanged as u8 as u8) << 7usize) &
+                         (128usize as u8))
             }
         }
         #[repr(C)]
         #[derive(Debug)]
         pub struct AnimationPropertySegment {
             pub mFromKey: f32,
             pub mToKey: f32,
             pub mFromValue: root::mozilla::AnimationValue,
--- a/servo/components/style/gecko/generated/structs_release.rs
+++ b/servo/components/style/gecko/generated/structs_release.rs
@@ -8971,41 +8971,116 @@ pub mod root {
                 let mut unit_field_val: u8 =
                     unsafe { ::std::mem::transmute(self._bitfield_1) };
                 unit_field_val &= !mask;
                 unit_field_val |= (val << 4usize) & mask;
                 self._bitfield_1 =
                     unsafe { ::std::mem::transmute(unit_field_val) };
             }
             #[inline]
+            pub fn mClassAttributeChanged(&self) -> bool {
+                let mask = 32usize as u8;
+                let unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                let val = (unit_field_val & mask) >> 5usize;
+                unsafe { ::std::mem::transmute(val as u8) }
+            }
+            #[inline]
+            pub fn set_mClassAttributeChanged(&mut self, val: bool) {
+                let mask = 32usize as u8;
+                let val = val as u8 as u8;
+                let mut unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                unit_field_val &= !mask;
+                unit_field_val |= (val << 5usize) & mask;
+                self._bitfield_1 =
+                    unsafe { ::std::mem::transmute(unit_field_val) };
+            }
+            #[inline]
+            pub fn mIdAttributeChanged(&self) -> bool {
+                let mask = 64usize as u8;
+                let unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                let val = (unit_field_val & mask) >> 6usize;
+                unsafe { ::std::mem::transmute(val as u8) }
+            }
+            #[inline]
+            pub fn set_mIdAttributeChanged(&mut self, val: bool) {
+                let mask = 64usize as u8;
+                let val = val as u8 as u8;
+                let mut unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                unit_field_val &= !mask;
+                unit_field_val |= (val << 6usize) & mask;
+                self._bitfield_1 =
+                    unsafe { ::std::mem::transmute(unit_field_val) };
+            }
+            #[inline]
+            pub fn mOtherAttributeChanged(&self) -> bool {
+                let mask = 128usize as u8;
+                let unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                let val = (unit_field_val & mask) >> 7usize;
+                unsafe { ::std::mem::transmute(val as u8) }
+            }
+            #[inline]
+            pub fn set_mOtherAttributeChanged(&mut self, val: bool) {
+                let mask = 128usize as u8;
+                let val = val as u8 as u8;
+                let mut unit_field_val: u8 =
+                    unsafe { ::std::mem::transmute(self._bitfield_1) };
+                unit_field_val &= !mask;
+                unit_field_val |= (val << 7usize) & mask;
+                self._bitfield_1 =
+                    unsafe { ::std::mem::transmute(unit_field_val) };
+            }
+            #[inline]
             pub fn new_bitfield_1(mIsHTMLElementInHTMLDocument: bool,
                                   mIsInChromeDocument: bool,
                                   mSupportsLangAttr: bool,
                                   mIsTableBorderNonzero: bool,
-                                  mIsMozBrowserFrame: bool) -> u8 {
+                                  mIsMozBrowserFrame: bool,
+                                  mClassAttributeChanged: bool,
+                                  mIdAttributeChanged: bool,
+                                  mOtherAttributeChanged: bool) -> u8 {
                 ({
                      ({
                           ({
                                ({
-                                    ({ 0 } |
-                                         ((mIsHTMLElementInHTMLDocument as u8
-                                               as u8) << 0usize) &
-                                             (1usize as u8))
+                                    ({
+                                         ({
+                                              ({
+                                                   ({ 0 } |
+                                                        ((mIsHTMLElementInHTMLDocument
+                                                              as u8 as u8) <<
+                                                             0usize) &
+                                                            (1usize as u8))
+                                               } |
+                                                   ((mIsInChromeDocument as u8
+                                                         as u8) << 1usize) &
+                                                       (2usize as u8))
+                                          } |
+                                              ((mSupportsLangAttr as u8 as u8)
+                                                   << 2usize) &
+                                                  (4usize as u8))
+                                     } |
+                                         ((mIsTableBorderNonzero as u8 as u8)
+                                              << 3usize) & (8usize as u8))
                                 } |
-                                    ((mIsInChromeDocument as u8 as u8) <<
-                                         1usize) & (2usize as u8))
+                                    ((mIsMozBrowserFrame as u8 as u8) <<
+                                         4usize) & (16usize as u8))
                            } |
-                               ((mSupportsLangAttr as u8 as u8) << 2usize) &
-                                   (4usize as u8))
+                               ((mClassAttributeChanged as u8 as u8) <<
+                                    5usize) & (32usize as u8))
                       } |
-                          ((mIsTableBorderNonzero as u8 as u8) << 3usize) &
-                              (8usize as u8))
+                          ((mIdAttributeChanged as u8 as u8) << 6usize) &
+                              (64usize as u8))
                  } |
-                     ((mIsMozBrowserFrame as u8 as u8) << 4usize) &
-                         (16usize as u8))
+                     ((mOtherAttributeChanged as u8 as u8) << 7usize) &
+                         (128usize as u8))
             }
         }
         #[repr(C)]
         #[derive(Debug)]
         pub struct AnimationPropertySegment {
             pub mFromKey: f32,
             pub mToKey: f32,
             pub mFromValue: root::mozilla::AnimationValue,
--- a/servo/components/style/gecko/snapshot.rs
+++ b/servo/components/style/gecko/snapshot.rs
@@ -8,17 +8,17 @@
 use dom::TElement;
 use element_state::ElementState;
 use gecko::snapshot_helpers;
 use gecko::wrapper::{NamespaceConstraintHelpers, GeckoElement};
 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};
 
 /// A snapshot of a Gecko element.
 pub type GeckoElementSnapshot = ServoElementSnapshot;
 
 /// A map from elements to snapshots for Gecko's style back-end.
 pub type SnapshotMap = ServoElementSnapshotTable;
@@ -57,16 +57,35 @@ impl GeckoElementSnapshot {
 
     /// Returns true if the snapshot has stored state for pseudo-classes
     /// that depend on things other than `ElementState`.
     #[inline]
     pub fn has_other_pseudo_class_state(&self) -> bool {
         self.has_any(Flags::OtherPseudoClassState)
     }
 
+    /// Returns true if the snapshot recorded an id change.
+    #[inline]
+    pub fn id_changed(&self) -> bool {
+        self.mIdAttributeChanged()
+    }
+
+    /// Returns true if the snapshot recorded a class attribute change.
+    #[inline]
+    pub fn class_changed(&self) -> bool {
+        self.mClassAttributeChanged()
+    }
+
+    /// Returns true if the snapshot recorded an attribute change which isn't a
+    /// class or id change.
+    #[inline]
+    pub fn other_attr_changed(&self) -> bool {
+        self.mOtherAttributeChanged()
+    }
+
     /// selectors::Element::attr_matches
     pub fn attr_matches(&self,
                         ns: &NamespaceConstraint<&Namespace>,
                         local_name: &Atom,
                         operation: &AttrSelectorOperation<&Atom>)
                         -> bool {
         unsafe {
             match *operation {
--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -403,16 +403,34 @@ impl<'lb> GeckoXBLBinding<'lb> {
 pub struct GeckoElement<'le>(pub &'le RawGeckoElement);
 
 impl<'le> fmt::Debug for GeckoElement<'le> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "<{}", self.get_local_name()));
         if let Some(id) = self.get_id() {
             try!(write!(f, " id={}", id));
         }
+
+        let mut first = true;
+        let mut any = false;
+        self.each_class(|c| {
+            if first {
+                first = false;
+                any = true;
+                let _ = f.write_str(" class=\"");
+            } else {
+                let _ = f.write_str(" ");
+            }
+            let _ = write!(f, "{}", c);
+        });
+
+        if any {
+            f.write_str("\"")?;
+        }
+
         write!(f, "> ({:#x})", self.as_node().opaque().0)
     }
 }
 
 impl<'le> GeckoElement<'le> {
     /// Parse the style attribute of an element.
     pub fn parse_style_attribute(value: &str,
                                  url_data: &UrlExtraData,
@@ -1235,16 +1253,20 @@ impl<'le> PresentationalHintsSynthesizer
             );
         }
 
         // Support for link, vlink, and alink presentation hints on <body>
         if self.is_link() {
             // Unvisited vs. visited styles are computed up-front based on the
             // visited mode (not the element's actual state).
             let declarations = match visited_handling {
+                VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                    unreachable!("We should never try to selector match with \
+                                 AllLinksVisitedAndUnvisited");
+                },
                 VisitedHandlingMode::AllLinksUnvisited => unsafe {
                     Gecko_GetUnvisitedLinkAttrDeclarationBlock(self.0)
                 },
                 VisitedHandlingMode::RelevantLinkVisited => unsafe {
                     Gecko_GetVisitedLinkAttrDeclarationBlock(self.0)
                 },
             };
             let declarations = declarations.and_then(|s| s.as_arc_opt());
@@ -1542,17 +1564,17 @@ impl<'le> ::selectors::Element for Gecko
             NonTSPseudoClass::MozIsHTML => {
                 self.is_html_element_in_html_document()
             }
             NonTSPseudoClass::MozPlaceholder => false,
             NonTSPseudoClass::MozAny(ref sels) => {
                 let old_value = context.within_functional_pseudo_class_argument;
                 context.within_functional_pseudo_class_argument = true;
                 let result = sels.iter().any(|s| {
-                    matches_complex_selector(s, 0, self, context, flags_setter)
+                    matches_complex_selector(s.iter(), self, context, flags_setter)
                 });
                 context.within_functional_pseudo_class_argument = old_value;
                 result
             }
             NonTSPseudoClass::Lang(ref lang_arg) => {
                 self.match_element_lang(None, lang_arg)
             }
             NonTSPseudoClass::MozSystemMetric(ref s) |
new file mode 100644
--- /dev/null
+++ b/servo/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))
+    }
+}
new file mode 100644
--- /dev/null
+++ b/servo/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
+    }
+}
new file mode 100644
--- /dev/null
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -0,0 +1,704 @@
+/* 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, IN_VISITED_OR_UNVISITED_STATE};
+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;
+        }
+
+        // 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.
+            let mut data = self.data.as_mut().unwrap();
+            data.ensure_restyle().hint.insert(RestyleHint::restyle_subtree().into());
+        }
+
+        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_for_visited(
+                MatchingMode::Normal,
+                None,
+                VisitedHandlingMode::AllLinksVisitedAndUnvisited,
+                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 } => {
+                debug!(" > Invalidation matched completely");
+                invalidated_self = true;
+            }
+            CompoundSelectorMatchingResult::Matched { next_combinator_offset } => {
+                let next_combinator =
+                    invalidation.selector.combinator_at(next_combinator_offset);
+
+                if matches!(next_combinator, Combinator::PseudoElement) {
+                    let pseudo_selector =
+                        invalidation.selector
+                            .iter_raw_rev_from(next_combinator_offset - 1)
+                            .next()
+                            .unwrap();
+                    let pseudo = match *pseudo_selector {
+                        Component::PseudoElement(ref pseudo) => pseudo,
+                        _ => unreachable!("Someone seriously messed up selector parsing"),
+                    };
+
+                    // FIXME(emilio): This is not ideal, and could not be
+                    // accurate if we ever have stateful element-backed eager
+                    // pseudos.
+                    //
+                    // Ideally, we'd just remove element-backed eager pseudos
+                    // altogether, given they work fine without it. Only gotcha
+                    // is that we wouldn't style them in parallel, which may or
+                    // may not be an issue.
+                    //
+                    // Also, this could be more fine grained now (perhaps a
+                    // RESTYLE_PSEUDOS hint?).
+                    //
+                    // Note that we'll also restyle the pseudo-element because
+                    // it would match this invalidation.
+                    if pseudo.is_eager() {
+                        invalidated_self = true;
+                    }
+                }
+
+
+                let next_invalidation = Invalidation {
+                    selector: invalidation.selector.clone(),
+                    offset: next_combinator_offset,
+                };
+
+                debug!(" > Invalidation matched, next: {:?}, ({:?})",
+                        next_invalidation, next_combinator);
+                if next_combinator.is_ancestor() {
+                    descendant_invalidations.push(next_invalidation);
+                } else {
+                    sibling_invalidations.push(next_invalidation);
+                }
+            }
+            CompoundSelectorMatchingResult::NotMatched => {}
+        }
+
+        if invalidated_self {
+            if let Some(ref mut data) = self.data {
+                data.ensure_restyle().hint.insert(RESTYLE_SELF.into());
+            }
+        }
+
+        // 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,
+                    /* is_visited_dependent = */ false
+                );
+                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,
+                    dependency.state.intersects(IN_VISITED_OR_UNVISITED_STATE)
+                );
+                true
+            },
+        );
+    }
+
+    fn scan_dependency(
+        &mut self,
+        dependency: &Dependency,
+        is_visited_dependent: bool
+    ) {
+        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 {
+            return self.note_dependency(dependency);
+        }
+
+        // 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 state or attribute change of
+        // this element (for example, for things like [foo]:visited).
+        //
+        // NOTE: This thing is actually untested because testing it is flaky,
+        // see the tests that were added and then backed out in bug 1328509.
+        if is_visited_dependent && now_context.relevant_link_found {
+            then_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
+            let matched_then =
+                matches_selector(&dependency.selector,
+                                 dependency.selector_offset,
+                                 &dependency.hashes,
+                                 &self.wrapper,
+                                 &mut then_context,
+                                 &mut |_, _| {});
+
+            now_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
+            let matches_now =
+                matches_selector(&dependency.selector,
+                                 dependency.selector_offset,
+                                 &dependency.hashes,
+                                 &self.element,
+                                 &mut now_context,
+                                 &mut |_, _| {});
+            if matched_then != matches_now {
+                return 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
+    }
+}
new file mode 100644
--- /dev/null
+++ b/servo/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;
new file mode 100644
--- /dev/null
+++ b/servo/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,
+    }
+}
--- a/servo/components/style/invalidation/mod.rs
+++ b/servo/components/style/invalidation/mod.rs
@@ -1,8 +1,9 @@
 /* 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/. */
 
 //! Different bits of code related to invalidating style.
 
+pub mod element;
 pub mod media_queries;
 pub mod stylesheets;
--- a/servo/components/style/invalidation/stylesheets.rs
+++ b/servo/components/style/invalidation/stylesheets.rs
@@ -111,22 +111,47 @@ impl StylesheetInvalidationSet {
     }
 
     /// Clears the invalidation set, invalidating elements as needed if
     /// `document_element` is provided.
     pub fn flush<E>(&mut self, document_element: Option<E>)
         where E: TElement,
     {
         if let Some(e) = document_element {
-            self.process_invalidations_in_subtree(e);
+            self.process_invalidations(e);
         }
         self.invalid_scopes.clear();
         self.fully_invalid = false;
     }
 
+    fn process_invalidations<E>(&self, element: E) -> bool
+        where E: TElement,
+    {
+        {
+            let mut data = match element.mutate_data() {
+                Some(data) => data,
+                None => return false,
+            };
+
+            if self.fully_invalid {
+                debug!("process_invalidations: fully_invalid({:?})",
+                       element);
+                data.ensure_restyle().hint.insert(StoredRestyleHint::subtree());
+                return true;
+            }
+        }
+
+        if self.invalid_scopes.is_empty() {
+            debug!("process_invalidations: empty invalidation set");
+            return false;
+        }
+
+        self.process_invalidations_in_subtree(element)
+    }
+
     /// Process style invalidations in a given subtree, that is, look for all
     /// the relevant scopes in the subtree, and mark as dirty only the relevant
     /// ones.
     ///
     /// Returns whether it invalidated at least one element's style.
     #[allow(unsafe_code)]
     fn process_invalidations_in_subtree<E>(&self, element: E) -> bool
         where E: TElement,
@@ -143,23 +168,16 @@ impl StylesheetInvalidationSet {
         if let Some(ref r) = data.get_restyle() {
             if r.hint.contains_subtree() {
                 debug!("process_invalidations_in_subtree: {:?} was already invalid",
                        element);
                 return false;
             }
         }
 
-        if self.fully_invalid {
-            debug!("process_invalidations_in_subtree: fully_invalid({:?})",
-                   element);
-            data.ensure_restyle().hint.insert(StoredRestyleHint::subtree());
-            return true;
-        }
-
         for scope in &self.invalid_scopes {
             if scope.matches(element) {
                 debug!("process_invalidations_in_subtree: {:?} matched {:?}",
                        element, scope);
                 data.ensure_restyle().hint.insert(StoredRestyleHint::subtree());
                 return true;
             }
         }
--- a/servo/components/style/lib.rs
+++ b/servo/components/style/lib.rs
@@ -112,17 +112,16 @@ pub mod font_metrics;
 #[cfg(feature = "gecko")] #[allow(unsafe_code)] pub mod gecko_bindings;
 pub mod invalidation;
 #[allow(missing_docs)] // TODO.
 pub mod logical_geometry;
 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;
 pub mod selector_parser;
 pub mod shared_lock;
 pub mod sharing;
 pub mod stylist;
 #[cfg(feature = "servo")] #[allow(unsafe_code)] pub mod servo;
--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -8,23 +8,24 @@
 #![deny(missing_docs)]
 
 use applicable_declarations::ApplicableDeclarationList;
 use cascade_info::CascadeInfo;
 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};
 use selectors::matching::{VisitedHandlingMode, AFFECTED_BY_PSEUDO_ELEMENTS};
 use sharing::StyleSharingBehavior;
 use stylearc::Arc;
 use stylist::RuleInclusion;
 
@@ -985,16 +986,20 @@ pub trait MatchMethods : TElement {
                 }
                 let important_rules_changed =
                     self.has_animations() &&
                     data.has_styles() &&
                     data.important_rules_are_different(&rules,
                                                    &context.shared.guards);
 
                 let rules_changed = match visited_handling {
+                    VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                        unreachable!("We should never try to selector match with \
+                                     AllLinksVisitedAndUnvisited");
+                    },
                     VisitedHandlingMode::AllLinksUnvisited => {
                         data.set_primary_rules(rules)
                     },
                     VisitedHandlingMode::RelevantLinkVisited => {
                         data.styles_mut().primary.set_visited_rules(rules)
                     },
                 };
 
@@ -1064,16 +1069,20 @@ pub trait MatchMethods : TElement {
             self.has_animations() &&
             data.has_styles() &&
             data.important_rules_are_different(
                 &primary_rule_node,
                 &context.shared.guards
             );
 
         let rules_changed = match visited_handling {
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                unreachable!("We should never try to selector match with \
+                             AllLinksVisitedAndUnvisited");
+            },
             VisitedHandlingMode::AllLinksUnvisited => {
                 data.set_primary_rules(primary_rule_node)
             },
             VisitedHandlingMode::RelevantLinkVisited => {
                 data.styles_mut().primary.set_visited_rules(primary_rule_node)
             },
         };
 
@@ -1271,44 +1280,49 @@ pub trait MatchMethods : TElement {
                                    new_values,
                                    pseudo)
     }
 
     /// Updates the rule nodes without re-running selector matching, using just
     /// 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);
         if !context.shared.traversal_flags.for_animation_only() {
             result |= self.replace_rules_internal(replacements, context, data,
                                                   CascadeVisitedMode::Visited);
         }
         result
     }
 
     /// Updates the rule nodes without re-running selector matching, using just
     /// 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,
             None => return false,
         };
 
         let replace_rule_node = |level: CascadeLevel,
                                  pdb: Option<&Arc<Locked<PropertyDeclarationBlock>>>,
@@ -1339,17 +1353,17 @@ pub trait MatchMethods : TElement {
             return result;
         }
 
         // Animation restyle hints are processed prior to other restyle
         // hints in the animation-only traversal.
         //
         // 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) {
                 replace_rule_node(CascadeLevel::SMILOverride,
                                   self.get_smil_override(),
                                   primary_rules);
             }
 
deleted file mode 100644
--- a/servo/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
-    }
-}
--- a/servo/components/style/selector_map.rs
+++ b/servo/components/style/selector_map.rs
@@ -326,31 +326,31 @@ impl<T: SelectorMapEntry> SelectorMap<T>
     /// Each entry is passed to the callback, which returns true to continue
     /// iterating entries, or false to terminate the lookup.
     ///
     /// Returns false if the callback ever returns false.
     #[inline]
     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
         where E: TElement,
               F: FnMut(&T) -> bool
     {
         // Do the normal lookup.
         if !self.lookup(element, quirks_mode, f) {
             return false;
         }
 
         // 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;
                     }
                 }
             }
         }
 
@@ -463,16 +463,26 @@ impl<V> MaybeCaseInsensitiveHashMap<Atom
     /// HashMap::entry
     pub fn entry(&mut self, mut key: Atom, quirks_mode: QuirksMode) -> hash_map::Entry<Atom, V> {
         if quirks_mode == QuirksMode::Quirks {
             key = key.to_ascii_lowercase()
         }
         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 {
             self.0.get(&key.to_ascii_lowercase())
         } else {
             self.0.get(key)
         }
     }
--- a/servo/components/style/servo/selector_parser.rs
+++ b/servo/components/style/servo/selector_parser.rs
@@ -7,17 +7,17 @@
 //! Servo's selector parser.
 
 use {Atom, Prefix, Namespace, LocalName, CaseSensitivityExt};
 use attr::{AttrIdentifier, AttrValue};
 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};
 use selectors::parser::{SelectorMethods, SelectorParseError};
 use selectors::visitor::SelectorVisitor;
 use std::ascii::AsciiExt;
 use std::borrow::Cow;
 use std::fmt;
@@ -540,28 +540,52 @@ impl DerefMut for SnapshotMap {
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 pub struct ServoElementSnapshot {
     /// The stored state of the element.
     pub state: Option<ElementState>,
     /// The set of stored attributes and its values.
     pub attrs: Option<Vec<(AttrIdentifier, AttrValue)>>,
     /// Whether this element is an HTML element in an HTML document.
     pub is_html_element_in_html_document: bool,
+    /// Whether the class attribute changed or not.
+    pub class_changed: bool,
+    /// Whether the id attribute changed or not.
+    pub id_changed: bool,
+    /// Whether other attributes other than id or class changed or not.
+    pub other_attributes_changed: bool,
 }
 
 impl ServoElementSnapshot {
     /// Create an empty element snapshot.
     pub fn new(is_html_element_in_html_document: bool) -> Self {
         ServoElementSnapshot {
             state: None,
             attrs: None,
             is_html_element_in_html_document: is_html_element_in_html_document,
+            class_changed: false,
+            id_changed: false,
+            other_attributes_changed: false,
         }
     }
 
+    /// Returns whether the id attribute changed or not.
+    pub fn id_changed(&self) -> bool {
+        self.id_changed
+    }
+
+    /// Returns whether the class attribute changed or not.
+    pub fn class_changed(&self) -> bool {
+        self.class_changed
+    }
+
+    /// Returns whether other attributes other than id or class changed or not.
+    pub fn other_attr_changed(&self) -> bool {
+        self.other_attributes_changed
+    }
+
     fn get_attr(&self, namespace: &Namespace, name: &LocalName) -> Option<&AttrValue> {
         self.attrs.as_ref().unwrap().iter()
             .find(|&&(ref ident, _)| ident.local_name == *name &&
                                      ident.namespace == *namespace)
             .map(|&(_, ref v)| v)
     }
 
     fn any_attr_ignore_ns<F>(&self, name: &LocalName, mut f: F) -> bool
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -2,31 +2,31 @@
  * 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/. */
 
 //! Selector matching.
 
 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;
 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};
 use selectors::attr::NamespaceConstraint;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{ElementSelectorFlags, matches_selector, MatchingContext, MatchingMode};
 use selectors::matching::AFFECTED_BY_PRESENTATIONAL_HINTS;
 use selectors::parser::{AncestorHashes, Combinator, Component, Selector, SelectorAndHashes};
@@ -111,18 +111,18 @@ pub struct Stylist {
     ///
     /// FIXME(emilio): Use the rule tree!
     precomputed_pseudo_element_decls: FnvHashMap<PseudoElement, Vec<ApplicableDeclarationBlock>>,
 
     /// A monotonically increasing counter to represent the order on which a
     /// 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.
     /// (We don't bother storing the namespace, since namespaced attributes
     /// are rare.)
     ///
     /// FIXME(heycam): This doesn't really need to be a counting Bloom filter.
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "just an array")]
@@ -244,17 +244,17 @@ impl Stylist {
             effective_media_query_results: EffectiveMediaQueryResults::new(),
 
             element_map: PerPseudoElementSelectorMap::new(),
             pseudos_map: Default::default(),
             animations: Default::default(),
             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(),
             mapped_ids: BloomFilter::new(),
             selectors_for_cache_revalidation: SelectorMap::new(),
             num_selectors: 0,
             num_declarations: 0,
             num_rebuilds: 0,
@@ -279,26 +279,26 @@ impl Stylist {
         self.num_declarations
     }
 
     /// Returns the number of times the stylist has been rebuilt.
     pub fn num_rebuilds(&self) -> usize {
         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.
     ///
     /// We preserve the state of the following members:
     ///   device: Someone might have set this on us.
     ///   quirks_mode: Again, someone might have set this on us.
     ///   num_rebuilds: clear() followed by rebuild() should just increment this
     ///
@@ -319,17 +319,17 @@ impl Stylist {
         self.is_device_dirty = true;
         // preserve current quirks_mode value
         self.element_map = PerPseudoElementSelectorMap::new();
         self.pseudos_map = Default::default();
         self.animations.clear(); // Or set to Default::default()?
         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();
         self.mapped_ids.clear();
         self.selectors_for_cache_revalidation = SelectorMap::new();
         self.num_selectors = 0;
         self.num_declarations = 0;
         // preserve num_rebuilds value, since it should stay across
@@ -479,17 +479,17 @@ impl Stylist {
 
                         map.insert(
                             Rule::new(selector_and_hashes.selector.clone(),
                                       selector_and_hashes.hashes.clone(),
                                       locked.clone(),
                                       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),
                                 self.quirks_mode);
                         }
                         selector_and_hashes.selector.visit(&mut AttributeAndStateDependencyVisitor {
                             attribute_dependencies: &mut self.attribute_dependencies,
                             style_attribute_dependency: &mut self.style_attribute_dependency,
@@ -1196,29 +1196,16 @@ impl Stylist {
                                               flags_setter));
                 true
             }
         );
 
         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,
                                     parent_style: &Arc<ComputedValues>,
                                     declarations: Arc<Locked<PropertyDeclarationBlock>>)
                                     -> Arc<ComputedValues> {
         use font_metrics::get_metrics_provider_for_product;
 
--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -3,19 +3,18 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Traversing the DOM tree; the bloom filter.
 
 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;
 use smallvec::SmallVec;
 use std::borrow::BorrowMut;
 
 /// A per-traversal-level chunk of data. This is sent down by the traversal, and
 /// currently only holds the dom depth for the bloom filter.
@@ -237,34 +236,21 @@ pub trait DomTraversal<E: TElement> : Sy
                 };
             }
             return PreTraverseToken {
                 traverse: true,
                 unstyled_children_only: true,
             };
         }
 
-        // 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 {
             traverse: Self::node_needs_traversal(root.as_node(), traversal_flags),
             unstyled_children_only: false,
         }
     }
 
@@ -663,42 +649,39 @@ pub fn recalc_style_at<E, D>(traversal: 
                              data: &mut ElementData)
     where E: TElement,
           D: DomTraversal<E>
 {
     context.thread_local.begin_element(element, data);
     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);
 
     // Compute style for this element if necessary.
     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 => {}
         };
 
         // 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
         // data in the subtree, notify the caller to early-return.
         if data.styles().is_display_none() {
             debug!("{:?} style is display:none - clearing data from descendants.",
                    element);
             clear_descendant_data(element, &|e| unsafe { D::clear_element_data(&e) });
@@ -715,48 +698,48 @@ pub fn recalc_style_at<E, D>(traversal: 
                           "animation restyle hint should be handled during \
                            animation-only restyles");
             r.hint.propagate(&context.shared.traversal_flags)
         },
     };
 
     // 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) ||
                   context.shared.traversal_flags.for_animation_only(),
                   "Should have computed style or haven't yet valid computed \
                    style in case of animation-only restyle");
 
     let has_dirty_descendants_for_this_restyle =
         if context.shared.traversal_flags.for_animation_only() {
             element.has_animation_only_dirty_descendants()
         } else {
             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,
                                           DontLog) &&
         (has_dirty_descendants_for_this_restyle ||
          !propagated_hint.is_empty()) {
         let damage_handled = data.get_restyle().map_or(RestyleDamage::empty(), |r| {
             r.damage_handled() | r.damage.handled_for_descendants()
         });
 
         preprocess_children::<E, D>(context,
-                                    traversal_data,
                                     element,
                                     propagated_hint,
                                     damage_handled);
     }
 
     // If we are in a restyle for reconstruction, drop the existing restyle
     // data here, since we won't need to perform a post-traversal to pick up
     // any change hints.
@@ -848,19 +831,18 @@ fn compute_style<E, D>(_traversal: &D,
                 data,
                 /* important_rules_changed = */ false
             )
         }
     }
 }
 
 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>,
 {
     trace!("preprocess_children: {:?}", element);
 
     // Loop over all the traversal children.
     for child in element.as_node().traversal_children() {
@@ -873,49 +855,42 @@ fn preprocess_children<E, D>(context: &m
         let mut child_data =
             unsafe { D::ensure_element_data(&child).borrow_mut() };
 
         // If the child is unstyled, we don't need to set up any restyling.
         if !child_data.has_styles() {
             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,
-                                          });
+        child_data.invalidate_style_if_needed(child, &context.shared);
 
-        trace!(" > {:?} -> {:?} + {:?}, pseudo: {:?}, later_siblings: {:?}",
+        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);
     }
 }
 
 /// Clear style data for all the subtree under `el`.
 pub fn clear_descendant_data<E: TElement, F: Fn(E)>(el: E, clear_data: &F) {
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -83,25 +83,25 @@ use style::gecko_bindings::structs::nsCS
 use style::gecko_bindings::structs::nsCompatibility;
 use style::gecko_bindings::structs::nsIDocument;
 use style::gecko_bindings::structs::nsStyleTransformMatrix::MatrixTransformOperator;
 use style::gecko_bindings::structs::nsresult;
 use style::gecko_bindings::sugar::ownership::{FFIArcHelpers, HasFFI, HasArcFFI, HasBoxFFI};
 use style::gecko_bindings::sugar::ownership::{HasSimpleFFI, Strong};
 use style::gecko_bindings::sugar::refptr::RefPtr;
 use style::gecko_properties::{self, style_structs};
+use style::invalidation::element::restyle_hints::{self, RestyleHint};
 use style::media_queries::{MediaList, parse_media_query_list};
 use style::parallel;
 use style::parser::{PARSING_MODE_DEFAULT, ParserContext};
 use style::properties::{CascadeFlags, ComputedValues, Importance, SourcePropertyDeclaration};
 use style::properties::{LonghandIdSet, PropertyDeclaration, PropertyDeclarationBlock, PropertyId, StyleBuilder};
 use style::properties::SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP;
 use style::properties::animated_properties::{Animatable, AnimationValue, TransitionProperty};
 use style::properties::parse_one_declaration_into;
-use style::restyle_hints::{self, RestyleHint};
 use style::rule_tree::StyleSource;
 use style::selector_parser::PseudoElementCascadeType;
 use style::sequential;
 use style::shared_lock::{SharedRwLock, SharedRwLockReadGuard, StylesheetGuards, ToCssWithGuard, Locked};
 use style::string_cache::Atom;
 use style::style_adjuster::StyleAdjuster;
 use style::stylearc::Arc;
 use style::stylesheets::{CssRule, CssRules, CssRuleType, CssRulesHelpers, DocumentRule};
--- a/servo/tests/unit/style/lib.rs
+++ b/servo/tests/unit/style/lib.rs
@@ -24,17 +24,16 @@ extern crate test;
 
 mod animated_properties;
 mod attr;
 mod keyframes;
 mod logical_geometry;
 mod media_queries;
 mod parsing;
 mod properties;
-mod restyle_hints;
 mod rule_tree;
 mod size_of;
 mod str;
 mod stylesheets;
 mod stylist;
 mod viewport;
 
 mod writing_modes {
deleted file mode 100644
--- a/servo/tests/unit/style/restyle_hints.rs
+++ /dev/null
@@ -1,30 +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/. */
-
-use style::context::QuirksMode;
-
-#[test]
-fn smoke_restyle_hints() {
-    use cssparser::{Parser, ParserInput};
-    use selectors::parser::SelectorList;
-    use style::restyle_hints::DependencySet;
-    use style::selector_parser::SelectorParser;
-    use style::stylesheets::{Origin, Namespaces};
-    let namespaces = Namespaces::default();
-    let parser = SelectorParser {
-        stylesheet_origin: Origin::Author,
-        namespaces: &namespaces,
-    };
-
-    let mut dependencies = DependencySet::new();
-
-    let mut input = ParserInput::new(":not(:active) ~ label");
-    let mut p = Parser::new(&mut input);
-    let selectors = SelectorList::parse(&parser, &mut p).unwrap();
-    assert_eq!((selectors.0).len(), 1);
-
-    let selector = (selectors.0).first().unwrap();
-    dependencies.note_selector(selector, QuirksMode::NoQuirks);
-    assert_eq!(dependencies.len(), 1);
-}