/*

 * 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>

 *

 *

 * @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<>();

    }

    private GeneralSubtrees(GeneralSubtrees source) {

        trees = new ArrayList<>(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() {

        return "   GeneralSubtrees:\n" + trees + '\n';

    }

    /**

     * Encode the GeneralSubtrees.

     *

     * @param 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 obj GeneralSubtrees to compare to this

     * @return 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.

     *

     * @param name GeneralNameInterface name

     * @return 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

     * @return  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 */

    }

}