cargo-vet 0.3.0

//! 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. Validating the audits against your policies
//! 2. Blaming packages for failed policies
//! 3. Suggesting audits that would make your project pass validation
//!
//! # High-level Usage
//!
//! * [`resolve`] is the main entry point, Validating and Blaming and producing a [`ResolveReport`]
//! * [`ResolveReport::compute_suggest`] does Suggesting and produces a [`Suggest`]
//! * various methods on [`ResolveReport`] and [`Suggest`] handle printing
//!
//! # 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_third_party: for each third-party package, resolve what criteria it's audited for
//!     * compute the [`AuditGraph`] and check for violations
//!     * for each criteria, search_for_path (check if it has a connected path in the audit graph)
//!         * if it does, then we have validated that it has that criteria
//!         * if it doesn't, but only because dependency_criteria, blame those dependencies
//!         * otherwise, blame ourselves and note the reachable nodes from root and target
//!
//! * resolve_first_party: inherit third-party criteria from normal/build deps, check policies
//!     * first-parties "inherit" the intersection of all their dependencies' validated criteria
//!         * as with third-parties, this is done per-criteria so we can granularly blame deps
//!     * if there is a policy.dependency_criteria, then that dep isn't inherited normally
//!       and is instead effectively no_criteria or all_criteria based on whether it passes or not
//!
//! * resolve_self_policy: if there is a policy.criteria (or it's a root), then we check
//!   the resolved criteria against that policy
//!     * on success, we set ourselves to all_criteria
//!     * on failure, we set ourselves to no_criteria
//!     * **This is the check that matters!** Anything that fails this check is registered
//!       as a "root (policy) failure" and will be fed into the blame phase.
//!
//! * resolve_dev: same as above, but check dev-deps and dev-policies
//!     * this must be done as a second pass because dev-deps can introduce cycles. by doing
//!       all other analysis first, we can guarantee all dev-deps are fully resolved, as you
//!       cannot actually depend on the "dev" build of a package.
//!
//!
//!
//! ## Blame
//!
//! * take the "root failures" and descend back down the DepGraph as a tree, following
//!   every package's "blames" until we hit packages that blame themselves. Packages that
//!   blame themselves are "leaf failures" and are will be the basis for `suggest`
//!
//!
//!
//! ## Suggest
//!
//! * take the blame and do a huge pile of diffstats on the reachable versions
//!   (from search_for_path) to figure out which audits to recommend for which criteria

use cargo_metadata::{DependencyKind, Metadata, Node, PackageId, Version};
use core::fmt;
use futures_util::future::join_all;
use miette::IntoDiagnostic;
use serde::Serialize;
use serde_json::json;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::mem;
use std::sync::Arc;
use tracing::{error, trace, trace_span};

use crate::errors::{RegenerateExemptionsError, SuggestError};
use crate::format::{
    self, AuditKind, AuditsFile, CriteriaName, CriteriaStr, Delta, DependencyCriteria, DiffStat,
    ExemptedDependency, ImportName, PackageName, PackageStr, PolicyEntry, RemoteImport,
    SAFE_TO_DEPLOY, SAFE_TO_RUN,
};
use crate::format::{FastMap, FastSet, SortedMap, SortedSet};
use crate::network::Network;
use crate::out::{progress_bar, IncProgressOnDrop, Out};
use crate::{
    AuditEntry, Cache, Config, CriteriaEntry, DumpGraphArgs, GraphFilter, GraphFilterProperty,
    GraphFilterQuery, PackageExt, Store,
};

/// A report of the results of running `resolve`.
#[derive(Debug, Clone)]
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`][].
    pub results: Vec<ResolveResult<'a>>,

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

#[derive(Debug, Clone)]
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>,
    /// Third-party packages that needed fresh imports to be successfully vetted
    pub needed_fresh_imports: SortedSet<PackageIdx>,
}

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

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

#[allow(clippy::large_enum_variant)]
#[derive(Debug, Clone, Serialize)]
pub enum ViolationConflict {
    UnauditedConflict {
        violation_source: CriteriaNamespace,
        violation: AuditEntry,
        exemptions: ExemptedDependency,
    },
    AuditConflict {
        violation_source: CriteriaNamespace,
        violation: AuditEntry,
        audit_source: CriteriaNamespace,
        audit: AuditEntry,
    },
}

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

#[derive(Debug, Clone)]
pub struct SuggestItem {
    pub package: PackageIdx,
    pub suggested_criteria: CriteriaFailureSet,
    pub suggested_diff: DiffRecommendation,
    pub notable_parents: String,
}

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

/// Set of booleans, 64 should be Enough For Anyone (but abstracting in case not).
///
/// Note that this intentionally doesn't implement Default to allow the implementation
/// to require the CriteriaMapper to provide the count of items at construction time.
/// Which will be useful if we ever decide to give it ~infinite capacity and wrap
/// a BitSet.
#[derive(Clone)]
pub struct CriteriaSet(u64);
const MAX_CRITERIA: usize = u64::BITS as usize; // funnier this way

/// Set of criteria which failed for a given package. `confident` contains only
/// criteria which we're confident about, whereas `all` contains all criteria.
#[derive(Debug, Clone)]
pub struct CriteriaFailureSet {
    pub confident: CriteriaSet,
    pub all: CriteriaSet,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
pub enum CriteriaNamespace {
    Local,
    Foreign(ImportName),
}

/// Misc info about a Criteria that CriteriaMapper wants for some tasks.
#[derive(Debug, Clone)]
pub struct CriteriaInfo {
    /// The namespace this criteria is natively part of.
    ///
    /// Note that builtins are in [`CriteriaNamespace::Local`] but still resolve
    /// in foreign namespaces. This is effectively done by having a copy of those
    /// criteria in every namespace that is auto-mapped into local. Because mapping
    /// is bijective, the foreign copies are pointless and everyone just uses the
    /// same local instance happily.
    ///
    /// The automapping is resolved by [`CriteriaMapper::index`].
    pub namespace: CriteriaNamespace,
    /// The name of the criteria with namespacing modifiers applied.
    ///
    /// e.g. a local criteria will show up as `some-criteria` but a foreign
    /// one will appear as `foreign::some-criteria`. This string is intended
    /// for user-facing messages to avoid ambiguities (and make it easier to
    /// tell if we mess up and leak a foreign criteria where it shouldn't be).
    pub namespaced_name: String,

    /// The raw name of the criteria, as it would appear if it was local.
    ///
    /// FIXME: arguably we don't need to hold onto this, but it's annoying
    /// to factor out and the overhead is completely trivial.
    raw_name: CriteriaName,
    /// FIXME: we don't actually need/want to store this but it's annoying
    /// to factor out and honestly the overhead is completely trivial.
    implies: Vec<CriteriaName>,
}

/// A processed version of config.toml's criteria definitions, for mapping
/// lists of criteria names to CriteriaSets.
#[derive(Debug, Clone)]
pub struct CriteriaMapper {
    /// All the criteria in their raw form
    pub list: Vec<CriteriaInfo>,
    /// name -> index in all lists
    pub index: FastMap<CriteriaNamespace, FastMap<CriteriaName, usize>>,
    /// The transitive closure of all criteria implied by each criteria (including self)
    pub implied_criteria: Vec<CriteriaSet>,
}

/// 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: &'a Version,
    /// 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<'a> {
    /// The set of criteria we validated for this package.
    pub validated_criteria: CriteriaSet,
    /// Individual search results for each criteria.
    pub search_results: Vec<SearchResult<'a>>,
    /// Whether there was an exemption for this exact version.
    pub directly_exempted: bool,
}

pub type PolicyFailures = SortedMap<PackageIdx, CriteriaSet>;
/// (FailedPackage, Failures, is_dev)
pub type RootFailures = Vec<(PackageIdx, PolicyFailures, bool)>;

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

/// The possible results of search for an audit chain for a Criteria
#[derive(Debug, Clone)]
pub enum SearchResult<'a> {
    /// We found a path, criteria validated.
    Connected {
        /// Caveats which were required to build the audit chain for this
        /// Criteria.
        caveats: Caveats,
    },
    /// We failed to find a *proper* path, criteria not valid, but adding in failing
    /// edges caused by our dependencies not meeting criteria created a connection!
    /// If you fix these dependencies then we should validate this criteria!
    PossiblyConnected {
        /// The dependencies that failed on some edges (blame them).
        /// This is currently overbroad in corner cases where there are two possible
        /// paths blocked by two different dependencies and so only fixing one would
        /// actually be sufficient, but, whatever.
        failed_deps: SortedMap<PackageIdx, CriteriaSet>,
    },
    /// We failed to find any path, criteria not valid.
    Disconnected {
        /// Nodes we could reach from "root"
        reachable_from_root: SortedSet<Option<&'a Version>>,
        /// Nodes we could reach from the "target"
        ///
        /// We will only ever fill in the other one, but on failure we run the algorithm
        /// in reverse and will merge that result into this value.
        reachable_from_target: SortedSet<Option<&'a Version>>,
    },
}

// NOTE: There's probably a more efficient representation for these in the
// general case.
/// Caveats which apply to the results of an audit.
#[derive(Debug, Clone, Default)]
pub struct Caveats {
    /// The set of packages which required exemptions in order to successfully
    /// audit.
    pub needed_exemptions: SortedSet<PackageIdx>,

    /// The set of packages which required fresh imports in order to
    /// successfully audit.
    pub needed_fresh_imports: SortedSet<PackageIdx>,
}

impl Caveats {
    /// Union the given caveat set with this set of caveats, mutating `self`.
    fn add(&mut self, other: &Caveats) {
        self.needed_exemptions.extend(&other.needed_exemptions);
        self.needed_fresh_imports
            .extend(&other.needed_fresh_imports);
    }
}

/// 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`.
pub type AuditGraph<'a> = SortedMap<Option<&'a Version>, Vec<DeltaEdge<'a>>>;

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum DeltaEdgeOrigin {
    /// This edge represents an audit from the store, either within audits.toml
    /// or within the cached imports.lock file. These edges will be tried first.
    StoredAudit,
    /// This edge represents an exemption. These edges will be tried after
    /// stored audits, but before freshly-imported audits have been attempted.
    Exemption,
    /// This edge represents an imported audit from a peer which is only present
    /// on the remote server, and not present in the cached imports.lock file.
    /// These edges will be tried after all locally-available audits have been
    /// attempted.
    FreshImportedAudit,
}

