sequoia-wot 0.15.0

use std::borrow::Borrow;
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::sync::{Arc, Mutex};
use std::time::SystemTime;

use sequoia_openpgp as openpgp;
use openpgp::cert::prelude::*;
use openpgp::cert::raw::RawCert;
use openpgp::Fingerprint;
use openpgp::KeyHandle;
use openpgp::packet::UserID;
use openpgp::policy::Policy;
use openpgp::Result;

use sequoia_cert_store as cert_store;
use cert_store::LazyCert;
use cert_store::store::MergeCerts;
use cert_store::store::Store as _;
use cert_store::store::StoreError;
use cert_store::store::UserIDQueryParams;

use crate::Depth;
use crate::CertificationSet;
use crate::CertSynopsis;
use crate::store::Backend;
use crate::store::Store;

const TRACE: bool = false;

// Reimport crate as wot so that the links in the doc comments work.
#[allow(unused)]
use crate as wot;

/// A wrapper type for objects implementing
/// `cert_store::store::Store`.
///
/// This data type is a wrapper type for objects that implement
/// [`cert_store::store::Store`].  It implements
/// [`wot::store::Backend`] in terms of the `cert_store::store::Store`
/// interface, and exposes the underlying object via `Deref` and
/// `DerefMut`.
///
/// This wrapper is useful for constructing a [`Network`] from an
/// object that implements [`cert_store::store::Store`], like
/// [`cert_store::CertStore`].
///
/// Note: because the reference time is fixed, and you usually want to
/// use the current time as the reference time, you do not want to
/// hold onto this object for a long time.  As such, in long-running
/// programs, you should create this object on demand.  Happily,
/// creating a `CertStore` is inexpensive.  On the other hand,
/// creating a new `CertStore` for each query means that the `redge`
/// cache cannot be used.  As such, it is best to use a single
/// `CertStore` for a single operation, like authenticating some User
/// IDs for one or more certificates.
///
/// This wrapper caches the results of calls to
/// [`wot::store::Backend::redges`], which are typically expensive.
/// It includes a multi-threaded implementation of
/// [`wot::store::Backend::precompute`], which precomputes
/// [`wot::store::Backend::redges`] for all known bindings.
///
/// Finally, it includes an implementation of [`wot::store::Store`] in
/// terms of the [`cert_store::store::Store`] interface, which is much
/// more efficient than the default implementation.
///
/// [`Network`]: crate::Network
///
/// # Examples
///
/// ```
/// use std::sync::Arc;
///
/// use sequoia_openpgp as openpgp;
/// use openpgp::cert::CertBuilder;
/// use openpgp::Fingerprint;
/// # use openpgp::Result;
/// use openpgp::packet::UserID;
/// use openpgp::policy::StandardPolicy;
///
/// use sequoia_cert_store as cert_store;
/// use cert_store::Store;
/// use sequoia_cert_store::StoreUpdate;
///
/// use sequoia_wot as wot;
/// use wot::Network;
/// use wot::Roots;
///
/// const P: &StandardPolicy = &StandardPolicy::new();
///
/// # fn main() -> Result<()> {
/// let (alice, _) = CertBuilder::general_purpose(Some("<alice@example.org>)"))
///     .generate()?;
/// let (bob, _) = CertBuilder::general_purpose(Some("<bob@example.org>"))
///     .generate()?;
///
/// let mut cert_store = cert_store::CertStore::empty();
/// cert_store.update(Arc::new(alice.clone().into()))?;
/// cert_store.update(Arc::new(bob.clone().into()))?;
///
/// // Build a WoT network.
/// let trust_roots = Roots::from(&[
///     (alice.fingerprint().into(), wot::FULLY_TRUSTED),
/// ]);
/// let wot_data = wot::store::CertStore::from_store(&cert_store, P, None);
/// let network = Network::new(&wot_data, trust_roots)?;
///
/// // Try and authenticate Bob.
/// let paths = network.authenticate(
///     UserID::from("<bob@example.org>"),
///     bob.fingerprint(),
///     wot::FULLY_TRUSTED);
/// // Alice, our sole trust root, did not certify Bob so this will fail.
/// assert_eq!(paths.amount(), 0);
///
/// // Since network only has a reference to the cert_store, we don't
/// // have to do anything special to get cert_store back.
/// assert_eq!(cert_store.fingerprints().count(), 2);
/// // And thanks to nll, we can immediately transfer ownership.
/// drop(cert_store);
/// # Ok(()) }
pub struct CertStore<'a: 'policy, 'policy, S>
    where S: cert_store::store::Store<'a>,
{
    store: S,

    // Certifications on a certificate.
    //
    // Example:
    //
    // ```
    // 0xA certifies <Carol, 0xC>.    \ CertificationSet
    // 0xA certifies <Caroline, 0xC>. /
    // 0xB certifies <Carol, 0xC>.    > CertificationSet
    // ```
    //
    // The entry for 0xC has two `CertificationSet`s: one for those
    // made by 0xA and one for those made by 0xB.
    //
    // This is a cache, which is derived from the certs, and is update
    // lazily.
    redge_cache: Mutex<BTreeMap<Fingerprint, Arc<Vec<CertificationSet>>>>,

    // The policy.  This is needed to compute the
    // certification sets.
    policy: MaybeOwnedPolicy<'policy>,

    // The reference time.  This is needed to compute the
    // certification sets.
    reference_time: SystemTime,

    _a: std::marker::PhantomData<&'a ()>,
}

