/*

 * 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.provider.certpath;

import java.io.IOException;

import java.security.GeneralSecurityException;

import java.security.InvalidAlgorithmParameterException;

import java.security.PublicKey;

import java.security.cert.*;

import java.security.cert.CertPathValidatorException.BasicReason;

import java.security.cert.PKIXReason;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Collections;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.LinkedList;

import java.util.Set;

import javax.security.auth.x500.X500Principal;

import sun.security.provider.certpath.PKIX.BuilderParams;

import static sun.security.x509.PKIXExtensions.*;

import sun.security.util.Debug;

/**

 * This class is able to build certification paths in either the forward

 * or reverse directions.

 *

 * <p> If successful, it returns a certification path which has successfully

 * satisfied all the constraints and requirements specified in the

 * PKIXBuilderParameters object and has been validated according to the PKIX

 * path validation algorithm defined in RFC 5280.

 *

 * <p> This implementation uses a depth-first search approach to finding

 * certification paths. If it comes to a point in which it cannot find

 * any more certificates leading to the target OR the path length is too long

 * it backtracks to previous paths until the target has been found or

 * all possible paths have been exhausted.

 *

 * <p> This implementation is not thread-safe.

 *

 * @since       1.4

 * @author      Sean Mullan

 * @author      Yassir Elley

 */

public final class SunCertPathBuilder extends CertPathBuilderSpi {

    private static final Debug debug = Debug.getInstance("certpath");

    /*

     * private objects shared by methods

     */

    private BuilderParams buildParams;

    private CertificateFactory cf;

    private boolean pathCompleted = false;

    private PolicyNode policyTreeResult;

    private TrustAnchor trustAnchor;

    private PublicKey finalPublicKey;

    /**

     * Create an instance of <code>SunCertPathBuilder</code>.

     *

     * @throws CertPathBuilderException if an error occurs

     */

    public SunCertPathBuilder() throws CertPathBuilderException {

        try {

            cf = CertificateFactory.getInstance("X.509");

        } catch (CertificateException e) {

            throw new CertPathBuilderException(e);

        }

    }

    @Override

    public CertPathChecker engineGetRevocationChecker() {

        return new RevocationChecker();

    }

    /**

     * Attempts to build a certification path using the Sun build

     * algorithm from a trusted anchor(s) to a target subject, which must both

     * be specified in the input parameter set. By default, this method will

     * attempt to build in the forward direction. In order to build in the

     * reverse direction, the caller needs to pass in an instance of

     * SunCertPathBuilderParameters with the buildForward flag set to false.

     *

     * <p>The certification path that is constructed is validated

     * according to the PKIX specification.

     *

     * @param params the parameter set for building a path. Must be an instance

     *  of <code>PKIXBuilderParameters</code>.

     * @return a certification path builder result.

     * @exception CertPathBuilderException Exception thrown if builder is

     *  unable to build a complete certification path from the trusted anchor(s)

     *  to the target subject.

     * @throws InvalidAlgorithmParameterException if the given parameters are

     *  inappropriate for this certification path builder.

     */

    @Override

    public CertPathBuilderResult engineBuild(CertPathParameters params)

        throws CertPathBuilderException, InvalidAlgorithmParameterException {

        if (debug != null) {

            debug.println("SunCertPathBuilder.engineBuild(" + params + ")");

        }

        buildParams = PKIX.checkBuilderParams(params);

        return build();

    }

    private PKIXCertPathBuilderResult build() throws CertPathBuilderException {

        List<List<Vertex>> adjList = new ArrayList<>();

        PKIXCertPathBuilderResult result = buildCertPath(false, adjList);

        if (result == null) {

            if (debug != null) {

            }

            // try again

            adjList.clear();

            result = buildCertPath(true, adjList);

            if (result == null) {

                throw new SunCertPathBuilderException("unable to find valid "

                    + "certification path to requested target",

                    new AdjacencyList(adjList));

            }

        }

        return result;

    }

    private PKIXCertPathBuilderResult buildCertPath(boolean searchAllCertStores,

                                                    List<List<Vertex>> adjList)

