ContentIterator.cpp (47927B)
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/Assertions.h" 10 #include "mozilla/DebugOnly.h" 11 #include "mozilla/RangeBoundary.h" 12 #include "mozilla/RangeUtils.h" 13 #include "mozilla/Result.h" 14 #include "mozilla/dom/HTMLSlotElement.h" 15 #include "mozilla/dom/ShadowRoot.h" 16 #include "nsContentUtils.h" 17 #include "nsElementTable.h" 18 #include "nsIContent.h" 19 #include "nsRange.h" 20 21 namespace mozilla { 22 23 using namespace dom; 24 25 #define NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(aResultType, aMethodName, ...) \ 26 template aResultType ContentIteratorBase<RefPtr<nsINode>>::aMethodName( \ 27 __VA_ARGS__); \ 28 template aResultType ContentIteratorBase<nsINode*>::aMethodName(__VA_ARGS__) 29 30 static bool ComparePostMode(const RawRangeBoundary& aStart, 31 const RawRangeBoundary& aEnd, nsINode& aNode) { 32 nsINode* parent = aNode.GetParentNode(); 33 if (!parent) { 34 return false; 35 } 36 37 // aNode should always be content, as we have a parent, but let's just be 38 // extra careful and check. 39 nsIContent* content = 40 NS_WARN_IF(!aNode.IsContent()) ? nullptr : aNode.AsContent(); 41 42 // Post mode: start < node <= end. 43 RawRangeBoundary afterNode(parent, content); 44 const auto isStartLessThanAfterNode = [&]() { 45 const Maybe<int32_t> startComparedToAfterNode = 46 nsContentUtils::ComparePoints(aStart, afterNode); 47 return !NS_WARN_IF(!startComparedToAfterNode) && 48 (*startComparedToAfterNode < 0); 49 }; 50 51 const auto isAfterNodeLessOrEqualToEnd = [&]() { 52 const Maybe<int32_t> afterNodeComparedToEnd = 53 nsContentUtils::ComparePoints(afterNode, aEnd); 54 return !NS_WARN_IF(!afterNodeComparedToEnd) && 55 (*afterNodeComparedToEnd <= 0); 56 }; 57 58 return isStartLessThanAfterNode() && isAfterNodeLessOrEqualToEnd(); 59 } 60 61 static bool ComparePreMode(const RawRangeBoundary& aStart, 62 const RawRangeBoundary& aEnd, nsINode& aNode) { 63 nsINode* parent = aNode.GetParentNode(); 64 if (!parent) { 65 return false; 66 } 67 68 // Pre mode: start <= node < end. 69 RawRangeBoundary beforeNode(parent, aNode.GetPreviousSibling()); 70 71 const auto isStartLessOrEqualToBeforeNode = [&]() { 72 const Maybe<int32_t> startComparedToBeforeNode = 73 nsContentUtils::ComparePoints(aStart, beforeNode); 74 return !NS_WARN_IF(!startComparedToBeforeNode) && 75 (*startComparedToBeforeNode <= 0); 76 }; 77 78 const auto isBeforeNodeLessThanEndNode = [&]() { 79 const Maybe<int32_t> beforeNodeComparedToEnd = 80 nsContentUtils::ComparePoints(beforeNode, aEnd); 81 return !NS_WARN_IF(!beforeNodeComparedToEnd) && 82 (*beforeNodeComparedToEnd < 0); 83 }; 84 85 return isStartLessOrEqualToBeforeNode() && isBeforeNodeLessThanEndNode(); 86 } 87 88 /////////////////////////////////////////////////////////////////////////// 89 // NodeIsInTraversalRange: returns true if content is visited during 90 // the traversal of the range in the specified mode. 91 // 92 static bool NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode, 93 const RawRangeBoundary& aStart, 94 const RawRangeBoundary& aEnd) { 95 if (NS_WARN_IF(!aStart.IsSet()) || NS_WARN_IF(!aEnd.IsSet()) || 96 NS_WARN_IF(!aNode)) { 97 return false; 98 } 99 100 // If a leaf node contains an end point of the traversal range, it is 101 // always in the traversal range. 102 if (aNode == aStart.GetContainer() || aNode == aEnd.GetContainer()) { 103 if (aNode->IsCharacterData()) { 104 return true; // text node or something 105 } 106 if (!aNode->HasChildren()) { 107 MOZ_ASSERT( 108 aNode != aStart.GetContainer() || aStart.IsStartOfContainer(), 109 "aStart.GetContainer() doesn't have children and not a data node, " 110 "aStart should be at the beginning of its container"); 111 MOZ_ASSERT( 112 aNode != aEnd.GetContainer() || aEnd.IsStartOfContainer(), 113 "aEnd.GetContainer() doesn't have children and not a data node, " 114 "aEnd should be at the beginning of its container"); 115 return true; 116 } 117 } 118 119 if (aIsPreMode) { 120 return ComparePreMode(aStart, aEnd, *aNode); 121 } 122 123 return ComparePostMode(aStart, aEnd, *aNode); 124 } 125 126 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback, 127 PostContentIterator& aField, const char* aName, 128 uint32_t aFlags = 0) { 129 ImplCycleCollectionTraverse( 130 aCallback, static_cast<SafeContentIteratorBase&>(aField), aName, aFlags); 131 } 132 133 void ImplCycleCollectionUnlink(PostContentIterator& aField) { 134 ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase&>(aField)); 135 } 136 137 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback, 138 PreContentIterator& aField, const char* aName, 139 uint32_t aFlags = 0) { 140 ImplCycleCollectionTraverse( 141 aCallback, static_cast<SafeContentIteratorBase&>(aField), aName, aFlags); 142 } 143 144 void ImplCycleCollectionUnlink(PreContentIterator& aField) { 145 ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase&>(aField)); 146 } 147 148 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback, 149 ContentSubtreeIterator& aField, 150 const char* aName, uint32_t aFlags = 0) { 151 ImplCycleCollectionTraverse(aCallback, aField.mRange, aName, aFlags); 152 ImplCycleCollectionTraverse( 153 aCallback, static_cast<SafeContentIteratorBase&>(aField), aName, aFlags); 154 } 155 156 void ImplCycleCollectionUnlink(ContentSubtreeIterator& aField) { 157 ImplCycleCollectionUnlink(aField.mRange); 158 ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase&>(aField)); 159 } 160 161 /****************************************************** 162 * ContentIteratorBase 163 ******************************************************/ 164 165 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(, ContentIteratorBase, Order); 166 167 template <typename NodeType> 168 ContentIteratorBase<NodeType>::ContentIteratorBase(Order aOrder) 169 : mOrder(aOrder) {} 170 171 template ContentIteratorBase<RefPtr<nsINode>>::~ContentIteratorBase(); 172 template ContentIteratorBase<nsINode*>::~ContentIteratorBase(); 173 174 template <typename NodeType> 175 ContentIteratorBase<NodeType>::~ContentIteratorBase() { 176 MOZ_DIAGNOSTIC_ASSERT_IF(mMutationGuard.isSome(), 177 !mMutationGuard->Mutated(0)); 178 } 179 180 /****************************************************** 181 * Init routines 182 ******************************************************/ 183 184 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, nsINode*); 185 186 template <typename NodeType> 187 nsresult ContentIteratorBase<NodeType>::Init(nsINode* aRoot) { 188 if (NS_WARN_IF(!aRoot)) { 189 return NS_ERROR_NULL_POINTER; 190 } 191 192 if (mOrder == Order::Pre) { 193 mFirst = aRoot; 194 mLast = ContentIteratorBase::GetDeepLastChild(aRoot); 195 NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null"); 196 } else { 197 mFirst = ContentIteratorBase::GetDeepFirstChild(aRoot); 198 NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null"); 199 mLast = aRoot; 200 } 201 202 mClosestCommonInclusiveAncestor = aRoot; 203 mCurNode = mFirst; 204 return NS_OK; 205 } 206 207 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, AbstractRange*); 208 209 template <typename NodeType> 210 nsresult ContentIteratorBase<NodeType>::Init(AbstractRange* aRange) { 211 if (NS_WARN_IF(!aRange)) { 212 return NS_ERROR_INVALID_ARG; 213 } 214 215 if (NS_WARN_IF(!aRange->IsPositioned())) { 216 return NS_ERROR_INVALID_ARG; 217 } 218 219 return InitInternal(aRange->StartRef().AsRaw(), aRange->EndRef().AsRaw()); 220 } 221 222 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, nsINode*, uint32_t, 223 nsINode*, uint32_t); 224 225 template <typename NodeType> 226 nsresult ContentIteratorBase<NodeType>::Init(nsINode* aStartContainer, 227 uint32_t aStartOffset, 228 nsINode* aEndContainer, 229 uint32_t aEndOffset) { 230 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStartContainer, aStartOffset, 231 aEndContainer, aEndOffset))) { 232 return NS_ERROR_INVALID_ARG; 233 } 234 235 return InitInternal(RawRangeBoundary(aStartContainer, aStartOffset), 236 RawRangeBoundary(aEndContainer, aEndOffset)); 237 } 238 239 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, const RawRangeBoundary&, 240 const RawRangeBoundary&); 241 242 template <typename NodeType> 243 nsresult ContentIteratorBase<NodeType>::Init(const RawRangeBoundary& aStart, 244 const RawRangeBoundary& aEnd) { 245 if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStart, aEnd))) { 246 return NS_ERROR_INVALID_ARG; 247 } 248 249 return InitInternal(aStart, aEnd); 250 } 251 252 template <typename NodeType> 253 nsresult ContentIteratorBase<NodeType>::InitWithoutValidatingPoints( 254 const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) { 255 MOZ_DIAGNOSTIC_ASSERT(RangeUtils::IsValidPoints(aStart, aEnd)); 256 return InitInternal(aStart, aEnd); 257 } 258 259 template <typename NodeType> 260 class MOZ_STACK_CLASS ContentIteratorBase<NodeType>::Initializer final { 261 public: 262 Initializer(ContentIteratorBase<NodeType>& aIterator, 263 const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) 264 : mIterator{aIterator}, 265 mStart{aStart}, 266 mEnd{aEnd}, 267 mStartIsCharacterData{mStart.GetContainer()->IsCharacterData()} { 268 MOZ_ASSERT(mStart.IsSetAndValid()); 269 MOZ_ASSERT(mEnd.IsSetAndValid()); 270 } 271 272 nsresult Run(); 273 274 private: 275 /** 276 * @return may be nullptr. 277 */ 278 nsINode* DetermineFirstNode() const; 279 280 /** 281 * @return may be nullptr. 282 */ 283 [[nodiscard]] Result<nsINode*, nsresult> DetermineLastNode() const; 284 285 bool IsCollapsedNonCharacterRange() const; 286 bool IsSingleNodeCharacterRange() const; 287 288 ContentIteratorBase& mIterator; 289 const RawRangeBoundary& mStart; 290 const RawRangeBoundary& mEnd; 291 const bool mStartIsCharacterData; 292 }; 293 294 template <> 295 nsresult ContentIteratorBase<RefPtr<nsINode>>::InitInternal( 296 const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) { 297 Initializer initializer{*this, aStart, aEnd}; 298 return initializer.Run(); 299 } 300 301 template <> 302 nsresult ContentIteratorBase<nsINode*>::InitInternal( 303 const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) { 304 Initializer initializer{*this, aStart, aEnd}; 305 nsresult rv = initializer.Run(); 306 if (NS_FAILED(rv)) { 307 return rv; 308 } 309 mMutationGuard.emplace(); 310 mAssertNoGC.emplace(); 311 return NS_OK; 312 } 313 314 template <typename NodeType> 315 bool ContentIteratorBase<NodeType>::Initializer::IsCollapsedNonCharacterRange() 316 const { 317 return !mStartIsCharacterData && mStart == mEnd; 318 } 319 320 template <typename NodeType> 321 bool ContentIteratorBase<NodeType>::Initializer::IsSingleNodeCharacterRange() 322 const { 323 return mStartIsCharacterData && mStart.GetContainer() == mEnd.GetContainer(); 324 } 325 326 template <typename NodeType> 327 nsresult ContentIteratorBase<NodeType>::Initializer::Run() { 328 // get common content parent 329 mIterator.mClosestCommonInclusiveAncestor = 330 nsContentUtils::GetClosestCommonInclusiveAncestor(mStart.GetContainer(), 331 mEnd.GetContainer()); 332 if (NS_WARN_IF(!mIterator.mClosestCommonInclusiveAncestor)) { 333 return NS_ERROR_FAILURE; 334 } 335 336 // Check to see if we have a collapsed range, if so, there is nothing to 337 // iterate over. 338 // 339 // XXX: CharacterDataNodes (text nodes) are currently an exception, since 340 // we always want to be able to iterate text nodes at the end points 341 // of a range. 342 343 if (IsCollapsedNonCharacterRange()) { 344 mIterator.SetEmpty(); 345 return NS_OK; 346 } 347 348 if (IsSingleNodeCharacterRange()) { 349 mIterator.mFirst = mStart.GetContainer()->AsContent(); 350 mIterator.mLast = mIterator.mFirst; 351 mIterator.mCurNode = mIterator.mFirst; 352 353 return NS_OK; 354 } 355 356 mIterator.mFirst = DetermineFirstNode(); 357 358 if (Result<nsINode*, nsresult> lastNode = DetermineLastNode(); 359 NS_WARN_IF(lastNode.isErr())) { 360 return lastNode.unwrapErr(); 361 } else { 362 mIterator.mLast = lastNode.unwrap(); 363 } 364 365 // If either first or last is null, they both have to be null! 366 if (!mIterator.mFirst || !mIterator.mLast) { 367 mIterator.SetEmpty(); 368 } 369 370 mIterator.mCurNode = mIterator.mFirst; 371 372 return NS_OK; 373 } 374 375 template <typename NodeType> 376 nsINode* ContentIteratorBase<NodeType>::Initializer::DetermineFirstNode() 377 const { 378 nsIContent* cChild = nullptr; 379 380 // Try to get the child at our starting point. This might return null if 381 // mStart is immediately after the last node in mStart.GetContainer(). 382 if (!mStartIsCharacterData) { 383 cChild = mStart.GetChildAtOffset(); 384 } 385 386 if (!cChild) { 387 // No children (possibly a <br> or text node), or index is after last child. 388 389 if (mIterator.mOrder == Order::Pre) { 390 // XXX: In the future, if start offset is after the last 391 // character in the cdata node, should we set mFirst to 392 // the next sibling? 393 394 // Normally we would skip the start node because the start node is outside 395 // of the range in pre mode. However, if aStartOffset == 0, and the node 396 // is a non-container node (e.g. <br>), we don't skip the node in this 397 // case in order to address bug 1215798. 398 bool startIsContainer = true; 399 if (mStart.GetContainer()->IsHTMLElement()) { 400 nsAtom* name = mStart.GetContainer()->NodeInfo()->NameAtom(); 401 startIsContainer = 402 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name)); 403 } 404 if (!mStartIsCharacterData && 405 (startIsContainer || !mStart.IsStartOfContainer())) { 406 nsINode* const result = 407 ContentIteratorBase::GetNextSibling(mStart.GetContainer()); 408 NS_WARNING_ASSERTION(result, "GetNextSibling returned null"); 409 410 // Does mFirst node really intersect the range? The range could be 411 // 'degenerate', i.e., not collapsed but still contain no content. 412 if (result && 413 NS_WARN_IF(!NodeIsInTraversalRange( 414 result, mIterator.mOrder == Order::Pre, mStart, mEnd))) { 415 return nullptr; 416 } 417 418 return result; 419 } 420 return mStart.GetContainer()->AsContent(); 421 } 422 423 // post-order 424 if (NS_WARN_IF(!mStart.GetContainer()->IsContent())) { 425 // What else can we do? 426 return nullptr; 427 } 428 return mStart.GetContainer()->AsContent(); 429 } 430 431 if (mIterator.mOrder == Order::Pre) { 432 return cChild; 433 } 434 435 // post-order 436 nsINode* const result = ContentIteratorBase::GetDeepFirstChild(cChild); 437 NS_WARNING_ASSERTION(result, "GetDeepFirstChild returned null"); 438 439 // Does mFirst node really intersect the range? The range could be 440 // 'degenerate', i.e., not collapsed but still contain no content. 441 if (result && !NodeIsInTraversalRange(result, mIterator.mOrder == Order::Pre, 442 mStart, mEnd)) { 443 return nullptr; 444 } 445 446 return result; 447 } 448 449 template <typename NodeType> 450 Result<nsINode*, nsresult> 451 ContentIteratorBase<NodeType>::Initializer::DetermineLastNode() const { 452 const bool endIsCharacterData = mEnd.GetContainer()->IsCharacterData(); 453 454 if (endIsCharacterData || !mEnd.GetContainer()->HasChildren() || 455 mEnd.IsStartOfContainer()) { 456 if (mIterator.mOrder == Order::Pre) { 457 if (NS_WARN_IF(!mEnd.GetContainer()->IsContent())) { 458 // Not much else to do here... 459 return nullptr; 460 } 461 462 // If the end node is a non-container element and the end offset is 0, 463 // the last element should be the previous node (i.e., shouldn't 464 // include the end node in the range). 465 bool endIsContainer = true; 466 if (mEnd.GetContainer()->IsHTMLElement()) { 467 nsAtom* name = mEnd.GetContainer()->NodeInfo()->NameAtom(); 468 endIsContainer = 469 nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name)); 470 } 471 if (!endIsCharacterData && !endIsContainer && mEnd.IsStartOfContainer()) { 472 nsINode* const result = mIterator.PrevNode(mEnd.GetContainer()); 473 NS_WARNING_ASSERTION(result, "PrevNode returned null"); 474 if (result && result != mIterator.mFirst && 475 NS_WARN_IF(!NodeIsInTraversalRange( 476 result, mIterator.mOrder == Order::Pre, 477 RawRangeBoundary(mIterator.mFirst, 0u), mEnd))) { 478 return nullptr; 479 } 480 481 return result; 482 } 483 484 return mEnd.GetContainer()->AsContent(); 485 } 486 487 // post-order 488 // 489 // XXX: In the future, if end offset is before the first character in the 490 // cdata node, should we set mLast to the prev sibling? 491 492 if (!endIsCharacterData) { 493 nsINode* const result = 494 ContentIteratorBase::GetPrevSibling(mEnd.GetContainer()); 495 NS_WARNING_ASSERTION(result, "GetPrevSibling returned null"); 496 497 if (!NodeIsInTraversalRange(result, mIterator.mOrder == Order::Pre, 498 mStart, mEnd)) { 499 return nullptr; 500 } 501 return result; 502 } 503 return mEnd.GetContainer()->AsContent(); 504 } 505 506 nsIContent* cChild = mEnd.Ref(); 507 508 if (NS_WARN_IF(!cChild)) { 509 // No child at offset! 510 MOZ_ASSERT_UNREACHABLE("ContentIterator::ContentIterator"); 511 return Err(NS_ERROR_FAILURE); 512 } 513 514 if (mIterator.mOrder == Order::Pre) { 515 nsINode* const result = ContentIteratorBase::GetDeepLastChild(cChild); 516 NS_WARNING_ASSERTION(result, "GetDeepLastChild returned null"); 517 518 if (NS_WARN_IF(!NodeIsInTraversalRange( 519 result, mIterator.mOrder == Order::Pre, mStart, mEnd))) { 520 return nullptr; 521 } 522 523 return result; 524 } 525 526 // post-order 527 return cChild; 528 } 529 530 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, SetEmpty); 531 532 template <typename NodeType> 533 void ContentIteratorBase<NodeType>::SetEmpty() { 534 mCurNode = nullptr; 535 mFirst = nullptr; 536 mLast = nullptr; 537 mClosestCommonInclusiveAncestor = nullptr; 538 } 539 540 // static 541 template <typename NodeType> 542 nsINode* ContentIteratorBase<NodeType>::GetDeepFirstChild(nsINode* aRoot) { 543 if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) { 544 return aRoot; 545 } 546 547 return ContentIteratorBase::GetDeepFirstChild(aRoot->GetFirstChild()); 548 } 549 550 // static 551 template <typename NodeType> 552 nsIContent* ContentIteratorBase<NodeType>::GetDeepFirstChild( 553 nsIContent* aRoot, 554 AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) { 555 if (NS_WARN_IF(!aRoot)) { 556 return nullptr; 557 } 558 559 nsIContent* node = aRoot; 560 nsIContent* child = nullptr; 561 562 if (ShadowRoot* shadowRoot = ShadowDOMSelectionHelpers::GetShadowRoot( 563 node, aAllowCrossShadowBoundary)) { 564 // When finding the deepest child of node, if this node has a 565 // web exposed shadow root, we use this shadow root to find the deepest 566 // child. 567 // If the first candidate should be a slotted content, 568 // shadowRoot->GetFirstChild() should be able to return the <slot> element. 569 // It's probably correct I think. Then it's up to the caller of this 570 // iterator to decide whether to use the slot's assigned nodes or not. 571 MOZ_ASSERT(aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes); 572 child = shadowRoot->GetFirstChild(); 573 } else { 574 child = node->GetFirstChild(); 575 } 576 577 while (child) { 578 node = child; 579 if (ShadowRoot* shadowRoot = ShadowDOMSelectionHelpers::GetShadowRoot( 580 node, aAllowCrossShadowBoundary)) { 581 // When finding the deepest child of node, if this node has a 582 // web exposed shadow root, we use this shadow root to find the deepest 583 // child. 584 // If the first candidate should be a slotted content, 585 // shadowRoot->GetFirstChild() should be able to return the <slot> 586 // element. It's probably correct I think. Then it's up to the caller of 587 // this iterator to decide whether to use the slot's assigned nodes or 588 // not. 589 child = shadowRoot->GetFirstChild(); 590 } else { 591 child = node->GetFirstChild(); 592 } 593 } 594 595 return node; 596 } 597 598 // static 599 template <typename NodeType> 600 nsINode* ContentIteratorBase<NodeType>::GetDeepLastChild(nsINode* aRoot) { 601 if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) { 602 return aRoot; 603 } 604 605 return ContentIteratorBase::GetDeepLastChild(aRoot->GetLastChild()); 606 } 607 608 // static 609 template <typename NodeType> 610 nsIContent* ContentIteratorBase<NodeType>::GetDeepLastChild( 611 nsIContent* aRoot, 612 AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) { 613 if (NS_WARN_IF(!aRoot)) { 614 return nullptr; 615 } 616 617 nsIContent* node = aRoot; 618 619 while (HTMLSlotElement* slot = HTMLSlotElement::FromNode(node)) { 620 auto assigned = slot->AssignedNodes(); 621 // The deep last child of a slot should be the last slotted element of it 622 if (!assigned.IsEmpty()) { 623 node = assigned[assigned.Length() - 1]->AsContent(); 624 continue; 625 } 626 break; 627 } 628 629 ShadowRoot* shadowRoot = 630 ShadowDOMSelectionHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary); 631 while (node->HasChildren() || (shadowRoot && shadowRoot->HasChildren())) { 632 if (node->HasChildren()) { 633 node = node->GetLastChild(); 634 } else { 635 MOZ_ASSERT(shadowRoot); 636 // If this node doesn't have a child, but it's also a shadow host 637 // that can be selected, we go into this shadow tree. 638 node = shadowRoot->GetLastChild(); 639 } 640 shadowRoot = ShadowDOMSelectionHelpers::GetShadowRoot( 641 node, aAllowCrossShadowBoundary); 642 } 643 return node; 644 } 645 646 // Get the next sibling, or parent's next sibling, or shadow host's next 647 // sibling (when aAllowCrossShadowBoundary is true), or grandpa's next 648 // sibling... 649 // 650 // static 651 // 652 template <typename NodeType> 653 nsIContent* ContentIteratorBase<NodeType>::GetNextSibling( 654 nsINode* aNode, AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary, 655 nsTArray<AncestorInfo>* aInclusiveAncestorsOfEndContainer) { 656 if (NS_WARN_IF(!aNode)) { 657 return nullptr; 658 } 659 660 if (aNode->IsContent() && 661 aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes) { 662 // Could have nested slots 663 while (HTMLSlotElement* slot = aNode->AsContent()->GetAssignedSlot()) { 664 if (!ShadowDOMSelectionHelpers::GetShadowRoot( 665 slot->GetContainingShadowHost(), aAllowCrossShadowBoundary)) { 666 // The corresponding shadow host isn't supported 667 // by ContentSubtreeIterator, so let's skip this slot. 668 break; 669 } 670 671 // Next sibling of a slotted node should be the next slotted node 672 auto assigned = slot->AssignedNodes(); 673 auto cur = assigned.IndexOf(aNode); 674 if (cur != assigned.npos && cur + 1 < assigned.Length()) { 675 return assigned[cur + 1]->AsContent(); 676 } 677 // Move on to assigned slot's next sibling 678 aNode = slot; 679 } 680 } 681 682 if (nsIContent* next = aNode->GetNextSibling()) { 683 return next; 684 } 685 686 nsINode* parent = ShadowDOMSelectionHelpers::GetParentNodeInSameSelection( 687 *aNode, aAllowCrossShadowBoundary); 688 if (NS_WARN_IF(!parent)) { 689 return nullptr; 690 } 691 692 // We now have finished iterating descendants within this shadow root, and 693 // reached to the shadow host. 694 if (aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes && 695 aInclusiveAncestorsOfEndContainer && parent->GetShadowRoot() == aNode) { 696 const int32_t i = aInclusiveAncestorsOfEndContainer->IndexOf( 697 parent, 0, InclusiveAncestorComparator()); 698 699 // If parent is an ancestor of the end container, we return the parent so 700 // that the caller (ContentSubtreeIterator::Next) can stop the iteration. 701 // 702 // This is only a special case for ShadowDOM selection where 703 // the end container is in light DOM and we have to iterate 704 // shadow DOM nodes first. We would have reached to mLast 705 // already if this isn't the case. 706 if (i != -1) { 707 MOZ_ASSERT(!aInclusiveAncestorsOfEndContainer->ElementAt(i) 708 .mIsDescendantInShadowTree); 709 return parent->AsContent(); 710 } 711 } 712 713 return ContentIteratorBase::GetNextSibling(parent, aAllowCrossShadowBoundary, 714 aInclusiveAncestorsOfEndContainer); 715 } 716 717 // Get the prev sibling, or parent's prev sibling, or shadow host's prev sibling 718 // (when aAllowCrossShadowBoundary is true), or grandpa's prev sibling... static 719 template <typename NodeType> 720 nsIContent* ContentIteratorBase<NodeType>::GetPrevSibling( 721 nsINode* aNode, AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary) { 722 if (NS_WARN_IF(!aNode)) { 723 return nullptr; 724 } 725 726 if (aNode->IsContent() && 727 aAllowCrossShadowBoundary == AllowRangeCrossShadowBoundary::Yes) { 728 // Could have nested slots. 729 while (HTMLSlotElement* slot = aNode->AsContent()->GetAssignedSlot()) { 730 if (!ShadowDOMSelectionHelpers::GetShadowRoot( 731 slot->GetContainingShadowHost(), aAllowCrossShadowBoundary)) { 732 // The corresponding shadow host isn't supported 733 // by ContentSubtreeIterator, so let's skip this slot. 734 break; 735 } 736 // prev sibling of a slotted node should be the prev slotted node 737 auto assigned = slot->AssignedNodes(); 738 auto cur = assigned.IndexOf(aNode); 739 if (cur != assigned.npos && cur != 0) { 740 return assigned[cur - 1]->AsContent(); 741 } 742 aNode = slot; 743 } 744 } 745 746 if (nsIContent* prev = aNode->GetPreviousSibling()) { 747 return prev; 748 } 749 750 nsINode* parent = ShadowDOMSelectionHelpers::GetParentNodeInSameSelection( 751 *aNode, aAllowCrossShadowBoundary); 752 if (NS_WARN_IF(!parent)) { 753 return nullptr; 754 } 755 756 return ContentIteratorBase::GetPrevSibling(parent, aAllowCrossShadowBoundary); 757 } 758 759 template <typename NodeType> 760 nsINode* ContentIteratorBase<NodeType>::NextNode(nsINode* aNode) { 761 nsINode* node = aNode; 762 763 // if we are a Pre-order iterator, use pre-order 764 if (mOrder == Order::Pre) { 765 // if it has children then next node is first child 766 if (node->HasChildren()) { 767 nsIContent* firstChild = node->GetFirstChild(); 768 MOZ_ASSERT(firstChild); 769 770 return firstChild; 771 } 772 773 // else next sibling is next 774 return ContentIteratorBase::GetNextSibling(node); 775 } 776 777 // post-order 778 nsINode* parent = node->GetParentNode(); 779 if (NS_WARN_IF(!parent)) { 780 MOZ_ASSERT(parent, "The node is the root node but not the last node"); 781 mCurNode = nullptr; 782 return node; 783 } 784 785 if (nsIContent* sibling = node->GetNextSibling()) { 786 // next node is sibling's "deep left" child 787 return ContentIteratorBase::GetDeepFirstChild(sibling); 788 } 789 790 return parent; 791 } 792 793 template <typename NodeType> 794 nsINode* ContentIteratorBase<NodeType>::PrevNode(nsINode* aNode) { 795 nsINode* node = aNode; 796 797 // if we are a Pre-order iterator, use pre-order 798 if (mOrder == Order::Pre) { 799 nsINode* parent = node->GetParentNode(); 800 if (NS_WARN_IF(!parent)) { 801 MOZ_ASSERT(parent, "The node is the root node but not the first node"); 802 mCurNode = nullptr; 803 return aNode; 804 } 805 806 nsIContent* sibling = node->GetPreviousSibling(); 807 if (sibling) { 808 return ContentIteratorBase::GetDeepLastChild(sibling); 809 } 810 811 return parent; 812 } 813 814 // post-order 815 if (node->HasChildren()) { 816 return node->GetLastChild(); 817 } 818 819 // else prev sibling is previous 820 return ContentIteratorBase::GetPrevSibling(node); 821 } 822 823 /****************************************************** 824 * ContentIteratorBase routines 825 ******************************************************/ 826 827 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, First); 828 829 template <typename NodeType> 830 void ContentIteratorBase<NodeType>::First() { 831 if (!mFirst) { 832 MOZ_ASSERT(IsDone()); 833 mCurNode = nullptr; 834 return; 835 } 836 837 mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst); 838 NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!"); 839 } 840 841 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Last); 842 843 template <typename NodeType> 844 void ContentIteratorBase<NodeType>::Last() { 845 // Note that mLast can be nullptr if SetEmpty() is called in Init() 846 // since at that time, Init() returns NS_OK. 847 if (!mLast) { 848 MOZ_ASSERT(IsDone()); 849 mCurNode = nullptr; 850 return; 851 } 852 853 mozilla::DebugOnly<nsresult> rv = PositionAt(mLast); 854 NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!"); 855 } 856 857 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Next); 858 859 template <typename NodeType> 860 void ContentIteratorBase<NodeType>::Next() { 861 if (IsDone()) { 862 return; 863 } 864 865 if (mCurNode == mLast) { 866 mCurNode = nullptr; 867 return; 868 } 869 870 mCurNode = NextNode(mCurNode); 871 } 872 873 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Prev); 874 875 template <typename NodeType> 876 void ContentIteratorBase<NodeType>::Prev() { 877 if (IsDone()) { 878 return; 879 } 880 881 if (mCurNode == mFirst) { 882 mCurNode = nullptr; 883 return; 884 } 885 886 mCurNode = PrevNode(mCurNode); 887 } 888 889 // Keeping arrays of indexes for the stack of nodes makes PositionAt 890 // interesting... 891 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, PositionAt, nsINode*); 892 893 template <typename NodeType> 894 nsresult ContentIteratorBase<NodeType>::PositionAt(nsINode* aCurNode) { 895 if (NS_WARN_IF(!aCurNode)) { 896 return NS_ERROR_NULL_POINTER; 897 } 898 899 // take an early out if this doesn't actually change the position 900 if (mCurNode == aCurNode) { 901 return NS_OK; 902 } 903 mCurNode = aCurNode; 904 905 // Check to see if the node falls within the traversal range. 906 907 RawRangeBoundary first(mFirst, 0u); 908 RawRangeBoundary last(mLast, 0u); 909 910 if (mFirst && mLast) { 911 if (mOrder == Order::Pre) { 912 // In pre we want to record the point immediately before mFirst, which is 913 // the point immediately after mFirst's previous sibling. 914 first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()}; 915 916 // If mLast has no children, then we want to make sure to include it. 917 if (!mLast->HasChildren()) { 918 last = {mLast->GetParentNode(), mLast->AsContent()}; 919 } 920 } else { 921 // If the first node has any children, we want to be immediately after the 922 // last. Otherwise we want to be immediately before mFirst. 923 if (mFirst->HasChildren()) { 924 first = {mFirst, mFirst->GetLastChild()}; 925 } else { 926 first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()}; 927 } 928 929 // Set the last point immediately after the final node. 930 last = {mLast->GetParentNode(), mLast->AsContent()}; 931 } 932 } 933 934 NS_WARNING_ASSERTION(first.IsSetAndValid(), "first is not valid"); 935 NS_WARNING_ASSERTION(last.IsSetAndValid(), "last is not valid"); 936 937 // The end positions are always in the range even if it has no parent. We 938 // need to allow that or 'iter->Init(root)' would assert in Last() or First() 939 // for example, bug 327694. 940 if (mFirst != mCurNode && mLast != mCurNode && 941 (NS_WARN_IF(!first.IsSet()) || NS_WARN_IF(!last.IsSet()) || 942 NS_WARN_IF(!NodeIsInTraversalRange(mCurNode, mOrder == Order::Pre, first, 943 last)))) { 944 mCurNode = nullptr; 945 return NS_ERROR_FAILURE; 946 } 947 948 return NS_OK; 949 } 950 951 /****************************************************** 952 * ContentSubtreeIterator init routines 953 ******************************************************/ 954 955 nsresult ContentSubtreeIterator::Init(nsINode* aRoot) { 956 return NS_ERROR_NOT_IMPLEMENTED; 957 } 958 959 nsresult ContentSubtreeIterator::Init(AbstractRange* aRange) { 960 MOZ_ASSERT(aRange); 961 962 if (NS_WARN_IF(!aRange->IsPositioned())) { 963 return NS_ERROR_INVALID_ARG; 964 } 965 966 mRange = aRange; 967 968 return InitWithRange(); 969 } 970 971 nsresult ContentSubtreeIterator::Init(nsINode* aStartContainer, 972 uint32_t aStartOffset, 973 nsINode* aEndContainer, 974 uint32_t aEndOffset) { 975 return Init(RawRangeBoundary(aStartContainer, aStartOffset), 976 RawRangeBoundary(aEndContainer, aEndOffset)); 977 } 978 979 nsresult ContentSubtreeIterator::Init(const RawRangeBoundary& aStartBoundary, 980 const RawRangeBoundary& aEndBoundary) { 981 RefPtr<nsRange> range = 982 nsRange::Create(aStartBoundary, aEndBoundary, IgnoreErrors()); 983 if (NS_WARN_IF(!range) || NS_WARN_IF(!range->IsPositioned())) { 984 return NS_ERROR_INVALID_ARG; 985 } 986 987 if (NS_WARN_IF(range->MayCrossShadowBoundaryStartRef() != aStartBoundary) || 988 NS_WARN_IF(range->MayCrossShadowBoundaryEndRef() != aEndBoundary)) { 989 // Could happen if the above nsRange::Create decides to collapse 990 // the range, like aStartBoundary is "after" aEndBoundary. 991 return NS_ERROR_UNEXPECTED; 992 } 993 994 mRange = std::move(range); 995 996 return InitWithRange(); 997 } 998 999 nsresult ContentSubtreeIterator::InitWithAllowCrossShadowBoundary( 1000 AbstractRange* aRange) { 1001 MOZ_ASSERT(aRange); 1002 1003 if (NS_WARN_IF(!aRange->IsPositioned())) { 1004 return NS_ERROR_INVALID_ARG; 1005 } 1006 1007 mRange = aRange; 1008 1009 if (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled()) { 1010 mAllowCrossShadowBoundary = AllowRangeCrossShadowBoundary::Yes; 1011 } 1012 return InitWithRange(); 1013 } 1014 1015 void ContentSubtreeIterator::CacheInclusiveAncestorsOfEndContainer() { 1016 mInclusiveAncestorsOfEndContainer.Clear(); 1017 nsINode* const endContainer = ShadowDOMSelectionHelpers::GetEndContainer( 1018 mRange, mAllowCrossShadowBoundary); 1019 nsIContent* endNode = 1020 endContainer->IsContent() ? endContainer->AsContent() : nullptr; 1021 1022 AncestorInfo info{endNode, false}; 1023 while (info.mAncestor) { 1024 const nsINode* child = info.mAncestor; 1025 mInclusiveAncestorsOfEndContainer.AppendElement(info); 1026 // Cross the boundary for contents in shadow tree. 1027 nsINode* parent = ShadowDOMSelectionHelpers::GetParentNodeInSameSelection( 1028 *child, mAllowCrossShadowBoundary); 1029 if (!parent || !parent->IsContent()) { 1030 break; 1031 } 1032 1033 // `ShadowDOMSelectionHelpers::GetShadowRoot` would return non-null shadow 1034 // root if parent is a shadow host that we support cross boundary selection. 1035 const bool isChildAShadowRootForSelection = 1036 ShadowDOMSelectionHelpers::GetShadowRoot( 1037 parent, mAllowCrossShadowBoundary) == child; 1038 1039 info.mAncestor = parent->AsContent(); 1040 // mIsDescendantInShadowTree indicates that whether child is in the 1041 // shadow tree of parent or in the regular light DOM tree of parent. 1042 // So that later, when info.mAncestor is reached, we can decide whether 1043 // we should dive into the shadow tree. 1044 info.mIsDescendantInShadowTree = 1045 IterAllowCrossShadowBoundary() && isChildAShadowRootForSelection; 1046 } 1047 } 1048 1049 nsIContent* ContentSubtreeIterator::DetermineCandidateForFirstContent() const { 1050 nsINode* startContainer = ShadowDOMSelectionHelpers::GetStartContainer( 1051 mRange, mAllowCrossShadowBoundary); 1052 nsIContent* firstCandidate = nullptr; 1053 // find first node in range 1054 nsINode* node = nullptr; 1055 if (!startContainer->GetChildCount()) { 1056 // no children, start at the node itself 1057 node = startContainer; 1058 } else { 1059 nsIContent* child = 1060 IterAllowCrossShadowBoundary() 1061 ? mRange->GetMayCrossShadowBoundaryChildAtStartOffset() 1062 : mRange->GetChildAtStartOffset(); 1063 1064 #ifdef DEBUG 1065 const auto& startRef = IterAllowCrossShadowBoundary() 1066 ? mRange->MayCrossShadowBoundaryStartRef() 1067 : mRange->StartRef(); 1068 const uint32_t startOffset = ShadowDOMSelectionHelpers::StartOffset( 1069 mRange, mAllowCrossShadowBoundary); 1070 MOZ_ASSERT(child == 1071 (startRef.GetTreeKind() == TreeKind::Flat 1072 ? startContainer->GetChildAtInFlatTree(startOffset) 1073 : startContainer->GetChildAt_Deprecated(startOffset))); 1074 #endif 1075 if (!child) { 1076 // offset after last child 1077 node = startContainer; 1078 } else { 1079 firstCandidate = child; 1080 } 1081 } 1082 1083 if (!firstCandidate) { 1084 // then firstCandidate is next node after node 1085 firstCandidate = 1086 ContentIteratorBase::GetNextSibling(node, mAllowCrossShadowBoundary); 1087 } 1088 1089 if (firstCandidate) { 1090 firstCandidate = ContentIteratorBase::GetDeepFirstChild( 1091 firstCandidate, mAllowCrossShadowBoundary); 1092 } 1093 1094 return firstCandidate; 1095 } 1096 1097 nsIContent* ContentSubtreeIterator::DetermineFirstContent() const { 1098 nsIContent* firstCandidate = DetermineCandidateForFirstContent(); 1099 if (!firstCandidate) { 1100 return nullptr; 1101 } 1102 1103 // confirm that this first possible contained node is indeed contained. Else 1104 // we have a range that does not fully contain any node. 1105 const Maybe<bool> isNodeContainedInRange = 1106 IterAllowCrossShadowBoundary() 1107 ? RangeUtils::IsNodeContainedInRange<TreeKind::Flat>(*firstCandidate, 1108 mRange) 1109 : RangeUtils::IsNodeContainedInRange<TreeKind::ShadowIncludingDOM>( 1110 *firstCandidate, mRange); 1111 MOZ_ALWAYS_TRUE(isNodeContainedInRange); 1112 if (!isNodeContainedInRange.value()) { 1113 return nullptr; 1114 } 1115 1116 // cool, we have the first node in the range. Now we walk up its ancestors 1117 // to find the most senior that is still in the range. That's the real first 1118 // node. 1119 return GetTopAncestorInRange(firstCandidate); 1120 } 1121 1122 nsIContent* ContentSubtreeIterator::DetermineCandidateForLastContent() const { 1123 nsIContent* lastCandidate{nullptr}; 1124 nsINode* endContainer = ShadowDOMSelectionHelpers::GetEndContainer( 1125 mRange, mAllowCrossShadowBoundary); 1126 // now to find the last node 1127 int32_t offset = 1128 ShadowDOMSelectionHelpers::EndOffset(mRange, mAllowCrossShadowBoundary); 1129 1130 int32_t numChildren = endContainer->GetChildCount(); 1131 1132 nsINode* node = nullptr; 1133 if (offset > numChildren) { 1134 // Can happen for text nodes 1135 offset = numChildren; 1136 } 1137 if (!offset || !numChildren) { 1138 node = endContainer; 1139 } else { 1140 lastCandidate = IterAllowCrossShadowBoundary() 1141 ? mRange->MayCrossShadowBoundaryEndRef().Ref() 1142 : mRange->EndRef().Ref(); 1143 #ifdef DEBUG 1144 const auto& endRef = IterAllowCrossShadowBoundary() 1145 ? mRange->MayCrossShadowBoundaryEndRef() 1146 : mRange->EndRef(); 1147 MOZ_ASSERT(lastCandidate == 1148 (endRef.GetTreeKind() == TreeKind::Flat 1149 ? endContainer->GetChildAtInFlatTree(offset - 1) 1150 : endContainer->GetChildAt_Deprecated(offset - 1))); 1151 #endif 1152 NS_ASSERTION(lastCandidate, 1153 "tree traversal trouble in ContentSubtreeIterator::Init"); 1154 } 1155 1156 if (!lastCandidate) { 1157 // then lastCandidate is prev node before node 1158 lastCandidate = 1159 ContentIteratorBase::GetPrevSibling(node, mAllowCrossShadowBoundary); 1160 } 1161 1162 if (lastCandidate) { 1163 lastCandidate = ContentIteratorBase::GetDeepLastChild( 1164 lastCandidate, mAllowCrossShadowBoundary); 1165 } 1166 1167 return lastCandidate; 1168 } 1169 1170 nsresult ContentSubtreeIterator::InitWithRange() { 1171 MOZ_ASSERT(mRange); 1172 MOZ_ASSERT(mRange->IsPositioned()); 1173 1174 // get the start node and offset, convert to nsINode 1175 mClosestCommonInclusiveAncestor = 1176 mRange->GetClosestCommonInclusiveAncestor(mAllowCrossShadowBoundary); 1177 1178 nsINode* startContainer = ShadowDOMSelectionHelpers::GetStartContainer( 1179 mRange, mAllowCrossShadowBoundary); 1180 const int32_t startOffset = 1181 ShadowDOMSelectionHelpers::StartOffset(mRange, mAllowCrossShadowBoundary); 1182 nsINode* endContainer = ShadowDOMSelectionHelpers::GetEndContainer( 1183 mRange, mAllowCrossShadowBoundary); 1184 const int32_t endOffset = 1185 ShadowDOMSelectionHelpers::EndOffset(mRange, mAllowCrossShadowBoundary); 1186 MOZ_ASSERT(mClosestCommonInclusiveAncestor && startContainer && endContainer); 1187 // Bug 767169 1188 MOZ_ASSERT(uint32_t(startOffset) <= startContainer->Length() && 1189 uint32_t(endOffset) <= endContainer->Length()); 1190 1191 // short circuit when start node == end node 1192 if (startContainer == endContainer) { 1193 nsINode* child = startContainer->GetFirstChild(); 1194 1195 if (!child || startOffset == endOffset) { 1196 // Text node, empty container, or collapsed 1197 SetEmpty(); 1198 return NS_OK; 1199 } 1200 } 1201 1202 CacheInclusiveAncestorsOfEndContainer(); 1203 1204 mFirst = DetermineFirstContent(); 1205 if (!mFirst) { 1206 SetEmpty(); 1207 return NS_OK; 1208 } 1209 1210 mLast = DetermineLastContent(); 1211 if (!mLast) { 1212 SetEmpty(); 1213 return NS_OK; 1214 } 1215 1216 mCurNode = mFirst; 1217 1218 return NS_OK; 1219 } 1220 1221 nsIContent* ContentSubtreeIterator::DetermineLastContent() const { 1222 nsIContent* lastCandidate = DetermineCandidateForLastContent(); 1223 if (!lastCandidate) { 1224 return nullptr; 1225 } 1226 1227 // confirm that this last possible contained node is indeed contained. Else 1228 // we have a range that does not fully contain any node. 1229 1230 const Maybe<bool> isNodeContainedInRange = 1231 IterAllowCrossShadowBoundary() 1232 ? RangeUtils::IsNodeContainedInRange<TreeKind::Flat>(*lastCandidate, 1233 mRange) 1234 : RangeUtils::IsNodeContainedInRange<TreeKind::ShadowIncludingDOM>( 1235 *lastCandidate, mRange); 1236 MOZ_ALWAYS_TRUE(isNodeContainedInRange); 1237 if (!isNodeContainedInRange.value()) { 1238 return nullptr; 1239 } 1240 1241 // cool, we have the last node in the range. Now we walk up its ancestors to 1242 // find the most senior that is still in the range. That's the real first 1243 // node. 1244 return GetTopAncestorInRange(lastCandidate); 1245 } 1246 1247 /**************************************************************** 1248 * ContentSubtreeIterator overrides of ContentIterator routines 1249 ****************************************************************/ 1250 1251 // we can't call PositionAt in a subtree iterator... 1252 void ContentSubtreeIterator::First() { mCurNode = mFirst; } 1253 1254 // we can't call PositionAt in a subtree iterator... 1255 void ContentSubtreeIterator::Last() { mCurNode = mLast; } 1256 1257 void ContentSubtreeIterator::Next() { 1258 if (IsDone()) { 1259 return; 1260 } 1261 1262 if (mCurNode == mLast) { 1263 mCurNode = nullptr; 1264 return; 1265 } 1266 1267 nsINode* nextNode = ContentIteratorBase::GetNextSibling( 1268 mCurNode, mAllowCrossShadowBoundary, &mInclusiveAncestorsOfEndContainer); 1269 1270 NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!"); 1271 1272 int32_t i = mInclusiveAncestorsOfEndContainer.IndexOf( 1273 nextNode, 0, InclusiveAncestorComparator()); 1274 1275 while (i != -1) { 1276 // as long as we are finding ancestors of the endpoint of the range, 1277 // dive down into their children 1278 ShadowRoot* root = ShadowDOMSelectionHelpers::GetShadowRoot( 1279 nextNode, mAllowCrossShadowBoundary); 1280 if (mInclusiveAncestorsOfEndContainer[i].mIsDescendantInShadowTree) { 1281 MOZ_ASSERT(root); 1282 nextNode = root->GetFirstChild(); 1283 } else if (auto* slot = HTMLSlotElement::FromNode(nextNode); 1284 slot && IterAllowCrossShadowBoundary() && 1285 !slot->AssignedNodes().IsEmpty()) { 1286 // Ancestor is a slot, we start from the first assigned node within this 1287 // slot 1288 nextNode = slot->AssignedNodes()[0]; 1289 } else { 1290 if (root) { 1291 // nextNode is a shadow host but the descendant in the light DOM 1292 // of it. There's no need to iterate light DOM elements for a 1293 // shadow tree. Stop here. 1294 mCurNode = nullptr; 1295 return; 1296 } 1297 nextNode = nextNode->GetFirstChild(); 1298 } 1299 NS_ASSERTION(nextNode, "Iterator error, expected a child node!"); 1300 1301 // should be impossible to get a null pointer. If we went all the way 1302 // down the child chain to the bottom without finding an interior node, 1303 // then the previous node should have been the last, which was 1304 // was tested at top of routine. 1305 i = mInclusiveAncestorsOfEndContainer.IndexOf( 1306 nextNode, 0, InclusiveAncestorComparator()); 1307 } 1308 1309 mCurNode = nextNode; 1310 } 1311 1312 void ContentSubtreeIterator::Prev() { 1313 // Prev should be optimized to use the mStartNodes, just as Next 1314 // uses mInclusiveAncestorsOfEndContainer. 1315 if (IsDone()) { 1316 return; 1317 } 1318 1319 if (mCurNode == mFirst) { 1320 mCurNode = nullptr; 1321 return; 1322 } 1323 1324 // If any of these function calls return null, so will all succeeding ones, 1325 // so mCurNode will wind up set to null. 1326 nsINode* prevNode = ContentIteratorBase::GetDeepFirstChild(mCurNode); 1327 1328 prevNode = PrevNode(prevNode); 1329 1330 prevNode = ContentIteratorBase::GetDeepLastChild(prevNode); 1331 1332 mCurNode = GetTopAncestorInRange(prevNode); 1333 } 1334 1335 nsresult ContentSubtreeIterator::PositionAt(nsINode* aCurNode) { 1336 NS_ERROR("Not implemented!"); 1337 return NS_ERROR_NOT_IMPLEMENTED; 1338 } 1339 1340 /**************************************************************** 1341 * ContentSubtreeIterator helper routines 1342 ****************************************************************/ 1343 1344 nsIContent* ContentSubtreeIterator::GetTopAncestorInRange( 1345 nsINode* aNode) const { 1346 if (!aNode || !ShadowDOMSelectionHelpers::GetParentNodeInSameSelection( 1347 *aNode, mAllowCrossShadowBoundary)) { 1348 return nullptr; 1349 } 1350 1351 // aNode has a parent, so it must be content. 1352 nsIContent* content = aNode->AsContent(); 1353 1354 // sanity check: aNode is itself in the range 1355 Maybe<bool> isNodeContainedInRange = 1356 IterAllowCrossShadowBoundary() 1357 ? RangeUtils::IsNodeContainedInRange<TreeKind::Flat>(*aNode, mRange) 1358 : RangeUtils::IsNodeContainedInRange<TreeKind::ShadowIncludingDOM>( 1359 *aNode, mRange); 1360 1361 NS_ASSERTION(isNodeContainedInRange && isNodeContainedInRange.value(), 1362 "aNode isn't in mRange, or something else weird happened"); 1363 if (!isNodeContainedInRange || !isNodeContainedInRange.value()) { 1364 return nullptr; 1365 } 1366 1367 nsIContent* lastContentInShadowTree = nullptr; 1368 while (content) { 1369 nsINode* parent = ShadowDOMSelectionHelpers::GetParentNodeInSameSelection( 1370 *content, mAllowCrossShadowBoundary); 1371 1372 // content always has a parent. If its parent is the root, however -- 1373 // i.e., either it's not content, or it is content but its own parent is 1374 // null -- then we're finished, since we don't go up to the root. 1375 // 1376 // Caveat: If iteration crossing shadow boundary is allowed 1377 // and the root is a shadow root, we keep going up to the 1378 // shadow host and continue. 1379 // 1380 // We have to special-case this because CompareNodeToRange treats the root 1381 // node differently -- see bug 765205. 1382 if (!parent || !ShadowDOMSelectionHelpers::GetParentNodeInSameSelection( 1383 *parent, mAllowCrossShadowBoundary)) { 1384 return content; 1385 } 1386 1387 isNodeContainedInRange = 1388 IterAllowCrossShadowBoundary() 1389 ? RangeUtils::IsNodeContainedInRange<TreeKind::Flat>(*parent, 1390 mRange) 1391 : RangeUtils::IsNodeContainedInRange<TreeKind::ShadowIncludingDOM>( 1392 *parent, mRange); 1393 1394 MOZ_ALWAYS_TRUE(isNodeContainedInRange); 1395 if (!isNodeContainedInRange.value()) { 1396 if (IterAllowCrossShadowBoundary() && content->IsShadowRoot()) { 1397 MOZ_ASSERT(parent->GetShadowRoot() == content); 1398 // host element is not in range, the last content in tree 1399 // should be the ancestor. 1400 MOZ_ASSERT(lastContentInShadowTree); 1401 return lastContentInShadowTree; 1402 } 1403 return content; 1404 } 1405 1406 // When we cross the boundary, we keep a reference to the 1407 // last content that is in tree, because if we later 1408 // find the shadow host element is not in the range, that means 1409 // the last content in the tree should be top ancestor in range. 1410 // 1411 // Using shadow root doesn't make sense here because it doesn't 1412 // represent a actual content. 1413 if (IterAllowCrossShadowBoundary() && parent->IsShadowRoot()) { 1414 lastContentInShadowTree = content; 1415 } 1416 1417 content = parent->AsContent(); 1418 } 1419 1420 MOZ_CRASH("This should only be possible if aNode was null"); 1421 } 1422 1423 #undef NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD 1424 1425 } // namespace mozilla