--- a/dom/base/ShadowRoot.cpp
+++ b/dom/base/ShadowRoot.cpp
@@ -203,22 +203,28 @@ ShadowRoot::RemoveSlot(HTMLSlotElement* 
       }
     }
   }
 }
 
 void
 ShadowRoot::StyleSheetChanged()
 {
-  mProtoBinding->FlushSkinSheets();
+  nsIDocument* doc = OwnerDoc();
 
-  if (nsIPresShell* shell = OwnerDoc()->GetShell()) {
-    OwnerDoc()->BeginUpdate(UPDATE_STYLE);
-    shell->RecordShadowStyleChange(this);
-    OwnerDoc()->EndUpdate(UPDATE_STYLE);
+  if (doc->IsStyledByServo()) {
+    mProtoBinding->SyncServoStyles();
+  } else {
+    mProtoBinding->FlushSkinSheets();
+  }
+
+  if (nsIPresShell* shell = doc->GetShell()) {
+    doc->BeginUpdate(UPDATE_STYLE);
+    shell->RecordShadowStyleChange(*this);
+    doc->EndUpdate(UPDATE_STYLE);
   }
 }
 
 void
 ShadowRoot::InsertSheet(StyleSheet* aSheet,
                         nsIContent* aLinkingContent)
 {
   nsCOMPtr<nsIStyleSheetLinkingElement>

--- a/dom/xbl/nsXBLPrototypeBinding.h
+++ b/dom/xbl/nsXBLPrototypeBinding.h
@@ -131,20 +131,28 @@ public:
   mozilla::StyleSheet* StyleSheetAt(size_t aIndex) const;
   size_t SheetCount() const;
   bool HasStyleSheets() const;
   void AppendStyleSheetsTo(nsTArray<mozilla::StyleSheet*>& aResult) const;
 
 #ifdef MOZ_OLD_STYLE
   nsIStyleRuleProcessor* GetRuleProcessor();
 #endif
+
   const RawServoAuthorStyles* GetServoStyles() const
   {
     return mResources ? mResources->GetServoStyles() : nullptr;
   }
+
+  void SyncServoStyles()
+  {
+    MOZ_ASSERT(mResources);
+    mResources->SyncServoStyles();
+  }
+
   RawServoAuthorStyles* GetServoStyles()
   {
     return mResources
       ? const_cast<RawServoAuthorStyles*>(mResources->GetServoStyles())
       : nullptr;
   }
 
   mozilla::ServoStyleRuleMap* GetServoStyleRuleMap()

--- a/dom/xbl/nsXBLPrototypeResources.cpp
+++ b/dom/xbl/nsXBLPrototypeResources.cpp
@@ -182,23 +182,29 @@ nsXBLPrototypeResources::GatherRuleProce
   mRuleProcessor = new nsCSSRuleProcessor(Move(sheets),
                                           SheetType::Doc,
                                           nullptr,
                                           mRuleProcessor);
 }
 #endif
 
 void
-nsXBLPrototypeResources::ComputeServoStyles(const ServoStyleSet& aMasterStyleSet)
+nsXBLPrototypeResources::SyncServoStyles()
 {
   mStyleRuleMap.reset(nullptr);
   mServoStyles.reset(Servo_AuthorStyles_Create());
   for (auto& sheet : mStyleSheetList) {
     Servo_AuthorStyles_AppendStyleSheet(mServoStyles.get(), sheet->AsServo());
   }
+}
+
+void
+nsXBLPrototypeResources::ComputeServoStyles(const ServoStyleSet& aMasterStyleSet)
+{
+  SyncServoStyles();
   Servo_AuthorStyles_Flush(mServoStyles.get(), aMasterStyleSet.RawSet());
 }
 
 ServoStyleRuleMap*
 nsXBLPrototypeResources::GetServoStyleRuleMap()
 {
   if (!HasStyleSheets() || !mServoStyles) {
     return nullptr;

--- a/dom/xbl/nsXBLPrototypeResources.h
+++ b/dom/xbl/nsXBLPrototypeResources.h
@@ -78,16 +78,18 @@ public:
   nsCSSRuleProcessor* GetRuleProcessor() const { return mRuleProcessor; }
 #endif
 
   const RawServoAuthorStyles* GetServoStyles() const
   {
     return mServoStyles.get();
   }
 
+  void SyncServoStyles();
+
   mozilla::ServoStyleRuleMap* GetServoStyleRuleMap();
 
   // Updates the ServoStyleSet object that holds the result of cascading the
   // sheets in mStyleSheetList. Equivalent to GatherRuleProcessor(), but for
   // the Servo style backend.
   void ComputeServoStyles(const mozilla::ServoStyleSet& aMasterStyleSet);
 
   size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;

--- a/layout/base/PresShell.cpp
+++ b/layout/base/PresShell.cpp
@@ -6305,17 +6305,17 @@ public:
   }
 
 private:
   PresShell* mShell;
   uint32_t mFlags;
 };
 
 void
-PresShell::RecordShadowStyleChange(ShadowRoot* aShadowRoot)
+nsIPresShell::RecordShadowStyleChange(ShadowRoot& aShadowRoot)
 {
   mStyleSet->RecordShadowStyleChange(aShadowRoot);
 }
 
 void
 PresShell::Paint(nsView*         aViewToPaint,
                  const nsRegion& aDirtyRegion,
                  uint32_t        aFlags)

--- a/layout/base/PresShell.h
+++ b/layout/base/PresShell.h
@@ -387,19 +387,16 @@ public:
   void RebuildApproximateFrameVisibility(nsRect* aRect = nullptr,
                                          bool aRemoveOnly = false) override;
 
   void EnsureFrameInApproximatelyVisibleList(nsIFrame* aFrame) override;
   void RemoveFrameFromApproximatelyVisibleList(nsIFrame* aFrame) override;
 
   bool AssumeAllFramesVisible() override;
 
-
-  virtual void RecordShadowStyleChange(mozilla::dom::ShadowRoot* aShadowRoot) override;
-
   virtual bool CanDispatchEvent(
       const mozilla::WidgetGUIEvent* aEvent = nullptr) const override;
 
   void SetNextPaintCompressed() { mNextPaintCompressed = true; }
 
   void NotifyStyleSheetServiceSheetAdded(mozilla::StyleSheet* aSheet,
                                          uint32_t aSheetType) override;
   void NotifyStyleSheetServiceSheetRemoved(mozilla::StyleSheet* aSheet,

--- a/layout/base/nsIPresShell.h
+++ b/layout/base/nsIPresShell.h
@@ -535,20 +535,20 @@ public:
    * Note that this may destroy frames for an ancestor instead.
    */
   virtual void DestroyFramesForAndRestyle(mozilla::dom::Element* aElement) = 0;
 
   void PostRecreateFramesFor(mozilla::dom::Element* aElement);
   void RestyleForAnimation(mozilla::dom::Element* aElement,
                            nsRestyleHint aHint);
 
-  // ShadowRoot has APIs that can change styles so we only
-  // want to restyle elements in the ShadowRoot and not the whole
-  // document.
-  virtual void RecordShadowStyleChange(mozilla::dom::ShadowRoot* aShadowRoot) = 0;
+  // ShadowRoot has APIs that can change styles. This notifies the shell that
+  // stlyes applicable in the shadow tree have potentially changed.
+  void RecordShadowStyleChange(mozilla::dom::ShadowRoot& aShadowRoot);
+
 
   /**
    * Determine if it is safe to flush all pending notifications.
    */
   bool IsSafeToFlush() const;
 
   /**
    * Flush pending notifications of the type specified.  This method

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -156,16 +156,26 @@ ServoStyleSet::Init(nsPresContext* aPres
                  "We should only append non-null raw sheets.");
       Servo_StyleSet_AppendStyleSheet(mRawSet.get(), sheet);
     }
   }
 
   // We added prefilled stylesheets into mRawSet, so the stylist is dirty.
   // The Stylist should be updated later when necessary.
   SetStylistStyleSheetsDirty();
+
+  // We may have Shadow DOM style changes that we weren't notified about because
+  // the document didn't have a shell, if the ShadowRoot was created in a
+  // display: none iframe.
+  //
+  // 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();
 }
 
 void
 ServoStyleSet::Shutdown()
 {
   // Make sure we drop our cached style contexts before the presshell arena
   // starts going away.
   ClearNonInheritingStyleContexts();
@@ -178,16 +188,30 @@ ServoStyleSet::InvalidateStyleForCSSRule
 {
   MOZ_ASSERT(StylistNeedsUpdate());
   if (nsPresContext* pc = GetPresContext()) {
     pc->RestyleManager()->AsServo()->PostRestyleEventForCSSRuleChanges();
   }
 }
 
 void
+ServoStyleSet::RecordShadowStyleChange(ShadowRoot& aShadowRoot)
+{
+  // TODO(emilio): We could keep track of the actual shadow roots that need
+  // their styles recomputed.
+  SetStylistXBLStyleSheetsDirty();
+
+  // FIXME(emilio): This should be done using stylesheet invalidation instead.
+  if (nsPresContext* pc = GetPresContext()) {
+    pc->RestyleManager()->PostRestyleEvent(
+      aShadowRoot.Host(), eRestyle_Subtree, nsChangeHint(0));
+  }
+}
+
+void
 ServoStyleSet::InvalidateStyleForDocumentStateChanges(EventStates aStatesChanged)
 {
   MOZ_ASSERT(mDocument);
   MOZ_ASSERT(!aStatesChanged.IsEmpty());
 
   nsPresContext* pc = GetPresContext();
   if (!pc) {
     return;

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -115,21 +115,17 @@ public:
 
   // All the relevant changes are handled in RuleAdded / RuleRemoved / etc, and
   // the relevant AppendSheet / RemoveSheet...
   void RecordStyleSheetChange(ServoStyleSheet*, StyleSheet::ChangeType) {}
 
   // Runs style invalidation due to document state changes.
   void InvalidateStyleForDocumentStateChanges(EventStates aStatesChanged);
 
-  void RecordShadowStyleChange(dom::ShadowRoot* aShadowRoot) {
-    // FIXME(emilio): When we properly support shadow dom we'll need to do
-    // better.
-    MarkOriginsDirty(OriginFlags::All);
-  }
+  void RecordShadowStyleChange(dom::ShadowRoot&);
 
   bool StyleSheetsHaveChanged() const
   {
     return StylistNeedsUpdate();
   }
 
   nsRestyleHint MediumFeaturesChanged(MediaFeatureChangeReason);
 

--- a/layout/style/StyleSetHandle.h
+++ b/layout/style/StyleSetHandle.h
@@ -187,17 +187,17 @@ public:
     inline nsresult AddDocStyleSheet(StyleSheet* aSheet, nsIDocument* aDocument);
 
     inline void RuleRemoved(StyleSheet&, css::Rule&);
     inline void RuleAdded(StyleSheet&, css::Rule&);
     inline void RuleChanged(StyleSheet&, css::Rule*);
 
     // TODO(emilio): Remove in favor of Rule* methods.
     inline void RecordStyleSheetChange(StyleSheet* aSheet, StyleSheet::ChangeType);
-    inline void RecordShadowStyleChange(mozilla::dom::ShadowRoot* aShadowRoot);
+    inline void RecordShadowStyleChange(mozilla::dom::ShadowRoot& aShadowRoot);
     inline bool StyleSheetsHaveChanged() const;
     inline void InvalidateStyleForCSSRuleChanges();
     inline nsRestyleHint MediumFeaturesChanged(mozilla::MediaFeatureChangeReason);
     inline already_AddRefed<nsStyleContext>
     ProbePseudoElementStyle(dom::Element* aParentElement,
                             mozilla::CSSPseudoElementType aType,
                             nsStyleContext* aParentContext);
     inline already_AddRefed<nsStyleContext>

--- a/layout/style/StyleSetHandleInlines.h
+++ b/layout/style/StyleSetHandleInlines.h
@@ -301,17 +301,17 @@ void
 StyleSetHandle::Ptr::RecordStyleSheetChange(StyleSheet* aSheet,
                                             StyleSheet::ChangeType aChangeType)
 {
   FORWARD_CONCRETE(RecordStyleSheetChange, (aSheet->AsGecko(), aChangeType),
                                            (aSheet->AsServo(), aChangeType));
 }
 
 void
-StyleSetHandle::Ptr::RecordShadowStyleChange(mozilla::dom::ShadowRoot* aShadowRoot)
+StyleSetHandle::Ptr::RecordShadowStyleChange(mozilla::dom::ShadowRoot& aShadowRoot)
 {
   FORWARD(RecordShadowStyleChange, (aShadowRoot));
 }
 
 bool
 StyleSetHandle::Ptr::StyleSheetsHaveChanged() const
 {
   FORWARD(StyleSheetsHaveChanged, ());

--- a/layout/style/nsStyleSet.cpp
+++ b/layout/style/nsStyleSet.cpp
@@ -2362,23 +2362,23 @@ nsStyleSet::SheetChanged(CSSStyleSheet& 
 
   mStylesHaveChanged = true;
   // If we need to restyle everything, no need to restyle individual
   // scoped style roots.
   mChangedScopeStyleRoots.Clear();
 }
 
 void
-nsStyleSet::RecordShadowStyleChange(ShadowRoot* aShadowRoot)
+nsStyleSet::RecordShadowStyleChange(ShadowRoot& aShadowRoot)
 {
   if (mStylesHaveChanged) {
     return;
   }
 
-  mChangedScopeStyleRoots.AppendElement(aShadowRoot->GetHost()->AsElement());
+  mChangedScopeStyleRoots.AppendElement(aShadowRoot.Host());
 }
 
 void
 nsStyleSet::InvalidateStyleForCSSRuleChanges()
 {
   MOZ_ASSERT(!mStylesHaveChanged || mChangedScopeStyleRoots.IsEmpty());
 
   AutoTArray<RefPtr<mozilla::dom::Element>, 1> scopeRoots;

--- a/layout/style/nsStyleSet.h
+++ b/layout/style/nsStyleSet.h
@@ -362,17 +362,17 @@ class nsStyleSet final
                               mozilla::StyleSheet::ChangeType)
   {
     SheetChanged(*aSheet);
   }
 
   void SheetChanged(mozilla::CSSStyleSheet&);
 
   // Notes that style sheets have changed in a shadow root.
-  void RecordShadowStyleChange(mozilla::dom::ShadowRoot* aShadowRoot);
+  void RecordShadowStyleChange(mozilla::dom::ShadowRoot& aShadowRoot);
 
   bool StyleSheetsHaveChanged() const
   {
     return mStylesHaveChanged || !mChangedScopeStyleRoots.IsEmpty();
   }
 
   void InvalidateStyleForCSSRuleChanges();
 

deleted file mode 100644
--- a/testing/web-platform/meta/shadow-dom/untriaged/styles/test-005.html.ini
+++ /dev/null
@@ -1,5 +0,0 @@
-[test-005.html]
-  [A_06_00_06_T01]
-    expected:
-      if stylo: FAIL
-