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