/// The [`CertStore`] may either borrow or own a policy.
#[non_exhaustive]
pub enum MaybeOwnedPolicy<'p> {
    /// A borrowed policy.
    Borrowed(&'p dyn Policy),

    /// A shared policy.
    Arc(Arc<dyn Policy + 'p>),

    /// An owned policy.
    Owned(Box<dyn Policy + 'p>),
}

impl MaybeOwnedPolicy<'_> {
    /// Returns the policy.
    fn as_ref(&self) -> &dyn Policy {
        match self {
            MaybeOwnedPolicy::Borrowed(p) => *p,
            MaybeOwnedPolicy::Arc(p) => p.as_ref(),
            MaybeOwnedPolicy::Owned(p) => p.as_ref(),
        }
    }
}

impl<'p> From<&'p dyn Policy> for MaybeOwnedPolicy<'p> {
    fn from(p: &'p dyn Policy) -> Self {
        MaybeOwnedPolicy::Borrowed(p)
    }
}

impl<'p, P: Policy> From<&'p P> for MaybeOwnedPolicy<'p> {
    fn from(p: &'p P) -> Self {
        MaybeOwnedPolicy::Borrowed(&*p)
    }
}

impl<'p> From<Arc<dyn Policy + 'p>> for MaybeOwnedPolicy<'p> {
    fn from(p: Arc<dyn Policy + 'p>) -> Self {
        MaybeOwnedPolicy::Arc(p)
    }
}

impl<'p> From<Box<dyn Policy + 'p>> for MaybeOwnedPolicy<'p> {
    fn from(p: Box<dyn Policy + 'p>) -> Self {
        MaybeOwnedPolicy::Owned(p)
    }
}

impl<'a: 'policy, 'policy, S> CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a>,
{
    /// Returns a new `CertStore` from a cert store.
    ///
    /// A wrapper for [`cert_store::store::Store`]s, and implements
    /// [`store::Backend`] and [`store::Store`] on it.
    ///
    /// [`store::Backend`]: crate::store::Backend
    /// [`store::Store`]: crate::store::Store
    pub fn from_store<P, T>(store: S, policy: P, t: T)
        -> Self
    where
        P: Into<MaybeOwnedPolicy<'policy>>,
        T: Into<Option<SystemTime>>,
    {
        let t = t.into().unwrap_or_else(SystemTime::now);

        Self {
            store,
            redge_cache: Default::default(),
            policy: policy.into(),
            reference_time: t,
            _a: std::marker::PhantomData,
        }
    }

