match.go

Documentation: github.com/in-toto/in-toto-golang/in_toto

     1  // Copyright 2010 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found at https://golang.org/LICENSE.
     4  
     5  // this is a modified version of path.Match that removes handling of path separators
     6  
     7  package in_toto
     8  
     9  import (
    10  	"errors"
    11  	"unicode/utf8"
    12  )
    13  
    14  // errBadPattern indicates a pattern was malformed.
    15  var errBadPattern = errors.New("syntax error in pattern")
    16  
    17  // match reports whether name matches the shell pattern.
    18  // The pattern syntax is:
    19  //
    20  //	pattern:
    21  //		{ term }
    22  //	term:
    23  //		'*'         matches any sequence of non-/ characters
    24  //		'?'         matches any single non-/ character
    25  //		'[' [ '^' ] { character-range } ']'
    26  //		            character class (must be non-empty)
    27  //		c           matches character c (c != '*', '?', '\\', '[')
    28  //		'\\' c      matches character c
    29  //
    30  //	character-range:
    31  //		c           matches character c (c != '\\', '-', ']')
    32  //		'\\' c      matches character c
    33  //		lo '-' hi   matches character c for lo <= c <= hi
    34  //
    35  // Match requires pattern to match all of name, not just a substring.
    36  // The only possible returned error is ErrBadPattern, when pattern
    37  // is malformed.
    38  func match(pattern, name string) (matched bool, err error) {
    39  Pattern:
    40  	for len(pattern) > 0 {
    41  		var star bool
    42  		var chunk string
    43  		star, chunk, pattern = scanChunk(pattern)
    44  		if star && chunk == "" {
    45  			// Trailing * matches everything
    46  			return true, nil
    47  		}
    48  		// Look for match at current position.
    49  		t, ok, err := matchChunk(chunk, name)
    50  		// if we're the last chunk, make sure we've exhausted the name
    51  		// otherwise we'll give a false result even if we could still match
    52  		// using the star
    53  		if ok && (len(t) == 0 || len(pattern) > 0) {
    54  			name = t
    55  			continue
    56  		}
    57  		if err != nil {
    58  			return false, err
    59  		}
    60  		if star {
    61  			// Look for match skipping i+1 bytes.
    62  			for i := 0; i < len(name); i++ {
    63  				t, ok, err := matchChunk(chunk, name[i+1:])
    64  				if ok {
    65  					// if we're the last chunk, make sure we exhausted the name
    66  					if len(pattern) == 0 && len(t) > 0 {
    67  						continue
    68  					}
    69  					name = t
    70  					continue Pattern
    71  				}
    72  				if err != nil {
    73  					return false, err
    74  				}
    75  			}
    76  		}
    77  		// Before returning false with no error,
    78  		// check that the remainder of the pattern is syntactically valid.
    79  		for len(pattern) > 0 {
    80  			_, chunk, pattern = scanChunk(pattern)
    81  			if _, _, err := matchChunk(chunk, ""); err != nil {
    82  				return false, err
    83  			}
    84  		}
    85  		return false, nil
    86  	}
    87  	return len(name) == 0, nil
    88  }
    89  
    90  // scanChunk gets the next segment of pattern, which is a non-star string
    91  // possibly preceded by a star.
    92  func scanChunk(pattern string) (star bool, chunk, rest string) {
    93  	for len(pattern) > 0 && pattern[0] == '*' {
    94  		pattern = pattern[1:]
    95  		star = true
    96  	}
    97  	inrange := false
    98  	var i int
    99  Scan:
   100  	for i = 0; i < len(pattern); i++ {
   101  		switch pattern[i] {
   102  		case '\\':
   103  			// error check handled in matchChunk: bad pattern.
   104  			if i+1 < len(pattern) {
   105  				i++
   106  			}
   107  		case '[':
   108  			inrange = true
   109  		case ']':
   110  			inrange = false
   111  		case '*':
   112  			if !inrange {
   113  				break Scan
   114  			}
   115  		}
   116  	}
   117  	return star, pattern[0:i], pattern[i:]
   118  }
   119  
   120  // matchChunk checks whether chunk matches the beginning of s.
   121  // If so, it returns the remainder of s (after the match).
   122  // Chunk is all single-character operators: literals, char classes, and ?.
   123  func matchChunk(chunk, s string) (rest string, ok bool, err error) {
   124  	// failed records whether the match has failed.
   125  	// After the match fails, the loop continues on processing chunk,
   126  	// checking that the pattern is well-formed but no longer reading s.
   127  	failed := false
   128  	for len(chunk) > 0 {
   129  		if !failed && len(s) == 0 {
   130  			failed = true
   131  		}
   132  		switch chunk[0] {
   133  		case '[':
   134  			// character class
   135  			var r rune
   136  			if !failed {
   137  				var n int
   138  				r, n = utf8.DecodeRuneInString(s)
   139  				s = s[n:]
   140  			}
   141  			chunk = chunk[1:]
   142  			// possibly negated
   143  			negated := false
   144  			if len(chunk) > 0 && chunk[0] == '^' {
   145  				negated = true
   146  				chunk = chunk[1:]
   147  			}
   148  			// parse all ranges
   149  			match := false
   150  			nrange := 0
   151  			for {
   152  				if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
   153  					chunk = chunk[1:]
   154  					break
   155  				}
   156  				var lo, hi rune
   157  				if lo, chunk, err = getEsc(chunk); err != nil {
   158  					return "", false, err
   159  				}
   160  				hi = lo
   161  				if chunk[0] == '-' {
   162  					if hi, chunk, err = getEsc(chunk[1:]); err != nil {
   163  						return "", false, err
   164  					}
   165  				}
   166  				if lo <= r && r <= hi {
   167  					match = true
   168  				}
   169  				nrange++
   170  			}
   171  			if match == negated {
   172  				failed = true
   173  			}
   174  
   175  		case '?':
   176  			if !failed {
   177  				_, n := utf8.DecodeRuneInString(s)
   178  				s = s[n:]
   179  			}
   180  			chunk = chunk[1:]
   181  
   182  		case '\\':
   183  			chunk = chunk[1:]
   184  			if len(chunk) == 0 {
   185  				return "", false, errBadPattern
   186  			}
   187  			fallthrough
   188  
   189  		default:
   190  			if !failed {
   191  				if chunk[0] != s[0] {
   192  					failed = true
   193  				}
   194  				s = s[1:]
   195  			}
   196  			chunk = chunk[1:]
   197  		}
   198  	}
   199  	if failed {
   200  		return "", false, nil
   201  	}
   202  	return s, true, nil
   203  }
   204  
   205  // getEsc gets a possibly-escaped character from chunk, for a character class.
   206  func getEsc(chunk string) (r rune, nchunk string, err error) {
   207  	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
   208  		err = errBadPattern
   209  		return
   210  	}
   211  	if chunk[0] == '\\' {
   212  		chunk = chunk[1:]
   213  		if len(chunk) == 0 {
   214  			err = errBadPattern
   215  			return
   216  		}
   217  	}
   218  	r, n := utf8.DecodeRuneInString(chunk)
   219  	if r == utf8.RuneError && n == 1 {
   220  		err = errBadPattern
   221  	}
   222  	nchunk = chunk[n:]
   223  	if len(nchunk) == 0 {
   224  		err = errBadPattern
   225  	}
   226  	return
   227  }
   228
View as plain text