ternary-grammar 0.1.0

//! # ternary-grammar
//!
//! Context-free grammar for generating and parsing valid ternary strategy expressions.
//!
//! Provides:
//! - `Grammar` — CFG definition and production rules
//! - `TernaryExpr` — AST for ternary strategy expressions
//! - `Parser` — Recursive descent parser for ternary expressions
//! - `Generator` — Generate valid ternary expressions from grammar
//! - `Evaluator` — Evaluate ternary expressions

use std::collections::HashMap;
use std::fmt;

/// Ternary value
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Trit {
    Neg,
    Zero,
    Pos,
}

impl Trit {
    pub fn to_i8(self) -> i8 {
        match self {
            Trit::Neg => -1,
            Trit::Zero => 0,
            Trit::Pos => 1,
        }
    }

    pub fn from_i8(v: i8) -> Option<Self> {
        match v {
            -1 => Some(Trit::Neg),
            0 => Some(Trit::Zero),
            1 => Some(Trit::Pos),
            _ => None,
        }
    }
}

/// Strategy operator for combining ternary values
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Op {
    Add,       // a + b (clamped)
    Multiply,  // a * b
    Max,       // max(a, b)
    Min,       // min(a, b)
    Negate,    // -a
    Compose,   // sequential composition
}

impl fmt::Display for Op {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Op::Add => write!(f, "+"),
            Op::Multiply => write!(f, "*"),
            Op::Max => write!(f, "max"),
            Op::Min => write!(f, "min"),
            Op::Negate => write!(f, "neg"),
            Op::Compose => write!(f, ">>"),
        }
    }
}

/// AST node for ternary strategy expressions
#[derive(Debug, Clone, PartialEq)]
pub enum TernaryExpr {
    /// Literal ternary value
    Literal(Trit),
    /// Variable reference (e.g., "x", "y")
    Var(String),
    /// Unary operation
    Unary(Op, Box<TernaryExpr>),
    /// Binary operation
    Binary(Op, Box<TernaryExpr>, Box<TernaryExpr>),
    /// Conditional: if guard then_expr else_expr
    If(Box<TernaryExpr>, Box<TernaryExpr>, Box<TernaryExpr>),
    /// Sequence of expressions
    Seq(Vec<TernaryExpr>),
}

impl fmt::Display for TernaryExpr {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            TernaryExpr::Literal(t) => write!(f, "{}", t.to_i8()),
            TernaryExpr::Var(name) => write!(f, "{}", name),
            TernaryExpr::Unary(op, expr) => write!(f, "({} {})", op, expr),
            TernaryExpr::Binary(op, l, r) => write!(f, "({} {} {})", l, op, r),
            TernaryExpr::If(guard, then_e, else_e) => write!(f, "(if {} {} {})", guard, then_e, else_e),
            TernaryExpr::Seq(exprs) => {
                write!(f, "(seq")?;
                for e in exprs {
                    write!(f, " {}", e)?;
                }
                write!(f, ")")
            }
        }
    }
}

/// A grammar production rule
#[derive(Debug, Clone)]
pub struct Production {
    pub name: String,
    pub alternatives: Vec<String>,
}

/// Context-free grammar for ternary expressions
#[derive(Debug, Clone)]
pub struct Grammar {
    productions: Vec<Production>,
    terminals: Vec<String>,
}

