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/DebugOnly.h"
  10 #include "mozilla/RangeBoundary.h"
  11 #include "mozilla/RangeUtils.h"
  12 #include "mozilla/Result.h"
  13
  14 #include "nsContentUtils.h"
  15 #include "nsElementTable.h"
  16 #include "nsIContent.h"
  17 #include "nsRange.h"
  18
  19 namespace mozilla {
  20
  21 static bool ComparePostMode(const RawRangeBoundary& aStart,
  22                             const RawRangeBoundary& aEnd, nsINode& aNode) {
  23   nsINode* parent = aNode.GetParentNode();
  24   if (!parent) {
  25     return false;
  26   }
  27
  28   // aNode should always be content, as we have a parent, but let's just be
  29   // extra careful and check.
  30   nsIContent* content =
  31       NS_WARN_IF(!aNode.IsContent()) ? nullptr : aNode.AsContent();
  32
  33   // Post mode: start < node <= end.
  34   RawRangeBoundary afterNode(parent, content);
  35   const auto isStartLessThanAfterNode = [&]() {
  36     const Maybe<int32_t> startComparedToAfterNode =
  37         nsContentUtils::ComparePoints(aStart, afterNode);
  38     return !NS_WARN_IF(!startComparedToAfterNode) &&
  39            (*startComparedToAfterNode < 0);
  40   };
  41
  42   const auto isAfterNodeLessOrEqualToEnd = [&]() {
  43     const Maybe<int32_t> afterNodeComparedToEnd =
  44         nsContentUtils::ComparePoints(afterNode, aEnd);
  45     return !NS_WARN_IF(!afterNodeComparedToEnd) &&
  46            (*afterNodeComparedToEnd <= 0);
  47   };
  48
  49   return isStartLessThanAfterNode() && isAfterNodeLessOrEqualToEnd();
  50 }
  51
  52 static bool ComparePreMode(const RawRangeBoundary& aStart,
  53                            const RawRangeBoundary& aEnd, nsINode& aNode) {
  54   nsINode* parent = aNode.GetParentNode();
  55   if (!parent) {
  56     return false;
  57   }
  58
  59   // Pre mode: start <= node < end.
  60   RawRangeBoundary beforeNode(parent, aNode.GetPreviousSibling());
  61
  62   const auto isStartLessOrEqualToBeforeNode = [&]() {
  63     const Maybe<int32_t> startComparedToBeforeNode =
  64         nsContentUtils::ComparePoints(aStart, beforeNode);
  65     return !NS_WARN_IF(!startComparedToBeforeNode) &&
  66            (*startComparedToBeforeNode <= 0);
  67   };
  68
  69   const auto isBeforeNodeLessThanEndNode = [&]() {
  70     const Maybe<int32_t> beforeNodeComparedToEnd =
  71         nsContentUtils::ComparePoints(beforeNode, aEnd);
  72     return !NS_WARN_IF(!beforeNodeComparedToEnd) &&
  73            (*beforeNodeComparedToEnd < 0);
  74   };
  75
  76   return isStartLessOrEqualToBeforeNode() && isBeforeNodeLessThanEndNode();
  77 }
  78
  79 ///////////////////////////////////////////////////////////////////////////
  80 // NodeIsInTraversalRange: returns true if content is visited during
  81 // the traversal of the range in the specified mode.
  82 //
  83 static bool NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode,
  84                                    const RawRangeBoundary& aStart,
  85                                    const RawRangeBoundary& aEnd) {
  86   if (NS_WARN_IF(!aStart.IsSet()) || NS_WARN_IF(!aEnd.IsSet()) ||
  87       NS_WARN_IF(!aNode)) {
  88     return false;
  89   }
  90
  91   // If a leaf node contains an end point of the traversal range, it is
  92   // always in the traversal range.
  93   if (aNode == aStart.Container() || aNode == aEnd.Container()) {
  94     if (aNode->IsCharacterData()) {
  95       return true;  // text node or something
  96     }
  97     if (!aNode->HasChildren()) {
  98       MOZ_ASSERT(
  99           aNode != aStart.Container() || aStart.IsStartOfContainer(),
 100           "aStart.Container() doesn't have children and not a data node, "
 101           "aStart should be at the beginning of its container");
 102       MOZ_ASSERT(aNode != aEnd.Container() || aEnd.IsStartOfContainer(),
 103                  "aEnd.Container() doesn't have children and not a data node, "
 104                  "aEnd should be at the beginning of its container");
 105       return true;
 106     }
 107   }
 108
 109   if (aIsPreMode) {
 110     return ComparePreMode(aStart, aEnd, *aNode);
 111   }
 112
 113   return ComparePostMode(aStart, aEnd, *aNode);
 114 }
 115
 116 // Each concreate class of ContentIteratorBase may be owned by another class
 117 // which may be owned by JS.  Therefore, all of them should be in the cycle
 118 // collection.  However, we cannot make non-refcountable classes only with the
 119 // macros.  So, we need to make them cycle collectable without the macros.
 120 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
 121                                  ContentIteratorBase& aField, const char* aName,
 122                                  uint32_t aFlags = 0) {
 123   ImplCycleCollectionTraverse(aCallback, aField.mCurNode, aName, aFlags);
 124   ImplCycleCollectionTraverse(aCallback, aField.mFirst, aName, aFlags);
 125   ImplCycleCollectionTraverse(aCallback, aField.mLast, aName, aFlags);
 126   ImplCycleCollectionTraverse(aCallback, aField.mClosestCommonInclusiveAncestor,
 127                               aName, aFlags);
 128 }
 129
 130 void ImplCycleCollectionUnlink(ContentIteratorBase& aField) {
 131   ImplCycleCollectionUnlink(aField.mCurNode);
 132   ImplCycleCollectionUnlink(aField.mFirst);
 133   ImplCycleCollectionUnlink(aField.mLast);
 134   ImplCycleCollectionUnlink(aField.mClosestCommonInclusiveAncestor);
 135 }
 136
 137 ContentIteratorBase::ContentIteratorBase(Order aOrder) : mOrder(aOrder) {}
 138
 139 ContentIteratorBase::~ContentIteratorBase() = default;
 140
 141 /******************************************************
 142  * Init routines
 143  ******************************************************/
 144
 145 nsresult ContentIteratorBase::Init(nsINode* aRoot) {
 146   if (NS_WARN_IF(!aRoot)) {
 147     return NS_ERROR_NULL_POINTER;
 148   }
 149
 150   if (mOrder == Order::Pre) {
 151     mFirst = aRoot;
 152     mLast = ContentIteratorBase::GetDeepLastChild(aRoot);
 153     NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
 154   } else {
 155     mFirst = ContentIteratorBase::GetDeepFirstChild(aRoot);
 156     NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
 157     mLast = aRoot;
 158   }
 159
 160   mClosestCommonInclusiveAncestor = aRoot;
 161   mCurNode = mFirst;
 162   return NS_OK;
 163 }
 164
 165 nsresult ContentIteratorBase::Init(nsRange* aRange) {
 166   if (NS_WARN_IF(!aRange)) {
 167     return NS_ERROR_INVALID_ARG;
 168   }
 169
 170   if (NS_WARN_IF(!aRange->IsPositioned())) {
 171     return NS_ERROR_INVALID_ARG;
 172   }
 173
 174   return InitInternal(aRange->StartRef().AsRaw(), aRange->EndRef().AsRaw());
 175 }
 176
 177 nsresult ContentIteratorBase::Init(nsINode* aStartContainer,
 178                                    uint32_t aStartOffset,
 179                                    nsINode* aEndContainer,
 180                                    uint32_t aEndOffset) {
 181   if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStartContainer, aStartOffset,
 182                                             aEndContainer, aEndOffset))) {
 183     return NS_ERROR_INVALID_ARG;
 184   }
 185
 186   return InitInternal(RawRangeBoundary(aStartContainer, aStartOffset),
 187                       RawRangeBoundary(aEndContainer, aEndOffset));
 188 }
 189
 190 nsresult ContentIteratorBase::Init(const RawRangeBoundary& aStart,
 191                                    const RawRangeBoundary& aEnd) {
 192   if (NS_WARN_IF(!RangeUtils::IsValidPoints(aStart, aEnd))) {
 193     return NS_ERROR_INVALID_ARG;
 194   }
 195
 196   return InitInternal(aStart, aEnd);
 197 }
 198
 199 class MOZ_STACK_CLASS ContentIteratorBase::Initializer final {
 200  public:
 201   Initializer(ContentIteratorBase& aIterator, const RawRangeBoundary& aStart,
 202               const RawRangeBoundary& aEnd)
 203       : mIterator{aIterator},
 204         mStart{aStart},
 205         mEnd{aEnd},
 206         mStartIsCharacterData{mStart.Container()->IsCharacterData()} {
 207     MOZ_ASSERT(mStart.IsSetAndValid());
 208     MOZ_ASSERT(mEnd.IsSetAndValid());
 209   }
 210
 211   nsresult Run();
 212
 213  private:
 214   /**
 215    * @return may be nullptr.
 216    */
 217   nsINode* DetermineFirstNode() const;
 218
 219   /**
 220    * @return may be nullptr.
 221    */
 222   [[nodiscard]] Result<nsINode*, nsresult> DetermineLastNode() const;
 223
 224   bool IsCollapsedNonCharacterRange() const;
 225   bool IsSingleNodeCharacterRange() const;
 226
 227   ContentIteratorBase& mIterator;
 228   const RawRangeBoundary& mStart;
 229   const RawRangeBoundary& mEnd;
 230   const bool mStartIsCharacterData;
 231 };
 232
 233 nsresult ContentIteratorBase::InitInternal(const RawRangeBoundary& aStart,
 234                                            const RawRangeBoundary& aEnd) {
 235   Initializer initializer{*this, aStart, aEnd};
 236   return initializer.Run();
 237 }
 238
 239 bool ContentIteratorBase::Initializer::IsCollapsedNonCharacterRange() const {
 240   return !mStartIsCharacterData && mStart == mEnd;
 241 }
 242
 243 bool ContentIteratorBase::Initializer::IsSingleNodeCharacterRange() const {
 244   return mStartIsCharacterData && mStart.Container() == mEnd.Container();
 245 }
 246
 247 nsresult ContentIteratorBase::Initializer::Run() {
 248   // get common content parent
 249   mIterator.mClosestCommonInclusiveAncestor =
 250       nsContentUtils::GetClosestCommonInclusiveAncestor(mStart.Container(),
 251                                                         mEnd.Container());
 252   if (NS_WARN_IF(!mIterator.mClosestCommonInclusiveAncestor)) {
 253     return NS_ERROR_FAILURE;
 254   }
 255
 256   // Check to see if we have a collapsed range, if so, there is nothing to
 257   // iterate over.
 258   //
 259   // XXX: CharacterDataNodes (text nodes) are currently an exception, since
 260   //      we always want to be able to iterate text nodes at the end points
 261   //      of a range.
 262
 263   if (IsCollapsedNonCharacterRange()) {
 264     mIterator.SetEmpty();
 265     return NS_OK;
 266   }
 267
 268   if (IsSingleNodeCharacterRange()) {
 269     mIterator.mFirst = mStart.Container()->AsContent();
 270     mIterator.mLast = mIterator.mFirst;
 271     mIterator.mCurNode = mIterator.mFirst;
 272
 273     return NS_OK;
 274   }
 275
 276   mIterator.mFirst = DetermineFirstNode();
 277
 278   if (Result<nsINode*, nsresult> lastNode = DetermineLastNode();
 279       NS_WARN_IF(lastNode.isErr())) {
 280     return lastNode.unwrapErr();
 281   } else {
 282     mIterator.mLast = lastNode.unwrap();
 283   }
 284
 285   // If either first or last is null, they both have to be null!
 286   if (!mIterator.mFirst || !mIterator.mLast) {
 287     mIterator.SetEmpty();
 288   }
 289
 290   mIterator.mCurNode = mIterator.mFirst;
 291
 292   return NS_OK;
 293 }
 294
 295 nsINode* ContentIteratorBase::Initializer::DetermineFirstNode() const {
 296   nsIContent* cChild = nullptr;
 297
 298   // Try to get the child at our starting point. This might return null if
 299   // mStart is immediately after the last node in mStart.Container().
 300   if (!mStartIsCharacterData) {
 301     cChild = mStart.GetChildAtOffset();
 302   }
 303
 304   if (!cChild) {
 305     // No children (possibly a <br> or text node), or index is after last child.
 306
 307     if (mIterator.mOrder == Order::Pre) {
 308       // XXX: In the future, if start offset is after the last
 309       //      character in the cdata node, should we set mFirst to
 310       //      the next sibling?
 311
 312       // Normally we would skip the start node because the start node is outside
 313       // of the range in pre mode. However, if aStartOffset == 0, and the node
 314       // is a non-container node (e.g. <br>), we don't skip the node in this
 315       // case in order to address bug 1215798.
 316       bool startIsContainer = true;
 317       if (mStart.Container()->IsHTMLElement()) {
 318         nsAtom* name = mStart.Container()->NodeInfo()->NameAtom();
 319         startIsContainer =
 320             nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name));
 321       }
 322       if (!mStartIsCharacterData &&
 323           (startIsContainer || !mStart.IsStartOfContainer())) {
 324         nsINode* const result =
 325             ContentIteratorBase::GetNextSibling(mStart.Container());
 326         NS_WARNING_ASSERTION(result, "GetNextSibling returned null");
 327
 328         // Does mFirst node really intersect the range?  The range could be
 329         // 'degenerate', i.e., not collapsed but still contain no content.
 330         if (result &&
 331             NS_WARN_IF(!NodeIsInTraversalRange(
 332                 result, mIterator.mOrder == Order::Pre, mStart, mEnd))) {
 333           return nullptr;
 334         }
 335
 336         return result;
 337       }
 338       return mStart.Container()->AsContent();
 339     }
 340
 341     // post-order
 342     if (NS_WARN_IF(!mStart.Container()->IsContent())) {
 343       // What else can we do?
 344       return nullptr;
 345     }
 346     return mStart.Container()->AsContent();
 347   }
 348
 349   if (mIterator.mOrder == Order::Pre) {
 350     return cChild;
 351   }
 352
 353   // post-order
 354   nsINode* const result = ContentIteratorBase::GetDeepFirstChild(cChild);
 355   NS_WARNING_ASSERTION(result, "GetDeepFirstChild returned null");
 356
 357   // Does mFirst node really intersect the range?  The range could be
 358   // 'degenerate', i.e., not collapsed but still contain no content.
 359   if (result && !NodeIsInTraversalRange(result, mIterator.mOrder == Order::Pre,
 360                                         mStart, mEnd)) {
 361     return nullptr;
 362   }
 363
 364   return result;
 365 }
 366
 367 Result<nsINode*, nsresult> ContentIteratorBase::Initializer::DetermineLastNode()
 368     const {
 369   const bool endIsCharacterData = mEnd.Container()->IsCharacterData();
 370
 371   if (endIsCharacterData || !mEnd.Container()->HasChildren() ||
 372       mEnd.IsStartOfContainer()) {
 373     if (mIterator.mOrder == Order::Pre) {
 374       if (NS_WARN_IF(!mEnd.Container()->IsContent())) {
 375         // Not much else to do here...
 376         return nullptr;
 377       }
 378
 379       // If the end node is a non-container element and the end offset is 0,
 380       // the last element should be the previous node (i.e., shouldn't
 381       // include the end node in the range).
 382       bool endIsContainer = true;
 383       if (mEnd.Container()->IsHTMLElement()) {
 384         nsAtom* name = mEnd.Container()->NodeInfo()->NameAtom();
 385         endIsContainer =
 386             nsHTMLElement::IsContainer(nsHTMLTags::AtomTagToId(name));
 387       }
 388       if (!endIsCharacterData && !endIsContainer && mEnd.IsStartOfContainer()) {
 389         nsINode* const result = mIterator.PrevNode(mEnd.Container());
 390         NS_WARNING_ASSERTION(result, "PrevNode returned null");
 391         if (result && result != mIterator.mFirst &&
 392             NS_WARN_IF(!NodeIsInTraversalRange(
 393                 result, mIterator.mOrder == Order::Pre,
 394                 RawRangeBoundary(mIterator.mFirst, 0u), mEnd))) {
 395           return nullptr;
 396         }
 397
 398         return result;
 399       }
 400
 401       return mEnd.Container()->AsContent();
 402     }
 403
 404     // post-order
 405     //
 406     // XXX: In the future, if end offset is before the first character in the
 407     //      cdata node, should we set mLast to the prev sibling?
 408
 409     if (!endIsCharacterData) {
 410       nsINode* const result =
 411           ContentIteratorBase::GetPrevSibling(mEnd.Container());
 412       NS_WARNING_ASSERTION(result, "GetPrevSibling returned null");
 413
 414       if (!NodeIsInTraversalRange(result, mIterator.mOrder == Order::Pre,
 415                                   mStart, mEnd)) {
 416         return nullptr;
 417       }
 418       return result;
 419     }
 420     return mEnd.Container()->AsContent();
 421   }
 422
 423   nsIContent* cChild = mEnd.Ref();
 424
 425   if (NS_WARN_IF(!cChild)) {
 426     // No child at offset!
 427     MOZ_ASSERT_UNREACHABLE("ContentIterator::ContentIterator");
 428     return Err(NS_ERROR_FAILURE);
 429   }
 430
 431   if (mIterator.mOrder == Order::Pre) {
 432     nsINode* const result = ContentIteratorBase::GetDeepLastChild(cChild);
 433     NS_WARNING_ASSERTION(result, "GetDeepLastChild returned null");
 434
 435     if (NS_WARN_IF(!NodeIsInTraversalRange(
 436             result, mIterator.mOrder == Order::Pre, mStart, mEnd))) {
 437       return nullptr;
 438     }
 439
 440     return result;
 441   }
 442
 443   // post-order
 444   return cChild;
 445 }
 446
 447 void ContentIteratorBase::SetEmpty() {
 448   mCurNode = nullptr;
 449   mFirst = nullptr;
 450   mLast = nullptr;
 451   mClosestCommonInclusiveAncestor = nullptr;
 452 }
 453
 454 // static
 455 nsINode* ContentIteratorBase::GetDeepFirstChild(nsINode* aRoot) {
 456   if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
 457     return aRoot;
 458   }
 459
 460   return ContentIteratorBase::GetDeepFirstChild(aRoot->GetFirstChild());
 461 }
 462
 463 // static
 464 nsIContent* ContentIteratorBase::GetDeepFirstChild(nsIContent* aRoot) {
 465   if (NS_WARN_IF(!aRoot)) {
 466     return nullptr;
 467   }
 468
 469   nsIContent* node = aRoot;
 470   nsIContent* child = node->GetFirstChild();
 471
 472   while (child) {
 473     node = child;
 474     child = node->GetFirstChild();
 475   }
 476
 477   return node;
 478 }
 479
 480 // static
 481 nsINode* ContentIteratorBase::GetDeepLastChild(nsINode* aRoot) {
 482   if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
 483     return aRoot;
 484   }
 485
 486   return ContentIteratorBase::GetDeepLastChild(aRoot->GetLastChild());
 487 }
 488
 489 // static
 490 nsIContent* ContentIteratorBase::GetDeepLastChild(nsIContent* aRoot) {
 491   if (NS_WARN_IF(!aRoot)) {
 492     return nullptr;
 493   }
 494
 495   nsIContent* node = aRoot;
 496   while (node->HasChildren()) {
 497     nsIContent* child = node->GetLastChild();
 498     node = child;
 499   }
 500   return node;
 501 }
 502
 503 // Get the next sibling, or parent's next sibling, or grandpa's next sibling...
 504 // static
 505 nsIContent* ContentIteratorBase::GetNextSibling(nsINode* aNode) {
 506   if (NS_WARN_IF(!aNode)) {
 507     return nullptr;
 508   }
 509
 510   if (aNode->GetNextSibling()) {
 511     return aNode->GetNextSibling();
 512   }
 513
 514   nsINode* parent = aNode->GetParentNode();
 515   if (NS_WARN_IF(!parent)) {
 516     return nullptr;
 517   }
 518
 519   // XXX This is a hack to preserve previous behaviour: This should be fixed
 520   // in bug 1404916. If we were positioned on anonymous content, move to
 521   // the first child of our parent.
 522   if (parent->GetLastChild() && parent->GetLastChild() != aNode) {
 523     return parent->GetFirstChild();
 524   }
 525
 526   return ContentIteratorBase::GetNextSibling(parent);
 527 }
 528
 529 // Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
 530 // static
 531 nsIContent* ContentIteratorBase::GetPrevSibling(nsINode* aNode) {
 532   if (NS_WARN_IF(!aNode)) {
 533     return nullptr;
 534   }
 535
 536   if (aNode->GetPreviousSibling()) {
 537     return aNode->GetPreviousSibling();
 538   }
 539
 540   nsINode* parent = aNode->GetParentNode();
 541   if (NS_WARN_IF(!parent)) {
 542     return nullptr;
 543   }
 544
 545   // XXX This is a hack to preserve previous behaviour: This should be fixed
 546   // in bug 1404916. If we were positioned on anonymous content, move to
 547   // the last child of our parent.
 548   if (parent->GetFirstChild() && parent->GetFirstChild() != aNode) {
 549     return parent->GetLastChild();
 550   }
 551
 552   return ContentIteratorBase::GetPrevSibling(parent);
 553 }
 554
 555 nsINode* ContentIteratorBase::NextNode(nsINode* aNode) {
 556   nsINode* node = aNode;
 557
 558   // if we are a Pre-order iterator, use pre-order
 559   if (mOrder == Order::Pre) {
 560     // if it has children then next node is first child
 561     if (node->HasChildren()) {
 562       nsIContent* firstChild = node->GetFirstChild();
 563       MOZ_ASSERT(firstChild);
 564
 565       return firstChild;
 566     }
 567
 568     // else next sibling is next
 569     return ContentIteratorBase::GetNextSibling(node);
 570   }
 571
 572   // post-order
 573   nsINode* parent = node->GetParentNode();
 574   if (NS_WARN_IF(!parent)) {
 575     MOZ_ASSERT(parent, "The node is the root node but not the last node");
 576     mCurNode = nullptr;
 577     return node;
 578   }
 579
 580   if (nsIContent* sibling = node->GetNextSibling()) {
 581     // next node is sibling's "deep left" child
 582     return ContentIteratorBase::GetDeepFirstChild(sibling);
 583   }
 584
 585   return parent;
 586 }
 587
 588 nsINode* ContentIteratorBase::PrevNode(nsINode* aNode) {
 589   nsINode* node = aNode;
 590
 591   // if we are a Pre-order iterator, use pre-order
 592   if (mOrder == Order::Pre) {
 593     nsINode* parent = node->GetParentNode();
 594     if (NS_WARN_IF(!parent)) {
 595       MOZ_ASSERT(parent, "The node is the root node but not the first node");
 596       mCurNode = nullptr;
 597       return aNode;
 598     }
 599
 600     nsIContent* sibling = node->GetPreviousSibling();
 601     if (sibling) {
 602       return ContentIteratorBase::GetDeepLastChild(sibling);
 603     }
 604
 605     return parent;
 606   }
 607
 608   // post-order
 609   if (node->HasChildren()) {
 610     return node->GetLastChild();
 611   }
 612
 613   // else prev sibling is previous
 614   return ContentIteratorBase::GetPrevSibling(node);
 615 }
 616
 617 /******************************************************
 618  * ContentIteratorBase routines
 619  ******************************************************/
 620
 621 void ContentIteratorBase::First() {
 622   if (!mFirst) {
 623     MOZ_ASSERT(IsDone());
 624     mCurNode = nullptr;
 625     return;
 626   }
 627
 628   mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst);
 629   NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 630 }
 631
 632 void ContentIteratorBase::Last() {
 633   // Note that mLast can be nullptr if SetEmpty() is called in Init()
 634   // since at that time, Init() returns NS_OK.
 635   if (!mLast) {
 636     MOZ_ASSERT(IsDone());
 637     mCurNode = nullptr;
 638     return;
 639   }
 640
 641   mozilla::DebugOnly<nsresult> rv = PositionAt(mLast);
 642   NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
 643 }
 644
 645 void ContentIteratorBase::Next() {
 646   if (IsDone()) {
 647     return;
 648   }
 649
 650   if (mCurNode == mLast) {
 651     mCurNode = nullptr;
 652     return;
 653   }
 654
 655   mCurNode = NextNode(mCurNode);
 656 }
 657
 658 void ContentIteratorBase::Prev() {
 659   if (IsDone()) {
 660     return;
 661   }
 662
 663   if (mCurNode == mFirst) {
 664     mCurNode = nullptr;
 665     return;
 666   }
 667
 668   mCurNode = PrevNode(mCurNode);
 669 }
 670
 671 // Keeping arrays of indexes for the stack of nodes makes PositionAt
 672 // interesting...
 673 nsresult ContentIteratorBase::PositionAt(nsINode* aCurNode) {
 674   if (NS_WARN_IF(!aCurNode)) {
 675     return NS_ERROR_NULL_POINTER;
 676   }
 677
 678   // take an early out if this doesn't actually change the position
 679   if (mCurNode == aCurNode) {
 680     return NS_OK;
 681   }
 682   mCurNode = aCurNode;
 683
 684   // Check to see if the node falls within the traversal range.
 685
 686   RawRangeBoundary first(mFirst, 0u);
 687   RawRangeBoundary last(mLast, 0u);
 688
 689   if (mFirst && mLast) {
 690     if (mOrder == Order::Pre) {
 691       // In pre we want to record the point immediately before mFirst, which is
 692       // the point immediately after mFirst's previous sibling.
 693       first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()};
 694
 695       // If mLast has no children, then we want to make sure to include it.
 696       if (!mLast->HasChildren()) {
 697         last = {mLast->GetParentNode(), mLast->AsContent()};
 698       }
 699     } else {
 700       // If the first node has any children, we want to be immediately after the
 701       // last. Otherwise we want to be immediately before mFirst.
 702       if (mFirst->HasChildren()) {
 703         first = {mFirst, mFirst->GetLastChild()};
 704       } else {
 705         first = {mFirst->GetParentNode(), mFirst->GetPreviousSibling()};
 706       }
 707
 708       // Set the last point immediately after the final node.
 709       last = {mLast->GetParentNode(), mLast->AsContent()};
 710     }
 711   }
 712
 713   NS_WARNING_ASSERTION(first.IsSetAndValid(), "first is not valid");
 714   NS_WARNING_ASSERTION(last.IsSetAndValid(), "last is not valid");
 715
 716   // The end positions are always in the range even if it has no parent.  We
 717   // need to allow that or 'iter->Init(root)' would assert in Last() or First()
 718   // for example, bug 327694.
 719   if (mFirst != mCurNode && mLast != mCurNode &&
 720       (NS_WARN_IF(!first.IsSet()) || NS_WARN_IF(!last.IsSet()) ||
 721        NS_WARN_IF(!NodeIsInTraversalRange(mCurNode, mOrder == Order::Pre, first,
 722                                           last)))) {
 723     mCurNode = nullptr;
 724     return NS_ERROR_FAILURE;
 725   }
 726
 727   return NS_OK;
 728 }
 729
 730 /******************************************************
 731  * ContentSubtreeIterator init routines
 732  ******************************************************/
 733
 734 nsresult ContentSubtreeIterator::Init(nsINode* aRoot) {
 735   return NS_ERROR_NOT_IMPLEMENTED;
 736 }
 737
 738 nsresult ContentSubtreeIterator::Init(nsRange* aRange) {
 739   MOZ_ASSERT(aRange);
 740
 741   if (NS_WARN_IF(!aRange->IsPositioned())) {
 742     return NS_ERROR_INVALID_ARG;
 743   }
 744
 745   mRange = aRange;
 746
 747   return InitWithRange();
 748 }
 749
 750 nsresult ContentSubtreeIterator::Init(nsINode* aStartContainer,
 751                                       uint32_t aStartOffset,
 752                                       nsINode* aEndContainer,
 753                                       uint32_t aEndOffset) {
 754   return Init(RawRangeBoundary(aStartContainer, aStartOffset),
 755               RawRangeBoundary(aEndContainer, aEndOffset));
 756 }
 757
 758 nsresult ContentSubtreeIterator::Init(const RawRangeBoundary& aStartBoundary,
 759                                       const RawRangeBoundary& aEndBoundary) {
 760   RefPtr<nsRange> range =
 761       nsRange::Create(aStartBoundary, aEndBoundary, IgnoreErrors());
 762   if (NS_WARN_IF(!range) || NS_WARN_IF(!range->IsPositioned())) {
 763     return NS_ERROR_INVALID_ARG;
 764   }
 765
 766   if (NS_WARN_IF(range->StartRef() != aStartBoundary) ||
 767       NS_WARN_IF(range->EndRef() != aEndBoundary)) {
 768     return NS_ERROR_UNEXPECTED;
 769   }
 770
 771   mRange = std::move(range);
 772
 773   return InitWithRange();
 774 }
 775
 776 void ContentSubtreeIterator::CacheInclusiveAncestorsOfEndContainer() {
 777   mInclusiveAncestorsOfEndContainer.Clear();
 778   nsINode* const endContainer = mRange->GetEndContainer();
 779   nsIContent* endNode =
 780       endContainer->IsContent() ? endContainer->AsContent() : nullptr;
 781   while (endNode) {
 782     mInclusiveAncestorsOfEndContainer.AppendElement(endNode);
 783     endNode = endNode->GetParent();
 784   }
 785 }
 786
 787 nsIContent* ContentSubtreeIterator::DetermineCandidateForFirstContent() const {
 788   nsINode* startContainer = mRange->GetStartContainer();
 789   nsIContent* firstCandidate = nullptr;
 790   // find first node in range
 791   nsINode* node = nullptr;
 792   if (!startContainer->GetChildCount()) {
 793     // no children, start at the node itself
 794     node = startContainer;
 795   } else {
 796     nsIContent* child = mRange->GetChildAtStartOffset();
 797     MOZ_ASSERT(child ==
 798                startContainer->GetChildAt_Deprecated(mRange->StartOffset()));
 799     if (!child) {
 800       // offset after last child
 801       node = startContainer;
 802     } else {
 803       firstCandidate = child;
 804     }
 805   }
 806
 807   if (!firstCandidate) {
 808     // then firstCandidate is next node after node
 809     firstCandidate = ContentIteratorBase::GetNextSibling(node);
 810   }
 811
 812   if (firstCandidate) {
 813     firstCandidate = ContentIteratorBase::GetDeepFirstChild(firstCandidate);
 814   }
 815
 816   return firstCandidate;
 817 }
 818
 819 nsIContent* ContentSubtreeIterator::DetermineFirstContent() const {
 820   nsIContent* firstCandidate = DetermineCandidateForFirstContent();
 821   if (!firstCandidate) {
 822     return nullptr;
 823   }
 824
 825   // confirm that this first possible contained node is indeed contained.  Else
 826   // we have a range that does not fully contain any node.
 827   const Maybe<bool> isNodeContainedInRange =
 828       RangeUtils::IsNodeContainedInRange(*firstCandidate, mRange);
 829   MOZ_ALWAYS_TRUE(isNodeContainedInRange);
 830   if (!isNodeContainedInRange.value()) {
 831     return nullptr;
 832   }
 833
 834   // cool, we have the first node in the range.  Now we walk up its ancestors
 835   // to find the most senior that is still in the range.  That's the real first
 836   // node.
 837   return GetTopAncestorInRange(firstCandidate);
 838 }
 839
 840 nsIContent* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
 841   nsIContent* lastCandidate{nullptr};
 842   nsINode* endContainer = mRange->GetEndContainer();
 843   // now to find the last node
 844   int32_t offset = mRange->EndOffset();
 845   int32_t numChildren = endContainer->GetChildCount();
 846
 847   nsINode* node = nullptr;
 848   if (offset > numChildren) {
 849     // Can happen for text nodes
 850     offset = numChildren;
 851   }
 852   if (!offset || !numChildren) {
 853     node = endContainer;
 854   } else {
 855     lastCandidate = mRange->EndRef().Ref();
 856     MOZ_ASSERT(lastCandidate == endContainer->GetChildAt_Deprecated(--offset));
 857     NS_ASSERTION(lastCandidate,
 858                  "tree traversal trouble in ContentSubtreeIterator::Init");
 859   }
 860
 861   if (!lastCandidate) {
 862     // then lastCandidate is prev node before node
 863     lastCandidate = ContentIteratorBase::GetPrevSibling(node);
 864   }
 865
 866   if (lastCandidate) {
 867     lastCandidate = ContentIteratorBase::GetDeepLastChild(lastCandidate);
 868   }
 869
 870   return lastCandidate;
 871 }
 872
 873 nsresult ContentSubtreeIterator::InitWithRange() {
 874   MOZ_ASSERT(mRange);
 875   MOZ_ASSERT(mRange->IsPositioned());
 876
 877   // get the start node and offset, convert to nsINode
 878   mClosestCommonInclusiveAncestor = mRange->GetClosestCommonInclusiveAncestor();
 879   nsINode* startContainer = mRange->GetStartContainer();
 880   const int32_t startOffset = mRange->StartOffset();
 881   nsINode* endContainer = mRange->GetEndContainer();
 882   const int32_t endOffset = mRange->EndOffset();
 883   MOZ_ASSERT(mClosestCommonInclusiveAncestor && startContainer && endContainer);
 884   // Bug 767169
 885   MOZ_ASSERT(uint32_t(startOffset) <= startContainer->Length() &&
 886              uint32_t(endOffset) <= endContainer->Length());
 887
 888   // short circuit when start node == end node
 889   if (startContainer == endContainer) {
 890     nsINode* child = startContainer->GetFirstChild();
 891
 892     if (!child || startOffset == endOffset) {
 893       // Text node, empty container, or collapsed
 894       SetEmpty();
 895       return NS_OK;
 896     }
 897   }
 898
 899   CacheInclusiveAncestorsOfEndContainer();
 900
 901   mFirst = DetermineFirstContent();
 902   if (!mFirst) {
 903     SetEmpty();
 904     return NS_OK;
 905   }
 906
 907   mLast = DetermineLastContent();
 908   if (!mLast) {
 909     SetEmpty();
 910     return NS_OK;
 911   }
 912
 913   mCurNode = mFirst;
 914
 915   return NS_OK;
 916 }
 917
 918 nsIContent* ContentSubtreeIterator::DetermineLastContent() const {
 919   nsIContent* lastCandidate = DetermineCandidateForLastContent();
 920   if (!lastCandidate) {
 921     return nullptr;
 922   }
 923
 924   // confirm that this last possible contained node is indeed contained.  Else
 925   // we have a range that does not fully contain any node.
 926
 927   const Maybe<bool> isNodeContainedInRange =
 928       RangeUtils::IsNodeContainedInRange(*lastCandidate, mRange);
 929   MOZ_ALWAYS_TRUE(isNodeContainedInRange);
 930   if (!isNodeContainedInRange.value()) {
 931     return nullptr;
 932   }
 933
 934   // cool, we have the last node in the range.  Now we walk up its ancestors to
 935   // find the most senior that is still in the range.  That's the real first
 936   // node.
 937   return GetTopAncestorInRange(lastCandidate);
 938 }
 939
 940 /****************************************************************
 941  * ContentSubtreeIterator overrides of ContentIterator routines
 942  ****************************************************************/
 943
 944 // we can't call PositionAt in a subtree iterator...
 945 void ContentSubtreeIterator::First() { mCurNode = mFirst; }
 946
 947 // we can't call PositionAt in a subtree iterator...
 948 void ContentSubtreeIterator::Last() { mCurNode = mLast; }
 949
 950 void ContentSubtreeIterator::Next() {
 951   if (IsDone()) {
 952     return;
 953   }
 954
 955   if (mCurNode == mLast) {
 956     mCurNode = nullptr;
 957     return;
 958   }
 959
 960   nsINode* nextNode = ContentIteratorBase::GetNextSibling(mCurNode);
 961   NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
 962
 963   int32_t i = mInclusiveAncestorsOfEndContainer.IndexOf(nextNode);
 964   while (i != -1) {
 965     // as long as we are finding ancestors of the endpoint of the range,
 966     // dive down into their children
 967     nextNode = nextNode->GetFirstChild();
 968     NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
 969
 970     // should be impossible to get a null pointer.  If we went all the way
 971     // down the child chain to the bottom without finding an interior node,
 972     // then the previous node should have been the last, which was
 973     // was tested at top of routine.
 974     i = mInclusiveAncestorsOfEndContainer.IndexOf(nextNode);
 975   }
 976
 977   mCurNode = nextNode;
 978 }
 979
 980 void ContentSubtreeIterator::Prev() {
 981   // Prev should be optimized to use the mStartNodes, just as Next
 982   // uses mInclusiveAncestorsOfEndContainer.
 983   if (IsDone()) {
 984     return;
 985   }
 986
 987   if (mCurNode == mFirst) {
 988     mCurNode = nullptr;
 989     return;
 990   }
 991
 992   // If any of these function calls return null, so will all succeeding ones,
 993   // so mCurNode will wind up set to null.
 994   nsINode* prevNode = ContentIteratorBase::GetDeepFirstChild(mCurNode);
 995
 996   prevNode = PrevNode(prevNode);
 997
 998   prevNode = ContentIteratorBase::GetDeepLastChild(prevNode);
 999
1000   mCurNode = GetTopAncestorInRange(prevNode);
1001 }
1002
1003 nsresult ContentSubtreeIterator::PositionAt(nsINode* aCurNode) {
1004   NS_ERROR("Not implemented!");
1005   return NS_ERROR_NOT_IMPLEMENTED;
1006 }
1007
1008 /****************************************************************
1009  * ContentSubtreeIterator helper routines
1010  ****************************************************************/
1011
1012 nsIContent* ContentSubtreeIterator::GetTopAncestorInRange(
1013     nsINode* aNode) const {
1014   if (!aNode || !aNode->GetParentNode()) {
1015     return nullptr;
1016   }
1017
1018   // aNode has a parent, so it must be content.
1019   nsIContent* content = aNode->AsContent();
1020
1021   // sanity check: aNode is itself in the range
1022   Maybe<bool> isNodeContainedInRange =
1023       RangeUtils::IsNodeContainedInRange(*aNode, mRange);
1024   NS_ASSERTION(isNodeContainedInRange && isNodeContainedInRange.value(),
1025                "aNode isn't in mRange, or something else weird happened");
1026   if (!isNodeContainedInRange || !isNodeContainedInRange.value()) {
1027     return nullptr;
1028   }
1029
1030   while (content) {
1031     nsIContent* parent = content->GetParent();
1032     // content always has a parent.  If its parent is the root, however --
1033     // i.e., either it's not content, or it is content but its own parent is
1034     // null -- then we're finished, since we don't go up to the root.
1035     //
1036     // We have to special-case this because CompareNodeToRange treats the root
1037     // node differently -- see bug 765205.
1038     if (!parent || !parent->GetParentNode()) {
1039       return content;
1040     }
1041
1042     isNodeContainedInRange =
1043         RangeUtils::IsNodeContainedInRange(*parent, mRange);
1044     MOZ_ALWAYS_TRUE(isNodeContainedInRange);
1045     if (!isNodeContainedInRange.value()) {
1046       return content;
1047     }
1048
1049     content = parent;
1050   }
1051
1052   MOZ_CRASH("This should only be possible if aNode was null");
1053 }
1054
1055 }  // namespace mozilla