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 "NodeIterator.h"
27
28#include "Document.h"
29#include "ExceptionCode.h"
30#include "NodeFilter.h"
31#include "ScriptState.h"
32
33namespace WebCore {
34
35NodeIterator::NodePointer::NodePointer()
36{
37}
38
39NodeIterator::NodePointer::NodePointer(PassRefPtr<Node> n, bool b)
40    : node(n)
41    , isPointerBeforeNode(b)
42{
43}
44
45void NodeIterator::NodePointer::clear()
46{
47    node.clear();
48}
49
50bool NodeIterator::NodePointer::moveToNext(Node* root)
51{
52    if (!node)
53        return false;
54    if (isPointerBeforeNode) {
55        isPointerBeforeNode = false;
56        return true;
57    }
58    node = node->traverseNextNode(root);
59    return node;
60}
61
62bool NodeIterator::NodePointer::moveToPrevious(Node* root)
63{
64    if (!node)
65        return false;
66    if (!isPointerBeforeNode) {
67        isPointerBeforeNode = true;
68        return true;
69    }
70    node = node->traversePreviousNode(root);
71    return node;
72}
73
74NodeIterator::NodeIterator(PassRefPtr<Node> rootNode, unsigned whatToShow, PassRefPtr<NodeFilter> filter, bool expandEntityReferences)
75    : Traversal(rootNode, whatToShow, filter, expandEntityReferences)
76    , m_referenceNode(root(), true)
77    , m_detached(false)
78{
79    // Document type nodes may have a null document. But since they can't have children, there is no need to listen for modifications to these.
80    ASSERT(root()->document() || root()->nodeType() == Node::DOCUMENT_TYPE_NODE);
81    if (Document* ownerDocument = root()->document())
82        ownerDocument->attachNodeIterator(this);
83}
84
85NodeIterator::~NodeIterator()
86{
87    if (Document* ownerDocument = root()->document())
88        ownerDocument->detachNodeIterator(this);
89}
90
91PassRefPtr<Node> NodeIterator::nextNode(ScriptState* state, ExceptionCode& ec)
92{
93    if (m_detached) {
94        ec = INVALID_STATE_ERR;
95        return 0;
96    }
97
98    RefPtr<Node> result;
99
100    m_candidateNode = m_referenceNode;
101    while (m_candidateNode.moveToNext(root())) {
102        // NodeIterators treat the DOM tree as a flat list of nodes.
103        // In other words, FILTER_REJECT does not pass over descendants
104        // of the rejected node. Hence, FILTER_REJECT is the same as FILTER_SKIP.
105        RefPtr<Node> provisionalResult = m_candidateNode.node;
106        bool nodeWasAccepted = acceptNode(state, provisionalResult.get()) == NodeFilter::FILTER_ACCEPT;
107        if (state && state->hadException())
108            break;
109        if (nodeWasAccepted) {
110            m_referenceNode = m_candidateNode;
111            result = provisionalResult.release();
112            break;
113        }
114    }
115
116    m_candidateNode.clear();
117    return result.release();
118}
119
120PassRefPtr<Node> NodeIterator::previousNode(ScriptState* state, ExceptionCode& ec)
121{
122    if (m_detached) {
123        ec = INVALID_STATE_ERR;
124        return 0;
125    }
126
127    RefPtr<Node> result;
128
129    m_candidateNode = m_referenceNode;
130    while (m_candidateNode.moveToPrevious(root())) {
131        // NodeIterators treat the DOM tree as a flat list of nodes.
132        // In other words, FILTER_REJECT does not pass over descendants
133        // of the rejected node. Hence, FILTER_REJECT is the same as FILTER_SKIP.
134        RefPtr<Node> provisionalResult = m_candidateNode.node;
135        bool nodeWasAccepted = acceptNode(state, provisionalResult.get()) == NodeFilter::FILTER_ACCEPT;
136        if (state && state->hadException())
137            break;
138        if (nodeWasAccepted) {
139            m_referenceNode = m_candidateNode;
140            result = provisionalResult.release();
141            break;
142        }
143    }
144
145    m_candidateNode.clear();
146    return result.release();
147}
148
149void NodeIterator::detach()
150{
151    if (Document* ownerDocument = root()->document())
152        ownerDocument->detachNodeIterator(this);
153    m_detached = true;
154    m_referenceNode.node.clear();
155}
156
157void NodeIterator::nodeWillBeRemoved(Node* removedNode)
158{
159    updateForNodeRemoval(removedNode, m_candidateNode);
160    updateForNodeRemoval(removedNode, m_referenceNode);
161}
162
163void NodeIterator::updateForNodeRemoval(Node* removedNode, NodePointer& referenceNode) const
164{
165    ASSERT(!m_detached);
166    ASSERT(removedNode);
167    ASSERT(root()->document());
168    ASSERT(root()->document() == removedNode->document());
169
170    // Iterator is not affected if the removed node is the reference node and is the root.
171    // or if removed node is not the reference node, or the ancestor of the reference node.
172    if (!removedNode->isDescendantOf(root()))
173        return;
174    bool willRemoveReferenceNode = removedNode == referenceNode.node;
175    bool willRemoveReferenceNodeAncestor = referenceNode.node && referenceNode.node->isDescendantOf(removedNode);
176    if (!willRemoveReferenceNode && !willRemoveReferenceNodeAncestor)
177        return;
178
179    if (referenceNode.isPointerBeforeNode) {
180        Node* node = removedNode->traverseNextNode(root());
181        if (node) {
182            // Move out from under the node being removed if the reference node is
183            // a descendant of the node being removed.
184            if (willRemoveReferenceNodeAncestor) {
185                while (node && node->isDescendantOf(removedNode))
186                    node = node->traverseNextNode(root());
187            }
188            if (node)
189                referenceNode.node = node;
190        } else {
191            node = removedNode->traversePreviousNode(root());
192            if (node) {
193                // Move out from under the node being removed if the reference node is
194                // a descendant of the node being removed.
195                if (willRemoveReferenceNodeAncestor) {
196                    while (node && node->isDescendantOf(removedNode))
197                        node = node->traversePreviousNode(root());
198                }
199                if (node) {
200                    // Removing last node.
201                    // Need to move the pointer after the node preceding the
202                    // new reference node.
203                    referenceNode.node = node;
204                    referenceNode.isPointerBeforeNode = false;
205                }
206            }
207        }
208    } else {
209        Node* node = removedNode->traversePreviousNode(root());
210        if (node) {
211            // Move out from under the node being removed if the reference node is
212            // a descendant of the node being removed.
213            if (willRemoveReferenceNodeAncestor) {
214                while (node && node->isDescendantOf(removedNode))
215                    node = node->traversePreviousNode(root());
216            }
217            if (node)
218                referenceNode.node = node;
219        } else {
220            node = removedNode->traverseNextNode(root());
221            // Move out from under the node being removed if the reference node is
222            // a descendant of the node being removed.
223            if (willRemoveReferenceNodeAncestor) {
224                while (node && node->isDescendantOf(removedNode))
225                    node = node->traversePreviousNode(root());
226            }
227            if (node)
228                referenceNode.node = node;
229        }
230    }
231}
232
233
234} // namespace WebCore
235