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            boot_start: None,
156            depends: depends.into_iter().map(String::from).collect(),
157            watch: vec![],
158            path: None,
159        }
160    }
161
162    #[test]
163    fn test_no_dependencies() {
164        let mut daemons = IndexMap::new();
165        daemons.insert("api".to_string(), make_daemon(vec![]));
166
167        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
168
169        assert_eq!(result.levels.len(), 1);
170        assert_eq!(result.levels[0], vec!["api"]);
171    }
172
173    #[test]
174    fn test_simple_dependency() {
175        let mut daemons = IndexMap::new();
176        daemons.insert("postgres".to_string(), make_daemon(vec![]));
177        daemons.insert("api".to_string(), make_daemon(vec!["postgres"]));
178
179        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
180
181        assert_eq!(result.levels.len(), 2);
182        assert_eq!(result.levels[0], vec!["postgres"]);
183        assert_eq!(result.levels[1], vec!["api"]);
184    }
185
186    #[test]
187    fn test_multiple_dependencies() {
188        let mut daemons = IndexMap::new();
189        daemons.insert("postgres".to_string(), make_daemon(vec![]));
190        daemons.insert("redis".to_string(), make_daemon(vec![]));
191        daemons.insert("api".to_string(), make_daemon(vec!["postgres", "redis"]));
192
193        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
194
195        assert_eq!(result.levels.len(), 2);
196        // postgres and redis can start in parallel
197        assert!(result.levels[0].contains(&"postgres".to_string()));
198        assert!(result.levels[0].contains(&"redis".to_string()));
199        assert_eq!(result.levels[1], vec!["api"]);
200    }
201
202    #[test]
203    fn test_transitive_dependencies() {
204        let mut daemons = IndexMap::new();
205        daemons.insert("database".to_string(), make_daemon(vec![]));
206        daemons.insert("backend".to_string(), make_daemon(vec!["database"]));
207        daemons.insert("api".to_string(), make_daemon(vec!["backend"]));
208
209        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
210
211        assert_eq!(result.levels.len(), 3);
212        assert_eq!(result.levels[0], vec!["database"]);
213        assert_eq!(result.levels[1], vec!["backend"]);
214        assert_eq!(result.levels[2], vec!["api"]);
215    }
216
217    #[test]
218    fn test_diamond_dependency() {
219        let mut daemons = IndexMap::new();
220        daemons.insert("db".to_string(), make_daemon(vec![]));
221        daemons.insert("auth".to_string(), make_daemon(vec!["db"]));
222        daemons.insert("data".to_string(), make_daemon(vec!["db"]));
223        daemons.insert("api".to_string(), make_daemon(vec!["auth", "data"]));
224
225        let result = resolve_dependencies(&["api".to_string()], &daemons).unwrap();
226
227        assert_eq!(result.levels.len(), 3);
228        assert_eq!(result.levels[0], vec!["db"]);
229        // auth and data can start in parallel
230        assert!(result.levels[1].contains(&"auth".to_string()));
231        assert!(result.levels[1].contains(&"data".to_string()));
232        assert_eq!(result.levels[2], vec!["api"]);
233    }
234
235    #[test]
236    fn test_circular_dependency_detected() {
237        let mut daemons = IndexMap::new();
238        daemons.insert("a".to_string(), make_daemon(vec!["c"]));
239        daemons.insert("b".to_string(), make_daemon(vec!["a"]));
240        daemons.insert("c".to_string(), make_daemon(vec!["b"]));
241
242        let result = resolve_dependencies(&["a".to_string()], &daemons);
243
244        assert!(result.is_err());
245        let err = result.unwrap_err().to_string();
246        assert!(err.contains("circular dependency"));
247    }
248
249    #[test]
250    fn test_missing_dependency_error() {
251        let mut daemons = IndexMap::new();
252        daemons.insert("api".to_string(), make_daemon(vec!["nonexistent"]));
253
254        let result = resolve_dependencies(&["api".to_string()], &daemons);
255
256        assert!(result.is_err());
257        let err = result.unwrap_err().to_string();
258        assert!(err.contains("nonexistent"));
259        assert!(err.contains("not defined"));
260    }
261
262    #[test]
263    fn test_missing_requested_daemon_error() {
264        let daemons = IndexMap::new();
265
266        let result = resolve_dependencies(&["nonexistent".to_string()], &daemons);
267
268        assert!(result.is_err());
269        let err = result.unwrap_err().to_string();
270        assert!(err.contains("nonexistent"));
271        assert!(err.contains("not found"));
272    }
273
274    #[test]
275    fn test_multiple_requested_daemons() {
276        let mut daemons = IndexMap::new();
277        daemons.insert("db".to_string(), make_daemon(vec![]));
278        daemons.insert("api".to_string(), make_daemon(vec!["db"]));
279        daemons.insert("worker".to_string(), make_daemon(vec!["db"]));
280
281        let result =
282            resolve_dependencies(&["api".to_string(), "worker".to_string()], &daemons).unwrap();
283
284        assert_eq!(result.levels.len(), 2);
285        assert_eq!(result.levels[0], vec!["db"]);
286        // api and worker can start in parallel
287        assert!(result.levels[1].contains(&"api".to_string()));
288        assert!(result.levels[1].contains(&"worker".to_string()));
289    }
290
291    #[test]
292    fn test_start_all_with_dependencies() {
293        let mut daemons = IndexMap::new();
294        daemons.insert("db".to_string(), make_daemon(vec![]));
295        daemons.insert("cache".to_string(), make_daemon(vec![]));
296        daemons.insert("api".to_string(), make_daemon(vec!["db", "cache"]));
297        daemons.insert("worker".to_string(), make_daemon(vec!["db"]));
298
299        let all_ids: Vec<String> = daemons.keys().cloned().collect();
300        let result = resolve_dependencies(&all_ids, &daemons).unwrap();
301
302        assert_eq!(result.levels.len(), 2);
303        // db and cache have no deps
304        assert!(result.levels[0].contains(&"db".to_string()));
305        assert!(result.levels[0].contains(&"cache".to_string()));
306        // api and worker depend on level 0
307        assert!(result.levels[1].contains(&"api".to_string()));
308        assert!(result.levels[1].contains(&"worker".to_string()));
309    }
310}
pitchfork_cli/deps.rs

pitchfork_cli/
deps.rs
