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

prune_lang/syntax/
parser.rs
