gopls/internal/diff/lcs/old

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	"io/ioutil"
10	"log"
11	"math/rand"
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 miminal 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 := ioutil.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[:n49/100] + src[n51/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