path: root/internal/cond/eval.go

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

package cond

import (
	"fmt"
	"io"
	"strings"
	"time"

	"git.labunix.xyz/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
	// ContentContains reports the index of the first of keywords, each
	// normalised under opt with norm.Text, that the file's text contains, or
	// -1 when it contains none.
	ContentContains(opt Options, keywords []string) (int, error)
	Duplicate(dirs []string) (original string, ok bool, err error)
	// Matched reports whether an earlier rule matched this file, and whether
	// an earlier rule could not be decided (its condition was unknown): with
	// no match and an undecided rule, (matched) is unknown.
	Matched() (matched, undecided bool)
	// Folded is norm.FoldMapped(subj), memoised per file. Folding is the
	// expensive half of a name test on a name with diacritics, and the
	// same name is folded again by every name test of every rule; the
	// implementation holds one file at a time, so a small memo there
	// removes the repetition entirely.
	Folded(subj string) norm.Folded
}

// 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`

	// Unreadable is true when the condition's value is unknown: it depends
	// on a content test that could not read the file. Match is then false;
	// an exclude holds anyway. A condition decided whatever the text holds
	// - (and (content "x") (type txt)) on a pdf - is not unknown.
	Unreadable bool
	// Undecided says what made the value unknown: "content unreadable",
	// "duplicate check failed", or both, comma-separated.
	Undecided string
}

// Trace is the full evaluation of every node, for krino explain.
type Trace struct {
	Label    string
	Value    bool
	Unknown  bool // the value depends on a content test that could not read the file
	Err      string
	Children []*Trace
}

// tri is a three-valued truth value: a content test that cannot read its
// file is unknown, and and/or/not follow Kleene's logic, so an unknown only
// spreads where the text could change the answer.
type tri int8

const (
	no tri = iota
	yes
	unknown
)

// 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
	// unknownContent and unknownDup record which kinds of test came back
	// unknown, for Result.Undecided.
	unknownContent, unknownDup bool
}

// undecidedLabel names the kinds of test that came back unknown.
func (ctx *evalCtx) undecidedLabel() string {
	switch {
	case ctx.unknownContent && ctx.unknownDup:
		return "content unreadable, duplicate check failed"
	case ctx.unknownDup:
		return "duplicate check failed"
	case ctx.unknownContent:
		return "content unreadable"
	}
	return ""
}

// undecidable reports whether a leaf whose fact could not be read is
// unknown rather than false: a content test or a duplicate test.
func undecidable(k kind) bool {
	return k == kContent || k == kDuplicate
}

// 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{}
	v, reasons := c.eval(c.root, f, ctx, false)
	r := Result{Match: v == yes, Captures: ctx.captures, Reasons: reasons, Warnings: ctx.warnings, Unreadable: v == unknown}
	if r.Unreadable {
		r.Undecided = ctx.undecidedLabel()
	}
	return r
}

// 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) (tri, []string) {
	switch n.kind {
	case kAnd:
		// A false child decides; an unknown one does not, so the rest still
		// run (one of them may be false).
		var reasons []string
		v := yes
		for _, ch := range n.children {
			cv, r := c.eval(ch, f, ctx, negated)
			switch cv {
			case no:
				return no, nil
			case unknown:
				v = unknown
			}
			reasons = append(reasons, r...)
		}
		if v == unknown {
			return unknown, nil
		}
		return yes, reasons
	case kOr:
		v := no
		for _, ch := range n.children {
			cv, r := c.eval(ch, f, ctx, negated)
			switch cv {
			case yes:
				return yes, r
			case unknown:
				v = unknown
			}
		}
		return v, nil
	case kNot:
		child := n.children[0]
		switch cv, _ := c.eval(child, f, ctx, !negated); cv {
		case yes:
			return no, nil
		case unknown:
			return unknown, 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 yes, []string{"not " + label}
	default:
		if m, undecided := f.Matched(); n.kind == kMatched && !m && undecided {
			return unknown, nil
		}
		ok, reason, warn, caps := c.evalLeaf(n, f)
		ctx.warn(warn)
		if warn != "" && undecidable(n.kind) {
			if n.kind == kContent {
				ctx.unknownContent = true
			} else {
				ctx.unknownDup = true
			}
			return unknown, nil
		}
		if !ok {
			return no, nil
		}
		if caps != nil && !negated && ctx.captures == nil {
			ctx.captures = caps
		}
		return yes, []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"
		}
		if n.kind == kPath {
			subj = norm.Name(subj, c.opt.Fold)
			for _, p := range n.patterns {
				if p.re.MatchString(subj) {
					return true, word + ` "` + p.src + `"`, "", nil
				}
			}
			return false, "", "", nil
		}
		// A name test matches the folded name, but its captures are read
		// back from the original, so {1} keeps the name's diacritics.
		folded := norm.Folded{Text: subj}
		if c.opt.Fold {
			folded = f.Folded(subj)
		}
		for _, p := range n.patterns {
			loc := p.re.FindStringSubmatchIndex(folded.Text)
			if loc == nil {
				continue
			}
			caps := make([]string, len(loc)/2)
			for g := range caps {
				if loc[2*g] >= 0 {
					caps[g] = folded.Source(loc[2*g], loc[2*g+1])
				}
			}
			return true, word + ` "` + p.src + `"`, "", caps
		}
		return false, "", "", nil

	case kContent:
		norms := make([]string, len(n.keywords))
		for i, kw := range n.keywords {
			norms[i] = kw.norm
		}
		i, err := f.ContentContains(c.opt, norms)
		if err != nil {
			return false, "", "content unreadable: " + err.Error(), nil
		}
		if i >= 0 {
			return true, `content "` + n.keywords[i].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 m, _ := f.Matched(); m {
			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}
		// Kleene: and is false on any false child, or on any true one.
		decide, other := no, yes
		if n.kind == kOr {
			decide, other = yes, no
		}
		v := other
		for _, ch := range n.children {
			ct := c.explain(ch, f)
			t.Children = append(t.Children, ct)
			switch cv := ct.tri(); {
			case cv == decide:
				v = decide
			case cv == unknown && v != decide:
				v = unknown
			}
		}
		t.set(v)
		return t
	case kNot:
		ct := c.explain(n.children[0], f)
		t := &Trace{Label: n.label, Children: []*Trace{ct}}
		switch ct.tri() {
		case yes:
			t.set(no)
		case no:
			t.set(yes)
		default:
			t.set(unknown)
		}
		return t
	default:
		ok, _, warn, _ := c.evalLeaf(n, f)
		t := &Trace{Label: n.label, Value: ok, Err: warn}
		if m, undecided := f.Matched(); (warn != "" && undecidable(n.kind)) || (n.kind == kMatched && !m && undecided) {
			t.set(unknown)
		}
		return t
	}
}

func (t *Trace) tri() tri {
	switch {
	case t.Unknown:
		return unknown
	case t.Value:
		return yes
	}
	return no
}

func (t *Trace) set(v tri) {
	t.Value, t.Unknown = v == yes, v == unknown
}

// Format writes one line per node: "yes", "no" or "?" (unknown) 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"
	switch {
	case t.Unknown:
		word = "?"
	case 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)
	}
}