001: /*
002: * @(#)GeneralSubtrees.java 1.4 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: /*
029: * Note that there are two versions of this file, this subsetted
030: * CDC/FP version which avoids using the X400Address class, and
031: * the "complete" one for the security optional package. Be sure
032: * you're changing the correct file!
033: */
034:
035: package sun.security.x509;
036:
037: import java.io.*;
038: import java.util.*;
039:
040: import sun.security.util.*;
041:
042: /**
043: * Represent the GeneralSubtrees ASN.1 object.
044: * <p>
045: * The ASN.1 for this is
046: * <pre>
047: * GeneralSubtrees ::= SEQUENCE SIZE (1..MAX) OF GeneralSubtree
048: * </pre>
049: * </p>
050: *
051: * @version 1.4, 10/10/06
052: *
053: * @author Amit Kapoor
054: * @author Hemma Prafullchandra
055: * @author Andreas Sterbenz
056: */
057: public class GeneralSubtrees implements Cloneable {
058:
059: private final List trees;
060:
061: // Private variables
062: private static final int NAME_DIFF_TYPE = GeneralNameInterface.NAME_DIFF_TYPE;
063: private static final int NAME_MATCH = GeneralNameInterface.NAME_MATCH;
064: private static final int NAME_NARROWS = GeneralNameInterface.NAME_NARROWS;
065: private static final int NAME_WIDENS = GeneralNameInterface.NAME_WIDENS;
066: private static final int NAME_SAME_TYPE = GeneralNameInterface.NAME_SAME_TYPE;
067:
068: /**
069: * The default constructor for the class.
070: */
071: public GeneralSubtrees() {
072: trees = new ArrayList();
073: }
074:
075: private GeneralSubtrees(GeneralSubtrees source) {
076: ArrayList sourceTrees = (ArrayList) source.trees;
077: trees = (List) sourceTrees.clone();
078: }
079:
080: /**
081: * Create the object from the passed DER encoded form.
082: *
083: * @param val the DER encoded form of the same.
084: */
085: public GeneralSubtrees(DerValue val) throws IOException {
086: this ();
087: if (val.tag != DerValue.tag_Sequence) {
088: throw new IOException(
089: "Invalid encoding of GeneralSubtrees.");
090: }
091: while (val.data.available() != 0) {
092: DerValue opt = val.data.getDerValue();
093: GeneralSubtree tree = new GeneralSubtree(opt);
094: add(tree);
095: }
096: }
097:
098: public GeneralSubtree get(int index) {
099: return (GeneralSubtree) trees.get(index);
100: }
101:
102: public void remove(int index) {
103: trees.remove(index);
104: }
105:
106: public void add(GeneralSubtree tree) {
107: if (tree == null) {
108: throw new NullPointerException();
109: }
110: trees.add(tree);
111: }
112:
113: public boolean contains(GeneralSubtree tree) {
114: if (tree == null) {
115: throw new NullPointerException();
116: }
117: return trees.contains(tree);
118: }
119:
120: public int size() {
121: return trees.size();
122: }
123:
124: public Iterator iterator() {
125: return trees.iterator();
126: }
127:
128: public Object clone() {
129: return new GeneralSubtrees(this );
130: }
131:
132: /**
133: * Return a printable string of the GeneralSubtree.
134: */
135: public String toString() {
136: String s = " GeneralSubtrees:\n" + trees.toString() + "\n";
137: return s;
138: }
139:
140: /**
141: * Encode the GeneralSubtrees.
142: *
143: * @params out the DerOutputStrean to encode this object to.
144: */
145: public void encode(DerOutputStream out) throws IOException {
146: DerOutputStream seq = new DerOutputStream();
147:
148: for (int i = 0, n = size(); i < n; i++) {
149: get(i).encode(seq);
150: }
151: out.write(DerValue.tag_Sequence, seq);
152: }
153:
154: /**
155: * Compare two general subtrees by comparing the subtrees
156: * of each.
157: *
158: * @param other GeneralSubtrees to compare to this
159: * @returns true if match
160: */
161: public boolean equals(Object obj) {
162: if (this == obj) {
163: return true;
164: }
165: if (obj instanceof GeneralSubtrees == false) {
166: return false;
167: }
168: GeneralSubtrees other = (GeneralSubtrees) obj;
169: return this .trees.equals(other.trees);
170: }
171:
172: public int hashCode() {
173: return trees.hashCode();
174: }
175:
176: /**
177: * Return the GeneralNameInterface form of the GeneralName in one of
178: * the GeneralSubtrees.
179: *
180: * @param ndx index of the GeneralSubtree from which to obtain the name
181: */
182: private GeneralNameInterface getGeneralNameInterface(int ndx) {
183: return getGeneralNameInterface(get(ndx));
184: }
185:
186: private static GeneralNameInterface getGeneralNameInterface(
187: GeneralSubtree gs) {
188: GeneralName gn = gs.getName();
189: GeneralNameInterface gni = gn.getName();
190: return gni;
191: }
192:
193: /**
194: * minimize this GeneralSubtrees by removing all redundant entries.
195: * Internal method used by intersect and reduce.
196: */
197: private void minimize() {
198:
199: // Algorithm: compare each entry n to all subsequent entries in
200: // the list: if any subsequent entry matches or widens entry n,
201: // remove entry n. If any subsequent entries narrow entry n, remove
202: // the subsequent entries.
203: for (int i = 0; i < size(); i++) {
204: GeneralNameInterface current = getGeneralNameInterface(i);
205: boolean remove1 = false;
206:
207: /* compare current to subsequent elements */
208: for (int j = i + 1; j < size(); j++) {
209: GeneralNameInterface subsequent = getGeneralNameInterface(j);
210: switch (current.constrains(subsequent)) {
211: case GeneralNameInterface.NAME_DIFF_TYPE:
212: /* not comparable; different name types; keep checking */
213: continue;
214: case GeneralNameInterface.NAME_MATCH:
215: /* delete one of the duplicates */
216: remove1 = true;
217: break;
218: case GeneralNameInterface.NAME_NARROWS:
219: /* subsequent narrows current */
220: /* remove narrower name (subsequent) */
221: remove(j);
222: j--; /* continue check with new subsequent */
223: continue;
224: case GeneralNameInterface.NAME_WIDENS:
225: /* subsequent widens current */
226: /* remove narrower name current */
227: remove1 = true;
228: break;
229: case GeneralNameInterface.NAME_SAME_TYPE:
230: /* keep both for now; keep checking */
231: continue;
232: }
233: break;
234: } /* end of this pass of subsequent elements */
235:
236: if (remove1) {
237: remove(i);
238: i--; /* check the new i value */
239: }
240:
241: }
242: }
243:
244: /**
245: * create a subtree containing an instance of the input
246: * name type that widens all other names of that type.
247: *
248: * @params name GeneralNameInterface name
249: * @returns GeneralSubtree containing widest name of that type
250: * @throws RuntimeException on error (should not occur)
251: */
252: private GeneralSubtree createWidestSubtree(GeneralNameInterface name) {
253: try {
254: GeneralName newName;
255: switch (name.getType()) {
256: case GeneralNameInterface.NAME_ANY:
257: // Create new OtherName with same OID as baseName, but
258: // empty value
259: ObjectIdentifier otherOID = ((OtherName) name).getOID();
260: newName = new GeneralName(new OtherName(otherOID, null));
261: break;
262: case GeneralNameInterface.NAME_RFC822:
263: newName = new GeneralName(new RFC822Name(""));
264: break;
265: case GeneralNameInterface.NAME_DNS:
266: newName = new GeneralName(new DNSName(""));
267: break;
268: /*
269: * CDC/FP subsets X400Address into the security
270: * optional package.
271: case GeneralNameInterface.NAME_X400:
272: newName = new GeneralName(new X400Address((byte[])null));
273: break;
274: */
275: case GeneralNameInterface.NAME_DIRECTORY:
276: newName = new GeneralName(new X500Name(""));
277: break;
278: case GeneralNameInterface.NAME_EDI:
279: newName = new GeneralName(new EDIPartyName(""));
280: break;
281: case GeneralNameInterface.NAME_URI:
282: newName = new GeneralName(new URIName(""));
283: break;
284: case GeneralNameInterface.NAME_IP:
285: newName = new GeneralName(new IPAddressName(
286: (byte[]) null));
287: break;
288: case GeneralNameInterface.NAME_OID:
289: newName = new GeneralName(new OIDName(
290: new ObjectIdentifier((int[]) null)));
291: break;
292: default:
293: throw new IOException(
294: "Unsupported GeneralNameInterface type: "
295: + name.getType());
296: }
297: return new GeneralSubtree(newName, 0, -1);
298: } catch (IOException e) {
299: throw new RuntimeException("Unexpected error: " + e, e);
300: }
301: }
302:
303: /**
304: * intersect this GeneralSubtrees with other. This function
305: * is used in merging permitted NameConstraints. The operation
306: * is performed as follows:
307: * <ul>
308: * <li>If a name in other narrows all names of the same type in this,
309: * the result will contain the narrower name and none of the
310: * names it narrows.
311: * <li>If a name in other widens all names of the same type in this,
312: * the result will not contain the wider name.
313: * <li>If a name in other does not share the same subtree with any name
314: * of the same type in this, then the name is added to the list
315: * of GeneralSubtrees returned. These names should be added to
316: * the list of names that are specifically excluded. The reason
317: * is that, if the intersection is empty, then no names of that
318: * type are permitted, and the only way to express this in
319: * NameConstraints is to include the name in excludedNames.
320: * <li>If a name in this has no name of the same type in other, then
321: * the result contains the name in this. No name of a given type
322: * means the name type is completely permitted.
323: * <li>If a name in other has no name of the same type in this, then
324: * the result contains the name in other. This means that
325: * the name is now constrained in some way, whereas before it was
326: * completely permitted.
327: * <ul>
328: *
329: * @param other GeneralSubtrees to be intersected with this
330: * @returns GeneralSubtrees to be merged with excluded; these are
331: * empty-valued name types corresponding to entries that were
332: * of the same type but did not share the same subtree between
333: * this and other. Returns null if no such.
334: */
335: public GeneralSubtrees intersect(GeneralSubtrees other) {
336:
337: if (other == null) {
338: throw new NullPointerException(
339: "other GeneralSubtrees must not be null");
340: }
341:
342: GeneralSubtrees newThis = new GeneralSubtrees();
343: GeneralSubtrees newExcluded = null;
344:
345: // Step 1: If this is empty, just add everything in other to this and
346: // return no new excluded entries
347: if (size() == 0) {
348: union(other);
349: return null;
350: }
351:
352: // Step 2: For ease of checking the subtrees, minimize them by
353: // constructing versions that contain only the widest instance of
354: // each type
355: this .minimize();
356: other.minimize();
357:
358: // Step 3: Check each entry in this to see whether we keep it or
359: // remove it, and whether we add anything to newExcluded or newThis.
360: // We keep an entry in this unless it is narrowed by all entries in
361: // other. We add an entry to newExcluded if there is at least one
362: // entry of the same nameType in other, but this entry does
363: // not share the same subtree with any of the entries in other.
364: // We add an entry from other to newThis if there is no name of the
365: // same type in this.
366: for (int i = 0; i < size(); i++) {
367: GeneralNameInterface this Entry = getGeneralNameInterface(i);
368: boolean removeThisEntry = false;
369:
370: // Step 3a: If the widest name of this type in other narrows
371: // thisEntry, remove thisEntry and add widest other to newThis.
372: // Simultaneously, check for situation where there is a name of
373: // this type in other, but no name in other matches, narrows,
374: // or widens thisEntry.
375: boolean sameType = false;
376: for (int j = 0; j < other.size(); j++) {
377: GeneralSubtree otherEntryGS = other.get(j);
378: GeneralNameInterface otherEntry = getGeneralNameInterface(otherEntryGS);
379: switch (this Entry.constrains(otherEntry)) {
380: case NAME_NARROWS:
381: remove(i);
382: i--;
383: newThis.add(otherEntryGS);
384: sameType = false;
385: break;
386: case NAME_SAME_TYPE:
387: sameType = true;
388: continue;
389: case NAME_MATCH:
390: case NAME_WIDENS:
391: sameType = false;
392: break;
393: case NAME_DIFF_TYPE:
394: default:
395: continue;
396: }
397: break;
398: }
399:
400: // Step 3b: If sameType is still true, we have the situation
401: // where there was a name of the same type as thisEntry in
402: // other, but no name in other widened, matched, or narrowed
403: // thisEntry.
404: if (sameType) {
405:
406: // Step 3b.1: See if there are any entries in this and other
407: // with this type that match, widen, or narrow each other.
408: // If not, then we need to add a "widest subtree" of this
409: // type to excluded.
410: boolean intersection = false;
411: for (int j = 0; j < size(); j++) {
412: GeneralNameInterface this AltEntry = getGeneralNameInterface(j);
413:
414: if (this AltEntry.getType() == this Entry.getType()) {
415: for (int k = 0; k < other.size(); k++) {
416: GeneralNameInterface othAltEntry = other
417: .getGeneralNameInterface(k);
418:
419: int constraintType = this AltEntry
420: .constrains(othAltEntry);
421: if (constraintType == NAME_MATCH
422: || constraintType == NAME_WIDENS
423: || constraintType == NAME_NARROWS) {
424: intersection = true;
425: break;
426: }
427: }
428: }
429: }
430: if (intersection == false) {
431: if (newExcluded == null) {
432: newExcluded = new GeneralSubtrees();
433: }
434: GeneralSubtree widestSubtree = createWidestSubtree(this Entry);
435: if (!newExcluded.contains(widestSubtree)) {
436: newExcluded.add(widestSubtree);
437: }
438: }
439:
440: // Step 3b.2: Remove thisEntry from this
441: remove(i);
442: i--;
443: }
444: }
445:
446: // Step 4: Add all entries in newThis to this
447: if (newThis.size() > 0) {
448: union(newThis);
449: }
450:
451: // Step 5: Add all entries in other that do not have any entry of the
452: // same type in this to this
453: for (int i = 0; i < other.size(); i++) {
454: GeneralSubtree otherEntryGS = other.get(i);
455: GeneralNameInterface otherEntry = getGeneralNameInterface(otherEntryGS);
456: boolean diffType = false;
457: for (int j = 0; j < size(); j++) {
458: GeneralNameInterface this Entry = getGeneralNameInterface(j);
459: switch (this Entry.constrains(otherEntry)) {
460: case NAME_DIFF_TYPE:
461: diffType = true;
462: // continue to see if we find something later of the
463: // same type
464: continue;
465: case NAME_NARROWS:
466: case NAME_SAME_TYPE:
467: case NAME_MATCH:
468: case NAME_WIDENS:
469: diffType = false; // we found an entry of the same type
470: // break because we know we won't be adding it to
471: // this now
472: break;
473: default:
474: continue;
475: }
476: break;
477: }
478: if (diffType) {
479: add(otherEntryGS);
480: }
481: }
482:
483: // Step 6: Return the newExcluded GeneralSubtrees
484: return newExcluded;
485: }
486:
487: /**
488: * construct union of this GeneralSubtrees with other.
489: *
490: * @param other GeneralSubtrees to be united with this
491: */
492: public void union(GeneralSubtrees other) {
493: if (other != null) {
494: for (int i = 0, n = other.size(); i < n; i++) {
495: add(other.get(i));
496: }
497: // Minimize this
498: minimize();
499: }
500: }
501:
502: /**
503: * reduce this GeneralSubtrees by contents of another. This function
504: * is used in merging excluded NameConstraints with permitted NameConstraints
505: * to obtain a minimal form of permitted NameConstraints. It is an
506: * optimization, and does not affect correctness of the results.
507: *
508: * @param excluded GeneralSubtrees
509: */
510: public void reduce(GeneralSubtrees excluded) {
511: if (excluded == null) {
512: return;
513: }
514: for (int i = 0, n = excluded.size(); i < n; i++) {
515: GeneralNameInterface excludedName = excluded
516: .getGeneralNameInterface(i);
517: for (int j = 0; j < size(); j++) {
518: GeneralNameInterface permitted = getGeneralNameInterface(j);
519: switch (excludedName.constrains(permitted)) {
520: case GeneralNameInterface.NAME_DIFF_TYPE:
521: break;
522: case GeneralNameInterface.NAME_MATCH:
523: remove(j);
524: j--;
525: break;
526: case GeneralNameInterface.NAME_NARROWS:
527: /* permitted narrows excluded */
528: remove(j);
529: j--;
530: break;
531: case GeneralNameInterface.NAME_WIDENS:
532: /* permitted widens excluded */
533: break;
534: case GeneralNameInterface.NAME_SAME_TYPE:
535: break;
536: }
537: } /* end of this pass of permitted */
538: } /* end of pass of excluded */
539: }
540: }
|