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 ¶
- Constants
- func MaskWords(n int) int
- func PopCountMasked(a, b []uint64) int
- func RawColumnUseful(width int, unsigned bool) bool
- 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 ColumnSource
- type DictResolver
- 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) ExactProbes() (probes []Probe, exact bool)
- 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
- func (q *Query) VecEval(src ColumnSource, n int, scratch *VecScratch) (*Vec, bool)
- type ReadPlan
- type Vec
- func (v *Vec) CopyElem(i int, src *Vec, j int) bool
- func (v *Vec) CountTrue(live []uint64) int
- func (v *Vec) Float(i int) float64
- func (v *Vec) IsTrue(i int) bool
- func (v *Vec) Len() int
- func (v *Vec) SetBool(i int, b bool)
- func (v Vec) SetInt(i int, x int64)
- func (v Vec) SetReal(i int, f float64)
- func (v *Vec) SetString(i int, s string)
- type VecScratch
Constants ¶
const ( VsInt uint8 = iota // I[i] is the integer VsReal // I[i] is math.Float64bits of the real VsBool // I[i] is 0 or 1 VsUndef // UNDEFINED VsError // ERROR VsString // S[i] is the string VsDictCode // I[i] is a code into Vec.Dict: a dictionary-encoded STRING )
Element states. A vector carries one per element, which is how three-valued logic and ERROR survive vectorization, and how int and real stay distinguishable -- 7/2 is not 7.0/2.0.
Variables ¶
This section is empty.
Functions ¶
func MaskWords ¶ added in v0.27.0
MaskWords returns the number of uint64 words a mask plane needs for n records. Exported so a caller that builds its own visibility mask sizes it the same way the executor does.
func PopCountMasked ¶ added in v0.27.0
PopCountMasked counts set bits of a & b, for a caller combining its own bitmaps.
func RawColumnUseful ¶ added in v0.27.0
RawColumnUseful reports whether handing a column of this width to the executor in its STORED form can pay off -- that is, whether an engine on this build and this CPU has lanes for it.
A source should gate on this rather than always supplying a raw column. Without an engine the raw form is not free: every non-comparison path has to widen it, and doing that measured 0.87x to 0.89x of a scan on the arithmetic shapes, where both operands widen. There is no point paying that for lanes nobody has.
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 ColumnSource ¶ added in v0.27.0
type ColumnSource interface {
LoadColumn(name string, scope ast.AttributeScope, dst *Vec) bool
}
ColumnSource supplies a batch of values for an attribute reference. The collections package implements it over a columnar block; anything that can produce n values per attribute can.
ok=false means the reference cannot be served as a vector -- a string column, or an attribute whose values are expressions -- and the evaluation declines as a whole.
type DictResolver ¶ added in v0.27.0
type DictResolver interface {
Range(lit string) (lo, hi int, ok bool)
At(code int) (string, bool)
Len() int
}
DictResolver resolves a dictionary-encoded string column for one block.
Range is what makes a comparison an integer test: because the dictionary is sorted by the evaluator's fold comparison, the entries that compare EQUAL to a literal are contiguous, so a match is `lo <= code < hi` and an ordering comparison is a test against one boundary. lo == hi means the literal is absent, and the caller can conclude that no record matches without reading a code.
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) ExactProbes ¶ added in v0.27.0
ExactProbes returns the query's probes together with whether they are EXACTLY equivalent to the query: the top-level expression is a conjunction and EVERY conjunct was recognized as a probe.
Probes and ProbePlan are deliberate OVER-APPROXIMATIONS, built for index pruning where the store re-verifies every candidate, so an omitted conjunct only costs selectivity. A consumer that answers from the probes ALONE -- a columnar COUNT/MIN/MAX that never re-verifies -- needs the opposite guarantee, and using Probes for that silently over-counts: `ProcId >= 5 && ClusterId != ProcId` compiles natively and yields ONE probe, because an attribute-to-attribute comparison is not `Attr OP literal`, so counting from that probe alone answers `ProcId >= 5` instead of the query.
exact=false means "do not answer from these probes"; they remain a sound candidate filter.
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.
func (*Query) ReadAttrs ¶
ReadAttrs returns the distinct unscoped attribute names the query may read.
func (*Query) VecEval ¶ added in v0.27.0
func (q *Query) VecEval(src ColumnSource, n int, scratch *VecScratch) (*Vec, bool)
VecEval executes the query over a batch of n records and returns the result vector. A record matches a constraint when its element is VsBool with I == 1; see Vec.IsTrue.
ok=false when the program uses something this executor does not implement. It never returns a partial answer.
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.
type Vec ¶ added in v0.27.0
type Vec struct {
// DATA form: one element per record.
I []int64
S []string
St []uint8
// MASK form: three-valued logic as two bitplanes, two bits per record. See vecmask.go.
Hi, Lo []uint64
// Raw, when non-nil, is the column in its STORED form: n values of RawWidth bytes, contiguous, as the
// block holds them. I is NOT populated while it is set.
//
// It exists for one reason: lanes come from width. A column fitted to two bytes is 8 lanes of a 128-bit
// vector against 2 as int64, and widening it at load throws that away before any kernel sees it. So a
// comparison against a literal can run width-native (see simdCompareRaw) and everything else calls
// ensureInts, which widens exactly as loadIntBatch used to and clears Raw. A transient optimization that
// collapses to the ordinary representation on first non-specialized use.
Raw []byte
RawWidth int
RawUnsigned bool
RawReal bool // a real's slot holds math.Float64bits, so widening it yields VsReal rather than VsInt
// Dict, when non-nil, resolves VsDictCode elements: the column is a dictionary-encoded string, so I[i]
// holds a code rather than a value and S[i] is not populated.
//
// A comparison against a string LITERAL specializes on this and becomes an integer range test, which is
// the whole point -- the dictionary is fold-ordered, so the entries matching a literal are contiguous.
// Everything else stays correct without knowing about it, because valueData resolves a code to its
// string and the parity hook takes it from there.
Dict DictResolver
// Const marks a vector every record of which holds the SAME value, kept once in element 0 with the
// rest left as garbage. A literal in an expression is the dominant case, and materializing one across
// a block cost 9.8% of a scan in the profile -- nine bytes per record written per block, to say the
// same thing 1000 times.
//
// Every consumer must either specialize on it (compareVec does, which also tightens its loop by
// reading a scalar instead of a second array) or call materialize first. valueData and IsTrue read
// element 0 when it is set, so the parity-hook path and the counters are safe without either.
Const bool
// Mask selects which form holds this vector's value. A comparison consumes data and produces a
// mask; a logical operator consumes and produces masks; arithmetic consumes and produces data.
// Conversion in either direction is available (toMask/toData) but only happens where an operator
// genuinely needs the other form.
Mask bool
// contains filtered or unexported fields
}
Vec is one batch of values. The payload is a single int64 slice because that is how both classad.Value and the columnar block already store a real (as IEEE-754 bits), so loading a column into a vector is a copy rather than a conversion, and no precision is lost for integers above 2^53.
func NewVec ¶ added in v0.28.0
NewVec allocates a data-form vector of n elements, every one UNDEFINED.
For a caller outside this package that materializes a column the loaders cannot produce -- one that exists for only SOME records, so it has to be presented at full length with the rest undefined. Undefined rather than zero is the safe start: an element nothing writes then reads as "no value here" instead of as the integer 0.
func (*Vec) CopyElem ¶ added in v0.28.0
CopyElem copies element j of src into element i of v, preserving its state -- int stays int, real stays real, a dictionary code stays a code. Returns false if either index is out of range.
This is the scatter primitive. Boxing through classad.Value would work and is what a caller without it must do, but it allocates for strings and loses the dictionary encoding, turning a code copy into a string materialization per record.
A src in RAW form is widened first: raw is a stored-width column, and an element of it means nothing once separated from its width and signedness.
func (*Vec) CountTrue ¶ added in v0.27.0
CountTrue counts records that are TRUE and whose bit is set in live.
In mask form that is one popcount per 64 records. In data form -- a constraint whose value is a number or a string, which never matches -- it walks elements, because such a constraint is rare and being right about it matters more than being quick.
func (*Vec) Float ¶ added in v0.27.0
Float returns element i as a float64 whatever its numeric state.
func (*Vec) IsTrue ¶ added in v0.27.0
IsTrue reports whether element i is TRUE, which is what counting matches needs. UNDEFINED and ERROR are not matches. IsTrue reports whether element i is strictly boolean TRUE, which is what counting matches needs.
This is NOT the truthiness used for a logical OPERAND. A constraint whose value is the number 42 does not match -- the store's isTrueValue takes a boolean or nothing -- while `42 && true` is TRUE because numbers are truthy as operands. Two different notions of truth, and conflating them is a silent wrong-answer bug, so they are separate functions: this one, and dataStateToMask.
type VecScratch ¶ added in v0.27.0
type VecScratch struct {
// contains filtered or unexported fields
}
VecScratch holds the vector stack and the evaluator so a scan reuses both across batches instead of allocating per block.
func (*VecScratch) Release ¶ added in v0.27.0
func (s *VecScratch) Release()
Release drops the vector stack's references to string payloads and returns the scratch to a state safe to keep in a pool.
A string element aliases a block's decompressed string region rather than copying it, so a pooled stack would otherwise pin whichever region it last read -- for as long as the pool holds it, and even if the table it came from has since been dropped. The regions are heap buffers, so this is a retention question rather than the use-after-munmap hazard aliasing mmap'd memory would create, but a few thousand pointer writes per query is a cheap way not to have the question at all.
Source Files