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