use crate::config::{Config, ResolvedRepo};
use std::collections::{HashMap, HashSet, VecDeque};
#[derive(Debug)]
pub struct Topology {
pub levels: Vec<Vec<usize>>,
#[allow(dead_code)]
pub order: Vec<usize>,
}
impl Topology {
pub fn compute(config: &Config) -> Result<Self, String> {
let n = config.repos.len();
if n == 0 {
return Ok(Topology {
levels: vec![],
order: vec![],
});
}
let name_to_idx: HashMap<&str, usize> = config
.repos
.iter()
.enumerate()
.map(|(i, r)| (r.name.as_str(), i))
.collect();
let mut outgoing: Vec<Vec<usize>> = vec![vec![]; n];
let mut in_degree: Vec<usize> = vec![0; n];
for (i, repo) in config.repos.iter().enumerate() {
for dep_name in &repo.deps {
if let Some(&dep_idx) = name_to_idx.get(dep_name.as_str()) {
outgoing[dep_idx].push(i); in_degree[i] += 1;
}
}
for dep_name in &repo.dev_deps {
if let Some(&dep_idx) = name_to_idx.get(dep_name.as_str()) {
outgoing[dep_idx].push(i);
in_degree[i] += 1;
}
}
}
let mut queue: VecDeque<usize> = (0..n).filter(|&i| in_degree[i] == 0).collect();
let mut order: Vec<usize> = Vec::with_capacity(n);
let mut levels: Vec<Vec<usize>> = vec![];
let mut seen: HashSet<usize> = HashSet::new();
while !queue.is_empty() {
let level: Vec<usize> = queue.drain(..).collect();
for &node in &level {
order.push(node);
seen.insert(node);
for &next in &outgoing[node] {
if in_degree[next] > 0 {
in_degree[next] -= 1;
if in_degree[next] == 0 {
queue.push_back(next);
}
}
}
}
levels.push(level);
}
if seen.len() != n {
let remaining: Vec<&str> = (0..n)
.filter(|i| !seen.contains(i))
.map(|i| config.repos[i].name.as_str())
.collect();
return Err(format!(
"Dependency cycle detected among: {}",
remaining.join(", ")
));
}
Ok(Topology { levels, order })
}
#[allow(dead_code)]
pub fn level_names(&self, repos: &[ResolvedRepo]) -> Vec<Vec<String>> {
self.levels
.iter()
.map(|level| level.iter().map(|&i| repos[i].name.clone()).collect())
.collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_topology_matches_expected() {
let n = 7;
let _names: Vec<&str> = vec![
"muskitty-dom",
"muskitty-css-tokenizer",
"muskitty-html5-tokenizer",
"muskitty-css-parser",
"muskitty-html5-parser",
"muskitty-css",
"muskitty-selectors",
];
let outgoing: Vec<Vec<usize>> = vec![
vec![4], vec![3, 5], vec![4], vec![5], vec![], vec![6], vec![], ];
let mut in_degree = vec![0; n];
for edges in &outgoing {
for &v in edges {
in_degree[v] += 1;
}
}
let mut queue: VecDeque<usize> = (0..n).filter(|&i| in_degree[i] == 0).collect();
let mut order = vec![];
let mut levels = vec![];
while !queue.is_empty() {
let level: Vec<usize> = queue.drain(..).collect();
for &node in &level {
order.push(node);
for &next in &outgoing[node] {
in_degree[next] -= 1;
if in_degree[next] == 0 {
queue.push_back(next);
}
}
}
levels.push(level);
}
assert_eq!(levels[0].len(), 3, "Level 0 should have 3 root crates");
assert_eq!(levels[1].len(), 2, "Level 1 should have 2 crates");
assert_eq!(levels[2].len(), 1, "Level 2 should have 1 crate");
assert_eq!(levels[3].len(), 1, "Level 3 should have 1 crate");
assert_eq!(order.len(), n, "Should cover all {} crates", n);
}
}