servo: Merge #13863 - stylo: Rearrange some data structures in preparation for the new incremental restyle algorithm (from bholley:shuffle_data_structures); r=emilio
authorBobby Holley <bobbyholley@gmail.com>
Fri, 21 Oct 2016 15:50:48 -0500
changeset 478139 95c3397bde26071da73726ed3ccd6c1199df5c3e
parent 478138 a41f256faace00f5a0ecbbcba65999280b1d177a
child 478140 cdd743176cf61f6375301dbb76dd331e34e4f80a
push id44079
push userbmo:gps@mozilla.com
push dateSat, 04 Feb 2017 00:14:49 +0000
reviewersemilio
servo: Merge #13863 - stylo: Rearrange some data structures in preparation for the new incremental restyle algorithm (from bholley:shuffle_data_structures); r=emilio Source-Repo: https://github.com/servo/servo Source-Revision: 9cbac40f618a5d87bd883e81a70e233e0ea3a87f
servo/components/layout/wrapper.rs
servo/components/script/layout_wrapper.rs
servo/components/script_layout_interface/lib.rs
servo/components/script_layout_interface/wrapper_traits.rs
servo/components/style/binding_tools/regen.py
servo/components/style/data.rs
servo/components/style/dom.rs
servo/components/style/gecko/traversal.rs
servo/components/style/gecko/wrapper.rs
servo/components/style/gecko_bindings/structs_debug.rs
servo/components/style/gecko_bindings/structs_release.rs
servo/components/style/matching.rs
servo/components/style/traversal.rs
servo/ports/geckolib/glue.rs
--- a/servo/components/layout/wrapper.rs
+++ b/servo/components/layout/wrapper.rs
@@ -36,17 +36,17 @@ use script_layout_interface::{OpaqueStyl
 use script_layout_interface::wrapper_traits::{LayoutNode, ThreadSafeLayoutNode};
 use style::atomic_refcell::{AtomicRef, AtomicRefCell, AtomicRefMut};
 use style::computed_values::content::{self, ContentItem};
 
 pub type NonOpaqueStyleAndLayoutData = *mut AtomicRefCell<PersistentLayoutData>;
 
 pub trait LayoutNodeLayoutData {
     /// Similar to borrow_data*, but returns the full PersistentLayoutData rather
-    /// than only the PersistentStyleData.
+    /// than only the style::data::NodeData.
     fn borrow_layout_data(&self) -> Option<AtomicRef<PersistentLayoutData>>;
     fn mutate_layout_data(&self) -> Option<AtomicRefMut<PersistentLayoutData>>;
     fn initialize_data(self);
     fn flow_debug_id(self) -> usize;
 }
 
 impl<T: LayoutNode> LayoutNodeLayoutData for T {
     fn borrow_layout_data(&self) -> Option<AtomicRef<PersistentLayoutData>> {
--- a/servo/components/script/layout_wrapper.rs
+++ b/servo/components/script/layout_wrapper.rs
@@ -47,25 +47,25 @@ use script_layout_interface::{HTMLCanvas
 use script_layout_interface::{OpaqueStyleAndLayoutData, PartialPersistentLayoutData};
 use script_layout_interface::restyle_damage::RestyleDamage;
 use script_layout_interface::wrapper_traits::{DangerousThreadSafeLayoutNode, LayoutNode, PseudoElementType};
 use script_layout_interface::wrapper_traits::{ThreadSafeLayoutElement, ThreadSafeLayoutNode};
 use selectors::matching::ElementFlags;
 use selectors::parser::{AttrSelector, NamespaceConstraint};
 use std::fmt;
 use std::marker::PhantomData;
-use std::mem::{replace, transmute};
+use std::mem::transmute;
 use std::sync::Arc;
 use std::sync::atomic::Ordering;
 use string_cache::{Atom, Namespace};
 use style::atomic_refcell::{AtomicRef, AtomicRefCell, AtomicRefMut};
 use style::attr::AttrValue;
 use style::computed_values::display;
 use style::context::SharedStyleContext;
-use style::data::{PersistentStyleData, PseudoStyles};
+use style::data::NodeData;
 use style::dom::{LayoutIterator, NodeInfo, OpaqueNode, PresentationalHintsSynthetizer, TDocument, TElement, TNode};
 use style::dom::{TRestyleDamage, UnsafeNode};
 use style::element_state::*;
 use style::properties::{ComputedValues, PropertyDeclarationBlock};
 use style::selector_impl::{ElementSnapshot, NonTSPseudoClass, PseudoElement, ServoSelectorImpl};
 use style::selector_matching::ApplicableDeclarationBlock;
 use style::sink::Push;
 use style::str::is_whitespace;
@@ -102,21 +102,17 @@ impl<'ln> ServoLayoutNode<'ln> {
     /// Creates a new layout node with the same lifetime as this layout node.
     pub unsafe fn new_with_this_lifetime(&self, node: &LayoutJS<Node>) -> ServoLayoutNode<'ln> {
         ServoLayoutNode {
             node: *node,
             chain: self.chain,
         }
     }
 
-    pub fn borrow_data(&self) -> Option<AtomicRef<PersistentStyleData>> {
-        self.get_style_data().map(|d| d.borrow())
-    }
-
-    pub fn mutate_data(&self) -> Option<AtomicRefMut<PersistentStyleData>> {
+    pub fn mutate_data(&self) -> Option<AtomicRefMut<NodeData>> {
         self.get_style_data().map(|d| d.borrow_mut())
     }
 
     fn script_type_id(&self) -> NodeTypeId {
         unsafe {
             self.node.type_id_for_layout()
         }
     }
@@ -229,42 +225,35 @@ impl<'ln> TNode for ServoLayoutNode<'ln>
 
     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 get_existing_style(&self) -> Option<Arc<ComputedValues>> {
-        self.borrow_data().and_then(|x| x.style.clone())
-    }
-
-    fn set_style(&self, style: Arc<ComputedValues>) {
-        self.mutate_data().unwrap().style = Some(style);
-    }
-
-    fn take_pseudo_styles(&self) -> PseudoStyles {
-        replace(&mut self.mutate_data().unwrap().per_pseudo, PseudoStyles::default())
-    }
-
-    fn set_pseudo_styles(&self, styles: PseudoStyles) {
-        debug_assert!(self.borrow_data().unwrap().per_pseudo.is_empty());
-        self.mutate_data().unwrap().per_pseudo = styles;
+    fn begin_styling(&self) -> AtomicRefMut<NodeData> {
+        let mut data = self.mutate_data().unwrap();
+        data.gather_previous_styles(|| None);
+        data
     }
 
     fn style_text_node(&self, style: Arc<ComputedValues>) {
         debug_assert!(self.is_text_node());
         let mut data = self.get_partial_layout_data().unwrap().borrow_mut();
-        data.style_data.style = Some(style);
+        data.style_data.style_text_node(style);
         if self.has_changed() {
             data.restyle_damage = RestyleDamage::rebuild_and_reflow();
         }
     }
 
+    fn borrow_data(&self) -> Option<AtomicRef<NodeData>> {
+        self.get_style_data().map(|d| d.borrow())
+    }
+
     fn restyle_damage(self) -> RestyleDamage {
         self.get_partial_layout_data().unwrap().borrow().restyle_damage
     }
 
     fn set_restyle_damage(self, damage: RestyleDamage) {
         let mut damage = damage;
         if self.has_changed() {
             damage = RestyleDamage::rebuild_and_reflow();
@@ -340,21 +329,21 @@ impl<'ln> LayoutNode for ServoLayoutNode
     }
 
     unsafe fn clear_dirty_bits(&self) {
         self.node.set_flag(HAS_CHANGED, false);
         self.node.set_flag(IS_DIRTY, false);
         self.node.set_flag(HAS_DIRTY_DESCENDANTS, false);
     }
 
-    fn get_style_data(&self) -> Option<&AtomicRefCell<PersistentStyleData>> {
+    fn get_style_data(&self) -> Option<&AtomicRefCell<NodeData>> {
         unsafe {
             self.get_jsmanaged().get_style_and_layout_data().map(|d| {
                 let ppld: &AtomicRefCell<PartialPersistentLayoutData> = &**d.ptr;
-                let psd: &AtomicRefCell<PersistentStyleData> = transmute(ppld);
+                let psd: &AtomicRefCell<NodeData> = transmute(ppld);
                 psd
             })
         }
     }
 
     fn init_style_and_layout_data(&self, data: OpaqueStyleAndLayoutData) {
         unsafe {
             self.get_jsmanaged().init_style_and_layout_data(data);
@@ -408,21 +397,17 @@ impl<'ln> ServoLayoutNode<'ln> {
 
     fn debug_str(self) -> String {
         format!("{:?}: changed={} dirty={} dirty_descendants={}",
                 self.script_type_id(), self.has_changed(), self.is_dirty(), self.has_dirty_descendants())
     }
 
     fn debug_style_str(self) -> String {
         if let Some(data) = self.borrow_data() {
-            if let Some(data) = data.style.as_ref() {
-                format!("{:?}: {:?}", self.script_type_id(), data)
-            } else {
-                format!("{:?}: style=None", self.script_type_id())
-            }
+            format!("{:?}: {:?}", self.script_type_id(), &*data)
         } else {
             format!("{:?}: style_data=None", self.script_type_id())
         }
     }
 
     /// Returns the interior of this node as a `LayoutJS`. This is highly unsafe for layout to
     /// call and as such is marked `unsafe`.
     pub unsafe fn get_jsmanaged(&self) -> &LayoutJS<Node> {
@@ -917,17 +902,17 @@ impl<'ln> ThreadSafeLayoutNode for Servo
     }
 
     fn get_colspan(&self) -> u32 {
         unsafe {
             self.get_jsmanaged().downcast::<Element>().unwrap().get_colspan()
         }
     }
 
-    fn get_style_data(&self) -> Option<&AtomicRefCell<PersistentStyleData>> {
+    fn get_style_data(&self) -> Option<&AtomicRefCell<NodeData>> {
         self.node.get_style_data()
     }
 }
 
 pub struct ThreadSafeLayoutNodeChildrenIterator<ConcreteNode: ThreadSafeLayoutNode> {
     current_node: Option<ConcreteNode>,
     parent_node: ConcreteNode,
 }
--- a/servo/components/script_layout_interface/lib.rs
+++ b/servo/components/script_layout_interface/lib.rs
@@ -48,36 +48,36 @@ pub mod wrapper_traits;
 
 use canvas_traits::CanvasMsg;
 use core::nonzero::NonZero;
 use ipc_channel::ipc::IpcSender;
 use libc::c_void;
 use restyle_damage::RestyleDamage;
 use std::sync::atomic::AtomicIsize;
 use style::atomic_refcell::AtomicRefCell;
-use style::data::PersistentStyleData;
+use style::data::NodeData;
 
 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 PersistentStyleData and PersistentLayoutData.
-    pub style_data: PersistentStyleData,
+    /// transmutations between NodeData and PersistentLayoutData.
+    pub style_data: NodeData,
 
     /// 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: PersistentStyleData::new(),
+            style_data: NodeData::new(),
             restyle_damage: RestyleDamage::empty(),
             parallel: DomParallelInfo::new(),
         }
     }
 }
 
 #[derive(Copy, Clone, HeapSizeOf)]
 pub struct OpaqueStyleAndLayoutData {
--- a/servo/components/script_layout_interface/wrapper_traits.rs
+++ b/servo/components/script_layout_interface/wrapper_traits.rs
@@ -13,17 +13,17 @@ use msg::constellation_msg::PipelineId;
 use range::Range;
 use restyle_damage::RestyleDamage;
 use std::fmt::Debug;
 use std::sync::Arc;
 use string_cache::{Atom, Namespace};
 use style::atomic_refcell::AtomicRefCell;
 use style::computed_values::display;
 use style::context::SharedStyleContext;
-use style::data::PersistentStyleData;
+use style::data::NodeData;
 use style::dom::{LayoutIterator, NodeInfo, PresentationalHintsSynthetizer, TNode};
 use style::dom::OpaqueNode;
 use style::properties::ServoComputedValues;
 use style::selector_impl::{PseudoElement, PseudoElementCascadeType, ServoSelectorImpl};
 use url::Url;
 
 #[derive(Copy, PartialEq, Clone)]
 pub enum PseudoElementType<T> {
@@ -78,17 +78,17 @@ pub trait LayoutNode: TNode {
 
     /// Returns the type ID of this node.
     fn type_id(&self) -> LayoutNodeType;
 
     fn has_changed(&self) -> bool;
 
     unsafe fn clear_dirty_bits(&self);
 
-    fn get_style_data(&self) -> Option<&AtomicRefCell<PersistentStyleData>>;
+    fn get_style_data(&self) -> Option<&AtomicRefCell<NodeData>>;
 
     fn init_style_and_layout_data(&self, data: OpaqueStyleAndLayoutData);
     fn get_style_and_layout_data(&self) -> Option<OpaqueStyleAndLayoutData>;
 
     fn rev_children(self) -> LayoutIterator<ReverseChildrenIterator<Self>> {
         LayoutIterator(ReverseChildrenIterator {
             current: self.last_child(),
         })
@@ -185,30 +185,30 @@ pub trait ThreadSafeLayoutNode: Clone + 
     #[inline]
     fn get_pseudo_element_type(&self) -> PseudoElementType<Option<display::T>>;
 
     #[inline]
     fn get_before_pseudo(&self) -> Option<Self> {
         if self.get_style_data()
                .unwrap()
                .borrow()
-               .per_pseudo
+               .current_styles().pseudos
                .contains_key(&PseudoElement::Before) {
             Some(self.with_pseudo(PseudoElementType::Before(None)))
         } else {
             None
         }
     }
 
     #[inline]
     fn get_after_pseudo(&self) -> Option<Self> {
         if self.get_style_data()
                .unwrap()
                .borrow()
-               .per_pseudo
+               .current_styles().pseudos
                .contains_key(&PseudoElement::After) {
             Some(self.with_pseudo(PseudoElementType::After(None)))
         } else {
             None
         }
     }
 
     #[inline]
@@ -244,60 +244,60 @@ pub trait ThreadSafeLayoutNode: Clone + 
     /// 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()
-                    .style.as_ref().unwrap().clone()
+                    .current_styles().primary.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()
-                                .per_pseudo.contains_key(&style_pseudo) {
+                                .current_styles().pseudos.contains_key(&style_pseudo) {
                             let mut data = self.get_style_data().unwrap().borrow_mut();
                             let new_style =
                                 context.stylist
                                        .precomputed_values_for_pseudo(&style_pseudo,
-                                                                      data.style.as_ref());
-                            data.per_pseudo
+                                                                      Some(&data.current_styles().primary));
+                            data.current_pseudos_mut()
                                 .insert(style_pseudo.clone(), new_style.unwrap());
                         }
                     }
                     PseudoElementCascadeType::Lazy => {
                         debug_assert!(self.is_element_or_elements_pseudo());
                         if !self.get_style_data()
                                 .unwrap()
                                 .borrow()
-                                .per_pseudo.contains_key(&style_pseudo) {
+                                .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.as_element(),
                                            &style_pseudo,
-                                           data.style.as_ref().unwrap());
-                            data.per_pseudo
+                                           &data.current_styles().primary);
+                            data.current_pseudos_mut()
                                 .insert(style_pseudo.clone(), new_style.unwrap());
                         }
                     }
                 }
 
                 self.get_style_data().unwrap().borrow()
-                    .per_pseudo.get(&style_pseudo)
+                    .current_styles().pseudos.get(&style_pseudo)
                     .unwrap().clone()
             }
         }
     }
 
     /// Returns the already resolved style of the node.
     ///
     /// This differs from `style(ctx)` in that if the pseudo-element has not yet
@@ -305,44 +305,29 @@ pub trait ThreadSafeLayoutNode: Clone + 
     ///
     /// 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.style.as_ref().unwrap().clone(),
+                => data.current_styles().primary.clone(),
             other
-                => data.per_pseudo.get(&other.style_pseudo_element()).unwrap().clone(),
+                => data.current_styles().pseudos.get(&other.style_pseudo_element()).unwrap().clone(),
         }
     }
 
     #[inline]
     fn selected_style(&self, _context: &SharedStyleContext) -> Arc<ServoComputedValues> {
         let data = self.get_style_data().unwrap().borrow();
-        data.per_pseudo
+        data.current_styles().pseudos
             .get(&PseudoElement::Selection)
-            .unwrap_or(data.style.as_ref().unwrap()).clone()
-    }
-
-    /// Removes the style from this node.
-    ///
-    /// Unlike the version on TNode, this handles pseudo-elements.
-    fn unstyle(self) {
-        let mut data = self.get_style_data().unwrap().borrow_mut();
-
-        match self.get_pseudo_element_type() {
-            PseudoElementType::Normal => {
-                data.style = None;
-            }
-            other => {
-                data.per_pseudo.remove(&other.style_pseudo_element());
-            }
-        };
+            .unwrap_or(&data.current_styles().primary)
+            .clone()
     }
 
     fn is_ignorable_whitespace(&self, context: &SharedStyleContext) -> bool;
 
     fn restyle_damage(self) -> RestyleDamage;
 
     fn set_restyle_damage(self, damage: RestyleDamage);
 
@@ -372,17 +357,17 @@ pub trait ThreadSafeLayoutNode: Clone + 
     fn svg_data(&self) -> Option<SVGSVGData>;
 
     /// If this node is an iframe element, returns its pipeline ID. If this node is
     /// not an iframe element, fails.
     fn iframe_pipeline_id(&self) -> PipelineId;
 
     fn get_colspan(&self) -> u32;
 
-    fn get_style_data(&self) -> Option<&AtomicRefCell<PersistentStyleData>>;
+    fn get_style_data(&self) -> Option<&AtomicRefCell<NodeData>>;
 }
 
 // This trait is only public so that it can be implemented by the gecko wrapper.
 // It can be used to violate thread-safety, so don't use it elsewhere in layout!
 #[allow(unsafe_code)]
 pub trait DangerousThreadSafeLayoutNode: ThreadSafeLayoutNode {
     unsafe fn dangerous_first_child(&self) -> Option<Self>;
     unsafe fn dangerous_next_sibling(&self) -> Option<Self>;
--- a/servo/components/style/binding_tools/regen.py
+++ b/servo/components/style/binding_tools/regen.py
@@ -61,18 +61,18 @@ COMPILATION_TARGETS = {
                     "-DDEBUG=1",
                     "-DJS_DEBUG=1",
                 ]
             },
             "release": {
             }
         },
         "raw_lines": [
-            # We can get rid of this when the bindings move into the style crate.
-            "pub enum OpaqueStyleData {}",
+            "use atomic_refcell::AtomicRefCell;",
+            "use data::NodeData;",
             "pub use nsstring::nsStringRepr as nsString;"
         ],
         "blacklist_types": ["nsString"],
         "whitelist_vars": [
             "NS_THEME_.*",
             "NODE_.*",
             "NS_FONT_.*",
             "NS_STYLE_.*",
@@ -224,17 +224,17 @@ COMPILATION_TARGETS = {
                 "servo": "::std::cell::UnsafeCell"
             }, {
                 "generic": True,
                 "gecko": "ServoCell",
                 "servo": "::std::cell::Cell"
             }, {
                 "generic": False,
                 "gecko": "ServoNodeData",
-                "servo": "OpaqueStyleData"
+                "servo": "AtomicRefCell<NodeData>",
             }
         ],
     },
     # Generation of the ffi bindings.
     "bindings": {
         "target_dir": "../gecko_bindings",
         "raw_lines": [],
         "flags": [
--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -3,29 +3,197 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Per-node data used in style calculation.
 
 use properties::ComputedValues;
 use selector_impl::PseudoElement;
 use std::collections::HashMap;
 use std::hash::BuildHasherDefault;
+use std::mem;
+use std::ops::{Deref, DerefMut};
 use std::sync::Arc;
 
-pub type PseudoStyles = HashMap<PseudoElement, Arc<ComputedValues>,
-                                BuildHasherDefault<::fnv::FnvHasher>>;
-pub struct PersistentStyleData {
+type PseudoStylesInner = HashMap<PseudoElement, Arc<ComputedValues>,
+                                 BuildHasherDefault<::fnv::FnvHasher>>;
+#[derive(Clone, Debug)]
+pub struct PseudoStyles(PseudoStylesInner);
+
+impl PseudoStyles {
+    pub fn empty() -> Self {
+        PseudoStyles(HashMap::with_hasher(Default::default()))
+    }
+}
+
+impl Deref for PseudoStyles {
+    type Target = PseudoStylesInner;
+    fn deref(&self) -> &Self::Target { &self.0 }
+}
+
+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 NodeStyles {
     /// The results of CSS styling for this node.
-    pub style: Option<Arc<ComputedValues>>,
+    pub primary: Arc<ComputedValues>,
 
     /// The results of CSS styling for each pseudo-element (if any).
-    pub per_pseudo: PseudoStyles,
+    pub pseudos: PseudoStyles,
+}
+
+impl NodeStyles {
+    pub fn new(primary: Arc<ComputedValues>) -> Self {
+        NodeStyles {
+            primary: primary,
+            pseudos: PseudoStyles::empty(),
+        }
+    }
 }
 
-impl PersistentStyleData {
-    pub fn new() -> Self {
-        PersistentStyleData {
-            style: None,
-            per_pseudo: HashMap::with_hasher(Default::default()),
+#[derive(Debug)]
+enum NodeDataStyles {
+    /// 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 NodeStyles contains an Arc, the null pointer
+    /// optimization prevents the Option<> here from consuming an extra word.
+    Previous(Option<NodeStyles>),
+
+    /// The field holds the current, up-to-date style.
+    ///
+    /// This is the output of the styling algorithm.
+    Current(NodeStyles),
+}
+
+impl NodeDataStyles {
+    fn is_previous(&self) -> bool {
+        use self::NodeDataStyles::*;
+        match *self {
+            Previous(_) => true,
+            _ => false,
+        }
+    }
+}
+
+/// 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,
+}
+
+impl RestyleData {
+    fn new() -> Self {
+        RestyleData {
+            _dummy: 42,
         }
     }
 }
 
+/// 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 NodeData {
+    styles: NodeDataStyles,
+    pub restyle: Option<RestyleData>,
+}
+
+impl NodeData {
+    pub fn new() -> Self {
+        NodeData {
+            styles: NodeDataStyles::Uninitialized,
+            restyle: None,
+        }
+    }
+
+    pub fn has_current_styles(&self) -> bool {
+        match self.styles {
+            NodeDataStyles::Current(_) => true,
+            _ => false,
+        }
+    }
+
+    pub fn get_current_styles(&self) -> Option<&NodeStyles> {
+        match self.styles {
+            NodeDataStyles::Current(ref s) => Some(s),
+            _ => None,
+        }
+    }
+
+    pub fn current_styles(&self) -> &NodeStyles {
+        self.get_current_styles().expect("Calling current_styles before or during styling")
+    }
+
+    // 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 {
+            NodeDataStyles::Current(ref mut s) => &mut s.pseudos,
+            _ => panic!("Calling current_pseudos_mut before or during styling"),
+        }
+    }
+
+    pub fn previous_styles(&self) -> Option<&NodeStyles> {
+        match self.styles {
+            NodeDataStyles::Previous(ref s) => s.as_ref(),
+            _ => panic!("Calling previous_styles without having gathered it"),
+        }
+    }
+
+    pub fn previous_styles_mut(&mut self) -> Option<&mut NodeStyles> {
+        match self.styles {
+            NodeDataStyles::Previous(ref mut s) => s.as_mut(),
+            _ => panic!("Calling previous_styles without having gathered it"),
+        }
+    }
+
+    pub fn gather_previous_styles<F>(&mut self, f: F)
+        where F: FnOnce() -> Option<NodeStyles>
+    {
+        use self::NodeDataStyles::*;
+        self.styles = match mem::replace(&mut self.styles, Uninitialized) {
+            Uninitialized => Previous(f()),
+            Current(x) => Previous(Some(x)),
+            _ => panic!("Already have previous styles"),
+        };
+    }
+
+    // FIXME(bholley): Called in future patches.
+    pub fn ensure_restyle_data(&mut self) {
+        if self.restyle.is_none() {
+            self.restyle = Some(RestyleData::new());
+        }
+    }
+
+    pub fn style_text_node(&mut self, style: Arc<ComputedValues>) {
+        debug_assert!(self.restyle.is_none());
+        self.styles = NodeDataStyles::Current(NodeStyles::new(style));
+    }
+
+    pub fn finish_styling(&mut self, styles: NodeStyles) {
+        debug_assert!(self.styles.is_previous());
+        self.styles = NodeDataStyles::Current(styles);
+        self.restyle = None;
+    }
+}
--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -1,17 +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/. */
 
 //! Types and traits used to access the DOM from style calculation.
 
 #![allow(unsafe_code)]
 
-use data::PseudoStyles;
+use atomic_refcell::{AtomicRef, AtomicRefMut};
+use data::NodeData;
 use element_state::ElementState;
 use parking_lot::RwLock;
 use properties::{ComputedValues, PropertyDeclarationBlock};
 use restyle_hints::{RESTYLE_DESCENDANTS, RESTYLE_LATER_SIBLINGS, RESTYLE_SELF, RestyleHint};
 use selector_impl::{ElementExt, PseudoElement};
 use selector_matching::ApplicableDeclarationBlock;
 use sink::Push;
 use std::fmt::Debug;
@@ -135,38 +136,27 @@ pub trait TNode : Sized + Copy + Clone +
     /// 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 the computed style values corresponding to the existing style
-    /// for this node, if any.
-    ///
-    /// This returns an cloned Arc (rather than a borrow) to abstract over the
-    /// multitude of ways these values may be stored under the hood. By
-    /// returning an enum with various OwningRef/OwningHandle entries, we could
-    /// avoid the refcounting traffic here, but it's probably not worth the
-    /// complexity.
-    fn get_existing_style(&self) -> Option<Arc<ComputedValues>>;
+    /// Sets up the appropriate data structures to style a node, returing a
+    /// mutable handle to the node data upon which further style calculations
+    /// can be performed.
+    fn begin_styling(&self) -> AtomicRefMut<NodeData>;
 
-    /// Sets the computed style for this node.
-    fn set_style(&self, style: Arc<ComputedValues>);
+    /// Set the style directly for a text node. This skips various unnecessary
+    /// steps from begin_styling like computing the previous style.
+    fn style_text_node(&self, style: Arc<ComputedValues>);
 
-    /// Transfers ownership of the existing pseudo styles, if any, to the
-    /// caller. The stored pseudo styles are replaced with an empty map.
-    fn take_pseudo_styles(&self) -> PseudoStyles;
-
-    /// Sets the pseudo styles on the element, replacing any existing styles.
-    fn set_pseudo_styles(&self, styles: PseudoStyles);
-
-    /// Set the style for a text node.
-    fn style_text_node(&self, style: Arc<ComputedValues>);
+    /// Immutable borrows the NodeData.
+    fn borrow_data(&self) -> Option<AtomicRef<NodeData>>;
 
     /// Get the description of how to account for recent style changes.
     fn restyle_damage(self) -> Self::ConcreteRestyleDamage;
 
     /// Set the restyle damage field.
     fn set_restyle_damage(self, damage: Self::ConcreteRestyleDamage);
 
     fn parent_node(&self) -> Option<Self>;
--- a/servo/components/style/gecko/traversal.rs
+++ b/servo/components/style/gecko/traversal.rs
@@ -24,20 +24,16 @@ 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>) -> RestyleResult {
-        // FIXME(pcwalton): Stop allocating here. Ideally this should just be done by the HTML
-        // parser.
-        node.initialize_data();
-
         recalc_style_at(&self.context, self.root, node)
     }
 
     fn process_postorder(&self, _: GeckoNode<'ln>) {
         unreachable!();
     }
 
     /// We don't use the post-order traversal for anything.
--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -1,17 +1,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #![allow(unsafe_code)]
 
 
 use atomic_refcell::{AtomicRef, AtomicRefCell, AtomicRefMut};
-use data::{PersistentStyleData, PseudoStyles};
+use data::{NodeData, NodeStyles};
 use dom::{LayoutIterator, NodeInfo, TDocument, TElement, TNode, TRestyleDamage, UnsafeNode};
 use dom::{OpaqueNode, PresentationalHintsSynthetizer};
 use element_state::ElementState;
 use error_reporting::StdoutErrorReporter;
 use gecko::selector_impl::{GeckoSelectorImpl, NonTSPseudoClass, PseudoElement};
 use gecko::snapshot::GeckoElementSnapshot;
 use gecko::snapshot_helpers;
 use gecko_bindings::bindings;
@@ -24,17 +24,16 @@ use gecko_bindings::bindings::{Gecko_IsL
 use gecko_bindings::bindings::{Gecko_IsUnvisitedLink, Gecko_IsVisitedLink, Gecko_Namespace};
 use gecko_bindings::bindings::Gecko_ClassOrClassList;
 use gecko_bindings::bindings::Gecko_GetStyleContext;
 use gecko_bindings::bindings::Gecko_SetNodeFlags;
 use gecko_bindings::structs;
 use gecko_bindings::structs::{NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO, NODE_IS_DIRTY_FOR_SERVO};
 use gecko_bindings::structs::{RawGeckoDocument, RawGeckoElement, RawGeckoNode};
 use gecko_bindings::structs::{nsChangeHint, nsIAtom, nsIContent, nsStyleContext};
-use gecko_bindings::structs::OpaqueStyleData;
 use gecko_bindings::sugar::ownership::FFIArcHelpers;
 use libc::uintptr_t;
 use parking_lot::RwLock;
 use parser::ParserContextExtraData;
 use properties::{ComputedValues, parse_style_attribute};
 use properties::PropertyDeclarationBlock;
 use selector_impl::ElementExt;
 use selector_matching::ApplicableDeclarationBlock;
@@ -43,32 +42,16 @@ use selectors::parser::{AttrSelector, Na
 use sink::Push;
 use std::fmt;
 use std::ops::BitOr;
 use std::ptr;
 use std::sync::Arc;
 use string_cache::{Atom, Namespace, WeakAtom, WeakNamespace};
 use url::Url;
 
-pub struct NonOpaqueStyleData(AtomicRefCell<PersistentStyleData>);
-
-impl NonOpaqueStyleData {
-    pub fn new() -> Self {
-        NonOpaqueStyleData(AtomicRefCell::new(PersistentStyleData::new()))
-    }
-}
-
-// We can eliminate OpaqueStyleData when the bindings move into the style crate.
-fn to_opaque_style_data(d: *mut NonOpaqueStyleData) -> *mut OpaqueStyleData {
-    d as *mut OpaqueStyleData
-}
-fn from_opaque_style_data(d: *mut OpaqueStyleData) -> *mut NonOpaqueStyleData {
-    d as *mut NonOpaqueStyleData
-}
-
 // Important: We don't currently refcount the DOM, because the wrapper lifetime
 // magic guarantees that our LayoutFoo references won't outlive the root, and
 // we don't mutate any of the references on the Gecko side during restyle. We
 // could implement refcounting if need be (at a potentially non-trivial
 // performance cost) by implementing Drop and making LayoutFoo non-Copy.
 #[derive(Clone, Copy)]
 pub struct GeckoNode<'ln>(pub &'ln RawGeckoNode);
 
@@ -89,50 +72,54 @@ impl<'ln> GeckoNode<'ln> {
     // 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.0, flags) }
     }
 
-    fn get_node_data(&self) -> Option<&NonOpaqueStyleData> {
-        unsafe {
-            from_opaque_style_data(self.0.mServoData.get()).as_ref()
-        }
-    }
+    pub fn clear_data(&self) {
+        let ptr = self.0.mServoData.get();
+        if !ptr.is_null() {
+            let data = unsafe { Box::from_raw(self.0.mServoData.get()) };
+            self.0.mServoData.set(ptr::null_mut());
 
-    pub fn initialize_data(self) {
-        if self.get_node_data().is_none() {
-            let ptr = Box::new(NonOpaqueStyleData::new());
-            debug_assert!(self.0.mServoData.get().is_null());
-            self.0.mServoData.set(to_opaque_style_data(Box::into_raw(ptr)));
-        }
-    }
-
-    pub fn clear_data(self) {
-        if !self.get_node_data().is_none() {
-            let d = from_opaque_style_data(self.0.mServoData.get());
-            let _ = unsafe { Box::from_raw(d) };
-            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.per_pseudo.get(pseudo).map(|c| c.clone()))
+        self.borrow_data().and_then(|data| data.current_styles().pseudos
+                                               .get(pseudo).map(|c| c.clone()))
+    }
+
+    fn styles_from_frame(&self) -> Option<NodeStyles> {
+        // FIXME(bholley): Once we start dropping NodeData from nodes when
+        // creating frames, we'll want to teach this method to actually get
+        // style data from the frame.
+        None
     }
 
-    #[inline(always)]
-    fn borrow_data(&self) -> Option<AtomicRef<PersistentStyleData>> {
-        self.get_node_data().as_ref().map(|d| d.0.borrow())
+    fn get_node_data(&self) -> Option<&AtomicRefCell<NodeData>> {
+        unsafe { self.0.mServoData.get().as_ref() }
     }
 
-    #[inline(always)]
-    fn mutate_data(&self) -> Option<AtomicRefMut<PersistentStyleData>> {
-        self.get_node_data().as_ref().map(|d| d.0.borrow_mut())
+    fn ensure_node_data(&self) -> &AtomicRefCell<NodeData> {
+        match self.get_node_data() {
+            Some(x) => x,
+            None => {
+                let ptr = Box::into_raw(Box::new(AtomicRefCell::new(NodeData::new())));
+                self.0.mServoData.set(ptr);
+                unsafe { &* ptr }
+            },
+        }
     }
 }
 
 #[derive(Clone, Copy, Debug, PartialEq)]
 pub struct GeckoRestyleDamage(nsChangeHint);
 
 impl TRestyleDamage for GeckoRestyleDamage {
     type PreExistingComputedValues = nsStyleContext;
@@ -278,39 +265,29 @@ impl<'ln> TNode for GeckoNode<'ln> {
     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 get_existing_style(&self) -> Option<Arc<ComputedValues>> {
-        self.borrow_data().and_then(|x| x.style.clone())
-    }
-
-    fn set_style(&self, style: Arc<ComputedValues>) {
-        self.mutate_data().unwrap().style = Some(style);
-    }
-
-    fn take_pseudo_styles(&self) -> PseudoStyles {
-        use std::mem;
-        let mut tmp = PseudoStyles::default();
-        mem::swap(&mut tmp, &mut self.mutate_data().unwrap().per_pseudo);
-        tmp
-    }
-
-    fn set_pseudo_styles(&self, styles: PseudoStyles) {
-        debug_assert!(self.borrow_data().unwrap().per_pseudo.is_empty());
-        self.mutate_data().unwrap().per_pseudo = styles;
+    fn begin_styling(&self) -> AtomicRefMut<NodeData> {
+        let mut data = self.ensure_node_data().borrow_mut();
+        data.gather_previous_styles(|| self.styles_from_frame());
+        data
     }
 
     fn style_text_node(&self, style: Arc<ComputedValues>) {
         debug_assert!(self.is_text_node());
-        self.mutate_data().unwrap().style = Some(style);
+        self.ensure_node_data().borrow_mut().style_text_node(style);
+    }
+
+    fn borrow_data(&self) -> Option<AtomicRef<NodeData>> {
+        self.get_node_data().map(|x| x.borrow())
     }
 
     fn restyle_damage(self) -> Self::ConcreteRestyleDamage {
         // Not called from style, only for layout.
         unimplemented!();
     }
 
     fn set_restyle_damage(self, damage: Self::ConcreteRestyleDamage) {
--- a/servo/components/style/gecko_bindings/structs_debug.rs
+++ b/servo/components/style/gecko_bindings/structs_debug.rs
@@ -1,15 +1,16 @@
 /* automatically generated by rust-bindgen */
 
-pub enum OpaqueStyleData {}
+use atomic_refcell::AtomicRefCell;
+use data::NodeData;
 pub use nsstring::nsStringRepr as nsString;
 pub type ServoUnsafeCell<T> = ::std::cell::UnsafeCell<T>;
 pub type ServoCell<T> = ::std::cell::Cell<T>;
-pub type ServoNodeData = OpaqueStyleData;
+pub type ServoNodeData = AtomicRefCell<NodeData>;
 
 #[derive(Debug)]
 #[repr(C)]
 pub struct __BindgenUnionField<T>(::std::marker::PhantomData<T>);
 impl <T> __BindgenUnionField<T> {
     #[inline]
     pub fn new() -> Self { __BindgenUnionField(::std::marker::PhantomData) }
     #[inline]
--- a/servo/components/style/gecko_bindings/structs_release.rs
+++ b/servo/components/style/gecko_bindings/structs_release.rs
@@ -1,15 +1,16 @@
 /* automatically generated by rust-bindgen */
 
-pub enum OpaqueStyleData {}
+use atomic_refcell::AtomicRefCell;
+use data::NodeData;
 pub use nsstring::nsStringRepr as nsString;
 pub type ServoUnsafeCell<T> = ::std::cell::UnsafeCell<T>;
 pub type ServoCell<T> = ::std::cell::Cell<T>;
-pub type ServoNodeData = OpaqueStyleData;
+pub type ServoNodeData = AtomicRefCell<NodeData>;
 
 #[derive(Debug)]
 #[repr(C)]
 pub struct __BindgenUnionField<T>(::std::marker::PhantomData<T>);
 impl <T> __BindgenUnionField<T> {
     #[inline]
     pub fn new() -> Self { __BindgenUnionField(::std::marker::PhantomData) }
     #[inline]
--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -6,28 +6,30 @@
 
 #![allow(unsafe_code)]
 
 use animation;
 use arc_ptr_eq;
 use cache::{LRUCache, SimpleHashCache};
 use cascade_info::CascadeInfo;
 use context::{SharedStyleContext, StyleContext};
+use data::{NodeStyles, PseudoStyles};
 use dom::{NodeInfo, TElement, TNode, TRestyleDamage, UnsafeNode};
 use properties::{ComputedValues, cascade};
 use properties::longhands::display::computed_value as display;
 use selector_impl::{PseudoElement, TheSelectorImpl};
 use selector_matching::{ApplicableDeclarationBlock, Stylist};
 use selectors::{Element, MatchAttr};
 use selectors::bloom::BloomFilter;
 use selectors::matching::{AFFECTED_BY_PSEUDO_ELEMENTS, MatchingReason, StyleRelations};
 use sink::ForgetfulSink;
 use smallvec::SmallVec;
 use std::collections::HashMap;
 use std::hash::{BuildHasherDefault, Hash, Hasher};
+use std::mem;
 use std::ops::Deref;
 use std::slice::IterMut;
 use std::sync::Arc;
 use string_cache::Atom;
 use traversal::RestyleResult;
 use util::opts;
 
 fn create_common_style_affecting_attributes_from_element<E: TElement>(element: &E)
@@ -435,17 +437,18 @@ impl StyleSharingCandidateCache {
         // These are things we don't check in the candidate match because they
         // are either uncommon or expensive.
         if !relations_are_shareable(&relations) {
             debug!("Failing to insert to the cache: {:?}", relations);
             return;
         }
 
         let node = element.as_node();
-        let style = node.get_existing_style().unwrap();
+        let data = node.borrow_data().unwrap();
+        let style = &data.current_styles().primary;
 
         let box_style = style.get_box();
         if box_style.transition_property_count() > 0 {
             debug!("Failing to insert to the cache: transitions");
             return;
         }
 
         if box_style.animation_name_count() > 0 {
@@ -717,40 +720,41 @@ pub trait ElementMatchMethods : TElement
         for (i, &mut (ref mut candidate, ())) in style_sharing_candidate_cache.iter_mut().enumerate() {
             let sharing_result = self.share_style_with_candidate_if_possible(parent,
                                                                              shared_context,
                                                                              candidate);
             match sharing_result {
                 Ok(shared_style) => {
                     // Yay, cache hit. Share the style.
                     let node = self.as_node();
+                    let mut data = node.begin_styling();
 
                     // 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 node.existing_style_for_restyle_damage(node.get_existing_style().as_ref(), None) {
+                        match node.existing_style_for_restyle_damage(data.previous_styles().map(|x| &x.primary), None) {
                             Some(ref source) => {
                                 <<Self as TElement>::ConcreteNode as TNode>
                                 ::ConcreteRestyleDamage::compute(source, &shared_style)
                             }
                             None => {
                                 <<Self as TElement>::ConcreteNode as TNode>
                                 ::ConcreteRestyleDamage::rebuild_and_reflow()
                             }
                         };
 
                     let restyle_result = if shared_style.get_box().clone_display() == display::T::none {
                         RestyleResult::Stop
                     } else {
                         RestyleResult::Continue
                     };
 
-                    node.set_style(shared_style);
+                    data.finish_styling(NodeStyles::new(shared_style));
 
                     return StyleSharingResult::StyleWasShared(i, damage, restyle_result)
                 }
                 Err(miss) => {
                     debug!("Cache miss: {:?}", miss);
 
                     // Cache miss, let's see what kind of failure to decide
                     // whether we keep trying or not.
@@ -874,98 +878,105 @@ pub trait MatchMethods : TNode {
     unsafe fn cascade_node<'a, Ctx>(&self,
                                     context: &Ctx,
                                     parent: Option<Self>,
                                     applicable_declarations: &ApplicableDeclarations)
                                     -> RestyleResult
         where Ctx: StyleContext<'a>
     {
         // Get our parent's style.
-        let parent_style = parent.as_ref().map(|x| x.get_existing_style().unwrap());
+        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);
 
         // In the case we're styling a text node, we don't need to compute the
         // restyle damage, since it's a subset of the restyle damage of the
         // parent.
         //
         // In Gecko, we're done, we don't need anything else from text nodes.
         //
         // In Servo, this is also true, since text nodes generate UnscannedText
         // fragments, which aren't repairable by incremental layout.
         if self.is_text_node() {
-            self.style_text_node(ComputedValues::style_for_child_text_node(parent_style.as_ref().unwrap()));
-
+            self.style_text_node(ComputedValues::style_for_child_text_node(parent_style.clone().unwrap()));
             return RestyleResult::Continue;
         }
 
+        let mut data = self.begin_styling();
+        let mut new_styles;
+
         let mut applicable_declarations_cache =
             context.local_context().applicable_declarations_cache.borrow_mut();
 
         let (damage, restyle_result) = {
-            // Compute the parameters for the cascade.
-            let mut old_style = self.get_existing_style();
-            let cacheable = match old_style {
-                None => true,
-                Some(ref mut old) => {
-                    // Update animations before the cascade. This may modify
-                    // the value of old_style.
-                    !self.update_animations_for_cascade(context.shared_context(), old)
-                },
+            // Update animations before the cascade. This may modify the value of the old primary
+            // style.
+            let cacheable = data.previous_styles_mut().map_or(true,
+                |x| !self.update_animations_for_cascade(context.shared_context(), &mut x.primary));
+            let shareable = applicable_declarations.normal_shareable;
+            let (old_primary, old_pseudos) = match data.previous_styles_mut() {
+                None => (None, None),
+                Some(x) => (Some(&x.primary), Some(&mut x.pseudos)),
             };
-            let shareable = applicable_declarations.normal_shareable;
 
 
-            let new_style =
+            new_styles = NodeStyles::new(
                 self.cascade_node_pseudo_element(context,
-                                                 parent_style.as_ref(),
-                                                 old_style.as_ref(),
+                                                 parent_style.clone(),
+                                                 old_primary,
                                                  &applicable_declarations.normal,
                                                  &mut applicable_declarations_cache,
                                                  CascadeBooleans {
                                                      shareable: shareable,
                                                      cacheable: cacheable,
                                                      animate: true,
-                                                 });
+                                                 }));
 
             let (damage, restyle_result) =
-                self.compute_damage_and_cascade_pseudos(&new_style, old_style.as_ref(),
+                self.compute_damage_and_cascade_pseudos(old_primary,
+                                                        old_pseudos,
+                                                        &new_styles.primary,
+                                                        &mut new_styles.pseudos,
                                                         context, applicable_declarations,
                                                         &mut applicable_declarations_cache);
 
-            self.set_style(new_style);
-
             self.set_can_be_fragmented(parent.map_or(false, |p| {
                 p.can_be_fragmented() ||
-                parent_style.as_ref().unwrap().is_multicol()
+                parent_style.unwrap().is_multicol()
             }));
 
             (damage, restyle_result)
         };
 
+        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);
 
         restyle_result
     }
 
     fn compute_damage_and_cascade_pseudos<'a, Ctx>(&self,
-                                                   new_style: &Arc<ComputedValues>,
-                                                   old_style: Option<&Arc<ComputedValues>>,
+                                                   old_primary: Option<&Arc<ComputedValues>>,
+                                                   mut old_pseudos: Option<&mut PseudoStyles>,
+                                                   new_primary: &Arc<ComputedValues>,
+                                                   new_pseudos: &mut PseudoStyles,
                                                    context: &Ctx,
                                                    applicable_declarations: &ApplicableDeclarations,
                                                    mut applicable_declarations_cache: &mut ApplicableDeclarationsCache)
                                                    -> (Self::ConcreteRestyleDamage, RestyleResult)
         where Ctx: StyleContext<'a>
     {
         // Here we optimise the case of the style changing but both the
         // previous and the new styles having display: none. In this
         // case, we can always optimize the traversal, regardless of the
         // restyle hint.
-        let this_display = new_style.get_box().clone_display();
+        let this_display = new_primary.get_box().clone_display();
         if this_display == display::T::none {
-            let old_display = old_style.map(|old_style| {
-                old_style.get_box().clone_display()
+            let old_display = old_primary.map(|old| {
+                old.get_box().clone_display()
             });
 
             // If display passed from none to something, then we need to reflow,
             // otherwise, we don't do anything.
             let damage = match old_display {
                 Some(display) if display == this_display => {
                     Self::ConcreteRestyleDamage::empty()
                 }
@@ -976,49 +987,48 @@ pub trait MatchMethods : TNode {
                    this_display, old_display, damage);
 
             return (damage, RestyleResult::Stop);
         }
 
         // Otherwise, we just compute the damage normally, and sum up the damage
         // related to pseudo-elements.
         let mut damage =
-            self.compute_restyle_damage(old_style, new_style, None);
+            self.compute_restyle_damage(old_primary, new_primary, None);
 
         let rebuild_and_reflow =
             Self::ConcreteRestyleDamage::rebuild_and_reflow();
         let no_damage = Self::ConcreteRestyleDamage::empty();
 
-        let mut pseudo_styles = self.take_pseudo_styles();
+        debug_assert!(new_pseudos.is_empty());
         <Self::ConcreteElement as MatchAttr>::Impl::each_eagerly_cascaded_pseudo_element(|pseudo| {
             let applicable_declarations_for_this_pseudo =
                 applicable_declarations.per_pseudo.get(&pseudo).unwrap();
 
             let has_declarations =
                 !applicable_declarations_for_this_pseudo.is_empty();
 
-            // The old entry will be replaced. Remove it from the map but keep
-            // it for analysis.
-            let mut old_pseudo_style = pseudo_styles.remove(&pseudo);
+            // Grab the old pseudo style for analysis.
+            let mut old_pseudo_style = old_pseudos.as_mut().and_then(|x| x.remove(&pseudo));
 
             if has_declarations {
                 // We have declarations, so we need to cascade. Compute parameters.
                 let animate = <Self::ConcreteElement as MatchAttr>::Impl
                                 ::pseudo_is_before_or_after(&pseudo);
                 let cacheable = if animate && old_pseudo_style.is_some() {
                     // 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.as_mut().unwrap())
                 } else {
                     true
                 };
 
                 let new_pseudo_style =
-                    self.cascade_node_pseudo_element(context, Some(new_style),
+                    self.cascade_node_pseudo_element(context, Some(new_primary),
                                                      old_pseudo_style.as_ref(),
                                                      &*applicable_declarations_for_this_pseudo,
                                                      &mut applicable_declarations_cache,
                                                      CascadeBooleans {
                                                          shareable: false,
                                                          cacheable: cacheable,
                                                          animate: animate,
                                                      });
@@ -1028,25 +1038,23 @@ pub trait MatchMethods : TNode {
                     damage = damage | match old_pseudo_style {
                         None => rebuild_and_reflow,
                         Some(ref old) => self.compute_restyle_damage(Some(old), &new_pseudo_style,
                                                                      Some(&pseudo)),
                     };
                 }
 
                 // Insert the new entry into the map.
-                let existing = pseudo_styles.insert(pseudo, new_pseudo_style);
+                let existing = new_pseudos.insert(pseudo, new_pseudo_style);
                 debug_assert!(existing.is_none());
             } else {
                 damage = damage | match old_pseudo_style {
                     Some(_) => rebuild_and_reflow,
                     None => no_damage,
                 }
             }
         });
 
-        self.set_pseudo_styles(pseudo_styles);
-
         (damage, RestyleResult::Continue)
     }
 }
 
 impl<N: TNode> MatchMethods for N {}
--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -244,20 +244,22 @@ fn ensure_node_styled_internal<'a, N, C>
         ensure_node_styled_internal(parent, context, parents_had_display_none);
     }
 
     // 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(ref style) = node.get_existing_style() {
-        if !*parents_had_display_none {
-            *parents_had_display_none = style.get_box().clone_display() == display::T::none;
-            return;
+    if let Some(data) = node.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;
+            }
         }
     }
 
     // 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
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -248,18 +248,19 @@ pub extern "C" fn Servo_StyleSheet_AddRe
 pub extern "C" fn Servo_StyleSheet_Release(sheet: RawServoStyleSheetBorrowed) -> () {
     unsafe { Stylesheet::release(sheet) };
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_ComputedValues_Get(node: RawGeckoNodeBorrowed)
      -> ServoComputedValuesStrong {
     let node = GeckoNode(node);
-    let arc_cv = match node.get_existing_style() {
-        Some(style) => style,
+    let data = node.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())
         },