.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/internal/lsp/diff/myers/diff.go

   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 // Package myers implements the Myers diff algorithm.
   6 package myers
   7
   8 import (
   9         "strings"
  10
  11         "golang.org/x/tools/internal/lsp/diff"
  12         "golang.org/x/tools/internal/span"
  13 )
  14
  15 // Sources:
  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
  18
  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))
  24                 switch op.Kind {
  25                 case diff.Delete:
  26                         // Delete: unformatted[i1:i2] is deleted.
  27                         edits = append(edits, diff.TextEdit{Span: s})
  28                 case diff.Insert:
  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})
  32                         }
  33                 }
  34         }
  35         return edits
  36 }
  37
  38 type operation struct {
  39         Kind    diff.OpKind
  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)
  43 }
  44
  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 {
  49                 return nil
  50         }
  51
  52         trace, offset := shortestEditSequence(a, b)
  53         snakes := backtrack(trace, len(a), len(b), offset)
  54
  55         M, N := len(a), len(b)
  56
  57         var i int
  58         solution := make([]*operation, len(a)+len(b))
  59
  60         add := func(op *operation, i2, j2 int) {
  61                 if op == nil {
  62                         return
  63                 }
  64                 op.I2 = i2
  65                 if op.Kind == diff.Insert {
  66                         op.Content = b[op.J1:j2]
  67                 }
  68                 solution[i] = op
  69                 i++
  70         }
  71         x, y := 0, 0
  72         for _, snake := range snakes {
  73                 if len(snake) < 2 {
  74                         continue
  75                 }
  76                 var op *operation
  77                 // delete (horizontal)
  78                 for snake[0]-snake[1] > x-y {
  79                         if op == nil {
  80                                 op = &operation{
  81                                         Kind: diff.Delete,
  82                                         I1:   x,
  83                                         J1:   y,
  84                                 }
  85                         }
  86                         x++
  87                         if x == M {
  88                                 break
  89                         }
  90                 }
  91                 add(op, x, y)
  92                 op = nil
  93                 // insert (vertical)
  94                 for snake[0]-snake[1] < x-y {
  95                         if op == nil {
  96                                 op = &operation{
  97                                         Kind: diff.Insert,
  98                                         I1:   x,
  99                                         J1:   y,
 100                                 }
 101                         }
 102                         y++
 103                 }
 104                 add(op, x, y)
 105                 op = nil
 106                 // equal (diagonal)
 107                 for x < snake[0] {
 108                         x++
 109                         y++
 110                 }
 111                 if x >= M && y >= N {
 112                         break
 113                 }
 114         }
 115         return solution[:i]
 116 }
 117
 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))
 123         d := len(trace) - 1
 124         for ; x > 0 && y > 0 && d > 0; d-- {
 125                 V := trace[d]
 126                 if len(V) == 0 {
 127                         continue
 128                 }
 129                 snakes[d] = []int{x, y}
 130
 131                 k := x - y
 132
 133                 var kPrev int
 134                 if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
 135                         kPrev = k + 1
 136                 } else {
 137                         kPrev = k - 1
 138                 }
 139
 140                 x = V[kPrev+offset]
 141                 y = x - kPrev
 142         }
 143         if x < 0 || y < 0 {
 144                 return snakes
 145         }
 146         snakes[d] = []int{x, y}
 147         return snakes
 148 }
 149
 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)
 154         offset := N + M
 155         trace := make([][]int, N+M+1)
 156
 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.
 166                         var x int
 167                         if k == -d || (k != d && V[k-1+offset] < V[k+1+offset]) {
 168                                 x = V[k+1+offset] // down
 169                         } else {
 170                                 x = V[k-1+offset] + 1 // right
 171                         }
 172
 173                         y := x - k
 174
 175                         // Diagonal moves while we have equal contents.
 176                         for x < M && y < N && a[x] == b[y] {
 177                                 x++
 178                                 y++
 179                         }
 180
 181                         V[k+offset] = x
 182
 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.
 186                                 copy(copyV, V)
 187                                 trace[d] = copyV
 188                                 return trace, offset
 189                         }
 190                 }
 191
 192                 // Save the state of the array.
 193                 copy(copyV, V)
 194                 trace[d] = copyV
 195         }
 196         return nil, 0
 197 }
 198
 199 func splitLines(text string) []string {
 200         lines := strings.SplitAfter(text, "\n")
 201         if lines[len(lines)-1] == "" {
 202                 lines = lines[:len(lines)-1]
 203         }
 204         return lines
 205 }