symbios_shape/

expr.rs

//! Arithmetic / logical expression language for grammar arguments.
//!
//! Every numeric argument position in the grammar (extrusion heights, split
//! sizes, scale factors, roof parameters, …) accepts an expression instead of
//! a bare literal. Expressions are evaluated at derivation time against the
//! current shape's [`EvalCtx`] — its scope extents, split position, depth,
//! bound rule parameters, and grammar attributes — so one rule adapts to
//! every scope it is applied to.
//!
//! ```text
//! Extrude(rand(8, 14))
//! Split(Y) { FloorH: Ground | ~1: Upper }          // FloorH = const/attr
//! Scale(scope.x * 0.5, 1, 1)
//! when(split.i == 0): CornerBay | else: MidBay
//! ```
//!
//! Design notes:
//! - **Floats only.** Booleans are CGA-style floats: comparisons yield `1.0` /
//!   `0.0`, and any non-zero value is truthy. This keeps one value type
//!   through parameters, attributes, and genetics.
//! - **Deterministic randomness.** `rand(..)` draws from the per-shape RNG
//!   stream supplied by the interpreter, so the same seed derives the same
//!   model. Short-circuit `&&` / `||` skip RHS draws by design — divergence
//!   is data-driven and reproducible.
//! - **Hard failure over silent nonsense.** Division by zero, non-finite
//!   results, unknown identifiers, and bad function domains all return
//!   [`ShapeError`] rather than propagating NaNs into scope math.

use std::collections::HashMap;
use std::fmt;

use nom::{
    IResult, Parser,
    bytes::complete::tag,
    character::complete::char as c_char,
    combinator::verify,
    error::{Error, ErrorKind},
    number::complete::double,
};
use rand::Rng;
use rand_pcg::Pcg64;
use serde::{Deserialize, Serialize};

use crate::error::ShapeError;
use crate::grammar::{identifier, space_or_comment};
use crate::scope::Vec3;

/// Maximum number of AST nodes in a single expression (DoS hardening).
/// Checked after parsing via [`Expr::node_count`]; grammar-level integration
/// rejects any argument expression exceeding this.
pub const MAX_EXPR_NODES: usize = 512;
/// Maximum parenthesis/recursion depth inside one expression. Bounds nom's
/// recursion during parsing (a `((((…))))` bomb would otherwise overflow the
/// stack long before node counting runs).
pub const MAX_EXPR_DEPTH: usize = 64;

// ── AST ──────────────────────────────────────────────────────────────────────

/// Built-in read-only variables.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum Var {
    /// Current scope extent along local X (`scope.x`).
    ScopeX,
    /// Current scope extent along local Y (`scope.y`).
    ScopeY,
    /// Current scope extent along local Z (`scope.z`).
    ScopeZ,
    /// Zero-based index of this shape within the last `Split` / `Repeat`
    /// (`split.i`). `0` outside any split.
    SplitI,
    /// Total sibling count of the last `Split` / `Repeat` (`split.n`).
    /// `1` outside any split.
    SplitN,
    /// Current derivation depth (`depth`); the root rule runs at `0`.
    Depth,
    /// A named binding: rule parameter, grammar attribute, or constant —
    /// resolved in that order at evaluation time.
    Named(String),
}

/// Unary operators.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum UnaryOp {
    /// Arithmetic negation `-x`.
    Neg,
    /// Logical not `!x` (`1.0` if `x == 0.0`, else `0.0`).
    Not,
}

/// Binary operators, lowest section = lowest precedence.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum BinOp {
    Add,
    Sub,
    Mul,
    Div,
    /// Remainder (`%`). Follows Rust `f64::rem` semantics (sign of dividend).
    Rem,
    Eq,
    Ne,
    Lt,
    Le,
    Gt,
    Ge,
    /// Logical and — short-circuits: RHS is not evaluated when LHS is falsy.
    And,
    /// Logical or — short-circuits: RHS is not evaluated when LHS is truthy.
    Or,
}

/// Built-in functions.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum Func {
    /// `rand()` → `[0,1)`, `rand(max)` → `[0,max)`, `rand(min,max)` → `[min,max)`.
    /// Draws from the per-shape RNG stream (deterministic per seed).
    Rand,
    Floor,
    Ceil,
    /// Round half-to-even (banker's rounding), CGA `rint` parity.
    Rint,
    Abs,
    Sqrt,
    Pow,
    /// `clamp(v, lo, hi)`; errors when `lo > hi`.
    Clamp,
    Min,
    Max,
}

