libgo/go/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 }