sequoia_git/

policy.rs

use std::{
    collections::{BTreeMap, BTreeSet, btree_map::Entry, HashSet},
    env,
    fmt,
    fs,
    io::{self, Read, Write},
    path::{Path, PathBuf},
    time::SystemTime,
};

use git2::{
    Repository,
    Oid,
};
use serde::{Deserialize, Serialize};

use sequoia_openpgp::{
    self as openpgp,
    Cert,
    Fingerprint,
    KeyHandle,
    Packet,
    cert::{
        amalgamation::ValidAmalgamation,
        prelude::{SubordinateKeyAmalgamation, UserIDAmalgamation},
        raw::{RawCert, RawCertParser},
    },
    packet::{
        Signature,
        UserID,
        key::PublicParts,
    },
    parse::Parse,
    parse::{stream::*},
    policy::StandardPolicy,
    serialize::Serialize as _,
    types::SignatureType,
};

use crate::{
    Error,
    Result,
    utils::prune_cert,
    utils::serialize_packet,
    utils::serialize_signature,
};

/// Whether to trace execution by default (on stderr).
const TRACE: bool = false;

/// A policy for OpenPGP signatures in git.
///
/// A `Policy` governs state changes in git repositories.  A state
/// change is a change from one git commit with a policy embedded into
/// it to the next commit, which may change the policy, the source, or
/// both.
#[derive(Default, Clone, Deserialize, Serialize, PartialEq, Eq)]
pub struct Policy {
    /// Policy version.
    ///
    /// We provide backwards-compatibility but not
    /// forward-compatibility, so that we can evolve the policy
    /// language.
    #[serde(default)]
    version: usize,

    /// Set of commits that is assumed to be good.
    ///
    /// The commits will pass verification even if it would fail for
    /// whatever reason.
    ///
    /// To change this set, you need the `audit` right.
    #[serde(default)]
    commit_goodlist: BTreeSet<String>,

    /// Set of authorizations.
    ///
    /// The key is a free-form, human-readable identifier for the
    /// authorization.
    #[serde(default)]
    authorization: BTreeMap<String, Authorization>,
}

impl Policy {
    /// Returns the path to the policy file in the current git
    /// repository.
    fn working_dir_policy_file()  -> Result<PathBuf> {
        let git = git2::Repository::discover(env::current_dir()?)?;
        if let Some(wd) = git.workdir() {
            Ok(wd.join("openpgp-policy.toml"))
        } else {
            Err(Error::InvalidOperation("doesn't work on bare repos".into()))
        }
    }

    pub fn parse_bytes<D: AsRef<[u8]>>(bytes: D) -> Result<Self> {
        let bytes = bytes.as_ref();
        let s = std::str::from_utf8(bytes)
            .map_err(|e| Error::StorageError(e.to_string()))?;
        let policy = toml::from_str(s)
            .map_err(|e| Error::StorageError(e.to_string()))?;
        Ok(policy)
    }

    /// Reads the policy from the given path.
    pub fn read_file<P: AsRef<Path>>(path: P) -> Result<Policy> {
        let path = path.as_ref();
        let mut f = fs::File::open(path)?;

        let mut s = String::new();
        f.read_to_string(&mut s)?;
        let p: Policy =
            toml::from_str(&s).map_err(|e| Error::StorageError(e.to_string()))?;

        Ok(p)
    }

    /// Reads the policy from the given path.
    pub fn read_file_or_default<P: AsRef<Path>>(path: P) -> Result<Policy> {
        let path = path.as_ref();
        let mut f = match fs::File::open(path) {
            Ok(f) => f,
            Err(e) => if e.kind() == io::ErrorKind::NotFound {
                return Ok(Policy::default());
            } else {
                return Err(e.into());
            },
        };

        let mut s = String::new();
        f.read_to_string(&mut s)?;
        let p: Policy =
            toml::from_str(&s).map_err(|e| Error::StorageError(e.to_string()))?;

        Ok(p)
    }

    /// Reads the policy from the current git working directory.
    ///
    /// Default to the empty policy if the work directory doesn't
    /// contain a policy.
    pub fn read_from_working_dir() -> Result<Policy> {
        Self::read_file_or_default(&Self::working_dir_policy_file()?)
    }

