crates/nornir-release/src/waves.rs
//! Pure **publish-wave** computation — the deps-first, parallel-publish order of a
//! cargo workspace, computed with **zero I/O** and no warehouse.
//!
//! A cascade release publishes crates to a registry, and a crate can only publish
//! once every crate it depends on is already on the registry. So the publish order
//! is a topological sort of the workspace's intra-workspace dependency graph — but
//! crates with *no remaining* unpublished dependency are mutually independent and
//! may publish **in parallel**. Grouping the topo sort into those parallel batches
//! gives the *waves*: `phases[0]` publishes first (all leaf crates), then
//! `phases[1]`, and so on. Every crate in `phases[i]` has all of its
//! publish-gating deps in some earlier phase.
//!
//! ## What gates publishing
//! Only `Normal` and `Build` dependencies gate publishing — a build-dependency
//! must be on the registry before its dependent builds. A **`Development`**
//! dependency does **not**: cargo strips dev-deps from the packaged crate at
//! publish time, so counting one would (a) invent a false cycle when two crates
//! dev-depend on each other's normal deps, and (b) needlessly delay a crate behind
//! a dependency the published artifact never references. [`DepKind::gates_publish`]
//! encodes exactly this rule.
//!
//! ## Why this lives in the leaf
//! This is the *logic* half of the release engine (per the nordisk leaf/conductor
//! split): pure graph math a third consumer wants as-is. The *orchestration* — the
//! `cargo metadata` read, registry state, the actual `cargo publish` walk — stays
//! in the conductor (nornir), which maps its `cargo_metadata::DependencyKind` onto
//! [`DepKind`] and feeds [`WorkspaceCrate`]s in. dwarves drives the same primitive
//! over gRPC. No `cargo_metadata` dependency is pulled into the leaf.
//!
//! ```
//! use nornir_release::waves::{DepKind, WorkspaceCrate, plan_waves};
//!
//! // `app` depends on `core`; `util` is independent.
//! let crates = vec![
//! WorkspaceCrate::new("app").dep("core", DepKind::Normal),
//! WorkspaceCrate::new("core"),
//! WorkspaceCrate::new("util"),
//! ];
//! let plan = plan_waves(&crates);
//! assert_eq!(plan.phases, vec![
//! vec!["core".to_string(), "util".to_string()], // publish first, in parallel
//! vec!["app".to_string()], // then the dependent
//! ]);
//! assert!(!plan.has_cycle());
//! ```
use std::collections::{BTreeMap, BTreeSet};
/// The cargo dependency kind of one edge, insofar as it matters to publishing.
///
/// Publishing is gated by [`Normal`](DepKind::Normal) and [`Build`](DepKind::Build)
/// deps — both must be on the registry before the dependent — but **not** by
/// [`Development`](DepKind::Development): cargo strips dev-deps at publish time, so
/// counting one would invent false cycles and mis-order the cascade.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum DepKind {
/// A regular `[dependencies]` edge — gates publishing.
Normal,
/// A `[build-dependencies]` edge — gates publishing (must ship first).
Build,
/// A `[dev-dependencies]` edge — does **not** gate publishing (stripped at
/// publish time).
Development,
}
impl DepKind {
/// Does a dependency of this kind have to be published *before* its dependent?
/// `true` for `Normal`/`Build`, `false` for `Development`.
#[inline]
pub fn gates_publish(self) -> bool {
!matches!(self, DepKind::Development)
}
}
/// One workspace member as the wave planner sees it: its name, whether it is
/// publishable (`publish = false` in its manifest ⇒ `false`), and its declared
/// dependencies with their kinds.
///
/// Dependencies naming a crate that is **not** a workspace member (an external
/// crates.io dep), or naming the crate itself, are ignored by the planner —
/// only intra-workspace, publish-gating edges shape the waves.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WorkspaceCrate {
/// The crate's package name.
pub name: String,
/// `false` when the manifest sets `publish = false` — the crate is dropped
/// from the plan (nothing waits on it, it publishes nowhere).
pub publishable: bool,
/// Declared dependencies, `(dep-name, kind)`. May include external and dev
/// deps; the planner filters them.
pub deps: Vec<(String, DepKind)>,
}
impl WorkspaceCrate {
/// A publishable member with no dependencies. Chain [`dep`](Self::dep) /
/// [`unpublishable`](Self::unpublishable) to build it up.
pub fn new(name: impl Into<String>) -> Self {
Self { name: name.into(), publishable: true, deps: Vec::new() }
}
/// Mark this member `publish = false` — it is dropped from the plan.
pub fn unpublishable(mut self) -> Self {
self.publishable = false;
self
}
/// Add one declared dependency edge (builder style).
pub fn dep(mut self, name: impl Into<String>, kind: DepKind) -> Self {
self.deps.push((name.into(), kind));
self
}
}
/// The deps-first parallel publish plan.
///
/// `phases` is an ordered list of publish waves: every crate in `phases[i]` has all
/// of its publish-gating workspace dependencies in phases `< i`, so a whole phase
/// may be published in parallel. Within a phase, names are alphabetical
/// (deterministic). `cyclic` holds any crates trapped in a dependency cycle — this
/// should never happen for a real publishable workspace, so it is surfaced
/// explicitly (via [`has_cycle`](Self::has_cycle)) rather than silently dropped or
/// mixed into the phases.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct PublishWaves {
/// The parallel publish waves, deps-first.
pub phases: Vec<Vec<String>>,
/// Crates left unresolved by a dependency cycle (empty for a clean DAG).
pub cyclic: Vec<String>,
}
impl PublishWaves {
/// The flattened deps-first publish order (phase order, then alphabetical
/// within each phase). Cyclic crates are **not** included.
pub fn flat(&self) -> Vec<String> {
self.phases.iter().flatten().cloned().collect()
}
/// Total number of crates across all phases (excludes cyclic).
pub fn len(&self) -> usize {
self.phases.iter().map(|p| p.len()).sum()
}
/// `true` when there are no phases at all (nothing publishable).
pub fn is_empty(&self) -> bool {
self.phases.is_empty()
}
/// Was any crate trapped in a dependency cycle?
pub fn has_cycle(&self) -> bool {
!self.cyclic.is_empty()
}
/// The 0-based wave a crate publishes in, or `None` if it is not in the plan
/// (unpublishable, external, or cyclic).
pub fn phase_of(&self, krate: &str) -> Option<usize> {
self.phases.iter().position(|p| p.iter().any(|c| c == krate))
}
}
/// Plan the publish waves for a set of workspace members — the ergonomic entry
/// point. Drops `publish = false` members, keeps only intra-workspace
/// publish-gating edges, and layers the resulting DAG into deps-first parallel
/// waves. See [`PublishWaves`].
pub fn plan_waves(crates: &[WorkspaceCrate]) -> PublishWaves {
// The workspace name set is every member — publishable or not — so a dep on
// an unpublishable workspace crate is recognised as intra-workspace (and then
// dropped for not surviving into the node set), while a dep on a crate not in
// the workspace at all is an external dep and ignored.
let ws: BTreeSet<String> = crates.iter().map(|c| c.name.clone()).collect();
let members = publish_edges(crates, &ws);
let (phases, cyclic) = layer(members);
PublishWaves { phases, cyclic }
}
/// Build the pure publish graph: drop unpublishable members, and for each survivor
/// keep only its intra-workspace, publish-gating deps (`Normal`/`Build`, never
/// `Development`; external deps dropped). Returns `(name, gating-deps)` pairs — the
/// exact shape [`topo_phases`] consumes. Exposed so a caller with its own metadata
/// source can reuse the filtering without the ergonomic [`WorkspaceCrate`] type.
pub fn publish_edges(
crates: &[WorkspaceCrate],
ws: &BTreeSet<String>,
) -> Vec<(String, Vec<String>)> {
let mut members: Vec<(String, Vec<String>)> = Vec::new();
for c in crates {
if !c.publishable {
continue;
}
let deps: Vec<String> = c
.deps
.iter()
.filter(|(_, kind)| kind.gates_publish())
.map(|(n, _)| n.clone())
.filter(|n| ws.contains(n))
.collect();
members.push((c.name.clone(), deps));
}
members
}
/// Pure, deterministic Kahn topological sort into deps-first phases (waves).
///
/// Each `(name, deps)` lists the crate's intra-workspace dependencies. A crate is
/// "ready" when none of its remaining workspace deps are unresolved; all ready
/// crates form one phase (alphabetical). Deps naming a crate outside `members`, or
/// naming the crate itself, are ignored. **Cycle handling:** if a round makes no
/// progress, the unresolved remainder is appended as a final phase so nothing is
/// silently dropped — a drop-in match for nornir's historic `topo_phases`. Prefer
/// [`plan_waves`] when you want the cycle remainder reported separately rather than
/// tacked onto the phase list.
pub fn topo_phases(members: Vec<(String, Vec<String>)>) -> Vec<Vec<String>> {
let (mut phases, cyclic) = layer(members);
if !cyclic.is_empty() {
phases.push(cyclic); // cycle guard — drop nothing
}
phases
}
/// The shared Kahn core: returns `(clean deps-first phases, cyclic remainder)`.
/// A clean DAG yields an empty remainder; a cycle yields the still-unresolved
/// names (alphabetical) so callers can present them however they wish.
fn layer(members: Vec<(String, Vec<String>)>) -> (Vec<Vec<String>>, Vec<String>) {
let names: BTreeSet<String> = members.iter().map(|(n, _)| n.clone()).collect();
let mut indeg: BTreeMap<String, usize> = BTreeMap::new();
let mut dependents: BTreeMap<String, Vec<String>> = BTreeMap::new(); // dep → dependents
for (n, deps) in &members {
let real: Vec<&String> =
deps.iter().filter(|d| names.contains(*d) && d.as_str() != n).collect();
indeg.insert(n.clone(), real.len());
for d in real {
dependents.entry(d.clone()).or_default().push(n.clone());
}
}
let mut phases: Vec<Vec<String>> = Vec::new();
let mut remaining: BTreeSet<String> = names;
while !remaining.is_empty() {
let ready: Vec<String> = remaining
.iter()
.filter(|n| indeg.get(*n).copied().unwrap_or(0) == 0)
.cloned()
.collect();
if ready.is_empty() {
// No progress ⇒ everything left is in (or blocked by) a cycle.
return (phases, remaining.into_iter().collect());
}
for n in &ready {
remaining.remove(n);
if let Some(deps) = dependents.get(n) {
for dep in deps {
if let Some(e) = indeg.get_mut(dep) {
*e = e.saturating_sub(1);
}
}
}
}
phases.push(ready); // already alphabetical (BTreeSet iteration order)
}
(phases, Vec::new())
}
#[cfg(test)]
mod tests {
use super::*;
fn n(s: &str) -> String {
s.to_string()
}
#[test]
fn dep_kind_gating() {
assert!(DepKind::Normal.gates_publish());
assert!(DepKind::Build.gates_publish());
assert!(!DepKind::Development.gates_publish());
}
#[test]
fn dependency_publishes_before_dependent() {
// app → core (Normal): core must be in an earlier wave than app.
let plan = plan_waves(&[
WorkspaceCrate::new("app").dep("core", DepKind::Normal),
WorkspaceCrate::new("core"),
]);
assert_eq!(plan.phases, vec![vec![n("core")], vec![n("app")]]);
assert!(plan.phase_of("core").unwrap() < plan.phase_of("app").unwrap());
assert!(!plan.has_cycle());
assert_eq!(plan.flat(), vec![n("core"), n("app")]);
assert_eq!(plan.len(), 2);
}
#[test]
fn independent_crates_share_one_wave_alphabetically() {
let plan = plan_waves(&[
WorkspaceCrate::new("zeta"),
WorkspaceCrate::new("alpha"),
WorkspaceCrate::new("mid"),
]);
assert_eq!(plan.phases, vec![vec![n("alpha"), n("mid"), n("zeta")]]);
}
#[test]
fn build_dep_gates_but_dev_dep_does_not() {
// b build-deps a ⇒ a first. c dev-deps a ⇒ NO ordering constraint,
// so c publishes in the first wave alongside a.
let plan = plan_waves(&[
WorkspaceCrate::new("b").dep("a", DepKind::Build),
WorkspaceCrate::new("a"),
WorkspaceCrate::new("c").dep("a", DepKind::Development),
]);
assert_eq!(plan.phase_of("b"), Some(1));
assert_eq!(plan.phase_of("a"), Some(0));
assert_eq!(plan.phase_of("c"), Some(0), "dev-dep must not delay c");
assert!(!plan.has_cycle());
}
#[test]
fn dev_dep_backedge_is_not_a_false_cycle() {
// app --Normal--> core, core --Development--> app. With dev-deps counted
// this is a cycle; correctly excluded, it is a clean DAG: core, then app.
let plan = plan_waves(&[
WorkspaceCrate::new("app").dep("core", DepKind::Normal),
WorkspaceCrate::new("core").dep("app", DepKind::Development),
]);
assert!(!plan.has_cycle(), "dev-dep back-edge must not read as a cycle");
assert_eq!(plan.phases, vec![vec![n("core")], vec![n("app")]]);
}
#[test]
fn unpublishable_member_is_dropped_and_never_gates() {
// gen is publish=false. app normal-deps gen — but gen never publishes, so
// app must NOT wait for it: app lands in the first wave.
let plan = plan_waves(&[
WorkspaceCrate::new("app").dep("gen", DepKind::Normal),
WorkspaceCrate::new("gen").unpublishable(),
]);
assert_eq!(plan.phase_of("gen"), None, "publish=false crate is dropped");
assert_eq!(plan.phase_of("app"), Some(0), "no wait on an unpublished dep");
assert_eq!(plan.len(), 1);
}
#[test]
fn external_dep_is_ignored() {
// serde is not a workspace member ⇒ no ordering constraint.
let plan = plan_waves(&[
WorkspaceCrate::new("app").dep("serde", DepKind::Normal),
]);
assert_eq!(plan.phases, vec![vec![n("app")]]);
}
#[test]
fn real_cycle_is_surfaced_not_dropped() {
// a ↔ b, both Normal: a genuine (illegal) publish cycle.
let plan = plan_waves(&[
WorkspaceCrate::new("a").dep("b", DepKind::Normal),
WorkspaceCrate::new("b").dep("a", DepKind::Normal),
]);
assert!(plan.has_cycle());
assert_eq!(plan.cyclic, vec![n("a"), n("b")]);
assert!(plan.phases.is_empty(), "cyclic crates are not placed in a wave");
}
#[test]
fn three_level_chain_layers_into_three_waves() {
// top → mid → base
let plan = plan_waves(&[
WorkspaceCrate::new("top").dep("mid", DepKind::Normal),
WorkspaceCrate::new("mid").dep("base", DepKind::Normal),
WorkspaceCrate::new("base"),
]);
assert_eq!(
plan.phases,
vec![vec![n("base")], vec![n("mid")], vec![n("top")]]
);
}
#[test]
fn topo_phases_appends_cycle_remainder_as_final_phase() {
// Drop-in shape for nornir's historic topo_phases: clean deps ordered,
// the cyclic remainder appended (nothing dropped).
let phases = topo_phases(vec![
(n("leaf"), vec![]),
(n("a"), vec![n("b")]),
(n("b"), vec![n("a")]),
]);
assert_eq!(phases.first(), Some(&vec![n("leaf")]));
assert_eq!(phases.last(), Some(&vec![n("a"), n("b")]), "cycle appended");
}
#[test]
fn publish_edges_filters_dev_external_and_unpublishable() {
let ws: BTreeSet<String> = ["app", "core", "gen"].iter().map(|s| n(s)).collect();
let crates = vec![
WorkspaceCrate::new("app")
.dep("core", DepKind::Normal)
.dep("gen", DepKind::Development) // dev — dropped
.dep("serde", DepKind::Normal), // external — dropped
WorkspaceCrate::new("core"),
WorkspaceCrate::new("gen").unpublishable(), // unpublishable — dropped
];
let edges = publish_edges(&crates, &ws);
assert_eq!(
edges,
vec![(n("app"), vec![n("core")]), (n("core"), vec![])]
);
}
}