servo: Merge #14300 - stylo: Basic infrastructure for RestyleHint-driven traversal (from bholley:restyle_driven_traversal); r=emilio
authorBobby Holley <bobbyholley@gmail.com>
Fri, 25 Nov 2016 09:00:44 -0800
changeset 478393 487970795136c909e1ed305d1b7f43fd054e686d
parent 478392 454e13d6e77108399c0b73290c2c08ee75793bcd
child 478394 2ebae01813c42a19e49dda59395b14807076fc50
push id44079
push userbmo:gps@mozilla.com
push dateSat, 04 Feb 2017 00:14:49 +0000
reviewersemilio
servo: Merge #14300 - stylo: Basic infrastructure for RestyleHint-driven traversal (from bholley:restyle_driven_traversal); r=emilio 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) Source-Repo: https://github.com/servo/servo Source-Revision: d98abaec20e624aa89a3abddf4cf2a6399951ef1
servo/components/layout/construct.rs
servo/components/layout/query.rs
servo/components/layout/traversal.rs
servo/components/layout/wrapper.rs
servo/components/layout_thread/lib.rs
servo/components/script/dom/document.rs
servo/components/script/dom/node.rs
servo/components/script/layout_wrapper.rs
servo/components/script_layout_interface/lib.rs
servo/components/script_layout_interface/message.rs
servo/components/script_layout_interface/wrapper_traits.rs
servo/components/style/atomic_refcell.rs
servo/components/style/binding_tools/regen.py
servo/components/style/binding_tools/setup_bindgen.sh
servo/components/style/context.rs
servo/components/style/data.rs
servo/components/style/dom.rs
servo/components/style/gecko/context.rs
servo/components/style/gecko/restyle_damage.rs
servo/components/style/gecko/snapshot.rs
servo/components/style/gecko/traversal.rs
servo/components/style/gecko/wrapper.rs
servo/components/style/gecko_bindings/bindings.rs
servo/components/style/gecko_bindings/structs_debug.rs
servo/components/style/gecko_bindings/structs_release.rs
servo/components/style/gecko_bindings/sugar/ownership.rs
servo/components/style/matching.rs
servo/components/style/parallel.rs
servo/components/style/restyle_hints.rs
servo/components/style/sequential.rs
servo/components/style/stylist.rs
servo/components/style/traversal.rs
servo/ports/geckolib/glue.rs
servo/ports/geckolib/lib.rs
servo/tests/unit/stylo/lib.rs
--- a/servo/components/layout/construct.rs
+++ b/servo/components/layout/construct.rs
@@ -1349,18 +1349,18 @@ impl<'a, ConcreteThreadSafeLayoutNode: T
 
         if node.can_be_fragmented() || node.style(self.style_context()).is_multicol() {
             return false
         }
 
         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,
                 ConstructionResult::Flow(ref mut flow, _) => {
                     // The node's flow is of the same type and has the same set of children and can
                     // therefore be repaired by simply propagating damage and style to the flow.
                     if !flow.is_block_flow() {
                         return false
--- a/servo/components/layout/query.rs
+++ b/servo/components/layout/query.rs
@@ -24,16 +24,17 @@ use script_traits::LayoutMsg as Constell
 use script_traits::UntrustedNodeAddress;
 use sequential;
 use servo_atoms::Atom;
 use std::cmp::{min, max};
 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;
 use style::selector_parser::PseudoElement;
 use style::stylist::Stylist;
 use style_traits::ToCss;
 use style_traits::cursor::Cursor;
 use wrapper::{LayoutNodeHelpers, LayoutNodeLayoutData};
@@ -602,48 +603,44 @@ pub fn process_node_scroll_area_request<
             let top = min(iterator.union_rect.origin.y, iterator.origin_rect.origin.y);
             let right = max(iterator.union_rect.size.width, iterator.origin_rect.size.width);
             Rect::new(Point2D::new(iterator.origin_rect.origin.x, top),
                       Size2D::new(right, iterator.origin_rect.size.height))
         }
     }
 }
 
-/// 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,
                                                 style_context: &'a C,
                                                 pseudo: &Option<PseudoElement>,
                                                 property: &Atom,
                                                 layout_root: &mut Flow) -> Option<String>
     where N: LayoutNode,
           C: StyleContext<'a>
 {
-    use style::traversal::ensure_element_styled;
+    use style::traversal::{clear_descendant_data, style_element_in_display_none_subtree};
+    let element = requested_node.as_element().unwrap();
 
-    // 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);
+    // 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 {
         Some(PseudoElement::Before) => layout_el.get_before_pseudo(),
         Some(PseudoElement::After) => layout_el.get_after_pseudo(),
         Some(PseudoElement::DetailsSummary) |
         Some(PseudoElement::DetailsContent) |
         Some(PseudoElement::Selection) => None,
@@ -657,16 +654,20 @@ pub fn process_resolved_style_request<'a
             // https://www.w3.org/Bugs/Public/show_bug.cgi?id=29006
             return None;
         }
         Some(layout_el) => layout_el
     };
 
     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 |*/
         position::computed_value::T::fixed |
         position::computed_value::T::absolute => true,
         _ => false
     };
 
--- a/servo/components/layout/traversal.rs
+++ b/servo/components/layout/traversal.rs
@@ -107,33 +107,28 @@ impl<'lc, N> DomTraversalContext<N> for 
             recalc_style_at::<_, _, Self>(&self.context, self.root, el);
         }
     }
 
     fn process_postorder(&self, node: N) {
         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 ||
                         el.as_node().to_threadsafe().restyle_damage() != RestyleDamage::empty(),
 
             // Text nodes never need styling. However, there are two cases they may need
             // flow construction:
             // (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(),
         }
     }
 
     unsafe fn ensure_element_data(element: &N::ConcreteElement) -> &AtomicRefCell<ElementData> {
         element.as_node().initialize_data();
         element.get_data().unwrap()
     }
 
@@ -151,37 +146,41 @@ pub trait PostorderNodeMutTraversal<Conc
     /// The operation to perform. Return true to continue or false to stop.
     fn process(&mut self, node: &ConcreteThreadSafeLayoutNode);
 }
 
 /// The flow construction traversal, which builds flows for styled nodes.
 #[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();
 
         // Always reconstruct if incremental layout is turned off.
         let nonincremental_layout = opts::get().nonincremental_layout;
         if nonincremental_layout || tnode.restyle_damage() != RestyleDamage::empty() ||
            node.as_element().map_or(false, |el| el.has_dirty_descendants()) {
             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();
     }
 
-    unsafe { node.clear_dirty_bits(); }
+    if let Some(el) = node.as_element() {
+        el.mutate_data().unwrap().persist();
+        unsafe { el.unset_dirty_descendants(); }
+    }
+
     remove_from_bloom_filter(context, root, node);
 }
 
 /// The bubble-inline-sizes traversal, the first part of layout computation. This computes
 /// preferred and intrinsic inline-sizes and bubbles them up the tree.
 pub struct BubbleISizes<'a> {
     pub layout_context: &'a LayoutContext<'a>,
 }
--- a/servo/components/layout/wrapper.rs
+++ b/servo/components/layout/wrapper.rs
@@ -32,18 +32,16 @@
 
 use core::nonzero::NonZero;
 use data::{LayoutDataFlags, PersistentLayoutData};
 use script_layout_interface::{OpaqueStyleAndLayoutData, PartialPersistentLayoutData};
 use script_layout_interface::wrapper_traits::{LayoutNode, ThreadSafeLayoutElement, ThreadSafeLayoutNode};
 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>;
 
 pub unsafe fn drop_style_and_layout_data(data: OpaqueStyleAndLayoutData) {
     let ptr: *mut AtomicRefCell<PartialPersistentLayoutData> = *data.ptr;
     let non_opaque: *mut NonOpaqueStyleAndLayoutData = ptr as *mut _;
     let _ = Box::from_raw(non_opaque);
 }
@@ -92,19 +90,16 @@ impl<T: LayoutNode> LayoutNodeHelpers fo
     fn initialize_data(&self) {
         if self.get_raw_data().is_none() {
             let ptr: *mut NonOpaqueStyleAndLayoutData =
                 Box::into_raw(box AtomicRefCell::new(PersistentLayoutData::new()));
             let opaque = OpaqueStyleAndLayoutData {
                 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());
-            }
         };
     }
 
     fn clear_data(&self) {
         if self.get_raw_data().is_some() {
             unsafe { drop_style_and_layout_data(self.take_style_and_layout_data()) };
         }
     }
--- a/servo/components/layout_thread/lib.rs
+++ b/servo/components/layout_thread/lib.rs
@@ -81,17 +81,17 @@ use layout::wrapper::drop_style_and_layo
 use layout_traits::LayoutThreadFactory;
 use msg::constellation_msg::{FrameId, PipelineId};
 use net_traits::image_cache_thread::{ImageCacheChan, ImageCacheResult, ImageCacheThread};
 use net_traits::image_cache_thread::UsePlaceholder;
 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};
 use script_layout_interface::wrapper_traits::LayoutNode;
 use script_traits::{ConstellationControlMsg, LayoutControlMsg, LayoutMsg as ConstellationMsg};
 use script_traits::{StackingContextScrollState, UntrustedNodeAddress};
 use selectors::Element;
 use servo_url::ServoUrl;
@@ -100,17 +100,18 @@ use std::collections::HashMap;
 use std::hash::BuildHasherDefault;
 use std::ops::{Deref, DerefMut};
 use std::process;
 use std::sync::{Arc, Mutex, MutexGuard};
 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};
 use style::parser::ParserContextExtraData;
 use style::servo::restyle_damage::{REFLOW, REFLOW_OUT_OF_FLOW, REPAINT, REPOSITION, STORE_OVERFLOW};
 use style::stylesheets::{Origin, Stylesheet, UserAgentStylesheets};
 use style::stylist::Stylist;
 use style::thread_state;
