src/mimir_subclone.rs
//! Mimir **SubClones** — duplicate code *inside* items, found by winnowing.
//!
//! # The hole this fills
//!
//! Every duplicate detector in the constellation keys on a **chunk**: dwarves'
//! four tiers hash or embed a chunk, `mimir_analyze` and `mimir_clones` compare
//! chunk vectors. A chunk is an item ([`crate::vector::spans`]). So a block of
//! code that lives *inside* two different functions is invisible to all of them,
//! and **no threshold reaches it** — the enclosing items differ, so the hashes
//! differ and the vectors differ, at every tier and at every setting.
//!
//! MEASURED 2026-08-25 with the `mimirprobe` rig (which `#[path]`-includes the
//! real `vector::chunk` and the real `dupes::tiers`, no warehouse): a
//! **byte-identical 24-line block** planted inside two otherwise different
//! functions in two repos was found **0 times** by tier 1 (exact), tier 2
//! (normalised), tier 3 (structural) and tier 4 (semantic) — first at the
//! shipped defaults, then again with **every gate loosened to 1**
//! (`min_lines: 1, min_code_tokens: 1, min_shape_tokens: 1, cosine: 0.01,
//! cross_repo_only: false, budget: unbounded`). The control — a whole function
//! copied verbatim between the same two repos — was found by tier 1 immediately,
//! in both regimes. The detector is not mis-tuned; it cannot see below an item.
//!
//! # Why winnowing, and not another threshold
//!
//! The boundary is the item, not the size, so no threshold on a chunk-keyed
//! detector can help. What is needed is a detector whose unit is a **run of
//! tokens** rather than a span someone else cut. Winnowing (Schleimer, Wilkerson
//! & Aiken 2003) is the standard answer: fingerprint every `k`-gram, then keep
//! the minimum fingerprint of every window of `w` — a selection that is
//! *position-independent*, so the same run selects the same fingerprints
//! wherever it appears, and that comes with a guarantee:
//!
//! * **every** shared run of at least `w + k - 1` tokens is detected, and
//! * **no** shared run shorter than `k` tokens is ever detected.
//!
//! # Alphabet: identifier-blind shape tokens
//!
//! Tokens are the same identifier-blind shape dwarves' tier 3 uses — keywords
//! verbatim, every other identifier `i`, every literal by KIND — so a copy with
//! renamed locals and retuned constants still matches, and the two detectors
//! agree about what "the same code under different names" means. The lexer here
//! is `proc-macro2` (already a nornir dependency, with `span-locations`) rather
//! than dwarves' hand-rolled one, because this pass runs over whole files that
//! parse and needs a LINE on every token — which the hand-rolled lexer, built
//! for arbitrary non-parsing fragments, does not carry.
//!
//! # Volume is the real risk, so the constants were decided first
//!
//! The liggare already records *10 152 clusters at cosine ≥ 0.80 — far too many
//! to act on*. A sub-item detector produces strictly more candidates than an
//! item-level one, so [`KGRAM_TOKENS`], [`GUARANTEE_TOKENS`], [`WINNOW_WINDOW`]
//! and [`OVERLAP_FLOOR`] were fixed on literature grounds BEFORE this module was
//! written and before any survivor count existed, and the counts are reported
//! as-is. A finding nobody can act on is worse than no finding.
//!
//! # The number a person sees is **65**
//!
//! RE-MEASURED 2026-08-26 on nornir's own `src/` (219 files, 1.32 M tokens,
//! 2.9 s wall, release build, no warehouse) and on nornir + dwarves + edda
//! (1 139 files, 4.56 M tokens, 7.2 s):
//!
//! | corpus | Type-2 | **findings** | groups | of which true sub-item |
//! |---|---|---|---|---|
//! | nornir/src | ON | **65** | 195 | 191 |
//! | nornir/src | OFF | **23** | 26 | 25 |
//! | 3 repos | ON | **347** | 810 | 733 |
//! | 3 repos | OFF | **132** | 171 | 143 |
//!
//! A **group** is one shared run. A [`SubcloneFinding`] is one *region* — the
//! connected component of groups that overlap in source. 195 groups on
//! nornir/src cover **65 regions**, and the largest single region is restated by
//! **38** of them (the warehouse-table modules: `agent_model_runs`,
//! `build_info`, `build_provenance`, `clone_events`, `feature_dep_edges`,
//! `feed_cache`, `lens_cache`, `saga_events`, `semantic_clusters`,
//! `airgap_events`, … — one boilerplate, fourteen files). Reporting 195 is
//! reporting that one boilerplate 38 times and calling it 38 problems. **65 is
//! the number to defend**, and both are always in the report.
//!
//! # The knob is not the threshold, and it is not normalisation either
//!
//! Item granularity ([`pair_items`], SourcererCC's own unit) gives
//! 1 057 / 1 001 / 979 pairs at overlap ≥ 0.70 / 0.80 / 0.90 — a curve that is
//! FLAT (8 % across the whole usable range), so **the threshold is the wrong
//! knob**. Normalisation moves volume ~4.5×, which made it look like the right
//! one, and an earlier note in this lane recorded the shipping decision as
//! *"Type-2 OFF, or one repo at a time with it ON"*.
//!
//! **That decision is wrong on its own fixture.** The verified top find, read by
//! hand on 2026-08-25, is `mimir.rs:332-434` (`fn svg`) ↔
//! `viz/diagram.rs:222-325` (`fn depgraph_svg`). It was recorded as *"103
//! identical lines"*; `diff` says **85 of the 103 are identical and 18 differ**
//! — `g`→`snap`, `out`→`s`, two reworded comments, one retuned stroke colour.
//! It is a **Type-2 clone, not an identical one**. With normalisation OFF the
//! detector cannot state it whole: it collapses to a 36-line fragment
//! (`mimir.rs:344-379`). So OFF is not a cheaper view of the same answer, it is
//! a different and worse one, and the default stays **ON**.
//! `normalisation_off_loses_the_verified_top_find` is that regression guard.
//!
//! What actually made the ON setting reportable was not a threshold at all but
//! an **output de-duplication** — the same move R5 (subsumption) already makes,
//! one step weaker. 195 → 65 without dropping a single group.
//!
//! The cheap setting is one shell variable away and never needs a code edit:
//! `NORNIR_SUBCLONE_NORMALIZE=0` ([`options_from_env`], [`ENV_KEYS`]).
//!
//! The tree is live (other lanes edit it), so these are a snapshot, not a
//! constant — re-run and the counts move by a few.
use std::collections::{BTreeMap, BTreeSet, HashMap};
use crate::vector::spans::{self, ItemSpan};
/// One source file handed to the detector: `(path, text, item spans)`.
///
/// The spans are an INPUT: the code room's node spans for the file (the
/// rustc-driver dump, read by `mimir_lens::room_feed`). `None` = the room holds
/// no span of this file (not compiled by the consumed configuration, or no room
/// in reach) — R6 (callable body) cannot judge it and no site gets an enclosing
/// item; both are COUNTED in the report, never assumed.
pub type SourceFile = (String, String, Option<Vec<ItemSpan>>);
// ---------------------------------------------------------------------------
// The decided constants — DECIDED 2026-08-25, on literature grounds, before the
// first survivor count. Named, with the reasoning, exactly as
// `mimir_clones::MIN_ITEM_SPAN_LINES` and `MAX_RANKED_CLUSTER_SIZE` are.
// ---------------------------------------------------------------------------
/// **`k` — the noise threshold**, in normalised tokens.
///
/// Winnowing's first guarantee: **nothing shorter than `k` tokens can ever
/// match**. This is the same false-positive class
/// [`crate::mimir_clones::MIN_ITEM_SPAN_LINES`] aims at (a 3-line getter embeds
/// close to every other 3-line getter) — but expressed in TOKENS, where it
/// belongs: a 3-line getter is ~15–20 tokens, so at `k = 25` it is not filtered
/// out after the fact, it is **unreportable by construction**. That is strictly
/// stronger than a filter, and it is why winnowing is the right answer here
/// rather than another threshold on the existing chain.
///
/// Schleimer, Wilkerson & Aiken, *Winnowing: Local Algorithms for Document
/// Fingerprinting*, SIGMOD 2003.
pub const KGRAM_TOKENS: usize = 25;
/// **`t` — the guarantee threshold**, in normalised tokens.
///
/// Winnowing's second guarantee: **every shared run of at least `t` tokens is
/// detected**, wherever it sits and however it is surrounded. Not heuristic —
/// this is the algorithm's proven property, and it is what makes the sub-item
/// case reachable at all.
///
/// 60 with a wide margin under our own case: the planted 24-line block is
/// ~150–250 tokens.
pub const GUARANTEE_TOKENS: usize = 60;
/// **`w` — the window**, in k-grams. `w = t − k + 1`. This is the FORMULA, not
/// a setting; changing it changes `t`. Density follows: at least one fingerprint
/// is selected per window, so the index is ~`2/(w+1)` of all k-grams —
/// predictable, which is what keeps the sweep bounded.
pub const WINNOW_WINDOW: usize = GUARANTEE_TOKENS - KGRAM_TOKENS + 1;
/// **The pairing threshold — overlap similarity, not Jaccard.**
///
/// `|shared fingerprints| / max(|A|, |B|)`, as SourcererCC defines it. The
/// `max` denominator is deliberate: Jaccard's `|A ∪ B|` denominator PENALISES a
/// small cloned block sitting inside a large otherwise-different function —
/// which is exactly the pair this lane exists to find. Overlap-max is always
/// ≥ Jaccard, so it is the measure that does not push our own target down.
///
/// 0.70 is SourcererCC's MEASURED operating point (Type-1 → Type-3, function
/// granularity). **Do not lower it to get more hits** — it is precision-chosen,
/// and lowering it is the documented way to wreck the precision.
///
/// Sajnani et al., *SourcererCC: Scaling Code Clone Detection to Big-Code*,
/// ICSE 2016.
pub const OVERLAP_FLOOR: f32 = 0.70;
/// Winnowing + reporting gates.
///
/// The defaults are the pre-registered ones. Changing them after seeing a
/// corpus count is exactly the move that turns a measurement into a story, so
/// the numbers and their reasons are recorded here rather than tuned in place.
#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize)]
pub struct SubcloneOptions {
/// `k` — k-gram length in shape tokens. The **hard noise floor**: no shared
/// run shorter than this can ever be reported. 16 shape tokens is about one
/// short statement; below it every Rust file matches every other one.
pub k: usize,
/// `w` — winnowing window, in k-grams. With `k`, gives the **guarantee
/// threshold** `w + k - 1`: every shared run at least that long is found.
pub w: usize,
/// **R1** — a reported run must be at least this many shape tokens at both
/// sites. 120 ≈ the 24-line planted block with a little margin, and well
/// above `min_shape_tokens`-sized noise.
pub min_run_tokens: usize,
/// **R2** — a reported run must span at least this many source lines at both
/// sites. A 19-line shared run is an idiom in this codebase; a 20-line one
/// is a decision someone made twice.
pub min_run_lines: usize,
/// **R3** — a run must occur in at least two DIFFERENT files. A run repeated
/// inside one file is one grep away and is not what hides.
pub cross_file_only: bool,
/// Above this many sites a group is a house **idiom**, not a twin: kept and
/// counted, but ranked separately so it cannot outrank a real two-site
/// finding by multiplying a small body by a big copy count. (Same ceiling
/// dwarves' `TierOptions::max_sites` uses, deliberately.)
pub max_sites: usize,
/// **R6 — the run must touch a callable body.**
///
/// POST-HOC, and said so plainly: added 2026-08-25 *after* the first
/// corpus measurement, whose entire top-5 by damage was `use` blocks: a
/// 25-line import list clears any token gate easily, because
/// `use a::b::c;` is seven tokens of nothing. Same false-positive class
/// dwarves' `min_code_tokens` was invented for, one level down, and the same
/// lesson — it is not a threshold problem, so it does not get a threshold.
/// A run is kept only when it overlaps a `fn` or `method` span.
///
/// MEASURED on nornir's own `src/` at k=25 / t=60, normalisation ON:
/// **394 groups without it, 191 with it.** Both are always reported
/// (`groups_non_callable`), so the reduction is visible and never assumed.
pub require_callable: bool,
/// A fingerprint occurring in more than this many places is boilerplate, not
/// a seed: extending from all of it is quadratic and yields nothing. The
/// bucket is SKIPPED and COUNTED (`buckets_skipped`), never silently
/// dropped — a clipped run must not read as a clean one.
pub max_bucket: usize,
/// Item-granularity pairing floor — [`OVERLAP_FLOOR`].
pub overlap_floor: f32,
/// **Type-2 normalisation on/off.** `true` (the default) collapses every
/// identifier to `i` and every literal to its kind BEFORE the k-grams, which
/// is what makes a rename irrelevant. `false` keeps identifiers verbatim.
///
/// SourcererCC deliberately does NOT normalise identifiers, to hold
/// precision up. We take the opposite default, and the reason is no longer
/// an argument but a fixture: **OFF loses the verified top find.**
/// `mimir.rs:332-434` ↔ `viz/diagram.rs:222-325` is a Type-2 clone (18 of
/// its 103 lines differ), so with identifiers kept verbatim the detector can
/// only state a 36-line fragment of it. A setting that halves the volume by
/// dropping the one finding a human verified is not a cheaper answer, it is
/// a wrong one — `normalisation_off_loses_the_verified_top_find` holds that
/// line, and it is written so it goes RED if OFF ever becomes able to state
/// the twin whole.
///
/// OFF is still 4.5x cheaper and still SourcererCC's own choice, so it is
/// reachable with `NORNIR_SUBCLONE_NORMALIZE=0` and no code edit
/// ([`options_from_env`]). It is not the default and should not become one
/// without a new fixture to replace the one it drops.
pub normalize_identifiers: bool,
}
impl Default for SubcloneOptions {
fn default() -> Self {
Self {
k: KGRAM_TOKENS,
w: WINNOW_WINDOW,
// Run granularity reports at the GUARANTEE threshold: anything the
// algorithm promises to find is worth showing. (An earlier
// pre-registration in this lane said 120; the decided `t = 60`
// supersedes it, and both counts are measured and reported.)
min_run_tokens: GUARANTEE_TOKENS,
min_run_lines: 20,
cross_file_only: true,
require_callable: true,
max_sites: 12,
max_bucket: 50,
overlap_floor: OVERLAP_FLOOR,
normalize_identifiers: true,
}
}
}
impl SubcloneOptions {
/// Guarantee threshold `w + k - 1`: every shared run at least this many
/// shape tokens long is detected. Stated in the report, because a recall
/// claim without its threshold is not a claim.
pub fn guarantee_tokens(&self) -> usize {
self.w + self.k - 1
}
}
// ---------------------------------------------------------------------------
// The door — the non-default setting must be reachable WITHOUT editing code
// ---------------------------------------------------------------------------
/// `0`/`false`/`off` turns **Type-2 normalisation** off; `1`/`true`/`on` turns
/// it on. The default is ON and stays ON — see
/// [`SubcloneOptions::normalize_identifiers`] and the
/// `normalisation_off_loses_the_verified_top_find` guard. OFF is the cheap,
/// low-volume, low-recall setting; it exists, it is one shell variable away, and
/// it is not what ships.
pub const ENV_NORMALIZE: &str = "NORNIR_SUBCLONE_NORMALIZE";
/// **R2** — minimum source-line height of a reported run, at every site.
pub const ENV_MIN_LINES: &str = "NORNIR_SUBCLONE_MIN_LINES";
/// **R1** — minimum shape-token length of a reported run, at every site.
pub const ENV_MIN_TOKENS: &str = "NORNIR_SUBCLONE_MIN_TOKENS";
/// Item-granularity pairing floor for [`pair_items`] — see [`OVERLAP_FLOOR`].
/// MEASURED to be the wrong knob (0.70 → 0.90 removes 8 %); exposed anyway, so
/// that claim stays falsifiable by anyone with a shell.
pub const ENV_OVERLAP: &str = "NORNIR_SUBCLONE_OVERLAP";
/// Every key this module reads, in one list — so a `--help` or a doc render can
/// enumerate the door instead of restating it and drifting.
pub const ENV_KEYS: &[&str] = &[ENV_NORMALIZE, ENV_MIN_LINES, ENV_MIN_TOKENS, ENV_OVERLAP];
/// Options plus **what the environment actually did to them**.
///
/// A knob that is read and silently dropped is the `test_args()` defect one
/// level down: declarable, validated, rendered, and thrown on the floor at the
/// only seam that mattered. So `applied` names every key that changed something
/// and `rejected` names every key whose value did NOT parse, with the value —
/// a malformed setting is a loud line, never a silent fall back to the default.
#[derive(Debug, Clone, Default)]
pub struct EnvOptions {
pub opts: SubcloneOptions,
/// Keys that were present and parsed, in [`ENV_KEYS`] order.
pub applied: Vec<&'static str>,
/// `KEY=value is not a …` for every key that was present and did not parse.
pub rejected: Vec<String>,
}
impl EnvOptions {
/// The one line a caller prints. Empty environment reads as "defaults", not
/// as silence.
pub fn line(&self) -> String {
let mut s = if self.applied.is_empty() {
"subclone: shipped defaults".to_string()
} else {
format!("subclone: {} from the environment", self.applied.join(", "))
};
s.push_str(&format!(
" (Type-2 {}, R1 {} tokens, R2 {} lines, overlap {:.2})",
if self.opts.normalize_identifiers { "ON" } else { "OFF" },
self.opts.min_run_tokens,
self.opts.min_run_lines,
self.opts.overlap_floor
));
for r in &self.rejected {
s.push_str(&format!("; ⚠ IGNORED {r}"));
}
s
}
}
/// Read [`ENV_KEYS`] from the process environment.
pub fn options_from_env() -> EnvOptions {
options_from_env_with(|k| std::env::var(k).ok())
}
/// [`options_from_env`] with the reader injected — the shape the tests use, so
/// they never call `set_var` and never race the other threads in the binary.
pub fn options_from_env_with(read: impl Fn(&str) -> Option<String>) -> EnvOptions {
let mut e = EnvOptions { opts: SubcloneOptions::default(), ..Default::default() };
if let Some(v) = read(ENV_NORMALIZE) {
match v.trim().to_ascii_lowercase().as_str() {
"1" | "true" | "on" | "yes" => {
e.opts.normalize_identifiers = true;
e.applied.push(ENV_NORMALIZE);
}
"0" | "false" | "off" | "no" => {
e.opts.normalize_identifiers = false;
e.applied.push(ENV_NORMALIZE);
}
_ => e.rejected.push(format!("{ENV_NORMALIZE}={v} is not a boolean")),
}
}
for (key, slot) in
[(ENV_MIN_LINES, &mut e.opts.min_run_lines), (ENV_MIN_TOKENS, &mut e.opts.min_run_tokens)]
{
if let Some(v) = read(key) {
match v.trim().parse::<usize>() {
Ok(n) => {
*slot = n;
e.applied.push(key);
}
Err(_) => e.rejected.push(format!("{key}={v} is not a whole number")),
}
}
}
if let Some(v) = read(ENV_OVERLAP) {
match v.trim().parse::<f32>() {
Ok(f) if (0.0..=1.0).contains(&f) => {
e.opts.overlap_floor = f;
e.applied.push(ENV_OVERLAP);
}
_ => e.rejected.push(format!("{ENV_OVERLAP}={v} is not a fraction in 0.0..=1.0")),
}
}
e.applied.sort_unstable_by_key(|k| ENV_KEYS.iter().position(|x| x == k).unwrap_or(usize::MAX));
e
}
// ---------------------------------------------------------------------------
// Alphabet
// ---------------------------------------------------------------------------
/// Rust keywords kept VERBATIM in a shape (everything else becomes `i`).
///
/// This is a data list, not logic, and it is deliberately the same list dwarves'
/// `dupes::normalize` keeps: the two detectors must agree about what survives a
/// rename, or a finding here would contradict a non-finding there.
const KEYWORDS: &[&str] = &[
"as", "async", "await", "break", "const", "continue", "crate", "dyn", "else", "enum",
"extern", "false", "fn", "for", "if", "impl", "in", "let", "loop", "match", "mod", "move",
"mut", "pub", "ref", "return", "self", "Self", "static", "struct", "super", "trait", "true",
"type", "union", "unsafe", "use", "where", "while", "yield",
];
/// One shape token: the interned alphabet symbol plus the source line it came
/// from. The line is what turns a token run back into a `file:start-end`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ShapeTok {
/// Interned id of the shape symbol (see [`Interner`]).
pub id: u32,
/// 1-based source line.
pub line: u32,
}
/// Assigns a stable `u32` to each distinct shape symbol, so run comparison is
/// integer equality rather than string equality.
#[derive(Debug, Default)]
pub struct Interner {
map: HashMap<String, u32>,
back: Vec<String>,
}
impl Interner {
pub fn intern(&mut self, s: &str) -> u32 {
if let Some(id) = self.map.get(s) {
return *id;
}
let id = self.back.len() as u32;
self.back.push(s.to_string());
self.map.insert(s.to_string(), id);
id
}
pub fn text(&self, id: u32) -> &str {
&self.back[id as usize]
}
}
/// Lex `text` into line-attributed tokens.
///
/// `normalize` selects **Type-2 normalisation**: identifiers collapse to `i` and
/// literals to their kind, which is what makes a rename irrelevant. With it off,
/// identifiers and literals are kept verbatim — SourcererCC's own choice, which
/// trades recall for precision. Both are measured; see
/// [`SubcloneOptions::normalize_identifiers`].
///
/// `None` when the file does not tokenise — never a partial guess.
pub fn shape_tokens(text: &str, interner: &mut Interner) -> Option<Vec<ShapeTok>> {
shape_tokens_opt(text, interner, true)
}
/// [`shape_tokens`] with the Type-2 switch exposed.
pub fn shape_tokens_opt(text: &str, interner: &mut Interner, normalize: bool) -> Option<Vec<ShapeTok>> {
let ts: proc_macro2::TokenStream = text.parse().ok()?;
let mut out = Vec::new();
walk_tokens(ts, interner, normalize, &mut out);
Some(out)
}
fn walk_tokens(ts: proc_macro2::TokenStream, it: &mut Interner, norm: bool, out: &mut Vec<ShapeTok>) {
for t in ts {
match t {
proc_macro2::TokenTree::Ident(id) => {
let s = id.to_string();
// **Visibility is not shape** — same rule dwarves'
// `normalize::shape` applies, and for the same reason: a shared
// leaf is `pub fn`, the hand-rolled copy of it is a private
// `fn`. Same code, same behaviour, different export decision.
if s == "pub" {
continue;
}
let sym = if KEYWORDS.contains(&s.as_str()) || !norm { s.as_str() } else { "i" };
out.push(ShapeTok { id: it.intern(sym), line: id.span().start().line as u32 });
}
proc_macro2::TokenTree::Literal(l) => {
let s = l.to_string();
let kind = if norm {
match s.as_bytes().first() {
Some(b'"') | Some(b'r') | Some(b'b') => "#s",
Some(b'\'') => "#c",
_ => "#n",
}
} else {
s.as_str()
};
out.push(ShapeTok { id: it.intern(kind), line: l.span().start().line as u32 });
}
proc_macro2::TokenTree::Punct(p) => {
let s = p.as_char().to_string();
out.push(ShapeTok { id: it.intern(&s), line: p.span().start().line as u32 });
}
proc_macro2::TokenTree::Group(g) => {
let (o, c) = match g.delimiter() {
proc_macro2::Delimiter::Parenthesis => ("(", ")"),
proc_macro2::Delimiter::Brace => ("{", "}"),
proc_macro2::Delimiter::Bracket => ("[", "]"),
proc_macro2::Delimiter::None => ("\u{2205}", "\u{2205}"),
};
out.push(ShapeTok { id: it.intern(o), line: g.span_open().start().line as u32 });
walk_tokens(g.stream(), it, norm, out);
out.push(ShapeTok { id: it.intern(c), line: g.span_close().start().line as u32 });
}
}
}
}
// ---------------------------------------------------------------------------
// The flat lexer of the clone signals (`crate::clone_signals::norm`)
// ---------------------------------------------------------------------------
/// One token of a function's text, as the clone signals' normaliser reads it.
/// The SAME lexer as [`shape_tokens`] (this file is the one place allowed to
/// name the token crate): the normaliser decides what an identifier's ROLE is
/// from its neighbours, so it needs the raw token, not a shape.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum FlatTok {
/// An identifier or keyword, verbatim (a raw identifier keeps its `r#`).
Ident(String),
/// A literal, by kind: `s` string / byte string, `c` char / byte, `n` number.
Lit(char),
/// One punctuation character; `joint` = glued to the next one (`::`, `->`).
Punct(char, bool),
/// A delimiter: `(`, `[`, `{` open and `)`, `]`, `}` close.
Open(char),
Close(char),
}
/// Lex `text` into a flat token list with the attributes (`#[…]` / `#![…]`,
/// which is also what a doc comment lexes to) left out. Comments and layout
/// are gone by construction. `None` when the text does not tokenise.
pub fn flat_tokens(text: &str) -> Option<Vec<FlatTok>> {
let ts: proc_macro2::TokenStream = text.parse().ok()?;
let mut out = Vec::new();
walk_flat(ts, &mut out);
Some(out)
}
fn walk_flat(ts: proc_macro2::TokenStream, out: &mut Vec<FlatTok>) {
let mut it = ts.into_iter().peekable();
while let Some(t) = it.next() {
match t {
proc_macro2::TokenTree::Punct(p) if p.as_char() == '#' => {
// `#[attr]`, `#![attr]`: an attribute is not behaviour
let bang = matches!(it.peek(), Some(proc_macro2::TokenTree::Punct(q)) if q.as_char() == '!');
if bang {
let _ = it.next();
}
match it.peek() {
Some(proc_macro2::TokenTree::Group(g)) if g.delimiter() == proc_macro2::Delimiter::Bracket => {
let _ = it.next();
}
_ => {
out.push(FlatTok::Punct('#', false));
if bang {
out.push(FlatTok::Punct('!', false));
}
}
}
}
proc_macro2::TokenTree::Punct(p) => out.push(FlatTok::Punct(p.as_char(), p.spacing() == proc_macro2::Spacing::Joint)),
proc_macro2::TokenTree::Ident(id) => out.push(FlatTok::Ident(id.to_string())),
proc_macro2::TokenTree::Literal(l) => {
let s = l.to_string();
let kind = match s.as_bytes() {
[b'"', ..] | [b'r', b'"' | b'#', ..] | [b'b', b'"', ..] | [b'b', b'r', ..] | [b'c', b'"', ..] => 's',
[b'\'', ..] | [b'b', b'\'', ..] => 'c',
_ => 'n',
};
out.push(FlatTok::Lit(kind));
}
proc_macro2::TokenTree::Group(g) => {
let (o, c) = match g.delimiter() {
proc_macro2::Delimiter::Parenthesis => ('(', ')'),
proc_macro2::Delimiter::Brace => ('{', '}'),
proc_macro2::Delimiter::Bracket => ('[', ']'),
proc_macro2::Delimiter::None => {
walk_flat(g.stream(), out);
continue;
}
};
out.push(FlatTok::Open(o));
walk_flat(g.stream(), out);
out.push(FlatTok::Close(c));
}
}
}
}
// ---------------------------------------------------------------------------
// Winnowing
// ---------------------------------------------------------------------------
/// FNV-1a over the interned ids of `toks[i..i+k]`.
fn kgram_hash(toks: &[ShapeTok], i: usize, k: usize) -> u64 {
let mut h: u64 = 0xcbf2_9ce4_8422_2325;
for t in &toks[i..i + k] {
for b in t.id.to_le_bytes() {
h ^= b as u64;
h = h.wrapping_mul(0x0000_0100_0000_01b3);
}
}
h
}
/// **Winnow** — the minimum k-gram hash of every window of `w` consecutive
/// k-grams, ties broken toward the RIGHTMOST occurrence (the canonical rule;
/// picking consistently is what makes the selection position-independent).
///
/// Returns `(hash, kgram_index)`, deduplicated on consecutive repeats.
pub fn winnow(toks: &[ShapeTok], k: usize, w: usize) -> Vec<(u64, usize)> {
if k == 0 || w == 0 || toks.len() < k {
return Vec::new();
}
let grams: Vec<u64> = (0..=toks.len() - k).map(|i| kgram_hash(toks, i, k)).collect();
let mut out: Vec<(u64, usize)> = Vec::new();
if grams.len() <= w {
// Fewer k-grams than one window: one fingerprint for the whole thing.
if let Some((i, h)) = grams.iter().enumerate().min_by_key(|(i, h)| (**h, std::cmp::Reverse(*i))) {
out.push((*h, i));
}
return out;
}
let mut last = usize::MAX;
for start in 0..=grams.len() - w {
let win = &grams[start..start + w];
let mut best = 0usize;
for j in 1..w {
if win[j] <= win[best] {
best = j; // <= keeps the RIGHTMOST minimum
}
}
let idx = start + best;
if idx != last {
out.push((grams[idx], idx));
last = idx;
}
}
out
}
// ---------------------------------------------------------------------------
// Report
// ---------------------------------------------------------------------------
/// One place a shared run occurs.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
pub struct SubcloneSite {
pub file: String,
/// 1-based inclusive.
pub start_line: u32,
/// 1-based inclusive.
pub end_line: u32,
/// Shape tokens in the matched run.
pub tokens: usize,
/// Innermost item the run sits in — a READING label, never identity.
/// `None` when the run straddles items or the file did not parse.
pub enclosing: Option<String>,
/// **The run is STRICTLY SMALLER than the item it sits in.**
///
/// This is the whole value proposition as a boolean. A chunk-keyed tier
/// can only ever express a WHOLE item, so a site with this `true` is one
/// no tier in the constellation can state at all — not at any threshold.
/// Counting "has an enclosing item" instead would be a blind guard: almost
/// every site has one, and the count would read 193 of 193 whatever the
/// detector did.
pub sub_item: bool,
}
impl SubcloneSite {
pub fn lines(&self) -> u32 {
self.end_line.saturating_sub(self.start_line) + 1
}
pub fn location(&self) -> String {
format!("{}:{}-{}", self.file, self.start_line, self.end_line)
}
}
/// One shared run, with every place it occurs.
#[derive(Debug, Clone, PartialEq, serde::Serialize)]
pub struct SubcloneGroup {
/// Stable id — 16 hex of the run's shape hash.
pub key: String,
pub sites: Vec<SubcloneSite>,
/// Median matched-run length in shape tokens.
pub tokens: usize,
/// Median matched-run height in source lines.
pub lines: u32,
/// More than [`SubcloneOptions::max_sites`] sites — a house idiom.
pub idiom: bool,
/// `lines × (sites − 1)` — the same "how much duplicated code exists" rank
/// key dwarves' tiers use, without a tier weight (there is one tier here).
pub damage: f64,
}
/// **One thing a person goes and fixes** — the unit the headline count is in.
///
/// A duplicated region does not arrive as one group. Each maximal extension is
/// maximal only for ITS seed pair, so the same lines come back at several
/// extents with several site sets, and R5's containment rule cannot fold them
/// (a 10-site group is not *contained* in a 7-site one, however much source
/// they share). MEASURED on nornir's own `src/` at the shipped defaults:
/// **195 groups covering 65 regions**, with the largest single region restated
/// by **38** of them. Reporting 195 is reporting the same warehouse-table
/// boilerplate 38 times and calling it 38 problems.
///
/// A finding is a connected component of groups linked by an **overlapping
/// site** — same file, intersecting line ranges. That is an output
/// de-duplication of the same family as R5, one step weaker (overlap, not
/// containment), and both counts are always reported so the reduction is
/// visible and never assumed. `two_unrelated_duplications_stay_two_findings`
/// is the guard against over-merging.
#[derive(Debug, Clone, PartialEq, serde::Serialize)]
pub struct SubcloneFinding {
/// The lead group's key — stable, and the same id the lead carries.
pub key: String,
/// Indices into [`SubcloneReport::groups`], **lead (highest damage) first**.
pub groups: Vec<usize>,
/// Distinct files this region touches, sorted.
pub files: Vec<String>,
/// Total sites across every member group.
pub sites: usize,
/// The lead group's median run height, in source lines.
pub lines: u32,
/// The lead group's damage. **Not a sum** — the members restate one region,
/// so adding them up would count the same lines several times, which is the
/// exact inflation this type exists to undo.
pub damage: f64,
}
/// The whole answer, including what it could NOT do.
#[derive(Debug, Clone, Default, serde::Serialize)]
pub struct SubcloneReport {
/// **The number a person actually sees.** Groups clustered into distinct
/// source regions — see [`SubcloneFinding`]. Ranked by damage.
pub findings: Vec<SubcloneFinding>,
pub groups: Vec<SubcloneGroup>,
/// Groups dropped by R6 (no callable body at some site) — the `use`-block
/// class. Counted, because a filter that hides its work is a silent-empty bug.
pub groups_non_callable: usize,
/// Groups R6 could NOT judge because a site's file carried no item spans
/// (see [`SourceFile`]). Kept, and counted here.
pub groups_r6_unjudged: usize,
/// Files handed over without item spans: their sites carry no enclosing item
/// and R6 cannot judge them. Non-zero ⇒ the report says so.
pub files_without_spans: usize,
/// Groups before the subsumption pass (R5) folded restatements of one
/// region into their longest form. Reported so the reduction is visible.
pub groups_before_subsumption: usize,
/// Groups above the idiom ceiling, counted separately (also in `groups`).
pub idiom_groups: usize,
pub files_scanned: usize,
/// Files that did not tokenise — counted, so "0 groups" is never a lie.
pub files_unparsed: usize,
pub tokens_total: usize,
/// Fingerprint buckets skipped for exceeding `max_bucket`. A non-zero value
/// means the sweep is INCOMPLETE and the report says so.
pub buckets_skipped: usize,
/// Candidate runs that were extended and then rejected by R1/R2.
pub runs_rejected: usize,
/// The options actually used — a count without its gate is not a result.
pub options: SubcloneOptions,
/// `w + k - 1`.
pub guarantee_tokens: usize,
}
// ---------------------------------------------------------------------------
// Detection
// ---------------------------------------------------------------------------
/// Per-file lexing result, the unit `gatling` fans out over.
struct FileToks {
file: String,
toks: Vec<ShapeTok>,
spans: Option<Vec<ItemSpan>>,
fps: Vec<(u64, usize)>,
ok: bool,
}
/// **Detect sub-item clones** across `files` (`(path, source)` pairs).
///
/// CPU fan-out is `gatling` (ROOT LAW #0 — the constellation's ONE worker-pool
/// engine). rayon is forbidden and is not here.
pub fn detect(files: Vec<SourceFile>, opts: &SubcloneOptions) -> SubcloneReport {
let files_scanned = files.len();
let (k, w) = (opts.k.max(1), opts.w.max(1));
let norm = opts.normalize_identifiers;
// ---- phase A: lex + winnow every file, in parallel ----
// Each worker owns its own interner, so the ids are per-file; runs are
// therefore compared by the k-gram HASH of their symbol TEXT, which is
// interner-independent. (Re-interning globally would serialise phase A.)
// LPT-balanced by source size: a 6 000-line file costs ~40× a 150-line one,
// and heaviest-first is the difference between a tail-bound sweep and a flat
// one. Same call `knowledge::symbols` already uses for its per-file syn scan.
let lexed: Vec<FileToks> = znippy_zoomies::gatling_forkjoin::gatling_map_balanced(
&files,
0,
1,
|(_, src, _): &SourceFile| src.len() as u64,
|_, (file, src, spans): &SourceFile| {
let (file, src) = (file.clone(), src.as_str());
let mut it = Interner::default();
match shape_tokens_opt(src, &mut it, norm) {
Some(toks) => {
// Re-key the ids to a canonical, interner-independent symbol id:
// FNV of the symbol text. Two files then agree on token equality
// without sharing an interner.
let toks: Vec<ShapeTok> = toks
.into_iter()
.map(|t| ShapeTok { id: sym_id(it.text(t.id)), line: t.line })
.collect();
let fps = winnow(&toks, k, w);
FileToks { file, toks, spans: spans.clone(), fps, ok: true }
}
None => FileToks { file, toks: Vec::new(), spans: spans.clone(), fps: Vec::new(), ok: false },
}
},
);
let files_unparsed = lexed.iter().filter(|f| !f.ok).count();
let files_without_spans = lexed.iter().filter(|f| f.spans.is_none()).count();
let tokens_total: usize = lexed.iter().map(|f| f.toks.len()).sum();
// ---- phase B: inverted index over the selected fingerprints ----
let mut index: HashMap<u64, Vec<(usize, usize)>> = HashMap::new();
for (fi, f) in lexed.iter().enumerate() {
for (h, gi) in &f.fps {
index.entry(*h).or_default().push((fi, *gi));
}
}
let mut buckets_skipped = 0usize;
let mut seeds: Vec<Vec<(usize, usize)>> = Vec::new();
for (_, occ) in index {
let distinct_files: BTreeSet<usize> = occ.iter().map(|(fi, _)| *fi).collect();
if distinct_files.len() < 2 && opts.cross_file_only {
continue;
}
if occ.len() < 2 {
continue;
}
if occ.len() > opts.max_bucket {
buckets_skipped += 1;
continue;
}
seeds.push(occ);
}
// ---- phase C: extend each seed pair maximally, both directions ----
// Runs are keyed by the hash of their shape-symbol sequence, so the SAME
// run reached from many seeds collapses into one group by construction.
let mut runs: BTreeMap<u64, BTreeSet<(String, u32, u32, usize)>> = BTreeMap::new();
let mut runs_rejected = 0usize;
for occ in &seeds {
for a in 0..occ.len() {
for b in (a + 1)..occ.len() {
let (fa, ia) = occ[a];
let (fb, ib) = occ[b];
if opts.cross_file_only && fa == fb {
continue;
}
let ta = &lexed[fa].toks;
let tb = &lexed[fb].toks;
let Some((sa, ea, sb, eb)) = extend(ta, tb, ia, ib, k) else { continue };
let len = ea - sa + 1;
if len < opts.min_run_tokens {
runs_rejected += 1;
continue;
}
let la = (ta[sa].line, ta[ea].line);
let lb = (tb[sb].line, tb[eb].line);
let ha = la.1.saturating_sub(la.0) + 1;
let hb = lb.1.saturating_sub(lb.0) + 1;
if (ha as usize) < opts.min_run_lines || (hb as usize) < opts.min_run_lines {
runs_rejected += 1;
continue;
}
let key = run_hash(&ta[sa..=ea]);
let e = runs.entry(key).or_default();
e.insert((lexed[fa].file.clone(), la.0, la.1, len));
e.insert((lexed[fb].file.clone(), lb.0, lb.1, len));
}
}
}
// ---- phase D: groups ----
let file_spans: HashMap<&str, &Vec<ItemSpan>> = lexed
.iter()
.filter_map(|f| f.spans.as_ref().map(|sp| (f.file.as_str(), sp)))
.collect();
let mut groups: Vec<SubcloneGroup> = Vec::new();
let mut non_callable = 0usize;
let mut r6_unjudged = 0usize;
for (key, sites) in runs {
// Drop a site fully contained in another site of the same group (the
// same run reached from two seeds at slightly different extents).
let sv: Vec<(String, u32, u32, usize)> = sites.into_iter().collect();
let mut kept: Vec<&(String, u32, u32, usize)> = Vec::new();
for s in &sv {
if sv.iter().any(|o| o != s && o.0 == s.0 && o.1 <= s.1 && o.2 >= s.2 && o.3 > s.3) {
continue;
}
kept.push(s);
}
if kept.len() < 2 {
continue;
}
let mut out_sites: Vec<SubcloneSite> = kept
.iter()
.map(|(file, s, e, len)| SubcloneSite {
enclosing: file_spans
.get(file.as_str())
.and_then(|sp| spans::enclosing(sp, *s as usize))
.map(|i| i.qualified()),
// Strictly smaller than the item it sits in: the run misses at
// least one line of it at one end or the other.
sub_item: file_spans
.get(file.as_str())
.and_then(|sp| spans::enclosing(sp, *s as usize))
.is_some_and(|i| i.start_line < *s as usize || i.end_line > *e as usize),
file: file.clone(),
start_line: *s,
end_line: *e,
tokens: *len,
})
.collect();
out_sites.sort_by(|a, b| (&a.file, a.start_line).cmp(&(&b.file, b.start_line)));
// R6 — every site must overlap a callable body. A run that lives wholly
// in a `use` block or a const table is shared TEXT, not shared BEHAVIOUR.
// A site in a file with NO spans cannot be judged: the group is kept and
// counted as unjudged, never dropped on a missing input.
if opts.require_callable && out_sites.iter().any(|s| !file_spans.contains_key(s.file.as_str())) {
r6_unjudged += 1;
} else if opts.require_callable {
let all_callable = out_sites.iter().all(|s| {
file_spans.get(s.file.as_str()).is_some_and(|sp| {
sp.iter().any(|i| {
(i.kind == "fn" || i.kind == "method")
&& i.start_line <= s.end_line as usize
&& s.start_line as usize <= i.end_line
})
})
});
if !all_callable {
non_callable += 1;
continue;
}
}
let mut hs: Vec<u32> = out_sites.iter().map(|s| s.lines()).collect();
hs.sort_unstable();
let mut ts: Vec<usize> = out_sites.iter().map(|s| s.tokens).collect();
ts.sort_unstable();
let lines = hs[(hs.len() - 1) / 2];
let idiom = out_sites.len() > opts.max_sites;
groups.push(SubcloneGroup {
key: format!("{key:016x}"),
damage: lines as f64 * (out_sites.len() - 1) as f64,
sites: out_sites,
tokens: ts[(ts.len() - 1) / 2],
lines,
idiom,
});
}
// ---- phase E: SUBSUMPTION (R5) ----
//
// Added 2026-08-25 AFTER the first green run, which is worth saying plainly:
// the pre-registered gate (R1/R2) is untouched, but the first run reported
// the SAME region five times at five extents — 103-145, 103-139, 103-133,
// 103-129, 103-127 — because different seed pairs pair different site sets
// and each maximal extension is maximal only for ITS pair. That is one
// finding restated, not five findings. A group is dropped when every one of
// its sites sits inside a site of a LONGER surviving group: strictly a
// de-duplication of the OUTPUT, never a threshold. Both counts are reported
// (`groups_before_subsumption`) so the reduction is visible, not assumed.
groups.sort_by(|a, b| {
b.tokens.cmp(&a.tokens).then(b.damage.total_cmp(&a.damage)).then(a.key.cmp(&b.key))
});
let groups_before_subsumption = groups.len();
let mut kept: Vec<SubcloneGroup> = Vec::new();
for g in groups {
let subsumed = kept.iter().any(|h| {
g.sites.iter().all(|s| {
h.sites
.iter()
.any(|t| t.file == s.file && t.start_line <= s.start_line && t.end_line >= s.end_line)
})
});
if !subsumed {
kept.push(g);
}
}
let mut groups = kept;
groups.sort_by(|a, b| b.damage.total_cmp(&a.damage).then(a.key.cmp(&b.key)));
let idiom_groups = groups.iter().filter(|g| g.idiom).count();
// ---- phase F: FINDINGS — the number a person actually sees ----
let findings = cluster_findings(&groups);
SubcloneReport {
findings,
idiom_groups,
groups_non_callable: non_callable,
groups_r6_unjudged: r6_unjudged,
files_without_spans,
groups_before_subsumption,
groups,
files_scanned,
files_unparsed,
tokens_total,
buckets_skipped,
runs_rejected,
options: *opts,
guarantee_tokens: opts.guarantee_tokens(),
}
}
/// Group the damage-sorted `groups` into [`SubcloneFinding`]s — the connected
/// components of "shares an overlapping site with".
///
/// A sweep, not the O(n²) cross-product: every site is emitted once as a
/// `(file, start, end, group)` tuple into ONE preallocated vector, sorted, then
/// walked per file with a running high-water end. Consecutive intervals are
/// unioned whenever the next one starts at or before that high-water mark, which
/// yields exactly the transitive closure of overlap — the merged-interval
/// identity. `O(S log S)` in the number of sites, one allocation.
fn cluster_findings(groups: &[SubcloneGroup]) -> Vec<SubcloneFinding> {
if groups.is_empty() {
return Vec::new();
}
let n = groups.len();
let mut parent: Vec<usize> = (0..n).collect();
fn root(p: &mut [usize], mut x: usize) -> usize {
while p[x] != x {
p[x] = p[p[x]]; // path halving
x = p[x];
}
x
}
let total_sites: usize = groups.iter().map(|g| g.sites.len()).sum();
let mut ivals: Vec<(&str, u32, u32, usize)> = Vec::with_capacity(total_sites);
for (gi, g) in groups.iter().enumerate() {
for s in &g.sites {
ivals.push((s.file.as_str(), s.start_line, s.end_line, gi));
}
}
ivals.sort_unstable_by(|a, b| (a.0, a.1, a.2).cmp(&(b.0, b.1, b.2)));
let mut i = 0usize;
while i < ivals.len() {
let file = ivals[i].0;
let (mut high, mut prev) = (ivals[i].2, ivals[i].3);
let mut j = i + 1;
while j < ivals.len() && ivals[j].0 == file {
if ivals[j].1 <= high {
let (a, b) = (root(&mut parent, prev), root(&mut parent, ivals[j].3));
if a != b {
parent[a] = b;
}
high = high.max(ivals[j].2);
} else {
high = ivals[j].2;
}
prev = ivals[j].3;
j += 1;
}
i = j;
}
// Components, in first-seen order — and `groups` is already damage-sorted,
// so the first member of each component IS its lead.
let mut slot: Vec<Option<usize>> = vec![None; n];
let mut members: Vec<Vec<usize>> = Vec::new();
for gi in 0..n {
let r = root(&mut parent, gi);
match slot[r] {
Some(s) => members[s].push(gi),
None => {
slot[r] = Some(members.len());
members.push(vec![gi]);
}
}
}
let mut out: Vec<SubcloneFinding> = members
.into_iter()
.map(|m| {
let lead = &groups[m[0]];
let mut files: Vec<String> =
m.iter().flat_map(|g| groups[*g].sites.iter().map(|s| s.file.clone())).collect();
files.sort();
files.dedup();
SubcloneFinding {
key: lead.key.clone(),
sites: m.iter().map(|g| groups[*g].sites.len()).sum(),
files,
lines: lead.lines,
damage: lead.damage,
groups: m,
}
})
.collect();
out.sort_by(|a, b| b.damage.total_cmp(&a.damage).then(a.key.cmp(&b.key)));
out
}
/// Interner-independent symbol id: FNV-1a of the symbol text.
fn sym_id(s: &str) -> u32 {
let mut h: u32 = 0x811c_9dc5;
for b in s.as_bytes() {
h ^= *b as u32;
h = h.wrapping_mul(0x0100_0193);
}
h
}
/// FNV-1a over a run's symbol ids — the group key.
fn run_hash(run: &[ShapeTok]) -> u64 {
let mut h: u64 = 0xcbf2_9ce4_8422_2325;
for t in run {
for b in t.id.to_le_bytes() {
h ^= b as u64;
h = h.wrapping_mul(0x0000_0100_0000_01b3);
}
}
h
}
/// Extend a matching k-gram seed at `ia` in `a` / `ib` in `b` maximally in both
/// directions, returning `(start_a, end_a, start_b, end_b)` inclusive token
/// indices — or `None` when the seed's k-grams are not actually equal (a
/// fingerprint collision, which winnowing does not rule out and which a
/// detector that trusted the hash would report as a finding).
fn extend(a: &[ShapeTok], b: &[ShapeTok], ia: usize, ib: usize, k: usize) -> Option<(usize, usize, usize, usize)> {
if ia + k > a.len() || ib + k > b.len() {
return None;
}
for j in 0..k {
if a[ia + j].id != b[ib + j].id {
return None; // hash collision, not a match
}
}
let (mut sa, mut sb) = (ia, ib);
while sa > 0 && sb > 0 && a[sa - 1].id == b[sb - 1].id {
sa -= 1;
sb -= 1;
}
let (mut ea, mut eb) = (ia + k - 1, ib + k - 1);
while ea + 1 < a.len() && eb + 1 < b.len() && a[ea + 1].id == b[eb + 1].id {
ea += 1;
eb += 1;
}
Some((sa, ea, sb, eb))
}
#[cfg(test)]
mod tests {
use super::*;
/// TEST FIXTURE spans for the hand-written fixtures below — one `fn` span per
/// top-level `fn` line, ending at the next column-0 `}` (or on the same line
/// for a one-line body). Fixture data, not a parser: the fixtures are written
/// in exactly this shape, and production spans come from the driver.
pub(super) fn fixture_spans(src: &str) -> Vec<ItemSpan> {
let lines: Vec<&str> = src.lines().collect();
let mut out = Vec::new();
for (i, l) in lines.iter().enumerate() {
let t = l.trim_start();
let Some(rest) = ["pub(crate) fn ", "pub fn ", "fn "]
.iter()
.find_map(|p| t.strip_prefix(p))
else {
continue;
};
if l.len() != t.len() {
continue; // top-level items only
}
let name: String = rest.chars().take_while(|c| c.is_alphanumeric() || *c == '_').collect();
let end = if l.trim_end().ends_with('}') {
i
} else {
(i + 1..lines.len()).find(|&j| lines[j] == "}").unwrap_or(i)
};
out.push(ItemSpan {
kind: "fn",
name,
path: String::new(),
start_line: i + 1,
end_line: end + 1,
depth: 0,
is_leaf: true,
});
}
out
}
/// The fixtures with their spans attached, as production callers hand them.
pub(super) fn spanned(files: Vec<(String, String)>) -> Vec<SourceFile> {
files
.into_iter()
.map(|(p, t)| {
let sp = fixture_spans(&t);
(p, t, Some(sp))
})
.collect()
}
fn detect(files: Vec<(String, String)>, opts: &SubcloneOptions) -> SubcloneReport {
super::detect(spanned(files), opts)
}
/// The 24-line block the red proof plants. Kept here so the green half of
/// the proof lives next to the code that turned it green.
const PLANTED: &str = "\
let mut acc: Vec<(String, u64)> = Vec::new();
let mut carry: u64 = 0;
for (idx, raw) in input.iter().enumerate() {
let trimmed = raw.trim_end_matches(|c: char| c.is_whitespace());
if trimmed.is_empty() {
carry = carry.saturating_add(1);
continue;
}
let weight = trimmed.len() as u64 * (idx as u64 + 1);
if weight % 3 == 0 {
carry = carry.wrapping_mul(31).wrapping_add(weight);
} else {
carry = carry.wrapping_add(weight >> 2);
}
acc.push((trimmed.to_string(), carry));
if acc.len() > 64 {
acc.remove(0);
}
}
acc.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
let total: u64 = acc.iter().map(|(_, w)| *w).fold(0u64, |a, b| a ^ b);
if total == 0 {
return Default::default();
}";
pub(super) fn file_a() -> String {
format!(
"pub fn summarise_manifest(input: &[String], route: &str) -> Vec<(String, u64)> {{\n\
\x20 let route_key = route.to_ascii_uppercase();\n\
\x20 let mut seen = std::collections::BTreeMap::new();\n\
\x20 for r in input {{ *seen.entry(r.clone()).or_insert(0) += 1; }}\n\
{PLANTED}\n\
\x20 let head = acc.first().map(|(n, _)| n.clone()).unwrap_or_default();\n\
\x20 eprintln!(\"{{route_key}} {{head}}\");\n\
\x20 acc\n\
}}\n"
)
}
pub(super) fn file_b() -> String {
format!(
"pub(crate) fn rollup_samples(input: &[String], window: u64) -> Vec<(String, u64)> {{\n\
\x20 if window == 0 {{ return Vec::new(); }}\n\
\x20 let mut hist = [0u32; 16];\n\
\x20 for (i, s) in input.iter().enumerate() {{ hist[i % 16] += s.len() as u32; }}\n\
{PLANTED}\n\
\x20 if hist[0] as usize > acc.len() {{ acc.truncate(acc.len() / 2); }}\n\
\x20 acc\n\
}}\n"
)
}
pub(super) fn corpus() -> Vec<(String, String)> {
vec![("alpha/src/manifest.rs".into(), file_a()), ("beta/src/rollup.rs".into(), file_b())]
}
#[test]
fn the_planted_sub_item_block_is_found() {
// GREEN. The RED half is in `red_control_*` below and in the mimirprobe
// rig, which runs the shipped chunk-keyed chain over these same two
// files and reports 0.
let r = detect(corpus(), &SubcloneOptions::default());
assert_eq!(r.files_unparsed, 0, "both fixtures tokenise");
assert_eq!(r.groups.len(), 1, "exactly one shared run: {:#?}", r.groups);
let g = &r.groups[0];
assert_eq!(g.sites.len(), 2);
assert!(g.lines >= 20, "the 24-line block, not a fragment: {}", g.lines);
assert!(g.tokens >= 120, "past the pre-registered token gate: {}", g.tokens);
assert_eq!(g.sites[0].file, "alpha/src/manifest.rs");
assert_eq!(g.sites[1].file, "beta/src/rollup.rs");
assert_eq!(
g.sites[0].enclosing.as_deref(),
Some("summarise_manifest"),
"the run is labelled with the item it hides inside"
);
assert_eq!(g.sites[1].enclosing.as_deref(), Some("rollup_samples"));
}
#[test]
fn a_rename_does_not_hide_the_clone() {
// The alphabet is identifier-blind, so renaming every local still matches.
let renamed = file_b().replace("acc", "bucket").replace("carry", "roll").replace("trimmed", "clean");
let r = detect(
vec![("alpha/src/manifest.rs".into(), file_a()), ("beta/src/rollup.rs".into(), renamed)],
&SubcloneOptions::default(),
);
assert_eq!(r.groups.len(), 1, "renamed copy still found");
}
#[test]
fn a_retuned_constant_does_not_hide_the_clone() {
// Literals collapse to their KIND, so `31` -> `37` and `64` -> `128` match.
let retuned = file_b().replace("wrapping_mul(31)", "wrapping_mul(37)").replace("> 64", "> 128");
let r = detect(
vec![("alpha/src/manifest.rs".into(), file_a()), ("beta/src/rollup.rs".into(), retuned)],
&SubcloneOptions::default(),
);
assert_eq!(r.groups.len(), 1, "retuned copy still found");
}
// ---- LAW 2: the guard must be shown to FAIL ----
#[test]
fn red_control_unrelated_files_yield_nothing() {
// If this ever passes with a finding, the detector matches noise and
// every green above is worthless.
let r = detect(
vec![
("alpha/src/manifest.rs".into(), file_a()),
(
"gamma/src/other.rs".into(),
"pub fn unrelated(x: u32) -> u32 {\n let mut t = 0u32;\n for i in 0..x { t = t.wrapping_add(i * 3); }\n t\n}\n".into(),
),
],
&SubcloneOptions::default(),
);
assert!(r.groups.is_empty(), "unrelated code is not a clone: {:#?}", r.groups);
}
#[test]
fn red_control_a_shorter_shared_run_is_rejected_by_the_gate() {
// Half the block, shared. Below the pre-registered 120-token / 20-line
// gate, so it must NOT be reported — proving the gate is load-bearing
// and not decorative.
let half: String = PLANTES_HALF.into();
let a = format!("pub fn one(input: &[String]) -> u32 {{\n{half}\n 0\n}}\n");
let b = format!("pub fn two(input: &[String]) -> u32 {{\n{half}\n 1\n}}\n");
let r = detect(vec![("a.rs".into(), a), ("b.rs".into(), b)], &SubcloneOptions::default());
assert!(r.groups.is_empty(), "a short shared run is Rust, not a clone: {:#?}", r.groups);
assert!(r.runs_rejected > 0, "and it was REJECTED, not simply never seen");
}
const PLANTES_HALF: &str = "\
let mut acc: Vec<(String, u64)> = Vec::new();
let mut carry: u64 = 0;
for (idx, raw) in input.iter().enumerate() {
let trimmed = raw.trim_end_matches(|c: char| c.is_whitespace());
carry = carry.wrapping_mul(31).wrapping_add(trimmed.len() as u64);
}";
#[test]
fn red_control_same_file_repetition_is_not_cross_file() {
let doubled = format!("{}\n{}", file_a(), file_a().replace("summarise_manifest", "summarise_manifest2"));
let r = detect(vec![("only.rs".into(), doubled)], &SubcloneOptions::default());
assert!(r.groups.is_empty(), "cross_file_only must suppress an in-file repeat");
}
#[test]
fn winnow_selects_the_same_fingerprints_wherever_a_run_appears() {
// The property the whole method rests on. If winnowing were
// position-dependent, a shifted copy would select different
// fingerprints and be missed.
let mut it = Interner::default();
let body = "fn f() { let a = 1; let b = 2; let c = a + b; let d = c * 3; let e = d - 1; let g = e / 2; }";
let pad = "fn pad() { let z = 9; }\n";
let t1 = shape_tokens(body, &mut it).unwrap();
let t2 = shape_tokens(&format!("{pad}{body}"), &mut it).unwrap();
let f1: BTreeSet<u64> = winnow(&t1, 6, 4).into_iter().map(|(h, _)| h).collect();
let f2: BTreeSet<u64> = winnow(&t2, 6, 4).into_iter().map(|(h, _)| h).collect();
assert!(!f1.is_empty());
assert!(f1.is_subset(&f2), "a shifted copy selects the same fingerprints");
}
#[test]
fn winnow_is_not_the_identity_it_actually_discards() {
// A "winnower" that returned every k-gram would make every test above
// pass while being useless. Assert it really selects a minority.
let mut it = Interner::default();
let src: String = (0..200).map(|i| format!("fn f{i}() {{ let x{i} = {i}; }}\n")).collect();
let toks = shape_tokens(&src, &mut it).unwrap();
let fps = winnow(&toks, 16, 25);
let grams = toks.len().saturating_sub(15);
assert!(fps.len() * 4 < grams, "winnowed {} of {} k-grams", fps.len(), grams);
assert!(!fps.is_empty());
}
#[test]
fn extend_rejects_a_hash_collision() {
// `extend` re-verifies the seed token-by-token. Feed it a seed that does
// not actually match and it must return None rather than a finding.
let mut it = Interner::default();
let a = shape_tokens("fn a() { let x = 1; }", &mut it).unwrap();
let b = shape_tokens("struct B { y: u32 }", &mut it).unwrap();
assert!(extend(&a, &b, 0, 0, 3).is_none());
}
#[test]
fn guarantee_threshold_is_reported() {
let o = SubcloneOptions::default();
assert_eq!(o.guarantee_tokens(), GUARANTEE_TOKENS, "t = w + k - 1 = 36 + 25 - 1 = 60");
let r = detect(corpus(), &o);
assert_eq!(r.guarantee_tokens, GUARANTEE_TOKENS);
assert_eq!(r.options.min_run_tokens, GUARANTEE_TOKENS);
assert_eq!(o.k, KGRAM_TOKENS);
assert_eq!(o.w, WINNOW_WINDOW);
assert!((o.overlap_floor - OVERLAP_FLOOR).abs() < f32::EPSILON);
}
#[test]
fn an_unparseable_file_is_counted_not_swallowed() {
let r = detect(
vec![("bad.rs".into(), "fn ((( ;;; \" unterminated".into()), ("a.rs".into(), file_a())],
&SubcloneOptions::default(),
);
assert_eq!(r.files_unparsed, 1, "a file that did not tokenise is COUNTED");
assert_eq!(r.files_scanned, 2);
}
}
#[cfg(test)]
mod r6_tests {
use super::*;
fn detect(files: Vec<(String, String)>, opts: &SubcloneOptions) -> SubcloneReport {
super::detect(super::tests::spanned(files), opts)
}
/// R6's own red: a long shared `use` block is shared TEXT, not shared
/// behaviour, and it was the entire top-5 of the first corpus run. With the
/// filter off it MUST be reported (proving the fixture really does trip the
/// pre-registered gate); with it on it MUST NOT be. A filter that cannot be
/// shown to change the answer is decoration.
#[test]
fn a_shared_use_block_is_reported_without_r6_and_suppressed_with_it() {
// Deliberately SHAPE-VARIED. A block of 40 identical `use a::b::{c,d,e};`
// lines is shape-periodic: every k-gram in it repeats ~40× per file, the
// fingerprint bucket blows past `max_bucket` and the block is skipped for
// a reason that has nothing to do with R6. That fixture made the RED half
// of this test pass for the wrong reason, so it is not the fixture.
let imports: String = (0..24)
.map(|i| {
match i % 5 {
0 => format!("use crate_{i}::thing;\n"),
1 => format!("use crate_{i}::deep::nested::{{One, Two, Three}};\n"),
2 => format!("pub use crate_{i}::re_exported as Alias{i};\n"),
3 => format!("use crate_{i}::{{a, b, c, d, e, f, g}};\n"),
_ => format!("use crate_{i}::mid::{{Left, Right}};\nuse crate_{i}::tail;\n"),
}
})
.collect();
// The two functions are STRUCTURALLY different, so the shared run stops
// at the end of the imports. With identical signatures the run would
// extend into a real `fn` and R6 would rightly keep it — which made an
// earlier version of this fixture fail for a reason that was not R6.
let a = format!("{imports}\npub fn work_a(x: u32) -> u32 {{\n x + 1\n}}\n");
let b = format!("{imports}\nstruct Held;\nimpl Held {{ const N: usize = 3; }}\n");
let files = vec![("a.rs".to_string(), a), ("b.rs".to_string(), b)];
let off = SubcloneOptions { require_callable: false, ..Default::default() };
let r_off = detect(files.clone(), &off);
assert!(
!r_off.groups.is_empty(),
"RED: the import block clears the pre-registered 120-token / 20-line gate"
);
let r_on = detect(files, &SubcloneOptions::default());
assert!(r_on.groups.is_empty(), "GREEN: R6 drops it — no callable body in the run");
assert!(r_on.groups_non_callable > 0, "and it was COUNTED, not silently lost");
}
/// The other half: R6 must not eat a real finding. The planted block lives
/// inside a function, so it survives the filter.
#[test]
fn r6_does_not_eat_a_run_inside_a_function() {
let r = detect(super::tests::corpus(), &SubcloneOptions::default());
assert_eq!(r.groups.len(), 1, "the planted block still survives R6");
assert_eq!(r.groups_non_callable, 0);
}
}
// ---------------------------------------------------------------------------
// Item granularity — SourcererCC's overlap similarity, for comparison
// ---------------------------------------------------------------------------
/// One item-granularity candidate pair, scored the SourcererCC way.
#[derive(Debug, Clone, PartialEq, serde::Serialize)]
pub struct ItemPair {
pub a: SubcloneSite,
pub b: SubcloneSite,
/// `|shared fingerprints| / max(|A|, |B|)` — see [`OVERLAP_FLOOR`].
pub overlap: f32,
/// Do the shipped chunk-keyed tiers already have a shot at this pair? True
/// when BOTH sites are whole items, which is the only granularity a chunk
/// has. A pair with this `false` is one today's chain cannot express.
pub visible_to_chunk_chain: bool,
}
/// **Overlap similarity** — `|A ∩ B| / max(|A|, |B|)`, SourcererCC's measure.
///
/// Deliberately NOT Jaccard: `|A ∪ B|` in the denominator penalises a small
/// cloned block inside a large otherwise-different function, which is precisely
/// the pair this module exists to find. `0.0` for an empty set on either side —
/// never a divide-by-zero NaN leaking into a rank key.
pub fn overlap_similarity(a: &BTreeSet<u64>, b: &BTreeSet<u64>) -> f32 {
let d = a.len().max(b.len());
if d == 0 {
return 0.0;
}
a.intersection(b).count() as f32 / d as f32
}
/// **Item-granularity clone pairs**, the SourcererCC comparison point.
///
/// Candidates are the leaf item spans from [`crate::vector::spans`] — one per
/// `fn`/`method`, which layer 1 made possible (before it, an `impl` block was
/// one candidate and its methods had no span of their own). Each candidate's
/// signature is the set of winnowing fingerprints falling inside it; a pair
/// survives when [`overlap_similarity`] ≥ `floor`.
///
/// This is here to be MEASURED against the run-granularity detector, not as a
/// replacement for it: a 24-line block shared between a 200-line and a 300-line
/// function has an overlap of roughly `24/300`, far under any usable floor, so
/// item granularity cannot reach the sub-item case however the floor is set.
/// The number that shows that is worth more than the argument.
pub fn pair_items(files: &[SourceFile], opts: &SubcloneOptions, floor: f32) -> Vec<ItemPair> {
let (k, w, norm) = (opts.k.max(1), opts.w.max(1), opts.normalize_identifiers);
struct Cand {
site: SubcloneSite,
fps: BTreeSet<u64>,
}
let per_file: Vec<Vec<Cand>> = znippy_zoomies::gatling_forkjoin::gatling_map_balanced(
files,
0,
1,
|(_, src, _): &SourceFile| src.len() as u64,
|_, (file, src, spans): &SourceFile| {
let mut it = Interner::default();
let Some(toks) = shape_tokens_opt(src, &mut it, norm) else { return Vec::new() };
let toks: Vec<ShapeTok> =
toks.into_iter().map(|t| ShapeTok { id: sym_id(it.text(t.id)), line: t.line }).collect();
let fps = winnow(&toks, k, w);
let Some(spans) = spans else { return Vec::new() };
spans
.iter()
.filter(|i| i.is_leaf && (i.kind == "fn" || i.kind == "method"))
.filter_map(|i| {
let set: BTreeSet<u64> = fps
.iter()
.filter(|(_, gi)| {
// The k-gram at `gi` lies inside the item when both
// its first and last token do.
let (s, e) = (*gi, (gi + k - 1).min(toks.len().saturating_sub(1)));
toks[s].line as usize >= i.start_line && (toks[e].line as usize) <= i.end_line
})
.map(|(h, _)| *h)
.collect();
if set.is_empty() {
return None;
}
Some(Cand {
site: SubcloneSite {
file: file.clone(),
start_line: i.start_line as u32,
end_line: i.end_line as u32,
tokens: set.len(),
enclosing: Some(i.qualified()),
// An item-granularity candidate IS the whole item.
sub_item: false,
},
fps: set,
})
})
.collect()
},
);
// Inverted index so only candidates sharing at least one fingerprint are
// ever compared — the SourcererCC filtering heuristic, and the reason this
// is not O(n²) over 5 000 functions.
let cands: Vec<Cand> = per_file.into_iter().flatten().collect();
let mut inv: HashMap<u64, Vec<usize>> = HashMap::new();
for (i, c) in cands.iter().enumerate() {
for f in &c.fps {
inv.entry(*f).or_default().push(i);
}
}
let mut seen: BTreeSet<(usize, usize)> = BTreeSet::new();
let mut out = Vec::new();
for (_, occ) in inv {
if occ.len() > opts.max_bucket {
continue;
}
for x in 0..occ.len() {
for y in (x + 1)..occ.len() {
let (i, j) = (occ[x].min(occ[y]), occ[x].max(occ[y]));
if i == j || !seen.insert((i, j)) {
continue;
}
let (a, b) = (&cands[i], &cands[j]);
if opts.cross_file_only && a.site.file == b.site.file {
continue;
}
let ov = overlap_similarity(&a.fps, &b.fps);
if ov >= floor {
out.push(ItemPair {
a: a.site.clone(),
b: b.site.clone(),
overlap: ov,
visible_to_chunk_chain: true,
});
}
}
}
}
out.sort_by(|p, q| q.overlap.total_cmp(&p.overlap));
out
}
#[cfg(test)]
mod normalisation_tests {
use super::*;
fn detect(files: Vec<(String, String)>, opts: &SubcloneOptions) -> SubcloneReport {
super::detect(super::tests::spanned(files), opts)
}
/// **The Type-2 trade, measured on both sides.**
///
/// Normalisation ON buys reordering-and-rename recall and costs volume;
/// OFF is SourcererCC's own choice and costs recall on renames. MEASURED
/// 2026-08-25 over nornir + dwarves + edda (975 `.rs` files): run-granularity
/// groups **680 with it on, 150 with it off** — a 4.5× volume difference on
/// the same corpus at the same `k`/`t`. Neither is "the answer"; the number
/// is, and it is why this is a switch and not a constant.
#[test]
fn normalisation_off_still_finds_a_byte_identical_block_but_loses_a_rename() {
let off = SubcloneOptions { normalize_identifiers: false, ..Default::default() };
// Byte-identical: found either way. This is the load-bearing half — the
// cheap, low-volume setting does NOT give up the planted case.
let r = detect(super::tests::corpus(), &off);
assert_eq!(r.groups.len(), 1, "an identical block is found without normalisation");
// Renamed: found WITH normalisation (asserted next door), lost without.
// That is the documented cost, and it is asserted rather than described.
let renamed = super::tests::file_b()
.replace("acc", "bucket")
.replace("carry", "roll")
.replace("trimmed", "clean");
let files = vec![
("alpha/src/manifest.rs".to_string(), super::tests::file_a()),
("beta/src/rollup.rs".to_string(), renamed),
];
assert!(
detect(files.clone(), &off).groups.is_empty(),
"RED for the cheap setting: a rename hides the clone when identifiers are kept"
);
assert_eq!(
detect(files, &SubcloneOptions::default()).groups.len(),
1,
"GREEN: normalisation is what buys the rename back"
);
}
}
#[cfg(test)]
mod actionability_tests {
use super::*;
fn detect(files: Vec<(String, String)>, opts: &SubcloneOptions) -> SubcloneReport {
super::detect(super::tests::spanned(files), opts)
}
/// **Shape-varied** body lines. A block of N *identical-shaped* lines is
/// shape-periodic: after normalisation every k-gram in it is the same one,
/// the fingerprint bucket blows past `max_bucket` and the block is skipped
/// for a reason that has nothing to do with what is being tested. (The
/// r6 fixture next door was rewritten for exactly this.) Eight distinct
/// statement shapes, cycled, keep the k-grams distinct.
fn body(n: usize, acc: &str, src: &str) -> String {
(0..n)
.map(|i| match i % 8 {
0 => format!(" let {acc}_{i} = {src}.edges.iter().filter(|e| e.from == {i}).count();\n"),
1 => format!(" if {acc}_{}.checked_mul({i}).is_some() {{ {acc}_{}.rotate_left({i}); }}\n", i - 1, i - 1),
2 => format!(" let mut {acc}_{i} = String::with_capacity({});\n", i * 3),
3 => format!(" for q in {src}.nodes.iter().skip({i}) {{ {acc}_{}.push_str(q.name()); }}\n", i - 1),
4 => format!(" match {src}.kind({i}) {{ Some(k) => {acc}_{}.push('x'), None => break }}\n", i - 2),
5 => format!(" let {acc}_{i}: Vec<u32> = {src}.rows({i}).map(|r| r.id ^ {i}).collect();\n"),
6 => format!(" while {acc}_{i}.len() > {} {{ {acc}_{i}.pop(); }}\n", i + 4),
_ => format!(" {src}.emit(&format!(\"{{}}/{{}}\", {acc}_{i}.len(), {i}));\n"),
})
.collect()
}
/// A ~90-line **Type-2** twin in the shape of the one verified by hand on
/// 2026-08-25: `mimir.rs:332-434` (`fn svg`) ↔ `viz/diagram.rs:222-325`
/// (`fn depgraph_svg`). Locals renamed (`g`→`snap`, `out`→`s`), comments
/// reworded — the differences the hand-read actually found.
fn type2_twin() -> (String, String) {
let a = format!(
"pub fn svg(g: &Snap, w: u32) -> String {{\n\
\x20 // Longest-path column assignment (sources at column 0), cycle-safe.\n\
{} String::new()\n}}\n",
body(80, "out", "g")
);
let b = format!(
"pub fn depgraph_svg(snap: &Snap, width: u32) -> String {{\n\
\x20 // Layered columns by longest-path depth. Cycle-safe: relaxation.\n\
{} String::new()\n}}\n",
body(80, "s", "snap")
);
(a, b)
}
/// **The ledger's shipping decision is wrong on its own fixture.**
///
/// The resume records *"skeppar med Type-2 AV"* — ship with normalisation
/// OFF, because it is 4.5× cheaper in volume. MEASURED here and on the real
/// tree: turning it off **loses the verified top find**. On nornir's own
/// `src/`, `mimir.rs:332-434 ↔ viz/diagram.rs:222-325` is reported as ONE
/// 103-line run with normalisation on, and collapses to a 36-line fragment
/// (`mimir.rs:344-379`) with it off — because the hand-read's own words are
/// not accurate: **85 of those 103 lines are identical, 18 differ**
/// (`g`→`snap`, `out`→`s`, two reworded comments, one retuned colour). It is
/// a Type-2 clone, not an identical one, so the cheap setting cannot see it
/// whole. Normalisation ON is therefore not a preference; it is the fixture.
#[test]
fn normalisation_off_loses_the_verified_top_find() {
let (a, b) = type2_twin();
let files = vec![("mimir.rs".to_string(), a), ("diagram.rs".to_string(), b)];
let on = detect(files.clone(), &SubcloneOptions::default());
let whole = on.groups.iter().any(|g| g.lines >= 80);
assert!(whole, "GREEN with normalisation: the twin is one long run: {:#?}", on.groups);
let off = SubcloneOptions { normalize_identifiers: false, ..Default::default() };
let r = detect(files, &off);
assert!(
!r.groups.iter().any(|g| g.lines >= 80),
"RED for the ledger's decision: normalisation OFF must NOT be able to state \
this twin whole — if it can, this guard has stopped guarding: {:#?}",
r.groups
);
assert!(
SubcloneOptions::default().normalize_identifiers,
"and so the DEFAULT stays ON: flipping it regresses the verified top find"
);
}
/// **The number a person sees is a FINDING, not a group.**
///
/// One duplicated region gets restated by several groups: each maximal
/// extension is maximal only for ITS seed pair, so the same lines come back
/// at several extents with several site sets, and R5's containment rule
/// cannot fold them (a 10-site group is not contained in a 7-site one).
/// Here: one long shared region in `a.rs`, partnered by `b.rs` over its
/// whole length and by `c.rs` over its tail. Two groups — one place to go.
#[test]
fn one_region_restated_by_two_groups_is_one_finding() {
let head = body(40, "head", "src");
let tail = body(40, "tail", "dst");
let a = format!("pub fn a(src: &Snap, dst: &Snap) -> u64 {{\n{head}{tail} 0\n}}\n");
let b = format!("pub fn b(src: &Snap, dst: &Snap) -> u64 {{\n{head}{tail} 1\n}}\n");
// `c` shares only the TAIL, behind a different prologue, so the
// extension from c's seeds stops earlier: a second, shorter group whose
// `a.rs` site sits INSIDE the first group's `a.rs` site.
let c = format!(
"pub fn c(dst: &Snap) -> u64 {{\n let z = dst.len();\n{tail} 2\n}}\n"
);
let files =
vec![("a.rs".to_string(), a), ("b.rs".to_string(), b), ("c.rs".to_string(), c)];
let r = detect(files, &SubcloneOptions::default());
assert!(
r.groups.len() >= 2,
"RED: the region really is restated by more than one group: {:#?}",
r.groups
);
assert_eq!(
r.findings.len(),
1,
"GREEN: overlapping regions are ONE thing to act on, not {}: {:#?}",
r.groups.len(),
r.findings
);
assert_eq!(r.findings[0].groups.len(), r.groups.len(), "every group is accounted for");
assert!(r.findings[0].files.iter().any(|f| f == "a.rs"));
}
/// A finding must never MERGE two unrelated duplications — the reduction is
/// only honest if the guard can go red on over-merging.
#[test]
fn two_unrelated_duplications_stay_two_findings() {
// Two runs with NO shared shape and no overlapping lines, kept apart by
// a wide gap of unshared filler so they cannot touch.
let one = body(40, "alpha", "left");
let two: String = (0..40)
.map(|i| match i % 4 {
0 => format!(" let beta_{i} = registry.lookup(\"k{i}\")?.weight;\n"),
1 => format!(" totals.entry(beta_{}).and_modify(|v| *v += {i}).or_default();\n", i - 1),
2 => format!(" if totals.len() % {} == 0 {{ registry.flush(); }}\n", i + 1),
_ => format!(" let _ = writeln!(sink, \"beta {{}} {{}}\", beta_{}, {i});\n", i - 2),
})
.collect();
// The filler between them must NOT be shared, or the two runs extend
// through it and become one run — which is a correct answer to a
// different question.
let gap_a: String =
(0..30).map(|i| format!(" let ga_{i} = {i}u64.wrapping_sub(3);\n")).collect();
let gap_b: String =
(0..30).map(|i| format!(" println!(\"{{}}\", {i} * 7usize);\n")).collect();
let a = format!(
"pub fn a1(left: &Snap) -> u64 {{\n{one} 0\n}}\n\
pub fn a_mid() -> u64 {{\n{gap_a} 1\n}}\n\
pub fn a2(registry: &Reg) -> u64 {{\n{two} 2\n}}\n"
);
let b = format!(
"pub fn b1(left: &Snap) -> u64 {{\n{one} 3\n}}\n\
pub fn b_mid() -> u64 {{\n{gap_b} 4\n}}\n\
pub fn b2(registry: &Reg) -> u64 {{\n{two} 5\n}}\n"
);
let r = detect(vec![("a.rs".into(), a), ("b.rs".into(), b)], &SubcloneOptions::default());
assert!(r.groups.len() >= 2, "two distinct runs: {:#?}", r.groups);
assert_eq!(
r.findings.len(),
2,
"two duplications that share no line must NOT be folded into one: {:#?}",
r.findings
);
}
/// **The other setting must be reachable without editing code.** No env
/// mutation: the reader is injected, so this is hermetic under `cargo test`'s
/// parallel threads (a `set_var` here would race every other test in the
/// binary).
#[test]
fn the_type2_switch_is_reachable_from_the_environment() {
let d = options_from_env_with(|_| None);
assert!(d.applied.is_empty(), "an unset environment changes nothing");
assert!(d.opts.normalize_identifiers, "and the default is the fixture-preserving one");
let off = options_from_env_with(|k| (k == ENV_NORMALIZE).then(|| "0".to_string()));
assert!(!off.opts.normalize_identifiers, "{ENV_NORMALIZE}=0 turns Type-2 off");
assert_eq!(off.applied, vec![ENV_NORMALIZE], "and says so");
let lines = options_from_env_with(|k| (k == ENV_MIN_LINES).then(|| "40".to_string()));
assert_eq!(lines.opts.min_run_lines, 40);
let floor = options_from_env_with(|k| (k == ENV_OVERLAP).then(|| "0.9".to_string()));
assert!((floor.opts.overlap_floor - 0.9).abs() < 1e-6);
}
/// A malformed value must be REFUSED and NAMED, never silently ignored —
/// a silently dropped knob is how `test_args()` lost its only caller.
#[test]
fn a_malformed_environment_value_is_named_not_swallowed() {
let bad = options_from_env_with(|k| (k == ENV_MIN_LINES).then(|| "twenty".to_string()));
assert_eq!(bad.opts.min_run_lines, SubcloneOptions::default().min_run_lines);
assert!(bad.applied.is_empty());
assert_eq!(bad.rejected.len(), 1, "the bad value is REPORTED");
assert!(bad.rejected[0].contains(ENV_MIN_LINES) && bad.rejected[0].contains("twenty"));
}
}