lex_syntax/

parser.rs

//! Recursive-descent parser for Lex. Pratt-style precedence climbing for
//! binary operators; everything else is straightforward LL(1)-with-lookahead.

use crate::syntax::*;
use crate::token::{Token, TokenKind};

pub fn parse(tokens: Vec<Token>) -> Result<Program, ParseError> {
    // Back-compat entry: no source available, so leading comments are
    // not recovered. `parse_source` in `lib.rs` calls
    // `parse_with_src` directly and is the path that preserves them.
    parse_with_src("", tokens)
}

/// Parse + attach `#` line-comments to the AST. The source string is
/// used only to scan the gaps between tokens (where the lexer skipped
/// whitespace and comments); the parser itself still operates purely
/// on tokens. See `Program::leading_comments` for the data model.
pub fn parse_with_src(src: &str, tokens: Vec<Token>) -> Result<Program, ParseError> {
    let mut p = Parser::new(src, tokens);
    let program = p.parse_program()?;
    p.skip_newlines();
    if !p.at_eof() {
        return Err(p.error("unexpected token after program"));
    }
    Ok(program)
}

#[derive(Debug, thiserror::Error)]
#[error("parse error at byte {pos}: {msg}")]
pub struct ParseError {
    pub pos: usize,
    pub msg: String,
}

struct Parser<'a> {
    /// Source text — needed only for trivia recovery (line comments
    /// in the gaps between tokens). Empty when called through the
    /// legacy `parse(tokens)` entry; comments are silently dropped
    /// in that path.
    src: &'a str,
    tokens: Vec<Token>,
    idx: usize,
    /// Recursion depth across `parse_expr`. Capped at `MAX_DEPTH`
    /// to defend against adversarial input like a long sequence of
    /// `[[[{{{...` that would otherwise blow the stack. Found by
    /// the libFuzzer parser target — see `fuzz/fuzz_targets/parser.rs`.
    depth: u32,
    /// Counter for `let _ := ...` discard bindings (#200). Each
    /// discard gets a unique synthetic name so multiple `let _`
    /// in the same scope shadow rather than collide. The names
    /// aren't expressible in user syntax (`__lex_discard_N`),
    /// so user code can't reference them by accident.
    discard_counter: u32,
}

/// Maximum nesting depth the parser will accept before refusing
/// with a parse error. Real Lex code rarely exceeds 30; 96 leaves
/// generous headroom for legitimate generated code.
///
/// Each `parse_expr` level produces ~4-5 stack frames through the
/// `parse_binary_expr → parse_unary_expr → parse_postfix →
/// parse_primary → ...` chain, so this caps the actual frame
/// count around 400-500 — well below even a 2 MiB test stack.
const MAX_DEPTH: u32 = 96;

impl<'a> Parser<'a> {
    fn new(src: &'a str, tokens: Vec<Token>) -> Self {
        Self { src, tokens, idx: 0, depth: 0, discard_counter: 0 }
    }

    /// Extract `#` line-comments from the source byte range
    /// `start..end`. The range must be a "gap" between two tokens
    /// (or between source-start/end and a token); by construction
    /// such gaps contain only whitespace and `#` comments — string
    /// contents never appear because the lexer's logos rules would
    /// have produced a `Str(...)` token covering them.
    ///
    /// Each returned entry is a single source line, trimmed of leading
    /// whitespace (the `#` and everything after it preserved) and of
    /// trailing whitespace. Blank lines between consecutive comments
    /// are dropped — preserving inter-comment blank lines is left to
    /// a follow-up; the bug this addresses (#417) is about comments
    /// disappearing entirely.
    fn extract_comments(&self, start: usize, end: usize) -> Vec<String> {
        if start >= end || end > self.src.len() {
            return Vec::new();
        }
        self.src[start..end]
            .lines()
            .filter_map(|line| {
                let trimmed = line.trim_start();
                if trimmed.starts_with('#') {
                    Some(trimmed.trim_end().to_string())
                } else {
                    None
                }
            })
            .collect()
    }

    fn at_eof(&self) -> bool {
        self.idx >= self.tokens.len()
    }

    fn peek(&self) -> Option<&TokenKind> {
        self.tokens.get(self.idx).map(|t| &t.kind)
    }

    fn bump(&mut self) -> Option<Token> {
        let t = self.tokens.get(self.idx).cloned();
        if t.is_some() {
            self.idx += 1;
        }
        t
    }

    fn current_pos(&self) -> usize {
        self.tokens
            .get(self.idx)
            .map(|t| t.span.start)
            .unwrap_or_else(|| self.tokens.last().map(|t| t.span.end).unwrap_or(0))
    }

    fn error(&self, msg: impl Into<String>) -> ParseError {
        ParseError { pos: self.current_pos(), msg: msg.into() }
    }

    fn skip_newlines(&mut self) {
        while matches!(self.peek(), Some(TokenKind::Newline) | Some(TokenKind::Semi)) {
            self.idx += 1;
        }
    }