@@ -975,21 +976,19 @@ impl LayoutThread {
         let document = document.as_document().unwrap();
 
         // FIXME(pcwalton): Combine `ReflowGoal` and `ReflowQueryType`. Then remove this assert.
         debug_assert!((data.reflow_info.goal == ReflowGoal::ForDisplay &&
                        data.query_type == ReflowQueryType::NoQuery) ||
                       (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");
                 match data.query_type {
                     ReflowQueryType::ContentBoxQuery(_) => {
                         rw_data.content_box_response = Rect::zero();
                     },
                     ReflowQueryType::ContentBoxesQuery(_) => {
@@ -1015,22 +1014,23 @@ impl LayoutThread {
                     },
                     ReflowQueryType::MarginStyleQuery(_) => {
                         rw_data.margin_style_response = MarginStyleResponse::empty();
                     },
                     ReflowQueryType::NoQuery => {}
                 }
                 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;
         let old_viewport_size = self.viewport_size;
         let current_screen_size = Size2D::new(Au::from_f32_px(initial_viewport.width),
                                               Au::from_f32_px(initial_viewport.height));
 
         // Calculate the actual viewport as per DEVICE-ADAPT § 6
@@ -1056,112 +1056,101 @@ impl LayoutThread {
         if viewport_size_changed {
             if let Some(constraints) = constraints {
                 // let the constellation know about the viewport constraints
                 rw_data.constellation_chan
                        .send(ConstellationMsg::ViewportConstrained(self.id, constraints))
                        .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() };
                         }
 
                         next = iter.next_skipping_children();
                     } else {
                         next = iter.next();
                     }
                 }
             }
         }
 
         // If the entire flow tree is invalid, then it will be reflowed anyhow.
         needs_dirtying |= Arc::get_mut(&mut rw_data.stylist).unwrap().update(&data.document_stylesheets,
                                                                              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
                 // the restyle calculation so that we can also do it for new
                 // unstyled nodes, which the descendants bit helps us find.
                 if let Some(parent) = el.parent_element() {
                     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;
+                // 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,
+                };
 
-                // 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;
-                }
+                // 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);
             }
         }
 
         // Create a layout context for use throughout the following passes.
         let mut shared_layout_context = self.build_shared_layout_context(&*rw_data,
                                                                          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(),
                     self.time_profiler_chan.clone(),
                     || {
                 // Perform CSS selector matching and flow construction.
                 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);
                     }
                 }
             });
 
             // TODO(pcwalton): Measure energy usage of text shaping, perhaps?
             let text_shaping_time =
                 (font::get_and_reset_text_shaping_performance_counter() as u64) /
                 (self.layout_threads as u64);
@@ -1169,21 +1158,21 @@ impl LayoutThread {
                                     self.profiler_metadata(),
                                     self.time_profiler_chan.clone(),
                                     0,
                                     text_shaping_time,
                                     0,
                                     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 {
             shared_layout_context.style_context.stylist.rule_tree.dump_stdout();
         }
 
         // GC the rule tree if some heuristics are met.
         unsafe { shared_layout_context.style_context.stylist.rule_tree.maybe_gc(); }
--- a/servo/components/script/dom/document.rs
+++ b/servo/components/script/dom/document.rs
@@ -429,17 +429,16 @@ impl Document {
     }
 
     pub fn needs_reflow(&self) -> bool {
         // FIXME: This should check the dirty bit on the document,
         // not the document element. Needs some layout changes to make
         // 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()
             }
             None => false,
         }
     }
 
--- a/servo/components/script/dom/node.rs
+++ b/servo/components/script/dom/node.rs
@@ -144,19 +144,16 @@ pub struct Node {
 
 bitflags! {
     #[doc = "Flags for node items."]
     #[derive(JSTraceable, HeapSizeOf)]
     pub flags NodeFlags: u8 {
         #[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
         // Perhaps using a Set in Document?
         #[doc = "Specifies whether or not there is an authentic click in progress on \
                  this element."]
         const CLICK_IN_PROGRESS = 0x10,
         #[doc = "Specifies whether this node is focusable and whether it is supposed \
@@ -167,17 +164,17 @@ bitflags! {
         const CAN_BE_FRAGMENTED = 0x40,
         #[doc = "Specifies whether this node needs to be dirted when viewport size changed."]
         const DIRTY_ON_VIEWPORT_SIZE_CHANGE = 0x80
     }
 }
 
 impl NodeFlags {
     pub fn new() -> NodeFlags {
-        IS_DIRTY
+        NodeFlags::empty()
     }
 }
 
 impl Drop for Node {
     #[allow(unsafe_code)]
     fn drop(&mut self) {
         self.style_and_layout_data.get().map(|d| self.dispose(d));
     }
@@ -423,24 +420,16 @@ impl Node {
             flags.insert(flag);
         } else {
             flags.remove(flag);
         }
 
         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)
     }
 
     pub fn set_has_dirty_descendants(&self, state: bool) {
         self.set_flag(HAS_DIRTY_DESCENDANTS, state)
     }
 
--- a/servo/components/script/layout_wrapper.rs
+++ b/servo/components/script/layout_wrapper.rs
@@ -31,38 +31,39 @@
 #![allow(unsafe_code)]
 
 use dom::bindings::inheritance::{CharacterDataTypeId, ElementTypeId};
 use dom::bindings::inheritance::{HTMLElementTypeId, NodeTypeId};
 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;
 use html5ever_atoms::{LocalName, Namespace};
 use msg::constellation_msg::PipelineId;
 use parking_lot::RwLock;
 use range::Range;
 use script_layout_interface::{HTMLCanvasData, LayoutNodeType, SVGSVGData, TrustedNodeAddress};
 use script_layout_interface::{OpaqueStyleAndLayoutData, PartialPersistentLayoutData};
 use script_layout_interface::wrapper_traits::{DangerousThreadSafeLayoutNode, GetLayoutData, LayoutNode};
 use script_layout_interface::wrapper_traits::{PseudoElementType, ThreadSafeLayoutElement, ThreadSafeLayoutNode};
 use selectors::matching::ElementFlags;
 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;
 use style::data::ElementData;
 use style::dom::{LayoutIterator, NodeInfo, OpaqueNode, PresentationalHintsSynthetizer, TElement, TNode};
 use style::dom::UnsafeNode;
 use style::element_state::*;
 use style::properties::{ComputedValues, PropertyDeclarationBlock};
@@ -75,16 +76,26 @@ use style::stylist::ApplicableDeclaratio
 pub struct ServoLayoutNode<'a> {
     /// The wrapped node.
     node: LayoutJS<Node>,
 
     /// Being chained to a PhantomData prevents `LayoutNode`s from escaping.
     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 {
         self.node == other.node
     }
 }
 
 impl<'ln> ServoLayoutNode<'ln> {
@@ -196,40 +207,16 @@ impl<'ln> TNode for ServoLayoutNode<'ln>
         self.node.set_flag(CAN_BE_FRAGMENTED, value)
     }
 
     fn parent_node(&self) -> Option<ServoLayoutNode<'ln>> {
         unsafe {
             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> {
     current: Option<ServoLayoutNode<'a>>,
 }
 
 impl<'a> Iterator for ServoChildrenIterator<'a> {
     type Item = ServoLayoutNode<'a>;
@@ -254,19 +241,38 @@ impl<'ln> LayoutNode for ServoLayoutNode
     unsafe fn init_style_and_layout_data(&self, data: OpaqueStyleAndLayoutData) {
         self.get_jsmanaged().init_style_and_layout_data(data);
     }
 
     unsafe fn take_style_and_layout_data(&self) -> OpaqueStyleAndLayoutData {
         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))
+        }
     }
 }
 
 impl<'ln> GetLayoutData for ServoLayoutNode<'ln> {
     fn get_style_and_layout_data(&self) -> Option<OpaqueStyleAndLayoutData> {
         unsafe {
             self.get_jsmanaged().get_style_and_layout_data()
         }
@@ -287,24 +293,16 @@ impl<'ln> GetLayoutData for ServoThreadS
 
 impl<'le> GetLayoutData for ServoThreadSafeLayoutElement<'le> {
     fn get_style_and_layout_data(&self) -> Option<OpaqueStyleAndLayoutData> {
         self.element.as_node().get_style_and_layout_data()
     }
 }
 
 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 {
             s.push_str("  ");
         }
 
         s.push_str(&self.debug_str());
         println!("{}", s);
@@ -325,19 +323,18 @@ impl<'ln> ServoLayoutNode<'ln> {
         }
 
         for kid in self.children() {
             kid.dump_style_indent(indent + 1);
         }
     }
 
     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()))
     }
 
     fn debug_style_str(self) -> String {
         let maybe_element = self.as_element();
         let maybe_data = match maybe_element {
             Some(ref el) => el.borrow_data(),
             None => None,
@@ -401,17 +398,17 @@ pub struct ServoLayoutElement<'le> {
 }
 
 impl<'le> fmt::Debug for ServoLayoutElement<'le> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "<{}", self.element.local_name()));
         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)
     }
 }
 
 impl<'le> PresentationalHintsSynthetizer for ServoLayoutElement<'le> {
     fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, hints: &mut V)
         where V: Push<ApplicableDeclarationBlock>
     {
         unsafe {
@@ -442,56 +439,48 @@ impl<'le> TElement for ServoLayoutElemen
         self.get_attr(namespace, attr).is_some()
     }
 
     #[inline]
     fn attr_equals(&self, namespace: &Namespace, attr: &LocalName, val: &Atom) -> bool {
         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>>,
                                              _pseudo_element: Option<&PseudoElement>)
                                              -> Option<&'a Arc<ComputedValues>> {
         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) }
     }
 
     unsafe fn set_dirty_descendants(&self) {
         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);
     }
 
     fn did_process_child(&self) -> isize {
         let data = self.get_partial_layout_data().unwrap().borrow();
         let old_value = data.parallel.children_to_process.fetch_sub(1, Ordering::Relaxed);
         debug_assert!(old_value >= 1);
         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| {
                 let ppld: &AtomicRefCell<PartialPersistentLayoutData> = &**d.ptr;
                 let psd: &AtomicRefCell<ElementData> = transmute(ppld);
                 psd
             })
         }
@@ -724,17 +713,17 @@ impl<'le> ::selectors::Element for Servo
         }
     }
 
     fn insert_flags(&self, flags: ElementFlags) {
         self.element.insert_atomic_flags(flags);
     }
 }
 
-#[derive(Copy, Clone)]
+#[derive(Copy, Clone, Debug)]
 pub struct ServoThreadSafeLayoutNode<'ln> {
     /// The wrapped node.
     node: ServoLayoutNode<'ln>,
 
     /// The pseudo-element type, with (optionally)
     /// a specified display value to override the stylesheet.
     pseudo: PseudoElementType<Option<display::T>>,
 }
