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         "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 //
  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 bytealg.IndexByteString(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                 // Before returning false with no error,
  79                 // check that the remainder of the pattern is syntactically valid.
  80                 for len(pattern) > 0 {
  81                         _, chunk, pattern = scanChunk(pattern)
  82                         if _, _, err := matchChunk(chunk, ""); err != nil {
  83                                 return false, err
  84                         }
  85                 }
  86                 return false, nil
  87         }
  88         return len(name) == 0, nil
  89 }
  90
  91 // scanChunk gets the next segment of pattern, which is a non-star string
  92 // possibly preceded by a star.
  93 func scanChunk(pattern string) (star bool, chunk, rest string) {
  94         for len(pattern) > 0 && pattern[0] == '*' {
  95                 pattern = pattern[1:]
  96                 star = true
  97         }
  98         inrange := false
  99         var i int
 100 Scan:
 101         for i = 0; i < len(pattern); i++ {
 102                 switch pattern[i] {
 103                 case '\\':
 104                         // error check handled in matchChunk: bad pattern.
 105                         if i+1 < len(pattern) {
 106                                 i++
 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         // failed records whether the match has failed.
 126         // After the match fails, the loop continues on processing chunk,
 127         // checking that the pattern is well-formed but no longer reading s.
 128         failed := false
 129         for len(chunk) > 0 {
 130                 if !failed && len(s) == 0 {
 131                         failed = true
 132                 }
 133                 switch chunk[0] {
 134                 case '[':
 135                         // character class
 136                         var r rune
 137                         if !failed {
 138                                 var n int
 139                                 r, n = utf8.DecodeRuneInString(s)
 140                                 s = s[n:]
 141                         }
 142                         chunk = chunk[1:]
 143                         // possibly negated
 144                         negated := false
 145                         if len(chunk) > 0 && chunk[0] == '^' {
 146                                 negated = true
 147                                 chunk = chunk[1:]
 148                         }
 149                         // parse all ranges
 150                         match := false
 151                         nrange := 0
 152                         for {
 153                                 if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
 154                                         chunk = chunk[1:]
 155                                         break
 156                                 }
 157                                 var lo, hi rune
 158                                 if lo, chunk, err = getEsc(chunk); err != nil {
 159                                         return "", false, err
 160                                 }
 161                                 hi = lo
 162                                 if chunk[0] == '-' {
 163                                         if hi, chunk, err = getEsc(chunk[1:]); err != nil {
 164                                                 return "", false, err
 165                                         }
 166                                 }
 167                                 if lo <= r && r <= hi {
 168                                         match = true
 169                                 }
 170                                 nrange++
 171                         }
 172                         if match == negated {
 173                                 failed = true
 174                         }
 175
 176                 case '?':
 177                         if !failed {
 178                                 if s[0] == '/' {
 179                                         failed = true
 180                                 }
 181                                 _, n := utf8.DecodeRuneInString(s)
 182                                 s = s[n:]
 183                         }
 184                         chunk = chunk[1:]
 185
 186                 case '\\':
 187                         chunk = chunk[1:]
 188                         if len(chunk) == 0 {
 189                                 return "", false, ErrBadPattern
 190                         }
 191                         fallthrough
 192
 193                 default:
 194                         if !failed {
 195                                 if chunk[0] != s[0] {
 196                                         failed = true
 197                                 }
 198                                 s = s[1:]
 199                         }
 200                         chunk = chunk[1:]
 201                 }
 202         }
 203         if failed {
 204                 return "", false, nil
 205         }
 206         return s, true, nil
 207 }
 208
 209 // getEsc gets a possibly-escaped character from chunk, for a character class.
 210 func getEsc(chunk string) (r rune, nchunk string, err error) {
 211         if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
 212                 err = ErrBadPattern
 213                 return
 214         }
 215         if chunk[0] == '\\' {
 216                 chunk = chunk[1:]
 217                 if len(chunk) == 0 {
 218                         err = ErrBadPattern
 219                         return
 220                 }
 221         }
 222         r, n := utf8.DecodeRuneInString(chunk)
 223         if r == utf8.RuneError && n == 1 {
 224                 err = ErrBadPattern
 225         }
 226         nchunk = chunk[n:]
 227         if len(nchunk) == 0 {
 228                 err = ErrBadPattern
 229         }
 230         return
 231 }