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

pitchfork_cli/
deps.rs
