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/ComposedTreeWalker.h" 30 31#include "core/dom/Element.h" 32#include "core/dom/shadow/ElementShadow.h" 33#include "core/html/HTMLShadowElement.h" 34 35namespace WebCore { 36 37static inline ElementShadow* shadowFor(const Node* node) 38{ 39 if (node && node->isElementNode()) 40 return toElement(node)->shadow(); 41 return 0; 42} 43 44Node* ComposedTreeWalker::traverseChild(const Node* node, TraversalDirection direction) const 45{ 46 ASSERT(node); 47 ElementShadow* shadow = shadowFor(node); 48 return shadow ? traverseLightChildren(shadow->youngestShadowRoot(), direction) 49 : traverseLightChildren(node, direction); 50} 51 52Node* ComposedTreeWalker::traverseLightChildren(const Node* node, TraversalDirection direction) 53{ 54 ASSERT(node); 55 return traverseSiblings(direction == TraversalDirectionForward ? node->firstChild() : node->lastChild(), direction); 56} 57 58Node* ComposedTreeWalker::traverseSiblings(const Node* node, TraversalDirection direction) 59{ 60 for (const Node* sibling = node; sibling; sibling = (direction == TraversalDirectionForward ? sibling->nextSibling() : sibling->previousSibling())) { 61 if (Node* found = traverseNode(sibling, direction)) 62 return found; 63 } 64 return 0; 65} 66 67Node* ComposedTreeWalker::traverseNode(const Node* node, TraversalDirection direction) 68{ 69 ASSERT(node); 70 if (!isActiveInsertionPoint(*node)) 71 return const_cast<Node*>(node); 72 const InsertionPoint* insertionPoint = toInsertionPoint(node); 73 if (Node* found = traverseDistributedNodes(direction == TraversalDirectionForward ? insertionPoint->first() : insertionPoint->last(), insertionPoint, direction)) 74 return found; 75 ASSERT(isHTMLShadowElement(node) || (isHTMLContentElement(node) && !node->hasChildren())); 76 return 0; 77} 78 79Node* ComposedTreeWalker::traverseDistributedNodes(const Node* node, const InsertionPoint* insertionPoint, TraversalDirection direction) 80{ 81 for (const Node* next = node; next; next = (direction == TraversalDirectionForward ? insertionPoint->nextTo(next) : insertionPoint->previousTo(next))) { 82 if (Node* found = traverseNode(next, direction)) 83 return found; 84 } 85 return 0; 86} 87 88Node* ComposedTreeWalker::traverseSiblingOrBackToInsertionPoint(const Node* node, TraversalDirection direction) 89{ 90 ASSERT(node); 91 92 if (!shadowWhereNodeCanBeDistributed(*node)) 93 return traverseSiblingInCurrentTree(node, direction); 94 95 const InsertionPoint* insertionPoint = resolveReprojection(node); 96 if (!insertionPoint) 97 return traverseSiblingInCurrentTree(node, direction); 98 99 if (Node* found = traverseDistributedNodes(direction == TraversalDirectionForward ? insertionPoint->nextTo(node) : insertionPoint->previousTo(node), insertionPoint, direction)) 100 return found; 101 return traverseSiblingOrBackToInsertionPoint(insertionPoint, direction); 102} 103 104Node* ComposedTreeWalker::traverseSiblingInCurrentTree(const Node* node, TraversalDirection direction) 105{ 106 ASSERT(node); 107 if (Node* found = traverseSiblings(direction == TraversalDirectionForward ? node->nextSibling() : node->previousSibling(), direction)) 108 return found; 109 if (Node* next = traverseBackToYoungerShadowRoot(node, direction)) 110 return next; 111 return 0; 112} 113 114Node* ComposedTreeWalker::traverseBackToYoungerShadowRoot(const Node* node, TraversalDirection direction) 115{ 116 ASSERT(node); 117 if (node->parentNode() && node->parentNode()->isShadowRoot()) { 118 ShadowRoot* parentShadowRoot = toShadowRoot(node->parentNode()); 119 if (!parentShadowRoot->isYoungest()) { 120 HTMLShadowElement* assignedInsertionPoint = parentShadowRoot->shadowInsertionPointOfYoungerShadowRoot(); 121 ASSERT(assignedInsertionPoint); 122 return traverseSiblingInCurrentTree(assignedInsertionPoint, direction); 123 } 124 } 125 return 0; 126} 127 128// FIXME: Use an iterative algorithm so that it can be inlined. 129// https://bugs.webkit.org/show_bug.cgi?id=90415 130Node* ComposedTreeWalker::traverseParent(const Node* node, ParentTraversalDetails* details) const 131{ 132 if (node->isPseudoElement()) 133 return node->parentOrShadowHostNode(); 134 135 if (shadowWhereNodeCanBeDistributed(*node)) { 136 if (const InsertionPoint* insertionPoint = resolveReprojection(node)) { 137 if (details) 138 details->didTraverseInsertionPoint(insertionPoint); 139 // The node is distributed. But the distribution was stopped at this insertion point. 140 if (shadowWhereNodeCanBeDistributed(*insertionPoint)) 141 return 0; 142 return traverseParentOrHost(insertionPoint); 143 } 144 return 0; 145 } 146 return traverseParentOrHost(node); 147} 148 149inline Node* ComposedTreeWalker::traverseParentOrHost(const Node* node) const 150{ 151 Node* parent = node->parentNode(); 152 if (!parent) 153 return 0; 154 if (!parent->isShadowRoot()) 155 return parent; 156 ShadowRoot* shadowRoot = toShadowRoot(parent); 157 ASSERT(!shadowRoot->shadowInsertionPointOfYoungerShadowRoot()); 158 if (!shadowRoot->isYoungest()) 159 return 0; 160 return shadowRoot->host(); 161} 162 163} // namespace 164