expr_parser/
evaluate.rs

1use crate::{
2    expression::{Expression, ExpressionKind},
3    Span,
4};
5
6pub trait Evaluator<Idx, B, U, T> {
7    type Value;
8    type Error;
9
10    fn evaluate_binary_operator(
11        &mut self,
12        span: Span<Idx>,
13        operator: B,
14        lhs: Self::Value,
15        rhs: Self::Value,
16    ) -> Result<Self::Value, Self::Error>;
17
18    fn evaluate_unary_operator(
19        &mut self,
20        span: Span<Idx>,
21        operator: U,
22        argument: Self::Value,
23    ) -> Result<Self::Value, Self::Error>;
24
25    fn evaluate_term(&mut self, span: Span<Idx>, term: T) -> Result<Self::Value, Self::Error>;
26
27    fn evaluate<I>(&mut self, input: I) -> Result<Self::Value, Self::Error>
28    where
29        I: IntoIterator<Item = Expression<Idx, B, U, T>>,
30    {
31        evaluate(self, input)
32    }
33}
34
35/// Evaluate the input expression queue using the provided `Evaluator`.
36///
37/// # Panics
38///
39/// This function will panic if it encounters an operator and the stack does not contain enough
40/// values for the operator's arguments. It will also panic if the input is empty.
41pub fn evaluate<E, I, Idx, B, U, T>(evaluator: &mut E, input: I) -> Result<E::Value, E::Error>
42where
43    E: Evaluator<Idx, B, U, T> + ?Sized,
44    I: IntoIterator<Item = Expression<Idx, B, U, T>>,
45{
46    const STACK_EMPTY: &str = "tried to pop from empty stack";
47
48    let mut stack = Vec::new();
49    for expr in input {
50        match expr.kind {
51            ExpressionKind::BinaryOperator(op) => {
52                let rhs = stack.pop().expect(STACK_EMPTY);
53                let lhs = stack.pop().expect(STACK_EMPTY);
54                stack.push(evaluator.evaluate_binary_operator(expr.span, op, lhs, rhs)?);
55            }
56            ExpressionKind::UnaryOperator(op) => {
57                let argument = stack.pop().expect(STACK_EMPTY);
58                stack.push(evaluator.evaluate_unary_operator(expr.span, op, argument)?);
59            }
60            ExpressionKind::Term(term) => {
61                stack.push(evaluator.evaluate_term(expr.span, term)?);
62            }
63        }
64    }
65
66    Ok(stack.pop().expect(STACK_EMPTY))
67}
68
69/// An `Evaluator` whose `Value` type is the same as its `Term` type, and whose operators
70/// are pure functions on that type that return `Result<Term, E>`
71pub struct PureEvaluator;
72
73impl<Idx, B, U, T, E> Evaluator<Idx, B, U, T> for PureEvaluator
74where
75    B: FnOnce(T, T) -> Result<T, E>,
76    U: FnOnce(T) -> Result<T, E>,
77{
78    type Value = T;
79    type Error = E;
80
81    fn evaluate_binary_operator(
82        &mut self,
83        _span: Span<Idx>,
84        operator: B,
85        lhs: Self::Value,
86        rhs: Self::Value,
87    ) -> Result<Self::Value, Self::Error> {
88        operator(lhs, rhs)
89    }
90
91    fn evaluate_unary_operator(
92        &mut self,
93        _span: Span<Idx>,
94        operator: U,
95        argument: Self::Value,
96    ) -> Result<Self::Value, Self::Error> {
97        operator(argument)
98    }
99
100    fn evaluate_term(&mut self, _span: Span<Idx>, term: T) -> Result<Self::Value, Self::Error> {
101        Ok(term)
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    use test_case::test_case;
108
109    use super::{Evaluator, PureEvaluator};
110    use crate::{
111        expression::{Expression, ExpressionKind},
112        Span,
113    };
114
115    #[derive(Debug, Eq, PartialEq)]
116    enum Error {
117        DivideByZero,
118    }
119
120    fn add(lhs: Term, rhs: Term) -> Result<Term, Error> {
121        Ok(lhs + rhs)
122    }
123
124    fn sub(lhs: Term, rhs: Term) -> Result<Term, Error> {
125        Ok(lhs - rhs)
126    }
127
128    fn mul(lhs: Term, rhs: Term) -> Result<Term, Error> {
129        Ok(lhs * rhs)
130    }
131
132    fn div(lhs: Term, rhs: Term) -> Result<Term, Error> {
133        if rhs == 0 {
134            Err(Error::DivideByZero)
135        } else {
136            Ok(lhs / rhs)
137        }
138    }
139
140    fn neg(argument: Term) -> Result<Term, Error> {
141        Ok(-argument)
142    }
143
144    type Term = i64;
145    type BinaryOperator = fn(Term, Term) -> Result<Term, Error>;
146    type UnaryOperator = fn(Term) -> Result<Term, Error>;
147
148    #[test_case([
149        ExpressionKind::Term(1), ExpressionKind::Term(1), ExpressionKind::BinaryOperator(add),
150    ], Ok(2); "basic")]
151    #[test_case([
152        ExpressionKind::Term(1), ExpressionKind::Term(1), ExpressionKind::BinaryOperator(add),
153        ExpressionKind::UnaryOperator(neg),
154        ExpressionKind::Term(3), ExpressionKind::BinaryOperator(mul),
155        ExpressionKind::Term(2), ExpressionKind::BinaryOperator(div),
156    ], Ok(-3); "basic 2")]
157    #[test_case([
158        ExpressionKind::Term(1), ExpressionKind::Term(1), ExpressionKind::BinaryOperator(add),
159        ExpressionKind::UnaryOperator(neg),
160        ExpressionKind::Term(3), ExpressionKind::BinaryOperator(mul),
161        ExpressionKind::Term(1), ExpressionKind::Term(1), ExpressionKind::BinaryOperator(sub),
162        ExpressionKind::BinaryOperator(div),
163    ], Err(Error::DivideByZero); "division by zero")]
164    fn evaluate_expression<const N: usize>(
165        expression: [ExpressionKind<BinaryOperator, UnaryOperator, Term>; N],
166        result: Result<Term, Error>,
167    ) {
168        const EMPTY_SPAN: Span<usize> = Span { start: 0, end: 0 };
169        let actual = PureEvaluator.evaluate(expression.into_iter().map(|kind| Expression {
170            kind,
171            span: EMPTY_SPAN,
172        }));
173
174        assert_eq!(actual, result);
175    }
176}
expr_parser/evaluate.rs

expr_parser/
evaluate.rs
