src/mimir_lens/symbol_identity.rs
//! **Lens — `Mimir.SymbolIdentity`: is the node id actually an identity?**
//!
//! Every claim Mímir makes — a caller count, a reachability set, "these two
//! symbols are the same" — rests on one assumption: that a node id (the moniker
//! rustc's items are filed under) identifies exactly one thing. The code room
//! folds every open row of an id into ONE node; where the rows do not agree it
//! keeps the record ([`KeyFact`], `Room::duplicate_keys`). This lens reads that
//! record and keeps its two causes apart, because they have different owners:
//!
//! 1. **A key repeated inside ONE compiled unit — OURS.** The dump itself wrote
//! the same id for more than one item: the moniker scheme does not tell them
//! apart (two impls that print the same self type, macro-generated twins).
//! Every edge onto that id is ambiguous. Reported as
//! [`Cause::RepeatedKeyInUnit`]; the cure is in the driver's moniker rules.
//! 2. **One id, several places — OURS.** Several compiled units write the same
//! id for items that lie in DIFFERENT files: two items, one id (a package's
//! lib root and the root of its bin target of the same name). Reported as
//! [`Cause::OneIdSeveralPlaces`].
//! 3. **Units that disagree about one id.** A crate's lib and its test harness
//! (or two feature sets) compile the same item with different payloads
//! (`cfg(test)` bodies, a type that changes with a feature). The id still
//! names one item; what differs is the configuration. Reported as
//! [`Cause::UnitsDisagree`], not repaired.
//!
//! ANTI-SILENT-EMPTY: a room without definitions must never read as "the
//! substrate is sound". It reports a MISSING FEED via [`evidence_note`] and a
//! [`Verdict::Unknown`].
use std::collections::{BTreeMap, BTreeSet};
use serde::{Deserialize, Serialize};
use super::sources::{Feed, evidence_note};
/// Why one id carries more than one definition.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Cause {
/// One dump wrote the id for several items of ONE compiled unit.
RepeatedKeyInUnit,
/// Several units write the id for items in different files.
OneIdSeveralPlaces,
/// Several compiled units describe the id with different payloads.
UnitsDisagree,
}
impl Cause {
pub fn label(self) -> &'static str {
match self {
Cause::RepeatedKeyInUnit => "repeated key in one unit (the moniker does not tell the items apart)",
Cause::OneIdSeveralPlaces => "one id, several places (units write it for items in different files)",
Cause::UnitsDisagree => "units disagree (one item, compiled differently by several units)",
}
}
/// Is this one OUR producer's defect (an id that names several items)?
pub fn ours(self) -> bool {
matches!(self, Cause::RepeatedKeyInUnit | Cause::OneIdSeveralPlaces)
}
}
/// The lens's one-word answer.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Verdict {
/// The room holds no definition of the scope: nothing was checked.
#[default]
Unknown,
/// One definition per id.
Sound,
/// Ids are unique; some items are compiled differently by several units.
UnitsDisagreeOnly,
/// Some id names more than one item.
Unsound,
}
impl Verdict {
pub fn label(self) -> &'static str {
match self {
Verdict::Unknown => "unknown — the room holds no definition of this scope",
Verdict::Sound => "sound — one definition per id",
Verdict::UnitsDisagreeOnly => "ids are unique — some items differ between compiled units",
Verdict::Unsound => "UNSOUND — an id names more than one item",
}
}
}
/// One ambiguous id, with enough to go look at it.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct AmbiguousSymbol {
pub repo: String,
/// The node id (moniker).
pub symbol: String,
pub kind: String,
pub cause: Cause,
/// Open rows describing the id.
pub definitions: usize,
/// Distinct files its spans lie in.
pub files: usize,
/// Its positions and the units that describe it.
pub sites: Vec<String>,
}
/// The whole reading.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct SymbolIdentityReport {
pub worst: Vec<AmbiguousSymbol>,
/// Distinct ids with a definition in the scope.
pub symbols_seen: usize,
pub ambiguous_symbols: usize,
/// Open definition rows (one per id, plus the extra rows of the merged ones).
pub definition_rows: usize,
/// Of those, the rows under an ambiguous id.
pub rows_under_ambiguous: usize,
pub by_cause: BTreeMap<String, usize>,
/// Repos that hold an id naming more than one item.
pub repos_with_repeated_keys: Vec<String>,
pub verdict: Verdict,
pub feeds: Vec<Feed>,
pub evidence_note: String,
}
impl SymbolIdentityReport {
/// The share of definition rows that sit under an ambiguous id.
pub fn doubt_ratio(&self) -> f64 {
if self.definition_rows == 0 {
return 0.0;
}
self.rows_under_ambiguous as f64 / self.definition_rows as f64
}
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"kind": "symbol_identity",
"verdict": self.verdict,
"verdict_label": Verdict::label(self.verdict),
"symbols_seen": self.symbols_seen,
"ambiguous_symbols": self.ambiguous_symbols,
"definition_rows": self.definition_rows,
"rows_under_ambiguous": self.rows_under_ambiguous,
"doubt_ratio": self.doubt_ratio(),
"by_cause": self.by_cause,
"repos_with_repeated_keys": self.repos_with_repeated_keys,
"evidence_note": self.evidence_note,
"feeds": self.feeds,
"worst": self.worst.iter().map(|a| serde_json::json!({
"repo": a.repo,
"symbol": a.symbol,
"kind": a.kind,
"cause": a.cause,
"cause_label": a.cause.label(),
"definitions": a.definitions,
"files": a.files,
"sites": a.sites,
})).collect::<Vec<_>>(),
})
}
}
/// One node id the fold merged, as the room records it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct KeyFact {
pub repo: String,
pub symbol: String,
pub kind: String,
/// Open rows describing the id.
pub rows: usize,
/// Distinct payloads among them.
pub distinct_payloads: usize,
/// Rows the dump marked as a key repeated inside one unit.
pub key_dup_rows: usize,
/// Distinct files the id's spans lie in.
pub files: usize,
pub sites: Vec<String>,
}
fn classify(k: &KeyFact) -> Cause {
if k.key_dup_rows > 0 {
Cause::RepeatedKeyInUnit
} else if k.files > 1 {
Cause::OneIdSeveralPlaces
} else {
Cause::UnitsDisagree
}
}
/// **Check the one-definition-per-id invariant.** `ids` is the number of ids
/// with a definition in the scope; `keys` the merged ones among them.
pub fn analyze(ids: usize, keys: &[KeyFact], feeds: Vec<Feed>, repo: &str, limit: usize) -> SymbolIdentityReport {
let want_all = repo.is_empty() || repo == "all";
let mut worst: Vec<AmbiguousSymbol> = Vec::new();
let mut by_cause: BTreeMap<String, usize> = BTreeMap::new();
let mut rows_under_ambiguous = 0usize;
let mut extra_rows = 0usize;
let mut repeated: BTreeSet<String> = BTreeSet::new();
let mut ours = 0usize;
for k in keys {
if !want_all && k.repo != repo {
continue;
}
let cause = classify(k);
rows_under_ambiguous += k.rows;
extra_rows += k.rows.saturating_sub(1);
*by_cause.entry(cause.label().to_string()).or_default() += 1;
if cause.ours() {
ours += 1;
repeated.insert(k.repo.clone());
}
worst.push(AmbiguousSymbol { repo: k.repo.clone(), symbol: k.symbol.clone(), kind: k.kind.clone(), cause, definitions: k.rows, files: k.files, sites: k.sites.clone() });
}
let ambiguous_symbols = worst.len();
worst.sort_by(|a, b| {
b.cause
.ours()
.cmp(&a.cause.ours())
.then_with(|| b.definitions.cmp(&a.definitions))
.then_with(|| a.repo.cmp(&b.repo))
.then_with(|| a.symbol.cmp(&b.symbol))
});
worst.truncate(limit);
let unfed = ids == 0;
let verdict = if unfed {
Verdict::Unknown
} else if ambiguous_symbols == 0 {
Verdict::Sound
} else if ours == 0 {
Verdict::UnitsDisagreeOnly
} else {
Verdict::Unsound
};
let mut note = evidence_note(&feeds, "symbol identity");
if unfed {
note.push_str(
" The room holds NO definition of this scope, so the one-definition-per-id invariant every \
caller count and reachability answer rests on is UNKNOWN — not satisfied.",
);
} else if !repeated.is_empty() {
note.push_str(&format!(
" {} repo(s) hold ids that name more than one item ({}): every edge onto such an \
id is ambiguous until the driver's moniker rules tell the items apart.",
repeated.len(),
repeated.iter().cloned().collect::<Vec<_>>().join(", ")
));
}
SymbolIdentityReport {
worst,
symbols_seen: ids,
ambiguous_symbols,
definition_rows: ids + extra_rows,
rows_under_ambiguous,
by_cause,
repos_with_repeated_keys: repeated.into_iter().collect(),
verdict,
feeds,
evidence_note: note,
}
}
#[cfg(test)]
mod tests {
use super::*;
fn key(repo: &str, symbol: &str, rows: usize, payloads: usize, dup: usize) -> KeyFact {
KeyFact { repo: repo.into(), symbol: symbol.into(), kind: "fn".into(), rows, distinct_payloads: payloads, key_dup_rows: dup, files: 1, sites: vec!["src/a.rs:3".into()] }
}
fn feeds(rows: usize) -> Vec<Feed> {
vec![Feed { table: "code_nodes".into(), rows, root: "code room".into(), missing: rows == 0 }]
}
/// **Red-when-reverted core.** One id written twice by ONE unit is OUR defect
/// and makes the substrate unsound; two units compiling one item differently
/// does not. Collapse the two causes and either a harmless `cfg(test)` body
/// reads as a broken moniker scheme, or a broken moniker scheme reads as
/// configuration noise.
#[test]
fn a_key_repeated_in_one_unit_is_unsound_and_units_disagreeing_is_not() {
let disagree = [key("a", "a helper().", 2, 2, 0)];
let r = analyze(10, &disagree, feeds(10), "", 20);
assert_eq!(r.verdict, Verdict::UnitsDisagreeOnly);
assert_eq!(r.worst[0].cause, Cause::UnitsDisagree);
assert!(r.repos_with_repeated_keys.is_empty());
let repeated = [key("a", "a helper().", 2, 2, 0), key("a", "a impl#[T]new().", 3, 2, 2)];
let r = analyze(10, &repeated, feeds(10), "", 20);
assert_eq!(r.verdict, Verdict::Unsound);
assert_eq!(r.worst[0].cause, Cause::RepeatedKeyInUnit, "ours ranks first");
assert_eq!(r.repos_with_repeated_keys, vec!["a".to_string()]);
assert!(r.evidence_note.contains("moniker rules"), "{}", r.evidence_note);
assert_eq!((r.ambiguous_symbols, r.rows_under_ambiguous, r.definition_rows), (2, 5, 13));
assert!((r.doubt_ratio() - 5.0 / 13.0).abs() < 1e-12);
}
/// A lib root and the root of the package's same-named bin: two files, one id.
#[test]
fn one_id_in_two_files_is_two_items_not_a_configuration_difference() {
let mut k = key("a", "a crate/", 3, 2, 0);
k.files = 2;
let r = analyze(10, &[k], feeds(10), "", 20);
assert_eq!((r.verdict, r.worst[0].cause), (Verdict::Unsound, Cause::OneIdSeveralPlaces));
assert_eq!(r.repos_with_repeated_keys, vec!["a".to_string()]);
}
#[test]
fn no_merged_id_is_sound() {
let r = analyze(42, &[], feeds(42), "", 20);
assert_eq!(r.verdict, Verdict::Sound);
assert_eq!((r.symbols_seen, r.definition_rows, r.doubt_ratio()), (42, 42, 0.0));
}
#[test]
fn the_repo_filter_scopes_the_verdict() {
let keys = [key("a", "a x().", 2, 1, 1), key("b", "b y().", 2, 2, 0)];
assert_eq!(analyze(5, &keys, feeds(5), "b", 20).verdict, Verdict::UnitsDisagreeOnly);
assert_eq!(analyze(5, &keys, feeds(5), "a", 20).verdict, Verdict::Unsound);
assert_eq!(analyze(5, &keys, feeds(5), "all", 20).ambiguous_symbols, 2);
}
/// ANTI-SILENT-EMPTY: no definition in scope is UNKNOWN, never sound.
#[test]
fn an_empty_room_is_unknown_not_sound() {
let r = analyze(0, &[], feeds(0), "", 20);
assert_eq!(r.verdict, Verdict::Unknown);
assert!(r.evidence_note.contains("MISSING FEEDS"), "{}", r.evidence_note);
assert!(r.evidence_note.contains("UNKNOWN"), "{}", r.evidence_note);
}
}