@@ -825,17 +814,17 @@ impl<'ln> ThreadSafeLayoutNode for Servo
         // properties like vertical-align on fragments have values that
         // match the parent element). This is an implementation detail of
         // Servo layout that is not central to how fragment construction
         // works, but would be difficult to change. (Text node style is
         // also not visible to script.)
         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 {
         self.node.debug_id()
     }
 
     fn children(&self) -> LayoutIterator<Self::ChildrenIterator> {
         LayoutIterator(ThreadSafeLayoutNodeChildrenIterator::new(*self))
@@ -869,32 +858,24 @@ impl<'ln> ThreadSafeLayoutNode for Servo
             //
             // If you implement other values for this property, you will almost certainly
             // want to update this check.
             !self.style(context).get_inheritedtext().white_space.preserve_newlines()
         }
     }
 
     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 {
         self.node.can_be_fragmented()
     }
 
     fn node_text_content(&self) -> String {
         let this = unsafe { self.get_jsmanaged() };
--- a/servo/components/script_layout_interface/lib.rs
+++ b/servo/components/script_layout_interface/lib.rs
@@ -46,41 +46,32 @@ pub mod wrapper_traits;
 
 use canvas_traits::CanvasMsg;
 use core::nonzero::NonZero;
 use ipc_channel::ipc::IpcSender;
 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
     /// style system is being used standalone, this is all that hangs
     /// off the node. This must be first to permit the various
     /// 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,
 }
 
 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(),
         }
     }
 }
 
 #[derive(Copy, Clone, HeapSizeOf)]
 pub struct OpaqueStyleAndLayoutData {
     #[ignore_heap_size_of = "TODO(#6910) Box value that should be counted but \
@@ -137,17 +128,17 @@ pub struct HTMLCanvasData {
 }
 
 pub struct SVGSVGData {
     pub width: u32,
     pub height: u32,
 }
 
 /// 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)]
 unsafe impl Send for TrustedNodeAddress {}
 
 pub fn is_image_data(uri: &str) -> bool {
     static TYPES: &'static [&'static str] = &["data:image/png", "data:image/gif", "data:image/jpeg"];
     TYPES.iter().any(|&type_| uri.starts_with(type_))
--- a/servo/components/script_layout_interface/message.rs
+++ b/servo/components/script_layout_interface/message.rs
@@ -82,17 +82,17 @@ pub enum Msg {
     SetFinalUrl(ServoUrl),
 
     /// Tells layout about the new scrolling offsets of each scrollable stacking context.
     SetStackingContextScrollStates(Vec<StackingContextScrollState>),
 }
 
 
 /// Any query to perform with this reflow.
-#[derive(PartialEq)]
+#[derive(Debug, PartialEq)]
 pub enum ReflowQueryType {
     NoQuery,
     ContentBoxQuery(TrustedNodeAddress),
     ContentBoxesQuery(TrustedNodeAddress),
     NodeOverflowQuery(TrustedNodeAddress),
     HitTestQuery(Point2D<f32>, Point2D<f32>, bool),
     NodeGeometryQuery(TrustedNodeAddress),
     NodeScrollGeometryQuery(TrustedNodeAddress),
--- a/servo/components/script_layout_interface/wrapper_traits.rs
+++ b/servo/components/script_layout_interface/wrapper_traits.rs
@@ -71,54 +71,60 @@ impl<T> PseudoElementType<T> {
 
 /// Trait to abstract access to layout data across various data structures.
 pub trait GetLayoutData {
     fn get_style_and_layout_data(&self) -> Option<OpaqueStyleAndLayoutData>;
 }
 
 /// 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;
 
     /// Returns the type ID of this node.
     fn type_id(&self) -> LayoutNodeType;
 
     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(),
         })
     }
 
     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;
         self.current = node.and_then(|node| node.prev_sibling());
         node
     }
 }
 
-pub struct TreeIterator<ConcreteNode> where ConcreteNode: TNode {
+pub struct TreeIterator<ConcreteNode> where ConcreteNode: LayoutNode {
     stack: Vec<ConcreteNode>,
 }
 
 impl<ConcreteNode> TreeIterator<ConcreteNode> where ConcreteNode: LayoutNode {
     fn new(root: ConcreteNode) -> TreeIterator<ConcreteNode> {
         let mut stack = vec![];
         stack.push(root);
         TreeIterator {
@@ -139,17 +145,17 @@ impl<ConcreteNode> Iterator for TreeIter
         ret.map(|node| self.stack.extend(node.rev_children()));
         ret
     }
 }
 
 
 /// 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>;
     type ChildrenIterator: Iterator<Item = Self> + Sized;
 
     /// Converts self into an `OpaqueNode`.
     fn opaque(&self) -> OpaqueNode;
 
@@ -228,18 +234,16 @@ pub trait ThreadSafeLayoutNode: Clone + 
             self.style_for_text_node()
         }
     }
 
     fn is_ignorable_whitespace(&self, context: &SharedStyleContext) -> bool;
 
     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 {
         self.type_id().is_some()
     }
 
     fn can_be_fragmented(&self) -> bool;
 
@@ -348,84 +352,84 @@ pub trait ThreadSafeLayoutElement: Clone
     /// Returns the style results for the given node. If CSS selector matching
     /// has not yet been performed, fails.
     ///
     /// Unlike the version on TNode, this handles pseudo-elements.
     #[inline]
     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.
                 let style_pseudo = other.style_pseudo_element();
                 match style_pseudo.cascade_type() {
                     // Already computed during the cascade.
                     PseudoElementCascadeType::Eager => {},
                     PseudoElementCascadeType::Precomputed => {
                         if !self.get_style_data()
                                 .unwrap()
                                 .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 => {
                         if !self.get_style_data()
                                 .unwrap()
                                 .borrow()
                                 .current_styles().pseudos.contains_key(&style_pseudo) {
                             let mut data = self.get_style_data().unwrap().borrow_mut();
                             let new_style =
                                 context.stylist
                                        .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());
                         }
                     }
                 }
 
                 self.get_style_data().unwrap().borrow()
                     .current_styles().pseudos.get(&style_pseudo)
-                    .unwrap().0.clone()
+                    .unwrap().values.clone()
             }
         }
     }
 
     #[inline]
     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.
     ///
     /// This differs from `style(ctx)` in that if the pseudo-element has not yet
     /// been computed it would panic.
     ///
     /// This should be used just for querying layout, or when we know the
     /// element style is precomputed, not from general layout itself.
     #[inline]
     fn resolved_style(&self) -> Arc<ServoComputedValues> {
         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(),
         }
     }
 }
--- a/servo/components/style/atomic_refcell.rs
+++ b/servo/components/style/atomic_refcell.rs
@@ -1,16 +1,18 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #![allow(unsafe_code)]
 
 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
 /// threads.
 ///
 /// RwLock is traditionally considered to be the |Sync| analogue of RefCell.
 /// However, for consumers that can guarantee that they will never mutably
 /// borrow the contents concurrently with immutable borrows, an RwLock feels
@@ -45,16 +47,28 @@ impl<'a, T> Deref for AtomicRefMut<'a, T
 }
 
 impl<'a, T> DerefMut for AtomicRefMut<'a, T> {
     fn deref_mut(&mut self) -> &mut T {
         self.0.deref_mut()
     }
 }
 
+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))
     }
     pub fn borrow(&self) -> AtomicRef<T> {
         AtomicRef(self.0.try_read().expect("already mutably borrowed"))
     }
     pub fn borrow_mut(&self) -> AtomicRefMut<T> {
--- a/servo/components/style/binding_tools/regen.py
+++ b/servo/components/style/binding_tools/regen.py
@@ -246,26 +246,30 @@ COMPILATION_TARGETS = {
             "type nsAString_internal = nsAString;"
         ],
         "flags": [
             "--ignore-methods",
         ],
         "match_headers": [
             "ServoBindingList.h",
             "ServoBindings.h",
+            "ServoTypes.h",
             "nsStyleStructList.h",
         ],
         "files": [
             "{}/dist/include/mozilla/ServoBindings.h",
         ],
         "whitelist": [
             "RawGeckoDocument",
             "RawGeckoElement",
             "RawGeckoNode",
             "ThreadSafe.*Holder",
+            "ConsumeStyleBehavior",
+            "LazyComputeBehavior",
+            "SkipRootBehavior",
         ],
 
         # Types to just use from the `structs` target.
         "structs_types": [
             "Element",
             "FontFamilyList",
             "FontFamilyType",
             "ServoElementSnapshot",
@@ -334,18 +338,26 @@ COMPILATION_TARGETS = {
         "servo_nullable_arc_types": [
             "ServoComputedValues",
             "ServoCssRules",
             "RawServoStyleSheet",
             "RawServoDeclarationBlock",
             "RawServoStyleRule",
         ],
         "servo_owned_types": [
-            "RawServoStyleSet",
-            "StyleChildrenIterator",
+            {
+                "name": "RawServoStyleSet",
+                "opaque": True,
+            }, {
+                "name": "StyleChildrenIterator",
+                "opaque": True,
+            }, {
+                "name": "ServoElementSnapshot",
+                "opaque": False,
+            },
         ],
         "servo_immutable_borrow_types": [
             "RawGeckoNode",
             "RawGeckoElement",
             "RawGeckoDocument",
             "RawServoDeclarationBlockStrong",
         ],
         "servo_borrow_types": [
@@ -441,17 +453,17 @@ def build(objdir, target_name, debug, de
 
         return ret
 
     if bindgen is None:
         bindgen = os.path.join(TOOLS_DIR, "rust-bindgen")
 
     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]
 
     if kind_name is not None:
         current_target = copy.deepcopy(current_target)
         extend_object(current_target, current_target["build_kinds"][kind_name])
 
     target_dir = None
@@ -601,17 +613,18 @@ Option<&'a mut {0}>;".format(ty))
     if "servo_mapped_generic_types" in current_target:
         for ty in current_target["servo_mapped_generic_types"]:
             flags.append("--blacklist-type")
             flags.append("{}".format(ty["gecko"]))
             flags.append("--raw-line")
             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")
             flags.append("pub type {0}Borrowed<'a> = &'a {0};".format(ty))
             flags.append("--blacklist-type")
             flags.append("{}BorrowedMut".format(ty))
             flags.append("--raw-line")
             flags.append("pub type {0}BorrowedMut<'a> = &'a mut {0};".format(ty))
@@ -628,17 +641,18 @@ Option<&'a mut {0}>;".format(ty))
             flags.append("{}BorrowedMutOrNull".format(ty))
             flags.append("--raw-line")
             flags.append("pub type {0}BorrowedMutOrNull<'a> = Option<&'a mut {0}>;"
                          .format(ty))
             flags.append("--blacklist-type")
             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"]:
             flags.append("--blacklist-type")
             flags.append(ty)
             flags.append("--raw-line")
             flags.append("use gecko_bindings::structs::{};".format(ty))
 
--- a/servo/components/style/binding_tools/setup_bindgen.sh
+++ b/servo/components/style/binding_tools/setup_bindgen.sh
@@ -30,9 +30,9 @@ export LD_LIBRARY_PATH="${LIBCLANG_PATH}
 export DYLD_LIBRARY_PATH="${LIBCLANG_PATH}"
 
 # Don't try to clone twice.
 if [[ ! -d rust-bindgen ]]; then
   git clone https://github.com/servo/rust-bindgen.git
 fi
 
 cd rust-bindgen
-cargo build --features llvm_stable
+cargo build --features llvm_stable --release
--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -33,16 +33,24 @@ impl LocalStyleContextCreationInfo {
 
 pub struct SharedStyleContext {
     /// The current viewport size.
     pub viewport_size: Size2D<Au>,
 
     /// 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>,
 
     /// Starts at zero, and increased by one every time a layout completes.
     /// This can be used to easily check for invalid stale data.
     pub generation: u32,
 
     /// Why is this reflow occurring
--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -1,24 +1,56 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Per-node data used in style calculation.
 
+use 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);
 
 impl PseudoStyles {
     pub fn empty() -> Self {
         PseudoStyles(HashMap::with_hasher(Default::default()))
     }
@@ -32,167 +64,418 @@ impl Deref for PseudoStyles {
 impl DerefMut for PseudoStyles {
     fn deref_mut(&mut self) -> &mut Self::Target { &mut self.0 }
 }
 
 /// The styles associated with a node, including the styles for any
 /// 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
+    }
+}
+
+/// 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)]
-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,
-        }
-    }
+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.
 ///
 /// In Gecko, this hangs directly off a node, but is dropped when the frame takes
 /// ownership of the computed style data.
 ///
 /// In Servo, this is embedded inside of layout data, which itself hangs directly
 /// off the node. Servo does not currently implement ownership transfer of the
 /// computed style data to the frame.
 ///
 /// 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 is_initial(&self) -> bool {
+        match *self {
+            ElementData::Initial(_) => true,
+            _ => false,
+        }
+    }
+
+    pub fn is_unstyled_initial(&self) -> bool {
+        match *self {
+            ElementData::Initial(None) => true,
+            _ => false,
         }
     }
 
-    pub fn has_current_styles(&self) -> bool {
-        match self.styles {
-            ElementDataStyles::Current(_) => true,
+    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,
         }
     }
 
-    pub fn get_current_styles(&self) -> Option<&ElementStyles> {
-        match self.styles {
-            ElementDataStyles::Current(ref s) => Some(s),
-            _ => None,
+    /// 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 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(&self) -> Option<&ElementStyles> {
-        match self.styles {
-            ElementDataStyles::Previous(ref s) => s.as_ref(),
-            _ => panic!("Calling previous_styles without having gathered it"),
+        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 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"),
+        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 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 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"),
+        };
     }
 }
--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -2,30 +2,27 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Types and traits used to access the DOM from style calculation.
 
 #![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;
 
 /// An opaque handle to a node, which, unlike UnsafeNode, cannot be transformed
 /// back into a non-opaque representation. The only safe operation that can be
 /// performed on this node is to compare it to another opaque handle or to another
 /// OpaqueNode.
@@ -41,46 +38,50 @@ pub struct OpaqueNode(pub usize);
 impl OpaqueNode {
     /// Returns the address of this node, for debugging purposes.
     #[inline]
     pub fn id(&self) -> usize {
         self.0
     }
 }
 
-#[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,
     /// The node has been styled before, but needs some amount of recomputation.
     Restyle,
     /// The node does not need any style processing, but one or more of its
     /// descendants do.
     Traverse,
     /// No nodes in this subtree require style processing.
     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.
     ///
     /// This is needed because Gecko has a few optimisations for the calculation
     /// of the difference depending on which values have been used during
     /// layout.
     ///
     /// This should be obtained via TNode::existing_style_for_restyle_damage
     type PreExistingComputedValues;
 
     fn compute(old: &Self::PreExistingComputedValues,
                new: &Arc<ComputedValues>) -> Self;
 
     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.
 ///
 /// We avoid exposing the full type id, since computing it in the general case
 /// would be difficult for Gecko nodes.
 pub trait NodeInfo {
     fn is_element(&self) -> bool;
@@ -116,95 +117,103 @@ pub trait TNode : Sized + Copy + Clone +
     fn dump_style(self);
 
     /// Returns an iterator over this node's children.
     fn children(self) -> LayoutIterator<Self::ConcreteChildrenIterator>;
 
     /// 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;
 
     fn as_element(&self) -> Option<Self::ConcreteElement>;
 
     fn needs_dirty_on_viewport_size_changed(&self) -> bool;
 
     unsafe fn set_dirty_on_viewport_size_changed(&self);
 
     fn can_be_fragmented(&self) -> bool;
 
     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 {
     fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, hints: &mut V)
         where V: Push<ApplicableDeclarationBlock>;
 }
 
 pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + PresentationalHintsSynthetizer {
     type ConcreteNode: TNode<ConcreteElement = Self>;
 
     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;
 
     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.
     fn existing_style_for_restyle_damage<'a>(&'a self,
                                              current_computed_values: Option<&'a Arc<ComputedValues>>,
                                              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);
 
     /// Atomically notes that a child has been processed during bottom-up
     /// traversal. Returns the number of children left to process.
     fn did_process_child(&self) -> isize;
 
     /// 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.
     fn frame_has_style(&self) -> bool { false }
 
     /// Returns the styles from the layout frame that owns them, if any.
     ///
     /// FIXME(bholley): Once we start dropping ElementData from nodes when
@@ -226,83 +235,42 @@ pub trait TElement : PartialEq + Debug +
 
         // Compute the default result if this node doesn't require processing.
         let mode_for_descendants = if self.has_dirty_descendants() {
             Traverse
         } else {
             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;
-        }
+    /// Immutably borrows the ElementData.
+    fn borrow_data(&self) -> Option<AtomicRef<ElementData>> {
+        self.get_data().map(|x| x.borrow())
+    }
 
-        // 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();
-            }
-        }
-
-        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())
     }
 }
