Backed out changeset bc3d643c4973 (bug 1395973) for failing browser-chrome's toolkit/content/tests/browser/browser_bug982298.js and toolkit/modules/tests/browser/browser_Finder_hidden_textarea.js. r=backout on a CLOSED TREE
authorSebastian Hengst <archaeopteryx@coole-files.de>
Thu, 14 Sep 2017 14:48:50 +0200
changeset 380780 6c7111ab968fc55accf3a2c6faf498cfd7c997a4
parent 380779 bf572b74ec5f3a9475e25c018f33eb76521c814e
child 380781 3022e88f7a8fe80945ad5a82a94e735b0af2ce2d
push id94995
push userarchaeopteryx@coole-files.de
push dateThu, 14 Sep 2017 12:49:09 +0000
treeherdermozilla-inbound@6c7111ab968f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbackout
bugs1395973, 982298
milestone57.0a1
backs outbc3d643c49739f2576a5f94eb53a13d3d3b4ebaf
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Backed out changeset bc3d643c4973 (bug 1395973) for failing browser-chrome's toolkit/content/tests/browser/browser_bug982298.js and toolkit/modules/tests/browser/browser_Finder_hidden_textarea.js. r=backout on a CLOSED TREE
dom/base/nsContentIterator.cpp
--- a/dom/base/nsContentIterator.cpp
+++ b/dom/base/nsContentIterator.cpp
@@ -139,39 +139,72 @@ protected:
    * - aStartOffset and aEndOffset are valid for its container.
    * - The start point and the end point are in document order.
    */
   nsresult InitInternal(nsINode* aStartContainer, uint32_t aStartOffset,
                         nsINode* aEndContainer, uint32_t aEndOffset);
 
   // Recursively get the deepest first/last child of aRoot.  This will return
   // aRoot itself if it has no children.
-  nsINode* GetDeepFirstChild(nsINode* aRoot);
-  nsIContent* GetDeepFirstChild(nsIContent* aRoot);
-  nsINode* GetDeepLastChild(nsINode* aRoot);
-  nsIContent* GetDeepLastChild(nsIContent* aRoot);
+  nsINode* GetDeepFirstChild(nsINode* aRoot,
+                             nsTArray<int32_t>* aIndexes = nullptr);
+  nsIContent* GetDeepFirstChild(nsIContent* aRoot,
+                                nsTArray<int32_t>* aIndexes = nullptr);
+  nsINode* GetDeepLastChild(nsINode* aRoot,
+                            nsTArray<int32_t>* aIndexes = nullptr);
+  nsIContent* GetDeepLastChild(nsIContent* aRoot,
+                               nsTArray<int32_t>* aIndexes = nullptr);
 
   // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
   // etc.  Returns null if aNode and all its ancestors have no next/previous
   // sibling.
-  nsIContent* GetNextSibling(nsINode* aNode);
-  nsIContent* GetPrevSibling(nsINode* aNode);
+  nsIContent* GetNextSibling(nsINode* aNode,
+                             nsTArray<int32_t>* aIndexes = nullptr);
+  nsIContent* GetPrevSibling(nsINode* aNode,
+                             nsTArray<int32_t>* aIndexes = nullptr);
 
-  nsINode* NextNode(nsINode* aNode);
-  nsINode* PrevNode(nsINode* aNode);
+  nsINode* NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
+  nsINode* PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
+
+  // WARNING: This function is expensive
+  nsresult RebuildIndexStack();
 
   void MakeEmpty();
 
   virtual void LastRelease();
 
   nsCOMPtr<nsINode> mCurNode;
   nsCOMPtr<nsINode> mFirst;
   nsCOMPtr<nsINode> mLast;
   nsCOMPtr<nsINode> mCommonParent;
 