    /// Returns a reference to the underlying store.
    pub fn store(&self) -> &S {
        &self.store
    }

    /// Returns a mutable reference to the underlying store.
    pub fn store_mut(&mut self) -> &mut S {
        &mut self.store
    }

    /// Returns the store.
    pub fn into_store(self) -> S {
        self.store
    }

    /// Returns the configured policy.
    pub fn policy(&self) -> &dyn Policy {
        self.policy.as_ref()
    }

    /// Returns the configured reference time.
    pub fn reference_time(&self) -> SystemTime {
        self.reference_time.clone()
    }
}

impl<'a: 'policy, 'policy, S> std::ops::Deref for CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a>,
{
    type Target = S;

    fn deref(&self) -> &Self::Target {
        &self.store
    }
}

impl<'a: 'policy, 'policy, S> std::ops::DerefMut for CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a>,
{
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.store
    }
}

impl<'a: 'policy, 'policy> CertStore<'a, 'policy, cert_store::store::Certs<'a>>
{
    /// Returns a new `CertStore` from a slice of bytes.
    ///
    /// The bytes are interpreted as an OpenPGP keyring.  The data
    /// may, but need not, be ASCII-armor encoded.
    pub fn from_bytes<P, T>(bytes: &'a [u8], policy: P, t: T)
        -> Result<Self>
    where
        P: Into<MaybeOwnedPolicy<'policy>>,
        T: Into<Option<SystemTime>>,
    {
        tracer!(TRACE, "CertStore::from_bytes");

        let store = cert_store::store::Certs::from_bytes(bytes)?;

        let t = t.into().unwrap_or_else(SystemTime::now);

        Ok(Self {
            store,
            redge_cache: Default::default(),
            policy: policy.into(),
            reference_time: t,
            _a: std::marker::PhantomData,
        })
    }

    /// Creates a `CertStore` from some `Cert`s.
    pub fn from_certs<P, T>(certs: impl IntoIterator<Item=Cert>,
                            policy: P, t: T)
        -> Result<Self>
    where
        P: Into<MaybeOwnedPolicy<'policy>>,
        T: Into<Option<SystemTime>>,
    {
        tracer!(TRACE, "CertStore::from_certs");

        let store = cert_store::store::Certs::from_certs(certs)?;

        let t = t.into().unwrap_or_else(SystemTime::now);

        Ok(Self {
            store,
            redge_cache: Default::default(),
            policy: policy.into(),
            reference_time: t,
            _a: std::marker::PhantomData,
        })
    }

    /// Creates a `CertStore` from `&Cert`s.
    pub fn from_cert_refs<P, T>(certs: impl IntoIterator<Item=&'a Cert>,
                                policy: P, t: T)
        -> Result<Self>
    where
        P: Into<MaybeOwnedPolicy<'policy>>,
        T: Into<Option<SystemTime>>,
    {
        tracer!(TRACE, "CertStore::from_cert_refs");

        let store = cert_store::store::Certs::from_certs(
            certs.into_iter().map(|c| {
                let c: &'a Cert = c.into();
                LazyCert::from(c)
            }))?;

        let t = t.into().unwrap_or_else(SystemTime::now);

        Ok(Self {
            store,
            redge_cache: Default::default(),
            policy: policy.into(),
            reference_time: t,
            _a: std::marker::PhantomData,
        })
    }

    /// Creates a `CertStore` from `RawCert`s.
    pub fn from_raw_certs<P, T>(certs: impl IntoIterator<Item=RawCert<'a>>,
                                policy: P, t: T)
        -> Result<Self>
    where
        P: Into<MaybeOwnedPolicy<'policy>>,
        T: Into<Option<SystemTime>>,
    {
        tracer!(TRACE, "CertStore::from_raw_certs");

        let store = cert_store::store::Certs::from_certs(certs)?;

        let t = t.into().unwrap_or_else(SystemTime::now);

        Ok(Self {
            store,
            redge_cache: Default::default(),
            policy: policy.into(),
            reference_time: t,
            _a: std::marker::PhantomData,
        })
    }
}

impl<'a: 'policy, 'policy, S> cert_store::Store<'a> for CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a>,
{
    fn lookup_by_cert(&self, kh: &KeyHandle) -> Result<Vec<Arc<LazyCert<'a>>>> {
        self.store.lookup_by_cert(kh)
    }

