use anyhow::{Result, bail};
use memoize::memoize;
use stacksafe::{StackSafe, stacksafe};
use std::{fmt::Debug, rc::Rc};

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum BoolTree {
    True,
    False,
    Neg(StackSafe<Rc<BoolTree>>),
    And(StackSafe<Rc<BoolTree>>, StackSafe<Rc<BoolTree>>),
    Or(StackSafe<Rc<BoolTree>>, StackSafe<Rc<BoolTree>>),
    Paren(StackSafe<Rc<BoolTree>>),
}

#[memoize]
pub fn evaluate_tree(tree: BoolTree) -> bool {
    match tree {
        BoolTree::True => true,
        BoolTree::False => false,
        BoolTree::Neg(a) => !evaluate_tree(a.as_ref().clone()),
        BoolTree::And(a, b) => {
            evaluate_tree(a.as_ref().clone()) & evaluate_tree(b.as_ref().clone())
        }
        BoolTree::Or(a, b) => evaluate_tree(a.as_ref().clone()) | evaluate_tree(b.as_ref().clone()),
        BoolTree::Paren(a) => evaluate_tree(a.as_ref().clone()),
    }
}

impl BoolTree {
    #[stacksafe]
    pub fn evaluate(&self) -> bool {
        evaluate_tree(self.clone())
    }
}

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum Token {
    True,
    False,
    Or,
    And,
    Not,
    LeftParen,
    RightParen,
}

impl Debug for Token {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::True => write!(f, "1"),
            Self::False => write!(f, "0"),
            Self::Or => write!(f, "|"),
            Self::And => write!(f, "&"),
            Self::Not => write!(f, "!"),
            Self::LeftParen => write!(f, "("),
            Self::RightParen => write!(f, ")"),
        }
    }
}

//
// expression := or;
// or         := and "|" or
//               | and;
// and        := not "&" and
//               | not;
// not        := "!" not
//               | terminal;
// terminal   := "1"
//               | "0"
//               | "(" expression ")";
//

#[stacksafe]
pub fn parse_or(computation: &[Token]) -> Result<(&[Token], BoolTree)> {
    let and_parse = parse_and(computation)?;

    if and_parse.0.iter().next() == Some(&Token::Or) {
        let (remainder, subtree) = parse_or(&and_parse.0[1..])?;
        Ok((
            remainder,
            BoolTree::Or(Rc::new(and_parse.1).into(), Rc::new(subtree).into()),
        ))
    } else {
        Ok(and_parse)
    }
}

#[stacksafe]
pub fn parse_and(computation: &[Token]) -> Result<(&[Token], BoolTree)> {
    let not_parse = parse_not(computation)?;

    if not_parse.0.iter().next() == Some(&Token::And) {
        let (remainder, subtree) = parse_and(&not_parse.0[1..])?;
        Ok((
            remainder,
            BoolTree::And(Rc::new(not_parse.1).into(), Rc::new(subtree).into()),
        ))
    } else {
        Ok(not_parse)
    }
}

#[stacksafe]
pub fn parse_not(computation: &[Token]) -> Result<(&[Token], BoolTree)> {
    if computation.iter().next() == Some(&Token::Not) {
        let (remainder, subtree) = parse_not(&computation[1..])?;
        Ok((remainder, BoolTree::Neg(Rc::new(subtree).into())))
    } else {
        parse_terminal(computation)
    }
}

#[stacksafe]
pub fn parse_terminal(computation: &[Token]) -> Result<(&[Token], BoolTree)> {
    if computation.is_empty() {
        bail!("No tokens left!");
    }

    let next_bit = &computation[1..];
    if computation[0] == Token::True {
        Ok((next_bit, BoolTree::True))
    } else if computation[0] == Token::False {
        Ok((next_bit, BoolTree::False))
    } else if computation[0] == Token::LeftParen {
        let (remainder, subtree) = parse_expression(&computation[1..])?;
        if remainder.iter().next() != Some(&Token::RightParen) {
            bail!("Mismatched parentheses.");
        }
        Ok((&remainder[1..], BoolTree::Paren(Rc::new(subtree).into())))
    } else {
        bail!("Invalid next token: {computation:?}");
    }
}

#[stacksafe]
pub fn parse_expression(computation: &[Token]) -> Result<(&[Token], BoolTree)> {
    parse_or(computation)
}

pub fn tokenize(computation: &str) -> Result<Vec<Token>> {
    let mut tokens = Vec::new();
    for c in computation.chars() {
        use Token::*;

        tokens.push(match c {
            '1' => True,
            '0' => False,
            '|' => Or,
            '&' => And,
            '!' => Not,
            '(' => LeftParen,
            ')' => RightParen,
            c if c.is_whitespace() => continue,
            _ => bail!("Failed to parse character: {c}"),
        })
    }

    Ok(tokens)
}

pub fn evaluate(computation: &str) -> Result<bool> {
    let tokens = tokenize(computation)?;

    let (output, tree) = parse_expression(&tokens)?;
    if !output.is_empty() {
        bail!("Non-empty remainder string: {computation:?}")
    } else {
        Ok(tree.evaluate())
    }
}

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

    #[test]
    pub fn test_evaluate() {
        // Terminal
        assert!(!evaluate("0").unwrap());
        assert!(evaluate("1").unwrap());

        // Not
        assert!(!evaluate("!1").unwrap());
        assert!(evaluate("!0").unwrap());
        assert!(!evaluate("!!0").unwrap());
        assert!(evaluate("!!1").unwrap());

        // And
        assert!(!evaluate("!1 & 1").unwrap());
        assert!(!evaluate("!0 & 0").unwrap());
        assert!(!evaluate("0 & 1").unwrap());

        // Or
        assert!(evaluate("!1 | 1").unwrap());
        assert!(!evaluate("0 | 0").unwrap());
        assert!(evaluate("0 | 1").unwrap());

        // Expression
        assert!(!evaluate("(1 | 0) & 1 & 0").unwrap());
        assert!(evaluate("(1 | 0) & (1 | 1)").unwrap());
        assert!(!evaluate("(1 | 0) & !(1 | 1)").unwrap());
        assert!(evaluate("1 | 1 | 0").unwrap());

        assert!(evaluate("0 | 0 |  | 1 | 0 | 1 | 0").unwrap());
    }
}
