bexeval/
parser.rs

1use std::collections::HashMap;
2use crate::lexer::{Lexer, LexToken};
3use crate::value_type::Integer;
4
5#[derive(Clone, Debug, PartialEq)]
6pub struct ParserError {
7    msg: String,
8}
9
10impl ParserError {
11    pub fn new(msg: &str) -> ParserError {
12        ParserError {
13            msg: msg.to_string(),
14        }
15    }
16    pub fn msg(&self) -> &str {
17        self.msg.as_str()
18    }
19}
20impl std::fmt::Display for ParserError {
21    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
22        write!(f, "{}", self.msg())
23    }
24}
25impl std::error::Error for ParserError {}
26
27pub struct Parser<T: Integer = i32> {
28    _phantom: std::marker::PhantomData<T>
29}
30
31/// By default, `i32` is used as the value type
32impl Default for Parser {
33    fn default() -> Self {
34        Parser::<i32>::new()
35    }
36}
37
38impl<T: Integer> Parser<T> {
39
40    pub fn new() -> Self {
41        Self {
42            _phantom: std::marker::PhantomData,
43        }
44    }
45
46    /// Available when expression string does not contain variables
47    pub fn eval(&self, src: &str) -> Result<T, ParserError>{
48        self.eval_inner(src, &HashMap::new())
49    }
50
51    /// Used when the expression string contains variables
52    /// The ctx argument stores information about the variable in array of tuples(&str, T).
53    pub fn eval_context(&self, src: &str, ctx: &[(&str, T)]) -> Result<T, ParserError> {
54        self.eval_inner(src, &HashMap::from_iter(ctx.iter().map(|(s, i)| (s.to_string(), *i))))
55    }
56
57    /// Internal method to convert the expression string to integer values
58    pub(crate) fn eval_inner(&self, src: &str, ctx: &HashMap<String, T>) -> Result<T, ParserError> {
59        let mut stack = Vec::new();
60        for token in self.to_rpn(src)?.into_iter() {
61            match token {
62                Token::Value(val) => {stack.push(val);},
63                Token::Variable(var) => {
64                    if let Some(&val) = ctx.get(&var) {
65                        stack.push(val);
66                    }
67                    else {
68                        return Err(ParserError::new(format!("Undefined Variable: {}", var).as_str()));
69                    }
70                },
71                Token::Unary(op) => {
72                    if let Some(val) = stack.pop() {
73                        stack.push(op.eval(val));
74                    }
75                    else {
76                        return Err(ParserError::new("The expression is incorrect"));
77                    }
78                },
79                Token::Binary(op) => {
80                    if let (Some(val2), Some(val1)) = (stack.pop(), stack.pop()) {
81                        stack.push(op.eval(val1, val2));
82                    }
83                    else {
84                        return Err(ParserError::new("The expression is incorrect"));
85                    }
86                }
87                Token::Function(func) => {
88                    let ret = match func.n_arg() {
89                        1 => {
90                            if let Some(val) = stack.pop() {
91                                func.eval1(val)
92                            }
93                            else {
94                                return Err(ParserError::new("The expression is incorrect"));
95                            }
96                        },
97                        2 => {
98                            if let (Some(val2), Some(val1)) = (stack.pop(), stack.pop()) {
99                                func.eval2(val1, val2)
100                            }
101                            else {
102                                return Err(ParserError::new("The expression is incorrect"));
103                            }
104                        }
105                        _ => unreachable!()
106                    };
107                    stack.push(ret);
108                },
109                _ => {
110                    return Err(ParserError::new("The expression is incorrect"));
111                }
112            }
113        }
114        if stack.len() == 1 {
115            Ok(stack.pop().unwrap())
116        }
117        else {
118            Err(ParserError::new("Failed to evaluate"))
119        }
120    }
121    
122    /// From a string statement of the form “var = expr”, evaluate `expr` and assign it to `var`.
123    /// Example of `src` argument : 
124    /// "x = 2 + 6"
125    /// "y = x * 2"
126    /// ParserError if `expr` contains a variable with no information
127    pub(crate) fn parse_statement(&self, stmt: &str, ctx: &HashMap<String, T>) -> Result<(String, T), ParserError> {
128        let mut split = stmt.splitn(2, '=');
129        if let (Some(var_str), Some(expr)) = (split.next(), split.next()) {
130            let mut var_iter = Lexer::new(var_str)?.into_iter();
131            
132            let var = if let (Some(LexToken::Variable(s)), None) = (var_iter.next(), var_iter.next()) {
133                s
134            }
135            else {
136                return Err(ParserError::new("The syntax on the left side is incorrect"));
137            };
138            
139            let val = self.eval_inner(expr, ctx)?;
140
141            Ok((var, val))
142        }
143        else {
144            Err(ParserError::new("The format of the statement must be \"var = expression\""))
145        }
146    }
147
148    /// Convert LexToken to Token and then to Reverse Polish Notation
149    /// Overflow due to the type of the number is treated as a ParserError
150    /// If the number type is u8, strings parsed as greater than 256 will result in a ParserError
151    /// (Based on the rules of the `from_str` function)
152    fn to_rpn(&self, src: &str) -> Result<Vec<Token<T>>, ParserError> {
153        // from lextokens to tokens
154        let mut tokens = Vec::new();
155        let mut paren_count = 0;
156        let mut lt_iter = Lexer::new(src)?.into_iter().peekable();
157        while let Some(lt) = lt_iter.next() {
158            match lt {
159                LexToken::LeftParen => {
160                    tokens.push(Token::Symbol(Symbol::LeftParen));
161                    paren_count += 1;
162                },
163                LexToken::RightParen => {
164                    tokens.push(Token::Symbol(Symbol::RightParen));
165                    paren_count -= 1;
166                },
167                LexToken::Comma => {
168                    tokens.push(Token::Symbol(Symbol::Comma));
169                },
170                LexToken::Plus => {
171                    tokens.push(Token::Binary(BinOp::Add));
172                },
173                LexToken::Minus => {
174                    match tokens.last() {
175                        Some(Token::Symbol(Symbol::RightParen)) | Some(Token::Value(_)) | Some(Token::Variable(_)) => {
176                            tokens.push(Token::Binary(BinOp::Sub));
177                        },
178                        _ => {tokens.push(Token::Unary(UnaryOp::Neg));}   
179                    }
180                },
181                LexToken::Star => {
182                    tokens.push(Token::Binary(BinOp::Mul));
183                },
184                LexToken::Slash => {
185                    tokens.push(Token::Binary(BinOp::Div));
186                },
187                LexToken::Percent => {
188                    tokens.push(Token::Binary(BinOp::Mod));
189                },
190                LexToken::And => {
191                    tokens.push(Token::Binary(BinOp::And));
192                },
193                LexToken::Or => {
194                    tokens.push(Token::Binary(BinOp::Or));
195                },
196                LexToken::Xor => {
197                    tokens.push(Token::Binary(BinOp::Xor));
198                },
199                LexToken::Not => {
200                    tokens.push(Token::Unary(UnaryOp::Not));
201                },
202                LexToken::Less => {
203                    tokens.push(Token::Binary(BinOp::Less));
204                },
205                LexToken::LessEqual => {
206                    tokens.push(Token::Binary(BinOp::LessEqual));
207                },
208                LexToken::Greater => {
209                    tokens.push(Token::Binary(BinOp::Greater));
210                },
211                LexToken::GreaterEqual => {
212                    tokens.push(Token::Binary(BinOp::GreaterEqual));
213                },
214                LexToken::LeftShift => {
215                    tokens.push(Token::Binary(BinOp::Shl));
216                },
217                LexToken::RightShift => {
218                    tokens.push(Token::Binary(BinOp::Shr));
219                },
220                LexToken::Equal => {
221                    tokens.push(Token::Equal);
222                },
223                LexToken::EqualEqual => {
224                    tokens.push(Token::Binary(BinOp::EqualEqual));
225                },
226                LexToken::NotEqual => {
227                    tokens.push(Token::Binary(BinOp::NotEqual));
228                },
229                LexToken::Variable(s) => {
230                    if let Some(LexToken::LeftParen) = lt_iter.peek() {
231                        tokens.push(Token::Function(s.parse::<Function>()?));
232                    }
233                    else {
234                        tokens.push(Token::Variable(s));
235                    }
236                }
237                LexToken::Number(s) => {
238                    let n = match s.replace("_", "").parse::<T>() {
239                        Ok(n) => {n},
240                        Err(_) => {
241                            return Err(ParserError::new(format!("Cannot parse string \"{}\" to {}", s, std::any::type_name::<T>()).as_str()));
242                        }
243                    };
244                    tokens.push(Token::Value(n));
245                }
246            }
247            if paren_count < 0 {
248                return Err(ParserError::new("The number of parentheses does not match"));
249            }
250        }
251        
252        if paren_count != 0 {
253            return Err(ParserError::new("The number of parentheses does not match"));
254        }
255        
256
257        // From Infix notation to Reverse Polish Notation using Shunting yard Algorithm
258        let mut rpn_stack: Vec<Token<T>> = Vec::new();
259        let mut op_stack: Vec<Token<T>> = Vec::new();
260
261        for token in tokens.into_iter() {
262            match token {
263                Token::Variable(_) | Token::Value(_) => {
264                    rpn_stack.push(token);
265                }
266                _ => {
267                    let (lp, _) = token.precedence();
268                    while let Some(top_token) = op_stack.last() {
269                        let (_, rp) = top_token.precedence();
270                        if lp > rp {
271                            break;
272                        }
273                        rpn_stack.push(op_stack.pop().unwrap());
274                    }
275
276                    if matches!(token, Token::Symbol(Symbol::RightParen)) {
277                        match op_stack.last() {
278                            Some(Token::Symbol(Symbol::LeftParen)) => {
279                                op_stack.pop();
280                                if let Some(Token::Function(_)) = op_stack.last() {
281                                    rpn_stack.push(op_stack.pop().unwrap());
282                                }
283                                continue;
284                            },
285                            _ => {
286                                return Err(ParserError::new("Unexpected parenthesis"));
287                            }
288                        }
289                    }
290
291                    if !matches!(token, Token::Symbol(Symbol::Comma)) {
292                        op_stack.push(token);
293                    }
294                }
295            }
296        }
297
298        while let Some(top_token) = op_stack.pop() {
299            if matches!(top_token, Token::Symbol(Symbol::RightParen)) || matches!(top_token, Token::Symbol(Symbol::LeftParen)) {
300                return Err(ParserError::new("Unexpected parenthesis"));
301            }
302            rpn_stack.push(top_token);
303        }
304
305        Ok(rpn_stack)
306    }
307    
308}
309
310#[derive(Debug)]
311pub enum Token<T: Integer> {
312    Equal,
313    Symbol(Symbol),
314    Unary(UnaryOp),
315    Binary(BinOp),
316    Value(T),
317    Variable(String),
318    Function(Function),
319}
320
321#[derive(Debug)]
322pub enum Symbol {
323    LeftParen,
324    RightParen,
325    Comma,
326}
327
328#[derive(Debug)]
329pub enum UnaryOp {
330    Neg,
331    Not,
332}
333
334impl UnaryOp {
335    fn eval<T: Integer>(&self, a: T) -> T {
336        match self {
337            Self::Neg => a.wrapping_neg(),
338            Self::Not => !a,
339        }
340    }
341}
342
343#[derive(Debug)]
344pub enum BinOp {
345    Add,
346    Sub,
347    Mul,
348    Div,
349    Mod,
350    And,
351    Or,
352    Xor,
353    Shl,
354    Shr,
355    EqualEqual,
356    Less,
357    LessEqual,
358    Greater,
359    GreaterEqual,
360    NotEqual
361}
362
363impl BinOp {
364    fn eval<T: Integer>(&self, a: T, b: T) -> T {
365        match self {
366            Self::Add => a.wrapping_add(&b),
367            Self::Sub => a.wrapping_sub(&b),
368            Self::Mul => a.wrapping_mul(&b),
369            Self::Div => a / b,
370            Self::Mod => a % b,
371            Self::And => a & b,
372            Self::Or => a | b,
373            Self::Xor => a ^ b,
374            Self::Shl => a.wrapping_shl(b.as_()),
375            Self::Shr => a.wrapping_shr(b.as_()),
376            Self::EqualEqual => T::from(a == b),
377            Self::Less => T::from(a < b),
378            Self::LessEqual => T::from(a <= b),
379            Self::Greater => T::from(a > b),
380            Self::GreaterEqual => T::from(a >= b),
381            Self::NotEqual => T::from(a != b),
382        }
383    }
384}
385
386#[derive(Debug)]
387pub enum Function {
388    Pow,
389    Max,
390    Min,
391    Abs,
392    AbsDiff,
393    CountOnes,
394    CountZeros,
395    LeadingZeros,
396    TrailingZeros,
397    RotateLeft,
398    RotateRight
399}
400
401impl Function {
402    fn n_arg(&self) -> u8 {
403        match self {
404            Self::Pow | Self::Max | Self::Min
405            | Self::AbsDiff 
406            | Self::RotateLeft | Self::RotateRight => {2},
407            _ => {1}
408        }
409    }
410
411    fn eval1<T: Integer>(&self, x1: T) -> T {
412        match self {
413            Self::CountOnes => x1.count_ones(),
414            Self::CountZeros => x1.count_zeros(),
415            Self::LeadingZeros => x1.leading_zeros(),
416            Self::TrailingZeros => x1.trailing_zeros(),
417            Self::Abs => x1.abs(),
418            _ => unreachable!("The number of arguments should be 1")
419        }
420    }
421
422    fn eval2<T: Integer>(&self, x1: T, x2: T) -> T {
423        match self {
424            Self::Pow => x1.wrapping_pow(x2.as_()),
425            Self::Max => x1.max(x2),
426            Self::Min => x1.min(x2),
427            Self::AbsDiff => x1.abs_diff(x2),
428            Self::RotateLeft => x1.rotate_left(x2.as_()),
429            Self::RotateRight => x1.rotate_right(x2.as_()),
430            _ => unreachable!("The number of arguments should be 2")
431        }
432    }
433}
434
435impl std::str::FromStr for Function {
436    type Err = ParserError;
437    fn from_str(s: &str) -> Result<Self, Self::Err> {
438        match s {
439            "pow" => Ok(Self::Pow),
440            "max" => Ok(Self::Max),
441            "min" => Ok(Self::Min),
442            "abs" => Ok(Self::Abs),
443            "abs_diff" => Ok(Self::AbsDiff),
444            "count_ones" => Ok(Self::CountOnes),
445            "count_zeros" => Ok(Self::CountZeros),
446            "leading_zeros" => Ok(Self::LeadingZeros),
447            "trailing_zeros" => Ok(Self::TrailingZeros),
448            "rotate_left" => Ok(Self::RotateLeft),
449            "rotate_right" => Ok(Self::RotateRight),
450            _ => Err(ParserError::new(format!("Cannot use function: {}", s).as_str()))
451        }
452    }
453}
454
455impl<T: Integer> Token<T> {
456    fn precedence(&self) -> (u8, u8) {
457        match self {
458            Self::Binary(BinOp::Add) | Self::Binary(BinOp::Sub) => (50, 51),
459            Self::Binary(BinOp::Mul) | Self::Binary(BinOp::Div) | Self::Binary(BinOp::Mod) => (55, 56),
460            Self::Binary(BinOp::Shl) | Self::Binary(BinOp::Shr) => (48, 49),
461            Self::Binary(BinOp::Less) | Self::Binary(BinOp::LessEqual)
462            | Self::Binary(BinOp::Greater) | Self::Binary(BinOp::GreaterEqual) => (44, 45),
463            Self::Binary(BinOp::EqualEqual) | Self::Binary(BinOp::NotEqual) => (42, 43),
464            Self::Binary(BinOp::And) => (39, 40),
465            Self::Binary(BinOp::Xor) => (37, 38),
466            Self::Binary(BinOp::Or) => (35, 36),
467            Self::Unary(UnaryOp::Neg) | Self::Unary(UnaryOp::Not) => (99, 80),
468            Self::Function(_) => (97, 3),
469            Self::Symbol(Symbol::LeftParen) => (99, 3),
470            Self::Symbol(Symbol::RightParen) => (4, 100),
471            Self::Equal => (2, 1),
472            Self::Symbol(Symbol::Comma) => (5, 6),
473            _ => (100, 100)
474        }
475    }
476}
477
478#[cfg(test)]
479mod tests {
480    use super::*;
481
482    #[test]
483    fn parse_expr() {
484        assert_eq!(
485            Parser::default().eval("1 + 4").unwrap(),
486            1 + 4
487        );
488        assert_eq!(
489            Parser::<i32>::new().eval("5 * 7 * 36 % 13 / 3").unwrap(),
490            5 * 7 * 36 % 13 / 3
491        );
492        assert_eq!(
493            Parser::<i32>::new().eval("1 + 2 * 3 - 8 ^ 5 & 29 | 15 / 2 % 9 & 25").unwrap(),
494            1 + 2 * 3 - 8 ^ 5 & 29 | 15 / 2 % 9 & 25
495        );
496        assert_eq!(
497            Parser::<i32>::new().eval("1+2*3-8^5&29|15/2%9&25").unwrap(),
498            1 + 2 * 3 - 8 ^ 5 & 29 | 15 / 2 % 9 & 25
499        );
500        assert_eq!(
501            Parser::<i32>::new().eval("(1 == 1) + 5 * (3 <= 2)").unwrap(),
502            1
503        );
504        assert_eq!(
505            Parser::<i32>::new().eval("max(1, 2) + min(3, 5) + pow(2, 3)").unwrap(),
506            1.max(2) + 3.min(5) + 2i32.pow(3)
507        );
508
509        assert_eq!(
510            Parser::<u8>::new().eval("123 * 146 | 126").unwrap(),
511            123u8.wrapping_mul(146) | 126
512        );
513        assert_eq!(
514            Parser::<u64>::new().eval("-1245 - 214_456").unwrap(),
515            1245u64.wrapping_neg() - 214456
516        );
517        assert_eq!(
518            Parser::<u16>::new().eval("max(1, 2) + min(3, 5) + pow(2, 3)").unwrap(),
519            1.max(2) + 3.min(5) + 2u16.pow(3)
520        );
521
522        assert!(
523            matches!(
524                Parser::<i8>::new().eval("256"),
525                Err(ParserError{..})
526            )
527        );
528        assert!(
529            matches!(
530                Parser::<i8>::new().eval("1+4 5*4"),
531                Err(ParserError{..})
532            )
533        );
534        assert!(
535            matches!(
536                Parser::<i8>::new().eval("(1+4 ) ) * 3"),
537                Err(ParserError{..})
538            )
539        );     
540        assert!(
541            matches!(
542                Parser::<i8>::new().eval("1++41"),
543                Err(ParserError{..})
544            )
545        );                                   
546    }
547
548    #[test]
549    fn parse_expr_with_context() {
550        let ctx = [("x", 5), ("y", 2)];
551        assert_eq!(
552            Parser::<i32>::new().eval_context("1 + y * 3 - (8 ^ x) | 15 / 2 % 9 & 25", &ctx).unwrap(), 
553            1 + 2 * 3 - (8 ^ 5) | 15 / 2 % 9 & 25
554        );
555        assert_eq!(
556            Parser::<i32>::new().eval_context("(1 == 0) + 5 * (3 >= y)", &ctx).unwrap(),
557            5
558        );
559        assert_eq!(
560            Parser::<i32>::new().eval_context("max(1, y) + min(9, x) + pow(2, x)", &ctx).unwrap(),
561            1.max(2) + 9.min(5) + 2i32.pow(5)
562        );
563
564        assert!(
565            matches!(
566                Parser::<i32>::new().eval_context("1+x y*4", &ctx),
567                Err(ParserError{..})
568            )
569        );
570    }
571}
bexeval/parser.rs

bexeval/
parser.rs
