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 globbing pattern was malformed.
    17	var ErrBadPattern = errors.New("syntax error in pattern")
    18	
    19	// Match returns true if 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.Index(name, string(Separator)) < 0, 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				// possibly negated
   136				negated := chunk[0] == '^'
   137				if negated {
   138					chunk = chunk[1:]
   139				}
   140				// parse all ranges
   141				match := false
   142				nrange := 0
   143				for {
   144					if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
   145						chunk = chunk[1:]
   146						break
   147					}
   148					var lo, hi rune
   149					if lo, chunk, err = getEsc(chunk); err != nil {
   150						return
   151					}
   152					hi = lo
   153					if chunk[0] == '-' {
   154						if hi, chunk, err = getEsc(chunk[1:]); err != nil {
   155							return
   156						}
   157					}
   158					if lo <= r && r <= hi {
   159						match = true
   160					}
   161					nrange++
   162				}
   163				if match == negated {
   164					return
   165				}
   166	
   167			case '?':
   168				if s[0] == Separator {
   169					return
   170				}
   171				_, n := utf8.DecodeRuneInString(s)
   172				s = s[n:]
   173				chunk = chunk[1:]
   174	
   175			case '\\':
   176				if runtime.GOOS != "windows" {
   177					chunk = chunk[1:]
   178					if len(chunk) == 0 {
   179						err = ErrBadPattern
   180						return
   181					}
   182				}
   183				fallthrough
   184	
   185			default:
   186				if chunk[0] != s[0] {
   187					return
   188				}
   189				s = s[1:]
   190				chunk = chunk[1:]
   191			}
   192		}
   193		return s, true, nil
   194	}
   195	
   196	// getEsc gets a possibly-escaped character from chunk, for a character class.
   197	func getEsc(chunk string) (r rune, nchunk string, err error) {
   198		if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
   199			err = ErrBadPattern
   200			return
   201		}
   202		if chunk[0] == '\\' && runtime.GOOS != "windows" {
   203			chunk = chunk[1:]
   204			if len(chunk) == 0 {
   205				err = ErrBadPattern
   206				return
   207			}
   208		}
   209		r, n := utf8.DecodeRuneInString(chunk)
   210		if r == utf8.RuneError && n == 1 {
   211			err = ErrBadPattern
   212		}
   213		nchunk = chunk[n:]
   214		if len(nchunk) == 0 {
   215			err = ErrBadPattern
   216		}
   217		return
   218	}
   219	
   220	// Glob returns the names of all files matching pattern or nil
   221	// if there is no matching file. The syntax of patterns is the same
   222	// as in Match. The pattern may describe hierarchical names such as
   223	// /usr/*/bin/ed (assuming the Separator is '/').
   224	//
   225	func Glob(pattern string) (matches []string, err error) {
   226		if !hasMeta(pattern) {
   227			if _, err = os.Stat(pattern); err != nil {
   228				return nil, nil
   229			}
   230			return []string{pattern}, nil
   231		}
   232	
   233		dir, file := Split(pattern)
   234		switch dir {
   235		case "":
   236			dir = "."
   237		case string(Separator):
   238			// nothing
   239		default:
   240			dir = dir[0 : len(dir)-1] // chop off trailing separator
   241		}
   242	
   243		if !hasMeta(dir) {
   244			return glob(dir, file, nil)
   245		}
   246	
   247		var m []string
   248		m, err = Glob(dir)
   249		if err != nil {
   250			return
   251		}
   252		for _, d := range m {
   253			matches, err = glob(d, file, matches)
   254			if err != nil {
   255				return
   256			}
   257		}
   258		return
   259	}
   260	
   261	// glob searches for files matching pattern in the directory dir
   262	// and appends them to matches. If the directory cannot be
   263	// opened, it returns the existing matches. New matches are
   264	// added in lexicographical order.
   265	func glob(dir, pattern string, matches []string) (m []string, e error) {
   266		m = matches
   267		fi, err := os.Stat(dir)
   268		if err != nil {
   269			return
   270		}
   271		if !fi.IsDir() {
   272			return
   273		}
   274		d, err := os.Open(dir)
   275		if err != nil {
   276			return
   277		}
   278		defer d.Close()
   279	
   280		names, err := d.Readdirnames(-1)
   281		if err != nil {
   282			return
   283		}
   284		sort.Strings(names)
   285	
   286		for _, n := range names {
   287			matched, err := Match(pattern, n)
   288			if err != nil {
   289				return m, err
   290			}
   291			if matched {
   292				m = append(m, Join(dir, n))
   293			}
   294		}
   295		return
   296	}
   297	
   298	// hasMeta returns true if path contains any of the magic characters
   299	// recognized by Match.
   300	func hasMeta(path string) bool {
   301		// TODO(niemeyer): Should other magic characters be added here?
   302		return strings.IndexAny(path, "*?[") >= 0
   303	}