pitchfork_cli/
deps.rs

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

pitchfork_cli/
deps.rs
