--- a/dom/base/Element.cpp
+++ b/dom/base/Element.cpp
@@ -1212,90 +1212,67 @@ Element::AttachShadow(const ShadowRootIn
         nameAtom == nsGkAtoms::nav ||
         nameAtom == nsGkAtoms::p ||
         nameAtom == nsGkAtoms::section ||
         nameAtom == nsGkAtoms::span)) {
     aError.Throw(NS_ERROR_DOM_NOT_SUPPORTED_ERR);
     return nullptr;
   }
 
-  return AttachShadowInternal(aInit.mMode == ShadowRootMode::Closed, aError);
+  return AttachShadowInternal(aInit.mMode, aError);
 }
 
 already_AddRefed<ShadowRoot>
 Element::CreateShadowRoot(ErrorResult& aError)
 {
-  return AttachShadowInternal(false, aError);
+  return AttachShadowInternal(ShadowRootMode::Open, aError);
 }
 
 already_AddRefed<ShadowRoot>
-Element::AttachShadowInternal(bool aClosed, ErrorResult& aError)
+Element::AttachShadowInternal(ShadowRootMode aMode, ErrorResult& aError)
 {
   /**
    * 3. If context object is a shadow host, then throw
    *    an "InvalidStateError" DOMException.
    */
   if (GetShadowRoot() || GetXBLBinding()) {
     aError.Throw(NS_ERROR_DOM_INVALID_STATE_ERR);
     return nullptr;
   }
 
   nsAutoScriptBlocker scriptBlocker;
 
-  RefPtr<mozilla::dom::NodeInfo> nodeInfo;
-  nodeInfo = mNodeInfo->NodeInfoManager()->GetNodeInfo(
-    nsGkAtoms::documentFragmentNodeName, nullptr, kNameSpaceID_None,
-    DOCUMENT_FRAGMENT_NODE);
-
-  RefPtr<nsXBLDocumentInfo> docInfo = new nsXBLDocumentInfo(OwnerDoc());
-
-  nsXBLPrototypeBinding* protoBinding = new nsXBLPrototypeBinding();
-  aError = protoBinding->Init(NS_LITERAL_CSTRING("shadowroot"),
-                              docInfo, nullptr, true);
-  if (aError.Failed()) {
-    delete protoBinding;
-    return nullptr;
-  }
+  RefPtr<mozilla::dom::NodeInfo> nodeInfo =
+    mNodeInfo->NodeInfoManager()->GetNodeInfo(
+      nsGkAtoms::documentFragmentNodeName, nullptr, kNameSpaceID_None,
+      DOCUMENT_FRAGMENT_NODE);
 
   if (nsIDocument* doc = GetComposedDoc()) {
     if (nsIPresShell* shell = doc->GetShell()) {
       shell->DestroyFramesForAndRestyle(this);
       MOZ_ASSERT(!shell->FrameManager()->GetDisplayContentsStyleFor(this));
     }
   }
   MOZ_ASSERT(!GetPrimaryFrame());
 
-  // Unlike for XBL, false is the default for inheriting style.
-  protoBinding->SetInheritsStyle(false);
-
-  // Calling SetPrototypeBinding takes ownership of protoBinding.
-  docInfo->SetPrototypeBinding(NS_LITERAL_CSTRING("shadowroot"), protoBinding);
-
   /**
    * 4. Let shadow be a new shadow root whose node document is
    *    context object’s node document, host is context object,
    *    and mode is init’s mode.
    */
   RefPtr<ShadowRoot> shadowRoot =
-    new ShadowRoot(this, aClosed, nodeInfo.forget(), protoBinding);
+    new ShadowRoot(this, aMode, nodeInfo.forget());
 
   shadowRoot->SetIsComposedDocParticipant(IsInComposedDoc());
 
   /**
    * 5. Set context object’s shadow root to shadow.
    */
   SetShadowRoot(shadowRoot);
 
-  // xblBinding takes ownership of docInfo.
-  RefPtr<nsXBLBinding> xblBinding = new nsXBLBinding(shadowRoot, protoBinding);
-  shadowRoot->SetAssociatedBinding(xblBinding);
-  xblBinding->SetBoundElement(this);
-
-  SetXBLBinding(xblBinding);
-
   /**
    * 6. Return shadow.
    */
   return shadowRoot.forget();
 }
 
 void
 Element::GetAttribute(const nsAString& aName, DOMString& aReturn)

--- a/dom/base/Element.h
+++ b/dom/base/Element.h
@@ -632,18 +632,18 @@ protected:
    * time and other places where we don't want to notify a state
    * change.
    */
   void RemoveStatesSilently(EventStates aStates)
   {
     mState &= ~aStates;
   }
 
-  already_AddRefed<ShadowRoot> AttachShadowInternal(bool aClosed,
-                                                    ErrorResult& aError);
+  already_AddRefed<ShadowRoot> AttachShadowInternal(
+    ShadowRootMode, ErrorResult& aError);
 
 private:
   // Need to allow the ESM, nsGlobalWindow, and the focus manager to
   // set our state
   friend class mozilla::EventStateManager;
   friend class ::nsGlobalWindowInner;
   friend class ::nsGlobalWindowOuter;
   friend class ::nsFocusManager;

