1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

//! Dependency graphs computed from `Cargo.lock` files.
//!
//! Uses the `petgraph` crate for modeling the dependency structure.

pub use petgraph;

use crate::{
    error::{Error, ErrorKind},
    lockfile::Lockfile,
    package::{self, Package},
};
use petgraph::graph::NodeIndex;
use std::collections::BTreeMap as Map;

/// Dependency graph (modeled using `petgraph`)
pub type Graph = petgraph::graph::Graph<Package, Edge>;

/// Nodes in the dependency graph
pub type Nodes = Map<package::Release, NodeIndex>;

/// Dependency graph computed from a `Cargo.lock` file
#[derive(Clone, Debug)]
pub struct DependencyGraph {
    /// Dependency graph for a particular package
    graph: Graph,

    /// Package data associated with nodes in the graph
    nodes: Nodes,

    /// Root node of the dependency graph
    root_node: NodeIndex,
}

impl DependencyGraph {
    /// Construct a new dependency graph for the given [`Lockfile`]
    pub fn new(lockfile: &Lockfile) -> Result<Self, Error> {
        let mut graph = Graph::new();
        let mut nodes = Map::new();

        let root_package = find_root_package(lockfile)?;
        let root_node = graph.add_node(root_package.clone());

        // TODO(tarcieri): index nodes by (name, version) tuples
        nodes.insert(root_package.release(), root_node);

        let mut dep_graph = Self {
            graph,
            nodes,
            root_node,
        };

        dep_graph.add_dependencies(lockfile, root_package, root_node);
        Ok(dep_graph)
    }

    /// Get the dependency graph
    pub fn graph(&self) -> &Graph {
        &self.graph
    }

    /// Get the nodes of the dependency graph
    pub fn nodes(&self) -> &Nodes {
        &self.nodes
    }

    /// Get the root package in the dependency graph
    pub fn root_package(&self) -> &Package {
        &self.graph[self.root_node]
    }

    /// Add the dependencies of a given package to the given node
    fn add_dependencies(&mut self, lockfile: &Lockfile, package: &Package, parent: NodeIndex) {
        for dependency in lockfile.dependencies(package) {
            let node = self.graph.add_node(dependency.clone());
            self.nodes.insert(dependency.release(), node);
            self.graph.add_edge(parent, node, Edge);
            self.add_dependencies(lockfile, dependency, node);
        }
    }
}

/// Find the root package in the given lockfile
fn find_root_package(lockfile: &Lockfile) -> Result<&Package, Error> {
    let mut dependency_counts = Map::new();

    for package in &lockfile.packages {
        dependency_counts.entry(&package.name).or_insert(0);

        for dependency in &package.dependencies {
            *dependency_counts.entry(&dependency.name).or_insert(0) += 1;
        }
    }

    let root_package_name = *dependency_counts
        .iter()
        .find(|(_, count)| **count == 0)
        .ok_or_else(|| format_err!(ErrorKind::Parse, "couldn't find root package"))?
        .0;

    Ok(lockfile
        .packages
        .iter()
        .find(|package| &package.name == root_package_name)
        .unwrap())
}

/// Graph edges. These are presently just a placeholder.
// TODO(tarcieri): use these for e.g. VersionReqs?
#[derive(Clone, Debug)]
pub struct Edge;

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

    /// Load the `rustsec` crate's `Cargo.lock`
    fn load_lockfile() -> Lockfile {
        Lockfile::load("Cargo.lock").unwrap()
    }

    #[test]
    fn root_package() {
        let lockfile = load_lockfile();
        assert_eq!(
            find_root_package(&lockfile).unwrap().name.as_str(),
            "cargo-lock"
        );
    }

    #[test]
    fn computed_graph() {
        let lockfile = load_lockfile();
        let dependencies = DependencyGraph::new(&lockfile).unwrap();
        let root_package = dependencies.root_package();
        assert_eq!(root_package.name.as_str(), "cargo-lock");

        // TODO(tarcieri): test dependency graph construction
    }
}