--- a/servo/components/style/gecko/context.rs
+++ b/servo/components/style/gecko/context.rs
@@ -17,16 +17,20 @@ fn create_or_get_local_context(shared: &
         } else {
             let context = Rc::new(LocalStyleContext::new(&shared.local_context_creation_data.lock().unwrap()));
             *r = Some(context.clone());
             context
         }
     })
 }
 
+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>,
 }
 
 impl<'a> StandaloneStyleContext<'a> {
     pub fn new(shared: &'a SharedStyleContext) -> Self {
         let local_context = create_or_get_local_context(shared);
--- a/servo/components/style/gecko/restyle_damage.rs
+++ b/servo/components/style/gecko/restyle_damage.rs
@@ -3,23 +3,27 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use dom::TRestyleDamage;
 use gecko_bindings::bindings;
 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
     }
 }
 
 impl TRestyleDamage for GeckoRestyleDamage {
     type PreExistingComputedValues = nsStyleContext;
 
@@ -45,8 +49,13 @@ impl TRestyleDamage for GeckoRestyleDama
 impl BitOr for GeckoRestyleDamage {
     type Output = Self;
 
     fn bitor(self, other: Self) -> Self {
         GeckoRestyleDamage(self.0 | other.0)
     }
 }
 
+impl BitOrAssign for GeckoRestyleDamage {
+    fn bitor_assign(&mut self, other: Self) {
+        *self = *self | other;
+    }
+}
--- a/servo/components/style/gecko/snapshot.rs
+++ b/servo/components/style/gecko/snapshot.rs
@@ -1,32 +1,46 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 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]
     fn is_html_element_in_html_document(&self) -> bool {
         unsafe { (*self.0).mIsHTMLElementInHTMLDocument }
     }
 
     #[inline]
@@ -35,76 +49,76 @@ impl GeckoElementSnapshot {
     }
 }
 
 impl ::selectors::MatchAttr for GeckoElementSnapshot {
     type Impl = SelectorImpl;
 
     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()))
         }
     }
 
     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(),
                                                /* ignoreCase = */ false)
         }
     }
 
     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(),
                                                /* ignoreCase = */ true)
         }
     }
     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())
         }
     }
     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())
         }
     }
     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())
         }
     }
     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())
         }
     }
     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())
         }
     }
 }
 
 impl ElementSnapshot for GeckoElementSnapshot {
@@ -118,34 +132,34 @@ impl ElementSnapshot for GeckoElementSna
 
     #[inline]
     fn has_attrs(&self) -> bool {
         self.has_any(Flags::Attributes)
     }
 
     fn id_attr(&self) -> Option<Atom> {
         let ptr = unsafe {
-            bindings::Gecko_SnapshotAtomAttrValue(self.0,
+            bindings::Gecko_SnapshotAtomAttrValue(self.ptr(),
                                                   atom!("id").as_ptr())
         };
 
         if ptr.is_null() {
             None
         } else {
             Some(Atom::from(ptr))
         }
     }
 
     // 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)
     }
 
     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)
     }
 }
--- a/servo/components/style/gecko/traversal.rs
+++ b/servo/components/style/gecko/traversal.rs
@@ -25,34 +25,30 @@ impl<'lc, 'ln> DomTraversalContext<Gecko
         let shared_lc: &'lc Self::SharedContext = unsafe { mem::transmute(shared) };
         RecalcStyleOnly {
             context: StandaloneStyleContext::new(shared_lc),
             root: root,
         }
     }
 
     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);
         }
     }
 
     fn process_postorder(&self, _: GeckoNode<'ln>) {
         unreachable!();
     }
 
     /// 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.
         }
     }
 
     unsafe fn ensure_element_data<'a>(element: &'a GeckoElement<'ln>) -> &'a AtomicRefCell<ElementData> {
         element.ensure_data()
--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -1,44 +1,42 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #![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;
 use gecko_bindings::bindings::{Gecko_DropStyleChildrenIterator, Gecko_MaybeCreateStyleChildrenIterator};
 use gecko_bindings::bindings::{Gecko_ElementState, Gecko_GetLastChild, Gecko_GetNextStyleChild};
 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;
 use sink::Push;
 use std::fmt;
 use std::ptr;
 use std::sync::Arc;
 use string_cache::{Atom, Namespace, WeakAtom, WeakNamespace};
@@ -56,16 +54,32 @@ impl<'ln> GeckoNode<'ln> {
     fn from_content(content: &'ln nsIContent) -> Self {
         GeckoNode(&content._base)
     }
 
     fn node_info(&self) -> &structs::NodeInfo {
         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> {
     fn is_element(&self) -> bool {
         use gecko_bindings::structs::nsINode_BooleanFlag;
         self.0.mBoolFlags & (1u32 << nsINode_BooleanFlag::NodeIsElement as u32) != 0
     }
 
@@ -110,24 +124,16 @@ impl<'ln> TNode for GeckoNode<'ln> {
         }
     }
 
     fn opaque(&self) -> OpaqueNode {
         let ptr: usize = self.0 as *const _ as usize;
         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!()
     }
 
     fn as_element(&self) -> Option<GeckoElement<'ln>> {
         if self.is_element() {
             unsafe { Some(GeckoElement(&*(self.0 as *const _ as *const RawGeckoElement))) }
         } else {
@@ -141,34 +147,18 @@ impl<'ln> TNode for GeckoNode<'ln> {
         false
     }
 
     unsafe fn set_can_be_fragmented(&self, _value: bool) {
         // FIXME(SimonSapin): Servo uses this to implement CSS multicol / fragmentation
         // 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 {
         // Gecko's node doesn't have the DIRTY_ON_VIEWPORT_SIZE_CHANGE flag,
         // so we force them to be dirtied on viewport size change, regardless if
         // they use viewport percentage size or not.
         // TODO(shinglyu): implement this in Gecko: https://github.com/servo/servo/pull/11890
         true
@@ -216,17 +206,17 @@ impl<'a> Iterator for GeckoChildrenItera
 pub struct GeckoElement<'le>(pub &'le RawGeckoElement);
 
 impl<'le> fmt::Debug for GeckoElement<'le> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "<{}", self.get_local_name()));
         if let Some(id) = self.get_id() {
             try!(write!(f, " id={}", id));
         }
-        write!(f, ">")
+        write!(f, "> ({:?})", self.0 as *const _)
     }
 }
 
 impl<'le> GeckoElement<'le> {
     pub fn parse_style_attribute(value: &str) -> PropertyDeclarationBlock {
         // FIXME(bholley): Real base URL and error reporter.
         let base_url = &*DUMMY_BASE_URL;
         // FIXME(heycam): Needs real ParserContextExtraData so that URLs parse
@@ -246,44 +236,60 @@ impl<'le> GeckoElement<'le> {
     // FIXME: We can implement this without OOL calls, but we can't easily given
     // GeckoNode is a raw reference.
     //
     // We can use a Cell<T>, but that's a bit of a pain.
     fn set_flags(&self, flags: u32) {
         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
             // when we destroy the data.
             debug_assert!({ let _ = data.borrow_mut(); true });
         }
     }
 
     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! {
     pub static ref DUMMY_BASE_URL: ServoUrl = {
         ServoUrl::parse("http://www.example.org").unwrap()
     };
 }
 
@@ -320,24 +326,16 @@ impl<'le> TElement for GeckoElement<'le>
             bindings::Gecko_AttrEquals(self.0,
                                        namespace.0.as_ptr(),
                                        attr.as_ptr(),
                                        val.as_ptr(),
                                        /* ignoreCase = */ false)
         }
     }
 
