1 /*
2 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
3 * @LastModified: Oct 2017
4 */
5 /*
6 * Licensed to the Apache Software Foundation (ASF) under one or more
7 * contributor license agreements. See the NOTICE file distributed with
8 * this work for additional information regarding copyright ownership.
9 * The ASF licenses this file to You under the Apache License, Version 2.0
10 * (the "License"); you may not use this file except in compliance with
11 * the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 */
21 package com.sun.org.apache.xerces.internal.dom;
22
23 import java.util.ArrayList;
24 import java.util.List;
25 import org.w3c.dom.Node;
26 import org.w3c.dom.NodeList;
27
28 /**
29 * This class implements the DOM's NodeList behavior for
30 * Element.getElementsByTagName()
31 * <P>
32 * The DOM describes NodeList as follows:
33 * <P>
34 * 1) It may represent EITHER nodes scattered through a subtree (when
35 * returned by Element.getElementsByTagName), or just the immediate
36 * children (when returned by Node.getChildNodes). The latter is easy,
37 * but the former (which this class addresses) is more challenging.
38 * <P>
39 * 2) Its behavior is "live" -- that is, it always reflects the
40 * current state of the document tree. To put it another way, the
41 * NodeLists obtained before and after a series of insertions and
42 * deletions are effectively identical (as far as the user is
43 * concerned, the former has been dynamically updated as the changes
44 * have been made).
45 * <P>
46 * 3) Its API accesses individual nodes via an integer index, with the
47 * listed nodes numbered sequentially in the order that they were
48 * found during a preorder depth-first left-to-right search of the tree.
49 * (Of course in the case of getChildNodes, depth is not involved.) As
50 * nodes are inserted or deleted in the tree, and hence the NodeList,
51 * the numbering of nodes that follow them in the NodeList will
52 * change.
53 * <P>
54 * It is rather painful to support the latter two in the
55 * getElementsByTagName case. The current solution is for Nodes to
56 * maintain a change count (eventually that may be a Digest instead),
57 * which the NodeList tracks and uses to invalidate itself.
58 * <P>
59 * Unfortunately, this does _not_ respond efficiently in the case that
60 * the dynamic behavior was supposed to address: scanning a tree while
61 * it is being extended. That requires knowing which subtrees have
62 * changed, which can become an arbitrarily complex problem.
63 * <P>
64 * We save some work by filling the vector only as we access the
65 * item()s... but I suspect the same users who demanded index-based
66 * access will also start by doing a getLength() to control their loop,
67 * blowing this optimization out of the water.
68 * <P>
69 * NOTE: Level 2 of the DOM will probably _not_ use NodeList for its
70 * extended search mechanisms, partly for the reasons just discussed.
71 *
72 * @xerces.internal
73 *
74 * @since PR-DOM-Level-1-19980818.
75 */
76 public class DeepNodeListImpl
77 implements NodeList {
78
79 //
80 // Data
81 //
82 protected NodeImpl rootNode; // Where the search started
83 protected String tagName; // Or "*" to mean all-tags-acceptable
84 protected int changes = 0;
85 protected List<Node> nodes;
86
87 protected String nsName;
88 protected boolean enableNS = false;
89
90 //
91 // Constructors
92 //
93
94 /** Constructor. */
95 public DeepNodeListImpl(NodeImpl rootNode, String tagName) {
96 this.rootNode = rootNode;
97 this.tagName = tagName;
98 nodes = new ArrayList<>();
99 }
100
101 /** Constructor for Namespace support. */
102 public DeepNodeListImpl(NodeImpl rootNode,
103 String nsName, String tagName) {
104 this(rootNode, tagName);
105 this.nsName = (nsName != null && nsName.length() != 0) ? nsName : null;
106 enableNS = true;
107 }
108
109 //
110 // NodeList methods
111 //
112
113 /** Returns the length of the node list. */
114 public int getLength() {
115 // Preload all matching elements. (Stops when we run out of subtree!)
116 item(java.lang.Integer.MAX_VALUE);
117 return nodes.size();
118 }
119
120 /** Returns the node at the specified index. */
121 public Node item(int index) {
122 Node thisNode;
123
124 // Tree changed. Do it all from scratch!
125 if (rootNode.changes() != changes) {
126 nodes = new ArrayList<>();
127 changes = rootNode.changes();
128 }
129
130 // In the cache
131 final int currentSize = nodes.size();
132 if (index < currentSize) {
133 return nodes.get(index);
134 } // Not yet seen
135 else {
136
137 // Pick up where we left off (Which may be the beginning)
138 if (currentSize == 0) {
139 thisNode = rootNode;
140 } else {
141 thisNode = (NodeImpl) (nodes.get(currentSize - 1));
142 }
143
144 // Add nodes up to the one we're looking for
145 while (thisNode != null && index >= nodes.size()) {
146 thisNode = nextMatchingElementAfter(thisNode);
147 if (thisNode != null) {
148 nodes.add(thisNode);
149 }
150 }
151
152 // Either what we want, or null (not avail.)
153 return thisNode;
154 }
155
156 } // item(int):Node
157
158 //
159 // Protected methods (might be overridden by an extending DOM)
160 //
161
162 /**
163 * Iterative tree-walker. When you have a Parent link, there's often no
164 * need to resort to recursion. NOTE THAT only Element nodes are matched
165 * since we're specifically supporting getElementsByTagName().
166 */
167 protected Node nextMatchingElementAfter(Node current) {
168
169 Node next;
170 while (current != null) {
171 // Look down to first child.
172 if (current.hasChildNodes()) {
173 current = (current.getFirstChild());
174 } // Look right to sibling (but not from root!)
175 else if (current != rootNode && null != (next = current.getNextSibling())) {
176 current = next;
177 } // Look up and right (but not past root!)
178 else {
179 next = null;
180 for (; current != rootNode; // Stop when we return to starting point
181 current = current.getParentNode()) {
182
183 next = current.getNextSibling();
184 if (next != null) {
185 break;
186 }
187 }
188 current = next;
189 }
190
191 // Have we found an Element with the right tagName?
192 // ("*" matches anything.)
193 if (current != rootNode
194 && current != null
195 && current.getNodeType() == Node.ELEMENT_NODE) {
196 if (!enableNS) {
197 if (tagName.equals("*")
198 || ((ElementImpl) current).getTagName().equals(tagName)) {
199 return current;
200 }
201 } else {
202 // DOM2: Namespace logic.
203 if (tagName.equals("*")) {
204 if (nsName != null && nsName.equals("*")) {
205 return current;
206 } else {
207 ElementImpl el = (ElementImpl) current;
208 if ((nsName == null
209 && el.getNamespaceURI() == null)
210 || (nsName != null
211 && nsName.equals(el.getNamespaceURI()))) {
212 return current;
213 }
214 }
215 } else {
216 ElementImpl el = (ElementImpl) current;
217 if (el.getLocalName() != null
218 && el.getLocalName().equals(tagName)) {
219 if (nsName != null && nsName.equals("*")) {
220 return current;
221 } else {
222 if ((nsName == null
223 && el.getNamespaceURI() == null)
224 || (nsName != null
225 && nsName.equals(el.getNamespaceURI()))) {
226 return current;
227 }
228 }
229 }
230 }
231 }
232 }
233
234 // Otherwise continue walking the tree
235 }
236
237 // Fell out of tree-walk; no more instances found
238 return null;
239
240 } // nextMatchingElementAfter(int):Node
241
242 } // class DeepNodeListImpl