cellang/
parser.rs

1use crate::Lexer;
2use crate::SyntaxError;
3use crate::lexer::{Token, TokenType};
4use miette::SourceSpan;
5use serde::Serialize;
6use serde::ser::SerializeStruct;
7use std::borrow::Cow;
8use std::fmt;
9
10/// A parser for the language.
11/// This parser is a Pratt parser, which is a top-down operator precedence parser.
12/// Produces TokenTree (AST) from the input by using the lexer.
13pub struct Parser<'src> {
14    input: &'src str,
15    lexer: Lexer<'src>,
16}
17
18impl<'src> Parser<'src> {
19    /// Creates a new parser from the given input string.
20    pub fn new(input: &'src str) -> Self {
21        Self {
22            input,
23            lexer: Lexer::new(input),
24        }
25    }
26
27    /// Parses the whole input and returns the AST.
28    pub fn parse(&mut self) -> Result<TokenTree<'src>, SyntaxError> {
29        self.parse_expr(0)
30    }
31
32    fn parse_expr(
33        &mut self,
34        min_bp: u8,
35    ) -> Result<TokenTree<'src>, SyntaxError> {
36        let lhs = match self.lexer.next() {
37            Some(Ok(token)) => token,
38            None => return Ok(TokenTree::Atom(Atom::Null)), // todo: figure out this
39            Some(Err(e)) => return Err(e),
40        };
41
42        let mut lhs = match lhs {
43            // atoms
44            Token {
45                ty: TokenType::Ident,
46                origin,
47                ..
48            } => TokenTree::Atom(Atom::Ident(origin)),
49            Token {
50                ty: TokenType::Int(n),
51                ..
52            } => TokenTree::Atom(Atom::Int(n)),
53            Token {
54                ty: TokenType::Uint(n),
55                ..
56            } => TokenTree::Atom(Atom::Uint(n)),
57            Token {
58                ty: TokenType::Double(n),
59                ..
60            } => TokenTree::Atom(Atom::Double(n)),
61            Token {
62                ty: TokenType::Null,
63                ..
64            } => TokenTree::Atom(Atom::Null),
65            Token {
66                ty: TokenType::String | TokenType::RawString,
67                origin,
68                ..
69            } => TokenTree::Atom(Atom::String(Token::unescape(origin))),
70            Token {
71                ty: TokenType::Bytes | TokenType::RawBytes,
72                origin,
73                ..
74            } => TokenTree::Atom(Atom::Bytes(Token::unescape_bytes(origin))),
75            Token {
76                ty: TokenType::True,
77                ..
78            } => TokenTree::Atom(Atom::Bool(true)),
79            Token {
80                ty: TokenType::False,
81                ..
82            } => TokenTree::Atom(Atom::Bool(false)),
83
84            // dyn
85            Token {
86                ty: TokenType::Dyn, ..
87            } => {
88                self.lexer.expect(
89                    TokenType::LeftParen,
90                    "Expected opening parenthesis after dyn",
91                )?;
92                let expr = self.parse_expr(0)?;
93                self.lexer.expect(
94                    TokenType::RightParen,
95                    "Expected closing parenthesis after dyn",
96                )?;
97                TokenTree::Cons(Op::Dyn, vec![expr])
98            }
99
100            // groups
101            Token {
102                ty: TokenType::LeftParen,
103                ..
104            } => {
105                let lhs = self.parse_expr(0)?;
106                self.lexer.expect(
107                    TokenType::RightParen,
108                    "Expected closing parenthesis",
109                )?;
110                TokenTree::Cons(Op::Group, vec![lhs])
111            }
112
113            // unary operators
114            Token {
115                ty: TokenType::Not | TokenType::Minus,
116                ..
117            } => {
118                let op = match lhs.ty {
119                    TokenType::Not => Op::Not,
120                    TokenType::Minus => Op::Minus,
121                    _ => unreachable!(),
122                };
123                let ((), r_bp) = prefix_binding_power(op);
124                let rhs = self.parse_expr(r_bp)?;
125                TokenTree::Cons(op, vec![rhs])
126            }
127
128            // aggregate types
129            Token {
130                ty: TokenType::LeftBrace,
131                ..
132            } => self.parse_map()?,
133
134            Token {
135                ty: TokenType::LeftBracket,
136                ..
137            } => self.parse_list()?,
138
139            token => {
140                return Err(SyntaxError::new(
141                    self.input.to_string(),
142                    SourceSpan::new(token.offset.into(), token.span_len),
143                    format!("Unexpected token: {:?}", token),
144                )
145                .with_help("Expected an expression"));
146            }
147        };
148
149        loop {
150            let op = self.lexer.peek();
151            if op.is_some_and(|op| op.is_err()) {
152                return Err(self
153                    .lexer
154                    .next()
155                    .expect("checked Some above")
156                    .expect_err("checked Err above"));
157            }
158
159            let op = match op
160                .map(|res| res.as_ref().expect("handled Err above"))
161            {
162                None
163                | Some(Token {
164                    ty:
165                        TokenType::RightParen
166                        | TokenType::RightBracket
167                        | TokenType::RightBrace
168                        | TokenType::Comma
169                        | TokenType::Colon
170                        | TokenType::Semicolon,
171                    ..
172                }) => break,
173                Some(Token {
174                    ty: TokenType::LeftParen,
175                    ..
176                }) => Op::Call,
177                Some(Token {
178                    ty: TokenType::LeftBracket,
179                    ..
180                }) => Op::Index,
181                Some(Token {
182                    ty: TokenType::Dot, ..
183                }) => Op::Field,
184                Some(Token {
185                    ty: TokenType::Minus,
186                    ..
187                }) => Op::Minus,
188                Some(Token {
189                    ty: TokenType::Plus,
190                    ..
191                }) => Op::Plus,
192                Some(Token {
193                    ty: TokenType::Star,
194                    ..
195                }) => Op::Multiply,
196                Some(Token {
197                    ty: TokenType::Percent,
198                    ..
199                }) => Op::Mod,
200                Some(Token {
201                    ty: TokenType::NotEqual,
202                    ..
203                }) => Op::NotEqual,
204                Some(Token {
205                    ty: TokenType::In, ..
206                }) => Op::In,
207                Some(Token {
208                    ty: TokenType::EqualEqual,
209                    ..
210                }) => Op::EqualEqual,
211                Some(Token {
212                    ty: TokenType::LessEqual,
213                    ..
214                }) => Op::LessEqual,
215                Some(Token {
216                    ty: TokenType::GreaterEqual,
217                    ..
218                }) => Op::GreaterEqual,
219                Some(Token {
220                    ty: TokenType::Less,
221                    ..
222                }) => Op::Less,
223                Some(Token {
224                    ty: TokenType::Greater,
225                    ..
226                }) => Op::Greater,
227                Some(Token {
228                    ty: TokenType::Slash,
229                    ..
230                }) => Op::Devide,
231                Some(Token {
232                    ty: TokenType::And, ..
233                }) => Op::And,
234                Some(Token {
235                    ty: TokenType::Or, ..
236                }) => Op::Or,
237                Some(Token {
238                    ty: TokenType::QuestionMark,
239                    ..
240                }) => Op::IfTernary,
241
242                Some(token) => {
243                    return Err(SyntaxError::new(
244                        self.input.to_string(),
245                        SourceSpan::new(token.offset.into(), token.span_len),
246                        format!("Unexpected token: {:?}", token),
247                    )
248                    .with_help("Expected an operator"));
249                }
250            };
251
252            if let Some((l_bp, ())) = postfix_binding_power(op) {
253                if l_bp < min_bp {
254                    break;
255                }
256                self.lexer.next();
257
258                lhs = match op {
259                    Op::Call => TokenTree::Call {
260                        func: Box::new(lhs),
261                        args: self.parse_fn_call_args()?,
262                        is_method: false,
263                    },
264                    Op::Index => {
265                        let index = self.parse_expr(0)?;
266                        self.lexer.expect(
267                            TokenType::RightBracket,
268                            "Expected closing bracket",
269                        )?;
270                        TokenTree::Cons(op, vec![lhs, index])
271                    }
272                    _ => TokenTree::Cons(op, vec![lhs]),
273                };
274                continue;
275            }
276
277            if let Some((l_bp, r_bp)) = infix_binding_power(op) {
278                if l_bp < min_bp {
279                    break;
280                }
281                self.lexer.next();
282
283                lhs = match op {
284                    Op::IfTernary => {
285                        let mhs = self.parse_expr(0)?;
286                        self.lexer.expect(
287                            TokenType::Colon,
288                            "Expected colon after the condition",
289                        )?;
290                        let rhs = self.parse_expr(r_bp)?;
291                        TokenTree::Cons(op, vec![lhs, mhs, rhs])
292                    }
293                    Op::Field => {
294                        let rhs = self.parse_expr(r_bp)?;
295                        match rhs {
296                            TokenTree::Call {
297                                func,
298                                mut args,
299                                is_method,
300                            } => {
301                                if !is_method {
302                                    TokenTree::Call {
303                                        func,
304                                        args: vec![lhs]
305                                            .into_iter()
306                                            .chain(args)
307                                            .collect(),
308                                        is_method: true,
309                                    }
310                                } else if args.is_empty() {
311                                    args.insert(0, lhs);
312                                    TokenTree::Call {
313                                        func,
314                                        args,
315                                        is_method: true,
316                                    }
317                                } else {
318                                    let access = args.remove(0);
319                                    let receiver = Self::attach_method_receiver(
320                                        lhs, access,
321                                    );
322                                    args.insert(0, receiver);
323                                    TokenTree::Call {
324                                        func,
325                                        args,
326                                        is_method,
327                                    }
328                                }
329                            }
330                            rhs => Self::chain_field_access(lhs, rhs),
331                        }
332                    }
333                    _ => {
334                        let rhs = self.parse_expr(r_bp)?;
335                        TokenTree::Cons(op, vec![lhs, rhs])
336                    }
337                };
338
339                continue;
340            }
341
342            break;
343        }
344
345        Ok(lhs)
346    }
347
348    fn attach_method_receiver(
349        lhs: TokenTree<'src>,
350        receiver: TokenTree<'src>,
351    ) -> TokenTree<'src> {
352        match receiver {
353            TokenTree::Call {
354                func,
355                args,
356                is_method: false,
357            } => TokenTree::Call {
358                func,
359                args: std::iter::once(lhs).chain(args).collect(),
360                is_method: true,
361            },
362            TokenTree::Call {
363                func,
364                mut args,
365                is_method: true,
366            } => {
367                if args.is_empty() {
368                    args.insert(0, lhs);
369                    TokenTree::Call {
370                        func,
371                        args,
372                        is_method: true,
373                    }
374                } else {
375                    let nested = args.remove(0);
376                    let updated = Self::attach_method_receiver(lhs, nested);
377                    args.insert(0, updated);
378                    TokenTree::Call {
379                        func,
380                        args,
381                        is_method: true,
382                    }
383                }
384            }
385            other => Self::chain_field_access(lhs, other),
386        }
387    }
388
389    fn chain_field_access(
390        lhs: TokenTree<'src>,
391        rhs: TokenTree<'src>,
392    ) -> TokenTree<'src> {
393        let mut acc = lhs;
394        let mut current = rhs;
395        loop {
396            current = match current {
397                TokenTree::Cons(Op::Field, mut nodes) if nodes.len() == 2 => {
398                    let next = nodes.remove(0);
399                    let rest = nodes.remove(0);
400                    acc = TokenTree::Cons(Op::Field, vec![acc, next]);
401                    rest
402                }
403                other => return TokenTree::Cons(Op::Field, vec![acc, other]),
404            };
405        }
406    }
407
408    fn parse_map(&mut self) -> Result<TokenTree<'src>, SyntaxError> {
409        let mut items = Vec::new();
410        if matches!(
411            self.lexer.peek(),
412            Some(Ok(Token {
413                ty: TokenType::RightBrace,
414                ..
415            }))
416        ) {
417            self.lexer.next();
418            return Ok(TokenTree::Cons(Op::Map, items));
419        }
420        loop {
421            let key = self.parse_expr(0)?;
422            self.lexer.expect(
423                TokenType::Colon,
424                "Expected colon between map key and value",
425            )?;
426            let value = self.parse_expr(0)?;
427            items.push(key);
428            items.push(value);
429
430            let token = self.lexer.expect_where(
431                |token| {
432                    matches!(token.ty, TokenType::Comma | TokenType::RightBrace)
433                },
434                "continuing map",
435            )?;
436
437            if token.ty == TokenType::RightBrace {
438                break;
439            }
440        }
441        Ok(TokenTree::Cons(Op::Map, items))
442    }
443
444    fn parse_list(&mut self) -> Result<TokenTree<'src>, SyntaxError> {
445        let mut items = Vec::new();
446        if matches!(
447            self.lexer.peek(),
448            Some(Ok(Token {
449                ty: TokenType::RightBracket,
450                ..
451            }))
452        ) {
453            self.lexer.next();
454            return Ok(TokenTree::Cons(Op::List, items));
455        }
456        loop {
457            let item = self.parse_expr(0)?;
458            items.push(item);
459            let token = self.lexer.expect_where(
460                |token| {
461                    matches!(
462                        token.ty,
463                        TokenType::Comma | TokenType::RightBracket
464                    )
465                },
466                "continuing list",
467            )?;
468
469            if token.ty == TokenType::RightBracket {
470                break;
471            }
472        }
473        Ok(TokenTree::Cons(Op::List, items))
474    }
475
476    fn parse_fn_call_args(
477        &mut self,
478    ) -> Result<Vec<TokenTree<'src>>, SyntaxError> {
479        let mut args = Vec::new();
480
481        if !matches!(
482            self.lexer.peek(),
483            Some(Ok(Token {
484                ty: TokenType::RightParen,
485                ..
486            }))
487        ) {
488            loop {
489                let arg = self.parse_expr(0)?;
490                args.push(arg);
491                let token = self.lexer.expect_where(
492                    |token| {
493                        matches!(
494                            token.ty,
495                            TokenType::Comma | TokenType::RightParen
496                        )
497                    },
498                    "continuing argument list",
499                )?;
500
501                if token.ty == TokenType::RightParen {
502                    break;
503                }
504            }
505        } else {
506            self.lexer.next();
507        }
508        Ok(args)
509    }
510}
511
512/// An atomic value in the AST.
513/// This is the smallest unit of the AST.
514#[derive(Debug, Clone, PartialEq)]
515pub enum Atom<'src> {
516    Bool(bool),
517    Int(i64),
518    Uint(u64),
519    Double(f64),
520    String(Cow<'src, str>),
521    Bytes(Cow<'src, [u8]>),
522    Ident(&'src str),
523    Null,
524}
525
526impl Serialize for Atom<'_> {
527    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
528    where
529        S: serde::Serializer,
530    {
531        match self {
532            Atom::Bool(b) => {
533                let mut s = serializer.serialize_struct("Bool", 2)?;
534                s.serialize_field("kind", "bool")?;
535                s.serialize_field("value", b)?;
536                s.end()
537            }
538            Atom::Int(i) => {
539                let mut s = serializer.serialize_struct("Int", 2)?;
540                s.serialize_field("kind", "int")?;
541                s.serialize_field("value", i)?;
542                s.end()
543            }
544            Atom::Uint(u) => {
545                let mut s = serializer.serialize_struct("Uint", 2)?;
546                s.serialize_field("kind", "uint")?;
547                s.serialize_field("value", u)?;
548                s.end()
549            }
550            Atom::Double(d) => {
551                let mut s = serializer.serialize_struct("Double", 2)?;
552                s.serialize_field("kind", "double")?;
553                s.serialize_field("value", d)?;
554                s.end()
555            }
556            Atom::String(s) => {
557                let mut srl = serializer.serialize_struct("String", 2)?;
558                srl.serialize_field("kind", "string")?;
559                srl.serialize_field("value", s)?;
560                srl.end()
561            }
562            Atom::Bytes(b) => {
563                let mut srl = serializer.serialize_struct("Bytes", 2)?;
564                srl.serialize_field("kind", "bytes")?;
565                srl.serialize_field("value", b)?;
566                srl.end()
567            }
568            Atom::Ident(i) => {
569                let mut s = serializer.serialize_struct("Ident", 2)?;
570                s.serialize_field("kind", "ident")?;
571                s.serialize_field("value", i)?;
572                s.end()
573            }
574            Atom::Null => {
575                let mut s = serializer.serialize_struct("Null", 1)?;
576                s.serialize_field("kind", "null")?;
577                s.end()
578            }
579        }
580    }
581}
582
583impl fmt::Display for Atom<'_> {
584    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
585        match self {
586            Atom::Bool(b) => write!(f, "{b:?}"),
587            Atom::Int(i) => write!(f, "{}", i),
588            Atom::Uint(u) => write!(f, "{}", u),
589            Atom::Double(d) => write!(f, "{}", d),
590            Atom::String(s) => write!(f, "{:?}", s),
591            Atom::Bytes(b) => write!(f, "{:?}", b),
592            Atom::Ident(i) => write!(f, "{}", i),
593            Atom::Null => write!(f, "null"),
594        }
595    }
596}
597
598/// An operator in the AST.
599#[derive(Debug, Clone, Copy, PartialEq)]
600pub enum Op {
601    Minus,
602    Plus,
603    Multiply,
604    Devide,
605    Mod,
606    NotEqual,
607    EqualEqual,
608    Less,
609    LessEqual,
610    Greater,
611    GreaterEqual,
612    Not,
613    And,
614    Or,
615    IfTernary,
616    In,
617    Call,
618    Index,
619    For,
620    Field,
621    While,
622    Var,
623    Group,
624    Map,
625    List,
626    Dyn,
627}
628
629impl Serialize for Op {
630    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
631    where
632        S: serde::Serializer,
633    {
634        let mut s = serializer.serialize_struct("Op", 1)?;
635        s.serialize_field("op", &self.to_string())?;
636        s.end()
637    }
638}
639
640impl fmt::Display for Op {
641    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
642        let s = match self {
643            Op::IfTernary => "?:",
644            Op::Minus => "-",
645            Op::Plus => "+",
646            Op::Multiply => "*",
647            Op::NotEqual => "!=",
648            Op::EqualEqual => "==",
649            Op::LessEqual => "<=",
650            Op::GreaterEqual => ">=",
651            Op::Less => "<",
652            Op::Greater => ">",
653            Op::Index => "[]",
654            Op::Var => "var",
655            Op::In => "in",
656            Op::Devide => "/",
657            Op::Not => "!",
658            Op::And => "&&",
659            Op::Or => "||",
660            Op::Call => "(args)",
661            Op::For => "for",
662            Op::Field => ".",
663            Op::While => "while",
664            Op::Group => "(",
665            Op::Map => "{map}",
666            Op::List => "[list]",
667            Op::Mod => "%",
668            Op::Dyn => "dyn",
669        };
670        write!(f, "{}", s)
671    }
672}
673
674/// A node in the AST.
675#[derive(Debug, Clone, PartialEq)]
676pub enum TokenTree<'src> {
677    Atom(Atom<'src>),
678    Cons(Op, Vec<TokenTree<'src>>),
679    Call {
680        func: Box<TokenTree<'src>>,
681        args: Vec<TokenTree<'src>>,
682        is_method: bool,
683    },
684}
685
686impl Serialize for TokenTree<'_> {
687    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
688    where
689        S: serde::Serializer,
690    {
691        match self {
692            TokenTree::Atom(atom) => atom.serialize(serializer),
693            TokenTree::Cons(op, args) => {
694                let mut state = serializer.serialize_struct("Cons", 2)?;
695                state.serialize_field("op", op)?;
696                state.serialize_field("args", args)?;
697                state.end()
698            }
699            TokenTree::Call {
700                func,
701                args,
702                is_method,
703            } => {
704                let mut state = serializer.serialize_struct("Call", 3)?;
705                state.serialize_field("func", func)?;
706                state.serialize_field("args", args)?;
707                state.serialize_field("is_method", is_method)?;
708                state.end()
709            }
710        }
711    }
712}
713
714impl fmt::Display for TokenTree<'_> {
715    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
716        match self {
717            TokenTree::Atom(atom) => write!(f, "{}", atom),
718            TokenTree::Cons(op, args) => {
719                write!(f, "{}", op)?;
720                for arg in args {
721                    write!(f, " {}", arg)?;
722                }
723                Ok(())
724            }
725            TokenTree::Call {
726                func,
727                args,
728                is_method,
729            } => {
730                if *is_method {
731                    write!(
732                        f,
733                        "{}.{}({})",
734                        args[0],
735                        func,
736                        args[1..]
737                            .iter()
738                            .map(|arg| arg.to_string())
739                            .collect::<Vec<_>>()
740                            .join(", ")
741                    )
742                } else {
743                    write!(
744                        f,
745                        "{}({})",
746                        func,
747                        args.iter()
748                            .map(|arg| arg.to_string())
749                            .collect::<Vec<_>>()
750                            .join(", ")
751                    )
752                }
753            }
754        }
755    }
756}
757
758fn prefix_binding_power(op: Op) -> ((), u8) {
759    match op {
760        Op::Minus | Op::Not => ((), 13),
761        _ => panic!("Unexpected operator: {:?}", op),
762    }
763}
764
765fn postfix_binding_power(op: Op) -> Option<(u8, ())> {
766    match op {
767        Op::Index => Some((15, ())),
768        Op::Call => Some((17, ())),
769        _ => None,
770    }
771}
772
773// Precedence levels for infix operators.
774// ?: - 1,2
775// || - 3,4
776// && - 5,6
777// in - 7,8
778// == != <><=>= - 7,8
779// -(binary) +(binary) - 9,10
780// * / % - 11,12
781// ! -(unary) - 13,14
782// () . [] {} - 15,16
783
784/// Returns the binding powers for the given infix operator.
785fn infix_binding_power(op: Op) -> Option<(u8, u8)> {
786    let res = match op {
787        // '=' => (2, 1),
788        Op::IfTernary => (2, 1),
789        Op::Or => (3, 4),
790        Op::And => (5, 6),
791        Op::In
792        | Op::NotEqual
793        | Op::EqualEqual
794        | Op::Less
795        | Op::LessEqual
796        | Op::Greater
797        | Op::GreaterEqual => (7, 8),
798        Op::Plus | Op::Minus => (9, 10),
799        Op::Multiply | Op::Devide | Op::Mod => (11, 12),
800        Op::Field | Op::Call => (18, 17),
801        _ => return None,
802    };
803    Some(res)
804}
805
806#[cfg(test)]
807mod tests {
808    use super::*;
809    use miette::Report;
810
811    #[track_caller]
812    fn assert_span_matches(
813        err: &SyntaxError,
814        expected_offset: usize,
815        expected_slice: &str,
816        report: &Report,
817    ) {
818        let span = err.span();
819        let offset: usize = span.offset();
820        assert_eq!(
821            offset, expected_offset,
822            "unexpected span offset: {report:?}"
823        );
824        assert_eq!(
825            span.len(),
826            expected_slice.len(),
827            "unexpected span len: {report:?}"
828        );
829        let fragment = &err.source_text()[offset..offset + span.len()];
830        assert_eq!(
831            fragment, expected_slice,
832            "unexpected source slice: {report:?}"
833        );
834    }
835
836    #[test]
837    fn test_add_and_multiply() {
838        let input = "1 + 2 * 3";
839        let mut parser = Parser::new(input);
840        let tree = parser.parse().unwrap();
841        assert_eq!(
842            tree,
843            TokenTree::Cons(
844                Op::Plus,
845                vec![
846                    TokenTree::Atom(Atom::Int(1)),
847                    TokenTree::Cons(
848                        Op::Multiply,
849                        vec![
850                            TokenTree::Atom(Atom::Int(2)),
851                            TokenTree::Atom(Atom::Int(3)),
852                        ]
853                    )
854                ]
855            )
856        );
857    }
858
859    #[test]
860    fn test_field_access() {
861        let input = "foo.bar.baz";
862        let mut parser = Parser::new(input);
863        let tree = parser.parse().unwrap();
864        assert_eq!(
865            tree,
866            TokenTree::Cons(
867                Op::Field,
868                vec![
869                    TokenTree::Cons(
870                        Op::Field,
871                        vec![
872                            TokenTree::Atom(Atom::Ident("foo")),
873                            TokenTree::Atom(Atom::Ident("bar")),
874                        ]
875                    ),
876                    TokenTree::Atom(Atom::Ident("baz")),
877                ]
878            )
879        );
880
881        let input = "foo.check[0].baz";
882        let mut parser = Parser::new(input);
883        let tree = parser.parse().unwrap();
884        assert_eq!(
885            tree,
886            TokenTree::Cons(
887                Op::Field,
888                vec![
889                    TokenTree::Cons(
890                        Op::Index,
891                        vec![
892                            TokenTree::Cons(
893                                Op::Field,
894                                vec![
895                                    TokenTree::Atom(Atom::Ident("foo")),
896                                    TokenTree::Atom(Atom::Ident("check")),
897                                ],
898                            ),
899                            TokenTree::Atom(Atom::Int(0)),
900                        ],
901                    ),
902                    TokenTree::Atom(Atom::Ident("baz")),
903                ]
904            )
905        );
906    }
907
908    #[test]
909    fn test_function_call() {
910        let input = "foo(bar, baz)";
911        let mut parser = Parser::new(input);
912        let tree = parser.parse().unwrap();
913        assert_eq!(
914            tree,
915            TokenTree::Call {
916                func: Box::new(TokenTree::Atom(Atom::Ident("foo"))),
917                args: vec![
918                    TokenTree::Atom(Atom::Ident("bar")),
919                    TokenTree::Atom(Atom::Ident("baz")),
920                ],
921                is_method: false,
922            }
923        );
924
925        let input = "foo([])";
926        let mut parser = Parser::new(input);
927        let tree = parser.parse().unwrap();
928        assert_eq!(
929            tree,
930            TokenTree::Call {
931                func: Box::new(TokenTree::Atom(Atom::Ident("foo"))),
932                args: vec![TokenTree::Cons(Op::List, vec![])],
933                is_method: false,
934            }
935        );
936
937        let input = "foo({})";
938        let mut parser = Parser::new(input);
939        let tree = parser.parse().unwrap();
940        assert_eq!(
941            tree,
942            TokenTree::Call {
943                func: Box::new(TokenTree::Atom(Atom::Ident("foo"))),
944                args: vec![TokenTree::Cons(Op::Map, vec![])],
945                is_method: false,
946            }
947        );
948    }
949
950    #[test]
951    fn test_method_call() {
952        let input = "foo.bar(baz)";
953        let mut parser = Parser::new(input);
954        let tree = parser.parse().unwrap();
955        assert_eq!(
956            tree,
957            TokenTree::Call {
958                func: Box::new(TokenTree::Atom(Atom::Ident("bar"))),
959                args: vec![
960                    TokenTree::Atom(Atom::Ident("foo")),
961                    TokenTree::Atom(Atom::Ident("baz")),
962                ],
963                is_method: true,
964            }
965        );
966    }
967
968    #[test]
969    fn test_method_call_chain() {
970        let input = "foo.bar().baz()";
971        let mut parser = Parser::new(input);
972        let tree = parser.parse().unwrap();
973        let want = TokenTree::Call {
974            func: Box::new(TokenTree::Atom(Atom::Ident("baz"))),
975            args: vec![TokenTree::Call {
976                func: Box::new(TokenTree::Atom(Atom::Ident("bar"))),
977                args: vec![TokenTree::Atom(Atom::Ident("foo"))],
978                is_method: true,
979            }],
980            is_method: true,
981        };
982        assert_eq!(tree, want);
983    }
984
985    #[test]
986    fn test_long_method_chain() {
987        let input = "foo.bar().baz().qux()";
988        let mut parser = Parser::new(input);
989        let tree = parser.parse().unwrap();
990        let want = TokenTree::Call {
991            func: Box::new(TokenTree::Atom(Atom::Ident("qux"))),
992            args: vec![TokenTree::Call {
993                func: Box::new(TokenTree::Atom(Atom::Ident("baz"))),
994                args: vec![TokenTree::Call {
995                    func: Box::new(TokenTree::Atom(Atom::Ident("bar"))),
996                    args: vec![TokenTree::Atom(Atom::Ident("foo"))],
997                    is_method: true,
998                }],
999                is_method: true,
1000            }],
1001            is_method: true,
1002        };
1003        assert_eq!(tree, want);
1004    }
1005
1006    #[test]
1007    fn test_nested_method_call() {
1008        let input = "foo.all(test, test.size() > 4)";
1009        let mut parser = Parser::new(input);
1010        let tree = parser.parse().unwrap();
1011        let want = TokenTree::Call {
1012            func: Box::new(TokenTree::Atom(Atom::Ident("all"))),
1013            args: vec![
1014                TokenTree::Atom(Atom::Ident("foo")),
1015                TokenTree::Atom(Atom::Ident("test")),
1016                TokenTree::Cons(
1017                    Op::Greater,
1018                    vec![
1019                        TokenTree::Call {
1020                            func: Box::new(TokenTree::Atom(Atom::Ident(
1021                                "size",
1022                            ))),
1023                            args: vec![TokenTree::Atom(Atom::Ident("test"))],
1024                            is_method: true,
1025                        },
1026                        TokenTree::Atom(Atom::Int(4)),
1027                    ],
1028                ),
1029            ],
1030            is_method: true,
1031        };
1032        assert_eq!(tree, want, "expected {want:?}, got {tree:?}");
1033    }
1034
1035    #[test]
1036    fn test_list_definition() {
1037        let input = "[1, 2, 3]";
1038        let mut parser = Parser::new(input);
1039        let tree = parser.parse();
1040        assert!(tree.is_ok(), "{:?}", tree);
1041        let tree = tree.unwrap();
1042        assert_eq!(
1043            tree,
1044            TokenTree::Cons(
1045                Op::List,
1046                vec![
1047                    TokenTree::Atom(Atom::Int(1)),
1048                    TokenTree::Atom(Atom::Int(2)),
1049                    TokenTree::Atom(Atom::Int(3)),
1050                ]
1051            )
1052        );
1053
1054        let input = "[]";
1055        let mut parser = Parser::new(input);
1056        let tree = parser.parse().unwrap();
1057        assert_eq!(tree, TokenTree::Cons(Op::List, vec![]));
1058    }
1059
1060    #[test]
1061    fn test_map_definition() {
1062        let input = "{foo: 1, bar: 2}";
1063        let mut parser = Parser::new(input);
1064        let tree = parser.parse();
1065        assert!(tree.is_ok(), "{:?}", tree);
1066        let tree = tree.unwrap();
1067        assert_eq!(
1068            tree,
1069            TokenTree::Cons(
1070                Op::Map,
1071                vec![
1072                    TokenTree::Atom(Atom::Ident("foo")),
1073                    TokenTree::Atom(Atom::Int(1)),
1074                    TokenTree::Atom(Atom::Ident("bar")),
1075                    TokenTree::Atom(Atom::Int(2)),
1076                ]
1077            )
1078        );
1079
1080        let input = "{}";
1081        let mut parser = Parser::new(input);
1082        let tree = parser.parse().unwrap();
1083        assert_eq!(tree, TokenTree::Cons(Op::Map, vec![]));
1084    }
1085
1086    #[test]
1087    fn test_grouping() {
1088        let input = "(1 + 2) * 3 % 4";
1089        let mut parser = Parser::new(input);
1090        let tree = parser.parse().unwrap();
1091        assert_eq!(
1092            tree,
1093            TokenTree::Cons(
1094                Op::Mod,
1095                vec![
1096                    TokenTree::Cons(
1097                        Op::Multiply,
1098                        vec![
1099                            TokenTree::Cons(
1100                                Op::Group,
1101                                vec![TokenTree::Cons(
1102                                    Op::Plus,
1103                                    vec![
1104                                        TokenTree::Atom(Atom::Int(1)),
1105                                        TokenTree::Atom(Atom::Int(2)),
1106                                    ]
1107                                ),]
1108                            ),
1109                            TokenTree::Atom(Atom::Int(3)),
1110                        ]
1111                    ),
1112                    TokenTree::Atom(Atom::Int(4)),
1113                ]
1114            )
1115        );
1116    }
1117
1118    #[test]
1119    fn test_unary_minus() {
1120        let input = "-1";
1121        let mut parser = Parser::new(input);
1122        let tree = parser.parse().unwrap();
1123        assert_eq!(
1124            tree,
1125            TokenTree::Cons(Op::Minus, vec![TokenTree::Atom(Atom::Int(1))])
1126        );
1127    }
1128
1129    #[test]
1130    fn test_unary_not() {
1131        let input = "!true";
1132        let mut parser = Parser::new(input);
1133        let tree = parser.parse().unwrap();
1134        assert_eq!(
1135            tree,
1136            TokenTree::Cons(Op::Not, vec![TokenTree::Atom(Atom::Bool(true))])
1137        );
1138    }
1139
1140    #[test]
1141    fn test_relations() {
1142        let input = "1 < 2 && 3 >= 4 || 5 == 6 && 5 in 6";
1143        let mut parser = Parser::new(input);
1144        let tree = parser.parse().unwrap();
1145        assert_eq!(
1146            tree,
1147            TokenTree::Cons(
1148                Op::Or,
1149                vec![
1150                    TokenTree::Cons(
1151                        Op::And,
1152                        vec![
1153                            TokenTree::Cons(
1154                                Op::Less,
1155                                vec![
1156                                    TokenTree::Atom(Atom::Int(1)),
1157                                    TokenTree::Atom(Atom::Int(2)),
1158                                ]
1159                            ),
1160                            TokenTree::Cons(
1161                                Op::GreaterEqual,
1162                                vec![
1163                                    TokenTree::Atom(Atom::Int(3)),
1164                                    TokenTree::Atom(Atom::Int(4)),
1165                                ]
1166                            ),
1167                        ]
1168                    ),
1169                    TokenTree::Cons(
1170                        Op::And,
1171                        vec![
1172                            TokenTree::Cons(
1173                                Op::EqualEqual,
1174                                vec![
1175                                    TokenTree::Atom(Atom::Int(5)),
1176                                    TokenTree::Atom(Atom::Int(6)),
1177                                ]
1178                            ),
1179                            TokenTree::Cons(
1180                                Op::In,
1181                                vec![
1182                                    TokenTree::Atom(Atom::Int(5)),
1183                                    TokenTree::Atom(Atom::Int(6)),
1184                                ]
1185                            ),
1186                        ]
1187                    ),
1188                ]
1189            )
1190        );
1191    }
1192
1193    #[test]
1194    fn test_singuler_expression() {
1195        let tt = vec![
1196            ("identifier", TokenTree::Atom(Atom::Ident("identifier"))),
1197            ("123", TokenTree::Atom(Atom::Int(123))),
1198            ("123u", TokenTree::Atom(Atom::Uint(123))),
1199            ("123.456", TokenTree::Atom(Atom::Double(123.456))),
1200            ("true", TokenTree::Atom(Atom::Bool(true))),
1201            ("false", TokenTree::Atom(Atom::Bool(false))),
1202            (
1203                "\"string\"",
1204                TokenTree::Atom(Atom::String(Cow::Borrowed("string"))),
1205            ),
1206            ("null", TokenTree::Atom(Atom::Null)),
1207        ]
1208        .into_iter();
1209
1210        for (input, expected) in tt {
1211            let mut parser = Parser::new(input);
1212            let tree = parser.parse();
1213            assert!(tree.is_ok(), "input={:?}, out={:?}", input, tree);
1214            let tree = tree.unwrap();
1215            assert_eq!(tree, expected);
1216        }
1217    }
1218
1219    #[test]
1220    fn test_indexing() {
1221        let input = "foo[1]";
1222        let mut parser = Parser::new(input);
1223        let tree = parser.parse().unwrap();
1224        assert_eq!(
1225            tree,
1226            TokenTree::Cons(
1227                Op::Index,
1228                vec![
1229                    TokenTree::Atom(Atom::Ident("foo")),
1230                    TokenTree::Atom(Atom::Int(1)),
1231                ]
1232            )
1233        );
1234
1235        let input = "foo[1][2]";
1236        let mut parser = Parser::new(input);
1237        let tree = parser.parse().unwrap();
1238        assert_eq!(
1239            tree,
1240            TokenTree::Cons(
1241                Op::Index,
1242                vec![
1243                    TokenTree::Cons(
1244                        Op::Index,
1245                        vec![
1246                            TokenTree::Atom(Atom::Ident("foo")),
1247                            TokenTree::Atom(Atom::Int(1)),
1248                        ]
1249                    ),
1250                    TokenTree::Atom(Atom::Int(2)),
1251                ]
1252            )
1253        );
1254    }
1255
1256    #[test]
1257    fn test_ternary_if() {
1258        let input = "true ? 1 : 2";
1259        let mut parser = Parser::new(input);
1260        let tree = parser.parse().unwrap();
1261        assert_eq!(
1262            tree,
1263            TokenTree::Cons(
1264                Op::IfTernary,
1265                vec![
1266                    TokenTree::Atom(Atom::Bool(true)),
1267                    TokenTree::Atom(Atom::Int(1)),
1268                    TokenTree::Atom(Atom::Int(2)),
1269                ]
1270            )
1271        );
1272
1273        let input = "true ? 1 : false ? 2 : 3";
1274        let mut parser = Parser::new(input);
1275        let tree = parser.parse().unwrap();
1276        assert_eq!(
1277            tree,
1278            TokenTree::Cons(
1279                Op::IfTernary,
1280                vec![
1281                    TokenTree::Atom(Atom::Bool(true)),
1282                    TokenTree::Atom(Atom::Int(1)),
1283                    TokenTree::Cons(
1284                        Op::IfTernary,
1285                        vec![
1286                            TokenTree::Atom(Atom::Bool(false)),
1287                            TokenTree::Atom(Atom::Int(2)),
1288                            TokenTree::Atom(Atom::Int(3)),
1289                        ]
1290                    ),
1291                ]
1292            )
1293        );
1294    }
1295
1296    #[test]
1297    fn test_method_relation() {
1298        let input = "foo.bar() < 4";
1299        let mut parser = Parser::new(input);
1300        let tree = parser.parse().unwrap();
1301        assert_eq!(
1302            tree,
1303            TokenTree::Cons(
1304                Op::Less,
1305                vec![
1306                    TokenTree::Call {
1307                        func: Box::new(TokenTree::Atom(Atom::Ident("bar"))),
1308                        args: vec![TokenTree::Atom(Atom::Ident("foo"))],
1309                        is_method: true,
1310                    },
1311                    TokenTree::Atom(Atom::Int(4)),
1312                ]
1313            )
1314        );
1315    }
1316
1317    #[test]
1318    fn test_inline_function_call() {
1319        let input = "1 + size(2u)";
1320        let mut parser = Parser::new(input);
1321        let tree = parser.parse().unwrap();
1322        assert_eq!(
1323            tree,
1324            TokenTree::Cons(
1325                Op::Plus,
1326                vec![
1327                    TokenTree::Atom(Atom::Int(1)),
1328                    TokenTree::Call {
1329                        func: Box::new(TokenTree::Atom(Atom::Ident("size"))),
1330                        args: vec![TokenTree::Atom(Atom::Uint(2))],
1331                        is_method: false,
1332                    },
1333                ]
1334            )
1335        );
1336    }
1337
1338    #[test]
1339    fn test_inline_dyn_call() {
1340        let input = "1 + dyn(2u)";
1341        let mut parser = Parser::new(input);
1342        let tree = parser.parse().unwrap();
1343        assert_eq!(
1344            tree,
1345            TokenTree::Cons(
1346                Op::Plus,
1347                vec![
1348                    TokenTree::Atom(Atom::Int(1)),
1349                    TokenTree::Cons(
1350                        Op::Dyn,
1351                        vec![TokenTree::Atom(Atom::Uint(2))],
1352                    ),
1353                ]
1354            )
1355        );
1356    }
1357
1358    #[test]
1359    fn test_nested_list_with_map() {
1360        let input = "[{foo: 1}, {bar: 2}]";
1361        let mut parser = Parser::new(input);
1362        let tree = parser.parse().unwrap();
1363        assert_eq!(
1364            tree,
1365            TokenTree::Cons(
1366                Op::List,
1367                vec![
1368                    TokenTree::Cons(
1369                        Op::Map,
1370                        vec![
1371                            TokenTree::Atom(Atom::Ident("foo")),
1372                            TokenTree::Atom(Atom::Int(1)),
1373                        ]
1374                    ),
1375                    TokenTree::Cons(
1376                        Op::Map,
1377                        vec![
1378                            TokenTree::Atom(Atom::Ident("bar")),
1379                            TokenTree::Atom(Atom::Int(2)),
1380                        ]
1381                    ),
1382                ]
1383            )
1384        );
1385    }
1386
1387    #[test]
1388    fn test_method_call_with_indexing() {
1389        let input = "foo.bar(x, t[x] > 10)";
1390        let mut parser = Parser::new(input);
1391        let tree = parser.parse().unwrap();
1392
1393        let want = TokenTree::Call {
1394            func: Box::new(TokenTree::Atom(Atom::Ident("bar"))),
1395            args: vec![
1396                TokenTree::Atom(Atom::Ident("foo")),
1397                TokenTree::Atom(Atom::Ident("x")),
1398                TokenTree::Cons(
1399                    Op::Greater,
1400                    vec![
1401                        TokenTree::Cons(
1402                            Op::Index,
1403                            vec![
1404                                TokenTree::Atom(Atom::Ident("t")),
1405                                TokenTree::Atom(Atom::Ident("x")),
1406                            ],
1407                        ),
1408                        TokenTree::Atom(Atom::Int(10)),
1409                    ],
1410                ),
1411            ],
1412            is_method: true,
1413        };
1414
1415        assert_eq!(tree, want);
1416    }
1417
1418    #[test]
1419    fn test_nested_fields() {
1420        let input = "foo.bar.baz";
1421        let mut parser = Parser::new(input);
1422        let tree = parser.parse().unwrap();
1423
1424        let want = TokenTree::Cons(
1425            Op::Field,
1426            vec![
1427                TokenTree::Cons(
1428                    Op::Field,
1429                    vec![
1430                        TokenTree::Atom(Atom::Ident("foo")),
1431                        TokenTree::Atom(Atom::Ident("bar")),
1432                    ],
1433                ),
1434                TokenTree::Atom(Atom::Ident("baz")),
1435            ],
1436        );
1437
1438        assert_eq!(tree, want);
1439    }
1440
1441    #[test]
1442    fn test_nested_fields_method_call() {
1443        let input = "foo.bar.foo.baz()";
1444        let mut parser = Parser::new(input);
1445        let tree = parser.parse().unwrap();
1446
1447        let want = TokenTree::Call {
1448            func: Box::new(TokenTree::Atom(Atom::Ident("baz"))),
1449            args: vec![TokenTree::Cons(
1450                Op::Field,
1451                vec![
1452                    TokenTree::Cons(
1453                        Op::Field,
1454                        vec![
1455                            TokenTree::Atom(Atom::Ident("foo")),
1456                            TokenTree::Atom(Atom::Ident("bar")),
1457                        ],
1458                    ),
1459                    TokenTree::Atom(Atom::Ident("foo")),
1460                ],
1461            )],
1462            is_method: true,
1463        };
1464
1465        assert_eq!(tree, want);
1466    }
1467
1468    #[test]
1469    fn test_nested_method_call_with_indexing() {
1470        let input = "foo.bar.filter(x, x > 10)[0].id";
1471        let mut parser = Parser::new(input);
1472        let tree = parser.parse().unwrap();
1473
1474        let want = TokenTree::Cons(
1475            Op::Field,
1476            vec![
1477                TokenTree::Cons(
1478                    Op::Index,
1479                    vec![
1480                        TokenTree::Call {
1481                            func: Box::new(TokenTree::Atom(Atom::Ident(
1482                                "filter",
1483                            ))),
1484                            args: vec![
1485                                TokenTree::Cons(
1486                                    Op::Field,
1487                                    vec![
1488                                        TokenTree::Atom(Atom::Ident("foo")),
1489                                        TokenTree::Atom(Atom::Ident("bar")),
1490                                    ],
1491                                ),
1492                                TokenTree::Atom(Atom::Ident("x")),
1493                                TokenTree::Cons(
1494                                    Op::Greater,
1495                                    vec![
1496                                        TokenTree::Atom(Atom::Ident("x")),
1497                                        TokenTree::Atom(Atom::Int(10)),
1498                                    ],
1499                                ),
1500                            ],
1501                            is_method: true,
1502                        },
1503                        TokenTree::Atom(Atom::Int(0)),
1504                    ],
1505                ),
1506                TokenTree::Atom(Atom::Ident("id")),
1507            ],
1508        );
1509
1510        assert_eq!(tree, want);
1511    }
1512
1513    #[test]
1514    fn test_parser_propagates_lexer_error_span() {
1515        let input = "&";
1516        let mut parser = Parser::new(input);
1517        let err = parser.parse().expect_err("expected lexer error");
1518        let report = Report::new(err.clone());
1519        assert_span_matches(&err, 0, "&", &report);
1520        assert!(
1521            err.message().contains("Unexpected character"),
1522            "unexpected message: {}; {report:?}",
1523            err.message()
1524        );
1525    }
1526
1527    #[test]
1528    fn test_parser_propagates_eof_span() {
1529        let input = "(";
1530        let mut parser = Parser::new(input);
1531        let err = parser.parse().expect_err("expected missing closing paren");
1532        let span = err.span();
1533        let offset: usize = span.offset();
1534        assert_eq!(
1535            offset,
1536            input.len(),
1537            "eof span should point to end of input"
1538        );
1539        assert_eq!(span.len(), 0, "eof span should have zero length");
1540    }
1541
1542    #[test]
1543    fn test_parser_propagates_unexpected_token_span() {
1544        let input = "1 + (1abc";
1545        let mut parser = Parser::new(input);
1546        let err = parser
1547            .parse()
1548            .expect_err("expected missing closing paren error");
1549        let report = Report::new(err.clone());
1550        assert_span_matches(&err, "1 + (1".len(), "abc", &report);
1551        assert!(
1552            err.message().contains("Unexpected token"),
1553            "unexpected message: {}; {report:?}",
1554            err.message()
1555        );
1556    }
1557}
cellang/parser.rs

cellang/
parser.rs
