--- a/dom/base/ChildIterator.cpp
+++ b/dom/base/ChildIterator.cpp
@@ -309,97 +309,163 @@ ExplicitChildIterator::GetPreviousChild(
   }
 
   return mChild;
 }
 
 bool
 AllChildrenIterator::Seek(nsIContent* aChildToFind)
 {
-  if (mPhase == eNeedBeforeKid) {
-    mPhase = eNeedExplicitKids;
+  if (mPhase == eAtBegin || mPhase == eAtBeforeKid) {
+    mPhase = eAtExplicitKids;
     nsIFrame* frame = mOriginalContent->GetPrimaryFrame();
     if (frame) {
       nsIFrame* beforeFrame = nsLayoutUtils::GetBeforeFrame(frame);
       if (beforeFrame) {
         if (beforeFrame->GetContent() == aChildToFind) {
+          mPhase = eAtBeforeKid;
           return true;
         }
       }
     }
   }
 
-  if (mPhase == eNeedExplicitKids) {
+  if (mPhase == eAtExplicitKids) {
     if (ExplicitChildIterator::Seek(aChildToFind)) {
       return true;
     }
-    mPhase = eNeedAnonKids;
+    mPhase = eAtAnonKids;
   }
 
   nsIContent* child = nullptr;
   do {
     child = GetNextChild();
   } while (child && child != aChildToFind);
 
   return child == aChildToFind;
 }
 
 nsIContent*
 AllChildrenIterator::GetNextChild()
 {
-  if (mPhase == eNeedBeforeKid) {
-    mPhase = eNeedExplicitKids;
+  if (mPhase == eAtBegin) {
+    mPhase = eAtExplicitKids;
     nsIFrame* frame = mOriginalContent->GetPrimaryFrame();
     if (frame) {
       nsIFrame* beforeFrame = nsLayoutUtils::GetBeforeFrame(frame);
       if (beforeFrame) {
+        mPhase = eAtBeforeKid;
         return beforeFrame->GetContent();
       }
     }
   }
 
-  if (mPhase == eNeedExplicitKids) {
+  if (mPhase == eAtBeforeKid) {
+    // Advance into our explicit kids.
+    mPhase = eAtExplicitKids;
+  }
+
+  if (mPhase == eAtExplicitKids) {
     nsIContent* kid = ExplicitChildIterator::GetNextChild();
     if (kid) {
       return kid;
     }
-
-    mPhase = eNeedAnonKids;
+    mPhase = eAtAnonKids;
   }
 
-  if (mPhase == eNeedAnonKids) {
+  if (mPhase == eAtAnonKids) {
     if (mAnonKids.IsEmpty()) {
+      MOZ_ASSERT(mAnonKidsIdx == UINT32_MAX);
       nsIAnonymousContentCreator* ac =
         do_QueryFrame(mOriginalContent->GetPrimaryFrame());
       if (ac) {
         ac->AppendAnonymousContentTo(mAnonKids, mFlags);
       }
+      mAnonKidsIdx = 0;
+    }
+    else {
+      if (mAnonKidsIdx == UINT32_MAX) {
+        mAnonKidsIdx = 0;
+      }
+      else {
+        mAnonKidsIdx++;
+      }
     }
 
-    if (!mAnonKids.IsEmpty()) {
-      nsIContent* nextKid = mAnonKids[0];
-      mAnonKids.RemoveElementAt(0);
-      if (mAnonKids.IsEmpty()) {
-        mPhase = eNeedAfterKid;
-      }
-
-      return nextKid;
+    if (mAnonKidsIdx < mAnonKids.Length()) {
+      return mAnonKids[mAnonKidsIdx];
     }
 
-    mPhase = eNeedAfterKid;
-  }
-
-  if (mPhase == eNeedAfterKid) {
-    mPhase = eDone;
     nsIFrame* frame = mOriginalContent->GetPrimaryFrame();
     if (frame) {
       nsIFrame* afterFrame = nsLayoutUtils::GetAfterFrame(frame);
       if (afterFrame) {
+        mPhase = eAtAfterKid;
+        return afterFrame->GetContent();
+      }
+    }
+  }
+
+  mPhase = eAtEnd;
+  return nullptr;
+}
+
+nsIContent*
+AllChildrenIterator::GetPreviousChild()
+{
+  if (mPhase == eAtEnd) {
+    MOZ_ASSERT(mAnonKidsIdx == mAnonKids.Length());
+    mPhase = eAtAnonKids;
+    nsIFrame* frame = mOriginalContent->GetPrimaryFrame();
+    if (frame) {
+      nsIFrame* afterFrame = nsLayoutUtils::GetAfterFrame(frame);
+      if (afterFrame) {
+        mPhase = eAtAfterKid;
         return afterFrame->GetContent();
       }
     }
   }
 
+  if (mPhase == eAtAfterKid) {
+    mPhase = eAtAnonKids;
+  }
+
+  if (mPhase == eAtAnonKids) {
+    if (mAnonKids.IsEmpty()) {
+      nsIAnonymousContentCreator* ac =
+        do_QueryFrame(mOriginalContent->GetPrimaryFrame());
+      if (ac) {
+        ac->AppendAnonymousContentTo(mAnonKids, mFlags);
+        mAnonKidsIdx = mAnonKids.Length();
+      }
+    }
+
+    // If 0 then it turns into UINT32_MAX, which indicates the iterator is
+    // before the anonymous children.
+    --mAnonKidsIdx;
+    if (mAnonKidsIdx < mAnonKids.Length()) {
+      return mAnonKids[mAnonKidsIdx];
+    }
+    mPhase = eAtExplicitKids;
+  }
+
+  if (mPhase == eAtExplicitKids) {
+    nsIContent* kid = ExplicitChildIterator::GetPreviousChild();
+    if (kid) {
+      return kid;
+    }
+
+    nsIFrame* frame = mOriginalContent->GetPrimaryFrame();
+    if (frame) {
+      nsIFrame* beforeFrame = nsLayoutUtils::GetBeforeFrame(frame);
+      if (beforeFrame) {
+        mPhase = eAtBeforeKid;
+        return beforeFrame->GetContent();
+      }
+    }
+  }
+
+  mPhase = eAtBegin;
   return nullptr;
 }
 
 } // namespace dom
 } // namespace mozilla

--- a/dom/base/ChildIterator.h
+++ b/dom/base/ChildIterator.h
@@ -177,50 +177,61 @@ protected:
  * providing false for aStartAtBeginning in order to start iterating in reverse
  * from the last child.
  */
 class AllChildrenIterator : private FlattenedChildIterator
 {
 public:
   AllChildrenIterator(nsIContent* aNode, uint32_t aFlags, bool aStartAtBeginning = true) :
     FlattenedChildIterator(aNode, aFlags, aStartAtBeginning),
-    mOriginalContent(aNode), mFlags(aFlags),
-    mPhase(eNeedBeforeKid) {}
+    mOriginalContent(aNode), mAnonKidsIdx(aStartAtBeginning ? UINT32_MAX : 0),
+    mFlags(aFlags), mPhase(aStartAtBeginning ? eAtBegin : eAtEnd) { }
 
   AllChildrenIterator(AllChildrenIterator&& aOther)
     : FlattenedChildIterator(Move(aOther)),
       mOriginalContent(aOther.mOriginalContent),
-      mAnonKids(Move(aOther.mAnonKids)), mFlags(aOther.mFlags),
-      mPhase(aOther.mPhase)
+      mAnonKids(Move(aOther.mAnonKids)), mAnonKidsIdx(aOther.mAnonKidsIdx),
+      mFlags(aOther.mFlags), mPhase(aOther.mPhase)
 #ifdef DEBUG
       , mMutationGuard(aOther.mMutationGuard)
 #endif
       {}
 
 #ifdef DEBUG
   ~AllChildrenIterator() { MOZ_ASSERT(!mMutationGuard.Mutated(0)); }
 #endif
 
   bool Seek(nsIContent* aChildToFind);
 
   nsIContent* GetNextChild();
+  nsIContent* GetPreviousChild();
   nsIContent* Parent() const { return mOriginalContent; }
 
 private:
   enum IteratorPhase
   {
-    eNeedBeforeKid,
-    eNeedExplicitKids,
-    eNeedAnonKids,
-    eNeedAfterKid,
-    eDone
+    eAtBegin,
+    eAtBeforeKid,
+    eAtExplicitKids,
+    eAtAnonKids,
+    eAtAfterKid,
+    eAtEnd
   };
 
   nsIContent* mOriginalContent;
+
+  // mAnonKids is an array of native anonymous children, mAnonKidsIdx is index
+  // in the array. If mAnonKidsIdx < mAnonKids.Length() and mPhase is
+  // eAtAnonKids then the iterator points at a child at mAnonKidsIdx index. If
+  // mAnonKidsIdx == mAnonKids.Length() then the iterator is somewhere after
+  // the last native anon child. If mAnonKidsIdx == UINT32_MAX then the iterator
+  // is somewhere before the first native anon child.
   nsTArray<nsIContent*> mAnonKids;
+  uint32_t mAnonKidsIdx;
+
   uint32_t mFlags;
   IteratorPhase mPhase;
 #ifdef DEBUG
   // XXX we should really assert there are no frame tree changes as well, but
   // there's no easy way to do that.
   nsMutationGuard mMutationGuard;
 #endif
 };