View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /**
6    * Licensed to the Apache Software Foundation (ASF) under one
7    * or more contributor license agreements. See the NOTICE file
8    * distributed with this work for additional information
9    * regarding copyright ownership. The ASF licenses this file
10   * to you under the Apache License, Version 2.0 (the
11   * "License"); you may not use this file except in compliance
12   * with the License. You may obtain a copy of the License at
13   *
14   * http://www.apache.org/licenses/LICENSE-2.0
15   *
16   * Unless required by applicable law or agreed to in writing,
17   * software distributed under the License is distributed on an
18   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
19   * KIND, either express or implied. See the License for the
20   * specific language governing permissions and limitations
21   * under the License.
22   */
23  package com.sun.org.apache.xml.internal.security.c14n.implementations;
24  
25  import java.util.ArrayList;
26  import java.util.Collection;
27  import java.util.Iterator;
28  import java.util.List;
29  
30  
31  import org.w3c.dom.Attr;
32  import org.w3c.dom.Node;
33  
34  /**
35   * A stack based Symbol Table.
36   *<br>For speed reasons all the symbols are introduced in the same map,
37   * and at the same time in a list so it can be removed when the frame is pop back.
38   * @author Raul Benito
39   */
40  public class NameSpaceSymbTable {
41  
42      private static final String XMLNS = "xmlns";
43      private static final SymbMap initialMap = new SymbMap();
44  
45      static {
46          NameSpaceSymbEntry ne = new NameSpaceSymbEntry("", null, true, XMLNS);
47          ne.lastrendered = "";
48          initialMap.put(XMLNS, ne);
49      }
50  
51      /**The map betwen prefix-> entry table. */
52      private SymbMap symb;
53  
54      /**The stacks for removing the definitions when doing pop.*/
55      private List<SymbMap> level;
56      private boolean cloned = true;
57  
58      /**
59       * Default constractor
60       **/
61      public NameSpaceSymbTable() {
62          level = new ArrayList<SymbMap>();
63          //Insert the default binding for xmlns.
64          symb = (SymbMap) initialMap.clone();
65      }
66  
67      /**
68       * Get all the unrendered nodes in the name space.
69       * For Inclusive rendering
70       * @param result the list where to fill the unrendered xmlns definitions.
71       **/
72      public void getUnrenderedNodes(Collection<Attr> result) {
73          Iterator<NameSpaceSymbEntry> it = symb.entrySet().iterator();
74          while (it.hasNext()) {
75              NameSpaceSymbEntry n = it.next();
76              //put them rendered?
77              if ((!n.rendered) && (n.n != null)) {
78                  n = (NameSpaceSymbEntry) n.clone();
79                  needsClone();
80                  symb.put(n.prefix, n);
81                  n.lastrendered = n.uri;
82                  n.rendered = true;
83  
84                  result.add(n.n);
85              }
86          }
87      }
88  
89      /**
90       * Push a frame for visible namespace.
91       * For Inclusive rendering.
92       **/
93      public void outputNodePush() {
94          push();
95      }
96  
97      /**
98       * Pop a frame for visible namespace.
99       **/
100     public void outputNodePop() {
101         pop();
102     }
103 
104     /**
105      * Push a frame for a node.
106      * Inclusive or Exclusive.
107      **/
108     public void push() {
109         //Put the number of namespace definitions in the stack.
110         level.add(null);
111         cloned = false;
112     }
113 
114     /**
115      * Pop a frame.
116      * Inclusive or Exclusive.
117      **/
118     public void pop() {
119         int size = level.size() - 1;
120         Object ob = level.remove(size);
121         if (ob != null) {
122             symb = (SymbMap)ob;
123             if (size == 0) {
124                 cloned = false;
125             } else {
126                 cloned = (level.get(size - 1) != symb);
127             }
128         } else {
129             cloned = false;
130         }
131     }
132 
133     final void needsClone() {
134         if (!cloned) {
135             level.set(level.size() - 1, symb);
136             symb = (SymbMap) symb.clone();
137             cloned = true;
138         }
139     }
140 
141 
142     /**
143      * Gets the attribute node that defines the binding for the prefix.
144      * @param prefix the prefix to obtain the attribute.
145      * @return null if there is no need to render the prefix. Otherwise the node of
146      * definition.
147      **/
148     public Attr getMapping(String prefix) {
149         NameSpaceSymbEntry entry = symb.get(prefix);
150         if (entry == null) {
151             //There is no definition for the prefix(a bug?).
152             return null;
153         }
154         if (entry.rendered) {
155             //No need to render an entry already rendered.
156             return null;
157         }
158         // Mark this entry as render.
159         entry = (NameSpaceSymbEntry) entry.clone();
160         needsClone();
161         symb.put(prefix, entry);
162         entry.rendered = true;
163         entry.lastrendered = entry.uri;
164         // Return the node for outputing.
165         return entry.n;
166     }
167 
168     /**
169      * Gets a definition without mark it as render.
170      * For render in exclusive c14n the namespaces in the include prefixes.
171      * @param prefix The prefix whose definition is neaded.
172      * @return the attr to render, null if there is no need to render
173      **/
174     public Attr getMappingWithoutRendered(String prefix) {
175         NameSpaceSymbEntry entry = symb.get(prefix);
176         if (entry == null) {
177             return null;
178         }
179         if (entry.rendered) {
180             return null;
181         }
182         return entry.n;
183     }
184 
185     /**
186      * Adds the mapping for a prefix.
187      * @param prefix the prefix of definition
188      * @param uri the Uri of the definition
189      * @param n the attribute that have the definition
190      * @return true if there is already defined.
191      **/
192     public boolean addMapping(String prefix, String uri, Attr n) {
193         NameSpaceSymbEntry ob = symb.get(prefix);
194         if ((ob != null) && uri.equals(ob.uri)) {
195             //If we have it previously defined. Don't keep working.
196             return false;
197         }
198         //Creates and entry in the table for this new definition.
199         NameSpaceSymbEntry ne = new NameSpaceSymbEntry(uri, n, false, prefix);
200         needsClone();
201         symb.put(prefix, ne);
202         if (ob != null) {
203             //We have a previous definition store it for the pop.
204             //Check if a previous definition(not the inmidiatly one) has been rendered.
205             ne.lastrendered = ob.lastrendered;
206             if ((ob.lastrendered != null) && (ob.lastrendered.equals(uri))) {
207                 //Yes it is. Mark as rendered.
208                 ne.rendered = true;
209             }
210         }
211         return true;
212     }
213 
214     /**
215      * Adds a definition and mark it as render.
216      * For inclusive c14n.
217      * @param prefix the prefix of definition
218      * @param uri the Uri of the definition
219      * @param n the attribute that have the definition
220      * @return the attr to render, null if there is no need to render
221      **/
222     public Node addMappingAndRender(String prefix, String uri, Attr n) {
223         NameSpaceSymbEntry ob = symb.get(prefix);
224 
225         if ((ob != null) && uri.equals(ob.uri)) {
226             if (!ob.rendered) {
227                 ob = (NameSpaceSymbEntry) ob.clone();
228                 needsClone();
229                 symb.put(prefix, ob);
230                 ob.lastrendered = uri;
231                 ob.rendered = true;
232                 return ob.n;
233             }
234             return null;
235         }
236 
237         NameSpaceSymbEntry ne = new NameSpaceSymbEntry(uri,n,true,prefix);
238         ne.lastrendered = uri;
239         needsClone();
240         symb.put(prefix, ne);
241         if ((ob != null) && (ob.lastrendered != null) && (ob.lastrendered.equals(uri))) {
242             ne.rendered = true;
243             return null;
244         }
245         return ne.n;
246     }
247 
248     public int getLevel() {
249         return level.size();
250     }
251 
252     public void removeMapping(String prefix) {
253         NameSpaceSymbEntry ob = symb.get(prefix);
254 
255         if (ob != null) {
256             needsClone();
257             symb.put(prefix, null);
258         }
259     }
260 
261     public void removeMappingIfNotRender(String prefix) {
262         NameSpaceSymbEntry ob = symb.get(prefix);
263 
264         if (ob != null && !ob.rendered) {
265             needsClone();
266             symb.put(prefix, null);
267         }
268     }
269 
270     public boolean removeMappingIfRender(String prefix) {
271         NameSpaceSymbEntry ob = symb.get(prefix);
272 
273         if (ob != null && ob.rendered) {
274             needsClone();
275             symb.put(prefix, null);
276         }
277         return false;
278     }
279 }
280 
281 /**
282  * The internal structure of NameSpaceSymbTable.
283  **/
284 class NameSpaceSymbEntry implements Cloneable {
285 
286     String prefix;
287 
288     /**The URI that the prefix defines */
289     String uri;
290 
291     /**The last output in the URI for this prefix (This for speed reason).*/
292     String lastrendered = null;
293 
294     /**This prefix-URI has been already render or not.*/
295     boolean rendered = false;
296 
297     /**The attribute to include.*/
298     Attr n;
299 
300     NameSpaceSymbEntry(String name, Attr n, boolean rendered, String prefix) {
301         this.uri = name;
302         this.rendered = rendered;
303         this.n = n;
304         this.prefix = prefix;
305     }
306 
307     /** @inheritDoc */
308     public Object clone() {
309         try {
310             return super.clone();
311         } catch (CloneNotSupportedException e) {
312             return null;
313         }
314     }
315 };
316 
317 class SymbMap implements Cloneable {
318     int free = 23;
319     NameSpaceSymbEntry[] entries;
320     String[] keys;
321 
322     SymbMap() {
323         entries = new NameSpaceSymbEntry[free];
324         keys = new String[free];
325     }
326 
327     void put(String key, NameSpaceSymbEntry value) {
328         int index = index(key);
329         Object oldKey = keys[index];
330         keys[index] = key;
331         entries[index] = value;
332         if ((oldKey == null || !oldKey.equals(key)) && (--free == 0)) {
333             free = entries.length;
334             int newCapacity = free << 2;
335             rehash(newCapacity);
336         }
337     }
338 
339     List<NameSpaceSymbEntry> entrySet() {
340         List<NameSpaceSymbEntry> a = new ArrayList<NameSpaceSymbEntry>();
341         for (int i = 0;i < entries.length;i++) {
342             if ((entries[i] != null) && !("".equals(entries[i].uri))) {
343                 a.add(entries[i]);
344             }
345         }
346         return a;
347     }
348 
349     protected int index(Object obj) {
350         Object[] set = keys;
351         int length = set.length;
352         //abs of index
353         int index = (obj.hashCode() & 0x7fffffff) % length;
354         Object cur = set[index];
355 
356         if (cur == null || (cur.equals(obj))) {
357             return index;
358         }
359         length--;
360         do {
361             index = index == length ? 0 : ++index;
362             cur = set[index];
363         } while (cur != null && (!cur.equals(obj)));
364         return index;
365     }
366 
367     /**
368      * rehashes the map to the new capacity.
369      *
370      * @param newCapacity an <code>int</code> value
371      */
372     protected void rehash(int newCapacity) {
373         int oldCapacity = keys.length;
374         String oldKeys[] = keys;
375         NameSpaceSymbEntry oldVals[] = entries;
376 
377         keys = new String[newCapacity];
378         entries = new NameSpaceSymbEntry[newCapacity];
379 
380         for (int i = oldCapacity; i-- > 0;) {
381             if (oldKeys[i] != null) {
382                 String o = oldKeys[i];
383                 int index = index(o);
384                 keys[index] = o;
385                 entries[index] = oldVals[i];
386             }
387         }
388     }
389 
390     NameSpaceSymbEntry get(String key) {
391         return entries[index(key)];
392     }
393 
394     protected Object clone()  {
395         try {
396             SymbMap copy = (SymbMap) super.clone();
397             copy.entries = new NameSpaceSymbEntry[entries.length];
398             System.arraycopy(entries, 0, copy.entries, 0, entries.length);
399             copy.keys = new String[keys.length];
400             System.arraycopy(keys, 0, copy.keys, 0, keys.length);
401 
402             return copy;
403         } catch (CloneNotSupportedException e) {
404             e.printStackTrace();
405         }
406         return null;
407     }
408 }