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 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.
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.
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.
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.
26 #ifndef NodeTraversal_h
27 #define NodeTraversal_h
29 #include "core/dom/ContainerNode.h"
30 #include "core/dom/Node.h"
34 template <class Iterator> class TraversalRange;
35 template <class TraversalNext> class TraversalChildrenIterator;
36 template <class TraversalNext> class TraversalDescendantIterator;
37 template <class TraversalNext> class TraversalInclusiveDescendantIterator;
38 template <class TraversalNext> class TraversalNextIterator;
42 using TraversalNodeType = Node;
43 // Does a pre-order traversal of the tree to find the next node after this one.
44 // This uses the same order that tags appear in the source file. If the stayWithin
45 // argument is non-null, the traversal will stop once the specified node is reached.
46 // This can be used to restrict traversal to a particular sub-tree.
47 static Node* next(const Node& current) { return traverseNextTemplate(current); }
48 static Node* next(const ContainerNode& current) { return traverseNextTemplate(current); }
49 static Node* next(const Node& current, const Node* stayWithin) { return traverseNextTemplate(current, stayWithin); }
50 static Node* next(const ContainerNode& current, const Node* stayWithin) { return traverseNextTemplate(current, stayWithin); }
52 // Like next, but skips children and starts with the next sibling.
53 static Node* nextSkippingChildren(const Node&);
54 static Node* nextSkippingChildren(const Node&, const Node* stayWithin);
56 static Node* firstWithin(const Node& current) { return current.firstChild(); }
58 static Node* lastWithin(const ContainerNode&);
59 static Node& lastWithinOrSelf(Node&);
61 // Does a reverse pre-order traversal to find the node that comes before the current one in document order
62 static Node* previous(const Node&, const Node* stayWithin = 0);
64 // Like previous, but skips children and starts with the next sibling.
65 static Node* previousSkippingChildren(const Node&, const Node* stayWithin = 0);
67 // Like next, but visits parents after their children.
68 static Node* nextPostOrder(const Node&, const Node* stayWithin = 0);
70 // Like previous, but visits parents before their children.
71 static Node* previousPostOrder(const Node&, const Node* stayWithin = 0);
73 // Pre-order traversal including the pseudo-elements.
74 static Node* previousIncludingPseudo(const Node&, const Node* stayWithin = 0);
75 static Node* nextIncludingPseudo(const Node&, const Node* stayWithin = 0);
76 static Node* nextIncludingPseudoSkippingChildren(const Node&, const Node* stayWithin = 0);
78 static Node* nextAncestorSibling(const Node&);
79 static Node* nextAncestorSibling(const Node&, const Node* stayWithin);
80 static Node& highestAncestorOrSelf(Node&);
82 // Children traversal.
83 static Node* childAt(const Node& parent, unsigned index) { return childAtTemplate(parent, index); }
84 static Node* childAt(const ContainerNode& parent, unsigned index) { return childAtTemplate(parent, index); }
86 static Node* nextSibling(const Node& node) { return node.nextSibling(); }
88 static TraversalRange<TraversalChildrenIterator<NodeTraversal>> childrenOf(const Node&);
89 static TraversalRange<TraversalDescendantIterator<NodeTraversal>> descendantsOf(const Node&);
90 static TraversalRange<TraversalInclusiveDescendantIterator<NodeTraversal>> inclusiveDescendantsOf(const Node&);
91 static TraversalRange<TraversalNextIterator<NodeTraversal>> startsAt(const Node*);
92 static TraversalRange<TraversalNextIterator<NodeTraversal>> startsAfter(const Node&);
95 template <class NodeType>
96 static Node* traverseNextTemplate(NodeType&);
97 template <class NodeType>
98 static Node* traverseNextTemplate(NodeType&, const Node* stayWithin);
99 template <class NodeType>
100 static Node* childAtTemplate(NodeType&, unsigned);
103 template <class Iterator>
104 class TraversalRange {
106 using StartNodeType = typename Iterator::StartNodeType;
107 explicit TraversalRange(const StartNodeType* start) : m_start(start) { }
108 Iterator begin() { return Iterator(m_start); }
109 Iterator end() { return Iterator::end(); }
111 const StartNodeType* m_start;
114 template <class TraversalNext>
115 class TraversalIteratorBase {
117 using NodeType = typename TraversalNext::TraversalNodeType;
118 NodeType& operator*() { return *m_current; }
119 bool operator!=(const TraversalIteratorBase& rval) const { return m_current != rval.m_current ; }
121 explicit TraversalIteratorBase(NodeType* current) : m_current(current) { };
125 template <class TraversalNext>
126 class TraversalChildrenIterator : public TraversalIteratorBase<TraversalNext> {
128 using StartNodeType = Node;
129 using TraversalIteratorBase<TraversalNext>::m_current;
130 explicit TraversalChildrenIterator(const StartNodeType* start) : TraversalIteratorBase<TraversalNext>(TraversalNext::firstWithin(*start)) { };
131 void operator++() { m_current = TraversalNext::nextSibling(*m_current); };
132 static TraversalChildrenIterator end() { return TraversalChildrenIterator(); };
134 TraversalChildrenIterator() : TraversalIteratorBase<TraversalNext>(nullptr) { };
137 template <class TraversalNext>
138 class TraversalNextIterator : public TraversalIteratorBase<TraversalNext> {
140 using StartNodeType = typename TraversalNext::TraversalNodeType;
141 using TraversalIteratorBase<TraversalNext>::m_current;
142 explicit TraversalNextIterator(const StartNodeType* start) : TraversalIteratorBase<TraversalNext>(const_cast<StartNodeType*>(start)) { };
143 void operator++() { m_current = TraversalNext::next(*m_current); }
144 static TraversalNextIterator end() { return TraversalNextIterator(nullptr); };
147 template <class TraversalNext>
148 class TraversalDescendantIterator : public TraversalIteratorBase<TraversalNext> {
150 using StartNodeType = Node;
151 using TraversalIteratorBase<TraversalNext>::m_current;
152 explicit TraversalDescendantIterator(const StartNodeType* start) : TraversalIteratorBase<TraversalNext>(TraversalNext::firstWithin(*start)), m_root(start) { };
153 void operator++() { m_current = TraversalNext::next(*m_current, m_root); }
154 static TraversalDescendantIterator end() { return TraversalDescendantIterator(); };
156 TraversalDescendantIterator() : TraversalIteratorBase<TraversalNext>(nullptr), m_root(nullptr) { };
160 template <class TraversalNext>
161 class TraversalInclusiveDescendantIterator : public TraversalIteratorBase<TraversalNext> {
163 using StartNodeType = typename TraversalNext::TraversalNodeType;
164 using NodeType = typename TraversalNext::TraversalNodeType;
165 using TraversalIteratorBase<TraversalNext>::m_current;
166 explicit TraversalInclusiveDescendantIterator(const StartNodeType* start) : TraversalIteratorBase<TraversalNext>(const_cast<NodeType*>(start)), m_root(start) { };
167 void operator++() { m_current = TraversalNext::next(*m_current, m_root); }
168 static TraversalInclusiveDescendantIterator end() { return TraversalInclusiveDescendantIterator(nullptr); };
170 const StartNodeType* m_root;
173 inline TraversalRange<TraversalChildrenIterator<NodeTraversal>> NodeTraversal::childrenOf(const Node& parent)
175 return TraversalRange<TraversalChildrenIterator<NodeTraversal>>(&parent);
178 inline TraversalRange<TraversalDescendantIterator<NodeTraversal>> NodeTraversal::descendantsOf(const Node& root)
180 return TraversalRange<TraversalDescendantIterator<NodeTraversal>>(&root);
183 inline TraversalRange<TraversalInclusiveDescendantIterator<NodeTraversal>> NodeTraversal::inclusiveDescendantsOf(const Node& root)
185 return TraversalRange<TraversalInclusiveDescendantIterator<NodeTraversal>>(&root);
188 inline TraversalRange<TraversalNextIterator<NodeTraversal>> NodeTraversal::startsAt(const Node* start)
190 return TraversalRange<TraversalNextIterator<NodeTraversal>>(start);
193 inline TraversalRange<TraversalNextIterator<NodeTraversal>> NodeTraversal::startsAfter(const Node& start)
195 return startsAt(NodeTraversal::next(start));
198 template <class NodeType>
199 inline Node* NodeTraversal::traverseNextTemplate(NodeType& current)
201 if (current.hasChildren())
202 return current.firstChild();
203 if (current.nextSibling())
204 return current.nextSibling();
205 return nextAncestorSibling(current);
208 template <class NodeType>
209 inline Node* NodeTraversal::traverseNextTemplate(NodeType& current, const Node* stayWithin)
211 if (current.hasChildren())
212 return current.firstChild();
213 if (current == stayWithin)
215 if (current.nextSibling())
216 return current.nextSibling();
217 return nextAncestorSibling(current, stayWithin);
220 inline Node* NodeTraversal::nextSkippingChildren(const Node& current)
222 if (current.nextSibling())
223 return current.nextSibling();
224 return nextAncestorSibling(current);
227 inline Node* NodeTraversal::nextSkippingChildren(const Node& current, const Node* stayWithin)
229 if (current == stayWithin)
231 if (current.nextSibling())
232 return current.nextSibling();
233 return nextAncestorSibling(current, stayWithin);
236 inline Node& NodeTraversal::highestAncestorOrSelf(Node& current)
238 Node* highest = ¤t;
239 while (highest->parentNode())
240 highest = highest->parentNode();
244 template <class NodeType>
245 inline Node* NodeTraversal::childAtTemplate(NodeType& parent, unsigned index)
247 Node* child = parent.firstChild();
248 while (child && index--)
249 child = child->nextSibling();