logic_parser/parsing/
parser.rs

1use crate::errors::ParserError;
2use crate::lexing::token::{Token, TokenKind};
3use ParserError::{UnexpectedToken, UnexpectedEOF};
4
5use super::node::ASTNode;
6
7pub type Result<T> = std::result::Result<T, ParserError>;
8
9#[derive(Debug)]
10pub struct Parser<'a> {
11    tokens: &'a Vec<Token>,
12    pos: usize
13}
14
15impl Parser<'_> {
16    pub fn new(tokens: &Vec<Token>) -> Parser {
17        Parser { tokens, pos: 0 }
18    }
19
20    /// Logic expressions parser
21    ///
22    /// ```yaml
23    /// expr: term [(<-> | ->) expr]
24    /// term: prop [(|| | &&) term]
25    /// prop: [~] (true | false | "name" | LPAREN expr RPAREN)
26    /// ```
27    pub fn parse(&mut self) -> Result<ASTNode> {
28        let ast = self.parse_expression()?;
29        // If expression was not completedly parsed, return an error
30        if let Some(t) = self.consume() {
31            return Err(UnexpectedToken(format!("'{t}'", t=t.kind), t.span))
32        }
33        Ok(ast)
34    }
35
36    fn parse_expression(&mut self) -> Result<ASTNode> {
37        let l_term = self.parse_term()?;
38
39        match self.peek().cloned() {
40            Some(TokenKind::Implies) => {
41                self.consume();
42                Ok(ASTNode::Implies {
43                    left: Box::new(l_term),
44                    right: Box::new(self.parse_expression()?)
45                })
46            },
47            Some(TokenKind::IfAndOnlyIf) => {
48                self.consume();
49                Ok(ASTNode::IfAndOnlyIf {
50                    left: Box::new(l_term),
51                    right: Box::new(self.parse_expression()?)
52                })
53            },
54            Some(_) => Ok(l_term),
55            None => Ok(l_term)
56        }
57    }
58
59    fn parse_term(&mut self) -> Result<ASTNode> {
60        let l_term = self.parse_proposition()?;
61
62        match self.peek().cloned() {
63            Some(TokenKind::And) => {
64                self.consume();
65                Ok(ASTNode::And {
66                    left: Box::new(l_term),
67                    right: Box::new(self.parse_term()?)
68                })
69            },
70            Some(TokenKind::Or) => {
71                self.consume();
72                Ok(ASTNode::Or {
73                    left: Box::new(l_term),
74                    right: Box::new(self.parse_term()?)
75                })
76            },
77            Some(_) => Ok(l_term),
78            None => Ok(l_term)
79        }
80    }
81
82    fn parse_proposition(&mut self) -> Result<ASTNode> {
83        let next_token = match self.consume().cloned() {
84            Some(t) => t,
85            None => {
86                // Gets the last token span, otherwise (start: 0, end: 0)
87                let last_span = self.tokens.last().map(|t| t.span).unwrap_or((0, 0).into());
88                return Err(
89                    UnexpectedEOF("Expected [~] (true | false | variable | (...))".into(), last_span)
90                )
91            },
92        };
93
94        match next_token.kind {
95            TokenKind::Identifier(name) => {
96                Ok(ASTNode::Identifier { name: name.to_owned() })
97            },
98            TokenKind::Literal(boolean) => {
99                Ok(ASTNode::Literal { value: boolean })
100            },
101            TokenKind::Not => {
102                let prop = self.parse_proposition()?;
103                Ok(ASTNode::Not{ operand: Box::new(prop) })
104            },
105            TokenKind::OpenParen => {
106                let expr = self.parse_expression()?;
107                if let Some(TokenKind::CloseParen) = self.peek() {
108                    self.consume();
109                    Ok(expr)
110                }
111                else {
112                    Err(UnexpectedToken("R_PAREN expected".into(), next_token.span))
113                }
114            },
115            TokenKind::CloseParen => {
116                Err(UnexpectedToken("R_PAREN".into(), next_token.span))
117            },
118            other @ (TokenKind::And | TokenKind::Or | TokenKind::Implies | TokenKind::IfAndOnlyIf) => {
119                Err(UnexpectedToken(format!("'{other}'"), next_token.span))
120            }
121        }
122    }
123
124    fn consume(&mut self) -> Option<&Token> {
125        let token = self.tokens.get(self.pos);
126        if token.is_some() {
127            self.pos += 1;
128        }
129        token
130    }
131
132    fn peek(&self) -> Option<&TokenKind> {
133        self.tokens.get(self.pos).map(|t| &t.kind)
134    }
135}
136
137#[cfg(test)]
138mod test {
139    use super::*;
140    use crate::lexing::Lexer;
141    use std::error::Error;
142    use std::result::Result;
143
144    #[test]
145    fn complex_json_rendered_properly() -> Result<(), Box<dyn Error>> {
146        use assert_json::assert_json;
147        let tokens = Lexer::new().tokenize("((p || q)) => (q & ~(r))")?;
148        let ast = Parser::new(&tokens).parse()?;
149        let result = ast.as_json();
150
151        assert_json!(result.as_str(), {
152            "type": "operator.implies",
153            "left": {
154                "type": "operator.or",
155                "left": {
156                    "type": "identifier",
157                    "name": "p"
158                },
159                "right": {
160                    "type": "identifier",
161                    "name": "q"
162                }
163            },
164            "right": {
165                "type": "operator.and",
166                "left": {
167                    "type": "identifier",
168                    "name": "q"
169                },
170                "right": {
171                    "type": "operator.not",
172                    "operand": {
173                        "type": "identifier",
174                        "name": "r"
175                    }
176                }
177            }
178        });
179        Ok(())
180    }
181
182    #[test]
183    fn multiple_negation_works() -> Result<(), Box<dyn Error>> {
184        use assert_json::assert_json;
185        let tokens = Lexer::new().tokenize("~~~negate_me")?;
186        let ast = Parser::new(&tokens).parse()?;
187        let result = ast.as_json();
188
189        assert_json!(result.as_str(), {
190            "type": "operator.not",
191            "operand": {
192                "type": "operator.not",
193                "operand": {
194                    "type": "operator.not",
195                    "operand": {
196                        "type": "identifier",
197                        "name": "negate_me"
198                    }
199                }
200            }
201        });
202        Ok(())
203    }
204
205    #[test]
206    fn iff_and_implies_work_together() -> Result<(), Box<dyn Error>> {
207        use assert_json::assert_json;
208        let tokens = Lexer::new().tokenize("(a => b) <=> c")?;
209        let ast = Parser::new(&tokens).parse()?;
210        let result = ast.as_json();
211
212        assert_json!(result.as_str(), {
213            "type": "operator.iff",
214            "left": {
215                "type": "operator.implies",
216                "left": {
217                    "type": "identifier",
218                    "name": "a"
219                },
220                "right": {
221                    "type": "identifier",
222                    "name": "b"
223                }
224            },
225            "right": {
226                "type": "identifier",
227                "name": "c"
228            }
229        });
230        Ok(())
231    }
232
233    #[test]
234    fn alternative_syntax_work() -> Result<(), Box<dyn Error>> {
235        use assert_json::assert_json;
236        let tokens = Lexer::new().tokenize("(a & b) && ((b | c) || b)")?;
237        let ast = Parser::new(&tokens).parse()?;
238        let result = ast.as_json();
239
240        assert_json!(result.as_str(), {
241            "type": "operator.and",
242            "left": {
243                "type": "operator.and",
244                "left": {
245                    "type": "identifier",
246                    "name": "a"
247                },
248                "right": {
249                    "type": "identifier",
250                    "name": "b"
251                }
252            },
253            "right": {
254                "type": "operator.or",
255                "left": {
256                    "type": "operator.or",
257                    "left": {
258                        "type": "identifier",
259                        "name": "b"
260                    },
261                    "right": {
262                        "type": "identifier",
263                        "name": "c"
264                    }
265                },
266                "right": {
267                    "type": "identifier",
268                    "name": "b"
269                }
270            }
271        });
272        Ok(())
273    }
274
275    #[test]
276    fn unmatched_paren_left_results_on_error() {
277        let tokens = Lexer::new().tokenize("((a => b) <=> c").unwrap();
278        let parse_error = Parser::new(&tokens).parse().unwrap_err();
279
280        match parse_error {
281            ParserError::UnexpectedToken(_, span) => {
282                assert_eq!(span, (0, 1).into())
283            },
284            _ => unreachable!()
285        }
286    }
287
288    #[test]
289    fn unmatched_paren_right_results_on_error() {
290        let tokens = Lexer::new().tokenize("(a => b)) <=> c").unwrap();
291
292        let parse_error = Parser::new(&tokens).parse().unwrap_err();
293        match parse_error {
294            ParserError::UnexpectedToken(_, span) => {
295                assert_eq!(span, (8, 9).into())
296            },
297            _ => unreachable!()
298        }
299    }
300
301    #[test]
302    fn parsing_custom_expressions() {
303        let query = "(tag:pink || tag:anime) && (mime:image/* || mime:video/*)";
304        let mut lexer = Lexer::with_alphabets(
305            |c| c.is_alphanumeric() || c == '_' || c == ':' || c == '*' || c == '/',
306            |c| c.is_alphabetic(),
307        );
308
309        let tokens = lexer.tokenize(query).unwrap();
310
311        let mut parser = Parser::new(&tokens);
312        parser.parse().unwrap();
313    }
314}
logic_parser/parsing/parser.rs

logic_parser/parsing/
parser.rs
