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 []byte) (matched bool, err error) {
38 Pattern:
39 for len(pattern) > 0 {
40 var star bool
41 var chunk []byte
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 []byte) (star bool, chunk, rest []byte) {
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 []byte) (rest []byte, 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 if !failed {
191 if chunk[0] != s[0] {
192 failed = true
193 }
194 s = s[1:]
195 }
196 chunk = chunk[1:]
197 198 default:
199 if !failed {
200 if chunk[0] != s[0] {
201 failed = true
202 }
203 s = s[1:]
204 }
205 chunk = chunk[1:]
206 }
207 }
208 if failed {
209 return "", false, nil
210 }
211 return s, true, nil
212 }
213 214 // getEsc gets a possibly-escaped character from chunk, for a character class.
215 func getEsc(chunk []byte) (r rune, nchunk []byte, err error) {
216 if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
217 err = ErrBadPattern
218 return
219 }
220 if chunk[0] == '\\' {
221 chunk = chunk[1:]
222 if len(chunk) == 0 {
223 err = ErrBadPattern
224 return
225 }
226 }
227 r, n := utf8.DecodeRuneInString(chunk)
228 if r == utf8.RuneError && n == 1 {
229 err = ErrBadPattern
230 }
231 nchunk = chunk[n:]
232 if len(nchunk) == 0 {
233 err = ErrBadPattern
234 }
235 return
236 }
237