nornir 0.5.2

//! Topological ROOT-CAUSE analysis for a failed publish/preflight cascade
//! (release-improvements item #9).
//!
//! A `doctor --publish` preflight (or the promote FAIL-STOP) can collect a
//! FLAT list of many failures that are really ONE problem seen from N angles:
//! a single dependency published without its new API makes every dependent
//! fail `cargo publish --dry-run` verify ("uses API from `gatling` that isn't
//! in the PUBLISHED `gatling`"). The operator then chases six symptoms instead
//! of the one root.
//!
//! This module partitions the failure set against the publish dependency graph:
//!   * a failure is a **ROOT** iff none of its (transitive) publish-dependencies
//!     are ALSO in the failure set — nothing upstream explains it;
//!   * a failure is **DOWNSTREAM** iff it (transitively) depends on a failed
//!     crate — that failed dependency explains it.
//! Multiple independent roots are supported: the set is split into root(s) plus
//! the downstream crates each root "unblocks" once fixed.
//!
//! Two edge sources are combined, so the analysis works even when the true root
//! was SKIPPED and never appeared as its own failure (the real incident:
//! `gatling` was `AlreadyPublished`, so it was NOT a preflight issue, yet all
//! six dependents' verify errors BLAMED it):
//!   1. the repo/publish dependency graph ([`WorkspaceGraph`]); and
//!   2. explicit `blames` captured on each failure — the crate a verify error
//!      names as the un-published API source. A blamed crate that is not itself
//!      a failure is synthesised as an INFERRED root.
//!
//! Pure and deterministic (BTree-ordered); the entry point is
//! [`classify_roots`], wrapped by [`analyze`] for the printable summary.

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

use crate::warehouse::dep_graph::WorkspaceGraph;

/// One collected failure: the crate name, a short human reason (from the
/// captured per-crate error), and the crate(s) its error explicitly BLAMES as
/// the un-published upstream (empty for a self-contained failure). The blames
/// are crate-precise edges the repo-level [`WorkspaceGraph`] may not carry.
#[derive(Debug, Clone)]
pub struct FailedCrate {
    pub name: String,
    pub reason: String,
    pub blames: Vec<String>,
}

impl FailedCrate {
    /// Convenience constructor with no blames (self-contained failure).
    pub fn new(name: impl Into<String>, reason: impl Into<String>) -> Self {
        Self { name: name.into(), reason: reason.into(), blames: Vec::new() }
    }

    /// Project a preflight [`Issue`](crate::release::preflight::Issue) onto a
    /// failure node. The issue's `detail` is the reason; a `VerifyFailed` issue
    /// carries the blamed dependency in `blames`, so a dep that was skipped
    /// (never its own issue) is still recovered as the inferred root.
    pub fn from_issue(issue: &crate::release::preflight::Issue) -> Self {
        Self {
            name: issue.krate.clone(),
            reason: issue.detail.clone(),
            blames: issue.blames.clone(),
        }
    }
}

/// One ROOT and the downstream failures it explains. `unblocks` is the sorted
/// set of failed crates that (transitively) depend on `root` — fix `root` and
/// they become publishable.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RootGroup {
    pub root: String,
    pub reason: String,
    pub unblocks: Vec<String>,
}

/// The whole classification: every ROOT (with its explained downstream set) and
/// the distinct downstream crates overall.
#[derive(Debug, Clone, Default)]
pub struct RootCauseSummary {
    pub roots: Vec<RootGroup>,
    /// Distinct downstream (non-root) failures, sorted.
    pub downstream: Vec<String>,
}

/// Reason attached to a root that was INFERRED from its dependents' blames
/// rather than collected as its own failure — the "skipped as AlreadyPublished,
/// new API never uploaded" case.
const INFERRED_ROOT_REASON: &str =
    "edited with a new API but not published (skipped as AlreadyPublished) — \
     dependents can't build against the published version";

/// Partition `failures` into ROOT(s) + downstream against the publish
/// dependency `graph`. Returns one [`RootGroup`] per root (roots that explain
/// downstream first — most explained, then name), each carrying the sorted set
/// of failures it unblocks. A root that is itself downstream of a NON-failed
/// crate is still a root (only failed deps count).
pub fn classify_roots(failures: &[FailedCrate], graph: &WorkspaceGraph) -> Vec<RootGroup> {
    analyze(failures, graph).roots
}

