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