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