1 /*
   2  * Copyright (C) 2006 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  * You have a lists of states.  kernel = locked, foo = NULL, ...
  20  * When you hit an if {} else {} statement then you swap the list
  21  * of states for a different list of states.  The lists are stored
  22  * on stacks.
  23  *
  24  * At the beginning of this file there are list of the stacks that
  25  * we use.  Each function in this file does something to one of
  26  * of the stacks.
  27  *
  28  * So the smatch_flow.c understands code but it doesn't understand states.
  29  * smatch_flow calls functions in this file.  This file calls functions
  30  * in smatch_slist.c which just has boring generic plumbing for handling
  31  * state lists.  But really it's this file where all the magic happens.
  32  */
  33 
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include "smatch.h"
  37 #include "smatch_slist.h"
  38 #include "smatch_extra.h"
  39 
  40 struct smatch_state undefined = { .name = "undefined" };
  41 struct smatch_state ghost = { .name = "ghost" };
  42 struct smatch_state merged = { .name = "merged" };
  43 struct smatch_state true_state = { .name = "true" };
  44 struct smatch_state false_state = { .name = "false" };
  45 
  46 static struct stree *cur_stree; /* current states */
  47 
  48 static struct stree_stack *true_stack; /* states after a t/f branch */
  49 static struct stree_stack *false_stack;
  50 static struct stree_stack *pre_cond_stack; /* states before a t/f branch */
  51 
  52 static struct stree_stack *cond_true_stack; /* states affected by a branch */
  53 static struct stree_stack *cond_false_stack;
  54 
  55 static struct stree_stack *fake_cur_stree_stack;
  56 static int read_only;
  57 
  58 static struct stree_stack *break_stack;
  59 static struct stree_stack *fake_break_stack;
  60 static struct stree_stack *switch_stack;
  61 static struct range_list_stack *remaining_cases;
  62 static struct stree_stack *default_stack;
  63 static struct stree_stack *continue_stack;
  64 
  65 static struct named_stree_stack *goto_stack;
  66 
  67 static struct ptr_list *backup;
  68 
  69 int option_debug;
  70 
  71 void __print_cur_stree(void)
  72 {
  73         __print_stree(cur_stree);
  74 }
  75 
  76 int unreachable(void)
  77 {
  78         if (!cur_stree)
  79                 return 1;
  80         return 0;
  81 }
  82 
  83 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
  84 {
  85         struct sm_state *ret;
  86 
  87         if (!name)
  88                 return NULL;
  89 
  90         if (read_only)
  91                 sm_perror("cur_stree is read only.");
  92 
  93         if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
  94                 struct smatch_state *s;
  95 
  96                 s = get_state(owner, name, sym);
  97                 if (!s)
  98                         sm_msg("%s new [%s] '%s' %s", __func__,
  99                                check_name(owner), name, show_state(state));
 100                 else
 101                         sm_msg("%s change [%s] '%s' %s => %s",
 102                                 __func__, check_name(owner), name, show_state(s),
 103                                 show_state(state));
 104         }
 105 
 106         if (owner != -1 && unreachable())
 107                 return NULL;
 108 
 109         if (fake_cur_stree_stack)
 110                 set_state_stree_stack(&fake_cur_stree_stack, owner, name, sym, state);
 111 
 112         ret = set_state_stree(&cur_stree, owner, name, sym, state);
 113 
 114         return ret;
 115 }
 116 
 117 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
 118 {
 119         char *name;
 120         struct symbol *sym;
 121         struct sm_state *ret = NULL;
 122 
 123         expr = strip_expr(expr);
 124         name = expr_to_var_sym(expr, &sym);
 125         if (!name || !sym)
 126                 goto free;
 127         ret = set_state(owner, name, sym, state);
 128 free:
 129         free_string(name);
 130         return ret;
 131 }
 132 
 133 void __swap_cur_stree(struct stree *stree)
 134 {
 135         free_stree(&cur_stree);
 136         cur_stree = stree;
 137 }
 138 
 139 void __push_fake_cur_stree(void)
 140 {
 141         push_stree(&fake_cur_stree_stack, NULL);
 142         __save_pre_cond_states();
 143 }
 144 
 145 struct stree *__pop_fake_cur_stree(void)
 146 {
 147         if (!fake_cur_stree_stack)
 148                 sm_perror("popping too many fake cur strees.");
 149         __use_pre_cond_states();
 150         return pop_stree(&fake_cur_stree_stack);
 151 }
 152 
 153 void __free_fake_cur_stree(void)
 154 {
 155         struct stree *stree;
 156 
 157         stree = __pop_fake_cur_stree();
 158         free_stree(&stree);
 159 }
 160 
 161 void __set_fake_cur_stree_fast(struct stree *stree)
 162 {
 163         push_stree(&pre_cond_stack, cur_stree);
 164         cur_stree = stree;
 165         read_only = 1;
 166 }
 167 
 168 void __pop_fake_cur_stree_fast(void)
 169 {
 170         cur_stree = pop_stree(&pre_cond_stack);
 171         read_only = 0;
 172 }
 173 
 174 void __merge_stree_into_cur(struct stree *stree)
 175 {
 176         struct sm_state *sm;
 177         struct sm_state *orig;
 178         struct sm_state *merged;
 179 
 180         FOR_EACH_SM(stree, sm) {
 181                 orig = get_sm_state(sm->owner, sm->name, sm->sym);
 182                 if (orig)
 183                         merged = merge_sm_states(orig, sm);
 184                 else
 185                         merged = sm;
 186                 __set_sm(merged);
 187         } END_FOR_EACH_SM(sm);
 188 }
 189 
 190 void __set_sm(struct sm_state *sm)
 191 {
 192         if (read_only)
 193                 sm_perror("cur_stree is read only.");
 194 
 195         if (option_debug ||
 196             strcmp(check_name(sm->owner), option_debug_check) == 0) {
 197                 struct smatch_state *s;
 198 
 199                 s = get_state(sm->owner, sm->name, sm->sym);
 200                 if (!s)
 201                         sm_msg("%s new %s", __func__, show_sm(sm));
 202                 else
 203                         sm_msg("%s change %s (was %s)", __func__, show_sm(sm),
 204                                show_state(s));
 205         }
 206 
 207         if (unreachable())
 208                 return;
 209 
 210         if (fake_cur_stree_stack)
 211                 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
 212 
 213         overwrite_sm_state_stree(&cur_stree, sm);
 214 }
 215 
 216 void __set_sm_cur_stree(struct sm_state *sm)
 217 {
 218         if (read_only)
 219                 sm_perror("cur_stree is read only.");
 220 
 221         if (option_debug ||
 222             strcmp(check_name(sm->owner), option_debug_check) == 0) {
 223                 struct smatch_state *s;
 224 
 225                 s = get_state(sm->owner, sm->name, sm->sym);
 226                 if (!s)
 227                         sm_msg("%s new %s", __func__, show_sm(sm));
 228                 else
 229                         sm_msg("%s change %s (was %s)",
 230                                 __func__, show_sm(sm), show_state(s));
 231         }
 232 
 233         if (unreachable())
 234                 return;
 235 
 236         overwrite_sm_state_stree(&cur_stree, sm);
 237 }
 238 
 239 void __set_sm_fake_stree(struct sm_state *sm)
 240 {
 241         if (read_only)
 242                 sm_perror("cur_stree is read only.");
 243 
 244         if (option_debug ||
 245             strcmp(check_name(sm->owner), option_debug_check) == 0) {
 246                 struct smatch_state *s;
 247 
 248                 s = get_state(sm->owner, sm->name, sm->sym);
 249                 if (!s)
 250                         sm_msg("%s new %s", __func__, show_sm(sm));
 251                 else
 252                         sm_msg("%s change %s (was %s)",
 253                                 __func__, show_sm(sm), show_state(s));
 254         }
 255 
 256         if (unreachable())
 257                 return;
 258 
 259         overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
 260 }
 261 
 262 
 263 typedef void (get_state_hook)(int owner, const char *name, struct symbol *sym);
 264 DECLARE_PTR_LIST(fn_list, get_state_hook *);
 265 static struct fn_list *get_state_hooks;
 266 
 267 void add_get_state_hook(get_state_hook *fn)
 268 {
 269         get_state_hook **p = malloc(sizeof(get_state_hook *));
 270         *p = fn;
 271         add_ptr_list(&get_state_hooks, p);
 272 }
 273 
 274 static void call_get_state_hooks(int owner, const char *name, struct symbol *sym)
 275 {
 276         static int recursion;
 277         get_state_hook **fn;
 278 
 279         if (recursion)
 280                 return;
 281         recursion = 1;
 282 
 283         FOR_EACH_PTR(get_state_hooks, fn) {
 284                 (*fn)(owner, name, sym);
 285         } END_FOR_EACH_PTR(fn);
 286 
 287         recursion = 0;
 288 }
 289 
 290 struct smatch_state *__get_state(int owner, const char *name, struct symbol *sym)
 291 {
 292         return get_state_stree(cur_stree, owner, name, sym);
 293 }
 294 
 295 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
 296 {
 297         call_get_state_hooks(owner, name, sym);
 298 
 299         return __get_state(owner, name, sym);
 300 }
 301 
 302 struct smatch_state *get_state_expr(int owner, struct expression *expr)
 303 {
 304         char *name;
 305         struct symbol *sym;
 306         struct smatch_state *ret = NULL;
 307 
 308         expr = strip_expr(expr);
 309         name = expr_to_var_sym(expr, &sym);
 310         if (!name || !sym)
 311                 goto free;
 312         ret = get_state(owner, name, sym);
 313 free:
 314         free_string(name);
 315         return ret;
 316 }
 317 
 318 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
 319 {
 320         struct sm_state *sms;
 321 
 322         sms = get_sm_state_stree(cur_stree, owner, name, sym);
 323         if (sms)
 324                 return sms->possible;
 325         return NULL;
 326 }
 327 
 328 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
 329 {
 330         char *name;
 331         struct symbol *sym;
 332         struct state_list *ret = NULL;
 333 
 334         expr = strip_expr(expr);
 335         name = expr_to_var_sym(expr, &sym);
 336         if (!name || !sym)
 337                 goto free;
 338         ret = get_possible_states(owner, name, sym);
 339 free:
 340         free_string(name);
 341         return ret;
 342 }
 343 
 344 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
 345 {
 346         return get_sm_state_stree(cur_stree, owner, name, sym);
 347 }
 348 
 349 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
 350 {
 351         char *name;
 352         struct symbol *sym;
 353         struct sm_state *ret = NULL;
 354 
 355         expr = strip_expr(expr);
 356         name = expr_to_var_sym(expr, &sym);
 357         if (!name || !sym)
 358                 goto free;
 359         ret = get_sm_state(owner, name, sym);
 360 free:
 361         free_string(name);
 362         return ret;
 363 }
 364 
 365 void delete_state(int owner, const char *name, struct symbol *sym)
 366 {
 367         delete_state_stree(&cur_stree, owner, name, sym);
 368         if (cond_true_stack) {
 369                 delete_state_stree_stack(&pre_cond_stack, owner, name, sym);
 370                 delete_state_stree_stack(&cond_true_stack, owner, name, sym);
 371                 delete_state_stree_stack(&cond_false_stack, owner, name, sym);
 372         }
 373 }
 374 
 375 void delete_state_expr(int owner, struct expression *expr)
 376 {
 377         char *name;
 378         struct symbol *sym;
 379 
 380         expr = strip_expr(expr);
 381         name = expr_to_var_sym(expr, &sym);
 382         if (!name || !sym)
 383                 goto free;
 384         delete_state(owner, name, sym);
 385 free:
 386         free_string(name);
 387 }
 388 
 389 static void delete_all_states_stree_sym(struct stree **stree, struct symbol *sym)
 390 {
 391         struct state_list *slist = NULL;
 392         struct sm_state *sm;
 393 
 394         FOR_EACH_SM(*stree, sm) {
 395                 if (sm->sym == sym)
 396                         add_ptr_list(&slist, sm);
 397         } END_FOR_EACH_SM(sm);
 398 
 399         FOR_EACH_PTR(slist, sm) {
 400                 delete_state_stree(stree, sm->owner, sm->name, sm->sym);
 401         } END_FOR_EACH_PTR(sm);
 402 
 403         free_slist(&slist);
 404 }
 405 
 406 static void delete_all_states_stree_stack_sym(struct stree_stack **stack, struct symbol *sym)
 407 {
 408         struct stree *stree;
 409 
 410         if (!*stack)
 411                 return;
 412 
 413         stree = pop_stree(stack);
 414         delete_all_states_stree_sym(&stree, sym);
 415         push_stree(stack, stree);
 416 }
 417 
 418 void __delete_all_states_sym(struct symbol *sym)
 419 {
 420         delete_all_states_stree_sym(&cur_stree, sym);
 421 
 422         delete_all_states_stree_stack_sym(&true_stack, sym);
 423         delete_all_states_stree_stack_sym(&true_stack, sym);
 424         delete_all_states_stree_stack_sym(&false_stack, sym);
 425         delete_all_states_stree_stack_sym(&pre_cond_stack, sym);
 426         delete_all_states_stree_stack_sym(&cond_true_stack, sym);
 427         delete_all_states_stree_stack_sym(&cond_false_stack, sym);
 428         delete_all_states_stree_stack_sym(&fake_cur_stree_stack, sym);
 429         delete_all_states_stree_stack_sym(&break_stack, sym);
 430         delete_all_states_stree_stack_sym(&fake_break_stack, sym);
 431         delete_all_states_stree_stack_sym(&switch_stack, sym);
 432         delete_all_states_stree_stack_sym(&continue_stack, sym);
 433 
 434         /*
 435          * deleting from the goto stack is problematic because we don't know
 436          * if the label is in scope and also we need the value for --two-passes.
 437          */
 438 }
 439 
 440 struct stree *get_all_states_from_stree(int owner, struct stree *source)
 441 {
 442         struct stree *ret = NULL;
 443         struct sm_state *tmp;
 444 
 445         FOR_EACH_SM(source, tmp) {
 446                 if (tmp->owner == owner)
 447                         avl_insert(&ret, tmp);
 448         } END_FOR_EACH_SM(tmp);
 449 
 450         return ret;
 451 }
 452 
 453 struct stree *get_all_states_stree(int owner)
 454 {
 455         return get_all_states_from_stree(owner, cur_stree);
 456 }
 457 
 458 struct stree *__get_cur_stree(void)
 459 {
 460         return cur_stree;
 461 }
 462 
 463 int is_reachable(void)
 464 {
 465         if (cur_stree)
 466                 return 1;
 467         return 0;
 468 }
 469 
 470 void set_true_false_states(int owner, const char *name, struct symbol *sym,
 471                            struct smatch_state *true_state,
 472                            struct smatch_state *false_state)
 473 {
 474         if (read_only)
 475                 sm_perror("cur_stree is read only.");
 476 
 477         if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
 478                 struct smatch_state *tmp;
 479 
 480                 tmp = get_state(owner, name, sym);
 481                 sm_msg("%s [%s] '%s'.  Was %s.  Now T:%s F:%s", __func__,
 482                        check_name(owner),  name, show_state(tmp),
 483                        show_state(true_state), show_state(false_state));
 484         }
 485 
 486         if (unreachable())
 487                 return;
 488 
 489         if (!cond_false_stack || !cond_true_stack) {
 490                 sm_perror("missing true/false stacks");
 491                 return;
 492         }
 493 
 494         if (true_state)
 495                 set_state_stree_stack(&cond_true_stack, owner, name, sym, true_state);
 496         if (false_state)
 497                 set_state_stree_stack(&cond_false_stack, owner, name, sym, false_state);
 498 }
 499 
 500 void set_true_false_states_expr(int owner, struct expression *expr,
 501                            struct smatch_state *true_state,
 502                            struct smatch_state *false_state)
 503 {
 504         char *name;
 505         struct symbol *sym;
 506 
 507         expr = strip_expr(expr);
 508         name = expr_to_var_sym(expr, &sym);
 509         if (!name || !sym)
 510                 goto free;
 511         set_true_false_states(owner, name, sym, true_state, false_state);
 512 free:
 513         free_string(name);
 514 }
 515 
 516 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
 517 {
 518         int owner;
 519         const char *name;
 520         struct symbol *sym;
 521 
 522         if (!true_sm && !false_sm)
 523                 return;
 524 
 525         if (unreachable())
 526                 return;
 527 
 528         owner = true_sm ? true_sm->owner : false_sm->owner;
 529         name = true_sm ? true_sm->name : false_sm->name;
 530         sym = true_sm ? true_sm->sym : false_sm->sym;
 531         if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
 532                 struct smatch_state *tmp;
 533 
 534                 tmp = get_state(owner, name, sym);
 535                 sm_msg("%s [%s] '%s'.  Was %s.  Now T:%s F:%s", __func__,
 536                        check_name(owner),  name, show_state(tmp),
 537                        show_state(true_sm ? true_sm->state : NULL),
 538                        show_state(false_sm ? false_sm->state : NULL));
 539         }
 540 
 541         if (!cond_false_stack || !cond_true_stack) {
 542                 sm_perror("missing true/false stacks");
 543                 return;
 544         }
 545 
 546         if (true_sm)
 547                 overwrite_sm_state_stree_stack(&cond_true_stack, true_sm);
 548         if (false_sm)
 549                 overwrite_sm_state_stree_stack(&cond_false_stack, false_sm);
 550 }
 551 
 552 void nullify_path(void)
 553 {
 554         if (fake_cur_stree_stack) {
 555                 __free_fake_cur_stree();
 556                 __push_fake_cur_stree();
 557         }
 558         free_stree(&cur_stree);
 559 }
 560 
 561 void __match_nullify_path_hook(const char *fn, struct expression *expr,
 562                                void *unused)
 563 {
 564         nullify_path();
 565 }
 566 
 567 /*
 568  * At the start of every function we mark the path
 569  * as unnull.  That way there is always at least one state
 570  * in the cur_stree until nullify_path is called.  This
 571  * is used in merge_slist() for the first null check.
 572  */
 573 void __unnullify_path(void)
 574 {
 575         if (!cur_stree)
 576                 set_state(-1, "unnull_path", NULL, &true_state);
 577 }
 578 
 579 int __path_is_null(void)
 580 {
 581         if (cur_stree)
 582                 return 0;
 583         return 1;
 584 }
 585 
 586 static void check_stree_stack_free(struct stree_stack **stack)
 587 {
 588         if (*stack) {
 589                 sm_perror("stack not empty");
 590                 free_stack_and_strees(stack);
 591         }
 592 }
 593 
 594 void save_all_states(void)
 595 {
 596         __add_ptr_list(&backup, cur_stree, 0);
 597         cur_stree = NULL;
 598 
 599         __add_ptr_list(&backup, true_stack, 0);
 600         true_stack = NULL;
 601         __add_ptr_list(&backup, false_stack, 0);
 602         false_stack = NULL;
 603         __add_ptr_list(&backup, pre_cond_stack, 0);
 604         pre_cond_stack = NULL;
 605 
 606         __add_ptr_list(&backup, cond_true_stack, 0);
 607         cond_true_stack = NULL;
 608         __add_ptr_list(&backup, cond_false_stack, 0);
 609         cond_false_stack = NULL;
 610 
 611         __add_ptr_list(&backup, fake_cur_stree_stack, 0);
 612         fake_cur_stree_stack = NULL;
 613 
 614         __add_ptr_list(&backup, break_stack, 0);
 615         break_stack = NULL;
 616         __add_ptr_list(&backup, fake_break_stack, 0);
 617         fake_break_stack = NULL;
 618 
 619         __add_ptr_list(&backup, switch_stack, 0);
 620         switch_stack = NULL;
 621         __add_ptr_list(&backup, remaining_cases, 0);
 622         remaining_cases = NULL;
 623         __add_ptr_list(&backup, default_stack, 0);
 624         default_stack = NULL;
 625         __add_ptr_list(&backup, continue_stack, 0);
 626         continue_stack = NULL;
 627 
 628         __add_ptr_list(&backup, goto_stack, 0);
 629         goto_stack = NULL;
 630 }
 631 
 632 static void *pop_backup(void)
 633 {
 634         void *ret;
 635 
 636         ret = last_ptr_list(backup);
 637         delete_ptr_list_last(&backup);
 638         return ret;
 639 }
 640 
 641 void restore_all_states(void)
 642 {
 643         goto_stack = pop_backup();
 644 
 645         continue_stack = pop_backup();
 646         default_stack = pop_backup();
 647         remaining_cases = pop_backup();
 648         switch_stack = pop_backup();
 649         fake_break_stack = pop_backup();
 650         break_stack = pop_backup();
 651 
 652         fake_cur_stree_stack = pop_backup();
 653 
 654         cond_false_stack = pop_backup();
 655         cond_true_stack = pop_backup();
 656 
 657         pre_cond_stack = pop_backup();
 658         false_stack = pop_backup();
 659         true_stack = pop_backup();
 660 
 661         cur_stree = pop_backup();
 662 }
 663 
 664 void free_goto_stack(void)
 665 {
 666         struct named_stree *named_stree;
 667 
 668         FOR_EACH_PTR(goto_stack, named_stree) {
 669                 free_stree(&named_stree->stree);
 670         } END_FOR_EACH_PTR(named_stree);
 671         __free_ptr_list((struct ptr_list **)&goto_stack);
 672 }
 673 
 674 void clear_all_states(void)
 675 {
 676         nullify_path();
 677         check_stree_stack_free(&true_stack);
 678         check_stree_stack_free(&false_stack);
 679         check_stree_stack_free(&pre_cond_stack);
 680         check_stree_stack_free(&cond_true_stack);
 681         check_stree_stack_free(&cond_false_stack);
 682         check_stree_stack_free(&break_stack);
 683         check_stree_stack_free(&fake_break_stack);
 684         check_stree_stack_free(&switch_stack);
 685         check_stree_stack_free(&continue_stack);
 686         check_stree_stack_free(&fake_cur_stree_stack);
 687 
 688         free_goto_stack();
 689 
 690         free_every_single_sm_state();
 691         free_tmp_expressions();
 692 }
 693 
 694 void __push_cond_stacks(void)
 695 {
 696         push_stree(&cond_true_stack, NULL);
 697         push_stree(&cond_false_stack, NULL);
 698         __push_fake_cur_stree();
 699 }
 700 
 701 void __fold_in_set_states(void)
 702 {
 703         struct stree *new_states;
 704         struct sm_state *sm;
 705 
 706         new_states = __pop_fake_cur_stree();
 707         FOR_EACH_SM(new_states, sm) {
 708                 __set_sm(sm);
 709                 __set_true_false_sm(sm, sm);
 710         } END_FOR_EACH_SM(sm);
 711         free_stree(&new_states);
 712 }
 713 
 714 void __free_set_states(void)
 715 {
 716         struct stree *new_states;
 717 
 718         new_states = __pop_fake_cur_stree();
 719         free_stree(&new_states);
 720 }
 721 
 722 struct stree *__copy_cond_true_states(void)
 723 {
 724         struct stree *ret;
 725 
 726         ret = pop_stree(&cond_true_stack);
 727         push_stree(&cond_true_stack, clone_stree(ret));
 728         return ret;
 729 }
 730 
 731 struct stree *__copy_cond_false_states(void)
 732 {
 733         struct stree *ret;
 734 
 735         ret = pop_stree(&cond_false_stack);
 736         push_stree(&cond_false_stack, clone_stree(ret));
 737         return ret;
 738 }
 739 
 740 struct stree *__pop_cond_true_stack(void)
 741 {
 742         return pop_stree(&cond_true_stack);
 743 }
 744 
 745 struct stree *__pop_cond_false_stack(void)
 746 {
 747         return pop_stree(&cond_false_stack);
 748 }
 749 
 750 /*
 751  * This combines the pre cond states with either the true or false states.
 752  * For example:
 753  * a = kmalloc() ; if (a !! foo(a)
 754  * In the pre state a is possibly null.  In the true state it is non null.
 755  * In the false state it is null.  Combine the pre and the false to get
 756  * that when we call 'foo', 'a' is null.
 757  */
 758 static void __use_cond_stack(struct stree_stack **stack)
 759 {
 760         struct stree *stree;
 761 
 762         free_stree(&cur_stree);
 763 
 764         cur_stree = pop_stree(&pre_cond_stack);
 765         push_stree(&pre_cond_stack, clone_stree(cur_stree));
 766 
 767         stree = pop_stree(stack);
 768         overwrite_stree(stree, &cur_stree);
 769         push_stree(stack, stree);
 770 }
 771 
 772 void __use_pre_cond_states(void)
 773 {
 774         free_stree(&cur_stree);
 775         cur_stree = pop_stree(&pre_cond_stack);
 776 }
 777 
 778 void __use_cond_true_states(void)
 779 {
 780         __use_cond_stack(&cond_true_stack);
 781 }
 782 
 783 void __use_cond_false_states(void)
 784 {
 785         __use_cond_stack(&cond_false_stack);
 786 }
 787 
 788 void __negate_cond_stacks(void)
 789 {
 790         struct stree *old_false, *old_true;
 791 
 792         __use_cond_stack(&cond_false_stack);
 793         old_false = pop_stree(&cond_false_stack);
 794         old_true = pop_stree(&cond_true_stack);
 795         push_stree(&cond_false_stack, old_true);
 796         push_stree(&cond_true_stack, old_false);
 797 }
 798 
 799 void __and_cond_states(void)
 800 {
 801         and_stree_stack(&cond_true_stack);
 802         or_stree_stack(&pre_cond_stack, cur_stree, &cond_false_stack);
 803 }
 804 
 805 void __or_cond_states(void)
 806 {
 807         or_stree_stack(&pre_cond_stack, cur_stree, &cond_true_stack);
 808         and_stree_stack(&cond_false_stack);
 809 }
 810 
 811 void __save_pre_cond_states(void)
 812 {
 813         push_stree(&pre_cond_stack, clone_stree(cur_stree));
 814 }
 815 
 816 void __discard_pre_cond_states(void)
 817 {
 818         struct stree *tmp;
 819 
 820         tmp = pop_stree(&pre_cond_stack);
 821         free_stree(&tmp);
 822 }
 823 
 824 struct stree *__get_true_states(void)
 825 {
 826         return clone_stree(top_stree(cond_true_stack));
 827 }
 828 
 829 struct stree *__get_false_states(void)
 830 {
 831         return clone_stree(top_stree(cond_false_stack));
 832 }
 833 
 834 void __use_cond_states(void)
 835 {
 836         struct stree *pre, *pre_clone, *true_states, *false_states;
 837 
 838         pre = pop_stree(&pre_cond_stack);
 839         pre_clone = clone_stree(pre);
 840 
 841         true_states = pop_stree(&cond_true_stack);
 842         overwrite_stree(true_states, &pre);
 843         free_stree(&true_states);
 844         /* we use the true states right away */
 845         free_stree(&cur_stree);
 846         cur_stree = pre;
 847 
 848         false_states = pop_stree(&cond_false_stack);
 849         overwrite_stree(false_states, &pre_clone);
 850         free_stree(&false_states);
 851         push_stree(&false_stack, pre_clone);
 852 }
 853 
 854 void __push_true_states(void)
 855 {
 856         push_stree(&true_stack, clone_stree(cur_stree));
 857 }
 858 
 859 void __use_false_states(void)
 860 {
 861         free_stree(&cur_stree);
 862         cur_stree = pop_stree(&false_stack);
 863 }
 864 
 865 void __discard_false_states(void)
 866 {
 867         struct stree *stree;
 868 
 869         stree = pop_stree(&false_stack);
 870         free_stree(&stree);
 871 }
 872 
 873 void __merge_false_states(void)
 874 {
 875         struct stree *stree;
 876 
 877         stree = pop_stree(&false_stack);
 878         merge_stree(&cur_stree, stree);
 879         free_stree(&stree);
 880 }
 881 
 882 /*
 883  * This function probably seemed common sensical when I wrote it but, oh wow,
 884  * does it look subtle in retrospect.  Say we set a state on one side of the if
 885  * else path but not on the other, then what we should record in the fake stree
 886  * is the merged state.
 887  *
 888  * This function relies on the fact that the we always set the cur_stree as well
 889  * and we already have the infrastructure to merge things correctly into the
 890  * cur_stree.
 891  *
 892  * So instead of merging fake strees together which is probably a lot of work,
 893  * we just use it as a list of set states and look up the actual current values
 894  * in the cur_stree.
 895  *
 896  */
 897 static void update_stree_with_merged(struct stree **stree)
 898 {
 899         struct state_list *slist = NULL;
 900         struct sm_state *sm, *new;
 901 
 902         FOR_EACH_SM(*stree, sm) {
 903                 new = get_sm_state(sm->owner, sm->name, sm->sym);
 904                 if (!new)  /* This can happen if we go out of scope */
 905                         continue;
 906                 add_ptr_list(&slist, new);
 907         } END_FOR_EACH_SM(sm);
 908 
 909         FOR_EACH_PTR(slist, sm) {
 910                 overwrite_sm_state_stree(stree, sm);
 911         } END_FOR_EACH_PTR(sm);
 912 
 913         free_slist(&slist);
 914 }
 915 
 916 static void update_fake_stree_with_merged(void)
 917 {
 918         struct stree *stree;
 919 
 920         if (!fake_cur_stree_stack)
 921                 return;
 922         stree = pop_stree(&fake_cur_stree_stack);
 923         update_stree_with_merged(&stree);
 924         push_stree(&fake_cur_stree_stack, stree);
 925 }
 926 
 927 void __merge_true_states(void)
 928 {
 929         struct stree *stree;
 930 
 931         stree = pop_stree(&true_stack);
 932         merge_stree(&cur_stree, stree);
 933         update_fake_stree_with_merged();
 934         free_stree(&stree);
 935 }
 936 
 937 void __push_continues(void)
 938 {
 939         push_stree(&continue_stack, NULL);
 940 }
 941 
 942 void __discard_continues(void)
 943 {
 944         struct stree *stree;
 945 
 946         stree = pop_stree(&continue_stack);
 947         free_stree(&stree);
 948 }
 949 
 950 void __process_continues(void)
 951 {
 952         struct stree *stree;
 953 
 954         stree = pop_stree(&continue_stack);
 955         if (!stree)
 956                 stree = clone_stree(cur_stree);
 957         else
 958                 merge_stree(&stree, cur_stree);
 959 
 960         push_stree(&continue_stack, stree);
 961 }
 962 
 963 void __merge_continues(void)
 964 {
 965         struct stree *stree;
 966 
 967         stree = pop_stree(&continue_stack);
 968         merge_stree(&cur_stree, stree);
 969         free_stree(&stree);
 970 }
 971 
 972 void __push_breaks(void)
 973 {
 974         push_stree(&break_stack, NULL);
 975         if (fake_cur_stree_stack)
 976                 push_stree(&fake_break_stack, NULL);
 977 }
 978 
 979 void __process_breaks(void)
 980 {
 981         struct stree *stree;
 982 
 983         stree = pop_stree(&break_stack);
 984         if (!stree)
 985                 stree = clone_stree(cur_stree);
 986         else
 987                 merge_stree(&stree, cur_stree);
 988         push_stree(&break_stack, stree);
 989 
 990         if (!fake_cur_stree_stack)
 991                 return;
 992 
 993         stree = pop_stree(&fake_break_stack);
 994         if (!stree)
 995                 stree = clone_stree(top_stree(fake_cur_stree_stack));
 996         else
 997                 merge_stree(&stree, top_stree(fake_cur_stree_stack));
 998         push_stree(&fake_break_stack, stree);
 999 }
