//! Dependency Checker
//!
//! Detects circular dependencies among SCROLL tasks using Tarjan's strongly
//! connected components (SCC) algorithm. Also validates that every task
//! dependency reference points to a known task, and checks for self-references.

use std::collections::{HashMap, HashSet};
use std::sync::Arc;

use anyhow::Result;
use tracing::{debug, instrument, warn};

use crate::db::KuzuGraph;
use crate::types::{Severity, Task, ValidationResult};

/// Detects cycles and validates the integrity of the task dependency graph.
pub struct DependencyChecker {
    kuzu: Arc<KuzuGraph>,
}

// ---------------------------------------------------------------------------
// Internal graph representation
// ---------------------------------------------------------------------------

/// A lightweight adjacency-list directed graph keyed by node identifiers.
#[derive(Debug, Default)]
struct DependencyGraph {
    /// Maps a node ID to its set of successor node IDs.
    adjacency: HashMap<String, Vec<String>>,
    /// All node IDs in insertion order.
    nodes: Vec<String>,
}

impl DependencyGraph {
    fn new() -> Self {
        Self::default()
    }

    fn add_node(&mut self, id: String) {
        if !self.adjacency.contains_key(&id) {
            self.adjacency.insert(id.clone(), Vec::new());
            self.nodes.push(id);
        }
    }

    fn add_edge(&mut self, from: String, to: String) {
        // Ensure both endpoints are present.
        self.add_node(from.clone());
        self.add_node(to.clone());
        self.adjacency.entry(from).or_default().push(to);
    }

    fn successors(&self, id: &str) -> &[String] {
        self.adjacency
            .get(id)
            .map(|v| v.as_slice())
            .unwrap_or(&[])
    }

    fn node_ids(&self) -> &[String] {
        &self.nodes
    }
}

// ---------------------------------------------------------------------------
// Tarjan's SCC
// ---------------------------------------------------------------------------

/// Per-node bookkeeping for Tarjan's algorithm.
struct TarjanState {
    index_counter: usize,
    stack: Vec<String>,
    on_stack: HashSet<String>,
    index: HashMap<String, usize>,
    lowlink: HashMap<String, usize>,
    /// Strongly connected components with size > 1 (i.e., cycles).
    sccs: Vec<Vec<String>>,
}

impl TarjanState {
    fn new() -> Self {
        Self {
            index_counter: 0,
            stack: Vec::new(),
            on_stack: HashSet::new(),
            index: HashMap::new(),
            lowlink: HashMap::new(),
            sccs: Vec::new(),
        }
    }
}

/// Run Tarjan's SCC algorithm on `graph`, returning all strongly connected
/// components that contain more than one node (each one represents a cycle).
fn tarjan_scc(graph: &DependencyGraph) -> Vec<Vec<String>> {
    let mut state = TarjanState::new();

    for node in graph.node_ids() {
        if !state.index.contains_key(node) {
            strongconnect(node, graph, &mut state);
        }
    }

    state.sccs
}

fn strongconnect(v: &str, graph: &DependencyGraph, state: &mut TarjanState) {
    let idx = state.index_counter;
    state.index.insert(v.to_string(), idx);
    state.lowlink.insert(v.to_string(), idx);
    state.index_counter += 1;
    state.stack.push(v.to_string());
    state.on_stack.insert(v.to_string());

    for w in graph.successors(v) {
        if !state.index.contains_key(w.as_str()) {
            // Successor w has not yet been visited; recurse.
            strongconnect(w, graph, state);
            let w_low = state.lowlink[w];
            let v_low = state.lowlink[v];
            if w_low < v_low {
                state.lowlink.insert(v.to_string(), w_low);
            }
        } else if state.on_stack.contains(w.as_str()) {
            // Successor w is on the stack and hence in the current SCC.
            let w_idx = state.index[w];
            let v_low = state.lowlink[v];
            if w_idx < v_low {
                state.lowlink.insert(v.to_string(), w_idx);
            }
        }
    }

    // If v is a root node, pop the SCC.
    if state.lowlink[v] == state.index[v] {
        let mut component = Vec::new();
        loop {
            let w = state.stack.pop().expect("stack should not be empty");
            state.on_stack.remove(&w);
            component.push(w.clone());
            if w == v {
                break;
            }
        }
        // Only report components with more than one node (actual cycles).
        // Also check for self-loops.
        if component.len() > 1 {
            // Reverse so the cycle reads in forward traversal order.
            component.reverse();
            state.sccs.push(component);
        } else if component.len() == 1 {
            // Check for a self-loop.
            let node = &component[0];
            if graph.successors(node).contains(node) {
                state.sccs.push(component);
            }
        }
    }
}

