smatch_math.c

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