--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -383,16 +383,21 @@ impl StoredRestyleHint {
         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)
     }
 
     /// Returns true if the hint has animation-only restyle.
     pub fn has_animation_hint(&self) -> bool {
         self.0.has_animation_hint()

--- a/servo/components/style/invalidation/mod.rs
+++ b/servo/components/style/invalidation/mod.rs
@@ -12,17 +12,17 @@ use dom::{TElement, TNode};
 use fnv::FnvHashSet;
 use selector_parser::SelectorImpl;
 use selectors::parser::{Component, Selector};
 use shared_lock::SharedRwLockReadGuard;
 use stylesheets::{CssRule, CssRules, Stylesheet};
 use stylist::Stylist;
 
 /// A style scope represents a kind of subtree that may need to be restyled.
-#[derive(Hash, Eq, PartialEq)]
+#[derive(Debug, Hash, Eq, PartialEq)]
 enum InvalidationScope {
     /// All the descendants of an element with a given id.
     ID(Atom),
     /// All the descendants of an element with a given class name.
     Class(Atom),
 }
 
 impl InvalidationScope {
@@ -64,39 +64,49 @@ impl StylesheetInvalidationSet {
         Self {
             invalid_scopes: FnvHashSet::default(),
             fully_invalid: false,
         }
     }
 
     /// Mark the DOM tree styles' as fully invalid.
     pub fn invalidate_fully(&mut self) {
+        debug!("StylesheetInvalidationSet::invalidate_fully");
         self.invalid_scopes.clear();
         self.fully_invalid = true;
     }
 
     /// Analyze the given stylesheet, and collect invalidations from their
     /// rules, in order to avoid doing a full restyle when we style the document
     /// next time.
     pub fn collect_invalidations_for(
         &mut self,
         stylist: &Stylist,
         stylesheet: &Stylesheet,
         guard: &SharedRwLockReadGuard)
     {
-        if self.fully_invalid ||
-           stylesheet.disabled() ||
+        debug!("StylesheetInvalidationSet::collect_invalidations_for");
+        if self.fully_invalid {
+            debug!(" > Fully invalid already");
+            return;
+        }
+
+        if stylesheet.disabled() ||
            !stylesheet.is_effective_for_device(stylist.device(), guard) {
+            debug!(" > Stylesheet was not effective");
             return; // Nothing to do here.
         }
 
         self.collect_invalidations_for_rule_list(
             stylesheet.rules.read_with(guard),
             stylist,
             guard);
+
+        debug!(" > resulting invalidations: {:?}", self.invalid_scopes);
+        debug!(" > fully_invalid: {}", self.fully_invalid);
     }
 
     /// 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 {
@@ -119,23 +129,35 @@ impl StylesheetInvalidationSet {
             Some(data) => data,
             None => return false,
         };
 
         if !data.has_styles() {
             return false;
         }
 
+        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;
             }
         }
 
 
         let mut any_children_invalid = false;
 