impl Grammar {
    pub fn new() -> Self {
        let productions = vec![
            Production {
                name: "expr".to_string(),
                alternatives: vec![
                    "literal".to_string(),
                    "variable".to_string(),
                    "unary".to_string(),
                    "binary".to_string(),
                    "conditional".to_string(),
                    "sequence".to_string(),
                ],
            },
            Production {
                name: "literal".to_string(),
                alternatives: vec!["NEG".to_string(), "ZERO".to_string(), "POS".to_string()],
            },
            Production {
                name: "variable".to_string(),
                alternatives: vec!["x".to_string(), "y".to_string(), "z".to_string()],
            },
            Production {
                name: "unary".to_string(),
                alternatives: vec!["NEGATE expr".to_string()],
            },
            Production {
                name: "binary".to_string(),
                alternatives: vec![
                    "expr ADD expr".to_string(),
                    "expr MUL expr".to_string(),
                    "expr MAX expr".to_string(),
                    "expr MIN expr".to_string(),
                    "expr COMP expr".to_string(),
                ],
            },
            Production {
                name: "conditional".to_string(),
                alternatives: vec!["IF expr expr expr".to_string()],
            },
            Production {
                name: "sequence".to_string(),
                alternatives: vec!["SEQ expr_list".to_string()],
            },
            Production {
                name: "expr_list".to_string(),
                alternatives: vec!["expr".to_string(), "expr expr_list".to_string()],
            },
        ];

        let terminals = vec![
            "NEG".to_string(), "ZERO".to_string(), "POS".to_string(),
            "ADD".to_string(), "MUL".to_string(), "MAX".to_string(), "MIN".to_string(),
            "NEGATE".to_string(), "COMP".to_string(),
            "IF".to_string(), "SEQ".to_string(),
            "x".to_string(), "y".to_string(), "z".to_string(),
        ];

        Grammar { productions, terminals }
    }

    pub fn productions(&self) -> &[Production] {
        &self.productions
    }

    pub fn terminals(&self) -> &[String] {
        &self.terminals
    }

    pub fn is_terminal(&self, symbol: &str) -> bool {
        self.terminals.iter().any(|t| t == symbol)
    }

    pub fn get_production(&self, name: &str) -> Option<&Production> {
        self.productions.iter().find(|p| p.name == name)
    }
}

/// Token for parsing
#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    Literal(Trit),
    Var(String),
    Op(Op),
    If,
    Seq,
    LParen,
    RParen,
}

/// Tokenizer for ternary expressions
pub struct Tokenizer;

impl Tokenizer {
    pub fn tokenize(input: &str) -> Result<Vec<Token>, String> {
        let mut tokens = Vec::new();
        let mut chars = input.chars().peekable();

        while let Some(&ch) = chars.peek() {
            match ch {
                ' ' | '\t' | '\n' | '\r' => { chars.next(); }
                '(' => { tokens.push(Token::LParen); chars.next(); }
                ')' => { tokens.push(Token::RParen); chars.next(); }
                '-' => {
                    chars.next();
                    if chars.peek() == Some(&'1') {
                        chars.next();
                        tokens.push(Token::Literal(Trit::Neg));
                    } else {
                        tokens.push(Token::Op(Op::Negate));
                    }
                }
                '0' => { chars.next(); tokens.push(Token::Literal(Trit::Zero)); }
                '1' => { chars.next(); tokens.push(Token::Literal(Trit::Pos)); }
                '+' => { chars.next(); tokens.push(Token::Op(Op::Add)); }
                '*' => { chars.next(); tokens.push(Token::Op(Op::Multiply)); }
                '>' => {
                    chars.next();
                    if chars.peek() == Some(&'>') {
                        chars.next();
                        tokens.push(Token::Op(Op::Compose));
                    }
                }
                _ if ch.is_alphabetic() => {
                    let mut word = String::new();
                    while let Some(&c) = chars.peek() {
                        if c.is_alphanumeric() || c == '_' {
                            word.push(c);
                            chars.next();
                        } else {
                            break;
                        }
                    }
                    match word.as_str() {
                        "neg" | "NEG" => tokens.push(Token::Op(Op::Negate)),
                        "max" | "MAX" => tokens.push(Token::Op(Op::Max)),
                        "min" | "MIN" => tokens.push(Token::Op(Op::Min)),
                        "if" | "IF" => tokens.push(Token::If),
                        "seq" | "SEQ" => tokens.push(Token::Seq),
                        _ => tokens.push(Token::Var(word)),
                    }
                }
                _ => return Err(format!("Unexpected character: {}", ch)),
            }
        }
        Ok(tokens)
    }
}

/// Recursive descent parser
pub struct Parser {
    pos: usize,
    tokens: Vec<Token>,
}

impl Parser {
    pub fn new(tokens: Vec<Token>) -> Self {
        Parser { pos: 0, tokens }
    }

