//! The Resolver is the heart of cargo-vet, and does all the work to validate the audits
//! for your current packages and to suggest fixes. This is done in 3 phases:
//!
//! 1. Resolving required criteria based on your policies
//! 2. Searching for audits which satisfy the required criteria
//! 3. Suggesting audits that would make your project pass validation
//!
//! # High-level Usage
//!
//! * [`resolve`] is the main entry point, Validating and Searching and producing a [`ResolveReport`]
//! * [`ResolveReport::compute_suggest`] does Suggesting and produces a [`Suggest`]
//! * various methods on [`ResolveReport`] and [`Suggest`] handle printing
//! * [`update_store`] handles automatically minimizing and generating exemptions and imports
//!
//! # Low-level Design
//!
//!
//! ## Resolve
//!
//! * construct the [`DepGraph`] and [`CriteriaMapper`]
//!     * the DepGraph contains computed facts like whether a node is a third-party or dev-only
//!       and includes a special topological sorting of the packages that prioritizes the normal
//!       build over the dev build (it's complicated...)
//!
//! * resolve_requirements: for each package, resolve what criteria it needs to be audited for
//!     * start with root targets and propagate requirements out towards leaf crates
//!     * policies can override requirements on the target crate and its dependencies
//!
//! * resolve_audits: for each package, resolve what criteria it's audited for
//!     * compute the [`AuditGraph`] and check for violations
//!     * for each criteria, search the for a connected path in the audit graph
//!     * check if the criteria are satisfied
//!         * if they are, record caveats which were required for the criteria
//!         * if they aren't record the criteria which failed, and how to fix them
//!
//!
//! ## Suggest
//!
//! * enumerate the failures and perform a number of diffstats based on the
//!   existing set of criteria, to suggest the best audit and criteria which could
//!   be used to allow the crate to vet successfully.

use cargo_metadata::{DependencyKind, Metadata, Node, PackageId};
use futures_util::future::join_all;
use miette::IntoDiagnostic;
use serde::{Deserialize, Serialize};
use std::cell::RefCell;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::sync::Arc;
use tracing::{trace, trace_span, warn};

use crate::cli::{DumpGraphArgs, GraphFilter, GraphFilterProperty, GraphFilterQuery, OutputFormat};
use crate::criteria::{CriteriaMapper, CriteriaSet};
use crate::errors::SuggestError;
use crate::format::{
    self, AuditEntry, AuditKind, AuditsFile, CratesCacheUser, CratesPublisher, CriteriaName, Delta,
    DiffStat, ExemptedDependency, FastMap, FastSet, ImportName, ImportsFile, JsonPackage,
    JsonReport, JsonReportConclusion, JsonReportFailForVet, JsonReportFailForViolationConflict,
    JsonReportSuccess, JsonSuggest, JsonSuggestItem, JsonVetFailure, PackageName, PackageStr,
    Policy, UnpublishedEntry, VetVersion, WildcardEntry,
};
use crate::format::{SortedMap, SortedSet};
use crate::network::Network;
use crate::out::{progress_bar, IncProgressOnDrop, Out};
use crate::storage::Cache;
use crate::string_format::FormatShortList;
use crate::{Config, PackageExt, Store};

pub struct ResolveReport<'a> {
    /// The Cargo dependency graph as parsed and understood by cargo-vet.
    ///
    /// All [`PackageIdx`][] values are indices into this graph's nodes.
    pub graph: DepGraph<'a>,

    /// Mappings between criteria names and CriteriaSets/Indices.
    pub criteria_mapper: CriteriaMapper,

    /// Low-level results for each package's individual criteria resolving
    /// analysis, indexed by [`PackageIdx`][]. Will be `None` for first-party
    /// crates or crates with violation conflicts.
    pub results: Vec<Option<ResolveResult>>,

    /// The final conclusion of our analysis.
    pub conclusion: Conclusion,
}

#[derive(Debug)]
pub enum Conclusion {
    Success(Success),
    FailForViolationConflict(FailForViolationConflict),
    FailForVet(FailForVet),
}

#[derive(Debug, Clone)]
pub struct Success {
    /// Third-party packages that were successfully vetted using only 'exemptions'
    pub vetted_with_exemptions: Vec<PackageIdx>,
    /// Third-party packages that were successfully vetted using both 'audits' and 'exemptions'
    pub vetted_partially: Vec<PackageIdx>,
    /// Third-party packages that were successfully vetted using only 'audits'
    pub vetted_fully: Vec<PackageIdx>,
}

#[derive(Debug, Clone)]
pub struct FailForViolationConflict {
    pub violations: Vec<(PackageIdx, Vec<ViolationConflict>)>,
}

#[derive(Debug)]
pub struct FailForVet {
    /// These packages are to blame and need to be fixed
    pub failures: Vec<(PackageIdx, AuditFailure)>,
    pub suggest: Option<Suggest>,
}

// FIXME: This format is pretty janky and unstable, so we probably should come
// up with an actually-useful format for this.
#[allow(clippy::large_enum_variant)]
#[derive(Debug, Clone, Serialize, Deserialize)]
pub enum ViolationConflict {
    UnauditedConflict {
        violation_source: Option<ImportName>,
        violation: AuditEntry,
        exemptions: ExemptedDependency,
    },
    AuditConflict {
        violation_source: Option<ImportName>,
        violation: AuditEntry,
        audit_source: Option<ImportName>,
        audit: AuditEntry,
    },
}

#[derive(Debug, Default)]
pub struct Suggest {
    pub suggestions: Vec<SuggestItem>,
    pub suggestions_by_criteria: SortedMap<CriteriaName, Vec<SuggestItem>>,
    pub total_lines: u64,
    pub warnings: Vec<String>,
}

#[derive(Debug, Clone)]
pub struct TrustHint {
    trusted_by: Vec<String>,
    publisher: CratesCacheUser,
    exact_version: bool,
}

#[derive(Debug, Clone)]
pub struct SuggestItem {
    pub package: PackageIdx,
    pub suggested_criteria: CriteriaSet,
    pub suggested_diff: DiffRecommendation,
    pub notable_parents: Vec<String>,
    pub publisher_login: Option<String>,
    pub trust_hint: Option<TrustHint>,
    pub is_sole_publisher: bool,
    pub registry_suggestion: Vec<RegistrySuggestion>,
}

#[derive(Debug, Clone, Serialize, Deserialize, Eq, PartialEq)]
pub struct DiffRecommendation {
    pub from: Option<VetVersion>,
    pub to: VetVersion,
    pub diffstat: DiffStat,
}

#[derive(Debug, Clone)]
pub struct RegistrySuggestion {
    pub name: ImportName,
    pub url: Vec<String>,
    pub diff: DiffRecommendation,
}

/// An "interned" cargo PackageId which is used to uniquely identify packages throughout
/// the code. This is simpler and faster than actually using PackageIds (strings) or name+version.
/// In the current implementation it can be used to directly index into the `graph` or `results`.
pub type PackageIdx = usize;

#[derive(Debug, Clone, Serialize)]
pub struct PackageNode<'a> {
    #[serde(skip_serializing_if = "pkgid_unstable")]
    /// The PackageId that cargo uses to uniquely identify this package
    ///
    /// Prefer using a [`DepGraph`] and its memoized [`PackageIdx`]'s.
    pub package_id: &'a PackageId,
    /// The name of the package
    pub name: PackageStr<'a>,
    /// The version of this package
    pub version: VetVersion,
    /// All normal deps (shipped in the project or a proc-macro it uses)
    pub normal_deps: Vec<PackageIdx>,
    /// All build deps (used for build.rs)
    pub build_deps: Vec<PackageIdx>,
    /// All dev deps (used for tests/benches)
    pub dev_deps: Vec<PackageIdx>,
    /// Just the normal and build deps (deduplicated)
    pub normal_and_build_deps: Vec<PackageIdx>,
    /// All deps combined (deduplicated)
    pub all_deps: Vec<PackageIdx>,
    /// All reverse-deps (mostly just used for contextualizing what uses it)
    pub reverse_deps: SortedSet<PackageIdx>,
    /// Whether this package is a workspace member (can have dev-deps)
    pub is_workspace_member: bool,
    /// Whether this package is third-party (from crates.io)
    pub is_third_party: bool,
    /// Whether this package is a root in the "normal" build graph
    pub is_root: bool,
    /// Whether this package only shows up in dev (test/bench) builds
    pub is_dev_only: bool,
}

/// Don't serialize path package ids, not stable across systems
fn pkgid_unstable(pkgid: &PackageId) -> bool {
    pkgid.repr.contains("(path+file:/")
}

/// The dependency graph in a form we can use more easily.
#[derive(Debug, Clone)]
pub struct DepGraph<'a> {
    pub nodes: Vec<PackageNode<'a>>,
    pub interner_by_pkgid: SortedMap<&'a PackageId, PackageIdx>,
    pub topo_index: Vec<PackageIdx>,
}

/// Results and notes from running vet on a particular package.
#[derive(Debug, Clone)]
pub struct ResolveResult {
    /// Cache of search results for each criteria.
    pub search_results: Vec<Result<Vec<DeltaEdgeOrigin>, SearchFailure>>,
}

#[derive(Debug, Clone)]
pub struct AuditFailure {
    pub criteria_failures: CriteriaSet,
}

/// Value indicating a failure to find a path in the audit graph between two nodes.
#[derive(Debug, Clone)]
pub struct SearchFailure {
    /// Nodes we could reach from "root"
    pub reachable_from_root: SortedSet<Option<VetVersion>>,
    /// Nodes we could reach from the "target"
    pub reachable_from_target: SortedSet<Option<VetVersion>>,
}

type DirectedAuditGraph<'a> = SortedMap<Option<&'a VetVersion>, Vec<DeltaEdge<'a>>>;

/// A graph of the audits for a package.
///
/// The nodes of the graph are Versions and the edges are audits.
/// An AuditGraph is directed, potentially cyclic, and potentially disconnected.
///
/// There are two important versions in each AuditGraph:
///
/// * The "root" version (None) which exists as a dummy node for full-audits
/// * The "target" version which is the current version of the package
///
/// The edges are constructed as follows:
///
/// * Delta Audits desugar directly to edges
/// * Full Audits and Unaudited desugar to None -> Some(Version)
///
/// If there are multiple versions of a package in-tree, we analyze each individually
/// so there is always one root and one target. All we want to know is if there exists
/// a path between the two where every edge on that path has a given criteria. We do this
/// check for every possible criteria in a loop to keep the analysis simple and composable.
///
/// When resolving the audits for a package, we create a "forward" graph and a "backward" graph.
/// These are the same graphs but with the edges reversed. The backward graph is only used if
/// we can't find the desired path in the forward graph, and is used to compute the
/// reachability set of the target version for that criteria. That reachability is
/// used for `suggest`.
#[derive(Debug, Clone)]
pub struct AuditGraph<'a> {
    forward_audits: DirectedAuditGraph<'a>,
    backward_audits: DirectedAuditGraph<'a>,
}

/// The precise origin of an edge in the audit graph.
#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd)]
pub enum DeltaEdgeOrigin {
    /// This edge represents an audit from the local audits.toml.
    StoredLocalAudit { audit_index: usize },
    /// This edge represents an audit imported from a peer, potentially stored
    /// in the local imports.lock.
    ImportedAudit {
        import_index: usize,
        audit_index: usize,
    },
    /// This edge represents a reified wildcard audit.
    WildcardAudit {
        import_index: Option<usize>,
        audit_index: usize,
        publisher_index: usize,
    },
    /// This edge represents a trusted publisher.
    Trusted { publisher_index: usize },
    /// This edge represents an exemption from the local config.toml.
    Exemption { exemption_index: usize },
    /// This edge represents an unpublished entry in imports.lock.
    Unpublished { unpublished_index: usize },
    /// This edge represents brand new exemption which didn't previously exist
    /// in the audit graph. Will only ever be produced from
    /// SearchMode::RegenerateExemptions.
    FreshExemption { version: VetVersion },
}

/// An indication of a required imported entry or exemption. Used to compute the
/// minimal set of possible imports for imports.lock.
#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd)]
pub enum RequiredEntry {
    Audit {
        import_index: usize,
        audit_index: usize,
    },
    WildcardAudit {
        import_index: usize,
        audit_index: usize,
    },
    Publisher {
        publisher_index: usize,
    },
    Exemption {
        exemption_index: usize,
    },
    Unpublished {
        unpublished_index: usize,
    },
    // NOTE: This variant must come last, as code in `update_store` depends on
    // `FreshExemption` entries sorting after all other entries.
    FreshExemption {
        version: VetVersion,
    },
}

