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