fe_parser/grammar/
expressions.rs

1use crate::ast::{self, CallArg, Expr, GenericArg, Path};
2use crate::node::Node;
3use crate::{Label, ParseFailed, ParseResult, Parser, Token, TokenKind};
4
5use super::types::parse_generic_args;
6
7use if_chain::if_chain;
8
9// Expressions are parsed in Pratt's top-down operator precedence style.
10// See this article for a nice explanation:
11// <https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html>
12
13/// Parse an expression, starting with the next token.
14pub fn parse_expr(par: &mut Parser) -> ParseResult<Node<Expr>> {
15    parse_expr_with_min_bp(par, 0)
16}
17
18/// Parse an expression, stopping if/when we reach an operator that binds less
19/// tightly than given binding power.
20pub fn parse_expr_with_min_bp(par: &mut Parser, min_bp: u8) -> ParseResult<Node<Expr>> {
21    let mut expr_head = parse_expr_head(par)?;
22
23    while let Some(op) = par.peek() {
24        if let Some(lbp) = postfix_binding_power(op) {
25            if lbp < min_bp {
26                break;
27            }
28
29            expr_head = match op {
30                TokenKind::ParenOpen => {
31                    let args = parse_call_args(par)?;
32                    let span = expr_head.span + args.span;
33                    Node::new(
34                        Expr::Call {
35                            func: Box::new(expr_head),
36                            generic_args: None,
37                            args,
38                        },
39                        span,
40                    )
41                }
42                TokenKind::BracketOpen => {
43                    par.next()?;
44                    let index = parse_expr(par)?;
45                    let rbracket = par.expect(
46                        TokenKind::BracketClose,
47                        "failed to parse subscript expression",
48                    )?;
49                    let span = expr_head.span + rbracket.span;
50                    Node::new(
51                        Expr::Subscript {
52                            value: Box::new(expr_head),
53                            index: Box::new(index),
54                        },
55                        span,
56                    )
57                }
58                TokenKind::If => {
59                    par.next()?;
60                    let test = parse_expr(par)?;
61                    par.expect(
62                        TokenKind::Else,
63                        "failed to parse ternary `if-else` expression",
64                    )?;
65                    let else_val = parse_expr(par)?;
66                    let span = expr_head.span + else_val.span;
67                    Node::new(
68                        Expr::Ternary {
69                            if_expr: Box::new(expr_head),
70                            test: Box::new(test),
71                            else_expr: Box::new(else_val),
72                        },
73                        span,
74                    )
75                }
76                _ => unreachable!(), // patterns above must match those in `postfix_binding_power`
77            };
78            continue;
79        }
80
81        if matches!(op, TokenKind::Lt) {
82            let mut bt_par = par.as_bt_parser();
83            if_chain! {
84                if let Ok(generic_args) = parse_generic_args(&mut bt_par);
85                if matches!(bt_par.peek(), Some(TokenKind::ParenOpen));
86                if let Ok(args) = parse_call_args(&mut bt_par);
87                then {
88                    let span = expr_head.span + args.span;
89                    expr_head = Node::new(
90                        Expr::Call {
91                            func: Box::new(expr_head),
92                            generic_args: Some(generic_args),
93                            args,
94                        },
95                        span,
96                    );
97                    bt_par.accept();
98                    continue;
99                }
100            }
101        }
102
103        if let Some((lbp, rbp)) = infix_binding_power(op) {
104            if lbp < min_bp {
105                break;
106            }
107
108            let op_tok = par.next()?;
109            let rhs = parse_expr_with_min_bp(par, rbp)?;
110            expr_head = infix_op(par, expr_head, &op_tok, rhs)?;
111            continue;
112        }
113        break;
114    }
115
116    Ok(expr_head)
117}
118
119/// Parse call arguments
120pub fn parse_call_args(par: &mut Parser) -> ParseResult<Node<Vec<Node<CallArg>>>> {
121    use TokenKind::*;
122    let lparen = par.assert(ParenOpen);
123    let mut args = vec![];
124    let mut span = lparen.span;
125    loop {
126        if par.peek_or_err()? == ParenClose {
127            span += par.next()?.span;
128            break;
129        }
130
131        let arg = parse_expr(par)?;
132        match par.peek_or_err()? {
133            TokenKind::Eq => {
134                let eq = par.next()?;
135                if let Expr::Name(name) = arg.kind {
136                    par.fancy_error(
137                        "Syntax error in argument list",
138                        vec![Label::primary(eq.span, "unexpected `=`".to_string())],
139                        vec![
140                            "Argument labels should be followed by `:`.".to_string(),
141                            format!("Hint: try `{name}:`"),
142                            "If this is a variable assignment, it must be a standalone statement."
143                                .to_string(),
144                        ],
145                    );
146                    let value = parse_expr(par)?;
147                    let span = arg.span + value.span;
148                    args.push(Node::new(
149                        CallArg {
150                            label: Some(Node::new(name, arg.span)),
151                            value,
152                        },
153                        span,
154                    ));
155                } else {
156                    par.fancy_error(
157                        "Syntax error in argument list",
158                        vec![Label::primary(eq.span, "unexpected `=`".to_string())],
159                        vec![],
160                    );
161                }
162            }
163
164            TokenKind::Colon => {
165                let sep_tok = par.next()?;
166                let value = parse_expr(par)?;
167                if let Expr::Name(name) = arg.kind {
168                    let span = arg.span + value.span;
169                    args.push(Node::new(
170                        CallArg {
171                            label: Some(Node::new(name, arg.span)),
172                            value,
173                        },
174                        span,
175                    ));
176                } else {
177                    par.fancy_error(
178                        "Syntax error in function call argument list",
179                        vec![
180                            Label::primary(
181                                sep_tok.span,
182                                "In a function call, `:` is used for named arguments".to_string(),
183                            ),
184                            Label::secondary(
185                                arg.span,
186                                "this should be a function parameter name".to_string(),
187                            ),
188                        ],
189                        vec![],
190                    );
191                    return Err(ParseFailed);
192                }
193            }
194            _ => {
195                let span = arg.span;
196                args.push(Node::new(
197                    CallArg {
198                        label: None,
199                        value: arg,
200                    },
201                    span,
202                ));
203            }
204        }
205        if par.peek_or_err()? == Comma {
206            par.next()?;
207        } else {
208            span += par
209                .expect(ParenClose, "failed to parse function call argument list")?
210                .span;
211            break;
212        }
213    }
214
215    Ok(Node::new(args, span))
216}
217
218/// Try to build an expression starting with the given token.
219fn parse_expr_head(par: &mut Parser) -> ParseResult<Node<Expr>> {
220    use TokenKind::*;
221
222    match par.peek_or_err()? {
223        Name | SelfValue | Int | Hex | Octal | Binary | Text | True | False => {
224            let tok = par.next()?;
225            Ok(atom(par, &tok))
226        }
227        Plus | Minus | Not | Tilde => {
228            let op = par.next()?;
229            let operand = parse_expr_with_min_bp(par, prefix_binding_power(op.kind))?;
230            unary_op(par, &op, operand)
231        }
232        ParenOpen => parse_group_or_tuple(par),
233        BracketOpen => parse_list_or_repeat(par),
234        _ => {
235            let tok = par.next()?;
236            par.unexpected_token_error(
237                &tok,
238                format!("Unexpected token while parsing expression: `{}`", tok.text),
239                vec![],
240            );
241            Err(ParseFailed)
242        }
243    }
244}
245
246/// Specifies how tightly a prefix unary operator binds to its operand.
247fn prefix_binding_power(op: TokenKind) -> u8 {
248    use TokenKind::*;
249    match op {
250        Not => 65,
251        Plus | Minus | Tilde => 135,
252        _ => panic!("Unexpected unary op token: {op:?}"),
253    }
254}
255
256/// Specifies how tightly does an infix operator bind to its left and right
257/// operands. See https://docs.python.org/3/reference/expressions.html#operator-precedence
258fn infix_binding_power(op: TokenKind) -> Option<(u8, u8)> {
259    use TokenKind::*;
260
261    let bp = match op {
262        // assignment expr `:=`?
263        // lambda?
264        // Comma => (40, 41),
265        Or => (50, 51),
266        And => (60, 61),
267        // prefix Not => 65
268
269        // all comparisons are the same
270        Lt | LtEq | Gt | GtEq | NotEq | EqEq => (70, 71),
271
272        Pipe => (80, 81),
273        Hat => (90, 91),
274        Amper => (100, 101),
275        LtLt | GtGt => (110, 111),
276        Plus | Minus => (120, 121),
277        Star | Slash | Percent => (130, 131),
278        // Prefix Plus | Minus | Tilde => 135
279        StarStar => (141, 140),
280        Dot => (150, 151),
281        ColonColon => (160, 161),
282        _ => return None,
283    };
284    Some(bp)
285}
286
287/// Specifies how tightly a postfix operator binds to its operand.
288/// We don't have any "real" postfix operators (like `?` in rust),
289/// but we treat `[`, `(`, and ternary `if` as though they're postfix
290/// operators.
291fn postfix_binding_power(op: TokenKind) -> Option<u8> {
292    use TokenKind::*;
293    match op {
294        If => Some(35), // ternary
295        BracketOpen | ParenOpen => Some(150),
296        _ => None,
297    }
298}
299
300/// Parse a square-bracket list expression, eg. `[1, 2, x]` or `[true; 42]`
301fn parse_list_or_repeat(par: &mut Parser) -> ParseResult<Node<Expr>> {
302    let lbracket = par.assert(TokenKind::BracketOpen);
303    let elts = parse_expr_list(par, &[TokenKind::BracketClose, TokenKind::Semi], None)?;
304
305    if elts.len() == 1 {
306        if par.peek() == Some(TokenKind::BracketClose) {
307            let rbracket = par.assert(TokenKind::BracketClose);
308            let span = lbracket.span + rbracket.span;
309            Ok(Node::new(Expr::List { elts }, span))
310        } else if par.peek() == Some(TokenKind::Semi) {
311            par.assert(TokenKind::Semi);
312
313            let len = if par.peek() == Some(TokenKind::BraceOpen) {
314                // handle `{ ... }` const expression
315                let brace_open = par.next()?;
316                let expr = parse_expr(par)?;
317                if !matches!(par.peek(), Some(TokenKind::BraceClose)) {
318                    par.error(brace_open.span, "missing closing delimiter `}`");
319                    return Err(ParseFailed);
320                }
321                let brace_close = par.assert(TokenKind::BraceClose);
322                let span = brace_open.span + brace_close.span;
323                Box::new(Node::new(GenericArg::ConstExpr(expr), span))
324            } else {
325                // handle const expression without braces
326                let expr = parse_expr(par)?;
327                let span = expr.span;
328                Box::new(Node::new(GenericArg::ConstExpr(expr), span))
329            };
330
331            let rbracket = par.assert(TokenKind::BracketClose);
332            let span = lbracket.span + rbracket.span;
333            Ok(Node::new(
334                Expr::Repeat {
335                    value: Box::new(elts[0].clone()),
336                    len,
337                },
338                span,
339            ))
340        } else {
341            par.error(lbracket.span, "expected `]` or `;`");
342            Err(ParseFailed)
343        }
344    } else {
345        let rbracket = par.assert(TokenKind::BracketClose);
346        let span = lbracket.span + rbracket.span;
347        Ok(Node::new(Expr::List { elts }, span))
348    }
349}
350
351/// Parse a paren-wrapped expression, which might turn out to be a tuple
352/// if it contains commas.
353fn parse_group_or_tuple(par: &mut Parser) -> ParseResult<Node<Expr>> {
354    use TokenKind::*;
355    let lparen = par.assert(ParenOpen);
356    if par.peek_or_err()? == ParenClose {
357        let rparen = par.next()?;
358        let span = lparen.span + rparen.span;
359        return Ok(Node::new(Expr::Unit, span));
360    }
361
362    let elem = parse_expr(par)?;
363    match par.peek_or_err()? {
364        ParenClose => {
365            // expr wrapped in parens
366            let rparen = par.next()?;
367            let span = lparen.span + rparen.span;
368            Ok(Node::new(elem.kind, span))
369        }
370        Comma => {
371            // tuple
372            par.next()?;
373            let elts = parse_expr_list(par, &[ParenClose], Some(elem))?;
374            let rparen = par.expect(ParenClose, "failed to parse tuple expression")?;
375            let span = lparen.span + rparen.span;
376            Ok(Node::new(Expr::Tuple { elts }, span))
377        }
378        _ => {
379            let tok = par.next()?;
380            par.unexpected_token_error(
381                &tok,
382                "Unexpected token while parsing expression in parentheses",
383                vec![],
384            );
385            Err(ParseFailed)
386        }
387    }
388}
389
390/// Parse some number of comma-separated expressions, until `end_marker` is
391/// `peek()`ed.
392fn parse_expr_list(
393    par: &mut Parser,
394    end_markers: &[TokenKind],
395    head: Option<Node<Expr>>,
396) -> ParseResult<Vec<Node<Expr>>> {
397    let mut elts = vec![];
398    if let Some(elem) = head {
399        elts.push(elem);
400    }
401    loop {
402        let next = par.peek_or_err()?;
403        if end_markers.contains(&next) {
404            break;
405        }
406        elts.push(parse_expr(par)?);
407        match par.peek_or_err()? {
408            TokenKind::Comma => {
409                par.next()?;
410            }
411            tk if end_markers.contains(&tk) => break,
412            _ => {
413                let tok = par.next()?;
414                par.unexpected_token_error(
415                    &tok,
416                    "Unexpected token while parsing list of expressions",
417                    vec![],
418                );
419                return Err(ParseFailed);
420            }
421        }
422    }
423
424    Ok(elts)
425}
426
427/* node building utils */
428
429/// Create an "atom" expr from the given `Token` (`Name`, `Num`, `Bool`, etc)
430fn atom(par: &mut Parser, tok: &Token) -> Node<Expr> {
431    use TokenKind::*;
432
433    let expr = match tok.kind {
434        Name | SelfValue => Expr::Name(tok.text.into()),
435        Int | Hex | Octal | Binary => Expr::Num(tok.text.into()),
436        True | False => Expr::Bool(tok.kind == True),
437        Text => {
438            if let Some(string) = unescape_string(tok.text) {
439                Expr::Str(string.into())
440            } else {
441                par.error(tok.span, "String contains an invalid escape sequence");
442                Expr::Str(tok.text.into())
443            }
444        }
445        _ => panic!("Unexpected atom token: {tok:?}"),
446    };
447    Node::new(expr, tok.span)
448}
449
450fn unescape_string(quoted_string: &str) -> Option<String> {
451    let inner = &quoted_string[1..quoted_string.len() - 1];
452    unescape::unescape(inner)
453}
454
455/// Create an expr from the given infix operator and operands.
456fn infix_op(
457    par: &mut Parser,
458    left: Node<Expr>,
459    op: &Token,
460    right: Node<Expr>,
461) -> ParseResult<Node<Expr>> {
462    use TokenKind::*;
463    let expr = match op.kind {
464        Or | And => bool_op(left, op, right),
465
466        Amper | Hat | Pipe | LtLt | GtGt | Plus | Minus | Star | Slash | Percent | StarStar => {
467            bin_op(left, op, right)
468        }
469
470        Lt | LtEq | Gt | GtEq | NotEq | EqEq => comp_op(left, op, right),
471
472        Dot => {
473            let span = left.span + right.span;
474            match right.kind {
475                Expr::Name(name) => Node::new(
476                    Expr::Attribute {
477                        value: Box::new(left),
478                        attr: Node::new(name, right.span),
479                    },
480                    span,
481                ),
482                Expr::Num(_num) => {
483                    par.error(span, "floats not supported");
484                    return Err(ParseFailed);
485                }
486                Expr::Call {
487                    func,
488                    generic_args,
489                    args,
490                } => {
491                    let func_span = left.span + func.span;
492                    let func = Box::new(Node::new(
493                        Expr::Attribute {
494                            value: Box::new(left),
495                            attr: {
496                                if let Expr::Name(name) = func.kind {
497                                    Node::new(name, func.span)
498                                } else {
499                                    par.fancy_error(
500                                        "failed to parse attribute expression",
501                                        vec![Label::primary(func.span, "expected a name")],
502                                        vec![],
503                                    );
504                                    return Err(ParseFailed);
505                                }
506                            },
507                        },
508                        func_span,
509                    ));
510
511                    Node::new(
512                        Expr::Call {
513                            func,
514                            generic_args,
515                            args,
516                        },
517                        span,
518                    )
519                }
520                _ => {
521                    par.fancy_error(
522                        "failed to parse attribute expression",
523                        vec![Label::primary(right.span, "expected a name")],
524                        vec![],
525                    );
526                    return Err(ParseFailed);
527                }
528            }
529        }
530        ColonColon => {
531            let mut path = match left.kind {
532                Expr::Name(name) => Path {
533                    segments: vec![Node::new(name, left.span)],
534                },
535                Expr::Path(path) => path,
536                _ => {
537                    par.fancy_error(
538                        "failed to parse path expression",
539                        vec![
540                            Label::secondary(op.span, "path delimiter".to_string()),
541                            Label::primary(left.span, "expected a name"),
542                        ],
543                        vec![],
544                    );
545                    return Err(ParseFailed);
546                }
547            };
548
549            // `right` can't be a Path (rbp > lbp); only valid option is `Name`
550            match right.kind {
551                Expr::Name(name) => {
552                    path.segments.push(Node::new(name, right.span));
553                    Node::new(Expr::Path(path), left.span + right.span)
554                }
555                _ => {
556                    par.fancy_error(
557                        "failed to parse path expression",
558                        vec![
559                            Label::secondary(op.span, "path delimiter".to_string()),
560                            Label::primary(right.span, "expected a name"),
561                        ],
562                        vec![],
563                    );
564                    return Err(ParseFailed);
565                }
566            }
567        }
568        _ => panic!("Unexpected infix op token: {op:?}"),
569    };
570    Ok(expr)
571}
572
573/// Create an `Expr::BoolOperation` node for the given operator and operands.
574fn bool_op(left: Node<Expr>, op: &Token, right: Node<Expr>) -> Node<Expr> {
575    use TokenKind::*;
576    let astop = match op.kind {
577        And => ast::BoolOperator::And,
578        Or => ast::BoolOperator::Or,
579        _ => panic!(),
580    };
581
582    let span = left.span + right.span;
583    Node::new(
584        Expr::BoolOperation {
585            left: Box::new(left),
586            op: Node::new(astop, op.span),
587            right: Box::new(right),
588        },
589        span,
590    )
591}
592
593/// Create an `Expr::BinOperation` node for the given operator and operands.
594fn bin_op(left: Node<Expr>, op: &Token, right: Node<Expr>) -> Node<Expr> {
595    use ast::BinOperator::*;
596    use TokenKind::*;
597
598    let astop = match op.kind {
599        Amper => BitAnd,
600        Hat => BitXor,
601        Pipe => BitOr,
602        LtLt => LShift,
603        GtGt => RShift,
604        Plus => Add,
605        Minus => Sub,
606        Star => Mult,
607        Slash => Div,
608        Percent => Mod,
609        StarStar => Pow,
610        _ => panic!(),
611    };
612
613    let span = left.span + right.span;
614    Node::new(
615        Expr::BinOperation {
616            left: Box::new(left),
617            op: Node::new(astop, op.span),
618            right: Box::new(right),
619        },
620        span,
621    )
622}
623
624/// Create an `Expr::UnaryOperation` node for the given operator and operands.
625fn unary_op(par: &mut Parser, op: &Token, operand: Node<Expr>) -> ParseResult<Node<Expr>> {
626    use ast::UnaryOperator;
627    use TokenKind::*;
628
629    let astop = match op.kind {
630        Tilde => UnaryOperator::Invert,
631        Not => UnaryOperator::Not,
632        Minus => UnaryOperator::USub,
633        Plus => {
634            par.fancy_error(
635                "unary plus not supported",
636                vec![Label::primary(op.span, "consider removing the '+'")],
637                vec![],
638            );
639            return Err(ParseFailed);
640        }
641        _ => panic!(),
642    };
643
644    let span = op.span + operand.span;
645    Ok(Node::new(
646        Expr::UnaryOperation {
647            op: Node::new(astop, op.span),
648            operand: Box::new(operand),
649        },
650        span,
651    ))
652}
653
654/// Create an `Expr::CompOperation` node for the given operator and operands.
655fn comp_op(left: Node<Expr>, op: &Token, right: Node<Expr>) -> Node<Expr> {
656    use ast::CompOperator;
657    use TokenKind::*;
658    let astop = match op.kind {
659        In => todo!("in"), // CompOperator::In,
660        Lt => CompOperator::Lt,
661        LtEq => CompOperator::LtE,
662        Gt => CompOperator::Gt,
663        GtEq => CompOperator::GtE,
664        NotEq => CompOperator::NotEq,
665        EqEq => CompOperator::Eq,
666        _ => panic!(),
667    };
668    let span = left.span + right.span;
669    Node::new(
670        Expr::CompOperation {
671            left: Box::new(left),
672            op: Node::new(astop, op.span),
673            right: Box::new(right),
674        },
675        span,
676    )
677}
fe_parser/grammar/expressions.rs

fe_parser/grammar/
expressions.rs
