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

eventql_parser/
parser.rs
