src/internal/diff/diff.go

   1 // Copyright 2022 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 diff
   6
   7 import (
   8         "bytes"
   9         "fmt"
  10         "sort"
  11         "strings"
  12 )
  13
  14 // A pair is a pair of values tracked for both the x and y side of a diff.
  15 // It is typically a pair of line indexes.
  16 type pair struct{ x, y int }
  17
  18 // Diff returns an anchored diff of the two texts old and new
  19 // in the “unified diff” format. If old and new are identical,
  20 // Diff returns a nil slice (no output).
  21 //
  22 // Unix diff implementations typically look for a diff with
  23 // the smallest number of lines inserted and removed,
  24 // which can in the worst case take time quadratic in the
  25 // number of lines in the texts. As a result, many implementations
  26 // either can be made to run for a long time or cut off the search
  27 // after a predetermined amount of work.
  28 //
  29 // In contrast, this implementation looks for a diff with the
  30 // smallest number of “unique” lines inserted and removed,
  31 // where unique means a line that appears just once in both old and new.
  32 // We call this an “anchored diff” because the unique lines anchor
  33 // the chosen matching regions. An anchored diff is usually clearer
  34 // than a standard diff, because the algorithm does not try to
  35 // reuse unrelated blank lines or closing braces.
  36 // The algorithm also guarantees to run in O(n log n) time
  37 // instead of the standard O(n²) time.
  38 //
  39 // Some systems call this approach a “patience diff,” named for
  40 // the “patience sorting” algorithm, itself named for a solitaire card game.
  41 // We avoid that name for two reasons. First, the name has been used
  42 // for a few different variants of the algorithm, so it is imprecise.
  43 // Second, the name is frequently interpreted as meaning that you have
  44 // to wait longer (to be patient) for the diff, meaning that it is a slower algorithm,
  45 // when in fact the algorithm is faster than the standard one.
  46 //
  47 func Diff(oldName string, old []byte, newName string, new []byte) []byte {
  48         if bytes.Equal(old, new) {
  49                 return nil
  50         }
  51         x := lines(old)
  52         y := lines(new)
  53
  54         // Print diff header.
  55         var out bytes.Buffer
  56         fmt.Fprintf(&out, "diff %s %s\n", oldName, newName)
  57         fmt.Fprintf(&out, "--- %s\n", oldName)
  58         fmt.Fprintf(&out, "+++ %s\n", newName)
  59
  60         // Loop over matches to consider,
  61         // expanding each match to include surrounding lines,
  62         // and then printing diff chunks.
  63         // To avoid setup/teardown cases outside the loop,
  64         // tgs returns a leading {0,0} and trailing {len(x), len(y)} pair
  65         // in the sequence of matches.
  66         var (
  67                 done  pair     // printed up to x[:done.x] and y[:done.y]
  68                 chunk pair     // start lines of current chunk
  69                 count pair     // number of lines from each side in current chunk
  70                 ctext []string // lines for current chunk
  71         )
  72         for _, m := range tgs(x, y) {
  73                 if m.x < done.x {
  74                         // Already handled scanning forward from earlier match.
  75                         continue
  76                 }
  77
  78                 // Expand matching lines as far possible,
  79                 // establishing that x[start.x:end.x] == y[start.y:end.y].
  80                 // Note that on the first (or last) iteration we may (or definitey do)
  81                 // have an empty match: start.x==end.x and start.y==end.y.
  82                 start := m
  83                 for start.x > done.x && start.y > done.y && x[start.x-1] == y[start.y-1] {
  84                         start.x--
  85                         start.y--
  86                 }
  87                 end := m
  88                 for end.x < len(x) && end.y < len(y) && x[end.x] == y[end.y] {
  89                         end.x++
  90                         end.y++
  91                 }
  92
  93                 // Emit the mismatched lines before start into this chunk.
  94                 // (No effect on first sentinel iteration, when start = {0,0}.)
  95                 for _, s := range x[done.x:start.x] {
  96                         ctext = append(ctext, "-"+s)
  97                         count.x++
  98                 }
  99                 for _, s := range y[done.y:start.y] {
 100                         ctext = append(ctext, "+"+s)
 101                         count.y++
 102                 }
 103
 104                 // If we're not at EOF and have too few common lines,
 105                 // the chunk includes all the common lines and continues.
 106                 const C = 3 // number of context lines
 107                 if (end.x < len(x) || end.y < len(y)) &&
 108                         (end.x-start.x < C || (len(ctext) > 0 && end.x-start.x < 2*C)) {
 109                         for _, s := range x[start.x:end.x] {
 110                                 ctext = append(ctext, " "+s)
 111                                 count.x++
 112                                 count.y++
 113                         }
 114                         done = end
 115                         continue
 116                 }
 117
 118                 // End chunk with common lines for context.
 119                 if len(ctext) > 0 {
 120                         n := end.x - start.x
 121                         if n > C {
 122                                 n = C
 123                         }
 124                         for _, s := range x[start.x : start.x+n] {
 125                                 ctext = append(ctext, " "+s)
 126                                 count.x++
 127                                 count.y++
 128                         }
 129                         done = pair{start.x + n, start.y + n}
 130
 131                         // Format and emit chunk.
 132                         // Convert line numbers to 1-indexed.
 133                         // Special case: empty file shows up as 0,0 not 1,0.
 134                         if count.x > 0 {
 135                                 chunk.x++
 136                         }
 137                         if count.y > 0 {
 138                                 chunk.y++
 139                         }
 140                         fmt.Fprintf(&out, "@@ -%d,%d +%d,%d @@\n", chunk.x, count.x, chunk.y, count.y)
 141                         for _, s := range ctext {
 142                                 out.WriteString(s)
 143                         }
 144                         count.x = 0
 145                         count.y = 0
 146                         ctext = ctext[:0]
 147                 }
 148
 149                 // If we reached EOF, we're done.
 150                 if end.x >= len(x) && end.y >= len(y) {
 151                         break
 152                 }
 153
 154                 // Otherwise start a new chunk.
 155                 chunk = pair{end.x - C, end.y - C}
 156                 for _, s := range x[chunk.x:end.x] {
 157                         ctext = append(ctext, " "+s)
 158                         count.x++
 159                         count.y++
 160                 }
 161                 done = end
 162         }
 163
 164         return out.Bytes()
 165 }
 166
 167 // lines returns the lines in the file x, including newlines.
 168 // If the file does not end in a newline, one is supplied
 169 // along with a warning about the missing newline.
 170 func lines(x []byte) []string {
 171         l := strings.SplitAfter(string(x), "\n")
 172         if l[len(l)-1] == "" {
 173                 l = l[:len(l)-1]
 174         } else {
 175                 // Treat last line as having a message about the missing newline attached,
 176                 // using the same text as BSD/GNU diff (including the leading backslash).
 177                 l[len(l)-1] += "\n\\ No newline at end of file\n"
 178         }
 179         return l
 180 }
 181
 182 // tgs returns the pairs of indexes of the longest common subsequence
 183 // of unique lines in x and y, where a unique line is one that appears
 184 // once in x and once in y.
 185 //
 186 // The longest common subsequence algorithm is as described in
 187 // Thomas G. Szymanski, “A Special Case of the Maximal Common
 188 // Subsequence Problem,” Princeton TR #170 (January 1975),
 189 // available at https://research.swtch.com/tgs170.pdf.
 190 func tgs(x, y []string) []pair {
 191         // Count the number of times each string appears in a and b.
 192         // We only care about 0, 1, many, counted as 0, -1, -2
 193         // for the x side and 0, -4, -8 for the y side.
 194         // Using negative numbers now lets us distinguish positive line numbers later.
 195         m := make(map[string]int)
 196         for _, s := range x {
 197                 if c := m[s]; c > -2 {
 198                         m[s] = c - 1
 199                 }
 200         }
 201         for _, s := range y {
 202                 if c := m[s]; c > -8 {
 203                         m[s] = c - 4
 204                 }
 205         }
 206
 207         // Now unique strings can be identified by m[s] = -1+-4.
 208         //
 209         // Gather the indexes of those strings in x and y, building:
 210         //      xi[i] = increasing indexes of unique strings in x.
 211         //      yi[i] = increasing indexes of unique strings in y.
 212         //      inv[i] = index j such that x[xi[i]] = y[yi[j]].
 213         var xi, yi, inv []int
 214         for i, s := range y {
 215                 if m[s] == -1+-4 {
 216                         m[s] = len(yi)
 217                         yi = append(yi, i)
 218                 }
 219         }
 220         for i, s := range x {
 221                 if j, ok := m[s]; ok && j >= 0 {
 222                         xi = append(xi, i)
 223                         inv = append(inv, j)
 224                 }
 225         }
 226
 227         // Apply Algorithm A from Szymanski's paper.
 228         // In those terms, A = J = inv and B = [0, n).
 229         // We add sentinel pairs {0,0}, and {len(x),len(y)}
 230         // to the returned sequence, to help the processing loop.
 231         J := inv
 232         n := len(xi)
 233         T := make([]int, n)
 234         L := make([]int, n)
 235         for i := range T {
 236                 T[i] = n + 1
 237         }
 238         for i := 0; i < n; i++ {
 239                 k := sort.Search(n, func(k int) bool {
 240                         return T[k] >= J[i]
 241                 })
 242                 T[k] = J[i]
 243                 L[i] = k + 1
 244         }
 245         k := 0
 246         for _, v := range L {
 247                 if k < v {
 248                         k = v
 249                 }
 250         }
 251         seq := make([]pair, 2+k)
 252         seq[1+k] = pair{len(x), len(y)} // sentinel at end
 253         lastj := n
 254         for i := n - 1; i >= 0; i-- {
 255                 if L[i] == k && J[i] < lastj {
 256                         seq[k] = pair{xi[i], yi[J[i]]}
 257                         k--
 258                 }
 259         }
 260         seq[0] = pair{0, 0} // sentinel at start
 261         return seq
 262 }