nucleus/topology/
dag.rs

1//! Dependency DAG resolution with topological sort.
2//!
3//! Resolves service dependencies into a startup order using Kahn's algorithm.
4//! Detects circular dependencies and generates systemd-compatible ordering
5//! (After=/Requires= edges).
6
7use crate::error::{NucleusError, Result};
8use crate::topology::config::TopologyConfig;
9use std::collections::{BTreeMap, VecDeque};
10
11/// A resolved dependency graph with startup ordering.
12#[derive(Debug, Clone)]
13pub struct DependencyGraph {
14    /// Services in topological order (dependencies first).
15    pub startup_order: Vec<String>,
16
17    /// For each service, the services it must wait for.
18    pub edges: BTreeMap<String, Vec<DependencyEdge>>,
19
20    /// Reverse map: for each service, the services that depend on it.
21    pub dependents: BTreeMap<String, Vec<String>>,
22}
23
24/// A dependency edge with condition metadata.
25#[derive(Debug, Clone)]
26pub struct DependencyEdge {
27    /// The upstream service this depends on.
28    pub service: String,
29    /// Condition: "started" or "healthy".
30    pub condition: String,
31}
32
33impl DependencyGraph {
34    /// Resolve dependencies from a topology config into a startup-ordered graph.
35    ///
36    /// Returns an error if circular dependencies are detected.
37    pub fn resolve(config: &TopologyConfig) -> Result<Self> {
38        let services: Vec<String> = config.services.keys().cloned().collect();
39
40        // Build adjacency list and in-degree map
41        let mut in_degree: BTreeMap<String, usize> = BTreeMap::new();
42        let mut edges: BTreeMap<String, Vec<DependencyEdge>> = BTreeMap::new();
43        let mut dependents: BTreeMap<String, Vec<String>> = BTreeMap::new();
44
45        for name in &services {
46            in_degree.entry(name.clone()).or_insert(0);
47            edges.entry(name.clone()).or_default();
48            dependents.entry(name.clone()).or_default();
49        }
50
51        for (name, svc) in &config.services {
52            for dep in &svc.depends_on {
53                if !config.services.contains_key(&dep.service) {
54                    return Err(NucleusError::ConfigError(format!(
55                        "Service '{}' depends on undefined service '{}'",
56                        name, dep.service
57                    )));
58                }
59                *in_degree.entry(name.clone()).or_insert(0) += 1;
60                edges.entry(name.clone()).or_default().push(DependencyEdge {
61                    service: dep.service.clone(),
62                    condition: dep.condition.clone(),
63                });
64                dependents
65                    .entry(dep.service.clone())
66                    .or_default()
67                    .push(name.clone());
68            }
69        }
70
71        // Kahn's algorithm for topological sort
72        let mut queue: VecDeque<String> = VecDeque::new();
73        for (name, &degree) in &in_degree {
74            if degree == 0 {
75                queue.push_back(name.clone());
76            }
77        }
78
79        let mut order = Vec::new();
80        while let Some(node) = queue.pop_front() {
81            order.push(node.clone());
82            if let Some(deps) = dependents.get(&node) {
83                for dependent in deps {
84                    if let Some(degree) = in_degree.get_mut(dependent) {
85                        *degree -= 1;
86                        if *degree == 0 {
87                            queue.push_back(dependent.clone());
88                        }
89                    }
90                }
91            }
92        }
93
94        if order.len() != services.len() {
95            let remaining: Vec<&String> = services.iter().filter(|s| !order.contains(s)).collect();
96            return Err(NucleusError::ConfigError(format!(
97                "Circular dependency detected among services: {:?}",
98                remaining
99            )));
100        }
101
102        Ok(Self {
103            startup_order: order,
104            edges,
105            dependents,
106        })
107    }
108
109    /// Get the shutdown order (reverse of startup order).
110    pub fn shutdown_order(&self) -> Vec<String> {
111        let mut order = self.startup_order.clone();
112        order.reverse();
113        order
114    }
115
116    /// Generate systemd unit dependency directives for a service.
117    ///
118    /// Returns (After, Requires) string pairs suitable for systemd unit files.
119    pub fn systemd_deps(&self, service: &str, topology_name: &str) -> (Vec<String>, Vec<String>) {
120        let mut after = Vec::new();
121        let mut requires = Vec::new();
122
123        if let Some(deps) = self.edges.get(service) {
124            for dep in deps {
125                let unit = format!("nucleus-{}-{}.service", topology_name, dep.service);
126                after.push(unit.clone());
127                if dep.condition == "healthy" {
128                    // For health-conditioned deps, use Type=notify + Requires
129                    requires.push(unit);
130                }
131            }
132        }
133
134        (after, requires)
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141
142    fn make_topology(deps: &[(&str, &[(&str, &str)])]) -> TopologyConfig {
143        use crate::topology::config::*;
144        let mut services = BTreeMap::new();
145        for (name, dep_list) in deps {
146            let depends_on = dep_list
147                .iter()
148                .map(|(svc, cond)| DependsOn {
149                    service: svc.to_string(),
150                    condition: cond.to_string(),
151                })
152                .collect();
153            services.insert(
154                name.to_string(),
155                ServiceDef {
156                    rootfs: format!("/nix/store/{}", name),
157                    command: vec![format!("/bin/{}", name)],
158                    memory: "256M".to_string(),
159                    cpus: 1.0,
160                    pids: 512,
161                    networks: vec![],
162                    volumes: vec![],
163                    depends_on,
164                    health_check: None,
165                    health_interval: 30,
166                    egress_allow: vec![],
167                    egress_tcp_ports: vec![],
168                    port_forwards: vec![],
169                    environment: BTreeMap::new(),
170                    user: None,
171                    group: None,
172                    additional_groups: vec![],
173                    secrets: vec![],
174                    dns: vec![],
175                    nat_backend: crate::network::NatBackend::Auto,
176                    replicas: 1,
177                    runtime: "native".to_string(),
178                    hooks: None,
179                },
180            );
181        }
182
183        TopologyConfig {
184            name: "test".to_string(),
185            networks: BTreeMap::new(),
186            volumes: BTreeMap::new(),
187            services,
188        }
189    }
190
191    #[test]
192    fn test_linear_dependency() {
193        let config = make_topology(&[
194            ("db", &[]),
195            ("cache", &[("db", "healthy")]),
196            ("web", &[("cache", "started")]),
197        ]);
198
199        let graph = DependencyGraph::resolve(&config).unwrap();
200        assert_eq!(graph.startup_order, vec!["db", "cache", "web"]);
201        assert_eq!(graph.shutdown_order(), vec!["web", "cache", "db"]);
202    }
203
204    #[test]
205    fn test_diamond_dependency() {
206        let config = make_topology(&[
207            ("db", &[]),
208            ("cache", &[("db", "started")]),
209            ("worker", &[("db", "started")]),
210            ("web", &[("cache", "started"), ("worker", "started")]),
211        ]);
212
213        let graph = DependencyGraph::resolve(&config).unwrap();
214        // db must be first, web must be last
215        assert_eq!(graph.startup_order[0], "db");
216        assert_eq!(graph.startup_order[3], "web");
217    }
218
219    #[test]
220    fn test_circular_dependency_detected() {
221        let config = make_topology(&[("a", &[("b", "started")]), ("b", &[("a", "started")])]);
222
223        let result = DependencyGraph::resolve(&config);
224        assert!(result.is_err());
225        assert!(result.unwrap_err().to_string().contains("Circular"));
226    }
227
228    #[test]
229    fn test_no_dependencies() {
230        let config = make_topology(&[("a", &[]), ("b", &[]), ("c", &[])]);
231
232        let graph = DependencyGraph::resolve(&config).unwrap();
233        assert_eq!(graph.startup_order.len(), 3);
234    }
235
236    #[test]
237    fn test_systemd_deps() {
238        let config = make_topology(&[("db", &[]), ("web", &[("db", "healthy")])]);
239
240        let graph = DependencyGraph::resolve(&config).unwrap();
241        let (after, requires) = graph.systemd_deps("web", "myapp");
242        assert_eq!(after, vec!["nucleus-myapp-db.service"]);
243        assert_eq!(requires, vec!["nucleus-myapp-db.service"]);
244    }
245
246    #[test]
247    fn test_missing_dependency_gives_clear_error() {
248        // BUG-05: When a service depends on an undefined service, the error
249        // must say "undefined service", not "circular dependency"
250        let config = make_topology(&[("web", &[("nonexistent", "started")])]);
251        let result = DependencyGraph::resolve(&config);
252        assert!(result.is_err());
253        let err_msg = result.unwrap_err().to_string();
254        assert!(
255            err_msg.contains("undefined")
256                || err_msg.contains("unknown")
257                || err_msg.contains("not found"),
258            "Error for missing dependency must mention 'undefined/unknown/not found', got: {}",
259            err_msg
260        );
261        // Must NOT say "circular"
262        assert!(
263            !err_msg.contains("ircular"),
264            "Missing dependency must not be reported as circular, got: {}",
265            err_msg
266        );
267    }
268}
nucleus/topology/dag.rs

nucleus/topology/
dag.rs
