new file mode 100644
--- /dev/null
+++ b/layout/inspector/ServoStyleRuleMap.cpp
@@ -0,0 +1,160 @@
+/* -*- 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/ServoStyleRuleMap.h"
+
+#include "mozilla/css/GroupRule.h"
+#include "mozilla/IntegerRange.h"
+#include "mozilla/ServoStyleRule.h"
+#include "mozilla/ServoStyleSet.h"
+#include "mozilla/ServoImportRule.h"
+
+#include "nsDocument.h"
+#include "nsStyleSheetService.h"
+
+namespace mozilla {
+
+ServoStyleRuleMap::ServoStyleRuleMap(ServoStyleSet* aStyleSet)
+  : mStyleSet(aStyleSet)
+{
+}
+
+ServoStyleRuleMap::~ServoStyleRuleMap()
+{
+}
+
+NS_IMPL_ISUPPORTS(ServoStyleRuleMap, nsIDocumentObserver)
+
+void
+ServoStyleRuleMap::EnsureTable()
+{
+  if (!IsEmpty()) {
+    return;
+  }
+  mStyleSet->EnumerateStyleSheetArrays(
+    [this](const nsTArray<RefPtr<ServoStyleSheet>>& aArray) {
+      for (auto& sheet : aArray) {
+        FillTableFromStyleSheet(sheet);
+      }
+    });
+}
+
+void
+ServoStyleRuleMap::StyleSheetAdded(StyleSheet* aStyleSheet,
+                                   bool aDocumentSheet)
+{
+  if (!IsEmpty()) {
+    FillTableFromStyleSheet(aStyleSheet->AsServo());
+  }
+}
+
+void
+ServoStyleRuleMap::StyleSheetRemoved(StyleSheet* aStyleSheet,
+                                     bool aDocumentSheet)
+{
+  // Invalidate all data inside. This isn't strictly necessary since
+  // we should always get update from document before new queries come.
+  // But it is probably still safer if we try to avoid having invalid
+  // pointers inside. Also if the document keep adding and removing
+  // stylesheets, this would also prevent us from infinitely growing
+  // memory usage.
+  mTable.Clear();
+}
+
+void
+ServoStyleRuleMap::StyleSheetApplicableStateChanged(StyleSheet* aStyleSheet)
+{
+  // We don't care if the stylesheet is disabled. Not removing no longer
+  // applicable stylesheets wouldn't make anything wrong.
+  if (!IsEmpty() && aStyleSheet->IsApplicable()) {
+    FillTableFromStyleSheet(aStyleSheet->AsServo());
+  }
+}
+
+void
+ServoStyleRuleMap::StyleRuleAdded(StyleSheet* aStyleSheet,
+                                  css::Rule* aStyleRule)
+{
+  if (!IsEmpty()) {
+    FillTableFromRule(aStyleRule);
+  }
+}
+
+void
+ServoStyleRuleMap::StyleRuleRemoved(StyleSheet* aStyleSheet,
+                                    css::Rule* aStyleRule)
+{
+  if (IsEmpty()) {
+    return;
+  }
+
+  switch (aStyleRule->Type()) {
+    case nsIDOMCSSRule::STYLE_RULE: {
+      auto rule = static_cast<ServoStyleRule*>(aStyleRule);
+      mTable.Remove(rule->Raw());
+      break;
+    }
+    case nsIDOMCSSRule::IMPORT_RULE:
+    case nsIDOMCSSRule::MEDIA_RULE:
+    case nsIDOMCSSRule::SUPPORTS_RULE:
+    case nsIDOMCSSRule::DOCUMENT_RULE: {
+      // See the comment in StyleSheetRemoved.
+      mTable.Clear();
+      break;
+    }
+  }
+}
+
+size_t
+ServoStyleRuleMap::SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
+{
+  size_t n = aMallocSizeOf(this);
+  n += mTable.ShallowSizeOfExcludingThis(aMallocSizeOf);
+  return n;
+}
+
+void
+ServoStyleRuleMap::FillTableFromRule(css::Rule* aRule)
+{
+  switch (aRule->Type()) {
+    case nsIDOMCSSRule::STYLE_RULE: {
+      auto rule = static_cast<ServoStyleRule*>(aRule);
+      mTable.Put(rule->Raw(), rule);
+      break;
+    }
+    case nsIDOMCSSRule::MEDIA_RULE:
+    case nsIDOMCSSRule::SUPPORTS_RULE:
+    case nsIDOMCSSRule::DOCUMENT_RULE: {
+      auto rule = static_cast<css::GroupRule*>(aRule);
+      auto ruleList = static_cast<ServoCSSRuleList*>(rule->CssRules());
+      FillTableFromRuleList(ruleList);
+      break;
+    }
+    case nsIDOMCSSRule::IMPORT_RULE: {
+      auto rule = static_cast<ServoImportRule*>(aRule);
+      FillTableFromStyleSheet(rule->GetStyleSheet()->AsServo());
+      break;
+    }
+  }
+}
+
+void
+ServoStyleRuleMap::FillTableFromRuleList(ServoCSSRuleList* aRuleList)
+{
+  for (uint32_t i : IntegerRange(aRuleList->Length())) {
+    FillTableFromRule(aRuleList->GetRule(i));
+  }
+}
+
+void
+ServoStyleRuleMap::FillTableFromStyleSheet(ServoStyleSheet* aSheet)
+{
+  nsAutoCString url;
+  aSheet->GetSheetURI()->GetSpec(url);
+  FillTableFromRuleList(aSheet->GetCssRulesInternal());
+}
+
+} // namespace mozilla

new file mode 100644
--- /dev/null
+++ b/layout/inspector/ServoStyleRuleMap.h
@@ -0,0 +1,62 @@
+/* -*- 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_ServoStyleRuleMap_h
+#define mozilla_ServoStyleRuleMap_h
+
+#include "mozilla/ServoStyleRule.h"
+
+#include "nsDataHashtable.h"
+#include "nsStubDocumentObserver.h"
+
+struct RawServoStyleRule;
+
+namespace mozilla {
+class ServoCSSRuleList;
+class ServoStyleSet;
+namespace css {
+class Rule;
+} // namespace css
+
+class ServoStyleRuleMap final : public nsStubDocumentObserver
+{
+public:
+  NS_DECL_ISUPPORTS
+
+  explicit ServoStyleRuleMap(ServoStyleSet* aStyleSet);
+
+  void EnsureTable();
+  ServoStyleRule* Lookup(const RawServoStyleRule* aRawRule) const {
+    return mTable.Get(aRawRule);
+  }
+
+  // nsIDocumentObserver methods
+  void StyleSheetAdded(StyleSheet* aStyleSheet, bool aDocumentSheet) final;
+  void StyleSheetRemoved(StyleSheet* aStyleSheet, bool aDocumentSheet) final;
+  void StyleSheetApplicableStateChanged(StyleSheet* aStyleSheet) final;
+  void StyleRuleAdded(StyleSheet* aStyleSheet, css::Rule* aStyleRule) final;
+  void StyleRuleRemoved(StyleSheet* aStyleSheet, css::Rule* aStyleRule) final;
+
+  size_t SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const;
+
+private:
+  ~ServoStyleRuleMap();
+
+  bool IsEmpty() const { return mTable.Count() == 0; }
+
+  void FillTableFromRule(css::Rule* aRule);
+  void FillTableFromRuleList(ServoCSSRuleList* aRuleList);
+  void FillTableFromStyleSheet(ServoStyleSheet* aSheet);
+
+  typedef nsDataHashtable<nsPtrHashKey<const RawServoStyleRule>,
+                          WeakPtr<ServoStyleRule>> Hashtable;
+  Hashtable mTable;
+  ServoStyleSet* mStyleSet;
+};
+
+} // namespace mozilla
+
+#endif // mozilla_ServoStyleRuleMap_h

--- a/layout/inspector/inDOMUtils.cpp
+++ b/layout/inspector/inDOMUtils.cpp
@@ -46,18 +46,18 @@
 #include "nsCSSParser.h"
 #include "nsCSSProps.h"
 #include "nsCSSValue.h"
 #include "nsColor.h"
 #include "mozilla/StyleSetHandleInlines.h"
 #include "nsStyleUtil.h"
 #include "nsQueryObject.h"
 #include "mozilla/ServoBindings.h"
-#include "mozilla/ServoCSSRuleList.h"
 #include "mozilla/ServoStyleRule.h"
+#include "mozilla/ServoStyleRuleMap.h"
 
 using namespace mozilla;
 using namespace mozilla::css;
 using namespace mozilla::dom;
 
 ///////////////////////////////////////////////////////////////////////////////
 
 inDOMUtils::inDOMUtils()
@@ -266,49 +266,35 @@ inDOMUtils::GetCSSStyleRules(nsIDOMEleme
         }
       }
     }
   } else {
     // It's a Servo source, so use some servo methods on the element to get
     // the rule list.
     nsTArray<const RawServoStyleRule*> rawRuleList;
     Servo_Element_GetStyleRuleList(element, &rawRuleList);
-    size_t rawRuleCount = rawRuleList.Length();
 
-    // We have RawServoStyleRules, and now we'll map them to ServoStyleRules
-    // by looking them up in the ServoStyleSheets owned by this document.
-    ServoCSSRuleList::StyleRuleHashtable rawRulesToRules;
-
-    nsIDocument* document = element->GetOwnerDocument();
-    int32_t sheetCount = document->GetNumberOfStyleSheets();
-
-    for (int32_t i = 0; i < sheetCount; i++) {
-      StyleSheet* sheet = document->GetStyleSheetAt(i);
-      MOZ_ASSERT(sheet->IsServo());
-
-      ErrorResult ignored;
-      ServoCSSRuleList* ruleList = static_cast<ServoCSSRuleList*>(
-        sheet->GetCssRules(*nsContentUtils::SubjectPrincipal(), ignored));
-      if (ruleList) {
-        // Generate the map from raw rules to rules.
-        ruleList->FillStyleRuleHashtable(rawRulesToRules);
-      }
+    nsIDocument* doc = element->GetOwnerDocument();
+    nsIPresShell* shell = doc->GetShell();
+    if (!shell) {
+      return NS_OK;
     }
 
+    ServoStyleSet* styleSet = shell->StyleSet()->AsServo();
+    ServoStyleRuleMap* map = styleSet->StyleRuleMap();
+    map->EnsureTable();
+
     // Find matching rules in the table.
-    for (size_t j = 0; j < rawRuleCount; j++) {
-      const RawServoStyleRule* rawRule = rawRuleList.ElementAt(j);
-      ServoStyleRule* rule = nullptr;
-      if (rawRulesToRules.Get(rawRule, &rule)) {
-        MOZ_ASSERT(rule, "rule should not be null");
-        RefPtr<css::Rule> ruleObj(rule);
-        rules->AppendElement(ruleObj, false);
+    for (const RawServoStyleRule* rawRule : Reversed(rawRuleList)) {
+      nsAutoCString text;
+      Servo_StyleRule_Debug(rawRule, &text);
+      if (ServoStyleRule* rule = map->Lookup(rawRule)) {
+        rules->AppendElement(static_cast<css::Rule*>(rule), false);
       } else {
-        // FIXME (bug 1359217): Need a reliable way to map raw rules to rules.
-        NS_WARNING("stylo: Could not map raw rule to a rule.");
+        MOZ_ASSERT_UNREACHABLE("We should be able to map a raw rule to a rule");
       }
     }
   }
 
   rules.forget(_retval);
 
   return NS_OK;
 }

--- a/layout/inspector/moz.build
+++ b/layout/inspector/moz.build
@@ -21,23 +21,28 @@ XPIDL_SOURCES += [
 
 XPIDL_MODULE = 'inspector'
 
 EXPORTS += [
     'nsFontFace.h',
     'nsFontFaceList.h',
 ]
 
+EXPORTS.mozilla += [
+    'ServoStyleRuleMap.h',
+]
+
 UNIFIED_SOURCES += [
     'inCSSValueSearch.cpp',
     'inDeepTreeWalker.cpp',
     'inDOMUtils.cpp',
     'inLayoutUtils.cpp',
     'nsFontFace.cpp',
     'nsFontFaceList.cpp',
+    'ServoStyleRuleMap.cpp',
 ]
 
 if CONFIG['MOZ_XUL']:
     UNIFIED_SOURCES += [
         'inDOMView.cpp',
     ]
 
 FINAL_LIBRARY = 'xul'

--- a/layout/style/ServoCSSRuleList.cpp
+++ b/layout/style/ServoCSSRuleList.cpp
@@ -304,36 +304,14 @@ ServoCSSRuleList::GetRuleType(uint32_t a
 {
   uintptr_t rule = mRules[aIndex];
   if (rule <= kMaxRuleType) {
     return rule;
   }
   return CastToPtr(rule)->Type();
 }
 
-void
-ServoCSSRuleList::FillStyleRuleHashtable(StyleRuleHashtable& aTable)
-{
-  for (uint32_t i = 0; i < mRules.Length(); i++) {
-    uint16_t type = GetRuleType(i);
-    if (type == nsIDOMCSSRule::STYLE_RULE) {
-      ServoStyleRule* castedRule = static_cast<ServoStyleRule*>(GetRule(i));
-      RawServoStyleRule* rawRule = castedRule->Raw();
-      aTable.Put(rawRule, castedRule);
-    } else if (type == nsIDOMCSSRule::MEDIA_RULE ||
-               type == nsIDOMCSSRule::SUPPORTS_RULE ||
-               type == nsIDOMCSSRule::DOCUMENT_RULE) {
-      auto castedRule = static_cast<css::GroupRule*>(GetRule(i));
-
-      // Call this method recursively on the ServoCSSRuleList in the rule.
-      ServoCSSRuleList* castedRuleList = static_cast<ServoCSSRuleList*>(
-        castedRule->CssRules());
-      castedRuleList->FillStyleRuleHashtable(aTable);
-    }
-  }
-}
-
 ServoCSSRuleList::~ServoCSSRuleList()
 {
   DropAllRules();
 }
 
 } // namespace mozilla

--- a/layout/style/ServoCSSRuleList.h
+++ b/layout/style/ServoCSSRuleList.h
@@ -46,20 +46,16 @@ public:
   void DropReference();
 
   css::Rule* GetRule(uint32_t aIndex);
   nsresult InsertRule(const nsAString& aRule, uint32_t aIndex);
   nsresult DeleteRule(uint32_t aIndex);
 
   uint16_t GetRuleType(uint32_t aIndex) const;
 
-  typedef nsDataHashtable<nsPtrHashKey<const RawServoStyleRule>,
-                          ServoStyleRule*> StyleRuleHashtable;
-  void FillStyleRuleHashtable(StyleRuleHashtable& aTable);
-
 private:
   virtual ~ServoCSSRuleList();
 
   // XXX Is it possible to have an address lower than or equal to 255?
   //     Is it possible to have more than 255 CSS rule types?
   static const uintptr_t kMaxRuleType = UINT8_MAX;
 
   static uintptr_t CastToUint(css::Rule* aPtr) {

--- a/layout/style/ServoStyleRule.h
+++ b/layout/style/ServoStyleRule.h
@@ -6,16 +6,17 @@
 
 /* representation of CSSStyleRule for stylo */
 
 #ifndef mozilla_ServoStyleRule_h
 #define mozilla_ServoStyleRule_h
 
 #include "mozilla/BindingStyleRule.h"
 #include "mozilla/ServoBindingTypes.h"
