crates/nornir-depgraph/src/funcgraph.rs
//! **The function-tier seam** — nornir's per-crate symbol + call-edge data lifted
//! into a small, egui-free / warehouse-free graph the WORLD GRAPH's function tier
//! renders as REAL (not synthetic).
//!
//! # Why it lives here
//! `nornir-depgraph` is the ONE depgraph model nornir AND dwarves already share
//! (`WorkspaceGraph` for the repo/crate tiers). The warehouse navigator
//! (dwarves' `nornir-warehouse-nav`) already depends on this crate, so the
//! function-tier PODs it needs to render belong here too — right next to the
//! repo/crate model — rather than in a new parallel graph type. This module is a
//! **pure data transform** (no warehouse, no arrow, no egui): a native host loads
//! the symbol/call rows through nornir's warehouse (`KnowledgeView`) and hands
//! their fields to [`build_function_graph`]; the result is the real function tier.
//!
//! # Stable identity (the known weak point, kept consistent)
//! `symbol_facts` rows carry no node-id. nornir synthesises one — in exactly ONE
//! place, `nornir::mimir_analyze::assemble_symbol_vecs` — as
//! `format!("{repo}::{crate}::{module}::{item}")`. [`stable_id`] reuses that SAME
//! synthesis so a function deduplicates consistently and a call edge resolves to
//! the same node the rest of nornir names. We do NOT invent a second id scheme.
//!
//! # Edge resolution (identifier-granularity, honest by construction)
//! nornir's syn scanner records a caller as `module_path::item_name` (its
//! `caller_path`) and a callee as a bare/last-qualified identifier
//! (`callee_ident`) — never a fully-resolved defining path. So call edges resolve
//! at **identifier granularity**, the SAME approximation
//! `KnowledgeView::call_path` documents: a caller matches the symbol whose
//! `module_path::item_name` equals its `caller_path`; a callee matches a symbol in
//! the SAME crate whose `item_name` equals the callee's last segment. Cross-crate
//! and unresolved callees are dropped — the edge set is the honest intra-crate
//! call graph, not a fabricated one.
use std::collections::{BTreeMap, BTreeSet};
/// One function node in a crate's function-tier graph: the stable id, the display
/// name, and its owning crate. `id` is [`stable_id`] — consistent with nornir's
/// own synthesis so nodes dedupe and edges resolve across the whole constellation.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FnNode {
/// `{repo}::{crate}::{module}::{item}` — the same synthesis nornir uses.
pub id: String,
/// The function's `item_name` (the chip label).
pub name: String,
/// The owning crate (the parent in the world graph's LOD hierarchy).
pub crate_name: String,
}
/// A resolved intra-crate call edge, caller stable-id → callee stable-id. Both
/// endpoints are [`FnNode::id`]s present in the SAME [`CrateFuncGraph`].
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct FnEdge {
pub from: String,
pub to: String,
}
/// One crate's real function tier: its function nodes and the call edges among
/// them. LOD-friendly — the world graph asks per crate (or per repo), so it never
/// has to pull all functions at once.
#[derive(Clone, Debug)]
pub struct CrateFuncGraph {
pub crate_name: String,
pub nodes: Vec<FnNode>,
pub edges: Vec<FnEdge>,
}
impl CrateFuncGraph {
/// Whether this crate really produced any function nodes (a crate with symbols
/// must NOT come back empty — an empty real result over a crate that HAS
/// symbols is a bug, and the caller asserts against it).
#[must_use]
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
}
/// Minimal borrowed view of a `symbol_facts` row — only the four fields the seam
/// needs. Kept POD + borrowed so this crate stays warehouse-free (no dependency on
/// `nornir-warehouse-trait` / arrow): a caller with real `SymbolRow`s adapts them
/// in one line (see `nornir_knowledge_view::KnowledgeView::function_graph`).
#[derive(Clone, Copy, Debug)]
pub struct SymIn<'a> {
pub crate_name: &'a str,
pub module_path: &'a str,
pub item_kind: &'a str,
pub item_name: &'a str,
}
/// Minimal borrowed view of a `call_edges` row.
#[derive(Clone, Copy, Debug)]
pub struct CallIn<'a> {
pub crate_name: &'a str,
pub caller_path: &'a str,
pub callee_ident: &'a str,
}
/// The stable node id for a symbol — the SAME synthesis nornir uses in
/// `mimir_analyze::assemble_symbol_vecs` (`{repo}::{crate}::{module}::{item}`).
/// Reused verbatim so ids match across the seam and the rest of nornir.
#[must_use]
pub fn stable_id(repo: &str, crate_name: &str, module_path: &str, item_name: &str) -> String {
format!("{repo}::{crate_name}::{module_path}::{item_name}")
}
/// The item kinds the function tier renders as nodes. nornir's scanner emits `"fn"`
/// for free fns AND impl methods, and `"method"` for trait-method signatures — the
/// callable surface. Types/traits/consts are NOT function-tier nodes.
#[must_use]
pub fn is_function_kind(kind: &str) -> bool {
matches!(kind, "fn" | "method")
}
fn last_seg(s: &str) -> &str {
s.rsplit("::").next().unwrap_or(s)
}
/// Build the per-crate function-tier graph for one `repo` from its `symbols` +
/// `calls`. Returns one [`CrateFuncGraph`] per crate that has ≥1 function symbol,
/// crates sorted by name, nodes sorted by id, edges sorted+deduped — fully
/// deterministic. Function identity is [`stable_id`]; edges are the honest
/// identifier-granularity intra-crate call graph (see the module docs).
#[must_use]
pub fn build_function_graph(repo: &str, symbols: &[SymIn], calls: &[CallIn]) -> Vec<CrateFuncGraph> {
// 1. Group the function symbols by crate, deduped by stable id.
// per_crate[crate] = map id -> FnNode (BTreeMap ⇒ nodes sorted by id).
let mut per_crate: BTreeMap<String, BTreeMap<String, FnNode>> = BTreeMap::new();
// resolution tables, per crate:
// callkey_to_id: "module::item" -> id (caller_path resolves exactly here)
// name_to_id: item_name -> id (callee last-seg resolves here; on a
// name collision the smallest id wins,
// the identifier-granularity collapse)
let mut callkey_to_id: BTreeMap<String, BTreeMap<String, String>> = BTreeMap::new();
let mut name_to_id: BTreeMap<String, BTreeMap<String, String>> = BTreeMap::new();
for s in symbols {
if !is_function_kind(s.item_kind) {
continue;
}
let id = stable_id(repo, s.crate_name, s.module_path, s.item_name);
per_crate
.entry(s.crate_name.to_string())
.or_default()
.entry(id.clone())
.or_insert_with(|| FnNode {
id: id.clone(),
name: s.item_name.to_string(),
crate_name: s.crate_name.to_string(),
});
let callkey = format!("{}::{}", s.module_path, s.item_name);
callkey_to_id
.entry(s.crate_name.to_string())
.or_default()
.entry(callkey)
.or_insert_with(|| id.clone());
// smallest-id-wins on a duplicate name (deterministic collapse).
name_to_id
.entry(s.crate_name.to_string())
.or_default()
.entry(s.item_name.to_string())
.and_modify(|cur| {
if id < *cur {
*cur = id.clone();
}
})
.or_insert_with(|| id.clone());
}
// 2. Resolve call edges within each crate.
let mut edges_per_crate: BTreeMap<String, BTreeSet<FnEdge>> = BTreeMap::new();
for c in calls {
let Some(callkeys) = callkey_to_id.get(c.crate_name) else { continue };
let Some(names) = name_to_id.get(c.crate_name) else { continue };
let Some(from) = callkeys.get(c.caller_path) else { continue };
let Some(to) = names.get(last_seg(c.callee_ident)) else { continue };
if from == to {
continue; // self-call: not a distinct edge in the function tier.
}
edges_per_crate
.entry(c.crate_name.to_string())
.or_default()
.insert(FnEdge { from: from.clone(), to: to.clone() });
}
// 3. Assemble, crates sorted by name (BTreeMap order).
per_crate
.into_iter()
.map(|(crate_name, nodes)| {
let edges = edges_per_crate
.remove(&crate_name)
.map(|s| s.into_iter().collect())
.unwrap_or_default();
CrateFuncGraph {
crate_name,
nodes: nodes.into_values().collect(),
edges,
}
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
fn sym<'a>(krate: &'a str, module: &'a str, kind: &'a str, item: &'a str) -> SymIn<'a> {
SymIn { crate_name: krate, module_path: module, item_kind: kind, item_name: item }
}
fn call<'a>(krate: &'a str, caller: &'a str, callee: &'a str) -> CallIn<'a> {
CallIn { crate_name: krate, caller_path: caller, callee_ident: callee }
}
/// The id synthesis is byte-identical to nornir's `assemble_symbol_vecs`.
#[test]
fn stable_id_matches_nornir_synthesis() {
assert_eq!(
stable_id("edda", "nornir-git", "crate::head", "resolve"),
"edda::nornir-git::crate::head::resolve"
);
}
/// A crate with known function symbols yields NON-EMPTY real nodes AND resolves
/// the intra-crate call edges among them. RED-when-broken: a crate that HAS
/// symbols must never come back empty.
#[test]
fn crate_with_symbols_yields_nonempty_nodes_and_edges() {
let symbols = [
sym("mycrate", "crate", "fn", "main"),
sym("mycrate", "crate", "fn", "helper"),
sym("mycrate", "crate::io", "fn", "read"),
sym("mycrate", "crate", "struct", "Config"), // NOT a function — excluded
];
// main() calls helper() and read(); helper() calls read().
let calls = [
call("mycrate", "crate::main", "helper"),
call("mycrate", "crate::main", "read"),
call("mycrate", "crate::helper", "read"),
call("mycrate", "crate::main", "println"), // external ⇒ dropped
];
let graphs = build_function_graph("myrepo", &symbols, &calls);
assert_eq!(graphs.len(), 1, "one crate");
let g = &graphs[0];
assert_eq!(g.crate_name, "mycrate");
assert!(!g.is_empty(), "a crate with fn symbols is never empty");
// 3 functions (the struct is excluded).
assert_eq!(g.nodes.len(), 3);
assert!(g.nodes.iter().all(|n| n.crate_name == "mycrate"));
// ids use nornir's synthesis.
assert!(g.nodes.iter().any(|n| n.id == "myrepo::mycrate::crate::main"));
assert!(g.nodes.iter().any(|n| n.id == "myrepo::mycrate::crate::io::read"));
// 3 real intra-crate edges resolved; the external println call is dropped.
assert_eq!(g.edges.len(), 3, "main→helper, main→read, helper→read");
assert!(g.edges.contains(&FnEdge {
from: "myrepo::mycrate::crate::main".into(),
to: "myrepo::mycrate::crate::helper".into(),
}));
assert!(g.edges.contains(&FnEdge {
from: "myrepo::mycrate::crate::main".into(),
to: "myrepo::mycrate::crate::io::read".into(),
}));
}
/// Path-qualified callees (`Arc::new`, `Config::load`) resolve on their last
/// segment, and multiple crates split into multiple graphs.
#[test]
fn qualified_callees_and_multiple_crates() {
let symbols = [
sym("a", "crate", "fn", "load"),
sym("a", "crate", "fn", "boot"),
sym("b", "crate", "fn", "serve"),
];
let calls = [
call("a", "crate::boot", "Config::load"), // qualified → last seg `load`
call("b", "crate::serve", "unknown"), // unresolved in b → dropped
];
let graphs = build_function_graph("r", &symbols, &calls);
assert_eq!(graphs.len(), 2);
let a = graphs.iter().find(|g| g.crate_name == "a").unwrap();
assert_eq!(a.edges.len(), 1);
assert_eq!(a.edges[0].from, "r::a::crate::boot");
assert_eq!(a.edges[0].to, "r::a::crate::load");
let b = graphs.iter().find(|g| g.crate_name == "b").unwrap();
assert!(b.edges.is_empty(), "unresolved callee dropped, not fabricated");
assert_eq!(b.nodes.len(), 1);
}
/// Determinism: the same input yields byte-identical output (sorted crates,
/// nodes, edges).
#[test]
fn output_is_deterministic() {
let symbols = [sym("k", "crate", "fn", "b"), sym("k", "crate", "fn", "a")];
let calls = [call("k", "crate::a", "b")];
let g1 = build_function_graph("r", &symbols, &calls);
let g2 = build_function_graph("r", &symbols, &calls);
let ser = |g: &[CrateFuncGraph]| format!("{g:?}");
assert_eq!(ser(&g1), ser(&g2));
// nodes sorted by id: `a` before `b`.
assert_eq!(g1[0].nodes[0].name, "a");
assert_eq!(g1[0].nodes[1].name, "b");
}
}