Something went wrong. Try again.
forked from tailscale/tailscale
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281// Copyright (c) Tailscale Inc & contributors// SPDX-License-Identifier: BSD-3-Clause
// Package safediff computes the difference between two lists.//// It is guaranteed to run in O(n), but may not produce an optimal diff.// Most diffing algorithms produce optimal diffs but run in O(n²).// It is safe to pass in untrusted input.package safediff
import ( "bytes" "fmt" "math" "strings" "unicode"
"github.com/google/go-cmp/cmp")
var diffTest = false
// Lines constructs a humanly readable line-by-line diff from x to y.// The output (if multiple lines) is guaranteed to be no larger than maxSize,// by truncating the output if necessary. A negative maxSize enforces no limit.//// Example diff://// … 440 identical lines// "ssh": [// … 35 identical lines// {// - "src": ["maisem@tailscale.com"],// - "dst": ["tag:maisem-test"],// - "users": ["maisem", "root"],// - "action": "check",// - // "recorder": ["100.12.34.56:80"],// + "src": ["maisem@tailscale.com"],// + "dst": ["tag:maisem-test"],// + "users": ["maisem", "root"],// + "action": "check",// + "recorder": ["node:recorder-2"],// },// … 77 identical lines// ],// … 345 identical lines//// Meaning of each line prefix://// - '…' precedes a summary statement// - ' ' precedes an identical line printed for context// - '-' precedes a line removed from x// - '+' precedes a line inserted from y//// The diffing algorithm runs in O(n) and is safe to use with untrusted inputs.func Lines(x, y string, maxSize int) (out string, truncated bool) { // Convert x and y into a slice of lines and compute the edit-script. xs := strings.Split(x, "\n") ys := strings.Split(y, "\n") es := diffStrings(xs, ys)
// Modify the edit-script to support printing identical lines of context. const identicalContext edit = '*' // special edit code to indicate printed line var xi, yi int // index into xs or ys isIdentical := func(e edit) bool { return e == identical || e == identicalContext } indentOf := func(s string) string { return s[:len(s)-len(strings.TrimLeftFunc(s, unicode.IsSpace))] } for i, e := range es { if isIdentical(e) { // Print current line if adjacent symbols are non-identical. switch { case i-1 >= 0 && !isIdentical(es[i-1]): es[i] = identicalContext case i+1 < len(es) && !isIdentical(es[i+1]): es[i] = identicalContext } } else { // Print any preceding or succeeding lines, // where the leading indent is a prefix of the current indent. // Indentation often indicates a parent-child relationship // in structured source code. addParents := func(ss []string, si, direction int) { childIndent := indentOf(ss[si]) for j := direction; i+j >= 0 && i+j < len(es) && isIdentical(es[i+j]); j += direction { parentIndent := indentOf(ss[si+j]) if strings.HasPrefix(childIndent, parentIndent) && len(parentIndent) < len(childIndent) && parentIndent != "" { es[i+j] = identicalContext childIndent = parentIndent } } } switch e { case removed, modified: // arbitrarily use the x value for modified values addParents(xs, xi, -1) addParents(xs, xi, +1) case inserted: addParents(ys, yi, -1) addParents(ys, yi, +1) } } if e != inserted { xi++ } if e != removed { yi++ } }
// Show the line for a single hidden identical line, // since it occupies the same vertical height. for i, e := range es { if e == identical { prevNotIdentical := i-1 < 0 || es[i-1] != identical nextNotIdentical := i+1 >= len(es) || es[i+1] != identical if prevNotIdentical && nextNotIdentical { es[i] = identicalContext } } }
// Adjust the maxSize, reserving space for the final summary. if maxSize < 0 { maxSize = math.MaxInt } maxSize -= len(stats{len(xs) + len(ys), len(xs), len(ys)}.appendText(nil))
// mayAppendLine appends a line if it does not exceed maxSize. // Otherwise, it just updates prevStats. var buf []byte var prevStats stats mayAppendLine := func(edit edit, line string) { // Append the stats (if non-zero) and the line text. // The stats reports the number of preceding identical lines. if !truncated { bufLen := len(buf) // original length (in case we exceed maxSize) if !prevStats.isZero() { buf = prevStats.appendText(buf) prevStats = stats{} // just printed, so clear the stats } buf = fmt.Appendf(buf, "%c %s\n", edit, line) truncated = len(buf) > maxSize if !truncated { return } buf = buf[:bufLen] // restore original buffer contents }
// Output is truncated, so just update the statistics. switch edit { case identical: prevStats.numIdentical++ case removed: prevStats.numRemoved++ case inserted: prevStats.numInserted++ } }
// Process the entire edit script. for len(es) > 0 { num := len(es) - len(bytes.TrimLeft(es, string(es[:1]))) switch es[0] { case identical: prevStats.numIdentical += num xs, ys = xs[num:], ys[num:] case identicalContext: for n := len(xs) - num; len(xs) > n; xs, ys = xs[1:], ys[1:] { mayAppendLine(identical, xs[0]) // implies xs[0] == ys[0] } case modified: for n := len(xs) - num; len(xs) > n; xs = xs[1:] { mayAppendLine(removed, xs[0]) } for n := len(ys) - num; len(ys) > n; ys = ys[1:] { mayAppendLine(inserted, ys[0]) } case removed: for n := len(xs) - num; len(xs) > n; xs = xs[1:] { mayAppendLine(removed, xs[0]) } case inserted: for n := len(ys) - num; len(ys) > n; ys = ys[1:] { mayAppendLine(inserted, ys[0]) } } es = es[num:] } if len(xs)+len(ys)+len(es) > 0 { panic("BUG: slices not fully consumed") }
if !prevStats.isZero() { buf = prevStats.appendText(buf) // may exceed maxSize } return string(buf), truncated}
type stats struct{ numIdentical, numRemoved, numInserted int }
func (s stats) isZero() bool { return s.numIdentical+s.numRemoved+s.numInserted == 0 }
func (s stats) appendText(b []byte) []byte { switch { case s.numIdentical > 0 && s.numRemoved > 0 && s.numInserted > 0: return fmt.Appendf(b, "… %d identical, %d removed, and %d inserted lines\n", s.numIdentical, s.numRemoved, s.numInserted) case s.numIdentical > 0 && s.numRemoved > 0: return fmt.Appendf(b, "… %d identical and %d removed lines\n", s.numIdentical, s.numRemoved) case s.numIdentical > 0 && s.numInserted > 0: return fmt.Appendf(b, "… %d identical and %d inserted lines\n", s.numIdentical, s.numInserted) case s.numRemoved > 0 && s.numInserted > 0: return fmt.Appendf(b, "… %d removed and %d inserted lines\n", s.numRemoved, s.numInserted) case s.numIdentical > 0: return fmt.Appendf(b, "… %d identical lines\n", s.numIdentical) case s.numRemoved > 0: return fmt.Appendf(b, "… %d removed lines\n", s.numRemoved) case s.numInserted > 0: return fmt.Appendf(b, "… %d inserted lines\n", s.numInserted) default: return fmt.Appendf(b, "…\n") }}
// diffStrings computes an edit-script of two slices of strings.//// This calls cmp.Equal to access the "github.com/go-cmp/cmp/internal/diff"// implementation, which has an O(N) diffing algorithm. It is not guaranteed// to produce an optimal edit-script, but protects our runtime against// adversarial inputs that would wreck the optimal O(N²) algorithm used by// most diffing packages available in open-source.//// TODO(https://go.dev/issue/58893): Use "golang.org/x/tools/diff" instead?func diffStrings(xs, ys []string) []edit { d := new(diffRecorder) cmp.Equal(xs, ys, cmp.Reporter(d)) if diffTest { numRemoved := bytes.Count(d.script, []byte{removed}) numInserted := bytes.Count(d.script, []byte{inserted}) if len(xs) != len(d.script)-numInserted || len(ys) != len(d.script)-numRemoved { panic("BUG: edit-script is inconsistent") } } return d.script}
type edit = byte
const ( identical edit = ' ' // equal symbol in both x and y modified edit = '~' // modified symbol in both x and y removed edit = '-' // removed symbol from x inserted edit = '+' // inserted symbol from y)
// diffRecorder reproduces an edit-script, essentially recording// the edit-script from "github.com/google/go-cmp/cmp/internal/diff".// This implements the cmp.Reporter interface.type diffRecorder struct { last cmp.PathStep script []edit}
func (d *diffRecorder) PushStep(ps cmp.PathStep) { d.last = ps }
func (d *diffRecorder) Report(rs cmp.Result) { if si, ok := d.last.(cmp.SliceIndex); ok { if rs.Equal() { d.script = append(d.script, identical) } else { switch xi, yi := si.SplitKeys(); { case xi >= 0 && yi >= 0: d.script = append(d.script, modified) case xi >= 0: d.script = append(d.script, removed) case yi >= 0: d.script = append(d.script, inserted) } } }}
func (d *diffRecorder) PopStep() { d.last = nil }