nornir 0.5.2

//! `nornir release doctor` — the **mathematical foundations**: the graph-theory +
//! optimization core the advisory doctor reasons over, so its answers are *derived*
//! (SCC / topo / MFAS / planning) instead of hand-coded heuristics.
//!
//! Model: the constellation is a directed graph `G=(V,E)` — `V` = crates (cargo
//! publishes CRATES, so that's the granularity), `E` = publish-order-gating edges
//! (`A→B` ⇔ `A` has an in-workspace Normal/Build `path` dep on `B` ⇒ `B` must
//! publish first). The gating graph is already built in [`super::doctor`]'s
//! `RepoGraph`/`crate_graph`; this module supplies the pure algorithms over it:
//!
//! * [`tarjan_scc`] — strongly-connected components, `O(V+E)`. Every SCC with >1
//!   node (or a self-loop) is *exactly* a dependency cycle.
//! * [`condense`] → [`Condensation`] — collapse each SCC to a super-node; the
//!   condensation `G/SCC` is always a DAG. [`Condensation::topo_order`] gives the
//!   coarse publish order, [`Condensation::waves`] the parallelizable antichains.
//! * [`min_feedback_arc_set`] — per-SCC MFAS: constellation SCCs are tiny (2–5
//!   crates) so we EXHAUSTIVELY enumerate edge-subsets and rank the candidate cuts
//!   by cost (DEV = 0, OPTIONAL/feature-gated = 1, crate-split = high) — each cut
//!   carries a proof (the residual topo order) that removing it yields a DAG.
//! * the invertive [`plan`] planner — a STRIPS-style closure over the outcome-space
//!   Ω: remedy operators held in a DATA TABLE ([`remedy_table`]) whose preconditions
//!   are matched against the current [`Symptoms`] and applied to a FIXPOINT. This is
//!   the anti-`if/else`: adding a remedy = adding a row, never a new branch.
//!
//! Everything here is PURE (no I/O), deterministic (BTree-ordered), and independent
//! of how the graph was extracted — the same code serves a source-derived graph and
//! (item 8) a future binary-derived one.

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

/// A directed graph as `node → the set of nodes it points at`. Throughout this
/// module the edge `A→B` reads "**A depends on B**" (B must publish first), matching
/// the doctor's `crate_deps`/`repo_edges` convention.
pub type Adj = BTreeMap<String, BTreeSet<String>>;

// ─────────────────────────── Tarjan SCC ───────────────────────────

/// Tarjan's strongly-connected components over `adj`, `O(V+E)`. Each returned
/// component is a sorted member list; the outer vector is deterministic. Every
/// component with more than one node — or a single node with a self-loop — IS a
/// dependency cycle (the nodes that provably cannot be linearly ordered).
///
/// Iterative (explicit work stack) so a deep graph can't blow the call stack.
pub fn tarjan_scc(adj: &Adj) -> Vec<Vec<String>> {
    let nodes: Vec<String> = adj.keys().cloned().collect();
    let mut index: BTreeMap<String, usize> = BTreeMap::new();
    let mut low: BTreeMap<String, usize> = BTreeMap::new();
    let mut on_stack: BTreeSet<String> = BTreeSet::new();
    let mut stack: Vec<String> = Vec::new();
    let mut idx = 0usize;
    let mut out: Vec<Vec<String>> = Vec::new();

    // Each work frame `(v, i)` resumes v's successor scan at index i.
    for start in &nodes {
        if index.contains_key(start) {
            continue;
        }
        let mut work: Vec<(String, usize)> = vec![(start.clone(), 0)];
        while let Some((v, mut i)) = work.pop() {
            if i == 0 {
                index.insert(v.clone(), idx);
                low.insert(v.clone(), idx);
                idx += 1;
                stack.push(v.clone());
                on_stack.insert(v.clone());
            }
            let succs: Vec<String> =
                adj.get(&v).map(|s| s.iter().cloned().collect()).unwrap_or_default();
            let mut recursed = false;
            while i < succs.len() {
                let w = &succs[i];
                if !index.contains_key(w) {
                    // Descend into the unvisited successor, resuming v after it.
                    work.push((v.clone(), i + 1));
                    work.push((w.clone(), 0));
                    recursed = true;
                    break;
                } else if on_stack.contains(w) {
                    let lw = index[w];
                    let lv = low[&v];
                    low.insert(v.clone(), lv.min(lw));
                }
                i += 1;
            }
            if recursed {
                continue;
            }
            // v is done: a root of its SCC iff its low-link == its own index.
            if low[&v] == index[&v] {
                let mut comp = Vec::new();
                while let Some(w) = stack.pop() {
                    on_stack.remove(&w);
                    comp.push(w.clone());
                    if w == v {
                        break;
                    }
                }
                comp.sort();
                out.push(comp);
            }
            // Fold v's low-link into its parent frame (the caller in the work stack).
            if let Some((parent, _)) = work.last() {
                let lp = low[parent];
                let lv = low[&v];
                low.insert(parent.clone(), lp.min(lv));
            }
        }
    }
    out
}

/// True when a single-node component `[n]` carries a self-loop (`n` depends on
/// itself) — the degenerate one-node cycle Tarjan reports as a size-1 SCC.
pub fn is_self_loop(adj: &Adj, comp: &[String]) -> bool {
    comp.len() == 1 && adj.get(&comp[0]).map(|d| d.contains(&comp[0])).unwrap_or(false)
}

/// The dependency CYCLES in `adj`: every SCC with >1 node, plus every self-loop.
/// (A clean DAG returns an empty vector.) Each cycle is the SCC's sorted node set —
/// the crates whose entanglement no linear order can resolve = the "must-break" set.
pub fn cycles(adj: &Adj) -> Vec<Vec<String>> {
    tarjan_scc(adj)
        .into_iter()
        .filter(|c| c.len() > 1 || is_self_loop(adj, c))
        .collect()
}