--- a/dom/base/ShadowRoot.cpp
+++ b/dom/base/ShadowRoot.cpp
@@ -22,50 +22,47 @@
 using namespace mozilla;
 using namespace mozilla::dom;
 
 NS_IMPL_CYCLE_COLLECTION_CLASS(ShadowRoot)
 
 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN_INHERITED(ShadowRoot,
                                                   DocumentFragment)
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mDOMStyleSheets)
-  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mAssociatedBinding)
   for (auto iter = tmp->mIdentifierMap.ConstIter(); !iter.Done();
        iter.Next()) {
     iter.Get()->Traverse(&cb);
   }
 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
 
 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(ShadowRoot)
   if (tmp->GetHost()) {
     tmp->GetHost()->RemoveMutationObserver(tmp);
   }
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mDOMStyleSheets)
-  NS_IMPL_CYCLE_COLLECTION_UNLINK(mAssociatedBinding)
   tmp->mIdentifierMap.Clear();
 NS_IMPL_CYCLE_COLLECTION_UNLINK_END_INHERITED(DocumentFragment)
 
 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(ShadowRoot)
   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIContent)
   NS_INTERFACE_MAP_ENTRY(nsIMutationObserver)
 NS_INTERFACE_MAP_END_INHERITING(DocumentFragment)
 
 NS_IMPL_ADDREF_INHERITED(ShadowRoot, DocumentFragment)
 NS_IMPL_RELEASE_INHERITED(ShadowRoot, DocumentFragment)
 
-ShadowRoot::ShadowRoot(Element* aElement, bool aClosed,
-                       already_AddRefed<mozilla::dom::NodeInfo>&& aNodeInfo,
-                       nsXBLPrototypeBinding* aProtoBinding)
+ShadowRoot::ShadowRoot(Element* aElement, ShadowRootMode aMode,
+                       already_AddRefed<mozilla::dom::NodeInfo>&& aNodeInfo)
   : DocumentFragment(aNodeInfo)
   , DocumentOrShadowRoot(*this)
-  , mProtoBinding(aProtoBinding)
+  , mMode(aMode)
+  , mServoStyles(Servo_AuthorStyles_Create())
   , mIsComposedDocParticipant(false)
 {
   SetHost(aElement);
-  mMode = aClosed ? ShadowRootMode::Closed : ShadowRootMode::Open;
 
   // Nodes in a shadow tree should never store a value
   // in the subtree root pointer, nodes in the shadow tree
   // track the subtree root using GetContainingShadow().
   ClearSubtreeRootPointer();
 
   SetFlags(NODE_IS_IN_SHADOW_TREE);
 
@@ -76,18 +73,17 @@ ShadowRoot::ShadowRoot(Element* aElement
   // for mutations because the insertion points in this ShadowRoot
   // may need to be updated when the host children are modified.
   GetHost()->AddMutationObserver(this);
 }
 
 ShadowRoot::~ShadowRoot()
 {
   if (auto* host = GetHost()) {
-    // mHost may have been unlinked or a new ShadowRoot may have been
-    // created, making this one obsolete.
+    // mHost may have been unlinked.
     host->RemoveMutationObserver(this);
   }
 
   UnsetFlags(NODE_IS_IN_SHADOW_TREE);
 
   // nsINode destructor expects mSubtreeRoot == this.
   SetSubtreeRootPointer(this);
 }
@@ -203,83 +199,73 @@ ShadowRoot::RemoveSlot(HTMLSlotElement* 
     aSlot->EnqueueSlotChangeEvent();
     replacementSlot->EnqueueSlotChangeEvent();
   }
 }
 
 void
 ShadowRoot::StyleSheetChanged()
 {
-  nsIDocument* doc = OwnerDoc();
+  // FIXME(emilio): This is not needed to handle sheet additions / removals,
+  // only for CSSOM mutations, we should distinguish both.
+  Servo_AuthorStyles_ForceDirty(mServoStyles.get());
+  // FIXME(emilio): Similarly, we should notify of the particular mutation to
+  // the rule map, instead of this...
+  mStyleRuleMap.reset(nullptr);
 
-  if (doc->IsStyledByServo()) {
-    mProtoBinding->SyncServoStyles();
-  } else {
-    mProtoBinding->FlushSkinSheets();
-  }
-
+  nsIDocument* doc = OwnerDoc();
   if (nsIPresShell* shell = doc->GetShell()) {
     doc->BeginUpdate(UPDATE_STYLE);
     shell->RecordShadowStyleChange(*this);
     doc->EndUpdate(UPDATE_STYLE);
   }
 }
 
+
 void
