# Design notes

## Pipeline

1. **Walk.** The [`ignore`](https://crates.io/crates/ignore) crate
   provides gitignore-aware traversal. Directories that are never worth
   scanning are excluded even when not gitignored: `node_modules/`,
   `vendor/`, `third_party/`, `dist/`, `build/`, `target/`, virtualenvs.
   Generated files are skipped by marker (`@generated`, `DO NOT EDIT`,
   `Code generated by`) and by pattern (`*.pb.go`, `*_pb2.py`,
   `*.min.js`, `*.d.ts`). Minified files are detected by line length.
   `--no-default-excludes` disables all of this.

2. **Extract.** Each file is parsed with tree-sitter. A query per
   language captures functions and methods; the *body* is the unit of
   comparison, so imports, signatures and license headers can never
   participate in a match.

3. **Normalize.** Leaf tokens of the body are mapped to a `u16` stream:
   identifiers to one sentinel, string/char literals to another
   (consecutive literal parts collapsed), numbers to a third, comments
   dropped. Everything else keeps its grammar kind id. Two functions
   that differ only in names and literals (type-2 clones) now have
   identical streams; functions that differ in operators or control
   flow do not.

4. **Fingerprint.** k-grams of k=10 tokens are hashed with a
   Rabin-Karp rolling hash, finalized with splitmix64, and selected by
   robust winnowing with window w=8 (Schleimer, Wilkerson & Aiken,
   SIGMOD 2003). Properties:
   - any shared run of at least w+k−1 = 17 normalized tokens yields at
     least one shared fingerprint (the guarantee threshold);
   - no match shorter than k=10 tokens is possible (the noise
     threshold).
   Both are asserted by tests, including a property test that plants
   common runs at arbitrary alignments.

5. **Match.** An inverted index maps fingerprint to functions, so
   candidate pairs come from shared fingerprints and there is no O(n²)
   all-pairs pass. Fingerprints shared by more than max(100, 0.5% of
   functions) are culled: at that frequency they are language idiom
   (Go's `if err != nil` ladders), not duplication. Culling is symmetric,
   so Jaccard stays unbiased. Similarity is exact Jaccard over distinct
   fingerprint sets, computed from posting-list intersection counts.
   Pairs at or above the threshold (0.80 for scan, 0.85 for check) are
   grouped with union-find.

6. **Suppress.** A cluster whose members all sit inside members of
   another cluster is dropped; an inner closure duplicated only because
   its enclosing function is duplicated would otherwise double-count.
   Functions are compared only within the same language.

## Slop score

The percentage of significant lines you could delete if every duplicate
cluster kept only one copy. Significant lines are non-blank,
non-comment-only lines. The largest member of each cluster is exempt.
Test-only clusters are excluded by default, since table-driven tests are
repetitive by design; they are still shown, labeled `[tests, not
scored]`. Grade buckets (A < 3%, B < 6%, C < 10%, D < 15%, F ≥ 15%) were
calibrated against express, gin, tokio, fastapi and vscode, which all
land in A.

The score deliberately makes no claim about authorship. dupehound cannot
know whether a human or a model wrote a duplicate, so it doesn't say.

## history

Commits are taken from `git log --first-parent`, bucketed by month (last
commit per month, downsampled evenly to at most 36 snapshots). File
blobs are read through a single long-lived `git cat-file --batch`
subprocess, never via checkout. Fingerprints are cached by blob SHA:
month to month most blobs are unchanged, so each distinct blob is parsed
once across the whole run, and a 36-snapshot history costs a few times
one scan.

The headline is conservative. Growth is reported against the minimum of
a 3-point moving average; if the early series is effectively zero, the
phrasing switches to "went from ~0 to X% since DATE" rather than
fabricating a ratio; if the series is flat, it says so.

## check

The index is built from the base revision (the merge-base for `--diff
REV`, otherwise HEAD), so nothing a change adds can pollute it. Only
functions whose lines intersect changed hunks are probed. Two
suppressions handle the classic false alarms:

- *in-place edit*: the best match is the same function (same file, same
  name) at the base revision;
- *move*: the matched original's file also changed and the original no
  longer exists in its new version.

## Limits

Function-level granularity only: a duplicated 30-line block inside two
otherwise different functions is not reported. Jaccard penalizes a small
function copied into a much larger one (containment matching is on the
roadmap). Seven languages at present.