+#include "mozilla/WeakPtr.h"
 
 #include "nsICSSStyleRuleDOMWrapper.h"
 #include "nsIDOMCSSStyleRule.h"
 #include "nsICSSStyleRuleDOMWrapper.h"
 #include "nsDOMCSSDeclaration.h"
 
 namespace mozilla {
 
@@ -48,27 +49,30 @@ private:
   inline ServoStyleRule* Rule();
   inline const ServoStyleRule* Rule() const;
 
   RefPtr<ServoDeclarationBlock> mDecls;
 };
 
 class ServoStyleRule final : public BindingStyleRule
                            , public nsICSSStyleRuleDOMWrapper
+                           , public SupportsWeakPtr<ServoStyleRule>
 {
 public:
   ServoStyleRule(already_AddRefed<RawServoStyleRule> aRawRule,
                  uint32_t aLine, uint32_t aColumn);
 
   NS_DECL_ISUPPORTS_INHERITED
   NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_CLASS_INHERITED(ServoStyleRule,
                                                          css::Rule)
   bool IsCCLeaf() const final MOZ_MUST_OVERRIDE;
   NS_DECL_NSIDOMCSSSTYLERULE
 
+  MOZ_DECLARE_WEAKREFERENCE_TYPENAME(ServoStyleRule)
+
   // nsICSSStyleRuleDOMWrapper
   NS_IMETHOD GetCSSStyleRule(BindingStyleRule **aResult) override;
 
   uint32_t GetSelectorCount() override;
   nsresult GetSelectorText(uint32_t aSelectorIndex,
                            nsAString& aText) override;
   nsresult GetSpecificity(uint32_t aSelectorIndex,
                           uint64_t* aSpecificity) override;

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -5,16 +5,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mozilla/ServoStyleSet.h"
 
 #include "gfxPlatformFontList.h"
 #include "mozilla/DocumentStyleRootIterator.h"
 #include "mozilla/ServoBindings.h"
 #include "mozilla/ServoRestyleManager.h"
+#include "mozilla/ServoStyleRuleMap.h"
 #include "mozilla/dom/AnonymousContent.h"
 #include "mozilla/dom/ChildIterator.h"
 #include "mozilla/dom/Element.h"
 #include "mozilla/dom/ElementInlines.h"
 #include "mozilla/RestyleManagerInlines.h"
 #include "nsCSSAnonBoxes.h"
 #include "nsCSSPseudoElements.h"
 #include "nsCSSRuleProcessor.h"
@@ -87,16 +88,22 @@ ServoStyleSet::Init(nsPresContext* aPres
   // mRawSet, so there was nothing to flush.
 }
 
 void
 ServoStyleSet::BeginShutdown()
 {
   nsIDocument* doc = mPresContext->Document();
 
+  // Remove the style rule map from document's observer and drop it.
+  if (mStyleRuleMap) {
+    doc->RemoveObserver(mStyleRuleMap);
+    mStyleRuleMap = nullptr;
+  }
+
   // It's important to do this before mRawSet is released, since that will cause
   // a RuleTree GC, which needs to happen after we have dropped all of the
   // document's strong references to RuleNodes.  We also need to do it here,
   // in BeginShutdown, and not in Shutdown, since Shutdown happens after the
   // frame tree has been destroyed, but before the script runners that delete
   // native anonymous content (which also could be holding on the RuleNodes)
   // have run.  By clearing style here, before the frame tree is destroyed,
   // the AllChildrenIterator will find the anonymous content.
@@ -140,16 +147,20 @@ ServoStyleSet::MediumFeaturesChanged() c
   return Servo_StyleSet_MediumFeaturesChanged(mRawSet.get());
 }
 
 size_t
 ServoStyleSet::SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
 {
   size_t n = aMallocSizeOf(this);
 
+  if (mStyleRuleMap) {
+    n += mStyleRuleMap->SizeOfIncludingThis(aMallocSizeOf);
+  }
+
   // Measurement of the following members may be added later if DMD finds it is
   // worthwhile:
   // - mRawSet
   // - mSheets
   // - mNonInheritingStyleContexts
   //
   // The following members are not measured:
   // - mPresContext, because it a non-owning pointer
@@ -1351,9 +1362,19 @@ ServoStyleSet::RunPostTraversalTasks()
   nsTArray<PostTraversalTask> tasks;
   tasks.SwapElements(mPostTraversalTasks);
 
   for (auto& task : tasks) {
     task.Run();
   }
 }
 
+ServoStyleRuleMap*
+ServoStyleSet::StyleRuleMap()
+{
+  if (!mStyleRuleMap) {
+    mStyleRuleMap = new ServoStyleRuleMap(this);
+    mPresContext->Document()->AddObserver(mStyleRuleMap);
+  }
+  return mStyleRuleMap;
+}
+
 ServoStyleSet* ServoStyleSet::sInServoTraversal = nullptr;

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -28,16 +28,17 @@ namespace mozilla {
 namespace dom {
 class Element;
 } // namespace dom
 class CSSStyleSheet;
 class ServoRestyleManager;
 class ServoStyleSheet;
 struct Keyframe;
 class ServoElementSnapshotTable;
+class ServoStyleRuleMap;
 } // namespace mozilla
 class nsCSSCounterStyleRule;
 class nsIContent;
 class nsIDocument;
 class nsStyleContext;
 class nsPresContext;
 struct nsTimingFunction;
 struct RawServoRuleNode;
@@ -243,16 +244,23 @@ public:
                          const nsTArray<RefPtr<ServoStyleSheet>>& aNewSheets);
   nsresult InsertStyleSheetBefore(SheetType aType,
                                   ServoStyleSheet* aNewSheet,
                                   ServoStyleSheet* aReferenceSheet);
 
   int32_t SheetCount(SheetType aType) const;
   ServoStyleSheet* StyleSheetAt(SheetType aType, int32_t aIndex) const;
 
