liberty_io/

boolean.rs

// Copyright (c) 2021-2021 Thomas Kramer.
// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Parse boolean expressions as used in the liberty format.
//!
//! # Example
//! ```
//! use liberty_io::boolean::*;
//!
//! // Expression to be parsed.
//! let expression = "A & (B | C)";
//!
//! // Construct expected expression.
//! let a = BooleanExpr::Var(0);
//! let b = BooleanExpr::Var(1);
//! let c = BooleanExpr::Var(2);
//! let expected_expr = a & (b | c);
//!
//! let result = parse_boolean_function(expression.chars().peekable());
//!
//! let (parsed_expression, name_map) = result.expect("parsing failed");
//!
//! let expected_name_map = vec![
//!     "A".to_string(), "B".to_string(), "C".to_string()
//! ];
//!
//! assert_eq!(parsed_expression, expected_expr);
//! assert_eq!(name_map, expected_name_map);
//!
//! ```

use itertools::{Itertools, PeekingNext};
use libreda_stream_parser::*;
use std::ops::*;

/// Boolean expression.
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
pub enum BooleanExpr<Var> {
    /// Boolean value `False`.
    False,
    /// Boolean value `True`.
    True,
    /// Variable in an expression.
    Var(Var),
    /// Unary negation of an expression.
    Neg(Box<Self>),
    /// Binary Boolean `AND` of two expressions.
    And(Box<Self>, Box<Self>),
    /// Binary Boolean `OR` of two expressions.
    Or(Box<Self>, Box<Self>),
    /// Binary Boolean `XOR` of two expressions.
    Xor(Box<Self>, Box<Self>),
}

impl<V> From<bool> for BooleanExpr<V> {
    fn from(value: bool) -> Self {
        match value {
            false => BooleanExpr::False,
            true => BooleanExpr::True,
        }
    }
}

impl<V> BooleanExpr<V> {
    /// Evaluate the expression.
    /// Variable are passed with the callback function `value_fn`.
    /// The type `B` usually represents Boolean logic values. For example `bool` can be used.
    ///
    /// Note that `B::default()` is required to return the Boolean value `false`.
    ///
    /// # Example
    /// ```
    /// use liberty_io::boolean::*;
    ///
    /// // Create a simple boolean expression.
    /// let a = BooleanExpr::Var(0);
    /// let b = BooleanExpr::Var(1);
    /// let expr = a ^ b;
    ///
    /// let values = [true, false];
    /// assert_eq!(expr.eval(&|var| values[*var]), true);
    ///
    /// let values = [true, true];
    /// assert_eq!(expr.eval(&|var| values[*var]), false);
    /// ```
    pub fn eval<B>(&self, value_fn: &impl Fn(&V) -> B) -> B
    where
        B: Not<Output = B> + BitAnd<Output = B> + BitOr<Output = B> + BitXor<Output = B> + Default,
    {
        match self {
            BooleanExpr::False => B::default(),
            BooleanExpr::True => !B::default(),
            BooleanExpr::Var(v) => value_fn(v),
            BooleanExpr::Neg(expr) => !expr.eval(value_fn),
            BooleanExpr::And(a, b) => a.eval(value_fn) & b.eval(value_fn),
            BooleanExpr::Or(a, b) => a.eval(value_fn) | b.eval(value_fn),
            BooleanExpr::Xor(a, b) => a.eval(value_fn) ^ b.eval(value_fn),
        }
    }