impl Func {
    /// `(name, func, min_arity, max_arity)` table shared by parser and eval.
    const TABLE: [(&'static str, Func, usize, usize); 10] = [
        ("rand", Func::Rand, 0, 2),
        ("floor", Func::Floor, 1, 1),
        ("ceil", Func::Ceil, 1, 1),
        ("rint", Func::Rint, 1, 1),
        ("abs", Func::Abs, 1, 1),
        ("sqrt", Func::Sqrt, 1, 1),
        ("pow", Func::Pow, 2, 2),
        ("clamp", Func::Clamp, 3, 3),
        ("min", Func::Min, 2, 2),
        ("max", Func::Max, 2, 2),
    ];

    fn by_name(name: &str) -> Option<(Func, usize, usize)> {
        Self::TABLE
            .iter()
            .find(|(n, ..)| *n == name)
            .map(|&(_, f, lo, hi)| (f, lo, hi))
    }

    fn name(self) -> &'static str {
        Self::TABLE
            .iter()
            .find(|&&(_, f, ..)| f == self)
            .map(|&(n, ..)| n)
            .unwrap_or("?")
    }
}

/// An argument expression, evaluated per shape at derivation time.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum Expr {
    /// Literal constant. The only node genetics mutates.
    Lit(f64),
    Var(Var),
    Unary(UnaryOp, Box<Expr>),
    Binary(BinOp, Box<Expr>, Box<Expr>),
    Call(Func, Vec<Expr>),
}

impl Expr {
    /// Convenience literal constructor.
    pub fn lit(v: f64) -> Self {
        Expr::Lit(v)
    }

    /// Total AST node count (self included). Used for the
    /// [`MAX_EXPR_NODES`] DoS cap and as a cheap complexity metric.
    pub fn node_count(&self) -> usize {
        match self {
            Expr::Lit(_) | Expr::Var(_) => 1,
            Expr::Unary(_, e) => 1 + e.node_count(),
            Expr::Binary(_, a, b) => 1 + a.node_count() + b.node_count(),
            Expr::Call(_, args) => 1 + args.iter().map(Expr::node_count).sum::<usize>(),
        }
    }

    /// `Some(v)` when the expression is a bare literal. Parse-time range
    /// checks apply only to bare literals; everything else re-validates at
    /// evaluation time.
    pub fn as_lit(&self) -> Option<f64> {
        match self {
            Expr::Lit(v) => Some(*v),
            _ => None,
        }
    }

    /// Visits every literal leaf mutably — the genetics mutation hook.
    pub fn visit_literals_mut(&mut self, f: &mut impl FnMut(&mut f64)) {
        match self {
            Expr::Lit(v) => f(v),
            Expr::Var(_) => {}
            Expr::Unary(_, e) => e.visit_literals_mut(f),
            Expr::Binary(_, a, b) => {
                a.visit_literals_mut(f);
                b.visit_literals_mut(f);
            }
            Expr::Call(_, args) => {
                for a in args {
                    a.visit_literals_mut(f);
                }
            }
        }
    }

    /// Structural equality that ignores literal *values* — two expressions
    /// have the same shape when they differ only in their `Lit` payloads.
    /// Genetics uses this to decide whether two ops are crossover-compatible.
    pub fn shape_eq(&self, other: &Expr) -> bool {
        match (self, other) {
            (Expr::Lit(_), Expr::Lit(_)) => true,
            (Expr::Var(a), Expr::Var(b)) => a == b,
            (Expr::Unary(oa, ea), Expr::Unary(ob, eb)) => oa == ob && ea.shape_eq(eb),
            (Expr::Binary(oa, la, ra), Expr::Binary(ob, lb, rb)) => {
                oa == ob && la.shape_eq(lb) && ra.shape_eq(rb)
            }
            (Expr::Call(fa, aa), Expr::Call(fb, ab)) => {
                fa == fb && aa.len() == ab.len() && aa.iter().zip(ab).all(|(x, y)| x.shape_eq(y))
            }
            _ => false,
        }
    }
}

// ── Evaluation ───────────────────────────────────────────────────────────────

/// Per-shape evaluation context.
///
/// Built by the interpreter for each work item; `params` are the innermost
/// rule-call arguments (linear scan, shadowing `globals`), `globals` the
/// merged attribute/constant table (style and host overrides already applied).
pub struct EvalCtx<'a> {
    /// Current scope extents (`scope.x` / `scope.y` / `scope.z`).
    pub scope_size: Vec3,
    /// Zero-based index within the last split/repeat; `0.0` at the root.
    pub split_i: f64,
    /// Sibling count of the last split/repeat; `1.0` at the root.
    pub split_n: f64,
    /// Derivation depth of the current rule invocation.
    pub depth: f64,
    /// Innermost rule-call parameter bindings; searched *in reverse* so the
    /// latest binding of a repeated name wins.
    pub params: &'a [(String, f64)],
    /// Grammar attributes + constants (merged, overrides applied).
    pub globals: &'a HashMap<String, f64>,
    /// Per-shape RNG stream (`rand(..)` draws).
    pub rng: &'a mut Pcg64,
}

