path: root/internal/engine/match.go

// SPDX-License-Identifier: GPL-3.0-or-later

package engine

import (
	"context"
	"fmt"
	"io/fs"
	"os"
	"path/filepath"
	"runtime"
	"slices"
	"sort"
	"strings"
	"sync"
	"time"

	"krino/internal/cond"
	"krino/internal/config"
	"krino/internal/kwcache"
	"krino/internal/norm"
	"krino/internal/plan"
	"krino/internal/scan"
	"krino/internal/xdg"
)

// RuleMatch is one rule that matched a file, and why.
type RuleMatch struct {
	Rule     *Rule
	Captures []string
	Reasons  []string
}

// FileMatch is one file and the rules that did, or did not, match it.
type FileMatch struct {
	File     scan.File
	Rules    []RuleMatch // matching rules in order, ending at the first with (stop)
	Warnings []string    // "<rule>: <warning>", e.g. "acme: content unreadable: needs pdftotext, not installed"

	// Excluded is the (exclude ...) form that set this file aside before any
	// rule ran, as written; "" when none did. An excluded file has no Rules.
	Excluded string

	// NoDelete is non-empty when no delete step may run for this file (spec
	// §5.5 rule 2), and says why: the file is a duplicate under a scope its
	// directory's rules use, or that check failed. Only set for a file some
	// matching rule would delete.
	NoDelete string

	// DuplicateOf is the file a (duplicate) test matched this one against,
	// absolute; "" when none did. The reason text says the same thing the
	// way it reads best - relative to the directory when it is inside it -
	// which leaves a front end no way to act on the other copy, or even to
	// say where it is (his report, 2026-09-17).
	DuplicateOf string
}

// Result is everything Match found in one directory.
type Result struct {
	Dir       *Dir
	Matched   []FileMatch // at least one rule matched; sorted by File.Rel
	Unmatched []FileMatch // no rule matched (Warnings may say why); sorted by File.Rel
	Skipped   []scan.Skipped
	Warnings  []string // directory-level, sorted; e.g. "duplicate: /x/y does not exist"
	// Unscanned is every existing rule destination inside the root, which
	// the walk leaves out (spec §8.1), so -v can say its files were not
	// counted (triage 4).
	Unscanned []string
	Elapsed   time.Duration
}

// Match walks d's root and evaluates every rule against every file found,
// concurrently. Output order never depends on scheduling: results are
// placed by index into a slice the size of the walk, then split into
// Matched and Unmatched keeping that (Rel-sorted) order.
func (e *Engine) Match(ctx context.Context, d *Dir) (*Result, error) {
	started := time.Now()
	now := e.Now()
	excl := e.excludeDirs(d)

	wres, err := scan.Walk(d.Root, walkOptions(d, excl, now))
	if err != nil {
		return nil, err
	}

	run := newMatchRun(e, d, ctx, now, wres.Files)
	cacheWarn := e.openCache(run)
	fileMatches := make([]FileMatch, len(wres.Files))

	workers := runtime.GOMAXPROCS(0)
	if workers < 1 {
		workers = 1
	}
	var wg sync.WaitGroup
	jobs := make(chan int)
	for w := 0; w < workers; w++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := range jobs {
				fileMatches[i] = evalFile(run, wres.Files[i])
			}
		}()
	}
	for i := range wres.Files {
		jobs <- i
	}
	close(jobs)
	wg.Wait()
	run.drainDupErrors()

	var matched, unmatched []FileMatch
	for _, fm := range fileMatches {
		if len(fm.Rules) > 0 || fm.Excluded != "" {
			matched = append(matched, fm)
		} else {
			unmatched = append(unmatched, fm)
		}
	}

	warnings := append(run.warnings(), cacheWarn...)
	if run.cache != nil {
		ids := make([]kwcache.ID, 0, len(wres.Files))
		for _, f := range wres.Files {
			if f.Ino != 0 {
				ids = append(ids, fileCacheID(f))
			}
		}
		keys := make([]string, len(d.ContentKeywords))
		for i, k := range d.ContentKeywords {
			keys[i] = k.Key()
		}
		if err := run.cache.Save(e.cacheFile(d), ids, keys); err != nil {
			warnings = append(warnings, "cache: "+err.Error())
		}
	}
	sort.Strings(warnings)

	var unscanned []string
	for _, dir := range e.destinationDirs(d) {
		if fi, err := os.Stat(dir); err == nil && fi.IsDir() && !slices.Contains(unscanned, dir) {
			unscanned = append(unscanned, dir)
		}
	}

	return &Result{
		Dir:       d,
		Matched:   matched,
		Unmatched: unmatched,
		Skipped:   wres.Skipped,
		Warnings:  warnings,
		Unscanned: unscanned,
		Elapsed:   time.Since(started),
	}, nil
}

