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  //
		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  	// 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] == Separator {
	 179  					failed = true
	 180  				}
	 181  				_, n := utf8.DecodeRuneInString(s)
	 182  				s = s[n:]
	 183  			}
	 184  			chunk = chunk[1:]
	 185  
	 186  		case '\\':
	 187  			if runtime.GOOS != "windows" {
	 188  				chunk = chunk[1:]
	 189  				if len(chunk) == 0 {
	 190  					return "", false, ErrBadPattern
	 191  				}
	 192  			}
	 193  			fallthrough
	 194  
	 195  		default:
	 196  			if !failed {
	 197  				if chunk[0] != s[0] {
	 198  					failed = true
	 199  				}
	 200  				s = s[1:]
	 201  			}
	 202  			chunk = chunk[1:]
	 203  		}
	 204  	}
	 205  	if failed {
	 206  		return "", false, nil
	 207  	}
	 208  	return s, true, nil
	 209  }
	 210  
	 211  // getEsc gets a possibly-escaped character from chunk, for a character class.
	 212  func getEsc(chunk string) (r rune, nchunk string, err error) {
	 213  	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
	 214  		err = ErrBadPattern
	 215  		return
	 216  	}
	 217  	if chunk[0] == '\\' && runtime.GOOS != "windows" {
	 218  		chunk = chunk[1:]
	 219  		if len(chunk) == 0 {
	 220  			err = ErrBadPattern
	 221  			return
	 222  		}
	 223  	}
	 224  	r, n := utf8.DecodeRuneInString(chunk)
	 225  	if r == utf8.RuneError && n == 1 {
	 226  		err = ErrBadPattern
	 227  	}
	 228  	nchunk = chunk[n:]
	 229  	if len(nchunk) == 0 {
	 230  		err = ErrBadPattern
	 231  	}
	 232  	return
	 233  }
	 234  
	 235  // Glob returns the names of all files matching pattern or nil
	 236  // if there is no matching file. The syntax of patterns is the same
	 237  // as in Match. The pattern may describe hierarchical names such as
	 238  // /usr/*/bin/ed (assuming the Separator is '/').
	 239  //
	 240  // Glob ignores file system errors such as I/O errors reading directories.
	 241  // The only possible returned error is ErrBadPattern, when pattern
	 242  // is malformed.
	 243  func Glob(pattern string) (matches []string, err error) {
	 244  	return globWithLimit(pattern, 0)
	 245  }
	 246  
	 247  func globWithLimit(pattern string, depth int) (matches []string, err error) {
	 248  	// This limit is used prevent stack exhaustion issues. See CVE-2022-30632.
	 249  	const pathSeparatorsLimit = 10000
	 250  	if depth == pathSeparatorsLimit {
	 251  		return nil, ErrBadPattern
	 252  	}
	 253  
	 254  	// Check pattern is well-formed.
	 255  	if _, err := Match(pattern, ""); err != nil {
	 256  		return nil, err
	 257  	}
	 258  	if !hasMeta(pattern) {
	 259  		if _, err = os.Lstat(pattern); err != nil {
	 260  			return nil, nil
	 261  		}
	 262  		return []string{pattern}, nil
	 263  	}
	 264  
	 265  	dir, file := Split(pattern)
	 266  	volumeLen := 0
	 267  	if runtime.GOOS == "windows" {
	 268  		volumeLen, dir = cleanGlobPathWindows(dir)
	 269  	} else {
	 270  		dir = cleanGlobPath(dir)
	 271  	}
	 272  
	 273  	if !hasMeta(dir[volumeLen:]) {
	 274  		return glob(dir, file, nil)
	 275  	}
	 276  
	 277  	// Prevent infinite recursion. See issue 15879.
	 278  	if dir == pattern {
	 279  		return nil, ErrBadPattern
	 280  	}
	 281  
	 282  	var m []string
	 283  	m, err = globWithLimit(dir, depth+1)
	 284  	if err != nil {
	 285  		return
	 286  	}
	 287  	for _, d := range m {
	 288  		matches, err = glob(d, file, matches)
	 289  		if err != nil {
	 290  			return
	 291  		}
	 292  	}
	 293  	return
	 294  }
	 295  
	 296  // cleanGlobPath prepares path for glob matching.
	 297  func cleanGlobPath(path string) string {
	 298  	switch path {
	 299  	case "":
	 300  		return "."
	 301  	case string(Separator):
	 302  		// do nothing to the path
	 303  		return path
	 304  	default:
	 305  		return path[0 : len(path)-1] // chop off trailing separator
	 306  	}
	 307  }
	 308  
	 309  // cleanGlobPathWindows is windows version of cleanGlobPath.
	 310  func cleanGlobPathWindows(path string) (prefixLen int, cleaned string) {
	 311  	vollen := volumeNameLen(path)
	 312  	switch {
	 313  	case path == "":
	 314  		return 0, "."
	 315  	case vollen+1 == len(path) && os.IsPathSeparator(path[len(path)-1]): // /, \, C:\ and C:/
	 316  		// do nothing to the path
	 317  		return vollen + 1, path
	 318  	case vollen == len(path) && len(path) == 2: // C:
	 319  		return vollen, path + "." // convert C: into C:.
	 320  	default:
	 321  		if vollen >= len(path) {
	 322  			vollen = len(path) - 1
	 323  		}
	 324  		return vollen, path[0 : len(path)-1] // chop off trailing separator
	 325  	}
	 326  }
	 327  
	 328  // glob searches for files matching pattern in the directory dir
	 329  // and appends them to matches. If the directory cannot be
	 330  // opened, it returns the existing matches. New matches are
	 331  // added in lexicographical order.
	 332  func glob(dir, pattern string, matches []string) (m []string, e error) {
	 333  	m = matches
	 334  	fi, err := os.Stat(dir)
	 335  	if err != nil {
	 336  		return // ignore I/O error
	 337  	}
	 338  	if !fi.IsDir() {
	 339  		return // ignore I/O error
	 340  	}
	 341  	d, err := os.Open(dir)
	 342  	if err != nil {
	 343  		return // ignore I/O error
	 344  	}
	 345  	defer d.Close()
	 346  
	 347  	names, _ := d.Readdirnames(-1)
	 348  	sort.Strings(names)
	 349  
	 350  	for _, n := range names {
	 351  		matched, err := Match(pattern, n)
	 352  		if err != nil {
	 353  			return m, err
	 354  		}
	 355  		if matched {
	 356  			m = append(m, Join(dir, n))
	 357  		}
	 358  	}
	 359  	return
	 360  }
	 361  
	 362  // hasMeta reports whether path contains any of the magic characters
	 363  // recognized by Match.
	 364  func hasMeta(path string) bool {
	 365  	magicChars := `*?[`
	 366  	if runtime.GOOS != "windows" {
	 367  		magicChars = `*?[\`
	 368  	}
	 369  	return strings.ContainsAny(path, magicChars)
	 370  }
	 371
View as plain text