| 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 #include "core/dom/shadow/ComposedTreeTraversal.h" | |
| 28 | |
| 29 #include "core/dom/Element.h" | |
| 30 #include "core/dom/shadow/ElementShadow.h" | |
| 31 #include "core/html/HTMLShadowElement.h" | |
| 32 #include "core/html/HTMLSlotElement.h" | |
| 33 | |
| 34 namespace blink { | |
| 35 | |
| 36 static inline ElementShadow* shadowFor(const Node& node) | |
| 37 { | |
| 38 return node.isElementNode() ? toElement(node).shadow() : nullptr; | |
| 39 } | |
| 40 | |
| 41 static inline bool canBeDistributedToInsertionPoint(const Node& node) | |
| 42 { | |
| 43 return node.isInV0ShadowTree() || node.isChildOfV0ShadowHost(); | |
| 44 } | |
| 45 | |
| 46 Node* ComposedTreeTraversal::traverseChild(const Node& node, TraversalDirection
direction) | |
| 47 { | |
| 48 ElementShadow* shadow = shadowFor(node); | |
| 49 if (shadow) { | |
| 50 ShadowRoot& shadowRoot = shadow->youngestShadowRoot(); | |
| 51 return resolveDistributionStartingAt(direction == TraversalDirectionForw
ard ? shadowRoot.firstChild() : shadowRoot.lastChild(), direction); | |
| 52 } | |
| 53 return resolveDistributionStartingAt(direction == TraversalDirectionForward
? node.firstChild() : node.lastChild(), direction); | |
| 54 } | |
| 55 | |
| 56 Node* ComposedTreeTraversal::resolveDistributionStartingAt(const Node* node, Tra
versalDirection direction) | |
| 57 { | |
| 58 if (!node) | |
| 59 return nullptr; | |
| 60 for (const Node* sibling = node; sibling; sibling = (direction == TraversalD
irectionForward ? sibling->nextSibling() : sibling->previousSibling())) { | |
| 61 if (isHTMLSlotElement(*sibling)) { | |
| 62 const HTMLSlotElement& slot = toHTMLSlotElement(*sibling); | |
| 63 if (Node* found = (direction == TraversalDirectionForward ? slot.fir
stDistributedNode() : slot.lastDistributedNode())) | |
| 64 return found; | |
| 65 continue; | |
| 66 } | |
| 67 if (node->isInV0ShadowTree()) | |
| 68 return v0ResolveDistributionStartingAt(*sibling, direction); | |
| 69 return const_cast<Node*>(sibling); | |
| 70 } | |
| 71 return nullptr; | |
| 72 } | |
| 73 | |
| 74 Node* ComposedTreeTraversal::v0ResolveDistributionStartingAt(const Node& node, T
raversalDirection direction) | |
| 75 { | |
| 76 ASSERT(!isHTMLSlotElement(node)); | |
| 77 for (const Node* sibling = &node; sibling; sibling = (direction == Traversal
DirectionForward ? sibling->nextSibling() : sibling->previousSibling())) { | |
| 78 if (!isActiveInsertionPoint(*sibling)) | |
| 79 return const_cast<Node*>(sibling); | |
| 80 const InsertionPoint& insertionPoint = toInsertionPoint(*sibling); | |
| 81 if (Node* found = (direction == TraversalDirectionForward ? insertionPoi
nt.firstDistributedNode() : insertionPoint.lastDistributedNode())) | |
| 82 return found; | |
| 83 ASSERT(isHTMLShadowElement(insertionPoint) || (isHTMLContentElement(inse
rtionPoint) && !insertionPoint.hasChildren())); | |
| 84 } | |
| 85 return nullptr; | |
| 86 } | |
| 87 | |
| 88 static HTMLSlotElement* finalDestinationSlotFor(const Node& node) | |
| 89 { | |
| 90 HTMLSlotElement* slot = node.assignedSlot(); | |
| 91 if (!slot) | |
| 92 return nullptr; | |
| 93 for (HTMLSlotElement* next = slot->assignedSlot(); next; next = next->assign
edSlot()) { | |
| 94 slot = next; | |
| 95 } | |
| 96 return slot; | |
| 97 } | |
| 98 | |
| 99 // TODO(hayato): This may return a wrong result for a node which is not in a | |
| 100 // document composed tree. See ComposedTreeTraversalTest's redistribution test
for details. | |
| 101 Node* ComposedTreeTraversal::traverseSiblings(const Node& node, TraversalDirecti
on direction) | |
| 102 { | |
| 103 if (node.isChildOfV1ShadowHost()) | |
| 104 return traverseSiblingsForV1HostChild(node, direction); | |
| 105 | |
| 106 if (shadowWhereNodeCanBeDistributed(node)) | |
| 107 return traverseSiblingsForV0Distribution(node, direction); | |
| 108 | |
| 109 if (Node* found = resolveDistributionStartingAt(direction == TraversalDirect
ionForward ? node.nextSibling() : node.previousSibling(), direction)) | |
| 110 return found; | |
| 111 | |
| 112 if (!node.isInV0ShadowTree()) | |
| 113 return nullptr; | |
| 114 | |
| 115 // For v0 older shadow tree | |
| 116 if (node.parentNode() && node.parentNode()->isShadowRoot()) { | |
| 117 ShadowRoot* parentShadowRoot = toShadowRoot(node.parentNode()); | |
| 118 if (!parentShadowRoot->isYoungest()) { | |
| 119 HTMLShadowElement* assignedInsertionPoint = parentShadowRoot->shadow
InsertionPointOfYoungerShadowRoot(); | |
| 120 ASSERT(assignedInsertionPoint); | |
| 121 return traverseSiblings(*assignedInsertionPoint, direction); | |
| 122 } | |
| 123 } | |
| 124 return nullptr; | |
| 125 } | |
| 126 | |
| 127 Node* ComposedTreeTraversal::traverseSiblingsForV1HostChild(const Node& node, Tr
aversalDirection direction) | |
| 128 { | |
| 129 HTMLSlotElement* slot = finalDestinationSlotFor(node); | |
| 130 if (!slot) | |
| 131 return nullptr; | |
| 132 if (Node* siblingInDistributedNodes = (direction == TraversalDirectionForwar
d ? slot->distributedNodeNextTo(node) : slot->distributedNodePreviousTo(node))) | |
| 133 return siblingInDistributedNodes; | |
| 134 return traverseSiblings(*slot, direction); | |
| 135 } | |
| 136 | |
| 137 Node* ComposedTreeTraversal::traverseSiblingsForV0Distribution(const Node& node,
TraversalDirection direction) | |
| 138 { | |
| 139 const InsertionPoint* finalDestination = resolveReprojection(&node); | |
| 140 if (!finalDestination) | |
| 141 return nullptr; | |
| 142 if (Node* found = (direction == TraversalDirectionForward ? finalDestination
->distributedNodeNextTo(&node) : finalDestination->distributedNodePreviousTo(&no
de))) | |
| 143 return found; | |
| 144 return traverseSiblings(*finalDestination, direction); | |
| 145 | |
| 146 } | |
| 147 | |
| 148 ContainerNode* ComposedTreeTraversal::traverseParent(const Node& node, ParentTra
versalDetails* details) | |
| 149 { | |
| 150 // TODO(hayato): Stop this hack for a pseudo element because a pseudo elemen
t is not a child of its parentOrShadowHostNode() in a composed tree. | |
| 151 if (node.isPseudoElement()) | |
| 152 return node.parentOrShadowHostNode(); | |
| 153 | |
| 154 if (node.isChildOfV1ShadowHost()) { | |
| 155 HTMLSlotElement* slot = finalDestinationSlotFor(node); | |
| 156 if (!slot) | |
| 157 return nullptr; | |
| 158 return traverseParent(*slot); | |
| 159 } | |
| 160 | |
| 161 Element* parent = node.parentElement(); | |
| 162 if (parent && isHTMLSlotElement(parent)) { | |
| 163 HTMLSlotElement& slot = toHTMLSlotElement(*parent); | |
| 164 if (!slot.getAssignedNodes().isEmpty()) | |
| 165 return nullptr; | |
| 166 return traverseParent(slot, details); | |
| 167 } | |
| 168 | |
| 169 if (canBeDistributedToInsertionPoint(node)) | |
| 170 return traverseParentForV0(node, details); | |
| 171 | |
| 172 ASSERT(!shadowWhereNodeCanBeDistributed(node)); | |
| 173 return traverseParentOrHost(node); | |
| 174 } | |
| 175 | |
| 176 ContainerNode* ComposedTreeTraversal::traverseParentForV0(const Node& node, Pare
ntTraversalDetails* details) | |
| 177 { | |
| 178 if (shadowWhereNodeCanBeDistributed(node)) { | |
| 179 if (const InsertionPoint* insertionPoint = resolveReprojection(&node)) { | |
| 180 if (details) | |
| 181 details->didTraverseInsertionPoint(insertionPoint); | |
| 182 // The node is distributed. But the distribution was stopped at this
insertion point. | |
| 183 if (shadowWhereNodeCanBeDistributed(*insertionPoint)) | |
| 184 return nullptr; | |
| 185 return traverseParent(*insertionPoint); | |
| 186 } | |
| 187 return nullptr; | |
| 188 } | |
| 189 ContainerNode* parent = traverseParentOrHost(node); | |
| 190 if (isActiveInsertionPoint(*parent)) | |
| 191 return nullptr; | |
| 192 return parent; | |
| 193 } | |
| 194 | |
| 195 ContainerNode* ComposedTreeTraversal::traverseParentOrHost(const Node& node) | |
| 196 { | |
| 197 ContainerNode* parent = node.parentNode(); | |
| 198 if (!parent) | |
| 199 return nullptr; | |
| 200 if (!parent->isShadowRoot()) | |
| 201 return parent; | |
| 202 ShadowRoot* shadowRoot = toShadowRoot(parent); | |
| 203 ASSERT(!shadowRoot->shadowInsertionPointOfYoungerShadowRoot()); | |
| 204 if (!shadowRoot->isYoungest()) | |
| 205 return nullptr; | |
| 206 return shadowRoot->host(); | |
| 207 } | |
| 208 | |
| 209 Node* ComposedTreeTraversal::childAt(const Node& node, unsigned index) | |
| 210 { | |
| 211 assertPrecondition(node); | |
| 212 Node* child = traverseFirstChild(node); | |
| 213 while (child && index--) | |
| 214 child = nextSibling(*child); | |
| 215 assertPostcondition(child); | |
| 216 return child; | |
| 217 } | |
| 218 | |
| 219 Node* ComposedTreeTraversal::nextSkippingChildren(const Node& node) | |
| 220 { | |
| 221 if (Node* nextSibling = traverseNextSibling(node)) | |
| 222 return nextSibling; | |
| 223 return traverseNextAncestorSibling(node); | |
| 224 } | |
| 225 | |
| 226 bool ComposedTreeTraversal::containsIncludingPseudoElement(const ContainerNode&
container, const Node& node) | |
| 227 { | |
| 228 assertPrecondition(container); | |
| 229 assertPrecondition(node); | |
| 230 // This can be slower than ComposedTreeTraversal::contains() because we | |
| 231 // can't early exit even when container doesn't have children. | |
| 232 for (const Node* current = &node; current; current = traverseParent(*current
)) { | |
| 233 if (current == &container) | |
| 234 return true; | |
| 235 } | |
| 236 return false; | |
| 237 } | |
| 238 | |
| 239 Node* ComposedTreeTraversal::previousSkippingChildren(const Node& node) | |
| 240 { | |
| 241 if (Node* previousSibling = traversePreviousSibling(node)) | |
| 242 return previousSibling; | |
| 243 return traversePreviousAncestorSibling(node); | |
| 244 } | |
| 245 | |
| 246 static Node* previousAncestorSiblingPostOrder(const Node& current, const Node* s
tayWithin) | |
| 247 { | |
| 248 ASSERT(!ComposedTreeTraversal::previousSibling(current)); | |
| 249 for (Node* parent = ComposedTreeTraversal::parent(current); parent; parent =
ComposedTreeTraversal::parent(*parent)) { | |
| 250 if (parent == stayWithin) | |
| 251 return nullptr; | |
| 252 if (Node* previousSibling = ComposedTreeTraversal::previousSibling(*pare
nt)) | |
| 253 return previousSibling; | |
| 254 } | |
| 255 return nullptr; | |
| 256 } | |
| 257 | |
| 258 // TODO(yosin) We should consider introducing template class to share code | |
| 259 // between DOM tree traversal and composed tree tarversal. | |
| 260 Node* ComposedTreeTraversal::previousPostOrder(const Node& current, const Node*
stayWithin) | |
| 261 { | |
| 262 assertPrecondition(current); | |
| 263 if (stayWithin) | |
| 264 assertPrecondition(*stayWithin); | |
| 265 if (Node* lastChild = traverseLastChild(current)) { | |
| 266 assertPostcondition(lastChild); | |
| 267 return lastChild; | |
| 268 } | |
| 269 if (current == stayWithin) | |
| 270 return nullptr; | |
| 271 if (Node* previousSibling = traversePreviousSibling(current)) { | |
| 272 assertPostcondition(previousSibling); | |
| 273 return previousSibling; | |
| 274 } | |
| 275 return previousAncestorSiblingPostOrder(current, stayWithin); | |
| 276 } | |
| 277 | |
| 278 bool ComposedTreeTraversal::isDescendantOf(const Node& node, const Node& other) | |
| 279 { | |
| 280 assertPrecondition(node); | |
| 281 assertPrecondition(other); | |
| 282 if (!hasChildren(other) || node.inDocument() != other.inDocument()) | |
| 283 return false; | |
| 284 for (const ContainerNode* n = traverseParent(node); n; n = traverseParent(*n
)) { | |
| 285 if (n == other) | |
| 286 return true; | |
| 287 } | |
| 288 return false; | |
| 289 } | |
| 290 | |
| 291 Node* ComposedTreeTraversal::commonAncestor(const Node& nodeA, const Node& nodeB
) | |
| 292 { | |
| 293 assertPrecondition(nodeA); | |
| 294 assertPrecondition(nodeB); | |
| 295 Node* result = nodeA.commonAncestor(nodeB, | |
| 296 [](const Node& node) | |
| 297 { | |
| 298 return ComposedTreeTraversal::parent(node); | |
| 299 }); | |
| 300 assertPostcondition(result); | |
| 301 return result; | |
| 302 } | |
| 303 | |
| 304 Node* ComposedTreeTraversal::traverseNextAncestorSibling(const Node& node) | |
| 305 { | |
| 306 ASSERT(!traverseNextSibling(node)); | |
| 307 for (Node* parent = traverseParent(node); parent; parent = traverseParent(*p
arent)) { | |
| 308 if (Node* nextSibling = traverseNextSibling(*parent)) | |
| 309 return nextSibling; | |
| 310 } | |
| 311 return nullptr; | |
| 312 } | |
| 313 | |
| 314 Node* ComposedTreeTraversal::traversePreviousAncestorSibling(const Node& node) | |
| 315 { | |
| 316 ASSERT(!traversePreviousSibling(node)); | |
| 317 for (Node* parent = traverseParent(node); parent; parent = traverseParent(*p
arent)) { | |
| 318 if (Node* previousSibling = traversePreviousSibling(*parent)) | |
| 319 return previousSibling; | |
| 320 } | |
| 321 return nullptr; | |
| 322 } | |
| 323 | |
| 324 unsigned ComposedTreeTraversal::index(const Node& node) | |
| 325 { | |
| 326 assertPrecondition(node); | |
| 327 unsigned count = 0; | |
| 328 for (Node* runner = traversePreviousSibling(node); runner; runner = previous
Sibling(*runner)) | |
| 329 ++count; | |
| 330 return count; | |
| 331 } | |
| 332 | |
| 333 unsigned ComposedTreeTraversal::countChildren(const Node& node) | |
| 334 { | |
| 335 assertPrecondition(node); | |
| 336 unsigned count = 0; | |
| 337 for (Node* runner = traverseFirstChild(node); runner; runner = traverseNextS
ibling(*runner)) | |
| 338 ++count; | |
| 339 return count; | |
| 340 } | |
| 341 | |
| 342 Node* ComposedTreeTraversal::lastWithin(const Node& node) | |
| 343 { | |
| 344 assertPrecondition(node); | |
| 345 Node* descendant = traverseLastChild(node); | |
| 346 for (Node* child = descendant; child; child = lastChild(*child)) | |
| 347 descendant = child; | |
| 348 assertPostcondition(descendant); | |
| 349 return descendant; | |
| 350 } | |
| 351 | |
| 352 Node& ComposedTreeTraversal::lastWithinOrSelf(const Node& node) | |
| 353 { | |
| 354 assertPrecondition(node); | |
| 355 Node* lastDescendant = lastWithin(node); | |
| 356 Node& result = lastDescendant ? *lastDescendant : const_cast<Node&>(node); | |
| 357 assertPostcondition(&result); | |
| 358 return result; | |
| 359 } | |
| 360 | |
| 361 } // namespace blink | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1675163002:
Rename ComposedTree to FlatTree (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master