Module: Uniword::Diff::Semantic::ParagraphComparator

Defined in:
lib/uniword/diff/semantic/paragraph_comparator.rb

Overview

LCS-based paragraph comparator. Aligns old and new paragraph lists with a proper dynamic-programming LCS, classifies each aligned pair, and emits changes for any pair that isn't :unchanged.

Reuses the paragraph text via Paragraph#text.

Class Method Summary collapse

Class Method Details

.align(old_keys, new_keys) ⇒ Array<Array(Integer, Integer)>

DP LCS alignment of two arrays of fingerprints. Returns a list of [old_idx, new_idx] pairs:

- matching pair `[i, j]` when keys are equal
- `[i, nil]` when old[i] is removed
- `[nil, j]` when new[j] is added

Parameters:

  • old_keys (Array<String>)
  • new_keys (Array<String>)

Returns:

  • (Array<Array(Integer, Integer)>) 


47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 47

def align(old_keys, new_keys)
  lcs_pairs = lcs_match_pairs(old_keys, new_keys)
  pairs = []
  i = 0
  j = 0
  lcs_pairs.each do |mi, mj|
    while i < mi
      pairs << [i, nil]
      i += 1
    end
    while j < mj
      pairs << [nil, j]
      j += 1
    end
    pairs << [mi, mj]
    i = mi + 1
    j = mj + 1
  end
  while i < old_keys.length
    pairs << [i, nil]
    i += 1
  end
  while j < new_keys.length
    pairs << [nil, j]
    j += 1
  end
  pairs
end

.backtrack(dp, a, b, i, j) ⇒ Object

Backtrack through the DP table to recover matching pairs.



98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 98

def backtrack(dp, a, b, i, j)
  return [] if i.zero? || j.zero?

  if a[i - 1] == b[j - 1]
    backtrack(dp, a, b, i - 1, j - 1) << [i - 1, j - 1]
  elsif dp[i - 1][j] >= dp[i][j - 1]
    backtrack(dp, a, b, i - 1, j)
  else
    backtrack(dp, a, b, i, j - 1)
  end
end

.classify_modified(old_para, new_para, old_idx, new_idx) ⇒ Object

Classify a modified pair by what changed.



160
161
162
163
164
165
166
167
168
169
170
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 160

def classify_modified(old_para, new_para, old_idx, new_idx)
  modifier = modifier_for(old_para, new_para)
  Change.new(
    kind: :modified,
    modifier: modifier,
    old_index: old_idx,
    new_index: new_idx,
    description: "Paragraph #{old_idx + 1} -> #{new_idx + 1} " \
                 "(#{modifier})",
  )
end

.collapse_remove_add_pairs(alignment) ⇒ Array<Array(Integer, Integer)>

Collapse adjacent [i, nil], [nil, j] pairs into [i, j] modified pairs. Without this, text edits show as one remove

  • one add instead of one modification.

Parameters:

  • alignment (Array<Array(Integer, Integer)>)

Returns:

  • (Array<Array(Integer, Integer)>) 


136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 136

def collapse_remove_add_pairs(alignment)
  result = []
  i = 0
  while i < alignment.length
    curr = alignment[i]
    nxt = alignment[i + 1]
    if curr[0] && curr[1].nil? && nxt && nxt[0].nil? && nxt[1]
      result << [curr[0], nxt[1]]
      i += 2
    else
      result << curr
      i += 1
    end
  end
  result
end

.each_change(old_paras, new_paras) {|change| ... } ⇒ void

This method returns an undefined value.

Parameters:

Yield Parameters:



19
20
21
22
23
24
25
26
27
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 19

def each_change(old_paras, new_paras, &block)
  old_paras ||= []
  new_paras ||= []
  old_keys = old_paras.map { |p| fingerprint(p) }
  new_keys = new_paras.map { |p| fingerprint(p) }
  alignment = align(old_keys, new_keys)

  emit_changes(alignment, old_paras, new_paras, &block)
end

.emit_changes(alignment, old_paras, new_paras) ⇒ Object 



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 110

def emit_changes(alignment, old_paras, new_paras)
  collapsed = collapse_remove_add_pairs(alignment)
  collapsed.each do |old_idx, new_idx|
    case [old_idx.nil?, new_idx.nil?]
    when [true, false]
      yield Change.new(kind: :added, new_index: new_idx,
                       description: "Paragraph #{new_idx + 1} added")
    when [false, true]
      yield Change.new(kind: :removed, old_index: old_idx,
                       description: "Paragraph #{old_idx + 1} removed")
    when [false, false]
      next if identical?(old_paras[old_idx], new_paras[new_idx])

      yield classify_modified(old_paras[old_idx],
                              new_paras[new_idx],
                              old_idx, new_idx)
    end
  end
end

.fingerprint(paragraph) ⇒ String

Stable text fingerprint for one paragraph. Identical text produces identical fingerprints.

Parameters:

Returns:

  • (String) 


34
35
36
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 34

def fingerprint(paragraph)
  (paragraph&.text || "").to_s
end

.format_only_change?(old_xml, new_xml) ⇒ Boolean

Heuristic: a format-only change alters rPr but not run structure. True when removing all <w:rPr>...</w:rPr> blocks equalizes the XML.

Returns:

  • (Boolean) 


187
188
189
190
191
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 187

def format_only_change?(old_xml, new_xml)
  stripped_old = old_xml.gsub(%r{<w:rPr>.*?</w:rPr>}m, "")
  stripped_new = new_xml.gsub(%r{<w:rPr>.*?</w:rPr>}m, "")
  stripped_old == stripped_new
end

.identical?(old_para, new_para) ⇒ Boolean

Two paragraphs are identical when their full XML is byte- equal — same text AND same formatting AND same structure.

Returns:

  • (Boolean) 


155
156
157
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 155

def identical?(old_para, new_para)
  old_para.to_xml == new_para.to_xml
end

.lcs_match_pairs(a, b) ⇒ Array<Array(Integer, Integer)>

DP LCS: returns the list of matching (i, j) pairs in order.

Parameters:

  • a (Array<String>)
  • b (Array<String>)

Returns:

  • (Array<Array(Integer, Integer)>) 


81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 81

def lcs_match_pairs(a, b)
  n = a.length
  m = b.length
  dp = Array.new(n + 1) { Array.new(m + 1, 0) }
  (1..n).each do |i|
    (1..m).each do |j|
      dp[i][j] = if a[i - 1] == b[j - 1]
                   dp[i - 1][j - 1] + 1
                 else
                   [dp[i - 1][j], dp[i][j - 1]].max
                 end
    end
  end
  backtrack(dp, a, b, n, m)
end

.modifier_for(old_para, new_para) ⇒ Object

Decide what changed between two paragraphs with the same text but different XML.



174
175
176
177
178
179
180
181
182
 
# File 'lib/uniword/diff/semantic/paragraph_comparator.rb', line 174

def modifier_for(old_para, new_para)
  return :text if old_para.text != new_para.text

  old_xml = old_para.to_xml
  new_xml = new_para.to_xml
  return :format if format_only_change?(old_xml, new_xml)

  :structure
end