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