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