smatch_extra.c

   1 /*
   2  * Copyright (C) 2008 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * smatch_extra.c is supposed to track the value of every variable.
  20  *
  21  */
  22
  23 #include <stdlib.h>
  24 #include <errno.h>
  25 #ifndef __USE_ISOC99
  26 #define __USE_ISOC99
  27 #endif
  28 #include <limits.h>
  29 #include "parse.h"
  30 #include "smatch.h"
  31 #include "smatch_slist.h"
  32 #include "smatch_extra.h"
  33
  34 static int my_id;
  35
  36 struct string_list *__ignored_macros = NULL;
  37 static int in_warn_on_macro(void)
  38 {
  39         struct statement *stmt;
  40         char *tmp;
  41         char *macro;
  42
  43         stmt = get_current_statement();
  44         if (!stmt)
  45                 return 0;
  46         macro = get_macro_name(stmt->pos);
  47         if (!macro)
  48                 return 0;
  49
  50         FOR_EACH_PTR(__ignored_macros, tmp) {
  51                 if (!strcmp(tmp, macro))
  52                         return 1;
  53         } END_FOR_EACH_PTR(tmp);
  54         return 0;
  55 }
  56
  57 typedef void (mod_hook)(const char *name, struct symbol *sym, struct smatch_state *state);
  58 DECLARE_PTR_LIST(void_fn_list, mod_hook *);
  59 static struct void_fn_list *extra_mod_hooks;
  60 void add_extra_mod_hook(mod_hook *fn)
  61 {
  62         mod_hook **p = malloc(sizeof(mod_hook *));
  63         *p = fn;
  64         add_ptr_list(&extra_mod_hooks, p);
  65 }
  66
  67 void call_extra_mod_hooks(const char *name, struct symbol *sym, struct smatch_state *state)
  68 {
  69         mod_hook **fn;
  70
  71         FOR_EACH_PTR(extra_mod_hooks, fn) {
  72                 (*fn)(name, sym, state);
  73         } END_FOR_EACH_PTR(fn);
  74 }
  75
  76 struct sm_state *set_extra_mod(const char *name, struct symbol *sym, struct smatch_state *state)
  77 {
  78         if (in_warn_on_macro())
  79                 return NULL;
  80         remove_from_equiv(name, sym);
  81         call_extra_mod_hooks(name, sym, state);
  82         return set_state(SMATCH_EXTRA, name, sym, state);
  83 }
  84
  85 struct sm_state *set_extra_expr_mod(struct expression *expr, struct smatch_state *state)
  86 {
  87         struct symbol *sym;
  88         char *name;
  89         struct sm_state *ret = NULL;
  90
  91         expr = strip_expr(expr);
  92         name = expr_to_var_sym(expr, &sym);
  93         if (!name || !sym)
  94                 goto free;
  95         ret = set_extra_mod(name, sym, state);
  96 free:
  97         free_string(name);
  98         return ret;
  99 }
 100
 101 void set_extra_nomod(const char *name, struct symbol *sym, struct smatch_state *state)
 102 {
 103         struct relation *rel;
 104         struct smatch_state *orig_state;
 105
 106         orig_state = get_state(SMATCH_EXTRA, name, sym);
 107
 108         if (!estate_related(orig_state)) {
 109                 set_state(SMATCH_EXTRA, name, sym, state);
 110                 return;
 111         }
 112
 113         set_related(state, estate_related(orig_state));
 114         FOR_EACH_PTR(estate_related(orig_state), rel) {
 115                 if (option_debug_related)
 116                         sm_msg("%s updating related %s to %s", name, rel->name, state->name);
 117                 set_state(SMATCH_EXTRA, rel->name, rel->sym, state);
 118         } END_FOR_EACH_PTR(rel);
 119 }
 120
 121 /*
 122  * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
 123  */
 124 void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state)
 125 {
 126         char *name;
 127         struct symbol *sym;
 128
 129         name = expr_to_var_sym(expr, &sym);
 130         if (!name || !sym)
 131                 goto free;
 132         set_extra_nomod(name, sym, state);
 133 free:
 134         free_string(name);
 135
 136 }
 137
 138 static void set_extra_true_false(const char *name, struct symbol *sym,
 139                         struct smatch_state *true_state,
 140                         struct smatch_state *false_state)
 141 {
 142         struct relation *rel;
 143         struct smatch_state *orig_state;
 144
 145         if (in_warn_on_macro())
 146                 return;
 147
 148         orig_state = get_state(SMATCH_EXTRA, name, sym);
 149
 150         if (!estate_related(orig_state)) {
 151                 set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state);
 152                 return;
 153         }
 154
 155         if (true_state)
 156                 set_related(true_state, estate_related(orig_state));
 157         if (false_state)
 158                 set_related(false_state, estate_related(orig_state));
 159
 160         FOR_EACH_PTR(estate_related(orig_state), rel) {
 161                 set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym,
 162                                 true_state, false_state);
 163         } END_FOR_EACH_PTR(rel);
 164 }
 165
 166 static void set_extra_expr_true_false(struct expression *expr,
 167                 struct smatch_state *true_state,
 168                 struct smatch_state *false_state)
 169 {
 170         char *name;
 171         struct symbol *sym;
 172
 173         expr = strip_expr(expr);
 174         name = expr_to_var_sym(expr, &sym);
 175         if (!name || !sym)
 176                 goto free;
 177         set_extra_true_false(name, sym, true_state, false_state);
 178 free:
 179         free_string(name);
 180 }
 181
 182 static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
 183 {
 184         struct expression *iter_var;
 185         struct expression *condition;
 186         struct sm_state *sm;
 187         struct smatch_state *estate;
 188         sval_t start;
 189
 190         condition = strip_expr(loop->iterator_pre_condition);
 191         if (!condition)
 192                 return NULL;
 193         if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
 194                 return NULL;
 195         if (condition->op != SPECIAL_DECREMENT)
 196                 return NULL;
 197
 198         iter_var = condition->unop;
 199         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 200         if (!sm)
 201                 return NULL;
 202         if (sval_cmp_val(estate_min(sm->state), 0) < 0)
 203                 return NULL;
 204         start = estate_max(sm->state);
 205         if  (sval_cmp_val(start, 0) <= 0)
 206                 return NULL;
 207         if (!sval_is_max(start))
 208                 start.value--;
 209
 210         if (condition->type == EXPR_PREOP) {
 211                 estate = alloc_estate_range(sval_type_val(start.type, 1), start);
 212                 if (estate_has_hard_max(sm->state))
 213                         estate_set_hard_max(estate);
 214                 estate_copy_fuzzy_max(estate, sm->state);
 215                 set_extra_expr_mod(iter_var, estate);
 216         }
 217         if (condition->type == EXPR_POSTOP) {
 218                 estate = alloc_estate_range(sval_type_val(start.type, 0), start);
 219                 if (estate_has_hard_max(sm->state))
 220                         estate_set_hard_max(estate);
 221                 estate_copy_fuzzy_max(estate, sm->state);
 222                 set_extra_expr_mod(iter_var, estate);
 223         }
 224         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 225 }
 226
 227 static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr,
 228                                                 struct expression *condition)
 229 {
 230         struct expression *iter_var;
 231         struct sm_state *sm;
 232         struct smatch_state *estate;
 233         sval_t start, end, max;
 234
 235         iter_var = iter_expr->unop;
 236         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 237         if (!sm)
 238                 return NULL;
 239         if (!estate_get_single_value(sm->state, &start))
 240                 return NULL;
 241         if (get_implied_max(condition->right, &end))
 242                 end = sval_cast(get_type(iter_var), end);
 243         else
 244                 end = sval_type_max(get_type(iter_var));
 245
 246         if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
 247                 return NULL;
 248
 249         switch (condition->op) {
 250         case SPECIAL_UNSIGNED_LT:
 251         case SPECIAL_NOTEQUAL:
 252         case '<':
 253                 if (!sval_is_min(end))
 254                         end.value--;
 255                 break;
 256         case SPECIAL_UNSIGNED_LTE:
 257         case SPECIAL_LTE:
 258                 break;
 259         default:
 260                 return NULL;
 261         }
 262         if (sval_cmp(end, start) < 0)
 263                 return NULL;
 264         estate = alloc_estate_range(start, end);
 265         if (get_hard_max(condition->right, &max)) {
 266                 estate_set_hard_max(estate);
 267                 if (condition->op == '<' ||
 268                     condition->op == SPECIAL_UNSIGNED_LT ||
 269                     condition->op == SPECIAL_NOTEQUAL)
 270                         max.value--;
 271                 estate_set_fuzzy_max(estate, max);
 272         }
 273         set_extra_expr_mod(iter_var, estate);
 274         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 275 }
 276
 277 static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr,
 278                                                 struct expression *condition)
 279 {
 280         struct expression *iter_var;
 281         struct sm_state *sm;
 282         struct smatch_state *estate;
 283         sval_t start, end;
 284
 285         iter_var = iter_expr->unop;
 286         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 287         if (!sm)
 288                 return NULL;
 289         if (!estate_get_single_value(sm->state, &start))
 290                 return NULL;
 291         if (!get_implied_min(condition->right, &end))
 292                 end = sval_type_min(get_type(iter_var));
 293         if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
 294                 return NULL;
 295
 296         switch (condition->op) {
 297         case SPECIAL_NOTEQUAL:
 298         case '>':
 299                 if (!sval_is_min(end) && !sval_is_max(end))
 300                         end.value++;
 301                 break;
 302         case SPECIAL_GTE:
 303                 break;
 304         default:
 305                 return NULL;
 306         }
 307         if (sval_cmp(end, start) > 0)
 308                 return NULL;
 309         estate = alloc_estate_range(end, start);
 310         estate_set_hard_max(estate);
 311         estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate));
 312         set_extra_expr_mod(iter_var, estate);
 313         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 314 }
 315
 316 static struct sm_state *handle_canonical_for_loops(struct statement *loop)
 317 {
 318         struct expression *iter_expr;
 319         struct expression *condition;
 320
 321         if (!loop->iterator_post_statement)
 322                 return NULL;
 323         if (loop->iterator_post_statement->type != STMT_EXPRESSION)
 324                 return NULL;
 325         iter_expr = loop->iterator_post_statement->expression;
 326         if (!loop->iterator_pre_condition)
 327                 return NULL;
 328         if (loop->iterator_pre_condition->type != EXPR_COMPARE)
 329                 return NULL;
 330         condition = loop->iterator_pre_condition;
 331
 332         if (iter_expr->op == SPECIAL_INCREMENT)
 333                 return handle_canonical_for_inc(iter_expr, condition);
 334         if (iter_expr->op == SPECIAL_DECREMENT)
 335                 return handle_canonical_for_dec(iter_expr, condition);
 336         return NULL;
 337 }
 338
 339 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree)
 340 {
 341         struct sm_state *ret;
 342
 343         __push_fake_cur_stree();
 344         if (!loop->iterator_post_statement)
 345                 ret = handle_canonical_while_count_down(loop);
 346         else
 347                 ret = handle_canonical_for_loops(loop);
 348         *stree = __pop_fake_cur_stree();
 349         return ret;
 350 }
 351
 352 int __iterator_unchanged(struct sm_state *sm)
 353 {
 354         if (!sm)
 355                 return 0;
 356         if (get_sm_state(my_id, sm->name, sm->sym) == sm)
 357                 return 1;
 358         return 0;
 359 }
 360
 361 static void while_count_down_after(struct sm_state *sm, struct expression *condition)
 362 {
 363         sval_t after_value;
 364
 365         /* paranoid checking.  prolly not needed */
 366         condition = strip_expr(condition);
 367         if (!condition)
 368                 return;
 369         if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
 370                 return;
 371         if (condition->op != SPECIAL_DECREMENT)
 372                 return;
 373         after_value = estate_min(sm->state);
 374         after_value.value--;
 375         set_extra_mod(sm->name, sm->sym, alloc_estate_sval(after_value));
 376 }
 377
 378 void __extra_pre_loop_hook_after(struct sm_state *sm,
 379                                 struct statement *iterator,
 380                                 struct expression *condition)
 381 {
 382         struct expression *iter_expr;
 383         sval_t limit;
 384         struct smatch_state *state;
 385
 386         if (!iterator) {
 387                 while_count_down_after(sm, condition);
 388                 return;
 389         }
 390
 391         iter_expr = iterator->expression;
 392
 393         if (condition->type != EXPR_COMPARE)
 394                 return;
 395         if (iter_expr->op == SPECIAL_INCREMENT) {
 396                 limit = sval_binop(estate_max(sm->state), '+',
 397                                    sval_type_val(estate_type(sm->state), 1));
 398         } else {
 399                 limit = sval_binop(estate_min(sm->state), '-',
 400                                    sval_type_val(estate_type(sm->state), 1));
 401         }
 402         if (!estate_has_hard_max(sm->state) && !__has_breaks()) {
 403                 if (iter_expr->op == SPECIAL_INCREMENT)
 404                         state = alloc_estate_range(estate_min(sm->state), limit);
 405                 else
 406                         state = alloc_estate_range(limit, estate_max(sm->state));
 407         } else {
 408                 state = alloc_estate_sval(limit);
 409         }
 410         if (!estate_has_hard_max(sm->state)) {
 411                 estate_clear_hard_max(state);
 412         }
 413         if (estate_has_fuzzy_max(sm->state)) {
 414                 sval_t hmax = estate_get_fuzzy_max(sm->state);
 415                 sval_t max = estate_max(sm->state);
 416
 417                 if (sval_cmp(hmax, max) != 0)
 418                         estate_clear_fuzzy_max(state);
 419         } else if (!estate_has_fuzzy_max(sm->state)) {
 420                 estate_clear_fuzzy_max(state);
 421         }
 422
 423         set_extra_mod(sm->name, sm->sym, state);
 424 }
 425
 426 static struct stree *unmatched_stree;
 427 static struct smatch_state *unmatched_state(struct sm_state *sm)
 428 {
 429         struct smatch_state *state;
 430
 431         if (unmatched_stree) {
 432                 state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym);
 433                 if (state)
 434                         return state;
 435         }
 436         if (parent_is_gone_var_sym(sm->name, sm->sym))
 437                 return alloc_estate_empty();
 438         return alloc_estate_whole(estate_type(sm->state));
 439 }
 440
 441 static void clear_the_pointed_at(struct expression *expr)
 442 {
 443         struct stree *stree;
 444         char *name;
 445         struct symbol *sym;
 446         struct sm_state *tmp;
 447
 448         name = expr_to_var_sym(expr, &sym);
 449         if (!name || !sym)
 450                 goto free;
 451
 452         stree = __get_cur_stree();
 453         FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) {
 454                 if (tmp->name[0] != '*')
 455                         continue;
 456                 if (tmp->sym != sym)
 457                         continue;
 458                 if (strcmp(tmp->name + 1, name) != 0)
 459                         continue;
 460                 set_extra_mod(tmp->name, tmp->sym, alloc_estate_whole(estate_type(tmp->state)));
 461         } END_FOR_EACH_SM(tmp);
 462
 463 free:
 464         free_string(name);
 465 }
 466
 467 static void match_function_call(struct expression *expr)
 468 {
 469         struct expression *arg;
 470         struct expression *tmp;
 471
 472         /* if we have the db this is handled in smatch_function_hooks.c */
 473         if (!option_no_db)
 474                 return;
 475         if (inlinable(expr->fn))
 476                 return;
 477
 478         FOR_EACH_PTR(expr->args, arg) {
 479                 tmp = strip_expr(arg);
 480                 if (tmp->type == EXPR_PREOP && tmp->op == '&')
 481                         set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop)));
 482                 else
 483                         clear_the_pointed_at(tmp);
 484         } END_FOR_EACH_PTR(arg);
 485 }
 486
 487 static int types_equiv_or_pointer(struct symbol *one, struct symbol *two)
 488 {
 489         if (!one || !two)
 490                 return 0;
 491         if (one->type == SYM_PTR && two->type == SYM_PTR)
 492                 return 1;
 493         return types_equiv(one, two);
 494 }
 495
 496 static bool is_non_null_array(struct expression *expr)
 497 {
 498         struct symbol *type;
 499         struct symbol *sym;
 500         struct symbol *tmp;
 501         char *name;
 502         int i;
 503
 504         type = get_type(expr);
 505         if (!type || type->type != SYM_ARRAY)
 506                 return 0;
 507         if (expr->type == EXPR_SYMBOL)
 508                 return 1;
 509         if (implied_not_equal(expr, 0))
 510                 return 1;
 511
 512         /* verify that it's not the first member of the struct */
 513         if (expr->type != EXPR_DEREF || !expr->member)
 514                 return 0;
 515         name = expr_to_var_sym(expr, &sym);
 516         free_string(name);
 517         if (!name || !sym)
 518                 return 0;
 519         type = get_real_base_type(sym);
 520         if (!type || type->type != SYM_PTR)
 521                 return 0;
 522         type = get_real_base_type(type);
 523         if (type->type != SYM_STRUCT)
 524                 return 0;
 525
 526         i = 0;
 527         FOR_EACH_PTR(type->symbol_list, tmp) {
 528                 i++;
 529                 if (!tmp->ident)
 530                         continue;
 531                 if (strcmp(expr->member->name, tmp->ident->name) == 0) {
 532                         if (i == 1)
 533                                 return 0;
 534                         return 1;
 535                 }
 536         } END_FOR_EACH_PTR(tmp);
 537
 538         return 0;
 539 }
 540
 541 static void match_vanilla_assign(struct expression *left, struct expression *right)
 542 {
 543         struct range_list *rl = NULL;
 544         struct symbol *right_sym;
 545         struct symbol *left_type;
 546         struct symbol *right_type;
 547         char *right_name = NULL;
 548         struct symbol *sym;
 549         char *name;
 550         sval_t max;
 551         struct smatch_state *state;
 552
 553         if (is_struct(left))
 554                 return;
 555
 556         name = expr_to_var_sym(left, &sym);
 557         if (!name)
 558                 return;
 559
 560         left_type = get_type(left);
 561         right_type = get_type(right);
 562
 563         right_name = expr_to_var_sym(right, &right_sym);
 564
 565         if (!(right->type == EXPR_PREOP && right->op == '&') &&
 566             right_name && right_sym &&
 567             types_equiv_or_pointer(left_type, right_type) &&
 568             !has_symbol(right, sym)) {
 569                 set_equiv(left, right);
 570                 goto free;
 571         }
 572
 573         if (is_non_null_array(right)) {
 574                 state = alloc_estate_range(array_min_sval, array_max_sval);
 575         } else if (get_implied_rl(right, &rl)) {
 576                 rl = cast_rl(left_type, rl);
 577                 state = alloc_estate_rl(rl);
 578                 if (get_hard_max(right, &max)) {
 579                         estate_set_hard_max(state);
 580                         estate_set_fuzzy_max(state, max);
 581                 }
 582         } else {
 583                 rl = alloc_whole_rl(right_type);
 584                 rl = cast_rl(left_type, rl);
 585                 state = alloc_estate_rl(rl);
 586         }
 587         set_extra_mod(name, sym, state);
 588 free:
 589         free_string(right_name);
 590 }
 591
 592 static int op_remove_assign(int op)
 593 {
 594         switch (op) {
 595         case SPECIAL_ADD_ASSIGN:
 596                 return '+';
 597         case SPECIAL_SUB_ASSIGN:
 598                 return '-';
 599         case SPECIAL_MUL_ASSIGN:
 600                 return '*';
 601         case SPECIAL_DIV_ASSIGN:
 602                 return '/';
 603         case SPECIAL_MOD_ASSIGN:
 604                 return '%';
 605         case SPECIAL_AND_ASSIGN:
 606                 return '&';
 607         case SPECIAL_OR_ASSIGN:
 608                 return '|';
 609         case SPECIAL_XOR_ASSIGN:
 610                 return '^';
 611         case SPECIAL_SHL_ASSIGN:
 612                 return SPECIAL_LEFTSHIFT;
 613         case SPECIAL_SHR_ASSIGN:
 614                 return SPECIAL_RIGHTSHIFT;
 615         default:
 616                 return op;
 617         }
 618 }
 619
 620 static void match_assign(struct expression *expr)
 621 {
 622         struct range_list *rl = NULL;
 623         struct expression *left;
 624         struct expression *right;
 625         struct expression *binop_expr;
 626         struct symbol *left_type;
 627         struct symbol *right_type;
 628         struct symbol *sym;
 629         char *name;
 630         sval_t left_min, left_max;
 631         sval_t right_min, right_max;
 632         sval_t res_min, res_max;
 633
 634         left = strip_expr(expr->left);
 635
 636         right = strip_expr(expr->right);
 637         while (right->type == EXPR_ASSIGNMENT && right->op == '=')
 638                 right = strip_expr(right->left);
 639
 640         if (is_condition(expr->right))
 641                 return; /* handled in smatch_condition.c */
 642         if (expr->op == '=' && right->type == EXPR_CALL)
 643                 return; /* handled in smatch_function_hooks.c */
 644         if (expr->op == '=') {
 645                 match_vanilla_assign(left, right);
 646                 return;
 647         }
 648
 649         name = expr_to_var_sym(left, &sym);
 650         if (!name)
 651                 return;
 652
 653         left_type = get_type(left);
 654         right_type = get_type(right);
 655
 656         res_min = sval_type_min(left_type);
 657         res_max = sval_type_max(left_type);
 658
 659         switch (expr->op) {
 660         case SPECIAL_ADD_ASSIGN:
 661                 get_absolute_max(left, &left_max);
 662                 get_absolute_max(right, &right_max);
 663                 if (sval_binop_overflows(left_max, '+', right_max))
 664                         break;
 665                 if (get_implied_min(left, &left_min) &&
 666                     !sval_is_negative_min(left_min) &&
 667                     get_implied_min(right, &right_min) &&
 668                     !sval_is_negative_min(right_min)) {
 669                         res_min = sval_binop(left_min, '+', right_min);
 670                         res_min = sval_cast(right_type, res_min);
 671                 }
 672                 if (inside_loop())  /* we are assuming loops don't lead to wrapping */
 673                         break;
 674                 res_max = sval_binop(left_max, '+', right_max);
 675                 res_max = sval_cast(right_type, res_max);
 676                 break;
 677         case SPECIAL_SUB_ASSIGN:
 678                 if (get_implied_max(left, &left_max) &&
 679                     !sval_is_max(left_max) &&
 680                     get_implied_min(right, &right_min) &&
 681                     !sval_is_min(right_min)) {
 682                         res_max = sval_binop(left_max, '-', right_min);
 683                         res_max = sval_cast(right_type, res_max);
 684                 }
 685                 if (inside_loop())
 686                         break;
 687                 if (get_implied_min(left, &left_min) &&
 688                     !sval_is_min(left_min) &&
 689                     get_implied_max(right, &right_max) &&
 690                     !sval_is_max(right_max)) {
 691                         res_min = sval_binop(left_min, '-', right_max);
 692                         res_min = sval_cast(right_type, res_min);
 693                 }
 694                 break;
 695         case SPECIAL_AND_ASSIGN:
 696         case SPECIAL_MOD_ASSIGN:
 697         case SPECIAL_SHL_ASSIGN:
 698         case SPECIAL_SHR_ASSIGN:
 699         case SPECIAL_OR_ASSIGN:
 700         case SPECIAL_XOR_ASSIGN:
 701         case SPECIAL_MUL_ASSIGN:
 702         case SPECIAL_DIV_ASSIGN:
 703                 binop_expr = binop_expression(expr->left,
 704                                               op_remove_assign(expr->op),
 705                                               expr->right);
 706                 if (get_absolute_rl(binop_expr, &rl)) {
 707                         rl = cast_rl(left_type, rl);
 708                         set_extra_mod(name, sym, alloc_estate_rl(rl));
 709                         goto free;
 710                 }
 711                 break;
 712         }
 713         rl = cast_rl(left_type, alloc_rl(res_min, res_max));
 714         set_extra_mod(name, sym, alloc_estate_rl(rl));
 715 free:
 716         free_string(name);
 717 }
 718
 719 static struct smatch_state *increment_state(struct smatch_state *state)
 720 {
 721         sval_t min = estate_min(state);
 722         sval_t max = estate_max(state);
 723
 724         if (!estate_rl(state))
 725                 return NULL;
 726
 727         if (inside_loop())
 728                 max = sval_type_max(max.type);
 729
 730         if (!sval_is_min(min) && !sval_is_max(min))
 731                 min.value++;
 732         if (!sval_is_min(max) && !sval_is_max(max))
 733                 max.value++;
 734         return alloc_estate_range(min, max);
 735 }
 736
 737 static struct smatch_state *decrement_state(struct smatch_state *state)
 738 {
 739         sval_t min = estate_min(state);
 740         sval_t max = estate_max(state);
 741
 742         if (!estate_rl(state))
 743                 return NULL;
 744
 745         if (inside_loop())
 746                 min = sval_type_min(min.type);
 747
 748         if (!sval_is_min(min) && !sval_is_max(min))
 749                 min.value--;
 750         if (!sval_is_min(max) && !sval_is_max(max))
 751                 max.value--;
 752         return alloc_estate_range(min, max);
 753 }
 754
 755 static void unop_expr(struct expression *expr)
 756 {
 757         struct smatch_state *state;
 758
 759         if (expr->smatch_flags & Handled)
 760                 return;
 761
 762         switch (expr->op) {
 763         case SPECIAL_INCREMENT:
 764                 state = get_state_expr(SMATCH_EXTRA, expr->unop);
 765                 state = increment_state(state);
 766                 if (!state)
 767                         state = alloc_estate_whole(get_type(expr));
 768                 set_extra_expr_mod(expr->unop, state);
 769                 break;
 770         case SPECIAL_DECREMENT:
 771                 state = get_state_expr(SMATCH_EXTRA, expr->unop);
 772                 state = decrement_state(state);
 773                 if (!state)
 774                         state = alloc_estate_whole(get_type(expr));
 775                 set_extra_expr_mod(expr->unop, state);
 776                 break;
 777         default:
 778                 return;
 779         }
 780 }
 781
 782 static void asm_expr(struct statement *stmt)
 783 {
 784
 785         struct expression *expr;
 786         struct symbol *type;
 787         int state = 0;
 788
 789         FOR_EACH_PTR(stmt->asm_outputs, expr) {
 790                 switch (state) {
 791                 case 0: /* identifier */
 792                 case 1: /* constraint */
 793                         state++;
 794                         continue;
 795                 case 2: /* expression */
 796                         state = 0;
 797                         type = get_type(strip_expr(expr));
 798                         set_extra_expr_mod(expr, alloc_estate_whole(type));
 799                         continue;
 800                 }
 801         } END_FOR_EACH_PTR(expr);
 802 }
 803
 804 static void delete_state_tracker(struct tracker *t)
 805 {
 806         remove_from_equiv(t->name, t->sym);
 807         delete_state(t->owner, t->name, t->sym);
 808 }
 809
 810 static void scoped_state_extra(const char *name, struct symbol *sym)
 811 {
 812         struct tracker *t;
 813
 814         t = alloc_tracker(SMATCH_EXTRA, name, sym);
 815         add_scope_hook((scope_hook *)&delete_state_tracker, t);
 816 }
 817
 818 static void match_declarations(struct symbol *sym)
 819 {
 820         const char *name;
 821
 822         if (sym->ident) {
 823                 name = sym->ident->name;
 824                 if (!sym->initializer) {
 825                         set_state(SMATCH_EXTRA, name, sym, alloc_estate_whole(get_real_base_type(sym)));
 826                         scoped_state_extra(name, sym);
 827                 }
 828         }
 829 }
 830
 831 static void check_dereference(struct expression *expr)
 832 {
 833         if (outside_of_function())
 834                 return;
 835         set_extra_expr_nomod(expr, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 836 }
 837
 838 static void match_dereferences(struct expression *expr)
 839 {
 840         if (expr->type != EXPR_PREOP)
 841                 return;
 842         check_dereference(expr->unop);
 843 }
 844
 845 static void match_pointer_as_array(struct expression *expr)
 846 {
 847         if (!is_array(expr))
 848                 return;
 849         check_dereference(expr->unop->left);
 850 }
 851
 852 static void set_param_dereferenced(struct expression *arg, char *key, char *unused)
 853 {
 854         struct symbol *sym;
 855         char *name;
 856
 857         name = get_variable_from_key(arg, key, &sym);
 858         if (!name || !sym)
 859                 goto free;
 860
 861         set_extra_nomod(name, sym, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 862
 863 free:
 864         free_string(name);
 865 }
 866
 867 static void match_function_def(struct symbol *sym)
 868 {
 869         struct symbol *arg;
 870
 871         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 872                 if (!arg->ident)
 873                         continue;
 874                 set_state(my_id, arg->ident->name, arg, alloc_estate_whole(get_real_base_type(arg)));
 875         } END_FOR_EACH_PTR(arg);
 876 }
 877
 878 static sval_t add_one(sval_t sval)
 879 {
 880         sval.value++;
 881         return sval;
 882 }
 883
 884 static sval_t sub_one(sval_t sval)
 885 {
 886         sval.value--;
 887         return sval;
 888 }
 889
 890 static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right)
 891 {
 892         struct range_list *left_orig;
 893         struct range_list *left_true;
 894         struct range_list *left_false;
 895         struct range_list *right_orig;
 896         struct range_list *right_true;
 897         struct range_list *right_false;
 898         struct smatch_state *left_true_state;
 899         struct smatch_state *left_false_state;
 900         struct smatch_state *right_true_state;
 901         struct smatch_state *right_false_state;
 902         sval_t min, max, dummy, hard_max;
 903         int left_postop = 0;
 904         int right_postop = 0;
 905
 906         if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) {
 907                 if (left->type == EXPR_POSTOP) {
 908                         left->smatch_flags |= Handled;
 909                         left_postop = left->op;
 910                 }
 911                 left = strip_expr(left->unop);
 912         }
 913         while (left->type == EXPR_ASSIGNMENT)
 914                 left = strip_expr(left->left);
 915
 916         if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) {
 917                 if (right->type == EXPR_POSTOP) {
 918                         right->smatch_flags |= Handled;
 919                         right_postop = right->op;
 920                 }
 921                 right = strip_expr(right->unop);
 922         }
 923
 924         if (get_implied_rl(left, &left_orig)) {
 925                 left_orig = cast_rl(type, left_orig);
 926         } else {
 927                 min = sval_type_min(get_type(left));
 928                 max = sval_type_max(get_type(left));
 929                 left_orig = cast_rl(type, alloc_rl(min, max));
 930         }
 931
 932         if (get_implied_rl(right, &right_orig)) {
 933                 right_orig = cast_rl(type, right_orig);
 934         } else {
 935                 min = sval_type_min(get_type(right));
 936                 max = sval_type_max(get_type(right));
 937                 right_orig = cast_rl(type, alloc_rl(min, max));
 938         }
 939         min = sval_type_min(type);
 940         max = sval_type_max(type);
 941
 942         left_true = clone_rl(left_orig);
 943         left_false = clone_rl(left_orig);
 944         right_true = clone_rl(right_orig);
 945         right_false = clone_rl(right_orig);
 946
 947         switch (op) {
 948         case '<':
 949         case SPECIAL_UNSIGNED_LT:
 950                 left_true = remove_range(left_orig, rl_max(right_orig), max);
 951                 if (!sval_is_min(rl_min(right_orig))) {
 952                         left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
 953                 }
 954
 955                 right_true = remove_range(right_orig, min, rl_min(left_orig));
 956                 if (!sval_is_max(rl_max(left_orig)))
 957                         right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
 958                 break;
 959         case SPECIAL_UNSIGNED_LTE:
 960         case SPECIAL_LTE:
 961                 if (!sval_is_max(rl_max(right_orig)))
 962                         left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
 963                 left_false = remove_range(left_orig, min, rl_min(right_orig));
 964
 965                 if (!sval_is_min(rl_min(left_orig)))
 966                         right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
 967                 right_false = remove_range(right_orig, rl_max(left_orig), max);
 968
 969                 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
 970                         left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
 971                 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
 972                         right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
 973                 break;
 974         case SPECIAL_EQUAL:
 975                 if (!sval_is_max(rl_max(right_orig))) {
 976                         left_true = remove_range(left_true, add_one(rl_max(right_orig)), max);
 977                 }
 978                 if (!sval_is_min(rl_min(right_orig))) {
 979                         left_true = remove_range(left_true, min, sub_one(rl_min(right_orig)));
 980                 }
 981                 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
 982                         left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
 983
 984                 if (!sval_is_max(rl_max(left_orig)))
 985                         right_true = remove_range(right_true, add_one(rl_max(left_orig)), max);
 986                 if (!sval_is_min(rl_min(left_orig)))
 987                         right_true = remove_range(right_true, min, sub_one(rl_min(left_orig)));
 988                 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
 989                         right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
 990                 break;
 991         case SPECIAL_UNSIGNED_GTE:
 992         case SPECIAL_GTE:
 993                 if (!sval_is_min(rl_min(right_orig)))
 994                         left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
 995                 left_false = remove_range(left_orig, rl_max(right_orig), max);
 996
 997                 if (!sval_is_max(rl_max(left_orig)))
 998                         right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
 999                 right_false = remove_range(right_orig, min, rl_min(left_orig));
1000
1001                 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
1002                         right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
1003                 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
1004                         left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
1005                 break;
1006         case '>':
1007         case SPECIAL_UNSIGNED_GT:
1008                 left_true = remove_range(left_orig, min, rl_min(right_orig));
1009                 if (!sval_is_max(rl_max(right_orig)))
1010                         left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
1011
1012                 right_true = remove_range(right_orig, rl_max(left_orig), max);
1013                 if (!sval_is_min(rl_min(left_orig)))
1014                         right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
1015                 break;
1016         case SPECIAL_NOTEQUAL:
1017                 if (!sval_is_max(rl_max(right_orig)))
1018                         left_false = remove_range(left_false, add_one(rl_max(right_orig)), max);
1019                 if (!sval_is_min(rl_min(right_orig)))
1020                         left_false = remove_range(left_false, min, sub_one(rl_min(right_orig)));
1021                 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
1022                         left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
1023
1024                 if (!sval_is_max(rl_max(left_orig)))
1025                         right_false = remove_range(right_false, add_one(rl_max(left_orig)), max);
1026                 if (!sval_is_min(rl_min(left_orig)))
1027                         right_false = remove_range(right_false, min, sub_one(rl_min(left_orig)));
1028                 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
1029                         right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
1030                 break;
1031         default:
1032                 return;
1033         }
1034
1035         left_true = rl_truncate_cast(get_type(left), left_true);
1036         left_false = rl_truncate_cast(get_type(left), left_false);
1037         right_true = rl_truncate_cast(get_type(right), right_true);
1038         right_false = rl_truncate_cast(get_type(right), right_false);
1039
1040         left_true_state = alloc_estate_rl(left_true);
1041         left_false_state = alloc_estate_rl(left_false);
1042         right_true_state = alloc_estate_rl(right_true);
1043         right_false_state = alloc_estate_rl(right_false);
1044
1045         switch (op) {
1046         case '<':
1047         case SPECIAL_UNSIGNED_LT:
1048         case SPECIAL_UNSIGNED_LTE:
1049         case SPECIAL_LTE:
1050                 if (get_hard_max(right, &dummy))
1051                         estate_set_hard_max(left_true_state);
1052                 if (get_hard_max(left, &dummy))
1053                         estate_set_hard_max(right_false_state);
1054                 break;
1055         case '>':
1056         case SPECIAL_UNSIGNED_GT:
1057         case SPECIAL_UNSIGNED_GTE:
1058         case SPECIAL_GTE:
1059                 if (get_hard_max(left, &dummy))
1060                         estate_set_hard_max(right_true_state);
1061                 if (get_hard_max(right, &dummy))
1062                         estate_set_hard_max(left_false_state);
1063                 break;
1064         }
1065
1066         switch (op) {
1067         case '<':
1068         case SPECIAL_UNSIGNED_LT:
1069         case SPECIAL_UNSIGNED_LTE:
1070         case SPECIAL_LTE:
1071                 if (get_hard_max(right, &hard_max)) {
1072                         if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1073                                 hard_max.value--;
1074                         estate_set_fuzzy_max(left_true_state, hard_max);
1075                 }
1076                 if (get_implied_value(right, &hard_max)) {
1077                         if (op == SPECIAL_UNSIGNED_LTE ||
1078                             op == SPECIAL_LTE)
1079                                 hard_max.value++;
1080                         estate_set_fuzzy_max(left_false_state, hard_max);
1081                 }
1082                 if (get_hard_max(left, &hard_max)) {
1083                         if (op == SPECIAL_UNSIGNED_LTE ||
1084                             op == SPECIAL_LTE)
1085                                 hard_max.value--;
1086                         estate_set_fuzzy_max(right_false_state, hard_max);
1087                 }
1088                 if (get_implied_value(left, &hard_max)) {
1089                         if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1090                                 hard_max.value++;
1091                         estate_set_fuzzy_max(right_true_state, hard_max);
1092                 }
1093                 break;
1094         case '>':
1095         case SPECIAL_UNSIGNED_GT:
1096         case SPECIAL_UNSIGNED_GTE:
1097         case SPECIAL_GTE:
1098                 if (get_hard_max(left, &hard_max)) {
1099                         if (op == '>' || op == SPECIAL_UNSIGNED_GT)
1100                                 hard_max.value--;
1101                         estate_set_fuzzy_max(right_true_state, hard_max);
1102                 }
1103                 if (get_implied_value(left, &hard_max)) {
1104                         if (op == SPECIAL_UNSIGNED_GTE ||
1105                             op == SPECIAL_GTE)
1106                                 hard_max.value++;
1107                         estate_set_fuzzy_max(right_false_state, hard_max);
1108                 }
1109                 if (get_hard_max(right, &hard_max)) {
1110                         if (op == SPECIAL_UNSIGNED_LTE ||
1111                             op == SPECIAL_LTE)
1112                                 hard_max.value--;
1113                         estate_set_fuzzy_max(left_false_state, hard_max);
1114                 }
1115                 if (get_implied_value(right, &hard_max)) {
1116                         if (op == '>' ||
1117                             op == SPECIAL_UNSIGNED_GT)
1118                                 hard_max.value++;
1119                         estate_set_fuzzy_max(left_true_state, hard_max);
1120                 }
1121                 break;
1122         case SPECIAL_EQUAL:
1123                 if (get_hard_max(left, &hard_max))
1124                         estate_set_fuzzy_max(right_true_state, hard_max);
1125                 if (get_hard_max(right, &hard_max))
1126                         estate_set_fuzzy_max(left_true_state, hard_max);
1127                 break;
1128         }
1129
1130         if (get_hard_max(left, &hard_max)) {
1131                 estate_set_hard_max(left_true_state);
1132                 estate_set_hard_max(left_false_state);
1133         }
1134         if (get_hard_max(right, &hard_max)) {
1135                 estate_set_hard_max(right_true_state);
1136                 estate_set_hard_max(right_false_state);
1137         }
1138
1139         if (left_postop == SPECIAL_INCREMENT) {
1140                 left_true_state = increment_state(left_true_state);
1141                 left_false_state = increment_state(left_false_state);
1142         }
1143         if (left_postop == SPECIAL_DECREMENT) {
1144                 left_true_state = decrement_state(left_true_state);
1145                 left_false_state = decrement_state(left_false_state);
1146         }
1147         if (right_postop == SPECIAL_INCREMENT) {
1148                 right_true_state = increment_state(right_true_state);
1149                 right_false_state = increment_state(right_false_state);
1150         }
1151         if (right_postop == SPECIAL_DECREMENT) {
1152                 right_true_state = decrement_state(right_true_state);
1153                 right_false_state = decrement_state(right_false_state);
1154         }
1155
1156         set_extra_expr_true_false(left, left_true_state, left_false_state);
1157         set_extra_expr_true_false(right, right_true_state, right_false_state);
1158 }
1159
1160 static int opposite_op(int op)
1161 {
1162         switch (op) {
1163         case '+':
1164                 return '-';
1165         case '-':
1166                 return '+';
1167         case '*':
1168                 return '/';
1169         }
1170         return 0;
1171 }
1172
1173 static int is_simple_math(struct expression *expr)
1174 {
1175         if (!expr)
1176                 return 0;
1177         if (expr->type != EXPR_BINOP)
1178                 return 0;
1179         if (!opposite_op(expr->op))
1180                 return 0;
1181         return 1;
1182 }
1183
1184 static void move_known_values(struct expression **left_p, struct expression **right_p)
1185 {
1186         struct expression *left = *left_p;
1187         struct expression *right = *right_p;
1188         sval_t sval;
1189
1190         if (get_implied_value(left, &sval)) {
1191                 if (!is_simple_math(right))
1192                         return;
1193                 if (right->op == '*') {
1194                         sval_t divisor;
1195
1196                         if (!get_value(right->right, &divisor))
1197                                 return;
1198                         if (divisor.value == 0 && sval.value % divisor.value)
1199                                 return;
1200                         *left_p = binop_expression(left, opposite_op(right->op), right->right);
1201                         *right_p = right->left;
1202                         return;
1203                 }
1204                 if (right->op == '+' && get_value(right->left, &sval)) {
1205                         *left_p = binop_expression(left, opposite_op(right->op), right->left);
1206                         *right_p = right->right;
1207                         return;
1208                 }
1209                 if (get_value(right->right, &sval)) {
1210                         *left_p = binop_expression(left, opposite_op(right->op), right->right);
1211                         *right_p = right->left;
1212                         return;
1213                 }
1214                 return;
1215         }
1216         if (get_implied_value(right, &sval)) {
1217                 if (!is_simple_math(left))
1218                         return;
1219                 if (left->op == '*') {
1220                         sval_t divisor;
1221
1222                         if (!get_value(left->right, &divisor))
1223                                 return;
1224                         if (divisor.value == 0 && sval.value % divisor.value)
1225                                 return;
1226                         *right_p = binop_expression(right, opposite_op(left->op), left->right);
1227                         *left_p = left->left;
1228                         return;
1229                 }
1230                 if (left->op == '+' && get_value(left->left, &sval)) {
1231                         *right_p = binop_expression(right, opposite_op(left->op), left->left);
1232                         *left_p = left->right;
1233                         return;
1234                 }
1235
1236                 if (get_value(left->right, &sval)) {
1237                         *right_p = binop_expression(right, opposite_op(left->op), left->right);
1238                         *left_p = left->left;
1239                         return;
1240                 }
1241                 return;
1242         }
1243 }
1244
1245 static int match_func_comparison(struct expression *expr)
1246 {
1247         struct expression *left = strip_expr(expr->left);
1248         struct expression *right = strip_expr(expr->right);
1249         sval_t sval;
1250
1251         /*
1252          * fixme: think about this harder. We should always be trying to limit
1253          * the non-call side as well.  If we can't determine the limitter does
1254          * that mean we aren't querying the database and are missing important
1255          * information?
1256          */
1257
1258         if (left->type == EXPR_CALL) {
1259                 if (get_implied_value(left, &sval)) {
1260                         handle_comparison(get_type(expr), left, expr->op, right);
1261                         return 1;
1262                 }
1263                 if (!get_implied_value(right, &sval))
1264                         return 1;
1265                 function_comparison(expr->op, left, sval, 1);
1266                 return 1;
1267         }
1268
1269         if (right->type == EXPR_CALL) {
1270                 if (get_implied_value(right, &sval)) {
1271                         handle_comparison(get_type(expr), left, expr->op, right);
1272                         return 1;
1273                 }
1274                 if (!get_implied_value(left, &sval))
1275                         return 1;
1276                 function_comparison(expr->op, right, sval, 0);
1277                 return 1;
1278         }
1279
1280         return 0;
1281 }
1282
1283 static void match_comparison(struct expression *expr)
1284 {
1285         struct expression *left_orig = strip_expr(expr->left);
1286         struct expression *right_orig = strip_expr(expr->right);
1287         struct expression *left, *right;
1288         struct expression *prev;
1289         struct symbol *type;
1290
1291         if (match_func_comparison(expr))
1292                 return;
1293
1294         type = get_type(expr);
1295         if (!type)
1296                 type = &llong_ctype;
1297
1298         left = left_orig;
1299         right = right_orig;
1300         move_known_values(&left, &right);
1301         handle_comparison(type, left, expr->op, right);
1302
1303         prev = get_assigned_expr(left_orig);
1304         if (is_simple_math(prev) && has_variable(prev, left_orig) == 0) {
1305                 left = prev;
1306                 right = right_orig;
1307                 move_known_values(&left, &right);
1308                 handle_comparison(type, left, expr->op, right);
1309         }
1310
1311         prev = get_assigned_expr(right_orig);
1312         if (is_simple_math(prev) && has_variable(prev, right_orig) == 0) {
1313                 left = left_orig;
1314                 right = prev;
1315                 move_known_values(&left, &right);
1316                 handle_comparison(type, left, expr->op, right);
1317         }
1318 }
1319
1320 static void handle_AND_condition(struct expression *expr)
1321 {
1322         struct range_list *rl = NULL;
1323         sval_t known;
1324
1325         if (get_implied_value(expr->left, &known) && known.value > 0) {
1326                 known.value--;
1327                 get_absolute_rl(expr->right, &rl);
1328                 rl = remove_range(rl, sval_type_val(known.type, 0), known);
1329                 set_extra_expr_true_false(expr->right, alloc_estate_rl(rl), NULL);
1330                 return;
1331         }
1332
1333         if (get_implied_value(expr->right, &known) && known.value > 0) {
1334                 known.value--;
1335                 get_absolute_rl(expr->left, &rl);
1336                 rl = remove_range(rl, sval_type_val(known.type, 0), known);
1337                 set_extra_expr_true_false(expr->left, alloc_estate_rl(rl), NULL);
1338                 return;
1339         }
1340 }
1341
1342 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
1343 void __extra_match_condition(struct expression *expr)
1344 {
1345         struct symbol *sym;
1346         char *name;
1347         struct smatch_state *pre_state;
1348         struct smatch_state *true_state;
1349         struct smatch_state *false_state;
1350
1351         expr = strip_expr(expr);
1352         switch (expr->type) {
1353         case EXPR_CALL:
1354                 function_comparison(SPECIAL_NOTEQUAL, expr, ll_to_sval(0), 1);
1355                 return;
1356         case EXPR_PREOP:
1357         case EXPR_SYMBOL:
1358         case EXPR_DEREF: {
1359                 sval_t zero;
1360
1361                 zero = sval_blank(expr);
1362                 zero.value = 0;
1363
1364                 name = expr_to_var_sym(expr, &sym);
1365                 if (!name)
1366                         return;
1367                 pre_state = get_state(my_id, name, sym);
1368                 true_state = estate_filter_sval(pre_state, zero);
1369                 if (possibly_true(expr, SPECIAL_EQUAL, zero_expr()))
1370                         false_state = alloc_estate_sval(zero);
1371                 else
1372                         false_state = alloc_estate_empty();
1373                 set_extra_true_false(name, sym, true_state, false_state);
1374                 free_string(name);
1375                 return;
1376         }
1377         case EXPR_COMPARE:
1378                 match_comparison(expr);
1379                 return;
1380         case EXPR_ASSIGNMENT:
1381                 __extra_match_condition(expr->left);
1382                 return;
1383         case EXPR_BINOP:
1384                 if (expr->op == '&')
1385                         handle_AND_condition(expr);
1386                 return;
1387         }
1388 }
1389
1390 static void assume_indexes_are_valid(struct expression *expr)
1391 {
1392         struct expression *array_expr;
1393         int array_size;
1394         struct expression *offset;
1395         struct symbol *offset_type;
1396         struct range_list *rl_before;
1397         struct range_list *rl_after;
1398         struct range_list *filter = NULL;
1399         sval_t size;
1400
1401         expr = strip_expr(expr);
1402         if (!is_array(expr))
1403                 return;
1404
1405         offset = get_array_offset(expr);
1406         offset_type = get_type(offset);
1407         if (offset_type && type_signed(offset_type)) {
1408                 filter = alloc_rl(sval_type_min(offset_type),
1409                                   sval_type_val(offset_type, -1));
1410         }
1411
1412         array_expr = strip_parens(expr->unop->left);
1413         array_size = get_real_array_size(array_expr);
1414         if (array_size > 1) {
1415                 size = sval_type_val(offset_type, array_size);
1416                 add_range(&filter, size, sval_type_max(offset_type));
1417         }
1418
1419         if (!filter)
1420                 return;
1421         get_absolute_rl(offset, &rl_before);
1422         rl_after = rl_filter(rl_before, filter);
1423         if (rl_equiv(rl_before, rl_after))
1424                 return;
1425         set_extra_expr_nomod(offset, alloc_estate_rl(rl_after));
1426 }
1427
1428 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
1429 int implied_not_equal(struct expression *expr, long long val)
1430 {
1431         return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val));
1432 }
1433
1434 int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val)
1435 {
1436         struct smatch_state *estate;
1437
1438         estate = get_state(SMATCH_EXTRA, name, sym);
1439         if (!estate)
1440                 return 0;
1441         if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0)))
1442                 return 1;
1443         return 0;
1444 }
1445
1446 int parent_is_null_var_sym(const char *name, struct symbol *sym)
1447 {
1448         char buf[256];
1449         char *start;
1450         char *end;
1451         struct smatch_state *state;
1452
1453         strncpy(buf, name, sizeof(buf) - 1);
1454         buf[sizeof(buf) - 1] = '\0';
1455
1456         start = &buf[0];
1457         while ((*start == '&'))
1458                 start++;
1459
1460         while ((end = strrchr(start, '-'))) {
1461                 *end = '\0';
1462                 state = get_state(SMATCH_EXTRA, start, sym);
1463                 if (!state)
1464                         continue;
1465                 if (estate_min(state).value == 0 &&
1466                     estate_max(state).value == 0)
1467                         return 1;
1468         }
1469         return 0;
1470 }
1471
1472 int parent_is_null(struct expression *expr)
1473 {
1474         struct symbol *sym;
1475         char *var;
1476         int ret = 0;
1477
1478         expr = strip_expr(expr);
1479         var = expr_to_var_sym(expr, &sym);
1480         if (!var || !sym)
1481                 goto free;
1482         ret = parent_is_null_var_sym(var, sym);
1483 free:
1484         free_string(var);
1485         return ret;
1486 }
1487
1488 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct smatch_state *state)
1489 {
1490         if (estate_is_whole(state))
1491                 return;
1492         sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, state->name);
1493         if (estate_has_fuzzy_max(state))
1494                 sql_insert_caller_info(call, FUZZY_MAX, param, printed_name,
1495                                        sval_to_str(estate_get_fuzzy_max(state)));
1496 }
1497
1498 static void db_limited_before(void)
1499 {
1500         unmatched_stree = clone_stree(__get_cur_stree());
1501 }
1502
1503 static void db_limited_after(void)
1504 {
1505         free_stree(&unmatched_stree);
1506 }
1507
1508 static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, int mod)
1509 {
1510         struct expression *arg;
1511         char *name;
1512         struct symbol *sym;
1513         struct sm_state *sm;
1514         struct symbol *compare_type, *var_type;
1515         struct range_list *rl;
1516         struct range_list *limit;
1517         struct range_list *new;
1518
1519         while (expr->type == EXPR_ASSIGNMENT)
1520                 expr = strip_expr(expr->right);
1521         if (expr->type != EXPR_CALL)
1522                 return;
1523
1524         arg = get_argument_from_call_expr(expr->args, param);
1525         if (!arg)
1526                 return;
1527
1528         name = get_variable_from_key(arg, key, &sym);
1529         if (!name || !sym)
1530                 goto free;
1531
1532         if (strcmp(key, "$$") == 0)
1533                 compare_type = get_arg_type(expr->fn, param);
1534         else
1535                 compare_type = get_member_type_from_key(arg, key);
1536
1537         sm = get_sm_state(SMATCH_EXTRA, name, sym);
1538         if (sm)
1539                 rl = estate_rl(sm->state);
1540         else
1541                 rl = alloc_whole_rl(compare_type);
1542
1543         call_results_to_rl(expr, compare_type, value, &limit);
1544         new = rl_intersection(rl, limit);
1545
1546         var_type = get_member_type_from_key(arg, key);
1547         new = cast_rl(var_type, new);
1548
1549         /* We want to preserve the implications here */
1550         if (sm && rl_equiv(estate_rl(sm->state), new)) {
1551                 __set_sm(sm);
1552         } else {
1553                 if (mod)
1554                         set_extra_mod(name, sym, alloc_estate_rl(new));
1555                 else
1556                         set_extra_nomod(name, sym, alloc_estate_rl(new));
1557         }
1558
1559 free:
1560         free_string(name);
1561 }
1562
1563 static void db_param_limit(struct expression *expr, int param, char *key, char *value)
1564 {
1565         db_param_limit_filter(expr, param, key, value, 0);
1566 }
1567
1568 static void db_param_filter(struct expression *expr, int param, char *key, char *value)
1569 {
1570         db_param_limit_filter(expr, param, key, value, 1);
1571 }
1572
1573 static void db_param_add(struct expression *expr, int param, char *key, char *value)
1574 {
1575         struct expression *arg;
1576         char *name;
1577         struct symbol *sym;
1578         struct symbol *type;
1579         struct smatch_state *state;
1580         struct range_list *added = NULL;
1581         struct range_list *new;
1582
1583         while (expr->type == EXPR_ASSIGNMENT)
1584                 expr = strip_expr(expr->right);
1585         if (expr->type != EXPR_CALL)
1586                 return;
1587
1588         arg = get_argument_from_call_expr(expr->args, param);
1589         if (!arg)
1590                 return;
1591         name = get_variable_from_key(arg, key, &sym);
1592         if (!name || !sym)
1593                 goto free;
1594
1595         type = get_member_type_from_key(arg, key);
1596         state = get_state(SMATCH_EXTRA, name, sym);
1597         if (state) {
1598                 call_results_to_rl(expr, type, value, &added);
1599                 new = rl_union(estate_rl(state), added);
1600         } else {
1601                 new = alloc_whole_rl(type);
1602         }
1603
1604         set_extra_mod(name, sym, alloc_estate_rl(new));
1605 free:
1606         free_string(name);
1607 }
1608
1609 static void db_returned_member_info(struct expression *expr, int param, char *key, char *value)
1610 {
1611         struct symbol *type;
1612         struct symbol *sym;
1613         char *name;
1614         struct range_list *rl;
1615
1616         if (expr->type != EXPR_ASSIGNMENT)
1617                 return;
1618
1619         name = return_state_to_var_sym(expr, param, key, &sym);
1620         if (!name || !sym)
1621                 goto free;
1622         type = get_member_type_from_key(expr->left, key);
1623         if (!type)
1624                 return;
1625         call_results_to_rl(expr->right, type, value, &rl);
1626         set_extra_mod(name, sym, alloc_estate_rl(rl));
1627
1628 free:
1629         free_string(name);
1630 }
1631
1632 static char *in_terms_of_param_math(struct expression *expr, char *printed_name)
1633 {
1634         struct symbol *sym;
1635         char *var;
1636         char buf[256];
1637         char *ret = NULL;
1638
1639         var = expr_to_var_sym(expr, &sym);
1640         if (!var || !sym)
1641                 goto free;
1642         snprintf(buf, sizeof(buf), "%s%s", var, printed_name + 2);
1643
1644         ret = get_value_in_terms_of_parameter_math_var_sym(buf, sym);
1645
1646 free:
1647         free_string(var);
1648         return ret;
1649 }
1650
1651 static void returned_member_callback(int return_id, char *return_ranges, struct expression *expr, char *printed_name, struct smatch_state *state)
1652 {
1653         char buf[256];
1654         char *math_str;
1655         sval_t sval;
1656
1657         /* these are handled in smatch_param_filter/set/limit.c */
1658         if (printed_name[0] != '*' &&
1659             !strchr(printed_name, '.') && !strchr(printed_name, '-'))
1660                 return;
1661
1662         if (estate_get_single_value(state, &sval)) {
1663                 sql_insert_return_states(return_id, return_ranges, RETURN_VALUE, -1,
1664                                 printed_name, sval_to_str(sval));
1665                 return;
1666         }
1667
1668         math_str = in_terms_of_param_math(expr, printed_name);
1669         if (math_str) {
1670                 snprintf(buf, sizeof(buf), "%s[%s]", state->name, math_str);
1671                 sql_insert_return_states(return_id, return_ranges, RETURN_VALUE, -1,
1672                                 printed_name, buf);
1673                 return;
1674         }
1675
1676         if (estate_is_whole(state))
1677                 return;
1678
1679         sql_insert_return_states(return_id, return_ranges, RETURN_VALUE, -1,
1680                         printed_name, state->name);
1681 }
1682
1683 static void match_call_info(struct expression *expr)
1684 {
1685         struct smatch_state *state;
1686         struct range_list *rl = NULL;
1687         struct expression *arg;
1688         struct symbol *type;
1689         int i = 0;
1690
1691         FOR_EACH_PTR(expr->args, arg) {
1692                 type = get_arg_type(expr->fn, i);
1693
1694                 if (get_implied_rl(arg, &rl))
1695                         rl = cast_rl(type, rl);
1696                 else
1697                         rl = cast_rl(type, alloc_whole_rl(get_type(arg)));
1698
1699                 if (!is_whole_rl(rl))
1700                         sql_insert_caller_info(expr, PARAM_VALUE, i, "$$", show_rl(rl));
1701                 state = get_state_expr(SMATCH_EXTRA, arg);
1702                 if (estate_has_fuzzy_max(state)) {
1703                         sql_insert_caller_info(expr, FUZZY_MAX, i, "$$",
1704                                                sval_to_str(estate_get_fuzzy_max(state)));
1705                 }
1706                 i++;
1707         } END_FOR_EACH_PTR(arg);
1708 }
1709
1710 static void set_param_value(const char *name, struct symbol *sym, char *key, char *value)
1711 {
1712         struct range_list *rl = NULL;
1713         struct smatch_state *state;
1714         struct symbol *type;
1715         char fullname[256];
1716
1717         if (strcmp(key, "*$$") == 0)
1718                 snprintf(fullname, sizeof(fullname), "*%s", name);
1719         else if (strncmp(key, "$$", 2) == 0)
1720                 snprintf(fullname, 256, "%s%s", name, key + 2);
1721         else
1722                 return;
1723
1724         type = get_member_type_from_key(symbol_expression(sym), key);
1725         str_to_rl(type, value, &rl);
1726         state = alloc_estate_rl(rl);
1727         set_state(SMATCH_EXTRA, fullname, sym, state);
1728 }
1729
1730 static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value)
1731 {
1732         struct range_list *rl = NULL;
1733         struct smatch_state *state;
1734         struct symbol *type;
1735         char fullname[256];
1736         sval_t max;
1737
1738         if (strcmp(key, "*$$") == 0)
1739                 snprintf(fullname, sizeof(fullname), "*%s", name);
1740         else if (strncmp(key, "$$", 2) == 0)
1741                 snprintf(fullname, 256, "%s%s", name, key + 2);
1742         else
1743                 return;
1744
1745         state = get_state(SMATCH_EXTRA, fullname, sym);
1746         if (!state)
1747                 return;
1748         type = get_member_type_from_key(symbol_expression(sym), key);
1749         str_to_rl(type, value, &rl);
1750         if (!rl_to_sval(rl, &max))
1751                 return;
1752         estate_set_fuzzy_max(state, max);
1753 }
1754
1755 void register_smatch_extra(int id)
1756 {
1757         my_id = id;
1758
1759         add_merge_hook(my_id, &merge_estates);
1760         add_unmatched_state_hook(my_id, &unmatched_state);
1761         add_hook(&match_function_def, FUNC_DEF_HOOK);
1762         add_hook(&match_declarations, DECLARATION_HOOK);
1763         select_caller_info_hook(set_param_value, PARAM_VALUE);
1764         select_caller_info_hook(set_param_hard_max, FUZZY_MAX);
1765         select_return_states_hook(RETURN_VALUE, &db_returned_member_info);
1766         select_return_states_before(&db_limited_before);
1767         select_return_states_hook(LIMITED_VALUE, &db_param_limit);
1768         select_return_states_hook(FILTER_VALUE, &db_param_filter);
1769         select_return_states_hook(ADDED_VALUE, &db_param_add);
1770         select_return_states_after(&db_limited_after);
1771 }
1772
1773 void register_smatch_extra_late(int id)
1774 {
1775         add_hook(&match_dereferences, DEREF_HOOK);
1776         add_hook(&match_pointer_as_array, OP_HOOK);
1777         select_call_implies_hook(DEREFERENCE, &set_param_dereferenced);
1778         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
1779         add_hook(&match_assign, ASSIGNMENT_HOOK);
1780         add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK);
1781         add_hook(&unop_expr, OP_HOOK);
1782         add_hook(&asm_expr, ASM_HOOK);
1783
1784         add_hook(&match_call_info, FUNCTION_CALL_HOOK);
1785         add_member_info_callback(my_id, struct_member_callback);
1786         add_returned_member_callback(my_id, returned_member_callback);
1787
1788         add_hook(&assume_indexes_are_valid, OP_HOOK);
1789 }