Source File
	compile.go

Belonging Package
	github.com/freeeve/gochickpeas/gql/internal/compile

// Expr -> CExpr lowering: hot leaves (slots, property reads) carry
// resolved indices/readers; correlated subqueries gain a result memo keyed
// on their outer reads; scalar functions with constant arguments fold at
// compile time; the remaining rarely-hot nodes fall back to the
// interpreter.
package compile

import (
	"maps"

	chickpeas "github.com/freeeve/gochickpeas"
	"github.com/freeeve/gochickpeas/flatset"
	"github.com/freeeve/gochickpeas/gql/internal/ast"
	"github.com/freeeve/gochickpeas/gql/internal/eval"
	"github.com/freeeve/gochickpeas/gql/value"
)

// Compiled is a compiled expression bound to a snapshot; it satisfies the
// executor's RowEval seam. fast, when derivable, is the whole-expression
// monomorphic form (rowfast.go), result-identical to the tree.
type Compiled struct {
	c    cnode
	g    *chickpeas.Snapshot
	fast rowFast
}

// newCompiled binds a lowered tree, deriving the monomorphic fast form
// when the root shape supports it. Every construction site (initial
// lowering and the hoisting rewrites) routes through here so the fast
// form always reflects the final tree.
func newCompiled(c cnode, g *chickpeas.Snapshot) *Compiled {
	return &Compiled{c: c, g: g, fast: deriveRowFast(c, g)}
}

// Eval evaluates the compiled expression against a row -- identical in
// result to the interpreter on the source expression.
func (c *Compiled) Eval(ctx *eval.Ctx, row []value.Value, slots map[string]int) value.Value {
	if c.fast != nil {
		return c.fast(ctx, row, slots)
	}
	return ceval(ctx, c.c, c.g, row, slots)
}

// cnode is one compiled node.
type cnode interface{ isC() }

type cLit struct{ v value.Value }
type cSlot struct{ s int }
type cProp struct {
	slot   int
	reader propReader
}
type cNot struct{ e cnode }
type cNeg struct{ e cnode }
type cBin struct {
	op   ast.BinOp
	l, r cnode
}
type cList struct{ xs []cnode }
type cIn struct{ e, list cnode }

// cInConst is IN over a batch-constant list, lowered once to a prebuilt
// membership index.
type cInConst struct {
	e cnode
	m inMembership
}

// cInCarried is IN over a loop-invariant (carried, not batch-constant)
// list: the membership index rebuilds once per match-call epoch and is
// reused across that call's candidates. lastList short-circuits the
// rebuild entirely when the epoch's list is payload-identical to the
// previous one (a segment-stable slot).
type cInCarried struct {
	e, list  cnode
	epoch    uint64
	built    bool
	notList  bool
	m        inMembership
	lastList value.Value
}

type cIsNull struct {
	e       cnode
	negated bool
}