+  // used by nsContentIterator to cache indices
+  AutoTArray<int32_t, 8> mIndexes;
+
+  // used by nsSubtreeIterator to cache indices.  Why put them in the base
+  // class?  Because otherwise I have to duplicate the routines GetNextSibling
+  // etc across both classes, with slight variations for caching.  Or
+  // alternately, create a base class for the cache itself and have all the
+  // cache manipulation go through a vptr.  I think this is the best space and
+  // speed combo, even though it's ugly.
+  int32_t mCachedIndex;
+  // another note about mCachedIndex: why should the subtree iterator use a
+  // trivial cached index instead of the mre robust array of indicies (which is
+  // what the basic content iterator uses)?  The reason is that subtree
+  // iterators do not do much transitioning between parents and children.  They
+  // tend to stay at the same level.  In fact, you can prove (though I won't
+  // attempt it here) that they change levels at most n+m times, where n is the
+  // height of the parent hierarchy from the range start to the common
+  // ancestor, and m is the the height of the parent hierarchy from the range
+  // end to the common ancestor.  If we used the index array, we would pay the
+  // price up front for n, and then pay the cost for m on the fly later on.
+  // With the simple cache, we only "pay as we go".  Either way, we call
+  // IndexOf() once for each change of level in the hierarchy.  Since a trivial
+  // index is much simpler, we use it for the subtree iterator.
+
   bool mIsDone;
   bool mPre;
 
 private:
 
   // no copies or assigns  FIX ME
   nsContentIterator(const nsContentIterator&);
   nsContentIterator& operator=(const nsContentIterator&);
@@ -227,19 +260,20 @@ nsContentIterator::LastRelease()
   mLast = nullptr;
   mCommonParent = nullptr;
 }
 
 /******************************************************
  * constructor/destructor
  ******************************************************/
 
-nsContentIterator::nsContentIterator(bool aPre)
-  : mIsDone(false)
-  , mPre(aPre)
+nsContentIterator::nsContentIterator(bool aPre) :
+  // don't need to explicitly initialize |nsCOMPtr|s, they will automatically
+  // be nullptr
+  mCachedIndex(0), mIsDone(false), mPre(aPre)
 {
 }
 
 
 nsContentIterator::~nsContentIterator()
 {
 }
 
@@ -252,29 +286,31 @@ nsContentIterator::~nsContentIterator()
 nsresult
 nsContentIterator::Init(nsINode* aRoot)
 {
   if (NS_WARN_IF(!aRoot)) {
     return NS_ERROR_NULL_POINTER;
   }
 
   mIsDone = false;
+  mIndexes.Clear();
 
   if (mPre) {
     mFirst = aRoot;
     mLast  = GetDeepLastChild(aRoot);
     NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
   } else {
     mFirst = GetDeepFirstChild(aRoot);
     NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
     mLast  = aRoot;
   }
 
   mCommonParent = aRoot;
   mCurNode = mFirst;
+  RebuildIndexStack();
   return NS_OK;
 }
 
 nsresult
 nsContentIterator::Init(nsIDOMRange* aDOMRange)
 {
   mIsDone = false;
 
@@ -335,16 +371,18 @@ nsContentIterator::InitInternal(nsINode*
     }
 
     if (startIsData) {
       // It's a character data node.
       mFirst   = aStartContainer->AsContent();
       mLast    = mFirst;
       mCurNode = mFirst;
 
+      DebugOnly<nsresult> rv = RebuildIndexStack();
+      NS_WARNING_ASSERTION(NS_SUCCEEDED(rv), "RebuildIndexStack failed");
       return NS_OK;
     }
   }
 
   // Find first node in range.
 
   nsIContent* cChild = nullptr;
 
@@ -499,189 +537,446 @@ nsContentIterator::InitInternal(nsINode*
   if (!mFirst || !mLast) {
     mFirst = nullptr;
     mLast  = nullptr;
   }
 
   mCurNode = mFirst;
   mIsDone  = !mCurNode;
 
+  if (!mCurNode) {
+    mIndexes.Clear();
+  } else {
+    DebugOnly<nsresult> rv = RebuildIndexStack();
+    NS_WARNING_ASSERTION(NS_SUCCEEDED(rv), "RebuildIndexStack failed");
+  }
+
   return NS_OK;
 }
 
 
 /******************************************************
  * Helper routines
  ******************************************************/
