dom/base/ContentIterator.cpp

   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/dom/ShadowRoot.h"
  11 #include "mozilla/DebugOnly.h"
  12 #include "mozilla/RangeBoundary.h"
  13 #include "mozilla/RangeUtils.h"
  14 #include "mozilla/Result.h"
  15
  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 /**
  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
  33  * boundary.
  34  */
  35 struct IteratorHelpers {
  36   IteratorHelpers() = delete;
  37
  38   static nsINode* GetStartContainer(AbstractRange* aRange,
  39                                     bool aAllowCrossShadowBoundary) {
  40     MOZ_ASSERT(aRange);
  41     return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
  42             aAllowCrossShadowBoundary)
  43                ? aRange->GetMayCrossShadowBoundaryStartContainer()
  44                : aRange->GetStartContainer();
  45   }
  46
  47   static int32_t StartOffset(AbstractRange* aRange,
  48                              bool aAllowCrossShadowBoundary) {
  49     MOZ_ASSERT(aRange);
  50     return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
  51             aAllowCrossShadowBoundary)
  52                ? aRange->MayCrossShadowBoundaryStartOffset()
  53                : aRange->StartOffset();
  54   }
  55
  56   static nsINode* GetEndContainer(AbstractRange* aRange,
  57                                   bool aAllowCrossShadowBoundary) {
  58     MOZ_ASSERT(aRange);
  59     return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
  60             aAllowCrossShadowBoundary)
  61                ? aRange->GetMayCrossShadowBoundaryEndContainer()
  62                : aRange->GetEndContainer();
  63   }
  64
  65   static int32_t EndOffset(AbstractRange* aRange,
  66                            bool aAllowCrossShadowBoundary) {
  67     MOZ_ASSERT(aRange);
  68     return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
  69             aAllowCrossShadowBoundary)
  70                ? aRange->MayCrossShadowBoundaryEndOffset()
  71                : aRange->EndOffset();
  72   }
  73
  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();
  81   }
  82
  83   static ShadowRoot* GetShadowRoot(const nsINode* aNode,
  84                                    bool aAllowCrossShadowBoundary) {
  85     MOZ_ASSERT(aNode);
  86     return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
  87             aAllowCrossShadowBoundary)
  88                ? aNode->GetShadowRootForSelection()
  89                : nullptr;
  90   }
  91 };
  92
  93 static bool ComparePostMode(const RawRangeBoundary& aStart,
  94                             const RawRangeBoundary& aEnd, nsINode& aNode) {
  95   nsINode* parent = aNode.GetParentNode();
  96   if (!parent) {
  97     return false;
  98   }
  99
 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();
 104
 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);
 112   };
 113
 114   const auto isAfterNodeLessOrEqualToEnd = [&]() {
 115     const Maybe<int32_t> afterNodeComparedToEnd =
 116         nsContentUtils::ComparePoints(afterNode, aEnd);
 117     return !NS_WARN_IF(!afterNodeComparedToEnd) &&
 118            (*afterNodeComparedToEnd <= 0);
 119   };
 120
 121   return isStartLessThanAfterNode() && isAfterNodeLessOrEqualToEnd();
 122 }
 123
 124 static bool ComparePreMode(const RawRangeBoundary& aStart,
 125                            const RawRangeBoundary& aEnd, nsINode& aNode) {
 126   nsINode* parent = aNode.GetParentNode();
 127   if (!parent) {
 128     return false;
 129   }
 130
 131   // Pre mode: start <= node < end.
 132   RawRangeBoundary beforeNode(parent, aNode.GetPreviousSibling());
 133
 134   const auto isStartLessOrEqualToBeforeNode = [&]() {
 135     const Maybe<int32_t> startComparedToBeforeNode =
 136         nsContentUtils::ComparePoints(aStart, beforeNode);
 137     return !NS_WARN_IF(!startComparedToBeforeNode) &&
 138            (*startComparedToBeforeNode <= 0);
 139   };
 140
 141   const auto isBeforeNodeLessThanEndNode = [&]() {
 142     const Maybe<int32_t> beforeNodeComparedToEnd =
 143         nsContentUtils::ComparePoints(beforeNode, aEnd);
 144     return !NS_WARN_IF(!beforeNodeComparedToEnd) &&
 145            (*beforeNodeComparedToEnd < 0);
 146   };
 147
 148   return isStartLessOrEqualToBeforeNode() && isBeforeNodeLessThanEndNode();
 149 }
 150
 151 ///////////////////////////////////////////////////////////////////////////
 152 // NodeIsInTraversalRange: returns true if content is visited during
 153 // the traversal of the range in the specified mode.
 154 //
 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)) {
 160     return false;
 161   }
 162
 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
 168     }
 169     if (!aNode->HasChildren()) {
 170       MOZ_ASSERT(
 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");
 177       return true;
 178     }
 179   }
 180
 181   if (aIsPreMode) {
 182     return ComparePreMode(aStart, aEnd, *aNode);
 183   }
 184
 185   return ComparePostMode(aStart, aEnd, *aNode);
 186 }
 187
 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);
 193 }
 194
 195 void ImplCycleCollectionUnlink(PostContentIterator& aField) {
 196   ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase&>(aField));
 197 }
 198
 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);
 204 }
 205
 206 void ImplCycleCollectionUnlink(PreContentIterator& aField) {
 207   ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase&>(aField));
 208 }
 209
 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);
 216 }
 217
 218 void ImplCycleCollectionUnlink(ContentSubtreeIterator& aField) {
 219   ImplCycleCollectionUnlink(aField.mRange);
 220   ImplCycleCollectionUnlink(static_cast<SafeContentIteratorBase&>(aField));
 221 }
 222
 223 /******************************************************
 224  * ContentIteratorBase
 225  ******************************************************/
 226
 227 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(, ContentIteratorBase, Order);
 228
 229 template <typename NodeType>
 230 ContentIteratorBase<NodeType>::ContentIteratorBase(Order aOrder)
 231     : mOrder(aOrder) {}
 232
 233 template ContentIteratorBase<RefPtr<nsINode>>::~ContentIteratorBase();
 234 template ContentIteratorBase<nsINode*>::~ContentIteratorBase();
 235
 236 template <typename NodeType>
 237 ContentIteratorBase<NodeType>::~ContentIteratorBase() {
 238   MOZ_DIAGNOSTIC_ASSERT_IF(mMutationGuard.isSome(),
 239                            !mMutationGuard->Mutated(0));
 240 }
 241
 242 /******************************************************
 243  * Init routines
 244  ******************************************************/
 245
 246 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, nsINode*);
 247
 248 template <typename NodeType>
 249 nsresult ContentIteratorBase<NodeType>::Init(nsINode* aRoot) {
 250   if (NS_WARN_IF(!aRoot)) {
 251     return NS_ERROR_NULL_POINTER;
 252   }
 253
 254   if (mOrder == Order::Pre) {
 255     mFirst = aRoot;
 256     mLast = ContentIteratorBase::GetDeepLastChild(aRoot);
 257     NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
 258   } else {
 259     mFirst = ContentIteratorBase::GetDeepFirstChild(aRoot);
 260     NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
 261     mLast = aRoot;
 262   }
 263
 264   mClosestCommonInclusiveAncestor = aRoot;
 265   mCurNode = mFirst;
 266   return NS_OK;
 267 }
 268
 269 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, AbstractRange*);
 270
 271 template <typename NodeType>
 272 nsresult ContentIteratorBase<NodeType>::Init(AbstractRange* aRange) {
 273   if (NS_WARN_IF(!aRange)) {
 274     return NS_ERROR_INVALID_ARG;
 275   }
 276
 277   if (NS_WARN_IF(!aRange->IsPositioned())) {
 278     return NS_ERROR_INVALID_ARG;
 279   }
 280
 281   return InitInternal(aRange->StartRef().AsRaw(), aRange->EndRef().AsRaw());
 282 }
 283
 284 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, nsINode*, uint32_t,
 285                                         nsINode*, uint32_t);
 286
 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;
 295   }
 296
 297   return InitInternal(RawRangeBoundary(aStartContainer, aStartOffset),
 298                       RawRangeBoundary(aEndContainer, aEndOffset));
 299 }
 300
 301 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, Init, const RawRangeBoundary&,
 302                                         const RawRangeBoundary&);
 303
 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;
 309   }
 310
 311   return InitInternal(aStart, aEnd);
 312 }
 313
 314 template <typename NodeType>
 315 class MOZ_STACK_CLASS ContentIteratorBase<NodeType>::Initializer final {
 316  public:
 317   Initializer(ContentIteratorBase<NodeType>& aIterator,
 318               const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd)
 319       : mIterator{aIterator},
 320         mStart{aStart},
 321         mEnd{aEnd},
 322         mStartIsCharacterData{mStart.Container()->IsCharacterData()} {
 323     MOZ_ASSERT(mStart.IsSetAndValid());
 324     MOZ_ASSERT(mEnd.IsSetAndValid());
 325   }
 326
 327   nsresult Run();
 328
 329  private:
 330   /**
 331    * @return may be nullptr.
 332    */
 333   nsINode* DetermineFirstNode() const;
 334
 335   /**
 336    * @return may be nullptr.
 337    */
 338   [[nodiscard]] Result<nsINode*, nsresult> DetermineLastNode() const;
 339
 340   bool IsCollapsedNonCharacterRange() const;
 341   bool IsSingleNodeCharacterRange() const;
 342
 343   ContentIteratorBase& mIterator;
 344   const RawRangeBoundary& mStart;
 345   const RawRangeBoundary& mEnd;
 346   const bool mStartIsCharacterData;
 347 };
 348
 349 template <>
 350 nsresult ContentIteratorBase<RefPtr<nsINode>>::InitInternal(
 351     const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) {
 352   Initializer initializer{*this, aStart, aEnd};
 353   return initializer.Run();
 354 }
 355
 356 template <>
 357 nsresult ContentIteratorBase<nsINode*>::InitInternal(
 358     const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) {
 359   Initializer initializer{*this, aStart, aEnd};
 360   nsresult rv = initializer.Run();
 361   if (NS_FAILED(rv)) {
 362     return rv;
 363   }
 364   mMutationGuard.emplace();
 365   mAssertNoGC.emplace();
 366   return NS_OK;
 367 }
 368
 369 template <typename NodeType>
 370 bool ContentIteratorBase<NodeType>::Initializer::IsCollapsedNonCharacterRange()
 371     const {
 372   return !mStartIsCharacterData && mStart == mEnd;
 373 }
 374
 375 template <typename NodeType>
 376 bool ContentIteratorBase<NodeType>::Initializer::IsSingleNodeCharacterRange()
 377     const {
 378   return mStartIsCharacterData && mStart.Container() == mEnd.Container();
 379 }
 380
 381 template <typename NodeType>
 382 nsresult ContentIteratorBase<NodeType>::Initializer::Run() {
 383   // get common content parent
 384   mIterator.mClosestCommonInclusiveAncestor =
 385       nsContentUtils::GetClosestCommonInclusiveAncestor(mStart.Container(),
 386                                                         mEnd.Container());
 387   if (NS_WARN_IF(!mIterator.mClosestCommonInclusiveAncestor)) {
 388     return NS_ERROR_FAILURE;
 389   }
 390
 391   // Check to see if we have a collapsed range, if so, there is nothing to
 392   // iterate over.
 393   //
 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
 396   //      of a range.
 397
 398   if (IsCollapsedNonCharacterRange()) {
 399     mIterator.SetEmpty();
 400     return NS_OK;
 401   }
 402
 403   if (IsSingleNodeCharacterRange()) {
 404     mIterator.mFirst = mStart.Container()->AsContent();
 405     mIterator.mLast = mIterator.mFirst;
 406     mIterator.mCurNode = mIterator.mFirst;
 407
 408     return NS_OK;
 409   }
 410
 411   mIterator.mFirst = DetermineFirstNode();
 412
 413   if (Result<nsINode*, nsresult> lastNode = DetermineLastNode();
 414       NS_WARN_IF(lastNode.isErr())) {
 415     return lastNode.unwrapErr();
 416   } else {
 417     mIterator.mLast = lastNode.unwrap();
 418   }
 419
 420   // If either first or last is null, they both have to be null!
 421   if (!mIterator.mFirst || !mIterator.mLast) {
 422     mIterator.SetEmpty();
 423   }
 424
 425   mIterator.mCurNode = mIterator.mFirst;
 426
 427   return NS_OK;
 428 }
 429
 430 template <typename NodeType>
 431 nsINode* ContentIteratorBase<NodeType>::Initializer::DetermineFirstNode()
 432     const {
 433   nsIContent* cChild = nullptr;
 434
 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();
 439   }
 440
 441   if (!cChild) {
 442     // No children (possibly a <br> or text node), or index is after last child.
 443
 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
 447       //      the next sibling?
 448
 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();
 456         startIsContainer =
 457             nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name));
 458       }
 459       if (!mStartIsCharacterData &&
 460           (startIsContainer || !mStart.IsStartOfContainer())) {
 461         nsINode* const result =
 462             ContentIteratorBase::GetNextSibling(mStart.Container());
 463         NS_WARNING_ASSERTION(result, "GetNextSibling returned null");
 464
 465         // Does mFirst node really intersect the range?  The range could be
 466         // 'degenerate', i.e., not collapsed but still contain no content.
 467         if (result &&
 468             NS_WARN_IF(!NodeIsInTraversalRange(
 469                 result, mIterator.mOrder == Order::Pre, mStart, mEnd))) {
 470           return nullptr;
 471         }
 472
 473         return result;
 474       }
 475       return mStart.Container()->AsContent();
 476     }
 477
 478     // post-order
 479     if (NS_WARN_IF(!mStart.Container()->IsContent())) {
 480       // What else can we do?
 481       return nullptr;
 482     }
 483     return mStart.Container()->AsContent();
 484   }
 485
 486   if (mIterator.mOrder == Order::Pre) {
 487     return cChild;
 488   }
 489
 490   // post-order
 491   nsINode* const result = ContentIteratorBase::GetDeepFirstChild(cChild);
 492   NS_WARNING_ASSERTION(result, "GetDeepFirstChild returned null");
 493
 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,
 497                                         mStart, mEnd)) {
 498     return nullptr;
 499   }
 500
 501   return result;
 502 }
 503
 504 template <typename NodeType>
 505 Result<nsINode*, nsresult>
 506 ContentIteratorBase<NodeType>::Initializer::DetermineLastNode() const {
 507   const bool endIsCharacterData = mEnd.Container()->IsCharacterData();
 508
 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...
 514         return nullptr;
 515       }
 516
 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();
 523         endIsContainer =
 524             nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name));
 525       }
 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))) {
 533           return nullptr;
 534         }
 535
 536         return result;
 537       }
 538
 539       return mEnd.Container()->AsContent();
 540     }
 541
 542     // post-order
 543     //
 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?
 546
 547     if (!endIsCharacterData) {
 548       nsINode* const result =
 549           ContentIteratorBase::GetPrevSibling(mEnd.Container());
 550       NS_WARNING_ASSERTION(result, "GetPrevSibling returned null");
 551
 552       if (!NodeIsInTraversalRange(result, mIterator.mOrder == Order::Pre,
 553                                   mStart, mEnd)) {
 554         return nullptr;
 555       }
 556       return result;
 557     }
 558     return mEnd.Container()->AsContent();
 559   }
 560
 561   nsIContent* cChild = mEnd.Ref();
 562
 563   if (NS_WARN_IF(!cChild)) {
 564     // No child at offset!
 565     MOZ_ASSERT_UNREACHABLE("ContentIterator::ContentIterator");
 566     return Err(NS_ERROR_FAILURE);
 567   }
 568
 569   if (mIterator.mOrder == Order::Pre) {
 570     nsINode* const result = ContentIteratorBase::GetDeepLastChild(cChild);
 571     NS_WARNING_ASSERTION(result, "GetDeepLastChild returned null");
 572
 573     if (NS_WARN_IF(!NodeIsInTraversalRange(
 574             result, mIterator.mOrder == Order::Pre, mStart, mEnd))) {
 575       return nullptr;
 576     }
 577
 578     return result;
 579   }
 580
 581   // post-order
 582   return cChild;
 583 }
 584
 585 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, SetEmpty);
 586
 587 template <typename NodeType>
 588 void ContentIteratorBase<NodeType>::SetEmpty() {
 589   mCurNode = nullptr;
 590   mFirst = nullptr;
 591   mLast = nullptr;
 592   mClosestCommonInclusiveAncestor = nullptr;
 593 }
 594
 595 // static
 596 template <typename NodeType>
 597 nsINode* ContentIteratorBase<NodeType>::GetDeepFirstChild(nsINode* aRoot) {
 598   if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
 599     return aRoot;
 600   }
 601
 602   return ContentIteratorBase::GetDeepFirstChild(aRoot->GetFirstChild());
 603 }
 604
 605 // static
 606 template <typename NodeType>
 607 nsIContent* ContentIteratorBase<NodeType>::GetDeepFirstChild(
 608     nsIContent* aRoot, bool aAllowCrossShadowBoundary) {
 609   if (NS_WARN_IF(!aRoot)) {
 610     return nullptr;
 611   }
 612
 613   nsIContent* node = aRoot;
 614   nsIContent* child = nullptr;
 615
 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
 620     // child.
 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();
 627   } else {
 628     child = node->GetFirstChild();
 629   }
 630
 631   while (child) {
 632     node = child;
 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
 637       // child.
 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
 642       // not.
 643       child = shadowRoot->GetFirstChild();
 644     } else {
 645       child = node->GetFirstChild();
 646     }
 647   }
 648
 649   return node;
 650 }
 651
 652 // static
 653 template <typename NodeType>
 654 nsINode* ContentIteratorBase<NodeType>::GetDeepLastChild(nsINode* aRoot) {
 655   if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
 656     return aRoot;
 657   }
 658
 659   return ContentIteratorBase::GetDeepLastChild(aRoot->GetLastChild());
 660 }
 661
 662 // static
 663 template <typename NodeType>
 664 nsIContent* ContentIteratorBase<NodeType>::GetDeepLastChild(
 665     nsIContent* aRoot, bool aAllowCrossShadowBoundary) {
 666   if (NS_WARN_IF(!aRoot)) {
 667     return nullptr;
 668   }
 669
 670   nsIContent* node = aRoot;
 671
 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();
 678     } else {
 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();
 683     }
 684     shadowRoot =
 685         IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary);
 686   }
 687   return node;
 688 }
 689
 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
 692 // sibling...
 693 //
 694 // static
 695 //
 696 template <typename NodeType>
 697 nsIContent* ContentIteratorBase<NodeType>::GetNextSibling(
 698     nsINode* aNode, bool aAllowCrossShadowBoundary) {
 699   if (NS_WARN_IF(!aNode)) {
 700     return nullptr;
 701   }
 702
 703   if (nsIContent* next = aNode->GetNextSibling()) {
 704     return next;
 705   }
 706
 707   nsINode* parent =
 708       IteratorHelpers::GetParentNode(*aNode, aAllowCrossShadowBoundary);
 709   if (NS_WARN_IF(!parent)) {
 710     return nullptr;
 711   }
 712
 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
 717     // slotted contents.
 718     if (aNode->IsShadowRoot()) {
 719       if (nsIContent* child = parent->GetFirstChild()) {
 720         return child;
 721       }
 722     }
 723   }
 724
 725   return ContentIteratorBase::GetNextSibling(parent, aAllowCrossShadowBoundary);
 726 }
 727
 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)) {
 734     return nullptr;
 735   }
 736
 737   if (nsIContent* prev = aNode->GetPreviousSibling()) {
 738     return prev;
 739   }
 740
 741   nsINode* parent =
 742       IteratorHelpers::GetParentNode(*aNode, aAllowCrossShadowBoundary);
 743   if (NS_WARN_IF(!parent)) {
 744     return nullptr;
 745   }
 746
 747   return ContentIteratorBase::GetPrevSibling(parent, aAllowCrossShadowBoundary);
 748 }
 749
 750 template <typename NodeType>
 751 nsINode* ContentIteratorBase<NodeType>::NextNode(nsINode* aNode) {
 752   nsINode* node = aNode;
 753
 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);
 760
 761       return firstChild;
 762     }
 763
 764     // else next sibling is next
 765     return ContentIteratorBase::GetNextSibling(node);
 766   }
 767
 768   // post-order
 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");
 772     mCurNode = nullptr;
 773     return node;
 774   }
 775
 776   if (nsIContent* sibling = node->GetNextSibling()) {
 777     // next node is sibling's "deep left" child
 778     return ContentIteratorBase::GetDeepFirstChild(sibling);
 779   }
 780
 781   return parent;
 782 }
 783
 784 template <typename NodeType>
 785 nsINode* ContentIteratorBase<NodeType>::PrevNode(nsINode* aNode) {
 786   nsINode* node = aNode;
 787
 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");
 793       mCurNode = nullptr;
 794       return aNode;
 795     }
 796
 797     nsIContent* sibling = node->GetPreviousSibling();
 798     if (sibling) {
 799       return ContentIteratorBase::GetDeepLastChild(sibling);
 800     }
 801
 802     return parent;
 803   }
 804
 805   // post-order
 806   if (node->HasChildren()) {
 807     return node->GetLastChild();
 808   }
 809
 810   // else prev sibling is previous
 811   return ContentIteratorBase::GetPrevSibling(node);
 812 }
 813
 814 /******************************************************
 815  * ContentIteratorBase routines
 816  ******************************************************/
 817
 818 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, First);
 819
 820 template <typename NodeType>
 821 void ContentIteratorBase<NodeType>::First() {
 822   if (!mFirst) {
 823     MOZ_ASSERT(IsDone());
 824     mCurNode = nullptr;
 825     return;
 826   }
 827
 828   mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst);
 829   NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 830 }
 831
 832 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Last);
 833
 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.
 838   if (!mLast) {
 839     MOZ_ASSERT(IsDone());
 840     mCurNode = nullptr;
 841     return;
 842   }
 843
 844   mozilla::DebugOnly<nsresult> rv = PositionAt(mLast);
 845   NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 846 }
 847
 848 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Next);
 849
 850 template <typename NodeType>
 851 void ContentIteratorBase<NodeType>::Next() {
 852   if (IsDone()) {
 853     return;
 854   }
 855
 856   if (mCurNode == mLast) {
 857     mCurNode = nullptr;
 858     return;
 859   }
 860
 861   mCurNode = NextNode(mCurNode);
 862 }
 863
 864 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Prev);
 865
 866 template <typename NodeType>
 867 void ContentIteratorBase<NodeType>::Prev() {
 868   if (IsDone()) {
 869     return;
 870   }
 871
 872   if (mCurNode == mFirst) {
 873     mCurNode = nullptr;
 874     return;
 875   }
 876
 877   mCurNode = PrevNode(mCurNode);
 878 }
 879
 880 // Keeping arrays of indexes for the stack of nodes makes PositionAt
 881 // interesting...
 882 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, PositionAt, nsINode*);
 883
 884 template <typename NodeType>
 885 nsresult ContentIteratorBase<NodeType>::PositionAt(nsINode* aCurNode) {
 886   if (NS_WARN_IF(!aCurNode)) {
 887     return NS_ERROR_NULL_POINTER;
 888   }
 889
 890   // take an early out if this doesn't actually change the position
 891   if (mCurNode == aCurNode) {
 892     return NS_OK;
 893   }
 894   mCurNode = aCurNode;
 895
 896   // Check to see if the node falls within the traversal range.
 897
 898   RawRangeBoundary first(mFirst, 0u);
 899   RawRangeBoundary last(mLast, 0u);
 900
 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()};
 906
 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()};
 910       }
 911     } else {
 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()};
 916       } else {
 917         first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()};
 918       }
 919
 920       // Set the last point immediately after the final node.
 921       last = {mLast->GetParentNode(), mLast->AsContent()};
 922     }
 923   }
 924
 925   NS_WARNING_ASSERTION(first.IsSetAndValid(), "first is not valid");
 926   NS_WARNING_ASSERTION(last.IsSetAndValid(), "last is not valid");
 927
 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,
 934                                           last)))) {
 935     mCurNode = nullptr;
 936     return NS_ERROR_FAILURE;
 937   }
 938
 939   return NS_OK;
 940 }
 941
 942 /******************************************************
 943  * ContentSubtreeIterator init routines
 944  ******************************************************/
 945
 946 nsresult ContentSubtreeIterator::Init(nsINode* aRoot) {
 947   return NS_ERROR_NOT_IMPLEMENTED;
 948 }
 949
 950 nsresult ContentSubtreeIterator::Init(AbstractRange* aRange) {
 951   MOZ_ASSERT(aRange);
 952
 953   if (NS_WARN_IF(!aRange->IsPositioned())) {
 954     return NS_ERROR_INVALID_ARG;
 955   }
 956
 957   mRange = aRange;
 958
 959   return InitWithRange();
 960 }
 961
 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));
 968 }
 969
 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;
 976   }
 977
 978   if (NS_WARN_IF(range->StartRef() != aStartBoundary) ||
 979       NS_WARN_IF(range->EndRef() != aEndBoundary)) {
 980     return NS_ERROR_UNEXPECTED;
 981   }
 982
 983   mRange = std::move(range);
 984
 985   return InitWithRange();
 986 }
 987
 988 nsresult ContentSubtreeIterator::InitWithAllowCrossShadowBoundary(
 989     AbstractRange* aRange) {
 990   MOZ_ASSERT(aRange);
 991
 992   if (NS_WARN_IF(!aRange->IsPositioned())) {
 993     return NS_ERROR_INVALID_ARG;
 994   }
 995
 996   mRange = aRange;
 997
 998   mAllowCrossShadowBoundary = AllowRangeCrossShadowBoundary::Yes;
 999   return InitWithRange();
1000 }
1001
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;
1008   while (endNode) {
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()) {
1014       break;
1015     }
1016     endNode = parent->AsContent();
1017   }
1018 }
1019
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;
1029   } else {
1030     nsIContent* child =
1031         IterAllowCrossShadowBoundary()
1032             ? mRange->GetMayCrossShadowBoundaryChildAtStartOffset()
1033             : mRange->GetChildAtStartOffset();
1034
1035     MOZ_ASSERT(child == startContainer->GetChildAt_Deprecated(
1036                             IteratorHelpers::StartOffset(
1037                                 mRange, IterAllowCrossShadowBoundary())));
1038     if (!child) {
1039       // offset after last child
1040       node = startContainer;
1041     } else {
1042       firstCandidate = child;
1043     }
1044   }
1045
1046   if (!firstCandidate) {
1047     // then firstCandidate is next node after node
1048     firstCandidate = ContentIteratorBase::GetNextSibling(
1049         node, IterAllowCrossShadowBoundary());
1050   }
1051
1052   if (firstCandidate) {
1053     firstCandidate = ContentIteratorBase::GetDeepFirstChild(
1054         firstCandidate, IterAllowCrossShadowBoundary());
1055   }
1056
1057   return firstCandidate;
1058 }
1059
1060 nsIContent* ContentSubtreeIterator::DetermineFirstContent() const {
1061   nsIContent* firstCandidate = DetermineCandidateForFirstContent();
1062   if (!firstCandidate) {
1063     return nullptr;
1064   }
1065
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()) {
1072     return nullptr;
1073   }
1074
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
1077   // node.
1078   return GetTopAncestorInRange(firstCandidate);
1079 }
1080
1081 nsIContent* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
1082   nsIContent* lastCandidate{nullptr};
1083   nsINode* endContainer =
1084       IteratorHelpers::GetEndContainer(mRange, IterAllowCrossShadowBoundary());
1085   // now to find the last node
1086   int32_t offset =
1087       IteratorHelpers::EndOffset(mRange, IterAllowCrossShadowBoundary());
1088
1089   int32_t numChildren = endContainer->GetChildCount();
1090
1091   nsINode* node = nullptr;
1092   if (offset > numChildren) {
1093     // Can happen for text nodes
1094     offset = numChildren;
1095   }
1096   if (!offset || !numChildren) {
1097     node = endContainer;
1098   } else {
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");
1105   }
1106
1107   if (!lastCandidate) {
1108     // then lastCandidate is prev node before node
1109     lastCandidate = ContentIteratorBase::GetPrevSibling(
1110         node, IterAllowCrossShadowBoundary());
1111   }
1112
1113   if (lastCandidate) {
1114     lastCandidate = ContentIteratorBase::GetDeepLastChild(
1115         lastCandidate, IterAllowCrossShadowBoundary());
1116   }
1117
1118   return lastCandidate;
1119 }
1120
1121 nsresult ContentSubtreeIterator::InitWithRange() {
1122   MOZ_ASSERT(mRange);
1123   MOZ_ASSERT(mRange->IsPositioned());
1124
1125   // get the start node and offset, convert to nsINode
1126   mClosestCommonInclusiveAncestor =
1127       mRange->GetClosestCommonInclusiveAncestor(mAllowCrossShadowBoundary);
1128
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);
1138   // Bug 767169
1139   MOZ_ASSERT(uint32_t(startOffset) <= startContainer->Length() &&
1140              uint32_t(endOffset) <= endContainer->Length());
1141
1142   // short circuit when start node == end node
1143   if (startContainer == endContainer) {
1144     nsINode* child = startContainer->GetFirstChild();
1145
1146     if (!child || startOffset == endOffset) {
1147       // Text node, empty container, or collapsed
1148       SetEmpty();
1149       return NS_OK;
1150     }
1151   }
1152
1153   CacheInclusiveAncestorsOfEndContainer();
1154
1155   mFirst = DetermineFirstContent();
1156   if (!mFirst) {
1157     SetEmpty();
1158     return NS_OK;
1159   }
1160
1161   mLast = DetermineLastContent();
1162   if (!mLast) {
1163     SetEmpty();
1164     return NS_OK;
1165   }
1166
1167   mCurNode = mFirst;
1168
1169   return NS_OK;
1170 }
1171
1172 nsIContent* ContentSubtreeIterator::DetermineLastContent() const {
1173   nsIContent* lastCandidate = DetermineCandidateForLastContent();
1174   if (!lastCandidate) {
1175     return nullptr;
1176   }
1177
1178   // confirm that this last possible contained node is indeed contained.  Else
1179   // we have a range that does not fully contain any node.
1180
1181   const Maybe<bool> isNodeContainedInRange =
1182       RangeUtils::IsNodeContainedInRange(*lastCandidate, mRange);
1183   MOZ_ALWAYS_TRUE(isNodeContainedInRange);
1184   if (!isNodeContainedInRange.value()) {
1185     return nullptr;
1186   }
1187
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
1190   // node.
1191   return GetTopAncestorInRange(lastCandidate);
1192 }
1193
1194 /****************************************************************
1195  * ContentSubtreeIterator overrides of ContentIterator routines
1196  ****************************************************************/
1197
1198 // we can't call PositionAt in a subtree iterator...
1199 void ContentSubtreeIterator::First() { mCurNode = mFirst; }
1200
1201 // we can't call PositionAt in a subtree iterator...
1202 void ContentSubtreeIterator::Last() { mCurNode = mLast; }
1203
1204 void ContentSubtreeIterator::Next() {
1205   if (IsDone()) {
1206     return;
1207   }
1208
1209   if (mCurNode == mLast) {
1210     mCurNode = nullptr;
1211     return;
1212   }
1213
1214   nsINode* nextNode = ContentIteratorBase::GetNextSibling(
1215       mCurNode, IterAllowCrossShadowBoundary());
1216
1217   NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
1218
1219   int32_t i = mInclusiveAncestorsOfEndContainer.IndexOf(nextNode);
1220   while (i != -1) {
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());
1225     if (!root) {
1226       nextNode = nextNode->GetFirstChild();
1227     } else {
1228       nextNode = mRange->MayCrossShadowBoundary() ? root->GetFirstChild()
1229                                                   : nextNode->GetFirstChild();
1230     }
1231     NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
1232
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);
1238   }
1239
1240   mCurNode = nextNode;
1241 }
1242
1243 void ContentSubtreeIterator::Prev() {
1244   // Prev should be optimized to use the mStartNodes, just as Next
1245   // uses mInclusiveAncestorsOfEndContainer.
1246   if (IsDone()) {
1247     return;
1248   }
1249
1250   if (mCurNode == mFirst) {
1251     mCurNode = nullptr;
1252     return;
1253   }
1254
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);
1258
1259   prevNode = PrevNode(prevNode);
1260
1261   prevNode = ContentIteratorBase::GetDeepLastChild(prevNode);
1262
1263   mCurNode = GetTopAncestorInRange(prevNode);
1264 }
1265
1266 nsresult ContentSubtreeIterator::PositionAt(nsINode* aCurNode) {
1267   NS_ERROR("Not implemented!");
1268   return NS_ERROR_NOT_IMPLEMENTED;
1269 }
1270
1271 /****************************************************************
1272  * ContentSubtreeIterator helper routines
1273  ****************************************************************/
1274
1275 nsIContent* ContentSubtreeIterator::GetTopAncestorInRange(
1276     nsINode* aNode) const {
1277   if (!aNode ||
1278       !IteratorHelpers::GetParentNode(*aNode, IterAllowCrossShadowBoundary())) {
1279     return nullptr;
1280   }
1281
1282   // aNode has a parent, so it must be content.
1283   nsIContent* content = aNode->AsContent();
1284
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()) {
1291     return nullptr;
1292   }
1293
1294   nsIContent* lastContentInShadowTree = nullptr;
1295   while (content) {
1296     nsINode* parent = IteratorHelpers::GetParentNode(
1297         *content, IterAllowCrossShadowBoundary());
1298
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.
1302     //
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.
1306     //
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())) {
1311       return content;
1312     }
1313
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;
1324       }
1325       return content;
1326     }
1327
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.
1332     //
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;
1337     }
1338
1339     content = parent->AsContent();
1340   }
1341
1342   MOZ_CRASH("This should only be possible if aNode was null");
1343 }
1344
1345 #undef NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD
1346
1347 }  // namespace mozilla