--- a/dom/base/ShadowRoot.cpp
+++ b/dom/base/ShadowRoot.cpp
@@ -76,22 +76,45 @@ ShadowRoot::ShadowRoot(Element* aElement
 
 ShadowRoot::~ShadowRoot()
 {
   if (auto* host = GetHost()) {
     // mHost may have been unlinked.
     host->RemoveMutationObserver(this);
   }
 
+  if (IsComposedDocParticipant()) {
+    OwnerDoc()->RemoveComposedDocShadowRoot(*this);
+  }
+
+  MOZ_DIAGNOSTIC_ASSERT(!OwnerDoc()->IsComposedDocShadowRoot(*this));
+
   UnsetFlags(NODE_IS_IN_SHADOW_TREE);
 
   // nsINode destructor expects mSubtreeRoot == this.
   SetSubtreeRootPointer(this);
 }
 
+void
+ShadowRoot::SetIsComposedDocParticipant(bool aIsComposedDocParticipant)
+{
+  bool changed = mIsComposedDocParticipant != aIsComposedDocParticipant;
+  mIsComposedDocParticipant = aIsComposedDocParticipant;
+  if (!changed) {
+    return;
+  }
+
+  nsIDocument* doc = OwnerDoc();
+  if (IsComposedDocParticipant()) {
+    doc->AddComposedDocShadowRoot(*this);
+  } else {
+    doc->RemoveComposedDocShadowRoot(*this);
+  }
+}
+
 JSObject*
 ShadowRoot::WrapObject(JSContext* aCx, JS::Handle<JSObject*> aGivenProto)
 {
   return mozilla::dom::ShadowRootBinding::Wrap(aCx, this, aGivenProto);
 }
 
 void
 ShadowRoot::CloneInternalDataFrom(ShadowRoot* aOther)

--- a/dom/base/ShadowRoot.h
+++ b/dom/base/ShadowRoot.h
@@ -181,20 +181,17 @@ public:
   void GetInnerHTML(nsAString& aInnerHTML);
   void SetInnerHTML(const nsAString& aInnerHTML, ErrorResult& aError);
 
   bool IsComposedDocParticipant() const
   {
     return mIsComposedDocParticipant;
   }
 
-  void SetIsComposedDocParticipant(bool aIsComposedDocParticipant)
-  {
-    mIsComposedDocParticipant = aIsComposedDocParticipant;
-  }
+  void SetIsComposedDocParticipant(bool aIsComposedDocParticipant);
 
   nsresult GetEventTargetParent(EventChainPreVisitor& aVisitor) override;
 
 protected:
   // FIXME(emilio): This will need to become more fine-grained.
   void ApplicableRulesChanged();
 
   virtual ~ShadowRoot();

--- a/dom/base/nsDocument.cpp
+++ b/dom/base/nsDocument.cpp
@@ -8639,16 +8639,17 @@ nsIDocument::MutationEventDispatched(nsI
 void
 nsIDocument::DestroyElementMaps()
 {
 #ifdef DEBUG
   mStyledLinksCleared = true;
 #endif
   mStyledLinks.Clear();
   mIdentifierMap.Clear();
+  mComposedShadowRoots.Clear();
   mResponsiveContent.Clear();
   IncrementExpandoGeneration(*this);
 }
 
 void
 nsIDocument::RefreshLinkHrefs()
 {
   // Get a list of all links we know about.  We will reset them, which will

--- a/dom/base/nsIDocument.h
+++ b/dom/base/nsIDocument.h
@@ -3009,16 +3009,43 @@ public:
   // Removes an element from mResponsiveContent when the element is
   // removed from the tree.
   void RemoveResponsiveContent(mozilla::dom::HTMLImageElement* aContent)
   {
     MOZ_ASSERT(aContent);
     mResponsiveContent.RemoveEntry(aContent);
   }
 
+  void AddComposedDocShadowRoot(mozilla::dom::ShadowRoot& aShadowRoot)
+  {
+    MOZ_ASSERT(IsShadowDOMEnabled());
+    mComposedShadowRoots.PutEntry(&aShadowRoot);
+  }
+
+  using ShadowRootSet = nsTHashtable<nsPtrHashKey<mozilla::dom::ShadowRoot>>;
+
+  void RemoveComposedDocShadowRoot(mozilla::dom::ShadowRoot& aShadowRoot)
+  {
+    MOZ_ASSERT(IsShadowDOMEnabled());
+    mComposedShadowRoots.RemoveEntry(&aShadowRoot);
+  }
+
+  // If you're considering using this, you probably want to use
+  // ShadowRoot::IsComposedDocParticipant instead. This is just for
+  // sanity-checking.
+  bool IsComposedDocShadowRoot(mozilla::dom::ShadowRoot& aShadowRoot)
+  {
+    return mComposedShadowRoots.Contains(&aShadowRoot);
+  }
+
+  const ShadowRootSet& ComposedShadowRoots() const
+  {
+    return mComposedShadowRoots;
+  }
+
   // Notifies any responsive content added by AddResponsiveContent upon media
   // features values changing.
   void NotifyMediaFeatureValuesChanged();
 
   nsresult GetStateObject(nsIVariant** aResult);
 
   nsDOMNavigationTiming* GetNavigationTiming() const
   {
@@ -3802,16 +3829,21 @@ protected:
   RefPtr<mozilla::css::Loader> mCSSLoader;
   RefPtr<mozilla::css::ImageLoader> mStyleImageLoader;
   RefPtr<nsHTMLStyleSheet> mAttrStyleSheet;
   RefPtr<nsHTMLCSSStyleSheet> mStyleAttrStyleSheet;
 
   // Tracking for images in the document.
   RefPtr<mozilla::dom::ImageTracker> mImageTracker;
 
+  // A hashtable of ShadowRoots belonging to the composed doc.
+  //
+  // See ShadowRoot::SetIsComposedDocParticipant.
+  ShadowRootSet mComposedShadowRoots;
+
   // The set of all object, embed, video/audio elements or
   // nsIObjectLoadingContent or nsIDocumentActivity for which this is the owner
   // document. (They might not be in the document.)
   //
   // These are non-owning pointers, the elements are responsible for removing
   // themselves when they go away.
   nsAutoPtr<nsTHashtable<nsPtrHashKey<nsISupports> > > mActivityObservers;
 

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -165,43 +165,29 @@ ServoStyleSet::Init(nsPresContext* aPres
   //
   // 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);
+  auto& shadowRoots = aDoc.ComposedShadowRoots();
+  for (auto iter = shadowRoots.ConstIter(); !iter.Done(); iter.Next()) {
+    ShadowRoot* root = iter.Get()->GetKey();
+    MOZ_ASSERT(root);
+    MOZ_DIAGNOSTIC_ASSERT(root->IsComposedDocParticipant());
+    aCb(*root);
+  }
 }
 
 void
 ServoStyleSet::Shutdown()
 {
   // Make sure we drop our cached styles before the presshell arena starts going
   // away.
   ClearNonInheritingComputedStyles();