The Tor Browser: content/base/src/nsContentIterator.cpp@deefc01c0e14 (annotated)

content/base/src/nsContentIterator.cpp@deefc01c0e14 (annotated)

content/base/src/nsContentIterator.cpp

Thu, 15 Jan 2015 21:03:48 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Thu, 15 Jan 2015 21:03:48 +0100
branch: TOR_BUG_9701
changeset 11: deefc01c0e14
permissions: -rw-r--r--

Integrate friendly tips from Tor colleagues to make (or not) 4.5 alpha 3;
This includes removal of overloaded (but unused) methods, and addition of
a overlooked call to DataStruct::SetData(nsISupports, uint32_t, bool.)

 /* -*- 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 / annotate

content/base/src/nsContentIterator.cpp@deefc01c0e14 (annotated)

content/base/src/nsContentIterator.cpp