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        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
296            loop {
297                self.skip_newlines();
298                let name = self.expect_ident("in record field")?;
299                self.expect(&TokenKind::ColonColon, "after record field name")?;
300                let ty = self.parse_type_expr()?;
301                fields.push(TypeField { name, ty });
302                self.skip_newlines();
303                if !self.eat(&TokenKind::Comma) { break; }
304                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
305            }
306        }
307        self.expect(&TokenKind::RBrace, "in record type")?;
308        Ok(TypeExpr::Record(fields))
309    }
310
311    fn parse_paren_type_or_function(&mut self) -> Result<TypeExpr, ParseError> {
312        self.expect(&TokenKind::LParen, "in type")?;
313        let mut args = Vec::new();
314        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
315            args.push(self.parse_type_expr()?);
316            while self.eat(&TokenKind::Comma) {
317                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
318                args.push(self.parse_type_expr()?);
319            }
320        }
321        self.expect(&TokenKind::RParen, "in type")?;
322        // Function type if followed by `->`.
323        if matches!(self.peek_skip_newlines(), Some(TokenKind::Arrow)) {
324            self.skip_newlines();
325            self.bump();
326            let effects = self.parse_effects()?;
327            let ret = self.parse_type_expr()?;
328            Ok(TypeExpr::Function {
329                params: args,
330                effects,
331                ret: Box::new(ret),
332            })
333        } else if args.len() == 1 {
334            // Parenthesized type expression.
335            Ok(args.into_iter().next().unwrap())
336        } else {
337            Ok(TypeExpr::Tuple(args))
338        }
339    }
340
341    fn parse_fn_decl(&mut self) -> Result<FnDecl, ParseError> {
342        self.expect(&TokenKind::Fn, "in fn decl")?;
343        let name = self.expect_ident("for function name")?;
344        let type_params = if self.eat(&TokenKind::LBracket) {
345            let ps = self.parse_ident_list()?;
346            self.expect(&TokenKind::RBracket, "after type params")?;
347            ps
348        } else {
349            Vec::new()
350        };
351        self.expect(&TokenKind::LParen, "before params")?;
352        let mut params = Vec::new();
353        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
354            params.push(self.parse_param()?);
355            while self.eat(&TokenKind::Comma) {
356                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
357                params.push(self.parse_param()?);
358            }
359        }
360        self.expect(&TokenKind::RParen, "after params")?;
361        self.expect(&TokenKind::Arrow, "before return type")?;
362        let effects = self.parse_effects()?;
363        let return_type = self.parse_type_expr()?;
364        let body = self.parse_block()?;
365        Ok(FnDecl { name, type_params, params, effects, return_type, body })
366    }
367
368    fn parse_param(&mut self) -> Result<Param, ParseError> {
369        let name = self.expect_ident("for parameter name")?;
370        self.expect(&TokenKind::ColonColon, "after parameter name")?;
371        let ty = self.parse_type_expr()?;
372        Ok(Param { name, ty })
373    }
374
375    fn parse_effects(&mut self) -> Result<Vec<Effect>, ParseError> {
376        if !self.eat(&TokenKind::LBracket) {
377            return Ok(Vec::new());
378        }
379        let mut out = Vec::new();
380        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) {
381            out.push(self.parse_effect()?);
382            while self.eat(&TokenKind::Comma) {
383                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
384                out.push(self.parse_effect()?);
385            }
386        }
387        self.expect(&TokenKind::RBracket, "after effects")?;
388        Ok(out)
389    }
390
391    fn parse_effect(&mut self) -> Result<Effect, ParseError> {
392        let name = self.expect_ident("for effect name")?;
393        let arg = if self.eat(&TokenKind::LParen) {
394            let arg = match self.bump().map(|t| t.kind) {
395                Some(TokenKind::Str(s)) => EffectArg::Str(s),
396                Some(TokenKind::Int(n)) => EffectArg::Int(n),
397                Some(TokenKind::Ident(s)) => EffectArg::Ident(s),
398                other => return Err(self.error(format!("invalid effect arg: {other:?}"))),
399            };
400            self.expect(&TokenKind::RParen, "after effect arg")?;
401            Some(arg)
402        } else {
403            None
404        };
405        Ok(Effect { name, arg })
406    }
407
408    // --- blocks and statements ---
409
410    fn parse_block(&mut self) -> Result<Block, ParseError> {
411        self.expect(&TokenKind::LBrace, "before block")?;
412        let mut statements = Vec::new();
413        let result;
414        loop {
415            self.skip_newlines();
416            if matches!(self.peek(), Some(TokenKind::RBrace)) {
417                // Empty block: synthesize Unit literal.
418                result = Box::new(Expr::Lit(Literal::Unit));
419                break;
420            }
421            // Try parsing a let; otherwise an expression.
422            if matches!(self.peek(), Some(TokenKind::Let)) {
423                let stmt = self.parse_let_statement()?;
424                statements.push(stmt);
425                self.skip_newlines();
426                continue;
427            }
428            let expr = self.parse_expr()?;
429            self.skip_newlines();
430            // If the next token is `}`, this expression is the block's result.
431            if matches!(self.peek(), Some(TokenKind::RBrace)) {
432                result = Box::new(expr);
433                break;
434            }
435            statements.push(Statement::Expr(expr));
436        }
437        self.expect(&TokenKind::RBrace, "to close block")?;
438        Ok(Block { statements, result })
439    }
440
441    fn parse_let_statement(&mut self) -> Result<Statement, ParseError> {
442        self.expect(&TokenKind::Let, "in let")?;
443        // `let _ := expr` is the discard idiom (#200). The RHS is
444        // still evaluated for its effect, but the result is bound
445        // to a synthetic name nothing else references — so the
446        // type-checker / VM treat it like a normal let, but user
447        // code can't accidentally reach it.
448        let name = if matches!(self.peek_skip_newlines(), Some(TokenKind::Underscore)) {
449            self.skip_newlines();
450            self.bump();
451            self.discard_counter += 1;
452            format!("__lex_discard_{}", self.discard_counter)
453        } else {
454            self.expect_ident("after `let`")?
455        };
456        let ty = if self.eat(&TokenKind::ColonColon) {
457            Some(self.parse_type_expr()?)
458        } else {
459            None
460        };
461        self.expect(&TokenKind::ColonEq, "in let")?;
462        let value = self.parse_expr()?;
463        Ok(Statement::Let { name, ty, value })
464    }
465
466    // --- expressions ---
467
468    fn parse_expr(&mut self) -> Result<Expr, ParseError> {
469        // Recursion gate: every nested expression — match arms,
470        // tuple/list/record/block elements, function args, etc. —
471        // enters here, so this is the right place to bound depth.
472        // Decrement happens whether the inner call succeeds or fails.
473        if self.depth >= MAX_DEPTH {
474            return Err(ParseError {
475                pos: self.current_pos(),
476                msg: format!(
477                    "expression nests too deeply (max {MAX_DEPTH}); \
478                     malformed or hand-crafted input?"),
479            });
480        }
481        self.depth += 1;
482        let r = self.parse_expr_inner();
483        self.depth -= 1;
484        r
485    }
486
487    fn parse_expr_inner(&mut self) -> Result<Expr, ParseError> {
488        // Pipes are left-associative and bind less tightly than binary ops.
489        let mut left = self.parse_binary_expr(0)?;
490        while matches!(self.peek_skip_newlines(), Some(TokenKind::Pipe)) {
491            self.skip_newlines();
492            self.bump();
493            let right = self.parse_binary_expr(0)?;
494            left = Expr::Pipe { left: Box::new(left), right: Box::new(right) };
495        }
496        Ok(left)
497    }
498
499    fn parse_binary_expr(&mut self, min_prec: u8) -> Result<Expr, ParseError> {
500        let mut lhs = self.parse_unary()?;
501        loop {
502            let op = match self.peek_binop() {
503                Some(op) if op.precedence() >= min_prec => op,
504                _ => break,
505            };
506            self.skip_newlines();
507            self.bump();
508            let rhs = self.parse_binary_expr(op.precedence() + 1)?;
509            lhs = Expr::BinOp { op, lhs: Box::new(lhs), rhs: Box::new(rhs) };
510        }
511        Ok(lhs)
512    }
513
514    fn peek_binop(&mut self) -> Option<BinOp> {
515        match self.peek_skip_newlines()? {
516            TokenKind::Plus => Some(BinOp::Add),
517            TokenKind::Minus => Some(BinOp::Sub),
518            TokenKind::Star => Some(BinOp::Mul),
519            TokenKind::Slash => Some(BinOp::Div),
520            TokenKind::Percent => Some(BinOp::Mod),
521            TokenKind::EqEq => Some(BinOp::Eq),
522            TokenKind::BangEq => Some(BinOp::Neq),
523            TokenKind::Lt => Some(BinOp::Lt),
524            TokenKind::LtEq => Some(BinOp::Lte),
525            TokenKind::Gt => Some(BinOp::Gt),
526            TokenKind::GtEq => Some(BinOp::Gte),
527            TokenKind::And => Some(BinOp::And),
528            TokenKind::Or => Some(BinOp::Or),
529            _ => None,
530        }
531    }
532
533    fn parse_unary(&mut self) -> Result<Expr, ParseError> {
534        self.skip_newlines();
535        match self.peek() {
536            Some(TokenKind::Not) => {
537                self.bump();
538                let inner = self.parse_unary()?;
539                Ok(Expr::UnaryOp { op: UnaryOp::Not, expr: Box::new(inner) })
540            }
541            Some(TokenKind::Minus) => {
542                self.bump();
543                let inner = self.parse_unary()?;
544                Ok(Expr::UnaryOp { op: UnaryOp::Neg, expr: Box::new(inner) })
545            }
546            _ => self.parse_postfix(),
547        }
548    }
549
550    fn parse_postfix(&mut self) -> Result<Expr, ParseError> {
551        let mut expr = self.parse_primary()?;
552        loop {
553            // Postfix operations don't cross newlines (they bind tightly).
554            match self.peek() {
555                Some(TokenKind::Dot) => {
556                    self.bump();
557                    let field = self.expect_ident("after `.`")?;
558                    expr = Expr::Field { value: Box::new(expr), field };
559                }
560                Some(TokenKind::LParen) => {
561                    self.bump();
562                    let mut args = Vec::new();
563                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
564                        args.push(self.parse_expr()?);
565                        while self.eat(&TokenKind::Comma) {
566                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
567                            args.push(self.parse_expr()?);
568                        }
569                    }
570                    self.expect(&TokenKind::RParen, "in call")?;
571                    expr = Expr::Call { callee: Box::new(expr), args };
572                }
573                Some(TokenKind::Question) => {
574                    self.bump();
575                    expr = Expr::Try(Box::new(expr));
576                }
577                _ => break,
578            }
579        }
580        Ok(expr)
581    }
582
583    fn parse_primary(&mut self) -> Result<Expr, ParseError> {
584        self.skip_newlines();
585        match self.peek() {
586            Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
587                TokenKind::Int(n) => Ok(Expr::Lit(Literal::Int(n))),
588                _ => unreachable!(),
589            },
590            Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
591                TokenKind::Float(n) => Ok(Expr::Lit(Literal::Float(n))),
592                _ => unreachable!(),
593            },
594            Some(TokenKind::Str(_)) => match self.bump().unwrap().kind {
595                TokenKind::Str(s) => Ok(Expr::Lit(Literal::Str(s))),
596                _ => unreachable!(),
597            },
598            Some(TokenKind::Bytes(_)) => match self.bump().unwrap().kind {
599                TokenKind::Bytes(b) => Ok(Expr::Lit(Literal::Bytes(b))),
600                _ => unreachable!(),
601            },
602            Some(TokenKind::True) => { self.bump(); Ok(Expr::Lit(Literal::Bool(true))) }
603            Some(TokenKind::False) => { self.bump(); Ok(Expr::Lit(Literal::Bool(false))) }
604            Some(TokenKind::If) => self.parse_if(),
605            Some(TokenKind::Match) => self.parse_match(),
606            Some(TokenKind::Fn) => self.parse_lambda(),
607            Some(TokenKind::LBrace) => self.parse_brace_expr(),
608            Some(TokenKind::LBracket) => self.parse_list_literal(),
609            Some(TokenKind::LParen) => self.parse_paren_or_tuple(),
610            Some(TokenKind::Ident(_)) => self.parse_ident_or_record(),
611            other => Err(self.error(format!("expected expression, got {other:?}"))),
612        }
613    }
614
615    /// Disambiguate `{` between record literal and block.
616    /// Lookahead: `{ Ident :` is a record literal; `{ }` is also a record
617    /// (empty block has no use). Anything else is a block.
618    fn parse_brace_expr(&mut self) -> Result<Expr, ParseError> {
619        // Save position; peek 2-3 tokens past `{` (skipping newlines).
620        let saved = self.idx;
621        self.bump(); // `{`
622        // Skip newlines.
623        while matches!(self.peek(), Some(TokenKind::Newline) | Some(TokenKind::Semi)) {
624            self.idx += 1;
625        }
626        let is_record = matches!(self.peek(), Some(TokenKind::RBrace))
627            || (matches!(self.peek(), Some(TokenKind::Ident(_)))
628                && matches!(self.tokens.get(self.idx + 1).map(|t| &t.kind), Some(TokenKind::Colon) | Some(TokenKind::Comma) | Some(TokenKind::RBrace)));
629        self.idx = saved;
630        if is_record {
631            self.parse_record_literal()
632        } else {
633            Ok(Expr::Block(self.parse_block()?))
634        }
635    }
636
637    fn parse_record_literal(&mut self) -> Result<Expr, ParseError> {
638        self.expect(&TokenKind::LBrace, "in record literal")?;
639        let mut fields = Vec::new();
640        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
641            loop {
642                self.skip_newlines();
643                let name = self.expect_ident("in record literal")?;
644                let value = if self.eat(&TokenKind::Colon) {
645                    self.parse_expr()?
646                } else {
647                    // shorthand: `{ name }` => `{ name: name }`
648                    Expr::Var(name.clone())
649                };
650                fields.push(RecordLitField { name, value });
651                self.skip_newlines();
652                if !self.eat(&TokenKind::Comma) { break; }
653                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
654            }
655        }
656        self.expect(&TokenKind::RBrace, "after record literal")?;
657        Ok(Expr::RecordLit(fields))
658    }
659
660    fn parse_if(&mut self) -> Result<Expr, ParseError> {
661        self.expect(&TokenKind::If, "in if")?;
662        let cond = self.parse_expr()?;
663        let then_block = self.parse_block()?;
664        self.expect(&TokenKind::Else, "expected `else`")?;
665        let else_block = self.parse_block()?;
666        Ok(Expr::If { cond: Box::new(cond), then_block, else_block })
667    }
668
669    fn parse_match(&mut self) -> Result<Expr, ParseError> {
670        self.expect(&TokenKind::Match, "in match")?;
671        let scrutinee = self.parse_expr()?;
672        self.expect(&TokenKind::LBrace, "before match arms")?;
673        let mut arms = Vec::new();
674        loop {
675            self.skip_newlines();
676            if matches!(self.peek(), Some(TokenKind::RBrace)) { break; }
677            let pattern = self.parse_pattern()?;
678            self.expect(&TokenKind::FatArrow, "in match arm")?;
679            let body = self.parse_expr()?;
680            arms.push(Arm { pattern, body });
681            self.skip_newlines();
682            if !self.eat(&TokenKind::Comma) { break; }
683        }
684        self.expect(&TokenKind::RBrace, "after match arms")?;
685        Ok(Expr::Match { scrutinee: Box::new(scrutinee), arms })
686    }
687
688    fn parse_lambda(&mut self) -> Result<Expr, ParseError> {
689        self.expect(&TokenKind::Fn, "in lambda")?;
690        self.expect(&TokenKind::LParen, "before lambda params")?;
691        let mut params = Vec::new();
692        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
693            params.push(self.parse_param()?);
694            while self.eat(&TokenKind::Comma) {
695                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
696                params.push(self.parse_param()?);
697            }
698        }
699        self.expect(&TokenKind::RParen, "after lambda params")?;
700        self.expect(&TokenKind::Arrow, "before lambda return type")?;
701        let effects = self.parse_effects()?;
702        let return_type = self.parse_type_expr()?;
703        let body = self.parse_block()?;
704        Ok(Expr::Lambda(Box::new(Lambda { params, effects, return_type, body })))
705    }
706
707    fn parse_list_literal(&mut self) -> Result<Expr, ParseError> {
708        self.expect(&TokenKind::LBracket, "before list literal")?;
709        let mut items = Vec::new();
710        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) {
711            items.push(self.parse_expr()?);
712            while self.eat(&TokenKind::Comma) {
713                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBracket)) { break; }
714                items.push(self.parse_expr()?);
715            }
716        }
717        self.expect(&TokenKind::RBracket, "after list literal")?;
718        Ok(Expr::ListLit(items))
719    }
720
721    fn parse_paren_or_tuple(&mut self) -> Result<Expr, ParseError> {
722        self.expect(&TokenKind::LParen, "")?;
723        if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
724            self.bump();
725            return Ok(Expr::Lit(Literal::Unit));
726        }
727        let first = self.parse_expr()?;
728        if self.eat(&TokenKind::Comma) {
729            let mut items = vec![first];
730            if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
731                items.push(self.parse_expr()?);
732                while self.eat(&TokenKind::Comma) {
733                    if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
734                    items.push(self.parse_expr()?);
735                }
736            }
737            self.expect(&TokenKind::RParen, "after tuple")?;
738            Ok(Expr::TupleLit(items))
739        } else {
740            self.expect(&TokenKind::RParen, "after parenthesized expression")?;
741            Ok(first)
742        }
743    }
744
745    fn parse_ident_or_record(&mut self) -> Result<Expr, ParseError> {
746        // Ident is parsed as a Var; later postfix (`(`, `.`, `?`) attach.
747        let name = self.expect_ident("")?;
748        Ok(Expr::Var(name))
749    }
750
751    // --- patterns ---
752
753    fn parse_pattern(&mut self) -> Result<Pattern, ParseError> {
754        self.skip_newlines();
755        match self.peek() {
756            Some(TokenKind::Underscore) => { self.bump(); Ok(Pattern::Wild) }
757            Some(TokenKind::Int(_)) => match self.bump().unwrap().kind {
758                TokenKind::Int(n) => Ok(Pattern::Lit(Literal::Int(n))),
759                _ => unreachable!(),
760            },
761            Some(TokenKind::Float(_)) => match self.bump().unwrap().kind {
762                TokenKind::Float(n) => Ok(Pattern::Lit(Literal::Float(n))),
763                _ => unreachable!(),
764            },
765            Some(TokenKind::Str(_)) => match self.bump().unwrap().kind {
766                TokenKind::Str(s) => Ok(Pattern::Lit(Literal::Str(s))),
767                _ => unreachable!(),
768            },
769            Some(TokenKind::True) => { self.bump(); Ok(Pattern::Lit(Literal::Bool(true))) }
770            Some(TokenKind::False) => { self.bump(); Ok(Pattern::Lit(Literal::Bool(false))) }
771            Some(TokenKind::LBrace) => self.parse_record_pattern(),
772            Some(TokenKind::LParen) => self.parse_tuple_pattern(),
773            Some(TokenKind::Ident(_)) => {
774                let name = self.expect_ident("")?;
775                if matches!(self.peek(), Some(TokenKind::LParen)) {
776                    self.bump();
777                    let mut args = Vec::new();
778                    if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
779                        args.push(self.parse_pattern()?);
780                        while self.eat(&TokenKind::Comma) {
781                            if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
782                            args.push(self.parse_pattern()?);
783                        }
784                    }
785                    self.expect(&TokenKind::RParen, "after constructor pattern")?;
786                    Ok(Pattern::Constructor { name, args })
787                } else {
788                    Ok(Pattern::Var(name))
789                }
790            }
791            other => Err(self.error(format!("expected pattern, got {other:?}"))),
792        }
793    }
794
795    fn parse_record_pattern(&mut self) -> Result<Pattern, ParseError> {
796        self.expect(&TokenKind::LBrace, "")?;
797        let mut fields = Vec::new();
798        let rest = false;
799        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) {
800            loop {
801                self.skip_newlines();
802                let name = self.expect_ident("in record pattern")?;
803                let pattern = if self.eat(&TokenKind::Colon) {
804                    Some(self.parse_pattern()?)
805                } else {
806                    None
807                };
808                fields.push(RecordPatField { name, pattern });
809                self.skip_newlines();
810                if !self.eat(&TokenKind::Comma) { break; }
811                if matches!(self.peek_skip_newlines(), Some(TokenKind::RBrace)) { break; }
812            }
813        }
814        self.expect(&TokenKind::RBrace, "after record pattern")?;
815        Ok(Pattern::Record { fields, rest })
816    }
817
818    fn parse_tuple_pattern(&mut self) -> Result<Pattern, ParseError> {
819        self.expect(&TokenKind::LParen, "")?;
820        let mut items = Vec::new();
821        if !matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) {
822            items.push(self.parse_pattern()?);
823            while self.eat(&TokenKind::Comma) {
824                if matches!(self.peek_skip_newlines(), Some(TokenKind::RParen)) { break; }
825                items.push(self.parse_pattern()?);
826            }
827        }
828        self.expect(&TokenKind::RParen, "after tuple pattern")?;
829        if items.len() == 1 {
830            Ok(items.into_iter().next().unwrap())
831        } else {
832            Ok(Pattern::Tuple(items))
833        }
834    }
835}
836
837/// In a union RHS, every leaf must be a `Named` type expression — that is, a
838/// PascalCase ident with optional payload via `Variant(payload_type)`.
839fn type_to_variant(t: TypeExpr) -> Result<UnionVariant, ParseError> {
840    match t {
841        TypeExpr::Named { name, args } => {
842            let payload = match args.len() {
843                0 => None,
844                1 => Some(args.into_iter().next().unwrap()),
845                _ => Some(TypeExpr::Tuple(args)),
846            };
847            Ok(UnionVariant { name, payload })
848        }
849        // `Foo({ field :: T })` parses as Named with one arg = Record. handled above.
850        _ => Err(ParseError {
851            pos: 0,
852            msg: "union variant must be a constructor name".into(),
853        }),
854    }
855}
lex_syntax/parser.rs

lex_syntax/
parser.rs
