repoverse 0.1.5

//! Dependency graph + topo-sort. Edge: consumer -> dependency.
//! Rollup order is dependencies first (leaves), consumers last (root).

use crate::config::Config;
use anyhow::{bail, Result};
use std::collections::{BTreeMap, BTreeSet, VecDeque};

#[derive(Debug, Clone)]
pub struct Graph {
    /// project path -> set of project paths it consumes (depends on)
    pub deps: BTreeMap<String, BTreeSet<String>>,
}

impl Graph {
    /// Build from `consumes:` in config. (Submodule inference: future — see
    /// decision A; config edges are authoritative today.)
    pub fn from_config(cfg: &Config) -> Graph {
        let name_to_path: BTreeMap<&str, &str> = cfg
            .projects
            .iter()
            .map(|p| (p.name.as_str(), p.path.as_str()))
            .collect();
        let mut deps: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
        for p in &cfg.projects {
            let entry = deps.entry(p.path.clone()).or_default();
            for c in &p.consumes {
                // accept path or name
                let dep_path = name_to_path.get(c.as_str()).copied().unwrap_or(c.as_str());
                entry.insert(dep_path.to_string());
            }
        }
        Graph { deps }
    }

    /// Kahn topo-sort: dependencies before consumers. Errors on cycle.
    pub fn topo_order(&self) -> Result<Vec<String>> {
        let nodes: BTreeSet<&String> = self
            .deps
            .keys()
            .chain(self.deps.values().flatten())
            .collect();
        // indegree = number of unmet dependencies
        let mut indeg: BTreeMap<String, usize> = nodes.iter().map(|n| ((*n).clone(), 0)).collect();
        for d in self.deps.values() {
            for _dep in d {
                // consumer has an edge to each dep; count deps as prerequisites
            }
        }
        for (consumer, ds) in &self.deps {
            *indeg.entry(consumer.clone()).or_insert(0) += ds.len();
        }
        let mut queue: VecDeque<String> = indeg
            .iter()
            .filter(|(_, &v)| v == 0)
            .map(|(k, _)| k.clone())
            .collect();
        // reverse adjacency: dep -> consumers
        let mut consumers: BTreeMap<String, Vec<String>> = BTreeMap::new();
        for (consumer, ds) in &self.deps {
            for dep in ds {
                consumers
                    .entry(dep.clone())
                    .or_default()
                    .push(consumer.clone());
            }
        }
        let mut order = Vec::new();
        while let Some(n) = queue.pop_front() {
            if let Some(cs) = consumers.get(&n) {
                for c in cs {
                    let e = indeg.get_mut(c).unwrap();
                    *e -= 1;
                    if *e == 0 {
                        queue.push_back(c.clone());
                    }
                }
            }
            order.push(n);
        }
        if order.len() != indeg.len() {
            bail!("dependency cycle detected among projects");
        }
        Ok(order)
    }

    /// Projects that consume `path` (need a bump when it changes).
    pub fn consumers_of(&self, path: &str) -> Vec<String> {
        self.deps
            .iter()
            .filter(|(_, ds)| ds.contains(path))
            .map(|(c, _)| c.clone())
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn cfg() -> Config {
        serde_yaml::from_str(
            r#"
version: 1
remotes: { github: { host: github.com } }
projects:
  - { name: acme/lib, path: lib }
  - { name: acme/mid, path: mid, consumes: [lib] }
  - { name: acme/app, path: ., consumes: [mid, lib] }
"#,
        )
        .unwrap()
    }

    #[test]
    fn topo_leaves_first() {
        let g = Graph::from_config(&cfg());
        let o = g.topo_order().unwrap();
        let pos = |p: &str| o.iter().position(|x| x == p).unwrap();
        assert!(pos("lib") < pos("mid"));
        assert!(pos("mid") < pos("."));
        assert!(pos("lib") < pos("."));
    }

    #[test]
    fn consumers_lookup() {
        let g = Graph::from_config(&cfg());
        let mut c = g.consumers_of("lib");
        c.sort();
        assert_eq!(c, vec![".".to_string(), "mid".to_string()]);
    }

    #[test]
    fn cycle_detected() {
        let cfg: Config = serde_yaml::from_str(
            r#"
version: 1
remotes: { github: { host: github.com } }
projects:
  - { name: a/a, path: a, consumes: [b] }
  - { name: a/b, path: b, consumes: [a] }
"#,
        )
        .unwrap();
        let g = Graph::from_config(&cfg);
        assert!(g.topo_order().is_err());
    }
}