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