Repository navigation
Description
Summary
Type-1 and type-2 detection only catches exact structural matches. Real codebases are full of near-miss clones: two blocks that are 80% identical with a statement added, removed, or swapped. These are the clones most worth refactoring — and the ones current detection misses entirely.
This issue implements type-3 detection using a mini-window overlap algorithm: split each candidate block into smaller sub-windows, hash them, and report a clone when the Jaccard similarity of those sub-windows meets a configurable threshold (default 0.70).
Algorithm
For each pair of blocks (A, B) of similar token count (within 30%):
1. Split A into mini-windows of size ceil(minTokens / 3)
2. Split B into mini-windows of same size
3. Compute set intersection: hashes(A) ∩ hashes(B)
4. Jaccard = |intersection| / |union|
5. If Jaccard >= threshold AND Jaccard < 1.0 → type-3 clone
(exact matches already handled by type-1/2 path)
Candidate pairing is done via an inverted index on mini-window hashes — only pairs sharing ≥1 mini-window are evaluated, keeping complexity manageable.
New flag
--similarity float minimum similarity threshold for type-3 detection (default: 0.70, range: 0.50–1.00)
set to 1.0 to disable type-3 detection entirely
Similarity score in output
Type-3 clones carry the computed Jaccard similarity (e.g. 0.82). Type-1/2 clones carry 1.0 (they already do after issue #3).
Implementation checklist
Detection
-
services/detector.go: extract adetectExact(files, minTokens)function for the current type-1/2 path -
services/detector.go: implementdetectFuzzy(files, minTokens, threshold float64) []domain.Clone- Build mini-window hash sets per file position
- Build inverted index: mini-hash → []globalPos
- For each pair of positions sharing ≥1 mini-hash, compute Jaccard
- If Jaccard ≥ threshold and < 1.0, emit a type-3 Clone with computed similarity
- Deduplicate: do not re-report blocks already found by exact path
-
services/detector.go:Detect()calls both paths and merges results, deduplicating by overlapping line ranges -
services/detector.go: addminSimilarity float64parameter toDetect()
Flags & options
-
flags.go: add--similarityflag (float, default0.70) -
services/scanner.go: addMinSimilarity float64toScanOptions, pass through toDetect -
actions/scan.go: read--similarityflag and populateScanOptions
Tests
-
services/detector_test.go: type-3: two functions identical except one extra statement → detected with similarity < 1.0 -
services/detector_test.go: type-3: two functions with one statement swapped → detected -
services/detector_test.go: type-3: completely different code → NOT detected -
services/detector_test.go:--similarity 1.0disables type-3 (only exact matches returned) -
services/detector_test.go: similarity score is in range [threshold, 1.0) for type-3 results -
services/scanner_test.go: near-miss scan returns type-3 clone -
integration/cli_test.go: CLI detects near-miss block with default similarity -
integration/cli_test.go:--similarity 1.0suppresses type-3 clone that would otherwise be found -
integration/cli_test.go: JSON output has"type": "type-3"andsimilarity< 1.0
Performance
- Benchmark
detectFuzzyon a ~50k LOC codebase — must complete in < 10s - Mini-window inverted index must not cause O(n²) blowup on large files
Build & quality
-
make testpasses -
lefthookpre-commit passes - No regressions on type-1/2 tests
Activity
feat(#4): type-3 fuzzy clone detection with mini-window Jaccard simil…
feat(#4): type-3 fuzzy clone detection with mini-window Jaccard simil…