1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.ws.security.util;
19
20 import org.apache.commons.logging.Log;
21 import org.apache.commons.logging.LogFactory;
22
23 import java.util.ArrayList;
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 Log log =
48 LogFactory.getLog(NSStack.class.getName());
49
50 private Mapping[] stack;
51 private int top = 0;
52 private int iterator = 0;
53 private int currentDefaultNS = -1;
54
55
56
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 stack[top] = null;
77 }
78
79 /***
80 * Remove the top frame from the stack.
81 */
82 public void pop() {
83 clearFrame();
84 top--;
85
86
87
88 if (top < currentDefaultNS) {
89
90 currentDefaultNS = top;
91 while (currentDefaultNS > 0) {
92 if (stack[currentDefaultNS] != null &&
93 stack[currentDefaultNS].getPrefix().length() == 0)
94 break;
95 currentDefaultNS--;
96 }
97 }
98 if (top == 0) {
99 if (traceEnabled)
100 log.trace("NSPop (empty)");
101 return;
102 }
103 if (traceEnabled) {
104 log.trace("NSPop (" + stack.length + ")");
105 }
106 }
107
108 /***
109 * Return a copy of the current frame. Returns null if none are present.
110 */
111 public ArrayList cloneFrame() {
112 if (stack[top] == null) return null;
113 ArrayList clone = new ArrayList();
114 for (Mapping map = topOfFrame(); map != null; map = next()) {
115 clone.add(map);
116 }
117 return clone;
118 }
119
120 /***
121 * Remove all mappings from the current frame.
122 */
123 private void clearFrame() {
124 while (stack[top] != null) top--;
125 }
126
127 /***
128 * Reset the embedded iterator in this class to the top of the current
129 * (i.e., last) frame. Note that this is not threadsafe, nor does it
130 * provide multiple iterators, so don't use this recursively. Nor
131 * should you modify the stack while iterating over it.
132 */
133 public Mapping topOfFrame() {
134 iterator = top;
135 while (stack[iterator] != null) iterator--;
136 iterator++;
137 return next();
138 }
139
140 /***
141 * Return the next namespace mapping in the top frame.
142 */
143 public Mapping next() {
144 if (iterator > top) {
145 return null;
146 } else {
147 return stack[iterator++];
148 }
149 }
150
151 /***
152 * Add a mapping for a namespaceURI to the specified prefix to the top
153 * frame in the stack. If the prefix is already mapped in that frame,
154 * remap it to the (possibly different) namespaceURI.
155 */
156 public void add(String namespaceURI, String prefix) {
157 int idx = top;
158 try {
159
160 for (int cursor = top; stack[cursor] != null; cursor--) {
161 if (stack[cursor].getPrefix().equals(prefix)) {
162 stack[cursor].setNamespaceURI(namespaceURI);
163 idx = cursor;
164 return;
165 }
166 }
167 push();
168 stack[top] = new Mapping(namespaceURI, prefix);
169 idx = top;
170 } finally {
171
172
173 if (prefix.length() == 0) {
174 currentDefaultNS = idx;
175 }
176 }
177 }
178
179 /***
180 * Return an active prefix for the given namespaceURI. NOTE : This
181 * may return null even if the namespaceURI was actually mapped further
182 * up the stack IF the prefix which was used has been repeated further
183 * down the stack. I.e.:
184 * <p/>
185 * <pre:outer xmlns:pre="namespace">
186 * <pre:inner xmlns:pre="otherNamespace">
187 * *here's where we're looking*
188 * </pre:inner>
189 * </pre:outer>
190 * <p/>
191 * If we look for a prefix for "namespace" at the indicated spot, we won't
192 * find one because "pre" is actually mapped to "otherNamespace"
193 */
194 public String getPrefix(String namespaceURI, boolean noDefault) {
195 if ((namespaceURI == null) || (namespaceURI.equals("")))
196 return null;
197 int hash = namespaceURI.hashCode();
198
199
200
201 if (!noDefault && currentDefaultNS > 0 && stack[currentDefaultNS] != null &&
202 namespaceURI.equals(stack[currentDefaultNS].getNamespaceURI()))
203 return "";
204 for (int cursor = top; cursor > 0; cursor--) {
205 Mapping map = stack[cursor];
206 if (map == null) continue;
207 if (map.getNamespaceHash() == hash &&
208 map.getNamespaceURI().equals(namespaceURI)) {
209 String possiblePrefix = map.getPrefix();
210 if (noDefault && possiblePrefix.length() == 0) continue;
211
212
213
214 int ppHash = possiblePrefix.hashCode();
215 for (int cursor2 = top; true; cursor2--) {
216 if (cursor2 == cursor) return possiblePrefix;
217 map = stack[cursor2];
218 if (map == null) continue;
219 if (ppHash == map.getPrefixHash() &&
220 possiblePrefix.equals(map.getPrefix()))
221 break;
222 }
223 }
224 }
225 return null;
226 }
227
228 /***
229 * Return an active prefix for the given namespaceURI, including
230 * the default prefix ("").
231 */
232 public String getPrefix(String namespaceURI) {
233 return getPrefix(namespaceURI, false);
234 }
235
236 /***
237 * Given a prefix, return the associated namespace (if any).
238 */
239 public String getNamespaceURI(String prefix) {
240 if (prefix == null)
241 prefix = "";
242 int hash = prefix.hashCode();
243 for (int cursor = top; cursor > 0; cursor--) {
244 Mapping map = stack[cursor];
245 if (map == null) continue;
246 if (map.getPrefixHash() == hash && map.getPrefix().equals(prefix))
247 return map.getNamespaceURI();
248 }
249 return null;
250 }
251
252 /***
253 * Produce a trace dump of the entire stack, starting from the top and
254 * including frame markers.
255 */
256 public void dump(String dumpPrefix) {
257 for (int cursor = top; cursor > 0; cursor--) {
258 Mapping map = stack[cursor];
259 if (map == null) {
260 log.trace(dumpPrefix + "stackFrame00");
261 } else {
262 log.trace(dumpPrefix + map.getNamespaceURI() + " -> " + map.getPrefix());
263 }
264 }
265 }
266 }