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