Documentation
¶
Overview ¶
Package vm compiles ClassAd expressions to a linear instruction stream and interprets them against a scope, replacing per-query AST walks.
Parity with the tree-walking evaluator is the overriding requirement: the interpreter routes every value operation through the exported hooks in the classad package (ApplyBinaryOp/ApplyUnaryOp/ResolveRef/ShortCircuit) and delegates any node type it does not natively compile back to the evaluator via an EvalNode instruction. It therefore cannot diverge from classad.Eval by construction; the differential fuzz test enforces this.
Index ¶
- func Run(p *Program, scope *classad.ClassAd) (result classad.Value)
- func SelfRefs(expr ast.Expr) []string
- func SelfRefsSafe(expr ast.Expr) (refs []string, partialSafe bool)
- type Instr
- type Matcher
- type Opcode
- type Probe
- type ProbeGroup
- type Program
- type Query
- func (q *Query) Eval(scope *classad.ClassAd) classad.Value
- func (q *Query) Expr() ast.Expr
- func (q *Query) Matcher() *Matcher
- func (q *Query) Matches(scope *classad.ClassAd) bool
- func (q *Query) Native() bool
- func (q *Query) ProbePlan() []ProbeGroup
- func (q *Query) Probes() []Probe
- func (q *Query) Program() *Program
- func (q *Query) ReadAttrs() []string
- func (q *Query) ReadPlan() ReadPlan
- type ReadPlan
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Run ¶
Run executes p against scope and returns the resulting Value. It produces the same value that classad evaluation of the source expression would: value operations are delegated to the classad evaluator hooks, and a cyclic reference resolves to an error value (as at the tree-walker's entry points).
Known limitation: for a self-referential cyclic lazy list (e.g. A = {a} where "a" case-folds to "A"), the value both engines produce is a list nested to the evaluator's depth limit terminating in an error element. The tree-walker folds the source expression's nesting depth into the list's captured depth, whereas this flat interpreter does not, so the two bottom out at slightly different nesting depths. Only such cyclic lists are affected; every non-cyclic expression is bit-identical to the tree-walker (enforced by FuzzDifferential).
func SelfRefs ¶
SelfRefs returns the self-scoped attribute names referenced directly by expr (unscoped or MY-scoped), for the store to expand the transitive read set as it decodes attribute expressions. It does not recurse into nested records.
func SelfRefsSafe ¶ added in v0.6.0
SelfRefsSafe is SelfRefs plus whether partial decode is sound for expr: partialSafe is false when expr calls eval(), whose referenced attributes cannot be determined statically, so a closure built from the static refs could miss one. A caller building a partial ad must fall back to a full decode when this is false.
Types ¶
type Instr ¶
Instr is one instruction: an opcode and a single integer argument whose meaning depends on the opcode (a pool index or an absolute jump target).
type Matcher ¶
type Matcher struct {
// contains filtered or unexported fields
}
Matcher evaluates one compiled Query against many ads while reusing its evaluator and value stack, so a table scan pays the per-ad cost of the ClassAd evaluation itself but not a fresh evaluator + stack allocation per ad. It is semantically identical to calling Query.Eval / Query.Matches for each ad; it only removes allocations.
A Matcher holds mutable state (the reused evaluator and stack) and is NOT safe for concurrent use. A parallel scan should use one Matcher per goroutine.
func (*Matcher) Eval ¶
Eval evaluates the query against scope and returns the raw Value, reusing the Matcher's evaluator and stack. The result equals Query.Eval(scope); a cyclic reference resolves to an error value.
func (*Matcher) EvalResolved ¶
func (m *Matcher) EvalResolved(resolver func(name string, scope ast.AttributeScope) classad.Value) (result classad.Value)
EvalResolved evaluates the query using a custom attribute resolver instead of a ClassAd scope, reusing the Matcher's evaluator and stack. resolver(name, scope) returns the value of an attribute reference; it lets the query run against an alternate backing (e.g. an encoded ad) with no ClassAd materialized.
The query must be Native. The result equals evaluating the same query against a ClassAd whose attributes return the same values; a cyclic reference resolves to an error value.
type Opcode ¶
type Opcode uint8
Opcode identifies an instruction. The program is a flat []Instr slice (a struct-of-op-and-arg IR); packing it to a dense byte stream is a future optimization that does not affect semantics.
const ( // OpPushConst pushes consts[A]. OpPushConst Opcode = iota // OpPushTrue/False/Undef/Error push the corresponding literal (no arg). OpPushTrue OpPushFalse OpPushUndef OpPushError // OpLoadRef resolves refs[A] (name+scope) in the scope and pushes the result. OpLoadRef // OpBinop pops right,left and pushes ApplyBinaryOp(ops[A], left, right). // Used for all non-short-circuiting binary operators. OpBinop // OpUnop pops v and pushes ApplyUnaryOp(ops[A], v). OpUnop // OpShortAnd/OpShortOr peek the left operand already on the stack. If it // short-circuits the logical operator, they replace it with the operator's // result and jump to A; otherwise they leave it on the stack and fall // through to the compiled right operand. OpShortAnd OpShortOr // OpCombineAnd/OpCombineOr pop right,left and push the combined logical value // (reached only when the right operand was evaluated). OpCombineAnd OpCombineOr // OpJmpIfNotUndef implements the Elvis operator: peek top; if it is NOT // undefined, jump to A leaving it on the stack (the result); otherwise pop it // and fall through to the compiled fallback expression. OpJmpIfNotUndef // OpEvalNode delegates nodes[A] (an ast.Expr subtree) to the tree-walking // evaluator and pushes its value. The escape hatch for node types the // compiler does not lower to native instructions. OpEvalNode )
type Probe ¶
Probe is an index-satisfiable constraint extracted from a query: a self-scoped attribute Attr related by Op to one or more literal values. Op is one of "==","!=","<","<=",">=",">" (a single Val), "in" (a set of Vals, from an OR-of-equalities), "is"/"isnt" (=?=/=!= exact identity), or "present"/"absent" (is/isnt undefined). A store matches Probes against its configured indexes to build a candidate set; because the store still re-verifies the full query, any Probe the planner omits only costs selectivity, never correctness.
func ProbeOf ¶ added in v0.6.0
ProbeOf returns the index probe a single (already slot-rewritten) expression yields, or ok=false if it is not a recognizable Attr-OP-literal / presence / OR-of-equalities. Callers use it to tell an already-probeable leaf from an opaque one (e.g. before finite-domain materialization).
type ProbeGroup ¶ added in v0.6.0
type ProbeGroup struct {
Probes []Probe
}
ProbeGroup is a conjunction of index probes -- a candidate matches the group when it satisfies ALL of them. An empty Probes means the group is unconstrained (that disjunct can match anything), so a plan containing one cannot prune.
type Program ¶
type Program struct {
// contains filtered or unexported fields
}
Program is a compiled expression: a flat instruction stream plus the constant pools its instructions index into.
func CompileProgram ¶
CompileProgram lowers a ClassAd expression to a Program. Node types with subtle scope/short-circuit/laziness semantics (conditional, list, record, function call, select, subscript) are emitted as OpEvalNode and delegated to the tree-walking evaluator at run time; the rest are native instructions.
type Query ¶
type Query struct {
// contains filtered or unexported fields
}
Query is a compiled boolean constraint over ads (a compiled Program plus the convenience of a match predicate). The store uses ReadAttrs for planning.
func Compile ¶
Compile compiles an already-parsed expression into a Query.
When the expression references the magic CurrentTime attribute, its constants are folded once here (FoldConstants resolves CurrentTime to the current time) so a single "now" is baked into both the program and its index probes -- the constraint prunes correctly and evaluates consistently, instead of the program re-reading the clock per ad. Expressions that do not reference CurrentTime are compiled unchanged.
func (*Query) Expr ¶ added in v0.6.0
Expr returns the source expression the query was compiled from (nil if empty).
func (*Query) Matcher ¶
Matcher returns a reusable Matcher for the query. Create one per scanning goroutine.
func (*Query) Matches ¶
Matches reports whether the query evaluates to boolean true against scope. Undefined, error, and non-boolean results are treated as non-matches, matching how a ClassAd requirement/constraint is applied.
func (*Query) Native ¶
Native reports whether the query compiled entirely to native instructions, with no delegated (OpEvalNode) subtrees. Only native queries can be evaluated with EvalResolved, because a delegated subtree needs a real ClassAd scope for its function/select/subscript/list semantics.
func (*Query) ProbePlan ¶ added in v0.6.0
func (q *Query) ProbePlan() []ProbeGroup
ProbePlan describes the query's index-satisfiable structure as a disjunction of conjunctive groups (DNF over the top-level `||` spine): a candidate satisfies the plan when it satisfies every probe of ANY group. A purely conjunctive query is a single group -- identical to Probes(). A disjunctive query like `(A && B) || C` yields one group per disjunct, which the planner executes as a union of intersections. Because each group is an over-approximation of its disjunct and the store re-verifies, the union is a sound candidate superset; a group with no probes makes the plan un-prunable (the caller then full-scans).
func (*Query) Probes ¶
Probes extracts the query's index-satisfiable conjuncts. It constant-folds the source expression (so `Memory > 2048*1024` normalizes), then flattens the top-level && spine and classifies each conjunct, pushing `!` into comparisons where that is identity under ClassAd three-valued logic. Conjuncts that are not a recognizable `Attr OP literal` (or OR-of-equalities on one attr) are omitted.
type ReadPlan ¶
type ReadPlan struct {
// Seeds are the distinct attribute names the query reads directly from the
// current ad — unscoped and MY-scoped references (TARGET references read the
// match target, which is absent during a collection scan). Resolving these
// may pull in further attributes they reference; the store expands the set
// transitively while decoding.
Seeds []string
// PartialSafe is true when the query contains no construct that reads an
// attribute whose name is not statically visible — specifically eval(), which
// parses a runtime string into an arbitrary expression. When false, a partial
// decode could miss an attribute, so the store must fully decode the ad.
PartialSafe bool
}
ReadPlan describes what a query reads from an ad, so a store can evaluate the query against a partially-decoded ad (only the needed attributes) instead of decoding every attribute of every ad.
Source Files