eventql_parser/
parser.rs

1//! Syntactic analysis (parsing) for EventQL.
2//!
3//! This module provides the parser that converts a sequence of tokens into
4//! an abstract syntax tree (AST). The parser implements a recursive descent
5//! parser with operator precedence for expressions.
6//!
7//! # Main Function
8//!
9//! - [`parse`] - Convert a slice of tokens into a Query AST
10
11use crate::ast::{
12    Access, App, Attrs, Binary, Expr, Field, Limit, Order, OrderBy, Query, Source, SourceKind,
13    Unary, Value,
14};
15use crate::error::ParserError;
16use crate::token::{Operator, Sym, Symbol, Token};
17use crate::{Binding, GroupBy, Raw};
18
19/// Result type for parser operations.
20///
21/// This is a convenience alias for `Result<T, ParserError>`.
22pub type ParseResult<A> = Result<A, ParserError>;
23
24/// A parser for EventQL expressions and queries.
25///
26/// The parser takes a stream of tokens and builds an abstract syntax tree (AST)
27/// representing the structure of the EventQL query or expression.
28pub struct Parser<'a> {
29    input: &'a [Token<'a>],
30    offset: usize,
31}
32
33impl<'a> Parser<'a> {
34    /// Creates a new parser from a slice of tokens.
35    ///
36    /// # Example
37    ///
38    /// ```rust
39    /// use eventql_parser::prelude::{tokenize, Parser};
40    ///
41    /// let tokens = tokenize("1 + 2").unwrap();
42    /// let parser = Parser::new(tokens.as_slice());
43    /// ```
44    pub fn new(input: &'a [Token<'a>]) -> Self {
45        Self { input, offset: 0 }
46    }
47
48    fn peek<'b>(&'b self) -> Token<'a> {
49        self.input[self.offset]
50    }
51
52    fn shift<'b>(&'b mut self) -> Token<'a> {
53        let res = self.input[self.offset];
54
55        if self.offset + 1 < self.input.len() {
56            self.offset += 1;
57        }
58
59        res
60    }
61
62    fn parse_ident(&mut self) -> ParseResult<String> {
63        let token = self.shift();
64
65        if let Sym::Id(id) = token.sym {
66            return Ok(id.to_owned());
67        }
68
69        Err(ParserError::ExpectedIdent(
70            token.line,
71            token.col,
72            token.sym.to_string(),
73        ))
74    }
75
76    fn parse_source_kind(&mut self) -> ParseResult<SourceKind<Raw>> {
77        let token = self.shift();
78        match token.sym {
79            Sym::Id(id) => Ok(SourceKind::Name(id.to_owned())),
80            Sym::String(sub) => Ok(SourceKind::Subject(sub.to_owned())),
81            Sym::Symbol(Symbol::OpenParen) => {
82                let query = self.parse_query()?;
83                expect_symbol(self.shift(), Symbol::CloseParen)?;
84
85                Ok(SourceKind::Subquery(Box::new(query)))
86            }
87            _ => Err(ParserError::UnexpectedToken(
88                token.line,
89                token.col,
90                token.sym.to_string(),
91            )),
92        }
93    }
94
95    fn parse_source(&mut self) -> ParseResult<Source<Raw>> {
96        expect_keyword(self.shift(), "from")?;
97
98        let token = self.shift();
99        let binding = if let Sym::Id(name) = token.sym {
100            Binding {
101                name: name.to_owned(),
102                pos: token.into(),
103            }
104        } else {
105            return Err(ParserError::ExpectedIdent(
106                token.line,
107                token.col,
108                token.sym.to_string(),
109            ));
110        };
111
112        expect_keyword(self.shift(), "in")?;
113        let kind = self.parse_source_kind()?;
114
115        Ok(Source { binding, kind })
116    }
117
118    fn parse_where_clause(&mut self) -> ParseResult<Expr> {
119        expect_keyword(self.shift(), "where")?;
120        self.parse_expr()
121    }
122
123    fn parse_group_by(&mut self) -> ParseResult<GroupBy> {
124        expect_keyword(self.shift(), "group")?;
125        expect_keyword(self.shift(), "by")?;
126
127        let expr = self.parse_expr()?;
128
129        let predicate = if let Sym::Id(name) = self.peek().sym
130            && name.eq_ignore_ascii_case("having")
131        {
132            self.shift();
133
134            Some(self.parse_expr()?)
135        } else {
136            None
137        };
138
139        Ok(GroupBy { expr, predicate })
140    }
141
142    fn parse_order_by(&mut self) -> ParseResult<OrderBy> {
143        expect_keyword(self.shift(), "order")?;
144        expect_keyword(self.shift(), "by")?;
145
146        let expr = self.parse_expr()?;
147        let token = self.shift();
148
149        if let Sym::Id(name) = token.sym {
150            let order = if name.eq_ignore_ascii_case("asc") {
151                Order::Asc
152            } else if name.eq_ignore_ascii_case("desc") {
153                Order::Desc
154            } else {
155                return Err(ParserError::UnexpectedToken(
156                    token.line,
157                    token.col,
158                    name.to_owned(),
159                ));
160            };
161
162            return Ok(OrderBy { expr, order });
163        }
164
165        Err(ParserError::UnexpectedToken(
166            token.line,
167            token.col,
168            token.sym.to_string(),
169        ))
170    }
171
172    fn parse_limit(&mut self) -> ParseResult<Limit> {
173        let token = self.shift();
174        let limit = expect_keyword(token, "top")
175            .map(|_| "top")
176            .or_else(|_| expect_keyword(token, "skip").map(|_| "skip"))
177            .map_err(|_| {
178                ParserError::UnexpectedToken(token.line, token.col, token.sym.to_string())
179            })?;
180
181        let token = self.shift();
182        if let Sym::Number(value) = token.sym
183            && value.fract() == 0.0
184        {
185            return match limit {
186                "top" => Ok(Limit::Top(value as u64)),
187                "skip" => Ok(Limit::Skip(value as u64)),
188                _ => unreachable!(),
189            };
190        }
191
192        Err(ParserError::UnexpectedToken(
193            token.line,
194            token.col,
195            token.sym.to_string(),
196        ))
197    }
198
199    /// Parses a single expression from the token stream.
200    ///
201    /// This method can be used to parse individual expressions rather than complete queries.
202    /// It's useful for testing or for parsing expression fragments.
203    ///
204    /// # Returns
205    ///
206    /// Returns the parsed expression, or a parse error if the tokens don't form a valid expression.
207    ///
208    /// # Example
209    ///
210    /// ```rust
211    /// use eventql_parser::prelude::{tokenize, Parser};
212    ///
213    /// let tokens = tokenize("NOW()").unwrap();
214    /// let expr = Parser::new(tokens.as_slice()).parse_expr().unwrap();
215    /// ```
216    pub fn parse_expr(&mut self) -> ParseResult<Expr> {
217        let token = self.peek();
218
219        match token.sym {
220            Sym::Eof => Err(ParserError::UnexpectedEof),
221
222            Sym::Id(_)
223            | Sym::String(_)
224            | Sym::Number(_)
225            | Sym::Symbol(Symbol::OpenParen | Symbol::OpenBracket | Symbol::OpenBrace)
226            | Sym::Operator(Operator::Add | Operator::Sub | Operator::Not) => self.parse_binary(0),
227
228            _ => Err(ParserError::UnexpectedToken(
229                token.line,
230                token.col,
231                token.sym.to_string(),
232            )),
233        }
234    }
235
236    fn parse_primary(&mut self) -> ParseResult<Expr> {
237        let token = self.shift();
238
239        let value = match token.sym {
240            Sym::Id(name) => {
241                if name.eq_ignore_ascii_case("true") {
242                    Value::Bool(true)
243                } else if name.eq_ignore_ascii_case("false") {
244                    Value::Bool(false)
245                } else if matches!(self.peek().sym, Sym::Symbol(Symbol::OpenParen)) {
246                    self.shift();
247
248                    let mut args = vec![];
249
250                    if !matches!(self.peek().sym, Sym::Symbol(Symbol::CloseParen)) {
251                        args.push(self.parse_expr()?);
252
253                        while matches!(self.peek().sym, Sym::Symbol(Symbol::Comma)) {
254                            self.shift();
255                            args.push(self.parse_expr()?);
256                        }
257                    }
258
259                    expect_symbol(self.shift(), Symbol::CloseParen)?;
260
261                    Value::App(App {
262                        func: name.to_owned(),
263                        args,
264                    })
265                } else if matches!(self.peek().sym, Sym::Symbol(Symbol::Dot)) {
266                    self.shift();
267                    let mut access = Access {
268                        target: Box::new(Expr {
269                            attrs: Attrs::new(token.into()),
270                            value: Value::Id(name.to_owned()),
271                        }),
272                        field: self.parse_ident()?,
273                    };
274
275                    while matches!(self.peek().sym, Sym::Symbol(Symbol::Dot)) {
276                        self.shift();
277                        access = Access {
278                            target: Box::new(Expr {
279                                attrs: access.target.attrs,
280                                value: Value::Access(access),
281                            }),
282                            field: self.parse_ident()?,
283                        };
284                    }
285
286                    Value::Access(access)
287                } else {
288                    Value::Id(name.to_owned())
289                }
290            }
291
292            Sym::String(s) => Value::String(s.to_owned()),
293            Sym::Number(n) => Value::Number(n),
294
295            Sym::Symbol(Symbol::OpenParen) => {
296                let expr = self.parse_expr()?;
297                expect_symbol(self.shift(), Symbol::CloseParen)?;
298
299                Value::Group(Box::new(expr))
300            }
301
302            Sym::Symbol(Symbol::OpenBracket) => {
303                let mut elems = vec![];
304
305                if !matches!(self.peek().sym, Sym::Symbol(Symbol::CloseBracket)) {
306                    elems.push(self.parse_expr()?);
307
308                    while matches!(self.peek().sym, Sym::Symbol(Symbol::Comma)) {
309                        self.shift();
310                        elems.push(self.parse_expr()?);
311                    }
312                }
313
314                expect_symbol(self.shift(), Symbol::CloseBracket)?;
315
316                Value::Array(elems)
317            }
318
319            Sym::Symbol(Symbol::OpenBrace) => {
320                let mut fields = vec![];
321
322                if !matches!(self.peek().sym, Sym::Symbol(Symbol::CloseBrace)) {
323                    let name = self.parse_ident()?;
324                    expect_symbol(self.shift(), Symbol::Colon)?;
325                    let value = self.parse_expr()?;
326
327                    fields.push(Field { name, value });
328
329                    while matches!(self.peek().sym, Sym::Symbol(Symbol::Comma)) {
330                        self.shift();
331
332                        let name = self.parse_ident()?;
333                        expect_symbol(self.shift(), Symbol::Colon)?;
334                        let value = self.parse_expr()?;
335
336                        fields.push(Field { name, value });
337                    }
338                }
339
340                expect_symbol(self.shift(), Symbol::CloseBrace)?;
341
342                Value::Record(fields)
343            }
344
345            Sym::Operator(op) if matches!(op, Operator::Add | Operator::Sub | Operator::Not) => {
346                Value::Unary(Unary {
347                    operator: op,
348                    expr: Box::new(self.parse_expr()?),
349                })
350            }
351
352            _ => {
353                return Err(ParserError::UnexpectedToken(
354                    token.line,
355                    token.col,
356                    token.sym.to_string(),
357                ));
358            }
359        };
360
361        Ok(Expr {
362            attrs: Attrs::new(token.into()),
363            value,
364        })
365    }
366
367    fn parse_binary(&mut self, min_bind: u64) -> ParseResult<Expr> {
368        let mut lhs = self.parse_primary()?;
369
370        loop {
371            let token = self.peek();
372            let operator = if let Sym::Operator(op) = token.sym {
373                op
374            } else {
375                break;
376            };
377
378            let (lhs_bind, rhs_bind) = binding_pow(operator);
379
380            if lhs_bind < min_bind {
381                break;
382            }
383
384            self.shift();
385            let rhs = self.parse_binary(rhs_bind)?;
386
387            if matches!(operator, Operator::As) && !matches!(rhs.value, Value::Id(_)) {
388                return Err(ParserError::ExpectedType(
389                    rhs.attrs.pos.line,
390                    rhs.attrs.pos.col,
391                ));
392            }
393
394            lhs = Expr {
395                attrs: lhs.attrs,
396                value: Value::Binary(Binary {
397                    lhs: Box::new(lhs),
398                    operator,
399                    rhs: Box::new(rhs),
400                }),
401            };
402        }
403
404        Ok(lhs)
405    }
406
407    fn parse_query(&mut self) -> ParseResult<Query<Raw>> {
408        let mut sources = vec![];
409        let pos = self.peek().into();
410
411        while let Sym::Id(name) = self.peek().sym
412            && name.eq_ignore_ascii_case("from")
413        {
414            sources.push(self.parse_source()?);
415        }
416
417        if sources.is_empty() {
418            let token = self.peek();
419            return Err(ParserError::MissingFromStatement(token.line, token.col));
420        }
421
422        let predicate = if let Sym::Id(name) = self.peek().sym
423            && name.eq_ignore_ascii_case("where")
424        {
425            Some(self.parse_where_clause()?)
426        } else {
427            None
428        };
429
430        let group_by = if let Sym::Id(name) = self.peek().sym
431            && name.eq_ignore_ascii_case("group")
432        {
433            Some(self.parse_group_by()?)
434        } else {
435            None
436        };
437
438        let order_by = if let Sym::Id(name) = self.peek().sym
439            && name.eq_ignore_ascii_case("order")
440        {
441            Some(self.parse_order_by()?)
442        } else {
443            None
444        };
445
446        let limit = if let Sym::Id(name) = self.peek().sym
447            && (name.eq_ignore_ascii_case("skip") || name.eq_ignore_ascii_case("top"))
448        {
449            Some(self.parse_limit()?)
450        } else {
451            None
452        };
453
454        expect_keyword(self.shift(), "project")?;
455        expect_keyword(self.shift(), "into")?;
456
457        let distinct = if let Sym::Id(name) = self.peek().sym
458            && name.eq_ignore_ascii_case("distinct")
459        {
460            self.shift();
461            true
462        } else {
463            false
464        };
465
466        let projection = self.parse_expr()?;
467
468        Ok(Query {
469            attrs: Attrs::new(pos),
470            sources,
471            predicate,
472            group_by,
473            order_by,
474            limit,
475            projection,
476            distinct,
477            meta: Raw,
478        })
479    }
480}
481
482fn expect_keyword(token: Token, keyword: &'static str) -> ParseResult<()> {
483    if let Sym::Id(id) = token.sym
484        && id.eq_ignore_ascii_case(keyword)
485    {
486        return Ok(());
487    }
488
489    Err(ParserError::ExpectedKeyword(
490        token.line,
491        token.col,
492        keyword,
493        token.sym.to_string(),
494    ))
495}
496
497fn expect_symbol(token: Token, expect: Symbol) -> ParseResult<()> {
498    if let Sym::Symbol(sym) = token.sym
499        && sym == expect
500    {
501        return Ok(());
502    }
503
504    Err(ParserError::ExpectedSymbol(
505        token.line,
506        token.col,
507        expect,
508        token.sym.to_string(),
509    ))
510}
511
512// Pratt parser operator binding power (precedence)
513fn binding_pow(op: Operator) -> (u64, u64) {
514    match op {
515        Operator::Add | Operator::Sub => (20, 21),
516        Operator::Mul | Operator::Div => (30, 31),
517        Operator::Contains => (40, 39),
518        Operator::As => (50, 49),
519        Operator::Eq
520        | Operator::Neq
521        | Operator::Gt
522        | Operator::Lt
523        | Operator::Gte
524        | Operator::Lte => (10, 11),
525        Operator::And | Operator::Or | Operator::Xor | Operator::Not => (1, 2),
526    }
527}
528
529/// Parse a sequence of tokens into a Query AST.
530///
531/// This function performs syntactic analysis on the token stream, constructing
532/// an abstract syntax tree that represents the structure of the EventQL query.
533///
534/// # Grammar
535///
536/// The parser recognizes the following EventQL grammar:
537///
538/// ```text
539/// Query     := FROM+ WHERE? GROUP_BY? ORDER_BY? LIMIT? PROJECT
540/// FROM      := "FROM" Id "IN" SourceKind
541/// SourceKind := Id | String | "(" Query ")"
542/// WHERE     := "WHERE" Expr
543/// GROUP_BY  := "GROUP" "BY" Expr
544/// ORDER_BY  := "ORDER" "BY" Expr ("ASC" | "DESC")
545/// LIMIT     := ("TOP" | "SKIP") Number
546/// PROJECT   := "PROJECT" "INTO" Expr
547/// Expr      := Binary | Unary | Primary
548/// Primary   := Number | String | Bool | Id | Array | Record | Access | App | "(" Expr ")"
549/// ```
550///
551/// # Expression Precedence
552///
553/// The parser uses a Pratt parser for expressions with the following precedence
554/// (from highest to lowest):
555///
556/// 1. Unary operators (`+`, `-`, `NOT`)
557/// 2. Multiplicative (`*`, `/`)
558/// 3. Additive (`+`, `-`)
559/// 4. Comparison (`<`, `<=`, `>`, `>=`, `==`, `!=`)
560/// 5. Logical (`AND`, `OR`, `XOR`)
561pub fn parse<'a>(input: &'a [Token<'a>]) -> ParseResult<Query<Raw>> {
562    let mut parser = Parser::new(input);
563
564    parser.parse_query()
565}
eventql_parser/parser.rs

eventql_parser/
parser.rs
