The Tor Browser: comparison content/base/src/nsContentIterator.cpp

--1:000000000000
+:b4993472e69e
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* 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 "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"
+// 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);
+}
+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 (!aStartNode || !aEndNode || !aNode) {
+return false;
+}
+// If a chardata node contains an end point of the traversal range, it is
+// always in the traversal range.
+if (aNode->IsNodeOfType(nsINode::eDATA_NODE) &&
+(aNode == aStartNode || aNode == aEndNode)) {
+return true;
+}
+nsINode* parent = aNode->GetParentNode();
+if (!parent) {
+return false;
+}
+int32_t indx = parent->IndexOf(aNode);
+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);
+virtual ~nsContentIterator();
+// nsIContentIterator interface methods ------------------------------
+virtual nsresult Init(nsINode* aRoot);
+virtual nsresult Init(nsIDOMRange* aRange);
+virtual void First();
+virtual void Last();
+virtual void Next();
+virtual void Prev();
+virtual nsINode* GetCurrentNode();
+virtual bool IsDone();
+virtual nsresult PositionAt(nsINode* aCurNode);
+protected:
+// 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
+nsAutoTArray<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 (!aRoot) {
+return NS_ERROR_NULL_POINTER;
+}
+mIsDone = false;
+mIndexes.Clear();
+if (mPre) {
+mFirst = aRoot;
+mLast  = GetDeepLastChild(aRoot);
+} else {
+mFirst = GetDeepFirstChild(aRoot);
+mLast  = aRoot;
+}
+mCommonParent = aRoot;
+mCurNode = mFirst;
+RebuildIndexStack();
+return NS_OK;
+}
+nsresult
+nsContentIterator::Init(nsIDOMRange* aDOMRange)
+{
+NS_ENSURE_ARG_POINTER(aDOMRange);
+nsRange* range = static_cast<nsRange*>(aDOMRange);
+mIsDone = false;
+// get common content parent
+mCommonParent = range->GetCommonAncestor();
+NS_ENSURE_TRUE(mCommonParent, NS_ERROR_FAILURE);
+// get the start node and offset
+int32_t startIndx = range->StartOffset();
+nsINode* startNode = range->GetStartParent();
+NS_ENSURE_TRUE(startNode, NS_ERROR_FAILURE);
+// get the end node and offset
+int32_t endIndx = range->EndOffset();
+nsINode* endNode = range->GetEndParent();
+NS_ENSURE_TRUE(endNode, 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;
+RebuildIndexStack();
+return NS_OK;
+}
+}
+// Find first node in range.
+nsIContent* cChild = nullptr;
+if (!startIsData && startNode->HasChildren()) {
+cChild = startNode->GetChildAt(startIndx);
+}
+if (!cChild) {
+// no children, must be a text node
+//
+// XXXbz no children might also just mean no children.  So I'm not
+// sure what that comment above is talking about.
+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?
+if (!startIsData) {
+mFirst = GetNextSibling(startNode);
+// 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;
+}
+} else {
+mFirst = startNode->AsContent();
+}
+} else {
+// post-order
+if (startNode->IsContent()) {
+mFirst = startNode->AsContent();
+} else {
+// What else can we do?
+mFirst = nullptr;
+}
+}
+} else {
+if (mPre) {
+mFirst = cChild;
+} else {
+// post-order
+mFirst = GetDeepFirstChild(cChild);
+// 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 (endNode->IsContent()) {
+mLast = endNode->AsContent();
+} else {
+// Not much else to do here...
+mLast = nullptr;
+}
+} 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);
+if (!NodeIsInTraversalRange(mLast, mPre, startNode, startIndx,
+endNode, endIndx)) {
+mLast = nullptr;
+}
+} else {
+mLast = endNode->AsContent();
+}
+}
+} else {
+int32_t indx = endIndx;
+cChild = endNode->GetChildAt(--indx);
+if (!cChild) {
+// No child at offset!
+NS_NOTREACHED("nsContentIterator::nsContentIterator");
+return NS_ERROR_FAILURE;
+}
+if (mPre) {
+mLast  = GetDeepLastChild(cChild);
+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 {
+RebuildIndexStack();
+}
+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 (!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 (!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 (!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 (!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 (!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 (!aNode) {
+return nullptr;
+}
+nsINode* parent = aNode->GetParentNode();
+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.
+// 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);
+}
+// 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 (!aNode) {
+return nullptr;
+}
+nsINode* parent = aNode->GetParentNode();
+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);
+}
+// 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();
+// 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();
+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);
+}
+// 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();
+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);
+}
+// 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();
+// if it has children then prev node is last child
+if (numChildren) {
+nsIContent* lastChild = node->GetLastChild();
+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) {
+#ifdef DEBUG
+nsresult rv =
+#endif
+PositionAt(mFirst);
+NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
+}
+mIsDone = mFirst == nullptr;
+}
+void
+nsContentIterator::Last()
+{
+NS_ASSERTION(mLast, "No last node!");
+if (mLast) {
+#ifdef DEBUG
+nsresult rv =
+#endif
+PositionAt(mLast);
+NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
+}
+mIsDone = mLast == nullptr;
+}
+void
+nsContentIterator::Next()
+{
+if (mIsDone || !mCurNode) {
+return;
+}
+if (mCurNode == mLast) {
+mIsDone = true;
+return;
+}
+mCurNode = NextNode(mCurNode, &mIndexes);
+}
+void
+nsContentIterator::Prev()
+{
+if (mIsDone || !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 (!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);
+if (lastNode->GetChildCount()) {
+lastOffset = 0;
+} else {
+lastNode = NodeToParentOffset(mLast, &lastOffset);
+++lastOffset;
+}
+} else {
+uint32_t numChildren = firstNode->GetChildCount();
+if (numChildren) {
+firstOffset = numChildren;
+} else {
+firstNode = NodeToParentOffset(mFirst, &firstOffset);
+}
+lastNode = NodeToParentOffset(mLast, &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 &&
+(!firstNode || !lastNode ||
+!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!
+nsAutoTArray<nsINode*, 8>     oldParentStack;
+nsAutoTArray<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 (!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 (!parent) {
+// this node has no parent, and thus no index
+break;
+}
+int32_t indx = parent->IndexOf(newCurNode);
+// 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) {}
+virtual ~nsContentSubtreeIterator() {}
+NS_DECL_ISUPPORTS_INHERITED
+NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsContentSubtreeIterator, nsContentIterator)
+// nsContentIterator overrides ------------------------------
+virtual nsresult Init(nsINode* aRoot);
+virtual nsresult Init(nsIDOMRange* aRange);
+virtual void Next();
+virtual void Prev();
+virtual nsresult PositionAt(nsINode* aCurNode);
+// Must override these because we don't do PositionAt
+virtual void First();
+// Must override these because we don't do PositionAt
+virtual void Last();
+protected:
+// 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() MOZ_OVERRIDE;
+nsRefPtr<nsRange> mRange;
+// these arrays all typically are used and have elements
+nsAutoTArray<nsIContent*, 8> mEndNodes;
+nsAutoTArray<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;
+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_TRUE(NS_SUCCEEDED(
+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_TRUE(NS_SUCCEEDED(
+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_TRUE(NS_SUCCEEDED(
+nsRange::CompareNodeToRange(parent, mRange, &nodeBefore, &nodeAfter)));
+if (nodeBefore || nodeAfter) {
+return content;
+}
+content = parent;
+}
+MOZ_CRASH("This should only be possible if aNode was null");
+}

The Tor Browser / file comparison

comparison: content/base/src/nsContentIterator.cpp

content/base/src/nsContentIterator.cpp