lex_syntax/
parser.rs

1//! Recursive-descent parser for Lex. Pratt-style precedence climbing for
2//! binary operators; everything else is straightforward LL(1)-with-lookahead.
3
4use crate::syntax::*;
5use crate::token::{Token, TokenKind};
6
7pub fn parse(tokens: Vec<Token>) -> Result<Program, ParseError> {
8    let mut p = Parser::new(tokens);
9    let program = p.parse_program()?;
10    p.skip_newlines();
11    if !p.at_eof() {
12        return Err(p.error("unexpected token after program"));
13    }
14    Ok(program)
15}
16
17#[derive(Debug, thiserror::Error)]
18#[error("parse error at byte {pos}: {msg}")]
19pub struct ParseError {
20    pub pos: usize,
21    pub msg: String,
22}
23
24struct Parser {
25    tokens: Vec<Token>,
26    idx: usize,
27    /// Recursion depth across `parse_expr`. Capped at `MAX_DEPTH`
28    /// to defend against adversarial input like a long sequence of
29    /// `[[[{{{...` that would otherwise blow the stack. Found by
30    /// the libFuzzer parser target — see `fuzz/fuzz_targets/parser.rs`.
31    depth: u32,
32    /// Counter for `let _ := ...` discard bindings (#200). Each
33    /// discard gets a unique synthetic name so multiple `let _`
34    /// in the same scope shadow rather than collide. The names
35    /// aren't expressible in user syntax (`__lex_discard_N`),
36    /// so user code can't reference them by accident.
37    discard_counter: u32,
38}
39
40/// Maximum nesting depth the parser will accept before refusing
41/// with a parse error. Real Lex code rarely exceeds 30; 96 leaves
42/// generous headroom for legitimate generated code.
43///
44/// Each `parse_expr` level produces ~4-5 stack frames through the
45/// `parse_binary_expr → parse_unary_expr → parse_postfix →
46/// parse_primary → ...` chain, so this caps the actual frame
47/// count around 400-500 — well below even a 2 MiB test stack.
48const MAX_DEPTH: u32 = 96;
49
50impl Parser {
51    fn new(tokens: Vec<Token>) -> Self {
52        Self { tokens, idx: 0, depth: 0, discard_counter: 0 }
53    }
54
55    fn at_eof(&self) -> bool {
56        self.idx >= self.tokens.len()
57    }
58
59    fn peek(&self) -> Option<&TokenKind> {
60        self.tokens.get(self.idx).map(|t| &t.kind)
61    }
62
63    fn bump(&mut self) -> Option<Token> {
64        let t = self.tokens.get(self.idx).cloned();
65        if t.is_some() {
66            self.idx += 1;
67        }
68        t
69    }
70
71    fn current_pos(&self) -> usize {
72        self.tokens
73            .get(self.idx)
74            .map(|t| t.span.start)
75            .unwrap_or_else(|| self.tokens.last().map(|t| t.span.end).unwrap_or(0))
76    }
77
78    fn error(&self, msg: impl Into<String>) -> ParseError {
79        ParseError { pos: self.current_pos(), msg: msg.into() }
80    }
81
82    fn skip_newlines(&mut self) {
83        while matches!(self.peek(), Some(TokenKind::Newline) | Some(TokenKind::Semi)) {
84            self.idx += 1;
85        }
86    }
87
88    fn expect(&mut self, expected: &TokenKind, ctx: &str) -> Result<Token, ParseError> {
89        self.skip_newlines();
90        match self.peek() {
91            Some(k) if std::mem::discriminant(k) == std::mem::discriminant(expected) => {
92                Ok(self.bump().unwrap())
93            }
94            Some(other) => Err(self.error(format!(
95                "expected {expected:?} {ctx}, got {other:?}"
96            ))),
97            None => Err(self.error(format!("expected {expected:?} {ctx}, got EOF"))),
98        }
99    }
100
101    fn eat(&mut self, k: &TokenKind) -> bool {
102        self.skip_newlines();
103        if let Some(cur) = self.peek() {
104            if std::mem::discriminant(cur) == std::mem::discriminant(k) {
105                self.bump();
106                return true;
107            }
108        }
109        false
110    }
111
112    fn expect_ident(&mut self, ctx: &str) -> Result<String, ParseError> {
113        self.skip_newlines();
114        match self.peek() {
115            Some(TokenKind::Ident(_)) => match self.bump().unwrap().kind {
116                TokenKind::Ident(name) => Ok(name),
117                _ => unreachable!(),
118            },
119            other => Err(self.error(format!("expected identifier {ctx}, got {other:?}"))),
120        }
121    }
122
123    // --- top level ---
124
125    fn parse_program(&mut self) -> Result<Program, ParseError> {
126        let mut items = Vec::new();
127        loop {
128            self.skip_newlines();
129            if self.at_eof() {
130                break;
131            }
132            items.push(self.parse_item()?);
133        }
134        Ok(Program { items })
135    }
136
137    fn parse_item(&mut self) -> Result<Item, ParseError> {
138        match self.peek() {
139            Some(TokenKind::Import) => self.parse_import().map(Item::Import),
140            Some(TokenKind::Type) => self.parse_type_decl().map(Item::TypeDecl),
141            Some(TokenKind::Fn) => self.parse_fn_decl().map(Item::FnDecl),
142            other => Err(self.error(format!(
143                "expected `import`, `type`, or `fn` at top level, got {other:?}"
144            ))),
145        }
146    }
147
148    fn parse_import(&mut self) -> Result<Import, ParseError> {
149        self.expect(&TokenKind::Import, "in import")?;
150        let reference = match self.bump().map(|t| t.kind) {
151            Some(TokenKind::Str(s)) => s,
152            other => return Err(self.error(format!("expected string after `import`, got {other:?}"))),
153        };
154        self.expect(&TokenKind::As, "in import")?;
155        let alias = self.expect_ident("for import alias")?;
156        Ok(Import { reference, alias })
157    }
158
159    fn parse_type_decl(&mut self) -> Result<TypeDecl, ParseError> {
160        self.expect(&TokenKind::Type, "in type decl")?;
161        let name = self.expect_ident("for type name")?;
162        let params = if self.eat(&TokenKind::LBracket) {
163            let ps = self.parse_ident_list()?;
164            self.expect(&TokenKind::RBracket, "after type params")?;
165            ps
166        } else {
167            Vec::new()
168        };
169        self.expect(&TokenKind::Eq, "in type decl")?;
170        let definition = self.parse_type_decl_rhs()?;
171        Ok(TypeDecl { name, params, definition })
172    }
173
174    fn parse_ident_list(&mut self) -> Result<Vec<String>, ParseError> {
175        let mut out = Vec::new();
176        out.push(self.expect_ident("in identifier list")?);
177        while self.eat(&TokenKind::Comma) {
178            if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
179            out.push(self.expect_ident("in identifier list")?);
180        }
181        Ok(out)
182    }
183
184    /// `type Foo = Variant1 | Variant2(Payload)` is a union; otherwise a plain type expression.
185    fn parse_type_decl_rhs(&mut self) -> Result<TypeExpr, ParseError> {
186        let first = self.parse_type_expr()?;
187        // Detect union: PascalCase ident (or named type w/ optional payload) followed by `|`.
188        if matches!(self.peek_skip_newlines(), Some(TokenKind::Bar)) {
189            let mut variants = Vec::new();
190            variants.push(type_to_variant(first)?);
191            while self.eat(&TokenKind::Bar) {
192                let next = self.parse_type_expr()?;
193                variants.push(type_to_variant(next)?);
194            }
195            Ok(TypeExpr::Union(variants))
196        } else {
197            Ok(first)
198        }
199    }
200
201    fn peek_skip_newlines(&mut self) -> Option<TokenKind> {
202        let saved = self.idx;
203        self.skip_newlines();
204        let out = self.peek().cloned();
205        self.idx = saved;
206        out
207    }
208
209    fn parse_type_expr(&mut self) -> Result<TypeExpr, ParseError> {
210        let base = self.parse_type_expr_base()?;
211        self.maybe_wrap_refinement(base)
212    }
213
214    fn parse_type_expr_base(&mut self) -> Result<TypeExpr, ParseError> {
215        self.skip_newlines();
216        match self.peek() {
217            Some(TokenKind::LBrace) => self.parse_record_type(),
218            Some(TokenKind::LParen) => self.parse_paren_type_or_function(),
219            Some(TokenKind::Ident(_)) => {
220                let mut name = self.expect_ident("in type expr")?;
221                // Module-qualified type: `m.Type` or `m.n.Type`. We accept
222                // dotted names here and let the loader rewrite them to the
223                // file-local mangled form. After the loader pass, all type
224                // names referenced by the type checker are single segments.
225                while matches!(self.peek(), Some(TokenKind::Dot)) {
226                    self.bump();
227                    let next = self.expect_ident("after `.` in qualified type")?;
228                    name.push('.');
229                    name.push_str(&next);
230                }
231                let args = if matches!(self.peek(), Some(TokenKind::LBracket)) {
232                    self.bump();
233                    let mut args = Vec::new();
234                    args.push(self.parse_type_expr()?);
235                    while self.eat(&TokenKind::Comma) {
236                        if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
237                        args.push(self.parse_type_expr()?);
238                    }
239                    self.expect(&TokenKind::RBracket, "after type args")?;
240                    args
241                } else if matches!(self.peek(), Some(TokenKind::LParen)) {
242                    // Constructor type with payload: `Name(T)` or `Name(T1, T2)`.
243                    self.bump();
244                    let mut args = Vec::new();
245                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
246                        args.push(self.parse_type_expr()?);
247                        while self.eat(&TokenKind::Comma) {
248                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
249                            args.push(self.parse_type_expr()?);
250                        }
251                    }
252                    self.expect(&TokenKind::RParen, "after constructor payload")?;
253                    args
254                } else {
255                    Vec::new()
256                };
257                Ok(TypeExpr::Named { name, args })
258            }
259            other => Err(self.error(format!("expected type expression, got {other:?}"))),
260        }
261    }
262
263    /// Refinement type postfix (#209): `BaseType{binding | predicate}`.
264    ///
265    /// Disambiguates from a function body's opening brace by peeking
266    /// three tokens ahead — refinement requires `{ Ident |`, a body
267    /// begins with `{ <expr-starting-token>`. This means a refinement
268    /// binding name can't start with `|`, but that's fine since
269    /// identifiers don't.
270    fn maybe_wrap_refinement(&mut self, base: TypeExpr) -> Result<TypeExpr, ParseError> {
271        let next0 = self.tokens.get(self.idx).map(|t| &t.kind);
272        let next1 = self.tokens.get(self.idx + 1).map(|t| &t.kind);
273        let next2 = self.tokens.get(self.idx + 2).map(|t| &t.kind);
274        let is_refinement_lookahead = matches!(next0, Some(TokenKind::LBrace))
275            && matches!(next1, Some(TokenKind::Ident(_)))
276            && matches!(next2, Some(TokenKind::Bar));
277        if !is_refinement_lookahead {
278            return Ok(base);
279        }
280        self.bump(); // `{`
281        let binding = self.expect_ident("for refinement binding")?;
282        self.expect(&TokenKind::Bar, "after refinement binding")?;
283        let predicate = self.parse_expr()?;
284        self.expect(&TokenKind::RBrace, "to close refinement")?;
285        Ok(TypeExpr::Refined {
286            base: Box::new(base),
287            binding,
288            predicate: Box::new(predicate),
289        })
290    }
291
292    fn parse_record_type(&mut self) -> Result<TypeExpr, ParseError> {
293        self.expect(&TokenKind::LBrace, "in record type")?;
294        let mut fields = Vec::new();
295        let mut spreads = Vec::new();
296        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
297            loop {
298                self.skip_newlines();
299                if matches!(self.peek(), Some(TokenKind::DotDotDot)) {
300                    self.bump(); // consume `...`
301                    let name = self.expect_ident("after `...` in record type spread")?;
302                    spreads.push(name);
303                } else {
304                    let name = self.expect_ident("in record field")?;
305                    self.expect(&TokenKind::ColonColon, "after record field name")?;
306                    let ty = self.parse_type_expr()?;
307                    fields.push(TypeField { name, ty });
308                }
309                self.skip_newlines();
310                if !self.eat(&TokenKind::Comma) { break; }
311                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
312            }
313        }
314        self.expect(&TokenKind::RBrace, "in record type")?;
315        if spreads.is_empty() {
316            Ok(TypeExpr::Record(fields))
317        } else {
318            Ok(TypeExpr::RecordWithSpreads { spreads, fields })
319        }
320    }
321
322    fn parse_paren_type_or_function(&mut self) -> Result<TypeExpr, ParseError> {
323        self.expect(&TokenKind::LParen, "in type")?;
324        let mut args = Vec::new();
325        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
326            args.push(self.parse_type_expr()?);
327            while self.eat(&TokenKind::Comma) {
328                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
329                args.push(self.parse_type_expr()?);
330            }
331        }
332        self.expect(&TokenKind::RParen, "in type")?;
333        // Function type if followed by `->`.
334        if matches!(self.peek_skip_newlines(), Some(TokenKind::Arrow)) {
335            self.skip_newlines();
336            self.bump();
337            let effects = self.parse_effects()?;
338            let ret = self.parse_type_expr()?;
339            Ok(TypeExpr::Function {
340                params: args,
341                effects,
342                ret: Box::new(ret),
343            })
344        } else if args.len() == 1 {
345            // Parenthesized type expression.
346            Ok(args.into_iter().next().unwrap())
347        } else {
348            Ok(TypeExpr::Tuple(args))
349        }
350    }
351
352    fn parse_fn_decl(&mut self) -> Result<FnDecl, ParseError> {
353        self.expect(&TokenKind::Fn, "in fn decl")?;
354        let name = self.expect_ident("for function name")?;
355        let type_params = if self.eat(&TokenKind::LBracket) {
356            let ps = self.parse_ident_list()?;
357            self.expect(&TokenKind::RBracket, "after type params")?;
358            ps
359        } else {
360            Vec::new()
361        };
362        self.expect(&TokenKind::LParen, "before params")?;
363        let mut params = Vec::new();
364        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
365            params.push(self.parse_param()?);
366            while self.eat(&TokenKind::Comma) {
367                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
368                params.push(self.parse_param()?);
369            }
370        }
371        self.expect(&TokenKind::RParen, "after params")?;
372        self.expect(&TokenKind::Arrow, "before return type")?;
373        let effects = self.parse_effects()?;
374        let return_type = self.parse_type_expr()?;
375        let examples = self.parse_examples_block()?;
376        let body = self.parse_block()?;
377        Ok(FnDecl { name, type_params, params, effects, return_type, body, examples })
378    }
379
380    /// Parse an optional `examples { call(a, b) => expected, ... }` block
381    /// sitting between the return type and the body (#369). Returns an
382    /// empty vec when no block is present.
383    fn parse_examples_block(&mut self) -> Result<Vec<Example>, ParseError> {
384        // Contextual: not a reserved keyword. Peek for the literal
385        // identifier `examples` followed by `{`; otherwise no block.
386        let is_examples_kw = matches!(
387            self.peek_skip_newlines(),
388            Some(TokenKind::Ident(s)) if s == "examples"
389        );
390        if !is_examples_kw {
391            return Ok(Vec::new());
392        }
393        self.skip_newlines();
394        self.bump(); // consume `examples`
395        self.expect(&TokenKind::LBrace, "after `examples`")?;
396        let mut cases = Vec::new();
397        loop {
398            self.skip_newlines();
399            if matches!(self.peek(), Some(TokenKind::RBrace)) { break; }
400            let call = self.parse_expr()?;
401            self.expect(&TokenKind::FatArrow, "in example case (between call and expected)")?;
402            let expected = self.parse_expr()?;
403            let (args, _) = match call {
404                Expr::Call { callee: _, args } => (args, ()),
405                other => return Err(self.error(
406                    format!("example case must be a call to the function under definition; got {other:?}")
407                )),
408            };
409            cases.push(Example { args, expected });
410            self.skip_newlines();
411            if !self.eat(&TokenKind::Comma) {
412                self.skip_newlines();
413                break;
414            }
415        }
416        self.expect(&TokenKind::RBrace, "to close examples block")?;
417        Ok(cases)
418    }
419
420    fn parse_param(&mut self) -> Result<Param, ParseError> {
421        let name = if matches!(self.peek_skip_newlines(), Some(TokenKind::Underscore)) {
422            self.skip_newlines();
423            self.bump();
424            self.discard_counter += 1;
425            format!("__lex_discard_{}", self.discard_counter)
426        } else {
427            self.expect_ident("for parameter name")?
428        };
429        self.expect(&TokenKind::ColonColon, "after parameter name")?;
430        let ty = self.parse_type_expr()?;
431        Ok(Param { name, ty })
432    }
433
434    fn parse_effects(&mut self) -> Result<Vec<Effect>, ParseError> {
435        if !self.eat(&TokenKind::LBracket) {
436            return Ok(Vec::new());
437        }
438        let mut out = Vec::new();
439        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) {
440            out.push(self.parse_effect()?);
441            while self.eat(&TokenKind::Comma) {
442                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
443                out.push(self.parse_effect()?);
444            }
445        }
446        self.expect(&TokenKind::RBracket, "after effects")?;
447        Ok(out)
448    }
449
450    fn parse_effect(&mut self) -> Result<Effect, ParseError> {
451        let name = self.expect_ident("for effect name")?;
452        let arg = if self.eat(&TokenKind::LParen) {
453            let arg = match self.bump().map(|t| t.kind) {
454                Some(TokenKind::Str(s)) => EffectArg::Str(s),
455                Some(TokenKind::Int(n)) => EffectArg::Int(n),
456                Some(TokenKind::Ident(s)) => EffectArg::Ident(s),
457                other => return Err(self.error(format!("invalid effect arg: {other:?}"))),
458            };
459            self.expect(&TokenKind::RParen, "after effect arg")?;
460            Some(arg)
461        } else {
462            None
463        };
464        Ok(Effect { name, arg })
465    }
466
467    // --- blocks and statements ---
468
469    fn parse_block(&mut self) -> Result<Block, ParseError> {
470        self.expect(&TokenKind::LBrace, "before block")?;
471        let mut statements = Vec::new();
472        let result;
473        loop {
474            self.skip_newlines();
475            if matches!(self.peek(), Some(TokenKind::RBrace)) {
476                // Empty block: synthesize Unit literal.
477                result = Box::new(Expr::Lit(Literal::Unit));
478                break;
479            }
480            // Try parsing a let; otherwise an expression.
481            if matches!(self.peek(), Some(TokenKind::Let)) {
482                let stmt = self.parse_let_statement()?;
483                statements.push(stmt);
484                self.skip_newlines();
485                continue;
486            }
487            let expr = self.parse_expr()?;
488            self.skip_newlines();
489            // If the next token is `}`, this expression is the block's result.
490            if matches!(self.peek(), Some(TokenKind::RBrace)) {
491                result = Box::new(expr);
492                break;
493            }
494            statements.push(Statement::Expr(expr));
495        }
496        self.expect(&TokenKind::RBrace, "to close block")?;
497        Ok(Block { statements, result })
498    }
499
500    fn parse_let_statement(&mut self) -> Result<Statement, ParseError> {
501        self.expect(&TokenKind::Let, "in let")?;
502        // `let _ := expr` is the discard idiom (#200). The RHS is
503        // still evaluated for its effect, but the result is bound
504        // to a synthetic name nothing else references — so the
505        // type-checker / VM treat it like a normal let, but user
506        // code can't accidentally reach it.
507        let name = if matches!(self.peek_skip_newlines(), Some(TokenKind::Underscore)) {
508            self.skip_newlines();
509            self.bump();
510            self.discard_counter += 1;
511            format!("__lex_discard_{}", self.discard_counter)
512        } else {
513            self.expect_ident("after `let`")?
514        };
515        let ty = if self.eat(&TokenKind::ColonColon) {
516            Some(self.parse_type_expr()?)
517        } else {
518            None
519        };
520        self.expect(&TokenKind::ColonEq, "in let")?;
521        let value = self.parse_expr()?;
522        Ok(Statement::Let { name, ty, value })
523    }
524
525    // --- expressions ---
526
527    fn parse_expr(&mut self) -> Result<Expr, ParseError> {
528        // Recursion gate: every nested expression — match arms,
529        // tuple/list/record/block elements, function args, etc. —
530        // enters here, so this is the right place to bound depth.
531        // Decrement happens whether the inner call succeeds or fails.
532        if self.depth >= MAX_DEPTH {
533            return Err(ParseError {
534                pos: self.current_pos(),
535                msg: format!(
536                    "expression nests too deeply (max {MAX_DEPTH}); \
537                     malformed or hand-crafted input?"),
538            });
539        }
540        self.depth += 1;
541        let r = self.parse_expr_inner();
542        self.depth -= 1;
543        r
544    }
545
546    fn parse_expr_inner(&mut self) -> Result<Expr, ParseError> {
547        // Pipes are left-associative and bind less tightly than binary ops.
548        let mut left = self.parse_binary_expr(0)?;
549        while matches!(self.peek_skip_newlines(), Some(TokenKind::Pipe)) {
550            self.skip_newlines();
551            self.bump();
552            let right = self.parse_binary_expr(0)?;
553            left = Expr::Pipe { left: Box::new(left), right: Box::new(right) };
554        }
555        Ok(left)
556    }
557
558    fn parse_binary_expr(&mut self, min_prec: u8) -> Result<Expr, ParseError> {
559        let mut lhs = self.parse_unary()?;
560        loop {
561            let op = match self.peek_binop() {
562                Some(op) if op.precedence() >= min_prec => op,
563                _ => break,
564            };
565            self.skip_newlines();
566            self.bump();
567            let rhs = self.parse_binary_expr(op.precedence() + 1)?;
568            lhs = Expr::BinOp { op, lhs: Box::new(lhs), rhs: Box::new(rhs) };
569        }
570        Ok(lhs)
571    }
572
573    fn peek_binop(&mut self) -> Option<BinOp> {
574        match self.peek_skip_newlines()? {
575            TokenKind::Plus => Some(BinOp::Add),
576            TokenKind::Minus => Some(BinOp::Sub),
577            TokenKind::Star => Some(BinOp::Mul),
578            TokenKind::Slash => Some(BinOp::Div),
579            TokenKind::Percent => Some(BinOp::Mod),
580            TokenKind::EqEq => Some(BinOp::Eq),
581            TokenKind::BangEq => Some(BinOp::Neq),
582            TokenKind::Lt => Some(BinOp::Lt),
583            TokenKind::LtEq => Some(BinOp::Lte),
584            TokenKind::Gt => Some(BinOp::Gt),
585            TokenKind::GtEq => Some(BinOp::Gte),
586            TokenKind::And => Some(BinOp::And),
587            TokenKind::Or => Some(BinOp::Or),
588            _ => None,
589        }
590    }
591
592    fn parse_unary(&mut self) -> Result<Expr, ParseError> {
593        self.skip_newlines();
594        match self.peek() {
595            Some(TokenKind::Not) => {
596                self.bump();
597                let inner = self.parse_unary()?;
598                Ok(Expr::UnaryOp { op: UnaryOp::Not, expr: Box::new(inner) })
599            }
600            Some(TokenKind::Minus) => {
601                self.bump();
602                let inner = self.parse_unary()?;
603                Ok(Expr::UnaryOp { op: UnaryOp::Neg, expr: Box::new(inner) })
604            }
605            _ => self.parse_postfix(),
606        }
607    }
608
609    fn parse_postfix(&mut self) -> Result<Expr, ParseError> {
610        let mut expr = self.parse_primary()?;
611        loop {
612            // Postfix operations don't cross newlines (they bind tightly).
613            match self.peek() {
614                Some(TokenKind::Dot) => {
615                    self.bump();
616                    let field = self.expect_ident("after `.`")?;
617                    expr = Expr::Field { value: Box::new(expr), field };
618                }
619                Some(TokenKind::LParen) => {
620                    self.bump();
621                    let mut args = Vec::new();
622                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
623                        args.push(self.parse_expr()?);
624                        while self.eat(&TokenKind::Comma) {
625                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
626                            args.push(self.parse_expr()?);
627                        }
628                    }
629                    self.expect(&TokenKind::RParen, "in call")?;
630                    expr = Expr::Call { callee: Box::new(expr), args };
631                }
632                Some(TokenKind::Question) => {
633                    self.bump();
634                    expr = Expr::Try(Box::new(expr));
635                }
636                _ => break,
637            }
638        }
639        Ok(expr)
640    }
641
642    fn parse_primary(&mut self) -> Result<Expr, ParseError> {
643        self.skip_newlines();
644        match self.peek() {
645            Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
646                TokenKind::Int(n) => Ok(Expr::Lit(Literal::Int(n))),
647                _ => unreachable!(),
648            },
649            Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
650                TokenKind::Float(n) => Ok(Expr::Lit(Literal::Float(n))),
651                _ => unreachable!(),
652            },
653            Some(TokenKind::Str(_)) => match self.bump().unwrap().kind {
654                TokenKind::Str(s) => Ok(Expr::Lit(Literal::Str(s))),
655                _ => unreachable!(),
656            },
657            Some(TokenKind::Bytes(_)) => match self.bump().unwrap().kind {
658                TokenKind::Bytes(b) => Ok(Expr::Lit(Literal::Bytes(b))),
659                _ => unreachable!(),
660            },
661            Some(TokenKind::True) => { self.bump(); Ok(Expr::Lit(Literal::Bool(true))) }
662            Some(TokenKind::False) => { self.bump(); Ok(Expr::Lit(Literal::Bool(false))) }
663            Some(TokenKind::If) => self.parse_if(),
664            Some(TokenKind::Match) => self.parse_match(),
665            Some(TokenKind::Fn) => self.parse_lambda(),
666            Some(TokenKind::LBrace) => self.parse_brace_expr(),
667            Some(TokenKind::LBracket) => self.parse_list_literal(),
668            Some(TokenKind::LParen) => self.parse_paren_or_tuple(),
669            Some(TokenKind::Ident(_)) => self.parse_ident_or_record(),
670            other => Err(self.error(format!("expected expression, got {other:?}"))),
671        }
672    }
673
674    /// Disambiguate `{` between record literal and block.
675    /// Lookahead: `{ Ident :` is a record literal; `{ }` is also a record
676    /// (empty block has no use). Anything else is a block.
677    fn parse_brace_expr(&mut self) -> Result<Expr, ParseError> {
678        // Save position; peek 2-3 tokens past `{` (skipping newlines).
679        let saved = self.idx;
680        self.bump(); // `{`
681        // Skip newlines.
682        while matches!(self.peek(), Some(TokenKind::Newline) | Some(TokenKind::Semi)) {
683            self.idx += 1;
684        }
685        let is_record = matches!(self.peek(), Some(TokenKind::RBrace))
686            || (matches!(self.peek(), Some(TokenKind::Ident(_)))
687                && matches!(self.tokens.get(self.idx + 1).map(|t| &t.kind), Some(TokenKind::Colon) | Some(TokenKind::Comma) | Some(TokenKind::RBrace)));
688        self.idx = saved;
689        if is_record {
690            self.parse_record_literal()
691        } else {
692            Ok(Expr::Block(self.parse_block()?))
693        }
694    }
695
696    fn parse_record_literal(&mut self) -> Result<Expr, ParseError> {
697        self.expect(&TokenKind::LBrace, "in record literal")?;
698        let mut fields = Vec::new();
699        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
700            loop {
701                self.skip_newlines();
702                let name = self.expect_ident("in record literal")?;
703                let value = if self.eat(&TokenKind::Colon) {
704                    self.parse_expr()?
705                } else {
706                    // shorthand: `{ name }` => `{ name: name }`
707                    Expr::Var(name.clone())
708                };
709                fields.push(RecordLitField { name, value });
710                self.skip_newlines();
711                if !self.eat(&TokenKind::Comma) { break; }
712                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
713            }
714        }
715        self.expect(&TokenKind::RBrace, "after record literal")?;
716        Ok(Expr::RecordLit(fields))
717    }
718
719    fn parse_if(&mut self) -> Result<Expr, ParseError> {
720        self.expect(&TokenKind::If, "in if")?;
721        let cond = self.parse_expr()?;
722        let then_block = self.parse_block()?;
723        self.expect(&TokenKind::Else, "expected `else`")?;
724        let else_block = self.parse_block()?;
725        Ok(Expr::If { cond: Box::new(cond), then_block, else_block })
726    }
727
728    fn parse_match(&mut self) -> Result<Expr, ParseError> {
729        self.expect(&TokenKind::Match, "in match")?;
730        let scrutinee = self.parse_expr()?;
731        self.expect(&TokenKind::LBrace, "before match arms")?;
732        let mut arms = Vec::new();
733        loop {
734            self.skip_newlines();
735            if matches!(self.peek(), Some(TokenKind::RBrace)) { break; }
736            let pattern = self.parse_pattern()?;
737            self.expect(&TokenKind::FatArrow, "in match arm")?;
738            let body = self.parse_expr()?;
739            arms.push(Arm { pattern, body });
740            self.skip_newlines();
741            if !self.eat(&TokenKind::Comma) { break; }
742        }
743        self.expect(&TokenKind::RBrace, "after match arms")?;
744        Ok(Expr::Match { scrutinee: Box::new(scrutinee), arms })
745    }
746
747    fn parse_lambda(&mut self) -> Result<Expr, ParseError> {
748        self.expect(&TokenKind::Fn, "in lambda")?;
749        self.expect(&TokenKind::LParen, "before lambda params")?;
750        let mut params = Vec::new();
751        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
752            params.push(self.parse_param()?);
753            while self.eat(&TokenKind::Comma) {
754                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
755                params.push(self.parse_param()?);
756            }
757        }
758        self.expect(&TokenKind::RParen, "after lambda params")?;
759        self.expect(&TokenKind::Arrow, "before lambda return type")?;
760        let effects = self.parse_effects()?;
761        let return_type = self.parse_type_expr()?;
762        let body = self.parse_block()?;
763        Ok(Expr::Lambda(Box::new(Lambda { params, effects, return_type, body })))
764    }
765
766    fn parse_list_literal(&mut self) -> Result<Expr, ParseError> {
767        self.expect(&TokenKind::LBracket, "before list literal")?;
768        let mut items = Vec::new();
769        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) {
770            items.push(self.parse_expr()?);
771            while self.eat(&TokenKind::Comma) {
772                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
773                items.push(self.parse_expr()?);
774            }
775        }
776        self.expect(&TokenKind::RBracket, "after list literal")?;
777        Ok(Expr::ListLit(items))
778    }
779
780    fn parse_paren_or_tuple(&mut self) -> Result<Expr, ParseError> {
781        self.expect(&TokenKind::LParen, "")?;
782        if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
783            self.bump();
784            return Ok(Expr::Lit(Literal::Unit));
785        }
786        let first = self.parse_expr()?;
787        // Inline type ascription: `(expr :: Type)` — peek for `::` before
788        // deciding whether this is a tuple, a grouping, or an ascription.
789        if self.eat(&TokenKind::ColonColon) {
790            let ty = self.parse_type_expr()?;
791            self.expect(&TokenKind::RParen, "after type ascription")?;
792            return Ok(Expr::Ascription { value: Box::new(first), ty });
793        }
794        if self.eat(&TokenKind::Comma) {
795            let mut items = vec![first];
796            if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
797                items.push(self.parse_expr()?);
798                while self.eat(&TokenKind::Comma) {
799                    if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
800                    items.push(self.parse_expr()?);
801                }
802            }
803            self.expect(&TokenKind::RParen, "after tuple")?;
804            Ok(Expr::TupleLit(items))
805        } else {
806            self.expect(&TokenKind::RParen, "after parenthesized expression")?;
807            Ok(first)
808        }
809    }
810
811    fn parse_ident_or_record(&mut self) -> Result<Expr, ParseError> {
812        // Ident is parsed as a Var; later postfix (`(`, `.`, `?`) attach.
813        let name = self.expect_ident("")?;
814        Ok(Expr::Var(name))
815    }
816
817    // --- patterns ---
818
819    fn parse_pattern(&mut self) -> Result<Pattern, ParseError> {
820        self.skip_newlines();
821        match self.peek() {
822            Some(TokenKind::Minus) => {
823                self.bump();
824                self.skip_newlines();
825                match self.peek() {
826                    Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
827                        TokenKind::Int(n) => Ok(Pattern::Lit(Literal::Int(-n))),
828                        _ => unreachable!(),
829                    },
830                    Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
831                        TokenKind::Float(n) => Ok(Pattern::Lit(Literal::Float(-n))),
832                        _ => unreachable!(),
833                    },
834                    other => Err(self.error(format!("expected Int or Float after `-` in pattern, got {other:?}"))),
835                }
836            }
837            Some(TokenKind::Underscore) => { self.bump(); Ok(Pattern::Wild) }
838            Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
839                TokenKind::Int(n) => Ok(Pattern::Lit(Literal::Int(n))),
840                _ => unreachable!(),
841            },
842            Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
843                TokenKind::Float(n) => Ok(Pattern::Lit(Literal::Float(n))),
844                _ => unreachable!(),
845            },
846            Some(TokenKind::Str(_)) => match self.bump().unwrap().kind {
847                TokenKind::Str(s) => Ok(Pattern::Lit(Literal::Str(s))),
848                _ => unreachable!(),
849            },
850            Some(TokenKind::True) => { self.bump(); Ok(Pattern::Lit(Literal::Bool(true))) }
851            Some(TokenKind::False) => { self.bump(); Ok(Pattern::Lit(Literal::Bool(false))) }
852            Some(TokenKind::LBrace) => self.parse_record_pattern(),
853            Some(TokenKind::LParen) => self.parse_tuple_pattern(),
854            Some(TokenKind::Ident(_)) => {
855                let name = self.expect_ident("")?;
856                if matches!(self.peek(), Some(TokenKind::LParen)) {
857                    self.bump();
858                    let mut args = Vec::new();
859                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
860                        args.push(self.parse_pattern()?);
861                        while self.eat(&TokenKind::Comma) {
862                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
863                            args.push(self.parse_pattern()?);
864                        }
865                    }
866                    self.expect(&TokenKind::RParen, "after constructor pattern")?;
867                    Ok(Pattern::Constructor { name, args })
868                } else {
869                    Ok(Pattern::Var(name))
870                }
871            }
872            other => Err(self.error(format!("expected pattern, got {other:?}"))),
873        }
874    }
875
876    fn parse_record_pattern(&mut self) -> Result<Pattern, ParseError> {
877        self.expect(&TokenKind::LBrace, "")?;
878        let mut fields = Vec::new();
879        let rest = false;
880        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
881            loop {
882                self.skip_newlines();
883                let name = self.expect_ident("in record pattern")?;
884                let pattern = if self.eat(&TokenKind::Colon) {
885                    Some(self.parse_pattern()?)
886                } else {
887                    None
888                };
889                fields.push(RecordPatField { name, pattern });
890                self.skip_newlines();
891                if !self.eat(&TokenKind::Comma) { break; }
892                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
893            }
894        }
895        self.expect(&TokenKind::RBrace, "after record pattern")?;
896        Ok(Pattern::Record { fields, rest })
897    }
898
899    fn parse_tuple_pattern(&mut self) -> Result<Pattern, ParseError> {
900        self.expect(&TokenKind::LParen, "")?;
901        let mut items = Vec::new();
902        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
903            items.push(self.parse_pattern()?);
904            while self.eat(&TokenKind::Comma) {
905                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
906                items.push(self.parse_pattern()?);
907            }
908        }
909        self.expect(&TokenKind::RParen, "after tuple pattern")?;
910        if items.len() == 1 {
911            Ok(items.into_iter().next().unwrap())
912        } else {
913            Ok(Pattern::Tuple(items))
914        }
915    }
916}
917
918/// In a union RHS, every leaf must be a `Named` type expression — that is, a
919/// PascalCase ident with optional payload via `Variant(payload_type)`.
920fn type_to_variant(t: TypeExpr) -> Result<UnionVariant, ParseError> {
921    match t {
922        TypeExpr::Named { name, args } => {
923            let payload = match args.len() {
924                0 => None,
925                1 => Some(args.into_iter().next().unwrap()),
926                _ => Some(TypeExpr::Tuple(args)),
927            };
928            Ok(UnionVariant { name, payload })
929        }
930        // `Foo({ field :: T })` parses as Named with one arg = Record. handled above.
931        _ => Err(ParseError {
932            pos: 0,
933            msg: "union variant must be a constructor name".into(),
934        }),
935    }
936}
lex_syntax/parser.rs

lex_syntax/
parser.rs