-    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>)
                                              -> Option<&'a nsStyleContext> {
         if current_cv.is_none() {
             // Don't bother in doing an ffi call to get null back.
             return None;
         }
@@ -345,49 +343,39 @@ impl<'le> TElement for GeckoElement<'le>
         unsafe {
             let atom_ptr = pseudo.map(|p| p.as_atom().as_ptr())
                                  .unwrap_or(ptr::null_mut());
             let context_ptr = Gecko_GetStyleContext(self.as_node().0, atom_ptr);
             context_ptr.as_ref()
         }
     }
 
-    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
     }
 
     unsafe fn set_dirty_descendants(&self) {
         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.
     }
 
     fn did_process_child(&self) -> isize {
         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.0.mServoData.get().as_ref() }
     }
-
-    fn get_data(&self) -> Option<&AtomicRefCell<ElementData>> {
-        unsafe { self.raw_node().mServoData.get().as_ref() }
-    }
-
 }
 
 impl<'le> PartialEq for GeckoElement<'le> {
     fn eq(&self, other: &Self) -> bool {
         self.0 as *const _ == other.0 as *const _
     }
 }
 
@@ -396,18 +384,17 @@ impl<'le> PresentationalHintsSynthetizer
         where V: Push<ApplicableDeclarationBlock>
     {
         // FIXME(bholley) - Need to implement this.
     }
 }
 
 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> {
         let mut child = self.as_node().first_child();
         while let Some(child_node) = child {
             if let Some(el) = child_node.as_element() {
                 return Some(el)
             }
--- a/servo/components/style/gecko_bindings/bindings.rs
+++ b/servo/components/style/gecko_bindings/bindings.rs
@@ -52,16 +52,22 @@ pub struct RawServoStyleSet(RawServoStyl
 pub type StyleChildrenIteratorBorrowed<'a> = &'a StyleChildrenIterator;
 pub type StyleChildrenIteratorBorrowedMut<'a> = &'a mut StyleChildrenIterator;
 pub type StyleChildrenIteratorOwned = ::gecko_bindings::sugar::ownership::Owned<StyleChildrenIterator>;
 pub type StyleChildrenIteratorBorrowedOrNull<'a> = Option<&'a StyleChildrenIterator>;
 pub type StyleChildrenIteratorBorrowedMutOrNull<'a> = Option<&'a mut StyleChildrenIterator>;
 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;
 use gecko_bindings::structs::ServoElementSnapshot;
 use gecko_bindings::structs::SheetParsingMode;
 use gecko_bindings::structs::StyleBasicShape;
 use gecko_bindings::structs::StyleBasicShapeType;
 use gecko_bindings::structs::StyleClipPath;
@@ -191,16 +197,25 @@ unsafe impl Send for nsStyleVariables {}
 unsafe impl Sync for nsStyleVariables {}
 use gecko_bindings::structs::nsStyleVisibility;
 unsafe impl Send for nsStyleVisibility {}
 unsafe impl Sync for nsStyleVisibility {}
 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;
 extern "C" {
     pub fn Servo_CssRules_AddRef(ptr: ServoCssRulesBorrowed);
 }
 extern "C" {
     pub fn Servo_CssRules_Release(ptr: ServoCssRulesBorrowed);
@@ -390,59 +405,61 @@ extern "C" {
                                str: *mut nsIAtom) -> bool;
 }
 extern "C" {
     pub fn Gecko_ClassOrClassList(element: RawGeckoElementBorrowed,
                                   class_: *mut *mut nsIAtom,
                                   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;
 }
 extern "C" {
     pub fn Gecko_GetServoDeclarationBlock(element: RawGeckoElementBorrowed)
      -> RawServoDeclarationBlockStrongBorrowedOrNull;
 }
@@ -575,18 +592,21 @@ extern "C" {
      -> *mut nsStyleContext;
 }
 extern "C" {
     pub fn Gecko_CalcStyleDifference(oldstyle: *mut nsStyleContext,
                                      newstyle: ServoComputedValuesBorrowed)
      -> 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);
 }
 extern "C" {
     pub fn Gecko_CopyStyleContentsFrom(content: *mut nsStyleContent,
                                        other: *const nsStyleContent);
 }
@@ -947,17 +967,17 @@ extern "C" {
 extern "C" {
     pub fn Gecko_CopyConstruct_nsStyleEffects(ptr: *mut nsStyleEffects,
                                               other: *const nsStyleEffects);
 }
 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)
      -> RawServoStyleSheetStrong;
 }
 extern "C" {
     pub fn Servo_StyleSheet_FromUTF8Bytes(data: *const nsACString_internal,
                                           parsing_mode: SheetParsingMode,
@@ -1120,20 +1140,16 @@ extern "C" {
                                                  property: *mut nsIAtom,
                                                  is_custom: bool);
 }
 extern "C" {
     pub fn Servo_CSSSupports(name: *const nsACString_internal,
                              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,
                                                    set:
                                                        RawServoStyleSetBorrowed)
      -> ServoComputedValuesStrong;
 }
 extern "C" {
@@ -1154,24 +1170,42 @@ extern "C" {
 }
 extern "C" {
     pub fn Servo_Initialize();
 }
 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_RestyleSubtree(node: RawGeckoNodeBorrowed,
-                                set: RawServoStyleSetBorrowed);
+    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_AssertTreeIsClean(root: RawGeckoElementBorrowed);
 }
 extern "C" {
     pub fn Servo_GetStyleFont(computed_values:
                                   ServoComputedValuesBorrowedOrNull)
      -> *const nsStyleFont;
 }
 extern "C" {
     pub fn Servo_GetStyleColor(computed_values:
--- a/servo/components/style/gecko_bindings/structs_debug.rs
+++ b/servo/components/style/gecko_bindings/structs_debug.rs
@@ -2695,32 +2695,69 @@ pub struct SourceHook {
     pub vtable_: *const SourceHook__bindgen_vtable,
 }
 #[test]
 fn bindgen_test_layout_SourceHook() {
     assert_eq!(::std::mem::size_of::<SourceHook>() , 8usize);
     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,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
 pub struct nsIGlobalObject_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_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)]
 #[derive(Debug, Copy)]
 pub struct nsIURI {
     pub _base: nsISupports,
 }
 #[repr(C)]
@@ -2754,16 +2791,17 @@ pub struct nsPIDOMWindowInner_COMTypeInf
 fn bindgen_test_layout_nsPIDOMWindowInner() {
     assert_eq!(::std::mem::size_of::<nsPIDOMWindowInner>() , 232usize);
     assert_eq!(::std::mem::align_of::<nsPIDOMWindowInner>() , 8usize);
 }
 #[repr(C)]
 #[derive(Debug)]
 pub struct nsIDocument {
     pub _base: nsINode,
+    pub _base_1: DispatcherTrait,
     pub mDeprecationWarnedAbout: u64,
     pub mDocWarningWarnedAbout: u64,
     pub mSelectorCache: [u64; 16usize],
     pub mReferrer: nsCString,
     pub mLastModified: nsString,
     pub mDocumentURI: nsCOMPtr<nsIURI>,
     pub mOriginalURI: nsCOMPtr<nsIURI>,
     pub mChromeXHRDocURI: nsCOMPtr<nsIURI>,
@@ -3678,17 +3716,16 @@ pub struct nsINode {
     pub mNodeInfo: RefPtr<NodeInfo>,
     pub mParent: *mut nsINode,
     pub mBoolFlags: u32,
     pub mNextSibling: *mut nsIContent,
     pub mPreviousSibling: *mut nsIContent,
     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;
 pub type nsINode_DOMPoint = DOMPoint;
 pub type nsINode_DOMPointInit = DOMPointInit;
 pub type nsINode_DOMQuad = DOMQuad;
 pub type nsINode_DOMRectReadOnly = DOMRectReadOnly;
 pub type nsINode_OwningNodeOrString = OwningNodeOrString;
@@ -3828,17 +3865,17 @@ fn bindgen_test_layout_nsINode__bindgen_
     assert_eq!(::std::mem::size_of::<nsINode__bindgen_ty_1>() , 8usize);
     assert_eq!(::std::mem::align_of::<nsINode__bindgen_ty_1>() , 8usize);
 }
 impl Clone for nsINode__bindgen_ty_1 {
     fn clone(&self) -> Self { *self }
 }
 #[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)]
 #[derive(Debug)]
 pub struct EventTarget {
     pub _base: nsIDOMEventTarget,
     pub _base_1: nsWrapperCache,
 }
@@ -4104,17 +4141,17 @@ pub struct nsIScriptGlobalObject {
 #[derive(Debug, Copy, Clone)]
 pub struct nsIScriptGlobalObject_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_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)]
 #[derive(Debug, Copy)]
 pub struct nsIVariant {
     pub _base: nsISupports,
 }
 #[repr(C)]
@@ -4127,36 +4164,16 @@ pub struct nsIVariant_COMTypeInfo<T, U> 
 #[test]
 fn bindgen_test_layout_nsIVariant() {
     assert_eq!(::std::mem::size_of::<nsIVariant>() , 8usize);
     assert_eq!(::std::mem::align_of::<nsIVariant>() , 8usize);
 }
 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)]
 pub struct Runnable {
     pub _base: nsIRunnable,
     pub mRefCnt: ThreadSafeAutoRefCnt,
     pub _mOwningThread: nsAutoOwningThread,
 }
@@ -5100,16 +5117,17 @@ impl Clone for RestyleManagerHandle_Ptr 
 #[test]
 fn bindgen_test_layout_RestyleManagerHandle() {
     assert_eq!(::std::mem::size_of::<RestyleManagerHandle>() , 8usize);
     assert_eq!(::std::mem::align_of::<RestyleManagerHandle>() , 8usize);
 }
 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 =
     nsChangeHint(2);
 pub const nsChangeHint_nsChangeHint_ClearAncestorIntrinsics: nsChangeHint =
     nsChangeHint(4);
 pub const nsChangeHint_nsChangeHint_ClearDescendantIntrinsics: nsChangeHint =
     nsChangeHint(8);
@@ -5499,17 +5517,17 @@ extern "C" {
     pub static mut nsIContent_sTabFocusModel: i32;
 }
 extern "C" {
     #[link_name = "_ZN10nsIContent26sTabFocusModelAppliesToXULE"]
     pub static mut nsIContent_sTabFocusModelAppliesToXUL: bool;
 }
 #[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);
 }
 /**
  * Struct that stores info on an attribute. The name and value must either both
  * be null or both be non-null.
  *
  * Note that, just as the pointers returned by GetAttrNameAt, the pointers that
  * this struct hold are only valid until the element or its attributes are
@@ -5553,16 +5571,17 @@ pub struct DocGroup {
 impl Clone for DocGroup {
     fn clone(&self) -> Self { *self }
 }
 #[repr(C)]
 #[derive(Debug)]
 pub struct Element {
     pub _base: FragmentOrElement,
     pub mState: EventStates,
+    pub mServoData: ServoCell<*mut ServoNodeData>,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
 pub struct Element_COMTypeInfo<T, U> {
     pub _address: u8,
     pub _phantom_0: ::std::marker::PhantomData<T>,
     pub _phantom_1: ::std::marker::PhantomData<U>,
 }
@@ -5763,33 +5782,33 @@ fn bindgen_test_layout_FragmentOrElement
 extern "C" {
     #[link_name =
           "_ZN7mozilla3dom17FragmentOrElement21_cycleCollectorGlobalE"]
     pub static mut FragmentOrElement__cycleCollectorGlobal:
                FragmentOrElement_cycleCollection;
 }
 #[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 =
     ReferrerPolicy::RP_No_Referrer_When_Downgrade;
 #[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)]
 pub struct nsIWeakReference {
     pub _base: nsISupports,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
@@ -6624,20 +6643,21 @@ fn bindgen_test_layout_nsIPresShell_Poin
                8usize);
 }
 #[repr(C)]
 #[derive(Debug, Copy)]
 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 {
     fn clone(&self) -> Self { *self }
 }
 #[repr(u32)]
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum nsIPresShell_PaintFlags {
@@ -7009,20 +7029,18 @@ pub const NODE_ALL_DIRECTION_FLAGS: _bin
 pub const NODE_CHROME_ONLY_ACCESS: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_CHROME_ONLY_ACCESS;
 pub const NODE_IS_ROOT_OF_CHROME_ONLY_ACCESS: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_IS_ROOT_OF_CHROME_ONLY_ACCESS;
 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 =
+pub const NODE_HAS_DIRTY_DESCENDANTS_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;
 pub const NODE_TYPE_SPECIFIC_BITS_OFFSET: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_TYPE_SPECIFIC_BITS_OFFSET;
 #[repr(u32)]
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum _bindgen_ty_23 {
     NODE_HAS_LISTENERMANAGER = 4,
     NODE_HAS_PROPERTIES = 8,
     NODE_IS_ANONYMOUS_ROOT = 16,
@@ -7379,17 +7397,17 @@ extern "C" {
     pub static mut Attr__cycleCollectorGlobal: Attr_cycleCollection;
 }
 extern "C" {
     #[link_name = "_ZN7mozilla3dom4Attr12sInitializedE"]
     pub static mut Attr_sInitialized: bool;
 }
 #[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)]
 #[derive(Debug)]
 pub struct nsIAttribute {
     pub _base: nsINode,
     pub mAttrMap: RefPtr<nsDOMAttributeMap>,
 }
@@ -7397,17 +7415,17 @@ pub struct nsIAttribute {
 #[derive(Debug, Copy, Clone)]
 pub struct nsIAttribute_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_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)]
 #[derive(Debug)]
 pub struct DOMIntersectionObserver {
     pub _base: nsISupports,
     pub _base_1: nsWrapperCache,
     pub mRefCnt: nsCycleCollectingAutoRefCnt,
@@ -7609,28 +7627,26 @@ pub enum ServoElementSnapshotFlags { Sta
  * etc...
  */
 #[repr(C)]
 #[derive(Debug)]
 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,
 }
 pub type ServoElementSnapshot_BorrowedAttrInfo = BorrowedAttrInfo;
 pub type ServoElementSnapshot_Element = Element;
 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)]
 #[derive(Debug, Copy)]
 pub struct nsMappedAttributes {
     pub _address: u8,
 }
 impl Clone for nsMappedAttributes {
--- a/servo/components/style/gecko_bindings/structs_release.rs
+++ b/servo/components/style/gecko_bindings/structs_release.rs
@@ -2682,32 +2682,69 @@ pub struct SourceHook {
     pub vtable_: *const SourceHook__bindgen_vtable,
 }
 #[test]
 fn bindgen_test_layout_SourceHook() {
     assert_eq!(::std::mem::size_of::<SourceHook>() , 8usize);
     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,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
 pub struct nsIGlobalObject_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_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)]
 #[derive(Debug, Copy)]
 pub struct nsIURI {
     pub _base: nsISupports,
 }
 #[repr(C)]
