1926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2012 Google Inc. All rights reserved. 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions are 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * met: 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * * Redistributions of source code must retain the above copyright 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * contributors may be used to endorse or promote products derived from 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this software without specific prior written permission. 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 29c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)#include "core/dom/shadow/ComposedTreeWalker.h" 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#include "core/dom/Element.h" 32e52495584422c5edb5b2944981473a2e208da323Torne (Richard Coles)#include "core/dom/shadow/ElementShadow.h" 33d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#include "core/html/HTMLShadowElement.h" 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 35c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static inline ElementShadow* shadowFor(const Node* node) 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node && node->isElementNode()) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return toElement(node)->shadow(); 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 44c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseChild(const Node* node, TraversalDirection direction) const 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node); 478abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) ElementShadow* shadow = shadowFor(node); 488abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) return shadow ? traverseLightChildren(shadow->youngestShadowRoot(), direction) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : traverseLightChildren(node, direction); 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 52c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseLightChildren(const Node* node, TraversalDirection direction) 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node); 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return traverseSiblings(direction == TraversalDirectionForward ? node->firstChild() : node->lastChild(), direction); 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 58c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseSiblings(const Node* node, TraversalDirection direction) 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (const Node* sibling = node; sibling; sibling = (direction == TraversalDirectionForward ? sibling->nextSibling() : sibling->previousSibling())) { 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Node* found = traverseNode(sibling, direction)) 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return found; 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 67c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseNode(const Node* node, TraversalDirection direction) 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node); 7019cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) if (!isActiveInsertionPoint(*node)) 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return const_cast<Node*>(node); 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const InsertionPoint* insertionPoint = toInsertionPoint(node); 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Node* found = traverseDistributedNodes(direction == TraversalDirectionForward ? insertionPoint->first() : insertionPoint->last(), insertionPoint, direction)) 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return found; 75d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(isHTMLShadowElement(node) || (isHTMLContentElement(node) && !node->hasChildren())); 7651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) return 0; 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 79c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseDistributedNodes(const Node* node, const InsertionPoint* insertionPoint, TraversalDirection direction) 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (const Node* next = node; next; next = (direction == TraversalDirectionForward ? insertionPoint->nextTo(next) : insertionPoint->previousTo(next))) { 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Node* found = traverseNode(next, direction)) 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return found; 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 88c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseSiblingOrBackToInsertionPoint(const Node* node, TraversalDirection direction) 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node); 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9219cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) if (!shadowWhereNodeCanBeDistributed(*node)) 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return traverseSiblingInCurrentTree(node, direction); 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9519cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) const InsertionPoint* insertionPoint = resolveReprojection(node); 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!insertionPoint) 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return traverseSiblingInCurrentTree(node, direction); 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Node* found = traverseDistributedNodes(direction == TraversalDirectionForward ? insertionPoint->nextTo(node) : insertionPoint->previousTo(node), insertionPoint, direction)) 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return found; 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return traverseSiblingOrBackToInsertionPoint(insertionPoint, direction); 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 104c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseSiblingInCurrentTree(const Node* node, TraversalDirection direction) 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node); 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Node* found = traverseSiblings(direction == TraversalDirectionForward ? node->nextSibling() : node->previousSibling(), direction)) 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return found; 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Node* next = traverseBackToYoungerShadowRoot(node, direction)) 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return next; 11119cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) return 0; 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 114c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseBackToYoungerShadowRoot(const Node* node, TraversalDirection direction) 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(node); 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (node->parentNode() && node->parentNode()->isShadowRoot()) { 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ShadowRoot* parentShadowRoot = toShadowRoot(node->parentNode()); 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!parentShadowRoot->isYoungest()) { 12019cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) HTMLShadowElement* assignedInsertionPoint = parentShadowRoot->shadowInsertionPointOfYoungerShadowRoot(); 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(assignedInsertionPoint); 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return traverseSiblingInCurrentTree(assignedInsertionPoint, direction); 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// FIXME: Use an iterative algorithm so that it can be inlined. 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// https://bugs.webkit.org/show_bug.cgi?id=90415 130c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)Node* ComposedTreeWalker::traverseParent(const Node* node, ParentTraversalDetails* details) const 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 132926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (node->isPseudoElement()) 133926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return node->parentOrShadowHostNode(); 134926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 13519cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) if (shadowWhereNodeCanBeDistributed(*node)) { 13619cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) if (const InsertionPoint* insertionPoint = resolveReprojection(node)) { 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (details) 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) details->didTraverseInsertionPoint(insertionPoint); 13919cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) // The node is distributed. But the distribution was stopped at this insertion point. 14019cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) if (shadowWhereNodeCanBeDistributed(*insertionPoint)) 14119cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) return 0; 14243e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) return traverseParentOrHost(insertionPoint); 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 14419cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) return 0; 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 14643e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) return traverseParentOrHost(node); 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 14943e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles)inline Node* ComposedTreeWalker::traverseParentOrHost(const Node* node) const 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 15151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) Node* parent = node->parentNode(); 15251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) if (!parent) 15351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) return 0; 15451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) if (!parent->isShadowRoot()) 15551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) return parent; 15651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) ShadowRoot* shadowRoot = toShadowRoot(parent); 15719cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) ASSERT(!shadowRoot->shadowInsertionPointOfYoungerShadowRoot()); 15851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) if (!shadowRoot->isYoungest()) 15951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) return 0; 16051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) return shadowRoot->host(); 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace 164