1package compiler
2
3// TODO use constructor with all matchers, and to their structs private
4// TODO glue multiple Text nodes (like after QuoteMeta)
5
6import (
7	"fmt"
8	"reflect"
9
10	"github.com/gobwas/glob/match"
11	"github.com/gobwas/glob/syntax/ast"
12	"github.com/gobwas/glob/util/runes"
13)
14
15func optimizeMatcher(matcher match.Matcher) match.Matcher {
16	switch m := matcher.(type) {
17
18	case match.Any:
19		if len(m.Separators) == 0 {
20			return match.NewSuper()
21		}
22
23	case match.AnyOf:
24		if len(m.Matchers) == 1 {
25			return m.Matchers[0]
26		}
27
28		return m
29
30	case match.List:
31		if m.Not == false && len(m.List) == 1 {
32			return match.NewText(string(m.List))
33		}
34
35		return m
36
37	case match.BTree:
38		m.Left = optimizeMatcher(m.Left)
39		m.Right = optimizeMatcher(m.Right)
40
41		r, ok := m.Value.(match.Text)
42		if !ok {
43			return m
44		}
45
46		var (
47			leftNil  = m.Left == nil
48			rightNil = m.Right == nil
49		)
50		if leftNil && rightNil {
51			return match.NewText(r.Str)
52		}
53
54		_, leftSuper := m.Left.(match.Super)
55		lp, leftPrefix := m.Left.(match.Prefix)
56		la, leftAny := m.Left.(match.Any)
57
58		_, rightSuper := m.Right.(match.Super)
59		rs, rightSuffix := m.Right.(match.Suffix)
60		ra, rightAny := m.Right.(match.Any)
61
62		switch {
63		case leftSuper && rightSuper:
64			return match.NewContains(r.Str, false)
65
66		case leftSuper && rightNil:
67			return match.NewSuffix(r.Str)
68
69		case rightSuper && leftNil:
70			return match.NewPrefix(r.Str)
71
72		case leftNil && rightSuffix:
73			return match.NewPrefixSuffix(r.Str, rs.Suffix)
74
75		case rightNil && leftPrefix:
76			return match.NewPrefixSuffix(lp.Prefix, r.Str)
77
78		case rightNil && leftAny:
79			return match.NewSuffixAny(r.Str, la.Separators)
80
81		case leftNil && rightAny:
82			return match.NewPrefixAny(r.Str, ra.Separators)
83		}
84
85		return m
86	}
87
88	return matcher
89}
90
91func compileMatchers(matchers []match.Matcher) (match.Matcher, error) {
92	if len(matchers) == 0 {
93		return nil, fmt.Errorf("compile error: need at least one matcher")
94	}
95	if len(matchers) == 1 {
96		return matchers[0], nil
97	}
98	if m := glueMatchers(matchers); m != nil {
99		return m, nil
100	}
101
102	idx := -1
103	maxLen := -1
104	var val match.Matcher
105	for i, matcher := range matchers {
106		if l := matcher.Len(); l != -1 && l >= maxLen {
107			maxLen = l
108			idx = i
109			val = matcher
110		}
111	}
112
113	if val == nil { // not found matcher with static length
114		r, err := compileMatchers(matchers[1:])
115		if err != nil {
116			return nil, err
117		}
118		return match.NewBTree(matchers[0], nil, r), nil
119	}
120
121	left := matchers[:idx]
122	var right []match.Matcher
123	if len(matchers) > idx+1 {
124		right = matchers[idx+1:]
125	}
126
127	var l, r match.Matcher
128	var err error
129	if len(left) > 0 {
130		l, err = compileMatchers(left)
131		if err != nil {
132			return nil, err
133		}
134	}
135
136	if len(right) > 0 {
137		r, err = compileMatchers(right)
138		if err != nil {
139			return nil, err
140		}
141	}
142
143	return match.NewBTree(val, l, r), nil
144}
145
146func glueMatchers(matchers []match.Matcher) match.Matcher {
147	if m := glueMatchersAsEvery(matchers); m != nil {
148		return m
149	}
150	if m := glueMatchersAsRow(matchers); m != nil {
151		return m
152	}
153	return nil
154}
155
156func glueMatchersAsRow(matchers []match.Matcher) match.Matcher {
157	if len(matchers) <= 1 {
158		return nil
159	}
160
161	var (
162		c []match.Matcher
163		l int
164	)
165	for _, matcher := range matchers {
166		if ml := matcher.Len(); ml == -1 {
167			return nil
168		} else {
169			c = append(c, matcher)
170			l += ml
171		}
172	}
173	return match.NewRow(l, c...)
174}
175
176func glueMatchersAsEvery(matchers []match.Matcher) match.Matcher {
177	if len(matchers) <= 1 {
178		return nil
179	}
180
181	var (
182		hasAny    bool
183		hasSuper  bool
184		hasSingle bool
185		min       int
186		separator []rune
187	)
188
189	for i, matcher := range matchers {
190		var sep []rune
191
192		switch m := matcher.(type) {
193		case match.Super:
194			sep = []rune{}
195			hasSuper = true
196
197		case match.Any:
198			sep = m.Separators
199			hasAny = true
200
201		case match.Single:
202			sep = m.Separators
203			hasSingle = true
204			min++
205
206		case match.List:
207			if !m.Not {
208				return nil
209			}
210			sep = m.List
211			hasSingle = true
212			min++
213
214		default:
215			return nil
216		}
217
218		// initialize
219		if i == 0 {
220			separator = sep
221		}
222
223		if runes.Equal(sep, separator) {
224			continue
225		}
226
227		return nil
228	}
229
230	if hasSuper && !hasAny && !hasSingle {
231		return match.NewSuper()
232	}
233
234	if hasAny && !hasSuper && !hasSingle {
235		return match.NewAny(separator)
236	}
237
238	if (hasAny || hasSuper) && min > 0 && len(separator) == 0 {
239		return match.NewMin(min)
240	}
241
242	every := match.NewEveryOf()
243
244	if min > 0 {
245		every.Add(match.NewMin(min))
246
247		if !hasAny && !hasSuper {
248			every.Add(match.NewMax(min))
249		}
250	}
251
252	if len(separator) > 0 {
253		every.Add(match.NewContains(string(separator), true))
254	}
255
256	return every
257}
258
259func minimizeMatchers(matchers []match.Matcher) []match.Matcher {
260	var done match.Matcher
261	var left, right, count int
262
263	for l := 0; l < len(matchers); l++ {
264		for r := len(matchers); r > l; r-- {
265			if glued := glueMatchers(matchers[l:r]); glued != nil {
266				var swap bool
267
268				if done == nil {
269					swap = true
270				} else {
271					cl, gl := done.Len(), glued.Len()
272					swap = cl > -1 && gl > -1 && gl > cl
273					swap = swap || count < r-l
274				}
275
276				if swap {
277					done = glued
278					left = l
279					right = r
280					count = r - l
281				}
282			}
283		}
284	}
285
286	if done == nil {
287		return matchers
288	}
289
290	next := append(append([]match.Matcher{}, matchers[:left]...), done)
291	if right < len(matchers) {
292		next = append(next, matchers[right:]...)
293	}
294
295	if len(next) == len(matchers) {
296		return next
297	}
298
299	return minimizeMatchers(next)
300}
301
302// minimizeAnyOf tries to apply some heuristics to minimize number of nodes in given tree
303func minimizeTree(tree *ast.Node) *ast.Node {
304	switch tree.Kind {
305	case ast.KindAnyOf:
306		return minimizeTreeAnyOf(tree)
307	default:
308		return nil
309	}
310}
311
312// minimizeAnyOf tries to find common children of given node of AnyOf pattern
313// it searches for common children from left and from right
314// if any common children are found – then it returns new optimized ast tree
315// else it returns nil
316func minimizeTreeAnyOf(tree *ast.Node) *ast.Node {
317	if !areOfSameKind(tree.Children, ast.KindPattern) {
318		return nil
319	}
320
321	commonLeft, commonRight := commonChildren(tree.Children)
322	commonLeftCount, commonRightCount := len(commonLeft), len(commonRight)
323	if commonLeftCount == 0 && commonRightCount == 0 { // there are no common parts
324		return nil
325	}
326
327	var result []*ast.Node
328	if commonLeftCount > 0 {
329		result = append(result, ast.NewNode(ast.KindPattern, nil, commonLeft...))
330	}
331
332	var anyOf []*ast.Node
333	for _, child := range tree.Children {
334		reuse := child.Children[commonLeftCount : len(child.Children)-commonRightCount]
335		var node *ast.Node
336		if len(reuse) == 0 {
337			// this pattern is completely reduced by commonLeft and commonRight patterns
338			// so it become nothing
339			node = ast.NewNode(ast.KindNothing, nil)
340		} else {
341			node = ast.NewNode(ast.KindPattern, nil, reuse...)
342		}
343		anyOf = appendIfUnique(anyOf, node)
344	}
345	switch {
346	case len(anyOf) == 1 && anyOf[0].Kind != ast.KindNothing:
347		result = append(result, anyOf[0])
348	case len(anyOf) > 1:
349		result = append(result, ast.NewNode(ast.KindAnyOf, nil, anyOf...))
350	}
351
352	if commonRightCount > 0 {
353		result = append(result, ast.NewNode(ast.KindPattern, nil, commonRight...))
354	}
355
356	return ast.NewNode(ast.KindPattern, nil, result...)
357}
358
359func commonChildren(nodes []*ast.Node) (commonLeft, commonRight []*ast.Node) {
360	if len(nodes) <= 1 {
361		return
362	}
363
364	// find node that has least number of children
365	idx := leastChildren(nodes)
366	if idx == -1 {
367		return
368	}
369	tree := nodes[idx]
370	treeLength := len(tree.Children)
371
372	// allocate max able size for rightCommon slice
373	// to get ability insert elements in reverse order (from end to start)
374	// without sorting
375	commonRight = make([]*ast.Node, treeLength)
376	lastRight := treeLength // will use this to get results as commonRight[lastRight:]
377
378	var (
379		breakLeft   bool
380		breakRight  bool
381		commonTotal int
382	)
383	for i, j := 0, treeLength-1; commonTotal < treeLength && j >= 0 && !(breakLeft && breakRight); i, j = i+1, j-1 {
384		treeLeft := tree.Children[i]
385		treeRight := tree.Children[j]
386
387		for k := 0; k < len(nodes) && !(breakLeft && breakRight); k++ {
388			// skip least children node
389			if k == idx {
390				continue
391			}
392
393			restLeft := nodes[k].Children[i]
394			restRight := nodes[k].Children[j+len(nodes[k].Children)-treeLength]
395
396			breakLeft = breakLeft || !treeLeft.Equal(restLeft)
397
398			// disable searching for right common parts, if left part is already overlapping
399			breakRight = breakRight || (!breakLeft && j <= i)
400			breakRight = breakRight || !treeRight.Equal(restRight)
401		}
402
403		if !breakLeft {
404			commonTotal++
405			commonLeft = append(commonLeft, treeLeft)
406		}
407		if !breakRight {
408			commonTotal++
409			lastRight = j
410			commonRight[j] = treeRight
411		}
412	}
413
414	commonRight = commonRight[lastRight:]
415
416	return
417}
418
419func appendIfUnique(target []*ast.Node, val *ast.Node) []*ast.Node {
420	for _, n := range target {
421		if reflect.DeepEqual(n, val) {
422			return target
423		}
424	}
425	return append(target, val)
426}
427
428func areOfSameKind(nodes []*ast.Node, kind ast.Kind) bool {
429	for _, n := range nodes {
430		if n.Kind != kind {
431			return false
432		}
433	}
434	return true
435}
436
437func leastChildren(nodes []*ast.Node) int {
438	min := -1
439	idx := -1
440	for i, n := range nodes {
441		if idx == -1 || (len(n.Children) < min) {
442			min = len(n.Children)
443			idx = i
444		}
445	}
446	return idx
447}
448
449func compileTreeChildren(tree *ast.Node, sep []rune) ([]match.Matcher, error) {
450	var matchers []match.Matcher
451	for _, desc := range tree.Children {
452		m, err := compile(desc, sep)
453		if err != nil {
454			return nil, err
455		}
456		matchers = append(matchers, optimizeMatcher(m))
457	}
458	return matchers, nil
459}
460
461func compile(tree *ast.Node, sep []rune) (m match.Matcher, err error) {
462	switch tree.Kind {
463	case ast.KindAnyOf:
464		// todo this could be faster on pattern_alternatives_combine_lite (see glob_test.go)
465		if n := minimizeTree(tree); n != nil {
466			return compile(n, sep)
467		}
468		matchers, err := compileTreeChildren(tree, sep)
469		if err != nil {
470			return nil, err
471		}
472		return match.NewAnyOf(matchers...), nil
473
474	case ast.KindPattern:
475		if len(tree.Children) == 0 {
476			return match.NewNothing(), nil
477		}
478		matchers, err := compileTreeChildren(tree, sep)
479		if err != nil {
480			return nil, err
481		}
482		m, err = compileMatchers(minimizeMatchers(matchers))
483		if err != nil {
484			return nil, err
485		}
486
487	case ast.KindAny:
488		m = match.NewAny(sep)
489
490	case ast.KindSuper:
491		m = match.NewSuper()
492
493	case ast.KindSingle:
494		m = match.NewSingle(sep)
495
496	case ast.KindNothing:
497		m = match.NewNothing()
498
499	case ast.KindList:
500		l := tree.Value.(ast.List)
501		m = match.NewList([]rune(l.Chars), l.Not)
502
503	case ast.KindRange:
504		r := tree.Value.(ast.Range)
505		m = match.NewRange(r.Lo, r.Hi, r.Not)
506
507	case ast.KindText:
508		t := tree.Value.(ast.Text)
509		m = match.NewText(t.Text)
510
511	default:
512		return nil, fmt.Errorf("could not compile tree: unknown node type")
513	}
514
515	return optimizeMatcher(m), nil
516}
517
518func Compile(tree *ast.Node, sep []rune) (match.Matcher, error) {
519	m, err := compile(tree, sep)
520	if err != nil {
521		return nil, err
522	}
523
524	return m, nil
525}
526