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