-
Notifications
You must be signed in to change notification settings - Fork 1
/
diff3.go
134 lines (112 loc) · 3.51 KB
/
diff3.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package diff3
import (
"fmt"
"strings"
"github.com/sergi/go-diff/diffmatchpatch"
)
const (
// Sep1 signifies the start of a conflict.
Sep1 = "<<<<<<<"
// Sep2 signifies the middle of a conflict.
Sep2 = "======="
// Sep3 signifies the end of a conflict.
Sep3 = ">>>>>>>"
)
// DiffMatchPatch contains the diff algorithm settings.
var DiffMatchPatch = diffmatchpatch.New()
// Merge implements the diff3 algorithm to merge two texts into a common base.
func Merge(textO, textA, textB string) string {
runesO, runesA, linesA := DiffMatchPatch.DiffLinesToRunes(textO, textA)
_, runesB, linesB := DiffMatchPatch.DiffLinesToRunes(textO, textB)
diffsA := DiffMatchPatch.DiffMainRunes(runesO, runesA, false)
diffsB := DiffMatchPatch.DiffMainRunes(runesO, runesB, false)
matchesA := matches(diffsA, runesA)
matchesB := matches(diffsB, runesB)
var result strings.Builder
indexO, indexA, indexB := 0, 0, 0
for {
i := nextMismatch(indexO, indexA, indexB, runesA, runesB, matchesA, matchesB)
o, a, b := 0, 0, 0
if i == 1 {
o, a, b = nextMatch(indexO, runesO, matchesA, matchesB)
} else if i > 1 {
o, a, b = indexO+i, indexA+i, indexB+i
}
if o == 0 || a == 0 || b == 0 {
break
}
chunk(indexO, indexA, indexB, o-1, a-1, b-1, runesO, runesA, runesB, linesA, linesB, &result)
indexO, indexA, indexB = o-1, a-1, b-1
}
chunk(indexO, indexA, indexB, len(runesO), len(runesA), len(runesB), runesO, runesA, runesB, linesA, linesB, &result)
return result.String()
}
// matches returns a map of the non-crossing matches.
func matches(diffs []diffmatchpatch.Diff, runes []rune) map[int]int {
matches := make(map[int]int)
for _, d := range diffs {
if d.Type != diffmatchpatch.DiffEqual {
continue
}
for _, r := range d.Text {
matches[int(r)] = indexOf(runes, r) + 1
}
}
return matches
}
// nextMismatch searches for the next index where a or b is not equal to o.
func nextMismatch(indexO, indexA, indexB int, runesA, runesB []rune, matchesA, matchesB map[int]int) int {
stop := min(len(runesA), len(runesB))
for i := 1; i <= stop; i++ {
a, okA := matchesA[indexO+i]
b, okB := matchesB[indexO+i]
if !okA || a != indexA+i || !okB || b != indexB+i {
return i
}
}
return stop
}
// nextMatch searches for the next index where a and b are equal to o.
func nextMatch(indexO int, runesO []rune, matchesA, matchesB map[int]int) (int, int, int) {
for o := indexO + 1; o <= len(runesO); o++ {
a, okA := matchesA[o]
b, okB := matchesB[o]
if okA && okB {
return o, a, b
}
}
return 0, 0, 0
}
// chunk merges the lines from o, a, and b into a single text.
func chunk(indexO, indexA, indexB, o, a, b int, runesO, runesA, runesB []rune, linesA, linesB []string, result *strings.Builder) {
chunkO := buildChunk(linesA, runesO[indexO:o])
chunkA := buildChunk(linesA, runesA[indexA:a])
chunkB := buildChunk(linesB, runesB[indexB:b])
switch {
case chunkA == chunkB:
fmt.Fprint(result, chunkO)
case chunkO == chunkA:
fmt.Fprint(result, chunkB)
case chunkO == chunkB:
fmt.Fprint(result, chunkA)
default:
fmt.Fprintf(result, "%s\n%s%s\n%s%s\n", Sep1, chunkA, Sep2, chunkB, Sep3)
}
}
// indexOf returns the index of the first occurance of the given value.
func indexOf(runes []rune, value rune) int {
for i, r := range runes {
if r == value {
return i
}
}
return -1
}
// buildChunk assembles the lines of the chunk into a string.
func buildChunk(lines []string, runes []rune) string {
var chunk strings.Builder
for _, r := range runes {
fmt.Fprint(&chunk, lines[int(r)])
}
return chunk.String()
}