cargo_msrv/dependency_graph/
mod.rs

1use cargo_metadata::{Package, PackageId};
2use petgraph::visit::Dfs;
3use std::collections::HashMap;
4
5pub(crate) mod resolver;
6
7type PackageGraphIndex = usize;
8// NB: stable graph because we need our DependencyGraph::index to be able to bridge between id's
9//  even after removals, which we do to remove dev- and build dependencies.
10type PackageGraph =
11    petgraph::stable_graph::StableDiGraph<cargo_metadata::Package, (), PackageGraphIndex>;
12
13/// A graph of dependencies from a designated root crate
14///
15/// Why a graph instead of simply a set of packages?
16/// To find the MSRV, all we need is the set, however, to locate where that dependency originates from,
17/// it is useful to have a graph.
18#[derive(Clone, Debug)]
19pub struct DependencyGraph {
20    // Useful to translate between the packages known to cargo_metadata and our petgraph.
21    index: HashMap<PackageId, PackageGraphIndex>,
22    // A directed graph of packages
23    packages: PackageGraph,
24    // The root crate is the crate we're creating the dependency graph for.
25    root_crate: PackageId,
26}
27
28impl DependencyGraph {
29    pub fn empty(root_crate: PackageId) -> Self {
30        Self {
31            index: HashMap::default(),
32            packages: PackageGraph::with_capacity(0, 0),
33            root_crate,
34        }
35    }
36
37    pub fn with_capacity(root_crate: PackageId, cap: usize) -> Self {
38        Self {
39            index: HashMap::default(),
40            packages: PackageGraph::with_capacity(cap, cap),
41            root_crate,
42        }
43    }
44
45    pub fn index(&self) -> &HashMap<PackageId, PackageGraphIndex> {
46        &self.index
47    }
48
49    pub fn packages(&self) -> &PackageGraph {
50        &self.packages
51    }
52
53    pub fn root_crate(&self) -> &PackageId {
54        &self.root_crate
55    }
56}
57
58impl PartialEq for DependencyGraph {
59    fn eq(&self, other: &Self) -> bool {
60        fn packages(graph: &DependencyGraph) -> Vec<&Package> {
61            let package_id = graph.root_crate();
62            let root_index = graph.index()[package_id].into();
63
64            let mut res = Vec::with_capacity(graph.packages().node_count());
65
66            while let Some(dep) = Dfs::new(graph.packages(), root_index).next(graph.packages()) {
67                let package = &graph.packages()[dep];
68                res.push(package);
69            }
70
71            res
72        }
73
74        self.root_crate() == other.root_crate() && packages(self) == packages(other)
75    }
76}
cargo_msrv/dependency_graph/mod.rs

cargo_msrv/dependency_graph/
mod.rs
