eventql-parser 0.1.16

//! Syntactic analysis (parsing) for EventQL.
//!
//! This module provides the parser that converts a sequence of tokens into
//! an abstract syntax tree (AST). The parser implements a recursive descent
//! parser with operator precedence for expressions.
//!
//! # Main Function
//!
//! - [`parse`] - Convert a slice of tokens into a Query AST

use crate::arena::Arena;
use crate::ast::{
    Access, App, Attrs, Binary, Field, Limit, Order, OrderBy, Query, Source, SourceKind, Unary,
    Value,
};
use crate::error::ParserError;
use crate::token::{Operator, Sym, Symbol, Token};
use crate::{Binding, ExprRef, GroupBy, Raw, StrRef};

/// Result type for parser operations.
///
/// This is a convenience alias for `Result<T, ParserError>`.
pub type ParseResult<A> = Result<A, ParserError>;

/// A parser for EventQL expressions and queries.
///
/// The parser takes a stream of tokens and builds an abstract syntax tree (AST)
/// representing the structure of the EventQL query or expression.
pub struct Parser<'a> {
    input: &'a [Token<'a>],
    arena: &'a mut Arena,
    offset: usize,
}

impl<'a> Parser<'a> {
    /// Creates a new parser from a slice of tokens.
    ///
    /// # Example
    ///
    /// ```rust
    /// use eventql_parser::Session;
    ///
    /// let session = Session::builder().build();
    /// let tokens = session.tokenize("1 + 2").unwrap();
    /// ```
    pub fn new(arena: &'a mut Arena, input: &'a [Token<'a>]) -> Self {
        Self {
            arena,
            input,
            offset: 0,
        }
    }

    fn peek<'b>(&'b self) -> Token<'a> {
        self.input[self.offset]
    }

    fn shift<'b>(&'b mut self) -> Token<'a> {
        let res = self.input[self.offset];

        if self.offset + 1 < self.input.len() {
            self.offset += 1;
        }

        res
    }

    fn parse_ident(&mut self) -> ParseResult<StrRef> {
        let token = self.shift();

        if let Sym::Id(id) = token.sym {
            return Ok(self.arena.strings.alloc(id));
        }

        Err(ParserError::ExpectedIdent(
            token.line,
            token.col,
            token.sym.to_string(),
        ))
    }

    fn parse_source_kind(&mut self) -> ParseResult<SourceKind<Raw>> {
        let token = self.shift();
        match token.sym {
            Sym::Id(id) => Ok(SourceKind::Name(self.arena.strings.alloc_no_case(id))),
            Sym::String(sub) => Ok(SourceKind::Subject(self.arena.strings.alloc(sub))),
            Sym::Symbol(Symbol::OpenParen) => {
                let query = self.parse_query()?;
                expect_symbol(self.shift(), Symbol::CloseParen)?;

                Ok(SourceKind::Subquery(Box::new(query)))
            }
            _ => Err(ParserError::UnexpectedToken(
                token.line,
                token.col,
                token.sym.to_string(),
            )),
        }
    }

    fn parse_source(&mut self) -> ParseResult<Source<Raw>> {
        expect_keyword(self.shift(), "from")?;

        let token = self.shift();
        let binding = if let Sym::Id(name) = token.sym {
            let name = self.arena.strings.alloc_no_case(name);

            Binding {
                name,
                pos: token.into(),
            }
        } else {
            return Err(ParserError::ExpectedIdent(
                token.line,
                token.col,
                token.sym.to_string(),
            ));
        };

        expect_keyword(self.shift(), "in")?;
        let kind = self.parse_source_kind()?;

        Ok(Source { binding, kind })
    }

    fn parse_where_clause(&mut self) -> ParseResult<ExprRef> {
        expect_keyword(self.shift(), "where")?;
        self.parse_expr()
    }

    fn parse_group_by(&mut self) -> ParseResult<GroupBy> {
        expect_keyword(self.shift(), "group")?;
        expect_keyword(self.shift(), "by")?;

        let expr = self.parse_expr()?;

        let predicate = if let Sym::Id(name) = self.peek().sym
            && name.eq_ignore_ascii_case("having")
        {
            self.shift();

            Some(self.parse_expr()?)
        } else {
            None
        };

        Ok(GroupBy { expr, predicate })
    }

    fn parse_order_by(&mut self) -> ParseResult<OrderBy> {
        expect_keyword(self.shift(), "order")?;
        expect_keyword(self.shift(), "by")?;

        let expr = self.parse_expr()?;
        let token = self.peek();

        if let Sym::Id(name) = token.sym {
            let order = if name.eq_ignore_ascii_case("asc") {
                self.shift();
                Order::Asc
            } else if name.eq_ignore_ascii_case("desc") {
                self.shift();
                Order::Desc
            } else {
                Order::Asc
            };

            return Ok(OrderBy { expr, order });
        }

        Err(ParserError::UnexpectedToken(
            token.line,
            token.col,
            token.sym.to_string(),
        ))
    }

    fn parse_limit(&mut self) -> ParseResult<Limit> {
        let token = self.shift();
        let limit = expect_keyword(token, "top")
            .map(|_| "top")
            .or_else(|_| expect_keyword(token, "skip").map(|_| "skip"))
            .map_err(|_| {
                ParserError::UnexpectedToken(token.line, token.col, token.sym.to_string())
            })?;

        let token = self.shift();
        if let Sym::Number(value) = token.sym
            && value.fract() == 0.0
        {
            return match limit {
                "top" => Ok(Limit::Top(value as u64)),
                "skip" => Ok(Limit::Skip(value as u64)),
                _ => unreachable!(),
            };
        }

        Err(ParserError::UnexpectedToken(
            token.line,
            token.col,
            token.sym.to_string(),
        ))
    }

    /// Parses a single expression from the token stream.
    ///
    /// This method can be used to parse individual expressions rather than complete queries.
    /// It's useful for testing or for parsing expression fragments.
    ///
    /// # Returns
    ///
    /// Returns the parsed expression, or a parse error if the tokens don't form a valid expression.
    ///
    /// # Example
    ///
    /// ```rust
    /// use eventql_parser::Session;
    ///
    /// let session = Session::builder().build();
    /// let tokens = session.tokenize("NOW()").unwrap();
    /// ```
    pub fn parse_expr(&mut self) -> ParseResult<ExprRef> {
        let token = self.peek();

        match token.sym {
            Sym::Eof => Err(ParserError::UnexpectedEof),

            Sym::Id(_)
            | Sym::String(_)
            | Sym::Number(_)
            | Sym::Symbol(Symbol::OpenParen | Symbol::OpenBracket | Symbol::OpenBrace)
            | Sym::Operator(Operator::Add | Operator::Sub | Operator::Not) => self.parse_binary(0),

            _ => Err(ParserError::UnexpectedToken(
                token.line,
                token.col,
                token.sym.to_string(),
            )),
        }
    }

    fn parse_primary(&mut self) -> ParseResult<ExprRef> {
        let token = self.shift();

        let value = match token.sym {
            Sym::Id(name) => {
                if name.eq_ignore_ascii_case("true") {
                    Value::Bool(true)
                } else if name.eq_ignore_ascii_case("false") {
                    Value::Bool(false)
                } else if matches!(self.peek().sym, Sym::Symbol(Symbol::OpenParen)) {
                    self.shift();

                    let mut args = vec![];

                    if !matches!(self.peek().sym, Sym::Symbol(Symbol::CloseParen)) {
                        args.push(self.parse_expr()?);

                        while matches!(self.peek().sym, Sym::Symbol(Symbol::Comma)) {
                            self.shift();
                            args.push(self.parse_expr()?);
                        }
                    }

                    expect_symbol(self.shift(), Symbol::CloseParen)?;
                    let args = self.arena.exprs.alloc_vec(args);

                    Value::App(App {
                        func: self.arena.strings.alloc_no_case(name),
                        args,
                    })
                } else if matches!(self.peek().sym, Sym::Symbol(Symbol::Dot)) {
                    self.shift();
                    let attrs = token.into();
                    let name = self.arena.strings.alloc_no_case(name);
                    let mut access = Access {
                        target: self.arena.exprs.alloc(attrs, Value::Id(name)),
                        field: self.parse_ident()?,
                    };

                    while matches!(self.peek().sym, Sym::Symbol(Symbol::Dot)) {
                        self.shift();
                        access = Access {
                            target: self.arena.exprs.alloc(attrs, Value::Access(access)),
                            field: self.parse_ident()?,
                        };
                    }

                    Value::Access(access)
                } else {
                    Value::Id(self.arena.strings.alloc_no_case(name))
                }
            }

            Sym::String(s) => Value::String(self.arena.strings.alloc(s)),
            Sym::Number(n) => Value::Number(n.into()),

            Sym::Symbol(Symbol::OpenParen) => {
                let expr = self.parse_expr()?;
                expect_symbol(self.shift(), Symbol::CloseParen)?;

                Value::Group(expr)
            }

            Sym::Symbol(Symbol::OpenBracket) => {
                let mut elems = vec![];

                if !matches!(self.peek().sym, Sym::Symbol(Symbol::CloseBracket)) {
                    elems.push(self.parse_expr()?);

                    while matches!(self.peek().sym, Sym::Symbol(Symbol::Comma)) {
                        self.shift();
                        elems.push(self.parse_expr()?);
                    }
                }

                expect_symbol(self.shift(), Symbol::CloseBracket)?;

                Value::Array(self.arena.exprs.alloc_vec(elems))
            }

            Sym::Symbol(Symbol::OpenBrace) => {
                let mut fields = vec![];

                if !matches!(self.peek().sym, Sym::Symbol(Symbol::CloseBrace)) {
                    let attrs: Attrs = self.peek().into();
                    let name = self.parse_ident()?;
                    expect_symbol(self.shift(), Symbol::Colon)?;
                    let value = self.parse_expr()?;

                    fields.push(Field {
                        attrs,
                        name,
                        expr: value,
                    });

                    while matches!(self.peek().sym, Sym::Symbol(Symbol::Comma)) {
                        self.shift();

                        let attrs: Attrs = self.peek().into();
                        let name = self.parse_ident()?;
                        expect_symbol(self.shift(), Symbol::Colon)?;
                        let value = self.parse_expr()?;

                        fields.push(Field {
                            attrs,
                            name,
                            expr: value,
                        });
                    }
                }

                expect_symbol(self.shift(), Symbol::CloseBrace)?;

                Value::Record(self.arena.exprs.alloc_rec(fields))
            }

            Sym::Operator(op) if matches!(op, Operator::Add | Operator::Sub | Operator::Not) => {
                Value::Unary(Unary {
                    operator: op,
                    expr: self.parse_expr()?,
                })
            }

            _ => {
                return Err(ParserError::UnexpectedToken(
                    token.line,
                    token.col,
                    token.sym.to_string(),
                ));
            }
        };

        let attrs = token.into();

        Ok(self.arena.exprs.alloc(attrs, value))
    }

    fn parse_binary(&mut self, min_bind: u64) -> ParseResult<ExprRef> {
        let mut lhs = self.parse_primary()?;
        let lhs_attrs = self.arena.exprs.get(lhs).attrs;

        loop {
            let token = self.peek();
            let operator = if let Sym::Operator(op) = token.sym {
                op
            } else {
                break;
            };

            let (lhs_bind, rhs_bind) = binding_pow(operator);

            if lhs_bind < min_bind {
                break;
            }

            self.shift();
            let rhs = self.parse_binary(rhs_bind)?;
            let node = self.arena.exprs.get(rhs);

            if matches!(operator, Operator::As) && !matches!(node.value, Value::Id(_)) {
                return Err(ParserError::ExpectedType(
                    node.attrs.pos.line,
                    node.attrs.pos.col,
                ));
            }

            lhs = self
                .arena
                .exprs
                .alloc(lhs_attrs, Value::Binary(Binary { lhs, operator, rhs }));
        }

        Ok(lhs)
    }

    fn parse_query(&mut self) -> ParseResult<Query<Raw>> {
        let mut sources = vec![];
        let pos = self.peek().into();

        while let Sym::Id(name) = self.peek().sym
            && name.eq_ignore_ascii_case("from")
        {
            sources.push(self.parse_source()?);
        }

        if sources.is_empty() {
            let token = self.peek();
            return Err(ParserError::MissingFromStatement(token.line, token.col));
        }

        let predicate = if let Sym::Id(name) = self.peek().sym
            && name.eq_ignore_ascii_case("where")
        {
            Some(self.parse_where_clause()?)
        } else {
            None
        };

        let group_by = if let Sym::Id(name) = self.peek().sym
            && name.eq_ignore_ascii_case("group")
        {
            Some(self.parse_group_by()?)
        } else {
            None
        };

        let order_by = if let Sym::Id(name) = self.peek().sym
            && name.eq_ignore_ascii_case("order")
        {
            Some(self.parse_order_by()?)
        } else {
            None
        };

        let limit = if let Sym::Id(name) = self.peek().sym
            && (name.eq_ignore_ascii_case("skip") || name.eq_ignore_ascii_case("top"))
        {
            Some(self.parse_limit()?)
        } else {
            None
        };

        expect_keyword(self.shift(), "project")?;
        expect_keyword(self.shift(), "into")?;

        let distinct = if let Sym::Id(name) = self.peek().sym
            && name.eq_ignore_ascii_case("distinct")
        {
            self.shift();
            true
        } else {
            false
        };

        let projection = self.parse_expr()?;

        Ok(Query {
            attrs: Attrs::new(pos),
            sources,
            predicate,
            group_by,
            order_by,
            limit,
            projection,
            distinct,
            meta: Raw,
        })
    }
}

