Skip to main content

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}