1/*
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3 * Copyright (C) 2000 Frederik Holljen (frederik.holljen@hig.no)
4 * Copyright (C) 2001 Peter Kelly (pmk@post.com)
5 * Copyright (C) 2006 Samuel Weinig (sam.weinig@gmail.com)
6 * Copyright (C) 2004, 2008 Apple Inc. All rights reserved.
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License as published by the Free Software Foundation; either
11 * version 2 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Library General Public License for more details.
17 *
18 * You should have received a copy of the GNU Library General Public License
19 * along with this library; see the file COPYING.LIB. If not, write to
20 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 * Boston, MA 02110-1301, USA.
22 *
23 */
24
25#include "config.h"
26#include "TreeWalker.h"
27
28#include "ContainerNode.h"
29#include "NodeTraversal.h"
30#include <wtf/IsoMallocInlines.h>
31
32namespace WebCore {
33
34WTF_MAKE_ISO_ALLOCATED_IMPL(TreeWalker);
35
36TreeWalker::TreeWalker(Node& rootNode, unsigned long whatToShow, RefPtr<NodeFilter>&& filter)
37 : NodeIteratorBase(rootNode, whatToShow, WTFMove(filter))
38 , m_current(root())
39{
40}
41
42void TreeWalker::setCurrentNode(Node& node)
43{
44 m_current = node;
45}
46
47inline Node* TreeWalker::setCurrent(Ref<Node>&& node)
48{
49 m_current = WTFMove(node);
50 return m_current.ptr();
51}
52
53ExceptionOr<Node*> TreeWalker::parentNode()
54{
55 RefPtr<Node> node = m_current.ptr();
56 while (node != &root()) {
57 node = node->parentNode();
58 if (!node)
59 return nullptr;
60
61 auto filterResult = acceptNode(*node);
62 if (filterResult.hasException())
63 return filterResult.releaseException();
64
65 if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
66 return setCurrent(node.releaseNonNull());
67 }
68 return nullptr;
69}
70
71ExceptionOr<Node*> TreeWalker::firstChild()
72{
73 for (RefPtr<Node> node = m_current->firstChild(); node; ) {
74 auto filterResult = acceptNode(*node);
75 if (filterResult.hasException())
76 return filterResult.releaseException();
77
78 switch (filterResult.returnValue()) {
79 case NodeFilter::FILTER_ACCEPT:
80 m_current = node.releaseNonNull();
81 return m_current.ptr();
82 case NodeFilter::FILTER_SKIP:
83 if (node->firstChild()) {
84 node = node->firstChild();
85 continue;
86 }
87 break;
88 case NodeFilter::FILTER_REJECT:
89 break;
90 }
91 do {
92 if (node->nextSibling()) {
93 node = node->nextSibling();
94 break;
95 }
96 ContainerNode* parent = node->parentNode();
97 if (!parent || parent == &root() || parent == m_current.ptr())
98 return nullptr;
99 node = parent;
100 } while (node);
101 }
102 return nullptr;
103}
104
105ExceptionOr<Node*> TreeWalker::lastChild()
106{
107 for (RefPtr<Node> node = m_current->lastChild(); node; ) {
108 auto filterResult = acceptNode(*node);
109 if (filterResult.hasException())
110 return filterResult.releaseException();
111
112 switch (filterResult.returnValue()) {
113 case NodeFilter::FILTER_ACCEPT:
114 m_current = node.releaseNonNull();
115 return m_current.ptr();
116 case NodeFilter::FILTER_SKIP:
117 if (node->lastChild()) {
118 node = node->lastChild();
119 continue;
120 }
121 break;
122 case NodeFilter::FILTER_REJECT:
123 break;
124 }
125 do {
126 if (node->previousSibling()) {
127 node = node->previousSibling();
128 break;
129 }
130 ContainerNode* parent = node->parentNode();
131 if (!parent || parent == &root() || parent == m_current.ptr())
132 return nullptr;
133 node = parent;
134 } while (node);
135 }
136 return nullptr;
137}
138
139template<TreeWalker::SiblingTraversalType type> ExceptionOr<Node*> TreeWalker::traverseSiblings()
140{
141 RefPtr<Node> node = m_current.ptr();
142 if (node == &root())
143 return nullptr;
144
145 auto isNext = type == SiblingTraversalType::Next;
146 while (true) {
147 for (RefPtr<Node> sibling = isNext ? node->nextSibling() : node->previousSibling(); sibling; ) {
148 auto filterResult = acceptNode(*sibling);
149 if (filterResult.hasException())
150 return filterResult.releaseException();
151
152 if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT) {
153 m_current = sibling.releaseNonNull();
154 return m_current.ptr();
155 }
156 node = sibling;
157 sibling = isNext ? sibling->firstChild() : sibling->lastChild();
158 if (filterResult.returnValue() == NodeFilter::FILTER_REJECT || !sibling)
159 sibling = isNext ? node->nextSibling() : node->previousSibling();
160 }
161 node = node->parentNode();
162 if (!node || node == &root())
163 return nullptr;
164
165 auto filterResult = acceptNode(*node);
166 if (filterResult.hasException())
167 return filterResult.releaseException();
168
169 if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
170 return nullptr;
171 }
172}
173
174ExceptionOr<Node*> TreeWalker::previousSibling()
175{
176 return traverseSiblings<SiblingTraversalType::Previous>();
177}
178
179ExceptionOr<Node*> TreeWalker::nextSibling()
180{
181 return traverseSiblings<SiblingTraversalType::Next>();
182}
183
184ExceptionOr<Node*> TreeWalker::previousNode()
185{
186 RefPtr<Node> node = m_current.ptr();
187 while (node != &root()) {
188 while (Node* previousSibling = node->previousSibling()) {
189 node = previousSibling;
190
191 auto filterResult = acceptNode(*node);
192 if (filterResult.hasException())
193 return filterResult.releaseException();
194
195 auto acceptNodeResult = filterResult.returnValue();
196 if (acceptNodeResult == NodeFilter::FILTER_REJECT)
197 continue;
198 while (Node* lastChild = node->lastChild()) {
199 node = lastChild;
200
201 auto filterResult = acceptNode(*node);
202 if (filterResult.hasException())
203 return filterResult.releaseException();
204
205 acceptNodeResult = filterResult.returnValue();
206 if (acceptNodeResult == NodeFilter::FILTER_REJECT)
207 break;
208 }
209 if (acceptNodeResult == NodeFilter::FILTER_ACCEPT) {
210 m_current = node.releaseNonNull();
211 return m_current.ptr();
212 }
213 }
214 if (node == &root())
215 return nullptr;
216 ContainerNode* parent = node->parentNode();
217 if (!parent)
218 return nullptr;
219 node = parent;
220
221 auto filterResult = acceptNode(*node);
222 if (filterResult.hasException())
223 return filterResult.releaseException();
224
225 if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
226 return setCurrent(node.releaseNonNull());
227 }
228 return nullptr;
229}
230
231ExceptionOr<Node*> TreeWalker::nextNode()
232{
233 RefPtr<Node> node = m_current.ptr();
234Children:
235 while (Node* firstChild = node->firstChild()) {
236 node = firstChild;
237
238 auto filterResult = acceptNode(*node);
239 if (filterResult.hasException())
240 return filterResult.releaseException();
241
242 if (filterResult.releaseReturnValue() == NodeFilter::FILTER_ACCEPT)
243 return setCurrent(node.releaseNonNull());
244 if (filterResult.returnValue() == NodeFilter::FILTER_REJECT)
245 break;
246 }
247 while (Node* nextSibling = NodeTraversal::nextSkippingChildren(*node, &root())) {
248 node = nextSibling;
249
250 auto filterResult = acceptNode(*node);
251 if (filterResult.hasException())
252 return filterResult.releaseException();
253
254 if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
255 return setCurrent(node.releaseNonNull());
256 if (filterResult.returnValue() == NodeFilter::FILTER_SKIP)
257 goto Children;
258 }
259 return nullptr;
260}
261
262} // namespace WebCore
263