clnrm_core/validation/

graph_validator.rs

//! Graph topology validation for span relationships
//!
//! Validates graph structure of OTEL spans including:
//! - Required edges (must_include)
//! - Forbidden edges (must_not_cross)
//! - Acyclicity checks

use crate::error::{CleanroomError, Result};
use crate::validation::span_validator::SpanData;
use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet};

/// Graph topology expectations for span relationships
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GraphExpectation {
    /// Required edges: list of (parent_name, child_name) tuples that MUST exist
    pub must_include: Vec<(String, String)>,

    /// Forbidden edges: list of (parent_name, child_name) tuples that MUST NOT exist
    #[serde(skip_serializing_if = "Option::is_none")]
    pub must_not_cross: Option<Vec<(String, String)>>,

    /// If true, validates that the span graph has no cycles
    #[serde(skip_serializing_if = "Option::is_none")]
    pub acyclic: Option<bool>,
}

impl GraphExpectation {
    /// Create a new GraphExpectation with required edges only
    pub fn new(must_include: Vec<(String, String)>) -> Self {
        Self {
            must_include,
            must_not_cross: None,
            acyclic: None,
        }
    }

    /// Set forbidden edges
    pub fn with_must_not_cross(mut self, must_not_cross: Vec<(String, String)>) -> Self {
        self.must_not_cross = Some(must_not_cross);
        self
    }

    /// Enable acyclicity check
    pub fn with_acyclic(mut self, acyclic: bool) -> Self {
        self.acyclic = Some(acyclic);
        self
    }

    /// Validate graph topology against the given spans
    ///
    /// # Arguments
    /// * `spans` - The spans to validate
    ///
    /// # Returns
    /// * `Result<()>` - Ok if validation passes, error with details if it fails
    ///
    /// # Errors
    /// * Missing required edges
    /// * Presence of forbidden edges
    /// * Cycles detected when acyclic=true
    pub fn validate(&self, spans: &[SpanData]) -> Result<()> {
        let validator = GraphValidator::new(spans);

        // Validate must_include edges
        for (parent_name, child_name) in &self.must_include {
            validator.validate_edge_exists(parent_name, child_name)?;
        }

        // Validate must_not_cross edges
        if let Some(ref forbidden_edges) = self.must_not_cross {
            for (parent_name, child_name) in forbidden_edges {
                validator.validate_edge_not_exists(parent_name, child_name)?;
            }
        }

        // Validate acyclicity
        if let Some(true) = self.acyclic {
            validator.validate_acyclic()?;
        }

        Ok(())
    }
}

/// Graph validator for span relationships
pub struct GraphValidator<'a> {
    /// The spans being validated
    spans: &'a [SpanData],

    /// Map from span_id to SpanData for quick lookup
    span_by_id: HashMap<String, &'a SpanData>,

    /// Map from span name to list of spans with that name
    spans_by_name: HashMap<String, Vec<&'a SpanData>>,
}

impl<'a> GraphValidator<'a> {
    /// Create a new GraphValidator
    pub fn new(spans: &'a [SpanData]) -> Self {
        let mut span_by_id = HashMap::new();
        let mut spans_by_name: HashMap<String, Vec<&SpanData>> = HashMap::new();

        for span in spans {
            span_by_id.insert(span.span_id.clone(), span);
            spans_by_name
                .entry(span.name.clone())
                .or_default()
                .push(span);
        }

        Self {
            spans,
            span_by_id,
            spans_by_name,
        }
    }

    /// Validate that at least one edge exists between parent_name and child_name
    ///
    /// # Arguments
    /// * `parent_name` - Name of parent span
    /// * `child_name` - Name of child span
    ///
    /// # Returns
    /// * `Result<()>` - Ok if edge exists, error otherwise
    ///
    /// # Errors
    /// * Parent span not found
    /// * Child span not found
    /// * No edge found between parent and child
    pub fn validate_edge_exists(&self, parent_name: &str, child_name: &str) -> Result<()> {
        let parent_spans = self.spans_by_name.get(parent_name).ok_or_else(|| {
            CleanroomError::validation_error(format!(
                "Graph validation failed: parent span '{}' not found",
                parent_name
            ))
        })?;

        let child_spans = self.spans_by_name.get(child_name).ok_or_else(|| {
            CleanroomError::validation_error(format!(
                "Graph validation failed: child span '{}' not found",
                child_name
            ))
        })?;

        // Check if any child has any parent as its parent_span_id
        let edge_exists = child_spans.iter().any(|child| {
            if let Some(ref parent_id) = child.parent_span_id {
                parent_spans
                    .iter()
                    .any(|parent| &parent.span_id == parent_id)
            } else {
                false
            }
        });

        if !edge_exists {
            return Err(CleanroomError::validation_error(format!(
                "Graph validation failed: required edge '{}' -> '{}' not found",
                parent_name, child_name
            )));
        }

        Ok(())
    }

