sequoia-wot 0.15.0

use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::collections::btree_map::Entry;
use std::fmt;
use std::sync::Arc;

use sequoia_openpgp as openpgp;

use openpgp::Fingerprint;
use openpgp::packet::prelude::*;

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

use crate::Certification;
use crate::CertificationSet;
use crate::FULLY_TRUSTED;
use crate::Network;
use crate::network::filter::CertificationFilter;
use crate::Path;
use crate::PriorityQueue;
use crate::store::Store;

use super::TRACE;

// A path's cost.
//
// This is needed to do a Dijkstra.
#[derive(Debug, Eq, Clone)]
struct Cost {
    // The path's depth (i.e., the number of hops to the target).
    // *Less* is better.
    depth: usize,

    // The trust amount along this path.  More is better.
    amount: usize,
}

impl Ord for Cost {
    fn cmp(&self, other: &Self) -> Ordering {
        self.depth.cmp(&other.depth).reverse()
            .then(self.amount.cmp(&self.amount))
    }
}

impl PartialOrd for Cost {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for Cost {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

// We perform a Dijkstra in reverse from the target towards the roots.
#[derive(Clone)]
struct ForwardPointer {
    // If None, then the target.
    next: Option<Certification>,
}

impl fmt::Debug for ForwardPointer {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut x = f.debug_struct("ForwardPointer");
        let x = if let Some(ref c) = self.next {
            x.field("next", &format!("{}", c.target()))
        } else {
            x.field("next", &"target")
        };
        x.finish()
    }
}

impl<S> Network<S>
    where S: Store
{
    /// Performs backward propagation from a binding towards all other
    /// nodes.
    ///
    /// If there is a path in the network from a node to the target,
    /// this algorithm will find it.  However, because it prefers
    /// shorter paths to longer paths, the path may not be optimal in
    /// terms of the amount of trust.
    ///
    /// # Return Value
    ///
    /// This function returns a hash from certificate fingerprints to
    /// paths to the target.
    ///
    /// If `roots` is specified, then only the best path from each
    /// root to the target is returned.  If `roots` is empty, then the
    /// best path from each certificates to the target is returned.
    ///
    /// # Algorithm
    ///
    /// This algorithm reverses the edges in the network and then
    /// executes a variant of [Dijkstra's shortest path algorithm].
    /// The algorithm sets the initial node to be the target and works
    /// outwards.  Consider the following network:
    ///
    /// ```text
    ///          .--> C ... v
    /// ... --> A           target
    ///          `--> D ... ^
    /// ```
    ///
    /// When visiting a certificate (say, `C`), the algorithm
    /// considers each certification on it (`A -> C`).  If prepending
    /// to the current path suffix (`C ... target`) results in a valid
    /// path suffix (`A - C ... target`), and the path suffix is
    /// better than the issuer's current path suffix (say `A - D
    /// ... target'), we update the issuer's forward pointer to use
    /// the new path suffix.
    ///
    ///   [Dijkstra's shortest path algorithm]: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
    ///
    /// A certification is valid if it has any regular expressions and
    /// they match the target User ID.  Further, the certification's
    /// depth must be sufficient for the current path suffix.  If a
    /// certification certifies the target, then it must certify the
    /// target User ID.
    ///
    /// When comparing two forward pointers, the one with the shorter
    /// path is preferred.  If the two forward pointers have the same
    /// trust amount, then the one with the larger trust amount is
    /// preferred.
    ///
    /// # Examples
    ///
    /// Consider the following network:
    ///
    /// ```text
    ///                          120/255
    ///                        C         D
    ///                      _ o ------> o
    ///             120/255  /|            \  120/0
    ///                     /              _\|
    ///  o --------------> o --------------> o
    ///  A     100/2       B      30/0       E
    /// ```
    ///
    /// The tuples stand for the trust amount and the trust depth
    /// parameters.  So 120/255 means the trust amount is 120 and the
    /// trust depth is 255.  (In this case, both are maximal.)
    ///
    /// Let us assume that we want to authenticate E, and A is our only
    /// trust root.  Using backward propagation, we start at the
    /// target, E, and consider each certification made on E: D-E and
    /// B-E.
    ///
    /// Say we start with D-E (the order doesn't matter).  Since D
    /// doesn't yet have a forward pointer, we set its forward pointer
    /// to E and add D to the queue.  Then we consider B-E.  Since B
    /// doesn't yet have a forward pointer, we set its forward pointer
    /// to E, and we add B to the queue.
    ///
    /// ```text
    /// queue = [ D, B ];
    /// forward_pointers = [ (B -> E), (D -> E) ];
    /// ```
    ///
    /// Next we pop the certificate with the best path suffix from the
    /// queue.  Because B and D's provisional paths are the same
    /// length (1), we compare the amount of trust along each path.
    /// D's amount of trust is 120 whereas B's is only 30.  So, we pop
    /// D.
    ///
    /// D is only certified by C.  Looking at C, we see that it
    /// doesn't yet have a forward pointer so we set its forward
    /// pointer to D, and we add C to the queue.
    ///
    /// ```text
    /// queue = [ B, C ];
    /// forward_pointers = [ (B -> E), (C -> D), (D -> E) ];
    /// ```
    ///
    /// The queue now contains B and C.  We prefer B, because its path
    /// is shorter (1 vs 2).
    ///
    /// B is certified by A.  Since A's forward pointer is empty, we
    /// set it to point to B and add it to the queue.
    ///
    /// ```text
    /// queue = [ C, A ];
    /// forward_pointers = [ (A -> B), (B -> E), (C-> D), (D -> E) ];
    /// ```
    ///
    /// We now pop C from the queue: the paths starting at A and C
    /// have the same path length, but the trust amount for the
    /// current path starting at C is larger (120 vs 30).
    ///
    /// C is certified by B.  We compare B's current path to the one
    /// via C.
    ///
    ///   B' forward pointer:        length: 1, amount: 30
    ///   B-C + C's forward pointer: length: 3, amount: 120
    ///
    /// We prefer the existing forward pointer because the path is
    /// shorter *even though the amount of trust is smaller*.  If we
    /// had taken the longer path, then any forward pointers pointing
    /// to B might become invalid.  This is, in fact, the case here:
    /// A-B has a trust depth of 2.  But to use B-C-D-E, A-B would
    /// need a trust depth of at least 3!
    ///
    /// Thus, because we never replace an existing forward pointer
    /// with a forward pointer with a longer path, all forward
    /// pointers remain---by construction---valid.
    ///
    /// # Arguments
    ///
    /// If `self_signed` is true, then the target User ID must be self
    /// signed and the target certificate must be a trusted
    /// introducer.  That is, if 0xB has two self-signed User IDs:
    /// `bob@example.org` and `bob@other.org`, and Alice certifies the
    /// first one, then only the first one would be considered
    /// authenticated.  But if Alice considers Bob via her
    /// certification on `bob@example.org` to be a trusted introducer,
    /// then he can certify User IDs on his own certificate, and Alice
    /// considers both of his self-signed User IDs to be
    /// authenticated.
    ///
    /// ```text
    /// A, "Alice"
    ///   |
    ///   | 120/1
    ///   v
    /// B, "bob@example.org"
    ///   |
    ///   | self signature
    ///   v
    /// B, "bob@other.org"
    /// ```
    ///
    /// If `self_signed` is false, then self-signed User IDs are not
    /// considered at all.
    ///
    /// `cf` is a callback which returns the trust depth, and trust
    /// amount to use for the certification and whether any regular
    /// expressions should be respected.  To simply use the values in
    /// the certification return None using the callback: `|_| None`.
    pub(crate) fn backward_propagate(&self,
                                     target_fpr: Fingerprint,
                                     target_userid: UserID,
                                     self_signed: bool,
                                     cf: &dyn CertificationFilter,
                                     gossip: bool)
        -> BTreeMap<Fingerprint, (Path, usize)>
    {
        tracer!(TRACE, "Network::backward_propagate");
        t!("Roots:\n{}",
           self.roots().iter().enumerate().map(|(i, r)| {
               let fpr = r.fingerprint();
               match self.lookup_synopsis_by_fpr(fpr) {
                   Ok(cert) => {
                       format!("  {}. {}", i, cert)
                   }
                   Err(err) => {
                       format!("  {}. {} (error: {})",
                               i, fpr, err)
                   }
               }
           })
           .collect::<Vec<_>>()
           .join("\n"));
        t!("target: {}, {}",
           target_fpr, String::from_utf8_lossy(target_userid.value()));
        t!("self signed: {}", self_signed);

        // If the node is not in the network, we're done.
        let target = match self.lookup_synopsis_by_fpr(&target_fpr) {
            Ok(target) => target,
            Err(err) => {
                t!("Target not in network: {}.", err);
                return BTreeMap::new();
            }
        };

        // Make sure the target is valid (not expired and not revoked
        // at the reference time).
        if let Some(e) = target.expiration_time() {
            if e <= self.reference_time() {
                t!("{}: Target certificate is expired at reference time.",
                   target_fpr);
                return BTreeMap::new();
            }
        }

        if target.revocation_status().in_effect(self.reference_time()) {
            t!("{}: Target certificate is revoked at reference time.",
               target_fpr);
            return BTreeMap::new();
        }

        // Recall: 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.
        let target_ua
            = target.userids().find(|u| u.userid() == &target_userid);
        if let Some(u) = target_ua {
            if u.revocation_status().in_effect(self.reference_time()) {
                t!("{}: Target user id is revoked at reference time.",
                   target_fpr);
                return BTreeMap::new();
            }
        }

        // Dijkstra.

        let mut distance: BTreeMap<Fingerprint, ForwardPointer> = BTreeMap::new();
        let mut queue: PriorityQueue<Fingerprint, Cost>
            = PriorityQueue::new();

        // Compute the "cost" of this path suffix.
        //
        // This is a macro, because lifetimes :/.
        macro_rules! fp_cost {
            ($fp:expr) => ({
                let mut fp: &ForwardPointer = $fp;
                let mut amount = 120;
                let mut depth: usize = if self_signed { 1 } else { 0 };

                while let Some(ref c) = fp.next {
                    let mut a = c.amount();
                    let mut d = c.depth();
                    let r = cf.cost(c, &mut d, &mut a, true, &mut None);
                    assert!(r, "cost function returned different result, \
                                but must be constant!");
                    amount = std::cmp::min(a, amount);
                    depth += 1;
                    fp = distance.get(&c.target().fingerprint()).unwrap();
                }

                Cost {
                    amount: amount as usize,
                    depth: depth.into(),
                }
            });
        }

        if self_signed {
            // If the target is a trusted introducer and has self signed
            // the User ID, then also consider that path.
            if target_ua.is_some() {
                t!("Target User ID is self signed.");

                let cost = Cost { depth: 1, amount: 120 };
                queue.push(target_fpr.clone(), cost);
                distance.insert(
                    target_fpr.clone(),
                    ForwardPointer {
                        next: None,
                    });
            } else {
                t!("Target User ID is not self-signed, but that is required.");
                return BTreeMap::new();
            }
        } else {
            let cost = Cost { depth: 0, amount: 120 };
            queue.push(target_fpr.clone(), cost);
            distance.insert(
                target_fpr.clone(),
                ForwardPointer {
                    next: None,
                });
        }


        // Iterate over each node in the priority queue.
        while let Some((signee_fpr, _)) = queue.pop() {
            if let Some(root) = self.roots().get(&signee_fpr) {
                // XXX: Technically, we could stop if the root's trust
                // amount is at least the required trust amount.
                // Since we don't know it, and the maximum is
                // `FULLY_TRUSTED`, we use that.
                if root.amount() >= FULLY_TRUSTED {
                    t!("Skipping fully trust root: {}.", root.fingerprint());
                    continue;
                }
            }

            let signee = self.lookup_synopsis_by_fpr(&signee_fpr)
                .expect("already looked up");

            // Get the signee's current forward pointer.
            //
            // We need to clone this, because we want to manipulate
            // 'distance' and we can't do that if there is a reference
            // to something in it.
            let signee_fp: ForwardPointer
                = distance.get(&signee_fpr).expect("was queued").clone();
            let signee_fp_cost = fp_cost!(&signee_fp);

            t!("{}'s forward pointer: {}",
               signee_fpr,
               signee_fp.next.as_ref()
                   .map(|c| format!("{}", c.target()))
                   .unwrap_or_else(|| String::from("target")));

            // Get all the certifications over the signee's
            // certificate.
            let required_depth = if self.certification_network() {
                0
            } else {
                signee_fp_cost.depth.into()
            }.into();
            let certification_sets: Arc<Vec<CertificationSet>>
                = match self.certifications_of(&signee_fpr, required_depth)
            {
                Ok(cs) => cs,
                Err(ref err) => {
                    if let Some(StoreError::NotFound(_))
                        = err.downcast_ref()
                    {
                        Arc::new(Vec::new())
                    } else {
                        t!("Reading third party certifications: {}", err);
                        continue;
                    }
                }
            };
            if certification_sets.is_empty() {
                // Nothing certified it.  The path is a dead end.
                t!("{} was not certified, dead end", signee_fpr);
                continue;
            }

            t!("Visiting {} ({}), certified {} times",
               signee.fingerprint(),
               signee.display(),
               certification_sets.len());

            for certification in certification_sets.iter()
                .flat_map(|cs| cs.certifications())
                .flat_map(|(_userid, certifications)| certifications.iter())
            {
                let issuer_fpr = certification.issuer().fingerprint();

                let mut certification_depth = certification.depth();
                let mut certification_amount = certification.amount();
                let mut certification_res
                    = if let Some(re) = certification.regular_expressions() {
                        Some(re.clone())
                    } else {
                        // Invalid, skip.
                        t!("  Skipping certification with invalid REs");
                        continue;
                    };

                if ! cf.cost(&certification, &mut certification_depth,
                             &mut certification_amount,
                             false, &mut certification_res)
                {
                    t!("  Cost function says to skip certification by {}",
                       certification.issuer());
                    continue;
                }

                t!("  Considering certification by: \
                    {}, depth: {} (of {}), amount: {} (of {}), regexes: {:?}",
                   certification.issuer(),
                   certification_depth,
                   certification.depth(),
                   certification_amount,
                   certification.amount(),
                   if let Some(ref certification_res) = certification_res {
                       if certification_res.matches_everything()
                       {
                           "*".into()
                       } else {
                           format!("{:?}", certification_res)
                       }
                   } else {
                       "*".into()
                   });

                if certification_amount == 0 {
                    t!("    Certification amount is 0, skipping");
                    continue;
                }

                if !self_signed
                    && signee_fpr == target_fpr
                    && certification.userid() != Some(&target_userid)
                {
                    assert!(signee_fp.next.is_none());

                    t!("    Certification certifies target, but for the wrong \
                        user id (want: {}, got: {})",
                       String::from_utf8_lossy(target_userid.value()),
                       if let Some(ref userid) = certification.userid() {
                           String::from_utf8_lossy(userid.value())
                       } else {
                           "<delegation>".into()
                       });
                    continue;
                }

                if certification_depth < signee_fp_cost.depth.into() {
                    t!("    Certification does not have enough depth \
                        ({}, needed: {}), skipping",
                       certification_depth, signee_fp_cost.depth);
                    continue;
                }

                // We check that the current certificate's regular
                // expressions match the target user ID UNLESS
                // (`signee_fp.next == None`) 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>
                // ```
                if signee_fp.next.is_some() {
                    if let Some(certification_res) = certification_res {
                        if ! certification_res.matches_userid(&target_userid)
                        {
                            t!("  Certification's re does not match target User ID, \
                                skipping.");
                            continue;
                        }
                    }
                }

                let proposed_fp: ForwardPointer = ForwardPointer {
                    next: Some(certification.clone()),
                };
                let proposed_fp_cost = Cost {
                    depth: signee_fp_cost.depth + 1,
                    amount: std::cmp::min(
                        certification_amount as usize,
                        signee_fp_cost.amount),
                };

                t!("  Forward pointer for {}:", certification.issuer());
                t!("    Proposed: {}, amount: {}, depth: {}",
                   proposed_fp.next.as_ref()
                       .map(|c| format!("{}", c.target()))
                       .unwrap_or_else(|| String::from("target")),
                   proposed_fp_cost.amount,
                   proposed_fp_cost.depth);

                // distance.entry takes a mutable ref, so we can't
                // compute the current fp's cost in the next block.
                let current_fp_cost = if let Some(current_fp)
                    = distance.get(&issuer_fpr.clone())
                {
                    Some(fp_cost!(&current_fp))
                } else {
                    None
                };

                match distance.entry(issuer_fpr.clone()) {
                    Entry::Occupied(mut oe) => {
                        // We've visited this node in the past.  Now
                        // we need to determine whether using
                        // certification and following the proposed
                        // path is better than the current path.

                        let current_fp_cost = current_fp_cost.unwrap();
                        let current_fp = oe.get_mut();

                        t!("    Current: {}, amount: {}, depth: {}",
                           current_fp.next.as_ref()
                               .map(|c| format!("{}", c.target()))
                           .unwrap_or_else(|| String::from("target")),
                           current_fp_cost.amount,
                           current_fp_cost.depth);

                        // We prefer a shorter path (in terms of
                        // edges) as this allows us to reach more of
                        // the graph.
                        //
                        // If the path length is equal, we prefer the
                        // larger amount of trust.

                        if proposed_fp_cost.depth < current_fp_cost.depth {
                            if proposed_fp_cost.amount < current_fp_cost.amount {
                                // We have two local optima: one
                                // has a shorter path, the other a
                                // higher trust amount.  We prefer
                                // the shorter path.
                                t!("    Preferring proposed: \
                                    current has a shorter path ({} < {}), \
                                    but worse amount of trust ({} < {})",
                                   proposed_fp_cost.depth, current_fp_cost.depth,
                                   proposed_fp_cost.amount, current_fp_cost.amount);
                                oe.insert(proposed_fp);
                            } else {
                                // Proposed fp is strictly better.
                                t!("    Preferring proposed: \
                                    current has a shorter path ({} < {}) \
                                    and a better amount of trust ({} < {})",
                                   proposed_fp_cost.depth, current_fp_cost.depth,
                                   proposed_fp_cost.amount, current_fp_cost.amount);
                                oe.insert(proposed_fp);
                            }
                        } else if proposed_fp_cost.depth == current_fp_cost.depth
                            && proposed_fp_cost.amount > current_fp_cost.amount
                        {
                            // Strictly better.
                            t!("    Preferring proposed fp: \
                                same path length ({}), better amount ({} > {})",
                               proposed_fp_cost.depth,
                               proposed_fp_cost.amount, current_fp_cost.amount);
                            oe.insert(proposed_fp);
                        } else if proposed_fp_cost.depth > current_fp_cost.depth
                            && proposed_fp_cost.amount > current_fp_cost.amount
                        {
                            // There's another possible path through here.
                            t!("    Preferring current fp: \
                                proposed has more trust ({} > {}), but a longer path ({} > {})",
                               proposed_fp_cost.amount, current_fp_cost.amount,
                               proposed_fp_cost.depth, current_fp_cost.depth);
                        } else {
                            t!("    Preferring current fp: \
                                it is strictly better \
                                (depth: {}, {}; amount: {}, {})",
                               proposed_fp_cost.depth, current_fp_cost.depth,
                               proposed_fp_cost.amount, current_fp_cost.amount);
                        }
                    }
                    e @ Entry::Vacant(_) => {
                        // We haven't seen this node before.
                        t!("    Current: None");
                        t!("  Setting {}'s forward pointer to {}",
                           certification.issuer(), signee);
                        t!("  Queuing {}", certification.issuer());
                        queue.push(issuer_fpr, proposed_fp_cost);
                        e.or_insert(proposed_fp);
                    }
                }
            }
        }


        // Follow the forward pointers and reconstruct the paths.
        let mut auth_rpaths: BTreeMap<Fingerprint, (Path, usize)>
            = BTreeMap::new();

        for (issuer_fpr, mut fp) in distance.iter() {
            // If we're looking for gossip, or no roots were
            // specified, then return all paths.  Otherwise, only
            // return paths from the roots.
            if ! (gossip || self.roots().is_empty()) {
                if ! self.roots().is_root(issuer_fpr) {
                    continue;
                }
            }

            let issuer = if let Some(ref c) = fp.next {
                c.issuer()
            } else {
                // The target.
                if ! self_signed {
                    continue;
                }

                // Apply any policy to the self certification.
                //
                // XXX: Self-signatures should be first class and not
                // synthesized like this on the fly.
                let selfsig = Certification::new(
                    target.clone(),
                    Some(target_userid.clone()),
                    target.clone(),
                    target_ua.map(|ua| ua.binding_signature_creation_time())
                        .unwrap_or(self.reference_time()));

                let mut a = 120;
                let mut d = 0.into();
                if cf.cost(&selfsig, &mut d, &mut a, true, &mut None) {
                    t!("Policy on selfsig => amount: {}", a);
                    if a == 0 {
                        continue;
                    }
                } else {
                    t!("Policy says to ignore selfsig");
                    continue;
                }

                let p = Path::new(target.clone());

                t!("Authenticated <{}, {}>: {:?}",
                   target_fpr, target_userid, p);

                auth_rpaths.insert(issuer_fpr.clone(), (p, a));
                continue;
            };

            t!("Recovering path starting at {}",
               self.lookup_synopsis_by_fpr(issuer_fpr)
                   .expect("already looked up"));

            let mut amount = 120;

            // nodes[0] is the root; nodes[nodes.len() - 1] is the target.
            let mut nodes: Vec<Certification> = Vec::new();
            while let Some(ref c) = fp.next {
                t!("  {:?}", fp);
                let mut d = c.depth();
                let mut a = c.amount();
                let r = cf.cost(c, &mut d, &mut a, true, &mut None);
                assert!(r, "cost function returned different result, \
                            but must be constant!");
                amount = std::cmp::min(a, amount);

                nodes.push(c.clone());
                fp = distance.get(&c.target().fingerprint()).expect("exists");
            }
            if self_signed {
                let tail = nodes.last().unwrap();
                if tail.userid() != Some(&target_userid) {
                    let selfsig = Certification::new(
                        target.clone(),
                        Some(target_userid.clone()),
                        target.clone(),
                        std::time::SystemTime::now());
                    nodes.push(selfsig);
                }
            }

            t!("  {:?}", fp);

            t!("\nShortest path from {}:\n  {}\n  Target: <{}, {}>",
               issuer,
               nodes.iter()
                   .enumerate()
                   .map(|(i, n)| {
                       format!("{}: {} ({}, {})",
                               i, n.issuer(), n.amount(), n.depth())
                   })
                  .collect::<Vec<_>>()
                  .join("\n  "),
               target_fpr,
               target_userid);

            assert!(nodes.len() > 0);

            let mut p = Path::new(issuer.clone());
            for n in nodes.iter() {
                p.append(n.clone()).expect("valid path");
            }

            t!("Authenticated <{}, {}>: {:?}",
               target_fpr, target_userid, p);

            auth_rpaths.insert(issuer_fpr.clone(), (p, amount as usize));
        }

        if TRACE {
            t!("auth_rpaths:");
            let mut v: Vec<_> = auth_rpaths.iter().collect();
            v.sort_by(|(fpr_a, _), (fpr_b, _)| {
                let userid_a = self
                    .lookup_synopsis_by_fpr(*fpr_a).expect("already looked up")
                    .primary_userid().map(|userid| {
                        String::from_utf8_lossy(userid.value()).into_owned()
                    }).unwrap_or("".into());
                let userid_b = self
                    .lookup_synopsis_by_fpr(*fpr_b).expect("already looked up")
                    .primary_userid().map(|userid| {
                        String::from_utf8_lossy(userid.value()).into_owned()
                    }).unwrap_or("".into());

                userid_a.cmp(&userid_b).
                    then(fpr_a.cmp(&fpr_b))
            });
            for (fpr, (path, amount)) in v {
                let userid = self
                    .lookup_synopsis_by_fpr(fpr).expect("already looked up")
                    .primary_userid().map(|userid| {
                        String::from_utf8_lossy(userid.value()).into_owned()
                    })
                    .unwrap_or("<missing User ID>".into());
                t!("  <{}, {}>: {}",
                   fpr, userid,
                   format!("{} trust amount (max: {}), {} edges",
                           amount, path.amount(),
                           path.len() - 1));
            }
        }

        auth_rpaths
    }
}

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