    fn lookup_by_cert_fpr(&self, fingerprint: &Fingerprint)
        -> Result<Arc<LazyCert<'a>>>
    {
        self.store.lookup_by_cert_fpr(fingerprint)
    }

    fn lookup_by_cert_or_subkey(&self, kh: &KeyHandle) -> Result<Vec<Arc<LazyCert<'a>>>> {
        self.store.lookup_by_cert_or_subkey(kh)
    }

    fn select_userid(&self, query: &UserIDQueryParams, pattern: &str)
        -> Result<Vec<Arc<LazyCert<'a>>>>
    {
        self.store.select_userid(query, pattern)
    }

    fn lookup_by_userid(&self, userid: &UserID) -> Result<Vec<Arc<LazyCert<'a>>>> {
        self.store.lookup_by_userid(userid)
    }

    fn grep_userid(&self, pattern: &str) -> Result<Vec<Arc<LazyCert<'a>>>> {
        self.store.grep_userid(pattern)
    }

    fn lookup_by_email(&self, email: &str) -> Result<Vec<Arc<LazyCert<'a>>>> {
        self.store.lookup_by_email(email)
    }

    fn grep_email(&self, pattern: &str) -> Result<Vec<Arc<LazyCert<'a>>>> {
        self.store.grep_email(pattern)
    }

    fn lookup_by_email_domain(&self, domain: &str) -> Result<Vec<Arc<LazyCert<'a>>>> {
        self.store.lookup_by_email_domain(domain)
    }

    fn fingerprints<'b>(&'b self) -> Box<dyn Iterator<Item=Fingerprint> + 'b> {
        self.store.fingerprints()
    }

    fn certs<'b>(&'b self)
        -> Box<dyn Iterator<Item=Arc<LazyCert<'a>>> + 'b>
        where 'a: 'b
    {
        self.store.certs()
    }

    fn prefetch_all(&self) {
        self.store.prefetch_all()
    }

    fn prefetch_some(&self, certs: &[KeyHandle]) {
        self.store.prefetch_some(certs)
    }
}

