Back to index...

	/*
	* Copyright (c) 1997, 2003, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package sun.security.x509;

	import java.io.*;
	import java.util.*;

	import sun.security.util.*;

	/**
	* Represent the GeneralSubtrees ASN.1 object.
	* <p>
	* The ASN.1 for this is
	* <pre>
	* GeneralSubtrees ::= SEQUENCE SIZE (1..MAX) OF GeneralSubtree
	* </pre>
	* </p>
	*
	*
	* @author Amit Kapoor
	* @author Hemma Prafullchandra
	* @author Andreas Sterbenz
	*/
	public class GeneralSubtrees implements Cloneable {

	private final List<GeneralSubtree> trees;

	// Private variables
	private static final int NAME_DIFF_TYPE = GeneralNameInterface.NAME_DIFF_TYPE;
	private static final int NAME_MATCH = GeneralNameInterface.NAME_MATCH;
	private static final int NAME_NARROWS = GeneralNameInterface.NAME_NARROWS;
	private static final int NAME_WIDENS = GeneralNameInterface.NAME_WIDENS;
	private static final int NAME_SAME_TYPE = GeneralNameInterface.NAME_SAME_TYPE;

	/**
	* The default constructor for the class.
	*/
	public GeneralSubtrees() {
	trees = new ArrayList<GeneralSubtree>();
	}

	private GeneralSubtrees(GeneralSubtrees source) {
	trees = new ArrayList<GeneralSubtree>(source.trees);
	}

	/**
	* Create the object from the passed DER encoded form.
	*
	* @param val the DER encoded form of the same.
	*/
	public GeneralSubtrees(DerValue val) throws IOException {
	this();
	if (val.tag != DerValue.tag_Sequence) {
	throw new IOException("Invalid encoding of GeneralSubtrees.");
	}
	while (val.data.available() != 0) {
	DerValue opt = val.data.getDerValue();
	GeneralSubtree tree = new GeneralSubtree(opt);
	add(tree);
	}
	}

	public GeneralSubtree get(int index) {
	return trees.get(index);
	}

	public void remove(int index) {
	trees.remove(index);
	}

	public void add(GeneralSubtree tree) {
	if (tree == null) {
	throw new NullPointerException();
	}
	trees.add(tree);
	}

	public boolean contains(GeneralSubtree tree) {
	if (tree == null) {
	throw new NullPointerException();
	}
	return trees.contains(tree);
	}

	public int size() {
	return trees.size();
	}

	public Iterator<GeneralSubtree> iterator() {
	return trees.iterator();
	}

	public List<GeneralSubtree> trees() {
	return trees;
	}

	public Object clone() {
	return new GeneralSubtrees(this);
	}

	/**
	* Return a printable string of the GeneralSubtree.
	*/
	public String toString() {
	String s = " GeneralSubtrees:\n" + trees.toString() + "\n";
	return s;
	}

	/**
	* Encode the GeneralSubtrees.
	*
	* @params out the DerOutputStrean to encode this object to.
	*/
	public void encode(DerOutputStream out) throws IOException {
	DerOutputStream seq = new DerOutputStream();

	for (int i = 0, n = size(); i < n; i++) {
	get(i).encode(seq);
	}
	out.write(DerValue.tag_Sequence, seq);
	}

	/**
	* Compare two general subtrees by comparing the subtrees
	* of each.
	*
	* @param other GeneralSubtrees to compare to this
	* @returns true if match
	*/
	public boolean equals(Object obj) {
	if (this == obj) {
	return true;
	}
	if (obj instanceof GeneralSubtrees == false) {
	return false;
	}
	GeneralSubtrees other = (GeneralSubtrees)obj;
	return this.trees.equals(other.trees);
	}

	public int hashCode() {
	return trees.hashCode();
	}

	/**
	* Return the GeneralNameInterface form of the GeneralName in one of
	* the GeneralSubtrees.
	*
	* @param ndx index of the GeneralSubtree from which to obtain the name
	*/
	private GeneralNameInterface getGeneralNameInterface(int ndx) {
	return getGeneralNameInterface(get(ndx));
	}

	private static GeneralNameInterface getGeneralNameInterface(GeneralSubtree gs) {
	GeneralName gn = gs.getName();
	GeneralNameInterface gni = gn.getName();
	return gni;
	}

	/**
	* minimize this GeneralSubtrees by removing all redundant entries.
	* Internal method used by intersect and reduce.
	*/
	private void minimize() {

	// Algorithm: compare each entry n to all subsequent entries in
	// the list: if any subsequent entry matches or widens entry n,
	// remove entry n. If any subsequent entries narrow entry n, remove
	// the subsequent entries.
	for (int i = 0; i < (size() - 1); i++) {
	GeneralNameInterface current = getGeneralNameInterface(i);
	boolean remove1 = false;

	/* compare current to subsequent elements */
	for (int j = i + 1; j < size(); j++) {
	GeneralNameInterface subsequent = getGeneralNameInterface(j);
	switch (current.constrains(subsequent)) {
	case GeneralNameInterface.NAME_DIFF_TYPE:
	/* not comparable; different name types; keep checking */
	continue;
	case GeneralNameInterface.NAME_MATCH:
	/* delete one of the duplicates */
	remove1 = true;
	break;
	case GeneralNameInterface.NAME_NARROWS:
	/* subsequent narrows current */
	/* remove narrower name (subsequent) */
	remove(j);
	j--; /* continue check with new subsequent */
	continue;
	case GeneralNameInterface.NAME_WIDENS:
	/* subsequent widens current */
	/* remove narrower name current */
	remove1 = true;
	break;
	case GeneralNameInterface.NAME_SAME_TYPE:
	/* keep both for now; keep checking */
	continue;
	}
	break;
	} /* end of this pass of subsequent elements */

	if (remove1) {
	remove(i);
	i--; /* check the new i value */
	}

	}
	}

	/**
	* create a subtree containing an instance of the input
	* name type that widens all other names of that type.
	*
	* @params name GeneralNameInterface name
	* @returns GeneralSubtree containing widest name of that type
	* @throws RuntimeException on error (should not occur)
	*/
	private GeneralSubtree createWidestSubtree(GeneralNameInterface name) {
	try {
	GeneralName newName;
	switch (name.getType()) {
	case GeneralNameInterface.NAME_ANY:
	// Create new OtherName with same OID as baseName, but
	// empty value
	ObjectIdentifier otherOID = ((OtherName)name).getOID();
	newName = new GeneralName(new OtherName(otherOID, null));
	break;
	case GeneralNameInterface.NAME_RFC822:
	newName = new GeneralName(new RFC822Name(""));
	break;
	case GeneralNameInterface.NAME_DNS:
	newName = new GeneralName(new DNSName(""));
	break;
	case GeneralNameInterface.NAME_X400:
	newName = new GeneralName(new X400Address((byte[])null));
	break;
	case GeneralNameInterface.NAME_DIRECTORY:
	newName = new GeneralName(new X500Name(""));
	break;
	case GeneralNameInterface.NAME_EDI:
	newName = new GeneralName(new EDIPartyName(""));
	break;
	case GeneralNameInterface.NAME_URI:
	newName = new GeneralName(new URIName(""));
	break;
	case GeneralNameInterface.NAME_IP:
	newName = new GeneralName(new IPAddressName((byte[])null));
	break;
	case GeneralNameInterface.NAME_OID:
	newName = new GeneralName
	(new OIDName(new ObjectIdentifier((int[])null)));
	break;
	default:
	throw new IOException
	("Unsupported GeneralNameInterface type: " + name.getType());
	}
	return new GeneralSubtree(newName, 0, -1);
	} catch (IOException e) {
	throw new RuntimeException("Unexpected error: " + e, e);
	}
	}

	/**
	* intersect this GeneralSubtrees with other. This function
	* is used in merging permitted NameConstraints. The operation
	* is performed as follows:
	* <ul>
	* <li>If a name in other narrows all names of the same type in this,
	* the result will contain the narrower name and none of the
	* names it narrows.
	* <li>If a name in other widens all names of the same type in this,
	* the result will not contain the wider name.
	* <li>If a name in other does not share the same subtree with any name
	* of the same type in this, then the name is added to the list
	* of GeneralSubtrees returned. These names should be added to
	* the list of names that are specifically excluded. The reason
	* is that, if the intersection is empty, then no names of that
	* type are permitted, and the only way to express this in
	* NameConstraints is to include the name in excludedNames.
	* <li>If a name in this has no name of the same type in other, then
	* the result contains the name in this. No name of a given type
	* means the name type is completely permitted.
	* <li>If a name in other has no name of the same type in this, then
	* the result contains the name in other. This means that
	* the name is now constrained in some way, whereas before it was
	* completely permitted.
	* <ul>
	*
	* @param other GeneralSubtrees to be intersected with this
	* @returns GeneralSubtrees to be merged with excluded; these are
	* empty-valued name types corresponding to entries that were
	* of the same type but did not share the same subtree between
	* this and other. Returns null if no such.
	*/
	public GeneralSubtrees intersect(GeneralSubtrees other) {

	if (other == null) {
	throw new NullPointerException("other GeneralSubtrees must not be null");
	}

	GeneralSubtrees newThis = new GeneralSubtrees();
	GeneralSubtrees newExcluded = null;

	// Step 1: If this is empty, just add everything in other to this and
	// return no new excluded entries
	if (size() == 0) {
	union(other);
	return null;
	}

	// Step 2: For ease of checking the subtrees, minimize them by
	// constructing versions that contain only the widest instance of
	// each type
	this.minimize();
	other.minimize();

	// Step 3: Check each entry in this to see whether we keep it or
	// remove it, and whether we add anything to newExcluded or newThis.
	// We keep an entry in this unless it is narrowed by all entries in
	// other. We add an entry to newExcluded if there is at least one
	// entry of the same nameType in other, but this entry does
	// not share the same subtree with any of the entries in other.
	// We add an entry from other to newThis if there is no name of the
	// same type in this.
	for (int i = 0; i < size(); i++) {
	GeneralNameInterface thisEntry = getGeneralNameInterface(i);
	boolean removeThisEntry = false;

	// Step 3a: If the widest name of this type in other narrows
	// thisEntry, remove thisEntry and add widest other to newThis.
	// Simultaneously, check for situation where there is a name of
	// this type in other, but no name in other matches, narrows,
	// or widens thisEntry.
	boolean sameType = false;
	for (int j = 0; j < other.size(); j++) {
	GeneralSubtree otherEntryGS = other.get(j);
	GeneralNameInterface otherEntry =
	getGeneralNameInterface(otherEntryGS);
	switch (thisEntry.constrains(otherEntry)) {
	case NAME_NARROWS:
	remove(i);
	i--;
	newThis.add(otherEntryGS);
	sameType = false;
	break;
	case NAME_SAME_TYPE:
	sameType = true;
	continue;
	case NAME_MATCH:
	case NAME_WIDENS:
	sameType = false;
	break;
	case NAME_DIFF_TYPE:
	default:
	continue;
	}
	break;
	}

	// Step 3b: If sameType is still true, we have the situation
	// where there was a name of the same type as thisEntry in
	// other, but no name in other widened, matched, or narrowed
	// thisEntry.
	if (sameType) {

	// Step 3b.1: See if there are any entries in this and other
	// with this type that match, widen, or narrow each other.
	// If not, then we need to add a "widest subtree" of this
	// type to excluded.
	boolean intersection = false;
	for (int j = 0; j < size(); j++) {
	GeneralNameInterface thisAltEntry = getGeneralNameInterface(j);

	if (thisAltEntry.getType() == thisEntry.getType()) {
	for (int k = 0; k < other.size(); k++) {
	GeneralNameInterface othAltEntry =
	other.getGeneralNameInterface(k);

	int constraintType =
	thisAltEntry.constrains(othAltEntry);
	if (constraintType == NAME_MATCH \|\|
	constraintType == NAME_WIDENS \|\|
	constraintType == NAME_NARROWS) {
	intersection = true;
	break;
	}
	}
	}
	}
	if (intersection == false) {
	if (newExcluded == null) {
	newExcluded = new GeneralSubtrees();
	}
	GeneralSubtree widestSubtree =
	createWidestSubtree(thisEntry);
	if (!newExcluded.contains(widestSubtree)) {
	newExcluded.add(widestSubtree);
	}
	}

	// Step 3b.2: Remove thisEntry from this
	remove(i);
	i--;
	}
	}

	// Step 4: Add all entries in newThis to this
	if (newThis.size() > 0) {
	union(newThis);
	}

	// Step 5: Add all entries in other that do not have any entry of the
	// same type in this to this
	for (int i = 0; i < other.size(); i++) {
	GeneralSubtree otherEntryGS = other.get(i);
	GeneralNameInterface otherEntry = getGeneralNameInterface(otherEntryGS);
	boolean diffType = false;
	for (int j = 0; j < size(); j++) {
	GeneralNameInterface thisEntry = getGeneralNameInterface(j);
	switch (thisEntry.constrains(otherEntry)) {
	case NAME_DIFF_TYPE:
	diffType = true;
	// continue to see if we find something later of the
	// same type
	continue;
	case NAME_NARROWS:
	case NAME_SAME_TYPE:
	case NAME_MATCH:
	case NAME_WIDENS:
	diffType = false; // we found an entry of the same type
	// break because we know we won't be adding it to
	// this now
	break;
	default:
	continue;
	}
	break;
	}
	if (diffType) {
	add(otherEntryGS);
	}
	}

	// Step 6: Return the newExcluded GeneralSubtrees
	return newExcluded;
	}

	/**
	* construct union of this GeneralSubtrees with other.
	*
	* @param other GeneralSubtrees to be united with this
	*/
	public void union(GeneralSubtrees other) {
	if (other != null) {
	for (int i = 0, n = other.size(); i < n; i++) {
	add(other.get(i));
	}
	// Minimize this
	minimize();
	}
	}

	/**
	* reduce this GeneralSubtrees by contents of another. This function
	* is used in merging excluded NameConstraints with permitted NameConstraints
	* to obtain a minimal form of permitted NameConstraints. It is an
	* optimization, and does not affect correctness of the results.
	*
	* @param excluded GeneralSubtrees
	*/
	public void reduce(GeneralSubtrees excluded) {
	if (excluded == null) {
	return;
	}
	for (int i = 0, n = excluded.size(); i < n; i++) {
	GeneralNameInterface excludedName = excluded.getGeneralNameInterface(i);
	for (int j = 0; j < size(); j++) {
	GeneralNameInterface permitted = getGeneralNameInterface(j);
	switch (excludedName.constrains(permitted)) {
	case GeneralNameInterface.NAME_DIFF_TYPE:
	break;
	case GeneralNameInterface.NAME_MATCH:
	remove(j);
	j--;
	break;
	case GeneralNameInterface.NAME_NARROWS:
	/* permitted narrows excluded */
	remove(j);
	j--;
	break;
	case GeneralNameInterface.NAME_WIDENS:
	/* permitted widens excluded */
	break;
	case GeneralNameInterface.NAME_SAME_TYPE:
	break;
	}
	} /* end of this pass of permitted */
	} /* end of pass of excluded */
	}
	}

Back to index...