1 package compiler
2
3 import (
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
11 var separators = []rune{'.'}
12
13 func 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
126 func 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
138 func 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
195 func 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
259 func 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
316 func 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
View as plain text