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         // failed records whether the match has failed.
 126         // After the match fails, the loop continues on processing chunk,
 127         // checking that the pattern is well-formed but no longer reading s.
 128         failed := false
 129         for len(chunk) > 0 {
 130                 if !failed && len(s) == 0 {
 131                         failed = true
 132                 }
 133                 switch chunk[0] {
 134                 case '[':
 135                         // character class
 136                         var r rune
 137                         if !failed {
 138                                 var n int
 139                                 r, n = utf8.DecodeRuneInString(s)
 140                                 s = s[n:]
 141                         }
 142                         chunk = chunk[1:]
 143                         // possibly negated
 144                         negated := false
 145                         if len(chunk) > 0 && chunk[0] == '^' {
 146                                 negated = true
 147                                 chunk = chunk[1:]
 148                         }
 149                         // parse all ranges
 150                         match := false
 151                         nrange := 0
 152                         for {
 153                                 if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
 154                                         chunk = chunk[1:]
 155                                         break
 156                                 }
 157                                 var lo, hi rune
 158                                 if lo, chunk, err = getEsc(chunk); err != nil {
 159                                         return "", false, err
 160                                 }
 161                                 hi = lo
 162                                 if chunk[0] == '-' {
 163                                         if hi, chunk, err = getEsc(chunk[1:]); err != nil {
 164                                                 return "", false, err
 165                                         }
 166                                 }
 167                                 if lo <= r && r <= hi {
 168                                         match = true
 169                                 }
 170                                 nrange++
 171                         }
 172                         if match == negated {
 173                                 failed = true
 174                         }
 175
 176                 case '?':
 177                         if !failed {
 178                                 if s[0] == Separator {
 179                                         failed = true
 180                                 }
 181                                 _, n := utf8.DecodeRuneInString(s)
 182                                 s = s[n:]
 183                         }
 184                         chunk = chunk[1:]
 185
 186                 case '\\':
 187                         if runtime.GOOS != "windows" {
 188                                 chunk = chunk[1:]
 189                                 if len(chunk) == 0 {
 190                                         return "", false, ErrBadPattern
 191                                 }
 192                         }
 193                         fallthrough
 194
 195                 default:
 196                         if !failed {
 197                                 if chunk[0] != s[0] {
 198                                         failed = true
 199                                 }
 200                                 s = s[1:]
 201                         }
 202                         chunk = chunk[1:]
 203                 }
 204         }
 205         if failed {
 206                 return "", false, nil
 207         }
 208         return s, true, nil
 209 }
 210
 211 // getEsc gets a possibly-escaped character from chunk, for a character class.
 212 func getEsc(chunk string) (r rune, nchunk string, err error) {
 213         if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
 214                 err = ErrBadPattern
 215                 return
 216         }
 217         if chunk[0] == '\\' && runtime.GOOS != "windows" {
 218                 chunk = chunk[1:]
 219                 if len(chunk) == 0 {
 220                         err = ErrBadPattern
 221                         return
 222                 }
 223         }
 224         r, n := utf8.DecodeRuneInString(chunk)
 225         if r == utf8.RuneError && n == 1 {
 226                 err = ErrBadPattern
 227         }
 228         nchunk = chunk[n:]
 229         if len(nchunk) == 0 {
 230                 err = ErrBadPattern
 231         }
 232         return
 233 }
 234
 235 // Glob returns the names of all files matching pattern or nil
 236 // if there is no matching file. The syntax of patterns is the same
 237 // as in Match. The pattern may describe hierarchical names such as
 238 // /usr/*/bin/ed (assuming the Separator is '/').
 239 //
 240 // Glob ignores file system errors such as I/O errors reading directories.
 241 // The only possible returned error is ErrBadPattern, when pattern
 242 // is malformed.
 243 func Glob(pattern string) (matches []string, err error) {
 244         // Check pattern is well-formed.
 245         if _, err := Match(pattern, ""); err != nil {
 246                 return nil, err
 247         }
 248         if !hasMeta(pattern) {
 249                 if _, err = os.Lstat(pattern); err != nil {
 250                         return nil, nil
 251                 }
 252                 return []string{pattern}, nil
 253         }
 254
 255         dir, file := Split(pattern)
 256         volumeLen := 0
 257         if runtime.GOOS == "windows" {
 258                 volumeLen, dir = cleanGlobPathWindows(dir)
 259         } else {
 260                 dir = cleanGlobPath(dir)
 261         }
 262
 263         if !hasMeta(dir[volumeLen:]) {
 264                 return glob(dir, file, nil)
 265         }
 266
 267         // Prevent infinite recursion. See issue 15879.
 268         if dir == pattern {
 269                 return nil, ErrBadPattern
 270         }
 271
 272         var m []string
 273         m, err = Glob(dir)
 274         if err != nil {
 275                 return
 276         }
 277         for _, d := range m {
 278                 matches, err = glob(d, file, matches)
 279                 if err != nil {
 280                         return
 281                 }
 282         }
 283         return
 284 }
 285
 286 // cleanGlobPath prepares path for glob matching.
 287 func cleanGlobPath(path string) string {
 288         switch path {
 289         case "":
 290                 return "."
 291         case string(Separator):
 292                 // do nothing to the path
 293                 return path
 294         default:
 295                 return path[0 : len(path)-1] // chop off trailing separator
 296         }
 297 }
 298
 299 // cleanGlobPathWindows is windows version of cleanGlobPath.
 300 func cleanGlobPathWindows(path string) (prefixLen int, cleaned string) {
 301         vollen := volumeNameLen(path)
 302         switch {
 303         case path == "":
 304                 return 0, "."
 305         case vollen+1 == len(path) && os.IsPathSeparator(path[len(path)-1]): // /, \, C:\ and C:/
 306                 // do nothing to the path
 307                 return vollen + 1, path
 308         case vollen == len(path) && len(path) == 2: // C:
 309                 return vollen, path + "." // convert C: into C:.
 310         default:
 311                 if vollen >= len(path) {
 312                         vollen = len(path) - 1
 313                 }
 314                 return vollen, path[0 : len(path)-1] // chop off trailing separator
 315         }
 316 }
 317
 318 // glob searches for files matching pattern in the directory dir
 319 // and appends them to matches. If the directory cannot be
 320 // opened, it returns the existing matches. New matches are
 321 // added in lexicographical order.
 322 func glob(dir, pattern string, matches []string) (m []string, e error) {
 323         m = matches
 324         fi, err := os.Stat(dir)
 325         if err != nil {
 326                 return // ignore I/O error
 327         }
 328         if !fi.IsDir() {
 329                 return // ignore I/O error
 330         }
 331         d, err := os.Open(dir)
 332         if err != nil {
 333                 return // ignore I/O error
 334         }
 335         defer d.Close()
 336
 337         names, _ := d.Readdirnames(-1)
 338         sort.Strings(names)
 339
 340         for _, n := range names {
 341                 matched, err := Match(pattern, n)
 342                 if err != nil {
 343                         return m, err
 344                 }
 345                 if matched {
 346                         m = append(m, Join(dir, n))
 347                 }
 348         }
 349         return
 350 }
 351
 352 // hasMeta reports whether path contains any of the magic characters
 353 // recognized by Match.
 354 func hasMeta(path string) bool {
 355         magicChars := `*?[`
 356         if runtime.GOOS != "windows" {
 357                 magicChars = `*?[\`
 358         }
 359         return strings.ContainsAny(path, magicChars)
 360 }