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 = node->GetFirstChild();
 615
 616   if (!child) {
 617     if (ShadowRoot* shadowRoot =
 618             IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary)) {
 619       // If this node doesn't have a child, but it's also a shadow host
 620       // that can be selected, we go into this shadow tree.
 621       child = shadowRoot->GetFirstChild();
 622     }
 623   }
 624
 625   // FIXME(sefeng): This is problematic for slotted contents
 626   while (child) {
 627     node = child;
 628     child = node->GetFirstChild();
 629     if (!child) {
 630       if (ShadowRoot* shadowRoot =
 631               IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary)) {
 632         child = shadowRoot->GetFirstChild();
 633       }
 634     }
 635   }
 636
 637   return node;
 638 }
 639
 640 // static
 641 template <typename NodeType>
 642 nsINode* ContentIteratorBase<NodeType>::GetDeepLastChild(nsINode* aRoot) {
 643   if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
 644     return aRoot;
 645   }
 646
 647   return ContentIteratorBase::GetDeepLastChild(aRoot->GetLastChild());
 648 }
 649
 650 // static
 651 template <typename NodeType>
 652 nsIContent* ContentIteratorBase<NodeType>::GetDeepLastChild(
 653     nsIContent* aRoot, bool aAllowCrossShadowBoundary) {
 654   if (NS_WARN_IF(!aRoot)) {
 655     return nullptr;
 656   }
 657
 658   nsIContent* node = aRoot;
 659
 660   ShadowRoot* shadowRoot =
 661       IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary);
 662   // FIXME(sefeng): This doesn't work with slots / flattened tree.
 663   while (node->HasChildren() || (shadowRoot && shadowRoot->HasChildren())) {
 664     if (node->HasChildren()) {
 665       node = node->GetLastChild();
 666     } else {
 667       MOZ_ASSERT(shadowRoot);
 668       // If this node doesn't have a child, but it's also a shadow host
 669       // that can be selected, we go into this shadow tree.
 670       node = shadowRoot->GetLastChild();
 671     }
 672     shadowRoot =
 673         IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary);
 674   }
 675   return node;
 676 }
 677
 678 // Get the next sibling, or parent's next sibling, or shadow host's next
 679 // sibling (when aAllowCrossShadowBoundary is true), or grandpa's next
 680 // sibling...
 681 //
 682 // static
 683 //
 684 template <typename NodeType>
 685 nsIContent* ContentIteratorBase<NodeType>::GetNextSibling(
 686     nsINode* aNode, bool aAllowCrossShadowBoundary) {
 687   if (NS_WARN_IF(!aNode)) {
 688     return nullptr;
 689   }
 690
 691   if (nsIContent* next = aNode->GetNextSibling()) {
 692     return next;
 693   }
 694
 695   nsINode* parent =
 696       IteratorHelpers::GetParentNode(*aNode, aAllowCrossShadowBoundary);
 697   if (NS_WARN_IF(!parent)) {
 698     return nullptr;
 699   }
 700
 701   if (aAllowCrossShadowBoundary) {
 702     // This is temporary solution.
 703     // For shadow root, instead of getting to the sibling of the parent
 704     // directly, we need to get into the light tree of the parent to handle
 705     // slotted contents.
 706     if (ShadowRoot* shadowRoot = ShadowRoot::FromNode(aNode)) {
 707       if (nsIContent* child = parent->GetFirstChild()) {
 708         return child;
 709       }
 710     }
 711   }
 712
 713   return ContentIteratorBase::GetNextSibling(parent, aAllowCrossShadowBoundary);
 714 }
 715
 716 // Get the prev sibling, or parent's prev sibling, or shadow host's prev sibling
 717 // (when aAllowCrossShadowBoundary is true), or grandpa's prev sibling... static
 718 template <typename NodeType>
 719 nsIContent* ContentIteratorBase<NodeType>::GetPrevSibling(
 720     nsINode* aNode, bool aAllowCrossShadowBoundary) {
 721   if (NS_WARN_IF(!aNode)) {
 722     return nullptr;
 723   }
 724
 725   if (nsIContent* prev = aNode->GetPreviousSibling()) {
 726     return prev;
 727   }
 728
 729   nsINode* parent =
 730       IteratorHelpers::GetParentNode(*aNode, aAllowCrossShadowBoundary);
 731   if (NS_WARN_IF(!parent)) {
 732     return nullptr;
 733   }
 734
 735   return ContentIteratorBase::GetPrevSibling(parent, aAllowCrossShadowBoundary);
 736 }
 737
 738 template <typename NodeType>
 739 nsINode* ContentIteratorBase<NodeType>::NextNode(nsINode* aNode) {
 740   nsINode* node = aNode;
 741
 742   // if we are a Pre-order iterator, use pre-order
 743   if (mOrder == Order::Pre) {
 744     // if it has children then next node is first child
 745     if (node->HasChildren()) {
 746       nsIContent* firstChild = node->GetFirstChild();
 747       MOZ_ASSERT(firstChild);
 748
 749       return firstChild;
 750     }
 751
 752     // else next sibling is next
 753     return ContentIteratorBase::GetNextSibling(node);
 754   }
 755
 756   // post-order
 757   nsINode* parent = node->GetParentNode();
 758   if (NS_WARN_IF(!parent)) {
 759     MOZ_ASSERT(parent, "The node is the root node but not the last node");
 760     mCurNode = nullptr;
 761     return node;
 762   }
 763
 764   if (nsIContent* sibling = node->GetNextSibling()) {
 765     // next node is sibling's "deep left" child
 766     return ContentIteratorBase::GetDeepFirstChild(sibling);
 767   }
 768
 769   return parent;
 770 }
 771
 772 template <typename NodeType>
 773 nsINode* ContentIteratorBase<NodeType>::PrevNode(nsINode* aNode) {
 774   nsINode* node = aNode;
 775
 776   // if we are a Pre-order iterator, use pre-order
 777   if (mOrder == Order::Pre) {
 778     nsINode* parent = node->GetParentNode();
 779     if (NS_WARN_IF(!parent)) {
 780       MOZ_ASSERT(parent, "The node is the root node but not the first node");
 781       mCurNode = nullptr;
 782       return aNode;
 783     }
 784
 785     nsIContent* sibling = node->GetPreviousSibling();
 786     if (sibling) {
 787       return ContentIteratorBase::GetDeepLastChild(sibling);
 788     }
 789
 790     return parent;
 791   }
 792
 793   // post-order
 794   if (node->HasChildren()) {
 795     return node->GetLastChild();
 796   }
 797
 798   // else prev sibling is previous
 799   return ContentIteratorBase::GetPrevSibling(node);
 800 }
 801
 802 /******************************************************
 803  * ContentIteratorBase routines
 804  ******************************************************/
 805
 806 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, First);
 807
 808 template <typename NodeType>
 809 void ContentIteratorBase<NodeType>::First() {
 810   if (!mFirst) {
 811     MOZ_ASSERT(IsDone());
 812     mCurNode = nullptr;
 813     return;
 814   }
 815
 816   mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst);
 817   NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 818 }
 819
 820 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Last);
 821
 822 template <typename NodeType>
 823 void ContentIteratorBase<NodeType>::Last() {
 824   // Note that mLast can be nullptr if SetEmpty() is called in Init()
 825   // since at that time, Init() returns NS_OK.
 826   if (!mLast) {
 827     MOZ_ASSERT(IsDone());
 828     mCurNode = nullptr;
 829     return;
 830   }
 831
 832   mozilla::DebugOnly<nsresult> rv = PositionAt(mLast);
 833   NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 834 }
 835
 836 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Next);
 837
 838 template <typename NodeType>
 839 void ContentIteratorBase<NodeType>::Next() {
 840   if (IsDone()) {
 841     return;
 842   }
 843
 844   if (mCurNode == mLast) {
 845     mCurNode = nullptr;
 846     return;
 847   }
 848
 849   mCurNode = NextNode(mCurNode);
 850 }
 851
 852 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(void, Prev);
 853
 854 template <typename NodeType>
 855 void ContentIteratorBase<NodeType>::Prev() {
 856   if (IsDone()) {
 857     return;
 858   }
 859
 860   if (mCurNode == mFirst) {
 861     mCurNode = nullptr;
 862     return;
 863   }
 864
 865   mCurNode = PrevNode(mCurNode);
 866 }
 867
 868 // Keeping arrays of indexes for the stack of nodes makes PositionAt
 869 // interesting...
 870 NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD(nsresult, PositionAt, nsINode*);
 871
 872 template <typename NodeType>
 873 nsresult ContentIteratorBase<NodeType>::PositionAt(nsINode* aCurNode) {
 874   if (NS_WARN_IF(!aCurNode)) {
 875     return NS_ERROR_NULL_POINTER;
 876   }
 877
 878   // take an early out if this doesn't actually change the position
 879   if (mCurNode == aCurNode) {
 880     return NS_OK;
 881   }
 882   mCurNode = aCurNode;
 883
 884   // Check to see if the node falls within the traversal range.
 885
 886   RawRangeBoundary first(mFirst, 0u);
 887   RawRangeBoundary last(mLast, 0u);
 888
 889   if (mFirst && mLast) {
 890     if (mOrder == Order::Pre) {
 891       // In pre we want to record the point immediately before mFirst, which is
 892       // the point immediately after mFirst's previous sibling.
 893       first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()};
 894
 895       // If mLast has no children, then we want to make sure to include it.
 896       if (!mLast->HasChildren()) {
 897         last = {mLast->GetParentNode(), mLast->AsContent()};
 898       }
 899     } else {
 900       // If the first node has any children, we want to be immediately after the
 901       // last. Otherwise we want to be immediately before mFirst.
 902       if (mFirst->HasChildren()) {
 903         first = {mFirst, mFirst->GetLastChild()};
 904       } else {
 905         first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()};
 906       }
 907
 908       // Set the last point immediately after the final node.
 909       last = {mLast->GetParentNode(), mLast->AsContent()};
 910     }
 911   }
 912
 913   NS_WARNING_ASSERTION(first.IsSetAndValid(), "first is not valid");
 914   NS_WARNING_ASSERTION(last.IsSetAndValid(), "last is not valid");
 915
 916   // The end positions are always in the range even if it has no parent.  We
 917   // need to allow that or 'iter->Init(root)' would assert in Last() or First()
 918   // for example, bug 327694.
 919   if (mFirst != mCurNode && mLast != mCurNode &&
 920       (NS_WARN_IF(!first.IsSet()) || NS_WARN_IF(!last.IsSet()) ||
 921        NS_WARN_IF(!NodeIsInTraversalRange(mCurNode, mOrder == Order::Pre, first,
 922                                           last)))) {
 923     mCurNode = nullptr;
 924     return NS_ERROR_FAILURE;
 925   }
 926
 927   return NS_OK;
 928 }
 929
 930 /******************************************************
 931  * ContentSubtreeIterator init routines
 932  ******************************************************/
 933
 934 nsresult ContentSubtreeIterator::Init(nsINode* aRoot) {
 935   return NS_ERROR_NOT_IMPLEMENTED;
 936 }
 937
 938 nsresult ContentSubtreeIterator::Init(AbstractRange* aRange) {
 939   MOZ_ASSERT(aRange);
 940
 941   if (NS_WARN_IF(!aRange->IsPositioned())) {
 942     return NS_ERROR_INVALID_ARG;
 943   }
 944
 945   mRange = aRange;
 946
 947   return InitWithRange();
 948 }
 949
 950 nsresult ContentSubtreeIterator::Init(nsINode* aStartContainer,
 951                                       uint32_t aStartOffset,
 952                                       nsINode* aEndContainer,
 953                                       uint32_t aEndOffset) {
 954   return Init(RawRangeBoundary(aStartContainer, aStartOffset),
 955               RawRangeBoundary(aEndContainer, aEndOffset));
 956 }
 957
 958 nsresult ContentSubtreeIterator::Init(const RawRangeBoundary& aStartBoundary,
 959                                       const RawRangeBoundary& aEndBoundary) {
 960   RefPtr<nsRange> range =
 961       nsRange::Create(aStartBoundary, aEndBoundary, IgnoreErrors());
 962   if (NS_WARN_IF(!range) || NS_WARN_IF(!range->IsPositioned())) {
 963     return NS_ERROR_INVALID_ARG;
 964   }
 965
 966   if (NS_WARN_IF(range->StartRef() != aStartBoundary) ||
 967       NS_WARN_IF(range->EndRef() != aEndBoundary)) {
 968     return NS_ERROR_UNEXPECTED;
 969   }
 970
 971   mRange = std::move(range);
 972
 973   return InitWithRange();
 974 }
 975
 976 nsresult ContentSubtreeIterator::InitWithAllowCrossShadowBoundary(
 977     AbstractRange* aRange) {
 978   MOZ_ASSERT(aRange);
 979
 980   if (NS_WARN_IF(!aRange->IsPositioned())) {
 981     return NS_ERROR_INVALID_ARG;
 982   }
 983
 984   mRange = aRange;
 985
 986   mAllowCrossShadowBoundary = AllowRangeCrossShadowBoundary::Yes;
 987   return InitWithRange();
 988 }
 989
 990 void ContentSubtreeIterator::CacheInclusiveAncestorsOfEndContainer() {
 991   mInclusiveAncestorsOfEndContainer.Clear();
 992   nsINode* const endContainer =
 993       IteratorHelpers::GetEndContainer(mRange, IterAllowCrossShadowBoundary());
 994   nsIContent* endNode =
 995       endContainer->IsContent() ? endContainer->AsContent() : nullptr;
 996   while (endNode) {
 997     mInclusiveAncestorsOfEndContainer.AppendElement(endNode);
 998     // Cross the boundary for contents in shadow tree.
 999     nsINode* parent = IteratorHelpers::GetParentNode(
1000         *endNode, IterAllowCrossShadowBoundary());
1001     if (!parent || !parent->IsContent()) {
1002       break;
1003     }
1004     endNode = parent->AsContent();
1005   }
1006 }
1007
1008 nsIContent* ContentSubtreeIterator::DetermineCandidateForFirstContent() const {
1009   nsINode* startContainer = IteratorHelpers::GetStartContainer(
1010       mRange, IterAllowCrossShadowBoundary());
1011   nsIContent* firstCandidate = nullptr;
1012   // find first node in range
1013   nsINode* node = nullptr;
1014   if (!startContainer->GetChildCount()) {
1015     // no children, start at the node itself
1016     node = startContainer;
1017   } else {
1018     nsIContent* child =
1019         IterAllowCrossShadowBoundary()
1020             ? mRange->GetMayCrossShadowBoundaryChildAtStartOffset()
1021             : mRange->GetChildAtStartOffset();
1022
1023     MOZ_ASSERT(child == startContainer->GetChildAt_Deprecated(
1024                             IteratorHelpers::StartOffset(
1025                                 mRange, IterAllowCrossShadowBoundary())));
1026     if (!child) {
1027       // offset after last child
1028       node = startContainer;
1029     } else {
1030       firstCandidate = child;
1031     }
1032   }
1033
1034   if (!firstCandidate) {
1035     // then firstCandidate is next node after node
1036     firstCandidate = ContentIteratorBase::GetNextSibling(
1037         node, IterAllowCrossShadowBoundary());
1038   }
1039
1040   if (firstCandidate) {
1041     firstCandidate = ContentIteratorBase::GetDeepFirstChild(
1042         firstCandidate, IterAllowCrossShadowBoundary());
1043   }
1044
1045   return firstCandidate;
1046 }
1047
1048 nsIContent* ContentSubtreeIterator::DetermineFirstContent() const {
1049   nsIContent* firstCandidate = DetermineCandidateForFirstContent();
1050   if (!firstCandidate) {
1051     return nullptr;
1052   }
1053
1054   // confirm that this first possible contained node is indeed contained.  Else
1055   // we have a range that does not fully contain any node.
1056   const Maybe<bool> isNodeContainedInRange =
1057       RangeUtils::IsNodeContainedInRange(*firstCandidate, mRange);
1058   MOZ_ALWAYS_TRUE(isNodeContainedInRange);
1059   if (!isNodeContainedInRange.value()) {
1060     return nullptr;
1061   }
1062
1063   // cool, we have the first node in the range.  Now we walk up its ancestors
1064   // to find the most senior that is still in the range.  That's the real first
1065   // node.
1066   return GetTopAncestorInRange(firstCandidate);
1067 }
1068
1069 nsIContent* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
1070   nsIContent* lastCandidate{nullptr};
1071   nsINode* endContainer =
1072       IteratorHelpers::GetEndContainer(mRange, IterAllowCrossShadowBoundary());
1073   // now to find the last node
1074   int32_t offset =
1075       IteratorHelpers::EndOffset(mRange, IterAllowCrossShadowBoundary());
1076
1077   int32_t numChildren = endContainer->GetChildCount();
1078
1079   nsINode* node = nullptr;
1080   if (offset > numChildren) {
1081     // Can happen for text nodes
1082     offset = numChildren;
1083   }
1084   if (!offset || !numChildren) {
1085     node = endContainer;
1086   } else {
1087     lastCandidate = IterAllowCrossShadowBoundary()
1088                         ? mRange->MayCrossShadowBoundaryEndRef().Ref()
1089                         : mRange->EndRef().Ref();
1090     MOZ_ASSERT(lastCandidate == endContainer->GetChildAt_Deprecated(--offset));
1091     NS_ASSERTION(lastCandidate,
1092                  "tree traversal trouble in ContentSubtreeIterator::Init");
1093   }
1094
1095   if (!lastCandidate) {
1096     // then lastCandidate is prev node before node
1097     lastCandidate = ContentIteratorBase::GetPrevSibling(
1098         node, IterAllowCrossShadowBoundary());
1099   }
1100
1101   if (lastCandidate) {
1102     lastCandidate = ContentIteratorBase::GetDeepLastChild(
1103         lastCandidate, IterAllowCrossShadowBoundary());
1104   }
1105
1106   return lastCandidate;
1107 }
1108
1109 nsresult ContentSubtreeIterator::InitWithRange() {
1110   MOZ_ASSERT(mRange);
1111   MOZ_ASSERT(mRange->IsPositioned());
1112
1113   // get the start node and offset, convert to nsINode
1114   mClosestCommonInclusiveAncestor =
1115       mRange->GetClosestCommonInclusiveAncestor(mAllowCrossShadowBoundary);
1116
1117   nsINode* startContainer = IteratorHelpers::GetStartContainer(
1118       mRange, IterAllowCrossShadowBoundary());
1119   const int32_t startOffset =
1120       IteratorHelpers::StartOffset(mRange, IterAllowCrossShadowBoundary());
1121   nsINode* endContainer =
1122       IteratorHelpers::GetEndContainer(mRange, IterAllowCrossShadowBoundary());
1123   const int32_t endOffset =
1124       IteratorHelpers::EndOffset(mRange, IterAllowCrossShadowBoundary());
1125   MOZ_ASSERT(mClosestCommonInclusiveAncestor && startContainer && endContainer);
1126   // Bug 767169
1127   MOZ_ASSERT(uint32_t(startOffset) <= startContainer->Length() &&
1128              uint32_t(endOffset) <= endContainer->Length());
1129
1130   // short circuit when start node == end node
1131   if (startContainer == endContainer) {
1132     nsINode* child = startContainer->GetFirstChild();
1133
1134     if (!child || startOffset == endOffset) {
1135       // Text node, empty container, or collapsed
1136       SetEmpty();
1137       return NS_OK;
1138     }
1139   }
1140
1141   CacheInclusiveAncestorsOfEndContainer();
1142
1143   mFirst = DetermineFirstContent();
1144   if (!mFirst) {
1145     SetEmpty();
1146     return NS_OK;
1147   }
1148
1149   mLast = DetermineLastContent();
1150   if (!mLast) {
1151     SetEmpty();
1152     return NS_OK;
1153   }
1154
1155   mCurNode = mFirst;
1156
1157   return NS_OK;
1158 }
1159
1160 nsIContent* ContentSubtreeIterator::DetermineLastContent() const {
1161   nsIContent* lastCandidate = DetermineCandidateForLastContent();
1162   if (!lastCandidate) {
1163     return nullptr;
1164   }
1165
1166   // confirm that this last possible contained node is indeed contained.  Else
1167   // we have a range that does not fully contain any node.
1168
1169   const Maybe<bool> isNodeContainedInRange =
1170       RangeUtils::IsNodeContainedInRange(*lastCandidate, mRange);
1171   MOZ_ALWAYS_TRUE(isNodeContainedInRange);
1172   if (!isNodeContainedInRange.value()) {
1173     return nullptr;
1174   }
1175
1176   // cool, we have the last node in the range.  Now we walk up its ancestors to
1177   // find the most senior that is still in the range.  That's the real first
1178   // node.
1179   return GetTopAncestorInRange(lastCandidate);
1180 }
1181
1182 /****************************************************************
1183  * ContentSubtreeIterator overrides of ContentIterator routines
1184  ****************************************************************/
1185
1186 // we can't call PositionAt in a subtree iterator...
1187 void ContentSubtreeIterator::First() { mCurNode = mFirst; }
1188
1189 // we can't call PositionAt in a subtree iterator...
1190 void ContentSubtreeIterator::Last() { mCurNode = mLast; }
1191
1192 void ContentSubtreeIterator::Next() {
1193   if (IsDone()) {
1194     return;
1195   }
1196
1197   if (mCurNode == mLast) {
1198     mCurNode = nullptr;
1199     return;
1200   }
1201
1202   nsINode* nextNode = ContentIteratorBase::GetNextSibling(
1203       mCurNode, IterAllowCrossShadowBoundary());
1204
1205   MOZ_ASSERT(nextNode, "No next sibling!?! This could mean deadlock!");
1206
1207   int32_t i = mInclusiveAncestorsOfEndContainer.IndexOf(nextNode);
1208   while (i != -1) {
1209     // as long as we are finding ancestors of the endpoint of the range,
1210     // dive down into their children
1211     ShadowRoot* root = IteratorHelpers::GetShadowRoot(
1212         Element::FromNode(nextNode), IterAllowCrossShadowBoundary());
1213     if (!root) {
1214       nextNode = nextNode->GetFirstChild();
1215     } else {
1216       nextNode = mRange->MayCrossShadowBoundary() ? root->GetFirstChild()
1217                                                   : nextNode->GetFirstChild();
1218     }
1219     MOZ_ASSERT(nextNode, "Iterator error, expected a child node!");
1220
1221     // should be impossible to get a null pointer.  If we went all the way
1222     // down the child chain to the bottom without finding an interior node,
1223     // then the previous node should have been the last, which was
1224     // was tested at top of routine.
1225     i = mInclusiveAncestorsOfEndContainer.IndexOf(nextNode);
1226   }
1227
1228   mCurNode = nextNode;
1229 }
1230
1231 void ContentSubtreeIterator::Prev() {
1232   // Prev should be optimized to use the mStartNodes, just as Next
1233   // uses mInclusiveAncestorsOfEndContainer.
1234   if (IsDone()) {
1235     return;
1236   }
1237
1238   if (mCurNode == mFirst) {
1239     mCurNode = nullptr;
1240     return;
1241   }
1242
1243   // If any of these function calls return null, so will all succeeding ones,
1244   // so mCurNode will wind up set to null.
1245   nsINode* prevNode = ContentIteratorBase::GetDeepFirstChild(mCurNode);
1246
1247   prevNode = PrevNode(prevNode);
1248
1249   prevNode = ContentIteratorBase::GetDeepLastChild(prevNode);
1250
1251   mCurNode = GetTopAncestorInRange(prevNode);
1252 }
1253
1254 nsresult ContentSubtreeIterator::PositionAt(nsINode* aCurNode) {
1255   NS_ERROR("Not implemented!");
1256   return NS_ERROR_NOT_IMPLEMENTED;
1257 }
1258
1259 /****************************************************************
1260  * ContentSubtreeIterator helper routines
1261  ****************************************************************/
1262
1263 nsIContent* ContentSubtreeIterator::GetTopAncestorInRange(
1264     nsINode* aNode) const {
1265   if (!aNode ||
1266       !IteratorHelpers::GetParentNode(*aNode, IterAllowCrossShadowBoundary())) {
1267     return nullptr;
1268   }
1269
1270   // aNode has a parent, so it must be content.
1271   nsIContent* content = aNode->AsContent();
1272
1273   // sanity check: aNode is itself in the range
1274   Maybe<bool> isNodeContainedInRange =
1275       RangeUtils::IsNodeContainedInRange(*aNode, mRange);
1276   NS_ASSERTION(isNodeContainedInRange && isNodeContainedInRange.value(),
1277                "aNode isn't in mRange, or something else weird happened");
1278   if (!isNodeContainedInRange || !isNodeContainedInRange.value()) {
1279     return nullptr;
1280   }
1281
1282   nsIContent* lastContentInShadowTree = nullptr;
1283   while (content) {
1284     nsINode* parent = IteratorHelpers::GetParentNode(
1285         *content, IterAllowCrossShadowBoundary());
1286
1287     // content always has a parent.  If its parent is the root, however --
1288     // i.e., either it's not content, or it is content but its own parent is
1289     // null -- then we're finished, since we don't go up to the root.
1290     //
1291     // Caveat: If iteration crossing shadow boundary is allowed
1292     // and the root is a shadow root, we keep going up to the
1293     // shadow host and continue.
1294     //
1295     // We have to special-case this because CompareNodeToRange treats the root
1296     // node differently -- see bug 765205.
1297     if (!parent || !IteratorHelpers::GetParentNode(
1298                        *parent, IterAllowCrossShadowBoundary())) {
1299       return content;
1300     }
1301
1302     isNodeContainedInRange =
1303         RangeUtils::IsNodeContainedInRange(*parent, mRange);
1304     MOZ_ALWAYS_TRUE(isNodeContainedInRange);
1305     if (!isNodeContainedInRange.value()) {
1306       if (IterAllowCrossShadowBoundary() && content->IsShadowRoot()) {
1307         MOZ_ASSERT(parent->GetShadowRoot() == content);
1308         // host element is not in range, the last content in tree
1309         // should be the ancestor.
1310         MOZ_ASSERT(lastContentInShadowTree);
1311         return lastContentInShadowTree;
1312       }
1313       return content;
1314     }
1315
1316     // When we cross the boundary, we keep a reference to the
1317     // last content that is in tree, because if we later
1318     // find the shadow host element is not in the range, that means
1319     // the last content in the tree should be top ancestor in range.
1320     //
1321     // Using shadow root doesn't make sense here because it doesn't
1322     // represent a actual content.
1323     if (IterAllowCrossShadowBoundary() && parent->IsShadowRoot()) {
1324       lastContentInShadowTree = content;
1325     }
1326
1327     content = parent->AsContent();
1328   }
1329
1330   MOZ_CRASH("This should only be possible if aNode was null");
1331 }
1332
1333 #undef NS_INSTANTIATE_CONTENT_ITER_BASE_METHOD
1334
1335 }  // namespace mozilla