use std::collections::HashSet;
use std::ops::Deref;
#[derive(Debug, Clone, PartialEq, Eq)]
enum Token {
End,
Or,
And,
Not,
LParen,
RParen,
Match(String),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct Error(String);
impl Error {
fn parse(message: impl Into<String>) -> Self {
Self(message.into())
}
fn in_expression(self, expression: &str) -> Self {
Self(format!("{}\nin expression: {:?}", self.0, expression))
}
}
impl Deref for Error {
type Target = str;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl std::fmt::Display for Error {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.0)
}
}
impl std::error::Error for Error {}
struct Lexer<'a> {
text: &'a str,
pos: usize,
}
impl<'a> Lexer<'a> {
fn new(expr: &'a str) -> Self {
Self { text: expr, pos: 0 }
}
fn remaining(&self) -> &'a str {
&self.text[self.pos..]
}
fn next_token(&mut self) -> Result<Token, Error> {
self.skip_ws();
let rest = self.remaining();
if rest.is_empty() {
return Ok(Token::End);
}
if rest.starts_with("&&") {
self.pos += 2;
return Ok(Token::And);
}
if rest.starts_with("||") {
self.pos += 2;
return Ok(Token::Or);
}
if rest.starts_with("!") {
self.pos += 1;
return Ok(Token::Not);
}
if rest.starts_with("(") {
self.pos += 1;
return Ok(Token::LParen);
}
if rest.starts_with(")") {
self.pos += 1;
return Ok(Token::RParen);
}
let start = self.pos;
let mut idx = self.pos;
loop {
let tail = &self.text[idx..];
if let Some(regex) = tail.strip_prefix("{{") {
let Some(end) = regex.find("}}") else {
break;
};
if end == 0 {
break;
}
idx += 2 + end + 2;
continue;
}
let identifier_len = tail
.bytes()
.take_while(|byte| {
matches!(
byte,
b'-' | b'+' | b'=' | b'.' | b'_'
| b'a'..=b'z'
| b'A'..=b'Z'
| b'0'..=b'9'
)
})
.count();
if identifier_len == 0 {
break;
}
idx += identifier_len;
}
if idx == start {
return Err(Error::parse(format!("couldn't parse text: {:?}", rest)));
}
self.pos = idx;
Ok(Token::Match(self.text[start..idx].to_string()))
}
fn skip_ws(&mut self) {
while self.pos < self.text.len() {
let mut chars = self.text[self.pos..].chars();
let Some(ch) = chars.next() else {
break;
};
if ch.is_whitespace() {
self.pos += ch.len_utf8();
continue;
}
break;
}
}
}
pub(crate) fn evaluate(expr: &str, variables: &HashSet<String>) -> Result<bool, Error> {
let mut vars = variables.clone();
vars.insert("true".into());
let mut parser = Parser::new(expr).map_err(|error| error.in_expression(expr))?;
parser
.parse_all(&vars)
.map_err(|error| error.in_expression(expr))
}
struct Parser<'a> {
lexer: Lexer<'a>,
token: Token,
}
impl<'a> Parser<'a> {
fn new(expr: &'a str) -> Result<Self, Error> {
let mut lexer = Lexer::new(expr);
let first = lexer.next_token()?;
Ok(Self {
lexer,
token: first,
})
}
fn consume(&mut self, expected: &Token) -> Result<bool, Error> {
if &self.token == expected {
self.token = self.lexer.next_token()?;
Ok(true)
} else {
Ok(false)
}
}
fn expect(&mut self, expected: &Token) -> Result<(), Error> {
if self.consume(expected)? {
Ok(())
} else {
Err(Error::parse(format!(
"expected: {}\nhave: {}",
quote(expected),
quote(&self.token)
)))
}
}
fn parse_all(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
let value = self.parse_or(variables)?;
self.expect(&Token::End)?;
Ok(value)
}
fn parse_or(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
let mut left = self.parse_and(variables)?;
while let Token::Or = self.token {
self.consume(&Token::Or)?;
let right = self.parse_and(variables)?;
left = left || right;
}
Ok(left)
}
fn parse_and(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
let mut left = self.parse_not(variables)?;
while let Token::And = self.token {
self.consume(&Token::And)?;
let right = self.parse_not(variables)?;
left = left && right;
}
Ok(left)
}
fn parse_not(&mut self, variables: &HashSet<String>) -> Result<bool, Error> {
if self.consume(&Token::Not)? {
return Ok(!self.parse_not(variables)?);
}
if self.consume(&Token::LParen)? {
let value = self.parse_or(variables)?;
self.expect(&Token::RParen)?;
return Ok(value);
}
match &self.token {
Token::Match(_) => {
let token = self.token.clone();
self.token = self.lexer.next_token()?;
let Token::Match(raw) = token else {
unreachable!()
};
matches_expr(&raw, variables)
}
Token::End => Err(Error::parse(
"expected: '!', '(', '{{', or identifier\nhave: <end of expression>",
)),
Token::And | Token::Or | Token::RParen | Token::LParen | Token::Not => {
Err(Error::parse(format!(
"expected: '!', '(', '{{', or identifier\nhave: {}",
quote(&self.token)
)))
}
}
}
}
fn matches_expr(expr: &str, features: &HashSet<String>) -> Result<bool, Error> {
let mut parts = Vec::new();
let re =
regex::Regex::new(r"\{\{.+?\}\}").expect("the braced regular-expression matcher is valid");
let mut last = 0usize;
for mat in re.find_iter(expr) {
let start = mat.start();
let end = mat.end();
if start > last {
parts.push(regex::escape(&expr[last..start]));
}
parts.push(format!("(?:{})", &expr[start + 2..end - 2]));
last = end;
}
if last < expr.len() {
parts.push(regex::escape(&expr[last..]));
}
let pattern = format!(r"\A(?:{})\z", parts.join(""));
let re = regex::Regex::new(&pattern).map_err(|error| {
Error::parse(format!(
"invalid regular expression in match {:?}: {error}",
expr
))
})?;
Ok(features.iter().any(|feature| re.is_match(feature)))
}
fn quote(t: &Token) -> String {
match t {
Token::End => "<end of expression>".into(),
Token::Or => "||".into(),
Token::And => "&&".into(),
Token::Not => "!".into(),
Token::LParen => "(".into(),
Token::RParen => ")".into(),
Token::Match(v) => format!("{:?}", v),
}
}
#[cfg(test)]
mod tests {
use super::evaluate;
fn make(features: &[&str]) -> std::collections::HashSet<String> {
features.iter().map(|v| v.to_string()).collect()
}
#[test]
fn operator_precedence() {
let features = make(&["true", "linux", "target=x86_64-unknown-linux-gnu"]);
assert!(evaluate("true || false", &features).unwrap());
assert!(!evaluate("false && false", &features).unwrap());
assert!(evaluate(
"linux && (target={{aarch64-.+}} || target={{x86_64-.+}})",
&features
)
.unwrap());
}
#[test]
fn regex_matching() {
let features = make(&["linux", "target=x86_64-unknown-linux-gnu"]);
assert!(evaluate("target={{x86_64-.+}}", &features).unwrap());
}
#[test]
fn parse_error_report() {
let err = evaluate("|| true", &make(&[])).unwrap_err();
assert!(err.contains("expected: '!', '(', '{', or identifier"));
assert!(err.contains("have:"));
}
}