1/* 2 * Copyright (c) 1997, 2003, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package sun.security.x509; 27 28import java.io.*; 29import java.util.*; 30 31import sun.security.util.*; 32 33/** 34 * Represent the GeneralSubtrees ASN.1 object. 35 * <p> 36 * The ASN.1 for this is 37 * <pre> 38 * GeneralSubtrees ::= SEQUENCE SIZE (1..MAX) OF GeneralSubtree 39 * </pre> 40 * 41 * 42 * @author Amit Kapoor 43 * @author Hemma Prafullchandra 44 * @author Andreas Sterbenz 45 */ 46public class GeneralSubtrees implements Cloneable { 47 48 private final List<GeneralSubtree> trees; 49 50 // Private variables 51 private static final int NAME_DIFF_TYPE = GeneralNameInterface.NAME_DIFF_TYPE; 52 private static final int NAME_MATCH = GeneralNameInterface.NAME_MATCH; 53 private static final int NAME_NARROWS = GeneralNameInterface.NAME_NARROWS; 54 private static final int NAME_WIDENS = GeneralNameInterface.NAME_WIDENS; 55 private static final int NAME_SAME_TYPE = GeneralNameInterface.NAME_SAME_TYPE; 56 57 /** 58 * The default constructor for the class. 59 */ 60 public GeneralSubtrees() { 61 trees = new ArrayList<>(); 62 } 63 64 private GeneralSubtrees(GeneralSubtrees source) { 65 trees = new ArrayList<>(source.trees); 66 } 67 68 /** 69 * Create the object from the passed DER encoded form. 70 * 71 * @param val the DER encoded form of the same. 72 */ 73 public GeneralSubtrees(DerValue val) throws IOException { 74 this(); 75 if (val.tag != DerValue.tag_Sequence) { 76 throw new IOException("Invalid encoding of GeneralSubtrees."); 77 } 78 while (val.data.available() != 0) { 79 DerValue opt = val.data.getDerValue(); 80 GeneralSubtree tree = new GeneralSubtree(opt); 81 add(tree); 82 } 83 } 84 85 public GeneralSubtree get(int index) { 86 return trees.get(index); 87 } 88 89 public void remove(int index) { 90 trees.remove(index); 91 } 92 93 public void add(GeneralSubtree tree) { 94 if (tree == null) { 95 throw new NullPointerException(); 96 } 97 trees.add(tree); 98 } 99 100 public boolean contains(GeneralSubtree tree) { 101 if (tree == null) { 102 throw new NullPointerException(); 103 } 104 return trees.contains(tree); 105 } 106 107 public int size() { 108 return trees.size(); 109 } 110 111 public Iterator<GeneralSubtree> iterator() { 112 return trees.iterator(); 113 } 114 115 public List<GeneralSubtree> trees() { 116 return trees; 117 } 118 119 public Object clone() { 120 return new GeneralSubtrees(this); 121 } 122 123 /** 124 * Return a printable string of the GeneralSubtree. 125 */ 126 public String toString() { 127 return " GeneralSubtrees:\n" + trees + '\n'; 128 } 129 130 /** 131 * Encode the GeneralSubtrees. 132 * 133 * @param out the DerOutputStrean to encode this object to. 134 */ 135 public void encode(DerOutputStream out) throws IOException { 136 DerOutputStream seq = new DerOutputStream(); 137 138 for (int i = 0, n = size(); i < n; i++) { 139 get(i).encode(seq); 140 } 141 out.write(DerValue.tag_Sequence, seq); 142 } 143 144 /** 145 * Compare two general subtrees by comparing the subtrees 146 * of each. 147 * 148 * @param obj GeneralSubtrees to compare to this 149 * @return true if match 150 */ 151 public boolean equals(Object obj) { 152 if (this == obj) { 153 return true; 154 } 155 if (obj instanceof GeneralSubtrees == false) { 156 return false; 157 } 158 GeneralSubtrees other = (GeneralSubtrees)obj; 159 return this.trees.equals(other.trees); 160 } 161 162 public int hashCode() { 163 return trees.hashCode(); 164 } 165 166 /** 167 * Return the GeneralNameInterface form of the GeneralName in one of 168 * the GeneralSubtrees. 169 * 170 * @param ndx index of the GeneralSubtree from which to obtain the name 171 */ 172 private GeneralNameInterface getGeneralNameInterface(int ndx) { 173 return getGeneralNameInterface(get(ndx)); 174 } 175 176 private static GeneralNameInterface getGeneralNameInterface(GeneralSubtree gs) { 177 GeneralName gn = gs.getName(); 178 GeneralNameInterface gni = gn.getName(); 179 return gni; 180 } 181 182 /** 183 * minimize this GeneralSubtrees by removing all redundant entries. 184 * Internal method used by intersect and reduce. 185 */ 186 private void minimize() { 187 188 // Algorithm: compare each entry n to all subsequent entries in 189 // the list: if any subsequent entry matches or widens entry n, 190 // remove entry n. If any subsequent entries narrow entry n, remove 191 // the subsequent entries. 192 for (int i = 0; i < (size() - 1); i++) { 193 GeneralNameInterface current = getGeneralNameInterface(i); 194 boolean remove1 = false; 195 196 /* compare current to subsequent elements */ 197 for (int j = i + 1; j < size(); j++) { 198 GeneralNameInterface subsequent = getGeneralNameInterface(j); 199 switch (current.constrains(subsequent)) { 200 case GeneralNameInterface.NAME_DIFF_TYPE: 201 /* not comparable; different name types; keep checking */ 202 continue; 203 case GeneralNameInterface.NAME_MATCH: 204 /* delete one of the duplicates */ 205 remove1 = true; 206 break; 207 case GeneralNameInterface.NAME_NARROWS: 208 /* subsequent narrows current */ 209 /* remove narrower name (subsequent) */ 210 remove(j); 211 j--; /* continue check with new subsequent */ 212 continue; 213 case GeneralNameInterface.NAME_WIDENS: 214 /* subsequent widens current */ 215 /* remove narrower name current */ 216 remove1 = true; 217 break; 218 case GeneralNameInterface.NAME_SAME_TYPE: 219 /* keep both for now; keep checking */ 220 continue; 221 } 222 break; 223 } /* end of this pass of subsequent elements */ 224 225 if (remove1) { 226 remove(i); 227 i--; /* check the new i value */ 228 } 229 230 } 231 } 232 233 /** 234 * create a subtree containing an instance of the input 235 * name type that widens all other names of that type. 236 * 237 * @param name GeneralNameInterface name 238 * @return GeneralSubtree containing widest name of that type 239 * @throws RuntimeException on error (should not occur) 240 */ 241 private GeneralSubtree createWidestSubtree(GeneralNameInterface name) { 242 try { 243 GeneralName newName; 244 switch (name.getType()) { 245 case GeneralNameInterface.NAME_ANY: 246 // Create new OtherName with same OID as baseName, but 247 // empty value 248 ObjectIdentifier otherOID = ((OtherName)name).getOID(); 249 newName = new GeneralName(new OtherName(otherOID, null)); 250 break; 251 case GeneralNameInterface.NAME_RFC822: 252 newName = new GeneralName(new RFC822Name("")); 253 break; 254 case GeneralNameInterface.NAME_DNS: 255 newName = new GeneralName(new DNSName("")); 256 break; 257 case GeneralNameInterface.NAME_X400: 258 newName = new GeneralName(new X400Address((byte[])null)); 259 break; 260 case GeneralNameInterface.NAME_DIRECTORY: 261 newName = new GeneralName(new X500Name("")); 262 break; 263 case GeneralNameInterface.NAME_EDI: 264 newName = new GeneralName(new EDIPartyName("")); 265 break; 266 case GeneralNameInterface.NAME_URI: 267 newName = new GeneralName(new URIName("")); 268 break; 269 case GeneralNameInterface.NAME_IP: 270 newName = new GeneralName(new IPAddressName((byte[])null)); 271 break; 272 case GeneralNameInterface.NAME_OID: 273 newName = new GeneralName 274 (new OIDName(new ObjectIdentifier((int[])null))); 275 break; 276 default: 277 throw new IOException 278 ("Unsupported GeneralNameInterface type: " + name.getType()); 279 } 280 return new GeneralSubtree(newName, 0, -1); 281 } catch (IOException e) { 282 throw new RuntimeException("Unexpected error: " + e, e); 283 } 284 } 285 286 /** 287 * intersect this GeneralSubtrees with other. This function 288 * is used in merging permitted NameConstraints. The operation 289 * is performed as follows: 290 * <ul> 291 * <li>If a name in other narrows all names of the same type in this, 292 * the result will contain the narrower name and none of the 293 * names it narrows. 294 * <li>If a name in other widens all names of the same type in this, 295 * the result will not contain the wider name. 296 * <li>If a name in other does not share the same subtree with any name 297 * of the same type in this, then the name is added to the list 298 * of GeneralSubtrees returned. These names should be added to 299 * the list of names that are specifically excluded. The reason 300 * is that, if the intersection is empty, then no names of that 301 * type are permitted, and the only way to express this in 302 * NameConstraints is to include the name in excludedNames. 303 * <li>If a name in this has no name of the same type in other, then 304 * the result contains the name in this. No name of a given type 305 * means the name type is completely permitted. 306 * <li>If a name in other has no name of the same type in this, then 307 * the result contains the name in other. This means that 308 * the name is now constrained in some way, whereas before it was 309 * completely permitted. 310 * </ul> 311 * 312 * @param other GeneralSubtrees to be intersected with this 313 * @return GeneralSubtrees to be merged with excluded; these are 314 * empty-valued name types corresponding to entries that were 315 * of the same type but did not share the same subtree between 316 * this and other. Returns null if no such. 317 */ 318 public GeneralSubtrees intersect(GeneralSubtrees other) { 319 320 if (other == null) { 321 throw new NullPointerException("other GeneralSubtrees must not be null"); 322 } 323 324 GeneralSubtrees newThis = new GeneralSubtrees(); 325 GeneralSubtrees newExcluded = null; 326 327 // Step 1: If this is empty, just add everything in other to this and 328 // return no new excluded entries 329 if (size() == 0) { 330 union(other); 331 return null; 332 } 333 334 // Step 2: For ease of checking the subtrees, minimize them by 335 // constructing versions that contain only the widest instance of 336 // each type 337 this.minimize(); 338 other.minimize(); 339 340 // Step 3: Check each entry in this to see whether we keep it or 341 // remove it, and whether we add anything to newExcluded or newThis. 342 // We keep an entry in this unless it is narrowed by all entries in 343 // other. We add an entry to newExcluded if there is at least one 344 // entry of the same nameType in other, but this entry does 345 // not share the same subtree with any of the entries in other. 346 // We add an entry from other to newThis if there is no name of the 347 // same type in this. 348 for (int i = 0; i < size(); i++) { 349 GeneralNameInterface thisEntry = getGeneralNameInterface(i); 350 boolean removeThisEntry = false; 351 352 // Step 3a: If the widest name of this type in other narrows 353 // thisEntry, remove thisEntry and add widest other to newThis. 354 // Simultaneously, check for situation where there is a name of 355 // this type in other, but no name in other matches, narrows, 356 // or widens thisEntry. 357 boolean sameType = false; 358 for (int j = 0; j < other.size(); j++) { 359 GeneralSubtree otherEntryGS = other.get(j); 360 GeneralNameInterface otherEntry = 361 getGeneralNameInterface(otherEntryGS); 362 switch (thisEntry.constrains(otherEntry)) { 363 case NAME_NARROWS: 364 remove(i); 365 i--; 366 newThis.add(otherEntryGS); 367 sameType = false; 368 break; 369 case NAME_SAME_TYPE: 370 sameType = true; 371 continue; 372 case NAME_MATCH: 373 case NAME_WIDENS: 374 sameType = false; 375 break; 376 case NAME_DIFF_TYPE: 377 default: 378 continue; 379 } 380 break; 381 } 382 383 // Step 3b: If sameType is still true, we have the situation 384 // where there was a name of the same type as thisEntry in 385 // other, but no name in other widened, matched, or narrowed 386 // thisEntry. 387 if (sameType) { 388 389 // Step 3b.1: See if there are any entries in this and other 390 // with this type that match, widen, or narrow each other. 391 // If not, then we need to add a "widest subtree" of this 392 // type to excluded. 393 boolean intersection = false; 394 for (int j = 0; j < size(); j++) { 395 GeneralNameInterface thisAltEntry = getGeneralNameInterface(j); 396 397 if (thisAltEntry.getType() == thisEntry.getType()) { 398 for (int k = 0; k < other.size(); k++) { 399 GeneralNameInterface othAltEntry = 400 other.getGeneralNameInterface(k); 401 402 int constraintType = 403 thisAltEntry.constrains(othAltEntry); 404 if (constraintType == NAME_MATCH || 405 constraintType == NAME_WIDENS || 406 constraintType == NAME_NARROWS) { 407 intersection = true; 408 break; 409 } 410 } 411 } 412 } 413 if (intersection == false) { 414 if (newExcluded == null) { 415 newExcluded = new GeneralSubtrees(); 416 } 417 GeneralSubtree widestSubtree = 418 createWidestSubtree(thisEntry); 419 if (!newExcluded.contains(widestSubtree)) { 420 newExcluded.add(widestSubtree); 421 } 422 } 423 424 // Step 3b.2: Remove thisEntry from this 425 remove(i); 426 i--; 427 } 428 } 429 430 // Step 4: Add all entries in newThis to this 431 if (newThis.size() > 0) { 432 union(newThis); 433 } 434 435 // Step 5: Add all entries in other that do not have any entry of the 436 // same type in this to this 437 for (int i = 0; i < other.size(); i++) { 438 GeneralSubtree otherEntryGS = other.get(i); 439 GeneralNameInterface otherEntry = getGeneralNameInterface(otherEntryGS); 440 boolean diffType = false; 441 for (int j = 0; j < size(); j++) { 442 GeneralNameInterface thisEntry = getGeneralNameInterface(j); 443 switch (thisEntry.constrains(otherEntry)) { 444 case NAME_DIFF_TYPE: 445 diffType = true; 446 // continue to see if we find something later of the 447 // same type 448 continue; 449 case NAME_NARROWS: 450 case NAME_SAME_TYPE: 451 case NAME_MATCH: 452 case NAME_WIDENS: 453 diffType = false; // we found an entry of the same type 454 // break because we know we won't be adding it to 455 // this now 456 break; 457 default: 458 continue; 459 } 460 break; 461 } 462 if (diffType) { 463 add(otherEntryGS); 464 } 465 } 466 467 // Step 6: Return the newExcluded GeneralSubtrees 468 return newExcluded; 469 } 470 471 /** 472 * construct union of this GeneralSubtrees with other. 473 * 474 * @param other GeneralSubtrees to be united with this 475 */ 476 public void union(GeneralSubtrees other) { 477 if (other != null) { 478 for (int i = 0, n = other.size(); i < n; i++) { 479 add(other.get(i)); 480 } 481 // Minimize this 482 minimize(); 483 } 484 } 485 486 /** 487 * reduce this GeneralSubtrees by contents of another. This function 488 * is used in merging excluded NameConstraints with permitted NameConstraints 489 * to obtain a minimal form of permitted NameConstraints. It is an 490 * optimization, and does not affect correctness of the results. 491 * 492 * @param excluded GeneralSubtrees 493 */ 494 public void reduce(GeneralSubtrees excluded) { 495 if (excluded == null) { 496 return; 497 } 498 for (int i = 0, n = excluded.size(); i < n; i++) { 499 GeneralNameInterface excludedName = excluded.getGeneralNameInterface(i); 500 for (int j = 0; j < size(); j++) { 501 GeneralNameInterface permitted = getGeneralNameInterface(j); 502 switch (excludedName.constrains(permitted)) { 503 case GeneralNameInterface.NAME_DIFF_TYPE: 504 break; 505 case GeneralNameInterface.NAME_MATCH: 506 remove(j); 507 j--; 508 break; 509 case GeneralNameInterface.NAME_NARROWS: 510 /* permitted narrows excluded */ 511 remove(j); 512 j--; 513 break; 514 case GeneralNameInterface.NAME_WIDENS: 515 /* permitted widens excluded */ 516 break; 517 case GeneralNameInterface.NAME_SAME_TYPE: 518 break; 519 } 520 } /* end of this pass of permitted */ 521 } /* end of pass of excluded */ 522 } 523} 524