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