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 sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 668 {
 669         sval_t ret;
 670
 671         ret = sval_blank(expr);
 672
 673         switch (implied) {
 674         case IMPLIED:
 675         case IMPLIED_MAX:
 676         case IMPLIED_MIN:
 677         case HARD_MAX:
 678         case ABSOLUTE_MIN:
 679         case ABSOLUTE_MAX:
 680                 if (!get_implied_value_helper(expr, &ret, implied))
 681                         *undefined = 1;
 682                 break;
 683         case FUZZY_MAX:
 684                 if (!get_fuzzy_max_helper(expr, &ret))
 685                         *undefined = 1;
 686                 break;
 687         case FUZZY_MIN:
 688                 if (!get_fuzzy_min_helper(expr, &ret))
 689                         *undefined = 1;
 690                 break;
 691         default:
 692                 *undefined = 1;
 693         }
 694         return ret;
 695 }
 696
 697 static int get_const_value(struct expression *expr, sval_t *sval)
 698 {
 699         struct symbol *sym;
 700         sval_t right;
 701
 702         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 703                 return 0;
 704         sym = expr->symbol;
 705         if (!(sym->ctype.modifiers & MOD_CONST))
 706                 return 0;
 707         if (get_value(sym->initializer, &right)) {
 708                 *sval = sval_cast(get_type(expr), right);
 709                 return 1;
 710         }
 711         return 0;
 712 }
 713
 714 static sval_t handle_sizeof(struct expression *expr)
 715 {
 716         struct symbol *sym;
 717         sval_t ret;
 718
 719         ret = sval_blank(expr);
 720         sym = expr->cast_type;
 721         if (!sym) {
 722                 sym = evaluate_expression(expr->cast_expression);
 723                 /*
 724                  * Expressions of restricted types will possibly get
 725                  * promoted - check that here
 726                  */
 727                 if (is_restricted_type(sym)) {
 728                         if (sym->bit_size < bits_in_int)
 729                                 sym = &int_ctype;
 730                 } else if (is_fouled_type(sym)) {
 731                         sym = &int_ctype;
 732                 }
 733         }
 734         examine_symbol_type(sym);
 735
 736         ret.type = size_t_ctype;
 737         if (sym->bit_size <= 0) /* sizeof(void) */ {
 738                 if (get_real_base_type(sym) == &void_ctype)
 739                         ret.value = 1;
 740                 else
 741                         ret.value = 0;
 742         } else
 743                 ret.value = bits_to_bytes(sym->bit_size);
 744
 745         return ret;
 746 }
 747
 748 static sval_t handle_call(struct expression *expr, int *undefined, int implied)
 749 {
 750         struct range_list *rl;
 751
 752         if (!get_implied_rl(expr, &rl)) {
 753                 *undefined = 1;
 754                 return bogus;
 755         }
 756
 757         switch (implied) {
 758         case IMPLIED:
 759                 if (sval_cmp(rl_min(rl), rl_max(rl)) == 0)
 760                         return rl_min(rl);
 761                 *undefined = 1;
 762                 return bogus;
 763         case IMPLIED_MIN:
 764         case ABSOLUTE_MIN:
 765                 return rl_min(rl);
 766
 767         case IMPLIED_MAX:
 768         case HARD_MAX:
 769         case ABSOLUTE_MAX:
 770                 return rl_max(rl);
 771         default:
 772                 *undefined = 1;
 773                 return bogus;
 774         }
 775
 776 }
 777
 778 static struct range_list *_get_rl(struct expression *expr, int implied)
 779 {
 780         struct range_list *rl;
 781         struct symbol *type;
 782         int undefined;
 783         sval_t sval;
 784
 785         expr = strip_parens(expr);
 786         if (!expr)
 787                 return NULL;
 788         type = get_type(expr);
 789
 790         undefined = 0;
 791         switch (expr->type) {
 792         case EXPR_VALUE:
 793                 sval = sval_from_val(expr, expr->value);
 794                 break;
 795         case EXPR_PREOP:
 796                 sval = handle_preop(expr, &undefined, implied);
 797                 break;
 798         case EXPR_POSTOP:
 799                 sval = _get_value(expr->unop, &undefined, implied);
 800                 break;
 801         case EXPR_CAST:
 802         case EXPR_FORCE_CAST:
 803         case EXPR_IMPLIED_CAST:
 804                 sval = _get_value(expr->cast_expression, &undefined, implied);
 805                 sval = sval_cast(type, sval);
 806                 break;
 807         case EXPR_BINOP:
 808                 sval = handle_binop(expr, &undefined, implied);
 809                 break;
 810         case EXPR_COMPARE:
 811                 sval = handle_comparison(expr, &undefined, implied);
 812                 break;
 813         case EXPR_LOGICAL:
 814                 sval = handle_logical(expr, &undefined, implied);
 815                 break;
 816         case EXPR_PTRSIZEOF:
 817         case EXPR_SIZEOF:
 818                 sval = handle_sizeof(expr);
 819                 break;
 820         case EXPR_SYMBOL:
 821                 if (get_const_value(expr, &sval)) {
 822                         break;
 823                 }
 824                 sval = _get_implied_value(expr, &undefined, implied);
 825                 break;
 826         case EXPR_SELECT:
 827         case EXPR_CONDITIONAL:
 828                 sval = handle_conditional(expr, &undefined, implied);
 829                 break;
 830         case EXPR_CALL:
 831                 sval = handle_call(expr, &undefined, implied);
 832                 break;
 833         default:
 834                 sval = _get_implied_value(expr, &undefined, implied);
 835         }
 836
 837         if (undefined && type &&
 838             (implied == ABSOLUTE_MAX || implied == ABSOLUTE_MIN))
 839                 return alloc_whole_rl(type);
 840         if (undefined)
 841                 return NULL;
 842         rl = alloc_rl(sval, sval);
 843         return rl;
 844 }
 845
 846 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 847 {
 848         struct symbol *type;
 849         sval_t ret;
 850
 851         if (!expr) {
 852                 *undefined = 1;
 853                 return bogus;
 854         }
 855         if (*undefined)
 856                 return bogus;
 857
 858         expr = strip_parens(expr);
 859         type = get_type(expr);
 860
 861         switch (expr->type) {
 862         case EXPR_VALUE:
 863                 ret = sval_from_val(expr, expr->value);
 864                 break;
 865         case EXPR_PREOP:
 866                 ret = handle_preop(expr, undefined, implied);
 867                 break;
 868         case EXPR_POSTOP:
 869                 ret = _get_value(expr->unop, undefined, implied);
 870                 break;
 871         case EXPR_CAST:
 872         case EXPR_FORCE_CAST:
 873         case EXPR_IMPLIED_CAST:
 874                 ret = _get_value(expr->cast_expression, undefined, implied);
 875                 ret = sval_cast(type, ret);
 876                 break;
 877         case EXPR_BINOP:
 878                 ret = handle_binop(expr, undefined, implied);
 879                 break;
 880         case EXPR_COMPARE:
 881                 ret = handle_comparison(expr, undefined, implied);
 882                 break;
 883         case EXPR_LOGICAL:
 884                 ret = handle_logical(expr, undefined, implied);
 885                 break;
 886         case EXPR_PTRSIZEOF:
 887         case EXPR_SIZEOF:
 888                 ret = handle_sizeof(expr);
 889                 break;
 890         case EXPR_SYMBOL:
 891                 if (get_const_value(expr, &ret)) {
 892                         break;
 893                 }
 894                 ret = _get_implied_value(expr, undefined, implied);
 895                 break;
 896         case EXPR_SELECT:
 897         case EXPR_CONDITIONAL:
 898                 ret = handle_conditional(expr, undefined, implied);
 899                 break;
 900         case EXPR_CALL:
 901                 ret = handle_call(expr, undefined, implied);
 902                 break;
 903         default:
 904                 ret = _get_implied_value(expr, undefined, implied);
 905         }
 906
 907         if (*undefined)
 908                 return bogus;
 909         return ret;
 910 }
 911
 912 /* returns 1 if it can get a value literal or else returns 0 */
 913 int get_value(struct expression *expr, sval_t *sval)
 914 {
 915         struct range_list *rl;
 916
 917         rl = _get_rl(expr, EXACT);
 918         if (!rl_to_sval(rl, sval))
 919                 return 0;
 920         return 1;
 921 }
 922
 923 int get_implied_value(struct expression *expr, sval_t *sval)
 924 {
 925         struct range_list *rl;
 926
 927         rl =  _get_rl(expr, IMPLIED);
 928         if (!rl_to_sval(rl, sval))
 929                 return 0;
 930         return 1;
 931 }
 932
 933 int get_implied_min(struct expression *expr, sval_t *sval)
 934 {
 935         struct range_list *rl;
 936
 937         rl =  _get_rl(expr, IMPLIED_MIN);
 938         if (!rl)
 939                 return 0;
 940         *sval = rl_min(rl);
 941         return 1;
 942 }
 943
 944 int get_implied_max(struct expression *expr, sval_t *sval)
 945 {
 946         struct range_list *rl;
 947
 948         rl =  _get_rl(expr, IMPLIED_MAX);
 949         if (!rl)
 950                 return 0;
 951         *sval = rl_max(rl);
 952         return 1;
 953 }
 954
 955 int get_implied_rl(struct expression *expr, struct range_list **rl)
 956 {
 957         sval_t sval;
 958         struct smatch_state *state;
 959         sval_t min, max;
 960         int min_known = 0;
 961         int max_known = 0;
 962
 963         *rl = NULL;
 964
 965         expr = strip_parens(expr);
 966         if (!expr)
 967                 return 0;
 968
 969         state = get_state_expr(SMATCH_EXTRA, expr);
 970         if (state) {
 971                 *rl = clone_rl(estate_rl(state));
 972                 return 1;
 973         }
 974
 975         if (expr->type == EXPR_CALL) {
 976                 if (get_implied_return(expr, rl))
 977                         return 1;
 978                 *rl = db_return_vals(expr);
 979                 if (*rl)
 980                         return 1;
 981                 return 0;
 982         }
 983
 984         if (get_implied_value(expr, &sval)) {
 985                 add_range(rl, sval, sval);
 986                 return 1;
 987         }
 988
 989         if (get_local_rl(expr, rl))
 990                 return 1;
 991
 992         min_known = get_implied_min(expr, &min);
 993         max_known = get_implied_max(expr, &max);
 994         if (!min_known && !max_known)
 995                 return 0;
 996         if (!min_known)
 997                 get_absolute_min(expr, &min);
 998         if (!max_known)
 999                 get_absolute_max(expr, &max);
1000
1001         *rl = alloc_rl(min, max);
1002         return 1;
1003 }
1004
1005 int get_hard_max(struct expression *expr, sval_t *sval)
1006 {
1007         struct range_list *rl;
1008
1009         rl =  _get_rl(expr, HARD_MAX);
1010         if (!rl)
1011                 return 0;
1012         *sval = rl_max(rl);
1013         return 1;
1014 }
1015
1016 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1017 {
1018         struct range_list *rl;
1019
1020         rl =  _get_rl(expr, FUZZY_MIN);
1021         if (!rl)
1022                 return 0;
1023         *sval = rl_min(rl);
1024         return 1;
1025 }
1026
1027 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1028 {
1029         struct range_list *rl;
1030         sval_t max;
1031
1032         rl =  _get_rl(expr, FUZZY_MAX);
1033         if (!rl)
1034                 return 0;
1035         max = rl_max(rl);
1036         if (max.uvalue > INT_MAX - 10000)
1037                 return 0;
1038         *sval = max;
1039         return 1;
1040 }
1041
1042 int get_absolute_min(struct expression *expr, sval_t *sval)
1043 {
1044         struct range_list *rl;
1045         struct symbol *type;
1046
1047         type = get_type(expr);
1048         if (!type)
1049                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1050         rl = _get_rl(expr, ABSOLUTE_MIN);
1051         if (rl)
1052                 *sval = rl_min(rl);
1053         else
1054                 *sval = sval_type_min(type);
1055
1056         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1057                 *sval = sval_type_min(type);
1058         return 1;
1059 }
1060
1061 int get_absolute_max(struct expression *expr, sval_t *sval)
1062 {
1063         struct range_list *rl;
1064         struct symbol *type;
1065
1066         type = get_type(expr);
1067         if (!type)
1068                 type = &llong_ctype;
1069         rl = _get_rl(expr, ABSOLUTE_MAX);
1070         if (rl)
1071                 *sval = rl_max(rl);
1072         else
1073                 *sval = sval_type_max(type);
1074
1075         if (sval_cmp(sval_type_max(type), *sval) < 0)
1076                 *sval = sval_type_max(type);
1077         return 1;
1078 }
1079
1080 int known_condition_true(struct expression *expr)
1081 {
1082         sval_t tmp;
1083
1084         if (!expr)
1085                 return 0;
1086
1087         if (get_value(expr, &tmp) && tmp.value)
1088                 return 1;
1089
1090         return 0;
1091 }
1092
1093 int known_condition_false(struct expression *expr)
1094 {
1095         if (!expr)
1096                 return 0;
1097
1098         if (is_zero(expr))
1099                 return 1;
1100
1101         if (expr->type == EXPR_CALL) {
1102                 if (sym_name_is("__builtin_constant_p", expr->fn))
1103                         return 1;
1104         }
1105         return 0;
1106 }
1107
1108 int implied_condition_true(struct expression *expr)
1109 {
1110         sval_t tmp;
1111
1112         if (!expr)
1113                 return 0;
1114
1115         if (known_condition_true(expr))
1116                 return 1;
1117         if (get_implied_value(expr, &tmp) && tmp.value)
1118                 return 1;
1119
1120         if (expr->type == EXPR_POSTOP)
1121                 return implied_condition_true(expr->unop);
1122
1123         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1124                 return implied_not_equal(expr->unop, 1);
1125         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1126                 return implied_not_equal(expr->unop, -1);
1127
1128         expr = strip_expr(expr);
1129         switch (expr->type) {
1130         case EXPR_COMPARE:
1131                 if (do_comparison(expr) == 1)
1132                         return 1;
1133                 break;
1134         case EXPR_PREOP:
1135                 if (expr->op == '!') {
1136                         if (implied_condition_false(expr->unop))
1137                                 return 1;
1138                         break;
1139                 }
1140                 break;
1141         default:
1142                 if (implied_not_equal(expr, 0) == 1)
1143                         return 1;
1144                 break;
1145         }
1146         return 0;
1147 }
1148
1149 int implied_condition_false(struct expression *expr)
1150 {
1151         struct expression *tmp;
1152         sval_t sval;
1153
1154         if (!expr)
1155                 return 0;
1156
1157         if (known_condition_false(expr))
1158                 return 1;
1159
1160         switch (expr->type) {
1161         case EXPR_COMPARE:
1162                 if (do_comparison(expr) == 2)
1163                         return 1;
1164         case EXPR_PREOP:
1165                 if (expr->op == '!') {
1166                         if (implied_condition_true(expr->unop))
1167                                 return 1;
1168                         break;
1169                 }
1170                 tmp = strip_expr(expr);
1171                 if (tmp != expr)
1172                         return implied_condition_false(tmp);
1173                 break;
1174         default:
1175                 if (get_implied_value(expr, &sval) && sval.value == 0)
1176                         return 1;
1177                 break;
1178         }
1179         return 0;
1180 }