libgo/go/path/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 path
   6
   7 import (
   8         "os"
   9         "strings"
  10         "utf8"
  11 )
  12
  13 var ErrBadPattern = os.NewError("syntax error in pattern")
  14
  15 // Match returns true if name matches the shell file name pattern.
  16 // The pattern syntax is:
  17 //
  18 //      pattern:
  19 //              { term }
  20 //      term:
  21 //              '*'         matches any sequence of non-/ characters
  22 //              '?'         matches any single non-/ character
  23 //              '[' [ '^' ] { character-range } ']'
  24 //                          character class (must be non-empty)
  25 //              c           matches character c (c != '*', '?', '\\', '[')
  26 //              '\\' c      matches character c
  27 //
  28 //      character-range:
  29 //              c           matches character c (c != '\\', '-', ']')
  30 //              '\\' c      matches character c
  31 //              lo '-' hi   matches character c for lo <= c <= hi
  32 //
  33 // Match requires pattern to match all of name, not just a substring.
  34 // The only possible error return is when pattern is malformed.
  35 //
  36 func Match(pattern, name string) (matched bool, err os.Error) {
  37 Pattern:
  38         for len(pattern) > 0 {
  39                 var star bool
  40                 var chunk string
  41                 star, chunk, pattern = scanChunk(pattern)
  42                 if star && chunk == "" {
  43                         // Trailing * matches rest of string unless it has a /.
  44                         return strings.Index(name, "/") < 0, nil
  45                 }
  46                 // Look for match at current position.
  47                 t, ok, err := matchChunk(chunk, name)
  48                 // if we're the last chunk, make sure we've exhausted the name
  49                 // otherwise we'll give a false result even if we could still match
  50                 // using the star
  51                 if ok && (len(t) == 0 || len(pattern) > 0) {
  52                         name = t
  53                         continue
  54                 }
  55                 if err != nil {
  56                         return false, err
  57                 }
  58                 if star {
  59                         // Look for match skipping i+1 bytes.
  60                         // Cannot skip /.
  61                         for i := 0; i < len(name) && name[i] != '/'; i++ {
  62                                 t, ok, err := matchChunk(chunk, name[i+1:])
  63                                 if ok {
  64                                         // if we're the last chunk, make sure we exhausted the name
  65                                         if len(pattern) == 0 && len(t) > 0 {
  66                                                 continue
  67                                         }
  68                                         name = t
  69                                         continue Pattern
  70                                 }
  71                                 if err != nil {
  72                                         return false, err
  73                                 }
  74                         }
  75                 }
  76                 return false, nil
  77         }
  78         return len(name) == 0, nil
  79 }
  80
  81 // scanChunk gets the next segment of pattern, which is a non-star string
  82 // possibly preceded by a star.
  83 func scanChunk(pattern string) (star bool, chunk, rest string) {
  84         for len(pattern) > 0 && pattern[0] == '*' {
  85                 pattern = pattern[1:]
  86                 star = true
  87         }
  88         inrange := false
  89         var i int
  90 Scan:
  91         for i = 0; i < len(pattern); i++ {
  92                 switch pattern[i] {
  93                 case '\\':
  94                         // error check handled in matchChunk: bad pattern.
  95                         if i+1 < len(pattern) {
  96                                 i++
  97                         }
  98                 case '[':
  99                         inrange = true
 100                 case ']':
 101                         inrange = false
 102                 case '*':
 103                         if !inrange {
 104                                 break Scan
 105                         }
 106                 }
 107         }
 108         return star, pattern[0:i], pattern[i:]
 109 }
 110
 111 // matchChunk checks whether chunk matches the beginning of s.
 112 // If so, it returns the remainder of s (after the match).
 113 // Chunk is all single-character operators: literals, char classes, and ?.
 114 func matchChunk(chunk, s string) (rest string, ok bool, err os.Error) {
 115         for len(chunk) > 0 {
 116                 if len(s) == 0 {
 117                         return
 118                 }
 119                 switch chunk[0] {
 120                 case '[':
 121                         // character class
 122                         r, n := utf8.DecodeRuneInString(s)
 123                         s = s[n:]
 124                         chunk = chunk[1:]
 125                         // possibly negated
 126                         notNegated := true
 127                         if len(chunk) > 0 && chunk[0] == '^' {
 128                                 notNegated = false
 129                                 chunk = chunk[1:]
 130                         }
 131                         // parse all ranges
 132                         match := false
 133                         nrange := 0
 134                         for {
 135                                 if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
 136                                         chunk = chunk[1:]
 137                                         break
 138                                 }
 139                                 var lo, hi rune
 140                                 if lo, chunk, err = getEsc(chunk); err != nil {
 141                                         return
 142                                 }
 143                                 hi = lo
 144                                 if chunk[0] == '-' {
 145                                         if hi, chunk, err = getEsc(chunk[1:]); err != nil {
 146                                                 return
 147                                         }
 148                                 }
 149                                 if lo <= r && r <= hi {
 150                                         match = true
 151                                 }
 152                                 nrange++
 153                         }
 154                         if match != notNegated {
 155                                 return
 156                         }
 157
 158                 case '?':
 159                         if s[0] == '/' {
 160                                 return
 161                         }
 162                         _, n := utf8.DecodeRuneInString(s)
 163                         s = s[n:]
 164                         chunk = chunk[1:]
 165
 166                 case '\\':
 167                         chunk = chunk[1:]
 168                         if len(chunk) == 0 {
 169                                 err = ErrBadPattern
 170                                 return
 171                         }
 172                         fallthrough
 173
 174                 default:
 175                         if chunk[0] != s[0] {
 176                                 return
 177                         }
 178                         s = s[1:]
 179                         chunk = chunk[1:]
 180                 }
 181         }
 182         return s, true, nil
 183 }
 184
 185 // getEsc gets a possibly-escaped character from chunk, for a character class.
 186 func getEsc(chunk string) (r rune, nchunk string, err os.Error) {
 187         if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
 188                 err = ErrBadPattern
 189                 return
 190         }
 191         if chunk[0] == '\\' {
 192                 chunk = chunk[1:]
 193                 if len(chunk) == 0 {
 194                         err = ErrBadPattern
 195                         return
 196                 }
 197         }
 198         r, n := utf8.DecodeRuneInString(chunk)
 199         if r == utf8.RuneError && n == 1 {
 200                 err = ErrBadPattern
 201         }
 202         nchunk = chunk[n:]
 203         if len(nchunk) == 0 {
 204                 err = ErrBadPattern
 205         }
 206         return
 207 }