sequoia-wot 0.15.0

use std::fmt;
use std::ops::Deref;

use sequoia_openpgp as openpgp;

use openpgp::Result;

use crate::Certification;
use crate::Depth;
use crate::CertSynopsis;

/// A path in a Network.
///
/// A path is a sequence of [`Certification`]s where the target of a
/// certification is the issuer of the next certification.  `Path`s
/// are built up gradually using [`Path::try_append`].  As such, a
/// `Path` may just be a path prefix.  For this reason, the regular
/// expression constraint is not enforced.  However, the `Path`
/// implementation does guarantee that the target of a certification
/// is the issuer of the next certification in the path.
#[derive(Clone)]
pub struct Path {
    // The root.
    root: CertSynopsis,

    // Then the transition from the previous node to the next, and the
    // next node.
    edges: Vec<Certification>,

    // Set if the path is in a certification network, i.e., depth
    // constraints and regular expressions are ignored.
    certification_network: bool,

    // Residual depth.  To append a certification, this must be >0.
    // After adding a new certification, the new residual depth is:
    // min(residual_depth - 1, certification.depth).
    residual_depth: Depth,
}

impl fmt::Debug for Path {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let indent = f.precision().unwrap_or(0);
        let indent: String = vec![ ' '; indent ].into_iter().collect();

        f.write_fmt(format_args!(
            "Path [\n"))?;

        if self.certification_network {
            f.write_fmt(format_args!(
                "{}  (certification network)\n", indent))?;
        }

        f.write_fmt(format_args!(
            "{}  {} ({})\n",
            indent,
            self.root.fingerprint(),
            self.root.primary_userid().map(|userid| {
                String::from_utf8_lossy(userid.value()).into_owned()
            }).unwrap_or_else(|| "[no User ID]".into())))?;

        for certification in self.edges.iter() {
            f.write_fmt(format_args!(
                "{}           |\n", indent))?;
            f.write_fmt(format_args!(
                "{}           | depth: {}\n", indent, certification.depth()))?;
            f.write_fmt(format_args!(
                "{}           | amount: {}\n", indent, certification.amount()))?;
            f.write_fmt(format_args!(
                "{}           | regexes: {}\n",
                indent,
                if let Some(re_set) = certification.regular_expressions() {
                    if re_set.matches_everything() {
                        String::from("*")
                    } else {
                        format!("{:?}", re_set)
                    }
                } else {
                    "<invalid RE>".into()
                }))?;
            f.write_fmt(format_args!(
                "{}           v\n", indent))?;
            f.write_fmt(format_args!(
                "{}  {} ({})\n",
                indent, certification.target().fingerprint(),
                certification.userid().map(|userid| {
                    String::from_utf8_lossy(userid.value()).into_owned()
                }).unwrap_or_else(|| "[no User ID]".into())))?;
        }
        f.write_fmt(format_args!("{}]", indent))?;

        Ok(())
    }
}

impl Path {
    /// Instantiates a path starting at the specified root.
    ///
    /// We assume that the root is ultimately trusted (its trust depth
    /// is unlimited and its trust amount is maximal).
    pub fn new<C>(root: C) -> Self
        where C: Into<CertSynopsis>
    {
        Self {
            root: root.into(),

            // Most paths will be direct (one edge) or via one trusted
            // introducer (two edges); meta-introducers are rarely
            // used.
            edges: Vec::with_capacity(2),

            certification_network: false,

            // Unconstrained.
            residual_depth: Depth::new(None),
        }
    }

    /// Controls how path validity is determined.
    ///
    /// In a certification network, trust depth and regular
    /// expressions are ignored and a certification isn't just used to
    /// validate a binding, but also to designate the target
    /// certificate as a trusted introducer.
    pub fn set_certification_network(&mut self, certification_network: bool) {
        self.certification_network = certification_network;
    }

    /// Returns how path validity is determined.
    ///
    /// In a certification network, trust depth and regular
    /// expressions are ignored and a certification isn't just used to
    /// validate a binding, but also to designate the target
    /// certificate as a trusted introducer.
    pub fn certification_network(&self) -> bool {
        self.certification_network
    }

