1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=4 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 /*
8 * Implementation of DOM Traversal's TreeWalker
9 */
10
11 #include "mozilla/dom/TreeWalker.h"
12
13 #include "nsIContent.h"
14 #include "nsError.h"
15 #include "nsINode.h"
16 #include "nsContentUtils.h"
17 #include "mozilla/dom/NodeFilterBinding.h"
18 #include "mozilla/dom/TreeWalkerBinding.h"
19
20 namespace mozilla::dom {
21
22 /*
23 * Factories, constructors and destructors
24 */
25
TreeWalker(nsINode * aRoot,uint32_t aWhatToShow,NodeFilter * aFilter)26 TreeWalker::TreeWalker(nsINode* aRoot, uint32_t aWhatToShow,
27 NodeFilter* aFilter)
28 : nsTraversal(aRoot, aWhatToShow, aFilter), mCurrentNode(aRoot) {}
29
~TreeWalker()30 TreeWalker::~TreeWalker() { /* destructor code */
31 }
32
33 /*
34 * nsISupports and cycle collection stuff
35 */
36
NS_IMPL_CYCLE_COLLECTION(TreeWalker,mFilter,mCurrentNode,mRoot)37 NS_IMPL_CYCLE_COLLECTION(TreeWalker, mFilter, mCurrentNode, mRoot)
38
39 // QueryInterface implementation for TreeWalker
40 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(TreeWalker)
41 NS_INTERFACE_MAP_ENTRY(nsISupports)
42 NS_INTERFACE_MAP_END
43
44 // Have to pass in dom::TreeWalker because a11y has an a11y::TreeWalker that
45 // passes TreeWalker so refcount logging would get confused on the name
46 // collision.
47 NS_IMPL_CYCLE_COLLECTING_ADDREF(dom::TreeWalker)
48 NS_IMPL_CYCLE_COLLECTING_RELEASE(dom::TreeWalker)
49
50 void TreeWalker::SetCurrentNode(nsINode& aNode, ErrorResult& aResult) {
51 aResult = nsContentUtils::CheckSameOrigin(mRoot, &aNode);
52 if (aResult.Failed()) {
53 return;
54 }
55
56 mCurrentNode = &aNode;
57 }
58
ParentNode(ErrorResult & aResult)59 already_AddRefed<nsINode> TreeWalker::ParentNode(ErrorResult& aResult) {
60 nsCOMPtr<nsINode> node = mCurrentNode;
61
62 while (node && node != mRoot) {
63 node = node->GetParentNode();
64
65 if (node) {
66 int16_t filtered = TestNode(node, aResult);
67 if (aResult.Failed()) {
68 return nullptr;
69 }
70 if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
71 mCurrentNode = node;
72 return node.forget();
73 }
74 }
75 }
76
77 return nullptr;
78 }
79
FirstChild(ErrorResult & aResult)80 already_AddRefed<nsINode> TreeWalker::FirstChild(ErrorResult& aResult) {
81 return FirstChildInternal(false, aResult);
82 }
83
LastChild(ErrorResult & aResult)84 already_AddRefed<nsINode> TreeWalker::LastChild(ErrorResult& aResult) {
85 return FirstChildInternal(true, aResult);
86 }
87
PreviousSibling(ErrorResult & aResult)88 already_AddRefed<nsINode> TreeWalker::PreviousSibling(ErrorResult& aResult) {
89 return NextSiblingInternal(true, aResult);
90 }
91
NextSibling(ErrorResult & aResult)92 already_AddRefed<nsINode> TreeWalker::NextSibling(ErrorResult& aResult) {
93 return NextSiblingInternal(false, aResult);
94 }
95
PreviousNode(ErrorResult & aResult)96 already_AddRefed<nsINode> TreeWalker::PreviousNode(ErrorResult& aResult) {
97 nsCOMPtr<nsINode> node = mCurrentNode;
98
99 while (node != mRoot) {
100 while (nsINode* previousSibling = node->GetPreviousSibling()) {
101 node = previousSibling;
102
103 int16_t filtered = TestNode(node, aResult);
104 if (aResult.Failed()) {
105 return nullptr;
106 }
107
108 nsINode* lastChild;
109 while (filtered != NodeFilter_Binding::FILTER_REJECT &&
110 (lastChild = node->GetLastChild())) {
111 node = lastChild;
112 filtered = TestNode(node, aResult);
113 if (aResult.Failed()) {
114 return nullptr;
115 }
116 }
117
118 if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
119 mCurrentNode = node;
120 return node.forget();
121 }
122 }
123
124 if (node == mRoot) {
125 break;
126 }
127
128 node = node->GetParentNode();
129 if (!node) {
130 break;
131 }
132
133 int16_t filtered = TestNode(node, aResult);
134 if (aResult.Failed()) {
135 return nullptr;
136 }
137
138 if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
139 mCurrentNode = node;
140 return node.forget();
141 }
142 }
143
144 return nullptr;
145 }
146
NextNode(ErrorResult & aResult)147 already_AddRefed<nsINode> TreeWalker::NextNode(ErrorResult& aResult) {
148 int16_t filtered =
149 NodeFilter_Binding::FILTER_ACCEPT; // pre-init for inner loop
150
151 nsCOMPtr<nsINode> node = mCurrentNode;
152
153 while (1) {
154 nsINode* firstChild;
155 while (filtered != NodeFilter_Binding::FILTER_REJECT &&
156 (firstChild = node->GetFirstChild())) {
157 node = firstChild;
158
159 filtered = TestNode(node, aResult);
160 if (aResult.Failed()) {
161 return nullptr;
162 }
163
164 if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
165 // Node found
166 mCurrentNode = node;
167 return node.forget();
168 }
169 }
170
171 nsINode* sibling = nullptr;
172 nsINode* temp = node;
173 do {
174 if (temp == mRoot) break;
175
176 sibling = temp->GetNextSibling();
177 if (sibling) break;
178
179 temp = temp->GetParentNode();
180 } while (temp);
181
182 if (!sibling) break;
183
184 node = sibling;
185
186 // Found a sibling. Either ours or ancestor's
187 filtered = TestNode(node, aResult);
188 if (aResult.Failed()) {
189 return nullptr;
190 }
191
192 if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
193 // Node found
194 mCurrentNode = node;
195 return node.forget();
196 }
197 }
198
199 return nullptr;
200 }
201
202 /*
203 * TreeWalker helper functions
204 */
205
206 /*
207 * Implements FirstChild and LastChild which only vary in which direction
208 * they search.
209 * @param aReversed Controls whether we search forwards or backwards
210 * @param aResult Whether we threw or not.
211 * @returns The desired node. Null if no child is found
212 */
FirstChildInternal(bool aReversed,ErrorResult & aResult)213 already_AddRefed<nsINode> TreeWalker::FirstChildInternal(bool aReversed,
214 ErrorResult& aResult) {
215 nsCOMPtr<nsINode> node =
216 aReversed ? mCurrentNode->GetLastChild() : mCurrentNode->GetFirstChild();
217
218 while (node) {
219 int16_t filtered = TestNode(node, aResult);
220 if (aResult.Failed()) {
221 return nullptr;
222 }
223
224 switch (filtered) {
225 case NodeFilter_Binding::FILTER_ACCEPT:
226 // Node found
227 mCurrentNode = node;
228 return node.forget();
229 case NodeFilter_Binding::FILTER_SKIP: {
230 nsINode* child =
231 aReversed ? node->GetLastChild() : node->GetFirstChild();
232 if (child) {
233 node = child;
234 continue;
235 }
236 break;
237 }
238 case NodeFilter_Binding::FILTER_REJECT:
239 // Keep searching
240 break;
241 }
242
243 do {
244 nsINode* sibling =
245 aReversed ? node->GetPreviousSibling() : node->GetNextSibling();
246 if (sibling) {
247 node = sibling;
248 break;
249 }
250
251 nsINode* parent = node->GetParentNode();
252
253 if (!parent || parent == mRoot || parent == mCurrentNode) {
254 return nullptr;
255 }
256
257 node = parent;
258
259 } while (node);
260 }
261
262 return nullptr;
263 }
264
265 /*
266 * Implements NextSibling and PreviousSibling which only vary in which
267 * direction they search.
268 * @param aReversed Controls whether we search forwards or backwards
269 * @param aResult Whether we threw or not.
270 * @returns The desired node. Null if no child is found
271 */
NextSiblingInternal(bool aReversed,ErrorResult & aResult)272 already_AddRefed<nsINode> TreeWalker::NextSiblingInternal(
273 bool aReversed, ErrorResult& aResult) {
274 nsCOMPtr<nsINode> node = mCurrentNode;
275
276 if (node == mRoot) {
277 return nullptr;
278 }
279
280 while (1) {
281 nsINode* sibling =
282 aReversed ? node->GetPreviousSibling() : node->GetNextSibling();
283
284 while (sibling) {
285 node = sibling;
286
287 int16_t filtered = TestNode(node, aResult);
288 if (aResult.Failed()) {
289 return nullptr;
290 }
291
292 if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
293 // Node found
294 mCurrentNode = node;
295 return node.forget();
296 }
297
298 // If rejected or no children, try a sibling
299 if (filtered == NodeFilter_Binding::FILTER_REJECT ||
300 !(sibling =
301 aReversed ? node->GetLastChild() : node->GetFirstChild())) {
302 sibling =
303 aReversed ? node->GetPreviousSibling() : node->GetNextSibling();
304 }
305 }
306
307 node = node->GetParentNode();
308
309 if (!node || node == mRoot) {
310 return nullptr;
311 }
312
313 // Is parent transparent in filtered view?
314 int16_t filtered = TestNode(node, aResult);
315 if (aResult.Failed()) {
316 return nullptr;
317 }
318 if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
319 return nullptr;
320 }
321 }
322 }
323
WrapObject(JSContext * aCx,JS::Handle<JSObject * > aGivenProto,JS::MutableHandle<JSObject * > aReflector)324 bool TreeWalker::WrapObject(JSContext* aCx, JS::Handle<JSObject*> aGivenProto,
325 JS::MutableHandle<JSObject*> aReflector) {
326 return TreeWalker_Binding::Wrap(aCx, this, aGivenProto, aReflector);
327 }
328
329 } // namespace mozilla::dom
330