sequoia_wot/network/

path.rs

use std::borrow::Borrow;
use std::time::SystemTime;
use std::sync::Arc;

use sequoia_openpgp as openpgp;

use openpgp::KeyHandle;
use openpgp::KeyID;
use openpgp::Result;
use openpgp::cert::prelude::*;
use openpgp::packet::prelude::*;
use openpgp::policy::NullPolicy;
use openpgp::policy::Policy;
use openpgp::types::ReasonForRevocation;
use openpgp::types::RevocationStatus;

use sequoia_cert_store as cert_store;
use cert_store::store::StoreError;
use cert_store::LazyCert;

use crate::CertSynopsis;
use crate::Certification;
use crate::CertificationSet;
use crate::Depth;
use crate::format_time;
use crate::Network;
use crate::Path;
use crate::store::Backend;
use crate::store::Store;

use super::TRACE;

const NP: NullPolicy = unsafe { NullPolicy::new() };

/// [`Network::lint_path`] specific error codes.
#[non_exhaustive]
#[derive(thiserror::Error, Debug)]
pub enum PathError {
    /// A path consists of at least one node.
    #[error("A path consists of at least one node.")]
    EmptyPath,

    /// There is a path, but the trust amount is insufficient.
    #[error("The path {path}, {1:?} exists, but its trust amount \
             is too low ({2}, required: {3}).",
            path=.0.iter()
                .map(|kh| KeyID::from(kh).to_hex())
                .collect::<Vec<String>>()
                .join(" -> "))]
    PathInadequate(Vec<KeyHandle>, UserID, usize, usize),

    /// Missing the issuer's certificate.
    #[error("Can't check certification: \
             missing the alleged issuer's certificate ({0})")]
    MissingIssuer(KeyHandle),

    /// Missing the target's certificate.
    #[error("Can't check certification: \
             missing the target's certificate ({0})")]
    MissingTarget(KeyHandle),

    /// The target certificate is expired.
    #[error("The target ({0}) is expired ({time1}) \
             as of the reference time ({time2})",
            time1=format_time(.1), time2=format_time(.2))]
    TargetExpired(KeyHandle, SystemTime, SystemTime),

    /// The target certificate is revoked.
    ///
    /// 0. Target cert, 1. revocation code, 2. revocation reason,
    /// 3. revocation time, 4. reference time.
    #[error("The target ({0}) is revoked ({time1}, {1}, {msg}) \
             as of the reference time ({time2})",
            time1=format_time(.3),
            msg=String::from_utf8_lossy(.2),
            time2=format_time(.4))]
    TargetRevoked(KeyHandle, ReasonForRevocation, Vec<u8>, SystemTime, SystemTime),

    /// The target User ID is revoked.
    ///
    /// 0. Target cert, 1. target user id, 2. revocation code,
    /// 3. revocation reason, 4. revocation time, 5. reference time.
    #[error("The target's ({0}) User ID ({userid:?}) is revoked \
             ({time1}, {2}, {msg}) as of the reference time ({time2})",
            userid=String::from_utf8_lossy(.1.value()),
            time1=format_time(.4),
            msg=String::from_utf8_lossy(.3),
            time2=format_time(.5))]
    TargetUserIDRevoked(KeyHandle, UserID, ReasonForRevocation, Vec<u8>,
                        SystemTime, SystemTime),

    /// None of this certificate's regular expressions match the
    /// target User ID.
    #[error("None of the certification's ({0}) regular expressions ({regex:?}) \
             match the target User ID ({userid:?})",
            regex=.0.regular_expressions_bytes()
                .iter()
                .map(|re| {
                    String::from_utf8_lossy(re).into_owned()
                })
                .collect::<Vec<String>>()
                .join(", "),
            userid=String::from_utf8_lossy(.1.value()))]
    RegexMismatch(Certification, UserID),

    /// The certification's target does not have a sufficiently high
    /// trust depth to authenticate the rest of the path.
    #[error("The path requires that {keyid} be a level-{1} \
             trusted introducer, the certification {0} only makes it \
             a level-{depth} trusted introducer",
            keyid=.0.target().keyid().to_hex(),
            depth=.0.depth())]
    InsufficientTrustDepth(Certification, Depth),

    /// The certification does not have a sufficient trust amount.
    #[error("The path requires a trust amount of {1}, but \
             this certification ({0}) only has a trust amount of \
             {amount}",
            amount=.0.amount())]
    InsufficientTrustAmount(Certification, usize),

    /// The certificate did not issue a certification for the
    /// specified binding.
    #[error("{} did not certify <{}, {:?}>",
            .0.keyid(), .1.keyid(),
            String::from_utf8_lossy(.2.value()))]
    NoCertification(CertSynopsis, CertSynopsis, UserID),

    /// The certificate did not delegate to the target.
    #[error("{} did not certify {}",
            .0.keyid(), .1.keyid())]
    NoDelegation(CertSynopsis, CertSynopsis),

    /// None of the active certifications were adequate for
    /// authenticating the target.
    #[error("No active certifications by {keyid1} for \
             <{keyid2}, {userid:?}> had a trust amount of at least {3}",
            keyid1=.0.keyid(), keyid2=.1.keyid(),
            userid=String::from_utf8_lossy(.2.value()))]
    NoAdequateCertification(CertSynopsis, CertSynopsis, UserID, usize),

    /// None of the active delegations were adequate for the path
    /// suffix.
    #[error("No active certifications by {keyid1} for {keyid2} \
             that make it at least a level-{2} trusted introducer \
             with a trust amount of at least {3}",
            keyid1=.0.keyid(), keyid2=.1.keyid())]
    NoAdequateDelegation(CertSynopsis, CertSynopsis, Depth, usize),

    /// A certification would be adequate, but it is not active.
    #[error("Certification ({0}) is adequate, but it is not active")]
    AdequateButNotActive(Certification),

    /// A certification would be adequate, but it is not valid.
    #[error("Certification ({0}) is adequate, but it is not valid")]
    AdequateButNotValid(Certification, #[source] anyhow::Error),
}

