libgo/go/path/match.go

   1 package path
   2
   3 import (
   4         "os"
   5         "sort"
   6         "strings"
   7         "utf8"
   8 )
   9
  10 var ErrBadPattern = os.NewError("syntax error in pattern")
  11
  12 // Match returns true if name matches the shell file name pattern.
  13 // The syntax used by pattern is:
  14 //
  15 //      pattern:
  16 //              { term }
  17 //      term:
  18 //              '*'         matches any sequence of non-/ characters
  19 //              '?'         matches any single non-/ character
  20 //              '[' [ '^' ] { character-range } ']'
  21 //                          character class (must be non-empty)
  22 //              c           matches character c (c != '*', '?', '\\', '[')
  23 //              '\\' c      matches character c
  24 //
  25 //      character-range:
  26 //              c           matches character c (c != '\\', '-', ']')
  27 //              '\\' c      matches character c
  28 //              lo '-' hi   matches character c for lo <= c <= hi
  29 //
  30 // Match requires pattern to match all of name, not just a substring.
  31 // The only possible error return is when pattern is malformed.
  32 //
  33 func Match(pattern, name string) (matched bool, err os.Error) {
  34 Pattern:
  35         for len(pattern) > 0 {
  36                 var star bool
  37                 var chunk string
  38                 star, chunk, pattern = scanChunk(pattern)
  39                 if star && chunk == "" {
  40                         // Trailing * matches rest of string unless it has a /.
  41                         return strings.Index(name, "/") < 0, nil
  42                 }
  43                 // Look for match at current position.
  44                 t, ok, err := matchChunk(chunk, name)
  45                 // if we're the last chunk, make sure we've exhausted the name
  46                 // otherwise we'll give a false result even if we could still match
  47                 // using the star
  48                 if ok && (len(t) == 0 || len(pattern) > 0) {
  49                         name = t
  50                         continue
  51                 }
  52                 if err != nil {
  53                         return false, err
  54                 }
  55                 if star {
  56                         // Look for match skipping i+1 bytes.
  57                         // Cannot skip /.
  58                         for i := 0; i < len(name) && name[i] != '/'; i++ {
  59                                 t, ok, err := matchChunk(chunk, name[i+1:])
  60                                 if ok {
  61                                         // if we're the last chunk, make sure we exhausted the name
  62                                         if len(pattern) == 0 && len(t) > 0 {
  63                                                 continue
  64                                         }
  65                                         name = t
  66                                         continue Pattern
  67                                 }
  68                                 if err != nil {
  69                                         return false, err
  70                                 }
  71                         }
  72                 }
  73                 return false, nil
  74         }
  75         return len(name) == 0, nil
  76 }
  77
  78 // scanChunk gets the next section of pattern, which is a non-star string
  79 // possibly preceded by a star.
  80 func scanChunk(pattern string) (star bool, chunk, rest string) {
  81         for len(pattern) > 0 && pattern[0] == '*' {
  82                 pattern = pattern[1:]
  83                 star = true
  84         }
  85         inrange := false
  86         var i int
  87 Scan:
  88         for i = 0; i < len(pattern); i++ {
  89                 switch pattern[i] {
  90                 case '\\':
  91                         // error check handled in matchChunk: bad pattern.
  92                         if i+1 < len(pattern) {
  93                                 i++
  94                         }
  95                         continue
  96                 case '[':
  97                         inrange = true
  98                 case ']':
  99                         inrange = false
 100                 case '*':
 101                         if !inrange {
 102                                 break Scan
 103                         }
 104                 }
 105         }
 106         return star, pattern[0:i], pattern[i:]
 107 }
 108
 109 // matchChunk checks whether chunk matches the beginning of s.
 110 // If so, it returns the remainder of s (after the match).
 111 // Chunk is all single-character operators: literals, char classes, and ?.
 112 func matchChunk(chunk, s string) (rest string, ok bool, err os.Error) {
 113         for len(chunk) > 0 {
 114                 if len(s) == 0 {
 115                         return
 116                 }
 117                 switch chunk[0] {
 118                 case '[':
 119                         // character class
 120                         r, n := utf8.DecodeRuneInString(s)
 121                         s = s[n:]
 122                         chunk = chunk[1:]
 123                         // possibly negated
 124                         notNegated := true
 125                         if len(chunk) > 0 && chunk[0] == '^' {
 126                                 notNegated = false
 127                                 chunk = chunk[1:]
 128                         }
 129                         // parse all ranges
 130                         match := false
 131                         nrange := 0
 132                         for {
 133                                 if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
 134                                         chunk = chunk[1:]
 135                                         break
 136                                 }
 137                                 var lo, hi int
 138                                 if lo, chunk, err = getEsc(chunk); err != nil {
 139                                         return
 140                                 }
 141                                 hi = lo
 142                                 if chunk[0] == '-' {
 143                                         if hi, chunk, err = getEsc(chunk[1:]); err != nil {
 144                                                 return
 145                                         }
 146                                 }
 147                                 if lo <= r && r <= hi {
 148                                         match = true
 149                                 }
 150                                 nrange++
 151                         }
 152                         if match != notNegated {
 153                                 return
 154                         }
 155
 156                 case '?':
 157                         if s[0] == '/' {
 158                                 return
 159                         }
 160                         _, n := utf8.DecodeRuneInString(s)
 161                         s = s[n:]
 162                         chunk = chunk[1:]
 163
 164                 case '\\':
 165                         chunk = chunk[1:]
 166                         if len(chunk) == 0 {
 167                                 err = ErrBadPattern
 168                                 return
 169                         }
 170                         fallthrough
 171
 172                 default:
 173                         if chunk[0] != s[0] {
 174                                 return
 175                         }
 176                         s = s[1:]
 177                         chunk = chunk[1:]
 178                 }
 179         }
 180         return s, true, nil
 181 }
 182
 183 // getEsc gets a possibly-escaped character from chunk, for a character class.
 184 func getEsc(chunk string) (r int, nchunk string, err os.Error) {
 185         if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
 186                 err = ErrBadPattern
 187                 return
 188         }
 189         if chunk[0] == '\\' {
 190                 chunk = chunk[1:]
 191                 if len(chunk) == 0 {
 192                         err = ErrBadPattern
 193                         return
 194                 }
 195         }
 196         r, n := utf8.DecodeRuneInString(chunk)
 197         if r == utf8.RuneError && n == 1 {
 198                 err = ErrBadPattern
 199         }
 200         nchunk = chunk[n:]
 201         if len(nchunk) == 0 {
 202                 err = ErrBadPattern
 203         }
 204         return
 205 }
 206
 207 // Glob returns the names of all files matching pattern or nil
 208 // if there is no matching file. The syntax of patterns is the same
 209 // as in Match. The pattern may describe hierarchical names such as
 210 // /usr/*/bin/ed.
 211 //
 212 func Glob(pattern string) (matches []string) {
 213         if !hasMeta(pattern) {
 214                 if _, err := os.Stat(pattern); err == nil {
 215                         return []string{pattern}
 216                 }
 217                 return nil
 218         }
 219
 220         dir, file := Split(pattern)
 221         switch dir {
 222         case "":
 223                 dir = "."
 224         case "/":
 225                 // nothing
 226         default:
 227                 dir = dir[0 : len(dir)-1] // chop off trailing '/'
 228         }
 229
 230         if hasMeta(dir) {
 231                 for _, d := range Glob(dir) {
 232                         matches = glob(d, file, matches)
 233                 }
 234         } else {
 235                 return glob(dir, file, nil)
 236         }
 237         return matches
 238 }
 239
 240 // glob searches for files matching pattern in the directory dir
 241 // and appends them to matches.
 242 func glob(dir, pattern string, matches []string) []string {
 243         fi, err := os.Stat(dir)
 244         if err != nil {
 245                 return nil
 246         }
 247         if !fi.IsDirectory() {
 248                 return matches
 249         }
 250         d, err := os.Open(dir, os.O_RDONLY, 0666)
 251         if err != nil {
 252                 return nil
 253         }
 254         defer d.Close()
 255
 256         names, err := d.Readdirnames(-1)
 257         if err != nil {
 258                 return nil
 259         }
 260         sort.SortStrings(names)
 261
 262         for _, n := range names {
 263                 matched, err := Match(pattern, n)
 264                 if err != nil {
 265                         return matches
 266                 }
 267                 if matched {
 268                         matches = append(matches, Join(dir, n))
 269                 }
 270         }
 271         return matches
 272 }
 273
 274 // hasMeta returns true if path contains any of the magic characters
 275 // recognized by Match.
 276 func hasMeta(path string) bool {
 277         return strings.IndexAny(path, "*?[") != -1
 278 }