openvet-policy 0.2.0

//! Requirement expression: parse + evaluate.
//!
//! Grammar:
//! ```text
//! expr   := or_expr
//! or_expr  := and_expr ('or' and_expr)*
//! and_expr := not_expr ('and' not_expr)*
//! not_expr := 'not' not_expr | atom
//! atom     := claim | '(' expr ')'
//! claim    := [a-zA-Z_][a-zA-Z0-9_-]*
//! ```
//!
//! Standard precedence (`not` > `and` > `or`); reserved words are
//! literally `and`, `or`, `not` (not case-sensitive).
//!
//! Evaluation is Kleene 3-valued logic over [`Tri`]:
//! - `False` short-circuits `and`
//! - `True` short-circuits `or`
//! - `Unknown` propagates whenever neither short-circuit fires and
//!   the result isn't determined.

use crate::error::PolicyError;

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
    Claim(String),
    Not(Box<Expr>),
    And(Box<Expr>, Box<Expr>),
    Or(Box<Expr>, Box<Expr>),
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Tri {
    True,
    False,
    Unknown,
}

impl std::ops::Not for Tri {
    type Output = Tri;
    fn not(self) -> Self {
        match self {
            Tri::True => Tri::False,
            Tri::False => Tri::True,
            Tri::Unknown => Tri::Unknown,
        }
    }
}

/// Evaluate `expr` against a claim-lookup function returning each
/// claim's tri-state. Short-circuits on `False` (and) / `True` (or).
pub fn evaluate<F>(expr: &Expr, lookup: &F) -> Tri
where
    F: Fn(&str) -> Tri,
{
    match expr {
        Expr::Claim(name) => lookup(name),
        Expr::Not(inner) => !evaluate(inner, lookup),
        Expr::And(l, r) => {
            let lv = evaluate(l, lookup);
            if lv == Tri::False {
                return Tri::False;
            }
            let rv = evaluate(r, lookup);
            match (lv, rv) {
                (_, Tri::False) => Tri::False,
                (Tri::True, Tri::True) => Tri::True,
                _ => Tri::Unknown,
            }
        }
        Expr::Or(l, r) => {
            let lv = evaluate(l, lookup);
            if lv == Tri::True {
                return Tri::True;
            }
            let rv = evaluate(r, lookup);
            match (lv, rv) {
                (_, Tri::True) => Tri::True,
                (Tri::False, Tri::False) => Tri::False,
                _ => Tri::Unknown,
            }
        }
    }
}

// ──────────────────────────────────────────────────────────────────
// Tokenizer
// ──────────────────────────────────────────────────────────────────

#[derive(Debug, PartialEq, Eq)]
enum Token {
    Ident(String),
    And,
    Or,
    Not,
    LParen,
    RParen,
}

fn tokenize(input: &str) -> Result<Vec<Token>, PolicyError> {
    let mut out = Vec::new();
    let mut chars = input.chars().peekable();
    while let Some(&c) = chars.peek() {
        if c.is_whitespace() {
            chars.next();
            continue;
        }
        if c == '(' {
            chars.next();
            out.push(Token::LParen);
            continue;
        }
        if c == ')' {
            chars.next();
            out.push(Token::RParen);
            continue;
        }
        if is_ident_start(c) {
            let mut s = String::new();
            while let Some(&c) = chars.peek() {
                if is_ident_continue(c) {
                    s.push(c);
                    chars.next();
                } else {
                    break;
                }
            }
            out.push(match s.to_ascii_lowercase().as_str() {
                "and" => Token::And,
                "or" => Token::Or,
                "not" => Token::Not,
                _ => Token::Ident(s),
            });
            continue;
        }
        return Err(PolicyError::ExprParse(format!(
            "unexpected character {c:?} in expression"
        )));
    }
    Ok(out)
}

fn is_ident_start(c: char) -> bool {
    c.is_ascii_alphabetic() || c == '_'
}

fn is_ident_continue(c: char) -> bool {
    c.is_ascii_alphanumeric() || c == '_' || c == '-'
}

// ──────────────────────────────────────────────────────────────────
// Recursive-descent parser
// ──────────────────────────────────────────────────────────────────

struct Parser {
    tokens: std::vec::IntoIter<Token>,
    peeked: Option<Token>,
}

impl Parser {
    fn new(tokens: Vec<Token>) -> Self {
        Self {
            tokens: tokens.into_iter(),
            peeked: None,
        }
    }

    fn peek(&mut self) -> Option<&Token> {
        if self.peeked.is_none() {
            self.peeked = self.tokens.next();
        }
        self.peeked.as_ref()
    }

    fn consume(&mut self) -> Option<Token> {
        if let Some(t) = self.peeked.take() {
            return Some(t);
        }
        self.tokens.next()
    }

    fn parse_expr(&mut self) -> Result<Expr, PolicyError> {
        self.parse_or()
    }

