old_test.go

Documentation: golang.org/x/tools/internal/diff/lcs

     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 lcs
     6  
     7  import (
     8  	"fmt"
     9  	"log"
    10  	"math/rand"
    11  	"os"
    12  	"strings"
    13  	"testing"
    14  )
    15  
    16  func TestAlgosOld(t *testing.T) {
    17  	for i, algo := range []func(*editGraph) lcs{forward, backward, twosided} {
    18  		t.Run(strings.Fields("forward backward twosided")[i], func(t *testing.T) {
    19  			for _, tx := range Btests {
    20  				lim := len(tx.a) + len(tx.b)
    21  
    22  				diffs, lcs := compute(stringSeqs{tx.a, tx.b}, algo, lim)
    23  				check(t, tx.a, lcs, tx.lcs)
    24  				checkDiffs(t, tx.a, diffs, tx.b)
    25  
    26  				diffs, lcs = compute(stringSeqs{tx.b, tx.a}, algo, lim)
    27  				check(t, tx.b, lcs, tx.lcs)
    28  				checkDiffs(t, tx.b, diffs, tx.a)
    29  			}
    30  		})
    31  	}
    32  }
    33  
    34  func TestIntOld(t *testing.T) {
    35  	// need to avoid any characters in btests
    36  	lfill, rfill := "AAAAAAAAAAAA", "BBBBBBBBBBBB"
    37  	for _, tx := range Btests {
    38  		if len(tx.a) < 2 || len(tx.b) < 2 {
    39  			continue
    40  		}
    41  		left := tx.a + lfill
    42  		right := tx.b + rfill
    43  		lim := len(tx.a) + len(tx.b)
    44  		diffs, lcs := compute(stringSeqs{left, right}, twosided, lim)
    45  		check(t, left, lcs, tx.lcs)
    46  		checkDiffs(t, left, diffs, right)
    47  		diffs, lcs = compute(stringSeqs{right, left}, twosided, lim)
    48  		check(t, right, lcs, tx.lcs)
    49  		checkDiffs(t, right, diffs, left)
    50  
    51  		left = lfill + tx.a
    52  		right = rfill + tx.b
    53  		diffs, lcs = compute(stringSeqs{left, right}, twosided, lim)
    54  		check(t, left, lcs, tx.lcs)
    55  		checkDiffs(t, left, diffs, right)
    56  		diffs, lcs = compute(stringSeqs{right, left}, twosided, lim)
    57  		check(t, right, lcs, tx.lcs)
    58  		checkDiffs(t, right, diffs, left)
    59  	}
    60  }
    61  
    62  func TestSpecialOld(t *testing.T) { // exercises lcs.fix
    63  	a := "golang.org/x/tools/intern"
    64  	b := "github.com/google/safehtml/template\"\n\t\"golang.org/x/tools/intern"
    65  	diffs, lcs := compute(stringSeqs{a, b}, twosided, 4)
    66  	if !lcs.valid() {
    67  		t.Errorf("%d,%v", len(diffs), lcs)
    68  	}
    69  }
    70  
    71  func TestRegressionOld001(t *testing.T) {
    72  	a := "// Copyright 2019 The Go Authors. All rights reserved.\n// Use of this source code is governed by a BSD-style\n// license that can be found in the LICENSE file.\n\npackage diff_test\n\nimport (\n\t\"fmt\"\n\t\"math/rand\"\n\t\"strings\"\n\t\"testing\"\n\n\t\"golang.org/x/tools/gopls/internal/lsp/diff\"\n\t\"golang.org/x/tools/internal/diff/difftest\"\n\t\"golang.org/x/tools/gopls/internal/span\"\n)\n"
    73  
    74  	b := "// Copyright 2019 The Go Authors. All rights reserved.\n// Use of this source code is governed by a BSD-style\n// license that can be found in the LICENSE file.\n\npackage diff_test\n\nimport (\n\t\"fmt\"\n\t\"math/rand\"\n\t\"strings\"\n\t\"testing\"\n\n\t\"github.com/google/safehtml/template\"\n\t\"golang.org/x/tools/gopls/internal/lsp/diff\"\n\t\"golang.org/x/tools/internal/diff/difftest\"\n\t\"golang.org/x/tools/gopls/internal/span\"\n)\n"
    75  	for i := 1; i < len(b); i++ {
    76  		diffs, lcs := compute(stringSeqs{a, b}, twosided, i) // 14 from gopls
    77  		if !lcs.valid() {
    78  			t.Errorf("%d,%v", len(diffs), lcs)
    79  		}
    80  		checkDiffs(t, a, diffs, b)
    81  	}
    82  }
    83  
    84  func TestRegressionOld002(t *testing.T) {
    85  	a := "n\"\n)\n"
    86  	b := "n\"\n\t\"golang.org/x//nnal/stack\"\n)\n"
    87  	for i := 1; i <= len(b); i++ {
    88  		diffs, lcs := compute(stringSeqs{a, b}, twosided, i)
    89  		if !lcs.valid() {
    90  			t.Errorf("%d,%v", len(diffs), lcs)
    91  		}
    92  		checkDiffs(t, a, diffs, b)
    93  	}
    94  }
    95  
    96  func TestRegressionOld003(t *testing.T) {
    97  	a := "golang.org/x/hello v1.0.0\nrequire golang.org/x/unused v1"
    98  	b := "golang.org/x/hello v1"
    99  	for i := 1; i <= len(a); i++ {
   100  		diffs, lcs := compute(stringSeqs{a, b}, twosided, i)
   101  		if !lcs.valid() {
   102  			t.Errorf("%d,%v", len(diffs), lcs)
   103  		}
   104  		checkDiffs(t, a, diffs, b)
   105  	}
   106  }
   107  
   108  func TestRandOld(t *testing.T) {
   109  	rand.Seed(1)
   110  	for i := 0; i < 1000; i++ {
   111  		// TODO(adonovan): use ASCII and bytesSeqs here? The use of
   112  		// non-ASCII isn't relevant to the property exercised by the test.
   113  		a := []rune(randstr("abω", 16))
   114  		b := []rune(randstr("abωc", 16))
   115  		seq := runesSeqs{a, b}
   116  
   117  		const lim = 24 // large enough to get true lcs
   118  		_, forw := compute(seq, forward, lim)
   119  		_, back := compute(seq, backward, lim)
   120  		_, two := compute(seq, twosided, lim)
   121  		if lcslen(two) != lcslen(forw) || lcslen(forw) != lcslen(back) {
   122  			t.Logf("\n%v\n%v\n%v", forw, back, two)
   123  			t.Fatalf("%d forw:%d back:%d two:%d", i, lcslen(forw), lcslen(back), lcslen(two))
   124  		}
   125  		if !two.valid() || !forw.valid() || !back.valid() {
   126  			t.Errorf("check failure")
   127  		}
   128  	}
   129  }
   130  
   131  // TestDiffAPI tests the public API functions (Diff{Bytes,Strings,Runes})
   132  // to ensure at least minimal parity of the three representations.
   133  func TestDiffAPI(t *testing.T) {
   134  	for _, test := range []struct {
   135  		a, b                              string
   136  		wantStrings, wantBytes, wantRunes string
   137  	}{
   138  		{"abcXdef", "abcxdef", "[{3 4 3 4}]", "[{3 4 3 4}]", "[{3 4 3 4}]"}, // ASCII
   139  		{"abcωdef", "abcΩdef", "[{3 5 3 5}]", "[{3 5 3 5}]", "[{3 4 3 4}]"}, // non-ASCII
   140  	} {
   141  
   142  		gotStrings := fmt.Sprint(DiffStrings(test.a, test.b))
   143  		if gotStrings != test.wantStrings {
   144  			t.Errorf("DiffStrings(%q, %q) = %v, want %v",
   145  				test.a, test.b, gotStrings, test.wantStrings)
   146  		}
   147  		gotBytes := fmt.Sprint(DiffBytes([]byte(test.a), []byte(test.b)))
   148  		if gotBytes != test.wantBytes {
   149  			t.Errorf("DiffBytes(%q, %q) = %v, want %v",
   150  				test.a, test.b, gotBytes, test.wantBytes)
   151  		}
   152  		gotRunes := fmt.Sprint(DiffRunes([]rune(test.a), []rune(test.b)))
   153  		if gotRunes != test.wantRunes {
   154  			t.Errorf("DiffRunes(%q, %q) = %v, want %v",
   155  				test.a, test.b, gotRunes, test.wantRunes)
   156  		}
   157  	}
   158  }
   159  
   160  func BenchmarkTwoOld(b *testing.B) {
   161  	tests := genBench("abc", 96)
   162  	for i := 0; i < b.N; i++ {
   163  		for _, tt := range tests {
   164  			_, two := compute(stringSeqs{tt.before, tt.after}, twosided, 100)
   165  			if !two.valid() {
   166  				b.Error("check failed")
   167  			}
   168  		}
   169  	}
   170  }
   171  
   172  func BenchmarkForwOld(b *testing.B) {
   173  	tests := genBench("abc", 96)
   174  	for i := 0; i < b.N; i++ {
   175  		for _, tt := range tests {
   176  			_, two := compute(stringSeqs{tt.before, tt.after}, forward, 100)
   177  			if !two.valid() {
   178  				b.Error("check failed")
   179  			}
   180  		}
   181  	}
   182  }
   183  
   184  func genBench(set string, n int) []struct{ before, after string } {
   185  	// before and after for benchmarks. 24 strings of length n with
   186  	// before and after differing at least once, and about 5%
   187  	rand.Seed(3)
   188  	var ans []struct{ before, after string }
   189  	for i := 0; i < 24; i++ {
   190  		// maybe b should have an approximately known number of diffs
   191  		a := randstr(set, n)
   192  		cnt := 0
   193  		bb := make([]rune, 0, n)
   194  		for _, r := range a {
   195  			if rand.Float64() < .05 {
   196  				cnt++
   197  				r = 'N'
   198  			}
   199  			bb = append(bb, r)
   200  		}
   201  		if cnt == 0 {
   202  			// avoid == shortcut
   203  			bb[n/2] = 'N'
   204  		}
   205  		ans = append(ans, struct{ before, after string }{a, string(bb)})
   206  	}
   207  	return ans
   208  }
   209  
   210  // This benchmark represents a common case for a diff command:
   211  // large file with a single relatively small diff in the middle.
   212  // (It's not clear whether this is representative of gopls workloads
   213  // or whether it is important to gopls diff performance.)
   214  //
   215  // TODO(adonovan) opt: it could be much faster.  For example,
   216  // comparing a file against itself is about 10x faster than with the
   217  // small deletion in the middle. Strangely, comparing a file against
   218  // itself minus the last byte is faster still; I don't know why.
   219  // There is much low-hanging fruit here for further improvement.
   220  func BenchmarkLargeFileSmallDiff(b *testing.B) {
   221  	data, err := os.ReadFile("old.go") // large file
   222  	if err != nil {
   223  		log.Fatal(err)
   224  	}
   225  
   226  	n := len(data)
   227  
   228  	src := string(data)
   229  	dst := src[:n*49/100] + src[n*51/100:] // remove 2% from the middle
   230  	b.Run("string", func(b *testing.B) {
   231  		for i := 0; i < b.N; i++ {
   232  			compute(stringSeqs{src, dst}, twosided, len(src)+len(dst))
   233  		}
   234  	})
   235  
   236  	srcBytes := []byte(src)
   237  	dstBytes := []byte(dst)
   238  	b.Run("bytes", func(b *testing.B) {
   239  		for i := 0; i < b.N; i++ {
   240  			compute(bytesSeqs{srcBytes, dstBytes}, twosided, len(srcBytes)+len(dstBytes))
   241  		}
   242  	})
   243  
   244  	srcRunes := []rune(src)
   245  	dstRunes := []rune(dst)
   246  	b.Run("runes", func(b *testing.B) {
   247  		for i := 0; i < b.N; i++ {
   248  			compute(runesSeqs{srcRunes, dstRunes}, twosided, len(srcRunes)+len(dstRunes))
   249  		}
   250  	})
   251  }
   252
View as plain text