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