-ShadowRoot::InsertSheet(StyleSheet* aSheet,
-                        nsIContent* aLinkingContent)
+ShadowRoot::InsertSheet(StyleSheet* aSheet, nsIContent* aLinkingContent)
 {
   nsCOMPtr<nsIStyleSheetLinkingElement>
     linkingElement = do_QueryInterface(aLinkingContent);
 
   // FIXME(emilio, bug 1410578): <link> should probably also be allowed here.
   MOZ_ASSERT(linkingElement, "The only styles in a ShadowRoot should come "
                              "from <style>.");
 
   linkingElement->SetStyleSheet(aSheet); // This sets the ownerNode on the sheet
 
-  MOZ_DIAGNOSTIC_ASSERT(mProtoBinding->SheetCount() == DocumentOrShadowRoot::SheetCount());
-#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
-  // FIXME(emilio, bug 1425759): For now we keep them duplicated, the proto
-  // binding will disappear soon (tm).
-  {
-    size_t i = 0;
-    for (RefPtr<StyleSheet>& sheet : mStyleSheets) {
-      MOZ_DIAGNOSTIC_ASSERT(sheet.get() == mProtoBinding->StyleSheetAt(i++));
-    }
-  }
-#endif
-
   // Find the correct position to insert into the style sheet list (must
   // be in tree order).
   for (size_t i = 0; i <= SheetCount(); i++) {
     if (i == SheetCount()) {
       AppendStyleSheet(*aSheet);
-      mProtoBinding->AppendStyleSheet(aSheet);
+      Servo_AuthorStyles_AppendStyleSheet(mServoStyles.get(), aSheet->AsServo());
       break;
     }
 
-    nsINode* sheetOwningNode = SheetAt(i)->GetOwnerNode();
+    StyleSheet* sheet = SheetAt(i);
+    nsINode* sheetOwningNode = sheet->GetOwnerNode();
     if (nsContentUtils::PositionIsBefore(aLinkingContent, sheetOwningNode)) {
       InsertSheetAt(i, *aSheet);
-      mProtoBinding->InsertStyleSheetAt(i, aSheet);
+      Servo_AuthorStyles_InsertStyleSheetBefore(
+        mServoStyles.get(), aSheet->AsServo(), sheet->AsServo());
       break;
     }
   }
 
   if (aSheet->IsApplicable()) {
     StyleSheetChanged();
   }
 }
 
 void
 ShadowRoot::RemoveSheet(StyleSheet* aSheet)
 {
-  mProtoBinding->RemoveStyleSheet(aSheet);
   DocumentOrShadowRoot::RemoveSheet(*aSheet);
+  Servo_AuthorStyles_RemoveStyleSheet(mServoStyles.get(), aSheet->AsServo());
 
   if (aSheet->IsApplicable()) {
     StyleSheetChanged();
   }
 }
 
 void
 ShadowRoot::AddToIdTable(Element* aElement, nsAtom* aId)
@@ -557,15 +543,25 @@ ShadowRoot::ContentRemoved(nsIDocument* 
   // nodes is the empty list, then run signal a slot change for parent.
   HTMLSlotElement* slot = HTMLSlotElement::FromContentOrNull(aContainer);
   if (slot && slot->GetContainingShadow() == this &&
       slot->AssignedNodes().IsEmpty()) {
     slot->EnqueueSlotChangeEvent();
   }
 }
 
+ServoStyleRuleMap&
+ShadowRoot::ServoStyleRuleMap()
+{
+  if (!mStyleRuleMap) {
+    mStyleRuleMap = MakeUnique<mozilla::ServoStyleRuleMap>();
+  }
+  mStyleRuleMap->EnsureTable(*this);
+  return *mStyleRuleMap;
+}
+
 nsresult
 ShadowRoot::Clone(mozilla::dom::NodeInfo *aNodeInfo, nsINode **aResult,
                   bool aPreallocateChildren) const
 {
   *aResult = nullptr;
   return NS_ERROR_DOM_NOT_SUPPORTED_ERR;
 }

--- a/dom/base/ShadowRoot.h
+++ b/dom/base/ShadowRoot.h
@@ -4,16 +4,17 @@
  * 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_dom_shadowroot_h__
 #define mozilla_dom_shadowroot_h__
 
 #include "mozilla/dom/DocumentFragment.h"
 #include "mozilla/dom/DocumentOrShadowRoot.h"
+#include "mozilla/ServoStyleRuleMap.h"
 #include "nsCOMPtr.h"
 #include "nsCycleCollectionParticipant.h"
 #include "nsIdentifierMapEntry.h"
 #include "nsTHashtable.h"
 
 class nsAtom;
 class nsIContent;
 class nsXBLPrototypeBinding;
@@ -55,19 +56,18 @@ public:
                                            DocumentFragment)
   NS_DECL_ISUPPORTS_INHERITED
 
   NS_DECL_NSIMUTATIONOBSERVER_ATTRIBUTECHANGED
   NS_DECL_NSIMUTATIONOBSERVER_CONTENTAPPENDED
   NS_DECL_NSIMUTATIONOBSERVER_CONTENTINSERTED
   NS_DECL_NSIMUTATIONOBSERVER_CONTENTREMOVED
 
-  ShadowRoot(Element* aElement, bool aClosed,
-             already_AddRefed<mozilla::dom::NodeInfo>&& aNodeInfo,
-             nsXBLPrototypeBinding* aProtoBinding);
+  ShadowRoot(Element* aElement, ShadowRootMode aMode,
+             already_AddRefed<mozilla::dom::NodeInfo>&& aNodeInfo);
 
   // Shadow DOM v1
   Element* Host() const
   {
     MOZ_ASSERT(GetHost(), "ShadowRoot always has a host, how did we create "
                           "this ShadowRoot?");
     return GetHost();
   }