    /// Reads the policy from the given git commit.
    pub fn read_bytes_from_commit(git: &Repository, commit: &Oid)
        -> Result<Vec<u8>>
    {
        tracer!(TRACE, "Policy::read_bytes_from_commit");
        t!("(_, {})", commit);

        let commit = git.find_commit(commit.clone())?;
        let tree = commit.tree()?;
        let result = if let Some(entry) = tree.get_name("openpgp-policy.toml") {
            Ok(entry.to_object(&git)?.peel_to_blob()?.content().to_vec())
        } else {
            Err(Error::MissingPolicy(commit.id()))
        };
        result
    }

    /// Reads the policy from the given git commit.
    pub fn read_from_commit(git: &Repository, commit: &Oid) -> Result<Self> {
        Self::parse_bytes(Self::read_bytes_from_commit(git, commit)?)
    }

    /// Writes the policy into a file with the given path.
    pub fn write<P: AsRef<Path>>(&self, path: P) -> Result<()> {
        let path = path.as_ref();
        let mut new =
            tempfile::NamedTempFile::new_in(path.parent().unwrap())?;

        new.write_all(toml::to_string_pretty(&self)
                      .map_err(|e| Error::StorageError(e.to_string()))?
                      .as_bytes())?;

        new.persist(path).map_err(|e| Error::StorageError(e.to_string()))?;

        Ok(())
    }

    /// Writes the policy to the current git working directory.
    pub fn write_to_working_dir(&self) -> Result<()> {
        self.write(&Self::working_dir_policy_file()?)
    }

    /// The policy version.
    pub fn version(&self) -> usize {
        self.version
    }

    /// Set of commits that is assumed to be good.
    ///
    /// The commits will pass verification even if it would fail for
    /// whatever reason.
    ///
    /// To change this set, you need the `audit` right.
    pub fn commit_goodlist(&self) -> &BTreeSet<String> {
        &self.commit_goodlist
    }

    /// Set of commits that is assumed to be good.
    ///
    /// The commits will pass verification even if it would fail for
    /// whatever reason.
    ///
    /// To change this set, you need the `audit` right.
    pub fn commit_goodlist_mut(&mut self) -> &mut BTreeSet<String> {
        &mut self.commit_goodlist
    }

    /// Set of authorizations.
    ///
    /// The key is a free-form, human-readable identifier for the
    /// authorization.
    pub fn authorization(&self) -> &BTreeMap<String, Authorization> {
        &self.authorization
    }

    /// Set of authorizations.
    ///
    /// The key is a free-form, human-readable identifier for the
    /// authorization.
    pub fn authorization_mut(&mut self) -> &mut BTreeMap<String, Authorization> {
        &mut self.authorization
    }

    /// Computes the difference between this policy and `other`.
    pub fn diff<'f, 't>(&'f self, other: &'t Policy) -> Result<Diff<'f, 't>> {
        let mut changes = Vec::new();

        // First, the version.
        if self.version != other.version {
            changes.push(Change::VersionChange {
                from: self.version,
                to: other.version,
            });
        }

        // Then, the commit goodlist.
        for c in self.commit_goodlist.difference(&other.commit_goodlist) {
            changes.push(Change::UngoodlistCommit(c.parse()?));
        }
        for c in other.commit_goodlist.difference(&self.commit_goodlist) {
            changes.push(Change::GoodlistCommit(c.parse()?));
        }

        // This null authorization comes in handy when introducing
        // new users and removing users.
        let null_auth = Authorization::default();

        // Now for the authorizations.  First, see if some vanished.
        for (k, from) in self.authorization.iter()
            .filter(|(k, _)| ! other.authorization.contains_key(k.as_str()))
        {
            // First, remove all the rights and certs.
            from.diff(&null_auth, k.into(), &mut changes);

            // Finally, remove the user.
            changes.push(Change::RetireUser(k.into()));
        }

        // Then, compare the common ones.
        for (k, from, to) in self.authorization.iter()
            .filter_map(|(k, from)| other.authorization.get(k)
                        .map(|to| (k, from, to)))
        {
            from.diff(to, k.into(), &mut changes);
        }

        // See if new users were introduced.
        for (k, to) in other.authorization.iter()
            .filter(|(k, _)| ! self.authorization.contains_key(k.as_str()))
        {
            // First introduce the new user.
            changes.push(Change::AddUser(k.into()));

            // Then, all the new rights and certs.
            null_auth.diff(to, k.into(), &mut changes);
        }

        Ok(Diff {
            version: DIFF_JSON_VERSION,
            from: self,
            changes,
            to: other,
        })
    }

