hayson_engine/query/
parser.rs

1use serde_json::Value;
2
3use crate::errors::HaysonQueryParseError;
4
5use super::planner::QuerySpec;
6use super::predicates::{Combine, ComparisonOp, PredicateNode};
7
8#[derive(Debug, Clone, PartialEq)]
9enum Token {
10    Ident(String),
11    String(String),
12    Number(String),
13    Op(&'static str),
14    LParen,
15    RParen,
16    LBracket,
17    RBracket,
18    Comma,
19    Eof,
20}
21
22#[derive(Debug, Clone, PartialEq)]
23struct Spanned {
24    token: Token,
25    position: usize,
26}
27
28fn err(position: usize, reason: impl Into<String>) -> HaysonQueryParseError {
29    HaysonQueryParseError {
30        position,
31        reason: reason.into(),
32    }
33}
34
35fn tokenize(text: &str) -> Result<Vec<Spanned>, HaysonQueryParseError> {
36    let bytes = text.as_bytes();
37    let mut tokens = Vec::new();
38    let mut i = 0usize;
39    while i < bytes.len() {
40        let c = bytes[i] as char;
41        if c.is_whitespace() {
42            i += 1;
43            continue;
44        }
45        let start = i;
46        match c {
47            '(' => {
48                tokens.push(Spanned {
49                    token: Token::LParen,
50                    position: start,
51                });
52                i += 1;
53            }
54            ')' => {
55                tokens.push(Spanned {
56                    token: Token::RParen,
57                    position: start,
58                });
59                i += 1;
60            }
61            '[' => {
62                tokens.push(Spanned {
63                    token: Token::LBracket,
64                    position: start,
65                });
66                i += 1;
67            }
68            ']' => {
69                tokens.push(Spanned {
70                    token: Token::RBracket,
71                    position: start,
72                });
73                i += 1;
74            }
75            ',' => {
76                tokens.push(Spanned {
77                    token: Token::Comma,
78                    position: start,
79                });
80                i += 1;
81            }
82            '=' => {
83                tokens.push(Spanned {
84                    token: Token::Op("="),
85                    position: start,
86                });
87                i += 1;
88            }
89            '!' => {
90                if bytes.get(i + 1) == Some(&b'=') {
91                    tokens.push(Spanned {
92                        token: Token::Op("!="),
93                        position: start,
94                    });
95                    i += 2;
96                } else {
97                    return Err(err(start, "expected \"!=\", found a bare \"!\""));
98                }
99            }
100            '>' => {
101                if bytes.get(i + 1) == Some(&b'=') {
102                    tokens.push(Spanned {
103                        token: Token::Op(">="),
104                        position: start,
105                    });
106                    i += 2;
107                } else {
108                    tokens.push(Spanned {
109                        token: Token::Op(">"),
110                        position: start,
111                    });
112                    i += 1;
113                }
114            }
115            '<' => {
116                if bytes.get(i + 1) == Some(&b'=') {
117                    tokens.push(Spanned {
118                        token: Token::Op("<="),
119                        position: start,
120                    });
121                    i += 2;
122                } else {
123                    tokens.push(Spanned {
124                        token: Token::Op("<"),
125                        position: start,
126                    });
127                    i += 1;
128                }
129            }
130            '\'' | '"' => {
131                let quote = c;
132                let mut value = String::new();
133                i += 1;
134                let mut closed = false;
135                while i < bytes.len() {
136                    let ch = bytes[i] as char;
137                    if ch == quote {
138                        i += 1;
139                        closed = true;
140                        break;
141                    }
142                    if ch == '\\' && i + 1 < bytes.len() {
143                        value.push(bytes[i + 1] as char);
144                        i += 2;
145                        continue;
146                    }
147                    value.push(ch);
148                    i += 1;
149                }
150                if !closed {
151                    return Err(err(start, "unterminated string literal"));
152                }
153                tokens.push(Spanned {
154                    token: Token::String(value),
155                    position: start,
156                });
157            }
158            _ if c.is_ascii_digit() || (c == '-' && bytes.get(i + 1).is_some_and(u8::is_ascii_digit)) => {
159                let mut end = i + 1;
160                while end < bytes.len() && (bytes[end].is_ascii_digit() || bytes[end] == b'.') {
161                    end += 1;
162                }
163                let slice = &text[start..end];
164                tokens.push(Spanned {
165                    token: Token::Number(slice.to_string()),
166                    position: start,
167                });
168                i = end;
169            }
170            _ if c.is_alphabetic() || c == '_' => {
171                let mut end = i + 1;
172                while end < bytes.len() && ((bytes[end] as char).is_alphanumeric() || bytes[end] == b'_') {
173                    end += 1;
174                }
175                tokens.push(Spanned {
176                    token: Token::Ident(text[start..end].to_string()),
177                    position: start,
178                });
179                i = end;
180            }
181            other => return Err(err(start, format!("unexpected character \"{other}\""))),
182        }
183    }
184    let eof_position = bytes.len();
185    tokens.push(Spanned {
186        token: Token::Eof,
187        position: eof_position,
188    });
189    Ok(tokens)
190}
191
192struct Parser<'a> {
193    tokens: &'a [Spanned],
194    pos: usize,
195}
196
197impl<'a> Parser<'a> {
198    fn peek(&self) -> &Spanned {
199        &self.tokens[self.pos]
200    }
201
202    fn advance(&mut self) -> Spanned {
203        let token = self.tokens[self.pos].clone();
204        if self.pos + 1 < self.tokens.len() {
205            self.pos += 1;
206        }
207        token
208    }
209
210    fn expect_ident_keyword(&mut self, keyword: &str) -> bool {
211        if let Token::Ident(name) = &self.peek().token {
212            if name.eq_ignore_ascii_case(keyword) {
213                self.advance();
214                return true;
215            }
216        }
217        false
218    }
219
220    fn parse_expr(&mut self) -> Result<PredicateNode, HaysonQueryParseError> {
221        let mut terms = vec![self.parse_and()?];
222        while self.expect_ident_keyword("or") {
223            terms.push(self.parse_and()?);
224        }
225        Ok(if terms.len() == 1 {
226            terms.pop().unwrap()
227        } else {
228            PredicateNode::Group {
229                combine: Combine::Or,
230                nodes: terms,
231            }
232        })
233    }
234
235    fn parse_and(&mut self) -> Result<PredicateNode, HaysonQueryParseError> {
236        let mut terms = vec![self.parse_unary()?];
237        while self.expect_ident_keyword("and") {
238            terms.push(self.parse_unary()?);
239        }
240        Ok(if terms.len() == 1 {
241            terms.pop().unwrap()
242        } else {
243            PredicateNode::Group {
244                combine: Combine::And,
245                nodes: terms,
246            }
247        })
248    }
249
250    fn parse_unary(&mut self) -> Result<PredicateNode, HaysonQueryParseError> {
251        if matches!(self.peek().token, Token::LParen) {
252            self.advance();
253            let node = self.parse_expr()?;
254            let closing = self.peek().clone();
255            if !matches!(closing.token, Token::RParen) {
256                return Err(err(
257                    closing.position,
258                    "expected \")\" to close the bracket opened earlier",
259                ));
260            }
261            self.advance();
262            return Ok(node);
263        }
264        self.parse_comparison()
265    }
266
267    fn parse_comparison(&mut self) -> Result<PredicateNode, HaysonQueryParseError> {
268        let field_token = self.peek().clone();
269        let field = match field_token.token {
270            Token::Ident(name) => {
271                self.advance();
272                name
273            }
274            other => {
275                return Err(err(
276                    field_token.position,
277                    format!("expected a field name, found {}", describe(&other)),
278                ))
279            }
280        };
281
282        if self.expect_ident_keyword("in") {
283            let value = self.parse_value()?;
284            if !matches!(value, Value::Array(_)) {
285                return Err(err(
286                    field_token.position,
287                    "\"in\" needs an array of values, e.g. field in [1, 2]",
288                ));
289            }
290            return Ok(PredicateNode::leaf(field, ComparisonOp::In, value));
291        }
292        if self.expect_ident_keyword("contains") {
293            let value = self.parse_value()?;
294            return Ok(PredicateNode::leaf(field, ComparisonOp::Contains, value));
295        }
296        if self.expect_ident_keyword("startswith") {
297            let value = self.parse_value()?;
298            return Ok(PredicateNode::leaf(field, ComparisonOp::StartsWith, value));
299        }
300
301        let op_token = self.peek().clone();
302        let op = match op_token.token {
303            Token::Op("=") => ComparisonOp::Eq,
304            Token::Op("!=") => ComparisonOp::Ne,
305            Token::Op(">") => ComparisonOp::Gt,
306            Token::Op(">=") => ComparisonOp::Gte,
307            Token::Op("<") => ComparisonOp::Lt,
308            Token::Op("<=") => ComparisonOp::Lte,
309            ref other => {
310                return Err(err(
311                    op_token.position,
312                    format!(
313                        "expected a comparison operator (= != > >= < <= in contains startsWith), found {}",
314                        describe(other)
315                    ),
316                ))
317            }
318        };
319        self.advance();
320        let value = self.parse_value()?;
321        Ok(PredicateNode::leaf(field, op, value))
322    }
323
324    fn parse_value(&mut self) -> Result<Value, HaysonQueryParseError> {
325        let token = self.peek().clone();
326        match token.token {
327            Token::String(text) => {
328                self.advance();
329                Ok(Value::String(text))
330            }
331            Token::Number(text) => {
332                self.advance();
333                serde_json::from_str(&text)
334                    .map_err(|_| err(token.position, format!("\"{text}\" is not a valid number")))
335            }
336            Token::Ident(name) if name.eq_ignore_ascii_case("true") => {
337                self.advance();
338                Ok(Value::Bool(true))
339            }
340            Token::Ident(name) if name.eq_ignore_ascii_case("false") => {
341                self.advance();
342                Ok(Value::Bool(false))
343            }
344            Token::Ident(name) if name.eq_ignore_ascii_case("null") => {
345                self.advance();
346                Ok(Value::Null)
347            }
348            Token::LBracket => {
349                self.advance();
350                let mut items = Vec::new();
351                if !matches!(self.peek().token, Token::RBracket) {
352                    items.push(self.parse_value()?);
353                    while matches!(self.peek().token, Token::Comma) {
354                        self.advance();
355                        items.push(self.parse_value()?);
356                    }
357                }
358                let closing = self.peek().clone();
359                if !matches!(closing.token, Token::RBracket) {
360                    return Err(err(closing.position, "expected \"]\" to close the array"));
361                }
362                self.advance();
363                Ok(Value::Array(items))
364            }
365            other => Err(err(
366                token.position,
367                format!(
368                    "expected a value (string, number, true, false, null or array), found {}",
369                    describe(&other)
370                ),
371            )),
372        }
373    }
374}
375
376fn describe(token: &Token) -> String {
377    match token {
378        Token::Ident(name) => format!("identifier \"{name}\""),
379        Token::String(text) => format!("string \"{text}\""),
380        Token::Number(text) => format!("number {text}"),
381        Token::Op(op) => format!("operator \"{op}\""),
382        Token::LParen => "\"(\"".to_string(),
383        Token::RParen => "\")\"".to_string(),
384        Token::LBracket => "\"[\"".to_string(),
385        Token::RBracket => "\"]\"".to_string(),
386        Token::Comma => "\",\"".to_string(),
387        Token::Eof => "end of query".to_string(),
388    }
389}
390
391/// Parses the WHERE-clause fragment of the SQL-like query language from ADR-0009 (cerebro
392/// ADR-6dk7): a predicate expression combining comparisons with `AND`/`OR` and parentheses.
393/// `SELECT`/`FROM`/`JOIN`/`MATCH`/`ORDER BY`/`LIMIT`/`OFFSET` and bound parameters are a separate,
394/// larger piece and are not covered here — see the query module's TODO.
395pub fn parse_query(text: &str) -> Result<QuerySpec, HaysonQueryParseError> {
396    let tokens = tokenize(text)?;
397    let mut parser = Parser {
398        tokens: &tokens,
399        pos: 0,
400    };
401    let root = parser.parse_expr()?;
402    let trailing = parser.peek().clone();
403    if !matches!(trailing.token, Token::Eof) {
404        return Err(err(
405            trailing.position,
406            format!("unexpected {} after a complete expression", describe(&trailing.token)),
407        ));
408    }
409    let root = match root {
410        PredicateNode::Group {
411            combine: Combine::And,
412            nodes,
413        } => PredicateNode::Group {
414            combine: Combine::And,
415            nodes,
416        },
417        other => PredicateNode::Group {
418            combine: Combine::And,
419            nodes: vec![other],
420        },
421    };
422    Ok(QuerySpec::new(root))
423}
424
425#[cfg(test)]
426mod tests {
427    use serde_json::json;
428
429    use super::*;
430    use crate::query::builder::QueryBuilder;
431
432    #[test]
433    fn parses_a_single_comparison() {
434        let spec = parse_query("age >= 30").unwrap();
435        let expected = QueryBuilder::new().r#where("age", ComparisonOp::Gte, json!(30)).spec();
436        assert_eq!(spec, expected);
437    }
438
439    #[test]
440    fn parses_every_comparison_operator() {
441        let cases: &[(&str, ComparisonOp, Value)] = &[
442            ("role = 'admin'", ComparisonOp::Eq, json!("admin")),
443            ("role != 'admin'", ComparisonOp::Ne, json!("admin")),
444            ("age > 30", ComparisonOp::Gt, json!(30)),
445            ("age >= 30", ComparisonOp::Gte, json!(30)),
446            ("age < 30", ComparisonOp::Lt, json!(30)),
447            ("age <= 30", ComparisonOp::Lte, json!(30)),
448            ("age in [1, 2, 3]", ComparisonOp::In, json!([1, 2, 3])),
449            ("tags contains 'go'", ComparisonOp::Contains, json!("go")),
450            ("name startsWith 'An'", ComparisonOp::StartsWith, json!("An")),
451        ];
452        for (text, op, value) in cases {
453            let spec = parse_query(text).unwrap();
454            let field = text.split_whitespace().next().unwrap();
455            let expected = QueryBuilder::new().r#where(field, *op, value.clone()).spec();
456            assert_eq!(spec, expected, "mismatch for {text:?}");
457        }
458    }
459
460    #[test]
461    fn flat_and_matches_chained_where() {
462        let spec = parse_query("role = 'admin' AND age > 30").unwrap();
463        let expected = QueryBuilder::new()
464            .r#where("role", ComparisonOp::Eq, json!("admin"))
465            .r#where("age", ComparisonOp::Gt, json!(30))
466            .spec();
467        assert_eq!(spec, expected);
468    }
469
470    #[test]
471    fn and_inside_or_bracket_matches_where_any_where_all() {
472        let text = "role = 'admin' OR (role = 'user' AND age > 35)";
473        let spec = parse_query(text).unwrap();
474        let expected = QueryBuilder::new()
475            .where_any(|group| {
476                group
477                    .r#where("role", ComparisonOp::Eq, json!("admin"))
478                    .where_all(|inner| {
479                        inner.r#where("role", ComparisonOp::Eq, json!("user")).r#where(
480                            "age",
481                            ComparisonOp::Gt,
482                            json!(35),
483                        );
484                    });
485            })
486            .spec();
487        assert_eq!(spec, expected);
488    }
489
490    #[test]
491    fn or_bracket_inside_flat_and_matches_where_then_where_any() {
492        let text = "role = 'user' AND (tags contains 'go' OR tags contains 'node')";
493        let spec = parse_query(text).unwrap();
494        let expected = QueryBuilder::new()
495            .r#where("role", ComparisonOp::Eq, json!("user"))
496            .where_any(|group| {
497                group.r#where("tags", ComparisonOp::Contains, json!("go")).r#where(
498                    "tags",
499                    ComparisonOp::Contains,
500                    json!("node"),
501                );
502            })
503            .spec();
504        assert_eq!(spec, expected);
505    }
506
507    #[test]
508    fn rejects_garbage_with_a_positioned_error() {
509        let error = parse_query("age >=").unwrap_err();
510        assert_eq!(error.position, 6);
511
512        let error = parse_query("age 30").unwrap_err();
513        assert!(error.reason.contains("comparison operator"));
514
515        let error = parse_query("age >= 30 age").unwrap_err();
516        assert!(error.reason.contains("unexpected"));
517
518        let error = parse_query("(age >= 30").unwrap_err();
519        assert!(error.reason.contains("\")\""));
520
521        let error = parse_query("age in 30").unwrap_err();
522        assert!(error.reason.contains("array"));
523    }
524
525    #[test]
526    fn error_display_carries_position_and_reason() {
527        let error = parse_query("").unwrap_err();
528        let message = error.to_string();
529        assert!(message.contains("position"));
530        assert!(message.contains(&error.reason));
531    }
532}
hayson_engine/query/parser.rs

hayson_engine/query/
parser.rs
