1/*
2 * Copyright (C) 2012 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Neither the name of Google Inc. nor the names of its
11 * contributors may be used to endorse or promote products derived from
12 * this software without specific prior written permission.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "config.h"
28#include "ReifiedTreeWalker.h"
29
30#include "Element.h"
31#include "HTMLContentSelector.h"
32#include "InsertionPoint.h"
33#include "ShadowTree.h"
34
35namespace WebCore {
36
37static inline bool isShadowHost(const Node* node)
38{
39 return node && node->isElementNode() && toElement(node)->hasShadowRoot();
40}
41
42static inline ShadowTree* shadowTreeFor(const Node* node)
43{
44 if (node && node->isElementNode())
45 return toElement(node)->shadowTree();
46 return 0;
47}
48
49static inline ShadowTree* shadowTreeOfParent(const Node* node)
50{
51 if (node && node->parentNode())
52 return shadowTreeFor(node->parentNode());
53 return 0;
54}
55
56void ReifiedTreeWalker::firstChild()
57{
58 ASSERT(m_node);
59 m_node = traverseChild(m_node, TraversalDirectionForward);
60 ASSERT(!m_node || !m_node->isShadowRoot());
61}
62
63Node* ReifiedTreeWalker::traverseFirstChild(const Node* node) const
64{
65 ASSERT(node);
66 return traverseChild(node, TraversalDirectionForward);
67}
68
69void ReifiedTreeWalker::lastChild()
70{
71 ASSERT(m_node);
72 m_node = traverseLastChild(m_node);
73 ASSERT(!m_node || !m_node->isShadowRoot());
74}
75
76Node* ReifiedTreeWalker::traverseLastChild(const Node* node) const
77{
78 ASSERT(node);
79 return traverseChild(node, TraversalDirectionBackward);
80}
81
82Node* ReifiedTreeWalker::traverseChild(const Node* node, TraversalDirection direction) const
83{
84 ASSERT(node);
85 // FIXME: Add an assertion once InsertionPoint have isActive() function.
86 // https://bugs.webkit.org/show_bug.cgi?id=82010
87 // ASSERT(!isInsertionPoint(node) || !toInsertionPoint(node)->isActive());
88 ASSERT(!node->isShadowRoot());
89 if (canCrossUpperBoundary()) {
90 ShadowTree* shadowTree = shadowTreeFor(node);
91 if (shadowTree && shadowTree->hasShadowRoot())
92 return traverseLightChildren(shadowTree->youngestShadowRoot(), direction);
93 return traverseLightChildren(node, direction);
94 }
95 if (isShadowHost(node))
96 return 0;
97 return traverseLightChildren(node, direction);
98}
99
100Node* ReifiedTreeWalker::traverseLightChildren(const Node* node, TraversalDirection direction)
101{
102 ASSERT(node);
103 if (Node* child = (direction == TraversalDirectionForward ? node->firstChild() : node->lastChild()))
104 return traverseNode(child, direction);
105 return 0;
106}
107
108Node* ReifiedTreeWalker::traverseNode(const Node* node, TraversalDirection direction)
109{
110 ASSERT(node);
111 if (isInsertionPoint(node)) {
112 const HTMLContentSelectionList* selectionList = toInsertionPoint(node)->selections();
113 if (HTMLContentSelection* selection = (direction == TraversalDirectionForward ? selectionList->first() : selectionList->last()))
114 return traverseNode(selection->node(), direction);
115 return traverseLightChildren(node, direction);
116 }
117 return const_cast<Node*>(node);
118}
119
120void ReifiedTreeWalker::nextSibling()
121{
122 ASSERT(m_node);
123 ASSERT(!m_node->isShadowRoot());
124 m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionForward);
125 ASSERT(!m_node || !m_nodet->isShadowRoot());
126}
127
128void ReifiedTreeWalker::previousSibling()
129{
130 ASSERT(m_node);
131 ASSERT(!m_node->isShadowRoot());
132 m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionBackward);
133 ASSERT(!m_node || !m_node->isShadowRoot());
134}
135
136Node* ReifiedTreeWalker::traverseSiblingOrBackToInsertionPoint(const Node* node, TraversalDirection direction)
137{
138 ASSERT(node);
139 ShadowTree* shadowTree = shadowTreeOfParent(node);
140 if (!shadowTree)
141 return traverseSiblingInCurrentTree(node, direction);
142 HTMLContentSelection* selection = shadowTree->selectionFor(node);
143 if (!selection)
144 return traverseSiblingInCurrentTree(node, direction);
145 if (HTMLContentSelection* nextSelection = (direction == TraversalDirectionForward ? selection->next() : selection->previous()))
146 return traverseNode(nextSelection->node(), direction);
147 return traverseSiblingOrBackToInsertionPoint(selection->insertionPoint(), direction);
148}
149
150Node* ReifiedTreeWalker::traverseSiblingInCurrentTree(const Node* node, TraversalDirection direction)
151{
152 ASSERT(node);
153 if (Node* next = (direction == TraversalDirectionForward ? node->nextSibling() : node->previousSibling()))
154 return traverseNode(next, direction);
155 if (Node* next = traverseSiblingOrBackToYoungerShadowRoot(node, direction))
156 return next;
157 return escapeFallbackContentElement(node, direction);
158}
159
160Node* ReifiedTreeWalker::traverseSiblingOrBackToYoungerShadowRoot(const Node* node, TraversalDirection direction)
161{
162 ASSERT(node);
163 if (node->parentNode() && node->parentNode()->isShadowRoot()) {
164 ShadowRoot* parentShadowRoot = toShadowRoot(node->parentNode());
165 if (!parentShadowRoot->isYoungest()) {
166 InsertionPoint* assignedInsertionPoint = parentShadowRoot->assignedTo();
167 ASSERT(assignedInsertionPoint);
168 return traverseSiblingInCurrentTree(assignedInsertionPoint, direction);
169 }
170 }
171 return 0;
172}
173
174Node* ReifiedTreeWalker::escapeFallbackContentElement(const Node* node, TraversalDirection direction)
175{
176 ASSERT(node);
177 if (node->parentNode() && isInsertionPoint(node->parentNode()))
178 return traverseSiblingOrBackToInsertionPoint(node->parentNode(), direction);
179 return 0;
180}
181
182Node* ReifiedTreeWalker::traverseNodeEscapingFallbackContents(const Node* node) const
183{
184 ASSERT(node);
185 if (isInsertionPoint(node))
186 return traverseParentNodeOrBackToInsertionPoint(node);
187 return const_cast<Node*>(node);
188}
189
190void ReifiedTreeWalker::parentNode()
191{
192 ASSERT(m_node);
193 ASSERT(!m_node->isShadowRoot());
194 // FIXME: Add an assertion once InsertionPoint have isActive() function.
195 // https://bugs.webkit.org/show_bug.cgi?id=82010
196 // ASSERT(!isInsertionPoint(node) || !toInsertionPoint(node)->isActive());
197 m_node = traverseParentNode(m_node);
198}
199
200Node* ReifiedTreeWalker::traverseParentNode(const Node* node) const
201{
202 if (ShadowTree* shadowTree = shadowTreeOfParent(node)) {
203 if (HTMLContentSelection* selection = shadowTree->selectionFor(node))
204 return traverseParentNode(selection->insertionPoint());
205 }
206 return traverseParentNodeInCurrentTree(node);
207}
208
209Node* ReifiedTreeWalker::traverseParentNodeInCurrentTree(const Node* node) const
210{
211 if (Node* parent = node->parentNode()) {
212 if (parent->isShadowRoot())
213 return traverseParentNodeBackToYoungerShadowRootOrHost(toShadowRoot(parent));
214 return traverseNodeEscapingFallbackContents(parent);
215 }
216 return 0;
217}
218
219Node* ReifiedTreeWalker::traverseParentNodeBackToYoungerShadowRootOrHost(const ShadowRoot* shadowRoot) const
220{
221 ASSERT(shadowRoot);
222 if (shadowRoot->isYoungest()) {
223 if (canCrossUpperBoundary())
224 return shadowRoot->host();
225 return 0;
226 }
227 InsertionPoint* assignedInsertionPoint = shadowRoot->assignedTo();
228 ASSERT(assignedInsertionPoint);
229 return traverseParentNodeOrBackToInsertionPoint(assignedInsertionPoint);
230}
231
232void ReifiedTreeWalker::adjustedParentNode()
233{
234 ASSERT(m_node);
235 if (ShadowTree* shadowTree = shadowTreeOfParent(m_node)) {
236 if (HTMLContentSelection* selection = shadowTree->selectionFor(m_node)) {
237 m_node = selection->insertionPoint();
238 return;
239 }
240 }
241 if (!m_node->isShadowRoot()) {
242 m_node = m_node->parentNode();
243 return;
244 }
245 const ShadowRoot* shadowRoot = toShadowRoot(m_node);
246 if (!shadowRoot->isYoungest()) {
247 ASSERT(shadowRoot->assignedTo());
248 m_node = shadowRoot->assignedTo();
249 return;
250 }
251 if (canCrossUpperBoundary())
252 m_node = shadowRoot->host();
253 else
254 m_node = 0;
255}
256
257Node* ReifiedTreeWalker::traverseNextSibling(const Node* node)
258{
259 ASSERT(node);
260 return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
261}
262
263Node* ReifiedTreeWalker::traversePreviousSibling(const Node* node)
264{
265 ASSERT(node);
266 return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
267}
268
269void ReifiedTreeWalker::nextNode()
270{
271 if (Node* next = traverseFirstChild(m_node)) {
272 m_node = next;
273 return;
274 }
275 if (Node* next = traverseNextSibling(m_node)) {
276 m_node = next;
277 return;
278 }
279 const Node* n = m_node;
280 while (n && !traverseNextSibling(n))
281 n = traverseParentNode(n);
282 if (n) {
283 m_node = traverseNextSibling(n);
284 return;
285 }
286 m_node = 0;
287}
288
289void ReifiedTreeWalker::previousNode()
290{
291 if (Node* n = traversePreviousSibling(m_node)) {
292 while (Node* child = traverseLastChild(n))
293 n = child;
294 m_node = n;
295 return;
296 }
297 parentNode();
298}
299
300} // namespace