Function topo_sort

nodedb-cluster/src/subsystem/topo_sort.rs:26–90

Topo-sort `subsystems` by their declared dependencies. Returns a `Vec ` where each element is an index into `subsystems` and the order represents a valid start sequence (dependencies before dependents). # Errors - `TopoError::UnknownDependency` — a subsystem lists a dependency name that is not present in `subsystems`. - `TopoError::Cycle` — a circular dependency was detected.

(subsystems: &[Arc<dyn ClusterSubsystem>])

///   that is not present in `subsystems`.
/// - `TopoError::Cycle` — a circular dependency was detected.
pub fn topo_sort(subsystems: &[Arc<dyn ClusterSubsystem>]) -> Result<Vec<usize>, TopoError> {
    // Build name → index map.
    let name_to_idx: HashMap<&'static str, usize> = subsystems
        .iter()
        .enumerate()
        .map(|(i, s)| (s.name(), i))
        .collect();

    // Validate all dependency names and build adjacency (dep → dependent)
    // plus in-degree per node.
    let n = subsystems.len();
    let mut in_degree = vec![0usize; n];
    // adjacency[i] = list of indices that depend on i (i must start before them)
    let mut adjacency: Vec<Vec<usize>> = vec![Vec::new(); n];

    for (i, subsystem) in subsystems.iter().enumerate() {
        for &dep_name in subsystem.dependencies() {
            let dep_idx =
                name_to_idx
                    .get(dep_name)
                    .copied()
                    .ok_or(TopoError::UnknownDependency {
                        subsystem: subsystem.name(),
                        dependency: dep_name,
                    })?;
            // dep_idx must come before i
            adjacency[dep_idx].push(i);
            in_degree[i] += 1;
        }
    }

    // Kahn's algorithm.
    let mut queue: VecDeque<usize> = (0..n).filter(|&i| in_degree[i] == 0).collect();

    let mut order = Vec::with_capacity(n);

    while let Some(idx) = queue.pop_front() {
        order.push(idx);
        for &dependent in &adjacency[idx] {
            in_degree[dependent] -= 1;
            if in_degree[dependent] == 0 {
                queue.push_back(dependent);
            }
        }
    }

    if order.len() != n {
        // Some nodes still have non-zero in-degree — there is a cycle.
        // Collect the names of nodes still in the cycle for diagnostics.
        let cycle_names: Vec<&'static str> = in_degree
            .iter()
            .enumerate()
            .filter_map(|(i, &deg)| {
                if deg > 0 {
                    Some(subsystems[i].name())
                } else {
                    None
                }