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