1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/base/src/nsContentIterator.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1474 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "nsISupports.h"
1.10 +#include "nsIDOMNodeList.h"
1.11 +#include "nsIContentIterator.h"
1.12 +#include "nsRange.h"
1.13 +#include "nsIContent.h"
1.14 +#include "nsCOMPtr.h"
1.15 +#include "nsTArray.h"
1.16 +#include "nsContentUtils.h"
1.17 +#include "nsINode.h"
1.18 +#include "nsCycleCollectionParticipant.h"
1.19 +
1.20 +// couple of utility static functs
1.21 +
1.22 +///////////////////////////////////////////////////////////////////////////
1.23 +// NodeToParentOffset: returns the node's parent and offset.
1.24 +//
1.25 +
1.26 +static nsINode*
1.27 +NodeToParentOffset(nsINode* aNode, int32_t* aOffset)
1.28 +{
1.29 + *aOffset = 0;
1.30 +
1.31 + nsINode* parent = aNode->GetParentNode();
1.32 +
1.33 + if (parent) {
1.34 + *aOffset = parent->IndexOf(aNode);
1.35 + }
1.36 +
1.37 + return parent;
1.38 +}
1.39 +
1.40 +///////////////////////////////////////////////////////////////////////////
1.41 +// NodeIsInTraversalRange: returns true if content is visited during
1.42 +// the traversal of the range in the specified mode.
1.43 +//
1.44 +static bool
1.45 +NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode,
1.46 + nsINode* aStartNode, int32_t aStartOffset,
1.47 + nsINode* aEndNode, int32_t aEndOffset)
1.48 +{
1.49 + if (!aStartNode || !aEndNode || !aNode) {
1.50 + return false;
1.51 + }
1.52 +
1.53 + // If a chardata node contains an end point of the traversal range, it is
1.54 + // always in the traversal range.
1.55 + if (aNode->IsNodeOfType(nsINode::eDATA_NODE) &&
1.56 + (aNode == aStartNode || aNode == aEndNode)) {
1.57 + return true;
1.58 + }
1.59 +
1.60 + nsINode* parent = aNode->GetParentNode();
1.61 + if (!parent) {
1.62 + return false;
1.63 + }
1.64 +
1.65 + int32_t indx = parent->IndexOf(aNode);
1.66 +
1.67 + if (!aIsPreMode) {
1.68 + ++indx;
1.69 + }
1.70 +
1.71 + return nsContentUtils::ComparePoints(aStartNode, aStartOffset,
1.72 + parent, indx) <= 0 &&
1.73 + nsContentUtils::ComparePoints(aEndNode, aEndOffset,
1.74 + parent, indx) >= 0;
1.75 +}
1.76 +
1.77 +
1.78 +
1.79 +/*
1.80 + * A simple iterator class for traversing the content in "close tag" order
1.81 + */
1.82 +class nsContentIterator : public nsIContentIterator
1.83 +{
1.84 +public:
1.85 + NS_DECL_CYCLE_COLLECTING_ISUPPORTS
1.86 + NS_DECL_CYCLE_COLLECTION_CLASS(nsContentIterator)
1.87 +
1.88 + explicit nsContentIterator(bool aPre);
1.89 + virtual ~nsContentIterator();
1.90 +
1.91 + // nsIContentIterator interface methods ------------------------------
1.92 +
1.93 + virtual nsresult Init(nsINode* aRoot);
1.94 +
1.95 + virtual nsresult Init(nsIDOMRange* aRange);
1.96 +
1.97 + virtual void First();
1.98 +
1.99 + virtual void Last();
1.100 +
1.101 + virtual void Next();
1.102 +
1.103 + virtual void Prev();
1.104 +
1.105 + virtual nsINode* GetCurrentNode();
1.106 +
1.107 + virtual bool IsDone();
1.108 +
1.109 + virtual nsresult PositionAt(nsINode* aCurNode);
1.110 +
1.111 +protected:
1.112 +
1.113 + // Recursively get the deepest first/last child of aRoot. This will return
1.114 + // aRoot itself if it has no children.
1.115 + nsINode* GetDeepFirstChild(nsINode* aRoot,
1.116 + nsTArray<int32_t>* aIndexes = nullptr);
1.117 + nsIContent* GetDeepFirstChild(nsIContent* aRoot,
1.118 + nsTArray<int32_t>* aIndexes = nullptr);
1.119 + nsINode* GetDeepLastChild(nsINode* aRoot,
1.120 + nsTArray<int32_t>* aIndexes = nullptr);
1.121 + nsIContent* GetDeepLastChild(nsIContent* aRoot,
1.122 + nsTArray<int32_t>* aIndexes = nullptr);
1.123 +
1.124 + // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
1.125 + // etc. Returns null if aNode and all its ancestors have no next/previous
1.126 + // sibling.
1.127 + nsIContent* GetNextSibling(nsINode* aNode,
1.128 + nsTArray<int32_t>* aIndexes = nullptr);
1.129 + nsIContent* GetPrevSibling(nsINode* aNode,
1.130 + nsTArray<int32_t>* aIndexes = nullptr);
1.131 +
1.132 + nsINode* NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
1.133 + nsINode* PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
1.134 +
1.135 + // WARNING: This function is expensive
1.136 + nsresult RebuildIndexStack();
1.137 +
1.138 + void MakeEmpty();
1.139 +
1.140 + virtual void LastRelease();
1.141 +
1.142 + nsCOMPtr<nsINode> mCurNode;
1.143 + nsCOMPtr<nsINode> mFirst;
1.144 + nsCOMPtr<nsINode> mLast;
1.145 + nsCOMPtr<nsINode> mCommonParent;
1.146 +
1.147 + // used by nsContentIterator to cache indices
1.148 + nsAutoTArray<int32_t, 8> mIndexes;
1.149 +
1.150 + // used by nsSubtreeIterator to cache indices. Why put them in the base
1.151 + // class? Because otherwise I have to duplicate the routines GetNextSibling
1.152 + // etc across both classes, with slight variations for caching. Or
1.153 + // alternately, create a base class for the cache itself and have all the
1.154 + // cache manipulation go through a vptr. I think this is the best space and
1.155 + // speed combo, even though it's ugly.
1.156 + int32_t mCachedIndex;
1.157 + // another note about mCachedIndex: why should the subtree iterator use a
1.158 + // trivial cached index instead of the mre robust array of indicies (which is
1.159 + // what the basic content iterator uses)? The reason is that subtree
1.160 + // iterators do not do much transitioning between parents and children. They
1.161 + // tend to stay at the same level. In fact, you can prove (though I won't
1.162 + // attempt it here) that they change levels at most n+m times, where n is the
1.163 + // height of the parent hierarchy from the range start to the common
1.164 + // ancestor, and m is the the height of the parent hierarchy from the range
1.165 + // end to the common ancestor. If we used the index array, we would pay the
1.166 + // price up front for n, and then pay the cost for m on the fly later on.
1.167 + // With the simple cache, we only "pay as we go". Either way, we call
1.168 + // IndexOf() once for each change of level in the hierarchy. Since a trivial
1.169 + // index is much simpler, we use it for the subtree iterator.
1.170 +
1.171 + bool mIsDone;
1.172 + bool mPre;
1.173 +
1.174 +private:
1.175 +
1.176 + // no copies or assigns FIX ME
1.177 + nsContentIterator(const nsContentIterator&);
1.178 + nsContentIterator& operator=(const nsContentIterator&);
1.179 +
1.180 +};
1.181 +
1.182 +
1.183 +/******************************************************
1.184 + * repository cruft
1.185 + ******************************************************/
1.186 +
1.187 +already_AddRefed<nsIContentIterator>
1.188 +NS_NewContentIterator()
1.189 +{
1.190 + nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(false);
1.191 + return iter.forget();
1.192 +}
1.193 +
1.194 +
1.195 +already_AddRefed<nsIContentIterator>
1.196 +NS_NewPreContentIterator()
1.197 +{
1.198 + nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(true);
1.199 + return iter.forget();
1.200 +}
1.201 +
1.202 +
1.203 +/******************************************************
1.204 + * XPCOM cruft
1.205 + ******************************************************/
1.206 +
1.207 +NS_IMPL_CYCLE_COLLECTING_ADDREF(nsContentIterator)
1.208 +NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(nsContentIterator,
1.209 + LastRelease())
1.210 +
1.211 +NS_INTERFACE_MAP_BEGIN(nsContentIterator)
1.212 + NS_INTERFACE_MAP_ENTRY(nsIContentIterator)
1.213 + NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIContentIterator)
1.214 + NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION(nsContentIterator)
1.215 +NS_INTERFACE_MAP_END
1.216 +
1.217 +NS_IMPL_CYCLE_COLLECTION(nsContentIterator,
1.218 + mCurNode,
1.219 + mFirst,
1.220 + mLast,
1.221 + mCommonParent)
1.222 +
1.223 +void
1.224 +nsContentIterator::LastRelease()
1.225 +{
1.226 + mCurNode = nullptr;
1.227 + mFirst = nullptr;
1.228 + mLast = nullptr;
1.229 + mCommonParent = nullptr;
1.230 +}
1.231 +
1.232 +/******************************************************
1.233 + * constructor/destructor
1.234 + ******************************************************/
1.235 +
1.236 +nsContentIterator::nsContentIterator(bool aPre) :
1.237 + // don't need to explicitly initialize |nsCOMPtr|s, they will automatically
1.238 + // be nullptr
1.239 + mCachedIndex(0), mIsDone(false), mPre(aPre)
1.240 +{
1.241 +}
1.242 +
1.243 +
1.244 +nsContentIterator::~nsContentIterator()
1.245 +{
1.246 +}
1.247 +
1.248 +
1.249 +/******************************************************
1.250 + * Init routines
1.251 + ******************************************************/
1.252 +
1.253 +
1.254 +nsresult
1.255 +nsContentIterator::Init(nsINode* aRoot)
1.256 +{
1.257 + if (!aRoot) {
1.258 + return NS_ERROR_NULL_POINTER;
1.259 + }
1.260 +
1.261 + mIsDone = false;
1.262 + mIndexes.Clear();
1.263 +
1.264 + if (mPre) {
1.265 + mFirst = aRoot;
1.266 + mLast = GetDeepLastChild(aRoot);
1.267 + } else {
1.268 + mFirst = GetDeepFirstChild(aRoot);
1.269 + mLast = aRoot;
1.270 + }
1.271 +
1.272 + mCommonParent = aRoot;
1.273 + mCurNode = mFirst;
1.274 + RebuildIndexStack();
1.275 + return NS_OK;
1.276 +}
1.277 +
1.278 +nsresult
1.279 +nsContentIterator::Init(nsIDOMRange* aDOMRange)
1.280 +{
1.281 + NS_ENSURE_ARG_POINTER(aDOMRange);
1.282 + nsRange* range = static_cast<nsRange*>(aDOMRange);
1.283 +
1.284 + mIsDone = false;
1.285 +
1.286 + // get common content parent
1.287 + mCommonParent = range->GetCommonAncestor();
1.288 + NS_ENSURE_TRUE(mCommonParent, NS_ERROR_FAILURE);
1.289 +
1.290 + // get the start node and offset
1.291 + int32_t startIndx = range->StartOffset();
1.292 + nsINode* startNode = range->GetStartParent();
1.293 + NS_ENSURE_TRUE(startNode, NS_ERROR_FAILURE);
1.294 +
1.295 + // get the end node and offset
1.296 + int32_t endIndx = range->EndOffset();
1.297 + nsINode* endNode = range->GetEndParent();
1.298 + NS_ENSURE_TRUE(endNode, NS_ERROR_FAILURE);
1.299 +
1.300 + bool startIsData = startNode->IsNodeOfType(nsINode::eDATA_NODE);
1.301 +
1.302 + // short circuit when start node == end node
1.303 + if (startNode == endNode) {
1.304 + // Check to see if we have a collapsed range, if so, there is nothing to
1.305 + // iterate over.
1.306 + //
1.307 + // XXX: CharacterDataNodes (text nodes) are currently an exception, since
1.308 + // we always want to be able to iterate text nodes at the end points
1.309 + // of a range.
1.310 +
1.311 + if (!startIsData && startIndx == endIndx) {
1.312 + MakeEmpty();
1.313 + return NS_OK;
1.314 + }
1.315 +
1.316 + if (startIsData) {
1.317 + // It's a character data node.
1.318 + mFirst = startNode->AsContent();
1.319 + mLast = mFirst;
1.320 + mCurNode = mFirst;
1.321 +
1.322 + RebuildIndexStack();
1.323 + return NS_OK;
1.324 + }
1.325 + }
1.326 +
1.327 + // Find first node in range.
1.328 +
1.329 + nsIContent* cChild = nullptr;
1.330 +
1.331 + if (!startIsData && startNode->HasChildren()) {
1.332 + cChild = startNode->GetChildAt(startIndx);
1.333 + }
1.334 +
1.335 + if (!cChild) {
1.336 + // no children, must be a text node
1.337 + //
1.338 + // XXXbz no children might also just mean no children. So I'm not
1.339 + // sure what that comment above is talking about.
1.340 +
1.341 + if (mPre) {
1.342 + // XXX: In the future, if start offset is after the last
1.343 + // character in the cdata node, should we set mFirst to
1.344 + // the next sibling?
1.345 +
1.346 + if (!startIsData) {
1.347 + mFirst = GetNextSibling(startNode);
1.348 +
1.349 + // Does mFirst node really intersect the range? The range could be
1.350 + // 'degenerate', i.e., not collapsed but still contain no content.
1.351 +
1.352 + if (mFirst && !NodeIsInTraversalRange(mFirst, mPre, startNode,
1.353 + startIndx, endNode, endIndx)) {
1.354 + mFirst = nullptr;
1.355 + }
1.356 + } else {
1.357 + mFirst = startNode->AsContent();
1.358 + }
1.359 + } else {
1.360 + // post-order
1.361 + if (startNode->IsContent()) {
1.362 + mFirst = startNode->AsContent();
1.363 + } else {
1.364 + // What else can we do?
1.365 + mFirst = nullptr;
1.366 + }
1.367 + }
1.368 + } else {
1.369 + if (mPre) {
1.370 + mFirst = cChild;
1.371 + } else {
1.372 + // post-order
1.373 + mFirst = GetDeepFirstChild(cChild);
1.374 +
1.375 + // Does mFirst node really intersect the range? The range could be
1.376 + // 'degenerate', i.e., not collapsed but still contain no content.
1.377 +
1.378 + if (mFirst && !NodeIsInTraversalRange(mFirst, mPre, startNode, startIndx,
1.379 + endNode, endIndx)) {
1.380 + mFirst = nullptr;
1.381 + }
1.382 + }
1.383 + }
1.384 +
1.385 +
1.386 + // Find last node in range.
1.387 +
1.388 + bool endIsData = endNode->IsNodeOfType(nsINode::eDATA_NODE);
1.389 +
1.390 + if (endIsData || !endNode->HasChildren() || endIndx == 0) {
1.391 + if (mPre) {
1.392 + if (endNode->IsContent()) {
1.393 + mLast = endNode->AsContent();
1.394 + } else {
1.395 + // Not much else to do here...
1.396 + mLast = nullptr;
1.397 + }
1.398 + } else {
1.399 + // post-order
1.400 + //
1.401 + // XXX: In the future, if end offset is before the first character in the
1.402 + // cdata node, should we set mLast to the prev sibling?
1.403 +
1.404 + if (!endIsData) {
1.405 + mLast = GetPrevSibling(endNode);
1.406 +
1.407 + if (!NodeIsInTraversalRange(mLast, mPre, startNode, startIndx,
1.408 + endNode, endIndx)) {
1.409 + mLast = nullptr;
1.410 + }
1.411 + } else {
1.412 + mLast = endNode->AsContent();
1.413 + }
1.414 + }
1.415 + } else {
1.416 + int32_t indx = endIndx;
1.417 +
1.418 + cChild = endNode->GetChildAt(--indx);
1.419 +
1.420 + if (!cChild) {
1.421 + // No child at offset!
1.422 + NS_NOTREACHED("nsContentIterator::nsContentIterator");
1.423 + return NS_ERROR_FAILURE;
1.424 + }
1.425 +
1.426 + if (mPre) {
1.427 + mLast = GetDeepLastChild(cChild);
1.428 +
1.429 + if (!NodeIsInTraversalRange(mLast, mPre, startNode, startIndx,
1.430 + endNode, endIndx)) {
1.431 + mLast = nullptr;
1.432 + }
1.433 + } else {
1.434 + // post-order
1.435 + mLast = cChild;
1.436 + }
1.437 + }
1.438 +
1.439 + // If either first or last is null, they both have to be null!
1.440 +
1.441 + if (!mFirst || !mLast) {
1.442 + mFirst = nullptr;
1.443 + mLast = nullptr;
1.444 + }
1.445 +
1.446 + mCurNode = mFirst;
1.447 + mIsDone = !mCurNode;
1.448 +
1.449 + if (!mCurNode) {
1.450 + mIndexes.Clear();
1.451 + } else {
1.452 + RebuildIndexStack();
1.453 + }
1.454 +
1.455 + return NS_OK;
1.456 +}
1.457 +
1.458 +
1.459 +/******************************************************
1.460 + * Helper routines
1.461 + ******************************************************/
1.462 +// WARNING: This function is expensive
1.463 +nsresult
1.464 +nsContentIterator::RebuildIndexStack()
1.465 +{
1.466 + // Make sure we start at the right indexes on the stack! Build array up
1.467 + // to common parent of start and end. Perhaps it's too many entries, but
1.468 + // that's far better than too few.
1.469 + nsINode* parent;
1.470 + nsINode* current;
1.471 +
1.472 + mIndexes.Clear();
1.473 + current = mCurNode;
1.474 + if (!current) {
1.475 + return NS_OK;
1.476 + }
1.477 +
1.478 + while (current != mCommonParent) {
1.479 + parent = current->GetParentNode();
1.480 +
1.481 + if (!parent) {
1.482 + return NS_ERROR_FAILURE;
1.483 + }
1.484 +
1.485 + mIndexes.InsertElementAt(0, parent->IndexOf(current));
1.486 +
1.487 + current = parent;
1.488 + }
1.489 +
1.490 + return NS_OK;
1.491 +}
1.492 +
1.493 +void
1.494 +nsContentIterator::MakeEmpty()
1.495 +{
1.496 + mCurNode = nullptr;
1.497 + mFirst = nullptr;
1.498 + mLast = nullptr;
1.499 + mCommonParent = nullptr;
1.500 + mIsDone = true;
1.501 + mIndexes.Clear();
1.502 +}
1.503 +
1.504 +nsINode*
1.505 +nsContentIterator::GetDeepFirstChild(nsINode* aRoot,
1.506 + nsTArray<int32_t>* aIndexes)
1.507 +{
1.508 + if (!aRoot || !aRoot->HasChildren()) {
1.509 + return aRoot;
1.510 + }
1.511 + // We can't pass aRoot itself to the full GetDeepFirstChild, because that
1.512 + // will only take nsIContent and aRoot might be a document. Pass aRoot's
1.513 + // child, but be sure to preserve aIndexes.
1.514 + if (aIndexes) {
1.515 + aIndexes->AppendElement(0);
1.516 + }
1.517 + return GetDeepFirstChild(aRoot->GetFirstChild(), aIndexes);
1.518 +}
1.519 +
1.520 +nsIContent*
1.521 +nsContentIterator::GetDeepFirstChild(nsIContent* aRoot,
1.522 + nsTArray<int32_t>* aIndexes)
1.523 +{
1.524 + if (!aRoot) {
1.525 + return nullptr;
1.526 + }
1.527 +
1.528 + nsIContent* node = aRoot;
1.529 + nsIContent* child = node->GetFirstChild();
1.530 +
1.531 + while (child) {
1.532 + if (aIndexes) {
1.533 + // Add this node to the stack of indexes
1.534 + aIndexes->AppendElement(0);
1.535 + }
1.536 + node = child;
1.537 + child = node->GetFirstChild();
1.538 + }
1.539 +
1.540 + return node;
1.541 +}
1.542 +
1.543 +nsINode*
1.544 +nsContentIterator::GetDeepLastChild(nsINode* aRoot,
1.545 + nsTArray<int32_t>* aIndexes)
1.546 +{
1.547 + if (!aRoot || !aRoot->HasChildren()) {
1.548 + return aRoot;
1.549 + }
1.550 + // We can't pass aRoot itself to the full GetDeepLastChild, because that will
1.551 + // only take nsIContent and aRoot might be a document. Pass aRoot's child,
1.552 + // but be sure to preserve aIndexes.
1.553 + if (aIndexes) {
1.554 + aIndexes->AppendElement(aRoot->GetChildCount() - 1);
1.555 + }
1.556 + return GetDeepLastChild(aRoot->GetLastChild(), aIndexes);
1.557 +}
1.558 +
1.559 +nsIContent*
1.560 +nsContentIterator::GetDeepLastChild(nsIContent* aRoot,
1.561 + nsTArray<int32_t>* aIndexes)
1.562 +{
1.563 + if (!aRoot) {
1.564 + return nullptr;
1.565 + }
1.566 +
1.567 + nsIContent* node = aRoot;
1.568 + int32_t numChildren = node->GetChildCount();
1.569 +
1.570 + while (numChildren) {
1.571 + nsIContent* child = node->GetChildAt(--numChildren);
1.572 +
1.573 + if (aIndexes) {
1.574 + // Add this node to the stack of indexes
1.575 + aIndexes->AppendElement(numChildren);
1.576 + }
1.577 + numChildren = child->GetChildCount();
1.578 + node = child;
1.579 + }
1.580 +
1.581 + return node;
1.582 +}
1.583 +
1.584 +// Get the next sibling, or parent's next sibling, or grandpa's next sibling...
1.585 +nsIContent*
1.586 +nsContentIterator::GetNextSibling(nsINode* aNode,
1.587 + nsTArray<int32_t>* aIndexes)
1.588 +{
1.589 + if (!aNode) {
1.590 + return nullptr;
1.591 + }
1.592 +
1.593 + nsINode* parent = aNode->GetParentNode();
1.594 + if (!parent) {
1.595 + return nullptr;
1.596 + }
1.597 +
1.598 + int32_t indx = 0;
1.599 +
1.600 + NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
1.601 + "ContentIterator stack underflow");
1.602 + if (aIndexes && !aIndexes->IsEmpty()) {
1.603 + // use the last entry on the Indexes array for the current index
1.604 + indx = (*aIndexes)[aIndexes->Length()-1];
1.605 + } else {
1.606 + indx = mCachedIndex;
1.607 + }
1.608 +
1.609 + // reverify that the index of the current node hasn't changed.
1.610 + // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
1.611 + // ignore result this time - the index may now be out of range.
1.612 + nsIContent* sib = parent->GetChildAt(indx);
1.613 + if (sib != aNode) {
1.614 + // someone changed our index - find the new index the painful way
1.615 + indx = parent->IndexOf(aNode);
1.616 + }
1.617 +
1.618 + // indx is now canonically correct
1.619 + if ((sib = parent->GetChildAt(++indx))) {
1.620 + // update index cache
1.621 + if (aIndexes && !aIndexes->IsEmpty()) {
1.622 + aIndexes->ElementAt(aIndexes->Length()-1) = indx;
1.623 + } else {
1.624 + mCachedIndex = indx;
1.625 + }
1.626 + } else {
1.627 + if (parent != mCommonParent) {
1.628 + if (aIndexes) {
1.629 + // pop node off the stack, go up one level and return parent or fail.
1.630 + // Don't leave the index empty, especially if we're
1.631 + // returning nullptr. This confuses other parts of the code.
1.632 + if (aIndexes->Length() > 1) {
1.633 + aIndexes->RemoveElementAt(aIndexes->Length()-1);
1.634 + }
1.635 + }
1.636 + }
1.637 +
1.638 + // ok to leave cache out of date here if parent == mCommonParent?
1.639 + sib = GetNextSibling(parent, aIndexes);
1.640 + }
1.641 +
1.642 + return sib;
1.643 +}
1.644 +
1.645 +// Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
1.646 +nsIContent*
1.647 +nsContentIterator::GetPrevSibling(nsINode* aNode,
1.648 + nsTArray<int32_t>* aIndexes)
1.649 +{
1.650 + if (!aNode) {
1.651 + return nullptr;
1.652 + }
1.653 +
1.654 + nsINode* parent = aNode->GetParentNode();
1.655 + if (!parent) {
1.656 + return nullptr;
1.657 + }
1.658 +
1.659 + int32_t indx = 0;
1.660 +
1.661 + NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
1.662 + "ContentIterator stack underflow");
1.663 + if (aIndexes && !aIndexes->IsEmpty()) {
1.664 + // use the last entry on the Indexes array for the current index
1.665 + indx = (*aIndexes)[aIndexes->Length()-1];
1.666 + } else {
1.667 + indx = mCachedIndex;
1.668 + }
1.669 +
1.670 + // reverify that the index of the current node hasn't changed
1.671 + // ignore result this time - the index may now be out of range.
1.672 + nsIContent* sib = parent->GetChildAt(indx);
1.673 + if (sib != aNode) {
1.674 + // someone changed our index - find the new index the painful way
1.675 + indx = parent->IndexOf(aNode);
1.676 + }
1.677 +
1.678 + // indx is now canonically correct
1.679 + if (indx > 0 && (sib = parent->GetChildAt(--indx))) {
1.680 + // update index cache
1.681 + if (aIndexes && !aIndexes->IsEmpty()) {
1.682 + aIndexes->ElementAt(aIndexes->Length()-1) = indx;
1.683 + } else {
1.684 + mCachedIndex = indx;
1.685 + }
1.686 + } else if (parent != mCommonParent) {
1.687 + if (aIndexes && !aIndexes->IsEmpty()) {
1.688 + // pop node off the stack, go up one level and try again.
1.689 + aIndexes->RemoveElementAt(aIndexes->Length()-1);
1.690 + }
1.691 + return GetPrevSibling(parent, aIndexes);
1.692 + }
1.693 +
1.694 + return sib;
1.695 +}
1.696 +
1.697 +nsINode*
1.698 +nsContentIterator::NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
1.699 +{
1.700 + nsINode* node = aNode;
1.701 +
1.702 + // if we are a Pre-order iterator, use pre-order
1.703 + if (mPre) {
1.704 + // if it has children then next node is first child
1.705 + if (node->HasChildren()) {
1.706 + nsIContent* firstChild = node->GetFirstChild();
1.707 +
1.708 + // update cache
1.709 + if (aIndexes) {
1.710 + // push an entry on the index stack
1.711 + aIndexes->AppendElement(0);
1.712 + } else {
1.713 + mCachedIndex = 0;
1.714 + }
1.715 +
1.716 + return firstChild;
1.717 + }
1.718 +
1.719 + // else next sibling is next
1.720 + return GetNextSibling(node, aIndexes);
1.721 + }
1.722 +
1.723 + // post-order
1.724 + nsINode* parent = node->GetParentNode();
1.725 + nsIContent* sibling = nullptr;
1.726 + int32_t indx = 0;
1.727 +
1.728 + // get the cached index
1.729 + NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
1.730 + "ContentIterator stack underflow");
1.731 + if (aIndexes && !aIndexes->IsEmpty()) {
1.732 + // use the last entry on the Indexes array for the current index
1.733 + indx = (*aIndexes)[aIndexes->Length()-1];
1.734 + } else {
1.735 + indx = mCachedIndex;
1.736 + }
1.737 +
1.738 + // reverify that the index of the current node hasn't changed. not super
1.739 + // cheap, but a lot cheaper than IndexOf(), and still O(1). ignore result
1.740 + // this time - the index may now be out of range.
1.741 + if (indx >= 0) {
1.742 + sibling = parent->GetChildAt(indx);
1.743 + }
1.744 + if (sibling != node) {
1.745 + // someone changed our index - find the new index the painful way
1.746 + indx = parent->IndexOf(node);
1.747 + }
1.748 +
1.749 + // indx is now canonically correct
1.750 + sibling = parent->GetChildAt(++indx);
1.751 + if (sibling) {
1.752 + // update cache
1.753 + if (aIndexes && !aIndexes->IsEmpty()) {
1.754 + // replace an entry on the index stack
1.755 + aIndexes->ElementAt(aIndexes->Length()-1) = indx;
1.756 + } else {
1.757 + mCachedIndex = indx;
1.758 + }
1.759 +
1.760 + // next node is sibling's "deep left" child
1.761 + return GetDeepFirstChild(sibling, aIndexes);
1.762 + }
1.763 +
1.764 + // else it's the parent, update cache
1.765 + if (aIndexes) {
1.766 + // Pop an entry off the index stack. Don't leave the index empty,
1.767 + // especially if we're returning nullptr. This confuses other parts of the
1.768 + // code.
1.769 + if (aIndexes->Length() > 1) {
1.770 + aIndexes->RemoveElementAt(aIndexes->Length()-1);
1.771 + }
1.772 + } else {
1.773 + // this might be wrong, but we are better off guessing
1.774 + mCachedIndex = 0;
1.775 + }
1.776 +
1.777 + return parent;
1.778 +}
1.779 +
1.780 +nsINode*
1.781 +nsContentIterator::PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
1.782 +{
1.783 + nsINode* node = aNode;
1.784 +
1.785 + // if we are a Pre-order iterator, use pre-order
1.786 + if (mPre) {
1.787 + nsINode* parent = node->GetParentNode();
1.788 + nsIContent* sibling = nullptr;
1.789 + int32_t indx = 0;
1.790 +
1.791 + // get the cached index
1.792 + NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
1.793 + "ContentIterator stack underflow");
1.794 + if (aIndexes && !aIndexes->IsEmpty()) {
1.795 + // use the last entry on the Indexes array for the current index
1.796 + indx = (*aIndexes)[aIndexes->Length()-1];
1.797 + } else {
1.798 + indx = mCachedIndex;
1.799 + }
1.800 +
1.801 + // reverify that the index of the current node hasn't changed. not super
1.802 + // cheap, but a lot cheaper than IndexOf(), and still O(1). ignore result
1.803 + // this time - the index may now be out of range.
1.804 + if (indx >= 0) {
1.805 + sibling = parent->GetChildAt(indx);
1.806 + }
1.807 +
1.808 + if (sibling != node) {
1.809 + // someone changed our index - find the new index the painful way
1.810 + indx = parent->IndexOf(node);
1.811 + }
1.812 +
1.813 + // indx is now canonically correct
1.814 + if (indx && (sibling = parent->GetChildAt(--indx))) {
1.815 + // update cache
1.816 + if (aIndexes && !aIndexes->IsEmpty()) {
1.817 + // replace an entry on the index stack
1.818 + aIndexes->ElementAt(aIndexes->Length()-1) = indx;
1.819 + } else {
1.820 + mCachedIndex = indx;
1.821 + }
1.822 +
1.823 + // prev node is sibling's "deep right" child
1.824 + return GetDeepLastChild(sibling, aIndexes);
1.825 + }
1.826 +
1.827 + // else it's the parent, update cache
1.828 + if (aIndexes && !aIndexes->IsEmpty()) {
1.829 + // pop an entry off the index stack
1.830 + aIndexes->RemoveElementAt(aIndexes->Length()-1);
1.831 + } else {
1.832 + // this might be wrong, but we are better off guessing
1.833 + mCachedIndex = 0;
1.834 + }
1.835 + return parent;
1.836 + }
1.837 +
1.838 + // post-order
1.839 + int32_t numChildren = node->GetChildCount();
1.840 +
1.841 + // if it has children then prev node is last child
1.842 + if (numChildren) {
1.843 + nsIContent* lastChild = node->GetLastChild();
1.844 + numChildren--;
1.845 +
1.846 + // update cache
1.847 + if (aIndexes) {
1.848 + // push an entry on the index stack
1.849 + aIndexes->AppendElement(numChildren);
1.850 + } else {
1.851 + mCachedIndex = numChildren;
1.852 + }
1.853 +
1.854 + return lastChild;
1.855 + }
1.856 +
1.857 + // else prev sibling is previous
1.858 + return GetPrevSibling(node, aIndexes);
1.859 +}
1.860 +
1.861 +/******************************************************
1.862 + * ContentIterator routines
1.863 + ******************************************************/
1.864 +
1.865 +void
1.866 +nsContentIterator::First()
1.867 +{
1.868 + if (mFirst) {
1.869 +#ifdef DEBUG
1.870 + nsresult rv =
1.871 +#endif
1.872 + PositionAt(mFirst);
1.873 +
1.874 + NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
1.875 + }
1.876 +
1.877 + mIsDone = mFirst == nullptr;
1.878 +}
1.879 +
1.880 +
1.881 +void
1.882 +nsContentIterator::Last()
1.883 +{
1.884 + NS_ASSERTION(mLast, "No last node!");
1.885 +
1.886 + if (mLast) {
1.887 +#ifdef DEBUG
1.888 + nsresult rv =
1.889 +#endif
1.890 + PositionAt(mLast);
1.891 +
1.892 + NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
1.893 + }
1.894 +
1.895 + mIsDone = mLast == nullptr;
1.896 +}
1.897 +
1.898 +
1.899 +void
1.900 +nsContentIterator::Next()
1.901 +{
1.902 + if (mIsDone || !mCurNode) {
1.903 + return;
1.904 + }
1.905 +
1.906 + if (mCurNode == mLast) {
1.907 + mIsDone = true;
1.908 + return;
1.909 + }
1.910 +
1.911 + mCurNode = NextNode(mCurNode, &mIndexes);
1.912 +}
1.913 +
1.914 +
1.915 +void
1.916 +nsContentIterator::Prev()
1.917 +{
1.918 + if (mIsDone || !mCurNode) {
1.919 + return;
1.920 + }
1.921 +
1.922 + if (mCurNode == mFirst) {
1.923 + mIsDone = true;
1.924 + return;
1.925 + }
1.926 +
1.927 + mCurNode = PrevNode(mCurNode, &mIndexes);
1.928 +}
1.929 +
1.930 +
1.931 +bool
1.932 +nsContentIterator::IsDone()
1.933 +{
1.934 + return mIsDone;
1.935 +}
1.936 +
1.937 +
1.938 +// Keeping arrays of indexes for the stack of nodes makes PositionAt
1.939 +// interesting...
1.940 +nsresult
1.941 +nsContentIterator::PositionAt(nsINode* aCurNode)
1.942 +{
1.943 + if (!aCurNode) {
1.944 + return NS_ERROR_NULL_POINTER;
1.945 + }
1.946 +
1.947 + nsINode* newCurNode = aCurNode;
1.948 + nsINode* tempNode = mCurNode;
1.949 +
1.950 + mCurNode = aCurNode;
1.951 + // take an early out if this doesn't actually change the position
1.952 + if (mCurNode == tempNode) {
1.953 + mIsDone = false; // paranoia
1.954 + return NS_OK;
1.955 + }
1.956 +
1.957 + // Check to see if the node falls within the traversal range.
1.958 +
1.959 + nsINode* firstNode = mFirst;
1.960 + nsINode* lastNode = mLast;
1.961 + int32_t firstOffset = 0, lastOffset = 0;
1.962 +
1.963 + if (firstNode && lastNode) {
1.964 + if (mPre) {
1.965 + firstNode = NodeToParentOffset(mFirst, &firstOffset);
1.966 +
1.967 + if (lastNode->GetChildCount()) {
1.968 + lastOffset = 0;
1.969 + } else {
1.970 + lastNode = NodeToParentOffset(mLast, &lastOffset);
1.971 + ++lastOffset;
1.972 + }
1.973 + } else {
1.974 + uint32_t numChildren = firstNode->GetChildCount();
1.975 +
1.976 + if (numChildren) {
1.977 + firstOffset = numChildren;
1.978 + } else {
1.979 + firstNode = NodeToParentOffset(mFirst, &firstOffset);
1.980 + }
1.981 +
1.982 + lastNode = NodeToParentOffset(mLast, &lastOffset);
1.983 + ++lastOffset;
1.984 + }
1.985 + }
1.986 +
1.987 + // The end positions are always in the range even if it has no parent. We
1.988 + // need to allow that or 'iter->Init(root)' would assert in Last() or First()
1.989 + // for example, bug 327694.
1.990 + if (mFirst != mCurNode && mLast != mCurNode &&
1.991 + (!firstNode || !lastNode ||
1.992 + !NodeIsInTraversalRange(mCurNode, mPre, firstNode, firstOffset,
1.993 + lastNode, lastOffset))) {
1.994 + mIsDone = true;
1.995 + return NS_ERROR_FAILURE;
1.996 + }
1.997 +
1.998 + // We can be at ANY node in the sequence. Need to regenerate the array of
1.999 + // indexes back to the root or common parent!
1.1000 + nsAutoTArray<nsINode*, 8> oldParentStack;
1.1001 + nsAutoTArray<int32_t, 8> newIndexes;
1.1002 +
1.1003 + // Get a list of the parents up to the root, then compare the new node with
1.1004 + // entries in that array until we find a match (lowest common ancestor). If
1.1005 + // no match, use IndexOf, take the parent, and repeat. This avoids using
1.1006 + // IndexOf() N times on possibly large arrays. We still end up doing it a
1.1007 + // fair bit. It's better to use Clone() if possible.
1.1008 +
1.1009 + // we know the depth we're down (though we may not have started at the top).
1.1010 + oldParentStack.SetCapacity(mIndexes.Length() + 1);
1.1011 +
1.1012 + // We want to loop mIndexes.Length() + 1 times here, because we want to make
1.1013 + // sure we include mCommonParent in the oldParentStack, for use in the next
1.1014 + // for loop, and mIndexes only has entries for nodes from tempNode up through
1.1015 + // an ancestor of tempNode that's a child of mCommonParent.
1.1016 + for (int32_t i = mIndexes.Length() + 1; i > 0 && tempNode; i--) {
1.1017 + // Insert at head since we're walking up
1.1018 + oldParentStack.InsertElementAt(0, tempNode);
1.1019 +
1.1020 + nsINode* parent = tempNode->GetParentNode();
1.1021 +
1.1022 + if (!parent) {
1.1023 + // this node has no parent, and thus no index
1.1024 + break;
1.1025 + }
1.1026 +
1.1027 + if (parent == mCurNode) {
1.1028 + // The position was moved to a parent of the current position. All we
1.1029 + // need to do is drop some indexes. Shortcut here.
1.1030 + mIndexes.RemoveElementsAt(mIndexes.Length() - oldParentStack.Length(),
1.1031 + oldParentStack.Length());
1.1032 + mIsDone = false;
1.1033 + return NS_OK;
1.1034 + }
1.1035 + tempNode = parent;
1.1036 + }
1.1037 +
1.1038 + // Ok. We have the array of old parents. Look for a match.
1.1039 + while (newCurNode) {
1.1040 + nsINode* parent = newCurNode->GetParentNode();
1.1041 +
1.1042 + if (!parent) {
1.1043 + // this node has no parent, and thus no index
1.1044 + break;
1.1045 + }
1.1046 +
1.1047 + int32_t indx = parent->IndexOf(newCurNode);
1.1048 +
1.1049 + // insert at the head!
1.1050 + newIndexes.InsertElementAt(0, indx);
1.1051 +
1.1052 + // look to see if the parent is in the stack
1.1053 + indx = oldParentStack.IndexOf(parent);
1.1054 + if (indx >= 0) {
1.1055 + // ok, the parent IS on the old stack! Rework things. We want
1.1056 + // newIndexes to replace all nodes equal to or below the match. Note
1.1057 + // that index oldParentStack.Length() - 1 is the last node, which is one
1.1058 + // BELOW the last index in the mIndexes stack. In other words, we want
1.1059 + // to remove elements starting at index (indx + 1).
1.1060 + int32_t numToDrop = oldParentStack.Length() - (1 + indx);
1.1061 + if (numToDrop > 0) {
1.1062 + mIndexes.RemoveElementsAt(mIndexes.Length() - numToDrop, numToDrop);
1.1063 + }
1.1064 + mIndexes.AppendElements(newIndexes);
1.1065 +
1.1066 + break;
1.1067 + }
1.1068 + newCurNode = parent;
1.1069 + }
1.1070 +
1.1071 + // phew!
1.1072 +
1.1073 + mIsDone = false;
1.1074 + return NS_OK;
1.1075 +}
1.1076 +
1.1077 +nsINode*
1.1078 +nsContentIterator::GetCurrentNode()
1.1079 +{
1.1080 + if (mIsDone) {
1.1081 + return nullptr;
1.1082 + }
1.1083 +
1.1084 + NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
1.1085 +
1.1086 + return mCurNode;
1.1087 +}
1.1088 +
1.1089 +
1.1090 +
1.1091 +
1.1092 +
1.1093 +/*====================================================================================*/
1.1094 +/*====================================================================================*/
1.1095 +
1.1096 +
1.1097 +
1.1098 +
1.1099 +
1.1100 +
1.1101 +/******************************************************
1.1102 + * nsContentSubtreeIterator
1.1103 + ******************************************************/
1.1104 +
1.1105 +
1.1106 +/*
1.1107 + * A simple iterator class for traversing the content in "top subtree" order
1.1108 + */
1.1109 +class nsContentSubtreeIterator : public nsContentIterator
1.1110 +{
1.1111 +public:
1.1112 + nsContentSubtreeIterator() : nsContentIterator(false) {}
1.1113 + virtual ~nsContentSubtreeIterator() {}
1.1114 +
1.1115 + NS_DECL_ISUPPORTS_INHERITED
1.1116 + NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1.1117 +
1.1118 + // nsContentIterator overrides ------------------------------
1.1119 +
1.1120 + virtual nsresult Init(nsINode* aRoot);
1.1121 +
1.1122 + virtual nsresult Init(nsIDOMRange* aRange);
1.1123 +
1.1124 + virtual void Next();
1.1125 +
1.1126 + virtual void Prev();
1.1127 +
1.1128 + virtual nsresult PositionAt(nsINode* aCurNode);
1.1129 +
1.1130 + // Must override these because we don't do PositionAt
1.1131 + virtual void First();
1.1132 +
1.1133 + // Must override these because we don't do PositionAt
1.1134 + virtual void Last();
1.1135 +
1.1136 +protected:
1.1137 +
1.1138 + // Returns the highest inclusive ancestor of aNode that's in the range
1.1139 + // (possibly aNode itself). Returns null if aNode is null, or is not itself
1.1140 + // in the range. A node is in the range if (node, 0) comes strictly after
1.1141 + // the range endpoint, and (node, node.length) comes strictly before it, so
1.1142 + // the range's start and end nodes will never be considered "in" it.
1.1143 + nsIContent* GetTopAncestorInRange(nsINode* aNode);
1.1144 +
1.1145 + // no copy's or assigns FIX ME
1.1146 + nsContentSubtreeIterator(const nsContentSubtreeIterator&);
1.1147 + nsContentSubtreeIterator& operator=(const nsContentSubtreeIterator&);
1.1148 +
1.1149 + virtual void LastRelease() MOZ_OVERRIDE;
1.1150 +
1.1151 + nsRefPtr<nsRange> mRange;
1.1152 +
1.1153 + // these arrays all typically are used and have elements
1.1154 + nsAutoTArray<nsIContent*, 8> mEndNodes;
1.1155 + nsAutoTArray<int32_t, 8> mEndOffsets;
1.1156 +};
1.1157 +
1.1158 +NS_IMPL_ADDREF_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1.1159 +NS_IMPL_RELEASE_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1.1160 +
1.1161 +NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator)
1.1162 +NS_INTERFACE_MAP_END_INHERITING(nsContentIterator)
1.1163 +
1.1164 +NS_IMPL_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator, nsContentIterator,
1.1165 + mRange)
1.1166 +
1.1167 +void
1.1168 +nsContentSubtreeIterator::LastRelease()
1.1169 +{
1.1170 + mRange = nullptr;
1.1171 + nsContentIterator::LastRelease();
1.1172 +}
1.1173 +
1.1174 +/******************************************************
1.1175 + * repository cruft
1.1176 + ******************************************************/
1.1177 +
1.1178 +already_AddRefed<nsIContentIterator>
1.1179 +NS_NewContentSubtreeIterator()
1.1180 +{
1.1181 + nsCOMPtr<nsIContentIterator> iter = new nsContentSubtreeIterator();
1.1182 + return iter.forget();
1.1183 +}
1.1184 +
1.1185 +
1.1186 +
1.1187 +/******************************************************
1.1188 + * Init routines
1.1189 + ******************************************************/
1.1190 +
1.1191 +
1.1192 +nsresult
1.1193 +nsContentSubtreeIterator::Init(nsINode* aRoot)
1.1194 +{
1.1195 + return NS_ERROR_NOT_IMPLEMENTED;
1.1196 +}
1.1197 +
1.1198 +
1.1199 +nsresult
1.1200 +nsContentSubtreeIterator::Init(nsIDOMRange* aRange)
1.1201 +{
1.1202 + MOZ_ASSERT(aRange);
1.1203 +
1.1204 + mIsDone = false;
1.1205 +
1.1206 + mRange = static_cast<nsRange*>(aRange);
1.1207 +
1.1208 + // get the start node and offset, convert to nsINode
1.1209 + mCommonParent = mRange->GetCommonAncestor();
1.1210 + nsINode* startParent = mRange->GetStartParent();
1.1211 + int32_t startOffset = mRange->StartOffset();
1.1212 + nsINode* endParent = mRange->GetEndParent();
1.1213 + int32_t endOffset = mRange->EndOffset();
1.1214 + MOZ_ASSERT(mCommonParent && startParent && endParent);
1.1215 + // Bug 767169
1.1216 + MOZ_ASSERT(uint32_t(startOffset) <= startParent->Length() &&
1.1217 + uint32_t(endOffset) <= endParent->Length());
1.1218 +
1.1219 + // short circuit when start node == end node
1.1220 + if (startParent == endParent) {
1.1221 + nsINode* child = startParent->GetFirstChild();
1.1222 +
1.1223 + if (!child || startOffset == endOffset) {
1.1224 + // Text node, empty container, or collapsed
1.1225 + MakeEmpty();
1.1226 + return NS_OK;
1.1227 + }
1.1228 + }
1.1229 +
1.1230 + // cache ancestors
1.1231 + nsContentUtils::GetAncestorsAndOffsets(endParent->AsDOMNode(), endOffset,
1.1232 + &mEndNodes, &mEndOffsets);
1.1233 +
1.1234 + nsIContent* firstCandidate = nullptr;
1.1235 + nsIContent* lastCandidate = nullptr;
1.1236 +
1.1237 + // find first node in range
1.1238 + int32_t offset = mRange->StartOffset();
1.1239 +
1.1240 + nsINode* node;
1.1241 + if (!startParent->GetChildCount()) {
1.1242 + // no children, start at the node itself
1.1243 + node = startParent;
1.1244 + } else {
1.1245 + nsIContent* child = startParent->GetChildAt(offset);
1.1246 + if (!child) {
1.1247 + // offset after last child
1.1248 + node = startParent;
1.1249 + } else {
1.1250 + firstCandidate = child;
1.1251 + }
1.1252 + }
1.1253 +
1.1254 + if (!firstCandidate) {
1.1255 + // then firstCandidate is next node after node
1.1256 + firstCandidate = GetNextSibling(node);
1.1257 +
1.1258 + if (!firstCandidate) {
1.1259 + MakeEmpty();
1.1260 + return NS_OK;
1.1261 + }
1.1262 + }
1.1263 +
1.1264 + firstCandidate = GetDeepFirstChild(firstCandidate);
1.1265 +
1.1266 + // confirm that this first possible contained node is indeed contained. Else
1.1267 + // we have a range that does not fully contain any node.
1.1268 +
1.1269 + bool nodeBefore, nodeAfter;
1.1270 + MOZ_ALWAYS_TRUE(NS_SUCCEEDED(
1.1271 + nsRange::CompareNodeToRange(firstCandidate, mRange, &nodeBefore, &nodeAfter)));
1.1272 +
1.1273 + if (nodeBefore || nodeAfter) {
1.1274 + MakeEmpty();
1.1275 + return NS_OK;
1.1276 + }
1.1277 +
1.1278 + // cool, we have the first node in the range. Now we walk up its ancestors
1.1279 + // to find the most senior that is still in the range. That's the real first
1.1280 + // node.
1.1281 + mFirst = GetTopAncestorInRange(firstCandidate);
1.1282 +
1.1283 + // now to find the last node
1.1284 + offset = mRange->EndOffset();
1.1285 + int32_t numChildren = endParent->GetChildCount();
1.1286 +
1.1287 + if (offset > numChildren) {
1.1288 + // Can happen for text nodes
1.1289 + offset = numChildren;
1.1290 + }
1.1291 + if (!offset || !numChildren) {
1.1292 + node = endParent;
1.1293 + } else {
1.1294 + lastCandidate = endParent->GetChildAt(--offset);
1.1295 + NS_ASSERTION(lastCandidate,
1.1296 + "tree traversal trouble in nsContentSubtreeIterator::Init");
1.1297 + }
1.1298 +
1.1299 + if (!lastCandidate) {
1.1300 + // then lastCandidate is prev node before node
1.1301 + lastCandidate = GetPrevSibling(node);
1.1302 + }
1.1303 +
1.1304 + if (!lastCandidate) {
1.1305 + MakeEmpty();
1.1306 + return NS_OK;
1.1307 + }
1.1308 +
1.1309 + lastCandidate = GetDeepLastChild(lastCandidate);
1.1310 +
1.1311 + // confirm that this last possible contained node is indeed contained. Else
1.1312 + // we have a range that does not fully contain any node.
1.1313 +
1.1314 + MOZ_ALWAYS_TRUE(NS_SUCCEEDED(
1.1315 + nsRange::CompareNodeToRange(lastCandidate, mRange, &nodeBefore, &nodeAfter)));
1.1316 +
1.1317 + if (nodeBefore || nodeAfter) {
1.1318 + MakeEmpty();
1.1319 + return NS_OK;
1.1320 + }
1.1321 +
1.1322 + // cool, we have the last node in the range. Now we walk up its ancestors to
1.1323 + // find the most senior that is still in the range. That's the real first
1.1324 + // node.
1.1325 + mLast = GetTopAncestorInRange(lastCandidate);
1.1326 +
1.1327 + mCurNode = mFirst;
1.1328 +
1.1329 + return NS_OK;
1.1330 +}
1.1331 +
1.1332 +/****************************************************************
1.1333 + * nsContentSubtreeIterator overrides of ContentIterator routines
1.1334 + ****************************************************************/
1.1335 +
1.1336 +// we can't call PositionAt in a subtree iterator...
1.1337 +void
1.1338 +nsContentSubtreeIterator::First()
1.1339 +{
1.1340 + mIsDone = mFirst == nullptr;
1.1341 +
1.1342 + mCurNode = mFirst;
1.1343 +}
1.1344 +
1.1345 +// we can't call PositionAt in a subtree iterator...
1.1346 +void
1.1347 +nsContentSubtreeIterator::Last()
1.1348 +{
1.1349 + mIsDone = mLast == nullptr;
1.1350 +
1.1351 + mCurNode = mLast;
1.1352 +}
1.1353 +
1.1354 +
1.1355 +void
1.1356 +nsContentSubtreeIterator::Next()
1.1357 +{
1.1358 + if (mIsDone || !mCurNode) {
1.1359 + return;
1.1360 + }
1.1361 +
1.1362 + if (mCurNode == mLast) {
1.1363 + mIsDone = true;
1.1364 + return;
1.1365 + }
1.1366 +
1.1367 + nsINode* nextNode = GetNextSibling(mCurNode);
1.1368 + NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
1.1369 +
1.1370 + int32_t i = mEndNodes.IndexOf(nextNode);
1.1371 + while (i != -1) {
1.1372 + // as long as we are finding ancestors of the endpoint of the range,
1.1373 + // dive down into their children
1.1374 + nextNode = nextNode->GetFirstChild();
1.1375 + NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
1.1376 +
1.1377 + // should be impossible to get a null pointer. If we went all the way
1.1378 + // down the child chain to the bottom without finding an interior node,
1.1379 + // then the previous node should have been the last, which was
1.1380 + // was tested at top of routine.
1.1381 + i = mEndNodes.IndexOf(nextNode);
1.1382 + }
1.1383 +
1.1384 + mCurNode = nextNode;
1.1385 +
1.1386 + // This shouldn't be needed, but since our selection code can put us
1.1387 + // in a situation where mLast is in generated content, we need this
1.1388 + // to stop the iterator when we've walked past past the last node!
1.1389 + mIsDone = mCurNode == nullptr;
1.1390 +}
1.1391 +
1.1392 +
1.1393 +void
1.1394 +nsContentSubtreeIterator::Prev()
1.1395 +{
1.1396 + // Prev should be optimized to use the mStartNodes, just as Next
1.1397 + // uses mEndNodes.
1.1398 + if (mIsDone || !mCurNode) {
1.1399 + return;
1.1400 + }
1.1401 +
1.1402 + if (mCurNode == mFirst) {
1.1403 + mIsDone = true;
1.1404 + return;
1.1405 + }
1.1406 +
1.1407 + // If any of these function calls return null, so will all succeeding ones,
1.1408 + // so mCurNode will wind up set to null.
1.1409 + nsINode* prevNode = GetDeepFirstChild(mCurNode);
1.1410 +
1.1411 + prevNode = PrevNode(prevNode);
1.1412 +
1.1413 + prevNode = GetDeepLastChild(prevNode);
1.1414 +
1.1415 + mCurNode = GetTopAncestorInRange(prevNode);
1.1416 +
1.1417 + // This shouldn't be needed, but since our selection code can put us
1.1418 + // in a situation where mFirst is in generated content, we need this
1.1419 + // to stop the iterator when we've walked past past the first node!
1.1420 + mIsDone = mCurNode == nullptr;
1.1421 +}
1.1422 +
1.1423 +
1.1424 +nsresult
1.1425 +nsContentSubtreeIterator::PositionAt(nsINode* aCurNode)
1.1426 +{
1.1427 + NS_ERROR("Not implemented!");
1.1428 +
1.1429 + return NS_ERROR_NOT_IMPLEMENTED;
1.1430 +}
1.1431 +
1.1432 +/****************************************************************
1.1433 + * nsContentSubtreeIterator helper routines
1.1434 + ****************************************************************/
1.1435 +
1.1436 +nsIContent*
1.1437 +nsContentSubtreeIterator::GetTopAncestorInRange(nsINode* aNode)
1.1438 +{
1.1439 + if (!aNode || !aNode->GetParentNode()) {
1.1440 + return nullptr;
1.1441 + }
1.1442 +
1.1443 + // aNode has a parent, so it must be content.
1.1444 + nsIContent* content = aNode->AsContent();
1.1445 +
1.1446 + // sanity check: aNode is itself in the range
1.1447 + bool nodeBefore, nodeAfter;
1.1448 + nsresult res = nsRange::CompareNodeToRange(aNode, mRange,
1.1449 + &nodeBefore, &nodeAfter);
1.1450 + NS_ASSERTION(NS_SUCCEEDED(res) && !nodeBefore && !nodeAfter,
1.1451 + "aNode isn't in mRange, or something else weird happened");
1.1452 + if (NS_FAILED(res) || nodeBefore || nodeAfter) {
1.1453 + return nullptr;
1.1454 + }
1.1455 +
1.1456 + while (content) {
1.1457 + nsIContent* parent = content->GetParent();
1.1458 + // content always has a parent. If its parent is the root, however --
1.1459 + // i.e., either it's not content, or it is content but its own parent is
1.1460 + // null -- then we're finished, since we don't go up to the root.
1.1461 + //
1.1462 + // We have to special-case this because CompareNodeToRange treats the root
1.1463 + // node differently -- see bug 765205.
1.1464 + if (!parent || !parent->GetParentNode()) {
1.1465 + return content;
1.1466 + }
1.1467 + MOZ_ALWAYS_TRUE(NS_SUCCEEDED(
1.1468 + nsRange::CompareNodeToRange(parent, mRange, &nodeBefore, &nodeAfter)));
1.1469 +
1.1470 + if (nodeBefore || nodeAfter) {
1.1471 + return content;
1.1472 + }
1.1473 + content = parent;
1.1474 + }
1.1475 +
1.1476 + MOZ_CRASH("This should only be possible if aNode was null");
1.1477 +}
