--- a/dom/base/nsDocument.cpp
+++ b/dom/base/nsDocument.cpp
@@ -9629,36 +9629,48 @@ nsDocument::ForgetImagePreload(nsIURI* a
     mPreloadingImages.Remove(aURI, getter_AddRefs(req));
     if (req) {
       // Make sure to cancel the request so imagelib knows it's gone.
       req->CancelAndForgetObserver(NS_BINDING_ABORTED);
     }
   }
 }
 
-EventStates
-nsDocument::GetDocumentState()
+void
+nsDocument::UpdatePossiblyStaleDocumentState()
 {
   if (!mGotDocumentState.HasState(NS_DOCUMENT_STATE_RTL_LOCALE)) {
     if (IsDocumentRightToLeft()) {
       mDocumentState |= NS_DOCUMENT_STATE_RTL_LOCALE;
     }
     mGotDocumentState |= NS_DOCUMENT_STATE_RTL_LOCALE;
   }
   if (!mGotDocumentState.HasState(NS_DOCUMENT_STATE_WINDOW_INACTIVE)) {
     nsIPresShell* shell = GetShell();
     if (shell && shell->GetPresContext() &&
         shell->GetPresContext()->IsTopLevelWindowInactive()) {
       mDocumentState |= NS_DOCUMENT_STATE_WINDOW_INACTIVE;
     }
     mGotDocumentState |= NS_DOCUMENT_STATE_WINDOW_INACTIVE;
   }
+}
+
+EventStates
+nsDocument::ThreadSafeGetDocumentState() const
+{
   return mDocumentState;
 }
 
