tclrs 0.3.0

//! The `expr` expression language.
//!
//! `expr` is a second grammar layered on Tcl's word syntax: operators, C-like
//! precedence, and operands that may themselves be substitutions. Parsing it
//! separately from the command language is what lets a braced expression —
//! `expr {$i < $n}` — be compiled once instead of re-parsed on every
//! evaluation, which is the single largest cost in the reference
//! implementation's hot loops.
//!
//! Precedence and associativity follow `expr(n)`, verified against tclsh 9.0.4:
//! `**` groups right-to-left, everything else left-to-right, and the
//! string-comparison operators share a level with their numeric counterparts
//! (`"a" eq "a" == 1` is 1, so `eq` cannot bind looser than `==`).

use crate::parser::{self, ParseError, Part};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum UnOp {
    Neg,
    Plus,
    BitNot,
    Not,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinOp {
    Pow,
    Mul,
    Div,
    Mod,
    Add,
    Sub,
    Shl,
    Shr,
    /// Numeric-preferring comparisons, falling back to string order.
    Lt,
    Gt,
    Le,
    Ge,
    /// Always-string comparisons: `lt gt le ge`.
    StrLt,
    StrGt,
    StrLe,
    StrGe,
    Eq,
    Ne,
    /// `eq ne`.
    StrEq,
    StrNe,
    In,
    Ni,
    BitAnd,
    BitXor,
    BitOr,
    And,
    Or,
}

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    /// An integer literal: its value, and the text the script wrote — which is
    /// what `eq` and the other always-string operators compare, since `010` and
    /// `10` are the same number and different strings.
    Int(i64, Box<str>),
    /// A double literal, with its spelling for the same reason: `1e3` and
    /// `1000.0` are one number and two strings.
    Float(f64, Box<str>),
    /// An operand built from literal text and substitutions: a quoted or braced
    /// string, `$var`, `$arr(i)`, or `[script]`.
    Subst(Vec<Part>),
    Unary(UnOp, Box<Expr>),
    Binary(BinOp, Box<Expr>, Box<Expr>),
    Ternary(Box<Expr>, Box<Expr>, Box<Expr>),
    /// A math function call — parsed here, lowered in a later phase.
    Call(String, Vec<Expr>),
}

/// How deeply subexpressions may nest before the parser refuses to go further.
///
/// This parser is recursive descent, so nesting costs native stack — and running
/// out of it is a signal, not an error, which kills the process with nothing to
/// report. [`crate::parser::MAX_NESTING_DEPTH`] bounds the command language's
/// recursion for the same reason; this is the same mechanism for the expression
/// language.
///
/// The number is measured, not chosen for looks. On the stack the `tclrs` binary
/// gives the parser ([`crate::runtime::RECOMMENDED_STACK`], which is what a host
/// embedding this crate is documented to provide), an unoptimized build of
/// `expr {((…1…))}` still parses and compiles at 7_500 parentheses and aborts by
/// 8_000; a chain of unary operators, whose frames are far cheaper, survives
/// 100_000 and aborts by 150_000. 5_000 is a third under the parenthesis floor,
/// which is the expensive descent of the two.
///
/// The unoptimized build is the one to calibrate against: it is the weakest this
/// crate is built as, and the one `cargo test` runs. An optimized build's frames
/// are small enough to survive 32_000 parentheses on the same stack, so a limit
/// set from *its* floor would leave a debug build aborting where a release build
/// only reported an error.
///
/// Unlike the command parser's limit, this one is *not* above every depth the
/// reference interpreter survives: tclsh 9.0.4 parses expressions with an
/// explicit stack (`tclCompExpr.c`) rather than by recursion, and evaluates
/// 1_000_000 nested parentheses without complaint. Bounding here therefore
/// refuses a handful of inputs tclsh accepts. That is the deliberate trade — an
/// input past the limit gets a Tcl error the script can catch, where before it
/// took the whole process down.
pub const MAX_EXPR_DEPTH: usize = 5_000;

/// Parse a complete expression.
pub fn parse(src: &str) -> Result<Expr, ParseError> {
    let mut p = ExprParser {
        src,
        pos: 0,
        depth: 0,
    };
    p.skip_space();
    let e = p.parse_binary(0)?;
    p.skip_space();
    if p.pos < p.src.len() {
        return Err(p.error(&format!(
            "extra characters after expression: {:?}",
            &p.src[p.pos..]
        )));
    }
    Ok(e)
}

