oxihuman_core/
dependency_resolver.rs

1//! Generic dependency resolver using topological sort (Kahn's algorithm).
2
3#[allow(dead_code)]
4#[derive(Clone)]
5pub struct Dependency {
6    pub name: String,
7    pub required: bool,
8    pub version_req: Option<String>,
9}
10
11#[allow(dead_code)]
12pub struct DependencyNode {
13    pub id: String,
14    pub version: String,
15    pub deps: Vec<Dependency>,
16}
17
18#[allow(dead_code)]
19pub struct DependencyGraph {
20    pub nodes: Vec<DependencyNode>,
21}
22
23#[allow(dead_code)]
24#[derive(Clone, PartialEq, Debug)]
25pub enum ResolveError {
26    CircularDependency(Vec<String>),
27    MissingDependency(String),
28    VersionConflict(String),
29}
30
31#[allow(dead_code)]
32pub struct ResolveResult {
33    /// Resolved load order.
34    pub order: Vec<String>,
35    pub warnings: Vec<String>,
36}
37
38// ---------------------------------------------------------------------------
39// Construction
40// ---------------------------------------------------------------------------
41
42#[allow(dead_code)]
43pub fn new_dependency_graph() -> DependencyGraph {
44    DependencyGraph { nodes: Vec::new() }
45}
46
47#[allow(dead_code)]
48pub fn add_dep_node(graph: &mut DependencyGraph, node: DependencyNode) {
49    graph.nodes.push(node);
50}
51
52// ---------------------------------------------------------------------------
53// Query helpers
54// ---------------------------------------------------------------------------
55
56#[allow(dead_code)]
57pub fn dep_node_count(graph: &DependencyGraph) -> usize {
58    graph.nodes.len()
59}
60
61#[allow(dead_code)]
62pub fn get_dep_node<'a>(graph: &'a DependencyGraph, id: &str) -> Option<&'a DependencyNode> {
63    graph.nodes.iter().find(|n| n.id == id)
64}
65
66#[allow(dead_code)]
67pub fn remove_dep_node(graph: &mut DependencyGraph, id: &str) -> bool {
68    let before = graph.nodes.len();
69    graph.nodes.retain(|n| n.id != id);
70    graph.nodes.len() < before
71}
72
73#[allow(dead_code)]
74pub fn missing_dependencies(graph: &DependencyGraph) -> Vec<String> {
75    let ids: std::collections::HashSet<&str> = graph.nodes.iter().map(|n| n.id.as_str()).collect();
76    let mut missing = Vec::new();
77    for node in &graph.nodes {
78        for dep in &node.deps {
79            if dep.required && !ids.contains(dep.name.as_str()) && !missing.contains(&dep.name) {
80                missing.push(dep.name.clone());
81            }
82        }
83    }
84    missing
85}
86
87#[allow(dead_code)]
88pub fn optional_dep_count(graph: &DependencyGraph) -> usize {
89    graph
90        .nodes
91        .iter()
92        .flat_map(|n| n.deps.iter())
93        .filter(|d| !d.required)
94        .count()
95}
96
97#[allow(dead_code)]
98pub fn direct_dependents<'a>(graph: &'a DependencyGraph, id: &str) -> Vec<&'a str> {
99    graph
100        .nodes
101        .iter()
102        .filter(|n| n.deps.iter().any(|d| d.name == id))
103        .map(|n| n.id.as_str())
104        .collect()
105}
106
107#[allow(dead_code)]
108pub fn all_dependents_transitive(graph: &DependencyGraph, id: &str) -> Vec<String> {
109    let mut visited: std::collections::HashSet<String> = std::collections::HashSet::new();
110    let mut queue = std::collections::VecDeque::new();
111    queue.push_back(id.to_string());
112    while let Some(current) = queue.pop_front() {
113        let dependents = direct_dependents(graph, &current);
114        for dep in dependents {
115            if !visited.contains(dep) {
116                visited.insert(dep.to_string());
117                queue.push_back(dep.to_string());
118            }
119        }
120    }
121    visited.into_iter().collect()
122}
123
124// ---------------------------------------------------------------------------
125// Topological sort (Kahn's algorithm)
126// ---------------------------------------------------------------------------
127
128#[allow(dead_code)]
129pub fn resolve_dependencies(graph: &DependencyGraph) -> Result<ResolveResult, ResolveError> {
130    use std::collections::HashMap;
131    use std::collections::VecDeque;
132
133    // Check for missing required deps first.
134    let missing = missing_dependencies(graph);
135    if !missing.is_empty() {
136        return Err(ResolveError::MissingDependency(missing[0].clone()));
137    }
138
139    // Build adjacency: dep_name → dependents (nodes that depend on it).
140    let mut in_degree: HashMap<&str, usize> = HashMap::new();
141    for node in &graph.nodes {
142        in_degree.entry(node.id.as_str()).or_insert(0);
143        for dep in &node.deps {
144            in_degree.entry(dep.name.as_str()).or_insert(0);
145        }
146    }
147    // In-degree for Kahn's: count how many required deps each node has.
148    let mut in_deg: HashMap<&str, usize> = HashMap::new();
149    for node in &graph.nodes {
150        let required_count = node.deps.iter().filter(|d| d.required).count();
151        in_deg.insert(node.id.as_str(), required_count);
152    }
153
154    // Build reverse mapping: dep → nodes that need it.
155    let mut dependents_map: HashMap<&str, Vec<&str>> = HashMap::new();
156    for node in &graph.nodes {
157        for dep in &node.deps {
158            if dep.required {
159                dependents_map
160                    .entry(dep.name.as_str())
161                    .or_default()
162                    .push(node.id.as_str());
163            }
164        }
165    }
166
167    let mut queue: VecDeque<&str> = VecDeque::new();
168    for node in &graph.nodes {
169        if *in_deg.get(node.id.as_str()).unwrap_or(&0) == 0 {
170            queue.push_back(node.id.as_str());
171        }
172    }
173
174    let mut order: Vec<String> = Vec::new();
175    while let Some(current) = queue.pop_front() {
176        order.push(current.to_string());
177        if let Some(deps_of_current) = dependents_map.get(current) {
178            for &dependent in deps_of_current {
179                let entry = in_deg.entry(dependent).or_insert(0);
180                *entry = entry.saturating_sub(1);
181                if *entry == 0 {
182                    queue.push_back(dependent);
183                }
184            }
185        }
186    }
187
188    if order.len() < graph.nodes.len() {
189        // Cycle detected — collect nodes not in order.
190        let cycle_nodes: Vec<String> = graph
191            .nodes
192            .iter()
193            .filter(|n| !order.contains(&n.id))
194            .map(|n| n.id.clone())
195            .collect();
196        return Err(ResolveError::CircularDependency(cycle_nodes));
197    }
198
199    Ok(ResolveResult {
200        order,
201        warnings: Vec::new(),
202    })
203}
204
205#[allow(dead_code)]
206pub fn has_circular_dependency(graph: &DependencyGraph) -> bool {
207    matches!(
208        resolve_dependencies(graph),
209        Err(ResolveError::CircularDependency(_))
210    )
211}
212
213// ---------------------------------------------------------------------------
214// Serialization
215// ---------------------------------------------------------------------------
216
217#[allow(dead_code)]
218pub fn dep_graph_to_json(graph: &DependencyGraph) -> String {
219    let mut s = String::from("{\"nodes\":[");
220    for (i, node) in graph.nodes.iter().enumerate() {
221        if i > 0 {
222            s.push(',');
223        }
224        s.push_str(&format!(
225            "{{\"id\":\"{}\",\"version\":\"{}\",\"deps\":[",
226            node.id, node.version
227        ));
228        for (j, dep) in node.deps.iter().enumerate() {
229            if j > 0 {
230                s.push(',');
231            }
232            let req_str = if dep.required { "true" } else { "false" };
233            let ver = dep.version_req.as_deref().unwrap_or("");
234            s.push_str(&format!(
235                "{{\"name\":\"{}\",\"required\":{},\"version_req\":\"{}\"}}",
236                dep.name, req_str, ver
237            ));
238        }
239        s.push_str("]}");
240    }
241    s.push_str("]}");
242    s
243}
244
245// ---------------------------------------------------------------------------
246// Tests
247// ---------------------------------------------------------------------------
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252
253    fn make_node(id: &str, deps: &[(&str, bool)]) -> DependencyNode {
254        DependencyNode {
255            id: id.to_string(),
256            version: "1.0.0".to_string(),
257            deps: deps
258                .iter()
259                .map(|(name, required)| Dependency {
260                    name: name.to_string(),
261                    required: *required,
262                    version_req: None,
263                })
264                .collect(),
265        }
266    }
267
268    #[test]
269    fn test_new_graph() {
270        let g = new_dependency_graph();
271        assert_eq!(dep_node_count(&g), 0);
272    }
273
274    #[test]
275    fn test_add_node() {
276        let mut g = new_dependency_graph();
277        add_dep_node(&mut g, make_node("A", &[]));
278        assert_eq!(dep_node_count(&g), 1);
279    }
280
281    #[test]
282    fn test_resolve_simple_chain() {
283        let mut g = new_dependency_graph();
284        add_dep_node(&mut g, make_node("A", &[]));
285        add_dep_node(&mut g, make_node("B", &[("A", true)]));
286        add_dep_node(&mut g, make_node("C", &[("B", true)]));
287        let result = resolve_dependencies(&g).expect("should succeed");
288        let order = &result.order;
289        let a_pos = order.iter().position(|x| x == "A").expect("should succeed");
290        let b_pos = order.iter().position(|x| x == "B").expect("should succeed");
291        let c_pos = order.iter().position(|x| x == "C").expect("should succeed");
292        assert!(a_pos < b_pos);
293        assert!(b_pos < c_pos);
294    }
295
296    #[test]
297    fn test_circular_detection() {
298        let mut g = new_dependency_graph();
299        add_dep_node(&mut g, make_node("A", &[("B", true)]));
300        add_dep_node(&mut g, make_node("B", &[("A", true)]));
301        assert!(has_circular_dependency(&g));
302    }
303
304    #[test]
305    fn test_no_circular_simple() {
306        let mut g = new_dependency_graph();
307        add_dep_node(&mut g, make_node("A", &[]));
308        add_dep_node(&mut g, make_node("B", &[("A", true)]));
309        assert!(!has_circular_dependency(&g));
310    }
311
312    #[test]
313    fn test_missing_dependencies() {
314        let mut g = new_dependency_graph();
315        add_dep_node(&mut g, make_node("A", &[("Z", true)]));
316        let missing = missing_dependencies(&g);
317        assert!(missing.contains(&"Z".to_string()));
318    }
319
320    #[test]
321    fn test_missing_deps_returns_error() {
322        let mut g = new_dependency_graph();
323        add_dep_node(&mut g, make_node("A", &[("Z", true)]));
324        assert!(matches!(
325            resolve_dependencies(&g),
326            Err(ResolveError::MissingDependency(_))
327        ));
328    }
329
330    #[test]
331    fn test_dep_node_count() {
332        let mut g = new_dependency_graph();
333        assert_eq!(dep_node_count(&g), 0);
334        add_dep_node(&mut g, make_node("A", &[]));
335        add_dep_node(&mut g, make_node("B", &[]));
336        assert_eq!(dep_node_count(&g), 2);
337    }
338
339    #[test]
340    fn test_get_dep_node() {
341        let mut g = new_dependency_graph();
342        add_dep_node(&mut g, make_node("A", &[]));
343        assert!(get_dep_node(&g, "A").is_some());
344        assert!(get_dep_node(&g, "X").is_none());
345    }
346
347    #[test]
348    fn test_direct_dependents() {
349        let mut g = new_dependency_graph();
350        add_dep_node(&mut g, make_node("A", &[]));
351        add_dep_node(&mut g, make_node("B", &[("A", true)]));
352        add_dep_node(&mut g, make_node("C", &[("A", false)]));
353        let deps = direct_dependents(&g, "A");
354        assert!(deps.contains(&"B"));
355        assert!(deps.contains(&"C"));
356    }
357
358    #[test]
359    fn test_all_dependents_transitive() {
360        let mut g = new_dependency_graph();
361        add_dep_node(&mut g, make_node("A", &[]));
362        add_dep_node(&mut g, make_node("B", &[("A", true)]));
363        add_dep_node(&mut g, make_node("C", &[("B", true)]));
364        let trans = all_dependents_transitive(&g, "A");
365        assert!(trans.contains(&"B".to_string()));
366        assert!(trans.contains(&"C".to_string()));
367    }
368
369    #[test]
370    fn test_remove_dep_node() {
371        let mut g = new_dependency_graph();
372        add_dep_node(&mut g, make_node("A", &[]));
373        add_dep_node(&mut g, make_node("B", &[]));
374        let removed = remove_dep_node(&mut g, "A");
375        assert!(removed);
376        assert_eq!(dep_node_count(&g), 1);
377        let not_removed = remove_dep_node(&mut g, "X");
378        assert!(!not_removed);
379    }
380
381    #[test]
382    fn test_optional_dep_count() {
383        let mut g = new_dependency_graph();
384        add_dep_node(&mut g, make_node("A", &[("B", false), ("C", true)]));
385        add_dep_node(&mut g, make_node("B", &[]));
386        add_dep_node(&mut g, make_node("C", &[]));
387        assert_eq!(optional_dep_count(&g), 1);
388    }
389
390    #[test]
391    fn test_dep_graph_to_json() {
392        let mut g = new_dependency_graph();
393        add_dep_node(&mut g, make_node("A", &[]));
394        let json = dep_graph_to_json(&g);
395        assert!(json.contains("\"id\":\"A\""));
396    }
397
398    #[test]
399    fn test_resolve_no_deps() {
400        let mut g = new_dependency_graph();
401        add_dep_node(&mut g, make_node("X", &[]));
402        add_dep_node(&mut g, make_node("Y", &[]));
403        let result = resolve_dependencies(&g).expect("should succeed");
404        assert_eq!(result.order.len(), 2);
405    }
406}
oxihuman_core/dependency_resolver.rs

oxihuman_core/
dependency_resolver.rs
