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_right_shift(struct expression *expr, int implied)
 310 {
 311         struct range_list *left_rl;
 312         sval_t right;
 313         sval_t min, max;
 314
 315         if (implied == RL_EXACT || implied == RL_HARD)
 316                 return NULL;
 317         /* this is hopeless without the right side */
 318         if (!get_implied_value(expr->right, &right))
 319                 return NULL;
 320         left_rl = _get_rl(expr->left, implied);
 321         if (left_rl) {
 322                 max = rl_max(left_rl);
 323                 min = rl_min(left_rl);
 324         } else {
 325                 if (implied == RL_FUZZY)
 326                         return NULL;
 327                 max = sval_type_max(get_type(expr->left));
 328                 min = sval_type_val(get_type(expr->left), 0);
 329         }
 330
 331         max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 332         min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 333         return alloc_rl(min, max);
 334 }
 335
 336 static struct range_list *handle_left_shift(struct expression *expr, int implied)
 337 {
 338         struct range_list *left_rl, *res;
 339         sval_t right;
 340         sval_t min, max;
 341         int add_zero = 0;
 342
 343         if (implied == RL_EXACT || implied == RL_HARD)
 344                 return NULL;
 345         /* this is hopeless without the right side */
 346         if (!get_implied_value(expr->right, &right))
 347                 return NULL;
 348         left_rl = _get_rl(expr->left, implied);
 349         if (left_rl) {
 350                 max = rl_max(left_rl);
 351                 min = rl_min(left_rl);
 352                 if (min.value == 0) {
 353                         min.value = 1;
 354                         add_zero = 1;
 355                 }
 356         } else {
 357                 if (implied == RL_FUZZY)
 358                         return NULL;
 359                 max = sval_type_max(get_type(expr->left));
 360                 min = sval_type_val(get_type(expr->left), 1);
 361                 add_zero = 1;
 362         }
 363
 364         max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
 365         min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
 366         res = alloc_rl(min, max);
 367         if (add_zero)
 368                 res = rl_union(res, rl_zero());
 369         return res;
 370 }
 371
 372 static struct range_list *handle_known_binop(struct expression *expr)
 373 {
 374         sval_t left, right;
 375
 376         if (!get_value(expr->left, &left))
 377                 return NULL;
 378         if (!get_value(expr->right, &right))
 379                 return NULL;
 380         left = sval_binop(left, expr->op, right);
 381         return alloc_rl(left, left);
 382 }
 383
 384 static struct range_list *handle_binop_rl(struct expression *expr, int implied)
 385 {
 386         struct symbol *type;
 387         struct range_list *left_rl, *right_rl, *rl;
 388         sval_t min, max;
 389
 390         rl = handle_known_binop(expr);
 391         if (rl)
 392                 return rl;
 393         if (implied == RL_EXACT)
 394                 return NULL;
 395
 396         switch (expr->op) {
 397         case '%':
 398                 return handle_mod_rl(expr, implied);
 399         case '&':
 400                 return handle_bitwise_AND(expr, implied);
 401         case SPECIAL_RIGHTSHIFT:
 402                 return handle_right_shift(expr, implied);
 403         case SPECIAL_LEFTSHIFT:
 404                 return handle_left_shift(expr, implied);
 405         case '-':
 406                 return handle_subtract_rl(expr, implied);
 407         case '/':
 408                 return handle_divide_rl(expr, implied);
 409         }
 410
 411         type = get_type(expr);
 412         left_rl = _get_rl(expr->left, implied);
 413         left_rl = cast_rl(type, left_rl);
 414         right_rl = _get_rl(expr->right, implied);
 415         right_rl = cast_rl(type, right_rl);
 416
 417         if (!left_rl || !right_rl)
 418                 return NULL;
 419
 420         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 421                 return NULL;
 422         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 423
 424         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) {
 425                 switch (implied) {
 426                 case RL_FUZZY:
 427                 case RL_HARD:
 428                         return NULL;
 429                 default:
 430                         max = sval_type_max(get_type(expr));
 431                 }
 432         } else {
 433                 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 434         }
 435
 436         return alloc_rl(min, max);
 437 }
 438
 439 static int do_comparison(struct expression *expr)
 440 {
 441         struct range_list *left_ranges = NULL;
 442         struct range_list *right_ranges = NULL;
 443         int poss_true, poss_false;
 444         struct symbol *type;
 445
 446         type = get_type(expr);
 447
 448         get_implied_rl(expr->left, &left_ranges);
 449         get_implied_rl(expr->right, &right_ranges);
 450         left_ranges = cast_rl(type, left_ranges);
 451         right_ranges = cast_rl(type, right_ranges);
 452
 453         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 454         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 455
 456         free_rl(&left_ranges);
 457         free_rl(&right_ranges);
 458
 459         if (!poss_true && !poss_false)
 460                 return 0;
 461         if (poss_true && !poss_false)
 462                 return 1;
 463         if (!poss_true && poss_false)
 464                 return 2;
 465         return 3;
 466 }
 467
 468 static struct range_list *handle_comparison_rl(struct expression *expr, int implied)
 469 {
 470         sval_t left, right;
 471         int res;
 472
 473         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 474                 struct data_range tmp_left, tmp_right;
 475
 476                 tmp_left.min = left;
 477                 tmp_left.max = left;
 478                 tmp_right.min = right;
 479                 tmp_right.max = right;
 480                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 481                         return rl_one();
 482                 return rl_zero();
 483         }
 484
 485         if (implied == RL_EXACT)
 486                 return NULL;
 487
 488         res = do_comparison(expr);
 489         if (res == 1)
 490                 return rl_one();
 491         if (res == 2)
 492                 return rl_zero();
 493
 494         return alloc_rl(zero, one);
 495 }
 496
 497 static struct range_list *handle_logical_rl(struct expression *expr, int implied)
 498 {
 499         sval_t left, right;
 500         int left_known = 0;
 501         int right_known = 0;
 502
 503         if (implied == RL_EXACT) {
 504                 if (get_value(expr->left, &left))
 505                         left_known = 1;
 506                 if (get_value(expr->right, &right))
 507                         right_known = 1;
 508         } else {
 509                 if (get_implied_value(expr->left, &left))
 510                         left_known = 1;
 511                 if (get_implied_value(expr->right, &right))
 512                         right_known = 1;
 513         }
 514
 515         switch (expr->op) {
 516         case SPECIAL_LOGICAL_OR:
 517                 if (left_known && left.value)
 518                         return rl_one();
 519                 if (right_known && right.value)
 520                         return rl_one();
 521                 if (left_known && right_known)
 522                         return rl_zero();
 523                 break;
 524         case SPECIAL_LOGICAL_AND:
 525                 if (left_known && right_known) {
 526                         if (left.value && right.value)
 527                                 return rl_one();
 528                         return rl_zero();
 529                 }
 530                 break;
 531         default:
 532                 return NULL;
 533         }
 534
 535         if (implied == RL_EXACT)
 536                 return NULL;
 537
 538         return alloc_rl(zero, one);
 539 }
 540
 541 static struct range_list *handle_conditional_rl(struct expression *expr, int implied)
 542 {
 543         struct range_list *true_rl, *false_rl;
 544         struct symbol *type;
 545         int final_pass_orig = final_pass;
 546
 547         if (known_condition_true(expr->conditional))
 548                 return _get_rl(expr->cond_true, implied);
 549         if (known_condition_false(expr->conditional))
 550                 return _get_rl(expr->cond_false, implied);
 551
 552         if (implied == RL_EXACT)
 553                 return NULL;
 554
 555         if (implied_condition_true(expr->conditional))
 556                 return _get_rl(expr->cond_true, implied);
 557         if (implied_condition_false(expr->conditional))
 558                 return _get_rl(expr->cond_false, implied);
 559
 560
 561         /* this becomes a problem with deeply nested conditional statements */
 562         if (low_on_memory())
 563                 return NULL;
 564
 565         type = get_type(expr);
 566
 567         __push_fake_cur_slist();
 568         final_pass = 0;
 569         __split_whole_condition(expr->conditional);
 570         true_rl = _get_rl(expr->cond_true, implied);
 571         __push_true_states();
 572         __use_false_states();
 573         false_rl = _get_rl(expr->cond_false, implied);
 574         __merge_true_states();
 575         __free_fake_cur_slist();
 576         final_pass = final_pass_orig;
 577
 578         if (!true_rl || !false_rl)
 579                 return NULL;
 580         true_rl = cast_rl(type, true_rl);
 581         false_rl = cast_rl(type, false_rl);
 582
 583         return rl_union(true_rl, false_rl);
 584 }
 585
 586 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 587 {
 588         struct sm_state *sm;
 589         struct sm_state *tmp;
 590         sval_t sval;
 591
 592         if (get_hard_max(expr, &sval)) {
 593                 *max = sval;
 594                 return 1;
 595         }
 596
 597         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 598         if (!sm)
 599                 return 0;
 600
 601         sval = sval_type_min(estate_type(sm->state));
 602         FOR_EACH_PTR(sm->possible, tmp) {
 603                 sval_t new_min;
 604
 605                 new_min = estate_min(tmp->state);
 606                 if (sval_cmp(new_min, sval) > 0)
 607                         sval = new_min;
 608         } END_FOR_EACH_PTR(tmp);
 609
 610         if (sval_is_min(sval))
 611                 return 0;
 612         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 613                 return 0;
 614
 615         *max = sval_cast(get_type(expr), sval);
 616         return 1;
 617 }
 618
 619 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 620 {
 621         struct sm_state *sm;
 622         struct sm_state *tmp;
 623         sval_t sval;
 624
 625         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 626         if (!sm)
 627                 return 0;
 628
 629         if (!sval_is_min(estate_min(sm->state))) {
 630                 *min = estate_min(sm->state);
 631                 return 1;
 632         }
 633
 634         sval = sval_type_max(estate_type(sm->state));
 635         FOR_EACH_PTR(sm->possible, tmp) {
 636                 sval_t new_max;
 637
 638                 new_max = estate_max(tmp->state);
 639                 if (sval_cmp(new_max, sval) < 0)
 640                         sval = new_max;
 641         } END_FOR_EACH_PTR(tmp);
 642
 643         if (sval_is_max(sval))
 644                 return 0;
 645         *min = sval_cast(get_type(expr), sval);
 646         return 1;
 647 }
 648
 649 static int get_const_value(struct expression *expr, sval_t *sval)
 650 {
 651         struct symbol *sym;
 652         sval_t right;
 653
 654         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 655                 return 0;
 656         sym = expr->symbol;
 657         if (!(sym->ctype.modifiers & MOD_CONST))
 658                 return 0;
 659         if (get_value(sym->initializer, &right)) {
 660                 *sval = sval_cast(get_type(expr), right);
 661                 return 1;
 662         }
 663         return 0;
 664 }
 665
 666 static struct range_list *handle_variable(struct expression *expr, int implied)
 667 {
 668         struct smatch_state *state;
 669         struct range_list *rl;
 670         sval_t sval, min, max;
 671
 672         if (get_const_value(expr, &sval))
 673                 return alloc_rl(sval, sval);
 674
 675         switch (implied) {
 676         case RL_EXACT:
 677                 return NULL;
 678         case RL_HARD:
 679         case RL_IMPLIED:
 680         case RL_ABSOLUTE:
 681                 state = get_state_expr(SMATCH_EXTRA, expr);
 682                 if (!state || !state->data) {
 683                         if (implied == RL_HARD)
 684                                 return NULL;
 685                         if (get_local_rl(expr, &rl))
 686                                 return rl;
 687                         return NULL;
 688                 }
 689                 if (implied == RL_HARD && !estate_has_hard_max(state))
 690                         return NULL;
 691                 return clone_rl(estate_rl(state));
 692         case RL_FUZZY:
 693                 if (!get_fuzzy_min_helper(expr, &min))
 694                         min = sval_type_min(get_type(expr));
 695                 if (!get_fuzzy_max_helper(expr, &max))
 696                         return NULL;
 697                 /* fuzzy ranges are often inverted */
 698                 if (sval_cmp(min, max) > 0) {
 699                         sval = min;
 700                         min = max;
 701                         max = sval;
 702                 }
 703                 return alloc_rl(min, max);
 704         }
 705         return NULL;
 706 }
 707
 708 static sval_t handle_sizeof(struct expression *expr)
 709 {
 710         struct symbol *sym;
 711         sval_t ret;
 712
 713         ret = sval_blank(expr);
 714         sym = expr->cast_type;
 715         if (!sym) {
 716                 sym = evaluate_expression(expr->cast_expression);
 717                 /*
 718                  * Expressions of restricted types will possibly get
 719                  * promoted - check that here
 720                  */
 721                 if (is_restricted_type(sym)) {
 722                         if (sym->bit_size < bits_in_int)
 723                                 sym = &int_ctype;
 724                 } else if (is_fouled_type(sym)) {
 725                         sym = &int_ctype;
 726                 }
 727         }
 728         examine_symbol_type(sym);
 729
 730         ret.type = size_t_ctype;
 731         if (sym->bit_size <= 0) /* sizeof(void) */ {
 732                 if (get_real_base_type(sym) == &void_ctype)
 733                         ret.value = 1;
 734                 else
 735                         ret.value = 0;
 736         } else
 737                 ret.value = bits_to_bytes(sym->bit_size);
 738
 739         return ret;
 740 }
 741
 742 static struct range_list *handle_call_rl(struct expression *expr, int implied)
 743 {
 744         struct range_list *rl;
 745
 746         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
 747                 return NULL;
 748
 749         if (get_implied_return(expr, &rl))
 750                 return rl;
 751         return db_return_vals(expr);
 752 }
 753
 754 static struct range_list *handle_cast(struct expression *expr, int implied)
 755 {
 756         struct range_list *rl;
 757         struct symbol *type;
 758
 759         type = get_type(expr);
 760         rl = _get_rl(expr->cast_expression, implied);
 761         if (rl)
 762                 return cast_rl(type, rl);
 763         if (implied == RL_ABSOLUTE)
 764                 return alloc_whole_rl(type);
 765         if (implied == RL_IMPLIED && type &&
 766             type->bit_size > 0 && type->bit_size < 32)
 767                 return alloc_whole_rl(type);
 768         return NULL;
 769 }
 770
 771 static struct range_list *_get_rl(struct expression *expr, int implied)
 772 {
 773         struct range_list *rl;
 774         struct symbol *type;
 775         sval_t sval;
 776
 777         expr = strip_parens(expr);
 778         if (!expr)
 779                 return NULL;
 780         type = get_type(expr);
 781
 782         switch (expr->type) {
 783         case EXPR_VALUE:
 784                 sval = sval_from_val(expr, expr->value);
 785                 rl = alloc_rl(sval, sval);
 786                 break;
 787         case EXPR_PREOP:
 788                 rl = handle_preop_rl(expr, implied);
 789                 break;
 790         case EXPR_POSTOP:
 791                 rl = _get_rl(expr->unop, implied);
 792                 break;
 793         case EXPR_CAST:
 794         case EXPR_FORCE_CAST:
 795         case EXPR_IMPLIED_CAST:
 796                 rl = handle_cast(expr, implied);
 797                 break;
 798         case EXPR_BINOP:
 799                 rl = handle_binop_rl(expr, implied);
 800                 break;
 801         case EXPR_COMPARE:
 802                 rl = handle_comparison_rl(expr, implied);
 803                 break;
 804         case EXPR_LOGICAL:
 805                 rl = handle_logical_rl(expr, implied);
 806                 break;
 807         case EXPR_PTRSIZEOF:
 808         case EXPR_SIZEOF:
 809                 sval = handle_sizeof(expr);
 810                 rl = alloc_rl(sval, sval);
 811                 break;
 812         case EXPR_SELECT:
 813         case EXPR_CONDITIONAL:
 814                 rl = handle_conditional_rl(expr, implied);
 815                 break;
 816         case EXPR_CALL:
 817                 rl = handle_call_rl(expr, implied);
 818                 break;
 819         default:
 820                 rl = handle_variable(expr, implied);
 821         }
 822
 823         if (rl)
 824                 return rl;
 825         if (type && implied == RL_ABSOLUTE)
 826                 return alloc_whole_rl(type);
 827         return NULL;
 828 }
 829
 830 /* returns 1 if it can get a value literal or else returns 0 */
 831 int get_value(struct expression *expr, sval_t *sval)
 832 {
 833         struct range_list *rl;
 834
 835         rl = _get_rl(expr, RL_EXACT);
 836         if (!rl_to_sval(rl, sval))
 837                 return 0;
 838         return 1;
 839 }
 840
 841 int get_implied_value(struct expression *expr, sval_t *sval)
 842 {
 843         struct range_list *rl;
 844
 845         rl =  _get_rl(expr, RL_IMPLIED);
 846         if (!rl_to_sval(rl, sval))
 847                 return 0;
 848         return 1;
 849 }
 850
 851 int get_implied_min(struct expression *expr, sval_t *sval)
 852 {
 853         struct range_list *rl;
 854
 855         rl =  _get_rl(expr, RL_IMPLIED);
 856         if (!rl)
 857                 return 0;
 858         *sval = rl_min(rl);
 859         return 1;
 860 }
 861
 862 int get_implied_max(struct expression *expr, sval_t *sval)
 863 {
 864         struct range_list *rl;
 865
 866         rl =  _get_rl(expr, RL_IMPLIED);
 867         if (!rl)
 868                 return 0;
 869         *sval = rl_max(rl);
 870         return 1;
 871 }
 872
 873 int get_implied_rl(struct expression *expr, struct range_list **rl)
 874 {
 875         *rl = _get_rl(expr, RL_IMPLIED);
 876         if (*rl)
 877                 return 1;
 878         return 0;
 879 }
 880
 881 int get_absolute_rl(struct expression *expr, struct range_list **rl)
 882 {
 883         *rl = _get_rl(expr, RL_ABSOLUTE);
 884         if (!*rl)
 885                 *rl = alloc_whole_rl(get_type(expr));
 886         return 1;
 887 }
 888
 889 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
 890 {
 891         struct smatch_state *state;
 892
 893         state = get_state(SMATCH_EXTRA, var, sym);
 894         *rl = estate_rl(state);
 895         if (*rl)
 896                 return 1;
 897         return 0;
 898 }
 899
 900 int get_hard_max(struct expression *expr, sval_t *sval)
 901 {
 902         struct range_list *rl;
 903
 904         rl =  _get_rl(expr, RL_HARD);
 905         if (!rl)
 906                 return 0;
 907         *sval = rl_max(rl);
 908         return 1;
 909 }
 910
 911 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 912 {
 913         struct range_list *rl;
 914         sval_t tmp;
 915
 916         rl =  _get_rl(expr, RL_FUZZY);
 917         if (!rl)
 918                 return 0;
 919         tmp = rl_min(rl);
 920         if (sval_is_negative(tmp) && sval_is_min(tmp))
 921                 return 0;
 922         *sval = tmp;
 923         return 1;
 924 }
 925
 926 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 927 {
 928         struct range_list *rl;
 929         sval_t max;
 930
 931         rl =  _get_rl(expr, RL_FUZZY);
 932         if (!rl)
 933                 return 0;
 934         max = rl_max(rl);
 935         if (max.uvalue > INT_MAX - 10000)
 936                 return 0;
 937         *sval = max;
 938         return 1;
 939 }
 940
 941 int get_absolute_min(struct expression *expr, sval_t *sval)
 942 {
 943         struct range_list *rl;
 944         struct symbol *type;
 945
 946         type = get_type(expr);
 947         if (!type)
 948                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 949         rl = _get_rl(expr, RL_ABSOLUTE);
 950         if (rl)
 951                 *sval = rl_min(rl);
 952         else
 953                 *sval = sval_type_min(type);
 954
 955         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 956                 *sval = sval_type_min(type);
 957         return 1;
 958 }
 959
 960 int get_absolute_max(struct expression *expr, sval_t *sval)
 961 {
 962         struct range_list *rl;
 963         struct symbol *type;
 964
 965         type = get_type(expr);
 966         if (!type)
 967                 type = &llong_ctype;
 968         rl = _get_rl(expr, RL_ABSOLUTE);
 969         if (rl)
 970                 *sval = rl_max(rl);
 971         else
 972                 *sval = sval_type_max(type);
 973
 974         if (sval_cmp(sval_type_max(type), *sval) < 0)
 975                 *sval = sval_type_max(type);
 976         return 1;
 977 }
 978
 979 int known_condition_true(struct expression *expr)
 980 {
 981         sval_t tmp;
 982
 983         if (!expr)
 984                 return 0;
 985
 986         if (get_value(expr, &tmp) && tmp.value)
 987                 return 1;
 988
 989         return 0;
 990 }
 991
 992 int known_condition_false(struct expression *expr)
 993 {
 994         if (!expr)
 995                 return 0;
 996
 997         if (is_zero(expr))
 998                 return 1;
 999
1000         if (expr->type == EXPR_CALL) {
1001                 if (sym_name_is("__builtin_constant_p", expr->fn))
1002                         return 1;
1003         }
1004         return 0;
1005 }
1006
1007 int implied_condition_true(struct expression *expr)
1008 {
1009         sval_t tmp;
1010
1011         if (!expr)
1012                 return 0;
1013
1014         if (known_condition_true(expr))
1015                 return 1;
1016         if (get_implied_value(expr, &tmp) && tmp.value)
1017                 return 1;
1018
1019         if (expr->type == EXPR_POSTOP)
1020                 return implied_condition_true(expr->unop);
1021
1022         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1023                 return implied_not_equal(expr->unop, 1);
1024         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1025                 return implied_not_equal(expr->unop, -1);
1026
1027         expr = strip_expr(expr);
1028         switch (expr->type) {
1029         case EXPR_COMPARE:
1030                 if (do_comparison(expr) == 1)
1031                         return 1;
1032                 break;
1033         case EXPR_PREOP:
1034                 if (expr->op == '!') {
1035                         if (implied_condition_false(expr->unop))
1036                                 return 1;
1037                         break;
1038                 }
1039                 break;
1040         default:
1041                 if (implied_not_equal(expr, 0) == 1)
1042                         return 1;
1043                 break;
1044         }
1045         return 0;
1046 }
1047
1048 int implied_condition_false(struct expression *expr)
1049 {
1050         struct expression *tmp;
1051         sval_t sval;
1052
1053         if (!expr)
1054                 return 0;
1055
1056         if (known_condition_false(expr))
1057                 return 1;
1058
1059         switch (expr->type) {
1060         case EXPR_COMPARE:
1061                 if (do_comparison(expr) == 2)
1062                         return 1;
1063         case EXPR_PREOP:
1064                 if (expr->op == '!') {
1065                         if (implied_condition_true(expr->unop))
1066                                 return 1;
1067                         break;
1068                 }
1069                 tmp = strip_expr(expr);
1070                 if (tmp != expr)
1071                         return implied_condition_false(tmp);
1072                 break;
1073         default:
1074                 if (get_implied_value(expr, &sval) && sval.value == 0)
1075                         return 1;
1076                 break;
1077         }
1078         return 0;
1079 }