1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "mozilla/DebugOnly.h"
8 #include "nsISupports.h"
9 #include "nsIDOMNodeList.h"
10 #include "nsIContentIterator.h"
11 #include "nsRange.h"
12 #include "nsIContent.h"
13 #include "nsCOMPtr.h"
14 #include "nsTArray.h"
15 #include "nsContentUtils.h"
16 #include "nsINode.h"
17 #include "nsCycleCollectionParticipant.h"
18
19 using mozilla::DebugOnly;
20
21 // couple of utility static functs
22
23 ///////////////////////////////////////////////////////////////////////////
24 // NodeToParentOffset: returns the node's parent and offset.
25 //
26
27 static nsINode*
NodeToParentOffset(nsINode * aNode,int32_t * aOffset)28 NodeToParentOffset(nsINode* aNode, int32_t* aOffset)
29 {
30 *aOffset = 0;
31
32 nsINode* parent = aNode->GetParentNode();
33
34 if (parent) {
35 *aOffset = parent->IndexOf(aNode);
36 NS_WARNING_ASSERTION(*aOffset >= 0, "bad offset");
37 }
38
39 return parent;
40 }
41
42 ///////////////////////////////////////////////////////////////////////////
43 // NodeIsInTraversalRange: returns true if content is visited during
44 // the traversal of the range in the specified mode.
45 //
46 static bool
NodeIsInTraversalRange(nsINode * aNode,bool aIsPreMode,nsINode * aStartNode,int32_t aStartOffset,nsINode * aEndNode,int32_t aEndOffset)47 NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode,
48 nsINode* aStartNode, int32_t aStartOffset,
49 nsINode* aEndNode, int32_t aEndOffset)
50 {
51 if (NS_WARN_IF(!aStartNode) || NS_WARN_IF(!aEndNode) || NS_WARN_IF(!aNode)) {
52 return false;
53 }
54
55 // If a leaf node contains an end point of the traversal range, it is
56 // always in the traversal range.
57 if (aNode == aStartNode || aNode == aEndNode) {
58 if (aNode->IsNodeOfType(nsINode::eDATA_NODE)) {
59 return true; // text node or something
60 }
61 if (!aNode->HasChildren()) {
62 MOZ_ASSERT(aNode != aStartNode || !aStartOffset,
63 "aStartNode doesn't have children and not a data node, "
64 "aStartOffset should be 0");
65 MOZ_ASSERT(aNode != aEndNode || !aEndOffset,
66 "aStartNode doesn't have children and not a data node, "
67 "aStartOffset should be 0");
68 return true;
69 }
70 }
71
72 nsINode* parent = aNode->GetParentNode();
73 if (!parent) {
74 return false;
75 }
76
77 int32_t indx = parent->IndexOf(aNode);
78 NS_WARNING_ASSERTION(indx != -1, "bad indx");
79
80 if (!aIsPreMode) {
81 ++indx;
82 }
83
84 return nsContentUtils::ComparePoints(aStartNode, aStartOffset,
85 parent, indx) <= 0 &&
86 nsContentUtils::ComparePoints(aEndNode, aEndOffset,
87 parent, indx) >= 0;
88 }
89
90
91
92 /*
93 * A simple iterator class for traversing the content in "close tag" order
94 */
95 class nsContentIterator : public nsIContentIterator
96 {
97 public:
98 NS_DECL_CYCLE_COLLECTING_ISUPPORTS
99 NS_DECL_CYCLE_COLLECTION_CLASS(nsContentIterator)
100
101 explicit nsContentIterator(bool aPre);
102
103 // nsIContentIterator interface methods ------------------------------
104
105 virtual nsresult Init(nsINode* aRoot) override;
106
107 virtual nsresult Init(nsIDOMRange* aRange) override;
108
109 virtual void First() override;
110
111 virtual void Last() override;
112
113 virtual void Next() override;
114
115 virtual void Prev() override;
116
117 virtual nsINode* GetCurrentNode() override;
118
119 virtual bool IsDone() override;
120
121 virtual nsresult PositionAt(nsINode* aCurNode) override;
122
123 protected:
124 virtual ~nsContentIterator();
125
126 // Recursively get the deepest first/last child of aRoot. This will return
127 // aRoot itself if it has no children.
128 nsINode* GetDeepFirstChild(nsINode* aRoot,
129 nsTArray<int32_t>* aIndexes = nullptr);
130 nsIContent* GetDeepFirstChild(nsIContent* aRoot,
131 nsTArray<int32_t>* aIndexes = nullptr);
132 nsINode* GetDeepLastChild(nsINode* aRoot,
133 nsTArray<int32_t>* aIndexes = nullptr);
134 nsIContent* GetDeepLastChild(nsIContent* aRoot,
135 nsTArray<int32_t>* aIndexes = nullptr);
136
137 // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
138 // etc. Returns null if aNode and all its ancestors have no next/previous
139 // sibling.
140 nsIContent* GetNextSibling(nsINode* aNode,
141 nsTArray<int32_t>* aIndexes = nullptr);
142 nsIContent* GetPrevSibling(nsINode* aNode,
143 nsTArray<int32_t>* aIndexes = nullptr);
144
145 nsINode* NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
146 nsINode* PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
147
148 // WARNING: This function is expensive
149 nsresult RebuildIndexStack();
150
151 void MakeEmpty();
152
153 virtual void LastRelease();
154
155 nsCOMPtr<nsINode> mCurNode;
156 nsCOMPtr<nsINode> mFirst;
157 nsCOMPtr<nsINode> mLast;
158 nsCOMPtr<nsINode> mCommonParent;
159
160 // used by nsContentIterator to cache indices
161 AutoTArray<int32_t, 8> mIndexes;
162
163 // used by nsSubtreeIterator to cache indices. Why put them in the base
164 // class? Because otherwise I have to duplicate the routines GetNextSibling
165 // etc across both classes, with slight variations for caching. Or
166 // alternately, create a base class for the cache itself and have all the
167 // cache manipulation go through a vptr. I think this is the best space and
168 // speed combo, even though it's ugly.
169 int32_t mCachedIndex;
170 // another note about mCachedIndex: why should the subtree iterator use a
171 // trivial cached index instead of the mre robust array of indicies (which is
172 // what the basic content iterator uses)? The reason is that subtree
173 // iterators do not do much transitioning between parents and children. They
174 // tend to stay at the same level. In fact, you can prove (though I won't
175 // attempt it here) that they change levels at most n+m times, where n is the
176 // height of the parent hierarchy from the range start to the common
177 // ancestor, and m is the the height of the parent hierarchy from the range
178 // end to the common ancestor. If we used the index array, we would pay the
179 // price up front for n, and then pay the cost for m on the fly later on.
180 // With the simple cache, we only "pay as we go". Either way, we call
181 // IndexOf() once for each change of level in the hierarchy. Since a trivial
182 // index is much simpler, we use it for the subtree iterator.
183
184 bool mIsDone;
185 bool mPre;
186
187 private:
188
189 // no copies or assigns FIX ME
190 nsContentIterator(const nsContentIterator&);
191 nsContentIterator& operator=(const nsContentIterator&);
192
193 };
194
195
196 /******************************************************
197 * repository cruft
198 ******************************************************/
199
200 already_AddRefed<nsIContentIterator>
NS_NewContentIterator()201 NS_NewContentIterator()
202 {
203 nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(false);
204 return iter.forget();
205 }
206
207
208 already_AddRefed<nsIContentIterator>
NS_NewPreContentIterator()209 NS_NewPreContentIterator()
210 {
211 nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(true);
212 return iter.forget();
213 }
214
215
216 /******************************************************
217 * XPCOM cruft
218 ******************************************************/
219
220 NS_IMPL_CYCLE_COLLECTING_ADDREF(nsContentIterator)
NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(nsContentIterator,LastRelease ())221 NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(nsContentIterator,
222 LastRelease())
223
224 NS_INTERFACE_MAP_BEGIN(nsContentIterator)
225 NS_INTERFACE_MAP_ENTRY(nsIContentIterator)
226 NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIContentIterator)
227 NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION(nsContentIterator)
228 NS_INTERFACE_MAP_END
229
230 NS_IMPL_CYCLE_COLLECTION(nsContentIterator,
231 mCurNode,
232 mFirst,
233 mLast,
234 mCommonParent)
235
236 void
237 nsContentIterator::LastRelease()
238 {
239 mCurNode = nullptr;
240 mFirst = nullptr;
241 mLast = nullptr;
242 mCommonParent = nullptr;
243 }
244
245 /******************************************************
246 * constructor/destructor
247 ******************************************************/
248
nsContentIterator(bool aPre)249 nsContentIterator::nsContentIterator(bool aPre) :
250 // don't need to explicitly initialize |nsCOMPtr|s, they will automatically
251 // be nullptr
252 mCachedIndex(0), mIsDone(false), mPre(aPre)
253 {
254 }
255
256
~nsContentIterator()257 nsContentIterator::~nsContentIterator()
258 {
259 }
260
261
262 /******************************************************
263 * Init routines
264 ******************************************************/
265
266
267 nsresult
Init(nsINode * aRoot)268 nsContentIterator::Init(nsINode* aRoot)
269 {
270 if (NS_WARN_IF(!aRoot)) {
271 return NS_ERROR_NULL_POINTER;
272 }
273
274 mIsDone = false;
275 mIndexes.Clear();
276
277 if (mPre) {
278 mFirst = aRoot;
279 mLast = GetDeepLastChild(aRoot);
280 NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
281 } else {
282 mFirst = GetDeepFirstChild(aRoot);
283 NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
284 mLast = aRoot;
285 }
286
287 mCommonParent = aRoot;
288 mCurNode = mFirst;
289 RebuildIndexStack();
290 return NS_OK;
291 }
292
293 nsresult
Init(nsIDOMRange * aDOMRange)294 nsContentIterator::Init(nsIDOMRange* aDOMRange)
295 {
296 if (NS_WARN_IF(!aDOMRange)) {
297 return NS_ERROR_INVALID_ARG;
298 }
299 nsRange* range = static_cast<nsRange*>(aDOMRange);
300
301 mIsDone = false;
302
303 // get common content parent
304 mCommonParent = range->GetCommonAncestor();
305 if (NS_WARN_IF(!mCommonParent)) {
306 return NS_ERROR_FAILURE;
307 }
308
309 // get the start node and offset
310 int32_t startIndx = range->StartOffset();
311 NS_WARNING_ASSERTION(startIndx >= 0, "bad startIndx");
312 nsINode* startNode = range->GetStartParent();
313 if (NS_WARN_IF(!startNode)) {
314 return NS_ERROR_FAILURE;
315 }
316
317 // get the end node and offset
318 int32_t endIndx = range->EndOffset();
319 NS_WARNING_ASSERTION(endIndx >= 0, "bad endIndx");
320 nsINode* endNode = range->GetEndParent();
321 if (NS_WARN_IF(!endNode)) {
322 return NS_ERROR_FAILURE;
323 }
324
325 bool startIsData = startNode->IsNodeOfType(nsINode::eDATA_NODE);
326
327 // short circuit when start node == end node
328 if (startNode == endNode) {
329 // Check to see if we have a collapsed range, if so, there is nothing to
330 // iterate over.
331 //
332 // XXX: CharacterDataNodes (text nodes) are currently an exception, since
333 // we always want to be able to iterate text nodes at the end points
334 // of a range.
335
336 if (!startIsData && startIndx == endIndx) {
337 MakeEmpty();
338 return NS_OK;
339 }
340
341 if (startIsData) {
342 // It's a character data node.
343 mFirst = startNode->AsContent();
344 mLast = mFirst;
345 mCurNode = mFirst;
346
347 DebugOnly<nsresult> rv = RebuildIndexStack();
348 NS_WARNING_ASSERTION(NS_SUCCEEDED(rv), "RebuildIndexStack failed");
349 return NS_OK;
350 }
351 }
352
353 // Find first node in range.
354
355 nsIContent* cChild = nullptr;
356
357 // Valid start indices are 0 <= startIndx <= childCount. That means if start
358 // node has no children, only offset 0 is valid.
359 if (!startIsData && uint32_t(startIndx) < startNode->GetChildCount()) {
360 cChild = startNode->GetChildAt(startIndx);
361 NS_WARNING_ASSERTION(cChild, "GetChildAt returned null");
362 }
363
364 if (!cChild) {
365 // No children (possibly a <br> or text node), or index is after last child.
366
367 if (mPre) {
368 // XXX: In the future, if start offset is after the last
369 // character in the cdata node, should we set mFirst to
370 // the next sibling?
371
372 // Normally we would skip the start node because the start node is outside
373 // of the range in pre mode. However, if startIndx == 0, it means the node
374 // has no children, and the node may be <br> or something. We don't skip
375 // the node in this case in order to address bug 1215798.
376 if (!startIsData && startIndx) {
377 mFirst = GetNextSibling(startNode);
378 NS_WARNING_ASSERTION(mFirst, "GetNextSibling returned null");
379
380 // Does mFirst node really intersect the range? The range could be
381 // 'degenerate', i.e., not collapsed but still contain no content.
382 if (mFirst &&
383 NS_WARN_IF(!NodeIsInTraversalRange(mFirst, mPre, startNode,
384 startIndx, endNode, endIndx))) {
385 mFirst = nullptr;
386 }
387 } else {
388 mFirst = startNode->AsContent();
389 }
390 } else {
391 // post-order
392 if (NS_WARN_IF(!startNode->IsContent())) {
393 // What else can we do?
394 mFirst = nullptr;
395 } else {
396 mFirst = startNode->AsContent();
397 }
398 }
399 } else {
400 if (mPre) {
401 mFirst = cChild;
402 } else {
403 // post-order
404 mFirst = GetDeepFirstChild(cChild);
405 NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
406
407 // Does mFirst node really intersect the range? The range could be
408 // 'degenerate', i.e., not collapsed but still contain no content.
409
410 if (mFirst &&
411 !NodeIsInTraversalRange(mFirst, mPre, startNode, startIndx,
412 endNode, endIndx)) {
413 mFirst = nullptr;
414 }
415 }
416 }
417
418
419 // Find last node in range.
420
421 bool endIsData = endNode->IsNodeOfType(nsINode::eDATA_NODE);
422
423 if (endIsData || !endNode->HasChildren() || endIndx == 0) {
424 if (mPre) {
425 if (NS_WARN_IF(!endNode->IsContent())) {
426 // Not much else to do here...
427 mLast = nullptr;
428 } else {
429 // If the end node is an empty element and the end offset is 0,
430 // the last element should be the previous node (i.e., shouldn't
431 // include the end node in the range).
432 if (!endIsData && !endNode->HasChildren() && !endIndx) {
433 mLast = PrevNode(endNode);
434 NS_WARNING_ASSERTION(mLast, "PrevNode returned null");
435 if (NS_WARN_IF(!NodeIsInTraversalRange(mLast, mPre,
436 startNode, startIndx,
437 endNode, endIndx))) {
438 mLast = nullptr;
439 }
440 } else {
441 mLast = endNode->AsContent();
442 }
443 }
444 } else {
445 // post-order
446 //
447 // XXX: In the future, if end offset is before the first character in the
448 // cdata node, should we set mLast to the prev sibling?
449
450 if (!endIsData) {
451 mLast = GetPrevSibling(endNode);
452 NS_WARNING_ASSERTION(mLast, "GetPrevSibling returned null");
453
454 if (!NodeIsInTraversalRange(mLast, mPre,
455 startNode, startIndx,
456 endNode, endIndx)) {
457 mLast = nullptr;
458 }
459 } else {
460 mLast = endNode->AsContent();
461 }
462 }
463 } else {
464 int32_t indx = endIndx;
465
466 cChild = endNode->GetChildAt(--indx);
467
468 if (NS_WARN_IF(!cChild)) {
469 // No child at offset!
470 NS_NOTREACHED("nsContentIterator::nsContentIterator");
471 return NS_ERROR_FAILURE;
472 }
473
474 if (mPre) {
475 mLast = GetDeepLastChild(cChild);
476 NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
477
478 if (NS_WARN_IF(!NodeIsInTraversalRange(mLast, mPre,
479 startNode, startIndx,
480 endNode, endIndx))) {
481 mLast = nullptr;
482 }
483 } else {
484 // post-order
485 mLast = cChild;
486 }
487 }
488
489 // If either first or last is null, they both have to be null!
490
491 if (!mFirst || !mLast) {
492 mFirst = nullptr;
493 mLast = nullptr;
494 }
495
496 mCurNode = mFirst;
497 mIsDone = !mCurNode;
498
499 if (!mCurNode) {
500 mIndexes.Clear();
501 } else {
502 DebugOnly<nsresult> rv = RebuildIndexStack();
503 NS_WARNING_ASSERTION(NS_SUCCEEDED(rv), "RebuildIndexStack failed");
504 }
505
506 return NS_OK;
507 }
508
509
510 /******************************************************
511 * Helper routines
512 ******************************************************/
513 // WARNING: This function is expensive
514 nsresult
RebuildIndexStack()515 nsContentIterator::RebuildIndexStack()
516 {
517 // Make sure we start at the right indexes on the stack! Build array up
518 // to common parent of start and end. Perhaps it's too many entries, but
519 // that's far better than too few.
520 nsINode* parent;
521 nsINode* current;
522
523 mIndexes.Clear();
524 current = mCurNode;
525 if (!current) {
526 return NS_OK;
527 }
528
529 while (current != mCommonParent) {
530 parent = current->GetParentNode();
531
532 if (NS_WARN_IF(!parent)) {
533 return NS_ERROR_FAILURE;
534 }
535
536 mIndexes.InsertElementAt(0, parent->IndexOf(current));
537
538 current = parent;
539 }
540
541 return NS_OK;
542 }
543
544 void
MakeEmpty()545 nsContentIterator::MakeEmpty()
546 {
547 mCurNode = nullptr;
548 mFirst = nullptr;
549 mLast = nullptr;
550 mCommonParent = nullptr;
551 mIsDone = true;
552 mIndexes.Clear();
553 }
554
555 nsINode*
GetDeepFirstChild(nsINode * aRoot,nsTArray<int32_t> * aIndexes)556 nsContentIterator::GetDeepFirstChild(nsINode* aRoot,
557 nsTArray<int32_t>* aIndexes)
558 {
559 if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
560 return aRoot;
561 }
562 // We can't pass aRoot itself to the full GetDeepFirstChild, because that
563 // will only take nsIContent and aRoot might be a document. Pass aRoot's
564 // child, but be sure to preserve aIndexes.
565 if (aIndexes) {
566 aIndexes->AppendElement(0);
567 }
568 return GetDeepFirstChild(aRoot->GetFirstChild(), aIndexes);
569 }
570
571 nsIContent*
GetDeepFirstChild(nsIContent * aRoot,nsTArray<int32_t> * aIndexes)572 nsContentIterator::GetDeepFirstChild(nsIContent* aRoot,
573 nsTArray<int32_t>* aIndexes)
574 {
575 if (NS_WARN_IF(!aRoot)) {
576 return nullptr;
577 }
578
579 nsIContent* node = aRoot;
580 nsIContent* child = node->GetFirstChild();
581
582 while (child) {
583 if (aIndexes) {
584 // Add this node to the stack of indexes
585 aIndexes->AppendElement(0);
586 }
587 node = child;
588 child = node->GetFirstChild();
589 }
590
591 return node;
592 }
593
594 nsINode*
GetDeepLastChild(nsINode * aRoot,nsTArray<int32_t> * aIndexes)595 nsContentIterator::GetDeepLastChild(nsINode* aRoot,
596 nsTArray<int32_t>* aIndexes)
597 {
598 if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
599 return aRoot;
600 }
601 // We can't pass aRoot itself to the full GetDeepLastChild, because that will
602 // only take nsIContent and aRoot might be a document. Pass aRoot's child,
603 // but be sure to preserve aIndexes.
604 if (aIndexes) {
605 aIndexes->AppendElement(aRoot->GetChildCount() - 1);
606 }
607 return GetDeepLastChild(aRoot->GetLastChild(), aIndexes);
608 }
609
610 nsIContent*
GetDeepLastChild(nsIContent * aRoot,nsTArray<int32_t> * aIndexes)611 nsContentIterator::GetDeepLastChild(nsIContent* aRoot,
612 nsTArray<int32_t>* aIndexes)
613 {
614 if (NS_WARN_IF(!aRoot)) {
615 return nullptr;
616 }
617
618 nsIContent* node = aRoot;
619 int32_t numChildren = node->GetChildCount();
620
621 while (numChildren) {
622 nsIContent* child = node->GetChildAt(--numChildren);
623
624 if (aIndexes) {
625 // Add this node to the stack of indexes
626 aIndexes->AppendElement(numChildren);
627 }
628 numChildren = child->GetChildCount();
629 node = child;
630 }
631
632 return node;
633 }
634
635 // Get the next sibling, or parent's next sibling, or grandpa's next sibling...
636 nsIContent*
GetNextSibling(nsINode * aNode,nsTArray<int32_t> * aIndexes)637 nsContentIterator::GetNextSibling(nsINode* aNode,
638 nsTArray<int32_t>* aIndexes)
639 {
640 if (NS_WARN_IF(!aNode)) {
641 return nullptr;
642 }
643
644 nsINode* parent = aNode->GetParentNode();
645 if (NS_WARN_IF(!parent)) {
646 return nullptr;
647 }
648
649 int32_t indx = 0;
650
651 NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
652 "ContentIterator stack underflow");
653 if (aIndexes && !aIndexes->IsEmpty()) {
654 // use the last entry on the Indexes array for the current index
655 indx = (*aIndexes)[aIndexes->Length()-1];
656 } else {
657 indx = mCachedIndex;
658 }
659 NS_WARNING_ASSERTION(indx >= 0, "bad indx");
660
661 // reverify that the index of the current node hasn't changed.
662 // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
663 // ignore result this time - the index may now be out of range.
664 nsIContent* sib = parent->GetChildAt(indx);
665 if (sib != aNode) {
666 // someone changed our index - find the new index the painful way
667 indx = parent->IndexOf(aNode);
668 NS_WARNING_ASSERTION(indx >= 0, "bad indx");
669 }
670
671 // indx is now canonically correct
672 if ((sib = parent->GetChildAt(++indx))) {
673 // update index cache
674 if (aIndexes && !aIndexes->IsEmpty()) {
675 aIndexes->ElementAt(aIndexes->Length()-1) = indx;
676 } else {
677 mCachedIndex = indx;
678 }
679 } else {
680 if (parent != mCommonParent) {
681 if (aIndexes) {
682 // pop node off the stack, go up one level and return parent or fail.
683 // Don't leave the index empty, especially if we're
684 // returning nullptr. This confuses other parts of the code.
685 if (aIndexes->Length() > 1) {
686 aIndexes->RemoveElementAt(aIndexes->Length()-1);
687 }
688 }
689 }
690
691 // ok to leave cache out of date here if parent == mCommonParent?
692 sib = GetNextSibling(parent, aIndexes);
693 }
694
695 return sib;
696 }
697
698 // Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
699 nsIContent*
GetPrevSibling(nsINode * aNode,nsTArray<int32_t> * aIndexes)700 nsContentIterator::GetPrevSibling(nsINode* aNode,
701 nsTArray<int32_t>* aIndexes)
702 {
703 if (NS_WARN_IF(!aNode)) {
704 return nullptr;
705 }
706
707 nsINode* parent = aNode->GetParentNode();
708 if (NS_WARN_IF(!parent)) {
709 return nullptr;
710 }
711
712 int32_t indx = 0;
713
714 NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
715 "ContentIterator stack underflow");
716 if (aIndexes && !aIndexes->IsEmpty()) {
717 // use the last entry on the Indexes array for the current index
718 indx = (*aIndexes)[aIndexes->Length()-1];
719 } else {
720 indx = mCachedIndex;
721 }
722
723 // reverify that the index of the current node hasn't changed
724 // ignore result this time - the index may now be out of range.
725 nsIContent* sib = parent->GetChildAt(indx);
726 if (sib != aNode) {
727 // someone changed our index - find the new index the painful way
728 indx = parent->IndexOf(aNode);
729 NS_WARNING_ASSERTION(indx >= 0, "bad indx");
730 }
731
732 // indx is now canonically correct
733 if (indx > 0 && (sib = parent->GetChildAt(--indx))) {
734 // update index cache
735 if (aIndexes && !aIndexes->IsEmpty()) {
736 aIndexes->ElementAt(aIndexes->Length()-1) = indx;
737 } else {
738 mCachedIndex = indx;
739 }
740 } else if (parent != mCommonParent) {
741 if (aIndexes && !aIndexes->IsEmpty()) {
742 // pop node off the stack, go up one level and try again.
743 aIndexes->RemoveElementAt(aIndexes->Length()-1);
744 }
745 return GetPrevSibling(parent, aIndexes);
746 }
747
748 return sib;
749 }
750
751 nsINode*
NextNode(nsINode * aNode,nsTArray<int32_t> * aIndexes)752 nsContentIterator::NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
753 {
754 nsINode* node = aNode;
755
756 // if we are a Pre-order iterator, use pre-order
757 if (mPre) {
758 // if it has children then next node is first child
759 if (node->HasChildren()) {
760 nsIContent* firstChild = node->GetFirstChild();
761 MOZ_ASSERT(firstChild);
762
763 // update cache
764 if (aIndexes) {
765 // push an entry on the index stack
766 aIndexes->AppendElement(0);
767 } else {
768 mCachedIndex = 0;
769 }
770
771 return firstChild;
772 }
773
774 // else next sibling is next
775 return GetNextSibling(node, aIndexes);
776 }
777
778 // post-order
779 nsINode* parent = node->GetParentNode();
780 if (NS_WARN_IF(!parent)) {
781 MOZ_ASSERT(parent, "The node is the root node but not the last node");
782 mIsDone = true;
783 return node;
784 }
785 nsIContent* sibling = nullptr;
786 int32_t indx = 0;
787
788 // get the cached index
789 NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
790 "ContentIterator stack underflow");
791 if (aIndexes && !aIndexes->IsEmpty()) {
792 // use the last entry on the Indexes array for the current index
793 indx = (*aIndexes)[aIndexes->Length()-1];
794 } else {
795 indx = mCachedIndex;
796 }
797
798 // reverify that the index of the current node hasn't changed. not super
799 // cheap, but a lot cheaper than IndexOf(), and still O(1). ignore result
800 // this time - the index may now be out of range.
801 if (indx >= 0) {
802 sibling = parent->GetChildAt(indx);
803 }
804 if (sibling != node) {
805 // someone changed our index - find the new index the painful way
806 indx = parent->IndexOf(node);
807 NS_WARNING_ASSERTION(indx >= 0, "bad indx");
808 }
809
810 // indx is now canonically correct
811 sibling = parent->GetChildAt(++indx);
812 if (sibling) {
813 // update cache
814 if (aIndexes && !aIndexes->IsEmpty()) {
815 // replace an entry on the index stack
816 aIndexes->ElementAt(aIndexes->Length()-1) = indx;
817 } else {
818 mCachedIndex = indx;
819 }
820
821 // next node is sibling's "deep left" child
822 return GetDeepFirstChild(sibling, aIndexes);
823 }
824
825 // else it's the parent, update cache
826 if (aIndexes) {
827 // Pop an entry off the index stack. Don't leave the index empty,
828 // especially if we're returning nullptr. This confuses other parts of the
829 // code.
830 if (aIndexes->Length() > 1) {
831 aIndexes->RemoveElementAt(aIndexes->Length()-1);
832 }
833 } else {
834 // this might be wrong, but we are better off guessing
835 mCachedIndex = 0;
836 }
837
838 return parent;
839 }
840
841 nsINode*
PrevNode(nsINode * aNode,nsTArray<int32_t> * aIndexes)842 nsContentIterator::PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
843 {
844 nsINode* node = aNode;
845
846 // if we are a Pre-order iterator, use pre-order
847 if (mPre) {
848 nsINode* parent = node->GetParentNode();
849 if (NS_WARN_IF(!parent)) {
850 MOZ_ASSERT(parent, "The node is the root node but not the first node");
851 mIsDone = true;
852 return aNode;
853 }
854 nsIContent* sibling = nullptr;
855 int32_t indx = 0;
856
857 // get the cached index
858 NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
859 "ContentIterator stack underflow");
860 if (aIndexes && !aIndexes->IsEmpty()) {
861 // use the last entry on the Indexes array for the current index
862 indx = (*aIndexes)[aIndexes->Length()-1];
863 } else {
864 indx = mCachedIndex;
865 }
866
867 // reverify that the index of the current node hasn't changed. not super
868 // cheap, but a lot cheaper than IndexOf(), and still O(1). ignore result
869 // this time - the index may now be out of range.
870 if (indx >= 0) {
871 sibling = parent->GetChildAt(indx);
872 NS_WARNING_ASSERTION(sibling, "GetChildAt returned null");
873 }
874
875 if (sibling != node) {
876 // someone changed our index - find the new index the painful way
877 indx = parent->IndexOf(node);
878 NS_WARNING_ASSERTION(indx >= 0, "bad indx");
879 }
880
881 // indx is now canonically correct
882 if (indx && (sibling = parent->GetChildAt(--indx))) {
883 // update cache
884 if (aIndexes && !aIndexes->IsEmpty()) {
885 // replace an entry on the index stack
886 aIndexes->ElementAt(aIndexes->Length()-1) = indx;
887 } else {
888 mCachedIndex = indx;
889 }
890
891 // prev node is sibling's "deep right" child
892 return GetDeepLastChild(sibling, aIndexes);
893 }
894
895 // else it's the parent, update cache
896 if (aIndexes && !aIndexes->IsEmpty()) {
897 // pop an entry off the index stack
898 aIndexes->RemoveElementAt(aIndexes->Length()-1);
899 } else {
900 // this might be wrong, but we are better off guessing
901 mCachedIndex = 0;
902 }
903 return parent;
904 }
905
906 // post-order
907 int32_t numChildren = node->GetChildCount();
908 NS_WARNING_ASSERTION(numChildren >= 0, "no children");
909
910 // if it has children then prev node is last child
911 if (numChildren) {
912 nsIContent* lastChild = node->GetLastChild();
913 NS_WARNING_ASSERTION(lastChild, "GetLastChild returned null");
914 numChildren--;
915
916 // update cache
917 if (aIndexes) {
918 // push an entry on the index stack
919 aIndexes->AppendElement(numChildren);
920 } else {
921 mCachedIndex = numChildren;
922 }
923
924 return lastChild;
925 }
926
927 // else prev sibling is previous
928 return GetPrevSibling(node, aIndexes);
929 }
930
931 /******************************************************
932 * ContentIterator routines
933 ******************************************************/
934
935 void
First()936 nsContentIterator::First()
937 {
938 if (mFirst) {
939 mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst);
940 NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
941 }
942
943 mIsDone = mFirst == nullptr;
944 }
945
946
947 void
Last()948 nsContentIterator::Last()
949 {
950 // Note that mLast can be nullptr if MakeEmpty() is called in Init() since
951 // at that time, Init() returns NS_OK.
952 if (!mLast) {
953 MOZ_ASSERT(mIsDone);
954 return;
955 }
956
957 mozilla::DebugOnly<nsresult> rv = PositionAt(mLast);
958 NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
959
960 mIsDone = mLast == nullptr;
961 }
962
963
964 void
Next()965 nsContentIterator::Next()
966 {
967 if (mIsDone || NS_WARN_IF(!mCurNode)) {
968 return;
969 }
970
971 if (mCurNode == mLast) {
972 mIsDone = true;
973 return;
974 }
975
976 mCurNode = NextNode(mCurNode, &mIndexes);
977 }
978
979
980 void
Prev()981 nsContentIterator::Prev()
982 {
983 if (NS_WARN_IF(mIsDone) || NS_WARN_IF(!mCurNode)) {
984 return;
985 }
986
987 if (mCurNode == mFirst) {
988 mIsDone = true;
989 return;
990 }
991
992 mCurNode = PrevNode(mCurNode, &mIndexes);
993 }
994
995
996 bool
IsDone()997 nsContentIterator::IsDone()
998 {
999 return mIsDone;
1000 }
1001
1002
1003 // Keeping arrays of indexes for the stack of nodes makes PositionAt
1004 // interesting...
1005 nsresult
PositionAt(nsINode * aCurNode)1006 nsContentIterator::PositionAt(nsINode* aCurNode)
1007 {
1008 if (NS_WARN_IF(!aCurNode)) {
1009 return NS_ERROR_NULL_POINTER;
1010 }
1011
1012 nsINode* newCurNode = aCurNode;
1013 nsINode* tempNode = mCurNode;
1014
1015 mCurNode = aCurNode;
1016 // take an early out if this doesn't actually change the position
1017 if (mCurNode == tempNode) {
1018 mIsDone = false; // paranoia
1019 return NS_OK;
1020 }
1021
1022 // Check to see if the node falls within the traversal range.
1023
1024 nsINode* firstNode = mFirst;
1025 nsINode* lastNode = mLast;
1026 int32_t firstOffset = 0, lastOffset = 0;
1027
1028 if (firstNode && lastNode) {
1029 if (mPre) {
1030 firstNode = NodeToParentOffset(mFirst, &firstOffset);
1031 NS_WARNING_ASSERTION(firstNode, "NodeToParentOffset returned null");
1032 NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
1033
1034 if (lastNode->GetChildCount()) {
1035 lastOffset = 0;
1036 } else {
1037 lastNode = NodeToParentOffset(mLast, &lastOffset);
1038 NS_WARNING_ASSERTION(lastNode, "NodeToParentOffset returned null");
1039 NS_WARNING_ASSERTION(lastOffset >= 0, "bad lastOffset");
1040 ++lastOffset;
1041 }
1042 } else {
1043 uint32_t numChildren = firstNode->GetChildCount();
1044
1045 if (numChildren) {
1046 firstOffset = numChildren;
1047 NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
1048 } else {
1049 firstNode = NodeToParentOffset(mFirst, &firstOffset);
1050 NS_WARNING_ASSERTION(firstNode, "NodeToParentOffset returned null");
1051 NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
1052 }
1053
1054 lastNode = NodeToParentOffset(mLast, &lastOffset);
1055 NS_WARNING_ASSERTION(lastNode, "NodeToParentOffset returned null");
1056 NS_WARNING_ASSERTION(lastOffset >= 0, "bad lastOffset");
1057 ++lastOffset;
1058 }
1059 }
1060
1061 // The end positions are always in the range even if it has no parent. We
1062 // need to allow that or 'iter->Init(root)' would assert in Last() or First()
1063 // for example, bug 327694.
1064 if (mFirst != mCurNode && mLast != mCurNode &&
1065 (NS_WARN_IF(!firstNode) || NS_WARN_IF(!lastNode) ||
1066 NS_WARN_IF(!NodeIsInTraversalRange(mCurNode, mPre,
1067 firstNode, firstOffset,
1068 lastNode, lastOffset)))) {
1069 mIsDone = true;
1070 return NS_ERROR_FAILURE;
1071 }
1072
1073 // We can be at ANY node in the sequence. Need to regenerate the array of
1074 // indexes back to the root or common parent!
1075 AutoTArray<nsINode*, 8> oldParentStack;
1076 AutoTArray<int32_t, 8> newIndexes;
1077
1078 // Get a list of the parents up to the root, then compare the new node with
1079 // entries in that array until we find a match (lowest common ancestor). If
1080 // no match, use IndexOf, take the parent, and repeat. This avoids using
1081 // IndexOf() N times on possibly large arrays. We still end up doing it a
1082 // fair bit. It's better to use Clone() if possible.
1083
1084 // we know the depth we're down (though we may not have started at the top).
1085 oldParentStack.SetCapacity(mIndexes.Length() + 1);
1086
1087 // We want to loop mIndexes.Length() + 1 times here, because we want to make
1088 // sure we include mCommonParent in the oldParentStack, for use in the next
1089 // for loop, and mIndexes only has entries for nodes from tempNode up through
1090 // an ancestor of tempNode that's a child of mCommonParent.
1091 for (int32_t i = mIndexes.Length() + 1; i > 0 && tempNode; i--) {
1092 // Insert at head since we're walking up
1093 oldParentStack.InsertElementAt(0, tempNode);
1094
1095 nsINode* parent = tempNode->GetParentNode();
1096
1097 if (NS_WARN_IF(!parent)) {
1098 // this node has no parent, and thus no index
1099 break;
1100 }
1101
1102 if (parent == mCurNode) {
1103 // The position was moved to a parent of the current position. All we
1104 // need to do is drop some indexes. Shortcut here.
1105 mIndexes.RemoveElementsAt(mIndexes.Length() - oldParentStack.Length(),
1106 oldParentStack.Length());
1107 mIsDone = false;
1108 return NS_OK;
1109 }
1110 tempNode = parent;
1111 }
1112
1113 // Ok. We have the array of old parents. Look for a match.
1114 while (newCurNode) {
1115 nsINode* parent = newCurNode->GetParentNode();
1116
1117 if (NS_WARN_IF(!parent)) {
1118 // this node has no parent, and thus no index
1119 break;
1120 }
1121
1122 int32_t indx = parent->IndexOf(newCurNode);
1123 NS_WARNING_ASSERTION(indx >= 0, "bad indx");
1124
1125 // insert at the head!
1126 newIndexes.InsertElementAt(0, indx);
1127
1128 // look to see if the parent is in the stack
1129 indx = oldParentStack.IndexOf(parent);
1130 if (indx >= 0) {
1131 // ok, the parent IS on the old stack! Rework things. We want
1132 // newIndexes to replace all nodes equal to or below the match. Note
1133 // that index oldParentStack.Length() - 1 is the last node, which is one
1134 // BELOW the last index in the mIndexes stack. In other words, we want
1135 // to remove elements starting at index (indx + 1).
1136 int32_t numToDrop = oldParentStack.Length() - (1 + indx);
1137 if (numToDrop > 0) {
1138 mIndexes.RemoveElementsAt(mIndexes.Length() - numToDrop, numToDrop);
1139 }
1140 mIndexes.AppendElements(newIndexes);
1141
1142 break;
1143 }
1144 newCurNode = parent;
1145 }
1146
1147 // phew!
1148
1149 mIsDone = false;
1150 return NS_OK;
1151 }
1152
1153 nsINode*
GetCurrentNode()1154 nsContentIterator::GetCurrentNode()
1155 {
1156 if (mIsDone) {
1157 return nullptr;
1158 }
1159
1160 NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
1161
1162 return mCurNode;
1163 }
1164
1165
1166
1167
1168
1169 /*====================================================================================*/
1170 /*====================================================================================*/
1171
1172
1173
1174
1175
1176
1177 /******************************************************
1178 * nsContentSubtreeIterator
1179 ******************************************************/
1180
1181
1182 /*
1183 * A simple iterator class for traversing the content in "top subtree" order
1184 */
1185 class nsContentSubtreeIterator : public nsContentIterator
1186 {
1187 public:
nsContentSubtreeIterator()1188 nsContentSubtreeIterator() : nsContentIterator(false) {}
1189
1190 NS_DECL_ISUPPORTS_INHERITED
1191 NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1192
1193 // nsContentIterator overrides ------------------------------
1194
1195 virtual nsresult Init(nsINode* aRoot) override;
1196
1197 virtual nsresult Init(nsIDOMRange* aRange) override;
1198
1199 virtual void Next() override;
1200
1201 virtual void Prev() override;
1202
1203 virtual nsresult PositionAt(nsINode* aCurNode) override;
1204
1205 // Must override these because we don't do PositionAt
1206 virtual void First() override;
1207
1208 // Must override these because we don't do PositionAt
1209 virtual void Last() override;
1210
1211 protected:
~nsContentSubtreeIterator()1212 virtual ~nsContentSubtreeIterator() {}
1213
1214 // Returns the highest inclusive ancestor of aNode that's in the range
1215 // (possibly aNode itself). Returns null if aNode is null, or is not itself
1216 // in the range. A node is in the range if (node, 0) comes strictly after
1217 // the range endpoint, and (node, node.length) comes strictly before it, so
1218 // the range's start and end nodes will never be considered "in" it.
1219 nsIContent* GetTopAncestorInRange(nsINode* aNode);
1220
1221 // no copy's or assigns FIX ME
1222 nsContentSubtreeIterator(const nsContentSubtreeIterator&);
1223 nsContentSubtreeIterator& operator=(const nsContentSubtreeIterator&);
1224
1225 virtual void LastRelease() override;
1226
1227 RefPtr<nsRange> mRange;
1228
1229 // these arrays all typically are used and have elements
1230 AutoTArray<nsIContent*, 8> mEndNodes;
1231 AutoTArray<int32_t, 8> mEndOffsets;
1232 };
1233
NS_IMPL_ADDREF_INHERITED(nsContentSubtreeIterator,nsContentIterator)1234 NS_IMPL_ADDREF_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1235 NS_IMPL_RELEASE_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1236
1237 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator)
1238 NS_INTERFACE_MAP_END_INHERITING(nsContentIterator)
1239
1240 NS_IMPL_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator, nsContentIterator,
1241 mRange)
1242
1243 void
1244 nsContentSubtreeIterator::LastRelease()
1245 {
1246 mRange = nullptr;
1247 nsContentIterator::LastRelease();
1248 }
1249
1250 /******************************************************
1251 * repository cruft
1252 ******************************************************/
1253
1254 already_AddRefed<nsIContentIterator>
NS_NewContentSubtreeIterator()1255 NS_NewContentSubtreeIterator()
1256 {
1257 nsCOMPtr<nsIContentIterator> iter = new nsContentSubtreeIterator();
1258 return iter.forget();
1259 }
1260
1261
1262
1263 /******************************************************
1264 * Init routines
1265 ******************************************************/
1266
1267
1268 nsresult
Init(nsINode * aRoot)1269 nsContentSubtreeIterator::Init(nsINode* aRoot)
1270 {
1271 return NS_ERROR_NOT_IMPLEMENTED;
1272 }
1273
1274
1275 nsresult
Init(nsIDOMRange * aRange)1276 nsContentSubtreeIterator::Init(nsIDOMRange* aRange)
1277 {
1278 MOZ_ASSERT(aRange);
1279
1280 mIsDone = false;
1281
1282 mRange = static_cast<nsRange*>(aRange);
1283
1284 // get the start node and offset, convert to nsINode
1285 mCommonParent = mRange->GetCommonAncestor();
1286 nsINode* startParent = mRange->GetStartParent();
1287 int32_t startOffset = mRange->StartOffset();
1288 nsINode* endParent = mRange->GetEndParent();
1289 int32_t endOffset = mRange->EndOffset();
1290 MOZ_ASSERT(mCommonParent && startParent && endParent);
1291 // Bug 767169
1292 MOZ_ASSERT(uint32_t(startOffset) <= startParent->Length() &&
1293 uint32_t(endOffset) <= endParent->Length());
1294
1295 // short circuit when start node == end node
1296 if (startParent == endParent) {
1297 nsINode* child = startParent->GetFirstChild();
1298
1299 if (!child || startOffset == endOffset) {
1300 // Text node, empty container, or collapsed
1301 MakeEmpty();
1302 return NS_OK;
1303 }
1304 }
1305
1306 // cache ancestors
1307 nsContentUtils::GetAncestorsAndOffsets(endParent->AsDOMNode(), endOffset,
1308 &mEndNodes, &mEndOffsets);
1309
1310 nsIContent* firstCandidate = nullptr;
1311 nsIContent* lastCandidate = nullptr;
1312
1313 // find first node in range
1314 int32_t offset = mRange->StartOffset();
1315
1316 nsINode* node = nullptr;
1317 if (!startParent->GetChildCount()) {
1318 // no children, start at the node itself
1319 node = startParent;
1320 } else {
1321 nsIContent* child = startParent->GetChildAt(offset);
1322 if (!child) {
1323 // offset after last child
1324 node = startParent;
1325 } else {
1326 firstCandidate = child;
1327 }
1328 }
1329
1330 if (!firstCandidate) {
1331 // then firstCandidate is next node after node
1332 firstCandidate = GetNextSibling(node);
1333
1334 if (!firstCandidate) {
1335 MakeEmpty();
1336 return NS_OK;
1337 }
1338 }
1339
1340 firstCandidate = GetDeepFirstChild(firstCandidate);
1341
1342 // confirm that this first possible contained node is indeed contained. Else
1343 // we have a range that does not fully contain any node.
1344
1345 bool nodeBefore, nodeAfter;
1346 MOZ_ALWAYS_SUCCEEDS(
1347 nsRange::CompareNodeToRange(firstCandidate, mRange, &nodeBefore, &nodeAfter));
1348
1349 if (nodeBefore || nodeAfter) {
1350 MakeEmpty();
1351 return NS_OK;
1352 }
1353
1354 // cool, we have the first node in the range. Now we walk up its ancestors
1355 // to find the most senior that is still in the range. That's the real first
1356 // node.
1357 mFirst = GetTopAncestorInRange(firstCandidate);
1358
1359 // now to find the last node
1360 offset = mRange->EndOffset();
1361 int32_t numChildren = endParent->GetChildCount();
1362
1363 if (offset > numChildren) {
1364 // Can happen for text nodes
1365 offset = numChildren;
1366 }
1367 if (!offset || !numChildren) {
1368 node = endParent;
1369 } else {
1370 lastCandidate = endParent->GetChildAt(--offset);
1371 NS_ASSERTION(lastCandidate,
1372 "tree traversal trouble in nsContentSubtreeIterator::Init");
1373 }
1374
1375 if (!lastCandidate) {
1376 // then lastCandidate is prev node before node
1377 lastCandidate = GetPrevSibling(node);
1378 }
1379
1380 if (!lastCandidate) {
1381 MakeEmpty();
1382 return NS_OK;
1383 }
1384
1385 lastCandidate = GetDeepLastChild(lastCandidate);
1386
1387 // confirm that this last possible contained node is indeed contained. Else
1388 // we have a range that does not fully contain any node.
1389
1390 MOZ_ALWAYS_SUCCEEDS(
1391 nsRange::CompareNodeToRange(lastCandidate, mRange, &nodeBefore, &nodeAfter));
1392
1393 if (nodeBefore || nodeAfter) {
1394 MakeEmpty();
1395 return NS_OK;
1396 }
1397
1398 // cool, we have the last node in the range. Now we walk up its ancestors to
1399 // find the most senior that is still in the range. That's the real first
1400 // node.
1401 mLast = GetTopAncestorInRange(lastCandidate);
1402
1403 mCurNode = mFirst;
1404
1405 return NS_OK;
1406 }
1407
1408 /****************************************************************
1409 * nsContentSubtreeIterator overrides of ContentIterator routines
1410 ****************************************************************/
1411
1412 // we can't call PositionAt in a subtree iterator...
1413 void
First()1414 nsContentSubtreeIterator::First()
1415 {
1416 mIsDone = mFirst == nullptr;
1417
1418 mCurNode = mFirst;
1419 }
1420
1421 // we can't call PositionAt in a subtree iterator...
1422 void
Last()1423 nsContentSubtreeIterator::Last()
1424 {
1425 mIsDone = mLast == nullptr;
1426
1427 mCurNode = mLast;
1428 }
1429
1430
1431 void
Next()1432 nsContentSubtreeIterator::Next()
1433 {
1434 if (mIsDone || !mCurNode) {
1435 return;
1436 }
1437
1438 if (mCurNode == mLast) {
1439 mIsDone = true;
1440 return;
1441 }
1442
1443 nsINode* nextNode = GetNextSibling(mCurNode);
1444 NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
1445
1446 int32_t i = mEndNodes.IndexOf(nextNode);
1447 while (i != -1) {
1448 // as long as we are finding ancestors of the endpoint of the range,
1449 // dive down into their children
1450 nextNode = nextNode->GetFirstChild();
1451 NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
1452
1453 // should be impossible to get a null pointer. If we went all the way
1454 // down the child chain to the bottom without finding an interior node,
1455 // then the previous node should have been the last, which was
1456 // was tested at top of routine.
1457 i = mEndNodes.IndexOf(nextNode);
1458 }
1459
1460 mCurNode = nextNode;
1461
1462 // This shouldn't be needed, but since our selection code can put us
1463 // in a situation where mLast is in generated content, we need this
1464 // to stop the iterator when we've walked past past the last node!
1465 mIsDone = mCurNode == nullptr;
1466 }
1467
1468
1469 void
Prev()1470 nsContentSubtreeIterator::Prev()
1471 {
1472 // Prev should be optimized to use the mStartNodes, just as Next
1473 // uses mEndNodes.
1474 if (mIsDone || !mCurNode) {
1475 return;
1476 }
1477
1478 if (mCurNode == mFirst) {
1479 mIsDone = true;
1480 return;
1481 }
1482
1483 // If any of these function calls return null, so will all succeeding ones,
1484 // so mCurNode will wind up set to null.
1485 nsINode* prevNode = GetDeepFirstChild(mCurNode);
1486
1487 prevNode = PrevNode(prevNode);
1488
1489 prevNode = GetDeepLastChild(prevNode);
1490
1491 mCurNode = GetTopAncestorInRange(prevNode);
1492
1493 // This shouldn't be needed, but since our selection code can put us
1494 // in a situation where mFirst is in generated content, we need this
1495 // to stop the iterator when we've walked past past the first node!
1496 mIsDone = mCurNode == nullptr;
1497 }
1498
1499
1500 nsresult
PositionAt(nsINode * aCurNode)1501 nsContentSubtreeIterator::PositionAt(nsINode* aCurNode)
1502 {
1503 NS_ERROR("Not implemented!");
1504
1505 return NS_ERROR_NOT_IMPLEMENTED;
1506 }
1507
1508 /****************************************************************
1509 * nsContentSubtreeIterator helper routines
1510 ****************************************************************/
1511
1512 nsIContent*
GetTopAncestorInRange(nsINode * aNode)1513 nsContentSubtreeIterator::GetTopAncestorInRange(nsINode* aNode)
1514 {
1515 if (!aNode || !aNode->GetParentNode()) {
1516 return nullptr;
1517 }
1518
1519 // aNode has a parent, so it must be content.
1520 nsIContent* content = aNode->AsContent();
1521
1522 // sanity check: aNode is itself in the range
1523 bool nodeBefore, nodeAfter;
1524 nsresult res = nsRange::CompareNodeToRange(aNode, mRange,
1525 &nodeBefore, &nodeAfter);
1526 NS_ASSERTION(NS_SUCCEEDED(res) && !nodeBefore && !nodeAfter,
1527 "aNode isn't in mRange, or something else weird happened");
1528 if (NS_FAILED(res) || nodeBefore || nodeAfter) {
1529 return nullptr;
1530 }
1531
1532 while (content) {
1533 nsIContent* parent = content->GetParent();
1534 // content always has a parent. If its parent is the root, however --
1535 // i.e., either it's not content, or it is content but its own parent is
1536 // null -- then we're finished, since we don't go up to the root.
1537 //
1538 // We have to special-case this because CompareNodeToRange treats the root
1539 // node differently -- see bug 765205.
1540 if (!parent || !parent->GetParentNode()) {
1541 return content;
1542 }
1543 MOZ_ALWAYS_SUCCEEDS(
1544 nsRange::CompareNodeToRange(parent, mRange, &nodeBefore, &nodeAfter));
1545
1546 if (nodeBefore || nodeAfter) {
1547 return content;
1548 }
1549 content = parent;
1550 }
1551
1552 MOZ_CRASH("This should only be possible if aNode was null");
1553 }
1554