+  template<typename Func>
+  void EnumerateStyleSheetArrays(Func aCallback) const {
+    for (const auto& sheetArray : mSheets) {
+      aCallback(sheetArray);
+    }
+  }
+
   nsresult RemoveDocStyleSheet(ServoStyleSheet* aSheet);
   nsresult AddDocStyleSheet(ServoStyleSheet* aSheet, nsIDocument* aDocument);
 
   // check whether there is ::before/::after style for an element
   already_AddRefed<nsStyleContext>
   ProbePseudoElementStyle(dom::Element* aOriginatingElement,
                           mozilla::CSSPseudoElementType aType,
                           nsStyleContext* aParentContext,
@@ -427,16 +435,19 @@ public:
   bool EnsureUniqueInnerOnCSSSheets();
 
   // Called by StyleSheet::EnsureUniqueInner to let us know it cloned
   // its inner.
   void SetNeedsRestyleAfterEnsureUniqueInner() {
     mNeedsRestyleAfterEnsureUniqueInner = true;
   }
 
+  // Returns the style rule map.
+  ServoStyleRuleMap* StyleRuleMap();
+
 private:
   // On construction, sets sInServoTraversal to the given ServoStyleSet.
   // On destruction, clears sInServoTraversal and calls RunPostTraversalTasks.
   class MOZ_STACK_CLASS AutoSetInServoTraversal
   {
   public:
     explicit AutoSetInServoTraversal(ServoStyleSet* aSet)
       : mSet(aSet)
@@ -578,14 +589,18 @@ private:
                   RefPtr<nsStyleContext>> mNonInheritingStyleContexts;
 
   // Tasks to perform after a traversal, back on the main thread.
   //
   // These are similar to Servo's SequentialTasks, except that they are
   // posted by C++ code running on style worker threads.
   nsTArray<PostTraversalTask> mPostTraversalTasks;
 
+  // Map from raw Servo style rule to Gecko's wrapper object.
+  // Constructed lazily when requested by devtools.
+  RefPtr<ServoStyleRuleMap> mStyleRuleMap;
+
   static ServoStyleSet* sInServoTraversal;
 };
 
 } // namespace mozilla
 
 #endif // mozilla_ServoStyleSet_h