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.
5 // Package myers implements the Myers diff algorithm.
11 "golang.org/x/tools/internal/lsp/diff"
12 "golang.org/x/tools/internal/span"
16 // https://blog.jcoglan.com/2017/02/17/the-myers-diff-algorithm-part-3/
17 // https://www.codeproject.com/Articles/42279/%2FArticles%2F42279%2FInvestigating-Myers-diff-algorithm-Part-1-of-2
19 func ComputeEdits(uri span.URI, before, after string) []diff.TextEdit {
20 ops := operations(splitLines(before), splitLines(after))
21 edits := make([]diff.TextEdit, 0, len(ops))
22 for _, op := range ops {
23 s := span.New(uri, span.NewPoint(op.I1+1, 1, 0), span.NewPoint(op.I2+1, 1, 0))
26 // Delete: unformatted[i1:i2] is deleted.
27 edits = append(edits, diff.TextEdit{Span: s})
29 // Insert: formatted[j1:j2] is inserted at unformatted[i1:i1].
30 if content := strings.Join(op.Content, ""); content != "" {
31 edits = append(edits, diff.TextEdit{Span: s, NewText: content})
38 type operation struct {
40 Content []string // content from b
41 I1, I2 int // indices of the line in a
42 J1 int // indices of the line in b, J2 implied by len(Content)
45 // operations returns the list of operations to convert a into b, consolidating
46 // operations for multiple lines and not including equal lines.
47 func operations(a, b []string) []*operation {
48 if len(a) == 0 && len(b) == 0 {
52 trace, offset := shortestEditSequence(a, b)
53 snakes := backtrack(trace, len(a), len(b), offset)
55 M, N := len(a), len(b)
58 solution := make([]*operation, len(a)+len(b))
60 add := func(op *operation, i2, j2 int) {
65 if op.Kind == diff.Insert {
66 op.Content = b[op.J1:j2]
72 for _, snake := range snakes {
77 // delete (horizontal)
78 for snake[0]-snake[1] > x-y {
94 for snake[0]-snake[1] < x-y {
111 if x >= M && y >= N {
118 // backtrack uses the trace for the edit sequence computation and returns the
119 // "snakes" that make up the solution. A "snake" is a single deletion or
120 // insertion followed by zero or diagonals.
121 func backtrack(trace [][]int, x, y, offset int) [][]int {
122 snakes := make([][]int, len(trace))
124 for ; x > 0 && y > 0 && d > 0; d-- {
129 snakes[d] = []int{x, y}
134 if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
146 snakes[d] = []int{x, y}
150 // shortestEditSequence returns the shortest edit sequence that converts a into b.
151 func shortestEditSequence(a, b []string) ([][]int, int) {
152 M, N := len(a), len(b)
153 V := make([]int, 2*(N+M)+1)
155 trace := make([][]int, N+M+1)
157 // Iterate through the maximum possible length of the SES (N+M).
158 for d := 0; d <= N+M; d++ {
159 copyV := make([]int, len(V))
160 // k lines are represented by the equation y = x - k. We move in
161 // increments of 2 because end points for even d are on even k lines.
162 for k := -d; k <= d; k += 2 {
163 // At each point, we either go down or to the right. We go down if
164 // k == -d, and we go to the right if k == d. We also prioritize
165 // the maximum x value, because we prefer deletions to insertions.
167 if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
168 x = V[k+1+offset] // down
170 x = V[k-1+offset] + 1 // right
175 // Diagonal moves while we have equal contents.
176 for x < M && y < N && a[x] == b[y] {
183 // Return if we've exceeded the maximum values.
184 if x == M && y == N {
185 // Makes sure to save the state of the array before returning.
192 // Save the state of the array.
199 func splitLines(text string) []string {
200 lines := strings.SplitAfter(text, "\n")
201 if lines[len(lines)-1] == "" {
202 lines = lines[:len(lines)-1]