| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (C) 2012 Google Inc. All rights reserved. | |
| 3 * | |
| 4 * Redistribution and use in source and binary forms, with or without | |
| 5 * modification, are permitted provided that the following conditions are | |
| 6 * met: | |
| 7 * | |
| 8 * * Redistributions of source code must retain the above copyright | |
| 9 * notice, this list of conditions and the following disclaimer. | |
| 10 * * Neither the name of Google Inc. nor the names of its | |
| 11 * contributors may be used to endorse or promote products derived from | |
| 12 * this software without specific prior written permission. | |
| 13 * | |
| 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| 15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| 16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| 17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
| 18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
| 19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
| 20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
| 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
| 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 25 */ | |
| 26 | |
| 27 #ifndef ComposedTreeTraversal_h | |
| 28 #define ComposedTreeTraversal_h | |
| 29 | |
| 30 #include "core/CoreExport.h" | |
| 31 #include "core/dom/Document.h" | |
| 32 #include "core/dom/LayoutTreeBuilderTraversal.h" | |
| 33 #include "core/dom/shadow/InsertionPoint.h" | |
| 34 #include "core/dom/shadow/ShadowRoot.h" | |
| 35 #include "wtf/Allocator.h" | |
| 36 | |
| 37 namespace blink { | |
| 38 | |
| 39 class ContainerNode; | |
| 40 class HTMLSlotElement; | |
| 41 class Node; | |
| 42 | |
| 43 // Composed tree version of |NodeTraversal|. | |
| 44 // | |
| 45 // None of member functions takes a |ShadowRoot| or an active insertion point, | |
| 46 // e.g. roughly speaking <content> and <shadow> in the shadow tree, see | |
| 47 // |InsertionPoint::isActive()| for details of active insertion points, since | |
| 48 // they aren't appeared in the composed tree. |assertPrecondition()| and | |
| 49 // |assertPostCondition()| check this condition. | |
| 50 // | |
| 51 // FIXME: Make some functions inline to optimise the performance. | |
| 52 // https://bugs.webkit.org/show_bug.cgi?id=82702 | |
| 53 class CORE_EXPORT ComposedTreeTraversal { | |
| 54 STATIC_ONLY(ComposedTreeTraversal); | |
| 55 public: | |
| 56 typedef LayoutTreeBuilderTraversal::ParentDetails ParentTraversalDetails; | |
| 57 | |
| 58 static Node* next(const Node&); | |
| 59 static Node* next(const Node&, const Node* stayWithin); | |
| 60 static Node* previous(const Node&); | |
| 61 | |
| 62 static Node* firstChild(const Node&); | |
| 63 static Node* lastChild(const Node&); | |
| 64 static bool hasChildren(const Node&); | |
| 65 | |
| 66 static ContainerNode* parent(const Node&, ParentTraversalDetails* = 0); | |
| 67 static Element* parentElement(const Node&); | |
| 68 | |
| 69 static Node* nextSibling(const Node&); | |
| 70 static Node* previousSibling(const Node&); | |
| 71 | |
| 72 // Returns a child node at |index|. If |index| is greater than or equal to | |
| 73 // the children, this function returns |nullptr|. | |
| 74 static Node* childAt(const Node&, unsigned index); | |
| 75 | |
| 76 // Composed tree version of |NodeTraversal::nextSkippingChildren()|. This | |
| 77 // function is similar to |next()| but skips child nodes of a specified | |
| 78 // node. | |
| 79 static Node* nextSkippingChildren(const Node&); | |
| 80 static Node* nextSkippingChildren(const Node&, const Node* stayWithin); | |
| 81 | |
| 82 // Composed tree version of |NodeTraversal::previousSkippingChildren()| | |
| 83 // similar to |previous()| but skipping child nodes of the specified node. | |
| 84 static Node* previousSkippingChildren(const Node&); | |
| 85 | |
| 86 // Like previous, but visits parents before their children. | |
| 87 static Node* previousPostOrder(const Node&, const Node* stayWithin = nullptr
); | |
| 88 | |
| 89 // Composed tree version of |Node::isDescendantOf(other)|. This function | |
| 90 // returns true if |other| contains |node|, otherwise returns | |
| 91 // false. If |other| is |node|, this function returns false. | |
| 92 static bool isDescendantOf(const Node& /*node*/, const Node& other); | |
| 93 | |
| 94 static bool contains(const ContainerNode& container, const Node& node) | |
| 95 { | |
| 96 assertPrecondition(container); | |
| 97 assertPrecondition(node); | |
| 98 return container == node || isDescendantOf(node, container); | |
| 99 } | |
| 100 | |
| 101 static bool containsIncludingPseudoElement(const ContainerNode&, const Node&
); | |
| 102 | |
| 103 // Returns a common ancestor of |nodeA| and |nodeB| if exists, otherwise | |
| 104 // returns |nullptr|. | |
| 105 static Node* commonAncestor(const Node& nodeA, const Node& nodeB); | |
| 106 | |
| 107 // Composed tree version of |Node::nodeIndex()|. This function returns a | |
| 108 // zero base position number of the specified node in child nodes list, or | |
| 109 // zero if the specified node has no parent. | |
| 110 static unsigned index(const Node&); | |
| 111 | |
| 112 // Composed tree version of |ContainerNode::countChildren()|. This function | |
| 113 // returns the number of the child nodes of the specified node in the | |
| 114 // composed tree. | |
| 115 static unsigned countChildren(const Node&); | |
| 116 | |
| 117 static Node* lastWithin(const Node&); | |
| 118 static Node& lastWithinOrSelf(const Node&); | |
| 119 | |
| 120 private: | |
| 121 enum TraversalDirection { | |
| 122 TraversalDirectionForward, | |
| 123 TraversalDirectionBackward | |
| 124 }; | |
| 125 | |
| 126 static void assertPrecondition(const Node& node) | |
| 127 { | |
| 128 #if ENABLE(ASSERT) | |
| 129 ASSERT(!node.needsDistributionRecalc()); | |
| 130 ASSERT(node.canParticipateInComposedTree()); | |
| 131 #endif | |
| 132 } | |
| 133 | |
| 134 static void assertPostcondition(const Node* node) | |
| 135 { | |
| 136 #if ENABLE(ASSERT) | |
| 137 if (node) | |
| 138 assertPrecondition(*node); | |
| 139 #endif | |
| 140 } | |
| 141 | |
| 142 static Node* resolveDistributionStartingAt(const Node*, TraversalDirection); | |
| 143 static Node* v0ResolveDistributionStartingAt(const Node&, TraversalDirection
); | |
| 144 | |
| 145 static Node* traverseNext(const Node&); | |
| 146 static Node* traverseNext(const Node&, const Node* stayWithin); | |
| 147 static Node* traverseNextSkippingChildren(const Node&, const Node* stayWithi
n); | |
| 148 static Node* traversePrevious(const Node&); | |
| 149 | |
| 150 static Node* traverseFirstChild(const Node&); | |
| 151 static Node* traverseLastChild(const Node&); | |
| 152 static Node* traverseChild(const Node&, TraversalDirection); | |
| 153 | |
| 154 static ContainerNode* traverseParent(const Node&, ParentTraversalDetails* =
0); | |
| 155 // TODO(hayato): Make ParentTraversalDetails be aware of slot elements too. | |
| 156 static ContainerNode* traverseParentForV0(const Node&, ParentTraversalDetai
ls* = 0); | |
| 157 static ContainerNode* traverseParentOrHost(const Node&); | |
| 158 | |
| 159 static Node* traverseNextSibling(const Node&); | |
| 160 static Node* traversePreviousSibling(const Node&); | |
| 161 | |
| 162 static Node* traverseSiblings(const Node&, TraversalDirection); | |
| 163 static Node* traverseSiblingsForV1HostChild(const Node&, TraversalDirection)
; | |
| 164 static Node* traverseSiblingsForV0Distribution(const Node&, TraversalDirecti
on); | |
| 165 | |
| 166 static Node* traverseNextAncestorSibling(const Node&); | |
| 167 static Node* traversePreviousAncestorSibling(const Node&); | |
| 168 }; | |
| 169 | |
| 170 inline ContainerNode* ComposedTreeTraversal::parent(const Node& node, ParentTrav
ersalDetails* details) | |
| 171 { | |
| 172 assertPrecondition(node); | |
| 173 ContainerNode* result = traverseParent(node, details); | |
| 174 assertPostcondition(result); | |
| 175 return result; | |
| 176 } | |
| 177 | |
| 178 inline Element* ComposedTreeTraversal::parentElement(const Node& node) | |
| 179 { | |
| 180 ContainerNode* parent = ComposedTreeTraversal::parent(node); | |
| 181 return parent && parent->isElementNode() ? toElement(parent) : nullptr; | |
| 182 } | |
| 183 | |
| 184 inline Node* ComposedTreeTraversal::nextSibling(const Node& node) | |
| 185 { | |
| 186 assertPrecondition(node); | |
| 187 Node* result = traverseSiblings(node, TraversalDirectionForward); | |
| 188 assertPostcondition(result); | |
| 189 return result; | |
| 190 } | |
| 191 | |
| 192 inline Node* ComposedTreeTraversal::previousSibling(const Node& node) | |
| 193 { | |
| 194 assertPrecondition(node); | |
| 195 Node* result = traverseSiblings(node, TraversalDirectionBackward); | |
| 196 assertPostcondition(result); | |
| 197 return result; | |
| 198 } | |
| 199 | |
| 200 inline Node* ComposedTreeTraversal::next(const Node& node) | |
| 201 { | |
| 202 assertPrecondition(node); | |
| 203 Node* result = traverseNext(node); | |
| 204 assertPostcondition(result); | |
| 205 return result; | |
| 206 } | |
| 207 | |
| 208 inline Node* ComposedTreeTraversal::next(const Node& node, const Node* stayWithi
n) | |
| 209 { | |
| 210 assertPrecondition(node); | |
| 211 Node* result = traverseNext(node, stayWithin); | |
| 212 assertPostcondition(result); | |
| 213 return result; | |
| 214 } | |
| 215 | |
| 216 inline Node* ComposedTreeTraversal::nextSkippingChildren(const Node& node, const
Node* stayWithin) | |
| 217 { | |
| 218 assertPrecondition(node); | |
| 219 Node* result = traverseNextSkippingChildren(node, stayWithin); | |
| 220 assertPostcondition(result); | |
| 221 return result; | |
| 222 } | |
| 223 | |
| 224 inline Node* ComposedTreeTraversal::traverseNext(const Node& node) | |
| 225 { | |
| 226 if (Node* next = traverseFirstChild(node)) | |
| 227 return next; | |
| 228 for (const Node* next = &node; next; next = traverseParent(*next)) { | |
| 229 if (Node* sibling = traverseNextSibling(*next)) | |
| 230 return sibling; | |
| 231 } | |
| 232 return nullptr; | |
| 233 } | |
| 234 | |
| 235 inline Node* ComposedTreeTraversal::traverseNext(const Node& node, const Node* s
tayWithin) | |
| 236 { | |
| 237 if (Node* next = traverseFirstChild(node)) | |
| 238 return next; | |
| 239 return traverseNextSkippingChildren(node, stayWithin); | |
| 240 } | |
| 241 | |
| 242 inline Node* ComposedTreeTraversal::traverseNextSkippingChildren(const Node& nod
e, const Node* stayWithin) | |
| 243 { | |
| 244 for (const Node* next = &node; next; next = traverseParent(*next)) { | |
| 245 if (next == stayWithin) | |
| 246 return nullptr; | |
| 247 if (Node* sibling = traverseNextSibling(*next)) | |
| 248 return sibling; | |
| 249 } | |
| 250 return nullptr; | |
| 251 } | |
| 252 | |
| 253 inline Node* ComposedTreeTraversal::previous(const Node& node) | |
| 254 { | |
| 255 assertPrecondition(node); | |
| 256 Node* result = traversePrevious(node); | |
| 257 assertPostcondition(result); | |
| 258 return result; | |
| 259 } | |
| 260 | |
| 261 inline Node* ComposedTreeTraversal::traversePrevious(const Node& node) | |
| 262 { | |
| 263 if (Node* previous = traversePreviousSibling(node)) { | |
| 264 while (Node* child = traverseLastChild(*previous)) | |
| 265 previous = child; | |
| 266 return previous; | |
| 267 } | |
| 268 return traverseParent(node); | |
| 269 } | |
| 270 | |
| 271 inline Node* ComposedTreeTraversal::firstChild(const Node& node) | |
| 272 { | |
| 273 assertPrecondition(node); | |
| 274 Node* result = traverseChild(node, TraversalDirectionForward); | |
| 275 assertPostcondition(result); | |
| 276 return result; | |
| 277 } | |
| 278 | |
| 279 inline Node* ComposedTreeTraversal::lastChild(const Node& node) | |
| 280 { | |
| 281 assertPrecondition(node); | |
| 282 Node* result = traverseLastChild(node); | |
| 283 assertPostcondition(result); | |
| 284 return result; | |
| 285 } | |
| 286 | |
| 287 inline bool ComposedTreeTraversal::hasChildren(const Node& node) | |
| 288 { | |
| 289 return firstChild(node); | |
| 290 } | |
| 291 | |
| 292 inline Node* ComposedTreeTraversal::traverseNextSibling(const Node& node) | |
| 293 { | |
| 294 return traverseSiblings(node, TraversalDirectionForward); | |
| 295 } | |
| 296 | |
| 297 inline Node* ComposedTreeTraversal::traversePreviousSibling(const Node& node) | |
| 298 { | |
| 299 return traverseSiblings(node, TraversalDirectionBackward); | |
| 300 } | |
| 301 | |
| 302 inline Node* ComposedTreeTraversal::traverseFirstChild(const Node& node) | |
| 303 { | |
| 304 return traverseChild(node, TraversalDirectionForward); | |
| 305 } | |
| 306 | |
| 307 inline Node* ComposedTreeTraversal::traverseLastChild(const Node& node) | |
| 308 { | |
| 309 return traverseChild(node, TraversalDirectionBackward); | |
| 310 } | |
| 311 | |
| 312 } // namespace blink | |
| 313 | |
| 314 #endif | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1675163002:
Rename ComposedTree to FlatTree (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master