// evalFile evaluates every rule of run.d, in order, against file: matched
// becomes true after the first matching rule, so a later (not (matched))
// test sees it, and evaluation stops right after a matching rule whose
// Stop is set.
func evalFile(run *matchRun, file scan.File) FileMatch {
	f := newFacts(run, file)
	fm := FileMatch{File: file}
	for _, x := range run.d.Excludes {
		res := x.Cond.Eval(f)
		for _, w := range res.Warnings {
			fm.Warnings = append(fm.Warnings, "exclude: "+w)
		}
		if excluded := excludedBy(x, res); excluded != "" {
			fm.Excluded = excluded
			return fm
		}
	}
	for _, r := range run.d.Rules {
		res := r.Cond.Eval(f)
		for _, w := range res.Warnings {
			fm.Warnings = append(fm.Warnings, r.Name+": "+w)
		}
		if res.Unreadable {
			f.undecided = true
			if r.Conf.Stop {
				// A (stop) rule that cannot be decided ends the search too:
				// it may be the rule written to keep this file from the
				// ones below (plan 12).
				break
			}
		}
		if !res.Match {
			continue
		}
		fm.Rules = append(fm.Rules, RuleMatch{Rule: r, Captures: res.Captures, Reasons: res.Reasons})
		f.matched = true
		if r.Conf.Stop {
			break
		}
	}
	if len(run.d.DupScopes) > 0 && deletes(fm.Rules) {
		fm.NoDelete = noDelete(f, run.d.DupScopes)
	}
	fm.DuplicateOf = f.DuplicateOriginal()
	return fm
}

// NeverDeleted is the reason a duplicate's delete step is skipped (spec
// §5.5).
const NeverDeleted = "a duplicate is never deleted"

// deletes reports whether any of rules has a delete action.
func deletes(rules []RuleMatch) bool {
	for _, rm := range rules {
		for _, a := range rm.Rule.Conf.Actions {
			if a.Kind == config.Delete || a.Kind == config.DeletePermanent {
				return true
			}
		}
	}
	return false
}

// noDelete looks f up under every scope, whether or not evaluating the
// rules reached that test (spec §5.5 rule 2), and returns why f must not be
// deleted, or "" when it may be. A failed lookup blocks the delete too:
// krino cannot show the file is not a duplicate, so it keeps it.
func noDelete(f *facts, scopes [][]string) string {
	for _, dirs := range scopes {
		_, dup, err := f.Duplicate(dirs)
		if err != nil {
			return "duplicate check failed, so not deleted: " + err.Error()
		}
		if dup {
			return NeverDeleted
		}
	}
	return ""
}

// RuleTrace is one rule's outcome in an Explain call.
type RuleTrace struct {
	Rule     *Rule
	Match    bool
	Captures []string    // of a matching rule, as its actions' {N} see them
	Trace    *cond.Trace // nil when not evaluated
	Stopped  string      // "stopped by rule acme" when an earlier (stop) ended the search
}

// ExcludeTrace is one (exclude ...) form's outcome in an Explain call.
type ExcludeTrace struct {
	Text  string
	Match bool
	Trace *cond.Trace
}

// Explanation is why (or why not) krino would act on one file.
type Explanation struct {
	Dir      *Dir
	File     scan.File
	Skip     string // why krino would not look at this file at all; "" when it would
	Excludes []ExcludeTrace
	Excluded string // the first exclude that matches, which sets the file aside; "" when none does
	Rules    []RuleTrace
	NoDelete string // why a delete from the matching rules would be skipped (spec §5.5); "" when it would not
	// Chain is what the matching rules would do to this file alone:
	// placeholders expanded and conflicts resolved against the disk, but
	// not against the other files of a plan, which can still take a name
	// this chain shows (the plan itself is where those are resolved). It is
	// nil unless ExplainWithChain asked for it, and nil for a file the scan
	// would skip or an exclude sets aside, which no rule acts on.
	Chain []plan.Step
}

