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

prune_lang/syntax/
parser.rs