/// A directed edge in the graph of audits. This may be forward or backwards,
/// depending on if we're searching from "roots" (forward) or the target (backward).
/// The source isn't included because that's implicit in the Node.
#[derive(Debug, Clone)]
struct DeltaEdge<'a> {
    /// The version this edge goes to.
    version: Option<&'a VetVersion>,
    /// The criteria that this edge is valid for.
    criteria: CriteriaSet,
    /// The origin of this edge. See `DeltaEdgeOrigin`'s documentation for more
    /// details.
    origin: DeltaEdgeOrigin,
    /// Whether or not the edge is a "fresh import", and should be
    /// de-prioritized to avoid unnecessary imports.lock updates.
    is_fresh_import: bool,
}

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub enum SearchMode {
    /// Prefer exemptions over fresh imports when searching.
    PreferExemptions,
    /// Prefer fresh imports over exemptions when searching for paths.
    PreferFreshImports,
    /// Prefer fresh imports over exemptions, and allow introducing new
    /// exemptions or expanding their criteria beyond the written criteria
    /// (unless they are suggest=false).
    RegenerateExemptions,
}

impl<'a> DepGraph<'a> {
    pub fn new(
        metadata: &'a Metadata,
        filter_graph: Option<&Vec<GraphFilter>>,
        policy: Option<&Policy>,
    ) -> Self {
        let default_policy = Policy::default();
        let policy = policy.unwrap_or(&default_policy);
        let package_list = &*metadata.packages;
        let resolve_list = &*metadata
            .resolve
            .as_ref()
            .expect("cargo metadata did not yield resolve!")
            .nodes;
        let package_index_by_pkgid = package_list
            .iter()
            .enumerate()
            .map(|(idx, pkg)| (&pkg.id, idx))
            .collect::<SortedMap<_, _>>();
        let resolve_index_by_pkgid = resolve_list
            .iter()
            .enumerate()
            .map(|(idx, pkg)| (&pkg.id, idx))
            .collect();

        // Do a first-pass where we populate skeletons of the primary nodes
        // and setup the interners, which will only ever refer to these nodes
        let mut interner_by_pkgid = SortedMap::<&PackageId, PackageIdx>::new();
        let mut nodes = vec![];

        // Stub out the initial state of all the nodes
        for resolve_node in resolve_list {
            let package = &package_list[package_index_by_pkgid[&resolve_node.id]];
            nodes.push(PackageNode {
                package_id: &resolve_node.id,
                name: &package.name,
                version: package.vet_version(),
                is_third_party: package.is_third_party(policy),
                // These will get (re)computed later
                normal_deps: vec![],
                build_deps: vec![],
                dev_deps: vec![],
                normal_and_build_deps: vec![],
                all_deps: vec![],
                reverse_deps: SortedSet::new(),
                is_workspace_member: false,
                is_root: false,
                is_dev_only: true,
            });
        }

        // Sort the nodes by package_id to make the graph more stable and to make
        // anything sorted by package_idx to also be approximately sorted by name and version.
        nodes.sort_by_key(|k| k.package_id);

        // Populate the interners based on the new ordering
        for (idx, node) in nodes.iter_mut().enumerate() {
            assert!(interner_by_pkgid.insert(node.package_id, idx).is_none());
        }

        // Do topological sort: just recursively visit all of a node's children, and only add it
        // to the list *after* visiting the children. In this way we have trivially already added
        // all of the dependencies of a node to the list by the time we add itself to the list.
        let mut topo_index = vec![];
        {
            let mut visited = FastMap::new();
            // All of the roots can be found in the workspace_members.
            // First we visit all the workspace members while ignoring dev-deps,
            // this should get us an analysis of the "normal" build graph, which
            // we should compute roots from. Then we will do a second pass on
            // the dev-deps. If we don't do it this way, then dev-dep cycles can
            // confuse us about which nodes are roots or not (potentially resulting
            // in no roots at all!
            for pkgid in &metadata.workspace_members {
                let node_idx = interner_by_pkgid[pkgid];
                nodes[node_idx].is_workspace_member = true;
                visit_node(
                    &mut nodes,
                    &mut topo_index,
                    &mut visited,
                    &interner_by_pkgid,
                    &resolve_index_by_pkgid,
                    resolve_list,
                    node_idx,
                );
            }

            // Anything we visited in the first pass isn't dev-only
            for (&node_idx, ()) in &visited {
                nodes[node_idx].is_dev_only = false;
            }

            // Now that we've visited the normal build graph, mark the nodes that are roots
            for pkgid in &metadata.workspace_members {
                let node = &mut nodes[interner_by_pkgid[pkgid]];
                node.is_root = node.reverse_deps.is_empty();
            }

            // And finally visit workspace-members' dev-deps, safe in the knowledge that
            // we know what all the roots are now.
            for pkgid in &metadata.workspace_members {
                let node_idx = interner_by_pkgid[pkgid];
                let resolve_node = &resolve_list[resolve_index_by_pkgid[pkgid]];
                let dev_deps = deps(
                    resolve_node,
                    &[DependencyKind::Development],
                    &interner_by_pkgid,
                );

                // Now visit all the dev deps
                for &child in &dev_deps {
                    visit_node(
                        &mut nodes,
                        &mut topo_index,
                        &mut visited,
                        &interner_by_pkgid,
                        &resolve_index_by_pkgid,
                        resolve_list,
                        child,
                    );
                    // Note that these edges do not change whether something is a "root"
                    nodes[child].reverse_deps.insert(node_idx);
                }

                let node = &mut nodes[node_idx];
                node.dev_deps = dev_deps;
            }
            fn visit_node<'a>(
                nodes: &mut Vec<PackageNode<'a>>,
                topo_index: &mut Vec<PackageIdx>,
                visited: &mut FastMap<PackageIdx, ()>,
                interner_by_pkgid: &SortedMap<&'a PackageId, PackageIdx>,
                resolve_index_by_pkgid: &SortedMap<&'a PackageId, usize>,
                resolve_list: &'a [cargo_metadata::Node],
                normal_idx: PackageIdx,
            ) {
                // Don't revisit a node we've already seen
                let query = visited.entry(normal_idx);
                if matches!(query, std::collections::hash_map::Entry::Vacant(..)) {
                    query.or_insert(());
                    let resolve_node =
                        &resolve_list[resolve_index_by_pkgid[nodes[normal_idx].package_id]];

                    // Compute the different kinds of dependencies
                    let all_deps = resolve_node
                        .dependencies
                        .iter()
                        .map(|pkgid| interner_by_pkgid[pkgid])
                        .collect::<Vec<_>>();
                    let build_deps =
                        deps(resolve_node, &[DependencyKind::Build], interner_by_pkgid);
                    let normal_deps =
                        deps(resolve_node, &[DependencyKind::Normal], interner_by_pkgid);
                    let normal_and_build_deps = deps(
                        resolve_node,
                        &[DependencyKind::Normal, DependencyKind::Build],
                        interner_by_pkgid,
                    );

                    // Now visit all the normal and build deps
                    for &child in &normal_and_build_deps {
                        visit_node(
                            nodes,
                            topo_index,
                            visited,
                            interner_by_pkgid,
                            resolve_index_by_pkgid,
                            resolve_list,
                            child,
                        );
                        nodes[child].reverse_deps.insert(normal_idx);
                    }

                    // Now visit this node itself
                    topo_index.push(normal_idx);

                    // Now commit all the deps
                    let cur_node = &mut nodes[normal_idx];
                    cur_node.build_deps = build_deps;
                    cur_node.normal_deps = normal_deps;
                    cur_node.normal_and_build_deps = normal_and_build_deps;
                    cur_node.all_deps = all_deps;

                    // dev-deps will be handled in a second pass
                }
            }
            fn deps(
                resolve_node: &Node,
                kinds: &[DependencyKind],
                interner_by_pkgid: &SortedMap<&PackageId, PackageIdx>,
            ) -> Vec<PackageIdx> {
                // Note that dep_kinds has target cfg info. If we want to handle targets
                // we should gather those up with filter/fold instead of just 'any'.
                // TODO: map normal-deps that whose package has a "proc-macro" target to be build-deps
                resolve_node
                    .deps
                    .iter()
                    .filter(|dep| {
                        dep.dep_kinds
                            .iter()
                            .any(|dep_kind| kinds.contains(&dep_kind.kind))
                    })
                    .map(|dep| interner_by_pkgid[&dep.pkg])
                    .collect()
            }
        }

        let result = Self {
            interner_by_pkgid,
            nodes,
            topo_index,
        };

        // Now apply filters, if any
        if let Some(filters) = filter_graph {
            result.filter(filters)
        } else {
            result
        }
    }

    pub fn filter(self, filters: &[GraphFilter]) -> Self {
        use GraphFilter::*;
        use GraphFilterProperty::*;
        use GraphFilterQuery::*;

        fn matches_query(package: &PackageNode, query: &GraphFilterQuery) -> bool {
            match query {
                All(queries) => queries.iter().all(|q| matches_query(package, q)),
                Any(queries) => queries.iter().any(|q| matches_query(package, q)),
                Not(query) => !matches_query(package, query),
                Prop(property) => matches_property(package, property),
            }
        }
        fn matches_property(package: &PackageNode, property: &GraphFilterProperty) -> bool {
            match property {
                Name(val) => package.name == val,
                Version(val) => &package.version == val,
                IsRoot(val) => &package.is_root == val,
                IsWorkspaceMember(val) => &package.is_workspace_member == val,
                IsThirdParty(val) => &package.is_third_party == val,
                IsDevOnly(val) => &package.is_dev_only == val,
            }
        }

        let mut passed_filters = FastSet::new();
        'nodes: for (idx, package) in self.nodes.iter().enumerate() {
            for filter in filters {
                match filter {
                    Include(query) => {
                        if !matches_query(package, query) {
                            continue 'nodes;
                        }
                    }

                    Exclude(query) => {
                        if matches_query(package, query) {
                            continue 'nodes;
                        }
                    }
                }
            }
            // If we pass all the filters, then we get to be included
            passed_filters.insert(idx);
        }

        let mut reachable = FastMap::new();
        for (idx, package) in self.nodes.iter().enumerate() {
            if package.is_workspace_member {
                visit(&mut reachable, &self, &passed_filters, idx);
            }
            fn visit(
                visited: &mut FastMap<PackageIdx, ()>,
                graph: &DepGraph,
                passed_filters: &FastSet<PackageIdx>,
                node_idx: PackageIdx,
            ) {
                if !passed_filters.contains(&node_idx) {
                    return;
                }
                let query = visited.entry(node_idx);
                if matches!(query, std::collections::hash_map::Entry::Vacant(..)) {
                    query.or_insert(());
                    for &child in &graph.nodes[node_idx].all_deps {
                        visit(visited, graph, passed_filters, child);
                    }
                }
            }
        }

        let mut old_to_new = FastMap::new();
        let mut nodes = Vec::new();
        let mut interner_by_pkgid = SortedMap::new();
        let mut topo_index = Vec::new();
        for (old_idx, package) in self.nodes.iter().enumerate() {
            if !reachable.contains_key(&old_idx) {
                continue;
            }
            let new_idx = nodes.len();
            old_to_new.insert(old_idx, new_idx);
            nodes.push(PackageNode {
                package_id: package.package_id,
                name: package.name,
                version: package.version.clone(),
                normal_deps: vec![],
                build_deps: vec![],
                dev_deps: vec![],
                normal_and_build_deps: vec![],
                all_deps: vec![],
                reverse_deps: SortedSet::new(),
                is_workspace_member: package.is_workspace_member,
                is_third_party: package.is_third_party,
                is_root: package.is_root,
                is_dev_only: package.is_dev_only,
            });
            interner_by_pkgid.insert(package.package_id, new_idx);
        }
        for old_idx in &self.topo_index {
            if let Some(&new_idx) = old_to_new.get(old_idx) {
                topo_index.push(new_idx);
            }
        }
        for (old_idx, old_package) in self.nodes.iter().enumerate() {
            if let Some(&new_idx) = old_to_new.get(&old_idx) {
                let new_package = &mut nodes[new_idx];
                for old_dep in &old_package.normal_deps {
                    if let Some(&new_dep) = old_to_new.get(old_dep) {
                        new_package.normal_deps.push(new_dep);
                    }
                }
                for old_dep in &old_package.build_deps {
                    if let Some(&new_dep) = old_to_new.get(old_dep) {
                        new_package.build_deps.push(new_dep);
                    }
                }
                for old_dep in &old_package.dev_deps {
                    if let Some(&new_dep) = old_to_new.get(old_dep) {
                        new_package.dev_deps.push(new_dep);
                    }
                }
                for old_dep in &old_package.normal_and_build_deps {
                    if let Some(&new_dep) = old_to_new.get(old_dep) {
                        new_package.normal_and_build_deps.push(new_dep);
                    }
                }
                for old_dep in &old_package.all_deps {
                    if let Some(&new_dep) = old_to_new.get(old_dep) {
                        new_package.all_deps.push(new_dep);
                    }
                }
                for old_dep in &old_package.reverse_deps {
                    if let Some(&new_dep) = old_to_new.get(old_dep) {
                        new_package.reverse_deps.insert(new_dep);
                    }
                }
            }
        }

        Self {
            nodes,
            interner_by_pkgid,
            topo_index,
        }
    }

    pub fn print_mermaid(
        &self,
        out: &Arc<dyn Out>,
        sub_args: &DumpGraphArgs,
    ) -> Result<(), std::io::Error> {
        use crate::DumpGraphDepth::*;
        let depth = sub_args.depth;

        let mut visible_nodes = SortedSet::new();
        let mut nodes_with_children = SortedSet::new();
        let mut shown = SortedSet::new();

        for (idx, package) in self.nodes.iter().enumerate() {
            if (package.is_root && depth >= Roots)
                || (package.is_workspace_member && depth >= Workspace)
                || (!package.is_third_party && depth >= FirstParty)
                || depth >= Full
            {
                visible_nodes.insert(idx);
                nodes_with_children.insert(idx);

                if depth >= FirstPartyAndDirects {
                    for &dep in &package.all_deps {
                        visible_nodes.insert(dep);
                    }
                }
            }
        }

        writeln!(out, "graph LR");

        writeln!(out, "    subgraph roots");
        for &idx in &visible_nodes {
            let package = &self.nodes[idx];
            if package.is_root && shown.insert(idx) {
                writeln!(
                    out,
                    "        node{idx}{{{}:{}}}",
                    package.name, package.version
                );
            }
        }
        writeln!(out, "    end");

        writeln!(out, "    subgraph workspace-members");
        for &idx in &visible_nodes {
            let package = &self.nodes[idx];
            if package.is_workspace_member && shown.insert(idx) {
                writeln!(
                    out,
                    "        node{idx}[/{}:{}/]",
                    package.name, package.version
                );
            }
        }
        writeln!(out, "    end");

        writeln!(out, "    subgraph first-party");
        for &idx in &visible_nodes {
            let package = &self.nodes[idx];
            if !package.is_third_party && shown.insert(idx) {
                writeln!(
                    out,
                    "        node{idx}[{}:{}]",
                    package.name, package.version
                );
            }
        }
        writeln!(out, "    end");

        writeln!(out, "    subgraph third-party");
        for &idx in &visible_nodes {
            let package = &self.nodes[idx];
            if shown.insert(idx) {
                writeln!(
                    out,
                    "        node{idx}({}:{})",
                    package.name, package.version
                );
            }
        }
        writeln!(out, "    end");

        for &idx in &nodes_with_children {
            let package = &self.nodes[idx];
            for &dep_idx in &package.all_deps {
                if visible_nodes.contains(&dep_idx) {
                    writeln!(out, "    node{idx} --> node{dep_idx}");
                }
            }
        }

        Ok(())
    }
}