    pub fn parse(input: &str) -> Result<TernaryExpr, String> {
        let tokens = Tokenizer::tokenize(input)?;
        let mut parser = Parser::new(tokens);
        let expr = parser.parse_expr()?;
        if parser.pos < parser.tokens.len() {
            return Err("Unexpected tokens after expression".to_string());
        }
        Ok(expr)
    }

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

    fn advance(&mut self) -> Option<Token> {
        if self.pos < self.tokens.len() {
            let tok = self.tokens[self.pos].clone();
            self.pos += 1;
            Some(tok)
        } else {
            None
        }
    }

    fn parse_expr(&mut self) -> Result<TernaryExpr, String> {
        // Check for parenthesized expression
        if self.peek() == Some(&Token::LParen) {
            self.advance(); // consume '('
            let expr = self.parse_inner()?;
            if self.peek() == Some(&Token::RParen) {
                self.advance(); // consume ')'
            }
            return Ok(expr);
        }

        // Simple atom
        self.parse_atom()
    }

    fn parse_inner(&mut self) -> Result<TernaryExpr, String> {
        // Check for 'if' keyword
        if self.peek() == Some(&Token::If) {
            self.advance();
            let guard = self.parse_expr()?;
            let then_expr = self.parse_expr()?;
            let else_expr = self.parse_expr()?;
            return Ok(TernaryExpr::If(
                Box::new(guard),
                Box::new(then_expr),
                Box::new(else_expr),
            ));
        }

        // Check for 'seq'
        if self.peek() == Some(&Token::Seq) {
            self.advance();
            let mut exprs = Vec::new();
            while self.peek().is_some() && self.peek() != Some(&Token::RParen) {
                exprs.push(self.parse_expr()?);
            }
            return Ok(TernaryExpr::Seq(exprs));
        }

        // Parse first operand
        let left = self.parse_expr()?;

        // Check for binary operator
        if let Some(Token::Op(op)) = self.peek() {
            if matches!(op, Op::Add | Op::Multiply | Op::Max | Op::Min | Op::Compose) {
                let op = *op;
                self.advance();
                let right = self.parse_expr()?;
                return Ok(TernaryExpr::Binary(op, Box::new(left), Box::new(right)));
            }
        }

        Ok(left)
    }

    fn parse_atom(&mut self) -> Result<TernaryExpr, String> {
        match self.advance() {
            Some(Token::Literal(t)) => Ok(TernaryExpr::Literal(t)),
            Some(Token::Var(name)) => Ok(TernaryExpr::Var(name)),
            Some(Token::Op(Op::Negate)) => {
                let expr = self.parse_expr()?;
                Ok(TernaryExpr::Unary(Op::Negate, Box::new(expr)))
            }
            Some(Token::LParen) => {
                let expr = self.parse_inner()?;
                if self.peek() == Some(&Token::RParen) {
                    self.advance();
                }
                Ok(expr)
            }
            other => Err(format!("Unexpected token: {:?}", other)),
        }
    }
}

/// Expression generator
pub struct Generator {
    max_depth: usize,
    counter: usize,
}

impl Generator {
    pub fn new(max_depth: usize) -> Self {
        Generator { max_depth, counter: 0 }
    }

    /// Generate a random-ish expression
    pub fn generate(&mut self) -> TernaryExpr {
        self.gen_expr(self.max_depth)
    }

    fn gen_expr(&mut self, depth: usize) -> TernaryExpr {
        if depth == 0 {
            return self.gen_literal();
        }

        self.counter = self.counter.wrapping_add(1);
        let choice = self.counter % 4;

        match choice {
            0 => self.gen_literal(),
            1 => self.gen_var(),
            2 => self.gen_binary(depth - 1),
            3 => self.gen_unary(depth - 1),
            _ => self.gen_literal(),
        }
    }

    fn gen_literal(&mut self) -> TernaryExpr {
        self.counter = self.counter.wrapping_add(1);
        let trit = match self.counter % 3 {
            0 => Trit::Neg,
            1 => Trit::Zero,
            _ => Trit::Pos,
        };
        TernaryExpr::Literal(trit)
    }

