crates/nornir-feature-graph/src/lib.rs
//! # nornir-feature-graph — the edge Mímir did not have
//!
//! Mímir knows which CODE a feature gates (`feature_gate_facts.cfg_expr`, with
//! file and line) and which crates a repo pulls (`dep_graph_edges`). It did not
//! know **which feature causes which optional dependency to be pulled**. That
//! single edge is what hand-maintained tables like holger's `FEATURE_PULLS` used
//! to encode by hand, and it is what this crate derives.
//!
//! ## Why not `cargo metadata`
//!
//! Because it provably cannot answer this. Measured on this constellation,
//! 2026-08-01 (prototype at `~/scratch/cargo/galois-probe`):
//!
//! - The closure from `znippy-cli` came back **457 crates against a real 276**
//! (`cargo tree -p -e no-dev`) — 65.6% inflation, 181 phantoms. `cargo
//! metadata` has no `-p`; it always resolves the whole workspace including
//! dev-dependencies.
//! - It **masked a whole feature**: it reported `pulls(sign) = 0 crates`; the
//! true answer is **46**. Cross-repo feature unification through
//! `[patch.crates-io]` turned `sign` on in every resolve.
//! - It flattens weak dependencies, so AND-groups vanish.
//!
//! The reliable oracle is `cargo tree -p <pkg> -e no-dev --features …`, at
//! 0.48–0.73 s per resolve. Measured against it over 19 cases spanning edda,
//! dwarves, holger and nornir (closures of 1–751 crates): **19/19 exact, recall
//! 1.0000, precision 1.0000** (2026-08-01). That is too slow to sit behind a UI click and too
//! stateful to put in a warehouse, so this crate reimplements cargo's activation
//! rules over parsed manifests and is **measured against that oracle** rather
//! than against itself.
//!
//! ## The shape
//!
//! | module | what |
//! |---|---|
//! | [`facts`] | one manifest's features + deps, and the `feature_dep_edges` ROW it emits |
//! | [`parse`] | `Cargo.toml` → facts, and the shared manifest walk |
//! | [`resolve`] | **`F`** — the least-fixpoint forward map |
//! | [`galois`] | the two adjoints, with exact AND-group handling |
//! | [`bipartite`] | the clickable feature↔crate graph, on the `nornir-graph` seam |
//!
//! ## The correction this crate encodes
//!
//! The old model said `features_pulling(c) = { f : c ∈ F({f}) }`. Under weak
//! dependencies that returns `[]` for a crate that a *pair* of features pulls,
//! and the crate is then reported as unremovable — a false negative on exactly
//! the crates a tier ladder exists to remove. The preimage here is a set of
//! **minimal causes**, each a conjunction; see [`galois`].
//!
//! It also fixes an overclaim. The documented "Galois connection between two
//! full powersets" does not hold. (A prior probe put the failure at 19.49%
//! outside the interval `[F(∅), F(⊤)]`, exact 16000/16000 inside it — that
//! figure is CITED, not re-measured here.)
//!
//! What this crate does verify, because everything else rests on it, is the
//! weaker and sufficient property: `F` is MONOTONE, therefore `{S : c ∈ F(S)}`
//! is upward-closed, therefore it is exactly the up-set of its minimal elements,
//! therefore a drop plan is correct iff it hits every minimal cause. See
//! `tests/monotone_law.rs` — checked over 400 subset pairs on a hostile fixture
//! and exhaustively over every added feature on dwarves' real manifests.
//!
//! ## Concurrency
//!
//! None. This crate is pure and single-threaded by design; callers that fan out
//! over repos use `gatling`. **rayon is forbidden** (LAW 3).
pub mod bipartite;
pub mod facts;
pub mod galois;
pub mod parse;
pub mod registry;
pub mod resolve;
pub use facts::{DepKind, DepSpec, EnableKind, FeatureDepEdgeRow, PackageFacts};
pub use galois::{Budget, Cause, CrateAnalysis, DropPlan, FeatureGalois, Reachability};
pub use parse::{
parse_manifest, parse_manifest_str, scan_repos, walk_cargo_tomls, ParseError, ScanOutcome,
};
pub use resolve::{resolve, root_features, ResolveConfig, Resolution, Universe};
use std::collections::BTreeMap;
/// **Every `feature_dep_edges` row for a set of repo roots.**
///
/// The single entry point a warehouse producer calls. Returns the rows AND the
/// universe they were derived from, because the graph a UI renders must come
/// from the same parse as the rows a table stores — two parses would be two
/// truths (LAW 5).
pub fn scan(roots: &[(&str, &std::path::Path)]) -> (Vec<FeatureDepEdgeRow>, Universe, ScanOutcome) {
let outcome = scan_repos(roots.iter().map(|(r, p)| (*r, *p)));
let mut rows = Vec::new();
for facts in outcome.packages.values() {
rows.extend(facts.edges());
}
rows.sort();
rows.dedup();
let universe = Universe::new(outcome.packages.clone());
(rows, universe, outcome)
}
/// Rebuild a [`Universe`] from warehouse rows.
///
/// This is the READ path: Build Thing does not re-walk the disk, it reads
/// `feature_dep_edges` out of Mímir and reconstitutes the same world.
///
/// **It refuses an empty input.** A universe built from no rows would answer
/// every query with "nothing depends on this", which is indistinguishable from
/// a correct answer and is exactly the confusion that cost an hour of a working
/// day on 2026-07-31. Empty must be loud.
pub fn universe_from_rows(rows: &[FeatureDepEdgeRow]) -> Result<Universe, EmptyWarehouse> {
if rows.is_empty() {
return Err(EmptyWarehouse);
}
let mut packages: BTreeMap<String, PackageFacts> = BTreeMap::new();
for r in rows {
let facts = packages.entry(r.crate_name.clone()).or_insert_with(|| PackageFacts {
id: r.crate_name.clone(),
name: r.crate_name.clone(),
version: String::new(),
repo: r.repo.clone(),
..Default::default()
});
let key = match r.kind {
EnableKind::Feature => None,
EnableKind::Dep | EnableKind::ImplicitDep => Some(r.enables.clone()),
EnableKind::DepFeature | EnableKind::WeakDepFeature => {
r.enables.split_once('/').map(|(d, _)| d.to_string())
}
};
if let Some(k) = key {
facts.deps.entry((k.clone(), r.dep_kind)).or_insert(DepSpec {
key: k.clone(),
package: k,
optional: r.optional,
default_features: true,
features: Vec::new(),
kind: r.dep_kind,
target_cfg: r.target_cfg.clone(),
});
}
if r.feature.is_empty() {
continue;
}
let tok = match r.kind {
EnableKind::Dep => format!("dep:{}", r.enables),
EnableKind::Feature => r.enables.clone(),
EnableKind::DepFeature => r.enables.clone(),
EnableKind::WeakDepFeature => {
let (d, g) = r.enables.split_once('/').unwrap_or((&r.enables, ""));
format!("{d}?/{g}")
}
// The implicit feature is synthesised by `implicit_dep_features`
// from the optional dep, exactly as cargo does — writing it into the
// feature table here would make it explicit and thereby suppress the
// real one.
EnableKind::ImplicitDep => continue,
};
facts.features.entry(r.feature.clone()).or_default().push(tok);
}
for f in packages.values_mut() {
for list in f.features.values_mut() {
list.sort();
list.dedup();
}
}
Ok(Universe::new(packages))
}
/// The read path found no rows. Distinct from "found rows saying nothing".
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct EmptyWarehouse;
impl std::fmt::Display for EmptyWarehouse {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"feature_dep_edges returned ZERO rows — this is 'the table was never populated', \
NOT 'no feature pulls anything'. Refusing to build a universe that would answer \
every query with a confident empty set. Run a scan, and check you are reading the \
SERVED warehouse rather than a local empty one."
)
}
}
impl std::error::Error for EmptyWarehouse {}