Simple boolean expression parser

README.md

A parser designed to parse extremely simple boolean logic expressions. Expressions may contain boolean literals, C style identifiers (which represent runtime booleans), and a few boolean logic operators.

Some example expressions:

• true
• a | b
• a & (b | c)
• a & !(b | c)
• !a & !b & !c

It is implemented in Nom using the following grammar as a reference (whitespace not included for clarity):

expr        -> or_term
or_term     -> and_term ("|" and_term)*
and_term    -> term_or_not ("&" term_or_not)*
term_or_not -> not_term | term 
not_term    -> "!" term
term        -> "(" or_term ")" | bool_lit | ident
bool_lit    -> "true" !ident_inner | "false" !ident_inner
ident       -> ident_front ident_inner*
ident_front -> [_a-zA-Z]
ident_inner -> [_a-zA-Z0-9]

Open questions:

• I don't like the way the operator precedence is enforced via the recursive functions. I'm wondering, is it possible to implement operator precedence in a more maintainable way?
• There is a hack in ExpressionError::new() which handles the case where the expr() parser returns UnexpectedSymbol when it should return UnexpectedEOF due to input being zero length

mod.rs

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::{alpha1, alphanumeric1, multispace0},
    combinator::{all_consuming, cut, map, not, recognize},
    multi::{fold_many0, many0, many1},
    sequence::{pair, preceded, terminated},
    Finish, IResult, Offset, Parser,
};

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum Token<'a> {
    Bool(bool),
    Ident(&'a str),
    And(Box<Token<'a>>, Box<Token<'a>>),
    Or(Box<Token<'a>>, Box<Token<'a>>),
    Not(Box<Token<'a>>),
}

#[derive(Debug, PartialEq, Clone, Copy)]
pub enum Specific {
    InternalError = 0,
    UnexpectedEOF,
    UnexpectedSymbol,
    ExpectEnclosedExpression,
    ExpectClosingParenthesis,
    ExpectNotExpression,
    ExpectAndExpression,
    ExpectOrExpression,
}

pub struct LineAndColumn {
    line: usize,
    column: usize,
}

trait SpecificError<I>: Sized {
    fn add_specific(input: I, kind: Specific, other: Self) -> Self;
}

fn specific<I, E, F, O>(kind: Specific, mut f: F) -> impl FnMut(I) -> IResult<I, O, E>
where
    F: Parser<I, O, E>,
    I: Clone,
    E: SpecificError<I>,
{
    move |i: I| match f.parse(i.clone()) {
        Ok(o) => Ok(o),
        Err(nom::Err::Incomplete(input)) => Err(nom::Err::Incomplete(input)),
        Err(nom::Err::Error(e)) => Err(nom::Err::Error(E::add_specific(i, kind, e))),
        Err(nom::Err::Failure(e)) => Err(nom::Err::Failure(E::add_specific(i, kind, e))),
    }
}

#[derive(Debug, PartialEq)]
pub struct ExpressionError<'a> {
    location: &'a str,
    kind: Specific,
}

impl<'a> ExpressionError<'a> {
    fn new(location: &'a str, kind: Specific) -> Self {
        // Check for EOF
        // #HACK This is a bit of a hack as I'm not sure how to convince the
        // expr() function to distinguish between unexpected symbols and EOF
        let mut kind = kind;
        if kind == Specific::UnexpectedSymbol && location.len() == 0 {
            kind = Specific::UnexpectedEOF;
        }

        Self { location, kind }
    }

    fn need_context(&self) -> bool {
        self.kind == Specific::InternalError
    }

    pub fn get_line_and_column_number(&self, input: &'a str) -> LineAndColumn {
        // Borrowed and truncated from nom::error::convert_error
        let offset = input.offset(self.location);
        let prefix = &input.as_bytes()[..offset];
        let line_number = prefix.iter().filter(|&&b| b == b'\n').count() + 1;
        let line_begin = prefix
            .iter()
            .rev()
            .position(|&b| b == b'\n')
            .map(|pos| offset - pos)
            .unwrap_or(0);
        let line = input[line_begin..]
            .lines()
            .next()
            .unwrap_or(&input[line_begin..])
            .trim_end();
        let column_number = line.offset(self.location) + 1;
        LineAndColumn {
            line: line_number,
            column: column_number,
        }
    }

