Skip to content

feat: type-3 fuzzy clone detection (near-miss blocks) #4

Closed

Description

@machado144

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 a detectExact(files, minTokens) function for the current type-1/2 path
  • services/detector.go: implement detectFuzzy(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: add minSimilarity float64 parameter to Detect()

Flags & options

  • flags.go: add --similarity flag (float, default 0.70)
  • services/scanner.go: add MinSimilarity float64 to ScanOptions, pass through to Detect
  • actions/scan.go: read --similarity flag and populate ScanOptions

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.0 disables 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.0 suppresses type-3 clone that would otherwise be found
  • integration/cli_test.go: JSON output has "type": "type-3" and similarity < 1.0

Performance

  • Benchmark detectFuzzy on a ~50k LOC codebase — must complete in < 10s
  • Mini-window inverted index must not cause O(n²) blowup on large files

Build & quality

  • make test passes
  • lefthook pre-commit passes
  • No regressions on type-1/2 tests

Activity

  1. added a commit that references this issue on Apr 2, 2026
  2. added a commit that references this issue on Apr 2, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      ⌂ 换网址