smatch_states.c

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