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 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  func Match(pattern, name string) (matched bool, err error) {
    44  Pattern:
    45  	for len(pattern) > 0 {
    46  		var star bool
    47  		var chunk string
    48  		star, chunk, pattern = scanChunk(pattern)
    49  		if star && chunk == "" {
    50  			// Trailing * matches rest of string unless it has a /.
    51  			return !strings.Contains(name, string(Separator)), nil
    52  		}
    53  		// Look for match at current position.
    54  		t, ok, err := matchChunk(chunk, name)
    55  		// if we're the last chunk, make sure we've exhausted the name
    56  		// otherwise we'll give a false result even if we could still match
    57  		// using the star
    58  		if ok && (len(t) == 0 || len(pattern) > 0) {
    59  			name = t
    60  			continue
    61  		}
    62  		if err != nil {
    63  			return false, err
    64  		}
    65  		if star {
    66  			// Look for match skipping i+1 bytes.
    67  			// Cannot skip /.
    68  			for i := 0; i < len(name) && name[i] != Separator; i++ {
    69  				t, ok, err := matchChunk(chunk, name[i+1:])
    70  				if ok {
    71  					// if we're the last chunk, make sure we exhausted the name
    72  					if len(pattern) == 0 && len(t) > 0 {
    73  						continue
    74  					}
    75  					name = t
    76  					continue Pattern
    77  				}
    78  				if err != nil {
    79  					return false, err
    80  				}
    81  			}
    82  		}
    83  		return false, nil
    84  	}
    85  	return len(name) == 0, nil
    86  }
    87  
    88  // scanChunk gets the next segment of pattern, which is a non-star string
    89  // possibly preceded by a star.
    90  func scanChunk(pattern string) (star bool, chunk, rest string) {
    91  	for len(pattern) > 0 && pattern[0] == '*' {
    92  		pattern = pattern[1:]
    93  		star = true
    94  	}
    95  	inrange := false
    96  	var i int
    97  Scan:
    98  	for i = 0; i < len(pattern); i++ {
    99  		switch pattern[i] {
   100  		case '\\':
   101  			if runtime.GOOS != "windows" {
   102  				// error check handled in matchChunk: bad pattern.
   103  				if i+1 < len(pattern) {
   104  					i++
   105  				}
   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  				if s[0] == Separator {
   178  					failed = true
   179  				}
   180  				_, n := utf8.DecodeRuneInString(s)
   181  				s = s[n:]
   182  			}
   183  			chunk = chunk[1:]
   184  
   185  		case '\\':
   186  			if runtime.GOOS != "windows" {
   187  				chunk = chunk[1:]
   188  				if len(chunk) == 0 {
   189  					return "", false, ErrBadPattern
   190  				}
   191  			}
   192  			fallthrough
   193  
   194  		default:
   195  			if !failed {
   196  				if chunk[0] != s[0] {
   197  					failed = true
   198  				}
   199  				s = s[1:]
   200  			}
   201  			chunk = chunk[1:]
   202  		}
   203  	}
   204  	if failed {
   205  		return "", false, nil
   206  	}
   207  	return s, true, nil
   208  }
   209  
   210  // getEsc gets a possibly-escaped character from chunk, for a character class.
   211  func getEsc(chunk string) (r rune, nchunk string, err error) {
   212  	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
   213  		err = ErrBadPattern
   214  		return
   215  	}
   216  	if chunk[0] == '\\' && runtime.GOOS != "windows" {
   217  		chunk = chunk[1:]
   218  		if len(chunk) == 0 {
   219  			err = ErrBadPattern
   220  			return
   221  		}
   222  	}
   223  	r, n := utf8.DecodeRuneInString(chunk)
   224  	if r == utf8.RuneError && n == 1 {
   225  		err = ErrBadPattern
   226  	}
   227  	nchunk = chunk[n:]
   228  	if len(nchunk) == 0 {
   229  		err = ErrBadPattern
   230  	}
   231  	return
   232  }
   233  
   234  // Glob returns the names of all files matching pattern or nil
   235  // if there is no matching file. The syntax of patterns is the same
   236  // as in [Match]. The pattern may describe hierarchical names such as
   237  // /usr/*/bin/ed (assuming the [Separator] is '/').
   238  //
   239  // Glob ignores file system errors such as I/O errors reading directories.
   240  // The only possible returned error is [ErrBadPattern], when pattern
   241  // is malformed.
   242  func Glob(pattern string) (matches []string, err error) {
   243  	return globWithLimit(pattern, 0)
   244  }
   245  
   246  func globWithLimit(pattern string, depth int) (matches []string, err error) {
   247  	// This limit is used prevent stack exhaustion issues. See CVE-2022-30632.
   248  	const pathSeparatorsLimit = 10000
   249  	if depth == pathSeparatorsLimit {
   250  		return nil, ErrBadPattern
   251  	}
   252  
   253  	// Check pattern is well-formed.
   254  	if _, err := Match(pattern, ""); err != nil {
   255  		return nil, err
   256  	}
   257  	if !hasMeta(pattern) {
   258  		if _, err = os.Lstat(pattern); err != nil {
   259  			return nil, nil
   260  		}
   261  		return []string{pattern}, nil
   262  	}
   263  
   264  	dir, file := Split(pattern)
   265  	volumeLen := 0
   266  	if runtime.GOOS == "windows" {
   267  		volumeLen, dir = cleanGlobPathWindows(dir)
   268  	} else {
   269  		dir = cleanGlobPath(dir)
   270  	}
   271  
   272  	if !hasMeta(dir[volumeLen:]) {
   273  		return glob(dir, file, nil)
   274  	}
   275  
   276  	// Prevent infinite recursion. See issue 15879.
   277  	if dir == pattern {
   278  		return nil, ErrBadPattern
   279  	}
   280  
   281  	var m []string
   282  	m, err = globWithLimit(dir, depth+1)
   283  	if err != nil {
   284  		return
   285  	}
   286  	for _, d := range m {
   287  		matches, err = glob(d, file, matches)
   288  		if err != nil {
   289  			return
   290  		}
   291  	}
   292  	return
   293  }
   294  
   295  // cleanGlobPath prepares path for glob matching.
   296  func cleanGlobPath(path string) string {
   297  	switch path {
   298  	case "":
   299  		return "."
   300  	case string(Separator):
   301  		// do nothing to the path
   302  		return path
   303  	default:
   304  		return path[0 : len(path)-1] // chop off trailing separator
   305  	}
   306  }
   307  
   308  // cleanGlobPathWindows is windows version of cleanGlobPath.
   309  func cleanGlobPathWindows(path string) (prefixLen int, cleaned string) {
   310  	vollen := volumeNameLen(path)
   311  	switch {
   312  	case path == "":
   313  		return 0, "."
   314  	case vollen+1 == len(path) && os.IsPathSeparator(path[len(path)-1]): // /, \, C:\ and C:/
   315  		// do nothing to the path
   316  		return vollen + 1, path
   317  	case vollen == len(path) && len(path) == 2: // C:
   318  		return vollen, path + "." // convert C: into C:.
   319  	default:
   320  		if vollen >= len(path) {
   321  			vollen = len(path) - 1
   322  		}
   323  		return vollen, path[0 : len(path)-1] // chop off trailing separator
   324  	}
   325  }
   326  
   327  // glob searches for files matching pattern in the directory dir
   328  // and appends them to matches. If the directory cannot be
   329  // opened, it returns the existing matches. New matches are
   330  // added in lexicographical order.
   331  func glob(dir, pattern string, matches []string) (m []string, e error) {
   332  	m = matches
   333  	fi, err := os.Stat(dir)
   334  	if err != nil {
   335  		return // ignore I/O error
   336  	}
   337  	if !fi.IsDir() {
   338  		return // ignore I/O error
   339  	}
   340  	d, err := os.Open(dir)
   341  	if err != nil {
   342  		return // ignore I/O error
   343  	}
   344  	defer d.Close()
   345  
   346  	names, _ := d.Readdirnames(-1)
   347  	sort.Strings(names)
   348  
   349  	for _, n := range names {
   350  		matched, err := Match(pattern, n)
   351  		if err != nil {
   352  			return m, err
   353  		}
   354  		if matched {
   355  			m = append(m, Join(dir, n))
   356  		}
   357  	}
   358  	return
   359  }
   360  
   361  // hasMeta reports whether path contains any of the magic characters
   362  // recognized by Match.
   363  func hasMeta(path string) bool {
   364  	magicChars := `*?[`
   365  	if runtime.GOOS != "windows" {
   366  		magicChars = `*?[\`
   367  	}
   368  	return strings.ContainsAny(path, magicChars)
   369  }
   370
View as plain text