// ─────────────────────────── condensation ───────────────────────────

/// The condensation `G/SCC`: each SCC collapsed to a super-node. Because every
/// cycle lives inside one SCC, the condensation is **always a DAG** — so it always
/// topo-sorts (coarse publish order) and layers into antichains (publish waves).
#[derive(Debug, Clone)]
pub struct Condensation {
    /// Component id → its member nodes (sorted). The "must-break" internals.
    pub comps: Vec<Vec<String>>,
    /// Node → the component it belongs to.
    pub comp_of: BTreeMap<String, usize>,
    /// Component → the components it depends on (the condensed edge set; acyclic).
    pub dag: Vec<BTreeSet<usize>>,
}

/// Build the [`Condensation`] of `adj` via [`tarjan_scc`]. `O(V+E)`.
pub fn condense(adj: &Adj) -> Condensation {
    let comps = tarjan_scc(adj);
    let n = comps.len();
    let mut comp_of: BTreeMap<String, usize> = BTreeMap::new();
    for (i, c) in comps.iter().enumerate() {
        for node in c {
            comp_of.insert(node.clone(), i);
        }
    }
    let mut dag: Vec<BTreeSet<usize>> = vec![BTreeSet::new(); n];
    for (from, tos) in adj {
        // A node may be absent from comp_of only if it appears purely as an edge
        // target with no key of its own — treat such nodes as their own trivial
        // component would require adding them; the doctor always keys every node,
        // so guard defensively and skip an unkeyed endpoint.
        let Some(&cf) = comp_of.get(from) else { continue };
        for to in tos {
            if let Some(&ct) = comp_of.get(to) {
                if cf != ct {
                    dag[cf].insert(ct);
                }
            }
        }
    }
    Condensation { comps, comp_of, dag }
}

impl Condensation {
    /// The components that ARE dependency cycles (size >1 super-nodes). Their member
    /// sets are the crates a cut must break.
    pub fn must_break(&self) -> Vec<&[String]> {
        self.comps.iter().filter(|c| c.len() > 1).map(|c| c.as_slice()).collect()
    }

    /// Coarse publish order over the condensation: component ids, **dependencies
    /// first**, Kahn's algorithm. Deterministic (ties by the component's smallest
    /// member name). Always succeeds — the condensation is a DAG.
    pub fn topo_order(&self) -> Vec<usize> {
        let n = self.comps.len();
        // indeg(c) = #components c depends on; a comp that depends on nothing is
        // publishable first.
        let mut indeg: Vec<usize> = (0..n).map(|c| self.dag[c].len()).collect();
        let mut consumers: Vec<Vec<usize>> = vec![Vec::new(); n];
        for (cf, deps) in self.dag.iter().enumerate() {
            for &ct in deps {
                consumers[ct].push(cf);
            }
        }
        let key = |c: usize| self.comps[c].first().cloned().unwrap_or_default();
        let mut ready: BTreeSet<(String, usize)> =
            (0..n).filter(|&c| indeg[c] == 0).map(|c| (key(c), c)).collect();
        let mut order = Vec::new();
        while let Some((k, c)) = ready.iter().next().cloned() {
            ready.remove(&(k, c));
            order.push(c);
            for &con in &consumers[c] {
                indeg[con] -= 1;
                if indeg[con] == 0 {
                    ready.insert((key(con), con));
                }
            }
        }
        order
    }

    /// PARALLELIZABLE PUBLISH WAVES: the DAG layered into antichains. Wave 0 = the
    /// components that depend on nothing (publishable immediately); each later wave
    /// is the components whose every dependency published in an earlier wave. Each
    /// component expands to its member crate names — so a wave is the set of crates
    /// that can be published **concurrently**. Deps-first, deterministic.
    pub fn waves(&self) -> Vec<Vec<String>> {
        let n = self.comps.len();
        let mut indeg: Vec<usize> = (0..n).map(|c| self.dag[c].len()).collect();
        let mut consumers: Vec<Vec<usize>> = vec![Vec::new(); n];
        for (cf, deps) in self.dag.iter().enumerate() {
            for &ct in deps {
                consumers[ct].push(cf);
            }
        }
        let mut frontier: Vec<usize> = (0..n).filter(|&c| indeg[c] == 0).collect();
        let mut waves: Vec<Vec<String>> = Vec::new();
        while !frontier.is_empty() {
            // Expand this antichain's components into crate names (sorted, stable).
            let mut wave: Vec<String> =
                frontier.iter().flat_map(|&c| self.comps[c].iter().cloned()).collect();
            wave.sort();
            waves.push(wave);
            let mut next: Vec<usize> = Vec::new();
            for &c in &frontier {
                for &con in &consumers[c] {
                    indeg[con] -= 1;
                    if indeg[con] == 0 {
                        next.push(con);
                    }
                }
            }
            frontier = next;
        }
        waves
    }
}

// ───────────────────── MFAS (minimum feedback arc set) ─────────────────────

/// How an intra-cycle edge can be cut, and its cost — the MFAS ranking key. Lower is
/// cheaper. A DEV edge is already non-gating (free to reclassify); an OPTIONAL edge
/// is a feature to gate off (cheap); a NORMAL gating edge needs a crate-split (dear).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EdgeClass {
    /// Already a dev-dep — not publish-gating; "cutting" it is free (cost 0).
    Dev,
    /// Feature-gated / optional path dep — gate the feature off (cost 1).
    Optional,
    /// Plain Normal/Build path dep — only a crate-split removes it (high cost).
    Normal,
}