impl<'a: 'policy, 'policy, S> cert_store::StoreUpdate<'a> for CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a> + cert_store::store::StoreUpdate<'a>,
{
    fn update_by(&self,
                 cert: Arc<LazyCert<'a>>,
                 merge_strategy: &dyn MergeCerts<'a>)
        -> Result<Arc<LazyCert<'a>>>
    {
        let fingerprint = cert.fingerprint();
        let r = self.store.update_by(cert, merge_strategy);

        // Invalidate the cache.
        //
        // We invalidate the cache after writing the certificate to
        // the store to avoid a race whereby another thread updates
        // the cache using the old entry.  Consider what could happen
        // if we invalidate the cache before writing the certificate
        // to the store:
        //
        //    Thread A       Thread B
        //    invalidate X
        //                   read X
        //    write X
        //
        // Thread B creates a cache entry based on the old data, and
        // it is never invalidated (or only much later).
        //
        // Our approach still has a race between updating the store
        // and invalidating the cache entry as shown here:
        //
        //    Thread A       Thread B
        //    write X
        //                   read X
        //    invalidate X
        //
        // Thead B uses the old version of the certificate even though
        // thread A has already written out a new version.  But that
        // is not a problem in practice, because thread B cannot
        // distinguish the above from this sequence of events:
        //
        //    Thread A       Thread B
        //                   read X
        //    write X
        //    invalidate X
        //
        // And this sequence is fine.
        let mut redge = self.redge_cache.lock().unwrap();
        redge.remove(&fingerprint);
        drop(redge);

        r
    }

    fn update(&self, cert: Arc<LazyCert<'a>>) -> Result<()> {
        let fingerprint = cert.fingerprint();
        let r = self.store.update(cert);

        // Invalidate the cache (see the comment above).
        let mut redge = self.redge_cache.lock().unwrap();
        redge.remove(&fingerprint);
        drop(redge);

        r
    }
}

impl<'a: 'policy, 'policy, S> Backend<'a> for CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a> + Send + Sync,
{
    /// Prefills the cache.
    ///
    /// Prefilling the cache makes sense when you plan to examine most
    /// nodes and edges in the network.  It doesn't make sense if you
    /// are just authenticating a single or a few bindings.
    ///
    /// This function is multi-threaded.
    ///
    /// Errors are silently ignored and are propagated when the
    /// operation in question is executed directly.
    fn precompute(&self) {
        tracer!(TRACE, "CertStore::precompute");
        t!("prefetching");

        // Figure out what certificates we need to work on.
        let all: BTreeSet<Fingerprint>
            = BTreeSet::from_iter(self.store.fingerprints());
        let done: BTreeSet<Fingerprint>
            = BTreeSet::from_iter(
                self.redge_cache.lock().unwrap().keys().cloned());
        let todo: Vec<&Fingerprint>
            = all.difference(&done).collect();

        // We could sort `todo` before distributing the work.  That
        // would ensure that any certificates with a lot of work are
        // done first and all threads will finish at about the same
        // time.  In practice: it's not worth it.

        use crossbeam::thread;
        use crossbeam::channel::unbounded as channel;

        // Avoid an extra level of indentation.
        let result = thread::scope(|thread_scope| {
        // The threads.  We start them on demand.
        let threads = if todo.len() < 16 {
            // The keyring is small, limit the number of threads.
            2
        } else {
            // Use at least one and not more than we have cores.
            num_cpus::get().max(1)
        };

        // A communication channel for sending work to the workers.
        let (work_tx, work_rx) = channel();

        let mut threads_extant = Vec::new();

        for fpr in todo.into_iter() {
            if threads_extant.len() < threads {
                let tid = threads_extant.len();
                t!("Starting thread {} of {}",
                   tid, threads);

                let mut work = Some(Ok(fpr));

                // The thread's state.
                let work_rx = work_rx.clone();

                // Reborrow to get a normal reference, which can be
                // copied to the threads.
                let backend = &*self;
                let policy = self.policy();
                let reference_time = self.reference_time.clone();

                threads_extant.push(thread_scope.spawn(move |_| {
                    let mut results: Vec<(Fingerprint, Arc<Vec<CertificationSet>>)>
                        = Vec::new();

                    loop {
                        match work.take().unwrap_or_else(|| work_rx.recv()) {
                            Err(_) => break,
                            Ok(fpr) => {
                                t!("Thread {} dequeuing {}!", tid, fpr);

                                // Silently ignore errors.  This will
                                // be caught later when the caller
                                // looks this one up.

                                let cert = if let Ok(cert)
                                    = backend.lookup_by_cert_fpr(fpr)
                                {
                                    cert
                                } else {
                                    continue;
                                };

                                match cert.with_policy(policy, reference_time)
                                {
                                    Ok(vc) => {
                                        results.push((
                                            cert.fingerprint(),
                                            backend.redges(vc, 0.into())))
                                    }
                                    Err(err) => {
                                        t!("{} is not valid under \
                                            the current policy: {}",
                                           cert.fingerprint(), err);
                                        results.push((
                                            cert.fingerprint(),
                                            Arc::new(Vec::new())))
                                    }
                                }
                            }
                        }
                    }

                    t!("Thread {} exiting", tid);

                    results
                }));
            } else {
                work_tx.send(fpr).unwrap();
            }
        }

        // When the threads see this drop, they will exit.
        drop(work_tx);

        let redges = threads_extant.into_iter().flat_map(|t| {
            let redges: Vec<(Fingerprint, Arc<Vec<CertificationSet>>)>
                = t.join().unwrap();
            redges
        });

        // Add the results to the cache.
        self.redge_cache.lock().unwrap().extend(redges.into_iter());
        }); // thread scope.

        // We're just caching results so we can ignore errors.
        if let Err(err) = result {
            t!("{:?}", err);
        }
    }
}

impl<'a: 'policy, 'policy, S> CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a> + Send + Sync,
{
    fn certifications_of_uncached<F>(&self, target: F)
        -> Result<Arc<Vec<CertificationSet>>>
    where F: Borrow<Fingerprint>
    {
        let target = target.borrow();
        let cert = self.store.lookup_by_cert_fpr(target)?;
        let redges = self.redges(
            cert.with_policy(self.policy(), self.reference_time)?,
            0.into());

        Ok(redges)
    }