// Explain reports, for one file, whether krino's ordinary scan would ever
// reach it and how every rule of its directory evaluates against it. Rules
// are traced in order even when Skip is set, so a user can see what would
// match if the file were looked at; a rule reached after an earlier
// matching (stop) is recorded as Stopped, with no trace.
func (e *Engine) Explain(ctx context.Context, path string) (*Explanation, error) {
	return e.explain(ctx, path, false)
}

// ExplainWithChain is Explain with Explanation.Chain filled in: the steps
// this file alone would get. Building them resolves conflicts against the
// disk, which can read files (a copy whose target holds the same bytes), so
// the command line's explain does not ask for it (plan 13 review F1).
func (e *Engine) ExplainWithChain(ctx context.Context, path string) (*Explanation, error) {
	return e.explain(ctx, path, true)
}

func (e *Engine) explain(ctx context.Context, path string, withChain bool) (*Explanation, error) {
	abs, err := filepath.Abs(path)
	if err != nil {
		return nil, err
	}
	abs = filepath.Clean(abs)

	d := e.dirFor(abs)
	if d == nil {
		return nil, fmt.Errorf("%s is not inside any included directory", path)
	}

	info, err := os.Lstat(abs)
	if err != nil {
		return nil, err
	}
	if info.Mode()&fs.ModeSymlink != 0 || !info.Mode().IsRegular() {
		return nil, fmt.Errorf("%s is not a regular file", path)
	}

	rel, err := filepath.Rel(d.Root, abs)
	if err != nil {
		return nil, err
	}
	rel = filepath.ToSlash(rel)

	sf := scan.NewFile(abs, rel, info)

	now := e.Now()
	excl := e.excludeDirs(d)
	skip := explainSkip(d, sf, excl, now)

	// The directory is walked only for a duplicate test - in a rule or in an
	// exclude - the one thing that needs its other files (triage 21, plan 11
	// review M3).
	files := []scan.File{sf}
	if len(d.DupScopes) > 0 || excludesUseDuplicate(d) {
		files = e.filesForExplain(d, sf, excl, now)
	}
	run := newMatchRun(e, d, ctx, now, files)
	if len(d.ContentKeywords) > 0 {
		// Loaded only: openCache would remove the cache of a directory with
		// no content tests, and Explain holds no lock (triage 28e).
		e.openCache(run)
	}
	f := newFacts(run, sf)

	var excludes []ExcludeTrace
	excluded := ""
	for _, x := range d.Excludes {
		trace := x.Cond.Explain(f)
		by := excludedBy(x, x.Cond.Eval(f))
		excludes = append(excludes, ExcludeTrace{Text: x.Text, Match: by != "", Trace: trace})
		if by != "" && excluded == "" {
			excluded = by
		}
	}

	var rules []RuleTrace
	var matched []RuleMatch
	stoppedBy := ""
	for _, r := range d.Rules {
		if stoppedBy != "" {
			rules = append(rules, RuleTrace{Rule: r, Stopped: "stopped by rule " + stoppedBy})
			continue
		}
		trace := r.Cond.Explain(f)
		match := trace.Value
		if trace.Unknown {
			f.undecided = true
			if r.Conf.Stop {
				rules = append(rules, RuleTrace{Rule: r, Trace: trace})
				stoppedBy = r.Name + ", which could not be decided"
				continue
			}
		}
		var caps []string
		if match {
			// Eval, on the same memoised facts and before matched becomes
			// true, is what gives the captures its actions would use.
			res := r.Cond.Eval(f)
			caps = res.Captures
			f.matched = true
			matched = append(matched, RuleMatch{Rule: r, Captures: caps, Reasons: res.Reasons})
		}
		rules = append(rules, RuleTrace{Rule: r, Match: match, Captures: caps, Trace: trace})
		if match && r.Conf.Stop {
			stoppedBy = r.Name
		}
	}
	noDel := ""
	if len(d.DupScopes) > 0 && deletes(matched) {
		noDel = noDelete(f, d.DupScopes)
	}

	var chain []plan.Step
	if withChain && skip == "" && excluded == "" && len(matched) > 0 {
		in := []plan.Input{{File: sf, Rules: planRules(matched), NoDelete: noDel}}
		if built := plan.Build(d.Root, in, now, plan.OS{}, plan.NewClaims()); len(built) == 1 {
			chain = built[0].Steps
		}
	}

	return &Explanation{Dir: d, File: sf, Skip: skip, Excludes: excludes, Excluded: excluded, Rules: rules, NoDelete: noDel, Chain: chain}, nil
}

