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 * 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 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 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 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 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 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 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 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 * 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 * 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 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 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 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