// cSubquery is a correlated EXISTS/COUNT with a result memo keyed on the
// outer slots it reads; memoSlots nil disables the memo (a nested
// subquery's dependencies can't be enumerated).
type cSubquery struct {
	pattern   *ast.Pattern
	where     ast.Expr
	isCount   bool
	memoSlots []int
	hasMemo   bool
	memo      map[string]int
	// memoI is the entity-id fast-path memo: when every correlated slot
	// holds a node id (<=2 of them), the key packs into a uint64. A flat
	// open-addressed table -- one backing-array doubling amortizes the fill
	// -- rather than a built-in map, whose per-insert bucket/overflow growth
	// dominated the correlated-subquery allocation profile (SPB a14). Both
	// memos are lazy; a subquery uses whichever its correlated slots select.
	memoI flatset.U64Map
	// key is the reusable memo-key buffer: lookups probe string(key)
	// without allocating; only a miss's insert converts.
	key []byte
	// decor holds the decorrelation plan for a COUNT{} over a linear chain
	// with BOTH endpoints bound to outer variables (task 084): instead of a
	// DFS per outer row, evaluate the subquery ONCE per distinct anchor value
	// (grouped by the other endpoint) and answer each row with an O(1) map
	// read. decorOK is set at compile time; the remaining fields are
	// per-execution scratch (the compiled tree is rebuilt each run, so their
	// zero values reset correctly). Nil pattern/absent decorOK leaves the
	// existing memo/DFS path untouched.
	decorOK                      bool
	decorStartVar, decorEndVar   string
	decorStartSlot, decorEndSlot int
	// decorAnchorDecided pins which endpoint anchors the single scan (the
	// hubbier end, decided once by typed first-hop degree); correctness is
	// anchor-independent, only speed depends on it.
	decorAnchorDecided bool
	decorAnchorIsEnd   bool
	// decorCanon is the node's canonical table identity (decor_canon.go),
	// computed once after the anchor role is decided; tables live on the
	// Ctx keyed by (canon, anchor node) so sibling subqueries share them.
	// decorBuilds counts the builds THIS node triggered (asserted in
	// tests: a shared anchor builds ONCE; a sibling hitting another
	// node's table builds ZERO). decorOff falls back to the DFS path once
	// too many builds prove the anchor is not amortizing.
	decorCanon     string
	decorCanonDone bool
	decorBuilds    int
	decorOff       bool
	// One-entry anchor cache in front of the shared store: consecutive
	// rows overwhelmingly share their anchor (a seeked hub never changes
	// across a segment), and the shared store's key hashes the canonical
	// identity string -- the cache answers those rows with one integer
	// compare. decorProbes counts shared-store consultations (asserted in
	// tests: a constant anchor probes once, not once per row). Sound
	// per-node: the canon is fixed once decided, so the anchor id alone
	// determines the table.
	decorLastAnchor uint32
	decorLastTbl    map[chickpeas.NodeID]int
	decorProbes     int
}

// decorAnchorCap bounds the distinct anchor tables built before decorrelation
// concedes the anchor is high-cardinality (not amortizing) and falls back to
// the per-row path. Bounds worst-case wasted builds; correctness holds either
// way.
const decorAnchorCap = 64

type cCase struct {
	operand cnode
	whens   [][2]cnode
	els     cnode
}
type cFunc struct {
	op   eval.FuncOp
	args []cnode
	// argv is the reused per-eval argument row. Safe because a compiled
	// tree is built per execution (compile.New takes the live Ctx), a node
	// cannot be its own descendant, and no ApplyFunc arm retains the argv
	// slice -- arms read elements by value or build fresh outputs.
	argv []value.Value
}

// cCmpPropConst fuses <prop> <comparison> <constant> -- the dominant
// filter shape -- into one node: the hoisted column read and the shared
// value.Compare run with no child dispatch. rev marks a constant left
// operand. Semantics are identical to the unfused cBin: same reader,
// same Compare coercions, same three-valued collapse.
type cCmpPropConst struct {
	prop *cProp
	c    value.Value
	op   ast.BinOp
	rev  bool
}

// cSlow defers to the interpreter (unrecognized functions, list
// machinery, map forms, label predicates, cost).
type cSlow struct{ e ast.Expr }

func (*cLit) isC()          {}
func (*cSlot) isC()         {}
func (*cProp) isC()         {}
func (*cCmpPropConst) isC() {}
func (*cNot) isC()          {}
func (*cNeg) isC()          {}
func (*cBin) isC()          {}
func (*cList) isC()         {}
func (*cIn) isC()           {}
func (*cInConst) isC()      {}
func (*cInCarried) isC()    {}
func (*cIsNull) isC()       {}
func (*cSubquery) isC()     {}
func (*cCase) isC()         {}
func (*cFunc) isC()         {}
func (*cSlow) isC()         {}

