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/Assertions.h"
10 #include "mozilla/dom/ShadowRoot.h"
11 #include "mozilla/DebugOnly.h"
12 #include "mozilla/RangeBoundary.h"
13 #include "mozilla/RangeUtils.h"
14 #include "mozilla/Result.h"
16 #include "nsContentUtils.h"
17 #include "nsElementTable.h"
18 #include "nsIContent.h"
25 #define NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(aResultType, aMethodName, ...) \
26 template aResultType ContentIteratorBase<RefPtr<nsINode>>::aMethodName( \
28 template aResultType ContentIteratorBase<nsINode*>::aMethodName(__VA_ARGS__)
31 * IteratorHelpers contains the static methods to help extra values
32 * based on whether or not the iterator allows to iterate nodes cross the shadow
35 struct IteratorHelpers
{
36 IteratorHelpers() = delete;
38 static nsINode
* GetStartContainer(AbstractRange
* aRange
,
39 bool aAllowCrossShadowBoundary
) {
41 return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
42 aAllowCrossShadowBoundary
)
43 ? aRange
->GetMayCrossShadowBoundaryStartContainer()
44 : aRange
->GetStartContainer();
47 static int32_t StartOffset(AbstractRange
* aRange
,
48 bool aAllowCrossShadowBoundary
) {
50 return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
51 aAllowCrossShadowBoundary
)
52 ? aRange
->MayCrossShadowBoundaryStartOffset()
53 : aRange
->StartOffset();
56 static nsINode
* GetEndContainer(AbstractRange
* aRange
,
57 bool aAllowCrossShadowBoundary
) {
59 return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
60 aAllowCrossShadowBoundary
)
61 ? aRange
->GetMayCrossShadowBoundaryEndContainer()
62 : aRange
->GetEndContainer();
65 static int32_t EndOffset(AbstractRange
* aRange
,
66 bool aAllowCrossShadowBoundary
) {
68 return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
69 aAllowCrossShadowBoundary
)
70 ? aRange
->MayCrossShadowBoundaryEndOffset()
71 : aRange
->EndOffset();
74 // FIXME(sefeng): This doesn't work with slots / flattened tree.
75 static nsINode
* GetParentNode(nsINode
& aNode
,
76 bool aAllowCrossShadowBoundary
) {
77 return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
78 aAllowCrossShadowBoundary
)
79 ? aNode
.GetParentOrShadowHostNode()
80 : aNode
.GetParentNode();
83 static ShadowRoot
* GetShadowRoot(const nsINode
* aNode
,
84 bool aAllowCrossShadowBoundary
) {
86 return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
87 aAllowCrossShadowBoundary
)
88 ? aNode
->GetShadowRootForSelection()
93 static bool ComparePostMode(const RawRangeBoundary
& aStart
,
94 const RawRangeBoundary
& aEnd
, nsINode
& aNode
) {
95 nsINode
* parent
= aNode
.GetParentNode();
100 // aNode should always be content, as we have a parent, but let's just be
101 // extra careful and check.
102 nsIContent
* content
=
103 NS_WARN_IF(!aNode
.IsContent()) ? nullptr : aNode
.AsContent();
105 // Post mode: start < node <= end.
106 RawRangeBoundary
afterNode(parent
, content
);
107 const auto isStartLessThanAfterNode
= [&]() {
108 const Maybe
<int32_t> startComparedToAfterNode
=
109 nsContentUtils::ComparePoints(aStart
, afterNode
);
110 return !NS_WARN_IF(!startComparedToAfterNode
) &&
111 (*startComparedToAfterNode
< 0);
114 const auto isAfterNodeLessOrEqualToEnd
= [&]() {
115 const Maybe
<int32_t> afterNodeComparedToEnd
=
116 nsContentUtils::ComparePoints(afterNode
, aEnd
);
117 return !NS_WARN_IF(!afterNodeComparedToEnd
) &&
118 (*afterNodeComparedToEnd
<= 0);
121 return isStartLessThanAfterNode() && isAfterNodeLessOrEqualToEnd();
124 static bool ComparePreMode(const RawRangeBoundary
& aStart
,
125 const RawRangeBoundary
& aEnd
, nsINode
& aNode
) {
126 nsINode
* parent
= aNode
.GetParentNode();
131 // Pre mode: start <= node < end.
132 RawRangeBoundary
beforeNode(parent
, aNode
.GetPreviousSibling());
134 const auto isStartLessOrEqualToBeforeNode
= [&]() {
135 const Maybe
<int32_t> startComparedToBeforeNode
=
136 nsContentUtils::ComparePoints(aStart
, beforeNode
);
137 return !NS_WARN_IF(!startComparedToBeforeNode
) &&
138 (*startComparedToBeforeNode
<= 0);
141 const auto isBeforeNodeLessThanEndNode
= [&]() {
142 const Maybe
<int32_t> beforeNodeComparedToEnd
=
143 nsContentUtils::ComparePoints(beforeNode
, aEnd
);
144 return !NS_WARN_IF(!beforeNodeComparedToEnd
) &&
145 (*beforeNodeComparedToEnd
< 0);
148 return isStartLessOrEqualToBeforeNode() && isBeforeNodeLessThanEndNode();
151 ///////////////////////////////////////////////////////////////////////////
152 // NodeIsInTraversalRange: returns true if content is visited during
153 // the traversal of the range in the specified mode.
155 static bool NodeIsInTraversalRange(nsINode
* aNode
, bool aIsPreMode
,
156 const RawRangeBoundary
& aStart
,
157 const RawRangeBoundary
& aEnd
) {
158 if (NS_WARN_IF(!aStart
.IsSet()) || NS_WARN_IF(!aEnd
.IsSet()) ||
159 NS_WARN_IF(!aNode
)) {
163 // If a leaf node contains an end point of the traversal range, it is
164 // always in the traversal range.
165 if (aNode
== aStart
.Container() || aNode
== aEnd
.Container()) {
166 if (aNode
->IsCharacterData()) {
167 return true; // text node or something
169 if (!aNode
->HasChildren()) {
171 aNode
!= aStart
.Container() || aStart
.IsStartOfContainer(),
172 "aStart.Container() doesn't have children and not a data node, "
173 "aStart should be at the beginning of its container");
174 MOZ_ASSERT(aNode
!= aEnd
.Container() || aEnd
.IsStartOfContainer(),
175 "aEnd.Container() doesn't have children and not a data node, "
176 "aEnd should be at the beginning of its container");
182 return ComparePreMode(aStart
, aEnd
, *aNode
);
185 return ComparePostMode(aStart
, aEnd
, *aNode
);
188 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback
& aCallback
,
189 PostContentIterator
& aField
, const char* aName
,
190 uint32_t aFlags
= 0) {
191 ImplCycleCollectionTraverse(
192 aCallback
, static_cast<SafeContentIteratorBase
&>(aField
), aName
, aFlags
);
195 void ImplCycleCollectionUnlink(PostContentIterator
& aField
) {
196 ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase
&>(aField
));
199 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback
& aCallback
,
200 PreContentIterator
& aField
, const char* aName
,
201 uint32_t aFlags
= 0) {
202 ImplCycleCollectionTraverse(
203 aCallback
, static_cast<SafeContentIteratorBase
&>(aField
), aName
, aFlags
);
206 void ImplCycleCollectionUnlink(PreContentIterator
& aField
) {
207 ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase
&>(aField
));
210 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback
& aCallback
,
211 ContentSubtreeIterator
& aField
,
212 const char* aName
, uint32_t aFlags
= 0) {
213 ImplCycleCollectionTraverse(aCallback
, aField
.mRange
, aName
, aFlags
);
214 ImplCycleCollectionTraverse(
215 aCallback
, static_cast<SafeContentIteratorBase
&>(aField
), aName
, aFlags
);
218 void ImplCycleCollectionUnlink(ContentSubtreeIterator
& aField
) {
219 ImplCycleCollectionUnlink(aField
.mRange
);
220 ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase
&>(aField
));
223 /******************************************************
224 * ContentIteratorBase
225 ******************************************************/
227 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(, ContentIteratorBase
, Order
);
229 template <typename NodeType
>
230 ContentIteratorBase
<NodeType
>::ContentIteratorBase(Order aOrder
)
233 template ContentIteratorBase
<RefPtr
<nsINode
>>::~ContentIteratorBase();
234 template ContentIteratorBase
<nsINode
*>::~ContentIteratorBase();
236 template <typename NodeType
>
237 ContentIteratorBase
<NodeType
>::~ContentIteratorBase() {
238 MOZ_DIAGNOSTIC_ASSERT_IF(mMutationGuard
.isSome(),
239 !mMutationGuard
->Mutated(0));
242 /******************************************************
244 ******************************************************/
246 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult
, Init
, nsINode
*);
248 template <typename NodeType
>
249 nsresult ContentIteratorBase
<NodeType
>::Init(nsINode
* aRoot
) {
250 if (NS_WARN_IF(!aRoot
)) {
251 return NS_ERROR_NULL_POINTER
;
254 if (mOrder
== Order::Pre
) {
256 mLast
= ContentIteratorBase::GetDeepLastChild(aRoot
);
257 NS_WARNING_ASSERTION(mLast
, "GetDeepLastChild returned null");
259 mFirst
= ContentIteratorBase::GetDeepFirstChild(aRoot
);
260 NS_WARNING_ASSERTION(mFirst
, "GetDeepFirstChild returned null");
264 mClosestCommonInclusiveAncestor
= aRoot
;
269 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult
, Init
, AbstractRange
*);
271 template <typename NodeType
>
272 nsresult ContentIteratorBase
<NodeType
>::Init(AbstractRange
* aRange
) {
273 if (NS_WARN_IF(!aRange
)) {
274 return NS_ERROR_INVALID_ARG
;
277 if (NS_WARN_IF(!aRange
->IsPositioned())) {
278 return NS_ERROR_INVALID_ARG
;
281 return InitInternal(aRange
->StartRef().AsRaw(), aRange
->EndRef().AsRaw());
284 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult
, Init
, nsINode
*, uint32_t,
287 template <typename NodeType
>
288 nsresult ContentIteratorBase
<NodeType
>::Init(nsINode
* aStartContainer
,
289 uint32_t aStartOffset
,
290 nsINode
* aEndContainer
,
291 uint32_t aEndOffset
) {
292 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStartContainer
, aStartOffset
,
293 aEndContainer
, aEndOffset
))) {
294 return NS_ERROR_INVALID_ARG
;
297 return InitInternal(RawRangeBoundary(aStartContainer
, aStartOffset
),
298 RawRangeBoundary(aEndContainer
, aEndOffset
));
301 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult
, Init
, const RawRangeBoundary
&,
302 const RawRangeBoundary
&);
304 template <typename NodeType
>
305 nsresult ContentIteratorBase
<NodeType
>::Init(const RawRangeBoundary
& aStart
,
306 const RawRangeBoundary
& aEnd
) {
307 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStart
, aEnd
))) {
308 return NS_ERROR_INVALID_ARG
;
311 return InitInternal(aStart
, aEnd
);
314 template <typename NodeType
>
315 class MOZ_STACK_CLASS ContentIteratorBase
<NodeType
>::Initializer final
{
317 Initializer(ContentIteratorBase
<NodeType
>& aIterator
,
318 const RawRangeBoundary
& aStart
, const RawRangeBoundary
& aEnd
)
319 : mIterator
{aIterator
},
322 mStartIsCharacterData
{mStart
.Container()->IsCharacterData()} {
323 MOZ_ASSERT(mStart
.IsSetAndValid());
324 MOZ_ASSERT(mEnd
.IsSetAndValid());
331 * @return may be nullptr.
333 nsINode
* DetermineFirstNode() const;
336 * @return may be nullptr.
338 [[nodiscard
]] Result
<nsINode
*, nsresult
> DetermineLastNode() const;
340 bool IsCollapsedNonCharacterRange() const;
341 bool IsSingleNodeCharacterRange() const;
343 ContentIteratorBase
& mIterator
;
344 const RawRangeBoundary
& mStart
;
345 const RawRangeBoundary
& mEnd
;
346 const bool mStartIsCharacterData
;
350 nsresult ContentIteratorBase
<RefPtr
<nsINode
>>::InitInternal(
351 const RawRangeBoundary
& aStart
, const RawRangeBoundary
& aEnd
) {
352 Initializer initializer
{*this, aStart
, aEnd
};
353 return initializer
.Run();
357 nsresult ContentIteratorBase
<nsINode
*>::InitInternal(
358 const RawRangeBoundary
& aStart
, const RawRangeBoundary
& aEnd
) {
359 Initializer initializer
{*this, aStart
, aEnd
};
360 nsresult rv
= initializer
.Run();
364 mMutationGuard
.emplace();
365 mAssertNoGC
.emplace();
369 template <typename NodeType
>
370 bool ContentIteratorBase
<NodeType
>::Initializer::IsCollapsedNonCharacterRange()
372 return !mStartIsCharacterData
&& mStart
== mEnd
;
375 template <typename NodeType
>
376 bool ContentIteratorBase
<NodeType
>::Initializer::IsSingleNodeCharacterRange()
378 return mStartIsCharacterData
&& mStart
.Container() == mEnd
.Container();
381 template <typename NodeType
>
382 nsresult ContentIteratorBase
<NodeType
>::Initializer::Run() {
383 // get common content parent
384 mIterator
.mClosestCommonInclusiveAncestor
=
385 nsContentUtils::GetClosestCommonInclusiveAncestor(mStart
.Container(),
387 if (NS_WARN_IF(!mIterator
.mClosestCommonInclusiveAncestor
)) {
388 return NS_ERROR_FAILURE
;
391 // Check to see if we have a collapsed range, if so, there is nothing to
394 // XXX: CharacterDataNodes (text nodes) are currently an exception, since
395 // we always want to be able to iterate text nodes at the end points
398 if (IsCollapsedNonCharacterRange()) {
399 mIterator
.SetEmpty();
403 if (IsSingleNodeCharacterRange()) {
404 mIterator
.mFirst
= mStart
.Container()->AsContent();
405 mIterator
.mLast
= mIterator
.mFirst
;
406 mIterator
.mCurNode
= mIterator
.mFirst
;
411 mIterator
.mFirst
= DetermineFirstNode();
413 if (Result
<nsINode
*, nsresult
> lastNode
= DetermineLastNode();
414 NS_WARN_IF(lastNode
.isErr())) {
415 return lastNode
.unwrapErr();
417 mIterator
.mLast
= lastNode
.unwrap();
420 // If either first or last is null, they both have to be null!
421 if (!mIterator
.mFirst
|| !mIterator
.mLast
) {
422 mIterator
.SetEmpty();
425 mIterator
.mCurNode
= mIterator
.mFirst
;
430 template <typename NodeType
>
431 nsINode
* ContentIteratorBase
<NodeType
>::Initializer::DetermineFirstNode()
433 nsIContent
* cChild
= nullptr;
435 // Try to get the child at our starting point. This might return null if
436 // mStart is immediately after the last node in mStart.Container().
437 if (!mStartIsCharacterData
) {
438 cChild
= mStart
.GetChildAtOffset();
442 // No children (possibly a <br> or text node), or index is after last child.
444 if (mIterator
.mOrder
== Order::Pre
) {
445 // XXX: In the future, if start offset is after the last
446 // character in the cdata node, should we set mFirst to
449 // Normally we would skip the start node because the start node is outside
450 // of the range in pre mode. However, if aStartOffset == 0, and the node
451 // is a non-container node (e.g. <br>), we don't skip the node in this
452 // case in order to address bug 1215798.
453 bool startIsContainer
= true;
454 if (mStart
.Container()->IsHTMLElement()) {
455 nsAtom
* name
= mStart
.Container()->NodeInfo()->NameAtom();
457 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name
));
459 if (!mStartIsCharacterData
&&
460 (startIsContainer
|| !mStart
.IsStartOfContainer())) {
461 nsINode
* const result
=
462 ContentIteratorBase::GetNextSibling(mStart
.Container());
463 NS_WARNING_ASSERTION(result
, "GetNextSibling returned null");
465 // Does mFirst node really intersect the range? The range could be
466 // 'degenerate', i.e., not collapsed but still contain no content.
468 NS_WARN_IF(!NodeIsInTraversalRange(
469 result
, mIterator
.mOrder
== Order::Pre
, mStart
, mEnd
))) {
475 return mStart
.Container()->AsContent();
479 if (NS_WARN_IF(!mStart
.Container()->IsContent())) {
480 // What else can we do?
483 return mStart
.Container()->AsContent();
486 if (mIterator
.mOrder
== Order::Pre
) {
491 nsINode
* const result
= ContentIteratorBase::GetDeepFirstChild(cChild
);
492 NS_WARNING_ASSERTION(result
, "GetDeepFirstChild returned null");
494 // Does mFirst node really intersect the range? The range could be
495 // 'degenerate', i.e., not collapsed but still contain no content.
496 if (result
&& !NodeIsInTraversalRange(result
, mIterator
.mOrder
== Order::Pre
,
504 template <typename NodeType
>
505 Result
<nsINode
*, nsresult
>
506 ContentIteratorBase
<NodeType
>::Initializer::DetermineLastNode() const {
507 const bool endIsCharacterData
= mEnd
.Container()->IsCharacterData();
509 if (endIsCharacterData
|| !mEnd
.Container()->HasChildren() ||
510 mEnd
.IsStartOfContainer()) {
511 if (mIterator
.mOrder
== Order::Pre
) {
512 if (NS_WARN_IF(!mEnd
.Container()->IsContent())) {
513 // Not much else to do here...
517 // If the end node is a non-container element and the end offset is 0,
518 // the last element should be the previous node (i.e., shouldn't
519 // include the end node in the range).
520 bool endIsContainer
= true;
521 if (mEnd
.Container()->IsHTMLElement()) {
522 nsAtom
* name
= mEnd
.Container()->NodeInfo()->NameAtom();
524 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name
));
526 if (!endIsCharacterData
&& !endIsContainer
&& mEnd
.IsStartOfContainer()) {
527 nsINode
* const result
= mIterator
.PrevNode(mEnd
.Container());
528 NS_WARNING_ASSERTION(result
, "PrevNode returned null");
529 if (result
&& result
!= mIterator
.mFirst
&&
530 NS_WARN_IF(!NodeIsInTraversalRange(
531 result
, mIterator
.mOrder
== Order::Pre
,
532 RawRangeBoundary(mIterator
.mFirst
, 0u), mEnd
))) {
539 return mEnd
.Container()->AsContent();
544 // XXX: In the future, if end offset is before the first character in the
545 // cdata node, should we set mLast to the prev sibling?
547 if (!endIsCharacterData
) {
548 nsINode
* const result
=
549 ContentIteratorBase::GetPrevSibling(mEnd
.Container());
550 NS_WARNING_ASSERTION(result
, "GetPrevSibling returned null");
552 if (!NodeIsInTraversalRange(result
, mIterator
.mOrder
== Order::Pre
,
558 return mEnd
.Container()->AsContent();
561 nsIContent
* cChild
= mEnd
.Ref();
563 if (NS_WARN_IF(!cChild
)) {
564 // No child at offset!
565 MOZ_ASSERT_UNREACHABLE("ContentIterator::ContentIterator");
566 return Err(NS_ERROR_FAILURE
);
569 if (mIterator
.mOrder
== Order::Pre
) {
570 nsINode
* const result
= ContentIteratorBase::GetDeepLastChild(cChild
);
571 NS_WARNING_ASSERTION(result
, "GetDeepLastChild returned null");
573 if (NS_WARN_IF(!NodeIsInTraversalRange(
574 result
, mIterator
.mOrder
== Order::Pre
, mStart
, mEnd
))) {
585 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, SetEmpty
);
587 template <typename NodeType
>
588 void ContentIteratorBase
<NodeType
>::SetEmpty() {
592 mClosestCommonInclusiveAncestor
= nullptr;
596 template <typename NodeType
>
597 nsINode
* ContentIteratorBase
<NodeType
>::GetDeepFirstChild(nsINode
* aRoot
) {
598 if (NS_WARN_IF(!aRoot
) || !aRoot
->HasChildren()) {
602 return ContentIteratorBase::GetDeepFirstChild(aRoot
->GetFirstChild());
606 template <typename NodeType
>
607 nsIContent
* ContentIteratorBase
<NodeType
>::GetDeepFirstChild(
608 nsIContent
* aRoot
, bool aAllowCrossShadowBoundary
) {
609 if (NS_WARN_IF(!aRoot
)) {
613 nsIContent
* node
= aRoot
;
614 nsIContent
* child
= nullptr;
616 if (ShadowRoot
* shadowRoot
=
617 IteratorHelpers::GetShadowRoot(node
, aAllowCrossShadowBoundary
)) {
618 // When finding the deepest child of node, if this node has a
619 // web exposed shadow root, we use this shadow root to find the deepest
621 // If the first candidate should be a slotted content,
622 // shadowRoot->GetFirstChild() should be able to return the <slot> element.
623 // It's probably correct I think. Then it's up to the caller of this
624 // iterator to decide whether to use the slot's assigned nodes or not.
625 MOZ_ASSERT(aAllowCrossShadowBoundary
);
626 child
= shadowRoot
->GetFirstChild();
628 child
= node
->GetFirstChild();
633 if (ShadowRoot
* shadowRoot
=
634 IteratorHelpers::GetShadowRoot(node
, aAllowCrossShadowBoundary
)) {
635 // When finding the deepest child of node, if this node has a
636 // web exposed shadow root, we use this shadow root to find the deepest
638 // If the first candidate should be a slotted content,
639 // shadowRoot->GetFirstChild() should be able to return the <slot>
640 // element. It's probably correct I think. Then it's up to the caller of
641 // this iterator to decide whether to use the slot's assigned nodes or
643 child
= shadowRoot
->GetFirstChild();
645 child
= node
->GetFirstChild();
653 template <typename NodeType
>
654 nsINode
* ContentIteratorBase
<NodeType
>::GetDeepLastChild(nsINode
* aRoot
) {
655 if (NS_WARN_IF(!aRoot
) || !aRoot
->HasChildren()) {
659 return ContentIteratorBase::GetDeepLastChild(aRoot
->GetLastChild());
663 template <typename NodeType
>
664 nsIContent
* ContentIteratorBase
<NodeType
>::GetDeepLastChild(
665 nsIContent
* aRoot
, bool aAllowCrossShadowBoundary
) {
666 if (NS_WARN_IF(!aRoot
)) {
670 nsIContent
* node
= aRoot
;
672 ShadowRoot
* shadowRoot
=
673 IteratorHelpers::GetShadowRoot(node
, aAllowCrossShadowBoundary
);
674 // FIXME(sefeng): This doesn't work with slots / flattened tree.
675 while (node
->HasChildren() || (shadowRoot
&& shadowRoot
->HasChildren())) {
676 if (node
->HasChildren()) {
677 node
= node
->GetLastChild();
679 MOZ_ASSERT(shadowRoot
);
680 // If this node doesn't have a child, but it's also a shadow host
681 // that can be selected, we go into this shadow tree.
682 node
= shadowRoot
->GetLastChild();
685 IteratorHelpers::GetShadowRoot(node
, aAllowCrossShadowBoundary
);
690 // Get the next sibling, or parent's next sibling, or shadow host's next
691 // sibling (when aAllowCrossShadowBoundary is true), or grandpa's next
696 template <typename NodeType
>
697 nsIContent
* ContentIteratorBase
<NodeType
>::GetNextSibling(
698 nsINode
* aNode
, bool aAllowCrossShadowBoundary
) {
699 if (NS_WARN_IF(!aNode
)) {
703 if (nsIContent
* next
= aNode
->GetNextSibling()) {
708 IteratorHelpers::GetParentNode(*aNode
, aAllowCrossShadowBoundary
);
709 if (NS_WARN_IF(!parent
)) {
713 if (aAllowCrossShadowBoundary
) {
714 // This is temporary solution.
715 // For shadow root, instead of getting to the sibling of the parent
716 // directly, we need to get into the light tree of the parent to handle
718 if (ShadowRoot
* shadowRoot
= ShadowRoot::FromNode(aNode
)) {
719 if (nsIContent
* child
= parent
->GetFirstChild()) {
725 return ContentIteratorBase::GetNextSibling(parent
, aAllowCrossShadowBoundary
);
728 // Get the prev sibling, or parent's prev sibling, or shadow host's prev sibling
729 // (when aAllowCrossShadowBoundary is true), or grandpa's prev sibling... static
730 template <typename NodeType
>
731 nsIContent
* ContentIteratorBase
<NodeType
>::GetPrevSibling(
732 nsINode
* aNode
, bool aAllowCrossShadowBoundary
) {
733 if (NS_WARN_IF(!aNode
)) {
737 if (nsIContent
* prev
= aNode
->GetPreviousSibling()) {
742 IteratorHelpers::GetParentNode(*aNode
, aAllowCrossShadowBoundary
);
743 if (NS_WARN_IF(!parent
)) {
747 return ContentIteratorBase::GetPrevSibling(parent
, aAllowCrossShadowBoundary
);
750 template <typename NodeType
>
751 nsINode
* ContentIteratorBase
<NodeType
>::NextNode(nsINode
* aNode
) {
752 nsINode
* node
= aNode
;
754 // if we are a Pre-order iterator, use pre-order
755 if (mOrder
== Order::Pre
) {
756 // if it has children then next node is first child
757 if (node
->HasChildren()) {
758 nsIContent
* firstChild
= node
->GetFirstChild();
759 MOZ_ASSERT(firstChild
);
764 // else next sibling is next
765 return ContentIteratorBase::GetNextSibling(node
);
769 nsINode
* parent
= node
->GetParentNode();
770 if (NS_WARN_IF(!parent
)) {
771 MOZ_ASSERT(parent
, "The node is the root node but not the last node");
776 if (nsIContent
* sibling
= node
->GetNextSibling()) {
777 // next node is sibling's "deep left" child
778 return ContentIteratorBase::GetDeepFirstChild(sibling
);
784 template <typename NodeType
>
785 nsINode
* ContentIteratorBase
<NodeType
>::PrevNode(nsINode
* aNode
) {
786 nsINode
* node
= aNode
;
788 // if we are a Pre-order iterator, use pre-order
789 if (mOrder
== Order::Pre
) {
790 nsINode
* parent
= node
->GetParentNode();
791 if (NS_WARN_IF(!parent
)) {
792 MOZ_ASSERT(parent
, "The node is the root node but not the first node");
797 nsIContent
* sibling
= node
->GetPreviousSibling();
799 return ContentIteratorBase::GetDeepLastChild(sibling
);
806 if (node
->HasChildren()) {
807 return node
->GetLastChild();
810 // else prev sibling is previous
811 return ContentIteratorBase::GetPrevSibling(node
);
814 /******************************************************
815 * ContentIteratorBase routines
816 ******************************************************/
818 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, First
);
820 template <typename NodeType
>
821 void ContentIteratorBase
<NodeType
>::First() {
823 MOZ_ASSERT(IsDone());
828 mozilla::DebugOnly
<nsresult
> rv
= PositionAt(mFirst
);
829 NS_ASSERTION(NS_SUCCEEDED(rv
), "Failed to position iterator!");
832 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Last
);
834 template <typename NodeType
>
835 void ContentIteratorBase
<NodeType
>::Last() {
836 // Note that mLast can be nullptr if SetEmpty() is called in Init()
837 // since at that time, Init() returns NS_OK.
839 MOZ_ASSERT(IsDone());
844 mozilla::DebugOnly
<nsresult
> rv
= PositionAt(mLast
);
845 NS_ASSERTION(NS_SUCCEEDED(rv
), "Failed to position iterator!");
848 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Next
);
850 template <typename NodeType
>
851 void ContentIteratorBase
<NodeType
>::Next() {
856 if (mCurNode
== mLast
) {
861 mCurNode
= NextNode(mCurNode
);
864 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Prev
);
866 template <typename NodeType
>
867 void ContentIteratorBase
<NodeType
>::Prev() {
872 if (mCurNode
== mFirst
) {
877 mCurNode
= PrevNode(mCurNode
);
880 // Keeping arrays of indexes for the stack of nodes makes PositionAt
882 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult
, PositionAt
, nsINode
*);
884 template <typename NodeType
>
885 nsresult ContentIteratorBase
<NodeType
>::PositionAt(nsINode
* aCurNode
) {
886 if (NS_WARN_IF(!aCurNode
)) {
887 return NS_ERROR_NULL_POINTER
;
890 // take an early out if this doesn't actually change the position
891 if (mCurNode
== aCurNode
) {
896 // Check to see if the node falls within the traversal range.
898 RawRangeBoundary
first(mFirst
, 0u);
899 RawRangeBoundary
last(mLast
, 0u);
901 if (mFirst
&& mLast
) {
902 if (mOrder
== Order::Pre
) {
903 // In pre we want to record the point immediately before mFirst, which is
904 // the point immediately after mFirst's previous sibling.
905 first
= {mFirst
->GetParentNode(), mFirst
->GetPreviousSibling()};
907 // If mLast has no children, then we want to make sure to include it.
908 if (!mLast
->HasChildren()) {
909 last
= {mLast
->GetParentNode(), mLast
->AsContent()};
912 // If the first node has any children, we want to be immediately after the
913 // last. Otherwise we want to be immediately before mFirst.
914 if (mFirst
->HasChildren()) {
915 first
= {mFirst
, mFirst
->GetLastChild()};
917 first
= {mFirst
->GetParentNode(), mFirst
->GetPreviousSibling()};
920 // Set the last point immediately after the final node.
921 last
= {mLast
->GetParentNode(), mLast
->AsContent()};
925 NS_WARNING_ASSERTION(first
.IsSetAndValid(), "first is not valid");
926 NS_WARNING_ASSERTION(last
.IsSetAndValid(), "last is not valid");
928 // The end positions are always in the range even if it has no parent. We
929 // need to allow that or 'iter->Init(root)' would assert in Last() or First()
930 // for example, bug 327694.
931 if (mFirst
!= mCurNode
&& mLast
!= mCurNode
&&
932 (NS_WARN_IF(!first
.IsSet()) || NS_WARN_IF(!last
.IsSet()) ||
933 NS_WARN_IF(!NodeIsInTraversalRange(mCurNode
, mOrder
== Order::Pre
, first
,
936 return NS_ERROR_FAILURE
;
942 /******************************************************
943 * ContentSubtreeIterator init routines
944 ******************************************************/
946 nsresult
ContentSubtreeIterator::Init(nsINode
* aRoot
) {
947 return NS_ERROR_NOT_IMPLEMENTED
;
950 nsresult
ContentSubtreeIterator::Init(AbstractRange
* aRange
) {
953 if (NS_WARN_IF(!aRange
->IsPositioned())) {
954 return NS_ERROR_INVALID_ARG
;
959 return InitWithRange();
962 nsresult
ContentSubtreeIterator::Init(nsINode
* aStartContainer
,
963 uint32_t aStartOffset
,
964 nsINode
* aEndContainer
,
965 uint32_t aEndOffset
) {
966 return Init(RawRangeBoundary(aStartContainer
, aStartOffset
),
967 RawRangeBoundary(aEndContainer
, aEndOffset
));
970 nsresult
ContentSubtreeIterator::Init(const RawRangeBoundary
& aStartBoundary
,
971 const RawRangeBoundary
& aEndBoundary
) {
972 RefPtr
<nsRange
> range
=
973 nsRange::Create(aStartBoundary
, aEndBoundary
, IgnoreErrors());
974 if (NS_WARN_IF(!range
) || NS_WARN_IF(!range
->IsPositioned())) {
975 return NS_ERROR_INVALID_ARG
;
978 if (NS_WARN_IF(range
->StartRef() != aStartBoundary
) ||
979 NS_WARN_IF(range
->EndRef() != aEndBoundary
)) {
980 return NS_ERROR_UNEXPECTED
;
983 mRange
= std::move(range
);
985 return InitWithRange();
988 nsresult
ContentSubtreeIterator::InitWithAllowCrossShadowBoundary(
989 AbstractRange
* aRange
) {
992 if (NS_WARN_IF(!aRange
->IsPositioned())) {
993 return NS_ERROR_INVALID_ARG
;
998 mAllowCrossShadowBoundary
= AllowRangeCrossShadowBoundary::Yes
;
999 return InitWithRange();
1002 void ContentSubtreeIterator::CacheInclusiveAncestorsOfEndContainer() {
1003 mInclusiveAncestorsOfEndContainer
.Clear();
1004 nsINode
* const endContainer
=
1005 IteratorHelpers::GetEndContainer(mRange
, IterAllowCrossShadowBoundary());
1006 nsIContent
* endNode
=
1007 endContainer
->IsContent() ? endContainer
->AsContent() : nullptr;
1009 mInclusiveAncestorsOfEndContainer
.AppendElement(endNode
);
1010 // Cross the boundary for contents in shadow tree.
1011 nsINode
* parent
= IteratorHelpers::GetParentNode(
1012 *endNode
, IterAllowCrossShadowBoundary());
1013 if (!parent
|| !parent
->IsContent()) {
1016 endNode
= parent
->AsContent();
1020 nsIContent
* ContentSubtreeIterator::DetermineCandidateForFirstContent() const {
1021 nsINode
* startContainer
= IteratorHelpers::GetStartContainer(
1022 mRange
, IterAllowCrossShadowBoundary());
1023 nsIContent
* firstCandidate
= nullptr;
1024 // find first node in range
1025 nsINode
* node
= nullptr;
1026 if (!startContainer
->GetChildCount()) {
1027 // no children, start at the node itself
1028 node
= startContainer
;
1031 IterAllowCrossShadowBoundary()
1032 ? mRange
->GetMayCrossShadowBoundaryChildAtStartOffset()
1033 : mRange
->GetChildAtStartOffset();
1035 MOZ_ASSERT(child
== startContainer
->GetChildAt_Deprecated(
1036 IteratorHelpers::StartOffset(
1037 mRange
, IterAllowCrossShadowBoundary())));
1039 // offset after last child
1040 node
= startContainer
;
1042 firstCandidate
= child
;
1046 if (!firstCandidate
) {
1047 // then firstCandidate is next node after node
1048 firstCandidate
= ContentIteratorBase::GetNextSibling(
1049 node
, IterAllowCrossShadowBoundary());
1052 if (firstCandidate
) {
1053 firstCandidate
= ContentIteratorBase::GetDeepFirstChild(
1054 firstCandidate
, IterAllowCrossShadowBoundary());
1057 return firstCandidate
;
1060 nsIContent
* ContentSubtreeIterator::DetermineFirstContent() const {
1061 nsIContent
* firstCandidate
= DetermineCandidateForFirstContent();
1062 if (!firstCandidate
) {
1066 // confirm that this first possible contained node is indeed contained. Else
1067 // we have a range that does not fully contain any node.
1068 const Maybe
<bool> isNodeContainedInRange
=
1069 RangeUtils::IsNodeContainedInRange(*firstCandidate
, mRange
);
1070 MOZ_ALWAYS_TRUE(isNodeContainedInRange
);
1071 if (!isNodeContainedInRange
.value()) {
1075 // cool, we have the first node in the range. Now we walk up its ancestors
1076 // to find the most senior that is still in the range. That's the real first
1078 return GetTopAncestorInRange(firstCandidate
);
1081 nsIContent
* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
1082 nsIContent
* lastCandidate
{nullptr};
1083 nsINode
* endContainer
=
1084 IteratorHelpers::GetEndContainer(mRange
, IterAllowCrossShadowBoundary());
1085 // now to find the last node
1087 IteratorHelpers::EndOffset(mRange
, IterAllowCrossShadowBoundary());
1089 int32_t numChildren
= endContainer
->GetChildCount();
1091 nsINode
* node
= nullptr;
1092 if (offset
> numChildren
) {
1093 // Can happen for text nodes
1094 offset
= numChildren
;
1096 if (!offset
|| !numChildren
) {
1097 node
= endContainer
;
1099 lastCandidate
= IterAllowCrossShadowBoundary()
1100 ? mRange
->MayCrossShadowBoundaryEndRef().Ref()
1101 : mRange
->EndRef().Ref();
1102 MOZ_ASSERT(lastCandidate
== endContainer
->GetChildAt_Deprecated(--offset
));
1103 NS_ASSERTION(lastCandidate
,
1104 "tree traversal trouble in ContentSubtreeIterator::Init");
1107 if (!lastCandidate
) {
1108 // then lastCandidate is prev node before node
1109 lastCandidate
= ContentIteratorBase::GetPrevSibling(
1110 node
, IterAllowCrossShadowBoundary());
1113 if (lastCandidate
) {
1114 lastCandidate
= ContentIteratorBase::GetDeepLastChild(
1115 lastCandidate
, IterAllowCrossShadowBoundary());
1118 return lastCandidate
;
1121 nsresult
ContentSubtreeIterator::InitWithRange() {
1123 MOZ_ASSERT(mRange
->IsPositioned());
1125 // get the start node and offset, convert to nsINode
1126 mClosestCommonInclusiveAncestor
=
1127 mRange
->GetClosestCommonInclusiveAncestor(mAllowCrossShadowBoundary
);
1129 nsINode
* startContainer
= IteratorHelpers::GetStartContainer(
1130 mRange
, IterAllowCrossShadowBoundary());
1131 const int32_t startOffset
=
1132 IteratorHelpers::StartOffset(mRange
, IterAllowCrossShadowBoundary());
1133 nsINode
* endContainer
=
1134 IteratorHelpers::GetEndContainer(mRange
, IterAllowCrossShadowBoundary());
1135 const int32_t endOffset
=
1136 IteratorHelpers::EndOffset(mRange
, IterAllowCrossShadowBoundary());
1137 MOZ_ASSERT(mClosestCommonInclusiveAncestor
&& startContainer
&& endContainer
);
1139 MOZ_ASSERT(uint32_t(startOffset
) <= startContainer
->Length() &&
1140 uint32_t(endOffset
) <= endContainer
->Length());
1142 // short circuit when start node == end node
1143 if (startContainer
== endContainer
) {
1144 nsINode
* child
= startContainer
->GetFirstChild();
1146 if (!child
|| startOffset
== endOffset
) {
1147 // Text node, empty container, or collapsed
1153 CacheInclusiveAncestorsOfEndContainer();
1155 mFirst
= DetermineFirstContent();
1161 mLast
= DetermineLastContent();
1172 nsIContent
* ContentSubtreeIterator::DetermineLastContent() const {
1173 nsIContent
* lastCandidate
= DetermineCandidateForLastContent();
1174 if (!lastCandidate
) {
1178 // confirm that this last possible contained node is indeed contained. Else
1179 // we have a range that does not fully contain any node.
1181 const Maybe
<bool> isNodeContainedInRange
=
1182 RangeUtils::IsNodeContainedInRange(*lastCandidate
, mRange
);
1183 MOZ_ALWAYS_TRUE(isNodeContainedInRange
);
1184 if (!isNodeContainedInRange
.value()) {
1188 // cool, we have the last node in the range. Now we walk up its ancestors to
1189 // find the most senior that is still in the range. That's the real first
1191 return GetTopAncestorInRange(lastCandidate
);
1194 /****************************************************************
1195 * ContentSubtreeIterator overrides of ContentIterator routines
1196 ****************************************************************/
1198 // we can't call PositionAt in a subtree iterator...
1199 void ContentSubtreeIterator::First() { mCurNode
= mFirst
; }
1201 // we can't call PositionAt in a subtree iterator...
1202 void ContentSubtreeIterator::Last() { mCurNode
= mLast
; }
1204 void ContentSubtreeIterator::Next() {
1209 if (mCurNode
== mLast
) {
1214 nsINode
* nextNode
= ContentIteratorBase::GetNextSibling(
1215 mCurNode
, IterAllowCrossShadowBoundary());
1217 NS_ASSERTION(nextNode
, "No next sibling!?! This could mean deadlock!");
1219 int32_t i
= mInclusiveAncestorsOfEndContainer
.IndexOf(nextNode
);
1221 // as long as we are finding ancestors of the endpoint of the range,
1222 // dive down into their children
1223 ShadowRoot
* root
= IteratorHelpers::GetShadowRoot(
1224 Element::FromNode(nextNode
), IterAllowCrossShadowBoundary());
1226 nextNode
= nextNode
->GetFirstChild();
1228 nextNode
= mRange
->MayCrossShadowBoundary() ? root
->GetFirstChild()
1229 : nextNode
->GetFirstChild();
1231 NS_ASSERTION(nextNode
, "Iterator error, expected a child node!");
1233 // should be impossible to get a null pointer. If we went all the way
1234 // down the child chain to the bottom without finding an interior node,
1235 // then the previous node should have been the last, which was
1236 // was tested at top of routine.
1237 i
= mInclusiveAncestorsOfEndContainer
.IndexOf(nextNode
);
1240 mCurNode
= nextNode
;
1243 void ContentSubtreeIterator::Prev() {
1244 // Prev should be optimized to use the mStartNodes, just as Next
1245 // uses mInclusiveAncestorsOfEndContainer.
1250 if (mCurNode
== mFirst
) {
1255 // If any of these function calls return null, so will all succeeding ones,
1256 // so mCurNode will wind up set to null.
1257 nsINode
* prevNode
= ContentIteratorBase::GetDeepFirstChild(mCurNode
);
1259 prevNode
= PrevNode(prevNode
);
1261 prevNode
= ContentIteratorBase::GetDeepLastChild(prevNode
);
1263 mCurNode
= GetTopAncestorInRange(prevNode
);
1266 nsresult
ContentSubtreeIterator::PositionAt(nsINode
* aCurNode
) {
1267 NS_ERROR("Not implemented!");
1268 return NS_ERROR_NOT_IMPLEMENTED
;
1271 /****************************************************************
1272 * ContentSubtreeIterator helper routines
1273 ****************************************************************/
1275 nsIContent
* ContentSubtreeIterator::GetTopAncestorInRange(
1276 nsINode
* aNode
) const {
1278 !IteratorHelpers::GetParentNode(*aNode
, IterAllowCrossShadowBoundary())) {
1282 // aNode has a parent, so it must be content.
1283 nsIContent
* content
= aNode
->AsContent();
1285 // sanity check: aNode is itself in the range
1286 Maybe
<bool> isNodeContainedInRange
=
1287 RangeUtils::IsNodeContainedInRange(*aNode
, mRange
);
1288 NS_ASSERTION(isNodeContainedInRange
&& isNodeContainedInRange
.value(),
1289 "aNode isn't in mRange, or something else weird happened");
1290 if (!isNodeContainedInRange
|| !isNodeContainedInRange
.value()) {
1294 nsIContent
* lastContentInShadowTree
= nullptr;
1296 nsINode
* parent
= IteratorHelpers::GetParentNode(
1297 *content
, IterAllowCrossShadowBoundary());
1299 // content always has a parent. If its parent is the root, however --
1300 // i.e., either it's not content, or it is content but its own parent is
1301 // null -- then we're finished, since we don't go up to the root.
1303 // Caveat: If iteration crossing shadow boundary is allowed
1304 // and the root is a shadow root, we keep going up to the
1305 // shadow host and continue.
1307 // We have to special-case this because CompareNodeToRange treats the root
1308 // node differently -- see bug 765205.
1309 if (!parent
|| !IteratorHelpers::GetParentNode(
1310 *parent
, IterAllowCrossShadowBoundary())) {
1314 isNodeContainedInRange
=
1315 RangeUtils::IsNodeContainedInRange(*parent
, mRange
);
1316 MOZ_ALWAYS_TRUE(isNodeContainedInRange
);
1317 if (!isNodeContainedInRange
.value()) {
1318 if (IterAllowCrossShadowBoundary() && content
->IsShadowRoot()) {
1319 MOZ_ASSERT(parent
->GetShadowRoot() == content
);
1320 // host element is not in range, the last content in tree
1321 // should be the ancestor.
1322 MOZ_ASSERT(lastContentInShadowTree
);
1323 return lastContentInShadowTree
;
1328 // When we cross the boundary, we keep a reference to the
1329 // last content that is in tree, because if we later
1330 // find the shadow host element is not in the range, that means
1331 // the last content in the tree should be top ancestor in range.
1333 // Using shadow root doesn't make sense here because it doesn't
1334 // represent a actual content.
1335 if (IterAllowCrossShadowBoundary() && parent
->IsShadowRoot()) {
1336 lastContentInShadowTree
= content
;
1339 content
= parent
->AsContent();
1342 MOZ_CRASH("This should only be possible if aNode was null");
1345 #undef NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD
1347 } // namespace mozilla