src/mimir_lens/identity.rs
//! **The ONE symbol-identity primitive of the CPG.**
//!
//! Every name-matched join in Mímir used to invent its own answer to "which
//! definition does this callee mean?", and each invented a DIFFERENT one:
//!
//! * the v1 test-coverage resolver (`testcov::resolve_edges`, gone with Mímir v2)
//! keyed definitions on the bare `item_name`
//! and looked them up with the WHOLE `callee_ident` — two different alphabets,
//! so no qualified callee could ever match (59,028 of 279,086 live edges, 21.2%,
//! silently discarded).
//! * [`super::trust`] and [`super::data_reach`] keyed graph NODES on
//! `(repo, leaf(ident))`, collapsing every same-named fn in a repo into one node
//! — `facett::new` merged 300 distinct functions, so an impure hop in any one of
//! them tainted the callees of all 300.
//! * [`super::name_collision`] applied `leaf()` to the callee and reported the
//! resulting ambiguity as the graph's soundness headline — measuring a matcher
//! none of the above actually ran.
//!
//! This module is the single answer. It is a *scoping* fix, not a query-time
//! filter: the identity is computed once, at the point where a name becomes a
//! graph node, and every lens keys on the same thing.
//!
//! # The rule: longest matching suffix, within the repo
//!
//! A definition's identity is its `fqn` = `<module_path>::<item_name>`, and
//! `module_path` already carries crate + module. `syn` writes a callee exactly as
//! the source spells it, so a callee is some SUFFIX of the definition it means
//! (`Sha256Hasher::new` for `nornir_hash::Sha256Hasher::new`). Resolving on the
//! longest suffix that matches a scanned definition therefore uses every bit of
//! qualification the source gave, and no more.
//!
//! Measured on the live nordisk warehouse, over the 59,028 qualified call edges:
//!
//! | resolver | resolved | targets | fan-out |
//! |---------------------------------|----------|-----------|---------|
//! | whole ident vs bare `item_name` | 0 | 0 | — |
//! | naive `leaf()` | 41,678 | 3,155,451 | 75.71× |
//! | longest suffix (this) | 41,678 | 1,962,443 | 47.09× |
//!
//! # Why the key is never COARSER than the leaf
//!
//! [`SymbolIndex::node_key`] returns the full `fqn` when the ident names exactly
//! one definition, the matched suffix when it names several, and the ident as
//! written when it names none. All three are suffix-extensions of `leaf(ident)`,
//! so the keying is a strict REFINEMENT of the old `(repo, leaf)` space: nodes may
//! split, never merge. Two idents with different leaves can never collide on one
//! key. That property is what makes swapping the key safe for the trust semiring
//! and the reverse-reach BFS alike, and it is asserted in
//! `node_key_is_always_a_refinement_of_the_leaf`.
//!
//! Scope is always the repo. `syn` call edges are overwhelmingly intra-repo, and
//! attributing a rare cross-repo callee to the caller's repo FRAGMENTS rather than
//! merges — the safe direction for a taint walk.
use std::collections::{BTreeMap, BTreeSet};
use super::rows::{SymbolFact, Table};
/// The bare function name — the last `::` segment. The coarsest possible identity,
/// and the one this module exists to stop using as a graph key.
pub fn leaf(path: &str) -> &str {
path.rsplit("::").next().unwrap_or(path).trim()
}
/// What a callee ident turned out to name.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Resolved<'a> {
/// Exactly one scanned definition — a true identity.
One(&'a str),
/// Several definitions share the longest suffix the ident spells. The
/// ambiguity belongs to the source (`syn` wrote no more), not to the resolver.
Many(&'a [String]),
/// No scanned definition matches — an external crate, a macro expansion, or a
/// method on a foreign type. Not part of the workspace's own graph.
None,
}
/// **Every `::`-suffix of every scanned definition, per repo.**
///
/// `foo::bar::run` is indexed under `run`, `bar::run` and `foo::bar::run`, so the
/// longest suffix a callee spells is the most specific binding available.
#[derive(Debug, Default, Clone)]
pub struct SymbolIndex {
by_repo: BTreeMap<String, BTreeMap<String, Vec<String>>>,
}
/// The item kinds that carry executable behaviour — the callable surface a call
/// edge can land on. Kept here so the three lenses cannot drift apart on it.
pub const CALLABLE_KINDS: &[&str] = &["fn", "method"];
impl SymbolIndex {
/// Build from parsed [`SymbolFact`] rows (any mix of repos).
pub fn from_facts(symbols: &[SymbolFact]) -> Self {
let mut idx = SymbolIndex::default();
for s in symbols
.iter()
.filter(|s| CALLABLE_KINDS.contains(&s.item_kind.as_str()))
{
idx.insert(&s.repo, &s.fqn());
}
idx
}
/// Build straight off a `symbol_facts` [`Table`] — the shape the lenses that
/// fold cursors (rather than typed rows) already hold.
pub fn from_table(t: &Table) -> Self {
let c = t.cursor(&["repo", "module_path", "item_kind", "item_name"]);
let mut idx = SymbolIndex::default();
for r in c.rows() {
if !CALLABLE_KINDS.contains(&c.get(r, 2)) {
continue;
}
let name = c.get(r, 3);
if name.is_empty() {
continue;
}
let module = c.get(r, 1);
let fqn = if module.is_empty() {
name.to_string()
} else {
format!("{module}::{name}")
};
idx.insert(c.get(r, 0), &fqn);
}
idx
}
fn insert(&mut self, repo: &str, fqn: &str) {
let per = self.by_repo.entry(repo.to_string()).or_default();
per.entry(fqn.to_string())
.or_default()
.push(fqn.to_string());
let mut rest = fqn;
while let Some(i) = rest.find("::") {
rest = &rest[i + 2..];
per.entry(rest.to_string())
.or_default()
.push(fqn.to_string());
}
}
/// Are there any definitions at all for `repo`? An unscanned repo must not be
/// mistaken for "every callee is external".
pub fn has_repo(&self, repo: &str) -> bool {
self.by_repo.contains_key(repo)
}
/// **Resolve `ident` within `repo` by longest matching suffix.**
pub fn resolve<'a>(&'a self, repo: &str, ident: &str) -> Resolved<'a> {
let Some(per) = self.by_repo.get(repo) else {
return Resolved::None;
};
let mut probe = ident.trim();
loop {
if let Some(hits) = per.get(probe) {
return match hits.len() {
1 => Resolved::One(hits[0].as_str()),
_ => Resolved::Many(hits.as_slice()),
};
}
match probe.find("::") {
Some(i) => probe = &probe[i + 2..],
None => return Resolved::None,
}
}
}
/// **The canonical graph-node name for `ident` in `repo`.**
///
/// The full `fqn` when the ident names one definition; the longest matching
/// suffix when it names several (all we honestly know); the ident as written
/// when it names none. Always a suffix-extension of `leaf(ident)` — see the
/// module doc on why that refinement property matters.
pub fn node_key(&self, repo: &str, ident: &str) -> String {
let ident = ident.trim();
match self.resolve(repo, ident) {
Resolved::One(f) => f.to_string(),
Resolved::Many(_) => {
// The matched suffix is the most specific thing that bound.
let per = match self.by_repo.get(repo) {
Some(p) => p,
None => return ident.to_string(),
};
let mut probe = ident;
loop {
if per.contains_key(probe) {
return probe.to_string();
}
match probe.find("::") {
Some(i) => probe = &probe[i + 2..],
None => return ident.to_string(),
}
}
}
Resolved::None => ident.to_string(),
}
}
/// Distinct definitions indexed for `repo` — used by the guards to prove the
/// index was actually fed (an empty index resolves everything to `None`, which
/// would look exactly like "all callees are external").
pub fn definitions(&self, repo: &str) -> usize {
self.by_repo
.get(repo)
.map(|p| p.values().flatten().collect::<BTreeSet<_>>().len())
.unwrap_or(0)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn idx(defs: &[(&str, &str)]) -> SymbolIndex {
let mut i = SymbolIndex::default();
for (repo, fqn) in defs {
i.insert(repo, fqn);
}
i
}
/// **Red-when-reverted core.** Qualification picks the definition it names;
/// a bare ident stays honestly ambiguous; an unknown ident resolves to nothing.
#[test]
fn longest_suffix_binds_qualification_and_keeps_bare_idents_ambiguous() {
let i = idx(&[
("a", "a::m1::run"),
("a", "a::m2::run"),
("a", "a::m1::solo"),
]);
assert_eq!(i.resolve("a", "a::m1::run"), Resolved::One("a::m1::run"));
assert_eq!(
i.resolve("a", "m1::run"),
Resolved::One("a::m1::run"),
"a partial suffix binds"
);
assert_eq!(
i.resolve("a", "solo"),
Resolved::One("a::m1::solo"),
"a unique leaf binds"
);
match i.resolve("a", "run") {
Resolved::Many(v) => assert_eq!(v.len(), 2, "a bare ambiguous leaf names both"),
other => panic!("expected Many, got {other:?}"),
}
assert_eq!(
i.resolve("a", "std::fs::read"),
Resolved::None,
"an external fn is not ours"
);
assert_eq!(
i.resolve("b", "run"),
Resolved::None,
"another repo's index is not consulted"
);
}
/// **The property the whole swap rests on: the node key REFINES the leaf key.**
/// Nodes may split, never merge — so nothing that was distinct under
/// `(repo, leaf)` becomes merged under `(repo, node_key)`. Drop the
/// suffix-extension rule (e.g. return `leaf(ident)` from `node_key`) and the
/// strictness assert below stops holding for the qualified case.
#[test]
fn node_key_is_always_a_refinement_of_the_leaf() {
let i = idx(&[
("a", "a::m1::run"),
("a", "a::m2::run"),
("a", "a::m1::solo"),
]);
for ident in [
"a::m1::run",
"m2::run",
"run",
"solo",
"std::fs::read",
"wholly_unknown",
] {
let key = i.node_key("a", ident);
assert!(
key.ends_with(leaf(ident)),
"node_key({ident}) = {key} must extend the leaf {}",
leaf(ident)
);
}
// The qualified idents SPLIT what the leaf merged.
assert_ne!(i.node_key("a", "a::m1::run"), i.node_key("a", "a::m2::run"));
// The genuinely ambiguous bare ident stays ONE node — we know no better.
assert_eq!(i.node_key("a", "run"), "run");
// An external ident keeps its full path rather than collapsing onto a
// same-leafed local fn.
assert_eq!(i.node_key("a", "std::fs::read"), "std::fs::read");
}
/// An unfed index must resolve to `None`, and `has_repo`/`definitions` must say
/// so — an empty index that silently answered "external" for every callee would
/// read as a clean graph rather than a missing feed.
#[test]
fn an_unfed_index_is_distinguishable_from_an_all_external_graph() {
let i = SymbolIndex::default();
assert_eq!(i.resolve("a", "run"), Resolved::None);
assert!(
!i.has_repo("a"),
"an unfed index must not claim to know the repo"
);
assert_eq!(i.definitions("a"), 0);
let fed = idx(&[("a", "a::m::run")]);
assert!(fed.has_repo("a"));
assert_eq!(fed.definitions("a"), 1);
}
}