// New compiles e against the segment's slots and snapshot. Parameters
// resolve at compile time (their values are constant for the execution).
func New(ctx *eval.Ctx, e ast.Expr, slots map[string]int, g *chickpeas.Snapshot) *Compiled {
	return newCompiled(comp(ctx, e, slots, g), g)
}

// ConstValue reports the expression's compile-time constant value: the
// bottom-up literal folding is the one authority on constness (a slot or
// property read never folds), so ok=false exactly when evaluation could
// depend on a row. slots must be the caller's real slot map -- with an
// empty map an unbound name folds to a null LITERAL, which would launder
// row-dependent expressions (coalesce(m.ts, d) folds to d) into
// constants.
func ConstValue(ctx *eval.Ctx, e ast.Expr, slots map[string]int, g *chickpeas.Snapshot) (value.Value, bool) {
	if lit, ok := comp(ctx, e, slots, g).(*cLit); ok {
		return lit.v, true
	}
	return value.Value{}, false
}

func comp(ctx *eval.Ctx, e ast.Expr, slots map[string]int, g *chickpeas.Snapshot) cnode {
	switch n := e.(type) {
	case *ast.Lit:
		return &cLit{v: eval.LitValue(ctx, n.Value)}
	case *ast.Var:
		if s, ok := slots[n.Name]; ok {
			return &cSlot{s: s}
		}
		return &cLit{v: value.Null()}
	case *ast.Prop:
		if s, ok := slots[n.Var]; ok {
			return &cProp{slot: s, reader: newPropReader(g, n.Key)}
		}
		return &cLit{v: value.Null()}
	case *ast.Unary:
		c := comp(ctx, n.Expr, slots, g)
		var built cnode
		if n.Op == ast.Not {
			built = &cNot{e: c}
		} else {
			built = &cNeg{e: c}
		}
		return foldLits(ctx, built, g, c)
	case *ast.Binary:
		l, r := comp(ctx, n.LHS, slots, g), comp(ctx, n.RHS, slots, g)
		built := foldLits(ctx, &cBin{op: n.Op, l: l, r: r}, g, l, r)
		if fused := fuseCmpPropConst(n.Op, built, l, r); fused != nil {
			return fused
		}
		return built
	case *ast.ListExpr:
		xs := make([]cnode, len(n.Elems))
		for i, el := range n.Elems {
			xs[i] = comp(ctx, el, slots, g)
		}
		return foldLits(ctx, &cList{xs: xs}, g, xs...)
	case *ast.In:
		e2, list := comp(ctx, n.Expr, slots, g), comp(ctx, n.List, slots, g)
		return foldLits(ctx, &cIn{e: e2, list: list}, g, e2, list)
	case *ast.IsNull:
		c := comp(ctx, n.Expr, slots, g)
		return foldLits(ctx, &cIsNull{e: c, negated: n.Negated}, g, c)
	case *ast.Exists:
		ms, ok := correlatedSlots(n.Pattern, n.Where, slots)
		// A single fixed hop with both endpoints outer-bound and no WHERE
		// answers in near-constant time (a bound-pair relationship count
		// off the edge-key sets), so memoizing it costs more than it
		// saves: the memo map for a large outer row set dwarfs every
		// other execution allocation while each hit barely beats the
		// probe it caches.
		cheap := cheapExistsProbe(n.Pattern, n.Where, slots)
		if ok && cheap {
			ok = false
		}
		cs := &cSubquery{pattern: n.Pattern, where: n.Where, memoSlots: ms, hasMemo: ok, memo: map[string]int{}}
		// EXISTS decorrelates exactly like COUNT (the table answers >0):
		// an existential filter over a (bound, bound) multi-hop pattern
		// otherwise walks the inner pattern once per candidate row. The
		// near-constant bound-pair probe keeps its direct path.
		if !cheap {
			setupDecor(cs, n.Pattern, n.Where, slots)
		}
		return cs
	case *ast.CountSub:
		ms, ok := correlatedSlots(n.Pattern, n.Where, slots)
		cs := &cSubquery{pattern: n.Pattern, where: n.Where, isCount: true, memoSlots: ms, hasMemo: ok, memo: map[string]int{}}
		setupDecor(cs, n.Pattern, n.Where, slots)
		return cs
	case *ast.Case:
		c := &cCase{whens: make([][2]cnode, len(n.Whens))}
		if n.Operand != nil {
			c.operand = comp(ctx, n.Operand, slots, g)
		}
		for i, w := range n.Whens {
			c.whens[i] = [2]cnode{comp(ctx, w.Cond, slots, g), comp(ctx, w.Result, slots, g)}
		}
		if n.Else != nil {
			c.els = comp(ctx, n.Else, slots, g)
		}
		return c
	case *ast.Func:
		// A recognized scalar function with positional args compiles (and
		// constant-folds); DISTINCT/star forms and unknown names stay
		// interpreted.
		if op, ok := eval.ResolveFuncOp(n.Name); ok && !n.Distinct && !n.Star {
			args := make([]cnode, len(n.Args))
			for i, a := range n.Args {
				args[i] = comp(ctx, a, slots, g)
			}
			return foldFunc(op, args)
		}
		return &cSlow{e: e}
	default:
		// Cost (kernel dispatch lands with M17), list predicates,
		// comprehensions, reduce, index/slice, property-of-expression,
		// map forms, label predicates: interpreter-backed -- but a
		// row-independent subtree still folds to its literal (the dominant
		// win is a constant map argument to a temporal constructor in a
		// hot filter, e.g. duration({hours: 4}), which otherwise
		// rebuilds map + value per row).
		if constExpr(e, nil) {
			return &cLit{v: eval.Eval(ctx, e, nil, nil)}
		}
		return &cSlow{e: e}
	}
}