/// 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)]
pub struct DeltaEdge<'a> {
    /// The version this edge goes to.
    version: Option<&'a Version>,
    /// The criteria that this edge is valid for.
    criteria: CriteriaSet,
    /// Requirements that dependencies must satisfy for the edge to be valid.
    /// If a dependency isn't mentioned, then it defaults to `criteria`.
    dependency_criteria: FastMap<PackageStr<'a>, CriteriaSet>,
    /// The origin of this edge. See `DeltaEdgeOrigin`'s documentation for more
    /// details.
    origin: DeltaEdgeOrigin,
}

const NUM_BUILTINS: usize = 2;
fn builtin_criteria() -> [CriteriaInfo; NUM_BUILTINS] {
    [
        CriteriaInfo {
            namespace: CriteriaNamespace::Local,
            raw_name: SAFE_TO_RUN.to_string(),
            namespaced_name: SAFE_TO_RUN.to_string(),
            implies: vec![],
        },
        CriteriaInfo {
            namespace: CriteriaNamespace::Local,
            raw_name: SAFE_TO_DEPLOY.to_string(),
            namespaced_name: SAFE_TO_DEPLOY.to_string(),
            implies: vec!["safe-to-run".to_string()],
        },
    ]
}

impl CriteriaMapper {
    pub fn new(
        criteria: &SortedMap<CriteriaName, CriteriaEntry>,
        imports: &SortedMap<ImportName, AuditsFile>,
        mappings: &SortedMap<ImportName, RemoteImport>,
    ) -> CriteriaMapper {
        // First, build a list of all our criteria
        let locals = criteria.iter().map(|(k, v)| CriteriaInfo {
            namespace: CriteriaNamespace::Local,
            raw_name: k.clone(),
            namespaced_name: k.clone(),
            implies: v.implies.iter().map(|s| s.to_string()).collect::<Vec<_>>(),
        });
        let builtins = builtin_criteria();
        let foreigns = imports.iter().flat_map(|(import, audit_file)| {
            audit_file.criteria.iter().map(move |(k, v)| CriteriaInfo {
                namespace: CriteriaNamespace::Foreign(import.clone()),
                raw_name: k.clone(),
                namespaced_name: format!("{}::{}", import, k),
                implies: v.implies.iter().map(|s| s.to_string()).collect::<Vec<_>>(),
            })
        });
        let list = builtins
            .into_iter()
            .chain(locals)
            .chain(foreigns)
            .collect::<Vec<_>>();
        let num_criteria = list.len();

        // Now construct an index over this list, that lets us map
        // (CriteriaNamespace, CriteriaName) => CriteriaIdx
        let mut index = FastMap::<CriteriaNamespace, FastMap<CriteriaName, usize>>::new();
        let all_import_names = mappings.iter().map(|(import_name, _)| import_name);

        // Add all the natural entries
        for (idx, info) in list.iter().enumerate() {
            let prev = index
                .entry(info.namespace.clone())
                .or_default()
                .insert(info.raw_name.clone(), idx);
            assert!(prev.is_none(), "criteria name was multiply defined???");
        }

        // Hack the builtins into every foreign namespace. Because they all use
        // the same CriteriaIdx, we can now forget that builtins are special and
        // just naturally look them up in any namespace without issue.
        for import_name in all_import_names {
            for (idx, info) in list[0..NUM_BUILTINS].iter().enumerate() {
                index
                    .entry(CriteriaNamespace::Foreign(import_name.clone()))
                    .or_default()
                    .insert(info.raw_name.clone(), idx);
            }
        }

        // Compute the graph of "implies" relationships. We will then run DFS from each
        // node to compute the transitive closure of each criteria's implications, which
        // will becomes `implies[idx]`, the value used whenever the criteria is named.
        let mut direct_implies = FastMap::<usize, CriteriaSet>::with_capacity(num_criteria);
        // Add all the edges for implies entries (and ensure there's a node for every idx)
        for (idx, info) in list.iter().enumerate() {
            let mut edges = CriteriaSet::none(num_criteria);
            for implied in &info.implies {
                let their_idx = index[&info.namespace][&**implied];
                edges.set_criteria(their_idx);
            }
            direct_implies.insert(idx, edges);
        }

        // Add all the edges for foreign mappings
        //
        // FIXME: in principle these foreign criteria can be completely eliminated
        // because they're 100% redundant with the local criteria they're getting
        // mapped to. However this results in us discarding some information that
        // conceivably could be useful for some diagnostics or other analysis.
        //
        // For now let's leave them in with an eye towards eliminating them.
        // We currently handle eliminating their redundant nature in a more "late-bound"
        // way in `CriteriaMapper::minimal_indices` and the various APIs that are
        // built on top of it (all the *_criteria_names APIs, which govern ~all output).
        for (import_name, mappings) in mappings
            .iter()
            .map(|(name, entry)| (name, &entry.criteria_map))
        {
            let foreign = CriteriaNamespace::Foreign(import_name.clone());
            let local = CriteriaNamespace::Local;
            for mapping in mappings {
                // Add a bidirectional edge between these two criteria (they are now completely equivalent)
                assert!(
                    mapping.theirs.len() == 1,
                    "criteria_map doesn't yet support multi-mapping, must be 1:1"
                );
                let our_idx = index[&local][&mapping.ours];
                let their_idx = index[&foreign][&*mapping.theirs[0]];
                direct_implies
                    .get_mut(&our_idx)
                    .unwrap()
                    .set_criteria(their_idx);
                direct_implies
                    .get_mut(&their_idx)
                    .unwrap()
                    .set_criteria(our_idx);
            }
        }

        // Now do DFS over the direct_implies graph to compute the true transitive implies closure
        let mut implied_criteria = Vec::with_capacity(num_criteria);
        for idx in 0..num_criteria {
            let mut implied = CriteriaSet::none(num_criteria);
            implied.set_criteria(idx);
            recursive_implies(&mut implied, &direct_implies, idx);
            implied_criteria.push(implied);

            fn recursive_implies(
                result: &mut CriteriaSet,
                direct_implies: &FastMap<usize, CriteriaSet>,
                cur_idx: usize,
            ) {
                for implied_idx in direct_implies[&cur_idx].indices() {
                    if result.has_criteria(implied_idx) {
                        // If we've already visited this criteria, don't do it again.
                        // This resolves all cycles (such as foreign mappings).
                        continue;
                    }
                    result.set_criteria(implied_idx);

                    // FIXME: we should detect infinite implies loops?
                    recursive_implies(result, direct_implies, implied_idx);
                }
            }
        }

        Self {
            list,
            index,
            implied_criteria,
        }
    }
    pub fn criteria_from_entry(&self, entry: &AuditEntry) -> CriteriaSet {
        self.criteria_from_namespaced_entry(&CriteriaNamespace::Local, entry)
    }
    pub fn criteria_from_namespaced_entry(
        &self,
        namespace: &CriteriaNamespace,
        entry: &AuditEntry,
    ) -> CriteriaSet {
        self.criteria_from_namespaced_list(namespace, &entry.criteria)
    }
    pub fn criteria_from_list<'b, S: AsRef<str> + 'b + ?Sized>(
        &self,
        list: impl IntoIterator<Item = &'b S>,
    ) -> CriteriaSet {
        self.criteria_from_namespaced_list(&CriteriaNamespace::Local, list)
    }
    pub fn criteria_from_namespaced_list<'b, S: AsRef<str> + 'b + ?Sized>(
        &self,
        namespace: &CriteriaNamespace,
        list: impl IntoIterator<Item = &'b S>,
    ) -> CriteriaSet {
        let mut result = self.no_criteria();
        for criteria in list {
            let idx = self.index[namespace][criteria.as_ref()];
            result.unioned_with(&self.implied_criteria[idx]);
        }
        result
    }
    pub fn set_criteria(&self, set: &mut CriteriaSet, criteria: CriteriaStr) {
        self.set_namespaced_criteria(set, &CriteriaNamespace::Local, criteria);
    }
    pub fn set_namespaced_criteria(
        &self,
        set: &mut CriteriaSet,
        namespace: &CriteriaNamespace,
        criteria: CriteriaStr,
    ) {
        set.unioned_with(&self.implied_criteria[self.index[namespace][criteria]])
    }
    pub fn clear_criteria(&self, set: &mut CriteriaFailureSet, criteria: CriteriaStr) {
        self.clear_namespaced_criteria(set, &CriteriaNamespace::Local, criteria)
    }
    pub fn clear_namespaced_criteria(
        &self,
        set: &mut CriteriaFailureSet,
        namespace: &CriteriaNamespace,
        criteria: CriteriaStr,
    ) {
        set.clear_criteria(&self.implied_criteria[self.index[namespace][criteria]])
    }
    /// An iterator over every criteria in order, with 'implies' fully applied.
    ///
    /// This includes any foreign criteria that has been eliminated as redundant.
    pub fn all_criteria_iter(&self) -> impl Iterator<Item = &CriteriaSet> {
        self.implied_criteria.iter()
    }
    /// An iterator over every **local** criteria in order, with 'implies' fully applied.
    pub fn all_local_criteria_iter(&self) -> impl Iterator<Item = &CriteriaSet> {
        // Just filter out the non-local criteria
        self.implied_criteria
            .iter()
            .enumerate()
            .filter(|(idx, _)| matches!(self.list[*idx].namespace, CriteriaNamespace::Local))
            .map(|(_, set)| set)
    }
    pub fn len(&self) -> usize {
        self.list.len()
    }
    pub fn is_empty(&self) -> bool {
        self.list.is_empty()
    }
    pub fn no_criteria(&self) -> CriteriaSet {
        CriteriaSet::none(self.len())
    }
    pub fn all_criteria(&self) -> CriteriaSet {
        CriteriaSet::_all(self.len())
    }
    pub fn no_criteria_failures(&self) -> CriteriaFailureSet {
        CriteriaFailureSet::none(self.len())
    }

