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