/// Full analysis: [`classify_roots`] plus the distinct downstream set, for the
/// printable [`RootCauseSummary::format`] header/footer.
pub fn analyze(failures: &[FailedCrate], graph: &WorkspaceGraph) -> RootCauseSummary {
    // Reasons + blame edges of the REAL (collected) failures.
    let mut reason: BTreeMap<String, String> = BTreeMap::new();
    let mut blame_edges: BTreeMap<String, BTreeSet<String>> = BTreeMap::new();
    for f in failures {
        reason.entry(f.name.clone()).or_insert_with(|| f.reason.clone());
        blame_edges
            .entry(f.name.clone())
            .or_default()
            .extend(f.blames.iter().cloned());
    }

    // Node set = collected failures ∪ every blamed crate. A blamed crate that is
    // not itself a collected failure is an INFERRED node (the skipped root).
    let mut nodes: BTreeSet<String> = reason.keys().cloned().collect();
    for f in failures {
        for b in &f.blames {
            nodes.insert(b.clone());
        }
    }

    // Transitive failed-dependencies of each node, over BOTH edge sources
    // (graph forward closure + blame closure), intersected with the node set.
    let tdeps: BTreeMap<String, BTreeSet<String>> = nodes
        .iter()
        .map(|n| (n.clone(), transitive_failed_deps(n, &nodes, graph, &blame_edges)))
        .collect();

    // ROOT ⟺ no failed (transitive) dependency. Everything else is downstream.
    let roots: BTreeSet<String> = nodes
        .iter()
        .filter(|n| tdeps[*n].is_empty())
        .cloned()
        .collect();
    let downstream: Vec<String> =
        nodes.iter().filter(|n| !roots.contains(*n)).cloned().collect();

    // Attribute each downstream to the root(s) it transitively depends on.
    let mut unblocks: BTreeMap<String, BTreeSet<String>> =
        roots.iter().map(|r| (r.clone(), BTreeSet::new())).collect();
    for d in &downstream {
        for r in tdeps[d].intersection(&roots) {
            unblocks.get_mut(r).unwrap().insert(d.clone());
        }
    }

    let mut groups: Vec<RootGroup> = roots
        .iter()
        .map(|r| RootGroup {
            root: r.clone(),
            reason: reason
                .get(r)
                .cloned()
                .unwrap_or_else(|| INFERRED_ROOT_REASON.to_string()),
            unblocks: unblocks[r].iter().cloned().collect(),
        })
        .collect();
    // Roots that explain the most first (then alphabetical) — "fix these, in order".
    groups.sort_by(|a, b| {
        b.unblocks
            .len()
            .cmp(&a.unblocks.len())
            .then_with(|| a.root.cmp(&b.root))
    });

    RootCauseSummary { roots: groups, downstream }
}

/// Every FAILED crate (in `nodes`) that `start` transitively depends on, via the
/// repo graph's forward closure UNION the blame closure. Excludes `start`.
fn transitive_failed_deps(
    start: &str,
    nodes: &BTreeSet<String>,
    graph: &WorkspaceGraph,
    blame_edges: &BTreeMap<String, BTreeSet<String>>,
) -> BTreeSet<String> {
    let mut reached: BTreeSet<String> = BTreeSet::new();
    // Repo-graph forward closure (already transitive; spans non-failed nodes too).
    if graph.has_component(start) {
        reached.extend(graph.deps_transitive(start));
    }
    // Blame closure: follow blamed crates, chaining through any that are
    // themselves failures with their own blames.
    let mut stack: Vec<String> =
        blame_edges.get(start).into_iter().flatten().cloned().collect();
    while let Some(cur) = stack.pop() {
        if !reached.insert(cur.clone()) {
            continue;
        }
        if graph.has_component(&cur) {
            reached.extend(graph.deps_transitive(&cur));
        }
        if let Some(bs) = blame_edges.get(&cur) {
            stack.extend(bs.iter().cloned());
        }
    }
    reached.remove(start);
    // Only FAILED crates count for root classification.
    reached.intersection(nodes).cloned().collect()
}