// excludesUseDuplicate reports whether any of d's excludes has a
// (duplicate) test.
func excludesUseDuplicate(d *Dir) bool {
	for _, x := range d.Excludes {
		if len(x.Cond.DupDirs) > 0 {
			return true
		}
	}
	return false
}

// cacheFingerprint identifies what a cached keyword answer of d depends on
// besides the file: the extractor (its version and tools), normalisation
// and its Unicode tables, the Go release, and d's max-read, which caps what
// is read. A cache written under any other is discarded.
func (e *Engine) cacheFingerprint(d *Dir) string {
	return fmt.Sprintf("%s %s %s max-read=%d", e.Extract.Fingerprint(), norm.Fingerprint(), runtime.Version(), d.Settings.MaxRead)
}

// excludedBy is what x sets a file aside as, given its evaluation: its text
// when it matched, its text marked "(content unreadable)" when a content
// test it reached could not read the file - an exclude protects files, so
// it fails closed (review M11) - or "" when it does not hold.
func excludedBy(x *Exclude, res cond.Result) string {
	switch {
	case res.Match:
		return x.Text
	case res.Unreadable:
		return x.Text + " (" + res.Undecided + ")"
	}
	return ""
}

// cacheFile is d's keyword cache file.
func (e *Engine) cacheFile(d *Dir) string {
	return filepath.Join(e.CacheDir, d.Name+".cache")
}

// openCache loads run's directory keyword cache into run.cache, when the
// engine has a CacheDir and the directory has content tests at all. A cache
// that cannot be read is replaced by an empty one, reported as a warning.
func (e *Engine) openCache(run *matchRun) []string {
	if e.CacheDir == "" {
		return nil
	}
	if len(run.d.ContentKeywords) == 0 {
		// No content test left: a cache from an earlier configuration only
		// holds keywords this directory no longer uses (review cache F6).
		if err := os.Remove(e.cacheFile(run.d)); err != nil && !os.IsNotExist(err) {
			return []string{"cache: " + err.Error()}
		}
		return nil
	}
	c, err := kwcache.Load(e.cacheFile(run.d), e.cacheFingerprint(run.d))
	run.cache = c
	if err != nil {
		return []string{"cache: " + err.Error() + " (starting a new one)"}
	}
	return nil
}

// filesForExplain returns the file set Explain's duplicate checks run
// against: the directory's ordinary scan, plus the explained file itself
// when that scan would not have reached it (it is busy, ignored, too new,
// excluded, or beyond recursive/max-depth) - so (duplicate ...) always has
// a real answer for the file being explained, and sees the same siblings
// Match would.
func (e *Engine) filesForExplain(d *Dir, sf scan.File, excl []string, now time.Time) []scan.File {
	wres, err := scan.Walk(d.Root, walkOptions(d, excl, now))
	if err != nil {
		return []scan.File{sf}
	}
	for _, wf := range wres.Files {
		if wf.Path == sf.Path {
			return wres.Files
		}
	}
	return append(append([]scan.File{}, wres.Files...), sf)
}

// walkOptions builds the scan.Options both Match and Explain's
// filesForExplain walk d's root with, so the two never drift apart.
func walkOptions(d *Dir, excl []string, now time.Time) scan.Options {
	return scan.Options{
		Recursive: d.Settings.Recursive,
		MaxDepth:  d.Settings.MaxDepth,
		Ignore:    d.Ignore,
		Exclude:   excl,
		Busy:      d.Settings.Busy,
		MinAge:    d.Settings.MinAge,
		MaxSize:   d.Settings.MaxSize,
		Now:       now,
	}
}