impl Expr {
    /// Evaluates the expression. Any non-finite intermediate or final result
    /// is an error — scope math must stay finite.
    pub fn eval(&self, ctx: &mut EvalCtx<'_>) -> Result<f64, ShapeError> {
        let v = self.eval_inner(ctx)?;
        if !v.is_finite() {
            return Err(ShapeError::ExprEval(format!(
                "expression produced a non-finite value: {self}"
            )));
        }
        Ok(v)
    }

    fn eval_inner(&self, ctx: &mut EvalCtx<'_>) -> Result<f64, ShapeError> {
        Ok(match self {
            Expr::Lit(v) => *v,
            Expr::Var(var) => match var {
                Var::ScopeX => ctx.scope_size.x,
                Var::ScopeY => ctx.scope_size.y,
                Var::ScopeZ => ctx.scope_size.z,
                Var::SplitI => ctx.split_i,
                Var::SplitN => ctx.split_n,
                Var::Depth => ctx.depth,
                Var::Named(name) => {
                    if let Some((_, v)) = ctx.params.iter().rev().find(|(n, _)| n == name) {
                        *v
                    } else if let Some(v) = ctx.globals.get(name) {
                        *v
                    } else {
                        return Err(ShapeError::UnknownIdentifier(name.clone()));
                    }
                }
            },
            Expr::Unary(op, e) => {
                let v = e.eval(ctx)?;
                match op {
                    UnaryOp::Neg => -v,
                    UnaryOp::Not => {
                        if v == 0.0 {
                            1.0
                        } else {
                            0.0
                        }
                    }
                }
            }
            Expr::Binary(op, a, b) => {
                // Short-circuit logicals first — RHS must not evaluate (and
                // must not draw from the RNG) when the LHS already decides.
                match op {
                    BinOp::And => {
                        let l = a.eval(ctx)?;
                        if l == 0.0 {
                            return Ok(0.0);
                        }
                        return Ok(if b.eval(ctx)? != 0.0 { 1.0 } else { 0.0 });
                    }
                    BinOp::Or => {
                        let l = a.eval(ctx)?;
                        if l != 0.0 {
                            return Ok(1.0);
                        }
                        return Ok(if b.eval(ctx)? != 0.0 { 1.0 } else { 0.0 });
                    }
                    _ => {}
                }
                let l = a.eval(ctx)?;
                let r = b.eval(ctx)?;
                let bool_to_f = |b: bool| if b { 1.0 } else { 0.0 };
                match op {
                    BinOp::Add => l + r,
                    BinOp::Sub => l - r,
                    BinOp::Mul => l * r,
                    BinOp::Div => {
                        if r == 0.0 {
                            return Err(ShapeError::ExprEval(format!("division by zero: {self}")));
                        }
                        l / r
                    }
                    BinOp::Rem => {
                        if r == 0.0 {
                            return Err(ShapeError::ExprEval(format!("remainder by zero: {self}")));
                        }
                        l % r
                    }
                    BinOp::Eq => bool_to_f(l == r),
                    BinOp::Ne => bool_to_f(l != r),
                    BinOp::Lt => bool_to_f(l < r),
                    BinOp::Le => bool_to_f(l <= r),
                    BinOp::Gt => bool_to_f(l > r),
                    BinOp::Ge => bool_to_f(l >= r),
                    BinOp::And | BinOp::Or => unreachable!("handled above"),
                }
            }
            Expr::Call(func, args) => {
                match func {
                    Func::Rand => {
                        // Arity fixed at parse time: 0, 1, or 2 args.
                        let (lo, hi) = match args.len() {
                            0 => (0.0, 1.0),
                            1 => (0.0, args[0].eval(ctx)?),
                            _ => (args[0].eval(ctx)?, args[1].eval(ctx)?),
                        };
                        if lo > hi {
                            return Err(ShapeError::ExprEval(format!(
                                "rand range is inverted ({lo} > {hi}): {self}"
                            )));
                        }
                        if lo == hi {
                            lo
                        } else {
                            ctx.rng.random::<f64>() * (hi - lo) + lo
                        }
                    }
                    Func::Floor => args[0].eval(ctx)?.floor(),
                    Func::Ceil => args[0].eval(ctx)?.ceil(),
                    Func::Rint => args[0].eval(ctx)?.round_ties_even(),
                    Func::Abs => args[0].eval(ctx)?.abs(),
                    Func::Sqrt => {
                        let v = args[0].eval(ctx)?;
                        if v < 0.0 {
                            return Err(ShapeError::ExprEval(format!(
                                "sqrt of negative value {v}: {self}"
                            )));
                        }
                        v.sqrt()
                    }
                    Func::Pow => args[0].eval(ctx)?.powf(args[1].eval(ctx)?),
                    Func::Clamp => {
                        let v = args[0].eval(ctx)?;
                        let lo = args[1].eval(ctx)?;
                        let hi = args[2].eval(ctx)?;
                        if lo > hi {
                            return Err(ShapeError::ExprEval(format!(
                                "clamp bounds are inverted ({lo} > {hi}): {self}"
                            )));
                        }
                        v.clamp(lo, hi)
                    }
                    Func::Min => args[0].eval(ctx)?.min(args[1].eval(ctx)?),
                    Func::Max => args[0].eval(ctx)?.max(args[1].eval(ctx)?),
                }
            }
        })
    }
}

