sieve/runtime/
expression.rs

1/*
2 * SPDX-FileCopyrightText: 2020 Stalwart Labs Ltd <hello@stalw.art>
3 *
4 * SPDX-License-Identifier: AGPL-3.0-only OR LicenseRef-SEL
5 */
6
7use crate::Event;
8use crate::compiler::grammar::expr::parser::ID_EXTERNAL;
9use crate::compiler::grammar::expr::{BinaryOperator, Expression, UnaryOperator};
10use crate::{Context, compiler::Number, runtime::Variable};
11use std::sync::Arc;
12use std::{cmp::Ordering, fmt::Display};
13
14impl Context<'_> {
15    pub(crate) fn eval_expression(&mut self, expr: &[Expression]) -> Result<Variable, Event> {
16        while let Some(item) = expr.get(self.expr_pos) {
17            self.expr_pos += 1;
18            match item {
19                Expression::VariableLocal(id) => {
20                    let value = self
21                        .vars_local
22                        .get(*id as usize)
23                        .cloned()
24                        .unwrap_or_default();
25                    self.expr_stack.push(value);
26                }
27                Expression::VariableMatch(id) => {
28                    let value = self
29                        .vars_match
30                        .get(*id as usize)
31                        .cloned()
32                        .unwrap_or_default();
33                    self.expr_stack.push(value);
34                }
35                Expression::VariableOther(v) => {
36                    self.expr_stack.push(self.variable(v).unwrap_or_default());
37                }
38                Expression::ConstantInteger(i) => {
39                    self.expr_stack.push(Variable::Integer(*i));
40                }
41                Expression::ConstantFloat(f) => {
42                    self.expr_stack.push(Variable::Float(*f));
43                }
44                Expression::ConstantString(id) => {
45                    let value = self.constant(*id);
46                    self.expr_stack.push(Variable::String(value));
47                }
48                Expression::UnaryOperator(op) => {
49                    let value = self.expr_stack.pop().unwrap_or_default();
50                    self.expr_stack.push(match op {
51                        UnaryOperator::Not => value.op_not(),
52                        UnaryOperator::Minus => value.op_minus(),
53                    });
54                }
55                Expression::BinaryOperator(op) => {
56                    let right = self.expr_stack.pop().unwrap_or_default();
57                    let left = self.expr_stack.pop().unwrap_or_default();
58                    self.expr_stack.push(match op {
59                        BinaryOperator::Add => left.op_add(right),
60                        BinaryOperator::Subtract => left.op_subtract(right),
61                        BinaryOperator::Multiply => left.op_multiply(right),
62                        BinaryOperator::Divide => left.op_divide(right),
63                        BinaryOperator::And => left.op_and(right),
64                        BinaryOperator::Or => left.op_or(right),
65                        BinaryOperator::Xor => left.op_xor(right),
66                        BinaryOperator::Eq => left.op_eq(right),
67                        BinaryOperator::Ne => left.op_ne(right),
68                        BinaryOperator::Lt => left.op_lt(right),
69                        BinaryOperator::Le => left.op_le(right),
70                        BinaryOperator::Gt => left.op_gt(right),
71                        BinaryOperator::Ge => left.op_ge(right),
72                    });
73                }
74                Expression::Function { id, num_args } => {
75                    let num_args = *num_args as usize;
76
77                    if let Some(fnc) = self.runtime.functions.get(*id as usize) {
78                        let start = self.expr_stack.len().saturating_sub(num_args);
79                        let arguments = self.expr_stack.split_off(start);
80                        let result = (fnc)(self, arguments);
81                        self.expr_stack.push(result);
82                    } else {
83                        let start = self.expr_stack.len().saturating_sub(num_args);
84                        let arguments = self.expr_stack.split_off(start);
85                        self.pos -= 1; // We need to re-evaluate the function call
86                        return Err(Event::Function {
87                            id: ID_EXTERNAL - *id,
88                            arguments,
89                        });
90                    }
91                }
92                Expression::JmpIf { val, pos } => {
93                    if self.expr_stack.last().is_some_and(|v| v.to_bool()) == *val {
94                        self.expr_pos += *pos as usize;
95                    }
96                }
97                Expression::ArrayAccess => {
98                    let index = self.expr_stack.pop().unwrap_or_default().to_usize();
99                    let array = self.expr_stack.pop().unwrap_or_default().into_array();
100                    self.expr_stack
101                        .push(array.get(index).cloned().unwrap_or_default());
102                }
103                Expression::ArrayBuild(num_items) => {
104                    let start = self.expr_stack.len().saturating_sub(*num_items as usize);
105                    let items = Arc::from(&self.expr_stack[start..]);
106                    self.expr_stack.truncate(start);
107                    self.expr_stack.push(Variable::Array(items));
108                }
109            }
110        }
111
112        let result = self.expr_stack.pop().unwrap_or_default();
113        self.expr_stack.clear();
114        self.expr_pos = 0;
115        Ok(result)
116    }
117}
118
119impl Variable {
120    pub fn op_add(self, other: Variable) -> Variable {
121        match (self, other) {
122            (Variable::Integer(a), Variable::Integer(b)) => Variable::Integer(a.saturating_add(b)),
123            (Variable::Float(a), Variable::Float(b)) => Variable::Float(a + b),
124            (Variable::Integer(i), Variable::Float(f))
125            | (Variable::Float(f), Variable::Integer(i)) => Variable::Float(i as f64 + f),
126            (Variable::Array(a), Variable::Array(b)) => {
127                Variable::Array(a.iter().chain(b.iter()).cloned().collect())
128            }
129            (Variable::Array(a), b) => Variable::Array(a.iter().cloned().chain([b]).collect()),
130            (a, Variable::Array(b)) => {
131                Variable::Array([a].into_iter().chain(b.iter().cloned()).collect())
132            }
133            (Variable::String(a), b) => {
134                if !a.is_empty() {
135                    Variable::String(format!("{}{}", a, b).into())
136                } else {
137                    b
138                }
139            }
140            (a, Variable::String(b)) => {
141                if !b.is_empty() {
142                    Variable::String(format!("{}{}", a, b).into())
143                } else {
144                    a
145                }
146            }
147        }
148    }
149
150    pub fn op_subtract(self, other: Variable) -> Variable {
151        match (self, other) {
152            (Variable::Integer(a), Variable::Integer(b)) => Variable::Integer(a.saturating_sub(b)),
153            (Variable::Float(a), Variable::Float(b)) => Variable::Float(a - b),
154            (Variable::Integer(a), Variable::Float(b)) => Variable::Float(a as f64 - b),
155            (Variable::Float(a), Variable::Integer(b)) => Variable::Float(a - b as f64),
156            (Variable::Array(a), b) | (b, Variable::Array(a)) => {
157                Variable::Array(a.iter().filter(|v| *v != &b).cloned().collect())
158            }
159            (a, b) => a.parse_number().op_subtract(b.parse_number()),
160        }
161    }
162
163    pub fn op_multiply(self, other: Variable) -> Variable {
164        match (self, other) {
165            (Variable::Integer(a), Variable::Integer(b)) => Variable::Integer(a.saturating_mul(b)),
166            (Variable::Float(a), Variable::Float(b)) => Variable::Float(a * b),
167            (Variable::Integer(i), Variable::Float(f))
168            | (Variable::Float(f), Variable::Integer(i)) => Variable::Float(i as f64 * f),
169            (a, b) => a.parse_number().op_multiply(b.parse_number()),
170        }
171    }
172
173    pub fn op_divide(self, other: Variable) -> Variable {
174        match (self, other) {
175            (Variable::Integer(a), Variable::Integer(b)) => {
176                Variable::Float(if b != 0 { a as f64 / b as f64 } else { 0.0 })
177            }
178            (Variable::Float(a), Variable::Float(b)) => {
179                Variable::Float(if b != 0.0 { a / b } else { 0.0 })
180            }
181            (Variable::Integer(a), Variable::Float(b)) => {
182                Variable::Float(if b != 0.0 { a as f64 / b } else { 0.0 })
183            }
184            (Variable::Float(a), Variable::Integer(b)) => {
185                Variable::Float(if b != 0 { a / b as f64 } else { 0.0 })
186            }
187            (a, b) => a.parse_number().op_divide(b.parse_number()),
188        }
189    }
190
191    pub fn op_and(self, other: Variable) -> Variable {
192        Variable::Integer(i64::from(self.to_bool() & other.to_bool()))
193    }
194
195    pub fn op_or(self, other: Variable) -> Variable {
196        Variable::Integer(i64::from(self.to_bool() | other.to_bool()))
197    }
198
199    pub fn op_xor(self, other: Variable) -> Variable {
200        Variable::Integer(i64::from(self.to_bool() ^ other.to_bool()))
201    }
202
203    pub fn op_eq(self, other: Variable) -> Variable {
204        Variable::Integer(i64::from(self == other))
205    }
206
207    pub fn op_ne(self, other: Variable) -> Variable {
208        Variable::Integer(i64::from(self != other))
209    }
210
211    pub fn op_lt(self, other: Variable) -> Variable {
212        Variable::Integer(i64::from(self < other))
213    }
214
215    pub fn op_le(self, other: Variable) -> Variable {
216        Variable::Integer(i64::from(self <= other))
217    }
218
219    pub fn op_gt(self, other: Variable) -> Variable {
220        Variable::Integer(i64::from(self > other))
221    }
222
223    pub fn op_ge(self, other: Variable) -> Variable {
224        Variable::Integer(i64::from(self >= other))
225    }
226
227    pub fn op_not(self) -> Variable {
228        Variable::Integer(i64::from(!self.to_bool()))
229    }
230
231    pub fn op_minus(self) -> Variable {
232        match self {
233            Variable::Integer(n) => Variable::Integer(-n),
234            Variable::Float(n) => Variable::Float(-n),
235            _ => self.parse_number().op_minus(),
236        }
237    }
238
239    pub fn parse_number(&self) -> Variable {
240        match self {
241            Variable::String(s) if !s.is_empty() => {
242                if let Ok(n) = s.parse::<i64>() {
243                    Variable::Integer(n)
244                } else if let Ok(n) = s.parse::<f64>() {
245                    Variable::Float(n)
246                } else {
247                    Variable::Integer(0)
248                }
249            }
250            Variable::Integer(n) => Variable::Integer(*n),
251            Variable::Float(n) => Variable::Float(*n),
252            Variable::Array(l) => Variable::Integer(l.is_empty() as i64),
253            _ => Variable::Integer(0),
254        }
255    }
256
257    pub fn to_bool(&self) -> bool {
258        match self {
259            Variable::Float(f) => *f != 0.0,
260            Variable::Integer(n) => *n != 0,
261            Variable::String(s) => !s.is_empty(),
262            Variable::Array(a) => !a.is_empty(),
263        }
264    }
265}
266
267impl PartialEq for Variable {
268    fn eq(&self, other: &Self) -> bool {
269        match (self, other) {
270            (Self::Integer(a), Self::Integer(b)) => a == b,
271            (Self::Float(a), Self::Float(b)) => a == b,
272            (Self::Integer(a), Self::Float(b)) | (Self::Float(b), Self::Integer(a)) => {
273                *a as f64 == *b
274            }
275            (Self::String(a), Self::String(b)) => a == b,
276            (Self::String(_), Self::Integer(_) | Self::Float(_)) => &self.parse_number() == other,
277            (Self::Integer(_) | Self::Float(_), Self::String(_)) => self == &other.parse_number(),
278            (Self::Array(a), Self::Array(b)) => a == b,
279            _ => false,
280        }
281    }
282}
283
284impl Eq for Variable {}
285
286#[allow(clippy::non_canonical_partial_ord_impl)]
287impl PartialOrd for Variable {
288    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
289        match (self, other) {
290            (Self::Integer(a), Self::Integer(b)) => a.partial_cmp(b),
291            (Self::Float(a), Self::Float(b)) => a.partial_cmp(b),
292            (Self::Integer(a), Self::Float(b)) => (*a as f64).partial_cmp(b),
293            (Self::Float(a), Self::Integer(b)) => a.partial_cmp(&(*b as f64)),
294            (Self::String(a), Self::String(b)) => a.partial_cmp(b),
295            (Self::String(_), Self::Integer(_) | Self::Float(_)) => {
296                self.parse_number().partial_cmp(other)
297            }
298            (Self::Integer(_) | Self::Float(_), Self::String(_)) => {
299                self.partial_cmp(&other.parse_number())
300            }
301            (Self::Array(a), Self::Array(b)) => a.partial_cmp(b),
302            (Self::Array(_) | Self::String(_), _) => Ordering::Greater.into(),
303            (_, Self::Array(_)) => Ordering::Less.into(),
304        }
305    }
306}
307
308impl Ord for Variable {
309    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
310        self.partial_cmp(other).unwrap_or(Ordering::Greater)
311    }
312}
313
314impl Display for Variable {
315    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
316        match self {
317            Variable::String(v) => v.fmt(f),
318            Variable::Integer(v) => v.fmt(f),
319            Variable::Float(v) => v.fmt(f),
320            Variable::Array(v) => {
321                for (i, v) in v.iter().enumerate() {
322                    if i > 0 {
323                        f.write_str("\n")?;
324                    }
325                    v.fmt(f)?;
326                }
327                Ok(())
328            }
329        }
330    }
331}
332
333impl Number {
334    pub fn is_non_zero(&self) -> bool {
335        match self {
336            Number::Integer(n) => *n != 0,
337            Number::Float(n) => *n != 0.0,
338        }
339    }
340}
341
342impl Default for Number {
343    fn default() -> Self {
344        Number::Integer(0)
345    }
346}
347
348impl From<bool> for Number {
349    #[inline(always)]
350    fn from(b: bool) -> Self {
351        Number::Integer(i64::from(b))
352    }
353}
354
355impl From<i64> for Number {
356    #[inline(always)]
357    fn from(n: i64) -> Self {
358        Number::Integer(n)
359    }
360}
361
362impl From<f64> for Number {
363    #[inline(always)]
364    fn from(n: f64) -> Self {
365        Number::Float(n)
366    }
367}
368
369impl From<i32> for Number {
370    #[inline(always)]
371    fn from(n: i32) -> Self {
372        Number::Integer(n as i64)
373    }
374}
375
376#[cfg(test)]
377mod test {
378    use ahash::{HashMap, HashMapExt};
379
380    use crate::{
381        compiler::{
382            VariableType,
383            grammar::expr::{
384                BinaryOperator, Expression, Token, UnaryOperator, parser::ExpressionParser,
385                tokenizer::Tokenizer,
386            },
387        },
388        runtime::Variable,
389    };
390
391    use evalexpr::*;
392
393    pub trait EvalExpression {
394        fn eval(&self, variables: &HashMap<String, Variable>) -> Option<Variable>;
395    }
396
397    impl EvalExpression for Vec<Expression> {
398        fn eval(&self, variables: &HashMap<String, Variable>) -> Option<Variable> {
399            let mut stack = Vec::with_capacity(self.len());
400            let mut exprs = self.iter();
401
402            while let Some(expr) = exprs.next() {
403                match expr {
404                    Expression::VariableOther(v) => {
405                        if let VariableType::Global(v) = v.as_ref() {
406                            stack.push(variables.get(v)?.clone());
407                        } else {
408                            unreachable!("Invalid expression")
409                        }
410                    }
411                    Expression::ConstantInteger(i) => stack.push(Variable::Integer(*i)),
412                    Expression::ConstantFloat(f) => stack.push(Variable::Float(*f)),
413                    Expression::UnaryOperator(op) => {
414                        let value = stack.pop()?;
415                        stack.push(match op {
416                            UnaryOperator::Not => value.op_not(),
417                            UnaryOperator::Minus => value.op_minus(),
418                        });
419                    }
420                    Expression::BinaryOperator(op) => {
421                        let right = stack.pop()?;
422                        let left = stack.pop()?;
423                        stack.push(match op {
424                            BinaryOperator::Add => left.op_add(right),
425                            BinaryOperator::Subtract => left.op_subtract(right),
426                            BinaryOperator::Multiply => left.op_multiply(right),
427                            BinaryOperator::Divide => left.op_divide(right),
428                            BinaryOperator::And => left.op_and(right),
429                            BinaryOperator::Or => left.op_or(right),
430                            BinaryOperator::Xor => left.op_xor(right),
431                            BinaryOperator::Eq => left.op_eq(right),
432                            BinaryOperator::Ne => left.op_ne(right),
433                            BinaryOperator::Lt => left.op_lt(right),
434                            BinaryOperator::Le => left.op_le(right),
435                            BinaryOperator::Gt => left.op_gt(right),
436                            BinaryOperator::Ge => left.op_ge(right),
437                        });
438                    }
439                    Expression::JmpIf { val, pos } => {
440                        if stack.last()?.to_bool() == *val {
441                            for _ in 0..*pos {
442                                exprs.next();
443                            }
444                        }
445                    }
446                    _ => unreachable!("Invalid expression"),
447                }
448            }
449            stack.pop()
450        }
451    }
452
453    #[test]
454    fn eval_expression() {
455        let mut variables = HashMap::from_iter([
456            ("A".to_string(), Variable::Integer(0)),
457            ("B".to_string(), Variable::Integer(0)),
458            ("C".to_string(), Variable::Integer(0)),
459            ("D".to_string(), Variable::Integer(0)),
460            ("E".to_string(), Variable::Integer(0)),
461            ("F".to_string(), Variable::Integer(0)),
462            ("G".to_string(), Variable::Integer(0)),
463            ("H".to_string(), Variable::Integer(0)),
464            ("I".to_string(), Variable::Integer(0)),
465            ("J".to_string(), Variable::Integer(0)),
466        ]);
467        let num_vars = variables.len();
468
469        for expr in [
470            "A + B",
471            "A * B",
472            "A / B",
473            "A - B",
474            "-A",
475            "A == B",
476            "A != B",
477            "A > B",
478            "A < B",
479            "A >= B",
480            "A <= B",
481            "A + B * C - D / E",
482            "A + B + C - D - E",
483            "(A + B) * (C - D) / E",
484            "A - B + C * D / E * F - G",
485            "A + B * C - D / E",
486            "(A + B) * (C - D) / E",
487            "A - B + C / D * E",
488            "(A + B) / (C - D) + E",
489            "A * (B + C) - D / E",
490            "A / (B - C + D) * E",
491            "(A + B) * C - D / (E + F)",
492            "A * B - C + D / E",
493            "A + B - C * D / E",
494            "(A * B + C) / D - E",
495            "A - B / C + D * E",
496            "A + B * (C - D) / E",
497            "A * B / C + (D - E)",
498            "(A - B) * C / D + E",
499            "A * (B / C) - D + E",
500            "(A + B) / (C + D) * E",
501            "A - B * C / D + E",
502            "A + (B - C) * D / E",
503            "(A + B) * (C / D) - E",
504            "A - B / (C * D) + E",
505            "(A + B) > (C - D) && E <= F",
506            "A * B == C / D || E - F != G + H",
507            "A / B >= C * D && E + F < G - H",
508            "(A * B - C) != (D / E + F) && G > H",
509            "A - B < C && D + E >= F * G",
510            "(A * B) > C && (D / E) < F || G == H",
511            "(A + B) <= (C - D) || E > F && G != H",
512            "A * B != C + D || E - F == G / H",
513            "A >= B * C && D < E - F || G != H + I",
514            "(A / B + C) > D && E * F <= G - H",
515            "A * (B - C) == D && E / F > G + H",
516            "(A - B + C) != D || E * F >= G && H < I",
517            "A < B / C && D + E * F == G - H",
518            "(A + B * C) <= D && E > F / G",
519            "(A * B - C) > D || E <= F + G && H != I",
520            "A != B / C && D == E * F - G",
521            "A <= B + C - D && E / F > G * H",
522            "(A - B * C) < D || E >= F + G && H != I",
523            "(A + B) / C == D && E - F < G * H",
524            "A * B != C && D >= E + F / G || H < I",
525            "!(A * B != C) && !(D >= E + F / G) || !(H < I)",
526            "-A - B - (- C - D) - E - (-F)",
527        ] {
528            println!("Testing {}", expr);
529            for (pos, v) in variables.values_mut().enumerate() {
530                *v = Variable::Integer(pos as i64 + 1);
531            }
532
533            assert_expr(expr, &variables);
534
535            for (pos, v) in variables.values_mut().enumerate() {
536                *v = Variable::Integer((num_vars - pos) as i64);
537            }
538
539            assert_expr(expr, &variables);
540        }
541
542        for expr in [
543            "true && false",
544            "!true || false",
545            "true && !false",
546            "!(true && false)",
547            "true || true && false",
548            "!false && (true || false)",
549            "!(true || !false) && true",
550            "!(!true && !false)",
551            "true || false && !true",
552            "!(true && true) || !false",
553            "!(!true || !false) && (!false) && !(!true)",
554        ] {
555            let pexp = parse_expression(expr.replace("true", "1").replace("false", "0").as_str());
556            let result = pexp.eval(&HashMap::new()).unwrap();
557
558            //println!("{} => {:?}", expr, result);
559
560            match (eval(expr).expect(expr), result) {
561                (Value::Float(a), Variable::Float(b)) if a == b => (),
562                (Value::Float(a), Variable::Integer(b)) if a == b as f64 => (),
563                (Value::Boolean(a), Variable::Integer(b)) if a == (b != 0) => (),
564                (a, b) => {
565                    panic!("{} => {:?} != {:?}", expr, a, b)
566                }
567            }
568        }
569    }
570
571    fn assert_expr(expr: &str, variables: &HashMap<String, Variable>) {
572        let e = parse_expression(expr);
573
574        let result = e.eval(variables).unwrap();
575
576        let mut str_expr = expr.to_string();
577        let mut str_expr_float = expr.to_string();
578        for (k, v) in variables {
579            let v = v.to_string();
580
581            if v.contains('.') {
582                str_expr_float = str_expr_float.replace(k, &v);
583            } else {
584                str_expr_float = str_expr_float.replace(k, &format!("{}.0", v));
585            }
586            str_expr = str_expr.replace(k, &v);
587        }
588
589        assert_eq!(
590            parse_expression(&str_expr)
591                .eval(&HashMap::new())
592                .unwrap()
593                .to_number()
594                .to_float(),
595            result.to_number().to_float()
596        );
597
598        assert_eq!(
599            parse_expression(&str_expr_float)
600                .eval(&HashMap::new())
601                .unwrap()
602                .to_number()
603                .to_float(),
604            result.to_number().to_float()
605        );
606
607        //println!("{str_expr} ({e:?}) => {result:?}");
608
609        match (
610            eval(&str_expr_float)
611                .map(|v| {
612                    // Divisions by zero are converted to 0.0
613                    if matches!(&v, Value::Float(f) if f64::is_infinite(*f)) {
614                        Value::Float(0.0)
615                    } else {
616                        v
617                    }
618                })
619                .expect(&str_expr),
620            result,
621        ) {
622            (Value::Float(a), Variable::Float(b)) if a == b => (),
623            (Value::Float(a), Variable::Integer(b)) if a == b as f64 => (),
624            (Value::Boolean(a), Variable::Integer(b)) if a == (b != 0) => (),
625            (a, b) => {
626                panic!("{} => {:?} != {:?}", str_expr, a, b)
627            }
628        }
629    }
630
631    fn parse_expression(expr: &str) -> Vec<Expression> {
632        ExpressionParser::from_tokenizer(Tokenizer::new(expr, |var_name: &str, _: bool| {
633            Ok::<_, String>(Token::Variable(VariableType::Global(var_name.to_string())))
634        }))
635        .parse()
636        .unwrap()
637        .output
638    }
639}
sieve/runtime/expression.rs

sieve/runtime/
expression.rs
