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.wss4j.common.util;
21
22 /**
23 * The abstraction this class provides is a push down stack of variable
24 * length frames of prefix to namespace mappings. Used for keeping track
25 * of what namespaces are active at any given point as an XML document is
26 * traversed or produced.
27 * <p/>
28 * From a performance point of view, this data will both be modified frequently
29 * (at a minimum, there will be one push and pop per XML element processed),
30 * and scanned frequently (many of the "good" mappings will be at the bottom
31 * of the stack). The one saving grace is that the expected maximum
32 * cardinalities of the number of frames and the number of total mappings
33 * is only in the dozens, representing the nesting depth of an XML document
34 * and the number of active namespaces at any point in the processing.
35 * <p/>
36 * Accordingly, this stack is implemented as a single array, will null
37 * values used to indicate frame boundaries.
38 *
39 */
40 public class NSStack {
41 private static final org.slf4j.Logger LOG =
42 org.slf4j.LoggerFactory.getLogger(NSStack.class);
43
44 private Mapping[] stack;
45 private int top;
46 private int iterator;
47 private int currentDefaultNS = -1;
48 // invariant member variable to track low-level logging requirements
49 // we cache this once per instance lifecycle to avoid repeated lookups
50 // in heavily used code.
51 private final boolean traceEnabled = LOG.isTraceEnabled();
52
53 public NSStack() {
54 stack = new Mapping[32];
55 stack[0] = null;
56 }
57
58 /**
59 * Create a new frame at the top of the stack.
60 */
61 public void push() {
62 top++;
63 if (top >= stack.length) {
64 Mapping[] newstack = new Mapping[stack.length * 2];
65 System.arraycopy(stack, 0, newstack, 0, stack.length);
66 stack = newstack;
67 }
68 if (traceEnabled) {
69 LOG.trace("NSPush (" + stack.length + ")");
70 }
71 stack[top] = null;
72 }
73
74 /**
75 * Remove the top frame from the stack.
76 */
77 public void pop() {
78 clearFrame();
79 top--;
80
81 // If we've moved below the current default NS, figure out the new
82 // default (if any)
83 if (top < currentDefaultNS) {
84 // Reset the currentDefaultNS to ignore the frame just removed.
85 currentDefaultNS = top;
86 while (currentDefaultNS > 0) {
87 if (stack[currentDefaultNS] != null
88 && stack[currentDefaultNS].getPrefix().length() == 0) {
89 break;
90 }
91 currentDefaultNS--;
92 }
93 }
94 if (top == 0) {
95 if (traceEnabled) {
96 LOG.trace("NSPop (empty)");
97 }
98 return;
99 }
100 if (traceEnabled) {
101 LOG.trace("NSPop (" + stack.length + ")");
102 }
103 }
104
105 /**
106 * Remove all mappings from the current frame.
107 */
108 private void clearFrame() {
109 while (stack[top] != null) {
110 top--;
111 }
112 }
113
114 /**
115 * Reset the embedded iterator in this class to the top of the current
116 * (i.e., last) frame. Note that this is not threadsafe, nor does it
117 * provide multiple iterators, so don't use this recursively. Nor
118 * should you modify the stack while iterating over it.
119 */
120 public Mapping topOfFrame() {
121 iterator = top;
122 while (stack[iterator] != null) {
123 iterator--;
124 }
125 iterator++;
126 return next();
127 }
128
129 /**
130 * Return the next namespace mapping in the top frame.
131 */
132 public Mapping next() {
133 if (iterator > top) {
134 return null;
135 } else {
136 return stack[iterator++];
137 }
138 }
139
140 /**
141 * Add a mapping for a namespaceURI to the specified prefix to the top
142 * frame in the stack. If the prefix is already mapped in that frame,
143 * remap it to the (possibly different) namespaceURI.
144 */
145 public void add(String namespaceURI, String prefix) {
146 int idx = top;
147 try {
148 // Replace duplicate prefixes (last wins - this could also fault)
149 for (int cursor = top; stack[cursor] != null; cursor--) {
150 if (stack[cursor].getPrefix().equals(prefix)) {
151 stack[cursor].setNamespaceURI(namespaceURI);
152 idx = cursor;
153 return;
154 }
155 }
156 push();
157 stack[top] = new Mapping(namespaceURI, prefix);
158 idx = top;
159 } finally {
160 // If this is the default namespace, note the new in-scope
161 // default is here.
162 if (prefix.length() == 0) {
163 currentDefaultNS = idx;
164 }
165 }
166 }
167
168 /**
169 * Return an active prefix for the given namespaceURI. NOTE : This
170 * may return null even if the namespaceURI was actually mapped further
171 * up the stack IF the prefix which was used has been repeated further
172 * down the stack. I.e.:
173 * <p/>
174 * <pre:outer xmlns:pre="namespace">
175 * <pre:inner xmlns:pre="otherNamespace">
176 * *here's where we're looking*
177 * </pre:inner>
178 * </pre:outer>
179 * <p/>
180 * If we look for a prefix for "namespace" at the indicated spot, we won't
181 * find one because "pre" is actually mapped to "otherNamespace"
182 */
183 public String getPrefix(String namespaceURI, boolean noDefault) {
184 if (namespaceURI == null || namespaceURI.isEmpty()) {
185 return null;
186 }
187 int hash = namespaceURI.hashCode();
188
189 // If defaults are OK, and the given NS is the current default,
190 // return "" as the prefix to favor defaults where possible.
191 if (!noDefault && currentDefaultNS > 0 && stack[currentDefaultNS] != null
192 && namespaceURI.equals(stack[currentDefaultNS].getNamespaceURI())) {
193 return "";
194 }
195 for (int cursor = top; cursor > 0; cursor--) {
196 Mapping map = stack[cursor];
197 if (map == null) {
198 continue;
199 }
200 if (map.getNamespaceHash() == hash && map.getNamespaceURI().equals(namespaceURI)) {
201 String possiblePrefix = map.getPrefix();
202 if (noDefault && possiblePrefix.length() == 0) {
203 continue;
204 }
205
206 // now make sure that this is the first occurance of this
207 // particular prefix
208 int ppHash = possiblePrefix.hashCode();
209 for (int cursor2 = top; true; cursor2--) {
210 if (cursor2 == cursor) {
211 return possiblePrefix;
212 }
213 map = stack[cursor2];
214 if (map == null) {
215 continue;
216 }
217 if (ppHash == map.getPrefixHash() && possiblePrefix.equals(map.getPrefix())) {
218 break;
219 }
220 }
221 }
222 }
223 return null;
224 }
225
226 /**
227 * Return an active prefix for the given namespaceURI, including
228 * the default prefix ("").
229 */
230 public String getPrefix(String namespaceURI) {
231 return getPrefix(namespaceURI, false);
232 }
233
234 /**
235 * Given a prefix, return the associated namespace (if any).
236 */
237 public String getNamespaceURI(String prefix) {
238 String pfix = prefix;
239 if (pfix == null) {
240 pfix = "";
241 }
242 int hash = pfix.hashCode();
243 for (int cursor = top; cursor > 0; cursor--) {
244 Mapping map = stack[cursor];
245 if (map == null) {
246 continue;
247 }
248 if (map.getPrefixHash() == hash && map.getPrefix().equals(pfix)) {
249 return map.getNamespaceURI();
250 }
251 }
252 return null;
253 }
254
255 /**
256 * Produce a trace dump of the entire stack, starting from the top and
257 * including frame markers.
258 */
259 public void dump(String dumpPrefix) {
260 for (int cursor = top; cursor > 0; cursor--) {
261 Mapping map = stack[cursor];
262 if (map == null) {
263 LOG.trace(dumpPrefix + "stackFrame00");
264 } else {
265 LOG.trace(dumpPrefix + map.getNamespaceURI() + " -> " + map.getPrefix());
266 }
267 }
268 }
269 }