smatch_math.c

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