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