src/mimir_lens/room_feed/graph_first.rs
//! **Graph first** — what every vector lens shares now that the compiled
//! graph is the PRIMARY index and the embeddings an OPTIONAL one beside it.
//!
//! * The GRAPH index answers on its own: the code room the rustc driver's MIR
//! dump built (CALLS, USES_TYPE, READS_FIELD, params, the `->` part, names,
//! spans) and the shapes cut by its spans. No model, no vector, no worker.
//! * The EMBEDDING index, when it holds vectors, proposes its own pairs; they
//! are ADDED beside the graph's with their cosine as an extra score. When it
//! holds none, the note says it added nothing — the answer is still
//! complete, never `partial`, never "no vector store".
//! * Every finding says which index found it: `graph`, `embedding` or `both`
//! (`source`), and the answer counts them per index (`indexes`, and one
//! basis row per index).
//!
//! The graph's candidate generator is the rare-feature POSTING pass of
//! [`structure::structural_pairs`]: an inverted index over the features
//! (callee / type / field / param / return ids, or name words) that at most
//! [`structure::RARE_DF`] functions share. It is exact where MinHash / LSH
//! banding is approximate — every pair that shares a rare feature is scored
//! by the same rarity-weighted Jaccard, so nothing above the bar is lost to a
//! band collision — and on the live room (≈10⁵ functions) it is one pass.
use std::collections::{BTreeMap, HashMap, HashSet};
use serde_json::{Value, json};
use super::Basis;
use crate::clone_signals::structure::{self, Features, StructPair};
use crate::mimir_lens::clone_inc as inc;
/// The words every note uses when the embedding index had nothing to add.
pub const IDLE: &str = "the embedding index added nothing";
/// `graph` / `embedding` / `both`.
pub fn source(graph: bool, embedding: bool) -> &'static str {
match (graph, embedding) {
(true, true) => "both",
(false, true) => "embedding",
_ => "graph",
}
}
/// The note when the embedding index holds no vector: why, and that the
/// graph answered alone.
pub fn idle_note(why: &str) -> String {
format!("{IDLE} — {why}. The graph index (the compiled code room) answered alone, and the answer is complete without it")
}
/// The answer's per-index counts over its findings (`source` of each), and
/// one basis row per index: the candidate pairs each proposed.
pub fn count(basis: &mut Basis, findings: &[&Value], graph_pairs: usize, embedding_pairs: usize, graph_root: &str, embedding_root: &str) -> Value {
let mut by: BTreeMap<&str, usize> = [("graph", 0), ("embedding", 0), ("both", 0)].into();
for f in findings {
if let Some(s) = f["source"].as_str() {
*by.entry(s).or_default() += 1;
}
}
basis.fact("graph index: candidate pairs from the compiled graph", graph_pairs, graph_root.to_string());
basis.fact("embedding index: candidate pairs from the vectors", embedding_pairs, embedding_root.to_string());
json!({
"graph": by["graph"],
"embedding": by["embedding"],
"both": by["both"],
"graph_pairs": graph_pairs,
"embedding_pairs": embedding_pairs,
})
}
/// The fingerprint of a feature population: every row's key in order with
/// its feature hash, and the pass's parameters.
pub fn population_fp(keys: &[u64], f: &Features, params: u64) -> u64 {
let mut fp = inc::Fp::default().add(¶ms).add(&keys.len());
for (r, k) in keys.iter().enumerate() {
fp = fp.add(k).add(&f.hash_of(r));
}
fp.fin()
}
/// [`structure::structural_pairs`] at `floor`, KEPT per `scope_key`: carried
/// while the population's fingerprint holds (the same rows, the same features
/// — the full pass's own output), else recomputed and kept.
pub fn struct_pairs(scope_key: &str, keys: &[u64], f: &Features, floor: f32) -> Vec<StructPair> {
let fp = population_fp(keys, f, inc::Fp::default().add(&floor.to_bits()).fin());
inc::graph_pairs(scope_key, fp, || structure::structural_pairs(f, floor, None).0).0
}
/// Mutual k nearest over scored pairs: `(a, b)` survives when each is among
/// the other's `k` best (ties by index). The graph's own hub guard.
pub fn mutual(pairs: &[(usize, usize, f32)], k: usize) -> HashSet<(usize, usize)> {
let mut near: HashMap<usize, Vec<(f32, usize)>> = HashMap::new();
for (a, b, s) in pairs {
near.entry(*a).or_default().push((*s, *b));
near.entry(*b).or_default().push((*s, *a));
}
let top: HashMap<usize, HashSet<usize>> = near
.into_iter()
.map(|(r, mut v)| {
v.sort_by(|x, y| y.0.total_cmp(&x.0).then(x.1.cmp(&y.1)));
(r, v.into_iter().take(k).map(|x| x.1).collect())
})
.collect();
pairs.iter().filter(|(a, b, _)| top.get(a).is_some_and(|t| t.contains(b)) && top.get(b).is_some_and(|t| t.contains(a))).map(|(a, b, _)| (*a.min(b), *a.max(b))).collect()
}
/// The words of an identifier: `snake_case` and `CamelCase` split, lower
/// case, digits kept on their word, one-letter words dropped.
pub fn words(ident: &str) -> Vec<String> {
let mut out = Vec::new();
for part in ident.split(|c: char| !c.is_alphanumeric()) {
let mut cur = String::new();
let mut prev_lower = false;
for c in part.chars() {
if c.is_uppercase() && prev_lower && !cur.is_empty() {
out.push(std::mem::take(&mut cur));
}
prev_lower = c.is_lowercase() || c.is_ascii_digit();
cur.extend(c.to_lowercase());
}
if !cur.is_empty() {
out.push(cur);
}
}
out.retain(|w| w.len() > 1 && w != "self");
out.sort();
out.dedup();
out
}
/// A function's NAME features for the graph's name-driven index: the words
/// of its own name and of its parameters' names, as the compiled graph holds
/// them (`n:<word>`).
pub fn name_features(name: &str, params: &[String]) -> Vec<(String, String)> {
let mut ws = words(name);
for p in params {
ws.extend(words(p));
}
ws.sort();
ws.dedup();
ws.into_iter().map(|w| (format!("n:{w}"), format!("say `{w}`"))).collect()
}
/// The name-word Jaccard floor of the graph's name-driven pairs (`same_intent`).
pub const NAME_FLOOR: f32 = 0.5;
/// A [`Features`] over `rows` (`(ordinal, features)`), interned and counted in
/// ONE pass ([`Features::push`] recounts per row: quadratic at room size).
pub fn features_of(rows: impl Iterator<Item = (u64, Vec<(String, String)>)>) -> Features {
let mut f = Features::default();
let mut intern: HashMap<String, u32> = HashMap::new();
for (o, feats) in rows {
let mut v: Vec<u32> = feats
.into_iter()
.map(|(k, l)| {
*intern.entry(k.clone()).or_insert_with(|| {
f.keys.push(k);
f.labels.push(l);
(f.keys.len() - 1) as u32
})
})
.collect();
v.sort_unstable();
v.dedup();
f.fns.push(o);
f.sets.push(v);
f.callers.push(Vec::new());
}
f.df = vec![0; f.keys.len()];
for set in &f.sets {
for x in set {
f.df[*x as usize] += 1;
}
}
f
}
/// The graph's NAME pairs: functions whose names (and parameter names) share
/// rare words, rarity-weighted Jaccard ≥ `floor`, at least two shared words,
/// each function at least two words. Rows `a < b` of `f`.
pub fn name_pairs(f: &Features, floor: f32) -> Vec<StructPair> {
let n = f.n();
let cap = structure::RARE_DF.min((n / 2).max(2) as u32);
let mut postings: HashMap<u32, Vec<usize>> = HashMap::new();
for (r, set) in f.sets.iter().enumerate() {
if set.len() < 2 {
continue;
}
for x in set {
if (2..=cap).contains(&f.df[*x as usize]) {
postings.entry(*x).or_default().push(r);
}
}
}
let mut out = Vec::new();
let mut partners: Vec<usize> = Vec::new();
for (r, set) in f.sets.iter().enumerate() {
if set.len() < 2 {
continue;
}
partners.clear();
for x in set {
if let Some(p) = postings.get(x) {
partners.extend(p.iter().copied().filter(|j| *j > r));
}
}
partners.sort_unstable();
partners.dedup();
for &j in &partners {
let (score, shared) = structure::weighted_jaccard(f, set, &f.sets[j]);
if score >= floor && shared.len() >= 2 {
out.push(StructPair { a: r, b: j, score, shared });
}
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn words_split_snake_and_camel_case() {
assert_eq!(words("bump_alphaLanes"), ["alpha", "bump", "lanes"]);
assert_eq!(words("now_unix_ms"), ["ms", "now", "unix"]);
assert_eq!(words("self"), Vec::<String>::new());
assert_eq!(words("HTTPServer"), ["httpserver"]);
}
#[test]
fn mutual_keeps_only_pairs_each_side_ranks_high() {
// 0's best is 1, 1's best is 0; 2 likes 0 but 0 does not rank 2 first
let pairs = [(0, 1, 0.9), (0, 2, 0.5), (1, 2, 0.1)];
let m = mutual(&pairs, 1);
assert!(m.contains(&(0, 1)) && !m.contains(&(0, 2)) && !m.contains(&(1, 2)), "{m:?}");
}
#[test]
fn name_pairs_need_two_shared_rare_words() {
let mut f = Features::default();
let add = |f: &mut Features, o: u64, name: &str, params: &[&str]| f.push(o, &name_features(name, ¶ms.iter().map(|s| s.to_string()).collect::<Vec<_>>()), &[]);
add(&mut f, 0, "bump_alpha", &["xs", "by"]);
add(&mut f, 1, "bump_beta", &["xs", "by"]);
add(&mut f, 2, "workspace_root", &[]);
add(&mut f, 3, "repo_root", &[]);
for i in 0..8 {
add(&mut f, 10 + i, &format!("other{i}_thing{i}"), &[]);
}
let p = name_pairs(&f, 0.5);
assert_eq!(p.iter().map(|x| (x.a, x.b)).collect::<Vec<_>>(), [(0, 1)], "{p:?}");
}
}