    /// Returns the path's root.
    pub fn root(&self) -> &CertSynopsis {
        &self.root
    }

    /// Returns the last node in the path.
    pub fn target(&self) -> &CertSynopsis {
        if self.edges.len() == 0 {
            &self.root
        } else {
            &self.edges[self.edges.len() - 1].target()
        }
    }

    /// Returns an iterator over the path's certificates (the nodes).
    ///
    /// The certificates are returned from the root towards the target.
    pub fn certificates(&self)
        -> impl Iterator<Item=&CertSynopsis> + DoubleEndedIterator
    {
        std::iter::once(&self.root)
            .chain(self.edges.iter().map(|certification| {
                certification.target()
            }))
    }

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

    /// Returns the certifications.
    ///
    /// The certifications are returned from the root towards the target.
    pub fn certifications(&self) -> impl Iterator<Item=&Certification> {
        self.edges.iter()
    }

    /// Returns the residual trust depth.
    ///
    /// The residual trust depth is calculated by taking the trust
    /// depth of root and reducing it by one for each certification in
    /// the path.  If passing a certification with a lower trust depth
    /// than the current trust value, the lower value is used from
    /// that point on.
    pub fn residual_depth(&self) -> Depth {
        self.residual_depth
    }

    /// Returns the amount that the target is trusted.
    ///
    /// 120 usually means fully trusted.  This function checks that
    /// each certification's depth parameter is sufficient for the
    /// rest of the path.  It does not check any regular expressions,
    /// as the regular expressions only apply to the User ID being
    /// authenticated, and that may not yet have been added to the
    /// path (i.e., the path may be a path prefix).
    pub fn amount(&self) -> usize {
        self.edges.iter()
            // The required depth for this path to be valid.
            .zip((0..self.edges.len()).rev())
            .map(|(e, required_depth)| {
                if self.certification_network
                    || e.depth() >= required_depth.into()
                {
                    e.amount()
                } else {
                    0
                }
            }).min().unwrap_or(120) as usize
    }

    /// Appends the certification to the path.
    ///
    /// This checks that the target of the last certification is the
    /// issuer of the new certification, but it does not check the
    /// depth constraints, nor does it check for cycles.  To ensure
    /// that the path is a valid path prefix, use [`Path::try_append`]
    /// instead.
    pub fn append(&mut self, certification: Certification)
        -> Result<()>
    {
        if self.target().fingerprint() != certification.issuer().fingerprint() {
            return Err(anyhow::format_err!(
                "Can't add certification to path: \
                 the path's tail ({}) is not the certification's issuer ({})",
                self.target().fingerprint(), certification.issuer()));
        }

        let depth = certification.depth();

        self.edges.push(certification);

        self.residual_depth = self.residual_depth
            // Avoid underflow.
            .max(1.into())
            .decrease(1)
            .min(depth);

        Ok(())
    }

    /// Appends the certification to the path if the path allows it.
    ///
    /// This will fail if the trust depth is insufficient, or adding
    /// the certificate would induce a cycle.  This function does not
    /// check any regular expressions, as the regular expressions only
    /// apply to the User ID being authenticated, and that may not yet
    /// have been added to the path (i.e., the path may be a path
    /// prefix).
    pub fn try_append(&mut self, certification: Certification)
        -> Result<()>
    {
        tracer!(false, "Path::try_append");
        t!("  path: {:?}", self);
        t!("  certification: {:?}", certification);

        if ! self.certification_network && self.residual_depth == 0.into() {
            return Err(anyhow::format_err!("Not enough depth"));
        }

        // Check for cycles.  The last two nodes can target the same
        // certificate, but then the target User IDs must be different.
        if self.root.fingerprint() == certification.target().fingerprint()
            || self.edges.iter()
                .enumerate()
                .any(|(i, c)| {
                    if c.target().fingerprint()
                        == certification.target().fingerprint()
                    {
                        if i == self.edges.len() - 1 {
                            c.userid() == certification.userid()
                        } else {
                            true
                        }
                    } else {
                        false
                    }
                })
        {
            return Err(anyhow::format_err!(
                "Adding {} to the path would create a cycle",
                certification.target()));
        }

        self.append(certification)?;

        Ok(())
    }