    /// Like [`CriteriaSet::indices`] but uses knowledge of things like
    /// `implies` relationships to remove redundant information. For
    /// instance, if safe-to-deploy is set, we don't also yield safe-to-run.
    pub fn minimal_indices<'a>(
        &'a self,
        criteria: &'a CriteriaSet,
    ) -> impl Iterator<Item = usize> + 'a {
        criteria.indices().filter(|&cur_idx| {
            criteria.indices().all(|other_idx| {
                // Ignore our own index
                let is_identity = cur_idx == other_idx;
                // Discard this criteria if it's implied by another
                let isnt_implied = !self.implied_criteria[other_idx].has_criteria(cur_idx);
                // Unless we're local and they're foreign, then we win
                let cur_is_local = self.list[cur_idx].namespace == CriteriaNamespace::Local;
                let other_is_foreign = self.list[other_idx].namespace != CriteriaNamespace::Local;
                let is_mapping = cur_is_local && other_is_foreign;
                is_identity || isnt_implied || is_mapping
            })
        })
    }

    /// Yields all the names of the set criteria with implied members filtered out.
    pub fn criteria_names<'a>(
        &'a self,
        criteria: &'a CriteriaSet,
    ) -> impl Iterator<Item = CriteriaStr<'a>> + 'a {
        self.minimal_indices(criteria)
            .map(|idx| &*self.list[idx].namespaced_name)
    }

    pub fn all_criteria_names<'a>(
        &'a self,
        criteria: &'a CriteriaFailureSet,
    ) -> impl Iterator<Item = CriteriaStr<'a>> + 'a {
        self.criteria_names(criteria.all())
    }

    pub fn confident_criteria_names<'a>(
        &'a self,
        criteria: &'a CriteriaFailureSet,
    ) -> impl Iterator<Item = CriteriaStr<'a>> + 'a {
        self.criteria_names(criteria.confident())
    }

    pub fn unconfident_criteria_names<'a>(
        &'a self,
        criteria: &'a CriteriaFailureSet,
    ) -> impl Iterator<Item = CriteriaStr<'a>> + 'a {
        // Filter criteria present in `confident()`
        self.minimal_indices(criteria.all())
            .filter(|idx| !criteria.confident().has_criteria(*idx))
            .map(|idx| &*self.list[idx].namespaced_name)
    }
}

impl CriteriaSet {
    pub fn none(count: usize) -> Self {
        assert!(
            count <= MAX_CRITERIA,
            "{MAX_CRITERIA} was not Enough For Everyone ({count} criteria)"
        );
        CriteriaSet(0)
    }
    pub fn _all(count: usize) -> Self {
        assert!(
            count <= MAX_CRITERIA,
            "{MAX_CRITERIA} was not Enough For Everyone ({count} criteria)"
        );
        if count == MAX_CRITERIA {
            CriteriaSet(!0)
        } else {
            // Bit Magic to get 'count' 1's
            CriteriaSet((1 << count) - 1)
        }
    }
    pub fn set_criteria(&mut self, idx: usize) {
        self.0 |= 1 << idx;
    }
    pub fn clear_criteria(&mut self, other: &CriteriaSet) {
        self.0 &= !other.0;
    }
    pub fn has_criteria(&self, idx: usize) -> bool {
        (self.0 & (1 << idx)) != 0
    }
    pub fn _intersected_with(&mut self, other: &CriteriaSet) {
        self.0 &= other.0;
    }
    pub fn unioned_with(&mut self, other: &CriteriaSet) {
        self.0 |= other.0;
    }
    pub fn contains(&self, other: &CriteriaSet) -> bool {
        (self.0 & other.0) == other.0
    }
    pub fn is_empty(&self) -> bool {
        self.0 == 0
    }
    pub fn indices(&self) -> impl Iterator<Item = usize> + '_ {
        // Yield all the offsets that are set by repeatedly getting the lowest 1 and clearing it
        let mut raw = self.0;
        std::iter::from_fn(move || {
            if raw == 0 {
                None
            } else {
                let next = raw.trailing_zeros() as usize;
                raw &= !(1 << next);
                Some(next)
            }
        })
    }
    /// Clear all the bits in the set
    fn clear(&mut self) {
        self.0 = 0;
    }
}

impl fmt::Debug for CriteriaSet {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        write!(fmt, "{:08b}", self.0)
    }
}

impl CriteriaFailureSet {
    pub fn none(count: usize) -> Self {
        CriteriaFailureSet {
            confident: CriteriaSet::none(count),
            all: CriteriaSet::none(count),
        }
    }
    pub fn from(criteria: &CriteriaSet, confident: bool) -> Self {
        CriteriaFailureSet {
            confident: if confident {
                criteria.clone()
            } else {
                // Kinda jank but lets us copy the capacity without knowing it
                let mut set = criteria.clone();
                set.clear();
                set
            },
            all: criteria.clone(),
        }
    }
    pub fn set_criteria(&mut self, idx: usize, confident: bool) {
        self.all.set_criteria(idx);
        if confident {
            self.confident.set_criteria(idx);
        }
    }
    pub fn clear_criteria(&mut self, other: &CriteriaSet) {
        self.confident.clear_criteria(other);
        self.all.clear_criteria(other);
    }
    pub fn unioned_with(&mut self, other: &CriteriaFailureSet) {
        self.all.unioned_with(&other.all);
        self.confident.unioned_with(&other.confident);
    }
    pub fn contains(&self, other: &CriteriaFailureSet) -> bool {
        self.all.contains(&other.all) && self.confident.contains(&other.confident)
    }
    pub fn is_empty(&self) -> bool {
        self.all.is_empty()
    }
    pub fn is_fully_confident(&self) -> bool {
        self.confident.contains(&self.all)
    }
    pub fn is_fully_unconfident(&self) -> bool {
        self.confident.is_empty()
    }
    pub fn all(&self) -> &CriteriaSet {
        &self.all
    }
    pub fn confident(&self) -> &CriteriaSet {
        &self.confident
    }
}

impl ResolveResult<'_> {
    fn with_no_criteria(empty: CriteriaSet) -> Self {
        Self {
            validated_criteria: empty,
            search_results: vec![],
            directly_exempted: false,
        }
    }
}

impl<'a> DepGraph<'a> {
    pub fn new(
        metadata: &'a Metadata,
        filter_graph: Option<&Vec<GraphFilter>>,
        policy: Option<&SortedMap<PackageName, PolicyEntry>>,
    ) -> Self {
        let empty_override = SortedMap::new();
        let policy = policy.unwrap_or(&empty_override);
        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.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,
                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(())
    }
}

#[derive(Copy, Clone, Eq, PartialEq, Debug)]
pub enum ResolveDepth {
    Deep,
    Shallow,
}

pub fn resolve<'a>(
    metadata: &'a Metadata,
    filter_graph: Option<&Vec<GraphFilter>>,
    store: &'a Store,
    resolve_depth: ResolveDepth,
) -> 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,
        store.imported_audits(),
        &store.config.imports,
    );
    trace!("built CriteriaMapper!");

    let (results, conclusion) = resolve_core(&graph, store, &criteria_mapper, resolve_depth);

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

fn resolve_core<'a>(
    graph: &DepGraph<'a>,
    store: &'a Store,
    criteria_mapper: &CriteriaMapper,
    resolve_depth: ResolveDepth,
) -> (Vec<ResolveResult<'a>>, Conclusion) {
    let _resolve_span = trace_span!("validate").entered();

    // This uses the same indexing pattern as graph.resolve_index_by_pkgid
    let mut results =
        vec![ResolveResult::with_no_criteria(criteria_mapper.no_criteria()); graph.nodes.len()];

    let mut root_failures = RootFailures::new();
    let mut violations = SortedMap::new();
    let mut root_caveats = Caveats::default();

    // Actually vet the build graph
    for &pkgidx in &graph.topo_index {
        let package = &graph.nodes[pkgidx];

        trace!("resolving {}:{}", package.name, package.version,);

        if package.is_third_party {
            resolve_third_party(
                store,
                graph,
                criteria_mapper,
                &mut results,
                &mut violations,
                &mut root_failures,
                pkgidx,
            );
        } else {
            resolve_first_party(
                store,
                graph,
                criteria_mapper,
                &mut results,
                &mut violations,
                &mut root_failures,
                pkgidx,
            );
        }

        // Check that any policy on our resolved value is satisfied
        resolve_self_policy(
            store,
            graph,
            criteria_mapper,
            &mut results,
            &mut violations,
            &mut root_failures,
            &mut root_caveats,
            pkgidx,
        );
    }

    // Now that we've processed the "normal" graph we need to check the dev (test/bench) builds.
    // This needs to be done as a separate pass because tests can introduce apparent cycles in
    // the Cargo graph, because our X's tests can depend on Y which in turn depend on X again.
    //
    // This is fine for Cargo because the tests are a completely different build from X itself
    // so the cycle completely disappears once the graph is "desugarred" into actual build units,
    // but it's an annoying problem for us because it essentially means we cannot fully analyze
    // X in one shot. However we have a few useful insights we can leverage:
    //
    // * Nothing can "depend" on X's tests, and therefore ignoring the tests on our first pass
    //   shouldn't logically affect any other node's results. i.e. UsesX being safe-to-run
    //   does not depend on X's tests being safe-to-run. If we were to desugar X into two nodes
    //   as Cargo does, the "dev" node would always be a root, so we should treat it as such
    //   during this second pass.
    //
    // * We don't actually *care* if a node *has* tests/benches. All we care about is if
    //   the node has dev-dependencies, because that's the only thing that could change the
    //   results of the previous pass. (TODO: is this actually true? Root nodes get special
    //   default policies, so maybe all nodes that are testable should get rescanned? But
    //   also tests are expected to have weaker requirements... hmm...)
    //
    // * We will only ever test/bench a workspace member, and workspace members are always
    //   first-party packages. This means we can avoid thinking about all the complicated
    //   graph search stuff and just need to do simple one-shot analysis of our deps and
    //   check against root policies.
    for &pkgidx in &graph.topo_index {
        let package = &graph.nodes[pkgidx];
        trace!("resolving dev {}:{}", package.name, package.version,);
        if package.is_workspace_member {
            resolve_dev(
                store,
                graph,
                criteria_mapper,
                &mut results,
                &mut violations,
                &mut root_failures,
                &mut root_caveats,
                pkgidx,
            );
        } else {
            assert!(
                package.dev_deps.is_empty(),
                "{}:{} isn't a workspace member but has dev-deps!",
                package.name,
                package.version
            );
        }
    }

    // If there were violations, report that
    if !violations.is_empty() {
        return (
            results,
            Conclusion::FailForViolationConflict(FailForViolationConflict { violations }),
        );
    }
    _resolve_span.exit();
    let _blame_span = trace_span!("blame").entered();

    // There weren't any violations, so now compute the final failures by pushing blame
    // down from the roots to the leaves that caused those failures.
    let mut failures = SortedMap::<PackageIdx, AuditFailure>::new();
    visit_failures(
        graph,
        criteria_mapper,
        &results,
        &root_failures,
        resolve_depth,
        |failure, depth, own_failure| {
            if let Some(criteria_failures) = own_failure {
                trace!(
                    " {:width$}blaming: {}:{} for {:?} + {:?}",
                    "",
                    graph.nodes[failure].name,
                    graph.nodes[failure].version,
                    criteria_mapper
                        .confident_criteria_names(criteria_failures)
                        .collect::<Vec<_>>(),
                    criteria_mapper
                        .unconfident_criteria_names(criteria_failures)
                        .collect::<Vec<_>>(),
                    width = depth
                );
                failures
                    .entry(failure)
                    .or_insert_with(|| AuditFailure {
                        criteria_failures: criteria_mapper.no_criteria_failures(),
                    })
                    .criteria_failures
                    .unioned_with(criteria_failures);
            }
            Ok::<(), ()>(())
        },
    )
    .unwrap();

    // There should always be leaf failures if there were root failures!
    assert_eq!(
        root_failures.is_empty(),
        failures.is_empty(),
        "failure blaming system bugged out"
    );

    // If there are any failures, report that
    if !failures.is_empty() {
        return (
            results,
            Conclusion::FailForVet(FailForVet {
                failures,
                suggest: None,
            }),
        );
    }

    // Ok, we've actually completely succeeded! Gather up stats on that success.
    let mut vetted_with_exemptions = vec![];
    let mut vetted_partially = vec![];
    let mut vetted_fully = vec![];
    for &pkgidx in &graph.topo_index {
        let package = &graph.nodes[pkgidx];
        if !package.is_third_party {
            // We only want to report on third-parties.
            continue;
        }
        let result = &results[pkgidx];

        if !root_caveats.needed_exemptions.contains(&pkgidx) {
            vetted_fully.push(pkgidx);
        } else if result.directly_exempted {
            vetted_with_exemptions.push(pkgidx);
        } else {
            vetted_partially.push(pkgidx);
        }
    }

    (
        results,
        Conclusion::Success(Success {
            vetted_with_exemptions,
            vetted_partially,
            vetted_fully,
            needed_fresh_imports: root_caveats.needed_fresh_imports,
        }),
    )
}

