smatch_math.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include "symbol.h"
  19 #include "smatch.h"
  20 #include "smatch_slist.h"
  21 #include "smatch_extra.h"
  22
  23 static struct range_list *_get_rl(struct expression *expr, int implied);
  24 static struct range_list *handle_variable(struct expression *expr, int implied);
  25
  26 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  27 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  28
  29 static struct range_list *rl_zero(void)
  30 {
  31         return alloc_rl(zero, zero);
  32 }
  33
  34 static struct range_list *rl_one(void)
  35 {
  36         return alloc_rl(one, one);
  37 }
  38
  39 enum {
  40         RL_EXACT,
  41         RL_HARD,
  42         RL_FUZZY,
  43         RL_IMPLIED,
  44         RL_ABSOLUTE
  45 };
  46
  47 static struct range_list *last_stmt_rl(struct statement *stmt, int implied)
  48 {
  49         if (!stmt)
  50                 return NULL;
  51
  52         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  53         if (stmt->type != STMT_EXPRESSION)
  54                 return NULL;
  55         return _get_rl(stmt->expression, implied);
  56 }
  57
  58 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied)
  59 {
  60         return last_stmt_rl(get_expression_statement(expr), implied);
  61 }
  62
  63 static struct range_list *handle_ampersand_rl(int implied)
  64 {
  65         if (implied == RL_EXACT || implied == RL_HARD)
  66                 return NULL;
  67         return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
  68 }
  69
  70 static struct range_list *handle_negate_rl(struct expression *expr, int implied)
  71 {
  72         if (known_condition_true(expr->unop))
  73                 return rl_zero();
  74         if (known_condition_false(expr->unop))
  75                 return rl_one();
  76
  77         if (implied == RL_EXACT)
  78                 return NULL;
  79
  80         if (implied_condition_true(expr->unop))
  81                 return rl_zero();
  82         if (implied_condition_false(expr->unop))
  83                 return rl_one();
  84         return alloc_rl(zero, one);
  85 }
  86
  87 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied)
  88 {
  89         struct range_list *rl;
  90         sval_t sval;
  91
  92         rl = _get_rl(expr->unop, implied);
  93         if (!rl_to_sval(rl, &sval))
  94                 return NULL;
  95         sval = sval_preop(sval, '~');
  96         sval_cast(get_type(expr->unop), sval);
  97         return alloc_rl(sval, sval);
  98 }
  99
 100 static struct range_list *handle_minus_preop(struct expression *expr, int implied)
 101 {
 102         struct range_list *rl;
 103         sval_t sval;
 104
 105         rl = _get_rl(expr->unop, implied);
 106         if (!rl_to_sval(rl, &sval))
 107                 return NULL;
 108         sval = sval_preop(sval, '-');
 109         return alloc_rl(sval, sval);
 110 }
 111
 112 static struct range_list *handle_preop_rl(struct expression *expr, int implied)
 113 {
 114         switch (expr->op) {
 115         case '&':
 116                 return handle_ampersand_rl(implied);
 117         case '!':
 118                 return handle_negate_rl(expr, implied);
 119         case '~':
 120                 return handle_bitwise_negate(expr, implied);
 121         case '-':
 122                 return handle_minus_preop(expr, implied);
 123         case '*':
 124                 return handle_variable(expr, implied);
 125         case '(':
 126                 return handle_expression_statement_rl(expr, implied);
 127         default:
 128                 return NULL;
 129         }
 130 }
 131
 132 static struct range_list *handle_divide_rl(struct expression *expr, int implied)
 133 {
 134         struct range_list *left_rl, *right_rl;
 135         struct symbol *type;
 136         sval_t min, max;
 137
 138         type = get_type(expr);
 139
 140         left_rl = _get_rl(expr->left, implied);
 141         left_rl = cast_rl(type, left_rl);
 142         right_rl = _get_rl(expr->right, implied);
 143         right_rl = cast_rl(type, right_rl);
 144
 145         if (!left_rl || !right_rl)
 146                 return NULL;
 147         if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
 148                 return NULL;
 149         if (sval_is_negative(rl_min(left_rl)) || sval_cmp_val(rl_min(right_rl), 0) <= 0)
 150                 return NULL;
 151
 152         max = rl_max(left_rl);
 153         if (!sval_is_max(max))
 154                 max = sval_binop(max, '/', rl_min(right_rl));
 155         min = sval_binop(rl_min(left_rl), '/', rl_max(right_rl));
 156         return alloc_rl(min, max);
 157 }
 158
 159 static struct range_list *handle_subtract_rl(struct expression *expr, int implied)
 160 {
 161         struct symbol *type;
 162         struct range_list *left_rl, *right_rl;
 163         sval_t max, min, tmp;
 164         int comparison;
 165
 166         type = get_type(expr);
 167         comparison = get_comparison(expr->left, expr->right);
 168
 169         left_rl = _get_rl(expr->left, implied);
 170         left_rl = cast_rl(type, left_rl);
 171         right_rl = _get_rl(expr->right, implied);
 172         right_rl = cast_rl(type, right_rl);
 173
 174         if ((!left_rl || !right_rl) &&
 175             (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
 176                 return NULL;
 177
 178         if (!left_rl)
 179                 left_rl = alloc_whole_rl(type);
 180         if (!right_rl)
 181                 right_rl = alloc_whole_rl(type);
 182
 183         /* negative values complicate everything fix this later */
 184         if (sval_is_negative(rl_min(right_rl)))
 185                 return NULL;
 186         max = rl_max(left_rl);
 187
 188         switch (comparison) {
 189         case '>':
 190         case SPECIAL_UNSIGNED_GT:
 191                 min = sval_type_val(type, 1);
 192                 max = rl_max(left_rl);
 193                 break;
 194         case SPECIAL_GTE:
 195         case SPECIAL_UNSIGNED_GTE:
 196                 min = sval_type_val(type, 0);
 197                 max = rl_max(left_rl);
 198                 break;
 199         default:
 200                 if (sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl)))
 201                         return NULL;
 202                 min = sval_type_min(type);
 203         }
 204
 205         if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
 206                 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
 207                 if (sval_cmp(tmp, min) > 0)
 208                         min = tmp;
 209         }
 210
 211         if (!sval_is_max(rl_max(left_rl))) {
 212                 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
 213                 if (sval_cmp(tmp, max) < 0)
 214                         max = tmp;
 215         }
 216
 217         if (sval_is_min(min) && sval_is_max(max))
 218                 return NULL;
 219
 220         return cast_rl(type, alloc_rl(min, max));
 221 }
 222
 223 static struct range_list *handle_mod_rl(struct expression *expr, int implied)
 224 {
 225         struct range_list *rl;
 226         sval_t left, right, sval;
 227
 228         if (implied == RL_EXACT) {
 229                 if (!get_value(expr->right, &right))
 230                         return NULL;
 231                 if (!get_value(expr->left, &left))
 232                         return NULL;
 233                 sval = sval_binop(left, '%', right);
 234                 return alloc_rl(sval, sval);
 235         }
 236         /* if we can't figure out the right side it's probably hopeless */
 237         if (!get_implied_value(expr->right, &right))
 238                 return NULL;
 239
 240         right = sval_cast(get_type(expr), right);
 241         right.value--;
 242
 243         rl = _get_rl(expr->left, implied);
 244         if (rl && rl_max(rl).uvalue < right.uvalue)
 245                 right.uvalue = rl_max(rl).uvalue;
 246
 247         return alloc_rl(zero, right);
 248 }
 249
 250 static sval_t sval_lowest_set_bit(sval_t sval)
 251 {
 252         int i;
 253         int found = 0;
 254
 255         for (i = 0; i < 64; i++) {
 256                 if (sval.uvalue & 1ULL << i) {
 257                         if (!found++)
 258                                 continue;
 259                         sval.uvalue &= ~(1ULL << i);
 260                 }
 261         }
 262         return sval;
 263 }
 264
 265 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied)
 266 {
 267         struct symbol *type;
 268         struct range_list *left_rl, *right_rl;
 269         sval_t known;
 270
 271         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE)
 272                 return NULL;
 273
 274         type = get_type(expr);
 275
 276         if (get_implied_value(expr->left, &known)) {
 277                 sval_t min;
 278
 279                 min = sval_lowest_set_bit(known);
 280                 left_rl = alloc_rl(min, known);
 281                 left_rl = cast_rl(type, left_rl);
 282                 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 283         } else {
 284                 left_rl = _get_rl(expr->left, implied);
 285                 if (left_rl) {
 286                         left_rl = cast_rl(type, left_rl);
 287                         left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
 288                 } else {
 289                         if (implied == RL_HARD)
 290                                 return NULL;
 291                         left_rl = alloc_whole_rl(type);
 292                 }
 293         }
 294
 295         if (get_implied_value(expr->right, &known)) {
 296                 sval_t min;
 297
 298                 min = sval_lowest_set_bit(known);
 299                 right_rl = alloc_rl(min, known);
 300                 right_rl = cast_rl(type, right_rl);
 301                 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 302         } else {
 303                 right_rl = _get_rl(expr->right, implied);
 304                 if (right_rl) {
 305                         right_rl = cast_rl(type, right_rl);
 306                         right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 307                 } else {
 308                         if (implied == RL_HARD)
 309                                 return NULL;
 310                         right_rl = alloc_whole_rl(type);
 311                 }
 312         }
 313
 314         return rl_intersection(left_rl, right_rl);
 315 }
 316
 317 static struct range_list *handle_bitwise_OR(struct expression *expr, int implied)
 318 {
 319         struct symbol *type;
 320         struct range_list *left_rl, *right_rl;
 321
 322         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE)
 323                 return NULL;
 324
 325         type = get_type(expr);
 326
 327         get_absolute_rl(expr->left, &left_rl);
 328         get_absolute_rl(expr->right, &right_rl);
 329         left_rl = cast_rl(type, left_rl);
 330         right_rl = cast_rl(type, right_rl);
 331
 332         return rl_union(left_rl, right_rl);
 333 }
 334
 335 static struct range_list *handle_right_shift(struct expression *expr, int implied)
 336 {
 337         struct range_list *left_rl;
 338         sval_t right;
 339         sval_t min, max;
 340
 341         if (implied == RL_EXACT || implied == RL_HARD)
 342                 return NULL;
 343         /* this is hopeless without the right side */
 344         if (!get_implied_value(expr->right, &right))
 345                 return NULL;
 346         left_rl = _get_rl(expr->left, implied);
 347         if (left_rl) {
 348                 max = rl_max(left_rl);
 349                 min = rl_min(left_rl);
 350         } else {
 351                 if (implied == RL_FUZZY)
 352                         return NULL;
 353                 max = sval_type_max(get_type(expr->left));
 354                 min = sval_type_val(get_type(expr->left), 0);
 355         }
 356
 357         max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 358         min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 359         return alloc_rl(min, max);
 360 }
 361
 362 static struct range_list *handle_left_shift(struct expression *expr, int implied)
 363 {
 364         struct range_list *left_rl, *res;
 365         sval_t right;
 366         sval_t min, max;
 367         int add_zero = 0;
 368
 369         if (implied == RL_EXACT || implied == RL_HARD)
 370                 return NULL;
 371         /* this is hopeless without the right side */
 372         if (!get_implied_value(expr->right, &right))
 373                 return NULL;
 374         left_rl = _get_rl(expr->left, implied);
 375         if (left_rl) {
 376                 max = rl_max(left_rl);
 377                 min = rl_min(left_rl);
 378                 if (min.value == 0) {
 379                         min.value = 1;
 380                         add_zero = 1;
 381                 }
 382         } else {
 383                 if (implied == RL_FUZZY)
 384                         return NULL;
 385                 max = sval_type_max(get_type(expr->left));
 386                 min = sval_type_val(get_type(expr->left), 1);
 387                 add_zero = 1;
 388         }
 389
 390         max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
 391         min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
 392         res = alloc_rl(min, max);
 393         if (add_zero)
 394                 res = rl_union(res, rl_zero());
 395         return res;
 396 }
 397
 398 static struct range_list *handle_known_binop(struct expression *expr)
 399 {
 400         sval_t left, right;
 401
 402         if (!get_value(expr->left, &left))
 403                 return NULL;
 404         if (!get_value(expr->right, &right))
 405                 return NULL;
 406         left = sval_binop(left, expr->op, right);
 407         return alloc_rl(left, left);
 408 }
 409
 410 static struct range_list *handle_binop_rl(struct expression *expr, int implied)
 411 {
 412         struct symbol *type;
 413         struct range_list *left_rl, *right_rl, *rl;
 414         sval_t min, max;
 415
 416         rl = handle_known_binop(expr);
 417         if (rl)
 418                 return rl;
 419         if (implied == RL_EXACT)
 420                 return NULL;
 421
 422         switch (expr->op) {
 423         case '%':
 424                 return handle_mod_rl(expr, implied);
 425         case '&':
 426                 return handle_bitwise_AND(expr, implied);
 427         case '|':
 428                 return handle_bitwise_OR(expr, implied);
 429         case SPECIAL_RIGHTSHIFT:
 430                 return handle_right_shift(expr, implied);
 431         case SPECIAL_LEFTSHIFT:
 432                 return handle_left_shift(expr, implied);
 433         case '-':
 434                 return handle_subtract_rl(expr, implied);
 435         case '/':
 436                 return handle_divide_rl(expr, implied);
 437         }
 438
 439         type = get_type(expr);
 440         left_rl = _get_rl(expr->left, implied);
 441         left_rl = cast_rl(type, left_rl);
 442         right_rl = _get_rl(expr->right, implied);
 443         right_rl = cast_rl(type, right_rl);
 444
 445         if (!left_rl || !right_rl)
 446                 return NULL;
 447
 448         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 449                 return NULL;
 450         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 451
 452         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) {
 453                 switch (implied) {
 454                 case RL_FUZZY:
 455                 case RL_HARD:
 456                         return NULL;
 457                 default:
 458                         max = sval_type_max(get_type(expr));
 459                 }
 460         } else {
 461                 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 462         }
 463
 464         return alloc_rl(min, max);
 465 }
 466
 467 static int do_comparison(struct expression *expr)
 468 {
 469         struct range_list *left_ranges = NULL;
 470         struct range_list *right_ranges = NULL;
 471         int poss_true, poss_false;
 472         struct symbol *type;
 473
 474         type = get_type(expr);
 475
 476         get_implied_rl(expr->left, &left_ranges);
 477         get_implied_rl(expr->right, &right_ranges);
 478         left_ranges = cast_rl(type, left_ranges);
 479         right_ranges = cast_rl(type, right_ranges);
 480
 481         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 482         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 483
 484         free_rl(&left_ranges);
 485         free_rl(&right_ranges);
 486
 487         if (!poss_true && !poss_false)
 488                 return 0;
 489         if (poss_true && !poss_false)
 490                 return 1;
 491         if (!poss_true && poss_false)
 492                 return 2;
 493         return 3;
 494 }
 495
 496 static struct range_list *handle_comparison_rl(struct expression *expr, int implied)
 497 {
 498         sval_t left, right;
 499         int res;
 500
 501         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 502                 struct data_range tmp_left, tmp_right;
 503
 504                 tmp_left.min = left;
 505                 tmp_left.max = left;
 506                 tmp_right.min = right;
 507                 tmp_right.max = right;
 508                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 509                         return rl_one();
 510                 return rl_zero();
 511         }
 512
 513         if (implied == RL_EXACT)
 514                 return NULL;
 515
 516         res = do_comparison(expr);
 517         if (res == 1)
 518                 return rl_one();
 519         if (res == 2)
 520                 return rl_zero();
 521
 522         return alloc_rl(zero, one);
 523 }
 524
 525 static struct range_list *handle_logical_rl(struct expression *expr, int implied)
 526 {
 527         sval_t left, right;
 528         int left_known = 0;
 529         int right_known = 0;
 530
 531         if (implied == RL_EXACT) {
 532                 if (get_value(expr->left, &left))
 533                         left_known = 1;
 534                 if (get_value(expr->right, &right))
 535                         right_known = 1;
 536         } else {
 537                 if (get_implied_value(expr->left, &left))
 538                         left_known = 1;
 539                 if (get_implied_value(expr->right, &right))
 540                         right_known = 1;
 541         }
 542
 543         switch (expr->op) {
 544         case SPECIAL_LOGICAL_OR:
 545                 if (left_known && left.value)
 546                         return rl_one();
 547                 if (right_known && right.value)
 548                         return rl_one();
 549                 if (left_known && right_known)
 550                         return rl_zero();
 551                 break;
 552         case SPECIAL_LOGICAL_AND:
 553                 if (left_known && right_known) {
 554                         if (left.value && right.value)
 555                                 return rl_one();
 556                         return rl_zero();
 557                 }
 558                 break;
 559         default:
 560                 return NULL;
 561         }
 562
 563         if (implied == RL_EXACT)
 564                 return NULL;
 565
 566         return alloc_rl(zero, one);
 567 }
 568
 569 static struct range_list *handle_conditional_rl(struct expression *expr, int implied)
 570 {
 571         struct range_list *true_rl, *false_rl;
 572         struct symbol *type;
 573         int final_pass_orig = final_pass;
 574
 575         if (known_condition_true(expr->conditional))
 576                 return _get_rl(expr->cond_true, implied);
 577         if (known_condition_false(expr->conditional))
 578                 return _get_rl(expr->cond_false, implied);
 579
 580         if (implied == RL_EXACT)
 581                 return NULL;
 582
 583         if (implied_condition_true(expr->conditional))
 584                 return _get_rl(expr->cond_true, implied);
 585         if (implied_condition_false(expr->conditional))
 586                 return _get_rl(expr->cond_false, implied);
 587
 588
 589         /* this becomes a problem with deeply nested conditional statements */
 590         if (low_on_memory())
 591                 return NULL;
 592
 593         type = get_type(expr);
 594
 595         __push_fake_cur_stree();
 596         final_pass = 0;
 597         __split_whole_condition(expr->conditional);
 598         true_rl = _get_rl(expr->cond_true, implied);
 599         __push_true_states();
 600         __use_false_states();
 601         false_rl = _get_rl(expr->cond_false, implied);
 602         __merge_true_states();
 603         __free_fake_cur_stree();
 604         final_pass = final_pass_orig;
 605
 606         if (!true_rl || !false_rl)
 607                 return NULL;
 608         true_rl = cast_rl(type, true_rl);
 609         false_rl = cast_rl(type, false_rl);
 610
 611         return rl_union(true_rl, false_rl);
 612 }
 613
 614 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 615 {
 616         struct smatch_state *state;
 617         sval_t sval;
 618
 619         if (get_hard_max(expr, &sval)) {
 620                 *max = sval;
 621                 return 1;
 622         }
 623
 624         state = get_state_expr(SMATCH_EXTRA, expr);
 625         if (!state || !estate_has_fuzzy_max(state))
 626                 return 0;
 627         *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
 628         return 1;
 629 }
 630
 631 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 632 {
 633         struct smatch_state *state;
 634         sval_t sval;
 635
 636         state = get_state_expr(SMATCH_EXTRA, expr);
 637         if (!state || !estate_rl(state))
 638                 return 0;
 639
 640         sval = estate_min(state);
 641         if (sval_is_negative(sval) && sval_is_min(sval))
 642                 return 0;
 643
 644         if (sval_is_max(sval))
 645                 return 0;
 646
 647         *min = sval_cast(get_type(expr), sval);
 648         return 1;
 649 }
 650
 651 int get_const_value(struct expression *expr, sval_t *sval)
 652 {
 653         struct symbol *sym;
 654         sval_t right;
 655
 656         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 657                 return 0;
 658         sym = expr->symbol;
 659         if (!(sym->ctype.modifiers & MOD_CONST))
 660                 return 0;
 661         if (get_value(sym->initializer, &right)) {
 662                 *sval = sval_cast(get_type(expr), right);
 663                 return 1;
 664         }
 665         return 0;
 666 }
 667
 668 static struct range_list *handle_variable(struct expression *expr, int implied)
 669 {
 670         struct smatch_state *state;
 671         struct range_list *rl;
 672         sval_t sval, min, max;
 673
 674         if (get_const_value(expr, &sval))
 675                 return alloc_rl(sval, sval);
 676
 677         switch (implied) {
 678         case RL_EXACT:
 679                 return NULL;
 680         case RL_HARD:
 681         case RL_IMPLIED:
 682         case RL_ABSOLUTE:
 683                 state = get_state_expr(SMATCH_EXTRA, expr);
 684                 if (!state || !state->data) {
 685                         if (implied == RL_HARD)
 686                                 return NULL;
 687                         if (get_local_rl(expr, &rl))
 688                                 return rl;
 689                         if (get_db_type_rl(expr, &rl))
 690                                 return rl;
 691                         return NULL;
 692                 }
 693                 if (implied == RL_HARD && !estate_has_hard_max(state))
 694                         return NULL;
 695                 return clone_rl(estate_rl(state));
 696         case RL_FUZZY:
 697                 if (!get_fuzzy_min_helper(expr, &min))
 698                         min = sval_type_min(get_type(expr));
 699                 if (!get_fuzzy_max_helper(expr, &max))
 700                         return NULL;
 701                 /* fuzzy ranges are often inverted */
 702                 if (sval_cmp(min, max) > 0) {
 703                         sval = min;
 704                         min = max;
 705                         max = sval;
 706                 }
 707                 return alloc_rl(min, max);
 708         }
 709         return NULL;
 710 }
 711
 712 static sval_t handle_sizeof(struct expression *expr)
 713 {
 714         struct symbol *sym;
 715         sval_t ret;
 716
 717         ret = sval_blank(expr);
 718         sym = expr->cast_type;
 719         if (!sym) {
 720                 sym = evaluate_expression(expr->cast_expression);
 721                 /*
 722                  * Expressions of restricted types will possibly get
 723                  * promoted - check that here
 724                  */
 725                 if (is_restricted_type(sym)) {
 726                         if (type_bits(sym) < bits_in_int)
 727                                 sym = &int_ctype;
 728                 } else if (is_fouled_type(sym)) {
 729                         sym = &int_ctype;
 730                 }
 731         }
 732         examine_symbol_type(sym);
 733
 734         ret.type = size_t_ctype;
 735         if (type_bits(sym) <= 0) /* sizeof(void) */ {
 736                 if (get_real_base_type(sym) == &void_ctype)
 737                         ret.value = 1;
 738                 else
 739                         ret.value = 0;
 740         } else
 741                 ret.value = type_bytes(sym);
 742
 743         return ret;
 744 }
 745
 746 static struct range_list *handle_call_rl(struct expression *expr, int implied)
 747 {
 748         struct range_list *rl;
 749
 750         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
 751                 return NULL;
 752
 753         if (get_implied_return(expr, &rl))
 754                 return rl;
 755         return db_return_vals(expr);
 756 }
 757
 758 static struct range_list *handle_cast(struct expression *expr, int implied)
 759 {
 760         struct range_list *rl;
 761         struct symbol *type;
 762
 763         type = get_type(expr);
 764         rl = _get_rl(expr->cast_expression, implied);
 765         if (rl)
 766                 return cast_rl(type, rl);
 767         if (implied == RL_ABSOLUTE)
 768                 return alloc_whole_rl(type);
 769         if (implied == RL_IMPLIED && type &&
 770             type_bits(type) > 0 && type_bits(type) < 32)
 771                 return alloc_whole_rl(type);
 772         return NULL;
 773 }
 774
 775 static struct range_list *_get_rl(struct expression *expr, int implied)
 776 {
 777         struct range_list *rl;
 778         struct symbol *type;
 779         sval_t sval;
 780
 781         expr = strip_parens(expr);
 782         if (!expr)
 783                 return NULL;
 784         type = get_type(expr);
 785
 786         switch (expr->type) {
 787         case EXPR_VALUE:
 788                 sval = sval_from_val(expr, expr->value);
 789                 rl = alloc_rl(sval, sval);
 790                 break;
 791         case EXPR_PREOP:
 792                 rl = handle_preop_rl(expr, implied);
 793                 break;
 794         case EXPR_POSTOP:
 795                 rl = _get_rl(expr->unop, implied);
 796                 break;
 797         case EXPR_CAST:
 798         case EXPR_FORCE_CAST:
 799         case EXPR_IMPLIED_CAST:
 800                 rl = handle_cast(expr, implied);
 801                 break;
 802         case EXPR_BINOP:
 803                 rl = handle_binop_rl(expr, implied);
 804                 break;
 805         case EXPR_COMPARE:
 806                 rl = handle_comparison_rl(expr, implied);
 807                 break;
 808         case EXPR_LOGICAL:
 809                 rl = handle_logical_rl(expr, implied);
 810                 break;
 811         case EXPR_PTRSIZEOF:
 812         case EXPR_SIZEOF:
 813                 sval = handle_sizeof(expr);
 814                 rl = alloc_rl(sval, sval);
 815                 break;
 816         case EXPR_SELECT:
 817         case EXPR_CONDITIONAL:
 818                 rl = handle_conditional_rl(expr, implied);
 819                 break;
 820         case EXPR_CALL:
 821                 rl = handle_call_rl(expr, implied);
 822                 break;
 823         default:
 824                 rl = handle_variable(expr, implied);
 825         }
 826
 827         if (rl)
 828                 return rl;
 829         if (type && implied == RL_ABSOLUTE)
 830                 return alloc_whole_rl(type);
 831         return NULL;
 832 }
 833
 834 /* returns 1 if it can get a value literal or else returns 0 */
 835 int get_value(struct expression *expr, sval_t *sval)
 836 {
 837         struct range_list *rl;
 838
 839         rl = _get_rl(expr, RL_EXACT);
 840         if (!rl_to_sval(rl, sval))
 841                 return 0;
 842         return 1;
 843 }
 844
 845 int get_implied_value(struct expression *expr, sval_t *sval)
 846 {
 847         struct range_list *rl;
 848
 849         rl =  _get_rl(expr, RL_IMPLIED);
 850         if (!rl_to_sval(rl, sval))
 851                 return 0;
 852         return 1;
 853 }
 854
 855 int get_implied_min(struct expression *expr, sval_t *sval)
 856 {
 857         struct range_list *rl;
 858
 859         rl =  _get_rl(expr, RL_IMPLIED);
 860         if (!rl)
 861                 return 0;
 862         *sval = rl_min(rl);
 863         return 1;
 864 }
 865
 866 int get_implied_max(struct expression *expr, sval_t *sval)
 867 {
 868         struct range_list *rl;
 869
 870         rl =  _get_rl(expr, RL_IMPLIED);
 871         if (!rl)
 872                 return 0;
 873         *sval = rl_max(rl);
 874         return 1;
 875 }
 876
 877 int get_implied_rl(struct expression *expr, struct range_list **rl)
 878 {
 879         *rl = _get_rl(expr, RL_IMPLIED);
 880         if (*rl)
 881                 return 1;
 882         return 0;
 883 }
 884
 885 int get_absolute_rl(struct expression *expr, struct range_list **rl)
 886 {
 887         *rl = _get_rl(expr, RL_ABSOLUTE);
 888         if (!*rl)
 889                 *rl = alloc_whole_rl(get_type(expr));
 890         return 1;
 891 }
 892
 893 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
 894 {
 895         struct smatch_state *state;
 896
 897         state = get_state(SMATCH_EXTRA, var, sym);
 898         *rl = estate_rl(state);
 899         if (*rl)
 900                 return 1;
 901         return 0;
 902 }
 903
 904 int get_hard_max(struct expression *expr, sval_t *sval)
 905 {
 906         struct range_list *rl;
 907
 908         rl =  _get_rl(expr, RL_HARD);
 909         if (!rl)
 910                 return 0;
 911         *sval = rl_max(rl);
 912         return 1;
 913 }
 914
 915 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 916 {
 917         struct range_list *rl;
 918         sval_t tmp;
 919
 920         rl =  _get_rl(expr, RL_FUZZY);
 921         if (!rl)
 922                 return 0;
 923         tmp = rl_min(rl);
 924         if (sval_is_negative(tmp) && sval_is_min(tmp))
 925                 return 0;
 926         *sval = tmp;
 927         return 1;
 928 }
 929
 930 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 931 {
 932         struct range_list *rl;
 933         sval_t max;
 934
 935         rl =  _get_rl(expr, RL_FUZZY);
 936         if (!rl)
 937                 return 0;
 938         max = rl_max(rl);
 939         if (max.uvalue > INT_MAX - 10000)
 940                 return 0;
 941         *sval = max;
 942         return 1;
 943 }
 944
 945 int get_absolute_min(struct expression *expr, sval_t *sval)
 946 {
 947         struct range_list *rl;
 948         struct symbol *type;
 949
 950         type = get_type(expr);
 951         if (!type)
 952                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 953         rl = _get_rl(expr, RL_ABSOLUTE);
 954         if (rl)
 955                 *sval = rl_min(rl);
 956         else
 957                 *sval = sval_type_min(type);
 958
 959         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 960                 *sval = sval_type_min(type);
 961         return 1;
 962 }
 963
 964 int get_absolute_max(struct expression *expr, sval_t *sval)
 965 {
 966         struct range_list *rl;
 967         struct symbol *type;
 968
 969         type = get_type(expr);
 970         if (!type)
 971                 type = &llong_ctype;
 972         rl = _get_rl(expr, RL_ABSOLUTE);
 973         if (rl)
 974                 *sval = rl_max(rl);
 975         else
 976                 *sval = sval_type_max(type);
 977
 978         if (sval_cmp(sval_type_max(type), *sval) < 0)
 979                 *sval = sval_type_max(type);
 980         return 1;
 981 }
 982
 983 int known_condition_true(struct expression *expr)
 984 {
 985         sval_t tmp;
 986
 987         if (!expr)
 988                 return 0;
 989
 990         if (get_value(expr, &tmp) && tmp.value)
 991                 return 1;
 992
 993         return 0;
 994 }
 995
 996 int known_condition_false(struct expression *expr)
 997 {
 998         if (!expr)
 999                 return 0;
1000
1001         if (is_zero(expr))
1002                 return 1;
1003
1004         if (expr->type == EXPR_CALL) {
1005                 if (sym_name_is("__builtin_constant_p", expr->fn))
1006                         return 1;
1007         }
1008         return 0;
1009 }
1010
1011 int implied_condition_true(struct expression *expr)
1012 {
1013         sval_t tmp;
1014
1015         if (!expr)
1016                 return 0;
1017
1018         if (known_condition_true(expr))
1019                 return 1;
1020         if (get_implied_value(expr, &tmp) && tmp.value)
1021                 return 1;
1022
1023         if (expr->type == EXPR_POSTOP)
1024                 return implied_condition_true(expr->unop);
1025
1026         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1027                 return implied_not_equal(expr->unop, 1);
1028         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1029                 return implied_not_equal(expr->unop, -1);
1030
1031         expr = strip_expr(expr);
1032         switch (expr->type) {
1033         case EXPR_COMPARE:
1034                 if (do_comparison(expr) == 1)
1035                         return 1;
1036                 break;
1037         case EXPR_PREOP:
1038                 if (expr->op == '!') {
1039                         if (implied_condition_false(expr->unop))
1040                                 return 1;
1041                         break;
1042                 }
1043                 break;
1044         default:
1045                 if (implied_not_equal(expr, 0) == 1)
1046                         return 1;
1047                 break;
1048         }
1049         return 0;
1050 }
1051
1052 int implied_condition_false(struct expression *expr)
1053 {
1054         struct expression *tmp;
1055         sval_t sval;
1056
1057         if (!expr)
1058                 return 0;
1059
1060         if (known_condition_false(expr))
1061                 return 1;
1062
1063         switch (expr->type) {
1064         case EXPR_COMPARE:
1065                 if (do_comparison(expr) == 2)
1066                         return 1;
1067         case EXPR_PREOP:
1068                 if (expr->op == '!') {
1069                         if (implied_condition_true(expr->unop))
1070                                 return 1;
1071                         break;
1072                 }
1073                 tmp = strip_expr(expr);
1074                 if (tmp != expr)
1075                         return implied_condition_false(tmp);
1076                 break;
1077         default:
1078                 if (get_implied_value(expr, &sval) && sval.value == 0)
1079                         return 1;
1080                 break;
1081         }
1082         return 0;
1083 }