compiler.go

Documentation: github.com/gobwas/glob/compiler

     1  package compiler
     2  
     3  // TODO use constructor with all matchers, and to their structs private
     4  // TODO glue multiple Text nodes (like after QuoteMeta)
     5  
     6  import (
     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  
    15  func 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  
    91  func 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  
   146  func 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  
   156  func 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  
   176  func 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  
   259  func 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
   303  func 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
   316  func 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  
   359  func 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  
   419  func 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  
   428  func 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  
   437  func 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  
   449  func 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  
   461  func 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  
   518  func 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
View as plain text