    fn to_synopsis(&self, cert: Arc<LazyCert>) -> Option<CertSynopsis> {
        cert
            .to_cert()
            .and_then(|c| {
                c.with_policy(self.policy(), self.reference_time)
            })
            .map(Into::into)
            .ok()
    }
}

impl<'a: 'policy, 'policy, S> Store for CertStore<'a, 'policy, S>
    where S: cert_store::store::Store<'a> + Send + Sync,
{
    fn reference_time(&self) -> SystemTime {
        self.reference_time
    }

    fn iter_fingerprints<'b>(&'b self) -> Box<dyn Iterator<Item=Fingerprint> + 'b> {
        tracer!(TRACE, "CertStore::iter_fingerprints");
        t!("");
        self.store.fingerprints()
    }

    fn synopses<'b>(&'b self) -> Box<dyn Iterator<Item=CertSynopsis> + 'b> {
        let certs = self.store
            .certs()
            .filter_map(|c| self.to_synopsis(c))
            .collect::<Vec<_>>();
        Box::new(certs.into_iter())
    }

    fn lookup_synopsis_by_fpr(&self, fingerprint: &Fingerprint)
        -> Result<CertSynopsis>
    {
        let cert = self.store.lookup_by_cert_fpr(fingerprint)?;
        self.to_synopsis(cert).ok_or_else(|| {
            StoreError::NotFound(KeyHandle::from(fingerprint.clone())).into()
        })
    }

    fn lookup_synopses(&self, kh: &KeyHandle) -> Result<Vec<CertSynopsis>> {
        tracer!(TRACE, "CertStore::lookup_synopses");

        t!("{}", kh);

        let certs: Vec<_> = self.store.lookup_by_cert(kh)?
            .into_iter()
            .filter_map(|c| self.to_synopsis(c))
            .collect();
        if certs.is_empty() {
            Err(StoreError::NotFound(kh.clone()).into())
        } else {
            Ok(certs)
        }
    }

    fn certifications_of(&self, target: &Fingerprint, _min_depth: Depth)
        -> Result<Arc<Vec<CertificationSet>>>
    {
        tracer!(TRACE, "CertStore::certifications_of");

        t!("{}", target);

        let redge_cache = self.redge_cache.lock().unwrap();
        if let Some(redges) = redge_cache.get(target) {
            t!("Cache hit!");
            return Ok(redges.clone());
        }
        drop(redge_cache);

        t!("Cache miss!");

        let redges = self.certifications_of_uncached(target)?;

        self.redge_cache
            .lock().unwrap()
            .insert(target.clone(), Arc::clone(&redges));

        Ok(redges)
    }

    fn certified_userids_of(&self, fpr: &Fingerprint)
        -> Vec<UserID>
    {
        let Ok(cert) = self.lookup_by_cert_fpr(fpr)
        else { return Vec::new() };

        cert.userids().collect()
    }

    fn certified_userids(&self)
        -> Vec<(Fingerprint, UserID)>
    {
        self.certs()
            .flat_map(|c| {
                let fpr = c.fingerprint();
                c.userids().into_iter()
                    .map(|u| {
                        (fpr.clone(), u)
                    })
                    .collect::<Vec<_>>()
                    .into_iter()
            })
            .collect()
    }

    fn lookup_synopses_by_userid(&self, userid: UserID) -> Vec<Fingerprint> {
        self.lookup_by_userid(&userid)
            .unwrap_or(Vec::new())
            .into_iter()
            .map(|c| c.fingerprint())
            .collect()
    }

    fn lookup_synopses_by_email(&self, email: &str) -> Vec<(Fingerprint, UserID)> {
        let email = if let Ok(email) = UserIDQueryParams::is_email(email) {
            email
        } else {
            return Vec::new();
        };

        self.lookup_by_email(&email)
            .unwrap_or(Vec::new())
            .into_iter()
            .flat_map(|cert| {
                cert.userids()
                    .filter_map(|userid| {
                        // We want to compare the normalized forms.
                        // But if they already match, then they will
                        // normalize to the same thing, and we can
                        // avoid the cost of doing the normalization.
                        if let Ok(Some(e)) = userid.email() {
                            if e == email {
                                Some((cert.fingerprint(), userid.clone()))
                            } else {
                                if let Ok(Some(e)) = userid.email_normalized() {
                                    if e == email {
                                        Some((cert.fingerprint(), userid.clone()))
                                    } else {
                                        None
                                    }
                                } else {
                                    None
                                }
                            }
                        } else {
                            None
                        }
                    })
                    .collect::<Vec<_>>()
                    .into_iter()
            })
            .collect()
    }
}

