glob.gno

  1// Package glob matches shell-style patterns against strings, in two modes:
  2// plain, where `*` crosses everything, and path, where `/` is a boundary that
  3// only `**` crosses.
  4//
  5// The reason to have it on chain is the allowlist. A realm that decides what a
  6// caller may touch writes the rule as a pattern (gno.land/r/moul/**), and the
  7// obvious alternative, strings.HasPrefix, is wrong in a way that only shows up
  8// in production: the prefix gno.land/r/moul/home also matches
  9// gno.land/r/moul/homeless, and the prefix a caller gets by trimming /** off
 10// the rule above, gno.land/r/moul, also matches gno.land/r/moulier/drain, a
 11// different namespace owned by a different person. A separator-aware matcher
 12// cannot make either mistake, because a boundary is part of the grammar rather
 13// than something the caller remembered to append. Remembering to append it is
 14// no answer either: gno.land/r/moul/home with a slash on the end stops being a
 15// rule that matches the path it names.
 16//
 17// The matcher is iterative with a single backtrack point, so it runs in
 18// O(len(pattern) * len(name)) time and constant space. That is not a style
 19// preference. The recursive one-liner every glob tutorial shows is exponential
 20// on a pattern like a*a*a*a*a*a*b, and a realm that accepts a pattern from a
 21// caller and runs an exponential matcher on it has handed out a gas bomb.
 22//
 23// Matching is byte-oriented, deliberately: `?` matches one byte and a class
 24// range compares bytes, so this package is for ASCII subjects (package paths,
 25// bech32 addresses, handles, file names) and not for matching prose. See the
 26// package README for what that rules out.
 27//
 28// A live demo of this package is at
 29// [r/moul/x/daily/globdemo](/r/moul/x/daily/globdemo/v0).
 30package glob
 31
 32import "strings"
 33
 34// Separator is the byte [MatchPath] treats as a path boundary.
 35const Separator = '/'
 36
 37// Match reports whether name matches pattern.
 38//
 39//	?          any single byte
 40//	*          any sequence of bytes, including none
 41//	[abc]      any one of the listed bytes
 42//	[a-z]      any byte in the range, ends inclusive
 43//	[!abc]     any byte NOT listed; [^abc] is the same thing
 44//	\x         the literal byte x, for any x
 45//	anything else  itself
 46//
 47// `*` crosses every byte, including [Separator]. Use [MatchPath] when the
 48// subject is a path and a wildcard must stay inside one segment.
 49//
 50// An invalid pattern matches nothing. There is no error return, so the choice
 51// is between inert and permissive, and a bad allowlist entry that matches
 52// everything is the worse of the two. Ask [Valid] when it matters.
 53func Match(pattern, name string) bool {
 54	if !Valid(pattern) {
 55		return false
 56	}
 57	return matchBytes(pattern, name)
 58}
 59
 60// MatchPath reports whether name matches pattern, with [Separator] as a
 61// boundary neither side may cross by accident.
 62//
 63// Both are split into segments, and then:
 64//
 65//   - a segment that is exactly `**` matches zero or more whole segments
 66//   - every other segment is matched by [Match] against one segment, so `*`,
 67//     `?` and a class can never reach past the separator
 68//
 69// `**` only crosses as a whole segment. Glued to anything else, as in `a**b`,
 70// it is an ordinary star confined to its segment.
 71//
 72// A [Separator] that is escaped (`a\/b`) or inside a class (`[/]`) belongs to
 73// its segment and does not split the pattern. Such a pattern matches nothing,
 74// because a name segment can never contain a separator, and it says so by
 75// returning false rather than by aborting.
 76//
 77// An invalid pattern matches nothing, as in [Match].
 78func MatchPath(pattern, name string) bool {
 79	if !Valid(pattern) {
 80		return false
 81	}
 82	return matchSegments(splitPattern(pattern), splitName(name))
 83}
 84
 85// Valid reports whether pattern is well formed.
 86//
 87// Three things make it malformed, and each of them is a typo a caller makes
 88// rather than a construct anyone writes on purpose: an unterminated class
 89// (`[a-z`), an empty one (`[]`, `[!]`), and a trailing backslash with nothing
 90// to escape (`abc\`).
 91func Valid(pattern string) bool {
 92	for i := 0; i < len(pattern); {
 93		switch pattern[i] {
 94		case '\\':
 95			if i+1 >= len(pattern) {
 96				return false
 97			}
 98			i += 2
 99		case '[':
100			j := i + 1
101			if j < len(pattern) && (pattern[j] == '!' || pattern[j] == '^') {
102				j++
103			}
104			start := j
105			for j < len(pattern) && pattern[j] != ']' {
106				if pattern[j] == '\\' {
107					j++
108					if j >= len(pattern) {
109						return false
110					}
111				}
112				j++
113			}
114			// j == start is an empty class, which is a typo rather than a
115			// class that matches nothing: nobody writes one deliberately.
116			if j >= len(pattern) || j == start {
117				return false
118			}
119			i = j + 1
120		default:
121			i++
122		}
123	}
124	return true
125}
126
127// Filter returns the elements of names matching pattern, in their original
128// order, using [Match].
129//
130// The result is never nil, so a caller can range and len it with no guard.
131func Filter(pattern string, names []string) []string {
132	out := []string{}
133	if !Valid(pattern) {
134		return out
135	}
136	for _, n := range names {
137		if matchBytes(pattern, n) {
138			out = append(out, n)
139		}
140	}
141	return out
142}
143
144// FilterPath is [Filter] with [MatchPath] semantics.
145func FilterPath(pattern string, names []string) []string {
146	out := []string{}
147	if !Valid(pattern) {
148		return out
149	}
150	psegs := splitPattern(pattern)
151	for _, n := range names {
152		if matchSegments(psegs, splitName(n)) {
153			out = append(out, n)
154		}
155	}
156	return out
157}
158
159// Any reports whether name matches at least one of patterns, using [Match].
160//
161// An invalid entry is skipped rather than failing the whole list: one typo in
162// an allowlist should cost that rule and no other.
163func Any(patterns []string, name string) bool {
164	for _, p := range patterns {
165		if Match(p, name) {
166			return true
167		}
168	}
169	return false
170}
171
172// AnyPath is [Any] with [MatchPath] semantics. This is the allowlist
173// primitive: a list of rules, a subject, one boolean.
174func AnyPath(patterns []string, name string) bool {
175	for _, p := range patterns {
176		if MatchPath(p, name) {
177			return true
178		}
179	}
180	return false
181}
182
183// matchBytes is the matcher proper, over a pattern already known valid.
184//
185// It walks both strings forward and remembers exactly one position: the most
186// recent `*` and how much of name it had consumed when it was reached. On a
187// mismatch it returns there and hands that star one more byte. That single
188// backtrack point is what keeps the whole thing O(len(pattern)*len(name)) in
189// time and O(1) in space, where the recursive formulation branches at every
190// star and goes exponential.
191//
192// It is correct precisely because every other pattern element consumes exactly
193// one byte: a later star can always absorb whatever an earlier one gives back,
194// so there is never a reason to reconsider any star but the last.
195func matchBytes(pattern, name string) bool {
196	px, nx := 0, 0
197	starPx, starNx := -1, -1
198
199	for nx < len(name) {
200		if px < len(pattern) {
201			if pattern[px] == '*' {
202				// Record the star and try to match the rest with it
203				// consuming nothing. Consecutive stars collapse naturally:
204				// the last one simply overwrites the mark.
205				starPx, starNx = px, nx
206				px++
207				continue
208			}
209			if ok, next := matchOne(pattern, px, name[nx]); ok {
210				px = next
211				nx++
212				continue
213			}
214		}
215		if starPx < 0 {
216			return false
217		}
218		starNx++
219		px, nx = starPx+1, starNx
220	}
221
222	// name is exhausted; the pattern may only have stars left.
223	for px < len(pattern) && pattern[px] == '*' {
224		px++
225	}
226	return px == len(pattern)
227}
228
229// matchOne reports whether the single-byte pattern element at px matches b,
230// and returns the index just past that element.
231//
232// The pattern is already known valid, which is why this can index past px
233// without checking: Valid has established that an escape has a byte after it
234// and a class has its closing bracket.
235func matchOne(pattern string, px int, b byte) (bool, int) {
236	switch pattern[px] {
237	case '?':
238		return true, px + 1
239	case '\\':
240		return pattern[px+1] == b, px + 2
241	case '[':
242		return matchClass(pattern, px, b)
243	default:
244		return pattern[px] == b, px + 1
245	}
246}
247
248// matchClass evaluates the bracket expression starting at px against b and
249// returns the index just past its closing bracket.
250//
251// There is no POSIX leading-`]` rule: a `]` inside a class is written `\]`.
252// One way to say it beats two, and the one that survives is the one that also
253// works for `-` and `\`.
254func matchClass(pattern string, px int, b byte) (bool, int) {
255	i := px + 1
256	negated := false
257	if pattern[i] == '!' || pattern[i] == '^' {
258		negated = true
259		i++
260	}
261
262	found := false
263	for pattern[i] != ']' {
264		lo := pattern[i]
265		if lo == '\\' {
266			i++
267			lo = pattern[i]
268		}
269		i++
270
271		// A '-' is a range only with something other than ']' after it, which
272		// is what makes [a-] and [-a] literal dashes rather than errors.
273		hi := lo
274		if pattern[i] == '-' && pattern[i+1] != ']' {
275			i++
276			hi = pattern[i]
277			if hi == '\\' {
278				i++
279				hi = pattern[i]
280			}
281			i++
282		}
283
284		if lo <= b && b <= hi {
285			found = true
286		}
287	}
288	return found != negated, i + 1
289}
290
291// splitName splits a subject on [Separator]. A name carries no pattern syntax,
292// so there is nothing to protect and a plain split is right.
293func splitName(name string) []string {
294	return strings.Split(name, string(Separator))
295}
296
297// splitPattern splits a pattern on every [Separator] that is not escaped and
298// not inside a character class.
299//
300// A plain strings.Split is wrong here, and wrong by aborting rather than by
301// answering: it cuts `a\/b` into `a\` and `b`, handing matchBytes a segment
302// whose trailing backslash has nothing after it, and `[/]` into `[` and `]`,
303// handing matchClass a bracket with no closing one. Both then index past the
304// end of the piece they were given, out of a Render that cannot be redeployed.
305// Splitting with the escape and the class in mind keeps every pattern element
306// whole, so each segment is itself a valid pattern.
307//
308// The resulting segment can still never match, since a name segment cannot
309// contain a separator. That is the correct answer and this returns it.
310func splitPattern(pattern string) []string {
311	segs := []string{}
312	start := 0
313	inClass := false
314	for i := 0; i < len(pattern); i++ {
315		switch pattern[i] {
316		case '\\':
317			// Valid has established there is a byte after it.
318			i++
319		case '[':
320			inClass = true
321		case ']':
322			inClass = false
323		case Separator:
324			if inClass {
325				continue
326			}
327			segs = append(segs, pattern[start:i])
328			start = i + 1
329		}
330	}
331	return append(segs, pattern[start:])
332}
333
334// matchSegments is matchBytes one level up: the same single-backtrack walk,
335// with `**` for the star and a whole segment for the byte.
336//
337// Writing it twice rather than generalising is the cheaper of the two: the
338// element test differs (a byte equality against a glob call), the alphabet
339// differs, and the shared version would take a comparison function and be
340// longer than both. What the duplication buys is that the zero-segment case,
341// `a/**/b` matching `a/b`, falls out of the algorithm instead of needing the
342// special case a segment-by-segment walk requires.
343func matchSegments(psegs, nsegs []string) bool {
344	pi, ni := 0, 0
345	starPi, starNi := -1, -1
346
347	for ni < len(nsegs) {
348		if pi < len(psegs) {
349			if psegs[pi] == "**" {
350				starPi, starNi = pi, ni
351				pi++
352				continue
353			}
354			if matchBytes(psegs[pi], nsegs[ni]) {
355				pi++
356				ni++
357				continue
358			}
359		}
360		if starPi < 0 {
361			return false
362		}
363		starNi++
364		pi, ni = starPi+1, starNi
365	}
366
367	for pi < len(psegs) && psegs[pi] == "**" {
368		pi++
369	}
370	return pi == len(psegs)
371}