sieve/compiler/grammar/expr/
parser.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::{tokenizer::Tokenizer, BinaryOperator, Expression, Token};
8
9pub(crate) struct ExpressionParser<'x, F>
10where
11    F: Fn(&str, bool) -> Result<Token, String>,
12{
13    pub(crate) tokenizer: Tokenizer<'x, F>,
14    pub(crate) output: Vec<Expression>,
15    operator_stack: Vec<(Token, Option<usize>)>,
16    arg_count: Vec<i32>,
17}
18
19pub(crate) const ID_ARRAY_ACCESS: u32 = u32::MAX;
20pub(crate) const ID_ARRAY_BUILD: u32 = u32::MAX - 1;
21pub(crate) const ID_EXTERNAL: u32 = u32::MAX - 2;
22
23impl<'x, F> ExpressionParser<'x, F>
24where
25    F: Fn(&str, bool) -> Result<Token, String>,
26{
27    pub fn from_tokenizer(tokenizer: Tokenizer<'x, F>) -> Self {
28        Self {
29            tokenizer,
30            output: Vec::new(),
31            operator_stack: Vec::new(),
32            arg_count: Vec::new(),
33        }
34    }
35
36    pub fn parse(mut self) -> Result<Self, String> {
37        let mut last_is_var_or_fnc = false;
38
39        while let Some(token) = self.tokenizer.next()? {
40            let mut is_var_or_fnc = false;
41            match token {
42                Token::Variable(v) => {
43                    self.inc_arg_count();
44                    is_var_or_fnc = true;
45                    self.output.push(Expression::Variable(v))
46                }
47                Token::Number(n) => {
48                    self.inc_arg_count();
49                    self.output.push(Expression::Constant(n.into()))
50                }
51                Token::String(s) => {
52                    self.inc_arg_count();
53                    self.output.push(Expression::Constant(s.into()))
54                }
55                Token::UnaryOperator(uop) => {
56                    self.operator_stack.push((Token::UnaryOperator(uop), None))
57                }
58                Token::OpenParen => self.operator_stack.push((token, None)),
59                Token::CloseParen | Token::CloseBracket => {
60                    let expect_token = if matches!(token, Token::CloseParen) {
61                        Token::OpenParen
62                    } else {
63                        Token::OpenBracket
64                    };
65                    loop {
66                        match self.operator_stack.pop() {
67                            Some((t, _)) if t == expect_token => {
68                                break;
69                            }
70                            Some((Token::BinaryOperator(bop), jmp_pos)) => {
71                                self.update_jmp_pos(jmp_pos);
72                                self.output.push(Expression::BinaryOperator(bop))
73                            }
74                            Some((Token::UnaryOperator(uop), _)) => {
75                                self.output.push(Expression::UnaryOperator(uop))
76                            }
77                            _ => return Err("Mismatched parentheses".to_string()),
78                        }
79                    }
80
81                    if let Some((Token::Function { id, num_args, name }, _)) =
82                        self.operator_stack.last()
83                    {
84                        let got_args = self.arg_count.pop().unwrap();
85                        if got_args != *num_args as i32 {
86                            return Err(if *id != u32::MAX {
87                                format!(
88                                    "Expression function {:?} expected {} arguments, got {}",
89                                    name, num_args, got_args
90                                )
91                            } else {
92                                "Missing array index".to_string()
93                            });
94                        }
95
96                        let expr = match *id {
97                            ID_ARRAY_ACCESS => Expression::ArrayAccess,
98                            ID_ARRAY_BUILD => Expression::ArrayBuild(*num_args),
99                            id => Expression::Function {
100                                id,
101                                num_args: *num_args,
102                            },
103                        };
104
105                        self.operator_stack.pop();
106                        self.output.push(expr);
107                    }
108
109                    is_var_or_fnc = true;
110                }
111                Token::BinaryOperator(bop) => {
112                    self.dec_arg_count();
113                    while let Some((top_token, prev_jmp_pos)) = self.operator_stack.last() {
114                        match top_token {
115                            Token::BinaryOperator(top_bop) => {
116                                if bop.precedence() <= top_bop.precedence() {
117                                    let top_bop = *top_bop;
118                                    let jmp_pos = *prev_jmp_pos;
119                                    self.update_jmp_pos(jmp_pos);
120                                    self.operator_stack.pop();
121                                    self.output.push(Expression::BinaryOperator(top_bop));
122                                } else {
123                                    break;
124                                }
125                            }
126                            Token::UnaryOperator(top_uop) => {
127                                let top_uop = *top_uop;
128                                self.operator_stack.pop();
129                                self.output.push(Expression::UnaryOperator(top_uop));
130                            }
131                            _ => break,
132                        }
133                    }
134
135                    // Add jump instruction for short-circuiting
136                    let jmp_pos = match bop {
137                        BinaryOperator::And => {
138                            self.output.push(Expression::JmpIf { val: false, pos: 0 });
139                            Some(self.output.len() - 1)
140                        }
141                        BinaryOperator::Or => {
142                            self.output.push(Expression::JmpIf { val: true, pos: 0 });
143                            Some(self.output.len() - 1)
144                        }
145                        _ => None,
146                    };
147
148                    self.operator_stack
149                        .push((Token::BinaryOperator(bop), jmp_pos));
150                }
151                Token::Function { id, name, num_args } => {
152                    self.inc_arg_count();
153                    self.arg_count.push(0);
154                    self.operator_stack
155                        .push((Token::Function { id, name, num_args }, None))
156                }
157                Token::OpenBracket => {
158                    // Array functions
159                    let (id, num_args, arg_count) = if last_is_var_or_fnc {
160                        (ID_ARRAY_ACCESS, 2, 1)
161                    } else {
162                        self.inc_arg_count();
163                        (ID_ARRAY_BUILD, 0, 0)
164                    };
165                    self.arg_count.push(arg_count);
166                    self.operator_stack.push((
167                        Token::Function {
168                            id,
169                            name: String::from("array"),
170                            num_args,
171                        },
172                        None,
173                    ));
174                    self.operator_stack.push((token, None));
175                }
176                Token::Comma => {
177                    while let Some((token, jmp_pos)) = self.operator_stack.last() {
178                        match token {
179                            Token::OpenParen => break,
180                            Token::BinaryOperator(bop) => {
181                                let bop = *bop;
182                                let jmp_pos = *jmp_pos;
183                                self.update_jmp_pos(jmp_pos);
184                                self.output.push(Expression::BinaryOperator(bop));
185                                self.operator_stack.pop();
186                            }
187                            Token::UnaryOperator(uop) => {
188                                self.output.push(Expression::UnaryOperator(*uop));
189                                self.operator_stack.pop();
190                            }
191                            _ => break,
192                        }
193                    }
194                }
195            }
196            last_is_var_or_fnc = is_var_or_fnc;
197        }
198
199        while let Some((token, jmp_pos)) = self.operator_stack.pop() {
200            match token {
201                Token::BinaryOperator(bop) => {
202                    self.update_jmp_pos(jmp_pos);
203                    self.output.push(Expression::BinaryOperator(bop))
204                }
205                Token::UnaryOperator(uop) => self.output.push(Expression::UnaryOperator(uop)),
206                _ => return Err("Invalid token on the operator stack".to_string()),
207            }
208        }
209
210        Ok(self)
211    }
212
213    fn inc_arg_count(&mut self) {
214        if let Some(x) = self.arg_count.last_mut() {
215            *x = x.saturating_add(1);
216            let op_pos = self.operator_stack.len().saturating_sub(2);
217            match self.operator_stack.get_mut(op_pos) {
218                Some((Token::Function { num_args, id, .. }, _)) if *id == ID_ARRAY_BUILD => {
219                    *num_args += 1;
220                }
221                _ => {}
222            }
223        }
224    }
225
226    fn dec_arg_count(&mut self) {
227        if let Some(x) = self.arg_count.last_mut() {
228            *x = x.saturating_sub(1);
229        }
230    }
231
232    fn update_jmp_pos(&mut self, jmp_pos: Option<usize>) {
233        if let Some(jmp_pos) = jmp_pos {
234            let cur_pos = self.output.len();
235            if let Expression::JmpIf { pos, .. } = &mut self.output[jmp_pos] {
236                *pos = (cur_pos - jmp_pos) as u32;
237            } else {
238                #[cfg(test)]
239                panic!("Invalid jump position");
240            }
241        }
242    }
243}
244
245impl BinaryOperator {
246    fn precedence(&self) -> i32 {
247        match self {
248            BinaryOperator::Multiply | BinaryOperator::Divide => 7,
249            BinaryOperator::Add | BinaryOperator::Subtract => 6,
250            BinaryOperator::Gt | BinaryOperator::Ge | BinaryOperator::Lt | BinaryOperator::Le => 5,
251            BinaryOperator::Eq | BinaryOperator::Ne => 4,
252            BinaryOperator::Xor => 3,
253            BinaryOperator::And => 2,
254            BinaryOperator::Or => 1,
255        }
256    }
257}
sieve/compiler/grammar/expr/parser.rs

sieve/compiler/grammar/expr/
parser.rs