    fn gen_var(&mut self) -> TernaryExpr {
        self.counter = self.counter.wrapping_add(1);
        let name = match self.counter % 3 {
            0 => "x".to_string(),
            1 => "y".to_string(),
            _ => "z".to_string(),
        };
        TernaryExpr::Var(name)
    }

    fn gen_binary(&mut self, depth: usize) -> TernaryExpr {
        self.counter = self.counter.wrapping_add(1);
        let op = match self.counter % 5 {
            0 => Op::Add,
            1 => Op::Multiply,
            2 => Op::Max,
            3 => Op::Min,
            _ => Op::Compose,
        };
        let left = self.gen_expr(depth);
        let right = self.gen_expr(depth);
        TernaryExpr::Binary(op, Box::new(left), Box::new(right))
    }

    fn gen_unary(&mut self, depth: usize) -> TernaryExpr {
        let expr = self.gen_expr(depth);
        TernaryExpr::Unary(Op::Negate, Box::new(expr))
    }

    /// Generate an if expression
    pub fn generate_if(&mut self) -> TernaryExpr {
        let guard = self.gen_expr(self.max_depth.saturating_sub(1));
        let then_expr = self.gen_literal();
        let else_expr = self.gen_literal();
        TernaryExpr::If(Box::new(guard), Box::new(then_expr), Box::new(else_expr))
    }

    /// Generate a sequence
    pub fn generate_seq(&mut self, len: usize) -> TernaryExpr {
        let exprs: Vec<TernaryExpr> = (0..len).map(|_| self.gen_expr(self.max_depth.saturating_sub(1))).collect();
        TernaryExpr::Seq(exprs)
    }
}

/// Evaluate ternary expressions
pub struct Evaluator;

impl Evaluator {
    /// Evaluate an expression with given variable bindings
    pub fn eval(expr: &TernaryExpr, vars: &HashMap<String, Trit>) -> Result<Trit, String> {
        match expr {
            TernaryExpr::Literal(t) => Ok(*t),
            TernaryExpr::Var(name) => {
                vars.get(name).copied().ok_or_else(|| format!("Undefined variable: {}", name))
            }
            TernaryExpr::Unary(Op::Negate, inner) => {
                let v = Self::eval(inner, vars)?.to_i8();
                Trit::from_i8(-v).ok_or("Negation failed".to_string())
            }
            TernaryExpr::Unary(_, inner) => Self::eval(inner, vars),
            TernaryExpr::Binary(op, left, right) => {
                let lv = Self::eval(left, vars)?.to_i8();
                let rv = Self::eval(right, vars)?.to_i8();
                let result = match op {
                    Op::Add => (lv + rv).clamp(-1, 1),
                    Op::Multiply => (lv * rv).clamp(-1, 1),
                    Op::Max => lv.max(rv),
                    Op::Min => lv.min(rv),
                    Op::Compose => rv, // Right-biased composition
                    _ => 0,
                };
                Ok(Trit::from_i8(result).unwrap_or(Trit::Zero))
            }
            TernaryExpr::If(guard, then_expr, else_expr) => {
                let g = Self::eval(guard, vars)?;
                if g == Trit::Pos {
                    Self::eval(then_expr, vars)
                } else {
                    Self::eval(else_expr, vars)
                }
            }
            TernaryExpr::Seq(exprs) => {
                let mut last = Trit::Zero;
                for e in exprs {
                    last = Self::eval(e, vars)?;
                }
                Ok(last)
            }
        }
    }

