nodedb_query/expr_parse/
parser.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! SQL expression text → SqlExpr AST parser.
4//!
5//! Parses the subset of SQL expressions used in `GENERATED ALWAYS AS (expr)`
6//! column definitions. Supports:
7//! - Column references: `price`, `tax_rate`
8//! - Numeric literals: `42`, `3.14`, `-1`
9//! - String literals: `'hello'`, `''escaped''`
10//! - Binary operators: `+`, `-`, `*`, `/`, `%`
11//! - Comparison: `=`, `!=`, `<>`, `<`, `>`, `<=`, `>=`
12//! - Logical: `AND`, `OR`, `NOT`
13//! - Predicates: `IS [NOT] NULL`, `[NOT] LIKE` / `ILIKE` (with `ESCAPE`),
14//!   `[NOT] IN (...)`, `[NOT] BETWEEN ... AND ...`
15//! - Parenthesized sub-expressions: `(a + b) * c`
16//! - Function calls: `ROUND(price * 1.08, 2)`, `CONCAT(a, ' ', b)`
17//! - COALESCE: `COALESCE(a, b, '')`
18//! - CASE WHEN: `CASE WHEN x > 0 THEN 'positive' ELSE 'non-positive' END`
19//! - NULL literal
20//!
21//! Determinism validation: rejects `NOW()`, `RANDOM()`, `NEXTVAL()`, `UUID()`.
22
23use super::error::ExprParseError;
24use super::predicate::parse_postfix_predicate;
25use super::tokenizer::{Token, TokenKind, tokenize};
26use super::validate::{collect_columns, validate_deterministic};
27use crate::expr::{BinaryOp, SqlExpr};
28use nodedb_types::Value;
29
30/// Parse a SQL expression string into an SqlExpr AST.
31///
32/// Returns the parsed expression and a list of column names it references
33/// (the `depends_on` set for generated columns).
34pub fn parse_generated_expr(text: &str) -> Result<(SqlExpr, Vec<String>), ExprParseError> {
35    let tokens = tokenize(text)?;
36    let mut pos = 0;
37    let expr = parse_expr(&tokens, &mut pos, &mut 0)?;
38    if pos < tokens.len() {
39        return Err(ExprParseError::UnexpectedToken {
40            found: tokens[pos].text.clone(),
41            pos,
42        });
43    }
44
45    // Validate determinism.
46    validate_deterministic(&expr)?;
47
48    // Collect column references.
49    let mut deps = Vec::new();
50    collect_columns(&expr, &mut deps);
51    deps.sort();
52    deps.dedup();
53
54    Ok((expr, deps))
55}
56
57// ── Recursive descent parser ──────────────────────────────────────────
58
59/// Maximum recursion depth for nested parentheses / sub-expressions.
60const MAX_EXPR_DEPTH: usize = 128;
61
62fn parse_expr(
63    tokens: &[Token],
64    pos: &mut usize,
65    depth: &mut usize,
66) -> Result<SqlExpr, ExprParseError> {
67    parse_or(tokens, pos, depth)
68}
69
70fn parse_or(
71    tokens: &[Token],
72    pos: &mut usize,
73    depth: &mut usize,
74) -> Result<SqlExpr, ExprParseError> {
75    let mut left = parse_and(tokens, pos, depth)?;
76    while peek_keyword(tokens, *pos, "OR") {
77        *pos += 1;
78        let right = parse_and(tokens, pos, depth)?;
79        left = SqlExpr::BinaryOp {
80            left: Box::new(left),
81            op: BinaryOp::Or,
82            right: Box::new(right),
83        };
84    }
85    Ok(left)
86}
87
88fn parse_and(
89    tokens: &[Token],
90    pos: &mut usize,
91    depth: &mut usize,
92) -> Result<SqlExpr, ExprParseError> {
93    let mut left = parse_not(tokens, pos, depth)?;
94    while peek_keyword(tokens, *pos, "AND") {
95        *pos += 1;
96        let right = parse_not(tokens, pos, depth)?;
97        left = SqlExpr::BinaryOp {
98            left: Box::new(left),
99            op: BinaryOp::And,
100            right: Box::new(right),
101        };
102    }
103    Ok(left)
104}
105
106/// `NOT` binds looser than a comparison: `NOT a = b` is `NOT (a = b)`.
107fn parse_not(
108    tokens: &[Token],
109    pos: &mut usize,
110    depth: &mut usize,
111) -> Result<SqlExpr, ExprParseError> {
112    if peek_keyword(tokens, *pos, "NOT") {
113        *pos += 1;
114        let inner = parse_not(tokens, pos, depth)?;
115        return Ok(SqlExpr::Negate(Box::new(inner)));
116    }
117    parse_comparison(tokens, pos, depth)
118}
119
120fn parse_comparison(
121    tokens: &[Token],
122    pos: &mut usize,
123    depth: &mut usize,
124) -> Result<SqlExpr, ExprParseError> {
125    let operand = parse_additive(tokens, pos, depth)?;
126    let left = parse_postfix_predicate(operand, tokens, pos, depth)?;
127    if *pos < tokens.len() && tokens[*pos].kind == TokenKind::Op {
128        let op = match tokens[*pos].text.as_str() {
129            "=" => BinaryOp::Eq,
130            "!=" | "<>" => BinaryOp::NotEq,
131            "<" => BinaryOp::Lt,
132            "<=" => BinaryOp::LtEq,
133            ">" => BinaryOp::Gt,
134            ">=" => BinaryOp::GtEq,
135            _ => return Ok(left),
136        };
137        *pos += 1;
138        let right = parse_additive(tokens, pos, depth)?;
139        return Ok(SqlExpr::BinaryOp {
140            left: Box::new(left),
141            op,
142            right: Box::new(right),
143        });
144    }
145    Ok(left)
146}
147
148pub(super) fn parse_additive(
149    tokens: &[Token],
150    pos: &mut usize,
151    depth: &mut usize,
152) -> Result<SqlExpr, ExprParseError> {
153    let mut left = parse_multiplicative(tokens, pos, depth)?;
154    while *pos < tokens.len() && tokens[*pos].kind == TokenKind::Op {
155        let op = match tokens[*pos].text.as_str() {
156            "+" => BinaryOp::Add,
157            "-" => BinaryOp::Sub,
158            "||" => BinaryOp::Concat,
159            _ => break,
160        };
161        *pos += 1;
162        let right = parse_multiplicative(tokens, pos, depth)?;
163        left = SqlExpr::BinaryOp {
164            left: Box::new(left),
165            op,
166            right: Box::new(right),
167        };
168    }
169    Ok(left)
170}
171
172fn parse_multiplicative(
173    tokens: &[Token],
174    pos: &mut usize,
175    depth: &mut usize,
176) -> Result<SqlExpr, ExprParseError> {
177    let mut left = parse_unary(tokens, pos, depth)?;
178    while *pos < tokens.len() && tokens[*pos].kind == TokenKind::Op {
179        let op = match tokens[*pos].text.as_str() {
180            "*" => BinaryOp::Mul,
181            "/" => BinaryOp::Div,
182            "%" => BinaryOp::Mod,
183            _ => break,
184        };
185        *pos += 1;
186        let right = parse_unary(tokens, pos, depth)?;
187        left = SqlExpr::BinaryOp {
188            left: Box::new(left),
189            op,
190            right: Box::new(right),
191        };
192    }
193    Ok(left)
194}
195
196fn parse_unary(
197    tokens: &[Token],
198    pos: &mut usize,
199    depth: &mut usize,
200) -> Result<SqlExpr, ExprParseError> {
201    if *pos < tokens.len() && tokens[*pos].kind == TokenKind::Op && tokens[*pos].text == "-" {
202        *pos += 1;
203        let expr = parse_primary(tokens, pos, depth)?;
204        return Ok(SqlExpr::Negate(Box::new(expr)));
205    }
206    if peek_keyword(tokens, *pos, "NOT") {
207        *pos += 1;
208        let expr = parse_primary(tokens, pos, depth)?;
209        return Ok(SqlExpr::Negate(Box::new(expr)));
210    }
211    parse_primary(tokens, pos, depth)
212}
213
214fn parse_primary(
215    tokens: &[Token],
216    pos: &mut usize,
217    depth: &mut usize,
218) -> Result<SqlExpr, ExprParseError> {
219    if *pos >= tokens.len() {
220        return Err(ExprParseError::UnexpectedEof);
221    }
222
223    let token = &tokens[*pos];
224
225    match token.kind {
226        TokenKind::LParen => {
227            *depth += 1;
228            if *depth > MAX_EXPR_DEPTH {
229                return Err(ExprParseError::DepthLimitExceeded {
230                    max: MAX_EXPR_DEPTH,
231                });
232            }
233            *pos += 1;
234            let expr = parse_expr(tokens, pos, depth)?;
235            *depth -= 1;
236            expect_token(tokens, pos, TokenKind::RParen, ")")?;
237            Ok(expr)
238        }
239
240        TokenKind::Number => {
241            *pos += 1;
242            if let Ok(i) = token.text.parse::<i64>() {
243                Ok(SqlExpr::Literal(Value::Integer(i)))
244            } else if let Ok(f) = token.text.parse::<f64>() {
245                Ok(SqlExpr::Literal(Value::Float(f)))
246            } else {
247                Err(ExprParseError::InvalidLiteral {
248                    detail: format!("invalid number: '{}'", token.text),
249                })
250            }
251        }
252
253        TokenKind::StringLit => {
254            *pos += 1;
255            Ok(SqlExpr::Literal(Value::String(token.text.clone())))
256        }
257
258        TokenKind::Ident => {
259            let name = token.text.clone();
260            let upper = name.to_uppercase();
261            *pos += 1;
262
263            match upper.as_str() {
264                "NULL" => Ok(SqlExpr::Literal(Value::Null)),
265                "TRUE" => Ok(SqlExpr::Literal(Value::Bool(true))),
266                "FALSE" => Ok(SqlExpr::Literal(Value::Bool(false))),
267                "CASE" => parse_case(tokens, pos, depth),
268                "COALESCE" => {
269                    let args = parse_arg_list(tokens, pos, depth)?;
270                    Ok(SqlExpr::Coalesce(args))
271                }
272                _ => {
273                    if *pos < tokens.len() && tokens[*pos].kind == TokenKind::LParen {
274                        let args = parse_arg_list(tokens, pos, depth)?;
275                        Ok(SqlExpr::Function {
276                            name: name.to_lowercase(),
277                            args,
278                        })
279                    } else {
280                        Ok(SqlExpr::Column(name.to_lowercase()))
281                    }
282                }
283            }
284        }
285
286        _ => Err(ExprParseError::UnexpectedToken {
287            found: token.text.clone(),
288            pos: *pos,
289        }),
290    }
291}
292
293fn parse_case(
294    tokens: &[Token],
295    pos: &mut usize,
296    depth: &mut usize,
297) -> Result<SqlExpr, ExprParseError> {
298    let mut when_thens = Vec::new();
299    let mut else_expr = None;
300
301    loop {
302        if peek_keyword(tokens, *pos, "WHEN") {
303            *pos += 1;
304            let cond = parse_expr(tokens, pos, depth)?;
305            expect_keyword(tokens, pos, "THEN")?;
306            let then = parse_expr(tokens, pos, depth)?;
307            when_thens.push((cond, then));
308        } else if peek_keyword(tokens, *pos, "ELSE") {
309            *pos += 1;
310            else_expr = Some(Box::new(parse_expr(tokens, pos, depth)?));
311        } else if peek_keyword(tokens, *pos, "END") {
312            *pos += 1;
313            break;
314        } else {
315            return Err(ExprParseError::UnexpectedToken {
316                found: tokens
317                    .get(*pos)
318                    .map_or("EOF".to_string(), |t| t.text.clone()),
319                pos: *pos,
320            });
321        }
322    }
323
324    if when_thens.is_empty() {
325        return Err(ExprParseError::InvalidLiteral {
326            detail: "CASE requires at least one WHEN clause".to_string(),
327        });
328    }
329
330    Ok(SqlExpr::Case {
331        operand: None,
332        when_thens,
333        else_expr,
334    })
335}
336
337pub(super) fn parse_arg_list(
338    tokens: &[Token],
339    pos: &mut usize,
340    depth: &mut usize,
341) -> Result<Vec<SqlExpr>, ExprParseError> {
342    expect_token(tokens, pos, TokenKind::LParen, "(")?;
343    let mut args = Vec::new();
344    if *pos < tokens.len() && tokens[*pos].kind == TokenKind::RParen {
345        *pos += 1;
346        return Ok(args);
347    }
348    loop {
349        args.push(parse_expr(tokens, pos, depth)?);
350        if *pos < tokens.len() && tokens[*pos].kind == TokenKind::Comma {
351            *pos += 1;
352        } else {
353            break;
354        }
355    }
356    expect_token(tokens, pos, TokenKind::RParen, ")")?;
357    Ok(args)
358}
359
360// ── Helpers ───────────────────────────────────────────────────────────
361
362pub(super) fn peek_keyword(tokens: &[Token], pos: usize, keyword: &str) -> bool {
363    pos < tokens.len()
364        && tokens[pos].kind == TokenKind::Ident
365        && tokens[pos].text.eq_ignore_ascii_case(keyword)
366}
367
368pub(super) fn expect_keyword(
369    tokens: &[Token],
370    pos: &mut usize,
371    keyword: &str,
372) -> Result<(), ExprParseError> {
373    if peek_keyword(tokens, *pos, keyword) {
374        *pos += 1;
375        Ok(())
376    } else {
377        let got = tokens
378            .get(*pos)
379            .map_or_else(|| "EOF".to_string(), |t| t.text.clone());
380        Err(ExprParseError::UnexpectedToken {
381            found: got,
382            pos: *pos,
383        })
384    }
385}
386
387fn expect_token(
388    tokens: &[Token],
389    pos: &mut usize,
390    kind: TokenKind,
391    _expected: &str,
392) -> Result<(), ExprParseError> {
393    if *pos < tokens.len() && tokens[*pos].kind == kind {
394        *pos += 1;
395        Ok(())
396    } else {
397        let got = tokens
398            .get(*pos)
399            .map_or_else(|| "EOF".to_string(), |t| t.text.clone());
400        Err(ExprParseError::UnexpectedToken {
401            found: got,
402            pos: *pos,
403        })
404    }
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410    use nodedb_types::Value;
411
412    fn parse_ok(text: &str) -> (SqlExpr, Vec<String>) {
413        parse_generated_expr(text).unwrap()
414    }
415
416    #[test]
417    fn simple_arithmetic() {
418        let (expr, deps) = parse_ok("price * (1 + tax_rate)");
419        assert_eq!(deps, vec!["price", "tax_rate"]);
420        let doc = Value::from(serde_json::json!({"price": 100.0, "tax_rate": 0.08}));
421        let result = expr.eval(&doc).unwrap();
422        assert_eq!(result.as_f64(), Some(108.0));
423    }
424
425    #[test]
426    fn round_function() {
427        let (expr, deps) = parse_ok("ROUND(price * (1 + tax_rate), 2)");
428        assert_eq!(deps, vec!["price", "tax_rate"]);
429        let doc = Value::from(serde_json::json!({"price": 99.99, "tax_rate": 0.08}));
430        let result = expr.eval(&doc).unwrap();
431        assert_eq!(result, Value::Float(107.99));
432    }
433
434    #[test]
435    fn concat_function() {
436        let (expr, deps) = parse_ok("CONCAT(name, ' ', brand)");
437        assert_eq!(deps, vec!["brand", "name"]);
438        let doc = Value::from(serde_json::json!({"name": "Shoe", "brand": "Nike"}));
439        assert_eq!(expr.eval(&doc).unwrap(), Value::String("Shoe Nike".into()));
440    }
441
442    #[test]
443    fn coalesce() {
444        let (expr, _) = parse_ok("COALESCE(description, '')");
445        let doc = Value::from(serde_json::json!({"description": null}));
446        assert_eq!(expr.eval(&doc).unwrap(), Value::String("".into()));
447    }
448
449    #[test]
450    fn case_when() {
451        let (expr, deps) =
452            parse_ok("CASE WHEN discount > 0 THEN price * (1 - discount) ELSE price END");
453        assert!(deps.contains(&"discount".to_string()));
454        assert!(deps.contains(&"price".to_string()));
455
456        let doc = Value::from(serde_json::json!({"price": 100.0, "discount": 0.2}));
457        assert_eq!(expr.eval(&doc).unwrap().as_f64(), Some(80.0));
458
459        let doc2 = Value::from(serde_json::json!({"price": 100.0, "discount": 0}));
460        assert_eq!(expr.eval(&doc2).unwrap().as_f64(), Some(100.0));
461    }
462
463    #[test]
464    fn rejects_now() {
465        assert!(parse_generated_expr("NOW()").is_err());
466    }
467
468    #[test]
469    fn rejects_random() {
470        assert!(parse_generated_expr("RANDOM()").is_err());
471    }
472
473    #[test]
474    fn rejects_uuid() {
475        assert!(parse_generated_expr("UUID()").is_err());
476    }
477
478    #[test]
479    fn string_literal() {
480        let (expr, _) = parse_ok("CONCAT(name, ' - ', 'default')");
481        let doc = Value::from(serde_json::json!({"name": "Product"}));
482        assert_eq!(
483            expr.eval(&doc).unwrap(),
484            Value::String("Product - default".into())
485        );
486    }
487
488    #[test]
489    fn null_literal() {
490        let (expr, _) = parse_ok("COALESCE(x, NULL, 0)");
491        let doc = Value::from(serde_json::json!({"x": null}));
492        assert_eq!(expr.eval(&doc).unwrap(), Value::Integer(0));
493    }
494
495    #[test]
496    fn nested_functions() {
497        let (expr, _) = parse_ok("ROUND(price * (1 - COALESCE(discount, 0)), 2)");
498        let doc = Value::from(serde_json::json!({"price": 49.99}));
499        assert_eq!(expr.eval(&doc).unwrap(), Value::Float(49.99));
500    }
501
502    #[test]
503    fn deeply_nested_parentheses_return_error_not_stack_overflow() {
504        let depth = 10_000;
505        let input = format!("{}x{}", "(".repeat(depth), ")".repeat(depth));
506        let result = parse_generated_expr(&input);
507        assert!(
508            result.is_err(),
509            "parse_generated_expr must return Err for {depth}-deep nesting"
510        );
511    }
512
513    #[test]
514    fn cjk_string_in_concat() {
515        let (expr, _) = parse_ok("CONCAT('你好', name)");
516        let doc = Value::from(serde_json::json!({"name": "world"}));
517        assert_eq!(expr.eval(&doc).unwrap(), Value::String("你好world".into()));
518    }
519
520    #[test]
521    fn comparison_with_utf8_literal() {
522        let (expr, deps) = parse_ok("name != '禁止'");
523        assert_eq!(deps, vec!["name"]);
524        let doc = Value::from(serde_json::json!({"name": "allowed"}));
525        assert_eq!(expr.eval(&doc).unwrap(), Value::Bool(true));
526    }
527}
nodedb_query/expr_parse/parser.rs

nodedb_query/expr_parse/
parser.rs