    /// Substitute variables in the expression. Can also be used to change the data-type of the variables.
    /// # Example
    /// ```
    /// use liberty_io::boolean::*;
    ///
    /// // Create a simple boolean expression.
    /// let a = BooleanExpr::Var(0);
    /// let b = BooleanExpr::Var(1);
    /// let expr = a & b;
    ///
    /// // Define the variable mapping used for the substitution.
    /// let substitution = |var: &usize| -> String {
    ///    match var {
    ///       0 => "a".into(),
    ///       1 => "b".into(),
    ///       _ => panic!("no such variable")
    ///    }
    /// };
    ///
    /// // Apply the substitution.
    /// let substituted = expr.substitute_variable_names(&substitution);
    /// ```
    pub fn substitute_variable_names<V2>(
        &self,
        substitution: &impl Fn(&V) -> V2,
    ) -> BooleanExpr<V2> {
        self.substitute_variables(&|v| BooleanExpr::Var(substitution(v)))
    }

    /// Substitute all variables by an expression.
    ///
    /// # Example
    /// Replace some variables by a constant:
    /// ```
    /// use liberty_io::boolean::*;
    ///
    /// // Create a simple boolean expression.
    /// let a = BooleanExpr::Var("a");
    /// let b = BooleanExpr::Var("b");
    /// let expr = a & b;
    ///
    /// // Define the variable mapping used for the substitution.
    /// let substitution = |&var: &&'static str| -> BooleanExpr<&'static str> {
    ///    match var {
    ///       "a" => BooleanExpr::False, // Replace "a".
    ///       var => BooleanExpr::Var(var) // Don't do anything else for all other variables.
    ///    }
    /// };
    ///
    /// // Apply the substitution.
    /// let substituted = expr.substitute_variables(&substitution);
    /// ```
    pub fn substitute_variables<V2>(
        &self,
        substitution: &impl Fn(&V) -> BooleanExpr<V2>,
    ) -> BooleanExpr<V2> {
        match self {
            BooleanExpr::False => BooleanExpr::False,
            BooleanExpr::True => BooleanExpr::True,
            BooleanExpr::Var(v) => substitution(v),
            BooleanExpr::Neg(expr) => {
                BooleanExpr::Neg(Box::new(expr.substitute_variables(substitution)))
            }
            BooleanExpr::And(a, b) => BooleanExpr::And(
                Box::new(a.substitute_variables(substitution)),
                Box::new(b.substitute_variables(substitution)),
            ),
            BooleanExpr::Or(a, b) => BooleanExpr::Or(
                Box::new(a.substitute_variables(substitution)),
                Box::new(b.substitute_variables(substitution)),
            ),
            BooleanExpr::Xor(a, b) => BooleanExpr::Xor(
                Box::new(a.substitute_variables(substitution)),
                Box::new(b.substitute_variables(substitution)),
            ),
        }
    }
}

impl<V> std::fmt::Display for BooleanExpr<V>
where
    V: std::fmt::Display,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            BooleanExpr::False => write!(f, "false"),
            BooleanExpr::True => write!(f, "true"),
            BooleanExpr::Var(v) => write!(f, "{}", v),
            BooleanExpr::Neg(expr) => match expr.as_ref() {
                v @ BooleanExpr::False | v @ BooleanExpr::True => write!(f, "!{}", v),
                BooleanExpr::Var(v) => write!(f, "!{}", v), // Ommit braces.
                _ => write!(f, "!({})", expr),
            },
            BooleanExpr::And(expr1, expr2) => write!(f, "({} & {})", expr1, expr2),
            BooleanExpr::Or(expr1, expr2) => write!(f, "({} | {})", expr1, expr2),
            BooleanExpr::Xor(expr1, expr2) => write!(f, "({} ^ {})", expr1, expr2),
        }
    }
}

#[test]
fn test_eval_boolean_expr() {
    let a = BooleanExpr::Var(0);
    let b = BooleanExpr::Var(1);

    let expr = a & b;

    let values = vec![false, true];
    assert!(!expr.eval(&|v| values[*v]));

    let values = vec![true, true];
    assert!(expr.eval(&|v| values[*v]));

    // Apply the expression to a bit vector.
    let values = vec![0b1010, 0b1100];
    assert_eq!(expr.eval(&|v| values[*v]), 0b1010 & 0b1100);
}