@@ -2741,16 +2778,17 @@ pub struct nsPIDOMWindowInner_COMTypeInf
 fn bindgen_test_layout_nsPIDOMWindowInner() {
     assert_eq!(::std::mem::size_of::<nsPIDOMWindowInner>() , 224usize);
     assert_eq!(::std::mem::align_of::<nsPIDOMWindowInner>() , 8usize);
 }
 #[repr(C)]
 #[derive(Debug)]
 pub struct nsIDocument {
     pub _base: nsINode,
+    pub _base_1: DispatcherTrait,
     pub mDeprecationWarnedAbout: u64,
     pub mDocWarningWarnedAbout: u64,
     pub mSelectorCache: [u64; 15usize],
     pub mReferrer: nsCString,
     pub mLastModified: nsString,
     pub mDocumentURI: nsCOMPtr<nsIURI>,
     pub mOriginalURI: nsCOMPtr<nsIURI>,
     pub mChromeXHRDocURI: nsCOMPtr<nsIURI>,
@@ -3660,17 +3698,16 @@ pub struct nsINode {
     pub mNodeInfo: RefPtr<NodeInfo>,
     pub mParent: *mut nsINode,
     pub mBoolFlags: u32,
     pub mNextSibling: *mut nsIContent,
     pub mPreviousSibling: *mut nsIContent,
     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;
 pub type nsINode_DOMPoint = DOMPoint;
 pub type nsINode_DOMPointInit = DOMPointInit;
 pub type nsINode_DOMQuad = DOMQuad;
 pub type nsINode_DOMRectReadOnly = DOMRectReadOnly;
 pub type nsINode_OwningNodeOrString = OwningNodeOrString;
@@ -3810,17 +3847,17 @@ fn bindgen_test_layout_nsINode__bindgen_
     assert_eq!(::std::mem::size_of::<nsINode__bindgen_ty_1>() , 8usize);
     assert_eq!(::std::mem::align_of::<nsINode__bindgen_ty_1>() , 8usize);
 }
 impl Clone for nsINode__bindgen_ty_1 {
     fn clone(&self) -> Self { *self }
 }
 #[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)]
 #[derive(Debug)]
 pub struct EventTarget {
     pub _base: nsIDOMEventTarget,
     pub _base_1: nsWrapperCache,
 }
@@ -4086,17 +4123,17 @@ pub struct nsIScriptGlobalObject {
 #[derive(Debug, Copy, Clone)]
 pub struct nsIScriptGlobalObject_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_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)]
 #[derive(Debug, Copy)]
 pub struct nsIVariant {
     pub _base: nsISupports,
 }
 #[repr(C)]
@@ -4109,36 +4146,16 @@ pub struct nsIVariant_COMTypeInfo<T, U> 
 #[test]
 fn bindgen_test_layout_nsIVariant() {
     assert_eq!(::std::mem::size_of::<nsIVariant>() , 8usize);
     assert_eq!(::std::mem::align_of::<nsIVariant>() , 8usize);
 }
 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)]
 pub struct Runnable {
     pub _base: nsIRunnable,
     pub mRefCnt: ThreadSafeAutoRefCnt,
     pub _mOwningThread: nsAutoOwningThread,
 }
@@ -5079,16 +5096,17 @@ impl Clone for RestyleManagerHandle_Ptr 
 #[test]
 fn bindgen_test_layout_RestyleManagerHandle() {
     assert_eq!(::std::mem::size_of::<RestyleManagerHandle>() , 8usize);
     assert_eq!(::std::mem::align_of::<RestyleManagerHandle>() , 8usize);
 }
 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 =
     nsChangeHint(2);
 pub const nsChangeHint_nsChangeHint_ClearAncestorIntrinsics: nsChangeHint =
     nsChangeHint(4);
 pub const nsChangeHint_nsChangeHint_ClearDescendantIntrinsics: nsChangeHint =
     nsChangeHint(8);
@@ -5459,17 +5477,17 @@ extern "C" {
     pub static mut nsIContent_sTabFocusModel: i32;
 }
 extern "C" {
     #[link_name = "_ZN10nsIContent26sTabFocusModelAppliesToXULE"]
     pub static mut nsIContent_sTabFocusModelAppliesToXUL: bool;
 }
 #[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);
 }
 /**
  * Struct that stores info on an attribute. The name and value must either both
  * be null or both be non-null.
  *
  * Note that, just as the pointers returned by GetAttrNameAt, the pointers that
  * this struct hold are only valid until the element or its attributes are
@@ -5513,16 +5531,17 @@ pub struct DocGroup {
 impl Clone for DocGroup {
     fn clone(&self) -> Self { *self }
 }
 #[repr(C)]
 #[derive(Debug)]
 pub struct Element {
     pub _base: FragmentOrElement,
     pub mState: EventStates,
+    pub mServoData: ServoCell<*mut ServoNodeData>,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
 pub struct Element_COMTypeInfo<T, U> {
     pub _address: u8,
     pub _phantom_0: ::std::marker::PhantomData<T>,
     pub _phantom_1: ::std::marker::PhantomData<U>,
 }
@@ -5723,33 +5742,33 @@ fn bindgen_test_layout_FragmentOrElement
 extern "C" {
     #[link_name =
           "_ZN7mozilla3dom17FragmentOrElement21_cycleCollectorGlobalE"]
     pub static mut FragmentOrElement__cycleCollectorGlobal:
                FragmentOrElement_cycleCollection;
 }
 #[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 =
     ReferrerPolicy::RP_No_Referrer_When_Downgrade;
 #[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)]
 pub struct nsIWeakReference {
     pub _base: nsISupports,
 }
 #[repr(C)]
 #[derive(Debug, Copy, Clone)]
@@ -6582,20 +6601,21 @@ fn bindgen_test_layout_nsIPresShell_Poin
                8usize);
 }
 #[repr(C)]
 #[derive(Debug, Copy)]
 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 {
     fn clone(&self) -> Self { *self }
 }
 #[repr(u32)]
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum nsIPresShell_PaintFlags {
@@ -6967,20 +6987,18 @@ pub const NODE_ALL_DIRECTION_FLAGS: _bin
 pub const NODE_CHROME_ONLY_ACCESS: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_CHROME_ONLY_ACCESS;
 pub const NODE_IS_ROOT_OF_CHROME_ONLY_ACCESS: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_IS_ROOT_OF_CHROME_ONLY_ACCESS;
 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 =
+pub const NODE_HAS_DIRTY_DESCENDANTS_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;
 pub const NODE_TYPE_SPECIFIC_BITS_OFFSET: _bindgen_ty_23 =
     _bindgen_ty_23::NODE_TYPE_SPECIFIC_BITS_OFFSET;
 #[repr(u32)]
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum _bindgen_ty_23 {
     NODE_HAS_LISTENERMANAGER = 4,
     NODE_HAS_PROPERTIES = 8,
     NODE_IS_ANONYMOUS_ROOT = 16,
@@ -7337,17 +7355,17 @@ extern "C" {
     pub static mut Attr__cycleCollectorGlobal: Attr_cycleCollection;
 }
 extern "C" {
     #[link_name = "_ZN7mozilla3dom4Attr12sInitializedE"]
     pub static mut Attr_sInitialized: bool;
 }
 #[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)]
 #[derive(Debug)]
 pub struct nsIAttribute {
     pub _base: nsINode,
     pub mAttrMap: RefPtr<nsDOMAttributeMap>,
 }
@@ -7355,17 +7373,17 @@ pub struct nsIAttribute {
 #[derive(Debug, Copy, Clone)]
 pub struct nsIAttribute_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_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)]
 #[derive(Debug)]
 pub struct DOMIntersectionObserver {
     pub _base: nsISupports,
     pub _base_1: nsWrapperCache,
     pub mRefCnt: nsCycleCollectingAutoRefCnt,
@@ -7566,28 +7584,26 @@ pub enum ServoElementSnapshotFlags { Sta
  * etc...
  */
 #[repr(C)]
 #[derive(Debug)]
 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,
 }
 pub type ServoElementSnapshot_BorrowedAttrInfo = BorrowedAttrInfo;
 pub type ServoElementSnapshot_Element = Element;
 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)]
 #[derive(Debug, Copy)]
 pub struct nsMappedAttributes {
     pub _address: u8,
 }
 impl Clone for nsMappedAttributes {
--- a/servo/components/style/gecko_bindings/sugar/ownership.rs
+++ b/servo/components/style/gecko_bindings/sugar/ownership.rs
@@ -203,16 +203,17 @@ unsafe impl<T: HasArcFFI> FFIArcHelpers 
     #[inline]
     fn as_borrowed_opt(&self) -> Option<&T::FFIType> {
         let borrowedptr = self as *const Arc<T> as *const Option<&T::FFIType>;
         unsafe { ptr::read(borrowedptr) }
     }
 }
 
 #[repr(C)]