    /// Verifies that the given commit adheres to this policy.
    ///
    /// During verification, the key(s) used are stored in
    /// `signer_keys`, and the primary user id of the issuing cert at
    /// the time of the signing is stored in `primary_uids`.  This
    /// information can be used to prune certs in a policy.
    ///
    /// If the commit is goodlisted, this function returns Ok with an
    /// empty vector of verification results.
    pub fn verify(&self, git: &Repository, commit_id: &Oid,
                  commit_policy: &Policy,
                  signer_keys: &mut BTreeSet<Fingerprint>,
                  primary_uids: &mut BTreeSet<UserID>)
                  -> Result<Vec<Result<(String, Signature, Cert, Fingerprint)>>>
    {
        tracer!(TRACE, "Policy::verify");
        t!("verify(_, {})", commit_id);

        if self.commit_goodlist.contains(&commit_id.to_string()) {
            Ok(vec![])
        } else {
            let Ok((sig, data)) = git.extract_signature(commit_id, None)
            else {
                return Ok(vec![Err(Error::MissingSignature(commit_id.clone()))]);
            };
            t!("{} bytes of signature", sig.len());

            //let commit = git.find_commit(commit_id.clone())?;
            //let commit_time = commit.time();
            //let commit_time = std::time::UNIX_EPOCH
            //    + std::time::Duration::new(commit_time.seconds() as u64, 0);

            // Note the commit time and the signature time will often
            // diverge.  This is because the signature is created
            // after the commit is made (the signature is over the
            // commit, including the creation time).  If we use the
            // commit's time as the reference time, then the signature
            // will appear to have been made in the future.  Note: it
            // is not enough to allow a few seconds of divergence,
            // because commits can be resigned without changing the
            // commit's time.
            self.verify_(&sig[..], &data[..],
                         commit_policy,
                         None,
                         signer_keys,
                         primary_uids,
                         Error::MissingSignature(commit_id.clone()),
                         Right::SignCommit)
        }
    }

    pub fn verify_archive<T, S>(&self,
                                signature: S,
                                archive: T)
                                -> Result<Vec<Result<(String, Signature, Cert,
                                                      Fingerprint)>>>
    where
        T: AsRef<[u8]>,
        S: AsRef<[u8]>,
    {
        let mut signer_keys = Default::default();
        let mut primary_uids = Default::default();
        self.verify_(signature.as_ref(),
                     archive.as_ref(),
                     self,
                     None,
                     &mut signer_keys,
                     &mut primary_uids,
                     Error::MissingDataSignature("Tarball".into()),
                     Right::SignArchive)
    }

