match.go

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