cypherlite_query/parser/
expression.rs

1// Pratt parser for expressions (arithmetic, comparison, boolean)
2
3use super::ast::*;
4use super::{ParseError, Parser};
5use crate::lexer::Token;
6
7/// Binding power for Pratt parser precedence.
8/// Returns (left_bp, right_bp) for infix operators.
9fn infix_binding_power(op: &BinaryOp) -> (u8, u8) {
10    match op {
11        BinaryOp::Or => (1, 2),
12        BinaryOp::And => (3, 4),
13        // Comparison operators are non-associative; use equal left/right
14        BinaryOp::Eq
15        | BinaryOp::Neq
16        | BinaryOp::Lt
17        | BinaryOp::Lte
18        | BinaryOp::Gt
19        | BinaryOp::Gte => (5, 6),
20        BinaryOp::Add | BinaryOp::Sub => (7, 8),
21        BinaryOp::Mul | BinaryOp::Div | BinaryOp::Mod => (9, 10),
22    }
23}
24
25/// Binding power for prefix unary operators.
26/// Returns right_bp.
27fn prefix_binding_power(op: &UnaryOp) -> u8 {
28    match op {
29        // NOT has same precedence as comparison level (between AND and comparison)
30        UnaryOp::Not => 4,
31        // Unary minus is high precedence
32        UnaryOp::Neg => 11,
33    }
34}
35
36/// Map a token to a binary operator, if applicable.
37fn token_to_binary_op(token: &Token) -> Option<BinaryOp> {
38    match token {
39        Token::Plus => Some(BinaryOp::Add),
40        Token::Minus => Some(BinaryOp::Sub),
41        Token::Star => Some(BinaryOp::Mul),
42        Token::Slash => Some(BinaryOp::Div),
43        Token::Percent => Some(BinaryOp::Mod),
44        Token::Eq => Some(BinaryOp::Eq),
45        Token::NotEqual | Token::BangEqual => Some(BinaryOp::Neq),
46        Token::Less => Some(BinaryOp::Lt),
47        Token::LessEqual => Some(BinaryOp::Lte),
48        Token::Greater => Some(BinaryOp::Gt),
49        Token::GreaterEqual => Some(BinaryOp::Gte),
50        Token::And => Some(BinaryOp::And),
51        Token::Or => Some(BinaryOp::Or),
52        _ => None,
53    }
54}
55
56impl<'a> Parser<'a> {
57    /// Parse an expression using Pratt parsing (precedence climbing).
58    pub fn parse_expression(&mut self) -> Result<Expression, ParseError> {
59        self.parse_expr_bp(0)
60    }
61
62    /// Parse an expression but stop before AND/OR (for `BETWEEN TIME expr AND expr`).
63    /// This prevents the AND keyword from being consumed as a binary AND operator.
64    pub fn parse_expression_no_and(&mut self) -> Result<Expression, ParseError> {
65        // AND has left bp = 3, so using min_bp = 4 will stop before AND
66        self.parse_expr_bp(4)
67    }
68
69    /// Pratt parser core: parse expression with minimum binding power.
70    fn parse_expr_bp(&mut self, min_bp: u8) -> Result<Expression, ParseError> {
71        // Parse prefix / primary
72        let mut lhs = self.parse_prefix()?;
73
74        loop {
75            // Property access (highest precedence postfix)
76            if self.check(&Token::Dot) {
77                self.advance();
78                let prop = self.expect_ident()?;
79                lhs = Expression::Property(Box::new(lhs), prop);
80                continue;
81            }
82
83            // IS [NOT] NULL (postfix)
84            if self.check(&Token::Is) {
85                let (line, col) = self.offset_to_line_col(self.current_span().start);
86                // IS NULL/IS NOT NULL has comparison-level precedence
87                let is_bp: u8 = 5;
88                if is_bp < min_bp {
89                    break;
90                }
91                self.advance(); // consume IS
92                let negated = self.eat(&Token::Not);
93                if !self.check(&Token::Null) {
94                    return Err(ParseError {
95                        line,
96                        column: col,
97                        message: "expected NULL after IS [NOT]".to_string(),
98                    });
99                }
100                self.advance(); // consume NULL
101                lhs = Expression::IsNull(Box::new(lhs), negated);
102                continue;
103            }
104
105            // Infix binary operator
106            let op = match self.peek().and_then(token_to_binary_op) {
107                Some(op) => op,
108                None => break,
109            };
110
111            let (l_bp, r_bp) = infix_binding_power(&op);
112            if l_bp < min_bp {
113                break;
114            }
115
116            self.advance(); // consume operator token
117            let rhs = self.parse_expr_bp(r_bp)?;
118            lhs = Expression::BinaryOp(op, Box::new(lhs), Box::new(rhs));
119        }
120
121        Ok(lhs)
122    }
123
124    /// Parse a prefix expression (unary operators or primary).
125    fn parse_prefix(&mut self) -> Result<Expression, ParseError> {
126        match self.peek() {
127            Some(Token::Not) => {
128                self.advance();
129                let r_bp = prefix_binding_power(&UnaryOp::Not);
130                let expr = self.parse_expr_bp(r_bp)?;
131                Ok(Expression::UnaryOp(UnaryOp::Not, Box::new(expr)))
132            }
133            Some(Token::Minus) => {
134                self.advance();
135                let r_bp = prefix_binding_power(&UnaryOp::Neg);
136                let expr = self.parse_expr_bp(r_bp)?;
137                Ok(Expression::UnaryOp(UnaryOp::Neg, Box::new(expr)))
138            }
139            Some(Token::LParen) => {
140                self.advance();
141                let expr = self.parse_expr_bp(0)?;
142                self.expect(&Token::RParen)?;
143                Ok(expr)
144            }
145            Some(Token::LBracket) => self.parse_list_literal(),
146            _ => self.parse_primary(),
147        }
148    }
149
150    /// Parse a list literal: `[expr, expr, ...]`
151    fn parse_list_literal(&mut self) -> Result<Expression, ParseError> {
152        self.expect(&Token::LBracket)?;
153        let mut elements = Vec::new();
154        if !self.check(&Token::RBracket) {
155            elements.push(self.parse_expression()?);
156            while self.eat(&Token::Comma) {
157                elements.push(self.parse_expression()?);
158            }
159        }
160        self.expect(&Token::RBracket)?;
161        Ok(Expression::ListLiteral(elements))
162    }
163
164    /// Parse a primary expression: literal, variable, function call, parameter.
165    fn parse_primary(&mut self) -> Result<Expression, ParseError> {
166        match self.peek().cloned() {
167            Some(Token::Integer(n)) => {
168                self.advance();
169                Ok(Expression::Literal(Literal::Integer(n)))
170            }
171            Some(Token::Float(f)) => {
172                self.advance();
173                Ok(Expression::Literal(Literal::Float(f)))
174            }
175            Some(Token::StringLiteral(s)) => {
176                self.advance();
177                Ok(Expression::Literal(Literal::String(s)))
178            }
179            Some(Token::True) => {
180                self.advance();
181                Ok(Expression::Literal(Literal::Bool(true)))
182            }
183            Some(Token::False) => {
184                self.advance();
185                Ok(Expression::Literal(Literal::Bool(false)))
186            }
187            Some(Token::Null) => {
188                self.advance();
189                Ok(Expression::Literal(Literal::Null))
190            }
191            Some(Token::Parameter(name)) => {
192                self.advance();
193                Ok(Expression::Parameter(name))
194            }
195            // count(*) or count(DISTINCT x) or count(x)
196            Some(Token::Count) => {
197                self.advance();
198                self.expect(&Token::LParen)?;
199                if self.eat(&Token::Star) {
200                    self.expect(&Token::RParen)?;
201                    return Ok(Expression::CountStar);
202                }
203                let distinct = self.eat(&Token::Distinct);
204                let arg = self.parse_expression()?;
205                self.expect(&Token::RParen)?;
206                Ok(Expression::FunctionCall {
207                    name: "count".to_string(),
208                    distinct,
209                    args: vec![arg],
210                })
211            }
212            // Generic function call: ident(args) or plain variable
213            Some(Token::Ident(name)) => {
214                self.advance();
215                // Check for function call
216                if self.check(&Token::LParen) {
217                    self.advance(); // consume '('
218                    let distinct = self.eat(&Token::Distinct);
219                    let mut args = Vec::new();
220                    if !self.check(&Token::RParen) {
221                        args.push(self.parse_expression()?);
222                        while self.eat(&Token::Comma) {
223                            args.push(self.parse_expression()?);
224                        }
225                    }
226                    self.expect(&Token::RParen)?;
227                    Ok(Expression::FunctionCall {
228                        name,
229                        distinct,
230                        args,
231                    })
232                } else {
233                    Ok(Expression::Variable(name))
234                }
235            }
236            Some(Token::BacktickIdent(name)) => {
237                self.advance();
238                Ok(Expression::Variable(name))
239            }
240            Some(tok) => Err(self.error(format!("unexpected token in expression: {:?}", tok))),
241            None => Err(self.error("unexpected end of input in expression")),
242        }
243    }
244}
245
246// ---------------------------------------------------------------------------
247// Tests
248// ---------------------------------------------------------------------------
249
250#[cfg(test)]
251mod tests {
252    use super::*;
253    use crate::lexer::lex;
254
255    /// Helper: parse an expression from a string.
256    fn parse_expr(input: &str) -> Result<Expression, ParseError> {
257        let tokens = lex(input).expect("lexing should succeed");
258        let mut parser = Parser::new(&tokens, input);
259        parser.parse_expression()
260    }
261
262    // -- TASK-022: Expression parser tests --
263
264    // Precedence: 1 + 2 * 3 -> Add(1, Mul(2, 3))
265    #[test]
266    fn expr_precedence_add_mul() {
267        let expr = parse_expr("1 + 2 * 3").expect("should parse");
268        assert_eq!(
269            expr,
270            Expression::BinaryOp(
271                BinaryOp::Add,
272                Box::new(Expression::Literal(Literal::Integer(1))),
273                Box::new(Expression::BinaryOp(
274                    BinaryOp::Mul,
275                    Box::new(Expression::Literal(Literal::Integer(2))),
276                    Box::new(Expression::Literal(Literal::Integer(3))),
277                )),
278            )
279        );
280    }
281
282    // Parenthesized: (1 + 2) * 3 -> Mul(Add(1, 2), 3)
283    #[test]
284    fn expr_parenthesized() {
285        let expr = parse_expr("(1 + 2) * 3").expect("should parse");
286        assert_eq!(
287            expr,
288            Expression::BinaryOp(
289                BinaryOp::Mul,
290                Box::new(Expression::BinaryOp(
291                    BinaryOp::Add,
292                    Box::new(Expression::Literal(Literal::Integer(1))),
293                    Box::new(Expression::Literal(Literal::Integer(2))),
294                )),
295                Box::new(Expression::Literal(Literal::Integer(3))),
296            )
297        );
298    }
299
300    // Comparison: n.age > 30
301    #[test]
302    fn expr_comparison_property() {
303        let expr = parse_expr("n.age > 30").expect("should parse");
304        assert_eq!(
305            expr,
306            Expression::BinaryOp(
307                BinaryOp::Gt,
308                Box::new(Expression::Property(
309                    Box::new(Expression::Variable("n".to_string())),
310                    "age".to_string(),
311                )),
312                Box::new(Expression::Literal(Literal::Integer(30))),
313            )
314        );
315    }
316
317    // Boolean: a AND b OR c -> Or(And(a, b), c)
318    #[test]
319    fn expr_boolean_precedence() {
320        let expr = parse_expr("a AND b OR c").expect("should parse");
321        assert_eq!(
322            expr,
323            Expression::BinaryOp(
324                BinaryOp::Or,
325                Box::new(Expression::BinaryOp(
326                    BinaryOp::And,
327                    Box::new(Expression::Variable("a".to_string())),
328                    Box::new(Expression::Variable("b".to_string())),
329                )),
330                Box::new(Expression::Variable("c".to_string())),
331            )
332        );
333    }
334
335    // NOT: NOT x
336    #[test]
337    fn expr_not_unary() {
338        let expr = parse_expr("NOT x").expect("should parse");
339        assert_eq!(
340            expr,
341            Expression::UnaryOp(
342                UnaryOp::Not,
343                Box::new(Expression::Variable("x".to_string())),
344            )
345        );
346    }
347
348    // NOT with AND: NOT a AND b -> And(Not(a), b)
349    #[test]
350    fn expr_not_and_precedence() {
351        let expr = parse_expr("NOT a AND b").expect("should parse");
352        assert_eq!(
353            expr,
354            Expression::BinaryOp(
355                BinaryOp::And,
356                Box::new(Expression::UnaryOp(
357                    UnaryOp::Not,
358                    Box::new(Expression::Variable("a".to_string())),
359                )),
360                Box::new(Expression::Variable("b".to_string())),
361            )
362        );
363    }
364
365    // Function call: count(n)
366    #[test]
367    fn expr_function_call_count() {
368        let expr = parse_expr("count(n)").expect("should parse");
369        assert_eq!(
370            expr,
371            Expression::FunctionCall {
372                name: "count".to_string(),
373                distinct: false,
374                args: vec![Expression::Variable("n".to_string())],
375            }
376        );
377    }
378
379    // Function call: count(DISTINCT n)
380    #[test]
381    fn expr_function_call_count_distinct() {
382        let expr = parse_expr("count(DISTINCT n)").expect("should parse");
383        assert_eq!(
384            expr,
385            Expression::FunctionCall {
386                name: "count".to_string(),
387                distinct: true,
388                args: vec![Expression::Variable("n".to_string())],
389            }
390        );
391    }
392
393    // count(*)
394    #[test]
395    fn expr_count_star() {
396        let expr = parse_expr("count(*)").expect("should parse");
397        assert_eq!(expr, Expression::CountStar);
398    }
399
400    // Generic function call: toUpper(n.name)
401    #[test]
402    fn expr_generic_function_call() {
403        let expr = parse_expr("toUpper(n.name)").expect("should parse");
404        assert_eq!(
405            expr,
406            Expression::FunctionCall {
407                name: "toUpper".to_string(),
408                distinct: false,
409                args: vec![Expression::Property(
410                    Box::new(Expression::Variable("n".to_string())),
411                    "name".to_string(),
412                )],
413            }
414        );
415    }
416
417    // Multi-arg function: coalesce(a, b, c)
418    #[test]
419    fn expr_multi_arg_function() {
420        let expr = parse_expr("coalesce(a, b, c)").expect("should parse");
421        assert_eq!(
422            expr,
423            Expression::FunctionCall {
424                name: "coalesce".to_string(),
425                distinct: false,
426                args: vec![
427                    Expression::Variable("a".to_string()),
428                    Expression::Variable("b".to_string()),
429                    Expression::Variable("c".to_string()),
430                ],
431            }
432        );
433    }
434
435    // Parameter: $name
436    #[test]
437    fn expr_parameter() {
438        let expr = parse_expr("$name").expect("should parse");
439        assert_eq!(expr, Expression::Parameter("name".to_string()));
440    }
441
442    // IS NULL
443    #[test]
444    fn expr_is_null() {
445        let expr = parse_expr("n.name IS NULL").expect("should parse");
446        assert_eq!(
447            expr,
448            Expression::IsNull(
449                Box::new(Expression::Property(
450                    Box::new(Expression::Variable("n".to_string())),
451                    "name".to_string(),
452                )),
453                false,
454            )
455        );
456    }
457
458    // IS NOT NULL
459    #[test]
460    fn expr_is_not_null() {
461        let expr = parse_expr("n.name IS NOT NULL").expect("should parse");
462        assert_eq!(
463            expr,
464            Expression::IsNull(
465                Box::new(Expression::Property(
466                    Box::new(Expression::Variable("n".to_string())),
467                    "name".to_string(),
468                )),
469                true,
470            )
471        );
472    }
473
474    // Literals
475    #[test]
476    fn expr_literal_integer() {
477        let expr = parse_expr("42").expect("should parse");
478        assert_eq!(expr, Expression::Literal(Literal::Integer(42)));
479    }
480
481    #[test]
482    fn expr_literal_float() {
483        let expr = parse_expr("3.15").expect("should parse");
484        assert_eq!(expr, Expression::Literal(Literal::Float(3.15)));
485    }
486
487    #[test]
488    fn expr_literal_string() {
489        let expr = parse_expr("'hello'").expect("should parse");
490        assert_eq!(
491            expr,
492            Expression::Literal(Literal::String("hello".to_string()))
493        );
494    }
495
496    #[test]
497    fn expr_literal_true() {
498        let expr = parse_expr("true").expect("should parse");
499        assert_eq!(expr, Expression::Literal(Literal::Bool(true)));
500    }
501
502    #[test]
503    fn expr_literal_false() {
504        let expr = parse_expr("false").expect("should parse");
505        assert_eq!(expr, Expression::Literal(Literal::Bool(false)));
506    }
507
508    #[test]
509    fn expr_literal_null() {
510        let expr = parse_expr("null").expect("should parse");
511        assert_eq!(expr, Expression::Literal(Literal::Null));
512    }
513
514    // Unary minus
515    #[test]
516    fn expr_unary_minus() {
517        let expr = parse_expr("-42").expect("should parse");
518        assert_eq!(
519            expr,
520            Expression::UnaryOp(
521                UnaryOp::Neg,
522                Box::new(Expression::Literal(Literal::Integer(42))),
523            )
524        );
525    }
526
527    // Chained property access: a.b.c
528    #[test]
529    fn expr_chained_property() {
530        let expr = parse_expr("a.b.c").expect("should parse");
531        assert_eq!(
532            expr,
533            Expression::Property(
534                Box::new(Expression::Property(
535                    Box::new(Expression::Variable("a".to_string())),
536                    "b".to_string(),
537                )),
538                "c".to_string(),
539            )
540        );
541    }
542
543    // Complex: n.age >= 18 AND n.name <> 'unknown'
544    #[test]
545    fn expr_complex_boolean_comparison() {
546        let expr = parse_expr("n.age >= 18 AND n.name <> 'unknown'").expect("should parse");
547        assert_eq!(
548            expr,
549            Expression::BinaryOp(
550                BinaryOp::And,
551                Box::new(Expression::BinaryOp(
552                    BinaryOp::Gte,
553                    Box::new(Expression::Property(
554                        Box::new(Expression::Variable("n".to_string())),
555                        "age".to_string(),
556                    )),
557                    Box::new(Expression::Literal(Literal::Integer(18))),
558                )),
559                Box::new(Expression::BinaryOp(
560                    BinaryOp::Neq,
561                    Box::new(Expression::Property(
562                        Box::new(Expression::Variable("n".to_string())),
563                        "name".to_string(),
564                    )),
565                    Box::new(Expression::Literal(Literal::String("unknown".to_string()))),
566                )),
567            )
568        );
569    }
570
571    // != operator
572    #[test]
573    fn expr_bang_equal() {
574        let expr = parse_expr("a != b").expect("should parse");
575        assert_eq!(
576            expr,
577            Expression::BinaryOp(
578                BinaryOp::Neq,
579                Box::new(Expression::Variable("a".to_string())),
580                Box::new(Expression::Variable("b".to_string())),
581            )
582        );
583    }
584
585    // Error case: empty input
586    #[test]
587    fn expr_error_empty() {
588        let result = parse_expr("");
589        assert!(result.is_err());
590    }
591
592    // Error case: unmatched paren
593    #[test]
594    fn expr_error_unmatched_paren() {
595        let result = parse_expr("(1 + 2");
596        assert!(result.is_err());
597    }
598
599    // ---- TASK-067/068: List literal expressions ----
600
601    #[test]
602    fn expr_list_literal_empty() {
603        let expr = parse_expr("[]").expect("should parse");
604        assert_eq!(expr, Expression::ListLiteral(vec![]));
605    }
606
607    #[test]
608    fn expr_list_literal_integers() {
609        let expr = parse_expr("[1, 2, 3]").expect("should parse");
610        assert_eq!(
611            expr,
612            Expression::ListLiteral(vec![
613                Expression::Literal(Literal::Integer(1)),
614                Expression::Literal(Literal::Integer(2)),
615                Expression::Literal(Literal::Integer(3)),
616            ])
617        );
618    }
619
620    #[test]
621    fn expr_list_literal_mixed() {
622        let expr = parse_expr("[1, 'hello', true, null]").expect("should parse");
623        assert_eq!(
624            expr,
625            Expression::ListLiteral(vec![
626                Expression::Literal(Literal::Integer(1)),
627                Expression::Literal(Literal::String("hello".to_string())),
628                Expression::Literal(Literal::Bool(true)),
629                Expression::Literal(Literal::Null),
630            ])
631        );
632    }
633
634    #[test]
635    fn expr_list_literal_nested() {
636        let expr = parse_expr("[[1, 2], [3]]").expect("should parse");
637        assert_eq!(
638            expr,
639            Expression::ListLiteral(vec![
640                Expression::ListLiteral(vec![
641                    Expression::Literal(Literal::Integer(1)),
642                    Expression::Literal(Literal::Integer(2)),
643                ]),
644                Expression::ListLiteral(vec![Expression::Literal(Literal::Integer(3)),]),
645            ])
646        );
647    }
648
649    #[test]
650    fn expr_list_literal_with_expressions() {
651        let expr = parse_expr("[1 + 2, n.name]").expect("should parse");
652        assert_eq!(
653            expr,
654            Expression::ListLiteral(vec![
655                Expression::BinaryOp(
656                    BinaryOp::Add,
657                    Box::new(Expression::Literal(Literal::Integer(1))),
658                    Box::new(Expression::Literal(Literal::Integer(2))),
659                ),
660                Expression::Property(
661                    Box::new(Expression::Variable("n".to_string())),
662                    "name".to_string(),
663                ),
664            ])
665        );
666    }
667
668    // All arithmetic operators
669    #[test]
670    fn expr_all_arithmetic() {
671        let expr = parse_expr("1 + 2 - 3 * 4 / 5 % 6").expect("should parse");
672        // 1 + 2 - ((3 * 4) / 5) % 6
673        // Due to left-to-right at same precedence:
674        // Mul/Div/Mod: 3*4=Mul(3,4), Mul(3,4)/5=Div(Mul(3,4),5), Div(...)/6... wait
675        // Actually: 3 * 4 / 5 % 6 at precedence 9/10 (left-to-right)
676        // = Mod(Div(Mul(3,4),5),6)
677        // Then: 1 + 2 - Mod(...) at precedence 7/8 (left-to-right)
678        // = Sub(Add(1,2), Mod(Div(Mul(3,4),5),6))
679        assert_eq!(
680            expr,
681            Expression::BinaryOp(
682                BinaryOp::Sub,
683                Box::new(Expression::BinaryOp(
684                    BinaryOp::Add,
685                    Box::new(Expression::Literal(Literal::Integer(1))),
686                    Box::new(Expression::Literal(Literal::Integer(2))),
687                )),
688                Box::new(Expression::BinaryOp(
689                    BinaryOp::Mod,
690                    Box::new(Expression::BinaryOp(
691                        BinaryOp::Div,
692                        Box::new(Expression::BinaryOp(
693                            BinaryOp::Mul,
694                            Box::new(Expression::Literal(Literal::Integer(3))),
695                            Box::new(Expression::Literal(Literal::Integer(4))),
696                        )),
697                        Box::new(Expression::Literal(Literal::Integer(5))),
698                    )),
699                    Box::new(Expression::Literal(Literal::Integer(6))),
700                )),
701            )
702        );
703    }
704}
cypherlite_query/parser/expression.rs

cypherlite_query/parser/
expression.rs
