Add m-esr52 at 52.6.0

1 files changed, 1553 insertions, 0 deletions

diff --git a/dom/base/nsContentIterator.cpp b/dom/base/nsContentIterator.cpp
new file mode 100644
index 000000000..287de7722
--- /dev/null
+++ b/dom/base/nsContentIterator.cpp
@@ -0,0 +1,1553 @@
+/* -*- 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/DebugOnly.h"
+#include "nsISupports.h"
+#include "nsIDOMNodeList.h"
+#include "nsIContentIterator.h"
+#include "nsRange.h"
+#include "nsIContent.h"
+#include "nsCOMPtr.h"
+#include "nsTArray.h"
+#include "nsContentUtils.h"
+#include "nsINode.h"
+#include "nsCycleCollectionParticipant.h"
+
+using mozilla::DebugOnly;
+
+// couple of utility static functs
+
+///////////////////////////////////////////////////////////////////////////
+// NodeToParentOffset: returns the node's parent and offset.
+//
+
+static nsINode*
+NodeToParentOffset(nsINode* aNode, int32_t* aOffset)
+{
+  *aOffset = 0;
+
+  nsINode* parent = aNode->GetParentNode();
+
+  if (parent) {
+    *aOffset = parent->IndexOf(aNode);
+    NS_WARNING_ASSERTION(*aOffset >= 0, "bad offset");
+  }
+
+  return parent;
+}
+
+///////////////////////////////////////////////////////////////////////////
+// NodeIsInTraversalRange: returns true if content is visited during
+// the traversal of the range in the specified mode.
+//
+static bool
+NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode,
+                       nsINode* aStartNode, int32_t aStartOffset,
+                       nsINode* aEndNode, int32_t aEndOffset)
+{
+  if (NS_WARN_IF(!aStartNode) || NS_WARN_IF(!aEndNode) || NS_WARN_IF(!aNode)) {
+    return false;
+  }
+
+  // If a leaf node contains an end point of the traversal range, it is
+  // always in the traversal range.
+  if (aNode == aStartNode || aNode == aEndNode) {
+    if (aNode->IsNodeOfType(nsINode::eDATA_NODE)) {
+      return true; // text node or something
+    }
+    if (!aNode->HasChildren()) {
+      MOZ_ASSERT(aNode != aStartNode || !aStartOffset,
+        "aStartNode doesn't have children and not a data node, "
+        "aStartOffset should be 0");
+      MOZ_ASSERT(aNode != aEndNode || !aEndOffset,
+        "aStartNode doesn't have children and not a data node, "
+        "aStartOffset should be 0");
+      return true;
+    }
+  }
+
+  nsINode* parent = aNode->GetParentNode();
+  if (!parent) {
+    return false;
+  }
+
+  int32_t indx = parent->IndexOf(aNode);
+  NS_WARNING_ASSERTION(indx != -1, "bad indx");
+
+  if (!aIsPreMode) {
+    ++indx;
+  }
+
+  return nsContentUtils::ComparePoints(aStartNode, aStartOffset,
+                                       parent, indx) <= 0 &&
+         nsContentUtils::ComparePoints(aEndNode, aEndOffset,
+                                       parent, indx) >= 0;
+}
+
+
+
+/*
+ *  A simple iterator class for traversing the content in "close tag" order
+ */
+class nsContentIterator : public nsIContentIterator
+{
+public:
+  NS_DECL_CYCLE_COLLECTING_ISUPPORTS
+  NS_DECL_CYCLE_COLLECTION_CLASS(nsContentIterator)
+
+  explicit nsContentIterator(bool aPre);
+
+  // nsIContentIterator interface methods ------------------------------
+
+  virtual nsresult Init(nsINode* aRoot) override;
+
+  virtual nsresult Init(nsIDOMRange* aRange) override;
+
+  virtual void First() override;
+
+  virtual void Last() override;
+
+  virtual void Next() override;
+
+  virtual void Prev() override;
+
+  virtual nsINode* GetCurrentNode() override;
+
+  virtual bool IsDone() override;
+
+  virtual nsresult PositionAt(nsINode* aCurNode) override;
+
+protected:
+  virtual ~nsContentIterator();
+
+  // Recursively get the deepest first/last child of aRoot.  This will return
+  // aRoot itself if it has no children.
+  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,
+                             nsTArray<int32_t>* aIndexes = nullptr);
+  nsIContent* GetPrevSibling(nsINode* aNode,
+                             nsTArray<int32_t>* aIndexes = nullptr);
+
+  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&);
+
+};
+
+
+/******************************************************
+ * repository cruft
+ ******************************************************/
+
+already_AddRefed<nsIContentIterator>
+NS_NewContentIterator()
+{
+  nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(false);
+  return iter.forget();
+}
+
+
+already_AddRefed<nsIContentIterator>
+NS_NewPreContentIterator()
+{
+  nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(true);
+  return iter.forget();
+}
+
+
+/******************************************************
+ * XPCOM cruft
+ ******************************************************/
+
+NS_IMPL_CYCLE_COLLECTING_ADDREF(nsContentIterator)
+NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(nsContentIterator,
+                                                   LastRelease())
+
+NS_INTERFACE_MAP_BEGIN(nsContentIterator)
+  NS_INTERFACE_MAP_ENTRY(nsIContentIterator)
+  NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIContentIterator)
+  NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION(nsContentIterator)
+NS_INTERFACE_MAP_END
+
+NS_IMPL_CYCLE_COLLECTION(nsContentIterator,
+                         mCurNode,
+                         mFirst,
+                         mLast,
+                         mCommonParent)
+
+void
+nsContentIterator::LastRelease()
+{
+  mCurNode = nullptr;
+  mFirst = nullptr;
+  mLast = nullptr;
+  mCommonParent = nullptr;
+}
+
+/******************************************************
+ * constructor/destructor
+ ******************************************************/
+
+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()
+{
+}
+
+
+/******************************************************
+ * Init routines
+ ******************************************************/
+
+
+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)
+{
+  if (NS_WARN_IF(!aDOMRange)) {
+    return NS_ERROR_INVALID_ARG;
+  }
+  nsRange* range = static_cast<nsRange*>(aDOMRange);
+
+  mIsDone = false;
+
+  // get common content parent
+  mCommonParent = range->GetCommonAncestor();
+  if (NS_WARN_IF(!mCommonParent)) {
+    return NS_ERROR_FAILURE;
+  }
+
+  // get the start node and offset
+  int32_t startIndx = range->StartOffset();
+  NS_WARNING_ASSERTION(startIndx >= 0, "bad startIndx");
+  nsINode* startNode = range->GetStartParent();
+  if (NS_WARN_IF(!startNode)) {
+    return NS_ERROR_FAILURE;
+  }
+
+  // get the end node and offset
+  int32_t endIndx = range->EndOffset();
+  NS_WARNING_ASSERTION(endIndx >= 0, "bad endIndx");
+  nsINode* endNode = range->GetEndParent();
+  if (NS_WARN_IF(!endNode)) {
+    return NS_ERROR_FAILURE;
+  }
+
+  bool startIsData = startNode->IsNodeOfType(nsINode::eDATA_NODE);
+
+  // short circuit when start node == end node
+  if (startNode == endNode) {
+    // Check to see if we have a collapsed range, if so, there is nothing to
+    // iterate over.
+    //
+    // XXX: CharacterDataNodes (text nodes) are currently an exception, since
+    //      we always want to be able to iterate text nodes at the end points
+    //      of a range.
+
+    if (!startIsData && startIndx == endIndx) {
+      MakeEmpty();
+      return NS_OK;
+    }
+
+    if (startIsData) {
+      // It's a character data node.
+      mFirst   = startNode->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;
+
+  // Valid start indices are 0 <= startIndx <= childCount. That means if start
+  // node has no children, only offset 0 is valid.
+  if (!startIsData && uint32_t(startIndx) < startNode->GetChildCount()) {
+    cChild = startNode->GetChildAt(startIndx);
+    NS_WARNING_ASSERTION(cChild, "GetChildAt returned null");
+  }
+
+  if (!cChild) {
+    // No children (possibly a <br> or text node), or index is after last child.
+
+    if (mPre) {
+      // XXX: In the future, if start offset is after the last
+      //      character in the cdata node, should we set mFirst to
+      //      the next sibling?
+
+      // Normally we would skip the start node because the start node is outside
+      // of the range in pre mode. However, if startIndx == 0, it means the node
+      // has no children, and the node may be <br> or something. We don't skip
+      // the node in this case in order to address bug 1215798.
+      if (!startIsData && startIndx) {
+        mFirst = GetNextSibling(startNode);
+        NS_WARNING_ASSERTION(mFirst, "GetNextSibling returned null");
+
+        // Does mFirst node really intersect the range?  The range could be
+        // 'degenerate', i.e., not collapsed but still contain no content.
+        if (mFirst &&
+            NS_WARN_IF(!NodeIsInTraversalRange(mFirst, mPre, startNode,
+                                               startIndx, endNode, endIndx))) {
+          mFirst = nullptr;
+        }
+      } else {
+        mFirst = startNode->AsContent();
+      }
+    } else {
+      // post-order
+      if (NS_WARN_IF(!startNode->IsContent())) {
+        // What else can we do?
+        mFirst = nullptr;
+      } else {
+        mFirst = startNode->AsContent();
+      }
+    }
+  } else {
+    if (mPre) {
+      mFirst = cChild;
+    } else {
+      // post-order
+      mFirst = GetDeepFirstChild(cChild);
+      NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
+
+      // Does mFirst node really intersect the range?  The range could be
+      // 'degenerate', i.e., not collapsed but still contain no content.
+
+      if (mFirst &&
+          !NodeIsInTraversalRange(mFirst, mPre, startNode, startIndx,
+                                  endNode, endIndx)) {
+        mFirst = nullptr;
+      }
+    }
+  }
+
+
+  // Find last node in range.
+
+  bool endIsData = endNode->IsNodeOfType(nsINode::eDATA_NODE);
+
+  if (endIsData || !endNode->HasChildren() || endIndx == 0) {
+    if (mPre) {
+      if (NS_WARN_IF(!endNode->IsContent())) {
+        // Not much else to do here...
+        mLast = nullptr;
+      } else {
+        // If the end node is an empty element and the end offset is 0,
+        // the last element should be the previous node (i.e., shouldn't
+        // include the end node in the range).
+        if (!endIsData && !endNode->HasChildren() && !endIndx) {
+          mLast = PrevNode(endNode);
+          NS_WARNING_ASSERTION(mLast, "PrevNode returned null");
+          if (NS_WARN_IF(!NodeIsInTraversalRange(mLast, mPre,
+                                                 startNode, startIndx,
+                                                 endNode, endIndx))) {
+            mLast = nullptr;
+          }
+        } else {
+          mLast = endNode->AsContent();
+        }
+      }
+    } else {
+      // post-order
+      //
+      // XXX: In the future, if end offset is before the first character in the
+      //      cdata node, should we set mLast to the prev sibling?
+
+      if (!endIsData) {
+        mLast = GetPrevSibling(endNode);
+        NS_WARNING_ASSERTION(mLast, "GetPrevSibling returned null");
+
+        if (!NodeIsInTraversalRange(mLast, mPre,
+                                    startNode, startIndx,
+                                    endNode, endIndx)) {
+          mLast = nullptr;
+        }
+      } else {
+        mLast = endNode->AsContent();
+      }
+    }
+  } else {
+    int32_t indx = endIndx;
+
+    cChild = endNode->GetChildAt(--indx);
+
+    if (NS_WARN_IF(!cChild)) {
+      // No child at offset!
+      NS_NOTREACHED("nsContentIterator::nsContentIterator");
+      return NS_ERROR_FAILURE;
+    }
+
+    if (mPre) {
+      mLast  = GetDeepLastChild(cChild);
+      NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
+
+      if (NS_WARN_IF(!NodeIsInTraversalRange(mLast, mPre,
+                                             startNode, startIndx,
+                                             endNode, endIndx))) {
+        mLast = nullptr;
+      }
+    } else {
+      // post-order
+      mLast = cChild;
+    }
+  }
+
+  // If either first or last is null, they both have to be null!
+
+  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,
+                                     nsTArray<int32_t>* aIndexes)
+{
+  if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
+    return aRoot;
+  }
+  // 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,
+                                     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,
+                                    nsTArray<int32_t>* aIndexes)
+{
+  if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
+    return aRoot;
+  }
+  // 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,
+                                    nsTArray<int32_t>* aIndexes)
+{
+  if (NS_WARN_IF(!aRoot)) {
+    return nullptr;
+  }
+
+  nsIContent* node = aRoot;
+  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,
+                                  nsTArray<int32_t>* aIndexes)
+{
+  if (NS_WARN_IF(!aNode)) {
+    return nullptr;
+  }
+
+  nsINode* parent = aNode->GetParentNode();
+  if (NS_WARN_IF(!parent)) {
+    return nullptr;
+  }
+
+  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,
+                                  nsTArray<int32_t>* aIndexes)
+{
+  if (NS_WARN_IF(!aNode)) {
+    return nullptr;
+  }
+
+  nsINode* parent = aNode->GetParentNode();
+  if (NS_WARN_IF(!parent)) {
+    return nullptr;
+  }
+
+  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, 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, 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 = 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, 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, 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;
+
+    // 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
+  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, aIndexes);
+}
+
+/******************************************************
+ * ContentIterator routines
+ ******************************************************/
+
+void
+nsContentIterator::First()
+{
+  if (mFirst) {
+    mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst);
+    NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
+  }
+
+  mIsDone = mFirst == nullptr;
+}
+
+
+void
+nsContentIterator::Last()
+{
+  // Note that mLast can be nullptr if MakeEmpty() is called in Init() since
+  // at that time, Init() returns NS_OK.
+  if (!mLast) {
+    MOZ_ASSERT(mIsDone);
+    return;
+  }
+
+  mozilla::DebugOnly<nsresult> rv = PositionAt(mLast);
+  NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
+
+  mIsDone = mLast == nullptr;
+}
+
+
+void
+nsContentIterator::Next()
+{
+  if (mIsDone || NS_WARN_IF(!mCurNode)) {
+    return;
+  }
+
+  if (mCurNode == mLast) {
+    mIsDone = true;
+    return;
+  }
+
+  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, &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 == tempNode) {
+    mIsDone = false;  // paranoia
+    return NS_OK;
+  }
+
+  // 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) {
+    if (mPre) {
+      firstNode = NodeToParentOffset(mFirst, &firstOffset);
+      NS_WARNING_ASSERTION(firstNode, "NodeToParentOffset returned null");
+      NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
+
+      if (lastNode->GetChildCount()) {
+        lastOffset = 0;
+      } else {
+        lastNode = NodeToParentOffset(mLast, &lastOffset);
+        NS_WARNING_ASSERTION(lastNode, "NodeToParentOffset returned null");
+        NS_WARNING_ASSERTION(lastOffset >= 0, "bad lastOffset");
+        ++lastOffset;
+      }
+    } else {
+      uint32_t numChildren = firstNode->GetChildCount();
+
+      if (numChildren) {
+        firstOffset = numChildren;
+        NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
+      } else {
+        firstNode = NodeToParentOffset(mFirst, &firstOffset);
+        NS_WARNING_ASSERTION(firstNode, "NodeToParentOffset returned null");
+        NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
+      }
+
+      lastNode = NodeToParentOffset(mLast, &lastOffset);
+      NS_WARNING_ASSERTION(lastNode, "NodeToParentOffset returned null");
+      NS_WARNING_ASSERTION(lastOffset >= 0, "bad lastOffset");
+      ++lastOffset;
+    }
+  }
+
+  // The end positions are always in the range even if it has no parent.  We
+  // need to allow that or 'iter->Init(root)' would assert in Last() or First()
+  // for example, bug 327694.
+  if (mFirst != mCurNode && mLast != mCurNode &&
+      (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) {
+    return nullptr;
+  }
+
+  NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
+
+  return mCurNode;
+}
+
+
+
+
+
+/*====================================================================================*/
+/*====================================================================================*/
+
+
+
+
+
+
+/******************************************************
+ * nsContentSubtreeIterator
+ ******************************************************/
+
+
+/*
+ *  A simple iterator class for traversing the content in "top subtree" order
+ */
+class nsContentSubtreeIterator : public nsContentIterator
+{
+public:
+  nsContentSubtreeIterator() : nsContentIterator(false) {}
+
+  NS_DECL_ISUPPORTS_INHERITED
+  NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsContentSubtreeIterator, nsContentIterator)
+
+  // nsContentIterator overrides ------------------------------
+
+  virtual nsresult Init(nsINode* aRoot) override;
+
+  virtual nsresult Init(nsIDOMRange* aRange) override;
+
+  virtual void Next() override;
+
+  virtual void Prev() override;
+
+  virtual nsresult PositionAt(nsINode* aCurNode) override;
+
+  // Must override these because we don't do PositionAt
+  virtual void First() override;
+
+  // Must override these because we don't do PositionAt
+  virtual void Last() override;
+
+protected:
+  virtual ~nsContentSubtreeIterator() {}
+
+  // Returns the highest inclusive ancestor of aNode that's in the range
+  // (possibly aNode itself).  Returns null if aNode is null, or is not itself
+  // in the range.  A node is in the range if (node, 0) comes strictly after
+  // the range endpoint, and (node, node.length) comes strictly before it, so
+  // the range's start and end nodes will never be considered "in" it.
+  nsIContent* GetTopAncestorInRange(nsINode* aNode);
+
+  // no copy's or assigns  FIX ME
+  nsContentSubtreeIterator(const nsContentSubtreeIterator&);
+  nsContentSubtreeIterator& operator=(const nsContentSubtreeIterator&);
+
+  virtual void LastRelease() override;
+
+  RefPtr<nsRange> mRange;
+
+  // these arrays all typically are used and have elements
+  AutoTArray<nsIContent*, 8> mEndNodes;
+  AutoTArray<int32_t, 8>     mEndOffsets;
+};
+
+NS_IMPL_ADDREF_INHERITED(nsContentSubtreeIterator, nsContentIterator)
+NS_IMPL_RELEASE_INHERITED(nsContentSubtreeIterator, nsContentIterator)
+
+NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator)
+NS_INTERFACE_MAP_END_INHERITING(nsContentIterator)
+
+NS_IMPL_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator, nsContentIterator,
+                                   mRange)
+
+void
+nsContentSubtreeIterator::LastRelease()
+{
+  mRange = nullptr;
+  nsContentIterator::LastRelease();
+}
+
+/******************************************************
+ * repository cruft
+ ******************************************************/
+
+already_AddRefed<nsIContentIterator>
+NS_NewContentSubtreeIterator()
+{
+  nsCOMPtr<nsIContentIterator> iter = new nsContentSubtreeIterator();
+  return iter.forget();
+}
+
+
+
+/******************************************************
+ * Init routines
+ ******************************************************/
+
+
+nsresult
+nsContentSubtreeIterator::Init(nsINode* aRoot)
+{
+  return NS_ERROR_NOT_IMPLEMENTED;
+}
+
+
+nsresult
+nsContentSubtreeIterator::Init(nsIDOMRange* aRange)
+{
+  MOZ_ASSERT(aRange);
+
+  mIsDone = false;
+
+  mRange = static_cast<nsRange*>(aRange);
+
+  // get the start node and offset, convert to nsINode
+  mCommonParent = mRange->GetCommonAncestor();
+  nsINode* startParent = mRange->GetStartParent();
+  int32_t startOffset = mRange->StartOffset();
+  nsINode* endParent = mRange->GetEndParent();
+  int32_t endOffset = mRange->EndOffset();
+  MOZ_ASSERT(mCommonParent && startParent && endParent);
+  // Bug 767169
+  MOZ_ASSERT(uint32_t(startOffset) <= startParent->Length() &&
+             uint32_t(endOffset) <= endParent->Length());
+
+  // short circuit when start node == end node
+  if (startParent == endParent) {
+    nsINode* child = startParent->GetFirstChild();
+
+    if (!child || startOffset == endOffset) {
+      // Text node, empty container, or collapsed
+      MakeEmpty();
+      return NS_OK;
+    }
+  }
+
+  // cache ancestors
+  nsContentUtils::GetAncestorsAndOffsets(endParent->AsDOMNode(), endOffset,
+                                         &mEndNodes, &mEndOffsets);
+
+  nsIContent* firstCandidate = nullptr;
+  nsIContent* lastCandidate = nullptr;
+
+  // find first node in range
+  int32_t offset = mRange->StartOffset();
+
+  nsINode* node = nullptr;
+  if (!startParent->GetChildCount()) {
+    // no children, start at the node itself
+    node = startParent;
+  } else {
+    nsIContent* child = startParent->GetChildAt(offset);
+    if (!child) {
+      // offset after last child
+      node = startParent;
+    } else {
+      firstCandidate = child;
+    }
+  }
+
+  if (!firstCandidate) {
+    // then firstCandidate is next node after node
+    firstCandidate = GetNextSibling(node);
+
+    if (!firstCandidate) {
+      MakeEmpty();
+      return NS_OK;
+    }
+  }
+
+  firstCandidate = GetDeepFirstChild(firstCandidate);
+
+  // confirm that this first possible contained node is indeed contained.  Else
+  // we have a range that does not fully contain any node.
+
+  bool nodeBefore, nodeAfter;
+  MOZ_ALWAYS_SUCCEEDS(
+    nsRange::CompareNodeToRange(firstCandidate, mRange, &nodeBefore, &nodeAfter));
+
+  if (nodeBefore || nodeAfter) {
+    MakeEmpty();
+    return NS_OK;
+  }
+
+  // cool, we have the first node in the range.  Now we walk up its ancestors
+  // to find the most senior that is still in the range.  That's the real first
+  // node.
+  mFirst = GetTopAncestorInRange(firstCandidate);
+
+  // now to find the last node
+  offset = mRange->EndOffset();
+  int32_t numChildren = endParent->GetChildCount();
+
+  if (offset > numChildren) {
+    // Can happen for text nodes
+    offset = numChildren;
+  }
+  if (!offset || !numChildren) {
+    node = endParent;
+  } else {
+    lastCandidate = endParent->GetChildAt(--offset);
+    NS_ASSERTION(lastCandidate,
+                 "tree traversal trouble in nsContentSubtreeIterator::Init");
+  }
+
+  if (!lastCandidate) {
+    // then lastCandidate is prev node before node
+    lastCandidate = GetPrevSibling(node);
+  }
+
+  if (!lastCandidate) {
+    MakeEmpty();
+    return NS_OK;
+  }
+
+  lastCandidate = GetDeepLastChild(lastCandidate);
+
+  // confirm that this last possible contained node is indeed contained.  Else
+  // we have a range that does not fully contain any node.
+
+  MOZ_ALWAYS_SUCCEEDS(
+    nsRange::CompareNodeToRange(lastCandidate, mRange, &nodeBefore, &nodeAfter));
+
+  if (nodeBefore || nodeAfter) {
+    MakeEmpty();
+    return NS_OK;
+  }
+
+  // cool, we have the last node in the range.  Now we walk up its ancestors to
+  // find the most senior that is still in the range.  That's the real first
+  // node.
+  mLast = GetTopAncestorInRange(lastCandidate);
+
+  mCurNode = mFirst;
+
+  return NS_OK;
+}
+
+/****************************************************************
+ * nsContentSubtreeIterator overrides of ContentIterator routines
+ ****************************************************************/
+
+// we can't call PositionAt in a subtree iterator...
+void
+nsContentSubtreeIterator::First()
+{
+  mIsDone = mFirst == nullptr;
+
+  mCurNode = mFirst;
+}
+
+// we can't call PositionAt in a subtree iterator...
+void
+nsContentSubtreeIterator::Last()
+{
+  mIsDone = mLast == nullptr;
+
+  mCurNode = mLast;
+}
+
+
+void
+nsContentSubtreeIterator::Next()
+{
+  if (mIsDone || !mCurNode) {
+    return;
+  }
+
+  if (mCurNode == mLast) {
+    mIsDone = true;
+    return;
+  }
+
+  nsINode* nextNode = GetNextSibling(mCurNode);
+  NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
+
+  int32_t i = mEndNodes.IndexOf(nextNode);
+  while (i != -1) {
+    // as long as we are finding ancestors of the endpoint of the range,
+    // dive down into their children
+    nextNode = nextNode->GetFirstChild();
+    NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
+
+    // should be impossible to get a null pointer.  If we went all the way
+    // down the child chain to the bottom without finding an interior node,
+    // then the previous node should have been the last, which was
+    // was tested at top of routine.
+    i = mEndNodes.IndexOf(nextNode);
+  }
+
+  mCurNode = nextNode;
+
+  // This shouldn't be needed, but since our selection code can put us
+  // in a situation where mLast is in generated content, we need this
+  // to stop the iterator when we've walked past past the last node!
+  mIsDone = mCurNode == nullptr;
+}
+
+
+void
+nsContentSubtreeIterator::Prev()
+{
+  // Prev should be optimized to use the mStartNodes, just as Next
+  // uses mEndNodes.
+  if (mIsDone || !mCurNode) {
+    return;
+  }
+
+  if (mCurNode == mFirst) {
+    mIsDone = true;
+    return;
+  }
+
+  // If any of these function calls return null, so will all succeeding ones,
+  // so mCurNode will wind up set to null.
+  nsINode* prevNode = GetDeepFirstChild(mCurNode);
+
+  prevNode = PrevNode(prevNode);
+
+  prevNode = GetDeepLastChild(prevNode);
+
+  mCurNode = GetTopAncestorInRange(prevNode);
+
+  // This shouldn't be needed, but since our selection code can put us
+  // in a situation where mFirst is in generated content, we need this
+  // to stop the iterator when we've walked past past the first node!
+  mIsDone = mCurNode == nullptr;
+}
+
+
+nsresult
+nsContentSubtreeIterator::PositionAt(nsINode* aCurNode)
+{
+  NS_ERROR("Not implemented!");
+
+  return NS_ERROR_NOT_IMPLEMENTED;
+}
+
+/****************************************************************
+ * nsContentSubtreeIterator helper routines
+ ****************************************************************/
+
+nsIContent*
+nsContentSubtreeIterator::GetTopAncestorInRange(nsINode* aNode)
+{
+  if (!aNode || !aNode->GetParentNode()) {
+    return nullptr;
+  }
+
+  // aNode has a parent, so it must be content.
+  nsIContent* content = aNode->AsContent();
+
+  // sanity check: aNode is itself in the range
+  bool nodeBefore, nodeAfter;
+  nsresult res = nsRange::CompareNodeToRange(aNode, mRange,
+                                             &nodeBefore, &nodeAfter);
+  NS_ASSERTION(NS_SUCCEEDED(res) && !nodeBefore && !nodeAfter,
+               "aNode isn't in mRange, or something else weird happened");
+  if (NS_FAILED(res) || nodeBefore || nodeAfter) {
+    return nullptr;
+  }
+
+  while (content) {
+    nsIContent* parent = content->GetParent();
+    // content always has a parent.  If its parent is the root, however --
+    // i.e., either it's not content, or it is content but its own parent is
+    // null -- then we're finished, since we don't go up to the root.
+    //
+    // We have to special-case this because CompareNodeToRange treats the root
+    // node differently -- see bug 765205.
+    if (!parent || !parent->GetParentNode()) {
+      return content;
+    }
+    MOZ_ALWAYS_SUCCEEDS(
+      nsRange::CompareNodeToRange(parent, mRange, &nodeBefore, &nodeAfter));
+
+    if (nodeBefore || nodeAfter) {
+      return content;
+    }
+    content = parent;
+  }
+
+  MOZ_CRASH("This should only be possible if aNode was null");
+}