@@ -112,66 +112,78 @@ private:
    */
   const HTMLSlotElement* UnassignSlotFor(nsIContent* aContent,
                                          const nsAString& aSlotName);
 
 public:
   void AddSlot(HTMLSlotElement* aSlot);
   void RemoveSlot(HTMLSlotElement* aSlot);
 
-  void SetAssociatedBinding(nsXBLBinding* aBinding) { mAssociatedBinding = aBinding; }
+  const RawServoAuthorStyles* ServoStyles() const
+  {
+    return mServoStyles.get();
+  }
+
+  RawServoAuthorStyles* ServoStyles()
+  {
+    return mServoStyles.get();
+  }
+
+  // FIXME(emilio): This will need to become more fine-grained.
+  void StyleSheetChanged();
+
+  mozilla::ServoStyleRuleMap& ServoStyleRuleMap();
 
   JSObject* WrapObject(JSContext* aCx, JS::Handle<JSObject*> aGivenProto) override;
 
   void AddToIdTable(Element* aElement, nsAtom* aId);
   void RemoveFromIdTable(Element* aElement, nsAtom* aId);
 
   // WebIDL methods.
   using mozilla::dom::DocumentOrShadowRoot::GetElementById;
 
   Element* GetActiveElement();
   void GetInnerHTML(nsAString& aInnerHTML);
   void SetInnerHTML(const nsAString& aInnerHTML, ErrorResult& aError);
-  void StyleSheetChanged();
 
   bool IsComposedDocParticipant() const
   {
     return mIsComposedDocParticipant;
   }
 
   void SetIsComposedDocParticipant(bool aIsComposedDocParticipant)
   {
     mIsComposedDocParticipant = aIsComposedDocParticipant;
   }
 
   nsresult GetEventTargetParent(EventChainPreVisitor& aVisitor) override;
 
 protected:
   virtual ~ShadowRoot();
 
-  ShadowRootMode mMode;
+  void SyncServoStyles();
+
+  const ShadowRootMode mMode;
+
+  // The computed data from the style sheets.
+  UniquePtr<RawServoAuthorStyles> mServoStyles;
+  UniquePtr<mozilla::ServoStyleRuleMap> mStyleRuleMap;
 
   using SlotArray = AutoTArray<HTMLSlotElement*, 1>;
   // Map from name of slot to an array of all slots in the shadow DOM with with
   // the given name. The slots are stored as a weak pointer because the elements
   // are in the shadow tree and should be kept alive by its parent.
   nsClassHashtable<nsStringHashKey, SlotArray> mSlotMap;
-  nsXBLPrototypeBinding* mProtoBinding;
-
-  // It is necessary to hold a reference to the associated nsXBLBinding
-  // because the binding holds a reference on the nsXBLDocumentInfo that
-  // owns |mProtoBinding|.
-  RefPtr<nsXBLBinding> mAssociatedBinding;
 
   // Flag to indicate whether the descendants of this shadow root are part of the
   // composed document. Ideally, we would use a node flag on nodes to
   // mark whether it is in the composed document, but we have run out of flags
   // so instead we track it here.
   bool mIsComposedDocParticipant;
 
-  nsresult Clone(mozilla::dom::NodeInfo *aNodeInfo, nsINode **aResult,
+  nsresult Clone(mozilla::dom::NodeInfo* aNodeInfo, nsINode** aResult,
                  bool aPreallocateChildren) const override;
 };
 
 } // namespace dom
 } // namespace mozilla
 
 #endif // mozilla_dom_shadowroot_h__

--- a/layout/inspector/InspectorUtils.cpp
+++ b/layout/inspector/InspectorUtils.cpp
@@ -233,30 +233,38 @@ InspectorUtils::GetCSSStyleRules(GlobalO
       maps.AppendElement(map);
     }
 
     // Collect style rule maps for bindings.
     for (nsIContent* bindingContent = &aElement; bindingContent;
          bindingContent = bindingContent->GetBindingParent()) {
       for (nsXBLBinding* binding = bindingContent->GetXBLBinding();
            binding; binding = binding->GetBaseBinding()) {
-        // TODO(emilio): We're going to need to figure out something for Shadow
-        // DOM and inspector, since those rules can definitely mutate and
-        // such...
         if (auto* map = binding->PrototypeBinding()->GetServoStyleRuleMap()) {
           maps.AppendElement(map);
         }
       }
       // Note that we intentionally don't cut off here, unlike when we
       // do styling, because even if style rules from parent binding
       // do not apply to the element directly in those cases, their
       // rules may still show up in the list we get above due to the
       // inheritance in cascading.
     }
 
