src/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         "internal/bytealg"
  10         "unicode/utf8"
  11 )
  12
  13 // ErrBadPattern indicates a pattern was malformed.
  14 var ErrBadPattern = errors.New("syntax error in pattern")
  15
  16 // Match reports whether name matches the shell 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 func Match(pattern, name string) (matched bool, err error) {
  38 Pattern:
  39         for len(pattern) > 0 {
  40                 var star bool
  41                 var chunk string
  42                 star, chunk, pattern = scanChunk(pattern)
  43                 if star && chunk == "" {
  44                         // Trailing * matches rest of string unless it has a /.
  45                         return bytealg.IndexByteString(name, '/') < 0, nil
  46                 }
  47                 // Look for match at current position.
  48                 t, ok, err := matchChunk(chunk, name)
  49                 // if we're the last chunk, make sure we've exhausted the name
  50                 // otherwise we'll give a false result even if we could still match
  51                 // using the star
  52                 if ok && (len(t) == 0 || len(pattern) > 0) {
  53                         name = t
  54                         continue
  55                 }
  56                 if err != nil {
  57                         return false, err
  58                 }
  59                 if star {
  60                         // Look for match skipping i+1 bytes.
  61                         // Cannot skip /.
  62                         for i := 0; i < len(name) && name[i] != '/'; i++ {
  63                                 t, ok, err := matchChunk(chunk, name[i+1:])
  64                                 if ok {
  65                                         // if we're the last chunk, make sure we exhausted the name
  66                                         if len(pattern) == 0 && len(t) > 0 {
  67                                                 continue
  68                                         }
  69                                         name = t
  70                                         continue Pattern
  71                                 }
  72                                 if err != nil {
  73                                         return false, err
  74                                 }
  75                         }
  76                 }
  77                 // Before returning false with no error,
  78                 // check that the remainder of the pattern is syntactically valid.
  79                 for len(pattern) > 0 {
  80                         _, chunk, pattern = scanChunk(pattern)
  81                         if _, _, err := matchChunk(chunk, ""); err != nil {
  82                                 return false, err
  83                         }
  84                 }
  85                 return false, nil
  86         }
  87         return len(name) == 0, nil
  88 }
  89
  90 // scanChunk gets the next segment of pattern, which is a non-star string
  91 // possibly preceded by a star.
  92 func scanChunk(pattern string) (star bool, chunk, rest string) {
  93         for len(pattern) > 0 && pattern[0] == '*' {
  94                 pattern = pattern[1:]
  95                 star = true
  96         }
  97         inrange := false
  98         var i int
  99 Scan:
 100         for i = 0; i < len(pattern); i++ {
 101                 switch pattern[i] {
 102                 case '\\':
 103                         // error check handled in matchChunk: bad pattern.
 104                         if i+1 < len(pattern) {
 105                                 i++
 106                         }
 107                 case '[':
 108                         inrange = true
 109                 case ']':
 110                         inrange = false
 111                 case '*':
 112                         if !inrange {
 113                                 break Scan
 114                         }
 115                 }
 116         }
 117         return star, pattern[0:i], pattern[i:]
 118 }
 119
 120 // matchChunk checks whether chunk matches the beginning of s.
 121 // If so, it returns the remainder of s (after the match).
 122 // Chunk is all single-character operators: literals, char classes, and ?.
 123 func matchChunk(chunk, s string) (rest string, ok bool, err error) {
 124         // failed records whether the match has failed.
 125         // After the match fails, the loop continues on processing chunk,
 126         // checking that the pattern is well-formed but no longer reading s.
 127         failed := false
 128         for len(chunk) > 0 {
 129                 if !failed && len(s) == 0 {
 130                         failed = true
 131                 }
 132                 switch chunk[0] {
 133                 case '[':
 134                         // character class
 135                         var r rune
 136                         if !failed {
 137                                 var n int
 138                                 r, n = utf8.DecodeRuneInString(s)
 139                                 s = s[n:]
 140                         }
 141                         chunk = chunk[1:]
 142                         // possibly negated
 143                         negated := false
 144                         if len(chunk) > 0 && chunk[0] == '^' {
 145                                 negated = true
 146                                 chunk = chunk[1:]
 147                         }
 148                         // parse all ranges
 149                         match := false
 150                         nrange := 0
 151                         for {
 152                                 if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
 153                                         chunk = chunk[1:]
 154                                         break
 155                                 }
 156                                 var lo, hi rune
 157                                 if lo, chunk, err = getEsc(chunk); err != nil {
 158                                         return "", false, err
 159                                 }
 160                                 hi = lo
 161                                 if chunk[0] == '-' {
 162                                         if hi, chunk, err = getEsc(chunk[1:]); err != nil {
 163                                                 return "", false, err
 164                                         }
 165                                 }
 166                                 if lo <= r && r <= hi {
 167                                         match = true
 168                                 }
 169                                 nrange++
 170                         }
 171                         if match == negated {
 172                                 failed = true
 173                         }
 174
 175                 case '?':
 176                         if !failed {
 177                                 if s[0] == '/' {
 178                                         failed = true
 179                                 }
 180                                 _, n := utf8.DecodeRuneInString(s)
 181                                 s = s[n:]
 182                         }
 183                         chunk = chunk[1:]
 184
 185                 case '\\':
 186                         chunk = chunk[1:]
 187                         if len(chunk) == 0 {
 188                                 return "", false, ErrBadPattern
 189                         }
 190                         fallthrough
 191
 192                 default:
 193                         if !failed {
 194                                 if chunk[0] != s[0] {
 195                                         failed = true
 196                                 }
 197                                 s = s[1:]
 198                         }
 199                         chunk = chunk[1:]
 200                 }
 201         }
 202         if failed {
 203                 return "", false, nil
 204         }
 205         return s, true, nil
 206 }
 207
 208 // getEsc gets a possibly-escaped character from chunk, for a character class.
 209 func getEsc(chunk string) (r rune, nchunk string, err error) {
 210         if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
 211                 err = ErrBadPattern
 212                 return
 213         }
 214         if chunk[0] == '\\' {
 215                 chunk = chunk[1:]
 216                 if len(chunk) == 0 {
 217                         err = ErrBadPattern
 218                         return
 219                 }
 220         }
 221         r, n := utf8.DecodeRuneInString(chunk)
 222         if r == utf8.RuneError && n == 1 {
 223                 err = ErrBadPattern
 224         }
 225         nchunk = chunk[n:]
 226         if len(nchunk) == 0 {
 227                 err = ErrBadPattern
 228         }
 229         return
 230 }