smatch_slist.c

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