internal/diffp/diff.go - tools - Git at Google

 // 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 diffp implements a basic diff algorithm equivalent to patience diff.
 // It is a copy of internal/diff from the main Go repo, renamed to diffp to avoid
 // conflict with the existing golang.org/x/tools/internal/diff.
 package diffp

 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 definitey 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 := end.x - start.x
 			if n > C {
 				n = 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 a and b.
 	// 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 := 0; i < n; i++ {
 		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
 }
	// 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 diffp implements a basic diff algorithm equivalent to patience diff.
	// It is a copy of internal/diff from the main Go repo, renamed to diffp to avoid
	// conflict with the existing golang.org/x/tools/internal/diff.
	package diffp

	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 definitey 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 := end.x - start.x
	if n > C {
	n = 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 a and b.
	// 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 := 0; i < n; i++ {
	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
	}