michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "nsISupports.h"
michael@0: #include "nsIDOMNodeList.h"
michael@0: #include "nsIContentIterator.h"
michael@0: #include "nsRange.h"
michael@0: #include "nsIContent.h"
michael@0: #include "nsCOMPtr.h"
michael@0: #include "nsTArray.h"
michael@0: #include "nsContentUtils.h"
michael@0: #include "nsINode.h"
michael@0: #include "nsCycleCollectionParticipant.h"
michael@0: 
michael@0: // couple of utility static functs
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // NodeToParentOffset: returns the node's parent and offset.
michael@0: //
michael@0: 
michael@0: static nsINode*
michael@0: NodeToParentOffset(nsINode* aNode, int32_t* aOffset)
michael@0: {
michael@0:   *aOffset = 0;
michael@0: 
michael@0:   nsINode* parent = aNode->GetParentNode();
michael@0: 
michael@0:   if (parent) {
michael@0:     *aOffset = parent->IndexOf(aNode);
michael@0:   }
michael@0: 
michael@0:   return parent;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // NodeIsInTraversalRange: returns true if content is visited during
michael@0: // the traversal of the range in the specified mode.
michael@0: //
michael@0: static bool
michael@0: NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode,
michael@0:                        nsINode* aStartNode, int32_t aStartOffset,
michael@0:                        nsINode* aEndNode, int32_t aEndOffset)
michael@0: {
michael@0:   if (!aStartNode || !aEndNode || !aNode) {
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   // If a chardata node contains an end point of the traversal range, it is
michael@0:   // always in the traversal range.
michael@0:   if (aNode->IsNodeOfType(nsINode::eDATA_NODE) &&
michael@0:       (aNode == aStartNode || aNode == aEndNode)) {
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0:   nsINode* parent = aNode->GetParentNode();
michael@0:   if (!parent) {
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   int32_t indx = parent->IndexOf(aNode);
michael@0: 
michael@0:   if (!aIsPreMode) {
michael@0:     ++indx;
michael@0:   }
michael@0: 
michael@0:   return nsContentUtils::ComparePoints(aStartNode, aStartOffset,
michael@0:                                        parent, indx) <= 0 &&
michael@0:          nsContentUtils::ComparePoints(aEndNode, aEndOffset,
michael@0:                                        parent, indx) >= 0;
michael@0: }
michael@0: 
michael@0: 
michael@0: 
michael@0: /*
michael@0:  *  A simple iterator class for traversing the content in "close tag" order
michael@0:  */
michael@0: class nsContentIterator : public nsIContentIterator
michael@0: {
michael@0: public:
michael@0:   NS_DECL_CYCLE_COLLECTING_ISUPPORTS
michael@0:   NS_DECL_CYCLE_COLLECTION_CLASS(nsContentIterator)
michael@0: 
michael@0:   explicit nsContentIterator(bool aPre);
michael@0:   virtual ~nsContentIterator();
michael@0: 
michael@0:   // nsIContentIterator interface methods ------------------------------
michael@0: 
michael@0:   virtual nsresult Init(nsINode* aRoot);
michael@0: 
michael@0:   virtual nsresult Init(nsIDOMRange* aRange);
michael@0: 
michael@0:   virtual void First();
michael@0: 
michael@0:   virtual void Last();
michael@0: 
michael@0:   virtual void Next();
michael@0: 
michael@0:   virtual void Prev();
michael@0: 
michael@0:   virtual nsINode* GetCurrentNode();
michael@0: 
michael@0:   virtual bool IsDone();
michael@0: 
michael@0:   virtual nsresult PositionAt(nsINode* aCurNode);
michael@0: 
michael@0: protected:
michael@0: 
michael@0:   // Recursively get the deepest first/last child of aRoot.  This will return
michael@0:   // aRoot itself if it has no children.
michael@0:   nsINode* GetDeepFirstChild(nsINode* aRoot,
michael@0:                              nsTArray<int32_t>* aIndexes = nullptr);
michael@0:   nsIContent* GetDeepFirstChild(nsIContent* aRoot,
michael@0:                                 nsTArray<int32_t>* aIndexes = nullptr);
michael@0:   nsINode* GetDeepLastChild(nsINode* aRoot,
michael@0:                             nsTArray<int32_t>* aIndexes = nullptr);
michael@0:   nsIContent* GetDeepLastChild(nsIContent* aRoot,
michael@0:                                nsTArray<int32_t>* aIndexes = nullptr);
michael@0: 
michael@0:   // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
michael@0:   // etc.  Returns null if aNode and all its ancestors have no next/previous
michael@0:   // sibling.
michael@0:   nsIContent* GetNextSibling(nsINode* aNode,
michael@0:                              nsTArray<int32_t>* aIndexes = nullptr);
michael@0:   nsIContent* GetPrevSibling(nsINode* aNode,
michael@0:                              nsTArray<int32_t>* aIndexes = nullptr);
michael@0: 
michael@0:   nsINode* NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
michael@0:   nsINode* PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
michael@0: 
michael@0:   // WARNING: This function is expensive
michael@0:   nsresult RebuildIndexStack();
michael@0: 
michael@0:   void MakeEmpty();
michael@0: 
michael@0:   virtual void LastRelease();
michael@0: 
michael@0:   nsCOMPtr<nsINode> mCurNode;
michael@0:   nsCOMPtr<nsINode> mFirst;
michael@0:   nsCOMPtr<nsINode> mLast;
michael@0:   nsCOMPtr<nsINode> mCommonParent;
michael@0: 
michael@0:   // used by nsContentIterator to cache indices
michael@0:   nsAutoTArray<int32_t, 8> mIndexes;
michael@0: 
michael@0:   // used by nsSubtreeIterator to cache indices.  Why put them in the base
michael@0:   // class?  Because otherwise I have to duplicate the routines GetNextSibling
michael@0:   // etc across both classes, with slight variations for caching.  Or
michael@0:   // alternately, create a base class for the cache itself and have all the
michael@0:   // cache manipulation go through a vptr.  I think this is the best space and
michael@0:   // speed combo, even though it's ugly.
michael@0:   int32_t mCachedIndex;
michael@0:   // another note about mCachedIndex: why should the subtree iterator use a
michael@0:   // trivial cached index instead of the mre robust array of indicies (which is
michael@0:   // what the basic content iterator uses)?  The reason is that subtree
michael@0:   // iterators do not do much transitioning between parents and children.  They
michael@0:   // tend to stay at the same level.  In fact, you can prove (though I won't
michael@0:   // attempt it here) that they change levels at most n+m times, where n is the
michael@0:   // height of the parent hierarchy from the range start to the common
michael@0:   // ancestor, and m is the the height of the parent hierarchy from the range
michael@0:   // end to the common ancestor.  If we used the index array, we would pay the
michael@0:   // price up front for n, and then pay the cost for m on the fly later on.
michael@0:   // With the simple cache, we only "pay as we go".  Either way, we call
michael@0:   // IndexOf() once for each change of level in the hierarchy.  Since a trivial
michael@0:   // index is much simpler, we use it for the subtree iterator.
michael@0: 
michael@0:   bool mIsDone;
michael@0:   bool mPre;
michael@0: 
michael@0: private:
michael@0: 
michael@0:   // no copies or assigns  FIX ME
michael@0:   nsContentIterator(const nsContentIterator&);
michael@0:   nsContentIterator& operator=(const nsContentIterator&);
michael@0: 
michael@0: };
michael@0: 
michael@0: 
michael@0: /******************************************************
michael@0:  * repository cruft
michael@0:  ******************************************************/
michael@0: 
michael@0: already_AddRefed<nsIContentIterator>
michael@0: NS_NewContentIterator()
michael@0: {
michael@0:   nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(false);
michael@0:   return iter.forget();
michael@0: }
michael@0: 
michael@0: 
michael@0: already_AddRefed<nsIContentIterator>
michael@0: NS_NewPreContentIterator()
michael@0: {
michael@0:   nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(true);
michael@0:   return iter.forget();
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************
michael@0:  * XPCOM cruft
michael@0:  ******************************************************/
michael@0: 
michael@0: NS_IMPL_CYCLE_COLLECTING_ADDREF(nsContentIterator)
michael@0: NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(nsContentIterator,
michael@0:                                                    LastRelease())
michael@0: 
michael@0: NS_INTERFACE_MAP_BEGIN(nsContentIterator)
michael@0:   NS_INTERFACE_MAP_ENTRY(nsIContentIterator)
michael@0:   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIContentIterator)
michael@0:   NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION(nsContentIterator)
michael@0: NS_INTERFACE_MAP_END
michael@0: 
michael@0: NS_IMPL_CYCLE_COLLECTION(nsContentIterator,
michael@0:                          mCurNode,
michael@0:                          mFirst,
michael@0:                          mLast,
michael@0:                          mCommonParent)
michael@0: 
michael@0: void
michael@0: nsContentIterator::LastRelease()
michael@0: {
michael@0:   mCurNode = nullptr;
michael@0:   mFirst = nullptr;
michael@0:   mLast = nullptr;
michael@0:   mCommonParent = nullptr;
michael@0: }
michael@0: 
michael@0: /******************************************************
michael@0:  * constructor/destructor
michael@0:  ******************************************************/
michael@0: 
michael@0: nsContentIterator::nsContentIterator(bool aPre) :
michael@0:   // don't need to explicitly initialize |nsCOMPtr|s, they will automatically
michael@0:   // be nullptr
michael@0:   mCachedIndex(0), mIsDone(false), mPre(aPre)
michael@0: {
michael@0: }
michael@0: 
michael@0: 
michael@0: nsContentIterator::~nsContentIterator()
michael@0: {
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************
michael@0:  * Init routines
michael@0:  ******************************************************/
michael@0: 
michael@0: 
michael@0: nsresult
michael@0: nsContentIterator::Init(nsINode* aRoot)
michael@0: {
michael@0:   if (!aRoot) {
michael@0:     return NS_ERROR_NULL_POINTER;
michael@0:   }
michael@0: 
michael@0:   mIsDone = false;
michael@0:   mIndexes.Clear();
michael@0: 
michael@0:   if (mPre) {
michael@0:     mFirst = aRoot;
michael@0:     mLast  = GetDeepLastChild(aRoot);
michael@0:   } else {
michael@0:     mFirst = GetDeepFirstChild(aRoot);
michael@0:     mLast  = aRoot;
michael@0:   }
michael@0: 
michael@0:   mCommonParent = aRoot;
michael@0:   mCurNode = mFirst;
michael@0:   RebuildIndexStack();
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsContentIterator::Init(nsIDOMRange* aDOMRange)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aDOMRange);
michael@0:   nsRange* range = static_cast<nsRange*>(aDOMRange);
michael@0: 
michael@0:   mIsDone = false;
michael@0: 
michael@0:   // get common content parent
michael@0:   mCommonParent = range->GetCommonAncestor();
michael@0:   NS_ENSURE_TRUE(mCommonParent, NS_ERROR_FAILURE);
michael@0: 
michael@0:   // get the start node and offset
michael@0:   int32_t startIndx = range->StartOffset();
michael@0:   nsINode* startNode = range->GetStartParent();
michael@0:   NS_ENSURE_TRUE(startNode, NS_ERROR_FAILURE);
michael@0: 
michael@0:   // get the end node and offset
michael@0:   int32_t endIndx = range->EndOffset();
michael@0:   nsINode* endNode = range->GetEndParent();
michael@0:   NS_ENSURE_TRUE(endNode, NS_ERROR_FAILURE);
michael@0: 
michael@0:   bool startIsData = startNode->IsNodeOfType(nsINode::eDATA_NODE);
michael@0: 
michael@0:   // short circuit when start node == end node
michael@0:   if (startNode == endNode) {
michael@0:     // Check to see if we have a collapsed range, if so, there is nothing to
michael@0:     // iterate over.
michael@0:     //
michael@0:     // XXX: CharacterDataNodes (text nodes) are currently an exception, since
michael@0:     //      we always want to be able to iterate text nodes at the end points
michael@0:     //      of a range.
michael@0: 
michael@0:     if (!startIsData && startIndx == endIndx) {
michael@0:       MakeEmpty();
michael@0:       return NS_OK;
michael@0:     }
michael@0: 
michael@0:     if (startIsData) {
michael@0:       // It's a character data node.
michael@0:       mFirst   = startNode->AsContent();
michael@0:       mLast    = mFirst;
michael@0:       mCurNode = mFirst;
michael@0: 
michael@0:       RebuildIndexStack();
michael@0:       return NS_OK;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Find first node in range.
michael@0: 
michael@0:   nsIContent* cChild = nullptr;
michael@0: 
michael@0:   if (!startIsData && startNode->HasChildren()) {
michael@0:     cChild = startNode->GetChildAt(startIndx);
michael@0:   }
michael@0: 
michael@0:   if (!cChild) {
michael@0:     // no children, must be a text node
michael@0:     //
michael@0:     // XXXbz no children might also just mean no children.  So I'm not
michael@0:     // sure what that comment above is talking about.
michael@0: 
michael@0:     if (mPre) {
michael@0:       // XXX: In the future, if start offset is after the last
michael@0:       //      character in the cdata node, should we set mFirst to
michael@0:       //      the next sibling?
michael@0: 
michael@0:       if (!startIsData) {
michael@0:         mFirst = GetNextSibling(startNode);
michael@0: 
michael@0:         // Does mFirst node really intersect the range?  The range could be
michael@0:         // 'degenerate', i.e., not collapsed but still contain no content.
michael@0: 
michael@0:         if (mFirst && !NodeIsInTraversalRange(mFirst, mPre, startNode,
michael@0:                                               startIndx, endNode, endIndx)) {
michael@0:           mFirst = nullptr;
michael@0:         }
michael@0:       } else {
michael@0:         mFirst = startNode->AsContent();
michael@0:       }
michael@0:     } else {
michael@0:       // post-order
michael@0:       if (startNode->IsContent()) {
michael@0:         mFirst = startNode->AsContent();
michael@0:       } else {
michael@0:         // What else can we do?
michael@0:         mFirst = nullptr;
michael@0:       }
michael@0:     }
michael@0:   } else {
michael@0:     if (mPre) {
michael@0:       mFirst = cChild;
michael@0:     } else {
michael@0:       // post-order
michael@0:       mFirst = GetDeepFirstChild(cChild);
michael@0: 
michael@0:       // Does mFirst node really intersect the range?  The range could be
michael@0:       // 'degenerate', i.e., not collapsed but still contain no content.
michael@0: 
michael@0:       if (mFirst && !NodeIsInTraversalRange(mFirst, mPre, startNode, startIndx,
michael@0:                                             endNode, endIndx)) {
michael@0:         mFirst = nullptr;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0: 
michael@0:   // Find last node in range.
michael@0: 
michael@0:   bool endIsData = endNode->IsNodeOfType(nsINode::eDATA_NODE);
michael@0: 
michael@0:   if (endIsData || !endNode->HasChildren() || endIndx == 0) {
michael@0:     if (mPre) {
michael@0:       if (endNode->IsContent()) {
michael@0:         mLast = endNode->AsContent();
michael@0:       } else {
michael@0:         // Not much else to do here...
michael@0:         mLast = nullptr;
michael@0:       }
michael@0:     } else {
michael@0:       // post-order
michael@0:       //
michael@0:       // XXX: In the future, if end offset is before the first character in the
michael@0:       //      cdata node, should we set mLast to the prev sibling?
michael@0: 
michael@0:       if (!endIsData) {
michael@0:         mLast = GetPrevSibling(endNode);
michael@0: 
michael@0:         if (!NodeIsInTraversalRange(mLast, mPre, startNode, startIndx,
michael@0:                                     endNode, endIndx)) {
michael@0:           mLast = nullptr;
michael@0:         }
michael@0:       } else {
michael@0:         mLast = endNode->AsContent();
michael@0:       }
michael@0:     }
michael@0:   } else {
michael@0:     int32_t indx = endIndx;
michael@0: 
michael@0:     cChild = endNode->GetChildAt(--indx);
michael@0: 
michael@0:     if (!cChild) {
michael@0:       // No child at offset!
michael@0:       NS_NOTREACHED("nsContentIterator::nsContentIterator");
michael@0:       return NS_ERROR_FAILURE;
michael@0:     }
michael@0: 
michael@0:     if (mPre) {
michael@0:       mLast  = GetDeepLastChild(cChild);
michael@0: 
michael@0:       if (!NodeIsInTraversalRange(mLast, mPre, startNode, startIndx,
michael@0:                                   endNode, endIndx)) {
michael@0:         mLast = nullptr;
michael@0:       }
michael@0:     } else {
michael@0:       // post-order
michael@0:       mLast = cChild;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // If either first or last is null, they both have to be null!
michael@0: 
michael@0:   if (!mFirst || !mLast) {
michael@0:     mFirst = nullptr;
michael@0:     mLast  = nullptr;
michael@0:   }
michael@0: 
michael@0:   mCurNode = mFirst;
michael@0:   mIsDone  = !mCurNode;
michael@0: 
michael@0:   if (!mCurNode) {
michael@0:     mIndexes.Clear();
michael@0:   } else {
michael@0:     RebuildIndexStack();
michael@0:   }
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************
michael@0:  * Helper routines
michael@0:  ******************************************************/
michael@0: // WARNING: This function is expensive
michael@0: nsresult
michael@0: nsContentIterator::RebuildIndexStack()
michael@0: {
michael@0:   // Make sure we start at the right indexes on the stack!  Build array up
michael@0:   // to common parent of start and end.  Perhaps it's too many entries, but
michael@0:   // that's far better than too few.
michael@0:   nsINode* parent;
michael@0:   nsINode* current;
michael@0: 
michael@0:   mIndexes.Clear();
michael@0:   current = mCurNode;
michael@0:   if (!current) {
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   while (current != mCommonParent) {
michael@0:     parent = current->GetParentNode();
michael@0: 
michael@0:     if (!parent) {
michael@0:       return NS_ERROR_FAILURE;
michael@0:     }
michael@0: 
michael@0:     mIndexes.InsertElementAt(0, parent->IndexOf(current));
michael@0: 
michael@0:     current = parent;
michael@0:   }
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: void
michael@0: nsContentIterator::MakeEmpty()
michael@0: {
michael@0:   mCurNode      = nullptr;
michael@0:   mFirst        = nullptr;
michael@0:   mLast         = nullptr;
michael@0:   mCommonParent = nullptr;
michael@0:   mIsDone       = true;
michael@0:   mIndexes.Clear();
michael@0: }
michael@0: 
michael@0: nsINode*
michael@0: nsContentIterator::GetDeepFirstChild(nsINode* aRoot,
michael@0:                                      nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   if (!aRoot || !aRoot->HasChildren()) {
michael@0:     return aRoot;
michael@0:   }
michael@0:   // We can't pass aRoot itself to the full GetDeepFirstChild, because that
michael@0:   // will only take nsIContent and aRoot might be a document.  Pass aRoot's
michael@0:   // child, but be sure to preserve aIndexes.
michael@0:   if (aIndexes) {
michael@0:     aIndexes->AppendElement(0);
michael@0:   }
michael@0:   return GetDeepFirstChild(aRoot->GetFirstChild(), aIndexes);
michael@0: }
michael@0: 
michael@0: nsIContent*
michael@0: nsContentIterator::GetDeepFirstChild(nsIContent* aRoot,
michael@0:                                      nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   if (!aRoot) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   nsIContent* node = aRoot;
michael@0:   nsIContent* child = node->GetFirstChild();
michael@0: 
michael@0:   while (child) {
michael@0:     if (aIndexes) {
michael@0:       // Add this node to the stack of indexes
michael@0:       aIndexes->AppendElement(0);
michael@0:     }
michael@0:     node = child;
michael@0:     child = node->GetFirstChild();
michael@0:   }
michael@0: 
michael@0:   return node;
michael@0: }
michael@0: 
michael@0: nsINode*
michael@0: nsContentIterator::GetDeepLastChild(nsINode* aRoot,
michael@0:                                     nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   if (!aRoot || !aRoot->HasChildren()) {
michael@0:     return aRoot;
michael@0:   }
michael@0:   // We can't pass aRoot itself to the full GetDeepLastChild, because that will
michael@0:   // only take nsIContent and aRoot might be a document.  Pass aRoot's child,
michael@0:   // but be sure to preserve aIndexes.
michael@0:   if (aIndexes) {
michael@0:     aIndexes->AppendElement(aRoot->GetChildCount() - 1);
michael@0:   }
michael@0:   return GetDeepLastChild(aRoot->GetLastChild(), aIndexes);
michael@0: }
michael@0: 
michael@0: nsIContent*
michael@0: nsContentIterator::GetDeepLastChild(nsIContent* aRoot,
michael@0:                                     nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   if (!aRoot) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   nsIContent* node = aRoot;
michael@0:   int32_t numChildren = node->GetChildCount();
michael@0: 
michael@0:   while (numChildren) {
michael@0:     nsIContent* child = node->GetChildAt(--numChildren);
michael@0: 
michael@0:     if (aIndexes) {
michael@0:       // Add this node to the stack of indexes
michael@0:       aIndexes->AppendElement(numChildren);
michael@0:     }
michael@0:     numChildren = child->GetChildCount();
michael@0:     node = child;
michael@0:   }
michael@0: 
michael@0:   return node;
michael@0: }
michael@0: 
michael@0: // Get the next sibling, or parent's next sibling, or grandpa's next sibling...
michael@0: nsIContent*
michael@0: nsContentIterator::GetNextSibling(nsINode* aNode,
michael@0:                                   nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   if (!aNode) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   nsINode* parent = aNode->GetParentNode();
michael@0:   if (!parent) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   int32_t indx = 0;
michael@0: 
michael@0:   NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
michael@0:                "ContentIterator stack underflow");
michael@0:   if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:     // use the last entry on the Indexes array for the current index
michael@0:     indx = (*aIndexes)[aIndexes->Length()-1];
michael@0:   } else {
michael@0:     indx = mCachedIndex;
michael@0:   }
michael@0: 
michael@0:   // reverify that the index of the current node hasn't changed.
michael@0:   // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
michael@0:   // ignore result this time - the index may now be out of range.
michael@0:   nsIContent* sib = parent->GetChildAt(indx);
michael@0:   if (sib != aNode) {
michael@0:     // someone changed our index - find the new index the painful way
michael@0:     indx = parent->IndexOf(aNode);
michael@0:   }
michael@0: 
michael@0:   // indx is now canonically correct
michael@0:   if ((sib = parent->GetChildAt(++indx))) {
michael@0:     // update index cache
michael@0:     if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:       aIndexes->ElementAt(aIndexes->Length()-1) = indx;
michael@0:     } else {
michael@0:       mCachedIndex = indx;
michael@0:     }
michael@0:   } else {
michael@0:     if (parent != mCommonParent) {
michael@0:       if (aIndexes) {
michael@0:         // pop node off the stack, go up one level and return parent or fail.
michael@0:         // Don't leave the index empty, especially if we're
michael@0:         // returning nullptr.  This confuses other parts of the code.
michael@0:         if (aIndexes->Length() > 1) {
michael@0:           aIndexes->RemoveElementAt(aIndexes->Length()-1);
michael@0:         }
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     // ok to leave cache out of date here if parent == mCommonParent?
michael@0:     sib = GetNextSibling(parent, aIndexes);
michael@0:   }
michael@0: 
michael@0:   return sib;
michael@0: }
michael@0: 
michael@0: // Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
michael@0: nsIContent*
michael@0: nsContentIterator::GetPrevSibling(nsINode* aNode,
michael@0:                                   nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   if (!aNode) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   nsINode* parent = aNode->GetParentNode();
michael@0:   if (!parent) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   int32_t indx = 0;
michael@0: 
michael@0:   NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
michael@0:                "ContentIterator stack underflow");
michael@0:   if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:     // use the last entry on the Indexes array for the current index
michael@0:     indx = (*aIndexes)[aIndexes->Length()-1];
michael@0:   } else {
michael@0:     indx = mCachedIndex;
michael@0:   }
michael@0: 
michael@0:   // reverify that the index of the current node hasn't changed
michael@0:   // ignore result this time - the index may now be out of range.
michael@0:   nsIContent* sib = parent->GetChildAt(indx);
michael@0:   if (sib != aNode) {
michael@0:     // someone changed our index - find the new index the painful way
michael@0:     indx = parent->IndexOf(aNode);
michael@0:   }
michael@0: 
michael@0:   // indx is now canonically correct
michael@0:   if (indx > 0 && (sib = parent->GetChildAt(--indx))) {
michael@0:     // update index cache
michael@0:     if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:       aIndexes->ElementAt(aIndexes->Length()-1) = indx;
michael@0:     } else {
michael@0:       mCachedIndex = indx;
michael@0:     }
michael@0:   } else if (parent != mCommonParent) {
michael@0:     if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:       // pop node off the stack, go up one level and try again.
michael@0:       aIndexes->RemoveElementAt(aIndexes->Length()-1);
michael@0:     }
michael@0:     return GetPrevSibling(parent, aIndexes);
michael@0:   }
michael@0: 
michael@0:   return sib;
michael@0: }
michael@0: 
michael@0: nsINode*
michael@0: nsContentIterator::NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   nsINode* node = aNode;
michael@0: 
michael@0:   // if we are a Pre-order iterator, use pre-order
michael@0:   if (mPre) {
michael@0:     // if it has children then next node is first child
michael@0:     if (node->HasChildren()) {
michael@0:       nsIContent* firstChild = node->GetFirstChild();
michael@0: 
michael@0:       // update cache
michael@0:       if (aIndexes) {
michael@0:         // push an entry on the index stack
michael@0:         aIndexes->AppendElement(0);
michael@0:       } else {
michael@0:         mCachedIndex = 0;
michael@0:       }
michael@0: 
michael@0:       return firstChild;
michael@0:     }
michael@0: 
michael@0:     // else next sibling is next
michael@0:     return GetNextSibling(node, aIndexes);
michael@0:   }
michael@0: 
michael@0:   // post-order
michael@0:   nsINode* parent = node->GetParentNode();
michael@0:   nsIContent* sibling = nullptr;
michael@0:   int32_t indx = 0;
michael@0: 
michael@0:   // get the cached index
michael@0:   NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
michael@0:                "ContentIterator stack underflow");
michael@0:   if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:     // use the last entry on the Indexes array for the current index
michael@0:     indx = (*aIndexes)[aIndexes->Length()-1];
michael@0:   } else {
michael@0:     indx = mCachedIndex;
michael@0:   }
michael@0: 
michael@0:   // reverify that the index of the current node hasn't changed.  not super
michael@0:   // cheap, but a lot cheaper than IndexOf(), and still O(1).  ignore result
michael@0:   // this time - the index may now be out of range.
michael@0:   if (indx >= 0) {
michael@0:     sibling = parent->GetChildAt(indx);
michael@0:   }
michael@0:   if (sibling != node) {
michael@0:     // someone changed our index - find the new index the painful way
michael@0:     indx = parent->IndexOf(node);
michael@0:   }
michael@0: 
michael@0:   // indx is now canonically correct
michael@0:   sibling = parent->GetChildAt(++indx);
michael@0:   if (sibling) {
michael@0:     // update cache
michael@0:     if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:       // replace an entry on the index stack
michael@0:       aIndexes->ElementAt(aIndexes->Length()-1) = indx;
michael@0:     } else {
michael@0:       mCachedIndex = indx;
michael@0:     }
michael@0: 
michael@0:     // next node is sibling's "deep left" child
michael@0:     return GetDeepFirstChild(sibling, aIndexes);
michael@0:   }
michael@0: 
michael@0:   // else it's the parent, update cache
michael@0:   if (aIndexes) {
michael@0:     // Pop an entry off the index stack.  Don't leave the index empty,
michael@0:     // especially if we're returning nullptr.  This confuses other parts of the
michael@0:     // code.
michael@0:     if (aIndexes->Length() > 1) {
michael@0:       aIndexes->RemoveElementAt(aIndexes->Length()-1);
michael@0:     }
michael@0:   } else {
michael@0:     // this might be wrong, but we are better off guessing
michael@0:     mCachedIndex = 0;
michael@0:   }
michael@0: 
michael@0:   return parent;
michael@0: }
michael@0: 
michael@0: nsINode*
michael@0: nsContentIterator::PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
michael@0: {
michael@0:   nsINode* node = aNode;
michael@0: 
michael@0:   // if we are a Pre-order iterator, use pre-order
michael@0:   if (mPre) {
michael@0:     nsINode* parent = node->GetParentNode();
michael@0:     nsIContent* sibling = nullptr;
michael@0:     int32_t indx = 0;
michael@0: 
michael@0:     // get the cached index
michael@0:     NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
michael@0:                  "ContentIterator stack underflow");
michael@0:     if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:       // use the last entry on the Indexes array for the current index
michael@0:       indx = (*aIndexes)[aIndexes->Length()-1];
michael@0:     } else {
michael@0:       indx = mCachedIndex;
michael@0:     }
michael@0: 
michael@0:     // reverify that the index of the current node hasn't changed.  not super
michael@0:     // cheap, but a lot cheaper than IndexOf(), and still O(1).  ignore result
michael@0:     // this time - the index may now be out of range.
michael@0:     if (indx >= 0) {
michael@0:       sibling = parent->GetChildAt(indx);
michael@0:     }
michael@0: 
michael@0:     if (sibling != node) {
michael@0:       // someone changed our index - find the new index the painful way
michael@0:       indx = parent->IndexOf(node);
michael@0:     }
michael@0: 
michael@0:     // indx is now canonically correct
michael@0:     if (indx && (sibling = parent->GetChildAt(--indx))) {
michael@0:       // update cache
michael@0:       if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:         // replace an entry on the index stack
michael@0:         aIndexes->ElementAt(aIndexes->Length()-1) = indx;
michael@0:       } else {
michael@0:         mCachedIndex = indx;
michael@0:       }
michael@0: 
michael@0:       // prev node is sibling's "deep right" child
michael@0:       return GetDeepLastChild(sibling, aIndexes);
michael@0:     }
michael@0: 
michael@0:     // else it's the parent, update cache
michael@0:     if (aIndexes && !aIndexes->IsEmpty()) {
michael@0:       // pop an entry off the index stack
michael@0:       aIndexes->RemoveElementAt(aIndexes->Length()-1);
michael@0:     } else {
michael@0:       // this might be wrong, but we are better off guessing
michael@0:       mCachedIndex = 0;
michael@0:     }
michael@0:     return parent;
michael@0:   }
michael@0: 
michael@0:   // post-order
michael@0:   int32_t numChildren = node->GetChildCount();
michael@0: 
michael@0:   // if it has children then prev node is last child
michael@0:   if (numChildren) {
michael@0:     nsIContent* lastChild = node->GetLastChild();
michael@0:     numChildren--;
michael@0: 
michael@0:     // update cache
michael@0:     if (aIndexes) {
michael@0:       // push an entry on the index stack
michael@0:       aIndexes->AppendElement(numChildren);
michael@0:     } else {
michael@0:       mCachedIndex = numChildren;
michael@0:     }
michael@0: 
michael@0:     return lastChild;
michael@0:   }
michael@0: 
michael@0:   // else prev sibling is previous
michael@0:   return GetPrevSibling(node, aIndexes);
michael@0: }
michael@0: 
michael@0: /******************************************************
michael@0:  * ContentIterator routines
michael@0:  ******************************************************/
michael@0: 
michael@0: void
michael@0: nsContentIterator::First()
michael@0: {
michael@0:   if (mFirst) {
michael@0: #ifdef DEBUG
michael@0:     nsresult rv =
michael@0: #endif
michael@0:     PositionAt(mFirst);
michael@0: 
michael@0:     NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
michael@0:   }
michael@0: 
michael@0:   mIsDone = mFirst == nullptr;
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: nsContentIterator::Last()
michael@0: {
michael@0:   NS_ASSERTION(mLast, "No last node!");
michael@0: 
michael@0:   if (mLast) {
michael@0: #ifdef DEBUG
michael@0:     nsresult rv =
michael@0: #endif
michael@0:     PositionAt(mLast);
michael@0: 
michael@0:     NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
michael@0:   }
michael@0: 
michael@0:   mIsDone = mLast == nullptr;
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: nsContentIterator::Next()
michael@0: {
michael@0:   if (mIsDone || !mCurNode) {
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   if (mCurNode == mLast) {
michael@0:     mIsDone = true;
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   mCurNode = NextNode(mCurNode, &mIndexes);
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: nsContentIterator::Prev()
michael@0: {
michael@0:   if (mIsDone || !mCurNode) {
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   if (mCurNode == mFirst) {
michael@0:     mIsDone = true;
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   mCurNode = PrevNode(mCurNode, &mIndexes);
michael@0: }
michael@0: 
michael@0: 
michael@0: bool
michael@0: nsContentIterator::IsDone()
michael@0: {
michael@0:   return mIsDone;
michael@0: }
michael@0: 
michael@0: 
michael@0: // Keeping arrays of indexes for the stack of nodes makes PositionAt
michael@0: // interesting...
michael@0: nsresult
michael@0: nsContentIterator::PositionAt(nsINode* aCurNode)
michael@0: {
michael@0:   if (!aCurNode) {
michael@0:     return NS_ERROR_NULL_POINTER;
michael@0:   }
michael@0: 
michael@0:   nsINode* newCurNode = aCurNode;
michael@0:   nsINode* tempNode = mCurNode;
michael@0: 
michael@0:   mCurNode = aCurNode;
michael@0:   // take an early out if this doesn't actually change the position
michael@0:   if (mCurNode == tempNode) {
michael@0:     mIsDone = false;  // paranoia
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   // Check to see if the node falls within the traversal range.
michael@0: 
michael@0:   nsINode* firstNode = mFirst;
michael@0:   nsINode* lastNode = mLast;
michael@0:   int32_t firstOffset = 0, lastOffset = 0;
michael@0: 
michael@0:   if (firstNode && lastNode) {
michael@0:     if (mPre) {
michael@0:       firstNode = NodeToParentOffset(mFirst, &firstOffset);
michael@0: 
michael@0:       if (lastNode->GetChildCount()) {
michael@0:         lastOffset = 0;
michael@0:       } else {
michael@0:         lastNode = NodeToParentOffset(mLast, &lastOffset);
michael@0:         ++lastOffset;
michael@0:       }
michael@0:     } else {
michael@0:       uint32_t numChildren = firstNode->GetChildCount();
michael@0: 
michael@0:       if (numChildren) {
michael@0:         firstOffset = numChildren;
michael@0:       } else {
michael@0:         firstNode = NodeToParentOffset(mFirst, &firstOffset);
michael@0:       }
michael@0: 
michael@0:       lastNode = NodeToParentOffset(mLast, &lastOffset);
michael@0:       ++lastOffset;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // The end positions are always in the range even if it has no parent.  We
michael@0:   // need to allow that or 'iter->Init(root)' would assert in Last() or First()
michael@0:   // for example, bug 327694.
michael@0:   if (mFirst != mCurNode && mLast != mCurNode &&
michael@0:       (!firstNode || !lastNode ||
michael@0:        !NodeIsInTraversalRange(mCurNode, mPre, firstNode, firstOffset,
michael@0:                                lastNode, lastOffset))) {
michael@0:     mIsDone = true;
michael@0:     return NS_ERROR_FAILURE;
michael@0:   }
michael@0: 
michael@0:   // We can be at ANY node in the sequence.  Need to regenerate the array of
michael@0:   // indexes back to the root or common parent!
michael@0:   nsAutoTArray<nsINode*, 8>     oldParentStack;
michael@0:   nsAutoTArray<int32_t, 8>      newIndexes;
michael@0: 
michael@0:   // Get a list of the parents up to the root, then compare the new node with
michael@0:   // entries in that array until we find a match (lowest common ancestor).  If
michael@0:   // no match, use IndexOf, take the parent, and repeat.  This avoids using
michael@0:   // IndexOf() N times on possibly large arrays.  We still end up doing it a
michael@0:   // fair bit.  It's better to use Clone() if possible.
michael@0: 
michael@0:   // we know the depth we're down (though we may not have started at the top).
michael@0:   oldParentStack.SetCapacity(mIndexes.Length() + 1);
michael@0: 
michael@0:   // We want to loop mIndexes.Length() + 1 times here, because we want to make
michael@0:   // sure we include mCommonParent in the oldParentStack, for use in the next
michael@0:   // for loop, and mIndexes only has entries for nodes from tempNode up through
michael@0:   // an ancestor of tempNode that's a child of mCommonParent.
michael@0:   for (int32_t i = mIndexes.Length() + 1; i > 0 && tempNode; i--) {
michael@0:     // Insert at head since we're walking up
michael@0:     oldParentStack.InsertElementAt(0, tempNode);
michael@0: 
michael@0:     nsINode* parent = tempNode->GetParentNode();
michael@0: 
michael@0:     if (!parent) {
michael@0:       // this node has no parent, and thus no index
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     if (parent == mCurNode) {
michael@0:       // The position was moved to a parent of the current position.  All we
michael@0:       // need to do is drop some indexes.  Shortcut here.
michael@0:       mIndexes.RemoveElementsAt(mIndexes.Length() - oldParentStack.Length(),
michael@0:                                 oldParentStack.Length());
michael@0:       mIsDone = false;
michael@0:       return NS_OK;
michael@0:     }
michael@0:     tempNode = parent;
michael@0:   }
michael@0: 
michael@0:   // Ok.  We have the array of old parents.  Look for a match.
michael@0:   while (newCurNode) {
michael@0:     nsINode* parent = newCurNode->GetParentNode();
michael@0: 
michael@0:     if (!parent) {
michael@0:       // this node has no parent, and thus no index
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     int32_t indx = parent->IndexOf(newCurNode);
michael@0: 
michael@0:     // insert at the head!
michael@0:     newIndexes.InsertElementAt(0, indx);
michael@0: 
michael@0:     // look to see if the parent is in the stack
michael@0:     indx = oldParentStack.IndexOf(parent);
michael@0:     if (indx >= 0) {
michael@0:       // ok, the parent IS on the old stack!  Rework things.  We want
michael@0:       // newIndexes to replace all nodes equal to or below the match.  Note
michael@0:       // that index oldParentStack.Length() - 1 is the last node, which is one
michael@0:       // BELOW the last index in the mIndexes stack.  In other words, we want
michael@0:       // to remove elements starting at index (indx + 1).
michael@0:       int32_t numToDrop = oldParentStack.Length() - (1 + indx);
michael@0:       if (numToDrop > 0) {
michael@0:         mIndexes.RemoveElementsAt(mIndexes.Length() - numToDrop, numToDrop);
michael@0:       }
michael@0:       mIndexes.AppendElements(newIndexes);
michael@0: 
michael@0:       break;
michael@0:     }
michael@0:     newCurNode = parent;
michael@0:   }
michael@0: 
michael@0:   // phew!
michael@0: 
michael@0:   mIsDone = false;
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsINode*
michael@0: nsContentIterator::GetCurrentNode()
michael@0: {
michael@0:   if (mIsDone) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
michael@0: 
michael@0:   return mCurNode;
michael@0: }
michael@0: 
michael@0: 
michael@0: 
michael@0: 
michael@0: 
michael@0: /*====================================================================================*/
michael@0: /*====================================================================================*/
michael@0: 
michael@0: 
michael@0: 
michael@0: 
michael@0: 
michael@0: 
michael@0: /******************************************************
michael@0:  * nsContentSubtreeIterator
michael@0:  ******************************************************/
michael@0: 
michael@0: 
michael@0: /*
michael@0:  *  A simple iterator class for traversing the content in "top subtree" order
michael@0:  */
michael@0: class nsContentSubtreeIterator : public nsContentIterator
michael@0: {
michael@0: public:
michael@0:   nsContentSubtreeIterator() : nsContentIterator(false) {}
michael@0:   virtual ~nsContentSubtreeIterator() {}
michael@0: 
michael@0:   NS_DECL_ISUPPORTS_INHERITED
michael@0:   NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsContentSubtreeIterator, nsContentIterator)
michael@0: 
michael@0:   // nsContentIterator overrides ------------------------------
michael@0: 
michael@0:   virtual nsresult Init(nsINode* aRoot);
michael@0: 
michael@0:   virtual nsresult Init(nsIDOMRange* aRange);
michael@0: 
michael@0:   virtual void Next();
michael@0: 
michael@0:   virtual void Prev();
michael@0: 
michael@0:   virtual nsresult PositionAt(nsINode* aCurNode);
michael@0: 
michael@0:   // Must override these because we don't do PositionAt
michael@0:   virtual void First();
michael@0: 
michael@0:   // Must override these because we don't do PositionAt
michael@0:   virtual void Last();
michael@0: 
michael@0: protected:
michael@0: 
michael@0:   // Returns the highest inclusive ancestor of aNode that's in the range
michael@0:   // (possibly aNode itself).  Returns null if aNode is null, or is not itself
michael@0:   // in the range.  A node is in the range if (node, 0) comes strictly after
michael@0:   // the range endpoint, and (node, node.length) comes strictly before it, so
michael@0:   // the range's start and end nodes will never be considered "in" it.
michael@0:   nsIContent* GetTopAncestorInRange(nsINode* aNode);
michael@0: 
michael@0:   // no copy's or assigns  FIX ME
michael@0:   nsContentSubtreeIterator(const nsContentSubtreeIterator&);
michael@0:   nsContentSubtreeIterator& operator=(const nsContentSubtreeIterator&);
michael@0: 
michael@0:   virtual void LastRelease() MOZ_OVERRIDE;
michael@0: 
michael@0:   nsRefPtr<nsRange> mRange;
michael@0: 
michael@0:   // these arrays all typically are used and have elements
michael@0:   nsAutoTArray<nsIContent*, 8> mEndNodes;
michael@0:   nsAutoTArray<int32_t, 8>     mEndOffsets;
michael@0: };
michael@0: 
michael@0: NS_IMPL_ADDREF_INHERITED(nsContentSubtreeIterator, nsContentIterator)
michael@0: NS_IMPL_RELEASE_INHERITED(nsContentSubtreeIterator, nsContentIterator)
michael@0: 
michael@0: NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator)
michael@0: NS_INTERFACE_MAP_END_INHERITING(nsContentIterator)
michael@0: 
michael@0: NS_IMPL_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator, nsContentIterator,
michael@0:                                    mRange)
michael@0: 
michael@0: void
michael@0: nsContentSubtreeIterator::LastRelease()
michael@0: {
michael@0:   mRange = nullptr;
michael@0:   nsContentIterator::LastRelease();
michael@0: }
michael@0: 
michael@0: /******************************************************
michael@0:  * repository cruft
michael@0:  ******************************************************/
michael@0: 
michael@0: already_AddRefed<nsIContentIterator>
michael@0: NS_NewContentSubtreeIterator()
michael@0: {
michael@0:   nsCOMPtr<nsIContentIterator> iter = new nsContentSubtreeIterator();
michael@0:   return iter.forget();
michael@0: }
michael@0: 
michael@0: 
michael@0: 
michael@0: /******************************************************
michael@0:  * Init routines
michael@0:  ******************************************************/
michael@0: 
michael@0: 
michael@0: nsresult
michael@0: nsContentSubtreeIterator::Init(nsINode* aRoot)
michael@0: {
michael@0:   return NS_ERROR_NOT_IMPLEMENTED;
michael@0: }
michael@0: 
michael@0: 
michael@0: nsresult
michael@0: nsContentSubtreeIterator::Init(nsIDOMRange* aRange)
michael@0: {
michael@0:   MOZ_ASSERT(aRange);
michael@0: 
michael@0:   mIsDone = false;
michael@0: 
michael@0:   mRange = static_cast<nsRange*>(aRange);
michael@0: 
michael@0:   // get the start node and offset, convert to nsINode
michael@0:   mCommonParent = mRange->GetCommonAncestor();
michael@0:   nsINode* startParent = mRange->GetStartParent();
michael@0:   int32_t startOffset = mRange->StartOffset();
michael@0:   nsINode* endParent = mRange->GetEndParent();
michael@0:   int32_t endOffset = mRange->EndOffset();
michael@0:   MOZ_ASSERT(mCommonParent && startParent && endParent);
michael@0:   // Bug 767169
michael@0:   MOZ_ASSERT(uint32_t(startOffset) <= startParent->Length() &&
michael@0:              uint32_t(endOffset) <= endParent->Length());
michael@0: 
michael@0:   // short circuit when start node == end node
michael@0:   if (startParent == endParent) {
michael@0:     nsINode* child = startParent->GetFirstChild();
michael@0: 
michael@0:     if (!child || startOffset == endOffset) {
michael@0:       // Text node, empty container, or collapsed
michael@0:       MakeEmpty();
michael@0:       return NS_OK;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // cache ancestors
michael@0:   nsContentUtils::GetAncestorsAndOffsets(endParent->AsDOMNode(), endOffset,
michael@0:                                          &mEndNodes, &mEndOffsets);
michael@0: 
michael@0:   nsIContent* firstCandidate = nullptr;
michael@0:   nsIContent* lastCandidate = nullptr;
michael@0: 
michael@0:   // find first node in range
michael@0:   int32_t offset = mRange->StartOffset();
michael@0: 
michael@0:   nsINode* node;
michael@0:   if (!startParent->GetChildCount()) {
michael@0:     // no children, start at the node itself
michael@0:     node = startParent;
michael@0:   } else {
michael@0:     nsIContent* child = startParent->GetChildAt(offset);
michael@0:     if (!child) {
michael@0:       // offset after last child
michael@0:       node = startParent;
michael@0:     } else {
michael@0:       firstCandidate = child;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (!firstCandidate) {
michael@0:     // then firstCandidate is next node after node
michael@0:     firstCandidate = GetNextSibling(node);
michael@0: 
michael@0:     if (!firstCandidate) {
michael@0:       MakeEmpty();
michael@0:       return NS_OK;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   firstCandidate = GetDeepFirstChild(firstCandidate);
michael@0: 
michael@0:   // confirm that this first possible contained node is indeed contained.  Else
michael@0:   // we have a range that does not fully contain any node.
michael@0: 
michael@0:   bool nodeBefore, nodeAfter;
michael@0:   MOZ_ALWAYS_TRUE(NS_SUCCEEDED(
michael@0:     nsRange::CompareNodeToRange(firstCandidate, mRange, &nodeBefore, &nodeAfter)));
michael@0: 
michael@0:   if (nodeBefore || nodeAfter) {
michael@0:     MakeEmpty();
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   // cool, we have the first node in the range.  Now we walk up its ancestors
michael@0:   // to find the most senior that is still in the range.  That's the real first
michael@0:   // node.
michael@0:   mFirst = GetTopAncestorInRange(firstCandidate);
michael@0: 
michael@0:   // now to find the last node
michael@0:   offset = mRange->EndOffset();
michael@0:   int32_t numChildren = endParent->GetChildCount();
michael@0: 
michael@0:   if (offset > numChildren) {
michael@0:     // Can happen for text nodes
michael@0:     offset = numChildren;
michael@0:   }
michael@0:   if (!offset || !numChildren) {
michael@0:     node = endParent;
michael@0:   } else {
michael@0:     lastCandidate = endParent->GetChildAt(--offset);
michael@0:     NS_ASSERTION(lastCandidate,
michael@0:                  "tree traversal trouble in nsContentSubtreeIterator::Init");
michael@0:   }
michael@0: 
michael@0:   if (!lastCandidate) {
michael@0:     // then lastCandidate is prev node before node
michael@0:     lastCandidate = GetPrevSibling(node);
michael@0:   }
michael@0: 
michael@0:   if (!lastCandidate) {
michael@0:     MakeEmpty();
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   lastCandidate = GetDeepLastChild(lastCandidate);
michael@0: 
michael@0:   // confirm that this last possible contained node is indeed contained.  Else
michael@0:   // we have a range that does not fully contain any node.
michael@0: 
michael@0:   MOZ_ALWAYS_TRUE(NS_SUCCEEDED(
michael@0:     nsRange::CompareNodeToRange(lastCandidate, mRange, &nodeBefore, &nodeAfter)));
michael@0: 
michael@0:   if (nodeBefore || nodeAfter) {
michael@0:     MakeEmpty();
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   // cool, we have the last node in the range.  Now we walk up its ancestors to
michael@0:   // find the most senior that is still in the range.  That's the real first
michael@0:   // node.
michael@0:   mLast = GetTopAncestorInRange(lastCandidate);
michael@0: 
michael@0:   mCurNode = mFirst;
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: /****************************************************************
michael@0:  * nsContentSubtreeIterator overrides of ContentIterator routines
michael@0:  ****************************************************************/
michael@0: 
michael@0: // we can't call PositionAt in a subtree iterator...
michael@0: void
michael@0: nsContentSubtreeIterator::First()
michael@0: {
michael@0:   mIsDone = mFirst == nullptr;
michael@0: 
michael@0:   mCurNode = mFirst;
michael@0: }
michael@0: 
michael@0: // we can't call PositionAt in a subtree iterator...
michael@0: void
michael@0: nsContentSubtreeIterator::Last()
michael@0: {
michael@0:   mIsDone = mLast == nullptr;
michael@0: 
michael@0:   mCurNode = mLast;
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: nsContentSubtreeIterator::Next()
michael@0: {
michael@0:   if (mIsDone || !mCurNode) {
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   if (mCurNode == mLast) {
michael@0:     mIsDone = true;
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   nsINode* nextNode = GetNextSibling(mCurNode);
michael@0:   NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
michael@0: 
michael@0:   int32_t i = mEndNodes.IndexOf(nextNode);
michael@0:   while (i != -1) {
michael@0:     // as long as we are finding ancestors of the endpoint of the range,
michael@0:     // dive down into their children
michael@0:     nextNode = nextNode->GetFirstChild();
michael@0:     NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
michael@0: 
michael@0:     // should be impossible to get a null pointer.  If we went all the way
michael@0:     // down the child chain to the bottom without finding an interior node,
michael@0:     // then the previous node should have been the last, which was
michael@0:     // was tested at top of routine.
michael@0:     i = mEndNodes.IndexOf(nextNode);
michael@0:   }
michael@0: 
michael@0:   mCurNode = nextNode;
michael@0: 
michael@0:   // This shouldn't be needed, but since our selection code can put us
michael@0:   // in a situation where mLast is in generated content, we need this
michael@0:   // to stop the iterator when we've walked past past the last node!
michael@0:   mIsDone = mCurNode == nullptr;
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: nsContentSubtreeIterator::Prev()
michael@0: {
michael@0:   // Prev should be optimized to use the mStartNodes, just as Next
michael@0:   // uses mEndNodes.
michael@0:   if (mIsDone || !mCurNode) {
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   if (mCurNode == mFirst) {
michael@0:     mIsDone = true;
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   // If any of these function calls return null, so will all succeeding ones,
michael@0:   // so mCurNode will wind up set to null.
michael@0:   nsINode* prevNode = GetDeepFirstChild(mCurNode);
michael@0: 
michael@0:   prevNode = PrevNode(prevNode);
michael@0: 
michael@0:   prevNode = GetDeepLastChild(prevNode);
michael@0: 
michael@0:   mCurNode = GetTopAncestorInRange(prevNode);
michael@0: 
michael@0:   // This shouldn't be needed, but since our selection code can put us
michael@0:   // in a situation where mFirst is in generated content, we need this
michael@0:   // to stop the iterator when we've walked past past the first node!
michael@0:   mIsDone = mCurNode == nullptr;
michael@0: }
michael@0: 
michael@0: 
michael@0: nsresult
michael@0: nsContentSubtreeIterator::PositionAt(nsINode* aCurNode)
michael@0: {
michael@0:   NS_ERROR("Not implemented!");
michael@0: 
michael@0:   return NS_ERROR_NOT_IMPLEMENTED;
michael@0: }
michael@0: 
michael@0: /****************************************************************
michael@0:  * nsContentSubtreeIterator helper routines
michael@0:  ****************************************************************/
michael@0: 
michael@0: nsIContent*
michael@0: nsContentSubtreeIterator::GetTopAncestorInRange(nsINode* aNode)
michael@0: {
michael@0:   if (!aNode || !aNode->GetParentNode()) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   // aNode has a parent, so it must be content.
michael@0:   nsIContent* content = aNode->AsContent();
michael@0: 
michael@0:   // sanity check: aNode is itself in the range
michael@0:   bool nodeBefore, nodeAfter;
michael@0:   nsresult res = nsRange::CompareNodeToRange(aNode, mRange,
michael@0:                                              &nodeBefore, &nodeAfter);
michael@0:   NS_ASSERTION(NS_SUCCEEDED(res) && !nodeBefore && !nodeAfter,
michael@0:                "aNode isn't in mRange, or something else weird happened");
michael@0:   if (NS_FAILED(res) || nodeBefore || nodeAfter) {
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   while (content) {
michael@0:     nsIContent* parent = content->GetParent();
michael@0:     // content always has a parent.  If its parent is the root, however --
michael@0:     // i.e., either it's not content, or it is content but its own parent is
michael@0:     // null -- then we're finished, since we don't go up to the root.
michael@0:     //
michael@0:     // We have to special-case this because CompareNodeToRange treats the root
michael@0:     // node differently -- see bug 765205.
michael@0:     if (!parent || !parent->GetParentNode()) {
michael@0:       return content;
michael@0:     }
michael@0:     MOZ_ALWAYS_TRUE(NS_SUCCEEDED(
michael@0:       nsRange::CompareNodeToRange(parent, mRange, &nodeBefore, &nodeAfter)));
michael@0: 
michael@0:     if (nodeBefore || nodeAfter) {
michael@0:       return content;
michael@0:     }
michael@0:     content = parent;
michael@0:   }
michael@0: 
michael@0:   MOZ_CRASH("This should only be possible if aNode was null");
michael@0: }