// ── Display (diagnostics + round-trip tests) ─────────────────────────────────

impl fmt::Display for Var {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Var::ScopeX => write!(f, "scope.x"),
            Var::ScopeY => write!(f, "scope.y"),
            Var::ScopeZ => write!(f, "scope.z"),
            Var::SplitI => write!(f, "split.i"),
            Var::SplitN => write!(f, "split.n"),
            Var::Depth => write!(f, "depth"),
            Var::Named(n) => write!(f, "{n}"),
        }
    }
}

impl BinOp {
    fn symbol(self) -> &'static str {
        match self {
            BinOp::Add => "+",
            BinOp::Sub => "-",
            BinOp::Mul => "*",
            BinOp::Div => "/",
            BinOp::Rem => "%",
            BinOp::Eq => "==",
            BinOp::Ne => "!=",
            BinOp::Lt => "<",
            BinOp::Le => "<=",
            BinOp::Gt => ">",
            BinOp::Ge => ">=",
            BinOp::And => "&&",
            BinOp::Or => "||",
        }
    }
}

impl fmt::Display for Expr {
    /// Renders with explicit parentheses around every compound node —
    /// unambiguous by construction, at the cost of elegance. Guarantees
    /// `parse(display(e))` reproduces `e` (asserted in tests).
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Expr::Lit(v) => write!(f, "{v}"),
            Expr::Var(v) => write!(f, "{v}"),
            Expr::Unary(UnaryOp::Neg, e) => write!(f, "(-{e})"),
            Expr::Unary(UnaryOp::Not, e) => write!(f, "(!{e})"),
            Expr::Binary(op, a, b) => write!(f, "({a} {} {b})", op.symbol()),
            Expr::Call(func, args) => {
                write!(f, "{}(", func.name())?;
                for (i, a) in args.iter().enumerate() {
                    if i > 0 {
                        write!(f, ", ")?;
                    }
                    write!(f, "{a}")?;
                }
                write!(f, ")")
            }
        }
    }
}

// ── Parser ───────────────────────────────────────────────────────────────────
//
// Precedence (loosest → tightest):
//   or  :=  and ( "||" and )*
//   and :=  cmp ( "&&" cmp )*
//   cmp :=  add ( ("==" | "!=" | "<=" | ">=" | "<" | ">") add )?   — single, non-associative
//   add :=  mul ( ("+" | "-") mul )*
//   mul :=  una ( ("*" | "/" | "%") una )*
//   una :=  "-" una | "!" una | atom
//   atom := number | call | var | "(" or ")"
//
// A comparison chain (`a < b < c`) is rejected: the second `<` is left
// unconsumed and surfaces as trailing input at the integration site.

fn ews<'a, F, O>(inner: F) -> impl Parser<&'a str, Output = O, Error = Error<&'a str>>
where
    F: Parser<&'a str, Output = O, Error = Error<&'a str>>,
{
    nom::sequence::delimited(space_or_comment, inner, space_or_comment)
}

/// A float literal that does NOT consume a leading sign — unary minus is
/// handled at the `una` level so `Scale(3 - 2, 1, 1)` parses as a binary
/// subtraction instead of two adjacent literals.
fn unsigned_double(input: &str) -> IResult<&str, f64> {
    if input.starts_with('-') || input.starts_with('+') {
        return Err(nom::Err::Error(Error::new(input, ErrorKind::Digit)));
    }
    verify(double, |x: &f64| x.is_finite()).parse(input)
}

fn depth_guard(input: &str, depth: usize) -> Result<(), nom::Err<Error<&str>>> {
    if depth > MAX_EXPR_DEPTH {
        Err(nom::Err::Failure(Error::new(input, ErrorKind::TooLarge)))
    } else {
        Ok(())
    }
}

