src/path/filepath/match.go - go - Git at Google

 // Copyright 2010 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package filepath

 import (
 	"errors"
 	"os"
 	"runtime"
 	"sort"
 	"strings"
 	"unicode/utf8"
 )

 // ErrBadPattern indicates a pattern was malformed.
 var ErrBadPattern = errors.New("syntax error in pattern")

 // Match reports whether name matches the shell file name pattern.
 // The pattern syntax is:
 //
 //	pattern:
 //		{ term }
 //	term:
 //		'*'         matches any sequence of non-Separator characters
 //		'?'         matches any single non-Separator character
 //		'[' [ '^' ] { character-range } ']'
 //		            character class (must be non-empty)
 //		c           matches character c (c != '*', '?', '\\', '[')
 //		'\\' c      matches character c
 //
 //	character-range:
 //		c           matches character c (c != '\\', '-', ']')
 //		'\\' c      matches character c
 //		lo '-' hi   matches character c for lo <= c <= hi
 //
 // Match requires pattern to match all of name, not just a substring.
 // The only possible returned error is ErrBadPattern, when pattern
 // is malformed.
 //
 // On Windows, escaping is disabled. Instead, '\\' is treated as
 // path separator.
 func Match(pattern, name string) (matched bool, err error) {
 Pattern:
 	for len(pattern) > 0 {
 		var star bool
 		var chunk string
 		star, chunk, pattern = scanChunk(pattern)
 		if star && chunk == "" {
 			// Trailing * matches rest of string unless it has a /.
 			return !strings.Contains(name, string(Separator)), nil
 		}
 		// Look for match at current position.
 		t, ok, err := matchChunk(chunk, name)
 		// if we're the last chunk, make sure we've exhausted the name
 		// otherwise we'll give a false result even if we could still match
 		// using the star
 		if ok && (len(t) == 0 || len(pattern) > 0) {
 			name = t
 			continue
 		}
 		if err != nil {
 			return false, err
 		}
 		if star {
 			// Look for match skipping i+1 bytes.
 			// Cannot skip /.
 			for i := 0; i < len(name) && name[i] != Separator; i++ {
 				t, ok, err := matchChunk(chunk, name[i+1:])
 				if ok {
 					// if we're the last chunk, make sure we exhausted the name
 					if len(pattern) == 0 && len(t) > 0 {
 						continue
 					}
 					name = t
 					continue Pattern
 				}
 				if err != nil {
 					return false, err
 				}
 			}
 		}
 		return false, nil
 	}
 	return len(name) == 0, nil
 }

 // scanChunk gets the next segment of pattern, which is a non-star string
 // possibly preceded by a star.
 func scanChunk(pattern string) (star bool, chunk, rest string) {
 	for len(pattern) > 0 && pattern[0] == '*' {
 		pattern = pattern[1:]
 		star = true
 	}
 	inrange := false
 	var i int
 Scan:
 	for i = 0; i < len(pattern); i++ {
 		switch pattern[i] {
 		case '\\':
 			if runtime.GOOS != "windows" {
 				// error check handled in matchChunk: bad pattern.
 				if i+1 < len(pattern) {
 					i++
 				}
 			}
 		case '[':
 			inrange = true
 		case ']':
 			inrange = false
 		case '*':
 			if !inrange {
 				break Scan
 			}
 		}
 	}
 	return star, pattern[0:i], pattern[i:]
 }

 // matchChunk checks whether chunk matches the beginning of s.
 // If so, it returns the remainder of s (after the match).
 // Chunk is all single-character operators: literals, char classes, and ?.
 func matchChunk(chunk, s string) (rest string, ok bool, err error) {
 	// failed records whether the match has failed.
 	// After the match fails, the loop continues on processing chunk,
 	// checking that the pattern is well-formed but no longer reading s.
 	failed := false
 	for len(chunk) > 0 {
 		if !failed && len(s) == 0 {
 			failed = true
 		}
 		switch chunk[0] {
 		case '[':
 			// character class
 			var r rune
 			if !failed {
 				var n int
 				r, n = utf8.DecodeRuneInString(s)
 				s = s[n:]
 			}
 			chunk = chunk[1:]
 			// possibly negated
 			negated := false
 			if len(chunk) > 0 && chunk[0] == '^' {
 				negated = true
 				chunk = chunk[1:]
 			}
 			// parse all ranges
 			match := false
 			nrange := 0
 			for {
 				if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
 					chunk = chunk[1:]
 					break
 				}
 				var lo, hi rune
 				if lo, chunk, err = getEsc(chunk); err != nil {
 					return "", false, err
 				}
 				hi = lo
 				if chunk[0] == '-' {
 					if hi, chunk, err = getEsc(chunk[1:]); err != nil {
 						return "", false, err
 					}
 				}
 				if lo <= r && r <= hi {
 					match = true
 				}
 				nrange++
 			}
 			if match == negated {
 				failed = true
 			}

 		case '?':
 			if !failed {
 				if s[0] == Separator {
 					failed = true
 				}
 				_, n := utf8.DecodeRuneInString(s)
 				s = s[n:]
 			}
 			chunk = chunk[1:]

 		case '\\':
 			if runtime.GOOS != "windows" {
 				chunk = chunk[1:]
 				if len(chunk) == 0 {
 					return "", false, ErrBadPattern
 				}
 			}
 			fallthrough

 		default:
 			if !failed {
 				if chunk[0] != s[0] {
 					failed = true
 				}
 				s = s[1:]
 			}
 			chunk = chunk[1:]
 		}
 	}
 	if failed {
 		return "", false, nil
 	}
 	return s, true, nil
 }

 // getEsc gets a possibly-escaped character from chunk, for a character class.
 func getEsc(chunk string) (r rune, nchunk string, err error) {
 	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
 		err = ErrBadPattern
 		return
 	}
 	if chunk[0] == '\\' && runtime.GOOS != "windows" {
 		chunk = chunk[1:]
 		if len(chunk) == 0 {
 			err = ErrBadPattern
 			return
 		}
 	}
 	r, n := utf8.DecodeRuneInString(chunk)
 	if r == utf8.RuneError && n == 1 {
 		err = ErrBadPattern
 	}
 	nchunk = chunk[n:]
 	if len(nchunk) == 0 {
 		err = ErrBadPattern
 	}
 	return
 }

 // Glob returns the names of all files matching pattern or nil
 // if there is no matching file. The syntax of patterns is the same
 // as in Match. The pattern may describe hierarchical names such as
 // /usr/*/bin/ed (assuming the Separator is '/').
 //
 // Glob ignores file system errors such as I/O errors reading directories.
 // The only possible returned error is ErrBadPattern, when pattern
 // is malformed.
 func Glob(pattern string) (matches []string, err error) {
 	return globWithLimit(pattern, 0)
 }

 func globWithLimit(pattern string, depth int) (matches []string, err error) {
 	// This limit is used prevent stack exhaustion issues. See CVE-2022-30632.
 	const pathSeparatorsLimit = 10000
 	if depth == pathSeparatorsLimit {
 		return nil, ErrBadPattern
 	}

 	// Check pattern is well-formed.
 	if _, err := Match(pattern, ""); err != nil {
 		return nil, err
 	}
 	if !hasMeta(pattern) {
 		if _, err = os.Lstat(pattern); err != nil {
 			return nil, nil
 		}
 		return []string{pattern}, nil
 	}

 	dir, file := Split(pattern)
 	volumeLen := 0
 	if runtime.GOOS == "windows" {
 		volumeLen, dir = cleanGlobPathWindows(dir)
 	} else {
 		dir = cleanGlobPath(dir)
 	}

 	if !hasMeta(dir[volumeLen:]) {
 		return glob(dir, file, nil)
 	}

 	// Prevent infinite recursion. See issue 15879.
 	if dir == pattern {
 		return nil, ErrBadPattern
 	}

 	var m []string
 	m, err = globWithLimit(dir, depth+1)
 	if err != nil {
 		return
 	}
 	for _, d := range m {
 		matches, err = glob(d, file, matches)
 		if err != nil {
 			return
 		}
 	}
 	return
 }

 // cleanGlobPath prepares path for glob matching.
 func cleanGlobPath(path string) string {
 	switch path {
 	case "":
 		return "."
 	case string(Separator):
 		// do nothing to the path
 		return path
 	default:
 		return path[0 : len(path)-1] // chop off trailing separator
 	}
 }

 // cleanGlobPathWindows is windows version of cleanGlobPath.
 func cleanGlobPathWindows(path string) (prefixLen int, cleaned string) {
 	vollen := volumeNameLen(path)
 	switch {
 	case path == "":
 		return 0, "."
 	case vollen+1 == len(path) && os.IsPathSeparator(path[len(path)-1]): // /, \, C:\ and C:/
 		// do nothing to the path
 		return vollen + 1, path
 	case vollen == len(path) && len(path) == 2: // C:
 		return vollen, path + "." // convert C: into C:.
 	default:
 		if vollen >= len(path) {
 			vollen = len(path) - 1
 		}
 		return vollen, path[0 : len(path)-1] // chop off trailing separator
 	}
 }

 // glob searches for files matching pattern in the directory dir
 // and appends them to matches. If the directory cannot be
 // opened, it returns the existing matches. New matches are
 // added in lexicographical order.
 func glob(dir, pattern string, matches []string) (m []string, e error) {
 	m = matches
 	fi, err := os.Stat(dir)
 	if err != nil {
 		return // ignore I/O error
 	}
 	if !fi.IsDir() {
 		return // ignore I/O error
 	}
 	d, err := os.Open(dir)
 	if err != nil {
 		return // ignore I/O error
 	}
 	defer d.Close()

 	names, _ := d.Readdirnames(-1)
 	sort.Strings(names)

 	for _, n := range names {
 		matched, err := Match(pattern, n)
 		if err != nil {
 			return m, err
 		}
 		if matched {
 			m = append(m, Join(dir, n))
 		}
 	}
 	return
 }

 // hasMeta reports whether path contains any of the magic characters
 // recognized by Match.
 func hasMeta(path string) bool {
 	magicChars := `*?[`
 	if runtime.GOOS != "windows" {
 		magicChars = `*?[\`
 	}
 	return strings.ContainsAny(path, magicChars)
 }
	// Copyright 2010 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package filepath

	import (
	"errors"
	"os"
	"runtime"
	"sort"
	"strings"
	"unicode/utf8"
	)

	// ErrBadPattern indicates a pattern was malformed.
	var ErrBadPattern = errors.New("syntax error in pattern")

	// Match reports whether name matches the shell file name pattern.
	// The pattern syntax is:
	//
	// pattern:
	// { term }
	// term:
	// '*' matches any sequence of non-Separator characters
	// '?' matches any single non-Separator character
	// '[' [ '^' ] { character-range } ']'
	// character class (must be non-empty)
	// c matches character c (c != '*', '?', '\\', '[')
	// '\\' c matches character c
	//
	// character-range:
	// c matches character c (c != '\\', '-', ']')
	// '\\' c matches character c
	// lo '-' hi matches character c for lo <= c <= hi
	//
	// Match requires pattern to match all of name, not just a substring.
	// The only possible returned error is ErrBadPattern, when pattern
	// is malformed.
	//
	// On Windows, escaping is disabled. Instead, '\\' is treated as
	// path separator.
	func Match(pattern, name string) (matched bool, err error) {
	Pattern:
	for len(pattern) > 0 {
	var star bool
	var chunk string
	star, chunk, pattern = scanChunk(pattern)
	if star && chunk == "" {
	// Trailing * matches rest of string unless it has a /.
	return !strings.Contains(name, string(Separator)), nil
	}
	// Look for match at current position.
	t, ok, err := matchChunk(chunk, name)
	// if we're the last chunk, make sure we've exhausted the name
	// otherwise we'll give a false result even if we could still match
	// using the star
	if ok && (len(t) == 0 \|\| len(pattern) > 0) {
	name = t
	continue
	}
	if err != nil {
	return false, err
	}
	if star {
	// Look for match skipping i+1 bytes.
	// Cannot skip /.
	for i := 0; i < len(name) && name[i] != Separator; i++ {
	t, ok, err := matchChunk(chunk, name[i+1:])
	if ok {
	// if we're the last chunk, make sure we exhausted the name
	if len(pattern) == 0 && len(t) > 0 {
	continue
	}
	name = t
	continue Pattern
	}
	if err != nil {
	return false, err
	}
	}
	}
	return false, nil
	}
	return len(name) == 0, nil
	}

	// scanChunk gets the next segment of pattern, which is a non-star string
	// possibly preceded by a star.
	func scanChunk(pattern string) (star bool, chunk, rest string) {
	for len(pattern) > 0 && pattern[0] == '*' {
	pattern = pattern[1:]
	star = true
	}
	inrange := false
	var i int
	Scan:
	for i = 0; i < len(pattern); i++ {
	switch pattern[i] {
	case '\\':
	if runtime.GOOS != "windows" {
	// error check handled in matchChunk: bad pattern.
	if i+1 < len(pattern) {
	i++
	}
	}
	case '[':
	inrange = true
	case ']':
	inrange = false
	case '*':
	if !inrange {
	break Scan
	}
	}
	}
	return star, pattern[0:i], pattern[i:]
	}

	// matchChunk checks whether chunk matches the beginning of s.
	// If so, it returns the remainder of s (after the match).
	// Chunk is all single-character operators: literals, char classes, and ?.
	func matchChunk(chunk, s string) (rest string, ok bool, err error) {
	// failed records whether the match has failed.
	// After the match fails, the loop continues on processing chunk,
	// checking that the pattern is well-formed but no longer reading s.
	failed := false
	for len(chunk) > 0 {
	if !failed && len(s) == 0 {
	failed = true
	}
	switch chunk[0] {
	case '[':
	// character class
	var r rune
	if !failed {
	var n int
	r, n = utf8.DecodeRuneInString(s)
	s = s[n:]
	}
	chunk = chunk[1:]
	// possibly negated
	negated := false
	if len(chunk) > 0 && chunk[0] == '^' {
	negated = true
	chunk = chunk[1:]
	}
	// parse all ranges
	match := false
	nrange := 0
	for {
	if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
	chunk = chunk[1:]
	break
	}
	var lo, hi rune
	if lo, chunk, err = getEsc(chunk); err != nil {
	return "", false, err
	}
	hi = lo
	if chunk[0] == '-' {
	if hi, chunk, err = getEsc(chunk[1:]); err != nil {
	return "", false, err
	}
	}
	if lo <= r && r <= hi {
	match = true
	}
	nrange++
	}
	if match == negated {
	failed = true
	}

	case '?':
	if !failed {
	if s[0] == Separator {
	failed = true
	}
	_, n := utf8.DecodeRuneInString(s)
	s = s[n:]
	}
	chunk = chunk[1:]

	case '\\':
	if runtime.GOOS != "windows" {
	chunk = chunk[1:]
	if len(chunk) == 0 {
	return "", false, ErrBadPattern
	}
	}
	fallthrough

	default:
	if !failed {
	if chunk[0] != s[0] {
	failed = true
	}
	s = s[1:]
	}
	chunk = chunk[1:]
	}
	}
	if failed {
	return "", false, nil
	}
	return s, true, nil
	}

	// getEsc gets a possibly-escaped character from chunk, for a character class.
	func getEsc(chunk string) (r rune, nchunk string, err error) {
	if len(chunk) == 0 \|\| chunk[0] == '-' \|\| chunk[0] == ']' {
	err = ErrBadPattern
	return
	}
	if chunk[0] == '\\' && runtime.GOOS != "windows" {
	chunk = chunk[1:]
	if len(chunk) == 0 {
	err = ErrBadPattern
	return
	}
	}
	r, n := utf8.DecodeRuneInString(chunk)
	if r == utf8.RuneError && n == 1 {
	err = ErrBadPattern
	}
	nchunk = chunk[n:]
	if len(nchunk) == 0 {
	err = ErrBadPattern
	}
	return
	}

	// Glob returns the names of all files matching pattern or nil
	// if there is no matching file. The syntax of patterns is the same
	// as in Match. The pattern may describe hierarchical names such as
	// /usr/*/bin/ed (assuming the Separator is '/').
	//
	// Glob ignores file system errors such as I/O errors reading directories.
	// The only possible returned error is ErrBadPattern, when pattern
	// is malformed.
	func Glob(pattern string) (matches []string, err error) {
	return globWithLimit(pattern, 0)
	}

	func globWithLimit(pattern string, depth int) (matches []string, err error) {
	// This limit is used prevent stack exhaustion issues. See CVE-2022-30632.
	const pathSeparatorsLimit = 10000
	if depth == pathSeparatorsLimit {
	return nil, ErrBadPattern
	}

	// Check pattern is well-formed.
	if _, err := Match(pattern, ""); err != nil {
	return nil, err
	}
	if !hasMeta(pattern) {
	if _, err = os.Lstat(pattern); err != nil {
	return nil, nil
	}
	return []string{pattern}, nil
	}

	dir, file := Split(pattern)
	volumeLen := 0
	if runtime.GOOS == "windows" {
	volumeLen, dir = cleanGlobPathWindows(dir)
	} else {
	dir = cleanGlobPath(dir)
	}

	if !hasMeta(dir[volumeLen:]) {
	return glob(dir, file, nil)
	}

	// Prevent infinite recursion. See issue 15879.
	if dir == pattern {
	return nil, ErrBadPattern
	}

	var m []string
	m, err = globWithLimit(dir, depth+1)
	if err != nil {
	return
	}
	for _, d := range m {
	matches, err = glob(d, file, matches)
	if err != nil {
	return
	}
	}
	return
	}

	// cleanGlobPath prepares path for glob matching.
	func cleanGlobPath(path string) string {
	switch path {
	case "":
	return "."
	case string(Separator):
	// do nothing to the path
	return path
	default:
	return path[0 : len(path)-1] // chop off trailing separator
	}
	}

	// cleanGlobPathWindows is windows version of cleanGlobPath.
	func cleanGlobPathWindows(path string) (prefixLen int, cleaned string) {
	vollen := volumeNameLen(path)
	switch {
	case path == "":
	return 0, "."
	case vollen+1 == len(path) && os.IsPathSeparator(path[len(path)-1]): // /, \, C:\ and C:/
	// do nothing to the path
	return vollen + 1, path
	case vollen == len(path) && len(path) == 2: // C:
	return vollen, path + "." // convert C: into C:.
	default:
	if vollen >= len(path) {
	vollen = len(path) - 1
	}
	return vollen, path[0 : len(path)-1] // chop off trailing separator
	}
	}

	// glob searches for files matching pattern in the directory dir
	// and appends them to matches. If the directory cannot be
	// opened, it returns the existing matches. New matches are
	// added in lexicographical order.
	func glob(dir, pattern string, matches []string) (m []string, e error) {
	m = matches
	fi, err := os.Stat(dir)
	if err != nil {
	return // ignore I/O error
	}
	if !fi.IsDir() {
	return // ignore I/O error
	}
	d, err := os.Open(dir)
	if err != nil {
	return // ignore I/O error
	}
	defer d.Close()

	names, _ := d.Readdirnames(-1)
	sort.Strings(names)

	for _, n := range names {
	matched, err := Match(pattern, n)
	if err != nil {
	return m, err
	}
	if matched {
	m = append(m, Join(dir, n))
	}
	}
	return
	}

	// hasMeta reports whether path contains any of the magic characters
	// recognized by Match.
	func hasMeta(path string) bool {
	magicChars := `*?[`
	if runtime.GOOS != "windows" {
	magicChars = `*?[\`
	}
	return strings.ContainsAny(path, magicChars)
	}