1package compiler 2 3import ( 4 "github.com/gobwas/glob/match" 5 "github.com/gobwas/glob/match/debug" 6 "github.com/gobwas/glob/syntax/ast" 7 "reflect" 8 "testing" 9) 10 11var separators = []rune{'.'} 12 13func TestCommonChildren(t *testing.T) { 14 for i, test := range []struct { 15 nodes []*ast.Node 16 left []*ast.Node 17 right []*ast.Node 18 }{ 19 { 20 nodes: []*ast.Node{ 21 ast.NewNode(ast.KindNothing, nil, 22 ast.NewNode(ast.KindText, ast.Text{"a"}), 23 ast.NewNode(ast.KindText, ast.Text{"z"}), 24 ast.NewNode(ast.KindText, ast.Text{"c"}), 25 ), 26 }, 27 }, 28 { 29 nodes: []*ast.Node{ 30 ast.NewNode(ast.KindNothing, nil, 31 ast.NewNode(ast.KindText, ast.Text{"a"}), 32 ast.NewNode(ast.KindText, ast.Text{"z"}), 33 ast.NewNode(ast.KindText, ast.Text{"c"}), 34 ), 35 ast.NewNode(ast.KindNothing, nil, 36 ast.NewNode(ast.KindText, ast.Text{"a"}), 37 ast.NewNode(ast.KindText, ast.Text{"b"}), 38 ast.NewNode(ast.KindText, ast.Text{"c"}), 39 ), 40 }, 41 left: []*ast.Node{ 42 ast.NewNode(ast.KindText, ast.Text{"a"}), 43 }, 44 right: []*ast.Node{ 45 ast.NewNode(ast.KindText, ast.Text{"c"}), 46 }, 47 }, 48 { 49 nodes: []*ast.Node{ 50 ast.NewNode(ast.KindNothing, nil, 51 ast.NewNode(ast.KindText, ast.Text{"a"}), 52 ast.NewNode(ast.KindText, ast.Text{"b"}), 53 ast.NewNode(ast.KindText, ast.Text{"c"}), 54 ast.NewNode(ast.KindText, ast.Text{"d"}), 55 ), 56 ast.NewNode(ast.KindNothing, nil, 57 ast.NewNode(ast.KindText, ast.Text{"a"}), 58 ast.NewNode(ast.KindText, ast.Text{"b"}), 59 ast.NewNode(ast.KindText, ast.Text{"c"}), 60 ast.NewNode(ast.KindText, ast.Text{"c"}), 61 ast.NewNode(ast.KindText, ast.Text{"d"}), 62 ), 63 }, 64 left: []*ast.Node{ 65 ast.NewNode(ast.KindText, ast.Text{"a"}), 66 ast.NewNode(ast.KindText, ast.Text{"b"}), 67 }, 68 right: []*ast.Node{ 69 ast.NewNode(ast.KindText, ast.Text{"c"}), 70 ast.NewNode(ast.KindText, ast.Text{"d"}), 71 }, 72 }, 73 { 74 nodes: []*ast.Node{ 75 ast.NewNode(ast.KindNothing, nil, 76 ast.NewNode(ast.KindText, ast.Text{"a"}), 77 ast.NewNode(ast.KindText, ast.Text{"b"}), 78 ast.NewNode(ast.KindText, ast.Text{"c"}), 79 ), 80 ast.NewNode(ast.KindNothing, nil, 81 ast.NewNode(ast.KindText, ast.Text{"a"}), 82 ast.NewNode(ast.KindText, ast.Text{"b"}), 83 ast.NewNode(ast.KindText, ast.Text{"b"}), 84 ast.NewNode(ast.KindText, ast.Text{"c"}), 85 ), 86 }, 87 left: []*ast.Node{ 88 ast.NewNode(ast.KindText, ast.Text{"a"}), 89 ast.NewNode(ast.KindText, ast.Text{"b"}), 90 }, 91 right: []*ast.Node{ 92 ast.NewNode(ast.KindText, ast.Text{"c"}), 93 }, 94 }, 95 { 96 nodes: []*ast.Node{ 97 ast.NewNode(ast.KindNothing, nil, 98 ast.NewNode(ast.KindText, ast.Text{"a"}), 99 ast.NewNode(ast.KindText, ast.Text{"d"}), 100 ), 101 ast.NewNode(ast.KindNothing, nil, 102 ast.NewNode(ast.KindText, ast.Text{"a"}), 103 ast.NewNode(ast.KindText, ast.Text{"d"}), 104 ), 105 ast.NewNode(ast.KindNothing, nil, 106 ast.NewNode(ast.KindText, ast.Text{"a"}), 107 ast.NewNode(ast.KindText, ast.Text{"e"}), 108 ), 109 }, 110 left: []*ast.Node{ 111 ast.NewNode(ast.KindText, ast.Text{"a"}), 112 }, 113 right: []*ast.Node{}, 114 }, 115 } { 116 left, right := commonChildren(test.nodes) 117 if !nodesEqual(left, test.left) { 118 t.Errorf("[%d] left, right := commonChildren(); left = %v; want %v", i, left, test.left) 119 } 120 if !nodesEqual(right, test.right) { 121 t.Errorf("[%d] left, right := commonChildren(); right = %v; want %v", i, right, test.right) 122 } 123 } 124} 125 126func nodesEqual(a, b []*ast.Node) bool { 127 if len(a) != len(b) { 128 return false 129 } 130 for i, av := range a { 131 if !av.Equal(b[i]) { 132 return false 133 } 134 } 135 return true 136} 137 138func TestGlueMatchers(t *testing.T) { 139 for id, test := range []struct { 140 in []match.Matcher 141 exp match.Matcher 142 }{ 143 { 144 []match.Matcher{ 145 match.NewSuper(), 146 match.NewSingle(nil), 147 }, 148 match.NewMin(1), 149 }, 150 { 151 []match.Matcher{ 152 match.NewAny(separators), 153 match.NewSingle(separators), 154 }, 155 match.EveryOf{match.Matchers{ 156 match.NewMin(1), 157 match.NewContains(string(separators), true), 158 }}, 159 }, 160 { 161 []match.Matcher{ 162 match.NewSingle(nil), 163 match.NewSingle(nil), 164 match.NewSingle(nil), 165 }, 166 match.EveryOf{match.Matchers{ 167 match.NewMin(3), 168 match.NewMax(3), 169 }}, 170 }, 171 { 172 []match.Matcher{ 173 match.NewList([]rune{'a'}, true), 174 match.NewAny([]rune{'a'}), 175 }, 176 match.EveryOf{match.Matchers{ 177 match.NewMin(1), 178 match.NewContains("a", true), 179 }}, 180 }, 181 } { 182 act, err := compileMatchers(test.in) 183 if err != nil { 184 t.Errorf("#%d convert matchers error: %s", id, err) 185 continue 186 } 187 188 if !reflect.DeepEqual(act, test.exp) { 189 t.Errorf("#%d unexpected convert matchers result:\nact: %#v;\nexp: %#v", id, act, test.exp) 190 continue 191 } 192 } 193} 194 195func TestCompileMatchers(t *testing.T) { 196 for id, test := range []struct { 197 in []match.Matcher 198 exp match.Matcher 199 }{ 200 { 201 []match.Matcher{ 202 match.NewSuper(), 203 match.NewSingle(separators), 204 match.NewText("c"), 205 }, 206 match.NewBTree( 207 match.NewText("c"), 208 match.NewBTree( 209 match.NewSingle(separators), 210 match.NewSuper(), 211 nil, 212 ), 213 nil, 214 ), 215 }, 216 { 217 []match.Matcher{ 218 match.NewAny(nil), 219 match.NewText("c"), 220 match.NewAny(nil), 221 }, 222 match.NewBTree( 223 match.NewText("c"), 224 match.NewAny(nil), 225 match.NewAny(nil), 226 ), 227 }, 228 { 229 []match.Matcher{ 230 match.NewRange('a', 'c', true), 231 match.NewList([]rune{'z', 't', 'e'}, false), 232 match.NewText("c"), 233 match.NewSingle(nil), 234 }, 235 match.NewRow( 236 4, 237 match.Matchers{ 238 match.NewRange('a', 'c', true), 239 match.NewList([]rune{'z', 't', 'e'}, false), 240 match.NewText("c"), 241 match.NewSingle(nil), 242 }..., 243 ), 244 }, 245 } { 246 act, err := compileMatchers(test.in) 247 if err != nil { 248 t.Errorf("#%d convert matchers error: %s", id, err) 249 continue 250 } 251 252 if !reflect.DeepEqual(act, test.exp) { 253 t.Errorf("#%d unexpected convert matchers result:\nact: %#v\nexp: %#v", id, act, test.exp) 254 continue 255 } 256 } 257} 258 259func TestConvertMatchers(t *testing.T) { 260 for id, test := range []struct { 261 in, exp []match.Matcher 262 }{ 263 { 264 []match.Matcher{ 265 match.NewRange('a', 'c', true), 266 match.NewList([]rune{'z', 't', 'e'}, false), 267 match.NewText("c"), 268 match.NewSingle(nil), 269 match.NewAny(nil), 270 }, 271 []match.Matcher{ 272 match.NewRow( 273 4, 274 []match.Matcher{ 275 match.NewRange('a', 'c', true), 276 match.NewList([]rune{'z', 't', 'e'}, false), 277 match.NewText("c"), 278 match.NewSingle(nil), 279 }..., 280 ), 281 match.NewAny(nil), 282 }, 283 }, 284 { 285 []match.Matcher{ 286 match.NewRange('a', 'c', true), 287 match.NewList([]rune{'z', 't', 'e'}, false), 288 match.NewText("c"), 289 match.NewSingle(nil), 290 match.NewAny(nil), 291 match.NewSingle(nil), 292 match.NewSingle(nil), 293 match.NewAny(nil), 294 }, 295 []match.Matcher{ 296 match.NewRow( 297 3, 298 match.Matchers{ 299 match.NewRange('a', 'c', true), 300 match.NewList([]rune{'z', 't', 'e'}, false), 301 match.NewText("c"), 302 }..., 303 ), 304 match.NewMin(3), 305 }, 306 }, 307 } { 308 act := minimizeMatchers(test.in) 309 if !reflect.DeepEqual(act, test.exp) { 310 t.Errorf("#%d unexpected convert matchers 2 result:\nact: %#v\nexp: %#v", id, act, test.exp) 311 continue 312 } 313 } 314} 315 316func TestCompiler(t *testing.T) { 317 for id, test := range []struct { 318 ast *ast.Node 319 result match.Matcher 320 sep []rune 321 }{ 322 { 323 ast: ast.NewNode(ast.KindPattern, nil, 324 ast.NewNode(ast.KindText, ast.Text{"abc"}), 325 ), 326 result: match.NewText("abc"), 327 }, 328 { 329 ast: ast.NewNode(ast.KindPattern, nil, 330 ast.NewNode(ast.KindAny, nil), 331 ), 332 sep: separators, 333 result: match.NewAny(separators), 334 }, 335 { 336 ast: ast.NewNode(ast.KindPattern, nil, 337 ast.NewNode(ast.KindAny, nil), 338 ), 339 result: match.NewSuper(), 340 }, 341 { 342 ast: ast.NewNode(ast.KindPattern, nil, 343 ast.NewNode(ast.KindSuper, nil), 344 ), 345 result: match.NewSuper(), 346 }, 347 { 348 ast: ast.NewNode(ast.KindPattern, nil, 349 ast.NewNode(ast.KindSingle, nil), 350 ), 351 sep: separators, 352 result: match.NewSingle(separators), 353 }, 354 { 355 ast: ast.NewNode(ast.KindPattern, nil, 356 ast.NewNode(ast.KindRange, ast.Range{ 357 Lo: 'a', 358 Hi: 'z', 359 Not: true, 360 }), 361 ), 362 result: match.NewRange('a', 'z', true), 363 }, 364 { 365 ast: ast.NewNode(ast.KindPattern, nil, 366 ast.NewNode(ast.KindList, ast.List{ 367 Chars: "abc", 368 Not: true, 369 }), 370 ), 371 result: match.NewList([]rune{'a', 'b', 'c'}, true), 372 }, 373 { 374 ast: ast.NewNode(ast.KindPattern, nil, 375 ast.NewNode(ast.KindAny, nil), 376 ast.NewNode(ast.KindSingle, nil), 377 ast.NewNode(ast.KindSingle, nil), 378 ast.NewNode(ast.KindSingle, nil), 379 ), 380 sep: separators, 381 result: match.EveryOf{Matchers: match.Matchers{ 382 match.NewMin(3), 383 match.NewContains(string(separators), true), 384 }}, 385 }, 386 { 387 ast: ast.NewNode(ast.KindPattern, nil, 388 ast.NewNode(ast.KindAny, nil), 389 ast.NewNode(ast.KindSingle, nil), 390 ast.NewNode(ast.KindSingle, nil), 391 ast.NewNode(ast.KindSingle, nil), 392 ), 393 result: match.NewMin(3), 394 }, 395 { 396 ast: ast.NewNode(ast.KindPattern, nil, 397 ast.NewNode(ast.KindAny, nil), 398 ast.NewNode(ast.KindText, ast.Text{"abc"}), 399 ast.NewNode(ast.KindSingle, nil), 400 ), 401 sep: separators, 402 result: match.NewBTree( 403 match.NewRow( 404 4, 405 match.Matchers{ 406 match.NewText("abc"), 407 match.NewSingle(separators), 408 }..., 409 ), 410 match.NewAny(separators), 411 nil, 412 ), 413 }, 414 { 415 ast: ast.NewNode(ast.KindPattern, nil, 416 ast.NewNode(ast.KindText, ast.Text{"/"}), 417 ast.NewNode(ast.KindAnyOf, nil, 418 ast.NewNode(ast.KindText, ast.Text{"z"}), 419 ast.NewNode(ast.KindText, ast.Text{"ab"}), 420 ), 421 ast.NewNode(ast.KindSuper, nil), 422 ), 423 sep: separators, 424 result: match.NewBTree( 425 match.NewText("/"), 426 nil, 427 match.NewBTree( 428 match.NewAnyOf(match.NewText("z"), match.NewText("ab")), 429 nil, 430 match.NewSuper(), 431 ), 432 ), 433 }, 434 { 435 ast: ast.NewNode(ast.KindPattern, nil, 436 ast.NewNode(ast.KindSuper, nil), 437 ast.NewNode(ast.KindSingle, nil), 438 ast.NewNode(ast.KindText, ast.Text{"abc"}), 439 ast.NewNode(ast.KindSingle, nil), 440 ), 441 sep: separators, 442 result: match.NewBTree( 443 match.NewRow( 444 5, 445 match.Matchers{ 446 match.NewSingle(separators), 447 match.NewText("abc"), 448 match.NewSingle(separators), 449 }..., 450 ), 451 match.NewSuper(), 452 nil, 453 ), 454 }, 455 { 456 ast: ast.NewNode(ast.KindPattern, nil, 457 ast.NewNode(ast.KindAny, nil), 458 ast.NewNode(ast.KindText, ast.Text{"abc"}), 459 ), 460 result: match.NewSuffix("abc"), 461 }, 462 { 463 ast: ast.NewNode(ast.KindPattern, nil, 464 ast.NewNode(ast.KindText, ast.Text{"abc"}), 465 ast.NewNode(ast.KindAny, nil), 466 ), 467 result: match.NewPrefix("abc"), 468 }, 469 { 470 ast: ast.NewNode(ast.KindPattern, nil, 471 ast.NewNode(ast.KindText, ast.Text{"abc"}), 472 ast.NewNode(ast.KindAny, nil), 473 ast.NewNode(ast.KindText, ast.Text{"def"}), 474 ), 475 result: match.NewPrefixSuffix("abc", "def"), 476 }, 477 { 478 ast: ast.NewNode(ast.KindPattern, nil, 479 ast.NewNode(ast.KindAny, nil), 480 ast.NewNode(ast.KindAny, nil), 481 ast.NewNode(ast.KindAny, nil), 482 ast.NewNode(ast.KindText, ast.Text{"abc"}), 483 ast.NewNode(ast.KindAny, nil), 484 ast.NewNode(ast.KindAny, nil), 485 ), 486 result: match.NewContains("abc", false), 487 }, 488 { 489 ast: ast.NewNode(ast.KindPattern, nil, 490 ast.NewNode(ast.KindAny, nil), 491 ast.NewNode(ast.KindAny, nil), 492 ast.NewNode(ast.KindAny, nil), 493 ast.NewNode(ast.KindText, ast.Text{"abc"}), 494 ast.NewNode(ast.KindAny, nil), 495 ast.NewNode(ast.KindAny, nil), 496 ), 497 sep: separators, 498 result: match.NewBTree( 499 match.NewText("abc"), 500 match.NewAny(separators), 501 match.NewAny(separators), 502 ), 503 }, 504 { 505 ast: ast.NewNode(ast.KindPattern, nil, 506 ast.NewNode(ast.KindSuper, nil), 507 ast.NewNode(ast.KindSingle, nil), 508 ast.NewNode(ast.KindText, ast.Text{"abc"}), 509 ast.NewNode(ast.KindSuper, nil), 510 ast.NewNode(ast.KindSingle, nil), 511 ), 512 result: match.NewBTree( 513 match.NewText("abc"), 514 match.NewMin(1), 515 match.NewMin(1), 516 ), 517 }, 518 { 519 ast: ast.NewNode(ast.KindPattern, nil, 520 ast.NewNode(ast.KindText, ast.Text{"abc"}), 521 ), 522 result: match.NewText("abc"), 523 }, 524 { 525 ast: ast.NewNode(ast.KindPattern, nil, 526 ast.NewNode(ast.KindAnyOf, nil, 527 ast.NewNode(ast.KindPattern, nil, 528 ast.NewNode(ast.KindAnyOf, nil, 529 ast.NewNode(ast.KindPattern, nil, 530 ast.NewNode(ast.KindText, ast.Text{"abc"}), 531 ), 532 ), 533 ), 534 ), 535 ), 536 result: match.NewText("abc"), 537 }, 538 { 539 ast: ast.NewNode(ast.KindPattern, nil, 540 ast.NewNode(ast.KindAnyOf, nil, 541 ast.NewNode(ast.KindPattern, nil, 542 ast.NewNode(ast.KindText, ast.Text{"abc"}), 543 ast.NewNode(ast.KindSingle, nil), 544 ), 545 ast.NewNode(ast.KindPattern, nil, 546 ast.NewNode(ast.KindText, ast.Text{"abc"}), 547 ast.NewNode(ast.KindList, ast.List{Chars: "def"}), 548 ), 549 ast.NewNode(ast.KindPattern, nil, 550 ast.NewNode(ast.KindText, ast.Text{"abc"}), 551 ), 552 ast.NewNode(ast.KindPattern, nil, 553 ast.NewNode(ast.KindText, ast.Text{"abc"}), 554 ), 555 ), 556 ), 557 result: match.NewBTree( 558 match.NewText("abc"), 559 nil, 560 match.AnyOf{Matchers: match.Matchers{ 561 match.NewSingle(nil), 562 match.NewList([]rune{'d', 'e', 'f'}, false), 563 match.NewNothing(), 564 }}, 565 ), 566 }, 567 { 568 ast: ast.NewNode(ast.KindPattern, nil, 569 ast.NewNode(ast.KindRange, ast.Range{Lo: 'a', Hi: 'z'}), 570 ast.NewNode(ast.KindRange, ast.Range{Lo: 'a', Hi: 'x', Not: true}), 571 ast.NewNode(ast.KindAny, nil), 572 ), 573 result: match.NewBTree( 574 match.NewRow( 575 2, 576 match.Matchers{ 577 match.NewRange('a', 'z', false), 578 match.NewRange('a', 'x', true), 579 }..., 580 ), 581 nil, 582 match.NewSuper(), 583 ), 584 }, 585 { 586 ast: ast.NewNode(ast.KindPattern, nil, 587 ast.NewNode(ast.KindAnyOf, nil, 588 ast.NewNode(ast.KindPattern, nil, 589 ast.NewNode(ast.KindText, ast.Text{"abc"}), 590 ast.NewNode(ast.KindList, ast.List{Chars: "abc"}), 591 ast.NewNode(ast.KindText, ast.Text{"ghi"}), 592 ), 593 ast.NewNode(ast.KindPattern, nil, 594 ast.NewNode(ast.KindText, ast.Text{"abc"}), 595 ast.NewNode(ast.KindList, ast.List{Chars: "def"}), 596 ast.NewNode(ast.KindText, ast.Text{"ghi"}), 597 ), 598 ), 599 ), 600 result: match.NewRow( 601 7, 602 match.Matchers{ 603 match.NewText("abc"), 604 match.AnyOf{Matchers: match.Matchers{ 605 match.NewList([]rune{'a', 'b', 'c'}, false), 606 match.NewList([]rune{'d', 'e', 'f'}, false), 607 }}, 608 match.NewText("ghi"), 609 }..., 610 ), 611 }, 612 } { 613 m, err := Compile(test.ast, test.sep) 614 if err != nil { 615 t.Errorf("compilation error: %s", err) 616 continue 617 } 618 619 if !reflect.DeepEqual(m, test.result) { 620 t.Errorf("[%d] Compile():\nexp: %#v\nact: %#v\n\ngraphviz:\nexp:\n%s\nact:\n%s\n", id, test.result, m, debug.Graphviz("", test.result.(match.Matcher)), debug.Graphviz("", m.(match.Matcher))) 621 continue 622 } 623 } 624} 625