1 /*-
2 * Copyright (c) 2015 Netflix, Inc.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer,
9 * in this position and unchanged.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. The name of the author may not be used to endorse or promote products
14 * derived from this software without specific prior written permission
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27 #include <sys/types.h>
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <unistd.h>
31 #include <string.h>
32 #include <strings.h>
33 #include <ctype.h>
34 #include "eval_expr.h"
35 __FBSDID("$FreeBSD$");
36
37 static struct expression *
alloc_and_hook_expr(struct expression ** exp_p,struct expression ** last_p)38 alloc_and_hook_expr(struct expression **exp_p, struct expression **last_p)
39 {
40 struct expression *ex, *at;
41
42 ex = malloc(sizeof(struct expression));
43 if (ex == NULL) {
44 printf("Out of memory in exp allocation\n");
45 exit(-2);
46 }
47 memset(ex, 0, sizeof(struct expression));
48 if (*exp_p == NULL) {
49 *exp_p = ex;
50 }
51 at = *last_p;
52 if (at == NULL) {
53 /* First one, its last */
54 *last_p = ex;
55 } else {
56 /* Chain it to the end and update last */
57 at->next = ex;
58 ex->prev = at;
59 *last_p = ex;
60 }
61 return (ex);
62 }
63
64
65 static int
validate_expr(struct expression * exp,int val1_is_set,int op_is_set,int val2_is_set,int * op_cnt)66 validate_expr(struct expression *exp, int val1_is_set, int op_is_set, int val2_is_set,
67 int *op_cnt)
68 {
69 int val1, op, val2;
70 int open_cnt;
71 val1 = op = val2 = 0;
72 if (val1_is_set) {
73 val1 = 1;
74 }
75 if (op_is_set) {
76 op = 1;
77 }
78 if (val2_is_set) {
79 val2 = 1;
80 }
81 open_cnt = *op_cnt;
82 if (exp == NULL) {
83 /* End of the road */
84 if (val1 && op && val2 && (open_cnt == 0)) {
85 return(0);
86 } else {
87 return(1);
88 }
89 }
90 switch(exp->type) {
91 case TYPE_OP_PLUS:
92 case TYPE_OP_MINUS:
93 case TYPE_OP_MULT:
94 case TYPE_OP_DIVIDE:
95 if (val1 && op && val2) {
96 /* We are at x + y +
97 * collapse back to val/op
98 */
99 val1 = 1;
100 op = 1;
101 val2 = 0;
102 } else if ((op == 0) && (val1)) {
103 op = 1;
104 } else {
105 printf("Op but no val1 set\n");
106 return(-1);
107 }
108 break;
109 case TYPE_PARN_OPEN:
110 if (exp->next == NULL) {
111 printf("NULL after open paren\n");
112 exit(-1);
113 }
114 if ((exp->next->type == TYPE_OP_PLUS) ||
115 (exp->next->type == TYPE_OP_MINUS) ||
116 (exp->next->type == TYPE_OP_DIVIDE) ||
117 (exp->next->type == TYPE_OP_MULT)) {
118 printf("'( OP' -- not allowed\n");
119 return(-1);
120 }
121 if (val1 && (op == 0)) {
122 printf("'Val (' -- not allowed\n");
123 return(-1);
124 }
125 if (val1 && op && val2) {
126 printf("'Val OP Val (' -- not allowed\n");
127 return(-1);
128 }
129 open_cnt++;
130 *op_cnt = open_cnt;
131 if (val1) {
132 if (validate_expr(exp->next, 0, 0, 0, op_cnt) == 0) {
133 val2 = 1;
134 } else {
135 return(-1);
136 }
137 } else {
138 return(validate_expr(exp->next, 0, 0, 0, op_cnt));
139 }
140 break;
141 case TYPE_PARN_CLOSE:
142 open_cnt--;
143 *op_cnt = open_cnt;
144 if (val1 && op && val2) {
145 return(0);
146 } else {
147 printf("Found close paren and not complete\n");
148 return(-1);
149 }
150 break;
151 case TYPE_VALUE_CON:
152 case TYPE_VALUE_PMC:
153 if (val1 == 0) {
154 val1 = 1;
155 } else if (val1 && op) {
156 val2 = 1;
157 } else {
158 printf("val1 set, val2 about to be set op empty\n");
159 return(-1);
160 }
161 break;
162 default:
163 printf("unknown type %d\n", exp->type);
164 exit(-5);
165 break;
166 }
167 return(validate_expr(exp->next, val1, op, val2, op_cnt));
168 }
169
170 void
print_exp(struct expression * exp)171 print_exp(struct expression *exp)
172 {
173 if (exp == NULL) {
174 printf("\n");
175 return;
176 }
177 switch(exp->type) {
178 case TYPE_OP_PLUS:
179 printf(" + ");
180 break;
181 case TYPE_OP_MINUS:
182 printf(" - ");
183 break;
184 case TYPE_OP_MULT:
185 printf(" * ");
186 break;
187 case TYPE_OP_DIVIDE:
188 printf(" / ");
189 break;
190 case TYPE_PARN_OPEN:
191 printf(" ( ");
192 break;
193 case TYPE_PARN_CLOSE:
194 printf(" ) ");
195 break;
196 case TYPE_VALUE_CON:
197 printf("%f", exp->value);
198 break;
199 case TYPE_VALUE_PMC:
200 printf("%s", exp->name);
201 break;
202 default:
203 printf("Unknown op %d\n", exp->type);
204 break;
205 }
206 print_exp(exp->next);
207 }
208
209 static void
walk_back_and_insert_paren(struct expression ** beg,struct expression * frm)210 walk_back_and_insert_paren(struct expression **beg, struct expression *frm)
211 {
212 struct expression *at, *ex;
213
214 /* Setup our new open paren */
215 ex = malloc(sizeof(struct expression));
216 if (ex == NULL) {
217 printf("Out of memory in exp allocation\n");
218 exit(-2);
219 }
220 memset(ex, 0, sizeof(struct expression));
221 ex->type = TYPE_PARN_OPEN;
222 /* Now lets place it */
223 at = frm->prev;
224 if (at == *beg) {
225 /* We are inserting at the head of the list */
226 in_beg:
227 ex->next = at;
228 at->prev = ex;
229 *beg = ex;
230 return;
231 } else if ((at->type == TYPE_VALUE_CON) ||
232 (at->type == TYPE_VALUE_PMC)) {
233 /* Simple case we have a value in the previous position */
234 in_mid:
235 ex->prev = at->prev;
236 ex->prev->next = ex;
237 ex->next = at;
238 at->prev = ex;
239 return;
240 } else if (at->type == TYPE_PARN_CLOSE) {
241 /* Skip through until we reach beg or all ( closes */
242 int par_cnt=1;
243
244 at = at->prev;
245 while(par_cnt) {
246 if (at->type == TYPE_PARN_CLOSE) {
247 par_cnt++;
248 } else if (at->type == TYPE_PARN_OPEN) {
249 par_cnt--;
250 if (par_cnt == 0) {
251 break;
252 }
253 }
254 at = at->prev;
255 }
256 if (at == *beg) {
257 /* At beginning we insert */
258 goto in_beg;
259 } else {
260 goto in_mid;
261 }
262 } else {
263 printf("%s:Unexpected type:%d?\n",
264 __FUNCTION__, at->type);
265 exit(-1);
266 }
267 }
268
269 static void
walk_fwd_and_insert_paren(struct expression * frm,struct expression ** added)270 walk_fwd_and_insert_paren(struct expression *frm, struct expression **added)
271 {
272 struct expression *at, *ex;
273 /* Setup our new close paren */
274 ex = malloc(sizeof(struct expression));
275 if (ex == NULL) {
276 printf("Out of memory in exp allocation\n");
277 exit(-2);
278 }
279 memset(ex, 0, sizeof(struct expression));
280 ex->type = TYPE_PARN_CLOSE;
281 *added = ex;
282 /* Now lets place it */
283 at = frm->next;
284 if ((at->type == TYPE_VALUE_CON) ||
285 (at->type == TYPE_VALUE_PMC)) {
286 /* Simple case we have a value in the previous position */
287 insertit:
288 ex->next = at->next;
289 ex->prev = at;
290 at->next = ex;
291 return;
292 } else if (at->type == TYPE_PARN_OPEN) {
293 int par_cnt=1;
294 at = at->next;
295 while(par_cnt) {
296 if (at->type == TYPE_PARN_OPEN) {
297 par_cnt++;
298 } else if (at->type == TYPE_PARN_CLOSE) {
299 par_cnt--;
300 if (par_cnt == 0) {
301 break;
302 }
303 }
304 at = at->next;
305 }
306 goto insertit;
307 } else {
308 printf("%s:Unexpected type:%d?\n",
309 __FUNCTION__,
310 at->type);
311 exit(-1);
312 }
313 }
314
315
316 static void
add_precendence(struct expression ** beg,struct expression * start,struct expression * end)317 add_precendence(struct expression **beg, struct expression *start, struct expression *end)
318 {
319 /*
320 * Between start and end add () around any * or /. This
321 * is quite tricky since if there is a () set inside the
322 * list we need to skip over everything in the ()'s considering
323 * that just a value.
324 */
325 struct expression *at, *newone;
326 int open_cnt;
327
328 at = start;
329 open_cnt = 0;
330 while(at != end) {
331 if (at->type == TYPE_PARN_OPEN) {
332 open_cnt++;
333 }
334 if (at->type == TYPE_PARN_CLOSE) {
335 open_cnt--;
336 }
337 if (open_cnt == 0) {
338 if ((at->type == TYPE_OP_MULT) ||
339 (at->type == TYPE_OP_DIVIDE)) {
340 walk_back_and_insert_paren(beg, at);
341 walk_fwd_and_insert_paren(at, &newone);
342 at = newone->next;
343 continue;
344 }
345 }
346 at = at->next;
347 }
348
349 }
350
351 static void
set_math_precidence(struct expression ** beg,struct expression * exp,struct expression ** stopped)352 set_math_precidence(struct expression **beg, struct expression *exp, struct expression **stopped)
353 {
354 struct expression *at, *start, *end;
355 int cnt_lower, cnt_upper;
356 /*
357 * Walk through and set any math precedence to
358 * get proper precedence we insert () around * / over + -
359 */
360 end = NULL;
361 start = at = exp;
362 cnt_lower = cnt_upper = 0;
363 while(at) {
364 if (at->type == TYPE_PARN_CLOSE) {
365 /* Done with that paren */
366 if (stopped) {
367 *stopped = at;
368 }
369 if (cnt_lower && cnt_upper) {
370 /* We have a mixed set ... add precedence between start/end */
371 add_precendence(beg, start, end);
372 }
373 return;
374 }
375 if (at->type == TYPE_PARN_OPEN) {
376 set_math_precidence(beg, at->next, &end);
377 at = end;
378 continue;
379 } else if ((at->type == TYPE_OP_PLUS) ||
380 (at->type == TYPE_OP_MINUS)) {
381 cnt_lower++;
382 } else if ((at->type == TYPE_OP_DIVIDE) ||
383 (at->type == TYPE_OP_MULT)) {
384 cnt_upper++;
385 }
386 at = at->next;
387 }
388 if (cnt_lower && cnt_upper) {
389 add_precendence(beg, start, NULL);
390 }
391 }
392
393 extern char **valid_pmcs;
394 extern int valid_pmc_cnt;
395
396 static void
pmc_name_set(struct expression * at)397 pmc_name_set(struct expression *at)
398 {
399 int i, idx, fnd;
400
401 if (at->name[0] == '%') {
402 /* Special number after $ gives index */
403 idx = strtol(&at->name[1], NULL, 0);
404 if (idx >= valid_pmc_cnt) {
405 printf("Unknown PMC %s -- largest we have is $%d -- can't run your expression\n",
406 at->name, valid_pmc_cnt);
407 exit(-1);
408 }
409 strcpy(at->name, valid_pmcs[idx]);
410 } else {
411 for(i=0, fnd=0; i<valid_pmc_cnt; i++) {
412 if (strcmp(valid_pmcs[i], at->name) == 0) {
413 fnd = 1;
414 break;
415 }
416 }
417 if (!fnd) {
418 printf("PMC %s does not exist on this machine -- can't run your expression\n",
419 at->name);
420 exit(-1);
421 }
422 }
423 }
424
425 struct expression *
parse_expression(char * str)426 parse_expression(char *str)
427 {
428 struct expression *exp=NULL, *last=NULL, *at;
429 int open_par, close_par;
430 int op_cnt=0;
431 size_t siz, i, x;
432 /*
433 * Walk through a string expression and convert
434 * it to a linked list of actions. We do this by:
435 * a) Counting the open/close paren's, there must
436 * be a matching number.
437 * b) If we have balanced paren's then create a linked list
438 * of the operators, then we validate that expression further.
439 * c) Validating that we have:
440 * val OP val <or>
441 * val OP ( <and>
442 * inside every paran you have a:
443 * val OP val <or>
444 * val OP ( <recursively>
445 * d) A final optional step (not implemented yet) would be
446 * to insert the mathematical precedence paran's. For
447 * the start we will just do the left to right evaluation and
448 * then later we can add this guy to add paran's to make it
449 * mathimatically correct... i.e instead of 1 + 2 * 3 we
450 * would translate it into 1 + ( 2 * 3).
451 */
452 open_par = close_par = 0;
453 siz = strlen(str);
454 /* No trailing newline please */
455 if (str[(siz-1)] == '\n') {
456 str[(siz-1)] = 0;
457 siz--;
458 }
459 for(i=0; i<siz; i++) {
460 if (str[i] == '(') {
461 open_par++;
462 } else if (str[i] == ')') {
463 close_par++;
464 }
465 }
466 if (open_par != close_par) {
467 printf("Invalid expression '%s' %d open paren's and %d close?\n",
468 str, open_par, close_par);
469 exit(-1);
470 }
471 for(i=0; i<siz; i++) {
472 if (str[i] == '(') {
473 at = alloc_and_hook_expr(&exp, &last);
474 at->type = TYPE_PARN_OPEN;
475 } else if (str[i] == ')') {
476 at = alloc_and_hook_expr(&exp, &last);
477 at->type = TYPE_PARN_CLOSE;
478 } else if (str[i] == ' ') {
479 /* Extra blank */
480 continue;
481 } else if (str[i] == '\t') {
482 /* Extra tab */
483 continue;
484 } else if (str[i] == '+') {
485 at = alloc_and_hook_expr(&exp, &last);
486 at->type = TYPE_OP_PLUS;
487 } else if (str[i] == '-') {
488 at = alloc_and_hook_expr(&exp, &last);
489 at->type = TYPE_OP_MINUS;
490 } else if (str[i] == '/') {
491 at = alloc_and_hook_expr(&exp, &last);
492 at->type = TYPE_OP_DIVIDE;
493 } else if (str[i] == '*') {
494 at = alloc_and_hook_expr(&exp, &last);
495 at->type = TYPE_OP_MULT;
496 } else {
497 /* Its a value or PMC constant */
498 at = alloc_and_hook_expr(&exp, &last);
499 if (isdigit(str[i]) || (str[i] == '.')) {
500 at->type = TYPE_VALUE_CON;
501 } else {
502 at->type = TYPE_VALUE_PMC;
503 }
504 x = 0;
505 while ((str[i] != ' ') &&
506 (str[i] != '\t') &&
507 (str[i] != 0) &&
508 (str[i] != ')') &&
509 (str[i] != '(')) {
510 /* We collect the constant until a space or tab */
511 at->name[x] = str[i];
512 i++;
513 x++;
514 if (x >=(sizeof(at->name)-1)) {
515 printf("Value/Constant too long %d max:%d\n",
516 (int)x, (int)(sizeof(at->name)-1));
517 exit(-3);
518 }
519 }
520 if (str[i] != 0) {
521 /* Need to back up and see the last char since
522 * the for will increment the loop.
523 */
524 i--;
525 }
526 /* Now we have pulled the string, set it up */
527 if (at->type == TYPE_VALUE_CON) {
528 at->state = STATE_FILLED;
529 at->value = strtod(at->name, NULL);
530 } else {
531 pmc_name_set(at);
532 }
533 }
534 }
535 /* Now lets validate its a workable expression */
536 if (validate_expr(exp, 0, 0, 0, &op_cnt)) {
537 printf("Invalid expression\n");
538 exit(-4);
539 }
540 set_math_precidence(&exp, exp, NULL);
541 return (exp);
542 }
543
544
545
546 static struct expression *
gather_exp_to_paren_close(struct expression * exp,double * val_fill)547 gather_exp_to_paren_close(struct expression *exp, double *val_fill)
548 {
549 /*
550 * I have been given ( ???
551 * so I could see either
552 * (
553 * or
554 * Val Op
555 *
556 */
557 struct expression *lastproc;
558 double val;
559
560 if (exp->type == TYPE_PARN_OPEN) {
561 lastproc = gather_exp_to_paren_close(exp->next, &val);
562 *val_fill = val;
563 } else {
564 *val_fill = run_expr(exp, 0, &lastproc);
565 }
566 return(lastproc);
567 }
568
569
570 double
run_expr(struct expression * exp,int initial_call,struct expression ** lastone)571 run_expr(struct expression *exp, int initial_call, struct expression **lastone)
572 {
573 /*
574 * We expect to find either
575 * a) A Open Paren
576 * or
577 * b) Val-> Op -> Val
578 * or
579 * c) Val-> Op -> Open Paren
580 */
581 double val1, val2, res;
582 struct expression *op, *other_half, *rest;
583
584 if (exp->type == TYPE_PARN_OPEN) {
585 op = gather_exp_to_paren_close(exp->next, &val1);
586 } else if(exp->type == TYPE_VALUE_CON) {
587 val1 = exp->value;
588 op = exp->next;
589 } else if (exp->type == TYPE_VALUE_PMC) {
590 val1 = exp->value;
591 op = exp->next;
592 } else {
593 printf("Illegal value in %s huh?\n", __FUNCTION__);
594 exit(-1);
595 }
596 if (op == NULL) {
597 return (val1);
598 }
599 more_to_do:
600 other_half = op->next;
601 if (other_half->type == TYPE_PARN_OPEN) {
602 rest = gather_exp_to_paren_close(other_half->next, &val2);
603 } else if(other_half->type == TYPE_VALUE_CON) {
604 val2 = other_half->value;
605 rest = other_half->next;
606 } else if (other_half->type == TYPE_VALUE_PMC) {
607 val2 = other_half->value;
608 rest = other_half->next;
609 } else {
610 printf("Illegal2 value in %s huh?\n", __FUNCTION__);
611 exit(-1);
612 }
613 switch(op->type) {
614 case TYPE_OP_PLUS:
615 res = val1 + val2;
616 break;
617 case TYPE_OP_MINUS:
618 res = val1 - val2;
619 break;
620 case TYPE_OP_MULT:
621 res = val1 * val2;
622 break;
623 case TYPE_OP_DIVIDE:
624 if (val2 != 0.0)
625 res = val1 / val2;
626 else {
627 printf("Division by zero averted\n");
628 res = 1.0;
629 }
630 break;
631 default:
632 printf("Op is not an operator -- its %d\n",
633 op->type);
634 exit(-1);
635 break;
636 }
637 if (rest == NULL) {
638 if (lastone) {
639 *lastone = NULL;
640 }
641 return (res);
642 }
643 if ((rest->type == TYPE_PARN_CLOSE) && (initial_call == 0)) {
644 if (lastone) {
645 *lastone = rest->next;
646 }
647 return(res);
648 }
649 /* There is more, as in
650 * a + b + c
651 * where we just did a + b
652 * so now it becomes val1 is set to res and
653 * we need to proceed with the rest of it.
654 */
655 val1 = res;
656 op = rest;
657 if ((op->type != TYPE_OP_PLUS) &&
658 (op->type != TYPE_OP_MULT) &&
659 (op->type != TYPE_OP_MINUS) &&
660 (op->type != TYPE_OP_DIVIDE)) {
661 printf("%s ending on type:%d not an op??\n", __FUNCTION__, op->type);
662 return(res);
663 }
664 if (op)
665 goto more_to_do;
666 return (res);
667 }
668
669 #ifdef STAND_ALONE_TESTING
670
671 static double
calc_expr(struct expression * exp)672 calc_expr(struct expression *exp)
673 {
674 struct expression *at;
675 double xx;
676
677 /* First clear PMC's setting */
678 for(at = exp; at != NULL; at = at->next) {
679 if (at->type == TYPE_VALUE_PMC) {
680 at->state = STATE_UNSET;
681 }
682 }
683 /* Now for all pmc's make up values .. here is where I would pull them */
684 for(at = exp; at != NULL; at = at->next) {
685 if (at->type == TYPE_VALUE_PMC) {
686 at->value = (random() * 1.0);
687 at->state = STATE_FILLED;
688 if (at->value == 0.0) {
689 /* So we don't have div by 0 */
690 at->value = 1.0;
691 }
692 }
693 }
694 /* Now lets calculate the expression */
695 print_exp(exp);
696 xx = run_expr(exp, 1, NULL);
697 printf("Answer is %f\n", xx);
698 return(xx);
699 }
700
701
702 int
main(int argc,char ** argv)703 main(int argc, char **argv)
704 {
705 struct expression *exp;
706 if (argc < 2) {
707 printf("Use %s expression\n", argv[0]);
708 return(-1);
709 }
710 exp = parse_expression(argv[1]);
711 printf("Now the calc\n");
712 calc_expr(exp);
713 return(0);
714 }
715
716 #endif
717