impl EdgeClass {
    /// The cut cost of an edge of this class. `Normal` is the crate-split cost —
    /// deliberately high so the MFAS prefers dev/optional cuts, and rises with the
    /// number of crates the edge rides on (passed by the caller via `via_len`).
    pub fn cost(self, via_len: usize) -> u32 {
        match self {
            EdgeClass::Dev => 0,
            EdgeClass::Optional => 1,
            EdgeClass::Normal => 10 + via_len as u32,
        }
    }
}

/// One directed intra-SCC edge, classified for MFAS: `from` depends on `to`, riding
/// on the `via` crate(s) (what `to` produces that `from` needs), with a cut class.
#[derive(Debug, Clone)]
pub struct ClassifiedEdge {
    pub from: String,
    pub to: String,
    pub via: Vec<String>,
    pub class: EdgeClass,
}

impl ClassifiedEdge {
    fn cost(&self) -> u32 {
        self.class.cost(self.via.len())
    }

    /// The concrete remedy sentence for cutting this edge.
    fn action(&self) -> String {
        match self.class {
            EdgeClass::Dev => format!(
                "cut `{} → {}` — it's a DEV edge (already non-gating); move it out of the order graph",
                self.from, self.to
            ),
            EdgeClass::Optional => format!(
                "gate the feature off so `{}` no longer requires `{}` (optional dep)",
                self.from, self.to
            ),
            EdgeClass::Normal => {
                let via = if self.via.is_empty() {
                    self.to.clone()
                } else {
                    self.via.join(", ")
                };
                format!(
                    "split `{}`: extract `{}` into a leaf crate both can depend on, so `{}` no longer path-depends on `{}`",
                    self.to, via, self.from, self.to
                )
            }
        }
    }
}

/// A ranked MFAS candidate: the set of edges to remove, the total cost, the concrete
/// remedy actions, and the PROOF the residual is a DAG (its topo order over the
/// SCC's nodes — non-empty ⇔ acyclic, which we also `assert` on construction).
#[derive(Debug, Clone)]
pub struct CutSolution {
    /// Edges to remove, as `(from, to)` pairs.
    pub edges: Vec<(String, String)>,
    /// Total cut cost (sum of removed-edge costs). Lower is better.
    pub cost: u32,
    /// One human remedy sentence per removed edge, cheapest-class first.
    pub actions: Vec<String>,
    /// Proof witness: a topological order of the SCC's nodes over the RESIDUAL edge
    /// set. A DAG always has one; its presence certifies acyclicity.
    pub proof_order: Vec<String>,
}

/// Kahn topo-sort of `nodes` under `edges` (edge `A→B` = A depends on B, so B
/// precedes A). Returns `Some(order)` iff the graph is acyclic — the DAG proof.
fn topo_of(nodes: &[String], edges: &[(&str, &str)]) -> Option<Vec<String>> {
    let set: BTreeSet<&str> = nodes.iter().map(|s| s.as_str()).collect();
    let mut indeg: BTreeMap<&str, usize> = nodes.iter().map(|n| (n.as_str(), 0)).collect();
    let mut consumers: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
    for &(from, to) in edges {
        if set.contains(from) && set.contains(to) {
            *indeg.get_mut(from).unwrap() += 1; // from depends on to
            consumers.entry(to).or_default().push(from);
        }
    }
    let mut ready: BTreeSet<&str> =
        indeg.iter().filter(|&(_, &d)| d == 0).map(|(&n, _)| n).collect();
    let mut order = Vec::new();
    while let Some(&n) = ready.iter().next() {
        ready.remove(n);
        order.push(n.to_string());
        if let Some(cs) = consumers.get(n) {
            for &c in cs {
                let d = indeg.get_mut(c).unwrap();
                *d -= 1;
                if *d == 0 {
                    ready.insert(c);
                }
            }
        }
    }
    (order.len() == nodes.len()).then_some(order)
}

/// **Minimum Feedback Arc Set** over one SCC: exhaustively enumerate edge-subsets
/// and return the cuts whose removal makes the SCC acyclic, ranked cheapest-first.
/// Constellation SCCs are tiny (2–5 crates), so the `2^m` enumeration is trivial;
/// for a pathologically large SCC (`m > 20` edges) we fall back to subsets of size
/// ≤ 3 (still finds every small cut). Only MINIMAL cuts are kept (no cut that is a
/// strict superset of another feasible cut). Each solution proves acyclicity by
/// carrying a residual topo order.
///
/// Ranking key: `(total cost, #edges, edge names)` — so a cost-0 DEV cut beats a
/// cost-1 OPTIONAL cut beats a crate-split, and ties are deterministic.
pub fn min_feedback_arc_set(nodes: &[String], edges: &[ClassifiedEdge]) -> Vec<CutSolution> {
    let m = edges.len();
    // The residual edge set for a removal mask, as (from,to) &str pairs.
    let residual = |mask: u64| -> Vec<(&str, &str)> {
        (0..m)
            .filter(|i| mask & (1 << i) == 0)
            .map(|i| (edges[i].from.as_str(), edges[i].to.as_str()))
            .collect()
    };

    // Candidate removal masks: full power set when small, else size-≤3 subsets.
    let masks: Vec<u64> = if m <= 20 {
        (1u64..(1u64 << m)).collect()
    } else {
        let mut v = Vec::new();
        for a in 0..m {
            v.push(1u64 << a);
            for b in (a + 1)..m {
                v.push((1u64 << a) | (1u64 << b));
                for c in (b + 1)..m {
                    v.push((1u64 << a) | (1u64 << b) | (1u64 << c));
                }
            }
        }
        v
    };

    // Feasible cuts: (mask, cost, proof_order).
    let mut feasible: Vec<(u64, u32, Vec<String>)> = Vec::new();
    for mask in masks {
        if let Some(order) = topo_of(nodes, &residual(mask)) {
            let cost: u32 = (0..m)
                .filter(|i| mask & (1 << i) != 0)
                .map(|i| edges[i].cost())
                .sum();
            feasible.push((mask, cost, order));
        }
    }

    // Drop non-minimal cuts: any mask that is a strict SUPERSET of another feasible
    // mask (removing extra edges is never necessary once acyclic).
    let minimal: Vec<(u64, u32, Vec<String>)> = feasible
        .iter()
        .filter(|(mask, _, _)| {
            !feasible
                .iter()
                .any(|(other, _, _)| other != mask && (mask & other) == *other)
        })
        .cloned()
        .collect();

    let mut sols: Vec<CutSolution> = minimal
        .into_iter()
        .map(|(mask, cost, proof_order)| {
            // Removed edges, ordered cheapest-class first for readable actions.
            let mut removed: Vec<&ClassifiedEdge> =
                (0..m).filter(|i| mask & (1 << i) != 0).map(|i| &edges[i]).collect();
            removed.sort_by_key(|e| (e.cost(), e.from.clone(), e.to.clone()));
            debug_assert_eq!(proof_order.len(), nodes.len(), "proof must cover every node");
            CutSolution {
                edges: removed.iter().map(|e| (e.from.clone(), e.to.clone())).collect(),
                cost,
                actions: removed.iter().map(|e| e.action()).collect(),
                proof_order,
            }
        })
        .collect();
    sols.sort_by(|a, b| {
        (a.cost, a.edges.len(), &a.edges).cmp(&(b.cost, b.edges.len(), &b.edges))
    });
    sols
}

