gopls/cmd/digraph/digraph

1	// Copyright 2019 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	package main
5
6	import (
7	"bytes"
8	"fmt"
9	"reflect"
10	"sort"
11	"strings"
12	"testing"
13	)
14
15	func TestDigraph(t *testing.T) {
16	const g1 = `
17	socks shoes
18	shorts pants
19	pants belt shoes
20	shirt tie sweater
21	sweater jacket
22	hat
23	`
24
25	const g2 = `
26	a b c
27	b d
28	c d
29	d c
30	e e
31	`
32
33	for _, test := range []struct {
34	name string
35	input string
36	cmd string
37	args []string
38	want string
39	}{
40	{"nodes", g1, "nodes", nil, "belt\nhat\njacket\npants\nshirt\nshoes\nshorts\nsocks\nsweater\ntie\n"},
41	{"reverse", g1, "reverse", []string{"jacket"}, "jacket\nshirt\nsweater\n"},
42	{"transpose", g1, "transpose", nil, "belt pants\njacket sweater\npants shorts\nshoes pants\nshoes socks\nsweater shirt\ntie shirt\n"},
43	{"forward", g1, "forward", []string{"socks"}, "shoes\nsocks\n"},
44	{"forward multiple args", g1, "forward", []string{"socks", "sweater"}, "jacket\nshoes\nsocks\nsweater\n"},
45	{"scss", g2, "sccs", nil, "c d\ne\n"},
46	{"scc", g2, "scc", []string{"d"}, "c\nd\n"},
47	{"succs", g2, "succs", []string{"a"}, "b\nc\n"},
48	{"preds", g2, "preds", []string{"c"}, "a\nd\n"},
49	{"preds multiple args", g2, "preds", []string{"c", "d"}, "a\nb\nc\nd\n"},
50	} {
51	t.Run(test.name, func(t *testing.T) {
52	stdin = strings.NewReader(test.input)
53	stdout = new(bytes.Buffer)
54	if err := digraph(test.cmd, test.args); err != nil {
55	t.Fatal(err)
56	}
57
58	got := stdout.(fmt.Stringer).String()
59	if got != test.want {
60	t.Errorf("digraph(%s, %s) = got %q, want %q", test.cmd, test.args, got, test.want)
61	}
62	})
63	}
64
65	// TODO(adonovan):
66	// - test somepath (it's nondeterministic).
67	// - test errors
68	}
69
70	func TestAllpaths(t *testing.T) {
71	for _, test := range []struct {
72	name string
73	in string
74	to string // from is always "A"
75	want string
76	}{
77	{
78	name: "Basic",
79	in: "A B\nB C",
80	to: "B",
81	want: "A B\n",
82	},
83	{
84	name: "Long",
85	in: "A B\nB C\n",
86	to: "C",
87	want: "A B\nB C\n",
88	},
89	{
90	name: "Cycle Basic",
91	in: "A B\nB A",
92	to: "B",
93	want: "A B\nB A\n",
94	},
95	{
96	name: "Cycle Path Out",
97	// A <-> B -> C -> D
98	in: "A B\nB A\nB C\nC D",
99	to: "C",
100	want: "A B\nB A\nB C\n",
101	},
102	{
103	name: "Cycle Path Out Further Out",
104	// A -> B <-> C -> D -> E
105	in: "A B\nB C\nC D\nC B\nD E",
106	to: "D",
107	want: "A B\nB C\nC B\nC D\n",
108	},
109	{
110	name: "Two Paths Basic",
111	// /-> C --\
112	// A -> B -- -> E -> F
113	// \-> D --/
114	in: "A B\nB C\nC E\nB D\nD E\nE F",
115	to: "E",
116	want: "A B\nB C\nB D\nC E\nD E\n",
117	},
118	{
119	name: "Two Paths With One Immediately From Start",
120	// /-> B -+ -> D
121	// A -- \|
122	// \-> C <+
123	in: "A B\nA C\nB C\nB D",
124	to: "C",
125	want: "A B\nA C\nB C\n",
126	},
127	{
128	name: "Two Paths Further Up",
129	// /-> B --\
130	// A -- -> D -> E -> F
131	// \-> C --/
132	in: "A B\nA C\nB D\nC D\nD E\nE F",
133	to: "E",
134	want: "A B\nA C\nB D\nC D\nD E\n",
135	},
136	{
137	// We should include A - C - D even though it's further up the
138	// second path than D (which would already be in the graph by
139	// the time we get around to integrating the second path).
140	name: "Two Splits",
141	// /-> B --\ /-> E --\
142	// A -- -> D -- -> G -> H
143	// \-> C --/ \-> F --/
144	in: "A B\nA C\nB D\nC D\nD E\nD F\nE G\nF G\nG H",
145	to: "G",
146	want: "A B\nA C\nB D\nC D\nD E\nD F\nE G\nF G\n",
147	},
148	{
149	// D - E should not be duplicated.
150	name: "Two Paths - Two Splits With Gap",
151	// /-> B --\ /-> F --\
152	// A -- -> D -> E -- -> H -> I
153	// \-> C --/ \-> G --/
154	in: "A B\nA C\nB D\nC D\nD E\nE F\nE G\nF H\nG H\nH I",
155	to: "H",
156	want: "A B\nA C\nB D\nC D\nD E\nE F\nE G\nF H\nG H\n",
157	},
158	} {
159	t.Run(test.name, func(t *testing.T) {
160	stdin = strings.NewReader(test.in)
161	stdout = new(bytes.Buffer)
162	if err := digraph("allpaths", []string{"A", test.to}); err != nil {
163	t.Fatal(err)
164	}
165
166	got := stdout.(fmt.Stringer).String()
167	if got != test.want {
168	t.Errorf("digraph(allpaths, A, %s) = got %q, want %q", test.to, got, test.want)
169	}
170	})
171	}
172	}
173
174	func TestSomepath(t *testing.T) {
175	for _, test := range []struct {
176	name string
177	in string
178	to string
179	// somepath is non-deterministic, so we have to provide all the
180	// possible options. Each option is separated with \|.
181	wantAnyOf string
182	}{
183	{
184	name: "Basic",
185	in: "A B\n",
186	to: "B",
187	wantAnyOf: "A B",
188	},
189	{
190	name: "Basic With Cycle",
191	in: "A B\nB A",
192	to: "B",
193	wantAnyOf: "A B",
194	},
195	{
196	name: "Two Paths",
197	// /-> B --\
198	// A -- -> D
199	// \-> C --/
200	in: "A B\nA C\nB D\nC D",
201	to: "D",
202	wantAnyOf: "A B\nB D\|A C\nC D",
203	},
204	} {
205	t.Run(test.name, func(t *testing.T) {
206	stdin = strings.NewReader(test.in)
207	stdout = new(bytes.Buffer)
208	if err := digraph("somepath", []string{"A", test.to}); err != nil {
209	t.Fatal(err)
210	}
211
212	got := stdout.(fmt.Stringer).String()
213	lines := strings.Split(got, "\n")
214	sort.Strings(lines)
215	got = strings.Join(lines[1:], "\n")
216
217	var oneMatch bool
218	for _, want := range strings.Split(test.wantAnyOf, "\|") {
219	if got == want {
220	oneMatch = true
221	}
222	}
223	if !oneMatch {
224	t.Errorf("digraph(somepath, A, %s) = got %q, want any of\n%s", test.to, got, test.wantAnyOf)
225	}
226	})
227	}
228	}
229
230	func TestSplit(t *testing.T) {
231	for _, test := range []struct {
232	line string
233	want []string
234	}{
235	{`one "2a 2b" three`, []string{"one", "2a 2b", "three"}},
236	{`one tw"\n\x0a\u000a\012"o three`, []string{"one", "tw\n\n\n\no", "three"}},
237	} {
238	got, err := split(test.line)
239	if err != nil {
240	t.Errorf("split(%s) failed: %v", test.line, err)
241	}
242	if !reflect.DeepEqual(got, test.want) {
243	t.Errorf("split(%s) = %v, want %v", test.line, got, test.want)
244	}
245	}
246	}
247
248	func TestQuotedLength(t *testing.T) {
249	for _, test := range []struct {
250	input string
251	want int
252	}{
253	{`"abc"`, 5},
254	{`"abc"def`, 5},
255	{`"abc\"d"ef`, 8}, // "abc\"d" is consumed, ef is residue
256	{`"\012\n\x0a\u000a\U0000000a"`, 28},
257	{"\"\xff\"", 3}, // bad UTF-8 is ok
258	{`"\xff"`, 6}, // hex escape for bad UTF-8 is ok
259	} {
260	got, ok := quotedLength(test.input)
261	if !ok {
262	got = 0
263	}
264	if got != test.want {
265	t.Errorf("quotedLength(%s) = %d, want %d", test.input, got, test.want)
266	}
267	}
268
269	// errors
270	for _, input := range []string{
271	``, // not a quotation
272	`a`, // not a quotation
273	`'a'`, // not a quotation
274	`"a`, // not terminated
275	`"\0"`, // short octal escape
276	`"\x1"`, // short hex escape
277	`"\u000"`, // short \u escape
278	`"\U0000000"`, // short \U escape
279	`"\k"`, // invalid escape
280	"\"ab\nc\"", // newline
281	} {
282	if n, ok := quotedLength(input); ok {
283	t.Errorf("quotedLength(%s) = %d, want !ok", input, n)
284	}
285	}
286	}
287
288	func TestFocus(t *testing.T) {
289	for _, test := range []struct {
290	name string
291	in string
292	focus string
293	want string
294	}{
295	{
296	name: "Basic",
297	in: "A B",
298	focus: "B",
299	want: "A B\n",
300	},
301	{
302	name: "Some Nodes Not Included",
303	// C does not have a path involving B, and should not be included
304	// in the output.
305	in: "A B\nA C",
306	focus: "B",
307	want: "A B\n",
308	},
309	{
310	name: "Cycle In Path",
311	// A <-> B -> C
312	in: "A B\nB A\nB C",
313	focus: "C",
314	want: "A B\nB A\nB C\n",
315	},
316	{
317	name: "Cycle Out Of Path",
318	// C <- A <->B
319	in: "A B\nB A\nB C",
320	focus: "C",
321	want: "A B\nB A\nB C\n",
322	},
323	{
324	name: "Complex",
325	// Paths in and out from focus.
326	// /-> F
327	// /-> B -> D --
328	// A -- \-> E
329	// \-> C
330	in: "A B\nA C\nB D\nD F\nD E",
331	focus: "D",
332	want: "A B\nB D\nD E\nD F\n",
333	},
334	} {
335	t.Run(test.name, func(t *testing.T) {
336	stdin = strings.NewReader(test.in)
337	stdout = new(bytes.Buffer)
338	if err := digraph("focus", []string{test.focus}); err != nil {
339	t.Fatal(err)
340	}
341	got := stdout.(fmt.Stringer).String()
342	if got != test.want {
343	t.Errorf("digraph(focus, %s) = got %q, want %q", test.focus, got, test.want)
344	}
345	})
346	}
347	}
348