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 36namespace WebCore { 37 38static inline ElementShadow* shadowFor(const Node* node) 39{ 40 if (node && node->isElementNode()) 41 return toElement(node)->shadow(); 42 return 0; 43} 44 45static 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 61Node* 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 74Node* ComposedShadowTreeWalker::traverseLightChildren(const Node* node, TraversalDirection direction) 75{ 76 ASSERT(node); 77 return traverseSiblings(direction == TraversalDirectionForward ? node->firstChild() : node->lastChild(), direction); 78} 79 80Node* 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 89Node* 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 100Node* 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 109Node* 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 125Node* 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 135Node* 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 149inline 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 157inline 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 169Node* 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 193inline 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 200Node* 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