match.go

Documentation: path

		 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