1 use crate::error::CalcError;
2 use crate::token::*;
3 use crate::value::{Value, IR};
4 use decimal::d128;
5 use rand::Rng;
6
7 const RECURSION_LIMIT: usize = 10;
8
9 /// Represents an environment for evaluating a mathematical expression
10 pub trait Environment {
11 /// Look up the arity of an atom:
12 /// - Variables have an implicit arity of zero
13 /// - This library currently does not support varadic functions
14 /// - If a symbol is not defined, return None
arity(&self, atom: &str) -> Option<usize>15 fn arity(&self, atom: &str) -> Option<usize>;
16
17 /// Resolve an atom given the name of the atom and some number of
18 /// arguments
19 /// Precondition: `args.len() == self.arity(atom)`
resolve( &mut self, atom: &str, args: &[Value], ) -> Result<Value, CalcError>20 fn resolve(
21 &mut self,
22 atom: &str,
23 args: &[Value],
24 ) -> Result<Value, CalcError>;
25
add_recursion_level(&mut self)26 fn add_recursion_level(&mut self);
subtract_recursion_level(&mut self)27 fn subtract_recursion_level(&mut self);
get_recursion_level(&self) -> usize28 fn get_recursion_level(&self) -> usize;
29
ans(&self) -> &Option<Value>30 fn ans(&self) -> &Option<Value>;
31 }
32
d_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError> where E: Environment,33 fn d_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError>
34 where
35 E: Environment,
36 {
37 if !token_list.is_empty() && token_list[0] == Token::BitWiseNot {
38 let mut e = d_expr(&token_list[1..], env)?;
39 e.value = (!e.value)?;
40 e.tokens += 1;
41 return Ok(e);
42 }
43
44 let mut e1 = e_expr(token_list, env)?;
45 let mut index = e1.tokens;
46
47 while index < token_list.len() {
48 match token_list[index] {
49 Token::BitWiseAnd => {
50 let e2 = e_expr(&token_list[index + 1..], env)?;
51 e1.value = (e1.value & e2.value)?;
52 e1.tokens += e2.tokens + 1;
53 }
54 Token::BitWiseOr => {
55 let e2 = e_expr(&token_list[index + 1..], env)?;
56 e1.value = (e1.value | e2.value)?;
57 e1.tokens += e2.tokens + 1;
58 }
59 Token::BitWiseXor => {
60 let e2 = e_expr(&token_list[index + 1..], env)?;
61 e1.value = (e1.value ^ e2.value)?;
62 e1.tokens += e2.tokens + 1;
63 }
64 Token::BitWiseLShift => {
65 let e2 = e_expr(&token_list[index + 1..], env)?;
66 e1.value = (e1.value << e2.value)?;
67 e1.tokens += e2.tokens + 1;
68 }
69 Token::BitWiseRShift => {
70 let e2 = e_expr(&token_list[index + 1..], env)?;
71 e1.value = (e1.value >> e2.value)?;
72 e1.tokens += e2.tokens + 1;
73 }
74 Token::Number(ref n) => {
75 return Err(CalcError::UnexpectedToken(
76 n.to_string(),
77 "operator",
78 ));
79 }
80 _ => break,
81 };
82 index = e1.tokens;
83 }
84 Ok(e1)
85 }
86 // Addition and subtraction
e_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError> where E: Environment,87 fn e_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError>
88 where
89 E: Environment,
90 {
91 let mut t1 = t_expr(token_list, env)?;
92 let mut index = t1.tokens;
93
94 while index < token_list.len() {
95 match token_list[index] {
96 Token::Plus => {
97 let t2 = t_expr(&token_list[index + 1..], env)?;
98 t1.value = (t1.value + t2.value)?;
99 t1.tokens += t2.tokens + 1;
100 }
101 Token::Minus => {
102 let t2 = t_expr(&token_list[index + 1..], env)?;
103 t1.value = (t1.value - t2.value)?;
104 t1.tokens += t2.tokens + 1;
105 }
106 Token::Number(ref n) => {
107 return Err(CalcError::UnexpectedToken(
108 n.to_string(),
109 "operator",
110 ))
111 }
112 _ => break,
113 };
114 index = t1.tokens;
115 }
116 Ok(t1)
117 }
118
119 // Multiplication and division
t_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError> where E: Environment,120 fn t_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError>
121 where
122 E: Environment,
123 {
124 let mut f1 = f_expr(token_list, env)?;
125 let mut index = f1.tokens;
126
127 while index < token_list.len() {
128 match token_list[index] {
129 Token::Multiply => {
130 let f2 = f_expr(&token_list[index + 1..], env)?;
131 f1.value = (f1.value * f2.value)?;
132 f1.tokens += f2.tokens + 1;
133 }
134 Token::Divide => {
135 let f2 = f_expr(&token_list[index + 1..], env)?;
136 f1.value = (f1.value / f2.value)?;
137 f1.tokens += f2.tokens + 1;
138 }
139 Token::Modulo => {
140 let f2 = f_expr(&token_list[index + 1..], env)?;
141 f1.value = (f1.value % f2.value)?;
142 f1.tokens += f2.tokens + 1;
143 }
144 Token::Dice => {
145 let f2 = f_expr(&token_list[index + 1..], env)?;
146 let dice_rolls: i32 = f1.value.as_float()?.into();
147 let dice_max: i32 = f2.value.as_float()?.into();
148 if dice_rolls < 1 || dice_max < 1 {
149 return Err(CalcError::ImpossibleDice);
150 }
151 let mut dice_result = 0;
152 let mut rng = rand::thread_rng();
153 for _i in 0..dice_rolls {
154 dice_result += rng.gen_range(1, dice_max + 1);
155 }
156 f1.value = Value::dec(dice_result);
157 f1.tokens += f2.tokens + 1;
158 }
159 Token::Number(ref n) => {
160 return Err(CalcError::UnexpectedToken(
161 n.to_string(),
162 "operator",
163 ));
164 }
165 _ => break,
166 }
167 index = f1.tokens;
168 }
169 Ok(f1)
170 }
171
172 // Exponentiation
f_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError> where E: Environment,173 fn f_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError>
174 where
175 E: Environment,
176 {
177 let mut g1 = g_expr(token_list, env)?; // was g1
178 let mut index = g1.tokens;
179 let token_len = token_list.len();
180 while index < token_len {
181 match token_list[index] {
182 Token::Exponent => {
183 let f = f_expr(&token_list[index + 1..], env)?;
184 g1.value = g1.value.pow(f.value)?;
185 g1.tokens += f.tokens + 1;
186 }
187 Token::Square => {
188 g1.value = (g1.value.clone() * g1.value)?;
189 g1.tokens += 1;
190 }
191 Token::Cube => {
192 g1.value = ((g1.value.clone() * g1.value.clone())? * g1.value)?;
193 g1.tokens += 1;
194 }
195 Token::Number(ref n) => {
196 return Err(CalcError::UnexpectedToken(
197 n.to_string(),
198 "operator",
199 ));
200 }
201 _ => break,
202 }
203 index = g1.tokens;
204 }
205 Ok(g1)
206 }
207
208 // Numbers, parenthesized expressions, and atoms
g_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError> where E: Environment,209 fn g_expr<E>(token_list: &[Token], env: &mut E) -> Result<IR, CalcError>
210 where
211 E: Environment,
212 {
213 if !token_list.is_empty() {
214 match token_list[0] {
215 Token::Ans => match env.ans() {
216 Some(v) => Ok(IR::new(v.clone(), 1)),
217 None => Err(CalcError::MissingAns),
218 },
219 Token::Number(ref n) => Ok(IR::new(n.clone(), 1)),
220 Token::Atom(ref s) => {
221 if let Some(nargs) = env.arity(s) {
222 let mut args: Vec<Value> = Vec::new();
223 let mut start = 1;
224 for _ in 0..nargs {
225 let ir = g_expr(&token_list[start..], env)?;
226 start += ir.tokens;
227 args.push(ir.value);
228 }
229 let res = env.resolve(s, &args);
230 Ok(IR::new(res?, start))
231 } else {
232 Err(CalcError::UnknownAtom(s.clone()))
233 }
234 }
235 Token::Minus => {
236 if token_list.len() >= 2 {
237 if let Token::Number(ref n) = token_list[1] {
238 Ok(IR::new(-n.clone(), 2))
239 } else {
240 let mut ir = d_expr(&token_list[1..], env)?;
241 ir.value = -ir.value;
242 ir.tokens += 1;
243 Ok(ir)
244 }
245 } else {
246 Err(CalcError::UnexpectedEndOfInput)
247 }
248 }
249 Token::OpenParen => {
250 env.add_recursion_level();
251 if env.get_recursion_level() > RECURSION_LIMIT {
252 Err(CalcError::RecursionLimitReached)?
253 }
254 let mut ir = d_expr(&token_list[1..], env)?;
255 let close_paren = ir.tokens + 1;
256 if close_paren < token_list.len() {
257 match token_list[close_paren] {
258 Token::CloseParen => {
259 env.subtract_recursion_level();
260 ir.tokens = close_paren + 1;
261 Ok(ir)
262 }
263 _ => Err(CalcError::UnexpectedToken(
264 token_list[close_paren].to_string(),
265 ")",
266 )),
267 }
268 } else {
269 Err(CalcError::UnmatchedParenthesis)
270 }
271 }
272 _ => Err(CalcError::UnexpectedToken(
273 token_list[0].to_string(),
274 "number",
275 )),
276 }
277 } else {
278 Err(CalcError::UnexpectedEndOfInput)
279 }
280 }
281
282 pub struct DefaultEnvironment {
283 recursion_level: usize,
284 ans: Option<Value>,
285 }
286
287 impl DefaultEnvironment {
new() -> DefaultEnvironment288 pub fn new() -> DefaultEnvironment {
289 DefaultEnvironment {
290 recursion_level: 0,
291 ans: None,
292 }
293 }
294
with_ans(ans: Option<Value>) -> DefaultEnvironment295 pub fn with_ans(ans: Option<Value>) -> DefaultEnvironment {
296 DefaultEnvironment {
297 recursion_level: 0,
298 ans,
299 }
300 }
301 }
302
303 impl Environment for DefaultEnvironment {
arity(&self, atom: &str) -> Option<usize>304 fn arity(&self, atom: &str) -> Option<usize> {
305 match atom {
306 "pi" | "tau" => Some(0),
307 "log" => Some(1),
308 _ => None,
309 }
310 }
311
resolve( &mut self, atom: &str, args: &[Value], ) -> Result<Value, CalcError>312 fn resolve(
313 &mut self,
314 atom: &str,
315 args: &[Value],
316 ) -> Result<Value, CalcError> {
317 match atom {
318 "pi" => {
319 Ok(Value::Float(d128!(3.1415926535897932384626433832795028)))
320 }
321 "tau" => Ok(Value::Float(
322 d128!(3.1415926535897932384626433832795028) * d128!(2.0),
323 )),
324 "log" => Ok(Value::Float(args[0].as_float()?.log10())),
325 // "sin" => Ok(Value::Float(args[0].as_float().sin())),
326 // "cos" => Ok(Value::Float(args[0].as_float().cos())),
327 // "tan" => Ok(Value::Float(args[0].as_float().tan())),
328 _ => Err(CalcError::UnknownAtom(atom.to_owned())),
329 }
330 }
331
get_recursion_level(&self) -> usize332 fn get_recursion_level(&self) -> usize {
333 self.recursion_level
334 }
335
add_recursion_level(&mut self)336 fn add_recursion_level(&mut self) {
337 self.recursion_level += 1;
338 }
subtract_recursion_level(&mut self)339 fn subtract_recursion_level(&mut self) {
340 self.recursion_level -= 1;
341 }
342
ans(&self) -> &Option<Value>343 fn ans(&self) -> &Option<Value> {
344 &self.ans
345 }
346 }
347
parse<E>(tokens: &[Token], env: &mut E) -> Result<Value, CalcError> where E: Environment,348 pub fn parse<E>(tokens: &[Token], env: &mut E) -> Result<Value, CalcError>
349 where
350 E: Environment,
351 {
352 d_expr(tokens, env).map(|answer| answer.value)
353 }
354
355 #[cfg(test)]
356 mod tests {
357
358 use super::*;
359
360 #[test]
unary_minus()361 fn unary_minus() {
362 let expr = [
363 Token::Minus,
364 Token::Number(Value::dec(1)),
365 Token::Plus,
366 Token::Number(Value::dec(1)),
367 ];
368 let expected = Value::dec(0);
369 let mut env = DefaultEnvironment::new();
370 assert_eq!(super::parse(&expr, &mut env), Ok(expected));
371 }
372
373 #[test]
dice_parse()374 fn dice_parse() {
375 let expr = [
376 Token::Number(Value::dec(3)),
377 Token::Dice,
378 Token::Number(Value::dec(6)),
379 ];
380 let mut env = DefaultEnvironment::new();
381 let out = super::parse(&expr, &mut env);
382 let out_float = out.unwrap().as_float().unwrap();
383 assert!(out_float >= d128!(3.0) && out_float <= d128!(18.0));
384 }
385
386 #[test]
ans_calculation()387 fn ans_calculation() {
388 let expr = [Token::Ans, Token::Multiply, Token::Number(Value::dec(3))];
389 let expected = Value::dec(12);
390 let mut env = DefaultEnvironment::with_ans(Some(Value::dec(4)));
391 assert_eq!(super::parse(&expr, &mut env), Ok(expected));
392 }
393
394 #[test]
function_binding()395 fn function_binding() {
396 let expr = [
397 Token::Atom("log".into()),
398 Token::Number(Value::Float(d128!(4.0))),
399 Token::Divide,
400 Token::Atom("log".into()),
401 Token::Number(Value::Float(d128!(2.0))),
402 ];
403 let expected = Value::Float(d128!(2.0));
404 let mut env = DefaultEnvironment::new();
405 assert_eq!(super::parse(&expr, &mut env), Ok(expected));
406 }
407 }
408