ContentIterator.h (14468B)
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 [[nodiscard]] virtual nsresult Init(nsINode* aRoot); 43 44 /** 45 * If you want to use `const AbstractRange*`, you can use an overload which 46 * takes RawRangeBoundary instances or InitWithoutValidatingPoints(). 47 * If your range is dynamic, i.e., an nsRange, you can use 48 * InitWithoutValidatingPoints() which skips comparing the boundary points. 49 */ 50 [[nodiscard]] virtual nsresult Init(dom::AbstractRange* aRange); 51 [[nodiscard]] virtual nsresult Init(nsINode* aStartContainer, 52 uint32_t aStartOffset, 53 nsINode* aEndContainer, 54 uint32_t aEndOffset); 55 [[nodiscard]] virtual nsresult Init(const RawRangeBoundary& aStart, 56 const RawRangeBoundary& aEnd); 57 [[nodiscard]] virtual nsresult InitWithoutValidatingPoints( 58 const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd); 59 virtual void First(); 60 virtual void Last(); 61 virtual void Next(); 62 virtual void Prev(); 63 64 nsINode* GetCurrentNode() const { return mCurNode; } 65 66 bool IsDone() const { return !mCurNode; } 67 68 [[nodiscard]] virtual nsresult PositionAt(nsINode* aCurNode); 69 70 protected: 71 enum class Order { 72 Pre, /*!< <https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_(NLR)>. 73 */ 74 Post /*!< <https://en.wikipedia.org/wiki/Tree_traversal#Post-order_(LRN)>. 75 */ 76 }; 77 78 explicit ContentIteratorBase(Order aOrder); 79 80 class Initializer; 81 82 /** 83 * Callers must guarantee that: 84 * - Neither aStartContainer nor aEndContainer is nullptr. 85 * - aStartOffset and aEndOffset are valid for its container. 86 * - The start point and the end point are in document order. 87 */ 88 [[nodiscard]] nsresult InitInternal(const RawRangeBoundary& aStart, 89 const RawRangeBoundary& aEnd); 90 91 // Recursively get the deepest first/last child of aRoot. This will return 92 // aRoot itself if it has no children. 93 static nsINode* GetDeepFirstChild(nsINode* aRoot); 94 // If aAllowCrossShadowBoundary is true, it'll continue with the shadow tree 95 // when it reaches to a shadow host. 96 static nsIContent* GetDeepFirstChild( 97 nsIContent* aRoot, 98 dom::AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary); 99 static nsINode* GetDeepLastChild(nsINode* aRoot); 100 // If aAllowCrossShadowBoundary is true, it'll continue with the shadow tree 101 // when it reaches to a shadow host. 102 static nsIContent* GetDeepLastChild( 103 nsIContent* aRoot, 104 dom::AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary); 105 106 struct AncestorInfo { 107 nsIContent* mAncestor = nullptr; 108 // mIsDescendantInShadowTree is used to determine if we should go 109 // dive into the shadow tree or regular light DOM tree if mAncestor 110 // is a shadow host. It should always be false otherwise. 111 bool mIsDescendantInShadowTree = false; 112 }; 113 114 class InclusiveAncestorComparator { 115 public: 116 bool Equals(const AncestorInfo& aA, const nsINode* aB) const { 117 return aA.mAncestor == aB; 118 } 119 }; 120 // Get the next/previous sibling of aNode, or its parent's, or grandparent's, 121 // etc. Returns null if aNode and all its ancestors have no next/previous 122 // sibling. 123 // 124 // If aAllowCrossShadowBoundary is true, it'll continue with the shadow host 125 // when it reaches to a shadow root. 126 static nsIContent* GetNextSibling( 127 nsINode* aNode, 128 dom::AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary = 129 dom::AllowRangeCrossShadowBoundary::No, 130 nsTArray<AncestorInfo>* aInclusiveAncestorsOfEndContainer = nullptr); 131 static nsIContent* GetPrevSibling( 132 nsINode* aNode, 133 dom::AllowRangeCrossShadowBoundary aAllowCrossShadowBoundary = 134 dom::AllowRangeCrossShadowBoundary::No); 135 136 nsINode* NextNode(nsINode* aNode); 137 nsINode* PrevNode(nsINode* aNode); 138 139 void SetEmpty(); 140 141 NodeType mCurNode = nullptr; 142 NodeType mFirst = nullptr; 143 NodeType mLast = nullptr; 144 // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>. 145 NodeType mClosestCommonInclusiveAncestor = nullptr; 146 147 Maybe<nsMutationGuard> mMutationGuard; 148 Maybe<JS::AutoAssertNoGC> mAssertNoGC; 149 150 const Order mOrder; 151 152 template <typename T> 153 friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&, 154 ContentIteratorBase<T>&, const char*, 155 uint32_t); 156 template <typename T> 157 friend void ImplCycleCollectionUnlink(ContentIteratorBase<T>&); 158 }; 159 160 // Each concrete class of ContentIteratorBase<RefPtr<nsINode>> may be owned by 161 // another class which may be owned by JS. Therefore, all of them should be in 162 // the cycle collection. However, we cannot make non-refcountable classes only 163 // with the macros. So, we need to make them cycle collectable without the 164 // macros. 165 template <typename NodeType> 166 void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback, 167 ContentIteratorBase<NodeType>& aField, 168 const char* aName, uint32_t aFlags = 0) { 169 ImplCycleCollectionTraverse(aCallback, aField.mCurNode, aName, aFlags); 170 ImplCycleCollectionTraverse(aCallback, aField.mFirst, aName, aFlags); 171 ImplCycleCollectionTraverse(aCallback, aField.mLast, aName, aFlags); 172 ImplCycleCollectionTraverse(aCallback, aField.mClosestCommonInclusiveAncestor, 173 aName, aFlags); 174 } 175 176 template <typename NodeType> 177 void ImplCycleCollectionUnlink(ContentIteratorBase<NodeType>& aField) { 178 ImplCycleCollectionUnlink(aField.mCurNode); 179 ImplCycleCollectionUnlink(aField.mFirst); 180 ImplCycleCollectionUnlink(aField.mLast); 181 ImplCycleCollectionUnlink(aField.mClosestCommonInclusiveAncestor); 182 } 183 184 using SafeContentIteratorBase = ContentIteratorBase<RefPtr<nsINode>>; 185 using UnsafeContentIteratorBase = ContentIteratorBase<nsINode*>; 186 187 /** 188 * A simple iterator class for traversing the content in "close tag" order. 189 */ 190 class PostContentIterator final : public SafeContentIteratorBase { 191 public: 192 PostContentIterator() : SafeContentIteratorBase(Order::Post) {} 193 PostContentIterator(const PostContentIterator&) = delete; 194 PostContentIterator& operator=(const PostContentIterator&) = delete; 195 virtual ~PostContentIterator() = default; 196 friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&, 197 PostContentIterator&, const char*, 198 uint32_t); 199 friend void ImplCycleCollectionUnlink(PostContentIterator&); 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 UnsafePostContentIterator final 208 : public UnsafeContentIteratorBase { 209 public: 210 UnsafePostContentIterator() : UnsafeContentIteratorBase(Order::Post) {} 211 UnsafePostContentIterator(const UnsafePostContentIterator&) = delete; 212 UnsafePostContentIterator& operator=(const UnsafePostContentIterator&) = 213 delete; 214 virtual ~UnsafePostContentIterator() = default; 215 }; 216 217 /** 218 * A simple iterator class for traversing the content in "start tag" order. 219 */ 220 class PreContentIterator final : public SafeContentIteratorBase { 221 public: 222 PreContentIterator() : ContentIteratorBase(Order::Pre) {} 223 PreContentIterator(const PreContentIterator&) = delete; 224 PreContentIterator& operator=(const PreContentIterator&) = delete; 225 virtual ~PreContentIterator() = default; 226 friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&, 227 PreContentIterator&, const char*, 228 uint32_t); 229 friend void ImplCycleCollectionUnlink(PreContentIterator&); 230 }; 231 232 /** 233 * Different from PostContentIterator, UnsafePostContentIterator does not 234 * grab nodes with strong pointers. Therefore, the user needs to guarantee 235 * that script won't run while this is alive. 236 */ 237 class MOZ_STACK_CLASS UnsafePreContentIterator final 238 : public UnsafeContentIteratorBase { 239 public: 240 UnsafePreContentIterator() : UnsafeContentIteratorBase(Order::Pre) {} 241 UnsafePreContentIterator(const UnsafePostContentIterator&) = delete; 242 UnsafePreContentIterator& operator=(const UnsafePostContentIterator&) = 243 delete; 244 virtual ~UnsafePreContentIterator() = default; 245 }; 246 247 /** 248 * A simple iterator class for traversing the content in "top subtree" order. 249 */ 250 class ContentSubtreeIterator final : public SafeContentIteratorBase { 251 public: 252 ContentSubtreeIterator() : SafeContentIteratorBase(Order::Pre) {} 253 ContentSubtreeIterator(const ContentSubtreeIterator&) = delete; 254 ContentSubtreeIterator& operator=(const ContentSubtreeIterator&) = delete; 255 virtual ~ContentSubtreeIterator() = default; 256 257 /** 258 * Not supported. 259 */ 260 [[nodiscard]] nsresult Init(nsINode* aRoot) override; 261 262 /** 263 * If you need to use const AbstractRange, use an overload which take 264 * RawRangeBoundary instances. 265 */ 266 [[nodiscard]] nsresult Init(dom::AbstractRange* aRange) override; 267 268 /** 269 * Initialize the iterator with aRange that does correct things 270 * when the aRange's start and/or the end containers are 271 * in shadow dom. 272 * 273 * If both start and end containers are in light dom, the iterator 274 * won't do anything special. 275 * 276 * When the start container is in shadow dom, the iterator can 277 * find the correct start node by crossing the shadow 278 * boundary when needed. 279 * 280 * When the end container is in shadow dom, the iterator can find 281 * the correct end node by crossing the shadow boundary when 282 * needed. Also when the next node is an ancestor of 283 * the end node, it can correctly iterate into the 284 * subtree of it by crossing the shadow boundary. 285 * 286 * Examples of what nodes will be returned can be found 287 * at test_content_iterator_subtree_shadow_tree.html. 288 * 289 * FIXME: This doesn't have a overload of this method which takes 290 * `const RawRangeBoundary`s. That allows the callers to make this with 291 * `const AbstractRange*`. So, it and its non-validation version (for 292 * `const nsRange*` should be here. 293 */ 294 [[nodiscard]] nsresult InitWithAllowCrossShadowBoundary( 295 dom::AbstractRange* aRange); 296 297 [[nodiscard]] nsresult Init(nsINode* aStartContainer, uint32_t aStartOffset, 298 nsINode* aEndContainer, 299 uint32_t aEndOffset) override; 300 [[nodiscard]] nsresult Init(const RawRangeBoundary& aStartBoundary, 301 const RawRangeBoundary& aEndBoundary) override; 302 [[nodiscard]] nsresult InitWithoutValidatingPoints( 303 const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) override { 304 // We need to create an nsRange from aStart and aEnd. Therefore, anyway 305 // nsRange will validate them. 306 return Init(aStart, aEnd); 307 } 308 309 void Next() override; 310 void Prev() override; 311 // Must override these because we don't do PositionAt 312 void First() override; 313 // Must override these because we don't do PositionAt 314 void Last() override; 315 316 [[nodiscard]] nsresult PositionAt(nsINode* aCurNode) override; 317 318 friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&, 319 ContentSubtreeIterator&, const char*, 320 uint32_t); 321 friend void ImplCycleCollectionUnlink(ContentSubtreeIterator&); 322 323 private: 324 /** 325 * See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>. 326 */ 327 void CacheInclusiveAncestorsOfEndContainer(); 328 329 /** 330 * @return may be nullptr. 331 */ 332 nsIContent* DetermineCandidateForFirstContent() const; 333 334 /** 335 * @return may be nullptr. 336 */ 337 nsIContent* DetermineCandidateForLastContent() const; 338 339 /** 340 * @return may be nullptr. 341 */ 342 nsIContent* DetermineFirstContent() const; 343 344 /** 345 * @return may be nullptr. 346 */ 347 nsIContent* DetermineLastContent() const; 348 349 /** 350 * Callers must guarantee that mRange isn't nullptr and is positioned. 351 */ 352 [[nodiscard]] nsresult InitWithRange(); 353 354 // Returns the highest inclusive ancestor of aNode that's in the range 355 // (possibly aNode itself). Returns null if aNode is null, or is not itself 356 // in the range. A node is in the range if (node, 0) comes strictly after 357 // the range endpoint, and (node, node.length) comes strictly before it, so 358 // the range's start and end nodes will never be considered "in" it. 359 nsIContent* GetTopAncestorInRange(nsINode* aNode) const; 360 361 bool IterAllowCrossShadowBoundary() const { 362 return mAllowCrossShadowBoundary == dom::AllowRangeCrossShadowBoundary::Yes; 363 } 364 365 RefPtr<dom::AbstractRange> mRange; 366 367 // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>. 368 AutoTArray<AncestorInfo, 8> mInclusiveAncestorsOfEndContainer; 369 370 // Whether this iterator allows to iterate nodes across shadow boundary. 371 dom::AllowRangeCrossShadowBoundary mAllowCrossShadowBoundary = 372 dom::AllowRangeCrossShadowBoundary::No; 373 }; 374 375 } // namespace mozilla 376 377 #endif // #ifndef mozilla_ContentIterator_h