Module near_match 

Structural-mode near-match candidate generation: MinHash + LSH.

The exact-hash seed layer (crate::candidate) finds fragments whose structure is identical under the feature recipe — Type-1 and Type-2 clones. Type-3 clones differ: statements inserted, deleted or reordered, so no single hash matches end to end, but most of the two units’ structural fingerprints still coincide. This layer finds those units by set similarity.

Each unit becomes a shingle set — the union of its statement-window and subtree feature hashes. A MinHash signature estimates the Jaccard similarity of any two sets from a fixed-length vector, and Locality- Sensitive Hashing bands those signatures so that only unit pairs likely to be similar are ever examined, sidestepping the quadratic all-pairs compare.

LSH is probabilistic, so it is used only to propose pairs; every proposed pair must then clear two deterministic gates before it is emitted, which is also what keeps the output a pure function of the input:

• a length-ratio pre-filter drops pairs whose unit sizes differ by more than NearMatchConfig::max_length_ratio — a large and a small unit are not a Type-3 pair however their shingles happened to band;
• an estimated-Jaccard gate drops pairs whose signature similarity is below NearMatchConfig::min_estimated_jaccard, so a spurious band collision between dissimilar units never survives.

Candidate-explosion control matches the seed layer (AGENTS.md invariant 10): an LSH bucket larger than the posting cap is high-frequency structure and is dropped whole and counted, and a global pair budget bounds the distinct pairs examined. Buckets are processed smallest-first within each deterministic band; a pair colliding in multiple LSH bands is charged once, when it first enters the distinct candidate set. Once the ceiling fires, later buckets are not walked. Everything dropped is counted in NearMatchStats.

As in crate::candidate, the budget is spent a bucket at a time: a bucket it cannot hold entirely is left alone rather than sampled, because a set of units compared to each other only in part is what grouping reads as a set that disagrees. The posting cap bounds the one bucket that must be materialised to identify its previously unseen pairs.

This design deliberately subsumes the separate size-bucket and prefix-filtering prefilters: LSH banding partitions the search, and the length-ratio gate bounds size divergence, which together already bound the candidate set without a second size index. Signatures are held in one flat buffer and capped before indexing; each LSH band builds and discards its own posting map, so the index itself cannot grow with every band at once.

Structs

NearMatchConfig

Tuning for near-match candidate generation. Defaults are provisional and calibrated against the corpus with the funnel measurement.

NearMatchNearMiss

One size-compatible LSH proposal whose estimate fell just below the primary candidate threshold.

NearMatchPair

A near-match candidate: two units whose structural shingle sets overlap enough to be a possible Type-3 clone. Canonical: a < b.

NearMatchSet

The near-match stage’s output: candidate unit pairs plus funnel statistics.

NearMatchStats

Counters describing what near-match generation saw and dropped.

Constants

DEFAULT_BANDS

Default number of LSH bands; rows per band is num_hashes / bands.

DEFAULT_MAX_LENGTH_RATIO

Default largest unit-size ratio a pair may span.

DEFAULT_MAX_SIGNED_UNITS

Default maximum number of units admitted to the near-match signature stage.

DEFAULT_MIN_ESTIMATED_JACCARD

Default smallest estimated Jaccard a pair must reach to be emitted. Type-3 edits routinely land here.

DEFAULT_MIN_SHINGLES

Default smallest shingle-set size a unit needs to be signed. Below this a MinHash estimate is too noisy to trust.

DEFAULT_NEAR_MISS_CAP

Default global cap on retained near-match diagnostics.

DEFAULT_NEAR_MISS_DELTA

Default width of the diagnostic band directly below the candidate gate.

DEFAULT_NUM_HASHES

Default number of MinHash permutations per signature.

DEFAULT_PAIR_BUDGET

Default global candidate-pair upper bound.

DEFAULT_POSTING_CAP

Default LSH-bucket cap; larger buckets are high-frequency and dropped.

Functions

generate

Generate near-match candidate unit pairs across files.