dhttp_access/expr/
eval.rs

1use std::fmt::Display;
2
3use crate::expr::exprs::Part;
4
5pub trait Evaluable<State: ?Sized> {
6    type Value;
7    fn eval(&self, state: &State) -> Self::Value;
8}
9
10pub trait BeOperator<Value> {
11    fn operand(&self) -> usize;
12
13    fn operate(&self, values: &mut dyn Iterator<Item = Value>) -> Option<Value>;
14
15    /// Dyn-compatible?
16    fn short_circuit(&self, values: &mut dyn Iterator<Item = &Value>) -> Option<(Value, usize)> {
17        _ = values;
18        None
19    }
20}
21
22#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
23pub enum BooleanOperator {
24    And,
25    Or,
26    Not,
27}
28
29impl Display for BooleanOperator {
30    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31        match self {
32            BooleanOperator::And => write!(f, "AND"),
33            BooleanOperator::Or => write!(f, "OR"),
34            BooleanOperator::Not => write!(f, "NOT"),
35        }
36    }
37}
38
39impl BeOperator<bool> for BooleanOperator {
40    fn operand(&self) -> usize {
41        match self {
42            BooleanOperator::And => 2,
43            BooleanOperator::Or => 2,
44            BooleanOperator::Not => 1,
45        }
46    }
47
48    fn operate(&self, values: &mut dyn Iterator<Item = bool>) -> Option<bool> {
49        Some(match self {
50            BooleanOperator::And => values.next()? && values.next()?,
51            BooleanOperator::Or => values.next()? || values.next()?,
52            BooleanOperator::Not => !values.next()?,
53        })
54    }
55
56    fn short_circuit(&self, values: &mut dyn Iterator<Item = &bool>) -> Option<(bool, usize)> {
57        match self {
58            BooleanOperator::And => (!values.next()?).then_some((false, 1)),
59            BooleanOperator::Or => values.next()?.then_some((true, 1)),
60            BooleanOperator::Not => None,
61        }
62    }
63}
64
65impl<E: Clone> BeOperator<Result<bool, E>> for BooleanOperator {
66    fn operand(&self) -> usize {
67        <Self as BeOperator<bool>>::operand(self)
68    }
69
70    fn operate(
71        &self,
72        values: &mut dyn Iterator<Item = Result<bool, E>>,
73    ) -> Option<Result<bool, E>> {
74        Some(match self {
75            BooleanOperator::And => {
76                let l = values.next()?;
77                let r = values.next()?;
78                r.and_then(|r| l.map(|l| l && r))
79            }
80            BooleanOperator::Or => {
81                let l = values.next()?;
82                let r = values.next()?;
83                r.and_then(|r| l.map(|l| l || r))
84            }
85            BooleanOperator::Not => {
86                let v = values.next()?;
87                v.map(|v| !v)
88            }
89        })
90    }
91
92    fn short_circuit(
93        &self,
94        values: &mut dyn Iterator<Item = &Result<bool, E>>,
95    ) -> Option<(Result<bool, E>, usize)> {
96        match self {
97            BooleanOperator::And => match values.next()? {
98                Ok(false) => Some((Ok(false), 1)),
99                Err(e) => Some((Err(e.clone()), 1)),
100                Ok(true) => None,
101            },
102            BooleanOperator::Or => match values.next()? {
103                Ok(true) => Some((Ok(true), 1)),
104                Err(e) => Some((Err(e.clone()), 1)),
105                Ok(false) => None,
106            },
107            BooleanOperator::Not => None,
108        }
109    }
110}
111
112impl BeOperator<()> for BooleanOperator {
113    fn operand(&self) -> usize {
114        <Self as BeOperator<bool>>::operand(self)
115    }
116
117    fn operate(&self, values: &mut dyn Iterator<Item = ()>) -> Option<()> {
118        for _ in 0..(<Self as BeOperator<()>>::operand(self)) {
119            values.next()?;
120        }
121        Some(())
122    }
123}
124
125#[derive(Debug, Clone, Copy, PartialEq, Eq, snafu::Snafu)]
126pub enum EvalPolishError {
127    #[snafu(display("polish notation expression is incomplete"))]
128    IncompleteExpression,
129    #[snafu(display("polish notation expression contains extra operands"))]
130    ExtraOperands,
131    #[snafu(display("polish notation operator is missing operands"))]
132    MissingOperands,
133}
134
135pub struct VM<Operator, Value> {
136    short_circuit: usize,
137    ops: Vec<Operator>,
138    values: Vec<Value>,
139}
140
141impl<Operator, Value> Default for VM<Operator, Value> {
142    fn default() -> Self {
143        Self {
144            short_circuit: Default::default(),
145            ops: Default::default(),
146            values: Default::default(),
147        }
148    }
149}
150
151impl<Operator: BeOperator<Value>, Value> VM<Operator, Value> {
152    pub fn new() -> Self {
153        Self::default()
154    }
155
156    fn try_eval(&mut self) -> Result<(), EvalPolishError> {
157        while let Some(op) = self.ops.last() {
158            if self.values.len() >= op.operand() {
159                let value = op
160                    .operate(&mut self.values.drain(self.values.len() - op.operand()..))
161                    .ok_or(EvalPolishError::MissingOperands)?;
162                self.values.push(value);
163                self.ops.pop();
164            } else if let Some((value, consumed)) = op.short_circuit(&mut self.values.iter().rev())
165            {
166                self.values.truncate(self.values.len() - consumed);
167                self.values.push(value);
168                self.short_circuit += op.operand() - consumed;
169                self.ops.pop();
170            } else {
171                break;
172            }
173        }
174        Ok(())
175    }
176
177    pub fn try_run(
178        mut self,
179        parts: impl IntoIterator<Item = Part<Operator, Value>>,
180    ) -> Result<Value, EvalPolishError> {
181        for part in parts {
182            match (part, self.short_circuit) {
183                (Part::Operator(opeartor), 0) => {
184                    self.ops.push(opeartor);
185                }
186                (Part::Expr(value), 0) => {
187                    self.values.push(value);
188                    self.try_eval()?;
189                }
190                (Part::Operator(opeartor), _n) => self.short_circuit += opeartor.operand() - 1,
191                (Part::Expr(_value), _n) => self.short_circuit -= 1,
192            }
193        }
194        if !self.ops.is_empty() || self.short_circuit != 0 || self.values.is_empty() {
195            return Err(EvalPolishError::IncompleteExpression);
196        }
197        if self.values.len() != 1 {
198            return Err(EvalPolishError::ExtraOperands);
199        }
200        self.values
201            .pop()
202            .ok_or(EvalPolishError::IncompleteExpression)
203    }
204}
205
206pub trait EvalRuleError<Action> {
207    fn fallback(&self, matched_action: Action) -> Option<Action>;
208}
209
210#[cfg(test)]
211mod tests {
212    use super::*;
213    use crate::expr::exprs::Part;
214
215    #[test]
216    fn boolean_operator_missing_operands_returns_none() {
217        let mut values = std::iter::empty::<bool>();
218
219        assert_eq!(BooleanOperator::And.operate(&mut values), None);
220    }
221
222    #[test]
223    fn vm_reports_incomplete_polish_notation() {
224        let result =
225            VM::<BooleanOperator, bool>::new().try_run([Part::Operator(BooleanOperator::And)]);
226
227        assert!(matches!(result, Err(EvalPolishError::IncompleteExpression)));
228    }
229
230    #[test]
231    fn vm_reports_extra_operands() {
232        let result =
233            VM::<BooleanOperator, bool>::new().try_run([Part::Expr(true), Part::Expr(false)]);
234
235        assert!(matches!(result, Err(EvalPolishError::ExtraOperands)));
236    }
237}
dhttp_access/expr/eval.rs

dhttp_access/expr/
eval.rs
