Skip to main content

hyprstream_service/service/
ordering.rs

1//! Dependency-aware startup ordering for services.
2//!
3//! Computes startup stages from the `depends_on` metadata declared in
4//! `#[service_factory]` registrations.  Services within the same stage
5//! have no mutual dependencies and can start in parallel; services in
6//! stage N depend only on services in stages 0..N-1.
7
8use std::collections::{HashMap, HashSet};
9
10use crate::service::factory::list_factories;
11
12/// Compute startup stages from the factory dependency graph.
13///
14/// Only services present in `requested` are included. Dependencies that
15/// are not in `requested` are silently ignored (they may already be
16/// running or managed externally).
17///
18/// Returns stages where stage 0 has no dependencies, stage 1 depends
19/// only on stage 0, etc.
20///
21/// # Panics
22///
23/// Panics if the dependency graph contains a cycle (should not happen
24/// with a well-formed `depends_on` declaration).
25pub fn startup_stages(requested: &[impl AsRef<str>]) -> Vec<Vec<String>> {
26    startup_stages_for_profile(requested, false)
27}
28
29/// Required native Discovery publishes through its owned state before Policy
30/// starts. Policy clients resolve signed bootstrap reach lazily until then.
31pub fn startup_stages_for_profile(
32    requested: &[impl AsRef<str>],
33    iroh_required: bool,
34) -> Vec<Vec<String>> {
35    let requested_set: HashSet<&str> = requested.iter().map(AsRef::as_ref).collect();
36
37    // Build adjacency: service -> [dependencies that are also in requested]
38    let mut deps: HashMap<&str, Vec<&str>> = HashMap::new();
39    for factory in list_factories() {
40        if !requested_set.contains(factory.name) {
41            continue;
42        }
43        let service_deps: Vec<&str> = factory
44            .depends_on
45            .iter()
46            .copied()
47            .filter(|d| requested_set.contains(d))
48            .collect();
49        deps.insert(factory.name, service_deps);
50    }
51
52    // Services in requested but not in any factory (shouldn't happen, but be safe)
53    for &name in &requested_set {
54        deps.entry(name).or_default();
55    }
56    if iroh_required {
57        if let Some(discovery) = deps.get_mut("discovery") {
58            discovery.retain(|dependency| *dependency != "policy");
59        }
60        if requested_set.contains("discovery") {
61            if let Some(policy) = deps.get_mut("policy") {
62                policy.push("discovery");
63            }
64        }
65    }
66
67    // Kahn's algorithm for topological sort by depth
68    let mut in_degree: HashMap<&str, usize> = HashMap::new();
69    for (&svc, svc_deps) in &deps {
70        in_degree.entry(svc).or_insert(0);
71        for &dep in svc_deps {
72            // dep blocks svc → svc has in-degree from dep
73            *in_degree.entry(svc).or_insert(0) += 1;
74            in_degree.entry(dep).or_insert(0);
75        }
76    }
77
78    // Reverse adjacency: dep -> [services that depend on it]
79    let mut dependents: HashMap<&str, Vec<&str>> = HashMap::new();
80    for (&svc, svc_deps) in &deps {
81        for &dep in svc_deps {
82            dependents.entry(dep).or_default().push(svc);
83        }
84    }
85
86    let mut stages: Vec<Vec<String>> = Vec::new();
87    let mut remaining: HashSet<&str> = deps.keys().copied().collect();
88
89    while !remaining.is_empty() {
90        // Collect all services with in-degree 0
91        let mut stage: Vec<&str> = remaining
92            .iter()
93            .filter(|&&s| in_degree.get(s).copied().unwrap_or(0) == 0)
94            .copied()
95            .collect();
96
97        assert!(
98            !stage.is_empty(),
99            "dependency cycle detected among: {:?}",
100            remaining
101        );
102
103        stage.sort(); // deterministic order within a stage
104
105        // Remove this stage's services and update in-degrees
106        for &svc in &stage {
107            remaining.remove(svc);
108            if let Some(deps_of_svc) = dependents.get(svc) {
109                for &dependent in deps_of_svc {
110                    if let Some(deg) = in_degree.get_mut(dependent) {
111                        *deg = deg.saturating_sub(1);
112                    }
113                }
114            }
115        }
116
117        stages.push(stage.into_iter().map(String::from).collect());
118    }
119
120    stages
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    // Note: these tests don't use the inventory (no factories registered in
128    // test binaries). They test the algorithm via direct construction.
129
130    #[test]
131    fn test_empty_requested() {
132        let stages = startup_stages(&Vec::<String>::new());
133        assert!(stages.is_empty());
134    }
135
136    #[test]
137    fn test_stages_from_inventory() {
138        // This test verifies the function runs against the real inventory.
139        // In test binaries the inventory is typically empty, so we just
140        // verify it doesn't panic.
141        let stages = startup_stages(&["policy", "registry", "model"]);
142        // All requested services should appear exactly once across all stages.
143        let all: Vec<&str> = stages
144            .iter()
145            .flat_map(|s| s.iter().map(String::as_str))
146            .collect();
147        // Services not in the inventory will still appear (with no deps).
148        assert!(all.len() <= 3);
149    }
150}