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