pitchfork_cli/
deps.rs

1use crate::Result;
2use crate::pitchfork_toml::PitchforkTomlDaemon;
3use indexmap::IndexMap;
4use miette::bail;
5use std::collections::{HashMap, HashSet, VecDeque};
6
7/// Result of dependency resolution
8#[derive(Debug)]
9pub struct DependencyOrder {
10    /// Groups of daemons that can be started in parallel.
11    /// Each level depends only on daemons in previous levels.
12    pub levels: Vec<Vec<String>>,
13}
14
15/// Resolve dependency order using Kahn's algorithm (topological sort).
16///
17/// Returns daemons grouped into levels where:
18/// - Level 0: daemons with no dependencies (or deps already satisfied)
19/// - Level 1: daemons that only depend on level 0
20/// - Level N: daemons that only depend on levels 0..(N-1)
21///
22/// Daemons within the same level can be started in parallel.
23pub fn resolve_dependencies(
24    requested: &[String],
25    all_daemons: &IndexMap<String, PitchforkTomlDaemon>,
26) -> Result<DependencyOrder> {
27    // 1. Build the full set of daemons to start (requested + transitive deps)
28    let mut to_start: HashSet<String> = HashSet::new();
29    let mut queue: VecDeque<String> = requested.iter().cloned().collect();
30
31    while let Some(id) = queue.pop_front() {
32        if to_start.contains(&id) {
33            continue;
34        }
35
36        let daemon = all_daemons
37            .get(&id)
38            .ok_or_else(|| miette::miette!("Daemon '{}' not found in configuration", id))?;
39
40        to_start.insert(id.clone());
41
42        // Add dependencies to queue
43        for dep in &daemon.depends {
44            if !all_daemons.contains_key(dep) {
45                bail!(
46                    "Daemon '{}' depends on '{}' which is not defined in configuration",
47                    id,
48                    dep
49                );
50            }
51            if !to_start.contains(dep) {
52                queue.push_back(dep.clone());
53            }
54        }
55    }
56
57    // 2. Build adjacency list and in-degree map
58    let mut in_degree: HashMap<String, usize> = HashMap::new();
59    let mut dependents: HashMap<String, Vec<String>> = HashMap::new();
60
61    for id in &to_start {
62        in_degree.entry(id.clone()).or_insert(0);
63        dependents.entry(id.clone()).or_default();
64    }
65
66    for id in &to_start {
67        let daemon = all_daemons.get(id).ok_or_else(|| {
68            miette::miette!("Internal error: daemon '{}' missing from configuration", id)
69        })?;
70        for dep in &daemon.depends {
71            if to_start.contains(dep) {
72                *in_degree.get_mut(id).ok_or_else(|| {
73                    miette::miette!("Internal error: in_degree missing for daemon '{}'", id)
74                })? += 1;
75                dependents
76                    .get_mut(dep)
77                    .ok_or_else(|| {
78                        miette::miette!("Internal error: dependents missing for daemon '{}'", dep)
79                    })?
80                    .push(id.clone());
81            }
82        }
83    }
84
85    // 3. Kahn's algorithm with level tracking
86    let mut processed: HashSet<String> = HashSet::new();
87    let mut levels: Vec<Vec<String>> = Vec::new();
88    let mut current_level: Vec<String> = in_degree
89        .iter()
90        .filter(|(_, deg)| **deg == 0)
91        .map(|(id, _)| id.clone())
92        .collect();
93
94    // Sort for deterministic order
95    current_level.sort();
96
97    while !current_level.is_empty() {
98        let mut next_level = Vec::new();
99
100        for id in &current_level {
101            processed.insert(id.clone());
102
103            let deps = dependents.get(id).ok_or_else(|| {
104                miette::miette!("Internal error: dependents missing for daemon '{}'", id)
105            })?;
106            for dependent in deps {
107                let deg = in_degree.get_mut(dependent).ok_or_else(|| {
108                    miette::miette!(
109                        "Internal error: in_degree missing for daemon '{}'",
110                        dependent
111                    )
112                })?;
113                *deg -= 1;
114                if *deg == 0 {
115                    next_level.push(dependent.clone());
116                }
117            }
118        }
119
120        levels.push(current_level);
121        next_level.sort(); // Sort for deterministic order
122        current_level = next_level;
123    }
124
125    // 4. Check for cycles
126    if processed.len() != to_start.len() {
127        let remaining: Vec<_> = to_start.difference(&processed).cloned().collect::<Vec<_>>();
128        bail!("Circular dependency detected involving: {:?}", remaining);
129    }
130
131    Ok(DependencyOrder { levels })
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137    use crate::pitchfork_toml::PitchforkTomlDaemon;
138    use indexmap::IndexMap;
139
140    fn make_daemon(depends: Vec<&str>) -> PitchforkTomlDaemon {
141        PitchforkTomlDaemon {
142            run: "echo test".to_string(),
143            auto: vec![],
144            cron: None,
145            retry: 0,
146            ready_delay: None,
147            ready_output: None,
148            ready_http: None,
149            ready_port: None,
150            boot_start: None,
151            depends: depends.into_iter().map(String::from).collect(),
152            path: None,
153        }
154    }
155
156    #[test]
157    fn test_no_dependencies() {
158        let mut daemons = IndexMap::new();
159        daemons.insert("api".to_string(), make_daemon(vec![]));
160
161        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
162
163        assert_eq!(result.levels.len(), 1);
164        assert_eq!(result.levels[0], vec!["api"]);
165    }
166
167    #[test]
168    fn test_simple_dependency() {
169        let mut daemons = IndexMap::new();
170        daemons.insert("postgres".to_string(), make_daemon(vec![]));
171        daemons.insert("api".to_string(), make_daemon(vec!["postgres"]));
172
173        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
174
175        assert_eq!(result.levels.len(), 2);
176        assert_eq!(result.levels[0], vec!["postgres"]);
177        assert_eq!(result.levels[1], vec!["api"]);
178    }
179
180    #[test]
181    fn test_multiple_dependencies() {
182        let mut daemons = IndexMap::new();
183        daemons.insert("postgres".to_string(), make_daemon(vec![]));
184        daemons.insert("redis".to_string(), make_daemon(vec![]));
185        daemons.insert("api".to_string(), make_daemon(vec!["postgres", "redis"]));
186
187        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
188
189        assert_eq!(result.levels.len(), 2);
190        // postgres and redis can start in parallel
191        assert!(result.levels[0].contains(&"postgres".to_string()));
192        assert!(result.levels[0].contains(&"redis".to_string()));
193        assert_eq!(result.levels[1], vec!["api"]);
194    }
195
196    #[test]
197    fn test_transitive_dependencies() {
198        let mut daemons = IndexMap::new();
199        daemons.insert("database".to_string(), make_daemon(vec![]));
200        daemons.insert("backend".to_string(), make_daemon(vec!["database"]));
201        daemons.insert("api".to_string(), make_daemon(vec!["backend"]));
202
203        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
204
205        assert_eq!(result.levels.len(), 3);
206        assert_eq!(result.levels[0], vec!["database"]);
207        assert_eq!(result.levels[1], vec!["backend"]);
208        assert_eq!(result.levels[2], vec!["api"]);
209    }
210
211    #[test]
212    fn test_diamond_dependency() {
213        let mut daemons = IndexMap::new();
214        daemons.insert("db".to_string(), make_daemon(vec![]));
215        daemons.insert("auth".to_string(), make_daemon(vec!["db"]));
216        daemons.insert("data".to_string(), make_daemon(vec!["db"]));
217        daemons.insert("api".to_string(), make_daemon(vec!["auth", "data"]));
218
219        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
220
221        assert_eq!(result.levels.len(), 3);
222        assert_eq!(result.levels[0], vec!["db"]);
223        // auth and data can start in parallel
224        assert!(result.levels[1].contains(&"auth".to_string()));
225        assert!(result.levels[1].contains(&"data".to_string()));
226        assert_eq!(result.levels[2], vec!["api"]);
227    }
228
229    #[test]
230    fn test_circular_dependency_detected() {
231        let mut daemons = IndexMap::new();
232        daemons.insert("a".to_string(), make_daemon(vec!["c"]));
233        daemons.insert("b".to_string(), make_daemon(vec!["a"]));
234        daemons.insert("c".to_string(), make_daemon(vec!["b"]));
235
236        let result = resolve_dependencies(&["a".to_string()], &daemons);
237
238        assert!(result.is_err());
239        let err = result.unwrap_err().to_string();
240        assert!(err.contains("Circular dependency"));
241    }
242
243    #[test]
244    fn test_missing_dependency_error() {
245        let mut daemons = IndexMap::new();
246        daemons.insert("api".to_string(), make_daemon(vec!["nonexistent"]));
247
248        let result = resolve_dependencies(&["api".to_string()], &daemons);
249
250        assert!(result.is_err());
251        let err = result.unwrap_err().to_string();
252        assert!(err.contains("nonexistent"));
253        assert!(err.contains("not defined"));
254    }
255
256    #[test]
257    fn test_missing_requested_daemon_error() {
258        let daemons = IndexMap::new();
259
260        let result = resolve_dependencies(&["nonexistent".to_string()], &daemons);
261
262        assert!(result.is_err());
263        let err = result.unwrap_err().to_string();
264        assert!(err.contains("nonexistent"));
265        assert!(err.contains("not found"));
266    }
267
268    #[test]
269    fn test_multiple_requested_daemons() {
270        let mut daemons = IndexMap::new();
271        daemons.insert("db".to_string(), make_daemon(vec![]));
272        daemons.insert("api".to_string(), make_daemon(vec!["db"]));
273        daemons.insert("worker".to_string(), make_daemon(vec!["db"]));
274
275        let result =
276            resolve_dependencies(&["api".to_string(), "worker".to_string()], &daemons).unwrap();
277
278        assert_eq!(result.levels.len(), 2);
279        assert_eq!(result.levels[0], vec!["db"]);
280        // api and worker can start in parallel
281        assert!(result.levels[1].contains(&"api".to_string()));
282        assert!(result.levels[1].contains(&"worker".to_string()));
283    }
284
285    #[test]
286    fn test_start_all_with_dependencies() {
287        let mut daemons = IndexMap::new();
288        daemons.insert("db".to_string(), make_daemon(vec![]));
289        daemons.insert("cache".to_string(), make_daemon(vec![]));
290        daemons.insert("api".to_string(), make_daemon(vec!["db", "cache"]));
291        daemons.insert("worker".to_string(), make_daemon(vec!["db"]));
292
293        let all_ids: Vec<String> = daemons.keys().cloned().collect();
294        let result = resolve_dependencies(&all_ids, &daemons).unwrap();
295
296        assert_eq!(result.levels.len(), 2);
297        // db and cache have no deps
298        assert!(result.levels[0].contains(&"db".to_string()));
299        assert!(result.levels[0].contains(&"cache".to_string()));
300        // api and worker depend on level 0
301        assert!(result.levels[1].contains(&"api".to_string()));
302        assert!(result.levels[1].contains(&"worker".to_string()));
303    }
304}
pitchfork_cli/deps.rs

pitchfork_cli/
deps.rs