fn parse_atom(input: &str, depth: usize) -> IResult<&str, Expr> {
    depth_guard(input, depth)?;
    // Parenthesised sub-expression.
    if let Ok((rest, _)) = ews(c_char::<_, Error<&str>>('(')).parse(input) {
        let (rest, e) = parse_or(rest, depth + 1)?;
        let (rest, _) = ews(c_char(')')).parse(rest)?;
        return Ok((rest, e));
    }
    // Number literal (sign handled by `parse_unary`).
    if let Ok((rest, v)) = ews(unsigned_double).parse(input) {
        return Ok((rest, Expr::Lit(v)));
    }
    // `scope.x` / `split.i` / `depth` / call / named binding.
    let (rest, name) = ews(identifier).parse(input)?;
    match name {
        "scope" | "split" => {
            let (rest, _) = c_char('.').parse(rest)?;
            let (rest, field) = identifier.parse(rest)?;
            let var = match (name, field) {
                ("scope", "x") => Var::ScopeX,
                ("scope", "y") => Var::ScopeY,
                ("scope", "z") => Var::ScopeZ,
                ("split", "i") => Var::SplitI,
                ("split", "n") => Var::SplitN,
                _ => return Err(nom::Err::Failure(Error::new(rest, ErrorKind::Tag))),
            };
            Ok((rest, Expr::Var(var)))
        }
        "depth" => Ok((rest, Expr::Var(Var::Depth))),
        _ => {
            // Function call when a builtin name is followed by `(`.
            if let Some((func, min_ar, max_ar)) = Func::by_name(name)
                && let Ok((mut rem, _)) = ews(c_char::<_, Error<&str>>('(')).parse(rest)
            {
                let mut args = Vec::new();
                if let Ok((after, _)) = ews(c_char::<_, Error<&str>>(')')).parse(rem) {
                    rem = after;
                } else {
                    loop {
                        let (after_arg, arg) = parse_or(rem, depth + 1)?;
                        args.push(arg);
                        if args.len() > max_ar {
                            return Err(nom::Err::Failure(Error::new(
                                after_arg,
                                ErrorKind::TooLarge,
                            )));
                        }
                        if let Ok((after, _)) = ews(c_char::<_, Error<&str>>(',')).parse(after_arg)
                        {
                            rem = after;
                            continue;
                        }
                        let (after, _) = ews(c_char(')')).parse(after_arg)?;
                        rem = after;
                        break;
                    }
                }
                if args.len() < min_ar || args.len() > max_ar {
                    return Err(nom::Err::Failure(Error::new(rem, ErrorKind::Verify)));
                }
                return Ok((rem, Expr::Call(func, args)));
            }
            Ok((rest, Expr::Var(Var::Named(name.to_string()))))
        }
    }
}

fn parse_unary(input: &str, depth: usize) -> IResult<&str, Expr> {
    depth_guard(input, depth)?;
    if let Ok((rest, _)) = ews(c_char::<_, Error<&str>>('-')).parse(input) {
        let (rest, e) = parse_unary(rest, depth + 1)?;
        // Constant-fold negated literals so `-0.2` IS a literal — parse-time
        // range checks (`as_lit`) and genetics mutation see the signed value.
        if let Expr::Lit(v) = e {
            return Ok((rest, Expr::Lit(-v)));
        }
        return Ok((rest, Expr::Unary(UnaryOp::Neg, Box::new(e))));
    }
    if let Ok((rest, _)) = ews(c_char::<_, Error<&str>>('!')).parse(input) {
        // `!=` must not be half-eaten as unary-not on the RHS of nothing:
        // at this position an operator cannot start, so a following `=` is
        // simply a parse error downstream — no special case needed.
        let (rest, e) = parse_unary(rest, depth + 1)?;
        return Ok((rest, Expr::Unary(UnaryOp::Not, Box::new(e))));
    }
    parse_atom(input, depth)
}

fn parse_mul(input: &str, depth: usize) -> IResult<&str, Expr> {
    let (mut rest, mut acc) = parse_unary(input, depth)?;
    loop {
        let op = if let Ok((r, _)) = ews(c_char::<_, Error<&str>>('*')).parse(rest) {
            (r, BinOp::Mul)
        } else if let Ok((r, _)) = ews(c_char::<_, Error<&str>>('/')).parse(rest) {
            // Guard: `//` and `/*` are comments, not division. space_or_comment
            // inside `ews` already consumed well-formed comments, so a raw `/`
            // followed by `/` or `*` here is a malformed comment — stop.
            if r.starts_with('/') || r.starts_with('*') {
                break;
            }
            (r, BinOp::Div)
        } else if let Ok((r, _)) = ews(c_char::<_, Error<&str>>('%')).parse(rest) {
            (r, BinOp::Rem)
        } else {
            break;
        };
        let (r2, rhs) = parse_unary(op.0, depth + 1)?;
        acc = Expr::Binary(op.1, Box::new(acc), Box::new(rhs));
        rest = r2;
    }
    Ok((rest, acc))
}

