agileplus-trace-validator 0.3.0

//! DAG validation: acyclicity check via DFS and flow rules against the
//! ontology's `DagValidationRules`.

use crate::{ValidationError, ValidationResult};
use agileplus_domain::intent_graph::*;
use std::collections::{HashMap, HashSet};

/// Ensure the graph contains no cycles using DFS-based cycle detection.
pub fn validate_dag_acyclicity(graph: &IntentGraph) -> ValidationResult {
    let mut errors = Vec::new();
    let mut adjacency: HashMap<&NodeId, Vec<&NodeId>> = HashMap::new();
    for edge in &graph.edges {
        adjacency.entry(&edge.source).or_default().push(&edge.target);
    }

    let mut visited = HashSet::new();
    let mut rec_stack = HashSet::new();

    fn dfs<'a>(
        node: &'a NodeId,
        adjacency: &HashMap<&'a NodeId, Vec<&'a NodeId>>,
        visited: &mut HashSet<&'a NodeId>,
        rec_stack: &mut HashSet<&'a NodeId>,
        path: &mut Vec<&'a NodeId>,
        errors: &mut Vec<ValidationError>,
    ) {
        visited.insert(node);
        rec_stack.insert(node);
        path.push(node);

        if let Some(neighbors) = adjacency.get(node) {
            for neighbor in neighbors {
                if !visited.contains(neighbor) {
                    dfs(neighbor, adjacency, visited, rec_stack, path, errors);
                } else if rec_stack.contains(neighbor) {
                    let cycle_start = path.iter().position(|&n| n == *neighbor).unwrap_or(0);
                    let cycle_nodes: Vec<String> = path[cycle_start..]
                        .iter()
                        .map(|&n| n.to_string())
                        .collect();
                    let cycle_str = cycle_nodes.join(" -> ");
                    errors.push(ValidationError::CycleDetected(format!(
                        "Cycle detected: {} -> {}",
                        cycle_str, neighbor
                    )));
                }
            }
        }

        path.pop();
        rec_stack.remove(node);
    }

    let mut path = Vec::new();
    for node in &graph.nodes {
        if !visited.contains(&node.id) {
            dfs(
                &node.id,
                &adjacency,
                &mut visited,
                &mut rec_stack,
                &mut path,
                &mut errors,
            );
        }
    }

    if errors.is_empty() {
        Ok(())
    } else {
        Err(errors)
    }
}

/// Validate that the graph follows the canonical DAG flow rules.
/// Root nodes must be Intent, leaf nodes should be Test or Artifact.
pub fn validate_dag_flow(graph: &IntentGraph) -> ValidationResult {
    let mut errors = Vec::new();
    let ontology = Ontology::default();
    let rules = &ontology.dag_flow.validation_rules;

    // Identify roots (no incoming edges)
    let mut has_incoming: HashSet<&NodeId> = HashSet::new();
    for edge in &graph.edges {
        has_incoming.insert(&edge.target);
    }

    let roots: Vec<&Node> = graph
        .nodes
        .iter()
        .filter(|n| !has_incoming.contains(&n.id))
        .collect();

    // Check root types
    if rules.no_cycles && !rules.root_nodes_must_be.is_empty() {
        for root in &roots {
            if !rules.root_nodes_must_be.contains(&root.node_type) {
                errors.push(ValidationError::DagFlowViolation(format!(
                    "Root node {} has type {:?}, but must be one of {:?}",
                    root.id, root.node_type, rules.root_nodes_must_be
                )));
            }
        }
    }

    // Identify leaves (no outgoing edges)
    let mut has_outgoing: HashSet<&NodeId> = HashSet::new();
    for edge in &graph.edges {
        has_outgoing.insert(&edge.source);
    }

    let leaves: Vec<&Node> = graph
        .nodes
        .iter()
        .filter(|n| !has_outgoing.contains(&n.id))
        .collect();

    // Prefer leaf types
    if !rules.leaf_nodes_prefer.is_empty() {
        for leaf in &leaves {
            if !rules.leaf_nodes_prefer.contains(&leaf.node_type) {
                errors.push(ValidationError::DagFlowViolation(format!(
                    "Leaf node {} has type {:?}, but preferred types are {:?}",
                    leaf.id, leaf.node_type, rules.leaf_nodes_prefer
                )));
            }
        }
    }

    // Check that nodes with edges have at least one root
    if !graph.nodes.is_empty() && !graph.edges.is_empty() && roots.is_empty() {
        errors.push(ValidationError::DagFlowViolation(
            "Graph has edges but no root nodes (no nodes without incoming edges)"
                .to_string(),
        ));
    }

    if errors.is_empty() {
        Ok(())
    } else {
        Err(errors)
    }
}