parser/
lib.rs

1pub mod ast;
2mod ast_tree_test;
3mod parser_test;
4mod precedences;
5pub mod validation;
6
7pub extern crate lexer;
8
9use crate::ast::*;
10use crate::precedences::{get_token_precedence, Precedence};
11use lexer::token::{Span, Token, TokenKind};
12use lexer::Lexer;
13
14type ParseError = String;
15type ParseErrors = Vec<ParseError>;
16
17pub struct Parser<'a> {
18    lexer: Lexer<'a>,
19    current_token: Token,
20    peek_token: Token,
21    errors: ParseErrors,
22    block_depth: usize,
23}
24
25impl<'a> Parser<'a> {
26    pub fn new(mut lexer: Lexer<'a>) -> Parser<'a> {
27        let cur = lexer.next_token();
28        let next = lexer.next_token();
29        let errors = Vec::new();
30        // in strict sense, rust can be as classic go pattern, but it requires more work
31        // so let's just use pattern matching
32        // ```rust
33        // type PrefixParseFn = fn() -> Result<Expression, ParseError>;
34        // type InfixParseFn = fn(Expression) -> Result<Expression, ParseError>;
35        // let prefix_parse_fns = HashMap::new();
36        // let infix_parse_fns = HashMap::new();
37        // ```
38
39        let p = Parser {
40            lexer,
41            current_token: cur,
42            peek_token: next,
43            errors,
44            block_depth: 0,
45        };
46
47        return p;
48    }
49
50    fn next_token(&mut self) {
51        self.current_token = self.peek_token.clone();
52        self.peek_token = self.lexer.next_token();
53    }
54
55    fn current_token_is(&mut self, token: &TokenKind) -> bool {
56        self.current_token.kind == *token
57    }
58
59    fn peek_token_is(&mut self, token: &TokenKind) -> bool {
60        self.peek_token.kind == *token
61    }
62
63    fn expect_peek(&mut self, token: &TokenKind) -> Result<(), ParseError> {
64        self.next_token();
65        if self.current_token.kind == *token {
66            Ok(())
67        } else {
68            let e = format!("expected token: {} got: {}", token, self.current_token);
69            Err(e)
70        }
71    }
72
73    pub fn parse_program(&mut self) -> Result<Program, ParseErrors> {
74        let mut program = Program::new();
75        while !self.current_token_is(&TokenKind::EOF) {
76            // a lone `;` is an empty statement, not the start of an expression
77            if self.current_token_is(&TokenKind::SEMICOLON) {
78                self.next_token();
79                continue;
80            }
81            match self.parse_statement() {
82                Ok(stmt) => program.body.push(stmt),
83                Err(e) => self.errors.push(e),
84            }
85            self.next_token();
86        }
87        program.span.end = self.current_token.span.end;
88
89        if self.errors.is_empty() {
90            return Ok(program);
91        } else {
92            return Err(self.errors.clone());
93        }
94    }
95
96    fn parse_statement(&mut self) -> Result<Statement, ParseError> {
97        match self.current_token.kind {
98            TokenKind::LET => self.parse_let_statement(),
99            TokenKind::RETURN => self.parse_return_statement(),
100            TokenKind::CLASS if self.block_depth == 0 => self.parse_class_declaration(),
101            TokenKind::CLASS => Err("class declarations are only allowed at top level".to_string()),
102            _ => self.parse_expression_statement(),
103        }
104    }
105
106    fn parse_let_statement(&mut self) -> Result<Statement, ParseError> {
107        let start = self.current_token.span.start;
108        self.next_token();
109
110        let name = self.current_token.clone();
111        let identifier_name = match &self.current_token.kind {
112            TokenKind::IDENTIFIER {
113                name,
114            } => name.to_string(),
115            _ => return Err(format!("{} not an identifier", self.current_token)),
116        };
117
118        self.expect_peek(&TokenKind::ASSIGN)?;
119        self.next_token();
120
121        let mut value = self.parse_expression(Precedence::Lowest)?.0;
122        if self.peek_token_is(&TokenKind::ASSIGN) {
123            return Err("property assignment is only allowed as a statement".to_string());
124        }
125        if let Expression::FUNCTION(ref mut f) = value {
126            f.name = identifier_name;
127        }
128
129        if self.peek_token_is(&TokenKind::SEMICOLON) {
130            self.next_token();
131        }
132
133        let end = self.current_token.span.end;
134
135        return Ok(Statement::Let(Let {
136            identifier: name,
137            expr: value,
138            span: Span {
139                start,
140                end,
141            },
142        }));
143    }
144
145    fn parse_return_statement(&mut self) -> Result<Statement, ParseError> {
146        let start = self.current_token.span.start;
147        self.next_token();
148
149        let value = self.parse_expression(Precedence::Lowest)?.0;
150
151        if self.peek_token_is(&TokenKind::ASSIGN) {
152            return Err("property assignment is only allowed as a statement".to_string());
153        }
154
155        if self.peek_token_is(&TokenKind::SEMICOLON) {
156            self.next_token();
157        }
158        let end = self.current_token.span.end;
159
160        return Ok(Statement::Return(ReturnStatement {
161            argument: value,
162            span: Span {
163                start,
164                end,
165            },
166        }));
167    }
168
169    fn parse_expression_statement(&mut self) -> Result<Statement, ParseError> {
170        let (expr, cover_span) = self.parse_expression(Precedence::Lowest)?;
171
172        if self.peek_token_is(&TokenKind::ASSIGN) {
173            let property_expression = match expr {
174                Expression::Property(property) => property,
175                _ => return Err("only instance property assignment is supported".to_string()),
176            };
177
178            self.next_token();
179            self.next_token();
180            let (value, value_span) = self.parse_expression(Precedence::Lowest)?;
181            if self.peek_token_is(&TokenKind::ASSIGN) {
182                return Err("chained property assignment is not supported".to_string());
183            }
184
185            let mut end = value_span.end;
186            if self.peek_token_is(&TokenKind::SEMICOLON) {
187                self.next_token();
188                end = self.current_token.span.end;
189            }
190
191            return Ok(Statement::SetProperty(SetPropertyStatement {
192                object: property_expression.object,
193                property: property_expression.property,
194                value,
195                span: Span {
196                    start: cover_span.start,
197                    end,
198                },
199            }));
200        }
201
202        if self.peek_token_is(&TokenKind::SEMICOLON) {
203            self.next_token();
204        }
205
206        Ok(Statement::Expr(expr))
207    }
208
209    fn parse_expression(
210        &mut self,
211        precedence: Precedence,
212    ) -> Result<(Expression, Span), ParseError> {
213        let (mut left, mut cover_span) = self.parse_prefix_expression()?;
214        while self.peek_token.kind != TokenKind::SEMICOLON
215            && precedence < get_token_precedence(&self.peek_token.kind)
216        {
217            match self.parse_infix_expression(&left, &cover_span) {
218                Some(infix) => {
219                    (left, cover_span) = infix?;
220                }
221                None => {
222                    return Ok((left, cover_span));
223                }
224            }
225        }
226
227        Ok((left, cover_span))
228    }
229
230    fn parse_prefix_expression(&mut self) -> Result<(Expression, Span), ParseError> {
231        // this is prefix fn map :)
232        match &self.current_token.kind {
233            TokenKind::IDENTIFIER {
234                name,
235            } => {
236                let span = self.current_token.span.clone();
237                return Ok((
238                    Expression::IDENTIFIER(IDENTIFIER {
239                        name: name.clone(),
240                        span: span.clone(),
241                    }),
242                    span,
243                ));
244            }
245            TokenKind::INT(i) => {
246                let span = self.current_token.span.clone();
247                return Ok((
248                    Expression::LITERAL(Literal::Integer(Integer {
249                        raw: *i,
250                        span: span.clone(),
251                    })),
252                    span,
253                ));
254            }
255            TokenKind::STRING(s) => {
256                let span = self.current_token.span.clone();
257                return Ok((
258                    Expression::LITERAL(Literal::String(StringType {
259                        raw: s.to_string(),
260                        span: span.clone(),
261                    })),
262                    span,
263                ));
264            }
265            b @ TokenKind::TRUE | b @ TokenKind::FALSE => {
266                let span = self.current_token.span.clone();
267                return Ok((
268                    Expression::LITERAL(Literal::Boolean(Boolean {
269                        raw: *b == TokenKind::TRUE,
270                        span: span.clone(),
271                    })),
272                    span,
273                ));
274            }
275            TokenKind::BANG | TokenKind::MINUS => {
276                let start = self.current_token.span.start;
277                let prefix_op = self.current_token.clone();
278                self.next_token();
279                let (expr, span) = self.parse_expression(Precedence::Prefix)?;
280                let expression_span = Span {
281                    start,
282                    end: span.end,
283                };
284                return Ok((
285                    Expression::PREFIX(UnaryExpression {
286                        op: prefix_op,
287                        operand: Box::new(expr),
288                        span: expression_span.clone(),
289                    }),
290                    expression_span,
291                ));
292            }
293            TokenKind::LPAREN => {
294                let start = self.current_token.span.start;
295                self.next_token();
296                let expr = self.parse_expression(Precedence::Lowest)?.0;
297                self.expect_peek(&TokenKind::RPAREN)?;
298                let span = Span {
299                    start,
300                    end: self.current_token.span.end,
301                };
302                return Ok((expr, span));
303            }
304            TokenKind::IF => {
305                let expression = self.parse_if_expression()?;
306                let span = expression.span().clone();
307                Ok((expression, span))
308            }
309            TokenKind::FUNCTION => {
310                let expression = self.parse_fn_expression()?;
311                let span = expression.span().clone();
312                Ok((expression, span))
313            }
314            TokenKind::LBRACKET => {
315                let (elements, span) = self.parse_expression_list(&TokenKind::RBRACKET)?;
316                return Ok((
317                    Expression::LITERAL(Literal::Array(Array {
318                        elements,
319                        span: span.clone(),
320                    })),
321                    span,
322                ));
323            }
324            TokenKind::LBRACE => {
325                let expression = self.parse_hash_expression()?;
326                let span = expression.span().clone();
327                Ok((expression, span))
328            }
329            TokenKind::THIS => {
330                let span = self.current_token.span.clone();
331                Ok((
332                    Expression::This(ThisExpression {
333                        span: span.clone(),
334                    }),
335                    span,
336                ))
337            }
338            TokenKind::NEW => {
339                let expression = self.parse_new_expression()?;
340                let span = expression.span().clone();
341                Ok((expression, span))
342            }
343            _ => Err(format!("no prefix function for token: {}", self.current_token)),
344        }
345    }
346
347    fn parse_infix_expression(
348        &mut self,
349        left: &Expression,
350        left_span: &Span,
351    ) -> Option<Result<(Expression, Span), ParseError>> {
352        match self.peek_token.kind {
353            TokenKind::PLUS
354            | TokenKind::MINUS
355            | TokenKind::ASTERISK
356            | TokenKind::SLASH
357            | TokenKind::EQ
358            | TokenKind::NotEq
359            | TokenKind::LT
360            | TokenKind::GT => {
361                self.next_token();
362                let infix_op = self.current_token.clone();
363                let precedence_value = get_token_precedence(&self.current_token.kind);
364                self.next_token();
365                let result = self
366                    .parse_expression(precedence_value)
367                    .map(|(right, span)| {
368                        let expression_span = Span {
369                            start: left_span.start,
370                            end: span.end,
371                        };
372                        (
373                            Expression::INFIX(BinaryExpression {
374                                op: infix_op,
375                                left: Box::new(left.clone()),
376                                right: Box::new(right),
377                                span: expression_span.clone(),
378                            }),
379                            expression_span,
380                        )
381                    });
382                return Some(result);
383            }
384            TokenKind::LPAREN => {
385                self.next_token();
386                return Some(self.parse_fn_call_expression(left.clone(), left_span.start));
387            }
388            TokenKind::LBRACKET => {
389                self.next_token();
390                return Some(self.parse_index_expression(left.clone(), left_span.start));
391            }
392            TokenKind::DOT => {
393                self.next_token();
394                return Some(self.parse_property_expression(left.clone(), left_span.start));
395            }
396            _ => None,
397        }
398    }
399
400    fn parse_if_expression(&mut self) -> Result<Expression, ParseError> {
401        let start = self.current_token.span.start;
402        self.expect_peek(&TokenKind::LPAREN)?;
403        self.next_token();
404
405        let condition = self.parse_expression(Precedence::Lowest)?.0;
406        self.expect_peek(&TokenKind::RPAREN)?;
407        self.expect_peek(&TokenKind::LBRACE)?;
408
409        let consequent = self.parse_block_statement()?;
410
411        let alternate = if self.peek_token_is(&TokenKind::ELSE) {
412            self.next_token();
413            self.expect_peek(&TokenKind::LBRACE)?;
414            Some(self.parse_block_statement()?)
415        } else {
416            None
417        };
418
419        let end = self.current_token.span.end;
420
421        return Ok(Expression::IF(IF {
422            condition: Box::new(condition),
423            consequent,
424            alternate,
425            span: Span {
426                start,
427                end,
428            },
429        }));
430    }
431
432    fn parse_block_statement(&mut self) -> Result<BlockStatement, ParseError> {
433        let start = self.current_token.span.start;
434        self.block_depth += 1;
435        self.next_token();
436        let mut block_statement = Vec::new();
437
438        while !self.current_token_is(&TokenKind::RBRACE) && !self.current_token_is(&TokenKind::EOF)
439        {
440            if self.current_token_is(&TokenKind::SEMICOLON) {
441                self.next_token();
442                continue;
443            }
444            let statement = match self.parse_statement() {
445                Ok(statement) => statement,
446                Err(error) => {
447                    self.block_depth -= 1;
448                    return Err(error);
449                }
450            };
451            block_statement.push(statement);
452
453            self.next_token();
454        }
455
456        self.block_depth -= 1;
457        if self.current_token_is(&TokenKind::EOF) {
458            return Err("expected '}' before end of input".to_string());
459        }
460
461        let end = self.current_token.span.end;
462
463        Ok(BlockStatement {
464            body: block_statement,
465            span: Span {
466                start,
467                end,
468            },
469        })
470    }
471
472    fn parse_fn_expression(&mut self) -> Result<Expression, ParseError> {
473        let start = self.current_token.span.start;
474        self.expect_peek(&TokenKind::LPAREN)?;
475
476        let params = self.parse_fn_parameters()?;
477
478        self.expect_peek(&TokenKind::LBRACE)?;
479
480        let function_body = self.parse_block_statement()?;
481
482        let end = self.current_token.span.end;
483
484        Ok(Expression::FUNCTION(FunctionDeclaration {
485            params,
486            body: function_body,
487            span: Span {
488                start,
489                end,
490            },
491            name: "".to_string(),
492        }))
493    }
494
495    fn parse_fn_parameters(&mut self) -> Result<Vec<IDENTIFIER>, ParseError> {
496        let mut params = Vec::new();
497        if self.peek_token_is(&TokenKind::RPAREN) {
498            self.next_token();
499            return Ok(params);
500        }
501
502        self.next_token();
503
504        match &self.current_token.kind {
505            TokenKind::IDENTIFIER {
506                name,
507            } => params.push(IDENTIFIER {
508                name: name.clone(),
509                span: self.current_token.span.clone(),
510            }),
511            token => {
512                return Err(format!("expected function params  to be an identifier, got {}", token))
513            }
514        }
515
516        while self.peek_token_is(&TokenKind::COMMA) {
517            self.next_token();
518            self.next_token();
519            match &self.current_token.kind {
520                TokenKind::IDENTIFIER {
521                    name,
522                } => params.push(IDENTIFIER {
523                    name: name.clone(),
524                    span: self.current_token.span.clone(),
525                }),
526                token => {
527                    return Err(format!(
528                        "expected function params  to be an identifier, got {}",
529                        token
530                    ))
531                }
532            }
533        }
534
535        self.expect_peek(&TokenKind::RPAREN)?;
536
537        return Ok(params);
538    }
539
540    fn parse_fn_call_expression(
541        &mut self,
542        expr: Expression,
543        start: usize,
544    ) -> Result<(Expression, Span), ParseError> {
545        let (arguments, ..) = self.parse_expression_list(&TokenKind::RPAREN)?;
546        let end = self.current_token.span.end;
547        let callee = Box::new(expr);
548        let span = Span {
549            start,
550            end,
551        };
552
553        Ok((
554            Expression::FunctionCall(FunctionCall {
555                callee,
556                arguments,
557                span: span.clone(),
558            }),
559            span,
560        ))
561    }
562
563    fn parse_expression_list(
564        &mut self,
565        end: &TokenKind,
566    ) -> Result<(Vec<Expression>, Span), ParseError> {
567        let start = self.current_token.span.start;
568        let mut expr_list = Vec::new();
569        if self.peek_token_is(end) {
570            self.next_token();
571            let end = self.current_token.span.end;
572            return Ok((
573                expr_list,
574                Span {
575                    start,
576                    end,
577                },
578            ));
579        }
580
581        self.next_token();
582
583        expr_list.push(self.parse_expression(Precedence::Lowest)?.0);
584
585        while self.peek_token_is(&TokenKind::COMMA) {
586            self.next_token();
587            self.next_token();
588            expr_list.push(self.parse_expression(Precedence::Lowest)?.0);
589        }
590
591        self.expect_peek(end)?;
592        let end = self.current_token.span.end;
593
594        return Ok((
595            expr_list,
596            Span {
597                start,
598                end,
599            },
600        ));
601    }
602
603    fn parse_index_expression(
604        &mut self,
605        left: Expression,
606        start: usize,
607    ) -> Result<(Expression, Span), ParseError> {
608        self.next_token();
609        let index = self.parse_expression(Precedence::Lowest)?.0;
610
611        self.expect_peek(&TokenKind::RBRACKET)?;
612
613        let end = self.current_token.span.end;
614
615        let span = Span {
616            start,
617            end,
618        };
619        return Ok((
620            Expression::Index(Index {
621                object: Box::new(left),
622                index: Box::new(index),
623                span: span.clone(),
624            }),
625            span,
626        ));
627    }
628
629    fn parse_property_expression(
630        &mut self,
631        object: Expression,
632        start: usize,
633    ) -> Result<(Expression, Span), ParseError> {
634        self.next_token();
635        let property = match &self.current_token.kind {
636            TokenKind::IDENTIFIER {
637                name,
638            } => IDENTIFIER {
639                name: name.clone(),
640                span: self.current_token.span.clone(),
641            },
642            _ => return Err("expected property name after '.'".to_string()),
643        };
644        let span = Span {
645            start,
646            end: property.span.end,
647        };
648        Ok((
649            Expression::Property(PropertyExpression {
650                object: Box::new(object),
651                property,
652                span: span.clone(),
653            }),
654            span,
655        ))
656    }
657
658    fn parse_new_expression(&mut self) -> Result<Expression, ParseError> {
659        let start = self.current_token.span.start;
660        self.next_token();
661        let callee = match &self.current_token.kind {
662            TokenKind::IDENTIFIER {
663                name,
664            } => IDENTIFIER {
665                name: name.clone(),
666                span: self.current_token.span.clone(),
667            },
668            _ => return Err("expected class name after 'new'".to_string()),
669        };
670
671        if !self.peek_token_is(&TokenKind::LPAREN) {
672            return Err("new expression requires an argument list".to_string());
673        }
674        self.next_token();
675        let (arguments, arguments_span) = self.parse_expression_list(&TokenKind::RPAREN)?;
676        Ok(Expression::New(NewExpression {
677            callee,
678            arguments,
679            span: Span {
680                start,
681                end: arguments_span.end,
682            },
683        }))
684    }
685
686    fn parse_class_declaration(&mut self) -> Result<Statement, ParseError> {
687        let start = self.current_token.span.start;
688        self.next_token();
689        let class_name = match &self.current_token.kind {
690            TokenKind::IDENTIFIER {
691                name,
692            } => IDENTIFIER {
693                name: name.clone(),
694                span: self.current_token.span.clone(),
695            },
696            _ => return Err("expected class name after 'class'".to_string()),
697        };
698
699        self.expect_peek(&TokenKind::LBRACE)?;
700        let mut methods = Vec::new();
701        let mut method_names = std::collections::HashSet::new();
702        let mut has_constructor = false;
703
704        while !self.peek_token_is(&TokenKind::RBRACE) {
705            self.next_token();
706            if self.current_token_is(&TokenKind::EOF) {
707                return Err(format!("expected '}}' after class {}", class_name.name));
708            }
709            // methods need no separator, but a `;` between them is harmless
710            if self.current_token_is(&TokenKind::SEMICOLON) {
711                continue;
712            }
713
714            let method_name = match &self.current_token.kind {
715                TokenKind::IDENTIFIER {
716                    name,
717                } => IDENTIFIER {
718                    name: name.clone(),
719                    span: self.current_token.span.clone(),
720                },
721                _ => return Err("expected method definition in class body".to_string()),
722            };
723            let method_start = method_name.span.start;
724            let kind = if method_name.name == "constructor" {
725                if has_constructor {
726                    return Err(format!("class {} has more than one constructor", class_name.name));
727                }
728                has_constructor = true;
729                MethodKind::Constructor
730            } else {
731                if !method_names.insert(method_name.name.clone()) {
732                    return Err(format!(
733                        "duplicate method {}.{}",
734                        class_name.name, method_name.name
735                    ));
736                }
737                MethodKind::Method
738            };
739
740            self.expect_peek(&TokenKind::LPAREN)?;
741            let params = self.parse_fn_parameters()?;
742            self.expect_peek(&TokenKind::LBRACE)?;
743            let body = self.parse_block_statement()?;
744            let method_end = body.span.end;
745            methods.push(MethodDefinition {
746                kind,
747                name: method_name,
748                params,
749                body,
750                span: Span {
751                    start: method_start,
752                    end: method_end,
753                },
754            });
755        }
756
757        self.next_token();
758        Ok(Statement::Class(ClassDeclaration {
759            name: class_name,
760            methods,
761            span: Span {
762                start,
763                end: self.current_token.span.end,
764            },
765        }))
766    }
767
768    fn parse_hash_expression(&mut self) -> Result<Expression, ParseError> {
769        let mut map = Vec::new();
770        let start = self.current_token.span.start;
771        while !self.peek_token_is(&TokenKind::RBRACE) {
772            self.next_token();
773
774            let key = self.parse_expression(Precedence::Lowest)?.0;
775
776            self.expect_peek(&TokenKind::COLON)?;
777
778            self.next_token();
779            let value = self.parse_expression(Precedence::Lowest)?.0;
780
781            map.push((key, value));
782
783            if !self.peek_token_is(&TokenKind::RBRACE) {
784                self.expect_peek(&TokenKind::COMMA)?;
785            }
786        }
787
788        self.expect_peek(&TokenKind::RBRACE)?;
789        let end = self.current_token.span.end;
790
791        Ok(Expression::LITERAL(Literal::Hash(Hash {
792            elements: map,
793            span: Span {
794                start,
795                end,
796            },
797        })))
798    }
799}
800
801pub fn parse(input: &str) -> Result<Node, ParseErrors> {
802    let lexer = Lexer::new(input);
803    let mut parser = Parser::new(lexer);
804    let program = parser.parse_program()?;
805
806    Ok(Node::Program(program))
807}
808
809pub fn parse_ast_json_string(input: &str) -> Result<String, ParseErrors> {
810    let node = parse(input)?;
811    let ast = serde_json::to_string_pretty(&node).unwrap();
812
813    return Ok(ast);
814}
815
816/// Serialize the parser AST without routing i64 integer literals through a
817/// JavaScript `number`. The JSON shape otherwise stays identical to
818/// [`parse_ast_json_string`].
819pub fn parse_ast_lossless_json_string(input: &str) -> Result<String, ParseErrors> {
820    let node = parse(input)?;
821    let mut ast = serde_json::to_value(&node).expect("AST serialization should not fail");
822    stringify_integer_literals(&mut ast);
823    Ok(serde_json::to_string_pretty(&ast).expect("AST serialization should not fail"))
824}
825
826/// Rewrite every `Integer` literal's `raw` field from a JSON number to a
827/// decimal string so JavaScript consumers keep the full signed 64-bit range.
828/// Shared with the wasm `analyze_lossless` envelope.
829pub fn stringify_integer_literals(value: &mut serde_json::Value) {
830    match value {
831        serde_json::Value::Array(values) => {
832            for value in values {
833                stringify_integer_literals(value);
834            }
835        }
836        serde_json::Value::Object(object) => {
837            if object.get("type").and_then(serde_json::Value::as_str) == Some("Integer") {
838                if let Some(raw) = object.get_mut("raw") {
839                    if let Some(integer) = raw.as_i64() {
840                        *raw = serde_json::Value::String(integer.to_string());
841                    }
842                }
843            }
844            for value in object.values_mut() {
845                stringify_integer_literals(value);
846            }
847        }
848        _ => {}
849    }
850}
parser/lib.rs

parser/
lib.rs
