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 | |
32 | namespace WebCore { |
33 | |
34 | WTF_MAKE_ISO_ALLOCATED_IMPL(TreeWalker); |
35 | |
36 | TreeWalker::TreeWalker(Node& rootNode, unsigned long whatToShow, RefPtr<NodeFilter>&& filter) |
37 | : NodeIteratorBase(rootNode, whatToShow, WTFMove(filter)) |
38 | , m_current(root()) |
39 | { |
40 | } |
41 | |
42 | void TreeWalker::setCurrentNode(Node& node) |
43 | { |
44 | m_current = node; |
45 | } |
46 | |
47 | inline Node* TreeWalker::setCurrent(Ref<Node>&& node) |
48 | { |
49 | m_current = WTFMove(node); |
50 | return m_current.ptr(); |
51 | } |
52 | |
53 | ExceptionOr<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 | |
71 | ExceptionOr<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 | |
105 | ExceptionOr<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 | |
139 | template<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 | |
174 | ExceptionOr<Node*> TreeWalker::previousSibling() |
175 | { |
176 | return traverseSiblings<SiblingTraversalType::Previous>(); |
177 | } |
178 | |
179 | ExceptionOr<Node*> TreeWalker::nextSibling() |
180 | { |
181 | return traverseSiblings<SiblingTraversalType::Next>(); |
182 | } |
183 | |
184 | ExceptionOr<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 | |
231 | ExceptionOr<Node*> TreeWalker::nextNode() |
232 | { |
233 | RefPtr<Node> node = m_current.ptr(); |
234 | Children: |
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 | |