// ---------------------------------------------------------------------------
// DependencyChecker implementation
// ---------------------------------------------------------------------------

impl DependencyChecker {
    pub fn new(kuzu: Arc<KuzuGraph>) -> Self {
        Self { kuzu }
    }

    /// Main entry point: check for circular dependencies among the supplied
    /// tasks. Returns one `ValidationResult` per detected cycle, plus a
    /// summary pass/fail, plus results for dangling and self-referencing deps.
    #[instrument(skip(self, tasks), fields(task_count = tasks.len()))]
    pub async fn check_circular_dependencies(
        &self,
        tasks: &[Task],
    ) -> Result<Vec<ValidationResult>> {
        let mut results = Vec::new();

        if tasks.is_empty() {
            results.push(ValidationResult {
                constraint_id: "dep_check".to_string(),
                passed: true,
                message: "No tasks to check for circular dependencies".to_string(),
                severity: Severity::Info,
            });
            return Ok(results);
        }

        // Pre-check: validate that dependency references are valid task IDs.
        let dangling = self.check_dangling_dependencies(tasks);
        results.extend(dangling);

        // Pre-check: detect self-referencing tasks.
        let self_refs = self.check_self_references(tasks);
        results.extend(self_refs);

        // Build the dependency graph from task declarations and Kuzu edges.
        let graph = self.build_dependency_graph(tasks).await?;

        // Run Tarjan's SCC to find cycles.
        let cycles = tarjan_scc(&graph);

        if cycles.is_empty() {
            debug!("No circular dependencies detected");
            results.push(ValidationResult {
                constraint_id: "circular_deps".to_string(),
                passed: true,
                message: "No circular dependencies detected".to_string(),
                severity: Severity::Info,
            });
        } else {
            for (i, cycle) in cycles.iter().enumerate() {
                let cycle_display = format_cycle(cycle);
                warn!(cycle = %cycle_display, "Circular dependency detected");
                results.push(ValidationResult {
                    constraint_id: format!("circular_dep_{}", i),
                    passed: false,
                    message: format!("Circular dependency detected: {}", cycle_display),
                    severity: Severity::Error,
                });
            }
        }

        Ok(results)
    }

    /// Build a `DependencyGraph` from the tasks' explicit `dependencies`
    /// fields and from file-level edges in the Kuzu knowledge graph.
    async fn build_dependency_graph(&self, tasks: &[Task]) -> Result<DependencyGraph> {
        let mut graph = DependencyGraph::new();

        // Index tasks by target file so we can resolve file-level deps back
        // to tasks.
        let task_by_file: HashMap<&str, &Task> =
            tasks.iter().map(|t| (t.target_file.as_str(), t)).collect();

        for task in tasks {
            graph.add_node(task.id.clone());

            // Explicit task-level dependencies.
            for dep_id in &task.dependencies {
                graph.add_edge(task.id.clone(), dep_id.clone());
            }

            // File-level dependency edges from Kuzu.
            let file_deps = self.kuzu.get_dependencies(&task.target_file).await?;
            for dep_file in &file_deps {
                // Map the file dependency back to a task ID if one targets
                // that file.
                if let Some(dep_task) = task_by_file.get(dep_file.as_str()) {
                    if dep_task.id != task.id {
                        graph.add_edge(task.id.clone(), dep_task.id.clone());
                    }
                }
            }
        }

        debug!(
            nodes = graph.node_ids().len(),
            "Dependency graph constructed"
        );
        Ok(graph)
    }

