Class: Canon::TreeDiff::Matchers::UniversalMatcher

Inherits:
Object
  • Object
show all
Defined in:
lib/canon/tree_diff/matchers/universal_matcher.rb

Overview

UniversalMatcher orchestrates the complete matching process by combining hash-based, similarity-based, and structural propagation matching strategies.

This is the main entry point for tree matching and follows a multi-phase pipeline approach:

Phase 1: Hash Matching (XyDiff BULD)

- Exact signature matching for identical subtrees
- O(n log n) complexity via priority queue
- Processes heaviest nodes first

Phase 2: Similarity Matching (JATS-diff)

- Content-based similarity via Jaccard index
- Configurable threshold (default 0.95)
- Groups by signature for efficiency

Phase 3: Structural Propagation (XyDiff)

- Bottom-up: match parents of matched children
- Top-down: match children of matched parents
- Adaptive propagation depth based on weight

Examples:

Basic usage

matcher = UniversalMatcher.new
matching = matcher.match(tree1, tree2)
puts "Matched #{matching.size} nodes"

With custom options

matcher = UniversalMatcher.new(
  similarity_threshold: 0.9,
  enable_propagation: false
)
matching = matcher.match(tree1, tree2)

Constant Summary collapse

DEFAULT_OPTIONS =

Default options for the matching process

{
  # Minimum Jaccard similarity for content matching
  similarity_threshold: 0.95,

  # Enable hash-based exact matching
  enable_hash_matching: true,

  # Enable similarity-based matching
  enable_similarity_matching: true,

  # Enable structural propagation
  enable_propagation: true,

  # Maximum propagation depth (nil = adaptive)
  max_propagation_depth: nil,

  # Minimum weight for propagation
  min_propagation_weight: 2.0,
}.freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}) ⇒ UniversalMatcher

Initialize a new UniversalMatcher

Parameters:

  • options (Hash) (defaults to: {}) —

    Configuration options

Options Hash (options):

  • :similarity_threshold (Float) — default: 0.95 —

    Minimum similarity for content matching

  • :enable_hash_matching (Boolean) — default: true —

    Enable hash-based exact matching

  • :enable_similarity_matching (Boolean) — default: true —

    Enable similarity-based matching

  • :enable_propagation (Boolean) — default: true —

    Enable structural propagation

  • :max_propagation_depth (Integer, nil) — default: nil —

    Maximum propagation depth (nil = adaptive)

  • :min_propagation_weight (Float) — default: 2.0 —

    Minimum weight for propagation



78
79
80
81
 
# File 'lib/canon/tree_diff/matchers/universal_matcher.rb', line 78

def initialize(options = {})
  @options = DEFAULT_OPTIONS.merge(options)
  @statistics = {}
end

Instance Attribute Details

#options ⇒ Object (readonly)

Returns the value of attribute options.



61
62
63
 
# File 'lib/canon/tree_diff/matchers/universal_matcher.rb', line 61

def options
  @options
end

#statistics ⇒ Object (readonly)

Returns the value of attribute statistics.



61
62
63
 
# File 'lib/canon/tree_diff/matchers/universal_matcher.rb', line 61

def statistics
  @statistics
end

Instance Method Details

#match(tree1, tree2) ⇒ Matching

Match two trees and return a Matching object

Parameters:

  • tree1 (TreeNode) —

    First tree root

  • tree2 (TreeNode) —

    Second tree root

Returns:

  • (Matching) —

    Matching object with all matched pairs



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/canon/tree_diff/matchers/universal_matcher.rb', line 88

def match(tree1, tree2)
  reset_statistics(tree1, tree2)

  matching = Core::Matching.new

  # Phase 1: Hash-based exact matching
  if @options[:enable_hash_matching]
    hash_matching_phase(tree1, tree2, matching)
  end

  # Phase 2: Similarity-based matching
  if @options[:enable_similarity_matching]
    similarity_matching_phase(tree1, tree2, matching)
  end

  # Phase 3: Structural propagation
  if @options[:enable_propagation]
    propagation_phase(tree1, tree2, matching)
  end

  finalize_statistics(matching)
  matching
end