--- a/dom/events/EventStates.h
+++ b/dom/events/EventStates.h
@@ -7,27 +7,30 @@
 #ifndef mozilla_EventStates_h_
 #define mozilla_EventStates_h_
 
 #include "mozilla/Attributes.h"
 #include "nsDebug.h"
 
 namespace mozilla {
 
+#define NS_EVENT_STATE_HIGHEST_SERVO_BIT 6
+
 /**
  * EventStates is the class used to represent the event states of nsIContent
  * instances. These states are calculated by IntrinsicState() and
  * ContentStatesChanged() has to be called when one of them changes thus
  * informing the layout/style engine of the change.
  * Event states are associated with pseudo-classes.
  */
 class EventStates
 {
 public:
   typedef uint64_t InternalType;
+  typedef uint8_t ServoType;
 
   constexpr EventStates()
     : mStates(0)
   {
   }
 
   // NOTE: the ideal scenario would be to have the default constructor public
   // setting mStates to 0 and this constructor (without = 0) private.
@@ -150,16 +153,23 @@ public:
   }
 
   // We only need that method for inDOMUtils::GetContentState.
   // If inDOMUtils::GetContentState is removed, this method should be removed.
   InternalType GetInternalValue() const {
     return mStates;
   }
 
+  /**
+   * Method used to get the appropriate state representation for servo.
+   */
+  ServoType ServoValue() const {
+    return mStates & ((1 << (NS_EVENT_STATE_HIGHEST_SERVO_BIT + 1)) - 1);
+  }
+
 private:
   InternalType mStates;
 };
 
 } // namespace mozilla
 
 /**
  * The following macros are creating EventStates instance with different
@@ -195,20 +205,21 @@ private:
 #define NS_EVENT_STATE_ENABLED       NS_DEFINE_EVENT_STATE_MACRO(3)
 // Content is disabled.
 #define NS_EVENT_STATE_DISABLED      NS_DEFINE_EVENT_STATE_MACRO(4)
 // Content is checked.
 #define NS_EVENT_STATE_CHECKED       NS_DEFINE_EVENT_STATE_MACRO(5)
 // Content is in the indeterminate state.
 #define NS_EVENT_STATE_INDETERMINATE NS_DEFINE_EVENT_STATE_MACRO(6)
 
-#define NS_EVENT_STATE_HIGHEST_SERVO_BIT 6
-
 /*
  * Bits below here do not have Servo-related ordering constraints.
+ *
+ * Remember to change NS_EVENT_STATE_HIGHEST_SERVO_BIT at the top of the file if
+ * this changes!
  */
 
 // Drag is hovering over content.
 #define NS_EVENT_STATE_DRAGOVER      NS_DEFINE_EVENT_STATE_MACRO(7)
 // Content is URL's target (ref).
 #define NS_EVENT_STATE_URLTARGET     NS_DEFINE_EVENT_STATE_MACRO(8)
 // Content is required.
 #define NS_EVENT_STATE_REQUIRED      NS_DEFINE_EVENT_STATE_MACRO(9)

