crates/nornir-feature-graph/src/galois.rs
//! **The two adjoints.**
//!
//! `F : 2^Feature → 2^Crate` is [`resolve`](crate::resolve::resolve). This module
//! is the other direction, and the correction to how it used to be written.
//!
//! ## What was wrong before
//!
//! The hand-maintained version modelled the preimage as
//! `features_pulling(c) = { f : c ∈ F({f}) }` — the crates a SINGLE feature
//! pulls. That is only correct when every crate has an OR of single causes.
//! Weak dependencies (`pkg?/feat`) break it: a crate can arrive under a
//! CONJUNCTION and under no single feature at all, so the preimage comes back
//! empty and the crate is reported as not removable — a false negative on
//! exactly the crates a tier ladder exists to remove.
//!
//! Measured on this constellation, 2026-08-01, `cargo tree -p nornir-auth-policy
//! -e no-dev --no-default-features`:
//!
//! | features | closure | `reqwest` |
//! |---|---|---|
//! | none | 72 | no |
//! | `online` | 72 | no |
//! | `auth-oidc` | 101 | no |
//! | `auth-oidc,online` | **140** | **yes** |
//!
//! 39 of 140 crates (27.9%) exist only under that conjunction. The old model
//! answers `[]` for all of them.
//!
//! ## What this does instead
//!
//! The preimage of `c` is a set of **minimal causes**, each a conjunction of
//! root features. `{S : c ∈ F(S)}` is upward-closed because `F` is monotone, so
//! it is exactly the up-set of its minimal elements — which means a set of
//! features to turn OFF works iff it **hits every minimal cause**.
//!
//! Causes are enumerated by shrink-from-the-top, and the resulting drop plan is
//! then **verified by re-running `F`**. The plan is never trusted because the
//! cause list looked complete; it is trusted because `c ∉ F(Φ \ R)` was actually
//! computed. Completeness of the cause list is established separately, by the
//! standard hitting-set duality: if every minimal hitting set of the found
//! causes also kills `c`, no cause was missed.
use crate::resolve::{resolve, ResolveConfig, Resolution, Universe};
use serde::{Deserialize, Serialize};
use std::collections::BTreeSet;
/// A minimal conjunction of root features that brings a crate into the build.
/// A one-element cause is the ordinary case; a two-element cause is an
/// **AND-group** and is the thing a naive UI lies about.
pub type Cause = BTreeSet<String>;
/// How a crate relates to the feature axis at all.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
pub enum Reachability {
/// In the build with NO features on — the ⊥ case. No click can remove it.
Unconditional,
/// Not in the build even with EVERY feature on. Nothing to show.
Never,
/// In the build under at least one cause.
Conditional,
}
/// **The lower adjoint**: what to turn off to lose a crate, and what that costs.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct DropPlan {
pub crate_name: String,
pub removable: bool,
/// The features to disable — a minimum-cardinality hitting set of the
/// causes. Empty when the crate is unconditional or unreachable.
pub features_to_disable: BTreeSet<String>,
/// Other equally small ways to do it, so a UI can offer a choice instead of
/// presenting one arbitrary answer as the only one.
pub alternatives: Vec<BTreeSet<String>>,
/// **`true` only when `c ∉ F(Φ \ features_to_disable)` was actually
/// computed.** A `false` here means the search hit its budget and the plan
/// is a proposal, not a proof — say so rather than shipping a maybe as a
/// fact.
pub verified: bool,
pub note: String,
}
/// Everything the UI needs about one crate on the feature axis.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct CrateAnalysis {
pub crate_name: String,
pub status: Reachability,
/// The minimal causes. Each inner set of size ≥ 2 is an AND-group.
pub causes: Vec<Cause>,
/// Whether every minimal cause was found (hitting-set duality confirmed).
pub causes_complete: bool,
pub drop: DropPlan,
}
impl CrateAnalysis {
/// The causes that are conjunctions — what must be rendered as an AND-group.
pub fn and_groups(&self) -> Vec<&Cause> {
self.causes.iter().filter(|c| c.len() > 1).collect()
}
/// A crate pulled by exactly one feature: one click removes it.
pub fn single_cause(&self) -> Option<&str> {
match self.causes.as_slice() {
[only] if only.len() == 1 => only.iter().next().map(String::as_str),
_ => None,
}
}
}
/// How hard to search before admitting the answer is not proven.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Budget {
/// Maximum minimal causes to enumerate for one crate.
pub max_causes: usize,
/// Maximum minimal hitting sets to enumerate when checking completeness.
pub max_hitting_sets: usize,
}
impl Default for Budget {
fn default() -> Self {
Self { max_causes: 32, max_hitting_sets: 256 }
}
}
/// **The analyser.** Holds the universe and the root so the (many) resolves a
/// full analysis needs all run against the same world.
pub struct FeatureGalois<'a> {
universe: &'a Universe,
root: String,
cfg: ResolveConfig,
all_features: BTreeSet<String>,
budget: Budget,
}
impl<'a> FeatureGalois<'a> {
pub fn new(universe: &'a Universe, root: &str, cfg: ResolveConfig) -> Self {
let all_features = crate::resolve::root_features(universe, root);
Self {
universe,
root: root.to_string(),
cfg,
all_features,
budget: Budget::default(),
}
}
pub fn with_budget(mut self, budget: Budget) -> Self {
self.budget = budget;
self
}
/// Restrict the toggleable feature universe `Φ`. A UI that only shows the
/// features a repo actually declares in its build variants passes them here,
/// so causes are stated in terms the user can click.
pub fn with_features(mut self, features: BTreeSet<String>) -> Self {
self.all_features = features;
self
}
pub fn root(&self) -> &str {
&self.root
}
pub fn features(&self) -> &BTreeSet<String> {
&self.all_features
}
/// **`F(S)`.**
pub fn pulls(&self, features: &BTreeSet<String>) -> Resolution {
resolve(self.universe, &self.root, features, &self.cfg)
}
fn has(&self, features: &BTreeSet<String>, krate: &str) -> bool {
self.pulls(features).contains(krate)
}
/// **The upper adjoint** — every minimal conjunction of root features that
/// brings `krate` in.
///
/// Returns `(causes, complete)`. A crate that arrives with no features on
/// yields an empty cause list with `complete = true`: the honest statement
/// that nothing causes it because it is always there.
pub fn features_pulling(&self, krate: &str) -> (Vec<Cause>, bool) {
let empty = BTreeSet::new();
if self.has(&empty, krate) {
return (Vec::new(), true);
}
if !self.has(&self.all_features, krate) {
return (Vec::new(), true);
}
let mut causes: Vec<Cause> = Vec::new();
// Seed with the whole universe shrunk down: guaranteed to yield one
// minimal cause, whatever its size.
causes.push(self.shrink(&self.all_features, krate));
// Hitting-set duality. If some minimal hitting set of the causes found
// so far does NOT kill the crate, there is a cause it does not hit —
// find it in what remains and add it. When every minimal hitting set
// kills the crate, the list is complete.
let mut complete = false;
for _ in 0..self.budget.max_causes {
let hs = min_hitting_sets(&causes, self.budget.max_hitting_sets);
let mut found_gap = false;
for h in &hs {
let remaining: BTreeSet<String> =
self.all_features.difference(h).cloned().collect();
if self.has(&remaining, krate) {
let c = self.shrink(&remaining, krate);
if !causes.contains(&c) {
causes.push(c);
}
found_gap = true;
break;
}
}
if !found_gap {
complete = true;
break;
}
}
causes.sort_by(|a, b| a.len().cmp(&b.len()).then_with(|| a.cmp(b)));
(causes, complete)
}
/// Shrink a known-sufficient feature set to a minimal cause: drop features
/// one at a time, keeping every drop that leaves the crate present.
///
/// The result is minimal by inclusion — no element can be removed — which is
/// what the duality argument needs.
fn shrink(&self, from: &BTreeSet<String>, krate: &str) -> Cause {
let mut s = from.clone();
for f in from {
let mut candidate = s.clone();
candidate.remove(f);
if self.has(&candidate, krate) {
s = candidate;
}
}
s
}
/// **The lower adjoint** — the smallest set of features to turn off so
/// `krate` leaves the build, VERIFIED by re-resolving.
pub fn drop_crate(&self, krate: &str) -> DropPlan {
let empty = BTreeSet::new();
if self.has(&empty, krate) {
return DropPlan {
crate_name: krate.to_string(),
removable: false,
features_to_disable: BTreeSet::new(),
alternatives: Vec::new(),
verified: true,
note: format!(
"{krate} is in the build with NO features enabled — it is pulled \
unconditionally, and no combination of feature clicks removes it."
),
};
}
if !self.has(&self.all_features, krate) {
return DropPlan {
crate_name: krate.to_string(),
removable: false,
features_to_disable: BTreeSet::new(),
alternatives: Vec::new(),
verified: true,
note: format!(
"{krate} is not in the build even with all {} features enabled — \
there is nothing to remove.",
self.all_features.len()
),
};
}
let (causes, complete) = self.features_pulling(krate);
let hs = min_hitting_sets(&causes, self.budget.max_hitting_sets);
let smallest = hs.iter().map(BTreeSet::len).min().unwrap_or(0);
let minimal: Vec<BTreeSet<String>> =
hs.into_iter().filter(|h| h.len() == smallest).collect();
let chosen = minimal.first().cloned().unwrap_or_default();
// LAW 2: do not report a plan because the arithmetic looked right —
// run F and look.
let remaining: BTreeSet<String> =
self.all_features.difference(&chosen).cloned().collect();
let verified = !self.has(&remaining, krate);
let conj = causes.iter().filter(|c| c.len() > 1).count();
let note = if !verified {
format!(
"UNVERIFIED: turning off {:?} did NOT remove {krate} when re-resolved. The \
cause search hit its budget ({} causes, complete={complete}).",
chosen, causes.len()
)
} else if conj > 0 {
format!(
"{krate} arrives under {} cause(s), {conj} of them a CONJUNCTION (a weak \
`pkg?/feat` AND-group). Turning off {:?} hits every cause; re-resolving \
confirms {krate} is then absent.",
causes.len(),
chosen
)
} else {
format!(
"{krate} arrives under {} single-feature cause(s). Turning off {:?} hits \
every cause; re-resolving confirms {krate} is then absent.",
causes.len(),
chosen
)
};
DropPlan {
crate_name: krate.to_string(),
removable: true,
features_to_disable: chosen,
alternatives: minimal.into_iter().skip(1).collect(),
verified,
note,
}
}
/// The whole picture for one crate.
pub fn analyse(&self, krate: &str) -> CrateAnalysis {
let empty = BTreeSet::new();
let status = if self.has(&empty, krate) {
Reachability::Unconditional
} else if !self.has(&self.all_features, krate) {
Reachability::Never
} else {
Reachability::Conditional
};
let (causes, causes_complete) = self.features_pulling(krate);
CrateAnalysis {
crate_name: krate.to_string(),
status,
causes,
causes_complete,
drop: self.drop_crate(krate),
}
}
/// **The other direction of the same connection**: the crates that leave the
/// build when `feature` is turned off, everything else staying on.
///
/// This is `F(Φ) \ F(Φ \ {f})` — computed from the SAME `F`, not from a
/// second table that has to agree with the first.
pub fn crates_lost_by_disabling(&self, feature: &str) -> BTreeSet<String> {
let all = self.pulls(&self.all_features);
let mut without = self.all_features.clone();
without.remove(feature);
let less = self.pulls(&without);
all.packages.difference(&less.packages).cloned().collect()
}
/// The crates a feature pulls **on its own**, from nothing else — the naive
/// reading, kept only so a caller can SEE the difference against
/// [`crates_lost_by_disabling`]. Where the two disagree, an AND-group is why.
pub fn crates_pulled_alone(&self, feature: &str) -> BTreeSet<String> {
let base = self.pulls(&BTreeSet::new());
let one: BTreeSet<String> = [feature.to_string()].into_iter().collect();
let with = self.pulls(&one);
with.packages.difference(&base.packages).cloned().collect()
}
}
/// **All minimal hitting sets** of a family of sets, smallest first.
///
/// A hitting set meets every member. Minimal = no proper subset does. These are
/// tiny (causes have 1–2 elements in every case measured on this constellation),
/// so a straightforward branch over the first unhit set is exact and fast; `cap`
/// exists only so a pathological input degrades into an honest partial answer
/// rather than a hang.
pub fn min_hitting_sets(sets: &[Cause], cap: usize) -> Vec<BTreeSet<String>> {
if sets.is_empty() {
return vec![BTreeSet::new()];
}
let mut found: Vec<BTreeSet<String>> = Vec::new();
let mut stack: Vec<BTreeSet<String>> = vec![BTreeSet::new()];
while let Some(current) = stack.pop() {
if found.len() >= cap {
break;
}
match sets.iter().find(|s| s.is_disjoint(¤t)) {
None => {
// Hits everything. Keep it only if nothing already found is a
// subset — that is exactly the minimality test.
if !found.iter().any(|f| f.is_subset(¤t)) {
found.retain(|f| !current.is_subset(f));
found.push(current);
}
}
Some(unhit) => {
for e in unhit {
let mut next = current.clone();
next.insert(e.clone());
stack.push(next);
}
}
}
}
found.sort_by(|a, b| a.len().cmp(&b.len()).then_with(|| a.cmp(b)));
found
}