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         struct statement *stmt;
 860
 861         if (!expr)
 862                 return 0;
 863
 864         if (get_value(expr, &tmp) && tmp)
 865                 return 1;
 866
 867         expr = strip_expr(expr);
 868         switch (expr->type) {
 869         case EXPR_PREOP:
 870                 if (expr->op == '!') {
 871                         if (known_condition_false(expr->unop))
 872                                 return 1;
 873                         break;
 874                 }
 875                 stmt = get_expression_statement(expr);
 876                 if (last_stmt_val(stmt, &tmp) && tmp == 1)
 877                         return 1;
 878                 break;
 879         default:
 880                 break;
 881         }
 882         return 0;
 883 }
 884
 885 int known_condition_false(struct expression *expr)
 886 {
 887         long long tmp;
 888         struct statement *stmt;
 889
 890         if (!expr)
 891                 return 0;
 892
 893         if (is_zero(expr))
 894                 return 1;
 895
 896         switch (expr->type) {
 897         case EXPR_PREOP:
 898                 if (expr->op == '!') {
 899                         if (known_condition_true(expr->unop))
 900                                 return 1;
 901                         break;
 902                 }
 903                 stmt = get_expression_statement(expr);
 904                 if (last_stmt_val(stmt, &tmp) && tmp == 0)
 905                         return 1;
 906                 break;
 907         default:
 908                 break;
 909         }
 910         return 0;
 911 }
 912
 913 struct range_list *get_range_list(struct expression *expr)
 914 {
 915         long long min;
 916         long long max;
 917         struct range_list *ret = NULL;
 918         struct smatch_state *state;
 919
 920         state = get_state_expr(SMATCH_EXTRA, expr);
 921         if (state)
 922                 return clone_range_list(get_dinfo(state)->value_ranges);
 923         if (!get_absolute_min(expr, &min))
 924                 return NULL;
 925         if (!get_absolute_max(expr, &max))
 926                 return NULL;
 927         add_range(&ret, min, max);
 928         return ret;
 929 }
 930
 931 static int do_comparison(struct expression *expr)
 932 {
 933         struct range_list *left_ranges;
 934         struct range_list *right_ranges;
 935         int poss_true, poss_false;
 936
 937         left_ranges = get_range_list(expr->left);
 938         right_ranges = get_range_list(expr->right);
 939
 940         poss_true = possibly_true_range_lists(left_ranges, expr->op, right_ranges);
 941         poss_false = possibly_false_range_lists(left_ranges, expr->op, right_ranges);
 942
 943         free_range_list(&left_ranges);
 944         free_range_list(&right_ranges);
 945
 946         if (!poss_true && !poss_false)
 947                 return 0;
 948         if (poss_true && !poss_false)
 949                 return 1;
 950         if (!poss_true && poss_false)
 951                 return 2;
 952         return 3;
 953 }
 954
 955 int implied_condition_true(struct expression *expr)
 956 {
 957         struct statement *stmt;
 958         long long tmp;
 959         long long val;
 960
 961         if (!expr)
 962                 return 0;
 963
 964         if (get_implied_value(expr, &tmp) && tmp)
 965                 return 1;
 966
 967         if (expr->type == EXPR_POSTOP)
 968                 return implied_condition_true(expr->unop);
 969
 970         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 971                 return implied_not_equal(expr->unop, 1);
 972         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 973                 return implied_not_equal(expr->unop, -1);
 974
 975         expr = strip_expr(expr);
 976         switch (expr->type) {
 977         case EXPR_COMPARE:
 978                 if (do_comparison(expr) == 1)
 979                         return 1;
 980                 break;
 981         case EXPR_PREOP:
 982                 if (expr->op == '!') {
 983                         if (implied_condition_false(expr->unop))
 984                                 return 1;
 985                         break;
 986                 }
 987                 stmt = get_expression_statement(expr);
 988                 if (last_stmt_val(stmt, &val) && val == 1)
 989                         return 1;
 990                 break;
 991         default:
 992                 if (implied_not_equal(expr, 0) == 1)
 993                         return 1;
 994                 break;
 995         }
 996         return 0;
 997 }
 998
 999 int implied_condition_false(struct expression *expr)
1000 {
1001         struct statement *stmt;
1002         struct expression *tmp;
1003         long long val;
1004
1005         if (!expr)
1006                 return 0;
1007
1008         if (is_zero(expr))
1009                 return 1;
1010
1011         switch (expr->type) {
1012         case EXPR_COMPARE:
1013                 if (do_comparison(expr) == 2)
1014                         return 1;
1015         case EXPR_PREOP:
1016                 if (expr->op == '!') {
1017                         if (implied_condition_true(expr->unop))
1018                                 return 1;
1019                         break;
1020                 }
1021                 stmt = get_expression_statement(expr);
1022                 if (last_stmt_val(stmt, &val) && val == 0)
1023                         return 1;
1024                 tmp = strip_expr(expr);
1025                 if (tmp != expr)
1026                         return implied_condition_false(tmp);
1027                 break;
1028         default:
1029                 if (get_implied_value(expr, &val) && val == 0)
1030                         return 1;
1031                 break;
1032         }
1033         return 0;
1034 }
1035
1036 int get_implied_range_list(struct expression *expr, struct range_list **rl)
1037 {
1038         long long val;
1039         struct smatch_state *state;
1040
1041         expr = strip_expr(expr);
1042
1043         state = get_state_expr(my_id, expr);
1044         if (state) {
1045                 *rl = clone_range_list(get_dinfo(state)->value_ranges);
1046                 return 1;
1047         }
1048
1049         if (get_implied_value(expr, &val)) {
1050                 *rl = NULL;
1051                 add_range(rl, val, val);
1052                 return 1;
1053         }
1054
1055         if (expr->type == EXPR_BINOP && expr->op == '%') {
1056                 if (!get_implied_value(expr->right, &val))
1057                         return 0;
1058                 *rl = NULL;
1059                 add_range(rl, 0, val - 1);
1060                 return 1;
1061         }
1062
1063         return 0;
1064 }
1065
1066 int is_whole_range(struct smatch_state *state)
1067 {
1068         struct data_info *dinfo;
1069         struct data_range *drange;
1070
1071         if (!state)
1072                 return 0;
1073         dinfo = get_dinfo(state);
1074         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
1075         if (drange->min == whole_range.min && drange->max == whole_range.max)
1076                 return 1;
1077         return 0;
1078 }
1079
1080 void register_smatch_extra(int id)
1081 {
1082         my_id = id;
1083         add_merge_hook(my_id, &merge_func);
1084         add_unmatched_state_hook(my_id, &unmatched_state);
1085         add_hook(&unop_expr, OP_HOOK);
1086         add_hook(&match_function_def, FUNC_DEF_HOOK);
1087         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
1088         add_hook(&match_assign, ASSIGNMENT_HOOK);
1089         add_hook(&match_declarations, DECLARATION_HOOK);
1090 }