    fn verify_(&self,
               signature: &[u8],
               data: &[u8],
               commit_policy: &Policy,
               commit_time: Option<SystemTime>,
               signer_keys: &mut BTreeSet<Fingerprint>,
               primary_uids: &mut BTreeSet<UserID>,
               missing_signature_error: Error,
               require_right: Right)
               -> Result<Vec<Result<(String, Signature, Cert, Fingerprint)>>>
    {
        tracer!(TRACE, "Policy::verify_");
        t!("verify_({} bytes, {} bytes, _, {:?}, _, _, {}, {})",
           signature.len(), data.len(), commit_time,
           missing_signature_error, require_right);

        let p = &StandardPolicy::new();
        let h = Helper {
            parent_policy: self,
            child_policy: commit_policy,
            signer_keys,
            primary_uids,
            results: Default::default(),
        };

        let mut v = DetachedVerifierBuilder::from_bytes(signature)?
            .with_policy(p, commit_time, h)?;
        v.verify_bytes(data)?;
        let h = v.into_helper();
        let signature_results = h.results;

        if signature_results.is_empty() {
            t!("no signatures found!");
            return Ok(vec![Err(missing_signature_error)]);
        }

        if signature_results.iter().all(|r| r.is_err()) {
            let e = signature_results.into_iter().find(|r| r.is_err())
                .expect("not empty and not all were ok");
            return Err(e.unwrap_err());
        }

        // If we are here, there is at least one valid OpenPGP
        // signature.  Compute the diff between the policies, and
        // check whether the authorization invariant is intact.
        let diff = self.diff(commit_policy)?;

        let mut results: Vec<Result<(String, Signature, Cert, Fingerprint)>>
            = Vec::new();
        for r in signature_results {
            match r {
                Ok((sig, cert, signer_fpr)) => {
                    // Find all authorizations that contain a
                    // certificate that did issue a valid signature.
                    let cert_fp = cert.fingerprint();
                    for (name, a) in self.authorization.iter()
                        .filter(|(_, a)| a.certs().into_iter()
                                .flat_map(|r| r.into_iter())
                                .flat_map(|r| r.into_iter())
                                .any(|c| c.fingerprint() == cert_fp))
                    {
                        t!("{}: valid signature", name);
                        let r = a.rights();
                        t!("{}: {:?}", name, r);

                        if let Err(e) = r.assert(require_right)
                            .and_then(|_| diff.assert(&r))
                        {
                            results.push(Err(e));
                        } else {
                            results.push(
                                Ok((name.into(), sig.clone(), cert.clone(),
                                    signer_fpr.clone())));
                        }
                    }
                },
                Err(e) => results.push(Err(e)),
            }
        }

        Ok(results)
    }
}

// This fetches keys and computes the validity of the verification.
struct Helper<'p> {
    parent_policy: &'p Policy,
    child_policy: &'p Policy,
    //signer_userids: &'p mut BTreeSet<openpgp::packet::UserID>,
    signer_keys: &'p mut BTreeSet<openpgp::Fingerprint>,
    primary_uids: &'p mut BTreeSet<UserID>,
    results: Vec<Result<(Signature, Cert, Fingerprint)>>,
}

impl Helper<'_> {
    fn handle_result(&mut self, r: VerificationResult) {
        tracer!(TRACE, "VerificationHelper::handle_result");
        match r {
            Ok(sig) => {
                self.signer_keys.insert(sig.ka.key().fingerprint());

                if let Ok(userid) = sig.ka.valid_cert().primary_userid() {
                    let u = userid.userid();
                    if ! self.primary_uids.contains(u) {
                        self.primary_uids.insert(u.clone());
                    }
                }

                self.results.push(
                    Ok((sig.sig.clone(), sig.ka.cert().clone(),
                        sig.ka.key().fingerprint().clone())));
            },
            Err(e) => {
                t!("Signature verification failed: {}", e);
                use VerificationError::*;
                self.results.push(Err(match e {
                    MalformedSignature { error, .. } =>
                        Error::BadSignature(error.to_string()),
                    MissingKey { sig } => {
                        let mut issuers = sig.get_issuers();
                        if issuers.is_empty() {
                            Error::BadSignature(
                                "No issuer information".into())
                        } else {
                            Error::MissingKey(issuers.remove(0))
                        }
                    },
                    UnboundKey { cert, error, .. } =>
                        Error::BadKey(cert.key_handle(),
                                      error.to_string()),
                    BadKey { ka, error, .. } =>
                        Error::BadKey(ka.cert().key_handle(),
                                      error.to_string()),
                    BadSignature { error, .. } =>
                        Error::BadSignature(error.to_string()),
                    UnknownSignature { sig, .. } =>
                        Error::BadSignature(sig.error().to_string()),
                    u =>
                        Error::BadSignature(u.to_string()),
                }));
            },
        }
    }
}

