Bug 1355343: Take all the snapshots into account. r=bholley

I've chosen this approach mainly because there's no other good way to guarantee
the model is correct than holding the snapshots alive until a style refresh.

What I tried before this (storing them in a sort of "immutable element data") is
a pain, since we call into style from the frame constructor and other content
notifications, which makes keeping track of which snapshots should be cleared an
which shouldn't an insane task.

Ideally we'd have a single entry-point for style, but that's not the case right
now, and changing that requires pretty non-trivial changes to the frame
constructor.

MozReview-Commit-ID: FF1KWZv2iBM
Signed-off-by: Emilio Cobos Álvarez <emilio@crisal.io>

15 files changed, 382 insertions, 261 deletions

diff --git a/components/layout_thread/lib.rs b/components/layout_thread/lib.rs
index c6ba5b6d4e6..cf9be917837 100644
--- a/components/layout_thread/lib.rs
+++ b/components/layout_thread/lib.rs
@@ -113,6 +113,7 @@ use style::dom::{ShowSubtree, ShowSubtreeDataAndPrimaryValues, TElement, TNode};
 use style::error_reporting::{NullReporter, RustLogReporter};
 use style::logical_geometry::LogicalPoint;
 use style::media_queries::{Device, MediaList, MediaType};
+use style::selector_parser::SnapshotMap;
 use style::servo::restyle_damage::{REFLOW, REFLOW_OUT_OF_FLOW, REPAINT, REPOSITION, STORE_OVERFLOW};
 use style::shared_lock::{SharedRwLock, SharedRwLockReadGuard, StylesheetGuards};
 use style::stylearc::Arc as StyleArc;
@@ -509,7 +510,8 @@ impl LayoutThread {
     fn build_layout_context<'a>(&self,
                                 guards: StylesheetGuards<'a>,
                                 rw_data: &LayoutThreadData,
-                                request_images: bool)
+                                request_images: bool,
+                                snapshot_map: &'a SnapshotMap)
                                 -> LayoutContext<'a> {
         let thread_local_style_context_creation_data =
             ThreadLocalStyleContextCreationInfo::new(self.new_animations_sender.clone());
@@ -527,6 +529,7 @@ impl LayoutThread {
                 timer: self.timer.clone(),
                 quirks_mode: self.quirks_mode.unwrap(),
                 traversal_flags: TraversalFlags::empty(),
+                snapshot_map: snapshot_map,
             },
             image_cache: self.image_cache.clone(),
             font_cache_thread: Mutex::new(self.font_cache_thread.clone()),
@@ -1111,37 +1114,51 @@ impl LayoutThread {
         }
 
         let restyles = document.drain_pending_restyles();
-        debug!("Draining restyles: {} (needs dirtying? {:?})", restyles.len(), needs_dirtying);
-        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() };
-                }
+        debug!("Draining restyles: {} (needs dirtying? {:?})",
+               restyles.len(), needs_dirtying);
+        let mut map = SnapshotMap::new();
+        let elements_with_snapshot: Vec<_> =
+            restyles
+                .iter()
+                .filter(|r| r.1.snapshot.is_some())
+                .map(|r| r.0)
+                .collect();
+
+        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 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.has_current_styles());
-                let mut restyle_data = style_data.ensure_restyle();
-
-                // Stash the data on the element for processing by the style system.
-                restyle_data.hint = restyle.hint.into();
-                restyle_data.damage = restyle.damage;
-                if let Some(s) = restyle.snapshot {
-                    restyle_data.snapshot.ensure(move || s);
+            // 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 => {
+                    unsafe { el.unset_snapshot_flags() };
+                    continue;
                 }
-                debug!("Noting restyle for {:?}: {:?}", el, restyle_data);
+            };
+
+            if let Some(s) = restyle.snapshot {
+                unsafe { el.set_has_snapshot() };
+                map.insert(el.as_node().opaque(), s);
             }
+
+            let mut style_data = &mut data.base.style_data;
+            let mut restyle_data = style_data.ensure_restyle();
+
+            // Stash the data on the element for processing by the style system.
+            restyle_data.hint.insert(&restyle.hint.into());
+            restyle_data.damage = restyle.damage;
+            debug!("Noting restyle for {:?}: {:?}", el, restyle_data);
         }
 
         // Create a layout context for use throughout the following passes.