    fn expect(&mut self, expected: &TokenKind, ctx: &str) -> Result<Token, ParseError> {
        self.skip_newlines();
        match self.peek() {
            Some(k) if std::mem::discriminant(k) == std::mem::discriminant(expected) => {
                Ok(self.bump().unwrap())
            }
            Some(other) => Err(self.error(format!(
                "expected {expected:?} {ctx}, got {other:?}"
            ))),
            None => Err(self.error(format!("expected {expected:?} {ctx}, got EOF"))),
        }
    }

    fn eat(&mut self, k: &TokenKind) -> bool {
        self.skip_newlines();
        if let Some(cur) = self.peek() {
            if std::mem::discriminant(cur) == std::mem::discriminant(k) {
                self.bump();
                return true;
            }
        }
        false
    }

    fn expect_ident(&mut self, ctx: &str) -> Result<String, ParseError> {
        self.skip_newlines();
        match self.peek() {
            Some(TokenKind::Ident(_)) => match self.bump().unwrap().kind {
                TokenKind::Ident(name) => Ok(name),
                _ => unreachable!(),
            },
            other => Err(self.error(format!("expected identifier {ctx}, got {other:?}"))),
        }
    }

    // --- top level ---

    fn parse_program(&mut self) -> Result<Program, ParseError> {
        let mut items = Vec::new();
        let mut leading_comments: Vec<String> = Vec::new();
        // Byte offset of the end of the last consumed token (or 0 at
        // start of file). The next gap to scan for comments is from
        // here up to the start of the upcoming item's first token.
        let mut gap_start: usize = 0;
        loop {
            self.skip_newlines();
            if self.at_eof() {
                break;
            }
            let item_start = self.tokens[self.idx].span.start;
            let gap_comments = self.extract_comments(gap_start, item_start);
            let pending_comments = if items.is_empty() {
                leading_comments = gap_comments;
                Vec::new()
            } else {
                gap_comments
            };
            let mut item = self.parse_item()?;
            if !pending_comments.is_empty() {
                attach_leading_comments(&mut item, pending_comments);
            }
            gap_start = self
                .tokens
                .get(self.idx.saturating_sub(1))
                .map(|t| t.span.end)
                .unwrap_or(gap_start);
            items.push(item);
        }
        // Trailing comments live after the last consumed token (or
        // span the whole file when there are no items).
        let trailing_comments = self.extract_comments(gap_start, self.src.len());
        Ok(Program { items, leading_comments, trailing_comments })
    }

    fn parse_item(&mut self) -> Result<Item, ParseError> {
        match self.peek() {
            Some(TokenKind::Import) => self.parse_import().map(Item::Import),
            Some(TokenKind::Type) => self.parse_type_decl().map(Item::TypeDecl),
            Some(TokenKind::Fn) => self.parse_fn_decl().map(Item::FnDecl),
            other => Err(self.error(format!(
                "expected `import`, `type`, or `fn` at top level, got {other:?}"
            ))),
        }
    }

    fn parse_import(&mut self) -> Result<Import, ParseError> {
        self.expect(&TokenKind::Import, "in import")?;
        let reference = match self.bump().map(|t| t.kind) {
            Some(TokenKind::Str(s)) => s,
            other => return Err(self.error(format!("expected string after `import`, got {other:?}"))),
        };
        self.expect(&TokenKind::As, "in import")?;
        let alias = self.expect_ident("for import alias")?;
        Ok(Import { reference, alias, leading_comments: Vec::new() })
    }

    fn parse_type_decl(&mut self) -> Result<TypeDecl, ParseError> {
        self.expect(&TokenKind::Type, "in type decl")?;
        let name = self.expect_ident("for type name")?;
        let params = if self.eat(&TokenKind::LBracket) {
            let ps = self.parse_ident_list()?;
            self.expect(&TokenKind::RBracket, "after type params")?;
            ps
        } else {
            Vec::new()
        };
        self.expect(&TokenKind::Eq, "in type decl")?;
        let definition = self.parse_type_decl_rhs()?;
        Ok(TypeDecl { name, params, definition, leading_comments: Vec::new() })
    }

    fn parse_ident_list(&mut self) -> Result<Vec<String>, ParseError> {
        let mut out = Vec::new();
        out.push(self.expect_ident("in identifier list")?);
        while self.eat(&TokenKind::Comma) {
            if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
            out.push(self.expect_ident("in identifier list")?);
        }
        Ok(out)
    }