/// What we know about a certificate.
///
/// Sometimes we only know its Key ID.
///
/// The lifetimes `'a` and `'b` have the same meaning as for
/// [`sequoia_wot::store::Store`]: `'a` is the lifetime of the object
/// on the backend, `'b` is the lifetime of the reference to the
/// object, and the object (`'a`) must outlive the reference (`'b`).
#[derive(Debug, Clone)]
enum CertVariants<'a> {
    KeyHandle(KeyHandle),
    Cert(Arc<LazyCert<'a>>),
    CertSynopsis(CertSynopsis),
}

impl<'a> CertVariants<'a> {
    /// Returns the certificate's KeyHandle.
    pub fn key_handle(&self) -> KeyHandle {
        match self {
            CertVariants::KeyHandle(ref kh) => kh.clone(),
            CertVariants::Cert(ref cert) => cert.key_handle(),
            CertVariants::CertSynopsis(ref cert) => cert.fingerprint().into(),
        }
    }

    /// Returns the certificate's primary User ID, if known.
    ///
    /// Note: this is best effort, and the User ID may not be valid
    /// under the policy.
    pub fn primary_userid(&self) -> Option<UserID> {
        match self {
            CertVariants::KeyHandle(_) => None,
            CertVariants::Cert(ref cert) => {
                // We can't get a ValidCert (otherwise we'd have a
                // CertVariants::CertSynopsis).  This is best effort.
                cert.with_policy(&NP, None)
                    .and_then(|vc| {
                        vc.primary_userid().map(|ua| ua.userid().clone())
                    })
                    .ok()
                    .or_else(|| {
                        cert.userids().next()
                    })
            }
            CertVariants::CertSynopsis(ref cert) => {
                cert.primary_userid().map(|u| u.userid().clone())
            }
        }
    }

    /// Returns the CertSynopsis, if it is available.
    pub fn cert(&self) -> Option<&CertSynopsis> {
        if let CertVariants::CertSynopsis(ref c) = self {
            Some(c)
        } else {
            None
        }
    }
}

/// What we know about a certificate, and any errors or lints.
///
/// Sometimes we only know its Key ID.
///
/// This is indirectly returned by [`Network::lint_path`].
///
/// The lifetimes `'a` and `'b` have the same meaning as for
/// [`Store`]: `'a` is the lifetime of the object on the backend, `'b`
/// is the lifetime of the reference to the object, and the object
/// (`'a`) must outlive the reference (`'b`).
#[derive(Debug)]
pub struct CertLints<'a> {
    cert: CertVariants<'a>,
    errors: Vec<anyhow::Error>,
    lints: Vec<anyhow::Error>,
}

impl<'a> CertLints<'a> {
    fn from_key_handle(kh: KeyHandle) -> Self {
        Self {
            cert: CertVariants::KeyHandle(kh),
            errors: Vec::new(),
            lints: Vec::new(),
        }
    }

    fn from_lazy_cert(lc: Arc<LazyCert<'a>>) -> Self {
        Self {
            cert: CertVariants::Cert(lc),
            errors: Vec::new(),
            lints: Vec::new(),
        }
    }

    fn from_cert_synopsis(cert: CertSynopsis) -> Self {
        Self {
            cert: CertVariants::CertSynopsis(cert),
            errors: Vec::new(),
            lints: Vec::new(),
        }
    }

    /// Returns the certificate's KeyHandle.
    pub fn key_handle(&self) -> KeyHandle {
        self.cert.key_handle()
    }

    /// Returns the certificate's primary User ID, if known.
    ///
    /// Note: this is best effort, and the User ID may not be valid
    /// under the policy.
    pub fn primary_userid(&self) -> Option<UserID> {
        self.cert.primary_userid()
    }

    /// Returns the CertSynopsis, if it is available.
    pub fn cert(&self) -> Option<&CertSynopsis> {
        self.cert.cert()
    }

    /// Returns any errors.
    ///
    /// Errors are fatal in the sense that the path is not valid.
    pub fn errors(&self) -> &[anyhow::Error] {
        &self.errors
    }

    /// Returns any lints.
    ///
    /// Lints are not fatal in the sense that the lint does not
    /// necessarily invalidate the path.
    pub fn lints(&self) -> &[anyhow::Error] {
        &self.lints
    }
}

/// What we know about a certificate.
///
/// Sometimes we only know the Key ID of the issuer and the Key ID of
/// the target.
#[derive(Debug, Clone)]
enum CertificationVariants {
    KeyHandles(KeyHandle, KeyHandle),
    Certs(KeyHandle, Option<CertSynopsis>, KeyHandle, Option<CertSynopsis>),
    Certification(Box<Certification>),
}