fn parse_add(input: &str, depth: usize) -> IResult<&str, Expr> {
    let (mut rest, mut acc) = parse_mul(input, depth)?;
    loop {
        let op = if let Ok((r, _)) = ews(c_char::<_, Error<&str>>('+')).parse(rest) {
            (r, BinOp::Add)
        } else if let Ok((r, _)) = ews(c_char::<_, Error<&str>>('-')).parse(rest) {
            // `-->` is the rule arrow; never treat it as subtraction. This
            // matters once guards parse expressions directly after a rule head.
            if r.starts_with('-') || r.starts_with('>') {
                break;
            }
            (r, BinOp::Sub)
        } else {
            break;
        };
        let (r2, rhs) = parse_mul(op.0, depth + 1)?;
        acc = Expr::Binary(op.1, Box::new(acc), Box::new(rhs));
        rest = r2;
    }
    Ok((rest, acc))
}

fn parse_cmp(input: &str, depth: usize) -> IResult<&str, Expr> {
    let (rest, lhs) = parse_add(input, depth)?;
    // Single optional comparison — non-associative by design.
    for (sym, op) in [
        ("==", BinOp::Eq),
        ("!=", BinOp::Ne),
        ("<=", BinOp::Le),
        (">=", BinOp::Ge),
        ("<", BinOp::Lt),
        (">", BinOp::Gt),
    ] {
        if let Ok((r, _)) = ews(tag::<_, _, Error<&str>>(sym)).parse(rest) {
            let (r2, rhs) = parse_add(r, depth + 1)?;
            return Ok((r2, Expr::Binary(op, Box::new(lhs), Box::new(rhs))));
        }
    }
    Ok((rest, lhs))
}

fn parse_and(input: &str, depth: usize) -> IResult<&str, Expr> {
    let (mut rest, mut acc) = parse_cmp(input, depth)?;
    while let Ok((r, _)) = ews(tag::<_, _, Error<&str>>("&&")).parse(rest) {
        let (r2, rhs) = parse_cmp(r, depth + 1)?;
        acc = Expr::Binary(BinOp::And, Box::new(acc), Box::new(rhs));
        rest = r2;
    }
    Ok((rest, acc))
}

fn parse_or(input: &str, depth: usize) -> IResult<&str, Expr> {
    let (mut rest, mut acc) = parse_and(input, depth)?;
    while let Ok((r, _)) = ews(tag::<_, _, Error<&str>>("||")).parse(rest) {
        let (r2, rhs) = parse_and(r, depth + 1)?;
        acc = Expr::Binary(BinOp::Or, Box::new(acc), Box::new(rhs));
        rest = r2;
    }
    Ok((rest, acc))
}

/// nom-style entry point: parses one expression, leaving trailing input.
/// Enforces [`MAX_EXPR_NODES`] before returning.
pub fn parse_expr(input: &str) -> IResult<&str, Expr> {
    let (rest, e) = parse_or(input, 0)?;
    if e.node_count() > MAX_EXPR_NODES {
        return Err(nom::Err::Failure(Error::new(input, ErrorKind::TooLarge)));
    }
    Ok((rest, e))
}

