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 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                         // 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 func Glob(pattern string) (matches []string, err error) {
 232         if !hasMeta(pattern) {
 233                 if _, err = os.Lstat(pattern); err != nil {
 234                         return nil, nil
 235                 }
 236                 return []string{pattern}, nil
 237         }
 238
 239         dir, file := Split(pattern)
 240         switch dir {
 241         case "":
 242                 dir = "."
 243         case string(Separator):
 244                 // nothing
 245         default:
 246                 dir = dir[0 : len(dir)-1] // chop off trailing separator
 247         }
 248
 249         if !hasMeta(dir) {
 250                 return glob(dir, file, nil)
 251         }
 252
 253         var m []string
 254         m, err = Glob(dir)
 255         if err != nil {
 256                 return
 257         }
 258         for _, d := range m {
 259                 matches, err = glob(d, file, matches)
 260                 if err != nil {
 261                         return
 262                 }
 263         }
 264         return
 265 }
 266
 267 // glob searches for files matching pattern in the directory dir
 268 // and appends them to matches. If the directory cannot be
 269 // opened, it returns the existing matches. New matches are
 270 // added in lexicographical order.
 271 func glob(dir, pattern string, matches []string) (m []string, e error) {
 272         m = matches
 273         fi, err := os.Stat(dir)
 274         if err != nil {
 275                 return
 276         }
 277         if !fi.IsDir() {
 278                 return
 279         }
 280         d, err := os.Open(dir)
 281         if err != nil {
 282                 return
 283         }
 284         defer d.Close()
 285
 286         names, err := d.Readdirnames(-1)
 287         if err != nil {
 288                 return
 289         }
 290         sort.Strings(names)
 291
 292         for _, n := range names {
 293                 matched, err := Match(pattern, n)
 294                 if err != nil {
 295                         return m, err
 296                 }
 297                 if matched {
 298                         m = append(m, Join(dir, n))
 299                 }
 300         }
 301         return
 302 }
 303
 304 // hasMeta returns true if path contains any of the magic characters
 305 // recognized by Match.
 306 func hasMeta(path string) bool {
 307         // TODO(niemeyer): Should other magic characters be added here?
 308         return strings.IndexAny(path, "*?[") >= 0
 309 }