#[test]
fn test_format_then_parse() {
    let [a, b, c, d] = std::array::from_fn(|i| {
        BooleanExpr::Var(i + 2 /* avoid using 0 and 1 as variable names*/)
    });

    let expr = !a & (b | c) ^ d;

    let formatted = format!("{}", &expr);

    let (parsed_expr, var_names) = parse_boolean_function(formatted.chars().peekable()).unwrap();
    let parsed_expr = parsed_expr.substitute_variable_names(&|v| v + 2);

    assert_eq!(expr, parsed_expr);
}

impl<V> Not for BooleanExpr<V> {
    type Output = Self;

    fn not(self) -> Self::Output {
        BooleanExpr::Neg(Box::new(self))
    }
}

impl<V> BitAnd for BooleanExpr<V> {
    type Output = Self;

    fn bitand(self, rhs: Self) -> Self::Output {
        Self::And(Box::new(self), Box::new(rhs))
    }
}

impl<V> BitOr for BooleanExpr<V> {
    type Output = Self;

    fn bitor(self, rhs: Self) -> Self::Output {
        Self::Or(Box::new(self), Box::new(rhs))
    }
}

impl<V> BitXor for BooleanExpr<V> {
    type Output = Self;

    fn bitxor(self, rhs: Self) -> Self::Output {
        Self::Xor(Box::new(self), Box::new(rhs))
    }
}

impl<V> Add for BooleanExpr<V> {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        self.bitor(rhs)
    }
}

impl<V> Mul for BooleanExpr<V> {
    type Output = Self;

    fn mul(self, rhs: Self) -> Self::Output {
        self.bitand(rhs)
    }
}

fn is_terminal_char(c: char) -> bool {
    c.is_whitespace()
        || matches!(
            c,
            '(' | ')' | '!' | '~' | '+' | '&' | '|' | '*' | '^' | '\''
        )
}

struct LibertyBooleanExpLexer {}

impl Lexer for LibertyBooleanExpLexer {
    type Char = char;

    fn consume_next_token(
        &mut self,
        input: &mut (impl Iterator<Item = Self::Char> + itertools::PeekingNext),
        mut output: impl FnMut(Self::Char),
    ) -> Result<(), ParserError<Self::Char>> {
        loop {
            // Skip whitespace.
            let _n = input.peeking_take_while(|c| c.is_whitespace()).count();

            // Look ahead.
            if let Some(c) = input.next() {
                match c {
                    '#' => {
                        // Skip comments.
                        input
                            .peeking_take_while(|&c| c != '\n' && c != '\r')
                            .count();
                    }
                    '/' => {
                        if input.peeking_next(|&c| c == '*').is_some() {
                            // Skip comment.

                            loop {
                                // Consume until next '*'.
                                input.peeking_take_while(|&c| c != '*').count();
                                if input.next() != Some('*') {
                                    break; // End of file.
                                }

                                if input.peeking_next(|&c| c == '/').is_some() {
                                    // End of comment.
                                    break;
                                }
                            }
                        } else if input.peeking_next(|&c| c == '/').is_some() {
                            // Skip comment.

                            // Consume until next '\n'.
                            input.peeking_take_while(|&c| c != '\n').count();
                        } else {
                            output(c);
                        }
                    }
                    '\\' => {
                        if input.peeking_next(|&c| c == '\\').is_some() {
                            // Ignore masked newlines.
                            output('\\');
                        } else if input.peeking_next(|&c| c == '\n').is_some() {
                            // Ignore masked newlines.
                            input.next();
                        } else if input.peeking_next(|&c| c == '\r').is_some() {
                            // Ignore masked newlines.
                            input.next();
                            if input.peeking_next(|&c| c == '\n').is_some() {
                                input.next();
                            }
                        } else {
                            output('\\');
                        }
                    }
                    _ => {
                        // Normal token.
                        let mut prev = Some(c);
                        output(c);

                        if is_terminal_char(c) {
                            return Ok(());
                        }

                        while let Some(c) = input.peeking_next(|&c| !is_terminal_char(c)) {
                            if prev != Some('\\') && (c.is_whitespace() || is_terminal_char(c)) {
                                // Abort on unmasked whitespace or terminal character.
                                break;
                            }

                            output(c);
                            prev = Some(c);
                        }
                        return Ok(());
                    }
                }
            } else {
                return Ok(());
            }
        }
    }
}

