krino: matching — scan, ignore, conditions, extraction, duplicates, explain, dry run

3 files changed, 476 insertions, 0 deletions

diff --git a/internal/ignore/ignore.go b/internal/ignore/ignore.go
new file mode 100644
index 0000000..fff6dcc
--- /dev/null
+++ b/internal/ignore/ignore.go
@@ -0,0 +1,324 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// Package ignore implements a gitignore(5)-compatible path matcher.
+package ignore
+
+import (
+	"errors"
+	"fmt"
+	"regexp"
+	"strings"
+)
+
+// pattern is one compiled gitignore(5) pattern.
+type pattern struct {
+	re      *regexp.Regexp
+	negate  bool
+	dirOnly bool
+}
+
+// Matcher decides which paths a set of gitignore(5) patterns ignores.
+type Matcher struct {
+	patterns []pattern
+}
+
+// New compiles patterns in gitignore(5) syntax, in order. Blank patterns and
+// patterns starting with "#" are skipped. A nil or empty list gives a
+// matcher that matches nothing.
+func New(patterns []string) (*Matcher, error) {
+	m := &Matcher{}
+	for _, orig := range patterns {
+		p := orig
+		if p == "" || strings.HasPrefix(p, "#") {
+			continue
+		}
+		negate := false
+		switch {
+		case strings.HasPrefix(p, "!"):
+			negate = true
+			p = p[1:]
+		case strings.HasPrefix(p, `\!`), strings.HasPrefix(p, `\#`):
+			p = p[1:]
+		}
+		p = trimTrailingSpaces(p)
+		dirOnly := false
+		if strings.HasSuffix(p, "/") {
+			dirOnly = true
+			p = strings.TrimSuffix(p, "/")
+		}
+		reStr, err := toRegexp(p)
+		if err != nil {
+			return nil, fmt.Errorf("bad ignore pattern %q: %v", orig, err)
+		}
+		re, err := regexp.Compile(reStr)
+		if err != nil {
+			return nil, fmt.Errorf("bad ignore pattern %q: %v", orig, err)
+		}
+		m.patterns = append(m.patterns, pattern{re: re, negate: negate, dirOnly: dirOnly})
+	}
+	return m, nil
+}
+
+// trimTrailingSpaces removes trailing spaces that are not escaped by a
+// preceding backslash, per gitignore(5).
+func trimTrailingSpaces(p string) string {
+	for strings.HasSuffix(p, " ") {
+		n := 0
+		for i := len(p) - 2; i >= 0 && p[i] == '\\'; i-- {
+			n++
+		}
+		if n%2 == 1 {
+			break // the trailing space is escaped: keep it
+		}
+		p = p[:len(p)-1]
+	}
+	return p
+}
+
+// Match reports whether rel is ignored. rel is slash-separated and relative
+// to the root, with no leading slash and no trailing slash, and each of its
+// path components must be "." and ".."-free (as produced by a directory
+// walk, not a raw user-typed path).
+func (m *Matcher) Match(rel string, isDir bool) bool {
+	parts := strings.Split(rel, "/")
+	for i := 1; i < len(parts); i++ {
+		ancestor := strings.Join(parts[:i], "/")
+		if m.matchOne(ancestor, true) {
+			return true
+		}
+	}
+	return m.matchOne(rel, isDir)
+}
+
+// matchOne applies every pattern in order to one path and returns the final
+// ignored state, without considering ancestor directories.
+func (m *Matcher) matchOne(path string, isDir bool) bool {
+	ignored := false
+	for _, pat := range m.patterns {
+		if pat.dirOnly && !isDir {
+			continue
+		}
+		if pat.re.MatchString(path) {
+			ignored = !pat.negate
+		}
+	}
+	return ignored
+}
+
+// toRegexp translates the body of one gitignore pattern (no leading "!",
+// no trailing "/") into a regular expression over slash-separated paths.
+func toRegexp(p string) (string, error) {
+	anchored := strings.Contains(p, "/")
+	p = strings.TrimPrefix(p, "/")
+	var b strings.Builder
+	b.WriteString("^")
+	if !anchored {
+		b.WriteString("(?:.*/)?")
+	}
+	for i := 0; i < len(p); i++ {
+		c := p[i]
+		switch {
+		case strings.HasPrefix(p[i:], "**/") && (i == 0 || p[i-1] == '/'):
+			b.WriteString("(?:.*/)?")
+			i += 2
+		case strings.HasPrefix(p[i:], "/**") && i+3 == len(p):
+			b.WriteString("/.*")
+			i += 2
+		case strings.HasPrefix(p[i:], "**"):
+			b.WriteString("[^/]*")
+			i++
+		case c == '*':
+			b.WriteString("[^/]*")
+		case c == '?':
+			b.WriteString("[^/]")
+		case c == '[':
+			negated := false
+			start := i + 1
+			if start < len(p) && (p[start] == '!' || p[start] == '^') {
+				negated = true
+				start++
+			}
+			items, end, err := parseClassBody(p, start)
+			if err != nil {
+				return "", err
+			}
+			b.WriteString(renderClass(items, negated))
+			i = end
+		case c == '\\' && i+1 < len(p):
+			i++
+			b.WriteString(regexp.QuoteMeta(string(p[i])))
+		default:
+			b.WriteString(regexp.QuoteMeta(string(c)))
+		}
+	}
+	b.WriteString("$")
+	return b.String(), nil
+}
+
+// classItem is one member of a gitignore bracket expression: either a
+// verbatim POSIX bracket subexpression ("[:digit:]", "[.ch.]", "[=e=]"), or
+// a literal byte (lo == hi) or a byte range (lo-hi).
+type classItem struct {
+	posix  string
+	lo, hi byte
+}
+
+// parseClassBody scans p starting at start (just past "[", "[!" or "[^")
+// for the members of a bracket expression, up to and including the
+// matching unescaped "]". A "]" appearing immediately at start is a
+// literal member, not the terminator, per glob syntax (e.g. "[]a]" matches
+// "]" or "a"). Inside the class, "\x" escapes x to a literal member,
+// neutralizing any meaning x would otherwise have (closing the class,
+// starting a POSIX subexpression, forming a range) — matching git's
+// wildmatch. It returns the members found and the index of the closing
+// "]", or an error if none is found (including a class left unterminated
+// because its only "]" was escaped).
+func parseClassBody(p string, start int) ([]classItem, int, error) {
+	var items []classItem
+	k := start
+	if k < len(p) && p[k] == ']' {
+		items = append(items, classItem{lo: ']', hi: ']'})
+		k++
+	}
+	for k < len(p) && p[k] != ']' {
+		// "\x" escapes x to a literal member; it can never start a
+		// POSIX subexpression or a range. A backslash with nothing
+		// after it can never close the class either.
+		if p[k] == '\\' {
+			if k+1 >= len(p) {
+				return nil, 0, errors.New("unterminated [")
+			}
+			items = append(items, classItem{lo: p[k+1], hi: p[k+1]})
+			k += 2
+			continue
+		}
+		if p[k] == '[' && k+1 < len(p) && (p[k+1] == ':' || p[k+1] == '.' || p[k+1] == '=') {
+			delim := p[k+1]
+			rest := strings.Index(p[k+2:], string(delim)+"]")
+			if rest < 0 {
+				return nil, 0, errors.New("unterminated [")
+			}
+			stop := k + 2 + rest + 2
+			items = append(items, classItem{posix: p[k:stop]})
+			k = stop
+			continue
+		}
+		// "x-y" is a range unless the "-" is the last character before
+		// the closing "]", in which case it is a literal "-".
+		if k+2 < len(p) && p[k+1] == '-' && p[k+2] != ']' {
+			items = append(items, classItem{lo: p[k], hi: p[k+2]})
+			k += 3
+			continue
+		}
+		items = append(items, classItem{lo: p[k], hi: p[k]})
+		k++
+	}
+	if k >= len(p) {
+		return nil, 0, errors.New("unterminated [")
+	}
+	return items, k, nil
+}
+
+// renderClass turns the members of a bracket expression into a Go regexp
+// character class. Git's bracket expressions never match "/", regardless
+// of negation, so "/" is dropped from a positive class (splitting any range
+// that spans it) and added to a negated one. A positive class left
+// matching nothing (e.g. "[/]") is rendered as a class that can never
+// match any character, since RE2 has no empty class or lookahead.
+func renderClass(items []classItem, negated bool) string {
+	if negated {
+		items = append(items, classItem{lo: '/', hi: '/'})
+		return "[^" + renderClassItems(items) + "]"
+	}
+	items = excludeSlash(items)
+	if len(items) == 0 {
+		return `[^\x00-\x{10FFFF}]`
+	}
+	return "[" + renderClassItems(items) + "]"
+}
+
+// posixSlashFree gives the ASCII definition, minus "/", of every standard
+// POSIX bracket class whose definition otherwise includes it: graph and
+// print (visible characters, "/" among them) and punct (documented in
+// gitignore's own toRegexp derivation as "!-. :-@ [-` {-~", i.e. punct's
+// usual "!-/" range with "/" trimmed to "!-."). The other nine standard
+// classes (alnum, alpha, blank, cntrl, digit, lower, space, upper,
+// xdigit) never contain "/" and so need no rewriting.
+var posixSlashFree = map[string][]classItem{
+	"graph": {{lo: '!', hi: '.'}, {lo: '0', hi: '~'}},
+	"print": {{lo: ' ', hi: '.'}, {lo: '0', hi: '~'}},
+	"punct": {{lo: '!', hi: '.'}, {lo: ':', hi: '@'}, {lo: '[', hi: '`'}, {lo: '{', hi: '~'}},
+}
+
+// posixClassName returns the name inside a "[:name:]" POSIX bracket class,
+// or "", false for anything else (a collating symbol "[.x.]", an
+// equivalence class "[=x=]", or a malformed value).
+func posixClassName(posix string) (string, bool) {
+	if strings.HasPrefix(posix, "[:") && strings.HasSuffix(posix, ":]") {
+		return posix[2 : len(posix)-2], true
+	}
+	return "", false
+}
+
+// excludeSlash removes "/" from a positive class's members, splitting any
+// range that spans it into the parts on either side, and substituting the
+// "/"-free ASCII definition for any POSIX class that would otherwise
+// include it.
+func excludeSlash(items []classItem) []classItem {
+	var out []classItem
+	for _, it := range items {
+		switch {
+		case it.posix != "":
+			if name, ok := posixClassName(it.posix); ok {
+				if repl, hasSlash := posixSlashFree[name]; hasSlash {
+					out = append(out, repl...)
+					continue
+				}
+			}
+			out = append(out, it)
+		case it.lo == '/' && it.hi == '/':
+			// drop the lone literal "/"
+		case it.lo <= '/' && '/' <= it.hi:
+			if it.lo <= '/'-1 {
+				out = append(out, classItem{lo: it.lo, hi: '/' - 1})
+			}
+			if '/'+1 <= it.hi {
+				out = append(out, classItem{lo: '/' + 1, hi: it.hi})
+			}
+		default:
+			out = append(out, it)
+		}
+	}
+	return out
+}
+
+func renderClassItems(items []classItem) string {
+	var b strings.Builder
+	for _, it := range items {
+		switch {
+		case it.posix != "":
+			b.WriteString(it.posix)
+		case it.lo == it.hi:
+			b.WriteString(classChar(it.lo))
+		default:
+			b.WriteString(classChar(it.lo))
+			b.WriteByte('-')
+			b.WriteString(classChar(it.hi))
+		}
+	}
+	return b.String()
+}
+
+// classChar escapes a byte that would otherwise be misread by the Go
+// regexp parser when emitted as a member (or range endpoint) inside a
+// character class: "]" would close the class, "^" would negate it if
+// first, "-" would start a range, "[" could open a POSIX subexpression,
+// and "\" always needs escaping to be literal.
+func classChar(c byte) string {
+	switch c {
+	case '\\', ']', '^', '-', '[':
+		return "\\" + string(c)
+	default:
+		return string(c)
+	}
+}
diff --git a/internal/ignore/ignore_test.go b/internal/ignore/ignore_test.go
new file mode 100644
index 0000000..04b60c4
--- /dev/null
+++ b/internal/ignore/ignore_test.go
@@ -0,0 +1,58 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package ignore
+
+import "testing"
+
+func TestMatch(t *testing.T) {
+	type c struct {
+		rel   string
+		isDir bool
+		want  bool
+	}
+	tests := []struct {
+		patterns []string
+		cases    []c
+	}{
+		{[]string{"*.log"}, []c{{"a.log", false, true}, {"dir/b.log", false, true}, {"a.txt", false, false}}},
+		{[]string{"/a.txt"}, []c{{"a.txt", false, true}, {"dir/a.txt", false, false}}},
+		{[]string{"build/"}, []c{{"build", true, true}, {"build", false, false}, {"src/build", true, true}, {"build/x.bin", false, true}}},
+		{[]string{"doc/*.md"}, []c{{"doc/r.md", false, true}, {"doc/sub/r.md", false, false}, {"x/doc/r.md", false, false}}},
+		{[]string{"**/readme.md"}, []c{{"readme.md", false, true}, {"a/b/readme.md", false, true}}},
+		{[]string{"deep/**"}, []c{{"deep", true, false}, {"deep/a", true, true}, {"deep/a/b/f.tmp", false, true}}},
+		{[]string{"x/**/z.txt"}, []c{{"x/z.txt", false, true}, {"x/y/z.txt", false, true}, {"x/y/w/z.txt", false, true}, {"q/x/z.txt", false, false}}},
+		{[]string{"*.part", "!keep.part"}, []c{{"a.part", false, true}, {"keep.part", false, false}}},
+		{[]string{"dir/", "!dir/c.txt"}, []c{{"dir/c.txt", false, true}}},
+		{[]string{".*"}, []c{{".hidden", false, true}, {"a/.cfg", false, true}, {"visible", false, false}}},
+		{[]string{"a?.txt", "[bc].txt"}, []c{{"a1.txt", false, true}, {"a12.txt", false, false}, {"b.txt", false, true}, {"d.txt", false, false}}},
+		{[]string{"[!a]*.txt"}, []c{{"b.txt", false, true}, {"a.txt", false, false}}},
+		{[]string{"sub"}, []c{{"sub", true, true}, {"x/sub", true, true}, {"x/sub/f", false, true}, {"subx", false, false}}},
+		{[]string{"\\#notes", "\\!bang"}, []c{{"#notes", false, true}, {"!bang", false, true}}},
+		{[]string{"", "# comment"}, []c{{"# comment", false, false}}},
+		{nil, []c{{"anything", false, false}}},
+		{[]string{"x[]a]y"}, []c{{"x]y", false, true}, {"xay", false, true}, {"xby", false, false}}},
+		{[]string{"a[/]b"}, []c{{"a/b", false, false}}},
+	}
+	for _, tt := range tests {
+		m, err := New(tt.patterns)
+		if err != nil {
+			t.Fatalf("New(%q): %v", tt.patterns, err)
+		}
+		for _, cs := range tt.cases {
+			if got := m.Match(cs.rel, cs.isDir); got != cs.want {
+				t.Errorf("patterns %q: Match(%q, dir=%v) = %v, want %v", tt.patterns, cs.rel, cs.isDir, got, cs.want)
+			}
+		}
+	}
+}
+
+func TestBadPattern(t *testing.T) {
+	if _, err := New([]string{"[abc"}); err == nil || err.Error() != `bad ignore pattern "[abc": unterminated [` {
+		t.Fatalf("got %v", err)
+	}
+	// "\]" escapes the only "]" to a literal member, leaving the class
+	// with no terminator.
+	if _, err := New([]string{"a[\\]d"}); err == nil || err.Error() != `bad ignore pattern "a[\\]d": unterminated [` {
+		t.Fatalf("got %v", err)
+	}
+}
diff --git a/internal/ignore/oracle_test.go b/internal/ignore/oracle_test.go
new file mode 100644
index 0000000..a5a589c
--- /dev/null
+++ b/internal/ignore/oracle_test.go
@@ -0,0 +1,94 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package ignore
+
+import (
+	"os"
+	"os/exec"
+	"path/filepath"
+	"sort"
+	"strings"
+	"testing"
+)
+
+var oracleFiles = []string{
+	"a.txt", "b.log", "a1.txt", "abc", ".hidden", "foo.part", "keep.part",
+	"dir/c.txt", "dir/d.log", "dir/.hidden2", "dir/sub/e.txt",
+	"build/out.bin", "src/build/x.go", "doc/readme.md", "doc/sub/readme.md",
+	"deep/a/b/c/file.tmp", "x/z.txt", "x/y/z.txt", "sub/f.txt", "space name.txt",
+	"x]y", "xay", "xby", "a/b", "1.txt", "]a.txt",
+	"a.b", "xyz", "aq", "bq",
+}
+
+var oracleSets = [][]string{
+	{"*.log"}, {"/a.txt"}, {"build/"}, {"doc/*.md"}, {"**/readme.md"},
+	{"deep/**"}, {"x/**/z.txt"}, {"*.part", "!keep.part"}, {".*"},
+	{"a?.txt", "[ab]*.txt"}, {"[!a]*.txt"}, {"dir/", "!dir/c.txt"},
+	{"sub"}, {"space name.txt"}, {"*", "!*.txt"}, {"dir/**/*.txt"},
+	{"x[]a]y"}, {"a[/]b"}, {"[[:digit:]]*.txt"}, {"[!]a]*"},
+	{"a[[:punct:]]b"}, {"x[[:alpha:]]z"}, {"[a\\b]q"},
+}
+
+// TestAgainstGit compares every file and directory of a real tree against
+// `git check-ignore --no-index` for each pattern set.
+func TestAgainstGit(t *testing.T) {
+	if _, err := exec.LookPath("git"); err != nil {
+		t.Skip("git not installed")
+	}
+	root := t.TempDir()
+	t.Setenv("HOME", root)
+	t.Setenv("GIT_CONFIG_GLOBAL", os.DevNull)
+	t.Setenv("GIT_CONFIG_NOSYSTEM", "1")
+	for _, f := range oracleFiles {
+		p := filepath.Join(root, f)
+		if err := os.MkdirAll(filepath.Dir(p), 0o755); err != nil {
+			t.Fatal(err)
+		}
+		if err := os.WriteFile(p, nil, 0o644); err != nil {
+			t.Fatal(err)
+		}
+	}
+	if out, err := exec.Command("git", "-C", root, "init", "-q").CombinedOutput(); err != nil {
+		t.Fatalf("git init: %v %s", err, out)
+	}
+	// every path in the tree, files and directories, relative and slash-separated
+	var paths []string
+	isDir := map[string]bool{}
+	filepath.WalkDir(root, func(p string, d os.DirEntry, err error) error {
+		rel, _ := filepath.Rel(root, p)
+		if rel == "." || rel == ".git" || strings.HasPrefix(rel, ".git"+string(filepath.Separator)) || rel == ".gitignore" {
+			if rel == ".git" {
+				return filepath.SkipDir
+			}
+			return nil
+		}
+		rel = filepath.ToSlash(rel)
+		paths = append(paths, rel)
+		isDir[rel] = d.IsDir()
+		return nil
+	})
+	sort.Strings(paths)
+	for _, set := range oracleSets {
+		if err := os.WriteFile(filepath.Join(root, ".gitignore"), []byte(strings.Join(set, "\n")+"\n"), 0o644); err != nil {
+			t.Fatal(err)
+		}
+		cmd := exec.Command("git", "-C", root, "check-ignore", "--no-index", "--stdin")
+		cmd.Stdin = strings.NewReader(strings.Join(paths, "\n") + "\n")
+		out, _ := cmd.Output() // exit status 1 means "nothing ignored"
+		gitIgnored := map[string]bool{}
+		for _, l := range strings.Split(strings.TrimSpace(string(out)), "\n") {
+			if l != "" {
+				gitIgnored[strings.TrimSuffix(l, "/")] = true
+			}
+		}
+		m, err := New(set)
+		if err != nil {
+			t.Fatalf("New(%q): %v", set, err)
+		}
+		for _, p := range paths {
+			if got := m.Match(p, isDir[p]); got != gitIgnored[p] {
+				t.Errorf("patterns %q, path %q (dir=%v): krino says %v, git says %v", set, p, isDir[p], got, gitIgnored[p])
+			}
+		}
+	}
+}