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