...
Run Format

Source file src/path/filepath/match.go

Documentation: path/filepath

     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 filepath
     6  
     7  import (
     8  	"errors"
     9  	"os"
    10  	"runtime"
    11  	"sort"
    12  	"strings"
    13  	"unicode/utf8"
    14  )
    15  
    16  // ErrBadPattern indicates a globbing pattern was malformed.
    17  var ErrBadPattern = errors.New("syntax error in pattern")
    18  
    19  // Match reports whether name matches the shell file name pattern.
    20  // The pattern syntax is:
    21  //
    22  //	pattern:
    23  //		{ term }
    24  //	term:
    25  //		'*'         matches any sequence of non-Separator characters
    26  //		'?'         matches any single non-Separator character
    27  //		'[' [ '^' ] { character-range } ']'
    28  //		            character class (must be non-empty)
    29  //		c           matches character c (c != '*', '?', '\\', '[')
    30  //		'\\' c      matches character c
    31  //
    32  //	character-range:
    33  //		c           matches character c (c != '\\', '-', ']')
    34  //		'\\' c      matches character c
    35  //		lo '-' hi   matches character c for lo <= c <= hi
    36  //
    37  // Match requires pattern to match all of name, not just a substring.
    38  // The only possible returned error is ErrBadPattern, when pattern
    39  // is malformed.
    40  //
    41  // On Windows, escaping is disabled. Instead, '\\' is treated as
    42  // path separator.
    43  //
    44  func Match(pattern, name string) (matched bool, err error) {
    45  Pattern:
    46  	for len(pattern) > 0 {
    47  		var star bool
    48  		var chunk string
    49  		star, chunk, pattern = scanChunk(pattern)
    50  		if star && chunk == "" {
    51  			// Trailing * matches rest of string unless it has a /.
    52  			return !strings.Contains(name, string(Separator)), nil
    53  		}
    54  		// Look for match at current position.
    55  		t, ok, err := matchChunk(chunk, name)
    56  		// if we're the last chunk, make sure we've exhausted the name
    57  		// otherwise we'll give a false result even if we could still match
    58  		// using the star
    59  		if ok && (len(t) == 0 || len(pattern) > 0) {
    60  			name = t
    61  			continue
    62  		}
    63  		if err != nil {
    64  			return false, err
    65  		}
    66  		if star {
    67  			// Look for match skipping i+1 bytes.
    68  			// Cannot skip /.
    69  			for i := 0; i < len(name) && name[i] != Separator; i++ {
    70  				t, ok, err := matchChunk(chunk, name[i+1:])
    71  				if ok {
    72  					// if we're the last chunk, make sure we exhausted the name
    73  					if len(pattern) == 0 && len(t) > 0 {
    74  						continue
    75  					}
    76  					name = t
    77  					continue Pattern
    78  				}
    79  				if err != nil {
    80  					return false, err
    81  				}
    82  			}
    83  		}
    84  		return false, nil
    85  	}
    86  	return len(name) == 0, nil
    87  }
    88  
    89  // scanChunk gets the next segment of pattern, which is a non-star string
    90  // possibly preceded by a star.
    91  func scanChunk(pattern string) (star bool, chunk, rest string) {
    92  	for len(pattern) > 0 && pattern[0] == '*' {
    93  		pattern = pattern[1:]
    94  		star = true
    95  	}
    96  	inrange := false
    97  	var i int
    98  Scan:
    99  	for i = 0; i < len(pattern); i++ {
   100  		switch pattern[i] {
   101  		case '\\':
   102  			if runtime.GOOS != "windows" {
   103  				// error check handled in matchChunk: bad pattern.
   104  				if i+1 < len(pattern) {
   105  					i++
   106  				}
   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  	for len(chunk) > 0 {
   126  		if len(s) == 0 {
   127  			return
   128  		}
   129  		switch chunk[0] {
   130  		case '[':
   131  			// character class
   132  			r, n := utf8.DecodeRuneInString(s)
   133  			s = s[n:]
   134  			chunk = chunk[1:]
   135  			// We can't end right after '[', we're expecting at least
   136  			// a closing bracket and possibly a caret.
   137  			if len(chunk) == 0 {
   138  				err = ErrBadPattern
   139  				return
   140  			}
   141  			// possibly negated
   142  			negated := chunk[0] == '^'
   143  			if negated {
   144  				chunk = chunk[1:]
   145  			}
   146  			// parse all ranges
   147  			match := false
   148  			nrange := 0
   149  			for {
   150  				if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
   151  					chunk = chunk[1:]
   152  					break
   153  				}
   154  				var lo, hi rune
   155  				if lo, chunk, err = getEsc(chunk); err != nil {
   156  					return
   157  				}
   158  				hi = lo
   159  				if chunk[0] == '-' {
   160  					if hi, chunk, err = getEsc(chunk[1:]); err != nil {
   161  						return
   162  					}
   163  				}
   164  				if lo <= r && r <= hi {
   165  					match = true
   166  				}
   167  				nrange++
   168  			}
   169  			if match == negated {
   170  				return
   171  			}
   172  
   173  		case '?':
   174  			if s[0] == Separator {
   175  				return
   176  			}
   177  			_, n := utf8.DecodeRuneInString(s)
   178  			s = s[n:]
   179  			chunk = chunk[1:]
   180  
   181  		case '\\':
   182  			if runtime.GOOS != "windows" {
   183  				chunk = chunk[1:]
   184  				if len(chunk) == 0 {
   185  					err = ErrBadPattern
   186  					return
   187  				}
   188  			}
   189  			fallthrough
   190  
   191  		default:
   192  			if chunk[0] != s[0] {
   193  				return
   194  			}
   195  			s = s[1:]
   196  			chunk = chunk[1:]
   197  		}
   198  	}
   199  	return s, true, nil
   200  }
   201  
   202  // getEsc gets a possibly-escaped character from chunk, for a character class.
   203  func getEsc(chunk string) (r rune, nchunk string, err error) {
   204  	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
   205  		err = ErrBadPattern
   206  		return
   207  	}
   208  	if chunk[0] == '\\' && runtime.GOOS != "windows" {
   209  		chunk = chunk[1:]
   210  		if len(chunk) == 0 {
   211  			err = ErrBadPattern
   212  			return
   213  		}
   214  	}
   215  	r, n := utf8.DecodeRuneInString(chunk)
   216  	if r == utf8.RuneError && n == 1 {
   217  		err = ErrBadPattern
   218  	}
   219  	nchunk = chunk[n:]
   220  	if len(nchunk) == 0 {
   221  		err = ErrBadPattern
   222  	}
   223  	return
   224  }
   225  
   226  // Glob returns the names of all files matching pattern or nil
   227  // if there is no matching file. The syntax of patterns is the same
   228  // as in Match. The pattern may describe hierarchical names such as
   229  // /usr/*/bin/ed (assuming the Separator is '/').
   230  //
   231  // Glob ignores file system errors such as I/O errors reading directories.
   232  // The only possible returned error is ErrBadPattern, when pattern
   233  // is malformed.
   234  func Glob(pattern string) (matches []string, err error) {
   235  	if !hasMeta(pattern) {
   236  		if _, err = os.Lstat(pattern); err != nil {
   237  			return nil, nil
   238  		}
   239  		return []string{pattern}, nil
   240  	}
   241  
   242  	dir, file := Split(pattern)
   243  	volumeLen := 0
   244  	if runtime.GOOS == "windows" {
   245  		volumeLen, dir = cleanGlobPathWindows(dir)
   246  	} else {
   247  		dir = cleanGlobPath(dir)
   248  	}
   249  
   250  	if !hasMeta(dir[volumeLen:]) {
   251  		return glob(dir, file, nil)
   252  	}
   253  
   254  	// Prevent infinite recursion. See issue 15879.
   255  	if dir == pattern {
   256  		return nil, ErrBadPattern
   257  	}
   258  
   259  	var m []string
   260  	m, err = Glob(dir)
   261  	if err != nil {
   262  		return
   263  	}
   264  	for _, d := range m {
   265  		matches, err = glob(d, file, matches)
   266  		if err != nil {
   267  			return
   268  		}
   269  	}
   270  	return
   271  }
   272  
   273  // cleanGlobPath prepares path for glob matching.
   274  func cleanGlobPath(path string) string {
   275  	switch path {
   276  	case "":
   277  		return "."
   278  	case string(Separator):
   279  		// do nothing to the path
   280  		return path
   281  	default:
   282  		return path[0 : len(path)-1] // chop off trailing separator
   283  	}
   284  }
   285  
   286  // cleanGlobPathWindows is windows version of cleanGlobPath.
   287  func cleanGlobPathWindows(path string) (prefixLen int, cleaned string) {
   288  	vollen := volumeNameLen(path)
   289  	switch {
   290  	case path == "":
   291  		return 0, "."
   292  	case vollen+1 == len(path) && os.IsPathSeparator(path[len(path)-1]): // /, \, C:\ and C:/
   293  		// do nothing to the path
   294  		return vollen + 1, path
   295  	case vollen == len(path) && len(path) == 2: // C:
   296  		return vollen, path + "." // convert C: into C:.
   297  	default:
   298  		if vollen >= len(path) {
   299  			vollen = len(path) - 1
   300  		}
   301  		return vollen, path[0 : len(path)-1] // chop off trailing separator
   302  	}
   303  }
   304  
   305  // glob searches for files matching pattern in the directory dir
   306  // and appends them to matches. If the directory cannot be
   307  // opened, it returns the existing matches. New matches are
   308  // added in lexicographical order.
   309  func glob(dir, pattern string, matches []string) (m []string, e error) {
   310  	m = matches
   311  	fi, err := os.Stat(dir)
   312  	if err != nil {
   313  		return
   314  	}
   315  	if !fi.IsDir() {
   316  		return
   317  	}
   318  	d, err := os.Open(dir)
   319  	if err != nil {
   320  		return
   321  	}
   322  	defer d.Close()
   323  
   324  	names, _ := d.Readdirnames(-1)
   325  	sort.Strings(names)
   326  
   327  	for _, n := range names {
   328  		matched, err := Match(pattern, n)
   329  		if err != nil {
   330  			return m, err
   331  		}
   332  		if matched {
   333  			m = append(m, Join(dir, n))
   334  		}
   335  	}
   336  	return
   337  }
   338  
   339  // hasMeta reports whether path contains any of the magic characters
   340  // recognized by Match.
   341  func hasMeta(path string) bool {
   342  	// TODO(niemeyer): Should other magic characters be added here?
   343  	return strings.ContainsAny(path, "*?[")
   344  }
   345  

View as plain text