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 path
6
7import (
8	"errors"
9	"internal/bytealg"
10	"unicode/utf8"
11)
12
13// ErrBadPattern indicates a pattern was malformed.
14var 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.
37func Match(pattern, name string) (matched bool, err error) {
38Pattern:
39	for len(pattern) > 0 {
40		var star bool
41		var chunk string
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.
92func scanChunk(pattern string) (star bool, chunk, rest string) {
93	for len(pattern) > 0 && pattern[0] == '*' {
94		pattern = pattern[1:]
95		star = true
96	}
97	inrange := false
98	var i int
99Scan:
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 ?.
123func matchChunk(chunk, s string) (rest string, 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			fallthrough
191
192		default:
193			if !failed {
194				if chunk[0] != s[0] {
195					failed = true
196				}
197				s = s[1:]
198			}
199			chunk = chunk[1:]
200		}
201	}
202	if failed {
203		return "", false, nil
204	}
205	return s, true, nil
206}
207
208// getEsc gets a possibly-escaped character from chunk, for a character class.
209func getEsc(chunk string) (r rune, nchunk string, err error) {
210	if len(chunk) == 0 || chunk[0] == '-' || chunk[0] == ']' {
211		err = ErrBadPattern
212		return
213	}
214	if chunk[0] == '\\' {
215		chunk = chunk[1:]
216		if len(chunk) == 0 {
217			err = ErrBadPattern
218			return
219		}
220	}
221	r, n := utf8.DecodeRuneInString(chunk)
222	if r == utf8.RuneError && n == 1 {
223		err = ErrBadPattern
224	}
225	nchunk = chunk[n:]
226	if len(nchunk) == 0 {
227		err = ErrBadPattern
228	}
229	return
230}
231