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 "ContentIterator.h"
8
9 #include "mozilla/DebugOnly.h"
10 #include "mozilla/RangeBoundary.h"
11 #include "mozilla/RangeUtils.h"
12
13 #include "nsContentUtils.h"
14 #include "nsElementTable.h"
15 #include "nsIContent.h"
16 #include "nsRange.h"
17
18 namespace mozilla {
19
ComparePostMode(const RawRangeBoundary & aStart,const RawRangeBoundary & aEnd,nsINode & aNode)20 static bool ComparePostMode(const RawRangeBoundary& aStart,
21 const RawRangeBoundary& aEnd, nsINode& aNode) {
22 nsINode* parent = aNode.GetParentNode();
23 if (!parent) {
24 return false;
25 }
26
27 // aNode should always be content, as we have a parent, but let's just be
28 // extra careful and check.
29 nsIContent* content =
30 NS_WARN_IF(!aNode.IsContent()) ? nullptr : aNode.AsContent();
31
32 // Post mode: start < node <= end.
33 RawRangeBoundary afterNode(parent, content);
34 const auto isStartLessThanAfterNode = [&]() {
35 const Maybe<int32_t> startComparedToAfterNode =
36 nsContentUtils::ComparePoints(aStart, afterNode);
37 return !NS_WARN_IF(!startComparedToAfterNode) &&
38 (*startComparedToAfterNode < 0);
39 };
40
41 const auto isAfterNodeLessOrEqualToEnd = [&]() {
42 const Maybe<int32_t> afterNodeComparedToEnd =
43 nsContentUtils::ComparePoints(afterNode, aEnd);
44 return !NS_WARN_IF(!afterNodeComparedToEnd) &&
45 (*afterNodeComparedToEnd <= 0);
46 };
47
48 return isStartLessThanAfterNode() && isAfterNodeLessOrEqualToEnd();
49 }
50
ComparePreMode(const RawRangeBoundary & aStart,const RawRangeBoundary & aEnd,nsINode & aNode)51 static bool ComparePreMode(const RawRangeBoundary& aStart,
52 const RawRangeBoundary& aEnd, nsINode& aNode) {
53 nsINode* parent = aNode.GetParentNode();
54 if (!parent) {
55 return false;
56 }
57
58 // Pre mode: start <= node < end.
59 RawRangeBoundary beforeNode(parent, aNode.GetPreviousSibling());
60
61 const auto isStartLessOrEqualToBeforeNode = [&]() {
62 const Maybe<int32_t> startComparedToBeforeNode =
63 nsContentUtils::ComparePoints(aStart, beforeNode);
64 return !NS_WARN_IF(!startComparedToBeforeNode) &&
65 (*startComparedToBeforeNode <= 0);
66 };
67
68 const auto isBeforeNodeLessThanEndNode = [&]() {
69 const Maybe<int32_t> beforeNodeComparedToEnd =
70 nsContentUtils::ComparePoints(beforeNode, aEnd);
71 return !NS_WARN_IF(!beforeNodeComparedToEnd) &&
72 (*beforeNodeComparedToEnd < 0);
73 };
74
75 return isStartLessOrEqualToBeforeNode() && isBeforeNodeLessThanEndNode();
76 }
77
78 ///////////////////////////////////////////////////////////////////////////
79 // NodeIsInTraversalRange: returns true if content is visited during
80 // the traversal of the range in the specified mode.
81 //
NodeIsInTraversalRange(nsINode * aNode,bool aIsPreMode,const RawRangeBoundary & aStart,const RawRangeBoundary & aEnd)82 static bool NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode,
83 const RawRangeBoundary& aStart,
84 const RawRangeBoundary& aEnd) {
85 if (NS_WARN_IF(!aStart.IsSet()) || NS_WARN_IF(!aEnd.IsSet()) ||
86 NS_WARN_IF(!aNode)) {
87 return false;
88 }
89
90 // If a leaf node contains an end point of the traversal range, it is
91 // always in the traversal range.
92 if (aNode == aStart.Container() || aNode == aEnd.Container()) {
93 if (aNode->IsCharacterData()) {
94 return true; // text node or something
95 }
96 if (!aNode->HasChildren()) {
97 MOZ_ASSERT(
98 aNode != aStart.Container() || aStart.IsStartOfContainer(),
99 "aStart.Container() doesn't have children and not a data node, "
100 "aStart should be at the beginning of its container");
101 MOZ_ASSERT(aNode != aEnd.Container() || aEnd.IsStartOfContainer(),
102 "aEnd.Container() doesn't have children and not a data node, "
103 "aEnd should be at the beginning of its container");
104 return true;
105 }
106 }
107
108 if (aIsPreMode) {
109 return ComparePreMode(aStart, aEnd, *aNode);
110 }
111
112 return ComparePostMode(aStart, aEnd, *aNode);
113 }
114
ContentIteratorBase(bool aPre)115 ContentIteratorBase::ContentIteratorBase(bool aPre)
116 : mIsDone(false), mPre(aPre) {}
117
118 /******************************************************
119 * Init routines
120 ******************************************************/
121
Init(nsINode * aRoot)122 nsresult ContentIteratorBase::Init(nsINode* aRoot) {
123 if (NS_WARN_IF(!aRoot)) {
124 return NS_ERROR_NULL_POINTER;
125 }
126
127 mIsDone = false;
128
129 if (mPre) {
130 mFirst = aRoot;
131 mLast = GetDeepLastChild(aRoot);
132 NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
133 } else {
134 mFirst = GetDeepFirstChild(aRoot);
135 NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
136 mLast = aRoot;
137 }
138
139 mCommonParent = aRoot;
140 mCurNode = mFirst;
141 return NS_OK;
142 }
143
Init(nsRange * aRange)144 nsresult ContentIteratorBase::Init(nsRange* aRange) {
145 mIsDone = false;
146
147 if (NS_WARN_IF(!aRange)) {
148 return NS_ERROR_INVALID_ARG;
149 }
150
151 if (NS_WARN_IF(!aRange->IsPositioned())) {
152 return NS_ERROR_INVALID_ARG;
153 }
154
155 return InitInternal(aRange->StartRef().AsRaw(), aRange->EndRef().AsRaw());
156 }
157
Init(nsINode * aStartContainer,uint32_t aStartOffset,nsINode * aEndContainer,uint32_t aEndOffset)158 nsresult ContentIteratorBase::Init(nsINode* aStartContainer,
159 uint32_t aStartOffset,
160 nsINode* aEndContainer,
161 uint32_t aEndOffset) {
162 mIsDone = false;
163
164 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStartContainer, aStartOffset,
165 aEndContainer, aEndOffset))) {
166 return NS_ERROR_INVALID_ARG;
167 }
168
169 return InitInternal(RawRangeBoundary(aStartContainer, aStartOffset),
170 RawRangeBoundary(aEndContainer, aEndOffset));
171 }
172
Init(const RawRangeBoundary & aStart,const RawRangeBoundary & aEnd)173 nsresult ContentIteratorBase::Init(const RawRangeBoundary& aStart,
174 const RawRangeBoundary& aEnd) {
175 mIsDone = false;
176
177 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStart, aEnd))) {
178 return NS_ERROR_INVALID_ARG;
179 }
180
181 return InitInternal(aStart, aEnd);
182 }
183
InitInternal(const RawRangeBoundary & aStart,const RawRangeBoundary & aEnd)184 nsresult ContentIteratorBase::InitInternal(const RawRangeBoundary& aStart,
185 const RawRangeBoundary& aEnd) {
186 // get common content parent
187 mCommonParent = nsContentUtils::GetClosestCommonInclusiveAncestor(
188 aStart.Container(), aEnd.Container());
189 if (NS_WARN_IF(!mCommonParent)) {
190 return NS_ERROR_FAILURE;
191 }
192
193 bool startIsData = aStart.Container()->IsCharacterData();
194
195 // Check to see if we have a collapsed range, if so, there is nothing to
196 // iterate over.
197 //
198 // XXX: CharacterDataNodes (text nodes) are currently an exception, since
199 // we always want to be able to iterate text nodes at the end points
200 // of a range.
201
202 if (!startIsData && aStart == aEnd) {
203 MakeEmpty();
204 return NS_OK;
205 }
206
207 // Handle ranges within a single character data node.
208 if (startIsData && aStart.Container() == aEnd.Container()) {
209 mFirst = aStart.Container()->AsContent();
210 mLast = mFirst;
211 mCurNode = mFirst;
212
213 return NS_OK;
214 }
215
216 // Find first node in range.
217
218 nsIContent* cChild = nullptr;
219
220 // Try to get the child at our starting point. This might return null if
221 // aStart is immediately after the last node in aStart.Container().
222 if (!startIsData) {
223 cChild = aStart.GetChildAtOffset();
224 }
225
226 if (!cChild) {
227 // No children (possibly a <br> or text node), or index is after last child.
228
229 if (mPre) {
230 // XXX: In the future, if start offset is after the last
231 // character in the cdata node, should we set mFirst to
232 // the next sibling?
233
234 // Normally we would skip the start node because the start node is outside
235 // of the range in pre mode. However, if aStartOffset == 0, and the node
236 // is a non-container node (e.g. <br>), we don't skip the node in this
237 // case in order to address bug 1215798.
238 bool startIsContainer = true;
239 if (aStart.Container()->IsHTMLElement()) {
240 nsAtom* name = aStart.Container()->NodeInfo()->NameAtom();
241 startIsContainer =
242 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name));
243 }
244 if (!startIsData && (startIsContainer || !aStart.IsStartOfContainer())) {
245 mFirst = GetNextSibling(aStart.Container());
246 NS_WARNING_ASSERTION(mFirst, "GetNextSibling returned null");
247
248 // Does mFirst node really intersect the range? The range could be
249 // 'degenerate', i.e., not collapsed but still contain no content.
250 if (mFirst &&
251 NS_WARN_IF(!NodeIsInTraversalRange(mFirst, mPre, aStart, aEnd))) {
252 mFirst = nullptr;
253 }
254 } else {
255 mFirst = aStart.Container()->AsContent();
256 }
257 } else {
258 // post-order
259 if (NS_WARN_IF(!aStart.Container()->IsContent())) {
260 // What else can we do?
261 mFirst = nullptr;
262 } else {
263 mFirst = aStart.Container()->AsContent();
264 }
265 }
266 } else {
267 if (mPre) {
268 mFirst = cChild;
269 } else {
270 // post-order
271 mFirst = GetDeepFirstChild(cChild);
272 NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
273
274 // Does mFirst node really intersect the range? The range could be
275 // 'degenerate', i.e., not collapsed but still contain no content.
276
277 if (mFirst && !NodeIsInTraversalRange(mFirst, mPre, aStart, aEnd)) {
278 mFirst = nullptr;
279 }
280 }
281 }
282
283 // Find last node in range.
284
285 bool endIsData = aEnd.Container()->IsCharacterData();
286
287 if (endIsData || !aEnd.Container()->HasChildren() ||
288 aEnd.IsStartOfContainer()) {
289 if (mPre) {
290 if (NS_WARN_IF(!aEnd.Container()->IsContent())) {
291 // Not much else to do here...
292 mLast = nullptr;
293 } else {
294 // If the end node is a non-container element and the end offset is 0,
295 // the last element should be the previous node (i.e., shouldn't
296 // include the end node in the range).
297 bool endIsContainer = true;
298 if (aEnd.Container()->IsHTMLElement()) {
299 nsAtom* name = aEnd.Container()->NodeInfo()->NameAtom();
300 endIsContainer =
301 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name));
302 }
303 if (!endIsData && !endIsContainer && aEnd.IsStartOfContainer()) {
304 mLast = PrevNode(aEnd.Container());
305 NS_WARNING_ASSERTION(mLast, "PrevNode returned null");
306 if (mLast && mLast != mFirst &&
307 NS_WARN_IF(!NodeIsInTraversalRange(
308 mLast, mPre, RawRangeBoundary(mFirst, 0u), aEnd))) {
309 mLast = nullptr;
310 }
311 } else {
312 mLast = aEnd.Container()->AsContent();
313 }
314 }
315 } else {
316 // post-order
317 //
318 // XXX: In the future, if end offset is before the first character in the
319 // cdata node, should we set mLast to the prev sibling?
320
321 if (!endIsData) {
322 mLast = GetPrevSibling(aEnd.Container());
323 NS_WARNING_ASSERTION(mLast, "GetPrevSibling returned null");
324
325 if (!NodeIsInTraversalRange(mLast, mPre, aStart, aEnd)) {
326 mLast = nullptr;
327 }
328 } else {
329 mLast = aEnd.Container()->AsContent();
330 }
331 }
332 } else {
333 cChild = aEnd.Ref();
334
335 if (NS_WARN_IF(!cChild)) {
336 // No child at offset!
337 MOZ_ASSERT_UNREACHABLE("ContentIterator::ContentIterator");
338 return NS_ERROR_FAILURE;
339 }
340
341 if (mPre) {
342 mLast = GetDeepLastChild(cChild);
343 NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
344
345 if (NS_WARN_IF(!NodeIsInTraversalRange(mLast, mPre, aStart, aEnd))) {
346 mLast = nullptr;
347 }
348 } else {
349 // post-order
350 mLast = cChild;
351 }
352 }
353
354 // If either first or last is null, they both have to be null!
355
356 if (!mFirst || !mLast) {
357 mFirst = nullptr;
358 mLast = nullptr;
359 }
360
361 mCurNode = mFirst;
362 mIsDone = !mCurNode;
363
364 return NS_OK;
365 }
366
MakeEmpty()367 void ContentIteratorBase::MakeEmpty() {
368 mCurNode = nullptr;
369 mFirst = nullptr;
370 mLast = nullptr;
371 mCommonParent = nullptr;
372 mIsDone = true;
373 }
374
GetDeepFirstChild(nsINode * aRoot)375 nsINode* ContentIteratorBase::GetDeepFirstChild(nsINode* aRoot) {
376 if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
377 return aRoot;
378 }
379
380 return GetDeepFirstChild(aRoot->GetFirstChild());
381 }
382
GetDeepFirstChild(nsIContent * aRoot)383 nsIContent* ContentIteratorBase::GetDeepFirstChild(nsIContent* aRoot) {
384 if (NS_WARN_IF(!aRoot)) {
385 return nullptr;
386 }
387
388 nsIContent* node = aRoot;
389 nsIContent* child = node->GetFirstChild();
390
391 while (child) {
392 node = child;
393 child = node->GetFirstChild();
394 }
395
396 return node;
397 }
398
GetDeepLastChild(nsINode * aRoot)399 nsINode* ContentIteratorBase::GetDeepLastChild(nsINode* aRoot) {
400 if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
401 return aRoot;
402 }
403
404 return GetDeepLastChild(aRoot->GetLastChild());
405 }
406
GetDeepLastChild(nsIContent * aRoot)407 nsIContent* ContentIteratorBase::GetDeepLastChild(nsIContent* aRoot) {
408 if (NS_WARN_IF(!aRoot)) {
409 return nullptr;
410 }
411
412 nsIContent* node = aRoot;
413 while (node->HasChildren()) {
414 nsIContent* child = node->GetLastChild();
415 node = child;
416 }
417 return node;
418 }
419
420 // Get the next sibling, or parent's next sibling, or grandpa's next sibling...
GetNextSibling(nsINode * aNode)421 nsIContent* ContentIteratorBase::GetNextSibling(nsINode* aNode) {
422 if (NS_WARN_IF(!aNode)) {
423 return nullptr;
424 }
425
426 if (aNode->GetNextSibling()) {
427 return aNode->GetNextSibling();
428 }
429
430 nsINode* parent = aNode->GetParentNode();
431 if (NS_WARN_IF(!parent)) {
432 return nullptr;
433 }
434
435 // XXX This is a hack to preserve previous behaviour: This should be fixed
436 // in bug 1404916. If we were positioned on anonymous content, move to
437 // the first child of our parent.
438 if (parent->GetLastChild() && parent->GetLastChild() != aNode) {
439 return parent->GetFirstChild();
440 }
441
442 return GetNextSibling(parent);
443 }
444
445 // Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
GetPrevSibling(nsINode * aNode)446 nsIContent* ContentIteratorBase::GetPrevSibling(nsINode* aNode) {
447 if (NS_WARN_IF(!aNode)) {
448 return nullptr;
449 }
450
451 if (aNode->GetPreviousSibling()) {
452 return aNode->GetPreviousSibling();
453 }
454
455 nsINode* parent = aNode->GetParentNode();
456 if (NS_WARN_IF(!parent)) {
457 return nullptr;
458 }
459
460 // XXX This is a hack to preserve previous behaviour: This should be fixed
461 // in bug 1404916. If we were positioned on anonymous content, move to
462 // the last child of our parent.
463 if (parent->GetFirstChild() && parent->GetFirstChild() != aNode) {
464 return parent->GetLastChild();
465 }
466
467 return GetPrevSibling(parent);
468 }
469
NextNode(nsINode * aNode)470 nsINode* ContentIteratorBase::NextNode(nsINode* aNode) {
471 nsINode* node = aNode;
472
473 // if we are a Pre-order iterator, use pre-order
474 if (mPre) {
475 // if it has children then next node is first child
476 if (node->HasChildren()) {
477 nsIContent* firstChild = node->GetFirstChild();
478 MOZ_ASSERT(firstChild);
479
480 return firstChild;
481 }
482
483 // else next sibling is next
484 return GetNextSibling(node);
485 }
486
487 // post-order
488 nsINode* parent = node->GetParentNode();
489 if (NS_WARN_IF(!parent)) {
490 MOZ_ASSERT(parent, "The node is the root node but not the last node");
491 mIsDone = true;
492 return node;
493 }
494
495 nsIContent* sibling = node->GetNextSibling();
496 if (sibling) {
497 // next node is sibling's "deep left" child
498 return GetDeepFirstChild(sibling);
499 }
500
501 return parent;
502 }
503
PrevNode(nsINode * aNode)504 nsINode* ContentIteratorBase::PrevNode(nsINode* aNode) {
505 nsINode* node = aNode;
506
507 // if we are a Pre-order iterator, use pre-order
508 if (mPre) {
509 nsINode* parent = node->GetParentNode();
510 if (NS_WARN_IF(!parent)) {
511 MOZ_ASSERT(parent, "The node is the root node but not the first node");
512 mIsDone = true;
513 return aNode;
514 }
515
516 nsIContent* sibling = node->GetPreviousSibling();
517 if (sibling) {
518 return GetDeepLastChild(sibling);
519 }
520
521 return parent;
522 }
523
524 // post-order
525 if (node->HasChildren()) {
526 return node->GetLastChild();
527 }
528
529 // else prev sibling is previous
530 return GetPrevSibling(node);
531 }
532
533 /******************************************************
534 * ContentIteratorBase routines
535 ******************************************************/
536
First()537 void ContentIteratorBase::First() {
538 if (mFirst) {
539 mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst);
540 NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
541 }
542
543 mIsDone = mFirst == nullptr;
544 }
545
Last()546 void ContentIteratorBase::Last() {
547 // Note that mLast can be nullptr if MakeEmpty() is called in Init() since
548 // at that time, Init() returns NS_OK.
549 if (!mLast) {
550 MOZ_ASSERT(mIsDone);
551 return;
552 }
553
554 mozilla::DebugOnly<nsresult> rv = PositionAt(mLast);
555 NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
556
557 mIsDone = mLast == nullptr;
558 }
559
Next()560 void ContentIteratorBase::Next() {
561 if (mIsDone || NS_WARN_IF(!mCurNode)) {
562 return;
563 }
564
565 if (mCurNode == mLast) {
566 mIsDone = true;
567 return;
568 }
569
570 mCurNode = NextNode(mCurNode);
571 }
572
Prev()573 void ContentIteratorBase::Prev() {
574 if (NS_WARN_IF(mIsDone) || NS_WARN_IF(!mCurNode)) {
575 return;
576 }
577
578 if (mCurNode == mFirst) {
579 mIsDone = true;
580 return;
581 }
582
583 mCurNode = PrevNode(mCurNode);
584 }
585
IsDone()586 bool ContentIteratorBase::IsDone() { return mIsDone; }
587
588 // Keeping arrays of indexes for the stack of nodes makes PositionAt
589 // interesting...
PositionAt(nsINode * aCurNode)590 nsresult ContentIteratorBase::PositionAt(nsINode* aCurNode) {
591 if (NS_WARN_IF(!aCurNode)) {
592 return NS_ERROR_NULL_POINTER;
593 }
594
595 // take an early out if this doesn't actually change the position
596 if (mCurNode == aCurNode) {
597 mIsDone = false;
598 return NS_OK;
599 }
600 mCurNode = aCurNode;
601
602 // Check to see if the node falls within the traversal range.
603
604 RawRangeBoundary first(mFirst, 0u);
605 RawRangeBoundary last(mLast, 0u);
606
607 if (mFirst && mLast) {
608 if (mPre) {
609 // In pre we want to record the point immediately before mFirst, which is
610 // the point immediately after mFirst's previous sibling.
611 first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()};
612
613 // If mLast has no children, then we want to make sure to include it.
614 if (!mLast->HasChildren()) {
615 last = {mLast->GetParentNode(), mLast->AsContent()};
616 }
617 } else {
618 // If the first node has any children, we want to be immediately after the
619 // last. Otherwise we want to be immediately before mFirst.
620 if (mFirst->HasChildren()) {
621 first = {mFirst, mFirst->GetLastChild()};
622 } else {
623 first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()};
624 }
625
626 // Set the last point immediately after the final node.
627 last = {mLast->GetParentNode(), mLast->AsContent()};
628 }
629 }
630
631 NS_WARNING_ASSERTION(first.IsSetAndValid(), "first is not valid");
632 NS_WARNING_ASSERTION(last.IsSetAndValid(), "last is not valid");
633
634 // The end positions are always in the range even if it has no parent. We
635 // need to allow that or 'iter->Init(root)' would assert in Last() or First()
636 // for example, bug 327694.
637 if (mFirst != mCurNode && mLast != mCurNode &&
638 (NS_WARN_IF(!first.IsSet()) || NS_WARN_IF(!last.IsSet()) ||
639 NS_WARN_IF(!NodeIsInTraversalRange(mCurNode, mPre, first, last)))) {
640 mIsDone = true;
641 return NS_ERROR_FAILURE;
642 }
643
644 mIsDone = false;
645 return NS_OK;
646 }
647
GetCurrentNode()648 nsINode* ContentIteratorBase::GetCurrentNode() {
649 if (mIsDone) {
650 return nullptr;
651 }
652
653 NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
654
655 return mCurNode;
656 }
657
658 /******************************************************
659 * ContentSubtreeIterator init routines
660 ******************************************************/
661
Init(nsINode * aRoot)662 nsresult ContentSubtreeIterator::Init(nsINode* aRoot) {
663 return NS_ERROR_NOT_IMPLEMENTED;
664 }
665
Init(nsRange * aRange)666 nsresult ContentSubtreeIterator::Init(nsRange* aRange) {
667 MOZ_ASSERT(aRange);
668
669 mIsDone = false;
670
671 if (NS_WARN_IF(!aRange->IsPositioned())) {
672 return NS_ERROR_INVALID_ARG;
673 }
674
675 mRange = aRange;
676
677 return InitWithRange();
678 }
679
Init(nsINode * aStartContainer,uint32_t aStartOffset,nsINode * aEndContainer,uint32_t aEndOffset)680 nsresult ContentSubtreeIterator::Init(nsINode* aStartContainer,
681 uint32_t aStartOffset,
682 nsINode* aEndContainer,
683 uint32_t aEndOffset) {
684 return Init(RawRangeBoundary(aStartContainer, aStartOffset),
685 RawRangeBoundary(aEndContainer, aEndOffset));
686 }
687
Init(const RawRangeBoundary & aStartBoundary,const RawRangeBoundary & aEndBoundary)688 nsresult ContentSubtreeIterator::Init(const RawRangeBoundary& aStartBoundary,
689 const RawRangeBoundary& aEndBoundary) {
690 mIsDone = false;
691
692 RefPtr<nsRange> range =
693 nsRange::Create(aStartBoundary, aEndBoundary, IgnoreErrors());
694 if (NS_WARN_IF(!range) || NS_WARN_IF(!range->IsPositioned())) {
695 return NS_ERROR_INVALID_ARG;
696 }
697
698 if (NS_WARN_IF(range->StartRef() != aStartBoundary) ||
699 NS_WARN_IF(range->EndRef() != aEndBoundary)) {
700 return NS_ERROR_UNEXPECTED;
701 }
702
703 mRange = std::move(range);
704
705 return InitWithRange();
706 }
707
InitWithRange()708 nsresult ContentSubtreeIterator::InitWithRange() {
709 MOZ_ASSERT(mRange);
710 MOZ_ASSERT(mRange->IsPositioned());
711
712 // get the start node and offset, convert to nsINode
713 mCommonParent = mRange->GetClosestCommonInclusiveAncestor();
714 nsINode* startContainer = mRange->GetStartContainer();
715 int32_t startOffset = mRange->StartOffset();
716 nsINode* endContainer = mRange->GetEndContainer();
717 int32_t endOffset = mRange->EndOffset();
718 MOZ_ASSERT(mCommonParent && startContainer && endContainer);
719 // Bug 767169
720 MOZ_ASSERT(uint32_t(startOffset) <= startContainer->Length() &&
721 uint32_t(endOffset) <= endContainer->Length());
722
723 // short circuit when start node == end node
724 if (startContainer == endContainer) {
725 nsINode* child = startContainer->GetFirstChild();
726
727 if (!child || startOffset == endOffset) {
728 // Text node, empty container, or collapsed
729 MakeEmpty();
730 return NS_OK;
731 }
732 }
733
734 // cache ancestors
735 mEndNodes.Clear();
736 nsIContent* endNode =
737 endContainer->IsContent() ? endContainer->AsContent() : nullptr;
738 while (endNode) {
739 mEndNodes.AppendElement(endNode);
740 endNode = endNode->GetParent();
741 }
742
743 nsIContent* firstCandidate = nullptr;
744 nsIContent* lastCandidate = nullptr;
745
746 // find first node in range
747 int32_t offset = mRange->StartOffset();
748
749 nsINode* node = nullptr;
750 if (!startContainer->GetChildCount()) {
751 // no children, start at the node itself
752 node = startContainer;
753 } else {
754 nsIContent* child = mRange->GetChildAtStartOffset();
755 MOZ_ASSERT(child == startContainer->GetChildAt_Deprecated(offset));
756 if (!child) {
757 // offset after last child
758 node = startContainer;
759 } else {
760 firstCandidate = child;
761 }
762 }
763
764 if (!firstCandidate) {
765 // then firstCandidate is next node after node
766 firstCandidate = GetNextSibling(node);
767
768 if (!firstCandidate) {
769 MakeEmpty();
770 return NS_OK;
771 }
772 }
773
774 firstCandidate = GetDeepFirstChild(firstCandidate);
775
776 // confirm that this first possible contained node is indeed contained. Else
777 // we have a range that does not fully contain any node.
778
779 bool nodeBefore, nodeAfter;
780 MOZ_ALWAYS_SUCCEEDS(RangeUtils::CompareNodeToRange(firstCandidate, mRange,
781 &nodeBefore, &nodeAfter));
782
783 if (nodeBefore || nodeAfter) {
784 MakeEmpty();
785 return NS_OK;
786 }
787
788 // cool, we have the first node in the range. Now we walk up its ancestors
789 // to find the most senior that is still in the range. That's the real first
790 // node.
791 mFirst = GetTopAncestorInRange(firstCandidate);
792
793 // now to find the last node
794 offset = mRange->EndOffset();
795 int32_t numChildren = endContainer->GetChildCount();
796
797 if (offset > numChildren) {
798 // Can happen for text nodes
799 offset = numChildren;
800 }
801 if (!offset || !numChildren) {
802 node = endContainer;
803 } else {
804 lastCandidate = mRange->EndRef().Ref();
805 MOZ_ASSERT(lastCandidate == endContainer->GetChildAt_Deprecated(--offset));
806 NS_ASSERTION(lastCandidate,
807 "tree traversal trouble in ContentSubtreeIterator::Init");
808 }
809
810 if (!lastCandidate) {
811 // then lastCandidate is prev node before node
812 lastCandidate = GetPrevSibling(node);
813 }
814
815 if (!lastCandidate) {
816 MakeEmpty();
817 return NS_OK;
818 }
819
820 lastCandidate = GetDeepLastChild(lastCandidate);
821
822 // confirm that this last possible contained node is indeed contained. Else
823 // we have a range that does not fully contain any node.
824
825 MOZ_ALWAYS_SUCCEEDS(RangeUtils::CompareNodeToRange(lastCandidate, mRange,
826 &nodeBefore, &nodeAfter));
827
828 if (nodeBefore || nodeAfter) {
829 MakeEmpty();
830 return NS_OK;
831 }
832
833 // cool, we have the last node in the range. Now we walk up its ancestors to
834 // find the most senior that is still in the range. That's the real first
835 // node.
836 mLast = GetTopAncestorInRange(lastCandidate);
837
838 mCurNode = mFirst;
839
840 return NS_OK;
841 }
842
843 /****************************************************************
844 * ContentSubtreeIterator overrides of ContentIterator routines
845 ****************************************************************/
846
847 // we can't call PositionAt in a subtree iterator...
First()848 void ContentSubtreeIterator::First() {
849 mIsDone = mFirst == nullptr;
850
851 mCurNode = mFirst;
852 }
853
854 // we can't call PositionAt in a subtree iterator...
Last()855 void ContentSubtreeIterator::Last() {
856 mIsDone = mLast == nullptr;
857
858 mCurNode = mLast;
859 }
860
Next()861 void ContentSubtreeIterator::Next() {
862 if (mIsDone || !mCurNode) {
863 return;
864 }
865
866 if (mCurNode == mLast) {
867 mIsDone = true;
868 return;
869 }
870
871 nsINode* nextNode = GetNextSibling(mCurNode);
872 NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
873
874 int32_t i = mEndNodes.IndexOf(nextNode);
875 while (i != -1) {
876 // as long as we are finding ancestors of the endpoint of the range,
877 // dive down into their children
878 nextNode = nextNode->GetFirstChild();
879 NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
880
881 // should be impossible to get a null pointer. If we went all the way
882 // down the child chain to the bottom without finding an interior node,
883 // then the previous node should have been the last, which was
884 // was tested at top of routine.
885 i = mEndNodes.IndexOf(nextNode);
886 }
887
888 mCurNode = nextNode;
889
890 // This shouldn't be needed, but since our selection code can put us
891 // in a situation where mLast is in generated content, we need this
892 // to stop the iterator when we've walked past past the last node!
893 mIsDone = mCurNode == nullptr;
894 }
895
Prev()896 void ContentSubtreeIterator::Prev() {
897 // Prev should be optimized to use the mStartNodes, just as Next
898 // uses mEndNodes.
899 if (mIsDone || !mCurNode) {
900 return;
901 }
902
903 if (mCurNode == mFirst) {
904 mIsDone = true;
905 return;
906 }
907
908 // If any of these function calls return null, so will all succeeding ones,
909 // so mCurNode will wind up set to null.
910 nsINode* prevNode = GetDeepFirstChild(mCurNode);
911
912 prevNode = PrevNode(prevNode);
913
914 prevNode = GetDeepLastChild(prevNode);
915
916 mCurNode = GetTopAncestorInRange(prevNode);
917
918 // This shouldn't be needed, but since our selection code can put us
919 // in a situation where mFirst is in generated content, we need this
920 // to stop the iterator when we've walked past past the first node!
921 mIsDone = mCurNode == nullptr;
922 }
923
PositionAt(nsINode * aCurNode)924 nsresult ContentSubtreeIterator::PositionAt(nsINode* aCurNode) {
925 NS_ERROR("Not implemented!");
926
927 return NS_ERROR_NOT_IMPLEMENTED;
928 }
929
930 /****************************************************************
931 * ContentSubtreeIterator helper routines
932 ****************************************************************/
933
GetTopAncestorInRange(nsINode * aNode)934 nsIContent* ContentSubtreeIterator::GetTopAncestorInRange(nsINode* aNode) {
935 if (!aNode || !aNode->GetParentNode()) {
936 return nullptr;
937 }
938
939 // aNode has a parent, so it must be content.
940 nsIContent* content = aNode->AsContent();
941
942 // sanity check: aNode is itself in the range
943 bool nodeBefore, nodeAfter;
944 nsresult res =
945 RangeUtils::CompareNodeToRange(aNode, mRange, &nodeBefore, &nodeAfter);
946 NS_ASSERTION(NS_SUCCEEDED(res) && !nodeBefore && !nodeAfter,
947 "aNode isn't in mRange, or something else weird happened");
948 if (NS_FAILED(res) || nodeBefore || nodeAfter) {
949 return nullptr;
950 }
951
952 while (content) {
953 nsIContent* parent = content->GetParent();
954 // content always has a parent. If its parent is the root, however --
955 // i.e., either it's not content, or it is content but its own parent is
956 // null -- then we're finished, since we don't go up to the root.
957 //
958 // We have to special-case this because CompareNodeToRange treats the root
959 // node differently -- see bug 765205.
960 if (!parent || !parent->GetParentNode()) {
961 return content;
962 }
963 MOZ_ALWAYS_SUCCEEDS(RangeUtils::CompareNodeToRange(
964 parent, mRange, &nodeBefore, &nodeAfter));
965
966 if (nodeBefore || nodeAfter) {
967 return content;
968 }
969 content = parent;
970 }
971
972 MOZ_CRASH("This should only be possible if aNode was null");
973 }
974
975 } // namespace mozilla
976