1 /*
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3 * (C) 1999 Antti Koivisto (koivisto@kde.org)
4 * (C) 2001 Dirk Mueller (mueller@kde.org)
5 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
6 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
7 * Copyright (C) 2014 Samsung Electronics. All rights reserved.
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Library General Public
11 * License as published by the Free Software Foundation; either
12 * version 2 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Library General Public License for more details.
18 *
19 * You should have received a copy of the GNU Library General Public License
20 * along with this library; see the file COPYING.LIB. If not, write to
21 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22 * Boston, MA 02110-1301, USA.
23 *
24 */
25
26 #ifndef ElementTraversal_h
27 #define ElementTraversal_h
28
29 #include "core/dom/Element.h"
30 #include "core/dom/NodeTraversal.h"
31
32 namespace blink {
33
34 template <class ElementType>
35 class Traversal {
36 public:
37 // First or last ElementType child of the node.
firstChild(const ContainerNode & current)38 static ElementType* firstChild(const ContainerNode& current) { return firstChildTemplate(current); }
firstChild(const Node & current)39 static ElementType* firstChild(const Node& current) { return firstChildTemplate(current); }
40 template <class MatchFunc>
41 static ElementType* firstChild(const ContainerNode&, MatchFunc);
lastChild(const ContainerNode & current)42 static ElementType* lastChild(const ContainerNode& current) { return lastChildTemplate(current); }
lastChild(const Node & current)43 static ElementType* lastChild(const Node& current) { return lastChildTemplate(current); }
44 template <class MatchFunc>
45 static ElementType* lastChild(const ContainerNode&, MatchFunc);
46
47 // First ElementType ancestor of the node.
48 static ElementType* firstAncestor(const Node& current);
firstAncestorOrSelf(Node & current)49 static ElementType* firstAncestorOrSelf(Node& current) { return firstAncestorOrSelfTemplate(current); }
firstAncestorOrSelf(Element & current)50 static ElementType* firstAncestorOrSelf(Element& current) { return firstAncestorOrSelfTemplate(current); }
firstAncestorOrSelf(const Node & current)51 static const ElementType* firstAncestorOrSelf(const Node& current) { return firstAncestorOrSelfTemplate(const_cast<Node&>(current)); }
firstAncestorOrSelf(const Element & current)52 static const ElementType* firstAncestorOrSelf(const Element& current) { return firstAncestorOrSelfTemplate(const_cast<Element&>(current)); }
53
54 // First or last ElementType descendant of the node.
55 // For Elements firstWithin() is always the same as firstChild().
firstWithin(const ContainerNode & current)56 static ElementType* firstWithin(const ContainerNode& current) { return firstWithinTemplate(current); }
firstWithin(const Node & current)57 static ElementType* firstWithin(const Node& current) { return firstWithinTemplate(current); }
58 template <typename MatchFunc>
59 static ElementType* firstWithin(const ContainerNode&, MatchFunc);
lastWithin(const ContainerNode & current)60 static ElementType* lastWithin(const ContainerNode& current) { return lastWithinTemplate(current); }
lastWithin(const Node & current)61 static ElementType* lastWithin(const Node& current) { return lastWithinTemplate(current); }
62 template <class MatchFunc>
63 static ElementType* lastWithin(const ContainerNode&, MatchFunc);
64
65 // Pre-order traversal skipping non-element nodes.
next(const ContainerNode & current)66 static ElementType* next(const ContainerNode& current) { return nextTemplate(current); }
next(const Node & current)67 static ElementType* next(const Node& current) { return nextTemplate(current); }
next(const ContainerNode & current,const Node * stayWithin)68 static ElementType* next(const ContainerNode& current, const Node* stayWithin) { return nextTemplate(current, stayWithin); }
next(const Node & current,const Node * stayWithin)69 static ElementType* next(const Node& current, const Node* stayWithin) { return nextTemplate(current, stayWithin); }
70 template <class MatchFunc>
71 static ElementType* next(const ContainerNode& current, const Node* stayWithin, MatchFunc);
72 static ElementType* previous(const Node&);
73 static ElementType* previous(const Node&, const Node* stayWithin);
74 template <class MatchFunc>
75 static ElementType* previous(const ContainerNode& current, const Node* stayWithin, MatchFunc);
76
77 // Like next, but skips children.
78 static ElementType* nextSkippingChildren(const Node&);
79 static ElementType* nextSkippingChildren(const Node&, const Node* stayWithin);
80
81 // Pre-order traversal including the pseudo-elements.
82 static ElementType* previousIncludingPseudo(const Node&, const Node* stayWithin = 0);
83 static ElementType* nextIncludingPseudo(const Node&, const Node* stayWithin = 0);
84 static ElementType* nextIncludingPseudoSkippingChildren(const Node&, const Node* stayWithin = 0);
85
86 // Utility function to traverse only the element and pseudo-element siblings of a node.
87 static ElementType* pseudoAwarePreviousSibling(const Node&);
88
89 // Previous / Next sibling.
90 static ElementType* previousSibling(const Node&);
91 template <class MatchFunc>
92 static ElementType* previousSibling(const Node&, MatchFunc);
93 static ElementType* nextSibling(const Node&);
94 template <class MatchFunc>
95 static ElementType* nextSibling(const Node&, MatchFunc);
96
97 private:
98 template <class NodeType>
99 static ElementType* firstChildTemplate(NodeType&);
100 template <class NodeType>
101 static ElementType* lastChildTemplate(NodeType&);
102 template <class NodeType>
103 static ElementType* firstAncestorOrSelfTemplate(NodeType&);
104 template <class NodeType>
105 static ElementType* firstWithinTemplate(NodeType&);
106 template <class NodeType>
107 static ElementType* lastWithinTemplate(NodeType&);
108 template <class NodeType>
109 static ElementType* nextTemplate(NodeType&);
110 template <class NodeType>
111 static ElementType* nextTemplate(NodeType&, const Node* stayWithin);
112 };
113
114 typedef Traversal<Element> ElementTraversal;
115
116 // Specialized for pure Element to exploit the fact that Elements parent is always either another Element or the root.
117 template <>
118 template <class NodeType>
firstWithinTemplate(NodeType & current)119 inline Element* Traversal<Element>::firstWithinTemplate(NodeType& current)
120 {
121 return firstChildTemplate(current);
122 }
123
124 template <>
125 template <class NodeType>
nextTemplate(NodeType & current)126 inline Element* Traversal<Element>::nextTemplate(NodeType& current)
127 {
128 Node* node = NodeTraversal::next(current);
129 while (node && !node->isElementNode())
130 node = NodeTraversal::nextSkippingChildren(*node);
131 return toElement(node);
132 }
133
134 template <>
135 template <class NodeType>
nextTemplate(NodeType & current,const Node * stayWithin)136 inline Element* Traversal<Element>::nextTemplate(NodeType& current, const Node* stayWithin)
137 {
138 Node* node = NodeTraversal::next(current, stayWithin);
139 while (node && !node->isElementNode())
140 node = NodeTraversal::nextSkippingChildren(*node, stayWithin);
141 return toElement(node);
142 }
143
144 // Generic versions.
145 template <class ElementType>
146 template <class NodeType>
firstChildTemplate(NodeType & current)147 inline ElementType* Traversal<ElementType>::firstChildTemplate(NodeType& current)
148 {
149 Node* node = current.firstChild();
150 while (node && !isElementOfType<const ElementType>(*node))
151 node = node->nextSibling();
152 return toElement<ElementType>(node);
153 }
154
155 template <class ElementType>
156 template <class MatchFunc>
firstChild(const ContainerNode & current,MatchFunc isMatch)157 inline ElementType* Traversal<ElementType>::firstChild(const ContainerNode& current, MatchFunc isMatch)
158 {
159 ElementType* element = Traversal<ElementType>::firstChild(current);
160 while (element && !isMatch(*element))
161 element = Traversal<ElementType>::nextSibling(*element);
162 return element;
163 }
164
165 template <class ElementType>
firstAncestor(const Node & current)166 inline ElementType* Traversal<ElementType>::firstAncestor(const Node& current)
167 {
168 ContainerNode* ancestor = current.parentNode();
169 while (ancestor && !isElementOfType<const ElementType>(*ancestor))
170 ancestor = ancestor->parentNode();
171 return toElement<ElementType>(ancestor);
172 }
173
174 template <class ElementType>
175 template <class NodeType>
firstAncestorOrSelfTemplate(NodeType & current)176 inline ElementType* Traversal<ElementType>::firstAncestorOrSelfTemplate(NodeType& current)
177 {
178 if (isElementOfType<const ElementType>(current))
179 return &toElement<ElementType>(current);
180 return firstAncestor(current);
181 }
182
183 template <class ElementType>
184 template <class NodeType>
lastChildTemplate(NodeType & current)185 inline ElementType* Traversal<ElementType>::lastChildTemplate(NodeType& current)
186 {
187 Node* node = current.lastChild();
188 while (node && !isElementOfType<const ElementType>(*node))
189 node = node->previousSibling();
190 return toElement<ElementType>(node);
191 }
192
193 template <class ElementType>
194 template <class MatchFunc>
lastChild(const ContainerNode & current,MatchFunc isMatch)195 inline ElementType* Traversal<ElementType>::lastChild(const ContainerNode& current, MatchFunc isMatch)
196 {
197 ElementType* element = Traversal<ElementType>::lastChild(current);
198 while (element && !isMatch(*element))
199 element = Traversal<ElementType>::previousSibling(*element);
200 return element;
201 }
202
203 template <class ElementType>
204 template <class NodeType>
firstWithinTemplate(NodeType & current)205 inline ElementType* Traversal<ElementType>::firstWithinTemplate(NodeType& current)
206 {
207 Node* node = current.firstChild();
208 while (node && !isElementOfType<const ElementType>(*node))
209 node = NodeTraversal::next(*node, ¤t);
210 return toElement<ElementType>(node);
211 }
212
213 template <class ElementType>
214 template <typename MatchFunc>
firstWithin(const ContainerNode & current,MatchFunc isMatch)215 inline ElementType* Traversal<ElementType>::firstWithin(const ContainerNode& current, MatchFunc isMatch)
216 {
217 ElementType* element = Traversal<ElementType>::firstWithin(current);
218 while (element && !isMatch(*element))
219 element = Traversal<ElementType>::next(*element, ¤t, isMatch);
220 return element;
221 }
222
223 template <class ElementType>
224 template <class NodeType>
lastWithinTemplate(NodeType & current)225 inline ElementType* Traversal<ElementType>::lastWithinTemplate(NodeType& current)
226 {
227 Node* node = NodeTraversal::lastWithin(current);
228 while (node && !isElementOfType<const ElementType>(*node))
229 node = NodeTraversal::previous(*node, ¤t);
230 return toElement<ElementType>(node);
231 }
232
233 template <class ElementType>
234 template <class MatchFunc>
lastWithin(const ContainerNode & current,MatchFunc isMatch)235 inline ElementType* Traversal<ElementType>::lastWithin(const ContainerNode& current, MatchFunc isMatch)
236 {
237 ElementType* element = Traversal<ElementType>::lastWithin(current);
238 while (element && !isMatch(*element))
239 element = Traversal<ElementType>::previous(*element, ¤t, isMatch);
240 return element;
241 }
242
243 template <class ElementType>
244 template <class NodeType>
nextTemplate(NodeType & current)245 inline ElementType* Traversal<ElementType>::nextTemplate(NodeType& current)
246 {
247 Node* node = NodeTraversal::next(current);
248 while (node && !isElementOfType<const ElementType>(*node))
249 node = NodeTraversal::next(*node);
250 return toElement<ElementType>(node);
251 }
252
253 template <class ElementType>
254 template <class NodeType>
nextTemplate(NodeType & current,const Node * stayWithin)255 inline ElementType* Traversal<ElementType>::nextTemplate(NodeType& current, const Node* stayWithin)
256 {
257 Node* node = NodeTraversal::next(current, stayWithin);
258 while (node && !isElementOfType<const ElementType>(*node))
259 node = NodeTraversal::next(*node, stayWithin);
260 return toElement<ElementType>(node);
261 }
262
263 template <class ElementType>
264 template <class MatchFunc>
next(const ContainerNode & current,const Node * stayWithin,MatchFunc isMatch)265 inline ElementType* Traversal<ElementType>::next(const ContainerNode& current, const Node* stayWithin, MatchFunc isMatch)
266 {
267 ElementType* element = Traversal<ElementType>::next(current, stayWithin);
268 while (element && !isMatch(*element))
269 element = Traversal<ElementType>::next(*element, stayWithin);
270 return element;
271 }
272
273 template <class ElementType>
previous(const Node & current)274 inline ElementType* Traversal<ElementType>::previous(const Node& current)
275 {
276 Node* node = NodeTraversal::previous(current);
277 while (node && !isElementOfType<const ElementType>(*node))
278 node = NodeTraversal::previous(*node);
279 return toElement<ElementType>(node);
280 }
281
282 template <class ElementType>
previous(const Node & current,const Node * stayWithin)283 inline ElementType* Traversal<ElementType>::previous(const Node& current, const Node* stayWithin)
284 {
285 Node* node = NodeTraversal::previous(current, stayWithin);
286 while (node && !isElementOfType<const ElementType>(*node))
287 node = NodeTraversal::previous(*node, stayWithin);
288 return toElement<ElementType>(node);
289 }
290
291 template <class ElementType>
292 template <class MatchFunc>
previous(const ContainerNode & current,const Node * stayWithin,MatchFunc isMatch)293 inline ElementType* Traversal<ElementType>::previous(const ContainerNode& current, const Node* stayWithin, MatchFunc isMatch)
294 {
295 ElementType* element = Traversal<ElementType>::previous(current, stayWithin);
296 while (element && !isMatch(*element))
297 element = Traversal<ElementType>::previous(*element, stayWithin);
298 return element;
299 }
300
301 template <class ElementType>
nextSkippingChildren(const Node & current)302 inline ElementType* Traversal<ElementType>::nextSkippingChildren(const Node& current)
303 {
304 Node* node = NodeTraversal::nextSkippingChildren(current);
305 while (node && !isElementOfType<const ElementType>(*node))
306 node = NodeTraversal::nextSkippingChildren(*node);
307 return toElement<ElementType>(node);
308 }
309
310 template <class ElementType>
nextSkippingChildren(const Node & current,const Node * stayWithin)311 inline ElementType* Traversal<ElementType>::nextSkippingChildren(const Node& current, const Node* stayWithin)
312 {
313 Node* node = NodeTraversal::nextSkippingChildren(current, stayWithin);
314 while (node && !isElementOfType<const ElementType>(*node))
315 node = NodeTraversal::nextSkippingChildren(*node, stayWithin);
316 return toElement<ElementType>(node);
317 }
318
319 template <class ElementType>
previousIncludingPseudo(const Node & current,const Node * stayWithin)320 inline ElementType* Traversal<ElementType>::previousIncludingPseudo(const Node& current, const Node* stayWithin)
321 {
322 Node* node = NodeTraversal::previousIncludingPseudo(current, stayWithin);
323 while (node && !isElementOfType<const ElementType>(*node))
324 node = NodeTraversal::previousIncludingPseudo(*node, stayWithin);
325 return toElement<ElementType>(node);
326 }
327
328 template <class ElementType>
nextIncludingPseudo(const Node & current,const Node * stayWithin)329 inline ElementType* Traversal<ElementType>::nextIncludingPseudo(const Node& current, const Node* stayWithin)
330 {
331 Node* node = NodeTraversal::nextIncludingPseudo(current, stayWithin);
332 while (node && !isElementOfType<const ElementType>(*node))
333 node = NodeTraversal::nextIncludingPseudo(*node, stayWithin);
334 return toElement<ElementType>(node);
335 }
336
337 template <class ElementType>
nextIncludingPseudoSkippingChildren(const Node & current,const Node * stayWithin)338 inline ElementType* Traversal<ElementType>::nextIncludingPseudoSkippingChildren(const Node& current, const Node* stayWithin)
339 {
340 Node* node = NodeTraversal::nextIncludingPseudoSkippingChildren(current, stayWithin);
341 while (node && !isElementOfType<const ElementType>(*node))
342 node = NodeTraversal::nextIncludingPseudoSkippingChildren(*node, stayWithin);
343 return toElement<ElementType>(node);
344 }
345
346 template <class ElementType>
pseudoAwarePreviousSibling(const Node & current)347 inline ElementType* Traversal<ElementType>::pseudoAwarePreviousSibling(const Node& current)
348 {
349 Node* node = current.pseudoAwarePreviousSibling();
350 while (node && !isElementOfType<const ElementType>(*node))
351 node = node->pseudoAwarePreviousSibling();
352 return toElement<ElementType>(node);
353 }
354
355 template <class ElementType>
previousSibling(const Node & current)356 inline ElementType* Traversal<ElementType>::previousSibling(const Node& current)
357 {
358 Node* node = current.previousSibling();
359 while (node && !isElementOfType<const ElementType>(*node))
360 node = node->previousSibling();
361 return toElement<ElementType>(node);
362 }
363
364 template <class ElementType>
365 template <class MatchFunc>
previousSibling(const Node & current,MatchFunc isMatch)366 inline ElementType* Traversal<ElementType>::previousSibling(const Node& current, MatchFunc isMatch)
367 {
368 ElementType* element = Traversal<ElementType>::previousSibling(current);
369 while (element && !isMatch(*element))
370 element = Traversal<ElementType>::previousSibling(*element);
371 return element;
372 }
373
374 template <class ElementType>
nextSibling(const Node & current)375 inline ElementType* Traversal<ElementType>::nextSibling(const Node& current)
376 {
377 Node* node = current.nextSibling();
378 while (node && !isElementOfType<const ElementType>(*node))
379 node = node->nextSibling();
380 return toElement<ElementType>(node);
381 }
382
383 template <class ElementType>
384 template <class MatchFunc>
nextSibling(const Node & current,MatchFunc isMatch)385 inline ElementType* Traversal<ElementType>::nextSibling(const Node& current, MatchFunc isMatch)
386 {
387 ElementType* element = Traversal<ElementType>::nextSibling(current);
388 while (element && !isMatch(*element))
389 element = Traversal<ElementType>::nextSibling(*element);
390 return element;
391 }
392
393 } // namespace blink
394
395 #endif
396