1000 
1001 int __has_breaks(void)
1002 {
1003         struct stree *stree;
1004         int ret;
1005 
1006         stree = pop_stree(&break_stack);
1007         ret = !!stree;
1008         push_stree(&break_stack, stree);
1009         return ret;
1010 }
1011 
1012 void __merge_breaks(void)
1013 {
1014         struct stree *stree;
1015         struct sm_state *sm;
1016 
1017         stree = pop_stree(&break_stack);
1018         merge_stree(&cur_stree, stree);
1019         free_stree(&stree);
1020 
1021         if (!fake_cur_stree_stack)
1022                 return;
1023 
1024         stree = pop_stree(&fake_break_stack);
1025         update_stree_with_merged(&stree);
1026         FOR_EACH_SM(stree, sm) {
1027                 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1028         } END_FOR_EACH_SM(sm);
1029         free_stree(&stree);
1030 }
1031 
1032 void __use_breaks(void)
1033 {
1034         struct stree *stree;
1035         struct sm_state *sm;
1036 
1037         free_stree(&cur_stree);
1038         cur_stree = pop_stree(&break_stack);
1039 
1040         if (!fake_cur_stree_stack)
1041                 return;
1042         stree = pop_stree(&fake_break_stack);
1043         FOR_EACH_SM(stree, sm) {
1044                 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1045         } END_FOR_EACH_SM(sm);
1046         free_stree(&stree);
1047 
1048 
1049 }
1050 
1051 void __save_switch_states(struct expression *switch_expr)
1052 {
1053         struct range_list *rl;
1054 
1055         get_absolute_rl(switch_expr, &rl);
1056 
1057         push_rl(&remaining_cases, rl);
1058         push_stree(&switch_stack, clone_stree(cur_stree));
1059 }
1060 
1061 int have_remaining_cases(void)
1062 {
1063         return !!top_rl(remaining_cases);
1064 }
1065 
1066 void __merge_switches(struct expression *switch_expr, struct range_list *case_rl)
1067 {
1068         struct stree *stree;
1069         struct stree *implied_stree;
1070 
1071         stree = pop_stree(&switch_stack);
1072         implied_stree = __implied_case_stree(switch_expr, case_rl, &remaining_cases, &stree);
1073         merge_stree(&cur_stree, implied_stree);
1074         free_stree(&implied_stree);
1075         push_stree(&switch_stack, stree);
1076 }
1077 
1078 void __discard_switches(void)
1079 {
1080         struct stree *stree;
1081 
1082         pop_rl(&remaining_cases);
1083         stree = pop_stree(&switch_stack);
1084         free_stree(&stree);
1085 }
1086 
1087 void __push_default(void)
1088 {
1089         push_stree(&default_stack, NULL);
1090 }
1091 
1092 void __set_default(void)
1093 {
1094         set_state_stree_stack(&default_stack, 0, "has_default", NULL, &true_state);
1095 }
1096 
1097 int __pop_default(void)
1098 {
1099         struct stree *stree;
1100 
1101         stree = pop_stree(&default_stack);
1102         if (stree) {
1103                 free_stree(&stree);
1104                 return 1;
1105         }
1106         return 0;
1107 }
1108 
1109 static struct named_stree *alloc_named_stree(const char *name, struct symbol *sym, struct stree *stree)
1110 {
1111         struct named_stree *named_stree = __alloc_named_stree(0);
1112 
1113         named_stree->name = (char *)name;
1114         named_stree->stree = stree;
1115         named_stree->sym = sym;
1116         return named_stree;
1117 }
1118 
1119 void __save_gotos(const char *name, struct symbol *sym)
1120 {
1121         struct stree **stree;
1122         struct stree *clone;
1123 
1124         stree = get_named_stree(goto_stack, name, sym);
1125         if (stree) {
1126                 merge_stree(stree, cur_stree);
1127                 return;
1128         } else {
1129                 struct named_stree *named_stree;
1130 
1131                 clone = clone_stree(cur_stree);
1132                 named_stree = alloc_named_stree(name, sym, clone);
1133                 add_ptr_list(&goto_stack, named_stree);
1134         }
1135 }
1136 
1137 void __merge_gotos(const char *name, struct symbol *sym)
1138 {
1139         struct stree **stree;
1140 
1141         stree = get_named_stree(goto_stack, name, sym);
1142         if (stree)
1143                 merge_stree(&cur_stree, *stree);
1144 }