/// Binding powers, lowest first. Each entry is one precedence level; every
/// level is left-associative except `**`, handled in [`ExprParser::parse_binary`].
///
/// Public because the reference page prints the ladder, and printing it from
/// anywhere but the table the parser binds with would let the two disagree.
pub const LEVELS: &[&[(&str, BinOp)]] = &[
    &[("||", BinOp::Or)],
    &[("&&", BinOp::And)],
    &[("|", BinOp::BitOr)],
    &[("^", BinOp::BitXor)],
    &[("&", BinOp::BitAnd)],
    &[
        ("==", BinOp::Eq),
        ("!=", BinOp::Ne),
        ("eq", BinOp::StrEq),
        ("ne", BinOp::StrNe),
        ("in", BinOp::In),
        ("ni", BinOp::Ni),
    ],
    &[
        ("<=", BinOp::Le),
        (">=", BinOp::Ge),
        ("<", BinOp::Lt),
        (">", BinOp::Gt),
        ("lt", BinOp::StrLt),
        ("gt", BinOp::StrGt),
        ("le", BinOp::StrLe),
        ("ge", BinOp::StrGe),
    ],
    &[("<<", BinOp::Shl), (">>", BinOp::Shr)],
    &[("+", BinOp::Add), ("-", BinOp::Sub)],
    &[("*", BinOp::Mul), ("/", BinOp::Div), ("%", BinOp::Mod)],
    &[("**", BinOp::Pow)],
];

struct ExprParser<'a> {
    src: &'a str,
    pos: usize,
    /// How many subexpressions are open at the cursor — the recursion this
    /// parser does, bounded by [`MAX_EXPR_DEPTH`].
    depth: usize,
}

