use indexmap::IndexMap;
use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::visit::EdgeRef;

use crate::model::Pipeline;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DepKind {
    /// Explicit `needs:` dependency
    Needs,
    /// Implicit stage ordering dependency
    Stage,
}

/// A positioned job node for rendering.
#[derive(Debug, Clone)]
pub struct JobNode {
    pub name: String,
    #[allow(dead_code)] // Used by dispatch mode
    pub stage: String,
    /// Column index (dependency-depth based)
    pub col: usize,
    /// Row index within the column
    pub row: usize,
    /// Whether the job is manual
    pub is_manual: bool,
    /// Whether the job has rules: when: never (disabled)
    pub is_never: bool,
    /// Whether the job has unresolved extends (tolerant mode)
    pub is_unresolved: bool,
    /// Whether the job allows failure
    pub allow_failure: bool,
}

/// An edge between two job nodes.
#[derive(Debug, Clone)]
pub struct Edge {
    pub from: String,
    pub to: String,
    #[allow(dead_code)] // Structural field for edge rendering
    pub kind: DepKind,
}

/// A stage header that can span multiple columns.
#[derive(Debug, Clone)]
pub struct StageHeader {
    pub name: String,
    /// First column this stage occupies
    pub start_col: usize,
    /// Number of columns this stage spans
    pub num_cols: usize,
}

/// The complete layout for rendering the pipeline DAG.
#[derive(Debug, Clone)]
pub struct GraphLayout {
    pub nodes: Vec<JobNode>,
    pub edges: Vec<Edge>,
    /// Number of columns
    pub num_cols: usize,
    /// Stage headers with column spans
    pub stage_headers: Vec<StageHeader>,
    /// Map from job name to node index in `nodes`
    pub node_index: IndexMap<String, usize>,
}

impl GraphLayout {
    pub fn compute(
        pipeline: &Pipeline,
        graph: &DiGraph<String, DepKind>,
        node_indices: &IndexMap<String, NodeIndex>,
    ) -> Self {
        let mut edges = Vec::new();

        for edge_ref in graph.edge_references() {
            let from_name = &graph[edge_ref.source()];
            let to_name = &graph[edge_ref.target()];
            edges.push(Edge {
                from: from_name.clone(),
                to: to_name.clone(),
                kind: *edge_ref.weight(),
            });
        }

        // Step 1: Compute each job's column based on dependency depth.
        let mut job_col: IndexMap<String, usize> = IndexMap::new();

        let topo_order = match petgraph::algo::toposort(graph, None) {
            Ok(order) => order,
            Err(_) => node_indices.values().copied().collect(),
        };

        for node_idx in &topo_order {
            let job_name = &graph[*node_idx];
            if !pipeline.jobs.contains_key(job_name) {
                continue;
            }

            let max_pred_col = graph
                .edges_directed(*node_idx, petgraph::Direction::Incoming)
                .filter_map(|e| {
                    let pred_name = &graph[e.source()];
                    job_col.get(pred_name).copied()
                })
                .max();

            let col = match max_pred_col {
                Some(pred_col) => pred_col + 1,
                None => 0,
            };

            job_col.insert(job_name.clone(), col);
        }

        // Step 2: Ensure stages don't share columns. Each stage's minimum column
        // must be greater than the previous stage's maximum column.
        let mut prev_stage_max_col: Option<usize> = None;

        for stage in &pipeline.stages {
            // Find current min and max columns for this stage's jobs
            let stage_cols: Vec<usize> = stage
                .job_names
                .iter()
                .filter_map(|name| job_col.get(name).copied())
                .collect();

            if stage_cols.is_empty() {
                continue;
            }

            let stage_min = *stage_cols.iter().min().unwrap();

            // If this stage overlaps with the previous, shift all its jobs right
            if let Some(prev_max) = prev_stage_max_col
                && stage_min <= prev_max
            {
                let shift = prev_max + 1 - stage_min;
                for job_name in &stage.job_names {
                    if let Some(col) = job_col.get_mut(job_name) {
                        *col += shift;
                    }
                }
            }

            // Recompute this stage's max after potential shift
            let stage_max = stage
                .job_names
                .iter()
                .filter_map(|name| job_col.get(name).copied())
                .max()
                .unwrap();

            prev_stage_max_col = Some(stage_max);
        }

        let num_cols = job_col.values().copied().max().map(|m| m + 1).unwrap_or(1);

        // Step 3: Build stage headers with column spans
        let mut stage_headers = Vec::new();
        for stage in &pipeline.stages {
            let stage_cols: Vec<usize> = stage
                .job_names
                .iter()
                .filter_map(|name| job_col.get(name).copied())
                .collect();

            if stage_cols.is_empty() {
                continue;
            }

            let min_col = *stage_cols.iter().min().unwrap();
            let max_col = *stage_cols.iter().max().unwrap();

            stage_headers.push(StageHeader {
                name: stage.name.clone(),
                start_col: min_col,
                num_cols: max_col - min_col + 1,
            });
        }

        // Step 4: Assign row positions using pipeline order
        let mut col_row_count: Vec<usize> = vec![0; num_cols];
        let mut nodes = Vec::new();
        let mut node_index_map: IndexMap<String, usize> = IndexMap::new();

        for stage in &pipeline.stages {
            for job_name in &stage.job_names {
                let job = match pipeline.jobs.get(job_name) {
                    Some(j) => j,
                    None => continue,
                };
                let col = job_col.get(job_name).copied().unwrap_or(0);
                let row = col_row_count[col];
                col_row_count[col] += 1;

                let idx = nodes.len();
                node_index_map.insert(job_name.clone(), idx);
                nodes.push(JobNode {
                    name: job_name.clone(),
                    stage: job.stage.clone(),
                    col,
                    row,
                    is_manual: job.is_manual(),
                    is_never: job.is_never(),
                    is_unresolved: job.is_unresolved(),
                    allow_failure: job.allow_failure,
                });
            }
        }

        GraphLayout {
            nodes,
            edges,
            num_cols,
            stage_headers,
            node_index: node_index_map,
        }
    }