fn resolve_third_party<'a>(
    store: &'a Store,
    graph: &DepGraph<'a>,
    criteria_mapper: &CriteriaMapper,
    results: &mut [ResolveResult<'a>],
    violations: &mut SortedMap<PackageIdx, Vec<ViolationConflict>>,
    _root_failures: &mut RootFailures,
    pkgidx: PackageIdx,
) {
    let package = &graph.nodes[pkgidx];
    let exemptions = store.config.exemptions.get(package.name);

    // 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<CriteriaNamespace> = store
        .imported_audits()
        .keys()
        .map(|import_name| CriteriaNamespace::Foreign(import_name.clone()))
        .collect();

    // Each of our own audits should be put into the "local" criteria namespace.
    let own_audits = store
        .audits
        .audits
        .get(package.name)
        .map(|v| &v[..])
        .unwrap_or(&[])
        .iter()
        .map(|audit| (&CriteriaNamespace::Local, audit));

    // Each foreign audit should be put into a "foreign" criteria namespace.
    let foreign_audits = store
        .imported_audits()
        .values()
        .enumerate()
        .flat_map(|(idx, audits)| {
            let namespace = &foreign_namespaces[idx];
            audits
                .audits
                .get(package.name)
                .map(|v| &v[..])
                .unwrap_or(&[])
                .iter()
                .map(move |audit| (namespace, audit))
        });

    let all_audits = own_audits.chain(foreign_audits);

    // See AuditGraph's docs for details on the lowering we do here
    let mut forward_audits = AuditGraph::new();
    let mut backward_audits = AuditGraph::new();
    let mut violation_nodes = Vec::new();

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

        let criteria = criteria_mapper.criteria_from_namespaced_entry(namespace, entry);
        // Convert all the custom criteria to CriteriaSets
        let dependency_criteria: FastMap<_, _> = dependency_criteria
            .iter()
            .map(|(pkg_name, criteria)| {
                (
                    &**pkg_name,
                    criteria_mapper.criteria_from_namespaced_list(namespace, criteria),
                )
            })
            .collect();

        let origin = if entry.is_fresh_import {
            DeltaEdgeOrigin::FreshImportedAudit
        } else {
            DeltaEdgeOrigin::StoredAudit
        };

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

    // Reject forbidden packages (violations)
    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_namespaced_list(violation_source, [&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.entry(pkgidx).or_default().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, audit) in all_audits.clone() {
            let audit_criteria = criteria_mapper.criteria_from_namespaced_entry(namespace, audit);
            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.entry(pkgidx).or_default().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.entry(pkgidx).or_default().push(
                            ViolationConflict::AuditConflict {
                                violation_source: violation_source.clone(),
                                violation: (*violation_entry).clone(),
                                audit_source: namespace.clone(),
                                audit: audit.clone(),
                            },
                        );
                    }
                }
                AuditKind::Violation { .. } => {
                    // don't care
                }
            }
        }

        // FIXME: this kind of violation is annoying to catch, but you kind of don't have to.
        //
        // It's impossible to validate a package with some criteria without an audit/exemptions
        // entry with that criteria (or a criteria that implies it) touching that version.
        // Therefore we can catch any "true" violations by just looking at the AuditGraph's
        // edges as we do above. However if you current version is a violation and but doesn't
        // have an audit, we may suggest an audit that *is* a violation. This is bad.
        //
        // This commented out code stands as a memorial to that problem for later.

        /*
        // Note if this entry conflicts with the current package's version
        if violation_range.matches(package.version) {
            violations
                .entry(pkgidx)
                .or_default()
                .push(ViolationConflict::CurVersionConflict {
                    source: violation_source.clone(),
                    violation: (*violation_entry).clone(),
                });
        }
        */
    }

    let mut directly_exempted = false;
    // Unaudited entries are equivalent to full-audits
    if let Some(alloweds) = exemptions {
        for allowed in alloweds {
            if &allowed.version == package.version {
                directly_exempted = true;
            }
            let from_ver = None;
            let to_ver = Some(&allowed.version);
            let criteria = criteria_mapper.criteria_from_list(&allowed.criteria);
            let dependency_criteria: FastMap<_, _> = allowed
                .dependency_criteria
                .iter()
                .map(|(pkg_name, criteria)| {
                    (&**pkg_name, criteria_mapper.criteria_from_list(criteria))
                })
                .collect();

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

    let mut validated_criteria = criteria_mapper.no_criteria();
    let mut search_results = vec![];
    for criteria in criteria_mapper.all_criteria_iter() {
        let result = search_for_path(
            criteria,
            None,
            Some(package.version),
            &forward_audits,
            graph,
            criteria_mapper,
            results,
            pkgidx,
            &package.normal_and_build_deps,
        );
        match result {
            SearchResult::Connected { caveats } => {
                // We found a patch to satisfy this criteria.
                validated_criteria.unioned_with(criteria);
                search_results.push(SearchResult::Connected { caveats });
            }
            SearchResult::PossiblyConnected { failed_deps } => {
                // We failed but found a possible solution if our dependencies were better.
                // Just forward this along so that we can blame them if it comes up!
                search_results.push(SearchResult::PossiblyConnected { failed_deps });
            }
            SearchResult::Disconnected {
                reachable_from_root,
                ..
            } => {
                // We failed to find a path, boo! Run the algorithm backwards to see what we
                // can reach from the other side, so we have our candidates for suggestions.
                let rev_result = search_for_path(
                    criteria,
                    Some(package.version),
                    None,
                    &backward_audits,
                    graph,
                    criteria_mapper,
                    results,
                    pkgidx,
                    &package.normal_and_build_deps,
                );
                if let SearchResult::Disconnected {
                    reachable_from_root: reachable_from_target,
                    ..
                } = rev_result
                {
                    search_results.push(SearchResult::Disconnected {
                        reachable_from_root,
                        reachable_from_target,
                    })
                } else {
                    unreachable!("We managed to find a path but only from one direction?!");
                }
            }
        }
    }

    trace!(
        "  third-party validation: {:?}",
        criteria_mapper
            .criteria_names(&validated_criteria)
            .collect::<Vec<_>>()
    );

    // We've completed our graph analysis for this package, now record the results
    results[pkgidx] = ResolveResult {
        validated_criteria,
        search_results,
        directly_exempted,
    };
}

/// Updates `caveats`, and `failed_deps` to include any caveats or failed
/// dependencies involved in requiring `dependencies` to satisfy the given
/// criteria.
#[allow(clippy::too_many_arguments)]
fn get_dependency_criteria_caveats(
    dep_graph: &DepGraph,
    criteria_mapper: &CriteriaMapper,
    results: &[ResolveResult<'_>],
    dependencies: &[PackageIdx],
    base_criteria: &CriteriaSet,
    dependency_criteria: &FastMap<PackageStr<'_>, CriteriaSet>,
    caveats: &mut Caveats,
    failed_deps: &mut SortedMap<PackageIdx, CriteriaSet>,
) {
    for &depidx in dependencies {
        let dep_package = &dep_graph.nodes[depidx];
        let dep_results = &results[depidx];

        // If no custom criteria is specified, then require our dependency to match
        // the base criteria that we're trying to validate. This makes audits effectively
        // break down their criteria into individually verifiable components instead of
        // purely "all or nothing".
        //
        // e.g. a safe-to-deploy audit with some deps that are only safe-to-run
        // still audits for safe-to-run, but not safe-to-deploy. Similarly so for
        // `[safe-to-run, some-other-criteria]` validating each criteria individually.
        let dep_req = dependency_criteria
            .get(dep_package.name)
            .unwrap_or(base_criteria);

        if !dep_results.validated_criteria.contains(dep_req) {
            // This dependency's criteria is not satisfied, so add it to the
            // failed deps map.
            failed_deps
                .entry(depidx)
                .or_insert_with(|| criteria_mapper.no_criteria())
                .unioned_with(dep_req);
            continue;
        }

        // Only iterate the minimal set of indices to reduce the number of
        // search results we check for caveats, as implied results will have a
        // subset of the caveats of the stronger criteria.
        for required_criteria_idx in criteria_mapper.minimal_indices(dep_req) {
            // Check if the original search results succeeded here, and if it
            // did record the relevant caveats. It's OK if we don't see
            // `Connected` here, as that just means a policy overwrote our
            // failure.
            if let SearchResult::Connected {
                caveats: dep_caveats,
            } = &dep_results.search_results[required_criteria_idx]
            {
                caveats.add(dep_caveats);
            }
        }
    }
}

#[allow(clippy::too_many_arguments)]
fn search_for_path<'a>(
    cur_criteria: &CriteriaSet,
    from_version: Option<&'a Version>,
    to_version: Option<&'a Version>,
    audit_graph: &AuditGraph<'a>,
    dep_graph: &DepGraph<'a>,
    criteria_mapper: &CriteriaMapper,
    results: &[ResolveResult],
    pkgidx: PackageIdx,
    dependencies: &[PackageIdx],
) -> SearchResult<'a> {
    // Search for any path through the graph with edges that satisfy
    // cur_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.
    //
    // These caveats extend all the way from exemptions (the least-important
    // caveat) to fresh imports and even failed edges (the most-important
    // caveat).
    struct Node<'a> {
        version: Option<&'a Version>,
        caveats: Caveats,
        failed_deps: SortedMap<PackageIdx, CriteriaSet>,
    }

    impl<'a> Node<'a> {
        fn key(&self) -> Reverse<(usize, usize, usize)> {
            // Nodes are compared by the number of failed dependencies, fresh
            // imports, and exemptions, in that order. Fewer caveats makes the
            // node sort higher, as it will be stored in a max heap.
            Reverse((
                self.failed_deps.len(),
                self.caveats.needed_fresh_imports.len(),
                self.caveats.needed_exemptions.len(),
            ))
        }
    }
    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,
        caveats: Caveats::default(),
        failed_deps: SortedMap::new(),
    });

    let mut visited = SortedSet::new();
    while let Some(Node {
        version,
        caveats,
        failed_deps,
    }) = 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 if failed_deps.is_empty() {
                SearchResult::Connected { caveats }
            } else {
                SearchResult::PossiblyConnected { failed_deps }
            };
        }

        // 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 {
            if !edge.criteria.contains(cur_criteria) {
                // 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;
            }

            let mut edge_caveats = caveats.clone();
            let mut edge_failed_deps = failed_deps.clone();

            match edge.origin {
                DeltaEdgeOrigin::Exemption => {
                    edge_caveats.needed_exemptions.insert(pkgidx);
                }
                DeltaEdgeOrigin::FreshImportedAudit => {
                    edge_caveats.needed_fresh_imports.insert(pkgidx);
                }
                DeltaEdgeOrigin::StoredAudit => {}
            }

            get_dependency_criteria_caveats(
                dep_graph,
                criteria_mapper,
                results,
                dependencies,
                cur_criteria,
                &edge.dependency_criteria,
                &mut edge_caveats,
                &mut edge_failed_deps,
            );

            queue.push(Node {
                version: edge.version,
                caveats: edge_caveats,
                failed_deps: edge_failed_deps,
            });
        }
    }

    // Complete failure, we need more audits for this package, so all that
    // matters is what nodes were reachable.
    SearchResult::Disconnected {
        reachable_from_root: visited,
        // This will get filled in by a second pass.
        reachable_from_target: Default::default(),
    }
}

