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, 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, 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, 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         case ABSOLUTE_MAX: {
 453                 struct smatch_state *state;
 454                 struct data_range *range;
 455
 456                 if (get_implied_value_helper(expr, &ret, implied))
 457                         break;
 458
 459                 state = get_state_expr(absolute_id, expr);
 460                 if (!state || !state->data) {
 461                         *undefined = 1;
 462                         break;
 463                 }
 464                 range = state->data;
 465                 if (implied == ABSOLUTE_MAX)
 466                         ret.value = range->max;
 467                 else
 468                         ret.value = range->min;
 469                 break;
 470         }
 471         case FUZZYMAX:
 472                 if (!get_fuzzy_max_helper(expr, &ret))
 473                         *undefined = 1;
 474                 break;
 475         case FUZZYMIN:
 476                 if (!get_fuzzy_min_helper(expr, &ret))
 477                         *undefined = 1;
 478                 break;
 479         default:
 480                 *undefined = 1;
 481         }
 482         return ret;
 483 }
 484
 485 static int get_const_value(struct expression *expr, sval_t *sval)
 486 {
 487         struct symbol *sym;
 488         sval_t right;
 489
 490         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 491                 return 0;
 492         sym = expr->symbol;
 493         if (!(sym->ctype.modifiers & MOD_CONST))
 494                 return 0;
 495         if (get_value_sval(sym->initializer, &right)) {
 496                 *sval = sval_cast(right, expr);
 497                 return 1;
 498         }
 499         return 0;
 500 }
 501
 502 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 503 {
 504         sval_t tmp_ret;
 505
 506         if (!expr) {
 507                 *undefined = 1;
 508                 return bogus;
 509         }
 510         if (*undefined)
 511                 return bogus;
 512
 513         expr = strip_parens(expr);
 514
 515         switch (expr->type) {
 516         case EXPR_VALUE:
 517                 tmp_ret = sval_from_val(expr, expr->value);
 518                 break;
 519         case EXPR_PREOP:
 520                 tmp_ret = handle_preop(expr, undefined, implied);
 521                 break;
 522         case EXPR_POSTOP:
 523                 tmp_ret = _get_value(expr->unop, undefined, implied);
 524                 break;
 525         case EXPR_CAST:
 526         case EXPR_FORCE_CAST:
 527         case EXPR_IMPLIED_CAST:
 528                 tmp_ret = _get_value(expr->cast_expression, undefined, implied);
 529                 tmp_ret = sval_cast(tmp_ret, expr);
 530                 break;
 531         case EXPR_BINOP:
 532                 tmp_ret = handle_binop(expr, undefined, implied);
 533                 break;
 534         case EXPR_COMPARE:
 535                 tmp_ret = handle_comparison(expr, undefined, implied);
 536                 break;
 537         case EXPR_LOGICAL:
 538                 tmp_ret = handle_logical(expr, undefined, implied);
 539                 break;
 540         case EXPR_PTRSIZEOF:
 541         case EXPR_SIZEOF:
 542                 tmp_ret = sval_blank(expr);
 543                 tmp_ret.value = get_expression_value_nomod(expr);
 544                 break;
 545         case EXPR_SYMBOL:
 546                 if (get_const_value(expr, &tmp_ret)) {
 547                         break;
 548                 }
 549                 tmp_ret = _get_implied_value(expr, undefined, implied);
 550                 break;
 551         case EXPR_SELECT:
 552         case EXPR_CONDITIONAL:
 553                 tmp_ret = handle_conditional(expr, undefined, implied);
 554                 break;
 555         default:
 556                 tmp_ret = _get_implied_value(expr, undefined, implied);
 557         }
 558         if (*undefined)
 559                 return bogus;
 560         return tmp_ret;
 561 }
 562
 563 /* returns 1 if it can get a value literal or else returns 0 */
 564 int get_value_sval(struct expression *expr, sval_t *val)
 565 {
 566         int undefined = 0;
 567
 568         *val = _get_value(expr, &undefined, NOTIMPLIED);
 569         if (undefined)
 570                 return 0;
 571         return 1;
 572 }
 573
 574 int get_implied_value_sval(struct expression *expr, sval_t *sval)
 575 {
 576         int undefined = 0;
 577
 578         *sval =  _get_value(expr, &undefined, IMPLIED);
 579         return !undefined;
 580 }
 581
 582 int get_implied_min_sval(struct expression *expr, sval_t *sval)
 583 {
 584         int undefined = 0;
 585
 586         *sval =  _get_value(expr, &undefined, IMPLIED_MIN);
 587         return !undefined;
 588 }
 589
 590 int get_implied_max_sval(struct expression *expr, sval_t *sval)
 591 {
 592         int undefined = 0;
 593
 594         *sval =  _get_value(expr, &undefined, IMPLIED_MAX);
 595         return !undefined;
 596 }
 597
 598 int get_fuzzy_min_sval(struct expression *expr, sval_t *sval)
 599 {
 600         int undefined = 0;
 601
 602         *sval =  _get_value(expr, &undefined, FUZZYMIN);
 603         return !undefined;
 604 }
 605
 606 int get_fuzzy_max_sval(struct expression *expr, sval_t *sval)
 607 {
 608         int undefined = 0;
 609
 610         *sval =  _get_value(expr, &undefined, FUZZYMAX);
 611         return !undefined;
 612 }
 613
 614 int get_absolute_min_sval(struct expression *expr, sval_t *sval)
 615 {
 616         int undefined = 0;
 617         struct symbol *type;
 618
 619         type = get_type(expr);
 620         *sval =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 621         if (undefined) {
 622                 *sval = sval_type_min(type);
 623                 return 1;
 624         }
 625
 626         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 627                 *sval = sval_type_min(type);
 628         return 1;
 629 }
 630
 631 int get_absolute_max_sval(struct expression *expr, sval_t *sval)
 632 {
 633         int undefined = 0;
 634
 635         *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
 636         if (undefined) {
 637                 sval->value = sval_type_max(sval->type).value;
 638                 return 1;
 639         }
 640
 641         if (sval_cmp(sval_type_max(sval->type), *sval) < 0)
 642                 sval->value = sval_type_max(sval->type).value;
 643         return 1;
 644 }
 645
 646 int known_condition_true(struct expression *expr)
 647 {
 648         sval_t tmp;
 649
 650         if (!expr)
 651                 return 0;
 652
 653         if (get_value_sval(expr, &tmp) && tmp.value)
 654                 return 1;
 655
 656         return 0;
 657 }
 658
 659 int known_condition_false(struct expression *expr)
 660 {
 661         if (!expr)
 662                 return 0;
 663
 664         if (is_zero(expr))
 665                 return 1;
 666
 667         if (expr->type == EXPR_CALL) {
 668                 if (sym_name_is("__builtin_constant_p", expr->fn))
 669                         return 1;
 670         }
 671         return 0;
 672 }
 673
 674 int implied_condition_true(struct expression *expr)
 675 {
 676         sval_t tmp;
 677
 678         if (!expr)
 679                 return 0;
 680
 681         if (known_condition_true(expr))
 682                 return 1;
 683         if (get_implied_value_sval(expr, &tmp) && tmp.value)
 684                 return 1;
 685
 686         if (expr->type == EXPR_POSTOP)
 687                 return implied_condition_true(expr->unop);
 688
 689         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 690                 return implied_not_equal(expr->unop, 1);
 691         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 692                 return implied_not_equal(expr->unop, -1);
 693
 694         expr = strip_expr(expr);
 695         switch (expr->type) {
 696         case EXPR_COMPARE:
 697                 if (do_comparison(expr) == 1)
 698                         return 1;
 699                 break;
 700         case EXPR_PREOP:
 701                 if (expr->op == '!') {
 702                         if (implied_condition_false(expr->unop))
 703                                 return 1;
 704                         break;
 705                 }
 706                 break;
 707         default:
 708                 if (implied_not_equal(expr, 0) == 1)
 709                         return 1;
 710                 break;
 711         }
 712         return 0;
 713 }
 714
 715 int implied_condition_false(struct expression *expr)
 716 {
 717         struct expression *tmp;
 718         sval_t sval;
 719
 720         if (!expr)
 721                 return 0;
 722
 723         if (known_condition_false(expr))
 724                 return 1;
 725
 726         switch (expr->type) {
 727         case EXPR_COMPARE:
 728                 if (do_comparison(expr) == 2)
 729                         return 1;
 730         case EXPR_PREOP:
 731                 if (expr->op == '!') {
 732                         if (implied_condition_true(expr->unop))
 733                                 return 1;
 734                         break;
 735                 }
 736                 tmp = strip_expr(expr);
 737                 if (tmp != expr)
 738                         return implied_condition_false(tmp);
 739                 break;
 740         default:
 741                 if (get_implied_value_sval(expr, &sval) && sval.value == 0)
 742                         return 1;
 743                 break;
 744         }
 745         return 0;
 746 }