#[test]
fn test_tokenize_expression() {
    let expr = r#"
        (AA & B)|C1+D1*E1+!f+~g
    "#;

    let mut tk = tokenize(expr.chars(), LibertyBooleanExpLexer {});

    // Convert to strings.
    let token_stream = tk.map(|token| {
        let s: String = token.iter().collect();
        s
    });

    let tokens: Vec<_> = token_stream.collect();

    assert_eq!(
        tokens,
        vec![
            "(", "AA", "&", "B", ")", "|", "C1", "+", "D1", "*", "E1", "+", "!", "f", "+", "~", "g"
        ]
    );
}

/// Parse a boolean expression.
/// Return the parsed expression and a mapping of variable IDs to variable names stored as a `Vec`.
pub fn parse_boolean_function(
    chars: impl Iterator<Item = char>,
) -> Result<(BooleanExpr<usize>, Vec<String>), ParserError<char>> {
    let mut tk = tokenize(chars.peekable(), LibertyBooleanExpLexer {});

    let mut var_names: Vec<String> = vec![];

    tk.advance(); // Initialize the streaming iterator.

    let expr = parse_or_expr(&mut tk, &mut var_names)?;

    Ok((expr, var_names))
}

fn parse_or_expr<I: Iterator<Item = char> + PeekingNext>(
    tk: &mut Tokenized<I, LibertyBooleanExpLexer>,
    names: &mut Vec<String>,
) -> Result<BooleanExpr<usize>, ParserError<char>> {
    let mut or_expr = parse_and_expr(tk, names)?;
    while tk.current_token_ref().is_some() {
        if tk.test_str("+")? || tk.test_str("|")? {
            let rhs = parse_and_expr(tk, names)?;
            or_expr = BooleanExpr::Or(Box::new(or_expr), Box::new(rhs));
        } else {
            break;
        }
    }

    Ok(or_expr)
}

fn parse_and_expr<I: Iterator<Item = char> + PeekingNext>(
    tk: &mut Tokenized<I, LibertyBooleanExpLexer>,
    names: &mut Vec<String>,
) -> Result<BooleanExpr<usize>, ParserError<char>> {
    let mut and_expr = parse_xor_expr(tk, names)?;

    while let Some(t) = tk.current_token_ref() {
        let t0 = t[0];
        // "A & B", "A * B", "A B"
        if tk.test_str("&")? || tk.test_str("*")? || !"^|+)".contains(t0) {
            let rhs = parse_xor_expr(tk, names)?;
            and_expr = BooleanExpr::And(Box::new(and_expr), Box::new(rhs));
        } else {
            break;
        }
    }
    Ok(and_expr)
}

fn parse_xor_expr<I: Iterator<Item = char> + PeekingNext>(
    tk: &mut Tokenized<I, LibertyBooleanExpLexer>,
    names: &mut Vec<String>,
) -> Result<BooleanExpr<usize>, ParserError<char>> {
    let mut xor_expr = parse_atom(tk, names)?;
    while tk.current_token_ref().is_some() {
        if tk.test_str("^")? {
            let rhs = parse_atom(tk, names)?;
            xor_expr = BooleanExpr::Xor(Box::new(xor_expr), Box::new(rhs));
        } else {
            break;
        }
    }
    Ok(xor_expr)
}

