Reinstate active flag for iterators
[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 filterResult = acceptNode(*node);
59         if (filterResult.hasException())
60             return filterResult.releaseException();
61
62         if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
63             return setCurrent(node.releaseNonNull());
64     }
65     return nullptr;
66 }
67
68 ExceptionOr<Node*> TreeWalker::firstChild()
69 {
70     for (RefPtr<Node> node = m_current->firstChild(); node; ) {
71         auto filterResult = acceptNode(*node);
72         if (filterResult.hasException())
73             return filterResult.releaseException();
74
75         switch (filterResult.returnValue()) {
76             case NodeFilter::FILTER_ACCEPT:
77                 m_current = node.releaseNonNull();
78                 return m_current.ptr();
79             case NodeFilter::FILTER_SKIP:
80                 if (node->firstChild()) {
81                     node = node->firstChild();
82                     continue;
83                 }
84                 break;
85             case NodeFilter::FILTER_REJECT:
86                 break;
87         }
88         do {
89             if (node->nextSibling()) {
90                 node = node->nextSibling();
91                 break;
92             }
93             ContainerNode* parent = node->parentNode();
94             if (!parent || parent == &root() || parent == m_current.ptr())
95                 return nullptr;
96             node = parent;
97         } while (node);
98     }
99     return nullptr;
100 }
101
102 ExceptionOr<Node*> TreeWalker::lastChild()
103 {
104     for (RefPtr<Node> node = m_current->lastChild(); node; ) {
105         auto filterResult = acceptNode(*node);
106         if (filterResult.hasException())
107             return filterResult.releaseException();
108
109         switch (filterResult.returnValue()) {
110             case NodeFilter::FILTER_ACCEPT:
111                 m_current = node.releaseNonNull();
112                 return m_current.ptr();
113             case NodeFilter::FILTER_SKIP:
114                 if (node->lastChild()) {
115                     node = node->lastChild();
116                     continue;
117                 }
118                 break;
119             case NodeFilter::FILTER_REJECT:
120                 break;
121         }
122         do {
123             if (node->previousSibling()) {
124                 node = node->previousSibling();
125                 break;
126             }
127             ContainerNode* parent = node->parentNode();
128             if (!parent || parent == &root() || parent == m_current.ptr())
129                 return nullptr;
130             node = parent;
131         } while (node);
132     }
133     return nullptr;
134 }
135
136 template<TreeWalker::SiblingTraversalType type> ExceptionOr<Node*> TreeWalker::traverseSiblings()
137 {
138     RefPtr<Node> node = m_current.ptr();
139     if (node == &root())
140         return nullptr;
141
142     auto isNext = type == SiblingTraversalType::Next;
143     while (true) {
144         for (RefPtr<Node> sibling = isNext ? node->nextSibling() : node->previousSibling(); sibling; ) {
145             auto filterResult = acceptNode(*sibling);
146             if (filterResult.hasException())
147                 return filterResult.releaseException();
148
149             if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT) {
150                 m_current = sibling.releaseNonNull();
151                 return m_current.ptr();
152             }
153             node = sibling;
154             sibling = isNext ? sibling->firstChild() : sibling->lastChild();
155             if (filterResult.returnValue() == NodeFilter::FILTER_REJECT || !sibling)
156                 sibling = isNext ? node->nextSibling() : node->previousSibling();
157         }
158         node = node->parentNode();
159         if (!node || node == &root())
160             return nullptr;
161
162         auto filterResult = acceptNode(*node);
163         if (filterResult.hasException())
164             return filterResult.releaseException();
165
166         if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
167             return nullptr;
168     }
169 }
170
171 ExceptionOr<Node*> TreeWalker::previousSibling()
172 {
173     return traverseSiblings<SiblingTraversalType::Previous>();
174 }
175
176 ExceptionOr<Node*> TreeWalker::nextSibling()
177 {
178     return traverseSiblings<SiblingTraversalType::Next>();
179 }
180
181 ExceptionOr<Node*> TreeWalker::previousNode()
182 {
183     RefPtr<Node> node = m_current.ptr();
184     while (node != &root()) {
185         while (Node* previousSibling = node->previousSibling()) {
186             node = previousSibling;
187
188             auto filterResult = acceptNode(*node);
189             if (filterResult.hasException())
190                 return filterResult.releaseException();
191
192             auto acceptNodeResult = filterResult.returnValue();
193             if (acceptNodeResult == NodeFilter::FILTER_REJECT)
194                 continue;
195             while (Node* lastChild = node->lastChild()) {
196                 node = lastChild;
197
198                 auto filterResult = acceptNode(*node);
199                 if (filterResult.hasException())
200                     return filterResult.releaseException();
201
202                 acceptNodeResult = filterResult.returnValue();
203                 if (acceptNodeResult == NodeFilter::FILTER_REJECT)
204                     break;
205             }
206             if (acceptNodeResult == NodeFilter::FILTER_ACCEPT) {
207                 m_current = node.releaseNonNull();
208                 return m_current.ptr();
209             }
210         }
211         if (node == &root())
212             return nullptr;
213         ContainerNode* parent = node->parentNode();
214         if (!parent)
215             return nullptr;
216         node = parent;
217
218         auto filterResult = acceptNode(*node);
219         if (filterResult.hasException())
220             return filterResult.releaseException();
221
222         if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
223             return setCurrent(node.releaseNonNull());
224     }
225     return nullptr;
226 }
227
228 ExceptionOr<Node*> TreeWalker::nextNode()
229 {
230     RefPtr<Node> node = m_current.ptr();
231 Children:
232     while (Node* firstChild = node->firstChild()) {
233         node = firstChild;
234
235         auto filterResult = acceptNode(*node);
236         if (filterResult.hasException())
237             return filterResult.releaseException();
238
239         if (filterResult.releaseReturnValue() == NodeFilter::FILTER_ACCEPT)
240             return setCurrent(node.releaseNonNull());
241         if (filterResult.returnValue() == NodeFilter::FILTER_REJECT)
242             break;
243     }
244     while (Node* nextSibling = NodeTraversal::nextSkippingChildren(*node, &root())) {
245         node = nextSibling;
246
247         auto filterResult = acceptNode(*node);
248         if (filterResult.hasException())
249             return filterResult.releaseException();
250
251         if (filterResult.returnValue() == NodeFilter::FILTER_ACCEPT)
252             return setCurrent(node.releaseNonNull());
253         if (filterResult.returnValue() == NodeFilter::FILTER_SKIP)
254             goto Children;
255     }
256     return nullptr;
257 }
258
259 } // namespace WebCore