fn resolve_first_party<'a>(
    store: &'a Store,
    graph: &DepGraph<'a>,
    criteria_mapper: &CriteriaMapper,
    results: &mut [ResolveResult<'a>],
    _violations: &mut SortedMap<PackageIdx, Vec<ViolationConflict>>,
    _root_failures: &mut RootFailures,
    pkgidx: PackageIdx,
) {
    // Check the build-deps and normal-deps of this package. dev-deps are checking in `resolve_dep`
    // In this pass we properly use package.is_root, but in the next pass all nodes are "roots"
    let package = &graph.nodes[pkgidx];

    // Get custom policies for our dependencies
    let dep_criteria = store
        .config
        .policy
        .get(package.name)
        .map(|policy| {
            policy
                .dependency_criteria
                .iter()
                .map(|(dep_name, criteria)| {
                    (&**dep_name, criteria_mapper.criteria_from_list(criteria))
                })
                .collect::<FastMap<_, _>>()
        })
        .unwrap_or_default();

    // Compute whether we have each criteria based on our dependencies
    let mut validated_criteria = criteria_mapper.no_criteria();
    let mut search_results = Vec::with_capacity(criteria_mapper.len());
    for criteria in criteria_mapper.all_criteria_iter() {
        // Find any build/normal dependencies that don't satisfy this criteria
        let mut caveats = Caveats::default();
        let mut failed_deps = SortedMap::new();

        get_dependency_criteria_caveats(
            graph,
            criteria_mapper,
            results,
            &package.normal_and_build_deps,
            criteria,
            &dep_criteria,
            &mut caveats,
            &mut failed_deps,
        );

        if failed_deps.is_empty() {
            // All our deps passed the test, so we have this criteria
            search_results.push(SearchResult::Connected { caveats });
            validated_criteria.unioned_with(criteria);
        } else {
            // Some of our deps failed to satisfy this criteria, record this
            search_results.push(SearchResult::PossiblyConnected { failed_deps })
        }
    }
    trace!(
        "  first-party validation: {:?}",
        criteria_mapper
            .criteria_names(&validated_criteria)
            .collect::<Vec<_>>()
    );

    // Save the results
    results[pkgidx] = ResolveResult {
        validated_criteria,
        search_results,
        directly_exempted: false,
    };
}

fn get_policy_caveats<'a>(
    criteria_mapper: &CriteriaMapper,
    search_results: &[SearchResult<'a>],
    own_policy: &CriteriaSet,
    pkgidx: PackageIdx,
    root_caveats: &mut Caveats,
    policy_failures: &mut PolicyFailures,
) {
    for criteria_idx in own_policy.indices() {
        match &search_results[criteria_idx] {
            SearchResult::PossiblyConnected { failed_deps } => {
                // Our children failed us
                for (&dep, failed_criteria) in failed_deps {
                    policy_failures
                        .entry(dep)
                        .or_insert_with(|| criteria_mapper.no_criteria())
                        .unioned_with(failed_criteria);
                }
            }
            SearchResult::Disconnected { .. } => {
                // We failed ourselves
                policy_failures
                    .entry(pkgidx)
                    .or_insert_with(|| criteria_mapper.no_criteria())
                    .set_criteria(criteria_idx)
            }
            SearchResult::Connected { caveats } => {
                // A-OK
                root_caveats.add(caveats);
            }
        }
    }
}

#[allow(clippy::too_many_arguments)]
fn resolve_self_policy<'a>(
    store: &'a Store,
    graph: &DepGraph<'a>,
    criteria_mapper: &CriteriaMapper,
    results: &mut [ResolveResult<'a>],
    _violations: &mut SortedMap<PackageIdx, Vec<ViolationConflict>>,
    root_failures: &mut RootFailures,
    root_caveats: &mut Caveats,
    pkgidx: PackageIdx,
) {
    let package = &graph.nodes[pkgidx];

    // Now check that we pass our own policy
    let entry = store.config.policy.get(package.name);
    let own_policy = if let Some(c) = entry.and_then(|p| p.criteria.as_ref()) {
        trace!("  explicit policy: {:?}", c);
        criteria_mapper.criteria_from_list(c)
    } else if package.is_root {
        trace!("  root policy: {:?}", [format::DEFAULT_POLICY_CRITERIA]);
        criteria_mapper.criteria_from_list([format::DEFAULT_POLICY_CRITERIA])
    } else {
        trace!("  has no policy, done");
        // We have no policy, we're done
        return;
    };

    let mut policy_failures = PolicyFailures::new();

    get_policy_caveats(
        criteria_mapper,
        &results[pkgidx].search_results,
        &own_policy,
        pkgidx,
        root_caveats,
        &mut policy_failures,
    );

    // NOTE: We don't update search results here, just `validated_criteria`.
    // This is the only way that these two should get out of sync, but we want
    // to keep around the old search results as it will be useful for blame.
    if policy_failures.is_empty() {
        // We had a policy and it passed, so now we're validated for all criteria
        // because our parents can never require anything else of us. No need
        // to update search_results, they'll be masked out by validated_criteria(?)
        trace!("  passed policy, all_criteria");
        results[pkgidx].validated_criteria = criteria_mapper.all_criteria();
    } else {
        // We had a policy and it failed, so now we're invalid for all criteria(?)
        trace!("  failed policy, no_criteria");
        results[pkgidx].validated_criteria = criteria_mapper.no_criteria();
        root_failures.push((pkgidx, policy_failures, false));
    }
}

