smatch_slist.c

   1 /*
   2  * Copyright (C) 2008,2009 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include <stdlib.h>
  19 #include <stdio.h>
  20 #include "smatch.h"
  21 #include "smatch_slist.h"
  22
  23 #undef CHECKORDER
  24
  25 ALLOCATOR(smatch_state, "smatch state");
  26 ALLOCATOR(sm_state, "sm state");
  27 ALLOCATOR(named_stree, "named slist");
  28 __DO_ALLOCATOR(char, 1, 4, "state names", sname);
  29
  30 static int sm_state_counter;
  31
  32 static struct stree_stack *all_pools;
  33
  34 char *show_sm(struct sm_state *sm)
  35 {
  36         static char buf[256];
  37         struct sm_state *tmp;
  38         int pos;
  39         int i;
  40
  41         pos = snprintf(buf, sizeof(buf), "[%s] '%s' = %s (",
  42                        check_name(sm->owner), sm->name, show_state(sm->state));
  43         if (pos > sizeof(buf))
  44                 goto truncate;
  45
  46         i = 0;
  47         FOR_EACH_PTR(sm->possible, tmp) {
  48                 if (i++)
  49                         pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
  50                 if (pos > sizeof(buf))
  51                         goto truncate;
  52                 pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
  53                                show_state(tmp->state));
  54                 if (pos > sizeof(buf))
  55                         goto truncate;
  56         } END_FOR_EACH_PTR(tmp);
  57         snprintf(buf + pos, sizeof(buf) - pos, ")");
  58
  59         return buf;
  60
  61 truncate:
  62         for (i = 0; i < 3; i++)
  63                 buf[sizeof(buf) - 2 - i] = '.';
  64         return buf;
  65 }
  66
  67 void __print_stree(struct stree *stree)
  68 {
  69         struct sm_state *sm;
  70
  71         printf("dumping stree at %d\n", get_lineno());
  72         FOR_EACH_SM(stree, sm) {
  73                 printf("%s\n", show_sm(sm));
  74         } END_FOR_EACH_SM(sm);
  75         printf("---\n");
  76 }
  77
  78 /* NULL states go at the end to simplify merge_slist */
  79 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
  80 {
  81         int ret;
  82
  83         if (a == b)
  84                 return 0;
  85         if (!b)
  86                 return -1;
  87         if (!a)
  88                 return 1;
  89
  90         if (a->owner > b->owner)
  91                 return -1;
  92         if (a->owner < b->owner)
  93                 return 1;
  94
  95         ret = strcmp(a->name, b->name);
  96         if (ret)
  97                 return ret;
  98
  99         if (!b->sym && a->sym)
 100                 return -1;
 101         if (!a->sym && b->sym)
 102                 return 1;
 103         if (a->sym > b->sym)
 104                 return -1;
 105         if (a->sym < b->sym)
 106                 return 1;
 107
 108         return 0;
 109 }
 110
 111 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b, int preserve)
 112 {
 113         int ret;
 114
 115         ret = cmp_tracker(a, b);
 116         if (ret)
 117                 return ret;
 118
 119         /* todo:  add hook for smatch_extra.c */
 120         if (a->state > b->state)
 121                 return -1;
 122         if (a->state < b->state)
 123                 return 1;
 124         /* This is obviously a massive disgusting hack but we need to preserve
 125          * the unmerged states for smatch extra because we use them in
 126          * smatch_db.c.  Meanwhile if we preserve all the other unmerged states
 127          * then it uses a lot of memory and we don't use it.  Hence this hack.
 128          *
 129          * Also sometimes even just preserving every possible SMATCH_EXTRA state
 130          * takes too much resources so we have to cap that.  Capping is probably
 131          * not often a problem in real life.
 132          */
 133         if (a->owner == SMATCH_EXTRA && preserve) {
 134                 if (a == b)
 135                         return 0;
 136                 if (a->merged == 1 && b->merged == 0)
 137                         return -1;
 138                 if (a->merged == 0)
 139                         return 1;
 140         }
 141
 142         return 0;
 143 }
 144
 145 static struct sm_state *alloc_sm_state(int owner, const char *name,
 146                              struct symbol *sym, struct smatch_state *state)
 147 {
 148         struct sm_state *sm_state = __alloc_sm_state(0);
 149
 150         sm_state_counter++;
 151
 152         sm_state->name = alloc_sname(name);
 153         sm_state->owner = owner;
 154         sm_state->sym = sym;
 155         sm_state->state = state;
 156         sm_state->line = get_lineno();
 157         sm_state->merged = 0;
 158         sm_state->implied = 0;
 159         sm_state->pool = NULL;
 160         sm_state->left = NULL;
 161         sm_state->right = NULL;
 162         sm_state->nr_children = 1;
 163         sm_state->possible = NULL;
 164         add_ptr_list(&sm_state->possible, sm_state);
 165         return sm_state;
 166 }
 167
 168 static struct sm_state *alloc_state_no_name(int owner, const char *name,
 169                                      struct symbol *sym,
 170                                      struct smatch_state *state)
 171 {
 172         struct sm_state *tmp;
 173
 174         tmp = alloc_sm_state(owner, NULL, sym, state);
 175         tmp->name = name;
 176         return tmp;
 177 }
 178
 179 int too_many_possible(struct sm_state *sm)
 180 {
 181         if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
 182                 return 1;
 183         return 0;
 184 }
 185
 186 void add_possible_sm(struct sm_state *to, struct sm_state *new)
 187 {
 188         struct sm_state *tmp;
 189         int preserve = 1;
 190
 191         if (too_many_possible(to))
 192                 preserve = 0;
 193
 194         FOR_EACH_PTR(to->possible, tmp) {
 195                 if (cmp_sm_states(tmp, new, preserve) < 0)
 196                         continue;
 197                 else if (cmp_sm_states(tmp, new, preserve) == 0) {
 198                         return;
 199                 } else {
 200                         INSERT_CURRENT(new, tmp);
 201                         return;
 202                 }
 203         } END_FOR_EACH_PTR(tmp);
 204         add_ptr_list(&to->possible, new);
 205 }
 206
 207 static void copy_possibles(struct sm_state *to, struct sm_state *from)
 208 {
 209         struct sm_state *tmp;
 210
 211         FOR_EACH_PTR(from->possible, tmp) {
 212                 add_possible_sm(to, tmp);
 213         } END_FOR_EACH_PTR(tmp);
 214 }
 215
 216 char *alloc_sname(const char *str)
 217 {
 218         char *tmp;
 219
 220         if (!str)
 221                 return NULL;
 222         tmp = __alloc_sname(strlen(str) + 1);
 223         strcpy(tmp, str);
 224         return tmp;
 225 }
 226
 227 int out_of_memory()
 228 {
 229         /*
 230          * I decided to use 50M here based on trial and error.
 231          * It works out OK for the kernel and so it should work
 232          * for most other projects as well.
 233          */
 234         if (sm_state_counter * sizeof(struct sm_state) >= 50000000)
 235                 return 1;
 236         return 0;
 237 }
 238
 239 int low_on_memory(void)
 240 {
 241         if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
 242                 return 1;
 243         return 0;
 244 }
 245
 246 static void free_sm_state(struct sm_state *sm)
 247 {
 248         free_slist(&sm->possible);
 249         /*
 250          * fixme.  Free the actual state.
 251          * Right now we leave it until the end of the function
 252          * because we don't want to double free it.
 253          * Use the freelist to not double free things
 254          */
 255 }
 256
 257 static void free_all_sm_states(struct allocation_blob *blob)
 258 {
 259         unsigned int size = sizeof(struct sm_state);
 260         unsigned int offset = 0;
 261
 262         while (offset < blob->offset) {
 263                 free_sm_state((struct sm_state *)(blob->data + offset));
 264                 offset += size;
 265         }
 266 }
 267
 268 /* At the end of every function we free all the sm_states */
 269 void free_every_single_sm_state(void)
 270 {
 271         struct allocator_struct *desc = &sm_state_allocator;
 272         struct allocation_blob *blob = desc->blobs;
 273
 274         desc->blobs = NULL;
 275         desc->allocations = 0;
 276         desc->total_bytes = 0;
 277         desc->useful_bytes = 0;
 278         desc->freelist = NULL;
 279         while (blob) {
 280                 struct allocation_blob *next = blob->next;
 281                 free_all_sm_states(blob);
 282                 blob_free(blob, desc->chunking);
 283                 blob = next;
 284         }
 285         clear_sname_alloc();
 286         clear_smatch_state_alloc();
 287
 288         free_stack_and_strees(&all_pools);
 289         sm_state_counter = 0;
 290 }
 291
 292 struct sm_state *clone_sm(struct sm_state *s)
 293 {
 294         struct sm_state *ret;
 295
 296         ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
 297         ret->merged = s->merged;
 298         ret->implied = s->implied;
 299         ret->line = s->line;
 300         /* clone_sm() doesn't copy the pools.  Each state needs to have
 301            only one pool. */
 302         ret->possible = clone_slist(s->possible);
 303         ret->left = s->left;
 304         ret->right = s->right;
 305         ret->nr_children = s->nr_children;
 306         return ret;
 307 }
 308
 309 int is_merged(struct sm_state *sm)
 310 {
 311         return sm->merged;
 312 }
 313
 314 int is_implied(struct sm_state *sm)
 315 {
 316         return sm->implied;
 317 }
 318
 319 int slist_has_state(struct state_list *slist, struct smatch_state *state)
 320 {
 321         struct sm_state *tmp;
 322
 323         FOR_EACH_PTR(slist, tmp) {
 324                 if (tmp->state == state)
 325                         return 1;
 326         } END_FOR_EACH_PTR(tmp);
 327         return 0;
 328 }
 329
 330 struct state_list *clone_slist(struct state_list *from_slist)
 331 {
 332         struct sm_state *sm;
 333         struct state_list *to_slist = NULL;
 334
 335         FOR_EACH_PTR(from_slist, sm) {
 336                 add_ptr_list(&to_slist, sm);
 337         } END_FOR_EACH_PTR(sm);
 338         return to_slist;
 339 }
 340
 341 struct smatch_state *merge_states(int owner, const char *name,
 342                                   struct symbol *sym,
 343                                   struct smatch_state *state1,
 344                                   struct smatch_state *state2)
 345 {
 346         struct smatch_state *ret;
 347
 348         if (state1 == state2)
 349                 ret = state1;
 350         else if (__has_merge_function(owner))
 351                 ret = __client_merge_function(owner, state1, state2);
 352         else if (!state1 || !state2)
 353                 ret = &undefined;
 354         else
 355                 ret = &merged;
 356         return ret;
 357 }
 358
 359 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
 360 {
 361         struct smatch_state *s;
 362         struct sm_state *result;
 363
 364         if (one == two)
 365                 return one;
 366         s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
 367         result = alloc_state_no_name(one->owner, one->name, one->sym, s);
 368         result->merged = 1;
 369         result->left = one;
 370         result->right = two;
 371         result->nr_children = one->nr_children + two->nr_children;
 372         copy_possibles(result, one);
 373         copy_possibles(result, two);
 374
 375         if (option_debug ||
 376             strcmp(check_name(one->owner), option_debug_check) == 0) {
 377                 struct sm_state *tmp;
 378                 int i = 0;
 379
 380                 printf("%d merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
 381                         get_lineno(), check_name(one->owner), one->name,
 382                         show_state(one->state), one->line,
 383                         show_state(two->state), two->line,
 384                         show_state(s));
 385
 386                 FOR_EACH_PTR(result->possible, tmp) {
 387                         if (i++)
 388                                 printf(", ");
 389                         printf("%s", show_state(tmp->state));
 390                 } END_FOR_EACH_PTR(tmp);
 391                 printf(")\n");
 392         }
 393
 394         return result;
 395 }
 396
 397 struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
 398                                 struct symbol *sym)
 399 {
 400         struct tracker tracker = {
 401                 .owner = owner,
 402                 .name = (char *)name,
 403                 .sym = sym,
 404         };
 405
 406         if (!name)
 407                 return NULL;
 408
 409
 410         return avl_lookup(stree, (struct sm_state *)&tracker);
 411 }
 412
 413 struct smatch_state *get_state_stree(struct stree *stree,
 414                                 int owner, const char *name,
 415                                 struct symbol *sym)
 416 {
 417         struct sm_state *sm;
 418
 419         sm = get_sm_state_stree(stree, owner, name, sym);
 420         if (sm)
 421                 return sm->state;
 422         return NULL;
 423 }
 424
 425 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
 426 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
 427 {
 428         avl_insert(stree, new);
 429 }
 430
 431 void overwrite_sm_state_stree_stack(struct stree_stack **stack,
 432                         struct sm_state *sm)
 433 {
 434         struct stree *stree;
 435
 436         stree = pop_stree(stack);
 437         overwrite_sm_state_stree(&stree, sm);
 438         push_stree(stack, stree);
 439 }
 440
 441 struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
 442                      struct symbol *sym, struct smatch_state *state)
 443 {
 444         struct sm_state *new = alloc_sm_state(owner, name, sym, state);
 445
 446         avl_insert(stree, new);
 447         return new;
 448 }
 449
 450 void delete_state_stree(struct stree **stree, int owner, const char *name,
 451                         struct symbol *sym)
 452 {
 453         struct tracker tracker = {
 454                 .owner = owner,
 455                 .name = (char *)name,
 456                 .sym = sym,
 457         };
 458
 459         avl_remove(stree, (struct sm_state *)&tracker);
 460 }
 461
 462 void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
 463                         struct symbol *sym)
 464 {
 465         struct stree *stree;
 466
 467         stree = pop_stree(stack);
 468         delete_state_stree(&stree, owner, name, sym);
 469         push_stree(stack, stree);
 470 }
 471
 472 void push_stree(struct stree_stack **stack, struct stree *stree)
 473 {
 474         add_ptr_list(stack, stree);
 475 }
 476
 477 struct stree *pop_stree(struct stree_stack **stack)
 478 {
 479         struct stree *stree;
 480
 481         stree = last_ptr_list((struct ptr_list *)*stack);
 482         delete_ptr_list_last((struct ptr_list **)stack);
 483         return stree;
 484 }
 485
 486 void free_slist(struct state_list **slist)
 487 {
 488         __free_ptr_list((struct ptr_list **)slist);
 489 }
 490
 491 void free_stree_stack(struct stree_stack **stack)
 492 {
 493         __free_ptr_list((struct ptr_list **)stack);
 494 }
 495
 496 void free_stack_and_strees(struct stree_stack **stree_stack)
 497 {
 498         struct stree *stree;
 499
 500         FOR_EACH_PTR(*stree_stack, stree) {
 501                 free_stree(&stree);
 502         } END_FOR_EACH_PTR(stree);
 503         free_stree_stack(stree_stack);
 504 }
 505
 506 struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
 507                                 struct symbol *sym, struct smatch_state *state)
 508 {
 509         struct stree *stree;
 510         struct sm_state *sm;
 511
 512         stree = pop_stree(stack);
 513         sm = set_state_stree(&stree, owner, name, sym, state);
 514         push_stree(stack, stree);
 515
 516         return sm;
 517 }
 518
 519 /*
 520  * get_sm_state_stack() gets the state for the top slist on the stack.
 521  */
 522 struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
 523                                 int owner, const char *name,
 524                                 struct symbol *sym)
 525 {
 526         struct stree *stree;
 527         struct sm_state *ret;
 528
 529         stree = pop_stree(&stack);
 530         ret = get_sm_state_stree(stree, owner, name, sym);
 531         push_stree(&stack, stree);
 532         return ret;
 533 }
 534
 535 struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
 536                                 int owner, const char *name,
 537                                 struct symbol *sym)
 538 {
 539         struct sm_state *sm;
 540
 541         sm = get_sm_state_stree_stack(stack, owner, name, sym);
 542         if (sm)
 543                 return sm->state;
 544         return NULL;
 545 }
 546
 547 static void match_states_stree(struct stree **one, struct stree **two)
 548 {
 549         struct smatch_state *tmp_state;
 550         struct sm_state *sm;
 551         struct state_list *add_to_one = NULL;
 552         struct state_list *add_to_two = NULL;
 553         AvlIter one_iter;
 554         AvlIter two_iter;
 555
 556         avl_iter_begin(&one_iter, *one, FORWARD);
 557         avl_iter_begin(&two_iter, *two, FORWARD);
 558
 559         for (;;) {
 560                 if (!one_iter.sm && !two_iter.sm)
 561                         break;
 562                 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
 563                         __set_fake_cur_stree_fast(*two);
 564                         tmp_state = __client_unmatched_state_function(one_iter.sm);
 565                         __pop_fake_cur_stree_fast();
 566                         sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
 567                                                   one_iter.sm->sym, tmp_state);
 568                         add_ptr_list(&add_to_two, sm);
 569                         avl_iter_next(&one_iter);
 570                 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
 571                         avl_iter_next(&one_iter);
 572                         avl_iter_next(&two_iter);
 573                 } else {
 574                         __set_fake_cur_stree_fast(*one);
 575                         tmp_state = __client_unmatched_state_function(two_iter.sm);
 576                         __pop_fake_cur_stree_fast();
 577                         sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
 578                                                   two_iter.sm->sym, tmp_state);
 579                         add_ptr_list(&add_to_one, sm);
 580                         avl_iter_next(&two_iter);
 581                 }
 582         }
 583
 584         FOR_EACH_PTR(add_to_one, sm) {
 585                 avl_insert(one, sm);
 586         } END_FOR_EACH_PTR(sm);
 587
 588         FOR_EACH_PTR(add_to_two, sm) {
 589                 avl_insert(two, sm);
 590         } END_FOR_EACH_PTR(sm);
 591
 592         free_slist(&add_to_one);
 593         free_slist(&add_to_two);
 594 }
 595
 596 static void clone_pool_havers_stree(struct stree **stree)
 597 {
 598         struct sm_state *sm, *tmp;
 599         struct state_list *slist = NULL;
 600
 601         FOR_EACH_SM(*stree, sm) {
 602                 if (sm->pool) {
 603                         tmp = clone_sm(sm);
 604                         add_ptr_list(&slist, tmp);
 605                 }
 606         } END_FOR_EACH_SM(sm);
 607
 608         FOR_EACH_PTR(slist, sm) {
 609                 avl_insert(stree, sm);
 610         } END_FOR_EACH_PTR(sm);
 611
 612         free_slist(&slist);
 613 }
 614
 615 int __stree_id;
 616
 617 /*
 618  * merge_slist() is called whenever paths merge, such as after
 619  * an if statement.  It takes the two slists and creates one.
 620  */
 621 static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
 622 {
 623         struct stree *results = NULL;
 624         struct stree *implied_one = NULL;
 625         struct stree *implied_two = NULL;
 626         AvlIter one_iter;
 627         AvlIter two_iter;
 628         struct sm_state *tmp_sm;
 629
 630         if (out_of_memory())
 631                 return;
 632
 633         /* merging a null and nonnull path gives you only the nonnull path */
 634         if (!stree)
 635                 return;
 636         if (*to == stree)
 637                 return;
 638
 639         if (!*to) {
 640                 *to = clone_stree(stree);
 641                 return;
 642         }
 643
 644         implied_one = clone_stree(*to);
 645         implied_two = clone_stree(stree);
 646
 647         match_states_stree(&implied_one, &implied_two);
 648
 649         if (add_pool) {
 650                 clone_pool_havers_stree(&implied_one);
 651                 clone_pool_havers_stree(&implied_two);
 652
 653                 set_stree_id(&implied_one, ++__stree_id);
 654                 set_stree_id(&implied_two, ++__stree_id);
 655         }
 656
 657         push_stree(&all_pools, implied_one);
 658         push_stree(&all_pools, implied_two);
 659
 660         avl_iter_begin(&one_iter, implied_one, FORWARD);
 661         avl_iter_begin(&two_iter, implied_two, FORWARD);
 662
 663         for (;;) {
 664                 if (!one_iter.sm && !two_iter.sm)
 665                         break;
 666                 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
 667                         sm_msg("error:  Internal smatch error.");
 668                         avl_iter_next(&one_iter);
 669                 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
 670                         if (add_pool && one_iter.sm != two_iter.sm) {
 671                                 one_iter.sm->pool = implied_one;
 672                                 two_iter.sm->pool = implied_two;
 673                         }
 674                         tmp_sm = merge_sm_states(one_iter.sm, two_iter.sm);
 675                         avl_insert(&results, tmp_sm);
 676                         avl_iter_next(&one_iter);
 677                         avl_iter_next(&two_iter);
 678                 } else {
 679                         sm_msg("error:  Internal smatch error.");
 680                         avl_iter_next(&two_iter);
 681                 }
 682         }
 683
 684         free_stree(to);
 685         *to = results;
 686 }
 687
 688 void merge_stree(struct stree **to, struct stree *stree)
 689 {
 690         __merge_stree(to, stree, 1);
 691 }
 692
 693 void merge_stree_no_pools(struct stree **to, struct stree *stree)
 694 {
 695         __merge_stree(to, stree, 0);
 696 }
 697
 698 /*
 699  * This is unfortunately a bit subtle...  The problem is that if a
 700  * state is set on one fake stree but not the other then we should
 701  * look up the the original state and use that as the unset state.
 702  * Fortunately, after you pop your fake stree then the cur_slist should
 703  * reflect the original state.
 704  */
 705 void merge_fake_stree(struct stree **to, struct stree *stree)
 706 {
 707         struct stree *one = *to;
 708         struct stree *two = stree;
 709         struct sm_state *sm;
 710         struct state_list *add_to_one = NULL;
 711         struct state_list *add_to_two = NULL;
 712         AvlIter one_iter;
 713         AvlIter two_iter;
 714
 715         if (!stree)
 716                 return;
 717         if (*to == stree)
 718                 return;
 719         if (!*to) {
 720                 *to = clone_stree(stree);
 721                 return;
 722         }
 723
 724         avl_iter_begin(&one_iter, one, FORWARD);
 725         avl_iter_begin(&two_iter, two, FORWARD);
 726
 727         for (;;) {
 728                 if (!one_iter.sm && !two_iter.sm)
 729                         break;
 730                 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
 731                         sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name,
 732                                           one_iter.sm->sym);
 733                         if (sm)
 734                                 add_ptr_list(&add_to_two, sm);
 735                         avl_iter_next(&one_iter);
 736                 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
 737                         avl_iter_next(&one_iter);
 738                         avl_iter_next(&two_iter);
 739                 } else {
 740                         sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name,
 741                                           two_iter.sm->sym);
 742                         if (sm)
 743                                 add_ptr_list(&add_to_one, sm);
 744                         avl_iter_next(&two_iter);
 745                 }
 746         }
 747
 748         FOR_EACH_PTR(add_to_one, sm) {
 749                 avl_insert(&one, sm);
 750         } END_FOR_EACH_PTR(sm);
 751
 752         FOR_EACH_PTR(add_to_two, sm) {
 753                 avl_insert(&two, sm);
 754         } END_FOR_EACH_PTR(sm);
 755
 756         free_slist(&add_to_one);
 757         free_slist(&add_to_two);
 758
 759         __merge_stree(&one, two, 1);
 760
 761         *to = one;
 762 }
 763
 764 /*
 765  * filter_slist() removes any sm states "slist" holds in common with "filter"
 766  */
 767 void filter_stree(struct stree **stree, struct stree *filter)
 768 {
 769         struct stree *results = NULL;
 770         AvlIter one_iter;
 771         AvlIter two_iter;
 772
 773         avl_iter_begin(&one_iter, *stree, FORWARD);
 774         avl_iter_begin(&two_iter, filter, FORWARD);
 775
 776         /* FIXME: This should probably be re-written with trees in mind */
 777
 778         for (;;) {
 779                 if (!one_iter.sm && !two_iter.sm)
 780                         break;
 781                 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
 782                         avl_insert(&results, one_iter.sm);
 783                         avl_iter_next(&one_iter);
 784                 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
 785                         if (one_iter.sm != two_iter.sm)
 786                                 avl_insert(&results, one_iter.sm);
 787                         avl_iter_next(&one_iter);
 788                         avl_iter_next(&two_iter);
 789                 } else {
 790                         avl_iter_next(&two_iter);
 791                 }
 792         }
 793
 794         free_stree(stree);
 795         *stree = results;
 796 }
 797
 798
 799 /*
 800  * and_slist_stack() pops the top two slists, overwriting the one with
 801  * the other and pushing it back on the stack.
 802  */
 803 void and_stree_stack(struct stree_stack **stack)
 804 {
 805         struct sm_state *tmp;
 806         struct stree *right_stree = pop_stree(stack);
 807
 808         FOR_EACH_SM(right_stree, tmp) {
 809                 overwrite_sm_state_stree_stack(stack, tmp);
 810         } END_FOR_EACH_SM(tmp);
 811         free_stree(&right_stree);
 812 }
 813
 814 /*
 815  * or_slist_stack() is for if we have:  if (foo || bar) { foo->baz;
 816  * It pops the two slists from the top of the stack and merges them
 817  * together in a way that preserves the things they have in common
 818  * but creates a merged state for most of the rest.
 819  * You could have code that had:  if (foo || foo) { foo->baz;
 820  * It's this function which ensures smatch does the right thing.
 821  */
 822 void or_stree_stack(struct stree_stack **pre_conds,
 823                     struct stree *cur_stree,
 824                     struct stree_stack **stack)
 825 {
 826         struct stree *new;
 827         struct stree *old;
 828         struct stree *pre_stree;
 829         struct stree *res;
 830         struct stree *tmp_stree;
 831
 832         new = pop_stree(stack);
 833         old = pop_stree(stack);
 834
 835         pre_stree = pop_stree(pre_conds);
 836         push_stree(pre_conds, clone_stree(pre_stree));
 837
 838         res = clone_stree(pre_stree);
 839         overwrite_stree(old, &res);
 840
 841         tmp_stree = clone_stree(cur_stree);
 842         overwrite_stree(new, &tmp_stree);
 843
 844         merge_stree(&res, tmp_stree);
 845         filter_stree(&res, pre_stree);
 846
 847         push_stree(stack, res);
 848         free_stree(&tmp_stree);
 849         free_stree(&pre_stree);
 850         free_stree(&new);
 851         free_stree(&old);
 852 }
 853
 854 /*
 855  * get_named_stree() is only used for gotos.
 856  */
 857 struct stree **get_named_stree(struct named_stree_stack *stack,
 858                                               const char *name)
 859 {
 860         struct named_stree *tmp;
 861
 862         FOR_EACH_PTR(stack, tmp) {
 863                 if (!strcmp(tmp->name, name))
 864                         return &tmp->stree;
 865         } END_FOR_EACH_PTR(tmp);
 866         return NULL;
 867 }
 868
 869 /* FIXME:  These parameters are in a different order from expected */
 870 void overwrite_stree(struct stree *from, struct stree **to)
 871 {
 872         struct sm_state *tmp;
 873
 874         FOR_EACH_SM(from, tmp) {
 875                 overwrite_sm_state_stree(to, tmp);
 876         } END_FOR_EACH_SM(tmp);
 877 }
 878