// ───────────────────── invertive planner (utfallsrum Ω) ─────────────────────

/// A finding CLASS in the release outcome-space Ω. The doctor's state `s ∈ Ω` is the
/// multiset of open symptoms; the green target is the empty multiset. A remedy
/// operator's precondition is simply "count of its target class > 0" — so dispatch
/// is generic (match preconditions), never a hand-coded `if` per symptom.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum SymptomKind {
    /// Path dep of a MEMBER crate missing `version=` — auto-fixable (`--fix`).
    VersionGap,
    /// Path dep on a NON-member crate — needs a decision (join cascade / publish it).
    NonMemberDep,
    /// External version skew — a repo behind the semver-join target.
    Skew,
    /// Dirty working tree (noise) — auto-tidyable.
    Dirty,
    /// A dependency cycle whose cheapest MFAS cut costs ≤ 1 (dev/optional) — auto.
    CheapCycle,
    /// A dependency cycle whose cheapest cut is a crate-split — needs a decision.
    HardCycle,
    /// A crate held from crates.io by a patch-fork — needs an upstream publish.
    PromoteBlock,
}

/// The open-symptom multiset — a point in Ω. `total()` is the convergence measure
/// each AUTO operator must strictly reduce.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Symptoms {
    counts: BTreeMap<SymptomKind, usize>,
}

impl Symptoms {
    pub fn new() -> Self {
        Self::default()
    }
    /// Set (or clear, with 0) the count of a symptom class.
    pub fn set(&mut self, kind: SymptomKind, n: usize) {
        if n == 0 {
            self.counts.remove(&kind);
        } else {
            self.counts.insert(kind, n);
        }
    }
    pub fn count(&self, kind: SymptomKind) -> usize {
        self.counts.get(&kind).copied().unwrap_or(0)
    }
    /// Total open symptoms across all classes — the multiset cardinality.
    pub fn total(&self) -> usize {
        self.counts.values().sum()
    }
    pub fn is_green(&self) -> bool {
        self.counts.is_empty()
    }
}

/// AUTO (safe to apply) vs DECISION (surface one crisp ask) — the operator's class.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RemedyClass {
    Auto,
    Decision,
}

/// A STRIPS-style remedy operator: `⟨precondition, effect⟩` held as DATA. The
/// precondition is implicit — "target class count > 0"; the effect closes that class
/// (`count ↦ 0`). Adding a remedy = adding a row to [`remedy_table`], never a branch.
#[derive(Debug, Clone)]
pub struct RemedyOp {
    /// Stable id the executor dispatches a real action on (e.g. `"fix-versions"`).
    pub id: &'static str,
    pub class: RemedyClass,
    /// The symptom class this operator closes (its precondition + effect target).
    pub target: SymptomKind,
    /// Human remedy sentence / the flag it corresponds to.
    pub action: &'static str,
}

/// The remedy operator TABLE — the doctor's entire remedy knowledge, as data. The
/// planner dispatches generically over it; the ORDER is the AUTO-application
/// priority (cheapest / most-foundational first). `fix-versions` is the first
/// operator (reusing the built `--fix`).
pub fn remedy_table() -> Vec<RemedyOp> {
    use RemedyClass::*;
    use SymptomKind::*;
    vec![
        RemedyOp {
            id: "fix-versions",
            class: Auto,
            target: VersionGap,
            action: "run --fix: fill `version = \"…\"` on every member path dep",
        },
        RemedyOp {
            id: "tidy-dirty",
            class: Auto,
            target: Dirty,
            action: "--tidy: drop working-tree noise (.claude/, *.arrows) and commit",
        },
        RemedyOp {
            id: "bump-skew-join",
            class: Auto,
            target: Skew,
            action: "bump each behind repo to the semver-join (⊔) target",
        },
        RemedyOp {
            id: "cut-cycle-cheap",
            class: Auto,
            target: CheapCycle,
            action: "MFAS: cut the cost-≤1 edge (drop a dev edge / gate a feature off)",
        },
        RemedyOp {
            id: "add-member",
            class: Decision,
            target: NonMemberDep,
            action: "DECIDE: add the non-member dep to the release cascade, or publish it first",
        },
        RemedyOp {
            id: "split-crate",
            class: Decision,
            target: HardCycle,
            action: "DECIDE: split a crate (extract a leaf) to break the cycle — MFAS crate-split",
        },
        RemedyOp {
            id: "unfork",
            class: Decision,
            target: PromoteBlock,
            action: "DECIDE: publish the forked dep's real version upstream, or wait for it",
        },
    ]
}

