Debian Codegraph @

internal/diff/myers/diff.go

raw
1 // Copyright 2019 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 // This code is a modified copy of code in gopls.
6 // It's not as efficient as it could be, it allocates way too much, the API is sloppy.
7 // But it's only used to print failed tests, so we don't care.
8
9 package myers
10
11 import (
12 "fmt"
13 "strings"
14 )
15
16 // OpKind is used to denote the type of operation a line represents.
17 type OpKind int
18
19 const (
20 // Delete is the operation kind for a line that is present in the input
21 // but not in the output.
22 Delete OpKind = iota
23 // Insert is the operation kind for a line that is new in the output.
24 Insert
25 // Equal is the operation kind for a line that is the same in the input and
26 // output, often used to provide context around edited lines.
27 Equal
28 )
29
30 // String returns a human readable representation of an OpKind. It is not
31 // intended for machine processing.
32 func (k OpKind) String() string {
33 switch k {
34 case Delete:
35 return "delete"
36 case Insert:
37 return "insert"
38 case Equal:
39 return "equal"
40 default:
41 panic("unknown operation kind")
42 }
43 }
44
45 // Sources:
46 // https://blog.jcoglan.com/2017/02/17/the-myers-diff-algorithm-part-3/
47 // https://www.codeproject.com/Articles/42279/%2FArticles%2F42279%2FInvestigating-Myers-diff-algorithm-Part-1-of-2
48
49 func ComputeEdits(before, after string) []*operation {
50 ops := operations(splitLines(before), splitLines(after))
51 return ops
52 }
53
54 type operation struct {
55 Kind OpKind
56 Content []string // content from b
57 I1, I2 int // indices of the line in a
58 J1 int // indices of the line in b, J2 implied by len(Content)
59 }
60
61 func (op *operation) String() string {
62 var prefix string
63 switch op.Kind {
64 case Delete:
65 prefix = "-"
66 case Insert:
67 prefix = "+"
68 case Equal:
69 prefix = " "
70 }
71 var out strings.Builder
72 for _, line := range op.Content {
73 out.WriteString(fmt.Sprintf("%s%s", prefix, line))
74 }
75 return out.String()
76 }
77
78 // operations returns the list of operations to convert a into b, consolidating
79 // operations for multiple lines and not including equal lines.
80 func operations(a, b []string) []*operation {
81 if len(a) == 0 && len(b) == 0 {
82 return nil
83 }
84
85 trace, offset := shortestEditSequence(a, b)
86 snakes := backtrack(trace, len(a), len(b), offset)
87
88 M, N := len(a), len(b)
89
90 var i int
91 solution := make([]*operation, len(a)+len(b))
92
93 add := func(op *operation, i2, j2 int) {
94 if op == nil {
95 return
96 }
97 op.I2 = i2
98 switch op.Kind {
99 case Insert:
100 op.Content = b[op.J1:j2]
101 case Delete:
102 op.Content = a[op.I1:op.I2]
103 case Equal:
104 op.Content = a[op.I1:op.I2]
105 }
106 solution[i] = op
107 i++
108 }
109 x, y := 0, 0
110 for _, snake := range snakes {
111 if len(snake) < 2 {
112 continue
113 }
114 var op *operation
115 // delete (horizontal)
116 for snake[0]-snake[1] > x-y {
117 if op == nil {
118 op = &operation{
119 Kind: Delete,
120 I1: x,
121 J1: y,
122 }
123 }
124 x++
125 if x == M {
126 break
127 }
128 }
129 add(op, x, y)
130 op = nil
131 // insert (vertical)
132 for snake[0]-snake[1] < x-y {
133 if op == nil {
134 op = &operation{
135 Kind: Insert,
136 I1: x,
137 J1: y,
138 }
139 }
140 y++
141 }
142 add(op, x, y)
143 op = nil
144 // equal (diagonal)
145 for x < snake[0] {
146 if op == nil {
147 op = &operation{
148 Kind: Equal,
149 I1: x,
150 J1: y,
151 }
152 }
153 x++
154 y++
155 }
156 add(op, x, y)
157 if x >= M && y >= N {
158 break
159 }
160 }
161 return solution[:i]
162 }
163
164 // backtrack uses the trace for the edit sequence computation and returns the
165 // "snakes" that make up the solution. A "snake" is a single deletion or
166 // insertion followed by zero or diagonals.
167 func backtrack(trace [][]int, x, y, offset int) [][]int {
168 snakes := make([][]int, len(trace))
169 d := len(trace) - 1
170 for ; x > 0 && y > 0 && d > 0; d-- {
171 V := trace[d]
172 if len(V) == 0 {
173 continue
174 }
175 snakes[d] = []int{x, y}
176
177 k := x - y
178
179 var kPrev int
180 if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
181 kPrev = k + 1
182 } else {
183 kPrev = k - 1
184 }
185
186 x = V[kPrev+offset]
187 y = x - kPrev
188 }
189 if x < 0 || y < 0 {
190 return snakes
191 }
192 snakes[d] = []int{x, y}
193 return snakes
194 }
195
196 // shortestEditSequence returns the shortest edit sequence that converts a into b.
197 func shortestEditSequence(a, b []string) ([][]int, int) {
198 M, N := len(a), len(b)
199 V := make([]int, 2*(N+M)+1)
200 offset := N + M
201 trace := make([][]int, N+M+1)
202
203 // Iterate through the maximum possible length of the SES (N+M).
204 for d := 0; d <= N+M; d++ {
205 copyV := make([]int, len(V))
206 // k lines are represented by the equation y = x - k. We move in
207 // increments of 2 because end points for even d are on even k lines.
208 for k := -d; k <= d; k += 2 {
209 // At each point, we either go down or to the right. We go down if
210 // k == -d, and we go to the right if k == d. We also prioritize
211 // the maximum x value, because we prefer deletions to insertions.
212 var x int
213 if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
214 x = V[k+1+offset] // down
215 } else {
216 x = V[k-1+offset] + 1 // right
217 }
218
219 y := x - k
220
221 // Diagonal moves while we have equal contents.
222 for x < M && y < N && a[x] == b[y] {
223 x++
224 y++
225 }
226
227 V[k+offset] = x
228
229 // Return if we've exceeded the maximum values.
230 if x == M && y == N {
231 // Makes sure to save the state of the array before returning.
232 copy(copyV, V)
233 trace[d] = copyV
234 return trace, offset
235 }
236 }
237
238 // Save the state of the array.
239 copy(copyV, V)
240 trace[d] = copyV
241 }
242 return nil, 0
243 }
244
245 func splitLines(text string) []string {
246 lines := strings.SplitAfter(text, "\n")
247 if lines[len(lines)-1] == "" {
248 lines = lines[:len(lines)-1]
249 }
250 return lines
251 }