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

nucleus/topology/
dag.rs
