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