    /// `type Foo = Variant1 | Variant2(Payload)` is a union; otherwise a plain type expression.
    fn parse_type_decl_rhs(&mut self) -> Result<TypeExpr, ParseError> {
        let first = self.parse_type_expr()?;
        // Detect union: PascalCase ident (or named type w/ optional payload) followed by `|`.
        if matches!(self.peek_skip_newlines(), Some(TokenKind::Bar)) {
            let mut variants = Vec::new();
            variants.push(type_to_variant(first)?);
            while self.eat(&TokenKind::Bar) {
                let next = self.parse_type_expr()?;
                variants.push(type_to_variant(next)?);
            }
            Ok(TypeExpr::Union(variants))
        } else {
            // Single-variant union without `|`: `type Msg = Execute(Str)`.
            // The `(...)` constructor-payload syntax is distinguishable from
            // `[...]` type-application by checking the last consumed token.
            // `Execute(Str)` ends with `)`, `List[Int]` ends with `]`,
            // `AnotherType` ends with the ident token.
            let last_was_rparen = self.idx > 0 && matches!(
                self.tokens.get(self.idx - 1).map(|t| &t.kind),
                Some(TokenKind::RParen)
            );
            if last_was_rparen {
                if let TypeExpr::Named { ref name, .. } = first {
                    let unqual = name.split('.').next_back().unwrap_or(name.as_str());
                    if unqual.chars().next().map(|c| c.is_ascii_uppercase()).unwrap_or(false) {
                        return Ok(TypeExpr::Union(vec![type_to_variant(first)?]));
                    }
                }
            }
            Ok(first)
        }
    }

    fn peek_skip_newlines(&mut self) -> Option<TokenKind> {
        let saved = self.idx;
        self.skip_newlines();
        let out = self.peek().cloned();
        self.idx = saved;
        out
    }

    fn parse_type_expr(&mut self) -> Result<TypeExpr, ParseError> {
        let base = self.parse_type_expr_base()?;
        self.maybe_wrap_refinement(base)
    }