    fn parse_or(&mut self) -> Result<Expr, PolicyError> {
        let mut left = self.parse_and()?;
        while matches!(self.peek(), Some(Token::Or)) {
            self.consume();
            let right = self.parse_and()?;
            left = Expr::Or(Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    fn parse_and(&mut self) -> Result<Expr, PolicyError> {
        let mut left = self.parse_not()?;
        while matches!(self.peek(), Some(Token::And)) {
            self.consume();
            let right = self.parse_not()?;
            left = Expr::And(Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    fn parse_not(&mut self) -> Result<Expr, PolicyError> {
        if matches!(self.peek(), Some(Token::Not)) {
            self.consume();
            let inner = self.parse_not()?;
            return Ok(Expr::Not(Box::new(inner)));
        }
        self.parse_atom()
    }

    fn parse_atom(&mut self) -> Result<Expr, PolicyError> {
        match self.consume() {
            Some(Token::Ident(s)) => Ok(Expr::Claim(s)),
            Some(Token::LParen) => {
                let inner = self.parse_expr()?;
                match self.consume() {
                    Some(Token::RParen) => Ok(inner),
                    _ => Err(PolicyError::ExprParse("missing closing ')'".into())),
                }
            }
            Some(t) => Err(PolicyError::ExprParse(format!(
                "unexpected token {t:?}; expected claim or '('"
            ))),
            None => Err(PolicyError::ExprParse(
                "unexpected end of expression".into(),
            )),
        }
    }
}

pub fn parse(input: &str) -> Result<Expr, PolicyError> {
    let tokens = tokenize(input)?;
    let mut p = Parser::new(tokens);
    let expr = p.parse_expr()?;
    if p.peek().is_some() {
        return Err(PolicyError::ExprParse(format!(
            "trailing tokens after expression: {:?}",
            p.consume()
        )));
    }
    Ok(expr)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn ev(expr: &str, claims: &[(&str, bool)]) -> Tri {
        let e = parse(expr).unwrap();
        let lookup = |name: &str| match claims.iter().find(|(n, _)| *n == name) {
            Some((_, true)) => Tri::True,
            Some((_, false)) => Tri::False,
            None => Tri::Unknown,
        };
        evaluate(&e, &lookup)
    }

    #[test]
    fn single_claim() {
        assert_eq!(ev("safe-to-deploy", &[("safe-to-deploy", true)]), Tri::True);
        assert_eq!(ev("safe-to-deploy", &[("safe-to-deploy", false)]), Tri::False);
        assert_eq!(ev("safe-to-deploy", &[]), Tri::Unknown);
    }

    #[test]
    fn and_basic() {
        assert_eq!(ev("a and b", &[("a", true), ("b", true)]), Tri::True);
        assert_eq!(ev("a and b", &[("a", true), ("b", false)]), Tri::False);
        assert_eq!(ev("a and b", &[("a", true)]), Tri::Unknown);
    }

    #[test]
    fn and_short_circuits_on_false() {
        // `b` is unknown but irrelevant since `a` is false.
        assert_eq!(ev("a and b", &[("a", false)]), Tri::False);
    }

    #[test]
    fn or_basic() {
        assert_eq!(ev("a or b", &[("a", false), ("b", true)]), Tri::True);
        assert_eq!(ev("a or b", &[("a", false), ("b", false)]), Tri::False);
        assert_eq!(ev("a or b", &[("a", false)]), Tri::Unknown);
    }

    #[test]
    fn or_short_circuits_on_true() {
        assert_eq!(ev("a or b", &[("a", true)]), Tri::True);
    }

    #[test]
    fn not_inverts() {
        assert_eq!(ev("not a", &[("a", true)]), Tri::False);
        assert_eq!(ev("not a", &[("a", false)]), Tri::True);
        assert_eq!(ev("not a", &[]), Tri::Unknown);
    }

    #[test]
    fn precedence_not_binds_tightest() {
        // `not a and b` parses as `(not a) and b`, not `not (a and b)`.
        assert_eq!(ev("not a and b", &[("a", false), ("b", true)]), Tri::True);
        assert_eq!(ev("not a and b", &[("a", true), ("b", true)]), Tri::False);
    }

    #[test]
    fn precedence_and_binds_tighter_than_or() {
        // `a or b and c` parses as `a or (b and c)`.
        assert_eq!(
            ev("a or b and c", &[("a", false), ("b", true), ("c", true)]),
            Tri::True
        );
        assert_eq!(
            ev("a or b and c", &[("a", false), ("b", true), ("c", false)]),
            Tri::False
        );
    }

    #[test]
    fn parens_override_precedence() {
        // `(a or b) and c` — without parens this'd be `a or (b and c)`.
        assert_eq!(
            ev("(a or b) and c", &[("a", true), ("c", false)]),
            Tri::False
        );
    }

    #[test]
    fn nested_not_and_or() {
        assert_eq!(
            ev("not (a and b) or c", &[("a", true), ("b", true), ("c", false)]),
            Tri::False
        );
        assert_eq!(
            ev("not (a and b) or c", &[("a", true), ("b", false)]),
            Tri::True
        );
    }

    #[test]
    fn case_insensitive_keywords() {
        assert_eq!(ev("a AND b", &[("a", true), ("b", true)]), Tri::True);
        assert_eq!(ev("NOT a", &[("a", true)]), Tri::False);
    }

    #[test]
    fn parse_errors() {
        assert!(parse("a and").is_err());
        assert!(parse("(a or b").is_err());
        assert!(parse("and a").is_err());
        assert!(parse("a b").is_err()); // trailing token
        assert!(parse("").is_err());
        assert!(parse("a #").is_err()); // unknown character
    }
}