fn parse_atom<I: Iterator<Item = char> + PeekingNext>(
    tk: &mut Tokenized<I, LibertyBooleanExpLexer>,
    names: &mut Vec<String>,
) -> Result<BooleanExpr<usize>, ParserError<char>> {
    let mut atom = if tk.test_str("0")? {
        BooleanExpr::False
    } else if tk.test_str("1")? {
        BooleanExpr::True
    } else if tk.test_str("!")? || tk.test_str("~")? {
        let atom = parse_atom(tk, names)?;
        BooleanExpr::Neg(Box::new(atom))
    } else if tk.test_str("(")? {
        let or_expr = parse_or_expr(tk, names)?;
        tk.expect_str(")")?;
        or_expr
    } else {
        // Variable name.
        let var_name = tk.take_str()?;

        let var_id = {
            // Convert the variable name to an integer ID.
            // Find name in the list of existing names.
            let var_id = names
                .iter()
                .enumerate()
                .find(|(idx, n)| n == &&var_name)
                .map(|(idx, _)| idx);

            // Insert the variable name if it does not exist yet.
            var_id.unwrap_or_else(|| {
                names.push(var_name);
                names.len() - 1
            })
        };

        BooleanExpr::Var(var_id)
    };

    while tk.current_token_ref().is_some() && tk.test_str("'")? {
        atom = BooleanExpr::Neg(Box::new(atom))
    }
    Ok(atom)
}

#[test]
fn test_parse_boolean_expression() {
    fn v(var_id: usize) -> BooleanExpr<usize> {
        BooleanExpr::Var(var_id)
    }

    let testcases = [
        //
        ("0", BooleanExpr::False),
        ("1", BooleanExpr::True),
        ("A", v(0)),
        ("(A)", v(0)),
        ("\t (\nA  ) ", v(0)),
        ("!A", !v(0)),
        ("!!A", !!v(0)),
        ("~A", !v(0)),
        ("A'", !v(0)),
        ("A''", !!v(0)),
        ("A B", v(0) & v(1)),
        ("x x", v(0) & v(0)),
        ("(A)(B)", v(0) & v(1)),
        ("A(B)", v(0) & v(1)),
        ("(A)B", v(0) & v(1)),
        ("A&B", v(0) & v(1)),
        ("A*B", v(0) & v(1)),
        ("A+B", v(0) | v(1)),
        ("A|B", v(0) | v(1)),
        ("(A)|(B)", v(0) | v(1)),
        ("A B C", v(0) & v(1) & v(2)),
        ("A (B C)", v(0) & (v(1) & v(2))),
        ("A | B C", v(0) | v(1) & v(2)),
        ("A B | C", v(0) & v(1) | v(2)),
        ("!A B' | ~C", !v(0) & !v(1) | !v(2)),
        (
            "(A' & ~B | !C & D & (E|A)')",
            !v(0) & !v(1) | !v(2) & v(3) & !(v(4) | v(0)),
        ),
    ];

    for (expr, expected) in testcases {
        let result = parse_boolean_function(expr.chars().peekable());

        let (parsed, name_map) = result.unwrap();

        assert_eq!(parsed, expected)
    }
}

#[test]
fn test_substitute_variables() {
    // Create a simple boolean expression.
    let a = BooleanExpr::Var(0);
    let b = BooleanExpr::Var(1);
    let c = BooleanExpr::Var(2);
    let expr = a & (b | c);

    // Define the variable mapping used for the substitution.
    let substitution = |var: &usize| -> String {
        match var {
            0 => "a".into(),
            1 => "b".into(),
            2 => "c".into(),
            _ => panic!("no such variable"),
        }
    };

    // Apply the substitution.
    let substituted = expr.substitute_variable_names(&substitution);

    // Construct a reference expression with strings as variables.
    let a = BooleanExpr::Var("a".into());
    let b = BooleanExpr::Var("b".into());
    let c = BooleanExpr::Var("c".into());
    let reference_expr = a & (b | c);

    // Check for correctness.
    assert_eq!(reference_expr, substituted);
}