policy_engine/
parser.rs

1use crate::{tokenizer::Token, error::ParseError};
2
3/// `Expression` contains all the possible type of symbols that can be parsed.
4/// 
5#[derive(Debug, PartialEq)]
6pub enum Expression {
7    Variable(String),
8    Literal(String),
9    Binary(Box<Expression>, Operator, Box<Expression>),
10    Equal(Box<Expression>, Box<Expression>),
11    Greater(Box<Expression>, Box<Expression>),
12    Less(Box<Expression>, Box<Expression>),
13    GreaterEqual(Box<Expression>, Box<Expression>),
14    LessEqual(Box<Expression>, Box<Expression>),
15    NotEqual(Box<Expression>, Box<Expression>),
16}
17
18/// `Operator` contains all the possible operators that can be used
19/// 
20/// In `parse_expression`, the tokens are parsed by breaking the stream down to
21/// a series of `and` or `or` operators.
22#[derive(Debug, PartialEq)]
23pub enum Operator {
24    And,
25    Or,
26}
27
28/// Parse a logical expression – the most simplest and final part of the parser.
29/// 
30/// This is where the identifers and literals are parsed.
31fn parse_primary(tokens: &mut std::iter::Peekable<std::slice::Iter<Token>>) -> Result<Option<Expression>, ParseError> {
32    match tokens.next().ok_or(ParseError::InvalidSyntax)? {
33        Token::Identifier(id) => Ok(Some(Expression::Variable(id.clone()))),
34        Token::Literal(value) => Ok(Some(Expression::Literal(value.clone()))),
35        Token::OpenParen => {
36            let expr = parse_expression(tokens)?;
37            if let Some(Token::CloseParen) = tokens.next() {
38                Ok(Some(expr.unwrap()))
39            } else {
40                Err(ParseError::MissingToken(Token::CloseParen))            
41            }
42        }
43        token => Err(ParseError::UnexpectedToken(token.clone())),
44        //Some(token) => Err(ParseError::UnexpectedToken(token.clone())),
45        //None => Ok(None),
46    }
47}
48
49/// Parse a comparison expression – the third stage of the parser. 
50/// 
51/// Here, the tokens are a which is a primary expression followed 
52/// by an operator and another primary expression
53/// 
54/// Basically, depending on the operator, the expression is parsed accordingly.
55/// 
56/// This is called by `parse_expression`, which is the second stage of the parser.
57fn parse_comparison(tokens: &mut std::iter::Peekable<std::slice::Iter<Token>>) -> Result<Option<Expression>, ParseError> {
58    let left = parse_primary(tokens)?;
59    match tokens.peek().copied() {
60        Some(Token::Equal) => {
61            tokens.next();
62            let right = parse_primary(tokens)?;
63            Ok(Some(Expression::Equal(Box::new(left.unwrap()), Box::new(right.unwrap()))))
64        }
65        Some(Token::Greater) => {
66            tokens.next();
67            let right = parse_primary(tokens)?;
68            Ok(Some(Expression::Greater(Box::new(left.unwrap()), Box::new(right.unwrap()))))
69        }
70        Some(Token::Less) => {
71            tokens.next();
72            let right = parse_primary(tokens)?;
73            Ok(Some(Expression::Less(Box::new(left.unwrap()), Box::new(right.unwrap()))))
74        }
75        Some(Token::GreaterEqual) => {
76            tokens.next();
77            let right = parse_primary(tokens)?;
78            Ok(Some(Expression::GreaterEqual(Box::new(left.unwrap()), Box::new(right.unwrap()))))
79        }
80        Some(Token::LessEqual) => {
81            tokens.next();
82            let right = parse_primary(tokens)?;
83            Ok(Some(Expression::LessEqual(Box::new(left.unwrap()), Box::new(right.unwrap()))))
84        }
85        Some (Token::NotEqual) => {
86            tokens.next();
87            let right = parse_primary(tokens)?;
88            Ok(Some(Expression::NotEqual(Box::new(left.unwrap()), Box::new(right.unwrap()))))
89        }
90        _ => Ok(Some(left.unwrap())),
91    }
92}
93
94/// Parse an expression – the second stage of the parser.
95/// 
96/// An expression is parsed which is a series of comparisons separated by 
97/// `and` or `or` operators, and each comparisons are parsed.
98/// 
99/// # Panics
100/// # Errors
101/// Returns an error if the expression is invalid.
102pub fn parse_expression(tokens: &mut std::iter::Peekable<std::slice::Iter<Token>>) -> Result<Option<Expression>, ParseError> {
103    let mut left = parse_comparison(tokens)?;
104    while let Some(&Token::And | &Token::Or) = tokens.peek() {
105        let op = match tokens.next() {
106            Some(Token::And) => Operator::And,
107            Some(Token::Or) => Operator::Or,
108            _ => unreachable!(),
109        };
110        let right = parse_comparison(tokens)?;
111        left = Some(Expression::Binary(Box::new(left.unwrap()), op, Box::new(right.unwrap())));
112    }
113    Ok(Some(left.unwrap()))
114}
115
116/// Evaluate two parsed expressions – the first stage of the parser.
117/// 
118/// Given two expressions of type Expression, `evaluate_expressions` will return on
119/// the basis of the comparison between the two expressions.
120/// 
121/// This is an implementation of a recursive descent parser
122/// 
123/// # Panics
124///
125/// Panics if the expression is invalid.
126#[must_use] pub fn evaluate_expressions(expr1: &Expression, expr2: &Expression) -> bool {
127    // If the expressions are completely equal, return true
128    if expr1 == expr2 {
129        true
130    } else if let Expression::Binary(e1a, op, e1b) = expr1 {
131        if *op == Operator::And {
132            // expr1 is an AND expression, check if both its left and right subtree match expr2
133            evaluate_expressions(e1a, expr2) && evaluate_expressions(e1b, expr2)
134        } else if *op == Operator::Or {
135            // expr1 is an OR expression, check if either its left or right subtree match expr2
136            evaluate_expressions(e1a, expr2) || evaluate_expressions(e1b, expr2)
137        } else {
138            false
139        }
140    } else if let Expression::Binary(e2a, Operator::Or, e2b) = expr2 {
141        // OR expression in expr2
142        evaluate_expressions(expr1, e2a) || evaluate_expressions(expr1, e2b)
143    } else if let Expression::Binary(e1a, Operator::And, e1b) = expr1 {
144        // expr1 is a binary AND expression, check if expr2 matches either of its subtrees
145        evaluate_expressions(e1a, expr2) || evaluate_expressions(e1b, expr2)
146    } else if let Expression::Binary(e2a, Operator::And, e2b) = expr2 {
147        // expr2 is a binary AND expression, check if expr1 matches either of its subtrees
148        evaluate_expressions(expr1, e2a) || evaluate_expressions(expr1, e2b)
149    } else if let Expression::Binary(e1a, Operator::Or, e1b) = expr1 {
150        // expr1 is a binary OR expression, check if expr2 matches either of its subtrees
151        evaluate_expressions(e1a, expr2) || evaluate_expressions(e1b, expr2)
152    } else if let Expression::Equal(e1a, e1b) = expr1 {
153        if let Expression::Equal(e2a, e2b) = expr2 {
154            evaluate_expressions(e1a, e2a) && evaluate_expressions(e1b, e2b)
155        } else {
156            false
157        }
158    // Parsing ```!=```
159    } else if let Expression::NotEqual(_e1a, e1b) = expr1 {
160            if let Expression::Equal(_e2a, e2b) = expr2 {
161                if let Expression::Literal(val1) = &**e1b {
162                    if let Expression::Literal(val2) = &**e2b {
163                        if let Ok(num1) = val1.parse::<i32>() {
164                            if let Ok(num2) = val2.parse::<i32>() {
165                                return num2 != num1;
166                            }
167                        }
168                    }
169                }
170            }
171        false
172    // Parsing ```<=```
173    } else if let Expression::Greater(_e1a, e1b) = expr1 {
174        if let Expression::Equal(_e2a, e2b) = expr2 {
175            if let Expression::Literal(val1) = &**e1b {
176                if let Expression::Literal(val2) = &**e2b {
177                    if let Ok(num1) = val1.parse::<i32>() {
178                        if let Ok(num2) = val2.parse::<i32>() {
179                            return num2 > num1;
180                        }
181                    }
182                }
183            }
184        }
185        false
186
187    // This is for ```>=``` to work with an ```=``` in the query
188    } else if let Expression::GreaterEqual(_e1a, e1b) = expr1 {
189        if let Expression::Equal(_e2a, e2b) = expr2 {
190            if let Expression::Literal(val1) = &**e1b {
191                if let Expression::Literal(val2) = &**e2b {
192                    if let Ok(num1) = val1.parse::<i32>() {
193                        if let Ok(num2) = val2.parse::<i32>() {
194                            return num2 >= num1;
195                        }
196                    }
197                }
198            }
199        }
200        false
201    // This is for ```<=``` to work with an ```=``` in the query
202    } else if let Expression::LessEqual(_e1a, e1b) = expr1 {
203        if let Expression::Equal(_e2a, e2b) = expr2 {
204            if let Expression::Literal(val1) = &**e1b {
205                if let Expression::Literal(val2) = &**e2b {
206                    if let Ok(num1) = val1.parse::<i32>() {
207                        if let Ok(num2) = val2.parse::<i32>() {
208                            return num2 <= num1;
209                        }
210                    }
211                }
212            }
213        }
214        false
215    // This is for ```<``` to work with an ```=``` in the query
216    } else if let Expression::Less(_e1a, e1b) | Expression::LessEqual(_e1a, e1b) = expr1 {
217        if let Expression::Equal(_e2a, e2b) = expr2 {
218            if let Expression::Literal(val1) = &**e1b {
219                if let Expression::Literal(val2) = &**e2b {
220                    if let Ok(num1) = val1.parse::<i32>() {
221                        if let Ok(num2) = val2.parse::<i32>() {
222                            return num2 < num1;
223                        }
224                    }
225                }
226            }
227        }
228        false
229    } else if let Expression::Less(e1a, e1b) = expr1 {
230        if let Expression::Less(e2a, e2b) = expr2 {
231            evaluate_expressions(e1a, e2a) && evaluate_expressions(e1b, e2b)
232        } else {
233            false
234        }
235    } else {
236        false
237    }
238}
policy_engine/parser.rs

policy_engine/
parser.rs
