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