Factor node traversal into standalone functions
[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 "NodeTraversal.h"
32 #include "ScriptState.h"
33
34 namespace WebCore {
35
36 NodeIterator::NodePointer::NodePointer()
37 {
38 }
39
40 NodeIterator::NodePointer::NodePointer(PassRefPtr<Node> n, bool b)
41     : node(n)
42     , isPointerBeforeNode(b)
43 {
44 }
45
46 void NodeIterator::NodePointer::clear()
47 {
48     node.clear();
49 }
50
51 bool 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
63 bool NodeIterator::NodePointer::moveToPrevious(Node* root)
64 {
65     if (!node)
66         return false;
67     if (!isPointerBeforeNode) {
68         isPointerBeforeNode = true;
69         return true;
70     }
71     node = NodeTraversal::previous(node.get(), root);
72     return node;
73 }
74
75 NodeIterator::NodeIterator(PassRefPtr<Node> rootNode, unsigned whatToShow, PassRefPtr<NodeFilter> filter, bool expandEntityReferences)
76     : Traversal(rootNode, whatToShow, filter, expandEntityReferences)
77     , m_referenceNode(root(), true)
78     , m_detached(false)
79 {
80     // 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.
81     ASSERT(root()->document() || root()->nodeType() == Node::DOCUMENT_TYPE_NODE);
82     if (Document* ownerDocument = root()->document())
83         ownerDocument->attachNodeIterator(this);
84 }
85
86 NodeIterator::~NodeIterator()
87 {
88     if (Document* ownerDocument = root()->document())
89         ownerDocument->detachNodeIterator(this);
90 }
91
92 PassRefPtr<Node> NodeIterator::nextNode(ScriptState* 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
121 PassRefPtr<Node> NodeIterator::previousNode(ScriptState* 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
150 void NodeIterator::detach()
151 {
152     if (Document* ownerDocument = root()->document())
153         ownerDocument->detachNodeIterator(this);
154     m_detached = true;
155     m_referenceNode.node.clear();
156 }
157
158 void NodeIterator::nodeWillBeRemoved(Node* removedNode)
159 {
160     updateForNodeRemoval(removedNode, m_candidateNode);
161     updateForNodeRemoval(removedNode, m_referenceNode);
162 }
163
164 void NodeIterator::updateForNodeRemoval(Node* removedNode, NodePointer& referenceNode) const
165 {
166     ASSERT(!m_detached);
167     ASSERT(removedNode);
168     ASSERT(root()->document());
169     ASSERT(root()->document() == removedNode->document());
170
171     // Iterator is not affected if the removed node is the reference node and is the root.
172     // or if removed node is not the reference node, or the ancestor of the reference node.
173     if (!removedNode->isDescendantOf(root()))
174         return;
175     bool willRemoveReferenceNode = removedNode == referenceNode.node;
176     bool willRemoveReferenceNodeAncestor = referenceNode.node && referenceNode.node->isDescendantOf(removedNode);
177     if (!willRemoveReferenceNode && !willRemoveReferenceNodeAncestor)
178         return;
179
180     if (referenceNode.isPointerBeforeNode) {
181         Node* node = NodeTraversal::next(removedNode, root());
182         if (node) {
183             // Move out from under the node being removed if the new reference
184             // node is a descendant of the node being removed.
185             while (node && node->isDescendantOf(removedNode))
186                 node = NodeTraversal::next(node, root());
187             if (node)
188                 referenceNode.node = node;
189         } else {
190             node = NodeTraversal::previous(removedNode, root());
191             if (node) {
192                 // Move out from under the node being removed if the reference node is
193                 // a descendant of the node being removed.
194                 if (willRemoveReferenceNodeAncestor) {
195                     while (node && node->isDescendantOf(removedNode))
196                         node = NodeTraversal::previous(node, root());
197                 }
198                 if (node) {
199                     // Removing last node.
200                     // Need to move the pointer after the node preceding the 
201                     // new reference node.
202                     referenceNode.node = node;
203                     referenceNode.isPointerBeforeNode = false;
204                 }
205             }
206         }
207     } else {
208         Node* node = NodeTraversal::previous(removedNode, root());
209         if (node) {
210             // Move out from under the node being removed if the reference node is
211             // a descendant of the node being removed.
212             if (willRemoveReferenceNodeAncestor) {
213                 while (node && node->isDescendantOf(removedNode))
214                     node = NodeTraversal::previous(node, root());
215             }
216             if (node)
217                 referenceNode.node = node;
218         } else {
219             // FIXME: This branch doesn't appear to have any LayoutTests.
220             node = NodeTraversal::next(removedNode, 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 = NodeTraversal::previous(node, root());
226             }
227             if (node)
228                 referenceNode.node = node;
229         }
230     }
231 }
232
233
234 } // namespace WebCore