+EventStates
+nsDocument::GetDocumentState()
+{
+  UpdatePossiblyStaleDocumentState();
+  return ThreadSafeGetDocumentState();
+}
+
 namespace {
 
 /**
  * Stub for LoadSheet(), since all we want is to get the sheet into
  * the CSSLoader's style cache
  */
 class StubCSSLoaderObserver final : public nsICSSLoaderObserver {
   ~StubCSSLoaderObserver() {}

--- a/dom/base/nsDocument.h
+++ b/dom/base/nsDocument.h
@@ -975,17 +975,22 @@ public:
                             ReferrerPolicy aReferrerPolicy,
                             const nsAString& aIntegrity) override;
 
   virtual nsresult LoadChromeSheetSync(nsIURI* uri, bool isAgentSheet,
                                        RefPtr<mozilla::StyleSheet>* aSheet) override;
 
   virtual nsISupports* GetCurrentContentSink() override;
 
-  virtual mozilla::EventStates GetDocumentState() override;
+  virtual mozilla::EventStates GetDocumentState() final;
+  // GetDocumentState() mutates the state due to lazy resolution;
+  // and can't be used during parallel traversal. Use this instead,
+  // and ensure GetDocumentState() has been called first.
+  // This will assert if the state is stale.
+  virtual mozilla::EventStates ThreadSafeGetDocumentState() const final;
 
   // Only BlockOnload should call this!
   void AsyncBlockOnload();
 
   virtual void SetScrollToRef(nsIURI *aDocumentURI) override;
   virtual void ScrollToRef() override;
   virtual void ResetScrolledToRefAlready() override;
   virtual void SetChangeScrollPosWhenScrollingToRef(bool aValue) override;
@@ -1386,16 +1391,17 @@ protected:
   // non-null when this document is in fullscreen mode.
   nsWeakPtr mFullscreenRoot;
 
   mozilla::dom::FlashClassification mFlashClassification;
   // Do not use this value directly. Call the |IsThirdParty()| method, which
   // caches its result here.
   mozilla::Maybe<bool> mIsThirdParty;
 private:
+  void UpdatePossiblyStaleDocumentState();
   static bool CustomElementConstructor(JSContext* aCx, unsigned aArgc, JS::Value* aVp);
 
   /**
    * Check if the passed custom element name, aOptions.mIs, is a registered
    * custom element type or not, then return the custom element name for future
    * usage.
    *
    * If there is no existing custom element definition for this name, throw a

--- a/dom/base/nsIDocument.h
+++ b/dom/base/nsIDocument.h
@@ -2376,16 +2376,17 @@ public:
   virtual int GetDocumentLWTheme() { return Doc_Theme_None; }
 
   /**
    * Returns the document state.
    * Document state bits have the form NS_DOCUMENT_STATE_* and are declared in
    * nsIDocument.h.
    */
   virtual mozilla::EventStates GetDocumentState() = 0;
+  virtual mozilla::EventStates ThreadSafeGetDocumentState() const = 0;
 
   virtual nsISupports* GetCurrentContentSink() = 0;
 
   virtual void SetScrollToRef(nsIURI *aDocumentURI) = 0;
   virtual void ScrollToRef() = 0;
   virtual void ResetScrolledToRefAlready() = 0;
   virtual void SetChangeScrollPosWhenScrollingToRef(bool aValue) = 0;
 

--- a/layout/style/ServoBindings.cpp
+++ b/layout/style/ServoBindings.cpp
@@ -486,16 +486,29 @@ nscolor Gecko_GetLookAndFeelSystemColor(
 {
   bool useStandinsForNativeColors = aPresContext && !aPresContext->IsChrome();
   nscolor result;
   LookAndFeel::ColorID colorId = static_cast<LookAndFeel::ColorID>(aId);
   LookAndFeel::GetColor(colorId, useStandinsForNativeColors, &result);
   return result;
 }
 
+bool
+Gecko_MatchStringArgPseudo(RawGeckoElementBorrowed aElement,
+                           CSSPseudoClassType aType,
+                           const char16_t* aIdent,
+                           bool* aSetSlowSelectorFlag)
+{
+  MOZ_ASSERT(aElement->OwnerDoc() == aElement->GetComposedDoc());
+  EventStates dummyMask; // mask is never read because we pass aDependence=nullptr
+  return nsCSSRuleProcessor::StringPseudoMatches(aElement, aType, aIdent,
+                                                 aElement->OwnerDoc(), true,
+                                                 dummyMask, aSetSlowSelectorFlag, nullptr);
+}
+
 template <typename Implementor>
 static nsIAtom*
 AtomAttrValue(Implementor* aElement, nsIAtom* aName)
 {
   const nsAttrValue* attr = aElement->GetParsedAttr(aName);
   return attr ? attr->GetAtomValue() : nullptr;
 }
 

--- a/layout/style/ServoBindings.h
+++ b/layout/style/ServoBindings.h
@@ -372,16 +372,21 @@ void Gecko_nsStyleFont_CopyLangFrom(nsSt
 
 const nsMediaFeature* Gecko_GetMediaFeatures();
 
 // We use an int32_t here instead of a LookAndFeel::ColorID
 // because forward-declaring a nested enum/struct is impossible
 nscolor Gecko_GetLookAndFeelSystemColor(int32_t color_id,
                                         RawGeckoPresContextBorrowed pres_context);
 
+bool Gecko_MatchStringArgPseudo(RawGeckoElementBorrowed element,
+                                mozilla::CSSPseudoClassType type,
+                                const char16_t* ident,
+                                bool* set_slow_selector);
+
 // Style-struct management.
 #define STYLE_STRUCT(name, checkdata_cb)                                       \
   void Gecko_Construct_Default_nsStyle##name(                                  \
     nsStyle##name* ptr,                                                        \
     RawGeckoPresContextBorrowed pres_context);                                 \
   void Gecko_CopyConstruct_nsStyle##name(nsStyle##name* ptr,                   \
                                          const nsStyle##name* other);          \
   void Gecko_Destroy_nsStyle##name(nsStyle##name* ptr);

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -143,17 +143,17 @@ ServoStyleSet::GetContext(nsIContent* aC
                           nsIAtom* aPseudoTag,
                           CSSPseudoElementType aPseudoType,
                           LazyComputeBehavior aMayCompute)
 {
   MOZ_ASSERT(aContent->IsElement());
   Element* element = aContent->AsElement();
 
 
-  ResolveMappedAttrDeclarationBlocks();
+  PreTraverseSync();
   RefPtr<ServoComputedValues> computedValues;
   if (aMayCompute == LazyComputeBehavior::Allow) {
     computedValues = ResolveStyleLazily(element, nullptr);
   } else {
     computedValues = ResolveServoStyle(element);
   }
 
   MOZ_ASSERT(computedValues);
@@ -185,19 +185,29 @@ ServoStyleSet::ResolveMappedAttrDeclarat
   if (nsHTMLStyleSheet* sheet = mPresContext->Document()->GetAttributeStyleSheet()) {
     sheet->CalculateMappedServoDeclarations();
   }
 
   mPresContext->Document()->ResolveScheduledSVGPresAttrs();
 }
 
 void
+ServoStyleSet::PreTraverseSync()
+{
+  ResolveMappedAttrDeclarationBlocks();
+
+  // This is lazily computed and pseudo matching needs to access
+  // it so force computation early.
+  mPresContext->Document()->GetDocumentState();
+}
+
+void
 ServoStyleSet::PreTraverse()
 {
-  ResolveMappedAttrDeclarationBlocks();
+  PreTraverseSync();
 
   // Process animation stuff that we should avoid doing during the parallel
   // traversal.
   mPresContext->EffectCompositor()->PreTraverse();
 }
 
 bool
 ServoStyleSet::PrepareAndTraverseSubtree(RawGeckoElementBorrowed aRoot,

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -280,16 +280,18 @@ private:
    * all style data or when shutting down the style set).
    */
   void ClearNonInheritingStyleContexts();
 
   /**
    * Perform processes that we should do before traversing.
    */
   void PreTraverse();
+  // Subset of the pre-traverse steps that involve syncing up data
+  void PreTraverseSync();
 
   already_AddRefed<ServoComputedValues> ResolveStyleLazily(dom::Element* aElement,
                                                            nsIAtom* aPseudoTag);
 
   nsPresContext* mPresContext;
   UniquePtr<RawServoStyleSet> mRawSet;
   EnumeratedArray<SheetType, SheetType::Count,
                   nsTArray<RefPtr<ServoStyleSheet>>> mSheets;

--- a/layout/style/nsCSSRuleProcessor.cpp
+++ b/layout/style/nsCSSRuleProcessor.cpp
@@ -1633,30 +1633,39 @@ StateSelectorMatches(Element* aElement,
                               statesToCheck)) {
       return false;
     }
   }
   return true;
 }
 
 /* static */ bool
