smatch_implied.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  * Imagine we have this code:
  20  * foo = 1;
  21  * if (bar)
  22  *         foo = 99;
  23  * else
  24  *         frob();
  25  *                   //  <-- point #1
  26  * if (foo == 99)    //  <-- point #2
  27  *         bar->baz; //  <-- point #3
  28  *
  29  *
  30  * At point #3 bar is non null and can be dereferenced.
  31  *
  32  * It's smatch_implied.c which sets bar to non null at point #2.
  33  *
  34  * At point #1 merge_slist() stores the list of states from both
  35  * the true and false paths.  On the true path foo == 99 and on
  36  * the false path foo == 1.  merge_slist() sets their pool
  37  * list to show the other states which were there when foo == 99.
  38  *
  39  * When it comes to the if (foo == 99) the smatch implied hook
  40  * looks for all the pools where foo was not 99.  It makes a list
  41  * of those.
  42  *
  43  * Then for bar (and all the other states) it says, ok bar is a
  44  * merged state that came from these previous states.  We'll
  45  * chop out all the states where it came from a pool where
  46  * foo != 99 and merge it all back together.
  47  *
  48  * That is the implied state of bar.
  49  *
  50  * merge_slist() sets up ->pool.  An sm_state only has one ->pool and
  51  *    that is the pool where it was first set.  The my pool gets set when
  52  *    code paths merge.  States that have been set since the last merge do
  53  *    not have a ->pool.
  54  * merge_sm_state() sets ->left and ->right.  (These are the states which were
  55  *    merged to form the current state.)
  56  * a pool:  a pool is an slist that has been merged with another slist.
  57  */
  58
  59 #include <sys/time.h>
  60 #include <time.h>
  61 #include "smatch.h"
  62 #include "smatch_slist.h"
  63 #include "smatch_extra.h"
  64
  65 char *implied_debug_msg;
  66 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
  67
  68 int option_debug_implied = 0;
  69 int option_no_implied = 0;
  70
  71 #define RIGHT 0
  72 #define LEFT  1
  73
  74 /*
  75  * tmp_range_list():
  76  * It messes things up to free range list allocations.  This helper fuction
  77  * lets us reuse memory instead of doing new allocations.
  78  */
  79 static struct range_list *tmp_range_list(long long num)
  80 {
  81         static struct range_list *my_list = NULL;
  82         static struct data_range *my_range;
  83
  84         __free_ptr_list((struct ptr_list **)&my_list);
  85         my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
  86         add_ptr_list(&my_list, my_range);
  87         return my_list;
  88 }
  89
  90 static void print_debug_tf(struct sm_state *s, int istrue, int isfalse)
  91 {
  92         if (!option_debug_implied && !option_debug)
  93                 return;
  94
  95         if (istrue && isfalse) {
  96                 printf("'%s = %s' from %d does not exist.\n", s->name,
  97                         show_state(s->state), s->line);
  98         } else if (istrue) {
  99                 printf("'%s = %s' from %d is true. [stree %d]\n", s->name, show_state(s->state),
 100                         s->line, get_stree_id(s->pool));
 101         } else if (isfalse) {
 102                 printf("'%s = %s' from %d is false. [stree %d]\n", s->name, show_state(s->state),
 103                         s->line, get_stree_id(s->pool));
 104         } else {
 105                 printf("'%s = %s' from %d could be true or false. [stree %d]\n", s->name,
 106                         show_state(s->state), s->line, get_stree_id(s->pool));
 107         }
 108 }
 109
 110 /*
 111  * add_pool() adds a slist to *pools. If the slist has already been
 112  * added earlier then it doesn't get added a second time.
 113  */
 114 void add_pool(struct stree_stack **pools, struct stree *new)
 115 {
 116         struct stree *tmp;
 117
 118         FOR_EACH_PTR(*pools, tmp) {
 119                 if (tmp < new)
 120                         continue;
 121                 else if (tmp == new) {
 122                         return;
 123                 } else {
 124                         INSERT_CURRENT(new, tmp);
 125                         return;
 126                 }
 127         } END_FOR_EACH_PTR(tmp);
 128         add_ptr_list(pools, new);
 129 }
 130
 131 /*
 132  * If 'foo' == 99 add it that pool to the true pools.  If it's false, add it to
 133  * the false pools.  If we're not sure, then we don't add it to either.
 134  */
 135 static void do_compare(struct sm_state *sm_state, int comparison, struct range_list *vals,
 136                         int lr,
 137                         struct stree_stack **true_stack,
 138                         struct stree_stack **false_stack)
 139 {
 140         struct sm_state *s;
 141         int istrue;
 142         int isfalse;
 143         struct symbol *type;
 144         struct range_list *var_rl;
 145
 146         if (!sm_state->pool)
 147                 return;
 148
 149         if (is_implied(sm_state)) {
 150                 s = get_sm_state_stree(sm_state->pool,
 151                                 sm_state->owner, sm_state->name,
 152                                 sm_state->sym);
 153         } else {
 154                 s = sm_state;
 155         }
 156
 157         if (!s) {
 158                 if (option_debug_implied || option_debug)
 159                         sm_msg("%s from %d, has borrowed implications.",
 160                                 sm_state->name, sm_state->line);
 161                 return;
 162         }
 163
 164         type = estate_type(sm_state->state);
 165         if (type_positive_bits(rl_type(vals)) > type_positive_bits(type))
 166                 type = rl_type(vals);
 167         if (type_positive_bits(type) < 31)
 168                 type = &int_ctype;
 169         var_rl = cast_rl(type, estate_rl(s->state));
 170         vals = cast_rl(type, vals);
 171
 172         if (lr == LEFT) {
 173                 istrue = !possibly_false_rl(var_rl, comparison, vals);
 174                 isfalse = !possibly_true_rl(var_rl, comparison, vals);
 175         } else {
 176                 istrue = !possibly_false_rl(vals, comparison, var_rl);
 177                 isfalse = !possibly_true_rl(vals, comparison, var_rl);
 178         }
 179
 180         print_debug_tf(s, istrue, isfalse);
 181
 182         if (istrue)
 183                 add_pool(true_stack, s->pool);
 184
 185         if (isfalse)
 186                 add_pool(false_stack, s->pool);
 187 }
 188
 189 static int pool_in_pools(struct stree *pool,
 190                         struct stree_stack *pools)
 191 {
 192         struct stree *tmp;
 193
 194         FOR_EACH_PTR(pools, tmp) {
 195                 if (tmp == pool)
 196                         return 1;
 197                 if (tmp > pool)
 198                         return 0;
 199         } END_FOR_EACH_PTR(tmp);
 200         return 0;
 201 }
 202
 203 static int is_checked(struct state_list *checked, struct sm_state *sm)
 204 {
 205         struct sm_state *tmp;
 206
 207         FOR_EACH_PTR(checked, tmp) {
 208                 if (tmp == sm)
 209                         return 1;
 210         } END_FOR_EACH_PTR(tmp);
 211         return 0;
 212 }
 213
 214 /*
 215  * separate_pools():
 216  * Example code:  if (foo == 99) {
 217  *
 218  * Say 'foo' is a merged state that has many possible values.  It is the combination
 219  * of merges.  separate_pools() iterates through the pools recursively and calls
 220  * do_compare() for each time 'foo' was set.
 221  */
 222 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list *vals,
 223                         int lr,
 224                         struct stree_stack **true_stack,
 225                         struct stree_stack **false_stack,
 226                         struct state_list **checked)
 227 {
 228         int free_checked = 0;
 229         struct state_list *checked_states = NULL;
 230
 231         if (!sm_state)
 232                 return;
 233
 234         /*
 235            Sometimes the implications are just too big to deal with
 236            so we bail.  Theoretically, bailing out here can cause more false
 237            positives but won't hide actual bugs.
 238         */
 239         if (sm_state->nr_children > 4000) {
 240                 if (option_debug || option_debug_implied) {
 241                         static char buf[1028];
 242                         snprintf(buf, sizeof(buf), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
 243                                  sm_state->nr_children, sm_state->name, show_state(sm_state->state));
 244                         implied_debug_msg = buf;
 245                 }
 246                 return;
 247         }
 248
 249         if (checked == NULL) {
 250                 checked = &checked_states;
 251                 free_checked = 1;
 252         }
 253         if (is_checked(*checked, sm_state))
 254                 return;
 255         add_ptr_list(checked, sm_state);
 256
 257         do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
 258
 259         separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
 260         separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
 261         if (free_checked)
 262                 free_slist(checked);
 263 }
 264
 265 struct sm_state *filter_pools(struct sm_state *sm,
 266                               struct stree_stack *remove_stack,
 267                               struct stree_stack *keep_stack,
 268                               int *modified)
 269 {
 270         struct sm_state *ret = NULL;
 271         struct sm_state *left;
 272         struct sm_state *right;
 273         int removed = 0;
 274
 275         if (!sm)
 276                 return NULL;
 277
 278         if (sm->nr_children > 4000) {
 279                 if (option_debug || option_debug_implied) {
 280                         static char buf[1028];
 281                         snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
 282                                  __func__, sm->nr_children, sm->name, show_state(sm->state));
 283                         implied_debug_msg = buf;
 284                 }
 285                 return NULL;
 286         }
 287
 288         if (pool_in_pools(sm->pool, remove_stack)) {
 289                 DIMPLIED("removed %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
 290                 *modified = 1;
 291                 return NULL;
 292         }
 293
 294         if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack)) {
 295                 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
 296                 return sm;
 297         }
 298
 299         DIMPLIED("checking %s from %d (%d) [stree %d] left = %s [stree %d] right = %s [stree %d]\n",
 300                  show_sm(sm), sm->line, sm->nr_children, get_stree_id(sm->pool),
 301                  sm->left ? show_sm(sm->left) : "<none>", sm->left ? get_stree_id(sm->left->pool) : -1,
 302                  sm->right ? show_sm(sm->right) : "<none>", sm->right ? get_stree_id(sm->right->pool) : -1);
 303         left = filter_pools(sm->left, remove_stack, keep_stack, &removed);
 304         right = filter_pools(sm->right, remove_stack, keep_stack, &removed);
 305         if (!removed) {
 306                 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
 307                 return sm;
 308         }
 309         *modified = 1;
 310         if (!left && !right) {
 311                 DIMPLIED("removed %s from %d <none> [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
 312                 return NULL;
 313         }
 314
 315         if (!left) {
 316                 ret = clone_sm(right);
 317                 ret->merged = 1;
 318                 ret->right = right;
 319                 ret->left = NULL;
 320                 ret->pool = sm->pool;
 321         } else if (!right) {
 322                 ret = clone_sm(left);
 323                 ret->merged = 1;
 324                 ret->left = left;
 325                 ret->right = NULL;
 326                 ret->pool = sm->pool;
 327         } else {
 328                 ret = merge_sm_states(left, right);
 329                 ret->pool = sm->pool;
 330         }
 331         ret->implied = 1;
 332         DIMPLIED("partial %s => ", show_sm(sm));
 333         DIMPLIED("%s from %d [stree %d]\n", show_sm(ret), sm->line, get_stree_id(sm->pool));
 334         return ret;
 335 }
 336
 337 static int highest_stree_id(struct sm_state *sm)
 338 {
 339         int left = 0;
 340         int right = 0;
 341
 342         if (!sm->left && !sm->right)
 343                 return 0;
 344
 345         if (sm->left)
 346                 left = get_stree_id(sm->left->pool);
 347         if (sm->right)
 348                 right = get_stree_id(sm->right->pool);
 349
 350         if (right > left)
 351                 return right;
 352         return left;
 353 }
 354
 355 static struct stree *filter_stack(struct sm_state *gate_sm,
 356                                        struct stree *pre_stree,
 357                                        struct stree_stack *remove_stack,
 358                                        struct stree_stack *keep_stack)
 359 {
 360         struct stree *ret = NULL;
 361         struct sm_state *tmp;
 362         struct sm_state *filtered_sm;
 363         int modified;
 364
 365         if (!remove_stack)
 366                 return NULL;
 367
 368         FOR_EACH_SM(pre_stree, tmp) {
 369                 if (highest_stree_id(tmp) < highest_stree_id(gate_sm)) {
 370                         DIMPLIED("skipping %s.  set before.  %d vs %d\n",
 371                                         tmp->name, highest_stree_id(tmp),
 372                                         highest_stree_id(gate_sm));
 373                         continue;
 374                 }
 375                 modified = 0;
 376                 filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified);
 377                 if (filtered_sm && modified) {
 378                         /* the assignments here are for borrowed implications */
 379                         filtered_sm->name = tmp->name;
 380                         filtered_sm->sym = tmp->sym;
 381                         avl_insert(&ret, filtered_sm);
 382                         if (out_of_memory())
 383                                 return NULL;
 384
 385                 }
 386         } END_FOR_EACH_SM(tmp);
 387         return ret;
 388 }
 389
 390 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
 391                 int lr,
 392                 struct stree *pre_stree,
 393                 struct stree **true_states,
 394                 struct stree **false_states)
 395 {
 396         struct stree_stack *true_stack = NULL;
 397         struct stree_stack *false_stack = NULL;
 398         struct timeval time_before;
 399         struct timeval time_after;
 400
 401         gettimeofday(&time_before, NULL);
 402
 403         if (!is_merged(sm_state)) {
 404                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
 405                 return;
 406         }
 407
 408         if (option_debug_implied || option_debug) {
 409                 if (lr == LEFT)
 410                         sm_msg("checking implications: (%s %s %s)",
 411                                 sm_state->name, show_special(comparison), show_rl(vals));
 412                 else
 413                         sm_msg("checking implications: (%s %s %s)",
 414                                 show_rl(vals), show_special(comparison), sm_state->name);
 415         }
 416
 417         separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
 418
 419         DIMPLIED("filtering true stack.\n");
 420         *true_states = filter_stack(sm_state, pre_stree, false_stack, true_stack);
 421         DIMPLIED("filtering false stack.\n");
 422         *false_states = filter_stack(sm_state, pre_stree, true_stack, false_stack);
 423         free_stree_stack(&true_stack);
 424         free_stree_stack(&false_stack);
 425         if (option_debug_implied || option_debug) {
 426                 printf("These are the implied states for the true path:\n");
 427                 __print_stree(*true_states);
 428                 printf("These are the implied states for the false path:\n");
 429                 __print_stree(*false_states);
 430         }
 431
 432         gettimeofday(&time_after, NULL);
 433         if (time_after.tv_sec - time_before.tv_sec > 7)
 434                 __bail_on_rest_of_function = 1;
 435 }
 436
 437 static struct expression *get_left_most_expr(struct expression *expr)
 438 {
 439         expr = strip_expr(expr);
 440         if (expr->type == EXPR_ASSIGNMENT)
 441                 return get_left_most_expr(expr->left);
 442         return expr;
 443 }
 444
 445 static int is_merged_expr(struct expression  *expr)
 446 {
 447         struct sm_state *sm;
 448         sval_t dummy;
 449
 450         if (get_value(expr, &dummy))
 451                 return 0;
 452         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 453         if (!sm)
 454                 return 0;
 455         if (is_merged(sm))
 456                 return 1;
 457         return 0;
 458 }
 459
 460 static void delete_equiv_stree(struct stree **stree, const char *name, struct symbol *sym)
 461 {
 462         struct smatch_state *state;
 463         struct relation *rel;
 464
 465         state = get_state(SMATCH_EXTRA, name, sym);
 466         if (!estate_related(state)) {
 467                 delete_state_stree(stree, SMATCH_EXTRA, name, sym);
 468                 return;
 469         }
 470
 471         FOR_EACH_PTR(estate_related(state), rel) {
 472                 delete_state_stree(stree, SMATCH_EXTRA, rel->name, rel->sym);
 473         } END_FOR_EACH_PTR(rel);
 474 }
 475
 476 static void handle_comparison(struct expression *expr,
 477                               struct stree **implied_true,
 478                               struct stree **implied_false)
 479 {
 480         struct sm_state *sm = NULL;
 481         struct range_list *ranges = NULL;
 482         struct expression *left;
 483         struct expression *right;
 484         int lr;
 485
 486         left = get_left_most_expr(expr->left);
 487         right = get_left_most_expr(expr->right);
 488
 489         if (is_merged_expr(left)) {
 490                 lr = LEFT;
 491                 sm = get_sm_state_expr(SMATCH_EXTRA, left);
 492                 get_implied_rl(right, &ranges);
 493         } else if (is_merged_expr(right)) {
 494                 lr = RIGHT;
 495                 sm = get_sm_state_expr(SMATCH_EXTRA, right);
 496                 get_implied_rl(left, &ranges);
 497         }
 498
 499         if (!ranges || !sm) {
 500                 free_rl(&ranges);
 501                 return;
 502         }
 503
 504         separate_and_filter(sm, expr->op, ranges, lr, __get_cur_stree(), implied_true, implied_false);
 505         free_rl(&ranges);
 506         delete_equiv_stree(implied_true, sm->name, sm->sym);
 507         delete_equiv_stree(implied_false, sm->name, sm->sym);
 508 }
 509
 510 static void handle_zero_comparison(struct expression *expr,
 511                                 struct stree **implied_true,
 512                                 struct stree **implied_false)
 513 {
 514         struct symbol *sym;
 515         char *name;
 516         struct sm_state *sm;
 517
 518         if (expr->type == EXPR_POSTOP)
 519                 expr = strip_expr(expr->unop);
 520
 521         if (expr->type == EXPR_ASSIGNMENT) {
 522                 /* most of the time ->pools will be empty here because we
 523                    just set the state, but if have assigned a conditional
 524                    function there are implications. */
 525                 expr = expr->left;
 526         }
 527
 528         name = expr_to_var_sym(expr, &sym);
 529         if (!name || !sym)
 530                 goto free;
 531         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 532         if (!sm)
 533                 goto free;
 534
 535         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_stree(), implied_true, implied_false);
 536         delete_equiv_stree(implied_true, name, sym);
 537         delete_equiv_stree(implied_false, name, sym);
 538 free:
 539         free_string(name);
 540 }
 541
 542 static int handled_by_implied_hook(struct expression *expr,
 543                                    struct stree **implied_true,
 544                                    struct stree **implied_false)
 545 {
 546         struct stree_stack *true_stack = NULL;
 547         struct stree_stack *false_stack = NULL;
 548         struct stree *pre_stree;
 549         struct sm_state *sm;
 550
 551         sm = comparison_implication_hook(expr, &true_stack, &false_stack);
 552         if (!sm)
 553                 sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
 554         if (!sm)
 555                 return 0;
 556
 557         pre_stree = clone_stree(__get_cur_stree());
 558
 559         *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
 560         *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
 561
 562         free_stree(&pre_stree);
 563         free_stree_stack(&true_stack);
 564         free_stree_stack(&false_stack);
 565
 566         return 1;
 567 }
 568
 569 static void get_tf_states(struct expression *expr,
 570                           struct stree **implied_true,
 571                           struct stree **implied_false)
 572 {
 573         if (handled_by_implied_hook(expr, implied_true, implied_false))
 574                 return;
 575
 576         if (expr->type == EXPR_COMPARE)
 577                 handle_comparison(expr, implied_true, implied_false);
 578         else
 579                 handle_zero_comparison(expr, implied_true, implied_false);
 580 }
 581
 582 static struct stree *saved_implied_true;
 583 static struct stree *saved_implied_false;
 584
 585 static void save_implications_hook(struct expression *expr)
 586 {
 587         if (option_no_implied)
 588                 return;
 589         get_tf_states(expr, &saved_implied_true, &saved_implied_false);
 590 }
 591
 592 static void set_implied_states(struct expression *expr)
 593 {
 594         struct sm_state *sm;
 595
 596         FOR_EACH_SM(saved_implied_true, sm) {
 597                 if (!get_state_stree(saved_implied_false, sm->owner, sm->name, sm->sym)) {
 598                         struct sm_state *orig;
 599
 600                         orig = get_sm_state(sm->owner, sm->name, sm->sym);
 601                         set_state_stree(&saved_implied_false, sm->owner, sm->name, sm->sym, orig->state);
 602                 }
 603         } END_FOR_EACH_SM(sm);
 604
 605         FOR_EACH_SM(saved_implied_false, sm) {
 606                 if (!get_state_stree(saved_implied_true, sm->owner, sm->name, sm->sym)) {
 607                         struct sm_state *orig;
 608
 609                         orig = get_sm_state(sm->owner, sm->name, sm->sym);
 610                         set_state_stree(&saved_implied_true, sm->owner, sm->name, sm->sym, orig->state);
 611                 }
 612         } END_FOR_EACH_SM(sm);
 613
 614         FOR_EACH_SM(saved_implied_true, sm) {
 615                 __set_true_false_sm(sm, NULL);
 616         } END_FOR_EACH_SM(sm);
 617         free_stree(&saved_implied_true);
 618
 619         FOR_EACH_SM(saved_implied_false, sm) {
 620                 __set_true_false_sm(NULL, sm);
 621         } END_FOR_EACH_SM(sm);
 622         free_stree(&saved_implied_false);
 623 }
 624
 625 struct range_list *__get_implied_values(struct expression *switch_expr)
 626 {
 627         char *name;
 628         struct symbol *sym;
 629         struct smatch_state *state;
 630         struct range_list *ret = NULL;
 631
 632         name = expr_to_var_sym(switch_expr, &sym);
 633         if (!name || !sym)
 634                 goto free;
 635         state = get_state(SMATCH_EXTRA, name, sym);
 636         if (!state)
 637                 goto free;
 638         ret = clone_rl(estate_rl(state));
 639 free:
 640         free_string(name);
 641         if (!ret) {
 642                 struct symbol *type;
 643
 644                 type = get_type(switch_expr);
 645                 ret = alloc_rl(sval_type_min(type), sval_type_max(type));
 646         }
 647         return ret;
 648 }
 649
 650 struct stree *__implied_case_stree(struct expression *switch_expr,
 651                                         struct expression *case_expr,
 652                                         struct range_list_stack **remaining_cases,
 653                                         struct stree **raw_stree)
 654 {
 655         char *name = NULL;
 656         struct symbol *sym;
 657         struct sm_state *sm;
 658         struct stree *true_states = NULL;
 659         struct stree *false_states = NULL;
 660         struct stree *extra_states = NULL;
 661         struct stree *ret = clone_stree(*raw_stree);
 662         sval_t sval;
 663         struct range_list *vals = NULL;
 664
 665         name = expr_to_var_sym(switch_expr, &sym);
 666         if (!name || !sym)
 667                 goto free;
 668         sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
 669
 670         if (case_expr) {
 671                 if (get_value(case_expr, &sval)) {
 672                         filter_top_rl(remaining_cases, sval);
 673                         add_range(&vals, sval, sval);
 674                 } else {
 675                         vals = clone_rl(top_rl(*remaining_cases));
 676                 }
 677         } else {
 678                 vals = top_rl(*remaining_cases);
 679         }
 680
 681         if (sm)
 682                 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_stree, &true_states, &false_states);
 683
 684         __push_fake_cur_stree();
 685         __unnullify_path();
 686         set_extra_nomod(name, sym, alloc_estate_rl(vals));
 687         extra_states = __pop_fake_cur_stree();
 688         overwrite_stree(extra_states, &true_states);
 689         overwrite_stree(true_states, &ret);
 690         free_stree(&extra_states);
 691         free_stree(&true_states);
 692         free_stree(&false_states);
 693 free:
 694         free_string(name);
 695         return ret;
 696 }
 697
 698 static void match_end_func(struct symbol *sym)
 699 {
 700         if (__inline_fn)
 701                 return;
 702         implied_debug_msg = NULL;
 703 }
 704
 705 static int sm_state_in_slist(struct sm_state *sm, struct state_list *slist)
 706 {
 707         struct sm_state *tmp;
 708
 709         FOR_EACH_PTR(slist, tmp) {
 710                 if (tmp == sm)
 711                         return 1;
 712         } END_FOR_EACH_PTR(tmp);
 713         return 0;
 714 }
 715
 716 /*
 717  * The situation is we have a SMATCH_EXTRA state and we want to break it into
 718  * each of the ->possible states and find the implications of each.  The caller
 719  * has to use __push_fake_cur_stree() to preserve the correct states so they
 720  * can be restored later.
 721  */
 722 void overwrite_states_using_pool(struct sm_state *sm)
 723 {
 724         struct sm_state *old;
 725         struct sm_state *new;
 726
 727         if (!sm->pool)
 728                 return;
 729
 730         FOR_EACH_SM(sm->pool, old) {
 731                 new = get_sm_state(old->owner, old->name, old->sym);
 732                 if (!new)  /* the variable went out of scope */
 733                         continue;
 734                 if (sm_state_in_slist(old, new->possible))
 735                         set_state(old->owner, old->name, old->sym, old->state);
 736         } END_FOR_EACH_SM(old);
 737 }
 738
 739 void __extra_match_condition(struct expression *expr);
 740 void __comparison_match_condition(struct expression *expr);
 741 void __stored_condition(struct expression *expr);
 742 void register_implications(int id)
 743 {
 744         add_hook(&save_implications_hook, CONDITION_HOOK);
 745         add_hook(&set_implied_states, CONDITION_HOOK);
 746         add_hook(&__extra_match_condition, CONDITION_HOOK);
 747         add_hook(&__comparison_match_condition, CONDITION_HOOK);
 748         add_hook(&__stored_condition, CONDITION_HOOK);
 749         add_hook(&match_end_func, END_FUNC_HOOK);
 750 }