eidos-kernel 0.1.0

use std::collections::{BTreeMap, BTreeSet};

use super::TaskDag;

/// Validation failures for a task DAG.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DagValidationError {
    Empty,
    DuplicateNodeId(String),
    MissingDependency { node_id: String, dependency: String },
    Cycle { nodes: Vec<String> },
}

/// Validate a DAG and return a deterministic topological execution order.
///
/// The returned order is stable: when multiple nodes are ready, lexical node id order wins.
pub fn validate_dag(dag: &TaskDag) -> Result<Vec<String>, DagValidationError> {
    if dag.nodes.is_empty() {
        return Err(DagValidationError::Empty);
    }

    let mut ids = BTreeSet::new();
    for node in &dag.nodes {
        if !ids.insert(node.id.clone()) {
            return Err(DagValidationError::DuplicateNodeId(node.id.clone()));
        }
    }

    for node in &dag.nodes {
        for dependency in &node.depends_on {
            if !ids.contains(dependency) {
                return Err(DagValidationError::MissingDependency {
                    node_id: node.id.clone(),
                    dependency: dependency.clone(),
                });
            }
        }
    }

    let mut remaining_deps: BTreeMap<String, BTreeSet<String>> = dag
        .nodes
        .iter()
        .map(|node| {
            (
                node.id.clone(),
                node.depends_on.iter().cloned().collect::<BTreeSet<_>>(),
            )
        })
        .collect();
    let mut dependents: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
    for node in &dag.nodes {
        for dependency in &node.depends_on {
            dependents
                .entry(dependency.clone())
                .or_default()
                .insert(node.id.clone());
        }
    }

    let mut ready = remaining_deps
        .iter()
        .filter_map(|(id, deps)| deps.is_empty().then_some(id.clone()))
        .collect::<BTreeSet<_>>();
    let mut order = Vec::with_capacity(dag.nodes.len());

    while let Some(id) = ready.pop_first() {
        if !remaining_deps.contains_key(&id) {
            continue;
        }
        remaining_deps.remove(&id);
        order.push(id.clone());

        if let Some(children) = dependents.get(&id) {
            for child in children {
                if let Some(deps) = remaining_deps.get_mut(child) {
                    deps.remove(&id);
                    if deps.is_empty() {
                        ready.insert(child.clone());
                    }
                }
            }
        }
    }

    if remaining_deps.is_empty() {
        Ok(order)
    } else {
        Err(DagValidationError::Cycle {
            nodes: remaining_deps.keys().cloned().collect(),
        })
    }
}