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