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