1 /*
2 * TINYEXPR - Tiny recursive descent parser and evaluation engine in C
3 *
4 * Copyright (c) 2015-2018 Lewis Van Winkle
5 *
6 * http://CodePlea.com
7 *
8 * This software is provided 'as-is', without any express or implied
9 * warranty. In no event will the authors be held liable for any damages
10 * arising from the use of this software.
11 *
12 * Permission is granted to anyone to use this software for any purpose,
13 * including commercial applications, and to alter it and redistribute it
14 * freely, subject to the following restrictions:
15 *
16 * 1. The origin of this software must not be misrepresented; you must not
17 * claim that you wrote the original software. If you use this software
18 * in a product, an acknowledgement in the product documentation would be
19 * appreciated but is not required.
20 * 2. Altered source versions must be plainly marked as such, and must not be
21 * misrepresented as being the original software.
22 * 3. This notice may not be removed or altered from any source distribution.
23 */
24
25 /* COMPILE TIME OPTIONS */
26
27 /* Exponentiation associativity:
28 For a^b^c = (a^b)^c and -a^b = (-a)^b do nothing.
29 For a^b^c = a^(b^c) and -a^b = -(a^b) uncomment the next line.*/
30 /* #define TE_POW_FROM_RIGHT */
31
32 /* Logarithms
33 For log = base 10 log do nothing
34 For log = natural log uncomment the next line. */
35 /* #define TE_NAT_LOG */
36
37 #include "tinyexpr.h"
38 #include <stdlib.h>
39 #include <math.h>
40 #include <string.h>
41 #include <stdio.h>
42 #include <limits.h>
43
44 #ifndef NAN
45 #define NAN (0.0/0.0)
46 #endif
47
48 #ifndef INFINITY
49 #define INFINITY (1.0/0.0)
50 #endif
51
52
53 typedef double (*te_fun2)(double, double);
54
55 enum {
56 TOK_NULL = TE_CLOSURE7+1, TOK_ERROR, TOK_END, TOK_SEP,
57 TOK_OPEN, TOK_CLOSE, TOK_NUMBER, TOK_VARIABLE, TOK_INFIX
58 };
59
60
61 enum {TE_CONSTANT = 1};
62
63
64 typedef struct state {
65 const char *start;
66 const char *next;
67 int type;
68 union {double value; const double *bound; const void *function;};
69 void *context;
70
71 const te_variable *lookup;
72 int lookup_len;
73 } state;
74
75
76 #define TYPE_MASK(TYPE) ((TYPE)&0x0000001F)
77
78 #define IS_PURE(TYPE) (((TYPE) & TE_FLAG_PURE) != 0)
79 #define IS_FUNCTION(TYPE) (((TYPE) & TE_FUNCTION0) != 0)
80 #define IS_CLOSURE(TYPE) (((TYPE) & TE_CLOSURE0) != 0)
81 #define ARITY(TYPE) ( ((TYPE) & (TE_FUNCTION0 | TE_CLOSURE0)) ? ((TYPE) & 0x00000007) : 0 )
82 #define NEW_EXPR(type, ...) new_expr((type), (const te_expr*[]){__VA_ARGS__})
83
new_expr(const int type,const te_expr * parameters[])84 static te_expr *new_expr(const int type, const te_expr *parameters[]) {
85 const int arity = ARITY(type);
86 const int psize = sizeof(void*) * arity;
87 const int size = (sizeof(te_expr) - sizeof(void*)) + psize + (IS_CLOSURE(type) ? sizeof(void*) : 0);
88 te_expr *ret = malloc(size);
89 memset(ret, 0, size);
90 if (arity && parameters) {
91 memcpy(ret->parameters, parameters, psize);
92 }
93 ret->type = type;
94 ret->bound = 0;
95 return ret;
96 }
97
98
te_free_parameters(te_expr * n)99 void te_free_parameters(te_expr *n) {
100 if (!n) return;
101 switch (TYPE_MASK(n->type)) {
102 case TE_FUNCTION7: case TE_CLOSURE7: te_free(n->parameters[6]); /* Falls through. */
103 case TE_FUNCTION6: case TE_CLOSURE6: te_free(n->parameters[5]); /* Falls through. */
104 case TE_FUNCTION5: case TE_CLOSURE5: te_free(n->parameters[4]); /* Falls through. */
105 case TE_FUNCTION4: case TE_CLOSURE4: te_free(n->parameters[3]); /* Falls through. */
106 case TE_FUNCTION3: case TE_CLOSURE3: te_free(n->parameters[2]); /* Falls through. */
107 case TE_FUNCTION2: case TE_CLOSURE2: te_free(n->parameters[1]); /* Falls through. */
108 case TE_FUNCTION1: case TE_CLOSURE1: te_free(n->parameters[0]);
109 }
110 }
111
112
te_free(te_expr * n)113 void te_free(te_expr *n) {
114 if (!n) return;
115 te_free_parameters(n);
116 free(n);
117 }
118
119
pi(void)120 static double pi(void) {return 3.14159265358979323846;}
e(void)121 static double e(void) {return 2.71828182845904523536;}
fac(double a)122 static double fac(double a) {/* simplest version of fac */
123 if (a < 0.0)
124 return NAN;
125 if (a > UINT_MAX)
126 return INFINITY;
127 unsigned int ua = (unsigned int)(a);
128 unsigned long int result = 1, i;
129 for (i = 1; i <= ua; i++) {
130 if (i > ULONG_MAX / result)
131 return INFINITY;
132 result *= i;
133 }
134 return (double)result;
135 }
ncr(double n,double r)136 static double ncr(double n, double r) {
137 if (n < 0.0 || r < 0.0 || n < r) return NAN;
138 if (n > UINT_MAX || r > UINT_MAX) return INFINITY;
139 unsigned long int un = (unsigned int)(n), ur = (unsigned int)(r), i;
140 unsigned long int result = 1;
141 if (ur > un / 2) ur = un - ur;
142 for (i = 1; i <= ur; i++) {
143 if (result > ULONG_MAX / (un - ur + i))
144 return INFINITY;
145 result *= un - ur + i;
146 result /= i;
147 }
148 return result;
149 }
npr(double n,double r)150 static double npr(double n, double r) {return ncr(n, r) * fac(r);}
151
152 static const te_variable functions[] = {
153 /* must be in alphabetical order */
154 {"abs", fabs, TE_FUNCTION1 | TE_FLAG_PURE, 0},
155 {"acos", acos, TE_FUNCTION1 | TE_FLAG_PURE, 0},
156 {"asin", asin, TE_FUNCTION1 | TE_FLAG_PURE, 0},
157 {"atan", atan, TE_FUNCTION1 | TE_FLAG_PURE, 0},
158 {"atan2", atan2, TE_FUNCTION2 | TE_FLAG_PURE, 0},
159 {"ceil", ceil, TE_FUNCTION1 | TE_FLAG_PURE, 0},
160 {"cos", cos, TE_FUNCTION1 | TE_FLAG_PURE, 0},
161 {"cosh", cosh, TE_FUNCTION1 | TE_FLAG_PURE, 0},
162 {"e", e, TE_FUNCTION0 | TE_FLAG_PURE, 0},
163 {"exp", exp, TE_FUNCTION1 | TE_FLAG_PURE, 0},
164 {"fac", fac, TE_FUNCTION1 | TE_FLAG_PURE, 0},
165 {"floor", floor, TE_FUNCTION1 | TE_FLAG_PURE, 0},
166 {"ln", log, TE_FUNCTION1 | TE_FLAG_PURE, 0},
167 #ifdef TE_NAT_LOG
168 {"log", log, TE_FUNCTION1 | TE_FLAG_PURE, 0},
169 #else
170 {"log", log10, TE_FUNCTION1 | TE_FLAG_PURE, 0},
171 #endif
172 {"log10", log10, TE_FUNCTION1 | TE_FLAG_PURE, 0},
173 {"ncr", ncr, TE_FUNCTION2 | TE_FLAG_PURE, 0},
174 {"npr", npr, TE_FUNCTION2 | TE_FLAG_PURE, 0},
175 {"pi", pi, TE_FUNCTION0 | TE_FLAG_PURE, 0},
176 {"pow", pow, TE_FUNCTION2 | TE_FLAG_PURE, 0},
177 {"sin", sin, TE_FUNCTION1 | TE_FLAG_PURE, 0},
178 {"sinh", sinh, TE_FUNCTION1 | TE_FLAG_PURE, 0},
179 {"sqrt", sqrt, TE_FUNCTION1 | TE_FLAG_PURE, 0},
180 {"tan", tan, TE_FUNCTION1 | TE_FLAG_PURE, 0},
181 {"tanh", tanh, TE_FUNCTION1 | TE_FLAG_PURE, 0},
182 {0, 0, 0, 0}
183 };
184
find_builtin(const char * name,int len)185 static const te_variable *find_builtin(const char *name, int len) {
186 int imin = 0;
187 int imax = sizeof(functions) / sizeof(te_variable) - 2;
188
189 /*Binary search.*/
190 while (imax >= imin) {
191 const int i = (imin + ((imax-imin)/2));
192 int c = strncmp(name, functions[i].name, len);
193 if (!c) c = '\0' - functions[i].name[len];
194 if (c == 0) {
195 return functions + i;
196 } else if (c > 0) {
197 imin = i + 1;
198 } else {
199 imax = i - 1;
200 }
201 }
202
203 return 0;
204 }
205
find_lookup(const state * s,const char * name,int len)206 static const te_variable *find_lookup(const state *s, const char *name, int len) {
207 int iters;
208 const te_variable *var;
209 if (!s->lookup) return 0;
210
211 for (var = s->lookup, iters = s->lookup_len; iters; ++var, --iters) {
212 if (strncmp(name, var->name, len) == 0 && var->name[len] == '\0') {
213 return var;
214 }
215 }
216 return 0;
217 }
218
219
220
add(double a,double b)221 static double add(double a, double b) {return a + b;}
sub(double a,double b)222 static double sub(double a, double b) {return a - b;}
mul(double a,double b)223 static double mul(double a, double b) {return a * b;}
divide(double a,double b)224 static double divide(double a, double b) {return a / b;}
negate(double a)225 static double negate(double a) {return -a;}
comma(double a,double b)226 static double comma(double a, double b) {(void)a; return b;}
227
greater(double a,double b)228 static double greater(double a, double b) {return a > b;}
greater_eq(double a,double b)229 static double greater_eq(double a, double b) {return a >= b;}
lower(double a,double b)230 static double lower(double a, double b) {return a < b;}
lower_eq(double a,double b)231 static double lower_eq(double a, double b) {return a <= b;}
equal(double a,double b)232 static double equal(double a, double b) {return a == b;}
not_equal(double a,double b)233 static double not_equal(double a, double b) {return a != b;}
logical_and(double a,double b)234 static double logical_and(double a, double b) {return a != 0.0 && b != 0.0;}
logical_or(double a,double b)235 static double logical_or(double a, double b) {return a != 0.0 || b != 0.0;}
logical_not(double a)236 static double logical_not(double a) {return a == 0.0;}
logical_notnot(double a)237 static double logical_notnot(double a) {return a != 0.0;}
negate_logical_not(double a)238 static double negate_logical_not(double a) {return -(a == 0.0);}
negate_logical_notnot(double a)239 static double negate_logical_notnot(double a) {return -(a != 0.0);}
240
241
next_token(state * s)242 void next_token(state *s) {
243 s->type = TOK_NULL;
244
245 do {
246
247 if (!*s->next){
248 s->type = TOK_END;
249 return;
250 }
251
252 /* Try reading a number. */
253 if ((s->next[0] >= '0' && s->next[0] <= '9') || s->next[0] == '.') {
254 s->value = strtod(s->next, (char**)&s->next);
255 s->type = TOK_NUMBER;
256 } else {
257 /* Look for a variable or builtin function call. */
258 if (s->next[0] == '$' || (s->next[0] >= 'a' && s->next[0] <= 'z')) {
259 const char *start;
260 start = s->next;
261 if (s->next[0] == '$') s->next++;
262 while ((s->next[0] >= 'a' && s->next[0] <= 'z') || (s->next[0] >= '0' && s->next[0] <= '9') || (s->next[0] == '_')) s->next++;
263
264 const te_variable *var = find_lookup(s, start, s->next - start);
265 if (!var) var = find_builtin(start, s->next - start);
266
267 if (!var) {
268 s->type = TOK_ERROR;
269 } else {
270 switch(TYPE_MASK(var->type))
271 {
272 case TE_VARIABLE:
273 s->type = TOK_VARIABLE;
274 s->bound = var->address;
275 break;
276
277 case TE_CLOSURE0: case TE_CLOSURE1: case TE_CLOSURE2: case TE_CLOSURE3: /* Falls through. */
278 case TE_CLOSURE4: case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7: /* Falls through. */
279 s->context = var->context; /* Falls through. */
280
281 case TE_FUNCTION0: case TE_FUNCTION1: case TE_FUNCTION2: case TE_FUNCTION3: /* Falls through. */
282 case TE_FUNCTION4: case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7: /* Falls through. */
283 s->type = var->type;
284 s->function = var->address;
285 break;
286 }
287 }
288
289 } else {
290 /* Look for an operator or special character. */
291 switch (s->next++[0]) {
292 case '+': s->type = TOK_INFIX; s->function = add; break;
293 case '-': s->type = TOK_INFIX; s->function = sub; break;
294 case '*': s->type = TOK_INFIX; s->function = mul; break;
295 case '/': s->type = TOK_INFIX; s->function = divide; break;
296 case '^': s->type = TOK_INFIX; s->function = pow; break;
297 case '%': s->type = TOK_INFIX; s->function = fmod; break;
298 case '!':
299 if (s->next++[0] == '=') {
300 s->type = TOK_INFIX; s->function = not_equal;
301 } else {
302 s->next--;
303 s->type = TOK_INFIX; s->function = logical_not;
304 }
305 break;
306 case '=':
307 if (s->next++[0] == '=') {
308 s->type = TOK_INFIX; s->function = equal;
309 } else {
310 s->type = TOK_ERROR;
311 }
312 break;
313 case '<':
314 if (s->next++[0] == '=') {
315 s->type = TOK_INFIX; s->function = lower_eq;
316 } else {
317 s->next--;
318 s->type = TOK_INFIX; s->function = lower;
319 }
320 break;
321 case '>':
322 if (s->next++[0] == '=') {
323 s->type = TOK_INFIX; s->function = greater_eq;
324 } else {
325 s->next--;
326 s->type = TOK_INFIX; s->function = greater;
327 }
328 break;
329 case '&':
330 if (s->next++[0] == '&') {
331 s->type = TOK_INFIX; s->function = logical_and;
332 } else {
333 s->type = TOK_ERROR;
334 }
335 break;
336 case '|':
337 if (s->next++[0] == '|') {
338 s->type = TOK_INFIX; s->function = logical_or;
339 } else {
340 s->type = TOK_ERROR;
341 }
342 break;
343 case '(': s->type = TOK_OPEN; break;
344 case ')': s->type = TOK_CLOSE; break;
345 case ',': s->type = TOK_SEP; break;
346 case ' ': case '\t': case '\n': case '\r': break;
347 default: s->type = TOK_ERROR; break;
348 }
349 }
350 }
351 } while (s->type == TOK_NULL);
352 }
353
354
355 static te_expr *list(state *s);
356 static te_expr *expr(state *s);
357 static te_expr *power(state *s);
358
base(state * s)359 static te_expr *base(state *s) {
360 /* <base> = <constant> | <variable> | <function-0> {"(" ")"} | <function-1> <power> | <function-X> "(" <expr> {"," <expr>} ")" | "(" <list> ")" */
361 te_expr *ret;
362 int arity;
363
364 switch (TYPE_MASK(s->type)) {
365 case TOK_NUMBER:
366 ret = new_expr(TE_CONSTANT, 0);
367 ret->value = s->value;
368 next_token(s);
369 break;
370
371 case TOK_VARIABLE:
372 ret = new_expr(TE_VARIABLE, 0);
373 ret->bound = s->bound;
374 next_token(s);
375 break;
376
377 case TE_FUNCTION0:
378 case TE_CLOSURE0:
379 ret = new_expr(s->type, 0);
380 ret->function = s->function;
381 if (IS_CLOSURE(s->type)) ret->parameters[0] = s->context;
382 next_token(s);
383 if (s->type == TOK_OPEN) {
384 next_token(s);
385 if (s->type != TOK_CLOSE) {
386 s->type = TOK_ERROR;
387 } else {
388 next_token(s);
389 }
390 }
391 break;
392
393 case TE_FUNCTION1:
394 case TE_CLOSURE1:
395 ret = new_expr(s->type, 0);
396 ret->function = s->function;
397 if (IS_CLOSURE(s->type)) ret->parameters[1] = s->context;
398 next_token(s);
399 ret->parameters[0] = power(s);
400 break;
401
402 case TE_FUNCTION2: case TE_FUNCTION3: case TE_FUNCTION4:
403 case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7:
404 case TE_CLOSURE2: case TE_CLOSURE3: case TE_CLOSURE4:
405 case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7:
406 arity = ARITY(s->type);
407
408 ret = new_expr(s->type, 0);
409 ret->function = s->function;
410 if (IS_CLOSURE(s->type)) ret->parameters[arity] = s->context;
411 next_token(s);
412
413 if (s->type != TOK_OPEN) {
414 s->type = TOK_ERROR;
415 } else {
416 int i;
417 for(i = 0; i < arity; i++) {
418 next_token(s);
419 ret->parameters[i] = expr(s);
420 if(s->type != TOK_SEP) {
421 break;
422 }
423 }
424 if(s->type != TOK_CLOSE || i != arity - 1) {
425 s->type = TOK_ERROR;
426 } else {
427 next_token(s);
428 }
429 }
430
431 break;
432
433 case TOK_OPEN:
434 next_token(s);
435 ret = list(s);
436 if (s->type != TOK_CLOSE) {
437 s->type = TOK_ERROR;
438 } else {
439 next_token(s);
440 }
441 break;
442
443 default:
444 ret = new_expr(0, 0);
445 s->type = TOK_ERROR;
446 ret->value = NAN;
447 break;
448 }
449
450 return ret;
451 }
452
453
power(state * s)454 static te_expr *power(state *s) {
455 /* <power> = {("-" | "+" | "!")} <base> */
456 int sign = 1;
457 while (s->type == TOK_INFIX && (s->function == add || s->function == sub)) {
458 if (s->function == sub) sign = -sign;
459 next_token(s);
460 }
461
462 int logical = 0;
463 while (s->type == TOK_INFIX && (s->function == add || s->function == sub || s->function == logical_not)) {
464 if (s->function == logical_not) {
465 if (logical == 0) {
466 logical = -1;
467 } else {
468 logical = -logical;
469 }
470 }
471 next_token(s);
472 }
473
474 te_expr *ret;
475
476 if (sign == 1) {
477 if (logical == 0) {
478 ret = base(s);
479 } else if (logical == -1) {
480 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, base(s));
481 ret->function = logical_not;
482 } else {
483 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, base(s));
484 ret->function = logical_notnot;
485 }
486 } else {
487 if (logical == 0) {
488 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, base(s));
489 ret->function = negate;
490 } else if (logical == -1) {
491 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, base(s));
492 ret->function = negate_logical_not;
493 } else {
494 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, base(s));
495 ret->function = negate_logical_notnot;
496 }
497 }
498
499 return ret;
500 }
501
502 #ifdef TE_POW_FROM_RIGHT
factor(state * s)503 static te_expr *factor(state *s) {
504 /* <factor> = <power> {"^" <power>} */
505 te_expr *ret = power(s);
506
507 const void *left_function = NULL;
508 te_expr *insertion = 0;
509
510 if (ret->type == (TE_FUNCTION1 | TE_FLAG_PURE) &&
511 (ret->function == negate || ret->function == logical_not || ret->function == logical_notnot ||
512 ret->function == negate_logical_not || ret->function == negate_logical_notnot)) {
513 left_function = ret->function;
514 te_expr *se = ret->parameters[0];
515 free(ret);
516 ret = se;
517 }
518
519 while (s->type == TOK_INFIX && (s->function == pow)) {
520 te_fun2 t = (te_fun2)s->function;
521 next_token(s);
522
523 if (insertion) {
524 /* Make exponentiation go right-to-left. */
525 te_expr *insert = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, insertion->parameters[1], power(s));
526 insert->function = t;
527 insertion->parameters[1] = insert;
528 insertion = insert;
529 } else {
530 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, power(s));
531 ret->function = t;
532 insertion = ret;
533 }
534 }
535
536 if (left_function) {
537 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, ret);
538 ret->function = left_function;
539 }
540
541 return ret;
542 }
543 #else
factor(state * s)544 static te_expr *factor(state *s) {
545 /* <factor> = <power> {"^" <power>} */
546 te_expr *ret = power(s);
547
548 while (s->type == TOK_INFIX && (s->function == pow)) {
549 te_fun2 t = (te_fun2)s->function;
550 next_token(s);
551 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, power(s));
552 ret->function = t;
553 }
554
555 return ret;
556 }
557 #endif
558
559
560
term(state * s)561 static te_expr *term(state *s) {
562 /* <term> = <factor> {("*" | "/" | "%") <factor>} */
563 te_expr *ret = factor(s);
564
565 while (s->type == TOK_INFIX && (s->function == mul || s->function == divide || s->function == fmod)) {
566 te_fun2 t = (te_fun2)s->function;
567 next_token(s);
568 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, factor(s));
569 ret->function = t;
570 }
571
572 return ret;
573 }
574
575
sum_expr(state * s)576 static te_expr *sum_expr(state *s) {
577 /* <expr> = <term> {("+" | "-") <term>} */
578 te_expr *ret = term(s);
579
580 while (s->type == TOK_INFIX && (s->function == add || s->function == sub)) {
581 te_fun2 t = (te_fun2)s->function;
582 next_token(s);
583 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, term(s));
584 ret->function = t;
585 }
586
587 return ret;
588 }
589
590
test_expr(state * s)591 static te_expr *test_expr(state *s) {
592 /* <expr> = <sum_expr> {(">" | ">=" | "<" | "<=" | "==" | "!=") <sum_expr>} */
593 te_expr *ret = sum_expr(s);
594
595 while (s->type == TOK_INFIX && (s->function == greater || s->function == greater_eq ||
596 s->function == lower || s->function == lower_eq || s->function == equal || s->function == not_equal)) {
597 te_fun2 t = (te_fun2)s->function;
598 next_token(s);
599 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, sum_expr(s));
600 ret->function = t;
601 }
602
603 return ret;
604 }
605
606
expr(state * s)607 static te_expr *expr(state *s) {
608 /* <expr> = <test_expr> {("&&" | "||") <test_expr>} */
609 te_expr *ret = test_expr(s);
610
611 while (s->type == TOK_INFIX && (s->function == logical_and || s->function == logical_or)) {
612 te_fun2 t = (te_fun2)s->function;
613 next_token(s);
614 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, test_expr(s));
615 ret->function = t;
616 }
617
618 return ret;
619 }
620
621
list(state * s)622 static te_expr *list(state *s) {
623 /* <list> = <expr> {"," <expr>} */
624 te_expr *ret = expr(s);
625
626 while (s->type == TOK_SEP) {
627 next_token(s);
628 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, expr(s));
629 ret->function = comma;
630 }
631
632 return ret;
633 }
634
635
636 #define TE_FUN(...) ((double(*)(__VA_ARGS__))n->function)
637 #define M(e) te_eval(n->parameters[e])
638
639
te_eval(const te_expr * n)640 double te_eval(const te_expr *n) {
641 if (!n) return NAN;
642
643 switch(TYPE_MASK(n->type)) {
644 case TE_CONSTANT: return n->value;
645 case TE_VARIABLE: return *n->bound;
646
647 case TE_FUNCTION0: case TE_FUNCTION1: case TE_FUNCTION2: case TE_FUNCTION3:
648 case TE_FUNCTION4: case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7:
649 switch(ARITY(n->type)) {
650 case 0: return TE_FUN(void)();
651 case 1: return TE_FUN(double)(M(0));
652 case 2: return TE_FUN(double, double)(M(0), M(1));
653 case 3: return TE_FUN(double, double, double)(M(0), M(1), M(2));
654 case 4: return TE_FUN(double, double, double, double)(M(0), M(1), M(2), M(3));
655 case 5: return TE_FUN(double, double, double, double, double)(M(0), M(1), M(2), M(3), M(4));
656 case 6: return TE_FUN(double, double, double, double, double, double)(M(0), M(1), M(2), M(3), M(4), M(5));
657 case 7: return TE_FUN(double, double, double, double, double, double, double)(M(0), M(1), M(2), M(3), M(4), M(5), M(6));
658 default: return NAN;
659 }
660
661 case TE_CLOSURE0: case TE_CLOSURE1: case TE_CLOSURE2: case TE_CLOSURE3:
662 case TE_CLOSURE4: case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7:
663 switch(ARITY(n->type)) {
664 case 0: return TE_FUN(void*)(n->parameters[0]);
665 case 1: return TE_FUN(void*, double)(n->parameters[1], M(0));
666 case 2: return TE_FUN(void*, double, double)(n->parameters[2], M(0), M(1));
667 case 3: return TE_FUN(void*, double, double, double)(n->parameters[3], M(0), M(1), M(2));
668 case 4: return TE_FUN(void*, double, double, double, double)(n->parameters[4], M(0), M(1), M(2), M(3));
669 case 5: return TE_FUN(void*, double, double, double, double, double)(n->parameters[5], M(0), M(1), M(2), M(3), M(4));
670 case 6: return TE_FUN(void*, double, double, double, double, double, double)(n->parameters[6], M(0), M(1), M(2), M(3), M(4), M(5));
671 case 7: return TE_FUN(void*, double, double, double, double, double, double, double)(n->parameters[7], M(0), M(1), M(2), M(3), M(4), M(5), M(6));
672 default: return NAN;
673 }
674
675 default: return NAN;
676 }
677
678 }
679
680 #undef TE_FUN
681 #undef M
682
optimize(te_expr * n)683 static void optimize(te_expr *n) {
684 /* Evaluates as much as possible. */
685 if (n->type == TE_CONSTANT) return;
686 if (n->type == TE_VARIABLE) return;
687
688 /* Only optimize out functions flagged as pure. */
689 if (IS_PURE(n->type)) {
690 const int arity = ARITY(n->type);
691 int known = 1;
692 int i;
693 for (i = 0; i < arity; ++i) {
694 optimize(n->parameters[i]);
695 if (((te_expr*)(n->parameters[i]))->type != TE_CONSTANT) {
696 known = 0;
697 }
698 }
699 if (known) {
700 const double value = te_eval(n);
701 te_free_parameters(n);
702 n->type = TE_CONSTANT;
703 n->value = value;
704 }
705 }
706 }
707
708
te_compile(const char * expression,const te_variable * variables,int var_count,int * error)709 te_expr *te_compile(const char *expression, const te_variable *variables, int var_count, int *error) {
710 state s;
711 s.start = s.next = expression;
712 s.lookup = variables;
713 s.lookup_len = var_count;
714
715 next_token(&s);
716 te_expr *root = list(&s);
717
718 if (s.type != TOK_END) {
719 te_free(root);
720 if (error) {
721 *error = (s.next - s.start);
722 if (*error == 0) *error = 1;
723 }
724 return 0;
725 } else {
726 optimize(root);
727 if (error) *error = 0;
728 return root;
729 }
730 }
731
732
te_interp(const char * expression,int * error)733 double te_interp(const char *expression, int *error) {
734 te_expr *n = te_compile(expression, 0, 0, error);
735 double ret;
736 if (n) {
737 ret = te_eval(n);
738 te_free(n);
739 } else {
740 ret = NAN;
741 }
742 return ret;
743 }
744
pn(const te_expr * n,int depth)745 static void pn (const te_expr *n, int depth) {
746 int i, arity;
747 printf("%*s", depth, "");
748
749 switch(TYPE_MASK(n->type)) {
750 case TE_CONSTANT: printf("%f\n", n->value); break;
751 case TE_VARIABLE: printf("bound %p\n", n->bound); break;
752
753 case TE_FUNCTION0: case TE_FUNCTION1: case TE_FUNCTION2: case TE_FUNCTION3:
754 case TE_FUNCTION4: case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7:
755 case TE_CLOSURE0: case TE_CLOSURE1: case TE_CLOSURE2: case TE_CLOSURE3:
756 case TE_CLOSURE4: case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7:
757 arity = ARITY(n->type);
758 printf("f%d", arity);
759 for(i = 0; i < arity; i++) {
760 printf(" %p", n->parameters[i]);
761 }
762 printf("\n");
763 for(i = 0; i < arity; i++) {
764 pn(n->parameters[i], depth + 1);
765 }
766 break;
767 }
768 }
769
770
te_print(const te_expr * n)771 void te_print(const te_expr *n) {
772 pn(n, 0);
773 }
774