src/mimir_groupclone_graph.rs
//! Mimir **group twins from the compiled-code graph** — the same group of
//! statements inside two DIFFERENT functions, read from what the compiler
//! resolved, never from a model.
//!
//! # What the room holds below a function (and what it does not)
//!
//! The code room is folded from the `mimir-driver` dump. The driver walks
//! every body's **typeck'd HIR** (`walk.rs`'s `BodyVisitor`, with the body's
//! `TypeckResults`) for these facts; the MIR facts (basic blocks, statements,
//! places, operators — see the MIR section below) are a second, newer layer
//! a room may or may not hold for a function. The HIR facts below the
//! function, positioned by line:
//!
//! | fact | from | position |
//! |---|---|---|
//! | the resolved callee of every call, method call and fn-as-value (trait methods resolved to the impl rustc picks) | `CALLS` edge, one `code_spans` site per call | the call expression's first line |
//! | every struct / union field a body names (`a.b`, read or written) | `READS_FIELD` edge + sites | the field expression's line |
//! | every table a storage call names, with read / write | `TOUCHES_TABLE` edge + sites, `access` | the site's line |
//! | every `let` binding, with the type typeck inferred | `local` PART node (`name@line`, `ty`), at most [`mimir_schema::LOCALS_PER_FN`] per fn | its ident's line |
//! | the signature: params with types, the `->` type, `USES_TYPE` to its ADTs | `param` / `ret` parts, `USES_TYPE` | none per statement (signature only) |
//!
//! Sites carry a LINE, no column and no order within the line; a site inside
//! a macro expansion has no position. So the finest unit the graph can cut a
//! function into is a **fact line**: one source line of the body that carries
//! at least one compiled fact.
//!
//! # The statement group
//!
//! A function is the line-ordered list of its fact lines. Each fact is a
//! name-free KEY ([`facts_of`]):
//!
//! * `c:<stable moniker>` — calls this resolved function,
//! * `f:<stable moniker>` — touches this field,
//! * `t:<table>:<access>` — touches this table so,
//! * `l:<type>` — binds a local of this type (the local's NAME is dropped:
//! renaming locals cannot move a key).
//!
//! Stable monikers ([`mimir_schema::moniker::stable`]) leave the version out,
//! so a dependency bump moves no key.
//!
//! For two functions A and B, a **group** is a run of A's fact lines that
//! carry a key B also has, where at most [`MAX_GAP`] fact lines that share
//! nothing sit between two members — the interleaved noise (a log line, an
//! unrelated local chain) stays outside, which is what makes an interleaved
//! copy recoverable. The same cut is made on B's side with the keys of A's
//! run; the best-weighted run on B is its partner. Both sides are then
//! trimmed to the lines whose keys the other side's group holds.
//!
//! # The fingerprint, the score, the gates
//!
//! A group's fingerprint is its ordered key sequence (per line, keys sorted).
//!
//! * **exact** — the two fingerprints are equal: one compiled group (the same
//! callees, fields, tables and let types, line for line).
//! * **score** — the IDF-weighted Jaccard of the two groups' key sets,
//! `Σ idf(shared) / Σ idf(either)`, `idf = ln(1 + N / df)` over the room's
//! functions — the rarity weighting of `structural_clones` /
//! `semantic_twins` ([`crate::clone_signals::structure`]): sharing a rare
//! callee is strong evidence, sharing `Vec::push` almost none.
//! * **order** — shared [`KGRAM`]-grams of the two key sequences: the same
//! things touched in the same order.
//!
//! A pair is a group twin when each side has ≥ [`MIN_GROUP_LINES`] fact
//! lines and ≥ [`MIN_GROUP_KEYS`] distinct keys, the score is ≥
//! [`SCORE_FLOOR`] (exact pairs are 1.0), ≥ [`MIN_SHARED_KGRAMS`] k-grams are
//! shared and ≥ 1 shared key is RARE (df ≤ [`RARE_DF`]). Candidates come only
//! from rare keys' posting lists, so two functions that share nothing rare
//! are never compared. No model, no vector, no embeddings table.
//!
//! # MIR block granularity (when the room holds MIR facts)
//!
//! A function the driver dumped with MIR facts (`mir_block` nodes, see
//! `mimir_schema::mir`) is cut by its **basic blocks** instead of its fact
//! lines ([`Granularity::MirBlock`], [`mir_facts_of`]): the unit is a block,
//! in source order, and its name-free keys are
//!
//! * `b:<fingerprint>` — the whole block (statements, terminator, resolved
//! callee, local types; locals renumbered, so renaming moves nothing),
//! * `s:<hash>` — each statement's shape on its own (a near copy that changes
//! one statement still shares the others),
//! * `c:<stable moniker>` — the block's resolved callee.
//!
//! The same pairing runs over those units (gap, k-grams, rarity, exact =
//! the same blocks in order); only functions of ONE granularity are paired
//! with each other, and a function without MIR facts (an older dump) keeps
//! the fact-line cut. The answer says which (`granularity`), and a MIR
//! group's `group_lines` are the source lines its blocks' statements sit on.
use std::collections::{BTreeMap, BTreeSet, HashMap};
/// Fact lines that share nothing with the twin allowed between two group
/// members (the interleaved noise a copy can carry).
pub const MAX_GAP: usize = 3;
/// Fact lines a group must have on each side.
pub const MIN_GROUP_LINES: usize = 3;
/// Distinct keys a group must have on each side (a two-call group says
/// nothing).
pub const MIN_GROUP_KEYS: usize = 4;
/// k-gram length over the ordered key sequence.
pub const KGRAM: usize = 2;
/// Shared k-grams a pair needs.
pub const MIN_SHARED_KGRAMS: usize = 2;
/// The IDF-weighted Jaccard floor of a non-exact pair. Set on this module's
/// fixtures: the planted interleaved, renamed copy is exact (1.0) after the
/// trim, the copy with one callee swapped scores 0.72, the control that
/// shares one rare callee and two common keys with it 0.38.
pub const SCORE_FLOOR: f32 = 0.6;
/// A key shared by at most this many functions of the room is RARE — the
/// structural signal's own threshold (`clone_signals::structure::RARE_DF`).
pub const RARE_DF: u32 = 64;
/// Candidate pairs judged per answer at most, the ones sharing the most rare
/// keys first. MIR blocks made the candidates of one repo 197,545 (nornir on
/// dwarf, 186 s); the rest is counted, never silently dropped.
pub const MAX_CANDIDATES: usize = 60_000;
/// Wall-clock budget of one pairing: past it the judging stops, the pairs not
/// judged are counted and the answer is partial (a lower bound).
pub const BUDGET_MS: u64 = 45_000;
/// MIR blocks a MIR group must have on each side. A basic block is far
/// smaller than a source line (one call is a block, its unwind another), so
/// [`MIN_GROUP_LINES`] blocks is a fraction of a line: nornir answered
/// 27,837 MIR groups at 3 blocks (3,486 by line). Set on the live sample.
pub const MIN_GROUP_BLOCKS: usize = 8;
/// The IDF weight (Σ idf of the keys the two sides share) a MIR group must
/// carry: a long run of common blocks (drops, moves, unwinds) weighs little.
/// Set on the live sample.
pub const MIN_GROUP_WEIGHT: f32 = 40.0;
/// Distinct SOURCE lines a MIR group must cover on each side. A derive's
/// expansion (serde visitors, clap builders) maps every block to the one
/// `#[derive]` line, and a two-line idiom is no copy worth a finding: of 23
/// hand-checked nornir findings 16 were derive code, 3 two-line idioms.
pub const MIN_GROUP_SRC_LINES: usize = 4;
/// Distinct callees outside the std / formatting / derive crates a MIR group
/// must share: what is left when only `json!` / `format!` machinery, drops
/// and control flow match is boilerplate, not a copy.
pub const MIN_GROUP_CALLEES: usize = 4;
/// Group source lines a MIR group must hold away from its item's first and
/// last two lines: a builder scaffold (`Schema::builder()` … `.build()?`)
/// matches only at the edges of two different field lists.
pub const MIN_INTERIOR_LINES: usize = 3;
/// The share of its item's lines a MIR group must cover: at least this on
/// the side it covers least ([`MIN_COVER_BOTH`]) and at least
/// [`MIN_COVER_ONE`] on the other. A third hand check (15 of 390) found the
/// weak half to be a shared prologue/epilogue of long functions (load the
/// table, take its arrow schema … append the batch) around different
/// columns: 6-7 lines of 30-160 (cover 0.04-0.28), while every real copy
/// covered ≥ 0.59 of one side and ≥ 0.38 of the other.
pub const MIN_COVER_BOTH: f32 = 0.3;
pub const MIN_COVER_ONE: f32 = 0.5;
/// Workers of one pairing by default: the server shares its host with the
/// consumer's builds and the other lenses, so not every core.
pub const GRAPH_WORKERS: usize = 6;
/// The crates whose callees are boilerplate to a MIR group ([`MIN_GROUP_CALLEES`]).
pub const BOILERPLATE_CRATES: &[&str] = &["core", "alloc", "std", "serde", "serde_json", "clap", "clap_builder"];
/// The gates, in one struct so a report can state what it ran with. The
/// field names `cosine_floor`, `min_shared_kgrams` and `kgram` are the ones
/// the pane reads; `cosine_floor` carries the score floor (no cosine is
/// computed anywhere here).
#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize)]
pub struct GraphOptions {
pub cosine_floor: f32,
pub score_floor: f32,
pub kgram: usize,
pub min_shared_kgrams: usize,
pub min_group_lines: usize,
pub min_group_keys: usize,
pub max_gap: usize,
pub rare_df: u32,
pub max_candidates: usize,
pub budget_ms: u64,
/// MIR granularity only: blocks a group needs on each side.
pub min_group_blocks: usize,
/// MIR granularity only: the shared keys' IDF weight a group needs.
pub min_group_weight: f32,
/// MIR granularity only: distinct source lines a group covers per side.
pub min_group_src_lines: usize,
/// MIR granularity only: shared callees outside [`BOILERPLATE_CRATES`].
pub min_group_callees: usize,
/// Workers judging candidates and scanning bodies (0 = [`GRAPH_WORKERS`]).
pub threads: usize,
/// MIR granularity only: group lines away from the item's edges.
pub min_interior_lines: usize,
/// MIR granularity only: the share of the item's lines each side's group
/// covers, the least of the two / the most of the two.
pub min_cover_both: f32,
pub min_cover_one: f32,
}
impl Default for GraphOptions {
fn default() -> Self {
Self {
cosine_floor: SCORE_FLOOR,
score_floor: SCORE_FLOOR,
kgram: KGRAM,
min_shared_kgrams: MIN_SHARED_KGRAMS,
min_group_lines: MIN_GROUP_LINES,
min_group_keys: MIN_GROUP_KEYS,
max_gap: MAX_GAP,
rare_df: RARE_DF,
max_candidates: MAX_CANDIDATES,
budget_ms: BUDGET_MS,
min_group_blocks: MIN_GROUP_BLOCKS,
min_group_weight: MIN_GROUP_WEIGHT,
min_group_src_lines: MIN_GROUP_SRC_LINES,
min_group_callees: MIN_GROUP_CALLEES,
threads: 0,
min_interior_lines: MIN_INTERIOR_LINES,
min_cover_both: MIN_COVER_BOTH,
min_cover_one: MIN_COVER_ONE,
}
}
}
impl GraphOptions {
/// The defaults, with the MIR gates and the budget overridable for a
/// live retune (`MIMIR_GT_MIN_BLOCKS`, `MIMIR_GT_MIN_WEIGHT`,
/// `MIMIR_GT_BUDGET_MS`).
pub fn from_env() -> Self {
let mut o = Self::default();
let get = |k: &str| std::env::var(k).ok();
if let Some(v) = get("MIMIR_GT_MIN_BLOCKS").and_then(|v| v.parse().ok()) {
o.min_group_blocks = v;
}
if let Some(v) = get("MIMIR_GT_MIN_WEIGHT").and_then(|v| v.parse().ok()) {
o.min_group_weight = v;
}
if let Some(v) = get("MIMIR_GT_BUDGET_MS").and_then(|v| v.parse().ok()) {
o.budget_ms = v;
}
if let Some(v) = get("MIMIR_GT_MIN_SRC_LINES").and_then(|v| v.parse().ok()) {
o.min_group_src_lines = v;
}
if let Some(v) = get("MIMIR_GT_MIN_CALLEES").and_then(|v| v.parse().ok()) {
o.min_group_callees = v;
}
if let Some(v) = get("MIMIR_GT_THREADS").and_then(|v| v.parse().ok()) {
o.threads = v;
}
o
}
/// Does a MIR group stand as a copy, not boilerplate: each side covers
/// enough distinct source lines, and the shared keys name enough callees
/// outside the std / formatting / derive crates? A fact-line group
/// always does (its own gates hold).
fn substantive(&self, fa: &CompiledFn, ga_units: &[u32], fb: &CompiledFn, gb_units: &[u32], shared: &BTreeSet<&str>) -> bool {
if fa.granularity != Granularity::MirBlock {
return true;
}
let src_lines = |f: &CompiledFn, units: &[u32]| -> usize {
let mut l: Vec<u32> = units.iter().filter_map(|u| f.units.get(*u as usize)).flat_map(|u| u.lines.iter().copied()).collect();
l.sort_unstable();
l.dedup();
l.len()
};
if src_lines(fa, ga_units) < self.min_group_src_lines || src_lines(fb, gb_units) < self.min_group_src_lines {
return false;
}
let interior = |f: &CompiledFn, units: &[u32]| -> usize {
let mut l: Vec<u32> = units.iter().filter_map(|u| f.units.get(*u as usize)).flat_map(|u| u.lines.iter().copied()).filter(|l| *l > f.item_start.saturating_add(2) && *l + 2 < f.item_end).collect();
l.sort_unstable();
l.dedup();
l.len()
};
if interior(fa, ga_units) < self.min_interior_lines || interior(fb, gb_units) < self.min_interior_lines {
return false;
}
// one source compiled into two crates (a test file in two test
// targets): the same file and span under two monikers is no copy
if fa.moniker != fb.moniker && fa.file == fb.file && fa.item_start == fb.item_start && fa.item_end == fb.item_end {
return false;
}
let cover = |f: &CompiledFn, units: &[u32]| -> f32 {
let span = f.item_end.saturating_sub(f.item_start) + 1;
let mut l: Vec<u32> = units.iter().filter_map(|u| f.units.get(*u as usize)).flat_map(|u| u.lines.iter().copied()).filter(|l| *l >= f.item_start && *l <= f.item_end).collect();
l.sort_unstable();
l.dedup();
l.len() as f32 / span.max(1) as f32
};
let (ca, cb) = (cover(fa, ga_units), cover(fb, gb_units));
if ca.min(cb) < self.min_cover_both || ca.max(cb) < self.min_cover_one {
return false;
}
let callees = shared.iter().filter_map(|k| k.strip_prefix("c:")).filter(|c| !BOILERPLATE_CRATES.contains(&callee_crate(c))).count();
callees >= self.min_group_callees
}
/// The worker count the judging fans out to.
fn workers(&self) -> usize {
if self.threads > 0 { self.threads } else { GRAPH_WORKERS }
}
/// Units a group of this granularity needs on each side.
fn min_units(&self, g: Granularity) -> usize {
match g {
Granularity::MirBlock => self.min_group_blocks.max(self.min_group_lines),
Granularity::FactLine => self.min_group_lines,
}
}
/// The shared weight a group of this granularity needs.
fn min_weight(&self, g: Granularity) -> f32 {
match g {
Granularity::MirBlock => self.min_group_weight,
Granularity::FactLine => 0.0,
}
}
}
/// One function as the room describes its body, before the names go.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct RawFn {
pub moniker: String,
pub file: String,
pub ident: String,
pub item_start: u32,
pub item_end: u32,
/// `(callee moniker, short label, line)`.
pub calls: Vec<(String, String, u32)>,
/// `(field moniker, label, line)`.
pub fields: Vec<(String, String, u32)>,
/// `(table name, access, line)`.
pub tables: Vec<(String, String, u32)>,
/// `(local name, its type, line)` — the name never reaches a key.
pub locals: Vec<(String, String, u32)>,
}
/// One compiled fact of a body.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Fact {
pub line: u32,
pub key: String,
pub label: String,
}
/// What a function is cut into.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, serde::Serialize)]
#[serde(rename_all = "snake_case")]
pub enum Granularity {
/// Source lines that carry a compiled fact (the HIR facts).
#[default]
FactLine,
/// MIR basic blocks (the room holds `mir_block` nodes for the fn).
MirBlock,
}
impl Granularity {
pub fn as_str(self) -> &'static str {
match self {
Granularity::FactLine => "fact_line",
Granularity::MirBlock => "mir_block",
}
}
}
/// One MIR block of a [`Granularity::MirBlock`] function: its name and the
/// source lines its statements and terminator sit on.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct MirUnit {
pub block: String,
pub lines: Vec<u32>,
}
/// One function as the pairer sees it: name-free facts in unit order. For a
/// fact-line function a fact's `line` is its source line; for a MIR one it is
/// the index of its block in `units`.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct CompiledFn {
pub moniker: String,
pub file: String,
pub ident: String,
pub item_start: u32,
pub item_end: u32,
pub facts: Vec<Fact>,
pub granularity: Granularity,
/// [`Granularity::MirBlock`] only: the blocks, in source order.
pub units: Vec<MirUnit>,
/// [`Granularity::MirBlock`] only: the `CFG_SUCC` edges between its
/// blocks, as unit indices — a group is a CONNECTED run of blocks (empty:
/// a room without the edges, every run stands as it is).
pub cfg: Vec<(u32, u32)>,
}
/// One MIR block as the room describes it, before it becomes keys.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct RawMirBlock {
/// `3` / `c1.3`.
pub block: String,
/// The block's fingerprint (16 hex).
pub fp: String,
/// The terminator kind (`call`, `switch` …).
pub term: String,
/// The resolved callee of a call terminator (stable moniker).
pub callee: Option<String>,
/// The statements' texts (locals as MIR indices).
pub stmts: Vec<String>,
/// Absolute source lines of its statements / terminator.
pub lines: Vec<u32>,
}
/// One function with MIR blocks, as the room describes it.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct RawMirFn {
pub moniker: String,
pub file: String,
pub ident: String,
pub item_start: u32,
pub item_end: u32,
pub blocks: Vec<RawMirBlock>,
/// The `CFG_SUCC` edges between its blocks, by block name.
pub succ: Vec<(String, String)>,
}
/// The last two path segments of a moniker, for a label.
fn short_label(m: &str) -> String {
let d = mimir_schema::moniker::parse(m).map(|(_, _, d)| d).unwrap_or(m);
let parts: Vec<&str> = d.split(['/', '#', '.']).filter(|p| !p.is_empty() && *p != "()").collect();
let n = parts.len();
parts[n.saturating_sub(2)..].join("::").replace("()", "")
}
/// The name-free keys of a MIR function, one unit per block, blocks in
/// source order (first line, then body order). See the module docs.
pub fn mir_facts_of(raw: &RawMirFn) -> CompiledFn {
let mut order: Vec<usize> = (0..raw.blocks.len()).collect();
order.sort_by_key(|i| (raw.blocks[*i].lines.first().copied().unwrap_or(u32::MAX), *i));
let mut facts: BTreeSet<Fact> = BTreeSet::new();
let mut units = Vec::with_capacity(order.len());
for (u, i) in order.iter().enumerate() {
let b = &raw.blocks[*i];
let line = u as u32;
facts.insert(Fact { line, key: format!("b:{}", b.fp), label: format!("the same `{}` block ({} statement(s))", b.term, b.stmts.len()) });
if let Some(c) = &b.callee {
facts.insert(Fact { line, key: format!("c:{c}"), label: format!("call `{}`", short_label(c)) });
}
for st in &b.stmts {
let canon = mimir_schema::mir::canonical_locals(st, &mut Vec::new());
facts.insert(Fact { line, key: format!("s:{:016x}", mimir_schema::mir::fnv64(canon.as_bytes())), label: format!("`{canon}`") });
}
units.push(MirUnit { block: b.block.clone(), lines: b.lines.clone() });
}
// the CFG's shape: each edge between two blocks is a key of its source
// block (the two fingerprints, in order), so a group's fingerprint holds
// its blocks AND how they flow into each other
let unit_of: HashMap<&str, u32> = order.iter().enumerate().map(|(u, i)| (raw.blocks[*i].block.as_str(), u as u32)).collect();
let mut cfg = Vec::new();
for (x, y) in &raw.succ {
let (Some(&ux), Some(&uy)) = (unit_of.get(x.as_str()), unit_of.get(y.as_str())) else { continue };
cfg.push((ux, uy));
let (fx, fy) = (&raw.blocks[order[ux as usize]].fp, &raw.blocks[order[uy as usize]].fp);
facts.insert(Fact { line: ux, key: format!("e:{fx}>{fy}"), label: "the same control flow between two blocks".to_string() });
}
cfg.sort_unstable();
cfg.dedup();
CompiledFn {
moniker: raw.moniker.clone(),
file: raw.file.clone(),
ident: raw.ident.clone(),
item_start: raw.item_start,
item_end: raw.item_end,
facts: facts.into_iter().collect(),
granularity: Granularity::MirBlock,
units,
cfg,
}
}
/// The name-free facts of one function, in (line, key) order, duplicates
/// gone. Only facts inside the item's own span count.
pub fn facts_of(raw: &RawFn) -> CompiledFn {
let stable = |m: &str| mimir_schema::moniker::stable(m).into_owned();
let mut facts: BTreeSet<Fact> = BTreeSet::new();
let inside = |l: u32| l >= raw.item_start && l <= raw.item_end;
for (m, label, line) in &raw.calls {
facts.insert(Fact { line: *line, key: format!("c:{}", stable(m)), label: format!("call `{label}`") });
}
for (m, label, line) in &raw.fields {
facts.insert(Fact { line: *line, key: format!("f:{}", stable(m)), label: format!("touch `.{label}`") });
}
for (t, access, line) in &raw.tables {
facts.insert(Fact { line: *line, key: format!("t:{t}:{access}"), label: format!("{access} table `{t}`") });
}
for (_name, ty, line) in &raw.locals {
facts.insert(Fact { line: *line, key: format!("l:{ty}"), label: format!("bind a `{ty}`") });
}
let mut facts: Vec<Fact> = facts.into_iter().filter(|f| inside(f.line)).collect();
// one key per line once (two labels of one key on a line are one fact)
facts.dedup_by(|a, b| a.line == b.line && a.key == b.key);
CompiledFn { moniker: raw.moniker.clone(), file: raw.file.clone(), ident: raw.ident.clone(), item_start: raw.item_start, item_end: raw.item_end, facts, ..Default::default() }
}
/// One side of a graph group twin.
#[derive(Debug, Clone, PartialEq, serde::Serialize)]
pub struct GraphSite {
pub moniker: String,
pub file: String,
pub ident: String,
pub item_start: u32,
pub item_end: u32,
/// The group's fact lines, sorted, possibly non-contiguous (at MIR block
/// granularity: the source lines of its blocks' statements).
pub group_lines: Vec<u32>,
/// Facts in the group.
pub facts: usize,
/// SHA-256 of the group's fingerprint (its ordered key sequence).
pub key: String,
/// What the group is cut from.
pub granularity: Granularity,
/// [`Granularity::MirBlock`]: the group's blocks (`3`, `c1.3`), in order.
#[serde(skip_serializing_if = "Vec::is_empty")]
pub group_blocks: Vec<String>,
/// [`Granularity::MirBlock`]: the group's unit indices in the fn.
#[serde(skip_serializing_if = "Vec::is_empty")]
pub group_units: Vec<u32>,
}
/// One group twin found in the graph.
#[derive(Debug, Clone, PartialEq, serde::Serialize)]
pub struct GraphTwin {
pub a: GraphSite,
pub b: GraphSite,
/// IDF-weighted Jaccard of the two groups' keys (1.0 when exact).
pub score: f32,
pub exact: bool,
pub shared_kgrams: usize,
pub rare_shared: usize,
/// The rarest shared facts, as a person reads them.
pub shared_words: Vec<String>,
pub found_by: Vec<String>,
/// Both sides are cut from the same kind of unit.
pub granularity: Granularity,
/// Both sides are in ONE function: the same group twice in one body.
#[serde(skip_serializing_if = "std::ops::Not::not")]
pub same_function: bool,
}
/// The whole answer of the graph pass.
#[derive(Debug, Clone, Default, serde::Serialize)]
pub struct GraphReport {
pub twins: Vec<GraphTwin>,
/// Functions of the repo handed in.
pub functions: usize,
/// … of which carried too few facts to hold a group.
pub functions_too_small: usize,
/// Functions the rarity weights were counted over (the room's).
pub population: usize,
pub candidates: usize,
pub options: Option<GraphOptions>,
/// `mir_block` when the room held MIR facts for the repo's functions
/// (those are cut by block; any without stay at fact lines), else
/// `fact_line`.
pub granularity: Granularity,
/// … of the functions, how many were cut by MIR block.
pub functions_mir: usize,
/// Candidate pairs NOT judged: past [`GraphOptions::max_candidates`] or
/// the time budget. Non-zero = the twins are a LOWER bound.
pub candidates_unjudged: usize,
/// Why judging stopped early (`""` when every candidate was judged).
pub bounded_by: String,
}
/// Rarity of every key over a population of functions: how many carry it.
#[derive(Debug, Clone, Default)]
pub struct Rarity {
pub n: usize,
pub df: HashMap<String, u32>,
}
impl Rarity {
pub fn of<'a>(sets: impl IntoIterator<Item = BTreeSet<&'a str>>) -> Self {
let mut r = Rarity::default();
for set in sets {
r.n += 1;
for k in set {
*r.df.entry(k.to_string()).or_default() += 1;
}
}
r
}
fn df(&self, k: &str) -> u32 {
self.df.get(k).copied().unwrap_or(1).max(1)
}
pub fn idf(&self, k: &str) -> f32 {
(1.0 + self.n.max(1) as f32 / self.df(k) as f32).ln()
}
/// Rare: at most `rare_df` functions carry it, and at most half the
/// population (two in a population of two or three).
pub fn rare(&self, k: &str, rare_df: u32) -> bool {
let d = self.df(k);
d <= rare_df && d as usize <= (self.n / 2).max(2)
}
}
/// A function's fact lines: `(line, keys sorted)`.
fn lines_of(f: &CompiledFn) -> Vec<(u32, Vec<&str>)> {
let mut by: BTreeMap<u32, Vec<&str>> = BTreeMap::new();
for x in &f.facts {
by.entry(x.line).or_default().push(x.key.as_str());
}
by.into_iter()
.map(|(l, mut ks)| {
ks.sort_unstable();
ks.dedup();
(l, ks)
})
.collect()
}
/// The runs of `lines` whose indices are `marked`, split where more than
/// `max_gap` unmarked fact lines sit between two marked ones.
fn runs(marked: &[usize], max_gap: usize) -> Vec<Vec<usize>> {
let mut out: Vec<Vec<usize>> = Vec::new();
for &i in marked {
match out.last_mut() {
Some(run) if i - run.last().copied().unwrap_or(i) <= max_gap + 1 => run.push(i),
_ => out.push(vec![i]),
}
}
out
}
fn keys_of<'a>(side: &[(u32, Vec<&'a str>)], run: &[usize]) -> BTreeSet<&'a str> {
run.iter().flat_map(|i| side[*i].1.iter().copied()).collect()
}
fn seq_of<'a>(side: &[(u32, Vec<&'a str>)], g: &[usize]) -> Vec<&'a str> {
g.iter().flat_map(|i| side[*i].1.iter().copied()).collect()
}
fn shape_of<'a>(side: &[(u32, Vec<&'a str>)], g: &[usize]) -> Vec<Vec<&'a str>> {
g.iter().map(|i| side[*i].1.clone()).collect()
}
fn kgrams(seq: &[&str], k: usize) -> BTreeSet<u64> {
let mut out = BTreeSet::new();
if k == 0 || seq.len() < k {
return out;
}
for w in seq.windows(k) {
let h = w.iter().fold(0xcbf2_9ce4_8422_2325u64, |h, s| s.bytes().chain(std::iter::once(0x1e)).fold(h, |h, b| (h ^ b as u64).wrapping_mul(0x0100_0000_01b3)));
out.insert(h);
}
out
}
/// **Pair groups across the functions of one repo.** `fns` are the repo's
/// functions, `rarity` is counted over the room's (it may be wider than
/// `fns`). A group repeated INSIDE one function is reported too
/// ([`self_twins`]: two runs that do not overlap, `same_function`).
pub fn pair(fns: &[CompiledFn], rarity: &Rarity, opts: &GraphOptions) -> GraphReport {
let functions_mir = fns.iter().filter(|f| f.granularity == Granularity::MirBlock).count();
let granularity = if functions_mir > 0 { Granularity::MirBlock } else { Granularity::FactLine };
let mut report = GraphReport { functions: fns.len(), population: rarity.n, options: Some(*opts), granularity, functions_mir, ..Default::default() };
let lines: Vec<Vec<(u32, Vec<&str>)>> = fns.iter().map(lines_of).collect();
let keysets: Vec<BTreeSet<&str>> = fns.iter().map(|f| f.facts.iter().map(|x| x.key.as_str()).collect()).collect();
// a derive's expansion (`impl … for X` inside `const _: () = { … }`:
// serde visitors, clap builders, schemars schemas) is generated, never a copy
let generated = |f: &CompiledFn| f.ident.contains("::_::");
let eligible: Vec<bool> = (0..fns.len()).map(|i| !generated(&fns[i]) && lines[i].len() >= opts.min_units(fns[i].granularity) && keysets[i].len() >= opts.min_group_keys).collect();
report.functions_too_small = eligible.iter().filter(|e| !**e).count();
// the repeats inside one function first: cheap (≤ SELF_SCAN_MAX_UNITS a
// body) and never starved by the cross pairs' budget (RED before: a
// repo whose pairs ran out the budget reported no repeat at all)
let self_found = self_twins(fns, &lines, &eligible, rarity, opts);
// candidates: functions sharing a rare key
let mut posting: HashMap<&str, Vec<usize>> = HashMap::new();
for (i, ks) in keysets.iter().enumerate().filter(|(i, _)| eligible[*i]) {
for k in ks.iter().filter(|k| rarity.rare(k, opts.rare_df)) {
posting.entry(k).or_default().push(i);
}
}
// each candidate with how many rare keys it shares: judged most-shared first
let mut shared_rare: HashMap<(usize, usize), u32> = HashMap::new();
for list in posting.values() {
for x in 0..list.len() {
for y in (x + 1)..list.len() {
let (a, b) = (list[x].min(list[y]), list[x].max(list[y]));
if a != b && fns[a].moniker != fns[b].moniker && fns[a].granularity == fns[b].granularity {
*shared_rare.entry((a, b)).or_default() += 1;
}
}
}
}
report.candidates = shared_rare.len();
let mut cands: Vec<((usize, usize), u32)> = shared_rare.into_iter().collect();
cands.sort_unstable_by(|x, y| y.1.cmp(&x.1).then(x.0.cmp(&y.0)));
if cands.len() > opts.max_candidates {
report.candidates_unjudged = cands.len() - opts.max_candidates;
report.bounded_by = format!("{} candidate pair(s) judged at most (the most rare keys shared first)", opts.max_candidates);
cands.truncate(opts.max_candidates);
}
let started = std::time::Instant::now();
let over_budget = || started.elapsed().as_millis() as u64 >= opts.budget_ms;
let weight = |ks: &BTreeSet<&str>| -> f32 { ks.iter().map(|k| rarity.idf(k)).sum() };
let total = cands.len();
// every candidate is judged on its own (heaviest first, gatling): the
// answers come back in candidate order, so N workers give the one
// worker's twins whenever the budget holds
let judge = |a: usize, b: usize| -> Option<Vec<GraphTwin>> {
if over_budget() {
return None;
}
let mut out: Vec<GraphTwin> = Vec::new();
let shared: BTreeSet<&str> = keysets[a].intersection(&keysets[b]).copied().collect();
let marked = |side: &[(u32, Vec<&str>)], with: &BTreeSet<&str>| -> Vec<usize> { side.iter().enumerate().filter(|(_, (_, ks))| ks.iter().any(|k| with.contains(k))).map(|(i, _)| i).collect() };
let (la, lb) = (&lines[a], &lines[b]);
let mut seen: BTreeSet<(Vec<usize>, Vec<usize>)> = BTreeSet::new();
for run_a in runs(&marked(la, &shared), opts.max_gap) {
let ka: BTreeSet<&str> = keys_of(la, &run_a).intersection(&shared).copied().collect();
// B's partner: the run over A's keys that carries the most weight of them
let Some(run_b) = runs(&marked(lb, &ka), opts.max_gap).into_iter().max_by(|x, y| {
let wx = weight(&keys_of(lb, x).intersection(&ka).copied().collect());
let wy = weight(&keys_of(lb, y).intersection(&ka).copied().collect());
wx.total_cmp(&wy).then(y.first().cmp(&x.first()))
}) else {
continue;
};
// trim both sides to the lines whose keys the other side's group holds
let kb_all = keys_of(lb, &run_b);
let ga: Vec<usize> = run_a.iter().copied().filter(|i| la[*i].1.iter().any(|k| kb_all.contains(k))).collect();
let ka_all = keys_of(la, &ga);
let gb: Vec<usize> = run_b.iter().copied().filter(|i| lb[*i].1.iter().any(|k| ka_all.contains(k))).collect();
// a MIR group is a CONNECTED run of blocks (CFG_SUCC): blocks that
// only sit near each other in the source are not one fragment
let (ga, gb) = (connected(&fns[a], la, &ga), connected(&fns[b], lb, &gb));
let min_units = opts.min_units(fns[a].granularity);
if ga.len() < min_units || gb.len() < min_units || !seen.insert((ga.clone(), gb.clone())) {
continue;
}
let (sa, sb) = (keys_of(la, &ga), keys_of(lb, &gb));
if sa.len() < opts.min_group_keys || sb.len() < opts.min_group_keys {
continue;
}
let both: BTreeSet<&str> = sa.intersection(&sb).copied().collect();
let either: BTreeSet<&str> = sa.union(&sb).copied().collect();
let score = weight(&both) / weight(&either).max(f32::MIN_POSITIVE);
let (qa, qb) = (seq_of(la, &ga), seq_of(lb, &gb));
let exact = shape_of(la, &ga) == shape_of(lb, &gb);
let shared_k = kgrams(&qa, opts.kgram).intersection(&kgrams(&qb, opts.kgram)).count();
let rare: Vec<&str> = both.iter().copied().filter(|k| rarity.rare(k, opts.rare_df)).collect();
if rare.is_empty() || shared_k < opts.min_shared_kgrams || (!exact && score < opts.score_floor) || weight(&both) < opts.min_weight(fns[a].granularity) {
continue;
}
let units = |side: &[(u32, Vec<&str>)], g: &[usize]| -> Vec<u32> { g.iter().map(|i| side[*i].0).collect() };
if !opts.substantive(&fns[a], &units(la, &ga), &fns[b], &units(lb, &gb), &both) {
continue;
}
let score = if exact { 1.0 } else { score };
// the words: the rarest shared facts first
let label_of = |k: &str| -> String { fns[a].facts.iter().find(|f| f.key == k).map(|f| f.label.clone()).unwrap_or_else(|| k.to_string()) };
let mut ranked: Vec<&str> = both.iter().copied().collect();
ranked.sort_by(|x, y| rarity.idf(y).total_cmp(&rarity.idf(x)).then(x.cmp(y)));
let shared_words: Vec<String> = ranked.iter().take(4).map(|k| label_of(k)).collect();
let mir = fns[a].granularity == Granularity::MirBlock;
let mut found_by = vec![match (exact, mir) {
(true, false) => "graph exact: one compiled group — the same resolved callees, fields, tables and let types, line for line".to_string(),
(true, true) => "graph exact (MIR blocks): one compiled group — the same basic blocks (statements, terminators, resolved callees, local types; locals renumbered), block for block".to_string(),
(false, false) => format!("graph: IDF-weighted Jaccard {score:.2} ≥ {:.2} over the group's compiled facts", opts.score_floor),
(false, true) => format!("graph (MIR blocks): IDF-weighted Jaccard {score:.2} ≥ {:.2} over the group's block, statement and callee keys", opts.score_floor),
}];
found_by.push(format!("order: {shared_k} shared {}-gram(s) of the {} sequence; {} rare fact(s) shared (df ≤ {})", opts.kgram, if mir { "block" } else { "fact" }, rare.len(), opts.rare_df));
out.push(GraphTwin {
a: site_of(&fns[a], la, &ga, &qa),
b: site_of(&fns[b], lb, &gb, &qb),
score,
exact,
shared_kgrams: shared_k,
rare_shared: rare.len(),
shared_words,
found_by,
granularity: fns[a].granularity,
same_function: false,
});
}
Some(out)
};
let judged: Vec<Option<Vec<GraphTwin>>> = znippy_zoomies::gatling_forkjoin::gatling_map_balanced(&cands, opts.workers(), 8, |c| c.1 as u64, |_, c| judge(c.0.0, c.0.1));
let done = judged.iter().filter(|r| r.is_some()).count();
if done < total {
report.candidates_unjudged += total - done;
report.bounded_by = format!("the {} ms budget: {done} of {total} candidate pair(s) judged (the most rare keys shared first)", opts.budget_ms);
}
for twins in judged.into_iter().flatten() {
report.twins.extend(twins);
}
report.twins.extend(self_found);
report.twins.sort_by(|x, y| {
y.score
.total_cmp(&x.score)
.then(y.rare_shared.cmp(&x.rare_shared))
.then(y.shared_kgrams.cmp(&x.shared_kgrams))
.then((x.a.file.as_str(), x.a.group_lines.first()).cmp(&(y.a.file.as_str(), y.a.group_lines.first())))
.then((x.b.file.as_str(), x.b.group_lines.first()).cmp(&(y.b.file.as_str(), y.b.group_lines.first())))
});
report
}
/// The crate a callee moniker names (`rust-analyzer cargo <crate> <ver> …`).
fn callee_crate(m: &str) -> &str {
m.split(' ').nth(2).unwrap_or("")
}
/// One side of a twin: the group `g` (indices into `side`, the fn's lines)
/// of `f`, its ordered key sequence `q`.
fn site_of(f: &CompiledFn, side: &[(u32, Vec<&str>)], g: &[usize], q: &[&str]) -> GraphSite {
let units: Vec<u32> = g.iter().map(|i| side[*i].0).collect();
let (group_lines, group_blocks, group_units) = match f.granularity {
Granularity::FactLine => (units, Vec::new(), Vec::new()),
Granularity::MirBlock => {
let mut lines: Vec<u32> = units.iter().filter_map(|u| f.units.get(*u as usize)).flat_map(|u| u.lines.iter().copied()).collect();
lines.sort_unstable();
lines.dedup();
let blocks = units.iter().filter_map(|u| f.units.get(*u as usize)).map(|u| u.block.clone()).collect();
(lines, blocks, units)
}
};
GraphSite {
moniker: f.moniker.clone(),
file: f.file.clone(),
ident: f.ident.clone(),
item_start: f.item_start,
item_end: f.item_end,
group_lines,
facts: q.len(),
key: nornir_hash::sha256_hex(q.join("\n").as_bytes()),
granularity: f.granularity,
group_blocks,
group_units,
}
}
/// The largest CFG-connected part of the group `g` of a MIR function (blocks
/// joined by `CFG_SUCC`, either direction). A fact-line function, or a MIR one
/// whose room holds no CFG edges, keeps its group whole.
fn connected(f: &CompiledFn, side: &[(u32, Vec<&str>)], g: &[usize]) -> Vec<usize> {
if f.granularity != Granularity::MirBlock || f.cfg.is_empty() || g.len() < 2 {
return g.to_vec();
}
let pos: HashMap<u32, usize> = g.iter().enumerate().map(|(k, i)| (side[*i].0, k)).collect();
let mut up: Vec<usize> = (0..g.len()).collect();
fn find(up: &mut [usize], x: usize) -> usize {
let mut r = x;
while up[r] != r {
r = up[r];
}
let mut c = x;
while up[c] != r {
let n = up[c];
up[c] = r;
c = n;
}
r
}
for (a, b) in &f.cfg {
if let (Some(&x), Some(&y)) = (pos.get(a), pos.get(b)) {
let (rx, ry) = (find(&mut up, x), find(&mut up, y));
if rx != ry {
up[rx] = ry;
}
}
}
let mut parts: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for k in 0..g.len() {
let r = find(&mut up, k);
parts.entry(r).or_default().push(g[k]);
}
// the largest part; on a tie the one that starts first
parts.into_values().max_by(|x, y| x.len().cmp(&y.len()).then(y.first().cmp(&x.first()))).unwrap_or_default()
}
/// Units above which a body is not scanned for a group repeated inside it
/// (the scan is quadratic in the body's units).
pub const SELF_SCAN_MAX_UNITS: usize = 800;
/// **The same group twice inside ONE function** — a pasted block, a loop body
/// written out twice: two runs of the function's own units with the same
/// shape, unit for unit, that do NOT overlap. Exact only: inside one body a
/// near match is the code's own rhythm, not a copy. The gates of a pair across
/// functions hold (group size, distinct keys, a rare key, shared k-grams), and
/// a MIR run must be CFG-connected on both sides.
fn self_twins(fns: &[CompiledFn], lines: &[Vec<(u32, Vec<&str>)>], eligible: &[bool], rarity: &Rarity, opts: &GraphOptions) -> Vec<GraphTwin> {
// one body at a time, each on its own (heaviest first): the repeats
// come back in function order, so N workers give the one worker's
let per_fn = |i: usize, f: &CompiledFn| -> Vec<GraphTwin> {
let mut out = Vec::new();
let side = &lines[i];
let n = side.len();
let min_units = opts.min_units(f.granularity);
if !eligible[i] || n < 2 * min_units || n > SELF_SCAN_MAX_UNITS {
return out;
}
// per offset d, every maximal stretch of positions whose unit equals
// the unit d further on; its first min(len, d) positions are the
// longest non-overlapping pair the stretch holds
for d in min_units..n {
let mut p = 0usize;
while p + d < n {
if side[p].1 != side[p + d].1 {
p += 1;
continue;
}
let start = p;
while p + d < n && side[p].1 == side[p + d].1 {
p += 1;
}
let k = (p - start).min(d);
if k < min_units {
continue;
}
let ga: Vec<usize> = (start..start + k).collect();
let gb: Vec<usize> = (start + d..start + d + k).collect();
if connected(f, side, &ga).len() != k || connected(f, side, &gb).len() != k {
continue;
}
let keys = keys_of(side, &ga);
let q = seq_of(side, &ga);
let rare = keys.iter().filter(|key| rarity.rare(key, opts.rare_df)).count();
let grams = kgrams(&q, opts.kgram).len();
let w: f32 = keys.iter().map(|k| rarity.idf(k)).sum();
if keys.len() < opts.min_group_keys || rare == 0 || grams < opts.min_shared_kgrams || w < opts.min_weight(f.granularity) {
continue;
}
let (ua, ub): (Vec<u32>, Vec<u32>) = (ga.iter().map(|i| side[*i].0).collect(), gb.iter().map(|i| side[*i].0).collect());
if !opts.substantive(f, &ua, f, &ub, &keys) {
continue;
}
let label_of = |key: &str| -> String { f.facts.iter().find(|x| x.key == key).map(|x| x.label.clone()).unwrap_or_else(|| key.to_string()) };
let mut ranked: Vec<&str> = keys.iter().copied().collect();
ranked.sort_by(|x, y| rarity.idf(y).total_cmp(&rarity.idf(x)).then(x.cmp(y)));
let mir = f.granularity == Granularity::MirBlock;
out.push(GraphTwin {
a: site_of(f, side, &ga, &q),
b: site_of(f, side, &gb, &seq_of(side, &gb)),
score: 1.0,
exact: true,
shared_kgrams: grams,
rare_shared: rare,
shared_words: ranked.iter().take(4).map(|k| label_of(k)).collect(),
found_by: vec![
format!(
"graph exact, inside ONE function: the same compiled group twice in `{}` — {k} {} each, {d} apart, not overlapping",
f.ident,
if mir { "MIR block(s)" } else { "fact line(s)" }
),
format!("{rare} rare fact(s) (df ≤ {}), {grams} {}-gram(s)", opts.rare_df, opts.kgram),
],
granularity: f.granularity,
same_function: true,
});
}
}
out
};
let found: Vec<Vec<GraphTwin>> = znippy_zoomies::gatling_forkjoin::gatling_map_balanced(fns, opts.workers(), 4, |f| (f.units.len().max(f.facts.len()) as u64).pow(2), |i, f| per_fn(i, f));
found.into_iter().flatten().collect()
}
/// What the graph pass read from a room: the repo's functions and the
/// rarity over the room's.
#[derive(Debug, Clone, Default)]
pub struct Gathered {
pub fns: Vec<CompiledFn>,
pub rarity: Rarity,
/// Functions of the repo the room holds no span for: their sites cannot
/// be placed, so they are in no group (counted, never guessed at).
pub without_span: usize,
/// Where it came from (a room scope), for the feed record.
pub source: String,
}
/// Gather the compiled facts of `repo`'s functions from a room, and the
/// rarity of every key over all of the room's (non-test, defined) functions.
#[cfg(feature = "code-room")]
///
/// `side` holds the repo's MIR block payloads (the room keeps the bodies
/// only, [`mimir_room::MirSide`]): a fn of the repo whose blocks it holds is
/// cut by block; the rest by fact line.
pub fn gather(room: &mimir_room::Room, repo: &str, side: &mimir_room::MirSide) -> anyhow::Result<Gathered> {
use mimir_room::MaskSpec;
use mimir_schema::{EdgeKind, kind as nk};
let spec = |repos: Vec<String>| MaskSpec { repos, node_kinds: vec![nk::FN.into(), nk::METHOD.into()], defined_only: true, is_test: Some(false), ..Default::default() };
let all: Vec<u64> = room.mask(&spec(Vec::new()))?.value.ordinals().to_vec();
let mine: BTreeSet<u64> = room.mask(&spec(vec![repo.to_string()]))?.value.ordinals().iter().copied().collect();
let mut raw: BTreeMap<u64, RawFn> = BTreeMap::new();
let mut without_span = 0usize;
for &o in &all {
// outside the repo only the keys count (the rarity): no file, no lines
let (file, start, end, ident) = match room.span(o) {
Some(s) if mine.contains(&o) => (s.file.to_string(), s.start_line, s.end_line, room.display_path(o)),
None if mine.contains(&o) => {
without_span += 1;
(String::new(), 0, u32::MAX, String::new())
}
_ => (String::new(), 0, u32::MAX, String::new()),
};
raw.insert(o, RawFn { moniker: room.moniker(o).to_string(), file, ident, item_start: start, item_end: end, ..Default::default() });
}
let short = |o: u64| -> String {
let p = room.display_path(o);
let parts: Vec<&str> = p.rsplit("::").take(2).collect();
parts.into_iter().rev().collect::<Vec<_>>().join("::")
};
// the line of every site of (from, to, kind) in the function's own file;
// outside the repo (rarity only) one key per edge is enough
let lines = |from: u64, to: u64, kind: EdgeKind, file: &str| -> Vec<u32> {
if file.is_empty() {
return vec![0];
}
room.sites(from, to, kind).into_iter().filter(|s| s.file == file).map(|s| s.start_line).collect()
};
for (kind, slot) in [(EdgeKind::Calls, 0u8), (EdgeKind::ReadsField, 1), (EdgeKind::TouchesTable, 2)] {
for (from, to) in room.out_pairs(kind, &all)? {
let Some(r) = raw.get(&from) else { continue };
let file = r.file.clone();
let ls = lines(from, to, kind, &file);
let r = raw.get_mut(&from).expect("present");
// labels are read for the repo's own functions only
let labelled = !file.is_empty();
for line in ls {
match slot {
0 => r.calls.push((room.moniker(to).to_string(), if labelled { short(to) } else { String::new() }, line)),
1 => {
let label = if labelled {
let f = room.node(to);
let owner = f.parent.and_then(|p| room.node(p).name).unwrap_or("?");
format!("{owner}.{}", f.name.unwrap_or("?"))
} else {
String::new()
};
r.fields.push((room.moniker(to).to_string(), label, line));
}
_ => {
let access = room.access_of(kind, from, to).map(|a| a.to_string()).unwrap_or_else(|| "touch".into());
r.tables.push((room.node(to).name.unwrap_or("?").to_string(), access, line));
}
}
}
}
}
for (from, to) in room.out_pairs(EdgeKind::Contains, &all)? {
let p = room.node(to);
if p.kind != Some(nk::LOCAL) {
continue;
}
let Some(r) = raw.get_mut(&from) else { continue };
let line = if r.file.is_empty() { 0 } else { p.start_line.unwrap_or(0) };
r.locals.push((p.name.unwrap_or("").to_string(), p.ty.unwrap_or("_").to_string(), line));
}
// MIR facts, where the room holds them: a fn with block nodes is cut by
// block; one with fingerprints only (a dependency) counts its block keys
// for the rarity; one without (an older dump) keeps its fact lines
let mut mir_fns: BTreeMap<u64, CompiledFn> = BTreeMap::new();
for (o, r) in &raw {
let Some(body) = room.mir_body(*o) else { continue };
// the repo's own fns are cut by block only with their blocks to place them
let full = mine.contains(o) && room.has_mir_blocks(*o, side);
if !full && mine.contains(o) {
continue;
}
let mut succ: Vec<(String, String)> = Vec::new();
let blocks: Vec<RawMirBlock> = if full {
let views = room.mir_blocks(*o, side);
// the control flow between the fn's blocks, by block name
let held: std::collections::HashSet<&str> = views.iter().map(|b| b.block).collect();
for (x, y) in room.mir_cfg(*o) {
if held.contains(x) && held.contains(y) {
succ.push((x.to_string(), y.to_string()));
}
}
views
.into_iter()
.map(|b| RawMirBlock {
block: b.block.to_string(),
fp: b.facts.fp.to_string(),
term: b.facts.term_kind().to_string(),
callee: b.facts.callee().map(str::to_string),
stmts: b.facts.stmts.iter().map(|s| s.text.to_string()).collect(),
lines: b.lines,
})
.collect()
} else {
body.blocks.iter().map(|b| RawMirBlock { block: b.block.to_string(), fp: b.fp.to_string(), term: b.term.to_string(), ..Default::default() }).collect()
};
if blocks.is_empty() {
continue;
}
let m = RawMirFn { moniker: r.moniker.clone(), file: r.file.clone(), ident: r.ident.clone(), item_start: r.item_start, item_end: r.item_end, blocks, succ };
mir_fns.insert(*o, mir_facts_of(&m));
}
let mut fns = Vec::new();
let mut sets: Vec<BTreeSet<String>> = Vec::new();
for (o, r) in &raw {
let c = match mir_fns.remove(o) {
Some(c) => c,
None => facts_of(r),
};
sets.push(c.facts.iter().map(|f| f.key.clone()).collect());
if mine.contains(o) && !r.file.is_empty() {
fns.push(c);
}
}
let rarity = Rarity::of(sets.iter().map(|s| s.iter().map(String::as_str).collect::<BTreeSet<&str>>()));
Ok(Gathered { fns, rarity, without_span, source: format!("code room {}", room.scope()) })
}
#[cfg(test)]
mod tests {
use super::*;
/// The gates the fixtures were set on: small MIR groups count (the
/// planted groups are four blocks), no weight floor.
fn small() -> GraphOptions {
GraphOptions { min_group_blocks: MIN_GROUP_LINES, min_group_weight: 0.0, min_group_callees: 2, min_interior_lines: 0, min_cover_both: 0.0, min_cover_one: 0.0, ..Default::default() }
}
/// RED before the boilerplate gates: a derive expansion (every block on
/// the one `#[derive]` line) and a group that shares only std /
/// formatting callees pair at the size gates, and are no finding now;
/// the planted group (five lines, three crate callees) still is.
#[test]
fn derive_lines_and_std_only_callees_are_no_mir_group() {
let on_one_line = |prefix: &str, l: u32, local: u32| -> Vec<RawMirBlock> {
planted_blocks(prefix, l, local).into_iter().map(|mut b| {
b.lines = vec![l];
b
}).collect()
};
let bg = |fns: &mut Vec<CompiledFn>| {
for i in 0..30u32 {
fns.push(mir_fn(&format!("bg{i}"), 1000 + 20 * i, vec![blk("0", "c0", None, &["_1=use(k:u64)"], &[1001 + 20 * i]), blk("1", &format!("d{i:x}"), Some(&format!("step{i}")), &["_2=use(_1)"], &[1002 + 20 * i]), blk("2", "c0", None, &["_1=use(k:u64)"], &[1003 + 20 * i])]));
}
};
let mut derive = vec![mir_fn("visit_map", 10, on_one_line("", 10, 5)), mir_fn("visit_seq", 40, on_one_line("c1.", 40, 11))];
bg(&mut derive);
assert!(pair(&derive, &rarity_of(&derive), &small()).twins.is_empty(), "every block on one line: a derive, no group");
let std_only = |prefix: &str, l0: u32, local: u32| -> Vec<RawMirBlock> {
planted_blocks(prefix, l0, local).into_iter().map(|mut b| {
if let Some(c) = &b.callee {
b.callee = Some(c.replace("rust-analyzer cargo grp *", "rust-analyzer cargo core *"));
}
b
}).collect()
};
let mut fmt = vec![mir_fn("render_a", 10, std_only("", 13, 5)), mir_fn("render_b", 40, std_only("c1.", 43, 11))];
bg(&mut fmt);
assert!(pair(&fmt, &rarity_of(&fmt), &small()).twins.is_empty(), "only core callees shared: boilerplate");
let mut real = vec![mir_fn("decode", 10, planted_blocks("", 13, 5)), mir_fn("serve", 40, planted_blocks("c1.", 43, 11))];
bg(&mut real);
assert_eq!(pair(&real, &rarity_of(&real), &small()).twins.len(), 1);
// the same planted group in two derive expansions (`::_::`): generated, no group
let mut derived = vec![mir_fn("x::_::A::visit_map", 10, planted_blocks("", 13, 5)), mir_fn("x::_::B::visit_map", 40, planted_blocks("c1.", 43, 11))];
bg(&mut derived);
assert!(pair(&derived, &rarity_of(&derived), &small()).twins.is_empty(), "derive expansions are generated code");
// only at the item's edges (a builder scaffold around two field lists): no group
let mut edges = vec![mir_fn("schema_a", 11, planted_blocks("", 13, 5)), mir_fn("schema_b", 41, planted_blocks("c1.", 43, 11))];
for f in edges.iter_mut() {
f.item_start = f.units.iter().flat_map(|u| u.lines.iter().copied()).min().unwrap() - 1;
f.item_end = f.item_start + 5;
}
bg(&mut edges);
assert!(pair(&edges, &rarity_of(&edges), &GraphOptions { min_interior_lines: MIN_INTERIOR_LINES, ..small() }).twins.is_empty(), "no interior line: a scaffold");
// a prologue of two long functions (5 of 60 lines each): no group
let mut long = vec![mir_fn("append_a", 10, planted_blocks("", 13, 5)), mir_fn("append_b", 100, planted_blocks("c1.", 103, 11))];
for f in long.iter_mut() {
f.item_end = f.item_start + 60;
}
bg(&mut long);
assert!(pair(&long, &rarity_of(&long), &GraphOptions { min_cover_both: MIN_COVER_BOTH, min_cover_one: MIN_COVER_ONE, ..small() }).twins.is_empty(), "a shared prologue covers too little");
// one file compiled into two crates: the same file and span, no copy
let mut twice = vec![mir_fn("t1::shop::rows", 10, planted_blocks("", 13, 5)), mir_fn("t2::shop::rows", 10, planted_blocks("", 13, 5))];
twice[1].moniker = twice[1].moniker.replace("grp 0.1.0", "grp2 0.1.0");
bg(&mut twice);
assert!(pair(&twice, &rarity_of(&twice), &small()).twins.is_empty(), "one source in two crates");
}
/// RED before the MIR gates: the planted four-block group is a twin at
/// the fixture gates and NOT at the defaults — four basic blocks are a
/// fraction of a source line.
#[test]
fn a_four_block_mir_group_is_below_the_default_gates() {
let mut fns = vec![mir_fn("decode", 10, planted_blocks("", 13, 5)), mir_fn("serve", 40, planted_blocks("c1.", 43, 11))];
for i in 0..30u32 {
fns.push(mir_fn(&format!("bg{i}"), 1000 + 20 * i, vec![blk("0", "c0", None, &["_1=use(k:u64)"], &[1001 + 20 * i]), blk("1", &format!("d{i:x}"), Some(&format!("step{i}")), &["_2=use(_1)"], &[1002 + 20 * i]), blk("2", "c0", None, &["_1=use(k:u64)"], &[1003 + 20 * i])]));
}
assert_eq!(pair(&fns, &rarity_of(&fns), &small()).twins.len(), 1);
assert!(pair(&fns, &rarity_of(&fns), &GraphOptions::default()).twins.is_empty());
let heavy = GraphOptions { min_group_blocks: 3, min_group_weight: 1.0e6, ..Default::default() };
assert!(pair(&fns, &rarity_of(&fns), &heavy).twins.is_empty(), "the weight floor gates too");
}
/// The fan-out changes nothing: one worker and four judge the same
/// candidates and scan the same bodies into the same twins, in order.
#[test]
fn one_worker_and_many_give_the_same_twins() {
let mut fns = Vec::new();
for k in 0..6u32 {
fns.push(mir_fn(&format!("dec{k}"), 10 + 100 * k, planted_blocks("", 13 + 100 * k, 5)));
}
let (p1, p2) = (planted("a"), planted("b"));
let mut body = as_refs(&p1);
body.push(vec!["c:log_route"]);
body.extend(as_refs(&p2));
fns.push(compiled("twice", 5000, &body));
for i in 0..30u32 {
fns.push(mir_fn(&format!("bg{i}"), 1000 + 20 * i, vec![blk("0", "c0", None, &["_1=use(k:u64)"], &[1001 + 20 * i]), blk("1", &format!("d{i:x}"), Some(&format!("step{i}")), &["_2=use(_1)"], &[1002 + 20 * i]), blk("2", "c0", None, &["_1=use(k:u64)"], &[1003 + 20 * i])]));
}
let rarity = rarity_of(&fns);
let one = pair(&fns, &rarity, &GraphOptions { threads: 1, ..small() });
let many = pair(&fns, &rarity, &GraphOptions { threads: 4, ..small() });
assert!(one.twins.len() > 6, "{}", one.twins.len());
assert_eq!(serde_json::to_value(&one.twins).unwrap(), serde_json::to_value(&many.twins).unwrap());
assert_eq!((one.candidates, one.candidates_unjudged), (many.candidates, many.candidates_unjudged));
}
/// RED before: the repeats inside one function were scanned only when
/// the cross pairs left budget — a repo that ran it out (nornir) found
/// no repeat at all. Now they are scanned first, whatever the budget.
#[test]
fn a_repeat_inside_one_function_survives_a_spent_budget() {
let (p1, p2) = (planted("a"), planted("b"));
let mut body = as_refs(&p1);
body.push(vec!["c:log_route"]);
body.extend(as_refs(&p2));
let mut fns = vec![compiled("twice", 10, &body)];
fns.extend(background(30));
let spent = GraphOptions { budget_ms: 0, ..small() };
let r = pair(&fns, &rarity_of(&fns), &spent);
assert!(r.twins.iter().any(|t| t.same_function), "{:#?}", r.twins);
}
/// A raw function at `start` whose lines are `body`: each entry is the
/// facts of one line, `c:x` a call, `f:x` a field, `l:name:ty` a local.
fn raw(name: &str, start: u32, body: &[&[&str]]) -> RawFn {
let mut r = RawFn {
moniker: format!("rust-analyzer cargo grp 0.1.0 {name}()."),
file: "src/lib.rs".into(),
ident: name.into(),
item_start: start,
item_end: start + body.len() as u32 + 1,
..Default::default()
};
for (i, line) in body.iter().enumerate() {
let l = start + 1 + i as u32;
for f in *line {
let (kind, rest) = f.split_once(':').unwrap();
match kind {
"c" => r.calls.push((format!("rust-analyzer cargo dep 1.2.3 {rest}()."), rest.into(), l)),
"f" => r.fields.push((format!("rust-analyzer cargo grp 0.1.0 Ledger#{rest}."), format!("Ledger.{rest}"), l)),
"l" => {
let (n, ty) = rest.split_once(':').unwrap();
r.locals.push((n.into(), ty.into(), l));
}
_ => unreachable!(),
}
}
}
r
}
/// The planted group: seven lines of compiled facts.
fn planted(local: &str) -> Vec<Vec<String>> {
vec![
vec![format!("l:{local}_acc:Vec<(String, u64)>")],
vec![format!("l:{local}_carry:u64")],
vec!["c:ledger_open".into(), "f:entries".into()],
vec!["c:weigh_entry".into(), format!("l:{local}_w:u64")],
vec!["c:u64::wrapping_mul".into(), "f:seed".into()],
vec!["c:Vec::push".into()],
vec!["c:sort_by_weight".into(), "f:entries".into()],
]
}
fn as_refs(v: &[Vec<String>]) -> Vec<Vec<&str>> {
v.iter().map(|l| l.iter().map(String::as_str).collect()).collect()
}
fn compiled(name: &str, start: u32, body: &[Vec<&str>]) -> CompiledFn {
let b: Vec<&[&str]> = body.iter().map(Vec::as_slice).collect();
facts_of(&raw(name, start, &b))
}
/// Background functions: the common keys (`Vec::push`, `u64`) are
/// everywhere, the planted group's own callees nowhere else.
fn background(n: usize) -> Vec<CompiledFn> {
(0..n)
.map(|i| {
let c = format!("c:step{i}");
compiled(&format!("bg{i}"), 1000 + 20 * i as u32, &[vec!["c:Vec::push", "l:x:u64"], vec![c.as_str()], vec!["l:y:u64", "c:Vec::push"], vec!["c:String::len"]])
})
.collect()
}
fn rarity_of(fns: &[CompiledFn]) -> Rarity {
Rarity::of(fns.iter().map(|f| f.facts.iter().map(|x| x.key.as_str()).collect::<BTreeSet<&str>>()))
}
/// RED before this module: two functions share one compiled statement
/// group — B's copy has its locals RENAMED and two unrelated statements
/// INTERLEAVED — and the pair is found from the graph facts alone. There
/// is no embeddings table and no vector anywhere in this test.
#[test]
fn a_shared_compiled_group_pairs_across_interleaved_noise_without_vectors() {
let (pa, pb) = (planted("a"), planted("zz"));
let a_body = as_refs(&pa);
let mut b_body = as_refs(&pb);
// noise interleaved into B: a log call and an unrelated local chain
b_body.insert(2, vec!["c:log_route", "l:banner:String"]);
b_body.insert(5, vec!["c:str::to_ascii_uppercase"]);
let mut fns = vec![compiled("summarise", 10, &a_body), compiled("rollup", 40, &b_body)];
fns.extend(background(30));
let r = pair(&fns, &rarity_of(&fns), &small());
assert_eq!(r.twins.len(), 1, "exactly the planted twin: {:#?}", r.twins);
let t = &r.twins[0];
assert_eq!((t.a.ident.as_str(), t.b.ident.as_str()), ("summarise", "rollup"));
assert!(t.exact, "the noise stays outside and the renamed locals move no key: {t:#?}");
assert_eq!(t.score, 1.0);
assert!(t.rare_shared >= 2 && t.shared_kgrams >= MIN_SHARED_KGRAMS, "{t:#?}");
assert_eq!(t.a.group_lines, (11..=17).collect::<Vec<_>>());
// B's group skips the two noise lines (43 and 46)
assert_eq!(t.b.group_lines, vec![41, 42, 44, 45, 47, 48, 49], "{t:#?}");
assert_eq!(t.a.key, t.b.key, "one fingerprint");
}
/// Local NAMES never reach a key: the same group with every local renamed
/// is ONE fingerprint, and still pairs.
#[test]
fn a_group_differing_only_in_local_names_still_pairs() {
let (pa, pb) = (planted("alpha"), planted("omega"));
let a = compiled("one", 1, &as_refs(&pa));
let b = compiled("two", 30, &as_refs(&pb));
assert_eq!(a.facts.iter().map(|f| &f.key).collect::<Vec<_>>(), b.facts.iter().map(|f| &f.key).collect::<Vec<_>>());
let mut fns = vec![a, b];
fns.extend(background(10));
let r = pair(&fns, &rarity_of(&fns), &small());
assert_eq!(r.twins.len(), 1, "{:#?}", r.twins);
assert!(r.twins[0].exact);
}
/// A near copy (one callee swapped) pairs on the weighted Jaccard, not
/// exactly; an unrelated function that shares only common keys never pairs.
#[test]
fn a_near_copy_pairs_on_the_score_and_common_keys_never_open_a_pair() {
let (pa, pb) = (planted("a"), planted("b"));
let a_body = as_refs(&pa);
let mut b_body = as_refs(&pb);
b_body[6] = vec!["c:sort_unstable_by_weight", "f:entries"];
let control = compiled("control", 200, &[vec!["c:Vec::push", "l:q:u64"], vec!["c:u64::wrapping_mul"], vec!["c:Vec::push"], vec!["c:String::len", "l:r:u64"]]);
let mut fns = vec![compiled("near_a", 10, &a_body), compiled("near_b", 40, &b_body), control];
fns.extend(background(30));
let r = pair(&fns, &rarity_of(&fns), &small());
assert_eq!(r.twins.len(), 1, "{:#?}", r.twins);
let t = &r.twins[0];
assert!(!t.exact && t.score >= SCORE_FLOOR && t.score < 1.0, "{t:#?}");
assert!(r.twins.iter().all(|t| t.a.ident != "control" && t.b.ident != "control"));
}
/// A version bump of a dependency moves no key (stable monikers).
#[test]
fn a_dependency_bump_moves_no_key() {
let mut r = raw("f", 1, &[&["c:open"]]);
let a = facts_of(&r);
r.calls[0].0 = r.calls[0].0.replace("1.2.3", "9.9.9");
assert_eq!(a.facts[0].key, facts_of(&r).facts[0].key);
}
/// A MIR block of a test function: `fp` names its shape, `stmts` its
/// statements, `lines` where it sits.
fn blk(name: &str, fp: &str, callee: Option<&str>, stmts: &[&str], lines: &[u32]) -> RawMirBlock {
RawMirBlock {
block: name.into(),
fp: format!("{:0>16}", fp),
term: if callee.is_some() { "call".into() } else { "goto".into() },
callee: callee.map(|c| format!("rust-analyzer cargo grp * {c}().")),
stmts: stmts.iter().map(|s| s.to_string()).collect(),
lines: lines.to_vec(),
}
}
fn mir_fn(name: &str, start: u32, blocks: Vec<RawMirBlock>) -> CompiledFn {
let end = blocks.iter().flat_map(|b| b.lines.iter().copied()).max().unwrap_or(start) + 1;
mir_facts_of(&RawMirFn { moniker: format!("rust-analyzer cargo grp 0.1.0 {name}()."), file: "src/lib.rs".into(), ident: name.into(), item_start: start, item_end: end, blocks, succ: Vec::new() })
}
/// The planted block group: four MIR blocks (the same shapes, callees and
/// statements), at `l0..` — locals numbered as each body numbers them.
fn planted_blocks(prefix: &str, l0: u32, local: u32) -> Vec<RawMirBlock> {
let (a, b) = (local, local + 1);
vec![
blk(&format!("{prefix}4"), "a11", Some("ledger_open"), &[&format!("_{a}=use(k:u64)")], &[l0]),
blk(&format!("{prefix}5"), "a12", Some("weigh_entry"), &[&format!("_{b}=Mul(_{a},k:u64)")], &[l0 + 1]),
blk(&format!("{prefix}6"), "a13", None, &[&format!("_{a}=AddWithOverflow(_{a},_{b})")], &[l0 + 2]),
blk(&format!("{prefix}7"), "a14", Some("sort_by_weight"), &[&format!("_{b}=ref(_{a})")], &[l0 + 3, l0 + 4]),
]
}
/// RED before MIR granularity: two functions that are otherwise
/// DIFFERENT (their own blocks before and after) share one group of four
/// MIR blocks — at other block numbers, other local numbers and other
/// lines — and the pair is found at `mir_block` granularity, its sites
/// naming the blocks and the source lines they sit on.
#[test]
fn a_shared_block_group_pairs_inside_two_different_functions_at_mir_block_granularity() {
let mut a = vec![blk("0", "f01", Some("parse_header"), &["_1=use(k:u8)"], &[11]), blk("1", "f02", None, &["_2=Lt(_1,k:u8)"], &[12])];
a.extend(planted_blocks("", 13, 5));
a.push(blk("9", "f03", Some("log_route"), &["_9=use(k:&str)"], &[18]));
let mut b = vec![blk("0", "e01", Some("open_socket"), &["_1=use(k:i32)"], &[41])];
b.extend(planted_blocks("c1.", 43, 11));
b.push(blk("12", "e02", Some("flush_all"), &["_3=use(k:bool)"], &[48]));
b.push(blk("13", "e03", None, &["_4=Not(_3)"], &[49]));
let mut fns = vec![mir_fn("decode", 10, a), mir_fn("serve", 40, b)];
// background: common blocks everywhere, the planted ones nowhere else
for i in 0..30u32 {
fns.push(mir_fn(&format!("bg{i}"), 1000 + 20 * i, vec![blk("0", "c0", None, &["_1=use(k:u64)"], &[1001 + 20 * i]), blk("1", &format!("d{i:x}"), Some(&format!("step{i}")), &["_2=use(_1)"], &[1002 + 20 * i]), blk("2", "c0", None, &["_1=use(k:u64)"], &[1003 + 20 * i])]));
}
let r = pair(&fns, &rarity_of(&fns), &small());
assert_eq!(r.granularity, Granularity::MirBlock);
assert_eq!(r.functions_mir, fns.len());
assert_eq!(r.twins.len(), 1, "exactly the planted group: {:#?}", r.twins);
let t = &r.twins[0];
assert_eq!((t.a.ident.as_str(), t.b.ident.as_str()), ("decode", "serve"));
assert_eq!(t.granularity, Granularity::MirBlock);
assert!(t.exact && t.score == 1.0, "the same four blocks, locals renumbered: {t:#?}");
assert_eq!(t.a.group_blocks, vec!["4", "5", "6", "7"]);
assert_eq!(t.b.group_blocks, vec!["c1.4", "c1.5", "c1.6", "c1.7"]);
assert_eq!(t.a.group_lines, vec![13, 14, 15, 16, 17]);
assert_eq!(t.b.group_lines, vec![43, 44, 45, 46, 47]);
assert_eq!(t.a.key, t.b.key, "one fingerprint");
assert!(t.found_by[0].contains("MIR blocks"), "{:?}", t.found_by);
let json = serde_json::to_value(t).unwrap();
assert_eq!(json["granularity"], "mir_block");
assert_eq!(json["a"]["granularity"], "mir_block");
}
/// A function with MIR facts is never paired with a fact-line one (two
/// different cuts of code), and a room with no MIR facts answers at
/// fact-line granularity exactly as before.
#[test]
fn granularities_never_mix_and_fact_lines_stay_the_fallback() {
let (pa, pb) = (planted("a"), planted("zz"));
let fact = compiled("summarise", 10, &as_refs(&pa));
let mut fns = vec![fact.clone(), compiled("rollup", 40, &as_refs(&pb))];
fns.extend(background(30));
let r = pair(&fns, &rarity_of(&fns), &small());
assert_eq!((r.granularity, r.functions_mir), (Granularity::FactLine, 0));
assert_eq!(r.twins.len(), 1);
assert_eq!(r.twins[0].granularity, Granularity::FactLine);
assert!(r.twins[0].a.group_blocks.is_empty());
// the same planted group, one side now cut by MIR: no cross pair
let mut mixed = vec![fact, mir_fn("rollup", 40, planted_blocks("", 41, 3))];
mixed.extend(background(30));
let r = pair(&mixed, &rarity_of(&mixed), &small());
assert!(r.twins.is_empty(), "{:#?}", r.twins);
}
/// RED before self pairs: ONE function holds the planted group twice (a
/// pasted block, two noise lines between) — the pair is that function with
/// itself, the two runs do not overlap; a function holding it once pairs
/// with nothing.
#[test]
fn a_group_repeated_inside_one_function_pairs_with_itself_without_overlap() {
let (p1, p2) = (planted("a"), planted("b"));
let mut body = as_refs(&p1);
body.push(vec!["c:log_route"]);
body.push(vec!["c:str::to_ascii_uppercase"]);
body.extend(as_refs(&p2));
let mut fns = vec![compiled("twice", 10, &body)];
fns.extend(background(30));
let r = pair(&fns, &rarity_of(&fns), &small());
assert_eq!(r.twins.len(), 1, "exactly the repeat inside `twice`: {:#?}", r.twins);
let t = &r.twins[0];
assert!(t.same_function && t.exact, "{t:#?}");
assert_eq!((t.a.ident.as_str(), t.b.ident.as_str()), ("twice", "twice"));
assert_eq!(t.a.group_lines, (11..=17).collect::<Vec<_>>(), "{t:#?}");
assert_eq!(t.b.group_lines, (20..=26).collect::<Vec<_>>(), "{t:#?}");
assert!(t.a.group_lines.last() < t.b.group_lines.first(), "the runs never overlap");
assert_eq!(t.a.key, t.b.key);
assert!(t.found_by[0].contains("inside ONE function"), "{:?}", t.found_by);
assert_eq!(serde_json::to_value(t).unwrap()["same_function"], true);
// the group once: nothing
let mut once = vec![compiled("once", 10, &as_refs(&p1))];
once.extend(background(30));
assert!(pair(&once, &rarity_of(&once), &small()).twins.is_empty());
}
/// A periodic body (one unit repeated) never yields overlapping runs.
#[test]
fn a_repeat_never_overlaps_itself() {
let unit = vec!["c:ledger_open", "f:entries", "l:w:u64"];
let body: Vec<Vec<&str>> = (0..9).map(|_| unit.clone()).collect();
let mut fns = vec![compiled("periodic", 10, &body)];
fns.extend(background(30));
for t in pair(&fns, &rarity_of(&fns), &small()).twins {
assert!(t.a.group_lines.last() < t.b.group_lines.first(), "{t:#?}");
}
}
fn mir_fn_cfg(name: &str, start: u32, blocks: Vec<RawMirBlock>, succ: &[(&str, &str)]) -> CompiledFn {
let end = blocks.iter().flat_map(|b| b.lines.iter().copied()).max().unwrap_or(start) + 1;
let succ = succ.iter().map(|(a, b)| (a.to_string(), b.to_string())).collect();
mir_facts_of(&RawMirFn { moniker: format!("rust-analyzer cargo grp 0.1.0 {name}()."), file: "src/lib.rs".into(), ident: name.into(), item_start: start, item_end: end, blocks, succ })
}
/// RED before the CFG shape: a MIR fragment is a CONNECTED run of blocks.
/// The same four blocks in two functions pair when each side's blocks flow
/// into each other (CFG_SUCC 4→5→6→7) — the edges are part of the group's
/// keys; when one side's four are two unconnected halves (4→5, 6→7 and
/// nothing between), no group of three connected blocks exists there and
/// nothing pairs.
#[test]
fn a_mir_fragment_is_a_connected_run_of_blocks() {
let chain = [("4", "5"), ("5", "6"), ("6", "7")];
let chain_c1 = [("c1.4", "c1.5"), ("c1.5", "c1.6"), ("c1.6", "c1.7")];
let background = |fns: &mut Vec<CompiledFn>| {
for i in 0..30u32 {
fns.push(mir_fn(&format!("bg{i}"), 1000 + 20 * i, vec![blk("0", "c0", None, &["_1=use(k:u64)"], &[1001 + 20 * i]), blk("1", &format!("d{i:x}"), Some(&format!("step{i}")), &["_2=use(_1)"], &[1002 + 20 * i])]));
}
};
let mut fns = vec![mir_fn_cfg("decode", 10, planted_blocks("", 11, 5), &chain), mir_fn_cfg("serve", 40, planted_blocks("c1.", 41, 11), &chain_c1)];
background(&mut fns);
let r = pair(&fns, &rarity_of(&fns), &small());
assert_eq!(r.twins.len(), 1, "{:#?}", r.twins);
assert!(r.twins[0].exact, "the same blocks AND the same flow: {:#?}", r.twins[0]);
assert!(fns[0].facts.iter().any(|f| f.key.starts_with("e:")), "the CFG edges are keys");
// serve's four blocks: two halves that do not flow into each other
let mut split = vec![mir_fn_cfg("decode", 10, planted_blocks("", 11, 5), &chain), mir_fn_cfg("serve", 40, planted_blocks("c1.", 41, 11), &[("c1.4", "c1.5"), ("c1.6", "c1.7")])];
background(&mut split);
let r = pair(&split, &rarity_of(&split), &small());
assert!(r.twins.is_empty(), "two unconnected halves are no fragment of three: {:#?}", r.twins);
}
/// RED before the bound: a pairing judged every candidate however many.
/// Past the candidate cap the rest is counted and named, the candidates
/// sharing the most rare keys are judged first (the planted twin, which
/// shares seven, survives a cap of one), and a zero budget judges nothing
/// and says so.
#[test]
fn the_pairing_is_bounded_and_counts_what_it_did_not_judge() {
let (pa, pb) = (planted("a"), planted("zz"));
let mut fns = vec![compiled("summarise", 10, &as_refs(&pa)), compiled("rollup", 40, &as_refs(&pb))];
// a weak candidate: one rare key in common with summarise
fns.push(compiled("weak", 300, &[vec!["c:ledger_open", "l:q:u64"], vec!["c:other_a"], vec!["c:other_b"], vec!["c:other_c"]]));
fns.extend(background(30));
let rarity = rarity_of(&fns);
let full = pair(&fns, &rarity, &small());
assert!(full.candidates >= 2 && full.candidates_unjudged == 0 && full.bounded_by.is_empty(), "{full:#?}");
let capped = pair(&fns, &rarity, &GraphOptions { max_candidates: 1, ..Default::default() });
assert_eq!(capped.candidates_unjudged, full.candidates - 1);
assert!(capped.bounded_by.contains("judged at most"), "{}", capped.bounded_by);
assert_eq!(capped.twins.len(), 1, "the best candidate first: {:#?}", capped.twins);
let none = pair(&fns, &rarity, &GraphOptions { budget_ms: 0, ..Default::default() });
assert_eq!((none.candidates_unjudged, none.twins.len()), (none.candidates, 0), "{none:#?}");
assert!(none.bounded_by.contains("budget"), "{}", none.bounded_by);
}
#[test]
fn runs_split_past_the_gap() {
assert_eq!(runs(&[0, 1, 5, 6, 20], 3), vec![vec![0, 1, 5, 6], vec![20]]);
assert_eq!(runs(&[0, 5], 3), vec![vec![0], vec![5]]);
}
}