Class: Scryer::DuplicateDetector

Inherits:
Object
  • Object
show all
Defined in:
lib/scryer/duplicate_detector.rb

Overview

Token-normalized near-duplicate detection across methods (see MethodExtractor for how a method's token stream is built and normalized — identifiers/literals become placeholders, keywords/operators stay literal, so a copy-pasted method with renamed variables still looks "the same shape" while structurally different code doesn't).

Approach: build a shingle set (sliding-window n-grams of the normalized token stream) per method, then compare methods pairwise via Jaccard similarity of their shingle sets, bucketing by token-count first so we don't bother comparing a 15-token method against a 200-token one. This is simpler than MinHash and fully correct (no approximation error) — fine for the method counts a typical Rails app has; a MinHash-based approximation would only be worth the complexity at codebases far larger than this tool is likely to run against in one pass.

Defined Under Namespace

Classes: DuplicateGroup, Entry

Constant Summary collapse

SHINGLE_SIZE =

A smaller shingle size is less disrupted by a single inserted/removed token (common in near-duplicates that were copy-pasted then tweaked) — each inserted token only breaks SHINGLE_SIZE consecutive shingles rather than a larger fraction of the total set, at some cost in precision (shorter shingles are individually less distinctive).

3
SIMILARITY_THRESHOLD = 
0.6
SIZE_BUCKET_RATIO =

only compare methods whose token counts are within +/-40% of each other

0.4

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(methods, threshold: SIMILARITY_THRESHOLD, kind: "method_duplicate") ⇒ DuplicateDetector

Returns a new instance of DuplicateDetector.



38
39
40
41
42
 
# File 'lib/scryer/duplicate_detector.rb', line 38

def initialize(methods, threshold: SIMILARITY_THRESHOLD, kind: "method_duplicate")
  @threshold = threshold
  @kind = kind
  @methods = methods.map { |m| Entry.new(m, shingles(m.token_stream)) }
end

Class Method Details

.call(methods, threshold: SIMILARITY_THRESHOLD, kind: "method_duplicate") ⇒ Object 



34
35
36
 
# File 'lib/scryer/duplicate_detector.rb', line 34

def self.call(methods, threshold: SIMILARITY_THRESHOLD, kind: "method_duplicate")
  new(methods, threshold: threshold, kind: kind).call
end

Instance Method Details

#call ⇒ Object 



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/scryer/duplicate_detector.rb', line 44

def call
  groups = []
  seen_pairs = 0

  @methods.combination(2).each do |a, b|
    next unless size_compatible?(a, b)

    seen_pairs += 1
    sim = jaccard(a.shingles, b.shingles)
    next if sim < @threshold

    merge_or_add(groups, a, b, sim)
  end

  groups
end