smatch_math.c

   1 /*
   2  * smatch/smatch_math.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "smatch.h"
  11 #include "smatch_slist.h"
  12 #include "smatch_extra.h"
  13
  14 static sval_t _get_value(struct expression *expr, int *undefined, int implied);
  15 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied);
  16
  17 #define BOGUS 12345
  18
  19 static sval_t zero  = {.type = &int_ctype, .value = 0};
  20 static sval_t one   = {.type = &int_ctype, .value = 1};
  21 static sval_t bogus = {.type = &int_ctype, .value = BOGUS};
  22
  23 #define NOTIMPLIED  0
  24 #define IMPLIED     1
  25 #define IMPLIED_MIN 2
  26 #define IMPLIED_MAX 3
  27 #define FUZZYMAX    4
  28 #define FUZZYMIN    5
  29 #define ABSOLUTE_MIN 6
  30 #define ABSOLUTE_MAX 7
  31
  32 static int opposite_implied(int implied)
  33 {
  34         if (implied == IMPLIED_MIN)
  35                 return IMPLIED_MAX;
  36         if (implied == IMPLIED_MAX)
  37                 return IMPLIED_MIN;
  38         if (implied == ABSOLUTE_MIN)
  39                 return ABSOLUTE_MAX;
  40         if (implied == ABSOLUTE_MAX)
  41                 return ABSOLUTE_MIN;
  42         return implied;
  43 }
  44
  45 static int last_stmt_sval(struct statement *stmt, sval_t *sval)
  46 {
  47         struct expression *expr;
  48
  49         if (!stmt)
  50                 return 0;
  51
  52         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  53         if (stmt->type != STMT_EXPRESSION)
  54                 return 0;
  55         expr = stmt->expression;
  56         if (!get_value_sval(expr, sval))
  57                 return 0;
  58         return 1;
  59 }
  60
  61 static sval_t handle_expression_statement(struct expression *expr, int *undefined, int implied)
  62 {
  63         struct statement *stmt;
  64         sval_t ret;
  65
  66         stmt = get_expression_statement(expr);
  67         if (!last_stmt_sval(stmt, &ret)) {
  68                 *undefined = 1;
  69                 ret.value = BOGUS;
  70         }
  71
  72         return ret;
  73 }
  74
  75 static sval_t handle_ampersand(int *undefined, int implied)
  76 {
  77         sval_t ret;
  78
  79         ret.type = &ptr_ctype;
  80         ret.value = BOGUS;
  81
  82         if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
  83                 return valid_ptr_min_sval;
  84         if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
  85                 return valid_ptr_max_sval;
  86
  87         *undefined = 1;
  88         return ret;
  89 }
  90
  91 static sval_t handle_preop(struct expression *expr, int *undefined, int implied)
  92 {
  93         sval_t ret;
  94
  95         switch (expr->op) {
  96         case '&':
  97                 ret = handle_ampersand(undefined, implied);
  98                 break;
  99         case '!':
 100                 ret = _get_value(expr->unop, undefined, implied);
 101                 ret = sval_preop(ret, '!');
 102                 break;
 103         case '~':
 104                 ret = _get_value(expr->unop, undefined, implied);
 105                 ret = sval_preop(ret, '~');
 106                 ret = sval_cast(ret, get_type(expr->unop));
 107                 break;
 108         case '-':
 109                 ret = _get_value(expr->unop, undefined, implied);
 110                 ret = sval_preop(ret, '-');
 111                 break;
 112         case '*':
 113                 ret = _get_implied_value(expr, undefined, implied);
 114                 break;
 115         case '(':
 116                 ret = handle_expression_statement(expr, undefined, implied);
 117                 break;
 118         default:
 119                 *undefined = 1;
 120                 ret = sval_blank(expr);
 121         }
 122         return ret;
 123 }
 124
 125 static sval_t handle_divide(struct expression *expr, int *undefined, int implied)
 126 {
 127         sval_t left, right;
 128
 129         left = _get_value(expr->left, undefined, implied);
 130         right = _get_value(expr->right, undefined, opposite_implied(implied));
 131
 132         if (right.value == 0)
 133                 *undefined = 1;
 134
 135         return sval_binop(left, '/', right);
 136 }
 137
 138 static sval_t handle_subtract(struct expression *expr, int *undefined, int implied)
 139 {
 140         sval_t left, right;
 141
 142         left = _get_value(expr->left, undefined, implied);
 143         right = _get_value(expr->right, undefined, opposite_implied(implied));
 144
 145         return sval_binop(left, '-', right);
 146 }
 147
 148 static sval_t handle_binop(struct expression *expr, int *undefined, int implied)
 149 {
 150         sval_t left, right;
 151         sval_t ret = {.type = &int_ctype, .value = 123456};
 152         int local_undef = 0;
 153
 154         switch (expr->op) {
 155         case '%':
 156                 left = _get_value(expr->left, &local_undef, implied);
 157                 if (local_undef) {
 158                         if (implied == ABSOLUTE_MIN) {
 159                                 ret = sval_blank(expr->left);
 160                                 ret.value = 0;
 161                                 return ret;
 162                         }
 163                         if (implied != ABSOLUTE_MAX)
 164                                 *undefined = 1;
 165                         if (!get_absolute_max_sval(expr->left, &left))
 166                                 *undefined = 1;
 167                 }
 168                 right = _get_value(expr->right, undefined, implied);
 169                 if (right.value == 0)
 170                         *undefined = 1;
 171                 else
 172                         ret = sval_binop(left, '%', right);
 173                 return ret;
 174
 175         case '&':
 176                 left = _get_value(expr->left, &local_undef, implied);
 177                 if (local_undef) {
 178                         if (implied == ABSOLUTE_MIN) {
 179                                 ret = sval_blank(expr->left);
 180                                 ret.value = 0;
 181                                 return ret;
 182                         }
 183                         if (implied != ABSOLUTE_MAX)
 184                                 *undefined = 1;
 185                         if (!get_absolute_max_sval(expr->left, &left))
 186                                 *undefined = 1;
 187                 }
 188                 right = _get_value(expr->right, undefined, implied);
 189                 return sval_binop(left, '&', right);
 190
 191         case SPECIAL_RIGHTSHIFT:
 192                 left = _get_value(expr->left, &local_undef, implied);
 193                 if (local_undef) {
 194                         if (implied == ABSOLUTE_MIN) {
 195                                 ret = sval_blank(expr->left);
 196                                 ret.value = 0;
 197                                 return ret;
 198                         }
 199                         if (implied != ABSOLUTE_MAX)
 200                                 *undefined = 1;
 201                         if (!get_absolute_max_sval(expr->left, &left))
 202                                 *undefined = 1;
 203                 }
 204                 right = _get_value(expr->right, undefined, implied);
 205                 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 206         }
 207
 208         left = _get_value(expr->left, undefined, implied);
 209         right = _get_value(expr->right, undefined, implied);
 210
 211         switch (expr->op) {
 212         case '/':
 213                 return handle_divide(expr, undefined, implied);
 214         case '%':
 215                 if (right.value == 0)
 216                         *undefined = 1;
 217                 else
 218                         ret = sval_binop(left, '%', right);
 219                 break;
 220         case '-':
 221                 ret = handle_subtract(expr, undefined, implied);
 222                 break;
 223         default:
 224                 ret = sval_binop(left, expr->op, right);
 225         }
 226         return ret;
 227 }
 228
 229 static int do_comparison(struct expression *expr)
 230 {
 231         struct range_list_sval *left_ranges = NULL;
 232         struct range_list_sval *right_ranges = NULL;
 233         int poss_true, poss_false;
 234
 235         get_implied_range_list_sval(expr->left, &left_ranges);
 236         get_implied_range_list_sval(expr->right, &right_ranges);
 237
 238         poss_true = possibly_true_range_lists_sval(left_ranges, expr->op, right_ranges);
 239         poss_false = possibly_false_range_lists_sval(left_ranges, expr->op, right_ranges);
 240
 241         free_range_list_sval(&left_ranges);
 242         free_range_list_sval(&right_ranges);
 243
 244         if (!poss_true && !poss_false)
 245                 return 0;
 246         if (poss_true && !poss_false)
 247                 return 1;
 248         if (!poss_true && poss_false)
 249                 return 2;
 250         return 3;
 251 }
 252
 253 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
 254 {
 255         sval_t left, right;
 256         int res;
 257
 258         if (get_value_sval(expr->left, &left) && get_value_sval(expr->right, &right)) {
 259                 struct data_range_sval tmp_left, tmp_right;
 260
 261                 tmp_left.min = left;
 262                 tmp_left.max = left;
 263                 tmp_right.min = right;
 264                 tmp_right.max = right;
 265                 if (true_comparison_range_sval(&tmp_left, expr->op, &tmp_right))
 266                         return one;
 267                 return zero;
 268         }
 269
 270         if (implied == NOTIMPLIED) {
 271                 *undefined = 1;
 272                 return bogus;
 273         }
 274
 275         res = do_comparison(expr);
 276         if (res == 1)
 277                 return one;
 278         if (res == 2)
 279                 return zero;
 280
 281         if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
 282                 return zero;
 283         if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
 284                 return one;
 285
 286         *undefined = 1;
 287         return bogus;
 288 }
 289
 290 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
 291 {
 292         sval_t left, right;
 293
 294         if ((implied == NOTIMPLIED && get_value_sval(expr->left, &left) &&
 295                                       get_value_sval(expr->right, &right)) ||
 296             (implied != NOTIMPLIED && get_implied_value_sval(expr->left, &left) &&
 297                                       get_implied_value_sval(expr->right, &right))) {
 298                 switch (expr->op) {
 299                 case SPECIAL_LOGICAL_OR:
 300                         if (left.value || right.value)
 301                                 return one;
 302                         return zero;
 303                 case SPECIAL_LOGICAL_AND:
 304                         if (left.value && right.value)
 305                                 return one;
 306                         return zero;
 307                 default:
 308                         *undefined = 1;
 309                         return bogus;
 310                 }
 311         }
 312
 313         if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
 314                 return zero;
 315         if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
 316                 return one;
 317
 318         *undefined = 1;
 319         return bogus;
 320 }
 321
 322 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 323 {
 324         if (known_condition_true(expr->conditional))
 325                 return _get_value(expr->cond_true, undefined, implied);
 326         if (known_condition_false(expr->conditional))
 327                 return _get_value(expr->cond_false, undefined, implied);
 328
 329         if (implied == NOTIMPLIED) {
 330                 *undefined = 1;
 331                 return bogus;
 332         }
 333
 334         if (implied_condition_true(expr->conditional))
 335                 return _get_value(expr->cond_true, undefined, implied);
 336         if (implied_condition_false(expr->conditional))
 337                 return _get_value(expr->cond_false, undefined, implied);
 338
 339         *undefined = 1;
 340         return bogus;
 341 }
 342
 343 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 344 {
 345         struct smatch_state *state;
 346         struct symbol *sym;
 347         char *name;
 348
 349         /* fixme: this should return the casted value */
 350
 351         expr = strip_expr(expr);
 352
 353         if (get_value_sval(expr, sval))
 354                 return 1;
 355
 356         name = get_variable_from_expr(expr, &sym);
 357         if (!name)
 358                 return 0;
 359         *sval = sval_blank(expr);
 360         state = get_state(SMATCH_EXTRA, name, sym);
 361         free_string(name);
 362         if (!state || !state->data)
 363                 return 0;
 364         if (implied == IMPLIED) {
 365                 if (estate_get_single_value_sval(state, sval))
 366                         return 1;
 367                 return 0;
 368         }
 369         if (implied == IMPLIED_MAX || implied == ABSOLUTE_MAX) {
 370                 *sval = estate_max_sval(state);
 371                 if (sval_is_max(*sval)) /* this means just guessing.  fixme. not really */
 372                         return 0;
 373                 return 1;
 374         }
 375         *sval = estate_min_sval(state);
 376         if (sval_is_min(*sval))       /* fixme */
 377                 return 0;
 378         return 1;
 379 }
 380
 381 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 382 {
 383         struct sm_state *sm;
 384         struct sm_state *tmp;
 385         sval_t sval;
 386
 387         if (get_implied_max_sval(expr, max))
 388                 return 1;
 389
 390         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 391         if (!sm)
 392                 return 0;
 393
 394         sval = sval_type_min(&llong_ctype);
 395         FOR_EACH_PTR(sm->possible, tmp) {
 396                 sval_t new_min;
 397
 398                 new_min = estate_min_sval(tmp->state);
 399                 if (sval_cmp(new_min, sval) > 0)
 400                         sval = new_min;
 401         } END_FOR_EACH_PTR(tmp);
 402
 403         if (sval_is_min(sval))
 404                 return 0;
 405
 406         *max = sval_cast(sval, get_type(expr));
 407         return 1;
 408 }
 409
 410 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 411 {
 412         struct sm_state *sm;
 413         struct sm_state *tmp;
 414         sval_t sval;
 415
 416         if (get_implied_min_sval(expr, min))
 417                 return 1;
 418
 419         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 420         if (!sm)
 421                 return 0;
 422
 423         sval = sval_type_max(&llong_ctype);
 424         FOR_EACH_PTR(sm->possible, tmp) {
 425                 sval_t new_max;
 426
 427                 new_max = estate_max_sval(tmp->state);
 428                 if (sval_cmp(new_max, sval) < 0)
 429                         sval = new_max;
 430         } END_FOR_EACH_PTR(tmp);
 431
 432         if (sval_is_max(sval))
 433                 return 0;
 434         *min = sval_cast(sval, get_type(expr));
 435         return 1;
 436 }
 437
 438 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 439 {
 440         sval_t ret;
 441
 442         ret = sval_blank(expr);
 443
 444         switch (implied) {
 445         case IMPLIED:
 446         case IMPLIED_MAX:
 447         case IMPLIED_MIN:
 448                 if (!get_implied_value_helper(expr, &ret, implied))
 449                         *undefined = 1;
 450                 break;
 451         case ABSOLUTE_MIN:
 452                 if (!get_absolute_min_helper(expr, &ret))
 453                         *undefined = 1;
 454                 break;
 455         case ABSOLUTE_MAX:
 456                 if (!get_absolute_max_helper(expr, &ret))
 457                         *undefined = 1;
 458                 break;
 459         case FUZZYMAX:
 460                 if (!get_fuzzy_max_helper(expr, &ret))
 461                         *undefined = 1;
 462                 break;
 463         case FUZZYMIN:
 464                 if (!get_fuzzy_min_helper(expr, &ret))
 465                         *undefined = 1;
 466                 break;
 467         default:
 468                 *undefined = 1;
 469         }
 470         return ret;
 471 }
 472
 473 static int get_const_value(struct expression *expr, sval_t *sval)
 474 {
 475         struct symbol *sym;
 476         sval_t right;
 477
 478         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 479                 return 0;
 480         sym = expr->symbol;
 481         if (!(sym->ctype.modifiers & MOD_CONST))
 482                 return 0;
 483         if (get_value_sval(sym->initializer, &right)) {
 484                 *sval = sval_cast(right, get_type(expr));
 485                 return 1;
 486         }
 487         return 0;
 488 }
 489
 490 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 491 {
 492         sval_t tmp_ret;
 493
 494         if (!expr) {
 495                 *undefined = 1;
 496                 return bogus;
 497         }
 498         if (*undefined)
 499                 return bogus;
 500
 501         expr = strip_parens(expr);
 502
 503         switch (expr->type) {
 504         case EXPR_VALUE:
 505                 tmp_ret = sval_from_val(expr, expr->value);
 506                 break;
 507         case EXPR_PREOP:
 508                 tmp_ret = handle_preop(expr, undefined, implied);
 509                 break;
 510         case EXPR_POSTOP:
 511                 tmp_ret = _get_value(expr->unop, undefined, implied);
 512                 break;
 513         case EXPR_CAST:
 514         case EXPR_FORCE_CAST:
 515         case EXPR_IMPLIED_CAST:
 516                 tmp_ret = _get_value(expr->cast_expression, undefined, implied);
 517                 tmp_ret = sval_cast(tmp_ret, get_type(expr));
 518                 break;
 519         case EXPR_BINOP:
 520                 tmp_ret = handle_binop(expr, undefined, implied);
 521                 break;
 522         case EXPR_COMPARE:
 523                 tmp_ret = handle_comparison(expr, undefined, implied);
 524                 break;
 525         case EXPR_LOGICAL:
 526                 tmp_ret = handle_logical(expr, undefined, implied);
 527                 break;
 528         case EXPR_PTRSIZEOF:
 529         case EXPR_SIZEOF:
 530                 tmp_ret = sval_blank(expr);
 531                 tmp_ret.value = get_expression_value_nomod(expr);
 532                 break;
 533         case EXPR_SYMBOL:
 534                 if (get_const_value(expr, &tmp_ret)) {
 535                         break;
 536                 }
 537                 tmp_ret = _get_implied_value(expr, undefined, implied);
 538                 break;
 539         case EXPR_SELECT:
 540         case EXPR_CONDITIONAL:
 541                 tmp_ret = handle_conditional(expr, undefined, implied);
 542                 break;
 543         default:
 544                 tmp_ret = _get_implied_value(expr, undefined, implied);
 545         }
 546         if (*undefined)
 547                 return bogus;
 548         return tmp_ret;
 549 }
 550
 551 /* returns 1 if it can get a value literal or else returns 0 */
 552 int get_value_sval(struct expression *expr, sval_t *val)
 553 {
 554         int undefined = 0;
 555
 556         *val = _get_value(expr, &undefined, NOTIMPLIED);
 557         if (undefined)
 558                 return 0;
 559         return 1;
 560 }
 561
 562 int get_implied_value_sval(struct expression *expr, sval_t *sval)
 563 {
 564         int undefined = 0;
 565
 566         *sval =  _get_value(expr, &undefined, IMPLIED);
 567         return !undefined;
 568 }
 569
 570 int get_implied_min_sval(struct expression *expr, sval_t *sval)
 571 {
 572         int undefined = 0;
 573
 574         *sval =  _get_value(expr, &undefined, IMPLIED_MIN);
 575         return !undefined;
 576 }
 577
 578 int get_implied_max_sval(struct expression *expr, sval_t *sval)
 579 {
 580         int undefined = 0;
 581
 582         *sval =  _get_value(expr, &undefined, IMPLIED_MAX);
 583         return !undefined;
 584 }
 585
 586 int get_fuzzy_min_sval(struct expression *expr, sval_t *sval)
 587 {
 588         int undefined = 0;
 589
 590         *sval =  _get_value(expr, &undefined, FUZZYMIN);
 591         return !undefined;
 592 }
 593
 594 int get_fuzzy_max_sval(struct expression *expr, sval_t *sval)
 595 {
 596         int undefined = 0;
 597
 598         *sval =  _get_value(expr, &undefined, FUZZYMAX);
 599         return !undefined;
 600 }
 601
 602 int get_absolute_min_sval(struct expression *expr, sval_t *sval)
 603 {
 604         int undefined = 0;
 605         struct symbol *type;
 606
 607         type = get_type(expr);
 608         *sval =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 609         if (undefined) {
 610                 *sval = sval_type_min(type);
 611                 return 1;
 612         }
 613
 614         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 615                 *sval = sval_type_min(type);
 616         return 1;
 617 }
 618
 619 int get_absolute_max_sval(struct expression *expr, sval_t *sval)
 620 {
 621         int undefined = 0;
 622
 623         *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
 624         if (undefined) {
 625                 sval->value = sval_type_max(sval->type).value;
 626                 return 1;
 627         }
 628
 629         if (sval_cmp(sval_type_max(sval->type), *sval) < 0)
 630                 sval->value = sval_type_max(sval->type).value;
 631         return 1;
 632 }
 633
 634 int known_condition_true(struct expression *expr)
 635 {
 636         sval_t tmp;
 637
 638         if (!expr)
 639                 return 0;
 640
 641         if (get_value_sval(expr, &tmp) && tmp.value)
 642                 return 1;
 643
 644         return 0;
 645 }
 646
 647 int known_condition_false(struct expression *expr)
 648 {
 649         if (!expr)
 650                 return 0;
 651
 652         if (is_zero(expr))
 653                 return 1;
 654
 655         if (expr->type == EXPR_CALL) {
 656                 if (sym_name_is("__builtin_constant_p", expr->fn))
 657                         return 1;
 658         }
 659         return 0;
 660 }
 661
 662 int implied_condition_true(struct expression *expr)
 663 {
 664         sval_t tmp;
 665
 666         if (!expr)
 667                 return 0;
 668
 669         if (known_condition_true(expr))
 670                 return 1;
 671         if (get_implied_value_sval(expr, &tmp) && tmp.value)
 672                 return 1;
 673
 674         if (expr->type == EXPR_POSTOP)
 675                 return implied_condition_true(expr->unop);
 676
 677         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 678                 return implied_not_equal(expr->unop, 1);
 679         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 680                 return implied_not_equal(expr->unop, -1);
 681
 682         expr = strip_expr(expr);
 683         switch (expr->type) {
 684         case EXPR_COMPARE:
 685                 if (do_comparison(expr) == 1)
 686                         return 1;
 687                 break;
 688         case EXPR_PREOP:
 689                 if (expr->op == '!') {
 690                         if (implied_condition_false(expr->unop))
 691                                 return 1;
 692                         break;
 693                 }
 694                 break;
 695         default:
 696                 if (implied_not_equal(expr, 0) == 1)
 697                         return 1;
 698                 break;
 699         }
 700         return 0;
 701 }
 702
 703 int implied_condition_false(struct expression *expr)
 704 {
 705         struct expression *tmp;
 706         sval_t sval;
 707
 708         if (!expr)
 709                 return 0;
 710
 711         if (known_condition_false(expr))
 712                 return 1;
 713
 714         switch (expr->type) {
 715         case EXPR_COMPARE:
 716                 if (do_comparison(expr) == 2)
 717                         return 1;
 718         case EXPR_PREOP:
 719                 if (expr->op == '!') {
 720                         if (implied_condition_true(expr->unop))
 721                                 return 1;
 722                         break;
 723                 }
 724                 tmp = strip_expr(expr);
 725                 if (tmp != expr)
 726                         return implied_condition_false(tmp);
 727                 break;
 728         default:
 729                 if (get_implied_value_sval(expr, &sval) && sval.value == 0)
 730                         return 1;
 731                 break;
 732         }
 733         return 0;
 734 }