fuzz_test.go

package glob

import (
	"errors"
	"fmt"
	"regexp"
	"slices"
	"strings"
	"testing"
	"unicode/utf8"
)

// FuzzMatchRegexp verifies Pattern.Match() against the regexp package.
//
// The fuzzer generates arbitrary (pattern, string, separators, globstar)
// inputs; each compilable pattern is translated into an equivalent anchored
// regular expression by translateGlob() -- a naive, independent
// re-implementation of the glob syntax -- and the match results are
// compared. Since the translator shares no code with Compile(), this
// validates the lexer, the parser, the compile-time rewrites and the
// matching engine all at once.
//
// Run with:
//
//	go test -fuzz=FuzzMatchRegexp
//
// Without -fuzz only the seed corpus is run, as a regression test.
func FuzzMatchRegexp(f *testing.F) {
	for _, seed := range []struct {
		pattern  string
		fixture  string
		seps     string // The separators, one rune each.
		globstar bool
	}{
		{
			pattern: "",
			fixture: "",
		},
		{
			pattern: "abc",
			fixture: "abc",
		},
		{
			pattern: "a*c",
			fixture: "abbbc",
		},
		{
			pattern: "a*a*a*a*b",
			fixture: "aaaaaaab",
		},
		{
			pattern: "**a*b",
			fixture: "axc.ab",
			seps:    ".",
		},
		{
			pattern: "*a**b",
			fixture: "xa.b",
			seps:    ".",
		},
		{
			pattern: "{*,**,?}",
			fixture: "a.b",
			seps:    ".",
		},
		{
			pattern: "{a,ab}c",
			fixture: "abc",
		},
		{
			pattern: "{*.google.*,yandex.*}",
			fixture: "www.google.com",
			seps:    ".",
		},
		{
			pattern: "{https://*gobwas.com,http://exclude.gobwas.com}",
			fixture: "https://safe.gobwas.com",
		},
		{
			pattern: "[!a]*",
			fixture: "this is a test3",
		},
		{
			pattern: "[a-z][!a-x]*cat*[h][!b]*eyes*",
			fixture: "my cat has very bright eyes",
		},
		{
			pattern: `\*`,
			fixture: "*",
		},
		{
			pattern: "*ä",
			fixture: "åä",
		},
		{
			pattern: "{,a}{a,}a",
			fixture: "a",
		},
		{
			pattern: "{{a,b},c}d",
			fixture: "bd",
		},
		{
			// A star inside an alternative must not discard the restart
			// point of a star outside of it; see the starsFloor handling
			// in matchContext.storeStar().
			pattern: "*{*0,}",
			fixture: "1",
		},
		{
			// U+FFFD is a valid character, not an invalid byte: the class
			// must match it, and the pattern must compile.
			pattern: "[!a]",
			fixture: "�",
		},
		{
			pattern: "[�]*",
			fixture: "�x",
		},
		{
			// Globstar: a leading `**.` may match zero segments.
			pattern:  "**.x",
			fixture:  "x",
			seps:     ".",
			globstar: true,
		},
		{
			pattern:  "a.**.b",
			fixture:  "a.b",
			seps:     ".",
			globstar: true,
		},
		{
			// Adjacent `**/` coalesce only with the same separator:
			// `{**.,}{**/,}x` is not `{**.,}x`.
			pattern:  "**.**/x",
			fixture:  "a.b/x",
			seps:     "./",
			globstar: true,
		},
		{
			pattern:  "**.**/x",
			fixture:  "x",
			seps:     "./",
			globstar: true,
		},
		{
			// An escaped separator is a separator too.
			pattern:  `**\.**.x`,
			fixture:  "a.x",
			seps:     ".",
			globstar: true,
		},
	} {
		f.Add(seed.pattern, seed.fixture, seed.seps, seed.globstar)
	}
	f.Fuzz(func(t *testing.T, pattern, s, seps string, globstar bool) {
		if len(pattern) > 32 || len(s) > 64 {
			t.Skip("too large")
		}
		if !utf8.ValidString(pattern) || !utf8.ValidString(s) || !utf8.ValidString(seps) {
			// The regexp package normalizes invalid UTF-8; the comparison
			// makes no sense for it.
			t.Skip("invalid utf8")
		}
		if len(seps) > 3 || strings.ContainsAny(seps, `*?[]{}\\,!-`) {
			// A meta character as a separator is a degenerate case the
			// naive oracle does not define; the rest is enough.
			t.Skip("odd separators")
		}
		sep := []rune(seps)
		if len(sep) > 0 {
			if strings.Count(pattern, "*") > 4 {
				// Backtracking over many separator-limited stars is
				// combinatorial in the worst case; keep the fuzzing fast.
				t.Skip("too many stars")
			}
		}
		if globstar && strings.ContainsAny(pattern, "{}") {
			// The oracle below does not track the segment starts across
			// the alternatives; TestGlobstar covers them.
			t.Skip("globstar with braces")
		}
		p, err := Compiler{Separators: sep, Globstar: globstar}.Compile(pattern)
		if err != nil {
			t.Skip("does not compile")
		}
		reStr, err := translateGlob(pattern, sep, globstar)
		if err != nil {
			t.Fatalf("Compile() accepted %#q but the translator did not: %v", pattern, err)
		}
		re, err := regexp.Compile(reStr)
		if err != nil {
			t.Fatalf("bad regexp translation of %#q: %v", pattern, err)
		}
		var (
			got  = p.Match(s)
			want = re.MatchString(s)
		)
		if got != want {
			t.Errorf(
				"sep=%q globstar=%t pattern=%#q (regexp %#q) string=%#q: Match()=%t, regexp=%t",
				string(sep), globstar, pattern, re, s, got, want,
			)
		}
	})
}