        throws CertPathBuilderException

    {

        // Init shared variables and build certification path

        pathCompleted = false;

        trustAnchor = null;

        finalPublicKey = null;

        policyTreeResult = null;

        LinkedList<X509Certificate> certPathList = new LinkedList<>();

        try {

            if (buildParams.buildForward()) {

                buildForward(adjList, certPathList, searchAllCertStores);

            } else {

                buildReverse(adjList, certPathList);

            }

        } catch (GeneralSecurityException | IOException e) {

            if (debug != null) {

                debug.println("SunCertPathBuilder.engineBuild() exception in "

                    + "build");

                e.printStackTrace();

            }

            throw new SunCertPathBuilderException("unable to find valid "

                + "certification path to requested target", e,

                new AdjacencyList(adjList));

        }

        // construct SunCertPathBuilderResult

        try {

            if (pathCompleted) {

                if (debug != null)

                    debug.println("SunCertPathBuilder.engineBuild() "

                                  + "pathCompleted");

                // we must return a certpath which has the target

                // as the first cert in the certpath - i.e. reverse

                // the certPathList

                Collections.reverse(certPathList);

                return new SunCertPathBuilderResult(

                    cf.generateCertPath(certPathList), trustAnchor,

                    policyTreeResult, finalPublicKey,

                    new AdjacencyList(adjList));

            }

        } catch (CertificateException e) {

            if (debug != null) {

                debug.println("SunCertPathBuilder.engineBuild() exception "

                              + "in wrap-up");

                e.printStackTrace();

            }

            throw new SunCertPathBuilderException("unable to find valid "

                + "certification path to requested target", e,

                new AdjacencyList(adjList));

        }

        return null;

    }

    /*

     * Private build reverse method.

     */

    private void buildReverse(List<List<Vertex>> adjacencyList,

                              LinkedList<X509Certificate> certPathList)

        throws GeneralSecurityException, IOException

    {

        if (debug != null) {

            debug.println("SunCertPathBuilder.buildReverse()...");

            debug.println("SunCertPathBuilder.buildReverse() InitialPolicies: "

                + buildParams.initialPolicies());

        }

        ReverseState currentState = new ReverseState();

        /* Initialize adjacency list */

        adjacencyList.clear();

        adjacencyList.add(new LinkedList<Vertex>());

        /*

         * Perform a search using each trust anchor, until a valid

         * path is found

         */

        Iterator<TrustAnchor> iter = buildParams.trustAnchors().iterator();

        while (iter.hasNext()) {

            TrustAnchor anchor = iter.next();

            /* check if anchor satisfies target constraints */

            if (anchorIsTarget(anchor, buildParams.targetCertConstraints())) {

                this.trustAnchor = anchor;

                this.pathCompleted = true;

                this.finalPublicKey = anchor.getTrustedCert().getPublicKey();

                break;

            }

            // skip anchor if it contains a DSA key with no DSA params

            X509Certificate trustedCert = anchor.getTrustedCert();

            PublicKey pubKey = trustedCert != null ? trustedCert.getPublicKey()

                                                   : anchor.getCAPublicKey();

            if (PKIX.isDSAPublicKeyWithoutParams(pubKey)) {

                continue;

            }

            /* Initialize current state */

            currentState.initState(buildParams);

            currentState.updateState(anchor, buildParams);

            currentState.algorithmChecker = new AlgorithmChecker(anchor);

            currentState.untrustedChecker = new UntrustedChecker();

            try {

                depthFirstSearchReverse(null, currentState,

                                        new ReverseBuilder(buildParams),

                                        adjacencyList, certPathList);

            } catch (GeneralSecurityException | IOException e) {

                // continue on error if more anchors to try

                if (iter.hasNext())

                    continue;

                else

                    throw e;

            }

            // break out of loop if search is successful

            if (pathCompleted) {

                break;

            }

        }

        if (debug != null) {

            debug.println("SunCertPathBuilder.buildReverse() returned from "

                + "depthFirstSearchReverse()");

            debug.println("SunCertPathBuilder.buildReverse() "

                + "certPathList.size: " + certPathList.size());

        }

    }