@@ -144,16 +166,18 @@ impl StylesheetInvalidationSet {
                 Some(e) => e,
                 None => continue,
             };
 
             any_children_invalid |= self.process_invalidations_in_subtree(child);
         }
 
         if any_children_invalid {
+            debug!("Children of {:?} changed, setting dirty descendants",
+                   element);
             unsafe { element.set_dirty_descendants() }
         }
 
         return any_children_invalid
     }
 
     /// Collects invalidations for a given list of CSS rules.
     fn collect_invalidations_for_rule_list(
@@ -164,50 +188,73 @@ impl StylesheetInvalidationSet {
     {
         for rule in &rules.0 {
             if !self.collect_invalidations_for_rule(rule, stylist, guard) {
                 return;
             }
         }
     }
 
+    fn scan_component(
+        component: &Component<SelectorImpl>,
+        scope: &mut Option<InvalidationScope>)
+    {
+        match *component {
+            Component::Class(ref class) => {
+                if scope.as_ref().map_or(true, |s| !s.is_id()) {
+                    *scope = Some(InvalidationScope::Class(class.clone()));
+                }
+            }
+            Component::ID(ref id) => {
+                if scope.is_none() {
+                    *scope = Some(InvalidationScope::ID(id.clone()));
+                }
+            }
+            _ => {
+                // Ignore everything else, at least for now.
+            }
+        }
+    }
+
     /// Collect a style scopes for a given selector.
     ///
     /// We look at the outermost class or id selector to the left of an ancestor
     /// combinator, in order to restyle only a given subtree.
     ///
     /// We prefer id scopes to class scopes, and outermost scopes to innermost
     /// scopes (to reduce the amount of traversal we need to do).
     fn collect_scopes(&mut self, selector: &Selector<SelectorImpl>) {
+        debug!("StylesheetInvalidationSet::collect_scopes({:?})", selector);
+
         let mut scope: Option<InvalidationScope> = None;
 
-        let iter = selector.inner.complex.iter_ancestors();
-        for component in iter {
-            match *component {
-                Component::Class(ref class) => {
-                    if scope.as_ref().map_or(true, |s| !s.is_id()) {
-                        scope = Some(InvalidationScope::Class(class.clone()));
-                    }
+        let mut scan = true;
+        let mut iter = selector.inner.complex.iter();
+
+        loop {
+            for component in &mut iter {
+                if scan {
+                    Self::scan_component(component, &mut scope);
                 }
-                Component::ID(ref id) => {
-                    if scope.is_none() {
-                        scope = Some(InvalidationScope::ID(id.clone()));
-                    }
-                }
-                _ => {
-                    // Ignore everything else, at least for now.
+            }
+            match iter.next_sequence() {
+                None => break,
+                Some(combinator) => {
+                    scan = combinator.is_ancestor();
                 }
             }
         }
 
         match scope {
             Some(s) => {
+                debug!(" > Found scope: {:?}", s);
                 self.invalid_scopes.insert(s);
             }
             None => {
+                debug!(" > Scope not found");
                 // If we didn't found a scope, any selector could match this, so
                 // let's just bail out.
                 self.fully_invalid = true;
             }
         }
     }
 
     /// Collects invalidations for a given CSS rule.
@@ -217,16 +264,17 @@ impl StylesheetInvalidationSet {
     fn collect_invalidations_for_rule(
         &mut self,
         rule: &CssRule,
         stylist: &Stylist,
         guard: &SharedRwLockReadGuard)
         -> bool
     {
         use stylesheets::CssRule::*;
+        debug!("StylesheetInvalidationSet::collect_invalidations_for_rule");
         debug_assert!(!self.fully_invalid, "Not worth to be here!");
 
         match *rule {
             Document(ref lock) => {
                 let doc_rule = lock.read_with(guard);
                 if !doc_rule.condition.evaluate(stylist.device()) {
                     return false; // Won't apply anything else after this.
                 }
@@ -270,16 +318,17 @@ impl StylesheetInvalidationSet {
                     stylist,
                     guard);
             }
             FontFace(..) |
             CounterStyle(..) |
             Keyframes(..) |
             Page(..) |
             Viewport(..) => {
+                debug!(" > Found unsupported rule, marking the whole subtree invalid.");
                 // TODO(emilio): Can we do better here?
                 //
                 // At least in `@page`, we could check the relevant media, I
                 // guess.
                 self.fully_invalid = true;
             }
         }
 

--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -363,17 +363,17 @@ impl RestyleHint {
         // A later patch should make it worthwhile to have an insert() function
         // that consumes its argument.
         self.insert_from(&other)
     }
 
     /// Returns whether this `RestyleHint` represents at least as much restyle
     /// work as the specified one.
     #[inline]
-    pub fn contains(&mut self, other: &Self) -> bool {
+    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.replacements.contains(other.replacements)
     }
 }
 
 impl RestyleReplacements {
     /// The replacements for the animation cascade levels.

--- a/servo/components/style/stylesheet_set.rs
+++ b/servo/components/style/stylesheet_set.rs
@@ -73,16 +73,17 @@ impl StylesheetSet {
     /// Appends a new stylesheet to the current set.
     pub fn append_stylesheet(
         &mut self,
         stylist: &Stylist,
         sheet: &Arc<Stylesheet>,
         unique_id: u64,
         guard: &SharedRwLockReadGuard)
     {
+        debug!("StylesheetSet::append_stylesheet");
         self.remove_stylesheet_if_present(unique_id);
         self.entries.push(StylesheetSetEntry {
             unique_id: unique_id,
             sheet: sheet.clone(),
         });
         self.dirty = true;
         self.invalidations.collect_invalidations_for(
             stylist,
@@ -93,16 +94,17 @@ impl StylesheetSet {
     /// Prepend a new stylesheet to the current set.
     pub fn prepend_stylesheet(
         &mut self,
         stylist: &Stylist,
         sheet: &Arc<Stylesheet>,
         unique_id: u64,
         guard: &SharedRwLockReadGuard)
     {
+        debug!("StylesheetSet::prepend_stylesheet");
         self.remove_stylesheet_if_present(unique_id);
         self.entries.insert(0, StylesheetSetEntry {
             unique_id: unique_id,
             sheet: sheet.clone(),
         });
         self.dirty = true;
         self.invalidations.collect_invalidations_for(
             stylist,
@@ -114,16 +116,17 @@ impl StylesheetSet {
     pub fn insert_stylesheet_before(
         &mut self,
         stylist: &Stylist,
         sheet: &Arc<Stylesheet>,
         unique_id: u64,
         before_unique_id: u64,
         guard: &SharedRwLockReadGuard)
     {
+        debug!("StylesheetSet::insert_stylesheet_before");
         self.remove_stylesheet_if_present(unique_id);
         let index = self.entries.iter().position(|x| {
             x.unique_id == before_unique_id
         }).expect("`before_unique_id` stylesheet not found");
         self.entries.insert(index, StylesheetSetEntry {
             unique_id: unique_id,
             sheet: sheet.clone(),
         });
@@ -131,24 +134,26 @@ impl StylesheetSet {
         self.invalidations.collect_invalidations_for(
             stylist,
             sheet,
             guard)
     }
 
     /// Remove a given stylesheet from the set.
     pub fn remove_stylesheet(&mut self, unique_id: u64) {
+        debug!("StylesheetSet::remove_stylesheet");
         self.remove_stylesheet_if_present(unique_id);
         self.dirty = true;
         // FIXME(emilio): We can do better!
         self.invalidations.invalidate_fully();
     }
 
     /// Notes that the author style has been disabled for this document.
     pub fn set_author_style_disabled(&mut self, disabled: bool) {
+        debug!("StylesheetSet::set_author_style_disabled");
         if self.author_style_disabled == disabled {
             return;
         }
         self.author_style_disabled = disabled;
         self.dirty = true;
         self.invalidations.invalidate_fully();
     }
 
@@ -159,16 +164,17 @@ impl StylesheetSet {
 
     /// Flush the current set, unmarking it as dirty, and returns an iterator
     /// over the new stylesheet list.
     pub fn flush<E>(&mut self,
                     document_element: Option<E>)
                     -> StylesheetIterator
         where E: TElement,
     {
+        debug!("StylesheetSet::flush");
         debug_assert!(self.dirty);
 
         self.dirty = false;
         self.invalidations.flush(document_element);
 
         StylesheetIterator(self.entries.iter())
     }