pub fn resolve<'a>(
    metadata: &'a Metadata,
    filter_graph: Option<&Vec<GraphFilter>>,
    store: &Store,
) -> ResolveReport<'a> {
    // A large part of our algorithm is unioning and intersecting criteria, so we map all
    // the criteria into indexed boolean sets (*whispers* an integer with lots of bits).
    let graph = DepGraph::new(metadata, filter_graph, Some(&store.config.policy));
    // trace!("built DepGraph: {:#?}", graph);
    trace!("built DepGraph!");

    let criteria_mapper = CriteriaMapper::new(&store.audits.criteria);
    trace!("built CriteriaMapper!");

    let requirements = resolve_requirements(&graph, &store.config.policy, &criteria_mapper);

    let (results, conclusion) = resolve_audits(&graph, store, &criteria_mapper, &requirements);

    ResolveReport {
        graph,
        criteria_mapper,
        results,
        conclusion,
    }
}

fn resolve_requirements(
    graph: &DepGraph<'_>,
    policy: &Policy,
    criteria_mapper: &CriteriaMapper,
) -> Vec<CriteriaSet> {
    let _resolve_requirements = trace_span!("resolve_requirements").entered();

    let mut requirements = vec![criteria_mapper.no_criteria(); graph.nodes.len()];

    // For any packages which have dev-dependencies, apply policy-specified
    // dependency-criteria or dev-criteria to those dependencies.
    for package in &graph.nodes {
        if package.dev_deps.is_empty() {
            continue;
        }

        let policy = policy.get(package.name, &package.version);
        let dev_criteria = if let Some(c) = policy.and_then(|p| p.dev_criteria.as_ref()) {
            criteria_mapper.criteria_from_list(c)
        } else {
            criteria_mapper.criteria_from_list([format::DEFAULT_POLICY_DEV_CRITERIA])
        };

        for &depidx in &package.dev_deps {
            let dep_package = &graph.nodes[depidx];
            let dependency_criteria = policy
                .and_then(|policy| policy.dependency_criteria.get(dep_package.name))
                .map(|criteria| criteria_mapper.criteria_from_list(criteria));
            requirements[depidx]
                .unioned_with(dependency_criteria.as_ref().unwrap_or(&dev_criteria));
        }
    }

    // Walk the topo graph in reverse, so that we visit each package before any
    // dependencies.
    for &pkgidx in graph.topo_index.iter().rev() {
        let package = &graph.nodes[pkgidx];
        let policy = policy.get(package.name, &package.version);

        if let Some(c) = policy.and_then(|p| p.criteria.as_ref()) {
            // If we specify a policy on ourselves, override any requirements we've
            // had placed on us by reverse-dependencies.
            requirements[pkgidx] = criteria_mapper.criteria_from_list(c);
        } else if package.is_root {
            // If this is a root crate, it will require at least
            // `DEFAULT_POLICY_CRITERIA` by default, unless overridden.
            requirements[pkgidx].unioned_with(
                &criteria_mapper.criteria_from_list([format::DEFAULT_POLICY_CRITERIA]),
            );
        }
        let normal_criteria = requirements[pkgidx].clone();

        // For each dependency, elaborate the dependency criteria from the configured policy and add it to the dependency requirements.
        for &depidx in &package.normal_and_build_deps {
            let dep_package = &graph.nodes[depidx];
            let dependency_criteria = policy
                .and_then(|policy| policy.dependency_criteria.get(dep_package.name))
                .map(|criteria| criteria_mapper.criteria_from_list(criteria));
            requirements[depidx]
                .unioned_with(dependency_criteria.as_ref().unwrap_or(&normal_criteria));
        }
    }

    requirements
}

fn resolve_audits(
    graph: &DepGraph<'_>,
    store: &Store,
    criteria_mapper: &CriteriaMapper,
    requirements: &[CriteriaSet],
) -> (Vec<Option<ResolveResult>>, Conclusion) {
    let _resolve_audits = trace_span!("resolve_audits").entered();
    let mut violations = Vec::new();
    let mut failures = Vec::new();
    let mut vetted_with_exemptions = Vec::new();
    let mut vetted_partially = Vec::new();
    let mut vetted_fully = Vec::new();
    let results: Vec<_> = requirements
        .iter()
        .enumerate()
        .map(|(pkgidx, required_criteria)| {
            let package = &graph.nodes[pkgidx];
            if !package.is_third_party {
                return None; // first-party crates don't need audits
            }

            let audit_graph = AuditGraph::build(store, criteria_mapper, package.name, None)
                .map_err(|v| violations.push((pkgidx, v)))
                .ok()?;

            // NOTE: We currently always compute all search results even if we
            // only need those in `req_criteria` because some later passes using
            // the resolver results might need that information. We might want
            // to look into simplifying this in the future.
            let search_results: Vec<_> = (0..criteria_mapper.len())
                .map(|criteria_idx| {
                    audit_graph.search(criteria_idx, &package.version, SearchMode::PreferExemptions)
                })
                .collect();

            let mut needed_exemptions = false;
            let mut directly_exempted = false;
            let mut criteria_failures = criteria_mapper.no_criteria();
            for criteria_idx in required_criteria.indices() {
                match &search_results[criteria_idx] {
                    Ok(path) => {
                        needed_exemptions |= path
                            .iter()
                            .any(|o| matches!(o, DeltaEdgeOrigin::Exemption { .. }));
                        // Ignore `Unpublished` entries when deciding if a crate
                        // is directly exempted.
                        directly_exempted |= path.iter().all(|o| {
                            matches!(
                                o,
                                DeltaEdgeOrigin::Exemption { .. }
                                    | DeltaEdgeOrigin::Unpublished { .. }
                            )
                        });
                    }
                    Err(_) => criteria_failures.set_criteria(criteria_idx),
                }
            }

            if !criteria_failures.is_empty() {
                failures.push((pkgidx, AuditFailure { criteria_failures }));
            }

            // XXX: Callers using these fields in success should perhaps be
            // changed to instead walk the results?
            if !needed_exemptions {
                vetted_fully.push(pkgidx);
            } else if directly_exempted {
                vetted_with_exemptions.push(pkgidx);
            } else {
                vetted_partially.push(pkgidx);
            }

            Some(ResolveResult { search_results })
        })
        .collect();

    let conclusion = if !violations.is_empty() {
        Conclusion::FailForViolationConflict(FailForViolationConflict { violations })
    } else if !failures.is_empty() {
        Conclusion::FailForVet(FailForVet {
            failures,
            suggest: None,
        })
    } else {
        Conclusion::Success(Success {
            vetted_with_exemptions,
            vetted_partially,
            vetted_fully,
        })
    };

    (results, conclusion)
}

