arcature-cli 2026.2.0

//! Deterministic topological sort with cycle detection (RV2.4).
//!
//! Uses Kahn's algorithm (BFS-based) with BTree-ordered iteration so the
//! output is deterministic: the same input always produces the same order.
//! Leaves (no dependencies) come first; dependents come later. A cycle is
//! reported as an error with the nodes involved.

use std::collections::{BTreeMap, BTreeSet};

/// The error returned when a topological sort encounters a cycle.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct TopoError {
    /// The nodes involved in the detected cycle, sorted deterministically.
    pub cycle: Vec<String>,
}

impl std::fmt::Display for TopoError {
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            formatter,
            "dependency cycle detected among: {}",
            self.cycle.join(", ")
        )
    }
}

impl std::error::Error for TopoError {}

/// Compute a deterministic topological ordering of `nodes`.
///
/// `edges` maps each node to the set of nodes it *depends on* (its
/// prerequisites). The output is ordered so every prerequisite appears
/// before the node that depends on it. Ties are broken by BTree name
/// order for determinism.
///
/// Returns `Err(TopoError)` if the graph contains a cycle. The error
/// lists the nodes still in the graph when no zero-in-degree node
/// remains — these are the nodes involved in (or reachable from) the
/// cycle.
pub(crate) fn topological_order(
    edges: &BTreeMap<String, BTreeSet<String>>,
) -> Result<Vec<String>, TopoError> {
    // in_degree[node] = number of prerequisites not yet emitted.
    let mut in_degree: BTreeMap<String, usize> = BTreeMap::new();
    // dependents[node] = set of nodes that depend on `node`.
    let mut dependents: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();

    for (node, deps) in edges {
        in_degree.entry(node.clone()).or_insert(0);
        dependents.entry(node.clone()).or_default();
        for dep in deps {
            // A dep may not be a key in edges (external or missing).
            in_degree.entry(dep.clone()).or_insert(0);
            dependents.entry(dep.clone()).or_default();
            dependents.get_mut(dep).unwrap().insert(node.clone());
            *in_degree.get_mut(node).unwrap() += 1;
        }
    }

    let mut queue: BTreeSet<String> = in_degree
        .iter()
        .filter(|(_, deg)| **deg == 0)
        .map(|(name, _)| name.clone())
        .collect();

    let mut result = Vec::with_capacity(in_degree.len());
    let total = in_degree.len();

    while let Some(node) = queue.iter().next().cloned() {
        queue.remove(&node);
        result.push(node.clone());

        if let Some(deps) = dependents.get(&node) {
            for dep in deps {
                let deg = in_degree.get_mut(dep).unwrap();
                *deg -= 1;
                if *deg == 0 {
                    queue.insert(dep.clone());
                }
            }
        }
    }

    if result.len() == total {
        Ok(result)
    } else {
        // Remaining nodes are in or reachable from a cycle.
        let remaining: Vec<String> = in_degree
            .iter()
            .filter(|&(_, deg)| *deg > 0)
            .map(|(name, _)| name.clone())
            .collect();
        Err(TopoError { cycle: remaining })
    }
}

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

    fn graph(edges: &[(&str, &[&str])]) -> BTreeMap<String, BTreeSet<String>> {
        edges
            .iter()
            .map(|(node, deps)| {
                (
                    (*node).to_string(),
                    deps.iter().map(|d| (*d).to_string()).collect(),
                )
            })
            .collect()
    }

    #[test]
    fn empty_graph_produces_empty_order() {
        let g: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
        assert_eq!(topological_order(&g).unwrap(), Vec::<String>::new());
    }

    #[test]
    fn single_node_no_deps() {
        let g = graph(&[("a", &[])]);
        assert_eq!(topological_order(&g).unwrap(), vec!["a"]);
    }

    #[test]
    fn linear_chain() {
        // c depends on b depends on a → order: a, b, c
        let g = graph(&[("a", &[]), ("b", &["a"]), ("c", &["b"])]);
        assert_eq!(topological_order(&g).unwrap(), vec!["a", "b", "c"]);
    }

    #[test]
    fn independent_nodes_sorted_by_name() {
        let g = graph(&[("c", &[]), ("a", &[]), ("b", &[])]);
        assert_eq!(topological_order(&g).unwrap(), vec!["a", "b", "c"]);
    }

    #[test]
    fn diamond_dependency() {
        // d depends on b and c; b and c depend on a → a first, then b/c, then d
        let g = graph(&[("a", &[]), ("b", &["a"]), ("c", &["a"]), ("d", &["b", "c"])]);
        let order = topological_order(&g).unwrap();
        assert_eq!(order[0], "a");
        assert_eq!(order[3], "d");
        // b before c (BTree tie-break)
        assert_eq!(order[1], "b");
        assert_eq!(order[2], "c");
    }

    #[test]
    fn self_cycle_detected() {
        let g = graph(&[("a", &["a"])]);
        let err = topological_order(&g).expect_err("self-cycle");
        assert_eq!(err.cycle, vec!["a"]);
    }

    #[test]
    fn two_node_cycle_detected() {
        let g = graph(&[("a", &["b"]), ("b", &["a"])]);
        let err = topological_order(&g).expect_err("cycle");
        assert!(err.cycle.contains(&"a".to_string()));
        assert!(err.cycle.contains(&"b".to_string()));
    }

    #[test]
    fn three_node_cycle_detected() {
        let g = graph(&[("a", &["c"]), ("b", &["a"]), ("c", &["b"])]);
        let err = topological_order(&g).expect_err("cycle");
        assert_eq!(err.cycle.len(), 3);
    }

    #[test]
    fn deterministic_repeated() {
        let g = graph(&[("z", &["a"]), ("a", &[]), ("m", &["a", "z"]), ("b", &["a"])]);
        let first = topological_order(&g).unwrap();
        let second = topological_order(&g).unwrap();
        assert_eq!(first, second);
        // a first, then b/z (BTree order), then m
        assert_eq!(first, vec!["a", "b", "z", "m"]);
    }

    #[test]
    fn external_dependency_not_in_graph_is_ignored() {
        // 'a' depends on 'external' which is not a node in the graph.
        let g = graph(&[("a", &["external"])]);
        // 'external' has in_degree 0 and appears in output.
        let order = topological_order(&g).unwrap();
        assert!(order.contains(&"external".to_string()));
        assert!(order.contains(&"a".to_string()));
    }
}