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