Jean de Klerk | 2868181 | 2019-06-28 11:55:43 -0600 | [diff] [blame] | 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. |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 4 | package main |
| 5 | |
| 6 | import ( |
| 7 | "bytes" |
| 8 | "fmt" |
Austin Clements | a4ed05f | 2023-06-15 16:49:00 -0400 | [diff] [blame] | 9 | "io" |
Alan Donovan | c097262 | 2014-11-12 13:37:06 -0500 | [diff] [blame] | 10 | "reflect" |
Jean de Klerk | a4e10e6 | 2019-07-16 16:12:11 -0600 | [diff] [blame] | 11 | "sort" |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 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 |
Russ Cox | c862641 | 2022-03-30 09:29:51 -0400 | [diff] [blame] | 31 | e e |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 32 | ` |
| 33 | |
| 34 | for _, test := range []struct { |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 35 | name string |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 36 | input string |
| 37 | cmd string |
| 38 | args []string |
| 39 | want string |
| 40 | }{ |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 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"}, |
Jean de Klerk | 6d4652c | 2019-07-18 14:20:30 -0600 | [diff] [blame] | 43 | {"transpose", g1, "transpose", nil, "belt pants\njacket sweater\npants shorts\nshoes pants\nshoes socks\nsweater shirt\ntie shirt\n"}, |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 44 | {"forward", g1, "forward", []string{"socks"}, "shoes\nsocks\n"}, |
| 45 | {"forward multiple args", g1, "forward", []string{"socks", "sweater"}, "jacket\nshoes\nsocks\nsweater\n"}, |
Russ Cox | c862641 | 2022-03-30 09:29:51 -0400 | [diff] [blame] | 46 | {"scss", g2, "sccs", nil, "c d\ne\n"}, |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 47 | {"scc", g2, "scc", []string{"d"}, "c\nd\n"}, |
| 48 | {"succs", g2, "succs", []string{"a"}, "b\nc\n"}, |
Fumitoshi Ukai | 5bedd86 | 2023-01-18 01:04:09 +0000 | [diff] [blame] | 49 | {"succs-long-token", g2 + "x " + strings.Repeat("x", 96*1024), "succs", []string{"x"}, strings.Repeat("x", 96*1024) + "\n"}, |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 50 | {"preds", g2, "preds", []string{"c"}, "a\nd\n"}, |
| 51 | {"preds multiple args", g2, "preds", []string{"c", "d"}, "a\nb\nc\nd\n"}, |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 52 | } { |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 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 | } |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 59 | |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 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 | }) |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 65 | } |
| 66 | |
| 67 | // TODO(adonovan): |
Alan Donovan | 5f5b110 | 2014-10-23 09:13:39 -0400 | [diff] [blame] | 68 | // - test errors |
| 69 | } |
Alan Donovan | c097262 | 2014-11-12 13:37:06 -0500 | [diff] [blame] | 70 | |
Jean de Klerk | fefcef0 | 2019-07-12 10:22:56 -0600 | [diff] [blame] | 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 | |
Jean de Klerk | a4e10e6 | 2019-07-16 16:12:11 -0600 | [diff] [blame] | 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 | }, |
Alan Donovan | d86c729 | 2023-07-03 12:00:59 -0400 | [diff] [blame] | 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 | }, |
Jean de Klerk | a4e10e6 | 2019-07-16 16:12:11 -0600 | [diff] [blame] | 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 | |
Alan Donovan | c097262 | 2014-11-12 13:37:06 -0500 | [diff] [blame] | 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 | } |
Jean de Klerk | e97fc27 | 2019-10-13 22:20:27 -0600 | [diff] [blame] | 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 | } |
Austin Clements | a4ed05f | 2023-06-15 16:49:00 -0400 | [diff] [blame] | 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 | } |