+#[derive(Debug)]
 /// Gecko-FFI-safe owned pointer
 /// Cannot be null
 /// Leaks on drop. Please don't drop this.
 pub struct Owned<T> {
     ptr: *mut T,
     _marker: PhantomData<T>,
 }
 
--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -7,29 +7,28 @@
 #![allow(unsafe_code)]
 
 use {Atom, LocalName};
 use animation;
 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;
 use rule_tree::StrongRuleNode;
 use selector_parser::{PseudoElement, RestyleDamage, SelectorImpl};
 use selectors::MatchAttr;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{AFFECTED_BY_PSEUDO_ELEMENTS, MatchingReason, StyleRelations};
 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;
 use util::opts;
 
 fn create_common_style_affecting_attributes_from_element<E: TElement>(element: &E)
                                                          -> CommonStyleAffectingAttributes {
     let mut flags = CommonStyleAffectingAttributes::empty();
@@ -116,17 +115,17 @@ pub enum CacheMiss {
     SiblingRules,
     NonCommonAttrRules,
 }
 
 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);
         }
     }
 
     if element.parent_element() != candidate_element.parent_element() {
         miss!(Parent)
@@ -182,20 +181,19 @@ fn element_matches_candidate<E: TElement
 
     if !match_same_not_common_style_affecting_attributes_rules(element,
                                                                candidate_element,
                                                                shared_context) {
         miss!(NonCommonAttrRules)
     }
 
     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,
                                                             candidate: &mut StyleSharingCandidate,
                                                             candidate_element: &E) -> bool {
     if candidate.common_style_affecting_attributes.is_none() {
         candidate.common_style_affecting_attributes =
             Some(create_common_style_affecting_attributes_from_element(candidate_element))
@@ -370,17 +368,17 @@ impl StyleSharingCandidateCache {
 /// The results of attempting to share a style.
 pub enum StyleSharingResult {
     /// We didn't find anybody to share the style with.
     CannotShare,
     /// The node's style can be shared. The integer specifies the index in the
     /// 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.
 // We encapsulate them in this struct to avoid mixing them up.
 //
 // FIXME(pcwalton): Unify with `CascadeFlags`, perhaps?
 struct CascadeBooleans {
     shareable: bool,
@@ -491,17 +489,17 @@ trait PrivateMatchMethods: TElement {
         }
 
         had_animations_to_expire || had_running_animations
     }
 
     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()
         };
 
         element_matches_candidate(self, candidate, &candidate_element,
                                   shared_context)
     }
 }
@@ -585,32 +583,33 @@ pub trait MatchMethods : TElement {
         if self.has_attr(&ns!(), &local_name!("id")) {
             return StyleSharingResult::CannotShare
         }
 
         let mut should_clear_cache = false;
         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);
 
                     // Cache miss, let's see what kind of failure to decide
                     // whether we keep trying or not.
                     match miss {
                         // Cache miss because of parent, clear the candidate cache.
@@ -713,73 +712,71 @@ pub trait MatchMethods : TElement {
                               new_style.get_box().clone_display() != display::T::none);
                 RestyleDamage::rebuild_and_reflow()
             }
         }
     }
 
     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,
                                     primary_is_shareable: bool)
         where Ctx: StyleContext<'a>
     {
         // 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;
 
         let damage = {
             let (old_primary, old_pseudos) = match data.previous_styles_mut() {
                 None => (None, None),
                 Some(previous) => {
                     // 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))
                 }
             };
 
             let new_style =
                 self.cascade_node_pseudo_element(context,
                                                  parent_style,
                                                  old_primary,
                                                  &primary_rule_node,
                                                  CascadeBooleans {
                                                      shareable: primary_is_shareable,
                                                      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);
 
             self.as_node().set_can_be_fragmented(parent.map_or(false, |p| {
                 p.as_node().can_be_fragmented() ||
                 parent_style.unwrap().is_multicol()
             }));
 
             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,
                                                    old_primary: Option<&Arc<ComputedValues>>,
                                                    mut old_pseudos: Option<&mut PseudoStyles>,
                                                    new_primary: &Arc<ComputedValues>,
                                                    new_pseudos: &mut PseudoStyles,
                                                    context: &Ctx,
@@ -823,56 +820,58 @@ pub trait MatchMethods : TElement {
 
         let rebuild_and_reflow = RestyleDamage::rebuild_and_reflow();
 
         debug_assert!(new_pseudos.is_empty());
         <Self as MatchAttr>::Impl::each_eagerly_cascaded_pseudo_element(|pseudo| {
             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() {
                 let new_rule_node = maybe_rule_node.unwrap();
 
                 // 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,
                                                          animate: animate,
                                                      });
 
                 // 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;
                 }
             }
         });
 
         damage
     }
 }
--- a/servo/components/style/parallel.rs
+++ b/servo/components/style/parallel.rs
@@ -1,32 +1,31 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Implements parallel traversal over the DOM tree.
 //!
 //! 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};
 use traversal::DomTraversalContext;
 use util::opts;
 
 pub const CHUNK_SIZE: usize = 64;
 
 pub fn traverse_dom<N, C>(root: N,
                           shared_context: &C::SharedContext,
                           queue: &rayon::ThreadPool)
     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);
     }
 
     let nodes = vec![root.to_unsafe()].into_boxed_slice();
     let root = root.opaque();
     queue.install(|| {
--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -1,16 +1,18 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Restyle hints: an optimization to avoid unnecessarily matching selectors.
 
 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};
 use selectors::{Element, MatchAttr};
 use selectors::matching::{MatchingReason, StyleRelations};
 use selectors::matching::matches_complex_selector;
 use selectors::parser::{AttrSelector, Combinator, ComplexSelector, SimpleSelector};
 use std::clone::Clone;
@@ -18,28 +20,43 @@ use std::sync::Arc;
 
 /// When the ElementState of an element (like IN_HOVER_STATE) changes, certain
 /// pseudo-classes (like :hover) may require us to restyle that element, its
 /// siblings, and/or its descendants. Similarly, when various attributes of an
 /// element change, we may also need to restyle things with id, class, and
 /// 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."]
         // NB: In Gecko, we have RESTYLE_SUBTREE which is inclusive of self, but heycam isn't aware
         // of a good reason for that.
         const RESTYLE_DESCENDANTS = 0x02,
         #[doc = "Rerun selector matching on all later siblings of the element and all of their descendants."]
         const RESTYLE_LATER_SIBLINGS = 0x08,
     }
 }
 
+#[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 }
 }
 
 /// In order to compute restyle hints, we perform a selector match against a
 /// list of partial selectors whose rightmost simple selector may be sensitive
 /// to the thing being changed. We do this matching twice, once for the element
--- a/servo/components/style/sequential.rs
+++ b/servo/components/style/sequential.rs
@@ -1,15 +1,15 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! 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,
                           shared: &C::SharedContext)
     where N: TNode,
           C: DomTraversalContext<N>
 {
     fn doit<'a, N, C>(context: &'a C, node: N)
@@ -21,15 +21,14 @@ pub fn traverse_dom<N, C>(root: N,
             C::traverse_children(el, |kid| doit::<N, C>(context, kid));
         }
 
         if context.needs_postorder_traversal() {
             context.process_postorder(node);
         }
     }
 
-    debug_assert!(root.as_element().unwrap().styling_mode() != StylingMode::Stop);
     let context = C::new(shared, root.opaque());
     doit::<N, C>(&context, root);
 
     // Clear the local LRU cache since we store stateful elements inside.
     context.local_context().style_sharing_candidate_cache.borrow_mut().clear();
 }
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -1,15 +1,16 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Selector matching.
 
 use {Atom, LocalName};
+use data::ComputedStyle;
 use dom::PresentationalHintsSynthetizer;
 use element_state::*;
 use error_reporting::StdoutErrorReporter;
 use keyframes::KeyframesAnimation;
 use media_queries::{Device, MediaType};
 use parking_lot::RwLock;
 use properties::{self, CascadeFlags, ComputedValues, INHERIT_ALL, Importance};
 use properties::{PropertyDeclaration, PropertyDeclarationBlock};
@@ -265,17 +266,17 @@ impl Stylist {
     ///
     /// If `inherit_all` is true, then all properties are inherited from the parent; otherwise,
     /// non-inherited properties are reset to their initial values. The flow constructor uses this
     /// flag when constructing anonymous flows.
     pub fn precomputed_values_for_pseudo(&self,
                                          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
             // use into_iter.
             let rule_node =
                 self.rule_tree.insert_ordered_rules(
                     declarations.iter().map(|a| (a.source.clone(), a.importance)));
 
@@ -286,19 +287,19 @@ impl Stylist {
 
             let computed =
                 properties::cascade(self.device.au_viewport_size(),
                                     &rule_node,
                                     parent.map(|p| &**p),
                                     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()))
         }
     }
 
     /// Returns the style for an anonymous box of the given type.
     #[cfg(feature = "servo")]
     pub fn style_for_anonymous_box(&self,
                                    pseudo: &PseudoElement,
                                    parent_style: &Arc<ComputedValues>)