    /// Returns whether the path describes a self signature.
    pub fn self_signature(&self) -> bool {
        self.edges.is_empty()
    }

    /// Returns whether the specified path is a suffix of the path.
    ///
    /// If two paths are the same, then this returns true.
    ///
    /// A self signature is not considered a suffix of non-self
    /// signature.  That is, a path describing a self-signature for
    /// Alice is different from Bob certifying Alice's certificate.
    ///
    /// This checks that the certificates along the path are the same.
    /// It does *not* check that the certification parameters (the
    /// trust amount, the regular expressions, etc.) or that the user
    /// IDs (including the target user ID) are the same.
    fn has_suffix(&self, path: &Path) -> bool {
        tracer!(false, "Path::has_suffix");
        t!("Self: {:?}", self);
        t!("Other: {:?}", path);

        if self.len() < path.len() {
            // `self` is shorter than `path`.  `path` can't be a
            // suffix of `self`.
            t!("self is shorter ({}) than path ({}); path can't be a suffix.",
               self.len(), path.len());
            return false;
        }

        if self.self_signature() != path.self_signature() {
            t!("self is{} a self signature, path is{}",
               if self.self_signature() {
                   ""
               } else {
                   " not"
               },
               if path.self_signature() {
                   ""
               } else {
                   " not"
               });
            return false;
        }

        let certs_match = self.certificates().rev()
            .zip(path.certificates().rev())
            .all(|(this, other)| {
                this.fingerprint() == other.fingerprint()
            });
        if certs_match {
            t!("Certificates match");
            true
        } else {
            t!("Certificates don't match");
            return false;
        }
    }
}

/// A collection of paths.
///
/// The trust amount is the trust amount while respecting the capacity
/// of the edges.
///
/// # Examples
///
/// Consider the following network (a number next to an edge is that
/// edge's trust amount):
///
/// ```text
///        root
///    60 /    \ 60
///      v      v
///    alice   bob
///    60 \    / 60
///        v  v
///       carol
///         | 90
///         v
///       target
/// ```
///
/// If we consider the following two paths: `root -> alice -> carol ->
/// target` and `root -> bob -> carol -> target`, then they each have
/// a trust amount of 60.  But taken together they only have a trust
/// amount of 90, because the edge `carol -> target` is shared, and
/// its capacity is 90.
#[derive(Clone)]
pub struct Paths {
    paths: Vec<(Path, usize)>,
}

impl Paths {
    /// Returns a new, empty `Paths` data structure.
    pub fn new() -> Self {
        Self {
            paths: Vec::new(),
        }
    }

    /// Returns an iterator over the paths.
    ///
    /// Returns an iterator over a reference to each path and its
    /// trust amount.
    ///
    /// Note: the trust amount is not recalculate, but is simply what
    /// was set when the `Path` was add using [`Paths::push`].
    pub fn iter(&self) -> impl Iterator<Item=&(Path, usize)> {
        self.paths.iter()
    }

    /// Returns an iterator over the paths.
    ///
    /// Returns an iterator over each path and its trust amount.
    ///
    /// Note: the trust amount is not recalculate, but is simply what
    /// was set when the `Path` was add using [`Paths::push`].
    pub fn into_iter(self) -> impl Iterator<Item=(Path, usize)> {
        self.paths.into_iter()
    }

    /// The aggregate trust amount.
    ///
    /// This respects the network's capacity.  Thus, if multiple paths
    /// use the same edge, the total trust amount may be less than
    /// simple the trust amount of each individual path.
    pub fn amount(&self) -> usize {
        self.paths.iter().map(|(_, a)| a).sum()
    }

    /// Adds a path.
    ///
    /// `amount` is the trust amount that this path contributes to the
    /// authentication.  This may be less than `path.amount()` if it
    /// overlaps with other paths in the path set.
    pub fn push(&mut self, path: Path, amount: usize) {
        self.paths.push((path, amount));
    }

    /// Returns whether the specified path is a suffix of an existing
    /// path.
    ///
    /// This only compares the certificates; it does not compare the
    /// trust values.
    pub fn has_suffix(&self, path: &Path) -> bool {
        self.iter().any(|(other, _amount)| other.has_suffix(path))
    }
}

