use std::collections::HashMap;
use super::utils::split_token;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum BoolExpression {
And(Box<BoolExpression>, Box<BoolExpression>),
Or(Box<BoolExpression>, Box<BoolExpression>),
Not(Box<BoolExpression>),
Var(String),
Literal(bool),
}
impl BoolExpression {
#[must_use]
pub fn evaluate(&self, context: &HashMap<String, bool>) -> bool {
match self {
Self::And(left, right) => left.evaluate(context) && right.evaluate(context),
Self::Or(left, right) => left.evaluate(context) || right.evaluate(context),
Self::Not(value) => !value.evaluate(context),
Self::Var(name) => context.get(name).copied().unwrap_or(false),
Self::Literal(value) => *value,
}
}
}
pub fn parse_bool_expression(expr: &str) -> Result<BoolExpression, String> {
let tokens = split_token(expr);
if tokens.is_empty() {
return Err("boolean expression cannot be empty".to_string());
}
let mut parser = Parser::new(tokens);
let expression = parser.parse_or()?;
if let Some(token) = parser.peek() {
return Err(format!("unexpected token `{token}`"));
}
Ok(expression)
}
struct Parser {
tokens: Vec<String>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<String>) -> Self {
Self {
tokens,
position: 0,
}
}
fn parse_or(&mut self) -> Result<BoolExpression, String> {
let mut expr = self.parse_and()?;
while self.consume("or") {
let rhs = self.parse_and()?;
expr = BoolExpression::Or(Box::new(expr), Box::new(rhs));
}
Ok(expr)
}
fn parse_and(&mut self) -> Result<BoolExpression, String> {
let mut expr = self.parse_not()?;
while self.consume("and") {
let rhs = self.parse_not()?;
expr = BoolExpression::And(Box::new(expr), Box::new(rhs));
}
Ok(expr)
}
fn parse_not(&mut self) -> Result<BoolExpression, String> {
if self.consume("not") {
return Ok(BoolExpression::Not(Box::new(self.parse_not()?)));
}
self.parse_primary()
}
fn parse_primary(&mut self) -> Result<BoolExpression, String> {
if self.consume("(") {
let expr = self.parse_or()?;
self.expect(")")?;
return Ok(expr);
}
let token = self
.next()
.ok_or_else(|| "unexpected end of expression".to_string())?;
match token.as_str() {
"true" | "True" | "TRUE" => Ok(BoolExpression::Literal(true)),
"false" | "False" | "FALSE" => Ok(BoolExpression::Literal(false)),
"and" | "or" | ")" => Err(format!("unexpected token `{token}`")),
_ => Ok(BoolExpression::Var(strip_matching_quotes(&token))),
}
}
fn consume(&mut self, expected: &str) -> bool {
matches!(self.peek(), Some(token) if token == expected)
.then(|| self.position += 1)
.is_some()
}
fn expect(&mut self, expected: &str) -> Result<(), String> {
match self.next() {
Some(token) if token == expected => Ok(()),
Some(token) => Err(format!("expected `{expected}`, found `{token}`")),
None => Err(format!("expected `{expected}`, found end of expression")),
}
}
fn peek(&self) -> Option<&str> {
self.tokens.get(self.position).map(String::as_str)
}
fn next(&mut self) -> Option<String> {
let token = self.tokens.get(self.position).cloned()?;
self.position += 1;
Some(token)
}
}
fn strip_matching_quotes(token: &str) -> String {
let bytes = token.as_bytes();
if bytes.len() >= 2 {
let first = bytes[0] as char;
let last = bytes[bytes.len() - 1] as char;
if matches!(first, '\'' | '"') && first == last {
return token[1..token.len() - 1].to_string();
}
}
token.to_string()
}
#[cfg(test)]
mod tests {
use std::collections::HashMap;
use super::{BoolExpression, parse_bool_expression};
#[test]
fn parses_single_variable_expression() {
let parsed = parse_bool_expression("feature_enabled").expect("expression parses");
assert_eq!(parsed, BoolExpression::Var("feature_enabled".to_string()));
}
#[test]
fn parses_boolean_literal_expression() {
let parsed = parse_bool_expression("true").expect("expression parses");
assert_eq!(parsed, BoolExpression::Literal(true));
}
#[test]
fn parses_and_expression() {
let parsed = parse_bool_expression("alpha and beta").expect("expression parses");
assert_eq!(
parsed,
BoolExpression::And(
Box::new(BoolExpression::Var("alpha".to_string())),
Box::new(BoolExpression::Var("beta".to_string())),
)
);
}
#[test]
fn parses_or_expression() {
let parsed = parse_bool_expression("alpha or beta").expect("expression parses");
assert_eq!(
parsed,
BoolExpression::Or(
Box::new(BoolExpression::Var("alpha".to_string())),
Box::new(BoolExpression::Var("beta".to_string())),
)
);
}
#[test]
fn parses_not_expression() {
let parsed = parse_bool_expression("not archived").expect("expression parses");
assert_eq!(
parsed,
BoolExpression::Not(Box::new(BoolExpression::Var("archived".to_string())))
);
}
#[test]
fn parses_nested_parenthesized_expression() {
let parsed =
parse_bool_expression("not (alpha and beta) or gamma").expect("expression parses");
assert_eq!(
parsed,
BoolExpression::Or(
Box::new(BoolExpression::Not(Box::new(BoolExpression::And(
Box::new(BoolExpression::Var("alpha".to_string())),
Box::new(BoolExpression::Var("beta".to_string())),
)))),
Box::new(BoolExpression::Var("gamma".to_string())),
)
);
}
#[test]
fn and_has_higher_precedence_than_or() {
let parsed = parse_bool_expression("alpha or beta and gamma").expect("expression parses");
assert_eq!(
parsed,
BoolExpression::Or(
Box::new(BoolExpression::Var("alpha".to_string())),
Box::new(BoolExpression::And(
Box::new(BoolExpression::Var("beta".to_string())),
Box::new(BoolExpression::Var("gamma".to_string())),
)),
)
);
}
#[test]
fn evaluate_resolves_variables_and_operators() {
let expr = parse_bool_expression("feature and not archived").expect("expression parses");
let context = HashMap::from([
("feature".to_string(), true),
("archived".to_string(), false),
]);
assert!(expr.evaluate(&context));
}
#[test]
fn evaluate_missing_variables_as_false() {
let expr = parse_bool_expression("missing or enabled").expect("expression parses");
let context = HashMap::from([("enabled".to_string(), false)]);
assert!(!expr.evaluate(&context));
}
#[test]
fn rejects_empty_expressions() {
let error = parse_bool_expression(" ").expect_err("expression should fail");
assert!(error.contains("cannot be empty"));
}
#[test]
fn rejects_unclosed_parentheses() {
let error = parse_bool_expression("(alpha or beta").expect_err("expression should fail");
assert!(error.contains("expected `)`"));
}
}