Auto merge of #14300 - bholley:restyle_driven_traversal, r=emilio

stylo: Basic infrastructure for RestyleHint-driven traversal

Gecko Bug: https://bugzilla.mozilla.org/show_bug.cgi?id=131701

(Don't review yet, will flag on the gecko bug when the time comes)

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/14300)
<!-- Reviewable:end -->

37 files changed, 1446 insertions, 888 deletions

diff --git a/components/layout/construct.rs b/components/layout/construct.rs
index 5c4f1ce7849..453c68dcae1 100644
--- a/components/layout/construct.rs
+++ b/components/layout/construct.rs
@@ -1354,8 +1354,8 @@ impl<'a, ConcreteThreadSafeLayoutNode: ThreadSafeLayoutNode>
         let mut set_has_newly_constructed_flow_flag = false;
         let result = {
             let mut style = node.style(self.style_context());
+            let damage = node.restyle_damage();
             let mut data = node.mutate_layout_data().unwrap();
-            let damage = data.base.restyle_damage;
 
             match *node.construction_result_mut(&mut *data) {
                 ConstructionResult::None => true,
diff --git a/components/layout/query.rs b/components/layout/query.rs
index 09cb53aa2e2..d34dbc59f07 100644
--- a/components/layout/query.rs
+++ b/components/layout/query.rs
@@ -29,6 +29,7 @@ use std::ops::Deref;
 use std::sync::{Arc, Mutex};
 use style::computed_values;
 use style::context::StyleContext;
+use style::dom::TElement;
 use style::logical_geometry::{WritingMode, BlockFlowDirection, InlineBaseDirection};
 use style::properties::longhands::{display, position};
 use style::properties::style_structs;
@@ -607,20 +608,6 @@ pub fn process_node_scroll_area_request< N: LayoutNode>(requested_node: N, layou
     }
 }
 
-/// Ensures that a node's data, and all its parents' is initialized. This is
-/// needed to resolve style lazily.
-fn ensure_node_data_initialized<N: LayoutNode>(node: &N) {
-    let mut cur = Some(node.clone());
-    while let Some(current) = cur {
-        if current.borrow_layout_data().is_some() {
-            break;
-        }
-
-        current.initialize_data();
-        cur = current.parent_node();
-    }
-}
-
 /// Return the resolved value of property for a given (pseudo)element.
 /// https://drafts.csswg.org/cssom/#resolved-value
 pub fn process_resolved_style_request<'a, N, C>(requested_node: N,
@@ -631,14 +618,24 @@ pub fn process_resolved_style_request<'a, N, C>(requested_node: N,
     where N: LayoutNode,
           C: StyleContext<'a>
 {
-    use style::traversal::ensure_element_styled;
-
-    // This node might have display: none, or it's style might be not up to
-    // date, so we might need to do style recalc.
-    //
-    // FIXME(emilio): Is a bit shame we have to do this instead of in style.
-    ensure_node_data_initialized(&requested_node);
-    ensure_element_styled(requested_node.as_element().unwrap(), style_context);
+    use style::traversal::{clear_descendant_data, style_element_in_display_none_subtree};
+    let element = requested_node.as_element().unwrap();
+
+    // We call process_resolved_style_request after performing a whole-document
+    // traversal, so the only reason we wouldn't have an up-to-date style here
+    // is that the requested node is in a display:none subtree. We currently
+    // maintain the invariant that elements in display:none subtrees always have
+    // no ElementData, so we need to temporarily bend those invariants here, and
+    // then throw them the style data away again before returning to preserve them.
+    // We could optimize this later to keep the style data cached somehow, but
+    // we'd need a mechanism to prevent detect when it's stale (since we don't
+    // traverse display:none subtrees during restyle).
+    let display_none_root = if element.get_data().is_none() {
+        Some(style_element_in_display_none_subtree(element, &|e| e.as_node().initialize_data(),
+                                                   style_context))
+    } else {
+        None
+    };
 
     let layout_el = requested_node.to_threadsafe().as_element().unwrap();
     let layout_el = match *pseudo {
@@ -662,6 +659,10 @@ pub fn process_resolved_style_request<'a, N, C>(requested_node: N,
 
     let style = &*layout_el.resolved_style();
 
+    // Clear any temporarily-resolved data to maintain our invariants. See the comment
+    // at the top of this function.
+    display_none_root.map(|r| clear_descendant_data(r, &|e| e.as_node().clear_data()));
+
     let positioned = match style.get_box().position {
         position::computed_value::T::relative |
         /*position::computed_value::T::sticky |*/
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs
index f0ba10d9f55..478299a62d6 100644
--- a/components/layout/traversal.rs
+++ b/components/layout/traversal.rs
@@ -112,12 +112,7 @@ impl<'lc, N> DomTraversalContext<N> for RecalcStyleAndConstructFlows<'lc>
         construct_flows_at(&self.context, self.root, node);
     }
 
-    fn should_traverse_child(parent: N::ConcreteElement, child: N) -> bool {
-        // If the parent is display:none, we don't need to do anything.
-        if parent.is_display_none() {
-            return false;
-        }
-
+    fn should_traverse_child(child: N) -> bool {
         match child.as_element() {
             // Elements should be traversed if they need styling or flow construction.
             Some(el) => el.styling_mode() != StylingMode::Stop ||
@@ -128,7 +123,7 @@ impl<'lc, N> DomTraversalContext<N> for RecalcStyleAndConstructFlows<'lc>
             // (1) They child doesn't yet have layout data (preorder traversal initializes it).
             // (2) The parent element has restyle damage (so the text flow also needs fixup).
             None => child.get_raw_data().is_none() ||
-                    parent.as_node().to_threadsafe().restyle_damage() != RestyleDamage::empty(),
+                    child.parent_node().unwrap().to_threadsafe().restyle_damage() != RestyleDamage::empty(),
         }
     }
 
@@ -156,6 +151,8 @@ pub trait PostorderNodeMutTraversal<ConcreteThreadSafeLayoutNode: ThreadSafeLayo
 #[inline]
 #[allow(unsafe_code)]
 fn construct_flows_at<'a, N: LayoutNode>(context: &'a LayoutContext<'a>, root: OpaqueNode, node: N) {
+    debug!("construct_flows_at: {:?}", node);
+
     // Construct flows for this node.
     {
         let tnode = node.to_threadsafe();
@@ -167,16 +164,18 @@ fn construct_flows_at<'a, N: LayoutNode>(context: &'a LayoutContext<'a>, root: O
             let mut flow_constructor = FlowConstructor::new(context);
             if nonincremental_layout || !flow_constructor.repair_if_possible(&tnode) {
                 flow_constructor.process(&tnode);
-                debug!("Constructed flow for {:x}: {:x}",
-                       tnode.debug_id(),
+                debug!("Constructed flow for {:?}: {:x}",
+                       tnode,
                        tnode.flow_debug_id());
             }
         }
+    }
 
-        tnode.clear_restyle_damage();
+    if let Some(el) = node.as_element() {
+        el.mutate_data().unwrap().persist();
+        unsafe { el.unset_dirty_descendants(); }
     }
 
-    unsafe { node.clear_dirty_bits(); }
     remove_from_bloom_filter(context, root, node);
 }
 
diff --git a/components/layout/wrapper.rs b/components/layout/wrapper.rs
index 9c1645c5f5e..32f24558ec0 100644
--- a/components/layout/wrapper.rs
+++ b/components/layout/wrapper.rs
@@ -37,8 +37,6 @@ use script_layout_interface::wrapper_traits::{LayoutNode, ThreadSafeLayoutElemen
 use script_layout_interface::wrapper_traits::GetLayoutData;
 use style::atomic_refcell::{AtomicRef, AtomicRefCell, AtomicRefMut};
 use style::computed_values::content::{self, ContentItem};
-use style::dom::TElement;
-use style::traversal::prepare_for_styling;
 
 pub type NonOpaqueStyleAndLayoutData = AtomicRefCell<PersistentLayoutData>;
 
@@ -97,9 +95,6 @@ impl<T: LayoutNode> LayoutNodeHelpers for T {
                 ptr: unsafe { NonZero::new(ptr as *mut AtomicRefCell<PartialPersistentLayoutData>) }
             };
             unsafe { self.init_style_and_layout_data(opaque) };
-            if let Some(el) = self.as_element() {
-                let _ = prepare_for_styling(el, el.get_data().unwrap());
-            }
         };
     }
 
diff --git a/components/layout_thread/lib.rs b/components/layout_thread/lib.rs
index b095a2069cd..3530cbb24e5 100644
--- a/components/layout_thread/lib.rs
+++ b/components/layout_thread/lib.rs
@@ -86,7 +86,7 @@ use parking_lot::RwLock;
 use profile_traits::mem::{self, Report, ReportKind, ReportsChan};
 use profile_traits::time::{self, TimerMetadata, profile};
 use profile_traits::time::{TimerMetadataFrameType, TimerMetadataReflowType};
-use script::layout_wrapper::{ServoLayoutDocument, ServoLayoutNode};
+use script::layout_wrapper::{ServoLayoutElement, ServoLayoutDocument, ServoLayoutNode};
 use script_layout_interface::message::{Msg, NewLayoutThreadInfo, Reflow, ReflowQueryType, ScriptReflow};
 use script_layout_interface::reporter::CSSErrorReporter;
 use script_layout_interface::rpc::{LayoutRPC, MarginStyleResponse, NodeOverflowResponse, OffsetParentResponse};
@@ -105,7 +105,8 @@ use std::sync::atomic::{AtomicUsize, Ordering};
 use std::sync::mpsc::{Receiver, Sender, channel};
 use style::animation::Animation;
 use style::context::{LocalStyleContextCreationInfo, ReflowGoal, SharedStyleContext};
-use style::dom::{TElement, TNode};
+use style::data::StoredRestyleHint;
+use style::dom::{StylingMode, TElement, TNode};
 use style::error_reporting::{ParseErrorReporter, StdoutErrorReporter};
 use style::logical_geometry::LogicalPoint;
 use style::media_queries::{Device, MediaType};
@@ -980,11 +981,9 @@ impl LayoutThread {
                       (data.reflow_info.goal == ReflowGoal::ForScriptQuery &&
                        data.query_type != ReflowQueryType::NoQuery));
 
-        debug!("layout: received layout request for: {}", self.url);
-
         let mut rw_data = possibly_locked_rw_data.lock();
 
-        let node: ServoLayoutNode = match document.root_node() {
+        let element: ServoLayoutElement = match document.root_node() {
             None => {
                 // Since we cannot compute anything, give spec-required placeholders.
                 debug!("layout: No root node: bailing");
@@ -1020,12 +1019,13 @@ impl LayoutThread {
                 }
                 return;
             },
-            Some(x) => x,
+            Some(x) => x.as_element().unwrap(),
         };
 
-        debug!("layout: received layout request for: {}", self.url);
+        debug!("layout: processing reflow request for: {:?} ({}) (query={:?})",
+               element, self.url, data.query_type);
         if log_enabled!(log::LogLevel::Debug) {
-            node.dump();
+            element.as_node().dump();
         }
 
         let initial_viewport = data.window_size.initial_viewport;
@@ -1061,15 +1061,15 @@ impl LayoutThread {
                        .unwrap();
             }
             if data.document_stylesheets.iter().any(|sheet| sheet.dirty_on_viewport_size_change()) {
-                let mut iter = node.traverse_preorder();
+                let mut iter = element.as_node().traverse_preorder();
 
                 let mut next = iter.next();
                 while let Some(node) = next {
                     if node.needs_dirty_on_viewport_size_changed() {
-                        // NB: The dirty bit is propagated down the tree.
-                        unsafe { node.set_dirty(); }
-
-                        if let Some(p) = node.parent_node().and_then(|n| n.as_element()) {
+                        let el = node.as_element().unwrap();
+                        el.mutate_data().map(|mut d| d.restyle()
+                                        .map(|mut r| r.hint.insert(&StoredRestyleHint::subtree())));
+                        if let Some(p) = el.parent_element() {
                             unsafe { p.note_dirty_descendant() };
                         }
 
@@ -1086,20 +1086,17 @@ impl LayoutThread {
                                                                              Some(&*UA_STYLESHEETS),
                                                                              data.stylesheets_changed);
         let needs_reflow = viewport_size_changed && !needs_dirtying;
-        unsafe {
-            if needs_dirtying {
-                // NB: The dirty flag is propagated down during the restyle
-                // process.
-                node.set_dirty();
-            }
+        if needs_dirtying {
+            element.mutate_data().map(|mut d| d.restyle().map(|mut r| r.hint.insert(&StoredRestyleHint::subtree())));
         }
         if needs_reflow {
-            if let Some(mut flow) = self.try_get_layout_root(node) {
+            if let Some(mut flow) = self.try_get_layout_root(element.as_node()) {
                 LayoutThread::reflow_all_nodes(FlowRef::deref_mut(&mut flow));
             }
         }
 
         let restyles = document.drain_pending_restyles();
+        debug!("Draining restyles: {}", restyles.len());
         if !needs_dirtying {
             for (el, restyle) in restyles {
                 // Propagate the descendant bit up the ancestors. Do this before
@@ -1109,30 +1106,23 @@ impl LayoutThread {
                     unsafe { parent.note_dirty_descendant() };
                 }
 
-                if el.get_data().is_none() {
-                    // If we haven't styled this node yet, we don't need to track
-                    // a restyle.
-                    continue;
-                }
-
-                // Start with the explicit hint, if any.
-                let mut hint = restyle.hint;
-
-                // Expand any snapshots.
-                if let Some(s) = restyle.snapshot {
-                    hint |= rw_data.stylist.compute_restyle_hint(&el, &s, el.get_state());
-                }
-
-                // Apply the cumulative hint.
-                if !hint.is_empty() {
-                    el.note_restyle_hint::<RecalcStyleAndConstructFlows>(hint);
-                }
-
-                // Apply explicit damage, if any.
-                if !restyle.damage.is_empty() {
-                    let mut d = el.mutate_layout_data().unwrap();
-                    d.base.restyle_damage |= restyle.damage;
-                }
+                // If we haven't styled this node yet, we don't need to track a restyle.
+                let mut data = match el.mutate_layout_data() {
+                    Some(d) => d,
+                    None => continue,
+                };
+                let mut style_data = &mut data.base.style_data;
+                debug_assert!(!style_data.is_restyle());
+                let mut restyle_data = match style_data.restyle() {
+                    Some(d) => d,
+                    None => continue,
+                };
+
+                // Stash the data on the element for processing by the style system.
+                restyle_data.hint = restyle.hint.into();
+                restyle_data.damage = restyle.damage;
+                restyle_data.snapshot = restyle.snapshot;
+                debug!("Noting restyle for {:?}: {:?}", el, restyle_data);
             }
         }
 
@@ -1141,8 +1131,7 @@ impl LayoutThread {
                                                                          viewport_size_changed,
                                                                          data.reflow_info.goal);
 
-        let el = node.as_element();
-        if el.is_some() && (el.unwrap().deprecated_dirty_bit_is_set() || el.unwrap().has_dirty_descendants()) {
+        if element.styling_mode() != StylingMode::Stop {
             // Recalculate CSS styles and rebuild flows and fragments.
             profile(time::ProfilerCategory::LayoutStyleRecalc,
                     self.profiler_metadata(),
@@ -1152,11 +1141,11 @@ impl LayoutThread {
                 match self.parallel_traversal {
                     None => {
                         sequential::traverse_dom::<ServoLayoutNode, RecalcStyleAndConstructFlows>(
-                            node, &shared_layout_context);
+                            element.as_node(), &shared_layout_context);
                     }
                     Some(ref mut traversal) => {
                         parallel::traverse_dom::<ServoLayoutNode, RecalcStyleAndConstructFlows>(
-                            node, &shared_layout_context, traversal);
+                            element.as_node(), &shared_layout_context, traversal);
                     }
                 }
             });
@@ -1174,11 +1163,11 @@ impl LayoutThread {
                                     0);
 
             // Retrieve the (possibly rebuilt) root flow.
-            self.root_flow = self.try_get_layout_root(node);
+            self.root_flow = self.try_get_layout_root(element.as_node());
         }
 
         if opts::get().dump_style_tree {
-            node.dump_style();
+            element.as_node().dump_style();
         }
 
         if opts::get().dump_rule_tree {
diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index b4273233c37..5870e4c1320 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -434,7 +434,6 @@ impl Document {
         // that workable.
         match self.GetDocumentElement() {
             Some(root) => {
-                root.upcast::<Node>().is_dirty() ||
                 root.upcast::<Node>().has_dirty_descendants() ||
                 !self.pending_restyles.borrow().is_empty() ||
                 self.needs_paint()
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index 8e8bf6edc9e..983e2e8d403 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -149,9 +149,6 @@ bitflags! {
         #[doc = "Specifies whether this node is in a document."]
         const IS_IN_DOC = 0x01,
         #[doc = "Specifies whether this node needs style recalc on next reflow."]
-        const IS_DIRTY = 0x04,
-        #[doc = "Specifies whether this node has descendants (inclusive of itself) which \
-                 have changed since the last reflow."]
         const HAS_DIRTY_DESCENDANTS = 0x08,
         // TODO: find a better place to keep this (#4105)
         // https://critic.hoppipolla.co.uk/showcomment?chain=8873
@@ -172,7 +169,7 @@ bitflags! {
 
 impl NodeFlags {
     pub fn new() -> NodeFlags {
-        IS_DIRTY
+        NodeFlags::empty()
     }
 }
 
@@ -428,14 +425,6 @@ impl Node {
         self.flags.set(flags);
     }
 
-    pub fn is_dirty(&self) -> bool {
-        self.get_flag(IS_DIRTY)
-    }
-
-    pub fn set_is_dirty(&self, state: bool) {
-        self.set_flag(IS_DIRTY, state)
-    }
-
     pub fn has_dirty_descendants(&self) -> bool {
         self.get_flag(HAS_DIRTY_DESCENDANTS)
     }
diff --git a/components/script/layout_wrapper.rs b/components/script/layout_wrapper.rs
index 18d2bd092c0..a386d5c8563 100644
--- a/components/script/layout_wrapper.rs
+++ b/components/script/layout_wrapper.rs
@@ -36,7 +36,7 @@ use dom::bindings::js::LayoutJS;
 use dom::characterdata::LayoutCharacterDataHelpers;
 use dom::document::{Document, LayoutDocumentHelpers, PendingRestyle};
 use dom::element::{Element, LayoutElementHelpers, RawLayoutElementHelpers};
-use dom::node::{CAN_BE_FRAGMENTED, DIRTY_ON_VIEWPORT_SIZE_CHANGE, HAS_DIRTY_DESCENDANTS, IS_DIRTY};
+use dom::node::{CAN_BE_FRAGMENTED, DIRTY_ON_VIEWPORT_SIZE_CHANGE, HAS_DIRTY_DESCENDANTS};
 use dom::node::{LayoutNodeHelpers, Node};
 use dom::text::Text;
 use gfx_traits::ByteIndex;
@@ -53,11 +53,12 @@ use selectors::parser::{AttrSelector, NamespaceConstraint};
 use servo_atoms::Atom;
 use servo_url::ServoUrl;
 use std::fmt;
+use std::fmt::Debug;
 use std::marker::PhantomData;
 use std::mem::transmute;
 use std::sync::Arc;
 use std::sync::atomic::Ordering;
-use style::atomic_refcell::{AtomicRef, AtomicRefCell};
+use style::atomic_refcell::AtomicRefCell;
 use style::attr::AttrValue;
 use style::computed_values::display;
 use style::context::SharedStyleContext;
@@ -80,6 +81,16 @@ pub struct ServoLayoutNode<'a> {
     chain: PhantomData<&'a ()>,
 }
 
+impl<'ln> Debug for ServoLayoutNode<'ln> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        if let Some(el) = self.as_element() {
+            el.fmt(f)
+        } else {
+            write!(f, "{:?} ({:#x})", self.type_id(), self.opaque().0)
+        }
+    }
+}
+
 impl<'a> PartialEq for ServoLayoutNode<'a> {
     #[inline]
     fn eq(&self, other: &ServoLayoutNode) -> bool {
@@ -201,30 +212,6 @@ impl<'ln> TNode for ServoLayoutNode<'ln> {
             self.node.parent_node_ref().map(|node| self.new_with_this_lifetime(&node))
         }
     }
-
-    fn first_child(&self) -> Option<ServoLayoutNode<'ln>> {
-        unsafe {
-            self.node.first_child_ref().map(|node| self.new_with_this_lifetime(&node))
-        }
-    }
-
-    fn last_child(&self) -> Option<ServoLayoutNode<'ln>> {
-        unsafe {
-            self.node.last_child_ref().map(|node| self.new_with_this_lifetime(&node))
-        }
-    }
-
-    fn prev_sibling(&self) -> Option<ServoLayoutNode<'ln>> {
-        unsafe {
-            self.node.prev_sibling_ref().map(|node| self.new_with_this_lifetime(&node))
-        }
-    }
-
-    fn next_sibling(&self) -> Option<ServoLayoutNode<'ln>> {
-        unsafe {
-            self.node.next_sibling_ref().map(|node| self.new_with_this_lifetime(&node))
-        }
-    }
 }
 
 pub struct ServoChildrenIterator<'a> {
@@ -259,9 +246,28 @@ impl<'ln> LayoutNode for ServoLayoutNode<'ln> {
         self.get_jsmanaged().take_style_and_layout_data()
     }
 
-    unsafe fn clear_dirty_bits(&self) {
-        self.node.set_flag(IS_DIRTY, false);
-        self.node.set_flag(HAS_DIRTY_DESCENDANTS, false);
+    fn first_child(&self) -> Option<ServoLayoutNode<'ln>> {
+        unsafe {
+            self.node.first_child_ref().map(|node| self.new_with_this_lifetime(&node))
+        }
+    }
+
+    fn last_child(&self) -> Option<ServoLayoutNode<'ln>> {
+        unsafe {
+            self.node.last_child_ref().map(|node| self.new_with_this_lifetime(&node))
+        }
+    }
+
+    fn prev_sibling(&self) -> Option<ServoLayoutNode<'ln>> {
+        unsafe {
+            self.node.prev_sibling_ref().map(|node| self.new_with_this_lifetime(&node))
+        }
+    }
+
+    fn next_sibling(&self) -> Option<ServoLayoutNode<'ln>> {
+        unsafe {
+            self.node.next_sibling_ref().map(|node| self.new_with_this_lifetime(&node))
+        }
     }
 }
 
@@ -292,14 +298,6 @@ impl<'le> GetLayoutData for ServoThreadSafeLayoutElement<'le> {
 }
 
 impl<'ln> ServoLayoutNode<'ln> {
-    pub fn is_dirty(&self) -> bool {
-        unsafe { self.node.get_flag(IS_DIRTY) }
-    }
-
-    pub unsafe fn set_dirty(&self) {
-        self.node.set_flag(IS_DIRTY, true)
-    }
-
     fn dump_indent(self, indent: u32) {
         let mut s = String::new();
         for _ in 0..indent {
@@ -330,9 +328,8 @@ impl<'ln> ServoLayoutNode<'ln> {
     }
 
     fn debug_str(self) -> String {
-        format!("{:?}: dirty={} dirty_descendants={}",
+        format!("{:?}: dirty_descendants={}",
                 self.script_type_id(),
-                self.as_element().map_or(false, |el| el.deprecated_dirty_bit_is_set()),
                 self.as_element().map_or(false, |el| el.has_dirty_descendants()))
     }
 
@@ -406,7 +403,7 @@ impl<'le> fmt::Debug for ServoLayoutElement<'le> {
         if let &Some(ref id) = unsafe { &*self.element.id_attribute() } {
             try!(write!(f, " id={}", id));
         }
-        write!(f, ">")
+        write!(f, "> ({:#x})", self.as_node().opaque().0)
     }
 }
 
@@ -447,10 +444,6 @@ impl<'le> TElement for ServoLayoutElement<'le> {
         self.get_attr(namespace, attr).map_or(false, |x| x == val)
     }
 
-    fn set_restyle_damage(self, damage: RestyleDamage) {
-        self.get_partial_layout_data().unwrap().borrow_mut().restyle_damage |= damage;
-    }
-
     #[inline]
     fn existing_style_for_restyle_damage<'a>(&'a self,
                                              current_cv: Option<&'a Arc<ComputedValues>>,
@@ -459,10 +452,6 @@ impl<'le> TElement for ServoLayoutElement<'le> {
         current_cv
     }
 
-    fn deprecated_dirty_bit_is_set(&self) -> bool {
-        unsafe { self.as_node().node.get_flag(IS_DIRTY) }
-    }
-
     fn has_dirty_descendants(&self) -> bool {
         unsafe { self.as_node().node.get_flag(HAS_DIRTY_DESCENDANTS) }
     }
@@ -471,6 +460,10 @@ impl<'le> TElement for ServoLayoutElement<'le> {
         self.as_node().node.set_flag(HAS_DIRTY_DESCENDANTS, true)
     }
 
+    unsafe fn unset_dirty_descendants(&self) {
+        self.as_node().node.set_flag(HAS_DIRTY_DESCENDANTS, false)
+    }
+
     fn store_children_to_process(&self, n: isize) {
         let data = self.get_partial_layout_data().unwrap().borrow();
         data.parallel.children_to_process.store(n, Ordering::Relaxed);
@@ -483,10 +476,6 @@ impl<'le> TElement for ServoLayoutElement<'le> {
         old_value - 1
     }
 
-    fn borrow_data(&self) -> Option<AtomicRef<ElementData>> {
-        self.get_data().map(|d| d.borrow())
-    }
-
     fn get_data(&self) -> Option<&AtomicRefCell<ElementData>> {
         unsafe {
             self.get_style_and_layout_data().map(|d| {
@@ -729,7 +718,7 @@ impl<'le> ::selectors::Element for ServoLayoutElement<'le> {
     }
 }
 
-#[derive(Copy, Clone)]
+#[derive(Copy, Clone, Debug)]
 pub struct ServoThreadSafeLayoutNode<'ln> {
     /// The wrapped node.
     node: ServoLayoutNode<'ln>,
@@ -830,7 +819,7 @@ impl<'ln> ThreadSafeLayoutNode for ServoThreadSafeLayoutNode<'ln> {
         debug_assert!(self.is_text_node());
         let parent = self.node.parent_node().unwrap().as_element().unwrap();
         let parent_data = parent.get_data().unwrap().borrow();
-        parent_data.current_styles().primary.clone()
+        parent_data.current_styles().primary.values.clone()
     }
 
     fn debug_id(self) -> usize {
@@ -874,22 +863,14 @@ impl<'ln> ThreadSafeLayoutNode for ServoThreadSafeLayoutNode<'ln> {
     }
 
     fn restyle_damage(self) -> RestyleDamage {
-        if self.is_text_node() {
-            let parent = self.node.parent_node().unwrap().as_element().unwrap();
-            let parent_data = parent.get_partial_layout_data().unwrap().borrow();
-            parent_data.restyle_damage
+        let element = if self.is_text_node() {
+            self.node.parent_node().unwrap().as_element().unwrap()
         } else {
-            let el = self.as_element().unwrap().element;
-            let damage = el.get_partial_layout_data().unwrap().borrow().restyle_damage.clone();
-            damage
-        }
-    }
+            self.node.as_element().unwrap()
+        };
 
-    fn clear_restyle_damage(self) {
-        if let Some(el) = self.as_element() {
-            let mut data = el.element.get_partial_layout_data().unwrap().borrow_mut();
-            data.restyle_damage = RestyleDamage::empty();
-        }
+        let damage = element.borrow_data().unwrap().damage();
+        damage
     }
 
     fn can_be_fragmented(&self) -> bool {
diff --git a/components/script_layout_interface/lib.rs b/components/script_layout_interface/lib.rs
index 5894e96049a..d52990fa8f4 100644
--- a/components/script_layout_interface/lib.rs
+++ b/components/script_layout_interface/lib.rs
@@ -51,8 +51,6 @@ use libc::c_void;
 use std::sync::atomic::AtomicIsize;
 use style::atomic_refcell::AtomicRefCell;
 use style::data::ElementData;
-use style::dom::TRestyleDamage;
-use style::selector_parser::RestyleDamage;
 
 pub struct PartialPersistentLayoutData {
     /// Data that the style system associates with a node. When the
@@ -61,9 +59,6 @@ pub struct PartialPersistentLayoutData {
     /// transmutations between ElementData and PersistentLayoutData.
     pub style_data: ElementData,
 
-    /// Description of how to account for recent style changes.
-    pub restyle_damage: RestyleDamage,
-
     /// Information needed during parallel traversals.
     pub parallel: DomParallelInfo,
 }
@@ -71,11 +66,7 @@ pub struct PartialPersistentLayoutData {
 impl PartialPersistentLayoutData {
     pub fn new() -> Self {
         PartialPersistentLayoutData {
-            style_data: ElementData::new(),
-            // FIXME(bholley): This is needed for now to make sure we do frame
-            // construction after initial styling. This will go away shortly when
-            // we move restyle damage into the style system.
-            restyle_damage: RestyleDamage::rebuild_and_reflow(),
+            style_data: ElementData::new(None),
             parallel: DomParallelInfo::new(),
         }
     }
@@ -142,7 +133,7 @@ pub struct SVGSVGData {
 }
 
 /// The address of a node known to be valid. These are sent from script to layout.
-#[derive(Clone, PartialEq, Eq, Copy)]
+#[derive(Clone, Debug, PartialEq, Eq, Copy)]
 pub struct TrustedNodeAddress(pub *const c_void);
 
 #[allow(unsafe_code)]
diff --git a/components/script_layout_interface/message.rs b/components/script_layout_interface/message.rs
index 06b661059b6..3af9af32c79 100644
--- a/components/script_layout_interface/message.rs
+++ b/components/script_layout_interface/message.rs
@@ -87,7 +87,7 @@ pub enum Msg {
 
 
 /// Any query to perform with this reflow.
-#[derive(PartialEq)]
+#[derive(Debug, PartialEq)]
 pub enum ReflowQueryType {
     NoQuery,
     ContentBoxQuery(TrustedNodeAddress),
diff --git a/components/script_layout_interface/wrapper_traits.rs b/components/script_layout_interface/wrapper_traits.rs
index e0a39ea9629..428642ce93b 100644
--- a/components/script_layout_interface/wrapper_traits.rs
+++ b/components/script_layout_interface/wrapper_traits.rs
@@ -76,7 +76,7 @@ pub trait GetLayoutData {
 
 /// A wrapper so that layout can access only the methods that it should have access to. Layout must
 /// only ever see these and must never see instances of `LayoutJS`.
-pub trait LayoutNode: GetLayoutData + TNode {
+pub trait LayoutNode: Debug + GetLayoutData + TNode {
     type ConcreteThreadSafeLayoutNode: ThreadSafeLayoutNode;
     fn to_threadsafe(&self) -> Self::ConcreteThreadSafeLayoutNode;
 
@@ -86,8 +86,6 @@ pub trait LayoutNode: GetLayoutData + TNode {
     unsafe fn init_style_and_layout_data(&self, data: OpaqueStyleAndLayoutData);
     unsafe fn take_style_and_layout_data(&self) -> OpaqueStyleAndLayoutData;
 
-    unsafe fn clear_dirty_bits(&self);
-
     fn rev_children(self) -> LayoutIterator<ReverseChildrenIterator<Self>> {
         LayoutIterator(ReverseChildrenIterator {
             current: self.last_child(),
@@ -97,14 +95,22 @@ pub trait LayoutNode: GetLayoutData + TNode {
     fn traverse_preorder(self) -> TreeIterator<Self> {
         TreeIterator::new(self)
     }
+
+    fn first_child(&self) -> Option<Self>;
+
+    fn last_child(&self) -> Option<Self>;
+
+    fn prev_sibling(&self) -> Option<Self>;
+
+    fn next_sibling(&self) -> Option<Self>;
 }
 
-pub struct ReverseChildrenIterator<ConcreteNode> where ConcreteNode: TNode {
+pub struct ReverseChildrenIterator<ConcreteNode> where ConcreteNode: LayoutNode {
     current: Option<ConcreteNode>,
 }
 
 impl<ConcreteNode> Iterator for ReverseChildrenIterator<ConcreteNode>
-                            where ConcreteNode: TNode {
+                            where ConcreteNode: LayoutNode {
     type Item = ConcreteNode;
     fn next(&mut self) -> Option<ConcreteNode> {
         let node = self.current;
@@ -113,7 +119,7 @@ impl<ConcreteNode> Iterator for ReverseChildrenIterator<ConcreteNode>
     }
 }
 
-pub struct TreeIterator<ConcreteNode> where ConcreteNode: TNode {
+pub struct TreeIterator<ConcreteNode> where ConcreteNode: LayoutNode {
     stack: Vec<ConcreteNode>,
 }
 
@@ -144,7 +150,7 @@ impl<ConcreteNode> Iterator for TreeIterator<ConcreteNode>
 
 /// A thread-safe version of `LayoutNode`, used during flow construction. This type of layout
 /// node does not allow any parents or siblings of nodes to be accessed, to avoid races.
-pub trait ThreadSafeLayoutNode: Clone + Copy + GetLayoutData + NodeInfo + PartialEq + Sized {
+pub trait ThreadSafeLayoutNode: Clone + Copy + Debug + GetLayoutData + NodeInfo + PartialEq + Sized {
     type ConcreteThreadSafeLayoutElement:
         ThreadSafeLayoutElement<ConcreteThreadSafeLayoutNode = Self>
         + ::selectors::Element<Impl=SelectorImpl>;
@@ -233,8 +239,6 @@ pub trait ThreadSafeLayoutNode: Clone + Copy + GetLayoutData + NodeInfo + Partia
 
     fn restyle_damage(self) -> RestyleDamage;
 
-    fn clear_restyle_damage(self);
-
     /// Returns true if this node contributes content. This is used in the implementation of
     /// `empty_cells` per CSS 2.1 § 17.6.1.1.
     fn is_content(&self) -> bool {
@@ -353,7 +357,7 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
     fn style(&self, context: &SharedStyleContext) -> Arc<ServoComputedValues> {
         match self.get_pseudo_element_type() {
             PseudoElementType::Normal => self.get_style_data().unwrap().borrow()
-                                             .current_styles().primary.clone(),
+                                             .current_styles().primary.values.clone(),
             other => {
                 // Precompute non-eagerly-cascaded pseudo-element styles if not
                 // cached before.
@@ -367,13 +371,13 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
                                 .borrow()
                                 .current_styles().pseudos.contains_key(&style_pseudo) {
                             let mut data = self.get_style_data().unwrap().borrow_mut();
-                            let new_style_and_rule_node =
+                            let new_style =
                                 context.stylist.precomputed_values_for_pseudo(
                                     &style_pseudo,
-                                    Some(&data.current_styles().primary),
+                                    Some(&data.current_styles().primary.values),
                                     false);
-                            data.current_pseudos_mut()
-                                .insert(style_pseudo.clone(), new_style_and_rule_node.unwrap());
+                            data.current_styles_mut().pseudos
+                                .insert(style_pseudo.clone(), new_style.unwrap());
                         }
                     }
                     PseudoElementCascadeType::Lazy => {
@@ -387,8 +391,8 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
                                        .lazily_compute_pseudo_element_style(
                                            self,
                                            &style_pseudo,
-                                           &data.current_styles().primary);
-                            data.current_pseudos_mut()
+                                           &data.current_styles().primary.values);
+                            data.current_styles_mut().pseudos
                                 .insert(style_pseudo.clone(), new_style.unwrap());
                         }
                     }
@@ -396,7 +400,7 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
 
                 self.get_style_data().unwrap().borrow()
                     .current_styles().pseudos.get(&style_pseudo)
-                    .unwrap().0.clone()
+                    .unwrap().values.clone()
             }
         }
     }
@@ -405,9 +409,9 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
     fn selected_style(&self) -> Arc<ServoComputedValues> {
         let data = self.get_style_data().unwrap().borrow();
         data.current_styles().pseudos
-            .get(&PseudoElement::Selection).map(|s| &s.0)
+            .get(&PseudoElement::Selection).map(|s| s)
             .unwrap_or(&data.current_styles().primary)
-            .clone()
+            .values.clone()
     }
 
     /// Returns the already resolved style of the node.
@@ -422,10 +426,10 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
         let data = self.get_style_data().unwrap().borrow();
         match self.get_pseudo_element_type() {
             PseudoElementType::Normal
-                => data.current_styles().primary.clone(),
+                => data.current_styles().primary.values.clone(),
             other
                 => data.current_styles().pseudos
-                       .get(&other.style_pseudo_element()).unwrap().0.clone(),
+                       .get(&other.style_pseudo_element()).unwrap().values.clone(),
         }
     }
 }
diff --git a/components/style/atomic_refcell.rs b/components/style/atomic_refcell.rs
index 9fb8c99a375..ee6771bc527 100644
--- a/components/style/atomic_refcell.rs
+++ b/components/style/atomic_refcell.rs
@@ -6,6 +6,8 @@
 
 use owning_ref::{OwningRef, StableAddress};
 use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};
+use std::fmt;
+use std::fmt::Debug;
 use std::ops::{Deref, DerefMut};
 
 /// Container type providing RefCell-like semantics for objects shared across
@@ -50,6 +52,18 @@ impl<'a, T> DerefMut for AtomicRefMut<'a, T> {
     }
 }
 
+impl<'a, T: 'a + Debug> Debug for AtomicRef<'a, T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{:?}", self.0.deref())
+    }
+}
+
+impl<'a, T: 'a + Debug> Debug for AtomicRefMut<'a, T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{:?}", self.0.deref())
+    }
+}
+
 impl<T> AtomicRefCell<T> {
     pub fn new(value: T) -> Self {
         AtomicRefCell(RwLock::new(value))
diff --git a/components/style/binding_tools/regen.py b/components/style/binding_tools/regen.py
index b348cc0615b..1c7e193fa13 100755
--- a/components/style/binding_tools/regen.py
+++ b/components/style/binding_tools/regen.py
@@ -251,6 +251,7 @@ COMPILATION_TARGETS = {
         "match_headers": [
             "ServoBindingList.h",
             "ServoBindings.h",
+            "ServoTypes.h",
             "nsStyleStructList.h",
         ],
         "files": [
@@ -261,6 +262,9 @@ COMPILATION_TARGETS = {
             "RawGeckoElement",
             "RawGeckoNode",
             "ThreadSafe.*Holder",
+            "ConsumeStyleBehavior",
+            "LazyComputeBehavior",
+            "SkipRootBehavior",
         ],
 
         # Types to just use from the `structs` target.
@@ -339,8 +343,16 @@ COMPILATION_TARGETS = {
             "RawServoStyleRule",
         ],
         "servo_owned_types": [
-            "RawServoStyleSet",
-            "StyleChildrenIterator",
+            {
+                "name": "RawServoStyleSet",
+                "opaque": True,
+            }, {
+                "name": "StyleChildrenIterator",
+                "opaque": True,
+            }, {
+                "name": "ServoElementSnapshot",
+                "opaque": False,
+            },
         ],
         "servo_immutable_borrow_types": [
             "RawGeckoNode",
@@ -446,7 +458,7 @@ def build(objdir, target_name, debug, debugger, kind_name=None,
 
     if os.path.isdir(bindgen):
         bindgen = ["cargo", "run", "--manifest-path",
-                   os.path.join(bindgen, "Cargo.toml"), "--features", "llvm_stable", "--"]
+                   os.path.join(bindgen, "Cargo.toml"), "--features", "llvm_stable", "--release", "--"]
     else:
         bindgen = [bindgen]
 
@@ -606,7 +618,8 @@ Option<&'a mut {0}>;".format(ty))
             flags.append("pub type {0}{2} = {1}{2};".format(ty["gecko"], ty["servo"], "<T>" if ty["generic"] else ""))
 
     if "servo_owned_types" in current_target:
-        for ty in current_target["servo_owned_types"]:
+        for entry in current_target["servo_owned_types"]:
+            ty = entry["name"]
             flags.append("--blacklist-type")
             flags.append("{}Borrowed".format(ty))
             flags.append("--raw-line")
@@ -633,7 +646,8 @@ Option<&'a mut {0}>;".format(ty))
             flags.append("{}OwnedOrNull".format(ty))
             flags.append("--raw-line")
             flags.append("pub type {0}OwnedOrNull = ::gecko_bindings::sugar::ownership::OwnedOrNull<{0}>;".format(ty))
-            zero_size_type(ty, flags)
+            if entry["opaque"]:
+                zero_size_type(ty, flags)
 
     if "structs_types" in current_target:
         for ty in current_target["structs_types"]:
diff --git a/components/style/binding_tools/setup_bindgen.sh b/components/style/binding_tools/setup_bindgen.sh
index cb0c5f175db..feb788d4bab 100755
--- a/components/style/binding_tools/setup_bindgen.sh
+++ b/components/style/binding_tools/setup_bindgen.sh
@@ -35,4 +35,4 @@ if [[ ! -d rust-bindgen ]]; then
 fi
 
 cd rust-bindgen
-cargo build --features llvm_stable
+cargo build --features llvm_stable --release
diff --git a/components/style/context.rs b/components/style/context.rs
index d5819555cf6..6785d752478 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -38,6 +38,14 @@ pub struct SharedStyleContext {
     /// Screen sized changed?
     pub screen_size_changed: bool,
 
+    /// Skip the root during traversal?
+    ///
+    /// This is used in Gecko to style newly-appended children without restyling
+    /// the parent. It would be cleaner to add an API to allow us to enqueue the
+    /// children directly from glue.rs.
+    #[cfg(feature = "gecko")]
+    pub skip_root: bool,
+
     /// The CSS selector stylist.
     pub stylist: Arc<Stylist>,
 
diff --git a/components/style/data.rs b/components/style/data.rs
index 9fc871c3bcf..b3049bba144 100644
--- a/components/style/data.rs
+++ b/components/style/data.rs
@@ -4,16 +4,48 @@
 
 //! Per-node data used in style calculation.
 
+use dom::TRestyleDamage;
 use properties::ComputedValues;
+use properties::longhands::display::computed_value as display;
+use restyle_hints::RestyleHint;
 use rule_tree::StrongRuleNode;
-use selector_parser::PseudoElement;
+use selector_parser::{PseudoElement, RestyleDamage, Snapshot};
 use std::collections::HashMap;
+use std::fmt;
 use std::hash::BuildHasherDefault;
 use std::mem;
 use std::ops::{Deref, DerefMut};
 use std::sync::Arc;
 
-type PseudoStylesInner = HashMap<PseudoElement, (Arc<ComputedValues>, StrongRuleNode),
+#[derive(Clone)]
+pub struct ComputedStyle {
+    /// The rule node representing the ordered list of rules matched for this
+    /// node.
+    pub rules: StrongRuleNode,
+
+    /// The computed values for each property obtained by cascading the
+    /// matched rules.
+    pub values: Arc<ComputedValues>,
+}
+
+impl ComputedStyle {
+    pub fn new(rules: StrongRuleNode, values: Arc<ComputedValues>) -> Self {
+        ComputedStyle {
+            rules: rules,
+            values: values,
+        }
+    }
+}
+
+// We manually implement Debug for ComputedStyle so tht we can avoid the verbose
+// stringification of ComputedValues for normal logging.
+impl fmt::Debug for ComputedStyle {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "ComputedStyle {{ rules: {:?}, values: {{..}} }}", self.rules)
+    }
+}
+
+type PseudoStylesInner = HashMap<PseudoElement, ComputedStyle,
                                  BuildHasherDefault<::fnv::FnvHasher>>;
 #[derive(Clone, Debug)]
 pub struct PseudoStyles(PseudoStylesInner);
@@ -37,73 +69,180 @@ impl DerefMut for PseudoStyles {
 /// pseudo-elements.
 #[derive(Clone, Debug)]
 pub struct ElementStyles {
-    /// The results of CSS styling for this node.
-    pub primary: Arc<ComputedValues>,
-
-    /// The rule node representing the last rule matched for this node.
-    pub rule_node: StrongRuleNode,
-
-    /// The results of CSS styling for each pseudo-element (if any).
+    pub primary: ComputedStyle,
     pub pseudos: PseudoStyles,
 }
 
 impl ElementStyles {
-    pub fn new(primary: Arc<ComputedValues>, rule_node: StrongRuleNode) -> Self {
+    pub fn new(primary: ComputedStyle) -> Self {
         ElementStyles {
             primary: primary,
-            rule_node: rule_node,
             pseudos: PseudoStyles::empty(),
         }
     }
+
+    pub fn is_display_none(&self) -> bool {
+        self.primary.values.get_box().clone_display() == display::T::none
+    }
 }
 
-#[derive(Debug)]
-enum ElementDataStyles {
-    /// The field has not been initialized.
-    Uninitialized,
-
-    /// The field holds the previous style of the node. If this is None, the
-    /// node has not been previously styled.
-    ///
-    /// This is the input to the styling algorithm. It would ideally be
-    /// immutable, but for now we need to mutate it a bit before styling to
-    /// handle animations.
-    ///
-    /// Note that since ElementStyles contains an Arc, the null pointer
-    /// optimization prevents the Option<> here from consuming an extra word.
-    Previous(Option<ElementStyles>),
-
-    /// The field holds the current, up-to-date style.
-    ///
-    /// This is the output of the styling algorithm.
-    Current(ElementStyles),
-}
-
-impl ElementDataStyles {
-    fn is_previous(&self) -> bool {
-        use self::ElementDataStyles::*;
-        match *self {
-            Previous(_) => true,
-            _ => false,
+/// Enum to describe the different requirements that a restyle hint may impose
+/// on its descendants.
+#[derive(Clone, Copy, Debug, PartialEq)]
+pub enum DescendantRestyleHint {
+    /// This hint does not require any descendants to be restyled.
+    Empty,
+    /// This hint requires direct children to be restyled.
+    Children,
+    /// This hint requires all descendants to be restyled.
+    Descendants,
+}
+
+impl DescendantRestyleHint {
+    /// Propagates this descendant behavior to a child element.
+    fn propagate(self) -> Self {
+        use self::DescendantRestyleHint::*;
+        if self == Descendants {
+            Descendants
+        } else {
+            Empty
+        }
+    }
+
+    fn union(self, other: Self) -> Self {
+        use self::DescendantRestyleHint::*;
+        if self == Descendants || other == Descendants {
+            Descendants
+        } else if self == Children || other == Children {
+            Children
+        } else {
+            Empty
         }
     }
 }
 
+/// Restyle hint for storing on ElementData. We use a separate representation
+/// to provide more type safety while propagating restyle hints down the tree.
+#[derive(Clone, Debug)]
+pub struct StoredRestyleHint {
+    pub restyle_self: bool,
+    pub descendants: DescendantRestyleHint,
+}
+
+impl StoredRestyleHint {
+    /// Propagates this restyle hint to a child element.
+    pub fn propagate(&self) -> Self {
+        StoredRestyleHint {
+            restyle_self: self.descendants == DescendantRestyleHint::Empty,
+            descendants: self.descendants.propagate(),
+        }
+    }
+
+    pub fn empty() -> Self {
+        StoredRestyleHint {
+            restyle_self: false,
+            descendants: DescendantRestyleHint::Empty,
+        }
+    }
+
+    pub fn subtree() -> Self {
+        StoredRestyleHint {
+            restyle_self: true,
+            descendants: DescendantRestyleHint::Descendants,
+        }
+    }
+
+    pub fn is_empty(&self) -> bool {
+        !self.restyle_self && self.descendants == DescendantRestyleHint::Empty
+    }
+
+    pub fn insert(&mut self, other: &Self) {
+        self.restyle_self = self.restyle_self || other.restyle_self;
+        self.descendants = self.descendants.union(other.descendants);
+    }
+}
+
+impl Default for StoredRestyleHint {
+    fn default() -> Self {
+        StoredRestyleHint {
+            restyle_self: false,
+            descendants: DescendantRestyleHint::Empty,
+        }
+    }
+}
+
+impl From<RestyleHint> for StoredRestyleHint {
+    fn from(hint: RestyleHint) -> Self {
+        use restyle_hints::*;
+        use self::DescendantRestyleHint::*;
+        debug_assert!(!hint.contains(RESTYLE_LATER_SIBLINGS), "Caller should apply sibling hints");
+        StoredRestyleHint {
+            restyle_self: hint.contains(RESTYLE_SELF),
+            descendants: if hint.contains(RESTYLE_DESCENDANTS) { Descendants } else { Empty },
+        }
+    }
+}
+
+#[derive(Debug)]
+pub enum RestyleDataStyles {
+    Previous(ElementStyles),
+    New(ElementStyles),
+}
+
 /// Transient data used by the restyle algorithm. This structure is instantiated
 /// either before or during restyle traversal, and is cleared at the end of node
 /// processing.
 #[derive(Debug)]
 pub struct RestyleData {
-    // FIXME(bholley): Start adding the fields from the algorithm doc.
-    pub _dummy: u64,
+    pub styles: RestyleDataStyles,
+    pub hint: StoredRestyleHint,
+    pub damage: RestyleDamage,
+    pub snapshot: Option<Snapshot>,
 }
 
 impl RestyleData {
-    fn new() -> Self {
+    fn new(previous: ElementStyles) -> Self {
         RestyleData {
-            _dummy: 42,
+            styles: RestyleDataStyles::Previous(previous),
+            hint: StoredRestyleHint::default(),
+            damage: RestyleDamage::empty(),
+            snapshot: None,
+        }
+    }
+
+    pub fn get_current_styles(&self) -> Option<&ElementStyles> {
+        use self::RestyleDataStyles::*;
+        match self.styles {
+            Previous(_) => None,
+            New(ref x) => Some(x),
         }
     }
+
+    pub fn current_styles(&self) -> &ElementStyles {
+        self.get_current_styles().unwrap()
+    }
+
+    pub fn current_styles_mut(&mut self) -> &mut ElementStyles {
+        use self::RestyleDataStyles::*;
+        match self.styles {
+            New(ref mut x) => x,
+            Previous(_) => panic!("Calling current_styles_mut before styling"),
+        }
+    }
+
+    pub fn current_or_previous_styles(&self) -> &ElementStyles {
+        use self::RestyleDataStyles::*;
+        match self.styles {
+            Previous(ref x) => x,
+            New(ref x) => x,
+        }
+    }
+
+    fn finish_styling(&mut self, styles: ElementStyles, damage: RestyleDamage) {
+        debug_assert!(self.get_current_styles().is_none());
+        self.styles = RestyleDataStyles::New(styles);
+        self.damage |= damage;
+    }
 }
 
 /// Style system data associated with a node.
@@ -118,81 +257,225 @@ impl RestyleData {
 /// In both cases, it is wrapped inside an AtomicRefCell to ensure thread
 /// safety.
 #[derive(Debug)]
-pub struct ElementData {
-    styles: ElementDataStyles,
-    pub restyle_data: Option<RestyleData>,
+pub enum ElementData {
+    Initial(Option<ElementStyles>),
+    Restyle(RestyleData),
+    Persistent(ElementStyles),
 }
 
 impl ElementData {
-    pub fn new() -> Self {
-        ElementData {
-            styles: ElementDataStyles::Uninitialized,
-            restyle_data: None,
+    pub fn new(existing: Option<ElementStyles>) -> Self {
+        if let Some(s) = existing {
+            ElementData::Persistent(s)
+        } else {
+            ElementData::Initial(None)
         }
     }
 
-    pub fn has_current_styles(&self) -> bool {
-        match self.styles {
-            ElementDataStyles::Current(_) => true,
+    pub fn is_initial(&self) -> bool {
+        match *self {
+            ElementData::Initial(_) => true,
             _ => false,
         }
     }
 
-    pub fn get_current_styles(&self) -> Option<&ElementStyles> {
-        match self.styles {
-            ElementDataStyles::Current(ref s) => Some(s),
+    pub fn is_unstyled_initial(&self) -> bool {
+        match *self {
+            ElementData::Initial(None) => true,
+            _ => false,
+        }
+    }
+
+    pub fn is_styled_initial(&self) -> bool {
+        match *self {
+            ElementData::Initial(Some(_)) => true,
+            _ => false,
+        }
+    }
+
+    pub fn is_restyle(&self) -> bool {
+        match *self {
+            ElementData::Restyle(_) => true,
+            _ => false,
+        }
+    }
+
+    pub fn as_restyle(&self) -> Option<&RestyleData> {
+        match *self {
+            ElementData::Restyle(ref x) => Some(x),
             _ => None,
         }
     }
 
+    pub fn as_restyle_mut(&mut self) -> Option<&mut RestyleData> {
+        match *self {
+            ElementData::Restyle(ref mut x) => Some(x),
+            _ => None,
+        }
+    }
+
+    pub fn is_persistent(&self) -> bool {
+        match *self {
+            ElementData::Persistent(_) => true,
+            _ => false,
+        }
+    }
+
+    /// Sets an element up for restyle, returning None for an unstyled element.
+    pub fn restyle(&mut self) -> Option<&mut RestyleData> {
+        if self.is_unstyled_initial() {
+            return None;
+        }
+
+        // If the caller never consumed the initial style, make sure that the
+        // change hint represents the delta from zero, rather than a delta from
+        // a previous style that was never observed. Ideally this shouldn't
+        // happen, but we handle it for robustness' sake.
+        let damage_override = if self.is_styled_initial() {
+            RestyleDamage::rebuild_and_reflow()
+        } else {
+            RestyleDamage::empty()
+        };
+
+        if !self.is_restyle() {
+            // Play some tricks to reshape the enum without cloning ElementStyles.
+            let old = mem::replace(self, ElementData::new(None));
+            let styles = match old {
+                ElementData::Initial(Some(s)) => s,
+                ElementData::Persistent(s) => s,
+                _ => unreachable!()
+            };
+            *self = ElementData::Restyle(RestyleData::new(styles));
+        }
+
+        let restyle = self.as_restyle_mut().unwrap();
+        restyle.damage |= damage_override;
+        Some(restyle)
+    }
+
+    /// Converts Initial and Restyle to Persistent. No-op for Persistent.
+    pub fn persist(&mut self) {
+        if self.is_persistent() {
+            return;
+        }
+
+        // Play some tricks to reshape the enum without cloning ElementStyles.
+        let old = mem::replace(self, ElementData::new(None));
+        let styles = match old {
+            ElementData::Initial(i) => i.unwrap(),
+            ElementData::Restyle(r) => match r.styles {
+                RestyleDataStyles::New(n) => n,
+                RestyleDataStyles::Previous(_) => panic!("Never restyled element"),
+            },
+            ElementData::Persistent(_) => unreachable!(),
+        };
+        *self = ElementData::Persistent(styles);
+    }
+
+    pub fn damage(&self) -> RestyleDamage {
+        use self::ElementData::*;
+        match *self {
+            Initial(ref s) => {
+                debug_assert!(s.is_some());
+                RestyleDamage::rebuild_and_reflow()
+            },
+            Restyle(ref r) => {
+                debug_assert!(r.get_current_styles().is_some());
+                r.damage
+            },
+            Persistent(_) => RestyleDamage::empty(),
+        }
+    }
+
+    // A version of the above, with the assertions replaced with warnings to
+    // be more robust in corner-cases. This will go away soon.
+    #[cfg(feature = "gecko")]
+    pub fn damage_sloppy(&self) -> RestyleDamage {
+        use self::ElementData::*;
+        match *self {
+            Initial(ref s) => {
+                if s.is_none() {
+                    error!("Accessing damage on unstyled element");
+                }
+                RestyleDamage::rebuild_and_reflow()
+            },
+            Restyle(ref r) => {
+                if r.get_current_styles().is_none() {
+                    error!("Accessing damage on dirty element");
+                }
+                r.damage
+            },
+            Persistent(_) => RestyleDamage::empty(),
+        }
+    }
+
     pub fn current_styles(&self) -> &ElementStyles {
-        self.get_current_styles().expect("Calling current_styles before or during styling")
+        self.get_current_styles().unwrap()
     }
 
-    // Servo does lazy pseudo computation in layout and needs mutable access
-    // to the current styles
-    #[cfg(not(feature = "gecko"))]
-    pub fn current_pseudos_mut(&mut self) -> &mut PseudoStyles {
-        match self.styles {
-            ElementDataStyles::Current(ref mut s) => &mut s.pseudos,
-            _ => panic!("Calling current_pseudos_mut before or during styling"),
+    pub fn get_current_styles(&self) -> Option<&ElementStyles> {
+        use self::ElementData::*;
+        match *self {
+            Initial(ref x) => x.as_ref(),
+            Restyle(ref x) => x.get_current_styles(),
+            Persistent(ref x) => Some(x),
         }
     }
 
-    pub fn previous_styles(&self) -> Option<&ElementStyles> {
-        match self.styles {
-            ElementDataStyles::Previous(ref s) => s.as_ref(),
-            _ => panic!("Calling previous_styles without having gathered it"),
+    pub fn current_styles_mut(&mut self) -> &mut ElementStyles {
+        use self::ElementData::*;
+        match *self {
+            Initial(ref mut x) => x.as_mut().unwrap(),
+            Restyle(ref mut x) => x.current_styles_mut(),
+            Persistent(ref mut x) => x,
         }
     }
 
-    pub fn previous_styles_mut(&mut self) -> Option<&mut ElementStyles> {
-        match self.styles {
-            ElementDataStyles::Previous(ref mut s) => s.as_mut(),
-            _ => panic!("Calling previous_styles without having gathered it"),
+    pub fn previous_styles(&self) -> Option<&ElementStyles> {
+        use self::ElementData::*;
+        use self::RestyleDataStyles::*;
+        match *self {
+            Initial(_) => None,
+            Restyle(ref x) => match x.styles {
+                Previous(ref styles) => Some(styles),
+                New(_) => panic!("Calling previous_styles after finish_styling"),
+            },
+            Persistent(_) => panic!("Calling previous_styles on Persistent ElementData"),
         }
     }
 
-    pub fn gather_previous_styles<F>(&mut self, f: F)
-        where F: FnOnce() -> Option<ElementStyles>
-    {
-        use self::ElementDataStyles::*;
-        self.styles = match mem::replace(&mut self.styles, Uninitialized) {
-            Uninitialized => Previous(f()),
-            Current(x) => Previous(Some(x)),
-            Previous(x) => Previous(x),
-        };
+    pub fn previous_styles_mut(&mut self) -> Option<&mut ElementStyles> {
+        use self::ElementData::*;
+        use self::RestyleDataStyles::*;
+        match *self {
+            Initial(_) => None,
+            Restyle(ref mut x) => match x.styles {
+                Previous(ref mut styles) => Some(styles),
+                New(_) => panic!("Calling previous_styles after finish_styling"),
+            },
+            Persistent(_) => panic!("Calling previous_styles on Persistent ElementData"),
+        }
     }
 
-    pub fn ensure_restyle_data(&mut self) {
-        if self.restyle_data.is_none() {
-            self.restyle_data = Some(RestyleData::new());
+    pub fn current_or_previous_styles(&self) -> &ElementStyles {
+        use self::ElementData::*;
+        match *self {
+            Initial(ref x) => x.as_ref().unwrap(),
+            Restyle(ref x) => x.current_or_previous_styles(),
+            Persistent(ref x) => x,
         }
     }
 
-    pub fn finish_styling(&mut self, styles: ElementStyles) {
-        debug_assert!(self.styles.is_previous());
-        self.styles = ElementDataStyles::Current(styles);
-        self.restyle_data = None;
+    pub fn finish_styling(&mut self, styles: ElementStyles, damage: RestyleDamage) {
+        use self::ElementData::*;
+        match *self {
+            Initial(ref mut x) => {
+                debug_assert!(x.is_none());
+                debug_assert!(damage == RestyleDamage::rebuild_and_reflow());
+                *x = Some(styles);
+            },
+            Restyle(ref mut x) => x.finish_styling(styles, damage),
+            Persistent(_) => panic!("Calling finish_styling on Persistent ElementData"),
+        };
     }
 }
diff --git a/components/style/dom.rs b/components/style/dom.rs
index 605baed33a7..c2874dee172 100644
--- a/components/style/dom.rs
+++ b/components/style/dom.rs
@@ -7,20 +7,17 @@
 #![allow(unsafe_code)]
 
 use {Atom, Namespace, LocalName};
-use atomic_refcell::{AtomicRef, AtomicRefCell};
+use atomic_refcell::{AtomicRef, AtomicRefCell, AtomicRefMut};
 use data::{ElementStyles, ElementData};
 use element_state::ElementState;
 use parking_lot::RwLock;
 use properties::{ComputedValues, PropertyDeclarationBlock};
-use properties::longhands::display::computed_value as display;
-use restyle_hints::{RESTYLE_DESCENDANTS, RESTYLE_LATER_SIBLINGS, RESTYLE_SELF, RestyleHint};
 use selector_parser::{ElementExt, PseudoElement, RestyleDamage};
 use sink::Push;
 use std::fmt::Debug;
-use std::ops::BitOr;
+use std::ops::{BitOr, BitOrAssign};
 use std::sync::Arc;
 use stylist::ApplicableDeclarationBlock;
-use traversal::DomTraversalContext;
 use util::opts;
 
 pub use style_traits::UnsafeNode;
@@ -46,7 +43,7 @@ impl OpaqueNode {
     }
 }
 
-#[derive(Clone, Copy, PartialEq)]
+#[derive(Clone, Copy, Debug, PartialEq)]
 pub enum StylingMode {
     /// The node has never been styled before, and needs a full style computation.
     Initial,
@@ -59,7 +56,7 @@ pub enum StylingMode {
     Stop,
 }
 
-pub trait TRestyleDamage : Debug + PartialEq + BitOr<Output=Self> + Copy {
+pub trait TRestyleDamage : BitOr<Output=Self> + BitOrAssign + Copy + Debug + PartialEq {
     /// The source for our current computed values in the cascade. This is a
     /// ComputedValues in Servo and a StyleContext in Gecko.
     ///
@@ -76,6 +73,10 @@ pub trait TRestyleDamage : Debug + PartialEq + BitOr<Output=Self> + Copy {
     fn empty() -> Self;
 
     fn rebuild_and_reflow() -> Self;
+
+    fn is_empty(&self) -> bool {
+        *self == Self::empty()
+    }
 }
 
 /// Simple trait to provide basic information about the type of an element.
@@ -121,9 +122,13 @@ pub trait TNode : Sized + Copy + Clone + NodeInfo {
     /// Converts self into an `OpaqueNode`.
     fn opaque(&self) -> OpaqueNode;
 
-    /// While doing a reflow, the node at the root has no parent, as far as we're
-    /// concerned. This method returns `None` at the reflow root.
-    fn layout_parent_element(self, reflow_root: OpaqueNode) -> Option<Self::ConcreteElement>;
+    fn layout_parent_element(self, reflow_root: OpaqueNode) -> Option<Self::ConcreteElement> {
+        if self.opaque() == reflow_root {
+            None
+        } else {
+            self.parent_node().and_then(|n| n.as_element())
+        }
+    }
 
     fn debug_id(self) -> usize;
 
@@ -138,14 +143,6 @@ pub trait TNode : Sized + Copy + Clone + NodeInfo {
     unsafe fn set_can_be_fragmented(&self, value: bool);
 
     fn parent_node(&self) -> Option<Self>;
-
-    fn first_child(&self) -> Option<Self>;
-
-    fn last_child(&self) -> Option<Self>;
-
-    fn prev_sibling(&self) -> Option<Self>;
-
-    fn next_sibling(&self) -> Option<Self>;
 }
 
 pub trait PresentationalHintsSynthetizer {
@@ -158,6 +155,16 @@ pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + Pre
 
     fn as_node(&self) -> Self::ConcreteNode;
 
+    /// While doing a reflow, the element at the root has no parent, as far as we're
+    /// concerned. This method returns `None` at the reflow root.
+    fn layout_parent_element(self, reflow_root: OpaqueNode) -> Option<Self> {
+        if self.as_node().opaque() == reflow_root {
+            None
+        } else {
+            self.parent_element()
+        }
+    }
+
     fn style_attribute(&self) -> Option<&Arc<RwLock<PropertyDeclarationBlock>>>;
 
     fn get_state(&self) -> ElementState;
@@ -165,9 +172,6 @@ pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + Pre
     fn has_attr(&self, namespace: &Namespace, attr: &LocalName) -> bool;
     fn attr_equals(&self, namespace: &Namespace, attr: &LocalName, value: &Atom) -> bool;
 
-    /// Set the restyle damage field.
-    fn set_restyle_damage(self, damage: RestyleDamage);
-
     /// XXX: It's a bit unfortunate we need to pass the current computed values
     /// as an argument here, but otherwise Servo would crash due to double
     /// borrows to return it.
@@ -176,16 +180,23 @@ pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + Pre
                                              pseudo: Option<&PseudoElement>)
         -> Option<&'a <RestyleDamage as TRestyleDamage>::PreExistingComputedValues>;
 
-    /// The concept of a dirty bit doesn't exist in our new restyle algorithm.
-    /// Instead, we associate restyle and change hints with nodes. However, we
-    /// continue to allow the dirty bit to trigger unconditional restyles while
-    /// we transition both Servo and Stylo to the new architecture.
-    fn deprecated_dirty_bit_is_set(&self) -> bool;
-
+    /// Returns true if this element may have a descendant needing style processing.
+    ///
+    /// Note that we cannot guarantee the existence of such an element, because
+    /// it may have been removed from the DOM between marking it for restyle and
+    /// the actual restyle traversal.
     fn has_dirty_descendants(&self) -> bool;
 
+    /// Flag that this element has a descendant for style processing.
+    ///
+    /// Only safe to call with exclusive access to the element.
     unsafe fn set_dirty_descendants(&self);
 
+    /// Flag that this element has no descendant for style processing.
+    ///
+    /// Only safe to call with exclusive access to the element.
+    unsafe fn unset_dirty_descendants(&self);
+
     /// Atomically stores the number of children of this node that we will
     /// need to process during bottom-up traversal.
     fn store_children_to_process(&self, n: isize);
@@ -197,9 +208,7 @@ pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + Pre
     /// Returns true if this element's current style is display:none. Only valid
     /// to call after styling.
     fn is_display_none(&self) -> bool {
-        self.borrow_data().unwrap()
-            .current_styles().primary
-            .get_box().clone_display() == display::T::none
+        self.borrow_data().unwrap().current_styles().is_display_none()
     }
 
     /// Returns true if this node has a styled layout frame that owns the style.
@@ -231,78 +240,37 @@ pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + Pre
             Stop
         };
 
-        let mut mode = match self.borrow_data() {
+        match self.borrow_data() {
             // No element data, no style on the frame.
             None if !self.frame_has_style() => Initial,
             // No element data, style on the frame.
             None => mode_for_descendants,
             // We have element data. Decide below.
-            Some(d) => {
-                if d.has_current_styles() {
-                    // The element has up-to-date style.
-                    debug_assert!(!self.frame_has_style());
-                    debug_assert!(d.restyle_data.is_none());
-                    mode_for_descendants
-                } else {
-                    // The element needs processing.
-                    if d.previous_styles().is_some() {
-                        Restyle
-                    } else {
-                        Initial
-                    }
-                }
+            Some(d) => match *d {
+                ElementData::Restyle(_) => Restyle,
+                ElementData::Persistent(_) => mode_for_descendants,
+                ElementData::Initial(None) => Initial,
+                // We previously computed the initial style for this element
+                // and then never consumed it. This is arguably a bug, since
+                // it means we either styled an element unnecessarily, or missed
+                // an opportunity to coalesce style traversals. However, this
+                // happens now for various reasons, so we just let it slide and
+                // treat it as persistent for now.
+                ElementData::Initial(Some(_)) => mode_for_descendants,
             },
-        };
-
-        // Handle the deprecated dirty bit. This should go away soon.
-        if mode != Initial && self.deprecated_dirty_bit_is_set() {
-            mode = Restyle;
         }
-        mode
-
     }
 
-    /// Immutable borrows the ElementData.
-    fn borrow_data(&self) -> Option<AtomicRef<ElementData>>;
-
     /// Gets a reference to the ElementData container.
     fn get_data(&self) -> Option<&AtomicRefCell<ElementData>>;
 
-    /// Properly marks nodes as dirty in response to restyle hints.
-    fn note_restyle_hint<C: DomTraversalContext<Self::ConcreteNode>>(&self, hint: RestyleHint) {
-        // Bail early if there's no restyling to do.
-        if hint.is_empty() {
-            return;
-        }
-
-        // If the restyle hint is non-empty, we need to restyle either this element
-        // or one of its siblings. Mark our ancestor chain as having dirty descendants.
-        let mut curr = *self;
-        while let Some(parent) = curr.parent_element() {
-            if parent.has_dirty_descendants() { break }
-            unsafe { parent.set_dirty_descendants(); }
-            curr = parent;
-        }
-
-        // Process hints.
-        if hint.contains(RESTYLE_SELF) {
-            unsafe { let _ = C::prepare_for_styling(self); }
-        // XXX(emilio): For now, dirty implies dirty descendants if found.
-        } else if hint.contains(RESTYLE_DESCENDANTS) {
-            unsafe { self.set_dirty_descendants(); }
-            let mut current = self.first_child_element();
-            while let Some(el) = current {
-                unsafe { let _ = C::prepare_for_styling(&el); }
-                current = el.next_sibling_element();
-            }
-        }
+    /// Immutably borrows the ElementData.
+    fn borrow_data(&self) -> Option<AtomicRef<ElementData>> {
+        self.get_data().map(|x| x.borrow())
+    }
 
-        if hint.contains(RESTYLE_LATER_SIBLINGS) {
-            let mut next = ::selectors::Element::next_sibling_element(self);
-            while let Some(sib) = next {
-                unsafe { let _ = C::prepare_for_styling(&sib); }
-                next = ::selectors::Element::next_sibling_element(&sib);
-            }
-        }
+    /// Mutably borrows the ElementData.
+    fn mutate_data(&self) -> Option<AtomicRefMut<ElementData>> {
+        self.get_data().map(|x| x.borrow_mut())
     }
 }
diff --git a/components/style/gecko/context.rs b/components/style/gecko/context.rs
index 4cfb3152b16..1313030f3dc 100644
--- a/components/style/gecko/context.rs
+++ b/components/style/gecko/context.rs
@@ -22,6 +22,10 @@ fn create_or_get_local_context(shared: &SharedStyleContext) -> Rc<LocalStyleCont
     })
 }
 
+pub fn clear_local_context() {
+    LOCAL_CONTEXT_KEY.with(|r| *r.borrow_mut() = None);
+}
+
 pub struct StandaloneStyleContext<'a> {
     pub shared: &'a SharedStyleContext,
     cached_local_context: Rc<LocalStyleContext>,
diff --git a/components/style/gecko/restyle_damage.rs b/components/style/gecko/restyle_damage.rs
index 33dd47c7daa..53523cac04a 100644
--- a/components/style/gecko/restyle_damage.rs
+++ b/components/style/gecko/restyle_damage.rs
@@ -8,13 +8,17 @@ use gecko_bindings::structs;
 use gecko_bindings::structs::{nsChangeHint, nsStyleContext};
 use gecko_bindings::sugar::ownership::FFIArcHelpers;
 use properties::ComputedValues;
-use std::ops::BitOr;
+use std::ops::{BitOr, BitOrAssign};
 use std::sync::Arc;
 
 #[derive(Clone, Copy, Debug, PartialEq)]
 pub struct GeckoRestyleDamage(nsChangeHint);
 
 impl GeckoRestyleDamage {
+    pub fn new(raw: nsChangeHint) -> Self {
+        GeckoRestyleDamage(raw)
+    }
+
     pub fn as_change_hint(&self) -> nsChangeHint {
         self.0
     }
@@ -50,3 +54,8 @@ impl BitOr for GeckoRestyleDamage {
     }
 }
 
+impl BitOrAssign for GeckoRestyleDamage {
+    fn bitor_assign(&mut self, other: Self) {
+        *self = *self | other;
+    }
+}
diff --git a/components/style/gecko/snapshot.rs b/components/style/gecko/snapshot.rs
index 72ee40bb038..bcb0874c853 100644
--- a/components/style/gecko/snapshot.rs
+++ b/components/style/gecko/snapshot.rs
@@ -4,24 +4,38 @@
 
 use element_state::ElementState;
 use gecko::snapshot_helpers;
-use gecko::wrapper::AttrSelectorHelpers;
+use gecko::wrapper::{AttrSelectorHelpers, GeckoElement};
 use gecko_bindings::bindings;
 use gecko_bindings::structs::ServoElementSnapshot;
 use gecko_bindings::structs::ServoElementSnapshotFlags as Flags;
 use restyle_hints::ElementSnapshot;
 use selector_parser::SelectorImpl;
 use selectors::parser::AttrSelector;
+use std::ptr;
 use string_cache::Atom;
 
-// NB: This is sound, in some sense, because during computation of restyle hints
-// the snapshot is kept alive by the modified elements table.
 #[derive(Debug)]
-pub struct GeckoElementSnapshot(*mut ServoElementSnapshot);
+pub struct GeckoElementSnapshot(bindings::ServoElementSnapshotOwned);
+
+impl Drop for GeckoElementSnapshot {
+    fn drop(&mut self) {
+        unsafe {
+            bindings::Gecko_DropElementSnapshot(ptr::read(&self.0 as *const _));
+        }
+    }
+}
 
 impl GeckoElementSnapshot {
-    #[inline]
-    pub unsafe fn from_raw(raw: *mut ServoElementSnapshot) -> Self {
-        GeckoElementSnapshot(raw)
+    pub fn new<'le>(el: GeckoElement<'le>) -> Self {
+        unsafe { GeckoElementSnapshot(bindings::Gecko_CreateElementSnapshot(el.0)) }
+    }
+
+    pub fn borrow_mut_raw(&mut self) -> bindings::ServoElementSnapshotBorrowedMut {
+        &mut *self.0
+    }
+
+    pub fn ptr(&self) -> *const ServoElementSnapshot {
+        &*self.0
     }
 
     #[inline]
@@ -40,7 +54,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
 
     fn match_attr_has(&self, attr: &AttrSelector<SelectorImpl>) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotHasAttr(self.0,
+            bindings::Gecko_SnapshotHasAttr(self.ptr(),
                                             attr.ns_or_null(),
                                             attr.select_name(self.is_html_element_in_html_document()))
         }
@@ -48,7 +62,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
 
     fn match_attr_equals(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrEquals(self.0,
+            bindings::Gecko_SnapshotAttrEquals(self.ptr(),
                                                attr.ns_or_null(),
                                                attr.select_name(self.is_html_element_in_html_document()),
                                                value.as_ptr(),
@@ -58,7 +72,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
 
     fn match_attr_equals_ignore_ascii_case(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrEquals(self.0,
+            bindings::Gecko_SnapshotAttrEquals(self.ptr(),
                                                attr.ns_or_null(),
                                                attr.select_name(self.is_html_element_in_html_document()),
                                                value.as_ptr(),
@@ -67,7 +81,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_includes(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrIncludes(self.0,
+            bindings::Gecko_SnapshotAttrIncludes(self.ptr(),
                                                  attr.ns_or_null(),
                                                  attr.select_name(self.is_html_element_in_html_document()),
                                                  value.as_ptr())
@@ -75,7 +89,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_dash(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrDashEquals(self.0,
+            bindings::Gecko_SnapshotAttrDashEquals(self.ptr(),
                                                    attr.ns_or_null(),
                                                    attr.select_name(self.is_html_element_in_html_document()),
                                                    value.as_ptr())
@@ -83,7 +97,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_prefix(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrHasPrefix(self.0,
+            bindings::Gecko_SnapshotAttrHasPrefix(self.ptr(),
                                                   attr.ns_or_null(),
                                                   attr.select_name(self.is_html_element_in_html_document()),
                                                   value.as_ptr())
@@ -91,7 +105,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_substring(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrHasSubstring(self.0,
+            bindings::Gecko_SnapshotAttrHasSubstring(self.ptr(),
                                                      attr.ns_or_null(),
                                                      attr.select_name(self.is_html_element_in_html_document()),
                                                      value.as_ptr())
@@ -99,7 +113,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_suffix(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrHasSuffix(self.0,
+            bindings::Gecko_SnapshotAttrHasSuffix(self.ptr(),
                                                   attr.ns_or_null(),
                                                   attr.select_name(self.is_html_element_in_html_document()),
                                                   value.as_ptr())
@@ -123,7 +137,7 @@ impl ElementSnapshot for GeckoElementSnapshot {
 
     fn id_attr(&self) -> Option<Atom> {
         let ptr = unsafe {
-            bindings::Gecko_SnapshotAtomAttrValue(self.0,
+            bindings::Gecko_SnapshotAtomAttrValue(self.ptr(),
                                                   atom!("id").as_ptr())
         };
 
@@ -136,7 +150,7 @@ impl ElementSnapshot for GeckoElementSnapshot {
 
     // TODO: share logic with Element::{has_class, each_class}?
     fn has_class(&self, name: &Atom) -> bool {
-        snapshot_helpers::has_class(self.0,
+        snapshot_helpers::has_class(self.ptr(),
                                     name,
                                     bindings::Gecko_SnapshotClassOrClassList)
     }
@@ -144,7 +158,7 @@ impl ElementSnapshot for GeckoElementSnapshot {
     fn each_class<F>(&self, callback: F)
         where F: FnMut(&Atom)
     {
-        snapshot_helpers::each_class(self.0,
+        snapshot_helpers::each_class(self.ptr(),
                                      callback,
                                      bindings::Gecko_SnapshotClassOrClassList)
     }
diff --git a/components/style/gecko/traversal.rs b/components/style/gecko/traversal.rs
index 6827f4e57b0..c323f48552a 100644
--- a/components/style/gecko/traversal.rs
+++ b/components/style/gecko/traversal.rs
@@ -30,7 +30,7 @@ impl<'lc, 'ln> DomTraversalContext<GeckoNode<'ln>> for RecalcStyleOnly<'lc> {
     }
 
     fn process_preorder(&self, node: GeckoNode<'ln>) {
-        if node.is_element() {
+        if node.is_element() && (!self.context.shared_context().skip_root || node.opaque() != self.root) {
             let el = node.as_element().unwrap();
             recalc_style_at::<_, _, Self>(&self.context, self.root, el);
         }
@@ -43,11 +43,7 @@ impl<'lc, 'ln> DomTraversalContext<GeckoNode<'ln>> for RecalcStyleOnly<'lc> {
     /// We don't use the post-order traversal for anything.
     fn needs_postorder_traversal(&self) -> bool { false }
 
-    fn should_traverse_child(parent: GeckoElement<'ln>, child: GeckoNode<'ln>) -> bool {
-        if parent.is_display_none() {
-            return false;
-        }
-
+    fn should_traverse_child(child: GeckoNode<'ln>) -> bool {
         match child.as_element() {
             Some(el) => el.styling_mode() != StylingMode::Stop,
             None => false, // Gecko restyle doesn't need to traverse text nodes.
diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs
index 3d178a5ab89..1bed9b13fde 100644
--- a/components/style/gecko/wrapper.rs
+++ b/components/style/gecko/wrapper.rs
@@ -5,13 +5,12 @@
 #![allow(unsafe_code)]
 
 
-use atomic_refcell::{AtomicRef, AtomicRefCell};
+use atomic_refcell::AtomicRefCell;
 use data::ElementData;
 use dom::{LayoutIterator, NodeInfo, TElement, TNode, UnsafeNode};
 use dom::{OpaqueNode, PresentationalHintsSynthetizer};
 use element_state::ElementState;
 use error_reporting::StdoutErrorReporter;
-use gecko::restyle_damage::GeckoRestyleDamage;
 use gecko::selector_parser::{SelectorImpl, NonTSPseudoClass, PseudoElement};
 use gecko::snapshot_helpers;
 use gecko_bindings::bindings;
@@ -20,20 +19,19 @@ use gecko_bindings::bindings::{Gecko_ElementState, Gecko_GetLastChild, Gecko_Get
 use gecko_bindings::bindings::{Gecko_GetServoDeclarationBlock, Gecko_IsHTMLElementInHTMLDocument};
 use gecko_bindings::bindings::{Gecko_IsLink, Gecko_IsRootElement};
 use gecko_bindings::bindings::{Gecko_IsUnvisitedLink, Gecko_IsVisitedLink, Gecko_Namespace};
+use gecko_bindings::bindings::{Gecko_SetNodeFlags, Gecko_UnsetNodeFlags};
 use gecko_bindings::bindings::{RawGeckoElement, RawGeckoNode};
 use gecko_bindings::bindings::Gecko_ClassOrClassList;
 use gecko_bindings::bindings::Gecko_GetStyleContext;
-use gecko_bindings::bindings::Gecko_SetNodeFlags;
-use gecko_bindings::bindings::Gecko_StoreStyleDifference;
 use gecko_bindings::structs;
-use gecko_bindings::structs::{NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO, NODE_IS_DIRTY_FOR_SERVO};
 use gecko_bindings::structs::{nsIAtom, nsIContent, nsStyleContext};
+use gecko_bindings::structs::NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO;
 use gecko_bindings::structs::NODE_IS_IN_NATIVE_ANONYMOUS_SUBTREE;
 use parking_lot::RwLock;
 use parser::ParserContextExtraData;
 use properties::{ComputedValues, parse_style_attribute};
 use properties::PropertyDeclarationBlock;
-use selector_parser::ElementExt;
+use selector_parser::{ElementExt, Snapshot};
 use selectors::Element;
 use selectors::parser::{AttrSelector, NamespaceConstraint};
 use servo_url::ServoUrl;
@@ -61,6 +59,22 @@ impl<'ln> GeckoNode<'ln> {
         debug_assert!(!self.0.mNodeInfo.mRawPtr.is_null());
         unsafe { &*self.0.mNodeInfo.mRawPtr }
     }
+
+    fn first_child(&self) -> Option<GeckoNode<'ln>> {
+        unsafe { self.0.mFirstChild.as_ref().map(GeckoNode::from_content) }
+    }
+
+    fn last_child(&self) -> Option<GeckoNode<'ln>> {
+        unsafe { Gecko_GetLastChild(self.0).map(GeckoNode) }
+    }
+
+    fn prev_sibling(&self) -> Option<GeckoNode<'ln>> {
+        unsafe { self.0.mPreviousSibling.as_ref().map(GeckoNode::from_content) }
+    }
+
+    fn next_sibling(&self) -> Option<GeckoNode<'ln>> {
+        unsafe { self.0.mNextSibling.as_ref().map(GeckoNode::from_content) }
+    }
 }
 
 impl<'ln> NodeInfo for GeckoNode<'ln> {
@@ -115,14 +129,6 @@ impl<'ln> TNode for GeckoNode<'ln> {
         OpaqueNode(ptr)
     }
 
-    fn layout_parent_element(self, reflow_root: OpaqueNode) -> Option<GeckoElement<'ln>> {
-        if self.opaque() == reflow_root {
-            None
-        } else {
-            self.parent_node().and_then(|x| x.as_element())
-        }
-    }
-
     fn debug_id(self) -> usize {
         unimplemented!()
     }
@@ -146,24 +152,8 @@ impl<'ln> TNode for GeckoNode<'ln> {
         // Maybe this isn’t useful for Gecko?
     }
 
-    fn parent_node(&self) -> Option<GeckoNode<'ln>> {
-        unsafe { self.0.mParent.as_ref().map(GeckoNode) }
-    }
-
-    fn first_child(&self) -> Option<GeckoNode<'ln>> {
-        unsafe { self.0.mFirstChild.as_ref().map(GeckoNode::from_content) }
-    }
-
-    fn last_child(&self) -> Option<GeckoNode<'ln>> {
-        unsafe { Gecko_GetLastChild(self.0).map(GeckoNode) }
-    }
-
-    fn prev_sibling(&self) -> Option<GeckoNode<'ln>> {
-        unsafe { self.0.mPreviousSibling.as_ref().map(GeckoNode::from_content) }
-    }
-
-    fn next_sibling(&self) -> Option<GeckoNode<'ln>> {
-        unsafe { self.0.mNextSibling.as_ref().map(GeckoNode::from_content) }
+    fn parent_node(&self) -> Option<Self> {
+        unsafe { bindings::Gecko_GetParentNode(self.0).map(GeckoNode) }
     }
 
     fn needs_dirty_on_viewport_size_changed(&self) -> bool {
@@ -221,7 +211,7 @@ impl<'le> fmt::Debug for GeckoElement<'le> {
         if let Some(id) = self.get_id() {
             try!(write!(f, " id={}", id));
         }
-        write!(f, ">")
+        write!(f, "> ({:?})", self.0 as *const _)
     }
 }
 
@@ -251,11 +241,16 @@ impl<'le> GeckoElement<'le> {
         unsafe { Gecko_SetNodeFlags(self.as_node().0, flags) }
     }
 
+    fn unset_flags(&self, flags: u32) {
+        unsafe { Gecko_UnsetNodeFlags(self.as_node().0, flags) }
+    }
+
     pub fn clear_data(&self) {
-        let ptr = self.raw_node().mServoData.get();
+        let ptr = self.0.mServoData.get();
         if !ptr.is_null() {
-            let data = unsafe { Box::from_raw(self.raw_node().mServoData.get()) };
-            self.raw_node().mServoData.set(ptr::null_mut());
+            debug!("Dropping ElementData for {:?}", self);
+            let data = unsafe { Box::from_raw(self.0.mServoData.get()) };
+            self.0.mServoData.set(ptr::null_mut());
 
             // Perform a mutable borrow of the data in debug builds. This
             // serves as an assertion that there are no outstanding borrows
@@ -265,20 +260,31 @@ impl<'le> GeckoElement<'le> {
     }
 
     pub fn get_pseudo_style(&self, pseudo: &PseudoElement) -> Option<Arc<ComputedValues>> {
-        self.borrow_data().and_then(|data| data.current_styles().pseudos
-                                               .get(pseudo).map(|c| c.0.clone()))
+        // NB: Gecko sometimes resolves pseudos after an element has already been
+        // marked for restyle. We should consider fixing this, but for now just allow
+        // it with current_or_previous_styles.
+        self.borrow_data().and_then(|data| data.current_or_previous_styles().pseudos
+                                               .get(pseudo).map(|c| c.values.clone()))
     }
 
-    pub fn ensure_data(&self) -> &AtomicRefCell<ElementData> {
+    // Only safe to call with exclusive access to the element.
+    pub unsafe fn ensure_data(&self) -> &AtomicRefCell<ElementData> {
         match self.get_data() {
             Some(x) => x,
             None => {
-                let ptr = Box::into_raw(Box::new(AtomicRefCell::new(ElementData::new())));
-                self.raw_node().mServoData.set(ptr);
+                debug!("Creating ElementData for {:?}", self);
+                let existing = self.get_styles_from_frame();
+                let ptr = Box::into_raw(Box::new(AtomicRefCell::new(ElementData::new(existing))));
+                self.0.mServoData.set(ptr);
                 unsafe { &* ptr }
             },
         }
     }
+
+    /// Creates a blank snapshot for this element.
+    pub fn create_snapshot(&self) -> Snapshot {
+        Snapshot::new(*self)
+    }
 }
 
 lazy_static! {
@@ -325,14 +331,6 @@ impl<'le> TElement for GeckoElement<'le> {
         }
     }
 
-    fn set_restyle_damage(self, damage: GeckoRestyleDamage) {
-        // FIXME(bholley): Gecko currently relies on the dirty bit being set to
-        // drive the post-traversal. This will go away soon.
-        unsafe { self.set_flags(NODE_IS_DIRTY_FOR_SERVO as u32) }
-
-        unsafe { Gecko_StoreStyleDifference(self.as_node().0, damage.as_change_hint()) }
-    }
-
     fn existing_style_for_restyle_damage<'a>(&'a self,
                                              current_cv: Option<&'a Arc<ComputedValues>>,
                                              pseudo: Option<&PseudoElement>)
@@ -350,16 +348,7 @@ impl<'le> TElement for GeckoElement<'le> {
         }
     }
 
-    fn deprecated_dirty_bit_is_set(&self) -> bool {
-        self.flags() & (NODE_IS_DIRTY_FOR_SERVO as u32) != 0
-    }
-
     fn has_dirty_descendants(&self) -> bool {
-        // Return true unconditionally if we're not yet styled. This is a hack
-        // and should go away soon.
-        if self.get_data().is_none() {
-            return true;
-        }
         self.flags() & (NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO as u32) != 0
     }
 
@@ -367,6 +356,10 @@ impl<'le> TElement for GeckoElement<'le> {
         self.set_flags(NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO as u32)
     }
 
+    unsafe fn unset_dirty_descendants(&self) {
+        self.unset_flags(NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO as u32)
+    }
+
     fn store_children_to_process(&self, _: isize) {
         // This is only used for bottom-up traversal, and is thus a no-op for Gecko.
     }
@@ -375,14 +368,9 @@ impl<'le> TElement for GeckoElement<'le> {
         panic!("Atomic child count not implemented in Gecko");
     }
 
-    fn borrow_data(&self) -> Option<AtomicRef<ElementData>> {
-        self.get_data().map(|x| x.borrow())
-    }
-
     fn get_data(&self) -> Option<&AtomicRefCell<ElementData>> {
-        unsafe { self.raw_node().mServoData.get().as_ref() }
+        unsafe { self.0.mServoData.get().as_ref() }
     }
-
 }
 
 impl<'le> PartialEq for GeckoElement<'le> {
@@ -401,8 +389,7 @@ impl<'le> PresentationalHintsSynthetizer for GeckoElement<'le> {
 
 impl<'le> ::selectors::Element for GeckoElement<'le> {
     fn parent_element(&self) -> Option<Self> {
-        let parent = self.as_node().parent_node();
-        parent.and_then(|parent| parent.as_element())
+        unsafe { bindings::Gecko_GetParentElement(self.0).map(GeckoElement) }
     }
 
     fn first_child_element(&self) -> Option<Self> {
diff --git a/components/style/gecko_bindings/bindings.rs b/components/style/gecko_bindings/bindings.rs
index 97d74120f7d..14806754df2 100644
--- a/components/style/gecko_bindings/bindings.rs
+++ b/components/style/gecko_bindings/bindings.rs
@@ -57,6 +57,12 @@ pub type StyleChildrenIteratorBorrowedMutOrNull<'a> = Option<&'a mut StyleChildr
 pub type StyleChildrenIteratorOwnedOrNull = ::gecko_bindings::sugar::ownership::OwnedOrNull<StyleChildrenIterator>;
 enum StyleChildrenIteratorVoid{ }
 pub struct StyleChildrenIterator(StyleChildrenIteratorVoid);
+pub type ServoElementSnapshotBorrowed<'a> = &'a ServoElementSnapshot;
+pub type ServoElementSnapshotBorrowedMut<'a> = &'a mut ServoElementSnapshot;
+pub type ServoElementSnapshotOwned = ::gecko_bindings::sugar::ownership::Owned<ServoElementSnapshot>;
+pub type ServoElementSnapshotBorrowedOrNull<'a> = Option<&'a ServoElementSnapshot>;
+pub type ServoElementSnapshotBorrowedMutOrNull<'a> = Option<&'a mut ServoElementSnapshot>;
+pub type ServoElementSnapshotOwnedOrNull = ::gecko_bindings::sugar::ownership::OwnedOrNull<ServoElementSnapshot>;
 use gecko_bindings::structs::Element;
 use gecko_bindings::structs::FontFamilyList;
 use gecko_bindings::structs::FontFamilyType;
@@ -196,6 +202,15 @@ use gecko_bindings::structs::nsStyleXUL;
 unsafe impl Send for nsStyleXUL {}
 unsafe impl Sync for nsStyleXUL {}
 
+#[repr(i32)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub enum ConsumeStyleBehavior { Consume = 0, DontConsume = 1, }
+#[repr(i32)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub enum LazyComputeBehavior { Allow = 0, Assert = 1, }
+#[repr(i32)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub enum SkipRootBehavior { Skip = 0, DontSkip = 1, }
 pub type RawGeckoNode = nsINode;
 pub type RawGeckoElement = Element;
 pub type RawGeckoDocument = nsIDocument;
@@ -395,49 +410,51 @@ extern "C" {
                                   classList: *mut *mut *mut nsIAtom) -> u32;
 }
 extern "C" {
-    pub fn Gecko_SnapshotAtomAttrValue(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotAtomAttrValue(element: *const ServoElementSnapshot,
                                        attribute: *mut nsIAtom)
      -> *mut nsIAtom;
 }
 extern "C" {
-    pub fn Gecko_SnapshotHasAttr(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotHasAttr(element: *const ServoElementSnapshot,
                                  ns: *mut nsIAtom, name: *mut nsIAtom)
      -> bool;
 }
 extern "C" {
-    pub fn Gecko_SnapshotAttrEquals(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotAttrEquals(element: *const ServoElementSnapshot,
                                     ns: *mut nsIAtom, name: *mut nsIAtom,
                                     str: *mut nsIAtom, ignoreCase: bool)
      -> bool;
 }
 extern "C" {
-    pub fn Gecko_SnapshotAttrDashEquals(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotAttrDashEquals(element: *const ServoElementSnapshot,
                                         ns: *mut nsIAtom, name: *mut nsIAtom,
                                         str: *mut nsIAtom) -> bool;
 }
 extern "C" {
-    pub fn Gecko_SnapshotAttrIncludes(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotAttrIncludes(element: *const ServoElementSnapshot,
                                       ns: *mut nsIAtom, name: *mut nsIAtom,
                                       str: *mut nsIAtom) -> bool;
 }
 extern "C" {
-    pub fn Gecko_SnapshotAttrHasSubstring(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotAttrHasSubstring(element:
+                                              *const ServoElementSnapshot,
                                           ns: *mut nsIAtom,
                                           name: *mut nsIAtom,
                                           str: *mut nsIAtom) -> bool;
 }
 extern "C" {
-    pub fn Gecko_SnapshotAttrHasPrefix(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotAttrHasPrefix(element: *const ServoElementSnapshot,
                                        ns: *mut nsIAtom, name: *mut nsIAtom,
                                        str: *mut nsIAtom) -> bool;
 }
 extern "C" {
-    pub fn Gecko_SnapshotAttrHasSuffix(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotAttrHasSuffix(element: *const ServoElementSnapshot,
                                        ns: *mut nsIAtom, name: *mut nsIAtom,
                                        str: *mut nsIAtom) -> bool;
 }
 extern "C" {
-    pub fn Gecko_SnapshotClassOrClassList(element: *mut ServoElementSnapshot,
+    pub fn Gecko_SnapshotClassOrClassList(element:
+                                              *const ServoElementSnapshot,
                                           class_: *mut *mut nsIAtom,
                                           classList: *mut *mut *mut nsIAtom)
      -> u32;
@@ -580,8 +597,11 @@ extern "C" {
      -> nsChangeHint;
 }
 extern "C" {
-    pub fn Gecko_StoreStyleDifference(node: RawGeckoNodeBorrowed,
-                                      change: nsChangeHint);
+    pub fn Gecko_CreateElementSnapshot(element: RawGeckoElementBorrowed)
+     -> ServoElementSnapshotOwned;
+}
+extern "C" {
+    pub fn Gecko_DropElementSnapshot(snapshot: ServoElementSnapshotOwned);
 }
 extern "C" {
     pub fn Gecko_ClearStyleContents(content: *mut nsStyleContent);
@@ -952,7 +972,7 @@ extern "C" {
     pub fn Gecko_Destroy_nsStyleEffects(ptr: *mut nsStyleEffects);
 }
 extern "C" {
-    pub fn Servo_Node_ClearNodeData(node: RawGeckoNodeBorrowed);
+    pub fn Servo_Element_ClearData(node: RawGeckoElementBorrowed);
 }
 extern "C" {
     pub fn Servo_StyleSheet_Empty(parsing_mode: SheetParsingMode)
@@ -1125,10 +1145,6 @@ extern "C" {
                              value: *const nsACString_internal) -> bool;
 }
 extern "C" {
-    pub fn Servo_ComputedValues_Get(node: RawGeckoNodeBorrowed)
-     -> ServoComputedValuesStrong;
-}
-extern "C" {
     pub fn Servo_ComputedValues_GetForAnonymousBox(parent_style_or_null:
                                                        ServoComputedValuesBorrowedOrNull,
                                                    pseudoTag: *mut nsIAtom,
@@ -1159,14 +1175,32 @@ extern "C" {
     pub fn Servo_Shutdown();
 }
 extern "C" {
-    pub fn Servo_ComputeRestyleHint(element: RawGeckoElementBorrowed,
-                                    snapshot: *mut ServoElementSnapshot,
-                                    set: RawServoStyleSetBorrowed)
-     -> nsRestyleHint;
+    pub fn Servo_Element_GetSnapshot(element: RawGeckoElementBorrowed)
+     -> *mut ServoElementSnapshot;
+}
+extern "C" {
+    pub fn Servo_NoteExplicitHints(element: RawGeckoElementBorrowed,
+                                   restyle_hint: nsRestyleHint,
+                                   change_hint: nsChangeHint);
+}
+extern "C" {
+    pub fn Servo_CheckChangeHint(element: RawGeckoElementBorrowed)
+     -> nsChangeHint;
+}
+extern "C" {
+    pub fn Servo_ResolveStyle(element: RawGeckoElementBorrowed,
+                              set: RawServoStyleSetBorrowed,
+                              consume: ConsumeStyleBehavior,
+                              compute: LazyComputeBehavior)
+     -> ServoComputedValuesStrong;
+}
+extern "C" {
+    pub fn Servo_TraverseSubtree(root: RawGeckoElementBorrowed,
+                                 set: RawServoStyleSetBorrowed,
+                                 skip_root: SkipRootBehavior);
 }
 extern "C" {
-    pub fn Servo_RestyleSubtree(node: RawGeckoNodeBorrowed,
-                                set: RawServoStyleSetBorrowed);
+    pub fn Servo_AssertTreeIsClean(root: RawGeckoElementBorrowed);
 }
 extern "C" {
     pub fn Servo_GetStyleFont(computed_values:
diff --git a/components/style/gecko_bindings/structs_debug.rs b/components/style/gecko_bindings/structs_debug.rs
index 47d1da541aa..4f93aaf7ef7 100644
--- a/components/style/gecko_bindings/structs_debug.rs
+++ b/components/style/gecko_bindings/structs_debug.rs
@@ -2700,9 +2700,46 @@ fn bindgen_test_layout_SourceHook() {
     assert_eq!(::std::mem::align_of::<SourceHook>() , 8usize);
 }
 #[repr(C)]
+#[derive(Debug, Copy)]
+pub struct nsIRunnable {
+    pub _base: nsISupports,
+}
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct nsIRunnable_COMTypeInfo<T, U> {
+    pub _address: u8,
+    pub _phantom_0: ::std::marker::PhantomData<T>,
+    pub _phantom_1: ::std::marker::PhantomData<U>,
+}
+#[test]
+fn bindgen_test_layout_nsIRunnable() {
+    assert_eq!(::std::mem::size_of::<nsIRunnable>() , 8usize);
+    assert_eq!(::std::mem::align_of::<nsIRunnable>() , 8usize);
+}
+impl Clone for nsIRunnable {
+    fn clone(&self) -> Self { *self }
+}
+#[repr(C)]
+pub struct DispatcherTrait__bindgen_vtable {
+}
+#[repr(C)]
+#[derive(Debug, Copy)]
+pub struct DispatcherTrait {
+    pub vtable_: *const DispatcherTrait__bindgen_vtable,
+}
+#[test]
+fn bindgen_test_layout_DispatcherTrait() {
+    assert_eq!(::std::mem::size_of::<DispatcherTrait>() , 8usize);
+    assert_eq!(::std::mem::align_of::<DispatcherTrait>() , 8usize);
+}
+impl Clone for DispatcherTrait {
+    fn clone(&self) -> Self { *self }
+}
+#[repr(C)]
 #[derive(Debug)]
 pub struct nsIGlobalObject {
     pub _base: nsISupports,
+    pub _base_1: DispatcherTrait,
     pub mHostObjectURIs: nsTArray<nsCString>,
     pub mIsDying: bool,
 }
@@ -2715,7 +2752,7 @@ pub struct nsIGlobalObject_COMTypeInfo<T, U> {
 }
 #[test]
 fn bindgen_test_layout_nsIGlobalObject() {
-    assert_eq!(::std::mem::size_of::<nsIGlobalObject>() , 24usize);
+    assert_eq!(::std::mem::size_of::<nsIGlobalObject>() , 32usize);
     assert_eq!(::std::mem::align_of::<nsIGlobalObject>() , 8usize);
 }
 #[repr(C)]
@@ -2759,6 +2796,7 @@ fn bindgen_test_layout_nsPIDOMWindowInner() {
 #[derive(Debug)]
 pub struct nsIDocument {
     pub _base: nsINode,
+    pub _base_1: DispatcherTrait,
     pub mDeprecationWarnedAbout: u64,
     pub mDocWarningWarnedAbout: u64,
     pub mSelectorCache: [u64; 16usize],
@@ -3683,7 +3721,6 @@ pub struct nsINode {
     pub mFirstChild: *mut nsIContent,
     pub __bindgen_anon_1: nsINode__bindgen_ty_1,
     pub mSlots: *mut nsINode_nsSlots,
-    pub mServoData: ServoCell<*mut ServoNodeData>,
 }
 pub type nsINode_BoxQuadOptions = BoxQuadOptions;
 pub type nsINode_ConvertCoordinateOptions = ConvertCoordinateOptions;
@@ -3833,7 +3870,7 @@ impl Clone for nsINode__bindgen_ty_1 {
 }
 #[test]
 fn bindgen_test_layout_nsINode() {
-    assert_eq!(::std::mem::size_of::<nsINode>() , 104usize);
+    assert_eq!(::std::mem::size_of::<nsINode>() , 96usize);
     assert_eq!(::std::mem::align_of::<nsINode>() , 8usize);
 }
 #[repr(C)]
@@ -4109,7 +4146,7 @@ pub struct nsIScriptGlobalObject_COMTypeInfo<T, U> {
 }
 #[test]
 fn bindgen_test_layout_nsIScriptGlobalObject() {
-    assert_eq!(::std::mem::size_of::<nsIScriptGlobalObject>() , 24usize);
+    assert_eq!(::std::mem::size_of::<nsIScriptGlobalObject>() , 32usize);
     assert_eq!(::std::mem::align_of::<nsIScriptGlobalObject>() , 8usize);
 }
 #[repr(C)]
@@ -4132,26 +4169,6 @@ fn bindgen_test_layout_nsIVariant() {
 impl Clone for nsIVariant {
     fn clone(&self) -> Self { *self }
 }
-#[repr(C)]
-#[derive(Debug, Copy)]
-pub struct nsIRunnable {
-    pub _base: nsISupports,
-}
-#[repr(C)]
-#[derive(Debug, Copy, Clone)]
-pub struct nsIRunnable_COMTypeInfo<T, U> {
-    pub _address: u8,
-    pub _phantom_0: ::std::marker::PhantomData<T>,
-    pub _phantom_1: ::std::marker::PhantomData<U>,
-}
-#[test]
-fn bindgen_test_layout_nsIRunnable() {
-    assert_eq!(::std::mem::size_of::<nsIRunnable>() , 8usize);
-    assert_eq!(::std::mem::align_of::<nsIRunnable>() , 8usize);
-}
-impl Clone for nsIRunnable {
-    fn clone(&self) -> Self { *self }
-}
 pub type TimeStampValue = u64;
 #[repr(C)]
 #[derive(Debug)]
@@ -5105,6 +5122,7 @@ fn bindgen_test_layout_RestyleManagerHandle() {
 impl Clone for RestyleManagerHandle {
     fn clone(&self) -> Self { *self }
 }
+pub const nsChangeHint_nsChangeHint_Empty: nsChangeHint = nsChangeHint(0);
 pub const nsChangeHint_nsChangeHint_RepaintFrame: nsChangeHint =
     nsChangeHint(1);
 pub const nsChangeHint_nsChangeHint_NeedReflow: nsChangeHint =
@@ -5504,7 +5522,7 @@ extern "C" {
 }
 #[test]
 fn bindgen_test_layout_nsIContent() {
-    assert_eq!(::std::mem::size_of::<nsIContent>() , 104usize);
+    assert_eq!(::std::mem::size_of::<nsIContent>() , 96usize);
     assert_eq!(::std::mem::align_of::<nsIContent>() , 8usize);
 }
 /**
@@ -5558,6 +5576,7 @@ impl Clone for DocGroup {
 pub struct Element {
     pub _base: FragmentOrElement,
     pub mState: EventStates,
+    pub mServoData: ServoCell<*mut ServoNodeData>,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
@@ -5768,7 +5787,7 @@ extern "C" {
 }
 #[test]
 fn bindgen_test_layout_FragmentOrElement() {
-    assert_eq!(::std::mem::size_of::<FragmentOrElement>() , 128usize);
+    assert_eq!(::std::mem::size_of::<FragmentOrElement>() , 120usize);
     assert_eq!(::std::mem::align_of::<FragmentOrElement>() , 8usize);
 }
 pub const ReferrerPolicy_RP_Default: ReferrerPolicy =
@@ -5776,15 +5795,15 @@ pub const ReferrerPolicy_RP_Default: ReferrerPolicy =
 #[repr(u32)]
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum ReferrerPolicy {
-    RP_No_Referrer = 1,
-    RP_Origin = 2,
-    RP_No_Referrer_When_Downgrade = 0,
-    RP_Origin_When_Crossorigin = 3,
-    RP_Unsafe_URL = 4,
-    RP_Same_Origin = 5,
-    RP_Strict_Origin = 6,
-    RP_Strict_Origin_When_Cross_Origin = 7,
-    RP_Unset = 4294967295,
+    RP_No_Referrer = 2,
+    RP_Origin = 3,
+    RP_No_Referrer_When_Downgrade = 1,
+    RP_Origin_When_Crossorigin = 4,
+    RP_Unsafe_URL = 5,
+    RP_Same_Origin = 6,
+    RP_Strict_Origin = 7,
+    RP_Strict_Origin_When_Cross_Origin = 8,
+    RP_Unset = 0,
 }
 #[repr(C)]
 #[derive(Debug, Copy)]
@@ -6629,10 +6648,11 @@ pub struct nsIPresShell_PointerInfo {
     pub mPointerType: u16,
     pub mActiveState: bool,
     pub mPrimaryState: bool,
+    pub mPreventMouseEventByContent: bool,
 }
 #[test]
 fn bindgen_test_layout_nsIPresShell_PointerInfo() {
-    assert_eq!(::std::mem::size_of::<nsIPresShell_PointerInfo>() , 4usize);
+    assert_eq!(::std::mem::size_of::<nsIPresShell_PointerInfo>() , 6usize);
     assert_eq!(::std::mem::align_of::<nsIPresShell_PointerInfo>() , 2usize);
 }
 impl Clone for nsIPresShell_PointerInfo {
@@ -7014,10 +7034,8 @@ pub const NODE_SHARED_RESTYLE_BIT_1: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_1;
 pub const NODE_SHARED_RESTYLE_BIT_2: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_2;
-pub const NODE_IS_DIRTY_FOR_SERVO: _bindgen_ty_23 =
-    _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_1;
 pub const NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO: _bindgen_ty_23 =
-    _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_2;
+    _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_1;
 pub const NODE_TYPE_SPECIFIC_BITS_OFFSET: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_TYPE_SPECIFIC_BITS_OFFSET;
 #[repr(u32)]
@@ -7384,7 +7402,7 @@ extern "C" {
 }
 #[test]
 fn bindgen_test_layout_Attr() {
-    assert_eq!(::std::mem::size_of::<Attr>() , 152usize);
+    assert_eq!(::std::mem::size_of::<Attr>() , 144usize);
     assert_eq!(::std::mem::align_of::<Attr>() , 8usize);
 }
 #[repr(C)]
@@ -7402,7 +7420,7 @@ pub struct nsIAttribute_COMTypeInfo<T, U> {
 }
 #[test]
 fn bindgen_test_layout_nsIAttribute() {
-    assert_eq!(::std::mem::size_of::<nsIAttribute>() , 112usize);
+    assert_eq!(::std::mem::size_of::<nsIAttribute>() , 104usize);
     assert_eq!(::std::mem::align_of::<nsIAttribute>() , 8usize);
 }
 #[repr(C)]
@@ -7614,8 +7632,6 @@ pub struct ServoElementSnapshot {
     pub mContains: ServoElementSnapshot_Flags,
     pub mAttrs: nsTArray<ServoAttrSnapshot>,
     pub mState: ServoElementSnapshot_ServoStateType,
-    pub mExplicitRestyleHint: nsRestyleHint,
-    pub mExplicitChangeHint: nsChangeHint,
     pub mIsHTMLElementInHTMLDocument: bool,
     pub mIsInChromeDocument: bool,
 }
@@ -7625,7 +7641,7 @@ pub type ServoElementSnapshot_ServoStateType = EventStates_ServoType;
 pub type ServoElementSnapshot_Flags = ServoElementSnapshotFlags;
 #[test]
 fn bindgen_test_layout_ServoElementSnapshot() {
-    assert_eq!(::std::mem::size_of::<ServoElementSnapshot>() , 32usize);
+    assert_eq!(::std::mem::size_of::<ServoElementSnapshot>() , 24usize);
     assert_eq!(::std::mem::align_of::<ServoElementSnapshot>() , 8usize);
 }
 #[repr(C)]
diff --git a/components/style/gecko_bindings/structs_release.rs b/components/style/gecko_bindings/structs_release.rs
index f90edb42f30..fde4d421746 100644
--- a/components/style/gecko_bindings/structs_release.rs
+++ b/components/style/gecko_bindings/structs_release.rs
@@ -2687,9 +2687,46 @@ fn bindgen_test_layout_SourceHook() {
     assert_eq!(::std::mem::align_of::<SourceHook>() , 8usize);
 }
 #[repr(C)]
+#[derive(Debug, Copy)]
+pub struct nsIRunnable {
+    pub _base: nsISupports,
+}
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct nsIRunnable_COMTypeInfo<T, U> {
+    pub _address: u8,
+    pub _phantom_0: ::std::marker::PhantomData<T>,
+    pub _phantom_1: ::std::marker::PhantomData<U>,
+}
+#[test]
+fn bindgen_test_layout_nsIRunnable() {
+    assert_eq!(::std::mem::size_of::<nsIRunnable>() , 8usize);
+    assert_eq!(::std::mem::align_of::<nsIRunnable>() , 8usize);
+}
+impl Clone for nsIRunnable {
+    fn clone(&self) -> Self { *self }
+}
+#[repr(C)]
+pub struct DispatcherTrait__bindgen_vtable {
+}
+#[repr(C)]
+#[derive(Debug, Copy)]
+pub struct DispatcherTrait {
+    pub vtable_: *const DispatcherTrait__bindgen_vtable,
+}
+#[test]
+fn bindgen_test_layout_DispatcherTrait() {
+    assert_eq!(::std::mem::size_of::<DispatcherTrait>() , 8usize);
+    assert_eq!(::std::mem::align_of::<DispatcherTrait>() , 8usize);
+}
+impl Clone for DispatcherTrait {
+    fn clone(&self) -> Self { *self }
+}
+#[repr(C)]
 #[derive(Debug)]
 pub struct nsIGlobalObject {
     pub _base: nsISupports,
+    pub _base_1: DispatcherTrait,
     pub mHostObjectURIs: nsTArray<nsCString>,
     pub mIsDying: bool,
 }
@@ -2702,7 +2739,7 @@ pub struct nsIGlobalObject_COMTypeInfo<T, U> {
 }
 #[test]
 fn bindgen_test_layout_nsIGlobalObject() {
-    assert_eq!(::std::mem::size_of::<nsIGlobalObject>() , 24usize);
+    assert_eq!(::std::mem::size_of::<nsIGlobalObject>() , 32usize);
     assert_eq!(::std::mem::align_of::<nsIGlobalObject>() , 8usize);
 }
 #[repr(C)]
@@ -2746,6 +2783,7 @@ fn bindgen_test_layout_nsPIDOMWindowInner() {
 #[derive(Debug)]
 pub struct nsIDocument {
     pub _base: nsINode,
+    pub _base_1: DispatcherTrait,
     pub mDeprecationWarnedAbout: u64,
     pub mDocWarningWarnedAbout: u64,
     pub mSelectorCache: [u64; 15usize],
@@ -3665,7 +3703,6 @@ pub struct nsINode {
     pub mFirstChild: *mut nsIContent,
     pub __bindgen_anon_1: nsINode__bindgen_ty_1,
     pub mSlots: *mut nsINode_nsSlots,
-    pub mServoData: ServoCell<*mut ServoNodeData>,
 }
 pub type nsINode_BoxQuadOptions = BoxQuadOptions;
 pub type nsINode_ConvertCoordinateOptions = ConvertCoordinateOptions;
@@ -3815,7 +3852,7 @@ impl Clone for nsINode__bindgen_ty_1 {
 }
 #[test]
 fn bindgen_test_layout_nsINode() {
-    assert_eq!(::std::mem::size_of::<nsINode>() , 104usize);
+    assert_eq!(::std::mem::size_of::<nsINode>() , 96usize);
     assert_eq!(::std::mem::align_of::<nsINode>() , 8usize);
 }
 #[repr(C)]
@@ -4091,7 +4128,7 @@ pub struct nsIScriptGlobalObject_COMTypeInfo<T, U> {
 }
 #[test]
 fn bindgen_test_layout_nsIScriptGlobalObject() {
-    assert_eq!(::std::mem::size_of::<nsIScriptGlobalObject>() , 24usize);
+    assert_eq!(::std::mem::size_of::<nsIScriptGlobalObject>() , 32usize);
     assert_eq!(::std::mem::align_of::<nsIScriptGlobalObject>() , 8usize);
 }
 #[repr(C)]
@@ -4114,26 +4151,6 @@ fn bindgen_test_layout_nsIVariant() {
 impl Clone for nsIVariant {
     fn clone(&self) -> Self { *self }
 }
-#[repr(C)]
-#[derive(Debug, Copy)]
-pub struct nsIRunnable {
-    pub _base: nsISupports,
-}
-#[repr(C)]
-#[derive(Debug, Copy, Clone)]
-pub struct nsIRunnable_COMTypeInfo<T, U> {
-    pub _address: u8,
-    pub _phantom_0: ::std::marker::PhantomData<T>,
-    pub _phantom_1: ::std::marker::PhantomData<U>,
-}
-#[test]
-fn bindgen_test_layout_nsIRunnable() {
-    assert_eq!(::std::mem::size_of::<nsIRunnable>() , 8usize);
-    assert_eq!(::std::mem::align_of::<nsIRunnable>() , 8usize);
-}
-impl Clone for nsIRunnable {
-    fn clone(&self) -> Self { *self }
-}
 pub type TimeStampValue = u64;
 #[repr(C)]
 #[derive(Debug)]
@@ -5084,6 +5101,7 @@ fn bindgen_test_layout_RestyleManagerHandle() {
 impl Clone for RestyleManagerHandle {
     fn clone(&self) -> Self { *self }
 }
+pub const nsChangeHint_nsChangeHint_Empty: nsChangeHint = nsChangeHint(0);
 pub const nsChangeHint_nsChangeHint_RepaintFrame: nsChangeHint =
     nsChangeHint(1);
 pub const nsChangeHint_nsChangeHint_NeedReflow: nsChangeHint =
@@ -5464,7 +5482,7 @@ extern "C" {
 }
 #[test]
 fn bindgen_test_layout_nsIContent() {
-    assert_eq!(::std::mem::size_of::<nsIContent>() , 104usize);
+    assert_eq!(::std::mem::size_of::<nsIContent>() , 96usize);
     assert_eq!(::std::mem::align_of::<nsIContent>() , 8usize);
 }
 /**
@@ -5518,6 +5536,7 @@ impl Clone for DocGroup {
 pub struct Element {
     pub _base: FragmentOrElement,
     pub mState: EventStates,
+    pub mServoData: ServoCell<*mut ServoNodeData>,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
@@ -5728,7 +5747,7 @@ extern "C" {
 }
 #[test]
 fn bindgen_test_layout_FragmentOrElement() {
-    assert_eq!(::std::mem::size_of::<FragmentOrElement>() , 128usize);
+    assert_eq!(::std::mem::size_of::<FragmentOrElement>() , 120usize);
     assert_eq!(::std::mem::align_of::<FragmentOrElement>() , 8usize);
 }
 pub const ReferrerPolicy_RP_Default: ReferrerPolicy =
@@ -5736,15 +5755,15 @@ pub const ReferrerPolicy_RP_Default: ReferrerPolicy =
 #[repr(u32)]
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum ReferrerPolicy {
-    RP_No_Referrer = 1,
-    RP_Origin = 2,
-    RP_No_Referrer_When_Downgrade = 0,
-    RP_Origin_When_Crossorigin = 3,
-    RP_Unsafe_URL = 4,
-    RP_Same_Origin = 5,
-    RP_Strict_Origin = 6,
-    RP_Strict_Origin_When_Cross_Origin = 7,
-    RP_Unset = 4294967295,
+    RP_No_Referrer = 2,
+    RP_Origin = 3,
+    RP_No_Referrer_When_Downgrade = 1,
+    RP_Origin_When_Crossorigin = 4,
+    RP_Unsafe_URL = 5,
+    RP_Same_Origin = 6,
+    RP_Strict_Origin = 7,
+    RP_Strict_Origin_When_Cross_Origin = 8,
+    RP_Unset = 0,
 }
 #[repr(C)]
 #[derive(Debug, Copy)]
@@ -6587,10 +6606,11 @@ pub struct nsIPresShell_PointerInfo {
     pub mPointerType: u16,
     pub mActiveState: bool,
     pub mPrimaryState: bool,
+    pub mPreventMouseEventByContent: bool,
 }
 #[test]
 fn bindgen_test_layout_nsIPresShell_PointerInfo() {
-    assert_eq!(::std::mem::size_of::<nsIPresShell_PointerInfo>() , 4usize);
+    assert_eq!(::std::mem::size_of::<nsIPresShell_PointerInfo>() , 6usize);
     assert_eq!(::std::mem::align_of::<nsIPresShell_PointerInfo>() , 2usize);
 }
 impl Clone for nsIPresShell_PointerInfo {
@@ -6972,10 +6992,8 @@ pub const NODE_SHARED_RESTYLE_BIT_1: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_1;
 pub const NODE_SHARED_RESTYLE_BIT_2: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_2;
-pub const NODE_IS_DIRTY_FOR_SERVO: _bindgen_ty_23 =
-    _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_1;
 pub const NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO: _bindgen_ty_23 =
-    _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_2;
+    _bindgen_ty_23::NODE_SHARED_RESTYLE_BIT_1;
 pub const NODE_TYPE_SPECIFIC_BITS_OFFSET: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_TYPE_SPECIFIC_BITS_OFFSET;
 #[repr(u32)]
@@ -7342,7 +7360,7 @@ extern "C" {
 }
 #[test]
 fn bindgen_test_layout_Attr() {
-    assert_eq!(::std::mem::size_of::<Attr>() , 152usize);
+    assert_eq!(::std::mem::size_of::<Attr>() , 144usize);
     assert_eq!(::std::mem::align_of::<Attr>() , 8usize);
 }
 #[repr(C)]
@@ -7360,7 +7378,7 @@ pub struct nsIAttribute_COMTypeInfo<T, U> {
 }
 #[test]
 fn bindgen_test_layout_nsIAttribute() {
-    assert_eq!(::std::mem::size_of::<nsIAttribute>() , 112usize);
+    assert_eq!(::std::mem::size_of::<nsIAttribute>() , 104usize);
     assert_eq!(::std::mem::align_of::<nsIAttribute>() , 8usize);
 }
 #[repr(C)]
@@ -7571,8 +7589,6 @@ pub struct ServoElementSnapshot {
     pub mContains: ServoElementSnapshot_Flags,
     pub mAttrs: nsTArray<ServoAttrSnapshot>,
     pub mState: ServoElementSnapshot_ServoStateType,
-    pub mExplicitRestyleHint: nsRestyleHint,
-    pub mExplicitChangeHint: nsChangeHint,
     pub mIsHTMLElementInHTMLDocument: bool,
     pub mIsInChromeDocument: bool,
 }
@@ -7582,7 +7598,7 @@ pub type ServoElementSnapshot_ServoStateType = EventStates_ServoType;
 pub type ServoElementSnapshot_Flags = ServoElementSnapshotFlags;
 #[test]
 fn bindgen_test_layout_ServoElementSnapshot() {
-    assert_eq!(::std::mem::size_of::<ServoElementSnapshot>() , 32usize);
+    assert_eq!(::std::mem::size_of::<ServoElementSnapshot>() , 24usize);
     assert_eq!(::std::mem::align_of::<ServoElementSnapshot>() , 8usize);
 }
 #[repr(C)]
diff --git a/components/style/gecko_bindings/sugar/ownership.rs b/components/style/gecko_bindings/sugar/ownership.rs
index 4b5401f3eaf..13562011fbb 100644
--- a/components/style/gecko_bindings/sugar/ownership.rs
+++ b/components/style/gecko_bindings/sugar/ownership.rs
@@ -208,6 +208,7 @@ unsafe impl<T: HasArcFFI> FFIArcHelpers for Arc<T> {
 }
 
 #[repr(C)]
+#[derive(Debug)]
 /// Gecko-FFI-safe owned pointer
 /// Cannot be null
 /// Leaks on drop. Please don't drop this.
diff --git a/components/style/matching.rs b/components/style/matching.rs
index 442e2c3fffa..09323631c7f 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -12,7 +12,7 @@ use atomic_refcell::AtomicRefMut;
 use cache::LRUCache;
 use cascade_info::CascadeInfo;
 use context::{SharedStyleContext, StyleContext};
-use data::{ElementData, ElementStyles, PseudoStyles};
+use data::{ComputedStyle, ElementData, ElementStyles, PseudoStyles};
 use dom::{TElement, TNode, TRestyleDamage, UnsafeNode};
 use properties::{CascadeFlags, ComputedValues, SHAREABLE, cascade};
 use properties::longhands::display::computed_value as display;
@@ -24,7 +24,6 @@ use selectors::matching::{AFFECTED_BY_PSEUDO_ELEMENTS, MatchingReason, StyleRela
 use sink::ForgetfulSink;
 use std::collections::HashMap;
 use std::hash::BuildHasherDefault;
-use std::mem;
 use std::slice::IterMut;
 use std::sync::Arc;
 use stylist::ApplicableDeclarationBlock;
@@ -121,7 +120,7 @@ fn element_matches_candidate<E: TElement>(element: &E,
                                           candidate: &mut StyleSharingCandidate,
                                           candidate_element: &E,
                                           shared_context: &SharedStyleContext)
-                                          -> Result<(Arc<ComputedValues>, StrongRuleNode), CacheMiss> {
+                                          -> Result<ComputedStyle, CacheMiss> {
     macro_rules! miss {
         ($miss: ident) => {
             return Err(CacheMiss::$miss);
@@ -187,10 +186,9 @@ fn element_matches_candidate<E: TElement>(element: &E,
     }
 
     let data = candidate_element.borrow_data().unwrap();
-    let current_styles = data.get_current_styles().unwrap();
+    let current_styles = data.current_styles();
 
-    Ok((current_styles.primary.clone(),
-        current_styles.rule_node.clone()))
+    Ok(current_styles.primary.clone())
 }
 
 fn have_same_common_style_affecting_attributes<E: TElement>(element: &E,
@@ -375,7 +373,7 @@ pub enum StyleSharingResult {
     /// LRU cache that was hit and the damage that was done, and the restyle
     /// result the original result of the candidate's styling, that is, whether
     /// it should stop the traversal or not.
-    StyleWasShared(usize, RestyleDamage),
+    StyleWasShared(usize),
 }
 
 // Callers need to pass several boolean flags to cascade_node_pseudo_element.
@@ -496,7 +494,7 @@ trait PrivateMatchMethods: TElement {
     fn share_style_with_candidate_if_possible(&self,
                                               shared_context: &SharedStyleContext,
                                               candidate: &mut StyleSharingCandidate)
-                                              -> Result<(Arc<ComputedValues>, StrongRuleNode), CacheMiss> {
+                                              -> Result<ComputedStyle, CacheMiss> {
         let candidate_element = unsafe {
             Self::ConcreteNode::from_unsafe(&candidate.node).as_element().unwrap()
         };
@@ -590,22 +588,23 @@ pub trait MatchMethods : TElement {
         for (i, &mut (ref mut candidate, ())) in style_sharing_candidate_cache.iter_mut().enumerate() {
             let sharing_result = self.share_style_with_candidate_if_possible(shared_context, candidate);
             match sharing_result {
-                Ok((shared_style, rule_node)) => {
+                Ok(shared_style) => {
                     // Yay, cache hit. Share the style.
 
                     // TODO: add the display: none optimisation here too! Even
                     // better, factor it out/make it a bit more generic so Gecko
                     // can decide more easily if it knows that it's a child of
                     // replaced content, or similar stuff!
-                    let damage =
-                        match self.existing_style_for_restyle_damage(data.previous_styles().map(|x| &x.primary), None) {
-                            Some(ref source) => RestyleDamage::compute(source, &shared_style),
+                    let damage = {
+                        let previous_values = data.previous_styles().map(|x| &x.primary.values);
+                        match self.existing_style_for_restyle_damage(previous_values, None) {
+                            Some(ref source) => RestyleDamage::compute(source, &shared_style.values),
                             None => RestyleDamage::rebuild_and_reflow(),
-                        };
-
-                    data.finish_styling(ElementStyles::new(shared_style, rule_node));
+                        }
+                    };
 
-                    return StyleSharingResult::StyleWasShared(i, damage)
+                    data.finish_styling(ElementStyles::new(shared_style), damage);
+                    return StyleSharingResult::StyleWasShared(i)
                 }
                 Err(miss) => {
                     debug!("Cache miss: {:?}", miss);
@@ -718,7 +717,7 @@ pub trait MatchMethods : TElement {
 
     unsafe fn cascade_node<'a, Ctx>(&self,
                                     context: &Ctx,
-                                    mut data: AtomicRefMut<ElementData>,
+                                    mut data: &mut AtomicRefMut<ElementData>,
                                     parent: Option<Self>,
                                     primary_rule_node: StrongRuleNode,
                                     pseudo_rule_nodes: PseudoRuleNodes,
@@ -727,7 +726,7 @@ pub trait MatchMethods : TElement {
     {
         // Get our parent's style.
         let parent_data = parent.as_ref().map(|x| x.borrow_data().unwrap());
-        let parent_style = parent_data.as_ref().map(|x| &x.current_styles().primary);
+        let parent_style = parent_data.as_ref().map(|x| &x.current_styles().primary.values);
 
         let mut new_styles;
 
@@ -738,8 +737,8 @@ pub trait MatchMethods : TElement {
                     // Update animations before the cascade. This may modify the
                     // value of the old primary style.
                     self.update_animations_for_cascade(context.shared_context(),
-                                                       &mut previous.primary);
-                    (Some(&previous.primary), Some(&mut previous.pseudos))
+                                                       &mut previous.primary.values);
+                    (Some(&previous.primary.values), Some(&mut previous.pseudos))
                 }
             };
 
@@ -753,12 +752,13 @@ pub trait MatchMethods : TElement {
                                                      animate: true,
                                                  });
 
-            new_styles = ElementStyles::new(new_style, primary_rule_node);
+            let primary = ComputedStyle::new(primary_rule_node, new_style);
+            new_styles = ElementStyles::new(primary);
 
             let damage =
                 self.compute_damage_and_cascade_pseudos(old_primary,
                                                         old_pseudos,
-                                                        &new_styles.primary,
+                                                        &new_styles.primary.values,
                                                         &mut new_styles.pseudos,
                                                         context,
                                                         pseudo_rule_nodes);
@@ -771,10 +771,7 @@ pub trait MatchMethods : TElement {
             damage
         };
 
-        data.finish_styling(new_styles);
-        // Drop the mutable borrow early, since Servo's set_restyle_damage also borrows.
-        mem::drop(data);
-        self.set_restyle_damage(damage);
+        data.finish_styling(new_styles, damage);
     }
 
     fn compute_damage_and_cascade_pseudos<'a, Ctx>(&self,
@@ -828,7 +825,7 @@ pub trait MatchMethods : TElement {
             let maybe_rule_node = pseudo_rule_nodes.remove(&pseudo);
 
             // Grab the old pseudo style for analysis.
-            let mut maybe_old_pseudo_style_and_rule_node =
+            let mut maybe_old_pseudo_style =
                 old_pseudos.as_mut().and_then(|x| x.remove(&pseudo));
 
             if maybe_rule_node.is_some() {
@@ -837,17 +834,17 @@ pub trait MatchMethods : TElement {
                 // We have declarations, so we need to cascade. Compute parameters.
                 let animate = <Self as MatchAttr>::Impl::pseudo_is_before_or_after(&pseudo);
                 if animate {
-                    if let Some((ref mut old_pseudo_style, _)) = maybe_old_pseudo_style_and_rule_node {
+                    if let Some(ref mut old_pseudo_style) = maybe_old_pseudo_style {
                         // Update animations before the cascade. This may modify
                         // the value of old_pseudo_style.
                         self.update_animations_for_cascade(context.shared_context(),
-                                                           old_pseudo_style);
+                                                           &mut old_pseudo_style.values);
                     }
                 }
 
-                let new_pseudo_style =
+                let new_pseudo_values =
                     self.cascade_node_pseudo_element(context, Some(new_primary),
-                                                     maybe_old_pseudo_style_and_rule_node.as_ref().map(|s| &s.0),
+                                                     maybe_old_pseudo_style.as_ref().map(|s| &s.values),
                                                      &new_rule_node,
                                                      CascadeBooleans {
                                                          shareable: false,
@@ -856,18 +853,20 @@ pub trait MatchMethods : TElement {
 
                 // Compute restyle damage unless we've already maxed it out.
                 if damage != rebuild_and_reflow {
-                    damage = damage | match maybe_old_pseudo_style_and_rule_node {
+                    damage = damage | match maybe_old_pseudo_style {
                         None => rebuild_and_reflow,
-                        Some((ref old, _)) => self.compute_restyle_damage(Some(old), &new_pseudo_style,
-                                                                          Some(&pseudo)),
+                        Some(ref old) => self.compute_restyle_damage(Some(&old.values),
+                                                                     &new_pseudo_values,
+                                                                     Some(&pseudo)),
                     };
                 }
 
                 // Insert the new entry into the map.
-                let existing = new_pseudos.insert(pseudo, (new_pseudo_style, new_rule_node));
+                let new_pseudo_style = ComputedStyle::new(new_rule_node, new_pseudo_values);
+                let existing = new_pseudos.insert(pseudo, new_pseudo_style);
                 debug_assert!(existing.is_none());
             } else {
-                if maybe_old_pseudo_style_and_rule_node.is_some() {
+                if maybe_old_pseudo_style.is_some() {
                     damage = rebuild_and_reflow;
                 }
             }
diff --git a/components/style/parallel.rs b/components/style/parallel.rs
index e3f4eaf50b1..1017e5fd900 100644
--- a/components/style/parallel.rs
+++ b/components/style/parallel.rs
@@ -6,7 +6,7 @@
 //!
 //! This code is highly unsafe. Keep this file small and easy to audit.
 
-use dom::{OpaqueNode, StylingMode, TElement, TNode, UnsafeNode};
+use dom::{OpaqueNode, TElement, TNode, UnsafeNode};
 use rayon;
 use std::sync::atomic::Ordering;
 use traversal::{STYLE_SHARING_CACHE_HITS, STYLE_SHARING_CACHE_MISSES};
@@ -21,7 +21,6 @@ pub fn traverse_dom<N, C>(root: N,
     where N: TNode,
           C: DomTraversalContext<N>
 {
-    debug_assert!(root.as_element().unwrap().styling_mode() != StylingMode::Stop);
     if opts::get().style_sharing_stats {
         STYLE_SHARING_CACHE_HITS.store(0, Ordering::SeqCst);
         STYLE_SHARING_CACHE_MISSES.store(0, Ordering::SeqCst);
diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs
index 36693efe1a7..03dc39d14ec 100644
--- a/components/style/restyle_hints.rs
+++ b/components/style/restyle_hints.rs
@@ -6,6 +6,8 @@
 
 use Atom;
 use element_state::*;
+#[cfg(feature = "gecko")]
+use gecko_bindings::structs::nsRestyleHint;
 #[cfg(feature = "servo")]
 use heapsize::HeapSizeOf;
 use selector_parser::{AttrValue, ElementExt, NonTSPseudoClass, Snapshot, SelectorImpl};
@@ -23,7 +25,7 @@ use std::sync::Arc;
 /// attribute selectors. Doing this conservatively is expensive, and so we use
 /// RestyleHints to short-circuit work we know is unnecessary.
 bitflags! {
-    pub flags RestyleHint: u8 {
+    pub flags RestyleHint: u32 {
         #[doc = "Rerun selector matching on the element."]
         const RESTYLE_SELF = 0x01,
         #[doc = "Rerun selector matching on all of the element's descendants."]
@@ -35,6 +37,21 @@ bitflags! {
     }
 }
 
+#[cfg(feature = "gecko")]
+impl From<nsRestyleHint> for RestyleHint {
+    fn from(raw: nsRestyleHint) -> Self {
+        use std::mem;
+        let raw_bits: u32 = unsafe { mem::transmute(raw) };
+        // FIXME(bholley): Finish aligning the binary representations here and
+        // then .expect() the result of the checked version.
+        if Self::from_bits(raw_bits).is_none() {
+            error!("stylo: dropping unsupported restyle hint bits");
+        }
+
+        Self::from_bits_truncate(raw_bits)
+    }
+}
+
 #[cfg(feature = "servo")]
 impl HeapSizeOf for RestyleHint {
     fn heap_size_of_children(&self) -> usize { 0 }
diff --git a/components/style/sequential.rs b/components/style/sequential.rs
index 333a9e3de4c..8e04b53e57e 100644
--- a/components/style/sequential.rs
+++ b/components/style/sequential.rs
@@ -4,7 +4,7 @@
 
 //! Implements sequential traversal over the DOM tree.
 
-use dom::{StylingMode, TElement, TNode};
+use dom::TNode;
 use traversal::DomTraversalContext;
 
 pub fn traverse_dom<N, C>(root: N,
@@ -26,7 +26,6 @@ pub fn traverse_dom<N, C>(root: N,
         }
     }
 
-    debug_assert!(root.as_element().unwrap().styling_mode() != StylingMode::Stop);
     let context = C::new(shared, root.opaque());
     doit::<N, C>(&context, root);
 
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index b5d36066238..c0910a72c81 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -5,6 +5,7 @@
 //! Selector matching.
 
 use {Atom, LocalName};
+use data::ComputedStyle;
 use dom::PresentationalHintsSynthetizer;
 use element_state::*;
 use error_reporting::StdoutErrorReporter;
@@ -270,7 +271,7 @@ impl Stylist {
                                          pseudo: &PseudoElement,
                                          parent: Option<&Arc<ComputedValues>>,
                                          inherit_all: bool)
-                                         -> Option<(Arc<ComputedValues>, StrongRuleNode)> {
+                                         -> Option<ComputedStyle> {
         debug_assert!(SelectorImpl::pseudo_element_cascade_type(pseudo).is_precomputed());
         if let Some(declarations) = self.precomputed_pseudo_element_decls.get(pseudo) {
             // FIXME(emilio): When we've taken rid of the cascade we can just
@@ -291,9 +292,9 @@ impl Stylist {
                                     None,
                                     Box::new(StdoutErrorReporter),
                                     flags);
-            Some((Arc::new(computed), rule_node))
+            Some(ComputedStyle::new(rule_node, Arc::new(computed)))
         } else {
-            parent.map(|p| (p.clone(), self.rule_tree.root()))
+            parent.map(|p| ComputedStyle::new(self.rule_tree.root(), p.clone()))
         }
     }
 
@@ -322,14 +323,14 @@ impl Stylist {
         };
         self.precomputed_values_for_pseudo(&pseudo, Some(parent_style), inherit_all)
             .expect("style_for_anonymous_box(): No precomputed values for that pseudo!")
-            .0
+            .values
     }
 
     pub fn lazily_compute_pseudo_element_style<E>(&self,
                                                   element: &E,
                                                   pseudo: &PseudoElement,
                                                   parent: &Arc<ComputedValues>)
-                                                  -> Option<(Arc<ComputedValues>, StrongRuleNode)>
+                                                  -> Option<ComputedStyle>
         where E: ElementExt +
                  fmt::Debug +
                  PresentationalHintsSynthetizer
@@ -359,7 +360,7 @@ impl Stylist {
                                 Box::new(StdoutErrorReporter),
                                 CascadeFlags::empty());
 
-        Some((Arc::new(computed), rule_node))
+        Some(ComputedStyle::new(rule_node, Arc::new(computed)))
     }
 
     pub fn set_device(&mut self, mut device: Device, stylesheets: &[Arc<Stylesheet>]) {
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index 2b26fe61143..ca76f167541 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -6,13 +6,14 @@
 
 use atomic_refcell::{AtomicRefCell, AtomicRefMut};
 use context::{LocalStyleContext, SharedStyleContext, StyleContext};
-use data::ElementData;
+use data::{ElementData, RestyleData, StoredRestyleHint};
 use dom::{OpaqueNode, StylingMode, TElement, TNode, UnsafeNode};
 use matching::{MatchMethods, StyleSharingResult};
+use restyle_hints::{RESTYLE_DESCENDANTS, RESTYLE_LATER_SIBLINGS, RESTYLE_SELF};
 use selectors::bloom::BloomFilter;
 use selectors::matching::StyleRelations;
 use std::cell::RefCell;
-use std::mem;
+use std::marker::PhantomData;
 use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
 use tid::tid;
 use util::opts;
@@ -109,7 +110,7 @@ fn insert_ancestors_into_bloom_filter<E>(bf: &mut Box<BloomFilter>,
         ancestors += 1;
 
         el.insert_into_bloom_filter(&mut **bf);
-        el = match el.as_node().layout_parent_element(root) {
+        el = match el.layout_parent_element(root) {
             None => break,
             Some(p) => p,
         };
@@ -147,18 +148,6 @@ pub fn remove_from_bloom_filter<'a, N, C>(context: &C, root: OpaqueNode, node: N
     };
 }
 
-pub fn prepare_for_styling<E: TElement>(element: E,
-                                        data: &AtomicRefCell<ElementData>)
-                                        -> AtomicRefMut<ElementData> {
-    let mut d = data.borrow_mut();
-    d.gather_previous_styles(|| element.get_styles_from_frame());
-    if d.previous_styles().is_some() {
-        d.ensure_restyle_data();
-    }
-
-    d
-}
-
 pub trait DomTraversalContext<N: TNode> {
     type SharedContext: Sync + 'static;
 
@@ -179,21 +168,22 @@ pub trait DomTraversalContext<N: TNode> {
     fn needs_postorder_traversal(&self) -> bool { true }
 
     /// Returns true if traversal should visit the given child.
-    fn should_traverse_child(parent: N::ConcreteElement, child: N) -> bool;
+    fn should_traverse_child(child: N) -> bool;
 
     /// Helper for the traversal implementations to select the children that
     /// should be enqueued for processing.
     fn traverse_children<F: FnMut(N)>(parent: N::ConcreteElement, mut f: F)
     {
-        // If we enqueue any children for traversal, we need to set the dirty
-        // descendants bit. Avoid doing it more than once.
-        let mut marked_dirty_descendants = false;
+        use dom::StylingMode::Restyle;
+
+        if parent.is_display_none() {
+            return;
+        }
 
         for kid in parent.as_node().children() {
-            if Self::should_traverse_child(parent, kid) {
-                if !marked_dirty_descendants {
+            if Self::should_traverse_child(kid) {
+                if kid.as_element().map_or(false, |el| el.styling_mode() == Restyle) {
                     unsafe { parent.set_dirty_descendants(); }
-                    marked_dirty_descendants = true;
                 }
                 f(kid);
             }
@@ -208,13 +198,6 @@ pub trait DomTraversalContext<N: TNode> {
     /// children of |element|.
     unsafe fn ensure_element_data(element: &N::ConcreteElement) -> &AtomicRefCell<ElementData>;
 
-    /// Sets up the appropriate data structures to style or restyle a node,
-    /// returing a mutable handle to the node data upon which further style
-    /// calculations can be performed.
-    unsafe fn prepare_for_styling(element: &N::ConcreteElement) -> AtomicRefMut<ElementData> {
-        prepare_for_styling(*element, Self::ensure_element_data(element))
-    }
-
     /// Clears the ElementData attached to this element, if any.
     ///
     /// This is only safe to call in top-down traversal before processing the
@@ -235,65 +218,40 @@ pub fn relations_are_shareable(relations: &StyleRelations) -> bool {
                           AFFECTED_BY_PRESENTATIONAL_HINTS)
 }
 
-pub fn ensure_element_styled<'a, E, C>(element: E,
-                                       context: &'a C)
-    where E: TElement,
-          C: StyleContext<'a>
-{
-    let mut display_none = false;
-    ensure_element_styled_internal(element, context, &mut display_none);
-}
-
-#[allow(unsafe_code)]
-fn ensure_element_styled_internal<'a, E, C>(element: E,
-                                            context: &'a C,
-                                            parents_had_display_none: &mut bool)
+/// Handles lazy resolution of style in display:none subtrees. See the comment
+/// at the callsite in query.rs.
+pub fn style_element_in_display_none_subtree<'a, E, C, F>(element: E,
+                                                          init_data: &F,
+                                                          context: &'a C) -> E
     where E: TElement,
-          C: StyleContext<'a>
+          C: StyleContext<'a>,
+          F: Fn(E),
 {
-    use properties::longhands::display::computed_value as display;
-
-    // NB: The node data must be initialized here.
-
-    // We need to go to the root and ensure their style is up to date.
-    //
-    // This means potentially a bit of wasted work (usually not much). We could
-    // add a flag at the node at which point we stopped the traversal to know
-    // where should we stop, but let's not add that complication unless needed.
-    let parent = element.parent_element();
-    if let Some(parent) = parent {
-        ensure_element_styled_internal(parent, context, parents_had_display_none);
+    // Check the base case.
+    if element.get_data().is_some() {
+        debug_assert!(element.is_display_none());
+        return element;
     }
 
-    // Common case: our style is already resolved and none of our ancestors had
-    // display: none.
-    //
-    // We only need to mark whether we have display none, and forget about it,
-    // our style is up to date.
-    if let Some(data) = element.borrow_data() {
-        if let Some(style) = data.get_current_styles().map(|x| &x.primary) {
-            if !*parents_had_display_none {
-                *parents_had_display_none = style.get_box().clone_display() == display::T::none;
-                return;
-            }
-        }
-    }
+    // Ensure the parent is styled.
+    let parent = element.parent_element().unwrap();
+    let display_none_root = style_element_in_display_none_subtree(parent, init_data, context);
 
-    // Otherwise, our style might be out of date. Time to do selector matching
-    // if appropriate and cascade the node.
-    //
-    // Note that we could add the bloom filter's complexity here, but that's
-    // probably not necessary since we're likely to be matching only a few
-    // nodes, at best.
-    let data = prepare_for_styling(element, element.get_data().unwrap());
+    // Initialize our data.
+    init_data(element);
+
+    // Resolve our style.
+    let mut data = element.mutate_data().unwrap();
     let match_results = element.match_element(context, None);
     unsafe {
         let shareable = match_results.primary_is_shareable();
-        element.cascade_node(context, data, parent,
+        element.cascade_node(context, &mut data, Some(parent),
                              match_results.primary,
                              match_results.per_pseudo,
                              shareable);
     }
+
+    display_none_root
 }
 
 /// Calculates the style for a single node.
@@ -307,110 +265,247 @@ pub fn recalc_style_at<'a, E, C, D>(context: &'a C,
           D: DomTraversalContext<E::ConcreteNode>
 {
     // Get the style bloom filter.
+    //
+    // FIXME(bholley): We need to do these even in the StylingMode::Stop case
+    // to handshake with the unconditional pop during servo's bottom-up
+    // traversal. We should avoid doing work here in the Stop case when we
+    // redesign the bloom filter.
     let mut bf = take_thread_local_bloom_filter(element.parent_element(), root, context.shared_context());
 
     let mode = element.styling_mode();
-    debug_assert!(mode != StylingMode::Stop, "Parent should not have enqueued us");
-    if mode != StylingMode::Traverse {
-        let mut data = unsafe { D::prepare_for_styling(&element) };
-
-        // Check to see whether we can share a style with someone.
-        let style_sharing_candidate_cache =
-            &mut context.local_context().style_sharing_candidate_cache.borrow_mut();
-
-        let sharing_result = if element.parent_element().is_none() {
-            StyleSharingResult::CannotShare
-        } else {
-            unsafe { element.share_style_if_possible(style_sharing_candidate_cache,
-                                                     context.shared_context(), &mut data) }
-        };
+    let should_compute = element.borrow_data().map_or(true, |d| d.get_current_styles().is_none());
+    debug!("recalc_style_at: {:?} (should_compute={:?} mode={:?}, data={:?})",
+           element, should_compute, mode, element.borrow_data());
+
+    let (computed_display_none, propagated_hint) = if should_compute {
+        compute_style::<_, _, D>(context, element, &*bf)
+    } else {
+        (false, StoredRestyleHint::empty())
+    };
 
-        // Otherwise, match and cascade selectors.
-        match sharing_result {
-            StyleSharingResult::CannotShare => {
-                let match_results;
-                let shareable_element = {
-                    if opts::get().style_sharing_stats {
-                        STYLE_SHARING_CACHE_MISSES.fetch_add(1, Ordering::Relaxed);
-                    }
-
-                    // Perform the CSS selector matching.
-                    match_results = element.match_element(context, Some(&*bf));
-                    if match_results.primary_is_shareable() {
-                        Some(element)
-                    } else {
-                        None
-                    }
-                };
-                let relations = match_results.relations;
-
-                // Perform the CSS cascade.
-                unsafe {
-                    let shareable = match_results.primary_is_shareable();
-                    element.cascade_node(context, data, element.parent_element(),
-                                         match_results.primary,
-                                         match_results.per_pseudo,
-                                         shareable);
-                }
+    // Preprocess children, computing restyle hints and handling sibling relationships.
+    //
+    // We don't need to do this if we're not traversing children, or if we're performing
+    // initial styling.
+    let will_traverse_children = !computed_display_none &&
+                                 (mode == StylingMode::Restyle ||
+                                  mode == StylingMode::Traverse);
+    if will_traverse_children {
+        preprocess_children::<_, _, D>(context, element, propagated_hint,
+                                       mode == StylingMode::Restyle);
+    }
 
-                // Add ourselves to the LRU cache.
-                if let Some(element) = shareable_element {
-                    style_sharing_candidate_cache.insert_if_possible(&element,
-                                                                     &element.borrow_data()
-                                                                             .unwrap()
-                                                                             .current_styles()
-                                                                             .primary,
-                                                                     relations);
-                }
-            }
-            StyleSharingResult::StyleWasShared(index, damage) => {
+    let unsafe_layout_node = element.as_node().to_unsafe();
+
+    // Before running the children, we need to insert our nodes into the bloom
+    // filter.
+    debug!("[{}] + {:X}", tid(), unsafe_layout_node.0);
+    element.insert_into_bloom_filter(&mut *bf);
+
+    // NB: flow construction updates the bloom filter on the way up.
+    put_thread_local_bloom_filter(bf, &unsafe_layout_node, context.shared_context());
+}
+
+fn compute_style<'a, E, C, D>(context: &'a C,
+                              element: E,
+                              bloom_filter: &BloomFilter) -> (bool, StoredRestyleHint)
+    where E: TElement,
+          C: StyleContext<'a>,
+          D: DomTraversalContext<E::ConcreteNode>
+{
+    let mut data = unsafe { D::ensure_element_data(&element).borrow_mut() };
+    debug_assert!(!data.is_persistent());
+
+    // Check to see whether we can share a style with someone.
+    let style_sharing_candidate_cache =
+        &mut context.local_context().style_sharing_candidate_cache.borrow_mut();
+
+    let sharing_result = if element.parent_element().is_none() {
+        StyleSharingResult::CannotShare
+    } else {
+        unsafe { element.share_style_if_possible(style_sharing_candidate_cache,
+                                                 context.shared_context(), &mut data) }
+    };
+
+    // Otherwise, match and cascade selectors.
+    match sharing_result {
+        StyleSharingResult::CannotShare => {
+            let match_results;
+            let shareable_element = {
                 if opts::get().style_sharing_stats {
-                    STYLE_SHARING_CACHE_HITS.fetch_add(1, Ordering::Relaxed);
+                    STYLE_SHARING_CACHE_MISSES.fetch_add(1, Ordering::Relaxed);
                 }
-                style_sharing_candidate_cache.touch(index);
 
-                // Drop the mutable borrow early, since Servo's set_restyle_damage also borrows.
-                mem::drop(data);
+                // Perform the CSS selector matching.
+                match_results = element.match_element(context, Some(bloom_filter));
+                if match_results.primary_is_shareable() {
+                    Some(element)
+                } else {
+                    None
+                }
+            };
+            let relations = match_results.relations;
+
+            // Perform the CSS cascade.
+            unsafe {
+                let shareable = match_results.primary_is_shareable();
+                element.cascade_node(context, &mut data,
+                                     element.parent_element(),
+                                     match_results.primary,
+                                     match_results.per_pseudo,
+                                     shareable);
+            }
 
-                element.set_restyle_damage(damage);
+            // Add ourselves to the LRU cache.
+            if let Some(element) = shareable_element {
+                style_sharing_candidate_cache.insert_if_possible(&element,
+                                                                 &data.current_styles().primary.values,
+                                                                 relations);
             }
         }
+        StyleSharingResult::StyleWasShared(index) => {
+            if opts::get().style_sharing_stats {
+                STYLE_SHARING_CACHE_HITS.fetch_add(1, Ordering::Relaxed);
+            }
+            style_sharing_candidate_cache.touch(index);
+        }
     }
 
-    if element.is_display_none() {
-        // If this element is display:none, throw away all style data in the subtree.
-        fn clear_descendant_data<E: TElement, D: DomTraversalContext<E::ConcreteNode>>(el: E) {
-            for kid in el.as_node().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
-                    // descendants with data.
-                    if kid.get_data().is_some() {
-                        unsafe { D::clear_element_data(&kid) };
-                        clear_descendant_data::<_, D>(kid);
-                    }
-                }
-            }
+    // If we're restyling this element to display:none, throw away all style data
+    // in the subtree, notify the caller to early-return.
+    let display_none = data.current_styles().is_display_none();
+    if display_none {
+        debug!("New element style is display:none - clearing data from descendants.");
+        clear_descendant_data(element, &|e| unsafe { D::clear_element_data(&e) });
+    }
+
+    (display_none, data.as_restyle().map_or(StoredRestyleHint::empty(), |r| r.hint.propagate()))
+}
+
+fn preprocess_children<'a, E, C, D>(context: &'a C,
+                                    element: E,
+                                    mut propagated_hint: StoredRestyleHint,
+                                    restyled_parent: bool)
+    where E: TElement,
+          C: StyleContext<'a>,
+          D: DomTraversalContext<E::ConcreteNode>
+{
+    // Loop over all the children.
+    for child in element.as_node().children() {
+        // FIXME(bholley): Add TElement::element_children instead of this.
+        let child = match child.as_element() {
+            Some(el) => el,
+            None => continue,
         };
-        clear_descendant_data::<_, D>(element);
-    } else if mode == StylingMode::Restyle {
-        // If we restyled this node, conservatively mark all our children as needing
-        // processing. The eventual algorithm we're designing does this in a more granular
-        // fashion.
-        for kid in element.as_node().children() {
-            if let Some(kid) = kid.as_element() {
-                unsafe { let _ = D::prepare_for_styling(&kid); }
+
+        // Set up our lazy child restyle data.
+        let mut child_data = unsafe { LazyRestyleData::<E, D>::new(&child) };
+
+        // Propagate the parent and sibling restyle hint.
+        if !propagated_hint.is_empty() {
+            child_data.ensure().map(|d| d.hint.insert(&propagated_hint));
+        }
+
+        // Handle element snashots.
+        if child_data.has_snapshot() {
+            // Compute the restyle hint.
+            let mut restyle_data = child_data.ensure().unwrap();
+            let mut hint = context.shared_context().stylist
+                                  .compute_restyle_hint(&child,
+                                                        restyle_data.snapshot.as_ref().unwrap(),
+                                                        child.get_state());
+
+            // If the hint includes a directive for later siblings, strip
+            // it out and modify the base hint for future siblings.
+            if hint.contains(RESTYLE_LATER_SIBLINGS) {
+                hint.remove(RESTYLE_LATER_SIBLINGS);
+                propagated_hint.insert(&(RESTYLE_SELF | RESTYLE_DESCENDANTS).into());
             }
+
+            // Insert the hint.
+            if !hint.is_empty() {
+                restyle_data.hint.insert(&hint.into());
+            }
+        }
+
+        // If we restyled this node, conservatively mark all our children as
+        // needing a re-cascade. Once we have the rule tree, we will be able
+        // to distinguish between re-matching and re-cascading.
+        if restyled_parent {
+            child_data.ensure();
         }
     }
+}
 
-    let unsafe_layout_node = element.as_node().to_unsafe();
+pub fn clear_descendant_data<E: TElement, F: Fn(E)>(el: E, clear_data: &F) {
+    for kid in el.as_node().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
+            // descendants with data.
+            if kid.get_data().is_some() {
+                clear_data(kid);
+                clear_descendant_data(kid, clear_data);
+            }
+        }
+    }
 
-    // Before running the children, we need to insert our nodes into the bloom
-    // filter.
-    debug!("[{}] + {:X}", tid(), unsafe_layout_node.0);
-    element.insert_into_bloom_filter(&mut *bf);
+    unsafe { el.unset_dirty_descendants(); }
+}
 
-    // NB: flow construction updates the bloom filter on the way up.
-    put_thread_local_bloom_filter(bf, &unsafe_layout_node, context.shared_context());
+/// Various steps in the child preparation algorithm above may cause us to lazily
+/// instantiate the ElementData on the child. Encapsulate that logic into a
+/// convenient abstraction.
+struct LazyRestyleData<'b, E: TElement + 'b, D: DomTraversalContext<E::ConcreteNode>> {
+    data: Option<AtomicRefMut<'b, ElementData>>,
+    element: &'b E,
+    phantom: PhantomData<D>,
+}
+
+impl<'b, E: TElement, D: DomTraversalContext<E::ConcreteNode>> LazyRestyleData<'b, E, D> {
+    /// This may lazily instantiate ElementData, and is therefore only safe to
+    /// call on an element for which we have exclusive access.
+    unsafe fn new(element: &'b E) -> Self {
+        LazyRestyleData {
+            data: None,
+            element: element,
+            phantom: PhantomData,
+        }
+    }
+
+    fn ensure(&mut self) -> Option<&mut RestyleData> {
+        if self.data.is_none() {
+            let mut d = unsafe { D::ensure_element_data(self.element).borrow_mut() };
+            d.restyle();
+            self.data = Some(d);
+        }
+
+        self.data.as_mut().unwrap().as_restyle_mut()
+    }
+
+    /// Checks for the existence of an element snapshot without lazily instantiating
+    /// anything. This allows the traversal to cheaply pass through already-styled
+    /// nodes when they don't need a restyle.
+    fn has_snapshot(&self) -> bool {
+        // If there's no element data, we're done.
+        let raw_data = self.element.get_data();
+        if raw_data.is_none() {
+            debug_assert!(self.data.is_none());
+            return false;
+        }
+
+        // If there is element data, we still may not have committed to processing
+        // the node. Carefully get a reference to the data.
+        let maybe_tmp_borrow;
+        let borrow_ref = match self.data {
+            Some(ref d) => d,
+            None => {
+                maybe_tmp_borrow = raw_data.unwrap().borrow_mut();
+                &maybe_tmp_borrow
+            }
+        };
+
+        // Check for a snapshot.
+        borrow_ref.as_restyle().map_or(false, |d| d.snapshot.is_some())
+    }
 }
diff --git a/ports/geckolib/glue.rs b/ports/geckolib/glue.rs
index a4e18b22258..4cfb8a50662 100644
--- a/ports/geckolib/glue.rs
+++ b/ports/geckolib/glue.rs
@@ -8,21 +8,27 @@ use cssparser::ToCss as ParserToCss;
 use env_logger;
 use euclid::Size2D;
 use parking_lot::RwLock;
+use selectors::Element;
 use servo_url::ServoUrl;
 use std::fmt::Write;
 use std::mem::transmute;
+use std::ptr;
 use std::sync::{Arc, Mutex};
 use style::arc_ptr_eq;
+use style::atomic_refcell::AtomicRefMut;
 use style::context::{LocalStyleContextCreationInfo, ReflowGoal, SharedStyleContext};
-use style::dom::{NodeInfo, StylingMode, TElement, TNode};
+use style::data::{ElementData, RestyleData};
+use style::dom::{StylingMode, TElement, TNode, TRestyleDamage};
 use style::error_reporting::StdoutErrorReporter;
-use style::gecko::data::{NUM_THREADS, PerDocumentStyleData};
+use style::gecko::context::StandaloneStyleContext;
+use style::gecko::context::clear_local_context;
+use style::gecko::data::{NUM_THREADS, PerDocumentStyleData, PerDocumentStyleDataImpl};
+use style::gecko::restyle_damage::GeckoRestyleDamage;
 use style::gecko::selector_parser::{SelectorImpl, PseudoElement};
-use style::gecko::snapshot::GeckoElementSnapshot;
 use style::gecko::traversal::RecalcStyleOnly;
-use style::gecko::wrapper::{GeckoElement, GeckoNode};
 use style::gecko::wrapper::DUMMY_BASE_URL;
-use style::gecko_bindings::bindings::{RawGeckoElementBorrowed, RawGeckoNodeBorrowed};
+use style::gecko::wrapper::GeckoElement;
+use style::gecko_bindings::bindings;
 use style::gecko_bindings::bindings::{RawServoDeclarationBlockBorrowed, RawServoDeclarationBlockStrong};
 use style::gecko_bindings::bindings::{RawServoStyleRuleBorrowed, RawServoStyleRuleStrong};
 use style::gecko_bindings::bindings::{RawServoStyleSetBorrowed, RawServoStyleSetOwned};
@@ -32,11 +38,12 @@ use style::gecko_bindings::bindings::{ServoCssRulesBorrowed, ServoCssRulesStrong
 use style::gecko_bindings::bindings::{ThreadSafePrincipalHolder, ThreadSafeURIHolder};
 use style::gecko_bindings::bindings::{nsACString, nsAString};
 use style::gecko_bindings::bindings::Gecko_Utf8SliceToString;
+use style::gecko_bindings::bindings::RawGeckoElementBorrowed;
 use style::gecko_bindings::bindings::ServoComputedValuesBorrowedOrNull;
 use style::gecko_bindings::bindings::nsTArrayBorrowed_uintptr_t;
+use style::gecko_bindings::structs;
 use style::gecko_bindings::structs::{SheetParsingMode, nsIAtom};
-use style::gecko_bindings::structs::ServoElementSnapshot;
-use style::gecko_bindings::structs::nsRestyleHint;
+use style::gecko_bindings::structs::{nsRestyleHint, nsChangeHint};
 use style::gecko_bindings::structs::nsString;
 use style::gecko_bindings::sugar::ownership::{FFIArcHelpers, HasArcFFI, HasBoxFFI};
 use style::gecko_bindings::sugar::ownership::{HasSimpleFFI, Strong};
@@ -46,12 +53,14 @@ use style::parser::{ParserContext, ParserContextExtraData};
 use style::properties::{CascadeFlags, ComputedValues, Importance, PropertyDeclaration};
 use style::properties::{PropertyDeclarationParseResult, PropertyDeclarationBlock};
 use style::properties::{apply_declarations, parse_one_declaration};
+use style::restyle_hints::RestyleHint;
 use style::selector_parser::PseudoElementCascadeType;
 use style::sequential;
 use style::string_cache::Atom;
 use style::stylesheets::{CssRule, Origin, Stylesheet, StyleRule};
 use style::thread_state;
 use style::timer::Timer;
+use style::traversal::recalc_style_at;
 use style_traits::ToCss;
 
 /*
@@ -80,29 +89,26 @@ pub extern "C" fn Servo_Initialize() -> () {
 pub extern "C" fn Servo_Shutdown() -> () {
     // Destroy our default computed values.
     unsafe { ComputedValues::shutdown(); }
-}
 
-fn restyle_subtree(element: GeckoElement, raw_data: RawServoStyleSetBorrowed) {
-    // Force the creation of our lazily-constructed initial computed values on
-    // the main thread, since it's not safe to call elsewhere.
-    //
-    // FIXME(bholley): this should move into Servo_Initialize as soon as we get
-    // rid of the HackilyFindSomeDeviceContext stuff that happens during
-    // initial_values computation, since that stuff needs to be called further
-    // along in startup than the sensible place to call Servo_Initialize.
-    ComputedValues::initial_values();
+    // In general, LocalStyleContexts will get destroyed when the worker thread
+    // is joined and the TLS is dropped. However, under some configurations we
+    // may do sequential style computation on the main thread, so we need to be
+    // sure to clear the main thread TLS entry as well.
+    clear_local_context();
+}
 
+fn create_shared_context(mut per_doc_data: &mut AtomicRefMut<PerDocumentStyleDataImpl>) -> SharedStyleContext {
     // The stylist consumes stylesheets lazily.
-    let mut per_doc_data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
     per_doc_data.flush_stylesheets();
 
     let local_context_data =
         LocalStyleContextCreationInfo::new(per_doc_data.new_animations_sender.clone());
 
-    let shared_style_context = SharedStyleContext {
+    SharedStyleContext {
         // FIXME (bug 1303229): Use the actual viewport size here
         viewport_size: Size2D::new(Au(0), Au(0)),
         screen_size_changed: false,
+        skip_root: false,
         generation: 0,
         goal: ReflowGoal::ForScriptQuery,
         stylist: per_doc_data.stylist.clone(),
@@ -111,13 +117,37 @@ fn restyle_subtree(element: GeckoElement, raw_data: RawServoStyleSetBorrowed) {
         error_reporter: Box::new(StdoutErrorReporter),
         local_context_creation_data: Mutex::new(local_context_data),
         timer: Timer::new(),
-    };
+    }
+}
+
+fn traverse_subtree(element: GeckoElement, raw_data: RawServoStyleSetBorrowed,
+                    skip_root: bool) {
+    // Force the creation of our lazily-constructed initial computed values on
+    // the main thread, since it's not safe to call elsewhere.
+    //
+    // FIXME(bholley): this should move into Servo_Initialize as soon as we get
+    // rid of the HackilyFindSomeDeviceContext stuff that happens during
+    // initial_values computation, since that stuff needs to be called further
+    // along in startup than the sensible place to call Servo_Initialize.
+    ComputedValues::initial_values();
 
-    if element.styling_mode() == StylingMode::Stop {
-        error!("Unnecessary call to restyle_subtree");
+    // When new content is inserted in a display:none subtree, we will call into
+    // servo to try to style it. Detect that here and bail out.
+    if let Some(parent) = element.parent_element() {
+        if parent.get_data().is_none() || parent.is_display_none() {
+            debug!("{:?} has unstyled parent - ignoring call to traverse_subtree", parent);
+            return;
+        }
+    }
+
+    if !skip_root && element.styling_mode() == StylingMode::Stop {
+        error!("Unnecessary call to traverse_subtree");
         return;
     }
 
+    let mut per_doc_data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
+    let mut shared_style_context = create_shared_context(&mut per_doc_data);
+    shared_style_context.skip_root = skip_root;
     if per_doc_data.num_threads == 1 || per_doc_data.work_queue.is_none() {
         sequential::traverse_dom::<_, RecalcStyleOnly>(element.as_node(), &shared_style_context);
     } else {
@@ -127,12 +157,12 @@ fn restyle_subtree(element: GeckoElement, raw_data: RawServoStyleSetBorrowed) {
 }
 
 #[no_mangle]
-pub extern "C" fn Servo_RestyleSubtree(node: RawGeckoNodeBorrowed,
-                                       raw_data: RawServoStyleSetBorrowed) -> () {
-    let node = GeckoNode(node);
-    if let Some(element) = node.as_element() {
-        restyle_subtree(element, raw_data);
-    }
+pub extern "C" fn Servo_TraverseSubtree(root: RawGeckoElementBorrowed,
+                                        raw_data: RawServoStyleSetBorrowed,
+                                        skip_root: bindings::SkipRootBehavior) -> () {
+    let element = GeckoElement(root);
+    debug!("Servo_TraverseSubtree: {:?}", element);
+    traverse_subtree(element, raw_data, skip_root == bindings::SkipRootBehavior::Skip);
 }
 
 #[no_mangle]
@@ -167,10 +197,8 @@ pub extern "C" fn Servo_StyleWorkerThreadCount() -> u32 {
 }
 
 #[no_mangle]
-pub extern "C" fn Servo_Node_ClearNodeData(node: RawGeckoNodeBorrowed) -> () {
-    if let Some(element) = GeckoNode(node).as_element() {
-        element.clear_data();
-    }
+pub extern "C" fn Servo_Element_ClearData(element: RawGeckoElementBorrowed) -> () {
+    GeckoElement(element).clear_data();
 }
 
 #[no_mangle]
@@ -358,38 +386,6 @@ pub extern "C" fn Servo_StyleRule_GetSelectorText(rule: RawServoStyleRuleBorrowe
 }
 
 #[no_mangle]
-pub extern "C" fn Servo_ComputedValues_Get(node: RawGeckoNodeBorrowed)
-     -> ServoComputedValuesStrong {
-    let node = GeckoNode(node);
-
-    // Gecko erroneously calls this function from ServoRestyleManager::RecreateStyleContexts.
-    // We plan to fix that, but just support it for now until that code gets rewritten.
-    if node.is_text_node() {
-        error!("Don't call Servo_ComputedValue_Get() for text nodes");
-        let parent = node.parent_node().unwrap().as_element().unwrap();
-        let parent_cv = parent.borrow_data().map_or_else(|| Arc::new(ComputedValues::initial_values().clone()),
-                                                         |x| x.get_current_styles().unwrap()
-                                                              .primary.clone());
-        return ComputedValues::inherit_from(&parent_cv).into_strong();
-    }
-
-    let element = node.as_element().unwrap();
-    let data = element.borrow_data();
-    let arc_cv = match data.as_ref().and_then(|x| x.get_current_styles()) {
-        Some(styles) => styles.primary.clone(),
-        None => {
-            // FIXME(bholley): This case subverts the intended semantics of this
-            // function, and exists only to make stylo builds more robust corner-
-            // cases where Gecko wants the style for a node that Servo never
-            // traversed. We should remove this as soon as possible.
-            error!("stylo: encountered unstyled node, substituting default values.");
-            Arc::new(ComputedValues::initial_values().clone())
-        },
-    };
-    arc_cv.into_strong()
-}
-
-#[no_mangle]
 pub extern "C" fn Servo_ComputedValues_GetForAnonymousBox(parent_style_or_null: ServoComputedValuesBorrowedOrNull,
                                                          pseudo_tag: *mut nsIAtom,
                                                          raw_data: RawServoStyleSetBorrowed)
@@ -404,7 +400,7 @@ pub extern "C" fn Servo_ComputedValues_GetForAnonymousBox(parent_style_or_null:
 
     let maybe_parent = ComputedValues::arc_from_borrowed(&parent_style_or_null);
     let new_computed = data.stylist.precomputed_values_for_pseudo(&pseudo, maybe_parent, false)
-                           .map(|(computed, _rule_node)| computed);
+                           .map(|styles| styles.values);
     new_computed.map_or(Strong::null(), |c| c.into_strong())
 }
 
@@ -444,7 +440,7 @@ pub extern "C" fn Servo_ComputedValues_GetForPseudoElement(parent_style: ServoCo
             let parent = ComputedValues::as_arc(&parent_style);
             data.stylist
                 .lazily_compute_pseudo_element_style(&element, &pseudo, parent)
-                .map(|(c, _rule_node)| c)
+                .map(|styles| styles.values)
                 .map_or_else(parent_or_null, FFIArcHelpers::into_strong)
         }
         PseudoElementCascadeType::Precomputed => {
@@ -677,21 +673,170 @@ pub extern "C" fn Servo_CSSSupports(property: *const nsACString, value: *const n
     }
 }
 
+/// Only safe to call on the main thread, with exclusive access to the element and
+/// its ancestors.
+unsafe fn maybe_restyle<'a>(data: &'a mut AtomicRefMut<ElementData>, element: GeckoElement)
+    -> Option<&'a mut RestyleData>
+{
+    let r = data.restyle();
+    if r.is_some() {
+        // Propagate the bit up the chain.
+        let mut curr = element;
+        while let Some(parent) = curr.parent_element() {
+            curr = parent;
+            if curr.has_dirty_descendants() { break; }
+            curr.set_dirty_descendants();
+        }
+    }
+    r
+}
+
 #[no_mangle]
-pub extern "C" fn Servo_ComputeRestyleHint(element: RawGeckoElementBorrowed,
-                                           snapshot: *mut ServoElementSnapshot,
-                                           raw_data: RawServoStyleSetBorrowed) -> nsRestyleHint {
-    let per_doc_data = PerDocumentStyleData::from_ffi(raw_data).borrow();
-    let snapshot = unsafe { GeckoElementSnapshot::from_raw(snapshot) };
+pub extern "C" fn Servo_Element_GetSnapshot(element: RawGeckoElementBorrowed) -> *mut structs::ServoElementSnapshot
+{
     let element = GeckoElement(element);
+    let mut data = unsafe { element.ensure_data().borrow_mut() };
+    let snapshot = if let Some(restyle_data) = unsafe { maybe_restyle(&mut data, element) } {
+        if restyle_data.snapshot.is_none() {
+            restyle_data.snapshot = Some(element.create_snapshot());
+        }
+        restyle_data.snapshot.as_mut().unwrap().borrow_mut_raw()
+    } else {
+        ptr::null_mut()
+    };
+
+    debug!("Servo_Element_GetSnapshot: {:?}: {:?}", element, snapshot);
+    snapshot
+}
+
+#[no_mangle]
+pub extern "C" fn Servo_NoteExplicitHints(element: RawGeckoElementBorrowed,
+                                          restyle_hint: nsRestyleHint,
+                                          change_hint: nsChangeHint) {
+    let element = GeckoElement(element);
+    let damage = GeckoRestyleDamage::new(change_hint);
+    let mut data = unsafe { element.ensure_data().borrow_mut() };
+    debug!("Servo_NoteExplicitHints: {:?}, restyle_hint={:?}, change_hint={:?}",
+           element, restyle_hint, change_hint);
+
+    let restore_current_style = restyle_hint.0 == 0 && data.get_current_styles().is_some();
+
+    if let Some(restyle_data) = unsafe { maybe_restyle(&mut data, element) } {
+        let restyle_hint: RestyleHint = restyle_hint.into();
+        restyle_data.hint.insert(&restyle_hint.into());
+        restyle_data.damage |= damage;
+    } else {
+        debug!("(Element not styled, discarding hints)");
+    }
+
+    // If we had up-to-date style before and only posted a change hint,
+    // avoid invalidating that style.
+    //
+    // This allows for posting explicit change hints during restyle between
+    // the servo style traversal and the gecko post-traversal (i.e. during the
+    // call to CreateNeedeFrames in ServoRestyleManager::ProcessPendingRestyles).
+    //
+    // FIXME(bholley): The is a very inefficient and hacky way of doing this,
+    // we should fix the ElementData restyle() API to be more granular so that it
+    // does the right thing automatically.
+    if restore_current_style {
+        let styles = data.previous_styles().unwrap().clone();
+        data.finish_styling(styles, GeckoRestyleDamage::empty());
+    }
+}
+
+#[no_mangle]
+pub extern "C" fn Servo_CheckChangeHint(element: RawGeckoElementBorrowed) -> nsChangeHint
+{
+    let element = GeckoElement(element);
+    if element.get_data().is_none() {
+        error!("Trying to get change hint from unstyled element");
+        return nsChangeHint(0);
+    }
+
+    let mut data = element.get_data().unwrap().borrow_mut();
+    let damage = data.damage_sloppy();
+
+    // If there's no change hint, the caller won't consume the new style. Do that
+    // ourselves.
+    //
+    // FIXME(bholley): Once we start storing style data on frames, we'll want to
+    // drop the data here instead.
+    if damage.is_empty() {
+        data.persist();
+    }
+
+    debug!("Servo_GetChangeHint: {:?}, damage={:?}", element, damage);
+    damage.as_change_hint()
+}
+
+#[no_mangle]
+pub extern "C" fn Servo_ResolveStyle(element: RawGeckoElementBorrowed,
+                                     raw_data: RawServoStyleSetBorrowed,
+                                     consume: bindings::ConsumeStyleBehavior,
+                                     compute: bindings::LazyComputeBehavior) -> ServoComputedValuesStrong
+{
+    let element = GeckoElement(element);
+    debug!("Servo_ResolveStyle: {:?}, consume={:?}, compute={:?}", element, consume, compute);
+
+    if compute == bindings::LazyComputeBehavior::Allow {
+        let should_compute = unsafe { element.ensure_data() }.borrow().get_current_styles().is_none();
+        if should_compute {
+            debug!("Performing manual style computation");
+            if let Some(parent) = element.parent_element() {
+                if parent.borrow_data().map_or(true, |d| d.get_current_styles().is_none()) {
+                    error!("Attempting manual style computation with unstyled parent");
+                    return Arc::new(ComputedValues::initial_values().clone()).into_strong();
+                }
+            }
+
+            let mut per_doc_data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
+            let shared_style_context = create_shared_context(&mut per_doc_data);
+            let context = StandaloneStyleContext::new(&shared_style_context);
+            recalc_style_at::<_, _, RecalcStyleOnly>(&context, element.as_node().opaque(), element);
+
+            // The element was either unstyled or needed restyle. If it was unstyled, it may have
+            // additional unstyled children that subsequent traversals won't find now that the style
+            // on this element is up-to-date. Mark dirty descendants in that case.
+            if element.first_child_element().is_some() {
+                unsafe { element.set_dirty_descendants() };
+            }
+        }
+    }
+
+    let data = element.mutate_data();
+    let values = match data.as_ref().and_then(|d| d.get_current_styles()) {
+        Some(x) => x.primary.values.clone(),
+        None => {
+            error!("Resolving style on unstyled element with lazy computation forbidden.");
+            return Arc::new(ComputedValues::initial_values().clone()).into_strong();
+        }
+    };
 
-    // NB: This involves an FFI call, we can get rid of it easily if needed.
-    let current_state = element.get_state();
+    if consume == bindings::ConsumeStyleBehavior::Consume {
+        // FIXME(bholley): Once we start storing style data on frames, we'll want to
+        // drop the data here instead.
+        data.unwrap().persist();
+    }
+
+    values.into_strong()
+}
 
-    let hint = per_doc_data.stylist
-                           .compute_restyle_hint(&element, &snapshot,
-                                                 current_state);
+#[no_mangle]
+pub extern "C" fn Servo_AssertTreeIsClean(root: RawGeckoElementBorrowed) {
+    if !cfg!(debug_assertions) {
+        panic!("Calling Servo_AssertTreeIsClean in release build");
+    }
+
+    let root = GeckoElement(root);
+    fn assert_subtree_is_clean<'le>(el: GeckoElement<'le>) {
+        debug_assert!(!el.has_dirty_descendants());
+        for child in el.as_node().children() {
+            if let Some(child) = child.as_element() {
+                assert_subtree_is_clean(child);
+            }
+        }
+    }
 
-    // NB: Binary representations match.
-    unsafe { transmute(hint.bits() as u32) }
+    assert_subtree_is_clean(root);
 }
diff --git a/ports/geckolib/lib.rs b/ports/geckolib/lib.rs
index a09fc47f782..0087e6aece6 100644
--- a/ports/geckolib/lib.rs
+++ b/ports/geckolib/lib.rs
@@ -12,6 +12,7 @@ extern crate euclid;
 extern crate libc;
 #[macro_use] extern crate log;
 extern crate parking_lot;
+extern crate selectors;
 extern crate servo_url;
 extern crate style_traits;
 
diff --git a/tests/unit/stylo/lib.rs b/tests/unit/stylo/lib.rs
index 497d1366cb9..d28f0663d0e 100644
--- a/tests/unit/stylo/lib.rs
+++ b/tests/unit/stylo/lib.rs
@@ -7,9 +7,9 @@ extern crate cssparser;
 extern crate env_logger;
 extern crate euclid;
 extern crate geckoservo;
-extern crate libc;
 #[macro_use] extern crate log;
 extern crate parking_lot;
+extern crate selectors;
 extern crate servo_url;
 extern crate style;
 extern crate style_traits;
diff --git a/tests/wpt/metadata-css/css-transitions-1_dev/html/pseudo-elements-001.htm.ini b/tests/wpt/metadata-css/css-transitions-1_dev/html/pseudo-elements-001.htm.ini
index 895b227441a..38e495fedd6 100644
--- a/tests/wpt/metadata-css/css-transitions-1_dev/html/pseudo-elements-001.htm.ini
+++ b/tests/wpt/metadata-css/css-transitions-1_dev/html/pseudo-elements-001.htm.ini
@@ -1,8 +1,3 @@
 [pseudo-elements-001.htm]
   type: testharness
-  [transition padding-left on :before / values]
-    expected: FAIL
-
-  [transition padding-left on :after / values]
-    expected: FAIL
-
+  disabled: https://github.com/servo/servo/issues/13593
diff --git a/tests/wpt/metadata-css/css21_dev/html4/pseudo-elements-001.htm.ini b/tests/wpt/metadata-css/css21_dev/html4/pseudo-elements-001.htm.ini
index 895b227441a..38e495fedd6 100644
--- a/tests/wpt/metadata-css/css21_dev/html4/pseudo-elements-001.htm.ini
+++ b/tests/wpt/metadata-css/css21_dev/html4/pseudo-elements-001.htm.ini
@@ -1,8 +1,3 @@
 [pseudo-elements-001.htm]
   type: testharness
-  [transition padding-left on :before / values]
-    expected: FAIL
-
-  [transition padding-left on :after / values]
-    expected: FAIL
-
+  disabled: https://github.com/servo/servo/issues/13593