impl VerificationHelper for Helper<'_> {
    fn get_certs(&mut self, ids: &[KeyHandle]) -> openpgp::Result<Vec<Cert>> {
        tracer!(TRACE, "VerificationHelper::get_certs");
        t!("get_certs({:?})", ids);

        let mut matches: BTreeMap<Fingerprint, Cert> = BTreeMap::new();

        let mut parent: BTreeMap<Fingerprint, Vec<RawCert>> = BTreeMap::new();

        for (name, auth) in self.parent_policy.authorization.iter() {
            for cert in auth.certs()? {
                let cert = cert?;

                // parent contains all of the certificates.
                let entry = parent.entry(cert.fingerprint());
                match entry {
                    Entry::Occupied(mut oe) => {
                        oe.get_mut().push(cert.clone());
                    }
                    Entry::Vacant(ve) => {
                        ve.insert(vec![ cert.clone() ]);
                    }
                }

                if cert.keys().any(
                    |k| ids.iter().any(|i| i.aliases(&k.key_handle())))
                {
                    t!("Signature could be from {}", name);

                    let cert = Cert::try_from(cert)?;

                    let entry = matches.entry(cert.fingerprint());
                    match entry {
                        Entry::Occupied(mut oe) => {
                            let c: &mut Cert = oe.get_mut();
                            *c = c.clone().merge_public(cert)?;
                        }
                        Entry::Vacant(ve) => {
                            ve.insert(cert);
                        }
                    }
                }
            }
        }

        // We now merge in certificate updates from the child.  That
        // is, we *don't* add new certificates.

        // Optimize the typical case: the policies are the same and
        // thus the child has no updates.
        if self.parent_policy != self.child_policy {
            // Merge child into parent stripping any revocation
            // certificates from the child.
            let merge = |parent: Cert, child: Cert| -> Result<Cert> {
                let child = child.into_packets().filter(|p| {
                    if let Packet::Signature(sig) = p {
                        ! matches!(sig.typ(),
                                   SignatureType::KeyRevocation
                                   | SignatureType::SubkeyRevocation
                                   | SignatureType::CertificationRevocation)
                    } else {
                        true
                    }
                });

                Ok(parent.insert_packets(child)?.0)
            };

            for (name, auth) in self.child_policy.authorization.iter() {
                let child_certs = if let Ok(certs) = auth.certs() {
                    certs
                } else {
                    // Silently ignore any parse errors.
                    continue;
                };

                for child_cert in child_certs {
                    let child_cert = if let Ok(cert) = child_cert {
                        cert
                    } else {
                        // Silently ignore any parse errors.
                        continue;
                    };

                    let fpr = child_cert.fingerprint();
                    if let Some(cert) = matches.get_mut(&fpr) {
                        t!("Updating {}", fpr);

                        let child_cert = if let Ok(cert)
                            = Cert::try_from(child_cert)
                        {
                            cert
                        } else {
                            // Silently ignore any parse errors.
                            continue;
                        };

                        if let Ok(merged) = merge(cert.clone(), child_cert) {
                            *cert = merged;
                        }
                    } else {
                        if child_cert.keys().any(
                            |k| ids.iter().any(|i| i.aliases(&k.key_handle())))
                        {
                            t!("Signature could be from {}", name);

                            // cert is not in matches, but it is
                            // present in the parent policy.  This
                            // happens if the certificate gains a
                            // subkey in the child policy, and the
                            // commit is signed by that subkey.
                            if let Some(certs)
                                = parent.get(&child_cert.fingerprint())
                            {
                                if let Ok(child_cert) = Cert::try_from(child_cert) {
                                    let mut parent: Option<Cert> = None;
                                    for c in certs.into_iter() {
                                        let c = if let Ok(c) = Cert::try_from(c) {
                                            c
                                        } else {
                                            continue;
                                        };
                                        if let Some(parent) = parent.as_mut() {
                                            if let Ok(merged) =
                                                parent.clone().merge_public(c)
                                            {
                                                *parent = merged;
                                            }
                                        } else {
                                            parent = Some(c);
                                        }
                                    }

                                    let parent = if let Some(parent) = parent {
                                        parent
                                    } else {
                                        continue;
                                    };

                                    // Merge in the child.
                                    if let Ok(merged) = merge(parent, child_cert) {
                                        matches.insert(
                                            merged.fingerprint(), merged);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        Ok(matches.into_values().collect())
    }
    fn check(&mut self, structure: MessageStructure) -> openpgp::Result<()> {
        tracer!(TRACE, "VerificationHelper::get_certs");
        if false {
            t!("check({:?})", structure);
        }

        for (i, layer) in structure.into_iter().enumerate() {
            match layer {
                MessageLayer::SignatureGroup { results } if i == 0 => {
                    for r in results {
                        self.handle_result(r);
                    }
                },
                _ => return Err(Error::BadSignature(
                    "Unexpected signature structure".into()).into()),
            }
        }
        Ok(())
    }
}

#[derive(Default, Clone, Deserialize, Serialize, PartialEq, Eq)]
pub struct Authorization {
    #[serde(default, skip_serializing_if = "bool_is_false")]
    pub sign_commit: bool,
    #[serde(default, skip_serializing_if = "bool_is_false")]
    pub sign_tag: bool,
    #[serde(default, skip_serializing_if = "bool_is_false")]
    pub sign_archive: bool,
    #[serde(default, skip_serializing_if = "bool_is_false")]
    pub add_user: bool,
    #[serde(default, skip_serializing_if = "bool_is_false")]
    pub retire_user: bool,
    #[serde(default, skip_serializing_if = "bool_is_false")]
    pub audit: bool,
    pub keyring: String,
}

fn bool_is_false(b: &bool) -> bool {
    *b == false
}

impl Authorization {
    pub fn rights(&self) -> Rights {
        use Right::*;

        let mut r = BTreeSet::default();

        if self.sign_commit {
            r.insert(SignCommit);
        }
        if self.sign_tag {
            r.insert(SignTag);
        }
        if self.sign_archive {
            r.insert(SignArchive);
        }
        if self.add_user {
            r.insert(AddUser);
        }
        if self.retire_user {
            r.insert(RetireUser);
        }
        if self.audit {
            r.insert(Audit);
        }

        Rights(r)
    }

    pub fn certs(&self) -> Result<impl Iterator<Item = openpgp::Result<RawCert>>> {
        Ok(RawCertParser::from_bytes(self.keyring.as_bytes())?)
    }

    pub fn set_certs(&mut self, certs: Vec<openpgp::Cert>) -> Result<()> {
        self.set_certs_filter(certs, |_| true, |_| true)
    }

    pub fn set_certs_filter<S, U>(&mut self, certs: Vec<openpgp::Cert>,
                                  mut subkeys: S,
                                  mut userids: U)
                                  -> Result<()>
    where
        S: FnMut(&SubordinateKeyAmalgamation<PublicParts>) -> bool,
        U: FnMut(&UserIDAmalgamation) -> bool,
    {
        let mut keyring = Vec::new();

        for c in certs {
            let c = prune_cert(c, &mut subkeys, &mut userids)?;
            c.armored().export(&mut keyring)?;
        }

        self.keyring = String::from_utf8(keyring)
            .map_err(|e| Error::StorageError(e.to_string()))?;
        Ok(())
    }

    /// Computes the difference between this authorization and `other`
    /// recording the changes in `changes`.
    fn diff(&self, other: &Authorization, name: String,
            changes: &mut Vec<Change>)
    {
        let (from, to) = (self, other);

        // First, see if rights were removed.
        if from.sign_commit && ! to.sign_commit {
            changes.push(Change::RemoveRight(name.clone(), Right::SignCommit));
        }
        if from.sign_tag && ! to.sign_tag {
            changes.push(Change::RemoveRight(name.clone(), Right::SignTag));
        }
        if from.sign_archive && ! to.sign_archive {
            changes.push(Change::RemoveRight(name.clone(), Right::SignArchive));
        }
        if from.add_user && ! to.add_user {
            changes.push(Change::RemoveRight(name.clone(), Right::AddUser));
        }
        if from.retire_user && ! to.retire_user {
            changes.push(Change::RemoveRight(name.clone(), Right::RetireUser));
        }
        if from.audit && ! to.audit {
            changes.push(Change::RemoveRight(name.clone(), Right::Audit));
        }

        // Then, see if rights were added.
        if ! from.sign_commit && to.sign_commit {
            changes.push(Change::AddRight(name.clone(), Right::SignCommit));
        }
        if ! from.sign_tag && to.sign_tag {
            changes.push(Change::AddRight(name.clone(), Right::SignTag));
        }
        if ! from.sign_archive && to.sign_archive {
            changes.push(Change::AddRight(name.clone(), Right::SignArchive));
        }
        if ! from.add_user && to.add_user {
            changes.push(Change::AddRight(name.clone(), Right::AddUser));
        }
        if ! from.retire_user && to.retire_user {
            changes.push(Change::AddRight(name.clone(), Right::RetireUser));
        }
        if ! from.audit && to.audit {
            changes.push(Change::AddRight(name.clone(), Right::Audit));
        }

        // Check for changes to the certificates.
        if self.keyring != other.keyring {
            // Parse the keyring.
            //
            // XXX: We silently ignore certificates that we are unable
            // to parse.  We should perhaps reject any changes that we
            // don't understand.
            fn parse_keyring<'a>(name: &str, keyring: &'a str)
                -> BTreeMap<Fingerprint, Vec<RawCert<'a>>>
            {
                match RawCertParser::from_bytes(keyring) {
                    Err(err) => {
                        eprintln!("Parsing {}'s keyring: {}", name, err);
                        Default::default()
                    }
                    Ok(certs) => {
                        let certs = certs.into_iter()
                            .filter_map(|cert| {
                                match cert {
                                    Err(err) => {
                                        eprintln!("Parsing certificate from {}'s keyring: {}",
                                                  name, err);
                                        None
                                    }
                                    Ok(cert) => Some(cert),
                                }
                            });

                        let mut map: BTreeMap<Fingerprint, Vec<RawCert>> = BTreeMap::new();
                        for cert in certs {
                            let entry = map.entry(cert.fingerprint());
                            match entry {
                                Entry::Occupied(mut oe) => {
                                    let oe: &mut Vec<RawCert> = oe.get_mut();
                                    oe.push(cert);
                                }
                                Entry::Vacant(ve) => {
                                    ve.insert(vec![ cert ]);
                                }
                            }
                        }

                        map
                    }
                }
            }

            let old = parse_keyring(&name, &self.keyring);
            let new = parse_keyring(&name, &other.keyring);

            // Identify certificates have been added or removed.
            let old_certs: BTreeSet<&Fingerprint> = old.keys().collect();
            let new_certs: BTreeSet<&Fingerprint> = new.keys().collect();

            for &removed in old_certs.difference(&new_certs) {
                changes.push(Change::RemoveCert(name.clone(), removed.clone()));
            }
            for &added in new_certs.difference(&old_certs) {
                changes.push(Change::AddCert(name.clone(), added.clone()));
            }

            // For certificates that the two keyrings have in common,
            // identify the packets that have been added or removed.
            for &fpr in old_certs.intersection(&new_certs) {
                let old = old.get(fpr).expect("have it");
                let new = new.get(fpr).expect("have it");

                if old == new {
                    continue;
                }

                // Convert each signature into a tuple consisting of a
                // signature and its associated component.
                let into_packets = |certs: Vec<RawCert>| -> HashSet<(Packet, Signature)> {
                    let mut pairs: HashSet<(Packet, Signature)> = HashSet::new();

                    for cert in certs.into_iter() {
                        let mut packets = cert.packets();
                        let primary_key
                            = packets.next().expect("have a primary key");
                        let primary_key = match Packet::try_from(primary_key) {
                            Ok(p) => p,
                            Err(err) => {
                                eprintln!(
                                    "Warning: {} has a corrupted primary key \
                                     packet (skipped): {}",
                                    cert.fingerprint(), err);
                                continue;
                            }
                        };

                        packets.fold(
                            primary_key,
                            |component, packet| {
                                let packet = match Packet::try_from(packet) {
                                    Ok(p) => p,
                                    Err(err) => {
                                        eprintln!(
                                            "Warning: {} has a corrupted packet \
                                             (skipped): {}",
                                            cert.fingerprint(), err);
                                        return component;
                                    }
                                };

                                match packet {
                                    Packet::Signature(sig) => {
                                        pairs.insert(
                                            (component.clone(), sig.clone()));
                                        component
                                    }
                                    Packet::Marker(_) => {
                                        // Silently skip marker packets.
                                        component
                                    }
                                    _ => {
                                        // New component.
                                        packet.clone()
                                    }
                                }
                            });
                    }

                    pairs
                };

                let old_packets = into_packets(old.clone());
                let new_packets = into_packets(new.clone());

                for (component, sig) in old_packets.difference(&new_packets) {
                    changes.push(Change::RemovePacket(name.clone(),
                                                      fpr.clone(),
                                                      component.clone(),
                                                      sig.clone()));
                }
                for (component, sig) in new_packets.difference(&old_packets) {
                    changes.push(Change::AddPacket(name.clone(),
                                                   fpr.clone(),
                                                   component.clone(),
                                                   sig.clone()));
                }
            }
        }
    }
}

// The version of the commit output.  This follows semantic
// versioning.
static DIFF_JSON_VERSION: &'static str = "1.0.0";

/// The difference between two [`Policy`]s.
#[derive(Serialize)]
pub struct Diff<'f, 't> {
    version: &'static str,

    pub from: &'f Policy,
    pub changes: Vec<Change>,
    pub to: &'t Policy,
}

impl Diff<'_, '_> {
    fn assert(&self, r: &Rights) -> Result<()> {
        for c in &self.changes {
            c.assert(r)?;
        }
        Ok(())
    }
}

use crate::utils::{serialize_fp, serialize_oid};

#[derive(Clone, Serialize)]
pub enum Change {
    VersionChange {
        from: usize,
        to: usize,
    },
    GoodlistCommit(
        #[serde(serialize_with = "serialize_oid")] Oid),
    UngoodlistCommit(
        #[serde(serialize_with = "serialize_oid")] Oid),

    AddUser(String),
    RetireUser(String),

    AddRight(String, Right),
    RemoveRight(String, Right),

    AddCert(String,
            #[serde(serialize_with = "serialize_fp")] Fingerprint),
    RemoveCert(String,
               #[serde(serialize_with = "serialize_fp")] Fingerprint),

    AddPacket(String,
              // The certificate.
              #[serde(serialize_with = "serialize_fp")] Fingerprint,
              // The component that the packet is associated with.
              #[serde(serialize_with = "serialize_packet")] Packet,
              // The signature that was added.
              #[serde(serialize_with = "serialize_signature")] Signature),
    RemovePacket(String,
                 // The certificate.
                 #[serde(serialize_with = "serialize_fp")] Fingerprint,
                 // The component that the packet is associated with.
                 #[serde(serialize_with = "serialize_packet")] Packet,
                 // The signature that was removed.
                 #[serde(serialize_with = "serialize_signature")] Signature),
}

impl Change {
    fn assert(&self, r: &Rights) -> Result<()> {
        use Change::*;
        match self {
            VersionChange { .. } => r.assert(Right::Audit),
            GoodlistCommit(_) => r.assert(Right::Audit),
            UngoodlistCommit(_) => r.assert(Right::Audit),

            // Rights management.
            AddUser(_) => r.assert(Right::AddUser),
            RetireUser(_) => r.assert(Right::RetireUser),
            AddRight(_, right) =>
                r.assert(Right::AddUser).and_then(|_| r.assert(*right)),
            RemoveRight(_, right) =>
                r.assert(Right::RetireUser).and_then(|_| r.assert(*right)),

            // Cert management.
            AddCert(_, _) => r.assert(Right::AddUser),
            RemoveCert(_, _) => r.assert(Right::RetireUser),

            // Lenient cert updates.
            AddPacket(_, _, _, _) => Ok(()),

            // Strict cert trimmings.
            RemovePacket(_, fpr, _component, sig) => {
                if sig.get_issuers().into_iter()
                    .any(|kh| kh.aliases(KeyHandle::from(fpr)))
                {
                    // First party signatures can only be removed by
                    // authorized users.
                    r.assert(Right::RetireUser)
                } else {
                    Ok(())
                }
            }
        }
    }
}

#[derive(Debug)]
pub struct Rights(BTreeSet<Right>);

impl Rights {
    fn assert(&self, r: Right) -> Result<()> {
        if ! self.0.contains(&r) {
            Err(Error::Unauthorized(format!("Right {} is missing", r)))
        } else {
            Ok(())
        }
    }
}

#[derive(Debug, Clone, Copy, Serialize, PartialEq, Eq, PartialOrd, Ord)]
pub enum Right {
    SignCommit,
    SignTag,
    SignArchive,
    AddUser,
    RetireUser,
    Audit,
}

impl fmt::Display for Right {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        use Right::*;
        match self {
            SignCommit => f.write_str("sign-commit"),
            SignTag => f.write_str("sign-tag"),
            SignArchive => f.write_str("sign-archive"),
            AddUser => f.write_str("add-user"),
            RetireUser => f.write_str("retire-user"),
            Audit => f.write_str("audit"),
        }
    }
}