1 // Copyright 2017 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef THIRD_PARTY_BLINK_RENDERER_CORE_PAINT_NG_NG_PAINT_FRAGMENT_TRAVERSAL_H_ 6 #define THIRD_PARTY_BLINK_RENDERER_CORE_PAINT_NG_NG_PAINT_FRAGMENT_TRAVERSAL_H_ 7 8 #include "third_party/blink/renderer/core/core_export.h" 9 #include "third_party/blink/renderer/core/layout/geometry/physical_offset.h" 10 #include "third_party/blink/renderer/platform/wtf/vector.h" 11 12 namespace blink { 13 14 class NGPaintFragment; 15 16 // Utility class for traversing the paint fragment tree. 17 // 18 // This class has two groups of functions; one is a traversing cursor, by 19 // instantiating and using instance functions. The other is a set of static 20 // functions that are similar to DOM traversal functions. 21 class CORE_EXPORT NGPaintFragmentTraversal { 22 STACK_ALLOCATED(); 23 24 public: 25 NGPaintFragmentTraversal(const NGPaintFragmentTraversal& other); 26 NGPaintFragmentTraversal(NGPaintFragmentTraversal&& other); 27 NGPaintFragmentTraversal(); 28 NGPaintFragmentTraversal& operator=(const NGPaintFragmentTraversal& other); 29 30 // Create an instance to traverse descendants of |root|. 31 explicit NGPaintFragmentTraversal(const NGPaintFragment& root); 32 33 // Create an instance to traverse descendants of |root|, starting at |start|. 34 // Same as constructing with |root| and then |MoveTo()|. 35 NGPaintFragmentTraversal(const NGPaintFragment& root, 36 const NGPaintFragment& start); 37 IsAtEnd()38 bool IsAtEnd() const { return !current_; } 39 explicit operator bool() const { return !IsAtEnd(); } 40 get()41 const NGPaintFragment* get() const { 42 DCHECK(current_); 43 return current_; 44 } 45 const NGPaintFragment& operator*() const { return *get(); } 46 const NGPaintFragment* operator->() const { return get(); } 47 48 // Move to the specified fragment. The fragment must be a descendant of 49 // |root|. This function is O(n) where |n| is the number of senior siblings 50 // before |fragment|. 51 void MoveTo(const NGPaintFragment& fragment); 52 53 // Move to the next node using the pre-order depth-first-search. 54 // Note: When |IsAtEnd()| is true, this function does nothing. 55 void MoveToNext(); 56 57 // Move to the next sibling, or next ancestor node using the pre-order 58 // depth-first-search, skipping children of the current node. 59 void MoveToNextSiblingOrAncestor(); 60 61 // Move to the parent of current fragment. When |current_| is a child of 62 // |root_|, this function makes |IsAtEnd()| to true. 63 // Note: When |IsAtEnd()| is true, this function does nothing. 64 void MoveToParent(); 65 66 // Move to the previous node using the pre-order depth-first-search. When 67 // |current_| is the first child of |root_|, this function makes |IsAtEnd()| 68 // to true. 69 // Note: When |IsAtEnd()| is true, this function does nothing. 70 void MoveToPrevious(); 71 72 // Returns the previous/next inline leaf fragment (text or atomic inline) of 73 // the passed fragment, which itself must be inline. 74 void MoveToPreviousInlineLeaf(); 75 void MoveToNextInlineLeaf(); 76 77 // Variants of the above two skipping line break fragments. 78 void MoveToPreviousInlineLeafIgnoringLineBreak(); 79 void MoveToNextInlineLeafIgnoringLineBreak(); 80 81 // 82 // Following functions are static, similar to DOM traversal utilities. 83 // 84 // Because fragments have children as a vector, not a two-way list, static 85 // functions are not as cheap as their DOM versions. When traversing more than 86 // once, instace functions are recommended. 87 88 class AncestorRange final { 89 STACK_ALLOCATED(); 90 91 public: 92 class Iterator final 93 : public std::iterator<std::forward_iterator_tag, NGPaintFragment*> { 94 STACK_ALLOCATED(); 95 96 public: Iterator(NGPaintFragment * current)97 explicit Iterator(NGPaintFragment* current) : current_(current) {} 98 99 NGPaintFragment* operator*() const { return operator->(); } 100 NGPaintFragment* operator->() const; 101 102 void operator++(); 103 104 bool operator==(const Iterator& other) const { 105 return current_ == other.current_; 106 } 107 bool operator!=(const Iterator& other) const { 108 return !operator==(other); 109 } 110 111 private: 112 NGPaintFragment* current_; 113 }; 114 AncestorRange(const NGPaintFragment & start)115 explicit AncestorRange(const NGPaintFragment& start) : start_(&start) {} 116 begin()117 Iterator begin() const { 118 return Iterator(const_cast<NGPaintFragment*>(start_)); 119 } end()120 Iterator end() const { return Iterator(nullptr); } 121 122 private: 123 const NGPaintFragment* const start_; 124 }; 125 126 // Returns inclusive ancestors. 127 static AncestorRange InclusiveAncestorsOf(const NGPaintFragment&); 128 129 class CORE_EXPORT InlineDescendantsRange final { 130 STACK_ALLOCATED(); 131 132 public: 133 class CORE_EXPORT Iterator final 134 : public std::iterator<std::forward_iterator_tag, NGPaintFragment*> { 135 STACK_ALLOCATED(); 136 137 public: 138 explicit Iterator(const NGPaintFragment& container); 139 Iterator() = default; 140 141 NGPaintFragment* operator*() const { return operator->(); } 142 NGPaintFragment* operator->() const; 143 144 void operator++(); 145 146 bool operator==(const Iterator& other) const { 147 return current_ == other.current_; 148 } 149 bool operator!=(const Iterator& other) const { 150 return !operator==(other); 151 } 152 153 private: 154 NGPaintFragment* Next(const NGPaintFragment& fragment) const; 155 static bool IsInlineFragment(const NGPaintFragment& fragment); 156 static bool ShouldTraverse(const NGPaintFragment& fragment); 157 158 const NGPaintFragment* container_ = nullptr; 159 NGPaintFragment* current_ = nullptr; 160 }; 161 InlineDescendantsRange(const NGPaintFragment & container)162 explicit InlineDescendantsRange(const NGPaintFragment& container) 163 : container_(&container) {} 164 begin()165 Iterator begin() const { return Iterator(*container_); } end()166 Iterator end() const { return Iterator(); } 167 168 private: 169 const NGPaintFragment* const container_; 170 }; 171 172 // Returns inline descendants of |container| in preorder. 173 static InlineDescendantsRange InlineDescendantsOf( 174 const NGPaintFragment& container); 175 176 private: 177 void EnsureIndex(); 178 bool IsInlineLeaf() const; 179 bool IsLineBreak() const; 180 void MoveToFirstChild(); 181 void MoveToLastChild(); 182 void Reset(); 183 184 // |current_| holds a |NGPaintFragment| specified by |index|th child of 185 // |parent| of the last element of |stack_|. 186 const NGPaintFragment* current_ = nullptr; 187 188 // The root of subtree where traversing is taken place. |root_| is excluded 189 // from traversal. |current_| can't |root_|. 190 const NGPaintFragment* root_ = nullptr; 191 192 // Keep a list of siblings for MoveToPrevious(). 193 // TODO(kojii): We could keep a stack of this to avoid repetitive 194 // constructions of the list when we move up/down levels. Also can consider 195 // sharing with NGPaintFragmentTraversalContext. 196 unsigned current_index_ = 0; 197 Vector<NGPaintFragment*, 16> siblings_; 198 }; 199 200 } // namespace blink 201 202 #endif // THIRD_PARTY_BLINK_RENDERER_CORE_PAINT_NG_NG_PAINT_FRAGMENT_TRAVERSAL_H_ 203