Source file src/pkg/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 }