#[allow(clippy::too_many_arguments)]
fn resolve_dev<'a>(
    store: &'a Store,
    graph: &DepGraph<'a>,
    criteria_mapper: &CriteriaMapper,
    results: &mut [ResolveResult<'a>],
    _violations: &mut SortedMap<PackageIdx, Vec<ViolationConflict>>,
    root_failures: &mut RootFailures,
    root_caveats: &mut Caveats,
    pkgidx: PackageIdx,
) {
    // Check the dev-deps of this package. It is assumed to be a root in this context,
    // so the default root dev policy will always be applicable.
    let package = &graph.nodes[pkgidx];

    // Get custom policies for our dependencies
    let dep_criteria = store
        .config
        .policy
        .get(package.name)
        .map(|policy| {
            policy
                .dependency_criteria
                .iter()
                .map(|(dep_name, criteria)| {
                    (&**dep_name, criteria_mapper.criteria_from_list(criteria))
                })
                .collect::<FastMap<_, _>>()
        })
        .unwrap_or_default();

    // Compute whether we have each criteria based on our dependencies
    let mut validated_criteria = criteria_mapper.no_criteria();
    let mut search_results = vec![];
    for criteria in criteria_mapper.all_criteria_iter() {
        // Find any build/normal dependencies that don't satisfy this criteria
        let mut caveats = Caveats::default();
        let mut failed_deps = SortedMap::new();

        get_dependency_criteria_caveats(
            graph,
            criteria_mapper,
            results,
            &package.dev_deps,
            criteria,
            &dep_criteria,
            &mut caveats,
            &mut failed_deps,
        );

        if failed_deps.is_empty() {
            // All our deps passed the test, so we have this criteria
            search_results.push(SearchResult::Connected { caveats });
            validated_criteria.unioned_with(criteria);
        } else {
            // Some of our deps failed to satisfy this criteria, record this
            search_results.push(SearchResult::PossiblyConnected { failed_deps })
        }
    }
    trace!(
        "  dev validation: {:?}",
        criteria_mapper
            .criteria_names(&validated_criteria)
            .collect::<Vec<_>>()
    );
    // NOTE: DON'T save the results, because we're analyzing this as a dev-node
    // and anything that depends on us only cares about the "normal" results.

    // Now check that we pass our own policy
    let entry = store.config.policy.get(package.name);
    let own_policy = if let Some(c) = entry.and_then(|p| p.dev_criteria.as_ref()) {
        trace!("  explicit policy: {:?}", c);
        criteria_mapper.criteria_from_list(c)
    } else {
        trace!("  root policy: {:?}", [format::DEFAULT_POLICY_DEV_CRITERIA]);
        criteria_mapper.criteria_from_list([format::DEFAULT_POLICY_DEV_CRITERIA])
    };

    let mut policy_failures = PolicyFailures::new();

    get_policy_caveats(
        criteria_mapper,
        &search_results,
        &own_policy,
        pkgidx,
        root_caveats,
        &mut policy_failures,
    );

    if policy_failures.is_empty() {
        trace!("  passed dev policy");
    } else {
        trace!("  failed dev policy");
        root_failures.push((pkgidx, policy_failures, true));
    }
}

