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