nordisk/dwarves

Release doctor — graph-math core (SCC · MFAS · waves · invertive --auto)

The release doctor's problem-solving is grounded in graph theory + planning, not ad-hoc if/else. This is the "less if-else, more utfallsrum + graph methods" engine (workspace_nordisk PLAN EPIC 1–3, 9–10). Lives in src/release/graph_math.rs, wired into src/release/doctor.rs and src/bin/nornir.rs.

Design

Model the constellation as a directed graph G = (V, E): V = crates, E = publish-gating edges (A → B ⇔ A has an in-workspace Normal/Build path dep on B ⇒ B must publish first). Dev-deps, pure version-pins and publish = false crates are excluded from E.

• Topological order = publish order. A linear publish order exists iff G is a DAG. Kahn/topo over the condensation gives it (deps-first).
• Cycle detection = Tarjan SCC (tarjan_scc, O(V+E)). Every strongly connected component with >1 node (or a self-loop) is exactly a dependency cycle — the crates that provably cannot be linearly ordered. cycles() filters SCCs to those must-break sets.
• Condensation (condense → Condensation): collapse each SCC to a super-node ⇒ G/SCC is always a DAG. topo_order() gives the coarse order, must_break() the SCC internals, waves() the antichains — each wave is a set of crates publishable concurrently.
• Cycle solutions = Minimum Feedback Arc Set (min_feedback_arc_set). To break a cycle: the minimum set of edges whose removal makes G acyclic. NP-hard in general, but constellation SCCs are tiny (2–5 crates), so we exhaustively enumerate edge subsets per SCC and rank by cut cost (EdgeClass): a DEV edge = 0 (already non-gating), an OPTIONAL/feature-gated edge = 1 (gate it off), a Normal edge / crate-split = 10+ (extract a leaf — the pattern that birthed znippy-zoomies and Skidbladnir). Each CutSolution carries a residual topo order that proves the cut yields a DAG.
• Invertive --auto = a planner over the outcome space Ω, not a branch tree. Each remedy is a STRIPS-style operator ⟨precondition, effect⟩ held in a data table (remedy_table). The engine projects the DoctorReport into a symptom multiset (Symptoms), matches preconditions generically, applies AUTO operators to a fixpoint (each strictly reduces the open symptom multiset ⇒ convergence is guaranteed and asserted), and surfaces the irreducible DECISION operators as a minimal, crisp ask set. Adding a remedy = adding a row to the table, never a new if arm.

Guide

# See cycles as ranked, proven solutions + the parallel publish waves:
nornir release doctor            # report now includes "Publish waves" and
                                 # "MFAS — ranked cycle solutions" sections

# Invertive self-heal: assess → apply AUTO remedies → re-assess → fixpoint,
# else stop at the minimal set of human decisions.
nornir release doctor --auto

# Dry invertive: print the ordered remedy PLAN (operator sequence), apply
# nothing — the "what would you do" inverse trace.
nornir release doctor --auto --dry

--auto reuses the existing --fix (path-dep version= gaps) as its first operator; skew → bump-to-semilattice-join is next; a DEV/OPTIONAL cycle cut is AUTO (cost 0/1), a crate-split is a DECISION.

Idiot guide

• "Can I publish in one line?" → nornir release doctor --auto tries to fix everything it safely can, then tells you the few things only you can decide.
• "It says there's a cycle." → look at the "ranked cycle solutions" — the top one is the cheapest fix (usually "turn feature X off"), and it's proven to leave a publishable graph. Do that one.
• "Publish waves?" → crates in the same wave can go up at the same time; waves go in order. It's just the dependency levels.