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