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