--- a/servo/components/style/bloom.rs
+++ b/servo/components/style/bloom.rs
@@ -117,16 +117,22 @@ impl<E: TElement> StyleBloom<E> {
         popped
     }
 
     /// Returns true if the bloom filter is empty.
     pub fn is_empty(&self) -> bool {
         self.elements.is_empty()
     }
 
+    /// Returns the DOM depth of elements that can be correctly
+    /// matched against the bloom filter (that is, the number of
+    /// elements in our list).
+    pub fn matching_depth(&self) -> usize {
+        self.elements.len()
+    }
 
     /// Clears the bloom filter.
     pub fn clear(&mut self) {
         self.filter.clear();
         self.elements.clear();
     }
 
     /// Rebuilds the bloom filter up to the parent of the given element.

--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -791,17 +791,18 @@ impl MatchingResults {
 
 /// The public API that elements expose for selector matching.
 pub trait MatchMethods : TElement {
     /// Performs selector matching and property cascading on an element and its
     /// eager pseudos.
     fn match_and_cascade(&self,
                          context: &mut StyleContext<Self>,
                          data: &mut ElementData,
-                         sharing: StyleSharingBehavior)
+                         sharing: StyleSharingBehavior,
+                         dom_depth: usize)
                          -> ChildCascadeRequirement
     {
         debug!("Match and cascade for {:?}", self);
 
         // Perform selector matching for the primary style.
         let mut primary_results =
             self.match_primary(context, data, VisitedHandlingMode::AllLinksUnvisited);
         let important_rules_changed =
@@ -862,17 +863,18 @@ pub trait MatchMethods : TElement {
                     .validation_data
                     .take();
 
             context.thread_local
                    .style_sharing_candidate_cache
                    .insert_if_possible(self,
                                        data.styles().primary.values(),
                                        primary_results.relations,
-                                       validation_data);
+                                       validation_data,
+                                       dom_depth);
         }
 
         child_cascade_requirement
     }
 
     /// Performs the cascade, without matching.
     fn cascade_primary_and_pseudos(&self,
                                    context: &mut StyleContext<Self>,

--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -315,28 +315,36 @@ impl<E: TElement> StyleSharingTarget<E> 
             true,
             &mut set_selector_flags)
     }
 
     /// Attempts to share a style with another node.
     pub fn share_style_if_possible(
         mut self,
         context: &mut StyleContext<E>,
-        data: &mut ElementData)
+        data: &mut ElementData,
+        dom_depth: usize)
         -> StyleSharingResult
     {
+        let cache = &mut context.thread_local.style_sharing_candidate_cache;
+        if cache.dom_depth != dom_depth {
+            debug!("Can't share style, because DOM depth changed from {:?} to {:?}, element: {:?}",
+                   cache.dom_depth, dom_depth, self.element);
+            return StyleSharingResult::CannotShare;
+        }
         let shared_context = &context.shared;
         let selector_flags_map = &mut context.thread_local.selector_flags;
         let bloom_filter = &context.thread_local.bloom_filter;
 
         debug_assert_eq!(bloom_filter.current_parent(),
                          self.element.parent_element());
+        debug_assert_eq!(bloom_filter.matching_depth(),
+                         dom_depth);
 
-        let result = context.thread_local
-            .style_sharing_candidate_cache
+        let result = cache
             .share_style_if_possible(shared_context,
                                      selector_flags_map,
                                      bloom_filter,
                                      &mut self,
                                      data);
 
 
         context.thread_local.current_element_info.as_mut().unwrap().validation_data =
@@ -390,23 +398,28 @@ pub enum StyleSharingResult {
 
 /// An LRU cache of the last few nodes seen, so that we can aggressively try to
 /// reuse their styles.
 ///
 /// Note that this cache is flushed every time we steal work from the queue, so
 /// storing nodes here temporarily is safe.
 pub struct StyleSharingCandidateCache<E: TElement> {
     cache: LRUCache<StyleSharingCandidate<E>>,
+    /// The DOM depth we're currently at.  This is used as an optimization to
+    /// clear the cache when we change depths, since we know at that point
+    /// nothing in the cache will match.
+    pub dom_depth: usize,
 }
 
 impl<E: TElement> StyleSharingCandidateCache<E> {
     /// Create a new style sharing candidate cache.
     pub fn new() -> Self {
         StyleSharingCandidateCache {
             cache: LRUCache::new(STYLE_SHARING_CANDIDATE_CACHE_SIZE),
+            dom_depth: 0,
         }
     }
 
     /// Returns the number of entries in the cache.
     pub fn num_entries(&self) -> usize {
         self.cache.num_entries()
     }
 
@@ -416,17 +429,18 @@ impl<E: TElement> StyleSharingCandidateC
 
     /// Tries to insert an element in the style sharing cache.
     ///
     /// Fails if we know it should never be in the cache.
     pub fn insert_if_possible(&mut self,
                               element: &E,
                               style: &ComputedValues,
                               relations: StyleRelations,
-                              mut validation_data: ValidationData) {
+                              mut validation_data: ValidationData,
+                              dom_depth: usize) {
         use selectors::matching::AFFECTED_BY_PRESENTATIONAL_HINTS;
 
         let parent = match element.parent_element() {
             Some(element) => element,
             None => {
                 debug!("Failing to insert to the cache: no parent element");
                 return;
             }
@@ -459,16 +473,22 @@ impl<E: TElement> StyleSharingCandidateC
         // selector-matching.
         if !relations.intersects(AFFECTED_BY_PRESENTATIONAL_HINTS) {
             debug_assert!(validation_data.pres_hints.as_ref().map_or(true, |v| v.is_empty()));
             validation_data.pres_hints = Some(SmallVec::new());
         }
 
         debug!("Inserting into cache: {:?} with parent {:?}", element, parent);
 
+        if self.dom_depth != dom_depth {
+            debug!("Clearing cache because depth changed from {:?} to {:?}, element: {:?}",
+                   self.dom_depth, dom_depth, element);
+            self.clear();
+            self.dom_depth = dom_depth;
+        }
         self.cache.insert(StyleSharingCandidate {
             element: unsafe { SendElement::new(*element) },
             validation_data: validation_data,
         });
     }
 
     /// Touch a given index in the style sharing candidate cache.
     pub fn touch(&mut self, index: usize) {
@@ -501,17 +521,16 @@ impl<E: TElement> StyleSharingCandidateC
             return StyleSharingResult::CannotShare
         }
 
         if target.is_native_anonymous() {
             debug!("{:?} Cannot share style: NAC", target.element);
             return StyleSharingResult::CannotShare;
         }
 
-        let mut should_clear_cache = false;
         for (i, candidate) in self.iter_mut().enumerate() {
             let sharing_result =
                 Self::test_candidate(
                     target,
                     candidate,
                     &shared_context,
                     bloom_filter,
                     selector_flags_map
@@ -545,38 +564,29 @@ impl<E: TElement> StyleSharingCandidateC
                     return StyleSharingResult::StyleWasShared(i, child_cascade_requirement)
                 }
                 Err(miss) => {
                     debug!("Cache miss: {:?}", miss);
 
                     // Cache miss, let's see what kind of failure to decide
                     // whether we keep trying or not.
                     match miss {
-                        // Cache miss because of parent, clear the candidate cache.
-                        CacheMiss::Parent => {
-                            should_clear_cache = true;
-                            break;
-                        },
                         // Too expensive failure, give up, we don't want another
                         // one of these.
                         CacheMiss::PresHints |
                         CacheMiss::Revalidation => break,
                         _ => {}
                     }
                 }
             }
         }
 
         debug!("{:?} Cannot share style: {} cache entries", target.element,
                self.cache.num_entries());
 
-        if should_clear_cache {
-            self.clear();
-        }
-
         StyleSharingResult::CannotShare
     }
 
     fn test_candidate(target: &mut StyleSharingTarget<E>,
                       candidate: &mut StyleSharingCandidate<E>,
                       shared: &SharedStyleContext,
                       bloom: &StyleBloom<E>,
                       selector_flags_map: &mut SelectorFlagsMap<E>)

--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -537,19 +537,21 @@ fn resolve_style_internal<E, F>(context:
             context.thread_local.bloom_filter.rebuild(element);
         } else {
             context.thread_local.bloom_filter.push(parent.unwrap());
             context.thread_local.bloom_filter.assert_complete(element);
         }
 
         // Compute our style.
         context.thread_local.begin_element(element, &data);
+        let dom_depth = context.thread_local.bloom_filter.matching_depth();
         element.match_and_cascade(context,
                                   &mut data,
-                                  StyleSharingBehavior::Disallow);
+                                  StyleSharingBehavior::Disallow,
+                                  dom_depth);
         context.thread_local.end_element(element);
 
         if !context.shared.traversal_flags.for_default_styles() {
             // Conservatively mark us as having dirty descendants, since there might
             // be other unstyled siblings we miss when walking straight up the parent
             // chain.  No need to do this if we're computing default styles, since
             // resolve_default_style will want the tree to be left as it is.
             unsafe { element.note_descendants::<DirtyDescendants>() };
@@ -804,31 +806,34 @@ fn compute_style<E, D>(_traversal: &D,
                    .insert_parents_recovering(element,
                                               traversal_data.current_dom_depth);
 
             context.thread_local.bloom_filter.assert_complete(element);
 
             // Now that our bloom filter is set up, try the style sharing
             // cache. If we get a match we can skip the rest of the work.
             let target = StyleSharingTarget::new(element);
-            let sharing_result = target.share_style_if_possible(context, data);
+            let sharing_result =
+                target.share_style_if_possible(context, data,
+                                               traversal_data.current_dom_depth);
 
             if let StyleWasShared(index, had_damage) = sharing_result {
                 context.thread_local.statistics.styles_shared += 1;
                 context.thread_local.style_sharing_candidate_cache.touch(index);
                 return had_damage;
             }
 
             context.thread_local.statistics.elements_matched += 1;
 
             // Perform the matching and cascading.
             element.match_and_cascade(
                 context,
                 data,
-                StyleSharingBehavior::Allow
+                StyleSharingBehavior::Allow,
+                traversal_data.current_dom_depth
             )
         }
         CascadeWithReplacements(flags) => {
             let important_rules_changed = element.replace_rules(flags, context, data);
             element.cascade_primary_and_pseudos(
                 context,
                 data,
                 important_rules_changed