View Javadoc
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 }