/// What we know about a certification, and any errors or lints.
///
/// Sometimes we only know the Key ID of the issuer and the Key ID of
/// the target.
///
/// This is indirectly returned by [`Network::lint_path`].
#[derive(Debug)]
pub struct CertificationLints {
    certification: CertificationVariants,
    userid: Option<UserID>,
    errors: Vec<anyhow::Error>,
    lints: Vec<anyhow::Error>,
}

impl CertificationLints {
    fn from_key_handles(issuer: KeyHandle, target: KeyHandle,
                        userid: Option<UserID>)
        -> Self
    {
        CertificationLints {
            certification:
                CertificationVariants::KeyHandles(issuer, target),
            userid: userid,
            errors: Vec::new(),
            lints: Vec::new(),
        }
    }

    fn from_certs<I, T>(issuer: I, target: T, userid: Option<UserID>)
        -> Self
    where I: Into<CertSynopsis>,
          T: Into<CertSynopsis>,
    {
        let issuer = issuer.into();
        let target = target.into();

        CertificationLints {
            certification:
                CertificationVariants::Certs(
                    issuer.key_handle(), Some(issuer),
                    target.key_handle(), Some(target)),
            userid: userid,
            errors: Vec::new(),
            lints: Vec::new(),
        }
    }

    fn from_certification(certification: Certification)
        -> Self
    {
        let certification = certification.into();

        CertificationLints {
            certification:
                CertificationVariants::Certification(certification),
            userid: None,
            errors: Vec::new(),
            lints: Vec::new(),
        }
    }

    /// Returns the issuer's KeyHandle.
    pub fn issuer(&self) -> KeyHandle {
        match self.certification {
            CertificationVariants::KeyHandles(ref issuer, _) =>
                issuer.clone(),
            CertificationVariants::Certs(ref issuer, _, _, _) =>
                issuer.clone(),
            CertificationVariants::Certification(ref c) =>
                KeyHandle::from(c.issuer().fingerprint()),
        }
    }

    /// Returns the issuer's CertSynopsis, if known.
    pub fn issuer_cert(&self) -> Option<&CertSynopsis> {
        match self.certification {
            CertificationVariants::KeyHandles(_, _) => None,
            CertificationVariants::Certs(_, ref i, _, _) => i.as_ref(),
            CertificationVariants::Certification(ref c) =>
                Some(c.issuer()),
        }
    }

    /// Returns the target's KeyHandle.
    pub fn target(&self) -> KeyHandle {
        match self.certification {
            CertificationVariants::KeyHandles(_, ref target) =>
                target.clone(),
            CertificationVariants::Certs(_, _, ref target, _) =>
                target.clone(),
            CertificationVariants::Certification(ref c) =>
                KeyHandle::from(c.target().fingerprint()),
        }
    }

    /// Returns the target's CertSynopsis, if known.
    pub fn target_cert(&self) -> Option<&CertSynopsis> {
        match self.certification {
            CertificationVariants::KeyHandles(_, _) =>
                None,
            CertificationVariants::Certs(_, _, _, ref t) =>
                t.as_ref(),
            CertificationVariants::Certification(ref c) =>
                Some(c.target()),
        }
    }

    /// Returns the certification's trust amount, if known.
    pub fn amount(&self) -> Option<usize> {
        self.certification().map(|c| c.amount())
    }

    /// Returns the certification's trust depth, if known.
    pub fn depth(&self) -> Option<Depth> {
        self.certification().map(|c| c.depth())
    }

    /// Returns the certification's creation time, if known.
    pub fn creation_time(&self) -> Option<SystemTime> {
        self.certification().map(|c| c.creation_time())
    }

    /// Returns the certification's creation time, if known.
    pub fn expiration_time(&self) -> Option<Option<SystemTime>> {
        self.certification().map(|c| c.expiration_time())
    }

    /// Returns the User ID that is being certified.
    ///
    /// This may be `None` if it is not known, or if this is a
    /// delegation (i.e., a third-party direct key signature).
    pub fn userid(&self) -> Option<&UserID> {
        if let CertificationVariants::Certification(ref c) = self.certification {
            c.userid()
        } else {
            self.userid.as_ref()
        }
    }

    /// Returns the Certification, if it is known.
    pub fn certification(&self) -> Option<&Certification> {
        if let CertificationVariants::Certification(ref c)
            = self.certification
        {
            Some(c)
        } else {
            None
        }
    }

    /// Returns any errors.
    ///
    /// Errors are fatal in the sense that the path is not valid.
    pub fn errors(&self) -> &[anyhow::Error] {
        &self.errors
    }

    /// Returns any lints.
    ///
    /// Lints are not fatal in the sense that the lint does not
    /// necessarily invalidate the path.
    pub fn lints(&self) -> &[anyhow::Error] {
        &self.lints
    }
}

/// A linted path.
///
/// This is returned by [`Network::lint_path`].
///
/// The lifetimes `'a` and `'b` have the same meaning as for
/// [`Store`]: `'a` is the lifetime of the object on the backend, `'b`
/// is the lifetime of the reference to the object, and the object
/// (`'a`) must outlive the reference (`'b`).
#[derive(Debug)]
pub struct PathLints<'a> {
    certs: Vec<CertLints<'a>>,
    certifications: Vec<CertificationLints>,
    certification_network: bool,
}

