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