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