src/mimir_lens/room_feed/reuse.rs
//! **`reimplements_shared`** — a library re-implemented by a crate that
//! already imports it. One graph query over what the room already holds:
//!
//! * the copy / twin pairs of `semantic_twins` and `similar_code` (both
//! indexes, graph and embedding), read from their KEPT answers — this lens
//! folds nothing of its own;
//! * the `DEPENDS_ON` edges between crate nodes: crate A has a path to crate
//! B, so B is the library and A the consumer (Cargo has no cycles — the
//! direction is never a guess);
//! * the `CALLS` edges (A calling B already is a wrapper, no finding), the
//! `param` / `ret` parts (a drop-in or an adapter) and B's effective
//! visibility (callable from A, or `pub` first).
//!
//! A finding: replace A's function with a call to B's. Left out and counted:
//! test code, two functions of one package, pairs with no dependency either
//! way (twins of peers — `semantic_twins` lists them), and wrappers.
use std::collections::{BTreeMap, HashMap, HashSet};
use mimir_schema::{EdgeKind, kind as nk, moniker};
use serde_json::{Value, json};
use super::clones::{Sources, path_excluded, population_with, test_like};
use super::graph::{Graph, internal};
use super::{Basis, Query, Warehouse};
use crate::code_room::{Reach, Refusal};
type Answered = Result<(Basis, Value), Refusal>;
/// A twin-only pair (no copy evidence) needs this much shared body (MinHash).
pub const TWIN_BODY_FLOOR: f64 = 0.3;
/// The lines a finding's rank counts at most.
pub const RANK_LINES_CAP: u64 = 30;
/// The lenses whose pairs are read, each asked for every finding it has.
const SOURCES: [&str; 2] = ["semantic_twins", "similar_code"];
/// The `limit` the pair lenses are asked with: every finding (one kept answer each).
const PAIRS_LIMIT: u64 = 1_000_000;
/// A function's parameter types (`self` left out: the receiver's type is
/// the type's own) and its return type.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Signature {
pub params: Vec<String>,
pub ret: Option<String>,
}
/// `drop_in` when the call can replace the body as it is (the same
/// parameter and return types), else `adapter`.
pub fn fit(a: &Signature, b: &Signature) -> &'static str {
if a == b { "drop_in" } else { "adapter" }
}
/// How A's crate has the library: `Direct` = a normal, non-optional
/// dependency of A's OWN manifest (call it now); anything else — reached only
/// through another crate, optional, or a dev-dependency — needs a dependency
/// added first.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Tier {
Direct,
AddDependency,
}
/// The direct, non-optional, non-dev dependencies (package names, `-` and `_`
/// alike) of the manifest text of A's package.
pub fn direct_deps(manifest: &str) -> HashSet<String> {
let norm = |s: &str| s.replace('_', "-");
let Ok(t) = manifest.parse::<toml::Table>() else { return HashSet::new() };
let mut out = HashSet::new();
let mut take = |deps: Option<&toml::Value>| {
for (key, spec) in deps.and_then(toml::Value::as_table).into_iter().flatten() {
if spec.get("optional").and_then(toml::Value::as_bool).unwrap_or(false) {
continue;
}
let name = spec.get("package").and_then(toml::Value::as_str).unwrap_or(key);
out.insert(norm(name));
}
};
take(t.get("dependencies"));
for (_, target) in t.get("target").and_then(toml::Value::as_table).into_iter().flatten() {
take(target.get("dependencies"));
}
out
}
/// The manifest of `package` around `file` in the clone at `root`: the
/// nearest `Cargo.toml` up from the file whose `[package] name` is it.
fn manifest_of(root: &std::path::Path, file: &str, package: &str) -> Option<String> {
let mut dir = root.join(file);
while dir.pop() {
if !dir.starts_with(root) {
return None;
}
let m = dir.join("Cargo.toml");
if let Ok(text) = std::fs::read_to_string(&m) {
let named = text.parse::<toml::Table>().ok().and_then(|t| t.get("package")?.get("name")?.as_str().map(str::to_string));
if named.as_deref() == Some(package) {
return Some(text);
}
}
}
None
}
/// An identifier both bodies read that each crate defines for itself — an
/// ALL_CAPS name used without a path (`REGISTRY`, `TABLE`): the two bodies are
/// one text over two different statics or consts, so a call into the library
/// would read the library's, not A's.
pub fn own_statics(a: &str, b: &str) -> Vec<String> {
let caps = |t: &str| -> HashSet<String> {
let mut out = HashSet::new();
let bytes: Vec<char> = t.chars().collect();
let mut i = 0;
while i < bytes.len() {
if bytes[i].is_ascii_uppercase() && (i == 0 || !(bytes[i - 1].is_alphanumeric() || bytes[i - 1] == '_' || bytes[i - 1] == ':')) {
let start = i;
while i < bytes.len() && (bytes[i].is_ascii_uppercase() || bytes[i].is_ascii_digit() || bytes[i] == '_') {
i += 1;
}
let word: String = bytes[start..i].iter().collect();
let next = bytes.get(i).copied().unwrap_or(' ');
if word.len() >= 3 && !(next.is_alphanumeric() || next == ':' || next == '(' || next == '{') {
out.insert(word);
}
} else {
i += 1;
}
}
out
};
let mut v: Vec<String> = caps(a).intersection(&caps(b)).cloned().collect();
v.sort();
v
}
/// Is `file` a library target's source (not an example, a bench, a test or a
/// binary's)?
fn library_file(file: &str) -> bool {
path_excluded(file).is_none() && !file.contains("/bin/") && !file.starts_with("bin/") && !file.ends_with("main.rs") && !file.contains("tests/")
}
/// One pair as a pair lens found it.
struct Pair {
a: String,
b: String,
similarity: f64,
evidence: Value,
}
/// The pairs of one kept answer: `semantic_twins` names two members per
/// finding, `similar_code` a cluster (every two of its members are a pair).
fn pairs_of(lens: &str, v: &Value) -> Vec<Pair> {
let mut out = Vec::new();
for f in v["worst"].as_array().into_iter().flatten() {
let ids: Vec<String> = f["members"].as_array().into_iter().flatten().filter_map(|m| m["id"].as_str()).map(|id| moniker::stable(id).into_owned()).collect();
let similarity = ["cosine", "avg_cosine", "body_similarity", "graph_score", "structural"].iter().find_map(|k| f[*k].as_f64()).unwrap_or(0.0).clamp(0.0, 1.0);
let evidence = json!({
"lens": lens,
"kind": f["kind"],
"source": f["source"],
"cosine": f.get("cosine").or_else(|| f.get("avg_cosine")),
"structural": f.get("structural").or_else(|| f.get("graph_score")),
"body_similarity": f.get("body_similarity"),
});
// a similar_code cluster names its real pairs: only those are pairs
if let Some(ps) = f["pairs"].as_array().filter(|_| lens == "similar_code") {
for p in ps {
if let (Some(a), Some(b)) = (p["a"].as_str(), p["b"].as_str()) {
out.push(Pair { a: moniker::stable(a).into_owned(), b: moniker::stable(b).into_owned(), similarity, evidence: evidence.clone() });
}
}
continue;
}
for i in 0..ids.len() {
for j in i + 1..ids.len() {
out.push(Pair { a: ids[i].clone(), b: ids[j].clone(), similarity, evidence: evidence.clone() });
}
}
}
out
}
/// The crate node a function sits in (its `parent` chain's crate).
fn crate_of(room: &mimir_room::Room, ordinal: u64) -> Option<u64> {
let mut cur = ordinal;
for _ in 0..64 {
let n = room.node(cur);
if n.kind == Some(nk::CRATE) {
return Some(cur);
}
cur = n.parent?;
}
None
}
/// The package a node's moniker names (`nornir-build-thing`).
fn package(room: &mimir_room::Room, ordinal: u64) -> String {
moniker::parse(room.moniker(ordinal)).map(|(p, _, _)| p.to_string()).unwrap_or_default()
}
fn signature(room: &mimir_room::Room, ordinal: u64) -> Result<Signature, Refusal> {
let mut params = Vec::new();
let mut ret = None;
for (_, c) in room.out_pairs(EdgeKind::Contains, &[ordinal]).map_err(internal)? {
let c = room.node(c);
match c.kind {
Some(nk::PARAM) if c.name != Some("self") => params.push(c.ty.unwrap_or("?").to_string()),
Some(nk::RET) => ret = c.ty.map(str::to_string),
_ => {}
}
}
Ok(Signature { params, ret })
}
fn place(room: &mimir_room::Room, ordinal: u64) -> Value {
let n = room.node(ordinal);
json!({
"id": moniker::stable(n.moniker),
"name": n.name,
"crate": package(room, crate_of(room, ordinal).unwrap_or(ordinal)),
"version": n.version,
"repo": n.repo,
"path": room.display_path(ordinal),
"file": n.file,
"line": n.start_line,
"end_line": n.end_line,
})
}
pub fn reimplements_shared(reach: &Reach<'_>, wh: &Warehouse<'_>, q: &Query<'_>) -> Answered {
let t0 = std::time::Instant::now();
let mut basis = Basis::default();
// the pairs: each pair lens's kept answer (folded now and kept when the
// room moved since — the next ask of either lens is served from it)
let mut pairs: Vec<Pair> = Vec::new();
let mut read: BTreeMap<&str, usize> = BTreeMap::new();
for lens in SOURCES {
// every PAIR (semantic_twins collapses its list into classes otherwise)
let v = crate::mimir_lens::queued::kept_or_fold(lens, reach, &if lens == "semantic_twins" { json!({ "limit": PAIRS_LIMIT, "pairs": true }) } else { json!({ "limit": PAIRS_LIMIT }) });
let state = v["lens_meta"]["state"].as_str().unwrap_or("?");
match state {
"complete" | "empty_fact" => {}
"partial" | "empty_gap" => basis.note(format!("`{lens}` answered `{state}`: its pairs are a lower bound")),
_ => {
basis.gap(format!("`{lens}` answered `{state}`: its pairs are not read — {}", v["lens_meta"]["error"].as_str().or(v["evidence_note"].as_str()).unwrap_or("")));
continue;
}
}
let p = pairs_of(lens, &v);
basis.fact(format!("{lens} pairs (kept answer)"), p.len(), "Mimir lens answer cache");
read.insert(lens, p.len());
pairs.extend(p);
}
let t_pairs = t0.elapsed().as_millis();
let g = Graph::open(reach, q, &mut basis)?;
let room = &g.room;
let pop = population_with(&g, wh, &mut basis, false)?;
let ord_of = |id: &str| pop.by_id.get(id).map(|i| pop.funcs[*i].ordinal);
// every function a pair names, resolved; the crates they sit in
let mut resolved: Vec<(u64, u64, &Pair)> = Vec::new();
let mut unresolved = 0usize;
for p in &pairs {
match (ord_of(&p.a), ord_of(&p.b)) {
(Some(a), Some(b)) if a != b => resolved.push((a, b, p)),
_ => unresolved += 1,
}
}
let mut crate_at: HashMap<u64, Option<u64>> = HashMap::new();
for &(a, b, _) in &resolved {
for o in [a, b] {
crate_at.entry(o).or_insert_with(|| crate_of(room, o));
}
}
// the dependency closure of every crate a pair touches: the crate nodes
// DEPENDS_ON reaches, and their packages (a dependency on another
// version of a workspace crate is the same library)
let mut crates: Vec<u64> = crate_at.values().flatten().copied().collect::<HashSet<_>>().into_iter().collect();
crates.sort_unstable();
let walks = room.reach_each(&crates, &[EdgeKind::DependsOn], None, None).map_err(internal)?;
let mut deps: HashMap<u64, (HashSet<u64>, HashSet<String>)> = HashMap::new();
for (c, w) in crates.iter().zip(walks) {
let reached: HashSet<u64> = w.value.reached.into_iter().filter(|r| r != c).collect();
let packages = reached.iter().map(|r| package(room, *r)).collect();
deps.insert(*c, (reached, packages));
}
let imports = |from: u64, to: u64| -> bool { deps.get(&from).is_some_and(|(o, p)| o.contains(&to) || p.contains(&package(room, to))) };
let consumers: Vec<u64> = {
let mut v: Vec<u64> = resolved.iter().flat_map(|(a, b, _)| [*a, *b]).collect::<HashSet<_>>().into_iter().collect();
v.sort_unstable();
v
};
let calls: HashSet<(u64, u64)> = room.out_pairs(EdgeKind::Calls, &consumers).map_err(internal)?.into_iter().collect();
let callers: HashMap<u64, u64> = room.fan_in(EdgeKind::Calls, None).map_err(internal)?.value.into_iter().collect();
let mut left_out: BTreeMap<&'static str, usize> = BTreeMap::new();
// (consumer, library) → the best similarity and every lens's evidence
let mut found: BTreeMap<(u64, u64), (f64, Vec<Value>)> = BTreeMap::new();
for (x, y, p) in &resolved {
let (Some(cx), Some(cy)) = (crate_at[x], crate_at[y]) else {
*left_out.entry("no crate node").or_default() += 1;
continue;
};
let test = |o: u64| {
let n = room.node(o);
n.is_test || test_like(&room.display_path(o), n.file.unwrap_or(""))
};
if test(*x) || test(*y) {
*left_out.entry("test code").or_default() += 1;
continue;
}
if cx == cy || package(room, cx) == package(room, cy) {
*left_out.entry("one package").or_default() += 1;
continue;
}
let (a, b) = if imports(cx, cy) {
(*x, *y)
} else if imports(cy, cx) {
(*y, *x)
} else {
*left_out.entry("no dependency either way (peers: twins, not a re-implementation)").or_default() += 1;
continue;
};
if calls.contains(&(a, b)) {
*left_out.entry("already calls the library (a wrapper)").or_default() += 1;
continue;
}
if !q.repo.is_empty() && room.node(a).repo != Some(q.repo) {
continue;
}
let e = found.entry((a, b)).or_insert((0.0, Vec::new()));
e.0 = e.0.max(p.similarity);
e.1.push(p.evidence.clone());
}
// the GATED pair decides: semantic_twins' gates (families, mutual kNN,
// bodies) passed it; a similar_code cluster names every two of its
// members, so a pair it alone names only adds evidence
let gated = |ev: &[Value]| ev.iter().any(|e| e["lens"] == "semantic_twins");
let before = found.len();
found.retain(|_, (_, ev)| gated(ev));
if before > found.len() {
*left_out.entry("only similar_code's cluster (no gated twin pair)").or_default() += before - found.len();
}
let mut rows: Vec<(f64, u64, Value)> = Vec::new();
let mut src = Sources::new(&g.layout);
let mut manifests: HashMap<(String, String), HashSet<String>> = HashMap::new();
for ((a, b), (similarity, evidence)) in found {
let (na, nb) = (room.node(a), room.node(b));
// the LIBRARY side: public API of a library target
let public = nb.effective_visibility.map(|v| v.is_public_api());
if public == Some(false) || !library_file(nb.file.unwrap_or("")) {
*left_out.entry("the library side is not a public fn of a library target").or_default() += 1;
continue;
}
// a twin only (no copy evidence) must share some text with it
let copy = evidence.iter().any(|e| e["kind"] == "copy" || e["lens"] == "similar_code");
let body = evidence.iter().filter_map(|e| e["body_similarity"].as_f64()).fold(f64::NAN, f64::max);
if !copy && !(body >= TWIN_BODY_FLOOR) {
*left_out.entry("a twin sharing under 0.3 of the body (another algorithm for the same idea)").or_default() += 1;
continue;
}
let lib = package(room, crate_at[&b].unwrap_or(b));
let pkg_a = package(room, crate_at[&a].unwrap_or(a));
let repo_a = na.repo.unwrap_or("").to_string();
// how A's crate has the library: its OWN manifest, normal and non-optional
let deps = manifests.entry((repo_a.clone(), pkg_a.clone())).or_insert_with(|| {
manifest_of(&g.layout.clone_of(&repo_a), na.file.unwrap_or(""), &pkg_a).map(|m| direct_deps(&m)).unwrap_or_default()
});
let tier = if deps.contains(&lib.replace('_', "-")) { Tier::Direct } else { Tier::AddDependency };
let lines = u64::from(na.end_line.unwrap_or(0).saturating_sub(na.start_line.unwrap_or(0)) + 1);
let n_callers = callers.get(&a).copied().unwrap_or(0);
let (sa, sb) = (signature(room, a)?, signature(room, b)?);
let mut fit = fit(&sa, &sb).to_string();
// one text over two crates' own statics: a call would read the library's
let text = |o: u64, n: &mimir_room::NodeView<'_>, src: &mut Sources<'_>| src.text(n.repo.unwrap_or(""), n.file.unwrap_or(""), n.start_line.unwrap_or(0), n.end_line.unwrap_or(0)).unwrap_or_else(|| room.display_path(o));
let (ta, tb) = (text(a, &na, &mut src), text(b, &nb, &mut src));
let statics = own_statics(&ta, &tb);
let path_b = room.display_path(b);
let path_a = room.display_path(a);
let mut action = match (tier, public) {
(Tier::Direct, _) => format!("replace `{path_a}` with a call to `{path_b}`"),
(Tier::AddDependency, _) => format!("add `{lib}` to `{pkg_a}`'s [dependencies], then replace `{path_a}` with a call to `{path_b}`"),
};
if !statics.is_empty() {
fit = "partial".to_string();
action = format!("{action} — but each reads its OWN {}: the library's would differ; pass it in or keep the copy", statics.iter().map(|w| format!("`{w}`")).collect::<Vec<_>>().join(", "));
}
// rank: similarity × callers, the lines capped (a long copy is not a better finding)
let score = similarity * (1.0 + (n_callers as f64).ln_1p()) * (lines.min(RANK_LINES_CAP) as f64) * if tier == Tier::Direct { 1.0 } else { 0.5 };
rows.push((
score,
a,
json!({
"kind": "reimplements_shared",
"tier": if tier == Tier::Direct { "already_imports" } else { "add_dependency" },
"replace": place(room, a),
"use_instead": place(room, b),
"library": lib,
"fit": fit,
"partial": !statics.is_empty(),
"own_statics": statics,
"signature": { "replace": { "params": sa.params, "ret": sa.ret }, "use_instead": { "params": sb.params, "ret": sb.ret } },
"use_instead_public": public,
"action": action,
"why": match tier {
Tier::Direct => format!("`{pkg_a}` depends on `{lib}` directly and holds a copy of `{path_b}` (similarity {similarity:.2}): call it"),
Tier::AddDependency => format!("`{pkg_a}` reaches `{lib}` only through another crate, an optional or a dev dependency, and holds a copy of `{path_b}` (similarity {similarity:.2})"),
},
"evidence": evidence,
"gain": { "lines": lines, "callers": n_callers },
"similarity": similarity,
"score": score,
}),
));
}
// ONE finding per function to replace: its best library function, the
// other candidates (the same copy in more than one imported crate) beside it
rows.sort_by(|x, y| y.0.total_cmp(&x.0));
let pairs_kept = rows.len();
let mut per_fn: Vec<(f64, Value)> = Vec::new();
let mut at: HashMap<u64, usize> = HashMap::new();
for (score, a, row) in rows {
match at.get(&a) {
Some(&i) => {
let also = per_fn[i].1["also"].as_array_mut().expect("also");
also.push(json!({ "use_instead": row["use_instead"]["path"], "library": row["library"], "fit": row["fit"], "similarity": row["similarity"] }));
}
None => {
let mut row = row;
row["also"] = json!([]);
at.insert(a, per_fn.len());
per_fn.push((score, row));
}
}
}
// the direct tier first, then what needs a dependency added
per_fn.sort_by(|x, y| (x.1["tier"] != "already_imports").cmp(&(y.1["tier"] != "already_imports")).then(y.0.total_cmp(&x.0)));
let total = per_fn.len();
let direct = per_fn.iter().filter(|r| r.1["tier"] == "already_imports").count();
let drop_in = per_fn.iter().filter(|r| r.1["fit"] == "drop_in").count();
let worst: Vec<Value> = per_fn.into_iter().take(q.limit).map(|r| r.1).collect();
let left: Vec<String> = left_out.iter().map(|(w, n)| format!("{n} {w}")).collect();
let read_line: Vec<String> = read.iter().map(|(l, n)| format!("{n} from `{l}`")).collect();
let note = format!(
"reimplements_shared: {total} function(s) re-implement a library their crate already imports ({drop_in} drop-in, {} need an adapter; {pairs_kept} pair(s), \
one finding per function, its other library candidates under `also`). Read {} pair(s) ({}) from the kept answers and joined them with DEPENDS_ON: \
crate A depends on crate B and A holds a copy or twin of a B function — a pair semantic_twins' gates passed; similar_code's clusters add evidence — \
so B is the library (Cargo has no cycles: the direction is the graph's, never a guess). Left out: {}; {unresolved} pair(s) named a function the room \
does not hold. Ranked by similarity × lines × (1 + callers). `group_twins` (statement groups inside one repo) is not read: a fragment is not a function \
to call. {} ms reading the pairs, {} ms in all.",
total - drop_in,
pairs.len(),
if read_line.is_empty() { "none".to_string() } else { read_line.join(", ") },
if left.is_empty() { "nothing".to_string() } else { left.join(", ") },
t_pairs,
t0.elapsed().as_millis(),
);
Ok((
basis,
json!({
"kind": "reimplements_shared",
"findings": total,
"functions": total,
"already_imports": direct,
"add_dependency": total - direct,
"pairs_kept": pairs_kept,
"drop_in": drop_in,
"pairs_read": pairs.len(),
"left_out": left_out,
"worst": worst,
"evidence_note": note,
}),
))
}