2 * Copyright (c) 2015 Netflix, Inc.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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
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.
27 #include <sys/types.h>
34 #include "eval_expr.h"
35 __FBSDID("$FreeBSD$");
37 static struct expression *
38 alloc_and_hook_expr(struct expression **exp_p, struct expression **last_p)
40 struct expression *ex, *at;
42 ex = malloc(sizeof(struct expression));
44 printf("Out of memory in exp allocation\n");
47 memset(ex, 0, sizeof(struct expression));
53 /* First one, its last */
56 /* Chain it to the end and update last */
66 validate_expr(struct expression *exp, int val1_is_set, int op_is_set, int val2_is_set,
84 if (val1 && op && val2 && (open_cnt == 0)) {
95 if (val1 && op && val2) {
97 * collapse back to val/op
102 } else if ((op == 0) && (val1)) {
105 printf("Op but no val1 set\n");
110 if (exp->next == NULL) {
111 printf("NULL after open paren\n");
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");
121 if (val1 && (op == 0)) {
122 printf("'Val (' -- not allowed\n");
125 if (val1 && op && val2) {
126 printf("'Val OP Val (' -- not allowed\n");
132 if (validate_expr(exp->next, 0, 0, 0, op_cnt) == 0) {
138 return(validate_expr(exp->next, 0, 0, 0, op_cnt));
141 case TYPE_PARN_CLOSE:
144 if (val1 && op && val2) {
147 printf("Found close paren and not complete\n");
155 } else if (val1 && op) {
158 printf("val1 set, val2 about to be set op empty\n");
163 printf("unknown type %d\n", exp->type);
167 return(validate_expr(exp->next, val1, op, val2, op_cnt));
171 print_exp(struct expression *exp)
193 case TYPE_PARN_CLOSE:
197 printf("%f", exp->value);
200 printf("%s", exp->name);
203 printf("Unknown op %d\n", exp->type);
206 print_exp(exp->next);
210 walk_back_and_insert_paren(struct expression **beg, struct expression *frm)
212 struct expression *at, *ex;
214 /* Setup our new open paren */
215 ex = malloc(sizeof(struct expression));
217 printf("Out of memory in exp allocation\n");
220 memset(ex, 0, sizeof(struct expression));
221 ex->type = TYPE_PARN_OPEN;
222 /* Now lets place it */
225 /* We are inserting at the head of the list */
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 */
240 } else if (at->type == TYPE_PARN_CLOSE) {
241 /* Skip through until we reach beg or all ( closes */
246 if (at->type == TYPE_PARN_CLOSE) {
248 } else if (at->type == TYPE_PARN_OPEN) {
257 /* At beginning we insert */
263 printf("%s:Unexpected type:%d?\n",
264 __FUNCTION__, at->type);
270 walk_fwd_and_insert_paren(struct expression *frm, struct expression **added)
272 struct expression *at, *ex;
273 /* Setup our new close paren */
274 ex = malloc(sizeof(struct expression));
276 printf("Out of memory in exp allocation\n");
279 memset(ex, 0, sizeof(struct expression));
280 ex->type = TYPE_PARN_CLOSE;
282 /* Now lets place it */
284 if ((at->type == TYPE_VALUE_CON) ||
285 (at->type == TYPE_VALUE_PMC)) {
286 /* Simple case we have a value in the previous position */
292 } else if (at->type == TYPE_PARN_OPEN) {
296 if (at->type == TYPE_PARN_OPEN) {
298 } else if (at->type == TYPE_PARN_CLOSE) {
308 printf("%s:Unexpected type:%d?\n",
317 add_precendence(struct expression **beg, struct expression *start, struct expression *end)
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
325 struct expression *at, *newone;
331 if (at->type == TYPE_PARN_OPEN) {
334 if (at->type == TYPE_PARN_CLOSE) {
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);
352 set_math_precidence(struct expression **beg, struct expression *exp, struct expression **stopped)
354 struct expression *at, *start, *end;
355 int cnt_lower, cnt_upper;
357 * Walk through and set any math precedence to
358 * get proper precedence we insert () around * / over + -
362 cnt_lower = cnt_upper = 0;
364 if (at->type == TYPE_PARN_CLOSE) {
365 /* Done with that paren */
369 if (cnt_lower && cnt_upper) {
370 /* We have a mixed set ... add precedence between start/end */
371 add_precendence(beg, start, end);
375 if (at->type == TYPE_PARN_OPEN) {
376 set_math_precidence(beg, at->next, &end);
379 } else if ((at->type == TYPE_OP_PLUS) ||
380 (at->type == TYPE_OP_MINUS)) {
382 } else if ((at->type == TYPE_OP_DIVIDE) ||
383 (at->type == TYPE_OP_MULT)) {
388 if (cnt_lower && cnt_upper) {
389 add_precendence(beg, start, NULL);
393 extern char **valid_pmcs;
394 extern int valid_pmc_cnt;
397 pmc_name_set(struct expression *at)
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);
409 strcpy(at->name, valid_pmcs[idx]);
411 for(i=0, fnd=0; i<valid_pmc_cnt; i++) {
412 if (strcmp(valid_pmcs[i], at->name) == 0) {
418 printf("PMC %s does not exist on this machine -- can't run your expression\n",
426 parse_expression(char *str)
428 struct expression *exp=NULL, *last=NULL, *at;
429 int open_par, close_par;
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:
442 * inside every paran you have a:
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).
452 open_par = close_par = 0;
454 /* No trailing newline please */
455 if (str[(siz-1)] == '\n') {
459 for(i=0; i<siz; i++) {
462 } else if (str[i] == ')') {
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);
471 for(i=0; i<siz; 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] == ' ') {
481 } else if (str[i] == '\t') {
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;
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;
502 at->type = TYPE_VALUE_PMC;
505 while ((str[i] != ' ') &&
510 /* We collect the constant until a space or tab */
511 at->name[x] = str[i];
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));
521 /* Need to back up and see the last char since
522 * the for will increment the loop.
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);
535 /* Now lets validate its a workable expression */
536 if (validate_expr(exp, 0, 0, 0, &op_cnt)) {
537 printf("Invalid expression\n");
540 set_math_precidence(&exp, exp, NULL);
546 static struct expression *
547 gather_exp_to_paren_close(struct expression *exp, double *val_fill)
550 * I have been given ( ???
551 * so I could see either
557 struct expression *lastproc;
560 if (exp->type == TYPE_PARN_OPEN) {
561 lastproc = gather_exp_to_paren_close(exp->next, &val);
564 *val_fill = run_expr(exp, 0, &lastproc);
571 run_expr(struct expression *exp, int initial_call, struct expression **lastone)
574 * We expect to find either
579 * c) Val-> Op -> Open Paren
581 double val1, val2, res;
582 struct expression *op, *other_half, *rest;
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) {
589 } else if (exp->type == TYPE_VALUE_PMC) {
593 printf("Illegal value in %s huh?\n", __FUNCTION__);
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;
610 printf("Illegal2 value in %s huh?\n", __FUNCTION__);
627 printf("Division by zero averted\n");
632 printf("Op is not an operator -- its %d\n",
643 if ((rest->type == TYPE_PARN_CLOSE) && (initial_call == 0)) {
645 *lastone = rest->next;
649 /* There is more, as in
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.
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);
669 #ifdef STAND_ALONE_TESTING
672 calc_expr(struct expression *exp)
674 struct expression *at;
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;
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 */
694 /* Now lets calculate the expression */
696 xx = run_expr(exp, 1, NULL);
697 printf("Answer is %f\n", xx);
703 main(int argc, char **argv)
705 struct expression *exp;
707 printf("Use %s expression\n", argv[0]);
710 exp = parse_expression(argv[1]);
711 printf("Now the calc\n");