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