--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -1,17 +1,17 @@
 /* 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/. */
 
 //! Per-node data used in style calculation.
 
 use arrayvec::ArrayVec;
 use context::SharedStyleContext;
-use dom::TElement;
+use dom::{TElement, TNode};
 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;
@@ -324,35 +324,51 @@ impl ElementStyles {
 /// 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);
 
 impl StoredRestyleHint {
-    /// Propagates this restyle hint to a child element.
-    pub fn propagate(&mut self, traversal_flags: &TraversalFlags) -> Self {
+    /// Computes the restyle hint to propagate to DOM children and to
+    /// traversal children.
+    pub fn propagate<E>(&mut self,
+                        element: E,
+                        traversal_flags: &TraversalFlags)
+                        -> (Self, Self)
+        where E : TElement,
+    {
         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.
         if traversal_flags.for_animation_only() {
             self.0.remove_animation_hints();
-            return Self::empty();
+            return (Self::empty(), Self::empty());
         }
 
         debug_assert!(!self.0.has_animation_hint(),
                       "There should not be any animation restyle hints \
                        during normal traversal");
 
-        // Else we should clear ourselves, and return the propagated hint.
-        let new_hint = mem::replace(&mut self.0, RestyleHint::empty())
-                       .propagate_for_non_animation_restyle();
-        StoredRestyleHint(new_hint)
+        // Else we should clear ourselves, and return the propagated hints.
+        let (new_children_hint, new_traversal_children_hint) =
+            mem::replace(&mut self.0, RestyleHint::empty())
+            .propagate_for_non_animation_restyle();
+
+        // No need to have a separate "for children" propagated hint if
+        // the list of DOM children and traversal children is the same,
+        // since the "for children" propagated hint is always a subset of
+        // the "for traversal children" hint.
+        if element.as_node().children_and_traversal_children_might_differ() {
+            (StoredRestyleHint(new_children_hint), StoredRestyleHint(new_traversal_children_hint))
+        } else {
+            (StoredRestyleHint::empty(), StoredRestyleHint(new_traversal_children_hint))
+        }
     }
 
     /// Creates an empty `StoredRestyleHint`.
     pub fn empty() -> Self {
         StoredRestyleHint(RestyleHint::empty())
     }
 
     /// Creates a restyle hint that forces the whole subtree to be restyled,
@@ -384,16 +400,22 @@ impl StoredRestyleHint {
         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()
     }
 
+    /// Whether this restyle hint represents at least as much restyle work as
+    /// the specified one.
+    pub fn contains(&self, other: &StoredRestyleHint) -> bool {
+        self.0.contains(&other.0)
+    }
+
     /// 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())

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -29,31 +29,31 @@ use gecko::selector_parser::{SelectorImp
 use gecko::snapshot_helpers;
 use gecko_bindings::bindings;
 use gecko_bindings::bindings::{Gecko_DropStyleChildrenIterator, Gecko_MaybeCreateStyleChildrenIterator};
 use gecko_bindings::bindings::{Gecko_ElementState, Gecko_GetLastChild, Gecko_GetNextStyleChild};
 use gecko_bindings::bindings::{Gecko_IsRootElement, Gecko_MatchesElement, Gecko_Namespace};
 use gecko_bindings::bindings::{Gecko_SetNodeFlags, Gecko_UnsetNodeFlags};
 use gecko_bindings::bindings::Gecko_ClassOrClassList;
 use gecko_bindings::bindings::Gecko_ElementHasAnimations;
+use gecko_bindings::bindings::Gecko_ElementHasBindingWithAnonymousContent;
 use gecko_bindings::bindings::Gecko_ElementHasCSSAnimations;
 use gecko_bindings::bindings::Gecko_ElementHasCSSTransitions;
 use gecko_bindings::bindings::Gecko_GetActiveLinkAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetAnimationRule;
 use gecko_bindings::bindings::Gecko_GetExtraContentStyleDeclarations;
 use gecko_bindings::bindings::Gecko_GetHTMLPresentationAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetSMILOverrideDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetStyleAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetStyleContext;
 use gecko_bindings::bindings::Gecko_GetUnvisitedLinkAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetVisitedLinkAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_IsSignificantChild;
 use gecko_bindings::bindings::Gecko_MatchLang;
 use gecko_bindings::bindings::Gecko_MatchStringArgPseudo;
-use gecko_bindings::bindings::Gecko_NodeHasBindingWithAnonymousContent;
 use gecko_bindings::bindings::Gecko_UnsetDirtyStyleAttr;
 use gecko_bindings::bindings::Gecko_UpdateAnimations;
 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;
@@ -268,17 +268,17 @@ impl<'ln> TNode for GeckoNode<'ln> {
         if let Some(iter) = maybe_iter.into_owned_opt() {
             LayoutIterator(GeckoChildrenIterator::GeckoIterator(iter))
         } else {
             LayoutIterator(self.dom_children())
         }
     }
 
     fn children_and_traversal_children_might_differ(&self) -> bool {
-        unsafe { Gecko_NodeHasBindingWithAnonymousContent(self.0) }
+        self.as_element().map_or(false, |e| unsafe { Gecko_ElementHasBindingWithAnonymousContent(e.0) })
     }
 
     fn opaque(&self) -> OpaqueNode {
         let ptr: usize = self.0 as *const _ as usize;
         OpaqueNode(ptr)
     }
 
     fn debug_id(self) -> usize {

--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -390,26 +390,35 @@ impl RestyleHint {
 
     /// 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.
+    /// Returns two new `RestyleHint`s appropriate for the regular DOM children
+    /// of the current element, and for the traversal children of the current
+    /// element, respectively.
     #[inline]
-    pub fn propagate_for_non_animation_restyle(&self) -> Self {
-        RestyleHint {
-            match_under_self: self.match_under_self.propagate(),
+    pub fn propagate_for_non_animation_restyle(&self) -> (Self, Self) {
+        let match_under_self = self.match_under_self.propagate();
+        let for_children = RestyleHint {
+            match_under_self: match_under_self,
+            match_later_siblings: false,
+            recascade: CascadeHint::empty(),
+            replacements: RestyleReplacements::empty(),
+        };
+        let for_traversal_children = RestyleHint {
+            match_under_self: match_under_self,
             match_later_siblings: false,
             recascade: self.recascade.propagate(),
             replacements: RestyleReplacements::empty(),
-        }
+        };
+        (for_children, for_traversal_children)
     }
 
     /// 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

--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -702,63 +702,70 @@ pub fn recalc_style_at<E, D>(traversal: 
             debug!("{:?} style is display:none - clearing data from descendants.",
                    element);
             clear_descendant_data(element, &|e| unsafe { D::clear_element_data(&e) });
         }
     }
 
     // Now that matching and cascading is done, clear the bits corresponding to
     // those operations and compute the propagated restyle hint.
-    let mut propagated_hint = match data.get_restyle_mut() {
-        None => StoredRestyleHint::empty(),
-        Some(r) => {
-            debug_assert!(context.shared.traversal_flags.for_animation_only() ||
-                          !r.hint.has_animation_hint(),
-                          "animation restyle hint should be handled during \
-                           animation-only restyles");
-            r.hint.propagate(&context.shared.traversal_flags)
-        },
-    };
+    let (propagated_hint_for_children, mut propagated_hint_for_traversal_children) =
+        match data.get_restyle_mut() {
+            None => (StoredRestyleHint::empty(), StoredRestyleHint::empty()),
+            Some(r) => {
+                debug_assert!(context.shared.traversal_flags.for_animation_only() ||
+                              !r.hint.has_animation_hint(),
+                              "animation restyle hint should be handled during \
+                               animation-only restyles");
+                r.hint.propagate(element, &context.shared.traversal_flags)
+            },
+        };
 
     // FIXME(bholley): Need to handle explicitly-inherited reset properties
     // somewhere.
-    propagated_hint.insert_cascade_hint(cascade_hint);
+    propagated_hint_for_traversal_children.insert_cascade_hint(cascade_hint);
 
-    trace!("propagated_hint={:?}, cascade_hint={:?}, \
+    trace!("propagated_hint_for_children={:?}, \
+            propagated_hint_for_traversal_children={:?}, cascade_hint={:?}, \
             is_display_none={:?}, implementing_pseudo={:?}",
-           propagated_hint, cascade_hint,
+           propagated_hint_for_children,
+           propagated_hint_for_traversal_children, cascade_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");
+    debug_assert!(propagated_hint_for_traversal_children.contains(&propagated_hint_for_children),
+                  "propagated hint for DOM children must always be a subset \
+                   of the hint for traversal children");
 
     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.
     if traversal.should_traverse_children(&mut context.thread_local,
                                           element,
                                           &data,
                                           DontLog) &&
         (has_dirty_descendants_for_this_restyle ||
-         !propagated_hint.is_empty()) {
+         !propagated_hint_for_traversal_children.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,
+                                    propagated_hint_for_children,
+                                    propagated_hint_for_traversal_children,
                                     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.
     if context.shared.traversal_flags.for_reconstruct() {
         data.clear_restyle();
@@ -850,17 +857,18 @@ fn compute_style<E, D>(_traversal: &D,
             )
         }
     }
 }
 
 fn preprocess_children<E, D>(context: &mut StyleContext<E>,
                              parent_traversal_data: &PerLevelTraversalData,
                              element: E,
-                             mut propagated_hint: StoredRestyleHint,
+                             propagated_hint_for_children: StoredRestyleHint,
+                             mut propagated_hint_for_traversal_children: 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() {
@@ -887,39 +895,73 @@ fn preprocess_children<E, D>(context: &m
                                           HintComputationContext::Child {
                                               local_context: &mut context.thread_local,
                                               dom_depth: parent_traversal_data.current_dom_depth + 1,
                                           });
 
         trace!(" > {:?} -> {:?} + {:?}, pseudo: {:?}, later_siblings: {:?}",
                child,
                child_data.get_restyle().map(|r| &r.hint),
-               propagated_hint,
+               propagated_hint_for_traversal_children,
                child.implemented_pseudo_element(),
                later_siblings);
 
         // 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_for_traversal_children.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);
+        restyle_data.hint.insert_from(&propagated_hint_for_traversal_children);
 
         if later_siblings {
-            propagated_hint.insert(RestyleHint::subtree().into());
+            propagated_hint_for_traversal_children.insert(RestyleHint::subtree().into());
         }
 
         // Store the damage already handled by ancestors.
         restyle_data.set_damage_handled(damage_handled);
     }
+
+    // Loop over all the real DOM children.
+    if !propagated_hint_for_children.is_empty() {
+        for child in element.as_node().children() {
+            let child = match child.as_element() {
+                Some(el) => el,
+                None => continue,
+            };
+
+            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;
+            }
+
+            let mut restyle_data = child_data.ensure_restyle();
+            restyle_data.hint.insert_from(&propagated_hint_for_children);
+
+            // Set dirty descendants bits from the DOM child up through its
+            // traversal ancestors until we find `element`, so that we will
+            // be sure to traverse down to it.
+            let mut current = child;
+            loop {
+                let parent = current.traversal_parent().expect("why didn't we find `element`?");
+                if parent == element {
+                    break;
+                }
+                current = parent;
+                unsafe { current.set_dirty_descendants(); }
+            }
+        }
+    }
 }
 
 /// Clear style data for all the subtree under `el`.
 pub fn clear_descendant_data<E: TElement, F: Fn(E)>(el: E, clear_data: &F) {
     for kid in el.as_node().traversal_children() {
         if let Some(kid) = kid.as_element() {
             // We maintain an invariant that, if an element has data, all its ancestors
             // have data as well. By consequence, any element without data has no