    pub fn get_node(&self, name: &str) -> Option<&JobNode> {
        self.node_index.get(name).map(|&i| &self.nodes[i])
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::model::{Job, JobDebugInfo, Pipeline, ResolvedNeed, Stage};

    fn make_job(name: &str, stage: &str) -> Job {
        Job {
            name: name.to_string(),
            stage: stage.to_string(),
            image: None,
            services: vec![],
            variables: IndexMap::new(),
            before_script: vec![],
            script: vec!["echo hi".to_string()],
            after_script: vec![],
            needs: vec![],
            artifact_sources: Some(vec![]),
            tags: vec![],
            when_val: "on_success".to_string(),
            allow_failure: false,
            rules_never: false,
            unresolved_extends: vec![],
            rules_summary: vec![],
            artifacts_paths: vec![],
            artifacts_exclude: vec![],
            artifacts_untracked: false,
            artifacts_when: "on_success".to_string(),
            dotenv_report: None,
            timeout: None,
            resource_group: None,
            coverage: None,
            resolved_yaml: String::new(),
            trigger_file: None,
            build_context: None,
            docker_entrypoint: None,
            step_id: None,
            steps: vec![],
            debug_info: JobDebugInfo::default(),
        }
    }

    fn make_job_with_needs(name: &str, stage: &str, needs: &[&str]) -> Job {
        let mut job = make_job(name, stage);
        job.needs = needs
            .iter()
            .map(|n| ResolvedNeed {
                job_name: n.to_string(),
                artifacts: true,
                optional: false,
            })
            .collect();
        job
    }

    fn make_pipeline(stages: &[(&str, &[&str])]) -> Pipeline {
        let mut jobs = IndexMap::new();
        let mut stage_list = Vec::new();
        for (stage_name, job_names) in stages {
            stage_list.push(Stage {
                name: stage_name.to_string(),
                job_names: job_names.iter().map(|s| s.to_string()).collect(),
            });
            for name in *job_names {
                jobs.insert(name.to_string(), make_job(name, stage_name));
            }
        }
        Pipeline {
            stages: stage_list,
            jobs,
            execution: Default::default(),
            checkout_path: None,
        }
    }

    /// Build a pipeline with custom Job objects (for setting needs).
    fn pipeline_from_jobs(stages: &[(&str, Vec<Job>)]) -> Pipeline {
        let mut jobs = IndexMap::new();
        let mut stage_list = Vec::new();
        for (stage_name, stage_jobs) in stages {
            let job_names: Vec<String> = stage_jobs.iter().map(|j| j.name.clone()).collect();
            stage_list.push(Stage {
                name: stage_name.to_string(),
                job_names,
            });
            for job in stage_jobs {
                jobs.insert(job.name.clone(), job.clone());
            }
        }
        Pipeline {
            stages: stage_list,
            jobs,
            execution: Default::default(),
            checkout_path: None,
        }
    }

    fn layout(pipeline: &Pipeline) -> GraphLayout {
        crate::graph::compute_layout(pipeline)
    }

    // --- Basic layout ---

    #[test]
    fn test_single_job() {
        let p = make_pipeline(&[("build", &["compile"])]);
        let l = layout(&p);

        assert_eq!(l.nodes.len(), 1);
        assert_eq!(l.num_cols, 1);
        let node = l.get_node("compile").unwrap();
        assert_eq!(node.col, 0);
        assert_eq!(node.row, 0);
    }

    #[test]
    fn test_empty_pipeline() {
        let p = Pipeline {
            stages: vec![],
            jobs: IndexMap::new(),
            execution: Default::default(),
            checkout_path: None,
        };
        let l = layout(&p);

        assert_eq!(l.nodes.len(), 0);
        assert_eq!(l.num_cols, 1); // default
        assert!(l.stage_headers.is_empty());
    }

    #[test]
    fn test_linear_three_stages() {
        // build -> test -> deploy (implicit stage deps)
        let p = make_pipeline(&[
            ("build", &["compile"]),
            ("test", &["unit"]),
            ("deploy", &["ship"]),
        ]);
        let l = layout(&p);

        assert_eq!(l.nodes.len(), 3);
        assert_eq!(l.num_cols, 3);
        assert_eq!(l.get_node("compile").unwrap().col, 0);
        assert_eq!(l.get_node("unit").unwrap().col, 1);
        assert_eq!(l.get_node("ship").unwrap().col, 2);
    }

    #[test]
    fn test_parallel_jobs_same_stage() {
        let p = make_pipeline(&[("test", &["unit", "lint", "format"])]);
        let l = layout(&p);

        assert_eq!(l.num_cols, 1);
        // All in column 0, different rows
        for name in &["unit", "lint", "format"] {
            assert_eq!(l.get_node(name).unwrap().col, 0);
        }
        let rows: Vec<usize> = ["unit", "lint", "format"]
            .iter()
            .map(|n| l.get_node(n).unwrap().row)
            .collect();
        // Rows should be 0, 1, 2 (unique, in pipeline order)
        assert_eq!(rows, vec![0, 1, 2]);
    }

    // --- Dependency depth ---

    #[test]
    fn test_explicit_needs_sets_column() {
        // compile (build) -> unit (test), with explicit needs
        let p = pipeline_from_jobs(&[
            ("build", vec![make_job("compile", "build")]),
            (
                "test",
                vec![make_job_with_needs("unit", "test", &["compile"])],
            ),
        ]);
        let l = layout(&p);

        assert_eq!(l.get_node("compile").unwrap().col, 0);
        assert_eq!(l.get_node("unit").unwrap().col, 1);
    }

    #[test]
    fn test_diamond_dependency() {
        //   compile
        //   /    \
        // unit  lint
        //   \    /
        //   deploy
        let p = pipeline_from_jobs(&[
            ("build", vec![make_job("compile", "build")]),
            (
                "test",
                vec![
                    make_job_with_needs("unit", "test", &["compile"]),
                    make_job_with_needs("lint", "test", &["compile"]),
                ],
            ),
            (
                "deploy",
                vec![make_job_with_needs("deploy", "deploy", &["unit", "lint"])],
            ),
        ]);
        let l = layout(&p);

        assert_eq!(l.get_node("compile").unwrap().col, 0);
        assert_eq!(l.get_node("unit").unwrap().col, 1);
        assert_eq!(l.get_node("lint").unwrap().col, 1);
        assert_eq!(l.get_node("deploy").unwrap().col, 2);
    }

    #[test]
    fn test_multiple_parents_max_depth() {
        // a (col 0) -> c (col 2)
        // a -> b (col 1) -> c
        // c's col = max(0, 1) + 1 = 2
        let p = pipeline_from_jobs(&[
            ("s1", vec![make_job("a", "s1")]),
            ("s2", vec![make_job_with_needs("b", "s2", &["a"])]),
            ("s3", vec![make_job_with_needs("c", "s3", &["a", "b"])]),
        ]);
        let l = layout(&p);

        assert_eq!(l.get_node("a").unwrap().col, 0);
        assert_eq!(l.get_node("b").unwrap().col, 1);
        assert_eq!(l.get_node("c").unwrap().col, 2);
    }

    // --- Stage boundary enforcement ---

    #[test]
    fn test_stage_boundary_no_overlap() {
        // Two stages, each with one job, no needs.
        // Implicit stage deps: test depends on build.
        // build jobs get col 0, test jobs get col 1.
        let p = make_pipeline(&[("build", &["compile"]), ("test", &["unit"])]);
        let l = layout(&p);

        let build_col = l.get_node("compile").unwrap().col;
        let test_col = l.get_node("unit").unwrap().col;
        assert!(test_col > build_col, "test stage must be after build stage");
    }

    #[test]
    fn test_stage_boundary_shift() {
        // Stage 1: a, b  (b needs a, so b gets col 1)
        // Stage 2: c (no explicit needs → implicit stage dep on a,b → col 2)
        // But without explicit needs, c depends implicitly on stage 1 jobs,
        // max predecessor col is 1 (from b), so c = col 2.
        // Stage boundary should enforce c is in a column after b.
        let p = pipeline_from_jobs(&[
            (
                "build",
                vec![
                    make_job("a", "build"),
                    make_job_with_needs("b", "build", &["a"]),
                ],
            ),
            ("test", vec![make_job("c", "test")]),
        ]);
        let l = layout(&p);

        let a_col = l.get_node("a").unwrap().col;
        let b_col = l.get_node("b").unwrap().col;
        let c_col = l.get_node("c").unwrap().col;
        assert_eq!(a_col, 0);
        assert_eq!(b_col, 1);
        assert!(
            c_col > b_col,
            "c must be shifted past build stage's max col"
        );
    }

    #[test]
    fn test_stages_never_share_columns() {
        // Three stages, 2 jobs each. Even though all first-stage jobs are col 0,
        // later stages must not reuse col 0.
        let p = make_pipeline(&[
            ("build", &["b1", "b2"]),
            ("test", &["t1", "t2"]),
            ("deploy", &["d1", "d2"]),
        ]);
        let l = layout(&p);

        let build_max = ["b1", "b2"]
            .iter()
            .map(|n| l.get_node(n).unwrap().col)
            .max()
            .unwrap();
        let test_min = ["t1", "t2"]
            .iter()
            .map(|n| l.get_node(n).unwrap().col)
            .min()
            .unwrap();
        let test_max = ["t1", "t2"]
            .iter()
            .map(|n| l.get_node(n).unwrap().col)
            .max()
            .unwrap();
        let deploy_min = ["d1", "d2"]
            .iter()
            .map(|n| l.get_node(n).unwrap().col)
            .min()
            .unwrap();

        assert!(test_min > build_max, "test must start after build ends");
        assert!(deploy_min > test_max, "deploy must start after test ends");
    }

    // --- Stage headers ---

    #[test]
    fn test_stage_headers_single_col() {
        let p = make_pipeline(&[("build", &["compile"]), ("test", &["unit"])]);
        let l = layout(&p);

        assert_eq!(l.stage_headers.len(), 2);
        assert_eq!(l.stage_headers[0].name, "build");
        assert_eq!(l.stage_headers[0].num_cols, 1);
        assert_eq!(l.stage_headers[1].name, "test");
        assert_eq!(l.stage_headers[1].num_cols, 1);
        assert!(l.stage_headers[1].start_col > l.stage_headers[0].start_col);
    }

    #[test]
    fn test_stage_header_multi_col_span() {
        // build stage: a and b, where b needs a → b is col 1
        // build header should span cols 0..1 (num_cols=2)
        let p = pipeline_from_jobs(&[(
            "build",
            vec![
                make_job("a", "build"),
                make_job_with_needs("b", "build", &["a"]),
            ],
        )]);
        let l = layout(&p);

        assert_eq!(l.stage_headers.len(), 1);
        assert_eq!(l.stage_headers[0].name, "build");
        assert_eq!(l.stage_headers[0].start_col, 0);
        assert_eq!(l.stage_headers[0].num_cols, 2);
    }

    // --- Edges ---

    #[test]
    fn test_edges_explicit_needs() {
        let p = pipeline_from_jobs(&[
            ("build", vec![make_job("compile", "build")]),
            (
                "test",
                vec![make_job_with_needs("unit", "test", &["compile"])],
            ),
        ]);
        let l = layout(&p);

        assert_eq!(l.edges.len(), 1);
        assert_eq!(l.edges[0].from, "compile");
        assert_eq!(l.edges[0].to, "unit");
        assert_eq!(l.edges[0].kind, DepKind::Needs);
    }

    #[test]
    fn test_edges_implicit_stage() {
        // No explicit needs → implicit deps on all jobs in previous stage
        let p = make_pipeline(&[("build", &["a", "b"]), ("test", &["c"])]);
        let l = layout(&p);

        // c should have Stage edges from both a and b
        let c_edges: Vec<&Edge> = l.edges.iter().filter(|e| e.to == "c").collect();
        assert_eq!(c_edges.len(), 2);
        let mut sources: Vec<&str> = c_edges.iter().map(|e| e.from.as_str()).collect();
        sources.sort();
        assert_eq!(sources, vec!["a", "b"]);
        assert!(c_edges.iter().all(|e| e.kind == DepKind::Stage));
    }

    #[test]
    fn test_first_stage_no_incoming_edges() {
        let p = make_pipeline(&[("build", &["a", "b"]), ("test", &["c"])]);
        let l = layout(&p);

        let a_incoming: Vec<&Edge> = l.edges.iter().filter(|e| e.to == "a").collect();
        let b_incoming: Vec<&Edge> = l.edges.iter().filter(|e| e.to == "b").collect();
        assert!(a_incoming.is_empty());
        assert!(b_incoming.is_empty());
    }

    // --- Node properties ---

    #[test]
    fn test_node_properties_manual() {
        let mut job = make_job("deploy", "deploy");
        job.when_val = "manual".to_string();
        let p = pipeline_from_jobs(&[("deploy", vec![job])]);
        let l = layout(&p);

        assert!(l.get_node("deploy").unwrap().is_manual);
    }

    #[test]
    fn test_node_properties_never() {
        let mut job = make_job("skip", "test");
        job.rules_never = true;
        let p = pipeline_from_jobs(&[("test", vec![job])]);
        let l = layout(&p);

        assert!(l.get_node("skip").unwrap().is_never);
    }

    #[test]
    fn test_node_properties_unresolved() {
        let mut job = make_job("broken", "test");
        job.unresolved_extends = vec![".missing".to_string()];
        let p = pipeline_from_jobs(&[("test", vec![job])]);
        let l = layout(&p);

        assert!(l.get_node("broken").unwrap().is_unresolved);
    }

    #[test]
    fn test_node_properties_allow_failure() {
        let mut job = make_job("flaky", "test");
        job.allow_failure = true;
        let p = pipeline_from_jobs(&[("test", vec![job])]);
        let l = layout(&p);

        assert!(l.get_node("flaky").unwrap().allow_failure);
    }

    // --- Node index / get_node ---

    #[test]
    fn test_get_node_found() {
        let p = make_pipeline(&[("build", &["compile"])]);
        let l = layout(&p);
        assert!(l.get_node("compile").is_some());
    }

    #[test]
    fn test_get_node_not_found() {
        let p = make_pipeline(&[("build", &["compile"])]);
        let l = layout(&p);
        assert!(l.get_node("nonexistent").is_none());
    }

    #[test]
    fn test_node_index_complete() {
        let p = make_pipeline(&[("build", &["a", "b"]), ("test", &["c", "d"])]);
        let l = layout(&p);

        assert_eq!(l.node_index.len(), 4);
        for name in &["a", "b", "c", "d"] {
            assert!(l.node_index.contains_key(*name));
        }
    }

    // --- Complex pipeline ---

    #[test]
    fn test_realistic_pipeline() {
        // Simulates a real CI:
        //   build: compile, lint (parallel)
        //   test: unit (needs compile), integration (needs compile)
        //   deploy: staging (needs unit, integration)
        let p = pipeline_from_jobs(&[
            (
                "build",
                vec![make_job("compile", "build"), make_job("lint", "build")],
            ),
            (
                "test",
                vec![
                    make_job_with_needs("unit", "test", &["compile"]),
                    make_job_with_needs("integration", "test", &["compile"]),
                ],
            ),
            (
                "deploy",
                vec![make_job_with_needs(
                    "staging",
                    "deploy",
                    &["unit", "integration"],
                )],
            ),
        ]);
        let l = layout(&p);

        // compile and lint are in build stage
        assert_eq!(l.get_node("compile").unwrap().col, 0);
        assert_eq!(l.get_node("lint").unwrap().col, 0);

        // unit and integration need compile → col 1
        assert_eq!(l.get_node("unit").unwrap().col, 1);
        assert_eq!(l.get_node("integration").unwrap().col, 1);

        // staging needs both test jobs → col 2
        assert_eq!(l.get_node("staging").unwrap().col, 2);

        // Stages don't overlap
        assert_eq!(l.stage_headers.len(), 3);

        // 5 edges: compile→unit, compile→integration, unit→staging, integration→staging
        // lint has no outgoing needs edges, but if someone depends on it implicitly... no.
        // lint has no dependents with explicit needs, and test jobs have explicit needs
        // so lint should have 0 outgoing edges.
        let lint_outgoing: Vec<&Edge> = l.edges.iter().filter(|e| e.from == "lint").collect();
        assert!(lint_outgoing.is_empty());
    }
}
