pets_tools 0.2.0

MusKitty multi-repo source management CLI — one command to clone, build, test, push, and publish 9 independent crate repositories
//! Topological ordering of crates via Kahn's algorithm.
//!
//! Computes build/publish levels from the dependency graph defined in repos.toml.
//! No hand-written levels — derived automatically from `deps` fields.

use crate::config::{Config, ResolvedRepo};
use std::collections::{HashMap, HashSet, VecDeque};

/// Topological result: levels of crate indices (each level can be built in parallel).
#[derive(Debug)]
pub struct Topology {
    /// Each inner vec is one topological level — repos within a level have no
    /// interdependencies and can be processed in parallel.
    pub levels: Vec<Vec<usize>>,
    /// Flat topological order (deps before dependents), for sequential commands.
    #[allow(dead_code)]
    pub order: Vec<usize>,
}

impl Topology {
    /// Compute topology from config's crate repos (excludes main_repo).
    ///
    /// Returns an error if a dependency cycle is detected.
    pub fn compute(config: &Config) -> Result<Self, String> {
        let n = config.repos.len();
        if n == 0 {
            return Ok(Topology {
                levels: vec![],
                order: vec![],
            });
        }

        // name → index
        let name_to_idx: HashMap<&str, usize> = config
            .repos
            .iter()
            .enumerate()
            .map(|(i, r)| (r.name.as_str(), i))
            .collect();

        // Build adjacency: deps[i] = indices that crate i depends on BEFORE it
        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); // dep → dependent
                    in_degree[i] += 1;
                }
            }
            // dev_deps are also required for building/tests
            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;
                }
            }
        }

        // Kahn's algorithm
        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 {
            // Cycle detected — report remaining nodes
            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 })
    }

    /// Get the names of repos at each level.
    #[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;

    /// The 9-crate MusKitty dependency graph as it appears in repos.toml.
    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();

        // Levels: [dom, css-tokenizer, html5-tokenizer] → [css-parser, html5-parser]
        //        → [css] → [css-values, cssom, selectors]
        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);

        // Every crate appears exactly once.
        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"));
    }
}