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