+// WARNING: This function is expensive
+nsresult
+nsContentIterator::RebuildIndexStack()
+{
+  // Make sure we start at the right indexes on the stack!  Build array up
+  // to common parent of start and end.  Perhaps it's too many entries, but
+  // that's far better than too few.
+  nsINode* parent;
+  nsINode* current;
+
+  mIndexes.Clear();
+  current = mCurNode;
+  if (!current) {
+    return NS_OK;
+  }
+
+  while (current != mCommonParent) {
+    parent = current->GetParentNode();
+
+    if (NS_WARN_IF(!parent)) {
+      return NS_ERROR_FAILURE;
+    }
+
+    mIndexes.InsertElementAt(0, parent->IndexOf(current));
+
+    current = parent;
+  }
+
+  return NS_OK;
+}
 
 void
 nsContentIterator::MakeEmpty()
 {
   mCurNode      = nullptr;
   mFirst        = nullptr;
   mLast         = nullptr;
   mCommonParent = nullptr;
   mIsDone       = true;
+  mIndexes.Clear();
 }
 
 nsINode*
-nsContentIterator::GetDeepFirstChild(nsINode* aRoot)
+nsContentIterator::GetDeepFirstChild(nsINode* aRoot,
+                                     nsTArray<int32_t>* aIndexes)
 {
   if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
     return aRoot;
   }
-
-  return GetDeepFirstChild(aRoot->GetFirstChild());
+  // We can't pass aRoot itself to the full GetDeepFirstChild, because that
+  // will only take nsIContent and aRoot might be a document.  Pass aRoot's
+  // child, but be sure to preserve aIndexes.
+  if (aIndexes) {
+    aIndexes->AppendElement(0);
+  }
+  return GetDeepFirstChild(aRoot->GetFirstChild(), aIndexes);
 }
 
 nsIContent*
-nsContentIterator::GetDeepFirstChild(nsIContent* aRoot)
+nsContentIterator::GetDeepFirstChild(nsIContent* aRoot,
+                                     nsTArray<int32_t>* aIndexes)
 {
   if (NS_WARN_IF(!aRoot)) {
     return nullptr;
   }
 
   nsIContent* node = aRoot;
   nsIContent* child = node->GetFirstChild();
 
   while (child) {
+    if (aIndexes) {
+      // Add this node to the stack of indexes
+      aIndexes->AppendElement(0);
+    }
     node = child;
     child = node->GetFirstChild();
   }
 
   return node;
 }
 
 nsINode*
-nsContentIterator::GetDeepLastChild(nsINode* aRoot)
+nsContentIterator::GetDeepLastChild(nsINode* aRoot,
+                                    nsTArray<int32_t>* aIndexes)
 {
   if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
     return aRoot;
   }
-
-  return GetDeepLastChild(aRoot->GetLastChild());
+  // We can't pass aRoot itself to the full GetDeepLastChild, because that will
+  // only take nsIContent and aRoot might be a document.  Pass aRoot's child,
+  // but be sure to preserve aIndexes.
+  if (aIndexes) {
+    aIndexes->AppendElement(aRoot->GetChildCount() - 1);
+  }
+  return GetDeepLastChild(aRoot->GetLastChild(), aIndexes);
 }
 
 nsIContent*
