e851e87ec141e6f5cf63e0108f6d49a9d4d1d145
[WebKit-https.git] / Source / WebCore / dom / TreeWalker.cpp
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
31 namespace WebCore {
32
33 TreeWalker::TreeWalker(Node& rootNode, unsigned long whatToShow, RefPtr<NodeFilter>&& filter)
34     : NodeIteratorBase(rootNode, whatToShow, WTFMove(filter))
35     , m_current(root())
36 {
37 }
38
39 void TreeWalker::setCurrentNode(Node& node)
40 {
41     m_current = node;
42 }
43
44 inline Node* TreeWalker::setCurrent(Ref<Node>&& node)
45 {
46     m_current = WTFMove(node);
47     return m_current.ptr();
48 }
49
50 ExceptionOr<Node*> TreeWalker::parentNode()
51 {
52     RefPtr<Node> node = m_current.ptr();
53     while (node != &root()) {
54         node = node->parentNode();
55         if (!node)
56             return nullptr;
57
58         auto callbackResult = acceptNode(*node);
59         if (callbackResult.type() == CallbackResultType::ExceptionThrown)
60             return Exception { ExistingExceptionError };
61
62         ASSERT(callbackResult.type() == CallbackResultType::Success);
63
64         auto acceptNodeResult = callbackResult.releaseReturnValue();
65         if (acceptNodeResult == 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 callbackResult = acceptNode(*node);
75         if (callbackResult.type() == CallbackResultType::ExceptionThrown)
76             return Exception { ExistingExceptionError };
77
78         ASSERT(callbackResult.type() == CallbackResultType::Success);
79
80         auto acceptNodeResult = callbackResult.releaseReturnValue();
81         switch (acceptNodeResult) {
82             case NodeFilter::FILTER_ACCEPT:
83                 m_current = node.releaseNonNull();
84                 return m_current.ptr();
85             case NodeFilter::FILTER_SKIP:
86                 if (node->firstChild()) {
87                     node = node->firstChild();
88                     continue;
89                 }
90                 break;
91             case NodeFilter::FILTER_REJECT:
92                 break;
93         }
94         do {
95             if (node->nextSibling()) {
96                 node = node->nextSibling();
97                 break;
98             }
99             ContainerNode* parent = node->parentNode();
100             if (!parent || parent == &root() || parent == m_current.ptr())
101                 return nullptr;
102             node = parent;
103         } while (node);
104     }
105     return nullptr;
106 }
107
108 ExceptionOr<Node*> TreeWalker::lastChild()
109 {
110     for (RefPtr<Node> node = m_current->lastChild(); node; ) {
111         auto callbackResult = acceptNode(*node);
112         if (callbackResult.type() == CallbackResultType::ExceptionThrown)
113             return Exception { ExistingExceptionError };
114
115         ASSERT(callbackResult.type() == CallbackResultType::Success);
116
117         auto acceptNodeResult = callbackResult.releaseReturnValue();
118         switch (acceptNodeResult) {
119             case NodeFilter::FILTER_ACCEPT:
120                 m_current = node.releaseNonNull();
121                 return m_current.ptr();
122             case NodeFilter::FILTER_SKIP:
123                 if (node->lastChild()) {
124                     node = node->lastChild();
125                     continue;
126                 }
127                 break;
128             case NodeFilter::FILTER_REJECT:
129                 break;
130         }
131         do {
132             if (node->previousSibling()) {
133                 node = node->previousSibling();
134                 break;
135             }
136             ContainerNode* parent = node->parentNode();
137             if (!parent || parent == &root() || parent == m_current.ptr())
138                 return nullptr;
139             node = parent;
140         } while (node);
141     }
142     return nullptr;
143 }
144
145 template<TreeWalker::SiblingTraversalType type> ExceptionOr<Node*> TreeWalker::traverseSiblings()
146 {
147     RefPtr<Node> node = m_current.ptr();
148     if (node == &root())
149         return nullptr;
150
151     auto isNext = type == SiblingTraversalType::Next;
152     while (true) {
153         for (RefPtr<Node> sibling = isNext ? node->nextSibling() : node->previousSibling(); sibling; ) {
154             auto callbackResult = acceptNode(*sibling);
155             if (callbackResult.type() == CallbackResultType::ExceptionThrown)
156                 return Exception { ExistingExceptionError };
157
158             ASSERT(callbackResult.type() == CallbackResultType::Success);
159
160             auto acceptNodeResult = callbackResult.releaseReturnValue();
161             if (acceptNodeResult == NodeFilter::FILTER_ACCEPT) {
162                 m_current = sibling.releaseNonNull();
163                 return m_current.ptr();
164             }
165             node = sibling;
166             sibling = isNext ? sibling->firstChild() : sibling->lastChild();
167             if (acceptNodeResult == NodeFilter::FILTER_REJECT || !sibling)
168                 sibling = isNext ? node->nextSibling() : node->previousSibling();
169         }
170         node = node->parentNode();
171         if (!node || node == &root())
172             return nullptr;
173
174         auto callbackResult = acceptNode(*node);
175         if (callbackResult.type() == CallbackResultType::ExceptionThrown)
176             return Exception { ExistingExceptionError };
177
178         ASSERT(callbackResult.type() == CallbackResultType::Success);
179
180         auto acceptNodeResult = callbackResult.releaseReturnValue();
181         if (acceptNodeResult == NodeFilter::FILTER_ACCEPT)
182             return nullptr;
183     }
184 }
185
186 ExceptionOr<Node*> TreeWalker::previousSibling()
187 {
188     return traverseSiblings<SiblingTraversalType::Previous>();
189 }
190
191 ExceptionOr<Node*> TreeWalker::nextSibling()
192 {
193     return traverseSiblings<SiblingTraversalType::Next>();
194 }
195
196 ExceptionOr<Node*> TreeWalker::previousNode()
197 {
198     RefPtr<Node> node = m_current.ptr();
199     while (node != &root()) {
200         while (Node* previousSibling = node->previousSibling()) {
201             node = previousSibling;
202
203             auto callbackResult = acceptNode(*node);
204             if (callbackResult.type() == CallbackResultType::ExceptionThrown)
205                 return Exception { ExistingExceptionError };
206
207             ASSERT(callbackResult.type() == CallbackResultType::Success);
208
209             auto acceptNodeResult = callbackResult.releaseReturnValue();
210             if (acceptNodeResult == NodeFilter::FILTER_REJECT)
211                 continue;
212             while (Node* lastChild = node->lastChild()) {
213                 node = lastChild;
214
215                 auto callbackResult = acceptNode(*node);
216                 if (callbackResult.type() == CallbackResultType::ExceptionThrown)
217                     return Exception { ExistingExceptionError };
218
219                 ASSERT(callbackResult.type() == CallbackResultType::Success);
220
221                 acceptNodeResult = callbackResult.releaseReturnValue();
222                 if (acceptNodeResult == NodeFilter::FILTER_REJECT)
223                     break;
224             }
225             if (acceptNodeResult == NodeFilter::FILTER_ACCEPT) {
226                 m_current = node.releaseNonNull();
227                 return m_current.ptr();
228             }
229         }
230         if (node == &root())
231             return nullptr;
232         ContainerNode* parent = node->parentNode();
233         if (!parent)
234             return nullptr;
235         node = parent;
236
237         auto callbackResult = acceptNode(*node);
238         if (callbackResult.type() == CallbackResultType::ExceptionThrown)
239             return Exception { ExistingExceptionError };
240
241         ASSERT(callbackResult.type() == CallbackResultType::Success);
242
243         auto acceptNodeResult = callbackResult.releaseReturnValue();
244         if (acceptNodeResult == NodeFilter::FILTER_ACCEPT)
245             return setCurrent(node.releaseNonNull());
246     }
247     return nullptr;
248 }
249
250 ExceptionOr<Node*> TreeWalker::nextNode()
251 {
252     RefPtr<Node> node = m_current.ptr();
253 Children:
254     while (Node* firstChild = node->firstChild()) {
255         node = firstChild;
256
257         auto callbackResult = acceptNode(*node);
258         if (callbackResult.type() == CallbackResultType::ExceptionThrown)
259             return Exception { ExistingExceptionError };
260
261         ASSERT(callbackResult.type() == CallbackResultType::Success);
262
263         auto acceptNodeResult = callbackResult.releaseReturnValue();
264         if (acceptNodeResult == NodeFilter::FILTER_ACCEPT)
265             return setCurrent(node.releaseNonNull());
266         if (acceptNodeResult == NodeFilter::FILTER_REJECT)
267             break;
268     }
269     while (Node* nextSibling = NodeTraversal::nextSkippingChildren(*node, &root())) {
270         node = nextSibling;
271
272         auto callbackResult = acceptNode(*node);
273         if (callbackResult.type() == CallbackResultType::ExceptionThrown)
274             return Exception { ExistingExceptionError };
275
276         ASSERT(callbackResult.type() == CallbackResultType::Success);
277
278         auto acceptNodeResult = callbackResult.releaseReturnValue();
279         if (acceptNodeResult == NodeFilter::FILTER_ACCEPT)
280             return setCurrent(node.releaseNonNull());
281         if (acceptNodeResult == NodeFilter::FILTER_SKIP)
282             goto Children;
283     }
284     return nullptr;
285 }
286
287 } // namespace WebCore