    /// Simplify an expression by evaluating constant sub-expressions
    pub fn simplify(expr: &TernaryExpr) -> TernaryExpr {
        match expr {
            TernaryExpr::Literal(t) => TernaryExpr::Literal(*t),
            TernaryExpr::Var(name) => TernaryExpr::Var(name.clone()),
            TernaryExpr::Unary(op, inner) => {
                let simplified = Self::simplify(inner);
                if let TernaryExpr::Literal(t) = simplified {
                    // Can evaluate
                    let v = t.to_i8();
                    if *op == Op::Negate {
                        TernaryExpr::Literal(Trit::from_i8(-v).unwrap_or(Trit::Zero))
                    } else {
                        TernaryExpr::Literal(t)
                    }
                } else {
                    TernaryExpr::Unary(*op, Box::new(simplified))
                }
            }
            TernaryExpr::Binary(op, left, right) => {
                let sl = Self::simplify(left);
                let sr = Self::simplify(right);
                if let (TernaryExpr::Literal(l), TernaryExpr::Literal(r)) = (&sl, &sr) {
                    let lv = l.to_i8();
                    let rv = r.to_i8();
                    let result = match op {
                        Op::Add => (lv + rv).clamp(-1, 1),
                        Op::Multiply => (lv * rv).clamp(-1, 1),
                        Op::Max => lv.max(rv),
                        Op::Min => lv.min(rv),
                        Op::Compose => rv,
                        _ => 0,
                    };
                    TernaryExpr::Literal(Trit::from_i8(result).unwrap_or(Trit::Zero))
                } else {
                    TernaryExpr::Binary(*op, Box::new(sl), Box::new(sr))
                }
            }
            TernaryExpr::If(guard, then_expr, else_expr) => {
                let sg = Self::simplify(guard);
                if let TernaryExpr::Literal(t) = sg {
                    if t == Trit::Pos {
                        Self::simplify(then_expr)
                    } else {
                        Self::simplify(else_expr)
                    }
                } else {
                    TernaryExpr::If(
                        Box::new(sg),
                        Box::new(Self::simplify(then_expr)),
                        Box::new(Self::simplify(else_expr)),
                    )
                }
            }
            TernaryExpr::Seq(exprs) => {
                let simplified: Vec<TernaryExpr> = exprs.iter().map(Self::simplify).collect();
                TernaryExpr::Seq(simplified)
            }
        }
    }
}

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

    #[test]
    fn test_trit_values() {
        assert_eq!(Trit::Neg.to_i8(), -1);
        assert_eq!(Trit::Zero.to_i8(), 0);
        assert_eq!(Trit::Pos.to_i8(), 1);
    }

    #[test]
    fn test_expr_display_literal() {
        let expr = TernaryExpr::Literal(Trit::Pos);
        assert_eq!(format!("{}", expr), "1");
    }

    #[test]
    fn test_expr_display_binary() {
        let expr = TernaryExpr::Binary(
            Op::Add,
            Box::new(TernaryExpr::Literal(Trit::Pos)),
            Box::new(TernaryExpr::Literal(Trit::Neg)),
        );
        assert_eq!(format!("{}", expr), "(1 + -1)");
    }

    #[test]
    fn test_expr_display_unary() {
        let expr = TernaryExpr::Unary(Op::Negate, Box::new(TernaryExpr::Literal(Trit::Pos)));
        assert_eq!(format!("{}", expr), "(neg 1)");
    }

    #[test]
    fn test_expr_display_var() {
        let expr = TernaryExpr::Var("x".to_string());
        assert_eq!(format!("{}", expr), "x");
    }

    #[test]
    fn test_grammar_new() {
        let g = Grammar::new();
        assert!(!g.productions().is_empty());
        assert!(!g.terminals().is_empty());
    }

    #[test]
    fn test_grammar_is_terminal() {
        let g = Grammar::new();
        assert!(g.is_terminal("NEG"));
        assert!(g.is_terminal("ADD"));
        assert!(!g.is_terminal("expr"));
    }

    #[test]
    fn test_grammar_get_production() {
        let g = Grammar::new();
        let prod = g.get_production("expr").unwrap();
        assert_eq!(prod.name, "expr");
        assert!(prod.alternatives.len() > 1);
    }

    #[test]
    fn test_tokenizer_literals() {
        let tokens = Tokenizer::tokenize("-1 0 1").unwrap();
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], Token::Literal(Trit::Neg));
        assert_eq!(tokens[1], Token::Literal(Trit::Zero));
        assert_eq!(tokens[2], Token::Literal(Trit::Pos));
    }

    #[test]
    fn test_tokenizer_operators() {
        let tokens = Tokenizer::tokenize("+ * >>").unwrap();
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], Token::Op(Op::Add));
        assert_eq!(tokens[1], Token::Op(Op::Multiply));
        assert_eq!(tokens[2], Token::Op(Op::Compose));
    }

    #[test]
    fn test_tokenizer_keywords() {
        let tokens = Tokenizer::tokenize("neg max min if seq").unwrap();
        assert_eq!(tokens.len(), 5);
        assert_eq!(tokens[0], Token::Op(Op::Negate));
        assert_eq!(tokens[1], Token::Op(Op::Max));
        assert_eq!(tokens[3], Token::If);
        assert_eq!(tokens[4], Token::Seq);
    }

    #[test]
    fn test_tokenizer_vars() {
        let tokens = Tokenizer::tokenize("x y z").unwrap();
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], Token::Var("x".to_string()));
    }

    #[test]
    fn test_parser_literal() {
        let expr = Parser::parse("1").unwrap();
        assert_eq!(expr, TernaryExpr::Literal(Trit::Pos));
    }

    #[test]
    fn test_parser_binary() {
        let expr = Parser::parse("(1 + -1)").unwrap();
        assert_eq!(expr, TernaryExpr::Binary(
            Op::Add,
            Box::new(TernaryExpr::Literal(Trit::Pos)),
            Box::new(TernaryExpr::Literal(Trit::Neg)),
        ));
    }

    #[test]
    fn test_parser_unary() {
        let expr = Parser::parse("neg 1").unwrap();
        assert_eq!(expr, TernaryExpr::Unary(Op::Negate, Box::new(TernaryExpr::Literal(Trit::Pos))));
    }

    #[test]
    fn test_parser_nested() {
        let expr = Parser::parse("((1 + -1) * 0)").unwrap();
        assert!(matches!(expr, TernaryExpr::Binary(Op::Multiply, _, _)));
    }

    #[test]
    fn test_evaluator_literal() {
        let expr = TernaryExpr::Literal(Trit::Pos);
        let result = Evaluator::eval(&expr, &HashMap::new()).unwrap();
        assert_eq!(result, Trit::Pos);
    }

    #[test]
    fn test_evaluator_var() {
        let expr = TernaryExpr::Var("x".to_string());
        let mut vars = HashMap::new();
        vars.insert("x".to_string(), Trit::Neg);
        let result = Evaluator::eval(&expr, &vars).unwrap();
        assert_eq!(result, Trit::Neg);
    }

    #[test]
    fn test_evaluator_add() {
        let expr = TernaryExpr::Binary(Op::Add, Box::new(TernaryExpr::Literal(Trit::Pos)), Box::new(TernaryExpr::Literal(Trit::Neg)));
        let result = Evaluator::eval(&expr, &HashMap::new()).unwrap();
        assert_eq!(result, Trit::Zero);
    }

    #[test]
    fn test_evaluator_multiply() {
        let expr = TernaryExpr::Binary(Op::Multiply, Box::new(TernaryExpr::Literal(Trit::Pos)), Box::new(TernaryExpr::Literal(Trit::Pos)));
        let result = Evaluator::eval(&expr, &HashMap::new()).unwrap();
        assert_eq!(result, Trit::Pos);
    }

    #[test]
    fn test_evaluator_negate() {
        let expr = TernaryExpr::Unary(Op::Negate, Box::new(TernaryExpr::Literal(Trit::Pos)));
        let result = Evaluator::eval(&expr, &HashMap::new()).unwrap();
        assert_eq!(result, Trit::Neg);
    }

    #[test]
    fn test_evaluator_if() {
        let expr = TernaryExpr::If(
            Box::new(TernaryExpr::Literal(Trit::Pos)),
            Box::new(TernaryExpr::Literal(Trit::Pos)),
            Box::new(TernaryExpr::Literal(Trit::Neg)),
        );
        let result = Evaluator::eval(&expr, &HashMap::new()).unwrap();
        assert_eq!(result, Trit::Pos);
    }

    #[test]
    fn test_simplify_constants() {
        let expr = TernaryExpr::Binary(Op::Add, Box::new(TernaryExpr::Literal(Trit::Pos)), Box::new(TernaryExpr::Literal(Trit::Neg)));
        let simplified = Evaluator::simplify(&expr);
        assert_eq!(simplified, TernaryExpr::Literal(Trit::Zero));
    }
}