crates/nornir-feature-graph/src/registry.rs
//! **Third-party manifests and exact version resolution**, so a closure is the
//! real closure.
//!
//! Walking a repo gives its own packages. Everything else — the thousand-odd
//! registry crates that make up most of any real dependency tree — lives in
//! `~/.cargo/registry/src/<index>/<name>-<version>/Cargo.toml`, already on disk
//! after any build.
//!
//! ## Why this keys on `name version`, not `name`
//!
//! A lockfile routinely holds several versions of a crate. This workspace locks
//! **indexmap 1.9.3 and 2.14.0** simultaneously, and their manifests disagree
//! about their own dependencies: 1.x has an `autocfg` build-dep that 2.x does
//! not, and 2.x has an `equivalent` dep that 1.x does not.
//!
//! Both name-keyed strategies were MEASURED against `cargo tree -e no-dev
//! --target all` on 2026-08-01 and both are wrong:
//!
//! | universe keyed by | recall | precision |
//! |---|---|---|
//! | name, first locked entry wins (oldest) | 0.9753 | 0.9857 |
//! | name, newest locked entry wins | 0.8816 | 0.9727 |
//! | **`name version`, edges from the lock** | see `tests/oracle_accuracy.rs` |
//!
//! Newest-wins being the WORSE of the two is the point: there is no right
//! heuristic, because cargo is not guessing — it resolved each edge against a
//! version requirement. `Cargo.lock` records the answer. Every `[[package]]`
//! carries a `dependencies` list whose entries are `"name"` when unambiguous
//! and `"name version"` when not, which is exactly the resolved edge set. This
//! module reads that instead of guessing.
use crate::facts::PackageFacts;
use crate::parse::{parse_manifest, ParseError};
use crate::resolve::Universe;
use std::collections::{BTreeMap, BTreeSet};
use std::path::{Path, PathBuf};
/// One `[[package]]` entry from a `Cargo.lock`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LockedPackage {
pub name: String,
pub version: String,
/// `None` for a path / workspace-member package.
pub source: Option<String>,
/// The RESOLVED dependency references: `"name"` or `"name version"`.
pub deps: Vec<String>,
}
impl LockedPackage {
/// The universe key. Space-separated so it matches the lockfile's own
/// disambiguated reference syntax verbatim.
pub fn id(&self) -> String {
format!("{} {}", self.name, self.version)
}
pub fn is_local(&self) -> bool {
self.source.is_none()
}
}
/// The package name out of a universe id.
pub fn name_of(id: &str) -> &str {
id.split(' ').next().unwrap_or(id)
}
/// Parse the `[[package]]` list out of a `Cargo.lock`.
pub fn parse_lockfile(text: &str) -> Result<Vec<LockedPackage>, toml::de::Error> {
let doc: toml::Value = toml::from_str(text)?;
let Some(pkgs) = doc.get("package").and_then(|v| v.as_array()) else {
return Ok(Vec::new());
};
Ok(pkgs
.iter()
.filter_map(|p| {
let t = p.as_table()?;
Some(LockedPackage {
name: t.get("name")?.as_str()?.to_string(),
version: t.get("version")?.as_str()?.to_string(),
source: t.get("source").and_then(|v| v.as_str()).map(str::to_string),
deps: t
.get("dependencies")
.and_then(|v| v.as_array())
.map(|a| {
a.iter().filter_map(|e| e.as_str().map(str::to_string)).collect()
})
.unwrap_or_default(),
})
})
.collect())
}
/// Where extracted registry sources live. Honours `CARGO_HOME`.
pub fn registry_src_roots() -> Vec<PathBuf> {
let home = std::env::var_os("CARGO_HOME")
.map(PathBuf::from)
.or_else(|| std::env::var_os("HOME").map(|h| PathBuf::from(h).join(".cargo")));
let Some(home) = home else { return Vec::new() };
let src = home.join("registry").join("src");
let Ok(rd) = std::fs::read_dir(&src) else { return Vec::new() };
let mut out: Vec<PathBuf> = rd
.filter_map(Result::ok)
.filter(|e| e.file_type().map(|t| t.is_dir()).unwrap_or(false))
.map(|e| e.path())
.collect();
out.sort();
out
}
/// What a load managed and what it did not — the honesty record.
#[derive(Debug, Default)]
pub struct RegistryLoad {
pub locked: usize,
pub loaded: usize,
/// Locked packages whose extracted source was not on disk. These become
/// `Resolution::unresolved` entries, so the truncation is visible rather
/// than silently shortening every closure.
pub missing: Vec<String>,
/// Dependency references in the lock that named no locked package. Should
/// be empty; a non-empty list means the lockfile and the parse disagree.
pub dangling: Vec<String>,
}
/// **The whole resolved world for one workspace**, keyed by `name version`.
///
/// `repo_roots` supplies first-party manifests (path packages are not in the
/// registry cache); the lockfile supplies both the version set and the exact
/// edges between them.
pub fn universe_from_lock(
repo_roots: &[(&str, &Path)],
lock_path: &Path,
) -> Result<(Universe, RegistryLoad), ParseError> {
let text = std::fs::read_to_string(lock_path)
.map_err(|source| ParseError::Io { path: lock_path.to_path_buf(), source })?;
let locked = parse_lockfile(&text)
.map_err(|source| ParseError::Toml { path: lock_path.to_path_buf(), source })?;
// First-party manifests, by package name.
let outcome = crate::parse::scan_repos(repo_roots.iter().map(|(r, p)| (*r, *p)));
// Registry directories, by `<name>-<version>`.
let mut dirs: BTreeMap<String, PathBuf> = BTreeMap::new();
for r in registry_src_roots() {
let Ok(rd) = std::fs::read_dir(&r) else { continue };
for e in rd.filter_map(Result::ok) {
if let Some(n) = e.file_name().to_str() {
dirs.entry(n.to_string()).or_insert_with(|| e.path());
}
}
}
// name → the locked ids carrying it, so a bare `"name"` reference resolves.
let mut by_name: BTreeMap<&str, Vec<&LockedPackage>> = BTreeMap::new();
for p in &locked {
by_name.entry(p.name.as_str()).or_default().push(p);
}
let mut load = RegistryLoad { locked: locked.len(), ..Default::default() };
let mut universe = Universe::default();
for p in &locked {
let id = p.id();
// Prefer the first-party manifest: a path package is the truth for
// itself, and a `[patch.crates-io]` redirect means the registry copy of
// the same name may be a different crate entirely.
let facts = match outcome.first_party(&p.name, &p.version) {
Some(f) if p.is_local() => Some(f.clone()),
_ => {
let dir_name = format!("{}-{}", p.name, p.version);
match dirs.get(&dir_name) {
Some(dir) => parse_manifest("<registry>", &dir.join("Cargo.toml")).ok(),
// Not in the registry cache — fall back to a first-party
// manifest of the same name if there is one (a path
// dependency that the lock marked with a source).
None => outcome.first_party(&p.name, &p.version).cloned(),
}
}
};
let Some(mut facts) = facts else {
load.missing.push(id);
continue;
};
// Rewrite every dep's target from a NAME to a locked ID, using this
// package's own resolved edge list. This is where the exactness comes
// from — no version guessing anywhere.
for dep in facts.deps.values_mut() {
match resolve_ref(&dep.package, &p.deps, &by_name) {
Some(target) => dep.package = target,
None => {
// An optional dep no feature ever enabled is absent from the
// lock, which is correct and expected. Point it at a
// non-existent id so that IF something activates it the
// resolve reports it unresolved rather than silently
// dropping the edge.
dep.package = format!("{} <unlocked>", dep.package);
}
}
}
facts.id = id.clone();
facts.name = p.name.clone();
facts.version = p.version.clone();
universe.insert(facts);
load.loaded += 1;
}
Ok((universe, load))
}
/// Resolve one `dependencies = [...]` reference to a universe id.
///
/// `dep_name` is the real package name the manifest declares (after a
/// `package = "..."` rename). `edges` is the parent's own resolved list.
fn resolve_ref(
dep_name: &str,
edges: &[String],
by_name: &BTreeMap<&str, Vec<&LockedPackage>>,
) -> Option<String> {
for e in edges {
// A lock reference is `name`, `name version`, or — when name AND version
// are both ambiguous (a path copy and a registry copy at the same
// version) — `name version (source)`. Splitting on the FIRST space only
// produced ids like `foo 0.1.4 (registry+https://…)` that matched no
// package, so the edge dangled and the closure came back
// `is_complete() == false`. The names still all matched, so ONLY the
// honesty field caught it.
let mut parts = e.split_whitespace();
let (n, v) = (parts.next().unwrap_or(""), parts.next());
if n != dep_name {
continue;
}
return match v {
Some(v) => Some(format!("{n} {v}")),
// A bare reference is unambiguous by construction — exactly one
// version of that name is locked.
None => by_name.get(n).and_then(|c| c.first()).map(|p| p.id()),
};
}
None
}
/// The universe for one workspace root, with its own `Cargo.lock`.
///
/// **Only correct for a repo with no sibling `path = "../<repo>"` dependencies.**
/// This constellation patches most of itself together that way, and a
/// single-root universe cannot find those packages: they are `source = None` in
/// the lock (so not in the registry cache) and outside the walk (so not
/// first-party). Every registry crate reachable ONLY through such a sibling then
/// drops out too, which is far more than the sibling count.
///
/// Measured 2026-08-01, single-root vs `cargo tree -p -e no-dev --target all`:
///
/// | root | oracle | derived | missing |
/// |---|---|---|---|
/// | `dwarves` | 451 | 107 | 344 |
/// | `holger-build` | 383 | 74 | 309 |
/// | `nornir` | 751 | 691 | 60 |
///
/// — recall 0.5665 over nine cases. With the siblings supplied via
/// [`universe_for_constellation`] the same nine cases are 9/9 EXACT (recall
/// 1.0000, precision 1.0000, tp=4902 fp=0 fn=0).
///
/// The truncation is never silent — `Resolution::is_complete` is false and
/// `unresolved` names every unexpandable package — but a caller that ignores
/// those fields will get a confident undercount. Prefer
/// [`universe_for_constellation`].
pub fn universe_for_workspace(
repo: &str,
workspace_root: &Path,
) -> Result<(Universe, RegistryLoad), ParseError> {
universe_from_lock(&[(repo, workspace_root)], &workspace_root.join("Cargo.lock"))
}
/// **Every repo this one reaches by `path = "..."`**, transitively, with `root`
/// FIRST.
///
/// This replaces a directory sweep of the checkout root, which was measurably
/// worse than useless. Measured 2026-08-01 over 20 holger cases against
/// `cargo tree -p -e no-dev --target all`:
///
/// | roots | exact | recall | precision |
/// |---|---|---|---|
/// | sweep every child of `~/git` (46) | 1/20 | 0.9465 | 0.9986 |
/// | **path-dep closure, root first (15)** | **20/20** | **1.0000** | **1.0000** |
///
/// The sweep loses because a working checkout holds *several worktrees of the
/// same repo on different branches* (`holger`, `holger-wt-mvp`,
/// `holger-audit`, …). [`crate::parse::scan_repos`] is first-claimer-wins over
/// sorted roots, so `holger/` shadowed the manifests of the worktree actually
/// being analysed — the analysis silently described a DIFFERENT BRANCH. It also
/// invented a package (`zip-core`), the only precision loss observed anywhere.
///
/// Following the path deps instead reaches exactly the repos that are really in
/// the build, in an order that puts the subject first. Build time is the same
/// (~200 ms).
pub fn path_dep_repo_roots(root: &Path) -> Vec<PathBuf> {
let root = root.canonicalize().unwrap_or_else(|_| root.to_path_buf());
let mut known: Vec<PathBuf> = vec![root.clone()];
let mut seen: BTreeSet<PathBuf> = [root.clone()].into_iter().collect();
let mut frontier = vec![root];
while let Some(dir) = frontier.pop() {
for r in repos_referenced_from(&dir) {
if seen.insert(r.clone()) {
known.push(r.clone());
frontier.push(r);
}
}
}
known
}
/// The repo roots named by `path = "..."` in any manifest under `scan`.
fn repos_referenced_from(scan: &Path) -> Vec<PathBuf> {
let Ok(manifests) = crate::parse::walk_cargo_tomls(scan) else { return Vec::new() };
let mut out: BTreeSet<PathBuf> = BTreeSet::new();
for m in manifests {
let Ok(text) = std::fs::read_to_string(&m) else { continue };
let Ok(doc) = text.parse::<toml::Table>().map(toml::Value::Table) else { continue };
let Some(dir) = m.parent() else { continue };
let mut paths = Vec::new();
collect_path_values(&doc, &mut paths);
for p in paths {
let Ok(abs) = dir.join(&p).canonicalize() else { continue };
if abs.starts_with(scan) {
continue;
}
if let Some(r) = enclosing_repo_root(&abs) {
out.insert(r);
}
}
}
out.into_iter().collect()
}
fn collect_path_values(v: &toml::Value, out: &mut Vec<String>) {
match v {
toml::Value::Table(t) => {
for (k, val) in t {
if k == "path" {
if let Some(s) = val.as_str() {
out.push(s.to_string());
}
} else {
collect_path_values(val, out);
}
}
}
toml::Value::Array(a) => a.iter().for_each(|e| collect_path_values(e, out)),
_ => {}
}
}
/// Walk up from a package directory to the enclosing REPO root (the topmost
/// ancestor that still has a `Cargo.toml`, or a `.git` entry).
fn enclosing_repo_root(pkg_dir: &Path) -> Option<PathBuf> {
let mut best: Option<PathBuf> = None;
let mut cur = Some(pkg_dir);
while let Some(d) = cur {
if d.join(".git").exists() {
return Some(d.to_path_buf());
}
if d.join("Cargo.toml").is_file() {
best = Some(d.to_path_buf());
}
cur = d.parent();
}
best
}
/// **The whole world a repo actually builds against**: itself plus every repo it
/// reaches by a `path` dependency, plus every locked registry crate.
///
/// This is the entry point a real closure needs. `root` is scanned FIRST so its
/// own manifests win over any other worktree of the same repo — see
/// [`path_dep_repo_roots`] for the measured cost of getting that wrong.
pub fn universe_for_constellation(
root: &Path,
lock_from: &Path,
) -> Result<(Universe, RegistryLoad), ParseError> {
let roots = path_dep_repo_roots(root);
let names: Vec<String> = roots
.iter()
.map(|p| p.file_name().unwrap_or_default().to_string_lossy().to_string())
.collect();
let pairs: Vec<(&str, &Path)> =
names.iter().map(String::as_str).zip(roots.iter().map(PathBuf::as_path)).collect();
universe_from_lock(&pairs, &lock_from.join("Cargo.lock"))
}
/// **The id of a package by name**, when exactly one version is locked.
///
/// Returns `Err` naming the candidates when several are — a caller that picked
/// one arbitrarily would reintroduce the guess this module removed.
pub fn id_for(universe: &Universe, name: &str) -> Result<String, Vec<String>> {
let hits: Vec<String> =
universe.names().filter(|id| name_of(id) == name).cloned().collect();
match hits.len() {
1 => Ok(hits.into_iter().next().expect("len 1")),
_ => Err(hits),
}
}
/// The package NAMES in a resolution — what a human and the `cargo tree` oracle
/// both speak.
pub fn names_of(ids: &BTreeSet<String>) -> BTreeSet<String> {
ids.iter().map(|i| name_of(i).to_string()).collect()
}
/// Every `feature_dep_edges` row in the universe.
pub fn rows_of(universe: &Universe) -> Vec<crate::facts::FeatureDepEdgeRow> {
let mut rows: Vec<_> = universe.packages().flat_map(PackageFacts::edges).collect();
rows.sort();
rows.dedup();
rows
}