src/clone_signals/structure.rs
//! **Signal 2 — the structure in the graph**, and the **role vectors** built
//! on it. No name counts: a function is described by what it touches, read
//! from the code room's resolved edges.
//!
//! | feature | from | reads as |
//! |---|---|---|
//! | `p:<type>` | CONTAINS → `param` part (not `self`), its printed type | "both take `&Path`" |
//! | `r:<type>` | CONTAINS → `ret` part (`->`), its printed type | "both return `MapLayout`" |
//! | `t:<id>` | USES_TYPE (the ADTs of the signature), the impl's own self type left out | "both use type `MapLayout`" |
//! | `f:<id>` | READS_FIELD | "both read `.MapLayout.repos`" |
//! | `c:<id>` | CALLS out | "both call `layout::place`" |
//! | `k:<id>` | CALLS in (role vectors only) | "both are called by `render`" |
//!
//! Ids are stable ids (`moniker::stable`: the version left out). Each feature
//! is weighted by how RARE it is among the room's functions,
//! `idf = ln(1 + N / df)`: sharing a struct ten functions use is strong
//! evidence, sharing `Result<(), Error>` (thousands) is almost none.
//!
//! **`structural_clones`** — the weighted Jaccard of two functions' feature
//! sets, `Σ idf(shared) / Σ idf(either)`, for pairs that share at least
//! [`MIN_SHARED`] features of which at least one is RARE (df ≤ [`RARE_DF`]).
//! Candidates come only from the rare features' posting lists — two functions
//! that share nothing rare are never compared — so the whole room is one pass.
//!
//! **Role vectors** ([`role_vectors`]) — FastRP (Chen et al., CIKM 2019): every
//! feature has a fixed very sparse random ±1 projection to [`ROLE_DIM`] dims
//! (seeded by the feature's own key, so a vector does not depend on the run);
//! a function's own vector is the IDF-weighted sum of its features'
//! projections (`X0`); two propagation steps over the room's CALLS (both
//! directions), USES_TYPE and READS_FIELD edges (row-normalised, on GraphBLAS:
//! one weighted `mxv` per column, [`mimir_graph::ops::propagate`]) mix in the
//! neighbourhood (`X1 = ·X0`, `X2 = ·X1`); the role vector is
//! `‖X0‖ + ‖X1‖ + ½‖X2‖`, normalised. Two functions with unrelated names that
//! play the same role — the same rare types, the same callees and callers —
//! end up close.
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use anyhow::Result;
use mimir_room::{EdgeSel, Room};
use mimir_schema::{EdgeKind, kind as nk, moniker};
/// A feature shared by this many functions or fewer (and by at most half of
/// the room's) is RARE: it opens a candidate pair. More common features still count in the score, at their
/// (small) weight, but never make two functions candidates on their own.
pub const RARE_DF: u32 = 64;
/// Features two functions must share to be a structural pair.
pub const MIN_SHARED: usize = 2;
/// Features a function must HAVE to be in a structural or role pair: a
/// two-feature accessor (`-> Option<bool>` reading one field) shares all it
/// has with every other one — a Jaccard of 1.0 that says nothing.
pub const MIN_FEATURES: usize = 3;
/// The weighted Jaccard at or above which two functions are structural clones.
pub const STRUCT_FLOOR: f32 = 0.5;
/// Role vector dimension.
pub const ROLE_DIM: usize = 128;
/// Non-zeros of one feature's random projection.
const PROJ_NNZ: usize = 4;
/// Weights of `X1` and `X2` in the role vector (X0 weighs 1).
const W1: f32 = 1.0;
const W2: f32 = 0.5;
/// The functions of a room and what each touches.
#[derive(Debug, Clone, Default)]
pub struct Features {
/// Room ordinals of the functions, one row each.
pub fns: Vec<u64>,
/// Per function, its structural features (sorted ids), callers excluded.
pub sets: Vec<Vec<u32>>,
/// Per function, its callers' features (`k:`), for the role vectors.
pub callers: Vec<Vec<u32>>,
/// Per feature: its key (`p:&str`, `t:<stable id>` …) and a human label.
pub keys: Vec<String>,
pub labels: Vec<String>,
/// Per feature: how many functions carry it.
pub df: Vec<u32>,
/// Per feature: its idf, `ln(1 + N / df)` — computed once per recount,
/// never per comparison (the pair loops read it billions of times).
pub idf_of: Vec<f32>,
}
impl Features {
pub fn n(&self) -> usize {
self.fns.len()
}
pub fn idf(&self, f: u32) -> f32 {
match self.idf_of.get(f as usize) {
Some(w) => *w,
None => (1.0 + self.n() as f32 / self.df[f as usize].max(1) as f32).ln(),
}
}
/// Add one function's features (keys with labels). Tests and the room
/// gatherer build through this.
pub fn push(&mut self, ordinal: u64, feats: &[(String, String)], callers: &[(String, String)]) {
let mut ids = |list: &[(String, String)], intern: &mut HashMap<String, u32>, keys: &mut Vec<String>, labels: &mut Vec<String>| -> Vec<u32> {
let mut v: Vec<u32> = list
.iter()
.map(|(k, l)| {
*intern.entry(k.clone()).or_insert_with(|| {
keys.push(k.clone());
labels.push(l.clone());
(keys.len() - 1) as u32
})
})
.collect();
v.sort_unstable();
v.dedup();
v
};
let mut intern: HashMap<String, u32> = self.keys.iter().enumerate().map(|(i, k)| (k.clone(), i as u32)).collect();
let s = ids(feats, &mut intern, &mut self.keys, &mut self.labels);
let c = ids(callers, &mut intern, &mut self.keys, &mut self.labels);
self.fns.push(ordinal);
self.sets.push(s);
self.callers.push(c);
self.recount();
}
fn recount(&mut self) {
self.df = vec![0; self.keys.len()];
for set in self.sets.iter().chain(&self.callers) {
for f in set {
self.df[*f as usize] += 1;
}
}
let n = self.n() as f32;
self.idf_of = self.df.iter().map(|d| (1.0 + n / (*d).max(1) as f32).ln()).collect();
}
/// A stable hash of one function's features (what the role vector of a
/// function is a function of, besides its neighbours): the incremental
/// update recomputes the functions whose hash moved, and their 2-hop ball.
pub fn hash_of(&self, row: usize) -> u64 {
let mut keys: Vec<&str> = self.sets[row].iter().chain(&self.callers[row]).map(|f| self.keys[*f as usize].as_str()).collect();
keys.sort_unstable();
keys.iter().fold(0xcbf2_9ce4_8422_2325u64, |h, k| k.bytes().chain(std::iter::once(0)).fold(h, |h, b| (h ^ b as u64).wrapping_mul(0x0100_0000_01b3)))
}
}
/// Gather the features of `fns` (room ordinals of function nodes).
pub fn gather(room: &Room, fns: &[u64]) -> Result<Features> {
let mask = room.mask_of(fns);
let out = |kinds: Vec<EdgeKind>| -> Result<Vec<mimir_room::EdgeOut>> { Ok(room.edges(&EdgeSel { kinds, from: Some(&mask), to: None, cap: None, heaviest_first: false })?.value.edges) };
// the same target is named by many edges: its stable id and short path once
let stable_memo: std::cell::RefCell<HashMap<u64, std::rc::Rc<str>>> = Default::default();
let stable = |o: u64| -> std::rc::Rc<str> { stable_memo.borrow_mut().entry(o).or_insert_with(|| moniker::stable(room.moniker(o)).into()).clone() };
let mut feats: BTreeMap<u64, Vec<(String, String)>> = BTreeMap::new();
let mut callers: BTreeMap<u64, Vec<(String, String)>> = BTreeMap::new();
let short_memo: std::cell::RefCell<HashMap<u64, std::rc::Rc<str>>> = Default::default();
let short = |o: u64| -> std::rc::Rc<str> {
short_memo
.borrow_mut()
.entry(o)
.or_insert_with(|| {
let p = room.display_path(o);
let parts: Vec<&str> = p.rsplit("::").take(2).collect();
parts.into_iter().rev().collect::<Vec<_>>().join("::").into()
})
.clone()
};
// params and the return type
for e in out(vec![EdgeKind::Contains])? {
let p = room.node(e.to);
let ty = p.ty.unwrap_or("_").to_string();
match p.kind {
Some(nk::PARAM) if p.name != Some("self") => feats.entry(e.from).or_default().push((format!("p:{ty}"), format!("take `{ty}`"))),
Some(nk::RET) => feats.entry(e.from).or_default().push((format!("r:{ty}"), format!("return `{ty}`"))),
_ => {}
}
}
// the impl's own self type: every method of a block has it, it says nothing
let blocks: Vec<u64> = fns.iter().filter_map(|o| room.node(*o).parent).filter(|p| room.node(*p).kind == Some(nk::IMPL)).collect::<BTreeSet<_>>().into_iter().collect();
let block_mask = room.mask_of(&blocks);
let mut self_ty: HashMap<u64, u64> = HashMap::new();
for e in room.edges(&EdgeSel { kinds: vec![EdgeKind::ForType], from: Some(&block_mask), to: None, cap: None, heaviest_first: false })?.value.edges {
self_ty.insert(e.from, e.to);
}
for e in out(vec![EdgeKind::UsesType, EdgeKind::ReadsField, EdgeKind::Calls])? {
let entry = feats.entry(e.from).or_default();
match e.kind {
EdgeKind::UsesType => {
if room.node(e.from).parent.and_then(|p| self_ty.get(&p)) == Some(&e.to) {
continue;
}
entry.push((format!("t:{}", stable(e.to)), format!("use type `{}`", room.node(e.to).name.unwrap_or("?"))));
}
EdgeKind::ReadsField => {
let f = room.node(e.to);
let owner = f.parent.and_then(|p| room.node(p).name).unwrap_or("?");
entry.push((format!("f:{}", stable(e.to)), format!("read `.{owner}.{}`", f.name.unwrap_or("?"))));
}
_ => entry.push((format!("c:{}", stable(e.to)), format!("call `{}`", short(e.to)))),
}
}
for e in room.edges(&EdgeSel { kinds: vec![EdgeKind::Calls], from: None, to: Some(&mask), cap: None, heaviest_first: false })?.value.edges {
callers.entry(e.to).or_default().push((format!("k:{}", stable(e.from)), format!("are called by `{}`", short(e.from))));
}
let mut f = Features::default();
let mut intern: HashMap<String, u32> = HashMap::new();
for o in fns {
let mut ids = |list: Option<&Vec<(String, String)>>| -> Vec<u32> {
let mut v: Vec<u32> = list
.into_iter()
.flatten()
.map(|(k, l)| {
*intern.entry(k.clone()).or_insert_with(|| {
f.keys.push(k.clone());
f.labels.push(l.clone());
(f.keys.len() - 1) as u32
})
})
.collect();
v.sort_unstable();
v.dedup();
v
};
let s = ids(feats.get(o));
let c = ids(callers.get(o));
f.fns.push(*o);
f.sets.push(s);
f.callers.push(c);
}
f.recount();
Ok(f)
}
/// One structural pair: rows `a < b` of [`Features`], the weighted Jaccard,
/// and the features they share (most informative first).
#[derive(Debug, Clone, PartialEq)]
pub struct StructPair {
pub a: usize,
pub b: usize,
pub score: f32,
pub shared: Vec<u32>,
}
/// What the pass did (the answer's evidence).
#[derive(Debug, Clone, Default, PartialEq, Eq, serde::Serialize)]
pub struct PassStats {
pub functions: usize,
pub features: usize,
pub rare_features: usize,
pub candidates: usize,
pub pairs: usize,
pub ms: u64,
}
/// The weighted Jaccard of two sorted feature sets, and what they share.
pub fn weighted_jaccard(f: &Features, a: &[u32], b: &[u32]) -> (f32, Vec<u32>) {
let (mut i, mut j) = (0usize, 0usize);
let (mut inter, mut union) = (0f32, 0f32);
let mut shared = Vec::new();
while i < a.len() || j < b.len() {
match (a.get(i), b.get(j)) {
(Some(x), Some(y)) if x == y => {
let w = f.idf(*x);
inter += w;
union += w;
shared.push(*x);
i += 1;
j += 1;
}
(Some(x), Some(y)) if x < y => {
union += f.idf(*x);
i += 1;
}
(Some(x), None) => {
union += f.idf(*x);
i += 1;
}
(_, Some(y)) => {
union += f.idf(*y);
j += 1;
}
(None, None) => break,
}
}
shared.sort_by(|x, y| f.idf(*y).total_cmp(&f.idf(*x)).then(x.cmp(y)));
(if union > 0.0 { inter / union } else { 0.0 }, shared)
}
/// The weighted Jaccard of two sorted feature sets and how many features
/// they share — allocating nothing (the candidate loop's test; the shared
/// list is built only for a pair that passes, by [`weighted_jaccard`]).
pub fn jaccard_score(f: &Features, a: &[u32], b: &[u32]) -> (f32, usize) {
let idf = &f.idf_of;
let w = |x: u32| idf.get(x as usize).copied().unwrap_or_else(|| f.idf(x));
let (mut i, mut j) = (0usize, 0usize);
let (mut inter, mut union, mut shared) = (0f32, 0f32, 0usize);
while i < a.len() && j < b.len() {
let (x, y) = (a[i], b[j]);
if x == y {
let v = w(x);
inter += v;
union += v;
shared += 1;
i += 1;
j += 1;
} else if x < y {
union += w(x);
i += 1;
} else {
union += w(y);
j += 1;
}
}
union += a[i..].iter().map(|x| w(*x)).sum::<f32>() + b[j..].iter().map(|y| w(*y)).sum::<f32>();
(if union > 0.0 { inter / union } else { 0.0 }, shared)
}
thread_local! {
/// One candidate-partner buffer per worker thread, cleared per row and
/// never freed between rows.
static PARTNERS: std::cell::RefCell<Vec<u32>> = const { std::cell::RefCell::new(Vec::new()) };
}
/// Every structural pair over the whole set (`rows`: only these rows can be
/// in a pair; `None` = all). See the module docs for the rule.
pub fn structural_pairs(f: &Features, floor: f32, rows: Option<&HashSet<usize>>) -> (Vec<StructPair>, PassStats) {
structural_pairs_on(f, floor, rows, 0)
}
/// [`structural_pairs`] on `workers` threads (`0` = one per core); the answer
/// is the same whatever the count.
pub fn structural_pairs_on(f: &Features, floor: f32, rows: Option<&HashSet<usize>>, workers: usize) -> (Vec<StructPair>, PassStats) {
let t0 = std::time::Instant::now();
let n = f.n();
// rare: shared by at most RARE_DF functions, and by at most half of them
// (a small room has no feature that is common in absolute numbers)
let cap = RARE_DF.min((n / 2).max(2) as u32);
let mut postings: HashMap<u32, Vec<u32>> = HashMap::new();
for (r, set) in f.sets.iter().enumerate() {
if rows.is_some_and(|keep| !keep.contains(&r)) || set.len() < MIN_FEATURES {
continue;
}
for x in set {
if (2..=cap).contains(&f.df[*x as usize]) {
postings.entry(*x).or_default().push(r as u32);
}
}
}
let rare = postings.len();
// one task per row, heaviest (most features) first, on every core; the
// results come back in row order (deterministic whatever the workers)
let order: Vec<u32> = (0..n as u32).collect();
let per_row: Vec<(Vec<StructPair>, usize)> = znippy_zoomies::gatling_forkjoin::gatling_map_balanced(
&order,
workers,
64,
|r| f.sets[*r as usize].len() as u64,
|_, r| {
let row = *r as usize;
if f.sets[row].len() < MIN_FEATURES {
return (Vec::new(), 0);
}
PARTNERS.with(|buf| {
let mut partners = buf.borrow_mut();
partners.clear();
for x in &f.sets[row] {
if let Some(p) = postings.get(x) {
partners.extend(p.iter().copied().filter(|j| *j as usize > row));
}
}
partners.sort_unstable();
partners.dedup();
let mut out = Vec::new();
for j in partners.iter() {
let (score, n_shared) = jaccard_score(f, &f.sets[row], &f.sets[*j as usize]);
if score >= floor && n_shared >= MIN_SHARED {
let (score, shared) = weighted_jaccard(f, &f.sets[row], &f.sets[*j as usize]);
out.push(StructPair { a: row, b: *j as usize, score, shared });
}
}
(out, partners.len())
})
},
);
let candidates: usize = per_row.iter().map(|r| r.1).sum();
let mut pairs: Vec<StructPair> = Vec::with_capacity(per_row.iter().map(|r| r.0.len()).sum());
for (o, _) in per_row {
pairs.extend(o);
}
pairs.sort_by(|x, y| y.score.total_cmp(&x.score).then((x.a, x.b).cmp(&(y.a, y.b))));
let stats = PassStats { functions: n, features: f.keys.len(), rare_features: rare, candidates, pairs: pairs.len(), ms: t0.elapsed().as_millis() as u64 };
(pairs, stats)
}
/// The words of a pair's shared features ("both return `MapLayout`, both
/// read `.MapLayout.repos`"), at most `max`.
pub fn shared_words(f: &Features, shared: &[u32], max: usize) -> Vec<String> {
shared.iter().take(max).map(|x| format!("both {} (df {})", f.labels[*x as usize], f.df[*x as usize])).collect()
}
// ── role vectors (FastRP) ───────────────────────────────────────────────────
fn mix(mut x: u64) -> u64 {
x = x.wrapping_add(0x9e37_79b9_7f4a_7c15);
x = (x ^ (x >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
x = (x ^ (x >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
x ^ (x >> 31)
}
/// A feature's fixed random projection: [`PROJ_NNZ`] (dim, ±1), seeded by the key.
fn projection(key: &str) -> [(usize, f32); PROJ_NNZ] {
let mut h = key.bytes().fold(0xcbf2_9ce4_8422_2325u64, |h, b| (h ^ b as u64).wrapping_mul(0x0100_0000_01b3));
let mut out = [(0usize, 0f32); PROJ_NNZ];
for slot in &mut out {
h = mix(h);
*slot = ((h % ROLE_DIM as u64) as usize, if (h >> 40) & 1 == 0 { 1.0 } else { -1.0 });
}
out
}
fn normalize(v: &mut [f32]) {
let n = v.iter().map(|x| x * x).sum::<f32>().sqrt();
if n > 0.0 {
v.iter_mut().for_each(|x| *x /= n);
}
}
/// The propagation graph: the functions first (rows `0..fns`), then every
/// other endpoint; symmetric, row-normalised.
#[derive(Debug, Clone, Default)]
pub struct RoleGraph {
pub nodes: usize,
pub neighbours: Vec<Vec<u32>>,
}
/// The role graph of `f`'s functions in `room`: CALLS both ways, USES_TYPE
/// and READS_FIELD to their targets (a type or field node is a row of its own,
/// so two functions on the same struct meet through it).
pub fn role_graph(room: &Room, f: &Features) -> Result<RoleGraph> {
let mut row_of: HashMap<u64, u32> = f.fns.iter().enumerate().map(|(i, o)| (*o, i as u32)).collect();
let mask = room.mask_of(&f.fns);
let mut adj: Vec<BTreeSet<u32>> = vec![BTreeSet::new(); f.n()];
let link = |a: u64, b: u64, row_of: &mut HashMap<u64, u32>, adj: &mut Vec<BTreeSet<u32>>| {
let mut row = |o: u64| {
let next = row_of.len() as u32;
let r = *row_of.entry(o).or_insert(next);
if r as usize >= adj.len() {
adj.push(BTreeSet::new());
}
r
};
let (ra, rb) = (row(a), row(b));
if ra != rb {
adj[ra as usize].insert(rb);
adj[rb as usize].insert(ra);
}
};
for e in room.edges(&EdgeSel { kinds: vec![EdgeKind::Calls, EdgeKind::UsesType, EdgeKind::ReadsField], from: Some(&mask), to: None, cap: None, heaviest_first: false })?.value.edges {
link(e.from, e.to, &mut row_of, &mut adj);
}
for e in room.edges(&EdgeSel { kinds: vec![EdgeKind::Calls], from: None, to: Some(&mask), cap: None, heaviest_first: false })?.value.edges {
link(e.from, e.to, &mut row_of, &mut adj);
}
Ok(RoleGraph { nodes: adj.len(), neighbours: adj.into_iter().map(|s| s.into_iter().collect()).collect() })
}
/// The role vectors of every function of `f`, or — with `only` — of the
/// functions in that set; `prev` gives the vectors kept for the others.
#[derive(Debug, Clone, Default)]
pub struct RoleVectors {
/// `fns × ROLE_DIM`, row-major, each row L2-normalised.
pub data: Vec<f32>,
/// Rows (function indexes) that were computed this time.
pub computed: usize,
pub ms: u64,
}
impl RoleVectors {
pub fn row(&self, i: usize) -> &[f32] {
&self.data[i * ROLE_DIM..(i + 1) * ROLE_DIM]
}
}
/// The 0..=k-hop ball of `seeds` in `g`.
pub fn ball(g: &RoleGraph, seeds: &[usize], k: usize) -> Vec<bool> {
let mut inside = vec![false; g.nodes];
let mut frontier: Vec<usize> = seeds.to_vec();
for s in seeds {
inside[*s] = true;
}
for _ in 0..k {
let mut next = Vec::new();
for r in frontier {
for nb in &g.neighbours[r] {
if !inside[*nb as usize] {
inside[*nb as usize] = true;
next.push(*nb as usize);
}
}
}
frontier = next;
}
inside
}
/// The row-normalised adjacency of `g` on GraphBLAS, with only the rows in
/// `rows` (the others empty: their `·x` is 0).
fn adjacency(g: &RoleGraph, rows: &[bool]) -> Result<mimir_graph::Matrix<f64>> {
let n = g.nodes as u64;
let mut offsets: Vec<u64> = Vec::with_capacity(g.nodes + 1);
let mut targets: Vec<u64> = Vec::new();
let mut weights: Vec<f64> = Vec::new();
offsets.push(0);
for (r, nb) in g.neighbours.iter().enumerate() {
if rows[r] && !nb.is_empty() {
let w = 1.0 / nb.len() as f64;
targets.extend(nb.iter().map(|x| *x as u64));
weights.extend(std::iter::repeat_n(w, nb.len()));
}
offsets.push(targets.len() as u64);
}
mimir_graph::Matrix::<f64>::from_csr(n, n, &offsets, &targets, Some(&weights)).map_err(|e| anyhow::anyhow!("role graph: {e}"))
}
/// One propagation step of one column on GraphBLAS: `y = ·x`.
fn step(a: &mimir_graph::Matrix<f64>, x: &[f64]) -> Result<Vec<f64>> {
let xv = mimir_graph::Vector::<f64>::from_dense(x).map_err(|e| anyhow::anyhow!("role column: {e}"))?;
let y = mimir_graph::ops::propagate(a, &xv).map_err(|e| anyhow::anyhow!("propagate: {e}"))?;
let (idx, vals) = y.to_tuples().map_err(|e| anyhow::anyhow!("role column: {e}"))?;
let mut dense = vec![0f64; x.len()];
for (i, v) in idx.into_iter().zip(vals) {
dense[i as usize] = v;
}
Ok(dense)
}
/// **FastRP role vectors.** `only` = the function rows to (re)compute (`None`
/// = every one); `prev` = the vectors of the previous state, kept for every
/// row not recomputed (same row order). The rows `only` names must be the
/// 2-hop ball of what changed: inside it the result equals a full run's.
///
/// Column by column (one `mxv` per step per dimension), so only the
/// functions' three parts are held, never three dense `nodes × dim` blocks.
pub fn role_vectors(f: &Features, g: &RoleGraph, only: Option<&[bool]>, prev: Option<&RoleVectors>) -> Result<RoleVectors> {
let t0 = std::time::Instant::now();
let fns = f.n();
let want: Vec<bool> = match only {
Some(o) => (0..g.nodes).map(|r| o.get(r).copied().unwrap_or(false)).collect(),
None => vec![true; g.nodes],
};
// X2 on `want` needs X1 on its 1-hop ball
let seeds: Vec<usize> = (0..g.nodes).filter(|r| want[*r]).collect();
let need1 = ball(g, &seeds, 1);
// X0: every function's own features, projected (cheap: computed for all)
let mut x0 = vec![0f32; fns * ROLE_DIM];
for r in 0..fns {
let v = &mut x0[r * ROLE_DIM..(r + 1) * ROLE_DIM];
for x in f.sets[r].iter().chain(&f.callers[r]) {
let w = f.idf(*x);
for (d, s) in projection(&f.keys[*x as usize]) {
v[d] += s * w;
}
}
normalize(v);
}
let a1 = adjacency(g, &need1)?;
let a2 = adjacency(g, &want)?;
let rows: Vec<usize> = (0..fns).filter(|r| want[*r]).collect();
let mut x1 = vec![0f32; rows.len() * ROLE_DIM];
let mut x2 = vec![0f32; rows.len() * ROLE_DIM];
let mut col = vec![0f64; g.nodes];
for d in 0..ROLE_DIM {
col.iter_mut().for_each(|c| *c = 0.0);
for r in 0..fns {
col[r] = x0[r * ROLE_DIM + d] as f64;
}
let y1 = step(&a1, &col)?;
let y2 = step(&a2, &y1)?;
for (k, r) in rows.iter().enumerate() {
x1[k * ROLE_DIM + d] = y1[*r] as f32;
x2[k * ROLE_DIM + d] = y2[*r] as f32;
}
}
let mut data = match prev {
Some(p) if p.data.len() == fns * ROLE_DIM => p.data.clone(),
_ => vec![0f32; fns * ROLE_DIM],
};
for (k, r) in rows.iter().enumerate() {
let mut a = x0[r * ROLE_DIM..(r + 1) * ROLE_DIM].to_vec();
let mut b = x1[k * ROLE_DIM..(k + 1) * ROLE_DIM].to_vec();
let mut c = x2[k * ROLE_DIM..(k + 1) * ROLE_DIM].to_vec();
normalize(&mut a);
normalize(&mut b);
normalize(&mut c);
let mut v: Vec<f32> = (0..ROLE_DIM).map(|d| a[d] + W1 * b[d] + W2 * c[d]).collect();
normalize(&mut v);
data[r * ROLE_DIM..(r + 1) * ROLE_DIM].copy_from_slice(&v);
}
Ok(RoleVectors { data, computed: rows.len(), ms: t0.elapsed().as_millis() as u64 })
}
// ── the role space: the seam other readers (the 3D code map) use ────────────
/// One function's role vector, keyed by its STABLE id and the seq of its repo
/// at the state it was computed for.
#[derive(Debug, Clone, PartialEq)]
pub struct RoleVector {
pub stable_id: String,
pub repo: String,
pub seq: i64,
/// The room ordinal (valid for the room it was asked with).
pub ordinal: u64,
/// [`ROLE_DIM`] floats, L2-normalised.
pub vector: Vec<f32>,
}
/// The role vectors of a room.
#[derive(Debug, Clone, Default)]
pub struct RoleSpace {
/// [`ROLE_DIM`].
pub dim: usize,
/// The space name (`fastrp-v1`): vectors of two spaces never mix.
pub space: &'static str,
pub vectors: Vec<RoleVector>,
/// The features the vectors were computed from (row i = `vectors[i]`),
/// for explaining a neighbour ("both return `Plate`").
pub features: Features,
/// `full` / `incremental`; rows (re)computed; rows whose features moved
/// since the kept vectors; rows written back.
pub mode: &'static str,
pub computed: usize,
pub changed: usize,
pub stored: usize,
pub gather_ms: u64,
pub vectors_ms: u64,
}
/// **The role vectors of every own function of `room`** (fn + method nodes of
/// the room's repos with text of their own; tests left out unless `tests`).
///
/// Computed ON READ from the room, and KEPT: the newest stored vector per
/// stable id (`fn_role_vectors` in `wh`) is reused when the function's
/// features did not move; the functions whose features moved and their
/// 2-hop ball are recomputed (all of them when that is a quarter of the room
/// or more, or nothing is kept yet), and what was recomputed is written back
/// when `wh` is writable (a read-only warehouse: computed, not kept).
pub fn role_space(room: &Room, wh: Option<&crate::warehouse::iceberg::IcebergWarehouse>, tests: bool) -> Result<RoleSpace> {
let names: Vec<String> = room.scope().repos.keys().cloned().collect();
let (fns, _) = crate::vector::fnvec::room::function_nodes(room, &names)?;
let ords: Vec<u64> = fns.iter().map(|f| f.ordinal).collect();
role_space_of(room, &ords, wh, tests)
}
/// [`role_space`] over the function nodes the caller already holds (`fns`:
/// `fnvec::room::function_nodes` of the room's repos, in its order) — a lens
/// that read them for its own population does not walk the room twice.
pub fn role_space_of(room: &Room, fns: &[u64], wh: Option<&crate::warehouse::iceberg::IcebergWarehouse>, tests: bool) -> Result<RoleSpace> {
let t0 = std::time::Instant::now();
let mut clock = crate::mimir_lens::clone_inc::Clock::new("role_space");
let ords: Vec<u64> = fns.iter().copied().filter(|o| tests || !room.node(*o).is_test).collect();
let f = gather(room, &ords)?;
clock.lap("gather");
let graph = role_graph(room, &f)?;
clock.lap("graph");
let gather_ms = t0.elapsed().as_millis() as u64;
let stable: Vec<String> = f.fns.iter().map(|o| moniker::stable(room.moniker(*o)).into_owned()).collect();
let kept = match wh {
Some(w) => super::store::read_roles_kept(w)?,
None => std::sync::Arc::new(HashMap::new()),
};
clock.lap("read kept roles");
let hashes: Vec<u64> = (0..f.n()).map(|r| f.hash_of(r)).collect();
let mut prev = RoleVectors { data: vec![0f32; f.n() * ROLE_DIM], ..Default::default() };
let mut changed: Vec<usize> = Vec::new();
for r in 0..f.n() {
match kept.get(&stable[r]) {
Some(p) if p.feat_hash == hashes[r] && p.vector.len() == ROLE_DIM => prev.data[r * ROLE_DIM..(r + 1) * ROLE_DIM].copy_from_slice(&p.vector),
_ => changed.push(r),
}
}
let (vectors, mode) = if kept.is_empty() || changed.len() * 4 > f.n() {
(role_vectors(&f, &graph, None, None)?, "full")
} else {
let only = ball(&graph, &changed, 2);
(role_vectors(&f, &graph, Some(&only), Some(&prev))?, "incremental")
};
clock.lap("vectors");
let seqs = &room.scope().repos;
let mut out_rows: Vec<RoleVector> = Vec::with_capacity(f.n());
let mut write: Vec<super::store::RoleRow> = Vec::new();
for r in 0..f.n() {
let repo = room.node(f.fns[r]).repo.unwrap_or("").to_string();
let seq = seqs.get(&repo).copied().unwrap_or(0);
let v = vectors.row(r).to_vec();
if !kept.get(&stable[r]).is_some_and(|p| p.feat_hash == hashes[r] && p.vector == v) {
write.push(super::store::RoleRow { repo: repo.clone(), stable_id: stable[r].clone(), seq, feat_hash: hashes[r], vector: v.clone(), ts_micros: 0 });
}
out_rows.push(RoleVector { stable_id: stable[r].clone(), repo, seq, ordinal: f.fns[r], vector: v });
}
clock.lap("rows out");
let stored = match wh {
Some(w) if super::store::append_roles_kept(w, &write).is_ok() => write.len(),
_ => 0,
};
clock.lap("write back");
Ok(RoleSpace { dim: ROLE_DIM, space: super::store::ROLE_SPACE, vectors: out_rows, features: f, mode, computed: vectors.computed, changed: changed.len(), stored, gather_ms, vectors_ms: vectors.ms })
}
#[cfg(test)]
mod tests {
use super::*;
fn feats(list: &[(&str, &str)]) -> Vec<(String, String)> {
list.iter().map(|(k, l)| (k.to_string(), l.to_string())).collect()
}
/// A room-sized population: 200 functions that all return `Result<()>`
/// and take `&str` — the common case — plus the pairs under test.
fn population() -> Features {
let mut f = Features::default();
for i in 0..200u64 {
f.push(1000 + i, &feats(&[("r:Result<()>", "return `Result<()>`"), ("p:&str", "take `&str`"), (&format!("c:own{i}"), "call own")]), &[]);
}
f
}
/// The fan-out changes nothing: one worker and eight give the same pairs
/// in the same order, and the allocation-free score equals the full one.
#[test]
fn one_worker_and_many_give_the_same_pairs_and_the_score_needs_no_list() {
let mut f = population();
for i in 0..20u64 {
let g = i / 2;
f.push(1 + i, &feats(&[(&format!("r:T{g}"), "return"), (&format!("f:T{g}#a."), "read a"), (&format!("f:T{g}#b."), "read b"), (&format!("c:x{i}"), "call")]), &[]);
}
let (one, _) = structural_pairs_on(&f, STRUCT_FLOOR, None, 1);
let (many, _) = structural_pairs_on(&f, STRUCT_FLOOR, None, 8);
assert_eq!(one, many);
assert!(!one.is_empty());
for a in 0..f.n() {
for b in 0..f.n() {
let (full, shared) = weighted_jaccard(&f, &f.sets[a], &f.sets[b]);
let (score, n) = jaccard_score(&f, &f.sets[a], &f.sets[b]);
assert!((full - score).abs() < 1e-6 && n == shared.len(), "{a} {b}");
}
}
}
/// KILL and PERVERT: unrelated names, different bodies (different callees),
/// the same rare return type and the same fields read → high on signal 2.
#[test]
fn unrelated_names_sharing_a_rare_return_type_and_fields_are_structural_clones() {
let mut f = population();
let rare = [("r:MapLayout", "return `MapLayout`"), ("t:MapLayout#", "use type `MapLayout`"), ("f:MapLayout#repos.", "read `.MapLayout.repos`"), ("f:MapLayout#plates.", "read `.MapLayout.plates`")];
let mut kill = rare.to_vec();
kill.extend([("c:a", "call `a`"), ("p:&str", "take `&str`")]);
let mut pervert = rare.to_vec();
pervert.extend([("c:b", "call `b`"), ("p:&str", "take `&str`")]);
f.push(1, &feats(&kill), &[]);
f.push(2, &feats(&pervert), &[]);
// two functions that only share `Result<()>` (and `&str`)
f.push(3, &feats(&[("r:Result<()>", "return `Result<()>`"), ("p:&str", "take `&str`"), ("c:x", "call x")]), &[]);
f.push(4, &feats(&[("r:Result<()>", "return `Result<()>`"), ("p:&str", "take `&str`"), ("c:y", "call y")]), &[]);
let (pairs, stats) = structural_pairs(&f, STRUCT_FLOOR, None);
let (k, p, a, b) = (200, 201, 202, 203);
let hit = pairs.iter().find(|x| (x.a, x.b) == (k, p)).unwrap_or_else(|| panic!("KILL/PERVERT not found: {pairs:?} {stats:?}"));
assert!(hit.score >= 0.6, "{hit:?}");
let words = shared_words(&f, &hit.shared, 6).join(", ");
assert!(words.contains("return `MapLayout`") && words.contains("read `.MapLayout.repos`"), "{words}");
assert!(!words.starts_with("both take `&str`"), "the common feature must rank last: {words}");
assert!(!pairs.iter().any(|x| (x.a, x.b) == (a, b)), "sharing only Result<()> is not structure");
// and directly: the weight of what they share is almost nothing
let (j, _) = weighted_jaccard(&f, &f.sets[a], &f.sets[b]);
assert!(j < 0.2, "{j}");
}
/// The role graph of a hand-built population: one node per function, one
/// per `t:` / `f:` / `c:` / `k:` key (the type, field, callee, caller).
fn graph_of(f: &Features) -> RoleGraph {
let mut rows: HashMap<String, usize> = HashMap::new();
let mut adj: Vec<BTreeSet<u32>> = vec![BTreeSet::new(); f.n()];
for r in 0..f.n() {
for x in f.sets[r].iter().chain(&f.callers[r]) {
let k = &f.keys[*x as usize];
if !(k.starts_with("t:") || k.starts_with("f:") || k.starts_with("c:") || k.starts_with("k:")) {
continue;
}
let next = adj.len();
let node = *rows.entry(k[2..].to_string()).or_insert(next);
if node == adj.len() {
adj.push(BTreeSet::new());
}
adj[r].insert(node as u32);
adj[node].insert(r as u32);
}
}
RoleGraph { nodes: adj.len(), neighbours: adj.into_iter().map(|s| s.into_iter().collect()).collect() }
}
fn cos(a: &[f32], b: &[f32]) -> f32 {
a.iter().zip(b).map(|(x, y)| x * y).sum()
}
/// The owner's case for the role vectors: two functions with unrelated
/// names that play the same role (the same rare types, the same callees,
/// one caller) are each other's nearest neighbours; a lone utility is not
/// near them. Then one function changes: recomputing its 2-hop ball gives
/// exactly what a full run gives there, and leaves the rest untouched.
#[test]
fn functions_in_the_same_role_are_nearest_neighbours_and_a_lone_utility_is_not() {
let mut f = population();
let role = [("t:Plate#", "use type `Plate`"), ("r:Plate", "return `Plate`"), ("c:layout/place().", "call `layout::place`"), ("c:layout/measure().", "call `layout::measure`"), ("f:Plate#rect.", "read `.Plate.rect`")];
let mut kill = role.to_vec();
kill.push(("c:k_only", "call k_only"));
let mut pervert = role.to_vec();
pervert.push(("c:p_only", "call p_only"));
let caller = [("k:render().", "are called by `render`")];
f.push(1, &feats(&kill), &feats(&caller));
f.push(2, &feats(&pervert), &feats(&caller));
f.push(3, &feats(&[("p:u64", "take `u64`"), ("r:u64", "return `u64`"), ("c:core/rotate_left().", "call rotate_left")]), &[]);
let (k, p, lone) = (200, 201, 202);
let g = graph_of(&f);
let full = role_vectors(&f, &g, None, None).unwrap();
assert_eq!(full.computed, f.n());
let nearest = |i: usize| (0..f.n()).filter(|j| *j != i).max_by(|a, b| cos(full.row(i), full.row(*a)).total_cmp(&cos(full.row(i), full.row(*b)))).unwrap();
assert_eq!(nearest(k), p, "KILL's nearest is PERVERT");
assert_eq!(nearest(p), k);
let kp = cos(full.row(k), full.row(p));
assert!(kp > 0.8, "{kp}");
assert!(cos(full.row(k), full.row(lone)) < 0.3 && cos(full.row(p), full.row(lone)) < 0.3, "the lone utility is near nobody in the role");
// PERVERT changes: it stops calling `measure`
let mut changed = f.clone();
let fid = changed.keys.iter().position(|x| x == "c:layout/measure().").unwrap() as u32;
changed.sets[p].retain(|x| *x != fid);
changed.recount();
let g2 = graph_of(&changed);
let only = ball(&g2, &[p], 2);
let inc = role_vectors(&changed, &g2, Some(&only), Some(&full)).unwrap();
let all = role_vectors(&changed, &g2, None, None).unwrap();
assert!(inc.computed < changed.n() / 2, "only the ball is recomputed: {}", inc.computed);
for r in 0..changed.n() {
if only[r] {
assert_eq!(inc.row(r), all.row(r), "row {r} inside the ball equals the full run");
} else {
assert_eq!(inc.row(r), full.row(r), "row {r} outside the ball is kept");
}
}
assert_ne!(inc.row(p), full.row(p));
}
}