-nsContentIterator::GetDeepLastChild(nsIContent* aRoot)
+nsContentIterator::GetDeepLastChild(nsIContent* aRoot,
+                                    nsTArray<int32_t>* aIndexes)
 {
   if (NS_WARN_IF(!aRoot)) {
     return nullptr;
   }
 
   nsIContent* node = aRoot;
-  while (node->HasChildren()) {
-    nsIContent* child = node->GetLastChild();
+  int32_t numChildren = node->GetChildCount();
+
+  while (numChildren) {
+    nsIContent* child = node->GetChildAt(--numChildren);
+
+    if (aIndexes) {
+      // Add this node to the stack of indexes
+      aIndexes->AppendElement(numChildren);
+    }
+    numChildren = child->GetChildCount();
     node = child;
   }
+
   return node;
 }
 
 // Get the next sibling, or parent's next sibling, or grandpa's next sibling...
 nsIContent*
-nsContentIterator::GetNextSibling(nsINode* aNode)
+nsContentIterator::GetNextSibling(nsINode* aNode,
+                                  nsTArray<int32_t>* aIndexes)
 {
   if (NS_WARN_IF(!aNode)) {
     return nullptr;
   }
 
-  if (aNode->GetNextSibling()) {
-    return aNode->GetNextSibling();
-  }
-
   nsINode* parent = aNode->GetParentNode();
   if (NS_WARN_IF(!parent)) {
     return nullptr;
   }
-  return GetNextSibling(parent);
+
+  int32_t indx = 0;
+
+  NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
+               "ContentIterator stack underflow");
+  if (aIndexes && !aIndexes->IsEmpty()) {
+    // use the last entry on the Indexes array for the current index
+    indx = (*aIndexes)[aIndexes->Length()-1];
+  } else {
+    indx = mCachedIndex;
+  }
+  NS_WARNING_ASSERTION(indx >= 0, "bad indx");
+
+  // reverify that the index of the current node hasn't changed.
+  // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
+  // ignore result this time - the index may now be out of range.
+  nsIContent* sib = parent->GetChildAt(indx);
+  if (sib != aNode) {
+    // someone changed our index - find the new index the painful way
+    indx = parent->IndexOf(aNode);
+    NS_WARNING_ASSERTION(indx >= 0, "bad indx");
+  }
+
+  // indx is now canonically correct
+  if ((sib = parent->GetChildAt(++indx))) {
+    // update index cache
+    if (aIndexes && !aIndexes->IsEmpty()) {
+      aIndexes->ElementAt(aIndexes->Length()-1) = indx;
+    } else {
+      mCachedIndex = indx;
+    }
+  } else {
+    if (parent != mCommonParent) {
+      if (aIndexes) {
+        // pop node off the stack, go up one level and return parent or fail.
+        // Don't leave the index empty, especially if we're
+        // returning nullptr.  This confuses other parts of the code.
+        if (aIndexes->Length() > 1) {
+          aIndexes->RemoveElementAt(aIndexes->Length()-1);
+        }
+      }
+    }
+
+    // ok to leave cache out of date here if parent == mCommonParent?
+    sib = GetNextSibling(parent, aIndexes);
+  }
+
+  return sib;
 }
 
 // Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
 nsIContent*
-nsContentIterator::GetPrevSibling(nsINode* aNode)
+nsContentIterator::GetPrevSibling(nsINode* aNode,
+                                  nsTArray<int32_t>* aIndexes)
 {
   if (NS_WARN_IF(!aNode)) {
     return nullptr;
   }
 
-  if (aNode->GetPreviousSibling()) {
-    return aNode->GetPreviousSibling();
-  }
-
   nsINode* parent = aNode->GetParentNode();
   if (NS_WARN_IF(!parent)) {
     return nullptr;
   }
-  return GetPrevSibling(parent);
+
+  int32_t indx = 0;
+
+  NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
+               "ContentIterator stack underflow");
+  if (aIndexes && !aIndexes->IsEmpty()) {
+    // use the last entry on the Indexes array for the current index
+    indx = (*aIndexes)[aIndexes->Length()-1];
+  } else {
+    indx = mCachedIndex;
+  }
+
+  // reverify that the index of the current node hasn't changed
+  // ignore result this time - the index may now be out of range.
+  nsIContent* sib = parent->GetChildAt(indx);
+  if (sib != aNode) {
+    // someone changed our index - find the new index the painful way
+    indx = parent->IndexOf(aNode);
+    NS_WARNING_ASSERTION(indx >= 0, "bad indx");
+  }
+
+  // indx is now canonically correct
+  if (indx > 0 && (sib = parent->GetChildAt(--indx))) {
+    // update index cache
+    if (aIndexes && !aIndexes->IsEmpty()) {
+      aIndexes->ElementAt(aIndexes->Length()-1) = indx;
+    } else {
+      mCachedIndex = indx;
+    }
+  } else if (parent != mCommonParent) {
+    if (aIndexes && !aIndexes->IsEmpty()) {
+      // pop node off the stack, go up one level and try again.
+      aIndexes->RemoveElementAt(aIndexes->Length()-1);
+    }
+    return GetPrevSibling(parent, aIndexes);
+  }
+
+  return sib;
 }
 
 nsINode*