fn expect_keyword(token: Token, keyword: &'static str) -> ParseResult<()> {
    if let Sym::Id(id) = token.sym
        && id.eq_ignore_ascii_case(keyword)
    {
        return Ok(());
    }

    Err(ParserError::ExpectedKeyword(
        token.line,
        token.col,
        keyword,
        token.sym.to_string(),
    ))
}

fn expect_symbol(token: Token, expect: Symbol) -> ParseResult<()> {
    if let Sym::Symbol(sym) = token.sym
        && sym == expect
    {
        return Ok(());
    }

    Err(ParserError::ExpectedSymbol(
        token.line,
        token.col,
        expect,
        token.sym.to_string(),
    ))
}

// Pratt parser operator binding power (precedence)
fn binding_pow(op: Operator) -> (u64, u64) {
    match op {
        Operator::Add | Operator::Sub => (20, 21),
        Operator::Mul | Operator::Div => (30, 31),
        Operator::Contains => (40, 39),
        Operator::As => (50, 49),
        Operator::Eq
        | Operator::Neq
        | Operator::Gt
        | Operator::Lt
        | Operator::Gte
        | Operator::Lte => (10, 11),
        Operator::And | Operator::Or | Operator::Xor | Operator::Not => (1, 2),
    }
}

/// Parse a sequence of tokens into a Query AST.
///
/// This function performs syntactic analysis on the token stream, constructing
/// an abstract syntax tree that represents the structure of the EventQL query.
///
/// # Grammar
///
/// The parser recognizes the following EventQL grammar:
///
/// ```text
/// Query     := FROM+ WHERE? GROUP_BY? ORDER_BY? LIMIT? PROJECT
/// FROM      := "FROM" Id "IN" SourceKind
/// SourceKind := Id | String | "(" Query ")"
/// WHERE     := "WHERE" Expr
/// GROUP_BY  := "GROUP" "BY" Expr
/// ORDER_BY  := "ORDER" "BY" Expr ("ASC" | "DESC")
/// LIMIT     := ("TOP" | "SKIP") Number
/// PROJECT   := "PROJECT" "INTO" Expr
/// Expr      := Binary | Unary | Primary
/// Primary   := Number | String | Bool | Id | Array | Record | Access | App | "(" Expr ")"
/// ```
///
/// # Expression Precedence
///
/// The parser uses a Pratt parser for expressions with the following precedence
/// (from highest to lowest):
///
/// 1. Unary operators (`+`, `-`, `NOT`)
/// 2. Multiplicative (`*`, `/`)
/// 3. Additive (`+`, `-`)
/// 4. Comparison (`<`, `<=`, `>`, `>=`, `==`, `!=`)
/// 5. Logical (`AND`, `OR`, `XOR`)
pub(crate) fn parse<'a>(arena: &'a mut Arena, input: &'a [Token<'a>]) -> ParseResult<Query<Raw>> {
    let mut parser = Parser::new(arena, input);

    parser.parse_query()
}