impl<'a> AuditGraph<'a> {
    /// Given the store, and a package name, builds up an audit graph. This can
    /// then be searched in order to find a specific path which satisfies a
    /// given criteria.
    pub fn build(
        store: &'a Store,
        criteria_mapper: &CriteriaMapper,
        package: PackageStr<'_>,
        extra_audits_file: Option<&'a AuditsFile>,
    ) -> Result<Self, Vec<ViolationConflict>> {
        // Pre-build the namespaces for each audit so that we can take a reference
        // to each one as-needed rather than cloning the name each time.
        let foreign_namespaces: Vec<Option<ImportName>> = store
            .imported_audits()
            .keys()
            .map(|import_name| Some(import_name.clone()))
            .collect();

        // Iterator over every audits file, including imported audits.
        let all_audits_files = store
            .imported_audits()
            .values()
            .enumerate()
            .map(|(import_index, audits_file)| {
                (
                    Some(import_index),
                    &foreign_namespaces[import_index],
                    audits_file,
                )
            })
            .chain([(None, &None, &store.audits)])
            .chain(
                // Consider extra audits as local for now - we don't care about
                // how the audits from it are prioritized.
                extra_audits_file
                    .iter()
                    .map(|&audits_file| (None, &None, audits_file)),
            );

        // Iterator over every normal audit.
        let all_audits =
            all_audits_files
                .clone()
                .flat_map(|(import_index, namespace, audits_file)| {
                    audits_file
                        .audits
                        .get(package)
                        .map(|v| &v[..])
                        .unwrap_or(&[])
                        .iter()
                        .enumerate()
                        .map(move |(audit_index, audit)| {
                            (
                                namespace,
                                match import_index {
                                    Some(import_index) => DeltaEdgeOrigin::ImportedAudit {
                                        import_index,
                                        audit_index,
                                    },
                                    None => DeltaEdgeOrigin::StoredLocalAudit { audit_index },
                                },
                                audit,
                            )
                        })
                });

        // Iterator over every wildcard audit.
        let all_wildcard_audits =
            all_audits_files
                .clone()
                .flat_map(|(import_index, namespace, audits_file)| {
                    audits_file
                        .wildcard_audits
                        .get(package)
                        .map(|v| &v[..])
                        .unwrap_or(&[])
                        .iter()
                        .enumerate()
                        .map(move |(audit_index, audit)| {
                            (namespace, import_index, audit_index, audit)
                        })
                });

        // Iterator over every trusted entry.
        let trusteds = store
            .audits
            .trusted
            .get(package)
            .map(|v| &v[..])
            .unwrap_or(&[]);

        let publishers = store
            .publishers()
            .get(package)
            .map(|v| &v[..])
            .unwrap_or(&[]);

        let unpublished = store
            .unpublished()
            .get(package)
            .map(|v| &v[..])
            .unwrap_or(&[]);

        let exemptions = store.config.exemptions.get(package);

        let mut forward_audits = DirectedAuditGraph::new();
        let mut backward_audits = DirectedAuditGraph::new();
        let mut violation_nodes = Vec::new();

        // Collect up all the deltas, and their criteria
        for (namespace, origin, entry) in all_audits.clone() {
            // For uniformity, model a Full Audit as `None -> x.y.z`
            let (from_ver, to_ver) = match &entry.kind {
                AuditKind::Full { version } => (None, version),
                AuditKind::Delta { from, to } => (Some(from), to),
                AuditKind::Violation { .. } => {
                    violation_nodes.push((namespace.clone(), entry));
                    continue;
                }
            };

            let criteria = criteria_mapper.criteria_from_list(&entry.criteria);

            forward_audits.entry(from_ver).or_default().push(DeltaEdge {
                version: Some(to_ver),
                criteria: criteria.clone(),
                origin: origin.clone(),
                is_fresh_import: entry.is_fresh_import,
            });
            backward_audits
                .entry(Some(to_ver))
                .or_default()
                .push(DeltaEdge {
                    version: from_ver,
                    criteria,
                    origin,
                    is_fresh_import: entry.is_fresh_import,
                });
        }

        // For each published version of the crate we're aware of, check if any
        // wildcard audits apply and add full-audits to those versions if they
        // do.
        for (publisher_index, publisher) in publishers.iter().enumerate() {
            for (_, import_index, audit_index, entry) in all_wildcard_audits.clone() {
                if entry.user_id == publisher.user_id
                    && *entry.start <= publisher.when
                    && publisher.when < *entry.end
                {
                    let from_ver = None;
                    let to_ver = Some(&publisher.version);
                    let criteria = criteria_mapper.criteria_from_list(&entry.criteria);
                    let origin = DeltaEdgeOrigin::WildcardAudit {
                        import_index,
                        audit_index,
                        publisher_index,
                    };
                    let is_fresh_import = entry.is_fresh_import || publisher.is_fresh_import;

                    forward_audits.entry(from_ver).or_default().push(DeltaEdge {
                        version: to_ver,
                        criteria: criteria.clone(),
                        origin: origin.clone(),
                        is_fresh_import,
                    });
                    backward_audits.entry(to_ver).or_default().push(DeltaEdge {
                        version: from_ver,
                        criteria,
                        origin,
                        is_fresh_import,
                    });
                }
            }

            for entry in trusteds {
                if entry.user_id == publisher.user_id
                    && *entry.start <= publisher.when
                    && publisher.when < *entry.end
                {
                    let from_ver = None;
                    let to_ver = Some(&publisher.version);
                    let criteria = criteria_mapper.criteria_from_list(&entry.criteria);
                    let origin = DeltaEdgeOrigin::Trusted { publisher_index };

                    forward_audits.entry(from_ver).or_default().push(DeltaEdge {
                        version: to_ver,
                        criteria: criteria.clone(),
                        origin: origin.clone(),
                        is_fresh_import: publisher.is_fresh_import,
                    });
                    backward_audits.entry(to_ver).or_default().push(DeltaEdge {
                        version: from_ver,
                        criteria,
                        origin,
                        is_fresh_import: publisher.is_fresh_import,
                    });
                }
            }
        }

        // For each unpublished entry for the crate we're aware of, generate a delta audit for that edge.
        for (unpublished_index, unpublished) in unpublished.iter().enumerate() {
            let from_ver = Some(&unpublished.audited_as);
            let to_ver = Some(&unpublished.version);
            let criteria = criteria_mapper.all_criteria();
            let origin = DeltaEdgeOrigin::Unpublished { unpublished_index };
            let is_fresh_import = unpublished.is_fresh_import;

            forward_audits.entry(from_ver).or_default().push(DeltaEdge {
                version: to_ver,
                criteria: criteria.clone(),
                origin: origin.clone(),
                is_fresh_import,
            });
            backward_audits.entry(to_ver).or_default().push(DeltaEdge {
                version: from_ver,
                criteria,
                origin,
                is_fresh_import,
            });
        }

        // Exempted entries are equivalent to full-audits
        if let Some(alloweds) = exemptions {
            for (exemption_index, allowed) in alloweds.iter().enumerate() {
                let from_ver = None;
                let to_ver = Some(&allowed.version);
                let criteria = criteria_mapper.criteria_from_list(&allowed.criteria);
                let origin = DeltaEdgeOrigin::Exemption { exemption_index };

                // For simplicity, turn 'exemptions' entries into deltas from None.
                forward_audits.entry(from_ver).or_default().push(DeltaEdge {
                    version: to_ver,
                    criteria: criteria.clone(),
                    origin: origin.clone(),
                    is_fresh_import: false,
                });
                backward_audits.entry(to_ver).or_default().push(DeltaEdge {
                    version: from_ver,
                    criteria,
                    origin,
                    is_fresh_import: false,
                });
            }
        }

        // Reject forbidden packages (violations)
        let mut violations = Vec::new();
        for (violation_source, violation_entry) in &violation_nodes {
            // Ok this is kind of weird. We want to reject any audits which contain any of these criteria.
            // Normally we would slap all the criteria in this entry into a set and do some kind of set
            // comparison, but that's not quite right. Here are the cases we want to work:
            //
            // * violation: safe-to-deploy, audit: safe-to-deploy -- ERROR!
            // * violation: safe-to-deploy, audit: safe-to-run    -- OK!
            // * violation: safe-to-run,    audit: safe-to-deploy -- ERROR!
            // * violation: [a, b],         audit: [a, c]         -- ERROR!
            //
            // The first 3 cases are correctly handled by audit.contains(violation)
            // but the last one isn't. I think the correct solution to this is to
            // *for each individual entry in the violation* do audit.contains(violation).
            // If any of those queries trips, then it's an ERROR.
            //
            // Note that this would also more correctly handle [safe-to-deploy, safe-to-run]
            // as a violation entry because it would effectively become safe-to-run instead
            // of safe-to-deploy, which is the correct and desirable behaviour!
            //
            // So here we make a criteria set for each entry in the violation.
            let violation_criterias = violation_entry
                .criteria
                .iter()
                .map(|c| criteria_mapper.criteria_from_list([&c]))
                .collect::<Vec<_>>();
            let violation_range = if let AuditKind::Violation { violation } = &violation_entry.kind
            {
                violation
            } else {
                unreachable!("violation_entry wasn't a Violation?");
            };

            // Note if this entry conflicts with any exemptions
            if let Some(alloweds) = exemptions {
                for allowed in alloweds {
                    let audit_criteria = criteria_mapper.criteria_from_list(&allowed.criteria);
                    let has_violation = violation_criterias
                        .iter()
                        .any(|v| audit_criteria.contains(v));
                    if !has_violation {
                        continue;
                    }
                    if violation_range.matches(&allowed.version) {
                        violations.push(ViolationConflict::UnauditedConflict {
                            violation_source: violation_source.clone(),
                            violation: (*violation_entry).clone(),
                            exemptions: allowed.clone(),
                        });
                    }
                }
            }

            // Note if this entry conflicts with any audits
            for (namespace, _origin, audit) in all_audits.clone() {
                let audit_criteria = criteria_mapper.criteria_from_list(&audit.criteria);
                let has_violation = violation_criterias
                    .iter()
                    .any(|v| audit_criteria.contains(v));
                if !has_violation {
                    continue;
                }
                match &audit.kind {
                    AuditKind::Full { version, .. } => {
                        if violation_range.matches(version) {
                            violations.push(ViolationConflict::AuditConflict {
                                violation_source: violation_source.clone(),
                                violation: (*violation_entry).clone(),
                                audit_source: namespace.clone(),
                                audit: audit.clone(),
                            });
                        }
                    }
                    AuditKind::Delta { from, to, .. } => {
                        if violation_range.matches(from) || violation_range.matches(to) {
                            violations.push(ViolationConflict::AuditConflict {
                                violation_source: violation_source.clone(),
                                violation: (*violation_entry).clone(),
                                audit_source: namespace.clone(),
                                audit: audit.clone(),
                            });
                        }
                    }
                    AuditKind::Violation { .. } => {
                        // don't care
                    }
                }
            }
        }

        // If we enountered any violations, report them.
        if !violations.is_empty() {
            return Err(violations);
        }

        Ok(AuditGraph {
            forward_audits,
            backward_audits,
        })
    }

    /// Search for a path in this AuditGraph which indicates that the given
    /// version of the crate satisfies the given criteria. Returns the path used
    /// for that proof if successful, and information about the versions which
    /// could be reached from both the target and root if unsuccessful.
    pub fn search(
        &self,
        criteria_idx: usize,
        version: &VetVersion,
        mode: SearchMode,
    ) -> Result<Vec<DeltaEdgeOrigin>, SearchFailure> {
        // First, search backwards, starting from the target, as that's more
        // likely to have a limited graph to traverse.
        // This also interacts well with the search ordering from
        // search_for_path, which prefers edges closer to `None` when
        // traversing.
        search_for_path(
            &self.backward_audits,
            criteria_idx,
            Some(version),
            None,
            mode,
        )
        .map_err(|reachable_from_target| {
            assert!(
                mode != SearchMode::RegenerateExemptions,
                "RegenerateExemptions search mode cannot fail"
            );

            // The search failed, perform the search in the other direction
            // in order to also get the set of nodes reachable from the
            // root. We can `unwrap_err()` here, as we'll definitely fail.
            let reachable_from_root = search_for_path(
                &self.forward_audits,
                criteria_idx,
                None,
                Some(version),
                mode,
            )
            .unwrap_err();
            SearchFailure {
                reachable_from_root,
                reachable_from_target,
            }
        })
    }
}

