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 }