-nsContentIterator::NextNode(nsINode* aNode)
+nsContentIterator::NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
 {
   nsINode* node = aNode;
 
   // if we are a Pre-order iterator, use pre-order
   if (mPre) {
     // if it has children then next node is first child
     if (node->HasChildren()) {
       nsIContent* firstChild = node->GetFirstChild();
       MOZ_ASSERT(firstChild);
 
+      // update cache
+      if (aIndexes) {
+        // push an entry on the index stack
+        aIndexes->AppendElement(0);
+      } else {
+        mCachedIndex = 0;
+      }
+
       return firstChild;
     }
 
     // else next sibling is next
-    return GetNextSibling(node);
+    return GetNextSibling(node, aIndexes);
   }
 
   // post-order
   nsINode* parent = node->GetParentNode();
   if (NS_WARN_IF(!parent)) {
     MOZ_ASSERT(parent, "The node is the root node but not the last node");
     mIsDone = true;
     return node;
   }
-  nsIContent* sibling = node->GetNextSibling();
+  nsIContent* sibling = nullptr;
+  int32_t indx = 0;
+
+  // get the cached index
+  NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
+               "ContentIterator stack underflow");
+  if (aIndexes && !aIndexes->IsEmpty()) {
+    // use the last entry on the Indexes array for the current index
+    indx = (*aIndexes)[aIndexes->Length()-1];
+  } else {
+    indx = mCachedIndex;
+  }
+
+  // reverify that the index of the current node hasn't changed.  not super
+  // cheap, but a lot cheaper than IndexOf(), and still O(1).  ignore result
+  // this time - the index may now be out of range.
+  if (indx >= 0) {
+    sibling = parent->GetChildAt(indx);
+  }
+  if (sibling != node) {
+    // someone changed our index - find the new index the painful way
+    indx = parent->IndexOf(node);
+    NS_WARNING_ASSERTION(indx >= 0, "bad indx");
+  }
+
+  // indx is now canonically correct
+  sibling = parent->GetChildAt(++indx);
   if (sibling) {
+    // update cache
+    if (aIndexes && !aIndexes->IsEmpty()) {
+      // replace an entry on the index stack
+      aIndexes->ElementAt(aIndexes->Length()-1) = indx;
+    } else {
+      mCachedIndex = indx;
+    }
+
     // next node is sibling's "deep left" child
-    return GetDeepFirstChild(sibling);
+    return GetDeepFirstChild(sibling, aIndexes);
+  }
+
+  // else it's the parent, update cache
+  if (aIndexes) {
+    // Pop an entry off the index stack.  Don't leave the index empty,
+    // especially if we're returning nullptr.  This confuses other parts of the
+    // code.
+    if (aIndexes->Length() > 1) {
+      aIndexes->RemoveElementAt(aIndexes->Length()-1);
+    }
+  } else {
+    // this might be wrong, but we are better off guessing
+    mCachedIndex = 0;
   }
 
   return parent;
 }
 
 nsINode*
