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