    pub fn get_error_message(&self) -> String {
        let error_message = match self.kind {
            Specific::InternalError => "Nom parser error",
            Specific::UnexpectedEOF => "Unexpected end of file",
            Specific::UnexpectedSymbol => "Unexpected symbol",
            Specific::ExpectEnclosedExpression => {
                "Expected expression after opening '(' parenthesis"
            }
            Specific::ExpectClosingParenthesis => {
                "Expected closing ')' parenthesis after expression"
            }
            Specific::ExpectNotExpression => "Expected expression after '!' operator",
            Specific::ExpectAndExpression => "Expected expression after '&' operator",
            Specific::ExpectOrExpression => "Expected expression after '|' operator",
        };

        if self.location.len() > 0 {
            format!(
                "{} - found '{}'",
                error_message,
                self.location.chars().next().unwrap()
            )
        } else {
            format!("{}", error_message)
        }
    }
}

impl<'a> nom::error::ParseError<&'a str> for ExpressionError<'a> {
    fn from_error_kind(input: &'a str, _kind: nom::error::ErrorKind) -> Self {
        Self::new(input, Specific::InternalError)
    }

    fn append(_input: &'a str, _kind: nom::error::ErrorKind, error: Self) -> Self {
        error
    }
}

impl<'a> SpecificError<&'a str> for ExpressionError<'a> {
    fn add_specific(_input: &'a str, context: Specific, error: Self) -> Self {
        if error.need_context() {
            Self::new(error.location, context)
        } else {
            error
        }
    }
}

// Main module entry point
pub fn parse(expression: &str) -> Result<Token, ExpressionError> {
    match expr(expression).finish() {
        Ok((_, t)) => Ok(t),
        Err(e) => Err(e),
    }
}

fn ws_tag<'a, E>(t: &'a str) -> impl FnMut(&'a str) -> IResult<&'a str, &'a str, E>
where
    E: nom::error::ParseError<&'a str>,
{
    preceded(multispace0, tag(t))
}

fn ident_primary_char<'a, E>(input: &'a str) -> IResult<&'a str, &'a str, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    alt((alpha1, tag("_")))(input)
}

fn ident_secondary_char<'a, E>(input: &'a str) -> IResult<&'a str, &'a str, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    alt((alphanumeric1, tag("_")))(input)
}

fn bool_lit<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    preceded(
        multispace0,
        alt((
            map(terminated(tag("true"), not(ident_secondary_char)), |_| {
                Token::Bool(true)
            }),
            map(terminated(tag("false"), not(ident_secondary_char)), |_| {
                Token::Bool(false)
            }),
        )),
    )(input)
}

fn ident<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    map(
        preceded(
            multispace0,
            recognize(pair(many1(ident_primary_char), many0(ident_secondary_char))),
        ),
        Token::Ident,
    )(input)
}

fn term<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    alt((
        preceded(
            ws_tag("("),
            cut(terminated(
                specific(Specific::ExpectEnclosedExpression, or_term),
                specific(Specific::ExpectClosingParenthesis, ws_tag(")")),
            )),
        ),
        bool_lit,
        ident,
    ))(input)
}

fn not_term<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    map(
        preceded(
            ws_tag("!"),
            cut(specific(Specific::ExpectNotExpression, term)),
        ),
        |t| Token::Not(Box::new(t)),
    )(input)
}

fn term_or_not_term<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    alt((not_term, term))(input)
}

fn and_term<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    // Here we cache init as Option so that we can explicitly transfer ownership via take()
    let (input, init) = term_or_not_term(input)?;
    let mut init = Some(init);
    fold_many0(
        preceded(
            ws_tag("&"),
            cut(specific(Specific::ExpectAndExpression, term_or_not_term)),
        ),
        move || init.take().unwrap(),
        |a, b| Token::And(Box::new(a), Box::new(b)),
    )(input)
}

fn or_term<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    // Here we cache init as Option so that we can explicitly transfer ownership via take()
    let (input, init) = and_term(input)?;
    let mut init = Some(init);
    fold_many0(
        preceded(
            ws_tag("|"),
            cut(specific(Specific::ExpectOrExpression, and_term)),
        ),
        move || init.take().unwrap(),
        |a, b| Token::Or(Box::new(a), Box::new(b)),
    )(input)
}

