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