impl<'a> PathLints<'a> {
    /// Returns whether the path is in a certification network.
    ///
    /// In a certification network, depth constraints and regular
    /// expressions are ignored.
    pub fn certification_network(&self) -> bool {
        self.certification_network
    }

    /// Returns the path's root.
    pub fn root(&self) -> &CertLints<'a> {
        &self.certs[0]
    }

    /// Returns the last node in the path.
    pub fn target(&self) -> &CertLints<'a> {
        &self.certs[self.certs.len() - 1]
    }

    /// Returns an iterator over the certificates.
    pub fn certs(&self) -> impl Iterator<Item=&CertLints<'a>> {
        self.certs.iter()
    }

    /// Returns the number of nodes (certificates) in the path.
    pub fn len(&self) -> usize {
        self.certs.len()
    }

    /// Returns an iterator over the certifications.
    pub fn certifications(&self) -> impl Iterator<Item=&CertificationLints> {
        self.certifications.iter()
    }

    /// Returns the amount that the target is trusted.
    ///
    /// 120 usually means fully trusted.  This function checks that
    /// there are no errors, that each certification's depth parameter
    /// is sufficient for the rest of the path, and that the regular
    /// expression constraints are respected.
    pub fn amount(&self) -> usize {
        tracer!(TRACE, "PathLint::amount");

        // If there are any errors, we return 0.
        if self.certs.iter().any(|c| ! c.errors().is_empty()) {
            return 0;
        }

        let userid = if let Some(userid)
            = self.certifications.last().expect("have one").userid() {
                userid
            } else {
                // This is an invalid path: the last certification
                // doesn't have a User ID.
                t!("Invalid path: no target User ID");
                return 0;
            };

        self.certifications.iter()
            // The required depth for this path to be valid.
            .zip((0..self.certifications.len()).rev())
            .map(|(c, required_depth)| {
                if ! c.errors.is_empty() {
                    return 0;
                }

                if let Some(c) = c.certification() {
                    if self.certification_network {
                        c.amount()
                    } else if c.depth() < required_depth.into() {
                        0
                    } else if required_depth > 0
                        && (! c.regular_expressions()
                            .map(|re_set| {
                                let matches = re_set.matches_userid(&userid);
                                t!("Certification's regular expression \
                                    {} target user ID {}",
                                   if matches {
                                       "matches"
                                   } else {
                                       "does not match"
                                   },
                                   String::from_utf8_lossy(userid.value()));
                                matches
                            })
                            // Invalid => assume everything matches.
                            .unwrap_or(true))
                    {
                        // We check that the current certificate's
                        // regular expressions match the target user
                        // ID UNLESS (`required_depth == 0`) this is
                        // the certification that introduces the
                        // target user ID.
                        //
                        // Consider: Alice delegates to 'Bob
                        // <bob@other.org>', but only for "some.org".
                        // Bob's email address (`bob@other.org`) is
                        // not in some.org, but that doesn't matter
                        // when considering Alice's introduction of
                        // Bob; the regular expressions only scopes
                        // what user IDs Bob can introduce!
                        //
                        // ```
                        //     Alice <alice@example.org>
                        //     |
                        //     | Authorization (depth: 1, amount: 120),
                        //     | Regular expression: some.org
                        //     v
                        //     Bob <bob@other.org>
                        //    /                   \
                        //   / Certification       \ Certification
                        // v                        v
                        // Carol <carol@some.org>   Dave <dave@other.org>
                        // ```
                        0
                    } else {
                        c.amount()
                    }
                } else {
                    0
                }
            }).min().unwrap_or(120) as usize
    }

    /// Converts the `PathLints` into a `Path`.
    ///
    /// This fails if the path is invalid.  Note: the path is still
    /// considered valid even if it doesn't have the required trust
    /// amount as passed to [`Network::lint_path`].
    ///
    /// There may be multiple reasons why a path is invalid.  This
    /// function tries to return the first (when checking from the
    /// root towards the target) reason why it is not valid.
    pub fn to_path(mut self) -> Result<Path> {
        let root = self.certifications.get(0)
            .and_then(|c| c.issuer_cert())
            .ok_or(PathError::EmptyPath)?;

        let singleton = self.certs.len() == 1;

        // If we're only checking a self signature, then we don't have
        // a separate target.
        let target_error = if singleton {
            None
        } else {
            let target = self.certs.pop().expect("have one");
            target.errors.into_iter().next()
        };

        let mut path = Path::new(root.clone());
        path.set_certification_network(self.certification_network);
        for (certification_lints, cert_lints)
            in self.certifications.into_iter()
               .zip(self.certs.into_iter())
        {
            // Issuer.
            if let Some(err) = cert_lints.errors.into_iter().next() {
                return Err(err);
            }
            // Certification.
            if let Some(err) = certification_lints.errors.into_iter().next() {
                return Err(err);
            }
            if let CertificationVariants::Certification(c)
                = certification_lints.certification
            {
                if ! singleton {
                    path.try_append(*c)?;
                }
            } else {
                unreachable!("If there's an error, \
                              we would have recorded it");
            }
        }

        if let Some(err) = target_error {
            return Err(err)
        }

        Ok(path)
    }
}

