summaryrefslogtreecommitdiffstats
path: root/dom/base/nsContentIterator.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'dom/base/nsContentIterator.cpp')
-rw-r--r--dom/base/nsContentIterator.cpp1553
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");
+}