fn expr<'a, E>(input: &'a str) -> IResult<&'a str, Token, E>
where
    E: nom::error::ParseError<&'a str> + SpecificError<&'a str>,
{
    specific(
        // May be translated to UnexpectedEOF if location.len() == 0 - See HACK above
        Specific::UnexpectedSymbol,
        all_consuming(terminated(or_term, multispace0)),
    )(input)
}

#[cfg(test)]
mod tests {
    use super::{parse, ExpressionError, Specific, Token};

    fn expect_error<'a>(
        kind: Specific,
        location: &'a str,
    ) -> Result<Token<'a>, ExpressionError<'a>> {
        Err(ExpressionError::new(location, kind))
    }

    fn expect_bool_lit<'a>(value: bool) -> Result<Token<'a>, ExpressionError<'a>> {
        Ok(Token::Bool(value))
    }

    fn expect_ident<'a>(ident: &'a str) -> Result<Token<'a>, ExpressionError<'a>> {
        Ok(Token::Ident(ident))
    }

    fn expect_not_ident<'a>(ident: &'a str) -> Result<Token<'a>, ExpressionError<'a>> {
        Ok(Token::Not(Box::new(Token::Ident(ident))))
    }

    fn expect_and_idents2<'a>(
        ident_a: &'a str,
        ident_b: &'a str,
    ) -> Result<Token<'a>, ExpressionError<'a>> {
        Ok(Token::And(
            Box::new(Token::Ident(ident_a)),
            Box::new(Token::Ident(ident_b)),
        ))
    }

    fn expect_and_idents3<'a>(
        ident_a: &'a str,
        ident_b: &'a str,
        ident_c: &'a str,
    ) -> Result<Token<'a>, ExpressionError<'a>> {
        Ok(Token::And(
            Box::new(Token::And(
                Box::new(Token::Ident(ident_a)),
                Box::new(Token::Ident(ident_b)),
            )),
            Box::new(Token::Ident(ident_c)),
        ))
    }

    fn expect_or_idents2<'a>(
        ident_a: &'a str,
        ident_b: &'a str,
    ) -> Result<Token<'a>, ExpressionError<'a>> {
        Ok(Token::Or(
            Box::new(Token::Ident(ident_a)),
            Box::new(Token::Ident(ident_b)),
        ))
    }

    fn expect_or_idents3<'a>(
        ident_a: &'a str,
        ident_b: &'a str,
        ident_c: &'a str,
    ) -> Result<Token<'a>, ExpressionError<'a>> {
        Ok(Token::Or(
            Box::new(Token::Or(
                Box::new(Token::Ident(ident_a)),
                Box::new(Token::Ident(ident_b)),
            )),
            Box::new(Token::Ident(ident_c)),
        ))
    }

    #[test]
    fn test_unexpected_eof_errors() {
        // Expressions have to contain something
        assert_eq!(parse(""), expect_error(Specific::UnexpectedEOF, ""));
        assert_eq!(parse("  "), expect_error(Specific::UnexpectedEOF, ""));
    }

    #[test]
    fn test_unexpected_symbol_errors() {
        // Simple unexpected symbols
        assert_eq!(parse("%"), expect_error(Specific::UnexpectedSymbol, "%"));
        assert_eq!(
            parse("123"),
            expect_error(Specific::UnexpectedSymbol, "123")
        );
        assert_eq!(
            parse("123ident"),
            expect_error(Specific::UnexpectedSymbol, "123ident")
        );
        assert_eq!(
            parse("  %  "),
            expect_error(Specific::UnexpectedSymbol, "%  ")
        );
        assert_eq!(
            parse("  123  "),
            expect_error(Specific::UnexpectedSymbol, "123  ")
        );
        assert_eq!(
            parse("  123ident  "),
            expect_error(Specific::UnexpectedSymbol, "123ident  ")
        );

        // First part is valid, second part is unexpected
        assert_eq!(parse("a %"), expect_error(Specific::UnexpectedSymbol, "%"));
        assert_eq!(
            parse("a 123"),
            expect_error(Specific::UnexpectedSymbol, "123")
        );
        assert_eq!(
            parse("a 123ident"),
            expect_error(Specific::UnexpectedSymbol, "123ident")
        );
        assert_eq!(
            parse("  a  %  "),
            expect_error(Specific::UnexpectedSymbol, "%  ")
        );
        assert_eq!(
            parse("  a  123  "),
            expect_error(Specific::UnexpectedSymbol, "123  ")
        );
        assert_eq!(
            parse("  a  123ident  "),
            expect_error(Specific::UnexpectedSymbol, "123ident  ")
        );
    }

    #[test]
    fn test_expect_enclosed_expression_errors() {
        // Testing for missing expression between inner most '(' parentheses ')'
        // Note that ExpectEnclosedExpression is more informative than UnexpectedEOF here
        assert_eq!(
            parse("("),
            expect_error(Specific::ExpectEnclosedExpression, "")
        );
        assert_eq!(
            parse("()"),
            expect_error(Specific::ExpectEnclosedExpression, ")")
        );
        assert_eq!(
            parse("(())"),
            expect_error(Specific::ExpectEnclosedExpression, "))")
        );
        assert_eq!(
            parse("  (  "),
            expect_error(Specific::ExpectEnclosedExpression, "")
        );
        assert_eq!(
            parse("  (  )  "),
            expect_error(Specific::ExpectEnclosedExpression, ")  ")
        );
        assert_eq!(
            parse("  (  (  )  )  "),
            expect_error(Specific::ExpectEnclosedExpression, ")  )  ")
        );

        // Throw in some unexpected symbols into an otherwise valid expression
        // Note that ExpectEnclosedExpression is more informative than UnexpectedSymbol here
        assert_eq!(
            parse("(%"),
            expect_error(Specific::ExpectEnclosedExpression, "%")
        );
        assert_eq!(
            parse("(%)"),
            expect_error(Specific::ExpectEnclosedExpression, "%)")
        );
        assert_eq!(
            parse("((%))"),
            expect_error(Specific::ExpectEnclosedExpression, "%))")
        );
        assert_eq!(
            parse("  (  %"),
            expect_error(Specific::ExpectEnclosedExpression, "%")
        );
        assert_eq!(
            parse("  (  %  )  "),
            expect_error(Specific::ExpectEnclosedExpression, "%  )  ")
        );
        assert_eq!(
            parse("  (  (  %  )  )  "),
            expect_error(Specific::ExpectEnclosedExpression, "%  )  )  ")
        );
    }

    #[test]
    fn test_expect_closing_parenthesis_errors() {
        // Testing for missing closing ')' parenthesis
        // Note that ExpectClosingParenthesis is more informative than UnexpectedEOF here
        assert_eq!(
            parse("(a"),
            expect_error(Specific::ExpectClosingParenthesis, "")
        );
        assert_eq!(
            parse("((a)"),
            expect_error(Specific::ExpectClosingParenthesis, "")
        );
        assert_eq!(
            parse("  (  a  "),
            expect_error(Specific::ExpectClosingParenthesis, "")
        );
        assert_eq!(
            parse("  ((  a  )  "),
            expect_error(Specific::ExpectClosingParenthesis, "")
        );

        // Throw in some unexpected symbols into an otherwise valid expression
        // Note that ExpectClosingParenthesis is more informative than UnexpectedSymbol here
        assert_eq!(
            parse("(a%)"),
            expect_error(Specific::ExpectClosingParenthesis, "%)")
        );
        assert_eq!(
            parse("((a)%)"),
            expect_error(Specific::ExpectClosingParenthesis, "%)")
        );
        assert_eq!(
            parse("  (  a  %  )  "),
            expect_error(Specific::ExpectClosingParenthesis, "%  )  ")
        );
        assert_eq!(
            parse("  ((  a  )  %  )  "),
            expect_error(Specific::ExpectClosingParenthesis, "%  )  ")
        );
    }

    #[test]
    fn test_expect_not_expression_errors() {
        // Testing for missing expression after '!' operator
        // Note that ExpectNotExpression is more informative than UnexpectedEOF here
        assert_eq!(parse("!"), expect_error(Specific::ExpectNotExpression, ""));
        assert_eq!(
            parse("  !  "),
            expect_error(Specific::ExpectNotExpression, "")
        );

        // Throw in some unexpected symbols into an otherwise valid expression
        // Note that ExpectNotExpression is more informative than UnexpectedSymbol here
        assert_eq!(
            parse("!%a"),
            expect_error(Specific::ExpectNotExpression, "%a")
        );
        assert_eq!(
            parse("  !  %  a  "),
            expect_error(Specific::ExpectNotExpression, "%  a  ")
        );
    }

    #[test]
    fn test_expect_and_expression_errors() {
        // Testing for missing expression after '&' operator
        // Note that ExpectAndExpression is more informative than UnexpectedEOF here
        assert_eq!(parse("a&"), expect_error(Specific::ExpectAndExpression, ""));
        assert_eq!(
            parse("(a&)"),
            expect_error(Specific::ExpectAndExpression, ")")
        );
        assert_eq!(
            parse("  a  &  "),
            expect_error(Specific::ExpectAndExpression, "")
        );
        assert_eq!(
            parse("  (  a  &  )  "),
            expect_error(Specific::ExpectAndExpression, ")  ")
        );

        // Throw in some unexpected symbols into an otherwise valid expression
        // Note that ExpectAndExpression is more informative than UnexpectedSymbol here
        assert_eq!(
            parse("a&%b"),
            expect_error(Specific::ExpectAndExpression, "%b")
        );
        assert_eq!(
            parse("(a&%b)"),
            expect_error(Specific::ExpectAndExpression, "%b)")
        );
        assert_eq!(
            parse("  a  &  %  b  "),
            expect_error(Specific::ExpectAndExpression, "%  b  ")
        );
        assert_eq!(
            parse("  (  a  &  %  b  )  "),
            expect_error(Specific::ExpectAndExpression, "%  b  )  ")
        );
    }

    #[test]
    fn test_expect_or_expression_errors() {
        // Testing for missing expression after '|' operator
        // Note that ExpectOrExpression is more informative than UnexpectedEOF here
        assert_eq!(parse("a|"), expect_error(Specific::ExpectOrExpression, ""));
        assert_eq!(
            parse("(a|)"),
            expect_error(Specific::ExpectOrExpression, ")")
        );
        assert_eq!(
            parse("  a  |  "),
            expect_error(Specific::ExpectOrExpression, "")
        );
        assert_eq!(
            parse("  (  a  |  )  "),
            expect_error(Specific::ExpectOrExpression, ")  ")
        );

        // Throw in some unexpected symbols into an otherwise valid expression
        // Note that ExpectOrExpression is more informative than UnexpectedSymbol here
        assert_eq!(
            parse("a|%b"),
            expect_error(Specific::ExpectOrExpression, "%b")
        );
        assert_eq!(
            parse("(a|%b)"),
            expect_error(Specific::ExpectOrExpression, "%b)")
        );
        assert_eq!(
            parse("  a  |  %  b  "),
            expect_error(Specific::ExpectOrExpression, "%  b  ")
        );
        assert_eq!(
            parse("  (  a  |  %  b  )  "),
            expect_error(Specific::ExpectOrExpression, "%  b  )  ")
        );
    }

    #[test]
    fn test_bool_literals() {
        // Various valid keywords with whitespace versions
        assert_eq!(parse("true"), expect_bool_lit(true));
        assert_eq!(parse("false"), expect_bool_lit(false));
        assert_eq!(parse("  true  "), expect_bool_lit(true));
        assert_eq!(parse("  false  "), expect_bool_lit(false));

        // Various permutations with parentheses
        assert_eq!(parse("(true)"), expect_bool_lit(true));
        assert_eq!(parse("(false)"), expect_bool_lit(false));
        assert_eq!(parse("  (true)  "), expect_bool_lit(true));
        assert_eq!(parse("  (false)  "), expect_bool_lit(false));
    }

    #[test]
    fn test_idents() {
        // Various valid idents with whitespace versions
        assert_eq!(parse("_"), expect_ident("_"));
        assert_eq!(parse("ident_a"), expect_ident("ident_a"));
        assert_eq!(parse("IDENT_A"), expect_ident("IDENT_A"));
        assert_eq!(parse("IDENT_A_123"), expect_ident("IDENT_A_123"));
        assert_eq!(parse("  _  "), expect_ident("_"));
        assert_eq!(parse("  ident_a  "), expect_ident("ident_a"));
        assert_eq!(parse("  IDENT_A  "), expect_ident("IDENT_A"));
        assert_eq!(parse("  IDENT_A_123  "), expect_ident("IDENT_A_123"));

        // Various permutations with parentheses
        assert_eq!(parse("(_)"), expect_ident("_"));
        assert_eq!(parse("(ident_a)"), expect_ident("ident_a"));
        assert_eq!(parse("(IDENT_A)"), expect_ident("IDENT_A"));
        assert_eq!(parse("(IDENT_A_123)"), expect_ident("IDENT_A_123"));
        assert_eq!(parse("  (  _  )  "), expect_ident("_"));
        assert_eq!(parse("  (  ident_a  )  "), expect_ident("ident_a"));
        assert_eq!(parse("  (  IDENT_A  )  "), expect_ident("IDENT_A"));
        assert_eq!(parse("  (  IDENT_A_123  )  "), expect_ident("IDENT_A_123"));
    }

    #[test]
    fn test_simple_not_terms() {
        // Various valid simple not terms
        assert_eq!(parse("!a"), expect_not_ident("a"));
        assert_eq!(parse("  !  a  "), expect_not_ident("a"));

        // Various permutations with parentheses
        assert_eq!(parse("!(a)"), expect_not_ident("a"));
        assert_eq!(parse("(!a)"), expect_not_ident("a"));
        assert_eq!(parse("(!(a))"), expect_not_ident("a"));
        assert_eq!(parse("  !  (  a  )  "), expect_not_ident("a"));
        assert_eq!(parse("  (  !  a  )  "), expect_not_ident("a"));
        assert_eq!(parse("  (  !  (  a  )  )  "), expect_not_ident("a"));
    }

    #[test]
    fn test_simple_and_terms() {
        // Various valid simple and terms
        assert_eq!(parse("a&b"), expect_and_idents2("a", "b"));
        assert_eq!(parse("a&b&c"), expect_and_idents3("a", "b", "c"));
        assert_eq!(parse("  a  &  b  "), expect_and_idents2("a", "b"));
        assert_eq!(
            parse("  a  &  b  &  c  "),
            expect_and_idents3("a", "b", "c")
        );

        // Various permutations with parentheses
        assert_eq!(parse("a&(b)"), expect_and_idents2("a", "b"));
        assert_eq!(parse("(a)&b"), expect_and_idents2("a", "b"));
        assert_eq!(parse("(a)&(b)"), expect_and_idents2("a", "b"));
        assert_eq!(parse("(a&(b))"), expect_and_idents2("a", "b"));
        assert_eq!(parse("((a)&b)"), expect_and_idents2("a", "b"));
        assert_eq!(parse("((a)&(b))"), expect_and_idents2("a", "b"));
        assert_eq!(parse("  a  &  (  b  )  "), expect_and_idents2("a", "b"));
        assert_eq!(parse("  (  a  )  &  b  "), expect_and_idents2("a", "b"));
        assert_eq!(
            parse("  (  a  )  &  (  b  )  "),
            expect_and_idents2("a", "b")
        );
        assert_eq!(
            parse("  (  a  &  (  b  )  )  "),
            expect_and_idents2("a", "b")
        );
        assert_eq!(
            parse("  (  (  a  )  &  b  )  "),
            expect_and_idents2("a", "b")
        );
        assert_eq!(
            parse("  (  (  a  )  &  (  b  )  )  "),
            expect_and_idents2("a", "b")
        );
    }

    #[test]
    fn test_simple_or_terms() {
        // Various valid simple or terms
        assert_eq!(parse("a|b"), expect_or_idents2("a", "b"));
        assert_eq!(parse("a|b|c"), expect_or_idents3("a", "b", "c"));
        assert_eq!(parse("  a  |  b  "), expect_or_idents2("a", "b"));
        assert_eq!(parse("  a  |  b  |  c  "), expect_or_idents3("a", "b", "c"));

        // Various permutations with parentheses
        assert_eq!(parse("a|(b)"), expect_or_idents2("a", "b"));
        assert_eq!(parse("(a)|b"), expect_or_idents2("a", "b"));
        assert_eq!(parse("(a)|(b)"), expect_or_idents2("a", "b"));
        assert_eq!(parse("(a|(b))"), expect_or_idents2("a", "b"));
        assert_eq!(parse("((a)|b)"), expect_or_idents2("a", "b"));
        assert_eq!(parse("((a)|(b))"), expect_or_idents2("a", "b"));
        assert_eq!(parse("  a  |  (  b  )  "), expect_or_idents2("a", "b"));
        assert_eq!(parse("  (  a  )  |  b  "), expect_or_idents2("a", "b"));
        assert_eq!(
            parse("  (  a  )  |  (  b  )  "),
            expect_or_idents2("a", "b")
        );
        assert_eq!(
            parse("  (  a  |  (  b  )  )  "),
            expect_or_idents2("a", "b")
        );
        assert_eq!(
            parse("  (  (  a  )  |  b  )  "),
            expect_or_idents2("a", "b")
        );
        assert_eq!(
            parse("  (  (  a  )  |  (  b  )  )  "),
            expect_or_idents2("a", "b")
        );
    }

    #[test]
    fn test_complex_and_or_not_operators() {
        // Check basic precedence
        assert_eq!(
            parse("a & b | c"),
            Ok(Token::Or(
                Box::new(Token::And(
                    Box::new(Token::Ident("a")),
                    Box::new(Token::Ident("b"))
                )),
                Box::new(Token::Ident("c"))
            ))
        );
        assert_eq!(
            parse("a | b & c"),
            Ok(Token::Or(
                Box::new(Token::Ident("a")),
                Box::new(Token::And(
                    Box::new(Token::Ident("b")),
                    Box::new(Token::Ident("c"))
                ))
            ))
        );

        // Using parenthesis to force precedence
        assert_eq!(
            parse("a & (b | c)"),
            Ok(Token::And(
                Box::new(Token::Ident("a")),
                Box::new(Token::Or(
                    Box::new(Token::Ident("b")),
                    Box::new(Token::Ident("c"))
                ))
            ))
        );
        assert_eq!(
            parse("(a | b) & c"),
            Ok(Token::And(
                Box::new(Token::Or(
                    Box::new(Token::Ident("a")),
                    Box::new(Token::Ident("b"))
                )),
                Box::new(Token::Ident("c"))
            ))
        );

        // Throw in a few nots for good measure
        assert_eq!(
            parse("a & (!b | c)"),
            Ok(Token::And(
                Box::new(Token::Ident("a")),
                Box::new(Token::Or(
                    Box::new(Token::Not(Box::new(Token::Ident("b")))),
                    Box::new(Token::Ident("c"))
                ))
            ))
        );

        assert_eq!(
            parse("(!a | b) & c"),
            Ok(Token::And(
                Box::new(Token::Or(
                    Box::new(Token::Not(Box::new(Token::Ident("a")))),
                    Box::new(Token::Ident("b")),
                )),
                Box::new(Token::Ident("c"))
            ))
        );

        assert_eq!(
            parse("!(a | b) & c"),
            Ok(Token::And(
                Box::new(Token::Not(Box::new(Token::Or(
                    Box::new(Token::Ident("a")),
                    Box::new(Token::Ident("b")),
                )))),
                Box::new(Token::Ident("c"))
            ))
        );

        assert_eq!(
            parse("!(a | b & c)"),
            Ok(Token::Not(Box::new(Token::Or(
                Box::new(Token::Ident("a")),
                Box::new(Token::And(
                    Box::new(Token::Ident("b")),
                    Box::new(Token::Ident("c")),
                ))
            ))))
        );
    }

    #[test]
    fn test_complex_and_or_not_operators_bools() {
        // We also need to make sure bools can be used in place of idents
        // Kinda hard/impossible to test this exhaustively
        // Maybe an algorithmic approach could be better
        assert_eq!(
            parse("a & b | true"),
            Ok(Token::Or(
                Box::new(Token::And(
                    Box::new(Token::Ident("a")),
                    Box::new(Token::Ident("b"))
                )),
                Box::new(Token::Bool(true))
            ))
        );
        assert_eq!(
            parse("true | a & false"),
            Ok(Token::Or(
                Box::new(Token::Bool(true)),
                Box::new(Token::And(
                    Box::new(Token::Ident("a")),
                    Box::new(Token::Bool(false))
                )),
            ))
        );
    }
}