@@ -317,24 +318,24 @@ impl Stylist {
             PseudoElement::Selection |
             PseudoElement::DetailsSummary |
             PseudoElement::DetailsContent => {
                 unreachable!("That pseudo doesn't represent an anonymous box!")
             }
         };
         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
     {
         debug_assert!(SelectorImpl::pseudo_element_cascade_type(pseudo).is_lazy());
         if self.pseudos_map.get(pseudo).is_none() {
             return None;
         }
@@ -354,17 +355,17 @@ impl Stylist {
         let computed =
             properties::cascade(self.device.au_viewport_size(),
                                 &rule_node,
                                 Some(&**parent),
                                 None,
                                 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>]) {
         let cascaded_rule = ViewportRule {
             declarations: viewport::Cascade::from_stylesheets(stylesheets, &device).finish(),
         };
 
         self.viewport_constraints = ViewportConstraints::maybe_new(device.viewport_size, &cascaded_rule);
--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -1,23 +1,24 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Traversing the DOM tree; the bloom filter.
 
 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;
 
 /// Every time we do another layout, the old bloom filters are invalid. This is
 /// detected by ticking a generation number every layout.
 pub type Generation = u32;
 
@@ -104,17 +105,17 @@ fn insert_ancestors_into_bloom_filter<E>
                                          root: OpaqueNode)
                                          where E: TElement {
     debug!("[{}] Inserting ancestors.", tid());
     let mut ancestors = 0;
     loop {
         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,
         };
     }
     debug!("[{}] Inserted {} ancestors.", tid(), ancestors);
 }
 
 pub fn remove_from_bloom_filter<'a, N, C>(context: &C, root: OpaqueNode, node: N)
@@ -142,28 +143,16 @@ pub fn remove_from_bloom_filter<'a, N, C
             // Otherwise, put it back, but remove this node.
             node.as_element().map(|x| x.remove_from_bloom_filter(&mut *bf));
             let unsafe_parent = parent.as_node().to_unsafe();
             put_thread_local_bloom_filter(bf, &unsafe_parent, &context.shared_context());
         },
     };
 }
 
-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;
 
     fn new<'a>(&'a Self::SharedContext, OpaqueNode) -> Self;
 
     /// Process `node` on the way down, before its children have been processed.
     fn process_preorder(&self, node: N);
 
@@ -174,52 +163,46 @@ pub trait DomTraversalContext<N: TNode> 
 
     /// Boolean that specifies whether a bottom up traversal should be
     /// performed.
     ///
     /// If it's false, then process_postorder has no effect at all.
     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);
             }
         }
     }
 
     /// Ensures the existence of the ElementData, and returns it. This can't live
     /// on TNode because of the trait-based separation between Servo's script
     /// and layout crates.
     ///
     /// This is only safe to call in top-down traversal before processing the
     /// 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
     /// children of |element|.
     unsafe fn clear_element_data(element: &N::ConcreteElement);
 
     fn local_context(&self) -> &LocalStyleContext;
 }
@@ -230,187 +213,299 @@ pub fn relations_are_shareable(relations
     use selectors::matching::*;
     !relations.intersects(AFFECTED_BY_ID_SELECTOR |
                           AFFECTED_BY_PSEUDO_ELEMENTS | AFFECTED_BY_STATE |
                           AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR |
                           AFFECTED_BY_STYLE_ATTRIBUTE |
                           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.
 #[inline]
 #[allow(unsafe_code)]
 pub fn recalc_style_at<'a, E, C, D>(context: &'a C,
                                     root: OpaqueNode,
                                     element: E)
     where E: TElement,
           C: StyleContext<'a>,
           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());
 
-        // 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);
-                }
+    let (computed_display_none, propagated_hint) = if should_compute {
+        compute_style::<_, _, D>(context, element, &*bf)
+    } else {
+        (false, StoredRestyleHint::empty())
+    };
 
-                // 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) => {
-                if opts::get().style_sharing_stats {
-                    STYLE_SHARING_CACHE_HITS.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);
-
-                element.set_restyle_damage(damage);
-            }
-        }
-    }
-
-    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);
-                    }
-                }
-            }
-        };
-        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); }
-            }
-        }
+    // 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);
     }
 
     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_MISSES.fetch_add(1, Ordering::Relaxed);
+                }
+
+                // 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);
+            }
+
+            // 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 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,
+        };
+
+        // 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();
+        }
+    }
+}
+
+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);
+            }
+        }
+    }
+
+    unsafe { el.unset_dirty_descendants(); }
+}
+
+/// 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())
+    }
+}
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -3,60 +3,69 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use app_units::Au;
 use cssparser::Parser;
 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};
 use style::gecko_bindings::bindings::{RawServoStyleSheetBorrowed, ServoComputedValuesBorrowed};
 use style::gecko_bindings::bindings::{RawServoStyleSheetStrong, ServoComputedValuesStrong};
 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};
 use style::gecko_bindings::sugar::refptr::{GeckoArcPrincipal, GeckoArcURI};
 use style::parallel;
 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;
 
 /*
  * For Gecko->Servo function calls, we need to redeclare the same signature that was declared in
  * the C header in Gecko. In order to catch accidental mismatches, we run rust-bindgen against
  * those signatures as well, giving us a second declaration of all the Servo_* functions in this
  * crate. If there's a mismatch, LLVM will assert and abort, which is a rather awful thing to
  * depend on but good enough for our purposes.
@@ -75,69 +84,90 @@ pub extern "C" fn Servo_Initialize() -> 
     // Pretend that we're a Servo Layout thread, to make some assertions happy.
     thread_state::initialize(thread_state::LAYOUT);
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_Shutdown() -> () {
     // Destroy our default computed values.
     unsafe { ComputedValues::shutdown(); }
+
+    // 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 restyle_subtree(element: GeckoElement, raw_data: RawServoStyleSetBorrowed) {
+fn create_shared_context(mut per_doc_data: &mut AtomicRefMut<PerDocumentStyleDataImpl>) -> SharedStyleContext {
+    // The stylist consumes stylesheets lazily.
+    per_doc_data.flush_stylesheets();
+
+    let local_context_data =
+        LocalStyleContextCreationInfo::new(per_doc_data.new_animations_sender.clone());
+
+    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(),
+        running_animations: per_doc_data.running_animations.clone(),
+        expired_animations: per_doc_data.expired_animations.clone(),
+        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();
 
-    // 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());
+    // 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;
+        }
+    }
 
-    let shared_style_context = SharedStyleContext {
-        // FIXME (bug 1303229): Use the actual viewport size here
-        viewport_size: Size2D::new(Au(0), Au(0)),
-        screen_size_changed: false,
-        generation: 0,
-        goal: ReflowGoal::ForScriptQuery,
-        stylist: per_doc_data.stylist.clone(),
-        running_animations: per_doc_data.running_animations.clone(),
-        expired_animations: per_doc_data.expired_animations.clone(),
-        error_reporter: Box::new(StdoutErrorReporter),
-        local_context_creation_data: Mutex::new(local_context_data),
-        timer: Timer::new(),
-    };
-
-    if element.styling_mode() == StylingMode::Stop {
-        error!("Unnecessary call to restyle_subtree");
+    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 {
         parallel::traverse_dom::<_, RecalcStyleOnly>(element.as_node(), &shared_style_context,
                                                      per_doc_data.work_queue.as_mut().unwrap());
     }
 }
 
 #[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]
 pub extern "C" fn Servo_RestyleWithAddedDeclaration(declarations: RawServoDeclarationBlockBorrowed,
                                                     previous_style: ServoComputedValuesBorrowed)
   -> ServoComputedValuesStrong
 {
     let previous_style = ComputedValues::as_arc(&previous_style);
@@ -162,20 +192,18 @@ pub extern "C" fn Servo_RestyleWithAdded
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleWorkerThreadCount() -> u32 {
     *NUM_THREADS as 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]
 pub extern "C" fn Servo_StyleSheet_Empty(mode: SheetParsingMode) -> RawServoStyleSheetStrong {
     let url = ServoUrl::parse("about:blank").unwrap();
     let extra_data = ParserContextExtraData::default();
     let origin = match mode {
         SheetParsingMode::eAuthorSheetFeatures => Origin::Author,
@@ -353,63 +381,31 @@ pub extern "C" fn Servo_StyleRule_GetCss
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleRule_GetSelectorText(rule: RawServoStyleRuleBorrowed, result: *mut nsAString) -> () {
     let rule = RwLock::<StyleRule>::as_arc(&rule);
     rule.read().selectors.to_css(unsafe { result.as_mut().unwrap() }).unwrap();
 }
 
 #[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)
      -> ServoComputedValuesStrong {
     // The stylist consumes stylesheets lazily.
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
     data.flush_stylesheets();
 
     let atom = Atom::from(pseudo_tag);
     let pseudo = PseudoElement::from_atom_unchecked(atom, /* anon_box = */ true);
 
 
     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())
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_ComputedValues_GetForPseudoElement(parent_style: ServoComputedValuesBorrowed,
                                                            match_element: RawGeckoElementBorrowed,
                                                            pseudo_tag: *mut nsIAtom,
                                                            raw_data: RawServoStyleSetBorrowed,
@@ -439,17 +435,17 @@ pub extern "C" fn Servo_ComputedValues_G
         PseudoElementCascadeType::Eager => {
             let maybe_computed = element.get_pseudo_style(&pseudo);
             maybe_computed.map_or_else(parent_or_null, FFIArcHelpers::into_strong)
         }
         PseudoElementCascadeType::Lazy => {
             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 => {
             unreachable!("Anonymous pseudo found in \
                          Servo_GetComputedValuesForPseudoElement");
         }
     }
 }
@@ -672,26 +668,175 @@ pub extern "C" fn Servo_CSSSupports(prop
     let extra_data = ParserContextExtraData::default();
 
     match parse_one_declaration(&property, &value, &base_url, Box::new(StdoutErrorReporter), extra_data) {
         Ok(decls) => !decls.is_empty(),
         Err(()) => false,
     }
 }
 
+/// 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();
 
-    // NB: This involves an FFI call, we can get rid of it easily if needed.
-    let current_state = element.get_state();
+    // 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);
 
-    let hint = per_doc_data.stylist
-                           .compute_restyle_hint(&element, &snapshot,
-                                                 current_state);
+            // 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: Binary representations match.
-    unsafe { transmute(hint.bits() as u32) }
+    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()
 }
+
+#[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);
+            }
+        }
+    }
+
+    assert_subtree_is_clean(root);
+}
--- a/servo/ports/geckolib/lib.rs
+++ b/servo/ports/geckolib/lib.rs
@@ -7,16 +7,17 @@
 #[macro_use]extern crate style;
 extern crate app_units;
 extern crate cssparser;
 extern crate env_logger;
 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;
 
 #[allow(non_snake_case)]
 pub mod glue;
 
 // FIXME(bholley): This should probably go away once we harmonize the allocators.
 #[no_mangle]
--- a/servo/tests/unit/stylo/lib.rs
+++ b/servo/tests/unit/stylo/lib.rs
@@ -2,19 +2,19 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 extern crate app_units;
 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;
 
 mod sanity_checks;
 
 mod servo_function_signatures;