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