NodeIterator loses track of the reference node when the reference node is removed...
[WebKit-https.git] / Source / WebCore / dom / NodeIterator.cpp
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
33 namespace WebCore {
34
35 NodeIterator::NodePointer::NodePointer()
36 {
37 }
38
39 NodeIterator::NodePointer::NodePointer(PassRefPtr<Node> n, bool b)
40     : node(n)
41     , isPointerBeforeNode(b)
42 {
43 }
44
45 void NodeIterator::NodePointer::clear()
46 {
47     node.clear();
48 }
49
50 bool 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
62 bool 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
74 NodeIterator::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
85 NodeIterator::~NodeIterator()
86 {
87     if (Document* ownerDocument = root()->document())
88         ownerDocument->detachNodeIterator(this);
89 }
90
91 PassRefPtr<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
120 PassRefPtr<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
149 void NodeIterator::detach()
150 {
151     if (Document* ownerDocument = root()->document())
152         ownerDocument->detachNodeIterator(this);
153     m_detached = true;
154     m_referenceNode.node.clear();
155 }
156
157 void NodeIterator::nodeWillBeRemoved(Node* removedNode)
158 {
159     updateForNodeRemoval(removedNode, m_candidateNode);
160     updateForNodeRemoval(removedNode, m_referenceNode);
161 }
162
163 void 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 new reference
183             // node is a descendant of the node being removed.
184             while (node && node->isDescendantOf(removedNode))
185                 node = node->traverseNextNode(root());
186             if (node)
187                 referenceNode.node = node;
188         } else {
189             node = removedNode->traversePreviousNode(root());
190             if (node) {
191                 // Move out from under the node being removed if the reference node is
192                 // a descendant of the node being removed.
193                 if (willRemoveReferenceNodeAncestor) {
194                     while (node && node->isDescendantOf(removedNode))
195                         node = node->traversePreviousNode(root());
196                 }
197                 if (node) {
198                     // Removing last node.
199                     // Need to move the pointer after the node preceding the 
200                     // new reference node.
201                     referenceNode.node = node;
202                     referenceNode.isPointerBeforeNode = false;
203                 }
204             }
205         }
206     } else {
207         Node* node = removedNode->traversePreviousNode(root());
208         if (node) {
209             // Move out from under the node being removed if the reference node is
210             // a descendant of the node being removed.
211             if (willRemoveReferenceNodeAncestor) {
212                 while (node && node->isDescendantOf(removedNode))
213                     node = node->traversePreviousNode(root());
214             }
215             if (node)
216                 referenceNode.node = node;
217         } else {
218             // FIXME: This branch doesn't appear to have any LayoutTests.
219             node = removedNode->traverseNextNode(root());
220             // Move out from under the node being removed if the reference node is
221             // a descendant of the node being removed.
222             if (willRemoveReferenceNodeAncestor) {
223                 while (node && node->isDescendantOf(removedNode))
224                     node = node->traversePreviousNode(root());
225             }
226             if (node)
227                 referenceNode.node = node;
228         }
229     }
230 }
231
232
233 } // namespace WebCore