predicatechecker/
parser.rs

1///! Small parser to convert a string into a predicate.
2
3
4
5// Do not use this parser for another purpose than parsing predicates.
6// A better parser would be the one used in Sloth, which is more general and more robust.
7// cf. https://github.com/MyselfLeo/sloth
8
9use std::{str::FromStr, any::type_name};
10
11use num::Num;
12
13use crate::{Predicate, Value};
14
15const VALUE_OPS: [&str; 5] = ["==", ">", "<", ">=", "<="];
16const PREDICATE_OPS: [&str; 3] = ["||", "&&", "!"];
17
18const OPERATORS: [&str; 8] = ["==", ">", "<", ">=", "<=", "||", "&&", "!"];
19const SEPARATORS: [&str; 2] = ["(", ")"];
20
21#[derive(Debug, Clone, PartialEq)]
22pub enum Token<T: Num> {
23    Boolean(bool),
24    Operator(String),
25    Separator(String),
26    Arg(String),
27    Literal(T)
28}
29
30
31
32/// Convert a string into a Vec of tokens
33pub fn parse<T: Num + FromStr>(txt: &str) -> Result<Vec<Token<T>>, String> {
34    let txt_cleaned = txt.replace("(", " ( ").replace(")", " ) ");
35    txt_cleaned.split(' ').filter(|x| !x.trim().is_empty()).map( |t|
36        if t == "true" {Ok(Token::Boolean(true))}
37        else if t == "false" {Ok(Token::Boolean(false))}
38        else if OPERATORS.contains(&t) {Ok(Token::Operator(t.to_string()))}
39        else if SEPARATORS.contains(&t) {Ok(Token::Separator(t.to_string()))}
40        else if t.parse::<T>().is_ok() {
41            match t.parse::<T>() {
42                Ok(v) => Ok(Token::Literal(v)),
43                Err(_) => return Err(format!("Unable to parse literal {t} into type {}", type_name::<T>()))
44            }
45        }
46        else if t.chars().next().unwrap().is_alphabetic() {Ok(Token::Arg(t.to_string()))}
47        else {Err(format!("Invalid token: {}", t))}
48    ).collect()
49}
50
51
52
53
54/// Convert an infix vec of tokens into a postfix stream one
55/// This function uses the Shunting-Yard algorithm
56pub fn infix_to_postfix<T: Num + FromStr>(tokens: Vec<Token<T>>) -> Result<Vec<Token<T>>, String> {
57    let mut res = vec![];
58    let mut operator_stack = vec![];
59
60    for t in tokens {
61        match &t {
62            Token::Operator(x) => {
63
64                if VALUE_OPS.contains(&x.as_str()) {    // Value operators (<, ==, etc.) have a higher precidence than boolean operators (&&, ||, etc.)
65                    while let Some(Token::Operator(x)) = operator_stack.last() {
66                        if !VALUE_OPS.contains(&x.as_str()) {break;}
67                        else {
68                            res.push(operator_stack.pop().unwrap());
69                        }
70                    }
71                }
72
73                else if PREDICATE_OPS.contains(&x.as_str()) {
74                    while let Some(Token::Operator(_)) = operator_stack.last() {
75                        res.push(operator_stack.pop().unwrap());
76                    }
77                }
78
79                operator_stack.push(t);
80            },
81
82            Token::Separator(s) => {
83                if s == "(" {
84                    operator_stack.push(t);
85                }
86                else if s == ")" {
87                    while *operator_stack.last().unwrap() != Token::Separator("(".to_string()) {
88                        res.push(operator_stack.pop().unwrap())
89                    }
90                    operator_stack.pop().unwrap();
91                }
92                else {return Err(format!("Invalid predicate string"))}
93            },
94
95            Token::Arg(_) => res.push(t),
96            Token::Literal(_) => res.push(t),
97            Token::Boolean(_) => res.push(t),
98        }
99    }    
100
101    while !operator_stack.is_empty() {
102        res.push(operator_stack.pop().unwrap())
103    }
104
105    Ok(res)
106}
107
108
109
110
111
112/// Create a predicate from a infix string for example `(x > 5) && (x < 10)
113pub fn parse_predicate<T: Num + PartialOrd + FromStr>(txt: &str) -> Result<Predicate<T>, String> {
114    let tokens = infix_to_postfix(parse(txt)?)?;
115
116    let mut predicate_stack = vec![];
117    let mut value_stack = vec![];
118
119    for token in tokens {
120
121        match token {
122
123            Token::Boolean(true) => predicate_stack.push(Predicate::True),
124            Token::Boolean(false) => predicate_stack.push(Predicate::False),
125            Token::Arg(x) => value_stack.push(Value::Arg(x)),
126            Token::Literal(l) => value_stack.push(Value::Literal(l)),
127
128
129            Token::Operator(op) => {
130                if VALUE_OPS.contains(&op.as_str()) {
131                    if value_stack.len() < 2 {return Err(format!("Invalid predicate string"))}
132
133                    let v2 = value_stack.pop().unwrap();
134                    let v1 = value_stack.pop().unwrap();
135
136                    match op.as_str() {
137                        //"==", ">", "<", ">=", "<="
138                        "==" => predicate_stack.push(Predicate::Equal(v1, v2)),
139                        ">" => predicate_stack.push(Predicate::GreaterThan(v1, v2)),
140                        "<" => predicate_stack.push(Predicate::LowerThan(v1, v2)),
141                        ">=" => predicate_stack.push(Predicate::GreaterEqual(v1, v2)),
142                        "<=" => predicate_stack.push(Predicate::LowerEqual(v1, v2)),
143                        _ => return Err(format!("Invalid predicate string"))
144                    }
145                }
146
147                else if PREDICATE_OPS.contains(&op.as_str()) {
148                    if predicate_stack.len() < 2 {return Err(format!("Invalid predicate string"))}
149
150                    let p2 = predicate_stack.pop().unwrap();
151                    let p1 = predicate_stack.pop().unwrap();
152
153                    match op.as_str() {
154                        //"||", "&&", "!"
155                        "||" => predicate_stack.push(Predicate::Or(Box::new(p1), Box::new(p2))),
156                        "&&" => predicate_stack.push(Predicate::And(Box::new(p1), Box::new(p2))),
157                        "!" => predicate_stack.push(Predicate::Not(Box::new(p1))),
158                        _ => return Err(format!("Invalid predicate string"))
159                    }
160                }
161            },
162
163
164            Token::Separator(_) => panic!("Unexpected separator"),
165        }
166
167    }
168
169    // At this point there should be only one predicate in the stack
170    match predicate_stack.pop() {
171        Some(p) => Ok(p),
172        None => Err(format!("Invalid predicate string"))
173    }
174}
predicatechecker/parser.rs

predicatechecker/
parser.rs
