--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -101,20 +101,24 @@ impl RestyleData {
 
     /// Returns whether any ancestor of this element is going to be
     /// reconstructed.
     fn reconstructed_ancestor(&self) -> bool {
         self.flags.contains(ANCESTOR_WAS_RECONSTRUCTED)
     }
 
     /// Sets the flag that tells us whether we've reconstructed an ancestor.
-    pub fn set_reconstructed_ancestor(&mut self) {
-        // If it weren't for animation-only traversals, we could assert
-        // `!self.reconstructed_ancestor()` here.
-        self.flags.insert(ANCESTOR_WAS_RECONSTRUCTED);
+    pub fn set_reconstructed_ancestor(&mut self, reconstructed: bool) {
+        if reconstructed {
+            // If it weren't for animation-only traversals, we could assert
+            // `!self.reconstructed_ancestor()` here.
+            self.flags.insert(ANCESTOR_WAS_RECONSTRUCTED);
+        } else {
+            self.flags.remove(ANCESTOR_WAS_RECONSTRUCTED);
+        }
     }
 
     /// Mark this element as restyled, which is useful to know whether we need
     /// to do a post-traversal.
     pub fn set_restyled(&mut self) {
         self.flags.insert(WAS_RESTYLED);
         self.flags.remove(TRAVERSED_WITHOUT_STYLING);
     }

--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -508,16 +508,23 @@ pub trait TElement : Eq + PartialEq + De
     }
 
     /// Flag that this element has no descendant for animation-only restyle processing.
     ///
     /// Only safe to call with exclusive access to the element.
     unsafe fn unset_animation_only_dirty_descendants(&self) {
     }
 
+    /// Clear all bits related to dirty descendant.
+    ///
+    /// In Gecko, this corresponds to the regular dirty descendants bit, the
+    /// animation-only dirty descendants bit, and the lazy frame construction
+    /// descendants bit.
+    unsafe fn clear_descendants_bits(&self) { self.unset_dirty_descendants(); }
+
     /// Returns true if this element is a visited link.
     ///
     /// Servo doesn't support visited styles yet.
     fn is_visited_link(&self) -> bool { false }
 
     /// Returns true if this element is native anonymous (only Gecko has native
     /// anonymous content).
     fn is_native_anonymous(&self) -> bool { false }

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -56,16 +56,17 @@ use gecko_bindings::bindings::Gecko_Upda
 use gecko_bindings::structs;
 use gecko_bindings::structs::{RawGeckoElement, RawGeckoNode, RawGeckoXBLBinding};
 use gecko_bindings::structs::{nsIAtom, nsIContent, nsINode_BooleanFlag, nsStyleContext};
 use gecko_bindings::structs::ELEMENT_HANDLED_SNAPSHOT;
 use gecko_bindings::structs::ELEMENT_HAS_ANIMATION_ONLY_DIRTY_DESCENDANTS_FOR_SERVO;
 use gecko_bindings::structs::ELEMENT_HAS_DIRTY_DESCENDANTS_FOR_SERVO;
 use gecko_bindings::structs::ELEMENT_HAS_SNAPSHOT;
 use gecko_bindings::structs::EffectCompositor_CascadeLevel as CascadeLevel;
+use gecko_bindings::structs::NODE_DESCENDANTS_NEED_FRAMES;
 use gecko_bindings::structs::NODE_IS_IN_NATIVE_ANONYMOUS_SUBTREE;
 use gecko_bindings::structs::NODE_IS_NATIVE_ANONYMOUS;
 use gecko_bindings::structs::nsChangeHint;
 use gecko_bindings::structs::nsIDocument_DocumentTheme as DocumentTheme;
 use gecko_bindings::structs::nsRestyleHint;
 use gecko_bindings::sugar::ownership::{HasArcFFI, HasSimpleFFI};
 use logical_geometry::WritingMode;
 use media_queries::Device;
@@ -1047,16 +1048,22 @@ impl<'le> TElement for GeckoElement<'le>
     unsafe fn set_animation_only_dirty_descendants(&self) {
         self.set_flags(ELEMENT_HAS_ANIMATION_ONLY_DIRTY_DESCENDANTS_FOR_SERVO as u32)
     }
 
     unsafe fn unset_animation_only_dirty_descendants(&self) {
         self.unset_flags(ELEMENT_HAS_ANIMATION_ONLY_DIRTY_DESCENDANTS_FOR_SERVO as u32)
     }
 
+    unsafe fn clear_descendants_bits(&self) {
+        self.unset_flags(ELEMENT_HAS_DIRTY_DESCENDANTS_FOR_SERVO as u32 |
+                         ELEMENT_HAS_ANIMATION_ONLY_DIRTY_DESCENDANTS_FOR_SERVO as u32 |
+                         NODE_DESCENDANTS_NEED_FRAMES as u32)
+    }
+
     fn is_visited_link(&self) -> bool {
         use element_state::IN_VISITED_STATE;
         self.get_state().intersects(IN_VISITED_STATE)
     }
 
     fn is_native_anonymous(&self) -> bool {
         self.flags() & (NODE_IS_NATIVE_ANONYMOUS as u32) != 0
     }

--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -165,16 +165,22 @@ pub trait DomTraversal<E: TElement> : Sy
         let flags = shared_context.traversal_flags;
         let mut data = root.mutate_data();
         let mut data = data.as_mut().map(|d| &mut **d);
 
         if let Some(ref mut data) = data {
             // Invalidate our style, and the one of our siblings and descendants
             // as needed.
             data.invalidate_style_if_needed(root, shared_context);
+
+            // Make sure we don't have any stale RECONSTRUCTED_ANCESTOR bits from
+            // the last traversal (at a potentially-higher root). From the
+            // perspective of this traversal, the root cannot have reconstructed
+            // ancestors.
+            data.restyle.set_reconstructed_ancestor(false);
         };
 
         let parent = root.traversal_parent();
         let parent_data = parent.as_ref().and_then(|p| p.borrow_data());
         let should_traverse = Self::element_needs_traversal(
             root,
             flags,
             data.map(|d| &*d),
@@ -586,39 +592,39 @@ where
 
     // If we are in a forgetful traversal, drop the existing restyle
     // data here, since we won't need to perform a post-traversal to pick up
     // any change hints.
     if flags.contains(Forgetful) {
         data.clear_restyle_flags_and_damage();
     }
 
-    // Optionally clear the descendants bit for the traversal type we're in.
-    if flags.for_animation_only() {
-        if flags.contains(ClearAnimationOnlyDirtyDescendants) {
-            unsafe { element.unset_animation_only_dirty_descendants(); }
-        }
-    } else {
-        // There are two cases when we want to clear the dity descendants bit here
-        // after styling this element. The first case is when we were explicitly
-        // asked to clear the bit by the caller.
-        //
-        // The second case is when this element is the root of a display:none
-        // subtree, even if the style didn't change (since, if the style did change,
+    // Optionally clear the descendants bits.
+    if data.styles.is_display_none() {
+        // When this element is the root of a display:none subtree, we want to clear
+        // the bits even if the style didn't change (since, if the style did change,
         // we'd have already cleared it above).
         //
         // This keeps the tree in a valid state without requiring the DOM to check
         // display:none on the parent when inserting new children (which can be
         // moderately expensive). Instead, DOM implementations can unconditionally
         // set the dirty descendants bit on any styled parent, and let the traversal
         // sort it out.
-        if flags.contains(ClearDirtyDescendants) ||
-           data.styles.is_display_none() {
-            unsafe { element.unset_dirty_descendants(); }
+        //
+        // Note that the NODE_DESCENDANTS_NEED_FRAMES bit should generally only be set
+        // when appending content beneath an element with a frame (i.e. not
+        // display:none), so clearing it here isn't strictly necessary, but good
+        // belt-and-suspenders.
+        unsafe { element.clear_descendants_bits(); }
+    } else if flags.for_animation_only() {
+        if flags.contains(ClearAnimationOnlyDirtyDescendants) {
+            unsafe { element.unset_animation_only_dirty_descendants(); }
         }
+    } else if flags.contains(ClearDirtyDescendants) {
+        unsafe { element.unset_dirty_descendants(); }
     }
 
     context.thread_local.end_element(element);
 }
 
 fn compute_style<E>(
     traversal_data: &PerLevelTraversalData,
     context: &mut StyleContext<E>,
@@ -788,19 +794,17 @@ where
                child,
                child_data.as_ref().map(|d| d.restyle.hint),
                propagated_hint,
                child.implemented_pseudo_element());
 
         if let Some(ref mut child_data) = child_data {
             // Propagate the parent restyle hint, that may make us restyle the whole
             // subtree.
-            if reconstructed_ancestor {
-                child_data.restyle.set_reconstructed_ancestor();
-            }
+            child_data.restyle.set_reconstructed_ancestor(reconstructed_ancestor);
 
             child_data.restyle.hint.insert(propagated_hint);
 
             // Handle element snapshots and invalidation of descendants and siblings
             // as needed.
             //
             // NB: This will be a no-op if there's no snapshot.
             child_data.invalidate_style_if_needed(child, &context.shared);
@@ -840,12 +844,11 @@ where
             if kid.get_data().is_some() {
                 unsafe { kid.clear_data() };
                 clear_descendant_data(kid);
             }
         }
     }
 
     unsafe {
-        el.unset_dirty_descendants();
-        el.unset_animation_only_dirty_descendants();
+        el.clear_descendants_bits();
     }
 }