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