use std::collections::BTreeSet;
use std::fmt;
const MAX_GUARD_DEPTH: usize = 64;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
Or(Box<Expr>, Box<Expr>),
And(Box<Expr>, Box<Expr>),
Not(Box<Expr>),
Matched,
Bound(String),
Unbound(String),
Compare {
left: Operand,
op: RelOp,
right: Operand,
},
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Operand {
Var(String),
Text(String),
Int(i64),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RelOp {
Eq,
Ne,
Lt,
Le,
Gt,
Ge,
}
#[allow(dead_code)]
impl Expr {
pub fn referenced_vars(&self) -> BTreeSet<String> {
let mut names = BTreeSet::new();
self.collect_vars(&mut names);
names
}
fn collect_vars(&self, names: &mut BTreeSet<String>) {
match self {
Expr::Or(left, right) | Expr::And(left, right) => {
left.collect_vars(names);
right.collect_vars(names);
}
Expr::Not(inner) => inner.collect_vars(names),
Expr::Matched => {}
Expr::Bound(name) | Expr::Unbound(name) => {
names.insert(name.clone());
}
Expr::Compare { left, right, .. } => {
if let Operand::Var(name) = left {
names.insert(name.clone());
}
if let Operand::Var(name) = right {
names.insert(name.clone());
}
}
}
}
pub fn uses_matched(&self) -> bool {
match self {
Expr::Matched => true,
Expr::Or(left, right) | Expr::And(left, right) => {
left.uses_matched() || right.uses_matched()
}
Expr::Not(inner) => inner.uses_matched(),
Expr::Bound(_) | Expr::Unbound(_) | Expr::Compare { .. } => false,
}
}
}
#[non_exhaustive]
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ParseError {
Empty,
UnexpectedChar(char),
UnterminatedString,
IntOverflow(String),
Expected(&'static str),
Trailing,
TooDeep,
}
impl fmt::Display for ParseError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
ParseError::Empty => write!(f, "the guard is empty"),
ParseError::UnexpectedChar(c) => write!(f, "unexpected character {c:?}"),
ParseError::UnterminatedString => write!(f, "a string literal is not closed"),
ParseError::IntOverflow(n) => write!(f, "the number {n} is too large"),
ParseError::Expected(what) => write!(f, "expected {what}"),
ParseError::Trailing => write!(f, "unexpected trailing input after the expression"),
ParseError::TooDeep => {
write!(f, "the guard nests deeper than {MAX_GUARD_DEPTH} levels")
}
}
}
}
impl std::error::Error for ParseError {}
pub fn parse(input: &str) -> Result<Expr, ParseError> {
let tokens = lex(input)?;
if tokens.is_empty() {
return Err(ParseError::Empty);
}
let mut parser = Parser {
tokens,
pos: 0,
depth: 0,
};
let expr = parser.or_expr()?;
if parser.pos != parser.tokens.len() {
return Err(ParseError::Trailing);
}
Ok(expr)
}
#[derive(Debug, Clone, PartialEq, Eq)]
enum Token {
And,
Or,
Not,
Matched,
Bound,
Unbound,
LParen,
RParen,
Op(RelOp),
Ident(String),
Text(String),
Int(i64),
}
fn lex(input: &str) -> Result<Vec<Token>, ParseError> {
let mut tokens = Vec::new();
let chars: Vec<char> = input.chars().collect();
let mut i = 0;
while i < chars.len() {
let c = chars[i];
match c {
c if c.is_whitespace() => i += 1,
'(' => {
tokens.push(Token::LParen);
i += 1;
}
')' => {
tokens.push(Token::RParen);
i += 1;
}
'<' | '>' | '=' | '!' => {
let two = chars.get(i + 1) == Some(&'=');
let op = match (c, two) {
('<', true) => RelOp::Le,
('<', false) => RelOp::Lt,
('>', true) => RelOp::Ge,
('>', false) => RelOp::Gt,
('=', true) => RelOp::Eq,
('!', true) => RelOp::Ne,
_ => return Err(ParseError::UnexpectedChar(c)),
};
tokens.push(Token::Op(op));
i += if two { 2 } else { 1 };
}
'\'' | '"' => {
let quote = c;
let start = i + 1;
let mut j = start;
while j < chars.len() && chars[j] != quote {
j += 1;
}
if j >= chars.len() {
return Err(ParseError::UnterminatedString);
}
tokens.push(Token::Text(chars[start..j].iter().collect()));
i = j + 1;
}
c if c.is_ascii_digit() => {
let start = i;
while i < chars.len() && chars[i].is_ascii_digit() {
i += 1;
}
let digits: String = chars[start..i].iter().collect();
let value = digits
.parse()
.map_err(|_| ParseError::IntOverflow(digits))?;
tokens.push(Token::Int(value));
}
c if c.is_ascii_alphabetic() || c == '_' => {
let start = i;
while i < chars.len() && (chars[i].is_ascii_alphanumeric() || chars[i] == '_') {
i += 1;
}
let word: String = chars[start..i].iter().collect();
tokens.push(keyword(word));
}
_ => return Err(ParseError::UnexpectedChar(c)),
}
}
Ok(tokens)
}
fn keyword(word: String) -> Token {
match word.as_str() {
"and" => Token::And,
"or" => Token::Or,
"not" => Token::Not,
"matched" => Token::Matched,
"bound" => Token::Bound,
"unbound" => Token::Unbound,
_ => Token::Ident(word),
}
}
struct Parser {
tokens: Vec<Token>,
pos: usize,
depth: usize,
}
impl Parser {
fn peek(&self) -> Option<&Token> {
self.tokens.get(self.pos)
}
fn advance(&mut self) -> Option<Token> {
let token = self.tokens.get(self.pos).cloned();
if token.is_some() {
self.pos += 1;
}
token
}
fn eat(&mut self, expected: &Token, what: &'static str) -> Result<(), ParseError> {
if self.peek() == Some(expected) {
self.pos += 1;
Ok(())
} else {
Err(ParseError::Expected(what))
}
}
fn or_expr(&mut self) -> Result<Expr, ParseError> {
self.depth += 1;
if self.depth > MAX_GUARD_DEPTH {
return Err(ParseError::TooDeep);
}
let mut left = self.and_expr()?;
while self.peek() == Some(&Token::Or) {
self.pos += 1;
let right = self.and_expr()?;
left = Expr::Or(Box::new(left), Box::new(right));
}
self.depth -= 1;
Ok(left)
}
fn and_expr(&mut self) -> Result<Expr, ParseError> {
let mut left = self.not_expr()?;
while self.peek() == Some(&Token::And) {
self.pos += 1;
let right = self.not_expr()?;
left = Expr::And(Box::new(left), Box::new(right));
}
Ok(left)
}
fn not_expr(&mut self) -> Result<Expr, ParseError> {
if self.peek() == Some(&Token::Not) {
self.pos += 1;
Ok(Expr::Not(Box::new(self.primary()?)))
} else {
self.primary()
}
}
fn primary(&mut self) -> Result<Expr, ParseError> {
match self.peek() {
Some(Token::LParen) => {
self.pos += 1;
let inner = self.or_expr()?;
self.eat(&Token::RParen, "a closing ')'")?;
Ok(inner)
}
Some(Token::Matched) => {
self.pos += 1;
Ok(Expr::Matched)
}
Some(Token::Bound) => {
self.pos += 1;
Ok(Expr::Bound(self.predicate_arg()?))
}
Some(Token::Unbound) => {
self.pos += 1;
Ok(Expr::Unbound(self.predicate_arg()?))
}
_ => self.comparison(),
}
}
fn predicate_arg(&mut self) -> Result<String, ParseError> {
self.eat(&Token::LParen, "'(' after the predicate")?;
let name = match self.advance() {
Some(Token::Ident(name)) => name,
_ => return Err(ParseError::Expected("a variable name")),
};
self.eat(&Token::RParen, "a closing ')'")?;
Ok(name)
}
fn comparison(&mut self) -> Result<Expr, ParseError> {
let left = self.operand()?;
let op = match self.advance() {
Some(Token::Op(op)) => op,
_ => return Err(ParseError::Expected("a comparison operator")),
};
let right = self.operand()?;
Ok(Expr::Compare { left, op, right })
}
fn operand(&mut self) -> Result<Operand, ParseError> {
match self.advance() {
Some(Token::Ident(name)) => Ok(Operand::Var(name)),
Some(Token::Text(text)) => Ok(Operand::Text(text)),
Some(Token::Int(value)) => Ok(Operand::Int(value)),
_ => Err(ParseError::Expected("a variable, string, or number")),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn ok(input: &str) -> Expr {
parse(input).expect("a valid guard")
}
fn var(name: &str) -> Operand {
Operand::Var(name.to_string())
}
fn text(value: &str) -> Operand {
Operand::Text(value.to_string())
}
#[test]
fn a_bare_predicate_parses() {
assert_eq!(ok("matched"), Expr::Matched);
assert_eq!(ok("bound(version)"), Expr::Bound("version".to_string()));
assert_eq!(ok("unbound(version)"), Expr::Unbound("version".to_string()));
}
#[test]
fn every_relational_operator_parses() {
for (src, op) in [
("v == '1'", RelOp::Eq),
("v != '1'", RelOp::Ne),
("v < '1'", RelOp::Lt),
("v <= '1'", RelOp::Le),
("v > '1'", RelOp::Gt),
("v >= '1'", RelOp::Ge),
] {
assert_eq!(
ok(src),
Expr::Compare {
left: var("v"),
op,
right: text("1"),
},
"{src}"
);
}
}
#[test]
fn operands_may_be_variables_strings_or_integers() {
assert_eq!(
ok("count == 3"),
Expr::Compare {
left: var("count"),
op: RelOp::Eq,
right: Operand::Int(3),
}
);
assert_eq!(
ok(r#"name == "nginx""#),
Expr::Compare {
left: var("name"),
op: RelOp::Eq,
right: text("nginx"),
}
);
}
#[test]
fn precedence_is_not_over_and_over_or() {
let expr = ok("bound(a) and bound(b) or bound(c)");
assert_eq!(
expr,
Expr::Or(
Box::new(Expr::And(
Box::new(Expr::Bound("a".to_string())),
Box::new(Expr::Bound("b".to_string())),
)),
Box::new(Expr::Bound("c".to_string())),
)
);
let expr = ok("not matched and bound(v)");
assert_eq!(
expr,
Expr::And(
Box::new(Expr::Not(Box::new(Expr::Matched))),
Box::new(Expr::Bound("v".to_string())),
)
);
}
#[test]
fn parentheses_override_precedence() {
let expr = ok("bound(a) and (bound(b) or bound(c))");
assert_eq!(
expr,
Expr::And(
Box::new(Expr::Bound("a".to_string())),
Box::new(Expr::Or(
Box::new(Expr::Bound("b".to_string())),
Box::new(Expr::Bound("c".to_string())),
)),
)
);
}
#[test]
fn the_grafana_guard_parses_as_written() {
let expr = ok("bound(version) and version < '8.3.1'");
assert_eq!(
expr,
Expr::And(
Box::new(Expr::Bound("version".to_string())),
Box::new(Expr::Compare {
left: var("version"),
op: RelOp::Lt,
right: text("8.3.1"),
}),
)
);
}
#[test]
fn referenced_vars_and_uses_matched_walk_the_whole_tree() {
let expr = ok("bound(a) and (version < '2' or unbound(b)) and not matched");
assert_eq!(
expr.referenced_vars(),
["a", "b", "version"]
.iter()
.map(|s| s.to_string())
.collect()
);
assert!(expr.uses_matched());
let literals = ok("3 < 4 and bound(x)");
assert_eq!(
literals.referenced_vars(),
["x"].iter().map(|s| s.to_string()).collect()
);
assert!(!literals.uses_matched());
}
#[test]
fn an_empty_or_whitespace_guard_is_rejected() {
assert_eq!(parse(""), Err(ParseError::Empty));
assert_eq!(parse(" "), Err(ParseError::Empty));
}
#[test]
fn a_bare_operand_is_not_a_guard() {
assert_eq!(
parse("version"),
Err(ParseError::Expected("a comparison operator"))
);
}
#[test]
fn malformed_predicates_and_parens_are_rejected() {
assert!(matches!(
parse("bound version"),
Err(ParseError::Expected(_))
));
assert!(matches!(parse("bound()"), Err(ParseError::Expected(_))));
assert!(matches!(parse("(matched"), Err(ParseError::Expected(_))));
assert_eq!(parse("matched matched"), Err(ParseError::Trailing));
}
#[test]
fn lexical_errors_name_their_cause() {
assert_eq!(parse("v = '1'"), Err(ParseError::UnexpectedChar('=')));
assert_eq!(parse("v & w"), Err(ParseError::UnexpectedChar('&')));
assert_eq!(parse("v == 'open"), Err(ParseError::UnterminatedString));
assert_eq!(parse("v < 8.3.1"), Err(ParseError::UnexpectedChar('.')));
}
#[test]
fn a_guard_nested_past_the_bound_is_refused_rather_than_overflowing_the_stack() {
let over = MAX_GUARD_DEPTH + 5;
let deep = format!("{}matched{}", "(".repeat(over), ")".repeat(over));
assert_eq!(parse(&deep), Err(ParseError::TooDeep));
let shallow = format!("{}matched{}", "(".repeat(4), ")".repeat(4));
assert!(parse(&shallow).is_ok());
}
}