    /*

     * Private build forward method.

     */

    private void buildForward(List<List<Vertex>> adjacencyList,

                              LinkedList<X509Certificate> certPathList,

                              boolean searchAllCertStores)

        throws GeneralSecurityException, IOException

    {

        if (debug != null) {

            debug.println("SunCertPathBuilder.buildForward()...");

        }

        /* Initialize current state */

        ForwardState currentState = new ForwardState();

        currentState.initState(buildParams.certPathCheckers());

        /* Initialize adjacency list */

        adjacencyList.clear();

        adjacencyList.add(new LinkedList<Vertex>());

        currentState.untrustedChecker = new UntrustedChecker();

        depthFirstSearchForward(buildParams.targetSubject(), currentState,

                                new ForwardBuilder(buildParams,

                                                   searchAllCertStores),

                                adjacencyList, certPathList);

    }

    /*

     * This method performs a depth first search for a certification

     * path while building forward which meets the requirements set in

     * the parameters object.

     * It uses an adjacency list to store all certificates which were

     * tried (i.e. at one time added to the path - they may not end up in

     * the final path if backtracking occurs). This information can

     * be used later to debug or demo the build.

     *

     * See "Data Structure and Algorithms, by Aho, Hopcroft, and Ullman"

     * for an explanation of the DFS algorithm.

     *

     * @param dN the distinguished name being currently searched for certs

     * @param currentState the current PKIX validation state

     */

    private void depthFirstSearchForward(X500Principal dN,

                                         ForwardState currentState,

                                         ForwardBuilder builder,

                                         List<List<Vertex>> adjList,

                                         LinkedList<X509Certificate> cpList)

        throws GeneralSecurityException, IOException

