1 2 /* 3 * Copyright (C) 2012 Google Inc. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Neither the name of Google Inc. nor the names of its 12 * contributors may be used to endorse or promote products derived from 13 * this software without specific prior written permission. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 18 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 19 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 21 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 25 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 */ 27 28 #include "config.h" 29 #include "core/dom/shadow/ComposedShadowTreeWalker.h" 30 31 #include "core/dom/Element.h" 32 #include "core/dom/shadow/ContentDistributor.h" 33 #include "core/dom/shadow/ElementShadow.h" 34 #include "core/dom/shadow/InsertionPoint.h" 35 36 namespace WebCore { 37 38 static inline ElementShadow* shadowFor(const Node* node) 39 { 40 if (node && node->isElementNode()) 41 return toElement(node)->shadow(); 42 return 0; 43 } 44 45 static inline bool nodeCanBeDistributed(const Node* node) 46 { 47 ASSERT(node); 48 Node* parent = parentNodeForDistribution(node); 49 if (!parent) 50 return false; 51 52 if (ShadowRoot* shadowRoot = parent->isShadowRoot() ? toShadowRoot(parent) : 0) 53 return shadowRoot->insertionPoint(); 54 55 if (parent->isElementNode() && toElement(parent)->shadow()) 56 return true; 57 58 return false; 59 } 60 61 Node* ComposedShadowTreeWalker::traverseChild(const Node* node, TraversalDirection direction) const 62 { 63 ASSERT(node); 64 if (canCrossUpperBoundary()) { 65 ElementShadow* shadow = shadowFor(node); 66 return shadow ? traverseLightChildren(shadow->youngestShadowRoot(), direction) 67 : traverseLightChildren(node, direction); 68 } 69 if (isShadowHost(node)) 70 return 0; 71 return traverseLightChildren(node, direction); 72 } 73 74 Node* ComposedShadowTreeWalker::traverseLightChildren(const Node* node, TraversalDirection direction) 75 { 76 ASSERT(node); 77 return traverseSiblings(direction == TraversalDirectionForward ? node->firstChild() : node->lastChild(), direction); 78 } 79 80 Node* ComposedShadowTreeWalker::traverseSiblings(const Node* node, TraversalDirection direction) 81 { 82 for (const Node* sibling = node; sibling; sibling = (direction == TraversalDirectionForward ? sibling->nextSibling() : sibling->previousSibling())) { 83 if (Node* found = traverseNode(sibling, direction)) 84 return found; 85 } 86 return 0; 87 } 88 89 Node* ComposedShadowTreeWalker::traverseNode(const Node* node, TraversalDirection direction) 90 { 91 ASSERT(node); 92 if (!isActiveInsertionPoint(node)) 93 return const_cast<Node*>(node); 94 const InsertionPoint* insertionPoint = toInsertionPoint(node); 95 if (Node* found = traverseDistributedNodes(direction == TraversalDirectionForward ? insertionPoint->first() : insertionPoint->last(), insertionPoint, direction)) 96 return found; 97 return traverseLightChildren(node, direction); 98 } 99 100 Node* ComposedShadowTreeWalker::traverseDistributedNodes(const Node* node, const InsertionPoint* insertionPoint, TraversalDirection direction) 101 { 102 for (const Node* next = node; next; next = (direction == TraversalDirectionForward ? insertionPoint->nextTo(next) : insertionPoint->previousTo(next))) { 103 if (Node* found = traverseNode(next, direction)) 104 return found; 105 } 106 return 0; 107 } 108 109 Node* ComposedShadowTreeWalker::traverseSiblingOrBackToInsertionPoint(const Node* node, TraversalDirection direction) 110 { 111 ASSERT(node); 112 113 if (!nodeCanBeDistributed(node)) 114 return traverseSiblingInCurrentTree(node, direction); 115 116 InsertionPoint* insertionPoint = resolveReprojection(node); 117 if (!insertionPoint) 118 return traverseSiblingInCurrentTree(node, direction); 119 120 if (Node* found = traverseDistributedNodes(direction == TraversalDirectionForward ? insertionPoint->nextTo(node) : insertionPoint->previousTo(node), insertionPoint, direction)) 121 return found; 122 return traverseSiblingOrBackToInsertionPoint(insertionPoint, direction); 123 } 124 125 Node* ComposedShadowTreeWalker::traverseSiblingInCurrentTree(const Node* node, TraversalDirection direction) 126 { 127 ASSERT(node); 128 if (Node* found = traverseSiblings(direction == TraversalDirectionForward ? node->nextSibling() : node->previousSibling(), direction)) 129 return found; 130 if (Node* next = traverseBackToYoungerShadowRoot(node, direction)) 131 return next; 132 return escapeFallbackContentElement(node, direction); 133 } 134 135 Node* ComposedShadowTreeWalker::traverseBackToYoungerShadowRoot(const Node* node, TraversalDirection direction) 136 { 137 ASSERT(node); 138 if (node->parentNode() && node->parentNode()->isShadowRoot()) { 139 ShadowRoot* parentShadowRoot = toShadowRoot(node->parentNode()); 140 if (!parentShadowRoot->isYoungest()) { 141 InsertionPoint* assignedInsertionPoint = parentShadowRoot->insertionPoint(); 142 ASSERT(assignedInsertionPoint); 143 return traverseSiblingInCurrentTree(assignedInsertionPoint, direction); 144 } 145 } 146 return 0; 147 } 148 149 inline Node* ComposedShadowTreeWalker::escapeFallbackContentElement(const Node* node, TraversalDirection direction) 150 { 151 ASSERT(node); 152 if (node->parentNode() && isActiveInsertionPoint(node->parentNode())) 153 return traverseSiblingOrBackToInsertionPoint(node->parentNode(), direction); 154 return 0; 155 } 156 157 inline Node* ComposedShadowTreeWalker::traverseNodeEscapingFallbackContents(const Node* node, ParentTraversalDetails* details) const 158 { 159 ASSERT(node); 160 if (!node->isInsertionPoint()) 161 return const_cast<Node*>(node); 162 const InsertionPoint* insertionPoint = toInsertionPoint(node); 163 return insertionPoint->hasDistribution() ? 0 : 164 insertionPoint->isActive() ? traverseParent(node, details) : const_cast<Node*>(node); 165 } 166 167 // FIXME: Use an iterative algorithm so that it can be inlined. 168 // https://bugs.webkit.org/show_bug.cgi?id=90415 169 Node* ComposedShadowTreeWalker::traverseParent(const Node* node, ParentTraversalDetails* details) const 170 { 171 if (node->isPseudoElement()) 172 return node->parentOrShadowHostNode(); 173 174 if (!canCrossUpperBoundary() && node->isShadowRoot()) { 175 ASSERT(toShadowRoot(node)->isYoungest()); 176 return 0; 177 } 178 179 if (nodeCanBeDistributed(node)) { 180 if (InsertionPoint* insertionPoint = resolveReprojection(node)) { 181 if (details) 182 details->didTraverseInsertionPoint(insertionPoint); 183 return traverseParent(insertionPoint, details); 184 } 185 186 // The node is a non-distributed light child or older shadow's child. 187 if (details) 188 details->childWasOutOfComposition(); 189 } 190 return traverseParentInCurrentTree(node, details); 191 } 192 193 inline Node* ComposedShadowTreeWalker::traverseParentInCurrentTree(const Node* node, ParentTraversalDetails* details) const 194 { 195 if (Node* parent = node->parentNode()) 196 return parent->isShadowRoot() ? traverseParentBackToYoungerShadowRootOrHost(toShadowRoot(parent), details) : traverseNodeEscapingFallbackContents(parent, details); 197 return 0; 198 } 199 200 Node* ComposedShadowTreeWalker::traverseParentBackToYoungerShadowRootOrHost(const ShadowRoot* shadowRoot, ParentTraversalDetails* details) const 201 { 202 ASSERT(shadowRoot); 203 ASSERT(!shadowRoot->insertionPoint()); 204 205 if (shadowRoot->isYoungest()) { 206 if (canCrossUpperBoundary()) { 207 if (details) 208 details->didTraverseShadowRoot(shadowRoot); 209 return shadowRoot->host(); 210 } 211 212 return const_cast<ShadowRoot*>(shadowRoot); 213 } 214 215 return 0; 216 } 217 218 } // namespace 219