xbp_deploy/

graph.rs

use std::collections::{HashMap, HashSet, VecDeque};

use crate::error::{DeployError, Result};
use crate::types::ServiceConfigView;

#[derive(Debug, Clone)]
pub struct ServiceNode {
    pub name: String,
    pub depends_on: Vec<String>,
}

#[derive(Debug, Clone, Default)]
pub struct ServiceGraph {
    pub nodes: HashMap<String, ServiceNode>,
}

impl ServiceGraph {
    pub fn from_services(services: &[ServiceConfigView]) -> Self {
        let mut nodes = HashMap::new();
        for svc in services {
            nodes.insert(
                svc.name.clone(),
                ServiceNode {
                    name: svc.name.clone(),
                    depends_on: svc.depends_on.clone(),
                },
            );
        }
        Self { nodes }
    }
}

/// Compute apply order for `selected` service names.
///
/// 1. If `group_order` is non-empty → authoritative (filtered to selected).
/// 2. Else DAG topological sort from `depends_on`.
/// 3. Stable fallback: preserve `selected` order for unconstrained nodes.
pub fn order_services(
    selected: &[String],
    group_order: Option<&[String]>,
    graph: &ServiceGraph,
) -> Result<Vec<String>> {
    if let Some(order) = group_order {
        if !order.is_empty() {
            let selected_set: HashSet<&str> = selected.iter().map(String::as_str).collect();
            let mut out = Vec::new();
            for name in order {
                if selected_set.contains(name.as_str()) {
                    out.push(name.clone());
                }
            }
            // Append any selected not listed in order (end).
            for name in selected {
                if !out.iter().any(|n| n == name) {
                    out.push(name.clone());
                }
            }
            return Ok(out);
        }
    }

    // Validate missing deps among selected.
    let selected_set: HashSet<String> = selected.iter().cloned().collect();
    for name in selected {
        let Some(node) = graph.nodes.get(name) else {
            continue;
        };
        for dep in &node.depends_on {
            if !graph.nodes.contains_key(dep) {
                return Err(DeployError::Graph(format!(
                    "service `{name}` depends on missing service `{dep}`"
                )));
            }
        }
    }

    // Kahn topological sort restricted to selected (+ their selected deps).
    let mut indegree: HashMap<String, usize> = selected
        .iter()
        .map(|n| (n.clone(), 0usize))
        .collect();
    let mut adj: HashMap<String, Vec<String>> = HashMap::new();

    for name in selected {
        let deps = graph
            .nodes
            .get(name)
            .map(|n| n.depends_on.clone())
            .unwrap_or_default();
        for dep in deps {
            if !selected_set.contains(&dep) {
                continue;
            }
            adj.entry(dep.clone()).or_default().push(name.clone());
            *indegree.entry(name.clone()).or_default() += 1;
        }
    }

    let mut queue: VecDeque<String> = selected
        .iter()
        .filter(|n| indegree.get(*n).copied().unwrap_or(0) == 0)
        .cloned()
        .collect();

    // Preserve original relative order for zero-indegree nodes.
    queue.make_contiguous().sort_by_key(|n| {
        selected.iter().position(|s| s == n).unwrap_or(usize::MAX)
    });

    let mut ordered = Vec::new();
    while let Some(node) = queue.pop_front() {
        ordered.push(node.clone());
        if let Some(children) = adj.get(&node) {
            for child in children {
                if let Some(d) = indegree.get_mut(child) {
                    *d = d.saturating_sub(1);
                    if *d == 0 {
                        queue.push_back(child.clone());
                    }
                }
            }
        }
    }

    if ordered.len() != selected.len() {
        return Err(DeployError::Graph(
            "dependency cycle detected among selected services".into(),
        ));
    }
    Ok(ordered)
}

/// Athena group guardrail: operator before runtime when both present.
pub fn enforce_athena_operator_before_runtime(order: &mut Vec<String>) {
    let op = order.iter().position(|s| s == "athena-operator");
    let rt = order.iter().position(|s| s == "athena-runtime");
    if let (Some(i), Some(j)) = (op, rt) {
        if i > j {
            order.swap(i, j);
        }
    }
}

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

    fn svc(name: &str, deps: &[&str]) -> ServiceConfigView {
        ServiceConfigView {
            name: name.into(),
            root_directory: None,
            version: None,
            depends_on: deps.iter().map(|s| (*s).into()).collect(),
            oci: None,
            deploy: None,
        }
    }

    #[test]
    fn group_order_authoritative() {
        let services = vec![svc("a", &[]), svc("b", &[]), svc("c", &[])];
        let graph = ServiceGraph::from_services(&services);
        let order = order_services(
            &["a".into(), "b".into(), "c".into()],
            Some(&["c".into(), "a".into(), "b".into()]),
            &graph,
        )
        .unwrap();
        assert_eq!(order, vec!["c", "a", "b"]);
    }

    #[test]
    fn topo_respects_depends_on() {
        let services = vec![svc("a", &[]), svc("b", &["a"]), svc("c", &["b"])];
        let graph = ServiceGraph::from_services(&services);
        let order = order_services(
            &["c".into(), "b".into(), "a".into()],
            None,
            &graph,
        )
        .unwrap();
        assert_eq!(order, vec!["a", "b", "c"]);
    }

    #[test]
    fn cycle_errors() {
        let services = vec![svc("a", &["b"]), svc("b", &["a"])];
        let graph = ServiceGraph::from_services(&services);
        let err = order_services(&["a".into(), "b".into()], None, &graph).unwrap_err();
        assert!(err.to_string().contains("cycle"));
    }

    #[test]
    fn athena_guardrail() {
        let mut order = vec!["athena-runtime".into(), "athena-operator".into()];
        enforce_athena_operator_before_runtime(&mut order);
        assert_eq!(order[0], "athena-operator");
    }
}