--- a/layout/base/ServoRestyleManager.cpp
+++ b/layout/base/ServoRestyleManager.cpp
@@ -34,36 +34,28 @@ ServoRestyleManager::PostRestyleEvent(El
 {
   MOZ_ASSERT(!(aMinChangeHint & nsChangeHint_NeutralChange),
              "Didn't expect explicit change hints to be neutral!");
   if (MOZ_UNLIKELY(IsDisconnected()) ||
       MOZ_UNLIKELY(PresContext()->PresShell()->IsDestroying())) {
     return;
   }
 
-  if (mInStyleRefresh && aRestyleHint == eRestyle_CSSAnimations) {
-    // FIXME: This is the initial restyle for CSS animations when the animation
-    // is created. We have to process this restyle if necessary. Currently we
-    // skip it here and will do this restyle in the next tick.
-    return;
-  }
+  // We allow posting restyles from within change hint handling, but not from
+  // within the restyle algorithm itself.
+  MOZ_ASSERT(!ServoStyleSet::IsInServoTraversal());
 
   if (aRestyleHint == 0 && !aMinChangeHint) {
     return; // Nothing to do.
   }
 
-  // We allow posting change hints during restyling, but not restyle hints
-  // themselves, since those would require us to re-traverse the tree.
-  MOZ_ASSERT_IF(mInStyleRefresh, aRestyleHint == 0);
-
-  // Processing change hints sometimes causes new change hints to be generated.
-  // Doing this after the gecko post-traversal is problematic, so instead we just
-  // queue them up for special handling.
-  if (mReentrantChanges) {
-    MOZ_ASSERT(aRestyleHint == 0);
+  // Processing change hints sometimes causes new change hints to be generated,
+  // and very occasionally, additional restyle hints. We collect the change
+  // hints manually to avoid re-traversing the DOM to find them.
+  if (mReentrantChanges && !aRestyleHint) {
     mReentrantChanges->AppendElement(ReentrantChange { aElement, aMinChangeHint });
     return;
   }
 
   // XXX This is a temporary hack to make style attribute change works.
   //     In the future, we should be able to use this hint directly.
   if (aRestyleHint & eRestyle_StyleAttribute) {
     aRestyleHint &= ~eRestyle_StyleAttribute;
@@ -387,20 +379,22 @@ ServoRestyleManager::ProcessPendingResty
 
   ServoStyleSet* styleSet = StyleSet();
   nsIDocument* doc = PresContext()->Document();
 
   // Ensure the refresh driver is active during traversal to avoid mutating
   // mActiveTimer and mMostRecentRefresh time.
   PresContext()->RefreshDriver()->MostRecentRefresh();
 
+
+  // Perform the Servo traversal, and the post-traversal if required. We do this
+  // in a loop because certain rare paths in the frame constructor (like
+  // uninstalling XBL bindings) can trigger additional style validations.
   mInStyleRefresh = true;
-
-  // Perform the Servo traversal, and the post-traversal if required.
-  if (styleSet->StyleDocument()) {
+  while (styleSet->StyleDocument()) {
 
     PresContext()->EffectCompositor()->ClearElementsToRestyle();
 
     // First do any queued-up frame creation. (see bugs 827239 and 997506).
     //
     // XXXEmilio I'm calling this to avoid random behavior changes, since we
     // delay frame construction after styling we should re-check once our
     // model is more stable whether we can skip this call.
@@ -429,22 +423,21 @@ ServoRestyleManager::ProcessPendingResty
       for (ReentrantChange& change: newChanges)  {
         currentChanges.AppendChange(change.mContent->GetPrimaryFrame(),
                                     change.mContent, change.mHint);
       }
       newChanges.Clear();
     }
     mReentrantChanges = nullptr;
 
-    styleSet->AssertTreeIsClean();
-
     IncrementRestyleGeneration();
   }
 
   mInStyleRefresh = false;
+  styleSet->AssertTreeIsClean();
 
   // Note: We are in the scope of |animationsWithDestroyedFrame|, so
   //       |mAnimationsWithDestroyedFrame| is still valid.
   MOZ_ASSERT(mAnimationsWithDestroyedFrame);
   mAnimationsWithDestroyedFrame->StopAnimationsForElementsWithoutFrames();
 }
 
 void