// fuseCmpPropConst collapses <prop> <comparison> <constant> (either
// operand order) into a cCmpPropConst when the binary did not already
// fold to a literal; nil when the shape doesn't apply.
func fuseCmpPropConst(op ast.BinOp, built, l, r cnode) cnode {
	switch op {
	case ast.OpEq, ast.OpNeq, ast.OpLt, ast.OpLte, ast.OpGt, ast.OpGte:
	default:
		return nil
	}
	if _, folded := built.(*cLit); folded {
		return nil
	}
	if p, ok := l.(*cProp); ok {
		if c, isLit := r.(*cLit); isLit {
			return &cCmpPropConst{prop: p, c: c.v, op: op}
		}
	}
	if p, ok := r.(*cProp); ok {
		if c, isLit := l.(*cLit); isLit {
			return &cCmpPropConst{prop: p, c: c.v, op: op, rev: true}
		}
	}
	return nil
}

// foldLits replaces built with its evaluated literal when every input is
// already a literal -- the cnode ops are pure, so one ceval with no row is
// result-identical to per-row evaluation. Folding composes bottom-up
// through comp, so nested constant expressions collapse to one cLit.
func foldLits(ctx *eval.Ctx, built cnode, g *chickpeas.Snapshot, inputs ...cnode) cnode {
	for _, in := range inputs {
		if _, ok := in.(*cLit); !ok {
			return built
		}
	}
	return &cLit{v: ceval(ctx, built, g, nil, nil)}
}