/// Core algorithm used to search for a path between two versions within a
/// DirectedAuditGraph. A path with the fewest "caveats" will be used in order
/// to minimize dependence on exemptions and freshly imported audits.
fn search_for_path(
    audit_graph: &DirectedAuditGraph<'_>,
    criteria_idx: usize,
    from_version: Option<&VetVersion>,
    to_version: Option<&VetVersion>,
    mode: SearchMode,
) -> Result<Vec<DeltaEdgeOrigin>, SortedSet<Option<VetVersion>>> {
    assert!(
        mode != SearchMode::RegenerateExemptions || to_version.is_none(),
        "RegenerateExemptions requires searching towards root"
    );

    // Search for any path through the graph with edges that satisfy criteria.
    // Finding any path validates that we satisfy that criteria.
    //
    // All full-audits and exemptions have been "desugarred" to a delta from
    // None, meaning our graph now has exactly one source and one sink,
    // significantly simplifying the start and end conditions.
    //
    // Some edges have caveats which we want to avoid requiring, so we defer
    // edges with caveats to be checked later, after all edges without caveats
    // have been visited. This is done by storing work to do in a BinaryHeap,
    // sorted by the caveats which apply to each node. This means that if we
    // find a patch without using a node with caveats, it's unambiguous proof we
    // don't need edges with caveats.
    #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
    enum CaveatLevel {
        None,
        PreferredExemption,
        PreferredUnpublished,
        FreshImport,
        Exemption,
        Unpublished,
        FreshExemption,
    }

    #[derive(Debug)]
    struct Node<'a> {
        version: Option<&'a VetVersion>,
        origin_version: Option<&'a VetVersion>,
        path: Vec<DeltaEdgeOrigin>,
        caveat_level: CaveatLevel,
    }

    impl Node<'_> {
        fn key(&self) -> impl Ord + '_ {
            // Nodes are compared by caveat level. A lower caveat level makes
            // the node sort higher, as it will be stored in a max heap.
            //
            // Once we've sorted by all caveats, we sort by the version
            // (preferring lower versions), exemption origin version (preferring
            // smaller exemptions), the length of the path (preferring short
            // paths), and then the most recently added DeltaEdgeOrigin
            // (preferring more-local audits).
            //
            // NOTE: This ordering logic priorities assume `to_version == None`,
            // as we will only be searched in the other direction if the search
            // is guaranteed to fail, in which case ordering doesn't matter (as
            // we're going to visit every node).
            Reverse((
                self.caveat_level,
                self.version,
                self.exemption_origin_version(),
                self.path.len(),
                self.path.last(),
            ))
        }

        // To make better decisions when selecting exemptions, exemption edges
        // with lower origin versions are preferred over those with higher
        // origin versions. This is checked before path length, as a longer path
        // which uses a smaller exemption is generally preferred to a short one
        // which uses a full-exemption. This is ignored for other edge types.
        fn exemption_origin_version(&self) -> Option<&VetVersion> {
            if matches!(
                self.caveat_level,
                CaveatLevel::PreferredExemption
                    | CaveatLevel::Exemption
                    | CaveatLevel::FreshExemption
            ) {
                self.origin_version
            } else {
                None
            }
        }
    }
    impl<'a> PartialEq for Node<'a> {
        fn eq(&self, other: &Self) -> bool {
            self.key() == other.key()
        }
    }
    impl<'a> Eq for Node<'a> {}
    impl<'a> PartialOrd for Node<'a> {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(other))
        }
    }
    impl<'a> Ord for Node<'a> {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            self.key().cmp(&other.key())
        }
    }

    let mut queue = BinaryHeap::new();
    queue.push(Node {
        version: from_version,
        origin_version: from_version,
        path: Vec::new(),
        caveat_level: CaveatLevel::None,
    });

    let mut visited = SortedSet::new();
    while let Some(Node {
        version,
        origin_version: _,
        path,
        caveat_level,
    }) = queue.pop()
    {
        // If We've been to a version before, We're not going to get a better
        // result revisiting it, as we visit the "best" edges first.
        if !visited.insert(version) {
            continue;
        }

        // We found a path! Return a search result reflecting what we
        // discovered.
        if version == to_version {
            return Ok(path);
        }

        // Apply deltas to move along to the next layer of the search, adding it
        // to our queue.
        let edges = audit_graph.get(&version).map(|v| &v[..]).unwrap_or(&[]);
        for edge in edges {
            // We'll allow any criteria if we're regenerating exemption edges.
            let allow_any_criteria = mode == SearchMode::RegenerateExemptions
                && matches!(edge.origin, DeltaEdgeOrigin::Exemption { .. });
            if !allow_any_criteria && !edge.criteria.has_criteria(criteria_idx) {
                // This edge never would have been useful to us.
                continue;
            }
            if visited.contains(&edge.version) {
                // We've been to the target of this edge already.
                continue;
            }

            // Compute the level of caveats which are being added by the current edge
            let edge_caveat_level = match &edge.origin {
                DeltaEdgeOrigin::Exemption { .. } if mode == SearchMode::PreferExemptions => {
                    CaveatLevel::PreferredExemption
                }
                DeltaEdgeOrigin::Exemption { .. } => CaveatLevel::Exemption,
                DeltaEdgeOrigin::FreshExemption { .. } => unreachable!(),
                DeltaEdgeOrigin::Unpublished { .. } => match mode {
                    // When preferring exemptions, prefer existing unpublished
                    // entries to avoid imports.lock churn.
                    SearchMode::PreferExemptions if !edge.is_fresh_import => {
                        CaveatLevel::PreferredUnpublished
                    }
                    SearchMode::PreferExemptions => CaveatLevel::Unpublished,
                    // Otherwise, prefer fresh to avoid outdated versions.
                    _ if edge.is_fresh_import => CaveatLevel::PreferredUnpublished,
                    _ => CaveatLevel::Unpublished,
                },
                _ if edge.is_fresh_import => CaveatLevel::FreshImport,
                _ => CaveatLevel::None,
            };

            queue.push(Node {
                version: edge.version,
                origin_version: version,
                path: path.iter().cloned().chain([edge.origin.clone()]).collect(),
                caveat_level: caveat_level.max(edge_caveat_level),
            });
        }

        // If we're regenerating exemptions, add a fresh exemption edge which
        // directly leads to the root version.
        if mode == SearchMode::RegenerateExemptions {
            queue.push(Node {
                version: None,
                origin_version: version,
                path: path
                    .iter()
                    .cloned()
                    .chain([DeltaEdgeOrigin::FreshExemption {
                        version: version
                            .expect("RegenerateExemptions requires searching towards None")
                            .clone(),
                    }])
                    .collect(),
                caveat_level: caveat_level.max(CaveatLevel::FreshExemption),
            })
        }
    }

    // Complete failure, we need more audits for this package, so all that
    // matters is what nodes were reachable.
    Err(visited.into_iter().map(|v| v.cloned()).collect())
}

impl<'a> ResolveReport<'a> {
    pub fn has_errors(&self) -> bool {
        // Just check the conclusion
        !matches!(self.conclusion, Conclusion::Success(_))
    }

    pub fn _has_warnings(&self) -> bool {
        false
    }

    pub fn compute_suggest(
        &self,
        cfg: &Config,
        store: &Store,
        network: Option<&Network>,
    ) -> Result<Option<Suggest>, SuggestError> {
        let _suggest_span = trace_span!("suggest").entered();
        let fail = if let Conclusion::FailForVet(fail) = &self.conclusion {
            fail
        } else {
            // Nothing to suggest unless we failed for vet
            return Ok(None);
        };

        let cache = Cache::acquire(cfg)?;

        let warnings = RefCell::new(Vec::new());

        let mut store = store.clone_for_suggest(false);
        let registry = if let (false, OutputFormat::Human, Some(network)) = (
            cfg.cli.no_registry_suggestions,
            cfg.cli.output_format,
            network,
        ) {
            tokio::runtime::Handle::current()
                .block_on(store.fetch_registry_audits(cfg, network, &cache))
                .map_err(|error| warnings.borrow_mut().push(error.to_string()))
                .ok()
        } else {
            None
        };

        const THIS_PROJECT: &str = "this project";

        let mut trusted_publishers: FastMap<u64, SortedSet<ImportName>> = FastMap::new();
        for trusted_entry in store.audits.trusted.values().flatten() {
            trusted_publishers
                .entry(trusted_entry.user_id)
                .or_default()
                .insert(THIS_PROJECT.to_owned());
        }
        for (import_name, audits_file) in store.imported_audits() {
            for trusted_entry in audits_file.trusted.values().flatten() {
                trusted_publishers
                    .entry(trusted_entry.user_id)
                    .or_default()
                    .insert(import_name.clone());
            }
        }

        let suggest_progress =
            progress_bar("Suggesting", "relevant audits", fail.failures.len() as u64);

        let mut suggestions = tokio::runtime::Handle::current()
            .block_on(join_all(fail.failures.iter().map(
                |(failure_idx, audit_failure)| async {
                    let _guard = IncProgressOnDrop(&suggest_progress, 1);

                    let failure_idx = *failure_idx;
                    let package = &self.graph.nodes[failure_idx];
                    let result = self.results[failure_idx]
                        .as_ref()
                        .expect("failed package without ResolveResults?");

                    // Precompute some "notable" parents
                    let notable_parents: Vec<_> = self.graph.nodes[failure_idx]
                        .reverse_deps
                        .iter()
                        .map(|&parent| self.graph.nodes[parent].name.to_string())
                        .collect();

                    let Some((suggested_diff, extra_suggested_diff)) = suggest_delta(
                        &cfg.metadata,
                        network,
                        &cache,
                        package.name,
                        &package.version,
                        audit_failure
                            .criteria_failures
                            .indices()
                            .map(|criteria_idx| {
                                result.search_results[criteria_idx].as_ref().unwrap_err()
                            }),
                        &warnings,
                    )
                    .await else {
                        return vec![];
                    };

                    // Attempt to look up the publisher of the target version
                    // for the suggested diff, and also record whether the given
                    // package has a sole publisher.
                    let mut is_sole_publisher = false;
                    let publisher_id =
                        if let (Some(network), None) = (&network, &suggested_diff.to.git_rev) {
                            let versions = cache
                                .get_publishers(
                                    Some(network),
                                    package.name,
                                    [&suggested_diff.to.semver].into_iter().collect(),
                                )
                                .await
                                .unwrap_or_default();
                            let publisher_count = versions
                                .iter()
                                .flat_map(|(_, details)| &details.published_by)
                                .collect::<FastSet<_>>()
                                .len();
                            is_sole_publisher = publisher_count == 1;
                            versions
                                .into_iter()
                                .find(|(v, _)| v == &suggested_diff.to.semver)
                                .and_then(|(_, d)| d.published_by)
                        } else {
                            None
                        };

                    // Compute the trust hint, which is the information used to generate "consider
                    // cargo trust FOO" messages. There can be multiple potential hints, but we
                    // only provide the most relevant one. If the publisher of the in-use version
                    // of the crate is potentially trustworthy, we suggest that. If not (and we
                    // don't already have at least one trusted entry for this crate), we iterate
                    // over the crate releases in reverse order to see if another version was
                    // published by a potentially-trustworth author. We pick the first one of
                    // those we find, if any.
                    let trust_hint = {
                        let mut exact_version = false;
                        let id_for_hint = if publisher_id
                            .map_or(false, |i| trusted_publishers.contains_key(&i))
                        {
                            exact_version = true;
                            publisher_id
                        } else if store.audits.trusted.get(package.name).is_none() {
                            cache
                                .get_cached_publishers(package.name)
                                .iter()
                                .rev()
                                .filter_map(|(_, details)| details.published_by)
                                .find(|i| trusted_publishers.contains_key(i))
                        } else {
                            None
                        };

                        id_for_hint.map(|id| {
                            let mut trusted_by: Vec<String> = trusted_publishers
                                .get(&id)
                                .unwrap()
                                .iter()
                                .cloned()
                                .collect();
                            // If we're already trusted by this project, don't
                            // bother listing anyone else.
                            if trusted_by.iter().any(|s| s == THIS_PROJECT) {
                                trusted_by.retain(|s| s == THIS_PROJECT);
                            }
                            let publisher = cache.get_crates_user_info(id).unwrap();
                            TrustHint {
                                trusted_by,
                                publisher,
                                exact_version,
                            }
                        })
                    };

                    let publisher_login = publisher_id
                        .and_then(|user_id| cache.get_crates_user_info(user_id))
                        .map(|pi| pi.login);

                    let mut registry_suggestion: Vec<_> = join_all(registry.iter().flatten().map(
                        |(name, entry, audits)| async {
                            // Don't search for git deltas in the registry.
                            if suggested_diff.to.git_rev.is_some() {
                                return None;
                            }

                            let audit_graph = AuditGraph::build(
                                &store,
                                &self.criteria_mapper,
                                package.name,
                                Some(audits),
                            )
                            .ok()?;

                            // If we have an extra diff, only try to search for
                            // a path to the "from" version in that diff, to
                            // make the results more comparable.
                            let target_version = extra_suggested_diff
                                .as_ref()
                                .and_then(|d| d.from.as_ref())
                                .unwrap_or(&package.version);

                            let failures: Vec<_> = audit_failure
                                .criteria_failures
                                .indices()
                                .filter_map(|criteria_idx| {
                                    audit_graph
                                        .search(
                                            criteria_idx,
                                            target_version,
                                            SearchMode::PreferExemptions,
                                        )
                                        .err()
                                })
                                .collect();

                            let (registry_suggested_diff, _) = suggest_delta(
                                &cfg.metadata,
                                network,
                                &cache,
                                package.name,
                                target_version,
                                failures.iter(),
                                &warnings,
                            )
                            .await?;

                            if registry_suggested_diff.diffstat.count()
                                < suggested_diff.diffstat.count()
                            {
                                Some(RegistrySuggestion {
                                    name: name.clone(),
                                    url: entry.url.clone(),
                                    diff: registry_suggested_diff,
                                })
                            } else {
                                None
                            }
                        },
                    ))
                    .await
                    .into_iter()
                    .flatten()
                    .collect();
                    registry_suggestion.sort_by_key(|suggestion| suggestion.diff.diffstat.count());

                    extra_suggested_diff
                        .into_iter()
                        .map(|suggested_diff| SuggestItem {
                            package: failure_idx,
                            suggested_diff,
                            suggested_criteria: audit_failure.criteria_failures.clone(),
                            notable_parents: notable_parents.clone(),
                            publisher_login: None,
                            trust_hint: None,
                            is_sole_publisher: false,
                            registry_suggestion: vec![],
                        })
                        .chain([SuggestItem {
                            package: failure_idx,
                            suggested_diff,
                            suggested_criteria: audit_failure.criteria_failures.clone(),
                            notable_parents: notable_parents.clone(),
                            publisher_login,
                            trust_hint,
                            is_sole_publisher,
                            registry_suggestion,
                        }])
                        .collect()
                },
            )))
            .into_iter()
            .flatten()
            .collect::<Vec<_>>();

        // First sort by diff size (ascending), then package name, then version
        // being certified, to have stable output ordering.
        suggestions.sort_by_key(|item| {
            (
                item.suggested_diff.diffstat.count(),
                self.graph.nodes[item.package].name,
                item.suggested_diff.to.clone(),
            )
        });

        // If we have duplicate suggestions in the output, e.g. due to multiple
        // versions of the same crate requiring the same new audit, deduplicate
        // them in the output to avoid clutter.
        suggestions.dedup_by(|a, b| {
            if self.graph.nodes[a.package].name == self.graph.nodes[b.package].name
                && a.suggested_diff == b.suggested_diff
            {
                // Per the `dedup_by` documentation, if true is returned, `a`
                // will be removed. Preserve its notable parents.
                b.notable_parents.extend_from_slice(&a.notable_parents);
                true
            } else {
                false
            }
        });

        // Sort and remove any duplicate entries from `notable_parents`.
        for s in &mut suggestions {
            s.notable_parents.sort();
            s.notable_parents.dedup();
        }

        let total_lines = suggestions
            .iter()
            .map(|s| s.suggested_diff.diffstat.count())
            .sum();

        let mut suggestions_by_criteria = SortedMap::<CriteriaName, Vec<SuggestItem>>::new();
        for s in suggestions.clone().into_iter() {
            let criteria_names = self
                .criteria_mapper
                .criteria_names(&s.suggested_criteria)
                .collect::<Vec<_>>()
                .join(", ");

            suggestions_by_criteria
                .entry(criteria_names)
                .or_default()
                .push(s);
        }

        Ok(Some(Suggest {
            suggestions,
            suggestions_by_criteria,
            total_lines,
            warnings: warnings.into_inner(),
        }))
    }

