Source file src/pkg/path/filepath/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		"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		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		magicChars := `*?[`
   343		if runtime.GOOS != "windows" {
   344			magicChars = `*?[\`
   345		}
   346		return strings.ContainsAny(path, magicChars)
   347	}
   348	

View as plain text