smatch_extra.c

   1 /*
   2  * sparse/smatch_extra.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * smatch_extra.c is supposed to track the value of every variable.
  12  */
  13
  14 #include <stdlib.h>
  15 #ifndef __USE_ISOC99
  16 #define __USE_ISOC99
  17 #endif
  18 #include <limits.h>
  19 #include "parse.h"
  20 #include "smatch.h"
  21 #include "smatch_slist.h"
  22 #include "smatch_extra.h"
  23
  24 static int my_id;
  25
  26 static struct symbol *cur_func;
  27
  28 struct data_range whole_range = {
  29         .min = LLONG_MIN,
  30         .max = LLONG_MAX,
  31 };
  32
  33 static struct data_info *alloc_dinfo_range(long long min, long long max)
  34 {
  35         struct data_info *ret;
  36
  37         ret = __alloc_data_info(0);
  38         ret->type = DATA_RANGE;
  39         ret->value_ranges = NULL;
  40         add_range(&ret->value_ranges, min, max);
  41         return ret;
  42 }
  43
  44 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
  45 {
  46         struct data_info *ret;
  47
  48         ret = __alloc_data_info(0);
  49         ret->type = DATA_RANGE;
  50         ret->value_ranges = rl;
  51         return ret;
  52 }
  53
  54 static struct smatch_state *alloc_extra_state_empty(void)
  55 {
  56         struct smatch_state *state;
  57         struct data_info *dinfo;
  58
  59         dinfo = __alloc_data_info(0);
  60         dinfo->type = DATA_RANGE;
  61         dinfo->value_ranges = NULL;
  62         state = __alloc_smatch_state(0);
  63         state->data = dinfo;
  64         return state;
  65 }
  66
  67 static struct smatch_state *alloc_extra_state_no_name(int val)
  68 {
  69         struct smatch_state *state;
  70
  71         state = __alloc_smatch_state(0);
  72         state->data = (void *)alloc_dinfo_range(val, val);
  73         return state;
  74 }
  75
  76 /* We do this because ->value_ranges is a list */
  77 struct smatch_state *extra_undefined(void)
  78 {
  79         struct data_info *dinfo;
  80         static struct smatch_state *ret;
  81         static struct symbol *prev_func;
  82
  83         if  (prev_func == cur_func)
  84                 return ret;
  85         prev_func = cur_func;
  86
  87         dinfo = alloc_dinfo_range(whole_range.min, whole_range.max);
  88         ret = __alloc_smatch_state(0);
  89         ret->name = "unknown";
  90         ret->data = dinfo;
  91         return ret;
  92 }
  93
  94 struct smatch_state *alloc_extra_state(long long val)
  95 {
  96         struct smatch_state *state;
  97
  98         state = alloc_extra_state_no_name(val);
  99         state->name = show_ranges(get_dinfo(state)->value_ranges);
 100         return state;
 101 }
 102
 103 struct smatch_state *alloc_extra_state_range(long long min, long long max)
 104 {
 105         struct smatch_state *state;
 106
 107         if (min == whole_range.min && max == whole_range.max)
 108                 return extra_undefined();
 109         state = __alloc_smatch_state(0);
 110         state->data = (void *)alloc_dinfo_range(min, max);
 111         state->name = show_ranges(get_dinfo(state)->value_ranges);
 112         return state;
 113 }
 114
 115 struct smatch_state *alloc_extra_state_range_list(struct range_list *rl)
 116 {
 117         struct smatch_state *state;
 118
 119         state = __alloc_smatch_state(0);
 120         state->data = (void *)alloc_dinfo_range_list(rl);
 121         state->name = show_ranges(get_dinfo(state)->value_ranges);
 122         return state;
 123 }
 124
 125 struct data_info *get_dinfo(struct smatch_state *state)
 126 {
 127         if (!state)
 128                 return NULL;
 129         return (struct data_info *)state->data;
 130
 131 }
 132
 133 struct smatch_state *filter_range(struct smatch_state *orig,
 134                                  long long filter_min, long long filter_max)
 135 {
 136         struct smatch_state *ret;
 137         struct data_info *orig_info;
 138         struct data_info *ret_info;
 139
 140         if (!orig)
 141                 orig = extra_undefined();
 142         orig_info = get_dinfo(orig);
 143         ret = alloc_extra_state_empty();
 144         ret_info = get_dinfo(ret);
 145         ret_info->value_ranges = remove_range(orig_info->value_ranges, filter_min, filter_max);
 146         ret->name = show_ranges(ret_info->value_ranges);
 147         return ret;
 148 }
 149
 150 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
 151 {
 152         return filter_range(orig, num, num);
 153 }
 154
 155 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
 156                                        struct smatch_state *s1,
 157                                        struct smatch_state *s2)
 158 {
 159         struct data_info *info1 = get_dinfo(s1);
 160         struct data_info *info2 = get_dinfo(s2);
 161         struct data_info *ret_info;
 162         struct smatch_state *tmp;
 163         struct range_list *value_ranges;
 164
 165         value_ranges = range_list_union(info1->value_ranges, info2->value_ranges);
 166         tmp = alloc_extra_state_empty();
 167         ret_info = get_dinfo(tmp);
 168         ret_info->value_ranges = value_ranges;
 169         tmp->name = show_ranges(ret_info->value_ranges);
 170         return tmp;
 171 }
 172
 173 static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
 174 {
 175         struct expression *iter_var;
 176         struct expression *condition;
 177         struct sm_state *sm;
 178         long long start;
 179
 180         condition = strip_expr(loop->iterator_pre_condition);
 181         if (!condition)
 182                 return NULL;
 183         if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
 184                 return NULL;
 185         if (condition->op != SPECIAL_DECREMENT)
 186                 return NULL;
 187
 188         iter_var = condition->unop;
 189         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 190         if (!sm)
 191                 return NULL;
 192         if (get_dinfo_min(get_dinfo(sm->state)) < 0)
 193                 return NULL;
 194         start = get_dinfo_max(get_dinfo(sm->state));
 195         if  (start <= 0)
 196                 return NULL;
 197         if (start != whole_range.max)
 198                 start--;
 199
 200         if (condition->type == EXPR_PREOP)
 201                 set_state_expr(SMATCH_EXTRA, iter_var, alloc_extra_state_range(1, start));
 202         if (condition->type == EXPR_POSTOP)
 203                 set_state_expr(SMATCH_EXTRA, iter_var, alloc_extra_state_range(0, start));
 204         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 205 }
 206
 207 static struct sm_state *handle_canonical_for_loops(struct statement *loop)
 208 {
 209         struct expression *iter_expr;
 210         struct expression *iter_var;
 211         struct expression *condition;
 212         struct sm_state *sm;
 213         long long start;
 214         long long end;
 215
 216         if (!loop->iterator_post_statement)
 217                 return NULL;
 218         if (loop->iterator_post_statement->type != STMT_EXPRESSION)
 219                 return NULL;
 220         iter_expr = loop->iterator_post_statement->expression;
 221         if (!loop->iterator_pre_condition)
 222                 return NULL;
 223         if (loop->iterator_pre_condition->type != EXPR_COMPARE)
 224                 return NULL;
 225         condition = loop->iterator_pre_condition;
 226
 227
 228         if (iter_expr->op != SPECIAL_INCREMENT)
 229                 return NULL;
 230         iter_var = iter_expr->unop;
 231         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 232         if (!sm)
 233                 return NULL;
 234         if (!get_single_value_from_dinfo(get_dinfo(sm->state), &start))
 235                 return NULL;
 236         if (!get_implied_value(condition->right, &end))
 237                 end = whole_range.max;
 238         if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
 239                 return NULL;
 240
 241         switch (condition->op) {
 242         case SPECIAL_NOTEQUAL:
 243         case '<':
 244                 if (end != whole_range.max)
 245                         end--;
 246                 break;
 247         case SPECIAL_LTE:
 248                 break;
 249         default:
 250                 return NULL;
 251         }
 252         if (end < start)
 253                 return NULL;
 254         set_state_expr(SMATCH_EXTRA, iter_var, alloc_extra_state_range(start, end));
 255         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 256 }
 257
 258 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct state_list **slist)
 259 {
 260         struct sm_state *ret;
 261
 262         __fake_cur = 1;
 263         if (!loop->iterator_post_statement)
 264                 ret = handle_canonical_while_count_down(loop);
 265         else
 266                 ret = handle_canonical_for_loops(loop);
 267         *slist = __fake_cur_slist;
 268         __fake_cur_slist = NULL;
 269         __fake_cur = 0;
 270         return ret;
 271 }
 272
 273 int __iterator_unchanged(struct sm_state *sm)
 274 {
 275         if (!sm)
 276                 return 0;
 277         if (get_sm_state(my_id, sm->name, sm->sym) == sm)
 278                 return 1;
 279         return 0;
 280 }
 281
 282 static void while_count_down_after(struct sm_state *sm, struct expression *condition)
 283 {
 284         long long after_value;
 285
 286         /* paranoid checking.  prolly not needed */
 287         condition = strip_expr(condition);
 288         if (!condition)
 289                 return;
 290         if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
 291                 return;
 292         if (condition->op != SPECIAL_DECREMENT)
 293                 return;
 294         after_value = get_dinfo_min(get_dinfo(sm->state));
 295         after_value--;
 296         set_state(SMATCH_EXTRA, sm->name, sm->sym, alloc_extra_state(after_value));
 297 }
 298
 299 void __extra_pre_loop_hook_after(struct sm_state *sm,
 300                                 struct statement *iterator,
 301                                 struct expression *condition)
 302 {
 303         struct expression *iter_expr;
 304         char *name;
 305         struct symbol *sym;
 306         long long value;
 307         int left = 0;
 308         struct smatch_state *state;
 309         struct data_info *dinfo;
 310         long long min, max;
 311
 312         if (!iterator) {
 313                 while_count_down_after(sm, condition);
 314                 return;
 315         }
 316
 317         iter_expr = iterator->expression;
 318
 319         if (condition->type != EXPR_COMPARE)
 320                 return;
 321         if (!get_value(condition->left, &value)) {
 322                 if (!get_value(condition->right, &value))
 323                         return;
 324                 left = 1;
 325         }
 326         if (left)
 327                 name = get_variable_from_expr(condition->left, &sym);
 328         else
 329                 name = get_variable_from_expr(condition->right, &sym);
 330         if (!name || !sym)
 331                 goto free;
 332         if (sym != sm->sym || strcmp(name, sm->name))
 333                 goto free;
 334         state = get_state(my_id, name, sym);
 335         dinfo = get_dinfo(state);
 336         min = get_dinfo_min(dinfo);
 337         max = get_dinfo_max(dinfo);
 338         if (iter_expr->op == SPECIAL_INCREMENT && min != whole_range.min && max == whole_range.max) {
 339                 set_state(my_id, name, sym, alloc_extra_state(min));
 340         } else if (min == whole_range.min && max != whole_range.max) {
 341                 set_state(my_id, name, sym, alloc_extra_state(max));
 342         }
 343 free:
 344         free_string(name);
 345         return;
 346 }
 347
 348 static struct smatch_state *unmatched_state(struct sm_state *sm)
 349 {
 350         return extra_undefined();
 351 }
 352
 353 static void match_function_call(struct expression *expr)
 354 {
 355         struct expression *tmp;
 356         struct symbol *sym;
 357         char *name;
 358         int i = 0;
 359
 360         FOR_EACH_PTR(expr->args, tmp) {
 361                 if (tmp->type == EXPR_PREOP && tmp->op == '&') {
 362                         name = get_variable_from_expr(tmp->unop, &sym);
 363                         if (name) {
 364                                 set_state(my_id, name, sym, extra_undefined());
 365                         }
 366                         free_string(name);
 367                 }
 368                 i++;
 369         } END_FOR_EACH_PTR(tmp);
 370 }
 371
 372 static void match_assign(struct expression *expr)
 373 {
 374         struct expression *left;
 375         struct expression *right;
 376         struct symbol *sym;
 377         char *name;
 378         long long value;
 379         int known;
 380         long long min = whole_range.min;
 381         long long max = whole_range.max;
 382         long long tmp;
 383         struct range_list *rl = NULL;
 384
 385         left = strip_expr(expr->left);
 386         name = get_variable_from_expr(left, &sym);
 387         if (!name)
 388                 return;
 389         right = strip_expr(expr->right);
 390         while (right->type == EXPR_ASSIGNMENT && right->op == '=')
 391                 right = strip_expr(right->left);
 392
 393         known = get_implied_range_list(right, &rl);
 394         if (expr->op == '=') {
 395                 if (known)
 396                         set_state(my_id, name, sym, alloc_extra_state_range_list(rl));
 397                 else
 398                         set_state(my_id, name, sym, extra_undefined());
 399                 goto free;
 400         }
 401
 402         known = get_implied_value(right, &value);
 403         if (expr->op == SPECIAL_ADD_ASSIGN) {
 404                 if (get_implied_min(left, &tmp)) {
 405                         if (known)
 406                                 min = tmp + value;
 407                         else
 408                                 min = tmp;
 409                 }
 410
 411         }
 412         if (expr->op == SPECIAL_SUB_ASSIGN) {
 413                 if (get_implied_max(left, &tmp)) {
 414                         if (known)
 415                                 max = tmp - value;
 416                         else
 417                                 max = tmp;
 418                 }
 419
 420         }
 421         set_state(my_id, name, sym, alloc_extra_state_range(min, max));
 422 free:
 423         free_string(name);
 424 }
 425
 426 static void unop_expr(struct expression *expr)
 427 {
 428         struct symbol *sym;
 429         char *name;
 430         long long min = whole_range.min;
 431         long long max = whole_range.max;
 432         long long val;
 433
 434         if (expr->op == '*')
 435                 return;
 436         if (expr->op == '(')
 437                 return;
 438         if (expr->op == '!')
 439                 return;
 440
 441         name = get_variable_from_expr(expr->unop, &sym);
 442         if (!name)
 443                 goto free;
 444         if (expr->op == SPECIAL_INCREMENT) {
 445                 if (get_implied_min(expr->unop, &val))
 446                         min = val + 1;
 447         }
 448         if (expr->op == SPECIAL_DECREMENT) {
 449                 if (get_implied_max(expr->unop, &val))
 450                         max = val - 1;
 451         }
 452         set_state(my_id, name, sym, alloc_extra_state_range(min, max));
 453 free:
 454         free_string(name);
 455 }
 456
 457 static void match_declarations(struct symbol *sym)
 458 {
 459         const char *name;
 460         long long val;
 461
 462         if (sym->ident) {
 463                 name = sym->ident->name;
 464                 if (sym->initializer) {
 465                         if (get_value(sym->initializer, &val))
 466                                 set_state(my_id, name, sym, alloc_extra_state(val));
 467                         else
 468                                 set_state(my_id, name, sym, extra_undefined());
 469                         scoped_state(my_id, name, sym);
 470                 } else {
 471                         set_state(my_id, name, sym, extra_undefined());
 472                         scoped_state(my_id, name, sym);
 473                 }
 474         }
 475 }
 476
 477 static void match_function_def(struct symbol *sym)
 478 {
 479         struct symbol *arg;
 480
 481         cur_func = sym;
 482         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 483                 if (!arg->ident) {
 484                         continue;
 485                 }
 486                 set_state(my_id, arg->ident->name, arg, extra_undefined());
 487         } END_FOR_EACH_PTR(arg);
 488 }
 489
 490 #define VAL_SINGLE 0
 491 #define VAL_MAX    1
 492 #define VAL_MIN    2
 493
 494 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 495 {
 496         struct smatch_state *state;
 497         struct symbol *sym;
 498         char *name;
 499
 500         if (get_value(expr, val))
 501                 return 1;
 502
 503         name = get_variable_from_expr(expr, &sym);
 504         if (!name)
 505                 return 0;
 506         state = get_state(my_id, name, sym);
 507         free_string(name);
 508         if (!state || !state->data)
 509                 return 0;
 510         if (what == VAL_SINGLE)
 511                 return get_single_value_from_dinfo(get_dinfo(state), val);
 512         if (what == VAL_MAX) {
 513                 *val = get_dinfo_max(get_dinfo(state));
 514                 if (*val == whole_range.max) /* this means just guessing */
 515                         return 0;
 516                 return 1;
 517         }
 518         *val = get_dinfo_min(get_dinfo(state));
 519         if (*val == whole_range.min)
 520                 return 0;
 521         return 1;
 522 }
 523
 524 int get_implied_single_val(struct expression *expr, long long *val)
 525 {
 526         return get_implied_value_helper(expr, val, VAL_SINGLE);
 527 }
 528
 529 int get_implied_max(struct expression *expr, long long *val)
 530 {
 531         return get_implied_value_helper(expr, val, VAL_MAX);
 532 }
 533
 534 int get_implied_min(struct expression *expr, long long *val)
 535 {
 536         return get_implied_value_helper(expr, val, VAL_MIN);
 537 }
 538
 539 int get_implied_single_fuzzy_max(struct expression *expr, long long *max)
 540 {
 541         struct sm_state *sm;
 542         struct sm_state *tmp;
 543
 544         if (get_implied_max(expr, max))
 545                 return 1;
 546
 547         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 548         if (!sm)
 549                 return 0;
 550
 551         *max = whole_range.min;
 552         FOR_EACH_PTR(sm->possible, tmp) {
 553                 long long new_min;
 554
 555                 new_min = get_dinfo_min(get_dinfo(tmp->state));
 556                 if (new_min > *max)
 557                         *max = new_min;
 558         } END_FOR_EACH_PTR(tmp);
 559
 560         if (*max > whole_range.min)
 561                 return 1;
 562         return 0;
 563 }
 564
 565 int get_implied_single_fuzzy_min(struct expression *expr, long long *min)
 566 {
 567         struct sm_state *sm;
 568         struct sm_state *tmp;
 569
 570         if (get_implied_min(expr, min))
 571                 return 1;
 572
 573         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 574         if (!sm)
 575                 return 0;
 576
 577         *min = whole_range.max;
 578         FOR_EACH_PTR(sm->possible, tmp) {
 579                 long long new_max;
 580
 581                 new_max = get_dinfo_max(get_dinfo(tmp->state));
 582                 if (new_max < *min)
 583                         *min = new_max;
 584         } END_FOR_EACH_PTR(tmp);
 585
 586         if (*min < whole_range.max)
 587                 return 1;
 588         return 0;
 589 }
 590
 591 static int last_stmt_val(struct statement *stmt, long long *val)
 592 {
 593         struct expression *expr;
 594
 595         if (!stmt)
 596                 return 0;
 597
 598         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 599         if (stmt->type != STMT_EXPRESSION)
 600                 return 0;
 601         expr = stmt->expression;
 602         return get_value(expr, val);
 603 }
 604
 605 static void match_comparison(struct expression *expr)
 606 {
 607         long long fixed;
 608         char *name = NULL;
 609         struct symbol *sym;
 610         struct smatch_state *true_state;
 611         struct smatch_state *false_state;
 612         struct smatch_state *orig;
 613         int left = 0;
 614         int comparison = expr->op;
 615         struct expression *varies = expr->right;
 616
 617         if (!get_value(expr->left, &fixed)) {
 618                 if (!get_value(expr->right, &fixed))
 619                         return;
 620                 varies = strip_expr(expr->left);
 621                 left = 1;
 622         }
 623         if (varies->op == SPECIAL_INCREMENT || varies->op == SPECIAL_DECREMENT)
 624                 varies = varies->unop;
 625         if (varies->type == EXPR_CALL) {
 626                 function_comparison(comparison, varies, fixed, left);
 627                 return;
 628         }
 629
 630         name = get_variable_from_expr(varies, &sym);
 631         if (!name || !sym)
 632                 goto free;
 633
 634         orig = get_state(my_id, name, sym);
 635         if (!orig)
 636                 orig = extra_undefined();
 637
 638         switch (comparison) {
 639         case '<':
 640         case SPECIAL_UNSIGNED_LT:
 641                 if (left) {
 642                         true_state = filter_range(orig, fixed, whole_range.max);
 643                         false_state = filter_range(orig, whole_range.min, fixed - 1);
 644                 } else {
 645                         true_state = filter_range(orig, whole_range.min, fixed);
 646                         false_state = filter_range(orig, fixed + 1, whole_range.max);
 647                 }
 648                 break;
 649         case SPECIAL_UNSIGNED_LTE:
 650         case SPECIAL_LTE:
 651                 if (left) {
 652                         true_state = filter_range(orig, fixed + 1, whole_range.max);
 653                         false_state = filter_range(orig, whole_range.min, fixed);
 654                 } else {
 655                         true_state = filter_range(orig, whole_range.min, fixed - 1);
 656                         false_state = filter_range(orig, fixed, whole_range.max);
 657                 }
 658                 break;
 659         case SPECIAL_EQUAL:
 660                 // todo.  print a warning here for impossible conditions.
 661                 true_state = alloc_extra_state(fixed);
 662                 false_state = filter_range(orig, fixed, fixed);
 663                 break;
 664         case SPECIAL_UNSIGNED_GTE:
 665         case SPECIAL_GTE:
 666                 if (left) {
 667                         true_state = filter_range(orig, whole_range.min, fixed - 1);
 668                         false_state = filter_range(orig, fixed, whole_range.max);
 669                 } else {
 670                         true_state = filter_range(orig, fixed + 1, whole_range.max);
 671                         false_state = filter_range(orig, whole_range.min, fixed);
 672                 }
 673                 break;
 674         case '>':
 675         case SPECIAL_UNSIGNED_GT:
 676                 if (left) {
 677                         true_state = filter_range(orig, whole_range.min, fixed);
 678                         false_state = filter_range(orig, fixed + 1, whole_range.max);
 679                 } else {
 680                         true_state = filter_range(orig, fixed, whole_range.max);
 681                         false_state = filter_range(orig, whole_range.min, fixed - 1);
 682                 }
 683                 break;
 684         case SPECIAL_NOTEQUAL:
 685                 true_state = filter_range(orig, fixed, fixed);
 686                 false_state = alloc_extra_state(fixed);
 687                 break;
 688         default:
 689                 sm_msg("unhandled comparison %d\n", comparison);
 690                 goto free;
 691         }
 692         set_true_false_states(my_id, name, sym, true_state, false_state);
 693 free:
 694         free_string(name);
 695 }
 696
 697 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 698 void __extra_match_condition(struct expression *expr)
 699 {
 700         struct symbol *sym;
 701         char *name;
 702         struct smatch_state *pre_state;
 703         struct smatch_state *true_state;
 704         struct smatch_state *false_state;
 705
 706         expr = strip_expr(expr);
 707         switch (expr->type) {
 708         case EXPR_CALL:
 709                 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
 710                 return;
 711         case EXPR_PREOP:
 712         case EXPR_SYMBOL:
 713         case EXPR_DEREF:
 714                 name = get_variable_from_expr(expr, &sym);
 715                 if (!name)
 716                         return;
 717                 pre_state = get_state(my_id, name, sym);
 718                 true_state = add_filter(pre_state, 0);
 719                 if (possibly_true(SPECIAL_EQUAL, get_dinfo(pre_state), 0, 0))
 720                         false_state = alloc_extra_state(0);
 721                 else
 722                         false_state = NULL;
 723                 set_true_false_states(my_id, name, sym, true_state, false_state);
 724                 free_string(name);
 725                 return;
 726         case EXPR_COMPARE:
 727                 match_comparison(expr);
 728                 return;
 729         case EXPR_ASSIGNMENT:
 730                 __extra_match_condition(expr->left);
 731                 return;
 732         }
 733 }
 734
 735 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
 736 int implied_not_equal(struct expression *expr, long long val)
 737 {
 738         char *name;
 739         struct symbol *sym;
 740         struct smatch_state *state;
 741         int ret = 0;
 742
 743         name = get_variable_from_expr(expr, &sym);
 744         if (!name || !sym)
 745                 goto exit;
 746         state = get_state(my_id, name, sym);
 747         if (!state || !state->data)
 748                 goto exit;
 749         ret = !possibly_false(SPECIAL_NOTEQUAL, get_dinfo(state), val, 1);
 750 exit:
 751         free_string(name);
 752         return ret;
 753 }
 754
 755 int known_condition_true(struct expression *expr)
 756 {
 757         long long tmp;
 758
 759         if (!expr)
 760                 return 0;
 761
 762         if (get_value(expr, &tmp) && tmp)
 763                 return 1;
 764
 765         expr = strip_expr(expr);
 766         switch (expr->type) {
 767         case EXPR_PREOP:
 768                 if (expr->op == '!') {
 769                         if (known_condition_false(expr->unop))
 770                                 return 1;
 771                         break;
 772                 }
 773                 break;
 774         default:
 775                 break;
 776         }
 777         return 0;
 778 }
 779
 780 int known_condition_false(struct expression *expr)
 781 {
 782         if (!expr)
 783                 return 0;
 784
 785         if (is_zero(expr))
 786                 return 1;
 787
 788         switch (expr->type) {
 789         case EXPR_PREOP:
 790                 if (expr->op == '!') {
 791                         if (known_condition_true(expr->unop))
 792                                 return 1;
 793                         break;
 794                 }
 795                 break;
 796         default:
 797                 break;
 798         }
 799         return 0;
 800 }
 801
 802 static int do_comparison_range(struct expression *expr)
 803 {
 804         struct symbol *sym;
 805         char *name;
 806         struct smatch_state *state;
 807         long long value;
 808         int left = 0;
 809         int poss_true, poss_false;
 810
 811         if (!get_value(expr->left, &value)) {
 812                 if (!get_value(expr->right, &value))
 813                         return 3;
 814                 left = 1;
 815         }
 816         if (left)
 817                 name = get_variable_from_expr(expr->left, &sym);
 818         else
 819                 name = get_variable_from_expr(expr->right, &sym);
 820         if (!name || !sym)
 821                 goto free;
 822         state = get_state(SMATCH_EXTRA, name, sym);
 823         if (!state)
 824                 goto free;
 825         poss_true = possibly_true(expr->op, get_dinfo(state), value, left);
 826         poss_false = possibly_false(expr->op, get_dinfo(state), value, left);
 827         if (!poss_true && !poss_false)
 828                 return 0;
 829         if (poss_true && !poss_false)
 830                 return 1;
 831         if (!poss_true && poss_false)
 832                 return 2;
 833         if (poss_true && poss_false)
 834                 return 3;
 835 free:
 836         free_string(name);
 837         return 3;
 838 }
 839
 840 int implied_condition_true(struct expression *expr)
 841 {
 842         struct statement *stmt;
 843         long long tmp;
 844         long long val;
 845
 846         if (!expr)
 847                 return 0;
 848
 849         if (get_implied_value(expr, &tmp) && tmp)
 850                 return 1;
 851
 852         if (expr->type == EXPR_POSTOP)
 853                 return implied_condition_true(expr->unop);
 854
 855         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 856                 return implied_not_equal(expr->unop, 1);
 857         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 858                 return implied_not_equal(expr->unop, -1);
 859
 860         expr = strip_expr(expr);
 861         switch (expr->type) {
 862         case EXPR_COMPARE:
 863                 if (do_comparison_range(expr) == 1)
 864                         return 1;
 865                 break;
 866         case EXPR_PREOP:
 867                 if (expr->op == '!') {
 868                         if (implied_condition_false(expr->unop))
 869                                 return 1;
 870                         break;
 871                 }
 872                 stmt = get_block_thing(expr);
 873                 if (last_stmt_val(stmt, &val) && val == 1)
 874                         return 1;
 875                 break;
 876         default:
 877                 if (implied_not_equal(expr, 0) == 1)
 878                         return 1;
 879                 break;
 880         }
 881         return 0;
 882 }
 883
 884 int implied_condition_false(struct expression *expr)
 885 {
 886         struct statement *stmt;
 887         struct expression *tmp;
 888         long long val;
 889
 890         if (!expr)
 891                 return 0;
 892
 893         if (is_zero(expr))
 894                 return 1;
 895
 896         switch (expr->type) {
 897         case EXPR_COMPARE:
 898                 if (do_comparison_range(expr) == 2)
 899                         return 1;
 900         case EXPR_PREOP:
 901                 if (expr->op == '!') {
 902                         if (implied_condition_true(expr->unop))
 903                                 return 1;
 904                         break;
 905                 }
 906                 stmt = get_block_thing(expr);
 907                 if (last_stmt_val(stmt, &val) && val == 0)
 908                         return 1;
 909                 tmp = strip_expr(expr);
 910                 if (tmp != expr)
 911                         return implied_condition_false(tmp);
 912                 break;
 913         default:
 914                 if (get_implied_value(expr, &val) && val == 0)
 915                         return 1;
 916                 break;
 917         }
 918         return 0;
 919 }
 920
 921 int get_implied_range_list(struct expression *expr, struct range_list **rl)
 922 {
 923         long long val;
 924         struct smatch_state *state;
 925
 926         expr = strip_expr(expr);
 927
 928         state = get_state_expr(my_id, expr);
 929         if (state) {
 930                 *rl = clone_range_list(get_dinfo(state)->value_ranges);
 931                 return 1;
 932         }
 933
 934         if (get_implied_value(expr, &val)) {
 935                 *rl = NULL;
 936                 add_range(rl, val, val);
 937                 return 1;
 938         }
 939
 940         if (expr->type == EXPR_BINOP && expr->op == '%') {
 941                 if (!get_implied_value(expr->right, &val))
 942                         return 0;
 943                 *rl = NULL;
 944                 add_range(rl, 0, val - 1);
 945                 return 1;
 946         }
 947
 948         return 0;
 949 }
 950
 951 int is_whole_range(struct smatch_state *state)
 952 {
 953         struct data_info *dinfo;
 954         struct data_range *drange;
 955
 956         if (!state)
 957                 return 0;
 958         dinfo = get_dinfo(state);
 959         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
 960         if (drange->min == whole_range.min && drange->max == whole_range.max)
 961                 return 1;
 962         return 0;
 963 }
 964
 965 void register_smatch_extra(int id)
 966 {
 967         my_id = id;
 968         add_merge_hook(my_id, &merge_func);
 969         add_unmatched_state_hook(my_id, &unmatched_state);
 970         add_hook(&unop_expr, OP_HOOK);
 971         add_hook(&match_function_def, FUNC_DEF_HOOK);
 972         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 973         add_hook(&match_assign, ASSIGNMENT_HOOK);
 974         add_hook(&match_declarations, DECLARATION_HOOK);
 975 }