crates/nornir-feature-graph/src/resolve.rs
//! **The forward map `F`** — the least fixpoint of cargo's feature activation
//! rules over a set of parsed manifests.
//!
//! `F(S)` = the set of packages that end up in the build when the root package
//! is built with root features `S`. This is the map the whole Galois connection
//! is built on, and it is the one thing `cargo metadata` gets wrong: it has no
//! `-p`, it always resolves the whole workspace including dev-dependencies, and
//! it flattens `pkg?/feat` so that a dependency arriving only under a
//! conjunction looks like a dependency arriving under nothing.
//!
//! Measured on this constellation, 2026-08-01: `cargo metadata`'s closure from
//! `znippy-cli` was 457 crates against a real 276 (65.6% inflation, 181
//! phantoms), and it reported `pulls(sign) = 0` where the truth is 46.
//!
//! The rules implemented here, which ARE cargo's:
//!
//! | token | effect |
//! |---|---|
//! | `dep:x` | activate optional dep `x`. Nothing else. |
//! | `g` | turn on this package's feature `g` (or, if `g` names an optional dep with no `dep:` mention anywhere, activate it — the implicit feature) |
//! | `x/g` | activate dep `x` **and** turn on `x`'s feature `g` |
//! | `x?/g` | turn on `x`'s feature `g` **only if `x` is already activated**. Never pulls `x` in. |
//!
//! A package activated through a dependency edge also gets the features that
//! edge requests, plus `default` unless the edge set `default-features = false`.
use crate::facts::{classify, dep_feature_of, DepKind, EnableKind, PackageFacts};
use std::collections::{BTreeMap, BTreeSet};
/// How to resolve — the knobs that must match the oracle being compared against.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolveConfig {
/// Include `[dev-dependencies]`. `false` mirrors `cargo tree -e no-dev`.
pub dev_deps: bool,
/// Include `[build-dependencies]`. `true` mirrors `cargo tree -e no-dev`,
/// which walks build deps.
pub build_deps: bool,
/// Include `[target.'cfg(...)']` dependencies. `true` mirrors
/// `cargo tree --target all`; `false` would need a real cfg evaluator, which
/// this crate deliberately does not pretend to have.
pub all_targets: bool,
/// Seed the root package's `default` feature.
pub default_features: bool,
}
impl Default for ResolveConfig {
fn default() -> Self {
Self { dev_deps: false, build_deps: true, all_targets: true, default_features: false }
}
}
/// The parsed world a resolve runs against.
#[derive(Debug, Clone, Default)]
pub struct Universe {
packages: BTreeMap<String, PackageFacts>,
}
impl Universe {
pub fn new(packages: BTreeMap<String, PackageFacts>) -> Self {
Self { packages }
}
pub fn insert(&mut self, facts: PackageFacts) {
self.packages.insert(facts.id.clone(), facts);
}
pub fn get(&self, name: &str) -> Option<&PackageFacts> {
self.packages.get(name)
}
pub fn len(&self) -> usize {
self.packages.len()
}
pub fn is_empty(&self) -> bool {
self.packages.is_empty()
}
pub fn names(&self) -> impl Iterator<Item = &String> {
self.packages.keys()
}
pub fn packages(&self) -> impl Iterator<Item = &PackageFacts> {
self.packages.values()
}
/// Parse `Cargo.toml` text straight into the universe — the test-friendly
/// door, so a fixture is a string literal and not a tempdir.
pub fn add_manifest_str(
&mut self,
repo: &str,
name_hint: &str,
text: &str,
) -> Result<(), crate::parse::ParseError> {
let facts =
crate::parse::parse_manifest_str(repo, std::path::Path::new(name_hint), text)?;
self.insert(facts);
Ok(())
}
}
/// **The result of one resolve.** Carries what it could NOT determine, so a
/// truncated closure can never be mistaken for a small one.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Resolution {
/// Every package in the build, by real package name (the root included).
pub packages: BTreeSet<String>,
/// Every `(package, feature)` turned on.
pub features: BTreeSet<(String, String)>,
/// **Packages that entered the closure but whose manifest is not in the
/// universe**, so their own dependencies could not be expanded.
///
/// This is the honesty field. A resolve with a non-empty `unresolved` has a
/// TRUNCATED closure — reporting its `packages` as "the dependencies" would
/// be a measurement dressed as a fact. Callers that care must check it.
pub unresolved: BTreeSet<String>,
}
impl Resolution {
pub fn contains(&self, pkg: &str) -> bool {
self.packages.contains(pkg)
}
/// Whether the closure is complete — every package reached was expandable.
pub fn is_complete(&self) -> bool {
self.unresolved.is_empty()
}
}
/// **`F`** — resolve `root` with exactly the root features `roots`.
///
/// Runs to a least fixpoint. Monotone in `roots` by construction: nothing here
/// ever removes an activation, so `S ⊆ T ⟹ F(S) ⊆ F(T)`.
pub fn resolve(
universe: &Universe,
root: &str,
roots: &BTreeSet<String>,
cfg: &ResolveConfig,
) -> Resolution {
let mut pkgs: BTreeSet<String> = BTreeSet::new();
let mut feats: BTreeSet<(String, String)> = BTreeSet::new();
// (parent package, dep KEY as the parent names it) — the weak rule asks
// whether a specific parent's optional dep is on, not whether the crate is
// in the build somewhere.
let mut dep_edges: BTreeSet<(String, String)> = BTreeSet::new();
pkgs.insert(root.to_string());
for f in roots {
feats.insert((root.to_string(), f.clone()));
}
if cfg.default_features {
if let Some(facts) = universe.get(root) {
if facts.features.contains_key("default") {
feats.insert((root.to_string(), "default".to_string()));
}
}
}
let want = |k: DepKind| match k {
DepKind::Normal => true,
DepKind::Build => cfg.build_deps,
DepKind::Dev => cfg.dev_deps,
};
loop {
let before = (pkgs.len(), feats.len(), dep_edges.len());
// (1) An active package pulls its NON-optional deps, unconditionally.
for p in pkgs.clone() {
let Some(facts) = universe.get(&p) else { continue };
for dep in facts.deps.values() {
if dep.optional || !want(dep.kind) {
continue;
}
if !cfg.all_targets && dep.target_cfg.is_some() {
continue;
}
dep_edges.insert((p.clone(), dep.key.clone()));
}
}
// (2) An active dep edge puts the crate in the build and applies the
// features that edge requested, plus `default` unless waived.
for (p, key) in dep_edges.clone() {
let Some(facts) = universe.get(&p) else { continue };
let Some(dep) = facts.dep_by_key(&key) else { continue };
if !want(dep.kind) {
continue;
}
if !cfg.all_targets && dep.target_cfg.is_some() {
continue;
}
pkgs.insert(dep.package.clone());
for g in &dep.features {
// A dep-edge feature list may itself carry `x/g` (asking for a
// feature of the dependency's OWN dependency). Cargo resolves
// that inside the dependency, so it is a feature token there.
let (kind, payload) = classify(g);
match kind {
EnableKind::Feature => {
feats.insert((dep.package.clone(), payload));
}
_ => {
feats.insert((dep.package.clone(), g.clone()));
}
}
}
if dep.default_features {
if let Some(df) = universe.get(&dep.package) {
if df.features.contains_key("default") {
feats.insert((dep.package.clone(), "default".to_string()));
}
}
}
}
// (3) An active feature applies its token list.
for (p, f) in feats.clone() {
let Some(facts) = universe.get(&p) else { continue };
match facts.features.get(&f) {
Some(list) => {
for tok in list {
let (kind, payload) = classify(tok);
match kind {
EnableKind::Dep => {
dep_edges.insert((p.clone(), payload));
}
EnableKind::Feature => {
feats.insert((p.clone(), payload));
}
EnableKind::DepFeature => {
let Some((dk, g)) = payload.split_once('/') else { continue };
dep_edges.insert((p.clone(), dk.to_string()));
if let Some(dep) = facts.dep_by_key(dk) {
feats.insert((dep.package.clone(), g.to_string()));
}
}
EnableKind::WeakDepFeature => {
// THE AND-GROUP. Only fires once the dep is
// already on — which is why a single feature
// can look innocent and a pair can pull 39
// crates.
let Some(dk) = payload.split_once('/').map(|(d, _)| d) else {
continue;
};
if !dep_edges.contains(&(p.clone(), dk.to_string())) {
continue;
}
let Some(g) = dep_feature_of(&payload) else { continue };
if let Some(dep) = facts.dep_by_key(dk) {
feats.insert((dep.package.clone(), g.to_string()));
}
}
EnableKind::ImplicitDep => {}
}
}
}
// Not a declared feature. Two things it can still be.
None => {
// (a) A `dep/feat` token that arrived from a DEPENDENCY EDGE's
// `features = [...]` list rather than from a feature table.
// `foo = { features = ["bar/baz"] }` asks foo to turn on
// baz of ITS dependency bar, so the token has to be
// applied in foo's context, not stored as a feature named
// "bar/baz" — which is what happened before, and the
// token then matched nothing and was silently dropped.
//
// Measured cost of the old behaviour, 2026-08-01: nornir
// derived 744 crates against a real 751 — cms, der_derive,
// flagset, num-bigint-dig, num-iter, spin and one more,
// all reached only through such a token.
if f.contains('/') {
let (kind, payload) = classify(&f);
let Some((dk, g)) = payload.split_once('/') else { continue };
let weak = kind == EnableKind::WeakDepFeature;
if weak && !dep_edges.contains(&(p.clone(), dk.to_string())) {
continue;
}
if !weak {
dep_edges.insert((p.clone(), dk.to_string()));
}
if let Some(dep) = facts.dep_by_key(dk) {
feats.insert((dep.package.clone(), g.to_string()));
}
continue;
}
// (b) The IMPLICIT feature of an optional dep of the same name.
if facts.implicit_dep_features().contains(&f) {
dep_edges.insert((p.clone(), f.clone()));
}
}
}
}
if (pkgs.len(), feats.len(), dep_edges.len()) == before {
break;
}
}
let unresolved: BTreeSet<String> =
pkgs.iter().filter(|p| universe.get(p).is_none()).cloned().collect();
Resolution { packages: pkgs, features: feats, unresolved }
}
/// Every root feature of `root` that a caller may toggle: the declared ones plus
/// the implicit optional-dep ones.
pub fn root_features(universe: &Universe, root: &str) -> BTreeSet<String> {
universe.get(root).map(|f| f.all_feature_names()).unwrap_or_default()
}