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