/// Traverse the build graph from the root failures to the leaf failures.
fn visit_failures<'a, T>(
    graph: &DepGraph<'a>,
    criteria_mapper: &CriteriaMapper,
    results: &[ResolveResult<'a>],
    root_failures: &RootFailures,
    resolve_depth: ResolveDepth,
    mut callback: impl FnMut(PackageIdx, usize, Option<&CriteriaFailureSet>) -> Result<(), T>,
) -> Result<(), T> {
    trace!(" traversing blame tree");

    // The crate graph can be messy in several ways:
    //
    // 1. The depth of the graph can be very large, so recursion could blow the stack.
    //
    // 2. The "tree" view of the graph can have an exponential number of nodes because
    //    of duplicated subgraphs from shared dependencies. Unfortunately, that is
    //    the representation we "have" to traverse to properly blame packages for
    //    specific policty failures.
    //
    // 3. Different "targets" for one package are actually logically separate crates,
    //    and naively unifying them can result in cycles. In particular, the "dev"
    //    version of a crate (tests and benches) can have dev-dependencies which depend
    //    on the "real" version of that crate, so if you combine "dev" and "normal"
    //    then you can have cycles. Horrifyingly, people do rely on this.
    //
    // Problem 1 is easy to fix: just use an explicit stack instead of recursion.
    //
    // Problem 2 can be solved by noting that, as long as we don't actually care about
    // *printing* the entire blame-tree and just want to figure out what the leaves
    // are and what criteria they need, we can use the usual "keep a set of visited
    // nodes and don't revisit nodes in that set" pattern *except* modified to include
    // the set of criteria it has been visited with. We then only revisit a node if
    // our current path has criteria that aren't yet in the visitor set.
    //
    // Problem 3 is trickier. Really we should "desugar" a node into its different
    // targets, but there are effectively infinite targets due to all the possible
    // cfg combinations and feature flags, so we'd *really* like to be able to abstractly
    // handle those. I *think* we only *really* need to split up "dev" from "everything else"
    // but I want to think about this more. For now we just rely on the solution to problem 2
    // to avoid infinite loops and just don't worry about the semantics.
    let mut search_stack = Vec::new();

    let mut immune_to_parent_demands = FastSet::new();
    for (failed_idx, policy_failures, is_dev) in root_failures {
        let failed_package = &graph.nodes[*failed_idx];
        trace!(
            " policy failure for {}:{}",
            failed_package.name,
            failed_package.version
        );
        for (&failed_dep_idx, failed_criteria) in policy_failures {
            let failed_dep = &graph.nodes[failed_dep_idx];
            trace!(
                "   {}:{} needed {:?}",
                failed_dep.name,
                failed_dep.version,
                criteria_mapper
                    .criteria_names(failed_criteria)
                    .collect::<Vec<_>>()
            );
            search_stack.push((
                failed_dep_idx,
                0,
                Some(CriteriaFailureSet::from(failed_criteria, true)),
            ));
        }
        if !is_dev {
            // If we have a root failure and it's not from the virtual dev-node, then
            // we have a self-policy that "shadows" anything a parent could require.
            // We will properly blame our children based on the existence of this entry,
            // so we should refuse any attempts from a parent to blame us for anything.
            immune_to_parent_demands.insert(failed_idx);
        }
    }
    let mut visited = FastMap::<PackageIdx, CriteriaFailureSet>::new();
    let no_criteria = criteria_mapper.no_criteria_failures();

    while let Some((failure_idx, depth, cur_criteria)) = search_stack.pop() {
        match visited.entry(failure_idx) {
            std::collections::hash_map::Entry::Vacant(entry) => {
                entry.insert(cur_criteria.clone().unwrap_or_else(|| no_criteria.clone()));
            }
            std::collections::hash_map::Entry::Occupied(mut entry) => {
                let cur = cur_criteria.as_ref().unwrap_or(&no_criteria);
                if entry.get().contains(cur) {
                    continue;
                } else {
                    entry.get_mut().unioned_with(cur);
                }
            }
        }

        let result = &results[failure_idx];
        let package = &graph.nodes[failure_idx];
        trace!(
            " {:width$}visiting {}:{} for {:?} + {:?}",
            "",
            package.name,
            package.version,
            cur_criteria.as_ref().map(|c| criteria_mapper
                .confident_criteria_names(c)
                .collect::<Vec<_>>()),
            cur_criteria.as_ref().map(|c| criteria_mapper
                .unconfident_criteria_names(c)
                .collect::<Vec<_>>()),
            width = depth
        );

        if let Some(failed_criteria) = cur_criteria {
            let mut own_fault = no_criteria.clone();
            let mut dep_faults = FastMap::<PackageIdx, CriteriaFailureSet>::new();

            // Collect up details of how we failed the criteria
            for criteria_idx in failed_criteria.all().indices() {
                let confident = failed_criteria.confident().has_criteria(criteria_idx);
                match &result.search_results[criteria_idx] {
                    SearchResult::Connected { .. } => {
                        // Do nothing, this package is good
                    }
                    SearchResult::PossiblyConnected { failed_deps } => {
                        // We're not to blame, it's our children who failed!
                        for (&failed_dep, failed_criteria) in failed_deps {
                            dep_faults
                                .entry(failed_dep)
                                .or_insert_with(|| no_criteria.clone())
                                .unioned_with(&CriteriaFailureSet::from(
                                    failed_criteria,
                                    confident,
                                ));
                        }
                    }
                    SearchResult::Disconnected { .. } => {
                        // Oh dang ok we *are* to blame, our bad
                        own_fault.set_criteria(criteria_idx, confident);

                        if resolve_depth != ResolveDepth::Shallow {
                            // Try to Guess Deeper by blaming our children for all |self| failures
                            // by assuming we would need them to conform to our own criteria too.
                            //
                            // Dev-deps should never be chased here because any issues with those show
                            // up as root_failures and have already been pushed into the search-stack.
                            // All recursive blaming is about deps for a "normal" build, which requires
                            // only these two kinds of deps.
                            for &dep_idx in &package.normal_and_build_deps {
                                let dep_result = &results[dep_idx];
                                if !dep_result.validated_criteria.has_criteria(criteria_idx) {
                                    dep_faults
                                        .entry(dep_idx)
                                        .or_insert_with(|| no_criteria.clone())
                                        .set_criteria(criteria_idx, false);
                                }
                            }
                        }
                    }
                }
            }

            // Visit ourselves based on whether we're to blame at all
            if own_fault.is_empty() {
                callback(failure_idx, depth, None)?;
            } else {
                callback(failure_idx, depth, Some(&own_fault))?;
            }

            // Now visit our children
            for (failed_dep, failed_criteria) in dep_faults {
                if immune_to_parent_demands.contains(&failed_dep) {
                    continue;
                }
                search_stack.push((failed_dep, depth + 1, Some(failed_criteria.clone())));
            }
        } else {
            unreachable!("I don't think this should happen..?");
        }
    }
    Ok(())
}

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,
        network: Option<&Network>,
        allow_deltas: bool,
    ) -> 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 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];

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

                        // To keep the display compact, sort by name length and truncate long lists.
                        // We first sort by name because rust defaults to a stable sort and this will
                        // have by-name as the tie breaker.
                        reverse_deps.sort();
                        reverse_deps.sort_by_key(|item| item.len());
                        let cutoff_index = reverse_deps
                            .iter()
                            .scan(0, |sum, s| {
                                *sum += s.len();
                                Some(*sum)
                            })
                            .position(|count| count > 20);
                        let remainder = cutoff_index.map(|i| reverse_deps.len() - i).unwrap_or(0);
                        if remainder > 1 {
                            reverse_deps.truncate(cutoff_index.unwrap());
                            reverse_deps.push(format!("and {} others", remainder));
                        }
                        reverse_deps.join(", ")
                    };

                    // Collect up the details of how we failed
                    let mut from_root = None::<SortedSet<Option<&Version>>>;
                    let mut from_target = None::<SortedSet<Option<&Version>>>;
                    for criteria_idx in audit_failure.criteria_failures.all().indices() {
                        let search_result = &result.search_results[criteria_idx];
                        if let SearchResult::Disconnected {
                            reachable_from_root,
                            reachable_from_target,
                        } = search_result
                        {
                            if let (Some(from_root), Some(from_target)) =
                                (from_root.as_mut(), from_target.as_mut())
                            {
                                // FIXME: this is horrible but I'm tired and this avoids false-positives
                                // and duplicates. 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 = &*from_root & reachable_from_root;
                                *from_target = &*from_target & reachable_from_target;
                            } else {
                                from_root = Some(reachable_from_root.clone());
                                from_target = Some(reachable_from_target.clone());
                            }
                        } else {
                            unreachable!("messed up suggest...");
                        }
                    }

                    // Now suggest solutions of those failures
                    let mut candidates = SortedSet::new();
                    if allow_deltas {
                        // If we're allowed deltas than try to find a bridge from src and dest
                        for &dest in from_target.as_ref().unwrap() {
                            let mut closest_above = None;
                            let mut closest_below = None;
                            for &src in from_root.as_ref().unwrap() {
                                if src < dest {
                                    if let Some(closest) = closest_below {
                                        if src > closest {
                                            closest_below = Some(src);
                                        }
                                    } else {
                                        closest_below = Some(src);
                                    }
                                } else if let Some(closest) = closest_above {
                                    if src < closest {
                                        closest_above = Some(src);
                                    }
                                } else {
                                    closest_above = Some(src);
                                }
                            }

                            for closest in closest_below.into_iter().chain(closest_above) {
                                candidates.insert(Delta {
                                    from: closest.cloned(),
                                    to: dest.unwrap().clone(),
                                });
                            }
                        }
                    } else {
                        // If we're not allowing deltas, just try everything reachable from the target
                        for &dest in from_target.as_ref().unwrap() {
                            candidates.insert(Delta {
                                from: None,
                                to: dest.unwrap().clone(),
                            });
                        }
                    }

                    let diffstats = join_all(candidates.iter().map(|delta| async {
                        match cache
                            .fetch_and_diffstat_package(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!
                                error!(
                                    "error diffing {}:{}: {:?}",
                                    package.name, package.version, err
                                );
                                None
                            }
                        }
                    }))
                    .await;

                    Some(SuggestItem {
                        package: failure_idx,
                        suggested_diff: diffstats
                            .into_iter()
                            .flatten()
                            .min_by_key(|diff| diff.diffstat.count)?,
                        suggested_criteria: audit_failure.criteria_failures.clone(),
                        notable_parents,
                    })
                },
            )))
            .into_iter()
            .flatten()
            .collect::<Vec<_>>();

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

        suggestions.sort_by_key(|item| self.graph.nodes[item.package].version);
        suggestions.sort_by_key(|item| self.graph.nodes[item.package].name);
        suggestions.sort_by_key(|item| item.suggested_diff.diffstat.count);
        suggestions.sort_by_key(|item| item.suggested_criteria.is_fully_unconfident());

        let mut suggestions_by_criteria = SortedMap::<CriteriaName, Vec<SuggestItem>>::new();
        for s in suggestions.clone().into_iter() {
            let criteria_names = self
                .criteria_mapper
                .all_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,
        }))
    }

    /// 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<&Version>,
        to: &Version,
    ) -> Vec<CriteriaName> {
        let fail = if let Conclusion::FailForVet(fail) = &self.conclusion {
            fail
        } else {
            return Vec::new();
        };

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

        // 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];
            for criteria_idx in audit_failure.criteria_failures.all().indices() {
                let search_result = &result.search_results[criteria_idx];
                if let SearchResult::Disconnected {
                    reachable_from_root,
                    reachable_from_target,
                } = search_result
                {
                    if reachable_from_target.contains(&Some(to))
                        && from.map_or(true, |v| reachable_from_root.contains(&Some(v)))
                    {
                        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>,
        _cfg: &Config,
        suggest: Option<&Suggest>,
    ) -> Result<(), miette::Report> {
        let result = match &self.conclusion {
            Conclusion::Success(success) => {
                let json_package = |pkgidx: &PackageIdx| {
                    let package = &self.graph.nodes[*pkgidx];
                    json!({
                        "name": package.name,
                        "version": package.version,
                    })
                };
                json!({
                    "conclusion": "success",
                    "vetted_fully": success.vetted_fully.iter().map(json_package).collect::<Vec<_>>(),
                    "vetted_partially": success.vetted_partially.iter().map(json_package).collect::<Vec<_>>(),
                    "vetted_with_exemptions": success.vetted_with_exemptions.iter().map(json_package).collect::<Vec<_>>(),
                })
            }
            Conclusion::FailForViolationConflict(fail) => json!({
                "conclusion": "fail (violation)",
                "violations": fail.violations.iter().map(|(pkgidx, violations)| {
                    let package = &self.graph.nodes[*pkgidx];
                    let key = format!("{}:{}", package.name, package.version);
                    (key, violations)
                }).collect::<SortedMap<_,_>>(),
            }),
            Conclusion::FailForVet(fail) => {
                // FIXME: How to report confidence for suggested criteria?
                let json_suggest_item = |item: &SuggestItem| {
                    let package = &self.graph.nodes[item.package];
                    json!({
                        "name": package.name,
                        "notable_parents": item.notable_parents,
                        "suggested_criteria": self.criteria_mapper.all_criteria_names(&item.suggested_criteria).collect::<Vec<_>>(),
                        "suggested_diff": item.suggested_diff,
                    })
                };
                json!({
                    "conclusion": "fail (vetting)",
                    "failures": fail.failures.iter().map(|(&pkgidx, audit_fail)| {
                        let package = &self.graph.nodes[pkgidx];
                        json!({
                            "name": package.name,
                            "version": package.version,
                            "missing_criteria": self.criteria_mapper.all_criteria_names(&audit_fail.criteria_failures).collect::<Vec<_>>(),
                        })
                    }).collect::<Vec<_>>(),
                    "suggest": suggest.map(|suggest| json!({
                        "suggestions": suggest.suggestions.iter().map(json_suggest_item).collect::<Vec<_>>(),
                        "suggest_by_criteria": suggest.suggestions_by_criteria.iter().map(|(criteria, items)| (criteria, items.iter().map(json_suggest_item).collect::<Vec<_>>())).collect::<SortedMap<_,_>>(),
                        "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", fully_audited_count);
                count_count -= 1;
                if count_count > 0 {
                    write!(out, ", ");
                }
            }
            if partially_audited_count != 0 {
                write!(out, "{} partially audited", partially_audited_count);
                count_count -= 1;
                if count_count > 0 {
                    write!(out, ", ");
                }
            }
            if exemptions_count != 0 {
                write!(out, "{} exempted", exemptions_count);
                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 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 parents = format!("(used by {})", item.notable_parents);
                    let diffstat = match &item.suggested_diff.from {
                        Some(_) => format!("({})", item.suggested_diff.diffstat.raw.trim()),
                        None => format!("({} lines)", item.suggested_diff.diffstat.count),
                    };
                    let style = if item.suggested_criteria.is_fully_unconfident() {
                        out.style().dim()
                    } else {
                        out.style()
                    };
                    (cmd, parents, diffstat, style)
                })
                .collect::<Vec<_>>();

            let mut max0 = 0;
            let mut max1 = 0;
            for (s0, s1, ..) in &strings {
                max0 = max0.max(console::measure_text_width(s0));
                max1 = max1.max(console::measure_text_width(s1));
            }

            for (s0, s1, s2, style) in strings {
                write!(
                    out,
                    "{}",
                    style
                        .clone()
                        .cyan()
                        .bold()
                        .apply_to(format_args!("    {s0:width$}", width = max0))
                );
                writeln!(
                    out,
                    "{}",
                    style.apply_to(format_args!("  {s1:width$}  {s2}", width = max1))
                );
            }

            writeln!(out);
        }

        writeln!(out, "estimated audit backlog: {} lines", self.total_lines);
        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);
        failures.sort_by_key(|(_, failure)| failure.criteria_failures.is_fully_unconfident());
        for (failed_package, failed_audit) in failures {
            let confident_criteria = report
                .criteria_mapper
                .confident_criteria_names(&failed_audit.criteria_failures)
                .collect::<Vec<_>>();
            let unconfident_criteria = report
                .criteria_mapper
                .unconfident_criteria_names(&failed_audit.criteria_failures)
                .collect::<Vec<_>>();

            let label = format!("  {}:{}", failed_package.name, failed_package.version);
            if !confident_criteria.is_empty() {
                writeln!(out, "{} missing {:?}", label, confident_criteria);
            }
            if !unconfident_criteria.is_empty() {
                writeln!(
                    out,
                    "{}",
                    out.style().dim().apply_to(format_args!(
                        "{} likely missing {:?}",
                        if confident_criteria.is_empty() {
                            label
                        } else {
                            format!("{:width$}", "", width = console::measure_text_width(&label))
                        },
                        unconfident_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: &CriteriaNamespace,
            entry: &AuditEntry,
        ) -> Result<(), std::io::Error> {
            match source {
                CriteriaNamespace::Local => write!(out, "own "),
                CriteriaNamespace::Foreign(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);
            if let Some(who) = &entry.who {
                writeln!(out, "      who: {who}");
            }
            if let Some(notes) = &entry.notes {
                writeln!(out, "      notes: {notes}");
            }
            Ok(())
        }

        Ok(())
    }
}

/// Ensure that vet will pass on the store by adding new exemptions, as well as
/// removing existing ones which are no longer necessary. Regenerating
/// exemptions generally tries to avoid unnecessary changes, and to continue to
/// pin exemptions in the past when delta-audits from exemptions are in-use.
pub fn regenerate_exemptions(
    cfg: &Config,
    store: &mut Store,
    allow_new_exemptions: bool,
    force_update_imports: bool,
) -> Result<(), RegenerateExemptionsError> {
    // While minimizing exemptions, a number of different calls to the resolver
    // will be made using the same DepGraph and CriteriaMapper, which will be
    // generated up-front.
    let graph = DepGraph::new(
        &cfg.metadata,
        cfg.cli.filter_graph.as_ref(),
        Some(&store.config.policy),
    );
    let criteria_mapper = CriteriaMapper::new(
        &store.audits.criteria,
        store.imported_audits(),
        &store.config.imports,
    );

    // If we're not allowing new exemptions, we must already be passing `vet`.
    // If we aren't, we can't do anything, so just update imports and return
    // immediately. We'll also do this if automatic exemption minimization is
    // disabled through the CLI.
    if !allow_new_exemptions {
        let (_, conclusion) = resolve_core(&graph, store, &criteria_mapper, ResolveDepth::Shallow);
        if !matches!(conclusion, Conclusion::Success(_)) || cfg.cli.no_minimize_exemptions {
            store.imports =
                store.get_updated_imports_file(&graph, &conclusion, force_update_imports);
            return Ok(());
        }
    }

    // Clear out the existing exemptions, starting with a clean slate. We'll
    // re-add exemptions as-needed.
    let old_exemptions = mem::take(&mut store.config.exemptions);

    // Build a list of all relevant versions of each crate used in this crate
    // graph by-name. We sort this in ascending order, meaning that we try to
    // add exemptions for earlier (in-use) versions first when needed.
    let mut pkg_versions_by_name: SortedMap<PackageStr<'_>, Vec<&Version>> = SortedMap::new();
    for package in &graph.nodes {
        pkg_versions_by_name
            .entry(package.name)
            .or_default()
            .push(package.version);
    }
    for versions in pkg_versions_by_name.values_mut() {
        versions.sort();
    }

    /// A single exemption which we may or may not end up mapping into the final
    /// exemptions file. There is one of these for each existing exemption, as
    /// well as for each used version, such that some combination of these
    /// exemptions can satisfy any criteria.
    struct PotentialExemption<'a> {
        version: &'a Version,
        max_criteria: CriteriaSet,
        useful_criteria: CriteriaSet,
        suggest: bool,
        dependency_criteria: &'a DependencyCriteria,
        notes: &'a Option<String>,
    }

    impl<'a> PotentialExemption<'a> {
        /// Check if the exemption is "special" (i.e. if it is `suggest = false`
        /// or has `dependency_criteria`). We avoid removing special exemptions
        /// if they could be applicable.
        fn is_special(&self) -> bool {
            !self.suggest || !self.dependency_criteria.is_empty()
        }
    }

    let no_dependency_criteria = DependencyCriteria::new();
    let mut potential_exemptions = SortedMap::<PackageStr<'_>, Vec<PotentialExemption<'_>>>::new();

    loop {
        // Try to vet. We only probe shallowly as we only want to add exemptions
        // which we're certain of the requirements for. We'll loop around again
        // to add more audits until we successfully vet.
        let (results, conclusion) =
            resolve_core(&graph, store, &criteria_mapper, ResolveDepth::Shallow);

        // We only need to do more work here if we have any failures which we
        // can work with.
        let fail = match &conclusion {
            Conclusion::FailForVet(fail) => fail,
            Conclusion::FailForViolationConflict(..) => {
                // Also force an update even if we're seeing a violation
                // conflict (to save the potentially-newly-imported violation),
                // although our caller is unlikely to commit these changes.
                store.imports =
                    store.get_updated_imports_file(&graph, &conclusion, force_update_imports);
                return Err(RegenerateExemptionsError::ViolationConflict);
            }
            Conclusion::Success(..) => {
                // We succeeded! Whatever exemptions we've recorded so-far are
                // suficient, so we're done. Record any imports which ended up
                // being required for the vet to pass.
                store.imports =
                    store.get_updated_imports_file(&graph, &conclusion, force_update_imports);
                return Ok(());
            }
        };

        let mut made_progress = false;
        let mut update_useful_criteria =
            |potential: &mut PotentialExemption<'_>, new_criteria: &CriteriaSet| {
                if potential.useful_criteria.contains(new_criteria) {
                    return;
                }
                made_progress = true;
                potential.useful_criteria.unioned_with(new_criteria);
            };

        for (&failure_idx, failure) in &fail.failures {
            let package = &graph.nodes[failure_idx];
            let result = &results[failure_idx];

            trace!("minimizing exemptions for {}", package.name);

            let potential_exemptions =
                potential_exemptions.entry(package.name).or_insert_with(|| {
                    let existing_exemptions = old_exemptions
                        .get(package.name)
                        .map(|v| &v[..])
                        .unwrap_or(&[]);
                    // First, we will consider all existing exemptions in the
                    // order they appear in the exemption list to satisfy our
                    // criteria.
                    let mut potentials: Vec<_> = existing_exemptions
                        .iter()
                        .map(|exemption| {
                            let mut potential = PotentialExemption {
                                version: &exemption.version,
                                max_criteria: criteria_mapper.all_criteria(),
                                useful_criteria: criteria_mapper.no_criteria(),
                                suggest: exemption.suggest,
                                dependency_criteria: &exemption.dependency_criteria,
                                notes: &exemption.notes,
                            };
                            // We don't allow special exemptions (criteria with
                            // `suggest = false` or `dependency_criteria`) to
                            // expand the allowed criteria, so record the
                            // existing criteria as our maximum.
                            // We also don't allow expanding criteria if we
                            // aren't allowing new exemptions.
                            if potential.is_special() || !allow_new_exemptions {
                                potential.max_criteria = criteria_mapper
                                    .criteria_from_namespaced_list(
                                        &CriteriaNamespace::Local,
                                        &exemption.criteria,
                                    );
                            }
                            potential
                        })
                        .collect();
                    // The existing exemptions are the only potential exemptions
                    // unless we're allowing adding new exemptions.
                    if allow_new_exemptions {
                        // Next, for criteria with `suggest = false` (but without
                        // `dependency_criteria`), we'll consider adding a
                        // suggestable expanded exemption at the same version
                        // without criteria limitations, to try to pin exemptions at
                        // specific past versions.
                        for exemption in existing_exemptions {
                            if !exemption.suggest && exemption.dependency_criteria.is_empty() {
                                potentials.push(PotentialExemption {
                                    version: &exemption.version,
                                    max_criteria: criteria_mapper.all_criteria(),
                                    useful_criteria: criteria_mapper.no_criteria(),
                                    suggest: true,
                                    dependency_criteria: &no_dependency_criteria,
                                    notes: &exemption.notes,
                                })
                            }
                        }
                        // Then, if none of those apply, we'll consider adding a new
                        // exemption for each version in the DepGraph.
                        potentials.extend(
                            pkg_versions_by_name
                                .get(package.name)
                                .expect("no versions of failed package?")
                                .iter()
                                .map(|version| PotentialExemption {
                                    version,
                                    max_criteria: criteria_mapper.all_criteria(),
                                    useful_criteria: criteria_mapper.no_criteria(),
                                    suggest: true,
                                    dependency_criteria: &no_dependency_criteria,
                                    notes: &None,
                                }),
                        );
                    }
                    potentials
                });

            'min_criteria: for criteria_idx in
                criteria_mapper.minimal_indices(failure.criteria_failures.confident())
            {
                let implied = &criteria_mapper.implied_criteria[criteria_idx];

                // In the first pass, try to satisfy as many implied criteria as
                // possible using "special" potential exemptions (i.e. those
                // with `suggest = false` or `dependency_criteria`).
                //
                // We always want to prioritize marking all "special" exemptions
                // which may be applicable as "used", as they may have different
                // conditions which will be relevant to keep the number of
                // suggested exemptions down.
                let mut missed_criteria = false;
                for implied_idx in implied.indices() {
                    // Check if this implied criteria actually failed, if it
                    // didn't, we don't need to add any new exemptions for it.
                    let reachable_from_target = match &result.search_results[implied_idx] {
                        SearchResult::Disconnected {
                            reachable_from_target,
                            ..
                        } => reachable_from_target,
                        _ => continue,
                    };
                    let mut found = false;
                    for potential in &mut potential_exemptions[..] {
                        if potential.is_special()
                            && potential.max_criteria.has_criteria(implied_idx)
                            && reachable_from_target.contains(&Some(potential.version))
                        {
                            // We found a "special" exemption which matches!
                            // Record the criteria we're using and that we found
                            // something, but continue to see if we find any
                            // other "special" exemptions.
                            found = true;
                            update_useful_criteria(
                                potential,
                                &criteria_mapper.implied_criteria[implied_idx],
                            );
                        }
                    }
                    if !found {
                        missed_criteria = true;
                    }
                }
                // If we were able to satisfy all criteria with only "special"
                // exemptions, we're done!
                if !missed_criteria {
                    continue;
                }

                let reachable_from_target = match &result.search_results[criteria_idx] {
                    SearchResult::Disconnected {
                        reachable_from_target,
                        ..
                    } => reachable_from_target,
                    _ => unreachable!("minimal criteria didn't actually fail?"),
                };

                // In the second pass, we'll take the first applicable exemption
                // which we're able to find, and ensure that its criteria
                // satisfies what we're looking for.
                for potential in &mut potential_exemptions[..] {
                    if potential.max_criteria.has_criteria(criteria_idx)
                        && reachable_from_target.contains(&Some(potential.version))
                    {
                        update_useful_criteria(
                            potential,
                            &criteria_mapper.implied_criteria[criteria_idx],
                        );
                        continue 'min_criteria;
                    }
                }

                if allow_new_exemptions {
                    // We should always find an exemption which satisfies the
                    // criteria due to us adding a potential exemption for each
                    // failed version which can satisfy any criteria.
                    unreachable!("couldn't find an exemption which satisfies the criteria?");
                }

                // If we're not allowing new exemptions, we at least know that
                // the vet _can_ pass with the existing set of exemptions.
                // Conservatively enable every criteria for every existing
                // exemption for this crate.
                for potential in &mut potential_exemptions[..] {
                    let new_criteria = potential.max_criteria.clone();
                    update_useful_criteria(potential, &new_criteria);
                }
                break;
            }
        }

        if made_progress {
            // Update `store.config.exemptions` to reflect changed exemptions and
            // loop back around.
            store.config.exemptions = potential_exemptions
                .iter()
                .filter_map(|(&package_name, potential)| {
                    let mut exemptions: Vec<_> = potential
                        .iter()
                        .filter(|potential| !potential.useful_criteria.is_empty())
                        .map(|potential| ExemptedDependency {
                            version: potential.version.clone(),
                            criteria: criteria_mapper
                                .criteria_names(&potential.useful_criteria)
                                .map(|criteria| criteria.to_owned().into())
                                .collect(),
                            suggest: potential.suggest,
                            dependency_criteria: potential.dependency_criteria.clone(),
                            notes: potential.notes.clone(),
                        })
                        .collect();
                    exemptions.sort();
                    if exemptions.is_empty() {
                        None
                    } else {
                        Some((package_name.to_owned(), exemptions))
                    }
                })
                .collect();
        } else {
            assert!(
                !allow_new_exemptions,
                "failed to make progress while allowing new exemptions?"
            );
            store.config.exemptions = old_exemptions.clone();
        }
    }
}