-nsCSSRuleProcessor::StringPseudoMatches(mozilla::dom::Element* aElement,
+nsCSSRuleProcessor::StringPseudoMatches(const mozilla::dom::Element* aElement,
                                         CSSPseudoClassType aPseudo,
-                                        char16_t* aString,
-                                        nsIDocument* aDocument,
+                                        const char16_t* aString,
+                                        const nsIDocument* aDocument,
                                         bool aForStyling,
                                         EventStates aStateMask,
+                                        bool* aSetSlowSelectorFlag,
                                         bool* const aDependence)
 {
+  MOZ_ASSERT(aSetSlowSelectorFlag);
+
   switch (aPseudo) {
     case CSSPseudoClassType::mozLocaleDir:
       {
-        bool docIsRTL =
-          aDocument->GetDocumentState().
-            HasState(NS_DOCUMENT_STATE_RTL_LOCALE);
+        bool docIsRTL;
+        if (aIsGecko) {
+          auto doc = const_cast<nsIDocument*>(aDocument);
+          docIsRTL = doc->GetDocumentState()
+                        .HasState(NS_DOCUMENT_STATE_RTL_LOCALE);
+        } else {
+          docIsRTL = aDocument->ThreadSafeGetDocumentState()
+                              .HasState(NS_DOCUMENT_STATE_RTL_LOCALE);
+        }
 
         nsDependentString dirString(aString);
 
         if (dirString.EqualsLiteral("rtl")) {
           if (!docIsRTL) {
             return false;
           }
         } else if (dirString.EqualsLiteral("ltr")) {
@@ -1686,17 +1695,17 @@ nsCSSRuleProcessor::StringPseudoMatches(
         int32_t index = -1;
 
         if (aForStyling) {
           // FIXME:  This isn't sufficient to handle:
           //   :-moz-empty-except-children-with-localname() + E
           //   :-moz-empty-except-children-with-localname() ~ E
           // because we don't know to restyle the grandparent of the
           // inserted/removed element (as in bug 534804 for :empty).
-          aElement->SetFlags(NODE_HAS_SLOW_SELECTOR);
+          *aSetSlowSelectorFlag = true;
         }
         do {
           child = aElement->GetChildAt(++index);
         } while (child &&
                   (!IsSignificantChild(child, true, false) ||
                   (child->GetNameSpaceID() == aElement->GetNameSpaceID() &&
                     child->NodeInfo()->NameAtom()->Equals(nsDependentString(aString)))));
         if (child) {
@@ -2136,23 +2145,28 @@ static bool SelectorMatches(Element* aEl
           return false;
         }
       }
       break;
 
     default:
       {
         MOZ_ASSERT(nsCSSPseudoClasses::HasStringArg(pseudoClass->mType));
+        bool setSlowSelectorFlag = false;
         bool matched = nsCSSRuleProcessor::StringPseudoMatches(aElement,
                                                                pseudoClass->mType,
                                                                pseudoClass->u.mString,
                                                                aTreeMatchContext.mDocument,
                                                                aTreeMatchContext.mForStyling,
                                                                aNodeMatchContext.mStateMask,
+                                                               &setSlowSelectorFlag,
                                                                aDependence);
+        if (setSlowSelectorFlag) {
+          aElement->SetFlags(NODE_HAS_SLOW_SELECTOR);
+        }
 
         if (!matched) {
           return false;
         }
       }
     }
   }
 

--- a/layout/style/nsCSSRuleProcessor.h
+++ b/layout/style/nsCSSRuleProcessor.h
@@ -136,37 +136,37 @@ public:
   /**
    * Checks if a function-like ident-containing pseudo (:pseudo(ident))
    * matches a given element.
    *
    * Returns true if it parses and matches, Some(false) if it
    * parses but does not match. Asserts if it fails to parse; only
    * call this when you're sure it's a string-like pseudo.
    *
-   * This will assert if the document has a stale document state,
-   * ensure that UpdatePossiblyStaleDocumentState() has been called
-   * first.
+   * In Servo mode, please ensure that UpdatePossiblyStaleDocumentState()
+   * has been called first.
    *
    * @param aElement The element we are trying to match
    * @param aPseudo The name of the pseudoselector
    * @param aString The identifier inside the pseudoselector (cannot be null)
    * @param aDocument The document
    * @param aForStyling Is this matching operation for the creation of a style context?
    *                    (For setting the slow selector flag)
    * @param aStateMask Mask containing states which we should exclude.
    *                   Ignored if aDependence is null
    * @param aDependence Pointer to be set to true if we ignored a state due to
    *                    aStateMask. Can be null.
    */
-  static bool StringPseudoMatches(mozilla::dom::Element* aElement,
+  static bool StringPseudoMatches(const mozilla::dom::Element* aElement,
                                   mozilla::CSSPseudoClassType aPseudo,
-                                  char16_t* aString,
-                                  nsIDocument* aDocument,
+                                  const char16_t* aString,
+                                  const nsIDocument* aDocument,
                                   bool aForStyling,
                                   mozilla::EventStates aStateMask,
+                                  bool* aSetSlowSelectorFlag,
                                   bool* const aDependence = nullptr);
 
   // nsIStyleRuleProcessor
   virtual void RulesMatching(ElementRuleProcessorData* aData) override;
 
   virtual void RulesMatching(PseudoElementRuleProcessorData* aData) override;
 
   virtual void RulesMatching(AnonBoxRuleProcessorData* aData) override;