    use openpgp::KeyHandle;
    use openpgp::Result;
    use openpgp::cert::prelude::*;
    use openpgp::parse::Parse;
    use openpgp::policy::StandardPolicy;

    use crate::Depth;
    use crate::Network;
    use crate::NetworkBuilder;
    use crate::network::filter::IdempotentCertificationFilter;
    use crate::store::Backend;
    use crate::store::CertStore;

    // Compares a computed path and a trust amount with the expected
    // result.
    fn pcmp<'a, S, D>(q: &Network<S>,
                      result: &(Path, usize),
                      residual_depth: D, amount: usize,
                      expected_path: &[ &Fingerprint ])
    where D: Into<Depth>,
          S: Store + Backend<'a>,
    {
        let residual_depth = residual_depth.into();

        let (got_path, got_amount) = result;
        let got_certs: Vec<Fingerprint>
            = got_path.certificates().map(|c| c.fingerprint()).collect();

        if got_certs.len() != expected_path.len()
            || got_certs.iter().zip(expected_path.iter()).any(|(a, b)| &a != b)
        {
            panic!("Paths don't match.  {}Got path:\n {:?}, expected:\n {}",
                   if got_certs.len() != expected_path.len() {
                       format!("Got {} certs, expected {}.  ",
                               got_certs.len(), expected_path.len())
                   } else {
                       "".into()
                   },
                   got_path,
                   expected_path.iter().enumerate()
                       .map(|(i, f)| format!("  {}. {}", i, f))
                       .collect::<Vec<String>>()
                       .join("\n "));
        }

        assert_eq!(*got_amount, amount, "amount");
        assert_eq!(got_path.residual_depth(), residual_depth, "residual amount");

        // Make sure Network::path agrees that the path is good.
        if let Some(userid) = got_path
            .certifications()
            .last().expect("got one")
            .userid()
        {
            if let Err(err) = q.path(
                &got_certs
                    .iter()
                    .map(|fpr| KeyHandle::from(fpr))
                    .collect::<Vec<_>>()[..],
                userid.clone(),
                amount,
                // XXX: This assumes that all tests use this policy.
                &StandardPolicy::new())
            {
                panic!("Failed to validate expected path: {}.", err);
            }
        }
    }

    #[test]
    #[allow(unused)]
    fn simple() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "39A479816C934B9E0464F1F4BC1DCFDEADA4EE90"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D

        let carol_fpr: Fingerprint =
            "43530F91B450EDB269AA58821A1CF4DC7F500F04"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 39A479816C934B9E0464F1F4BC1DCFDEADA4EE90

        let dave_fpr: Fingerprint =
            "329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 43530F91B450EDB269AA58821A1CF4DC7F500F04

        let ellen_fpr: Fingerprint =
            "A7319A9B166AB530A5FBAC8AB43CA77F7C176AF4"
           .parse().expect("valid fingerprint");
        let ellen_uid
            = UserID::from("<ellen@example.org>");
        // Certified by: 329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281

        let frank_fpr: Fingerprint =
            "2693237D2CED0BB68F118D78DC86A97CD2C819D9"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("simple.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        let auth = n.backward_propagate(ellen_fpr.clone(),
                                        ellen_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             1, 100,
             &[ &dave_fpr, &ellen_fpr ]);
        pcmp(&n, auth.get(&carol_fpr).unwrap(),
             0, 100,
             &[ &carol_fpr, &dave_fpr, &ellen_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        assert!(&auth.get(&ellen_fpr).is_none());
        pcmp(&n, &auth.get(&carol_fpr).unwrap(),
             1, 100,
             &[ &carol_fpr, &dave_fpr ]);
        pcmp(&n, &auth.get(&bob_fpr).unwrap(),
             0, 100,
             &[ &bob_fpr, &carol_fpr, &dave_fpr ]);
        pcmp(&n, &auth.get(&alice_fpr).unwrap(),
             0, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        assert!(&auth.get(&ellen_fpr).is_none());
        pcmp(&n, &auth.get(&carol_fpr).unwrap(),
             1, 100,
             &[ &carol_fpr, &dave_fpr ]);
        pcmp(&n, &auth.get(&bob_fpr).unwrap(),
             0, 100,
             &[ &bob_fpr, &carol_fpr, &dave_fpr ]);

        // This should work even though Bob is the root and the path
        // is via Bob.
        pcmp(&n, &auth.get(&alice_fpr).unwrap(),
             0, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        assert!(&auth.get(&ellen_fpr).is_none());
        pcmp(&n, &auth.get(&carol_fpr).unwrap(),
             1, 100,
             &[ &carol_fpr, &dave_fpr ]);

        // This should work even though Carol is the root is the path
        // is via Carol.
        pcmp(&n, &auth.get(&bob_fpr).unwrap(),
             0, 100,
             &[ &bob_fpr, &carol_fpr, &dave_fpr ]);
        pcmp(&n, &auth.get(&alice_fpr).unwrap(),
             0, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ]);


        // Try to authenticate dave's key for an User ID that no one
        // has certified.
        let auth = n.backward_propagate(dave_fpr.clone(),
                                        ellen_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        assert!(&auth.get(&ellen_fpr).is_none());
        assert!(&auth.get(&dave_fpr).is_none());
        assert!(&auth.get(&carol_fpr).is_none());
        assert!(&auth.get(&bob_fpr).is_none());
        assert!(&auth.get(&alice_fpr).is_none());

        // Target is not in the network.
        let fpr: Fingerprint
            = "0123 4567 89AB CDEF  0123 4567 89AB CDEF".parse().expect("valid");
        let auth = n.backward_propagate(fpr.clone(),
                                        ellen_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        assert!(&auth.get(&ellen_fpr).is_none());
        assert!(&auth.get(&dave_fpr).is_none());
        assert!(&auth.get(&carol_fpr).is_none());
        assert!(&auth.get(&bob_fpr).is_none());
        assert!(&auth.get(&alice_fpr).is_none());

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn cycle() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "BFC5CA10FB55A4B790E2A1DBA5CFAB9A9E34E183"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "A637747DCF876A7F6C9149F74D47846E24A20C0B"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 4458062DC7388909CF760E6823150D8E4408638A
        // Certified by: BFC5CA10FB55A4B790E2A1DBA5CFAB9A9E34E183

        let carol_fpr: Fingerprint =
            "394B04774FDAB0CDBF4D6FFD7930EA0FB549E303"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: A637747DCF876A7F6C9149F74D47846E24A20C0B

        let dave_fpr: Fingerprint =
            "4458062DC7388909CF760E6823150D8E4408638A"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 394B04774FDAB0CDBF4D6FFD7930EA0FB549E303

        let ed_fpr: Fingerprint =
            "78C3814EFD16E68F4F1AB4B874E30AE11FFCFB1B"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 4458062DC7388909CF760E6823150D8E4408638A

        let frank_fpr: Fingerprint =
            "A6219FF753AEAE2DE8A74E8487977DD568A08237"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");
        // Certified by: 78C3814EFD16E68F4F1AB4B874E30AE11FFCFB1B


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cycle.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, &auth.get(&ed_fpr).unwrap(),
             0, 120,
             &[ &ed_fpr, &frank_fpr ]);
        pcmp(&n, &auth.get(&dave_fpr).unwrap(),
             0, 30,
             &[ &dave_fpr, &ed_fpr, &frank_fpr ]);
        pcmp(&n, &auth.get(&carol_fpr).unwrap(),
             0, 30,
             &[ &carol_fpr, &dave_fpr, &ed_fpr, &frank_fpr ]);
        pcmp(&n, &auth.get(&bob_fpr).unwrap(),
             0, 30,
             &[ &bob_fpr, &carol_fpr, &dave_fpr, &ed_fpr, &frank_fpr ]);
        assert!(&auth.get(&alice_fpr).is_none());


        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, &auth.get(&ed_fpr).unwrap(),
             0, 120,
             &[ &ed_fpr, &frank_fpr ]);
        pcmp(&n, &auth.get(&dave_fpr).unwrap(),
             0, 30,
             &[ &dave_fpr, &ed_fpr, &frank_fpr ]);
        pcmp(&n, &auth.get(&carol_fpr).unwrap(),
             0, 30,
             &[ &carol_fpr, &dave_fpr, &ed_fpr, &frank_fpr ]);
        pcmp(&n, &auth.get(&bob_fpr).unwrap(),
             0, 30,
             &[ &bob_fpr, &carol_fpr, &dave_fpr, &ed_fpr, &frank_fpr ]);
        assert!(&auth.get(&alice_fpr).is_none());

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        assert!(&auth.get(&frank_fpr).is_none());
        pcmp(&n, &auth.get(&dave_fpr).unwrap(),
             1, 30,
             &[ &dave_fpr, &ed_fpr ]);
        pcmp(&n, &auth.get(&carol_fpr).unwrap(),
             1, 30,
             &[ &carol_fpr, &dave_fpr, &ed_fpr ]);
        pcmp(&n, &auth.get(&bob_fpr).unwrap(),
             1, 30,
             &[ &bob_fpr, &carol_fpr, &dave_fpr, &ed_fpr ]);
        pcmp(&n, &auth.get(&alice_fpr).unwrap(),
             0, 30,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr, &ed_fpr ]);

        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        assert!(&auth.get(&frank_fpr).is_none());
        assert!(&auth.get(&ed_fpr).is_none());
        pcmp(&n, &auth.get(&dave_fpr).unwrap(),
             Depth::unconstrained(), 90,
             &[ &dave_fpr, &bob_fpr, &carol_fpr ]);
        pcmp(&n, &auth.get(&bob_fpr).unwrap(),
             Depth::unconstrained(), 90,
             &[ &bob_fpr, &carol_fpr ]);
        // The backward propagation algorithm doesn't know that alice
        // is not reachable from the root (dave).
        pcmp(&n, &auth.get(&alice_fpr).unwrap(),
             2, 90,
             &[ &alice_fpr, &bob_fpr, &carol_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn cliques() -> Result<()> {
        let p = &StandardPolicy::new();

        let root_fpr: Fingerprint =
            "D2B0 C383 5C01 B0C1 20BC  540D A4AA 8F88 0BA5 12B5"
           .parse().expect("valid fingerprint");
        let root_uid
            = UserID::from("<root@example.org>");

        let a_0_fpr: Fingerprint =
            "3630 82E9 EEB2 2E50 AD30  3D8B 1BFE 9BA3 F4AB D40E"
           .parse().expect("valid fingerprint");
        let a_0_uid
            = UserID::from("<a-0@example.org>");

        let a_1_fpr: Fingerprint =
            "7974 C04E 8D5B 540D 23CD  4E62 DDFA 779D 91C6 9894"
           .parse().expect("valid fingerprint");
        let a_1_uid
            = UserID::from("<a-1@example.org>");

        let b_0_fpr: Fingerprint =
            "25D8 EAAB 8947 05BB 64D4  A6A8 9649 EF81 AEFE 5162"
           .parse().expect("valid fingerprint");
        let b_0_uid
            = UserID::from("<b-0@example.org>");

        let b_1_fpr: Fingerprint =
            "46D2 F5CE D9BD 3D63 A11D  DFEE 1BA0 1950 6BE6 7FBB"
           .parse().expect("valid fingerprint");
        let b_1_uid
            = UserID::from("<b-1@example.org>");

        let c_0_fpr: Fingerprint =
            "A0CD 8758 2C21 743C 0E30  637F 7FAD B1C3 FEFB FE59"
           .parse().expect("valid fingerprint");
        let c_0_uid
            = UserID::from("<c-0@example.org>");

        let c_1_fpr: Fingerprint =
            "5277 C14F 9D37 A0F4 D615  DD9C CDCC 1AC8 464C 8FE5"
           .parse().expect("valid fingerprint");
        let c_1_uid
            = UserID::from("<c-1@example.org>");

        let d_0_fpr: Fingerprint =
            "C24C C091 02D2 2E38 E839  3C55 1669 8256 1E14 0C03"
           .parse().expect("valid fingerprint");
        let d_0_uid
            = UserID::from("<d-0@example.org>");

        let d_1_fpr: Fingerprint =
            "7A80 DB53 30B7 D900 D5BD  1F82 EAD7 2FF7 9140 78B2"
           .parse().expect("valid fingerprint");
        let d_1_uid
            = UserID::from("<d-1@example.org>");

        let e_0_fpr: Fingerprint =
            "D1E9 F85C EF62 7169 9FBD  E5AB 26EF E0E0 35AC 522E"
           .parse().expect("valid fingerprint");
        let e_0_uid
            = UserID::from("<e-0@example.org>");

        let f_0_fpr: Fingerprint =
            "C0FF AEDE F092 8B18 1265  775A 222B 480E B43E 0AFF"
           .parse().expect("valid fingerprint");
        let f_0_uid
            = UserID::from("<f-0@example.org>");

        let target_fpr: Fingerprint =
            "CE22 ECD2 82F2 19AA 9959  8BA3 B58A 7DA6 1CA9 7F55"
           .parse().expect("valid fingerprint");
        let target_uid
            = UserID::from("<target@example.org>");


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cliques.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        let auth = n.backward_propagate(target_fpr.clone(),
                                        target_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        // root -> a-0 -> b-0 -> ... -> f-0 -> target
        pcmp(&n, &auth.get(&root_fpr).unwrap(),
             90, 120,
             &[
                 &root_fpr,
                 &a_0_fpr,
                 &a_1_fpr,
                 &b_0_fpr,
                 &b_1_fpr,
                 &c_0_fpr,
                 &c_1_fpr,
                 &d_0_fpr,
                 &d_1_fpr,
                 &e_0_fpr,
                 &f_0_fpr,
                 &target_fpr
             ]);


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cliques-local-optima.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        let auth = n.backward_propagate(target_fpr.clone(),
                                        target_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        // root -> a-0 -> b-0 -> ... -> f-0 -> target
        pcmp(&n, &auth.get(&root_fpr).unwrap(),
             93, 30,
             &[
                 &root_fpr,
                 &b_0_fpr,
                 &b_1_fpr,
                 &c_0_fpr,
                 &c_1_fpr,
                 &d_0_fpr,
                 &d_1_fpr,
                 &e_0_fpr,
                 &f_0_fpr,
                 &target_fpr
             ]);

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cliques-local-optima-2.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        let auth = n.backward_propagate(target_fpr.clone(),
                                        target_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        // root -> a-0 -> b-0 -> ... -> f-0 -> target
        pcmp(&n, &auth.get(&root_fpr).unwrap(),
             94, 30,
             &[
                 &root_fpr,
                 &b_0_fpr,
                 &b_1_fpr,
                 &c_1_fpr,
                 &d_0_fpr,
                 &d_1_fpr,
                 &e_0_fpr,
                 &f_0_fpr,
                 &target_fpr
             ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn roundabout() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "41E9B069C96EB6D47525294B10BBBD00912BEA02"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "2E90AEE966DF28CB916439B20397E086E705AC1A"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 3267D46247D26101B3E5014CDF4F9BA5831D91DA
        // Certified by: 41E9B069C96EB6D47525294B10BBBD00912BEA02

        let carol_fpr: Fingerprint =
            "92DDE8747C8E6ED09D41A4E1330D1190E858754C"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 41E9B069C96EB6D47525294B10BBBD00912BEA02

        let dave_fpr: Fingerprint =
            "D4515E6619084ED8142DF8589059E3846A025611"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 92DDE8747C8E6ED09D41A4E1330D1190E858754C

        let elmar_fpr: Fingerprint =
            "E553C11DCFA777F3205E5090F5EE59C2795CDBA2"
           .parse().expect("valid fingerprint");
        let elmar_uid
            = UserID::from("<elmar@example.org>");
        // Certified by: AE40578962411356F9609CAA9C2447E61FFDBB15
        // Certified by: D4515E6619084ED8142DF8589059E3846A025611

        let frank_fpr: Fingerprint =
            "3267D46247D26101B3E5014CDF4F9BA5831D91DA"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");
        // Certified by: E553C11DCFA777F3205E5090F5EE59C2795CDBA2

        let george_fpr: Fingerprint =
            "CCD5DB27BD7C4F8E2010083605EF17E8A93EB652"
           .parse().expect("valid fingerprint");
        let george_uid
            = UserID::from("<george@example.org>");
        // Certified by: AE40578962411356F9609CAA9C2447E61FFDBB15
        // Certified by: 2E90AEE966DF28CB916439B20397E086E705AC1A

        let henry_fpr: Fingerprint =
            "7F62EF97091AE1FCB4E1C67EC8D9E94C4731529B"
           .parse().expect("valid fingerprint");
        let henry_uid
            = UserID::from("<henry@example.org>");
        // Certified by: CCD5DB27BD7C4F8E2010083605EF17E8A93EB652

        let isaac_fpr: Fingerprint =
            "32FD4D68B3227334CD0583E9FA0721F49D2F395D"
           .parse().expect("valid fingerprint");
        let isaac_uid
            = UserID::from("<isaac@example.org>");
        // Certified by: 7F62EF97091AE1FCB4E1C67EC8D9E94C4731529B

        let jenny_fpr: Fingerprint =
            "AE40578962411356F9609CAA9C2447E61FFDBB15"
           .parse().expect("valid fingerprint");
        let jenny_uid
            = UserID::from("<jenny@example.org>");


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("roundabout.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        let auth = n.backward_propagate(isaac_fpr.clone(),
                                        isaac_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, &auth.get(&alice_fpr).unwrap(),
             0, 60,
             &[ &alice_fpr, &bob_fpr, &george_fpr, &henry_fpr, &isaac_fpr ]);
        assert!(&auth.get(&carol_fpr).is_none());
        assert!(&auth.get(&jenny_fpr).is_none());


        let auth = n.backward_propagate(henry_fpr.clone(),
                                        henry_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        // The backward propagation algorithm doesn't know that jenny
        // is not reachable from the root (alice).
        pcmp(&n, &auth.get(&jenny_fpr).unwrap(),
             0, 100,
             &[ &jenny_fpr, &george_fpr, &henry_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn local_optima() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "EAAE12F98D39F38BF0D1B4C5C46A428ADEFBB2F8"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: EAAE12F98D39F38BF0D1B4C5C46A428ADEFBB2F8
        // Certified by: EAAE12F98D39F38BF0D1B4C5C46A428ADEFBB2F8

        let carol_fpr: Fingerprint =
            "E9DF94E389F529F8EF6AA223F6CC1F8544C0874D"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F

        let dave_fpr: Fingerprint =
            "C2F822F17B68E946853A2DCFF55541D89F27F88B"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: E9DF94E389F529F8EF6AA223F6CC1F8544C0874D
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F

        let ellen_fpr: Fingerprint =
            "70507A9058A57FEAE18CC3CE6A398AC9051D9CA8"
           .parse().expect("valid fingerprint");
        let ellen_uid
            = UserID::from("<ellen@example.org>");
        // Certified by: C2F822F17B68E946853A2DCFF55541D89F27F88B
        // Certified by: C2F822F17B68E946853A2DCFF55541D89F27F88B
        // Certified by: E9DF94E389F529F8EF6AA223F6CC1F8544C0874D

        let francis_fpr: Fingerprint =
            "D8DDA78A2297CA3C35B9377577E8B54B9350C082"
           .parse().expect("valid fingerprint");
        let francis_uid
            = UserID::from("<francis@example.org>");
        // Certified by: 70507A9058A57FEAE18CC3CE6A398AC9051D9CA8
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F

        let georgina_fpr: Fingerprint =
            "C5D1B22FEC75911A04E1A5DC75B66B994E70ADE2"
           .parse().expect("valid fingerprint");
        let georgina_uid
            = UserID::from("<georgina@example.org>");
        // Certified by: 70507A9058A57FEAE18CC3CE6A398AC9051D9CA8

        let henry_fpr: Fingerprint =
            "F260739E3F755389EFC2FEE67F58AACB661D5120"
           .parse().expect("valid fingerprint");
        let henry_uid
            = UserID::from("<henry@example.org>");
        // Certified by: 70507A9058A57FEAE18CC3CE6A398AC9051D9CA8


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("local-optima.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        let auth = n.backward_propagate(henry_fpr.clone(),
                                        henry_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &ellen_fpr, &henry_fpr ]);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             0, 100,
             &[ &bob_fpr, &carol_fpr, &ellen_fpr, &henry_fpr ]);
        pcmp(&n, auth.get(&carol_fpr).unwrap(),
             0, 100,
             &[ &carol_fpr, &ellen_fpr, &henry_fpr ]);
        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             0, 50,
             &[ &dave_fpr, &ellen_fpr, &henry_fpr ]);
        pcmp(&n, auth.get(&ellen_fpr).unwrap(),
             0, 120,
             &[ &ellen_fpr, &henry_fpr ]);
        assert!(auth.get(&francis_fpr).is_none());
        assert!(auth.get(&georgina_fpr).is_none());

        let auth = n.backward_propagate(francis_fpr.clone(),
                                        francis_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        // Recall: given a choice, we prefer the forward pointer that
        // has the least depth.
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             149, 75,
             &[ &alice_fpr, &bob_fpr, &francis_fpr ]);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             200, 75,
             &[ &bob_fpr, &francis_fpr ]);
        pcmp(&n, auth.get(&carol_fpr).unwrap(),
             49, 100,
             &[ &carol_fpr, &ellen_fpr, &francis_fpr ]);
        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             99, 50,
             &[ &dave_fpr, &ellen_fpr, &francis_fpr ]);
        pcmp(&n, auth.get(&ellen_fpr).unwrap(),
             100, 120,
             &[ &ellen_fpr, &francis_fpr ]);
        assert!(auth.get(&georgina_fpr).is_none());
        assert!(auth.get(&henry_fpr).is_none());

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn best_via_root() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "B95FF5B1D055D26F758FD4E3BF12C4D1D28FDFFB"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "6A8B9EC7D0A1B297B5D4A7A1C048DFF96601D9BD"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: B95FF5B1D055D26F758FD4E3BF12C4D1D28FDFFB

        let carol_fpr: Fingerprint =
            "77A6F7D4BEE0369F70B249579D2987669F792B35"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 6A8B9EC7D0A1B297B5D4A7A1C048DFF96601D9BD

        let target_fpr: Fingerprint =
            "2AB08C06FC795AC26673B23CAD561ABDCBEBFDF0"
           .parse().expect("valid fingerprint");
        let target_uid
            = UserID::from("<target@example.org>");
        // Certified by: 77A6F7D4BEE0369F70B249579D2987669F792B35
        // Certified by: 56D44411F982758169E4681B402E8D5D9D7D6567

        let yellow_fpr: Fingerprint =
            "86CB4639D1FE096BA941D05822B8AF50198C49DD"
           .parse().expect("valid fingerprint");
        let yellow_uid
            = UserID::from("<yellow@example.org>");
        // Certified by: B95FF5B1D055D26F758FD4E3BF12C4D1D28FDFFB

        let zebra_fpr: Fingerprint =
            "56D44411F982758169E4681B402E8D5D9D7D6567"
           .parse().expect("valid fingerprint");
        let zebra_uid
            = UserID::from("<zebra@example.org>");
        // Certified by: 86CB4639D1FE096BA941D05822B8AF50198C49DD

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("best-via-root.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        /// Tests.

        let auth = n.backward_propagate(target_fpr.clone(),
                                        target_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             9, 120,
             &[ &bob_fpr, &carol_fpr, &target_fpr ]);

        pcmp(&n, auth.get(&carol_fpr).unwrap(),
             10, 120,
             &[ &carol_fpr, &target_fpr ]);

        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             8, 120,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &target_fpr ]);

        let auth = n.backward_propagate(target_fpr.clone(),
                                        target_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             8, 120,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &target_fpr ]);

        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             9, 120,
             &[ &bob_fpr, &carol_fpr, &target_fpr ]);

        pcmp(&n, auth.get(&carol_fpr).unwrap(),
             10, 120,
             &[ &carol_fpr, &target_fpr ]);



        // Again, but this time we specify the roots.

        let n = NetworkBuilder::rooted(&store, &[ alice_fpr.clone() ]).build();
        let auth = n.backward_propagate(target_fpr.clone(),
                                        target_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             8, 120,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &target_fpr ]);

        // As seen above, the best path from Alice to the target is
        // via Bob.  But, when both Alice and Bob are both fully
        // trusted roots, the returned path is not via Bob, but one
        // that is less optimal.
        let n = NetworkBuilder::rooted(
            &store,
            &[ alice_fpr.clone(), bob_fpr.clone() ])
            .build();
        let auth = n.backward_propagate(target_fpr.clone(),
                                        target_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             9, 120,
             &[ &bob_fpr, &carol_fpr, &target_fpr ]);

        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             8, 50,
             &[ &alice_fpr, &yellow_fpr, &zebra_fpr, &target_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn regex_1() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "3AD1F297E4B150F75DBFC43476FB81BFE0665C3A"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@some.org>");

        let bob_fpr: Fingerprint =
            "20C812117FB2A3940EAE9160FEE6B4E47A096FD1"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 3AD1F297E4B150F75DBFC43476FB81BFE0665C3A

        let carol_fpr: Fingerprint =
            "BC30978345D789CADECDE492F54B42E1625E1A1D"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 20C812117FB2A3940EAE9160FEE6B4E47A096FD1

        let dave_fpr: Fingerprint =
            "319810FAD46CBE96DAD7F1F5B014902592999B21"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: 20C812117FB2A3940EAE9160FEE6B4E47A096FD1

        let ed_fpr: Fingerprint =
            "23D7418EA0C6A42A54C32DBE8D4FE4911ED08467"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 319810FAD46CBE96DAD7F1F5B014902592999B21

        let frank_fpr: Fingerprint =
            "7FAE20D68EE87F74368AF275A0C40E741FC1C50F"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@other.org>");
        // Certified by: 319810FAD46CBE96DAD7F1F5B014902592999B21


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("regex-1.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        // Tests.

        // alice as root.
        let auth = n.backward_propagate(bob_fpr.clone(),
                                        bob_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             3, 100,
             &[ &alice_fpr, &bob_fpr ]);

        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             1, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // There is no path, because dave@example.org does not match
        // the constraint on bob (domain: example.org).
        assert!(auth.get(&alice_fpr).is_none());

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // There is no path, because ed@example.org does not match
        // the constraint on dave (domain: other.org).
        assert!(auth.get(&alice_fpr).is_none());

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        // There is no path, because frank@other.org does not match
        // the constraint on bob (domain: example.org).
        assert!(auth.get(&alice_fpr).is_none());


        // bob as root.
        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             1, 100,
             &[ &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             1, 100,
             &[ &bob_fpr, &dave_fpr ]);

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);

        // There is no path, because ed@example.org does not match
        // the constraint on dave (domain: other.org).
        assert!(auth.get(&bob_fpr).is_none());

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             0, 100,
             &[ &bob_fpr, &dave_fpr, &frank_fpr ]);


        // dave as root.
        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             1, 100,
             &[ &dave_fpr, &ed_fpr ]);

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             1, 100,
             &[ &dave_fpr, &frank_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn regex_2() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "5C396C920399898461F17CB747FDBF3EB3453919"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@some.org>");

        let bob_fpr: Fingerprint =
            "584D195AD89CE0354D2CCBAEBCDD9EBC09692780"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@some.org>");
        // Certified by: 5C396C920399898461F17CB747FDBF3EB3453919

        let carol_fpr: Fingerprint =
            "FC7A96D4810D0CF477031956AED58C644370C183"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@other.org>");
        // Certified by: 584D195AD89CE0354D2CCBAEBCDD9EBC09692780

        let dave_fpr: Fingerprint =
            "58077E659732526C1B8BF9837EFC0EDE07B506A8"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@their.org>");
        // Certified by: FC7A96D4810D0CF477031956AED58C644370C183

        let ed_fpr: Fingerprint =
            "36089C49F18BF6FC6BCA35E3BB85877766C009E4"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 58077E659732526C1B8BF9837EFC0EDE07B506A8

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("regex-2.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        /// Tests.

        let auth = n.backward_propagate(bob_fpr.clone(),
                                        bob_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             7, 100,
             &[ &alice_fpr, &bob_fpr ]);

        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // An interesting case: bob authorizes carol@other.org to
        // introduce other certificates for example.org.  This means
        // that carol@other.org is authenticated, because the regex
        // only applies to the certifications that carol makes, not
        // bob's certificate of carol.
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             6, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // There is no path, because dave@their.org does not match
        // the constraint on carol (domain: example.org).
        assert!(auth.get(&alice_fpr).is_none());

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             4, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr, &ed_fpr ]);


        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // An interesting case: bob authorizes carol@other.org to
        // introduce other certificates for example.org.  This means
        // that carol@other.org is authenticated, because the regex
        // only applies to the certifications that carol makes, not
        // bob's certificate of carol.
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             7, 100,
             &[ &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // There is no path, because dave@their.org does not match
        // the constraint on carol (domain: example.org).
        assert!(auth.get(&bob_fpr).is_none());

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             5, 100,
             &[ &bob_fpr, &carol_fpr, &dave_fpr, &ed_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&carol_fpr).unwrap(),
             7, 100,
             &[ &carol_fpr, &dave_fpr ]);

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&carol_fpr).unwrap(),
             6, 100,
             &[ &carol_fpr, &dave_fpr, &ed_fpr ]);



        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn regex_3() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "D8CFEBBA006E2ED57CF45CC413F0BAE09D94FE4E"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@some.org>");

        let bob_fpr: Fingerprint =
            "A75DC1A1EDA5282F3A7381B51824E46BBCC801F0"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: D8CFEBBA006E2ED57CF45CC413F0BAE09D94FE4E

        let carol_fpr: Fingerprint =
            "4BCD4325BDACA452F0301227A30CB4BCC329E769"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: A75DC1A1EDA5282F3A7381B51824E46BBCC801F0

        let dave_fpr: Fingerprint =
            "2E1AAA8D9A22C94ACCA362A22B34031CD5CB9380"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: A75DC1A1EDA5282F3A7381B51824E46BBCC801F0

        let ed_fpr: Fingerprint =
            "F645D081F480BE26C7D2C84D941B3E2CE53FAF16"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 2E1AAA8D9A22C94ACCA362A22B34031CD5CB9380

        let frank_fpr: Fingerprint =
            "AFAB11F1A37FD20C85CF8093F4941D1A0EC5749F"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@other.org>");
        // Certified by: 2E1AAA8D9A22C94ACCA362A22B34031CD5CB9380

        let george_fpr: Fingerprint =
            "D01C8752D9BA9F3F5F06B21F394E911938D6DB0A"
           .parse().expect("valid fingerprint");
        let george_uid
            = UserID::from("<george@their.org>");
        // Certified by: 2E1AAA8D9A22C94ACCA362A22B34031CD5CB9380

        let henry_fpr: Fingerprint =
            "B99A8696FD820192CEEE285D3A253E49F1D97109"
           .parse().expect("valid fingerprint");
        let henry_uid
            = UserID::from("<henry@their.org>");
        // Certified by: A75DC1A1EDA5282F3A7381B51824E46BBCC801F0


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("regex-3.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        /// Tests.

        // alice as root.
        let auth = n.backward_propagate(bob_fpr.clone(),
                                        bob_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             3, 100,
             &[ &alice_fpr, &bob_fpr ]);

        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             1, 100,
             &[ &alice_fpr, &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             1, 100,
             &[ &alice_fpr, &bob_fpr, &dave_fpr ]);

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // There is no path, because ed@example.org does not match
        // the constraint on dave (domain: other.org).
        assert!(auth.get(&alice_fpr).is_none());

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 100,
             &[ &alice_fpr, &bob_fpr, &dave_fpr, &frank_fpr ]);

        let auth = n.backward_propagate(george_fpr.clone(),
                                        george_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        assert!(auth.get(&alice_fpr).is_none());

        let auth = n.backward_propagate(henry_fpr.clone(),
                                        henry_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        assert!(auth.get(&alice_fpr).is_none());


        // bob as root.
        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             1, 100,
             &[ &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             1, 100,
             &[ &bob_fpr, &dave_fpr ]);

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        // There is no path, because ed@example.org does not match
        // the constraint on dave (domain: other.org).
        assert!(auth.get(&bob_fpr).is_none());

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             0, 100,
             &[ &bob_fpr, &dave_fpr, &frank_fpr ]);

        let auth = n.backward_propagate(george_fpr.clone(),
                                        george_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             0, 100,
             &[ &bob_fpr, &dave_fpr, &george_fpr ]);

        let auth = n.backward_propagate(henry_fpr.clone(),
                                        henry_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&bob_fpr).unwrap(),
             1, 100,
             &[ &bob_fpr, &henry_fpr ]);


        // dave as root.
        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             1, 100,
             &[ &dave_fpr, &ed_fpr ]);

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             1, 100,
             &[ &dave_fpr, &frank_fpr ]);

        let auth = n.backward_propagate(george_fpr.clone(),
                                        george_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&dave_fpr).unwrap(),
             1, 100,
             &[ &dave_fpr, &george_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn multiple_userids_1() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "03182611B91B1E7E20B848E83DFC151ABFAD85D5"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@other.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");
        // Certified by: 2A2A4A23A7EEC119BC0B46642B3825DC02A05FEA

        let carol_fpr: Fingerprint =
            "9CA36907B46FE7B6B9EE9601E78064C12B6D7902"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 03182611B91B1E7E20B848E83DFC151ABFAD85D5

        let dave_fpr: Fingerprint =
            "C1BC6794A6C6281B968A6A41ACE2055D610CEA03"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: 9CA36907B46FE7B6B9EE9601E78064C12B6D7902


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-userids-1.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        /// Tests.

        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 70,
             &[ &alice_fpr, &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 50,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn multiple_userids_2() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "F1C99C4019837703DD17C45440F8A0141DF278EA"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "5528B9E5DAFC519ED2E37F0377B332E4111456CB"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@other.org>");
        // Certified by: F1C99C4019837703DD17C45440F8A0141DF278EA
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");
        // Certified by: F1C99C4019837703DD17C45440F8A0141DF278EA

        let carol_fpr: Fingerprint =
            "6F8291428420AB53576BAB4BEFF6477D3E348D71"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 5528B9E5DAFC519ED2E37F0377B332E4111456CB

        let dave_fpr: Fingerprint =
            "62C57D90DAD253DEA01D5A86C7382FD6285C18F0"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: 6F8291428420AB53576BAB4BEFF6477D3E348D71

        let ed_fpr: Fingerprint =
            "0E974D0ACBA0C4D8F51D7CF68F048FF83B173504"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 6F8291428420AB53576BAB4BEFF6477D3E348D71

        let frank_fpr: Fingerprint =
            "5BEE3D41F85B2FCBC300DE4E18CB2BDA65465F03"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@other.org>");
        // Certified by: 5528B9E5DAFC519ED2E37F0377B332E4111456CB

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-userids-2.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        /// Tests.

        let auth = n.backward_propagate(bob_fpr.clone(),
                                        bob_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             Depth::unconstrained(), 70,
             &[ &alice_fpr, &bob_fpr ]);

        let auth = n.backward_propagate(bob_fpr.clone(),
                                        bob_some_org_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             1, 50,
             &[ &alice_fpr, &bob_fpr ]);

        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 50,
             &[ &alice_fpr, &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 70,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ]);

        let auth = n.backward_propagate(ed_fpr.clone(),
                                        ed_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        assert!(auth.get(&alice_fpr).is_none());

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 70,
             &[ &alice_fpr, &bob_fpr, &frank_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn multiple_certifications_1() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "9219941467AA737C6EC1207959A2CEFC112C359A"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "72CAA0F0A4A020F5FA20CD8CB5CC04473AA88123"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 9219941467AA737C6EC1207959A2CEFC112C359A
        // Certified by: 9219941467AA737C6EC1207959A2CEFC112C359A
        // Certified by: 9219941467AA737C6EC1207959A2CEFC112C359A

        let carol_fpr: Fingerprint =
            "853304031E7B0B116BBD0B398734F11945313904"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 72CAA0F0A4A020F5FA20CD8CB5CC04473AA88123

        let dave_fpr: Fingerprint =
            "4C77ABDBE4F855E0C3C7A7D549F6B2BFDA83E424"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 853304031E7B0B116BBD0B398734F11945313904

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-certifications-1.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        /// Tests.

        let auth = n.backward_propagate(carol_fpr.clone(),
                                        carol_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 70,
             &[ &alice_fpr, &bob_fpr, &carol_fpr ]);

        let auth = n.backward_propagate(dave_fpr.clone(),
                                        dave_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 50,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn multiple_userids_3() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "DA3CFC60BD4B8835702A66782C7A431946C12DF7"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "28C108707090FCDFF630D1E141FB02F0E397D55E"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@other.org>");
        // Certified by: DA3CFC60BD4B8835702A66782C7A431946C12DF7
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");
        // Certified by: DA3CFC60BD4B8835702A66782C7A431946C12DF7
        let bob_third_org_uid
            = UserID::from("<bob@third.org>");

        let carol_fpr: Fingerprint =
            "9FB1D2F41AB5C478378E728C8DD5A5A434EEAAB8"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 28C108707090FCDFF630D1E141FB02F0E397D55E

        let dave_fpr: Fingerprint =
            "0C131F8959F45D08B6136FDAAD2E16A26F73D48E"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 28C108707090FCDFF630D1E141FB02F0E397D55E

        let ed_fpr: Fingerprint =
            "296935FAE420CCCF3AEDCEC9232BFF0AE9A7E5DB"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 0C131F8959F45D08B6136FDAAD2E16A26F73D48E

        let frank_fpr: Fingerprint =
            "A72AA1B7D9D8CB04D988F1520A404E37A7766608"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");
        // Certified by: 9FB1D2F41AB5C478378E728C8DD5A5A434EEAAB8
        // Certified by: 296935FAE420CCCF3AEDCEC9232BFF0AE9A7E5DB

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-userids-3.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

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

        /// Tests.

        let auth = n.backward_propagate(frank_fpr.clone(),
                                        frank_uid.clone(),
                                        false,
                                        &IdempotentCertificationFilter::new(),
                                        false);
        pcmp(&n, auth.get(&alice_fpr).unwrap(),
             0, 20,
             &[ &alice_fpr, &bob_fpr, &carol_fpr, &frank_fpr ]);

        Ok(())
    }
}