src/mimir_analyze.rs
//! Mimir `analyze duplicates` — **copied-not-moved** detection.
//!
//! The vector index can see duplicates directly: two symbols whose embeddings are
//! near-identical are *semantically the same code*. On its own that is noisy (a
//! trait impl and its default method embed alike). So this analysis INTERSECTS the
//! vector signal with STRUCTURAL signals already in Mimir — the item signature and
//! the `call_edges` callee neighbourhood — and only keeps a pair when BOTH agree:
//!
//! * vector cosine ≥ `cosine` threshold → "semantically the same", AND
//! * structural agreement ≥ `structural` → "literally the same".
//!
//! Cross-scope pairs (different crates/repos) that pass the AND are **copied-not-
//! moved** candidates. Surviving pairs are unioned into clusters, ranked by
//! similarity × size, and each cluster gets a keep/kill recommendation per the
//! move-means-delete + REUSE laws: one copy is canonical (keep — preferring a
//! shared reuse home such as `edda`/`skidbladnir`), the rest are the rot
//! (kill, or re-point at the canonical home).
//!
//! This module is the PURE analysis core: it takes already-materialised
//! [`SymbolVec`] rows (embedding + structural fingerprint) and returns a
//! serialisable [`DuplicateReport`]. Sourcing those rows from the warehouse
//! (`embeddings` ⋈ `symbol_facts` ⋈ `call_edges`) and the CLI/facett surfaces are
//! thin wiring layered on top — this core has no warehouse or GPU dependency, so
//! it is exhaustively unit-testable.
use std::collections::{BTreeMap, BTreeSet};
use serde::Serialize;
/// **Per-phase progress for the long lens folds** — stinky mimir-11
/// (observability), MEASURED 2026-08-19: `mimir analyze semantic-clones` over
/// the 68 k-vector nordisk corpus produced **zero bytes for 9.5 minutes** and
/// was then killed blind by a timeout; a run that is working and a run that is
/// wedged looked EXACTLY alike. The embed verb next door already does this right
/// (`vector/store.rs` prints `nornir-embed: done/total · chunk/s · eta`), so
/// this is that habit rather than a new one.
///
/// OFF by default, switched on by the CLI arms only. The same folds run
/// in-process inside the Mímir RPC handlers, where a per-RPC stderr commentary
/// would be noise in a live instrument — the caller who owns a terminal is the
/// caller who gets the terminal output. Lines go to **stderr**; the single JSON
/// answer keeps stdout to itself.
pub mod progress {
use std::sync::atomic::{AtomicBool, Ordering};
use std::time::Instant;
static ON: AtomicBool = AtomicBool::new(false);
/// Turn per-phase progress on for this process (the CLI arms call this).
pub fn enable() {
ON.store(true, Ordering::Relaxed);
}
/// Whether progress is being printed.
pub fn enabled() -> bool {
ON.load(Ordering::Relaxed)
}
/// One line, now.
pub fn say(msg: impl std::fmt::Display) {
if enabled() {
eprintln!("nornir-mimir: {msg}");
}
}
/// A named phase that announces itself on ENTRY and reports elapsed time
/// plus its result on [`Phase::done`]. Announcing on entry is the whole
/// point: the 9.5-minute silence happened INSIDE a phase, so a line printed
/// only on completion would have printed nothing at all.
pub struct Phase {
name: &'static str,
t: Instant,
}
impl Phase {
pub fn start(name: &'static str, detail: impl std::fmt::Display) -> Self {
say(format_args!("{name} … {detail}"));
Phase {
name,
t: Instant::now(),
}
}
pub fn done(self, detail: impl std::fmt::Display) {
say(format_args!(
"{} done in {:.1}s — {detail}",
self.name,
self.t.elapsed().as_secs_f64()
));
}
}
}
/// One embedded code symbol plus its structural fingerprint — the analysis input.
///
/// `vector` is the raw embedding (need not be pre-normalised; cosine normalises).
/// `signature` and `callees` are the structural signals the vector match is
/// intersected with to reject semantic-but-not-literal look-alikes.
#[derive(Debug, Clone)]
pub struct SymbolVec {
/// Stable, globally-unique id — e.g. `repo::crate::module::name`.
pub id: String,
pub repo: String,
pub crate_name: String,
pub module_path: String,
pub item_kind: String,
pub item_name: String,
pub file: String,
pub line: u32,
/// The item signature (`symbol_facts.signature`) when known.
pub signature: Option<String>,
/// The callee identifiers this item invokes (`call_edges.callee_ident`).
pub callees: BTreeSet<String>,
/// Line span of the embedding CHUNK the vector came from (`end - start + 1`).
/// This is the chunk's extent, NOT the item's — `symbol_facts` has no
/// `end_line` (stinky mimir-2), so it is the only size signal available.
/// `0` = unknown/not applicable (hand-built rows, slice rows) and is never
/// treated as "small".
pub span_lines: u32,
/// **PROVENANCE of the vector** — the identity of the embedding-manifest chunk
/// [`best_vector`] attributed to this symbol, as `repo<SEP>file<SEP>start-end`.
/// Empty for rows not built from a manifest chunk (hand-built test rows, the
/// call-chain SLICE rows, benches), which therefore share a chunk with nothing.
///
/// Load-bearing, not decorative: `symbol_facts` has no `end_line` (stinky
/// mimir-2), so attribution is a CONTAINMENT heuristic — every symbol whose
/// `line` falls inside one <=120-line chunk is handed THE SAME vector. Two
/// such symbols then have cosine EXACTLY 1.0 by construction, which is a fact
/// about the chunking, not evidence of similarity. Recording which chunk a
/// vector came from is what lets the gates refuse that pair; see
/// [`shares_one_chunk_vector`].
///
/// ⚠ IT IS THE CHUNK INSTANCE, NOT THE `content_hash`, AND THE DIFFERENCE IS
/// THE WHOLE POINT. `content_hash` is CONTENT-addressed, so a genuine
/// byte-identical copy of a helper in two crates carries the SAME hash — the
/// exact true positive SimilarCode exists to find. Keying the refusal on the
/// hash would delete those findings. RED-SEEN: the first version of this gate
/// did key on `content_hash`, and
/// `assembled_rows_feed_the_duplicate_detector` went from 1 cluster to 0.
/// `repo` is part of the key because the same relative path (`src/lib.rs`)
/// exists in every repo and [`assemble_symbol_vecs`] runs per repo.
pub chunk_hash: String,
/// **The ITEM's last line** — the extent `symbol_facts` has never carried
/// (stinky mimir-2). `0` = UNKNOWN, which is never treated as "small" and
/// never treated as "disjoint".
///
/// With [`Self::line`] this makes an item's own span expressible for the
/// first time, which is what lets [`chunk_share_verdict`] tell the two
/// causes of a shared vector apart. Sources, in order of availability:
/// [`crate::vector::spans::ItemSpan::end_line`] (source-side, no warehouse,
/// MEASURED 100 % of parseable files) and `scip_occurrences.enc_end_line`
/// (warehouse-side, coverage unmeasured — see the module note).
pub item_end_line: u32,
/// **The enclosing `impl` header**, verbatim from the `impl` row the syn
/// walker emits beside every impl block (`symbol_facts.item_kind = "impl"`,
/// `item_name = "impl Cloud for UpCloud"` or `"impl UpCloud"`). `Some` only
/// for a method the walker recorded INSIDE that block — its `module_path` is
/// `<impl's module_path>::<SelfTy>`, which is how [`assemble_symbol_vecs`]
/// joins the two rows without re-parsing any source.
///
/// Load-bearing for precision: 8 of the top 20 type-3 clusters in the
/// 2026-09-10 sweep were `impl Trait for X` families where `structural = 1.00`
/// only meant the signature agreed — which a trait GUARANTEES. `None` = not
/// inside an impl, or unknown (hand-built rows, slice rows, benches).
pub impl_header: Option<String>,
/// The embedding vector.
pub vector: Vec<f32>,
}
/// **Why a cluster member is correct-by-construction rather than a copy.**
///
/// The type-3 gate scores signature + callee-set agreement, and three item
/// shapes satisfy it WITHOUT anyone having copied anything: a method body of
/// `impl Trait for X` (the trait dictates the signature), a constructor (every
/// `fn new(..) -> Self` embeds alike — inventory §3 #2 measured cosine `1.0000`
/// on four-line `Self { .. }` bodies), and a zero-argument accessor (`fn x(self)`
/// families like `path`/`header`/`tx`, inventory #16/#17/#19). A cluster whose
/// EVERY member has one of these shapes is not evidence of copying, so the
/// detector suppresses it by default — and REPORTS the suppression (dwarves'
/// dupes-box rule: suppressions are always reported). `--keep-trait-impls`
/// turns the filter off and labels each member with its shape instead.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[serde(rename_all = "snake_case")]
pub enum TrivialShape {
/// Method body inside `impl <Trait> for <Type>` — [`SymbolVec::impl_header`]
/// carries ` for `.
TraitImpl,
/// `new` / `new_*` / `default` — a constructor.
Constructor,
/// Signature is exactly `fn <name>(self)`: a receiver and nothing else.
Accessor,
}
impl TrivialShape {
pub fn as_str(self) -> &'static str {
match self {
TrivialShape::TraitImpl => "trait-impl",
TrivialShape::Constructor => "constructor",
TrivialShape::Accessor => "accessor",
}
}
}
/// Classify one symbol by the shape that would make its structural agreement
/// meaningless. Pure over the facts already in the row — `item_kind`,
/// `item_name`, `signature`, [`SymbolVec::impl_header`] — no source is read.
/// `None` = an ordinary item whose agreement IS evidence.
pub fn trivial_shape(s: &SymbolVec) -> Option<TrivialShape> {
if s.item_kind != "fn" {
return None;
}
if s.impl_header.as_deref().is_some_and(|h| h.contains(" for ")) {
return Some(TrivialShape::TraitImpl);
}
if s.item_name == "new" || s.item_name.starts_with("new_") || s.item_name == "default" {
return Some(TrivialShape::Constructor);
}
if s
.signature
.as_deref()
.is_some_and(|sig| sig == format!("fn {}(self)", s.item_name))
{
return Some(TrivialShape::Accessor);
}
None
}
impl SymbolVec {
/// The item's own 1-based inclusive extent, when known.
///
/// `None` while [`Self::item_end_line`] is `0` — and the difference between
/// "unknown" and "known" is load-bearing, so it is an `Option` and not a
/// pair of numbers a caller can accidentally compare.
pub fn extent(&self) -> Option<(u32, u32)> {
(self.item_end_line >= self.line && self.item_end_line > 0).then_some((self.line, self.item_end_line))
}
}
/// **Why two rows share one vector** — the distinction the old boolean could not
/// make.
///
/// [`shares_one_chunk_vector`] answers *"is this pair's cosine an artefact?"*
/// with one bit, and that bit is right: two symbols attributed to the same
/// embedding chunk have cosine EXACTLY 1.0 by construction, which is a fact
/// about the chunker and not evidence of anything. But it collapsed two very
/// different situations into one refusal, and only one of them is permanent.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[serde(rename_all = "snake_case")]
pub enum ChunkShareVerdict {
/// Different chunks (or no provenance): the vectors are independent and the
/// cosine means what it says.
NotShared,
/// Same chunk, and at least one extent is UNKNOWN. Nothing can be said and
/// nothing can be done about it from here — this is stinky mimir-2 itself.
UnknownExtent,
/// Same chunk, extents known and OVERLAPPING — e.g. a method and the `impl`
/// that contains it. Genuinely one region; the refusal is permanent.
OverlappingExtents,
/// **Same chunk, extents known and DISJOINT.** Two separate items that
/// merely fell inside one ≤120-line chunk. The vector evidence is still
/// vacuous — so this is still a refusal, and judging the pair on a cosine of
/// 1.0 would MANUFACTURE a finding rather than reveal one — but unlike the
/// other two this is a **stale-chunking** condition with a fix that exists:
/// re-index. `vector::spans::leaf_spans` gives every method its own span, and
/// on nornir's own `src/` that took the shared-chunk population from
/// **3 063 of 5 323 functions (57.5 %) to 0 (0.0 %)** — MEASURED 2026-08-25.
/// The pair whose vectors are vacuous is also exactly the pair
/// [`crate::mimir_subclone`] can judge on token evidence instead.
StaleChunking,
}
impl ChunkShareVerdict {
/// Is the pair's cosine an artefact of the chunking? True for every variant
/// except [`Self::NotShared`] — the behaviour
/// [`shares_one_chunk_vector`] has always had, unchanged.
pub fn is_artefact(self) -> bool {
!matches!(self, ChunkShareVerdict::NotShared)
}
/// Short label for evidence notes and persisted rows.
pub fn as_str(self) -> &'static str {
match self {
ChunkShareVerdict::NotShared => "not_shared",
ChunkShareVerdict::UnknownExtent => "unknown_extent",
ChunkShareVerdict::OverlappingExtents => "overlapping_extents",
ChunkShareVerdict::StaleChunking => "stale_chunking",
}
}
}
/// Classify why (or whether) `a` and `b` share one embedding chunk's vector.
///
/// [`shares_one_chunk_vector`] is this, narrowed to one bit, and stays the
/// gate. This is the finer answer the extent makes possible.
pub fn chunk_share_verdict(a: &SymbolVec, b: &SymbolVec) -> ChunkShareVerdict {
if a.chunk_hash.is_empty() || a.chunk_hash != b.chunk_hash {
return ChunkShareVerdict::NotShared;
}
match (a.extent(), b.extent()) {
(Some((s1, e1)), Some((s2, e2))) => {
if e1 < s2 || e2 < s1 {
ChunkShareVerdict::StaleChunking
} else {
ChunkShareVerdict::OverlappingExtents
}
}
_ => ChunkShareVerdict::UnknownExtent,
}
}
/// **How much of the warehouse's symbol population actually HAS a vector** — the
/// anti-silent-empty record for both embedding lenses.
///
/// [`assemble_symbol_vecs`] DROPS every symbol with no covering embedding chunk,
/// because a cosine gate is meaningless without a vector. That drop was silent,
/// and it is not a small one: `deepscan` writes `symbol_facts`/`call_edges` under
/// `repo = "deps"` and `coderoom` under `"<crate>@<version>"`, and NEITHER
/// invokes an embedder (stinky mimir-1). So the entire dependency closure and the
/// crates.io world are present as symbols and absent as vectors, and a finding of
/// the form "N local re-implementations of ONE library function" is structurally
/// impossible — not rare, impossible. A lens that cannot express that must SAY
/// so, which is what [`dark_repos`](Self::dark_repos) is for.
#[derive(Debug, Clone, Default, Serialize)]
pub struct VectorCoverage {
/// Symbols read out of `symbol_facts` across every repo.
pub symbols_total: usize,
/// Of those, the ones a covering embedding chunk gave a vector to. The rest
/// were dropped and can never appear in any finding.
pub symbols_vectored: usize,
/// Repos that contributed symbols.
pub repos_total: usize,
/// Repos that contributed symbols and ZERO vectors — the DARK population.
/// Sorted; capped for the note, with the count kept whole.
pub dark_repos: Vec<String>,
}
impl VectorCoverage {
/// One sentence stating the limit in numbers, for the lens `evidence_note`.
/// Never omitted when the population is dark, never a percentage without its
/// denominator.
pub fn note(&self) -> String {
if self.symbols_total == 0 {
return "Vector coverage: 0 symbol(s) read — the symbol_facts read was EMPTY, \
so no finding of any kind is possible."
.to_string();
}
let pct = 100.0 * self.symbols_vectored as f64 / self.symbols_total as f64;
let mut s = format!(
"Vector coverage: {}/{} symbol(s) ({pct:.1}%) across {} repo(s) carry an embedding \
vector; the rest are DROPPED before any gate and cannot appear in a finding.",
self.symbols_vectored, self.symbols_total, self.repos_total,
);
if !self.dark_repos.is_empty() {
let shown: Vec<&str> = self
.dark_repos
.iter()
.take(8)
.map(String::as_str)
.collect();
s.push_str(&format!(
" {} repo(s) are entirely DARK (symbols, zero vectors): {}{}. \
`deps`/`<crate>@<version>` namespaces are dark BY CONSTRUCTION — deepscan and \
coderoom write symbols and never embed (stinky mimir-1) — so \
\"local re-implementation of a LIBRARY function\" is outside what this \
reading can express.",
self.dark_repos.len(),
shown.join(", "),
if self.dark_repos.len() > shown.len() {
", …"
} else {
""
},
));
}
s
}
}
/// **The two symbols carry the SAME vector because they landed in the same
/// embedding chunk** — so their cosine is 1.0 by construction and says nothing.
///
/// The ONE predicate both embedding lenses route through (LAW 5): SimilarCode's
/// [`analyze_duplicates`] and the Type-4 detector in
/// [`crate::mimir_clones`]. An empty [`chunk_hash`](SymbolVec::chunk_hash) means
/// "no manifest provenance" and never matches, not even another empty one.
pub fn shares_one_chunk_vector(a: &SymbolVec, b: &SymbolVec) -> bool {
!a.chunk_hash.is_empty() && a.chunk_hash == b.chunk_hash
}
/// Detection thresholds. Defaults are deliberately strict — a duplicate report is
/// a call to delete code, so precision beats recall.
#[derive(Debug, Clone, Serialize)]
pub struct DupThresholds {
/// Minimum vector cosine similarity for a pair to be "semantically the same".
pub cosine: f32,
/// Minimum structural agreement (signature + callee-set) for "literally the same".
pub structural: f32,
/// Only consider pairs whose crates differ (the copied-not-moved case). When
/// `false`, same-crate near-duplicates are reported too.
pub cross_scope_only: bool,
/// Suppress clusters whose EVERY member is a [`TrivialShape`] (trait-impl
/// method / constructor / zero-arg accessor). Default `true`; the CLI's
/// `--keep-trait-impls` sets it `false`. Suppressed clusters are never
/// dropped silently — they are counted and listed in
/// [`DuplicateReport::suppressed_trivial`].
pub suppress_trivial_families: bool,
}
impl Default for DupThresholds {
fn default() -> Self {
DupThresholds {
cosine: 0.92,
structural: 0.5,
cross_scope_only: true,
suppress_trivial_families: true,
}
}
}
/// What to do with a cluster member.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[serde(rename_all = "lowercase")]
pub enum Disposition {
/// The canonical copy — the one to keep.
Keep,
/// A redundant copy to delete outright (no shared home to point at).
Kill,
/// A redundant copy to delete and re-point at the canonical shared home.
Repoint,
}
/// One member of a duplicate cluster with its verdict.
#[derive(Debug, Clone, Serialize)]
pub struct ClusterMember {
pub id: String,
pub repo: String,
pub crate_name: String,
pub module_path: String,
pub item_name: String,
pub file: String,
pub line: u32,
pub disposition: Disposition,
/// Mean cosine similarity of this member to the other cluster members — the
/// "most central" copy is the natural canonical pick.
pub centrality: f32,
/// The correct-by-construction shape of this member, if any — so a reader of
/// a `--keep-trait-impls` run can still tell a trait method from a copy.
#[serde(skip_serializing_if = "Option::is_none")]
pub trivial_shape: Option<TrivialShape>,
}
/// A cluster the trivial-family filter held back, reported in full enough to
/// audit: which shape, how big, and every member's id. Never a silent drop.
#[derive(Debug, Clone, Serialize)]
pub struct SuppressedCluster {
/// `id` of the member the detector would have called canonical.
pub canonical: String,
/// The shape EVERY member had. When members mix shapes (a `new` beside a
/// trait method) this is the canonical member's.
pub shape: TrivialShape,
pub size: usize,
pub avg_cosine: f32,
pub structural: f32,
pub member_ids: Vec<String>,
}
/// A cluster of copied-not-moved symbols.
#[derive(Debug, Clone, Serialize)]
pub struct DuplicateCluster {
pub members: Vec<ClusterMember>,
/// Lowest pairwise cosine among surviving edges in the cluster.
pub min_cosine: f32,
/// Mean pairwise cosine among surviving edges.
pub avg_cosine: f32,
/// Mean structural agreement among surviving edges.
pub structural: f32,
/// Rank key: similarity × size (`avg_cosine * member_count`).
pub score: f32,
/// `id` of the canonical (keep) member.
pub canonical: String,
/// Human-readable keep/kill recommendation.
pub recommendation: String,
/// Which index found the cluster's pairs (`graph` / `embedding` / `both`)
/// — set by the graph-first lens, absent on the v1 vector-only path.
#[serde(skip_serializing_if = "Option::is_none")]
pub source: Option<&'static str>,
/// Mean graph score (rarity-weighted structural Jaccard) over the pairs
/// the graph index found, when it found any.
#[serde(skip_serializing_if = "Option::is_none")]
pub graph_score: Option<f32>,
}
/// The whole analysis result — serialises straight to `state_json`.
#[derive(Debug, Clone, Serialize)]
pub struct DuplicateReport {
pub cluster_count: usize,
/// Number of surviving duplicate pairs (edges) across all clusters.
pub pair_count: usize,
/// Candidate pairs REFUSED because both symbols carry the same embedding
/// chunk's vector ([`shares_one_chunk_vector`]) — a cosine of 1.0 that is a
/// fact about chunking, not about the code. Counted, never silent.
pub same_chunk_pairs: usize,
/// How much of the symbol population had a vector at all. Default (all
/// zeroes) on the pure in-memory entry point, which has no warehouse to
/// measure; the warehouse entry point always fills it.
#[serde(default)]
pub coverage: VectorCoverage,
pub thresholds: DupThresholds,
pub clusters: Vec<DuplicateCluster>,
/// Clusters withheld by the trivial-family filter
/// (`thresholds.suppress_trivial_families`), each named. Empty when the
/// filter is off or nothing matched. `cluster_count` counts SURVIVORS only;
/// `suppressed_trivial.len()` is the other half of the population.
#[serde(default)]
pub suppressed_trivial: Vec<SuppressedCluster>,
}
impl DuplicateReport {
/// Compact summary for robot `state_json` assertions: counts, thresholds, and
/// the top clusters (canonical + size + score).
pub fn state_json(&self) -> serde_json::Value {
let top: Vec<serde_json::Value> = self
.clusters
.iter()
.take(10)
.map(|c| {
serde_json::json!({
"canonical": c.canonical,
"size": c.members.len(),
"avg_cosine": c.avg_cosine,
"structural": c.structural,
"score": c.score,
})
})
.collect();
serde_json::json!({
"cluster_count": self.cluster_count,
"pair_count": self.pair_count,
"same_chunk_pairs": self.same_chunk_pairs,
"suppressed_trivial_clusters": self.suppressed_trivial.len(),
"suppressed_trivial_note": self.suppression_note(),
"vector_coverage": self.coverage.note(),
"thresholds": {
"cosine": self.thresholds.cosine,
"structural": self.thresholds.structural,
"cross_scope_only": self.thresholds.cross_scope_only,
"suppress_trivial_families": self.thresholds.suppress_trivial_families,
},
"top_clusters": top,
})
}
/// One sentence a reader cannot miss: how many clusters the trivial-family
/// filter withheld, by shape, and the flag that shows them.
pub fn suppression_note(&self) -> String {
if !self.thresholds.suppress_trivial_families {
return "trivial-family filter OFF (--keep-trait-impls): trait-impl / constructor / \
accessor clusters are listed and labelled, not suppressed"
.to_string();
}
if self.suppressed_trivial.is_empty() {
return "0 clusters suppressed as trait-impl / constructor / accessor families".to_string();
}
let mut by_shape: BTreeMap<&'static str, usize> = BTreeMap::new();
for s in &self.suppressed_trivial {
*by_shape.entry(s.shape.as_str()).or_default() += 1;
}
let parts: Vec<String> = by_shape.iter().map(|(k, v)| format!("{v} {k}")).collect();
format!(
"{} cluster(s) SUPPRESSED as correct-by-construction families ({}); structural \
agreement there is what a trait/constructor/accessor guarantees, not evidence of a \
copy. Pass --keep-trait-impls to list them.",
self.suppressed_trivial.len(),
parts.join(", ")
)
}
}
/// Cosine similarity of two vectors. Returns `0.0` for a length mismatch or a
/// zero-norm vector (never NaN), so callers can threshold safely.
pub fn cosine(a: &[f32], b: &[f32]) -> f32 {
if a.len() != b.len() || a.is_empty() {
return 0.0;
}
let mut dot = 0.0f32;
let mut na = 0.0f32;
let mut nb = 0.0f32;
for i in 0..a.len() {
dot += a[i] * b[i];
na += a[i] * a[i];
nb += b[i] * b[i];
}
if na <= 0.0 || nb <= 0.0 {
return 0.0;
}
dot / (na.sqrt() * nb.sqrt())
}
/// Jaccard overlap of two string sets (`|A∩B| / |A∪B|`). Two empty sets carry no
/// structural signal, so they score `0.0` rather than a vacuous `1.0`.
fn jaccard(a: &BTreeSet<String>, b: &BTreeSet<String>) -> f32 {
if a.is_empty() && b.is_empty() {
return 0.0;
}
let inter = a.intersection(b).count() as f32;
let union = a.union(b).count() as f32;
if union <= 0.0 { 0.0 } else { inter / union }
}
/// Whitespace-token Jaccard of two signatures, after collapsing runs of
/// whitespace. Identical signatures score `1.0`; unrelated ones near `0.0`.
fn signature_similarity(a: &str, b: &str) -> f32 {
let toks =
|s: &str| -> BTreeSet<String> { s.split_whitespace().map(|t| t.to_string()).collect() };
jaccard(&toks(a), &toks(b))
}
/// Structural agreement of two symbols in `0.0..=1.0`: how *literally* alike they
/// are, independent of the embedding. When both carry a signature it weighs
/// signature (0.6) over the callee-set overlap (0.4); when a signature is missing
/// it falls back to the callee overlap alone. This is the "literally the same"
/// half of the AND that rejects semantic-only look-alikes.
pub fn structural_agreement(a: &SymbolVec, b: &SymbolVec) -> f32 {
let callee = jaccard(&a.callees, &b.callees);
match (a.signature.as_deref(), b.signature.as_deref()) {
(Some(sa), Some(sb)) => {
let sig = signature_similarity(sa, sb);
// If neither symbol calls anything, the callee overlap is a non-signal
// (jaccard of two empty sets = 0) — lean fully on the signature so a
// pair of identical leaf fns isn't punished for having no callees.
if a.callees.is_empty() && b.callees.is_empty() {
sig
} else {
0.6 * sig + 0.4 * callee
}
}
_ => callee,
}
}
/// Disjoint-set forest for clustering surviving duplicate edges.
pub(crate) struct UnionFind {
parent: Vec<usize>,
rank: Vec<u8>,
}
impl UnionFind {
pub(crate) fn new(n: usize) -> Self {
UnionFind {
parent: (0..n).collect(),
rank: vec![0; n],
}
}
pub(crate) fn find(&mut self, x: usize) -> usize {
let mut root = x;
while self.parent[root] != root {
root = self.parent[root];
}
// Path compression.
let mut cur = x;
while self.parent[cur] != root {
let next = self.parent[cur];
self.parent[cur] = root;
cur = next;
}
root
}
pub(crate) fn union(&mut self, a: usize, b: usize) {
let (ra, rb) = (self.find(a), self.find(b));
if ra == rb {
return;
}
if self.rank[ra] < self.rank[rb] {
self.parent[ra] = rb;
} else if self.rank[ra] > self.rank[rb] {
self.parent[rb] = ra;
} else {
self.parent[rb] = ra;
self.rank[ra] += 1;
}
}
}
/// Every symbol pair `(i, j)`, `i < j`, whose embedding cosine is ≥ `threshold`,
/// as indices into `symbols` — the candidate set the expensive structural
/// predicates then run over.
///
/// Fast path: when every symbol carries a non-empty vector of the SAME
/// dimensionality (one embedding space, one dim), the whole set is
/// computed by [`VectorIndex::pairs_above`]: SIMD dot products over
/// pre-normalized rows, fanned out on gatling.
///
/// Fallback: a ragged or empty-vector input (hand-built fixtures, a partially
/// embedded corpus), or a build without the `vector` feature, can't go through a
/// fixed-dim index, so it walks the naive pairs with [`cosine`], which is defined
/// to return `0.0` for mismatched or empty operands. Both paths produce the SAME
/// pairs in the SAME (ascending `(i, j)`) order — `analyze_duplicates` cannot
/// tell them apart, which is what keeps its existing unit tests meaningful and is
/// asserted directly by `both_candidate_paths_agree`.
#[cfg(feature = "vector")]
pub(crate) fn candidate_pairs(symbols: &[SymbolVec], threshold: f32) -> Vec<(usize, usize, f32)> {
// a workspace-sized set at a lens bar: the process's pair index (exact,
// over the distinct vectors, brought forward by what changed)
if let Some((pairs, _)) = crate::vector::pair_index::pairs_above(symbols.iter().map(|s| s.vector.as_slice()), threshold) {
return pairs;
}
let n = symbols.len();
let dim = symbols.first().map(|s| s.vector.len()).unwrap_or(0);
if dim == 0 || !symbols.iter().all(|s| s.vector.len() == dim) {
return naive_candidate_pairs(symbols, threshold);
}
let Ok(mut idx) = crate::vector::VectorIndex::new(dim) else {
return naive_candidate_pairs(symbols, threshold);
};
let mut flat = Vec::with_capacity(n * dim);
for s in symbols {
flat.extend_from_slice(&s.vector);
}
// Row index doubles as the id, so the returned ids ARE indices into
// `symbols` — no id→index map needed.
let ids: Vec<u64> = (0..n as u64).collect();
if idx.add(&flat, &ids).is_err() {
return naive_candidate_pairs(symbols, threshold);
}
idx.pairs_above(threshold)
.into_iter()
.map(|(a, b, cos)| (a as usize, b as usize, cos))
.collect()
}
/// Without the `vector` feature there is no index to route through; the naive
/// scan IS the implementation.
#[cfg(not(feature = "vector"))]
pub(crate) fn candidate_pairs(symbols: &[SymbolVec], threshold: f32) -> Vec<(usize, usize, f32)> {
naive_candidate_pairs(symbols, threshold)
}
/// The reference O(n²) candidate scan — the pre-index behaviour, kept as the
/// fallback for ragged input and as the oracle the fast path is tested against.
fn naive_candidate_pairs(symbols: &[SymbolVec], threshold: f32) -> Vec<(usize, usize, f32)> {
let n = symbols.len();
let mut out = Vec::new();
for i in 0..n {
for j in (i + 1)..n {
let cos = cosine(&symbols[i].vector, &symbols[j].vector);
if cos >= threshold {
out.push((i, j, cos));
}
}
}
out
}
/// One surviving duplicate edge (indices into the input slice). `pub(crate)`:
/// the incremental `similar_code` fold carries edges forward and rebuilds the
/// report from them through [`duplicates_from_edges`].
pub(crate) struct Edge {
pub(crate) i: usize,
pub(crate) j: usize,
/// The pair's cosine — `NaN` when the pair has none (a graph pair of
/// functions without vectors).
pub(crate) cos: f32,
pub(crate) structural: f32,
/// The graph index's score for the pair, `NaN` when the graph did not
/// propose it.
pub(crate) graph: f32,
/// The embedding index proposed the pair (cosine at or above the bar).
pub(crate) emb: bool,
}
impl Edge {
/// An edge the embedding index proposed (the v1 path's only kind).
pub(crate) fn embedding(i: usize, j: usize, cos: f32, structural: f32) -> Self {
Edge { i, j, cos, structural, graph: f32::NAN, emb: true }
}
/// The rank weight: the cosine when there is one, else the graph score.
fn weight(&self) -> f32 {
if self.cos.is_finite() { self.cos } else { self.graph }
}
}
/// `graph` / `embedding` / `both`: which index found a set of edges.
pub(crate) fn source_of<'a>(edges: impl Iterator<Item = &'a Edge>) -> &'static str {
let (mut g, mut e) = (false, false);
for x in edges {
g |= x.graph.is_finite();
e |= x.emb;
}
match (g, e) {
(true, false) => "graph",
(false, true) => "embedding",
_ => "both",
}
}
/// **The pairwise gate** — phase 2 of [`analyze_duplicates`], shared with the
/// incremental fold so a re-joined pair is judged by EXACTLY the predicates
/// the full path runs: the same-lines refusal first (counted, returned as
/// pairs so the incremental fold can carry them), the cross-crate gate, then
/// the structural floor.
pub(crate) fn gate_pairs(symbols: &[SymbolVec], pairs: &[(usize, usize, f32)], t: &DupThresholds) -> (Vec<Edge>, Vec<(usize, usize)>) {
let mut edges: Vec<Edge> = Vec::new();
let mut same_chunk: Vec<(usize, usize)> = Vec::new();
for &(i, j, cos) in pairs {
// Two symbols that share ONE embedding chunk were handed the SAME vector
// by `best_vector` — cosine 1.0 by construction. Refuse before any other
// predicate, so the count is the honest size of the contamination.
if shares_one_chunk_vector(&symbols[i], &symbols[j]) {
same_chunk.push((i, j));
continue;
}
if t.cross_scope_only && symbols[i].crate_name == symbols[j].crate_name {
continue;
}
let structural = structural_agreement(&symbols[i], &symbols[j]);
if structural < t.structural {
continue;
}
edges.push(Edge::embedding(i, j, cos, structural));
}
(edges, same_chunk)
}
/// Run the copied-not-moved analysis: every cross-scope symbol pair whose vector
/// cosine AND structural agreement clear the thresholds becomes a duplicate edge;
/// edges are unioned into clusters, ranked by similarity × size, and each cluster
/// gets a keep/kill recommendation. `canonical_crates` names the shared reuse
/// homes (e.g. `edda`, `skidbladnir`) — a copy living in one of them is preferred
/// as the canonical keep, and the others are marked `Repoint` at it.
pub fn analyze_duplicates(
symbols: &[SymbolVec],
t: &DupThresholds,
canonical_crates: &BTreeSet<String>,
) -> DuplicateReport {
let n = symbols.len();
// Phase 1 — CANDIDATE GENERATION through the vector index.
//
// This used to be a serial `i × j` loop calling `cosine()`, which recomputes
// BOTH operand norms on every one of the n²/2 pairs. On the real warehouse
// (~79k symbols × 768 dims) that is ~7·10¹² scalar flops on one core, and the
// verb simply never finished — 15 min of CPU, SIGTERM, zero output.
//
// `candidate_pairs` hands the same n²/2 comparisons to `VectorIndex`: rows are
// L2-normalized ONCE at insert, so a cosine is a single SIMD dot product
// instead of a dot plus two norms, and the scan runs over gatling fork-join
// bands instead of one core.
//
// It stays **exact** — no ANN prefilter. An HNSW top-k prefilter would be the
// obvious next step, but this report's consumer deletes code: a silently
// dropped pair is a far worse outcome than a slower scan, and the HNSW build
// alone (single-threaded, ~2.5 min at this size) would cost more than the
// exact scan it replaces. The index earns its place here through its kernel
// and its fan-out, not through approximation.
// Announced on ENTRY, not on completion: this scan is the phase that used to
// consume the whole runtime in silence (stinky mimir-11).
let ph = progress::Phase::start(
"candidate pairs",
format_args!(
"{n} row(s), ~{} comparison(s) at cosine >= {:.2}",
(n as u64).saturating_mul(n.saturating_sub(1) as u64) / 2,
t.cosine,
),
);
let pairs = candidate_pairs(symbols, t.cosine);
ph.done(format_args!("{} candidate pair(s)", pairs.len()));
// Phase 2 — the expensive per-pair predicates run ONLY on survivors. The
// cosine threshold is strict, so this is a tiny fraction of n²/2.
let ph = progress::Phase::start(
"structural gate",
format_args!("structural >= {:.2}", t.structural),
);
let (edges, same_chunk) = gate_pairs(symbols, &pairs, t);
ph.done(format_args!("{} surviving duplicate pair(s)", edges.len()));
duplicates_from_edges(symbols, edges, same_chunk.len(), t, canonical_crates)
}
/// **Cluster and report** — the tail of [`analyze_duplicates`] from the gated
/// edges on: union-find, ranking, the trivial-family filter. Shared with the
/// incremental `similar_code` fold, which hands it carried edges plus the
/// re-joined ones, in the full path's ascending `(i, j)` order — so the two
/// paths produce the identical report from identical edges.
pub(crate) fn duplicates_from_edges(
symbols: &[SymbolVec],
edges: Vec<Edge>,
same_chunk_pairs: usize,
t: &DupThresholds,
canonical_crates: &BTreeSet<String>,
) -> DuplicateReport {
let n = symbols.len();
let pair_count = edges.len();
let ph = progress::Phase::start("clustering", "union-find over surviving pairs");
let mut uf = UnionFind::new(n);
for e in &edges {
uf.union(e.i, e.j);
}
// Group member indices + intra-cluster edges by cluster root.
let mut members_by_root: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for e in &edges {
// Ensure both endpoints are registered (roots are stable post-union).
for idx in [e.i, e.j] {
let root = uf.find(idx);
let list = members_by_root.entry(root).or_default();
if !list.contains(&idx) {
list.push(idx);
}
}
}
let mut edges_by_root: BTreeMap<usize, Vec<&Edge>> = BTreeMap::new();
for e in &edges {
edges_by_root.entry(uf.find(e.i)).or_default().push(e);
}
ph.done(format_args!("{} group(s)", members_by_root.len()));
let mut clusters: Vec<DuplicateCluster> = Vec::new();
for (root, mut idxs) in members_by_root {
idxs.sort();
let cluster_edges = edges_by_root.remove(&root).unwrap_or_default();
// the cosine stats are over the edges that HAVE a cosine (a graph pair
// of functions without vectors has none)
let min_cosine = cluster_edges
.iter()
.map(|e| e.cos)
.filter(|c| c.is_finite())
.fold(f32::INFINITY, f32::min);
let avg_cosine = mean(cluster_edges.iter().map(|e| e.cos).filter(|c| c.is_finite()));
let structural = mean(cluster_edges.iter().map(|e| e.structural));
let graph_scores: Vec<f32> = cluster_edges.iter().map(|e| e.graph).filter(|g| g.is_finite()).collect();
let source = source_of(cluster_edges.iter().copied());
// Centrality = mean cosine of a member to every OTHER cluster member
// (full pairwise within the component, not just surviving edges); a
// member without a vector is placed by its structural agreement.
let centralities: Vec<f32> = idxs
.iter()
.map(|&a| {
let vals: Vec<f32> = idxs
.iter()
.filter(|&&b| b != a)
.map(|&b| {
if symbols[a].vector.is_empty() || symbols[b].vector.is_empty() {
structural_agreement(&symbols[a], &symbols[b])
} else {
cosine(&symbols[a].vector, &symbols[b].vector)
}
})
.collect();
mean(vals.into_iter())
})
.collect();
// Canonical pick: prefer a member in a shared reuse home; among those (or,
// failing any, all members) the most central; ties broken by lexicographic
// id for determinism.
let canon_pos = pick_canonical(symbols, &idxs, ¢ralities, canonical_crates);
let canonical_idx = idxs[canon_pos];
let canonical_in_home = canonical_crates.contains(&symbols[canonical_idx].crate_name);
let members: Vec<ClusterMember> = idxs
.iter()
.enumerate()
.map(|(k, &a)| {
let disposition = if a == canonical_idx {
Disposition::Keep
} else if canonical_in_home {
Disposition::Repoint
} else {
Disposition::Kill
};
ClusterMember {
id: symbols[a].id.clone(),
repo: symbols[a].repo.clone(),
crate_name: symbols[a].crate_name.clone(),
module_path: symbols[a].module_path.clone(),
item_name: symbols[a].item_name.clone(),
file: symbols[a].file.clone(),
line: symbols[a].line,
disposition,
centrality: centralities[k],
trivial_shape: trivial_shape(&symbols[a]),
}
})
.collect();
let score = mean(cluster_edges.iter().map(|e| e.weight())) * members.len() as f32;
let canonical = symbols[canonical_idx].id.clone();
let recommendation = recommend(symbols, canonical_idx, &idxs, canonical_in_home);
clusters.push(DuplicateCluster {
members,
min_cosine: if min_cosine.is_finite() {
min_cosine
} else {
0.0
},
avg_cosine,
structural,
score,
canonical,
recommendation,
source: Some(source),
graph_score: (!graph_scores.is_empty()).then(|| mean(graph_scores.iter().copied())),
});
}
// Rank by similarity × size desc, then size desc, then canonical id for a
// stable order.
clusters.sort_by(|a, b| {
b.score
.partial_cmp(&a.score)
.unwrap_or(std::cmp::Ordering::Equal)
.then(b.members.len().cmp(&a.members.len()))
.then(a.canonical.cmp(&b.canonical))
});
// THE TRAIT-IMPL FILTER. A cluster whose every member is correct-by-
// construction (trait method / constructor / accessor) is withheld — and
// NAMED in `suppressed_trivial`, never dropped. Runs after ranking so the
// suppressed list carries the same order the reader would have seen.
// A cluster with even ONE ordinary member survives whole: that member's
// agreement with the rest is still a finding.
let mut suppressed_trivial: Vec<SuppressedCluster> = Vec::new();
if t.suppress_trivial_families {
let ph = progress::Phase::start(
"trivial-family filter",
format_args!("{} ranked cluster(s)", clusters.len()),
);
let (trivial, kept): (Vec<DuplicateCluster>, Vec<DuplicateCluster>) = clusters
.into_iter()
.partition(|c| c.members.iter().all(|m| m.trivial_shape.is_some()));
clusters = kept;
suppressed_trivial.reserve_exact(trivial.len());
for c in trivial {
let shape = c
.members
.iter()
.find(|m| m.id == c.canonical)
.and_then(|m| m.trivial_shape)
.or_else(|| c.members.first().and_then(|m| m.trivial_shape))
.expect("every member of a suppressed cluster has a shape");
suppressed_trivial.push(SuppressedCluster {
canonical: c.canonical,
shape,
size: c.members.len(),
avg_cosine: c.avg_cosine,
structural: c.structural,
member_ids: c.members.into_iter().map(|m| m.id).collect(),
});
}
ph.done(format_args!(
"{} suppressed, {} kept",
suppressed_trivial.len(),
clusters.len()
));
}
DuplicateReport {
cluster_count: clusters.len(),
pair_count,
same_chunk_pairs,
coverage: VectorCoverage::default(),
thresholds: t.clone(),
clusters,
suppressed_trivial,
}
}
/// Mean of an iterator of `f32`, or `0.0` when empty.
pub(crate) fn mean(it: impl Iterator<Item = f32>) -> f32 {
let mut sum = 0.0f32;
let mut n = 0u32;
for v in it {
sum += v;
n += 1;
}
if n == 0 { 0.0 } else { sum / n as f32 }
}
/// Choose the canonical member's position within `idxs`. Prefers a member whose
/// crate is a shared reuse home; among the eligible set picks the most central,
/// tie-broken by lexicographic id. `pub(crate)`: the SemanticClones lens reuses
/// this exact disposition so the two lenses cannot disagree on the keep-pick.
pub(crate) fn pick_canonical(
symbols: &[SymbolVec],
idxs: &[usize],
centralities: &[f32],
canonical_crates: &BTreeSet<String>,
) -> usize {
let in_home: Vec<usize> = (0..idxs.len())
.filter(|&k| canonical_crates.contains(&symbols[idxs[k]].crate_name))
.collect();
let pool: Vec<usize> = if in_home.is_empty() {
(0..idxs.len()).collect()
} else {
in_home
};
*pool
.iter()
.max_by(|&&a, &&b| {
centralities[a]
.partial_cmp(¢ralities[b])
.unwrap_or(std::cmp::Ordering::Equal)
.then(symbols[idxs[b]].id.cmp(&symbols[idxs[a]].id))
})
.expect("cluster is non-empty")
}
/// Build the human-readable keep/kill line for a cluster.
fn recommend(
symbols: &[SymbolVec],
canonical_idx: usize,
idxs: &[usize],
canonical_in_home: bool,
) -> String {
let others: Vec<String> = idxs
.iter()
.filter(|&&a| a != canonical_idx)
.map(|&a| format!("{} ({})", symbols[a].id, symbols[a].crate_name))
.collect();
let verb = if canonical_in_home {
"re-point at"
} else {
"delete in favour of"
};
format!(
"keep {} ({}); {} it: {}",
symbols[canonical_idx].id,
symbols[canonical_idx].crate_name,
verb,
others.join(", ")
)
}
#[cfg(test)]
mod tests {
use super::*;
fn bset(items: &[&str]) -> BTreeSet<String> {
items.iter().map(|s| s.to_string()).collect()
}
fn sym(id: &str, krate: &str, vec: Vec<f32>, sig: &str, callees: &[&str]) -> SymbolVec {
SymbolVec {
id: id.to_string(),
repo: krate.to_string(),
crate_name: krate.to_string(),
module_path: "m".to_string(),
item_kind: "fn".to_string(),
item_name: id.to_string(),
file: "src/lib.rs".to_string(),
line: 1,
signature: Some(sig.to_string()),
callees: bset(callees),
item_end_line: 0,
span_lines: 0,
chunk_hash: String::new(),
impl_header: None,
vector: vec,
}
}
/// Deterministic pseudo-random unit-ish vector for the candidate-scan tests.
fn tvec(seed: u64, dim: usize) -> Vec<f32> {
let mut s = seed
.wrapping_mul(0x9E37_79B9_7F4A_7C15)
.wrapping_add(0x1234_5678);
(0..dim)
.map(|_| {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
((s >> 11) as f64 / (1u64 << 53) as f64 * 2.0 - 1.0) as f32
})
.collect()
}
/// The indexed candidate scan must be a drop-in for the naive `i × j` loop it
/// replaced: identical pairs, identical order, identical cosines. This is what
/// makes the speedup a pure implementation change rather than a change of
/// answer — the guard against "fast but different".
#[test]
fn both_candidate_paths_agree() {
let dim = 64usize;
// A mix of clustered near-duplicates (so pairs actually clear the bar) and
// unrelated vectors.
let syms: Vec<SymbolVec> = (0..300u64)
.map(|i| {
let base = tvec(i % 30, dim); // 30 groups of 10 near-identical rows
let jitter = tvec(1_000 + i, dim);
let v: Vec<f32> = base
.iter()
.zip(&jitter)
.map(|(b, j)| b + 0.05 * j)
.collect();
sym(
&format!("s{i}"),
&format!("crate_{}", i % 7),
v,
"fn f()",
&["g"],
)
})
.collect();
for &thr in &[0.95f32, 0.80, 0.0] {
let fast = candidate_pairs(&syms, thr);
let naive = naive_candidate_pairs(&syms, thr);
let fp: Vec<(usize, usize)> = fast.iter().map(|&(i, j, _)| (i, j)).collect();
let np: Vec<(usize, usize)> = naive.iter().map(|&(i, j, _)| (i, j)).collect();
assert_eq!(
fp, np,
"candidate pair set/order differs at threshold {thr}"
);
for (f, n) in fast.iter().zip(&naive) {
assert!(
(f.2 - n.2).abs() < 1e-5,
"cosine differs for {:?}: indexed {} vs naive {}",
(f.0, f.1),
f.2,
n.2
);
}
assert!(
!fast.is_empty(),
"threshold {thr} selected nothing — vacuous test"
);
}
}
/// Ragged / empty vectors must not panic or silently drop symbols — they take
/// the naive fallback (a fixed-dim index cannot hold them).
#[test]
fn candidate_scan_tolerates_ragged_vectors() {
let syms = [
sym("a", "c1", vec![1.0, 0.0, 0.0], "fn f()", &["g"]),
sym("b", "c2", vec![1.0, 0.0], "fn f()", &["g"]), // shorter
sym("c", "c3", vec![], "fn f()", &["g"]), // empty
];
assert_eq!(
candidate_pairs(&syms, 0.9),
naive_candidate_pairs(&syms, 0.9)
);
// …and the whole verb still runs to a (green) report.
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(rep.cluster_count, 0);
}
/// SCALE GUARD — `analyze_duplicates` used to be a serial `i × j` loop with a
/// scalar 768-dim cosine, and on the real warehouse (~79k symbols) it never
/// returned: 15 min of CPU, SIGTERM, zero output. This runs the real
/// production shape (768 dims) at a size the old loop could not have finished
/// in the time this test is allowed to take.
///
/// The candidate scan is EXACT O(n²) by design (see `analyze_duplicates` —
/// no ANN prefilter), so what separates the fast path from the regression is
/// pure throughput (SIMD kernel + gatling fan-out), not a sub-quadratic
/// candidate count we could assert deterministically. That makes the pass
/// condition a wall-clock bound, which is only meaningful on an unloaded host
/// — under concurrent build/test load the timer trips spuriously. Gated
/// `#[ignore]` so CI stays deterministic; run it deliberately on a quiet host
/// with `cargo test -p nornir --features vector -- --ignored
/// analyze_duplicates_completes_at_scale`.
#[test]
#[ignore = "perf/throughput guard: exact O(n²) scan; wall-clock bound only valid on a quiet host — run with --ignored"]
fn analyze_duplicates_completes_at_scale() {
let (n, dim) = (4_000usize, 768usize);
let syms: Vec<SymbolVec> = (0..n as u64)
.map(|i| {
sym(
&format!("s{i}"),
&format!("crate_{}", i % 11),
tvec(i, dim),
"fn f()",
&["g"],
)
})
.collect();
let t0 = std::time::Instant::now();
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
let secs = t0.elapsed().as_secs_f64();
assert!(
rep.pair_count < n,
"sanity: unrelated vectors must not all pair up"
);
assert!(
secs < 60.0,
"{n}×{dim} duplicate analysis took {secs:.1}s — the candidate scan is not \
going through the index"
);
}
#[test]
fn cosine_identical_is_one_orthogonal_is_zero() {
assert!((cosine(&[1.0, 2.0, 3.0], &[1.0, 2.0, 3.0]) - 1.0).abs() < 1e-5);
assert!(cosine(&[1.0, 0.0], &[0.0, 1.0]).abs() < 1e-5);
// Degenerate inputs never NaN.
assert_eq!(cosine(&[0.0, 0.0], &[1.0, 1.0]), 0.0);
assert_eq!(cosine(&[1.0], &[1.0, 2.0]), 0.0);
}
#[test]
fn detects_cross_crate_duplicate() {
let syms = [
sym(
"a::f",
"crate_a",
vec![1.0, 0.0, 0.0],
"fn f(x: i32) -> i32",
&["g", "h"],
),
sym(
"b::f",
"crate_b",
vec![1.0, 0.0, 0.0],
"fn f(x: i32) -> i32",
&["g", "h"],
),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(rep.cluster_count, 1, "one cross-crate duplicate cluster");
assert_eq!(rep.pair_count, 1);
assert_eq!(rep.clusters[0].members.len(), 2);
// Exactly one Keep, one non-keep.
let keeps = rep.clusters[0]
.members
.iter()
.filter(|m| m.disposition == Disposition::Keep)
.count();
assert_eq!(keeps, 1);
}
#[test]
fn same_crate_respects_cross_scope_only() {
let syms = [
sym("a::f", "crate_a", vec![1.0, 0.0], "fn f()", &["g"]),
sym("a::g", "crate_a", vec![1.0, 0.0], "fn f()", &["g"]),
];
// Default cross_scope_only = true → same-crate pair ignored.
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(
rep.cluster_count, 0,
"same-crate pair not flagged when cross_scope_only"
);
// Turned off → the pair surfaces.
let mut t = DupThresholds::default();
t.cross_scope_only = false;
let rep2 = analyze_duplicates(&syms, &t, &BTreeSet::new());
assert_eq!(rep2.cluster_count, 1);
}
/// The crux: identical embeddings but disjoint signature AND callees must NOT
/// be flagged — the structural intersection rejects a semantic-only match.
/// Red-when-broken: dropping the `structural` gate makes this a false cluster.
#[test]
fn structural_gate_rejects_semantic_only_match() {
let syms = [
sym(
"a::f",
"crate_a",
vec![1.0, 0.0, 0.0],
"fn parse(s: &str) -> Ast",
&["lex", "build"],
),
sym(
"b::g",
"crate_b",
vec![1.0, 0.0, 0.0],
"fn render(v: View) -> Html",
&["paint", "draw"],
),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(
rep.cluster_count, 0,
"vector-identical but structurally-unrelated is NOT a duplicate"
);
}
#[test]
fn recommendation_prefers_canonical_reuse_home() {
let syms = [
sym(
"nornir::helper",
"nornir",
vec![1.0, 0.0, 0.0],
"fn helper()",
&["a"],
),
sym(
"edda::helper",
"edda",
vec![1.0, 0.0, 0.0],
"fn helper()",
&["a"],
),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &bset(&["edda"]));
assert_eq!(rep.cluster_count, 1);
let c = &rep.clusters[0];
assert_eq!(
c.canonical, "edda::helper",
"the shared reuse home is canonical"
);
// Non-canonical copies are Repoint (a home exists), never Kill.
for m in &c.members {
if m.id != "edda::helper" {
assert_eq!(m.disposition, Disposition::Repoint);
} else {
assert_eq!(m.disposition, Disposition::Keep);
}
}
assert!(c.recommendation.contains("re-point at"));
}
#[test]
fn no_reuse_home_marks_copies_kill() {
let syms = [
sym(
"a::helper",
"crate_a",
vec![1.0, 0.0],
"fn helper()",
&["a"],
),
sym(
"b::helper",
"crate_b",
vec![1.0, 0.0],
"fn helper()",
&["a"],
),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
let c = &rep.clusters[0];
let kills = c
.members
.iter()
.filter(|m| m.disposition == Disposition::Kill)
.count();
assert_eq!(kills, 1, "with no shared home the redundant copy is Kill");
assert!(c.recommendation.contains("delete in favour of"));
}
#[test]
fn three_copies_form_one_transitive_cluster() {
let syms = [
sym("a::f", "crate_a", vec![1.0, 0.0, 0.0], "fn f()", &["g"]),
sym("b::f", "crate_b", vec![1.0, 0.0, 0.0], "fn f()", &["g"]),
sym("c::f", "crate_c", vec![1.0, 0.0, 0.0], "fn f()", &["g"]),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(
rep.cluster_count, 1,
"three mutual copies collapse to one cluster"
);
assert_eq!(rep.clusters[0].members.len(), 3);
assert_eq!(rep.pair_count, 3, "all three pairwise edges survive");
}
#[test]
fn clusters_ranked_by_similarity_times_size() {
// Cluster X: 3 identical copies (score ≈ 1.0 * 3 = 3). Cluster Y: 2
// identical copies (score ≈ 1.0 * 2 = 2). X must rank first.
let syms = [
sym("x1::f", "cx1", vec![1.0, 0.0, 0.0], "fn f()", &["g"]),
sym("x2::f", "cx2", vec![1.0, 0.0, 0.0], "fn f()", &["g"]),
sym("x3::f", "cx3", vec![1.0, 0.0, 0.0], "fn f()", &["g"]),
sym("y1::h", "cy1", vec![0.0, 1.0, 0.0], "fn h()", &["k"]),
sym("y2::h", "cy2", vec![0.0, 1.0, 0.0], "fn h()", &["k"]),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(rep.cluster_count, 2);
assert!(
rep.clusters[0].members.len() == 3 && rep.clusters[1].members.len() == 2,
"the larger, higher-scored cluster ranks first"
);
assert!(rep.clusters[0].score > rep.clusters[1].score);
}
/// **The contamination itself, both directions.** Two symbols attributed to
/// ONE embedding chunk carry ONE vector — cosine 1.0 that is a chunking
/// fact, not a similarity fact — so the detector must refuse the pair and
/// COUNT the refusal.
///
/// NON-VACUITY IS THE POINT OF THE SECOND HALF: the same two vectors from
/// two SEPARATE chunk instances (a byte-identical copy) must STILL cluster.
/// The chunk-instance key is [`SymbolVec::chunk_hash`], not the content hash.
#[test]
fn two_symbols_sharing_one_chunk_are_not_a_duplicate_pair() {
let mut alpha = sym("alpha", "k", vec![1.0, 0.0, 0.0], "fn alpha() -> i32", &[]);
let mut beta = sym("beta", "k", vec![1.0, 0.0, 0.0], "fn beta() -> i32", &[]);
alpha.chunk_hash = "repo_a\u{1}src/lib.rs\u{1}1\u{1}120".to_string();
beta.chunk_hash = alpha.chunk_hash.clone();
assert!(shares_one_chunk_vector(&alpha, &beta));
let mut t = DupThresholds::default();
t.cross_scope_only = false; // the scope filter must not be what saves us
let rep = analyze_duplicates(&[alpha, beta], &t, &BTreeSet::new());
assert_eq!(
rep.cluster_count, 0,
"two items inside ONE embedding chunk are not duplicates of each other"
);
assert_eq!(rep.same_chunk_pairs, 1, "and the refusal must be COUNTED");
let mut a = sym("alpha", "k", vec![1.0, 0.0, 0.0], "fn alpha() -> i32", &[]);
let mut b = sym("alpha", "k2", vec![1.0, 0.0, 0.0], "fn alpha() -> i32", &[]);
a.chunk_hash = "repo_a\u{1}src/lib.rs\u{1}1\u{1}20".to_string();
b.chunk_hash = "repo_a\u{1}src/other.rs\u{1}1\u{1}20".to_string();
b.id = "alpha2".to_string();
assert!(
!shares_one_chunk_vector(&a, &b),
"two DIFFERENT chunks with the same content are a real copy, not an artefact"
);
let rep2 = analyze_duplicates(&[a, b], &DupThresholds::default(), &BTreeSet::new());
assert_eq!(
rep2.cluster_count, 1,
"a genuine byte-identical copy across crates must STILL be reported"
);
assert_eq!(rep2.same_chunk_pairs, 0);
}
#[test]
fn state_json_carries_counts_and_thresholds() {
let syms = [
sym("a::f", "crate_a", vec![1.0, 0.0], "fn f()", &["g"]),
sym("b::f", "crate_b", vec![1.0, 0.0], "fn f()", &["g"]),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
let js = rep.state_json();
assert_eq!(js["cluster_count"], 1);
assert_eq!(js["pair_count"], 1);
assert_eq!(js["thresholds"]["cross_scope_only"], true);
assert_eq!(js["top_clusters"].as_array().unwrap().len(), 1);
assert_eq!(js["suppressed_trivial_clusters"], 0);
assert_eq!(js["thresholds"]["suppress_trivial_families"], true);
}
// ─────────────────────── the trait-impl filter (§5 #2) ─────────────────────
/// The shape rules run over the facts already in the row — nothing else.
/// Each arm is one inventory verdict: `zones` (#4, trait impl), `new` (#2,
/// constructor), `path` (#17, accessor), and the `now_unix_ms` shape (#13,
/// a TRUE twin) must come back `None`.
#[test]
fn trivial_shape_reads_kind_name_signature_and_impl_header() {
let mut zones = sym("zones", "monetize-cloud-impl", vec![1.0, 0.0], "fn zones(self)", &[]);
zones.impl_header = Some("impl Cloud for UpCloud".to_string());
assert_eq!(trivial_shape(&zones), Some(TrivialShape::TraitImpl));
// Inherent impl: no ` for ` in the header, so NOT a trait method — but
// `new` is a constructor whatever block it sits in.
let mut new = sym("new", "korp-collectors", vec![1.0, 0.0], "fn new(u64, u64)", &[]);
new.impl_header = Some("impl HttpRange".to_string());
assert_eq!(trivial_shape(&new), Some(TrivialShape::Constructor));
let mut new_with = sym("new_with_rng", "k", vec![1.0, 0.0], "fn new_with_rng(Rng)", &[]);
new_with.impl_header = Some("impl X".to_string());
assert_eq!(trivial_shape(&new_with), Some(TrivialShape::Constructor));
// `fn path(self)` — a receiver and nothing else.
let path = sym("path", "korp-collectors", vec![1.0, 0.0], "fn path(self)", &[]);
assert_eq!(trivial_shape(&path), Some(TrivialShape::Accessor));
// …but a receiver PLUS an argument is a real method body.
let lookup = sym("header", "draupnir", vec![1.0, 0.0], "fn header(self, &str)", &[]);
assert_eq!(trivial_shape(&lookup), None);
// The true twin: a free fn with an ordinary signature.
let now = sym("now_unix_ms", "gunnar-ui", vec![1.0, 0.0], "fn now_unix_ms()", &[]);
assert_eq!(trivial_shape(&now), None);
// Non-fn rows (the `impl` header row itself, a struct) are never trivial.
let mut imp = sym("impl Cloud for UpCloud", "m", vec![1.0, 0.0], "", &[]);
imp.item_kind = "impl".to_string();
imp.signature = None;
assert_eq!(trivial_shape(&imp), None);
}
/// Inventory §3 #4 in miniature: eight `impl Cloud for X` implementors of
/// `zones`, structural 1.00 by construction. Default: the cluster is
/// WITHHELD and NAMED (count, shape, every member id, the note).
/// `--keep-trait-impls`: it is listed, each member labelled `trait_impl`.
#[test]
fn trait_impl_families_are_suppressed_and_reported_not_dropped() {
let impls = ["FakeCloud", "Sandbox", "Server", "NoCloud", "MockCloud", "Scaleway", "UpCloud", "Hetzner"];
let syms: Vec<SymbolVec> = impls
.iter()
.enumerate()
.map(|(i, ty)| {
let mut s = sym(
&format!("crate_{i}::zones"),
&format!("crate_{i}"),
vec![1.0, 0.0],
"fn zones(self)",
&["collect"],
);
s.item_name = "zones".to_string();
s.impl_header = Some(format!("impl Cloud for {ty}"));
s
})
.collect();
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(rep.cluster_count, 0, "the family is not a finding");
assert_eq!(rep.clusters.len(), 0);
assert_eq!(rep.suppressed_trivial.len(), 1, "…but it is COUNTED");
let s = &rep.suppressed_trivial[0];
assert_eq!(s.shape, TrivialShape::TraitImpl);
assert_eq!(s.size, 8);
assert_eq!(s.member_ids.len(), 8, "every member is named");
assert!(s.member_ids.contains(&"crate_3::zones".to_string()));
assert!((s.structural - 1.0).abs() < 1e-6);
let js = rep.state_json();
assert_eq!(js["suppressed_trivial_clusters"], 1);
let note = rep.suppression_note();
assert!(note.contains("1 cluster(s) SUPPRESSED"), "{note}");
assert!(note.contains("1 trait-impl"), "{note}");
assert!(note.contains("--keep-trait-impls"), "{note}");
// The FULL serialisation carries the list — what `--full` prints.
let full = serde_json::to_value(&rep).unwrap();
assert_eq!(full["suppressed_trivial"].as_array().unwrap().len(), 1);
assert_eq!(full["suppressed_trivial"][0]["shape"], "trait_impl");
// --keep-trait-impls
let t = DupThresholds {
suppress_trivial_families: false,
..DupThresholds::default()
};
let kept = analyze_duplicates(&syms, &t, &BTreeSet::new());
assert_eq!(kept.cluster_count, 1);
assert!(kept.suppressed_trivial.is_empty());
assert_eq!(kept.clusters[0].members.len(), 8);
assert!(
kept.clusters[0]
.members
.iter()
.all(|m| m.trivial_shape == Some(TrivialShape::TraitImpl)),
"every listed member wears its shape"
);
assert!(kept.suppression_note().contains("OFF"));
assert_eq!(kept.state_json()["thresholds"]["suppress_trivial_families"], false);
let full = serde_json::to_value(&kept).unwrap();
assert_eq!(full["clusters"][0]["members"][0]["trivial_shape"], "trait_impl");
}
/// One ordinary member is enough to keep the whole cluster: its agreement
/// with the trait methods is still a finding, so nothing is withheld and
/// the members keep their individual labels (`None` for the ordinary one).
#[test]
fn one_ordinary_member_keeps_the_cluster_whole() {
let mut a = sym("a::zones", "crate_a", vec![1.0, 0.0], "fn zones(self)", &["collect"]);
a.item_name = "zones".to_string();
a.impl_header = Some("impl Cloud for A".to_string());
let mut b = sym("b::zones", "crate_b", vec![1.0, 0.0], "fn zones(self)", &["collect"]);
b.item_name = "zones".to_string();
b.impl_header = Some("impl Cloud for B".to_string());
// A free fn that happens to agree — an actual copy somebody made.
let mut c = sym("c::zones", "crate_c", vec![1.0, 0.0], "fn zones(self)", &["collect"]);
c.item_name = "zones".to_string();
c.signature = Some("fn zones(self, &Ctx)".to_string()); // receiver + arg ⇒ ordinary
let rep = analyze_duplicates(&[a, b, c], &DupThresholds::default(), &BTreeSet::new());
assert_eq!(rep.suppressed_trivial.len(), 0);
assert_eq!(rep.cluster_count, 1);
// `c`'s signature differs, so its edges have lower structural agreement;
// it still clusters through the 0.5 floor (callees agree fully).
let m = &rep.clusters[0].members;
assert_eq!(m.len(), 3);
assert_eq!(m.iter().filter(|x| x.trivial_shape.is_none()).count(), 1);
assert_eq!(m.iter().filter(|x| x.trivial_shape == Some(TrivialShape::TraitImpl)).count(), 2);
}
/// Inventory #2 (`fn new(..) -> Self` ×15) and #17 (`fn path(&self)` ×5):
/// constructor and accessor families are suppressed under their own shape
/// names, and the note counts each shape separately.
#[test]
fn constructor_and_accessor_families_are_suppressed_by_shape() {
let mk = |name: &str, krate: &str, sig: &str, v: Vec<f32>| {
let mut s = sym(&format!("{krate}::{name}"), krate, v, sig, &[]);
s.item_name = name.to_string();
s.impl_header = Some(format!("impl Thing{krate}"));
s
};
let syms = [
mk("new", "k1", "fn new(u64)", vec![1.0, 0.0, 0.0]),
mk("new", "k2", "fn new(u64)", vec![1.0, 0.0, 0.0]),
mk("new", "k3", "fn new(u64)", vec![1.0, 0.0, 0.0]),
mk("path", "p1", "fn path(self)", vec![0.0, 1.0, 0.0]),
mk("path", "p2", "fn path(self)", vec![0.0, 1.0, 0.0]),
];
let rep = analyze_duplicates(&syms, &DupThresholds::default(), &BTreeSet::new());
assert_eq!(rep.cluster_count, 0);
assert_eq!(rep.suppressed_trivial.len(), 2);
let shapes: BTreeSet<&str> = rep.suppressed_trivial.iter().map(|s| s.shape.as_str()).collect();
let want: BTreeSet<&str> = ["accessor", "constructor"].into_iter().collect();
assert_eq!(shapes, want);
let note = rep.suppression_note();
assert!(note.contains("1 accessor") && note.contains("1 constructor"), "{note}");
// Ranked order is preserved into the suppressed list: the 3-member
// constructor family (score 3.0) precedes the 2-member accessor one.
assert_eq!(rep.suppressed_trivial[0].shape, TrivialShape::Constructor);
assert_eq!(rep.suppressed_trivial[1].shape, TrivialShape::Accessor);
}
}