use crate::{
config::Config,
dep::{DepKind, ResolvedDep},
error::{Error, Result},
project::RootDepsMap,
};
use std::{collections::HashMap, fmt, io::Write};
pub type Node = usize;
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Copy, Clone)]
pub struct Edge(pub Node, pub Node);
impl Edge {
pub fn label<W: Write>(&self, w: &mut W, dg: &DepGraph) -> Result<()> {
use crate::dep::DepKind::{Build, Dev, Optional, Regular, Unknown};
let parent = dg.get(self.0).unwrap();
let child = dg.get(self.1).unwrap();
// Special case: always color edge from root to root dep by its actual root dependency kind.
// Otherwise, the root dep could also be a dep of a regular dep which will cause the root ->
// root dep edge to appear regular, which is misleading as it is not regular in Cargo.toml.
let child_kind = if let Some(dep_kinds_map) = &dg.root_deps_map.get(&parent.name) {
if let Some(kinds) = dep_kinds_map.get(&child.name) {
if kinds.contains(&Regular) {
Regular
} else if kinds.contains(&Build) {
Build
} else if kinds.contains(&Dev) {
Dev
} else if kinds.contains(&Optional) {
Optional
} else {
Unknown
}
} else {
return Err(Error::Generic(format!(
"Crate '{}' is not a dependency of a root crate. This is probably a logic \
error.",
child.name
)));
}
} else {
child.kind()
};
match (parent.kind(), child_kind) {
(Regular, Regular) => writeln!(w, ";")?,
(Build, _) | (Regular, Build) => writeln!(w, " [color=purple, style=dashed];")?,
(Dev, _) | (Regular, Dev) => writeln!(w, " [color=blue, style=dashed];")?,
(Optional, _) | (Regular, Optional) => writeln!(w, " [color=red, style=dashed];")?,
_ => writeln!(w, " [color=orange, style=dashed];")?,
}
Ok(())
}
}
impl fmt::Display for Edge {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let &Self(il, ir) = self;
write!(f, "n{} -> n{}", il, ir)
}
}
#[derive(Debug)]
pub struct DepGraph {
/// Vector of nodes containing resolved dependency information as well as the indices of parent
/// and children nodes.
pub nodes: Vec<ResolvedDep>,
pub edges: Vec<Edge>,
pub root_deps_map: RootDepsMap,
pub cfg: Config,
}
impl DepGraph {
pub fn new(cfg: Config) -> Self {
Self {
nodes: vec![],
edges: vec![],
root_deps_map: HashMap::new(),
cfg,
}
}
/// Performs a topological sort on the edges.
pub fn topological_sort(&mut self) -> Result<()> {
// Create a clone of the nodes list so we can remove parents and children without affecting
// the original list. We work on the original list of edges, clearing it as we go, because
// we construct a new one at the end, in topological order.
let mut graph_nodes = self.nodes.clone();
// Will contain indices of the nodes in sorted order.
let mut l: Vec<Node> = vec![];
// Set of nodes with no incoming edges.
let mut s: Vec<Node> = vec![];
// Populate initial list of start nodes which have no incoming edges.
for (i, node) in self.nodes.iter().enumerate() {
if node.parents.is_empty() {
s.push(i);
}
}
while let Some(n) = s.pop() {
l.push(n);
while let Some(child) = graph_nodes[n].children.pop() {
assert_ne!(n, child);
// Remove the edge from n -> child.
let edge_index = self
.edges
.iter()
.position(|Edge(a, b)| a == &n && b == &child)
.unwrap();
self.edges.remove(edge_index);
let node_index = graph_nodes[child]
.parents
.iter()
.position(|node| *node == n)
.unwrap();
graph_nodes[child].parents.remove(node_index);
// If child has no other parents, it is in the next topological level.
if graph_nodes[child].parents.is_empty() {
s.push(child);
}
}
}
if self.edges.is_empty() {
// Add back the edges, this time in topological order.
for n in l.iter() {
'child_loop: for child in self.nodes[*n].children.iter() {
// Push an edge for each child, unless filtering of transitive deps is enabled,
// in which case skip to the next child if a transitive dependency exists to the
// child through one of the other children nodes.
if !self.cfg.transitive_deps {
for c in self.nodes[*n].children.iter().filter(|c| *c != child) {
if self.transitive_dep(*c, *child) {
continue 'child_loop;
}
}
}
self.edges.push(Edge(*n, *child));
}
}
Ok(())
} else {
Err(Error::Generic("Cycle detected in dependency graph".into()))
}
}
/// Sets the kind of each dependency based on how the dependencies are declared in the manifest.
pub fn set_resolved_kind(&mut self) -> Result<()> {
// Set regular kind for all root nodes.
for node in self.nodes.iter_mut() {
if self.root_deps_map.contains_key(&node.name) {
node.is_regular = true;
}
}
// Iterate over edges in topologically-sorted order to propogate the kinds.
for ed in self.edges.iter() {
// Get the parent attributes and drop the `parent` binding to avoid having two
// simultaneous mutable references.
let (
parent_name,
parent_depth,
parent_regular,
parent_build,
parent_dev,
parent_optional,
) = {
let parent = &mut self.nodes[ed.0];
// If the parent depth isn't set yet, set it to 0.
if parent.depth.is_none() {
parent.depth = Some(0);
}
(
parent.name.to_string(),
parent.depth,
parent.is_regular,
parent.is_build,
parent.is_dev,
parent.is_optional,
)
};
let mut child = &mut self.nodes[ed.1];
// If the child depth isn't set yet, set it based on the parent depth.
if child.depth.is_none() {
child.depth = Some(parent_depth.unwrap() + 1);
}
if let Some(dep_kinds_map) = self.root_deps_map.get(&parent_name) {
// If this is an edge from the root node,
// set the kind based on how the dependency is declared in the manifest file.
if let Some(kinds) = dep_kinds_map.get(&child.name) {
for kind in kinds {
match *kind {
DepKind::Regular => child.is_regular = true,
DepKind::Build => child.is_build = true,
DepKind::Dev => child.is_dev = true,
DepKind::Optional => child.is_optional = true,
_ => (),
}
}
} else {
return Err(Error::Generic(format!(
"Crate '{}' is not a dependency of a root crate. This is probably a logic \
error.",
child.name
)));
}
} else {
// If this is an edge from a dependency node, propagate the kind. This is a set
// of flags because a dependency can appear several times in the graph, and the
// kind of dependency may vary based on the path to that dependency. The flags
// start at false, and once they become true, they stay true.
// ResolvedDep::kind() will pick a kind based on their priority.
if parent_regular {
child.is_regular = true;
}
if parent_build {
child.is_build = true;
}
if parent_dev {
child.is_dev = true;
}
if parent_optional {
child.is_optional = true;
}
}
}
Ok(())
}
/// Forces the version to be displayed on dependencies that have the same name (but a different
/// version) as another dependency.
pub fn show_version_on_duplicates(&mut self) {
// Build a list of node IDs, sorted by the name of the dependency on that node.
let dep_ids_sorted_by_name = {
let mut deps = self.nodes.iter().enumerate().collect::<Vec<_>>();
deps.sort_by_key(|dep| &*dep.1.name);
deps.iter().map(|dep| dep.0).collect::<Vec<_>>()
};
for (i, &dep_id_i) in dep_ids_sorted_by_name
.iter()
.enumerate()
.take(dep_ids_sorted_by_name.len() - 1)
{
// Find other nodes with the same name.
// We need to iterate one more time after the last node to handle the break.
for (j, &dep) in dep_ids_sorted_by_name
.iter()
.enumerate()
.take(dep_ids_sorted_by_name.len() + 1)
.skip(i + 1)
{
// Stop once we've found a node with a different name or reached the end of the
// list.
if j >= dep_ids_sorted_by_name.len()
|| self.nodes[dep_id_i].name != self.nodes[dep].name
{
// If there are at least two nodes with the same name
if j >= i + 2 {
// Set force_write_ver = true on all nodes
// from dep_ids_sorted_by_name[i] to dep_ids_sorted_by_name[j - 1].
// Remember: j is pointing on the next node with a *different* name!
// Remember also: i..j includes i but excludes j.
for &dep_id_k in dep_ids_sorted_by_name.iter().take(j).skip(i) {
self.nodes[dep_id_k].force_write_ver = true;
}
}
break;
}
}
}
}
pub fn add_child(
&mut self,
parent: usize,
dep_name: &str,
dep_ver: &str,
registry: &Option<String>,
) {
let child = self.find_or_add(dep_name, dep_ver, registry);
if parent == child {
return;
}
self.edges.push(Edge(parent, child));
self.nodes[parent].children.push(child);
self.nodes[child].parents.push(parent);
}
pub fn get(&self, id: usize) -> Option<&ResolvedDep> {
if id < self.nodes.len() {
return Some(&self.nodes[id]);
}
None
}
pub fn find(&self, name: &str, ver: &str) -> Option<usize> {
for (i, d) in self.nodes.iter().enumerate() {
if d.name == name && d.ver == ver {
return Some(i);
}
}
None
}
pub fn find_or_add(&mut self, name: &str, ver: &str, registry: &Option<String>) -> usize {
if let Some(i) = self.find(name, ver) {
return i;
}
self.nodes.push(ResolvedDep::new(
name.to_owned(),
ver.to_owned(),
registry.clone(),
));
self.nodes.len() - 1
}
pub fn render_to<W: Write>(self, output: &mut W) -> Result<()> {
// Keep track of all added nodes.
let mut nodes_added = vec![];
writeln!(output, "digraph dependencies {{")?;
// Output all non-subgraph nodes.
for (i, dep) in self.nodes.iter().enumerate() {
// Skip subgraph nodes, will be declared in the subgraph.
if let Some(sub_deps) = &self.cfg.subgraph {
if sub_deps.contains(&dep.name) {
continue;
}
}
// Skip nodes below the maximum depth, if specified.
// These nodes will still be output later if specified in a subgraph.
if let Some(depth) = self.cfg.depth {
// The depth can be None if nodes have been filtered out.
if dep.depth.is_none() || dep.depth.unwrap() > depth {
continue;
}
}
// Skip orphan nodes.
// Orphan nodes will still be output later if specified in a subgraph.
if !self.cfg.include_orphans {
if let DepKind::Unknown = dep.kind() {
continue;
}
}
// Skip registries.
if let Some(registries) = &self.cfg.registries {
if let Some(registry) = &dep.registry {
if !registries.contains(registry) {
continue;
}
} else {
continue;
}
}
// Add the node.
write!(output, "\tn{}", i)?;
dep.label(output, &self)?;
nodes_added.push(i);
}
writeln!(output)?;
// Output any subgraph nodes.
if let Some(sub_deps) = &self.cfg.subgraph {
writeln!(output, "\tsubgraph cluster_subgraph {{")?;
if let Some(sub_name) = &self.cfg.subgraph_name {
writeln!(output, "\t\tlabel=\"{}\";", sub_name)?;
}
writeln!(output, "\t\tcolor=brown;")?;
writeln!(output, "\t\tstyle=dashed;")?;
writeln!(output)?;
for (i, dep) in self.nodes.iter().enumerate() {
if sub_deps.contains(&dep.name) {
write!(output, "\t\tn{}", i)?;
dep.label(output, &self)?;
nodes_added.push(i);
}
}
writeln!(output, "\t}}\n")?;
}
// Output edges.
for ed in &self.edges {
// Only add edges if both nodes exist in the graph.
if !(nodes_added.contains(&ed.0) && nodes_added.contains(&ed.1)) {
continue;
}
write!(output, "\t{}", ed)?;
ed.label(output, &self)?;
}
writeln!(output, "}}")?;
Ok(())
}
// TODO: make this function more efficient with memoization:
// ahead of time, generate a list of all dependencies (direct and indirect)
// for all nodes, and then this function can simply check if child is in
// parent's list of dependencies (or possibly remove this function
// entirely)
fn transitive_dep(&self, parent: usize, child: usize) -> bool {
for c in self.nodes[parent].children.iter() {
if *c == child || self.transitive_dep(*c, child) {
return true;
}
}
false
}
}