Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281// Copyright 2022 The Go Authors. All rights reserved.// Use of this source code is governed by a BSD-style// license that can be found in the LICENSE file.
package formatter
import ( "bytes" "fmt" "sort" "strings")
// A pair is a pair of values tracked for both the x and y side of a diff.// It is typically a pair of line indexes.type pair struct{ x, y int }
// diff returns an anchored diff of the two texts old and new// in the “unified diff” format. If old and new are identical,// Diff returns a nil slice (no output).//// Unix diff implementations typically look for a diff with// the smallest number of lines inserted and removed,// which can in the worst case take time quadratic in the// number of lines in the texts. As a result, many implementations// either can be made to run for a long time or cut off the search// after a predetermined amount of work.//// In contrast, this implementation looks for a diff with the// smallest number of “unique” lines inserted and removed,// where unique means a line that appears just once in both old and new.// We call this an “anchored diff” because the unique lines anchor// the chosen matching regions. An anchored diff is usually clearer// than a standard diff, because the algorithm does not try to// reuse unrelated blank lines or closing braces.// The algorithm also guarantees to run in O(n log n) time// instead of the standard O(n²) time.//// Some systems call this approach a “patience diff,” named for// the “patience sorting” algorithm, itself named for a solitaire card game.// We avoid that name for two reasons. First, the name has been used// for a few different variants of the algorithm, so it is imprecise.// Second, the name is frequently interpreted as meaning that you have// to wait longer (to be patient) for the diff, meaning that it is a slower algorithm,// when in fact the algorithm is faster than the standard one.func diff(oldName string, old []byte, newName string, new []byte) []byte { if bytes.Equal(old, new) { return nil }
x := lines(old) y := lines(new)
// Print diff header. var out bytes.Buffer fmt.Fprintf(&out, "diff %s %s\n", oldName, newName) fmt.Fprintf(&out, "--- %s\n", oldName) fmt.Fprintf(&out, "+++ %s\n", newName)
// Loop over matches to consider, // expanding each match to include surrounding lines, // and then printing diff chunks. // To avoid setup/teardown cases outside the loop, // tgs returns a leading {0,0} and trailing {len(x), len(y)} pair // in the sequence of matches. var ( done pair // printed up to x[:done.x] and y[:done.y] chunk pair // start lines of current chunk count pair // number of lines from each side in current chunk ctext []string // lines for current chunk ) for _, m := range tgs(x, y) { if m.x < done.x { // Already handled scanning forward from earlier match. continue }
// Expand matching lines as far possible, // establishing that x[start.x:end.x] == y[start.y:end.y]. // Note that on the first (or last) iteration we may (or definitely do) // have an empty match: start.x==end.x and start.y==end.y. start := m for start.x > done.x && start.y > done.y && x[start.x-1] == y[start.y-1] { start.x-- start.y-- }
end := m for end.x < len(x) && end.y < len(y) && x[end.x] == y[end.y] { end.x++ end.y++ }
// Emit the mismatched lines before start into this chunk. // (No effect on first sentinel iteration, when start = {0,0}.) for _, s := range x[done.x:start.x] { ctext = append(ctext, "-"+s) count.x++ }
for _, s := range y[done.y:start.y] { ctext = append(ctext, "+"+s) count.y++ }
// If we're not at EOF and have too few common lines, // the chunk includes all the common lines and continues. const C = 3 // number of context lines if (end.x < len(x) || end.y < len(y)) && (end.x-start.x < C || (len(ctext) > 0 && end.x-start.x < 2*C)) { for _, s := range x[start.x:end.x] { ctext = append(ctext, " "+s) count.x++ count.y++ }
done = end
continue }
// End chunk with common lines for context. if len(ctext) > 0 { n := min(end.x-start.x, C) for _, s := range x[start.x : start.x+n] { ctext = append(ctext, " "+s) count.x++ count.y++ }
done = pair{start.x + n, start.y + n}
// Format and emit chunk. // Convert line numbers to 1-indexed. // Special case: empty file shows up as 0,0 not 1,0. if count.x > 0 { chunk.x++ }
if count.y > 0 { chunk.y++ }
fmt.Fprintf(&out, "@@ -%d,%d +%d,%d @@\n", chunk.x, count.x, chunk.y, count.y)
for _, s := range ctext { out.WriteString(s) }
count.x = 0 count.y = 0 ctext = ctext[:0] }
// If we reached EOF, we're done. if end.x >= len(x) && end.y >= len(y) { break }
// Otherwise start a new chunk. chunk = pair{end.x - C, end.y - C} for _, s := range x[chunk.x:end.x] { ctext = append(ctext, " "+s) count.x++ count.y++ }
done = end }
return out.Bytes()}
// lines returns the lines in the file x, including newlines.// If the file does not end in a newline, one is supplied// along with a warning about the missing newline.func lines(x []byte) []string { l := strings.SplitAfter(string(x), "\n") if l[len(l)-1] == "" { l = l[:len(l)-1] } else { // Treat last line as having a message about the missing newline attached, // using the same text as BSD/GNU diff (including the leading backslash). l[len(l)-1] += "\n\\ No newline at end of file\n" }
return l}
// tgs returns the pairs of indexes of the longest common subsequence// of unique lines in x and y, where a unique line is one that appears// once in x and once in y.//// The longest common subsequence algorithm is as described in// Thomas G. Szymanski, “A Special Case of the Maximal Common// Subsequence Problem,” Princeton TR #170 (January 1975),// available at https://research.swtch.com/tgs170.pdf.func tgs(x, y []string) []pair { // Count the number of times each string appears in x and y. // We only care about 0, 1, many, counted as 0, -1, -2 // for the x side and 0, -4, -8 for the y side. // Using negative numbers now lets us distinguish positive line numbers later. m := make(map[string]int) for _, s := range x { if c := m[s]; c > -2 { m[s] = c - 1 } }
for _, s := range y { if c := m[s]; c > -8 { m[s] = c - 4 } }
// Now unique strings can be identified by m[s] = -1+-4. // // Gather the indexes of those strings in x and y, building: // xi[i] = increasing indexes of unique strings in x. // yi[i] = increasing indexes of unique strings in y. // inv[i] = index j such that x[xi[i]] = y[yi[j]]. var xi, yi, inv []int
for i, s := range y { if m[s] == -1+-4 { m[s] = len(yi) yi = append(yi, i) } }
for i, s := range x { if j, ok := m[s]; ok && j >= 0 { xi = append(xi, i) inv = append(inv, j) } }
// Apply Algorithm A from Szymanski's paper. // In those terms, A = J = inv and B = [0, n). // We add sentinel pairs {0,0}, and {len(x),len(y)} // to the returned sequence, to help the processing loop. J := inv n := len(xi) T := make([]int, n)
L := make([]int, n) for i := range T { T[i] = n + 1 }
for i := range n { k := sort.Search(n, func(k int) bool { return T[k] >= J[i] }) T[k] = J[i] L[i] = k + 1 }
k := 0 for _, v := range L { if k < v { k = v } }
seq := make([]pair, 2+k) seq[1+k] = pair{len(x), len(y)} // sentinel at end
lastj := n for i := n - 1; i >= 0; i-- { if L[i] == k && J[i] < lastj { seq[k] = pair{xi[i], yi[J[i]]} k-- } }
seq[0] = pair{0, 0} // sentinel at start
return seq}