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

pitchfork_cli/
deps.rs