    /// Given a package name and a delta to be certified, determine the set of
    /// additional criteria for that delta/version pair which would have a
    /// healing impact on the audit graph.
    ///
    /// This is more reliable than running a suggest and looking for a matching
    /// output, as it will also select criteria for non-suggested audits.
    pub fn compute_suggested_criteria(
        &self,
        package_name: PackageStr<'_>,
        from: Option<&VetVersion>,
        to: &VetVersion,
    ) -> Vec<CriteriaName> {
        let fail = if let Conclusion::FailForVet(fail) = &self.conclusion {
            fail
        } else {
            return Vec::new();
        };

        let mut criteria = self.criteria_mapper.no_criteria();

        // Make owned versions of the `Version` types, such that we can look
        // them up in search results more easily.
        let from = from.cloned();
        let to = Some(to.clone());

        // Enumerate over the recorded failures, adding any criteria for this
        // delta which would connect that package version into the audit graph.
        for (failure_idx, audit_failure) in &fail.failures {
            let package = &self.graph.nodes[*failure_idx];
            if package.name != package_name {
                continue;
            }

            let result = &self.results[*failure_idx]
                .as_ref()
                .expect("failure without ResolveResults?");
            for criteria_idx in audit_failure.criteria_failures.indices() {
                let search_result = &result.search_results[criteria_idx];
                if let Err(SearchFailure {
                    reachable_from_root,
                    reachable_from_target,
                }) = search_result
                {
                    if reachable_from_target.contains(&to) && reachable_from_root.contains(&from) {
                        criteria.set_criteria(criteria_idx);
                    }
                }
            }
        }

        self.criteria_mapper
            .criteria_names(&criteria)
            .map(str::to_owned)
            .collect()
    }

    /// Print a full human-readable report
    pub fn print_human(
        &self,
        out: &Arc<dyn Out>,
        cfg: &Config,
        suggest: Option<&Suggest>,
    ) -> Result<(), std::io::Error> {
        match &self.conclusion {
            Conclusion::Success(res) => res.print_human(out, self, cfg),
            Conclusion::FailForViolationConflict(res) => res.print_human(out, self, cfg),
            Conclusion::FailForVet(res) => res.print_human(out, self, cfg, suggest),
        }
    }

    /// Print only the suggest portion of a human-readable report
    pub fn print_suggest_human(
        &self,
        out: &Arc<dyn Out>,
        _cfg: &Config,
        suggest: Option<&Suggest>,
    ) -> Result<(), std::io::Error> {
        if let Some(suggest) = suggest {
            suggest.print_human(out, self)?;
        } else {
            // This API is only used for vet-suggest
            writeln!(out, "Nothing to suggest, you're fully audited!");
        }
        Ok(())
    }

    /// Print a full json report
    pub fn print_json(
        &self,
        out: &Arc<dyn Out>,
        suggest: Option<&Suggest>,
    ) -> Result<(), miette::Report> {
        let result = JsonReport {
            conclusion: match &self.conclusion {
                Conclusion::Success(success) => {
                    let json_package = |pkgidx: &PackageIdx| {
                        let package = &self.graph.nodes[*pkgidx];
                        JsonPackage {
                            name: package.name.to_owned(),
                            version: package.version.clone(),
                        }
                    };
                    JsonReportConclusion::Success(JsonReportSuccess {
                        vetted_fully: success.vetted_fully.iter().map(json_package).collect(),
                        vetted_partially: success
                            .vetted_partially
                            .iter()
                            .map(json_package)
                            .collect(),
                        vetted_with_exemptions: success
                            .vetted_with_exemptions
                            .iter()
                            .map(json_package)
                            .collect(),
                    })
                }
                Conclusion::FailForViolationConflict(fail) => {
                    JsonReportConclusion::FailForViolationConflict(
                        JsonReportFailForViolationConflict {
                            violations: fail
                                .violations
                                .iter()
                                .map(|(pkgidx, violations)| {
                                    let package = &self.graph.nodes[*pkgidx];
                                    let key = format!("{}:{}", package.name, package.version);
                                    (key, violations.clone())
                                })
                                .collect(),
                        },
                    )
                }
                Conclusion::FailForVet(fail) => {
                    // FIXME: How to report confidence for suggested criteria?
                    let json_suggest_item = |item: &SuggestItem| {
                        let package = &self.graph.nodes[item.package];
                        JsonSuggestItem {
                            name: package.name.to_owned(),
                            notable_parents: FormatShortList::string(item.notable_parents.clone()),
                            suggested_criteria: self
                                .criteria_mapper
                                .criteria_names(&item.suggested_criteria)
                                .map(|s| s.to_owned())
                                .collect(),
                            suggested_diff: item.suggested_diff.clone(),
                        }
                    };
                    JsonReportConclusion::FailForVet(JsonReportFailForVet {
                        failures: fail
                            .failures
                            .iter()
                            .map(|(pkgidx, audit_fail)| {
                                let package = &self.graph.nodes[*pkgidx];
                                JsonVetFailure {
                                    name: package.name.to_owned(),
                                    version: package.version.clone(),
                                    missing_criteria: self
                                        .criteria_mapper
                                        .criteria_names(&audit_fail.criteria_failures)
                                        .map(|s| s.to_owned())
                                        .collect(),
                                }
                            })
                            .collect(),
                        suggest: suggest.as_ref().map(|suggest| JsonSuggest {
                            suggestions: suggest
                                .suggestions
                                .iter()
                                .map(json_suggest_item)
                                .collect(),
                            suggest_by_criteria: suggest
                                .suggestions_by_criteria
                                .iter()
                                .map(|(criteria, items)| {
                                    (
                                        criteria.to_owned(),
                                        items.iter().map(json_suggest_item).collect::<Vec<_>>(),
                                    )
                                })
                                .collect(),
                            total_lines: suggest.total_lines,
                        }),
                    })
                }
            },
        };

        serde_json::to_writer_pretty(&**out, &result).into_diagnostic()?;

        Ok(())
    }
}

impl Success {
    pub fn print_human(
        &self,
        out: &Arc<dyn Out>,
        _report: &ResolveReport<'_>,
        _cfg: &Config,
    ) -> Result<(), std::io::Error> {
        let fully_audited_count = self.vetted_fully.len();
        let partially_audited_count: usize = self.vetted_partially.len();
        let exemptions_count = self.vetted_with_exemptions.len();

        // Figure out how many entries we're going to print
        let mut count_count = (fully_audited_count != 0) as usize
            + (partially_audited_count != 0) as usize
            + (exemptions_count != 0) as usize;

        // Print out a summary of how we succeeded
        if count_count == 0 {
            writeln!(
                out,
                "Vetting Succeeded (because you have no third-party dependencies)"
            );
        } else {
            write!(out, "Vetting Succeeded (");

            if fully_audited_count != 0 {
                write!(out, "{fully_audited_count} fully audited");
                count_count -= 1;
                if count_count > 0 {
                    write!(out, ", ");
                }
            }
            if partially_audited_count != 0 {
                write!(out, "{partially_audited_count} partially audited");
                count_count -= 1;
                if count_count > 0 {
                    write!(out, ", ");
                }
            }
            if exemptions_count != 0 {
                write!(out, "{exemptions_count} exempted");
                count_count -= 1;
                if count_count > 0 {
                    write!(out, ", ");
                }
            }

            writeln!(out, ")");
        }
        Ok(())
    }
}

impl Suggest {
    pub fn print_human(
        &self,
        out: &Arc<dyn Out>,
        report: &ResolveReport<'_>,
    ) -> Result<(), std::io::Error> {
        for (criteria, suggestions) in &self.suggestions_by_criteria {
            writeln!(out, "recommended audits for {criteria}:");

            let mut strings = suggestions
                .iter()
                .map(|item| {
                    let package = &report.graph.nodes[item.package];
                    let cmd = match &item.suggested_diff.from {
                        Some(from) => format!(
                            "cargo vet diff {} {} {}",
                            package.name, from, item.suggested_diff.to
                        ),
                        None => format!(
                            "cargo vet inspect {} {}",
                            package.name, item.suggested_diff.to
                        ),
                    };
                    let publisher = item
                        .publisher_login
                        .clone()
                        .unwrap_or_else(|| "UNKNOWN".into());
                    let parents = FormatShortList::string(item.notable_parents.clone());
                    let diffstat = match &item.suggested_diff.from {
                        Some(_) => format!("{}", item.suggested_diff.diffstat),
                        None => format!("{} lines", item.suggested_diff.diffstat.count()),
                    };
                    (cmd, publisher, parents, diffstat, item)
                })
                .collect::<Vec<_>>();

            let (h0, h1, h2, h3) = ("Command", "Publisher", "Used By", "Audit Size");
            let mut max0 = console::measure_text_width(h0);
            let mut max1 = console::measure_text_width(h1);
            let mut max2 = console::measure_text_width(h2);
            for (s0, s1, s2, ..) in &mut strings {
                // If the command is too long (happens occasionally, particularly with @git
                // version specifiers), wrap subsequent columns to the next line.
                const MAX_COMMAND_CHARS: usize = 52;
                let command_width = console::measure_text_width(s0);
                if command_width > MAX_COMMAND_CHARS {
                    s0.push('\n');
                    s0.push_str(&" ".repeat(MAX_COMMAND_CHARS + 4));
                }
                max0 = max0.max(command_width.min(MAX_COMMAND_CHARS));
                max1 = max1.max(console::measure_text_width(s1));
                max2 = max2.max(console::measure_text_width(s2));
            }

            writeln!(
                out,
                "{}",
                out.style()
                    .bold()
                    .dim()
                    .apply_to(format_args!("    {h0:max0$}  {h1:max1$}  {h2:max2$}  {h3}"))
            );
            for (s0, s1, s2, s3, item) in strings {
                let package = &report.graph.nodes[item.package];

                write!(
                    out,
                    "{}",
                    out.style()
                        .cyan()
                        .bold()
                        .apply_to(format_args!("    {s0:max0$}"))
                );
                writeln!(out, "  {s1:max1$}  {s2:max2$}  {s3}");

                let dim = out.style().dim();
                for suggestion in &item.registry_suggestion {
                    writeln!(
                        out,
                        "      {} {} {}",
                        dim.clone().apply_to("NOTE:"),
                        dim.clone()
                            .cyan()
                            .bold()
                            .apply_to(format_args!("cargo vet import {}", suggestion.name)),
                        dim.clone()
                            .apply_to(match suggestion.diff.diffstat.count() {
                                0 => "would eliminate this".to_owned(),
                                n => format!("would reduce this to a {n}-line diff"),
                            }),
                    );
                }
                if let Some(hint) = &item.trust_hint {
                    let trust = if hint.trusted_by.len() == 1 {
                        "trusts"
                    } else {
                        "trust"
                    };
                    let caveat = if !hint.exact_version {
                        ", who published another version of this crate"
                    } else {
                        ""
                    };
                    let publisher = hint.publisher.clone();
                    let trusted_by = FormatShortList::new(hint.trusted_by.clone());
                    writeln!(
                        out,
                        "      {} {}",
                        dim.clone().apply_to(format_args!(
                            "NOTE: {trusted_by} {trust} {publisher}{caveat} - consider",
                        )),
                        if item.is_sole_publisher {
                            let this_cmd = format!("cargo vet trust {}", package.name);
                            let all_cmd = format!("cargo vet trust --all {}", publisher.login);
                            format!(
                                "{} {} {}",
                                dim.clone().cyan().apply_to(this_cmd),
                                dim.clone().apply_to("or"),
                                dim.clone().cyan().apply_to(all_cmd),
                            )
                        } else {
                            let cmd =
                                format!("cargo vet trust {} {}", package.name, publisher.login);
                            dim.clone().cyan().apply_to(cmd).to_string()
                        }
                    );
                }
            }

            writeln!(out);
        }

        writeln!(out, "estimated audit backlog: {} lines", self.total_lines);

        if !self.warnings.is_empty() {
            writeln!(out);
            for warning in &self.warnings {
                writeln!(
                    out,
                    "{}: {warning}",
                    out.style().yellow().apply_to("WARNING"),
                );
            }
        }

        writeln!(out);
        writeln!(out, "Use |cargo vet certify| to record the audits.");

        Ok(())
    }
}

