main
range_diff.go
Eric Bower
·
2026-02-25
1package patchbin
2
3import (
4 "fmt"
5 "math"
6 "sort"
7 "strings"
8
9 "github.com/bluekeyes/go-gitdiff/gitdiff"
10 ha "github.com/oddg/hungarian-algorithm"
11)
12
13var (
14 COST_MAX = 65536
15 RANGE_DIFF_CREATION_FACTOR_DEFAULT = 60
16)
17
18// RangeDiffOutput represents a single commit comparison entry in the range diff.
19type RangeDiffOutput struct {
20 Header *RangeDiffHeader
21 Order int
22 Files []*RangeDiffFile
23 Type string // "rm", "add", "equal", "changed"
24}
25
26// RangeDiffFile represents a file-level change between two matched commits.
27type RangeDiffFile struct {
28 OldName string
29 NewName string
30 Type string // "added", "removed", "changed"
31}
32
33// RangeDiffHeader is a header combining old and new commit pairs.
34type RangeDiffHeader struct {
35 OldIdx int
36 OldSha string
37 OldAuthorName string
38 OldAuthorEmail string
39 OldTitle string
40 OldBody string
41 NewIdx int
42 NewSha string
43 NewAuthorName string
44 NewAuthorEmail string
45 NewTitle string
46 NewBody string
47 Title string
48 ContentEqual bool
49 AuthorChanged bool
50 TitleChanged bool
51 BodyChanged bool
52}
53
54// NewRangeDiffHeader creates a header from two patch ranges.
55func NewRangeDiffHeader(a, b *Patch, aIndex, bIndex int) *RangeDiffHeader {
56 hdr := &RangeDiffHeader{}
57 if a == nil {
58 hdr.NewIdx = bIndex
59 hdr.NewSha = b.CommitSha
60 hdr.NewAuthorName = b.AuthorName
61 hdr.NewAuthorEmail = b.AuthorEmail
62 hdr.NewTitle = b.Title
63 hdr.NewBody = b.Body
64 hdr.Title = b.Title
65 return hdr
66 }
67 if b == nil {
68 hdr.OldIdx = aIndex
69 hdr.OldSha = a.CommitSha
70 hdr.OldAuthorName = a.AuthorName
71 hdr.OldAuthorEmail = a.AuthorEmail
72 hdr.OldTitle = a.Title
73 hdr.OldBody = a.Body
74 hdr.Title = a.Title
75 return hdr
76 }
77
78 hdr.OldIdx = aIndex
79 hdr.NewIdx = bIndex
80 hdr.OldSha = a.CommitSha
81 hdr.NewSha = b.CommitSha
82 hdr.OldAuthorName = a.AuthorName
83 hdr.OldAuthorEmail = a.AuthorEmail
84 hdr.OldTitle = a.Title
85 hdr.OldBody = a.Body
86 hdr.NewAuthorName = b.AuthorName
87 hdr.NewAuthorEmail = b.AuthorEmail
88 hdr.NewTitle = b.Title
89 hdr.NewBody = b.Body
90
91 // Check what changed
92 hdr.AuthorChanged = a.AuthorName != b.AuthorName || a.AuthorEmail != b.AuthorEmail
93 hdr.TitleChanged = a.Title != b.Title
94 hdr.BodyChanged = a.Body != b.Body
95
96 if a.ContentSha == b.ContentSha {
97 hdr.Title = a.Title
98 hdr.ContentEqual = true
99 } else {
100 hdr.Title = b.Title
101 }
102
103 return hdr
104}
105
106func (hdr *RangeDiffHeader) String() string {
107 if hdr.OldIdx == 0 {
108 return fmt.Sprintf("-: ------- > %d: %s %s\n", hdr.NewIdx, truncateSha(hdr.NewSha), hdr.Title)
109 }
110 if hdr.NewIdx == 0 {
111 return fmt.Sprintf("%d: %s < -: ------- %s\n", hdr.OldIdx, truncateSha(hdr.OldSha), hdr.Title)
112 }
113 if hdr.ContentEqual {
114 return fmt.Sprintf(
115 "%d: %s = %d: %s %s\n",
116 hdr.OldIdx, truncateSha(hdr.OldSha),
117 hdr.NewIdx, truncateSha(hdr.NewSha),
118 hdr.Title,
119 )
120 }
121 return fmt.Sprintf(
122 "%d: %s ! %d: %s %s\n",
123 hdr.OldIdx, truncateSha(hdr.OldSha),
124 hdr.NewIdx, truncateSha(hdr.NewSha),
125 hdr.Title,
126 )
127}
128
129// RangeDiff compares two patchsets and returns commit-level changes.
130func RangeDiff(a []*Patch, b []*Patch) []*RangeDiffOutput {
131 aPatches := make([]*patchEntry, len(a))
132 for i, p := range a {
133 aPatches[i] = &patchEntry{Patch: p, Matching: -1, Size: patchSize(p)}
134 }
135 bPatches := make([]*patchEntry, len(b))
136 for i, p := range b {
137 bPatches[i] = &patchEntry{Patch: p, Matching: -1, Size: patchSize(p)}
138 }
139
140 findExactMatches(aPatches, bPatches)
141 getCorrespondences(aPatches, bPatches, RANGE_DIFF_CREATION_FACTOR_DEFAULT)
142 return buildOutput(aPatches, bPatches)
143}
144
145// patchEntry wraps a Patch with matching state for the algorithm.
146type patchEntry struct {
147 *Patch
148 Matching int
149 Size int
150}
151
152// patchSize returns a rough size metric for a patch (used for matching cost).
153func patchSize(p *Patch) int {
154 return len(p.RawText)
155}
156
157// buildOutput constructs the final range diff output from matched patches.
158func buildOutput(a []*patchEntry, b []*patchEntry) []*RangeDiffOutput {
159 outputs := []*RangeDiffOutput{}
160
161 // Removed commits (in A but not matched in B)
162 for i, patchA := range a {
163 if patchA.Matching == -1 {
164 hdr := NewRangeDiffHeader(patchA.Patch, nil, i+1, -1)
165 files := filesRemoved(patchA.Patch)
166 outputs = append(outputs, &RangeDiffOutput{
167 Header: hdr,
168 Type: "rm",
169 Order: i + 1,
170 Files: files,
171 })
172 }
173 }
174
175 // Added or changed commits (from B side)
176 for j, entryB := range b {
177 if entryB.Matching == -1 {
178 // Added commit (in B but not matched in A)
179 hdr := NewRangeDiffHeader(nil, entryB.Patch, -1, j+1)
180 files := filesAdded(entryB.Patch)
181 outputs = append(outputs, &RangeDiffOutput{
182 Header: hdr,
183 Type: "add",
184 Order: j + 1,
185 Files: files,
186 })
187 continue
188 }
189
190 entryA := a[entryB.Matching]
191 if entryB.ContentSha == entryA.ContentSha {
192 // Equal commits
193 hdr := NewRangeDiffHeader(entryA.Patch, entryB.Patch, entryB.Matching+1, entryA.Matching+1)
194 outputs = append(outputs, &RangeDiffOutput{
195 Header: hdr,
196 Type: "equal",
197 Order: entryA.Matching + 1,
198 })
199 } else {
200 // Changed commits
201 hdr := NewRangeDiffHeader(entryA.Patch, entryB.Patch, entryB.Matching+1, entryA.Matching+1)
202 files := filesChanged(entryA.Patch, entryB.Patch)
203 outputs = append(outputs, &RangeDiffOutput{
204 Order: entryA.Matching + 1,
205 Header: hdr,
206 Files: files,
207 Type: "changed",
208 })
209 }
210 }
211
212 sort.Slice(outputs, func(i, j int) bool {
213 return outputs[i].Order < outputs[j].Order
214 })
215 return outputs
216}
217
218// fileContent extracts the diff content from a file for comparison.
219func fileContent(f *gitdiff.File) string {
220 var buf strings.Builder
221 for _, frag := range f.TextFragments {
222 for _, line := range frag.Lines {
223 buf.WriteString(line.String())
224 }
225 }
226 return buf.String()
227}
228
229// filesAdded returns a list of files added in the given patch.
230func filesAdded(p *Patch) []*RangeDiffFile {
231 files := []*RangeDiffFile{}
232 for _, f := range p.Files {
233 files = append(files, &RangeDiffFile{
234 NewName: f.NewName,
235 OldName: f.OldName,
236 Type: "added",
237 })
238 }
239 return files
240}
241
242// filesRemoved returns a list of files removed from the given patch.
243func filesRemoved(p *Patch) []*RangeDiffFile {
244 files := []*RangeDiffFile{}
245 for _, f := range p.Files {
246 files = append(files, &RangeDiffFile{
247 NewName: f.NewName,
248 OldName: f.OldName,
249 Type: "removed",
250 })
251 }
252 return files
253}
254
255// filesChanged returns a list of files that were added, removed, or changed
256// between two matched patches.
257func filesChanged(oldPatch, newPatch *Patch) []*RangeDiffFile {
258 files := []*RangeDiffFile{}
259
260 // Build lookup maps by new file name
261 oldFiles := map[string]*gitdiff.File{}
262 for _, f := range oldPatch.Files {
263 oldFiles[f.NewName] = f
264 }
265 newFiles := map[string]*gitdiff.File{}
266 for _, f := range newPatch.Files {
267 newFiles[f.NewName] = f
268 }
269
270 // Find changed and removed files
271 for name, oldFile := range oldFiles {
272 newFile, ok := newFiles[name]
273 if !ok {
274 // File removed
275 files = append(files, &RangeDiffFile{
276 OldName: oldFile.OldName,
277 Type: "removed",
278 })
279 } else if fileContent(oldFile) != fileContent(newFile) {
280 // File changed
281 files = append(files, &RangeDiffFile{
282 OldName: oldFile.OldName,
283 NewName: newFile.NewName,
284 Type: "changed",
285 })
286 }
287 }
288
289 // Find added files
290 for name, newFile := range newFiles {
291 if _, ok := oldFiles[name]; !ok {
292 files = append(files, &RangeDiffFile{
293 NewName: newFile.NewName,
294 OldName: newFile.OldName,
295 Type: "added",
296 })
297 }
298 }
299
300 // Sort for deterministic output
301 sort.Slice(files, func(i, j int) bool {
302 return files[i].NewName < files[j].NewName
303 })
304 return files
305}
306
307// RangeDiffToStr returns a simple string representation of the range diff.
308func RangeDiffToStr(diffs []*RangeDiffOutput) string {
309 out := ""
310 for _, diff := range diffs {
311 out += diff.Header.String()
312 for _, f := range diff.Files {
313 name := f.NewName
314 if name == "" {
315 name = f.OldName
316 }
317 switch f.Type {
318 case "added":
319 out += " + " + name + "\n"
320 case "removed":
321 out += " - " + name + "\n"
322 case "changed":
323 out += " ~ " + name + "\n"
324 }
325 }
326 }
327 return out
328}
329
330// --- Matching algorithm (unchanged) ---
331
332func findExactMatches(a, b []*patchEntry) {
333 for i, entryA := range a {
334 for j, entryB := range b {
335 if entryA.ContentSha == entryB.ContentSha {
336 a[i].Matching = j
337 b[j].Matching = i
338 }
339 }
340 }
341}
342
343func createMatrix(rows, cols int) [][]int {
344 mat := make([][]int, rows)
345 for i := range mat {
346 mat[i] = make([]int, cols)
347 }
348 return mat
349}
350
351func getCorrespondences(a, b []*patchEntry, creationFactor int) {
352 n := len(a) + len(b)
353 cost := createMatrix(n, n)
354
355 for i, entryA := range a {
356 for j, entryB := range b {
357 var c int
358 if entryA.Matching == j {
359 c = 0
360 } else if entryA.Matching == -1 && entryB.Matching == -1 {
361 c = absDiff(entryA.Size, entryB.Size)
362 } else {
363 c = COST_MAX
364 }
365 cost[i][j] = c
366 }
367 }
368
369 for j, entryB := range b {
370 creationCost := (entryB.Size * creationFactor) / 100
371 if entryB.Matching >= 0 {
372 creationCost = math.MaxInt32
373 }
374 for i := len(a); i < n; i++ {
375 cost[i][j] = creationCost
376 }
377 }
378
379 for i := len(a); i < n; i++ {
380 for j := len(b); j < n; j++ {
381 cost[i][j] = 0
382 }
383 }
384
385 assignment, _ := ha.Solve(cost)
386 for i := range a {
387 j := assignment[i]
388 if j >= 0 && j < len(b) {
389 a[i].Matching = j
390 b[j].Matching = i
391 }
392 }
393}
394
395func absDiff(a, b int) int {
396 if a > b {
397 return a - b
398 }
399 return b - a
400}