2 * Copyright (c) 2015 Netflix Inc.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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
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.
28 #include <sys/types.h>
35 #include "eval_expr.h"
36 __FBSDID("$FreeBSD$");
38 static struct expression *
39 alloc_and_hook_expr(struct expression **exp_p, struct expression **last_p)
41 struct expression *ex, *at;
43 ex = malloc(sizeof(struct expression));
45 printf("Out of memory in exp allocation\n");
48 memset(ex, 0, sizeof(struct expression));
54 /* First one, its last */
57 /* Chain it to the end and update last */
67 validate_expr(struct expression *exp, int val1_is_set, int op_is_set, int val2_is_set,
85 if (val1 && op && val2 && (open_cnt == 0)) {
96 if (val1 && op && val2) {
98 * collapse back to val/op
103 } else if ((op == 0) && (val1)) {
106 printf("Op but no val1 set\n");
111 if (exp->next == NULL) {
112 printf("NULL after open paren\n");
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");
122 if (val1 && (op == 0)) {
123 printf("'Val (' -- not allowed\n");
126 if (val1 && op && val2) {
127 printf("'Val OP Val (' -- not allowed\n");
133 if (validate_expr(exp->next, 0, 0, 0, op_cnt) == 0) {
139 return(validate_expr(exp->next, 0, 0, 0, op_cnt));
142 case TYPE_PARN_CLOSE:
145 if (val1 && op && val2) {
148 printf("Found close paren and not complete\n");
156 } else if (val1 && op) {
159 printf("val1 set, val2 about to be set op empty\n");
164 printf("unknown type %d\n", exp->type);
168 return(validate_expr(exp->next, val1, op, val2, op_cnt));
172 print_exp(struct expression *exp)
194 case TYPE_PARN_CLOSE:
198 printf("%f", exp->value);
201 printf("%s", exp->name);
204 printf("Unknown op %d\n", exp->type);
207 print_exp(exp->next);
211 walk_back_and_insert_paren(struct expression **beg, struct expression *frm)
213 struct expression *at, *ex;
215 /* Setup our new open paren */
216 ex = malloc(sizeof(struct expression));
218 printf("Out of memory in exp allocation\n");
221 memset(ex, 0, sizeof(struct expression));
222 ex->type = TYPE_PARN_OPEN;
223 /* Now lets place it */
226 /* We are inserting at the head of the list */
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 */
241 } else if (at->type == TYPE_PARN_CLOSE) {
242 /* Skip through until we reach beg or all ( closes */
247 if (at->type == TYPE_PARN_CLOSE) {
249 } else if (at->type == TYPE_PARN_OPEN) {
258 /* At beginning we insert */
264 printf("%s:Unexpected type:%d?\n",
265 __FUNCTION__, at->type);
271 walk_fwd_and_insert_paren(struct expression *frm, struct expression **added)
273 struct expression *at, *ex;
274 /* Setup our new close paren */
275 ex = malloc(sizeof(struct expression));
277 printf("Out of memory in exp allocation\n");
280 memset(ex, 0, sizeof(struct expression));
281 ex->type = TYPE_PARN_CLOSE;
283 /* Now lets place it */
285 if ((at->type == TYPE_VALUE_CON) ||
286 (at->type == TYPE_VALUE_PMC)) {
287 /* Simple case we have a value in the previous position */
293 } else if (at->type == TYPE_PARN_OPEN) {
297 if (at->type == TYPE_PARN_OPEN) {
299 } else if (at->type == TYPE_PARN_CLOSE) {
309 printf("%s:Unexpected type:%d?\n",
318 add_precendence(struct expression **beg, struct expression *start, struct expression *end)
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
326 struct expression *at, *newone;
332 if (at->type == TYPE_PARN_OPEN) {
335 if (at->type == TYPE_PARN_CLOSE) {
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);
353 set_math_precidence(struct expression **beg, struct expression *exp, struct expression **stopped)
355 struct expression *at, *start, *end;
356 int cnt_lower, cnt_upper;
358 * Walk through and set any math precedence to
359 * get proper precedence we insert () around * / over + -
363 cnt_lower = cnt_upper = 0;
365 if (at->type == TYPE_PARN_CLOSE) {
366 /* Done with that paren */
370 if (cnt_lower && cnt_upper) {
371 /* We have a mixed set ... add precedence between start/end */
372 add_precendence(beg, start, end);
376 if (at->type == TYPE_PARN_OPEN) {
377 set_math_precidence(beg, at->next, &end);
380 } else if ((at->type == TYPE_OP_PLUS) ||
381 (at->type == TYPE_OP_MINUS)) {
383 } else if ((at->type == TYPE_OP_DIVIDE) ||
384 (at->type == TYPE_OP_MULT)) {
389 if (cnt_lower && cnt_upper) {
390 add_precendence(beg, start, NULL);
394 extern char **valid_pmcs;
395 extern int valid_pmc_cnt;
398 pmc_name_set(struct expression *at)
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);
410 strcpy(at->name, valid_pmcs[idx]);
412 for(i=0, fnd=0; i<valid_pmc_cnt; i++) {
413 if (strcmp(valid_pmcs[i], at->name) == 0) {
419 printf("PMC %s does not exist on this machine -- can't run your expression\n",
427 parse_expression(char *str)
429 struct expression *exp=NULL, *last=NULL, *at;
430 int open_par, close_par;
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:
443 * inside every paran you have a:
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).
453 open_par = close_par = 0;
455 /* No trailing newline please */
456 if (str[(siz-1)] == '\n') {
460 for(i=0; i<siz; i++) {
463 } else if (str[i] == ')') {
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);
472 for(i=0; i<siz; 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] == ' ') {
482 } else if (str[i] == '\t') {
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;
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;
503 at->type = TYPE_VALUE_PMC;
506 while ((str[i] != ' ') &&
511 /* We collect the constant until a space or tab */
512 at->name[x] = str[i];
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));
522 /* Need to back up and see the last char since
523 * the for will increment the loop.
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);
536 /* Now lets validate its a workable expression */
537 if (validate_expr(exp, 0, 0, 0, &op_cnt)) {
538 printf("Invalid expression\n");
541 set_math_precidence(&exp, exp, NULL);
547 static struct expression *
548 gather_exp_to_paren_close(struct expression *exp, double *val_fill)
551 * I have been given ( ???
552 * so I could see either
558 struct expression *lastproc;
561 if (exp->type == TYPE_PARN_OPEN) {
562 lastproc = gather_exp_to_paren_close(exp->next, &val);
565 *val_fill = run_expr(exp, 0, &lastproc);
572 run_expr(struct expression *exp, int initial_call, struct expression **lastone)
575 * We expect to find either
580 * c) Val-> Op -> Open Paren
582 double val1, val2, res;
583 struct expression *op, *other_half, *rest;
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) {
590 } else if (exp->type == TYPE_VALUE_PMC) {
594 printf("Illegal value in %s huh?\n", __FUNCTION__);
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;
611 printf("Illegal2 value in %s huh?\n", __FUNCTION__);
628 printf("Division by zero averted\n");
633 printf("Op is not an operator -- its %d\n",
644 if ((rest->type == TYPE_PARN_CLOSE) && (initial_call == 0)) {
646 *lastone = rest->next;
650 /* There is more, as in
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.
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);
670 #ifdef STAND_ALONE_TESTING
673 calc_expr(struct expression *exp)
675 struct expression *at;
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;
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 */
695 /* Now lets calculate the expression */
697 xx = run_expr(exp, 1, NULL);
698 printf("Answer is %f\n", xx);
704 main(int argc, char **argv)
706 struct expression *exp;
708 printf("Use %s expression\n", argv[0]);
711 exp = parse_expression(argv[1]);
712 printf("Now the calc\n");