smatch_slist.c

   1 /*
   2  * sparse/smatch_slist.c
   3  *
   4  * Copyright (C) 2008,2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include "smatch.h"
  13 #include "smatch_slist.h"
  14
  15 #undef CHECKORDER
  16
  17 ALLOCATOR(smatch_state, "smatch state");
  18 ALLOCATOR(sm_state, "sm state");
  19 ALLOCATOR(named_slist, "named slist");
  20 __DO_ALLOCATOR(char, 0, 1, "state names", sname);
  21
  22 static int sm_state_counter;
  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("[%s] '%s'=%s (", check_name(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(int owner, const char *name,
  96                                      struct symbol *sym,
  97                                      struct smatch_state *state)
  98 {
  99         struct sm_state *tmp;
 100
 101         tmp = alloc_sm_state(owner, NULL, 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->owner, sm->name, sm->sym, sm->state, NULL);
 132                 tmp = alloc_state_no_name(sm->owner, sm->name, 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->owner,tmp->name, 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 int out_of_memory()
 156 {
 157         /*
 158          * I decided to use 50M here based on trial and error.
 159          * It works out OK for the kernel and so it should work
 160          * for most other projects as well.
 161          */
 162         if (sm_state_counter * sizeof(struct sm_state) >= 50000000)
 163                 return 1;
 164         return 0;
 165 }
 166
 167 struct sm_state *alloc_sm_state(int owner, const char *name,
 168                              struct symbol *sym, struct smatch_state *state)
 169 {
 170         struct sm_state *sm_state = __alloc_sm_state(0);
 171
 172         sm_state_counter++;
 173
 174         sm_state->name = alloc_sname(name);
 175         sm_state->owner = owner;
 176         sm_state->sym = sym;
 177         sm_state->state = state;
 178         sm_state->line = get_lineno();
 179         sm_state->merged = 0;
 180         sm_state->implied = 0;
 181         sm_state->my_pool = NULL;
 182         sm_state->left = NULL;
 183         sm_state->right = NULL;
 184         sm_state->nr_children = 1;
 185         sm_state->possible = NULL;
 186         add_ptr_list(&sm_state->possible, sm_state);
 187         return sm_state;
 188 }
 189
 190 static void free_sm_state(struct sm_state *sm)
 191 {
 192         free_slist(&sm->possible);
 193         /*
 194          * fixme.  Free the actual state.
 195          * Right now we leave it until the end of the function
 196          * because we don't want to double free it.
 197          * Use the freelist to not double free things
 198          */
 199 }
 200
 201 static void free_all_sm_states(struct allocation_blob *blob)
 202 {
 203         unsigned int size = sizeof(struct sm_state);
 204         unsigned int offset = 0;
 205
 206         while (offset < blob->offset) {
 207                 free_sm_state((struct sm_state *)(blob->data + offset));
 208                 offset += size;
 209         }
 210 }
 211
 212 /* At the end of every function we free all the sm_states */
 213 void free_every_single_sm_state(void)
 214 {
 215         struct allocator_struct *desc = &sm_state_allocator;
 216         struct allocation_blob *blob = desc->blobs;
 217
 218         desc->blobs = NULL;
 219         desc->allocations = 0;
 220         desc->total_bytes = 0;
 221         desc->useful_bytes = 0;
 222         desc->freelist = NULL;
 223         while (blob) {
 224                 struct allocation_blob *next = blob->next;
 225                 free_all_sm_states(blob);
 226                 blob_free(blob, desc->chunking);
 227                 blob = next;
 228         }
 229         clear_sname_alloc();
 230
 231         sm_state_counter = 0;;
 232 }
 233
 234 struct sm_state *clone_sm(struct sm_state *s)
 235 {
 236         struct sm_state *ret;
 237
 238         ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
 239         ret->merged = s->merged;
 240         ret->implied = s->implied;
 241         /* clone_sm() doesn't copy the my_pools.  Each state needs to have
 242            only one my_pool. */
 243         ret->possible = clone_slist(s->possible);
 244         ret->left = s->left;
 245         ret->right = s->right;
 246         ret->nr_children = s->nr_children;
 247         return ret;
 248 }
 249
 250 int is_merged(struct sm_state *sm)
 251 {
 252         return sm->merged;
 253 }
 254
 255 int is_implied(struct sm_state *sm)
 256 {
 257         return sm->implied;
 258 }
 259
 260 int slist_has_state(struct state_list *slist, struct smatch_state *state)
 261 {
 262         struct sm_state *tmp;
 263
 264         FOR_EACH_PTR(slist, tmp) {
 265                 if (tmp->state == state)
 266                         return 1;
 267         } END_FOR_EACH_PTR(tmp);
 268         return 0;
 269 }
 270
 271 static void check_order(struct state_list *slist)
 272 {
 273 #ifdef CHECKORDER
 274         struct sm_state *sm;
 275         struct sm_state *last = NULL;
 276         int printed = 0;
 277
 278         FOR_EACH_PTR(slist, sm) {
 279                 if (last && cmp_tracker(sm, last) <= 0) {
 280                         printf("Error.  Unsorted slist %d vs %d, %p vs %p, "
 281                                "%s vs %s\n", last->owner, sm->owner,
 282                                last->sym, sm->sym, last->name, sm->name);
 283                         printed = 1;
 284                 }
 285                 last = state;
 286         } END_FOR_EACH_PTR(sm);
 287
 288         if (printed)
 289                 printf("======\n");
 290 #endif
 291 }
 292
 293 struct state_list *clone_slist(struct state_list *from_slist)
 294 {
 295         struct sm_state *sm;
 296         struct state_list *to_slist = NULL;
 297
 298         FOR_EACH_PTR(from_slist, sm) {
 299                 add_ptr_list(&to_slist, sm);
 300         } END_FOR_EACH_PTR(sm);
 301         check_order(to_slist);
 302         return to_slist;
 303 }
 304
 305 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
 306 {
 307         struct state_list *slist;
 308         struct state_list_stack *to_stack = NULL;
 309
 310         FOR_EACH_PTR(from_stack, slist) {
 311                 push_slist(&to_stack, slist);
 312         } END_FOR_EACH_PTR(slist);
 313         return to_stack;
 314 }
 315
 316 struct smatch_state *merge_states(int owner, const char *name,
 317                                   struct symbol *sym,
 318                                   struct smatch_state *state1,
 319                                   struct smatch_state *state2)
 320 {
 321         struct smatch_state *ret;
 322
 323         if (state1 == state2)
 324                 ret = state1;
 325         else if (__has_merge_function(owner))
 326                 ret = __client_merge_function(owner, name, sym, state1, state2);
 327         else if (!state1 || !state2)
 328                 ret = &undefined;
 329         else
 330                 ret = &merged;
 331         return ret;
 332 }
 333
 334 /*
 335  * add_pool() adds a slist to ->pools. If the slist has already been
 336  * added earlier then it doesn't get added a second time.
 337  */
 338 void add_pool(struct state_list_stack **pools, struct state_list *new)
 339 {
 340         struct state_list *tmp;
 341
 342         FOR_EACH_PTR(*pools, tmp) {
 343                 if (tmp < new)
 344                         continue;
 345                 else if (tmp == new) {
 346                         return;
 347                 } else {
 348                         INSERT_CURRENT(new, tmp);
 349                         return;
 350                 }
 351         } END_FOR_EACH_PTR(tmp);
 352         add_ptr_list(pools, new);
 353 }
 354
 355 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
 356 {
 357         struct smatch_state *s;
 358         struct sm_state *result;
 359
 360         if (one == two)
 361                 return one;
 362         s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
 363         result = alloc_state_no_name(one->owner, one->name, one->sym, s);
 364         if (one->line == two->line)
 365                 result->line = one->line;
 366         result->merged = 1;
 367         result->left = one;
 368         result->right = two;
 369         result->nr_children = one->nr_children + two->nr_children;
 370         add_possible(result, one);
 371         add_possible(result, two);
 372
 373         if (option_debug) {
 374                 struct sm_state *tmp;
 375                 int i = 0;
 376
 377                 printf("%d merge name='%s' [%s] %s(L %d) + %s(L %d) => %s (",
 378                         get_lineno(), one->name, check_name(one->owner),
 379                         show_state(one->state), one->line,
 380                         show_state(two->state), two->line,
 381                         show_state(s));
 382
 383                 FOR_EACH_PTR(result->possible, tmp) {
 384                         if (i++) {
 385                                 printf(", ");
 386                         }
 387                         printf("%s", show_state(tmp->state));
 388                 } END_FOR_EACH_PTR(tmp);
 389                 printf(")\n");
 390         }
 391
 392         return result;
 393 }
 394
 395 struct sm_state *get_sm_state_slist(struct state_list *slist, int owner, const char *name,
 396                                 struct symbol *sym)
 397 {
 398         struct sm_state *sm;
 399
 400         if (!name)
 401                 return NULL;
 402
 403         FOR_EACH_PTR(slist, sm) {
 404                 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name))
 405                         return sm;
 406         } END_FOR_EACH_PTR(sm);
 407         return NULL;
 408 }
 409
 410 struct smatch_state *get_state_slist(struct state_list *slist,
 411                                 int owner, const char *name,
 412                                 struct symbol *sym)
 413 {
 414         struct sm_state *sm;
 415
 416         sm = get_sm_state_slist(slist, owner, name, sym);
 417         if (sm)
 418                 return sm->state;
 419         return NULL;
 420 }
 421
 422 void overwrite_sm_state(struct state_list **slist, struct sm_state *new)
 423 {
 424         struct sm_state *tmp;
 425
 426         FOR_EACH_PTR(*slist, tmp) {
 427                 if (cmp_tracker(tmp, new) < 0)
 428                         continue;
 429                 else if (cmp_tracker(tmp, new) == 0) {
 430                         REPLACE_CURRENT_PTR(tmp, new);
 431                         return;
 432                 } else {
 433                         INSERT_CURRENT(new, tmp);
 434                         return;
 435                 }
 436         } END_FOR_EACH_PTR(tmp);
 437         add_ptr_list(slist, new);
 438 }
 439
 440 void overwrite_sm_state_stack(struct state_list_stack **stack,
 441                         struct sm_state *sm)
 442 {
 443         struct state_list *slist;
 444
 445         slist = pop_slist(stack);
 446         overwrite_sm_state(&slist, sm);
 447         push_slist(stack, slist);
 448 }
 449
 450 struct sm_state *set_state_slist(struct state_list **slist, int owner, const char *name,
 451                      struct symbol *sym, struct smatch_state *state)
 452 {
 453         struct sm_state *tmp;
 454         struct sm_state *new = alloc_sm_state(owner, name, sym, state);
 455
 456         FOR_EACH_PTR(*slist, tmp) {
 457                 if (cmp_tracker(tmp, new) < 0)
 458                         continue;
 459                 else if (cmp_tracker(tmp, new) == 0) {
 460                         REPLACE_CURRENT_PTR(tmp, new);
 461                         return new;
 462                 } else {
 463                         INSERT_CURRENT(new, tmp);
 464                         return new;
 465                 }
 466         } END_FOR_EACH_PTR(tmp);
 467         add_ptr_list(slist, new);
 468         return new;
 469 }
 470
 471 void delete_state_slist(struct state_list **slist, int owner, const char *name,
 472                         struct symbol *sym)
 473 {
 474         struct sm_state *sm;
 475
 476         FOR_EACH_PTR(*slist, sm) {
 477                 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name)){
 478                         DELETE_CURRENT_PTR(sm);
 479                         return;
 480                 }
 481         } END_FOR_EACH_PTR(sm);
 482 }
 483
 484 void delete_state_stack(struct state_list_stack **stack, int owner, const char *name,
 485                         struct symbol *sym)
 486 {
 487         struct state_list *slist;
 488
 489         slist = pop_slist(stack);
 490         delete_state_slist(&slist, owner, name, sym);
 491         push_slist(stack, slist);
 492 }
 493
 494 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 495 {
 496         add_ptr_list(list_stack, slist);
 497 }
 498
 499 struct state_list *pop_slist(struct state_list_stack **list_stack)
 500 {
 501         struct state_list *slist;
 502
 503         slist = last_ptr_list((struct ptr_list *)*list_stack);
 504         delete_ptr_list_last((struct ptr_list **)list_stack);
 505         return slist;
 506 }
 507
 508 void free_slist(struct state_list **slist)
 509 {
 510         __free_ptr_list((struct ptr_list **)slist);
 511 }
 512
 513 void free_stack(struct state_list_stack **stack)
 514 {
 515         __free_ptr_list((struct ptr_list **)stack);
 516 }
 517
 518 void free_stack_and_slists(struct state_list_stack **slist_stack)
 519 {
 520         struct state_list *slist;
 521
 522         FOR_EACH_PTR(*slist_stack, slist) {
 523                 free_slist(&slist);
 524         } END_FOR_EACH_PTR(slist);
 525         free_stack(slist_stack);
 526 }
 527
 528 /*
 529  * set_state_stack() sets the state for the top slist on the stack.
 530  */
 531 struct sm_state *set_state_stack(struct state_list_stack **stack, int owner, const char *name,
 532                                 struct symbol *sym, struct smatch_state *state)
 533 {
 534         struct state_list *slist;
 535         struct sm_state *sm;
 536
 537         slist = pop_slist(stack);
 538         sm = set_state_slist(&slist, owner, name, sym, state);
 539         push_slist(stack, slist);
 540
 541         return sm;
 542 }
 543
 544 /*
 545  * get_sm_state_stack() gets the state for the top slist on the stack.
 546  */
 547 struct sm_state *get_sm_state_stack(struct state_list_stack *stack,
 548                                 int owner, const char *name,
 549                                 struct symbol *sym)
 550 {
 551         struct state_list *slist;
 552         struct sm_state *ret;
 553
 554         slist = pop_slist(&stack);
 555         ret = get_sm_state_slist(slist, owner, name, sym);
 556         push_slist(&stack, slist);
 557         return ret;
 558 }
 559
 560
 561 struct smatch_state *get_state_stack(struct state_list_stack *stack,
 562                                 int owner, const char *name,
 563                                 struct symbol *sym)
 564 {
 565         struct sm_state *sm;
 566
 567         sm = get_sm_state_stack(stack, owner, name, sym);
 568         if (sm)
 569                 return sm->state;
 570         return NULL;
 571 }
 572
 573 static void match_states(struct state_list **one, struct state_list **two)
 574 {
 575         struct sm_state *one_sm;
 576         struct sm_state *two_sm;
 577         struct sm_state *tmp;
 578         struct smatch_state *tmp_state;
 579         struct state_list *add_to_one = NULL;
 580         struct state_list *add_to_two = NULL;
 581
 582         PREPARE_PTR_LIST(*one, one_sm);
 583         PREPARE_PTR_LIST(*two, two_sm);
 584         for (;;) {
 585                 if (!one_sm && !two_sm)
 586                         break;
 587                 if (cmp_tracker(one_sm, two_sm) < 0) {
 588                         tmp_state = __client_unmatched_state_function(one_sm);
 589                         tmp = alloc_state_no_name(one_sm->owner, one_sm->name,
 590                                                   one_sm->sym, tmp_state);
 591                         add_ptr_list(&add_to_two, tmp);
 592                         NEXT_PTR_LIST(one_sm);
 593                 } else if (cmp_tracker(one_sm, two_sm) == 0) {
 594                         NEXT_PTR_LIST(one_sm);
 595                         NEXT_PTR_LIST(two_sm);
 596                 } else {
 597                         tmp_state = __client_unmatched_state_function(two_sm);
 598                         tmp = alloc_state_no_name(two_sm->owner, two_sm->name,
 599                                                   two_sm->sym, tmp_state);
 600                         add_ptr_list(&add_to_one, tmp);
 601                         NEXT_PTR_LIST(two_sm);
 602                 }
 603         }
 604         FINISH_PTR_LIST(two_sm);
 605         FINISH_PTR_LIST(one_sm);
 606
 607         overwrite_slist(add_to_one, one);
 608         overwrite_slist(add_to_two, two);
 609 }
 610
 611 static void clone_pool_havers(struct state_list *slist)
 612 {
 613         struct sm_state *sm;
 614         struct sm_state *new;
 615
 616         FOR_EACH_PTR(slist, sm) {
 617                 if (sm->my_pool) {
 618                         new = clone_sm(sm);
 619                         REPLACE_CURRENT_PTR(sm, new);
 620                 }
 621         } END_FOR_EACH_PTR(sm);
 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 *one_sm, *two_sm, *tmp;
 631         struct state_list *results = NULL;
 632         struct state_list *implied_one = NULL;
 633         struct state_list *implied_two = NULL;
 634
 635         if (out_of_memory())
 636                 return;
 637
 638         check_order(*to);
 639         check_order(slist);
 640
 641         /* merging a null and nonnull path gives you only the nonnull path */
 642         if (!slist) {
 643                 return;
 644         }
 645         if (!*to) {
 646                 *to = clone_slist(slist);
 647                 return;
 648         }
 649
 650         implied_one = clone_slist(*to);
 651         implied_two = clone_slist(slist);
 652
 653         match_states(&implied_one, &implied_two);
 654
 655         clone_pool_havers(implied_one);
 656         clone_pool_havers(implied_two);
 657
 658         PREPARE_PTR_LIST(implied_one, one_sm);
 659         PREPARE_PTR_LIST(implied_two, two_sm);
 660         for (;;) {
 661                 if (!one_sm && !two_sm)
 662                         break;
 663                 if (cmp_tracker(one_sm, two_sm) < 0) {
 664                         sm_msg("error:  Internal smatch error.");
 665                         NEXT_PTR_LIST(one_sm);
 666                 } else if (cmp_tracker(one_sm, two_sm) == 0) {
 667                         if (one_sm != two_sm) {
 668                                 one_sm->my_pool = implied_one;
 669                                 two_sm->my_pool = implied_two;
 670                         }
 671
 672                         tmp = merge_sm_states(one_sm, two_sm);
 673                         add_ptr_list(&results, tmp);
 674                         NEXT_PTR_LIST(one_sm);
 675                         NEXT_PTR_LIST(two_sm);
 676                 } else {
 677                         sm_msg("error:  Internal smatch error.");
 678                         NEXT_PTR_LIST(two_sm);
 679                 }
 680         }
 681         FINISH_PTR_LIST(two_sm);
 682         FINISH_PTR_LIST(one_sm);
 683
 684         free_slist(to);
 685         *to = results;
 686 }
 687
 688 /*
 689  * filter_slist() removes any sm states "slist" holds in common with "filter"
 690  */
 691 void filter_slist(struct state_list **slist, struct state_list *filter)
 692 {
 693         struct sm_state *one_sm, *two_sm;
 694         struct state_list *results = NULL;
 695
 696         PREPARE_PTR_LIST(*slist, one_sm);
 697         PREPARE_PTR_LIST(filter, two_sm);
 698         for (;;) {
 699                 if (!one_sm && !two_sm)
 700                         break;
 701                 if (cmp_tracker(one_sm, two_sm) < 0) {
 702                         add_ptr_list(&results, one_sm);
 703                         NEXT_PTR_LIST(one_sm);
 704                 } else if (cmp_tracker(one_sm, two_sm) == 0) {
 705                         if (one_sm != two_sm)
 706                                 add_ptr_list(&results, one_sm);
 707                         NEXT_PTR_LIST(one_sm);
 708                         NEXT_PTR_LIST(two_sm);
 709                 } else {
 710                         NEXT_PTR_LIST(two_sm);
 711                 }
 712         }
 713         FINISH_PTR_LIST(two_sm);
 714         FINISH_PTR_LIST(one_sm);
 715
 716         free_slist(slist);
 717         *slist = results;
 718 }
 719
 720 /*
 721  * and_slist_stack() pops the top two slists, overwriting the one with
 722  * the other and pushing it back on the stack.
 723  */
 724 void and_slist_stack(struct state_list_stack **slist_stack)
 725 {
 726         struct sm_state *tmp;
 727         struct state_list *right_slist = pop_slist(slist_stack);
 728
 729         FOR_EACH_PTR(right_slist, tmp) {
 730                 overwrite_sm_state_stack(slist_stack, tmp);
 731         } END_FOR_EACH_PTR(tmp);
 732         free_slist(&right_slist);
 733 }
 734
 735 /*
 736  * or_slist_stack() is for if we have:  if (foo || bar) { foo->baz;
 737  * It pops the two slists from the top of the stack and merges them
 738  * together in a way that preserves the things they have in common
 739  * but creates a merged state for most of the rest.
 740  * You could have code that had:  if (foo || foo) { foo->baz;
 741  * It's this function which ensures smatch does the right thing.
 742  */
 743 void or_slist_stack(struct state_list_stack **pre_conds,
 744                     struct state_list *cur_slist,
 745                     struct state_list_stack **slist_stack)
 746 {
 747         struct state_list *new;
 748         struct state_list *old;
 749         struct state_list *pre_slist;
 750         struct state_list *res;
 751         struct state_list *tmp_slist;
 752
 753         new = pop_slist(slist_stack);
 754         old = pop_slist(slist_stack);
 755
 756         pre_slist = pop_slist(pre_conds);
 757         push_slist(pre_conds, clone_slist(pre_slist));
 758
 759         res = clone_slist(pre_slist);
 760         overwrite_slist(old, &res);
 761
 762         tmp_slist = clone_slist(cur_slist);
 763         overwrite_slist(new, &tmp_slist);
 764
 765         merge_slist(&res, tmp_slist);
 766         filter_slist(&res, pre_slist);
 767
 768         push_slist(slist_stack, res);
 769         free_slist(&tmp_slist);
 770         free_slist(&pre_slist);
 771         free_slist(&new);
 772         free_slist(&old);
 773 }
 774
 775 /*
 776  * get_slist_from_named_stack() is only used for gotos.
 777  */
 778 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
 779                                               const char *name)
 780 {
 781         struct named_slist *tmp;
 782
 783         FOR_EACH_PTR(stack, tmp) {
 784                 if (!strcmp(tmp->name, name))
 785                         return &tmp->slist;
 786         } END_FOR_EACH_PTR(tmp);
 787         return NULL;
 788 }
 789
 790 void overwrite_slist(struct state_list *from, struct state_list **to)
 791 {
 792         struct sm_state *tmp;
 793
 794         FOR_EACH_PTR(from, tmp) {
 795                 overwrite_sm_state(to, tmp);
 796         } END_FOR_EACH_PTR(tmp);
 797 }