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

sieve/runtime/
expression.rs
