Use is<>() / downcast<>() for Element
[WebKit-https.git] / Source / WebCore / dom / NodeRenderingTraversal.cpp
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
34 namespace WebCore {
35
36 namespace NodeRenderingTraversal {
37
38 static Node* findFirstSiblingEnteringInsertionPoints(const Node*);
39 static Node* findFirstEnteringInsertionPoints(const Node*);
40 static Node* findFirstFromDistributedNode(const Node*, const InsertionPoint*);
41 static Node* findLastSiblingEnteringInsertionPoints(const Node*);
42 static Node* findLastEnteringInsertionPoints(const Node*);
43 static Node* findLastFromDistributedNode(const Node*, const InsertionPoint*);
44
45 static 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 (is<Element>(parent) && downcast<Element>(*parent).shadowRoot())
56         return true;
57     
58     return false;
59 }
60
61 static 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
70 static Node* findFirstEnteringInsertionPoints(const Node* node)
71 {
72     ASSERT(node);
73     if (!isActiveInsertionPoint(node))
74         return const_cast<Node*>(node);
75     const InsertionPoint& insertionPoint = downcast<InsertionPoint>(*node);
76     if (Node* found = findFirstFromDistributedNode(insertionPoint.firstDistributed(), &insertionPoint))
77         return found;
78     return findFirstSiblingEnteringInsertionPoints(node->firstChild());
79 }
80
81 static 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
90 static 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
99 static Node* findLastEnteringInsertionPoints(const Node* node)
100 {
101     ASSERT(node);
102     if (!isActiveInsertionPoint(node))
103         return const_cast<Node*>(node);
104     const InsertionPoint& insertionPoint = downcast<InsertionPoint>(*node);
105     if (Node* found = findLastFromDistributedNode(insertionPoint.lastDistributed(), &insertionPoint))
106         return found;
107     return findLastSiblingEnteringInsertionPoints(node->lastChild());
108 }
109
110 static 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
119 enum ShadowRootCrossing { CrossShadowRoot, DontCrossShadowRoot };
120
121 static ContainerNode* traverseParent(const Node* node, ShadowRootCrossing shadowRootCrossing)
122 {
123     if (shadowRootCrossing == DontCrossShadowRoot  && node->isShadowRoot())
124         return nullptr;
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 (is<ShadowRoot>(parent))
136         return shadowRootCrossing == CrossShadowRoot ? downcast<ShadowRoot>(parent)->hostElement() : parent;
137
138     if (is<InsertionPoint>(parent)) {
139         const InsertionPoint& insertionPoint = downcast<InsertionPoint>(*parent);
140         if (insertionPoint.hasDistribution())
141             return nullptr;
142         if (insertionPoint.isActive())
143             return traverseParent(parent, shadowRootCrossing);
144     }
145     return parent;
146 }
147
148 static 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
159 static 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
170 static 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
192 static 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
214 ContainerNode* parentSlow(const Node* node)
215 {
216     ASSERT(!node->isShadowRoot());
217
218     return traverseParent(node, CrossShadowRoot);
219 }
220
221 Node* firstChildSlow(const Node* node)
222 {
223     ASSERT(!node->isShadowRoot());
224
225     return traverseFirstChild(node, DontCrossShadowRoot);
226 }
227
228 Node* nextSiblingSlow(const Node* node)
229 {
230     ASSERT(!node->isShadowRoot());
231
232     return traverseNextSibling(node);
233 }
234
235 Node* previousSiblingSlow(const Node* node)
236 {
237     ASSERT(!node->isShadowRoot());
238
239     return traversePreviousSibling(node);
240 }
241
242 Node* 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
256 Node* 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
268 Node* parentInScope(const Node* node)
269 {
270     ASSERT(!isActiveInsertionPoint(node));
271
272     return traverseParent(node, DontCrossShadowRoot);
273 }
274
275 Node* lastChildInScope(const Node* node)
276 {
277     ASSERT(!isActiveInsertionPoint(node));
278
279     return traverseLastChild(node, DontCrossShadowRoot);
280 }
281
282 }
283
284 } // namespace