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