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