crates/mimir-binary/src/lib.rs
//! # mimir-binary — the binary layer of the Mímir code graph (plan §1, lane 9)
//!
//! One linked artifact → `code_nodes` / `code_edges` / `code_symbols` rows on
//! the SAME node ids (SCIP monikers) as the source layer (mimir-driver's dump).
//!
//! ```text
//! artifact ──symtab──► symbols ──v0 decode──► (crate name, StableCrateId, path tree)
//! │ │
//! └──DWARF CU names / deps-dir rlibs / driver ────┴──► package@version
//! │
//! mimir_schema::moniker ◄────────┘ candidates → source dump lookup
//! ```
//!
//! Per defined symbol, in order:
//! 1. **exact symbol**: the driver's `.symbols.arrow` (rustc's own symbol name
//! per item) has it → that moniker. Only an artifact built BY the driver
//! compile (`cargo mimir-dump --build`) hits here.
//! 2. **v0 path**: decode, resolve the root crate (see [`crates`]), build the
//! descriptor-chain candidates the driver's moniker rules allow (a `t`
//! segment is a module or a type, a `v` segment with children is a fn or a
//! const, an impl's self type is the bare ADT name for a generic impl or the
//! printed type for a concrete one …), and look them up in the dump:
//! exact → loose (impl slots cut to their head: `&T` ≡ `&u32`) → blanket
//! (impl self slot wildcarded). More than one hit at a level is COUNTED as
//! an ambiguity (exact level: the first by candidate priority is taken;
//! loose levels: none is taken).
//! 3. the matched item is generic (it, or its impl / trait / fn scope, owns a
//! `generic` node; trait items are generic over Self) → the symbol is a
//! `mono_instance` node (id = [`mimir_schema::moniker::mono_instance`]) with
//! `INSTANCE_OF` → the generic item. Closures / shims are attributed to the
//! item (or instance) that owns them (`code_symbols.role`).
//! 4. no hit → a `binary_only` node on the first candidate moniker.
//!
//! Undefined symbols are imports: the FFI border. A source `ffi` node with
//! that link name (driver symbol table first, else by name) becomes `both`;
//! none → a `binary_only` `ffi_import` node under the pseudo package `extern`
//! (version = the ELF symbol version, `-` when unversioned).
//!
//! Provenance is NOT written here (plan L9-dec, one writer per table): the
//! binary layer is its own producer stream — its rows are the symbols, the
//! nodes only it knows (mono instances, ffi imports, unmatched symbols) and
//! INSTANCE_OF edges; it never re-emits a source node. `source_only` /
//! `binary_only` / `both` is DERIVED at read time by joining the two streams
//! on the moniker ([`mimir_schema::derive_provenance`], [`BinaryIndex`]): a
//! source item with a linked twin (its own symbol, or for a generic item ≥1
//! linked instance) is `both`; mono instances and unmatched symbols are
//! `binary_only`; the rest stays `source_only` (inlined, dead, cfg'd out, not
//! instantiated).
//!
//! Legacy (`_ZN`) symbols: hash-free paths without `<`/`{` are matched by
//! crate NAME only (legacy hashes carry no recoverable crate id); the rest is
//! counted `legacy_unsupported`.
pub mod crates;
pub mod elf;
pub mod source;
pub mod v0;
use std::collections::{BTreeMap, HashMap, HashSet};
use std::path::{Path, PathBuf};
use std::time::Instant;
use mimir_schema::moniker::{self, Suffix};
use mimir_schema::{kind, role, EdgeKind, EdgeRow, Level, NodeRow, Origin, Provenance, SymbolRow};
use serde::Serialize;
use crate::crates::{CrateIdent, Resolver, Via};
use crate::source::SourceDump;
use crate::v0::{GenericArg, Path as VPath, Type};
/// What to join.
#[derive(Debug, Clone, Default)]
pub struct Options {
/// the linked artifact
pub binary: PathBuf,
/// a mimir-driver dump dir (`*.nodes.arrow`, `*.symbols.arrow`, `*.stats.json`)
pub dump: PathBuf,
/// more dump dirs read into the same source half — e.g. the toolchain's
/// std / core / alloc dump (`cargo mimir-dump --std`)
pub extra_dumps: Vec<PathBuf>,
/// cargo's `target/<profile>/deps` of the build that linked `binary`
pub deps_dir: Option<PathBuf>,
/// the workspace manifest (for `cargo metadata`: root file → package@version)
pub manifest: Option<PathBuf>,
/// pre-loaded cargo metadata packages (instead of running cargo)
pub packages: Option<Vec<crates::MetaPackage>>,
/// a toolchain sysroot whose rlibs (std, core, and std's private deps
/// such as gimli / addr2line / miniz_oxide) name their crate ids
pub sysroot: Option<PathBuf>,
/// skip step 1 (the driver's exact symbol names): forces every symbol
/// through the v0 path — the oracle test compares the two
pub ignore_driver_symbols: bool,
pub sha: Option<String>,
}
/// The rows + the ledger.
#[derive(Debug, Default)]
pub struct Output {
pub nodes: Vec<NodeRow>,
pub edges: Vec<EdgeRow>,
pub symbols: Vec<SymbolRow>,
pub ledger: Ledger,
}
/// Counts for the ingest ledger / the report. Every symbol lands in exactly
/// one bucket of each breakdown; nothing is dropped silently.
#[derive(Debug, Default, Clone, Serialize)]
pub struct Ledger {
pub binary: String,
pub file_size: u64,
pub text_size: u64,
pub has_dwarf: bool,
pub symbol_table: String,
/// crate ids known before the walk, by source (cu / rlib / driver)
pub crate_ids_known: BTreeMap<String, usize>,
pub crate_id_conflicts: Vec<String>,
pub cu_crates: usize,
pub deps_rlibs: usize,
pub sysroot_rlibs: usize,
pub defined: usize,
pub defined_bytes: u64,
pub undefined: usize,
/// defined symbols by mangling: v0 / legacy / other (C, asm, linker)
pub by_mangling: BTreeMap<String, usize>,
pub decode_errors: BTreeMap<String, usize>,
pub decode_error_samples: Vec<String>,
/// defined Rust symbols by how their crate was resolved
pub crate_via: BTreeMap<String, usize>,
/// crate names that could not be resolved to one package@version
pub ambiguous_crates: BTreeMap<String, usize>,
pub unknown_crates: BTreeMap<String, usize>,
/// defined symbols by match level: exact_symbol / exact / loose / blanket /
/// unmatched / no_moniker
pub matched: BTreeMap<String, usize>,
pub ambiguous_exact: usize,
pub ambiguous_loose: usize,
pub ambiguity_samples: Vec<String>,
/// unmatched symbols of local / library crates (the ones a source twin
/// was expected for), then of toolchain crates
pub unmatched_samples: Vec<String>,
pub unmatched_lang_samples: Vec<String>,
/// defined Rust symbols with a resolved crate, by the crate's origin
/// (local / library / lang): symbols, bytes, matched to a source node
pub by_origin: BTreeMap<String, OriginCount>,
/// matched symbols by role: item / mono / closure / shim
pub roles: BTreeMap<String, usize>,
/// a symbol with generic args matched a NON-generic source item
pub instance_of_nongeneric: usize,
/// a symbol WITHOUT generic args matched an item in a generic scope (an
/// inherent impl merged with a generic sibling block, or an instance whose
/// args are all defaults — the two are indistinguishable): taken as the item
pub generic_item_without_args: usize,
pub imports: BTreeMap<String, usize>,
/// source nodes the artifact links (derived `both`; never re-emitted)
pub nodes_both: usize,
/// nodes the binary stream owns (mono_instance, ffi_import, unmatched)
pub nodes_binary_only: usize,
pub nodes_mono_instance: usize,
pub edges_instance_of: usize,
/// INSTANCE_OF edges whose generic item is not in the source dump
pub instance_of_dangling: usize,
/// defined symbols that got a moniker (crate resolved), and that matched
/// a source node, as % of all defined / of defined Rust symbols
pub pct_moniker_of_defined: f64,
pub pct_moniker_of_rust: f64,
pub pct_source_match_of_rust: f64,
/// symbol-bearing source nodes (fn / method / static / ffi, defined_here)
/// of the crates present in the artifact, and how many stay source_only
pub source_items_in_linked_crates: usize,
pub source_only_items: usize,
pub source_only_samples: Vec<String>,
/// bytes per crate (`package@version`, `?` = unresolved, `-` = not Rust)
pub bytes_by_crate: Vec<(String, u64, usize)>,
pub ms_read: u128,
pub ms_join: u128,
}
#[derive(Debug, Default, Clone, Serialize)]
pub struct OriginCount {
pub symbols: usize,
pub bytes: u64,
pub matched: usize,
}
const SAMPLES: usize = 25;
fn sample(v: &mut Vec<String>, s: String) {
if v.len() < SAMPLES {
v.push(s);
}
}
// ------------------------------------------------------------ flattening
#[derive(Debug, Clone, PartialEq, Eq)]
enum Seg {
/// `t` namespace: a module, or a type when under a fn
T(String),
/// `t` that IS a type (the trait of a `<T as Trait>` qualification)
Ty(String),
/// `v` namespace: fn, or const / static
V(String),
Impl { selves: Vec<String>, traits: Option<Vec<String>> },
Meta(String),
/// a closure (`{closure#n}`, n = its DefPath disambiguator) or a
/// synthetic coroutine body
Closure(Option<u64>),
Shim,
}
#[derive(Debug, Clone)]
struct Flat {
crate_name: String,
crate_id: u64,
segs: Vec<Seg>,
has_args: bool,
}
fn dis_name(name: &str, dis: u64) -> String {
if dis == 0 { name.to_string() } else { format!("{name}${dis}") }
}
fn non_lifetime(args: &[GenericArg]) -> Vec<&GenericArg> {
args.iter().filter(|a| !matches!(a, GenericArg::Lifetime)).collect()
}
fn flatten(p: &VPath) -> Result<Flat, &'static str> {
Ok(match p {
VPath::Crate { name, id } => Flat { crate_name: name.clone(), crate_id: *id, segs: Vec::new(), has_args: false },
VPath::Nested { ns, parent, name, dis } => {
let mut f = flatten(parent)?;
match ns {
't' => f.segs.push(Seg::T(dis_name(name, *dis))),
'v' => f.segs.push(Seg::V(dis_name(name, *dis))),
'C' => f.segs.push(Seg::Closure(Some(*dis))),
's' => f.segs.push(Seg::Closure(None)),
'S' => f.segs.push(Seg::Shim),
// anonymous const scopes: the driver's `$n:` meta descriptor
'K' | 'k' => f.segs.push(Seg::Meta(format!("${dis}"))),
// ctor / opaque type / nested static / global asm: transparent
'c' | 'i' | 'n' | 'a' => {}
_ => return Err("namespace"),
}
f
}
VPath::Generic { path, args } => {
let mut f = flatten(path)?;
f.has_args |= !non_lifetime(args).is_empty();
f
}
VPath::InherentImpl { parent, self_ty } => {
let mut f = flatten(parent)?;
let (selves, generic) = self_candidates(self_ty);
f.has_args |= generic;
f.segs.push(Seg::Impl { selves, traits: None });
f
}
VPath::TraitImpl { parent, self_ty, trait_ } => {
let mut f = flatten(parent)?;
let (selves, generic) = self_candidates(self_ty);
f.has_args |= generic;
f.segs.push(Seg::Impl { selves, traits: Some(trait_candidates(trait_, self_ty)) });
f
}
VPath::TraitDef { trait_, .. } => {
// `<T as Trait>::m`: an item of the trait, instantiated for Self
let base = match &**trait_ {
VPath::Generic { path, .. } => path,
other => other,
};
let mut f = flatten(base)?;
match f.segs.pop() {
Some(Seg::T(n)) => f.segs.push(Seg::Ty(n)),
_ => return Err("trait path"),
}
f.has_args = true;
f
}
})
}
/// Impl self-type spellings the driver may have written, most likely first,
/// and whether the binary's self type carries generic args (an instance of a
/// generic impl is possible).
fn self_candidates(t: &Type) -> (Vec<String>, bool) {
if let Type::Path(p) = t {
let (base, args) = match p {
VPath::Generic { path, args } => (&**path, non_lifetime(args)),
other => (other, Vec::new()),
};
if let VPath::Nested { ns: 't', name, dis, .. } = base {
let bare = dis_name(name, *dis);
return if args.is_empty() { (vec![bare], false) } else { (vec![bare, v0::print_type_short(t)], true) };
}
}
(vec![v0::print_type_short(t)], false)
}
/// Trait spellings: rust-analyzer's bare name, with its args (Self-typed args
/// written `Self`) when it has any beyond Self.
fn trait_candidates(trait_: &VPath, self_ty: &Type) -> Vec<String> {
let (base, args) = match trait_ {
VPath::Generic { path, args } => (&**path, non_lifetime(args)),
other => (other, Vec::new()),
};
let name = match base {
VPath::Nested { name, dis, .. } => dis_name(name, *dis),
_ => v0::print_path(base),
};
if args.is_empty() {
return vec![name];
}
let printed: Vec<String> = args
.iter()
.map(|a| match a {
GenericArg::Type(t) if t == self_ty => "Self".to_string(),
GenericArg::Type(t) => v0::print_type_short(t),
GenericArg::Const(c) => c.clone(),
GenericArg::Lifetime => String::new(),
})
.collect();
vec![format!("{name}<{}>", printed.join(", ")), name]
}
const MAX_CANDIDATES: usize = 64;
/// Descriptor-chain candidates for the item `segs` names (closures / shims
/// already stripped from the end), most likely first.
fn candidates(segs: &[Seg], is_data: bool) -> Vec<String> {
let mut acc: Vec<String> = vec![String::new()];
for (i, s) in segs.iter().enumerate() {
let last = i + 1 == segs.len();
let prev_is_fn = i > 0 && matches!(segs[i - 1], Seg::V(_));
let alts: Vec<String> = match s {
Seg::T(n) if last || prev_is_fn => vec![moniker::descriptor(Suffix::Type, n)],
Seg::T(n) => vec![moniker::descriptor(Suffix::Namespace, n), moniker::descriptor(Suffix::Type, n)],
Seg::Ty(n) => vec![moniker::descriptor(Suffix::Type, n)],
Seg::V(n) if last => vec![moniker::descriptor(if is_data { Suffix::Term } else { Suffix::Method }, n)],
Seg::V(n) if n == "_" || n.starts_with("_$") => vec![moniker::descriptor(Suffix::Term, n)],
Seg::V(n) => vec![moniker::descriptor(Suffix::Method, n), moniker::descriptor(Suffix::Term, n)],
Seg::Impl { selves, traits } => {
let mut v = Vec::new();
for sn in selves {
match traits {
None => v.push(moniker::impl_descriptor(sn, None)),
Some(ts) => {
for t in ts {
v.push(moniker::impl_descriptor(sn, Some(t)));
}
}
}
}
v
}
Seg::Meta(m) => vec![moniker::descriptor(Suffix::Meta, m)],
Seg::Closure(_) | Seg::Shim => vec![String::new()],
};
let mut next = Vec::with_capacity(acc.len() * alts.len());
'o: for a in &acc {
for b in &alts {
next.push(format!("{a}{b}"));
if next.len() >= MAX_CANDIDATES {
break 'o;
}
}
}
acc = next;
}
acc
}
/// Strip trailing closure / shim segments (→ role). A closure in the MIDDLE
/// (an item defined inside a closure) becomes the driver's `$n:` scope: v0's
/// `{closure#n}` is the closure's DefPath disambiguator, the same `n` the
/// driver writes. A shim or coroutine body in the middle is rejected (counted).
fn split_role(mut segs: Vec<Seg>) -> Result<(Vec<Seg>, &'static str), &'static str> {
let mut r = role::ITEM;
while let Some(last) = segs.last() {
match last {
Seg::Closure(_) => r = role::CLOSURE,
Seg::Shim => {
if r == role::ITEM {
r = role::SHIM;
}
}
_ => break,
}
segs.pop();
}
for s in segs.iter_mut() {
match s {
Seg::Closure(Some(n)) => *s = Seg::Meta(format!("${n}")),
Seg::Closure(None) | Seg::Shim => return Err("item nested in a shim / coroutine body"),
_ => {}
}
}
if segs.is_empty() {
return Err("crate-root symbol");
}
Ok((segs, r))
}
/// The item-level path (closures / shims stripped) for the instance key.
fn item_path(p: &VPath) -> &VPath {
match p {
VPath::Nested { ns: 'C' | 'S' | 's', parent, .. } => item_path(parent),
other => other,
}
}
// ------------------------------------------------------------ the join
enum Hit {
Exact(String),
ExactAmbiguous(String, usize),
Loose(String),
Blanket(String),
LooseAmbiguous(usize),
None,
}
fn lookup(src: &SourceDump, ident: &CrateIdent, cands: &[String]) -> Hit {
let ids: Vec<String> = cands.iter().map(|d| moniker::moniker(&ident.package, &ident.version, &format!("{}{d}", ident.prefix))).collect();
let mut hits: Vec<&String> = ids.iter().filter(|i| src.has(i)).collect();
hits.dedup();
match hits.len() {
1 => return Hit::Exact(hits[0].clone()),
n if n > 1 => return Hit::ExactAmbiguous(hits[0].clone(), n),
_ => {}
}
for blanket in [false, true] {
let mut found: Vec<&String> = Vec::new();
for d in cands {
if let Some(k) = source::loose_key(&format!("{}{d}", ident.prefix), blanket) {
for h in src.loose_hits(&ident.package, &ident.version, &k, blanket) {
if !found.contains(&h) {
found.push(h);
}
}
}
}
match found.len() {
0 => continue,
1 => return if blanket { Hit::Blanket(found[0].clone()) } else { Hit::Loose(found[0].clone()) },
n => return Hit::LooseAmbiguous(n),
}
}
Hit::None
}
struct Emit<'a> {
src: &'a SourceDump,
binary_name: String,
sha: Option<String>,
nodes: Vec<NodeRow>,
node_ids: HashSet<String>,
edges: Vec<EdgeRow>,
edge_ids: HashSet<(String, String)>,
symbols: Vec<SymbolRow>,
touched: HashSet<String>,
}
impl Emit<'_> {
/// A source node the artifact links: recorded, never re-emitted (the
/// provenance `both` is derived from the symbol / INSTANCE_OF rows).
fn both(&mut self, id: &str) {
self.touched.insert(id.to_string());
}
fn binary_only(&mut self, row: NodeRow) {
if self.node_ids.insert(row.id.clone()) {
self.nodes.push(row);
}
}
fn instance_of(&mut self, from: &str, to: &str) {
if self.edge_ids.insert((from.to_string(), to.to_string())) {
self.edges.push(EdgeRow {
from: from.to_string(),
to: to.to_string(),
kind: EdgeKind::InstanceOf,
count: 1,
provenance: Provenance::BinaryOnly,
valid_from_sha: self.sha.clone(),
valid_to_sha: None,
negated: None,
partial: None,
access: None,
});
}
}
#[allow(clippy::too_many_arguments)]
fn symbol(&mut self, id: &str, s: &elf::BinSymbol, demangled: Option<String>, r: &str, krate: &str, version: &str, prov: Provenance) {
self.symbols.push(SymbolRow {
id: id.to_string(),
symbol: s.name.clone(),
demangled,
role: r.to_string(),
krate: krate.to_string(),
version: version.to_string(),
binary: Some(self.binary_name.clone()),
section: s.section.clone(),
addr: s.defined.then_some(s.addr),
size: s.defined.then_some(s.size),
provenance: prov,
valid_from_sha: self.sha.clone(),
valid_to_sha: None,
});
}
fn fresh_node(&self, id: String, k: &str, name: String, parent: Option<String>, ident: Option<&CrateIdent>, krate: &str) -> NodeRow {
NodeRow {
id,
kind: k.to_string(),
level: Level::Item,
name,
parent,
repo: None,
krate: ident.map(|i| i.package.clone()).unwrap_or_else(|| krate.to_string()),
version: ident.map(|i| i.version.clone()).unwrap_or_else(|| "?".into()),
file: None,
start_line: None,
end_line: None,
cfg: None,
origin: ident.map(|i| i.origin).unwrap_or(Origin::Library),
provenance: Provenance::BinaryOnly,
valid_from_sha: self.sha.clone(),
valid_to_sha: None,
ty: None,
is_test: false,
defined_here: true,
visibility: None,
effective_visibility: None,
doc: None,
has_doc: None,
ignored: None,
doc_hidden: None,
link_name: None,
}
}
}
/// The binary stream's facts per moniker, for deriving provenance at read
/// time ([`mimir_schema::derive_provenance`]).
#[derive(Debug, Default)]
pub struct BinaryIndex {
symbols: HashSet<String>,
instance_targets: HashSet<String>,
nodes: HashSet<String>,
}
impl BinaryIndex {
pub fn new(o: &Output) -> BinaryIndex {
BinaryIndex {
symbols: o.symbols.iter().map(|s| s.id.clone()).collect(),
instance_targets: o.edges.iter().filter(|e| e.kind == EdgeKind::InstanceOf).map(|e| e.to.clone()).collect(),
nodes: o.nodes.iter().map(|n| n.id.clone()).collect(),
}
}
pub fn facts(&self, id: &str) -> mimir_schema::BinaryFacts {
mimir_schema::BinaryFacts {
has_symbol: self.symbols.contains(id),
instances_linked: self.instance_targets.contains(id),
binary_node: self.nodes.contains(id),
}
}
/// The derived provenance of `id` against the source half `src` (a
/// reference stub is not a source definition).
pub fn provenance(&self, src: &SourceDump, id: &str) -> Option<Provenance> {
mimir_schema::derive_provenance(src.nodes.get(id).is_some_and(|n| n.defined_here), self.facts(id))
}
}
/// Run the join against the driver dump directories `opts` names.
pub fn run(opts: &Options) -> Result<Output, String> {
let mut dirs = vec![opts.dump.clone()];
dirs.extend(opts.extra_dumps.iter().cloned());
let src = SourceDump::load_many(&dirs)?;
run_with(opts, &src)
}
/// Run the join against a source half the caller already holds
/// ([`SourceDump::from_rows`]: the rows a log keeps, not a dump directory).
/// `opts.dump` / `opts.extra_dumps` are not read.
pub fn run_with(opts: &Options, src: &SourceDump) -> Result<Output, String> {
let t0 = Instant::now();
let bin = elf::read_binary(&opts.binary)?;
let packages = match (&opts.packages, &opts.manifest) {
(Some(p), _) => p.clone(),
(None, Some(m)) => crates::cargo_metadata(m)?,
(None, None) => Vec::new(),
};
let mut res = Resolver::new(&packages);
res.add_cus(&bin.cus);
let rlibs = opts.deps_dir.as_deref().map(elf::scan_deps_dir).unwrap_or_default();
res.add_rlibs(&rlibs);
let sysroot_rlibs = opts.sysroot.as_deref().map(elf::scan_sysroot).unwrap_or_default();
res.add_sysroot(&sysroot_rlibs);
res.add_driver(&src.crate_ids);
let ms_read = t0.elapsed().as_millis();
let t1 = Instant::now();
let binary_name = opts.binary.file_name().map(|s| s.to_string_lossy().into_owned()).unwrap_or_default();
let mut l = Ledger {
binary: opts.binary.display().to_string(),
file_size: bin.file_size,
text_size: bin.section_size(".text"),
has_dwarf: bin.has_dwarf,
symbol_table: if bin.sections.iter().any(|(n, _)| n == ".symtab") { ".symtab".into() } else { ".dynsym".into() },
crate_ids_known: res.known_ids(),
crate_id_conflicts: res.conflicts.clone(),
cu_crates: bin.cus.len(),
deps_rlibs: rlibs.len(),
sysroot_rlibs: sysroot_rlibs.len(),
..Default::default()
};
let mut e = Emit {
src,
binary_name,
sha: opts.sha.clone(),
nodes: Vec::new(),
node_ids: HashSet::new(),
edges: Vec::new(),
edge_ids: HashSet::new(),
symbols: Vec::new(),
touched: HashSet::new(),
};
let mut bytes: HashMap<String, (u64, usize)> = HashMap::new();
let mut linked_crates: HashSet<(String, String)> = HashSet::new();
let mut rust_defined = 0usize;
let mut with_moniker = 0usize;
let mut source_matched = 0usize;
let mut seen_defined: HashSet<(String, u64)> = HashSet::new();
for s in &bin.symbols {
if !s.defined {
import(&mut e, &mut l, s);
continue;
}
// `.symtab` can list one symbol twice (local + global alias)
if !seen_defined.insert((s.name.clone(), s.addr)) {
continue;
}
l.defined += 1;
l.defined_bytes += s.size;
// `$`-suffixed names (`…$got`, `…$plt`) are linker-made entries ABOUT a
// symbol, not the symbol: counted as `other`, never matched
let mangling = if s.name.contains('$') {
"other"
} else if s.name.starts_with("_R") {
"v0"
} else if s.name.starts_with("_ZN") {
"legacy"
} else {
"other"
};
*l.by_mangling.entry(mangling.into()).or_default() += 1;
if mangling != "other" {
rust_defined += 1;
}
if s.name.contains('$') {
*l.matched.entry("no_moniker".into()).or_default() += 1;
let b = bytes.entry("-".into()).or_default();
b.0 += s.size;
b.1 += 1;
continue;
}
// 1. exact symbol (driver-built artifact)
let clean = s.name.split('.').next().unwrap_or(&s.name);
let exact = if opts.ignore_driver_symbols { None } else { src.symbol_ids.get(clean).or_else(|| src.symbol_ids.get(&s.name)) };
if let Some(id) = exact {
let n = src.nodes.get(id);
let (k, v) = n.map(|n| (n.krate.clone(), n.version.clone())).unwrap_or_default();
let oc = l.by_origin.entry(n.map(|n| n.origin.as_str()).unwrap_or("?").to_string()).or_default();
oc.symbols += 1;
oc.bytes += s.size;
oc.matched += 1;
linked_crates.insert((k.clone(), v.clone()));
let id = id.clone();
e.both(&id);
e.symbol(&id, s, demangle(&s.name), role::ITEM, &k, &v, Provenance::Both);
*l.matched.entry("exact_symbol".into()).or_default() += 1;
*l.roles.entry(role::ITEM.into()).or_default() += 1;
let b = bytes.entry(format!("{k}@{v}")).or_default();
b.0 += s.size;
b.1 += 1;
with_moniker += 1;
source_matched += 1;
continue;
}
match mangling {
"v0" => {}
"legacy" => {
let r = legacy(&mut e, &mut l, &mut res, s);
if let Some((key, matched)) = r {
with_moniker += 1;
source_matched += matched as usize;
let b = bytes.entry(key).or_default();
b.0 += s.size;
b.1 += 1;
} else {
let b = bytes.entry("?".into()).or_default();
b.0 += s.size;
b.1 += 1;
}
continue;
}
_ => {
*l.matched.entry("no_moniker".into()).or_default() += 1;
let b = bytes.entry("-".into()).or_default();
b.0 += s.size;
b.1 += 1;
continue;
}
}
// 2. v0
let decoded = match v0::decode(&s.name) {
Ok(d) => d,
Err(err) => {
let k = match &err {
v0::Error::Unsupported(w) => format!("unsupported: {w}"),
v0::Error::Invalid(w, _) => format!("invalid: {w}"),
v0::Error::NotV0 => "not v0".into(),
};
*l.decode_errors.entry(k).or_default() += 1;
sample(&mut l.decode_error_samples, format!("{} ({err})", s.name));
*l.matched.entry("no_moniker".into()).or_default() += 1;
let b = bytes.entry("?".into()).or_default();
b.0 += s.size;
b.1 += 1;
continue;
}
};
let item = item_path(&decoded.path);
let flat = match flatten(&decoded.path).and_then(|f| split_role(f.segs.clone()).map(|(segs, r)| (f, segs, r))) {
Ok(x) => x,
Err(why) => {
*l.decode_errors.entry(format!("shape: {why}")).or_default() += 1;
sample(&mut l.decode_error_samples, format!("{} ({why})", v0::print_path(&decoded.path)));
*l.matched.entry("no_moniker".into()).or_default() += 1;
let b = bytes.entry("?".into()).or_default();
b.0 += s.size;
b.1 += 1;
continue;
}
};
let (f, segs, r) = flat;
// the internal `__rustc` crate (`__rust_alloc` & co): no source item
if f.crate_name == "__rustc" {
*l.matched.entry("no_moniker".into()).or_default() += 1;
*l.decode_errors.entry("rustc internal symbol".into()).or_default() += 1;
let b = bytes.entry("-".into()).or_default();
b.0 += s.size;
b.1 += 1;
continue;
}
let (ident, via) = res.resolve(&f.crate_name, f.crate_id);
*l.crate_via.entry(via.as_str().into()).or_default() += 1;
match via {
Via::Ambiguous => *l.ambiguous_crates.entry(f.crate_name.clone()).or_default() += 1,
Via::Unknown => *l.unknown_crates.entry(f.crate_name.clone()).or_default() += 1,
_ => {}
}
let key = ident.as_ref().map(|i| format!("{}@{}", i.package, i.version)).unwrap_or_else(|| "?".into());
let b = bytes.entry(key).or_default();
b.0 += s.size;
b.1 += 1;
let cands = candidates(&segs, s.is_data);
let demangled = Some(v0::print_path(&decoded.path));
let instance_key = v0::print_path(item);
let Some(ident) = ident else {
// crate not resolvable to ONE package: a node anyway (version `?`), counted
let id = moniker::moniker(&f.crate_name, "?", &cands[0]);
unmatched(&mut e, &mut l, s, &f, &segs, id, &instance_key, demangled, r, None);
continue;
};
with_moniker += 1;
linked_crates.insert((ident.package.clone(), ident.version.clone()));
let oc = l.by_origin.entry(ident.origin.as_str().to_string()).or_default();
oc.symbols += 1;
oc.bytes += s.size;
let (hit, level) = match lookup(src, &ident, &cands) {
Hit::Exact(id) => (Some(id), "exact"),
Hit::ExactAmbiguous(id, n) => {
l.ambiguous_exact += 1;
sample(&mut l.ambiguity_samples, format!("exact×{n}: {} → {id}", demangled.as_deref().unwrap_or("")));
(Some(id), "exact")
}
Hit::Loose(id) => (Some(id), "loose"),
Hit::Blanket(id) => (Some(id), "blanket"),
Hit::LooseAmbiguous(n) => {
l.ambiguous_loose += 1;
sample(&mut l.ambiguity_samples, format!("loose×{n}: {}", demangled.as_deref().unwrap_or("")));
(None, "")
}
Hit::None => (None, ""),
};
let Some(m) = hit else {
let id = moniker::moniker(&ident.package, &ident.version, &format!("{}{}", ident.prefix, cands[0]));
unmatched(&mut e, &mut l, s, &f, &segs, id, &instance_key, demangled, r, Some(&ident));
continue;
};
source_matched += 1;
*l.matched.entry(level.into()).or_default() += 1;
l.by_origin.entry(ident.origin.as_str().to_string()).or_default().matched += 1;
// an instance needs BOTH: a generic source item and generic args in
// the symbol (an impl block merged with a generic sibling, or an
// all-default instance, is the item itself)
let generic = src.is_generic(&m);
if generic && !f.has_args {
l.generic_item_without_args += 1;
}
if generic && f.has_args {
let mono = moniker::mono_instance(&m, &instance_key);
e.both(&m);
if !e.node_ids.contains(&mono) {
let g = &src.nodes[&m];
let mut row = e.fresh_node(mono.clone(), kind::MONO_INSTANCE, instance_key.clone(), Some(m.clone()), Some(&ident), &f.crate_name);
row.krate = g.krate.clone();
row.version = g.version.clone();
row.origin = g.origin;
row.file = g.file.clone();
row.start_line = g.start_line;
row.end_line = g.end_line;
row.repo = g.repo.clone();
e.binary_only(row);
l.nodes_mono_instance += 1;
}
e.instance_of(&mono, &m);
let rr = if r == role::ITEM { role::MONO } else { r };
*l.roles.entry(rr.into()).or_default() += 1;
e.symbol(&mono, s, demangled, rr, &ident.package, &ident.version, Provenance::BinaryOnly);
} else {
if f.has_args {
l.instance_of_nongeneric += 1;
}
e.both(&m);
*l.roles.entry(r.into()).or_default() += 1;
e.symbol(&m, s, demangled, r, &ident.package, &ident.version, Provenance::Both);
}
}
// ---- source items of linked crates with no binary twin
for n in src.nodes.values() {
if !n.defined_here || !source::symbol_bearing(&n.kind) || n.kind == kind::FFI {
continue;
}
if !linked_crates.contains(&(n.krate.clone(), n.version.clone())) {
continue;
}
l.source_items_in_linked_crates += 1;
if !e.touched.contains(&n.id) {
l.source_only_items += 1;
sample(&mut l.source_only_samples, n.id.clone());
}
}
l.nodes_both = e.touched.iter().filter(|id| src.nodes.get(*id).is_some_and(|n| n.defined_here)).count();
l.nodes_binary_only = e.nodes.len();
l.edges_instance_of = e.edges.len();
l.instance_of_dangling = e.edges.iter().filter(|x| !src.nodes.contains_key(&x.to)).count();
let pct = |a: usize, b: usize| if b == 0 { 0.0 } else { (a as f64 * 1000.0 / b as f64).round() / 10.0 };
l.pct_moniker_of_defined = pct(with_moniker, l.defined);
l.pct_moniker_of_rust = pct(with_moniker, rust_defined);
l.pct_source_match_of_rust = pct(source_matched, rust_defined);
let mut by: Vec<(String, u64, usize)> = bytes.into_iter().map(|(k, (b, n))| (k, b, n)).collect();
by.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)));
l.bytes_by_crate = by;
l.ms_read = ms_read;
l.ms_join = t1.elapsed().as_millis();
Ok(Output { nodes: e.nodes, edges: e.edges, symbols: e.symbols, ledger: l })
}
#[allow(clippy::too_many_arguments)]
fn unmatched(
e: &mut Emit,
l: &mut Ledger,
s: &elf::BinSymbol,
f: &Flat,
segs: &[Seg],
id: String,
instance_key: &str,
demangled: Option<String>,
r: &str,
ident: Option<&CrateIdent>,
) {
*l.matched.entry("unmatched".into()).or_default() += 1;
let line = format!("{} → {id}", demangled.as_deref().unwrap_or(&s.name));
if ident.is_some_and(|i| i.origin == Origin::Lang) {
sample(&mut l.unmatched_lang_samples, line);
} else {
sample(&mut l.unmatched_samples, line);
}
let name = match segs.last() {
Some(Seg::T(n) | Seg::Ty(n) | Seg::V(n) | Seg::Meta(n)) => n.clone(),
_ => s.name.clone(),
};
let (pkg, ver) = (id_pkg(&id), id_ver(&id));
if f.has_args {
let mono = moniker::mono_instance(&id, instance_key);
if !e.node_ids.contains(&mono) {
let row = e.fresh_node(mono.clone(), kind::MONO_INSTANCE, instance_key.to_string(), Some(id.clone()), ident, &f.crate_name);
e.binary_only(row);
l.nodes_mono_instance += 1;
}
e.instance_of(&mono, &id);
let rr = if r == role::ITEM { role::MONO } else { r };
*l.roles.entry(rr.into()).or_default() += 1;
e.symbol(&mono, s, demangled, rr, &pkg, &ver, Provenance::BinaryOnly);
} else {
let in_impl = segs.len() >= 2 && matches!(segs[segs.len() - 2], Seg::Impl { .. });
let k = if s.is_data { kind::STATIC } else if in_impl { kind::METHOD } else { kind::FN };
let row = e.fresh_node(id.clone(), k, name, None, ident, &f.crate_name);
e.binary_only(row);
*l.roles.entry(r.into()).or_default() += 1;
e.symbol(&id, s, demangled, r, &pkg, &ver, Provenance::BinaryOnly);
}
}
fn id_pkg(id: &str) -> String {
moniker::parse(id).map(|(p, _, _)| p.to_string()).unwrap_or_default()
}
fn id_ver(id: &str) -> String {
moniker::parse(id).map(|(_, v, _)| v.to_string()).unwrap_or_default()
}
fn demangle(name: &str) -> Option<String> {
rustc_demangle::try_demangle(name).ok().map(|d| format!("{d:#}"))
}
/// An undefined symbol: the FFI border.
fn import(e: &mut Emit, l: &mut Ledger, s: &elf::BinSymbol) {
l.undefined += 1;
let (name, version) = match s.name.split_once('@') {
Some((n, v)) => (n.to_string(), v.trim_start_matches('@').to_string()),
None => (s.name.clone(), String::new()),
};
// driver symbol table: a foreign item whose link name is this symbol
let mut ids: Vec<String> = e.src.symbol_ids.get(&name).filter(|id| e.src.nodes.get(*id).is_some_and(|n| n.kind == kind::FFI)).cloned().into_iter().collect();
if ids.is_empty() {
ids = e.src.ffi_by_name.get(&name).cloned().unwrap_or_default();
}
match ids.len() {
0 => {
*l.imports.entry("extern".into()).or_default() += 1;
let ver = if version.is_empty() { "-".to_string() } else { version };
let suffix = if s.is_data { Suffix::Term } else { Suffix::Method };
let id = moniker::moniker("extern", &ver, &moniker::descriptor(suffix, &name));
let mut row = e.fresh_node(id.clone(), kind::FFI_IMPORT, name, None, None, "extern");
row.version = ver.clone();
e.binary_only(row);
e.symbol(&id, s, None, role::IMPORT, "extern", &ver, Provenance::BinaryOnly);
}
n => {
*l.imports.entry(if n == 1 { "source_ffi".into() } else { "source_ffi_multi_decl".into() }).or_default() += 1;
for id in ids {
e.both(&id);
let (k, v) = e.src.nodes.get(&id).map(|n| (n.krate.clone(), n.version.clone())).unwrap_or_default();
e.symbol(&id, s, None, role::IMPORT, &k, &v, Provenance::Both);
}
}
}
}
/// Legacy (`_ZN…17h<hash>E`) symbols: the hash is opaque, so only plain
/// paths (no `<impl>` / `{closure}` / generic args) are matched, by crate
/// NAME. Returns (crate key, matched-to-source) when a moniker was formed.
fn legacy(e: &mut Emit, l: &mut Ledger, res: &mut Resolver, s: &elf::BinSymbol) -> Option<(String, bool)> {
let d = demangle(&s.name)?;
if d.contains('<') || d.contains('{') || !d.contains("::") {
*l.matched.entry("legacy_unsupported".into()).or_default() += 1;
return None;
}
let parts: Vec<&str> = d.split("::").collect();
let (ident, via) = res.resolve(parts[0], u64::MAX);
*l.crate_via.entry(format!("legacy_{}", via.as_str())).or_default() += 1;
let Some(ident) = ident else {
*l.matched.entry("legacy_unsupported".into()).or_default() += 1;
return None;
};
let segs: Vec<Seg> = parts[1..]
.iter()
.enumerate()
.map(|(i, p)| if i + 2 == parts.len() { Seg::V(p.to_string()) } else { Seg::T(p.to_string()) })
.collect();
let cands = candidates(&segs, s.is_data);
let key = format!("{}@{}", ident.package, ident.version);
match lookup(e.src, &ident, &cands) {
Hit::Exact(id) | Hit::ExactAmbiguous(id, _) => {
*l.matched.entry("legacy_exact".into()).or_default() += 1;
e.both(&id);
e.symbol(&id, s, Some(d), role::ITEM, &ident.package, &ident.version, Provenance::Both);
Some((key, true))
}
_ => {
*l.matched.entry("legacy_unmatched".into()).or_default() += 1;
Some((key, false))
}
}
}
/// Write `<stem>.binary.{nodes,edges,symbols}.arrow` + `<stem>.binary.ledger.json`.
pub fn write(out: &Path, stem: &str, o: &Output) -> Result<(), String> {
std::fs::create_dir_all(out).map_err(|e| e.to_string())?;
let nb = mimir_schema::nodes_batch(&o.nodes).map_err(|e| e.to_string())?;
let eb = mimir_schema::edges_batch(&o.edges).map_err(|e| e.to_string())?;
let sb = mimir_schema::symbols_batch(&o.symbols).map_err(|e| e.to_string())?;
write_ipc(&out.join(format!("{stem}.binary.nodes.arrow")), &nb)?;
write_ipc(&out.join(format!("{stem}.binary.edges.arrow")), &eb)?;
write_ipc(&out.join(format!("{stem}.binary.symbols.arrow")), &sb)?;
std::fs::write(out.join(format!("{stem}.binary.ledger.json")), serde_json::to_vec_pretty(&o.ledger).map_err(|e| e.to_string())?)
.map_err(|e| e.to_string())
}
/// Read an Arrow IPC file back as (columns, rows of strings; null → empty).
pub fn read_table(path: &Path) -> Result<(Vec<String>, Vec<Vec<String>>), String> {
use arrow_array::cast::AsArray;
use arrow_array::types::{UInt32Type, UInt64Type};
use arrow_array::Array;
let mut cols = Vec::new();
let mut rows = Vec::new();
for b in source::read_ipc(path)? {
if cols.is_empty() {
cols = b.schema().fields().iter().map(|f| f.name().clone()).collect();
}
for i in 0..b.num_rows() {
rows.push(
b.columns()
.iter()
.map(|c| {
if c.is_null(i) {
return String::new();
}
match c.data_type() {
arrow_schema::DataType::Utf8 => c.as_string::<i32>().value(i).to_string(),
arrow_schema::DataType::UInt32 => c.as_primitive::<UInt32Type>().value(i).to_string(),
arrow_schema::DataType::UInt64 => c.as_primitive::<UInt64Type>().value(i).to_string(),
arrow_schema::DataType::Boolean => c.as_boolean().value(i).to_string(),
_ => "?".into(),
}
})
.collect(),
);
}
}
Ok((cols, rows))
}
fn write_ipc(path: &Path, batch: &arrow_array::RecordBatch) -> Result<(), String> {
let f = std::fs::File::create(path).map_err(|e| e.to_string())?;
let mut w = arrow_ipc::writer::FileWriter::try_new(std::io::BufWriter::new(f), &batch.schema()).map_err(|e| e.to_string())?;
w.write(batch).map_err(|e| e.to_string())?;
w.finish().map_err(|e| e.to_string())
}
#[cfg(test)]
mod tests {
use super::*;
fn segs_of(sym: &str) -> (Flat, Vec<Seg>, &'static str) {
let d = v0::decode(sym).unwrap();
let f = flatten(&d.path).unwrap();
let (s, r) = split_role(f.segs.clone()).unwrap();
(f, s, r)
}
#[test]
fn candidates_for_fns_methods_and_impls() {
let (f, s, r) = segs_of("_RNvCsfPIvSHfysBz_1b3run");
assert_eq!((f.crate_name.as_str(), r), ("b", role::ITEM));
assert_eq!(candidates(&s, false), vec!["run()."]);
// <&str as core::fmt::Debug>::fmt — a trait impl over a non-ADT self
let (f, s, _) = segs_of("_RNvXs1g_NtCsgxBkk5gSRhY_4core3fmtReNtB6_5Debug3fmtCsfPIvSHfysBz_1b");
assert_eq!(f.crate_name, "core");
assert_eq!(candidates(&s, false), vec!["fmt/impl#[`&str`][Debug]fmt().", "fmt#impl#[`&str`][Debug]fmt()."]);
// a::ident::<u32>: generic args → an instance candidate
let (f, s, _) = segs_of("_RINvCsbR8JNGoZHix_1a5identmECsfPIvSHfysBz_1b");
assert!(f.has_args);
assert_eq!(candidates(&s, false), vec!["ident()."]);
}
#[test]
fn closures_and_shims_attribute_to_their_item() {
let (_, s, r) = segs_of("_RNCINvMs0_NtNtCs9k3SxhrAWiO_3std4sync4onceNtB8_4Once15call_once_forceNCINvMNtBa_9once_lockINtB1b_8OnceLockINtNtBa_14reentrant_lock13ReentrantLockINtNtCsgxBkk5gSRhY_4core4cell7RefCellINtNtNtNtBc_2io8buffered10linewriter10LineWriterNtNtB31_5stdio9StdoutRawEEEE10initializeNCINvB1a_11get_or_initNCNvB3I_6stdout0E0zE0E0Bc_");
assert_eq!(r, role::CLOSURE);
assert_eq!(candidates(&s, false)[0], "sync/once/impl#[Once]call_once_force().");
}
#[test]
fn provided_trait_method_instances_land_on_the_trait() {
// <std::panicking::begin_panic::Payload<&str> as core::panic::PanicPayload>::as_str
// is an X (trait impl) path; a Y path names the trait's own item:
let (f, s, _) = segs_of("_RNvYINtNvNtCs9k3SxhrAWiO_3std9panicking11begin_panic7PayloadReENtNtCsgxBkk5gSRhY_4core5panic12PanicPayload6as_strB9_");
assert_eq!(f.crate_name, "core");
assert!(f.has_args);
assert_eq!(candidates(&s, false), vec!["panic/PanicPayload#as_str().", "panic#PanicPayload#as_str()."]);
}
}