1/* 2 * Copyright (C) 2012 Google Inc. All rights reserved. 3 * Copyright (C) 2013 Apple 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 "NodeRenderingTraversal.h" 30 31#include "InsertionPoint.h" 32#include "ShadowRoot.h" 33 34namespace WebCore { 35 36namespace NodeRenderingTraversal { 37 38static Node* findFirstSiblingEnteringInsertionPoints(const Node*); 39static Node* findFirstEnteringInsertionPoints(const Node*); 40static Node* findFirstFromDistributedNode(const Node*, const InsertionPoint*); 41static Node* findLastSiblingEnteringInsertionPoints(const Node*); 42static Node* findLastEnteringInsertionPoints(const Node*); 43static Node* findLastFromDistributedNode(const Node*, const InsertionPoint*); 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 (parent->isShadowRoot()) 53 return false; 54 55 if (parent->isElementNode() && toElement(parent)->shadowRoot()) 56 return true; 57 58 return false; 59} 60 61static Node* findFirstSiblingEnteringInsertionPoints(const Node* node) 62{ 63 for (const Node* sibling = node; sibling; sibling = sibling->nextSibling()) { 64 if (Node* found = findFirstEnteringInsertionPoints(sibling)) 65 return found; 66 } 67 return nullptr; 68} 69 70static Node* findFirstEnteringInsertionPoints(const Node* node) 71{ 72 ASSERT(node); 73 if (!isActiveInsertionPoint(node)) 74 return const_cast<Node*>(node); 75 const InsertionPoint* insertionPoint = toInsertionPoint(node); 76 if (Node* found = findFirstFromDistributedNode(insertionPoint->firstDistributed(), insertionPoint)) 77 return found; 78 return findFirstSiblingEnteringInsertionPoints(node->firstChild()); 79} 80 81static Node* findFirstFromDistributedNode(const Node* node, const InsertionPoint* insertionPoint) 82{ 83 for (const Node* next = node; next; next = insertionPoint->nextDistributedTo(next)) { 84 if (Node* found = findFirstEnteringInsertionPoints(next)) 85 return found; 86 } 87 return nullptr; 88} 89 90static Node* findLastSiblingEnteringInsertionPoints(const Node* node) 91{ 92 for (const Node* sibling = node; sibling; sibling = sibling->previousSibling()) { 93 if (Node* found = findLastEnteringInsertionPoints(sibling)) 94 return found; 95 } 96 return nullptr; 97} 98 99static Node* findLastEnteringInsertionPoints(const Node* node) 100{ 101 ASSERT(node); 102 if (!isActiveInsertionPoint(node)) 103 return const_cast<Node*>(node); 104 const InsertionPoint* insertionPoint = toInsertionPoint(node); 105 if (Node* found = findLastFromDistributedNode(insertionPoint->lastDistributed(), insertionPoint)) 106 return found; 107 return findLastSiblingEnteringInsertionPoints(node->lastChild()); 108} 109 110static Node* findLastFromDistributedNode(const Node* node, const InsertionPoint* insertionPoint) 111{ 112 for (const Node* next = node; next; next = insertionPoint->previousDistributedTo(next)) { 113 if (Node* found = findLastEnteringInsertionPoints(next)) 114 return found; 115 } 116 return nullptr; 117} 118 119enum ShadowRootCrossing { CrossShadowRoot, DontCrossShadowRoot }; 120 121static ContainerNode* traverseParent(const Node* node, ShadowRootCrossing shadowRootCrossing) 122{ 123 if (shadowRootCrossing == DontCrossShadowRoot && node->isShadowRoot()) 124 return 0; 125 126 if (nodeCanBeDistributed(node)) { 127 if (InsertionPoint* insertionPoint = findInsertionPointOf(node)) 128 return traverseParent(insertionPoint, shadowRootCrossing); 129 return nullptr; 130 } 131 ContainerNode* parent = node->parentNode(); 132 if (!parent) 133 return nullptr; 134 135 if (parent->isShadowRoot()) 136 return shadowRootCrossing == CrossShadowRoot ? toShadowRoot(parent)->hostElement() : parent; 137 138 if (parent->isInsertionPoint()) { 139 const InsertionPoint* insertionPoint = toInsertionPoint(parent); 140 if (insertionPoint->hasDistribution()) 141 return nullptr; 142 if (insertionPoint->isActive()) 143 return traverseParent(parent, shadowRootCrossing); 144 } 145 return parent; 146} 147 148static Node* traverseFirstChild(const Node* node, ShadowRootCrossing shadowRootCrossing) 149{ 150 ASSERT(node); 151 if (node->shadowRoot()) { 152 if (shadowRootCrossing == DontCrossShadowRoot) 153 return nullptr; 154 node = node->shadowRoot(); 155 } 156 return findFirstSiblingEnteringInsertionPoints(node->firstChild()); 157} 158 159static Node* traverseLastChild(const Node* node, ShadowRootCrossing shadowRootCrossing) 160{ 161 ASSERT(node); 162 if (node->shadowRoot()) { 163 if (shadowRootCrossing == DontCrossShadowRoot) 164 return nullptr; 165 node = node->shadowRoot(); 166 } 167 return findLastSiblingEnteringInsertionPoints(node->lastChild()); 168} 169 170static Node* traverseNextSibling(const Node* node) 171{ 172 ASSERT(node); 173 174 InsertionPoint* insertionPoint; 175 if (nodeCanBeDistributed(node) && (insertionPoint = findInsertionPointOf(node))) { 176 Node* found = findFirstFromDistributedNode(insertionPoint->nextDistributedTo(node), insertionPoint); 177 if (found) 178 return found; 179 return traverseNextSibling(insertionPoint); 180 } 181 182 for (const Node* sibling = node->nextSibling(); sibling; sibling = sibling->nextSibling()) { 183 if (Node* found = findFirstEnteringInsertionPoints(sibling)) 184 return found; 185 } 186 if (node->parentNode() && isActiveInsertionPoint(node->parentNode())) 187 return traverseNextSibling(node->parentNode()); 188 189 return nullptr; 190} 191 192static Node* traversePreviousSibling(const Node* node) 193{ 194 ASSERT(node); 195 196 InsertionPoint* insertionPoint; 197 if (nodeCanBeDistributed(node) && (insertionPoint = findInsertionPointOf(node))) { 198 Node* found = findLastFromDistributedNode(insertionPoint->previousDistributedTo(node), insertionPoint); 199 if (found) 200 return found; 201 return traversePreviousSibling(insertionPoint); 202 } 203 204 for (const Node* sibling = node->previousSibling(); sibling; sibling = sibling->previousSibling()) { 205 if (Node* found = findLastEnteringInsertionPoints(sibling)) 206 return found; 207 } 208 if (node->parentNode() && isActiveInsertionPoint(node->parentNode())) 209 return traversePreviousSibling(node->parentNode()); 210 211 return nullptr; 212} 213 214ContainerNode* parentSlow(const Node* node) 215{ 216 ASSERT(!node->isShadowRoot()); 217 218 return traverseParent(node, CrossShadowRoot); 219} 220 221Node* firstChildSlow(const Node* node) 222{ 223 ASSERT(!node->isShadowRoot()); 224 225 return traverseFirstChild(node, DontCrossShadowRoot); 226} 227 228Node* nextSiblingSlow(const Node* node) 229{ 230 ASSERT(!node->isShadowRoot()); 231 232 return traverseNextSibling(node); 233} 234 235Node* previousSiblingSlow(const Node* node) 236{ 237 ASSERT(!node->isShadowRoot()); 238 239 return traversePreviousSibling(node); 240} 241 242Node* nextInScope(const Node* node) 243{ 244 ASSERT(!isActiveInsertionPoint(node)); 245 246 if (Node* next = traverseFirstChild(node, DontCrossShadowRoot)) 247 return next; 248 if (Node* next = traverseNextSibling(node)) 249 return next; 250 const Node* current = node; 251 while (current && !traverseNextSibling(current)) 252 current = traverseParent(current, DontCrossShadowRoot); 253 return current ? traverseNextSibling(current) : 0; 254} 255 256Node* previousInScope(const Node* node) 257{ 258 ASSERT(!isActiveInsertionPoint(node)); 259 260 if (Node* current = traversePreviousSibling(node)) { 261 while (Node* child = traverseLastChild(current, DontCrossShadowRoot)) 262 current = child; 263 return current; 264 } 265 return traverseParent(node, DontCrossShadowRoot); 266} 267 268Node* parentInScope(const Node* node) 269{ 270 ASSERT(!isActiveInsertionPoint(node)); 271 272 return traverseParent(node, DontCrossShadowRoot); 273} 274 275Node* lastChildInScope(const Node* node) 276{ 277 ASSERT(!isActiveInsertionPoint(node)); 278 279 return traverseLastChild(node, DontCrossShadowRoot); 280} 281 282} 283 284} // namespace 285