--- a/layout/base/ServoRestyleManager.cpp
+++ b/layout/base/ServoRestyleManager.cpp
@@ -12,30 +12,35 @@ using namespace mozilla::dom;
 namespace mozilla {
 
 ServoRestyleManager::ServoRestyleManager(nsPresContext* aPresContext)
   : RestyleManagerBase(aPresContext)
 {
 }
 
 /* static */ void
-ServoRestyleManager::DirtyTree(nsIContent* aContent)
+ServoRestyleManager::DirtyTree(nsIContent* aContent, bool aIncludingRoot)
 {
-  if (aContent->IsDirtyForServo()) {
-    return;
+  if (aIncludingRoot) {
+    // XXX: This can in theory leave nodes not dirty, but in practice this is not
+    // a problem, at least for now, since right now element dirty implies
+    // descendants dirty. Remove this early return if this ever changes.
+    if (aContent->IsDirtyForServo()) {
+      return;
+    }
+
+    aContent->SetIsDirtyForServo();
   }
 
-  aContent->SetIsDirtyForServo();
-
   FlattenedChildIterator it(aContent);
 
   nsIContent* n = it.GetNextChild();
   bool hadChildren = bool(n);
   for ( ; n; n = it.GetNextChild()) {
-    DirtyTree(n);
+    DirtyTree(n, true);
   }
 
   if (hadChildren) {
     aContent->SetHasDirtyDescendantsForServo();
   }
 }
 
 void
@@ -43,39 +48,49 @@ ServoRestyleManager::PostRestyleEvent(El
                                       nsRestyleHint aRestyleHint,
                                       nsChangeHint aMinChangeHint)
 {
   if (MOZ_UNLIKELY(IsDisconnected()) ||
       MOZ_UNLIKELY(PresContext()->PresShell()->IsDestroying())) {
     return;
   }
 
-  if (aRestyleHint == 0 && !aMinChangeHint) {
-    // Nothing to do here
-    return;
-  }
+  // NOTE: We defer the processing of restyle/change hints until
+  // ProcessPendingRestyles.
+  //
+  // This snapshot effectively stores nothing (at least yet), except the
+  // restyle/change hint.
+  //
+  // TODO: we could do some space optimisations here it seems, though I don't
+  // expect this path to be really hot.
+  bool needsRestyle = false;
 
-  nsIPresShell* presShell = PresContext()->PresShell();
-  if (!ObservingRefreshDriver()) {
-    SetObservingRefreshDriver(PresContext()->RefreshDriver()->
-        AddStyleFlushObserver(presShell));
+  if (aRestyleHint || aMinChangeHint) {
+    AddElementSnapshot(aElement, ServoElementSnapshot::Flags::No,
+                       aRestyleHint, aMinChangeHint);
+    needsRestyle = true;
+  } else {
+    // Note that we could have been called just after adding an element to the
+    // table, for example.
+    //
+    // Other way to structure this would be to duplicate the logic in
+    // AddElementSnapshot, at the (very minor) cost of possibly doing things
+    // twice.
+    needsRestyle = HasPendingRestyles();
   }
 
-  // Propagate the IS_DIRTY flag down the tree.
-  DirtyTree(aElement);
+  if (needsRestyle) {
+    nsIPresShell* presShell = PresContext()->PresShell();
+    if (!ObservingRefreshDriver()) {
+      SetObservingRefreshDriver(PresContext()->RefreshDriver()->
+          AddStyleFlushObserver(presShell));
+    }
 
-  // Propagate the HAS_DIRTY_DESCENDANTS flag to the root.
-  nsINode* cur = aElement;
-  while ((cur = cur->GetParentNode())) {
-    if (cur->HasDirtyDescendantsForServo())
-      break;
-    cur->SetHasDirtyDescendantsForServo();
+    presShell->GetDocument()->SetNeedStyleFlush();
   }
-
-  presShell->GetDocument()->SetNeedStyleFlush();
 }
 
 void
 ServoRestyleManager::PostRestyleEventForLazyConstruction()
 {
   NS_ERROR("stylo: ServoRestyleManager::PostRestyleEventForLazyConstruction not implemented");
 }
 
@@ -132,32 +147,92 @@ ServoRestyleManager::RecreateStyleContex
     FlattenedChildIterator it(aContent);
     for (nsIContent* n = it.GetNextChild(); n; n = it.GetNextChild()) {
       RecreateStyleContexts(n, primaryFrame->StyleContext(), aStyleSet);
     }
     aContent->UnsetFlags(NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO);
   }
 }
 
+static void
+MarkParentsAsHavingDirtyDescendants(Element* aElement)
+{
+  nsINode* cur = aElement;
+  while ((cur = cur->GetParentNode())) {
+    if (cur->HasDirtyDescendantsForServo()) {
+      break;
+    }
+
+    cur->SetHasDirtyDescendantsForServo();
+  }
+}
+
+void
+ServoRestyleManager::NoteRestyleHint(Element* aElement, nsRestyleHint aHint)
+{
+  if (aHint & eRestyle_Self) {
+    aElement->SetIsDirtyForServo();
+    MarkParentsAsHavingDirtyDescendants(aElement);
+
+    // XXX Self must imply Subtree, at least for Servo, because of style
+    // structs inheritance. Would that be taken care by the SetStyleContext
+    // call?
+    aHint |= eRestyle_Subtree;
+    // MarkParentsAsHavingDirtyDescendants(aElement);
+  }
+
+  if (aHint & eRestyle_Subtree) {
+    DirtyTree(aElement, /* aIncludingRoot = */ false);
+    MarkParentsAsHavingDirtyDescendants(aElement);
+  }
+
+  if (aHint & eRestyle_LaterSiblings) {
+    for (nsINode* cur = aElement->GetNextSibling(); cur; cur = cur->GetNextSibling()) {
+      if (cur->IsContent()) {
+        DirtyTree(cur->AsContent(), /* aIncludingRoot = */ true);
+      }
+    }
+  }
+
+  // TODO: detect restyle for animations/transitions/etc, and act properly.
+  //
+  // The cascade levels there are going to be fun, if we keep the actual
+  // mechanism.
+}
+
 void
 ServoRestyleManager::ProcessPendingRestyles()
 {
   if (!HasPendingRestyles()) {
     return;
   }
   ServoStyleSet* styleSet = StyleSet();
 
   nsIDocument* doc = PresContext()->Document();
 
   Element* root = doc->GetRootElement();
   if (root) {
+    for (auto iter = mModifiedElements.Iter(); !iter.Done(); iter.Next()) {
+      ServoElementSnapshot* snapshot = iter.UserData();
+      Element* element = iter.Key();
+
+      // TODO: avoid this if we already have the highest restyle hint in the
+      // subtree.
+      nsRestyleHint hint = styleSet->ComputeRestyleHint(element, snapshot);
+      hint = hint | snapshot->RestyleHint();
+      // nsRestyleHint hint = eRestyle_Self;
+      NoteRestyleHint(element, hint);
+    }
+
     styleSet->RestyleSubtree(root, /* aForce = */ false);
     RecreateStyleContexts(root, nullptr, styleSet);
   }
 
+  mModifiedElements.Clear();
+
   // NB: we restyle from the root element, but the document also gets the
   // HAS_DIRTY_DESCENDANTS flag as part of the loop on PostRestyleEvent, and we
   // use that to check we have pending restyles.
   //
   // Thus, they need to get cleared here.
   MOZ_ASSERT(!doc->IsDirtyForServo());
   doc->UnsetFlags(NODE_HAS_DIRTY_DESCENDANTS_FOR_SERVO);
 
@@ -192,18 +267,36 @@ ServoRestyleManager::ContentStateChanged
 {
   if (!aContent->IsElement()) {
     return NS_OK;
   }
 
   Element* aElement = aContent->AsElement();
   nsChangeHint changeHint;
   nsRestyleHint restyleHint;
+
+  // NOTE: restyleHint here is effectively always 0, since that's what
+  // ServoStyleSet::HasStateDependentStyle returns. Servo computes on
+  // ProcessPendingRestyles using the ElementSnapshot, but in theory could
+  // compute it sequentially easily.
+  //
+  // Determine what's the best way to do it, and how much work do we save
+  // processing the restyle hint early (i.e., computing the style hint in
+  // ServoStyleSet), vs lazily (snapshot approach), and if we definitely take
+  // the second approach, take rid of HasStateDependentStyle, etc.
+  //
+  // Also, profile whether we save something storing the restyle hint in the
+  // table and deferring the dirtiness setting until ProcessPendingRestyles
+  // (that's a requirement if we store snapshots though), vs processing the
+  // restyle hint in-place, dirtying the nodes on PostRestyleEvent.
   ContentStateChangedInternal(aElement, aStateMask, &changeHint, &restyleHint);
 
+  AddElementSnapshot(aElement, ServoElementSnapshot::Flags::State,
+                     restyleHint, changeHint);
+
   PostRestyleEvent(aElement, restyleHint, changeHint);
   return NS_OK;
 }
 
 void
 ServoRestyleManager::AttributeWillChange(Element* aElement,
                                          int32_t aNameSpaceID,
                                          nsIAtom* aAttribute,
@@ -224,9 +317,31 @@ ServoRestyleManager::AttributeChanged(El
 }
 
 nsresult
 ServoRestyleManager::ReparentStyleContext(nsIFrame* aFrame)
 {
   MOZ_CRASH("stylo: ServoRestyleManager::ReparentStyleContext not implemented");
 }
 
+void
+ServoRestyleManager::AddElementSnapshot(Element* aElement,
+                                        ServoElementSnapshot::Flags aWhatToCapture)
+{
+  AddElementSnapshot(aElement,
+                     aWhatToCapture,
+                     nsRestyleHint(0),
+                     nsChangeHint(0));
+}
+
+void
+ServoRestyleManager::AddElementSnapshot(Element* aElement,
+                                        ServoElementSnapshot::Flags aWhatToCapture,
+                                        nsRestyleHint aRestyleHint,
+                                        nsChangeHint aMinChangeHint)
+{
+  ServoElementSnapshot* existingSnapshot = mModifiedElements.LookupOrAdd(aElement);
+  MOZ_ASSERT(existingSnapshot);
+
+  existingSnapshot->Add(aElement, aWhatToCapture, aRestyleHint, aMinChangeHint);
+}
+
 } // namespace mozilla

--- a/layout/base/ServoRestyleManager.h
+++ b/layout/base/ServoRestyleManager.h
@@ -4,20 +4,22 @@
  * 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/. */
 
 #ifndef mozilla_ServoRestyleManager_h
 #define mozilla_ServoRestyleManager_h
 
 #include "mozilla/EventStates.h"
 #include "mozilla/RestyleManagerBase.h"
+#include "mozilla/ServoElementSnapshot.h"
 #include "nsChangeHint.h"
 #include "nsISupportsImpl.h"
 #include "nsPresContext.h"
 #include "nsINode.h"
+#include "nsHashKeys.h"
 
 namespace mozilla {
 namespace dom {
 class Element;
 } // namespace dom
 } // namespace mozilla
 class nsAttrValue;
 class nsIAtom;
@@ -63,48 +65,62 @@ public:
   void AttributeChanged(dom::Element* aElement,
                         int32_t aNameSpaceID,
                         nsIAtom* aAttribute,
                         int32_t aModType,
                         const nsAttrValue* aOldValue);
   nsresult ReparentStyleContext(nsIFrame* aFrame);
 
   bool HasPendingRestyles() {
-    if (MOZ_UNLIKELY(IsDisconnected())) {
-      return false;
-    }
-
-    return PresContext()->PresShell()->GetDocument()->HasDirtyDescendantsForServo();
+    // XXX IsEmpty isn't public here, consider implementing it in
+    // nsClassHashTable?
+    return mModifiedElements.Count() != 0;
   }
 
 protected:
   ~ServoRestyleManager() {}
 
 private:
   /**
+   * The element-to-element snapshot table to compute restyle hints.
+   */
+  nsClassHashtable<nsRefPtrHashKey<Element>,
+                   ServoElementSnapshot> mModifiedElements;
+
+  /**
    * Traverses a tree of content that Servo has just restyled, recreating style
    * contexts for their frames with the new style data.
    *
    * This is just static so ServoStyleSet can mark this class as friend, so we
    * can access to the GetContext method without making it available to everyone
    * else.
    */
   static void RecreateStyleContexts(nsIContent* aContent,
                                     nsStyleContext* aParentContext,
                                     ServoStyleSet* aStyleSet);
 
   /**
    * Propagates the IS_DIRTY flag down to the tree, setting
    * HAS_DIRTY_DESCENDANTS appropriately.
    */
-  static void DirtyTree(nsIContent* aContent);
+  static void DirtyTree(nsIContent* aContent, bool aIncludingRoot = true);
+
+  static void NoteRestyleHint(Element* aElement, nsRestyleHint aRestyleHint);
 
   inline ServoStyleSet* StyleSet() const {
     MOZ_ASSERT(PresContext()->StyleSet()->IsServo(),
                "ServoRestyleManager should only be used with a Servo-flavored "
                "style backend");
     return PresContext()->StyleSet()->AsServo();
   }
+
+  void AddElementSnapshot(Element* aElement,
+                          ServoElementSnapshot::Flags aWhatToCapture);
+
+  void AddElementSnapshot(Element* aElement,
+                          ServoElementSnapshot::Flags aWhatToCapture,
+                          nsRestyleHint aRestyleHint,
+                          nsChangeHint aMinChangeHint);
 };
 
 } // namespace mozilla
 
 #endif // mozilla_ServoRestyleManager_h

--- a/layout/style/ServoBindings.cpp
+++ b/layout/style/ServoBindings.cpp
@@ -97,21 +97,20 @@ Gecko_GetNextSiblingElement(RawGeckoElem
 }
 
 RawGeckoElement*
 Gecko_GetDocumentElement(RawGeckoDocument* aDoc)
 {
   return aDoc->GetDocumentElement();
 }
 
-uint8_t
+EventStates::ServoType
 Gecko_ElementState(RawGeckoElement* aElement)
 {
-  return aElement->StyleState().GetInternalValue() &
-         ((1 << (NS_EVENT_STATE_HIGHEST_SERVO_BIT + 1)) - 1);
+  return aElement->StyleState().ServoValue();
 }
 
 bool
 Gecko_IsHTMLElementInHTMLDocument(RawGeckoElement* aElement)
 {
   return aElement->IsHTMLElement() && aElement->OwnerDoc()->IsHTMLDocument();
 }
 

--- a/layout/style/ServoBindings.h
+++ b/layout/style/ServoBindings.h
@@ -7,16 +7,17 @@
 #ifndef mozilla_ServoBindings_h
 #define mozilla_ServoBindings_h
 
 #include "stdint.h"
 #include "nsColor.h"
 #include "nsStyleStruct.h"
 #include "mozilla/css/SheetParsingMode.h"
 #include "nsProxyRelease.h"
+#include "nsChangeHint.h"
 
 /*
  * API for Servo to access Gecko data structures. This file must compile as valid
  * C code in order for the binding generator to parse it.
  *
  * Functions beginning with Gecko_ are implemented in Gecko and invoked from Servo.
  * Functions beginning with Servo_ are implemented in Servo and invoked from Gecko.
  */
@@ -45,16 +46,17 @@ struct RawServoStyleSet;
 class nsHTMLCSSStyleSheet;
 struct nsStyleList;
 struct nsStyleImage;
 struct nsStyleGradientStop;
 class nsStyleGradient;
 class nsStyleCoord;
 struct nsStyleDisplay;
 struct ServoDeclarationBlock;
+class ServoElementSnapshot;
 
 #define NS_DECL_THREADSAFE_FFI_REFCOUNTING(class_, name_)                     \
   void Gecko_AddRef##name_##ArbitraryThread(class_* aPtr);                    \
   void Gecko_Release##name_##ArbitraryThread(class_* aPtr);
 #define NS_IMPL_THREADSAFE_FFI_REFCOUNTING(class_, name_)                     \
   static_assert(class_::HasThreadSafeRefCnt::value,                           \
                 "NS_DECL_THREADSAFE_FFI_REFCOUNTING can only be used with "   \
                 "classes that have thread-safe refcounting");                 \
@@ -245,16 +247,22 @@ void Servo_ReleaseComputedValues(ServoCo
 
 // Initialize Servo components. Should be called exactly once at startup.
 void Servo_Initialize();
 
 // Restyle the given document or subtree.
 void Servo_RestyleDocument(RawGeckoDocument* doc, RawServoStyleSet* set);
 void Servo_RestyleSubtree(RawGeckoNode* node, RawServoStyleSet* set);
 
+// Restyle hints.
+nsRestyleHint Servo_ComputeRestyleHint(RawGeckoElement* element,
+                                       ServoElementSnapshot* snapshot);
+
+uint32_t Servo_StyleWorkerThreadCount();
+
 // Style-struct management.
 #define STYLE_STRUCT(name, checkdata_cb) \
 struct nsStyle##name; \
 void Gecko_Construct_nsStyle##name(nsStyle##name* ptr); \
 void Gecko_CopyConstruct_nsStyle##name(nsStyle##name* ptr, const nsStyle##name* other); \
 void Gecko_Destroy_nsStyle##name(nsStyle##name* ptr); \
 const nsStyle##name* Servo_GetStyle##name(ServoComputedValues* computedValues);
 #include "nsStyleStructList.h"

new file mode 100644
--- /dev/null
+++ b/layout/style/ServoElementSnapshot.cpp
@@ -0,0 +1,65 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* 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/. */
+#include "mozilla/ServoElementSnapshot.h"
+#include "mozilla/dom/Element.h"
+
+namespace mozilla {
+
+ServoElementSnapshot::ServoElementSnapshot(Element* aElement,
+                                           Flags aWhatToCapture)
+  : mContains(Flags(0))
+{
+  MOZ_ASSERT(aWhatToCapture & Flags::All,
+             "Huh, nothing to snapshot?");
+
+  Add(aElement, aWhatToCapture, nsRestyleHint(0), nsChangeHint(0));
+
+  MOZ_ASSERT(mContains == aWhatToCapture, "What happened here?");
+}
+
+void ServoElementSnapshot::Add(Element* aElement,
+                               Flags aWhatToCapture,
+                               nsRestyleHint aRestyleHint,
+                               nsChangeHint aMinChangeHint)
+{
+  if (aWhatToCapture & Flags::State) {
+    AddState(aElement);
+  }
+
+  if (aWhatToCapture & Flags::Attributes) {
+    AddAttrs(aElement);
+  }
+
+  mExplicitChangeHint |= aMinChangeHint;
+  mExplicitRestyleHint |= aRestyleHint;
+}
+
+void
+ServoElementSnapshot::AddState(Element* aElement)
+{
+  MOZ_ASSERT(aElement);
+  if (!HasAny(Flags::State)) {
+    mState = aElement->StyleState().ServoValue();
+    mContains |= Flags::State;
+  }
+}
+
+void
+ServoElementSnapshot::AddAttrs(Element* aElement)
+{
+  MOZ_ASSERT(aElement);
+  uint32_t attrCount = aElement->GetAttrCount();
+  const nsAttrName* attrName;
+  for (uint32_t i = 0; i < attrCount; ++i) {
+    attrName = aElement->GetAttrNameAt(i);
+    const nsAttrValue* attrValue =
+      aElement->GetParsedAttr(attrName->LocalName(), attrName->NamespaceID());
+    mAttrs.AppendElement(ServoAttrSnapshot(*attrName, *attrValue));
+  }
+  mContains |= Flags::Attributes;
+}
+
+} // namespace mozilla

new file mode 100644
--- /dev/null
+++ b/layout/style/ServoElementSnapshot.h
@@ -0,0 +1,175 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* 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/. */
+
+#ifndef mozilla_ServoElementSnapshot_h
+#define mozilla_ServoElementSnapshot_h
+
+#include "mozilla/EventStates.h"
+#include "nsAttrName.h"
+#include "nsAttrValue.h"
+#include "nsChangeHint.h"
+
+namespace mozilla {
+
+namespace dom {
+class Element;
+} // namespace dom
+
+/**
+ * A structure representing a single attribute name and value.
+ *
+ * This is pretty similar to the private nsAttrAndChildArray::InternalAttr.
+ */
+struct ServoAttrSnapshot {
+  nsAttrName mName;
+  nsAttrValue mValue;
+
+  explicit ServoAttrSnapshot(const nsAttrName& aName,
+                             const nsAttrValue& aValue)
+    : mName(aName)
+    , mValue(aValue)
+  {}
+};
+
+/**
+ * This class holds all non-tree-structural state of an element that might be
+ * used for selector matching eventually.
+ *
+ * This means the attributes, and the element state, such as :hover, :active,
+ * etc...
+ */
+class ServoElementSnapshot
+{
+  typedef mozilla::dom::Element Element;
+  typedef EventStates::ServoType ServoStateType;
+public:
+  /**
+   * A bitflags enum class used to determine what data does a ServoElementSnapshot
+   * contain, if either only State, only Attributes, or everything.
+   */
+  class Flags {
+  public:
+    typedef uint8_t InternalType;
+
+    enum InternalTypeEnum : InternalType {
+      No = 0, // XXX None is a macro on Linux.
+      State = 1 << 0,
+      Attributes = 1 << 1,
+      All = State | Attributes
+    };
+
+    /* implicit */
+    Flags(enum InternalTypeEnum aFlags)
+      : mInternal(aFlags)
+    {}
+
+    explicit Flags(InternalType aFlags)
+      : mInternal(aFlags)
+    {}
+
+    Flags
+    operator |(Flags aOther) {
+      return Flags(mInternal | aOther.mInternal);
+    }
+
+    Flags&
+    operator |=(Flags aOther) {
+      mInternal |= aOther.mInternal;
+      return *this;
+    }
+
+    Flags
+    operator &(Flags aOther) {
+      return Flags(mInternal & aOther.mInternal);
+    }
+
+    operator bool() {
+      return mInternal != 0;
+    }
+
+    // FIXME: These are lame.
+    Flags
+    operator |(enum InternalTypeEnum aOther) {
+      return Flags(mInternal | aOther);
+    }
+
+    Flags&
+    operator |=(enum InternalTypeEnum aOther) {
+      mInternal |= aOther;
+      return *this;
+    }
+
+    Flags
+    operator &(enum InternalTypeEnum aOther) {
+      return Flags(mInternal & aOther);
+    }
+
+  private:
+    InternalType mInternal;
+  };
+
+  explicit ServoElementSnapshot(Element* aElement,
+                                Flags aWhatToCapture);
+
+  /**
+   * Empty snapshot, with no data at all.
+   */
+  explicit ServoElementSnapshot()
+    : mContains(0)
+    , mState(0)
+    , mExplicitRestyleHint(nsRestyleHint(0))
+    , mExplicitChangeHint(nsChangeHint(0))
+  {}
+
+  bool HasAttrs() {
+    return HasAny(Flags::Attributes);
+  }
+
+  bool HasState() {
+    return HasAny(Flags::State);
+  }
+
+  void Add(Element* aElement,
+           Flags aWhatToCapture,
+           nsRestyleHint aRestyleHint,
+           nsChangeHint aMinChangeHint);
+
+  /**
+   * Captures the given element state (if not previously captured).
+   *
+   * Equivalent to call Add(aElement, Flags::State).
+   */
+  void AddState(Element* aElement);
+
+  /**
+   * Captures the given element attributes (if not previously captured).
+   *
+   * Equivalent to call Add(aElement, Flags::Attributes).
+   */
+  void AddAttrs(Element* aElement);
+
+  nsRestyleHint RestyleHint() { return mExplicitRestyleHint; }
+
+  nsChangeHint ChangeHint() { return mExplicitChangeHint; }
+
+private:
+  bool HasAny(Flags aFlags) {
+    return mContains & aFlags;
+  }
+
+  // TODO: Profile, a 1 or 2 element AutoTArray could be worth it, given we know
+  // we're dealing with attribute changes when we take snapshots of attributes,
+  // though it can be wasted space if we deal with a lot of state-only
+  // snapshots.
+  Flags mContains;
+  nsTArray<ServoAttrSnapshot> mAttrs;
+  ServoStateType mState;
+  nsRestyleHint mExplicitRestyleHint;
+  nsChangeHint mExplicitChangeHint;
+};
+
+} // namespace mozilla
+#endif

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -6,16 +6,17 @@
 
 #ifndef mozilla_ServoStyleSet_h
 #define mozilla_ServoStyleSet_h
 
 #include "mozilla/EnumeratedArray.h"
 #include "mozilla/EventStates.h"
 #include "mozilla/RefPtr.h"
 #include "mozilla/ServoBindingHelpers.h"
+#include "mozilla/ServoElementSnapshot.h"
 #include "mozilla/ServoStyleSheet.h"
 #include "mozilla/SheetType.h"
 #include "mozilla/UniquePtr.h"
 #include "nsChangeHint.h"
 #include "nsCSSPseudoElements.h"
 #include "nsIAtom.h"
 #include "nsTArray.h"
 
@@ -114,16 +115,25 @@ public:
   nsRestyleHint HasStateDependentStyle(dom::Element* aElement,
                                        EventStates aStateMask);
   nsRestyleHint HasStateDependentStyle(dom::Element* aElement,
                                        mozilla::CSSPseudoElementType aPseudoType,
                                        dom::Element* aPseudoElement,
                                        EventStates aStateMask);
 
   /**
+   * Computes a restyle hint given a element and a previous element snapshot.
+   */
+  nsRestyleHint ComputeRestyleHint(dom::Element* aElement,
+                                   ServoElementSnapshot* aSnapshot) {
+    // Not yet.
+    return eRestyle_Self;
+  }
+
+  /**
    * Restyles a whole subtree of nodes.
    *
    * The aForce parameter propagates the dirty bits down the subtree, and when
    * used aNode needs to be nsIContent.
    */
   void RestyleSubtree(nsINode* aNode, bool aForce);
 
 private:

--- a/layout/style/moz.build
+++ b/layout/style/moz.build
@@ -88,16 +88,17 @@ EXPORTS.mozilla += [
     'CSSVariableValues.h',
     'HandleRefPtr.h',
     'IncrementalClearCOMRuleArray.h',
     'LayerAnimationInfo.h',
     'RuleNodeCacheConditions.h',
     'RuleProcessorCache.h',
     'ServoBindingHelpers.h',
     'ServoBindings.h',
+    'ServoElementSnapshot.h',
     'ServoStyleSet.h',
     'ServoStyleSheet.h',
     'SheetType.h',
     'StyleAnimationValue.h',
     'StyleBackendType.h',
     'StyleContextSource.h',
     'StyleSetHandle.h',
     'StyleSetHandleInlines.h',
@@ -185,16 +186,17 @@ UNIFIED_SOURCES += [
     'nsStyleSet.cpp',
     'nsStyleStruct.cpp',
     'nsStyleTransformMatrix.cpp',
     'nsStyleUtil.cpp',
     'nsTransitionManager.cpp',
     'RuleNodeCacheConditions.cpp',
     'RuleProcessorCache.cpp',
     'ServoBindings.cpp',
+    'ServoElementSnapshot.cpp',
     'ServoStyleSet.cpp',
     'ServoStyleSheet.cpp',
     'StyleAnimationValue.cpp',
     'StyleRule.cpp',
     'StyleSheet.cpp',
     'StyleSheetInfo.cpp',
     'SVGAttrAnimationRuleProcessor.cpp',
 ]