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

lex_syntax/
parser.rs