    {

        if (debug != null) {

            debug.println("SunCertPathBuilder.depthFirstSearchForward(" + dN

                          + ", " + currentState.toString() + ")");

        }

        /*

         * Find all the certificates issued to dN which

         * satisfy the PKIX certification path constraints.

         */

        Collection<X509Certificate> certs =

            builder.getMatchingCerts(currentState, buildParams.certStores());

        List<Vertex> vertices = addVertices(certs, adjList);

        if (debug != null) {

            debug.println("SunCertPathBuilder.depthFirstSearchForward(): "

                          + "certs.size=" + vertices.size());

        }

        /*

         * For each cert in the collection, verify anything

         * that hasn't been checked yet (signature, revocation, etc)

         * and check for loops. Call depthFirstSearchForward()

         * recursively for each good cert.

         */

               vertices:

        for (Vertex vertex : vertices) {

            /**

             * Restore state to currentState each time through the loop.

             * This is important because some of the user-defined

             * checkers modify the state, which MUST be restored if

             * the cert eventually fails to lead to the target and

             * the next matching cert is tried.

             */

            ForwardState nextState = (ForwardState) currentState.clone();

            X509Certificate cert = vertex.getCertificate();

            try {

                builder.verifyCert(cert, nextState, cpList);

            } catch (GeneralSecurityException gse) {

                if (debug != null) {

                    debug.println("SunCertPathBuilder.depthFirstSearchForward()"

                                  + ": validation failed: " + gse);

                    gse.printStackTrace();

                }

                vertex.setThrowable(gse);

                continue;

            }

            /*

             * Certificate is good.

             * If cert completes the path,

             *    process userCheckers that don't support forward checking

             *    and process policies over whole path

             *    and backtrack appropriately if there is a failure

             * else if cert does not complete the path,

             *    add it to the path

             */

            if (builder.isPathCompleted(cert)) {

                if (debug != null)

                    debug.println("SunCertPathBuilder.depthFirstSearchForward()"

                                  + ": commencing final verification");

                List<X509Certificate> appendedCerts = new ArrayList<>(cpList);

                /*

                 * if the trust anchor selected is specified as a trusted

                 * public key rather than a trusted cert, then verify this

                 * cert (which is signed by the trusted public key), but

                 * don't add it yet to the cpList

                 */

                if (builder.trustAnchor.getTrustedCert() == null) {

                    appendedCerts.add(0, cert);

                }

                Set<String> initExpPolSet =

                    Collections.singleton(PolicyChecker.ANY_POLICY);

                PolicyNodeImpl rootNode = new PolicyNodeImpl(null,

                    PolicyChecker.ANY_POLICY, null, false, initExpPolSet, false);

                List<PKIXCertPathChecker> checkers = new ArrayList<>();

                PolicyChecker policyChecker

                    = new PolicyChecker(buildParams.initialPolicies(),

                                        appendedCerts.size(),

                                        buildParams.explicitPolicyRequired(),

                                        buildParams.policyMappingInhibited(),

                                        buildParams.anyPolicyInhibited(),

                                        buildParams.policyQualifiersRejected(),

                                        rootNode);

                checkers.add(policyChecker);

                // add the algorithm checker

                checkers.add(new AlgorithmChecker(builder.trustAnchor));

                BasicChecker basicChecker = null;

                if (nextState.keyParamsNeeded()) {

                    PublicKey rootKey = cert.getPublicKey();

                    if (builder.trustAnchor.getTrustedCert() == null) {

                        rootKey = builder.trustAnchor.getCAPublicKey();

                        if (debug != null)

                            debug.println(

                                "SunCertPathBuilder.depthFirstSearchForward " +

                                "using buildParams public key: " +

                                rootKey.toString());

                    }

                    TrustAnchor anchor = new TrustAnchor

                        (cert.getSubjectX500Principal(), rootKey, null);

                    // add the basic checker

                    basicChecker = new BasicChecker(anchor, buildParams.date(),

                                                    buildParams.sigProvider(),

                                                    true);

                    checkers.add(basicChecker);

                }

                buildParams.setCertPath(cf.generateCertPath(appendedCerts));

                boolean revCheckerAdded = false;

                List<PKIXCertPathChecker> ckrs = buildParams.certPathCheckers();

                for (PKIXCertPathChecker ckr : ckrs) {

                    if (ckr instanceof PKIXRevocationChecker) {

                        if (revCheckerAdded) {

                            throw new CertPathValidatorException(

                                "Only one PKIXRevocationChecker can be specified");

                        }

                        revCheckerAdded = true;

                        // if it's our own, initialize it

                        if (ckr instanceof RevocationChecker) {

                            ((RevocationChecker)ckr).init(builder.trustAnchor,

                                                          buildParams);

                        }

                    }

                }

                // only add a RevocationChecker if revocation is enabled and

                // a PKIXRevocationChecker has not already been added

                if (buildParams.revocationEnabled() && !revCheckerAdded) {

                    checkers.add(new RevocationChecker(builder.trustAnchor,

                                                       buildParams));

                }

                checkers.addAll(ckrs);

                // Why we don't need BasicChecker and RevocationChecker

                // if nextState.keyParamsNeeded() is false?

                for (int i = 0; i < appendedCerts.size(); i++) {

                    X509Certificate currCert = appendedCerts.get(i);

                    if (debug != null)

                        debug.println("current subject = "

                                      + currCert.getSubjectX500Principal());

                    Set<String> unresCritExts =

                        currCert.getCriticalExtensionOIDs();

                    if (unresCritExts == null) {

                        unresCritExts = Collections.<String>emptySet();

                    }

                    for (PKIXCertPathChecker currChecker : checkers) {

                        if (!currChecker.isForwardCheckingSupported()) {

                            if (i == 0) {

                                currChecker.init(false);

                                // The user specified

                                // AlgorithmChecker may not be

                                // able to set the trust anchor until now.

                                if (currChecker instanceof AlgorithmChecker) {

                                    ((AlgorithmChecker)currChecker).

                                        trySetTrustAnchor(builder.trustAnchor);

                                }

                            }

                            try {

                                currChecker.check(currCert, unresCritExts);

                            } catch (CertPathValidatorException cpve) {