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                    secrets: vec![],
171                    dns: vec![],
172                    replicas: 1,
173                    runtime: "native".to_string(),
174                    hooks: None,
175                },
176            );
177        }
178
179        TopologyConfig {
180            name: "test".to_string(),
181            networks: BTreeMap::new(),
182            volumes: BTreeMap::new(),
183            services,
184        }
185    }
186
187    #[test]
188    fn test_linear_dependency() {
189        let config = make_topology(&[
190            ("db", &[]),
191            ("cache", &[("db", "healthy")]),
192            ("web", &[("cache", "started")]),
193        ]);
194
195        let graph = DependencyGraph::resolve(&config).unwrap();
196        assert_eq!(graph.startup_order, vec!["db", "cache", "web"]);
197        assert_eq!(graph.shutdown_order(), vec!["web", "cache", "db"]);
198    }
199
200    #[test]
201    fn test_diamond_dependency() {
202        let config = make_topology(&[
203            ("db", &[]),
204            ("cache", &[("db", "started")]),
205            ("worker", &[("db", "started")]),
206            ("web", &[("cache", "started"), ("worker", "started")]),
207        ]);
208
209        let graph = DependencyGraph::resolve(&config).unwrap();
210        // db must be first, web must be last
211        assert_eq!(graph.startup_order[0], "db");
212        assert_eq!(graph.startup_order[3], "web");
213    }
214
215    #[test]
216    fn test_circular_dependency_detected() {
217        let config = make_topology(&[("a", &[("b", "started")]), ("b", &[("a", "started")])]);
218
219        let result = DependencyGraph::resolve(&config);
220        assert!(result.is_err());
221        assert!(result.unwrap_err().to_string().contains("Circular"));
222    }
223
224    #[test]
225    fn test_no_dependencies() {
226        let config = make_topology(&[("a", &[]), ("b", &[]), ("c", &[])]);
227
228        let graph = DependencyGraph::resolve(&config).unwrap();
229        assert_eq!(graph.startup_order.len(), 3);
230    }
231
232    #[test]
233    fn test_systemd_deps() {
234        let config = make_topology(&[("db", &[]), ("web", &[("db", "healthy")])]);
235
236        let graph = DependencyGraph::resolve(&config).unwrap();
237        let (after, requires) = graph.systemd_deps("web", "myapp");
238        assert_eq!(after, vec!["nucleus-myapp-db.service"]);
239        assert_eq!(requires, vec!["nucleus-myapp-db.service"]);
240    }
241
242    #[test]
243    fn test_missing_dependency_gives_clear_error() {
244        // BUG-05: When a service depends on an undefined service, the error
245        // must say "undefined service", not "circular dependency"
246        let config = make_topology(&[("web", &[("nonexistent", "started")])]);
247        let result = DependencyGraph::resolve(&config);
248        assert!(result.is_err());
249        let err_msg = result.unwrap_err().to_string();
250        assert!(
251            err_msg.contains("undefined") || err_msg.contains("unknown") || err_msg.contains("not found"),
252            "Error for missing dependency must mention 'undefined/unknown/not found', got: {}",
253            err_msg
254        );
255        // Must NOT say "circular"
256        assert!(
257            !err_msg.contains("ircular"),
258            "Missing dependency must not be reported as circular, got: {}",
259            err_msg
260        );
261    }
262}
nucleus/topology/dag.rs

nucleus/topology/
dag.rs
