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