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
5package filepath
6
7import (
8	"errors"
9	"os"
10	"runtime"
11	"sort"
12	"strings"
13	"unicode/utf8"
14)
15
16// ErrBadPattern indicates a pattern was malformed.
17var ErrBadPattern = errors.New("syntax error in pattern")
18
19// Match reports whether 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//
44func Match(pattern, name string) (matched bool, err error) {
45Pattern:
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.Contains(name, string(Separator)), 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.
91func 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
98Scan:
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 ?.
124func 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			// We can't end right after '[', we're expecting at least
136			// a closing bracket and possibly a caret.
137			if len(chunk) == 0 {
138				err = ErrBadPattern
139				return
140			}
141			// possibly negated
142			negated := chunk[0] == '^'
143			if negated {
144				chunk = chunk[1:]
145			}
146			// parse all ranges
147			match := false
148			nrange := 0
149			for {
150				if len(chunk) > 0 && chunk[0] == ']' && nrange > 0 {
151					chunk = chunk[1:]
152					break
153				}
154				var lo, hi rune
155				if lo, chunk, err = getEsc(chunk); err != nil {
156					return
157				}
158				hi = lo
159				if chunk[0] == '-' {
160					if hi, chunk, err = getEsc(chunk[1:]); err != nil {
161						return
162					}
163				}
164				if lo <= r && r <= hi {
165					match = true
166				}
167				nrange++
168			}
169			if match == negated {
170				return
171			}
172
173		case '?':
174			if s[0] == Separator {
175				return
176			}
177			_, n := utf8.DecodeRuneInString(s)
178			s = s[n:]
179			chunk = chunk[1:]
180
181		case '\\':
182			if runtime.GOOS != "windows" {
183				chunk = chunk[1:]
184				if len(chunk) == 0 {
185					err = ErrBadPattern
186					return
187				}
188			}
189			fallthrough
190
191		default:
192			if chunk[0] != s[0] {
193				return
194			}
195			s = s[1:]
196			chunk = chunk[1:]
197		}
198	}
199	return s, true, nil
200}
201
202// getEsc gets a possibly-escaped character from chunk, for a character class.
203func getEsc(chunk string) (r rune, nchunk string, err error) {
204	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
205		err = ErrBadPattern
206		return
207	}
208	if chunk[0] == '\\' && runtime.GOOS != "windows" {
209		chunk = chunk[1:]
210		if len(chunk) == 0 {
211			err = ErrBadPattern
212			return
213		}
214	}
215	r, n := utf8.DecodeRuneInString(chunk)
216	if r == utf8.RuneError && n == 1 {
217		err = ErrBadPattern
218	}
219	nchunk = chunk[n:]
220	if len(nchunk) == 0 {
221		err = ErrBadPattern
222	}
223	return
224}
225
226// Glob returns the names of all files matching pattern or nil
227// if there is no matching file. The syntax of patterns is the same
228// as in Match. The pattern may describe hierarchical names such as
229// /usr/*/bin/ed (assuming the Separator is '/').
230//
231// Glob ignores file system errors such as I/O errors reading directories.
232// The only possible returned error is ErrBadPattern, when pattern
233// is malformed.
234func Glob(pattern string) (matches []string, err error) {
235	if !hasMeta(pattern) {
236		if _, err = os.Lstat(pattern); err != nil {
237			return nil, nil
238		}
239		return []string{pattern}, nil
240	}
241
242	dir, file := Split(pattern)
243	volumeLen := 0
244	if runtime.GOOS == "windows" {
245		volumeLen, dir = cleanGlobPathWindows(dir)
246	} else {
247		dir = cleanGlobPath(dir)
248	}
249
250	if !hasMeta(dir[volumeLen:]) {
251		return glob(dir, file, nil)
252	}
253
254	// Prevent infinite recursion. See issue 15879.
255	if dir == pattern {
256		return nil, ErrBadPattern
257	}
258
259	var m []string
260	m, err = Glob(dir)
261	if err != nil {
262		return
263	}
264	for _, d := range m {
265		matches, err = glob(d, file, matches)
266		if err != nil {
267			return
268		}
269	}
270	return
271}
272
273// cleanGlobPath prepares path for glob matching.
274func cleanGlobPath(path string) string {
275	switch path {
276	case "":
277		return "."
278	case string(Separator):
279		// do nothing to the path
280		return path
281	default:
282		return path[0 : len(path)-1] // chop off trailing separator
283	}
284}
285
286// cleanGlobPathWindows is windows version of cleanGlobPath.
287func cleanGlobPathWindows(path string) (prefixLen int, cleaned string) {
288	vollen := volumeNameLen(path)
289	switch {
290	case path == "":
291		return 0, "."
292	case vollen+1 == len(path) && os.IsPathSeparator(path[len(path)-1]): // /, \, C:\ and C:/
293		// do nothing to the path
294		return vollen + 1, path
295	case vollen == len(path) && len(path) == 2: // C:
296		return vollen, path + "." // convert C: into C:.
297	default:
298		if vollen >= len(path) {
299			vollen = len(path) - 1
300		}
301		return vollen, path[0 : len(path)-1] // chop off trailing separator
302	}
303}
304
305// glob searches for files matching pattern in the directory dir
306// and appends them to matches. If the directory cannot be
307// opened, it returns the existing matches. New matches are
308// added in lexicographical order.
309func glob(dir, pattern string, matches []string) (m []string, e error) {
310	m = matches
311	fi, err := os.Stat(dir)
312	if err != nil {
313		return
314	}
315	if !fi.IsDir() {
316		return
317	}
318	d, err := os.Open(dir)
319	if err != nil {
320		return
321	}
322	defer d.Close()
323
324	names, _ := d.Readdirnames(-1)
325	sort.Strings(names)
326
327	for _, n := range names {
328		matched, err := Match(pattern, n)
329		if err != nil {
330			return m, err
331		}
332		if matched {
333			m = append(m, Join(dir, n))
334		}
335	}
336	return
337}
338
339// hasMeta reports whether path contains any of the magic characters
340// recognized by Match.
341func hasMeta(path string) bool {
342	magicChars := `*?[`
343	if runtime.GOOS != "windows" {
344		magicChars = `*?[\`
345	}
346	return strings.ContainsAny(path, magicChars)
347}
348