impl FailForVet {
    fn print_human(
        &self,
        out: &Arc<dyn Out>,
        report: &ResolveReport<'_>,
        _cfg: &Config,
        suggest: Option<&Suggest>,
    ) -> Result<(), std::io::Error> {
        writeln!(out, "Vetting Failed!");
        writeln!(out);
        writeln!(out, "{} unvetted dependencies:", self.failures.len());
        let mut failures = self
            .failures
            .iter()
            .map(|(failed_idx, failure)| (&report.graph.nodes[*failed_idx], failure))
            .collect::<Vec<_>>();
        failures.sort_by_key(|(failed, _)| &failed.version);
        failures.sort_by_key(|(failed, _)| failed.name);
        for (failed_package, failed_audit) in failures {
            let criteria = report
                .criteria_mapper
                .criteria_names(&failed_audit.criteria_failures)
                .collect::<Vec<_>>();

            let label = format!("  {}:{}", failed_package.name, failed_package.version);
            writeln!(out, "{label} missing {criteria:?}");
        }

        // Suggest output generally requires hitting the network.
        if let Some(suggest) = suggest {
            writeln!(out);
            suggest.print_human(out, report)?;
        }

        Ok(())
    }
}

impl FailForViolationConflict {
    fn print_human(
        &self,
        out: &Arc<dyn Out>,
        report: &ResolveReport<'_>,
        _cfg: &Config,
    ) -> Result<(), std::io::Error> {
        writeln!(out, "Violations Found!");

        for (pkgidx, violations) in &self.violations {
            let package = &report.graph.nodes[*pkgidx];
            writeln!(out, "  {}:{}", package.name, package.version);
            for violation in violations {
                match violation {
                    ViolationConflict::UnauditedConflict {
                        violation_source,
                        violation,
                        exemptions,
                    } => {
                        write!(out, "    the ");
                        print_exemption(out, exemptions)?;
                        write!(out, "    conflicts with ");
                        print_entry(out, violation_source, violation)?;
                    }
                    ViolationConflict::AuditConflict {
                        violation_source,
                        violation,
                        audit_source,
                        audit,
                    } => {
                        write!(out, "    the ");
                        print_entry(out, audit_source, audit)?;
                        write!(out, "    conflicts with ");
                        print_entry(out, violation_source, violation)?;
                    }
                }
                writeln!(out);
            }
        }

        fn print_exemption(
            out: &Arc<dyn Out>,
            entry: &ExemptedDependency,
        ) -> Result<(), std::io::Error> {
            writeln!(out, "exemption {}", entry.version);
            writeln!(out, "      criteria: {:?}", entry.criteria);
            if let Some(notes) = &entry.notes {
                writeln!(out, "      notes: {notes}");
            }
            Ok(())
        }

        fn print_entry(
            out: &Arc<dyn Out>,
            source: &Option<ImportName>,
            entry: &AuditEntry,
        ) -> Result<(), std::io::Error> {
            match source {
                None => write!(out, "own "),
                Some(name) => write!(out, "foreign ({name}) "),
            }
            match &entry.kind {
                AuditKind::Full { version, .. } => {
                    writeln!(out, "audit {version}");
                }
                AuditKind::Delta { from, to, .. } => {
                    writeln!(out, "audit {from} -> {to}");
                }
                AuditKind::Violation { violation } => {
                    writeln!(out, "violation against {violation}");
                }
            }
            writeln!(out, "      criteria: {:?}", entry.criteria);
            for (idx, who) in entry.who.iter().enumerate() {
                if idx == 0 {
                    write!(out, "      who: {who}");
                } else {
                    write!(out, ", {who}");
                }
            }
            if !entry.who.is_empty() {
                writeln!(out);
            }
            if let Some(notes) = &entry.notes {
                writeln!(out, "      notes: {notes}");
            }
            Ok(())
        }

        Ok(())
    }
}

async fn suggest_delta(
    metadata: &cargo_metadata::Metadata,
    network: Option<&Network>,
    cache: &Cache,
    package_name: PackageStr<'_>,
    package_version: &VetVersion,
    failures: impl Iterator<Item = &SearchFailure>,
    warnings: &RefCell<Vec<String>>,
) -> Option<(DiffRecommendation, Option<DiffRecommendation>)> {
    // Fetch the set of known versions from crates.io so we know which versions
    // we'll have sources for.
    let known_versions = cache.get_versions(network, package_name).await.ok();

    // Collect up the details of how we failed
    struct Reachable<'a> {
        from_root: SortedSet<&'a Option<VetVersion>>,
        from_target: SortedSet<&'a Option<VetVersion>>,
    }
    let mut reachable = None::<Reachable<'_>>;
    for SearchFailure {
        reachable_from_root,
        reachable_from_target,
    } in failures
    {
        if let Some(Reachable {
            from_root,
            from_target,
        }) = reachable.as_mut()
        {
            // This does the right thing in the common cases, by restricting
            // ourselves to the reachable nodes that are common to all failures,
            // so that we can suggest just one change that will fix everything.
            from_root.retain(|ver| reachable_from_root.contains(ver));
            from_target.retain(|ver| reachable_from_target.contains(ver));
        } else {
            let version_has_sources = |ver: &&Option<VetVersion>| -> bool {
                // We always have sources for an empty crate.
                let Some(ver) = ver else { return true; };
                // We only have git sources for the package itself.
                if ver.git_rev.is_some() {
                    return ver == package_version;
                }
                // We have sources if the version has been published to crates.io.
                //
                // For testing fallbacks, assume we always have sources if the
                // index is unavailable.
                known_versions
                    .as_ref()
                    .map_or(true, |versions| versions.contains(&ver.semver))
            };
            reachable = Some(Reachable {
                from_root: reachable_from_root
                    .iter()
                    .filter(version_has_sources)
                    .collect(),
                from_target: reachable_from_target
                    .iter()
                    .filter(version_has_sources)
                    .collect(),
            });
        }
    }

    let Some(Reachable { from_root, from_target }) = &mut reachable else {
        // Nothing failed, return a dummy suggestion for an empty diff.
        return Some((
            DiffRecommendation {
                from: Some(package_version.clone()),
                to: package_version.clone(),
                diffstat: DiffStat { insertions: 0, deletions: 0, files_changed: 0 },
            },
            None,
        ));
    };

    // If we have a git revision, we want to ensure the nearest published
    // version has been audited before we suggest an audit for the git revision
    // itself.
    let published_version;
    let mut extra_delta = None;
    if package_version.git_rev.is_some() {
        // Find the largest published revision with an equal or lower semver
        // than the git revision. This will be the published version we
        // encourage auditing first.
        let closest_below = if let Some(known_versions) = &known_versions {
            known_versions
                .iter()
                .filter(|&v| v <= &package_version.semver)
                .max()
        } else {
            // For testing fallbacks, assume the bare version has been published
            // to crates.io.
            Some(&package_version.semver)
        };
        published_version = closest_below.map(|semver| VetVersion {
            semver: semver.clone(),
            git_rev: None,
        });
        // If the closest published version is not already audited, replace the
        // target version with `published_version` in the reachable from target
        // set, ensuring that a delta to that version is suggested rather than a
        // full audit for the git revision.
        if !from_root.contains(&published_version) {
            from_target.remove(&Some(package_version.clone()));
            if from_target.insert(&published_version) {
                extra_delta = Some(Delta {
                    from: published_version.clone(),
                    to: package_version.clone(),
                });
            }
        }
    }

    // Now suggest solutions of those failures
    let mut candidates = Vec::new();
    for &dest in &*from_target {
        let closest_above = from_root.range::<&Option<VetVersion>, _>(dest..).next();
        let closest_below = from_root
            .range::<&Option<VetVersion>, _>(..dest)
            .next_back();

        for &closest in closest_below.into_iter().chain(closest_above) {
            candidates.push(Delta {
                from: closest.clone(),
                to: dest.clone().unwrap(),
            });
        }
    }

    let do_fetch_and_diffstat = |delta| async move {
        match cache
            .fetch_and_diffstat_package(metadata, network, package_name, &delta)
            .await
        {
            Ok(diffstat) => Some(DiffRecommendation {
                diffstat,
                from: delta.from.clone(),
                to: delta.to.clone(),
            }),
            Err(err) => {
                // We don't want to actually error out completely here,
                // as other packages might still successfully diff!
                warnings
                    .borrow_mut()
                    .push(format!("error diffing {}:{}: {}", package_name, delta, err));
                None
            }
        }
    };

    let diffstats = join_all(candidates.into_iter().map(do_fetch_and_diffstat)).await;

    // If we need an "extra delta" due to a git revision, also get the diffstat
    // for that entry.
    let extra_diffstat = if let Some(delta) = extra_delta {
        do_fetch_and_diffstat(delta).await
    } else {
        None
    };

    let recommendation = diffstats
        .into_iter()
        .flatten()
        .min_by_key(|diff| diff.diffstat.count())?;

    Some((recommendation, extra_diffstat))
}

