digraph_test.go

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