// translateGlob translates the glob pattern into an equivalent anchored
// regular expression. It is intentionally independent from Compile(): a naive
// rune-by-rune re-implementation of the documented syntax, sharing no code
// with the lexer or the parser, to serve as the differential oracle.
//
// With globstar set, a run of two or more stars that begins the pattern or
// follows a separator, and is followed by a (possibly escaped) separator,
// is an optional run of segments. Braces are not supported in this mode.
func translateGlob(pattern string, sep []rune, globstar bool) (string, error) {
	var sb strings.Builder
	sb.WriteString("^(?:")
	rs := []rune(pattern)
	depth := 0
	for i := 0; i < len(rs); i++ {
		switch r := rs[i]; r {
		case '\\':
			// A trailing backslash does not compile, so it never gets here.
			if i+1 < len(rs) {
				i++
				sb.WriteString(regexp.QuoteMeta(string(rs[i])))
			}

		case '*':
			// Adjacent stars are one star: the most general of them.
			at := i
			for i+1 < len(rs) && rs[i+1] == '*' {
				i++
			}
			if at == i {
				sb.WriteString(sepClassRegexp(sep) + `*`)
				break
			}
			if globstar && (at == 0 || slices.Contains(sep, rs[at-1])) {
				j := i + 1
				if j < len(rs) && rs[j] == '\\' {
					j++
				}
				if j < len(rs) && slices.Contains(sep, rs[j]) {
					sb.WriteString(`(?:(?s:.*)` + regexp.QuoteMeta(string(rs[j])) + `)?`)
					i = j
					break
				}
			}
			sb.WriteString(`(?s:.*)`)

		case '?':
			sb.WriteString(sepClassRegexp(sep))

		case '{':
			depth++
			sb.WriteString(`(?:`)

		case '}':
			if depth == 0 {
				// A literal outside of braces.
				sb.WriteString(regexp.QuoteMeta(`}`))
				break
			}
			depth--
			sb.WriteString(`)`)

		case ',':
			if depth == 0 {
				// A literal outside of braces.
				sb.WriteString(`,`)
				break
			}
			sb.WriteString(`|`)

		case '[':
			n, err := translateClass(&sb, rs[i:])
			if err != nil {
				return "", err
			}
			i += n - 1

		default:
			sb.WriteString(regexp.QuoteMeta(string(r)))
		}
	}
	if depth != 0 {
		return "", errors.New("unclosed `{`")
	}
	sb.WriteString(`)$`)
	return sb.String(), nil
}

// translateClass translates the `[...]` character class rs begins with and
// returns the number of runes consumed. Mirroring the syntax, a class is
// either a range `[a-z]` or a set `[abc]`, both optionally negated with the
// leading `!`; the range boundary characters are taken verbatim, the set
// characters may be escaped.
func translateClass(sb *strings.Builder, rs []rune) (int, error) {
	i := 1 // Skip the `[`.
	not := ""
	if i < len(rs) && rs[i] == '!' {
		not = "^"
		i++
	}
	if i+1 < len(rs) && rs[i+1] == '-' {
		// A range.
		if i+3 >= len(rs) || rs[i+3] != ']' {
			return 0, errors.New("unclosed range")
		}
		lo, hi := rs[i], rs[i+2]
		if hi < lo {
			return 0, errors.New("range hi character is less than lo")
		}
		fmt.Fprintf(sb, `[%s\x{%x}-\x{%x}]`, not, lo, hi)
		return i + 4, nil
	}
	// A set.
	var chars []rune
	escaped := false
	for ; i < len(rs); i++ {
		r := rs[i]
		switch {
		case escaped:
			chars = append(chars, r)
			escaped = false
		case r == '\\':
			escaped = true
		case r == ']':
			if len(chars) == 0 {
				return 0, errors.New("empty class")
			}
			sb.WriteString("[" + not)
			for _, c := range chars {
				fmt.Fprintf(sb, `\x{%x}`, c)
			}
			sb.WriteString("]")
			return i + 1, nil
		default:
			chars = append(chars, r)
		}
	}
	return 0, errors.New("unclosed `[`")
}

// sepClassRegexp returns a class matching any single rune except the
// separators, e.g. `[^\x{2e}]` -- or the match-all when there are none.
func sepClassRegexp(sep []rune) string {
	if len(sep) == 0 {
		return `(?s:.)`
	}
	var sb strings.Builder
	sb.WriteString("[^")
	for _, r := range sep {
		fmt.Fprintf(&sb, `\x{%x}`, r)
	}
	sb.WriteString("]")
	return sb.String()
}