/// Resolve which entries in the store and imports.lock are required to
/// successfully audit this package. May return `None` if the package cannot
/// successfully vet given the restrictions placed upon it.
///
/// NOTE: A package which does not exist in the dependency will return the empty
/// set, as it does not have any audit requirements.
///
/// [`SearchMode`] controls how edges are selected when searching for paths.
#[tracing::instrument(skip(graph, criteria_mapper, requirements, store))]
fn resolve_package_required_entries(
    graph: &DepGraph<'_>,
    criteria_mapper: &CriteriaMapper,
    requirements: &[CriteriaSet],
    store: &Store,
    package_name: PackageStr<'_>,
    search_mode: SearchMode,
) -> Option<SortedMap<RequiredEntry, CriteriaSet>> {
    assert_eq!(graph.nodes.len(), requirements.len());

    // Collect the list of third-party packages with the given name, along with
    // their requirements.
    let packages: Vec<_> = graph
        .nodes
        .iter()
        .zip(requirements)
        .filter(|(package, _)| package.name == package_name && package.is_third_party)
        .collect();

    // If there are no third-party packages with the name, we definitely don't
    // need any entries.
    if packages.is_empty() {
        return Some(SortedMap::new());
    }

    let Ok(audit_graph) = AuditGraph::build(store, criteria_mapper, package_name, None) else {
        // There were violations when building the audit graph, return `None` to
        // indicate that this package is failing.
        return None;
    };

    let mut required_entries = SortedMap::new();
    for &(package, reqs) in &packages {
        // Do the minimal set of searches to validate that the required criteria
        // are matched.
        for criteria_idx in criteria_mapper.minimal_indices(reqs) {
            let Ok(path) = audit_graph.search(criteria_idx, &package.version, search_mode) else {
                // This package failed to vet, return `None`.
                return None;
            };

            let mut add_entry = |entry: RequiredEntry| {
                required_entries
                    .entry(entry)
                    .or_insert_with(|| criteria_mapper.no_criteria())
                    .set_criteria(criteria_idx);
            };

            for origin in path {
                match origin {
                    DeltaEdgeOrigin::Exemption { exemption_index } => {
                        add_entry(RequiredEntry::Exemption { exemption_index });
                    }
                    DeltaEdgeOrigin::FreshExemption { version } => {
                        add_entry(RequiredEntry::FreshExemption { version });
                    }
                    DeltaEdgeOrigin::ImportedAudit {
                        import_index,
                        audit_index,
                    } => {
                        add_entry(RequiredEntry::Audit {
                            import_index,
                            audit_index,
                        });
                    }
                    DeltaEdgeOrigin::WildcardAudit {
                        import_index,
                        audit_index,
                        publisher_index,
                    } => {
                        if let Some(import_index) = import_index {
                            add_entry(RequiredEntry::WildcardAudit {
                                import_index,
                                audit_index,
                            })
                        }
                        add_entry(RequiredEntry::Publisher { publisher_index })
                    }
                    DeltaEdgeOrigin::Trusted { publisher_index } => {
                        add_entry(RequiredEntry::Publisher { publisher_index })
                    }
                    DeltaEdgeOrigin::Unpublished { unpublished_index } => {
                        add_entry(RequiredEntry::Unpublished { unpublished_index })
                    }
                    DeltaEdgeOrigin::StoredLocalAudit { .. } => {}
                }
            }
        }
        continue;
    }

    Some(required_entries)
}

/// Per-package options to control store pruning.
#[derive(Copy, Clone)]
pub struct UpdateMode {
    pub search_mode: SearchMode,
    pub prune_exemptions: bool,
    pub prune_imports: bool,
}

/// Refresh the state of the store, importing required audits, and optionally
/// pruning unnecessary exemptions and/or imports.
pub fn update_store(
    cfg: &Config,
    store: &mut Store,
    mode: impl FnMut(PackageStr<'_>) -> UpdateMode,
) {
    let (new_imports, new_exemptions) = get_store_updates(cfg, store, mode);

    // Update the store to reflect the new imports and exemptions files.
    store.imports = new_imports;
    store.config.exemptions = new_exemptions;
}

/// The non-mutating core of `update_store` for use in non-mutating situations.
pub(crate) fn get_store_updates(
    cfg: &Config,
    store: &Store,
    mut mode: impl FnMut(PackageStr<'_>) -> UpdateMode,
) -> (ImportsFile, SortedMap<PackageName, Vec<ExemptedDependency>>) {
    // Compute the set of required entries from the store for all packages in
    // the dependency graph.
    let graph = DepGraph::new(
        &cfg.metadata,
        cfg.cli.filter_graph.as_ref(),
        Some(&store.config.policy),
    );
    let criteria_mapper = CriteriaMapper::new(&store.audits.criteria);
    let requirements = resolve_requirements(&graph, &store.config.policy, &criteria_mapper);

    let mut required_entries = SortedMap::new();
    for package in &graph.nodes {
        required_entries.entry(package.name).or_insert_with(|| {
            resolve_package_required_entries(
                &graph,
                &criteria_mapper,
                &requirements,
                store,
                package.name,
                mode(package.name).search_mode,
            )
        });
    }

    // Dummy value to use if a package isn't found in `required_entries` - no
    // edges will be required.
    let no_required_entries = Some(SortedMap::new());

    let mut new_imports = ImportsFile {
        unpublished: SortedMap::new(),
        publisher: SortedMap::new(),
        audits: SortedMap::new(),
    };

    // Determine which live imports to keep in the imports.lock file.
    for (import_index, (import_name, live_audits_file)) in
        store.imported_audits().iter().enumerate()
    {
        let new_audits_file = AuditsFile {
            criteria: live_audits_file.criteria.clone(),

            wildcard_audits: live_audits_file
                .wildcard_audits
                .iter()
                .map(|(pkgname, wildcard_audits)| {
                    let prune_imports = mode(&pkgname[..]).prune_imports;
                    let required_entries = required_entries
                        .get(&pkgname[..])
                        .unwrap_or(&no_required_entries);
                    (
                        pkgname,
                        wildcard_audits
                            .iter()
                            .enumerate()
                            .filter(|&(audit_index, entry)| {
                                // Keep existing if we're not pruning imports.
                                if !prune_imports && !entry.is_fresh_import {
                                    return true;
                                }

                                if let Some(required_entries) = required_entries {
                                    required_entries.contains_key(&RequiredEntry::WildcardAudit {
                                        import_index,
                                        audit_index,
                                    })
                                } else {
                                    !entry.is_fresh_import
                                }
                            })
                            .map(|(_, entry)| WildcardEntry {
                                is_fresh_import: false,
                                ..entry.clone()
                            })
                            .collect::<Vec<_>>(),
                    )
                })
                .filter(|(_, l)| !l.is_empty())
                .map(|(n, mut l)| {
                    l.sort();
                    (n.clone(), l)
                })
                .collect(),

            audits: live_audits_file
                .audits
                .iter()
                .map(|(pkgname, audits)| {
                    let prune_imports = mode(&pkgname[..]).prune_imports;
                    let (uses_package, required_entries) = match required_entries.get(&pkgname[..])
                    {
                        Some(e) => (true, e),
                        None => (false, &no_required_entries),
                    };
                    (
                        pkgname,
                        audits
                            .iter()
                            .enumerate()
                            .filter(|&(audit_index, entry)| {
                                // Keep existing if we're not pruning imports.
                                if !prune_imports && !entry.is_fresh_import {
                                    return true;
                                }

                                // Keep violations if the package is used in the graph.
                                if matches!(entry.kind, AuditKind::Violation { .. }) {
                                    return uses_package;
                                }

                                if let Some(required_entries) = required_entries {
                                    required_entries.contains_key(&RequiredEntry::Audit {
                                        import_index,
                                        audit_index,
                                    })
                                } else {
                                    !entry.is_fresh_import
                                }
                            })
                            .map(|(_, entry)| AuditEntry {
                                is_fresh_import: false,
                                ..entry.clone()
                            })
                            .collect::<Vec<_>>(),
                    )
                })
                .filter(|(_, l)| !l.is_empty())
                .map(|(n, mut l)| {
                    l.sort();
                    (n.clone(), l)
                })
                .collect(),

            // We never import trusted entries in imports.lock.
            trusted: SortedMap::new(),
        };
        new_imports
            .audits
            .insert(import_name.clone(), new_audits_file);
    }

    // Determine which live publisher information to keep in the imports.lock file.
    for (pkgname, publishers) in store.publishers() {
        let prune_imports = mode(&pkgname[..]).prune_imports;
        let required_entries = required_entries
            .get(&pkgname[..])
            .unwrap_or(&no_required_entries);
        let mut publishers: Vec<_> = publishers
            .iter()
            .enumerate()
            .filter(|&(publisher_index, entry)| {
                // Keep existing if we're not pruning imports.
                if !prune_imports && !entry.is_fresh_import {
                    return true;
                }

                if let Some(required_entries) = required_entries {
                    required_entries.contains_key(&RequiredEntry::Publisher { publisher_index })
                } else {
                    !entry.is_fresh_import
                }
            })
            .map(|(_, entry)| CratesPublisher {
                is_fresh_import: false,
                ..entry.clone()
            })
            .collect();
        publishers.sort();
        if !publishers.is_empty() {
            new_imports.publisher.insert(pkgname.clone(), publishers);
        }
    }

    // Determine which live publisher information to keep in the imports.lock file.
    for (pkgname, unpublished) in store.unpublished() {
        // Although `unpublished` entries are stored in imports.lock, they're
        // more like automatically-managed delta-exemptions than imports, so
        // we'll prune them when pruning exemptions.
        let prune_exemptions = mode(&pkgname[..]).prune_exemptions;
        let required_entries = required_entries
            .get(&pkgname[..])
            .unwrap_or(&no_required_entries);
        let mut unpublished: Vec<_> = unpublished
            .iter()
            .enumerate()
            .filter(|&(unpublished_index, entry)| {
                // Keep existing if we're not pruning exemptions.
                if !prune_exemptions && !entry.is_fresh_import {
                    return true;
                }

                if let Some(required_entries) = required_entries {
                    required_entries.contains_key(&RequiredEntry::Unpublished { unpublished_index })
                } else {
                    !entry.is_fresh_import
                }
            })
            .map(|(_, entry)| UnpublishedEntry {
                is_fresh_import: false,
                ..entry.clone()
            })
            .collect();
        unpublished.sort();
        // Clean up any duplicate Unpublished entries now that `is_fresh_import`
        // has been cleared.  This ensures that even if we end up using
        // `PreferFreshImports` when not pruning exemptions, we won't end up
        // with duplicate unpublished entries.
        unpublished.dedup();
        if !unpublished.is_empty() {
            new_imports.unpublished.insert(pkgname.clone(), unpublished);
        }
    }

    let mut all_new_exemptions = SortedMap::new();

    // Enumerate existing exemptions to check for criteria changes.
    for (pkgname, exemptions) in &store.config.exemptions {
        let prune_exemptions = mode(pkgname).prune_exemptions;
        let required_entries = required_entries
            .get(&pkgname[..])
            .unwrap_or(&no_required_entries);

        let mut new_exemptions = Vec::with_capacity(exemptions.len());
        for (exemption_index, entry) in exemptions.iter().enumerate() {
            let original_criteria = criteria_mapper.criteria_from_list(&entry.criteria);

            // Determine the set of useful criteria from required_entries,
            // falling back to `original_criteria` if it failed to audit.
            let mut useful_criteria = if let Some(required_entries) = required_entries {
                required_entries
                    .get(&RequiredEntry::Exemption { exemption_index })
                    .cloned()
                    .unwrap_or_else(|| criteria_mapper.no_criteria())
            } else {
                original_criteria.clone()
            };

            // If we're not pruning exemptions, maintain all existing criteria.
            if !prune_exemptions {
                useful_criteria.unioned_with(&original_criteria);
            }
            if useful_criteria.is_empty() {
                continue; // Skip this exemption
            }

            // If we're expanding the criteria set and are `suggest = false`, we
            // can't update the existing entry, so try adding a new one, and
            // reset the existing node to the original criteria.
            // XXX: The behaviour around suggest here is a bit jank, we might
            // want to change it.
            if !entry.suggest && !original_criteria.contains(&useful_criteria) {
                let mut extra_criteria = useful_criteria.clone();
                extra_criteria.clear_criteria(&original_criteria);
                new_exemptions.push(ExemptedDependency {
                    version: entry.version.clone(),
                    criteria: criteria_mapper
                        .criteria_names(&extra_criteria)
                        .map(|n| n.to_owned().into())
                        .collect(),
                    suggest: true,
                    notes: None,
                });
                useful_criteria = original_criteria;
            }

            // Add the exemption with the determined minimal useful criteria.
            new_exemptions.push(ExemptedDependency {
                version: entry.version.clone(),
                criteria: criteria_mapper
                    .criteria_names(&useful_criteria)
                    .map(|n| n.to_owned().into())
                    .collect(),
                suggest: entry.suggest,
                notes: entry.notes.clone(),
            });
        }
        if !new_exemptions.is_empty() {
            all_new_exemptions.insert(pkgname.clone(), new_exemptions);
        }
    }

    // Check if we have any FreshExemption entries which should be converted
    // into new exemptions.
    for (&pkgname, required_entries) in &required_entries {
        let Some(required_entries) = required_entries else { continue };

        for (entry, criteria) in required_entries.iter().rev() {
            let RequiredEntry::FreshExemption { version } = entry else {
                // FreshExemption entries always sort last in the BTreeMap, so
                // we can rely on there being no more FreshExemption entries
                // after we've seen one.
                break;
            };

            all_new_exemptions
                .entry(pkgname.to_owned())
                .or_default()
                .push(ExemptedDependency {
                    version: version.clone(),
                    criteria: criteria_mapper
                        .criteria_names(criteria)
                        .map(|n| n.to_owned().into())
                        .collect(),
                    suggest: true,
                    notes: None,
                });
        }
    }

    for exemptions in all_new_exemptions.values_mut() {
        exemptions.sort();
    }

    (new_imports, all_new_exemptions)
}