/// Whole-string entry point: the entire input must be one expression.
pub fn parse_expr_str(input: &str) -> Result<Expr, ShapeError> {
    let (rest, e) = parse_expr(input).map_err(|e| ShapeError::ParseError(e.to_string()))?;
    let (rest, _) =
        space_or_comment::<Error<&str>>(rest).map_err(|e| ShapeError::ParseError(e.to_string()))?;
    if !rest.is_empty() {
        return Err(ShapeError::ParseError(format!(
            "trailing input after expression: {rest:?}"
        )));
    }
    Ok(e)
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;

    fn ctx_fixture<'a>(
        globals: &'a HashMap<String, f64>,
        params: &'a [(String, f64)],
        rng: &'a mut Pcg64,
    ) -> EvalCtx<'a> {
        EvalCtx {
            scope_size: Vec3::new(10.0, 4.0, 8.0),
            split_i: 2.0,
            split_n: 5.0,
            depth: 3.0,
            params,
            globals,
            rng,
        }
    }

    fn eval_str(s: &str) -> Result<f64, ShapeError> {
        let globals = HashMap::from([("FloorH".to_string(), 3.2)]);
        let params = [("w".to_string(), 1.5)];
        let mut rng = Pcg64::seed_from_u64(7);
        let mut ctx = ctx_fixture(&globals, &params, &mut rng);
        parse_expr_str(s)?.eval(&mut ctx)
    }

    #[test]
    fn precedence_and_parens() {
        assert_eq!(eval_str("1 + 2 * 3").unwrap(), 7.0);
        assert_eq!(eval_str("(1 + 2) * 3").unwrap(), 9.0);
        assert_eq!(eval_str("10 - 4 - 3").unwrap(), 3.0); // left assoc
        assert_eq!(eval_str("7 % 4").unwrap(), 3.0);
        assert_eq!(eval_str("-2 * 3").unwrap(), -6.0);
        assert_eq!(eval_str("--2").unwrap(), 2.0);
    }

    #[test]
    fn comparisons_and_logic() {
        assert_eq!(eval_str("3 < 4").unwrap(), 1.0);
        assert_eq!(eval_str("3 >= 4").unwrap(), 0.0);
        assert_eq!(eval_str("1 && 0").unwrap(), 0.0);
        assert_eq!(eval_str("1 || 0").unwrap(), 1.0);
        assert_eq!(eval_str("!0").unwrap(), 1.0);
        assert_eq!(eval_str("!3").unwrap(), 0.0);
        assert_eq!(eval_str("1 + 1 == 2 && 3 > 1").unwrap(), 1.0);
    }

    #[test]
    fn chained_comparison_is_rejected() {
        assert!(matches!(
            parse_expr_str("1 < 2 < 3"),
            Err(ShapeError::ParseError(_))
        ));
    }

    #[test]
    fn builtin_vars() {
        assert_eq!(eval_str("scope.x").unwrap(), 10.0);
        assert_eq!(eval_str("scope.y + scope.z").unwrap(), 12.0);
        assert_eq!(eval_str("split.i").unwrap(), 2.0);
        assert_eq!(eval_str("split.n - 1").unwrap(), 4.0);
        assert_eq!(eval_str("depth").unwrap(), 3.0);
        assert_eq!(eval_str("split.i == split.n - 1 - 2").unwrap(), 1.0);
    }

    #[test]
    fn named_bindings_param_shadows_global() {
        assert_eq!(eval_str("FloorH").unwrap(), 3.2);
        assert_eq!(eval_str("w * 2").unwrap(), 3.0);
        let globals = HashMap::from([("w".to_string(), 100.0)]);
        let params = [("w".to_string(), 1.0)];
        let mut rng = Pcg64::seed_from_u64(1);
        let mut ctx = ctx_fixture(&globals, &params, &mut rng);
        assert_eq!(parse_expr_str("w").unwrap().eval(&mut ctx).unwrap(), 1.0);
    }

    #[test]
    fn unknown_identifier_errors() {
        assert!(matches!(
            eval_str("NoSuchThing"),
            Err(ShapeError::UnknownIdentifier(n)) if n == "NoSuchThing"
        ));
    }

    #[test]
    fn functions() {
        assert_eq!(eval_str("floor(3.7)").unwrap(), 3.0);
        assert_eq!(eval_str("ceil(3.2)").unwrap(), 4.0);
        assert_eq!(eval_str("abs(-5)").unwrap(), 5.0);
        assert_eq!(eval_str("sqrt(16)").unwrap(), 4.0);
        assert_eq!(eval_str("pow(2, 10)").unwrap(), 1024.0);
        assert_eq!(eval_str("clamp(15, 0, 10)").unwrap(), 10.0);
        assert_eq!(eval_str("min(3, 4) + max(3, 4)").unwrap(), 7.0);
        // Banker's rounding: both 2.5 and 3.5 round to even neighbours.
        assert_eq!(eval_str("rint(2.5)").unwrap(), 2.0);
        assert_eq!(eval_str("rint(3.5)").unwrap(), 4.0);
    }

    #[test]
    fn function_arity_is_enforced() {
        assert!(parse_expr_str("floor()").is_err());
        assert!(parse_expr_str("floor(1, 2)").is_err());
        assert!(parse_expr_str("pow(2)").is_err());
        assert!(parse_expr_str("rand(1, 2, 3)").is_err());
        assert!(parse_expr_str("clamp(1, 2)").is_err());
    }

    #[test]
    fn rand_is_seed_deterministic_and_in_range() {
        let expr = parse_expr_str("rand(2, 6)").unwrap();
        let globals = HashMap::new();
        let params: [(String, f64); 0] = [];
        let draw = |seed: u64| {
            let mut rng = Pcg64::seed_from_u64(seed);
            let mut ctx = ctx_fixture(&globals, &params, &mut rng);
            expr.eval(&mut ctx).unwrap()
        };
        let a = draw(42);
        let b = draw(42);
        let c = draw(43);
        assert_eq!(a, b, "same seed must reproduce the same value");
        assert_ne!(a, c, "different seeds should diverge");
        assert!((2.0..6.0).contains(&a));
        // Zero-width range degenerates to the bound without an RNG draw.
        assert_eq!(eval_str("rand(3, 3)").unwrap(), 3.0);
    }

    #[test]
    fn short_circuit_skips_rhs_rand_draw() {
        // `0 && rand()`: the RHS draw must NOT happen — verify by comparing
        // the RNG position via a subsequent draw.
        let globals = HashMap::new();
        let params: [(String, f64); 0] = [];
        let run = |src: &str| {
            let mut rng = Pcg64::seed_from_u64(9);
            let mut ctx = ctx_fixture(&globals, &params, &mut rng);
            parse_expr_str(src).unwrap().eval(&mut ctx).unwrap();
            rng.random::<f64>()
        };
        let after_short = run("0 && rand()");
        let after_no_rand = run("0 * 1");
        let after_draw = run("1 && rand()");
        assert_eq!(
            after_short, after_no_rand,
            "short-circuit must leave the stream untouched"
        );
        assert_ne!(
            after_draw, after_no_rand,
            "taken RHS must advance the stream"
        );
    }

    #[test]
    fn error_paths() {
        assert!(matches!(eval_str("1 / 0"), Err(ShapeError::ExprEval(_))));
        assert!(matches!(eval_str("1 % 0"), Err(ShapeError::ExprEval(_))));
        assert!(matches!(eval_str("sqrt(-1)"), Err(ShapeError::ExprEval(_))));
        assert!(matches!(
            eval_str("clamp(1, 5, 0)"),
            Err(ShapeError::ExprEval(_))
        ));
        assert!(matches!(
            eval_str("rand(6, 2)"),
            Err(ShapeError::ExprEval(_))
        ));
        // Overflow to infinity is caught, not propagated.
        assert!(matches!(
            eval_str("pow(10, 400)"),
            Err(ShapeError::ExprEval(_))
        ));
    }

    #[test]
    fn comments_inside_expressions() {
        assert_eq!(eval_str("1 + /* two */ 2").unwrap(), 3.0);
        assert_eq!(eval_str("scope.x /* width */ * 0.5").unwrap(), 5.0);
    }

    #[test]
    fn division_is_not_mistaken_for_comments() {
        assert_eq!(eval_str("10 / 2").unwrap(), 5.0);
    }

    #[test]
    fn depth_cap_rejects_paren_bombs() {
        let bomb = format!("{}1{}", "(".repeat(200), ")".repeat(200));
        assert!(parse_expr_str(&bomb).is_err());
    }

    #[test]
    fn node_cap_rejects_huge_expressions() {
        let huge = (0..400).map(|_| "1").collect::<Vec<_>>().join(" + ");
        assert!(matches!(
            parse_expr_str(&huge),
            Err(ShapeError::ParseError(_))
        ));
    }

    #[test]
    fn display_round_trips() {
        for src in [
            "1 + 2 * 3",
            "(scope.x - 1.5) / split.n",
            "rand(2, 6) + FloorH",
            "!(a && b) || c > 3",
            "clamp(scope.y, 0, pow(2, depth))",
            "-w * -2",
        ] {
            let e = parse_expr_str(src).unwrap();
            let rendered = e.to_string();
            let reparsed = parse_expr_str(&rendered)
                .unwrap_or_else(|err| panic!("re-parse of {rendered:?} failed: {err}"));
            assert_eq!(e, reparsed, "round-trip mismatch for {src:?}");
        }
    }

    #[test]
    fn shape_eq_ignores_literal_values_only() {
        let a = parse_expr_str("scope.x * 2 + 1").unwrap();
        let b = parse_expr_str("scope.x * 9 + 7").unwrap();
        let c = parse_expr_str("scope.y * 2 + 1").unwrap();
        assert!(a.shape_eq(&b));
        assert!(!a.shape_eq(&c));
    }

    #[test]
    fn visit_literals_mut_reaches_every_leaf() {
        // `-4` constant-folds to the literal -4.0 (signed value visible).
        let mut e = parse_expr_str("1 + rand(2, 3) * -4").unwrap();
        let mut seen = Vec::new();
        e.visit_literals_mut(&mut |v| {
            seen.push(*v);
            *v += 10.0;
        });
        seen.sort_by(f64::total_cmp);
        assert_eq!(seen, vec![-4.0, 1.0, 2.0, 3.0]);
        let mut seen2 = Vec::new();
        e.visit_literals_mut(&mut |v| seen2.push(*v));
        seen2.sort_by(f64::total_cmp);
        assert_eq!(seen2, vec![6.0, 11.0, 12.0, 13.0]);
    }

    #[test]
    fn negative_literals_constant_fold() {
        assert_eq!(parse_expr_str("-0.2").unwrap(), Expr::Lit(-0.2));
        assert_eq!(parse_expr_str("-0.2").unwrap().as_lit(), Some(-0.2));
        // Folding only applies to literals; other operands keep the node.
        assert!(matches!(
            parse_expr_str("-scope.x").unwrap(),
            Expr::Unary(UnaryOp::Neg, _)
        ));
    }

    #[test]
    fn serde_round_trip() {
        let e = parse_expr_str("clamp(scope.x * w, 0, 10)").unwrap();
        let json = serde_json::to_string(&e).unwrap();
        let back: Expr = serde_json::from_str(&json).unwrap();
        assert_eq!(e, back);
    }
}