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