...
Run Format

Source file src/path/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  	"strings"
    10  	"unicode/utf8"
    11  )
    12  
    13  // ErrBadPattern indicates a globbing pattern was malformed.
    14  var ErrBadPattern = errors.New("syntax error in pattern")
    15  
    16  // Match reports whether name matches the shell file name 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 !strings.Contains(name, "/"), 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  		return false, nil
    79  	}
    80  	return len(name) == 0, nil
    81  }
    82  
    83  // scanChunk gets the next segment of pattern, which is a non-star string
    84  // possibly preceded by a star.
    85  func scanChunk(pattern string) (star bool, chunk, rest string) {
    86  	for len(pattern) > 0 && pattern[0] == '*' {
    87  		pattern = pattern[1:]
    88  		star = true
    89  	}
    90  	inrange := false
    91  	var i int
    92  Scan:
    93  	for i = 0; i < len(pattern); i++ {
    94  		switch pattern[i] {
    95  		case '\\':
    96  			// error check handled in matchChunk: bad pattern.
    97  			if i+1 < len(pattern) {
    98  				i++
    99  			}
   100  		case '[':
   101  			inrange = true
   102  		case ']':
   103  			inrange = false
   104  		case '*':
   105  			if !inrange {
   106  				break Scan
   107  			}
   108  		}
   109  	}
   110  	return star, pattern[0:i], pattern[i:]
   111  }
   112  
   113  // matchChunk checks whether chunk matches the beginning of s.
   114  // If so, it returns the remainder of s (after the match).
   115  // Chunk is all single-character operators: literals, char classes, and ?.
   116  func matchChunk(chunk, s string) (rest string, ok bool, err error) {
   117  	for len(chunk) > 0 {
   118  		if len(s) == 0 {
   119  			return
   120  		}
   121  		switch chunk[0] {
   122  		case '[':
   123  			// character class
   124  			r, n := utf8.DecodeRuneInString(s)
   125  			s = s[n:]
   126  			chunk = chunk[1:]
   127  			// possibly negated
   128  			notNegated := true
   129  			if len(chunk) > 0 && chunk[0] == '^' {
   130  				notNegated = false
   131  				chunk = chunk[1:]
   132  			}
   133  			// parse all ranges
   134  			match := false
   135  			nrange := 0
   136  			for {
   137  				if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
   138  					chunk = chunk[1:]
   139  					break
   140  				}
   141  				var lo, hi rune
   142  				if lo, chunk, err = getEsc(chunk); err != nil {
   143  					return
   144  				}
   145  				hi = lo
   146  				if chunk[0] == '-' {
   147  					if hi, chunk, err = getEsc(chunk[1:]); err != nil {
   148  						return
   149  					}
   150  				}
   151  				if lo <= r && r <= hi {
   152  					match = true
   153  				}
   154  				nrange++
   155  			}
   156  			if match != notNegated {
   157  				return
   158  			}
   159  
   160  		case '?':
   161  			if s[0] == '/' {
   162  				return
   163  			}
   164  			_, n := utf8.DecodeRuneInString(s)
   165  			s = s[n:]
   166  			chunk = chunk[1:]
   167  
   168  		case '\\':
   169  			chunk = chunk[1:]
   170  			if len(chunk) == 0 {
   171  				err = ErrBadPattern
   172  				return
   173  			}
   174  			fallthrough
   175  
   176  		default:
   177  			if chunk[0] != s[0] {
   178  				return
   179  			}
   180  			s = s[1:]
   181  			chunk = chunk[1:]
   182  		}
   183  	}
   184  	return s, true, nil
   185  }
   186  
   187  // getEsc gets a possibly-escaped character from chunk, for a character class.
   188  func getEsc(chunk string) (r rune, nchunk string, err error) {
   189  	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
   190  		err = ErrBadPattern
   191  		return
   192  	}
   193  	if chunk[0] == '\\' {
   194  		chunk = chunk[1:]
   195  		if len(chunk) == 0 {
   196  			err = ErrBadPattern
   197  			return
   198  		}
   199  	}
   200  	r, n := utf8.DecodeRuneInString(chunk)
   201  	if r == utf8.RuneError && n == 1 {
   202  		err = ErrBadPattern
   203  	}
   204  	nchunk = chunk[n:]
   205  	if len(nchunk) == 0 {
   206  		err = ErrBadPattern
   207  	}
   208  	return
   209  }
   210  

View as plain text