-        let mut layout_context = self.build_layout_context(guards.clone(), &*rw_data, true);
+        let mut layout_context =
+            self.build_layout_context(guards.clone(), &*rw_data, true, &map);
 
         // NB: Type inference falls apart here for some reason, so we need to be very verbose. :-(
         let traversal_driver = if self.parallel_flag && self.parallel_traversal.is_some() {
@@ -1152,10 +1169,12 @@ impl LayoutThread {
 
         let traversal = RecalcStyleAndConstructFlows::new(layout_context, traversal_driver);
         let token = {
-            let stylist = &<RecalcStyleAndConstructFlows as
-                            DomTraversal<ServoLayoutElement>>::shared_context(&traversal).stylist;
+            let context = <RecalcStyleAndConstructFlows as
+                           DomTraversal<ServoLayoutElement>>::shared_context(&traversal);
             <RecalcStyleAndConstructFlows as
-             DomTraversal<ServoLayoutElement>>::pre_traverse(element, stylist, TraversalFlags::empty())
+             DomTraversal<ServoLayoutElement>>::pre_traverse(element,
+                                                             context,
+                                                             TraversalFlags::empty())
         };
 
         if token.should_traverse() {
@@ -1192,6 +1211,10 @@ impl LayoutThread {
             self.root_flow = self.try_get_layout_root(element.as_node());
         }
 
+        for element in elements_with_snapshot {
+            unsafe { element.unset_snapshot_flags() }
+        }
+
         layout_context = traversal.destroy();
 
         if opts::get().dump_style_tree {
@@ -1382,7 +1405,11 @@ impl LayoutThread {
                 author: &author_guard,
                 ua_or_user: &ua_or_user_guard,
             };
-            let mut layout_context = self.build_layout_context(guards, &*rw_data, false);
+            let snapshots = SnapshotMap::new();
+            let mut layout_context = self.build_layout_context(guards,
+                                                               &*rw_data,
+                                                               false,
+                                                               &snapshots);
 
             {
                 // Perform an abbreviated style recalc that operates without access to the DOM.
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index 6f65faaed07..31e48b5b695 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -144,29 +144,40 @@ pub struct Node {
 bitflags! {
     #[doc = "Flags for node items."]
     #[derive(JSTraceable, HeapSizeOf)]
-    pub flags NodeFlags: u8 {
+    pub flags NodeFlags: u16 {
         #[doc = "Specifies whether this node is in a document."]
-        const IS_IN_DOC = 0x01,
+        const IS_IN_DOC = 1 << 0,
+
         #[doc = "Specifies whether this node needs style recalc on next reflow."]
-        const HAS_DIRTY_DESCENDANTS = 0x08,
+        const HAS_DIRTY_DESCENDANTS = 1 << 1,
         // 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,
+        const CLICK_IN_PROGRESS = 1 << 2,
         #[doc = "Specifies whether this node is focusable and whether it is supposed \
                  to be reachable with using sequential focus navigation."]
-        const SEQUENTIALLY_FOCUSABLE = 0x20,
+        const SEQUENTIALLY_FOCUSABLE = 1 << 3,
 
         /// Whether any ancestor is a fragmentation container
-        const CAN_BE_FRAGMENTED = 0x40,
+        const CAN_BE_FRAGMENTED = 1 << 4,
+
         #[doc = "Specifies whether this node needs to be dirted when viewport size changed."]
-        const DIRTY_ON_VIEWPORT_SIZE_CHANGE = 0x80,
+        const DIRTY_ON_VIEWPORT_SIZE_CHANGE = 1 << 5,
 
         #[doc = "Specifies whether the parser has set an associated form owner for \
                  this element. Only applicable for form-associatable elements."]
-        const PARSER_ASSOCIATED_FORM_OWNER = 0x90,
+        const PARSER_ASSOCIATED_FORM_OWNER = 1 << 6,
+
+        /// Whether this element has a snapshot stored due to a style or
+        /// attribute change.
+        ///
+        /// See the `style::restyle_hints` module.
+        const HAS_SNAPSHOT = 1 << 7,
+
+        /// Whether this element has already handled the stored snapshot.
+        const HANDLED_SNAPSHOT = 1 << 8,
     }
 }
 
@@ -289,7 +300,9 @@ impl Node {
 
         for node in child.traverse_preorder() {
             // Out-of-document elements never have the descendants flag set.
-            node.set_flag(IS_IN_DOC | HAS_DIRTY_DESCENDANTS, false);
+            node.set_flag(IS_IN_DOC | HAS_DIRTY_DESCENDANTS |
+                          HAS_SNAPSHOT | HANDLED_SNAPSHOT,
+                          false);
         }
         for node in child.traverse_preorder() {
             // This needs to be in its own loop, because unbind_from_tree may
diff --git a/components/script/layout_wrapper.rs b/components/script/layout_wrapper.rs
index 46e5921e3ac..7ae6a7e621e 100644
--- a/components/script/layout_wrapper.rs
+++ b/components/script/layout_wrapper.rs
@@ -39,6 +39,7 @@ 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_IN_DOC};
+use dom::node::{HANDLED_SNAPSHOT, HAS_SNAPSHOT};
 use dom::node::{LayoutNodeHelpers, Node};
 use dom::text::Text;
 use gfx_traits::ByteIndex;
@@ -413,6 +414,18 @@ impl<'le> TElement for ServoLayoutElement<'le> {
         unsafe { self.as_node().node.get_flag(HAS_DIRTY_DESCENDANTS) }
     }
 
+    fn has_snapshot(&self) -> bool {
+        unsafe { self.as_node().node.get_flag(HAS_SNAPSHOT) }
+    }
+
+    fn handled_snapshot(&self) -> bool {
+        unsafe { self.as_node().node.get_flag(HANDLED_SNAPSHOT) }
+    }
+
+    unsafe fn set_handled_snapshot(&self) {
+        self.as_node().node.set_flag(HANDLED_SNAPSHOT, true);
+    }
+
     unsafe fn note_descendants<B: DescendantsBit<Self>>(&self) {
         debug_assert!(self.get_data().is_some());
         style::dom::raw_note_descendants::<Self, B>(*self);
@@ -509,6 +522,14 @@ impl<'le> ServoLayoutElement<'le> {
         }
     }
 
+    pub unsafe fn unset_snapshot_flags(&self) {
+        self.as_node().node.set_flag(HAS_SNAPSHOT | HANDLED_SNAPSHOT, false);
+    }
+
+    pub unsafe fn set_has_snapshot(&self) {
+        self.as_node().node.set_flag(HAS_SNAPSHOT, true);
+    }
+
     // FIXME(bholley): This should be merged with TElement::note_descendants,
     // but that requires re-testing and possibly fixing the broken callers given
     // the FIXME below, which I don't have time to do right now.
diff --git a/components/style/build_gecko.rs b/components/style/build_gecko.rs
index 9b5b1273327..8376587d5ac 100644
--- a/components/style/build_gecko.rs
+++ b/components/style/build_gecko.rs
@@ -305,6 +305,7 @@ mod bindings {
             .include(add_include("mozilla/ComputedTimingFunction.h"))
             .include(add_include("mozilla/Keyframe.h"))
             .include(add_include("mozilla/ServoElementSnapshot.h"))
+            .include(add_include("mozilla/ServoElementSnapshotTable.h"))
             .include(add_include("mozilla/dom/Element.h"))
             .include(add_include("mozilla/dom/NameSpaceConstants.h"))
             .include(add_include("mozilla/LookAndFeel.h"))
@@ -671,6 +672,7 @@ mod bindings {
             "Keyframe",
             "ServoBundledURI",
             "ServoElementSnapshot",
+            "ServoElementSnapshotTable",
             "SheetParsingMode",
             "StyleBasicShape",
             "StyleBasicShapeType",
diff --git a/components/style/context.rs b/components/style/context.rs
index 029f8901aa9..f319c76ba34 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -3,7 +3,6 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! The context within which style is calculated.
-#![deny(missing_docs)]
 
 use animation::{Animation, PropertyAnimation};
 use app_units::Au;
@@ -20,6 +19,7 @@ use font_metrics::FontMetricsProvider;
 use matching::StyleSharingCandidateCache;
 use parking_lot::RwLock;
 #[cfg(feature = "gecko")] use properties::ComputedValues;
+use selector_parser::SnapshotMap;
 use selectors::matching::ElementSelectorFlags;
 #[cfg(feature = "servo")] use servo_config::opts;
 use shared_lock::StylesheetGuards;
@@ -135,6 +135,9 @@ pub struct SharedStyleContext<'a> {
 
     /// Flags controlling how we traverse the tree.
     pub traversal_flags: TraversalFlags,
+
+    /// A map with our snapshots in order to handle restyle hints.
+    pub snapshot_map: &'a SnapshotMap,
 }
 
 impl<'a> SharedStyleContext<'a> {
diff --git a/components/style/data.rs b/components/style/data.rs
index 651f003e4e9..0a1e42d6dd7 100644
--- a/components/style/data.rs
+++ b/components/style/data.rs
@@ -6,19 +6,17 @@
 
 #![deny(missing_docs)]
 
+use context::SharedStyleContext;
 use dom::TElement;
 use properties::ComputedValues;
 use properties::longhands::display::computed_value as display;
 use restyle_hints::{RESTYLE_DESCENDANTS, RESTYLE_LATER_SIBLINGS, RESTYLE_SELF, RestyleHint};
 use rule_tree::StrongRuleNode;
-use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage, Snapshot};
+use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage};
 #[cfg(feature = "servo")] use std::collections::HashMap;
 use std::fmt;
 #[cfg(feature = "servo")] use std::hash::BuildHasherDefault;
-use std::ops::Deref;
 use stylearc::Arc;
-use stylist::Stylist;
-use thread_state;
 use traversal::TraversalFlags;
 
 /// The structure that represents the result of style computation. This is
@@ -199,9 +197,7 @@ impl StoredRestyleHint {
         // In the middle of an animation only restyle, we don't need to
         // propagate any restyle hints, and we need to remove ourselves.
         if traversal_flags.for_animation_only() {
-            if self.0.intersects(RestyleHint::for_animations()) {
-                self.0.remove(RestyleHint::for_animations());
-            }
+            self.0.remove(RestyleHint::for_animations());
             return Self::empty();
         }
 
@@ -275,55 +271,6 @@ impl From<RestyleHint> for StoredRestyleHint {
     }
 }
 
-static NO_SNAPSHOT: Option<Snapshot> = None;
-
-/// We really want to store an Option<Snapshot> here, but we can't drop Gecko
-/// Snapshots off-main-thread. So we make a convenient little wrapper to provide
-/// the semantics of Option<Snapshot>, while deferring the actual drop.
-#[derive(Debug, Default)]
-pub struct SnapshotOption {
-    snapshot: Option<Snapshot>,
-    destroyed: bool,
-}
-
-impl SnapshotOption {
-    /// An empty snapshot.
-    pub fn empty() -> Self {
-        SnapshotOption {
-            snapshot: None,
-            destroyed: false,
-        }
-    }
-
-    /// Destroy this snapshot.
-    pub fn destroy(&mut self) {
-        self.destroyed = true;
-        debug_assert!(self.is_none());
-    }
-
-    /// Ensure a snapshot is available and return a mutable reference to it.
-    pub fn ensure<F: FnOnce() -> Snapshot>(&mut self, create: F) -> &mut Snapshot {
-        debug_assert!(thread_state::get().is_layout());
-        if self.is_none() {
-            self.snapshot = Some(create());
-            self.destroyed = false;
-        }
-
-        self.snapshot.as_mut().unwrap()
-    }
-}
-
-impl Deref for SnapshotOption {
-    type Target = Option<Snapshot>;
-    fn deref(&self) -> &Option<Snapshot> {
-        if self.destroyed {
-            &NO_SNAPSHOT
-        } else {
-            &self.snapshot
-        }
-    }
-}
-
 /// 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.
@@ -350,54 +297,17 @@ pub struct RestyleData {
     /// for Servo for now.
     #[cfg(feature = "gecko")]
     pub damage_handled: RestyleDamage,
-
-    /// An optional snapshot of the original state and attributes of the element,
-    /// from which we may compute additional restyle hints at traversal time.
-    pub snapshot: SnapshotOption,
 }
 
 impl RestyleData {
-    /// Computes the final restyle hint for this element.
-    ///
-    /// This expands the snapshot (if any) into a restyle hint, and handles
-    /// explicit sibling restyle hints from the stored restyle hint.
-    ///
-    /// Returns true if later siblings must be restyled.
-    pub fn compute_final_hint<E: TElement>(&mut self,
-                                           element: E,
-                                           stylist: &Stylist)
-                                           -> bool {
-        let mut hint = self.hint.0;
-
-        if let Some(snapshot) = self.snapshot.as_ref() {
-            hint |= stylist.compute_restyle_hint(&element, snapshot);
-        }
-
-        // If the hint includes a directive for later siblings, strip it out and
-        // notify the caller to modify the base hint for future siblings.
-        let later_siblings = hint.contains(RESTYLE_LATER_SIBLINGS);
-        hint.remove(RESTYLE_LATER_SIBLINGS);
-
-        // Insert the hint, overriding the previous hint. This effectively takes
-        // care of removing the later siblings restyle hint.
-        self.hint = hint.into();
-
-        // Destroy the snapshot.
-        self.snapshot.destroy();
-
-        later_siblings
-    }
-
     /// Returns true if this RestyleData might invalidate the current style.
     pub fn has_invalidations(&self) -> bool {
-        self.hint.has_self_invalidations() ||
-            self.recascade ||
-            self.snapshot.is_some()
+        self.hint.has_self_invalidations() || self.recascade
     }
 
     /// Returns true if this RestyleData might invalidate sibling styles.
     pub fn has_sibling_invalidations(&self) -> bool {
-        self.hint.has_sibling_invalidations() || self.snapshot.is_some()
+        self.hint.has_sibling_invalidations()
     }
 
     /// Returns damage handled.
@@ -452,6 +362,51 @@ pub enum RestyleKind {
 }
 
 impl ElementData {
+    /// Computes the final restyle hint for this element, potentially allocating
+    /// a `RestyleData` if we need to.
+    ///
+    /// This expands the snapshot (if any) into a restyle hint, and handles
+    /// explicit sibling restyle hints from the stored restyle hint.
+    ///
+    /// Returns true if later siblings must be restyled.
+    pub fn compute_final_hint<E: TElement>(
+        &mut self,
+        element: E,
+        context: &SharedStyleContext)
+        -> bool
+    {
+        debug!("compute_final_hint: {:?}, {:?}",
+               element,
+               context.traversal_flags);
+
+        let mut hint = match self.get_restyle() {
+            Some(r) => r.hint.0,
+            None => RestyleHint::empty(),
+        };
+
+        if element.has_snapshot() && !element.handled_snapshot() {
+            hint |= context.stylist.compute_restyle_hint(&element, context.snapshot_map);
+            unsafe { element.set_handled_snapshot() }
+            debug_assert!(element.handled_snapshot());
+        }
+
+        let empty_hint = hint.is_empty();
+
+        // If the hint includes a directive for later siblings, strip it out and
+        // notify the caller to modify the base hint for future siblings.
+        let later_siblings = hint.contains(RESTYLE_LATER_SIBLINGS);
+        hint.remove(RESTYLE_LATER_SIBLINGS);
+
+        // Insert the hint, overriding the previous hint. This effectively takes
+        // care of removing the later siblings restyle hint.
+        if !empty_hint {
+            self.ensure_restyle().hint = hint.into();
+        }
+
+        later_siblings
+    }
+
+
     /// Trivially construct an ElementData.
     pub fn new(existing: Option<ElementStyles>) -> Self {
         ElementData {
@@ -460,22 +415,21 @@ impl ElementData {
         }
     }
 
-    /// Returns true if this element has a computed styled.
+    /// Returns true if this element has a computed style.
     pub fn has_styles(&self) -> bool {
         self.styles.is_some()
     }
 
-    /// Returns true if this element's style is up-to-date and has no potential
-    /// invalidation.
-    pub fn has_current_styles(&self) -> bool {
-        self.has_styles() &&
-            self.restyle.as_ref().map_or(true, |r| !r.has_invalidations())
+    /// Returns whether we have any outstanding style invalidation.
+    pub fn has_invalidations(&self) -> bool {
+        self.restyle.as_ref().map_or(false, |r| r.has_invalidations())
     }
 
     /// Returns the kind of restyling that we're going to need to do on this
     /// element, based of the stored restyle hint.
     pub fn restyle_kind(&self) -> RestyleKind {
-        debug_assert!(!self.has_current_styles(), "Should've stopped earlier");
+        debug_assert!(!self.has_styles() || self.has_invalidations(),
+                      "Should've stopped earlier");
         if !self.has_styles() {
             return RestyleKind::MatchAndCascade;
         }
@@ -527,8 +481,6 @@ impl ElementData {
 
     /// Sets the computed element styles.
     pub fn set_styles(&mut self, styles: ElementStyles) {
-        debug_assert!(self.get_restyle().map_or(true, |r| r.snapshot.is_none()),
-                      "Traversal should have expanded snapshots");
         self.styles = Some(styles);
     }
 
diff --git a/components/style/dom.rs b/components/style/dom.rs
index 7a4fe5d1003..a8c2928b531 100644
--- a/components/style/dom.rs
+++ b/components/style/dom.rs
@@ -385,6 +385,26 @@ pub trait TElement : Eq + PartialEq + Debug + Hash + Sized + Copy + Clone +
     /// the actual restyle traversal.
     fn has_dirty_descendants(&self) -> bool;
 
+    /// Returns whether state or attributes that may change style have changed
+    /// on the element, and thus whether the element has been snapshotted to do
+    /// restyle hint computation.
+    fn has_snapshot(&self) -> bool;
+
+    /// Returns whether the current snapshot if present has been handled.
+    fn handled_snapshot(&self) -> bool;
+
+    /// Flags this element as having handled already its snapshot.
+    unsafe fn set_handled_snapshot(&self);
+
+    /// Returns whether the element's styles are up-to-date.
+    fn has_current_styles(&self, data: &ElementData) -> bool {
+        if self.has_snapshot() && !self.handled_snapshot() {
+            return false;
+        }
+
+        data.has_styles() && !data.has_invalidations()
+    }
+
     /// Flags an element and its ancestors with a given `DescendantsBit`.
     ///
     /// TODO(emilio): We call this conservatively from restyle_element_internal
diff --git a/components/style/gecko/selector_parser.rs b/components/style/gecko/selector_parser.rs
index af7dd323faf..6badfd145b6 100644
--- a/components/style/gecko/selector_parser.rs
+++ b/components/style/gecko/selector_parser.rs
@@ -16,6 +16,8 @@ use std::fmt;
 use std::ptr;
 use string_cache::{Atom, Namespace, WeakAtom, WeakNamespace};
 
+pub use gecko::snapshot::SnapshotMap;
+
 /// A representation of a CSS pseudo-element.
 ///
 /// In Gecko, we represent pseudo-elements as plain `Atom`s.
diff --git a/components/style/gecko/snapshot.rs b/components/style/gecko/snapshot.rs
index c3ce3a5a345..ea4871bc2a7 100644
--- a/components/style/gecko/snapshot.rs
+++ b/components/style/gecko/snapshot.rs
@@ -5,61 +5,60 @@
 //! A gecko snapshot, that stores the element attributes and state before they
 //! change in order to properly calculate restyle hints.
 
+use dom::TElement;
 use element_state::ElementState;
 use gecko::snapshot_helpers;
 use gecko::wrapper::{AttrSelectorHelpers, GeckoElement};
 use gecko_bindings::bindings;
 use gecko_bindings::structs::ServoElementSnapshot;
 use gecko_bindings::structs::ServoElementSnapshotFlags as Flags;
+use gecko_bindings::structs::ServoElementSnapshotTable;
 use restyle_hints::ElementSnapshot;
 use selector_parser::SelectorImpl;
 use selectors::parser::AttrSelector;
-use std::ptr;
 use string_cache::Atom;
 
 /// A snapshot of a Gecko element.
-///
-/// This is really a Gecko type (see `ServoElementSnapshot.h` in Gecko) we wrap
-/// here.
-#[derive(Debug)]
-pub struct GeckoElementSnapshot(bindings::ServoElementSnapshotOwned);
-
-// FIXME(bholley): Add support for *OwnedConst type, and then we get Sync
-// automatically.
-unsafe impl Sync for GeckoElementSnapshot {}
-
-impl Drop for GeckoElementSnapshot {
-    fn drop(&mut self) {
+pub type GeckoElementSnapshot = ServoElementSnapshot;
+
+/// A map from elements to snapshots for Gecko's style back-end.
+pub type SnapshotMap = ServoElementSnapshotTable;
+
+impl SnapshotMap {
+    /// Gets the snapshot for this element, if any.
+    ///
+    /// FIXME(emilio): The transmute() business we do here is kind of nasty, but
+    /// it's a consequence of the map being a OpaqueNode -> Snapshot table in
+    /// Servo and an Element -> Snapshot table in Gecko.
+    ///
+    /// We should be able to make this a more type-safe with type annotations by
+    /// making SnapshotMap a trait and moving the implementations outside, but
+    /// that's a pain because it implies parameterizing SharedStyleContext.
+    pub fn get<E: TElement>(&self, element: &E) -> Option<&GeckoElementSnapshot> {
+        debug_assert!(element.has_snapshot());
+
         unsafe {
-            bindings::Gecko_DropElementSnapshot(ptr::read(&self.0 as *const _));
+            let element =
+                unsafe { ::std::mem::transmute::<&E, &GeckoElement>(element) };
+
+            bindings::Gecko_GetElementSnapshot(self, element.0).as_ref()
         }
     }
 }
 
 impl GeckoElementSnapshot {
-    /// Create a new snapshot of the given element.
-    pub fn new<'le>(el: GeckoElement<'le>) -> Self {
-        unsafe { GeckoElementSnapshot(bindings::Gecko_CreateElementSnapshot(el.0)) }
-    }
-
-    /// Get a mutable reference to the snapshot.
-    pub fn borrow_mut_raw(&mut self) -> bindings::ServoElementSnapshotBorrowedMut {
-        &mut *self.0
-    }
-
-    /// Get the pointer to the actual snapshot.
-    pub fn ptr(&self) -> *const ServoElementSnapshot {
-        &*self.0
-    }
-
     #[inline]
     fn is_html_element_in_html_document(&self) -> bool {
-        unsafe { (*self.0).mIsHTMLElementInHTMLDocument }
+        self.mIsHTMLElementInHTMLDocument
     }
 
     #[inline]
     fn has_any(&self, flags: Flags) -> bool {
-        unsafe { ((*self.0).mContains as u8 & flags as u8) != 0 }
+        (self.mContains as u8 & flags as u8) != 0
+    }
+
+    fn as_ptr(&self) -> *const Self {
+        self
     }
 }
 
@@ -68,7 +67,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
 
     fn match_attr_has(&self, attr: &AttrSelector<SelectorImpl>) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotHasAttr(self.ptr(),
+            bindings::Gecko_SnapshotHasAttr(self,
                                             attr.ns_or_null(),
                                             attr.select_name(self.is_html_element_in_html_document()))
         }
@@ -76,7 +75,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
 
     fn match_attr_equals(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrEquals(self.ptr(),
+            bindings::Gecko_SnapshotAttrEquals(self,
                                                attr.ns_or_null(),
                                                attr.select_name(self.is_html_element_in_html_document()),
                                                value.as_ptr(),
@@ -86,7 +85,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
 
     fn match_attr_equals_ignore_ascii_case(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrEquals(self.ptr(),
+            bindings::Gecko_SnapshotAttrEquals(self,
                                                attr.ns_or_null(),
                                                attr.select_name(self.is_html_element_in_html_document()),
                                                value.as_ptr(),
@@ -95,7 +94,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_includes(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrIncludes(self.ptr(),
+            bindings::Gecko_SnapshotAttrIncludes(self,
                                                  attr.ns_or_null(),
                                                  attr.select_name(self.is_html_element_in_html_document()),
                                                  value.as_ptr())
@@ -103,7 +102,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_dash(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrDashEquals(self.ptr(),
+            bindings::Gecko_SnapshotAttrDashEquals(self,
                                                    attr.ns_or_null(),
                                                    attr.select_name(self.is_html_element_in_html_document()),
                                                    value.as_ptr())
@@ -111,7 +110,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_prefix(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrHasPrefix(self.ptr(),
+            bindings::Gecko_SnapshotAttrHasPrefix(self,
                                                   attr.ns_or_null(),
                                                   attr.select_name(self.is_html_element_in_html_document()),
                                                   value.as_ptr())
@@ -119,7 +118,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_substring(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrHasSubstring(self.ptr(),
+            bindings::Gecko_SnapshotAttrHasSubstring(self,
                                                      attr.ns_or_null(),
                                                      attr.select_name(self.is_html_element_in_html_document()),
                                                      value.as_ptr())
@@ -127,7 +126,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
     }
     fn match_attr_suffix(&self, attr: &AttrSelector<SelectorImpl>, value: &Atom) -> bool {
         unsafe {
-            bindings::Gecko_SnapshotAttrHasSuffix(self.ptr(),
+            bindings::Gecko_SnapshotAttrHasSuffix(self,
                                                   attr.ns_or_null(),
                                                   attr.select_name(self.is_html_element_in_html_document()),
                                                   value.as_ptr())
@@ -138,7 +137,7 @@ impl ::selectors::MatchAttr for GeckoElementSnapshot {
 impl ElementSnapshot for GeckoElementSnapshot {
     fn state(&self) -> Option<ElementState> {
         if self.has_any(Flags::State) {
-            Some(ElementState::from_bits_truncate(unsafe { (*self.0).mState }))
+            Some(ElementState::from_bits_truncate(self.mState))
         } else {
             None
         }
@@ -151,7 +150,7 @@ impl ElementSnapshot for GeckoElementSnapshot {
 
     fn id_attr(&self) -> Option<Atom> {
         let ptr = unsafe {
-            bindings::Gecko_SnapshotAtomAttrValue(self.ptr(),
+            bindings::Gecko_SnapshotAtomAttrValue(self,
                                                   atom!("id").as_ptr())
         };
 
@@ -163,7 +162,7 @@ impl ElementSnapshot for GeckoElementSnapshot {
     }
 
     fn has_class(&self, name: &Atom) -> bool {
-        snapshot_helpers::has_class(self.ptr(),
+        snapshot_helpers::has_class(self.as_ptr(),
                                     name,
                                     bindings::Gecko_SnapshotClassOrClassList)
     }
@@ -171,7 +170,7 @@ impl ElementSnapshot for GeckoElementSnapshot {
     fn each_class<F>(&self, callback: F)
         where F: FnMut(&Atom)
     {
-        snapshot_helpers::each_class(self.ptr(),
+        snapshot_helpers::each_class(self.as_ptr(),
                                      callback,
                                      bindings::Gecko_SnapshotClassOrClassList)
     }
diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs
index 17ee344bbbe..41a83526fd6 100644
--- a/components/style/gecko/wrapper.rs
+++ b/components/style/gecko/wrapper.rs
@@ -62,7 +62,7 @@ use properties::{Importance, PropertyDeclaration, PropertyDeclarationBlock};
 use properties::animated_properties::{AnimationValue, AnimationValueMap, TransitionProperty};
 use properties::style_structs::Font;
 use rule_tree::CascadeLevel as ServoCascadeLevel;
-use selector_parser::{ElementExt, Snapshot};
+use selector_parser::ElementExt;
 use selectors::Element;
 use selectors::matching::{ElementSelectorFlags, StyleRelations};
 use selectors::parser::{AttrSelector, NamespaceConstraint};
@@ -363,6 +363,10 @@ impl<'le> GeckoElement<'le> {
     /// Clear the element data for a given element.
     pub fn clear_data(&self) {
         let ptr = self.0.mServoData.get();
+        unsafe {
+            self.unset_flags(ELEMENT_HAS_SNAPSHOT as u32 |
+                             ELEMENT_HANDLED_SNAPSHOT as u32);
+        }
         if !ptr.is_null() {
             debug!("Dropping ElementData for {:?}", self);
             let data = unsafe { Box::from_raw(self.0.mServoData.get()) };
@@ -391,11 +395,6 @@ impl<'le> GeckoElement<'le> {
             },
         }
     }
-
-    /// Creates a blank snapshot for this element.
-    pub fn create_snapshot(&self) -> Snapshot {
-        Snapshot::new(*self)
-    }
 }
 
 /// Converts flags from the layout used by rust-selectors to the layout used
@@ -591,6 +590,19 @@ impl<'le> TElement for GeckoElement<'le> {
         }
     }
 
+    fn has_snapshot(&self) -> bool {
+        self.flags() & (ELEMENT_HAS_SNAPSHOT as u32) != 0
+    }
+
+    fn handled_snapshot(&self) -> bool {
+        self.flags() & (ELEMENT_HANDLED_SNAPSHOT as u32) != 0
+    }
+
+    unsafe fn set_handled_snapshot(&self) {
+        debug_assert!(self.get_data().is_some());
+        self.set_flags(ELEMENT_HANDLED_SNAPSHOT as u32)
+    }
+
     fn has_dirty_descendants(&self) -> bool {
         self.flags() & (ELEMENT_HAS_DIRTY_DESCENDANTS_FOR_SERVO as u32) != 0
     }
diff --git a/components/style/matching.rs b/components/style/matching.rs
index 8da1192d4d3..0e1f94c9327 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -196,7 +196,7 @@ fn element_matches_candidate<E: TElement>(element: &E,
     }
 
     let data = candidate_element.borrow_data().unwrap();
-    debug_assert!(data.has_current_styles());
+    debug_assert!(element.has_current_styles(&data));
     let current_styles = data.styles();
 
     debug!("Sharing style between {:?} and {:?}", element, candidate_element);
@@ -432,7 +432,8 @@ trait PrivateMatchMethods: TElement {
                     // construct a frame for some small piece of newly-added
                     // content in order to do something specific with that frame,
                     // but not wanting to flush all of layout).
-                    debug_assert!(cfg!(feature = "gecko") || d.has_current_styles());
+                    debug_assert!(cfg!(feature = "gecko") ||
+                                  parent_el.unwrap().has_current_styles(d));
                     d.styles().primary.values()
                 });
 
diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs
index 1ac3774a66f..343c601c26f 100644
--- a/components/style/restyle_hints.rs
+++ b/components/style/restyle_hints.rs
@@ -13,7 +13,7 @@ use element_state::*;
 use gecko_bindings::structs::nsRestyleHint;
 #[cfg(feature = "servo")]
 use heapsize::HeapSizeOf;
-use selector_parser::{AttrValue, NonTSPseudoClass, Snapshot, SelectorImpl};
+use selector_parser::{AttrValue, NonTSPseudoClass, SelectorImpl, Snapshot, SnapshotMap};
 use selectors::{Element, MatchAttr};
 use selectors::matching::{ElementSelectorFlags, StyleRelations};
 use selectors::matching::matches_selector;
@@ -126,6 +126,7 @@ impl RestyleHint {
 impl From<nsRestyleHint> for RestyleHint {
     fn from(raw: nsRestyleHint) -> Self {
         let raw_bits: u32 = raw.0;
+
         // 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() {
@@ -193,20 +194,29 @@ struct ElementWrapper<'a, E>
     where E: TElement,
 {
     element: E,
-    snapshot: Option<&'a Snapshot>,
+    snapshot_map: &'a SnapshotMap,
 }
 
 impl<'a, E> ElementWrapper<'a, E>
     where E: TElement,
 {
-    /// Trivially constructs an `ElementWrapper` without a snapshot.
-    pub fn new(el: E) -> ElementWrapper<'a, E> {
-        ElementWrapper { element: el, snapshot: None }
+    /// Trivially constructs an `ElementWrapper`.
+    fn new(el: E, snapshot_map: &'a SnapshotMap) -> Self {
+        ElementWrapper { element: el, snapshot_map: snapshot_map }
     }
 
-    /// Trivially constructs an `ElementWrapper` with a snapshot.
-    pub fn new_with_snapshot(el: E, snapshot: &'a Snapshot) -> ElementWrapper<'a, E> {
-        ElementWrapper { element: el, snapshot: Some(snapshot) }
+    /// Gets the snapshot associated with this element, if any.
+    ///
+    /// TODO(emilio): If the hash table lookup happens to appear in profiles, we
+    /// can cache the snapshot in a RefCell<&'a Snapshot>.
+    fn snapshot(&self) -> Option<&'a Snapshot> {
+        if !self.element.has_snapshot() {
+            return None
+        }
+
+        let snapshot = self.snapshot_map.get(&self.element);
+        debug_assert!(snapshot.is_some(), "has_snapshot lied!");
+        snapshot
     }
 }
 
@@ -216,7 +226,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     type Impl = SelectorImpl;
 
     fn match_attr_has(&self, attr: &AttrSelector<SelectorImpl>) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_has(attr),
             _   => self.element.match_attr_has(attr)
@@ -226,7 +236,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     fn match_attr_equals(&self,
                          attr: &AttrSelector<SelectorImpl>,
                          value: &AttrValue) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_equals(attr, value),
             _   => self.element.match_attr_equals(attr, value)
@@ -236,7 +246,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     fn match_attr_equals_ignore_ascii_case(&self,
                                            attr: &AttrSelector<SelectorImpl>,
                                            value: &AttrValue) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_equals_ignore_ascii_case(attr, value),
             _   => self.element.match_attr_equals_ignore_ascii_case(attr, value)
@@ -246,7 +256,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     fn match_attr_includes(&self,
                            attr: &AttrSelector<SelectorImpl>,
                            value: &AttrValue) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_includes(attr, value),
             _   => self.element.match_attr_includes(attr, value)
@@ -256,7 +266,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     fn match_attr_dash(&self,
                        attr: &AttrSelector<SelectorImpl>,
                        value: &AttrValue) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_dash(attr, value),
             _   => self.element.match_attr_dash(attr, value)
@@ -266,7 +276,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     fn match_attr_prefix(&self,
                          attr: &AttrSelector<SelectorImpl>,
                          value: &AttrValue) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_prefix(attr, value),
             _   => self.element.match_attr_prefix(attr, value)
@@ -276,7 +286,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     fn match_attr_substring(&self,
                             attr: &AttrSelector<SelectorImpl>,
                             value: &AttrValue) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_substring(attr, value),
             _   => self.element.match_attr_substring(attr, value)
@@ -286,7 +296,7 @@ impl<'a, E> MatchAttr for ElementWrapper<'a, E>
     fn match_attr_suffix(&self,
                          attr: &AttrSelector<SelectorImpl>,
                          value: &AttrValue) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.match_attr_suffix(attr, value),
             _   => self.element.match_attr_suffix(attr, value)
@@ -322,7 +332,7 @@ impl<'a, E> Element for ElementWrapper<'a, E>
                                                           relations,
                                                           &mut |_, _| {})
         }
-        match self.snapshot.and_then(|s| s.state()) {
+        match self.snapshot().and_then(|s| s.state()) {
             Some(snapshot_state) => snapshot_state.contains(flag),
             None => {
                 self.element.match_non_ts_pseudo_class(pseudo_class,
@@ -333,23 +343,28 @@ impl<'a, E> Element for ElementWrapper<'a, E>
     }
 
     fn parent_element(&self) -> Option<Self> {
-        self.element.parent_element().map(ElementWrapper::new)
+        self.element.parent_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
     }
 
     fn first_child_element(&self) -> Option<Self> {
-        self.element.first_child_element().map(ElementWrapper::new)
+        self.element.first_child_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
     }
 
     fn last_child_element(&self) -> Option<Self> {
-        self.element.last_child_element().map(ElementWrapper::new)
+        self.element.last_child_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
     }
 
     fn prev_sibling_element(&self) -> Option<Self> {
-        self.element.prev_sibling_element().map(ElementWrapper::new)
+        self.element.prev_sibling_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
     }
 
     fn next_sibling_element(&self) -> Option<Self> {
-        self.element.next_sibling_element().map(ElementWrapper::new)
+        self.element.next_sibling_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
     }
 
     fn is_html_element_in_html_document(&self) -> bool {
@@ -365,7 +380,7 @@ impl<'a, E> Element for ElementWrapper<'a, E>
     }
 
     fn get_id(&self) -> Option<Atom> {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.id_attr(),
             _   => self.element.get_id()
@@ -373,7 +388,7 @@ impl<'a, E> Element for ElementWrapper<'a, E>
     }
 
     fn has_class(&self, name: &Atom) -> bool {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.has_class(name),
             _   => self.element.has_class(name)
@@ -390,7 +405,7 @@ impl<'a, E> Element for ElementWrapper<'a, E>
 
     fn each_class<F>(&self, callback: F)
         where F: FnMut(&Atom) {
-        match self.snapshot {
+        match self.snapshot() {
             Some(snapshot) if snapshot.has_attrs()
                 => snapshot.each_class(callback),
             _   => self.element.each_class(callback)
@@ -606,13 +621,21 @@ impl DependencySet {
     /// explained in the rest of the documentation.
     pub fn compute_hint<E>(&self,
                            el: &E,
-                           snapshot: &Snapshot)
+                           snapshots: &SnapshotMap)
                            -> RestyleHint
         where E: TElement + Clone,
     {
+        debug_assert!(el.has_snapshot(), "Shouldn't be here!");
+        let snapshot_el = ElementWrapper::new(el.clone(), snapshots);
+
+        let snapshot =
+            snapshot_el.snapshot().expect("has_snapshot lied so badly");
+
         let current_state = el.get_state();
-        let state_changes = snapshot.state()
-                                    .map_or_else(ElementState::empty, |old_state| current_state ^ old_state);
+        let state_changes =
+            snapshot.state()
+                .map_or_else(ElementState::empty,
+                             |old_state| current_state ^ old_state);
         let attrs_changed = snapshot.has_attrs();
 
         if state_changes.is_empty() && !attrs_changed {
@@ -620,7 +643,6 @@ impl DependencySet {
         }
 
         let mut hint = RestyleHint::empty();
-        let snapshot_el = ElementWrapper::new_with_snapshot(el.clone(), snapshot);
 
         // Compute whether the snapshot has any different id or class attributes
         // from the element. If it does, we need to pass those to the lookup, so
@@ -637,12 +659,14 @@ impl DependencySet {
         }
 
         self.0.lookup_with_additional(*el, additional_id, &additional_classes, &mut |dep| {
-            if !dep.sensitivities.sensitive_to(attrs_changed, state_changes) || hint.contains(dep.hint) {
+            if !dep.sensitivities.sensitive_to(attrs_changed, state_changes) ||
+               hint.contains(dep.hint) {
                 return true;
             }
 
-            // We can ignore the selector flags, since they would have already been set during
-            // original matching for any element that might change its matching behavior here.
+            // We can ignore the selector flags, since they would have already
+            // been set during original matching for any element that might
+            // change its matching behavior here.
             let matched_then =
                 matches_selector(&dep.selector, &snapshot_el, None,
                                  &mut StyleRelations::empty(),
@@ -658,8 +682,8 @@ impl DependencySet {
             !hint.is_all()
         });
 
-        debug!("Calculated restyle hint: {:?}. (Element={:?}, State={:?}, Snapshot={:?}, {} Deps)",
-               hint, el, current_state, snapshot, self.len());
+        debug!("Calculated restyle hint: {:?} for {:?}. (State={:?}, {} Deps)",
+               hint, el, current_state, self.len());
         trace!("Deps: {:?}", self);
 
         hint
diff --git a/components/style/servo/selector_parser.rs b/components/style/servo/selector_parser.rs
index 0335b249cb1..d81e14235a2 100644
--- a/components/style/servo/selector_parser.rs
+++ b/components/style/servo/selector_parser.rs
@@ -9,7 +9,9 @@
 use {Atom, Prefix, Namespace, LocalName};
 use attr::{AttrIdentifier, AttrValue};
 use cssparser::{Parser as CssParser, ToCss, serialize_identifier};
+use dom::{OpaqueNode, TElement, TNode};
 use element_state::ElementState;
+use fnv::FnvHashMap;
 use restyle_hints::ElementSnapshot;
 use selector_parser::{ElementExt, PseudoElementCascadeType, SelectorParser};
 use selectors::{Element, MatchAttrGeneric};
@@ -20,6 +22,7 @@ use std::borrow::Cow;
 use std::fmt;
 use std::fmt::Debug;
 use std::mem;
+use std::ops::{Deref, DerefMut};
 
 /// A pseudo-element, both public and private.
 ///
@@ -448,6 +451,36 @@ impl SelectorImpl {
     }
 }
 
+/// A map from elements to snapshots for the Servo style back-end.
+#[derive(Debug)]
+pub struct SnapshotMap(FnvHashMap<OpaqueNode, ServoElementSnapshot>);
+
+impl SnapshotMap {
+    /// Create a new empty `SnapshotMap`.
+    pub fn new() -> Self {
+        SnapshotMap(FnvHashMap::default())
+    }
+
+    /// Get a snapshot given an element.
+    pub fn get<T: TElement>(&self, el: &T) -> Option<&ServoElementSnapshot> {
+        self.0.get(&el.as_node().opaque())
+    }
+}
+
+impl Deref for SnapshotMap {
+    type Target = FnvHashMap<OpaqueNode, ServoElementSnapshot>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl DerefMut for SnapshotMap {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
 /// Servo's version of an element snapshot.
 #[derive(Debug)]
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index 28d05589bbf..1f2dee79ae3 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -22,7 +22,7 @@ use properties::INHERIT_ALL;
 use properties::PropertyDeclarationBlock;
 use restyle_hints::{RestyleHint, DependencySet};
 use rule_tree::{CascadeLevel, RuleTree, StrongRuleNode, StyleSource};
-use selector_parser::{SelectorImpl, PseudoElement, Snapshot};
+use selector_parser::{SelectorImpl, PseudoElement, SnapshotMap};
 use selectors::Element;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{AFFECTED_BY_STYLE_ATTRIBUTE, AFFECTED_BY_PRESENTATIONAL_HINTS};
@@ -894,16 +894,16 @@ impl Stylist {
         results
     }
 
-    /// Given an element, and a snapshot that represents a previous state of the
-    /// element, compute the appropriate restyle hint, that is, the kind of
+    /// Given an element, and a snapshot table that represents a previous state
+    /// of the tree, compute the appropriate restyle hint, that is, the kind of
     /// restyle we need to do.
     pub fn compute_restyle_hint<E>(&self,
                                    element: &E,
-                                   snapshot: &Snapshot)
+                                   snapshots: &SnapshotMap)
                                    -> RestyleHint
         where E: TElement,
     {
-        self.dependencies.compute_hint(element, snapshot)
+        self.dependencies.compute_hint(element, snapshots)
     }
 
     /// Computes styles for a given declaration with parent_style.
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index 831a9454a62..44816c7a985 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -13,7 +13,6 @@ use restyle_hints::{RESTYLE_DESCENDANTS, RESTYLE_SELF};
 use selector_parser::RestyleDamage;
 #[cfg(feature = "servo")] use servo_config::opts;
 use std::borrow::BorrowMut;
-use stylist::Stylist;
 
 /// A per-traversal-level chunk of data. This is sent down by the traversal, and
 /// currently only holds the dom depth for the bloom filter.
@@ -200,7 +199,9 @@ pub trait DomTraversal<E: TElement> : Sync {
     /// appended children without restyling the parent.
     /// If traversal_flag::ANIMATION_ONLY is specified, style only elements for
     /// animations.
-    fn pre_traverse(root: E, stylist: &Stylist, traversal_flags: TraversalFlags)
+    fn pre_traverse(root: E,
+                    shared_context: &SharedStyleContext,
+                    traversal_flags: TraversalFlags)
                     -> PreTraverseToken
     {
         debug_assert!(!(traversal_flags.for_reconstruct() &&
@@ -226,14 +227,12 @@ pub trait DomTraversal<E: TElement> : Sync {
         // Expanding snapshots here may create a LATER_SIBLINGS restyle hint, which
         // we propagate to the next sibling element.
         if let Some(mut data) = root.mutate_data() {
-            if let Some(r) = data.get_restyle_mut() {
-                let later_siblings = r.compute_final_hint(root, stylist);
-                if later_siblings {
-                    if let Some(next) = root.next_sibling_element() {
-                        if let Some(mut next_data) = next.mutate_data() {
-                            let hint = StoredRestyleHint::subtree_and_later_siblings();
-                            next_data.ensure_restyle().hint.insert(&hint);
-                        }
+            let later_siblings = data.compute_final_hint(root, shared_context);
+            if later_siblings {
+                if let Some(next) = root.next_sibling_element() {
+                    if let Some(mut next_data) = next.mutate_data() {
+                        let hint = StoredRestyleHint::subtree_and_later_siblings();
+                        next_data.ensure_restyle().hint.insert(&hint);
                     }
                 }
             }
@@ -375,6 +374,7 @@ pub trait DomTraversal<E: TElement> : Sync {
             return true;
         }
 
+        trace!("{:?} doesn't need traversal", el);
         false
     }
 
@@ -390,7 +390,7 @@ pub trait DomTraversal<E: TElement> : Sync {
                                 log: LogBehavior) -> bool
     {
         // See the comment on `cascade_node` for why we allow this on Gecko.
-        debug_assert!(cfg!(feature = "gecko") || parent_data.has_current_styles());
+        debug_assert!(cfg!(feature = "gecko") || parent.has_current_styles(parent_data));
 
         // If the parent computed display:none, we don't style the subtree.
         if parent_data.styles().is_display_none() {
@@ -597,11 +597,13 @@ pub fn recalc_style_at<E, D>(traversal: &D,
 {
     context.thread_local.begin_element(element, &data);
     context.thread_local.statistics.elements_traversed += 1;
+    debug_assert!(!element.has_snapshot() || element.handled_snapshot(),
+                  "Should've handled snapshots here already");
     debug_assert!(data.get_restyle().map_or(true, |r| {
-        r.snapshot.is_none() && !r.has_sibling_invalidations()
+        !r.has_sibling_invalidations()
     }), "Should've computed the final hint and handled later_siblings already");
 
-    let compute_self = !data.has_current_styles();
+    let compute_self = !element.has_current_styles(data);
     let mut inherited_style_changed = false;
 
     debug!("recalc_style_at: {:?} (compute_self={:?}, dirty_descendants={:?}, data={:?})",
@@ -613,9 +615,9 @@ pub fn recalc_style_at<E, D>(traversal: &D,
 
         // 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.styles().is_display_none();
-        if display_none {
-            debug!("New element style is display:none - clearing data from descendants.");
+        if data.styles().is_display_none() {
+            debug!("{:?} style is display:none - clearing data from descendants.",
+                   element);
             clear_descendant_data(element, &|e| unsafe { D::clear_element_data(&e) });
         }
 
@@ -636,15 +638,15 @@ pub fn recalc_style_at<E, D>(traversal: &D,
             r.hint.propagate(&context.shared.traversal_flags)
         },
     };
-    debug_assert!(data.has_current_styles() ||
-                  context.shared.traversal_flags.for_animation_only(),
-                  "Should have computed style or haven't yet valid computed \
-                   style in case of animation-only restyle");
     trace!("propagated_hint={:?}, inherited_style_changed={:?}, \
             is_display_none={:?}, implementing_pseudo={:?}",
            propagated_hint, inherited_style_changed,
            data.styles().is_display_none(),
            element.implemented_pseudo_element());
+    debug_assert!(element.has_current_styles(data) ||
+                  context.shared.traversal_flags.for_animation_only(),
+                  "Should have computed style or haven't yet valid computed \
+                   style in case of animation-only restyle");
 
     let has_dirty_descendants_for_this_restyle =
         if context.shared.traversal_flags.for_animation_only() {
@@ -779,6 +781,18 @@ fn preprocess_children<E, D>(traversal: &D,
             continue;
         }
 
+        // Handle element snapshots and sibling restyle hints.
+        //
+        // NB: This will be a no-op if there's no restyle data and no snapshot.
+        let later_siblings =
+            child_data.compute_final_hint(child, traversal.shared_context());
+
+        trace!(" > {:?} -> {:?} + {:?}, later_siblings: {:?}",
+               child,
+               child_data.get_restyle().map(|r| &r.hint),
+               propagated_hint,
+               later_siblings);
+
         // If the child doesn't have pre-existing RestyleData and we don't have
         // any reason to create one, avoid the useless allocation and move on to
         // the next child.
@@ -786,6 +800,7 @@ fn preprocess_children<E, D>(traversal: &D,
            damage_handled.is_empty() && !child_data.has_restyle() {
             continue;
         }
+
         let mut restyle_data = child_data.ensure_restyle();
 
         // Propagate the parent and sibling restyle hint.
@@ -793,11 +808,6 @@ fn preprocess_children<E, D>(traversal: &D,
             restyle_data.hint.insert(&propagated_hint);
         }
 
-        // Handle element snapshots and sibling restyle hints.
-        let stylist = &traversal.shared_context().stylist;
-        let later_siblings = restyle_data.compute_final_hint(child, stylist);
-        trace!(" > {:?} -> {:?}, later_siblings: {:?}",
-               child, restyle_data.hint, later_siblings);
         if later_siblings {
             propagated_hint.insert(&(RESTYLE_SELF | RESTYLE_DESCENDANTS).into());
         }
@@ -805,9 +815,11 @@ fn preprocess_children<E, D>(traversal: &D,
         // Store the damage already handled by ancestors.
         restyle_data.set_damage_handled(damage_handled);
 
-        // If properties that we inherited from the parent changed, we need to recascade.
+        // If properties that we inherited from the parent changed, we need to
+        // recascade.
         //
-        // FIXME(bholley): Need to handle explicitly-inherited reset properties somewhere.
+        // FIXME(bholley): Need to handle explicitly-inherited reset properties
+        // somewhere.
         if parent_inherited_style_changed {
             restyle_data.recascade = true;
         }