#[cfg(test)]
mod test {
    use super::*;

    use sequoia_openpgp as openpgp;
    use openpgp::cert::CertBuilder;
    use openpgp::Result;
    use openpgp::packet::UserID;
    use openpgp::parse::Parse;
    use openpgp::policy::StandardPolicy;

    use sequoia_cert_store as cert_store;
    use cert_store::Store;
    use sequoia_cert_store::StoreUpdate;

    use crate::NetworkBuilder;
    use crate::Roots;
    use crate::FULLY_TRUSTED;

    const P: &StandardPolicy = &StandardPolicy::new();

    // Check that that lifetimes allow us to use a CertStore as follow:
    #[test]
    fn cert_store_lifetimes() -> Result<()> {
        fn authenticate<'store: 'policy, 'policy>(
            // The core of our check.  Does the following compile:
            store: &CertStore<'store, 'policy,
                              &'policy cert_store::CertStore<'store>>,
            trust_root: Fingerprint,
            target_fpr: Fingerprint,
            target_userid: UserID)
            -> usize
        {
            eprintln!("trust root: {}", trust_root);
            eprintln!("target: {}, {:?}", target_fpr, target_userid);

            let n = NetworkBuilder::rooted(
                &store, Roots::from(&[
                    (trust_root, FULLY_TRUSTED),
                ]))
                .build();

            let paths = n.authenticate(
                target_userid,
                target_fpr,
                FULLY_TRUSTED);

            eprintln!("paths: {:?}", paths);

            paths.amount()
        }

        let (alice, _) = CertBuilder::general_purpose(
            Some("<alice@example.org>"))
            .generate()?;
        let (bob, _) = CertBuilder::general_purpose(
            Some("<bob@example.org>"))
            .generate()?;

        let cert_store = cert_store::CertStore::empty();
        cert_store.update(Arc::new(alice.clone().into()))?;
        cert_store.update(Arc::new(bob.clone().into()))?;

        eprintln!("certificates:");
        for (i, cert) in cert_store.certs().enumerate() {
            eprintln!("  {}. {}, {}",
                      i,
                      cert.fingerprint(),
                      cert.userids().next().expect("have one"));
        }

