pipechecker 0.2.5

//! Dependency graph auditor - detects circular dependencies and missing job references
//!
//! This module analyzes job dependencies using a directed graph:
//! - Builds a dependency graph from job `needs` relationships
//! - Uses Tarjan's SCC algorithm to detect cycles
//! - Reports missing dependencies (references to non-existent jobs)

use crate::error::Result;
use crate::models::{Issue, Pipeline, Severity};
use petgraph::algo::tarjan_scc;
use petgraph::graph::DiGraph;
use std::collections::HashMap;

/// Audit a pipeline for dependency-related issues
///
/// Checks for:
/// - Circular dependencies between jobs
/// - References to non-existent jobs in `needs` clauses
pub fn audit(pipeline: &Pipeline) -> Result<Vec<Issue>> {
    let mut issues = Vec::new();

    // Build dependency graph
    let mut graph = DiGraph::new();
    let mut job_indices = HashMap::new();

    // Add nodes
    for job in &pipeline.jobs {
        let idx = graph.add_node(job.id.clone());
        job_indices.insert(job.id.clone(), idx);
    }

    // Add edges
    for job in &pipeline.jobs {
        let from_idx = job_indices[&job.id];
        for dep in &job.depends_on {
            if let Some(&to_idx) = job_indices.get(dep) {
                graph.add_edge(from_idx, to_idx, ());
            } // Missing dependency errors are handled in the syntax auditor; skip duplicate reporting
        }
    }

    // Detect cycles using Tarjan's algorithm
    let sccs = tarjan_scc(&graph);
    for scc in sccs {
        if scc.len() > 1 {
            let job_names: Vec<_> = scc.iter().map(|&idx| graph[idx].clone()).collect();
            // Find line of first job in the cycle for location
            let first_job = &job_names[0];
            let (line, col) = pipeline.find_job_line(first_job, "runs-on");
            issues.push(Issue::for_job(
                Severity::Error,
                &format!("Circular dependency detected: {}", job_names.join(" -> ")),
                first_job,
                line,
                col,
                Some("Remove one of the dependencies to break the cycle".to_string()),
            ));
        }
    }
    Ok(issues)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::parsers::github;

    #[test]
    fn test_missing_dependency() {
        let yaml = r#"on:
  push: {}
jobs:
  build:
    needs: nonexistent
    runs-on: ubuntu-latest
    steps: []
"#;
        let pipeline = github::parse(yaml).unwrap();
        let issues = audit(&pipeline).unwrap();
        // DAG auditor does not report missing dependencies (handled by syntax auditor);
        // Ensure it runs without error and returns zero issues for this case.
        assert!(issues.is_empty());
    }

    #[test]
    fn test_circular_dependency() {
        let yaml = r#"on:
  push: {}
jobs:
  a:
    needs: b
    runs-on: ubuntu-latest
    steps: []
  b:
    needs: a
    runs-on: ubuntu-latest
    steps: []
"#;
        let pipeline = github::parse(yaml).unwrap();
        let issues = audit(&pipeline).unwrap();
        assert!(issues
            .iter()
            .any(|i| i.message.contains("Circular dependency detected")));
    }
}