src/filter/dsl/parser/grammar.rs

//! Recursive-descent grammar for the filter DSL.
//!
//! Precedence (lowest to highest):
//!
//! ```text
//! expr     := or_expr
//! or_expr  := and_expr (`or` and_expr)*
//! and_expr := not_expr (`and` not_expr)*
//! not_expr := `not`? primary
//! primary  := `(` expr `)` | comparison
//! comparison := ident op value
//! op := `=` | `!=` | `<` | `<=` | `>` | `>=` | `~`
//! value := string | int | regex
//! ```

use crate::filter::dsl::ast::{Cmp, Expr, Value};
use crate::filter::dsl::error::{DslError, DslResult};
use crate::filter::dsl::parser::lexer::{Spanned, Token};

pub fn parse_tokens(tokens: Vec<Spanned>) -> DslResult<Expr> {
    let mut cur = Cursor { tokens, pos: 0 };
    let expr = parse_or(&mut cur)?;
    if let Some(stray) = cur.peek() {
        return Err(DslError::Syntax {
            column: stray.column,
            message: format!("unexpected trailing token {:?}", stray.token),
        });
    }
    Ok(expr)
}

struct Cursor {
    tokens: Vec<Spanned>,
    pos: usize,
}

impl Cursor {
    fn peek(&self) -> Option<&Spanned> {
        self.tokens.get(self.pos)
    }

    fn advance(&mut self) -> Option<Spanned> {
        let t = self.tokens.get(self.pos).cloned();
        if t.is_some() {
            self.pos += 1;
        }
        t
    }

    fn column(&self) -> usize {
        self.tokens
            .get(self.pos.saturating_sub(1))
            .map(|s| s.column)
            .unwrap_or(1)
    }
}

fn parse_or(cur: &mut Cursor) -> DslResult<Expr> {
    let mut lhs = parse_and(cur)?;
    while matches!(cur.peek().map(|s| &s.token), Some(Token::Or)) {
        cur.advance();
        let rhs = parse_and(cur)?;
        lhs = Expr::Or(Box::new(lhs), Box::new(rhs));
    }
    Ok(lhs)
}

fn parse_and(cur: &mut Cursor) -> DslResult<Expr> {
    let mut lhs = parse_not(cur)?;
    while matches!(cur.peek().map(|s| &s.token), Some(Token::And)) {
        cur.advance();
        let rhs = parse_not(cur)?;
        lhs = Expr::And(Box::new(lhs), Box::new(rhs));
    }
    Ok(lhs)
}

fn parse_not(cur: &mut Cursor) -> DslResult<Expr> {
    if matches!(cur.peek().map(|s| &s.token), Some(Token::Not)) {
        cur.advance();
        let inner = parse_not(cur)?;
        return Ok(Expr::Not(Box::new(inner)));
    }
    parse_primary(cur)
}

fn parse_primary(cur: &mut Cursor) -> DslResult<Expr> {
    match cur.peek().map(|s| s.token.clone()) {
        Some(Token::LParen) => {
            cur.advance();
            let inner = parse_or(cur)?;
            match cur.advance().map(|s| s.token) {
                Some(Token::RParen) => Ok(inner),
                _ => Err(DslError::Syntax {
                    column: cur.column(),
                    message: "expected `)`".into(),
                }),
            }
        }
        Some(Token::Ident(name)) => {
            cur.advance();
            let op = parse_op(cur)?;
            let value = parse_value(cur)?;
            Ok(Expr::Compare {
                field: name,
                op,
                value,
            })
        }
        other => Err(DslError::Syntax {
            column: cur.column(),
            message: format!("expected identifier, found {:?}", other),
        }),
    }
}

fn parse_op(cur: &mut Cursor) -> DslResult<Cmp> {
    let span = cur.advance().ok_or_else(|| DslError::Syntax {
        column: cur.column(),
        message: "expected comparison operator".into(),
    })?;
    match span.token {
        Token::Eq => Ok(Cmp::Eq),
        Token::Ne => Ok(Cmp::Ne),
        Token::Lt => Ok(Cmp::Lt),
        Token::Le => Ok(Cmp::Le),
        Token::Gt => Ok(Cmp::Gt),
        Token::Ge => Ok(Cmp::Ge),
        Token::Tilde => Ok(Cmp::Match),
        other => Err(DslError::Syntax {
            column: span.column,
            message: format!("expected comparison operator, found {:?}", other),
        }),
    }
}

fn parse_value(cur: &mut Cursor) -> DslResult<Value> {
    let span = cur.advance().ok_or_else(|| DslError::Syntax {
        column: cur.column(),
        message: "expected value".into(),
    })?;
    match span.token {
        Token::Str(s) => Ok(Value::Str(s)),
        Token::Int(n) => Ok(Value::Int(n)),
        Token::Regex(r) => Ok(Value::Regex(r)),
        Token::Ident(i) => Ok(Value::Str(i)),
        other => Err(DslError::Syntax {
            column: span.column,
            message: format!("expected literal, found {:?}", other),
        }),
    }
}