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
 595         }
 596         if (expr->op == SPECIAL_SUB_ASSIGN) {
 597                 if (get_implied_max(left, &tmp)) {
 598                         if (known)
 599                                 max = tmp - value;
 600                         else
 601                                 max = tmp;
 602                 }
 603
 604         }
 605         set_extra_mod(name, sym, alloc_extra_state_range(min, max));
 606 free:
 607         free_string(name);
 608 }
 609
 610 static void unop_expr(struct expression *expr)
 611 {
 612         struct symbol *sym;
 613         char *name;
 614         long long min = whole_range.min;
 615         long long max = whole_range.max;
 616         long long val;
 617
 618         if (expr->op == '*')
 619                 return;
 620         if (expr->op == '(')
 621                 return;
 622         if (expr->op == '!')
 623                 return;
 624
 625         name = get_variable_from_expr(expr->unop, &sym);
 626         if (!name)
 627                 goto free;
 628         if (expr->op == SPECIAL_INCREMENT) {
 629                 if (get_implied_min(expr->unop, &val))
 630                         min = val + 1;
 631         }
 632         if (expr->op == SPECIAL_DECREMENT) {
 633                 if (get_implied_max(expr->unop, &val))
 634                         max = val - 1;
 635         }
 636         set_extra_mod(name, sym, alloc_extra_state_range(min, max));
 637 free:
 638         free_string(name);
 639 }
 640
 641 static void delete_state_tracker(struct tracker *t)
 642 {
 643         remove_from_equiv(t->name, t->sym);
 644         delete_state(t->owner, t->name, t->sym);
 645 }
 646
 647 static void scoped_state_extra(const char *name, struct symbol *sym)
 648 {
 649         struct tracker *t;
 650
 651         t = alloc_tracker(SMATCH_EXTRA, name, sym);
 652         add_scope_hook((scope_hook *)&delete_state_tracker, t);
 653 }
 654
 655 static void match_declarations(struct symbol *sym)
 656 {
 657         const char *name;
 658
 659         if (sym->ident) {
 660                 name = sym->ident->name;
 661                 if (!sym->initializer) {
 662                         set_state(SMATCH_EXTRA, name, sym, extra_undefined());
 663                         scoped_state_extra(name, sym);
 664                 }
 665         }
 666 }
 667
 668 static void match_function_def(struct symbol *sym)
 669 {
 670         struct symbol *arg;
 671
 672         cur_func = sym;
 673         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 674                 if (!arg->ident) {
 675                         continue;
 676                 }
 677                 set_state(my_id, arg->ident->name, arg, extra_undefined());
 678         } END_FOR_EACH_PTR(arg);
 679 }
 680
 681 static int last_stmt_val(struct statement *stmt, long long *val)
 682 {
 683         struct expression *expr;
 684
 685         if (!stmt)
 686                 return 0;
 687
 688         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 689         if (stmt->type != STMT_EXPRESSION)
 690                 return 0;
 691         expr = stmt->expression;
 692         return get_value(expr, val);
 693 }
 694
 695 static void match_comparison(struct expression *expr)
 696 {
 697         long long fixed;
 698         char *name = NULL;
 699         struct symbol *sym;
 700         struct smatch_state *true_state;
 701         struct smatch_state *false_state;
 702         struct smatch_state *orig;
 703         int left = 0;
 704         int comparison = expr->op;
 705         struct expression *varies = expr->right;
 706
 707         if (!get_value(expr->left, &fixed)) {
 708                 if (!get_value(expr->right, &fixed))
 709                         return;
 710                 varies = strip_expr(expr->left);
 711                 left = 1;
 712         }
 713         if (varies->op == SPECIAL_INCREMENT || varies->op == SPECIAL_DECREMENT)
 714                 varies = varies->unop;
 715         if (varies->type == EXPR_CALL) {
 716                 function_comparison(comparison, varies, fixed, left);
 717                 return;
 718         }
 719
 720         name = get_variable_from_expr(varies, &sym);
 721         if (!name || !sym)
 722                 goto free;
 723
 724         orig = get_state(my_id, name, sym);
 725         if (!orig)
 726                 orig = extra_undefined();
 727
 728         switch (comparison) {
 729         case '<':
 730         case SPECIAL_UNSIGNED_LT:
 731                 if (left) {
 732                         true_state = filter_range(orig, fixed, whole_range.max);
 733                         false_state = filter_range(orig, whole_range.min, fixed - 1);
 734                 } else {
 735                         true_state = filter_range(orig, whole_range.min, fixed);
 736                         false_state = filter_range(orig, fixed + 1, whole_range.max);
 737                 }
 738                 break;
 739         case SPECIAL_UNSIGNED_LTE:
 740         case SPECIAL_LTE:
 741                 if (left) {
 742                         true_state = filter_range(orig, fixed + 1, whole_range.max);
 743                         false_state = filter_range(orig, whole_range.min, fixed);
 744                 } else {
 745                         true_state = filter_range(orig, whole_range.min, fixed - 1);
 746                         false_state = filter_range(orig, fixed, whole_range.max);
 747                 }
 748                 break;
 749         case SPECIAL_EQUAL:
 750                 if (possibly_true(SPECIAL_EQUAL, get_dinfo(orig), fixed, fixed))
 751                         true_state = alloc_extra_state(fixed);
 752                 else
 753                         true_state = alloc_extra_state_empty();
 754                 false_state = filter_range(orig, fixed, fixed);
 755                 break;
 756         case SPECIAL_UNSIGNED_GTE:
 757         case SPECIAL_GTE:
 758                 if (left) {
 759                         true_state = filter_range(orig, whole_range.min, fixed - 1);
 760                         false_state = filter_range(orig, fixed, whole_range.max);
 761                 } else {
 762                         true_state = filter_range(orig, fixed + 1, whole_range.max);
 763                         false_state = filter_range(orig, whole_range.min, fixed);
 764                 }
 765                 break;
 766         case '>':
 767         case SPECIAL_UNSIGNED_GT:
 768                 if (left) {
 769                         true_state = filter_range(orig, whole_range.min, fixed);
 770                         false_state = filter_range(orig, fixed + 1, whole_range.max);
 771                 } else {
 772                         true_state = filter_range(orig, fixed, whole_range.max);
 773                         false_state = filter_range(orig, whole_range.min, fixed - 1);
 774                 }
 775                 break;
 776         case SPECIAL_NOTEQUAL:
 777                 true_state = filter_range(orig, fixed, fixed);
 778                 if (possibly_true(SPECIAL_EQUAL, get_dinfo(orig), fixed, fixed))
 779                         false_state = alloc_extra_state(fixed);
 780                 else
 781                         false_state = alloc_extra_state_empty();
 782                 break;
 783         default:
 784                 sm_msg("unhandled comparison %d\n", comparison);
 785                 goto free;
 786         }
 787         set_extra_true_false(name, sym, true_state, false_state);
 788 free:
 789         free_string(name);
 790 }
 791
 792 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 793 void __extra_match_condition(struct expression *expr)
 794 {
 795         struct symbol *sym;
 796         char *name;
 797         struct smatch_state *pre_state;
 798         struct smatch_state *true_state;
 799         struct smatch_state *false_state;
 800
 801         expr = strip_expr(expr);
 802         switch (expr->type) {
 803         case EXPR_CALL:
 804                 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
 805                 return;
 806         case EXPR_PREOP:
 807         case EXPR_SYMBOL:
 808         case EXPR_DEREF:
 809                 name = get_variable_from_expr(expr, &sym);
 810                 if (!name)
 811                         return;
 812                 pre_state = get_state(my_id, name, sym);
 813                 true_state = add_filter(pre_state, 0);
 814                 if (possibly_true(SPECIAL_EQUAL, get_dinfo(pre_state), 0, 0))
 815                         false_state = alloc_extra_state(0);
 816                 else
 817                         false_state = alloc_extra_state_empty();
 818                 set_extra_true_false(name, sym, true_state, false_state);
 819                 free_string(name);
 820                 return;
 821         case EXPR_COMPARE:
 822                 match_comparison(expr);
 823                 return;
 824         case EXPR_ASSIGNMENT:
 825                 __extra_match_condition(expr->left);
 826                 return;
 827         }
 828 }
 829
 830 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
 831 int implied_not_equal(struct expression *expr, long long val)
 832 {
 833         char *name;
 834         struct symbol *sym;
 835         struct smatch_state *state;
 836         int ret = 0;
 837
 838         name = get_variable_from_expr(expr, &sym);
 839         if (!name || !sym)
 840                 goto exit;
 841         state = get_state(my_id, name, sym);
 842         if (!state || !state->data)
 843                 goto exit;
 844         ret = !possibly_false(SPECIAL_NOTEQUAL, get_dinfo(state), val, 1);
 845 exit:
 846         free_string(name);
 847         return ret;
 848 }
 849
 850 int known_condition_true(struct expression *expr)
 851 {
 852         long long tmp;
 853
 854         if (!expr)
 855                 return 0;
 856
 857         if (get_value(expr, &tmp) && tmp)
 858                 return 1;
 859
 860         expr = strip_expr(expr);
 861         switch (expr->type) {
 862         case EXPR_PREOP:
 863                 if (expr->op == '!') {
 864                         if (known_condition_false(expr->unop))
 865                                 return 1;
 866                         break;
 867                 }
 868                 break;
 869         default:
 870                 break;
 871         }
 872         return 0;
 873 }
 874
 875 int known_condition_false(struct expression *expr)
 876 {
 877         if (!expr)
 878                 return 0;
 879
 880         if (is_zero(expr))
 881                 return 1;
 882
 883         switch (expr->type) {
 884         case EXPR_PREOP:
 885                 if (expr->op == '!') {
 886                         if (known_condition_true(expr->unop))
 887                                 return 1;
 888                         break;
 889                 }
 890                 break;
 891         default:
 892                 break;
 893         }
 894         return 0;
 895 }
 896
 897 static int do_comparison_range(struct expression *expr)
 898 {
 899         struct symbol *sym;
 900         char *name;
 901         struct smatch_state *state;
 902         long long value;
 903         int left = 0;
 904         int poss_true, poss_false;
 905
 906         if (!get_value(expr->left, &value)) {
 907                 if (!get_value(expr->right, &value))
 908                         return 3;
 909                 left = 1;
 910         }
 911         if (left)
 912                 name = get_variable_from_expr(expr->left, &sym);
 913         else
 914                 name = get_variable_from_expr(expr->right, &sym);
 915         if (!name || !sym)
 916                 goto free;
 917         state = get_state(SMATCH_EXTRA, name, sym);
 918         if (!state)
 919                 goto free;
 920         poss_true = possibly_true(expr->op, get_dinfo(state), value, left);
 921         poss_false = possibly_false(expr->op, get_dinfo(state), value, left);
 922         if (!poss_true && !poss_false)
 923                 return 0;
 924         if (poss_true && !poss_false)
 925                 return 1;
 926         if (!poss_true && poss_false)
 927                 return 2;
 928         if (poss_true && poss_false)
 929                 return 3;
 930 free:
 931         free_string(name);
 932         return 3;
 933 }
 934
 935 int implied_condition_true(struct expression *expr)
 936 {
 937         struct statement *stmt;
 938         long long tmp;
 939         long long val;
 940
 941         if (!expr)
 942                 return 0;
 943
 944         if (get_implied_value(expr, &tmp) && tmp)
 945                 return 1;
 946
 947         if (expr->type == EXPR_POSTOP)
 948                 return implied_condition_true(expr->unop);
 949
 950         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 951                 return implied_not_equal(expr->unop, 1);
 952         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 953                 return implied_not_equal(expr->unop, -1);
 954
 955         expr = strip_expr(expr);
 956         switch (expr->type) {
 957         case EXPR_COMPARE:
 958                 if (do_comparison_range(expr) == 1)
 959                         return 1;
 960                 break;
 961         case EXPR_PREOP:
 962                 if (expr->op == '!') {
 963                         if (implied_condition_false(expr->unop))
 964                                 return 1;
 965                         break;
 966                 }
 967                 stmt = get_block_thing(expr);
 968                 if (last_stmt_val(stmt, &val) && val == 1)
 969                         return 1;
 970                 break;
 971         default:
 972                 if (implied_not_equal(expr, 0) == 1)
 973                         return 1;
 974                 break;
 975         }
 976         return 0;
 977 }
 978
 979 int implied_condition_false(struct expression *expr)
 980 {
 981         struct statement *stmt;
 982         struct expression *tmp;
 983         long long val;
 984
 985         if (!expr)
 986                 return 0;
 987
 988         if (is_zero(expr))
 989                 return 1;
 990
 991         switch (expr->type) {
 992         case EXPR_COMPARE:
 993                 if (do_comparison_range(expr) == 2)
 994                         return 1;
 995         case EXPR_PREOP:
 996                 if (expr->op == '!') {
 997                         if (implied_condition_true(expr->unop))
 998                                 return 1;
 999                         break;
1000                 }
1001                 stmt = get_block_thing(expr);
1002                 if (last_stmt_val(stmt, &val) && val == 0)
1003                         return 1;
1004                 tmp = strip_expr(expr);
1005                 if (tmp != expr)
1006                         return implied_condition_false(tmp);
1007                 break;
1008         default:
1009                 if (get_implied_value(expr, &val) && val == 0)
1010                         return 1;
1011                 break;
1012         }
1013         return 0;
1014 }
1015
1016 int get_implied_range_list(struct expression *expr, struct range_list **rl)
1017 {
1018         long long val;
1019         struct smatch_state *state;
1020
1021         expr = strip_expr(expr);
1022
1023         state = get_state_expr(my_id, expr);
1024         if (state) {
1025                 *rl = clone_range_list(get_dinfo(state)->value_ranges);
1026                 return 1;
1027         }
1028
1029         if (get_implied_value(expr, &val)) {
1030                 *rl = NULL;
1031                 add_range(rl, val, val);
1032                 return 1;
1033         }
1034
1035         if (expr->type == EXPR_BINOP && expr->op == '%') {
1036                 if (!get_implied_value(expr->right, &val))
1037                         return 0;
1038                 *rl = NULL;
1039                 add_range(rl, 0, val - 1);
1040                 return 1;
1041         }
1042
1043         return 0;
1044 }
1045
1046 int is_whole_range(struct smatch_state *state)
1047 {
1048         struct data_info *dinfo;
1049         struct data_range *drange;
1050
1051         if (!state)
1052                 return 0;
1053         dinfo = get_dinfo(state);
1054         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
1055         if (drange->min == whole_range.min && drange->max == whole_range.max)
1056                 return 1;
1057         return 0;
1058 }
1059
1060 void register_smatch_extra(int id)
1061 {
1062         my_id = id;
1063         add_merge_hook(my_id, &merge_func);
1064         add_unmatched_state_hook(my_id, &unmatched_state);
1065         add_hook(&unop_expr, OP_HOOK);
1066         add_hook(&match_function_def, FUNC_DEF_HOOK);
1067         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
1068         add_hook(&match_assign, ASSIGNMENT_HOOK);
1069         add_hook(&match_declarations, DECLARATION_HOOK);
1070 }