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