impl<'a> From<&Path> for PathLints<'a> {
    fn from(path: &Path) -> PathLints<'a> {
        let mut certs: Vec<CertLints> = Vec::new();
        let mut certifications: Vec<CertificationLints> = Vec::new();

        for c in path.certifications() {
            certs.push(CertLints::from_cert_synopsis(c.issuer().clone()));
            certifications.push(
                CertificationLints::from_certification(c.clone()));
        }
        certs.push(CertLints::from_cert_synopsis(path.target().clone()));

        PathLints {
            certs,
            certifications,
            certification_network: path.certification_network(),
        }
    }
}

/// The lifetimes `'a` and `'b` have the same meaning as for
/// [`Store`]: `'a` is the lifetime of the object on the backend, `'b`
/// is the lifetime of the reference to the object, and the object
/// (`'a`) must outlive the reference (`'b`).
impl<'a, S> Network<S>
    where S: Store + Backend<'a>
{
    /// Authenticates a path in the network.
    ///
    /// This checks that there are valid certifications from the first
    /// certificate in `khs` to the last over the User ID, `userid`
    /// for the specified trust amount.
    ///
    /// This function will return `Ok` if a path with the required
    /// trust amount can be found.
    ///
    /// Unlike [`Network::lint_path`], this function returns as soon
    /// as an error is encountered.
    ///
    /// This function requires that the [`Network`] object implement
    /// [`Backend`] in addition to [`Store`].  This is technically
    /// needed by [`Network::lint_path`] to provide better diagnostics,
    /// but it is not strictly required by [`Network::path`], which
    /// only needs active certifications.  This requirement exists,
    /// because [`Network::path`] and [`Network::lint_path`] share a
    /// fair amount of code.  This bound may be lifted in the future.
    ///
    /// [`Network`]: crate::Network
    /// [`Backend`]: crate::store::Backend
    /// [`Store`]: crate::store::Store
    pub fn path<U>(&self, khs: &[KeyHandle], userid: U,
                   required_amount: usize,
                   policy: &dyn Policy)
        -> Result<Path>
    where U: Borrow<UserID>
    {
        let userid = userid.borrow();

        self.path_internal(khs, userid, required_amount, policy, false)
            .and_then(|path_info| {
                let path = path_info.to_path()?;
                let amount = path.amount();
                if amount < required_amount {
                    Err(PathError::PathInadequate(
                            khs.to_vec(), userid.clone(),
                            amount, required_amount)
                        .into())
                } else {
                    Ok(path)
                }
            })
    }

    /// Lints a path in the network.
    ///
    /// This checks that the there are valid certifications from the
    /// first certificate in `khs` to the last over the User ID,
    /// `userid`.
    ///
    /// This function almost always returns `Ok`; it only returns an
    /// error in an extraordinary circumstance.
    ///
    /// Unlike [`Network::path`], this function does extra work to
    /// identify reasons why a path is invalid.  For instance, if
    /// there is no valid certification for a path segment, but there
    /// is an expired certification that is expired, this function
    /// will indicate that.
    pub fn lint_path<U>(&self, khs: &[KeyHandle], userid: U,
                        required_amount: usize,
                        policy: &dyn Policy)
        -> Result<PathLints<'a>>
    where U: Borrow<UserID>
    {
        self.path_internal(khs, userid, required_amount, policy, true)
    }

    /// Authenticates a path in the network.
    fn path_internal<U>(&self, khs: &[KeyHandle], userid: U,
                        required_amount: usize,
                        policy: &dyn Policy,
                        lint: bool)
        -> Result<PathLints<'a>>
    where U: Borrow<UserID>
    {
        let userid = userid.borrow();

        tracer!(TRACE, "Network::path_internal");
        t!("Checking path {} {}",
           khs.iter()
               .map(|kh| KeyID::from(kh).to_hex())
               .collect::<Vec<String>>()
               .join(" "),
           String::from_utf8_lossy(userid.value()));

        if khs.len() == 0 {
            return Err(PathError::EmptyPath.into());
        }

        // Change the lifetime.
        let khs: &[KeyHandle] = khs;

        // XXX: let policy = self.policy();
        let reference_time = self.reference_time();

        // Look up the certificates.
        let mut cert_lints: Vec<CertLints> = Vec::with_capacity(khs.len());
        let mut certs: Vec<Option<Arc<LazyCert>>>
            = Vec::with_capacity(khs.len());
        for kh in khs.iter() {
            cert_lints.push(CertLints::from_key_handle(kh.clone()));
            let cl = cert_lints.last_mut().expect("have one");

            certs.push(None);
            let cert = certs.last_mut().expect("have one");

            match self.lookup_by_cert(kh) {
                Ok(certs) => {
                    if certs.len() > 1 {
                        // XXX: keyid collision :/.  Silently ignore for
                        // now.
                        t!("Store returned multiple certificates \
                            for {}: {}",
                           kh,
                           certs.iter()
                               .map(|c| c.fingerprint().to_hex())
                               .collect::<Vec<String>>()
                               .join(", "));
                    }

                    if let Some(c) = certs.into_iter().next() {
                        t!("Looking up {}: hit!", kh);
                        *cl = CertLints::from_lazy_cert(c.clone());
                        *cert = Some(c);
                    } else {
                        let err = StoreError::NotFound(kh.clone()).into();
                        t!("Looking up {}: {}", kh, err);
                        if lint {
                            // We'll transform this to a valid
                            // cert below.
                            cl.errors.push(err);
                        } else {
                            return Err(err);
                        }
                    }
                }
                Err(err) =>  {
                    t!("Looking up {}: {}", kh, err);
                    if lint {
                        cl.errors.push(err);
                    } else {
                        return Err(err);
                    }
                }
            }
        }

        assert_eq!(certs.len(), khs.len());
        assert_eq!(cert_lints.len(), khs.len());

        // Convert them to ValidCerts (if the policy allows it).  Due
        // to lifetimes, we don't do this in the previous loop.
        let certs: Vec<Option<ValidCert>> = certs.iter()
            .zip(cert_lints.iter_mut())
            .map(|(c, cl)| {
                if let Some(c) = c {
                    match c.with_policy(policy, reference_time) {
                        Ok(c) => Ok(Some(c)),
                        Err(err) => {
                            if lint {
                                // We're linting.  Just keep going.
                                cl.errors.push(err);
                                Ok(None)
                            } else {
                                Err(err)
                            }
                        }
                    }
                } else {
                    Ok(None)
                }
            })
            .collect::<Result<Vec<_>>>()?;


        // If we were only give a single node, we assume the caller is
        // asking the question: does this node have this self
        // signature?  In that case, we run one iteration of the where
        // the issuer and target are the same.
        let singleton = khs.len() == 1;

        // Look for a valid certification for each piece of the path.
        let mut certification_lints = Vec::with_capacity(certs.len() - 1);
        'certification: for i in 0..(certs.len() - 1).max(1) {
            // Whether this is the last path segment.
            let last = singleton || (i == certs.len() - 2);

            let issuer: Option<&ValidCert> = certs[i].as_ref();
            let issuer_kh = issuer.map(|c| c.key_handle())
                .unwrap_or_else(|| khs[i].clone());

            // Carefully handle the singleton case:
            let target: Option<&ValidCert> = if singleton {
                issuer
            } else {
                certs[i + 1].as_ref()
            };
            let target_kh = target.map(|c| c.key_handle())
                .unwrap_or_else(|| {
                    if singleton {
                        issuer_kh.clone()
                    } else {
                        khs[i + 1].clone()
                    }
                });
            t!("Considering {} -> {}", issuer_kh, target_kh);

            certification_lints.push(
                CertificationLints::from_key_handles(
                    issuer_kh.clone(), target_kh.clone(),
                    if last { Some(userid.clone()) } else { None }));
            let mut cl = certification_lints.last_mut().expect("have one");

            if issuer.is_none() {
                let err = PathError::MissingIssuer(issuer_kh.clone());
                t!("  {} -> {}: {}",
                   KeyID::from(&issuer_kh), KeyID::from(&target_kh),
                   err);
                cl.errors.push(err.into());
            }
            if target.is_none() {
                let err = PathError::MissingTarget(target_kh.clone());
                t!("  {} -> {}: {}",
                   KeyID::from(&issuer_kh), KeyID::from(&target_kh),
                   err);
                cl.errors.push(err.into());
            }

            let target: &ValidCert = if let Some(target) = target {
                target
            } else {
                // We already emitted a lint.
                continue 'certification;
            };

            if last {
                // We need to check that the target is valid (i.e., it
                // is not expired, and not revoked) at the reference
                // time.  Note: Certification::try_from_signature
                // already checks that the certification and the
                // certificates are valid at the *certification* time.

                match target.clone().with_policy(target.policy(), reference_time) {
                    Err(err) => {
                        // Target is invalid at the reference time.
                        if lint {
                            cert_lints.last_mut().expect("have one")
                                .errors.push(err.into());
                        } else {
                            return Err(err.into());
                        }
                    }
                    Ok(vc) => {
                        // Check that the target is not revoked.
                        if let RevocationStatus::Revoked(revs)
                            = vc.revocation_status()
                        {
                            let rev = revs.iter().next().expect("have one");

                            // We know we have at least one revocation.
                            let reason = rev.reason_for_revocation();
                            let msg = reason
                                .map(|r| r.1.to_vec())
                                .unwrap_or(Vec::new());
                            let code = reason
                                .map(|r| r.0)
                                .unwrap_or(ReasonForRevocation::Unspecified);

                            let err = PathError::TargetRevoked(
                                target.key_handle(), code, msg,
                                rev.signature_creation_time()
                                    .unwrap_or(std::time::UNIX_EPOCH),
                                reference_time);
                            t!("{}", err);
                            if lint {
                                cert_lints.last_mut().expect("have one")
                                    .errors.push(err.into());
                            } else {
                                return Err(err.into());
                            }
                        }

                        // Check that the target certificate is not expired.
                        if let Some(e) = vc.primary_key().key_expiration_time() {
                            if e <= reference_time {
                                let err = PathError::TargetExpired(
                                    target.key_handle(), e, reference_time);
                                t!("{}", err);
                                if lint {
                                    cert_lints.last_mut().expect("have one")
                                        .errors.push(err.into());
                                } else {
                                    return Err(err.into());
                                }
                            }
                        }

                        // The target doesn't need to have self signed
                        // the User ID to authenticate the User ID.
                        // But if the target has revoked it, then it
                        // can't be authenticated.
                        if let Some(ua) = vc.userids().find(|u| {
                            u.userid() == userid
                        })
                        {
                            if let RevocationStatus::Revoked(revs)
                                = ua.revocation_status()
                            {
                                let rev = revs.iter().next().expect("have one");

                                // We know we have at least one revocation.
                                let reason = rev.reason_for_revocation();
                                let msg = reason
                                    .map(|r| r.1.to_vec())
                                    .unwrap_or(Vec::new());
                                let code = reason
                                    .map(|r| r.0)
                                    .unwrap_or(ReasonForRevocation::Unspecified);

                                let err = PathError::TargetUserIDRevoked(
                                    target.key_handle(), userid.clone(),
                                    code, msg,
                                    rev.signature_creation_time()
                                        .unwrap_or(std::time::UNIX_EPOCH),
                                    reference_time);
                                t!("{}", err);
                                if lint {
                                    cert_lints.last_mut().expect("have one")
                                        .errors.push(err.into());
                                } else {
                                    return Err(err.into());
                                }
                            }
                        }
                    }
                }
            }

            let issuer: &ValidCert = if let Some(issuer) = issuer {
                issuer
            } else {
                // We already emitted a lint.
                continue 'certification;
            };
            let issuer_kh = KeyHandle::from(issuer.fingerprint());

            *cl = CertificationLints::from_certs(
                issuer, target,
                if last { Some(userid.clone()) } else { None });

            // We iterate over all of the certifications, take
            // those whose issuer, target and target User ID
            // match what we are looking for and partition
            // them into:
            //
            //  - valid certifications: Those that
            //    Certification::try_from_signature says are
            //    valid.  Note: not all of these are
            //    necessarily *active*.
            //
            //  - invalid_certifications: Those that are
            //    invalid, because they violate the policy, are
            //    revoked, etc.
            let mut valid_certifications: Vec<Certification>
                = Vec::new();
            let mut invalid_certifications:
                Vec<(Signature, Option<UserID>, anyhow::Error)>
                = Vec::new();

            let mut parse_component = |ua: Option<&UserIDAmalgamation>| {
                if let Some(ua) = ua {
                    t!("parse_component({}, {} self certifications, \
                        {} third-party certifications)",
                       String::from_utf8_lossy(ua.userid().value()),
                       ua.self_signatures().count(),
                       ua.certifications().count());
                } else {
                    t!("parse_component(primary)");
                }

                let valid_certifications
                    = if issuer.fingerprint() == target.fingerprint()
                    {
                        t!("Returning self signatures.");
                        if let Some(ua) = ua {
                            Box::new(ua.self_signatures())
                                as Box<dyn Iterator<Item=&Signature>>
                        } else {
                            // This is non-sense: a certificate never
                            // has to delegate to itself.  That would
                            // create a cycle, anyway.
                            Box::new(std::iter::empty())
                        }
                    } else {
                        Box::new(if let Some(ua) = ua {
                            Box::new(ua.certifications())
                                as Box<dyn Iterator<Item=&Signature>>
                        } else {
                            Box::new(target.primary_key().certifications())
                        }
                        .filter(|c| {
                            c.get_issuers()
                                .into_iter().any(|i| {
                                    i.aliases(&issuer_kh)
                                })
                        }))
                    }
                    .filter_map(|c| {
                        match Certification::try_from_signature(
                            &issuer, ua, &target, c)
                        {
                            Ok(c) => Some(c),
                            Err(err) => {
                                t!("  {}", err);
                                if lint {
                                    // Only save the error if we
                                    // are linting.
                                    invalid_certifications.push(
                                        (c.clone(),
                                         ua.map(|ua| ua.userid().clone()),
                                         err));
                                }
                                None
                            }
                        }
                    })
                    .collect::<Vec<_>>();

                valid_certifications
            };

            // Get the active delegations / certifications.
            if last {
                // This is the last path segment: we want a
                // certification of a specific User ID.

                if let Some(ua) = target.cert().userids()
                    .filter(|ua| ua.userid() == userid)
                    .next()
                {
                    valid_certifications = parse_component(Some(&ua));
                }

                if valid_certifications.is_empty() {
                    let err = PathError::NoCertification(
                        CertSynopsis::from(issuer),
                        CertSynopsis::from(target),
                        userid.clone());
                    t!("  {}", err);
                    cl.errors.push(err.into());
                }
            } else {
                // We're looking for a delegation; a certification on
                // any User ID will do.

                // We use the Cert and to the ValidCert, because
                // we want to consider all User IDs and all third
                // party certifications, not only those considered
                // valid by the current policy.
                for ua in target.cert().userids() {
                    valid_certifications.extend_from_slice(
                        &parse_component(Some(&ua)))
                }
                valid_certifications.extend_from_slice(&parse_component(None));

                if valid_certifications.is_empty() {
                    let err = PathError::NoDelegation(
                        CertSynopsis::from(issuer),
                        CertSynopsis::from(target));
                    t!("  {}", err);
                    cl.errors.push(err.into());
                }
            }
            t!("  Have {} valid certifications",
               valid_certifications.len());

            // Checks if a certification is adequate.
            //
            // The first time through, we only look if any
            // certification satisfies the requirements.  If so, we
            // don't want to lint the irrelevant certifications.  The
            // second time through, we know no active certification
            // was sufficient so we do want to lint everything.
            let required_depth = if singleton || self.certification_network() {
                Depth::from(0)
            } else {
                Depth::from(certs.len() - 1 - (i + 1))
            };

            let adequate = |certification: &Certification,
                            cl: Option<&mut CertificationLints>|
            {
                // We check that the current certificate's regular
                // expressions match the target user ID UNLESS
                // (`required_depth == 0`) this is the certification
                // that introduces the target user ID.
                //
                // Consider: Alice delegates to 'Bob <bob@other.org>',
                // but only for "some.org".  Bob's email address
                // (`bob@other.org`) is not in some.org, but that
                // doesn't matter when considering Alice's
                // introduction of Bob; the regular expressions only
                // scopes what user IDs Bob can introduce!
                //
                // ```
                //     Alice <alice@example.org>
                //     |
                //     | Authorization (depth: 1, amount: 120),
                //     | Regular expression: some.org
                //     v
                //     Bob <bob@other.org>
                //    /                   \
                //   / Certification       \ Certification
                // v                        v
                // Carol <carol@some.org>   Dave <dave@other.org>
                // ```
                let result = if ! self.certification_network()
                    && (required_depth > 0.into()
                        && (! certification.regular_expressions()
                            .map(|re_set| re_set.matches_userid(&userid))
                            // Invalid => everything matches.
                            .unwrap_or(true)))
                {
                    if let Some(cl) = cl {
                        let err = PathError::RegexMismatch(
                            certification.clone(), userid.clone());
                        t!("  {}", err);
                        cl.errors.push(err.into());
                    }
                    false
                } else if ! self.certification_network()
                    && certification.depth() < required_depth
                {
                    if let Some(cl) = cl {
                        let err = PathError::InsufficientTrustDepth(
                            certification.clone(), required_depth);
                        t!("  {}", err);
                        cl.errors.push(err.into());
                    }
                    false
                } else if certification.amount() < required_amount {
                    if let Some(cl) = cl {
                        let err = PathError::InsufficientTrustAmount(
                            certification.clone(), required_amount);
                        t!("  {}", err);
                        cl.errors.push(err.into());
                    }
                    false
                } else {
                    true
                };

                t!("  Certification is {}adequate: {:?}",
                   if result { "" } else { "not " },
                   certification);

                result
            };

            // The CertificationSet returns the active
            // certifications, but not in the most convenient
            // form.
            let cs = CertificationSet::from_certifications(
                valid_certifications.clone(), reference_time);
            let active_certifications: Vec<Certification> = cs
                .into_iter()
                .flat_map(|cs| cs.into_certifications())
                .collect();
            t!("Have {} active certifications", active_certifications.len());
            for certification in active_certifications.iter() {
                if adequate(&certification, None) {
                    // We found a good certification /
                    // delegation.  We're done, even if we are
                    // linting.
                    *cl = CertificationLints::from_certification(
                        certification.clone());
                    continue 'certification;
                }
            }

            let err = if last {
                PathError::NoAdequateCertification(
                    CertSynopsis::from(issuer),
                    CertSynopsis::from(target),
                    userid.clone(),
                    required_amount)
            } else {
                PathError::NoAdequateDelegation(
                    CertSynopsis::from(issuer),
                    CertSynopsis::from(target),
                    required_depth, required_amount)
            };
            t!("  {}", err);
            if lint {
                cl.errors.push(err.into());
            } else {
                return Err(err.into());
            }

            // None of the active certifications are adequate.
            // Iterate again, but be verbose.
            for certification in active_certifications.iter() {
                adequate(certification, Some(&mut cl));
            }

            // Now lint the inactive certifications.
            for certification in valid_certifications.iter() {
                // Skip the active certifications.  We just
                // linted them.
                if active_certifications.contains(&certification) {
                    continue;
                }

                if adequate(certification, Some(&mut cl)) {
                    let err = PathError::AdequateButNotActive(
                        certification.clone());
                    t!("  {}", err);
                    cl.errors.push(err.into());
                }
            }

            // Finally add the lints for the invalid certifications.
            for (certification, userid, err)
                in invalid_certifications.into_iter()
            {
                let certification = Certification::from_signature(
                    issuer, userid, target, &certification);
                if adequate(&certification, Some(&mut cl)) {
                    let err = PathError::AdequateButNotValid(
                        certification.clone(), err);
                    t!("  {}", err);
                    cl.errors.push(err.into());
                }
            }
        }

        Ok(PathLints {
            certs: cert_lints,
            certifications: certification_lints,
            certification_network: self.certification_network(),
        })
    }
}

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

    use openpgp::policy::StandardPolicy;

    use crate::NetworkBuilder;
    use crate::store::CertStore;

    // Check that Network::path and Network::lint_path correctly error
    // out (and don't panic) when the path is empty.
    #[test]
    fn empty_path() -> Result<()> {
        let p = &StandardPolicy::new();

        let store = CertStore::from_certs(Vec::new(), p, None)?;
        let network: Network<_> = NetworkBuilder::rootless(&store).build();

        let uid = UserID::from("user@example.org");

        network.path(&[], &uid, 0, p)
            .unwrap_err();

        network.lint_path(&[], &uid, 0, p)
            .unwrap_err();

        Ok(())
    }
}