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 #ifndef ComposedTreeWalker_h
28 #define ComposedTreeWalker_h
29
30 #include "core/dom/NodeRenderingTraversal.h"
31 #include "core/dom/shadow/InsertionPoint.h"
32 #include "core/dom/shadow/ShadowRoot.h"
33
34 namespace WebCore {
35
36 class Node;
37 class ShadowRoot;
38
39 // FIXME: Make some functions inline to optimise the performance.
40 // https://bugs.webkit.org/show_bug.cgi?id=82702
41 class ComposedTreeWalker {
42 public:
43 typedef NodeRenderingTraversal::ParentDetails ParentTraversalDetails;
44
45 enum StartPolicy {
46 CanStartFromShadowBoundary,
47 CannotStartFromShadowBoundary
48 };
49
50 ComposedTreeWalker(const Node*, StartPolicy = CannotStartFromShadowBoundary);
51
get()52 Node* get() const { return const_cast<Node*>(m_node); }
53
54 void firstChild();
55 void lastChild();
56
57 void nextSibling();
58 void previousSibling();
59
60 void parent();
61
62 void next();
63 void previous();
64
65 Node* traverseParent(const Node*, ParentTraversalDetails* = 0) const;
66
67 private:
68 ComposedTreeWalker(const Node*, ParentTraversalDetails*);
69
70 enum TraversalDirection {
71 TraversalDirectionForward,
72 TraversalDirectionBackward
73 };
74
assertPrecondition()75 void assertPrecondition() const
76 {
77 #ifndef NDEBUG
78 ASSERT(m_node);
79 ASSERT(!m_node->isShadowRoot());
80 ASSERT(!isActiveInsertionPoint(*m_node));
81 #endif
82 }
83
assertPostcondition()84 void assertPostcondition() const
85 {
86 #ifndef NDEBUG
87 if (m_node)
88 assertPrecondition();
89 #endif
90 }
91
92 static Node* traverseNode(const Node*, TraversalDirection);
93 static Node* traverseLightChildren(const Node*, TraversalDirection);
94
95 Node* traverseFirstChild(const Node*) const;
96 Node* traverseLastChild(const Node*) const;
97 Node* traverseChild(const Node*, TraversalDirection) const;
98
99 static Node* traverseNextSibling(const Node*);
100 static Node* traversePreviousSibling(const Node*);
101
102 static Node* traverseSiblingOrBackToInsertionPoint(const Node*, TraversalDirection);
103 static Node* traverseSiblingInCurrentTree(const Node*, TraversalDirection);
104
105 static Node* traverseSiblings(const Node*, TraversalDirection);
106 static Node* traverseDistributedNodes(const Node*, const InsertionPoint*, TraversalDirection);
107
108 static Node* traverseBackToYoungerShadowRoot(const Node*, TraversalDirection);
109
110 Node* traverseParentOrHost(const Node*, ParentTraversalDetails* = 0) const;
111
112 const Node* m_node;
113 };
114
ComposedTreeWalker(const Node * node,StartPolicy startPolicy)115 inline ComposedTreeWalker::ComposedTreeWalker(const Node* node, StartPolicy startPolicy)
116 : m_node(node)
117 {
118 #ifndef NDEBUG
119 if (m_node && startPolicy == CannotStartFromShadowBoundary)
120 assertPrecondition();
121 #endif
122 }
123
parent()124 inline void ComposedTreeWalker::parent()
125 {
126 assertPrecondition();
127 m_node = traverseParent(m_node);
128 assertPostcondition();
129 }
130
nextSibling()131 inline void ComposedTreeWalker::nextSibling()
132 {
133 assertPrecondition();
134 m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionForward);
135 assertPostcondition();
136 }
137
previousSibling()138 inline void ComposedTreeWalker::previousSibling()
139 {
140 assertPrecondition();
141 m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionBackward);
142 assertPostcondition();
143 }
144
next()145 inline void ComposedTreeWalker::next()
146 {
147 assertPrecondition();
148 if (Node* next = traverseFirstChild(m_node)) {
149 m_node = next;
150 } else {
151 while (m_node) {
152 if (Node* sibling = traverseNextSibling(m_node)) {
153 m_node = sibling;
154 break;
155 }
156 m_node = traverseParent(m_node);
157 }
158 }
159 assertPostcondition();
160 }
161
previous()162 inline void ComposedTreeWalker::previous()
163 {
164 assertPrecondition();
165 if (Node* previous = traversePreviousSibling(m_node)) {
166 while (Node* child = traverseLastChild(previous))
167 previous = child;
168 m_node = previous;
169 } else {
170 parent();
171 }
172 assertPostcondition();
173 }
174
firstChild()175 inline void ComposedTreeWalker::firstChild()
176 {
177 assertPrecondition();
178 m_node = traverseChild(m_node, TraversalDirectionForward);
179 assertPostcondition();
180 }
181
lastChild()182 inline void ComposedTreeWalker::lastChild()
183 {
184 assertPrecondition();
185 m_node = traverseLastChild(m_node);
186 assertPostcondition();
187 }
188
traverseNextSibling(const Node * node)189 inline Node* ComposedTreeWalker::traverseNextSibling(const Node* node)
190 {
191 ASSERT(node);
192 return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
193 }
194
traversePreviousSibling(const Node * node)195 inline Node* ComposedTreeWalker::traversePreviousSibling(const Node* node)
196 {
197 ASSERT(node);
198 return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
199 }
200
traverseFirstChild(const Node * node)201 inline Node* ComposedTreeWalker::traverseFirstChild(const Node* node) const
202 {
203 ASSERT(node);
204 return traverseChild(node, TraversalDirectionForward);
205 }
206
traverseLastChild(const Node * node)207 inline Node* ComposedTreeWalker::traverseLastChild(const Node* node) const
208 {
209 ASSERT(node);
210 return traverseChild(node, TraversalDirectionBackward);
211 }
212
213 } // namespace
214
215 #endif
216