dom/base/ContentIterator.h

   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 #ifndef mozilla_ContentIterator_h
   8 #define mozilla_ContentIterator_h
   9
  10 #include "js/GCAPI.h"
  11 #include "mozilla/Maybe.h"
  12 #include "mozilla/RangeBoundary.h"
  13 #include "mozilla/RefPtr.h"
  14 #include "nsCycleCollectionParticipant.h"
  15 #include "nsINode.h"
  16 #include "nsRange.h"
  17 #include "nsTArray.h"
  18
  19 class nsIContent;
  20
  21 namespace mozilla {
  22
  23 /**
  24  * ContentIteratorBase is a base class of PostContentIterator,
  25  * PreContentIterator and ContentSubtreeIterator.  Making each concrete
  26  * classes "final", compiler can avoid virtual calls if they are treated
  27  * by the users directly.
  28  */
  29 template <typename NodeType>
  30 class ContentIteratorBase {
  31  public:
  32   ContentIteratorBase() = delete;
  33   ContentIteratorBase(const ContentIteratorBase&) = delete;
  34   ContentIteratorBase& operator=(const ContentIteratorBase&) = delete;
  35   virtual ~ContentIteratorBase();
  36
  37   /**
  38    * Allows to iterate over the inclusive descendants
  39    * (https://dom.spec.whatwg.org/#concept-tree-inclusive-descendant) of
  40    * aRoot.
  41    */
  42   virtual nsresult Init(nsINode* aRoot);
  43
  44   virtual nsresult Init(dom::AbstractRange* aRange);
  45   virtual nsresult Init(nsINode* aStartContainer, uint32_t aStartOffset,
  46                         nsINode* aEndContainer, uint32_t aEndOffset);
  47   virtual nsresult Init(const RawRangeBoundary& aStart,
  48                         const RawRangeBoundary& aEnd);
  49
  50   virtual void First();
  51   virtual void Last();
  52   virtual void Next();
  53   virtual void Prev();
  54
  55   nsINode* GetCurrentNode() const { return mCurNode; }
  56
  57   bool IsDone() const { return !mCurNode; }
  58
  59   virtual nsresult PositionAt(nsINode* aCurNode);
  60
  61  protected:
  62   enum class Order {
  63     Pre, /*!< <https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_(NLR)>.
  64           */
  65     Post /*!< <https://en.wikipedia.org/wiki/Tree_traversal#Post-order_(LRN)>.
  66           */
  67   };
  68
  69   explicit ContentIteratorBase(Order aOrder);
  70
  71   class Initializer;
  72
  73   /**
  74    * Callers must guarantee that:
  75    * - Neither aStartContainer nor aEndContainer is nullptr.
  76    * - aStartOffset and aEndOffset are valid for its container.
  77    * - The start point and the end point are in document order.
  78    */
  79   nsresult InitInternal(const RawRangeBoundary& aStart,
  80                         const RawRangeBoundary& aEnd);
  81
  82   // Recursively get the deepest first/last child of aRoot.  This will return
  83   // aRoot itself if it has no children.
  84   static nsINode* GetDeepFirstChild(nsINode* aRoot);
  85   static nsIContent* GetDeepFirstChild(nsIContent* aRoot);
  86   static nsINode* GetDeepLastChild(nsINode* aRoot);
  87   static nsIContent* GetDeepLastChild(nsIContent* aRoot);
  88
  89   // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
  90   // etc.  Returns null if aNode and all its ancestors have no next/previous
  91   // sibling.
  92   static nsIContent* GetNextSibling(nsINode* aNode);
  93   static nsIContent* GetPrevSibling(nsINode* aNode);
  94
  95   nsINode* NextNode(nsINode* aNode);
  96   nsINode* PrevNode(nsINode* aNode);
  97
  98   void SetEmpty();
  99
 100   NodeType mCurNode;
 101   NodeType mFirst;
 102   NodeType mLast;
 103   // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
 104   NodeType mClosestCommonInclusiveAncestor;
 105
 106   Maybe<nsMutationGuard> mMutationGuard;
 107   Maybe<JS::AutoAssertNoGC> mAssertNoGC;
 108
 109   const Order mOrder;
 110
 111   template <typename T>
 112   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 113                                           ContentIteratorBase<T>&, const char*,
 114                                           uint32_t);
 115   template <typename T>
 116   friend void ImplCycleCollectionUnlink(ContentIteratorBase<T>&);
 117 };
 118
 119 // Each concrete class of ContentIteratorBase<RefPtr<nsINode>> may be owned by
 120 // another class which may be owned by JS.  Therefore, all of them should be in
 121 // the cycle collection.  However, we cannot make non-refcountable classes only
 122 // with the macros.  So, we need to make them cycle collectable without the
 123 // macros.
 124 template <typename NodeType>
 125 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
 126                                  ContentIteratorBase<NodeType>& aField,
 127                                  const char* aName, uint32_t aFlags = 0) {
 128   ImplCycleCollectionTraverse(aCallback, aField.mCurNode, aName, aFlags);
 129   ImplCycleCollectionTraverse(aCallback, aField.mFirst, aName, aFlags);
 130   ImplCycleCollectionTraverse(aCallback, aField.mLast, aName, aFlags);
 131   ImplCycleCollectionTraverse(aCallback, aField.mClosestCommonInclusiveAncestor,
 132                               aName, aFlags);
 133 }
 134
 135 template <typename NodeType>
 136 void ImplCycleCollectionUnlink(ContentIteratorBase<NodeType>& aField) {
 137   ImplCycleCollectionUnlink(aField.mCurNode);
 138   ImplCycleCollectionUnlink(aField.mFirst);
 139   ImplCycleCollectionUnlink(aField.mLast);
 140   ImplCycleCollectionUnlink(aField.mClosestCommonInclusiveAncestor);
 141 }
 142
 143 using SafeContentIteratorBase = ContentIteratorBase<RefPtr<nsINode>>;
 144 using UnsafeContentIteratorBase = ContentIteratorBase<nsINode*>;
 145
 146 /**
 147  * A simple iterator class for traversing the content in "close tag" order.
 148  */
 149 class PostContentIterator final : public SafeContentIteratorBase {
 150  public:
 151   PostContentIterator() : SafeContentIteratorBase(Order::Post) {}
 152   PostContentIterator(const PostContentIterator&) = delete;
 153   PostContentIterator& operator=(const PostContentIterator&) = delete;
 154   virtual ~PostContentIterator() = default;
 155   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 156                                           PostContentIterator&, const char*,
 157                                           uint32_t);
 158   friend void ImplCycleCollectionUnlink(PostContentIterator&);
 159 };
 160
 161 /**
 162  * Different from PostContentIterator, UnsafePostContentIterator does not
 163  * grab nodes with strong pointers.  Therefore, the user needs to guarantee
 164  * that script won't run while this is alive.
 165  */
 166 class MOZ_STACK_CLASS UnsafePostContentIterator final
 167     : public UnsafeContentIteratorBase {
 168  public:
 169   UnsafePostContentIterator() : UnsafeContentIteratorBase(Order::Post) {}
 170   UnsafePostContentIterator(const UnsafePostContentIterator&) = delete;
 171   UnsafePostContentIterator& operator=(const UnsafePostContentIterator&) =
 172       delete;
 173   virtual ~UnsafePostContentIterator() = default;
 174 };
 175
 176 /**
 177  * A simple iterator class for traversing the content in "start tag" order.
 178  */
 179 class PreContentIterator final : public SafeContentIteratorBase {
 180  public:
 181   PreContentIterator() : ContentIteratorBase(Order::Pre) {}
 182   PreContentIterator(const PreContentIterator&) = delete;
 183   PreContentIterator& operator=(const PreContentIterator&) = delete;
 184   virtual ~PreContentIterator() = default;
 185   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 186                                           PreContentIterator&, const char*,
 187                                           uint32_t);
 188   friend void ImplCycleCollectionUnlink(PreContentIterator&);
 189 };
 190
 191 /**
 192  * Different from PostContentIterator, UnsafePostContentIterator does not
 193  * grab nodes with strong pointers.  Therefore, the user needs to guarantee
 194  * that script won't run while this is alive.
 195  */
 196 class MOZ_STACK_CLASS UnsafePreContentIterator final
 197     : public UnsafeContentIteratorBase {
 198  public:
 199   UnsafePreContentIterator() : UnsafeContentIteratorBase(Order::Pre) {}
 200   UnsafePreContentIterator(const UnsafePostContentIterator&) = delete;
 201   UnsafePreContentIterator& operator=(const UnsafePostContentIterator&) =
 202       delete;
 203   virtual ~UnsafePreContentIterator() = default;
 204 };
 205
 206 /**
 207  *  A simple iterator class for traversing the content in "top subtree" order.
 208  */
 209 class ContentSubtreeIterator final : public SafeContentIteratorBase {
 210  public:
 211   ContentSubtreeIterator() : SafeContentIteratorBase(Order::Pre) {}
 212   ContentSubtreeIterator(const ContentSubtreeIterator&) = delete;
 213   ContentSubtreeIterator& operator=(const ContentSubtreeIterator&) = delete;
 214   virtual ~ContentSubtreeIterator() = default;
 215
 216   /**
 217    * Not supported.
 218    */
 219   virtual nsresult Init(nsINode* aRoot) override;
 220
 221   virtual nsresult Init(dom::AbstractRange* aRange) override;
 222   virtual nsresult Init(nsINode* aStartContainer, uint32_t aStartOffset,
 223                         nsINode* aEndContainer, uint32_t aEndOffset) override;
 224   virtual nsresult Init(const RawRangeBoundary& aStartBoundary,
 225                         const RawRangeBoundary& aEndBoundary) override;
 226
 227   void Next() override;
 228   void Prev() override;
 229   // Must override these because we don't do PositionAt
 230   void First() override;
 231   // Must override these because we don't do PositionAt
 232   void Last() override;
 233
 234   nsresult PositionAt(nsINode* aCurNode) override;
 235
 236   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 237                                           ContentSubtreeIterator&, const char*,
 238                                           uint32_t);
 239   friend void ImplCycleCollectionUnlink(ContentSubtreeIterator&);
 240
 241  private:
 242   /**
 243    * See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
 244    */
 245   void CacheInclusiveAncestorsOfEndContainer();
 246
 247   /**
 248    * @return may be nullptr.
 249    */
 250   nsIContent* DetermineCandidateForFirstContent() const;
 251
 252   /**
 253    * @return may be nullptr.
 254    */
 255   nsIContent* DetermineCandidateForLastContent() const;
 256
 257   /**
 258    * @return may be nullptr.
 259    */
 260   nsIContent* DetermineFirstContent() const;
 261
 262   /**
 263    * @return may be nullptr.
 264    */
 265   nsIContent* DetermineLastContent() const;
 266
 267   /**
 268    * Callers must guarantee that mRange isn't nullptr and is positioned.
 269    */
 270   nsresult InitWithRange();
 271
 272   // Returns the highest inclusive ancestor of aNode that's in the range
 273   // (possibly aNode itself).  Returns null if aNode is null, or is not itself
 274   // in the range.  A node is in the range if (node, 0) comes strictly after
 275   // the range endpoint, and (node, node.length) comes strictly before it, so
 276   // the range's start and end nodes will never be considered "in" it.
 277   nsIContent* GetTopAncestorInRange(nsINode* aNode) const;
 278
 279   RefPtr<dom::AbstractRange> mRange;
 280
 281   // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
 282   AutoTArray<nsIContent*, 8> mInclusiveAncestorsOfEndContainer;
 283 };
 284
 285 }  // namespace mozilla
 286
 287 #endif  // #ifndef mozilla_ContentIterator_h