smatch_slist.c

   1 /*
   2  * sparse/smatch_slist.c
   3  *
   4  * Copyright (C) 2008,2009 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include "smatch.h"
  13 #include "smatch_slist.h"
  14
  15 #undef CHECKORDER
  16
  17 ALLOCATOR(sm_state, "smatch state");
  18 ALLOCATOR(named_slist, "named slist");
  19
  20 void __print_slist(struct state_list *slist)
  21 {
  22         struct sm_state *state;
  23         struct sm_state *poss;
  24         int i;
  25
  26         printf("dumping slist at %d\n", get_lineno());
  27         FOR_EACH_PTR(slist, state) {
  28                 printf("%d '%s'=%s (", state->owner, state->name,
  29                         show_state(state->state));
  30                 i = 0;
  31                 FOR_EACH_PTR(state->possible, poss) {
  32                         if (i++)
  33                                 printf(", ");
  34                         printf("%s", show_state(poss->state));
  35                 } END_FOR_EACH_PTR(poss);
  36                 printf(")\n");
  37         } END_FOR_EACH_PTR(state);
  38         printf("---\n");
  39 }
  40
  41
  42 /* NULL states go at the end to simplify merge_slist */
  43 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
  44 {
  45         int ret;
  46
  47         if (!a && !b)
  48                 return 0;
  49         if (!b)
  50                 return -1;
  51         if (!a)
  52                 return 1;
  53
  54         if (a->owner > b->owner)
  55                 return -1;
  56         if (a->owner < b->owner)
  57                 return 1;
  58
  59         ret = strcmp(a->name, b->name);
  60         if (ret)
  61                 return ret;
  62
  63         if (!b->sym && a->sym)
  64                 return -1;
  65         if (!a->sym && b->sym)
  66                 return 1;
  67         if (a->sym > b->sym)
  68                 return -1;
  69         if (a->sym < b->sym)
  70                 return 1;
  71
  72         return 0;
  73 }
  74
  75 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b)
  76 {
  77         int ret;
  78
  79         ret = cmp_tracker(a, b);
  80         if (ret)
  81                 return ret;
  82
  83         /* todo:  add hook for smatch_extra.c */
  84         if (a->state > b->state)
  85                 return -1;
  86         if (a->state < b->state)
  87                 return 1;
  88         return 0;
  89 }
  90
  91 void add_sm_state_slist(struct state_list **slist, struct sm_state *new)
  92 {
  93         struct sm_state *tmp;
  94
  95         FOR_EACH_PTR(*slist, tmp) {
  96                 if (cmp_sm_states(tmp, new) < 0)
  97                         continue;
  98                 else if (cmp_sm_states(tmp, new) == 0) {
  99                         return;
 100                 } else {
 101                         INSERT_CURRENT(new, tmp);
 102                         return;
 103                 }
 104         } END_FOR_EACH_PTR(tmp);
 105         add_ptr_list(slist, new);
 106 }
 107
 108 static void add_possible(struct sm_state *sm, struct sm_state *new)
 109 {
 110         struct sm_state *tmp;
 111         struct sm_state *tmp2;
 112
 113         if (!new) {
 114                 struct smatch_state *s;
 115
 116                 s = merge_states(sm->name, sm->owner, sm->sym, sm->state, NULL);
 117                 tmp = alloc_state(sm->name, sm->owner, sm->sym, s);
 118                 add_sm_state_slist(&sm->possible, tmp);
 119                 return;
 120         }
 121
 122         FOR_EACH_PTR(new->possible, tmp) {
 123                 tmp2 = alloc_state(tmp->name, tmp->owner, tmp->sym, tmp->state);
 124                 add_sm_state_slist(&sm->possible, tmp2);
 125         } END_FOR_EACH_PTR(tmp);
 126 }
 127
 128 struct sm_state *alloc_state(const char *name, int owner,
 129                              struct symbol *sym, struct smatch_state *state)
 130 {
 131         struct sm_state *sm_state = __alloc_sm_state(0);
 132
 133         sm_state->name = alloc_string(name);
 134         sm_state->owner = owner;
 135         sm_state->sym = sym;
 136         sm_state->state = state;
 137         sm_state->my_pools = NULL;
 138         sm_state->all_pools = NULL;
 139         sm_state->possible = NULL;
 140         add_ptr_list(&sm_state->possible, sm_state);
 141         return sm_state;
 142 }
 143
 144 static void free_sm_state_lists(struct allocation_blob *blob)
 145 {
 146         unsigned int size = sizeof(struct sm_state);
 147         unsigned int offset = 0;
 148
 149         while (offset < blob->offset) {
 150                 struct sm_state *sm = (struct sm_state *)(blob->data + offset);
 151
 152                 free_string(sm->name);
 153                 free_slist(&sm->possible);
 154                 free_stack(&sm->my_pools);
 155                 free_stack(&sm->all_pools);
 156                 offset += size;
 157         }
 158 }
 159
 160 /* At the end of every function we free all the sm_states */
 161 void free_every_single_sm_state()
 162 {
 163         struct allocator_struct *desc = &sm_state_allocator;
 164         struct allocation_blob *blob = desc->blobs;
 165
 166         desc->blobs = NULL;
 167         desc->allocations = 0;
 168         desc->total_bytes = 0;
 169         desc->useful_bytes = 0;
 170         desc->freelist = NULL;
 171         while (blob) {
 172                 struct allocation_blob *next = blob->next;
 173                 free_sm_state_lists(blob);
 174                 blob_free(blob, desc->chunking);
 175                 blob = next;
 176         }
 177 }
 178
 179 struct sm_state *clone_state(struct sm_state *s)
 180 {
 181         struct sm_state *ret;
 182         struct sm_state *poss;
 183
 184         ret = alloc_state(s->name, s->owner, s->sym, s->state);
 185         ret->my_pools = clone_stack(s->my_pools);
 186         ret->all_pools = clone_stack(s->all_pools);
 187         FOR_EACH_PTR(s->possible, poss) {
 188                 add_sm_state_slist(&ret->possible, poss);
 189         } END_FOR_EACH_PTR(poss);
 190         return ret;
 191 }
 192
 193 int slist_has_state(struct state_list *slist, struct smatch_state *state)
 194 {
 195         struct sm_state *tmp;
 196
 197         FOR_EACH_PTR(slist, tmp) {
 198                 if (tmp->state == state)
 199                         return 1;
 200         } END_FOR_EACH_PTR(tmp);
 201         return 0;
 202 }
 203
 204 #ifdef CHECKORDER
 205 static void check_order(struct state_list *slist)
 206 {
 207         struct sm_state *state;
 208         struct sm_state *last = NULL;
 209         int printed = 0;
 210
 211         FOR_EACH_PTR(slist, state) {
 212                 if (last && cmp_tracker(state, last) <= 0) {
 213                         printf("Error.  Unsorted slist %d vs %d, %p vs %p, "
 214                                "%s vs %s\n", last->owner, state->owner,
 215                                last->sym, state->sym, last->name, state->name);
 216                         printed = 1;
 217                 }
 218                 last = state;
 219         } END_FOR_EACH_PTR(state);
 220
 221         if (printed)
 222                 printf("======\n");
 223 }
 224 #endif
 225
 226 struct state_list *clone_slist(struct state_list *from_slist)
 227 {
 228         struct sm_state *state;
 229         struct sm_state *tmp;
 230         struct state_list *to_slist = NULL;
 231
 232         FOR_EACH_PTR(from_slist, state) {
 233                 tmp = clone_state(state);
 234                 add_ptr_list(&to_slist, tmp);
 235         } END_FOR_EACH_PTR(state);
 236 #ifdef CHECKORDER
 237         check_order(to_slist);
 238 #endif
 239         return to_slist;
 240 }
 241
 242 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
 243 {
 244         struct state_list *slist;
 245         struct state_list_stack *to_stack = NULL;
 246
 247         FOR_EACH_PTR(from_stack, slist) {
 248                 push_slist(&to_stack, slist);
 249         } END_FOR_EACH_PTR(slist);
 250         return to_stack;
 251 }
 252
 253 struct smatch_state *merge_states(const char *name, int owner,
 254                                   struct symbol *sym,
 255                                   struct smatch_state *state1,
 256                                   struct smatch_state *state2)
 257 {
 258         struct smatch_state *ret;
 259
 260         if (state1 == state2)
 261                 ret = state1;
 262         else if (__has_merge_function(owner))
 263                 ret = __client_merge_function(owner, name, sym, state1, state2);
 264         else if (!state1 || !state2)
 265                 ret = &undefined;
 266         else
 267                 ret = &merged;
 268         return ret;
 269 }
 270
 271 /*
 272  * add_pool() adds a slist to ->pools. If the slist has already been
 273  * added earlier then it doesn't get added a second time.
 274  */
 275 static void add_pool(struct state_list_stack **pools, struct state_list *new)
 276 {
 277         struct state_list *tmp;
 278
 279         FOR_EACH_PTR(*pools, tmp) {
 280                 if (tmp < new)
 281                         continue;
 282                 else if (tmp == new) {
 283                         return;
 284                 } else {
 285                         INSERT_CURRENT(new, tmp);
 286                         return;
 287                 }
 288         } END_FOR_EACH_PTR(tmp);
 289         add_ptr_list(pools, new);
 290 }
 291
 292 static void copy_pools(struct sm_state *to, struct sm_state *sm)
 293 {
 294         struct state_list *tmp;
 295
 296         if (!sm)
 297                 return;
 298
 299         FOR_EACH_PTR(sm->my_pools, tmp) {
 300                 add_pool(&to->my_pools, tmp);
 301         } END_FOR_EACH_PTR(tmp);
 302
 303         FOR_EACH_PTR(sm->all_pools, tmp) {
 304                 add_pool(&to->all_pools, tmp);
 305         } END_FOR_EACH_PTR(tmp);
 306 }
 307
 308 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
 309 {
 310         struct smatch_state *s;
 311         struct sm_state *result;
 312
 313         s = merge_states(one->name, one->owner, one->sym, one->state,
 314                         (two?two->state:NULL));
 315         result = alloc_state(one->name, one->owner, one->sym, s);
 316         add_possible(result, one);
 317         add_possible(result, two);
 318         copy_pools(result, one);
 319         copy_pools(result, two);
 320
 321         if (debug_states) {
 322                 struct sm_state *tmp;
 323                 int i = 0;
 324
 325                 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
 326                         get_lineno(), one->name, one->owner,
 327                         show_state(one->state), show_state(two?two->state:NULL),
 328                         show_state(s));
 329
 330                 FOR_EACH_PTR(result->possible, tmp) {
 331                         if (i++) {
 332                                 printf(", ");
 333                         }
 334                         printf("%s", show_state(tmp->state));
 335                 } END_FOR_EACH_PTR(tmp);
 336                 printf(")\n");
 337         }
 338
 339         return result;
 340 }
 341
 342 struct sm_state *get_sm_state_slist(struct state_list *slist, const char *name,
 343                                 int owner, struct symbol *sym)
 344 {
 345         struct sm_state *state;
 346
 347         if (!name)
 348                 return NULL;
 349
 350         FOR_EACH_PTR(slist, state) {
 351                 if (state->owner == owner && state->sym == sym
 352                     && !strcmp(state->name, name))
 353                         return state;
 354         } END_FOR_EACH_PTR(state);
 355         return NULL;
 356 }
 357
 358 struct smatch_state *get_state_slist(struct state_list *slist,
 359                                 const char *name, int owner,
 360                                 struct symbol *sym)
 361 {
 362         struct sm_state *state;
 363
 364         state = get_sm_state_slist(slist, name, owner, sym);
 365         if (state)
 366                 return state->state;
 367         return NULL;
 368 }
 369
 370 void overwrite_sm_state(struct state_list **slist, struct sm_state *new)
 371 {
 372         struct sm_state *tmp;
 373
 374         FOR_EACH_PTR(*slist, tmp) {
 375                 if (cmp_tracker(tmp, new) < 0)
 376                         continue;
 377                 else if (cmp_tracker(tmp, new) == 0) {
 378                         REPLACE_CURRENT_PTR(tmp, new);
 379                         return;
 380                 } else {
 381                         INSERT_CURRENT(new, tmp);
 382                         return;
 383                 }
 384         } END_FOR_EACH_PTR(tmp);
 385         add_ptr_list(slist, new);
 386 }
 387
 388 void overwrite_sm_state_stack(struct state_list_stack **stack,
 389                         struct sm_state *state)
 390 {
 391         struct state_list *slist;
 392
 393         slist = pop_slist(stack);
 394         overwrite_sm_state(&slist, state);
 395         push_slist(stack, slist);
 396 }
 397
 398 void set_state_slist(struct state_list **slist, const char *name, int owner,
 399                      struct symbol *sym, struct smatch_state *state)
 400 {
 401         struct sm_state *tmp;
 402         struct sm_state *new = alloc_state(name, owner, sym, state);
 403
 404         FOR_EACH_PTR(*slist, tmp) {
 405                 if (cmp_tracker(tmp, new) < 0)
 406                         continue;
 407                 else if (cmp_tracker(tmp, new) == 0) {
 408                         REPLACE_CURRENT_PTR(tmp, new);
 409                         return;
 410                 } else {
 411                         INSERT_CURRENT(new, tmp);
 412                         return;
 413                 }
 414         } END_FOR_EACH_PTR(tmp);
 415         add_ptr_list(slist, new);
 416 }
 417
 418 void delete_state_slist(struct state_list **slist, const char *name, int owner,
 419                         struct symbol *sym)
 420 {
 421         struct sm_state *state;
 422
 423         FOR_EACH_PTR(*slist, state) {
 424                 if (state->owner == owner && state->sym == sym
 425                     && !strcmp(state->name, name)){
 426                         delete_ptr_list_entry((struct ptr_list **)slist,
 427                                               state, 1);
 428                         return;
 429                 }
 430         } END_FOR_EACH_PTR(state);
 431 }
 432
 433
 434 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 435 {
 436         add_ptr_list(list_stack, slist);
 437 }
 438
 439 struct state_list *pop_slist(struct state_list_stack **list_stack)
 440 {
 441         struct state_list *slist;
 442
 443         slist = last_ptr_list((struct ptr_list *)*list_stack);
 444         delete_ptr_list_last((struct ptr_list **)list_stack);
 445         return slist;
 446 }
 447
 448 void free_slist(struct state_list **slist)
 449 {
 450         __free_ptr_list((struct ptr_list **)slist);
 451 }
 452
 453 void free_stack(struct state_list_stack **stack)
 454 {
 455         __free_ptr_list((struct ptr_list **)stack);
 456 }
 457
 458 void free_stack_and_slists(struct state_list_stack **slist_stack)
 459 {
 460         struct state_list *slist;
 461
 462         FOR_EACH_PTR(*slist_stack, slist) {
 463                 free_slist(&slist);
 464         } END_FOR_EACH_PTR(slist);
 465         free_stack(slist_stack);
 466 }
 467
 468 /*
 469  * set_state_stack() sets the state for the top slist on the stack.
 470  */
 471 void set_state_stack(struct state_list_stack **stack, const char *name,
 472                      int owner, struct symbol *sym, struct smatch_state *state)
 473 {
 474         struct state_list *slist;
 475
 476         slist = pop_slist(stack);
 477         set_state_slist(&slist, name, owner, sym, state);
 478         push_slist(stack, slist);
 479 }
 480
 481 /*
 482  * get_state_stack() gets the state for the top slist on the stack.
 483  */
 484 struct smatch_state *get_state_stack(struct state_list_stack *stack,
 485                                      const char *name, int owner,
 486                                      struct symbol *sym)
 487 {
 488         struct state_list *slist;
 489         struct smatch_state *ret;
 490
 491         slist = pop_slist(&stack);
 492         ret = get_state_slist(slist, name, owner, sym);
 493         push_slist(&stack, slist);
 494         return ret;
 495 }
 496
 497 /*
 498  * We want to find which states have been modified inside a branch.
 499  * If you have 2 &merged states they could be different states really
 500  * and maybe one or both were modified.  We say it is unchanged if
 501  * the ->state pointers are the same and they belong to the same pools.
 502  * If they have been modified on both sides of a branch to the same thing,
 503  * it's still OK to say they are the same, because that means they won't
 504  * belong to any pools.
 505  */
 506 static int is_really_same(struct sm_state *one, struct sm_state *two)
 507 {
 508         struct state_list *tmp1;
 509         struct state_list *tmp2;
 510
 511         if (one->state != two->state)
 512                 return 0;
 513
 514         PREPARE_PTR_LIST(one->my_pools, tmp1);
 515         PREPARE_PTR_LIST(two->my_pools, tmp2);
 516         for (;;) {
 517                 if (!tmp1 && !tmp2)
 518                         return 1;
 519                 if (tmp1 < tmp2) {
 520                         return 0;
 521                 } else if (tmp1 == tmp2) {
 522                         NEXT_PTR_LIST(tmp1);
 523                         NEXT_PTR_LIST(tmp2);
 524                 } else {
 525                         return 0;
 526                 }
 527         }
 528         FINISH_PTR_LIST(tmp2);
 529         FINISH_PTR_LIST(tmp1);
 530         return 1;
 531 }
 532
 533 /*
 534  * merge_slist() is called whenever paths merge, such as after
 535  * an if statement.  It takes the two slists and creates one.
 536  */
 537 void merge_slist(struct state_list **to, struct state_list *slist)
 538 {
 539         struct sm_state *to_state, *state, *tmp;
 540         struct state_list *results = NULL;
 541         struct state_list *implied_to = NULL;
 542         struct state_list *implied_from = NULL;
 543
 544 #ifdef CHECKORDER
 545         check_order(*to);
 546         check_order(slist);
 547 #endif
 548
 549         /* merging a null and nonnull path gives you only the nonnull path */
 550         if (!slist) {
 551                 return;
 552         }
 553         if (!*to) {
 554                 *to = clone_slist(slist);
 555                 return;
 556         }
 557
 558         implied_to = clone_slist(*to);
 559         implied_from = clone_slist(slist);
 560
 561         PREPARE_PTR_LIST(*to, to_state);
 562         PREPARE_PTR_LIST(slist, state);
 563         for (;;) {
 564                 if (!to_state && !state)
 565                         break;
 566                 if (cmp_tracker(to_state, state) < 0) {
 567                         tmp = merge_sm_states(to_state, NULL);
 568                         add_pool(&tmp->my_pools, implied_to);
 569                         add_pool(&tmp->all_pools, implied_to);
 570                         add_ptr_list(&results, tmp);
 571                         NEXT_PTR_LIST(to_state);
 572                 } else if (cmp_tracker(to_state, state) == 0) {
 573                         tmp = merge_sm_states(to_state, state);
 574                         if (!is_really_same(to_state, state)) {
 575                                 add_pool(&tmp->my_pools, implied_to);
 576                                 add_pool(&tmp->my_pools, implied_from);
 577                         }
 578                         add_pool(&tmp->all_pools, implied_to);
 579                         add_pool(&tmp->all_pools, implied_from);
 580                         add_ptr_list(&results, tmp);
 581                         NEXT_PTR_LIST(to_state);
 582                         NEXT_PTR_LIST(state);
 583                 } else {
 584                         tmp = merge_sm_states(state, NULL);
 585                         add_pool(&tmp->my_pools, implied_from);
 586                         add_pool(&tmp->all_pools, implied_from);
 587                         add_ptr_list(&results, tmp);
 588                         NEXT_PTR_LIST(state);
 589                 }
 590         }
 591         FINISH_PTR_LIST(state);
 592         FINISH_PTR_LIST(to_state);
 593
 594         free_slist(to);
 595         *to = results;
 596
 597         push_slist(&implied_pools, implied_from);
 598         push_slist(&implied_pools, implied_to);
 599 }
 600
 601 static int pool_in_pools(struct state_list_stack *pools,
 602                         struct state_list *pool)
 603 {
 604         struct state_list *tmp;
 605
 606         FOR_EACH_PTR(pools, tmp) {
 607                 if (tmp == pool)
 608                         return 1;
 609         } END_FOR_EACH_PTR(tmp);
 610         return 0;
 611 }
 612
 613 struct state_list *clone_states_in_pool(struct state_list *pool,
 614                                 struct state_list *cur_slist)
 615 {
 616         struct sm_state *state;
 617         struct sm_state *cur_state;
 618         struct sm_state *tmp;
 619         struct state_list *to_slist = NULL;
 620
 621         FOR_EACH_PTR(pool, state) {
 622                 cur_state = get_sm_state_slist(cur_slist, state->name,
 623                                         state->owner, state->sym);
 624                 if (!cur_state)
 625                         continue;
 626                 if (is_really_same(state, cur_state))
 627                         continue;
 628                 if (pool_in_pools(cur_state->all_pools, pool)) {
 629                         tmp = clone_state(state);
 630                         add_ptr_list(&to_slist, tmp);
 631                 }
 632         } END_FOR_EACH_PTR(state);
 633         return to_slist;
 634 }
 635
 636 /*
 637  * merge_implied() takes an implied state and another possibly implied state
 638  * from another pool.  It checks that the second pool is reachable from
 639  * cur_slist then merges the two states and returns the result.
 640  */
 641 struct sm_state *merge_implied(struct sm_state *one, struct sm_state *two,
 642                                 struct state_list *pool,
 643                                 struct state_list *cur_slist)
 644 {
 645         struct sm_state *cur_state;
 646
 647         cur_state = get_sm_state_slist(cur_slist, two->name, two->owner,
 648                                 two->sym);
 649         if (!cur_state)
 650                 return NULL;  /* this can't actually happen */
 651         if (!pool_in_pools(cur_state->all_pools, pool))
 652                 return NULL;
 653         return merge_sm_states(one, two);
 654 }
 655
 656 /*
 657  * filter() is used to find what states are the same across
 658  * a series of slists.
 659  * It takes a **slist and a *filter.
 660  * It removes everything from **slist that isn't in *filter.
 661  * The reason you would want to do this is if you want to
 662  * know what other states are true if one state is true.  (smatch_implied).
 663  */
 664 void filter(struct state_list **slist, struct state_list *filter,
 665         struct state_list *cur_slist)
 666 {
 667         struct sm_state *s_one, *s_two;
 668         struct state_list *results = NULL;
 669         struct sm_state *tmp;
 670
 671 #ifdef CHECKORDER
 672         check_order(*slist);
 673         check_order(filter);
 674 #endif
 675
 676         PREPARE_PTR_LIST(*slist, s_one);
 677         PREPARE_PTR_LIST(filter, s_two);
 678         for (;;) {
 679                 if (!s_one || !s_two)
 680                         break;
 681                 if (cmp_tracker(s_one, s_two) < 0) {
 682                         NEXT_PTR_LIST(s_one);
 683                 } else if (cmp_tracker(s_one, s_two) == 0) {
 684                         tmp = merge_implied(s_one, s_two, filter, cur_slist);
 685                         if (tmp)
 686                                 add_ptr_list(&results, tmp);
 687                         NEXT_PTR_LIST(s_one);
 688                         NEXT_PTR_LIST(s_two);
 689                 } else {
 690                         NEXT_PTR_LIST(s_two);
 691                 }
 692         }
 693         FINISH_PTR_LIST(s_two);
 694         FINISH_PTR_LIST(s_one);
 695
 696         free_slist(slist);
 697         *slist = results;
 698 }
 699
 700 /*
 701  * and_slist_stack() is basically the same as popping the top two slists,
 702  * overwriting the one with the other and pushing it back on the stack.
 703  * The difference is that it checks to see that a mutually exclusive
 704  * state isn't included in both stacks.  If smatch sees something like
 705  * "if (a && !a)" it prints a warning.
 706  */
 707 void and_slist_stack(struct state_list_stack **slist_stack)
 708 {
 709         struct sm_state *tmp;
 710         struct smatch_state *tmp_state;
 711         struct state_list *tmp_slist = pop_slist(slist_stack);
 712
 713         FOR_EACH_PTR(tmp_slist, tmp) {
 714                 tmp_state = get_state_stack(*slist_stack, tmp->name,
 715                                             tmp->owner, tmp->sym);
 716                 if (tmp_state && tmp_state != tmp->state) {
 717                         smatch_msg("mutually exclusive 'and' conditions states "
 718                                 "'%s': %s + %s",
 719                                 tmp->name, show_state(tmp_state),
 720                                 show_state(tmp->state));
 721                 }
 722                 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
 723                                 tmp->state);
 724         } END_FOR_EACH_PTR(tmp);
 725         free_slist(&tmp_slist);
 726 }
 727
 728 /*
 729  * or_slist_stack() is for if we have:  if (foo || bar) { foo->baz;
 730  * It pops the two slists from the top of the stack and merges them
 731  * together in a way that preserves the things they have in common
 732  * but creates a merged state for most of the rest.
 733  * You could have code that had:  if (foo || foo) { foo->baz;
 734  * It's this function which ensures smatch does the right thing.
 735  */
 736 void or_slist_stack(struct state_list_stack **pre_conds,
 737                     struct state_list *cur_slist,
 738                     struct state_list_stack **slist_stack)
 739 {
 740         struct state_list *new;
 741         struct state_list *old;
 742         struct state_list *res = NULL;
 743         struct state_list *tmp_slist;
 744         struct state_list *tmp_slist2;
 745         struct sm_state *tmp;
 746         struct sm_state *sm;
 747         struct sm_state *new_sm;
 748
 749         new = pop_slist(slist_stack);
 750         old = pop_slist(slist_stack);
 751
 752         tmp_slist = pop_slist(pre_conds);
 753         tmp_slist2 = clone_slist(tmp_slist);
 754         push_slist(pre_conds, tmp_slist);
 755         overwrite_slist(old, &tmp_slist2);
 756         FOR_EACH_PTR(new, tmp) {
 757                 sm = get_sm_state_slist(tmp_slist2, tmp->name, tmp->owner,
 758                                         tmp->sym);
 759                 new_sm = merge_sm_states(tmp, sm);
 760                 add_ptr_list(&res, new_sm);
 761         } END_FOR_EACH_PTR(tmp);
 762         free_slist(&tmp_slist2);
 763
 764         tmp_slist2 = clone_slist(cur_slist);
 765         overwrite_slist(new, &tmp_slist2);
 766         FOR_EACH_PTR(old, tmp) {
 767                 sm = get_sm_state_slist(tmp_slist2, tmp->name, tmp->owner,
 768                                         tmp->sym);
 769                 new_sm = merge_sm_states(tmp, sm);
 770                 add_ptr_list(&res, new_sm);
 771         } END_FOR_EACH_PTR(tmp);
 772         free_slist(&tmp_slist2);
 773
 774         push_slist(slist_stack, res);
 775
 776         free_slist(&new);
 777         free_slist(&old);
 778 }
 779
 780 /*
 781  * get_slist_from_named_stack() is only used for gotos.
 782  */
 783 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
 784                                               const char *name)
 785 {
 786         struct named_slist *tmp;
 787
 788         FOR_EACH_PTR(stack, tmp) {
 789                 if (!strcmp(tmp->name, name))
 790                         return &tmp->slist;
 791         } END_FOR_EACH_PTR(tmp);
 792         return NULL;
 793 }
 794
 795 void overwrite_slist(struct state_list *from, struct state_list **to)
 796 {
 797         struct sm_state *tmp;
 798
 799         FOR_EACH_PTR(from, tmp) {
 800                 overwrite_sm_state(to, tmp);
 801         } END_FOR_EACH_PTR(tmp);
 802 }
 803
 804 unsigned int __get_allocations()
 805 {
 806         return sm_state_allocator.allocations;
 807 }