truth-table 0.2.0

//! Parse a stream of Tokens into a syntax tree

use super::lexer::{rposition_if_not_in_paren, Token, Tokens};

/// Unit in an abstract syntax tree
#[derive(Debug, PartialEq)]
pub enum Expr {
    Ident(char),
    Not(Box<Expr>),
    And(Box<(Expr, Expr)>),
    Or(Box<(Expr, Expr)>),
    Equals(Box<(Expr, Expr)>),
    NotEquals(Box<(Expr, Expr)>),
    Implication(Box<(Expr, Expr)>),
    True,
    False,
}

impl Expr {
    #[allow(dead_code)]
    pub fn from_text(text: &str) -> Self {
        Self::from_tokens(&Tokens::from_text(text))
    }

    pub fn from_tokens(tokens: &[Token]) -> Self {
        match tokens {
            [] => panic!("Error while parsing"),
            [one] => {
                // A single lone Token must be an identifier or a constant
                match one {
                    Token::Ident(ident) => {
                        Expr::Ident(*ident)
                    },
                    Token::True => Expr::True,
                    Token::False => Expr::False,
                    _ => {
                        panic!("Error while parsing {:?}", one);
                    }
                }
            },
            in_brackets
                //if in_brackets[0] == Token::OpenParen
                //	&& in_brackets[in_brackets.len() - 1] == Token::CloseParen =>
                if is_wrapped_in_parens(in_brackets) => {
                // Trim Parentheses: "(a and b)" => "a and b"
                Expr::from_tokens(&in_brackets[1..(in_brackets.len() - 1)])
            }
            tokens => {
                // Split at binary operations, least precedence comes first
                let split_and_parse_each_half = |token: Token, expr_contructor: fn(Box<(Expr, Expr)>) -> Expr| -> Option<Expr> {
                    if let Some(index) = rposition_if_not_in_paren(tokens, token) {
                        let (left, right) = tokens.split_at(index);
                        return Some(expr_contructor(Box::new((
                            Expr::from_tokens(left),
                            Expr::from_tokens(&right[1..]), // Don't include the operator
                        ))));
                    }
                    None
                };

                if let Some(expr) = split_and_parse_each_half(Token::NotEquals, Expr::NotEquals) {
                    return expr;
                }
                if let Some(expr) = split_and_parse_each_half(Token::Equals, Expr::Equals) {
                    return expr;
                }
                if let Some(expr) = split_and_parse_each_half(Token::Or, Expr::Or) {
                    return expr;
                }
                if let Some(expr) = split_and_parse_each_half(Token::And, Expr::And) {
                    return expr;
                }
                if let Some(expr) = split_and_parse_each_half(Token::Implication, Expr::Implication) {
                    return expr;
                }
                // The Expr does not contain a binary operator. The Expr must be a Not-Expr
                assert_eq!(tokens[0], Token::Not);
                Expr::Not(Box::new(Expr::from_tokens(&tokens[1..])))
            }
        }
    }
}

/// Returns true, when the tokens start with OpenParen and ends with a matching CloseParen
/// ```
/// "(a and b)" => true
/// "(a and b) or (a and c)" => false
/// ```
fn is_wrapped_in_parens(tokens: &[Token]) -> bool {
    if tokens[0] != Token::OpenParen
        || tokens[tokens.len() - 1] != Token::CloseParen
    {
        return false;
    }
    let mut open_parens = 1;
    for token in tokens[1..(tokens.len() - 1)].iter() {
        if matches!(token, Token::OpenParen) {
            open_parens += 1;
        }
        if matches!(token, Token::CloseParen) {
            open_parens -= 1;
        }
        if open_parens == 0 {
            return false;
        }
    }
    open_parens == 1
}

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

    use super::*;

    #[test]
    fn constants() {
        let expr = Expr::from_text(" 1 or 0");
        assert_eq!(expr, Expr::Or(Box::new((Expr::True, Expr::False,))))
    }

    #[test]
    fn wrapping_parens() {
        let expr = Expr::from_text("(a and b) or (a and c)");
        assert_eq!(
            expr,
            Expr::Or(Box::new((
                Expr::And(Box::new((Expr::Ident('a'), Expr::Ident('b'),))),
                Expr::And(Box::new((Expr::Ident('a'), Expr::Ident('c'),)))
            )))
        )
    }

    #[test]
    fn parens() {
        let text = "( a or b ) and c";
        assert_eq!(
            Expr::from_text(text),
            And(Box::new((
                Or(Box::new((Ident('a'), Ident('b')))),
                Ident('c')
            )))
        );
    }

    #[test]
    fn ident() {
        let text = "a";
        assert_eq!(Expr::from_text(text), Ident('a'));
    }

    #[test]
    fn or() {
        let text = "a or b"; // Or(a, b)
        assert_eq!(
            Expr::from_text(text),
            Or(Box::new((Ident('a'), Ident('b'),)))
        );

        let text = "a or b or c"; // Or(Or(a, b), c)
        assert_eq!(
            Expr::from_text(text),
            Or(Box::new((
                Or(Box::new((Ident('a'), Ident('b')))),
                Ident('c'),
            )))
        );
    }

    #[test]
    fn and() {
        let text = "a and b"; // And(a, b)
        assert_eq!(
            Expr::from_text(text),
            And(Box::new((Ident('a'), Ident('b'),)))
        );
    }
    #[test]
    fn precedence_order() {
        let text = "a and b or c"; // (a and b) or c // And comes first
        assert_eq!(
            Expr::from_text(text),
            Or(Box::new((
                And(Box::new((Ident('a'), Ident('b')))),
                Ident('c'),
            )))
        );
    }

    #[test]
    fn not() {
        let text = "not a";
        assert_eq!(Expr::from_text(text), Not(Box::new(Ident('a'))));
    }

    #[test]
    fn chained() {
        let text = "a or b and not c"; // a or (b and (not c))
        assert_eq!(
            Expr::from_text(text),
            Or(Box::new((
                Ident('a'),
                And(Box::new((Ident('b'), Not(Box::new(Ident('c'))))))
            )))
        );

        let text = "not a and not b"; // (not a) and (not b)
        assert_eq!(
            Expr::from_text(text),
            And(Box::new((
                Not(Box::new(Ident('a'))),
                Not(Box::new(Ident('b'))),
            )))
        );
    }

    #[test]
    fn implication() {
        let s = "a -> b";
        assert_eq!(
            Expr::from_text(s),
            Expr::Implication(Box::new((Expr::Ident('a'), Expr::Ident('b'))))
        );
    }

    #[test]
    fn equals() {
        let s = "a = b";
        assert_eq!(
            Expr::from_text(s),
            Expr::Equals(Box::new((Expr::Ident('a'), Expr::Ident('b'))))
        );
    }

    #[test]
    fn not_equals() {
        let s = "a != b";
        assert_eq!(
            Expr::from_text(s),
            Expr::NotEquals(Box::new((Expr::Ident('a'), Expr::Ident('b'))))
        );
    }
}