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