/*

 * Copyright (c) 2002, 2012, 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.provider.certpath;

import java.util.*;

import java.security.InvalidAlgorithmParameterException;

import java.security.cert.*;

import javax.security.auth.x500.X500Principal;

/**

 * A <code>CertStore</code> that retrieves <code>Certificates</code> and

 * <code>CRL</code>s from a <code>Collection</code>.

 * <p>

 * This implementation is functionally equivalent to CollectionCertStore

 * with two differences:

 * <ol>

 * <li>Upon construction, the elements in the specified Collection are

 * partially indexed. X509Certificates are indexed by subject, X509CRLs

 * by issuer, non-X509 Certificates and CRLs are copied without indexing,

 * other objects are ignored. This increases CertStore construction time

 * but allows significant speedups for searches which specify the indexed

 * attributes, in particular for large Collections (reduction from linear

 * time to effectively constant time). Searches for non-indexed queries

 * are as fast (or marginally faster) than for the standard

 * CollectionCertStore. Certificate subjects and CRL issuers

 * were found to be specified in most searches used internally by the

 * CertPath provider. Additional attributes could indexed if there are

 * queries that justify the effort.

 *

 * <li>Changes to the specified Collection after construction time are

 * not detected and ignored. This is because there is no way to efficiently

 * detect if a Collection has been modified, a full traversal would be

 * required. That would degrade lookup performance to linear time and

 * eliminated the benefit of indexing. We may fix this via the introduction

 * of new public APIs in the future.

 * </ol>

 * <p>

 * Before calling the {@link #engineGetCertificates engineGetCertificates} or

 * {@link #engineGetCRLs engineGetCRLs} methods, the

 * {@link #CollectionCertStore(CertStoreParameters)

 * CollectionCertStore(CertStoreParameters)} constructor is called to

 * create the <code>CertStore</code> and establish the

 * <code>Collection</code> from which <code>Certificate</code>s and

 * <code>CRL</code>s will be retrieved. If the specified

 * <code>Collection</code> contains an object that is not a

 * <code>Certificate</code> or <code>CRL</code>, that object will be

 * ignored.

 * <p>

 * <b>Concurrent Access</b>

 * <p>

 * As described in the javadoc for <code>CertStoreSpi</code>, the

 * <code>engineGetCertificates</code> and <code>engineGetCRLs</code> methods

 * must be thread-safe. That is, multiple threads may concurrently

 * invoke these methods on a single <code>CollectionCertStore</code>

 * object (or more than one) with no ill effects.

 * <p>

 * This is achieved by requiring that the <code>Collection</code> passed to

 * the {@link #CollectionCertStore(CertStoreParameters)

 * CollectionCertStore(CertStoreParameters)} constructor (via the

 * <code>CollectionCertStoreParameters</code> object) must have fail-fast

 * iterators. Simultaneous modifications to the <code>Collection</code> can thus be

 * detected and certificate or CRL retrieval can be retried. The fact that

 * <code>Certificate</code>s and <code>CRL</code>s must be thread-safe is also

 * essential.

 *

 * @see java.security.cert.CertStore

 * @see CollectionCertStore

 *

 * @author Andreas Sterbenz

 */

public class IndexedCollectionCertStore extends CertStoreSpi {

    /**

     * Map X500Principal(subject) -> X509Certificate | List of X509Certificate

     */

    private Map<X500Principal, Object> certSubjects;

    /**

     * Map X500Principal(issuer) -> X509CRL | List of X509CRL

     */

    private Map<X500Principal, Object> crlIssuers;

    /**

     * Sets of non-X509 certificates and CRLs

     */

    private Set<Certificate> otherCertificates;

    private Set<CRL> otherCRLs;

    /**

     * Creates a <code>CertStore</code> with the specified parameters.

     * For this class, the parameters object must be an instance of

     * <code>CollectionCertStoreParameters</code>.

     *

     * @param params the algorithm parameters

     * @exception InvalidAlgorithmParameterException if params is not an

     *   instance of <code>CollectionCertStoreParameters</code>

     */

    public IndexedCollectionCertStore(CertStoreParameters params)

            throws InvalidAlgorithmParameterException {

        super(params);

        if (!(params instanceof CollectionCertStoreParameters)) {

            throw new InvalidAlgorithmParameterException(

                "parameters must be CollectionCertStoreParameters");

        }

        Collection<?> coll = ((CollectionCertStoreParameters)params).getCollection();

        if (coll == null) {

            throw new InvalidAlgorithmParameterException

                                        ("Collection must not be null");

        }

        buildIndex(coll);

    }

