//! AIRGAP8 — dependency-ordered install + start.
//!
//! Design (`.nornir/airgap-install.md` §2 Phase 3): products may point at each
//! other, so bring-up is a **topo-sorted** walk of the `depends_on` graph.
//! nornir owns dep-graph machinery (`src/warehouse/dep_graph.rs` / `mimir.rs`)
//! but it lives behind nornir's heavy deps; this lean crate re-implements the
//! same **Kahn topological sort** (sources first) self-contained — the algorithm
//! is small and the seam is just `&[Product]`.
//!
//! [`start_order`] returns a flat dependency-respecting order; [`start_waves`]
//! returns the parallelizable **waves** (each wave = all products whose deps are
//! already started — the `install-system.md` Phase 4 model). Cycles are a hard
//! error (an install that can never converge).

use std::collections::{BTreeMap, BTreeSet, VecDeque};

use anyhow::{anyhow, Result};

use crate::product::Product;

/// Flat dependency-ordered start order (Kahn topo sort, sources first). Errors
/// on a cycle, naming the products still entangled.
pub fn start_order(products: &[Product]) -> Result<Vec<String>> {
    Ok(start_waves(products)?.into_iter().flatten().collect())
}

/// Dependency-respecting **teardown** order — the reverse of [`start_order`], so a
/// dependent is stopped/removed **before** the thing it depends on (the Go
/// bundler's `destroy`, AIRGAP-TEARDOWN). A caller walks this order calling
/// `Installer::remove` per component. Same cycle error as [`start_order`].
pub fn teardown_order(products: &[Product]) -> Result<Vec<String>> {
    let mut order = start_order(products)?;
    order.reverse();
    Ok(order)
}

/// Dependency-ordered **waves**: wave `i` holds every product all of whose
/// `depends_on` appear in waves `< i`. Within a wave, products are independent
/// and can be started concurrently (LAW: no rayon — a caller uses
/// `std::thread::scope`/gatling over a wave). Order within a wave is stable
/// (sorted) for deterministic tests.
pub fn start_waves(products: &[Product]) -> Result<Vec<Vec<String>>> {
    let names: BTreeSet<&str> = products.iter().map(|p| p.name.as_str()).collect();

    // Build in-degree + adjacency over only the known products (ignore deps that
    // point outside this set — e.g. `network.target` — they're not our nodes).
    let mut indeg: BTreeMap<String, usize> = BTreeMap::new();
    let mut dependents: BTreeMap<String, Vec<String>> = BTreeMap::new();
    for p in products {
        indeg.entry(p.name.clone()).or_insert(0);
        for dep in &p.depends_on {
            if names.contains(dep.as_str()) {
                *indeg.entry(p.name.clone()).or_insert(0) += 1;
                dependents.entry(dep.clone()).or_default().push(p.name.clone());
            }
        }
    }

    // Kahn: repeatedly take all in-degree-0 nodes as a wave.
    let mut waves: Vec<Vec<String>> = Vec::new();
    let mut ready: VecDeque<String> = indeg
        .iter()
        .filter(|&(_, &d)| d == 0)
        .map(|(n, _)| n.clone())
        .collect();
    let mut done = 0usize;
    while !ready.is_empty() {
        let mut wave: Vec<String> = ready.drain(..).collect();
        wave.sort();
        let mut next: BTreeSet<String> = BTreeSet::new();
        for n in &wave {
            done += 1;
            if let Some(deps) = dependents.get(n) {
                for d in deps {
                    let e = indeg.get_mut(d).expect("dependent tracked");
                    *e -= 1;
                    if *e == 0 {
                        next.insert(d.clone());
                    }
                }
            }
        }
        waves.push(wave);
        ready.extend(next);
    }

    if done != indeg.len() {
        let stuck: Vec<String> = indeg
            .iter()
            .filter(|&(_, &d)| d != 0)
            .map(|(n, _)| n.clone())
            .collect();
        return Err(anyhow!(
            "dependency cycle among products: {} (cannot order an install that never converges)",
            stuck.join(", ")
        ));
    }
    Ok(waves)
}

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

    fn p(name: &str, after: &[&str]) -> Product {
        Product {
            name: name.into(),
            user: format!("_{name}"),
            depends_on: after.iter().map(|s| s.to_string()).collect(),
            ports: vec![],
        }
    }

    /// LAW 1 (inject-assert): feed a real 5-node dep graph, assert the topo
    /// WAVES match the expected dependency-ordered bring-up
    /// (holger → nornir-server → {mail,tunnr}), and the flat order respects deps.
    #[test]
    fn topo_waves_from_fixture_dep_graph() {
        let products = vec![
            p("tunnr", &["nornir-server"]),
            p("nornir-server", &["holger"]),
            p("mail-server", &["nornir-server"]),
            p("holger", &[]),
            p("pki", &[]), // independent root → joins wave 1
        ];

        let waves = start_waves(&products).unwrap();
        // Wave 1: the two roots (sorted).
        assert_eq!(waves[0], vec!["holger", "pki"]);
        // Wave 2: nornir-server (after holger).
        assert_eq!(waves[1], vec!["nornir-server"]);
        // Wave 3: mail-server + tunnr (both after nornir-server, sorted).
        assert_eq!(waves[2], vec!["mail-server", "tunnr"]);

        // Flat order respects every edge: a dep precedes its dependent.
        let order = start_order(&products).unwrap();
        let pos = |n: &str| order.iter().position(|x| x == n).unwrap();
        assert!(pos("holger") < pos("nornir-server"));
        assert!(pos("nornir-server") < pos("mail-server"));
        assert!(pos("nornir-server") < pos("tunnr"));
        assert_eq!(order.len(), 5);
    }

    /// Deps that point outside the product set (e.g. `network.target`) are
    /// ignored, not treated as missing nodes.
    #[test]
    fn external_deps_are_ignored() {
        let products = vec![p("holger", &["network.target"])];
        assert_eq!(start_order(&products).unwrap(), vec!["holger"]);
    }

    /// Teardown is the exact reverse of start — a dependent is removed before the
    /// thing it depends on (holger dies last).
    #[test]
    fn teardown_is_reverse_of_start() {
        let products = vec![
            p("tunnr", &["nornir-server"]),
            p("nornir-server", &["holger"]),
            p("holger", &[]),
        ];
        let mut expected = start_order(&products).unwrap();
        expected.reverse();
        let td = teardown_order(&products).unwrap();
        assert_eq!(td, expected);
        let pos = |n: &str| td.iter().position(|x| x == n).unwrap();
        assert!(pos("tunnr") < pos("nornir-server"));
        assert!(pos("nornir-server") < pos("holger"));
    }

    /// A cycle is a hard error naming the entangled products.
    #[test]
    fn cycle_is_rejected() {
        let products = vec![p("a", &["b"]), p("b", &["a"])];
        let err = start_waves(&products).unwrap_err().to_string();
        assert!(err.contains("cycle"), "got: {err}");
        assert!(err.contains('a') && err.contains('b'));
    }
}