impl RootCauseSummary {
    /// The root-cause summary block, or "" when there is nothing to summarise
    /// (no root explains any downstream — the flat list already suffices).
    ///
    /// ```text
    /// ROOT CAUSE(S) — fix these, in order:
    ///   ⛔ gatling — <reason> → unblocks: lbzip2, lgz, ljar, …
    /// (12 downstream failures explained by 2 roots)
    /// ```
    pub fn format(&self) -> String {
        let explaining: Vec<&RootGroup> =
            self.roots.iter().filter(|g| !g.unblocks.is_empty()).collect();
        if explaining.is_empty() {
            return String::new();
        }
        let mut s = String::from("\nROOT CAUSE(S) — fix these, in order:\n");
        for g in &explaining {
            s.push_str(&format!(
                "  \u{26D4} {} — {} → unblocks: {}\n",
                g.root,
                g.reason,
                g.unblocks.join(", ")
            ));
        }
        s.push_str(&format!(
            "({} downstream failure{} explained by {} root{})\n",
            self.downstream.len(),
            if self.downstream.len() == 1 { "" } else { "s" },
            explaining.len(),
            if explaining.len() == 1 { "" } else { "s" }
        ));
        s
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::warehouse::dep_graph::{CrossRepoEdge, WorkspaceGraph};

    /// Build a graph from `consumer → dependency` pairs (the publish-dep
    /// convention: `from` consumes what `to` produces).
    fn graph(edges: &[(&str, &str)]) -> WorkspaceGraph {
        let e: Vec<CrossRepoEdge> = edges
            .iter()
            .map(|(from, to)| {
                let mut via = BTreeSet::new();
                via.insert((*to).to_string());
                CrossRepoEdge::normal(*from, *to, via)
            })
            .collect();
        WorkspaceGraph::from_query_parts(Default::default(), e)
    }

    fn names(v: &[String]) -> Vec<&str> {
        v.iter().map(String::as_str).collect()
    }

    /// (a) ONE root, MANY downstream — the real `gatling` incident. Six
    /// dependents each fail verify; `gatling` itself is the collected root.
    #[test]
    fn one_root_many_downstream() {
        let g = graph(&[
            ("lbzip2", "gatling"),
            ("lgz", "gatling"),
            ("ljar", "gatling"),
            ("lzip-parallel", "gatling"),
            ("znippy-zoomies", "gatling"),
            ("osm-katana", "gatling"),
        ]);
        let failures = vec![
            FailedCrate::new("gatling", "already-published: new API never uploaded"),
            FailedCrate::new("lbzip2", "verify: uses API not in published gatling"),
            FailedCrate::new("lgz", "verify"),
            FailedCrate::new("ljar", "verify"),
            FailedCrate::new("lzip-parallel", "verify"),
            FailedCrate::new("znippy-zoomies", "verify"),
            FailedCrate::new("osm-katana", "verify"),
        ];
        let summary = analyze(&failures, &g);
        assert_eq!(summary.roots.len(), 1, "exactly one root");
        let root = &summary.roots[0];
        assert_eq!(root.root, "gatling");
        assert_eq!(
            names(&root.unblocks),
            vec!["lbzip2", "lgz", "ljar", "lzip-parallel", "osm-katana", "znippy-zoomies"]
        );
        assert_eq!(summary.downstream.len(), 6);
        let text = summary.format();
        assert!(text.contains("ROOT CAUSE(S)"), "{text}");
        assert!(text.contains("6 downstream failures explained by 1 root"), "{text}");
    }

    /// The skipped-root case: `gatling` is NOT its own failure (skipped as
    /// AlreadyPublished), but every dependent BLAMES it. It is recovered as an
    /// INFERRED root with the inferred reason.
    #[test]
    fn inferred_root_from_blames_when_root_was_skipped() {
        let g = graph(&[("lbzip2", "gatling"), ("lgz", "gatling")]);
        let failures = vec![
            FailedCrate { name: "lbzip2".into(), reason: "verify".into(), blames: vec!["gatling".into()] },
            FailedCrate { name: "lgz".into(), reason: "verify".into(), blames: vec!["gatling".into()] },
        ];
        let summary = analyze(&failures, &g);
        assert_eq!(summary.roots.len(), 1);
        assert_eq!(summary.roots[0].root, "gatling");
        assert_eq!(names(&summary.roots[0].unblocks), vec!["lbzip2", "lgz"]);
        assert!(summary.roots[0].reason.contains("AlreadyPublished"));
        assert_eq!(names(&summary.downstream), vec!["lbzip2", "lgz"]);
    }

    /// (b) TWO INDEPENDENT roots, each with its own downstream. Partition must
    /// keep the two blast-radii separate.
    #[test]
    fn two_independent_roots() {
        let g = graph(&[
            ("app-a", "core-x"),
            ("lib-a", "core-x"),
            ("app-b", "core-y"),
        ]);
        let failures = vec![
            FailedCrate::new("core-x", "dirty tree"),
            FailedCrate::new("app-a", "verify"),
            FailedCrate::new("lib-a", "verify"),
            FailedCrate::new("core-y", "missing metadata"),
            FailedCrate::new("app-b", "verify"),
        ];
        let roots = classify_roots(&failures, &g);
        assert_eq!(roots.len(), 2, "two roots");
        // Most-explained first: core-x (2) before core-y (1).
        assert_eq!(roots[0].root, "core-x");
        assert_eq!(names(&roots[0].unblocks), vec!["app-a", "lib-a"]);
        assert_eq!(roots[0].reason, "dirty tree");
        assert_eq!(roots[1].root, "core-y");
        assert_eq!(names(&roots[1].unblocks), vec!["app-b"]);

        let summary = analyze(&failures, &g);
        assert!(
            summary.format().contains("3 downstream failures explained by 2 roots"),
            "{}",
            summary.format()
        );
    }

    /// (c) A root that is itself DOWNSTREAM of a NON-FAILED crate. `gatling`
    /// depends on `serde` (not failed), so `gatling` is STILL a root: only
    /// failed deps disqualify a root.
    #[test]
    fn root_downstream_of_non_failed_crate_is_still_root() {
        let g = graph(&[
            ("gatling", "serde"), // serde is NOT in the failure set
            ("lbzip2", "gatling"),
        ]);
        let failures = vec![
            FailedCrate::new("gatling", "already-published"),
            FailedCrate::new("lbzip2", "verify"),
        ];
        let roots = classify_roots(&failures, &g);
        assert_eq!(roots.len(), 1, "serde is not failed ⇒ gatling is the sole root");
        assert_eq!(roots[0].root, "gatling");
        assert_eq!(names(&roots[0].unblocks), vec!["lbzip2"]);
    }

    /// A CHAIN root → mid → leaf: the deepest failed crate is the single root
    /// and unblocks BOTH the mid and the leaf (transitive attribution).
    #[test]
    fn transitive_chain_attributes_all_to_the_deepest_root() {
        let g = graph(&[("leaf", "mid"), ("mid", "root")]);
        let failures = vec![
            FailedCrate::new("root", "dirty"),
            FailedCrate::new("mid", "verify"),
            FailedCrate::new("leaf", "verify"),
        ];
        let roots = classify_roots(&failures, &g);
        assert_eq!(roots.len(), 1);
        assert_eq!(roots[0].root, "root");
        assert_eq!(names(&roots[0].unblocks), vec!["leaf", "mid"]);
    }

    /// No downstream (every failure independent) ⇒ empty summary text: the flat
    /// list already tells the whole story, so we don't add noise.
    #[test]
    fn all_independent_failures_produce_no_summary() {
        let g = graph(&[]);
        let failures = vec![
            FailedCrate::new("a", "metadata"),
            FailedCrate::new("b", "metadata"),
        ];
        let summary = analyze(&failures, &g);
        assert_eq!(summary.roots.len(), 2, "both are roots");
        assert!(summary.downstream.is_empty());
        assert_eq!(summary.format(), "", "nothing to explain ⇒ no block");
    }
}