configbuilder_pattern_loader/
topology.rs

1use crate::{ConfigError, TopologyOps};
2
3/// Topological dependency resolver for feature load ordering.
4pub struct Topology;
5
6impl TopologyOps for Topology {
7    fn sort(&self, names: &[&str], requires: &[&[&str]]) -> Result<Vec<usize>, ConfigError> {
8        let n = names.len();
9        let index: std::collections::HashMap<&str, usize> = names
10            .iter()
11            .enumerate()
12            .map(|(i, &name)| (name, i))
13            .collect();
14
15        let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
16        let mut in_degree: Vec<usize> = vec![0; n];
17
18        for (i, deps) in requires.iter().enumerate() {
19            for dep in *deps {
20                if let Some(&j) = index.get(dep) {
21                    adj[j].push(i);
22                    in_degree[i] += 1;
23                }
24            }
25        }
26
27        let mut queue: std::collections::VecDeque<usize> = in_degree
28            .iter()
29            .enumerate()
30            .filter(|(_, &d)| d == 0)
31            .map(|(i, _)| i)
32            .collect();
33
34        let mut order = Vec::with_capacity(n);
35        while let Some(i) = queue.pop_front() {
36            order.push(i);
37            for &j in &adj[i] {
38                in_degree[j] -= 1;
39                if in_degree[j] == 0 {
40                    queue.push_back(j);
41                }
42            }
43        }
44
45        if order.len() == n {
46            Ok(order)
47        } else {
48            let cycle: Vec<&str> = names
49                .iter()
50                .enumerate()
51                .filter(|(i, _)| in_degree[*i] > 0)
52                .map(|(_, name)| *name)
53                .collect();
54            Err(ConfigError::Validation {
55                section: String::from("dependency_graph"),
56                reason: format!("dependency cycle detected among: {}", cycle.join(", ")),
57            })
58        }
59    }
60}
configbuilder_pattern_loader/topology.rs

configbuilder_pattern_loader/
topology.rs