    /**

     * Index the specified Collection copying all references to Certificates

     * and CRLs.

     */

    private void buildIndex(Collection<?> coll) {

        certSubjects = new HashMap<X500Principal, Object>();

        crlIssuers = new HashMap<X500Principal, Object>();

        otherCertificates = null;

        otherCRLs = null;

        for (Object obj : coll) {

            if (obj instanceof X509Certificate) {

                indexCertificate((X509Certificate)obj);

            } else if (obj instanceof X509CRL) {

                indexCRL((X509CRL)obj);

            } else if (obj instanceof Certificate) {

                if (otherCertificates == null) {

                    otherCertificates = new HashSet<Certificate>();

                }

                otherCertificates.add((Certificate)obj);

            } else if (obj instanceof CRL) {

                if (otherCRLs == null) {

                    otherCRLs = new HashSet<CRL>();

                }

                otherCRLs.add((CRL)obj);

            } else {

                // ignore

            }

        }

        if (otherCertificates == null) {

            otherCertificates = Collections.<Certificate>emptySet();

        }

        if (otherCRLs == null) {

            otherCRLs = Collections.<CRL>emptySet();

        }

    }

    /**

     * Add an X509Certificate to the index.

     */

    private void indexCertificate(X509Certificate cert) {

        X500Principal subject = cert.getSubjectX500Principal();

        Object oldEntry = certSubjects.put(subject, cert);

        if (oldEntry != null) { // assume this is unlikely

            if (oldEntry instanceof X509Certificate) {

                if (cert.equals(oldEntry)) {

                    return;

                }

                List<X509Certificate> list = new ArrayList<>(2);

                list.add(cert);

                list.add((X509Certificate)oldEntry);

                certSubjects.put(subject, list);

            } else {

                @SuppressWarnings("unchecked") // See certSubjects javadoc.

                List<X509Certificate> list = (List<X509Certificate>)oldEntry;

                if (list.contains(cert) == false) {

                    list.add(cert);

                }

                certSubjects.put(subject, list);

            }

        }

    }

    /**

     * Add an X509CRL to the index.

     */

    private void indexCRL(X509CRL crl) {

        X500Principal issuer = crl.getIssuerX500Principal();

        Object oldEntry = crlIssuers.put(issuer, crl);

        if (oldEntry != null) { // assume this is unlikely

            if (oldEntry instanceof X509CRL) {

                if (crl.equals(oldEntry)) {

                    return;

                }

                List<X509CRL> list = new ArrayList<>(2);

                list.add(crl);

                list.add((X509CRL)oldEntry);

                crlIssuers.put(issuer, list);

            } else {

                // See crlIssuers javadoc.

                @SuppressWarnings("unchecked")

                List<X509CRL> list = (List<X509CRL>)oldEntry;

                if (list.contains(crl) == false) {

                    list.add(crl);

                }

                crlIssuers.put(issuer, list);

            }

        }

    }

    /**

     * Returns a <code>Collection</code> of <code>Certificate</code>s that

     * match the specified selector. If no <code>Certificate</code>s

     * match the selector, an empty <code>Collection</code> will be returned.

     *

     * @param selector a <code>CertSelector</code> used to select which

     *  <code>Certificate</code>s should be returned. Specify <code>null</code>

     *  to return all <code>Certificate</code>s.

     * @return a <code>Collection</code> of <code>Certificate</code>s that

     *         match the specified selector

     * @throws CertStoreException if an exception occurs

     */

    @Override

    public Collection<? extends Certificate> engineGetCertificates(CertSelector selector)

            throws CertStoreException {

        // no selector means match all

        if (selector == null) {

            Set<Certificate> matches = new HashSet<>();

            matchX509Certs(new X509CertSelector(), matches);

            matches.addAll(otherCertificates);

            return matches;

        }

        if (selector instanceof X509CertSelector == false) {

            Set<Certificate> matches = new HashSet<>();

            matchX509Certs(selector, matches);

            for (Certificate cert : otherCertificates) {

                if (selector.match(cert)) {

                    matches.add(cert);

                }

            }

            return matches;

        }

        if (certSubjects.isEmpty()) {

            return Collections.<X509Certificate>emptySet();

        }

        X509CertSelector x509Selector = (X509CertSelector)selector;

        // see if the subject is specified

        X500Principal subject;

        X509Certificate matchCert = x509Selector.getCertificate();

        if (matchCert != null) {

            subject = matchCert.getSubjectX500Principal();

        } else {

            subject = x509Selector.getSubject();

        }

        if (subject != null) {

            // yes, narrow down candidates to indexed possibilities

            Object entry = certSubjects.get(subject);

            if (entry == null) {

                return Collections.<X509Certificate>emptySet();

            }

            if (entry instanceof X509Certificate) {

                X509Certificate x509Entry = (X509Certificate)entry;

                if (x509Selector.match(x509Entry)) {

                    return Collections.singleton(x509Entry);

                } else {

                    return Collections.<X509Certificate>emptySet();

                }

            } else {

                // See certSubjects javadoc.

                @SuppressWarnings("unchecked")

                List<X509Certificate> list = (List<X509Certificate>)entry;

                Set<X509Certificate> matches = new HashSet<>(16);

                for (X509Certificate cert : list) {

                    if (x509Selector.match(cert)) {

                        matches.add(cert);

                    }

                }

                return matches;

            }

        }

        // cannot use index, iterate all

        Set<Certificate> matches = new HashSet<>(16);

        matchX509Certs(x509Selector, matches);

        return matches;

    }

