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

5 files changed, 1173 insertions, 0 deletions

diff --git a/internal/cond/compile.go b/internal/cond/compile.go
new file mode 100644
index 0000000..4fdc75f
--- /dev/null
+++ b/internal/cond/compile.go
@@ -0,0 +1,388 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package cond
+
+import (
+	"errors"
+	"fmt"
+	"regexp"
+	"regexp/syntax"
+	"sort"
+	"strings"
+
+	"krino/internal/config"
+	"krino/internal/norm"
+	"krino/internal/sexp"
+)
+
+// maxDepth is the deepest a condition may nest; the top-level conditions
+// are depth 1.
+const maxDepth = 64
+
+// Compile compiles a rule's (when ...) conditions, applying cost-based
+// reordering. If it returns any diagnostic, the returned *Cond is nil: a
+// caller that ignores errs and calls Eval/Explain on the result panics
+// loudly, instead of silently treating a broken rule as "no conditions"
+// (always true).
+func Compile(file string, when []*sexp.Node, opt Options) (*Cond, []*config.Diag) {
+	c, errs := compile(file, when, opt, true)
+	if len(errs) > 0 {
+		return nil, errs
+	}
+	return c, errs
+}
+
+// compile is Compile with cost reordering switchable, for the property test
+// in Task 8.
+func compile(file string, when []*sexp.Node, opt Options, reorder bool) (*Cond, []*config.Diag) {
+	c := &compiler{file: file, opt: opt, reorder: reorder, cond: &Cond{opt: opt}}
+	var roots []*node
+	for _, n := range when {
+		if nd := c.compileNode(n, 1); nd != nil {
+			roots = append(roots, nd)
+		}
+	}
+	switch len(roots) {
+	case 0:
+		// no conditions: root stays nil, always true
+	case 1:
+		c.cond.root = roots[0]
+	default:
+		// several top-level conditions are an implicit and
+		c.cond.root = c.combine(kAnd, "and", roots, when[0].Pos)
+	}
+	return c.cond, c.errs
+}
+
+// compiler holds the state of one Compile call.
+type compiler struct {
+	file    string
+	opt     Options
+	reorder bool
+	cond    *Cond
+	errs    []*config.Diag
+}
+
+// errorf records a diagnostic at n's position; a nil n means the file as a
+// whole (unused here, kept for symmetry with config.diags).
+func (c *compiler) errorf(n *sexp.Node, format string, args ...any) {
+	var pos sexp.Pos
+	if n != nil {
+		pos = n.Pos
+	}
+	c.errs = append(c.errs, &config.Diag{File: c.file, Pos: pos, Msg: fmt.Sprintf(format, args...)})
+}
+
+// compileNode compiles one condition node at the given nesting depth (the
+// top-level conditions are depth 1). It returns nil, having recorded at
+// least one diagnostic, when n does not compile.
+func (c *compiler) compileNode(n *sexp.Node, depth int) *node {
+	if depth > maxDepth {
+		c.errorf(n, "conditions nest deeper than %d levels", maxDepth)
+		return nil
+	}
+	if n.Kind != sexp.List || n.Head() == "" {
+		c.errorf(n, "a condition is a form like (type pdf), not %s", n.String())
+		return nil
+	}
+	switch head := n.Head(); head {
+	case "and":
+		return c.compileCombiner(n, depth, kAnd, "and", "and needs at least one condition")
+	case "or":
+		return c.compileCombiner(n, depth, kOr, "or", "or needs at least one condition")
+	case "not":
+		return c.compileNot(n, depth)
+	case "type":
+		return c.compileType(n)
+	case "name":
+		return c.compileRegex(n, kName, "name")
+	case "path":
+		return c.compileRegex(n, kPath, "path")
+	case "content":
+		return c.compileContent(n)
+	case "size":
+		return c.compileSize(n)
+	case "age":
+		return c.compileAge(n)
+	case "duplicate":
+		return c.compileDuplicate(n)
+	case "matched":
+		return c.compileMatched(n)
+	default:
+		c.errorf(n, "unknown test (%s ...); tests are type, name, path, content, size, age, duplicate, matched, and, or, not", head)
+		return nil
+	}
+}
+
+// compileCombiner compiles (and ...) / (or ...): one or more child
+// conditions, cost-summed and cost-sorted (via combine).
+func (c *compiler) compileCombiner(n *sexp.Node, depth int, k kind, label, emptyMsg string) *node {
+	args := n.Args()
+	if len(args) == 0 {
+		c.errorf(n, "%s", emptyMsg)
+		return nil
+	}
+	children := make([]*node, 0, len(args))
+	for _, a := range args {
+		if ch := c.compileNode(a, depth+1); ch != nil {
+			children = append(children, ch)
+		}
+	}
+	return c.combine(k, label, children, n.Pos)
+}
+
+// combine builds an and/or node from already-compiled children: stable
+// cost-sort when reordering, cost is the sum of the children's.
+func (c *compiler) combine(k kind, label string, children []*node, pos sexp.Pos) *node {
+	if len(children) == 0 {
+		return nil
+	}
+	if c.reorder {
+		sort.SliceStable(children, func(i, j int) bool { return children[i].cost < children[j].cost })
+	}
+	cost := 0
+	for _, ch := range children {
+		cost += ch.cost
+	}
+	return &node{kind: k, pos: pos, label: label, children: children, cost: cost}
+}
+
+// compileNot compiles (not C): exactly one child condition.
+func (c *compiler) compileNot(n *sexp.Node, depth int) *node {
+	args := n.Args()
+	if len(args) != 1 {
+		c.errorf(n, "not takes exactly one condition")
+		return nil
+	}
+	child := c.compileNode(args[0], depth+1)
+	if child == nil {
+		return nil
+	}
+	return &node{kind: kNot, pos: n.Pos, label: "not", children: []*node{child}, cost: child.cost}
+}
+
+// compileType compiles (type T...): symbols, lower-cased; a group name
+// expands to its extensions, anything else is a literal (possibly
+// multi-part) extension.
+func (c *compiler) compileType(n *sexp.Node) *node {
+	args := n.Args()
+	if len(args) == 0 {
+		c.errorf(n, "type needs at least one extension or group, like (type pdf)")
+		return nil
+	}
+	var suffixes []string
+	bad := false
+	for _, a := range args {
+		if a.Kind != sexp.Symbol {
+			c.errorf(a, "type names are bare words: write (type pdf)")
+			bad = true
+			continue
+		}
+		lower := strings.ToLower(a.Text)
+		if exts, ok := groups[lower]; ok {
+			for _, e := range exts {
+				suffixes = append(suffixes, "."+e)
+			}
+		} else {
+			suffixes = append(suffixes, "."+lower)
+		}
+	}
+	if bad {
+		return nil
+	}
+	return &node{kind: kType, pos: n.Pos, label: argsLabel("type", args), cost: costCheap, suffixes: suffixes}
+}
+
+// compileRegex compiles (name "RE"...) / (path "RE"...).
+func (c *compiler) compileRegex(n *sexp.Node, k kind, test string) *node {
+	args := n.Args()
+	if len(args) == 0 {
+		c.errorf(n, "%s needs at least one regex in quotes", test)
+		return nil
+	}
+	var patterns []pattern
+	bad := false
+	for _, a := range args {
+		if a.Kind != sexp.String {
+			c.quotedExampleErr(a, test, "regexes")
+			bad = true
+			continue
+		}
+		src := a.Text
+		pat := src
+		if c.opt.Fold {
+			// E5: folding is applied to the regex source itself, not just
+			// to the text it is matched against - so a fold that expands
+			// one character into several changes the pattern's structure,
+			// not just its literal characters: "ß+" (one letter, a
+			// quantifier on it) becomes "ss+" (a quantifier on only the
+			// second "s") once norm.Fold expands "ß" to "ss", and likewise
+			// "æ" to "ae". A rule relying on repetition or anchoring
+			// around such a letter needs to account for this.
+			pat = norm.Fold(pat)
+		}
+		if c.opt.IgnoreCase {
+			pat = "(?i)" + pat
+		}
+		re, err := regexp.Compile(pat)
+		if err != nil {
+			var se *syntax.Error
+			if errors.As(err, &se) {
+				c.errorf(a, "%s: bad regex %q: %s", test, src, se.Code)
+			} else {
+				c.errorf(a, "%s: bad regex %q: %s", test, src, err)
+			}
+			bad = true
+			continue
+		}
+		patterns = append(patterns, pattern{re: re, src: src})
+	}
+	if bad {
+		return nil
+	}
+	return &node{kind: k, pos: n.Pos, label: argsLabel(test, args), cost: costRegex, patterns: patterns}
+}
+
+// compileContent compiles (content "KW"...): each keyword is normalised;
+// an empty result is an error.
+func (c *compiler) compileContent(n *sexp.Node) *node {
+	args := n.Args()
+	if len(args) == 0 {
+		c.errorf(n, "content needs at least one keyword in quotes")
+		return nil
+	}
+	var keywords []keyword
+	bad := false
+	for _, a := range args {
+		if a.Kind != sexp.String {
+			c.quotedExampleErr(a, "content", "keywords")
+			bad = true
+			continue
+		}
+		normed := norm.Text(a.Text, c.opt.IgnoreCase, c.opt.Fold)
+		if normed == "" {
+			c.errorf(a, "content keyword is empty")
+			bad = true
+			continue
+		}
+		keywords = append(keywords, keyword{norm: normed, src: a.Text})
+	}
+	if bad {
+		return nil
+	}
+	c.cond.UsesContent = true
+	return &node{kind: kContent, pos: n.Pos, label: argsLabel("content", args), cost: costContent, keywords: keywords}
+}
+
+// compileSize compiles (size OP SIZE).
+func (c *compiler) compileSize(n *sexp.Node) *node {
+	args := n.Args()
+	if len(args) != 2 || args[0].Kind != sexp.Symbol || args[1].Kind != sexp.Symbol {
+		c.errorf(n, "size takes an operator and a size, like (size > 10M)")
+		return nil
+	}
+	op := args[0].Text
+	bad := false
+	if !validOp(op) {
+		c.errorf(args[0], "size operator is one of > >= < <= =, not %s", op)
+		bad = true
+	}
+	val, err := config.ParseSize(args[1].Text)
+	if err != nil {
+		c.errorf(args[1], "size: %s", err)
+		bad = true
+	}
+	if bad {
+		return nil
+	}
+	return &node{kind: kSize, pos: n.Pos, label: argsLabel("size", args), cost: costCheap, op: op, sizeVal: val}
+}
+
+// compileAge compiles (age OP DURATION).
+func (c *compiler) compileAge(n *sexp.Node) *node {
+	args := n.Args()
+	if len(args) != 2 || args[0].Kind != sexp.Symbol || args[1].Kind != sexp.Symbol {
+		c.errorf(n, "age takes an operator and a duration, like (age > 30d)")
+		return nil
+	}
+	op := args[0].Text
+	bad := false
+	if !validOp(op) {
+		c.errorf(args[0], "age operator is one of > >= < <= =, not %s", op)
+		bad = true
+	}
+	val, err := config.ParseDuration(args[1].Text)
+	if err != nil {
+		c.errorf(args[1], "age: %s", err)
+		bad = true
+	}
+	if bad {
+		return nil
+	}
+	return &node{kind: kAge, pos: n.Pos, label: argsLabel("age", args), cost: costCheap, op: op, ageVal: val}
+}
+
+// validOp reports whether op is one of the size/age comparison operators.
+func validOp(op string) bool {
+	switch op {
+	case ">", ">=", "<", "<=", "=":
+		return true
+	}
+	return false
+}
+
+// compileDuplicate compiles (duplicate "DIR"...): zero or more directories,
+// stored raw for the engine to resolve. Every compiled test's list is
+// appended to Cond.DupDirs, in order.
+func (c *compiler) compileDuplicate(n *sexp.Node) *node {
+	args := n.Args()
+	dirs := make([]string, 0, len(args))
+	bad := false
+	for _, a := range args {
+		if a.Kind != sexp.String {
+			c.quotedExampleErr(a, "duplicate", "directories")
+			bad = true
+			continue
+		}
+		dirs = append(dirs, a.Text)
+	}
+	if bad {
+		return nil
+	}
+	c.cond.DupDirs = append(c.cond.DupDirs, dirs)
+	return &node{kind: kDuplicate, pos: n.Pos, label: argsLabel("duplicate", args), cost: costDuplicate, dirs: dirs}
+}
+
+// compileMatched compiles (matched): no arguments.
+func (c *compiler) compileMatched(n *sexp.Node) *node {
+	if len(n.Args()) != 0 {
+		c.errorf(n, "matched takes nothing: write (matched)")
+		return nil
+	}
+	return &node{kind: kMatched, pos: n.Pos, label: "matched", cost: costCheap}
+}
+
+// quotedExampleErr records the shared "takes X in quotes: write (test
+// "arg")" diagnostic used by name, path, content and duplicate.
+func (c *compiler) quotedExampleErr(a *sexp.Node, test, noun string) {
+	c.errorf(a, "%s takes %s in quotes: write (%s %s)", test, noun, test, sexp.Quote(a.Text))
+}
+
+// argsLabel renders a leaf test as written: the head followed by each
+// argument, bare symbols verbatim, strings as their decoded text in double
+// quotes without escaping.
+func argsLabel(head string, args []*sexp.Node) string {
+	var b strings.Builder
+	b.WriteString(head)
+	for _, a := range args {
+		b.WriteByte(' ')
+		if a.Kind == sexp.String {
+			b.WriteByte('"')
+			b.WriteString(a.Text)
+			b.WriteByte('"')
+		} else {
+			b.WriteString(a.Text)
+		}
+	}
+	return b.String()
+}
diff --git a/internal/cond/compile_test.go b/internal/cond/compile_test.go
new file mode 100644
index 0000000..e68a4d8
--- /dev/null
+++ b/internal/cond/compile_test.go
@@ -0,0 +1,150 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package cond
+
+import (
+	"reflect"
+	"strings"
+	"testing"
+
+	"krino/internal/sexp"
+)
+
+func nodes(t *testing.T, src string) []*sexp.Node {
+	t.Helper()
+	n, err := sexp.Parse("d.conf", []byte(src))
+	if err != nil {
+		t.Fatalf("parse %q: %v", src, err)
+	}
+	return n
+}
+
+func TestCompileGood(t *testing.T) {
+	for _, src := range []string{
+		``,
+		`(type pdf)`,
+		`(type document image tar.gz)`,
+		`(and (type pdf) (or (content "acme ltd" "0000000000") (name "\bacme\b")) (not (name "^draft")))`,
+		`(path "^Work/") (size >= 10M) (age < 2w) (matched)`,
+		`(duplicate) (duplicate "Work" "~/docs")`,
+		`(not (not (type pdf)))`,
+	} {
+		if _, errs := Compile("d.conf", nodes(t, src), Options{IgnoreCase: true, Fold: true}); len(errs) > 0 {
+			t.Errorf("%s: %v", src, errs)
+		}
+	}
+}
+
+func TestCompileErrors(t *testing.T) {
+	tests := []struct{ src, want string }{
+		{`pdf`, `d.conf:1:1: a condition is a form like (type pdf), not pdf`},
+		{`("type" pdf)`, `d.conf:1:1: a condition is a form like (type pdf), not ("type" pdf)`},
+		{`(foo 1)`, `d.conf:1:1: unknown test (foo ...); tests are type, name, path, content, size, age, duplicate, matched, and, or, not`},
+		{`(and)`, `d.conf:1:1: and needs at least one condition`},
+		{`(or)`, `d.conf:1:1: or needs at least one condition`},
+		{`(not)`, `d.conf:1:1: not takes exactly one condition`},
+		{`(not (type pdf) (type doc))`, `d.conf:1:1: not takes exactly one condition`},
+		{`(type)`, `d.conf:1:1: type needs at least one extension or group, like (type pdf)`},
+		{`(type "pdf")`, `d.conf:1:7: type names are bare words: write (type pdf)`},
+		{`(name)`, `d.conf:1:1: name needs at least one regex in quotes`},
+		{`(path)`, `d.conf:1:1: path needs at least one regex in quotes`},
+		{`(name x)`, `d.conf:1:7: name takes regexes in quotes: write (name "x")`},
+		{`(name "(abc")`, `d.conf:1:7: name: bad regex "(abc": missing closing )`},
+		{`(path "[z-a]")`, `d.conf:1:7: path: bad regex "[z-a]": invalid character class range`},
+		{`(content)`, `d.conf:1:1: content needs at least one keyword in quotes`},
+		{`(content acme)`, `d.conf:1:10: content takes keywords in quotes: write (content "acme")`},
+		{`(content "  ")`, `d.conf:1:10: content keyword is empty`},
+		{`(size 10M)`, `d.conf:1:1: size takes an operator and a size, like (size > 10M)`},
+		{`(age 30d)`, `d.conf:1:1: age takes an operator and a duration, like (age > 30d)`},
+		{`(size >> 10M)`, `d.conf:1:7: size operator is one of > >= < <= =, not >>`},
+		{`(size > 10Q)`, `d.conf:1:9: size: bad size "10Q": want a whole number with an optional K, M, G or T, like 50M`},
+		{`(age > 30)`, `d.conf:1:8: age: bad duration "30": want a whole number followed by s, m, h, d or w, like 30d`},
+		{`(duplicate Work)`, `d.conf:1:12: duplicate takes directories in quotes: write (duplicate "Work")`},
+		{`(matched x)`, `d.conf:1:1: matched takes nothing: write (matched)`},
+	}
+	for _, tt := range tests {
+		_, errs := Compile("d.conf", nodes(t, tt.src), Options{IgnoreCase: true})
+		if len(errs) != 1 || errs[0].Error() != tt.want {
+			t.Errorf("%s:\n got  %v\n want %s", tt.src, errs, tt.want)
+		}
+	}
+}
+
+func TestCompileCollectsAllErrors(t *testing.T) {
+	_, errs := Compile("d.conf", nodes(t, `(type "a") (size 1) (matched x)`), Options{})
+	if len(errs) != 3 {
+		t.Fatalf("got %d errors: %v", len(errs), errs)
+	}
+}
+
+func TestDepthLimit(t *testing.T) {
+	deep := func(n int) string { return strings.Repeat("(not ", n) + "(type pdf)" + strings.Repeat(")", n) }
+	if _, errs := Compile("d.conf", nodes(t, deep(63)), Options{}); len(errs) != 0 {
+		t.Fatalf("64 levels rejected: %v", errs)
+	}
+	_, errs := Compile("d.conf", nodes(t, deep(64)), Options{})
+	if len(errs) != 1 || !strings.HasSuffix(errs[0].Error(), "conditions nest deeper than 64 levels") {
+		t.Fatalf("65 levels: %v", errs)
+	}
+}
+
+func TestFlagsAndDupDirs(t *testing.T) {
+	c, _ := Compile("d.conf", nodes(t, `(or (type pdf) (content "x")) (duplicate) (duplicate "Work" "~/docs")`), Options{})
+	if !c.UsesContent {
+		t.Error("UsesContent not set")
+	}
+	if want := [][]string{{}, {"Work", "~/docs"}}; !reflect.DeepEqual(c.DupDirs, want) {
+		t.Errorf("DupDirs = %#v, want %#v", c.DupDirs, want)
+	}
+	c, _ = Compile("d.conf", nodes(t, `(type pdf)`), Options{})
+	if c.UsesContent || len(c.DupDirs) != 0 {
+		t.Errorf("flags set without content/duplicate tests: %+v", c)
+	}
+}
+
+func TestCompileErrorReturnsNilCond(t *testing.T) {
+	c, errs := Compile("d.conf", nodes(t, `(type "pdf")`), Options{})
+	if len(errs) != 1 || c != nil {
+		t.Fatalf("got c=%v errs=%v, want c=nil and exactly one error", c, errs)
+	}
+}
+
+// TestEmptyChildrenGuard is a regression test for combine's empty-children
+// guard: an and/or all of whose children failed to compile must not become
+// a hollow node that evaluates vacuously (and -> true). Without the guard,
+// the inner (and (name "[")) would compile to an empty and, evaluate to
+// true, and the outer or would match on any file.
+func TestEmptyChildrenGuard(t *testing.T) {
+	c, errs := compile("d.conf", nodes(t, `(or (type pdf) (and (name "[")))`), Options{}, true)
+	if len(errs) != 1 {
+		t.Fatalf("got %d errors, want 1: %v", len(errs), errs)
+	}
+	if c.Eval(&fake{name: "x.txt"}).Match {
+		t.Error("hollow and inside or vacuously matched")
+	}
+}
+
+func TestGroupsMatchSpec(t *testing.T) {
+	want := map[string]string{
+		"image":        "jpg jpeg png gif webp bmp tif tiff heic heif avif svg ico raw cr2 nef arw dng",
+		"video":        "mp4 mkv webm mov avi m4v mpg mpeg wmv flv 3gp",
+		"audio":        "mp3 flac ogg opus m4a aac wav wma aiff",
+		"archive":      "zip tar gz tgz bz2 tbz2 xz txz zst 7z rar lz lzma cpio",
+		"document":     "pdf doc docx odt rtf txt md tex",
+		"spreadsheet":  "xls xlsx ods csv tsv",
+		"presentation": "ppt pptx odp",
+		"ebook":        "epub mobi azw azw3 fb2 djvu",
+		"code":         "go c h cpp hpp py sh js ts rs java rb pl lua html css json yaml yml toml xml sql",
+		"text":         "txt md log csv tsv json yaml yml toml xml ini conf",
+		"package":      "deb rpm apk appimage exe msi flatpak snap",
+		"font":         "ttf otf woff woff2",
+	}
+	if len(groups) != len(want) {
+		t.Fatalf("%d groups, want %d", len(groups), len(want))
+	}
+	for g, exts := range want {
+		if got := strings.Join(groups[g], " "); got != exts {
+			t.Errorf("group %s = %q, want %q", g, got, exts)
+		}
+	}
+}
diff --git a/internal/cond/eval.go b/internal/cond/eval.go
new file mode 100644
index 0000000..e3093af
--- /dev/null
+++ b/internal/cond/eval.go
@@ -0,0 +1,302 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package cond
+
+import (
+	"fmt"
+	"io"
+	"strings"
+	"time"
+
+	"krino/internal/norm"
+)
+
+// Facts is what a condition may ask about one file. Implementations
+// memoise: Eval and Explain may ask the same question more than once.
+type Facts interface {
+	Name() string // base name
+	Rel() string  // slash path relative to the root
+	Size() int64
+	ModTime() time.Time
+	Now() time.Time
+	Content(ignoreCase, fold bool) (string, error) // normalised with norm.Text
+	Duplicate(dirs []string) (original string, ok bool, err error)
+	Matched() bool // an earlier rule matched this file
+}
+
+// Result is the outcome of evaluating a Cond against one file's Facts.
+type Result struct {
+	Match    bool
+	Captures []string // submatches of the first true, non-negated name test: [0] whole match, [1:] groups
+	Reasons  []string // what made it true, e.g. `type pdf`, `content "acme ltd"`, `name "\bacme\b"`
+	Warnings []string // e.g. `content unreadable: needs pdftotext, not installed`
+}
+
+// Trace is the full evaluation of every node, for krino explain.
+type Trace struct {
+	Label    string
+	Value    bool
+	Err      string
+	Children []*Trace
+}
+
+// evalCtx accumulates state across one Eval call: the captures of the
+// first true, non-negated name test, and warnings de-duplicated in
+// first-seen order.
+type evalCtx struct {
+	captures []string
+	warned   map[string]bool
+	warnings []string
+}
+
+// warn records msg unless it has already been recorded.
+func (ctx *evalCtx) warn(msg string) {
+	if msg == "" {
+		return
+	}
+	if ctx.warned == nil {
+		ctx.warned = map[string]bool{}
+	}
+	if ctx.warned[msg] {
+		return
+	}
+	ctx.warned[msg] = true
+	ctx.warnings = append(ctx.warnings, msg)
+}
+
+// Eval evaluates c against f. and/or short-circuit in (cost-sorted) order,
+// cheapest tests first, so an unreadable or slow test may never run.
+func (c *Cond) Eval(f Facts) Result {
+	if c.root == nil {
+		return Result{Match: true, Reasons: []string{"no condition"}}
+	}
+	ctx := &evalCtx{}
+	match, reasons := c.eval(c.root, f, ctx, false)
+	return Result{Match: match, Captures: ctx.captures, Reasons: reasons, Warnings: ctx.warnings}
+}
+
+// eval evaluates one node against f, short-circuiting and/or in child
+// (cost-sorted) order. negated tracks whether n is reached under an odd
+// number of enclosing nots, so a matching name test found there does not
+// supply Result.Captures.
+func (c *Cond) eval(n *node, f Facts, ctx *evalCtx, negated bool) (bool, []string) {
+	switch n.kind {
+	case kAnd:
+		var reasons []string
+		for _, ch := range n.children {
+			ok, r := c.eval(ch, f, ctx, negated)
+			if !ok {
+				return false, nil
+			}
+			reasons = append(reasons, r...)
+		}
+		return true, reasons
+	case kOr:
+		for _, ch := range n.children {
+			if ok, r := c.eval(ch, f, ctx, negated); ok {
+				return true, r
+			}
+		}
+		return false, nil
+	case kNot:
+		child := n.children[0]
+		ok, _ := c.eval(child, f, ctx, !negated)
+		if ok {
+			return false, nil
+		}
+		// E4: a negated leaf reads fine as "not " plus the leaf's own
+		// label ("not matched", "not type pdf"), but a negated and/or's
+		// bare label is just the word "and"/"or" - "not and"/"not or"
+		// reaches the user in the reasons column reading as nothing a
+		// person would write, so it is parenthesised instead, the way the
+		// config itself would write a negated combinator.
+		label := child.label
+		if child.kind == kAnd || child.kind == kOr {
+			label = "(" + child.label + " ...)"
+		}
+		return true, []string{"not " + label}
+	default:
+		ok, reason, warn, caps := c.evalLeaf(n, f)
+		if warn != "" {
+			ctx.warn(warn)
+		}
+		if !ok {
+			return false, nil
+		}
+		if caps != nil && !negated && ctx.captures == nil {
+			ctx.captures = caps
+		}
+		return true, []string{reason}
+	}
+}
+
+// evalLeaf evaluates one leaf (non-combinator) node against f: whether it
+// matched, its reason if so, a warning if a fact could not be read (only
+// content and duplicate can fail), and (for a matching name test) its
+// regex captures.
+func (c *Cond) evalLeaf(n *node, f Facts) (ok bool, reason, warn string, caps []string) {
+	switch n.kind {
+	case kType:
+		lower := strings.ToLower(f.Name())
+		for _, suf := range n.suffixes {
+			if strings.HasSuffix(lower, suf) {
+				return true, "type " + strings.TrimPrefix(suf, "."), "", nil
+			}
+		}
+		return false, "", "", nil
+
+	case kName, kPath:
+		subj := f.Name()
+		word := "name"
+		if n.kind == kPath {
+			subj = f.Rel()
+			word = "path"
+		}
+		subj = norm.Name(subj, c.opt.Fold)
+		for _, p := range n.patterns {
+			m := p.re.FindStringSubmatch(subj)
+			if m == nil {
+				continue
+			}
+			reason = word + ` "` + p.src + `"`
+			if n.kind == kName {
+				return true, reason, "", m
+			}
+			return true, reason, "", nil
+		}
+		return false, "", "", nil
+
+	case kContent:
+		text, err := f.Content(c.opt.IgnoreCase, c.opt.Fold)
+		if err != nil {
+			return false, "", "content unreadable: " + err.Error(), nil
+		}
+		for _, kw := range n.keywords {
+			if strings.Contains(text, kw.norm) {
+				return true, `content "` + kw.src + `"`, "", nil
+			}
+		}
+		return false, "", "", nil
+
+	case kSize:
+		if compareInt64(f.Size(), n.op, n.sizeVal) {
+			return true, n.label, "", nil
+		}
+		return false, "", "", nil
+
+	case kAge:
+		if compareDuration(f.Now().Sub(f.ModTime()), n.op, n.ageVal) {
+			return true, n.label, "", nil
+		}
+		return false, "", "", nil
+
+	case kDuplicate:
+		orig, dup, err := f.Duplicate(n.dirs)
+		if err != nil {
+			return false, "", "duplicate check failed: " + err.Error(), nil
+		}
+		if dup {
+			return true, "duplicate of " + orig, "", nil
+		}
+		return false, "", "", nil
+
+	case kMatched:
+		if f.Matched() {
+			return true, "matched", "", nil
+		}
+		return false, "", "", nil
+	}
+	return false, "", "", nil
+}
+
+// compareInt64 applies a size comparison operator (one of > >= < <= =).
+func compareInt64(v int64, op string, want int64) bool {
+	switch op {
+	case ">":
+		return v > want
+	case ">=":
+		return v >= want
+	case "<":
+		return v < want
+	case "<=":
+		return v <= want
+	case "=":
+		return v == want
+	}
+	return false
+}
+
+// compareDuration applies an age comparison operator (one of > >= < <= =).
+func compareDuration(v time.Duration, op string, want time.Duration) bool {
+	switch op {
+	case ">":
+		return v > want
+	case ">=":
+		return v >= want
+	case "<":
+		return v < want
+	case "<=":
+		return v <= want
+	case "=":
+		return v == want
+	}
+	return false
+}
+
+// Explain evaluates every node of c against f with no short-circuit,
+// building the full trace for krino explain.
+func (c *Cond) Explain(f Facts) *Trace {
+	if c.root == nil {
+		return &Trace{Label: "no condition", Value: true}
+	}
+	return c.explain(c.root, f)
+}
+
+// explain visits n and, for and/or/not, every child, in (cost-sorted)
+// order, always - unlike eval, it never short-circuits.
+func (c *Cond) explain(n *node, f Facts) *Trace {
+	switch n.kind {
+	case kAnd, kOr:
+		t := &Trace{Label: n.label}
+		val := n.kind == kAnd // identity: and starts true, or starts false
+		for _, ch := range n.children {
+			ct := c.explain(ch, f)
+			t.Children = append(t.Children, ct)
+			if n.kind == kAnd {
+				val = val && ct.Value
+			} else {
+				val = val || ct.Value
+			}
+		}
+		t.Value = val
+		return t
+	case kNot:
+		ct := c.explain(n.children[0], f)
+		return &Trace{Label: n.label, Value: !ct.Value, Children: []*Trace{ct}}
+	default:
+		ok, _, warn, _ := c.evalLeaf(n, f)
+		return &Trace{Label: n.label, Value: ok, Err: warn}
+	}
+}
+
+// Format writes one line per node: "yes"/"no " padded to three, two
+// spaces, two spaces of indent per depth, the label, and "  (Err)" when
+// Err is set.
+func (t *Trace) Format(w io.Writer) {
+	t.format(w, 0)
+}
+
+func (t *Trace) format(w io.Writer, depth int) {
+	word := "no"
+	if t.Value {
+		word = "yes"
+	}
+	fmt.Fprintf(w, "%-3s  %s%s", word, strings.Repeat("  ", depth), t.Label)
+	if t.Err != "" {
+		fmt.Fprintf(w, "  (%s)", t.Err)
+	}
+	fmt.Fprint(w, "\n")
+	for _, ch := range t.Children {
+		ch.format(w, depth+1)
+	}
+}
diff --git a/internal/cond/eval_test.go b/internal/cond/eval_test.go
new file mode 100644
index 0000000..3607978
--- /dev/null
+++ b/internal/cond/eval_test.go
@@ -0,0 +1,222 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package cond
+
+import (
+	"errors"
+	"math/rand"
+	"reflect"
+	"strings"
+	"testing"
+	"time"
+
+	"krino/internal/norm"
+)
+
+var now = time.Date(2026, 9, 11, 12, 0, 0, 0, time.UTC)
+
+type fake struct {
+	name, rel, raw string
+	rawErr         error
+	size           int64
+	age            time.Duration
+	matched        bool
+	dupOrig        string
+	dupOK          bool
+	contentCalls   int
+}
+
+func (f *fake) Name() string { return f.name }
+func (f *fake) Rel() string {
+	if f.rel != "" {
+		return f.rel
+	}
+	return f.name
+}
+func (f *fake) Size() int64        { return f.size }
+func (f *fake) ModTime() time.Time { return now.Add(-f.age) }
+func (f *fake) Now() time.Time     { return now }
+func (f *fake) Matched() bool      { return f.matched }
+func (f *fake) Content(ic, fold bool) (string, error) {
+	f.contentCalls++
+	if f.rawErr != nil {
+		return "", f.rawErr
+	}
+	return norm.Text(f.raw, ic, fold), nil
+}
+func (f *fake) Duplicate(dirs []string) (string, bool, error) { return f.dupOrig, f.dupOK, nil }
+
+func eval(t *testing.T, src string, opt Options, f Facts) Result {
+	t.Helper()
+	c, errs := Compile("d.conf", nodes(t, src), opt)
+	if len(errs) > 0 {
+		t.Fatalf("%s: %v", src, errs)
+	}
+	return c.Eval(f)
+}
+
+func TestTruth(t *testing.T) {
+	ic := Options{IgnoreCase: true}
+	pdf := &fake{name: "Scan001.PDF", raw: "Invoice from ACME LTD", size: 20 << 20, age: 40 * 24 * time.Hour}
+	tests := []struct {
+		src  string
+		want bool
+	}{
+		{``, true},
+		{`(type pdf)`, true},
+		{`(type document)`, true},
+		{`(type jpg)`, false},
+		{`(type pdf) (size > 10M)`, true},
+		{`(type pdf) (size < 10M)`, false},
+		{`(or (type jpg) (content "acme ltd"))`, true},
+		{`(not (content "acme ltd"))`, false},
+		{`(age > 30d) (age <= 41d)`, true},
+		{`(name "^scan\d+")`, true},
+		{`(name "(?-i)^scan")`, false},
+		{`(matched)`, false},
+		{`(and (type pdf) (or (name "^x") (not (name "^y"))))`, true},
+	}
+	for _, tt := range tests {
+		if got := eval(t, tt.src, ic, pdf); got.Match != tt.want {
+			t.Errorf("%s = %v, want %v (%+v)", tt.src, got.Match, tt.want, got)
+		}
+	}
+}
+
+func TestCaseAndFold(t *testing.T) {
+	f := &fake{name: "SPOLKA-umowa.pdf", raw: "Umowa: spółka z o.o."}
+	if !eval(t, `(name "spółka")`, Options{IgnoreCase: true, Fold: true}, f).Match {
+		t.Error("folded, case-ignoring name did not match")
+	}
+	if eval(t, `(name "spółka")`, Options{IgnoreCase: true, Fold: false}, f).Match {
+		t.Error("matched without folding")
+	}
+	if !eval(t, `(content "SPOLKA Z O.O.")`, Options{IgnoreCase: true, Fold: true}, f).Match {
+		t.Error("folded content did not match")
+	}
+	img := &fake{name: "IMG_0001.jpg"}
+	if eval(t, `(name "^img")`, Options{IgnoreCase: false}, img).Match {
+		t.Error("strict case matched")
+	}
+	if !eval(t, `(name "(?i)^img")`, Options{IgnoreCase: false}, img).Match {
+		t.Error("inline (?i) did not override strict case")
+	}
+}
+
+func TestReasonsAndCaptures(t *testing.T) {
+	f := &fake{name: "Screenshot_20260911.png", raw: "acme ltd"}
+	r := eval(t, `(type image) (name "^Screenshot_(\d{4})(\d{2})") (not (name "^x(y)"))`, Options{IgnoreCase: true}, f)
+	if !r.Match {
+		t.Fatal("no match")
+	}
+	if want := []string{"Screenshot_202609", "2026", "09"}; !reflect.DeepEqual(r.Captures, want) {
+		t.Errorf("captures = %q, want %q", r.Captures, want)
+	}
+	if want := []string{`type png`, `name "^Screenshot_(\d{4})(\d{2})"`, `not name "^x(y)"`}; !reflect.DeepEqual(r.Reasons, want) {
+		t.Errorf("reasons = %q, want %q", r.Reasons, want)
+	}
+	r = eval(t, `(or (content "nope" "acme ltd") (type png))`, Options{IgnoreCase: true}, f)
+	if want := []string{`type png`}; !reflect.DeepEqual(r.Reasons, want) {
+		t.Errorf("or reasons = %q, want %q (cheapest true child)", r.Reasons, want)
+	}
+	r = eval(t, `(content "nope" "acme ltd")`, Options{IgnoreCase: true}, f)
+	if want := []string{`content "acme ltd"`}; !reflect.DeepEqual(r.Reasons, want) {
+		t.Errorf("content reasons = %q, want %q", r.Reasons, want)
+	}
+	if r := eval(t, ``, Options{}, f); !reflect.DeepEqual(r.Reasons, []string{"no condition"}) {
+		t.Errorf("empty reasons = %q", r.Reasons)
+	}
+	d := &fake{name: "report (1).pdf", dupOrig: "report.pdf", dupOK: true}
+	if r := eval(t, `(duplicate)`, Options{}, d); !r.Match || r.Reasons[0] != "duplicate of report.pdf" {
+		t.Errorf("duplicate = %+v", r)
+	}
+}
+
+func TestCheapFirstAvoidsContent(t *testing.T) {
+	f := &fake{name: "a.txt", raw: "x"}
+	eval(t, `(and (content "x") (type pdf))`, Options{}, f)
+	if f.contentCalls != 0 {
+		t.Errorf("content read although type was false (%d calls)", f.contentCalls)
+	}
+	g := &fake{name: "a.pdf", raw: "x"}
+	eval(t, `(or (content "x") (type pdf))`, Options{}, g)
+	if g.contentCalls != 0 {
+		t.Errorf("content read although type was true (%d calls)", g.contentCalls)
+	}
+}
+
+func TestContentErrorWarns(t *testing.T) {
+	f := &fake{name: "a.pdf", rawErr: errors.New("needs pdftotext, not installed")}
+	r := eval(t, `(or (content "acme") (content "other"))`, Options{}, f)
+	if r.Match {
+		t.Fatal("matched unreadable content")
+	}
+	if want := []string{"content unreadable: needs pdftotext, not installed"}; !reflect.DeepEqual(r.Warnings, want) {
+		t.Errorf("warnings = %q, want %q (de-duplicated)", r.Warnings, want)
+	}
+}
+
+func TestExplainFormat(t *testing.T) {
+	f := &fake{name: "scan.pdf", rawErr: errors.New("needs pdftotext, not installed")}
+	c, _ := Compile("d.conf", nodes(t, `(type pdf) (or (content "acme ltd") (name "\bacme\b"))`), Options{IgnoreCase: true})
+	var b strings.Builder
+	c.Explain(f).Format(&b)
+	want := "no   and\n" +
+		"yes    type pdf\n" +
+		"no     or\n" +
+		"no       name \"\\bacme\\b\"\n" +
+		"no       content \"acme ltd\"  (content unreadable: needs pdftotext, not installed)\n"
+	if b.String() != want {
+		t.Fatalf("got\n%s\nwant\n%s", b.String(), want)
+	}
+}
+
+// TestReorderKeepsMeaning: random trees give the same answer with and without
+// cost reordering.
+func TestReorderKeepsMeaning(t *testing.T) {
+	leaves := []string{`(type pdf)`, `(type txt)`, `(name "^a")`, `(name "b$")`, `(size > 10)`, `(size < 5)`,
+		`(age > 1d)`, `(content "x")`, `(content "y")`, `(matched)`}
+	rng := rand.New(rand.NewSource(1))
+	var gen func(depth int) string
+	gen = func(depth int) string {
+		if depth == 0 || rng.Intn(3) == 0 {
+			return leaves[rng.Intn(len(leaves))]
+		}
+		switch rng.Intn(3) {
+		case 0:
+			return "(not " + gen(depth-1) + ")"
+		case 1:
+			return "(and " + gen(depth-1) + " " + gen(depth-1) + ")"
+		default:
+			return "(or " + gen(depth-1) + " " + gen(depth-1) + " " + gen(depth-1) + ")"
+		}
+	}
+	names := []string{"a.pdf", "b.txt", "ab.pdf", "c.jpg"}
+	for i := 0; i < 500; i++ {
+		src := gen(4)
+		f := &fake{name: names[rng.Intn(len(names))], raw: []string{"x", "y", "xy", ""}[rng.Intn(4)],
+			size: int64(rng.Intn(20)), age: time.Duration(rng.Intn(72)) * time.Hour, matched: rng.Intn(2) == 0}
+		a, _ := compile("d.conf", nodes(t, src), Options{}, true)
+		b, _ := compile("d.conf", nodes(t, src), Options{}, false)
+		if ra, rb := a.Eval(f), b.Eval(f); ra.Match != rb.Match {
+			t.Fatalf("%s on %+v: reordered %v, original %v", src, f, ra.Match, rb.Match)
+		}
+	}
+}
+
+// TestNegatedCombinatorReason: E4. Negating a combinator must read as
+// something a person would write ("not (and ...)" / "not (or ...)"), not
+// the bare "not and" / "not or"; a negated leaf keeps its own label
+// unchanged ("not matched").
+func TestNegatedCombinatorReason(t *testing.T) {
+	f := &fake{name: "a.pdf"}
+	if r := eval(t, `(not (and (type pdf) (matched)))`, Options{}, f); !r.Match || r.Reasons[0] != "not (and ...)" {
+		t.Errorf("negated and = %+v, want reason %q", r, "not (and ...)")
+	}
+	if r := eval(t, `(not (or (matched) (name "^zzz")))`, Options{}, f); !r.Match || r.Reasons[0] != "not (or ...)" {
+		t.Errorf("negated or = %+v, want reason %q", r, "not (or ...)")
+	}
+	if r := eval(t, `(not (matched))`, Options{}, f); !r.Match || r.Reasons[0] != "not matched" {
+		t.Errorf("negated leaf = %+v, want its own label unchanged: %q", r, "not matched")
+	}
+}
diff --git a/internal/cond/types.go b/internal/cond/types.go
new file mode 100644
index 0000000..81c2f45
--- /dev/null
+++ b/internal/cond/types.go
@@ -0,0 +1,111 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// Package cond compiles the s-expression conditions of a rule's (when ...)
+// into a tree that Task 8's evaluator walks against one file's facts.
+package cond
+
+import (
+	"regexp"
+	"time"
+
+	"krino/internal/sexp"
+)
+
+// Options carries a rule's resolved case and fold settings into compilation.
+type Options struct {
+	IgnoreCase bool // the rule's resolved case setting is "ignore"
+	Fold       bool // the rule's resolved fold setting
+}
+
+// Cond is a compiled condition. A Cond compiled from no conditions (a rule
+// without when) is always true.
+type Cond struct {
+	root        *node      // nil: always true
+	opt         Options    // the case/fold settings conditions were compiled with; Task 8 needs them again at eval time
+	UsesContent bool       // some content test exists
+	DupDirs     [][]string // the raw directory arguments of each duplicate test, in order
+}
+
+// kind is what a compiled node tests, or how it combines its children.
+type kind int
+
+const (
+	kAnd kind = iota
+	kOr
+	kNot
+	kType
+	kName
+	kPath
+	kContent
+	kSize
+	kAge
+	kDuplicate
+	kMatched
+)
+
+// Costs, per the brief's cost order: cheapest first when sorting and/or
+// children. not takes its child's cost; and/or take the sum of theirs.
+const (
+	costCheap     = 1 // type, size, age, matched
+	costRegex     = 2 // name, path
+	costDuplicate = 5
+	costContent   = 10
+)
+
+// pattern is one name/path regex, compiled and paired with the text it was
+// written as (undecorated by (?i) or folding), for labels and reasons.
+type pattern struct {
+	re  *regexp.Regexp
+	src string
+}
+
+// keyword is one content keyword, normalised for matching and paired with
+// the text it was written as, for labels and reasons.
+type keyword struct {
+	norm string
+	src  string
+}
+
+// node is one compiled condition: a leaf test, or an and/or/not combinator
+// over other nodes. Task 8 evaluates this tree.
+type node struct {
+	kind     kind
+	pos      sexp.Pos // the position of the node as written, for diagnostics
+	label    string   // the test as written, e.g. `content "acme ltd" "0000000000"`
+	cost     int      // this node's evaluation cost; and/or sort children by it
+	children []*node  // and, or, not
+
+	// type
+	suffixes []string // leading-dot, lower-case, e.g. ".pdf"
+
+	// name, path
+	patterns []pattern
+
+	// content
+	keywords []keyword
+
+	// size, age (kind tells which is populated)
+	op      string
+	sizeVal int64
+	ageVal  time.Duration
+
+	// duplicate
+	dirs []string
+}
+
+// groups maps a (type ...) group name to the extensions it expands to,
+// spec Appendix A.
+var groups = map[string][]string{
+	"image":        {"jpg", "jpeg", "png", "gif", "webp", "bmp", "tif", "tiff", "heic", "heif", "avif", "svg", "ico", "raw", "cr2", "nef", "arw", "dng"},
+	"video":        {"mp4", "mkv", "webm", "mov", "avi", "m4v", "mpg", "mpeg", "wmv", "flv", "3gp"},
+	"audio":        {"mp3", "flac", "ogg", "opus", "m4a", "aac", "wav", "wma", "aiff"},
+	"archive":      {"zip", "tar", "gz", "tgz", "bz2", "tbz2", "xz", "txz", "zst", "7z", "rar", "lz", "lzma", "cpio"},
+	"document":     {"pdf", "doc", "docx", "odt", "rtf", "txt", "md", "tex"},
+	"spreadsheet":  {"xls", "xlsx", "ods", "csv", "tsv"},
+	"presentation": {"ppt", "pptx", "odp"},
+	"ebook":        {"epub", "mobi", "azw", "azw3", "fb2", "djvu"},
+	"code":         {"go", "c", "h", "cpp", "hpp", "py", "sh", "js", "ts", "rs", "java", "rb", "pl", "lua", "html", "css", "json", "yaml", "yml", "toml", "xml", "sql"},
+	"text":         {"txt", "md", "log", "csv", "tsv", "json", "yaml", "yml", "toml", "xml", "ini", "conf"},
+	"package":      {"deb", "rpm", "apk", "appimage", "exe", "msi", "flatpak", "snap"},
+	"font":         {"ttf", "otf", "woff", "woff2"},
+}