    /// Check that every declared dependency ID actually refers to a task in
    /// the current SCROLL. Dangling references are Error-severity failures.
    fn check_dangling_dependencies(&self, tasks: &[Task]) -> Vec<ValidationResult> {
        let known_ids: HashSet<&str> = tasks.iter().map(|t| t.id.as_str()).collect();
        let mut results = Vec::new();

        for task in tasks {
            for dep_id in &task.dependencies {
                if !known_ids.contains(dep_id.as_str()) {
                    results.push(ValidationResult {
                        constraint_id: format!("dangling_dep_{}_{}", task.id, dep_id),
                        passed: false,
                        message: format!(
                            "Task '{}' depends on '{}', which is not a known task in this SCROLL",
                            task.id, dep_id
                        ),
                        severity: Severity::Error,
                    });
                }
            }
        }

        results
    }

    /// Detect tasks that list themselves as a dependency.
    fn check_self_references(&self, tasks: &[Task]) -> Vec<ValidationResult> {
        let mut results = Vec::new();

        for task in tasks {
            if task.dependencies.contains(&task.id) {
                results.push(ValidationResult {
                    constraint_id: format!("self_ref_{}", task.id),
                    passed: false,
                    message: format!(
                        "Task '{}' has a self-referencing dependency",
                        task.id
                    ),
                    severity: Severity::Error,
                });
            }
        }

        results
    }
}

