151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Copyright (c) 1997, 2003, Oracle and/or its affiliates. All rights reserved. 351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is free software; you can redistribute it and/or modify it 651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under the terms of the GNU General Public License version 2 only, as 751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * published by the Free Software Foundation. Oracle designates this 851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * particular file as subject to the "Classpath" exception as provided 951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by Oracle in the LICENSE file that accompanied this code. 1051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is distributed in the hope that it will be useful, but WITHOUT 1251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version 2 for more details (a copy is included in the LICENSE file that 1551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * accompanied this code). 1651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * You should have received a copy of the GNU General Public License version 1851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2 along with this work; if not, write to the Free Software Foundation, 1951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or visit www.oracle.com if you need additional information or have any 2351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * questions. 2451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 2551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipackage sun.security.x509; 2751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport java.io.*; 2951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport java.util.*; 3051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport sun.security.util.*; 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Represent the GeneralSubtrees ASN.1 object. 3551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p> 3651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The ASN.1 for this is 3751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <pre> 3851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * GeneralSubtrees ::= SEQUENCE SIZE (1..MAX) OF GeneralSubtree 3951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </pre> 4051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </p> 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Amit Kapoor 4451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Hemma Prafullchandra 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Andreas Sterbenz 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic class GeneralSubtrees implements Cloneable { 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final List<GeneralSubtree> trees; 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Private variables 5251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int NAME_DIFF_TYPE = GeneralNameInterface.NAME_DIFF_TYPE; 5351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int NAME_MATCH = GeneralNameInterface.NAME_MATCH; 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int NAME_NARROWS = GeneralNameInterface.NAME_NARROWS; 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int NAME_WIDENS = GeneralNameInterface.NAME_WIDENS; 5651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int NAME_SAME_TYPE = GeneralNameInterface.NAME_SAME_TYPE; 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The default constructor for the class. 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 6151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public GeneralSubtrees() { 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski trees = new ArrayList<GeneralSubtree>(); 6351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private GeneralSubtrees(GeneralSubtrees source) { 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski trees = new ArrayList<GeneralSubtree>(source.trees); 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Create the object from the passed DER encoded form. 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param val the DER encoded form of the same. 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public GeneralSubtrees(DerValue val) throws IOException { 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this(); 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (val.tag != DerValue.tag_Sequence) { 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IOException("Invalid encoding of GeneralSubtrees."); 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 7951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (val.data.available() != 0) { 8051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski DerValue opt = val.data.getDerValue(); 8151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralSubtree tree = new GeneralSubtree(opt); 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski add(tree); 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public GeneralSubtree get(int index) { 8751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return trees.get(index); 8851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void remove(int index) { 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski trees.remove(index); 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 9351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void add(GeneralSubtree tree) { 9551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (tree == null) { 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NullPointerException(); 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski trees.add(tree); 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean contains(GeneralSubtree tree) { 10251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (tree == null) { 10351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NullPointerException(); 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return trees.contains(tree); 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int size() { 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return trees.size(); 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Iterator<GeneralSubtree> iterator() { 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return trees.iterator(); 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public List<GeneralSubtree> trees() { 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return trees; 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 12051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Object clone() { 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new GeneralSubtrees(this); 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Return a printable string of the GeneralSubtree. 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public String toString() { 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski String s = " GeneralSubtrees:\n" + trees.toString() + "\n"; 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return s; 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Encode the GeneralSubtrees. 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @params out the DerOutputStrean to encode this object to. 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void encode(DerOutputStream out) throws IOException { 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski DerOutputStream seq = new DerOutputStream(); 13951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 14051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0, n = size(); i < n; i++) { 14151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski get(i).encode(seq); 14251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 14351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski out.write(DerValue.tag_Sequence, seq); 14451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 14651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 14751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Compare two general subtrees by comparing the subtrees 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of each. 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 15051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param other GeneralSubtrees to compare to this 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @returns true if match 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean equals(Object obj) { 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (this == obj) { 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (obj instanceof GeneralSubtrees == false) { 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return false; 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralSubtrees other = (GeneralSubtrees)obj; 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return this.trees.equals(other.trees); 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 16451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int hashCode() { 16551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return trees.hashCode(); 16651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Return the GeneralNameInterface form of the GeneralName in one of 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the GeneralSubtrees. 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param ndx index of the GeneralSubtree from which to obtain the name 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private GeneralNameInterface getGeneralNameInterface(int ndx) { 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return getGeneralNameInterface(get(ndx)); 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static GeneralNameInterface getGeneralNameInterface(GeneralSubtree gs) { 17951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralName gn = gs.getName(); 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface gni = gn.getName(); 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return gni; 18251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 18551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * minimize this GeneralSubtrees by removing all redundant entries. 18651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Internal method used by intersect and reduce. 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void minimize() { 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 19051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Algorithm: compare each entry n to all subsequent entries in 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // the list: if any subsequent entry matches or widens entry n, 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // remove entry n. If any subsequent entries narrow entry n, remove 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // the subsequent entries. 1946d63dcb838153e1fa57dd0047485c576036e4a6aPrzemyslaw Szczepaniak for (int i = 0; i < (size() - 1); i++) { 19551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface current = getGeneralNameInterface(i); 19651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean remove1 = false; 19751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 19851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* compare current to subsequent elements */ 19951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = i + 1; j < size(); j++) { 20051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface subsequent = getGeneralNameInterface(j); 20151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski switch (current.constrains(subsequent)) { 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_DIFF_TYPE: 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* not comparable; different name types; keep checking */ 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski continue; 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_MATCH: 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* delete one of the duplicates */ 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove1 = true; 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_NARROWS: 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* subsequent narrows current */ 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* remove narrower name (subsequent) */ 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove(j); 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski j--; /* continue check with new subsequent */ 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski continue; 21551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_WIDENS: 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* subsequent widens current */ 21751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* remove narrower name current */ 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove1 = true; 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_SAME_TYPE: 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* keep both for now; keep checking */ 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski continue; 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } /* end of this pass of subsequent elements */ 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (remove1) { 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove(i); 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i--; /* check the new i value */ 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * create a subtree containing an instance of the input 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * name type that widens all other names of that type. 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @params name GeneralNameInterface name 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @returns GeneralSubtree containing widest name of that type 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws RuntimeException on error (should not occur) 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private GeneralSubtree createWidestSubtree(GeneralNameInterface name) { 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski try { 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralName newName; 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski switch (name.getType()) { 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_ANY: 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Create new OtherName with same OID as baseName, but 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // empty value 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ObjectIdentifier otherOID = ((OtherName)name).getOID(); 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new OtherName(otherOID, null)); 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_RFC822: 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new RFC822Name("")); 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_DNS: 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new DNSName("")); 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_X400: 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new X400Address((byte[])null)); 26151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 26251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_DIRECTORY: 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new X500Name("")); 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_EDI: 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new EDIPartyName("")); 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_URI: 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new URIName("")); 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_IP: 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName(new IPAddressName((byte[])null)); 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_OID: 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newName = new GeneralName 27651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (new OIDName(new ObjectIdentifier((int[])null))); 27751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 27851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski default: 27951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IOException 28051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ("Unsupported GeneralNameInterface type: " + name.getType()); 28151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 28251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new GeneralSubtree(newName, 0, -1); 28351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } catch (IOException e) { 28451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new RuntimeException("Unexpected error: " + e, e); 28551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 28651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 28751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 28851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * intersect this GeneralSubtrees with other. This function 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is used in merging permitted NameConstraints. The operation 29151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is performed as follows: 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <ul> 29351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <li>If a name in other narrows all names of the same type in this, 29451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the result will contain the narrower name and none of the 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * names it narrows. 29651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <li>If a name in other widens all names of the same type in this, 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the result will not contain the wider name. 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <li>If a name in other does not share the same subtree with any name 29951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the same type in this, then the name is added to the list 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of GeneralSubtrees returned. These names should be added to 30151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the list of names that are specifically excluded. The reason 30251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is that, if the intersection is empty, then no names of that 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * type are permitted, and the only way to express this in 30451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * NameConstraints is to include the name in excludedNames. 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <li>If a name in this has no name of the same type in other, then 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the result contains the name in this. No name of a given type 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * means the name type is completely permitted. 30851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <li>If a name in other has no name of the same type in this, then 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the result contains the name in other. This means that 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the name is now constrained in some way, whereas before it was 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * completely permitted. 31251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <ul> 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param other GeneralSubtrees to be intersected with this 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @returns GeneralSubtrees to be merged with excluded; these are 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * empty-valued name types corresponding to entries that were 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the same type but did not share the same subtree between 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this and other. Returns null if no such. 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public GeneralSubtrees intersect(GeneralSubtrees other) { 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (other == null) { 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NullPointerException("other GeneralSubtrees must not be null"); 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralSubtrees newThis = new GeneralSubtrees(); 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralSubtrees newExcluded = null; 32851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 1: If this is empty, just add everything in other to this and 33051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // return no new excluded entries 33151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (size() == 0) { 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski union(other); 33351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return null; 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 2: For ease of checking the subtrees, minimize them by 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // constructing versions that contain only the widest instance of 33851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // each type 33951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.minimize(); 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski other.minimize(); 34151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 3: Check each entry in this to see whether we keep it or 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // remove it, and whether we add anything to newExcluded or newThis. 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // We keep an entry in this unless it is narrowed by all entries in 34551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // other. We add an entry to newExcluded if there is at least one 34651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // entry of the same nameType in other, but this entry does 34751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // not share the same subtree with any of the entries in other. 34851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // We add an entry from other to newThis if there is no name of the 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // same type in this. 35051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < size(); i++) { 35151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface thisEntry = getGeneralNameInterface(i); 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removeThisEntry = false; 35351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 35451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 3a: If the widest name of this type in other narrows 35551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // thisEntry, remove thisEntry and add widest other to newThis. 35651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Simultaneously, check for situation where there is a name of 35751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // this type in other, but no name in other matches, narrows, 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // or widens thisEntry. 35951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean sameType = false; 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < other.size(); j++) { 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralSubtree otherEntryGS = other.get(j); 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface otherEntry = 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski getGeneralNameInterface(otherEntryGS); 36451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski switch (thisEntry.constrains(otherEntry)) { 36551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_NARROWS: 36651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove(i); 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i--; 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newThis.add(otherEntryGS); 36951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski sameType = false; 37051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_SAME_TYPE: 37251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski sameType = true; 37351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski continue; 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_MATCH: 37551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_WIDENS: 37651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski sameType = false; 37751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_DIFF_TYPE: 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski default: 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski continue; 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 3b: If sameType is still true, we have the situation 38651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // where there was a name of the same type as thisEntry in 38751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // other, but no name in other widened, matched, or narrowed 38851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // thisEntry. 38951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (sameType) { 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 3b.1: See if there are any entries in this and other 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // with this type that match, widen, or narrow each other. 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If not, then we need to add a "widest subtree" of this 39451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // type to excluded. 39551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean intersection = false; 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < size(); j++) { 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface thisAltEntry = getGeneralNameInterface(j); 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (thisAltEntry.getType() == thisEntry.getType()) { 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int k = 0; k < other.size(); k++) { 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface othAltEntry = 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski other.getGeneralNameInterface(k); 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int constraintType = 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski thisAltEntry.constrains(othAltEntry); 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (constraintType == NAME_MATCH || 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski constraintType == NAME_WIDENS || 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski constraintType == NAME_NARROWS) { 40951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski intersection = true; 41051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 41151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (intersection == false) { 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (newExcluded == null) { 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newExcluded = new GeneralSubtrees(); 41851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralSubtree widestSubtree = 42051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski createWidestSubtree(thisEntry); 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (!newExcluded.contains(widestSubtree)) { 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newExcluded.add(widestSubtree); 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 3b.2: Remove thisEntry from this 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove(i); 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i--; 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 43151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 4: Add all entries in newThis to this 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (newThis.size() > 0) { 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski union(newThis); 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 43651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 5: Add all entries in other that do not have any entry of the 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // same type in this to this 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < other.size(); i++) { 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralSubtree otherEntryGS = other.get(i); 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface otherEntry = getGeneralNameInterface(otherEntryGS); 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean diffType = false; 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < size(); j++) { 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface thisEntry = getGeneralNameInterface(j); 44551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski switch (thisEntry.constrains(otherEntry)) { 44651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_DIFF_TYPE: 44751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski diffType = true; 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // continue to see if we find something later of the 44951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // same type 45051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski continue; 45151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_NARROWS: 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_SAME_TYPE: 45351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_MATCH: 45451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case NAME_WIDENS: 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski diffType = false; // we found an entry of the same type 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // break because we know we won't be adding it to 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // this now 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski default: 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski continue; 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (diffType) { 46551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski add(otherEntryGS); 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 46751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 46851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Step 6: Return the newExcluded GeneralSubtrees 47051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return newExcluded; 47151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * construct union of this GeneralSubtrees with other. 47551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param other GeneralSubtrees to be united with this 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void union(GeneralSubtrees other) { 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (other != null) { 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0, n = other.size(); i < n; i++) { 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski add(other.get(i)); 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Minimize this 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski minimize(); 48551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * reduce this GeneralSubtrees by contents of another. This function 49051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is used in merging excluded NameConstraints with permitted NameConstraints 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to obtain a minimal form of permitted NameConstraints. It is an 49251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * optimization, and does not affect correctness of the results. 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param excluded GeneralSubtrees 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void reduce(GeneralSubtrees excluded) { 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (excluded == null) { 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0, n = excluded.size(); i < n; i++) { 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface excludedName = excluded.getGeneralNameInterface(i); 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < size(); j++) { 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski GeneralNameInterface permitted = getGeneralNameInterface(j); 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski switch (excludedName.constrains(permitted)) { 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_DIFF_TYPE: 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_MATCH: 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove(j); 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski j--; 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_NARROWS: 51251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* permitted narrows excluded */ 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski remove(j); 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski j--; 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_WIDENS: 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* permitted widens excluded */ 51851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 51951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case GeneralNameInterface.NAME_SAME_TYPE: 52051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 52151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 52251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } /* end of this pass of permitted */ 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } /* end of pass of excluded */ 52451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 52551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 526