arb/expr.rs
1//! Arb's computational substrate: arithmetic expressions are compiled to a
2//! `fusevm::Chunk` and executed on the fusevm VM (Cranelift JIT for hot chunks).
3//! This is what "arb runs on fusevm" means concretely — every computed value in
4//! a spec flows through fusevm bytecode, not a bespoke evaluator.
5//!
6//! `x` is the pipeline input scalar; a bareword identifier (`amount`, `latency`)
7//! is a field of the current record, resolved by the caller's closure. Both are
8//! baked into the chunk as constants per evaluation, so no VM slot state is
9//! assumed across `run()`.
10//! Comparisons (`== != < <= > >=`) lower to fusevm's `Num*` ops and yield a
11//! boolean; `eval_pred` reads the result via `Value::is_truthy` for `where`.
12
13use fusevm::vm::{VMResult, VM};
14use fusevm::{ChunkBuilder, Op, Value};
15use std::cell::RefCell;
16
17#[derive(Debug, Clone, Copy)]
18pub enum BinOp {
19 Add,
20 Sub,
21 Mul,
22 Div,
23 Mod,
24 Eq,
25 Ne,
26 Lt,
27 Le,
28 Gt,
29 Ge,
30 /// Logical `and`/`or` over truthiness (each operand normalized to 0/1).
31 And,
32 Or,
33}
34
35#[derive(Debug, Clone)]
36pub enum Expr {
37 Num(f64),
38 /// The pipeline input scalar.
39 Var,
40 /// A named field of the current record, resolved at eval time.
41 Field(String),
42 /// A live control reference (`.th` — an `input`/control widget's value),
43 /// written `.name` in a predicate. `resolve_pipeline` substitutes it with a
44 /// `Num` before eval when the control holds a number; unresolved -> NaN.
45 Control(String),
46 /// A string literal — only produced by substituting a string control.
47 Str(String),
48 /// `match(.q)` — substring test of the whole line against a control's text.
49 /// Evaluated Rust-side (not on the numeric VM); empty control -> matches all.
50 Match(Box<Expr>),
51 /// `<field> in .lv` — set membership: keep lines whose FIELD value is in the
52 /// control's comma-separated selected set. Empty set -> matches all.
53 InSet(String, Box<Expr>),
54 Neg(Box<Expr>),
55 /// Logical negation: truthy input -> 0, falsy -> 1.
56 Not(Box<Expr>),
57 /// `name(arg, …)` — a call to an inline-Rust FFI export registered by a
58 /// `rust { ... }` block. Numeric-only: each arg is evaluated to an f64 and
59 /// marshaled as a `fusevm::Value::float`; the export's return is read back as
60 /// an f64. An unregistered name (or a failed call) evaluates to NaN, so a
61 /// comparison against it is simply false.
62 Call(String, Vec<Expr>),
63 /// Membership: `left in [a, b, c]` — truthy iff `left` equals any element
64 /// (jq `IN`). Empty list is always falsy.
65 InList(Box<Expr>, Vec<Expr>),
66 /// Range membership: `left in lo..hi` — truthy iff `lo <= left <= hi`.
67 InRange(Box<Expr>, Box<Expr>, Box<Expr>),
68 /// Ternary `cond ? then : else` — only the taken branch is evaluated (real
69 /// fusevm branching), so a guarded `x != 0 ? 100/x : 0` never divides by 0.
70 Cond(Box<Expr>, Box<Expr>, Box<Expr>),
71 Bin(BinOp, Box<Expr>, Box<Expr>),
72}
73
74/// Parse an expression: numbers, `x`, `+ - * / %`, comparisons
75/// (`== != < <= > >=`), unary `-`, and parentheses.
76pub fn parse(src: &str) -> Result<Expr, String> {
77 let mut p = Parser {
78 c: src.chars().collect(),
79 i: 0,
80 depth: 0,
81 };
82 let e = p.ternary()?;
83 if p.peek().is_some() {
84 return Err(format!("calc: unexpected `{}`", p.c[p.i]));
85 }
86 Ok(e)
87}
88
89/// Evaluate as a number with no field resolver (field refs -> NaN).
90pub fn eval(e: &Expr, x: f64) -> Result<f64, String> {
91 eval_ctx(e, x, &|_| f64::NAN)
92}
93
94/// Collect the names of every `Control` reference in `e` (e.g. `.th` -> "th").
95pub fn control_names(e: &Expr, out: &mut Vec<String>) {
96 match e {
97 Expr::Control(n) => out.push(n.clone()),
98 Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => {}
99 Expr::Neg(a) | Expr::Not(a) | Expr::Match(a) | Expr::InSet(_, a) => control_names(a, out),
100 Expr::Call(_, items) => items.iter().for_each(|it| control_names(it, out)),
101 Expr::InList(l, items) => {
102 control_names(l, out);
103 items.iter().for_each(|it| control_names(it, out));
104 }
105 Expr::InRange(l, lo, hi) => {
106 control_names(l, out);
107 control_names(lo, out);
108 control_names(hi, out);
109 }
110 Expr::Cond(a, b, c) => {
111 control_names(a, out);
112 control_names(b, out);
113 control_names(c, out);
114 }
115 Expr::Bin(_, a, b) => {
116 control_names(a, out);
117 control_names(b, out);
118 }
119 }
120}
121
122/// Split control refs by the type they resolve to: `Match`/`InSet` inners are
123/// string controls, everything else is numeric. Lets `resolve_pipeline` require
124/// numeric controls to resolve (or drop the filter) while string controls with
125/// an empty value simply match everything.
126pub fn control_names_typed(e: &Expr, num: &mut Vec<String>, strv: &mut Vec<String>) {
127 match e {
128 Expr::Control(n) => num.push(n.clone()),
129 Expr::Match(inner) | Expr::InSet(_, inner) => {
130 if let Expr::Control(n) = inner.as_ref() {
131 strv.push(n.clone());
132 } else {
133 control_names_typed(inner, num, strv);
134 }
135 }
136 Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => {}
137 Expr::Neg(a) | Expr::Not(a) => control_names_typed(a, num, strv),
138 Expr::Call(_, items) => items
139 .iter()
140 .for_each(|it| control_names_typed(it, num, strv)),
141 Expr::InList(l, items) => {
142 control_names_typed(l, num, strv);
143 items
144 .iter()
145 .for_each(|it| control_names_typed(it, num, strv));
146 }
147 Expr::InRange(l, lo, hi) => {
148 control_names_typed(l, num, strv);
149 control_names_typed(lo, num, strv);
150 control_names_typed(hi, num, strv);
151 }
152 Expr::Cond(a, b, c) => {
153 control_names_typed(a, num, strv);
154 control_names_typed(b, num, strv);
155 control_names_typed(c, num, strv);
156 }
157 Expr::Bin(_, a, b) => {
158 control_names_typed(a, num, strv);
159 control_names_typed(b, num, strv);
160 }
161 }
162}
163
164/// Whether `e` contains a string predicate (`match`/`in .set`) — the query layer
165/// routes such a `where` to the Rust evaluator instead of the numeric VM.
166pub fn expr_has_str(e: &Expr) -> bool {
167 match e {
168 Expr::Match(_) | Expr::InSet(..) | Expr::Str(_) => true,
169 Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Control(_) => false,
170 Expr::Neg(a) | Expr::Not(a) => expr_has_str(a),
171 // A Call yields an f64; numeric-only args carry no string predicate, but
172 // recurse for consistency with every other compound node.
173 Expr::Call(_, items) => items.iter().any(expr_has_str),
174 Expr::InList(l, items) => expr_has_str(l) || items.iter().any(expr_has_str),
175 Expr::InRange(l, lo, hi) => expr_has_str(l) || expr_has_str(lo) || expr_has_str(hi),
176 Expr::Cond(a, b, c) => expr_has_str(a) || expr_has_str(b) || expr_has_str(c),
177 Expr::Bin(_, a, b) => expr_has_str(a) || expr_has_str(b),
178 }
179}
180
181/// Rewrite every `Control(name)` in `e` to `Control("{ns}.{name}")`, in place —
182/// used by `import X as Y` to namespace a module's control references.
183pub fn prefix_controls(e: &mut Expr, ns: &str) {
184 match e {
185 Expr::Control(n) => *n = format!("{ns}.{n}"),
186 Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => {}
187 Expr::Neg(a) | Expr::Not(a) | Expr::Match(a) | Expr::InSet(_, a) => prefix_controls(a, ns),
188 Expr::Call(_, items) => items.iter_mut().for_each(|it| prefix_controls(it, ns)),
189 Expr::InList(l, items) => {
190 prefix_controls(l, ns);
191 items.iter_mut().for_each(|it| prefix_controls(it, ns));
192 }
193 Expr::InRange(l, lo, hi) => {
194 prefix_controls(l, ns);
195 prefix_controls(lo, ns);
196 prefix_controls(hi, ns);
197 }
198 Expr::Cond(a, b, c) => {
199 prefix_controls(a, ns);
200 prefix_controls(b, ns);
201 prefix_controls(c, ns);
202 }
203 Expr::Bin(_, a, b) => {
204 prefix_controls(a, ns);
205 prefix_controls(b, ns);
206 }
207 }
208}
209
210/// Return a copy of `e` with control refs substituted: a numeric `Control` ->
211/// `Num(num(n))` when resolvable (else left as-is -> NaN); a string control
212/// inside `match`/`in .set` -> `Str(strv(n))` (empty when unset -> matches all).
213pub fn substitute_controls(
214 e: &Expr,
215 num: &dyn Fn(&str) -> Option<f64>,
216 strv: &dyn Fn(&str) -> Option<String>,
217) -> Expr {
218 let sub = |b: &Expr| Box::new(substitute_controls(b, num, strv));
219 // Resolve a control ref to a string node (for match/in-set inners).
220 let sub_str = |b: &Expr| -> Box<Expr> {
221 match b {
222 Expr::Control(n) => Box::new(Expr::Str(strv(n).unwrap_or_default())),
223 other => Box::new(substitute_controls(other, num, strv)),
224 }
225 };
226 match e {
227 Expr::Control(n) => match num(n) {
228 Some(v) => Expr::Num(v),
229 None => Expr::Control(n.clone()),
230 },
231 Expr::Match(inner) => Expr::Match(sub_str(inner)),
232 Expr::InSet(field, inner) => Expr::InSet(field.clone(), sub_str(inner)),
233 Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => e.clone(),
234 Expr::Call(name, items) => Expr::Call(
235 name.clone(),
236 items
237 .iter()
238 .map(|it| substitute_controls(it, num, strv))
239 .collect(),
240 ),
241 Expr::Neg(a) => Expr::Neg(sub(a)),
242 Expr::Not(a) => Expr::Not(sub(a)),
243 Expr::InList(l, items) => Expr::InList(
244 sub(l),
245 items
246 .iter()
247 .map(|it| substitute_controls(it, num, strv))
248 .collect(),
249 ),
250 Expr::InRange(l, lo, hi) => Expr::InRange(sub(l), sub(lo), sub(hi)),
251 Expr::Cond(a, b, c) => Expr::Cond(sub(a), sub(b), sub(c)),
252 Expr::Bin(op, a, b) => Expr::Bin(*op, sub(a), sub(b)),
253 }
254}
255
256/// Arm fusevm's Cranelift tiers on a VM about to run an expression chunk.
257///
258/// One flag gates both tiers: `vm.rs`'s tiered auto-dispatch checks
259/// `tracing_jit` before it will even ask `is_block_eligible`, so without this
260/// call a chunk runs on the interpreter no matter what the `jit` feature says.
261/// An arb expression lowers to straight-line native ops with no backward
262/// branch, so the block tier is the one that takes it — compiled once, then
263/// reused from fusevm's on-disk cache across runs, which is what a predicate
264/// evaluated over every row wants. `arb --tiers` reports the outcome.
265fn arm_tiers(vm: &mut VM) {
266 vm.enable_tracing_jit();
267}
268
269/// Lower `e` to a fusevm chunk (with `x` and resolved fields baked in), run it on
270/// the VM, and return the resulting number. `resolve` maps a field name to its
271/// numeric value.
272pub fn eval_ctx(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64) -> Result<f64, String> {
273 let mut b = ChunkBuilder::new();
274 emit(e, x, resolve, &mut b);
275 with_pooled_vm(b.build(), |vm| match vm.run() {
276 VMResult::Ok(v) => Ok(v.to_float()),
277 VMResult::Halted => Ok(vm.peek().to_float()),
278 VMResult::Error(err) => Err(err),
279 })
280}
281
282thread_local! {
283 /// Recycled VMs for the per-record expression path.
284 ///
285 /// `where`/`map` lower a chunk PER LINE — the chunk is a function of `x` and
286 /// the resolved fields, both baked in as constants — so a stream of N records
287 /// ran `VM::new` N times, and each of those rebuilds the VM's builtin table
288 /// and its stack/frame/global vectors from scratch. `VMPool::acquire` keeps
289 /// those allocations and only clears state, which is exactly what a
290 /// per-record caller needs.
291 ///
292 /// Measured over 50,000 records, release build, against `jq 1.8.2` on the
293 /// same data: `field v; where x > 500` was 1.174s before this (jq: 0.141s).
294 static VM_POOL: RefCell<fusevm::vm::VMPool> = RefCell::new(fusevm::vm::VMPool::new());
295}
296
297/// Run `f` against a VM from this thread's pool, returning it afterwards.
298fn with_pooled_vm<T>(chunk: fusevm::Chunk, f: impl FnOnce(&mut VM) -> T) -> T {
299 VM_POOL.with(|p| {
300 // The pool is borrowed only to check a VM out and back in, never across
301 // `f` — a nested expression evaluation (an FFI argument) re-enters here.
302 let mut vm = p.borrow_mut().acquire(chunk);
303 arm_tiers(&mut vm);
304 let r = f(&mut vm);
305 p.borrow_mut().release(vm);
306 r
307 })
308}
309
310/// Lower `e` to the fusevm chunk [`eval_ctx`] would run, without running it.
311///
312/// The chunk is a function of `x` and the resolved fields, not of `e` alone:
313/// both are baked in as `LoadFloat` constants (see the private `emit`). Two evaluations
314/// of the same expression at different `x` are therefore *different* chunks
315/// with different op hashes, which is what [`crate::tiers`] exists to report on.
316pub fn chunk_of(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64) -> fusevm::Chunk {
317 let mut b = ChunkBuilder::new();
318 emit(e, x, resolve, &mut b);
319 b.build()
320}
321
322/// Evaluate as a predicate with no field resolver.
323pub fn eval_pred(e: &Expr, x: f64) -> Result<bool, String> {
324 eval_pred_ctx(e, x, &|_| f64::NAN)
325}
326
327/// Evaluate `e` as a predicate — compiled to fusevm, run on the VM, read as a
328/// boolean via `Value::is_truthy`. `resolve` maps a field name to its value.
329pub fn eval_pred_ctx(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64) -> Result<bool, String> {
330 let mut b = ChunkBuilder::new();
331 emit(e, x, resolve, &mut b);
332 with_pooled_vm(b.build(), |vm| match vm.run() {
333 VMResult::Ok(v) => Ok(v.is_truthy()),
334 VMResult::Halted => Ok(vm.peek().is_truthy()),
335 VMResult::Error(err) => Err(err),
336 })
337}
338
339/// Evaluate a `name(args)` inline-Rust FFI call at lowering time: resolve each
340/// argument to an f64 on the same VM, marshal it as a `fusevm::Value::float`
341/// (fusevm coerces to the export's `i64`/`f64` signature), dispatch to the
342/// registered export, and read the return back as an f64. An unregistered name
343/// or a failed call yields NaN — the same way an unresolved control degrades —
344/// so the emitter can bake the result in as a constant without a fallible path.
345fn eval_call(name: &str, args: &[Expr], x: f64, resolve: &dyn Fn(&str) -> f64) -> f64 {
346 if !fusevm::ffi::is_registered(name) {
347 return f64::NAN;
348 }
349 let vals: Vec<Value> = args
350 .iter()
351 .map(|a| Value::float(eval_ctx(a, x, resolve).unwrap_or(f64::NAN)))
352 .collect();
353 match fusevm::ffi::try_call(name, &vals) {
354 Some(Ok(v)) => v.to_float(),
355 _ => f64::NAN,
356 }
357}
358
359fn emit(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64, b: &mut ChunkBuilder) {
360 match e {
361 Expr::Num(n) => {
362 b.emit(Op::LoadFloat(*n), 0);
363 }
364 Expr::Var => {
365 b.emit(Op::LoadFloat(x), 0);
366 }
367 Expr::Field(name) => {
368 b.emit(Op::LoadFloat(resolve(name)), 0);
369 }
370 // An unsubstituted control (its value was empty/non-numeric) -> NaN, so
371 // comparisons against it are false. Normally resolve_pipeline replaces it
372 // with a Num, or drops the whole `where` op, before we get here.
373 Expr::Control(_) => {
374 b.emit(Op::LoadFloat(f64::NAN), 0);
375 }
376 // String predicates never reach the numeric VM — the query layer routes a
377 // string-bearing `where` to a Rust evaluator. Emit a neutral 0 so any
378 // stray numeric use degrades gracefully instead of panicking.
379 Expr::Str(_) | Expr::Match(_) | Expr::InSet(..) => {
380 b.emit(Op::LoadFloat(0.0), 0);
381 }
382 // An FFI call can't run inside fusevm bytecode, so evaluate it now and
383 // bake the resulting f64 in as a constant.
384 Expr::Call(name, args) => {
385 b.emit(Op::LoadFloat(eval_call(name, args, x, resolve)), 0);
386 }
387 Expr::Neg(a) => {
388 emit(a, x, resolve, b);
389 b.emit(Op::Negate, 0);
390 }
391 Expr::Not(a) => {
392 // Logical not: `a == 0` yields 1 for falsy `a`, 0 for truthy.
393 emit(a, x, resolve, b);
394 b.emit(Op::LoadFloat(0.0), 0);
395 b.emit(Op::NumEq, 0);
396 }
397 Expr::InList(left, items) => {
398 // Sum of `(left == item)` over the list; truthy iff any matched.
399 // The sum COUNTS matches, so a list with a repeated element yields 2
400 // or 3 — fine for `where`'s truthiness test, wrong for `map`/`calc`,
401 // which print the expression's value. Normalize back to 0/1.
402 if items.is_empty() {
403 b.emit(Op::LoadFloat(0.0), 0);
404 } else {
405 for (k, it) in items.iter().enumerate() {
406 emit(left, x, resolve, b);
407 emit(it, x, resolve, b);
408 b.emit(Op::NumEq, 0);
409 if k > 0 {
410 b.emit(Op::Add, 0);
411 }
412 }
413 if items.len() > 1 {
414 emit_normalize_bool(b);
415 }
416 }
417 }
418 Expr::InRange(left, lo, hi) => {
419 // `(left >= lo) and (left <= hi)` — both yield 0/1, product is 1 iff
420 // in range.
421 emit(left, x, resolve, b);
422 emit(lo, x, resolve, b);
423 b.emit(Op::NumGe, 0);
424 emit(left, x, resolve, b);
425 emit(hi, x, resolve, b);
426 b.emit(Op::NumLe, 0);
427 b.emit(Op::Mul, 0);
428 }
429 Expr::Cond(c, t, e2) => {
430 // Real branching: `JumpIfFalse` pops the condition and skips to the
431 // else branch when falsy, so only the taken branch runs.
432 emit(c, x, resolve, b);
433 let jf = b.emit(Op::JumpIfFalse(0), 0);
434 emit(t, x, resolve, b);
435 let jend = b.emit(Op::Jump(0), 0);
436 let else_pos = b.current_pos();
437 b.patch_jump(jf, else_pos);
438 emit(e2, x, resolve, b);
439 let end_pos = b.current_pos();
440 b.patch_jump(jend, end_pos);
441 }
442 // `and`/`or` operate on truthiness: normalize each side to 0/1 first,
443 // then `and` = product (1 iff both 1), `or` = sum (>=1 iff either 1).
444 Expr::Bin(BinOp::And, a, c) => {
445 emit_bool(a, x, resolve, b);
446 emit_bool(c, x, resolve, b);
447 b.emit(Op::Mul, 0);
448 }
449 Expr::Bin(BinOp::Or, a, c) => {
450 emit_bool(a, x, resolve, b);
451 emit_bool(c, x, resolve, b);
452 b.emit(Op::Add, 0);
453 // The sum is 2 when BOTH sides are true. `where` only reads
454 // truthiness so it never noticed, but `map`/`calc` print the value —
455 // `map x > 1 or x > 2` at x=5 printed `2`. Every other
456 // boolean-producing node (`and`, a comparison, `not`) yields 0/1, so
457 // normalize `or` to match.
458 emit_normalize_bool(b);
459 }
460 Expr::Bin(op, a, c) => {
461 emit(a, x, resolve, b);
462 emit(c, x, resolve, b);
463 b.emit(
464 match op {
465 BinOp::Add => Op::Add,
466 BinOp::Sub => Op::Sub,
467 BinOp::Mul => Op::Mul,
468 BinOp::Div => Op::Div,
469 BinOp::Mod => Op::Mod,
470 BinOp::Eq => Op::NumEq,
471 BinOp::Ne => Op::NumNe,
472 BinOp::Lt => Op::NumLt,
473 BinOp::Le => Op::NumLe,
474 BinOp::Gt => Op::NumGt,
475 BinOp::Ge => Op::NumGe,
476 BinOp::And | BinOp::Or => unreachable!("handled above"),
477 },
478 0,
479 );
480 }
481 }
482}
483
484/// Emit `e` normalized to a boolean 0.0/1.0 (`e != 0`), for logical combinators.
485fn emit_bool(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64, b: &mut ChunkBuilder) {
486 emit(e, x, resolve, b);
487 emit_normalize_bool(b);
488}
489
490/// Normalize the value already on the stack to a boolean 0.0/1.0 (`v != 0`).
491/// Used wherever a node builds its answer by SUMMING 0/1 terms (`or`, `in
492/// [list]`), whose sum can exceed 1 and would otherwise leak out of a `map`
493/// or `calc` as a count instead of a boolean.
494fn emit_normalize_bool(b: &mut ChunkBuilder) {
495 b.emit(Op::LoadFloat(0.0), 0);
496 b.emit(Op::NumNe, 0);
497}
498
499struct Parser {
500 c: Vec<char>,
501 i: usize,
502 /// Recursion depth of `primary()`, so a pathologically nested expression
503 /// (`(((…x…)))`) fails closed instead of overflowing the stack.
504 depth: usize,
505}
506
507/// Cap on `(`-nesting in `map`/`where`/`calc` expressions — well past any real
508/// expression, but bounded so a malicious input can't abort the process.
509///
510/// The bound that matters is STACK, not syntax: one nesting level costs one
511/// frame per nonterminal between `primary` and its recursive call. A
512/// parenthesized group re-enters at `ternary`, so a level walks
513/// `ternary → or → and → not → comparison → additive → multiplicative → unary →
514/// primary` — about twice the chain a group that re-entered at `additive` cost,
515/// and a limit tuned for the shorter chain aborted the process (SIGABRT) instead
516/// of erroring. Halved to keep the guard inside the same stack budget;
517/// `tests/expr.rs::deep_nesting_errors_not_stack_overflow` is what proves it.
518const MAX_EXPR_DEPTH: usize = 128;
519
520impl Parser {
521 /// Peek the next non-whitespace char (consuming leading whitespace).
522 fn peek(&mut self) -> Option<char> {
523 while self.i < self.c.len() && self.c[self.i].is_whitespace() {
524 self.i += 1;
525 }
526 self.c.get(self.i).copied()
527 }
528
529 /// Lowest precedence: `cond ? then : else` (right-associative).
530 fn ternary(&mut self) -> Result<Expr, String> {
531 let cond = self.or_expr()?;
532 if self.peek() == Some('?') {
533 self.i += 1;
534 let then = self.ternary()?;
535 if self.peek() != Some(':') {
536 return Err("calc: expected `:` in `?:`".into());
537 }
538 self.i += 1;
539 let els = self.ternary()?;
540 return Ok(Expr::Cond(Box::new(cond), Box::new(then), Box::new(els)));
541 }
542 Ok(cond)
543 }
544
545 /// `a or b`.
546 fn or_expr(&mut self) -> Result<Expr, String> {
547 let mut left = self.and_expr()?;
548 while self.match_kw("or") {
549 let right = self.and_expr()?;
550 left = Expr::Bin(BinOp::Or, Box::new(left), Box::new(right));
551 }
552 Ok(left)
553 }
554
555 /// `a and b`, binding tighter than `or`.
556 fn and_expr(&mut self) -> Result<Expr, String> {
557 let mut left = self.not_expr()?;
558 while self.match_kw("and") {
559 let right = self.not_expr()?;
560 left = Expr::Bin(BinOp::And, Box::new(left), Box::new(right));
561 }
562 Ok(left)
563 }
564
565 /// Prefix `not`, binding tighter than `and`/`or` but looser than comparison.
566 fn not_expr(&mut self) -> Result<Expr, String> {
567 if self.match_kw("not") {
568 // `not not … 1` recurses here, never through `primary`, so guard it
569 // too or a long chain overflows the stack (rc=134).
570 self.deepen()?;
571 let inner = self.not_expr();
572 self.depth -= 1;
573 return Ok(Expr::Not(Box::new(inner?)));
574 }
575 self.comparison()
576 }
577
578 /// Consume the keyword `kw` if it is the next whole word (not a prefix of a
579 /// longer identifier, e.g. `and` must not match inside `android`).
580 fn match_kw(&mut self, kw: &str) -> bool {
581 let save = self.i;
582 while self.i < self.c.len() && self.c[self.i].is_whitespace() {
583 self.i += 1;
584 }
585 let start = self.i;
586 let kwc: Vec<char> = kw.chars().collect();
587 let end = start + kwc.len();
588 let boundary_ok =
589 end >= self.c.len() || !(self.c[end].is_ascii_alphanumeric() || self.c[end] == '_');
590 if end <= self.c.len() && self.c[start..end] == kwc[..] && boundary_ok {
591 self.i = end;
592 true
593 } else {
594 self.i = save;
595 false
596 }
597 }
598
599 fn comparison(&mut self) -> Result<Expr, String> {
600 let mut left = self.additive()?;
601 if self.match_kw("in") {
602 return self.in_list(left);
603 }
604 while let Some(op) = self.cmp_op() {
605 let right = self.additive()?;
606 left = Expr::Bin(op, Box::new(left), Box::new(right));
607 }
608 Ok(left)
609 }
610
611 /// Parse a `.name` control reference into `Expr::Control(name)`.
612 fn control_ref(&mut self) -> Result<Expr, String> {
613 if self.peek() != Some('.') {
614 return Err("expected a control ref `.name`".into());
615 }
616 self.i += 1; // consume '.'
617 let name = self.dotted_ident();
618 if name.is_empty() {
619 return Err("expected a control name after `.`".into());
620 }
621 Ok(Expr::Control(name))
622 }
623
624 /// Parse the right-hand side of an `in` test: a `.name` control set, a
625 /// `[a, b, c]` list, or a `lo..hi` range.
626 fn in_list(&mut self, left: Expr) -> Result<Expr, String> {
627 // `<field> in .lv` — set membership against a live control's selected set.
628 // Only a `.`+letter is a control ref; `.5` stays a fractional range bound.
629 if self.peek() == Some('.')
630 && matches!(self.c.get(self.i + 1), Some(c) if c.is_ascii_alphabetic() || *c == '_')
631 {
632 let field = match &left {
633 Expr::Field(n) => n.clone(),
634 Expr::Var => "x".to_string(),
635 _ => return Err("in .set: left side must be a field".into()),
636 };
637 let ctrl = self.control_ref()?;
638 return Ok(Expr::InSet(field, Box::new(ctrl)));
639 }
640 if self.peek() != Some('[') {
641 // `lo..hi` range membership.
642 let lo = self.additive()?;
643 if !(self.peek() == Some('.') && self.c.get(self.i + 1) == Some(&'.')) {
644 return Err("in: expected `[list]` or `lo..hi`".into());
645 }
646 self.i += 2;
647 let hi = self.additive()?;
648 return Ok(Expr::InRange(Box::new(left), Box::new(lo), Box::new(hi)));
649 }
650 self.i += 1;
651 let mut items = Vec::new();
652 loop {
653 if self.peek() == Some(']') {
654 self.i += 1;
655 break;
656 }
657 items.push(self.additive()?);
658 match self.peek() {
659 Some(',') => self.i += 1,
660 Some(']') => {
661 self.i += 1;
662 break;
663 }
664 _ => return Err("in: expected `,` or `]`".into()),
665 }
666 }
667 Ok(Expr::InList(Box::new(left), items))
668 }
669
670 /// Consume a comparison operator (`< <= > >= == !=`) if one is next.
671 fn cmp_op(&mut self) -> Option<BinOp> {
672 let c = self.peek()?;
673 if !matches!(c, '<' | '>' | '=' | '!') {
674 return None;
675 }
676 let next = self.c.get(self.i + 1).copied();
677 let (op, len) = match (c, next) {
678 ('<', Some('=')) => (BinOp::Le, 2),
679 ('<', _) => (BinOp::Lt, 1),
680 ('>', Some('=')) => (BinOp::Ge, 2),
681 ('>', _) => (BinOp::Gt, 1),
682 ('=', Some('=')) => (BinOp::Eq, 2),
683 ('!', Some('=')) => (BinOp::Ne, 2),
684 _ => return None,
685 };
686 self.i += len;
687 Some(op)
688 }
689
690 fn additive(&mut self) -> Result<Expr, String> {
691 let mut left = self.multiplicative()?;
692 while let Some(c) = self.peek() {
693 let op = match c {
694 '+' => BinOp::Add,
695 '-' => BinOp::Sub,
696 _ => break,
697 };
698 self.i += 1;
699 let right = self.multiplicative()?;
700 left = Expr::Bin(op, Box::new(left), Box::new(right));
701 }
702 Ok(left)
703 }
704
705 fn multiplicative(&mut self) -> Result<Expr, String> {
706 let mut left = self.unary()?;
707 while let Some(c) = self.peek() {
708 let op = match c {
709 '*' => BinOp::Mul,
710 '/' => BinOp::Div,
711 '%' => BinOp::Mod,
712 _ => break,
713 };
714 self.i += 1;
715 let right = self.unary()?;
716 left = Expr::Bin(op, Box::new(left), Box::new(right));
717 }
718 Ok(left)
719 }
720
721 fn unary(&mut self) -> Result<Expr, String> {
722 if self.peek() == Some('-') {
723 self.i += 1;
724 // `- - … 1` recurses here, never through `primary`; guard it too.
725 self.deepen()?;
726 let inner = self.unary();
727 self.depth -= 1;
728 return Ok(Expr::Neg(Box::new(inner?)));
729 }
730 self.primary()
731 }
732
733 /// Enter one recursion level, failing closed if it exceeds `MAX_EXPR_DEPTH`
734 /// (decrementing itself on that error). Every self-recursive parse point —
735 /// `primary` (paren nesting), `not_expr`, `unary` — calls this then does
736 /// `self.depth -= 1` after its recursive call, so adversarial input errors
737 /// instead of overflowing the stack.
738 fn deepen(&mut self) -> Result<(), String> {
739 self.depth += 1;
740 if self.depth > MAX_EXPR_DEPTH {
741 self.depth -= 1;
742 return Err("calc: expression too deeply nested".into());
743 }
744 Ok(())
745 }
746
747 fn primary(&mut self) -> Result<Expr, String> {
748 self.deepen()?;
749 let r = self.primary_inner();
750 self.depth -= 1;
751 r
752 }
753
754 fn primary_inner(&mut self) -> Result<Expr, String> {
755 match self.peek() {
756 // A parenthesized group is a FULL expression, the same nonterminal a
757 // call argument gets. Recursing into `additive` instead stopped at the
758 // first comparison or keyword, so the three natural groupings —
759 // `(x > 1) and (x < 5)`, `not (a or b)`, `(x > 1 ? 10 : 20)` — were
760 // rejected with "calc: expected `)`" even though the doc comment on
761 // `parse` lists parentheses as supported.
762 Some('(') => {
763 self.i += 1;
764 let e = self.ternary()?;
765 if self.peek() != Some(')') {
766 return Err("calc: expected `)`".into());
767 }
768 self.i += 1;
769 Ok(e)
770 }
771 Some(c) if c.is_ascii_alphabetic() || c == '_' => {
772 let name = self.ident();
773 // `match(.q)` — a builtin substring test against a control string.
774 if name == "match" && self.peek() == Some('(') {
775 self.i += 1; // consume '('
776 let inner = self.control_ref()?;
777 if self.peek() != Some(')') {
778 return Err("match: expected `)`".into());
779 }
780 self.i += 1;
781 return Ok(Expr::Match(Box::new(inner)));
782 }
783 // `name(arg, …)` — an inline-Rust FFI call. Any other identifier
784 // immediately followed by `(` was previously a parse error, so
785 // this grammar addition is purely additive.
786 if self.peek() == Some('(') {
787 return self.call(name);
788 }
789 Ok(if name == "x" {
790 Expr::Var
791 } else {
792 Expr::Field(name)
793 })
794 }
795 // `.name` is a control reference (a live widget value); `.5` stays a
796 // number. Distinguish by whether the char after `.` is a letter.
797 Some('.') if matches!(self.c.get(self.i + 1), Some(c) if c.is_ascii_alphabetic() || *c == '_') =>
798 {
799 self.i += 1; // consume the leading `.`
800 Ok(Expr::Control(self.dotted_ident()))
801 }
802 Some(c) if c.is_ascii_digit() || c == '.' => self.number(),
803 // A double-quoted string literal. jq's `select(.status == "ok")` is a
804 // COMPARE, which the spec documents as in-subset, but without a string
805 // atom the predicate could not even parse; `eval_where` gives the
806 // resulting `Str` node its string-comparison semantics.
807 Some('"') => {
808 self.i += 1; // consume the opening quote
809 let mut s = String::new();
810 while let Some(&c) = self.c.get(self.i) {
811 match c {
812 '"' => {
813 self.i += 1;
814 return Ok(Expr::Str(s));
815 }
816 '\\' if self.i + 1 < self.c.len() => {
817 s.push(match self.c[self.i + 1] {
818 'n' => '\n',
819 't' => '\t',
820 o => o,
821 });
822 self.i += 2;
823 }
824 _ => {
825 s.push(c);
826 self.i += 1;
827 }
828 }
829 }
830 Err("calc: unterminated string literal".into())
831 }
832 Some(c) => Err(format!("calc: unexpected `{c}`")),
833 None => Err("calc: unexpected end of expression".into()),
834 }
835 }
836
837 fn ident(&mut self) -> String {
838 let start = self.i;
839 while self.i < self.c.len()
840 && (self.c[self.i].is_ascii_alphanumeric() || self.c[self.i] == '_')
841 {
842 self.i += 1;
843 }
844 self.c[start..self.i].iter().collect()
845 }
846
847 /// A control name that may be dot-segmented (`ps.sel`, `g.cpu`): the leading
848 /// ident, then any `.segment` where the char after the `.` is a letter/`_` (so
849 /// `.5` fractional bounds and `..` ranges are left alone). Enables the
850 /// `.<widget>.sel` selection accessor (SPEC §14) as a live control ref.
851 fn dotted_ident(&mut self) -> String {
852 let mut name = self.ident();
853 while self.i < self.c.len()
854 && self.c[self.i] == '.'
855 && matches!(self.c.get(self.i + 1), Some(c) if c.is_ascii_alphabetic() || *c == '_')
856 {
857 self.i += 1; // consume '.'
858 name.push('.');
859 name.push_str(&self.ident());
860 }
861 name
862 }
863
864 /// Parse the argument list of a `name(arg, …)` FFI call — the leading `(` is
865 /// the next char. Each argument is a full expression; `,` separates and `)`
866 /// closes. A zero-arg call `name()` is allowed.
867 fn call(&mut self, name: String) -> Result<Expr, String> {
868 self.i += 1; // consume '('
869 let mut args = Vec::new();
870 if self.peek() != Some(')') {
871 loop {
872 args.push(self.ternary()?);
873 match self.peek() {
874 Some(',') => self.i += 1,
875 Some(')') => break,
876 _ => return Err(format!("calc: expected `,` or `)` in call to `{name}`")),
877 }
878 }
879 }
880 self.i += 1; // consume ')'
881 Ok(Expr::Call(name, args))
882 }
883
884 fn number(&mut self) -> Result<Expr, String> {
885 let start = self.i;
886 while self.i < self.c.len() && self.c[self.i].is_ascii_digit() {
887 self.i += 1;
888 }
889 // At most one fractional part, and only when the `.` is followed by a
890 // digit — so `1..10` (a range) leaves the `..` for the range parser
891 // instead of the number greedily swallowing both dots.
892 if self.i < self.c.len()
893 && self.c[self.i] == '.'
894 && matches!(self.c.get(self.i + 1), Some(d) if d.is_ascii_digit())
895 {
896 self.i += 1;
897 while self.i < self.c.len() && self.c[self.i].is_ascii_digit() {
898 self.i += 1;
899 }
900 }
901 // An exponent suffix, so a literal can be written the way arb PRINTS one.
902 // `fmt_num` renders a computed number in jq's format, which is
903 // exponential past `1e16` and below `1e-4` — without this, arb emitted
904 // `1e+17` and then rejected `x > 1e+17` with "calc: unexpected `e`", so a
905 // value the language produced could not be typed back into it. The
906 // stream side never had that gap: a DATA line is read with Rust's
907 // `parse::<f64>`, which has always accepted `1e17`.
908 //
909 // Only consume the `e` when what follows really is an exponent — a
910 // digit, or a sign then a digit. A bare trailing `e` stays whatever the
911 // caller meant it to be rather than turning `1 e` into a bad number.
912 if matches!(self.c.get(self.i), Some('e' | 'E')) {
913 let after_sign = match self.c.get(self.i + 1) {
914 Some('+' | '-') => self.i + 2,
915 _ => self.i + 1,
916 };
917 if matches!(self.c.get(after_sign), Some(d) if d.is_ascii_digit()) {
918 self.i = after_sign;
919 while self.i < self.c.len() && self.c[self.i].is_ascii_digit() {
920 self.i += 1;
921 }
922 }
923 }
924 let s: String = self.c[start..self.i].iter().collect();
925 s.parse::<f64>()
926 .map(Expr::Num)
927 .map_err(|_| format!("calc: bad number `{s}`"))
928 }
929}
930
931#[cfg(test)]
932mod tests {
933 use super::*;
934
935 #[test]
936 fn dotted_control_name_parses_whole() {
937 // `.ps.sel` (a widget's selection accessor) is one control ref, not
938 // `.ps` followed by a stray `.sel`.
939 let e = parse(".ps.sel").unwrap();
940 let mut names = Vec::new();
941 control_names(&e, &mut names);
942 assert_eq!(names, vec!["ps.sel".to_string()]);
943 }
944
945 #[test]
946 fn dotted_control_substitutes_and_evals() {
947 // `.k.v * 2` with the control resolved to 21 -> 42.
948 let e = parse(".k.v * 2").unwrap();
949 let num = |n: &str| if n == "k.v" { Some(21.0) } else { None };
950 let strv = |_: &str| None;
951 let sub = substitute_controls(&e, &num, &strv);
952 assert_eq!(eval(&sub, 0.0).unwrap(), 42.0);
953 }
954
955 /// Every boolean-producing node must yield 0 or 1, because `map`/`calc`
956 /// print the expression's VALUE. `or` lowered to the sum of its two
957 /// normalized operands, so a row where both sides held answered `2`; `in
958 /// [list]` lowered to the count of matching elements, so a list with a
959 /// repeated element answered `2` or `3`. `where` reads only truthiness and
960 /// never saw either.
961 #[test]
962 fn boolean_nodes_yield_zero_or_one_not_a_count() {
963 let ev = |src: &str, x: f64| eval(&parse(src).unwrap(), x).unwrap();
964 // Both sides of the `or` hold.
965 assert_eq!(ev("x > 1 or x > 2", 5.0), 1.0);
966 assert_eq!(ev("x > 1 or x > 2", 0.0), 0.0);
967 // Exactly one side holds — the case that was already right.
968 assert_eq!(ev("x > 4 or x < 1", 5.0), 1.0);
969 // Chained `or`, three terms all true.
970 assert_eq!(ev("x > 1 or x > 2 or x > 3", 9.0), 1.0);
971 // A repeated element in an `in` list.
972 assert_eq!(ev("x in [1,1,1]", 1.0), 1.0);
973 assert_eq!(ev("x in [1,5,5,9]", 5.0), 1.0);
974 assert_eq!(ev("x in [1,2,3]", 7.0), 0.0);
975 // A single-element list still answers 0/1.
976 assert_eq!(ev("x in [5]", 5.0), 1.0);
977 }
978
979 /// A parenthesized group is a full expression, not just an additive one.
980 /// `(x > 1) and (x < 5)`, `not (a or b)` and `(cond ? a : b)` are the
981 /// spellings a reader writes first, and each used to be `calc: expected `)``.
982 #[test]
983 fn parentheses_group_a_whole_expression() {
984 let ev = |src: &str, x: f64| eval(&parse(src).unwrap(), x).unwrap();
985 assert_eq!(ev("(x > 1) and (x < 5)", 3.0), 1.0);
986 assert_eq!(ev("(x > 1) and (x < 5)", 9.0), 0.0);
987 assert_eq!(ev("not (x > 1 or x > 2)", 5.0), 0.0);
988 assert_eq!(ev("not (x > 1 or x > 2)", 0.0), 1.0);
989 assert_eq!(ev("(x > 5 ? 100 : 0)", 9.0), 100.0);
990 assert_eq!(ev("(x > 5 ? 100 : 0)", 1.0), 0.0);
991 // Arithmetic grouping is unchanged.
992 assert_eq!(ev("(x + 2) * 3", 1.0), 9.0);
993 assert_eq!(ev("x - (2 - 1)", 5.0), 4.0);
994 assert_eq!(ev("((x))", 7.0), 7.0);
995 }
996
997 #[test]
998 fn fractional_bound_still_a_number_not_a_control() {
999 // `.5` stays a number; only `.<letter>` is a control ref.
1000 assert!(matches!(
1001 parse("x + .5").unwrap(),
1002 Expr::Bin(BinOp::Add, _, _)
1003 ));
1004 }
1005}