impl Deref for Paths {
    type Target=[(Path, usize)];

    fn deref(&self) -> &Self::Target {
        &self.paths[..]
    }
}

impl fmt::Debug for Paths {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let indent = f.precision().unwrap_or(0);
        let indent: String = vec![ ' '; indent ].into_iter().collect();

        f.write_fmt(format_args!("Paths [\n"))?;
        for (i, (p, a)) in self.iter().enumerate() {
            f.write_fmt(format_args!(
                "{}  PATH #{}, trust amount: {}: {:.*?}\n",
                indent, i, a, indent.len() + 2, p))?;
        }
        f.write_fmt(format_args!("{}]", indent))?;
        Ok(())
    }
}

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

    use std::time::SystemTime;

    use sequoia_openpgp as openpgp;
    use openpgp::Fingerprint;
    use sequoia_openpgp::packet::UserID;
    use openpgp::types::RevocationStatus;

    #[allow(unused)]
    #[test]
    fn has_suffix() {
        let alice_fpr: Fingerprint =
            "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
            .parse().expect("valid fingerprint");
        let alice_uid = UserID::from("<alice@example.org>");

        let alice = CertSynopsis::new(
            alice_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            std::iter::once((alice_uid.clone(), SystemTime::now())));

        let bob_fpr: Fingerprint =
            "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
            .parse().expect("valid fingerprint");
        let bob_uid = UserID::from("<bob@example.org>");

        let bob = CertSynopsis::new(
            bob_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            std::iter::once((bob_uid.clone(), SystemTime::now())));

        let carol_fpr: Fingerprint =
            "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"
            .parse().expect("valid fingerprint");
        let carol_uid = UserID::from("<carol@example.org>");

        let carol = CertSynopsis::new(
            carol_fpr.clone(), None,
            RevocationStatus::NotAsFarAsWeKnow.into(),
            std::iter::once((carol_uid.clone(), SystemTime::now())));

        let t = SystemTime::now();

        // Alice certifies Bob.
        let alice_certifies_bob
            = Certification::new(alice.clone(),
                                 Some(bob_uid.clone()),
                                 bob.clone(),
                                 t);

        // Alice certifies Carol.
        let alice_certifies_carol
            = Certification::new(alice.clone(),
                                 Some(carol_uid.clone()),
                                 carol.clone(),
                                 t);

        // Bob certifies Carol.
        let bob_certifies_carol
            = Certification::new(bob.clone(),
                                 Some(carol_uid.clone()),
                                 carol.clone(),
                                 t);

        let mut alice_bob_carol = Path::new(alice.clone());
        alice_bob_carol.append(alice_certifies_bob.clone());
        alice_bob_carol.append(bob_certifies_carol.clone());

        let mut alice_bob = Path::new(alice.clone());
        alice_bob.append(alice_certifies_bob.clone());

        let mut alice_carol = Path::new(alice.clone());
        alice_carol.append(alice_certifies_carol.clone());

        let mut bob_carol = Path::new(bob.clone());
        bob_carol.append(bob_certifies_carol.clone());

        // The following are self signatures and thus aren't suffixes
        // of longer paths.
        let mut alice = Path::new(alice.clone());
        let mut bob = Path::new(bob.clone());
        let mut carol = Path::new(carol.clone());

        assert!(! alice.has_suffix(&bob));
        assert!(alice.has_suffix(&alice));

        assert!(! alice_bob.has_suffix(&alice));
        assert!(alice_bob.has_suffix(&alice_bob));
        assert!(! alice_bob.has_suffix(&alice_carol));
        assert!(! alice_bob.has_suffix(&bob));

        assert!(! alice_bob_carol.has_suffix(&alice));
        assert!(! alice_bob_carol.has_suffix(&bob));
        assert!(! alice_bob_carol.has_suffix(&carol));
        assert!(! alice_bob_carol.has_suffix(&alice_bob));
        assert!(! alice_bob.has_suffix(&alice_carol));
        assert!(alice_bob_carol.has_suffix(&alice_bob_carol));
        assert!(alice_bob_carol.has_suffix(&bob_carol));
    }
}