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