1 /*
2 * Copyright (c) 2002-2026 Gargoyle Software Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 * https://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15 package org.htmlunit.html;
16
17 import java.io.Serializable;
18
19 import org.w3c.dom.DOMException;
20 import org.w3c.dom.Node;
21 import org.w3c.dom.traversal.NodeFilter;
22
23 /**
24 * In general this is an implementation of org.w3c.dom.traversal.TreeWalker.
25 * The class org.w3c.dom.traversal.TreeWalker is not available on Android
26 * therefore we have this impl as backend.
27 *
28 * @see <a href="http://www.w3.org/TR/DOM-Level-2-Traversal-Range/traversal.html">
29 * DOM-Level-2-Traversal-Range</a>
30 * @author Mike Dirolf
31 * @author Frank Danek
32 * @author Ahmed Ashour
33 * @author Ronald Brill
34 */
35 public class HtmlDomTreeWalker implements Serializable {
36
37 private final DomNode root_;
38 private DomNode currentNode_;
39 private final int whatToShow_;
40 private final NodeFilter filter_;
41 private final boolean expandEntityReferences_;
42
43 /**
44 * Creates an instance.
45 *
46 * @param root The root node of the TreeWalker. Must not be
47 * {@code null}.
48 * @param whatToShow Flag specifying which types of nodes appear in the
49 * logical view of the TreeWalker. See {@link NodeFilter} for the
50 * set of possible Show_ values.
51 * @param filter The {@link NodeFilter} to be used with this TreeWalker,
52 * or {@code null} to indicate no filter.
53 * @param expandEntityReferences If false, the contents of
54 * EntityReference nodes are not present in the logical view.
55 * @throws DOMException on attempt to create a TreeWalker with a root that
56 * is {@code null}.
57 */
58 public HtmlDomTreeWalker(final DomNode root, final int whatToShow, final NodeFilter filter,
59 final boolean expandEntityReferences) throws DOMException {
60 if (root == null) {
61 throw new IllegalArgumentException("root must not be null");
62 }
63 root_ = root;
64 whatToShow_ = whatToShow;
65 filter_ = filter;
66 expandEntityReferences_ = expandEntityReferences;
67 currentNode_ = root_;
68 }
69
70 /**
71 * Returns the root node of this tree walker.
72 *
73 * @see org.w3c.dom.traversal.TreeWalker#getRoot()
74 * @return the root node
75 */
76 public DomNode getRoot() {
77 return root_;
78 }
79
80 /**
81 * Returns the node types visible to this tree walker.
82 *
83 * @see org.w3c.dom.traversal.TreeWalker#getWhatToShow()
84 * @return NodeFilter constant
85 */
86 public int getWhatToShow() {
87 return whatToShow_;
88 }
89
90 /**
91 * Returns the node filter used by this tree walker.
92 *
93 * @see org.w3c.dom.traversal.TreeWalker#getFilter()
94 * @return the filter
95 */
96 public NodeFilter getFilter() {
97 return filter_;
98 }
99
100 /**
101 * Returns whether entity reference nodes are expanded.
102 *
103 * @see org.w3c.dom.traversal.TreeWalker#getExpandEntityReferences()
104 * @return the ExpandEntityReferences setting
105 */
106 @SuppressWarnings("PMD.BooleanGetMethodName")
107 public boolean getExpandEntityReferences() {
108 return expandEntityReferences_;
109 }
110
111 /**
112 * Returns the current node.
113 *
114 * @see org.w3c.dom.traversal.TreeWalker#getCurrentNode()
115 * @return the current node
116 */
117 public DomNode getCurrentNode() {
118 return currentNode_;
119 }
120
121 /**
122 * Sets the current node.
123 *
124 * @see org.w3c.dom.traversal.TreeWalker#setCurrentNode(Node)
125 * @param currentNode the current node
126 * @throws DOMException if the current node provided is {@code null}
127 */
128 public void setCurrentNode(final Node currentNode) throws DOMException {
129 if (currentNode == null) {
130 throw new DOMException(DOMException.NOT_SUPPORTED_ERR,
131 "currentNode cannot be set to null");
132 }
133 currentNode_ = (DomNode) currentNode;
134 }
135
136 /**
137 * Returns the next node in document order.
138 *
139 * @see org.w3c.dom.traversal.TreeWalker#nextNode()
140 * @return the next node
141 */
142 public DomNode nextNode() {
143 final DomNode leftChild = getEquivalentLogical(currentNode_.getFirstChild(), false);
144 if (leftChild != null) {
145 currentNode_ = leftChild;
146 return leftChild;
147 }
148 final DomNode rightSibling = getEquivalentLogical(currentNode_.getNextSibling(), false);
149 if (rightSibling != null) {
150 currentNode_ = rightSibling;
151 return rightSibling;
152 }
153
154 final DomNode uncle = getFirstUncleNode(currentNode_);
155 if (uncle != null) {
156 currentNode_ = uncle;
157 return uncle;
158 }
159
160 return null;
161 }
162
163 /**
164 * Returns the first ancestor's next sibling in document order.
165 */
166 private DomNode getFirstUncleNode(final DomNode n) {
167 if (n == root_ || n == null) {
168 return null;
169 }
170
171 final DomNode parent = n.getParentNode();
172 if (parent == null) {
173 return null;
174 }
175
176 final DomNode uncle = getEquivalentLogical(parent.getNextSibling(), false);
177 if (uncle != null) {
178 return uncle;
179 }
180
181 return getFirstUncleNode(parent);
182 }
183
184 /**
185 * Returns the logical node occupying the same position as the specified actual node.
186 * <p>
187 * Recursively find the logical node occupying the same position as this
188 * _actual_ node. It could be the same node, a different node, or null
189 * depending on filtering.
190 * </p>
191 *
192 * @param n The actual node we are trying to find the "equivalent" of
193 * @param lookLeft If true, traverse the tree in the left direction. If
194 * false, traverse the tree to the right.
195 * @return the logical node in the same position as n
196 */
197 private DomNode getEquivalentLogical(final DomNode n, final boolean lookLeft) {
198 // Base cases
199 if (n == null) {
200 return null;
201 }
202 if (isNodeVisible(n)) {
203 return n;
204 }
205
206 // If a node is skipped, try getting one of its descendants
207 if (isNodeSkipped(n)) {
208 final DomNode child;
209 if (lookLeft) {
210 child = getEquivalentLogical(n.getLastChild(), lookLeft);
211 }
212 else {
213 child = getEquivalentLogical(n.getFirstChild(), lookLeft);
214 }
215
216 if (child != null) {
217 return child;
218 }
219 }
220
221 // If this node is rejected or has no descendants that will work, go
222 // to its sibling.
223 return getSibling(n, lookLeft);
224 }
225
226 /**
227 * Returns whether the specified node is visible to this tree walker.
228 */
229 private boolean isNodeVisible(final Node n) {
230 if (acceptNode(n) == NodeFilter.FILTER_ACCEPT) {
231 if (filter_ == null || filter_.acceptNode(n) == NodeFilter.FILTER_ACCEPT) {
232 return expandEntityReferences_ || n.getParentNode() == null
233 || n.getParentNode().getNodeType() != Node.ENTITY_REFERENCE_NODE;
234 }
235 }
236 return false;
237 }
238
239 /**
240 * Test whether a specified node is visible in the logical view of a
241 * TreeWalker, based solely on the whatToShow constant.
242 *
243 * @param n The node to check to see if it should be shown or not
244 * @return a constant to determine whether the node is accepted, rejected,
245 * or skipped.
246 */
247 private short acceptNode(final Node n) {
248 final int flag = getFlagForNode(n);
249
250 if ((whatToShow_ & flag) != 0) {
251 return NodeFilter.FILTER_ACCEPT;
252 }
253 // Skip, don't reject.
254 return NodeFilter.FILTER_SKIP;
255 }
256
257 /**
258 * <span style="color:red">INTERNAL API - SUBJECT TO CHANGE AT ANY TIME - USE AT YOUR OWN RISK.</span><br>
259 *
260 * Given a {@link Node}, return the appropriate constant for whatToShow.
261 *
262 * @param node the node
263 * @return the whatToShow constant for the type of specified node
264 */
265 public static int getFlagForNode(final Node node) {
266 return switch (node.getNodeType()) {
267 case Node.ELEMENT_NODE -> NodeFilter.SHOW_ELEMENT;
268 case Node.ATTRIBUTE_NODE -> NodeFilter.SHOW_ATTRIBUTE;
269 case Node.TEXT_NODE -> NodeFilter.SHOW_TEXT;
270 case Node.CDATA_SECTION_NODE -> NodeFilter.SHOW_CDATA_SECTION;
271 case Node.ENTITY_REFERENCE_NODE -> NodeFilter.SHOW_ENTITY_REFERENCE;
272 case Node.ENTITY_NODE -> NodeFilter.SHOW_ENTITY;
273 case Node.PROCESSING_INSTRUCTION_NODE -> NodeFilter.SHOW_PROCESSING_INSTRUCTION;
274 case Node.COMMENT_NODE -> NodeFilter.SHOW_COMMENT;
275 case Node.DOCUMENT_NODE -> NodeFilter.SHOW_DOCUMENT;
276 case Node.DOCUMENT_TYPE_NODE -> NodeFilter.SHOW_DOCUMENT_TYPE;
277 case Node.DOCUMENT_FRAGMENT_NODE -> NodeFilter.SHOW_DOCUMENT_FRAGMENT;
278 case Node.NOTATION_NODE -> NodeFilter.SHOW_NOTATION;
279 default -> 0;
280 };
281 }
282
283 /* Returns whether the node is skipped by the TreeWalker. */
284 private boolean isNodeSkipped(final Node n) {
285 return !isNodeVisible(n) && !isNodeRejected(n);
286 }
287
288 /* Returns whether the node is rejected by the TreeWalker. */
289 private boolean isNodeRejected(final Node n) {
290 if (acceptNode(n) == NodeFilter.FILTER_REJECT) {
291 return true;
292 }
293 if (filter_ != null && filter_.acceptNode(n) == NodeFilter.FILTER_REJECT) {
294 return true;
295 }
296 return !expandEntityReferences_ && n.getParentNode() != null
297 && n.getParentNode().getNodeType() == Node.ENTITY_REFERENCE_NODE;
298 }
299
300 // Helper method for getEquivalentLogical
301 private DomNode getSibling(final DomNode n, final boolean lookLeft) {
302 if (n == null) {
303 return null;
304 }
305
306 if (isNodeVisible(n)) {
307 return null;
308 }
309
310 final DomNode sibling;
311 if (lookLeft) {
312 sibling = n.getPreviousSibling();
313 }
314 else {
315 sibling = n.getNextSibling();
316 }
317
318 if (sibling == null) {
319 // If this node has no logical siblings at or below it's "level", it might have one above
320 if (n == root_) {
321 return null;
322 }
323 return getSibling(n.getParentNode(), lookLeft);
324
325 }
326 return getEquivalentLogical(sibling, lookLeft);
327 }
328
329 /**
330 * Returns the next sibling of the current node.
331 *
332 * @see org.w3c.dom.traversal.TreeWalker#nextSibling()
333 * @return the next sibling node
334 */
335 public DomNode nextSibling() {
336 if (currentNode_ == root_) {
337 return null;
338 }
339
340 final DomNode newNode = getEquivalentLogical(currentNode_.getNextSibling(), false);
341
342 if (newNode != null) {
343 currentNode_ = newNode;
344 }
345
346 return newNode;
347 }
348
349 /**
350 * Returns the parent of the current node.
351 *
352 * @see org.w3c.dom.traversal.TreeWalker#parentNode()
353 * @return the parent node
354 */
355 public DomNode parentNode() {
356 if (currentNode_ == root_) {
357 return null;
358 }
359
360 DomNode newNode = currentNode_;
361
362 do {
363 newNode = newNode.getParentNode();
364 }
365 while (newNode != null && !isNodeVisible(newNode) && newNode != root_);
366
367 if (newNode == null || !isNodeVisible(newNode)) {
368 return null;
369 }
370 currentNode_ = newNode;
371 return newNode;
372 }
373
374 /**
375 * Returns the previous sibling of the current node.
376 *
377 * @see org.w3c.dom.traversal.TreeWalker#previousSibling()
378 * @return the previous sibling node
379 */
380 public DomNode previousSibling() {
381 if (currentNode_ == root_) {
382 return null;
383 }
384
385 final DomNode newNode = getEquivalentLogical(currentNode_.getPreviousSibling(), true);
386
387 if (newNode != null) {
388 currentNode_ = newNode;
389 }
390
391 return newNode;
392 }
393
394 /**
395 * Returns the last child of the current node.
396 *
397 * @see org.w3c.dom.traversal.TreeWalker#lastChild()
398 * @return the last child node
399 */
400 public DomNode lastChild() {
401 final DomNode newNode = getEquivalentLogical(currentNode_.getLastChild(), true);
402
403 if (newNode != null) {
404 currentNode_ = newNode;
405 }
406
407 return newNode;
408 }
409
410 /**
411 * Returns the previous node in document order.
412 *
413 * @see org.w3c.dom.traversal.TreeWalker#previousNode()
414 * @return the previous node
415 */
416 public DomNode previousNode() {
417 final DomNode newNode = getPreviousNode(currentNode_);
418
419 if (newNode != null) {
420 currentNode_ = newNode;
421 }
422
423 return newNode;
424 }
425
426 /**
427 * Returns the previous node in document order from the specified node.
428 */
429 private DomNode getPreviousNode(final DomNode n) {
430 if (n == root_) {
431 return null;
432 }
433 final DomNode left = getEquivalentLogical(n.getPreviousSibling(), true);
434 if (left == null) {
435 final DomNode parent = n.getParentNode();
436 if (parent == null) {
437 return null;
438 }
439 if (isNodeVisible(parent)) {
440 return parent;
441 }
442 }
443
444 DomNode follow = left;
445 if (follow != null) {
446 while (follow.hasChildNodes()) {
447 final DomNode toFollow = getEquivalentLogical(follow.getLastChild(), true);
448 if (toFollow == null) {
449 break;
450 }
451 follow = toFollow;
452 }
453 }
454 return follow;
455 }
456
457 /**
458 * Returns the first child of the current node.
459 *
460 * @see org.w3c.dom.traversal.TreeWalker#firstChild()
461 * @return the first child node
462 */
463 public DomNode firstChild() {
464 final DomNode newNode = getEquivalentLogical(currentNode_.getFirstChild(), false);
465
466 if (newNode != null) {
467 currentNode_ = newNode;
468 }
469
470 return newNode;
471 }
472 }