// constExpr reports whether e reads nothing from the row or graph -- no
// free variable (iteration variables bound by an enclosing list scope
// pass), no property access, no subquery, pattern, path, or label form --
// so it evaluates identically for every row. Parameters count as constant:
// New resolves them at compile time, once per execution. Scalar functions
// are all deterministic; startNode/endNode sit outside ResolveFuncOp and
// so fail the resolution check.
func constExpr(e ast.Expr, bound map[string]bool) bool {
	switch n := e.(type) {
	case *ast.Lit:
		return true
	case *ast.Var:
		return bound[n.Name]
	case *ast.Unary:
		return constExpr(n.Expr, bound)
	case *ast.Binary:
		return constExpr(n.LHS, bound) && constExpr(n.RHS, bound)
	case *ast.ListExpr:
		for _, el := range n.Elems {
			if !constExpr(el, bound) {
				return false
			}
		}
		return true
	case *ast.MapLit:
		for _, f := range n.Fields {
			if !constExpr(f.Val, bound) {
				return false
			}
		}
		return true
	case *ast.In:
		return constExpr(n.Expr, bound) && constExpr(n.List, bound)
	case *ast.IsNull:
		return constExpr(n.Expr, bound)
	case *ast.Index:
		return constExpr(n.Base, bound) && constExpr(n.Idx, bound)
	case *ast.Slice:
		return constExpr(n.Base, bound) &&
			(n.From == nil || constExpr(n.From, bound)) &&
			(n.To == nil || constExpr(n.To, bound))
	case *ast.PropOf:
		return constExpr(n.Base, bound)
	case *ast.Case:
		if n.Operand != nil && !constExpr(n.Operand, bound) {
			return false
		}
		for _, w := range n.Whens {
			if !constExpr(w.Cond, bound) || !constExpr(w.Result, bound) {
				return false
			}
		}
		return n.Else == nil || constExpr(n.Else, bound)
	case *ast.Func:
		if n.Distinct || n.Star {
			return false
		}
		if _, ok := eval.ResolveFuncOp(n.Name); !ok {
			return false
		}
		for _, a := range n.Args {
			if !constExpr(a, bound) {
				return false
			}
		}
		return true
	case *ast.ListPred:
		return constExpr(n.List, bound) && constExpr(n.Pred, boundWith(bound, n.Var))
	case *ast.Reduce:
		return constExpr(n.List, bound) && constExpr(n.Init, bound) &&
			constExpr(n.Body, boundWith(bound, n.Acc, n.Var))
	case *ast.ListComp:
		if !constExpr(n.List, bound) {
			return false
		}
		inner := boundWith(bound, n.Var)
		return (n.Filter == nil || constExpr(n.Filter, inner)) &&
			(n.Map == nil || constExpr(n.Map, inner))
	default:
		return false
	}
}

// boundWith extends a bound-variable set with list-scope iteration names.
func boundWith(bound map[string]bool, vars ...string) map[string]bool {
	out := make(map[string]bool, len(bound)+len(vars))
	maps.Copy(out, bound)
	for _, v := range vars {
		out[v] = true
	}
	return out
}

// foldFunc constant-folds a scalar function whose arguments are all
// compile-time constants -- every FuncOp is deterministic, so this is
// result-identical to per-row evaluation (the dominant win is a temporal
// constructor in a hot filter parsing its ISO string once).
// foldFunc evaluates a scalar function at plan time when every argument is a
// literal, so a hot filter's constant call (e.g. duration({hours: 4})) is one
// value instead of a per-row rebuild. A ZERO-arg call folds vacuously (the
// loop below is empty) -- sound only because every scalar function here is
// deterministic: the only zero-arg forms, date()/datetime()/localdatetime(),
// return Null, not the current instant. A volatile function (rand/timestamp)
// must NOT reach this fold -- its plan-time value would be baked into the
// cached plan and replayed forever -- so it would need excluding here and at
// constExpr both (the two fold sites). Locked by the gql package's zero-arg
// fold tests.
func foldFunc(op eval.FuncOp, args []cnode) cnode {
	argv := make([]value.Value, len(args))
	for i, a := range args {
		lit, ok := a.(*cLit)
		if !ok {
			return &cFunc{op: op, args: args}
		}
		argv[i] = lit.v
	}
	return &cLit{v: eval.ApplyFunc(op, argv)}
}

The pages are generated with Golds v0.8.7. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds.