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 "symbol.h"
  11 #include "smatch.h"
  12 #include "smatch_slist.h"
  13 #include "smatch_extra.h"
  14
  15 static struct range_list *_get_rl(struct expression *expr, int implied);
  16 static sval_t _get_value(struct expression *expr, int *undefined, int implied);
  17 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied);
  18
  19 #define BOGUS 12345
  20
  21 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  22 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  23 static sval_t bogus = {.type = &int_ctype, {.value = BOGUS} };
  24
  25 enum {
  26         EXACT,
  27         IMPLIED,
  28         IMPLIED_MIN,
  29         IMPLIED_MAX,
  30         FUZZY_MAX,
  31         FUZZY_MIN,
  32         ABSOLUTE_MIN,
  33         ABSOLUTE_MAX,
  34         HARD_MAX,
  35 };
  36
  37 enum {
  38         RL_EXACT,
  39         RL_HARD,
  40         RL_FUZZY,
  41         RL_IMPLIED,
  42         RL_ABSOLUTE
  43 };
  44
  45 static int implied_to_rl_enum(int implied)
  46 {
  47         switch (implied) {
  48         case EXACT:
  49                 return RL_EXACT;
  50         case HARD_MAX:
  51                 return RL_HARD;
  52         case FUZZY_MAX:
  53         case FUZZY_MIN:
  54                 return RL_FUZZY;
  55         case IMPLIED:
  56         case IMPLIED_MIN:
  57         case IMPLIED_MAX:
  58                 return RL_IMPLIED;
  59         case ABSOLUTE_MIN:
  60         case ABSOLUTE_MAX:
  61                 return RL_ABSOLUTE;
  62         }
  63         return 0;
  64 }
  65
  66 static int opposite_implied(int implied)
  67 {
  68         if (implied == IMPLIED_MIN)
  69                 return IMPLIED_MAX;
  70         if (implied == IMPLIED_MAX)
  71                 return IMPLIED_MIN;
  72         if (implied == FUZZY_MIN)
  73                 return FUZZY_MAX;
  74         if (implied == FUZZY_MAX)
  75                 return FUZZY_MIN;
  76         if (implied == ABSOLUTE_MIN)
  77                 return ABSOLUTE_MAX;
  78         if (implied == ABSOLUTE_MAX)
  79                 return ABSOLUTE_MIN;
  80         if (implied == HARD_MAX)  /* we don't have a hard min.  */
  81                 return EXACT;
  82
  83         return implied;
  84 }
  85
  86 static int last_stmt_sval(struct statement *stmt, sval_t *sval)
  87 {
  88         struct expression *expr;
  89
  90         if (!stmt)
  91                 return 0;
  92
  93         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  94         if (stmt->type != STMT_EXPRESSION)
  95                 return 0;
  96         expr = stmt->expression;
  97         if (!get_value(expr, sval))
  98                 return 0;
  99         return 1;
 100 }
 101
 102 static sval_t handle_expression_statement(struct expression *expr, int *undefined, int implied)
 103 {
 104         struct statement *stmt;
 105         sval_t ret;
 106
 107         stmt = get_expression_statement(expr);
 108         if (!last_stmt_sval(stmt, &ret)) {
 109                 *undefined = 1;
 110                 ret = bogus;
 111         }
 112
 113         return ret;
 114 }
 115
 116 static sval_t handle_ampersand(int *undefined, int implied)
 117 {
 118         sval_t ret;
 119
 120         ret.type = &ptr_ctype;
 121         ret.value = BOGUS;
 122
 123         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 124                 return valid_ptr_min_sval;
 125         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 126                 return valid_ptr_max_sval;
 127
 128         *undefined = 1;
 129         return ret;
 130 }
 131
 132 static sval_t handle_negate(struct expression *expr, int *undefined, int implied)
 133 {
 134         sval_t ret;
 135
 136         ret = sval_blank(expr->unop);
 137
 138         if (known_condition_true(expr->unop)) {
 139                 ret.value = 0;
 140                 return ret;
 141         }
 142
 143         if (implied == EXACT) {
 144                 *undefined = 1;
 145                 return bogus;
 146         }
 147
 148         if (implied_condition_true(expr->unop)) {
 149                 ret.value = 0;
 150                 return ret;
 151         }
 152         if (implied_condition_false(expr->unop)) {
 153                 ret.value = 1;
 154                 return ret;
 155         }
 156         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN) {
 157                 ret.value = 0;
 158                 return ret;
 159         }
 160         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX) {
 161                 ret.value = 1;
 162                 return ret;
 163         }
 164         *undefined = 1;
 165         return bogus;
 166 }
 167
 168 static sval_t handle_preop(struct expression *expr, int *undefined, int implied)
 169 {
 170         sval_t ret;
 171
 172         switch (expr->op) {
 173         case '&':
 174                 ret = handle_ampersand(undefined, implied);
 175                 break;
 176         case '!':
 177                 ret = handle_negate(expr, undefined, implied);
 178                 break;
 179         case '~':
 180                 ret = _get_value(expr->unop, undefined, implied);
 181                 ret = sval_preop(ret, '~');
 182                 ret = sval_cast(get_type(expr->unop), ret);
 183                 break;
 184         case '-':
 185                 ret = _get_value(expr->unop, undefined, implied);
 186                 ret = sval_preop(ret, '-');
 187                 break;
 188         case '*':
 189                 ret = _get_implied_value(expr, undefined, implied);
 190                 break;
 191         case '(':
 192                 ret = handle_expression_statement(expr, undefined, implied);
 193                 break;
 194         default:
 195                 *undefined = 1;
 196                 ret = sval_blank(expr);
 197         }
 198         ret = sval_cast(get_type(expr), ret);
 199         return ret;
 200 }
 201
 202 static sval_t handle_divide(struct expression *expr, int *undefined, int implied)
 203 {
 204         sval_t left, right;
 205
 206         left = _get_value(expr->left, undefined, implied);
 207         right = _get_value(expr->right, undefined, opposite_implied(implied));
 208
 209         if (right.value == 0) {
 210                 *undefined = 1;
 211                 return bogus;
 212         }
 213
 214         return sval_binop(left, '/', right);
 215 }
 216
 217 static sval_t handle_subtract(struct expression *expr, int *undefined, int implied)
 218 {
 219         struct symbol *type;
 220         sval_t left, right, ret;
 221         int left_undefined = 0;
 222         int right_undefined = 0;
 223         int known_but_negative = 0;
 224         int comparison;
 225
 226         left = _get_value(expr->left, &left_undefined, implied);
 227         right = _get_value(expr->right, &right_undefined, opposite_implied(implied));
 228
 229         if (!left_undefined && !right_undefined) {
 230                 ret = sval_binop(left, '-', right);
 231                 if (sval_is_negative(ret))
 232                         known_but_negative = 1;
 233                 else
 234                         return ret;  /* best case scenario */
 235         }
 236
 237         comparison = get_comparison(expr->left, expr->right);
 238         if (!comparison)
 239                 goto bogus;
 240
 241         type = get_type(expr);
 242
 243         switch (comparison) {
 244         case '>':
 245         case SPECIAL_UNSIGNED_GT:
 246                 switch (implied) {
 247                 case IMPLIED_MIN:
 248                 case FUZZY_MIN:
 249                 case ABSOLUTE_MIN:
 250                         return sval_type_val(type, 1);
 251                 case IMPLIED_MAX:
 252                 case FUZZY_MAX:
 253                 case ABSOLUTE_MAX:
 254                         return _get_value(expr->left, undefined, implied);
 255                 }
 256                 break;
 257         case SPECIAL_GTE:
 258         case SPECIAL_UNSIGNED_GTE:
 259                 switch (implied) {
 260                 case IMPLIED_MIN:
 261                 case FUZZY_MIN:
 262                 case ABSOLUTE_MIN:
 263                         return sval_type_val(type, 0);
 264                 case IMPLIED_MAX:
 265                 case FUZZY_MAX:
 266                 case ABSOLUTE_MAX:
 267                         return _get_value(expr->left, undefined, implied);
 268                 }
 269                 break;
 270         }
 271
 272         if (known_but_negative)
 273                 return ret;
 274
 275 bogus:
 276         *undefined = 1;
 277         return bogus;
 278 }
 279
 280 static sval_t handle_mod(struct expression *expr, int *undefined, int implied)
 281 {
 282         sval_t left, right;
 283
 284         /* if we can't figure out the right side it's probably hopeless */
 285         right = _get_value(expr->right, undefined, implied);
 286         if (*undefined || right.value == 0) {
 287                 *undefined = 1;
 288                 return bogus;
 289         }
 290
 291         switch (implied) {
 292         case EXACT:
 293         case IMPLIED:
 294                 left = _get_value(expr->left, undefined, implied);
 295                 if (!*undefined)
 296                         return sval_binop(left, '%', right);
 297                 return bogus;
 298         case IMPLIED_MIN:
 299         case FUZZY_MIN:
 300         case ABSOLUTE_MIN:
 301                 *undefined = 0;
 302                 return sval_type_val(get_type(expr), 0);
 303         case IMPLIED_MAX:
 304         case FUZZY_MAX:
 305         case ABSOLUTE_MAX:
 306                 *undefined = 0;
 307                 right = sval_cast(get_type(expr), right);
 308                 right.value--;
 309                 return right;
 310         }
 311         return bogus;
 312 }
 313
 314 static sval_t handle_binop(struct expression *expr, int *undefined, int implied)
 315 {
 316         struct symbol *type;
 317         sval_t left, right;
 318         sval_t ret = {.type = &int_ctype, {.value = 123456} };
 319         int local_undef = 0;
 320
 321         switch (expr->op) {
 322         case '%':
 323                 return handle_mod(expr, undefined, implied);
 324         case '&':
 325                 if (implied == HARD_MAX) {
 326                         *undefined = 1;
 327                         return bogus;
 328                 }
 329                 left = _get_value(expr->left, &local_undef, implied);
 330                 if (local_undef) {
 331                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 332                                 ret = sval_blank(expr->left);
 333                                 ret.value = 0;
 334                                 return ret;
 335                         }
 336                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 337                                 *undefined = 1;
 338                         if (!get_absolute_max(expr->left, &left))
 339                                 *undefined = 1;
 340                 }
 341                 right = _get_value(expr->right, undefined, implied);
 342                 if (*undefined)
 343                         return bogus;
 344                 return sval_binop(left, '&', right);
 345
 346         case SPECIAL_RIGHTSHIFT:
 347                 if (implied == HARD_MAX) {
 348                         *undefined = 1;
 349                         return bogus;
 350                 }
 351                 left = _get_value(expr->left, &local_undef, implied);
 352                 if (local_undef) {
 353                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 354                                 ret = sval_blank(expr->left);
 355                                 ret.value = 0;
 356                                 return ret;
 357                         }
 358                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 359                                 *undefined = 1;
 360                         if (!get_absolute_max(expr->left, &left))
 361                                 *undefined = 1;
 362                 }
 363                 right = _get_value(expr->right, undefined, implied);
 364                 if (*undefined)
 365                         return bogus;
 366                 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 367         case '-':
 368                 return handle_subtract(expr, undefined, implied);
 369         }
 370
 371         left = _get_value(expr->left, undefined, implied);
 372         right = _get_value(expr->right, undefined, implied);
 373
 374         if (*undefined)
 375                 return bogus;
 376
 377         type = get_type(expr);
 378         left = sval_cast(type, left);
 379         right = sval_cast(type, right);
 380
 381         switch (implied) {
 382         case IMPLIED_MAX:
 383         case ABSOLUTE_MAX:
 384                 if (sval_binop_overflows(left, expr->op, right))
 385                         return sval_type_max(get_type(expr));
 386                 break;
 387         case HARD_MAX:
 388         case FUZZY_MAX:
 389                 if (sval_binop_overflows(left, expr->op, right)) {
 390                         *undefined = 1;
 391                         return bogus;
 392                 }
 393         }
 394
 395         switch (expr->op) {
 396         case '/':
 397                 return handle_divide(expr, undefined, implied);
 398         case '%':
 399                 if (right.value == 0) {
 400                         *undefined = 1;
 401                         return bogus;
 402                 } else {
 403                         return sval_binop(left, '%', right);
 404                 }
 405         default:
 406                 ret = sval_binop(left, expr->op, right);
 407         }
 408         return ret;
 409 }
 410
 411 static int do_comparison(struct expression *expr)
 412 {
 413         struct range_list *left_ranges = NULL;
 414         struct range_list *right_ranges = NULL;
 415         int poss_true, poss_false;
 416         struct symbol *type;
 417
 418         type = get_type(expr);
 419
 420         get_implied_rl(expr->left, &left_ranges);
 421         get_implied_rl(expr->right, &right_ranges);
 422         left_ranges = cast_rl(type, left_ranges);
 423         right_ranges = cast_rl(type, right_ranges);
 424
 425         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 426         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 427
 428         free_rl(&left_ranges);
 429         free_rl(&right_ranges);
 430
 431         if (!poss_true && !poss_false)
 432                 return 0;
 433         if (poss_true && !poss_false)
 434                 return 1;
 435         if (!poss_true && poss_false)
 436                 return 2;
 437         return 3;
 438 }
 439
 440 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
 441 {
 442         sval_t left, right;
 443         int res;
 444
 445         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 446                 struct data_range tmp_left, tmp_right;
 447
 448                 tmp_left.min = left;
 449                 tmp_left.max = left;
 450                 tmp_right.min = right;
 451                 tmp_right.max = right;
 452                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 453                         return one;
 454                 return zero;
 455         }
 456
 457         if (implied == EXACT) {
 458                 *undefined = 1;
 459                 return bogus;
 460         }
 461
 462         res = do_comparison(expr);
 463         if (res == 1)
 464                 return one;
 465         if (res == 2)
 466                 return zero;
 467
 468         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 469                 return zero;
 470         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 471                 return one;
 472
 473         *undefined = 1;
 474         return bogus;
 475 }
 476
 477 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
 478 {
 479         sval_t left, right;
 480         int left_known = 0;
 481         int right_known = 0;
 482
 483         if (implied == EXACT) {
 484                 if (get_value(expr->left, &left))
 485                         left_known = 1;
 486                 if (get_value(expr->right, &right))
 487                         right_known = 1;
 488         } else {
 489                 if (get_implied_value(expr->left, &left))
 490                         left_known = 1;
 491                 if (get_implied_value(expr->right, &right))
 492                         right_known = 1;
 493         }
 494
 495         switch (expr->op) {
 496         case SPECIAL_LOGICAL_OR:
 497                 if (left_known && left.value)
 498                         return one;
 499                 if (right_known && right.value)
 500                         return one;
 501                 if (left_known && right_known)
 502                         return zero;
 503                 break;
 504         case SPECIAL_LOGICAL_AND:
 505                 if (left_known && right_known) {
 506                         if (left.value && right.value)
 507                                 return one;
 508                         return zero;
 509                 }
 510                 break;
 511         default:
 512                 *undefined = 1;
 513                 return bogus;
 514         }
 515
 516         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 517                 return zero;
 518         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 519                 return one;
 520
 521         *undefined = 1;
 522         return bogus;
 523 }
 524
 525 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 526 {
 527         if (known_condition_true(expr->conditional))
 528                 return _get_value(expr->cond_true, undefined, implied);
 529         if (known_condition_false(expr->conditional))
 530                 return _get_value(expr->cond_false, undefined, implied);
 531
 532         if (implied == EXACT) {
 533                 *undefined = 1;
 534                 return bogus;
 535         }
 536
 537         if (implied_condition_true(expr->conditional))
 538                 return _get_value(expr->cond_true, undefined, implied);
 539         if (implied_condition_false(expr->conditional))
 540                 return _get_value(expr->cond_false, undefined, implied);
 541
 542         *undefined = 1;
 543         return bogus;
 544 }
 545
 546 static int get_local_value(struct expression *expr, sval_t *sval, int implied)
 547 {
 548         switch (implied) {
 549         case EXACT:
 550         case IMPLIED:
 551                 return 0;
 552         case IMPLIED_MIN:
 553         case FUZZY_MIN:
 554         case ABSOLUTE_MIN:
 555                 return get_local_min_helper(expr, sval);
 556         case ABSOLUTE_MAX:
 557         case HARD_MAX:
 558         case IMPLIED_MAX:
 559         case FUZZY_MAX:
 560                 return get_local_max_helper(expr, sval);
 561         }
 562         return 0;
 563 }
 564
 565 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 566 {
 567         struct smatch_state *state;
 568         struct symbol *sym;
 569         char *name;
 570
 571         /* fixme: this should return the casted value */
 572
 573         expr = strip_expr(expr);
 574
 575         if (get_value(expr, sval))
 576                 return 1;
 577
 578         name = expr_to_var_sym(expr, &sym);
 579         if (!name)
 580                 return 0;
 581         *sval = sval_blank(expr);
 582         state = get_state(SMATCH_EXTRA, name, sym);
 583         free_string(name);
 584         if (!state || !state->data)
 585                 return get_local_value(expr, sval, implied);
 586         if (implied == IMPLIED) {
 587                 if (estate_get_single_value(state, sval))
 588                         return 1;
 589                 return 0;
 590         }
 591         if (implied == HARD_MAX) {
 592                 if (estate_get_hard_max(state, sval))
 593                         return 1;
 594                 return 0;
 595         }
 596         if (implied == IMPLIED_MAX || implied == ABSOLUTE_MAX) {
 597                 *sval = estate_max(state);
 598                 return 1;
 599         }
 600         *sval = estate_min(state);
 601         return 1;
 602 }
 603
 604 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 605 {
 606         struct sm_state *sm;
 607         struct sm_state *tmp;
 608         sval_t sval;
 609
 610         if (get_hard_max(expr, &sval)) {
 611                 *max = sval;
 612                 return 1;
 613         }
 614
 615         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 616         if (!sm)
 617                 return 0;
 618
 619         sval = sval_type_min(estate_type(sm->state));
 620         FOR_EACH_PTR(sm->possible, tmp) {
 621                 sval_t new_min;
 622
 623                 new_min = estate_min(tmp->state);
 624                 if (sval_cmp(new_min, sval) > 0)
 625                         sval = new_min;
 626         } END_FOR_EACH_PTR(tmp);
 627
 628         if (sval_is_min(sval))
 629                 return 0;
 630         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 631                 return 0;
 632
 633         *max = sval_cast(get_type(expr), sval);
 634         return 1;
 635 }
 636
 637 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 638 {
 639         struct sm_state *sm;
 640         struct sm_state *tmp;
 641         sval_t sval;
 642
 643         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 644         if (!sm)
 645                 return 0;
 646
 647         if (!sval_is_min(estate_min(sm->state))) {
 648                 *min = estate_min(sm->state);
 649                 return 1;
 650         }
 651
 652         sval = sval_type_max(estate_type(sm->state));
 653         FOR_EACH_PTR(sm->possible, tmp) {
 654                 sval_t new_max;
 655
 656                 new_max = estate_max(tmp->state);
 657                 if (sval_cmp(new_max, sval) < 0)
 658                         sval = new_max;
 659         } END_FOR_EACH_PTR(tmp);
 660
 661         if (sval_is_max(sval))
 662                 return 0;
 663         *min = sval_cast(get_type(expr), sval);
 664         return 1;
 665 }
 666
 667 static int get_const_value(struct expression *expr, sval_t *sval)
 668 {
 669         struct symbol *sym;
 670         sval_t right;
 671
 672         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 673                 return 0;
 674         sym = expr->symbol;
 675         if (!(sym->ctype.modifiers & MOD_CONST))
 676                 return 0;
 677         if (get_value(sym->initializer, &right)) {
 678                 *sval = sval_cast(get_type(expr), right);
 679                 return 1;
 680         }
 681         return 0;
 682 }
 683
 684 static struct range_list *handle_variable(struct expression *expr, int implied)
 685 {
 686         struct smatch_state *state;
 687         struct range_list *rl;
 688         sval_t sval, min, max;
 689
 690         if (get_const_value(expr, &sval))
 691                 return alloc_rl(sval, sval);
 692
 693         switch (implied_to_rl_enum(implied)) {
 694         case RL_EXACT:
 695                 return NULL;
 696         case RL_HARD:
 697         case RL_IMPLIED:
 698         case RL_ABSOLUTE:
 699                 state = get_state_expr(SMATCH_EXTRA, expr);
 700                 if (!state || !state->data) {
 701                         if (get_local_rl(expr, &rl))
 702                                 return rl;
 703                         return NULL;
 704                 }
 705                 if (implied == HARD_MAX && !estate_has_hard_max(state))
 706                         return NULL;
 707                 return estate_rl(state);
 708         case RL_FUZZY:
 709                 if (!get_fuzzy_min_helper(expr, &min))
 710                         min = sval_type_min(get_type(expr));
 711                 if (!get_fuzzy_max_helper(expr, &max))
 712                         return NULL;
 713                 return alloc_rl(min, max);
 714         }
 715         return NULL;
 716 }
 717
 718 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 719 {
 720         sval_t ret;
 721
 722         ret = sval_blank(expr);
 723
 724         switch (implied) {
 725         case IMPLIED:
 726         case IMPLIED_MAX:
 727         case IMPLIED_MIN:
 728         case HARD_MAX:
 729         case ABSOLUTE_MIN:
 730         case ABSOLUTE_MAX:
 731                 if (!get_implied_value_helper(expr, &ret, implied))
 732                         *undefined = 1;
 733                 break;
 734         case FUZZY_MAX:
 735                 if (!get_fuzzy_max_helper(expr, &ret))
 736                         *undefined = 1;
 737                 break;
 738         case FUZZY_MIN:
 739                 if (!get_fuzzy_min_helper(expr, &ret))
 740                         *undefined = 1;
 741                 break;
 742         default:
 743                 *undefined = 1;
 744         }
 745         return ret;
 746 }
 747
 748 static sval_t handle_sizeof(struct expression *expr)
 749 {
 750         struct symbol *sym;
 751         sval_t ret;
 752
 753         ret = sval_blank(expr);
 754         sym = expr->cast_type;
 755         if (!sym) {
 756                 sym = evaluate_expression(expr->cast_expression);
 757                 /*
 758                  * Expressions of restricted types will possibly get
 759                  * promoted - check that here
 760                  */
 761                 if (is_restricted_type(sym)) {
 762                         if (sym->bit_size < bits_in_int)
 763                                 sym = &int_ctype;
 764                 } else if (is_fouled_type(sym)) {
 765                         sym = &int_ctype;
 766                 }
 767         }
 768         examine_symbol_type(sym);
 769
 770         ret.type = size_t_ctype;
 771         if (sym->bit_size <= 0) /* sizeof(void) */ {
 772                 if (get_real_base_type(sym) == &void_ctype)
 773                         ret.value = 1;
 774                 else
 775                         ret.value = 0;
 776         } else
 777                 ret.value = bits_to_bytes(sym->bit_size);
 778
 779         return ret;
 780 }
 781
 782 static struct range_list *handle_call_rl(struct expression *expr, int implied)
 783 {
 784         struct range_list *rl;
 785
 786         if (implied == EXACT)
 787                 return NULL;
 788
 789         if (get_implied_return(expr, &rl))
 790                 return rl;
 791         return db_return_vals(expr);
 792 }
 793
 794 static sval_t handle_call(struct expression *expr, int *undefined, int implied)
 795 {
 796         struct range_list *rl;
 797
 798         if (!get_implied_rl(expr, &rl)) {
 799                 *undefined = 1;
 800                 return bogus;
 801         }
 802
 803         switch (implied) {
 804         case IMPLIED:
 805                 if (sval_cmp(rl_min(rl), rl_max(rl)) == 0)
 806                         return rl_min(rl);
 807                 *undefined = 1;
 808                 return bogus;
 809         case IMPLIED_MIN:
 810         case ABSOLUTE_MIN:
 811                 return rl_min(rl);
 812
 813         case IMPLIED_MAX:
 814         case HARD_MAX:
 815         case ABSOLUTE_MAX:
 816                 return rl_max(rl);
 817         default:
 818                 *undefined = 1;
 819                 return bogus;
 820         }
 821
 822 }
 823
 824 static struct range_list *_get_rl(struct expression *expr, int implied)
 825 {
 826         struct range_list *rl;
 827         struct symbol *type;
 828         int undefined;
 829         sval_t sval;
 830
 831         expr = strip_parens(expr);
 832         if (!expr)
 833                 return NULL;
 834         type = get_type(expr);
 835
 836         undefined = 0;
 837         switch (expr->type) {
 838         case EXPR_VALUE:
 839                 sval = sval_from_val(expr, expr->value);
 840                 break;
 841         case EXPR_PREOP:
 842                 sval = handle_preop(expr, &undefined, implied);
 843                 break;
 844         case EXPR_POSTOP:
 845                 sval = _get_value(expr->unop, &undefined, implied);
 846                 break;
 847         case EXPR_CAST:
 848         case EXPR_FORCE_CAST:
 849         case EXPR_IMPLIED_CAST:
 850                 rl = _get_rl(expr->cast_expression, implied);
 851                 if (!rl)
 852                         undefined = 1;
 853                 else
 854                         return cast_rl(type, rl);
 855                 break;
 856         case EXPR_BINOP:
 857                 sval = handle_binop(expr, &undefined, implied);
 858                 break;
 859         case EXPR_COMPARE:
 860                 sval = handle_comparison(expr, &undefined, implied);
 861                 break;
 862         case EXPR_LOGICAL:
 863                 sval = handle_logical(expr, &undefined, implied);
 864                 break;
 865         case EXPR_PTRSIZEOF:
 866         case EXPR_SIZEOF:
 867                 sval = handle_sizeof(expr);
 868                 break;
 869         case EXPR_SELECT:
 870         case EXPR_CONDITIONAL:
 871                 sval = handle_conditional(expr, &undefined, implied);
 872                 break;
 873         case EXPR_CALL:
 874                 rl = handle_call_rl(expr, implied);
 875                 if (rl)
 876                         return rl;
 877                 else
 878                         undefined = 1;
 879                 break;
 880         default:
 881                 rl = handle_variable(expr, implied);
 882                 if (rl)
 883                         return rl;
 884                 else
 885                         undefined = 1;
 886         }
 887
 888         if (undefined && type &&
 889             (implied == ABSOLUTE_MAX || implied == ABSOLUTE_MIN))
 890                 return alloc_whole_rl(type);
 891         if (undefined)
 892                 return NULL;
 893         rl = alloc_rl(sval, sval);
 894         return rl;
 895 }
 896
 897 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 898 {
 899         struct symbol *type;
 900         sval_t ret;
 901
 902         if (!expr) {
 903                 *undefined = 1;
 904                 return bogus;
 905         }
 906         if (*undefined)
 907                 return bogus;
 908
 909         expr = strip_parens(expr);
 910         type = get_type(expr);
 911
 912         switch (expr->type) {
 913         case EXPR_VALUE:
 914                 ret = sval_from_val(expr, expr->value);
 915                 break;
 916         case EXPR_PREOP:
 917                 ret = handle_preop(expr, undefined, implied);
 918                 break;
 919         case EXPR_POSTOP:
 920                 ret = _get_value(expr->unop, undefined, implied);
 921                 break;
 922         case EXPR_CAST:
 923         case EXPR_FORCE_CAST:
 924         case EXPR_IMPLIED_CAST:
 925                 ret = _get_value(expr->cast_expression, undefined, implied);
 926                 ret = sval_cast(type, ret);
 927                 break;
 928         case EXPR_BINOP:
 929                 ret = handle_binop(expr, undefined, implied);
 930                 break;
 931         case EXPR_COMPARE:
 932                 ret = handle_comparison(expr, undefined, implied);
 933                 break;
 934         case EXPR_LOGICAL:
 935                 ret = handle_logical(expr, undefined, implied);
 936                 break;
 937         case EXPR_PTRSIZEOF:
 938         case EXPR_SIZEOF:
 939                 ret = handle_sizeof(expr);
 940                 break;
 941         case EXPR_SYMBOL:
 942                 if (get_const_value(expr, &ret)) {
 943                         break;
 944                 }
 945                 ret = _get_implied_value(expr, undefined, implied);
 946                 break;
 947         case EXPR_SELECT:
 948         case EXPR_CONDITIONAL:
 949                 ret = handle_conditional(expr, undefined, implied);
 950                 break;
 951         case EXPR_CALL:
 952                 ret = handle_call(expr, undefined, implied);
 953                 break;
 954         default:
 955                 ret = _get_implied_value(expr, undefined, implied);
 956         }
 957
 958         if (*undefined)
 959                 return bogus;
 960         return ret;
 961 }
 962
 963 /* returns 1 if it can get a value literal or else returns 0 */
 964 int get_value(struct expression *expr, sval_t *sval)
 965 {
 966         struct range_list *rl;
 967
 968         rl = _get_rl(expr, EXACT);
 969         if (!rl_to_sval(rl, sval))
 970                 return 0;
 971         return 1;
 972 }
 973
 974 int get_implied_value(struct expression *expr, sval_t *sval)
 975 {
 976         struct range_list *rl;
 977
 978         rl =  _get_rl(expr, IMPLIED);
 979         if (!rl_to_sval(rl, sval))
 980                 return 0;
 981         return 1;
 982 }
 983
 984 int get_implied_min(struct expression *expr, sval_t *sval)
 985 {
 986         struct range_list *rl;
 987
 988         rl =  _get_rl(expr, IMPLIED_MIN);
 989         if (!rl)
 990                 return 0;
 991         *sval = rl_min(rl);
 992         return 1;
 993 }
 994
 995 int get_implied_max(struct expression *expr, sval_t *sval)
 996 {
 997         struct range_list *rl;
 998
 999         rl =  _get_rl(expr, IMPLIED_MAX);
1000         if (!rl)
1001                 return 0;
1002         *sval = rl_max(rl);
1003         return 1;
1004 }
1005
1006 int get_implied_rl(struct expression *expr, struct range_list **rl)
1007 {
1008         sval_t sval;
1009         struct smatch_state *state;
1010         sval_t min, max;
1011         int min_known = 0;
1012         int max_known = 0;
1013
1014         *rl = NULL;
1015
1016         expr = strip_parens(expr);
1017         if (!expr)
1018                 return 0;
1019
1020         state = get_state_expr(SMATCH_EXTRA, expr);
1021         if (state) {
1022                 *rl = clone_rl(estate_rl(state));
1023                 return 1;
1024         }
1025
1026         if (expr->type == EXPR_CALL) {
1027                 if (get_implied_return(expr, rl))
1028                         return 1;
1029                 *rl = db_return_vals(expr);
1030                 if (*rl)
1031                         return 1;
1032                 return 0;
1033         }
1034
1035         if (get_implied_value(expr, &sval)) {
1036                 add_range(rl, sval, sval);
1037                 return 1;
1038         }
1039
1040         if (get_local_rl(expr, rl))
1041                 return 1;
1042
1043         min_known = get_implied_min(expr, &min);
1044         max_known = get_implied_max(expr, &max);
1045         if (!min_known && !max_known)
1046                 return 0;
1047         if (!min_known)
1048                 get_absolute_min(expr, &min);
1049         if (!max_known)
1050                 get_absolute_max(expr, &max);
1051
1052         *rl = alloc_rl(min, max);
1053         return 1;
1054 }
1055
1056 int get_hard_max(struct expression *expr, sval_t *sval)
1057 {
1058         struct range_list *rl;
1059
1060         rl =  _get_rl(expr, HARD_MAX);
1061         if (!rl)
1062                 return 0;
1063         *sval = rl_max(rl);
1064         return 1;
1065 }
1066
1067 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1068 {
1069         struct range_list *rl;
1070
1071         rl =  _get_rl(expr, FUZZY_MIN);
1072         if (!rl)
1073                 return 0;
1074         *sval = rl_min(rl);
1075         return 1;
1076 }
1077
1078 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1079 {
1080         struct range_list *rl;
1081         sval_t max;
1082
1083         rl =  _get_rl(expr, FUZZY_MAX);
1084         if (!rl)
1085                 return 0;
1086         max = rl_max(rl);
1087         if (max.uvalue > INT_MAX - 10000)
1088                 return 0;
1089         *sval = max;
1090         return 1;
1091 }
1092
1093 int get_absolute_min(struct expression *expr, sval_t *sval)
1094 {
1095         struct range_list *rl;
1096         struct symbol *type;
1097
1098         type = get_type(expr);
1099         if (!type)
1100                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1101         rl = _get_rl(expr, ABSOLUTE_MIN);
1102         if (rl)
1103                 *sval = rl_min(rl);
1104         else
1105                 *sval = sval_type_min(type);
1106
1107         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1108                 *sval = sval_type_min(type);
1109         return 1;
1110 }
1111
1112 int get_absolute_max(struct expression *expr, sval_t *sval)
1113 {
1114         struct range_list *rl;
1115         struct symbol *type;
1116
1117         type = get_type(expr);
1118         if (!type)
1119                 type = &llong_ctype;
1120         rl = _get_rl(expr, ABSOLUTE_MAX);
1121         if (rl)
1122                 *sval = rl_max(rl);
1123         else
1124                 *sval = sval_type_max(type);
1125
1126         if (sval_cmp(sval_type_max(type), *sval) < 0)
1127                 *sval = sval_type_max(type);
1128         return 1;
1129 }
1130
1131 int known_condition_true(struct expression *expr)
1132 {
1133         sval_t tmp;
1134
1135         if (!expr)
1136                 return 0;
1137
1138         if (get_value(expr, &tmp) && tmp.value)
1139                 return 1;
1140
1141         return 0;
1142 }
1143
1144 int known_condition_false(struct expression *expr)
1145 {
1146         if (!expr)
1147                 return 0;
1148
1149         if (is_zero(expr))
1150                 return 1;
1151
1152         if (expr->type == EXPR_CALL) {
1153                 if (sym_name_is("__builtin_constant_p", expr->fn))
1154                         return 1;
1155         }
1156         return 0;
1157 }
1158
1159 int implied_condition_true(struct expression *expr)
1160 {
1161         sval_t tmp;
1162
1163         if (!expr)
1164                 return 0;
1165
1166         if (known_condition_true(expr))
1167                 return 1;
1168         if (get_implied_value(expr, &tmp) && tmp.value)
1169                 return 1;
1170
1171         if (expr->type == EXPR_POSTOP)
1172                 return implied_condition_true(expr->unop);
1173
1174         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1175                 return implied_not_equal(expr->unop, 1);
1176         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1177                 return implied_not_equal(expr->unop, -1);
1178
1179         expr = strip_expr(expr);
1180         switch (expr->type) {
1181         case EXPR_COMPARE:
1182                 if (do_comparison(expr) == 1)
1183                         return 1;
1184                 break;
1185         case EXPR_PREOP:
1186                 if (expr->op == '!') {
1187                         if (implied_condition_false(expr->unop))
1188                                 return 1;
1189                         break;
1190                 }
1191                 break;
1192         default:
1193                 if (implied_not_equal(expr, 0) == 1)
1194                         return 1;
1195                 break;
1196         }
1197         return 0;
1198 }
1199
1200 int implied_condition_false(struct expression *expr)
1201 {
1202         struct expression *tmp;
1203         sval_t sval;
1204
1205         if (!expr)
1206                 return 0;
1207
1208         if (known_condition_false(expr))
1209                 return 1;
1210
1211         switch (expr->type) {
1212         case EXPR_COMPARE:
1213                 if (do_comparison(expr) == 2)
1214                         return 1;
1215         case EXPR_PREOP:
1216                 if (expr->op == '!') {
1217                         if (implied_condition_true(expr->unop))
1218                                 return 1;
1219                         break;
1220                 }
1221                 tmp = strip_expr(expr);
1222                 if (tmp != expr)
1223                         return implied_condition_false(tmp);
1224                 break;
1225         default:
1226                 if (get_implied_value(expr, &sval) && sval.value == 0)
1227                         return 1;
1228                 break;
1229         }
1230         return 0;
1231 }