// dirFor returns the configured Dir whose root most specifically (longest
// root wins) contains abs, or nil if none does.
func (e *Engine) dirFor(abs string) *Dir {
	var best *Dir
	var bestRoot string
	for _, d := range e.Dirs {
		root := filepath.Clean(d.Root)
		if abs != root && !strings.HasPrefix(abs, root+string(filepath.Separator)) {
			continue
		}
		if best == nil || len(root) > len(bestRoot) {
			best, bestRoot = d, root
		}
	}
	return best
}

// explainSkip decides, in priority order, why krino's ordinary scan would
// not reach sf, or "" if it would.
func explainSkip(d *Dir, sf scan.File, excl []string, now time.Time) string {
	segs := strings.Split(sf.Rel, "/")
	if !d.Settings.Recursive && len(segs) > 1 {
		return "in a subdirectory, and recursive is off"
	}
	if d.Settings.MaxDepth > 0 && len(segs) > d.Settings.MaxDepth {
		return "deeper than max-depth"
	}
	if insideAny(sf.Path, excl) {
		return "inside a rule destination, which krino never scans"
	}
	if d.Ignore != nil && d.Ignore.Match(sf.Rel, false) {
		return "ignored"
	}
	if isBusy(sf.Path, d.Settings.Busy) {
		return "busy"
	}
	if scan.Age(now, sf.ModTime) < d.Settings.MinAge {
		return "too new"
	}
	if d.Settings.MaxSize > 0 && sf.Size > d.Settings.MaxSize {
		return "too big"
	}
	return ""
}

// insideAny reports whether path is dir itself, or inside it, for any dir
// in dirs.
func insideAny(path string, dirs []string) bool {
	for _, dir := range dirs {
		if path == dir || strings.HasPrefix(path, dir+string(filepath.Separator)) {
			return true
		}
	}
	return false
}

// isBusy reports whether path has a sibling named path+suffix, for any
// configured busy suffix - the mark of an in-progress download.
func isBusy(path string, suffixes []string) bool {
	for _, suf := range suffixes {
		if _, err := os.Lstat(path + suf); err == nil {
			return true
		}
	}
	return false
}

// excludeDirs computes the directories Match and Explain never enter: each
// rule's copy/move destination, the Trash, and the directory holding the
// main config file - each kept only when it lies strictly inside d's root
// (C3: root itself is not "inside" it here - a rule cannot exclude the very
// directory being scanned. cmd/krino/render.go's relToRoot answers a
// different question, whether a destination is root or beneath it for
// display purposes, and there root does count as inside; the two are each
// correct for their own question, so do not "unify" them).
// A destination with no template placeholder excludes exactly that
// directory; a destination with a placeholder excludes only the static
// part before its first "{", cut back to a full path component (its last
// "/"), since anything from there on varies per file - spec 8.1: "Work/
// Acme/{mtime:%Y}" excludes "Work/Acme", and "Work/Acme-{mtime:%Y}"
// (the placeholder mid-segment) excludes "Work".
func (e *Engine) excludeDirs(d *Dir) []string {
	out := e.destinationDirs(d)
	root := filepath.Clean(d.Root)
	for _, p := range []string{filepath.Join(xdg.DataHome(), "Trash"), filepath.Dir(e.MainFile)} {
		if p = filepath.Clean(p); strings.HasPrefix(p, root+string(filepath.Separator)) {
			out = append(out, p)
		}
	}
	return out
}

// destinationDirs is the rule-destination half of excludeDirs: every
// copy/move destination's static directory strictly inside d's root.
func (e *Engine) destinationDirs(d *Dir) []string {
	root := filepath.Clean(d.Root)
	var out []string
	add := func(p string) {
		if p == "" {
			return
		}
		p = filepath.Clean(p)
		if strings.HasPrefix(p, root+string(filepath.Separator)) {
			out = append(out, p)
		}
	}
	for _, r := range d.Rules {
		for _, a := range r.Conf.Actions {
			if a.Kind != config.Copy && a.Kind != config.Move {
				continue
			}
			prefix, templated := plan.StaticPrefix(a.Arg)
			if templated {
				if idx2 := strings.LastIndexByte(prefix, '/'); idx2 >= 0 {
					prefix = prefix[:idx2]
				} else {
					// The very first path component is itself templated
					// (e.g. "{year}-Stuff"): nothing about the destination
					// is known statically, so there is nothing to exclude.
					prefix = ""
				}
			}
			add(plan.ResolveDir(prefix, root))
		}
	}
	return out
}