/// Format a cycle as `A -> B -> C -> A` for display.
fn format_cycle(cycle: &[String]) -> String {
    if cycle.is_empty() {
        return String::new();
    }
    let mut display = cycle.join(" -> ");
    display.push_str(" -> ");
    display.push_str(&cycle[0]);
    display
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use crate::types::{Task, TaskStatus, TaskType};
    use chrono::Utc;
    use std::path::Path;

    fn make_task(id: &str, deps: Vec<&str>) -> Task {
        Task {
            id: id.to_string(),
            scroll_id: "scroll_1".to_string(),
            description: format!("Task {}", id),
            target_file: format!("src/{}.rs", id),
            task_type: TaskType::Create,
            status: TaskStatus::Pending,
            dependencies: deps.into_iter().map(String::from).collect(),
            generated_code: None,
            diff: None,
            created_at: Utc::now(),
            group_label: None,
        }
    }

    fn next_test_id() -> u64 {
        static COUNTER: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
        COUNTER.fetch_add(1, std::sync::atomic::Ordering::SeqCst)
    }

    async fn make_checker() -> DependencyChecker {
        let kuzu = Arc::new(
            KuzuGraph::new(Path::new(&format!("/tmp/furnace_test_dc_kuzu_{}_{}", std::process::id(), next_test_id())))
                .expect("failed to create test KuzuGraph"),
        );
        DependencyChecker::new(kuzu)
    }

    // -- Tarjan unit tests (pure, no async) --

    #[test]
    fn test_tarjan_no_cycle() {
        let mut g = DependencyGraph::new();
        g.add_edge("A".into(), "B".into());
        g.add_edge("B".into(), "C".into());
        let sccs = tarjan_scc(&g);
        assert!(sccs.is_empty(), "Expected no cycles");
    }

    #[test]
    fn test_tarjan_simple_cycle() {
        let mut g = DependencyGraph::new();
        g.add_edge("A".into(), "B".into());
        g.add_edge("B".into(), "A".into());
        let sccs = tarjan_scc(&g);
        assert_eq!(sccs.len(), 1);
        let scc = &sccs[0];
        assert!(scc.contains(&"A".to_string()));
        assert!(scc.contains(&"B".to_string()));
    }

    #[test]
    fn test_tarjan_three_node_cycle() {
        let mut g = DependencyGraph::new();
        g.add_edge("A".into(), "B".into());
        g.add_edge("B".into(), "C".into());
        g.add_edge("C".into(), "A".into());
        let sccs = tarjan_scc(&g);
        assert_eq!(sccs.len(), 1);
        assert_eq!(sccs[0].len(), 3);
    }

    #[test]
    fn test_tarjan_self_loop() {
        let mut g = DependencyGraph::new();
        g.add_edge("A".into(), "A".into());
        let sccs = tarjan_scc(&g);
        assert_eq!(sccs.len(), 1);
        assert_eq!(sccs[0], vec!["A".to_string()]);
    }

    #[test]
    fn test_tarjan_multiple_independent_cycles() {
        let mut g = DependencyGraph::new();
        // Cycle 1: A <-> B
        g.add_edge("A".into(), "B".into());
        g.add_edge("B".into(), "A".into());
        // Cycle 2: C <-> D
        g.add_edge("C".into(), "D".into());
        g.add_edge("D".into(), "C".into());
        let sccs = tarjan_scc(&g);
        assert_eq!(sccs.len(), 2);
    }

    #[test]
    fn test_tarjan_empty_graph() {
        let g = DependencyGraph::new();
        let sccs = tarjan_scc(&g);
        assert!(sccs.is_empty());
    }

    #[test]
    fn test_tarjan_disconnected_no_cycle() {
        let mut g = DependencyGraph::new();
        g.add_node("A".into());
        g.add_node("B".into());
        g.add_node("C".into());
        let sccs = tarjan_scc(&g);
        assert!(sccs.is_empty());
    }

    #[test]
    fn test_tarjan_complex_graph() {
        // Graph:
        //   A -> B -> C -> A  (cycle)
        //   C -> D -> E       (tail, no cycle)
        //   E -> F -> E       (cycle)
        let mut g = DependencyGraph::new();
        g.add_edge("A".into(), "B".into());
        g.add_edge("B".into(), "C".into());
        g.add_edge("C".into(), "A".into());
        g.add_edge("C".into(), "D".into());
        g.add_edge("D".into(), "E".into());
        g.add_edge("E".into(), "F".into());
        g.add_edge("F".into(), "E".into());
        let sccs = tarjan_scc(&g);
        assert_eq!(sccs.len(), 2);
    }

    // -- Integration-level async tests --

    #[tokio::test]
    async fn test_no_tasks() {
        let checker = make_checker().await;
        let results = checker.check_circular_dependencies(&[]).await.unwrap();
        assert_eq!(results.len(), 1);
        assert!(results[0].passed);
    }

    #[tokio::test]
    async fn test_linear_dependencies() {
        let checker = make_checker().await;
        let tasks = vec![
            make_task("t1", vec![]),
            make_task("t2", vec!["t1"]),
            make_task("t3", vec!["t2"]),
        ];
        let results = checker.check_circular_dependencies(&tasks).await.unwrap();
        assert!(results.iter().all(|r| r.passed));
    }

    #[tokio::test]
    async fn test_circular_dependency_detected() {
        let checker = make_checker().await;
        let tasks = vec![
            make_task("t1", vec!["t3"]),
            make_task("t2", vec!["t1"]),
            make_task("t3", vec!["t2"]),
        ];
        let results = checker.check_circular_dependencies(&tasks).await.unwrap();
        let failures: Vec<_> = results.iter().filter(|r| !r.passed).collect();
        assert!(!failures.is_empty(), "Should detect at least one cycle");
    }

    #[tokio::test]
    async fn test_dangling_dependency() {
        let checker = make_checker().await;
        let tasks = vec![make_task("t1", vec!["nonexistent"])];
        let results = checker.check_circular_dependencies(&tasks).await.unwrap();
        let failures: Vec<_> = results.iter().filter(|r| !r.passed).collect();
        assert!(!failures.is_empty());
        assert!(failures[0].message.contains("not a known task"));
    }

    #[tokio::test]
    async fn test_self_reference() {
        let checker = make_checker().await;
        let tasks = vec![make_task("t1", vec!["t1"])];
        let results = checker.check_circular_dependencies(&tasks).await.unwrap();
        let failures: Vec<_> = results.iter().filter(|r| !r.passed).collect();
        assert!(!failures.is_empty());
        assert!(failures[0].message.contains("self-referencing"));
    }

    #[test]
    fn test_format_cycle() {
        let cycle = vec!["A".into(), "B".into(), "C".into()];
        assert_eq!(format_cycle(&cycle), "A -> B -> C -> A");
    }

    #[test]
    fn test_format_cycle_empty() {
        let cycle: Vec<String> = vec![];
        assert_eq!(format_cycle(&cycle), "");
    }
}