/// One applied (or proposed) remedy in the plan trace.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PlanStep {
    pub op_id: &'static str,
    pub class: RemedyClass,
    pub action: &'static str,
    pub closes: SymptomKind,
    /// How many findings of that class the step closes.
    pub count: usize,
}

/// The invertive remedy PLAN: the ordered AUTO steps applied to a fixpoint, then the
/// minimal set of DECISION asks that remain (surfaced one at a time). `green` ⇔ the
/// autos reach the empty multiset with no decisions left — a self-healed release.
#[derive(Debug, Clone)]
pub struct RemedyPlan {
    /// AUTO steps, in application order — each strictly reduces the open multiset.
    pub steps: Vec<PlanStep>,
    /// DECISION asks that block a full auto-heal, cheapest/most-actionable first.
    pub decisions: Vec<PlanStep>,
    /// True iff the AUTO closure reaches green with zero decisions.
    pub green: bool,
}

/// THE PLANNER — closure of the remedy operators over Ω. Starting from `initial`,
/// repeatedly match an AUTO operator's precondition (its target class is open) and
/// apply its effect (close that class), recording the step; loop to a FIXPOINT (no
/// AUTO operator applies). Then collect the DECISION operators still triggered as the
/// minimal ask set. Model-based / declarative: no `if` per symptom, only table
/// matching.
///
/// **Convergence** is guaranteed: every AUTO application strictly reduces
/// `state.total()` (it closes a non-empty class and no operator re-opens a closed
/// one), so the loop runs at most `initial.total()` times — asserted below.
pub fn plan(initial: &Symptoms, table: &[RemedyOp]) -> RemedyPlan {
    let mut state = initial.clone();
    let mut steps = Vec::new();
    let budget = initial.total() + 1; // strict-decrease ⇒ ≤ total iterations
    let mut guard = 0;
    loop {
        guard += 1;
        assert!(guard <= budget + 1, "planner must converge (strict-decrease invariant)");
        // Precondition matching: first AUTO op (table order = priority) whose target
        // class is open. This is the generic dispatch — the anti-if/else.
        let Some(op) = table
            .iter()
            .find(|o| o.class == RemedyClass::Auto && state.count(o.target) > 0)
        else {
            break;
        };
        let before = state.total();
        let closed = state.count(op.target);
        state.set(op.target, 0); // effect
        debug_assert!(state.total() < before, "AUTO op must strictly reduce the multiset");
        steps.push(PlanStep {
            op_id: op.id,
            class: RemedyClass::Auto,
            action: op.action,
            closes: op.target,
            count: closed,
        });
    }
    // Remaining open classes are exactly the DECISION-targeted ones (any class with
    // no operator would also remain — surfaced too, so nothing is silently dropped).
    let decisions: Vec<PlanStep> = table
        .iter()
        .filter(|o| o.class == RemedyClass::Decision && state.count(o.target) > 0)
        .map(|o| PlanStep {
            op_id: o.id,
            class: RemedyClass::Decision,
            action: o.action,
            closes: o.target,
            count: state.count(o.target),
        })
        .collect();
    let green = state.is_green();
    RemedyPlan { steps, decisions, green }
}

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

    fn adj(pairs: &[(&str, &[&str])]) -> Adj {
        pairs
            .iter()
            .map(|(n, ds)| (n.to_string(), ds.iter().map(|s| s.to_string()).collect()))
            .collect()
    }

    fn edge(from: &str, to: &str, class: EdgeClass) -> ClassifiedEdge {
        ClassifiedEdge { from: from.to_string(), to: to.to_string(), via: vec![to.to_string()], class }
    }

    /// Tarjan on a known graph: one 3-node cycle (a→b→c→a) + a clean tail (c→d).
    #[test]
    fn tarjan_finds_the_scc() {
        let g = adj(&[("a", &["b"]), ("b", &["c"]), ("c", &["a", "d"]), ("d", &[])]);
        let cs = cycles(&g);
        assert_eq!(cs.len(), 1, "exactly one cycle");
        assert_eq!(cs[0], vec!["a", "b", "c"], "the SCC = the 3-node loop, sorted");
        // Two SCCs total: the {a,b,c} loop and the singleton {d}.
        assert_eq!(tarjan_scc(&g).len(), 2, "{{a,b,c}} + {{d}}");

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "tarjan_scc",
            cs.len() == 1 && cs[0] == vec!["a", "b", "c"],
            "3-node cycle a→b→c→a isolated from tail d",
        );
    }

    #[test]
    fn dag_has_no_cycle_and_topo_orders() {
        let g = adj(&[("app", &["lib"]), ("lib", &["core"]), ("core", &[])]);
        assert!(cycles(&g).is_empty(), "a DAG has no cycle");
        let cond = condense(&g);
        // 3 singleton comps; coarse order is deps-first: core, lib, app.
        let order: Vec<String> = cond
            .topo_order()
            .iter()
            .map(|&c| cond.comps[c].join("+"))
            .collect();
        assert_eq!(order, vec!["core", "lib", "app"]);

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "condensation_topo",
            order == vec!["core", "lib", "app"],
            "deps-first coarse order over a DAG",
        );
    }

    /// Publish waves = antichains: independent leaves publish together.
    #[test]
    fn waves_are_antichains() {
        // core is a shared leaf; a and b both depend on core; app depends on a+b.
        let g = adj(&[
            ("core", &[]),
            ("a", &["core"]),
            ("b", &["core"]),
            ("app", &["a", "b"]),
        ]);
        let waves = condense(&g).waves();
        assert_eq!(waves.len(), 3, "three waves");
        assert_eq!(waves[0], vec!["core"], "wave 0 = the shared leaf");
        assert_eq!(waves[1], vec!["a", "b"], "wave 1 = the two independents, concurrent");
        assert_eq!(waves[2], vec!["app"], "wave 2 = the sink");

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "publish_waves",
            waves.len() == 3 && waves[1] == vec!["a", "b"],
            "antichain wave 1 = {a,b} publishable concurrently",
        );
    }

    /// MFAS ranking: a 2-node cycle where one edge is OPTIONAL (cost 1) and the other
    /// NORMAL (crate-split, cost ≥10) → the cheapest cut is the optional edge.
    #[test]
    fn mfas_ranks_cheapest_cut_first() {
        let nodes = vec!["a".to_string(), "b".to_string()];
        let edges = vec![
            edge("a", "b", EdgeClass::Normal),   // a→b: costly split
            edge("b", "a", EdgeClass::Optional), // b→a: cheap gate-off
        ];
        let sols = min_feedback_arc_set(&nodes, &edges);
        assert!(!sols.is_empty(), "the cycle is breakable");
        let best = &sols[0];
        assert_eq!(best.edges, vec![("b".to_string(), "a".to_string())], "cut the optional edge");
        assert_eq!(best.cost, 1, "gate-off costs 1");
        assert_eq!(best.proof_order.len(), 2, "residual is a DAG (proof covers both nodes)");
        // Every solution's proof must actually be acyclic.
        for s in &sols {
            assert_eq!(s.proof_order.len(), nodes.len(), "each cut proves a DAG");
        }
        // Cheapest first.
        assert!(sols.windows(2).all(|w| w[0].cost <= w[1].cost), "ranked by cost");

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "mfas_ranking",
            best.cost == 1 && best.edges == vec![("b".to_string(), "a".to_string())],
            "optional-edge cut (cost 1) ranked above crate-split (cost ≥10)",
        );
    }

    /// A DEV edge is a cost-0 cut and wins outright.
    #[test]
    fn mfas_prefers_free_dev_cut() {
        let nodes = vec!["x".to_string(), "y".to_string()];
        let edges = vec![
            edge("x", "y", EdgeClass::Dev),    // free
            edge("y", "x", EdgeClass::Normal), // split
        ];
        let sols = min_feedback_arc_set(&nodes, &edges);
        assert_eq!(sols[0].cost, 0, "the dev cut is free");
        assert_eq!(sols[0].edges, vec![("x".to_string(), "y".to_string())]);
    }

    /// Invertive planner: version gaps + skew are AUTO → applied to a fixpoint; a
    /// non-member dep + a hard cycle remain as DECISION asks. Convergence: the auto
    /// steps strictly reduce the multiset to just the decisions.
    #[test]
    fn planner_converges_autos_then_asks() {
        let mut s = Symptoms::new();
        s.set(SymptomKind::VersionGap, 37);
        s.set(SymptomKind::Skew, 2);
        s.set(SymptomKind::NonMemberDep, 4);
        s.set(SymptomKind::HardCycle, 1);
        let plan = plan(&s, &remedy_table());

        // AUTO closure handled the version gaps + skew.
        let auto_ids: Vec<&str> = plan.steps.iter().map(|p| p.op_id).collect();
        assert!(auto_ids.contains(&"fix-versions"), "version gaps auto-fixed first");
        assert!(auto_ids.contains(&"bump-skew-join"), "skew auto-bumped");
        assert_eq!(plan.steps.len(), 2, "exactly the two applicable AUTO ops");
        // The FIRST operator is the reused --fix.
        assert_eq!(plan.steps[0].op_id, "fix-versions", "--fix is the first operator");

        // DECISION asks remain, minimal set.
        let dec_ids: Vec<&str> = plan.decisions.iter().map(|p| p.op_id).collect();
        assert_eq!(dec_ids, vec!["add-member", "split-crate"], "two crisp asks, ordered");
        assert!(!plan.green, "not green: decisions block the auto-heal");

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "planner_fixpoint",
            plan.steps.len() == 2 && plan.decisions.len() == 2 && !plan.green,
            "37 version-gaps + 2 skew auto-closed; non-member + hard-cycle → 2 asks",
        );
    }

    /// A clean state plans to GREEN with no steps and no asks (fixpoint = green).
    #[test]
    fn planner_green_on_clean_state() {
        let plan = plan(&Symptoms::new(), &remedy_table());
        assert!(plan.steps.is_empty() && plan.decisions.is_empty() && plan.green);
    }

    /// A cheap cycle is an AUTO remedy; feeding only a CheapCycle drives the
    /// cut-cycle-cheap operator to a green fixpoint.
    #[test]
    fn planner_auto_cuts_cheap_cycle() {
        let mut s = Symptoms::new();
        s.set(SymptomKind::CheapCycle, 1);
        let plan = plan(&s, &remedy_table());
        assert_eq!(plan.steps.len(), 1);
        assert_eq!(plan.steps[0].op_id, "cut-cycle-cheap");
        assert!(plan.green, "the cheap cut heals it fully");
    }

    // ═══════════════════ additional edge-case coverage ═══════════════════
    // Hand-verifiable small graphs: disconnected components, self-loops, larger
    // SCCs, MFAS minimality, and the condensation-is-a-DAG invariant.

    /// Given `nodes` and the FULL edge list (`A→B` = "A depends on B"), verify that
    /// `order` is a genuine topological order of the graph with `removed` edges cut:
    /// it's a permutation of the nodes and every surviving dependency precedes its
    /// dependent (pos(B) < pos(A) for a kept edge A→B). This is an INDEPENDENT
    /// re-check of a [`CutSolution::proof_order`] — the residual really is acyclic.
    fn is_valid_topo(
        nodes: &[&str],
        all_edges: &[(&str, &str)],
        removed: &[(String, String)],
        order: &[String],
    ) -> bool {
        // permutation check
        let want: BTreeSet<&str> = nodes.iter().copied().collect();
        let got: BTreeSet<&str> = order.iter().map(|s| s.as_str()).collect();
        if want != got || order.len() != nodes.len() {
            return false;
        }
        let pos = |n: &str| order.iter().position(|x| x == n).unwrap();
        let cut: BTreeSet<(String, String)> = removed.iter().cloned().collect();
        all_edges.iter().all(|&(from, to)| {
            if cut.contains(&(from.to_string(), to.to_string())) {
                return true; // this edge was removed
            }
            // A→B means B must publish first ⇒ B precedes A in the order.
            pos(to) < pos(from)
        })
    }

    /// Two disjoint 2-cycles plus an isolated node: `cycles()` finds BOTH cycles
    /// (order-independent), the lone node is not a cycle, and the condensation is
    /// acyclic with every node collapsed into a single wave (nothing gates anything).
    #[test]
    fn disconnected_two_cycles_and_isolated_node() {
        let g = adj(&[
            ("a", &["b"]), ("b", &["a"]), // cycle {a,b}
            ("c", &["d"]), ("d", &["c"]), // cycle {c,d}
            ("e", &[]),                    // isolated leaf
        ]);
        let cs = cycles(&g);
        assert_eq!(cs.len(), 2, "two independent cycles");
        assert!(cs.contains(&vec!["a".to_string(), "b".to_string()]));
        assert!(cs.contains(&vec!["c".to_string(), "d".to_string()]));
        assert!(!cs.iter().any(|c| c.contains(&"e".to_string())), "e is no cycle");

        let cond = condense(&g);
        // 3 components: {a,b}, {c,d}, {e}. None depends on another ⇒ acyclic ⇒
        // topo covers all, and every node sits in ONE wave.
        assert_eq!(cond.comps.len(), 3);
        assert_eq!(cond.topo_order().len(), 3, "condensation is a DAG (all ordered)");
        let waves = cond.waves();
        assert_eq!(waves.len(), 1, "no cross-component edges ⇒ a single wave");
        assert_eq!(waves[0], vec!["a", "b", "c", "d", "e"], "all publishable together");
        // must_break = the two multi-node SCCs.
        assert_eq!(cond.must_break().len(), 2);

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "disconnected_components",
            cs.len() == 2 && waves.len() == 1,
            "two disjoint 2-cycles + isolated node isolated correctly",
        );
    }

    /// A self-loop `n→n` is the degenerate one-node cycle: `is_self_loop` detects it,
    /// `cycles()` reports the singleton, and a plain singleton (`m`, no self-edge) is
    /// NOT a cycle even though it is its own SCC.
    #[test]
    fn self_loop_is_a_one_node_cycle() {
        let g = adj(&[("n", &["n"]), ("m", &["n"])]);
        assert!(is_self_loop(&g, &["n".to_string()]), "n→n is a self-loop");
        assert!(!is_self_loop(&g, &["m".to_string()]), "m has no self-edge");
        let cs = cycles(&g);
        assert_eq!(cs, vec![vec!["n".to_string()]], "only the self-loop is a cycle");
        // Tarjan still finds two SCCs total ({n} and {m}).
        assert_eq!(tarjan_scc(&g).len(), 2);

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "self_loop_cycle",
            cs == vec![vec!["n".to_string()]],
            "self-loop n→n flagged as a size-1 cycle; clean singleton m is not",
        );
    }

    /// Condensation of a 3-cycle with a tail: the loop collapses to ONE super-node,
    /// the tail stays singletons, `comp_of` groups the loop together, and the coarse
    /// order is strictly dependencies-first over the acyclic condensation.
    #[test]
    fn condensation_groups_scc_and_stays_acyclic() {
        // a→b→c→a is the loop; c→d, d→e is a clean tail hanging off it.
        let g = adj(&[
            ("a", &["b"]), ("b", &["c"]), ("c", &["a", "d"]),
            ("d", &["e"]), ("e", &[]),
        ]);
        let cond = condense(&g);
        // The loop's three nodes share ONE component; d, e are their own.
        let ca = cond.comp_of["a"];
        assert_eq!(cond.comp_of["b"], ca);
        assert_eq!(cond.comp_of["c"], ca);
        assert_ne!(cond.comp_of["d"], ca);
        assert_ne!(cond.comp_of["e"], cond.comp_of["d"]);
        // Exactly one must-break SCC = the loop, sorted.
        assert_eq!(cond.must_break(), vec![["a".to_string(), "b".to_string(), "c".to_string()].as_slice()]);
        // Acyclic ⇒ topo covers every component; deps-first ⇒ e, then d, then loop.
        let order: Vec<String> =
            cond.topo_order().iter().map(|&c| cond.comps[c].join("+")).collect();
        assert_eq!(order, vec!["e", "d", "a+b+c"], "tail leaf first, cycle super-node last");
        // No component depends on itself (the DAG invariant).
        assert!(cond.dag.iter().enumerate().all(|(i, deps)| !deps.contains(&i)));

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "condensation_acyclic",
            order == vec!["e", "d", "a+b+c"],
            "3-cycle collapsed to one super-node; condensation topo-sorts deps-first",
        );
    }

    /// MFAS on a 3-node cycle where every edge is a costly `Normal`: exactly the three
    /// single-edge cuts are minimal (any 2-edge cut is a strict superset and dropped),
    /// each costs the same, and each proof order is an INDEPENDENTLY-verified DAG.
    #[test]
    fn mfas_three_cycle_yields_three_minimal_single_cuts() {
        let nodes = vec!["a".to_string(), "b".to_string(), "c".to_string()];
        let all: [(&str, &str); 3] = [("a", "b"), ("b", "c"), ("c", "a")];
        let edges = vec![
            edge("a", "b", EdgeClass::Normal),
            edge("b", "c", EdgeClass::Normal),
            edge("c", "a", EdgeClass::Normal),
        ];
        let sols = min_feedback_arc_set(&nodes, &edges);
        assert_eq!(sols.len(), 3, "three minimal single-edge cuts, no supersets");
        for s in &sols {
            assert_eq!(s.edges.len(), 1, "each minimal cut removes exactly one edge");
            assert_eq!(s.cost, 11, "Normal cut = 10 + via_len(1)");
            // The carried proof really is a topological order of the residual.
            assert!(
                is_valid_topo(&["a", "b", "c"], &all, &s.edges, &s.proof_order),
                "proof_order must be a valid residual DAG order: {:?}",
                s.proof_order
            );
        }
        // The three cuts are exactly the three distinct edges.
        let mut cut_edges: Vec<(String, String)> =
            sols.iter().map(|s| s.edges[0].clone()).collect();
        cut_edges.sort();
        assert_eq!(
            cut_edges,
            vec![
                ("a".to_string(), "b".to_string()),
                ("b".to_string(), "c".to_string()),
                ("c".to_string(), "a".to_string()),
            ]
        );

        nornir_testmatrix::functional_status(
            "release-graph-math",
            "mfas_three_cycle_minimal",
            sols.len() == 3 && sols.iter().all(|s| s.edges.len() == 1),
            "3-cycle: 3 minimal single-edge cuts, each a proven residual DAG",
        );
    }

    /// MFAS minimality: a feasible cut is dropped when it is a strict SUPERSET of
    /// another feasible cut. On a 2-cycle both single-edge cuts work, so the
    /// remove-both cut (also feasible) must NOT be returned.
    #[test]
    fn mfas_drops_non_minimal_superset_cuts() {
        let nodes = vec!["a".to_string(), "b".to_string()];
        let edges = vec![
            edge("a", "b", EdgeClass::Normal),
            edge("b", "a", EdgeClass::Optional),
        ];
        let sols = min_feedback_arc_set(&nodes, &edges);
        assert_eq!(sols.len(), 2, "both single-edge cuts; the 2-edge superset is dropped");
        assert!(sols.iter().all(|s| s.edges.len() == 1), "no non-minimal (2-edge) cut kept");
        // Cheapest (optional, cost 1) first.
        assert_eq!(sols[0].cost, 1);
        assert_eq!(sols[0].edges, vec![("b".to_string(), "a".to_string())]);
    }

    /// The `EdgeClass` cut-cost schedule: Dev is free, Optional flat 1, and a Normal
    /// crate-split rises with the number of crates the edge rides on.
    #[test]
    fn edge_class_cost_schedule() {
        assert_eq!(EdgeClass::Dev.cost(5), 0, "a dev cut is always free");
        assert_eq!(EdgeClass::Optional.cost(3), 1, "an optional gate-off is flat 1");
        assert_eq!(EdgeClass::Normal.cost(0), 10, "base crate-split cost");
        assert_eq!(EdgeClass::Normal.cost(2), 12, "cost grows with via_len");
        // So a Normal cut is always dearer than an Optional, which beats Dev.
        assert!(EdgeClass::Dev.cost(9) < EdgeClass::Optional.cost(9));
        assert!(EdgeClass::Optional.cost(9) < EdgeClass::Normal.cost(0));
    }

    /// The planner surfaces a DECISION-only symptom with no AUTO reduction: a
    /// promote-block yields zero auto steps and one crisp `unfork` ask, not green.
    #[test]
    fn planner_surfaces_decision_only_symptom() {
        let mut s = Symptoms::new();
        s.set(SymptomKind::PromoteBlock, 3);
        let plan = plan(&s, &remedy_table());
        assert!(plan.steps.is_empty(), "nothing auto-heals a promote block");
        assert_eq!(plan.decisions.len(), 1);
        assert_eq!(plan.decisions[0].op_id, "unfork");
        assert_eq!(plan.decisions[0].count, 3, "the ask carries the finding count");
        assert!(!plan.green);
    }

    /// Multiple distinct AUTO symptoms all close to a green fixpoint, and `Symptoms`
    /// bookkeeping (`set(_, 0)` clears, `total`, `is_green`) is exact.
    #[test]
    fn planner_multiple_autos_reach_green() {
        let mut s = Symptoms::new();
        s.set(SymptomKind::Dirty, 1);
        s.set(SymptomKind::CheapCycle, 2);
        assert_eq!(s.total(), 3);
        s.set(SymptomKind::Dirty, 0); // clearing removes the class entirely
        assert_eq!(s.total(), 2);
        assert_eq!(s.count(SymptomKind::Dirty), 0);
        s.set(SymptomKind::Dirty, 1); // put it back
        let plan = plan(&s, &remedy_table());
        let ids: BTreeSet<&str> = plan.steps.iter().map(|p| p.op_id).collect();
        assert!(ids.contains("tidy-dirty") && ids.contains("cut-cycle-cheap"));
        assert_eq!(plan.steps.len(), 2);
        assert!(plan.green && plan.decisions.is_empty(), "all AUTO ⇒ self-healed green");
    }
}