    /// Validate that NO edge exists between parent_name and child_name
    ///
    /// # Arguments
    /// * `parent_name` - Name of parent span
    /// * `child_name` - Name of child span
    ///
    /// # Returns
    /// * `Result<()>` - Ok if edge does NOT exist, error if it does
    ///
    /// # Errors
    /// * Forbidden edge was found
    pub fn validate_edge_not_exists(&self, parent_name: &str, child_name: &str) -> Result<()> {
        // If either span doesn't exist, the edge can't exist (valid)
        let Some(parent_spans) = self.spans_by_name.get(parent_name) else {
            return Ok(());
        };

        let Some(child_spans) = self.spans_by_name.get(child_name) else {
            return Ok(());
        };

        // Check if any child has any parent as its parent_span_id
        let edge_exists = child_spans.iter().any(|child| {
            if let Some(ref parent_id) = child.parent_span_id {
                parent_spans
                    .iter()
                    .any(|parent| &parent.span_id == parent_id)
            } else {
                false
            }
        });

        if edge_exists {
            return Err(CleanroomError::validation_error(format!(
                "Graph validation failed: forbidden edge '{}' -> '{}' found",
                parent_name, child_name
            )));
        }

        Ok(())
    }

    /// Validate that the span graph is acyclic (no cycles)
    ///
    /// Uses depth-first search with visited tracking to detect cycles.
    ///
    /// # Returns
    /// * `Result<()>` - Ok if acyclic, error if cycle detected
    ///
    /// # Errors
    /// * Cycle detected in graph
    pub fn validate_acyclic(&self) -> Result<()> {
        // Track visited spans and spans in current DFS path
        let mut visited = HashSet::new();
        let mut in_path = HashSet::new();

        // DFS from each span to detect cycles
        for span in self.spans {
            if !visited.contains(&span.span_id) {
                if let Some(cycle_path) =
                    self.detect_cycle_dfs(span, &mut visited, &mut in_path, &mut Vec::new())
                {
                    return Err(CleanroomError::validation_error(format!(
                        "Graph validation failed: cycle detected in span graph: {}",
                        cycle_path.join(" -> ")
                    )));
                }
            }
        }

        Ok(())
    }

    /// Perform DFS to detect cycles, returning cycle path if found
    fn detect_cycle_dfs(
        &self,
        span: &SpanData,
        visited: &mut HashSet<String>,
        in_path: &mut HashSet<String>,
        path: &mut Vec<String>,
    ) -> Option<Vec<String>> {
        visited.insert(span.span_id.clone());
        in_path.insert(span.span_id.clone());
        path.push(span.name.clone());

        // Check parent (reverse direction - child points to parent)
        if let Some(ref parent_id) = span.parent_span_id {
            if let Some(parent) = self.span_by_id.get(parent_id) {
                if in_path.contains(parent_id) {
                    // Cycle detected - build cycle path
                    path.push(parent.name.clone());
                    return Some(path.clone());
                }

                if !visited.contains(parent_id) {
                    if let Some(cycle) = self.detect_cycle_dfs(parent, visited, in_path, path) {
                        return Some(cycle);
                    }
                }
            }
        }

        in_path.remove(&span.span_id);
        path.pop();
        None
    }

    /// Get all edges in the graph as (parent_name, child_name) pairs
    pub fn get_all_edges(&self) -> Vec<(String, String)> {
        let mut edges = Vec::new();

        for child in self.spans {
            if let Some(ref parent_id) = child.parent_span_id {
                if let Some(parent) = self.span_by_id.get(parent_id) {
                    edges.push((parent.name.clone(), child.name.clone()));
                }
            }
        }

        edges
    }
}