temex 0.10.0

use crate::propform::PropformToken::*;
use crate::temex_error::TemexError;
use core::iter::Peekable;
use core::str::Chars;
use itertools::Itertools;
use std::iter::Iterator;
use std::str::FromStr;

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum PropformToken {
    AlphaNum(String),
    True,
    False,
    LParen,
    RParen,
    And,
    Or,
    Xor,
    Nand,
    Nor,
    Not,
    Eof,
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum PropformErrorToken {
    AlphaNum,
    LParen,
    RParen,
    And,
    Or,
    Xor,
    Nand,
    Nor,
    Not,
    Eof,
}

// Get all the boolean variables that occur in an unparsed formula.
pub fn get_boolean_vars(raw_input: &str) -> Result<Vec<String>, TemexError> {
    Ok(lex_propform(raw_input)?
        .into_iter()
        .filter_map(|x| match x {
            AlphaNum(s) => Some(s),
            _ => None,
        })
        .collect::<Vec<String>>())
}

// Throw away whitespace from the input.
fn consume_whitespace(raw_chars: &mut Peekable<Chars>) {
    for _ in raw_chars.peeking_take_while(|x| (*x).is_ascii_whitespace()) {}
}

// Lexes a propositional formula encoded as a string, returning a sequence of tokens.
pub fn lex_propform(raw_input: &str) -> Result<Vec<PropformToken>, TemexError> {
    let raw_chars = &mut raw_input.chars().peekable();
    let mut tokens: Vec<PropformToken> = vec![];

    loop {
        consume_whitespace(raw_chars);
        let ch = raw_chars.next();
        match ch {
            None => break,
            Some('(') => tokens.push(PropformToken::LParen),
            Some(')') => tokens.push(PropformToken::RParen),
            // c expected to be a keyword or a boolean variable
            Some(c) if c.is_ascii_alphabetic() => {
                let mut alpha_num_chars = vec![c];
                loop {
                    match raw_chars.peek() {
                        Some(chr) if (*chr).is_ascii_alphanumeric() || *chr == '_' => {
                            alpha_num_chars.push(*chr);
                            let _ = raw_chars.next();
                        }
                        _ => break,
                    }
                }
                let alpha_num: String = alpha_num_chars.into_iter().collect();
                // check if it's a keyword
                match alpha_num.as_str() {
                    "and" => tokens.push(PropformToken::And),
                    "or" => tokens.push(PropformToken::Or),
                    "not" => tokens.push(PropformToken::Not),
                    "nand" => tokens.push(PropformToken::Nand),
                    "xor" => tokens.push(PropformToken::Xor),
                    "nor" => tokens.push(PropformToken::Nor),
                    "true" => tokens.push(PropformToken::True),
                    "false" => tokens.push(PropformToken::False),
                    // if it's not a keyword, it's the name of a boolean variable
                    _ => tokens.push(PropformToken::AlphaNum(alpha_num)),
                }
            }
            // unexpected character
            Some(e) => return Err(TemexError::UnexpectedCharacter(e)),
        }
    }
    Ok(tokens)
}

// parser

#[derive(Debug, Eq, PartialEq, Clone)]
pub enum Propform {
    True,
    False,
    BooleanVar(String),
    And(Box<Propform>, Box<Propform>),
    Nand(Box<Propform>, Box<Propform>),
    Nor(Box<Propform>, Box<Propform>),
    Xor(Box<Propform>, Box<Propform>),
    Or(Box<Propform>, Box<Propform>),
    Not(Box<Propform>),
}

// Recursive-descent parsing of a propositional formula.
// Grammar defined as follows:
//
// Start -> P0
//
// P0 -> P1 P0'
//
// P0' ->  'and'  P0
//      |  'or'   P0
//      |  'xor'  P0
//      |  'nor'  P0
//      |  'nand' P0
//
// P1 -> 'not' P1
//     |  P2
//
// P2 -> '(' P0 ')'
//     | boolean_var
//     | 'true'
//     | 'false'
impl FromStr for Propform {
    type Err = TemexError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        // P0 -> P1 P0'
        fn pf0(tokens: &[PropformToken]) -> Result<(Propform, &[PropformToken]), TemexError> {
            // P1
            let (lhs, rest) = pf1(tokens)?;
            // P0' -> binary_op P0
            match rest.split_first() {
                Some((And, ys)) => {
                    let (rhs, rest2) = pf0(ys)?;
                    Ok((Propform::And(Box::new(lhs), Box::new(rhs)), rest2))
                }
                Some((Or, ys)) => {
                    let (rhs, rest2) = pf0(ys)?;
                    Ok((Propform::Or(Box::new(lhs), Box::new(rhs)), rest2))
                }
                Some((Xor, ys)) => {
                    let (rhs, rest2) = pf0(ys)?;
                    Ok((Propform::Xor(Box::new(lhs), Box::new(rhs)), rest2))
                }
                Some((Nor, ys)) => {
                    let (rhs, rest2) = pf0(ys)?;
                    Ok((Propform::Nor(Box::new(lhs), Box::new(rhs)), rest2))
                }
                Some((Nand, ys)) => {
                    let (rhs, rest2) = pf0(ys)?;
                    Ok((Propform::Nand(Box::new(lhs), Box::new(rhs)), rest2))
                }
                // P0' -> epsilon
                Some((RParen, _)) | None => Ok((lhs, rest)),

                Some((e, _)) => Err(TemexError::UnexpectedToken(
                    vec![
                        PropformErrorToken::And,
                        PropformErrorToken::Or,
                        PropformErrorToken::Xor,
                        PropformErrorToken::Nor,
                        PropformErrorToken::Nand,
                        PropformErrorToken::RParen,
                    ],
                    e.clone(),
                )),
            }
        }

        // P1 -> 'not' P1
        //     | P2
        fn pf1(tokens: &[PropformToken]) -> Result<(Propform, &[PropformToken]), TemexError> {
            match tokens.split_first() {
                // P1 -> not P1
                Some((Not, xs)) => {
                    let (prop, rest) = pf1(xs)?;
                    Ok((Propform::Not(Box::new(prop)), rest))
                }
                // P1 -> P2
                _ => pf2(tokens),
            }
        }

        // P2 -> '(' P0 ')'
        //     | boolean_var
        //     | 'true'
        //     | 'false'
        fn pf2(tokens: &[PropformToken]) -> Result<(Propform, &[PropformToken]), TemexError> {
            match tokens.split_first() {
                // P2 -> '(' P0 ')'
                Some((LParen, xs)) => {
                    let (prop, rest) = pf0(xs)?;
                    match rest.split_first() {
                        Some((RParen, ys)) => Ok((prop, ys)),

                        Some((e, _)) => Err(TemexError::UnexpectedToken(
                            vec![PropformErrorToken::RParen],
                            e.clone(),
                        )),
                        None => Err(TemexError::UnexpectedToken(
                            vec![PropformErrorToken::RParen],
                            Eof,
                        )),
                    }
                }
                // P2 -> boolean_var
                //     | 'true'
                //     | 'false'
                Some((AlphaNum(s), xs)) => Ok((Propform::BooleanVar(s.to_owned()), xs)),
                Some((True, xs)) => Ok((Propform::True, xs)),
                Some((False, xs)) => Ok((Propform::False, xs)),
                Some((e, _)) => Err(TemexError::UnexpectedToken(
                    vec![PropformErrorToken::RParen, PropformErrorToken::AlphaNum],
                    e.clone(),
                )),
                None => Err(TemexError::UnexpectedToken(
                    vec![PropformErrorToken::RParen, PropformErrorToken::AlphaNum],
                    Eof,
                )),
            }
        }

        let tokens = lex_propform(s)?;
        // Start -> P0
        match pf0(&tokens)? {
            (propform, []) => Ok(propform),
            (_, [e, ..]) => Err(TemexError::UnexpectedToken(
                vec![PropformErrorToken::Eof],
                e.clone(),
            )),
        }
    }
}

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

    const PROP1: &str = "p1";
    const PROP2: &str = "p1 and p2";
    const PROP3: &str = "p1 or p2";
    const PROP4: &str = "true";
    const PROP5: &str = "false";
    const PROP6: &str = "not p1";

    #[test]
    fn test1() {
        let pf1 = PROP1.to_string().parse::<Propform>().unwrap();
        let pf2 = PROP2.to_string().parse::<Propform>().unwrap();
        let pf3 = PROP3.to_string().parse::<Propform>().unwrap();
        let pf4 = PROP4.to_string().parse::<Propform>().unwrap();
        let pf5 = PROP5.to_string().parse::<Propform>().unwrap();
        let pf6 = PROP6.to_string().parse::<Propform>().unwrap();
        let p1 = Box::new(pf1.clone());
        let p2 = Box::new(BooleanVar("p2".to_string()));
        assert_eq!(pf1, BooleanVar("p1".to_string()));
        assert_eq!(pf2, And(p1.clone(), p2.clone()));
        assert_eq!(pf3, Or(p1.clone(), p2.clone()));
        assert_eq!(pf4, True);
        assert_eq!(pf5, False);
        assert_eq!(pf6, Not(p1.clone()));
    }
}