-nsContentIterator::PrevNode(nsINode* aNode)
+nsContentIterator::PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
 {
   nsINode* node = aNode;
 
   // if we are a Pre-order iterator, use pre-order
   if (mPre) {
     nsINode* parent = node->GetParentNode();
     if (NS_WARN_IF(!parent)) {
       MOZ_ASSERT(parent, "The node is the root node but not the first node");
       mIsDone = true;
       return aNode;
     }
+    nsIContent* sibling = nullptr;
+    int32_t indx = 0;
 
-    nsIContent* sibling = node->GetPreviousSibling();
-    if (sibling) {
-      return GetDeepLastChild(sibling);
+    // get the cached index
+    NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
+                 "ContentIterator stack underflow");
+    if (aIndexes && !aIndexes->IsEmpty()) {
+      // use the last entry on the Indexes array for the current index
+      indx = (*aIndexes)[aIndexes->Length()-1];
+    } else {
+      indx = mCachedIndex;
+    }
+
+    // reverify that the index of the current node hasn't changed.  not super
+    // cheap, but a lot cheaper than IndexOf(), and still O(1).  ignore result
+    // this time - the index may now be out of range.
+    if (indx >= 0) {
+      sibling = parent->GetChildAt(indx);
+      NS_WARNING_ASSERTION(sibling, "GetChildAt returned null");
     }
 
+    if (sibling != node) {
+      // someone changed our index - find the new index the painful way
+      indx = parent->IndexOf(node);
+      NS_WARNING_ASSERTION(indx >= 0, "bad indx");
+    }
+
+    // indx is now canonically correct
+    if (indx && (sibling = parent->GetChildAt(--indx))) {
+      // update cache
+      if (aIndexes && !aIndexes->IsEmpty()) {
+        // replace an entry on the index stack
+        aIndexes->ElementAt(aIndexes->Length()-1) = indx;
+      } else {
+        mCachedIndex = indx;
+      }
+
+      // prev node is sibling's "deep right" child
+      return GetDeepLastChild(sibling, aIndexes);
+    }
+
+    // else it's the parent, update cache
+    if (aIndexes && !aIndexes->IsEmpty()) {
+      // pop an entry off the index stack
+      aIndexes->RemoveElementAt(aIndexes->Length()-1);
+    } else {
+      // this might be wrong, but we are better off guessing
+      mCachedIndex = 0;
+    }
     return parent;
   }
 
   // post-order
-  if (node->HasChildren()) {
-    return node->GetLastChild();
+  int32_t numChildren = node->GetChildCount();
+  NS_WARNING_ASSERTION(numChildren >= 0, "no children");
+
+  // if it has children then prev node is last child
+  if (numChildren) {
+    nsIContent* lastChild = node->GetLastChild();
+    NS_WARNING_ASSERTION(lastChild, "GetLastChild returned null");
+    numChildren--;
+
+    // update cache
+    if (aIndexes) {
+      // push an entry on the index stack
+      aIndexes->AppendElement(numChildren);
+    } else {
+      mCachedIndex = numChildren;
+    }
+
+    return lastChild;
   }
 
   // else prev sibling is previous
-  return GetPrevSibling(node);
+  return GetPrevSibling(node, aIndexes);
 }
 
 /******************************************************
  * ContentIterator routines
  ******************************************************/
 
 void
 nsContentIterator::First()
@@ -719,57 +1014,61 @@ nsContentIterator::Next()
     return;
   }
 
   if (mCurNode == mLast) {
     mIsDone = true;
     return;
   }
 
-  mCurNode = NextNode(mCurNode);
+  mCurNode = NextNode(mCurNode, &mIndexes);
 }
 
 
 void
 nsContentIterator::Prev()
 {
   if (NS_WARN_IF(mIsDone) || NS_WARN_IF(!mCurNode)) {
     return;
   }
 
   if (mCurNode == mFirst) {
     mIsDone = true;
     return;
   }
 
-  mCurNode = PrevNode(mCurNode);
+  mCurNode = PrevNode(mCurNode, &mIndexes);
 }
 
 
 bool
 nsContentIterator::IsDone()
 {
   return mIsDone;
 }
 
