1 /**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20 package org.apache.ws.security.util;
21
22 import java.util.ArrayList;
23 import java.util.List;
24
25 /**
26 * The abstraction this class provides is a push down stack of variable
27 * length frames of prefix to namespace mappings. Used for keeping track
28 * of what namespaces are active at any given point as an XML document is
29 * traversed or produced.
30 * <p/>
31 * From a performance point of view, this data will both be modified frequently
32 * (at a minimum, there will be one push and pop per XML element processed),
33 * and scanned frequently (many of the "good" mappings will be at the bottom
34 * of the stack). The one saving grace is that the expected maximum
35 * cardinalities of the number of frames and the number of total mappings
36 * is only in the dozens, representing the nesting depth of an XML document
37 * and the number of active namespaces at any point in the processing.
38 * <p/>
39 * Accordingly, this stack is implemented as a single array, will null
40 * values used to indicate frame boundaries.
41 *
42 * @author James Snell
43 * @author Glen Daniels (gdaniels@apache.org)
44 * @author Sam Ruby (rubys@us.ibm.com)
45 */
46 public class NSStack {
47 protected static final org.apache.commons.logging.Log log =
48 org.apache.commons.logging.LogFactory.getLog(NSStack.class);
49
50 private Mapping[] stack;
51 private int top = 0;
52 private int iterator = 0;
53 private int currentDefaultNS = -1;
54 // invariant member variable to track low-level logging requirements
55 // we cache this once per instance lifecycle to avoid repeated lookups
56 // in heavily used code.
57 private final boolean traceEnabled = log.isTraceEnabled();
58
59 public NSStack() {
60 stack = new Mapping[32];
61 stack[0] = null;
62 }
63
64 /**
65 * Create a new frame at the top of the stack.
66 */
67 public void push() {
68 top++;
69 if (top >= stack.length) {
70 Mapping newstack[] = new Mapping[stack.length * 2];
71 System.arraycopy(stack, 0, newstack, 0, stack.length);
72 stack = newstack;
73 }
74 if (traceEnabled) {
75 log.trace("NSPush (" + stack.length + ")");
76 }
77 stack[top] = null;
78 }
79
80 /**
81 * Remove the top frame from the stack.
82 */
83 public void pop() {
84 clearFrame();
85 top--;
86
87 // If we've moved below the current default NS, figure out the new
88 // default (if any)
89 if (top < currentDefaultNS) {
90 // Reset the currentDefaultNS to ignore the frame just removed.
91 currentDefaultNS = top;
92 while (currentDefaultNS > 0) {
93 if (stack[currentDefaultNS] != null &&
94 stack[currentDefaultNS].getPrefix().length() == 0) {
95 break;
96 }
97 currentDefaultNS--;
98 }
99 }
100 if (top == 0) {
101 if (traceEnabled) {
102 log.trace("NSPop (empty)");
103 }
104 return;
105 }
106 if (traceEnabled) {
107 log.trace("NSPop (" + stack.length + ")");
108 }
109 }
110
111 /**
112 * Return a copy of the current frame. Returns null if none are present.
113 */
114 public List<Mapping> cloneFrame() {
115 if (stack[top] == null) {
116 return null;
117 }
118 List<Mapping> clone = new ArrayList<Mapping>();
119 for (Mapping map = topOfFrame(); map != null; map = next()) {
120 clone.add(map);
121 }
122 return clone;
123 }
124
125 /**
126 * Remove all mappings from the current frame.
127 */
128 private void clearFrame() {
129 while (stack[top] != null) {
130 top--;
131 }
132 }
133
134 /**
135 * Reset the embedded iterator in this class to the top of the current
136 * (i.e., last) frame. Note that this is not threadsafe, nor does it
137 * provide multiple iterators, so don't use this recursively. Nor
138 * should you modify the stack while iterating over it.
139 */
140 public Mapping topOfFrame() {
141 iterator = top;
142 while (stack[iterator] != null) {
143 iterator--;
144 }
145 iterator++;
146 return next();
147 }
148
149 /**
150 * Return the next namespace mapping in the top frame.
151 */
152 public Mapping next() {
153 if (iterator > top) {
154 return null;
155 } else {
156 return stack[iterator++];
157 }
158 }
159
160 /**
161 * Add a mapping for a namespaceURI to the specified prefix to the top
162 * frame in the stack. If the prefix is already mapped in that frame,
163 * remap it to the (possibly different) namespaceURI.
164 */
165 public void add(String namespaceURI, String prefix) {
166 int idx = top;
167 try {
168 // Replace duplicate prefixes (last wins - this could also fault)
169 for (int cursor = top; stack[cursor] != null; cursor--) {
170 if (stack[cursor].getPrefix().equals(prefix)) {
171 stack[cursor].setNamespaceURI(namespaceURI);
172 idx = cursor;
173 return;
174 }
175 }
176 push();
177 stack[top] = new Mapping(namespaceURI, prefix);
178 idx = top;
179 } finally {
180 // If this is the default namespace, note the new in-scope
181 // default is here.
182 if (prefix.length() == 0) {
183 currentDefaultNS = idx;
184 }
185 }
186 }
187
188 /**
189 * Return an active prefix for the given namespaceURI. NOTE : This
190 * may return null even if the namespaceURI was actually mapped further
191 * up the stack IF the prefix which was used has been repeated further
192 * down the stack. I.e.:
193 * <p/>
194 * <pre:outer xmlns:pre="namespace">
195 * <pre:inner xmlns:pre="otherNamespace">
196 * *here's where we're looking*
197 * </pre:inner>
198 * </pre:outer>
199 * <p/>
200 * If we look for a prefix for "namespace" at the indicated spot, we won't
201 * find one because "pre" is actually mapped to "otherNamespace"
202 */
203 public String getPrefix(String namespaceURI, boolean noDefault) {
204 if ((namespaceURI == null) || (namespaceURI.equals(""))) {
205 return null;
206 }
207 int hash = namespaceURI.hashCode();
208
209 // If defaults are OK, and the given NS is the current default,
210 // return "" as the prefix to favor defaults where possible.
211 if (!noDefault && currentDefaultNS > 0 && stack[currentDefaultNS] != null &&
212 namespaceURI.equals(stack[currentDefaultNS].getNamespaceURI())) {
213 return "";
214 }
215 for (int cursor = top; cursor > 0; cursor--) {
216 Mapping map = stack[cursor];
217 if (map == null) {
218 continue;
219 }
220 if (map.getNamespaceHash() == hash &&
221 map.getNamespaceURI().equals(namespaceURI)) {
222 String possiblePrefix = map.getPrefix();
223 if (noDefault && possiblePrefix.length() == 0) {
224 continue;
225 }
226
227 // now make sure that this is the first occurance of this
228 // particular prefix
229 int ppHash = possiblePrefix.hashCode();
230 for (int cursor2 = top; true; cursor2--) {
231 if (cursor2 == cursor) {
232 return possiblePrefix;
233 }
234 map = stack[cursor2];
235 if (map == null) {
236 continue;
237 }
238 if (ppHash == map.getPrefixHash() &&
239 possiblePrefix.equals(map.getPrefix())) {
240 break;
241 }
242 }
243 }
244 }
245 return null;
246 }
247
248 /**
249 * Return an active prefix for the given namespaceURI, including
250 * the default prefix ("").
251 */
252 public String getPrefix(String namespaceURI) {
253 return getPrefix(namespaceURI, false);
254 }
255
256 /**
257 * Given a prefix, return the associated namespace (if any).
258 */
259 public String getNamespaceURI(String prefix) {
260 if (prefix == null) {
261 prefix = "";
262 }
263 int hash = prefix.hashCode();
264 for (int cursor = top; cursor > 0; cursor--) {
265 Mapping map = stack[cursor];
266 if (map == null) {
267 continue;
268 }
269 if (map.getPrefixHash() == hash && map.getPrefix().equals(prefix)) {
270 return map.getNamespaceURI();
271 }
272 }
273 return null;
274 }
275
276 /**
277 * Produce a trace dump of the entire stack, starting from the top and
278 * including frame markers.
279 */
280 public void dump(String dumpPrefix) {
281 for (int cursor = top; cursor > 0; cursor--) {
282 Mapping map = stack[cursor];
283 if (map == null) {
284 log.trace(dumpPrefix + "stackFrame00");
285 } else {
286 log.trace(dumpPrefix + map.getNamespaceURI() + " -> " + map.getPrefix());
287 }
288 }
289 }
290 }