1use crate::lexer::{lex, LexerError, Token};
2use crate::lexer::Token::*;
3
4#[derive(Debug, Clone, PartialEq)]
5pub enum Expr {
6 Literal {
7 token: Token,
8 },
9 Identifier {
10 token: Token,
11 },
12 Array {
13 elements: Vec<Expr>,
14 },
15 ArrowFunction {
16 params: Vec<Expr>,
17 body: Box<Expr>,
18 },
19 Binary {
20 left: Box<Expr>,
21 operator: Token,
22 right: Box<Expr>,
23 },
24 Call {
25 callee: Box<Expr>,
26 arguments: Vec<Expr>,
27 },
28 Comma {
29 expressions: Vec<Expr>,
30 },
31 Conditional {
32 test: Box<Expr>,
33 consequent: Box<Expr>,
34 alternate: Box<Expr>,
35 },
36 Object {
37 properties: Vec<PropertyExpr>,
38 },
39 Spread {
40 expr: Box<Expr>,
41 },
42 Member {
43 computed: bool,
44 object: Box<Expr>,
45 property: Box<Expr>,
46 optional: bool,
47 },
48 New {
49 callee: Box<Expr>,
50 arguments: Vec<Expr>,
51 },
52 TemplateLiteral {
53 quasis: Vec<TemplateString>,
54 expressions: Vec<Expr>,
55 },
56 TaggedTemplate {
57 tag: Box<Expr>,
58 quasi: Box<Expr>,
59 },
60 Unary {
61 operator: Token,
62 argument: Box<Expr>,
63 prefix: bool,
64 },
65}
66
67#[derive(Debug, Clone, PartialEq)]
68pub struct TemplateString {
69 token: Token,
70 tail: bool,
71}
72
73#[derive(Debug, Clone, PartialEq)]
74pub enum PropertyExpr {
75 Property {
76 computed: bool,
77 key: Expr,
78 shorthand: bool,
79 value: Option<Expr>,
80 },
81 Spread {
82 expr: Expr,
83 },
84}
85
86#[derive(Debug)]
87pub enum ParserError {
88 UnexpectedToken(Token),
89 ExpectedToken(Token),
90 LexerError(LexerError),
91}
92
93impl From<LexerError> for ParserError {
94 fn from(err: LexerError) -> Self {
95 ParserError::LexerError(err)
96 }
97}
98
99macro_rules! cur {
100 ($tokens:expr, $pos:expr) => {
101 $tokens.get(*$pos).unwrap()
102 };
103}
104
105macro_rules! la {
106 ($tokens:expr, $pos:expr) => {
107 $tokens.get(*$pos + 1).unwrap()
108 };
109}
110
111macro_rules! next {
112 ($tokens:expr, $pos:expr) => {{
113 let token = cur!($tokens, $pos);
114 *$pos += 1;
115 token
116 }};
117}
118
119macro_rules! check {
120 ($tokens:expr, $pos:expr, $token:expr) => {
121 cur!($tokens, $pos) == &$token
122 };
123}
124
125macro_rules! consume {
126 ($tokens:expr, $pos:expr, $expected:expr) => {{
127 let token = next!($tokens, $pos);
128 if token != &$expected {
129 return Err(ParserError::ExpectedToken($expected));
130 }
131 token
132 }};
133}
134
135macro_rules! match_token {
136 ($tokens:expr, $pos:expr, $expected:expr) => {
137 if check!($tokens, $pos, $expected) {
138 next!($tokens, $pos);
139 true
140 } else {
141 false
142 }
143 };
144}
145
146pub fn parse(expression: &str) -> Result<Expr, ParserError> {
148 let tokens = lex(expression)?;
149 let mut pos: usize = 0;
150 let expr = parse_expr(&tokens, &mut pos, 0)?;
151 let token = cur!(tokens, &pos);
152
153 if token != &Eof {
154 return Err(ParserError::UnexpectedToken(token.clone()));
155 }
156
157 Ok(expr)
158}
159
160fn parse_expr(tokens: &[Token], pos: &mut usize, prec: i32) -> Result<Expr, ParserError> {
161 let mut token = next!(tokens, pos);
162 let mut expr = parse_prefix(tokens, pos, token)?;
163
164 while prec < precedence(cur!(tokens, pos)) {
165 token = next!(tokens, pos);
166 expr = parse_infix(tokens, pos, token, expr)?;
167 }
168
169 Ok(expr)
170}
171
172fn parse_prefix(tokens: &[Token], pos: &mut usize, token: &Token) -> Result<Expr, ParserError> {
173 match token {
174 Identifier(_) => Ok(Expr::Identifier {
175 token: token.clone(),
176 }),
177
178 True | False | Null | Undefined | This | Super | Number(_) | String(_) | Regex(_, _) => {
179 Ok(Expr::Literal {
180 token: token.clone(),
181 })
182 }
183
184 LParen => {
185 if cur!(tokens, pos) == &RParen {
186 next!(tokens, pos);
187 return Ok(Expr::Comma {
188 expressions: Vec::new(),
189 });
190 }
191
192 let expr = parse_expr(tokens, pos, 0)?;
193 consume!(tokens, pos, RParen);
194 Ok(expr)
195 }
196
197 Backtick => {
198 let mut quasis: Vec<TemplateString> = Vec::new();
199 let mut expressions: Vec<Expr> = Vec::new();
200
201 while !check!(tokens, pos, Backtick) {
202 if match_token!(tokens, pos, DollarBrace) {
203 expressions.push(parse_expr(tokens, pos, 1)?);
204 consume!(tokens, pos, RBrace);
205 } else {
206 let token = next!(tokens, pos);
207 match token {
208 String(_) => quasis.push(TemplateString {
209 token: (*token).clone(),
210 tail: false,
211 }),
212 _ => return Err(ParserError::ExpectedToken(String("".to_string()))),
213 }
214 }
215 }
216
217 quasis.last_mut().unwrap().tail = true;
218
219 consume!(tokens, pos, Backtick);
220
221 Ok(Expr::TemplateLiteral {
222 quasis,
223 expressions,
224 })
225 }
226
227 LBrace => {
228 let mut properties: Vec<PropertyExpr> = Vec::new();
229
230 while !check!(tokens, pos, RBrace) {
231 let expr = parse_expr(tokens, pos, 1)?;
232
233 if check!(tokens, pos, Colon) {
234 let key = expr;
235 next!(tokens, pos);
236 let value = parse_expr(tokens, pos, 1)?;
237
238 properties.push(PropertyExpr::Property {
239 computed: matches!(&key, Expr::Array { .. }),
240 key,
241 shorthand: false,
242 value: Some(value),
243 });
244 } else {
245 match expr {
246 Expr::Identifier { .. } => {
247 properties.push(PropertyExpr::Property {
248 computed: false,
249 key: expr,
250 shorthand: true,
251 value: None,
252 });
253 }
254 Expr::Spread { expr } => {
255 properties.push(PropertyExpr::Spread { expr: *expr });
256 }
257 _ => {
258 return Err(ParserError::ExpectedToken(Colon));
259 }
260 }
261 }
262
263 if check!(tokens, pos, Comma) {
264 next!(tokens, pos);
265 }
266 }
267
268 consume!(tokens, pos, RBrace);
269
270 Ok(Expr::Object { properties })
271 }
272
273 LBracket => {
274 let mut elements: Vec<Expr> = Vec::new();
275
276 while !check!(tokens, pos, RBracket) {
277 elements.push(parse_expr(tokens, pos, 1)?);
278
279 if check!(tokens, pos, Comma) {
280 next!(tokens, pos);
281 }
282 }
283
284 consume!(tokens, pos, RBracket);
285
286 Ok(Expr::Array { elements })
287 }
288
289 New => match parse_expr(tokens, pos, 16)? {
290 Expr::Call { callee, arguments } => Ok(Expr::New { callee, arguments }),
291 _ => Err(ParserError::ExpectedToken(LParen)),
292 },
293
294 DotDotDot => Ok(Expr::Spread {
295 expr: parse_expr(tokens, pos, 1)?.into(),
296 }),
297
298 PlusPlus | MinusMinus | Tilde | Not | Minus | Await | Plus | Typeof | Delete | Void => {
299 Ok(Expr::Unary {
300 operator: token.clone(),
301 argument: parse_expr(tokens, pos, 14)?.into(),
302 prefix: true,
303 })
304 }
305
306 _ => Err(ParserError::UnexpectedToken(token.clone())),
307 }
308}
309
310fn parse_infix(
311 tokens: &[Token],
312 pos: &mut usize,
313 token: &Token,
314 expr: Expr,
315) -> Result<Expr, ParserError> {
316 match token {
317 LParen => {
318 let mut arguments: Vec<Expr> = Vec::new();
319
320 while !check!(tokens, pos, RParen) {
321 arguments.push(parse_expr(tokens, pos, 1)?);
322
323 if check!(tokens, pos, Comma) {
324 next!(tokens, pos);
325 }
326 }
327
328 consume!(tokens, pos, RParen);
329
330 Ok(Expr::Call {
331 callee: expr.into(),
332 arguments,
333 })
334 }
335
336 Dot => Ok(Expr::Member {
337 computed: false,
338 object: expr.into(),
339 property: parse_expr(tokens, pos, 17)?.into(),
340 optional: false,
341 }),
342
343 Backtick => Ok(Expr::TaggedTemplate {
344 tag: expr.into(),
345 quasi: parse_prefix(tokens, pos, token)?.into(),
346 }),
347
348 Comma => {
349 if check!(tokens, pos, RParen) && la!(tokens, pos) == &EqGt {
350 return Ok(expr);
351 }
352
353 let mut expressions = vec![expr];
354
355 loop {
356 expressions.push(parse_expr(tokens, pos, 1)?);
357
358 if !match_token!(tokens, pos, Comma) {
359 break;
360 }
361 }
362
363 Ok(Expr::Comma { expressions })
364 }
365
366 Question => {
367 let consequent = parse_expr(tokens, pos, 1)?;
368 consume!(tokens, pos, Colon);
369 let alternate = parse_expr(tokens, pos, 1)?;
370
371 Ok(Expr::Conditional {
372 test: expr.into(),
373 consequent: consequent.into(),
374 alternate: alternate.into(),
375 })
376 }
377
378 EqGt => Ok(Expr::ArrowFunction {
379 params: match expr {
380 Expr::Comma { expressions } => expressions,
381 _ => vec![expr],
382 },
383 body: parse_expr(tokens, pos, 1)?.into(),
384 }),
385
386 StarStar => Ok(Expr::Binary {
387 left: expr.into(),
388 operator: token.clone(),
389 right: parse_expr(tokens, pos, 12)?.into(),
390 }),
391
392 PlusPlus | MinusMinus => Ok(Expr::Unary {
393 operator: token.clone(),
394 argument: expr.into(),
395 prefix: false,
396 }),
397
398 Plus | Minus | Star | Slash | Percent | EqEq | EqEqEq | NotEq | NotEqEq | Lt | LtEq
399 | Gt | GtEq | In | InstanceOf | LtLt | GtGt | GtGtGt | And | AndAnd | Pipe | PipePipe
400 | Caret | QuestionQuestion => Ok(Expr::Binary {
401 left: expr.into(),
402 operator: token.clone(),
403 right: parse_expr(tokens, pos, precedence(token))?.into(),
404 }),
405
406 QuestionDot => Ok(Expr::Member {
407 computed: false,
408 object: expr.into(),
409 property: parse_expr(tokens, pos, 17)?.into(),
410 optional: true,
411 }),
412
413 LBracket => {
414 let property = parse_expr(tokens, pos, 0)?;
415
416 consume!(tokens, pos, RBracket);
417
418 Ok(Expr::Member {
419 computed: true,
420 object: expr.into(),
421 property: property.into(),
422 optional: false,
423 })
424 }
425
426 _ => Err(ParserError::UnexpectedToken(token.clone())),
427 }
428}
429
430fn precedence(token: &Token) -> i32 {
431 match token {
432 Comma => 1,
433 DotDotDot | EqGt | Question => 2,
434 PipePipe | QuestionQuestion => 3,
435 AndAnd => 4,
436 Pipe => 5,
437 Caret => 6,
438 And => 7,
439 EqEq | EqEqEq | NotEq | NotEqEq => 8,
440 Lt | LtEq | Gt | GtEq | In | InstanceOf => 9,
441 LtLt | GtGt | GtGtGt => 10,
442 Plus | Minus => 11,
443 Star | Slash | Percent => 12,
444 StarStar => 13,
445 PlusPlus | MinusMinus => 15,
446 Dot | QuestionDot | LBracket | Backtick | LParen => 17,
447 _ => -1,
448 }
449}
450
451#[cfg(test)]
452mod tests {
453 use insta::assert_debug_snapshot;
454
455 use super::*;
456
457 macro_rules! parse {
458 ($($expr:expr),*) => {
459 assert_debug_snapshot!(
460 vec![$(parse($expr).unwrap()),*]
461 )
462 };
463 }
464
465 macro_rules! precedence {
466 ($expr:expr, $expected:expr) => {
467 assert_eq!(parse($expr).unwrap(), parse($expected).unwrap())
468 };
469 }
470
471 #[test]
472 fn usage() {
473 let result = parse("(s) => `hello from ${s}!`");
474
475 match result {
476 Ok(expr) => {
477 println!("{:#?}", expr);
478 }
479 Err(err) => {
480 println!("{:#?}", err);
481 }
482 }
483 }
484
485 #[test]
486 fn primaries() {
487 parse!(
488 "false",
489 "true",
490 "null",
491 "undefined",
492 "this",
493 "super",
494 "123",
495 "'abc'",
496 "/foo/",
497 "(123)",
498 "[123]",
499 "[123,]",
500 "[123, 456]",
501 "[]",
502 "[_, al]",
503 "{}",
504 "{foo}",
505 "{foo, bar}",
506 "{foo: 123}",
507 "{1: \"foo\"}",
508 "{\"foo:bar\": 42}",
509 "{...foo}",
510 "{foo: {bar} }",
511 "{ album: a.title, artist: ar.name, track: t.name }",
512 "``",
513 "`abc`",
514 "`${foo}`",
515 "`$`",
516 "`\\${`",
517 "`${ `a${b}c` }`",
518 "tag`foo`",
519 "sql`select * from table`",
520 "`${{ $id }}`",
521 "`${ { id: { } } }`",
522 "sql``.f",
523 "{ a: `${a.title}!` }"
524 );
525 }
526
527 #[test]
528 fn computed_key() {
529 parse!("{[abc]: 123}");
530 }
531
532 #[test]
533 fn members() {
534 parse!(
535 "a[10]",
536 "this.foo",
537 "foo.bar.baz",
538 "foo?.bar?.baz",
539 "foo[bar]",
540 "foo[bar]?.baz",
541 "foo[(a, b)]"
542 );
543 }
544
545 #[test]
546 fn comma() {
547 parse!("a, 12, b", "(a, 12)", "foo[a, b]");
548 }
549
550 #[test]
551 fn call() {
552 parse!(
553 "foo()",
554 "foo.bar()",
555 "foo.bar()[baz?.qux()]",
556 "foo(12, abc)"
557 );
558 }
559
560 #[test]
561 fn spread() {
562 parse!("...foo", "...foo.bar", "foo(...bar)", "foo(...bar, ...baz)");
563 }
564
565 #[test]
566 fn arrow() {
567 parse!(
568 "(foo,baz) => bar",
569 "foo => bar",
570 "() => a+b",
571 "(a, [b, _]) => a+b",
572 "() => (a, b) => a+b",
573 "([_, al]) => al.title",
574 "(al,) => al.title"
575 );
576 }
577
578 #[test]
579 fn ternary() {
580 parse!("foo ? bar : baz", "foo ? bar : baz ? qux : quux");
581 precedence!(
582 "foo ? bar : baz ? qux : quux",
583 "foo ? bar : (baz ? qux : quux)"
584 );
585 }
586
587 #[test]
588 fn nullish() {
589 parse!("foo ?? bar", "foo ?? bar ?? baz");
590 precedence!("foo ?? bar ?? baz", "(foo ?? bar) ?? baz");
591 }
592
593 #[test]
594 fn logical_or() {
595 parse!("123 || 456");
596 precedence!("123 || 456 || 789", "(123 || 456) || 789");
597 precedence!("123 || 456 && 789", "123 || (456 && 789)");
598 }
599
600 #[test]
601 fn logical_and() {
602 parse!("123 && 456", "foo || bar && baz");
603 precedence!("foo && bar && baz", "(foo && bar) && baz");
604 precedence!("foo && bar | baz", "foo && (bar | baz)");
605 }
606
607 #[test]
608 fn bitwise_or() {
609 parse!("123 | 456");
610 precedence!("123 | 456 | 789", "(123 | 456) | 789");
611 precedence!("123 | 456 ^ 789", "123 | (456 ^ 789)");
612 }
613
614 #[test]
615 fn bitwise_xor() {
616 parse!("123 ^ 456");
617 precedence!("123 ^ 456 ^ 789", "(123 ^ 456) ^ 789");
618 precedence!("123 ^ 456 & 789", "123 ^ (456 & 789)");
619 }
620
621 #[test]
622 fn bitwise_and() {
623 parse!("123 & 456");
624 precedence!("123 & 456 & 789", "(123 & 456) & 789");
625 precedence!("123 & 456 === 789", "123 & (456 === 789)");
626 }
627
628 #[test]
629 fn equality() {
630 parse!("123 == bar[12]", "123 === 456", "123 != 456", "123 !== 456");
631 precedence!("123 == 456 === 789", "(123 == 456) === 789");
632 precedence!("123 == 456 < 789", "123 == (456 < 789)");
633 }
634
635 #[test]
636 fn relational() {
637 parse!("123 < foo.bar", "123 > 456", "123 <= \"abc\"", "bar >= 456");
638 precedence!("123 < 456 > 789", "(123 < 456) > 789");
639 precedence!("123 < 456 << foo", "123 < (456 << foo)");
640 }
641
642 #[test]
643 fn bitwise_shift() {
644 parse!("123 << 456", "123 >> 456", "123 >>> 456");
645 }
646
647 #[test]
648 fn additive() {
649 parse!("123 + 456", "123 - 456 * 789");
650 precedence!("123 + 456 + 789", "(123 + 456) + 789");
651 precedence!("123 + 456 * 789", "123 + (456 * 789)");
652 }
653
654 #[test]
655 fn multiplicative() {
656 parse!("123 / 456 * 789", "123 % (456 / abc.def)");
657 precedence!("123 * 456 / 789", "(123 * 456) / 789");
658 precedence!("123 * 456 ** 789", "123 * (456 ** 789)");
659 }
660
661 #[test]
662 fn exponentiation() {
663 parse!("123 ** 456 ** 789");
664 precedence!("123 ** 456 ** 789", "123 ** (456 ** 789)");
665 precedence!("123 ** -456", "123 ** (-456)");
666 }
667
668 #[test]
669 fn prefix() {
670 parse!("+123", "+abc", "-abc", "!abc", "-(foo)", "~foo");
671 }
672
673 #[test]
674 fn prefix_increment() {
675 parse!(
676 "++foo",
677 "--foo",
678 "void 0",
679 "typeof foo",
680 "await obj[key]",
681 "delete obj[key]"
682 );
683 }
684
685 #[test]
686 fn postfix() {
687 parse!("foo++", "abc--");
688 }
689
690 #[test]
691 fn new() {
692 parse!("new Foo()", "new Foo(123)", "new x(y)");
693 }
694
695 #[test]
696 fn trailing_commas() {
697 parse!("foo(12,)", "{foo,}", "(foo,)=>123");
698 }
699
700 #[test]
701 fn parser_errors() {
702 assert!(matches!(parse("("), Err(ParserError::UnexpectedToken(Eof))));
703 assert!(matches!(
704 parse("new Foo"),
705 Err(ParserError::ExpectedToken(LParen))
706 ));
707 assert!(matches!(
708 parse("new Foo(12"),
709 Err(ParserError::UnexpectedToken(Eof))
710 ));
711 assert!(matches!(
712 parse("foo."),
713 Err(ParserError::UnexpectedToken(Eof))
714 ));
715 assert!(matches!(
716 parse("foo[12"),
717 Err(ParserError::ExpectedToken(RBracket))
718 ));
719 assert!(matches!(
720 parse("(12"),
721 Err(ParserError::ExpectedToken(RParen))
722 ));
723 assert!(matches!(
724 parse("12,"),
725 Err(ParserError::UnexpectedToken(Eof))
726 ));
727 assert!(matches!(
728 parse("(12,"),
729 Err(ParserError::UnexpectedToken(Eof))
730 ));
731 assert!(matches!(
732 parse("foo(12"),
733 Err(ParserError::UnexpectedToken(Eof))
734 ));
735 assert!(matches!(
736 parse("[,]"),
737 Err(ParserError::UnexpectedToken(Comma))
738 ));
739 assert!(matches!(
740 parse("foo(,)"),
741 Err(ParserError::UnexpectedToken(Comma))
742 ));
743 assert!(matches!(
744 parse("{12}"),
745 Err(ParserError::ExpectedToken(Colon))
746 ));
747 }
748}