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};
15
16#[derive(Debug, Clone, Copy)]
17pub enum BinOp {
18    Add,
19    Sub,
20    Mul,
21    Div,
22    Mod,
23    Eq,
24    Ne,
25    Lt,
26    Le,
27    Gt,
28    Ge,
29    /// Logical `and`/`or` over truthiness (each operand normalized to 0/1).
30    And,
31    Or,
32}
33
34#[derive(Debug, Clone)]
35pub enum Expr {
36    Num(f64),
37    /// The pipeline input scalar.
38    Var,
39    /// A named field of the current record, resolved at eval time.
40    Field(String),
41    /// A live control reference (`.th` — an `input`/control widget's value),
42    /// written `.name` in a predicate. `resolve_pipeline` substitutes it with a
43    /// `Num` before eval when the control holds a number; unresolved -> NaN.
44    Control(String),
45    /// A string literal — only produced by substituting a string control.
46    Str(String),
47    /// `match(.q)` — substring test of the whole line against a control's text.
48    /// Evaluated Rust-side (not on the numeric VM); empty control -> matches all.
49    Match(Box<Expr>),
50    /// `<field> in .lv` — set membership: keep lines whose FIELD value is in the
51    /// control's comma-separated selected set. Empty set -> matches all.
52    InSet(String, Box<Expr>),
53    Neg(Box<Expr>),
54    /// Logical negation: truthy input -> 0, falsy -> 1.
55    Not(Box<Expr>),
56    /// `name(arg, …)` — a call to an inline-Rust FFI export registered by a
57    /// `rust { ... }` block. Numeric-only: each arg is evaluated to an f64 and
58    /// marshaled as a `fusevm::Value::float`; the export's return is read back as
59    /// an f64. An unregistered name (or a failed call) evaluates to NaN, so a
60    /// comparison against it is simply false.
61    Call(String, Vec<Expr>),
62    /// Membership: `left in [a, b, c]` — truthy iff `left` equals any element
63    /// (jq `IN`). Empty list is always falsy.
64    InList(Box<Expr>, Vec<Expr>),
65    /// Range membership: `left in lo..hi` — truthy iff `lo <= left <= hi`.
66    InRange(Box<Expr>, Box<Expr>, Box<Expr>),
67    /// Ternary `cond ? then : else` — only the taken branch is evaluated (real
68    /// fusevm branching), so a guarded `x != 0 ? 100/x : 0` never divides by 0.
69    Cond(Box<Expr>, Box<Expr>, Box<Expr>),
70    Bin(BinOp, Box<Expr>, Box<Expr>),
71}
72
73/// Parse an expression: numbers, `x`, `+ - * / %`, comparisons
74/// (`== != < <= > >=`), unary `-`, and parentheses.
75pub fn parse(src: &str) -> Result<Expr, String> {
76    let mut p = Parser {
77        c: src.chars().collect(),
78        i: 0,
79        depth: 0,
80    };
81    let e = p.ternary()?;
82    if p.peek().is_some() {
83        return Err(format!("calc: unexpected `{}`", p.c[p.i]));
84    }
85    Ok(e)
86}
87
88/// Evaluate as a number with no field resolver (field refs -> NaN).
89pub fn eval(e: &Expr, x: f64) -> Result<f64, String> {
90    eval_ctx(e, x, &|_| f64::NAN)
91}
92
93/// Collect the names of every `Control` reference in `e` (e.g. `.th` -> "th").
94pub fn control_names(e: &Expr, out: &mut Vec<String>) {
95    match e {
96        Expr::Control(n) => out.push(n.clone()),
97        Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => {}
98        Expr::Neg(a) | Expr::Not(a) | Expr::Match(a) | Expr::InSet(_, a) => control_names(a, out),
99        Expr::Call(_, items) => items.iter().for_each(|it| control_names(it, out)),
100        Expr::InList(l, items) => {
101            control_names(l, out);
102            items.iter().for_each(|it| control_names(it, out));
103        }
104        Expr::InRange(l, lo, hi) => {
105            control_names(l, out);
106            control_names(lo, out);
107            control_names(hi, out);
108        }
109        Expr::Cond(a, b, c) => {
110            control_names(a, out);
111            control_names(b, out);
112            control_names(c, out);
113        }
114        Expr::Bin(_, a, b) => {
115            control_names(a, out);
116            control_names(b, out);
117        }
118    }
119}
120
121/// Split control refs by the type they resolve to: `Match`/`InSet` inners are
122/// string controls, everything else is numeric. Lets `resolve_pipeline` require
123/// numeric controls to resolve (or drop the filter) while string controls with
124/// an empty value simply match everything.
125pub fn control_names_typed(e: &Expr, num: &mut Vec<String>, strv: &mut Vec<String>) {
126    match e {
127        Expr::Control(n) => num.push(n.clone()),
128        Expr::Match(inner) | Expr::InSet(_, inner) => {
129            if let Expr::Control(n) = inner.as_ref() {
130                strv.push(n.clone());
131            } else {
132                control_names_typed(inner, num, strv);
133            }
134        }
135        Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => {}
136        Expr::Neg(a) | Expr::Not(a) => control_names_typed(a, num, strv),
137        Expr::Call(_, items) => items
138            .iter()
139            .for_each(|it| control_names_typed(it, num, strv)),
140        Expr::InList(l, items) => {
141            control_names_typed(l, num, strv);
142            items
143                .iter()
144                .for_each(|it| control_names_typed(it, num, strv));
145        }
146        Expr::InRange(l, lo, hi) => {
147            control_names_typed(l, num, strv);
148            control_names_typed(lo, num, strv);
149            control_names_typed(hi, num, strv);
150        }
151        Expr::Cond(a, b, c) => {
152            control_names_typed(a, num, strv);
153            control_names_typed(b, num, strv);
154            control_names_typed(c, num, strv);
155        }
156        Expr::Bin(_, a, b) => {
157            control_names_typed(a, num, strv);
158            control_names_typed(b, num, strv);
159        }
160    }
161}
162
163/// Whether `e` contains a string predicate (`match`/`in .set`) — the query layer
164/// routes such a `where` to the Rust evaluator instead of the numeric VM.
165pub fn expr_has_str(e: &Expr) -> bool {
166    match e {
167        Expr::Match(_) | Expr::InSet(..) | Expr::Str(_) => true,
168        Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Control(_) => false,
169        Expr::Neg(a) | Expr::Not(a) => expr_has_str(a),
170        // A Call yields an f64; numeric-only args carry no string predicate, but
171        // recurse for consistency with every other compound node.
172        Expr::Call(_, items) => items.iter().any(expr_has_str),
173        Expr::InList(l, items) => expr_has_str(l) || items.iter().any(expr_has_str),
174        Expr::InRange(l, lo, hi) => expr_has_str(l) || expr_has_str(lo) || expr_has_str(hi),
175        Expr::Cond(a, b, c) => expr_has_str(a) || expr_has_str(b) || expr_has_str(c),
176        Expr::Bin(_, a, b) => expr_has_str(a) || expr_has_str(b),
177    }
178}
179
180/// Rewrite every `Control(name)` in `e` to `Control("{ns}.{name}")`, in place —
181/// used by `import X as Y` to namespace a module's control references.
182pub fn prefix_controls(e: &mut Expr, ns: &str) {
183    match e {
184        Expr::Control(n) => *n = format!("{ns}.{n}"),
185        Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => {}
186        Expr::Neg(a) | Expr::Not(a) | Expr::Match(a) | Expr::InSet(_, a) => prefix_controls(a, ns),
187        Expr::Call(_, items) => items.iter_mut().for_each(|it| prefix_controls(it, ns)),
188        Expr::InList(l, items) => {
189            prefix_controls(l, ns);
190            items.iter_mut().for_each(|it| prefix_controls(it, ns));
191        }
192        Expr::InRange(l, lo, hi) => {
193            prefix_controls(l, ns);
194            prefix_controls(lo, ns);
195            prefix_controls(hi, ns);
196        }
197        Expr::Cond(a, b, c) => {
198            prefix_controls(a, ns);
199            prefix_controls(b, ns);
200            prefix_controls(c, ns);
201        }
202        Expr::Bin(_, a, b) => {
203            prefix_controls(a, ns);
204            prefix_controls(b, ns);
205        }
206    }
207}
208
209/// Return a copy of `e` with control refs substituted: a numeric `Control` ->
210/// `Num(num(n))` when resolvable (else left as-is -> NaN); a string control
211/// inside `match`/`in .set` -> `Str(strv(n))` (empty when unset -> matches all).
212pub fn substitute_controls(
213    e: &Expr,
214    num: &dyn Fn(&str) -> Option<f64>,
215    strv: &dyn Fn(&str) -> Option<String>,
216) -> Expr {
217    let sub = |b: &Expr| Box::new(substitute_controls(b, num, strv));
218    // Resolve a control ref to a string node (for match/in-set inners).
219    let sub_str = |b: &Expr| -> Box<Expr> {
220        match b {
221            Expr::Control(n) => Box::new(Expr::Str(strv(n).unwrap_or_default())),
222            other => Box::new(substitute_controls(other, num, strv)),
223        }
224    };
225    match e {
226        Expr::Control(n) => match num(n) {
227            Some(v) => Expr::Num(v),
228            None => Expr::Control(n.clone()),
229        },
230        Expr::Match(inner) => Expr::Match(sub_str(inner)),
231        Expr::InSet(field, inner) => Expr::InSet(field.clone(), sub_str(inner)),
232        Expr::Num(_) | Expr::Var | Expr::Field(_) | Expr::Str(_) => e.clone(),
233        Expr::Call(name, items) => Expr::Call(
234            name.clone(),
235            items
236                .iter()
237                .map(|it| substitute_controls(it, num, strv))
238                .collect(),
239        ),
240        Expr::Neg(a) => Expr::Neg(sub(a)),
241        Expr::Not(a) => Expr::Not(sub(a)),
242        Expr::InList(l, items) => Expr::InList(
243            sub(l),
244            items
245                .iter()
246                .map(|it| substitute_controls(it, num, strv))
247                .collect(),
248        ),
249        Expr::InRange(l, lo, hi) => Expr::InRange(sub(l), sub(lo), sub(hi)),
250        Expr::Cond(a, b, c) => Expr::Cond(sub(a), sub(b), sub(c)),
251        Expr::Bin(op, a, b) => Expr::Bin(*op, sub(a), sub(b)),
252    }
253}
254
255/// Arm fusevm's Cranelift tiers on a VM about to run an expression chunk.
256///
257/// One flag gates both tiers: `vm.rs`'s tiered auto-dispatch checks
258/// `tracing_jit` before it will even ask `is_block_eligible`, so without this
259/// call a chunk runs on the interpreter no matter what the `jit` feature says.
260/// An arb expression lowers to straight-line native ops with no backward
261/// branch, so the block tier is the one that takes it — compiled once, then
262/// reused from fusevm's on-disk cache across runs, which is what a predicate
263/// evaluated over every row wants. `arb --tiers` reports the outcome.
264fn arm_tiers(vm: &mut VM) {
265    vm.enable_tracing_jit();
266}
267
268/// Lower `e` to a fusevm chunk (with `x` and resolved fields baked in), run it on
269/// the VM, and return the resulting number. `resolve` maps a field name to its
270/// numeric value.
271pub fn eval_ctx(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64) -> Result<f64, String> {
272    let mut b = ChunkBuilder::new();
273    emit(e, x, resolve, &mut b);
274    let mut vm = VM::new(b.build());
275    arm_tiers(&mut vm);
276    match vm.run() {
277        VMResult::Ok(v) => Ok(v.to_float()),
278        VMResult::Halted => Ok(vm.peek().to_float()),
279        VMResult::Error(err) => Err(err),
280    }
281}
282
283/// Lower `e` to the fusevm chunk [`eval_ctx`] would run, without running it.
284///
285/// The chunk is a function of `x` and the resolved fields, not of `e` alone:
286/// both are baked in as `LoadFloat` constants (see [`emit`]). Two evaluations
287/// of the same expression at different `x` are therefore *different* chunks
288/// with different op hashes, which is what [`crate::tiers`] exists to report on.
289pub fn chunk_of(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64) -> fusevm::Chunk {
290    let mut b = ChunkBuilder::new();
291    emit(e, x, resolve, &mut b);
292    b.build()
293}
294
295/// Evaluate as a predicate with no field resolver.
296pub fn eval_pred(e: &Expr, x: f64) -> Result<bool, String> {
297    eval_pred_ctx(e, x, &|_| f64::NAN)
298}
299
300/// Evaluate `e` as a predicate — compiled to fusevm, run on the VM, read as a
301/// boolean via `Value::is_truthy`. `resolve` maps a field name to its value.
302pub fn eval_pred_ctx(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64) -> Result<bool, String> {
303    let mut b = ChunkBuilder::new();
304    emit(e, x, resolve, &mut b);
305    let mut vm = VM::new(b.build());
306    arm_tiers(&mut vm);
307    match vm.run() {
308        VMResult::Ok(v) => Ok(v.is_truthy()),
309        VMResult::Halted => Ok(vm.peek().is_truthy()),
310        VMResult::Error(err) => Err(err),
311    }
312}
313
314/// Evaluate a `name(args)` inline-Rust FFI call at lowering time: resolve each
315/// argument to an f64 on the same VM, marshal it as a `fusevm::Value::float`
316/// (fusevm coerces to the export's `i64`/`f64` signature), dispatch to the
317/// registered export, and read the return back as an f64. An unregistered name
318/// or a failed call yields NaN — the same way an unresolved control degrades —
319/// so the emitter can bake the result in as a constant without a fallible path.
320fn eval_call(name: &str, args: &[Expr], x: f64, resolve: &dyn Fn(&str) -> f64) -> f64 {
321    if !fusevm::ffi::is_registered(name) {
322        return f64::NAN;
323    }
324    let vals: Vec<Value> = args
325        .iter()
326        .map(|a| Value::float(eval_ctx(a, x, resolve).unwrap_or(f64::NAN)))
327        .collect();
328    match fusevm::ffi::try_call(name, &vals) {
329        Some(Ok(v)) => v.to_float(),
330        _ => f64::NAN,
331    }
332}
333
334fn emit(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64, b: &mut ChunkBuilder) {
335    match e {
336        Expr::Num(n) => {
337            b.emit(Op::LoadFloat(*n), 0);
338        }
339        Expr::Var => {
340            b.emit(Op::LoadFloat(x), 0);
341        }
342        Expr::Field(name) => {
343            b.emit(Op::LoadFloat(resolve(name)), 0);
344        }
345        // An unsubstituted control (its value was empty/non-numeric) -> NaN, so
346        // comparisons against it are false. Normally resolve_pipeline replaces it
347        // with a Num, or drops the whole `where` op, before we get here.
348        Expr::Control(_) => {
349            b.emit(Op::LoadFloat(f64::NAN), 0);
350        }
351        // String predicates never reach the numeric VM — the query layer routes a
352        // string-bearing `where` to a Rust evaluator. Emit a neutral 0 so any
353        // stray numeric use degrades gracefully instead of panicking.
354        Expr::Str(_) | Expr::Match(_) | Expr::InSet(..) => {
355            b.emit(Op::LoadFloat(0.0), 0);
356        }
357        // An FFI call can't run inside fusevm bytecode, so evaluate it now and
358        // bake the resulting f64 in as a constant.
359        Expr::Call(name, args) => {
360            b.emit(Op::LoadFloat(eval_call(name, args, x, resolve)), 0);
361        }
362        Expr::Neg(a) => {
363            emit(a, x, resolve, b);
364            b.emit(Op::Negate, 0);
365        }
366        Expr::Not(a) => {
367            // Logical not: `a == 0` yields 1 for falsy `a`, 0 for truthy.
368            emit(a, x, resolve, b);
369            b.emit(Op::LoadFloat(0.0), 0);
370            b.emit(Op::NumEq, 0);
371        }
372        Expr::InList(left, items) => {
373            // Sum of `(left == item)` over the list; truthy iff any matched.
374            if items.is_empty() {
375                b.emit(Op::LoadFloat(0.0), 0);
376            } else {
377                for (k, it) in items.iter().enumerate() {
378                    emit(left, x, resolve, b);
379                    emit(it, x, resolve, b);
380                    b.emit(Op::NumEq, 0);
381                    if k > 0 {
382                        b.emit(Op::Add, 0);
383                    }
384                }
385            }
386        }
387        Expr::InRange(left, lo, hi) => {
388            // `(left >= lo) and (left <= hi)` — both yield 0/1, product is 1 iff
389            // in range.
390            emit(left, x, resolve, b);
391            emit(lo, x, resolve, b);
392            b.emit(Op::NumGe, 0);
393            emit(left, x, resolve, b);
394            emit(hi, x, resolve, b);
395            b.emit(Op::NumLe, 0);
396            b.emit(Op::Mul, 0);
397        }
398        Expr::Cond(c, t, e2) => {
399            // Real branching: `JumpIfFalse` pops the condition and skips to the
400            // else branch when falsy, so only the taken branch runs.
401            emit(c, x, resolve, b);
402            let jf = b.emit(Op::JumpIfFalse(0), 0);
403            emit(t, x, resolve, b);
404            let jend = b.emit(Op::Jump(0), 0);
405            let else_pos = b.current_pos();
406            b.patch_jump(jf, else_pos);
407            emit(e2, x, resolve, b);
408            let end_pos = b.current_pos();
409            b.patch_jump(jend, end_pos);
410        }
411        // `and`/`or` operate on truthiness: normalize each side to 0/1 first,
412        // then `and` = product (1 iff both 1), `or` = sum (>=1 iff either 1).
413        Expr::Bin(BinOp::And, a, c) => {
414            emit_bool(a, x, resolve, b);
415            emit_bool(c, x, resolve, b);
416            b.emit(Op::Mul, 0);
417        }
418        Expr::Bin(BinOp::Or, a, c) => {
419            emit_bool(a, x, resolve, b);
420            emit_bool(c, x, resolve, b);
421            b.emit(Op::Add, 0);
422        }
423        Expr::Bin(op, a, c) => {
424            emit(a, x, resolve, b);
425            emit(c, x, resolve, b);
426            b.emit(
427                match op {
428                    BinOp::Add => Op::Add,
429                    BinOp::Sub => Op::Sub,
430                    BinOp::Mul => Op::Mul,
431                    BinOp::Div => Op::Div,
432                    BinOp::Mod => Op::Mod,
433                    BinOp::Eq => Op::NumEq,
434                    BinOp::Ne => Op::NumNe,
435                    BinOp::Lt => Op::NumLt,
436                    BinOp::Le => Op::NumLe,
437                    BinOp::Gt => Op::NumGt,
438                    BinOp::Ge => Op::NumGe,
439                    BinOp::And | BinOp::Or => unreachable!("handled above"),
440                },
441                0,
442            );
443        }
444    }
445}
446
447/// Emit `e` normalized to a boolean 0.0/1.0 (`e != 0`), for logical combinators.
448fn emit_bool(e: &Expr, x: f64, resolve: &dyn Fn(&str) -> f64, b: &mut ChunkBuilder) {
449    emit(e, x, resolve, b);
450    b.emit(Op::LoadFloat(0.0), 0);
451    b.emit(Op::NumNe, 0);
452}
453
454struct Parser {
455    c: Vec<char>,
456    i: usize,
457    /// Recursion depth of `primary()`, so a pathologically nested expression
458    /// (`(((…x…)))`) fails closed instead of overflowing the stack.
459    depth: usize,
460}
461
462/// Cap on `(`-nesting in `map`/`where`/`calc` expressions — well past any real
463/// expression, but bounded so a malicious input can't abort the process.
464const MAX_EXPR_DEPTH: usize = 256;
465
466impl Parser {
467    /// Peek the next non-whitespace char (consuming leading whitespace).
468    fn peek(&mut self) -> Option<char> {
469        while self.i < self.c.len() && self.c[self.i].is_whitespace() {
470            self.i += 1;
471        }
472        self.c.get(self.i).copied()
473    }
474
475    /// Lowest precedence: `cond ? then : else` (right-associative).
476    fn ternary(&mut self) -> Result<Expr, String> {
477        let cond = self.or_expr()?;
478        if self.peek() == Some('?') {
479            self.i += 1;
480            let then = self.ternary()?;
481            if self.peek() != Some(':') {
482                return Err("calc: expected `:` in `?:`".into());
483            }
484            self.i += 1;
485            let els = self.ternary()?;
486            return Ok(Expr::Cond(Box::new(cond), Box::new(then), Box::new(els)));
487        }
488        Ok(cond)
489    }
490
491    /// `a or b`.
492    fn or_expr(&mut self) -> Result<Expr, String> {
493        let mut left = self.and_expr()?;
494        while self.match_kw("or") {
495            let right = self.and_expr()?;
496            left = Expr::Bin(BinOp::Or, Box::new(left), Box::new(right));
497        }
498        Ok(left)
499    }
500
501    /// `a and b`, binding tighter than `or`.
502    fn and_expr(&mut self) -> Result<Expr, String> {
503        let mut left = self.not_expr()?;
504        while self.match_kw("and") {
505            let right = self.not_expr()?;
506            left = Expr::Bin(BinOp::And, Box::new(left), Box::new(right));
507        }
508        Ok(left)
509    }
510
511    /// Prefix `not`, binding tighter than `and`/`or` but looser than comparison.
512    fn not_expr(&mut self) -> Result<Expr, String> {
513        if self.match_kw("not") {
514            // `not not … 1` recurses here, never through `primary`, so guard it
515            // too or a long chain overflows the stack (rc=134).
516            self.deepen()?;
517            let inner = self.not_expr();
518            self.depth -= 1;
519            return Ok(Expr::Not(Box::new(inner?)));
520        }
521        self.comparison()
522    }
523
524    /// Consume the keyword `kw` if it is the next whole word (not a prefix of a
525    /// longer identifier, e.g. `and` must not match inside `android`).
526    fn match_kw(&mut self, kw: &str) -> bool {
527        let save = self.i;
528        while self.i < self.c.len() && self.c[self.i].is_whitespace() {
529            self.i += 1;
530        }
531        let start = self.i;
532        let kwc: Vec<char> = kw.chars().collect();
533        let end = start + kwc.len();
534        let boundary_ok =
535            end >= self.c.len() || !(self.c[end].is_ascii_alphanumeric() || self.c[end] == '_');
536        if end <= self.c.len() && self.c[start..end] == kwc[..] && boundary_ok {
537            self.i = end;
538            true
539        } else {
540            self.i = save;
541            false
542        }
543    }
544
545    fn comparison(&mut self) -> Result<Expr, String> {
546        let mut left = self.additive()?;
547        if self.match_kw("in") {
548            return self.in_list(left);
549        }
550        while let Some(op) = self.cmp_op() {
551            let right = self.additive()?;
552            left = Expr::Bin(op, Box::new(left), Box::new(right));
553        }
554        Ok(left)
555    }
556
557    /// Parse a `.name` control reference into `Expr::Control(name)`.
558    fn control_ref(&mut self) -> Result<Expr, String> {
559        if self.peek() != Some('.') {
560            return Err("expected a control ref `.name`".into());
561        }
562        self.i += 1; // consume '.'
563        let name = self.dotted_ident();
564        if name.is_empty() {
565            return Err("expected a control name after `.`".into());
566        }
567        Ok(Expr::Control(name))
568    }
569
570    /// Parse the right-hand side of an `in` test: a `.name` control set, a
571    /// `[a, b, c]` list, or a `lo..hi` range.
572    fn in_list(&mut self, left: Expr) -> Result<Expr, String> {
573        // `<field> in .lv` — set membership against a live control's selected set.
574        // Only a `.`+letter is a control ref; `.5` stays a fractional range bound.
575        if self.peek() == Some('.')
576            && matches!(self.c.get(self.i + 1), Some(c) if c.is_ascii_alphabetic() || *c == '_')
577        {
578            let field = match &left {
579                Expr::Field(n) => n.clone(),
580                Expr::Var => "x".to_string(),
581                _ => return Err("in .set: left side must be a field".into()),
582            };
583            let ctrl = self.control_ref()?;
584            return Ok(Expr::InSet(field, Box::new(ctrl)));
585        }
586        if self.peek() != Some('[') {
587            // `lo..hi` range membership.
588            let lo = self.additive()?;
589            if !(self.peek() == Some('.') && self.c.get(self.i + 1) == Some(&'.')) {
590                return Err("in: expected `[list]` or `lo..hi`".into());
591            }
592            self.i += 2;
593            let hi = self.additive()?;
594            return Ok(Expr::InRange(Box::new(left), Box::new(lo), Box::new(hi)));
595        }
596        self.i += 1;
597        let mut items = Vec::new();
598        loop {
599            if self.peek() == Some(']') {
600                self.i += 1;
601                break;
602            }
603            items.push(self.additive()?);
604            match self.peek() {
605                Some(',') => self.i += 1,
606                Some(']') => {
607                    self.i += 1;
608                    break;
609                }
610                _ => return Err("in: expected `,` or `]`".into()),
611            }
612        }
613        Ok(Expr::InList(Box::new(left), items))
614    }
615
616    /// Consume a comparison operator (`< <= > >= == !=`) if one is next.
617    fn cmp_op(&mut self) -> Option<BinOp> {
618        let c = self.peek()?;
619        if !matches!(c, '<' | '>' | '=' | '!') {
620            return None;
621        }
622        let next = self.c.get(self.i + 1).copied();
623        let (op, len) = match (c, next) {
624            ('<', Some('=')) => (BinOp::Le, 2),
625            ('<', _) => (BinOp::Lt, 1),
626            ('>', Some('=')) => (BinOp::Ge, 2),
627            ('>', _) => (BinOp::Gt, 1),
628            ('=', Some('=')) => (BinOp::Eq, 2),
629            ('!', Some('=')) => (BinOp::Ne, 2),
630            _ => return None,
631        };
632        self.i += len;
633        Some(op)
634    }
635
636    fn additive(&mut self) -> Result<Expr, String> {
637        let mut left = self.multiplicative()?;
638        while let Some(c) = self.peek() {
639            let op = match c {
640                '+' => BinOp::Add,
641                '-' => BinOp::Sub,
642                _ => break,
643            };
644            self.i += 1;
645            let right = self.multiplicative()?;
646            left = Expr::Bin(op, Box::new(left), Box::new(right));
647        }
648        Ok(left)
649    }
650
651    fn multiplicative(&mut self) -> Result<Expr, String> {
652        let mut left = self.unary()?;
653        while let Some(c) = self.peek() {
654            let op = match c {
655                '*' => BinOp::Mul,
656                '/' => BinOp::Div,
657                '%' => BinOp::Mod,
658                _ => break,
659            };
660            self.i += 1;
661            let right = self.unary()?;
662            left = Expr::Bin(op, Box::new(left), Box::new(right));
663        }
664        Ok(left)
665    }
666
667    fn unary(&mut self) -> Result<Expr, String> {
668        if self.peek() == Some('-') {
669            self.i += 1;
670            // `- - … 1` recurses here, never through `primary`; guard it too.
671            self.deepen()?;
672            let inner = self.unary();
673            self.depth -= 1;
674            return Ok(Expr::Neg(Box::new(inner?)));
675        }
676        self.primary()
677    }
678
679    /// Enter one recursion level, failing closed if it exceeds `MAX_EXPR_DEPTH`
680    /// (decrementing itself on that error). Every self-recursive parse point —
681    /// `primary` (paren nesting), `not_expr`, `unary` — calls this then does
682    /// `self.depth -= 1` after its recursive call, so adversarial input errors
683    /// instead of overflowing the stack.
684    fn deepen(&mut self) -> Result<(), String> {
685        self.depth += 1;
686        if self.depth > MAX_EXPR_DEPTH {
687            self.depth -= 1;
688            return Err("calc: expression too deeply nested".into());
689        }
690        Ok(())
691    }
692
693    fn primary(&mut self) -> Result<Expr, String> {
694        self.deepen()?;
695        let r = self.primary_inner();
696        self.depth -= 1;
697        r
698    }
699
700    fn primary_inner(&mut self) -> Result<Expr, String> {
701        match self.peek() {
702            Some('(') => {
703                self.i += 1;
704                let e = self.additive()?;
705                if self.peek() != Some(')') {
706                    return Err("calc: expected `)`".into());
707                }
708                self.i += 1;
709                Ok(e)
710            }
711            Some(c) if c.is_ascii_alphabetic() || c == '_' => {
712                let name = self.ident();
713                // `match(.q)` — a builtin substring test against a control string.
714                if name == "match" && self.peek() == Some('(') {
715                    self.i += 1; // consume '('
716                    let inner = self.control_ref()?;
717                    if self.peek() != Some(')') {
718                        return Err("match: expected `)`".into());
719                    }
720                    self.i += 1;
721                    return Ok(Expr::Match(Box::new(inner)));
722                }
723                // `name(arg, …)` — an inline-Rust FFI call. Any other identifier
724                // immediately followed by `(` was previously a parse error, so
725                // this grammar addition is purely additive.
726                if self.peek() == Some('(') {
727                    return self.call(name);
728                }
729                Ok(if name == "x" {
730                    Expr::Var
731                } else {
732                    Expr::Field(name)
733                })
734            }
735            // `.name` is a control reference (a live widget value); `.5` stays a
736            // number. Distinguish by whether the char after `.` is a letter.
737            Some('.') if matches!(self.c.get(self.i + 1), Some(c) if c.is_ascii_alphabetic() || *c == '_') =>
738            {
739                self.i += 1; // consume the leading `.`
740                Ok(Expr::Control(self.dotted_ident()))
741            }
742            Some(c) if c.is_ascii_digit() || c == '.' => self.number(),
743            Some(c) => Err(format!("calc: unexpected `{c}`")),
744            None => Err("calc: unexpected end of expression".into()),
745        }
746    }
747
748    fn ident(&mut self) -> String {
749        let start = self.i;
750        while self.i < self.c.len()
751            && (self.c[self.i].is_ascii_alphanumeric() || self.c[self.i] == '_')
752        {
753            self.i += 1;
754        }
755        self.c[start..self.i].iter().collect()
756    }
757
758    /// A control name that may be dot-segmented (`ps.sel`, `g.cpu`): the leading
759    /// ident, then any `.segment` where the char after the `.` is a letter/`_` (so
760    /// `.5` fractional bounds and `..` ranges are left alone). Enables the
761    /// `.<widget>.sel` selection accessor (SPEC §14) as a live control ref.
762    fn dotted_ident(&mut self) -> String {
763        let mut name = self.ident();
764        while self.i < self.c.len()
765            && self.c[self.i] == '.'
766            && matches!(self.c.get(self.i + 1), Some(c) if c.is_ascii_alphabetic() || *c == '_')
767        {
768            self.i += 1; // consume '.'
769            name.push('.');
770            name.push_str(&self.ident());
771        }
772        name
773    }
774
775    /// Parse the argument list of a `name(arg, …)` FFI call — the leading `(` is
776    /// the next char. Each argument is a full expression; `,` separates and `)`
777    /// closes. A zero-arg call `name()` is allowed.
778    fn call(&mut self, name: String) -> Result<Expr, String> {
779        self.i += 1; // consume '('
780        let mut args = Vec::new();
781        if self.peek() != Some(')') {
782            loop {
783                args.push(self.ternary()?);
784                match self.peek() {
785                    Some(',') => self.i += 1,
786                    Some(')') => break,
787                    _ => return Err(format!("calc: expected `,` or `)` in call to `{name}`")),
788                }
789            }
790        }
791        self.i += 1; // consume ')'
792        Ok(Expr::Call(name, args))
793    }
794
795    fn number(&mut self) -> Result<Expr, String> {
796        let start = self.i;
797        while self.i < self.c.len() && self.c[self.i].is_ascii_digit() {
798            self.i += 1;
799        }
800        // At most one fractional part, and only when the `.` is followed by a
801        // digit — so `1..10` (a range) leaves the `..` for the range parser
802        // instead of the number greedily swallowing both dots.
803        if self.i < self.c.len()
804            && self.c[self.i] == '.'
805            && matches!(self.c.get(self.i + 1), Some(d) if d.is_ascii_digit())
806        {
807            self.i += 1;
808            while self.i < self.c.len() && self.c[self.i].is_ascii_digit() {
809                self.i += 1;
810            }
811        }
812        let s: String = self.c[start..self.i].iter().collect();
813        s.parse::<f64>()
814            .map(Expr::Num)
815            .map_err(|_| format!("calc: bad number `{s}`"))
816    }
817}
818
819#[cfg(test)]
820mod tests {
821    use super::*;
822
823    #[test]
824    fn dotted_control_name_parses_whole() {
825        // `.ps.sel` (a widget's selection accessor) is one control ref, not
826        // `.ps` followed by a stray `.sel`.
827        let e = parse(".ps.sel").unwrap();
828        let mut names = Vec::new();
829        control_names(&e, &mut names);
830        assert_eq!(names, vec!["ps.sel".to_string()]);
831    }
832
833    #[test]
834    fn dotted_control_substitutes_and_evals() {
835        // `.k.v * 2` with the control resolved to 21 -> 42.
836        let e = parse(".k.v * 2").unwrap();
837        let num = |n: &str| if n == "k.v" { Some(21.0) } else { None };
838        let strv = |_: &str| None;
839        let sub = substitute_controls(&e, &num, &strv);
840        assert_eq!(eval(&sub, 0.0).unwrap(), 42.0);
841    }
842
843    #[test]
844    fn fractional_bound_still_a_number_not_a_control() {
845        // `.5` stays a number; only `.<letter>` is a control ref.
846        assert!(matches!(
847            parse("x + .5").unwrap(),
848            Expr::Bin(BinOp::Add, _, _)
849        ));
850    }
851}