check_deprule/dependency_graph/
mod.rs

1use anyhow::{Error, anyhow};
2use cargo_metadata::{DependencyKind, Metadata, Package, PackageId};
3use petgraph::graph::NodeIndex;
4use petgraph::stable_graph::StableGraph;
5use petgraph::visit::Dfs;
6use std::collections::HashMap;
7
8pub(crate) mod formatter;
9pub mod tree;
10
11#[derive(Debug, Clone)]
12pub struct Graph {
13    pub graph: StableGraph<Package, DependencyKind>,
14    pub nodes: HashMap<PackageId, NodeIndex>,
15    pub root: Option<PackageId>,
16}
17
18#[derive(Debug, Clone, Default)]
19pub struct DependencyGraphBuildConfigs {
20    no_dev_dependencies: bool,
21}
22impl DependencyGraphBuildConfigs {
23    pub fn new(no_dev_dependencies: bool) -> Self {
24        Self {
25            no_dev_dependencies,
26        }
27    }
28}
29
30pub fn build_dependency_graph(
31    metadata: Metadata,
32    config: DependencyGraphBuildConfigs,
33) -> Result<Graph, Error> {
34    let resolve = metadata.resolve.unwrap();
35
36    let mut graph = Graph {
37        graph: StableGraph::new(),
38        nodes: HashMap::new(),
39        root: resolve.root,
40    };
41
42    for package in metadata.packages {
43        let id = package.id.clone();
44        let index = graph.graph.add_node(package);
45        graph.nodes.insert(id, index);
46    }
47
48    for node in resolve.nodes {
49        if node.deps.len() != node.dependencies.len() {
50            return Err(anyhow!("cargo tree requires cargo 1.41 or newer"));
51        }
52
53        let from = graph.nodes[&node.id];
54        for dep in node.deps {
55            if dep.dep_kinds.is_empty() {
56                return Err(anyhow!("cargo tree requires cargo 1.41 or newer"));
57            }
58
59            // https://github.com/rust-lang/cargo/issues/7752
60            let mut kinds = vec![];
61            for kind in dep.dep_kinds {
62                if !kinds.iter().any(|k| *k == kind.kind) {
63                    kinds.push(kind.kind);
64                }
65            }
66
67            let to = graph.nodes[&dep.pkg];
68            for kind in kinds {
69                if config.no_dev_dependencies && kind == DependencyKind::Development {
70                    continue;
71                }
72
73                graph.graph.add_edge(from, to, kind);
74            }
75        }
76    }
77
78    // prune nodes not reachable from the root package (directionally)
79    if let Some(root) = &graph.root {
80        let mut dfs = Dfs::new(&graph.graph, graph.nodes[root]);
81        while dfs.next(&graph.graph).is_some() {}
82
83        let g = &mut graph.graph;
84        graph.nodes.retain(|_, idx| {
85            if !dfs.discovered.contains(idx.index()) {
86                g.remove_node(*idx);
87                false
88            } else {
89                true
90            }
91        });
92    }
93
94    Ok(graph)
95}
check_deprule/dependency_graph/mod.rs

check_deprule/dependency_graph/
mod.rs