+
 // Keeping arrays of indexes for the stack of nodes makes PositionAt
 // interesting...
 nsresult
 nsContentIterator::PositionAt(nsINode* aCurNode)
 {
   if (NS_WARN_IF(!aCurNode)) {
     return NS_ERROR_NULL_POINTER;
   }
 
+  nsINode* newCurNode = aCurNode;
+  nsINode* tempNode = mCurNode;
+
+  mCurNode = aCurNode;
   // take an early out if this doesn't actually change the position
-  if (mCurNode == aCurNode) {
-    mIsDone = false;
+  if (mCurNode == tempNode) {
+    mIsDone = false;  // paranoia
     return NS_OK;
   }
-  mCurNode = aCurNode;
 
   // Check to see if the node falls within the traversal range.
 
   nsINode* firstNode = mFirst;
   nsINode* lastNode = mLast;
   int32_t firstOffset = 0, lastOffset = 0;
 
   if (firstNode && lastNode) {
@@ -812,16 +1111,92 @@ nsContentIterator::PositionAt(nsINode* a
       (NS_WARN_IF(!firstNode) || NS_WARN_IF(!lastNode) ||
        NS_WARN_IF(!NodeIsInTraversalRange(mCurNode, mPre,
                                           firstNode, firstOffset,
                                           lastNode, lastOffset)))) {
     mIsDone = true;
     return NS_ERROR_FAILURE;
   }
 
+  // We can be at ANY node in the sequence.  Need to regenerate the array of
+  // indexes back to the root or common parent!
+  AutoTArray<nsINode*, 8>     oldParentStack;
+  AutoTArray<int32_t, 8>      newIndexes;
+
+  // Get a list of the parents up to the root, then compare the new node with
+  // entries in that array until we find a match (lowest common ancestor).  If
+  // no match, use IndexOf, take the parent, and repeat.  This avoids using
+  // IndexOf() N times on possibly large arrays.  We still end up doing it a
+  // fair bit.  It's better to use Clone() if possible.
+
+  // we know the depth we're down (though we may not have started at the top).
+  oldParentStack.SetCapacity(mIndexes.Length() + 1);
+
+  // We want to loop mIndexes.Length() + 1 times here, because we want to make
+  // sure we include mCommonParent in the oldParentStack, for use in the next
+  // for loop, and mIndexes only has entries for nodes from tempNode up through
+  // an ancestor of tempNode that's a child of mCommonParent.
+  for (int32_t i = mIndexes.Length() + 1; i > 0 && tempNode; i--) {
+    // Insert at head since we're walking up
+    oldParentStack.InsertElementAt(0, tempNode);
+
+    nsINode* parent = tempNode->GetParentNode();
+
+    if (NS_WARN_IF(!parent)) {
+      // this node has no parent, and thus no index
+      break;
+    }
+
+    if (parent == mCurNode) {
+      // The position was moved to a parent of the current position.  All we
+      // need to do is drop some indexes.  Shortcut here.
+      mIndexes.RemoveElementsAt(mIndexes.Length() - oldParentStack.Length(),
+                                oldParentStack.Length());
+      mIsDone = false;
+      return NS_OK;
+    }
+    tempNode = parent;
+  }
+
+  // Ok.  We have the array of old parents.  Look for a match.
+  while (newCurNode) {
+    nsINode* parent = newCurNode->GetParentNode();
+
+    if (NS_WARN_IF(!parent)) {
+      // this node has no parent, and thus no index
+      break;
+    }
+
+    int32_t indx = parent->IndexOf(newCurNode);
+    NS_WARNING_ASSERTION(indx >= 0, "bad indx");
+
+    // insert at the head!
+    newIndexes.InsertElementAt(0, indx);
+
+    // look to see if the parent is in the stack
+    indx = oldParentStack.IndexOf(parent);
+    if (indx >= 0) {
+      // ok, the parent IS on the old stack!  Rework things.  We want
+      // newIndexes to replace all nodes equal to or below the match.  Note
+      // that index oldParentStack.Length() - 1 is the last node, which is one
+      // BELOW the last index in the mIndexes stack.  In other words, we want
+      // to remove elements starting at index (indx + 1).
+      int32_t numToDrop = oldParentStack.Length() - (1 + indx);
+      if (numToDrop > 0) {
+        mIndexes.RemoveElementsAt(mIndexes.Length() - numToDrop, numToDrop);
+      }
+      mIndexes.AppendElements(newIndexes);
+
+      break;
+    }
+    newCurNode = parent;
+  }
+
+  // phew!
+
   mIsDone = false;
   return NS_OK;
 }
 
 nsINode*
 nsContentIterator::GetCurrentNode()
 {
   if (mIsDone) {