prune_lang/syntax/
parser.rs

1use super::lexer::*;
2use super::*;
3use crate::cli::diagnostic::Diagnostic;
4use crate::syntax::ast::*;
5
6pub struct Parser<'src> {
7    source: &'src str,
8    tokens: Vec<TokenSpan>,
9    cursor: usize,
10    errors: Vec<ParseError>,
11}
12
13#[derive(Debug, Clone)]
14pub enum ParseError {
15    LexerError(Span),
16    UnknownPrim(Span),
17    FailedToMatch(Token, Token, Span),
18    FailedToParse(&'static str, Token, Span),
19}
20
21impl From<ParseError> for Diagnostic {
22    fn from(val: ParseError) -> Self {
23        match val {
24            ParseError::LexerError(span) => Diagnostic::error("cannot scan next token!")
25                .line_span(span.clone(), "here is the bad token"),
26
27            ParseError::UnknownPrim(span) => Diagnostic::error("unknown primitve!")
28                .line_span(span.clone(), "here is the primitive"),
29            ParseError::FailedToMatch(expect, found, span) => {
30                Diagnostic::error("cannot match token!").line_span(
31                    span.clone(),
32                    format!("expect token {expect:?}, found token {found:?}"),
33                )
34            }
35            ParseError::FailedToParse(name, found, span) => {
36                Diagnostic::error(format!("cannot parse {name}!"))
37                    .line_span(span.clone(), format!("found token {found:?}"))
38            }
39        }
40    }
41}
42
43type ParseResult<T> = Result<T, ParseError>;
44
45impl<'src> Parser<'src> {
46    pub fn new(src: &'src str) -> Parser<'src> {
47        let tokens = lexer::tokenize(src);
48        Parser {
49            source: src,
50            tokens,
51            cursor: 0,
52            errors: Vec::new(),
53        }
54    }
55
56    #[allow(dead_code)]
57    fn peek_token_span(&self) -> &TokenSpan {
58        &self.tokens[self.cursor]
59    }
60
61    fn peek_token(&self) -> Token {
62        self.tokens[self.cursor].token
63    }
64
65    #[allow(dead_code)]
66    fn peek_token_nth(&self, n: usize) -> Token {
67        if self.cursor + n < self.tokens.len() {
68            self.tokens[self.cursor + n].token
69        } else {
70            Token::EndOfFile
71        }
72    }
73
74    fn peek_span(&self) -> &Span {
75        &self.tokens[self.cursor].span
76    }
77
78    #[allow(dead_code)]
79    fn peek_span_nth(&self, n: usize) -> &Span {
80        if self.cursor + n < self.tokens.len() {
81            &self.tokens[self.cursor + n].span
82        } else {
83            &self.tokens[self.tokens.len() - 1].span
84        }
85    }
86
87    fn peek_slice(&self) -> &'src str {
88        let span = &self.tokens[self.cursor].span;
89        &self.source[span.start..span.end]
90    }
91
92    fn start_pos(&self) -> usize {
93        self.tokens[self.cursor].span.start
94    }
95
96    fn end_pos(&self) -> usize {
97        self.tokens[self.cursor - 1].span.end
98    }
99
100    fn next_token(&mut self) -> ParseResult<&TokenSpan> {
101        let tok = &self.tokens[self.cursor];
102        if tok.token == Token::TokError {
103            Err(ParseError::LexerError(self.peek_span().clone()))
104        } else {
105            if self.cursor < self.tokens.len() - 1 {
106                self.cursor += 1;
107            }
108            Ok(tok)
109        }
110    }
111
112    fn match_token(&mut self, tok: Token) -> ParseResult<()> {
113        if self.peek_token() == tok {
114            self.next_token()?;
115            Ok(())
116        } else {
117            Err(ParseError::FailedToMatch(
118                tok,
119                self.peek_token(),
120                self.peek_span().clone(),
121            ))
122        }
123    }
124
125    #[allow(dead_code)]
126    fn option<T, F>(&mut self, func: F) -> ParseResult<Option<T>>
127    where
128        F: Fn(&mut Parser) -> ParseResult<T>,
129    {
130        let last = self.cursor;
131        match func(self) {
132            Ok(res) => Ok(Some(res)),
133            Err(err) => {
134                // if it failed without consuming any token
135                if self.cursor == last {
136                    Ok(None) // return Err(ParseError::FailedToParse((), self.peek_token(), self.peek_span().clone()))
137                } else {
138                    Err(err) // otherwise fail
139                }
140            }
141        }
142    }
143
144    #[allow(dead_code)]
145    fn surround<T, F>(&mut self, left: Token, right: Token, func: F) -> ParseResult<T>
146    where
147        F: Fn(&mut Parser) -> ParseResult<T>,
148    {
149        self.match_token(left)?;
150        let res = func(self)?;
151        self.match_token(right)?;
152        Ok(res)
153    }
154
155    fn delimited_list<T, F>(
156        &mut self,
157        left: Token,
158        delim: Token,
159        right: Token,
160        func: F,
161    ) -> ParseResult<Vec<T>>
162    where
163        F: Fn(&mut Parser) -> ParseResult<T>,
164    {
165        // An ad-hoc solution for interpreting Unit as [LParen, RParen]
166        if self.peek_token() == Token::Unit && left == Token::LParen && right == Token::RParen {
167            self.next_token()?;
168            return Ok(Vec::new());
169        }
170        let mut vec: Vec<T> = Vec::new();
171        self.match_token(left)?;
172        // allow leading delimiter
173        if self.peek_token() == delim {
174            self.next_token()?;
175        }
176        // allow empty list
177        if self.peek_token() == right {
178            self.next_token()?;
179            return Ok(vec);
180        }
181        vec.push(func(self)?);
182        while self.peek_token() == delim {
183            self.next_token()?;
184            // allow trailing delimiter
185            if self.peek_token() == right {
186                break;
187            }
188            vec.push(func(self)?);
189        }
190        self.match_token(right)?;
191        Ok(vec)
192    }
193
194    fn parse_lit_val(&mut self) -> ParseResult<LitVal> {
195        match self.peek_token() {
196            Token::Int => {
197                let x = self.peek_slice().parse::<i64>().unwrap();
198                self.next_token()?;
199                Ok(LitVal::Int(x))
200            }
201            Token::Float => {
202                let x = self.peek_slice().parse::<f64>().unwrap();
203                self.next_token()?;
204                Ok(LitVal::Float(x))
205            }
206            Token::Bool => {
207                let x = self.peek_slice().parse::<bool>().unwrap();
208                self.next_token()?;
209                Ok(LitVal::Bool(x))
210            }
211            Token::Char => {
212                let x = self.peek_slice().trim_matches('\'');
213                // transform from 'c' to "c"
214                let x: String = "\"".chars().chain(x.chars()).chain("\"".chars()).collect();
215                if let Ok(s) = snailquote::unescape(&x) {
216                    assert_eq!(s.len(), 1);
217                    self.next_token()?;
218                    Ok(LitVal::Char(s.chars().nth(0).unwrap()))
219                } else {
220                    Err(ParseError::LexerError(self.peek_span().clone()))
221                }
222            }
223            _tok => Err(ParseError::FailedToParse(
224                "literal value",
225                self.peek_token(),
226                self.peek_span().clone(),
227            )),
228        }
229    }
230
231    fn parse_lit_typ(&mut self) -> ParseResult<LitType> {
232        match self.peek_token() {
233            Token::TyInt => {
234                self.next_token()?;
235                Ok(LitType::TyInt)
236            }
237            Token::TyFloat => {
238                self.next_token()?;
239                Ok(LitType::TyFloat)
240            }
241            Token::TyBool => {
242                self.next_token()?;
243                Ok(LitType::TyBool)
244            }
245            Token::TyChar => {
246                self.next_token()?;
247                Ok(LitType::TyChar)
248            }
249            _tok => Err(ParseError::FailedToParse(
250                "literal type",
251                self.peek_token(),
252                self.peek_span().clone(),
253            )),
254        }
255    }
256
257    fn parse_lower_var(&mut self) -> ParseResult<Var> {
258        match self.peek_token() {
259            Token::LowerIdent => {
260                // handle wildcard identifier
261                let ident = if self.peek_slice() == "_" {
262                    Ident::fresh(&"_")
263                } else {
264                    Ident::dummy(&self.peek_slice())
265                };
266                let span = self.peek_span().clone();
267                self.next_token()?;
268                Ok(Var { ident, span })
269            }
270            _tok => Err(ParseError::FailedToParse(
271                "lowercase varible",
272                self.peek_token(),
273                self.peek_span().clone(),
274            )),
275        }
276    }
277
278    fn parse_upper_var(&mut self) -> ParseResult<Var> {
279        match self.peek_token() {
280            Token::UpperIdent => {
281                let ident = Ident::dummy(&self.peek_slice());
282                let span = self.peek_span().clone();
283                self.next_token()?;
284                Ok(Var { ident, span })
285            }
286            _tok => Err(ParseError::FailedToParse(
287                "uppercase varible",
288                self.peek_token(),
289                self.peek_span().clone(),
290            )),
291        }
292    }
293
294    fn parse_prim_opr(&mut self) -> ParseResult<Prim> {
295        match self.peek_token() {
296            Token::PrimOpr => {
297                let s = self.peek_slice();
298                self.next_token()?;
299                let res = match s {
300                    "@iadd" => Prim::IAdd,
301                    "@isub" => Prim::ISub,
302                    "@imul" => Prim::IMul,
303                    "@idiv" => Prim::IDiv,
304                    "@irem" => Prim::IRem,
305                    "@ineg" => Prim::INeg,
306                    "@icmplt" => Prim::ICmp(Compare::Lt),
307                    "@icmple" => Prim::ICmp(Compare::Le),
308                    "@icmpeq" => Prim::ICmp(Compare::Eq),
309                    "@icmpgt" => Prim::ICmp(Compare::Gt),
310                    "@icmpge" => Prim::ICmp(Compare::Ge),
311                    "@icmpne" => Prim::ICmp(Compare::Ne),
312                    "@band" => Prim::BAnd,
313                    "@bor" => Prim::BOr,
314                    "@bnot" => Prim::BNot,
315                    _ => {
316                        return Err(ParseError::UnknownPrim(self.peek_span().clone()));
317                    }
318                };
319                Ok(res)
320            }
321            _tok => Err(ParseError::FailedToParse(
322                "primitive operator",
323                self.peek_token(),
324                self.peek_span().clone(),
325            )),
326        }
327    }
328
329    fn parse_expr_args(&mut self) -> ParseResult<Vec<Expr>> {
330        self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
331            par.parse_expr()
332        })
333    }
334
335    fn parse_expr(&mut self) -> ParseResult<Expr> {
336        let mut expr_stack: Vec<(Expr, Span)> = Vec::new();
337        let mut opr_stack: Vec<Prim> = Vec::new();
338
339        fn squash(expr_stack: &mut Vec<(Expr, Span)>, opr_stack: &mut Vec<Prim>) {
340            let (rhs, span1) = expr_stack.pop().unwrap();
341            let opr = opr_stack.pop().unwrap();
342            let (lhs, span2) = expr_stack.pop().unwrap();
343            let span = Span {
344                start: span1.start,
345                end: span2.end,
346            };
347            let new_expr = Expr::Prim {
348                prim: opr,
349                args: vec![lhs, rhs],
350                span: span.clone(),
351            };
352            expr_stack.push((new_expr, span));
353        }
354
355        loop {
356            let start = self.start_pos();
357            let expr = self.parse_expr_factor()?;
358            let end = self.end_pos();
359            let span = Span { start, end };
360            expr_stack.push((expr, span));
361            // todo: ad-hoc polymorphism
362            let opr = match self.peek_token() {
363                Token::Plus => Prim::IAdd,
364                Token::Minus => Prim::ISub,
365                Token::Star => Prim::IMul,
366                Token::Slash => Prim::IDiv,
367                Token::Percent => Prim::IRem,
368                Token::Less => Prim::ICmp(Compare::Lt),
369                Token::LessEqual => Prim::ICmp(Compare::Le),
370                Token::EqualEqual => Prim::ICmp(Compare::Eq),
371                Token::GreaterEqual => Prim::ICmp(Compare::Ge),
372                Token::Greater => Prim::ICmp(Compare::Gt),
373                Token::BangEqual => Prim::ICmp(Compare::Ne),
374                Token::DoubleAmpersand => Prim::BAnd,
375                Token::DoubleBar => Prim::BOr,
376                _ => {
377                    while !opr_stack.is_empty() {
378                        squash(&mut expr_stack, &mut opr_stack);
379                    }
380                    assert_eq!(expr_stack.len(), 1);
381                    return Ok(expr_stack.pop().unwrap().0);
382                }
383            };
384            self.next_token()?;
385
386            while !opr_stack.is_empty() {
387                let opr2 = opr_stack.last().unwrap();
388                if opr2.get_prior() > opr.get_prior() {
389                    squash(&mut expr_stack, &mut opr_stack);
390                } else {
391                    break;
392                }
393            }
394            opr_stack.push(opr);
395        }
396    }
397
398    fn parse_expr_factor(&mut self) -> ParseResult<Expr> {
399        let start = self.start_pos();
400        match self.peek_token() {
401            Token::Int | Token::Float | Token::Bool | Token::Char => {
402                let lit = self.parse_lit_val()?;
403                let end = self.end_pos();
404                let span = Span { start, end };
405                Ok(Expr::Lit { lit, span })
406            }
407            Token::LowerIdent => {
408                let var = self.parse_lower_var()?;
409                let args = self.option(|par| par.parse_expr_args())?;
410                if let Some(args) = args {
411                    let end = self.end_pos();
412                    let span = Span { start, end };
413                    Ok(Expr::App {
414                        func: var,
415                        args,
416                        span,
417                    })
418                } else {
419                    let end = self.end_pos();
420                    let span = Span { start, end };
421                    Ok(Expr::Var { var, span })
422                }
423            }
424            Token::UpperIdent => {
425                let cons = self.parse_upper_var()?;
426                let flds = if let Token::LParen = self.peek_token() {
427                    self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
428                        par.parse_expr()
429                    })?
430                } else {
431                    Vec::new()
432                };
433                let end = self.end_pos();
434                let span = Span { start, end };
435                Ok(Expr::Cons { cons, flds, span })
436            }
437            Token::PrimOpr => {
438                let prim = self.parse_prim_opr()?;
439                let args = self.parse_expr_args()?;
440                let end = self.end_pos();
441                let span = Span { start, end };
442                Ok(Expr::Prim { prim, args, span })
443            }
444            Token::Let => {
445                self.match_token(Token::Let)?;
446                let bind = self.parse_pattern()?;
447                self.match_token(Token::Equal)?;
448                let expr = Box::new(self.parse_expr()?);
449                self.match_token(Token::Semi)?;
450                let cont = Box::new(self.parse_expr()?);
451                let end = self.end_pos();
452                let span = Span { start, end };
453                Ok(Expr::Let {
454                    patn: bind,
455                    expr,
456                    cont,
457                    span,
458                })
459            }
460            Token::If => {
461                self.match_token(Token::If)?;
462                let cond = Box::new(self.parse_expr()?);
463                self.match_token(Token::Then)?;
464                let then = Box::new(self.parse_expr()?);
465                self.match_token(Token::Else)?;
466                let els = Box::new(self.parse_expr()?);
467                let end = self.end_pos();
468                let span = Span { start, end };
469                Ok(Expr::Ifte {
470                    cond,
471                    then,
472                    els,
473                    span,
474                })
475            }
476            Token::Match => {
477                self.match_token(Token::Match)?;
478                let expr = Box::new(self.parse_expr()?);
479                let brchs = self.delimited_list(Token::With, Token::Bar, Token::End, |par| {
480                    par.parse_match_brch()
481                })?;
482                let end = self.end_pos();
483                let span = Span { start, end };
484                Ok(Expr::Match { expr, brchs, span })
485            }
486            Token::Condition => {
487                let brchs =
488                    self.delimited_list(Token::Condition, Token::Bar, Token::End, |par| {
489                        par.parse_cond_brch()
490                    })?;
491                let end = self.end_pos();
492                let span = Span { start, end };
493                Ok(Expr::Cond { brchs, span })
494            }
495            Token::Alternative => {
496                let brchs =
497                    self.delimited_list(Token::Alternative, Token::Bar, Token::End, |par| {
498                        par.parse_expr()
499                    })?;
500                let end = self.end_pos();
501                let span = Span { start, end };
502                Ok(Expr::Alter { brchs, span })
503            }
504            Token::Fresh => {
505                let vars = self.delimited_list(Token::Fresh, Token::Comma, Token::Semi, |par| {
506                    par.parse_lower_var()
507                })?;
508                let cont = Box::new(self.parse_expr()?);
509                let end = self.end_pos();
510                let span = Span { start, end };
511                Ok(Expr::Fresh { vars, cont, span })
512            }
513            Token::Guard => {
514                self.match_token(Token::Guard)?;
515                let lhs = Box::new(self.parse_expr()?);
516
517                let rhs = match self.peek_token() {
518                    Token::Equal => {
519                        // guard e1 = e2; e3, in which e1 and e2 have the same type
520                        self.match_token(Token::Equal)?;
521                        Some(Box::new(self.parse_expr()?))
522                    }
523                    Token::Semi => {
524                        // guard e1; e2, if e1 has Unit type
525                        None
526                    }
527                    _ => {
528                        return Err(ParseError::FailedToParse(
529                            "right-hand-side of guard expression",
530                            self.peek_token(),
531                            self.peek_span().clone(),
532                        ));
533                    }
534                };
535
536                self.match_token(Token::Semi)?;
537                let cont = Box::new(self.parse_expr()?);
538                let end = self.end_pos();
539                let span = Span { start, end };
540                Ok(Expr::Guard {
541                    lhs,
542                    rhs,
543                    cont,
544                    span,
545                })
546            }
547            Token::Bang => {
548                self.match_token(Token::Bang)?;
549                let arg = self.parse_expr_factor()?;
550                let end = self.end_pos();
551                let span = Span { start, end };
552                Ok(Expr::Prim {
553                    prim: Prim::BNot,
554                    args: vec![arg],
555                    span,
556                })
557            }
558            Token::Undefined => {
559                self.match_token(Token::Undefined)?;
560                let end = self.end_pos();
561                let span = Span { start, end };
562                Ok(Expr::Undefined { span })
563            }
564            Token::LParen => {
565                let exprs =
566                    self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
567                        par.parse_expr()
568                    })?;
569                let end = self.end_pos();
570                let span = Span { start, end };
571                match exprs.len() {
572                    0 => Err(ParseError::FailedToParse(
573                        "tuple of expressions",
574                        self.peek_token(),
575                        self.peek_span().clone(),
576                    )),
577                    1 => Ok(exprs.into_iter().next().unwrap()),
578                    _ => Ok(Expr::Tuple { flds: exprs, span }),
579                }
580            }
581            Token::Unit => {
582                self.next_token()?;
583                let end = self.end_pos();
584                let span = Span { start, end };
585                Ok(Expr::Tuple {
586                    flds: Vec::new(),
587                    span,
588                })
589            }
590            Token::End | Token::Bar | Token::Else => {
591                let end = self.end_pos();
592                let span = Span { start, end };
593                Ok(Expr::Tuple {
594                    flds: Vec::new(),
595                    span,
596                })
597            }
598            _tok => Err(ParseError::FailedToParse(
599                "expression",
600                self.peek_token(),
601                self.peek_span().clone(),
602            )),
603        }
604    }
605
606    fn parse_match_brch(&mut self) -> ParseResult<(Pattern, Expr)> {
607        let start = self.start_pos();
608        let patn = self.parse_pattern()?;
609        self.match_token(Token::FatArrow)?;
610        let body = self.parse_expr()?;
611        let end = self.end_pos();
612        let _span = Span { start, end };
613        Ok((patn, body))
614    }
615
616    fn parse_cond_brch(&mut self) -> ParseResult<(Expr, Expr)> {
617        let start = self.start_pos();
618        let cond = self.parse_expr()?;
619        self.match_token(Token::FatArrow)?;
620        let body = self.parse_expr()?;
621        let end = self.end_pos();
622        let _span = Span { start, end };
623        Ok((cond, body))
624    }
625
626    fn parse_pattern(&mut self) -> ParseResult<Pattern> {
627        let start = self.start_pos();
628        match self.peek_token() {
629            Token::Int | Token::Float | Token::Bool | Token::Char | Token::Unit => {
630                let lit = self.parse_lit_val()?;
631                let end = self.end_pos();
632                let span = Span { start, end };
633                Ok(Pattern::Lit { lit, span })
634            }
635            Token::LowerIdent => {
636                let var = self.parse_lower_var()?;
637                let end = self.end_pos();
638                let span = Span { start, end };
639                Ok(Pattern::Var { var, span })
640            }
641            Token::UpperIdent => {
642                let cons = self.parse_upper_var()?;
643                let flds = if let Token::LParen = self.peek_token() {
644                    self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
645                        par.parse_pattern()
646                    })?
647                } else {
648                    Vec::new()
649                };
650                let end = self.end_pos();
651                let span = Span { start, end };
652                Ok(Pattern::Cons { cons, flds, span })
653            }
654            Token::LParen => {
655                let patns =
656                    self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
657                        par.parse_pattern()
658                    })?;
659                let end = self.end_pos();
660                let span = Span { start, end };
661                match patns.len() {
662                    0 => Err(ParseError::FailedToParse(
663                        "tuple of patterns",
664                        self.peek_token(),
665                        self.peek_span().clone(),
666                    )),
667                    1 => Ok(patns.into_iter().next().unwrap()),
668                    _ => Ok(Pattern::Tuple { flds: patns, span }),
669                }
670            }
671            _tok => Err(ParseError::FailedToParse(
672                "pattern",
673                self.peek_token(),
674                self.peek_span().clone(),
675            )),
676        }
677    }
678
679    fn parse_type(&mut self) -> ParseResult<Type> {
680        let start = self.start_pos();
681        match self.peek_token() {
682            Token::TyInt | Token::TyFloat | Token::TyBool | Token::TyChar => {
683                let lit = self.parse_lit_typ()?;
684                let end = self.end_pos();
685                let span = Span { start, end };
686                Ok(Type::Lit { lit, span })
687            }
688            Token::LowerIdent => {
689                let var = self.parse_lower_var()?;
690                let end = self.end_pos();
691                let span = Span { start, end };
692                Ok(Type::Var { var, span })
693            }
694            Token::UpperIdent => {
695                let cons = self.parse_upper_var()?;
696                let flds = self
697                    .option(|par| {
698                        par.delimited_list(Token::LBracket, Token::Comma, Token::RBracket, |par| {
699                            par.parse_type()
700                        })
701                    })?
702                    .unwrap_or(Vec::new());
703                let end = self.end_pos();
704                let span = Span { start, end };
705                Ok(Type::Cons { cons, flds, span })
706            }
707            Token::LParen => {
708                let typs =
709                    self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
710                        par.parse_type()
711                    })?;
712                let end = self.end_pos();
713                let span = Span { start, end };
714                match typs.len() {
715                    0 => Err(ParseError::FailedToParse(
716                        "tuple of types",
717                        self.peek_token(),
718                        self.peek_span().clone(),
719                    )),
720                    1 => Ok(typs.into_iter().next().unwrap()),
721                    _ => Ok(Type::Tuple { flds: typs, span }),
722                }
723            }
724            Token::Unit => {
725                self.next_token()?;
726                let end = self.end_pos();
727                let span = Span { start, end };
728                Ok(Type::Tuple {
729                    flds: Vec::new(),
730                    span,
731                })
732            }
733            _tok => Err(ParseError::FailedToParse(
734                "type",
735                self.peek_token(),
736                self.peek_span().clone(),
737            )),
738        }
739    }
740
741    fn parse_varient(&mut self) -> ParseResult<Constructor> {
742        let start = self.start_pos();
743        let name = self.parse_upper_var()?;
744        let flds = if let Token::LParen = self.peek_token() {
745            self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
746                par.parse_type()
747            })?
748        } else {
749            Vec::new()
750        };
751        let end = self.end_pos();
752        let span = Span { start, end };
753        Ok(Constructor { name, flds, span })
754    }
755
756    fn parse_data_decl(&mut self) -> ParseResult<DataDecl> {
757        let start = self.start_pos();
758        self.match_token(Token::Datatype)?;
759        let name = self.parse_upper_var()?;
760        let polys = self
761            .option(|par| {
762                par.delimited_list(Token::LBracket, Token::Comma, Token::RBracket, |par| {
763                    par.parse_lower_var()
764                })
765            })?
766            .unwrap_or(Vec::new());
767        let vars = self.delimited_list(Token::Where, Token::Bar, Token::End, |par| {
768            par.parse_varient()
769        })?;
770        let end = self.end_pos();
771        let span = Span { start, end };
772        Ok(DataDecl {
773            name,
774            polys,
775            cons: vars,
776            span,
777        })
778    }
779
780    fn parse_func_decl(&mut self) -> ParseResult<FuncDecl> {
781        let start = self.start_pos();
782        self.match_token(Token::Function)?;
783        let name = self.parse_lower_var()?;
784        let polys = self
785            .option(|par| {
786                par.delimited_list(Token::LBracket, Token::Comma, Token::RBracket, |par| {
787                    par.parse_lower_var()
788                })
789            })?
790            .unwrap_or(Vec::new());
791        let pars = self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
792            let ident = par.parse_lower_var()?;
793            par.match_token(Token::Colon)?;
794            let typ = par.parse_type()?;
795            Ok((ident, typ))
796        })?;
797
798        let res: Type = self
799            .option(|par| {
800                par.match_token(Token::Arrow)?;
801                par.parse_type()
802            })?
803            .unwrap_or_else(|| {
804                let start = self.start_pos();
805                let end = self.end_pos();
806                let span = Span { start, end };
807                Type::Tuple {
808                    flds: Vec::new(),
809                    span,
810                }
811            });
812
813        self.match_token(Token::Begin)?;
814        let body = self.parse_expr()?;
815        self.match_token(Token::End)?;
816        let end = self.end_pos();
817        let span = Span { start, end };
818        Ok(FuncDecl {
819            name,
820            polys,
821            pars,
822            res,
823            body,
824            span,
825        })
826    }
827
828    fn parse_pos_int(&mut self) -> ParseResult<usize> {
829        match self.peek_token() {
830            Token::Int => {
831                let x = self.peek_slice().parse::<i64>().unwrap();
832                if x >= 0 {
833                    self.next_token()?;
834                    Ok(x as usize)
835                } else {
836                    Err(ParseError::FailedToParse(
837                        "positive integer",
838                        self.peek_token(),
839                        self.peek_span().clone(),
840                    ))
841                }
842            }
843            _ => Err(ParseError::FailedToParse(
844                "positive integer",
845                self.peek_token(),
846                self.peek_span().clone(),
847            )),
848        }
849    }
850
851    fn parse_bool(&mut self) -> ParseResult<bool> {
852        match self.peek_token() {
853            Token::Bool => {
854                let x = self.peek_slice().parse::<bool>().unwrap();
855                self.next_token()?;
856                Ok(x)
857            }
858            _ => Err(ParseError::FailedToParse(
859                "boolean literal",
860                self.peek_token(),
861                self.peek_span().clone(),
862            )),
863        }
864    }
865
866    fn parse_query_decl(&mut self) -> ParseResult<QueryDecl> {
867        let start = self.start_pos();
868        self.match_token(Token::Query)?;
869        let entry = self.parse_lower_var()?;
870        let params = self.delimited_list(Token::LParen, Token::Comma, Token::RParen, |par| {
871            par.parse_query_param()
872        })?;
873        let end = self.end_pos();
874        let span = Span { start, end };
875        Ok(QueryDecl {
876            entry,
877            params,
878            span,
879        })
880    }
881
882    fn parse_query_param(&mut self) -> ParseResult<(QueryParam, Span)> {
883        let start = self.start_pos();
884        let name = self.parse_lower_var()?;
885
886        match name.ident.as_str() {
887            "depth_step" => {
888                self.match_token(Token::Equal)?;
889                let val = self.parse_pos_int()?;
890                let end = self.end_pos();
891                let span = Span { start, end };
892                Ok((QueryParam::DepthStep(val), span))
893            }
894
895            "depth_limit" => {
896                self.match_token(Token::Equal)?;
897                let val = self.parse_pos_int()?;
898                let end = self.end_pos();
899                let span = Span { start, end };
900                Ok((QueryParam::DepthLimit(val), span))
901            }
902
903            "answer_limit" => {
904                self.match_token(Token::Equal)?;
905                let val = self.parse_pos_int()?;
906                let end = self.end_pos();
907                let span = Span { start, end };
908                Ok((QueryParam::AnswerLimit(val), span))
909            }
910            "answer_pause" => {
911                self.match_token(Token::Equal)?;
912                let val = self.parse_bool()?;
913                let end = self.end_pos();
914                let span = Span { start, end };
915                Ok((QueryParam::AnswerPause(val), span))
916            }
917            _ => {
918                let end = self.end_pos();
919                let span = Span { start, end };
920                Err(ParseError::FailedToParse(
921                    "query parameter",
922                    Token::LowerIdent,
923                    span,
924                ))
925            }
926        }
927    }
928
929    fn parse_decl(&mut self) -> ParseResult<Declaration> {
930        match self.peek_token() {
931            Token::Datatype => {
932                let decl = self.parse_data_decl()?;
933                Ok(Declaration::Data(decl))
934            }
935            Token::Function => {
936                let decl = self.parse_func_decl()?;
937                Ok(Declaration::Func(decl))
938            }
939            Token::Query => {
940                let decl = self.parse_query_decl()?;
941                Ok(Declaration::Query(decl))
942            }
943            _tok => Err(ParseError::FailedToParse(
944                "declaration",
945                self.peek_token(),
946                self.peek_span().clone(),
947            )),
948        }
949    }
950
951    fn parse_program(&mut self) -> Program {
952        let mut decls: Vec<Declaration> = Vec::new();
953        loop {
954            match self.peek_token() {
955                Token::Datatype | Token::Function | Token::Query => {
956                    // toplevel error recovering
957                    match self.parse_decl() {
958                        Ok(res) => decls.push(res),
959                        Err(err) => self.errors.push(err),
960                    }
961                }
962                Token::TokError => {
963                    self.errors
964                        .push(ParseError::LexerError(self.peek_span().clone()));
965                    self.cursor += 1;
966                }
967                Token::EndOfFile => break,
968                tok => {
969                    self.errors.push(ParseError::FailedToParse(
970                        "declaration",
971                        tok,
972                        self.peek_span().clone(),
973                    ));
974                    // skip all tokens before the next "header" token
975                    loop {
976                        if let Token::Datatype | Token::Function | Token::Query | Token::EndOfFile =
977                            self.peek_token()
978                        {
979                            break;
980                        }
981                        self.next_token().unwrap();
982                    }
983                }
984            }
985        }
986        self.match_token(Token::EndOfFile).unwrap();
987
988        let mut datas = Vec::new();
989        let mut funcs = Vec::new();
990        let mut querys = Vec::new();
991
992        for decl in decls.into_iter() {
993            match decl {
994                Declaration::Data(data) => datas.push(data),
995                Declaration::Func(func) => funcs.push(func),
996                Declaration::Query(query) => querys.push(query),
997            }
998        }
999
1000        Program {
1001            datas,
1002            funcs,
1003            querys,
1004        }
1005    }
1006}
1007
1008pub fn parse_program(src: &str) -> (Program, Vec<ParseError>) {
1009    let mut pass = Parser::new(src);
1010    let prog = pass.parse_program();
1011    (prog, pass.errors)
1012}
1013
1014#[test]
1015fn parser_test() {
1016    let src = r#"
1017// test line comment
1018/*
1019    /*
1020        test block comment
1021    */
1022*/
1023
1024datatype IntList where
1025| Cons(Int, IntList)
1026| Nil
1027end
1028
1029function append(xs: IntList, x: Int) -> IntList
1030begin
1031    match xs with
1032    | Cons(head, tail) => Cons(head, append(tail, x))
1033    | Nil => Cons(x, Nil)
1034    end
1035end
1036
1037function is_elem(xs: IntList, x: Int) -> Bool
1038begin
1039    match xs with
1040    | Cons(head, tail) => if head == x then true else is_elem(tail, x) 
1041    | Nil => false
1042    end
1043end
1044
1045function is_elem_after_append(xs: IntList, x: Int) -> Bool
1046begin
1047    guard !is_elem(append(xs, x), x);
1048    true
1049end
1050
1051query is_elem_after_append(depth_step=5, depth_limit=50, answer_limit=1)
1052"#;
1053    let (_prog, errs) = parse_program(&src);
1054    // println!("{:#?}", prog);
1055
1056    assert!(errs.is_empty());
1057
1058    // for diag in diags {
1059    //     println!("{}", diag.report(s, 10));
1060    // }
1061}
prune_lang/syntax/parser.rs

prune_lang/syntax/
parser.rs
