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/. */
7 #include "ContentIterator.h"
9 #include "mozilla/DebugOnly.h"
10 #include "mozilla/RangeBoundary.h"
11 #include "mozilla/RangeUtils.h"
12 #include "mozilla/Result.h"
14 #include "nsContentUtils.h"
15 #include "nsElementTable.h"
16 #include "nsIContent.h"
23 static bool ComparePostMode(const RawRangeBoundary
& aStart
,
24 const RawRangeBoundary
& aEnd
, nsINode
& aNode
) {
25 nsINode
* parent
= aNode
.GetParentNode();
30 // aNode should always be content, as we have a parent, but let's just be
31 // extra careful and check.
33 NS_WARN_IF(!aNode
.IsContent()) ? nullptr : aNode
.AsContent();
35 // Post mode: start < node <= end.
36 RawRangeBoundary
afterNode(parent
, content
);
37 const auto isStartLessThanAfterNode
= [&]() {
38 const Maybe
<int32_t> startComparedToAfterNode
=
39 nsContentUtils::ComparePoints(aStart
, afterNode
);
40 return !NS_WARN_IF(!startComparedToAfterNode
) &&
41 (*startComparedToAfterNode
< 0);
44 const auto isAfterNodeLessOrEqualToEnd
= [&]() {
45 const Maybe
<int32_t> afterNodeComparedToEnd
=
46 nsContentUtils::ComparePoints(afterNode
, aEnd
);
47 return !NS_WARN_IF(!afterNodeComparedToEnd
) &&
48 (*afterNodeComparedToEnd
<= 0);
51 return isStartLessThanAfterNode() && isAfterNodeLessOrEqualToEnd();
54 static bool ComparePreMode(const RawRangeBoundary
& aStart
,
55 const RawRangeBoundary
& aEnd
, nsINode
& aNode
) {
56 nsINode
* parent
= aNode
.GetParentNode();
61 // Pre mode: start <= node < end.
62 RawRangeBoundary
beforeNode(parent
, aNode
.GetPreviousSibling());
64 const auto isStartLessOrEqualToBeforeNode
= [&]() {
65 const Maybe
<int32_t> startComparedToBeforeNode
=
66 nsContentUtils::ComparePoints(aStart
, beforeNode
);
67 return !NS_WARN_IF(!startComparedToBeforeNode
) &&
68 (*startComparedToBeforeNode
<= 0);
71 const auto isBeforeNodeLessThanEndNode
= [&]() {
72 const Maybe
<int32_t> beforeNodeComparedToEnd
=
73 nsContentUtils::ComparePoints(beforeNode
, aEnd
);
74 return !NS_WARN_IF(!beforeNodeComparedToEnd
) &&
75 (*beforeNodeComparedToEnd
< 0);
78 return isStartLessOrEqualToBeforeNode() && isBeforeNodeLessThanEndNode();
81 ///////////////////////////////////////////////////////////////////////////
82 // NodeIsInTraversalRange: returns true if content is visited during
83 // the traversal of the range in the specified mode.
85 static bool NodeIsInTraversalRange(nsINode
* aNode
, bool aIsPreMode
,
86 const RawRangeBoundary
& aStart
,
87 const RawRangeBoundary
& aEnd
) {
88 if (NS_WARN_IF(!aStart
.IsSet()) || NS_WARN_IF(!aEnd
.IsSet()) ||
93 // If a leaf node contains an end point of the traversal range, it is
94 // always in the traversal range.
95 if (aNode
== aStart
.Container() || aNode
== aEnd
.Container()) {
96 if (aNode
->IsCharacterData()) {
97 return true; // text node or something
99 if (!aNode
->HasChildren()) {
101 aNode
!= aStart
.Container() || aStart
.IsStartOfContainer(),
102 "aStart.Container() doesn't have children and not a data node, "
103 "aStart should be at the beginning of its container");
104 MOZ_ASSERT(aNode
!= aEnd
.Container() || aEnd
.IsStartOfContainer(),
105 "aEnd.Container() doesn't have children and not a data node, "
106 "aEnd should be at the beginning of its container");
112 return ComparePreMode(aStart
, aEnd
, *aNode
);
115 return ComparePostMode(aStart
, aEnd
, *aNode
);
118 // Each concreate class of ContentIteratorBase may be owned by another class
119 // which may be owned by JS. Therefore, all of them should be in the cycle
120 // collection. However, we cannot make non-refcountable classes only with the
121 // macros. So, we need to make them cycle collectable without the macros.
122 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback
& aCallback
,
123 ContentIteratorBase
& aField
, const char* aName
,
124 uint32_t aFlags
= 0) {
125 ImplCycleCollectionTraverse(aCallback
, aField
.mCurNode
, aName
, aFlags
);
126 ImplCycleCollectionTraverse(aCallback
, aField
.mFirst
, aName
, aFlags
);
127 ImplCycleCollectionTraverse(aCallback
, aField
.mLast
, aName
, aFlags
);
128 ImplCycleCollectionTraverse(aCallback
, aField
.mClosestCommonInclusiveAncestor
,
132 void ImplCycleCollectionUnlink(ContentIteratorBase
& aField
) {
133 ImplCycleCollectionUnlink(aField
.mCurNode
);
134 ImplCycleCollectionUnlink(aField
.mFirst
);
135 ImplCycleCollectionUnlink(aField
.mLast
);
136 ImplCycleCollectionUnlink(aField
.mClosestCommonInclusiveAncestor
);
139 ContentIteratorBase::ContentIteratorBase(Order aOrder
) : mOrder(aOrder
) {}
141 ContentIteratorBase::~ContentIteratorBase() = default;
143 /******************************************************
145 ******************************************************/
147 nsresult
ContentIteratorBase::Init(nsINode
* aRoot
) {
148 if (NS_WARN_IF(!aRoot
)) {
149 return NS_ERROR_NULL_POINTER
;
152 if (mOrder
== Order::Pre
) {
154 mLast
= ContentIteratorBase::GetDeepLastChild(aRoot
);
155 NS_WARNING_ASSERTION(mLast
, "GetDeepLastChild returned null");
157 mFirst
= ContentIteratorBase::GetDeepFirstChild(aRoot
);
158 NS_WARNING_ASSERTION(mFirst
, "GetDeepFirstChild returned null");
162 mClosestCommonInclusiveAncestor
= aRoot
;
167 nsresult
ContentIteratorBase::Init(AbstractRange
* aRange
) {
168 if (NS_WARN_IF(!aRange
)) {
169 return NS_ERROR_INVALID_ARG
;
172 if (NS_WARN_IF(!aRange
->IsPositioned())) {
173 return NS_ERROR_INVALID_ARG
;
176 return InitInternal(aRange
->StartRef().AsRaw(), aRange
->EndRef().AsRaw());
179 nsresult
ContentIteratorBase::Init(nsINode
* aStartContainer
,
180 uint32_t aStartOffset
,
181 nsINode
* aEndContainer
,
182 uint32_t aEndOffset
) {
183 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStartContainer
, aStartOffset
,
184 aEndContainer
, aEndOffset
))) {
185 return NS_ERROR_INVALID_ARG
;
188 return InitInternal(RawRangeBoundary(aStartContainer
, aStartOffset
),
189 RawRangeBoundary(aEndContainer
, aEndOffset
));
192 nsresult
ContentIteratorBase::Init(const RawRangeBoundary
& aStart
,
193 const RawRangeBoundary
& aEnd
) {
194 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStart
, aEnd
))) {
195 return NS_ERROR_INVALID_ARG
;
198 return InitInternal(aStart
, aEnd
);
201 class MOZ_STACK_CLASS
ContentIteratorBase::Initializer final
{
203 Initializer(ContentIteratorBase
& aIterator
, const RawRangeBoundary
& aStart
,
204 const RawRangeBoundary
& aEnd
)
205 : mIterator
{aIterator
},
208 mStartIsCharacterData
{mStart
.Container()->IsCharacterData()} {
209 MOZ_ASSERT(mStart
.IsSetAndValid());
210 MOZ_ASSERT(mEnd
.IsSetAndValid());
217 * @return may be nullptr.
219 nsINode
* DetermineFirstNode() const;
222 * @return may be nullptr.
224 [[nodiscard
]] Result
<nsINode
*, nsresult
> DetermineLastNode() const;
226 bool IsCollapsedNonCharacterRange() const;
227 bool IsSingleNodeCharacterRange() const;
229 ContentIteratorBase
& mIterator
;
230 const RawRangeBoundary
& mStart
;
231 const RawRangeBoundary
& mEnd
;
232 const bool mStartIsCharacterData
;
235 nsresult
ContentIteratorBase::InitInternal(const RawRangeBoundary
& aStart
,
236 const RawRangeBoundary
& aEnd
) {
237 Initializer initializer
{*this, aStart
, aEnd
};
238 return initializer
.Run();
241 bool ContentIteratorBase::Initializer::IsCollapsedNonCharacterRange() const {
242 return !mStartIsCharacterData
&& mStart
== mEnd
;
245 bool ContentIteratorBase::Initializer::IsSingleNodeCharacterRange() const {
246 return mStartIsCharacterData
&& mStart
.Container() == mEnd
.Container();
249 nsresult
ContentIteratorBase::Initializer::Run() {
250 // get common content parent
251 mIterator
.mClosestCommonInclusiveAncestor
=
252 nsContentUtils::GetClosestCommonInclusiveAncestor(mStart
.Container(),
254 if (NS_WARN_IF(!mIterator
.mClosestCommonInclusiveAncestor
)) {
255 return NS_ERROR_FAILURE
;
258 // Check to see if we have a collapsed range, if so, there is nothing to
261 // XXX: CharacterDataNodes (text nodes) are currently an exception, since
262 // we always want to be able to iterate text nodes at the end points
265 if (IsCollapsedNonCharacterRange()) {
266 mIterator
.SetEmpty();
270 if (IsSingleNodeCharacterRange()) {
271 mIterator
.mFirst
= mStart
.Container()->AsContent();
272 mIterator
.mLast
= mIterator
.mFirst
;
273 mIterator
.mCurNode
= mIterator
.mFirst
;
278 mIterator
.mFirst
= DetermineFirstNode();
280 if (Result
<nsINode
*, nsresult
> lastNode
= DetermineLastNode();
281 NS_WARN_IF(lastNode
.isErr())) {
282 return lastNode
.unwrapErr();
284 mIterator
.mLast
= lastNode
.unwrap();
287 // If either first or last is null, they both have to be null!
288 if (!mIterator
.mFirst
|| !mIterator
.mLast
) {
289 mIterator
.SetEmpty();
292 mIterator
.mCurNode
= mIterator
.mFirst
;
297 nsINode
* ContentIteratorBase::Initializer::DetermineFirstNode() const {
298 nsIContent
* cChild
= nullptr;
300 // Try to get the child at our starting point. This might return null if
301 // mStart is immediately after the last node in mStart.Container().
302 if (!mStartIsCharacterData
) {
303 cChild
= mStart
.GetChildAtOffset();
307 // No children (possibly a <br> or text node), or index is after last child.
309 if (mIterator
.mOrder
== Order::Pre
) {
310 // XXX: In the future, if start offset is after the last
311 // character in the cdata node, should we set mFirst to
314 // Normally we would skip the start node because the start node is outside
315 // of the range in pre mode. However, if aStartOffset == 0, and the node
316 // is a non-container node (e.g. <br>), we don't skip the node in this
317 // case in order to address bug 1215798.
318 bool startIsContainer
= true;
319 if (mStart
.Container()->IsHTMLElement()) {
320 nsAtom
* name
= mStart
.Container()->NodeInfo()->NameAtom();
322 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name
));
324 if (!mStartIsCharacterData
&&
325 (startIsContainer
|| !mStart
.IsStartOfContainer())) {
326 nsINode
* const result
=
327 ContentIteratorBase::GetNextSibling(mStart
.Container());
328 NS_WARNING_ASSERTION(result
, "GetNextSibling returned null");
330 // Does mFirst node really intersect the range? The range could be
331 // 'degenerate', i.e., not collapsed but still contain no content.
333 NS_WARN_IF(!NodeIsInTraversalRange(
334 result
, mIterator
.mOrder
== Order::Pre
, mStart
, mEnd
))) {
340 return mStart
.Container()->AsContent();
344 if (NS_WARN_IF(!mStart
.Container()->IsContent())) {
345 // What else can we do?
348 return mStart
.Container()->AsContent();
351 if (mIterator
.mOrder
== Order::Pre
) {
356 nsINode
* const result
= ContentIteratorBase::GetDeepFirstChild(cChild
);
357 NS_WARNING_ASSERTION(result
, "GetDeepFirstChild returned null");
359 // Does mFirst node really intersect the range? The range could be
360 // 'degenerate', i.e., not collapsed but still contain no content.
361 if (result
&& !NodeIsInTraversalRange(result
, mIterator
.mOrder
== Order::Pre
,
369 Result
<nsINode
*, nsresult
> ContentIteratorBase::Initializer::DetermineLastNode()
371 const bool endIsCharacterData
= mEnd
.Container()->IsCharacterData();
373 if (endIsCharacterData
|| !mEnd
.Container()->HasChildren() ||
374 mEnd
.IsStartOfContainer()) {
375 if (mIterator
.mOrder
== Order::Pre
) {
376 if (NS_WARN_IF(!mEnd
.Container()->IsContent())) {
377 // Not much else to do here...
381 // If the end node is a non-container element and the end offset is 0,
382 // the last element should be the previous node (i.e., shouldn't
383 // include the end node in the range).
384 bool endIsContainer
= true;
385 if (mEnd
.Container()->IsHTMLElement()) {
386 nsAtom
* name
= mEnd
.Container()->NodeInfo()->NameAtom();
388 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name
));
390 if (!endIsCharacterData
&& !endIsContainer
&& mEnd
.IsStartOfContainer()) {
391 nsINode
* const result
= mIterator
.PrevNode(mEnd
.Container());
392 NS_WARNING_ASSERTION(result
, "PrevNode returned null");
393 if (result
&& result
!= mIterator
.mFirst
&&
394 NS_WARN_IF(!NodeIsInTraversalRange(
395 result
, mIterator
.mOrder
== Order::Pre
,
396 RawRangeBoundary(mIterator
.mFirst
, 0u), mEnd
))) {
403 return mEnd
.Container()->AsContent();
408 // XXX: In the future, if end offset is before the first character in the
409 // cdata node, should we set mLast to the prev sibling?
411 if (!endIsCharacterData
) {
412 nsINode
* const result
=
413 ContentIteratorBase::GetPrevSibling(mEnd
.Container());
414 NS_WARNING_ASSERTION(result
, "GetPrevSibling returned null");
416 if (!NodeIsInTraversalRange(result
, mIterator
.mOrder
== Order::Pre
,
422 return mEnd
.Container()->AsContent();
425 nsIContent
* cChild
= mEnd
.Ref();
427 if (NS_WARN_IF(!cChild
)) {
428 // No child at offset!
429 MOZ_ASSERT_UNREACHABLE("ContentIterator::ContentIterator");
430 return Err(NS_ERROR_FAILURE
);
433 if (mIterator
.mOrder
== Order::Pre
) {
434 nsINode
* const result
= ContentIteratorBase::GetDeepLastChild(cChild
);
435 NS_WARNING_ASSERTION(result
, "GetDeepLastChild returned null");
437 if (NS_WARN_IF(!NodeIsInTraversalRange(
438 result
, mIterator
.mOrder
== Order::Pre
, mStart
, mEnd
))) {
449 void ContentIteratorBase::SetEmpty() {
453 mClosestCommonInclusiveAncestor
= nullptr;
457 nsINode
* ContentIteratorBase::GetDeepFirstChild(nsINode
* aRoot
) {
458 if (NS_WARN_IF(!aRoot
) || !aRoot
->HasChildren()) {
462 return ContentIteratorBase::GetDeepFirstChild(aRoot
->GetFirstChild());
466 nsIContent
* ContentIteratorBase::GetDeepFirstChild(nsIContent
* aRoot
) {
467 if (NS_WARN_IF(!aRoot
)) {
471 nsIContent
* node
= aRoot
;
472 nsIContent
* child
= node
->GetFirstChild();
476 child
= node
->GetFirstChild();
483 nsINode
* ContentIteratorBase::GetDeepLastChild(nsINode
* aRoot
) {
484 if (NS_WARN_IF(!aRoot
) || !aRoot
->HasChildren()) {
488 return ContentIteratorBase::GetDeepLastChild(aRoot
->GetLastChild());
492 nsIContent
* ContentIteratorBase::GetDeepLastChild(nsIContent
* aRoot
) {
493 if (NS_WARN_IF(!aRoot
)) {
497 nsIContent
* node
= aRoot
;
498 while (node
->HasChildren()) {
499 nsIContent
* child
= node
->GetLastChild();
505 // Get the next sibling, or parent's next sibling, or grandpa's next sibling...
507 nsIContent
* ContentIteratorBase::GetNextSibling(nsINode
* aNode
) {
508 if (NS_WARN_IF(!aNode
)) {
512 if (aNode
->GetNextSibling()) {
513 return aNode
->GetNextSibling();
516 nsINode
* parent
= aNode
->GetParentNode();
517 if (NS_WARN_IF(!parent
)) {
521 // XXX This is a hack to preserve previous behaviour: This should be fixed
522 // in bug 1404916. If we were positioned on anonymous content, move to
523 // the first child of our parent.
524 if (parent
->GetLastChild() && parent
->GetLastChild() != aNode
) {
525 return parent
->GetFirstChild();
528 return ContentIteratorBase::GetNextSibling(parent
);
531 // Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
533 nsIContent
* ContentIteratorBase::GetPrevSibling(nsINode
* aNode
) {
534 if (NS_WARN_IF(!aNode
)) {
538 if (aNode
->GetPreviousSibling()) {
539 return aNode
->GetPreviousSibling();
542 nsINode
* parent
= aNode
->GetParentNode();
543 if (NS_WARN_IF(!parent
)) {
547 // XXX This is a hack to preserve previous behaviour: This should be fixed
548 // in bug 1404916. If we were positioned on anonymous content, move to
549 // the last child of our parent.
550 if (parent
->GetFirstChild() && parent
->GetFirstChild() != aNode
) {
551 return parent
->GetLastChild();
554 return ContentIteratorBase::GetPrevSibling(parent
);
557 nsINode
* ContentIteratorBase::NextNode(nsINode
* aNode
) {
558 nsINode
* node
= aNode
;
560 // if we are a Pre-order iterator, use pre-order
561 if (mOrder
== Order::Pre
) {
562 // if it has children then next node is first child
563 if (node
->HasChildren()) {
564 nsIContent
* firstChild
= node
->GetFirstChild();
565 MOZ_ASSERT(firstChild
);
570 // else next sibling is next
571 return ContentIteratorBase::GetNextSibling(node
);
575 nsINode
* parent
= node
->GetParentNode();
576 if (NS_WARN_IF(!parent
)) {
577 MOZ_ASSERT(parent
, "The node is the root node but not the last node");
582 if (nsIContent
* sibling
= node
->GetNextSibling()) {
583 // next node is sibling's "deep left" child
584 return ContentIteratorBase::GetDeepFirstChild(sibling
);
590 nsINode
* ContentIteratorBase::PrevNode(nsINode
* aNode
) {
591 nsINode
* node
= aNode
;
593 // if we are a Pre-order iterator, use pre-order
594 if (mOrder
== Order::Pre
) {
595 nsINode
* parent
= node
->GetParentNode();
596 if (NS_WARN_IF(!parent
)) {
597 MOZ_ASSERT(parent
, "The node is the root node but not the first node");
602 nsIContent
* sibling
= node
->GetPreviousSibling();
604 return ContentIteratorBase::GetDeepLastChild(sibling
);
611 if (node
->HasChildren()) {
612 return node
->GetLastChild();
615 // else prev sibling is previous
616 return ContentIteratorBase::GetPrevSibling(node
);
619 /******************************************************
620 * ContentIteratorBase routines
621 ******************************************************/
623 void ContentIteratorBase::First() {
625 MOZ_ASSERT(IsDone());
630 mozilla::DebugOnly
<nsresult
> rv
= PositionAt(mFirst
);
631 NS_ASSERTION(NS_SUCCEEDED(rv
), "Failed to position iterator!");
634 void ContentIteratorBase::Last() {
635 // Note that mLast can be nullptr if SetEmpty() is called in Init()
636 // since at that time, Init() returns NS_OK.
638 MOZ_ASSERT(IsDone());
643 mozilla::DebugOnly
<nsresult
> rv
= PositionAt(mLast
);
644 NS_ASSERTION(NS_SUCCEEDED(rv
), "Failed to position iterator!");
647 void ContentIteratorBase::Next() {
652 if (mCurNode
== mLast
) {
657 mCurNode
= NextNode(mCurNode
);
660 void ContentIteratorBase::Prev() {
665 if (mCurNode
== mFirst
) {
670 mCurNode
= PrevNode(mCurNode
);
673 // Keeping arrays of indexes for the stack of nodes makes PositionAt
675 nsresult
ContentIteratorBase::PositionAt(nsINode
* aCurNode
) {
676 if (NS_WARN_IF(!aCurNode
)) {
677 return NS_ERROR_NULL_POINTER
;
680 // take an early out if this doesn't actually change the position
681 if (mCurNode
== aCurNode
) {
686 // Check to see if the node falls within the traversal range.
688 RawRangeBoundary
first(mFirst
, 0u);
689 RawRangeBoundary
last(mLast
, 0u);
691 if (mFirst
&& mLast
) {
692 if (mOrder
== Order::Pre
) {
693 // In pre we want to record the point immediately before mFirst, which is
694 // the point immediately after mFirst's previous sibling.
695 first
= {mFirst
->GetParentNode(), mFirst
->GetPreviousSibling()};
697 // If mLast has no children, then we want to make sure to include it.
698 if (!mLast
->HasChildren()) {
699 last
= {mLast
->GetParentNode(), mLast
->AsContent()};
702 // If the first node has any children, we want to be immediately after the
703 // last. Otherwise we want to be immediately before mFirst.
704 if (mFirst
->HasChildren()) {
705 first
= {mFirst
, mFirst
->GetLastChild()};
707 first
= {mFirst
->GetParentNode(), mFirst
->GetPreviousSibling()};
710 // Set the last point immediately after the final node.
711 last
= {mLast
->GetParentNode(), mLast
->AsContent()};
715 NS_WARNING_ASSERTION(first
.IsSetAndValid(), "first is not valid");
716 NS_WARNING_ASSERTION(last
.IsSetAndValid(), "last is not valid");
718 // The end positions are always in the range even if it has no parent. We
719 // need to allow that or 'iter->Init(root)' would assert in Last() or First()
720 // for example, bug 327694.
721 if (mFirst
!= mCurNode
&& mLast
!= mCurNode
&&
722 (NS_WARN_IF(!first
.IsSet()) || NS_WARN_IF(!last
.IsSet()) ||
723 NS_WARN_IF(!NodeIsInTraversalRange(mCurNode
, mOrder
== Order::Pre
, first
,
726 return NS_ERROR_FAILURE
;
732 /******************************************************
733 * ContentSubtreeIterator init routines
734 ******************************************************/
736 nsresult
ContentSubtreeIterator::Init(nsINode
* aRoot
) {
737 return NS_ERROR_NOT_IMPLEMENTED
;
740 nsresult
ContentSubtreeIterator::Init(AbstractRange
* aRange
) {
743 if (NS_WARN_IF(!aRange
->IsPositioned())) {
744 return NS_ERROR_INVALID_ARG
;
749 return InitWithRange();
752 nsresult
ContentSubtreeIterator::Init(nsINode
* aStartContainer
,
753 uint32_t aStartOffset
,
754 nsINode
* aEndContainer
,
755 uint32_t aEndOffset
) {
756 return Init(RawRangeBoundary(aStartContainer
, aStartOffset
),
757 RawRangeBoundary(aEndContainer
, aEndOffset
));
760 nsresult
ContentSubtreeIterator::Init(const RawRangeBoundary
& aStartBoundary
,
761 const RawRangeBoundary
& aEndBoundary
) {
762 RefPtr
<nsRange
> range
=
763 nsRange::Create(aStartBoundary
, aEndBoundary
, IgnoreErrors());
764 if (NS_WARN_IF(!range
) || NS_WARN_IF(!range
->IsPositioned())) {
765 return NS_ERROR_INVALID_ARG
;
768 if (NS_WARN_IF(range
->StartRef() != aStartBoundary
) ||
769 NS_WARN_IF(range
->EndRef() != aEndBoundary
)) {
770 return NS_ERROR_UNEXPECTED
;
773 mRange
= std::move(range
);
775 return InitWithRange();
778 void ContentSubtreeIterator::CacheInclusiveAncestorsOfEndContainer() {
779 mInclusiveAncestorsOfEndContainer
.Clear();
780 nsINode
* const endContainer
= mRange
->GetEndContainer();
781 nsIContent
* endNode
=
782 endContainer
->IsContent() ? endContainer
->AsContent() : nullptr;
784 mInclusiveAncestorsOfEndContainer
.AppendElement(endNode
);
785 endNode
= endNode
->GetParent();
789 nsIContent
* ContentSubtreeIterator::DetermineCandidateForFirstContent() const {
790 nsINode
* startContainer
= mRange
->GetStartContainer();
791 nsIContent
* firstCandidate
= nullptr;
792 // find first node in range
793 nsINode
* node
= nullptr;
794 if (!startContainer
->GetChildCount()) {
795 // no children, start at the node itself
796 node
= startContainer
;
798 nsIContent
* child
= mRange
->GetChildAtStartOffset();
800 startContainer
->GetChildAt_Deprecated(mRange
->StartOffset()));
802 // offset after last child
803 node
= startContainer
;
805 firstCandidate
= child
;
809 if (!firstCandidate
) {
810 // then firstCandidate is next node after node
811 firstCandidate
= ContentIteratorBase::GetNextSibling(node
);
814 if (firstCandidate
) {
815 firstCandidate
= ContentIteratorBase::GetDeepFirstChild(firstCandidate
);
818 return firstCandidate
;
821 nsIContent
* ContentSubtreeIterator::DetermineFirstContent() const {
822 nsIContent
* firstCandidate
= DetermineCandidateForFirstContent();
823 if (!firstCandidate
) {
827 // confirm that this first possible contained node is indeed contained. Else
828 // we have a range that does not fully contain any node.
829 const Maybe
<bool> isNodeContainedInRange
=
830 RangeUtils::IsNodeContainedInRange(*firstCandidate
, mRange
);
831 MOZ_ALWAYS_TRUE(isNodeContainedInRange
);
832 if (!isNodeContainedInRange
.value()) {
836 // cool, we have the first node in the range. Now we walk up its ancestors
837 // to find the most senior that is still in the range. That's the real first
839 return GetTopAncestorInRange(firstCandidate
);
842 nsIContent
* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
843 nsIContent
* lastCandidate
{nullptr};
844 nsINode
* endContainer
= mRange
->GetEndContainer();
845 // now to find the last node
846 int32_t offset
= mRange
->EndOffset();
847 int32_t numChildren
= endContainer
->GetChildCount();
849 nsINode
* node
= nullptr;
850 if (offset
> numChildren
) {
851 // Can happen for text nodes
852 offset
= numChildren
;
854 if (!offset
|| !numChildren
) {
857 lastCandidate
= mRange
->EndRef().Ref();
858 MOZ_ASSERT(lastCandidate
== endContainer
->GetChildAt_Deprecated(--offset
));
859 NS_ASSERTION(lastCandidate
,
860 "tree traversal trouble in ContentSubtreeIterator::Init");
863 if (!lastCandidate
) {
864 // then lastCandidate is prev node before node
865 lastCandidate
= ContentIteratorBase::GetPrevSibling(node
);
869 lastCandidate
= ContentIteratorBase::GetDeepLastChild(lastCandidate
);
872 return lastCandidate
;
875 nsresult
ContentSubtreeIterator::InitWithRange() {
877 MOZ_ASSERT(mRange
->IsPositioned());
879 // get the start node and offset, convert to nsINode
880 mClosestCommonInclusiveAncestor
= mRange
->GetClosestCommonInclusiveAncestor();
881 nsINode
* startContainer
= mRange
->GetStartContainer();
882 const int32_t startOffset
= mRange
->StartOffset();
883 nsINode
* endContainer
= mRange
->GetEndContainer();
884 const int32_t endOffset
= mRange
->EndOffset();
885 MOZ_ASSERT(mClosestCommonInclusiveAncestor
&& startContainer
&& endContainer
);
887 MOZ_ASSERT(uint32_t(startOffset
) <= startContainer
->Length() &&
888 uint32_t(endOffset
) <= endContainer
->Length());
890 // short circuit when start node == end node
891 if (startContainer
== endContainer
) {
892 nsINode
* child
= startContainer
->GetFirstChild();
894 if (!child
|| startOffset
== endOffset
) {
895 // Text node, empty container, or collapsed
901 CacheInclusiveAncestorsOfEndContainer();
903 mFirst
= DetermineFirstContent();
909 mLast
= DetermineLastContent();
920 nsIContent
* ContentSubtreeIterator::DetermineLastContent() const {
921 nsIContent
* lastCandidate
= DetermineCandidateForLastContent();
922 if (!lastCandidate
) {
926 // confirm that this last possible contained node is indeed contained. Else
927 // we have a range that does not fully contain any node.
929 const Maybe
<bool> isNodeContainedInRange
=
930 RangeUtils::IsNodeContainedInRange(*lastCandidate
, mRange
);
931 MOZ_ALWAYS_TRUE(isNodeContainedInRange
);
932 if (!isNodeContainedInRange
.value()) {
936 // cool, we have the last node in the range. Now we walk up its ancestors to
937 // find the most senior that is still in the range. That's the real first
939 return GetTopAncestorInRange(lastCandidate
);
942 /****************************************************************
943 * ContentSubtreeIterator overrides of ContentIterator routines
944 ****************************************************************/
946 // we can't call PositionAt in a subtree iterator...
947 void ContentSubtreeIterator::First() { mCurNode
= mFirst
; }
949 // we can't call PositionAt in a subtree iterator...
950 void ContentSubtreeIterator::Last() { mCurNode
= mLast
; }
952 void ContentSubtreeIterator::Next() {
957 if (mCurNode
== mLast
) {
962 nsINode
* nextNode
= ContentIteratorBase::GetNextSibling(mCurNode
);
963 NS_ASSERTION(nextNode
, "No next sibling!?! This could mean deadlock!");
965 int32_t i
= mInclusiveAncestorsOfEndContainer
.IndexOf(nextNode
);
967 // as long as we are finding ancestors of the endpoint of the range,
968 // dive down into their children
969 nextNode
= nextNode
->GetFirstChild();
970 NS_ASSERTION(nextNode
, "Iterator error, expected a child node!");
972 // should be impossible to get a null pointer. If we went all the way
973 // down the child chain to the bottom without finding an interior node,
974 // then the previous node should have been the last, which was
975 // was tested at top of routine.
976 i
= mInclusiveAncestorsOfEndContainer
.IndexOf(nextNode
);
982 void ContentSubtreeIterator::Prev() {
983 // Prev should be optimized to use the mStartNodes, just as Next
984 // uses mInclusiveAncestorsOfEndContainer.
989 if (mCurNode
== mFirst
) {
994 // If any of these function calls return null, so will all succeeding ones,
995 // so mCurNode will wind up set to null.
996 nsINode
* prevNode
= ContentIteratorBase::GetDeepFirstChild(mCurNode
);
998 prevNode
= PrevNode(prevNode
);
1000 prevNode
= ContentIteratorBase::GetDeepLastChild(prevNode
);
1002 mCurNode
= GetTopAncestorInRange(prevNode
);
1005 nsresult
ContentSubtreeIterator::PositionAt(nsINode
* aCurNode
) {
1006 NS_ERROR("Not implemented!");
1007 return NS_ERROR_NOT_IMPLEMENTED
;
1010 /****************************************************************
1011 * ContentSubtreeIterator helper routines
1012 ****************************************************************/
1014 nsIContent
* ContentSubtreeIterator::GetTopAncestorInRange(
1015 nsINode
* aNode
) const {
1016 if (!aNode
|| !aNode
->GetParentNode()) {
1020 // aNode has a parent, so it must be content.
1021 nsIContent
* content
= aNode
->AsContent();
1023 // sanity check: aNode is itself in the range
1024 Maybe
<bool> isNodeContainedInRange
=
1025 RangeUtils::IsNodeContainedInRange(*aNode
, mRange
);
1026 NS_ASSERTION(isNodeContainedInRange
&& isNodeContainedInRange
.value(),
1027 "aNode isn't in mRange, or something else weird happened");
1028 if (!isNodeContainedInRange
|| !isNodeContainedInRange
.value()) {
1033 nsIContent
* parent
= content
->GetParent();
1034 // content always has a parent. If its parent is the root, however --
1035 // i.e., either it's not content, or it is content but its own parent is
1036 // null -- then we're finished, since we don't go up to the root.
1038 // We have to special-case this because CompareNodeToRange treats the root
1039 // node differently -- see bug 765205.
1040 if (!parent
|| !parent
->GetParentNode()) {
1044 isNodeContainedInRange
=
1045 RangeUtils::IsNodeContainedInRange(*parent
, mRange
);
1046 MOZ_ALWAYS_TRUE(isNodeContainedInRange
);
1047 if (!isNodeContainedInRange
.value()) {
1054 MOZ_CRASH("This should only be possible if aNode was null");
1057 } // namespace mozilla