cat-fetch 0.1.1

MusKitty multi-repo source management CLI — one command to clone, build, test, push, and publish 8 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::*;

    #[test]
    fn test_topology_matches_expected() {
        // This validates the computed topology against the known dependency graph.
        // muskitty-dom (0) → html5-parser (5) ...
        // css-tokenizer (2) → css-parser (4) → css (6) → selectors (7)
        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],    // dom → html5-parser
            vec![3, 5], // css-tokenizer → css-parser, css
            vec![4],    // html5-tokenizer → html5-parser
            vec![5],    // css-parser → css
            vec![],     // html5-parser
            vec![6],    // css → selectors
            vec![],     // selectors
        ];

        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);
        }

        // Level 0: dom, css-tokenizer, html5-tokenizer (3 roots)
        assert_eq!(levels[0].len(), 3, "Level 0 should have 3 root crates");
        // Level 1: css-parser, html5-parser
        assert_eq!(levels[1].len(), 2, "Level 1 should have 2 crates");
        // Level 2: css
        assert_eq!(levels[2].len(), 1, "Level 2 should have 1 crate");
        // Level 3: selectors
        assert_eq!(levels[3].len(), 1, "Level 3 should have 1 crate");
        assert_eq!(order.len(), n, "Should cover all {} crates", n);
    }
}