    /**

     * Iterate through all the X509Certificates and add matches to the

     * collection.

     */

    private void matchX509Certs(CertSelector selector,

        Collection<Certificate> matches) {

        for (Object obj : certSubjects.values()) {

            if (obj instanceof X509Certificate) {

                X509Certificate cert = (X509Certificate)obj;

                if (selector.match(cert)) {

                    matches.add(cert);

                }

            } else {

                // See certSubjects javadoc.

                @SuppressWarnings("unchecked")

                List<X509Certificate> list = (List<X509Certificate>)obj;

                for (X509Certificate cert : list) {

                    if (selector.match(cert)) {

                        matches.add(cert);

                    }

                }

            }

        }

    }

    /**

     * Returns a <code>Collection</code> of <code>CRL</code>s that

     * match the specified selector. If no <code>CRL</code>s

     * match the selector, an empty <code>Collection</code> will be returned.

     *

     * @param selector a <code>CRLSelector</code> used to select which

     *  <code>CRL</code>s should be returned. Specify <code>null</code>

     *  to return all <code>CRL</code>s.

     * @return a <code>Collection</code> of <code>CRL</code>s that

     *         match the specified selector

     * @throws CertStoreException if an exception occurs

     */

    @Override

    public Collection<CRL> engineGetCRLs(CRLSelector selector)

            throws CertStoreException {

        if (selector == null) {

            Set<CRL> matches = new HashSet<>();

            matchX509CRLs(new X509CRLSelector(), matches);

            matches.addAll(otherCRLs);

            return matches;

        }

        if (selector instanceof X509CRLSelector == false) {

            Set<CRL> matches = new HashSet<>();

            matchX509CRLs(selector, matches);

            for (CRL crl : otherCRLs) {

                if (selector.match(crl)) {

                    matches.add(crl);

                }

            }

            return matches;

        }

        if (crlIssuers.isEmpty()) {

            return Collections.<CRL>emptySet();

        }

        X509CRLSelector x509Selector = (X509CRLSelector)selector;

        // see if the issuer is specified

        Collection<X500Principal> issuers = x509Selector.getIssuers();

        if (issuers != null) {

            HashSet<CRL> matches = new HashSet<>(16);

            for (X500Principal issuer : issuers) {

                Object entry = crlIssuers.get(issuer);

                if (entry == null) {

                    // empty

                } else if (entry instanceof X509CRL) {

                    X509CRL crl = (X509CRL)entry;

                    if (x509Selector.match(crl)) {

                        matches.add(crl);

                    }

                } else { // List

                    // See crlIssuers javadoc.

                    @SuppressWarnings("unchecked")

                    List<X509CRL> list = (List<X509CRL>)entry;

                    for (X509CRL crl : list) {

                        if (x509Selector.match(crl)) {

                            matches.add(crl);

                        }

                    }

                }

            }

            return matches;

        }

        // cannot use index, iterate all

        Set<CRL> matches = new HashSet<>(16);

        matchX509CRLs(x509Selector, matches);

        return matches;

    }

    /**

     * Iterate through all the X509CRLs and add matches to the

     * collection.

     */

    private void matchX509CRLs(CRLSelector selector, Collection<CRL> matches) {

        for (Object obj : crlIssuers.values()) {

            if (obj instanceof X509CRL) {

                X509CRL crl = (X509CRL)obj;

                if (selector.match(crl)) {

                    matches.add(crl);

                }

            } else {

                // See crlIssuers javadoc.

                @SuppressWarnings("unchecked")

                List<X509CRL> list = (List<X509CRL>)obj;

                for (X509CRL crl : list) {

                    if (selector.match(crl)) {

                        matches.add(crl);

                    }

                }

            }

        }

    }

}