+    // Now shadow DOM stuff...
+    if (auto* shadow = aElement.GetShadowRoot()) {
+      maps.AppendElement(&shadow->ServoStyleRuleMap());
+    }
+
+    for (auto* shadow = aElement.GetContainingShadow();
+         shadow;
+         shadow = shadow->Host()->GetContainingShadow()) {
+      maps.AppendElement(&shadow->ServoStyleRuleMap());
+    }
+
     // Find matching rules in the table.
     for (const RawServoStyleRule* rawRule : Reversed(rawRuleList)) {
       ServoStyleRule* rule = nullptr;
       for (ServoStyleRuleMap* map : maps) {
         rule = map->Lookup(rawRule);
         if (rule) {
           break;
         }

--- a/layout/inspector/ServoStyleRuleMap.cpp
+++ b/layout/inspector/ServoStyleRuleMap.cpp
@@ -39,16 +39,27 @@ ServoStyleRuleMap::EnsureTable(nsXBLProt
     return;
   }
   for (auto index : IntegerRange(aXBLResources.SheetCount())) {
     FillTableFromStyleSheet(*aXBLResources.StyleSheetAt(index)->AsServo());
   }
 }
 
 void
+ServoStyleRuleMap::EnsureTable(ShadowRoot& aShadowRoot)
+{
+  if (!IsEmpty()) {
+    return;
+  }
+  for (auto index : IntegerRange(aShadowRoot.SheetCount())) {
+    FillTableFromStyleSheet(*aShadowRoot.SheetAt(index)->AsServo());
+  }
+}
+
+void
 ServoStyleRuleMap::SheetAdded(ServoStyleSheet& aStyleSheet)
 {
   if (!IsEmpty()) {
     FillTableFromStyleSheet(aStyleSheet);
   }
 }
 
 void

--- a/layout/inspector/ServoStyleRuleMap.h
+++ b/layout/inspector/ServoStyleRuleMap.h
@@ -15,24 +15,28 @@ struct RawServoStyleRule;
 class nsXBLPrototypeResources;
 
 namespace mozilla {
 class ServoCSSRuleList;
 class ServoStyleSet;
 namespace css {
 class Rule;
 } // namespace css
-
+namespace dom {
+class ShadowRoot;
+}
 class ServoStyleRuleMap
 {
 public:
   ServoStyleRuleMap() = default;
 
   void EnsureTable(ServoStyleSet&);
   void EnsureTable(nsXBLPrototypeResources&);
+  void EnsureTable(dom::ShadowRoot&);
+
   ServoStyleRule* Lookup(const RawServoStyleRule* aRawRule) const
   {
     return mTable.Get(aRawRule);
   }
 
   void SheetAdded(ServoStyleSheet&);
   void SheetRemoved(ServoStyleSheet&);
 

--- a/layout/style/ServoBindingList.h
+++ b/layout/style/ServoBindingList.h
@@ -175,25 +175,32 @@ SERVO_BINDING_FUNC(Servo_UACache_AddSize
                    mozilla::MallocSizeOf malloc_size_of,
                    mozilla::MallocSizeOf malloc_enclosing_size_of,
                    mozilla::ServoStyleSetSizes* sizes)
 
 // AuthorStyles
 SERVO_BINDING_FUNC(Servo_AuthorStyles_Create, RawServoAuthorStyles*)
 SERVO_BINDING_FUNC(Servo_AuthorStyles_Drop, void,
                    RawServoAuthorStylesOwned self)
-// TODO(emilio): This will need to take an optional master style set to
-// implement invalidation for Shadow DOM.
+// TODO(emilio): These will need to take a master style set to implement
+// invalidation for Shadow DOM.
 SERVO_BINDING_FUNC(Servo_AuthorStyles_AppendStyleSheet, void,
                    RawServoAuthorStylesBorrowedMut self,
                    const mozilla::ServoStyleSheet* gecko_sheet)
+SERVO_BINDING_FUNC(Servo_AuthorStyles_RemoveStyleSheet, void,
+                   RawServoAuthorStylesBorrowedMut self,
+                   const mozilla::ServoStyleSheet* gecko_sheet)
+SERVO_BINDING_FUNC(Servo_AuthorStyles_InsertStyleSheetBefore, void,
+                   RawServoAuthorStylesBorrowedMut self,
+                   const mozilla::ServoStyleSheet* gecko_sheet,
+                   const mozilla::ServoStyleSheet* before)
 SERVO_BINDING_FUNC(Servo_AuthorStyles_ForceDirty, void,
                    RawServoAuthorStylesBorrowedMut self)
-// TODO(emilio): This will need to take an element to implement invalidation for
-// Shadow DOM.
+// TODO(emilio): This will need to take an element and a master style set to
+// implement invalidation for Shadow DOM.
 SERVO_BINDING_FUNC(Servo_AuthorStyles_Flush, void,
                    RawServoAuthorStylesBorrowedMut self,
                    RawServoStyleSetBorrowed document_styles)
 SERVO_BINDING_FUNC(Servo_AuthorStyles_SizeOfIncludingThis, size_t,
                    mozilla::MallocSizeOf malloc_size_of,
                    mozilla::MallocSizeOf malloc_enclosing_size_of,
                    RawServoAuthorStylesBorrowed self)
 

--- a/layout/style/ServoBindings.toml
+++ b/layout/style/ServoBindings.toml
@@ -53,16 +53,17 @@ headers = [
     "mozilla/StyleAnimationValue.h",
     "gfxFontConstants.h",
     "gfxFontFeatures.h",
     "nsThemeConstants.h",
     "mozilla/css/Loader.h",
     "mozilla/dom/AnimationEffectReadOnlyBinding.h",
     "mozilla/dom/HTMLSlotElement.h",
     "mozilla/dom/KeyframeEffectBinding.h",
+    "mozilla/dom/ShadowRoot.h",
     "mozilla/AnimationPropertySegment.h",
     "mozilla/ComputedTiming.h",
     "mozilla/ComputedTimingFunction.h",
     "mozilla/Keyframe.h",
     "mozilla/ServoElementSnapshot.h",
     "mozilla/ServoElementSnapshotTable.h",
     "mozilla/css/ErrorReporter.h",
     "mozilla/dom/Element.h",

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -4,16 +4,17 @@
  * 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/ServoStyleSet.h"
 
 #include "gfxPlatformFontList.h"
 #include "mozilla/AutoRestyleTimelineMarker.h"
 #include "mozilla/DocumentStyleRootIterator.h"
+#include "mozilla/IntegerRange.h"
 #include "mozilla/LookAndFeel.h"
 #include "mozilla/RestyleManagerInlines.h"
 #include "mozilla/ServoBindings.h"
 #include "mozilla/ServoRestyleManager.h"
 #include "mozilla/ServoStyleRuleMap.h"
 #include "mozilla/ServoTypes.h"
 #include "mozilla/css/Loader.h"
 #include "mozilla/dom/AnonymousContent.h"
@@ -163,16 +164,47 @@ ServoStyleSet::Init(nsPresContext* aPres
   //
   // Now that we got a shell, we may need to get them up-to-date.
   //
   // TODO(emilio, bug 1418159): This wouldn't be needed if the StyleSet was
   // owned by the document.
   SetStylistXBLStyleSheetsDirty();
 }
 
+template<typename Functor>
+void
+EnumerateShadowRootsInSubtree(const nsINode& aRoot, const Functor& aCb)
+{
+  for (const nsINode* cur = &aRoot; cur; cur = cur->GetNextNode()) {
+    if (!cur->IsElement()) {
+      continue;
+    }
+
+    auto* shadowRoot = cur->AsElement()->GetShadowRoot();
+    if (!shadowRoot) {
+      continue;
+    }
+
+    aCb(*shadowRoot);
+    EnumerateShadowRootsInSubtree(*shadowRoot, aCb);
+  }
+}
+
+// FIXME(emilio): We may want a faster way to do this.
+template<typename Functor>
+void
+EnumerateShadowRoots(const nsIDocument& aDoc, const Functor& aCb)
+{
+  if (!aDoc.IsShadowDOMEnabled()) {
+    return;
+  }
+
+  EnumerateShadowRootsInSubtree(aDoc, aCb);
+}
+
 void
 ServoStyleSet::Shutdown()
 {
   // Make sure we drop our cached style contexts before the presshell arena
   // starts going away.
   ClearNonInheritingStyleContexts();
   mRawSet = nullptr;
   mStyleRuleMap = nullptr;
@@ -213,32 +245,37 @@ ServoStyleSet::InvalidateStyleForDocumen
   }
 
   Element* root = mDocument->GetRootElement();
   if (!root) {
     return;
   }
 
   // TODO(emilio): It may be nicer to just invalidate stuff in a given subtree
-  // for XBL sheets / shadow DOM. Consider just enumerating bound content
+  // for XBL sheets / Shadow DOM. Consider just enumerating bound content
   // instead and run invalidation individually, passing mRawSet for the UA /
   // User sheets.
-  AutoTArray<RawServoAuthorStylesBorrowed, 20> xblStyles;
+  AutoTArray<RawServoAuthorStylesBorrowed, 20> nonDocumentStyles;
+
+  EnumerateShadowRoots(*mDocument, [&](ShadowRoot& aShadowRoot) {
+    nonDocumentStyles.AppendElement(aShadowRoot.ServoStyles());
+  });
+
   // FIXME(emilio): When bug 1425759 is fixed we need to enumerate ShadowRoots
   // too.
   mDocument->BindingManager()->EnumerateBoundContentBindings(
     [&](nsXBLBinding* aBinding) {
       if (auto* authorStyles = aBinding->PrototypeBinding()->GetServoStyles()) {
-        xblStyles.AppendElement(authorStyles);
+        nonDocumentStyles.AppendElement(authorStyles);
       }
       return true;
     });
 
   Servo_InvalidateStyleForDocStateChanges(
-    root, mRawSet.get(), &xblStyles, aStatesChanged.ServoValue());
+    root, mRawSet.get(), &nonDocumentStyles, aStatesChanged.ServoValue());
 }
 
 static const MediaFeatureChangeReason kMediaFeaturesAffectingDefaultStyle =
   // Zoom changes change the meaning of em units.
   MediaFeatureChangeReason::ZoomChange |
   // Changes the meaning of em units, depending on which one is the actual
   // min-font-size.
   MediaFeatureChangeReason::MinFontSizeChange |
@@ -247,19 +284,21 @@ static const MediaFeatureChangeReason kM
   // not do that, maybe doing it on layout directly, to try to avoid relying on
   // the pres context (bug 1418159).
   MediaFeatureChangeReason::ResolutionChange;
 
 nsRestyleHint
 ServoStyleSet::MediumFeaturesChanged(MediaFeatureChangeReason aReason)
 {
   AutoTArray<RawServoAuthorStylesBorrowedMut, 20> nonDocumentStyles;
-  // FIXME(emilio): When bug 1425759 is fixed we need to enumerate ShadowRoots
-  // too.
-  //
+
+  EnumerateShadowRoots(*mDocument, [&](ShadowRoot& aShadowRoot) {
+    nonDocumentStyles.AppendElement(aShadowRoot.ServoStyles());
+  });
+
   // FIXME(emilio): This is broken for XBL. See bug 1406875.
   mDocument->BindingManager()->EnumerateBoundContentBindings(
     [&](nsXBLBinding* aBinding) {
       if (auto* authorStyles = aBinding->PrototypeBinding()->GetServoStyles()) {
         nonDocumentStyles.AppendElement(authorStyles);
       }
       return true;
     });
@@ -1254,48 +1293,61 @@ ServoStyleSet::ComputeAnimationValue(
                                       aDeclarations,
                                       aContext,
                                       mRawSet.get()).Consume();
 }
 
 bool
 ServoStyleSet::EnsureUniqueInnerOnCSSSheets()
 {
-  using SheetOwner = Variant<ServoStyleSet*, nsXBLPrototypeBinding*>;
+  using SheetOwner = Variant<ServoStyleSet*, nsXBLPrototypeBinding*, ShadowRoot*>;
 
   AutoTArray<Pair<StyleSheet*, SheetOwner>, 32> queue;
   for (auto& entryArray : mSheets) {
     for (auto& sheet : entryArray) {
       StyleSheet* downcasted = sheet;
       queue.AppendElement(MakePair(downcasted, SheetOwner { this }));
     }
   }
 
+  EnumerateShadowRoots(*mDocument, [&](ShadowRoot& aShadowRoot) {
+    for (auto index : IntegerRange(aShadowRoot.SheetCount())) {
+      queue.AppendElement(
+        MakePair(aShadowRoot.SheetAt(index), SheetOwner { &aShadowRoot }));
+    }
+  });
+
   mDocument->BindingManager()->EnumerateBoundContentBindings(
       [&](nsXBLBinding* aBinding) {
         AutoTArray<StyleSheet*, 3> sheets;
         aBinding->PrototypeBinding()->AppendStyleSheetsTo(sheets);
         for (auto* sheet : sheets) {
           queue.AppendElement(MakePair(sheet, SheetOwner { aBinding->PrototypeBinding() }));
         }
         return true;
       });
 
-  bool anyXBLSheetChanged = false;
+  bool anyNonDocStyleChanged = false;
   while (!queue.IsEmpty()) {
     uint32_t idx = queue.Length() - 1;
     auto* sheet = queue[idx].first();
     SheetOwner owner = queue[idx].second();
     queue.RemoveElementAt(idx);
 
-    if (!sheet->HasUniqueInner() && owner.is<nsXBLPrototypeBinding*>()) {
-      if (auto* styles = owner.as<nsXBLPrototypeBinding*>()->GetServoStyles()) {
-        Servo_AuthorStyles_ForceDirty(styles);
+    if (!sheet->HasUniqueInner()) {
+      if (owner.is<ShadowRoot*>()) {
+        Servo_AuthorStyles_ForceDirty(owner.as<ShadowRoot*>()->ServoStyles());
         mNeedsRestyleAfterEnsureUniqueInner = true;
-        anyXBLSheetChanged = true;
+        anyNonDocStyleChanged = true;
+      } else if (owner.is<nsXBLPrototypeBinding*>()) {
+        if (auto* styles = owner.as<nsXBLPrototypeBinding*>()->GetServoStyles()) {
+          Servo_AuthorStyles_ForceDirty(styles);
+          mNeedsRestyleAfterEnsureUniqueInner = true;
+          anyNonDocStyleChanged = true;
+        }
       }
     }
 
     // Only call EnsureUniqueInner for complete sheets. If we do call it on
     // incomplete sheets, we'll cause problems when the sheet is actually
     // loaded. We don't care about incomplete sheets here anyway, because this
     // method is only invoked by nsPresContext::EnsureSafeToHandOutCSSRules.
     // The CSSRule objects we are handing out won't contain any rules derived
@@ -1307,17 +1359,17 @@ ServoStyleSet::EnsureUniqueInnerOnCSSShe
     // Enqueue all the sheet's children.
     AutoTArray<StyleSheet*, 3> children;
     sheet->AppendAllChildSheets(children);
     for (auto* sheet : children) {
       queue.AppendElement(MakePair(sheet, owner));
     }
   }
 
-  if (anyXBLSheetChanged) {
+  if (anyNonDocStyleChanged) {
     SetStylistXBLStyleSheetsDirty();
   }
 
   if (mNeedsRestyleAfterEnsureUniqueInner) {
     // TODO(emilio): We could make this faster if needed tracking the specific
     // origins and all that, but the only caller of this doesn't seem to really
     // care about perf.
     MarkOriginsDirty(OriginFlags::All);
@@ -1467,16 +1519,21 @@ ServoStyleSet::UpdateStylist()
     if (nsPresContext* pc = GetPresContext()) {
       snapshots = &pc->RestyleManager()->AsServo()->Snapshots();
     }
     Servo_StyleSet_FlushStyleSheets(mRawSet.get(), root, snapshots);
   }
 
   if (MOZ_UNLIKELY(mStylistState & StylistState::XBLStyleSheetsDirty)) {
     MOZ_ASSERT(GetPresContext(), "How did they get dirty?");
+
+    EnumerateShadowRoots(*mDocument, [&](ShadowRoot& aShadowRoot) {
+      Servo_AuthorStyles_Flush(aShadowRoot.ServoStyles(), mRawSet.get());
+    });
+
     mDocument->BindingManager()->EnumerateBoundContentBindings(
       [&](nsXBLBinding* aBinding) {
         if (auto* authorStyles = aBinding->PrototypeBinding()->GetServoStyles()) {
           Servo_AuthorStyles_Flush(authorStyles, mRawSet.get());
         }
         return true;
       });
   }

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -1404,29 +1404,44 @@ impl<'le> TElement for GeckoElement<'le>
         F: FnMut(&'a CascadeData, QuirksMode),
     {
         // Walk the binding scope chain, starting with the binding attached to
         // our content, up till we run out of scopes or we get cut off.
         //
         // If we are a NAC pseudo-element, we want to get rules from our
         // rule_hash_target, that is, our originating element.
         let mut current = Some(self.rule_hash_target());
+        while let Some(element) = current {
+            // TODO(emilio): Deal with Shadow DOM separately than with XBL
+            // (right now we still rely on get_xbl_binding_parent()).
+            //
+            // That will allow to clean up a bunch in
+            // push_applicable_declarations.
+            if let Some(shadow) = element.shadow_root() {
+                debug_assert!(!shadow.mServoStyles.mPtr.is_null());
+                let author_styles = unsafe {
+                    &*(shadow.mServoStyles.mPtr as *const structs::RawServoAuthorStyles as *const bindings::RawServoAuthorStyles)
+                };
 
-        while let Some(element) = current {
+                let author_styles: &'a _ = AuthorStyles::<GeckoStyleSheet>::from_ffi(author_styles);
+                f(&author_styles.data, author_styles.quirks_mode);
+                if element != *self {
+                    break;
+                }
+            }
+
             if let Some(binding) = element.xbl_binding() {
                 binding.each_xbl_cascade_data(&mut f);
 
                 // If we're not looking at our original element, allow the
                 // binding to cut off style inheritance.
-                if element != *self {
-                    if !binding.inherits_style() {
-                        // Go no further; we're not inheriting style from
-                        // anything above here.
-                        break;
-                    }
+                if element != *self && !binding.inherits_style() {
+                    // Go no further; we're not inheriting style from
+                    // anything above here.
+                    break;
                 }
             }
 
             if element.is_root_of_native_anonymous_subtree() {
                 // Deliberately cut off style inheritance here.
                 break;
             }
 

--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -1145,16 +1145,50 @@ pub unsafe extern "C" fn Servo_AuthorSty
 
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let sheet = GeckoStyleSheet::new(sheet);
     styles.stylesheets.append_stylesheet(None, sheet, &guard);
 }
 
 #[no_mangle]
+pub unsafe extern "C" fn Servo_AuthorStyles_InsertStyleSheetBefore(
+    styles: RawServoAuthorStylesBorrowedMut,
+    sheet: *const ServoStyleSheet,
+    before_sheet: *const ServoStyleSheet,
+) {
+    let styles = AuthorStyles::<GeckoStyleSheet>::from_ffi_mut(styles);
+
+    let global_style_data = &*GLOBAL_STYLE_DATA;
+    let guard = global_style_data.shared_lock.read();
+    styles.stylesheets.insert_stylesheet_before(
+        None,
+        GeckoStyleSheet::new(sheet),
+        GeckoStyleSheet::new(before_sheet),
+        &guard,
+    );
+}
+
+#[no_mangle]
+pub unsafe extern "C" fn Servo_AuthorStyles_RemoveStyleSheet(
+    styles: RawServoAuthorStylesBorrowedMut,
+    sheet: *const ServoStyleSheet,
+) {
+    let styles = AuthorStyles::<GeckoStyleSheet>::from_ffi_mut(styles);
+
+    let global_style_data = &*GLOBAL_STYLE_DATA;
+    let guard = global_style_data.shared_lock.read();
+    styles.stylesheets.remove_stylesheet(
+        None,
+        GeckoStyleSheet::new(sheet),
+        &guard,
+    );
+}
+
+#[no_mangle]
 pub unsafe extern "C" fn Servo_AuthorStyles_ForceDirty(
     styles: RawServoAuthorStylesBorrowedMut,
 ) {
     let styles = AuthorStyles::<GeckoStyleSheet>::from_ffi_mut(styles);
     styles.stylesheets.force_dirty();
 }
 
 #[no_mangle]