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