muninn_query/parser/
binary_expression.rs

1use crate::{
2  ast::{BinaryExpression, BinaryOperator, ErrorToken, Expression},
3  parser::{
4    simple_expr,
5    utils::{keyword, IResult, LocatedSpan},
6  },
7};
8use nom::{
9  branch::alt,
10  bytes::complete::tag,
11  combinator::value,
12  error::{FromExternalError, ParseError},
13  multi::many1,
14  sequence::tuple,
15};
16use std::{iter::Peekable, vec::IntoIter};
17
18#[derive(Debug, PartialEq, Clone)]
19enum Token {
20  Operator(BinaryOperator),
21  Expression(Expression),
22}
23impl Token {
24  pub fn precedence(&self) -> u8 {
25    match self {
26      Token::Operator(op) => op.precedence(),
27      _ => u8::max_value(),
28    }
29  }
30}
31#[derive(Debug)]
32enum AstError {
33  ExpectedOperator,
34  ExpectedToken,
35}
36
37impl<'a> ParseError<LocatedSpan<'a>> for AstError {
38  fn from_error_kind(_: LocatedSpan, _: nom::error::ErrorKind) -> Self {
39    todo!()
40  }
41  fn append(_: LocatedSpan, _: nom::error::ErrorKind, _: Self) -> Self {
42    todo!()
43  }
44}
45
46struct PrecedenceSolver {
47  token_iter: Peekable<IntoIter<Token>>,
48}
49
50impl PrecedenceSolver {
51  fn nud(&mut self, t: Token) -> Expression {
52    match t {
53      Token::Expression(e) => e,
54      _ => Expression::Error(ErrorToken::Unexpected),
55    }
56  }
57
58  fn led(&mut self, bp: u8, left: Expression, op: Token) -> Result<Expression, AstError> {
59    match op {
60      Token::Operator(operator) => {
61        let right = self.expr(bp)?;
62
63        Ok(Expression::BinaryExpression(Box::new(BinaryExpression {
64          lhs: left,
65          rhs: right,
66          op: operator,
67        })))
68      }
69      _ => Err(AstError::ExpectedOperator),
70    }
71  }
72
73  fn expr(&mut self, rbp: u8) -> Result<Expression, AstError> {
74    let first_token = self.token_iter.next().ok_or(AstError::ExpectedToken)?;
75    let mut left = self.nud(first_token);
76
77    while let Some(peeked) = self.token_iter.peek() {
78      if rbp >= peeked.precedence() {
79        break;
80      }
81
82      let op = self.token_iter.next().unwrap();
83      left = self.led(op.precedence(), left, op)?;
84    }
85
86    Ok(left)
87  }
88
89  fn solve(tokens: IntoIter<Token>) -> Result<Expression, AstError> {
90    let mut solver = PrecedenceSolver {
91      token_iter: tokens.peekable(),
92    };
93    solver.expr(0)
94  }
95}
96
97pub(crate) fn binary_expr(i: LocatedSpan) -> IResult<Expression> {
98  let (i, first_expr) = simple_expr(i)?;
99  let first_token = Token::Expression(first_expr);
100  let (i, other_tokens) = many1(tuple((binary_operator, simple_expr)))(i)?;
101  let mut tokens = vec![first_token];
102  for (sep, expr) in other_tokens {
103    tokens.push(Token::Operator(sep));
104    tokens.push(Token::Expression(expr));
105  }
106
107  match PrecedenceSolver::solve(tokens.into_iter()) {
108    Ok(expr) => Ok((i, expr)),
109    Err(err) => Err(nom::Err::Error(nom::error::Error::from_external_error(
110      i,
111      nom::error::ErrorKind::MapRes,
112      err,
113    ))),
114  }
115}
116
117fn binary_operator(i: LocatedSpan) -> IResult<BinaryOperator> {
118  alt((
119    op_and, op_or, op_before, op_after, op_eq, op_ne, op_lte, op_lt, op_gte, op_gt, op_match,
120    op_imatch,
121  ))(i)
122}
123fn op_and(i: LocatedSpan) -> IResult<BinaryOperator> {
124  value(BinaryOperator::And, keyword("and"))(i)
125}
126fn op_or(i: LocatedSpan) -> IResult<BinaryOperator> {
127  value(BinaryOperator::Or, keyword("or"))(i)
128}
129fn op_before(i: LocatedSpan) -> IResult<BinaryOperator> {
130  value(BinaryOperator::Lte, keyword("before"))(i)
131}
132fn op_after(i: LocatedSpan) -> IResult<BinaryOperator> {
133  value(BinaryOperator::Gte, keyword("after"))(i)
134}
135fn op_eq(i: LocatedSpan) -> IResult<BinaryOperator> {
136  value(BinaryOperator::Eq, tag("=="))(i)
137}
138fn op_ne(i: LocatedSpan) -> IResult<BinaryOperator> {
139  value(BinaryOperator::Ne, tag("!="))(i)
140}
141fn op_lt(i: LocatedSpan) -> IResult<BinaryOperator> {
142  value(BinaryOperator::Lt, tag("<"))(i)
143}
144fn op_lte(i: LocatedSpan) -> IResult<BinaryOperator> {
145  value(BinaryOperator::Lte, tag("<="))(i)
146}
147fn op_gt(i: LocatedSpan) -> IResult<BinaryOperator> {
148  value(BinaryOperator::Gt, tag(">"))(i)
149}
150fn op_gte(i: LocatedSpan) -> IResult<BinaryOperator> {
151  value(BinaryOperator::Gte, tag(">="))(i)
152}
153fn op_match(i: LocatedSpan) -> IResult<BinaryOperator> {
154  value(BinaryOperator::Match, keyword("match"))(i)
155}
156fn op_imatch(i: LocatedSpan) -> IResult<BinaryOperator> {
157  value(BinaryOperator::IMatch, keyword("imatch"))(i)
158}
159
160#[cfg(test)]
161mod tests {
162  use crate::{
163    ast::{
164      BinaryExpression, BinaryOperator, Duration, Expression, RelativeTime, TimeAnchor, Value,
165    },
166    parser::{
167      binary_expr,
168      utils::{span, unwrap_span},
169    },
170  };
171
172  #[test]
173
174  fn test_binary_expr() {
175    assert_eq!(
176      binary_expr(span(".a.b.c and true")).map(unwrap_span),
177      Ok((
178        "",
179        Expression::BinaryExpression(Box::new(BinaryExpression {
180          lhs: Expression::AbsolutePath(vec!["a".to_string(), "b".to_string(), "c".to_string(),]),
181          op: BinaryOperator::And,
182          rhs: Expression::Value(Value::Bool(true)),
183        }))
184      ))
185    );
186
187    assert_eq!(
188      binary_expr(span("true and false or false and true")).map(unwrap_span),
189      Ok((
190        "",
191        Expression::BinaryExpression(Box::new(BinaryExpression {
192          lhs: Expression::BinaryExpression(Box::new(BinaryExpression {
193            lhs: Expression::Value(Value::Bool(true)),
194            op: BinaryOperator::And,
195            rhs: Expression::Value(Value::Bool(false)),
196          })),
197          op: BinaryOperator::Or,
198          rhs: Expression::BinaryExpression(Box::new(BinaryExpression {
199            lhs: Expression::Value(Value::Bool(false)),
200            op: BinaryOperator::And,
201            rhs: Expression::Value(Value::Bool(true)),
202          })),
203        }))
204      ))
205    );
206
207    assert_eq!(
208      binary_expr(span("true and false or false and true == 0 > 3")).map(unwrap_span),
209      Ok((
210        "",
211        Expression::BinaryExpression(Box::new(BinaryExpression {
212          lhs: Expression::BinaryExpression(Box::new(BinaryExpression {
213            lhs: Expression::Value(Value::Bool(true)),
214            op: BinaryOperator::And,
215            rhs: Expression::Value(Value::Bool(false)),
216          })),
217          op: BinaryOperator::Or,
218          rhs: Expression::BinaryExpression(Box::new(BinaryExpression {
219            lhs: Expression::Value(Value::Bool(false)),
220            op: BinaryOperator::And,
221            rhs: Expression::BinaryExpression(Box::new(BinaryExpression {
222              lhs: Expression::Value(Value::Bool(true)),
223              op: BinaryOperator::Eq,
224              rhs: Expression::BinaryExpression(Box::new(BinaryExpression {
225                lhs: Expression::Value(Value::Int(0)),
226                op: BinaryOperator::Gt,
227                rhs: Expression::Value(Value::Int(3)),
228              })),
229            }))
230          })),
231        }))
232      ))
233    );
234
235    assert_eq!(
236      binary_expr(span(".time after 10 minutes ago")).map(unwrap_span),
237      Ok((
238        "",
239        Expression::BinaryExpression(Box::new(BinaryExpression {
240          lhs: Expression::AbsolutePath(vec!["time".to_string()]),
241          op: BinaryOperator::Gte,
242          rhs: Expression::Value(Value::RelativeTime(RelativeTime::Duration(
243            Duration::Minutes(10),
244            TimeAnchor::Ago
245          ))),
246        }))
247      ))
248    );
249  }
250}
muninn_query/parser/binary_expression.rs

muninn_query/parser/
binary_expression.rs