impl<'a> ExprParser<'a> {
    fn bytes(&self) -> &'a [u8] {
        self.src.as_bytes()
    }

    /// Parse one nesting level deeper, or refuse.
    ///
    /// Every recursive call that opens a subexpression goes through here: a
    /// parenthesized operand, a function argument, both arms of a ternary, the
    /// right operand of the right-associative `**`, and a unary operator's
    /// operand. The level walk inside [`ExprParser::parse_binary`] does not,
    /// because it is bounded by [`LEVELS`] rather than by the input.
    ///
    /// The wording follows the shape the reference interpreter uses for its own
    /// depth refusals (`too many nested evaluations (infinite loop?)`), because
    /// there is no reference behavior to copy: tclsh's expression parser does
    /// not recurse and so has no limit to match.
    fn nested<T>(
        &mut self,
        parse: impl FnOnce(&mut Self) -> Result<T, ParseError>,
    ) -> Result<T, ParseError> {
        if self.depth >= MAX_EXPR_DEPTH {
            return Err(self.error("too many nested subexpressions (infinite loop?)"));
        }
        self.depth += 1;
        let parsed = parse(self);
        self.depth -= 1;
        parsed
    }

    fn peek(&self) -> Option<u8> {
        self.bytes().get(self.pos).copied()
    }

    fn error(&self, msg: &str) -> ParseError {
        ParseError {
            msg: msg.to_string(),
            offset: self.pos,
            line: 1,
        }
    }

    fn skip_space(&mut self) {
        while matches!(self.peek(), Some(b' ' | b'\t' | b'\n' | b'\r')) {
            self.pos += 1;
        }
    }

    /// Does an operator token sit at the cursor? Word operators (`eq`, `in`)
    /// must not be a prefix of a longer bare word, so `$income` is not `in`.
    fn match_op(&self, op: &str) -> bool {
        if !self.src[self.pos..].starts_with(op) {
            return false;
        }
        if op.as_bytes()[0].is_ascii_alphabetic() {
            match self.bytes().get(self.pos + op.len()) {
                Some(b) if b.is_ascii_alphanumeric() || *b == b'_' => return false,
                _ => {}
            }
        }
        // `**` must win over `*`, `<=` over `<`; the level tables are ordered
        // so the longer token is tried first within a level, but `*` and `**`
        // sit on different levels, so guard here too.
        if op == "*" && self.src[self.pos..].starts_with("**") {
            return false;
        }
        if op == "<" && self.src[self.pos..].starts_with("<<") {
            return false;
        }
        if op == ">" && self.src[self.pos..].starts_with(">>") {
            return false;
        }
        if (op == "&" && self.src[self.pos..].starts_with("&&"))
            || (op == "|" && self.src[self.pos..].starts_with("||"))
        {
            return false;
        }
        true
    }

    fn parse_binary(&mut self, level: usize) -> Result<Expr, ParseError> {
        if level >= LEVELS.len() {
            return self.parse_unary();
        }
        let mut lhs = self.parse_binary(level + 1)?;
        loop {
            self.skip_space();
            let Some(&(tok, op)) = LEVELS[level].iter().find(|(tok, _)| self.match_op(tok)) else {
                break;
            };
            self.pos += tok.len();
            self.skip_space();
            // Exponentiation is the one right-associative level.
            let rhs = if op == BinOp::Pow {
                self.nested(|p| p.parse_binary(level))?
            } else {
                self.parse_binary(level + 1)?
            };
            lhs = Expr::Binary(op, Box::new(lhs), Box::new(rhs));
        }
        // The ternary sits below every binary level.
        if level == 0 {
            self.skip_space();
            if self.peek() == Some(b'?') {
                self.pos += 1;
                self.skip_space();
                let then = self.nested(|p| p.parse_binary(0))?;
                self.skip_space();
                if self.peek() != Some(b':') {
                    return Err(self.error("missing : in ternary"));
                }
                self.pos += 1;
                self.skip_space();
                let other = self.nested(|p| p.parse_binary(0))?;
                lhs = Expr::Ternary(Box::new(lhs), Box::new(then), Box::new(other));
            }
        }
        Ok(lhs)
    }

    fn parse_unary(&mut self) -> Result<Expr, ParseError> {
        self.skip_space();
        let op = match self.peek() {
            Some(b'-') => Some(UnOp::Neg),
            Some(b'+') => Some(UnOp::Plus),
            Some(b'~') => Some(UnOp::BitNot),
            Some(b'!') if self.bytes().get(self.pos + 1) != Some(&b'=') => Some(UnOp::Not),
            _ => None,
        };
        if let Some(op) = op {
            self.pos += 1;
            let operand = self.nested(|p| p.parse_unary())?;
            return Ok(Expr::Unary(op, Box::new(operand)));
        }
        self.parse_operand()
    }

    fn parse_operand(&mut self) -> Result<Expr, ParseError> {
        self.skip_space();
        match self.peek() {
            None => Err(self.error("premature end of expression")),
            Some(b'(') => {
                self.pos += 1;
                let e = self.nested(|p| p.parse_binary(0))?;
                self.skip_space();
                if self.peek() != Some(b')') {
                    return Err(self.error("missing close-paren"));
                }
                self.pos += 1;
                Ok(e)
            }
            Some(b'$') => {
                let Some((part, next)) = parser::substitution_at(self.src, self.pos)? else {
                    return Err(self.error("invalid $ in expression"));
                };
                self.pos = next;
                Ok(Expr::Subst(vec![part]))
            }
            Some(b'[') => {
                let (script, next) = parser::command_at(self.src, self.pos)?;
                self.pos = next;
                Ok(Expr::Subst(vec![Part::Script(script)]))
            }
            Some(b'"') => {
                let (parts, next) = parser::quoted_at(self.src, self.pos)?;
                self.pos = next;
                Ok(Expr::Subst(parts))
            }
            Some(b'{') => {
                let (text, next) = parser::braced_at(self.src, self.pos)?;
                self.pos = next;
                Ok(Expr::Subst(vec![Part::Lit(text)]))
            }
            Some(b) if b.is_ascii_digit() || b == b'.' => self.parse_number(),
            Some(b) if b.is_ascii_alphabetic() || b == b'_' => self.parse_call(),
            // A whole character, not the byte at the cursor: `expr {Ü}` reports
            // `invalid character "Ü"`, and reporting `self.src[pos]` named the
            // lead byte of its UTF-8 encoding (`Ã`) instead. The wording is
            // tclsh 9.0.4's, measured, and covers ASCII too — `expr {@}` is
            // `invalid character "@"`.
            Some(_) => {
                let c = self.src[self.pos..]
                    .chars()
                    .next()
                    .expect("a byte at the cursor is part of a character");
                Err(self.error(&format!("invalid character \"{c}\"")))
            }
        }
    }

    /// Tcl integer literals carry the C-ish radix prefixes; anything with a
    /// decimal point or exponent is a double.
    fn parse_number(&mut self) -> Result<Expr, ParseError> {
        let start = self.pos;
        let rest = &self.src[start..];

        if let Some(radix_body) = rest.strip_prefix("0x").or_else(|| rest.strip_prefix("0X")) {
            return self.radix_literal(radix_body, 16, 2);
        }
        if let Some(radix_body) = rest.strip_prefix("0o").or_else(|| rest.strip_prefix("0O")) {
            return self.radix_literal(radix_body, 8, 2);
        }
        if let Some(radix_body) = rest.strip_prefix("0b").or_else(|| rest.strip_prefix("0B")) {
            return self.radix_literal(radix_body, 2, 2);
        }
        if let Some(radix_body) = rest.strip_prefix("0d").or_else(|| rest.strip_prefix("0D")) {
            return self.radix_literal(radix_body, 10, 2);
        }

        let mut end = start;
        let b = self.bytes();
        // `_` separates digits in Tcl 9's integer grammar — `1_0` is ten — and
        // is part of the literal's text, so it is scanned here and dropped
        // before the parse below rather than ending the number.
        while end < b.len() && (b[end].is_ascii_digit() || b[end] == b'_') {
            end += 1;
        }
        let mut is_float = false;
        if end < b.len() && b[end] == b'.' {
            is_float = true;
            end += 1;
            while end < b.len() && b[end].is_ascii_digit() {
                end += 1;
            }
        }
        if end < b.len() && (b[end] == b'e' || b[end] == b'E') {
            let mut probe = end + 1;
            if probe < b.len() && (b[probe] == b'+' || b[probe] == b'-') {
                probe += 1;
            }
            if probe < b.len() && b[probe].is_ascii_digit() {
                is_float = true;
                end = probe;
                while end < b.len() && b[end].is_ascii_digit() {
                    end += 1;
                }
            }
        }

        let text = &self.src[start..end];
        self.pos = end;
        // Parsed without the separators, remembered with them: `1_0` is the
        // number ten and the string "1_0".
        let bare: String = text.chars().filter(|c| *c != '_').collect();
        if is_float {
            bare.parse::<f64>()
                .map(|v| Expr::Float(v, text.into()))
                .map_err(|_| self.error(&format!("invalid floating-point number {text:?}")))
        } else {
            // Out of `i64` range: Tcl promotes to a bignum, which this frontend
            // does not have. The literal stays its own text, and every *operation*
            // on it is refused by the numeric hook — which is where the overflow
            // is reported now that `runtime::parse_number` no longer hands the
            // spelling to the double parser and answers `1e+20`.
            //
            // Deliberately not refused here. A decimal spelling this large is
            // exactly what tclsh prints for it, so `expr {99999999999999999999}`
            // and `puts 99999999999999999999` are both right as text; refusing at
            // compile time would take down whole scripts that only ever print the
            // value or never reach it at all.
            bare.parse::<i64>()
                .map(|v| Expr::Int(v, text.into()))
                .or_else(|_| Ok(Expr::Subst(vec![Part::Lit(text.to_string())])))
        }
    }

    fn radix_literal(
        &mut self,
        body: &str,
        radix: u32,
        prefix_len: usize,
    ) -> Result<Expr, ParseError> {
        let written: String = body
            .chars()
            .take_while(|c| c.is_digit(radix) || *c == '_')
            .collect();
        let digits: String = written.chars().filter(|c| *c != '_').collect();
        if digits.is_empty() {
            return Err(self.error("missing digits after radix prefix"));
        }
        // The spelling, prefix included: `0x10` and `16` are the same number and
        // different strings, and `eq` compares the strings.
        let text: Box<str> = format!("{}{written}", &self.src[self.pos..self.pos + prefix_len]).into();
        // The written length, not the parsed one: `0x1_0` is five characters and
        // two digits, and advancing by the digits alone left the `_0` behind as
        // "extra characters after expression".
        self.pos += prefix_len + written.len();
        i64::from_str_radix(&digits, radix)
            .map(|v| Expr::Int(v, text))
            // The same bignum case as a decimal literal's, and the same wording —
            // but refused here rather than deferred, because a radix spelling is
            // *not* what tclsh prints for the value: `expr {0x10000000000000000}`
            // is `18446744073709551616` there, so carrying the text through would
            // answer with something the script did not mean.
            .map_err(|_| self.error("integer value too large to represent"))
    }

    fn parse_call(&mut self) -> Result<Expr, ParseError> {
        let start = self.pos;
        let b = self.bytes();
        let mut end = start;
        while end < b.len() && (b[end].is_ascii_alphanumeric() || b[end] == b'_' || b[end] == b':')
        {
            end += 1;
        }
        let name = self.src[start..end].to_string();
        self.pos = end;
        self.skip_space();
        if self.peek() != Some(b'(') {
            return Err(self.error(&format!("invalid bare word {name:?} in expression")));
        }
        self.pos += 1;
        let mut args = Vec::new();
        self.skip_space();
        if self.peek() == Some(b')') {
            self.pos += 1;
            return Ok(Expr::Call(name, args));
        }
        loop {
            args.push(self.nested(|p| p.parse_binary(0))?);
            self.skip_space();
            match self.peek() {
                Some(b',') => {
                    self.pos += 1;
                }
                Some(b')') => {
                    self.pos += 1;
                    return Ok(Expr::Call(name, args));
                }
                _ => return Err(self.error("missing close-paren in function call")),
            }
        }
    }
}