1package difflib
2
3import (
4	"bytes"
5	"fmt"
6	"math"
7	"reflect"
8	"strings"
9	"testing"
10)
11
12func assertAlmostEqual(t *testing.T, a, b float64, places int) {
13	if math.Abs(a-b) > math.Pow10(-places) {
14		t.Errorf("%.7f != %.7f", a, b)
15	}
16}
17
18func assertEqual(t *testing.T, a, b interface{}) {
19	if !reflect.DeepEqual(a, b) {
20		t.Errorf("%v != %v", a, b)
21	}
22}
23
24func splitChars(s string) []string {
25	chars := make([]string, 0, len(s))
26	// Assume ASCII inputs
27	for i := 0; i != len(s); i++ {
28		chars = append(chars, string(s[i]))
29	}
30	return chars
31}
32
33func TestSequenceMatcherRatio(t *testing.T) {
34	s := NewMatcher(splitChars("abcd"), splitChars("bcde"))
35	assertEqual(t, s.Ratio(), 0.75)
36	assertEqual(t, s.QuickRatio(), 0.75)
37	assertEqual(t, s.RealQuickRatio(), 1.0)
38}
39
40func TestGetOptCodes(t *testing.T) {
41	a := "qabxcd"
42	b := "abycdf"
43	s := NewMatcher(splitChars(a), splitChars(b))
44	w := &bytes.Buffer{}
45	for _, op := range s.GetOpCodes() {
46		fmt.Fprintf(w, "%s a[%d:%d], (%s) b[%d:%d] (%s)\n", string(op.Tag),
47			op.I1, op.I2, a[op.I1:op.I2], op.J1, op.J2, b[op.J1:op.J2])
48	}
49	result := string(w.Bytes())
50	expected := `d a[0:1], (q) b[0:0] ()
51e a[1:3], (ab) b[0:2] (ab)
52r a[3:4], (x) b[2:3] (y)
53e a[4:6], (cd) b[3:5] (cd)
54i a[6:6], () b[5:6] (f)
55`
56	if expected != result {
57		t.Errorf("unexpected op codes: \n%s", result)
58	}
59}
60
61func TestGroupedOpCodes(t *testing.T) {
62	a := []string{}
63	for i := 0; i != 39; i++ {
64		a = append(a, fmt.Sprintf("%02d", i))
65	}
66	b := []string{}
67	b = append(b, a[:8]...)
68	b = append(b, " i")
69	b = append(b, a[8:19]...)
70	b = append(b, " x")
71	b = append(b, a[20:22]...)
72	b = append(b, a[27:34]...)
73	b = append(b, " y")
74	b = append(b, a[35:]...)
75	s := NewMatcher(a, b)
76	w := &bytes.Buffer{}
77	for _, g := range s.GetGroupedOpCodes(-1) {
78		fmt.Fprintf(w, "group\n")
79		for _, op := range g {
80			fmt.Fprintf(w, "  %s, %d, %d, %d, %d\n", string(op.Tag),
81				op.I1, op.I2, op.J1, op.J2)
82		}
83	}
84	result := string(w.Bytes())
85	expected := `group
86  e, 5, 8, 5, 8
87  i, 8, 8, 8, 9
88  e, 8, 11, 9, 12
89group
90  e, 16, 19, 17, 20
91  r, 19, 20, 20, 21
92  e, 20, 22, 21, 23
93  d, 22, 27, 23, 23
94  e, 27, 30, 23, 26
95group
96  e, 31, 34, 27, 30
97  r, 34, 35, 30, 31
98  e, 35, 38, 31, 34
99`
100	if expected != result {
101		t.Errorf("unexpected op codes: \n%s", result)
102	}
103}
104
105func ExampleGetUnifiedDiffCode() {
106	a := `one
107two
108three
109four
110fmt.Printf("%s,%T",a,b)`
111	b := `zero
112one
113three
114four`
115	diff := UnifiedDiff{
116		A:        SplitLines(a),
117		B:        SplitLines(b),
118		FromFile: "Original",
119		FromDate: "2005-01-26 23:30:50",
120		ToFile:   "Current",
121		ToDate:   "2010-04-02 10:20:52",
122		Context:  3,
123	}
124	result, _ := GetUnifiedDiffString(diff)
125	fmt.Println(strings.Replace(result, "\t", " ", -1))
126	// Output:
127	// --- Original 2005-01-26 23:30:50
128	// +++ Current 2010-04-02 10:20:52
129	// @@ -1,5 +1,4 @@
130	// +zero
131	//  one
132	// -two
133	//  three
134	//  four
135	// -fmt.Printf("%s,%T",a,b)
136}
137
138func ExampleGetContextDiffCode() {
139	a := `one
140two
141three
142four
143fmt.Printf("%s,%T",a,b)`
144	b := `zero
145one
146tree
147four`
148	diff := ContextDiff{
149		A:        SplitLines(a),
150		B:        SplitLines(b),
151		FromFile: "Original",
152		ToFile:   "Current",
153		Context:  3,
154		Eol:      "\n",
155	}
156	result, _ := GetContextDiffString(diff)
157	fmt.Print(strings.Replace(result, "\t", " ", -1))
158	// Output:
159	// *** Original
160	// --- Current
161	// ***************
162	// *** 1,5 ****
163	//   one
164	// ! two
165	// ! three
166	//   four
167	// - fmt.Printf("%s,%T",a,b)
168	// --- 1,4 ----
169	// + zero
170	//   one
171	// ! tree
172	//   four
173}
174
175func ExampleGetContextDiffString() {
176	a := `one
177two
178three
179four`
180	b := `zero
181one
182tree
183four`
184	diff := ContextDiff{
185		A:        SplitLines(a),
186		B:        SplitLines(b),
187		FromFile: "Original",
188		ToFile:   "Current",
189		Context:  3,
190		Eol:      "\n",
191	}
192	result, _ := GetContextDiffString(diff)
193	fmt.Printf(strings.Replace(result, "\t", " ", -1))
194	// Output:
195	// *** Original
196	// --- Current
197	// ***************
198	// *** 1,4 ****
199	//   one
200	// ! two
201	// ! three
202	//   four
203	// --- 1,4 ----
204	// + zero
205	//   one
206	// ! tree
207	//   four
208}
209
210func rep(s string, count int) string {
211	return strings.Repeat(s, count)
212}
213
214func TestWithAsciiOneInsert(t *testing.T) {
215	sm := NewMatcher(splitChars(rep("b", 100)),
216		splitChars("a"+rep("b", 100)))
217	assertAlmostEqual(t, sm.Ratio(), 0.995, 3)
218	assertEqual(t, sm.GetOpCodes(),
219		[]OpCode{{'i', 0, 0, 0, 1}, {'e', 0, 100, 1, 101}})
220	assertEqual(t, len(sm.bPopular), 0)
221
222	sm = NewMatcher(splitChars(rep("b", 100)),
223		splitChars(rep("b", 50)+"a"+rep("b", 50)))
224	assertAlmostEqual(t, sm.Ratio(), 0.995, 3)
225	assertEqual(t, sm.GetOpCodes(),
226		[]OpCode{{'e', 0, 50, 0, 50}, {'i', 50, 50, 50, 51}, {'e', 50, 100, 51, 101}})
227	assertEqual(t, len(sm.bPopular), 0)
228}
229
230func TestWithAsciiOnDelete(t *testing.T) {
231	sm := NewMatcher(splitChars(rep("a", 40)+"c"+rep("b", 40)),
232		splitChars(rep("a", 40)+rep("b", 40)))
233	assertAlmostEqual(t, sm.Ratio(), 0.994, 3)
234	assertEqual(t, sm.GetOpCodes(),
235		[]OpCode{{'e', 0, 40, 0, 40}, {'d', 40, 41, 40, 40}, {'e', 41, 81, 40, 80}})
236}
237
238func TestWithAsciiBJunk(t *testing.T) {
239	isJunk := func(s string) bool {
240		return s == " "
241	}
242	sm := NewMatcherWithJunk(splitChars(rep("a", 40)+rep("b", 40)),
243		splitChars(rep("a", 44)+rep("b", 40)), true, isJunk)
244	assertEqual(t, sm.bJunk, map[string]struct{}{})
245
246	sm = NewMatcherWithJunk(splitChars(rep("a", 40)+rep("b", 40)),
247		splitChars(rep("a", 44)+rep("b", 40)+rep(" ", 20)), false, isJunk)
248	assertEqual(t, sm.bJunk, map[string]struct{}{" ": struct{}{}})
249
250	isJunk = func(s string) bool {
251		return s == " " || s == "b"
252	}
253	sm = NewMatcherWithJunk(splitChars(rep("a", 40)+rep("b", 40)),
254		splitChars(rep("a", 44)+rep("b", 40)+rep(" ", 20)), false, isJunk)
255	assertEqual(t, sm.bJunk, map[string]struct{}{" ": struct{}{}, "b": struct{}{}})
256}
257
258func TestSFBugsRatioForNullSeqn(t *testing.T) {
259	sm := NewMatcher(nil, nil)
260	assertEqual(t, sm.Ratio(), 1.0)
261	assertEqual(t, sm.QuickRatio(), 1.0)
262	assertEqual(t, sm.RealQuickRatio(), 1.0)
263}
264
265func TestSFBugsComparingEmptyLists(t *testing.T) {
266	groups := NewMatcher(nil, nil).GetGroupedOpCodes(-1)
267	assertEqual(t, len(groups), 0)
268	diff := UnifiedDiff{
269		FromFile: "Original",
270		ToFile:   "Current",
271		Context:  3,
272	}
273	result, err := GetUnifiedDiffString(diff)
274	assertEqual(t, err, nil)
275	assertEqual(t, result, "")
276}
277
278func TestOutputFormatRangeFormatUnified(t *testing.T) {
279	// Per the diff spec at http://www.unix.org/single_unix_specification/
280	//
281	// Each <range> field shall be of the form:
282	//   %1d", <beginning line number>  if the range contains exactly one line,
283	// and:
284	//  "%1d,%1d", <beginning line number>, <number of lines> otherwise.
285	// If a range is empty, its beginning line number shall be the number of
286	// the line just before the range, or 0 if the empty range starts the file.
287	fm := formatRangeUnified
288	assertEqual(t, fm(3, 3), "3,0")
289	assertEqual(t, fm(3, 4), "4")
290	assertEqual(t, fm(3, 5), "4,2")
291	assertEqual(t, fm(3, 6), "4,3")
292	assertEqual(t, fm(0, 0), "0,0")
293}
294
295func TestOutputFormatRangeFormatContext(t *testing.T) {
296	// Per the diff spec at http://www.unix.org/single_unix_specification/
297	//
298	// The range of lines in file1 shall be written in the following format
299	// if the range contains two or more lines:
300	//     "*** %d,%d ****\n", <beginning line number>, <ending line number>
301	// and the following format otherwise:
302	//     "*** %d ****\n", <ending line number>
303	// The ending line number of an empty range shall be the number of the preceding line,
304	// or 0 if the range is at the start of the file.
305	//
306	// Next, the range of lines in file2 shall be written in the following format
307	// if the range contains two or more lines:
308	//     "--- %d,%d ----\n", <beginning line number>, <ending line number>
309	// and the following format otherwise:
310	//     "--- %d ----\n", <ending line number>
311	fm := formatRangeContext
312	assertEqual(t, fm(3, 3), "3")
313	assertEqual(t, fm(3, 4), "4")
314	assertEqual(t, fm(3, 5), "4,5")
315	assertEqual(t, fm(3, 6), "4,6")
316	assertEqual(t, fm(0, 0), "0")
317}
318
319func TestOutputFormatTabDelimiter(t *testing.T) {
320	diff := UnifiedDiff{
321		A:        splitChars("one"),
322		B:        splitChars("two"),
323		FromFile: "Original",
324		FromDate: "2005-01-26 23:30:50",
325		ToFile:   "Current",
326		ToDate:   "2010-04-12 10:20:52",
327		Eol:      "\n",
328	}
329	ud, err := GetUnifiedDiffString(diff)
330	assertEqual(t, err, nil)
331	assertEqual(t, SplitLines(ud)[:2], []string{
332		"--- Original\t2005-01-26 23:30:50\n",
333		"+++ Current\t2010-04-12 10:20:52\n",
334	})
335	cd, err := GetContextDiffString(ContextDiff(diff))
336	assertEqual(t, err, nil)
337	assertEqual(t, SplitLines(cd)[:2], []string{
338		"*** Original\t2005-01-26 23:30:50\n",
339		"--- Current\t2010-04-12 10:20:52\n",
340	})
341}
342
343func TestOutputFormatNoTrailingTabOnEmptyFiledate(t *testing.T) {
344	diff := UnifiedDiff{
345		A:        splitChars("one"),
346		B:        splitChars("two"),
347		FromFile: "Original",
348		ToFile:   "Current",
349		Eol:      "\n",
350	}
351	ud, err := GetUnifiedDiffString(diff)
352	assertEqual(t, err, nil)
353	assertEqual(t, SplitLines(ud)[:2], []string{"--- Original\n", "+++ Current\n"})
354
355	cd, err := GetContextDiffString(ContextDiff(diff))
356	assertEqual(t, err, nil)
357	assertEqual(t, SplitLines(cd)[:2], []string{"*** Original\n", "--- Current\n"})
358}
359
360func TestOmitFilenames(t *testing.T) {
361	diff := UnifiedDiff{
362		A:   SplitLines("o\nn\ne\n"),
363		B:   SplitLines("t\nw\no\n"),
364		Eol: "\n",
365	}
366	ud, err := GetUnifiedDiffString(diff)
367	assertEqual(t, err, nil)
368	assertEqual(t, SplitLines(ud), []string{
369		"@@ -0,0 +1,2 @@\n",
370		"+t\n",
371		"+w\n",
372		"@@ -2,2 +3,0 @@\n",
373		"-n\n",
374		"-e\n",
375		"\n",
376	})
377
378	cd, err := GetContextDiffString(ContextDiff(diff))
379	assertEqual(t, err, nil)
380	assertEqual(t, SplitLines(cd), []string{
381		"***************\n",
382		"*** 0 ****\n",
383		"--- 1,2 ----\n",
384		"+ t\n",
385		"+ w\n",
386		"***************\n",
387		"*** 2,3 ****\n",
388		"- n\n",
389		"- e\n",
390		"--- 3 ----\n",
391		"\n",
392	})
393}
394
395func TestSplitLines(t *testing.T) {
396	allTests := []struct {
397		input string
398		want  []string
399	}{
400		{"foo", []string{"foo\n"}},
401		{"foo\nbar", []string{"foo\n", "bar\n"}},
402		{"foo\nbar\n", []string{"foo\n", "bar\n", "\n"}},
403	}
404	for _, test := range allTests {
405		assertEqual(t, SplitLines(test.input), test.want)
406	}
407}
408
409func benchmarkSplitLines(b *testing.B, count int) {
410	str := strings.Repeat("foo\n", count)
411
412	b.ResetTimer()
413
414	n := 0
415	for i := 0; i < b.N; i++ {
416		n += len(SplitLines(str))
417	}
418}
419
420func BenchmarkSplitLines100(b *testing.B) {
421	benchmarkSplitLines(b, 100)
422}
423
424func BenchmarkSplitLines10000(b *testing.B) {
425	benchmarkSplitLines(b, 10000)
426}
427