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::*;
use crate::config::Config;
const NINE_CRATES: &str = r#"
[project]
name = "MusKitty"
root = "/p"
crates_dir = "/p/crates"
[main_repo]
name = "MusKitty"
dir = "/p"
url = "u"
token_key = "main"
[[repos]]
name = "muskitty-dom"
dir = "crates/muskitty-dom"
url = "u"
[[repos]]
name = "muskitty-css-tokenizer"
dir = "crates/muskitty-css-tokenizer"
url = "u"
[[repos]]
name = "muskitty-html5-tokenizer"
dir = "crates/muskitty-html5-tokenizer"
url = "u"
[[repos]]
name = "muskitty-css-parser"
dir = "crates/muskitty-css-parser"
url = "u"
deps = ["muskitty-css-tokenizer"]
[[repos]]
name = "muskitty-html5-parser"
dir = "crates/muskitty-html5-parser"
url = "u"
deps = ["muskitty-dom", "muskitty-html5-tokenizer"]
[[repos]]
name = "muskitty-css"
dir = "crates/muskitty-css"
url = "u"
deps = ["muskitty-css-tokenizer", "muskitty-css-parser"]
[[repos]]
name = "muskitty-css-values"
dir = "crates/muskitty-css-values"
url = "u"
deps = ["muskitty-css"]
[[repos]]
name = "muskitty-cssom"
dir = "crates/muskitty-cssom"
url = "u"
deps = ["muskitty-css"]
[[repos]]
name = "muskitty-selectors"
dir = "crates/muskitty-selectors"
url = "u"
deps = ["muskitty-css"]
dev_deps = ["muskitty-dom"]
"#;
fn nine_crate_config() -> Config {
Config::parse(NINE_CRATES).expect("valid nine-crate config")
}
#[test]
fn topo_matches_expected_levels() {
let cfg = nine_crate_config();
let topo = Topology::compute(&cfg).unwrap();
assert_eq!(topo.levels.len(), 4);
assert_eq!(topo.levels[0].len(), 3);
assert_eq!(topo.levels[1].len(), 2);
assert_eq!(topo.levels[2].len(), 1);
assert_eq!(topo.levels[3].len(), 3);
assert_eq!(topo.order.len(), 9);
let mut seen: Vec<&str> = topo
.order
.iter()
.map(|&i| cfg.repos[i].name.as_str())
.collect();
seen.sort_unstable();
assert_eq!(
seen,
vec![
"muskitty-css",
"muskitty-css-parser",
"muskitty-css-tokenizer",
"muskitty-css-values",
"muskitty-cssom",
"muskitty-dom",
"muskitty-html5-parser",
"muskitty-html5-tokenizer",
"muskitty-selectors",
]
);
}
#[test]
fn cycle_is_detected() {
let toml = r#"
[project]
name = "P"
root = "/p"
[main_repo]
name = "M"
dir = "/p"
url = "u"
token_key = "main"
[[repos]]
name = "a"
dir = "crates/a"
url = "u"
deps = ["b"]
[[repos]]
name = "b"
dir = "crates/b"
url = "u"
deps = ["a"]
"#;
let cfg = Config::parse(toml).unwrap();
let err = Topology::compute(&cfg).unwrap_err();
assert!(err.contains("cycle"));
}
}