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