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   // If aAllowCrossShadowBoundary is true, it'll continue with the shadow tree
  86   // when it reaches to a shadow host.
  87   static nsIContent* GetDeepFirstChild(nsIContent* aRoot,
  88                                        bool aAllowCrossShadowBoundary);
  89   static nsINode* GetDeepLastChild(nsINode* aRoot);
  90   // If aAllowCrossShadowBoundary is true, it'll continue with the shadow tree
  91   // when it reaches to a shadow host.
  92   static nsIContent* GetDeepLastChild(nsIContent* aRoot,
  93                                       bool aAllowCrossShadowBoundary);
  94
  95   // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
  96   // etc.  Returns null if aNode and all its ancestors have no next/previous
  97   // sibling.
  98   //
  99   // If aAllowCrossShadowBoundary is true, it'll continue with the shadow host
 100   // when it reaches to a shadow root.
 101   static nsIContent* GetNextSibling(nsINode* aNode,
 102                                     bool aAllowCrossShadowBoundary = false);
 103   static nsIContent* GetPrevSibling(nsINode* aNode,
 104                                     bool aAllowCrossShadowBoundary = false);
 105
 106   nsINode* NextNode(nsINode* aNode);
 107   nsINode* PrevNode(nsINode* aNode);
 108
 109   void SetEmpty();
 110
 111   NodeType mCurNode;
 112   NodeType mFirst;
 113   NodeType mLast;
 114   // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
 115   NodeType mClosestCommonInclusiveAncestor;
 116
 117   Maybe<nsMutationGuard> mMutationGuard;
 118   Maybe<JS::AutoAssertNoGC> mAssertNoGC;
 119
 120   const Order mOrder;
 121
 122   template <typename T>
 123   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 124                                           ContentIteratorBase<T>&, const char*,
 125                                           uint32_t);
 126   template <typename T>
 127   friend void ImplCycleCollectionUnlink(ContentIteratorBase<T>&);
 128 };
 129
 130 // Each concrete class of ContentIteratorBase<RefPtr<nsINode>> may be owned by
 131 // another class which may be owned by JS.  Therefore, all of them should be in
 132 // the cycle collection.  However, we cannot make non-refcountable classes only
 133 // with the macros.  So, we need to make them cycle collectable without the
 134 // macros.
 135 template <typename NodeType>
 136 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
 137                                  ContentIteratorBase<NodeType>& aField,
 138                                  const char* aName, uint32_t aFlags = 0) {
 139   ImplCycleCollectionTraverse(aCallback, aField.mCurNode, aName, aFlags);
 140   ImplCycleCollectionTraverse(aCallback, aField.mFirst, aName, aFlags);
 141   ImplCycleCollectionTraverse(aCallback, aField.mLast, aName, aFlags);
 142   ImplCycleCollectionTraverse(aCallback, aField.mClosestCommonInclusiveAncestor,
 143                               aName, aFlags);
 144 }
 145
 146 template <typename NodeType>
 147 void ImplCycleCollectionUnlink(ContentIteratorBase<NodeType>& aField) {
 148   ImplCycleCollectionUnlink(aField.mCurNode);
 149   ImplCycleCollectionUnlink(aField.mFirst);
 150   ImplCycleCollectionUnlink(aField.mLast);
 151   ImplCycleCollectionUnlink(aField.mClosestCommonInclusiveAncestor);
 152 }
 153
 154 using SafeContentIteratorBase = ContentIteratorBase<RefPtr<nsINode>>;
 155 using UnsafeContentIteratorBase = ContentIteratorBase<nsINode*>;
 156
 157 /**
 158  * A simple iterator class for traversing the content in "close tag" order.
 159  */
 160 class PostContentIterator final : public SafeContentIteratorBase {
 161  public:
 162   PostContentIterator() : SafeContentIteratorBase(Order::Post) {}
 163   PostContentIterator(const PostContentIterator&) = delete;
 164   PostContentIterator& operator=(const PostContentIterator&) = delete;
 165   virtual ~PostContentIterator() = default;
 166   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 167                                           PostContentIterator&, const char*,
 168                                           uint32_t);
 169   friend void ImplCycleCollectionUnlink(PostContentIterator&);
 170 };
 171
 172 /**
 173  * Different from PostContentIterator, UnsafePostContentIterator does not
 174  * grab nodes with strong pointers.  Therefore, the user needs to guarantee
 175  * that script won't run while this is alive.
 176  */
 177 class MOZ_STACK_CLASS UnsafePostContentIterator final
 178     : public UnsafeContentIteratorBase {
 179  public:
 180   UnsafePostContentIterator() : UnsafeContentIteratorBase(Order::Post) {}
 181   UnsafePostContentIterator(const UnsafePostContentIterator&) = delete;
 182   UnsafePostContentIterator& operator=(const UnsafePostContentIterator&) =
 183       delete;
 184   virtual ~UnsafePostContentIterator() = default;
 185 };
 186
 187 /**
 188  * A simple iterator class for traversing the content in "start tag" order.
 189  */
 190 class PreContentIterator final : public SafeContentIteratorBase {
 191  public:
 192   PreContentIterator() : ContentIteratorBase(Order::Pre) {}
 193   PreContentIterator(const PreContentIterator&) = delete;
 194   PreContentIterator& operator=(const PreContentIterator&) = delete;
 195   virtual ~PreContentIterator() = default;
 196   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 197                                           PreContentIterator&, const char*,
 198                                           uint32_t);
 199   friend void ImplCycleCollectionUnlink(PreContentIterator&);
 200 };
 201
 202 /**
 203  * Different from PostContentIterator, UnsafePostContentIterator does not
 204  * grab nodes with strong pointers.  Therefore, the user needs to guarantee
 205  * that script won't run while this is alive.
 206  */
 207 class MOZ_STACK_CLASS UnsafePreContentIterator final
 208     : public UnsafeContentIteratorBase {
 209  public:
 210   UnsafePreContentIterator() : UnsafeContentIteratorBase(Order::Pre) {}
 211   UnsafePreContentIterator(const UnsafePostContentIterator&) = delete;
 212   UnsafePreContentIterator& operator=(const UnsafePostContentIterator&) =
 213       delete;
 214   virtual ~UnsafePreContentIterator() = default;
 215 };
 216
 217 /**
 218  *  A simple iterator class for traversing the content in "top subtree" order.
 219  */
 220 class ContentSubtreeIterator final : public SafeContentIteratorBase {
 221  public:
 222   ContentSubtreeIterator() : SafeContentIteratorBase(Order::Pre) {}
 223   ContentSubtreeIterator(const ContentSubtreeIterator&) = delete;
 224   ContentSubtreeIterator& operator=(const ContentSubtreeIterator&) = delete;
 225   virtual ~ContentSubtreeIterator() = default;
 226
 227   /**
 228    * Not supported.
 229    */
 230   virtual nsresult Init(nsINode* aRoot) override;
 231
 232   virtual nsresult Init(dom::AbstractRange* aRange) override;
 233
 234   /**
 235    * Initialize the iterator with aRange that does correct things
 236    * when the aRange's start and/or the end containers are
 237    * in shadow dom.
 238    *
 239    * If both start and end containers are in light dom, the iterator
 240    * won't do anything special.
 241    *
 242    * When the start container is in shadow dom, the iterator can
 243    * find the correct start node by crossing the shadow
 244    * boundary when needed.
 245    *
 246    * When the end container is in shadow dom, the iterator can find
 247    * the correct end node by crossing the shadow boundary when
 248    * needed. Also when the next node is an ancestor of
 249    * the end node, it can correctly iterate into the
 250    * subtree of it by crossing the shadow boundary.
 251    *
 252    * Examples of what nodes will be returned can be found
 253    * at test_content_iterator_subtree_shadow_tree.html.
 254    */
 255   nsresult InitWithAllowCrossShadowBoundary(dom::AbstractRange* aRange);
 256   virtual nsresult Init(nsINode* aStartContainer, uint32_t aStartOffset,
 257                         nsINode* aEndContainer, uint32_t aEndOffset) override;
 258   virtual nsresult Init(const RawRangeBoundary& aStartBoundary,
 259                         const RawRangeBoundary& aEndBoundary) override;
 260
 261   void Next() override;
 262   void Prev() override;
 263   // Must override these because we don't do PositionAt
 264   void First() override;
 265   // Must override these because we don't do PositionAt
 266   void Last() override;
 267
 268   nsresult PositionAt(nsINode* aCurNode) override;
 269
 270   friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
 271                                           ContentSubtreeIterator&, const char*,
 272                                           uint32_t);
 273   friend void ImplCycleCollectionUnlink(ContentSubtreeIterator&);
 274
 275  private:
 276   /**
 277    * See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
 278    */
 279   void CacheInclusiveAncestorsOfEndContainer();
 280
 281   /**
 282    * @return may be nullptr.
 283    */
 284   nsIContent* DetermineCandidateForFirstContent() const;
 285
 286   /**
 287    * @return may be nullptr.
 288    */
 289   nsIContent* DetermineCandidateForLastContent() const;
 290
 291   /**
 292    * @return may be nullptr.
 293    */
 294   nsIContent* DetermineFirstContent() const;
 295
 296   /**
 297    * @return may be nullptr.
 298    */
 299   nsIContent* DetermineLastContent() const;
 300
 301   /**
 302    * Callers must guarantee that mRange isn't nullptr and is positioned.
 303    */
 304   nsresult InitWithRange();
 305
 306   // Returns the highest inclusive ancestor of aNode that's in the range
 307   // (possibly aNode itself).  Returns null if aNode is null, or is not itself
 308   // in the range.  A node is in the range if (node, 0) comes strictly after
 309   // the range endpoint, and (node, node.length) comes strictly before it, so
 310   // the range's start and end nodes will never be considered "in" it.
 311   nsIContent* GetTopAncestorInRange(nsINode* aNode) const;
 312
 313   bool IterAllowCrossShadowBoundary() const {
 314     return mAllowCrossShadowBoundary == dom::AllowRangeCrossShadowBoundary::Yes;
 315   }
 316
 317   RefPtr<dom::AbstractRange> mRange;
 318
 319   // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
 320   AutoTArray<nsIContent*, 8> mInclusiveAncestorsOfEndContainer;
 321
 322   // Whether this iterator allows to iterate nodes across shadow boundary.
 323   dom::AllowRangeCrossShadowBoundary mAllowCrossShadowBoundary =
 324       dom::AllowRangeCrossShadowBoundary::No;
 325 };
 326
 327 }  // namespace mozilla
 328
 329 #endif  // #ifndef mozilla_ContentIterator_h