    fn parse_type_expr_base(&mut self) -> Result<TypeExpr, ParseError> {
        self.skip_newlines();
        match self.peek() {
            Some(TokenKind::LBrace) => self.parse_record_type(),
            Some(TokenKind::LParen) => self.parse_paren_type_or_function(),
            Some(TokenKind::Ident(_)) => {
                let mut name = self.expect_ident("in type expr")?;
                // Module-qualified type: `m.Type` or `m.n.Type`. We accept
                // dotted names here and let the loader rewrite them to the
                // file-local mangled form. After the loader pass, all type
                // names referenced by the type checker are single segments.
                while matches!(self.peek(), Some(TokenKind::Dot)) {
                    self.bump();
                    let next = self.expect_ident("after `.` in qualified type")?;
                    name.push('.');
                    name.push_str(&next);
                }
                let args = if matches!(self.peek(), Some(TokenKind::LBracket)) {
                    self.bump();
                    let mut args = Vec::new();
                    args.push(self.parse_type_expr()?);
                    while self.eat(&TokenKind::Comma) {
                        if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
                        args.push(self.parse_type_expr()?);
                    }
                    self.expect(&TokenKind::RBracket, "after type args")?;
                    args
                } else if matches!(self.peek(), Some(TokenKind::LParen)) {
                    // Constructor type with payload: `Name(T)` or `Name(T1, T2)`.
                    self.bump();
                    let mut args = Vec::new();
                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
                        args.push(self.parse_type_expr()?);
                        while self.eat(&TokenKind::Comma) {
                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                            args.push(self.parse_type_expr()?);
                        }
                    }
                    self.expect(&TokenKind::RParen, "after constructor payload")?;
                    args
                } else {
                    Vec::new()
                };
                Ok(TypeExpr::Named { name, args })
            }
            other => Err(self.error(format!("expected type expression, got {other:?}"))),
        }
    }

    /// Refinement type postfix (#209): `BaseType{binding | predicate}`.
    ///
    /// Disambiguates from a function body's opening brace by peeking
    /// three tokens ahead — refinement requires `{ Ident |`, a body
    /// begins with `{ <expr-starting-token>`. This means a refinement
    /// binding name can't start with `|`, but that's fine since
    /// identifiers don't.
    fn maybe_wrap_refinement(&mut self, base: TypeExpr) -> Result<TypeExpr, ParseError> {
        let next0 = self.tokens.get(self.idx).map(|t| &t.kind);
        let next1 = self.tokens.get(self.idx + 1).map(|t| &t.kind);
        let next2 = self.tokens.get(self.idx + 2).map(|t| &t.kind);
        let is_refinement_lookahead = matches!(next0, Some(TokenKind::LBrace))
            && matches!(next1, Some(TokenKind::Ident(_)))
            && matches!(next2, Some(TokenKind::Bar));
        if !is_refinement_lookahead {
            return Ok(base);
        }
        self.bump(); // `{`
        let binding = self.expect_ident("for refinement binding")?;
        self.expect(&TokenKind::Bar, "after refinement binding")?;
        let predicate = self.parse_expr()?;
        self.expect(&TokenKind::RBrace, "to close refinement")?;
        Ok(TypeExpr::Refined {
            base: Box::new(base),
            binding,
            predicate: Box::new(predicate),
        })
    }

    fn parse_record_type(&mut self) -> Result<TypeExpr, ParseError> {
        self.expect(&TokenKind::LBrace, "in record type")?;
        let mut fields = Vec::new();
        let mut spreads = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
            loop {
                self.skip_newlines();
                if matches!(self.peek(), Some(TokenKind::DotDotDot)) {
                    self.bump(); // consume `...`
                    let name = self.expect_ident("after `...` in record type spread")?;
                    spreads.push(name);
                } else {
                    let name = self.expect_ident("in record field")?;
                    self.expect(&TokenKind::ColonColon, "after record field name")?;
                    let ty = self.parse_type_expr()?;
                    fields.push(TypeField { name, ty });
                }
                self.skip_newlines();
                if !self.eat(&TokenKind::Comma) { break; }
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
            }
        }
        self.expect(&TokenKind::RBrace, "in record type")?;
        if spreads.is_empty() {
            Ok(TypeExpr::Record(fields))
        } else {
            Ok(TypeExpr::RecordWithSpreads { spreads, fields })
        }
    }

    fn parse_paren_type_or_function(&mut self) -> Result<TypeExpr, ParseError> {
        self.expect(&TokenKind::LParen, "in type")?;
        let mut args = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
            args.push(self.parse_type_expr()?);
            while self.eat(&TokenKind::Comma) {
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                args.push(self.parse_type_expr()?);
            }
        }
        self.expect(&TokenKind::RParen, "in type")?;
        // Function type if followed by `->`.
        if matches!(self.peek_skip_newlines(), Some(TokenKind::Arrow)) {
            self.skip_newlines();
            self.bump();
            let effects = self.parse_effects()?;
            let ret = self.parse_type_expr()?;
            Ok(TypeExpr::Function {
                params: args,
                effects,
                ret: Box::new(ret),
            })
        } else if args.len() == 1 {
            // Parenthesized type expression.
            Ok(args.into_iter().next().unwrap())
        } else {
            Ok(TypeExpr::Tuple(args))
        }
    }

    fn parse_fn_decl(&mut self) -> Result<FnDecl, ParseError> {
        self.expect(&TokenKind::Fn, "in fn decl")?;
        let name = self.expect_ident("for function name")?;
        let type_params = if self.eat(&TokenKind::LBracket) {
            let ps = self.parse_ident_list()?;
            self.expect(&TokenKind::RBracket, "after type params")?;
            ps
        } else {
            Vec::new()
        };
        self.expect(&TokenKind::LParen, "before params")?;
        let mut params = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
            params.push(self.parse_param()?);
            while self.eat(&TokenKind::Comma) {
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                params.push(self.parse_param()?);
            }
        }
        self.expect(&TokenKind::RParen, "after params")?;
        self.expect(&TokenKind::Arrow, "before return type")?;
        let effects = self.parse_effects()?;
        let return_type = self.parse_type_expr()?;
        let examples = self.parse_examples_block()?;
        let body = self.parse_block()?;
        Ok(FnDecl { name, type_params, params, effects, return_type, body, examples, leading_comments: Vec::new() })
    }

    /// Parse an optional `examples { call(a, b) => expected, ... }` block
    /// sitting between the return type and the body (#369). Returns an
    /// empty vec when no block is present.
    fn parse_examples_block(&mut self) -> Result<Vec<Example>, ParseError> {
        // Contextual: not a reserved keyword. Peek for the literal
        // identifier `examples` followed by `{`; otherwise no block.
        let is_examples_kw = matches!(
            self.peek_skip_newlines(),
            Some(TokenKind::Ident(s)) if s == "examples"
        );
        if !is_examples_kw {
            return Ok(Vec::new());
        }
        self.skip_newlines();
        self.bump(); // consume `examples`
        self.expect(&TokenKind::LBrace, "after `examples`")?;
        let mut cases = Vec::new();
        loop {
            self.skip_newlines();
            if matches!(self.peek(), Some(TokenKind::RBrace)) { break; }
            let call = self.parse_expr()?;
            self.expect(&TokenKind::FatArrow, "in example case (between call and expected)")?;
            let expected = self.parse_expr()?;
            let (args, _) = match call {
                Expr::Call { callee: _, args } => (args, ()),
                other => return Err(self.error(
                    format!("example case must be a call to the function under definition; got {other:?}")
                )),
            };
            cases.push(Example { args, expected });
            self.skip_newlines();
            if !self.eat(&TokenKind::Comma) {
                self.skip_newlines();
                break;
            }
        }
        self.expect(&TokenKind::RBrace, "to close examples block")?;
        Ok(cases)
    }

    fn parse_param(&mut self) -> Result<Param, ParseError> {
        let name = if matches!(self.peek_skip_newlines(), Some(TokenKind::Underscore)) {
            self.skip_newlines();
            self.bump();
            self.discard_counter += 1;
            format!("__lex_discard_{}", self.discard_counter)
        } else {
            self.expect_ident("for parameter name")?
        };
        self.expect(&TokenKind::ColonColon, "after parameter name")?;
        let ty = self.parse_type_expr()?;
        Ok(Param { name, ty })
    }

    fn parse_effects(&mut self) -> Result<Vec<Effect>, ParseError> {
        if !self.eat(&TokenKind::LBracket) {
            return Ok(Vec::new());
        }
        let mut out = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) {
            out.push(self.parse_effect()?);
            while self.eat(&TokenKind::Comma) {
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
                out.push(self.parse_effect()?);
            }
        }
        self.expect(&TokenKind::RBracket, "after effects")?;
        Ok(out)
    }

    fn parse_effect(&mut self) -> Result<Effect, ParseError> {
        let name = self.expect_ident("for effect name")?;
        let arg = if self.eat(&TokenKind::LParen) {
            let arg = match self.bump().map(|t| t.kind) {
                Some(TokenKind::Str(s)) => EffectArg::Str(s),
                Some(TokenKind::Int(n)) => EffectArg::Int(n),
                Some(TokenKind::Ident(s)) => EffectArg::Ident(s),
                other => return Err(self.error(format!("invalid effect arg: {other:?}"))),
            };
            self.expect(&TokenKind::RParen, "after effect arg")?;
            Some(arg)
        } else {
            None
        };
        Ok(Effect { name, arg })
    }

    // --- blocks and statements ---

    fn parse_block(&mut self) -> Result<Block, ParseError> {
        self.expect(&TokenKind::LBrace, "before block")?;
        let mut statements = Vec::new();
        let result;
        loop {
            self.skip_newlines();
            if matches!(self.peek(), Some(TokenKind::RBrace)) {
                // Empty block: synthesize Unit literal.
                result = Box::new(Expr::Lit(Literal::Unit));
                break;
            }
            // Try parsing a let; otherwise an expression.
            if matches!(self.peek(), Some(TokenKind::Let)) {
                let stmt = self.parse_let_statement()?;
                statements.push(stmt);
                self.skip_newlines();
                continue;
            }
            let expr = self.parse_expr()?;
            self.skip_newlines();
            // If the next token is `}`, this expression is the block's result.
            if matches!(self.peek(), Some(TokenKind::RBrace)) {
                result = Box::new(expr);
                break;
            }
            statements.push(Statement::Expr(expr));
        }
        self.expect(&TokenKind::RBrace, "to close block")?;
        Ok(Block { statements, result })
    }

    fn parse_let_statement(&mut self) -> Result<Statement, ParseError> {
        self.expect(&TokenKind::Let, "in let")?;
        // `let _ := expr` is the discard idiom (#200). The RHS is
        // still evaluated for its effect, but the result is bound
        // to a synthetic name nothing else references — so the
        // type-checker / VM treat it like a normal let, but user
        // code can't accidentally reach it.
        let name = if matches!(self.peek_skip_newlines(), Some(TokenKind::Underscore)) {
            self.skip_newlines();
            self.bump();
            self.discard_counter += 1;
            format!("__lex_discard_{}", self.discard_counter)
        } else {
            self.expect_ident("after `let`")?
        };
        let ty = if self.eat(&TokenKind::ColonColon) {
            Some(self.parse_type_expr()?)
        } else {
            None
        };
        self.expect(&TokenKind::ColonEq, "in let")?;
        let value = self.parse_expr()?;
        Ok(Statement::Let { name, ty, value })
    }

    // --- expressions ---

    fn parse_expr(&mut self) -> Result<Expr, ParseError> {
        // Recursion gate: every nested expression — match arms,
        // tuple/list/record/block elements, function args, etc. —
        // enters here, so this is the right place to bound depth.
        // Decrement happens whether the inner call succeeds or fails.
        if self.depth >= MAX_DEPTH {
            return Err(ParseError {
                pos: self.current_pos(),
                msg: format!(
                    "expression nests too deeply (max {MAX_DEPTH}); \
                     malformed or hand-crafted input?"),
            });
        }
        self.depth += 1;
        let r = self.parse_expr_inner();
        self.depth -= 1;
        r
    }

    fn parse_expr_inner(&mut self) -> Result<Expr, ParseError> {
        // Pipes are left-associative and bind less tightly than binary ops.
        let mut left = self.parse_binary_expr(0)?;
        while matches!(self.peek_skip_newlines(), Some(TokenKind::Pipe)) {
            self.skip_newlines();
            self.bump();
            let right = self.parse_binary_expr(0)?;
            left = Expr::Pipe { left: Box::new(left), right: Box::new(right) };
        }
        Ok(left)
    }

    fn parse_binary_expr(&mut self, min_prec: u8) -> Result<Expr, ParseError> {
        let mut lhs = self.parse_unary()?;
        loop {
            let op = match self.peek_binop() {
                Some(op) if op.precedence() >= min_prec => op,
                _ => break,
            };
            self.skip_newlines();
            self.bump();
            let rhs = self.parse_binary_expr(op.precedence() + 1)?;
            lhs = Expr::BinOp { op, lhs: Box::new(lhs), rhs: Box::new(rhs) };
        }
        Ok(lhs)
    }

    fn peek_binop(&mut self) -> Option<BinOp> {
        match self.peek_skip_newlines()? {
            TokenKind::Plus => Some(BinOp::Add),
            TokenKind::Minus => Some(BinOp::Sub),
            TokenKind::Star => Some(BinOp::Mul),
            TokenKind::Slash => Some(BinOp::Div),
            TokenKind::Percent => Some(BinOp::Mod),
            TokenKind::EqEq => Some(BinOp::Eq),
            TokenKind::BangEq => Some(BinOp::Neq),
            TokenKind::Lt => Some(BinOp::Lt),
            TokenKind::LtEq => Some(BinOp::Lte),
            TokenKind::Gt => Some(BinOp::Gt),
            TokenKind::GtEq => Some(BinOp::Gte),
            TokenKind::And => Some(BinOp::And),
            TokenKind::Or => Some(BinOp::Or),
            _ => None,
        }
    }

    fn parse_unary(&mut self) -> Result<Expr, ParseError> {
        self.skip_newlines();
        match self.peek() {
            Some(TokenKind::Not) => {
                self.bump();
                let inner = self.parse_unary()?;
                Ok(Expr::UnaryOp { op: UnaryOp::Not, expr: Box::new(inner) })
            }
            Some(TokenKind::Minus) => {
                self.bump();
                let inner = self.parse_unary()?;
                Ok(Expr::UnaryOp { op: UnaryOp::Neg, expr: Box::new(inner) })
            }
            _ => self.parse_postfix(),
        }
    }

    fn parse_postfix(&mut self) -> Result<Expr, ParseError> {
        let mut expr = self.parse_primary()?;
        loop {
            // Postfix operations don't cross newlines (they bind tightly).
            match self.peek() {
                Some(TokenKind::Dot) => {
                    self.bump();
                    let field = self.expect_ident("after `.`")?;
                    expr = Expr::Field { value: Box::new(expr), field };
                }
                Some(TokenKind::LParen) => {
                    self.bump();
                    let mut args = Vec::new();
                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
                        args.push(self.parse_expr()?);
                        while self.eat(&TokenKind::Comma) {
                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                            args.push(self.parse_expr()?);
                        }
                    }
                    self.expect(&TokenKind::RParen, "in call")?;
                    expr = Expr::Call { callee: Box::new(expr), args };
                }
                Some(TokenKind::Question) => {
                    self.bump();
                    expr = Expr::Try(Box::new(expr));
                }
                _ => break,
            }
        }
        Ok(expr)
    }

    fn parse_primary(&mut self) -> Result<Expr, ParseError> {
        self.skip_newlines();
        match self.peek() {
            Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
                TokenKind::Int(n) => Ok(Expr::Lit(Literal::Int(n))),
                _ => unreachable!(),
            },
            Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
                TokenKind::Float(n) => Ok(Expr::Lit(Literal::Float(n))),
                _ => unreachable!(),
            },
            Some(TokenKind::Str(_)) => match self.bump().unwrap().kind {
                TokenKind::Str(s) => Ok(Expr::Lit(Literal::Str(s))),
                _ => unreachable!(),
            },
            Some(TokenKind::Bytes(_)) => match self.bump().unwrap().kind {
                TokenKind::Bytes(b) => Ok(Expr::Lit(Literal::Bytes(b))),
                _ => unreachable!(),
            },
            Some(TokenKind::True) => { self.bump(); Ok(Expr::Lit(Literal::Bool(true))) }
            Some(TokenKind::False) => { self.bump(); Ok(Expr::Lit(Literal::Bool(false))) }
            Some(TokenKind::If) => self.parse_if(),
            Some(TokenKind::Match) => self.parse_match(),
            Some(TokenKind::Fn) => self.parse_lambda(),
            Some(TokenKind::LBrace) => self.parse_brace_expr(),
            Some(TokenKind::LBracket) => self.parse_list_literal(),
            Some(TokenKind::LParen) => self.parse_paren_or_tuple(),
            Some(TokenKind::Ident(_)) => self.parse_ident_or_record(),
            other => Err(self.error(format!("expected expression, got {other:?}"))),
        }
    }

    /// Disambiguate `{` between record literal and block.
    /// Lookahead: `{ Ident :` is a record literal; `{ }` is also a record
    /// (empty block has no use). Anything else is a block.
    fn parse_brace_expr(&mut self) -> Result<Expr, ParseError> {
        // Save position; peek 2-3 tokens past `{` (skipping newlines).
        let saved = self.idx;
        self.bump(); // `{`
        // Skip newlines.
        while matches!(self.peek(), Some(TokenKind::Newline) | Some(TokenKind::Semi)) {
            self.idx += 1;
        }
        let is_record = matches!(self.peek(), Some(TokenKind::RBrace))
            || (matches!(self.peek(), Some(TokenKind::Ident(_)))
                && matches!(self.tokens.get(self.idx + 1).map(|t| &t.kind), Some(TokenKind::Colon) | Some(TokenKind::Comma) | Some(TokenKind::RBrace)));
        self.idx = saved;
        if is_record {
            self.parse_record_literal()
        } else {
            Ok(Expr::Block(self.parse_block()?))
        }
    }

    fn parse_record_literal(&mut self) -> Result<Expr, ParseError> {
        self.expect(&TokenKind::LBrace, "in record literal")?;
        let mut fields = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
            loop {
                self.skip_newlines();
                let name = self.expect_ident("in record literal")?;
                let value = if self.eat(&TokenKind::Colon) {
                    self.parse_expr()?
                } else {
                    // shorthand: `{ name }` => `{ name: name }`
                    Expr::Var(name.clone())
                };
                fields.push(RecordLitField { name, value });
                self.skip_newlines();
                if !self.eat(&TokenKind::Comma) { break; }
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
            }
        }
        self.expect(&TokenKind::RBrace, "after record literal")?;
        Ok(Expr::RecordLit(fields))
    }

    fn parse_if(&mut self) -> Result<Expr, ParseError> {
        self.expect(&TokenKind::If, "in if")?;
        let cond = self.parse_expr()?;
        let then_block = self.parse_block()?;
        self.expect(&TokenKind::Else, "expected `else`")?;
        let else_block = self.parse_block()?;
        Ok(Expr::If { cond: Box::new(cond), then_block, else_block })
    }

    fn parse_match(&mut self) -> Result<Expr, ParseError> {
        self.expect(&TokenKind::Match, "in match")?;
        let scrutinee = self.parse_expr()?;
        self.expect(&TokenKind::LBrace, "before match arms")?;
        let mut arms = Vec::new();
        loop {
            self.skip_newlines();
            if matches!(self.peek(), Some(TokenKind::RBrace)) { break; }
            let pattern = self.parse_pattern()?;
            self.expect(&TokenKind::FatArrow, "in match arm")?;
            let body = self.parse_expr()?;
            arms.push(Arm { pattern, body });
            self.skip_newlines();
            if !self.eat(&TokenKind::Comma) { break; }
        }
        self.expect(&TokenKind::RBrace, "after match arms")?;
        Ok(Expr::Match { scrutinee: Box::new(scrutinee), arms })
    }

    fn parse_lambda(&mut self) -> Result<Expr, ParseError> {
        self.expect(&TokenKind::Fn, "in lambda")?;
        self.expect(&TokenKind::LParen, "before lambda params")?;
        let mut params = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
            params.push(self.parse_param()?);
            while self.eat(&TokenKind::Comma) {
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                params.push(self.parse_param()?);
            }
        }
        self.expect(&TokenKind::RParen, "after lambda params")?;
        self.expect(&TokenKind::Arrow, "before lambda return type")?;
        let effects = self.parse_effects()?;
        let return_type = self.parse_type_expr()?;
        let body = self.parse_block()?;
        Ok(Expr::Lambda(Box::new(Lambda { params, effects, return_type, body })))
    }

    fn parse_list_literal(&mut self) -> Result<Expr, ParseError> {
        self.expect(&TokenKind::LBracket, "before list literal")?;
        let mut items = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) {
            items.push(self.parse_expr()?);
            while self.eat(&TokenKind::Comma) {
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
                items.push(self.parse_expr()?);
            }
        }
        self.expect(&TokenKind::RBracket, "after list literal")?;
        Ok(Expr::ListLit(items))
    }

    fn parse_paren_or_tuple(&mut self) -> Result<Expr, ParseError> {
        self.expect(&TokenKind::LParen, "")?;
        if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
            self.bump();
            return Ok(Expr::Lit(Literal::Unit));
        }
        let first = self.parse_expr()?;
        // Inline type ascription: `(expr :: Type)` — peek for `::` before
        // deciding whether this is a tuple, a grouping, or an ascription.
        if self.eat(&TokenKind::ColonColon) {
            let ty = self.parse_type_expr()?;
            self.expect(&TokenKind::RParen, "after type ascription")?;
            return Ok(Expr::Ascription { value: Box::new(first), ty });
        }
        if self.eat(&TokenKind::Comma) {
            let mut items = vec![first];
            if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
                items.push(self.parse_expr()?);
                while self.eat(&TokenKind::Comma) {
                    if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                    items.push(self.parse_expr()?);
                }
            }
            self.expect(&TokenKind::RParen, "after tuple")?;
            Ok(Expr::TupleLit(items))
        } else {
            self.expect(&TokenKind::RParen, "after parenthesized expression")?;
            Ok(first)
        }
    }

    fn parse_ident_or_record(&mut self) -> Result<Expr, ParseError> {
        // Ident is parsed as a Var; later postfix (`(`, `.`, `?`) attach.
        let name = self.expect_ident("")?;
        Ok(Expr::Var(name))
    }

    // --- patterns ---

    fn parse_pattern(&mut self) -> Result<Pattern, ParseError> {
        self.skip_newlines();
        match self.peek() {
            Some(TokenKind::Minus) => {
                self.bump();
                self.skip_newlines();
                match self.peek() {
                    Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
                        TokenKind::Int(n) => Ok(Pattern::Lit(Literal::Int(-n))),
                        _ => unreachable!(),
                    },
                    Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
                        TokenKind::Float(n) => Ok(Pattern::Lit(Literal::Float(-n))),
                        _ => unreachable!(),
                    },
                    other => Err(self.error(format!("expected Int or Float after `-` in pattern, got {other:?}"))),
                }
            }
            Some(TokenKind::Underscore) => { self.bump(); Ok(Pattern::Wild) }
            Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
                TokenKind::Int(n) => Ok(Pattern::Lit(Literal::Int(n))),
                _ => unreachable!(),
            },
            Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
                TokenKind::Float(n) => Ok(Pattern::Lit(Literal::Float(n))),
                _ => unreachable!(),
            },
            Some(TokenKind::Str(_)) => match self.bump().unwrap().kind {
                TokenKind::Str(s) => Ok(Pattern::Lit(Literal::Str(s))),
                _ => unreachable!(),
            },
            Some(TokenKind::True) => { self.bump(); Ok(Pattern::Lit(Literal::Bool(true))) }
            Some(TokenKind::False) => { self.bump(); Ok(Pattern::Lit(Literal::Bool(false))) }
            Some(TokenKind::LBrace) => self.parse_record_pattern(),
            Some(TokenKind::LParen) => self.parse_tuple_pattern(),
            Some(TokenKind::Ident(_)) => {
                let mut name = self.expect_ident("")?;
                // Handle module-qualified constructor patterns: `module.Constructor(args)`.
                // Strip the qualifier and keep only the final name, matching how the
                // compiler emits MakeVariant with the unqualified constructor name.
                while matches!(self.peek(), Some(TokenKind::Dot)) {
                    self.bump();
                    name = self.expect_ident("after `.` in qualified pattern")?;
                }
                if matches!(self.peek(), Some(TokenKind::LParen)) {
                    self.bump();
                    let mut args = Vec::new();
                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
                        args.push(self.parse_pattern()?);
                        while self.eat(&TokenKind::Comma) {
                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                            args.push(self.parse_pattern()?);
                        }
                    }
                    self.expect(&TokenKind::RParen, "after constructor pattern")?;
                    Ok(Pattern::Constructor { name, args })
                } else {
                    Ok(Pattern::Var(name))
                }
            }
            other => Err(self.error(format!("expected pattern, got {other:?}"))),
        }
    }

    fn parse_record_pattern(&mut self) -> Result<Pattern, ParseError> {
        self.expect(&TokenKind::LBrace, "")?;
        let mut fields = Vec::new();
        let rest = false;
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
            loop {
                self.skip_newlines();
                let name = self.expect_ident("in record pattern")?;
                let pattern = if self.eat(&TokenKind::Colon) {
                    Some(self.parse_pattern()?)
                } else {
                    None
                };
                fields.push(RecordPatField { name, pattern });
                self.skip_newlines();
                if !self.eat(&TokenKind::Comma) { break; }
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
            }
        }
        self.expect(&TokenKind::RBrace, "after record pattern")?;
        Ok(Pattern::Record { fields, rest })
    }

    fn parse_tuple_pattern(&mut self) -> Result<Pattern, ParseError> {
        self.expect(&TokenKind::LParen, "")?;
        let mut items = Vec::new();
        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
            items.push(self.parse_pattern()?);
            while self.eat(&TokenKind::Comma) {
                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
                items.push(self.parse_pattern()?);
            }
        }
        self.expect(&TokenKind::RParen, "after tuple pattern")?;
        if items.len() == 1 {
            Ok(items.into_iter().next().unwrap())
        } else {
            Ok(Pattern::Tuple(items))
        }
    }
}

/// In a union RHS, every leaf must be a `Named` type expression — that is, a
/// PascalCase ident with optional payload via `Variant(payload_type)`.
fn type_to_variant(t: TypeExpr) -> Result<UnionVariant, ParseError> {
    match t {
        TypeExpr::Named { name, args } => {
            let payload = match args.len() {
                0 => None,
                1 => Some(args.into_iter().next().unwrap()),
                _ => Some(TypeExpr::Tuple(args)),
            };
            Ok(UnionVariant { name, payload })
        }
        // `Foo({ field :: T })` parses as Named with one arg = Record. handled above.
        _ => Err(ParseError {
            pos: 0,
            msg: "union variant must be a constructor name".into(),
        }),
    }
}

/// Attach a collected list of `#` comments to whichever top-level
/// item variant carries them. Empty input is a no-op; the per-variant
/// `leading_comments: Vec<String>` field is always present.
fn attach_leading_comments(item: &mut Item, comments: Vec<String>) {
    if comments.is_empty() {
        return;
    }
    match item {
        Item::Import(i) => i.leading_comments = comments,
        Item::TypeDecl(t) => t.leading_comments = comments,
        Item::FnDecl(f) => f.leading_comments = comments,
    }
}