        // Build a few WoT networks.
        for _ in 0..2 {
            let store = CertStore::from_store(&cert_store, P, None);

            // Try and authenticate Bob.
            let amount = authenticate(
                &store,
                alice.fingerprint(),
                bob.fingerprint(),
                UserID::from("<bob@example.org>"));

            // Alice, our sole trust root, did not certify Bob so this
            // will fail.
            assert_eq!(amount, 0);


            let amount = authenticate(
                &store,
                alice.fingerprint(),
                alice.fingerprint(),
                UserID::from("<alice@example.org>"));

            // Alice, our trust root, self signed the User ID, so this
            // should pass.
            assert_eq!(amount, FULLY_TRUSTED);
        }

        // Since network only has a reference to the cert_store, we don't
        // have to do anything special to get cert_store back.
        assert_eq!(cert_store.fingerprints().count(), 2);

        // And thanks to nll, we can recover ownership to the
        // underlying cert store.
        drop(cert_store);

        Ok(())
    }

    // Reproducer for
    // https://gitlab.com/sequoia-pgp/sequoia-wot/-/issues/54
    #[test]
    fn my_own_grandfather() -> Result<()> {
        let ref_cert = Cert::from_bytes(
            &crate::testdata::data("my-own-grandpa.pgp"))?;
        let ref_fpr = ref_cert.fingerprint();
        let ref_kh = ref_cert.key_handle();

        // The certificate has a primary key that is also bound as a
        // subkey.
        assert!(ref_cert.keys().subkeys().any(|k| {
            k.key().fingerprint() == ref_fpr
        }));

        let store = CertStore::from_cert_refs(
            std::iter::once(&ref_cert), P, None)?;

        // The bug in issue #54 was in the local implementation of
        // cert_store::store::Store::lookup_by_cert_or_subkey.  We
        // exercise that by calling precompute on the store.
        store.precompute();

        // Also test that the CertStore implementation is not
        // impacted.
        let cert = store.lookup_by_cert_fpr(&ref_fpr)
            .expect("found cert");
        assert_eq!(cert.fingerprint(), ref_fpr);

        // Make sure the implementation doesn't return the certificate
        // twice, once when matching on the primary key, and once when
        // matching on the subkey.
        let certs = store.lookup_by_cert(&ref_kh)
            .expect("found cert");
        assert_eq!(certs.len(), 1);
        assert_eq!(certs[0].fingerprint(), ref_fpr);

        let certs = store.lookup_by_cert_or_subkey(&ref_kh)
            .expect("found cert");
        assert_eq!(certs.len(), 1);
        assert_eq!(certs[0].fingerprint(), ref_fpr);

        let certs = store.certs().collect::<Vec<_>>();
        assert_eq!(certs.len(), 1);
        assert_eq!(certs[0].fingerprint(), ref_fpr);

        let fprs = store.fingerprints().collect::<Vec<_>>();
        assert_eq!(fprs.len(), 1);
        assert_eq!(fprs[0], ref_fpr);

        Ok(())
    }

    #[test]
    fn email_lookup() -> Result<()> {
        use crate::store::Store as _;

        let certs = CertParser::from_bytes(
            &crate::testdata::data("puny-code.pgp"))?
            .collect::<Result<Vec<Cert>>>()?;
        let store = CertStore::from_cert_refs(
            certs.iter(), P, None)?;

        let certs = store.lookup_synopses_by_email("hÄNS@bücher.tld");
        assert_eq!(certs.len(), 1);

        // Not a valid email address.
        let certs = store.lookup_synopses_by_email("<hÄNS@bücher.tld>");
        assert_eq!(certs.len(), 0);

        // Make sure we compare on the normalized email address.
        let certs = store.lookup_synopses_by_email("hÄns@bücher.tld");
        assert_eq!(certs.len(), 1);

        let certs = store.lookup_synopses_by_email("häns@xn--bcher-kva.tld");
        assert_eq!(certs.len(), 1);

        Ok(())
    }
}