Source file src/pkg/path/filepath/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 filepath
6
7 import (
8 "errors"
9 "os"
10 "runtime"
11 "sort"
12 "strings"
13 "unicode/utf8"
14 )
15
16 // ErrBadPattern indicates a globbing pattern was malformed.
17 var ErrBadPattern = errors.New("syntax error in pattern")
18
19 // Match returns true if name matches the shell file name pattern.
20 // The pattern syntax is:
21 //
22 // pattern:
23 // { term }
24 // term:
25 // '*' matches any sequence of non-Separator characters
26 // '?' matches any single non-Separator character
27 // '[' [ '^' ] { character-range } ']'
28 // character class (must be non-empty)
29 // c matches character c (c != '*', '?', '\\', '[')
30 // '\\' c matches character c
31 //
32 // character-range:
33 // c matches character c (c != '\\', '-', ']')
34 // '\\' c matches character c
35 // lo '-' hi matches character c for lo <= c <= hi
36 //
37 // Match requires pattern to match all of name, not just a substring.
38 // The only possible returned error is ErrBadPattern, when pattern
39 // is malformed.
40 //
41 // On Windows, escaping is disabled. Instead, '\\' is treated as
42 // path separator.
43 //
44 func Match(pattern, name string) (matched bool, err error) {
45 Pattern:
46 for len(pattern) > 0 {
47 var star bool
48 var chunk string
49 star, chunk, pattern = scanChunk(pattern)
50 if star && chunk == "" {
51 // Trailing * matches rest of string unless it has a /.
52 return strings.Index(name, string(Separator)) < 0, nil
53 }
54 // Look for match at current position.
55 t, ok, err := matchChunk(chunk, name)
56 // if we're the last chunk, make sure we've exhausted the name
57 // otherwise we'll give a false result even if we could still match
58 // using the star
59 if ok && (len(t) == 0 || len(pattern) > 0) {
60 name = t
61 continue
62 }
63 if err != nil {
64 return false, err
65 }
66 if star {
67 // Look for match skipping i+1 bytes.
68 // Cannot skip /.
69 for i := 0; i < len(name) && name[i] != Separator; i++ {
70 t, ok, err := matchChunk(chunk, name[i+1:])
71 if ok {
72 // if we're the last chunk, make sure we exhausted the name
73 if len(pattern) == 0 && len(t) > 0 {
74 continue
75 }
76 name = t
77 continue Pattern
78 }
79 if err != nil {
80 return false, err
81 }
82 }
83 }
84 return false, nil
85 }
86 return len(name) == 0, nil
87 }
88
89 // scanChunk gets the next segment of pattern, which is a non-star string
90 // possibly preceded by a star.
91 func scanChunk(pattern string) (star bool, chunk, rest string) {
92 for len(pattern) > 0 && pattern[0] == '*' {
93 pattern = pattern[1:]
94 star = true
95 }
96 inrange := false
97 var i int
98 Scan:
99 for i = 0; i < len(pattern); i++ {
100 switch pattern[i] {
101 case '\\':
102 if runtime.GOOS != "windows" {
103 // error check handled in matchChunk: bad pattern.
104 if i+1 < len(pattern) {
105 i++
106 }
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 for len(chunk) > 0 {
126 if len(s) == 0 {
127 return
128 }
129 switch chunk[0] {
130 case '[':
131 // character class
132 r, n := utf8.DecodeRuneInString(s)
133 s = s[n:]
134 chunk = chunk[1:]
135 // possibly negated
136 negated := chunk[0] == '^'
137 if negated {
138 chunk = chunk[1:]
139 }
140 // parse all ranges
141 match := false
142 nrange := 0
143 for {
144 if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
145 chunk = chunk[1:]
146 break
147 }
148 var lo, hi rune
149 if lo, chunk, err = getEsc(chunk); err != nil {
150 return
151 }
152 hi = lo
153 if chunk[0] == '-' {
154 if hi, chunk, err = getEsc(chunk[1:]); err != nil {
155 return
156 }
157 }
158 if lo <= r && r <= hi {
159 match = true
160 }
161 nrange++
162 }
163 if match == negated {
164 return
165 }
166
167 case '?':
168 if s[0] == Separator {
169 return
170 }
171 _, n := utf8.DecodeRuneInString(s)
172 s = s[n:]
173 chunk = chunk[1:]
174
175 case '\\':
176 if runtime.GOOS != "windows" {
177 chunk = chunk[1:]
178 if len(chunk) == 0 {
179 err = ErrBadPattern
180 return
181 }
182 }
183 fallthrough
184
185 default:
186 if chunk[0] != s[0] {
187 return
188 }
189 s = s[1:]
190 chunk = chunk[1:]
191 }
192 }
193 return s, true, nil
194 }
195
196 // getEsc gets a possibly-escaped character from chunk, for a character class.
197 func getEsc(chunk string) (r rune, nchunk string, err error) {
198 if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
199 err = ErrBadPattern
200 return
201 }
202 if chunk[0] == '\\' && runtime.GOOS != "windows" {
203 chunk = chunk[1:]
204 if len(chunk) == 0 {
205 err = ErrBadPattern
206 return
207 }
208 }
209 r, n := utf8.DecodeRuneInString(chunk)
210 if r == utf8.RuneError && n == 1 {
211 err = ErrBadPattern
212 }
213 nchunk = chunk[n:]
214 if len(nchunk) == 0 {
215 err = ErrBadPattern
216 }
217 return
218 }
219
220 // Glob returns the names of all files matching pattern or nil
221 // if there is no matching file. The syntax of patterns is the same
222 // as in Match. The pattern may describe hierarchical names such as
223 // /usr/*/bin/ed (assuming the Separator is '/').
224 //
225 func Glob(pattern string) (matches []string, err error) {
226 if !hasMeta(pattern) {
227 if _, err = os.Stat(pattern); err != nil {
228 return nil, nil
229 }
230 return []string{pattern}, nil
231 }
232
233 dir, file := Split(pattern)
234 switch dir {
235 case "":
236 dir = "."
237 case string(Separator):
238 // nothing
239 default:
240 dir = dir[0 : len(dir)-1] // chop off trailing separator
241 }
242
243 if !hasMeta(dir) {
244 return glob(dir, file, nil)
245 }
246
247 var m []string
248 m, err = Glob(dir)
249 if err != nil {
250 return
251 }
252 for _, d := range m {
253 matches, err = glob(d, file, matches)
254 if err != nil {
255 return
256 }
257 }
258 return
259 }
260
261 // glob searches for files matching pattern in the directory dir
262 // and appends them to matches. If the directory cannot be
263 // opened, it returns the existing matches. New matches are
264 // added in lexicographical order.
265 func glob(dir, pattern string, matches []string) (m []string, e error) {
266 m = matches
267 fi, err := os.Stat(dir)
268 if err != nil {
269 return
270 }
271 if !fi.IsDir() {
272 return
273 }
274 d, err := os.Open(dir)
275 if err != nil {
276 return
277 }
278 defer d.Close()
279
280 names, err := d.Readdirnames(-1)
281 if err != nil {
282 return
283 }
284 sort.Strings(names)
285
286 for _, n := range names {
287 matched, err := Match(pattern, n)
288 if err != nil {
289 return m, err
290 }
291 if matched {
292 m = append(m, Join(dir, n))
293 }
294 }
295 return
296 }
297
298 // hasMeta returns true if path contains any of the magic characters
299 // recognized by Match.
300 func hasMeta(path string) bool {
301 // TODO(niemeyer): Should other magic characters be added here?
302 return strings.IndexAny(path, "*?[") >= 0
303 }