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
  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->merged = 0;
 165         sm_state->my_pools = NULL;
 166         sm_state->pre_merge = 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_slist(&sm->pre_merge);
 176         free_stack(&sm->my_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
 220         ret = alloc_state_no_name(s->name, s->owner, s->sym, s->state);
 221         ret->line = s->line;
 222         ret->merged = s->merged;
 223         ret->my_pools = clone_stack(s->my_pools);
 224         ret->possible = clone_slist(s->possible);
 225         ret->pre_merge = clone_slist(s->pre_merge);
 226         return ret;
 227 }
 228
 229 int is_merged(struct sm_state *sm)
 230 {
 231         return sm->merged;
 232 }
 233
 234 int slist_has_state(struct state_list *slist, struct smatch_state *state)
 235 {
 236         struct sm_state *tmp;
 237
 238         FOR_EACH_PTR(slist, tmp) {
 239                 if (tmp->state == state)
 240                         return 1;
 241         } END_FOR_EACH_PTR(tmp);
 242         return 0;
 243 }
 244
 245 static void check_order(struct state_list *slist)
 246 {
 247 #ifdef CHECKORDER
 248         struct sm_state *state;
 249         struct sm_state *last = NULL;
 250         int printed = 0;
 251
 252         FOR_EACH_PTR(slist, state) {
 253                 if (last && cmp_tracker(state, last) <= 0) {
 254                         printf("Error.  Unsorted slist %d vs %d, %p vs %p, "
 255                                "%s vs %s\n", last->owner, state->owner,
 256                                last->sym, state->sym, last->name, state->name);
 257                         printed = 1;
 258                 }
 259                 last = state;
 260         } END_FOR_EACH_PTR(state);
 261
 262         if (printed)
 263                 printf("======\n");
 264 #endif
 265 }
 266
 267 struct state_list *clone_slist(struct state_list *from_slist)
 268 {
 269         struct sm_state *state;
 270         struct state_list *to_slist = NULL;
 271
 272         FOR_EACH_PTR(from_slist, state) {
 273                 add_ptr_list(&to_slist, state);
 274         } END_FOR_EACH_PTR(state);
 275         check_order(to_slist);
 276         return to_slist;
 277 }
 278
 279 struct state_list *clone_slist_and_states(struct state_list *from_slist)
 280 {
 281         struct sm_state *state;
 282         struct sm_state *tmp;
 283         struct state_list *to_slist = NULL;
 284
 285         FOR_EACH_PTR(from_slist, state) {
 286                 tmp = clone_state(state);
 287                 add_ptr_list(&to_slist, tmp);
 288         } END_FOR_EACH_PTR(state);
 289         check_order(to_slist);
 290         return to_slist;
 291 }
 292
 293 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
 294 {
 295         struct state_list *slist;
 296         struct state_list_stack *to_stack = NULL;
 297
 298         FOR_EACH_PTR(from_stack, slist) {
 299                 push_slist(&to_stack, slist);
 300         } END_FOR_EACH_PTR(slist);
 301         return to_stack;
 302 }
 303
 304 struct smatch_state *merge_states(const char *name, int owner,
 305                                   struct symbol *sym,
 306                                   struct smatch_state *state1,
 307                                   struct smatch_state *state2)
 308 {
 309         struct smatch_state *ret;
 310
 311         if (state1 == state2)
 312                 ret = state1;
 313         else if (__has_merge_function(owner))
 314                 ret = __client_merge_function(owner, name, sym, state1, state2);
 315         else if (!state1 || !state2)
 316                 ret = &undefined;
 317         else
 318                 ret = &merged;
 319         return ret;
 320 }
 321
 322 /*
 323  * add_pool() adds a slist to ->pools. If the slist has already been
 324  * added earlier then it doesn't get added a second time.
 325  */
 326 void add_pool(struct state_list_stack **pools, struct state_list *new)
 327 {
 328         struct state_list *tmp;
 329
 330         FOR_EACH_PTR(*pools, tmp) {
 331                 if (tmp < new)
 332                         continue;
 333                 else if (tmp == new) {
 334                         return;
 335                 } else {
 336                         INSERT_CURRENT(new, tmp);
 337                         return;
 338                 }
 339         } END_FOR_EACH_PTR(tmp);
 340         add_ptr_list(pools, new);
 341 }
 342
 343 void merge_pools(struct state_list_stack **to, struct state_list_stack *from)
 344 {
 345         struct state_list *tmp;
 346
 347         FOR_EACH_PTR(from, tmp) {
 348                 add_pool(to, tmp);
 349         } END_FOR_EACH_PTR(tmp);
 350 }
 351
 352 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
 353 {
 354         struct smatch_state *s;
 355         struct sm_state *result;
 356
 357         if (one == two)
 358                 return one;
 359         s = merge_states(one->name, one->owner, one->sym, one->state,
 360                         (two?two->state:NULL));
 361         result = alloc_state_no_name(one->name, one->owner, one->sym, s);
 362         if (two && one->line == two->line)
 363                 result->line = one->line;
 364         result->merged = 1;
 365         add_ptr_list(&result->pre_merge, one);
 366         add_ptr_list(&result->pre_merge, two);
 367         add_possible(result, one);
 368         add_possible(result, two);
 369
 370         if (debug_states) {
 371                 struct sm_state *tmp;
 372                 int i = 0;
 373
 374                 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
 375                         get_lineno(), one->name, one->owner,
 376                         show_state(one->state), show_state(two?two->state:NULL),
 377                         show_state(s));
 378
 379                 FOR_EACH_PTR(result->possible, tmp) {
 380                         if (i++) {
 381                                 printf(", ");
 382                         }
 383                         printf("%s", show_state(tmp->state));
 384                 } END_FOR_EACH_PTR(tmp);
 385                 printf(")\n");
 386         }
 387
 388         return result;
 389 }
 390
 391 struct sm_state *get_sm_state_slist(struct state_list *slist, const char *name,
 392                                 int owner, struct symbol *sym)
 393 {
 394         struct sm_state *state;
 395
 396         if (!name)
 397                 return NULL;
 398
 399         FOR_EACH_PTR(slist, state) {
 400                 if (state->owner == owner && state->sym == sym
 401                     && !strcmp(state->name, name))
 402                         return state;
 403         } END_FOR_EACH_PTR(state);
 404         return NULL;
 405 }
 406
 407 struct smatch_state *get_state_slist(struct state_list *slist,
 408                                 const char *name, int owner,
 409                                 struct symbol *sym)
 410 {
 411         struct sm_state *state;
 412
 413         state = get_sm_state_slist(slist, name, owner, sym);
 414         if (state)
 415                 return state->state;
 416         return NULL;
 417 }
 418
 419 void overwrite_sm_state(struct state_list **slist, struct sm_state *new)
 420 {
 421         struct sm_state *tmp;
 422
 423         FOR_EACH_PTR(*slist, tmp) {
 424                 if (cmp_tracker(tmp, new) < 0)
 425                         continue;
 426                 else if (cmp_tracker(tmp, new) == 0) {
 427                         REPLACE_CURRENT_PTR(tmp, new);
 428                         return;
 429                 } else {
 430                         INSERT_CURRENT(new, tmp);
 431                         return;
 432                 }
 433         } END_FOR_EACH_PTR(tmp);
 434         add_ptr_list(slist, new);
 435 }
 436
 437 void overwrite_sm_state_stack(struct state_list_stack **stack,
 438                         struct sm_state *state)
 439 {
 440         struct state_list *slist;
 441
 442         slist = pop_slist(stack);
 443         overwrite_sm_state(&slist, state);
 444         push_slist(stack, slist);
 445 }
 446
 447 void set_state_slist(struct state_list **slist, const char *name, int owner,
 448                      struct symbol *sym, struct smatch_state *state)
 449 {
 450         struct sm_state *tmp;
 451         struct sm_state *new = alloc_state(name, owner, sym, state);
 452
 453         FOR_EACH_PTR(*slist, tmp) {
 454                 if (cmp_tracker(tmp, new) < 0)
 455                         continue;
 456                 else if (cmp_tracker(tmp, new) == 0) {
 457                         REPLACE_CURRENT_PTR(tmp, new);
 458                         return;
 459                 } else {
 460                         INSERT_CURRENT(new, tmp);
 461                         return;
 462                 }
 463         } END_FOR_EACH_PTR(tmp);
 464         add_ptr_list(slist, new);
 465 }
 466
 467 void delete_state_slist(struct state_list **slist, const char *name, int owner,
 468                         struct symbol *sym)
 469 {
 470         struct sm_state *state;
 471
 472         FOR_EACH_PTR(*slist, state) {
 473                 if (state->owner == owner && state->sym == sym
 474                     && !strcmp(state->name, name)){
 475                         DELETE_CURRENT_PTR(state);
 476                         return;
 477                 }
 478         } END_FOR_EACH_PTR(state);
 479 }
 480
 481
 482 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 483 {
 484         add_ptr_list(list_stack, slist);
 485 }
 486
 487 struct state_list *pop_slist(struct state_list_stack **list_stack)
 488 {
 489         struct state_list *slist;
 490
 491         slist = last_ptr_list((struct ptr_list *)*list_stack);
 492         delete_ptr_list_last((struct ptr_list **)list_stack);
 493         return slist;
 494 }
 495
 496 void free_slist(struct state_list **slist)
 497 {
 498         __free_ptr_list((struct ptr_list **)slist);
 499 }
 500
 501 void free_stack(struct state_list_stack **stack)
 502 {
 503         __free_ptr_list((struct ptr_list **)stack);
 504 }
 505
 506 void free_stack_and_slists(struct state_list_stack **slist_stack)
 507 {
 508         struct state_list *slist;
 509
 510         FOR_EACH_PTR(*slist_stack, slist) {
 511                 free_slist(&slist);
 512         } END_FOR_EACH_PTR(slist);
 513         free_stack(slist_stack);
 514 }
 515
 516 /*
 517  * set_state_stack() sets the state for the top slist on the stack.
 518  */
 519 void set_state_stack(struct state_list_stack **stack, const char *name,
 520                      int owner, struct symbol *sym, struct smatch_state *state)
 521 {
 522         struct state_list *slist;
 523
 524         slist = pop_slist(stack);
 525         set_state_slist(&slist, name, owner, sym, state);
 526         push_slist(stack, slist);
 527 }
 528
 529 /*
 530  * get_sm_state_stack() gets the state for the top slist on the stack.
 531  */
 532 struct sm_state *get_sm_state_stack(struct state_list_stack *stack,
 533                                     const char *name, int owner,
 534                                     struct symbol *sym)
 535 {
 536         struct state_list *slist;
 537         struct sm_state *ret;
 538
 539         slist = pop_slist(&stack);
 540         ret = get_sm_state_slist(slist, name, owner, sym);
 541         push_slist(&stack, slist);
 542         return ret;
 543 }
 544
 545
 546 struct smatch_state *get_state_stack(struct state_list_stack *stack,
 547                                      const char *name, int owner,
 548                                      struct symbol *sym)
 549 {
 550         struct sm_state *state;
 551
 552         state = get_sm_state_stack(stack, name, owner, sym);
 553         if (state)
 554                 return state->state;
 555         return NULL;
 556 }
 557
 558 static void match_states(struct state_list **one, struct state_list **two)
 559 {
 560         struct sm_state *one_state;
 561         struct sm_state *two_state;
 562         struct sm_state *tmp;
 563         struct smatch_state *tmp_state;
 564         struct state_list *add_to_one = NULL;
 565         struct state_list *add_to_two = NULL;
 566
 567         PREPARE_PTR_LIST(*one, one_state);
 568         PREPARE_PTR_LIST(*two, two_state);
 569         for (;;) {
 570                 if (!one_state && !two_state)
 571                         break;
 572                 if (cmp_tracker(one_state, two_state) < 0) {
 573                         tmp_state = __client_unmatched_state_function(one_state);
 574                         tmp = alloc_state_no_name(one_state->name,
 575                                                   one_state->owner,
 576                                                   one_state->sym, tmp_state);
 577                         add_ptr_list(&add_to_two, tmp);
 578                         NEXT_PTR_LIST(one_state);
 579                 } else if (cmp_tracker(one_state, two_state) == 0) {
 580                         NEXT_PTR_LIST(one_state);
 581                         NEXT_PTR_LIST(two_state);
 582                 } else {
 583                         tmp_state = __client_unmatched_state_function(two_state);
 584                         tmp = alloc_state_no_name(two_state->name,
 585                                                   two_state->owner,
 586                                                   two_state->sym, tmp_state);
 587                         add_ptr_list(&add_to_one, tmp);
 588                         NEXT_PTR_LIST(two_state);
 589                 }
 590         }
 591         FINISH_PTR_LIST(two_state);
 592         FINISH_PTR_LIST(one_state);
 593
 594         overwrite_slist(add_to_one, one);
 595         overwrite_slist(add_to_two, two);
 596 }
 597
 598 /*
 599  * merge_slist() is called whenever paths merge, such as after
 600  * an if statement.  It takes the two slists and creates one.
 601  */
 602 void merge_slist(struct state_list **to, struct state_list *slist)
 603 {
 604         struct sm_state *to_state, *state, *tmp;
 605         struct state_list *results = NULL;
 606         struct state_list *implied_to = NULL;
 607         struct state_list *implied_from = NULL;
 608
 609         check_order(*to);
 610         check_order(slist);
 611
 612         /* merging a null and nonnull path gives you only the nonnull path */
 613         if (!slist) {
 614                 return;
 615         }
 616         if (!*to) {
 617                 *to = clone_slist(slist);
 618                 return;
 619         }
 620
 621         implied_to = clone_slist(*to);
 622         implied_from = clone_slist(slist);
 623
 624         match_states(&implied_to, &implied_from);
 625
 626         PREPARE_PTR_LIST(implied_to, to_state);
 627         PREPARE_PTR_LIST(implied_from, state);
 628         for (;;) {
 629                 if (!to_state && !state)
 630                         break;
 631                 if (cmp_tracker(to_state, state) < 0) {
 632                         smatch_msg("error:  Internal smatch error.");
 633                         NEXT_PTR_LIST(to_state);
 634                 } else if (cmp_tracker(to_state, state) == 0) {
 635                         if (to_state != state) {
 636                                 add_pool(&to_state->my_pools, implied_to);
 637                                 add_pool(&state->my_pools, implied_from);
 638                         }
 639
 640                         tmp = merge_sm_states(to_state, state);
 641                         add_ptr_list(&results, tmp);
 642                         NEXT_PTR_LIST(to_state);
 643                         NEXT_PTR_LIST(state);
 644                 } else {
 645                         smatch_msg("error:  Internal smatch error.");
 646                         NEXT_PTR_LIST(state);
 647                 }
 648         }
 649         FINISH_PTR_LIST(state);
 650         FINISH_PTR_LIST(to_state);
 651
 652         free_slist(to);
 653         *to = results;
 654 }
 655
 656 static struct sm_state *find_intersection(struct sm_state *one,
 657                                           struct sm_state *two)
 658 {
 659         struct state_list *tmp1, *tmp2;
 660         struct state_list_stack *stack = NULL;
 661         struct sm_state *tmp_state;
 662         struct sm_state *ret;
 663         int count = 0;
 664
 665         if (!one)
 666                 return two;
 667
 668         if (one->owner != SMATCH_EXTRA && one->state != &merged) {
 669                 if (one->state == two->state)
 670                         return one;
 671                 if (two->state != &merged) {
 672                         SM_DEBUG("mutually exclusive 'and' conditions states "
 673                                    "'%s': %s + %s\n", one->name,
 674                                    show_state(one->state),
 675                                    show_state(two->state));
 676                         return two;
 677                 }
 678         }
 679         if (one->owner == SMATCH_EXTRA) {
 680                 if (one->state == two->state)
 681                         return one;
 682
 683                 ret = NULL;
 684                 if (!one->my_pools) {
 685                         ret = one;
 686                 }
 687                 if (!two->my_pools) {
 688                         ret = two;
 689                 }
 690                 if (ret)
 691                         return ret;
 692         }
 693
 694         PREPARE_PTR_LIST(one->my_pools, tmp1);
 695         PREPARE_PTR_LIST(two->my_pools, tmp2);
 696         for (;;) {
 697                 if (!tmp1 && !tmp2)
 698                         break;
 699                 if (!tmp2 || (tmp1 && tmp1 < tmp2)) {
 700                         NEXT_PTR_LIST(tmp1);
 701                 } else if (tmp1 == tmp2) {
 702                         push_slist(&stack, tmp1);
 703                         count++;
 704                         NEXT_PTR_LIST(tmp1);
 705                         NEXT_PTR_LIST(tmp2);
 706                 } else {
 707                         NEXT_PTR_LIST(tmp2);
 708                 }
 709         }
 710         FINISH_PTR_LIST(tmp2);
 711         FINISH_PTR_LIST(tmp1);
 712
 713         if (count == 0) {
 714                 SM_DEBUG("mutually eXclusive 'and' conditions states "
 715                            "'%s': %s + %s\n", one->name, show_state(one->state),
 716                            show_state(two->state));
 717                 return two;
 718         }
 719         if (count == 1)
 720                 return get_sm_state_stack(stack, one->name, one->owner,
 721                                           one->sym);
 722
 723         if (one->owner == SMATCH_EXTRA)
 724                 return __extra_and_merge(one, stack);
 725
 726         ret = alloc_state_no_name(one->name, one->owner, one->sym, &merged);
 727         FOR_EACH_PTR(stack, tmp1) {
 728                 tmp_state = get_sm_state_slist(tmp1, one->name, one->owner,
 729                                                one->sym);
 730                 add_possible(ret, tmp_state);
 731         } END_FOR_EACH_PTR(tmp1);
 732         ret->my_pools = stack;
 733         return ret;
 734 }
 735
 736 /*
 737  * and_slist_stack() is basically the same as popping the top two slists,
 738  * overwriting the one with the other and pushing it back on the stack.
 739  * The difference is that it checks to see that a mutually exclusive
 740  * state isn't included in both stacks.  If smatch sees something like
 741  * "if (a && !a)" it prints a warning.
 742  */
 743 void and_slist_stack(struct state_list_stack **slist_stack)
 744 {
 745         struct sm_state *tmp;
 746         struct sm_state *left_state;
 747         struct sm_state *res;
 748         struct state_list *right_slist = pop_slist(slist_stack);
 749
 750         FOR_EACH_PTR(right_slist, tmp) {
 751                 left_state = get_sm_state_stack(*slist_stack, tmp->name,
 752                                                 tmp->owner, tmp->sym);
 753                 res = find_intersection(left_state, tmp);
 754                 overwrite_sm_state_stack(slist_stack, res);
 755         } END_FOR_EACH_PTR(tmp);
 756         free_slist(&right_slist);
 757 }
 758
 759 /*
 760  * or_slist_stack() is for if we have:  if (foo || bar) { foo->baz;
 761  * It pops the two slists from the top of the stack and merges them
 762  * together in a way that preserves the things they have in common
 763  * but creates a merged state for most of the rest.
 764  * You could have code that had:  if (foo || foo) { foo->baz;
 765  * It's this function which ensures smatch does the right thing.
 766  */
 767 void or_slist_stack(struct state_list_stack **pre_conds,
 768                     struct state_list *cur_slist,
 769                     struct state_list_stack **slist_stack)
 770 {
 771         struct state_list *new;
 772         struct state_list *old;
 773         struct state_list *res = NULL;
 774         struct state_list *tmp_slist;
 775
 776         new = pop_slist(slist_stack);
 777         old = pop_slist(slist_stack);
 778
 779         tmp_slist = pop_slist(pre_conds);
 780         res = clone_slist(tmp_slist);
 781         push_slist(pre_conds, tmp_slist);
 782         overwrite_slist(old, &res);
 783
 784         tmp_slist = clone_slist(cur_slist);
 785         overwrite_slist(new, &tmp_slist);
 786
 787         merge_slist(&res, tmp_slist);
 788
 789         push_slist(slist_stack, res);
 790         free_slist(&tmp_slist);
 791         free_slist(&new);
 792         free_slist(&old);
 793 }
 794
 795 /*
 796  * get_slist_from_named_stack() is only used for gotos.
 797  */
 798 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
 799                                               const char *name)
 800 {
 801         struct named_slist *tmp;
 802
 803         FOR_EACH_PTR(stack, tmp) {
 804                 if (!strcmp(tmp->name, name))
 805                         return &tmp->slist;
 806         } END_FOR_EACH_PTR(tmp);
 807         return NULL;
 808 }
 809
 810 void overwrite_slist(struct state_list *from, struct state_list **to)
 811 {
 812         struct sm_state *tmp;
 813
 814         FOR_EACH_PTR(from, tmp) {
 815                 overwrite_sm_state(to, tmp);
 816         } END_FOR_EACH_PTR(tmp);
 817 }
 818
 819 unsigned int __get_allocations()
 820 {
 821         return sm_state_allocator.allocations;
 822 }