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.h"
  14 #include "smatch_slist.h"
  15
  16 #undef CHECKORDER
  17
  18 ALLOCATOR(sm_state, "smatch state");
  19 ALLOCATOR(named_slist, "named slist");
  20
  21 void __print_slist(struct state_list *slist)
  22 {
  23         struct sm_state *state;
  24
  25         printf("dumping slist at %d\n", get_lineno());
  26         FOR_EACH_PTR(slist, state) {
  27                 printf("%d '%s'=%s\n", state->owner, state->name,
  28                         show_state(state->state));
  29         } END_FOR_EACH_PTR(state);
  30         printf("---\n");
  31 }
  32
  33 void add_history(struct sm_state *state)
  34 {
  35         struct state_history *tmp;
  36
  37         if (!state)
  38                 return;
  39         tmp = malloc(sizeof(*tmp));
  40         tmp->loc = get_lineno();
  41         add_ptr_list(&state->line_history, tmp);
  42 }
  43
  44
  45 /* NULL states go at the end to simplify merge_slist */
  46 static int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
  47 {
  48         int ret;
  49
  50         if (!a && !b)
  51                 return 0;
  52         if (!b)
  53                 return -1;
  54         if (!a)
  55                 return 1;
  56
  57         if (a->owner > b->owner)
  58                 return -1;
  59         if (a->owner < b->owner)
  60                 return 1;
  61
  62         ret = strcmp(a->name, b->name);
  63         if (ret)
  64                 return ret;
  65
  66         if (!b->sym && a->sym)
  67                 return -1;
  68         if (!a->sym && b->sym)
  69                 return 1;
  70         if (a->sym > b->sym)
  71                 return -1;
  72         if (a->sym < b->sym)
  73                 return 1;
  74
  75         return 0;
  76 }
  77
  78 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b)
  79 {
  80         int ret;
  81
  82         ret = cmp_tracker(a, b);
  83         if (ret)
  84                 return ret;
  85
  86         /* todo:  add hook for smatch_extra.c */
  87         if (a->state > b->state)
  88                 return -1;
  89         if (a->state < b->state)
  90                 return 1;
  91         return 0;
  92 }
  93
  94 void add_sm_state_slist(struct state_list **slist, struct sm_state *new)
  95 {
  96         struct sm_state *tmp;
  97
  98         FOR_EACH_PTR(*slist, tmp) {
  99                 if (cmp_sm_states(tmp, new) < 0)
 100                         continue;
 101                 else if (cmp_sm_states(tmp, new) == 0) {
 102                         return;
 103                 } else {
 104                         INSERT_CURRENT(new, tmp);
 105                         return;
 106                 }
 107         } END_FOR_EACH_PTR(tmp);
 108         add_ptr_list(slist, new);
 109 }
 110
 111 static void add_possible(struct sm_state *sm, struct sm_state *new)
 112 {
 113         struct sm_state *tmp;
 114
 115
 116         if (!new) {
 117                 struct smatch_state *s;
 118
 119                 s = merge_states(sm->name, sm->owner, sm->sym, sm->state, NULL);
 120                 tmp = alloc_state(sm->name, sm->owner, sm->sym, s);
 121                 add_sm_state_slist(&sm->possible, tmp);
 122                 return;
 123         }
 124         FOR_EACH_PTR(new->possible, tmp) {
 125                 add_sm_state_slist(&sm->possible, tmp);
 126         } END_FOR_EACH_PTR(tmp);
 127 }
 128
 129 struct sm_state *alloc_state(const char *name, int owner,
 130                              struct symbol *sym, struct smatch_state *state)
 131 {
 132         struct sm_state *sm_state = __alloc_sm_state(0);
 133
 134         sm_state->name = (char *)name;
 135         sm_state->owner = owner;
 136         sm_state->sym = sym;
 137         sm_state->state = state;
 138         sm_state->line_history = NULL;
 139         add_history(sm_state);
 140         sm_state->pools = NULL;
 141         sm_state->possible = NULL;
 142         add_ptr_list(&sm_state->possible, sm_state);
 143         return sm_state;
 144 }
 145
 146 struct sm_state *clone_state(struct sm_state *s)
 147 {
 148         struct sm_state *tmp;
 149
 150         tmp = alloc_state(s->name, s->owner, s->sym, s->state);
 151         tmp->pools = clone_stack(s->pools);
 152         tmp->possible = s->possible;
 153         return tmp;
 154 }
 155
 156 int slist_has_state(struct state_list *slist, struct smatch_state *state)
 157 {
 158         struct sm_state *tmp;
 159
 160         FOR_EACH_PTR(slist, tmp) {
 161                 if (tmp->state == state)
 162                         return 1;
 163         } END_FOR_EACH_PTR(tmp);
 164         return 0;
 165 }
 166
 167 #ifdef CHECKORDER
 168 static void check_order(struct state_list *slist)
 169 {
 170         struct sm_state *state;
 171         struct sm_state *last = NULL;
 172         int printed = 0;
 173
 174         FOR_EACH_PTR(slist, state) {
 175                 if (last && cmp_tracker(state, last) <= 0) {
 176                         printf("Error.  Unsorted slist %d vs %d, %p vs %p, "
 177                                "%s vs %s\n", last->owner, state->owner,
 178                                last->sym, state->sym, last->name, state->name);
 179                         printed = 1;
 180                 }
 181                 last = state;
 182         } END_FOR_EACH_PTR(state);
 183
 184         if (printed)
 185                 printf("======\n");
 186 }
 187 #endif
 188
 189 struct state_list *clone_slist(struct state_list *from_slist)
 190 {
 191         struct sm_state *state;
 192         struct sm_state *tmp;
 193         struct state_list *to_slist = NULL;
 194
 195         FOR_EACH_PTR(from_slist, state) {
 196                 tmp = clone_state(state);
 197                 add_ptr_list(&to_slist, tmp);
 198         } END_FOR_EACH_PTR(state);
 199 #ifdef CHECKORDER
 200         check_order(to_slist);
 201 #endif
 202         return to_slist;
 203 }
 204
 205 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
 206 {
 207         struct state_list *slist;
 208         struct state_list_stack *to_stack = NULL;
 209
 210         FOR_EACH_PTR(from_stack, slist) {
 211                 push_slist(&to_stack, slist);
 212         } END_FOR_EACH_PTR(slist);
 213         return to_stack;
 214 }
 215
 216 // FIXME...  shouldn't we free some of these state pointers?
 217 struct smatch_state *merge_states(const char *name, int owner,
 218                                   struct symbol *sym,
 219                                   struct smatch_state *state1,
 220                                   struct smatch_state *state2)
 221 {
 222         struct smatch_state *ret;
 223
 224         if (state1 == state2)
 225                 ret = state1;
 226         else if (__has_merge_function(owner))
 227                 ret = __client_merge_function(owner, name, sym, state1, state2);
 228         else if (!state1 || !state2)
 229                 ret = &undefined;
 230         else
 231                 ret = &merged;
 232         return ret;
 233 }
 234
 235 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
 236 {
 237         struct smatch_state *s;
 238         struct sm_state *result;
 239
 240         s = merge_states(one->name, one->owner, one->sym, one->state,
 241                         (two?two->state:NULL));
 242         result = alloc_state(one->name, one->owner, one->sym, s);
 243         add_possible(result, one);
 244         add_possible(result, two);
 245
 246         if (debug_states) {
 247                 struct sm_state *tmp;
 248                 int i = 0;
 249
 250                 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
 251                         get_lineno(), one->name, one->owner,
 252                         show_state(one->state), show_state(two?two->state:NULL),
 253                         show_state(s));
 254
 255                 FOR_EACH_PTR(result->possible, tmp) {
 256                         if (i++) {
 257                                 printf(", ");
 258                         }
 259                         printf("%s", show_state(tmp->state));
 260                 } END_FOR_EACH_PTR(tmp);
 261                 printf(")\n");
 262         }
 263
 264         return result;
 265 }
 266
 267 struct sm_state *get_sm_state_slist(struct state_list *slist, const char *name,
 268                                 int owner, struct symbol *sym)
 269 {
 270         struct sm_state *state;
 271
 272         if (!name)
 273                 return NULL;
 274
 275         FOR_EACH_PTR(slist, state) {
 276                 if (state->owner == owner && state->sym == sym
 277                     && !strcmp(state->name, name))
 278                         return state;
 279         } END_FOR_EACH_PTR(state);
 280         return NULL;
 281 }
 282
 283 struct smatch_state *get_state_slist(struct state_list *slist,
 284                                 const char *name, int owner,
 285                                 struct symbol *sym)
 286 {
 287         struct sm_state *state;
 288
 289         state = get_sm_state_slist(slist, name, owner, sym);
 290         if (state)
 291                 return state->state;
 292         return NULL;
 293 }
 294
 295 static void overwrite_sm_state(struct state_list **slist,
 296                                struct sm_state *state)
 297 {
 298         struct sm_state *tmp;
 299         struct sm_state *new = clone_state(state); //fixme. why?
 300
 301         FOR_EACH_PTR(*slist, tmp) {
 302                 if (cmp_tracker(tmp, new) < 0)
 303                         continue;
 304                 else if (cmp_tracker(tmp, new) == 0) {
 305                         tmp->state = new->state;
 306                         tmp->pools = new->pools;
 307                         tmp->possible = new->possible;
 308                         __free_sm_state(new);
 309                         return;
 310                 } else {
 311                         INSERT_CURRENT(new, tmp);
 312                         return;
 313                 }
 314         } END_FOR_EACH_PTR(tmp);
 315         add_ptr_list(slist, new);
 316 }
 317
 318 void set_state_slist(struct state_list **slist, const char *name, int owner,
 319                      struct symbol *sym, struct smatch_state *state)
 320 {
 321         struct sm_state *tmp;
 322         struct sm_state *new = alloc_state(name, owner, sym, state);
 323
 324         FOR_EACH_PTR(*slist, tmp) {
 325                 if (cmp_tracker(tmp, new) < 0)
 326                         continue;
 327                 else if (cmp_tracker(tmp, new) == 0) {
 328                         tmp->state = state;
 329                         tmp->pools = NULL;
 330                         tmp->possible = NULL;
 331                         add_ptr_list(&tmp->possible, tmp);
 332                         __free_sm_state(new);
 333                         return;
 334                 } else {
 335                         INSERT_CURRENT(new, tmp);
 336                         return;
 337                 }
 338         } END_FOR_EACH_PTR(tmp);
 339         add_ptr_list(slist, new);
 340 }
 341
 342 void delete_state_slist(struct state_list **slist, const char *name, int owner,
 343                         struct symbol *sym)
 344 {
 345         struct sm_state *state;
 346
 347         FOR_EACH_PTR(*slist, state) {
 348                 if (state->owner == owner && state->sym == sym
 349                     && !strcmp(state->name, name)){
 350                         delete_ptr_list_entry((struct ptr_list **)slist,
 351                                               state, 1);
 352                         __free_sm_state(state);
 353                         return;
 354                 }
 355         } END_FOR_EACH_PTR(state);
 356 }
 357
 358
 359 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 360 {
 361         add_ptr_list(list_stack, slist);
 362 }
 363
 364 struct state_list *pop_slist(struct state_list_stack **list_stack)
 365 {
 366         struct state_list *slist;
 367
 368         slist = last_ptr_list((struct ptr_list *)*list_stack);
 369         delete_ptr_list_last((struct ptr_list **)list_stack);
 370         return slist;
 371 }
 372
 373 void del_slist(struct state_list **slist)
 374 {
 375         __free_ptr_list((struct ptr_list **)slist);
 376 }
 377
 378 void del_slist_stack(struct state_list_stack **slist_stack)
 379 {
 380         struct state_list *slist;
 381
 382         FOR_EACH_PTR(*slist_stack, slist) {
 383                 __free_ptr_list((struct ptr_list **)&slist);
 384         } END_FOR_EACH_PTR(slist);
 385         __free_ptr_list((struct ptr_list **)slist_stack);
 386 }
 387
 388 /*
 389  * set_state_stack() sets the state for the top slist on the stack.
 390  */
 391 void set_state_stack(struct state_list_stack **stack, const char *name,
 392                      int owner, struct symbol *sym, struct smatch_state *state)
 393 {
 394         struct state_list *slist;
 395
 396         slist = pop_slist(stack);
 397         set_state_slist(&slist, name, owner, sym, state);
 398         push_slist(stack, slist);
 399 }
 400
 401 /*
 402  * get_state_stack() gets the state for the top slist on the stack.
 403  */
 404 struct smatch_state *get_state_stack(struct state_list_stack *stack,
 405                                      const char *name, int owner,
 406                                      struct symbol *sym)
 407 {
 408         struct state_list *slist;
 409         struct smatch_state *ret;
 410
 411         slist = pop_slist(&stack);
 412         ret = get_state_slist(slist, name, owner, sym);
 413         push_slist(&stack, slist);
 414         return ret;
 415 }
 416
 417 /*
 418  * add_pool() adds a slist to ->pools. If the slist has already been
 419  * added earlier then it doesn't get added a second time.
 420  */
 421 static void add_pool(struct sm_state *to, struct state_list *new)
 422 {
 423         struct state_list *tmp;
 424
 425         FOR_EACH_PTR(to->pools, tmp) {
 426                 if (tmp < new)
 427                         continue;
 428                 else if (tmp == new) {
 429                         return;
 430                 } else {
 431                         INSERT_CURRENT(new, tmp);
 432                         return;
 433                 }
 434         } END_FOR_EACH_PTR(tmp);
 435         add_ptr_list(&to->pools, new);
 436 }
 437
 438 static void copy_pools(struct sm_state *to, struct sm_state *sm)
 439 {
 440         struct state_list *tmp;
 441
 442         FOR_EACH_PTR(sm->pools, tmp) {
 443                 add_pool(to, tmp);
 444         } END_FOR_EACH_PTR(tmp);
 445 }
 446
 447 /*
 448  * merge_slist() is called whenever paths merge, such as after
 449  * an if statement.  It takes the two slists and creates one.
 450  */
 451 void merge_slist(struct state_list **to, struct state_list *slist)
 452 {
 453         struct sm_state *to_state, *state, *tmp;
 454         struct state_list *results = NULL;
 455         struct state_list *implied_to = NULL;
 456         struct state_list *implied_from = NULL;
 457
 458 #ifdef CHECKORDER
 459         check_order(*to);
 460         check_order(slist);
 461 #endif
 462
 463         /* merging a null and nonnull path gives you only the nonnull path */
 464         if (!slist) {
 465                 return;
 466         }
 467         if (!*to) {
 468                 *to = clone_slist(slist);
 469                 return;
 470         }
 471
 472         PREPARE_PTR_LIST(*to, to_state);
 473         PREPARE_PTR_LIST(slist, state);
 474         for (;;) {
 475                 if (!to_state && !state)
 476                         break;
 477                 if (cmp_tracker(to_state, state) < 0) {
 478                         tmp = merge_sm_states(to_state, NULL);
 479
 480                         copy_pools(tmp, to_state);
 481
 482                         add_ptr_list(&implied_to, to_state);
 483                         add_pool(tmp, implied_to);
 484
 485                         add_ptr_list(&results, tmp);
 486                         NEXT_PTR_LIST(to_state);
 487                 } else if (cmp_tracker(to_state, state) == 0) {
 488                         if (to_state->state == state->state) {
 489                                 tmp = merge_sm_states(to_state, state);
 490                         } else {
 491                                 tmp = merge_sm_states(to_state, state);
 492
 493                                 copy_pools(tmp, to_state);
 494                                 copy_pools(tmp, state);
 495
 496                                 add_ptr_list(&implied_to, to_state);
 497                                 add_pool(tmp, implied_to);
 498                                 add_ptr_list(&implied_from, state);
 499                                 add_pool(tmp, implied_from);
 500                         }
 501                         add_ptr_list(&results, tmp);
 502                         NEXT_PTR_LIST(to_state);
 503                         NEXT_PTR_LIST(state);
 504                 } else {
 505                         tmp = merge_sm_states(state, NULL);
 506
 507                         copy_pools(tmp, state);
 508
 509                         add_ptr_list(&implied_from, state);
 510                         add_pool(tmp, implied_from);
 511
 512                         add_ptr_list(&results, tmp);
 513                         NEXT_PTR_LIST(state);
 514                 }
 515         }
 516         FINISH_PTR_LIST(state);
 517         FINISH_PTR_LIST(to_state);
 518
 519         del_slist(to);
 520         *to = results;
 521
 522         if (implied_from)
 523                 push_slist(&implied_pools, implied_from);
 524         if (implied_to)
 525                 push_slist(&implied_pools, implied_to);
 526 }
 527
 528 /*
 529  * is_currently_in_pool() is used because we remove states from pools.
 530  * When set_state() is called then we set ->pools to NULL, but on
 531  * other paths the state is still a member of those pools.
 532  * Confusing huh?
 533  * if (foo) {
 534  *        bar = 1;
 535  *        a = malloc();
 536  * }
 537  * if (!a)
 538  *        return;
 539  * if (bar)
 540  *        a->b = x;
 541  */
 542 static int is_currently_in_pool(struct sm_state *sm, struct state_list *pool,
 543                         struct state_list *cur_slist)
 544 {
 545         struct sm_state *cur_state;
 546         struct state_list *tmp;
 547
 548         cur_state = get_sm_state_slist(cur_slist, sm->name, sm->owner, sm->sym);
 549         if (!cur_state)
 550                 return 0;
 551
 552         FOR_EACH_PTR(cur_state->pools, tmp) {
 553                 if (tmp == pool)
 554                         return 1;
 555         } END_FOR_EACH_PTR(tmp);
 556         return 0;
 557 }
 558
 559 struct state_list *clone_states_in_pool(struct state_list *pool,
 560                                 struct state_list *cur_slist)
 561 {
 562         struct sm_state *state;
 563         struct sm_state *tmp;
 564         struct state_list *to_slist = NULL;
 565
 566         FOR_EACH_PTR(pool, state) {
 567                 if (is_currently_in_pool(state, pool, cur_slist)) {
 568                         tmp = clone_state(state);
 569                         add_ptr_list(&to_slist, tmp);
 570                 }
 571         } END_FOR_EACH_PTR(state);
 572 #ifdef CHECKORDER
 573         check_order(to_slist);
 574 #endif
 575         return to_slist;
 576 }
 577
 578 /*
 579  * filter() is used to find what states are the same across
 580  * a series of slists.
 581  * It takes a **slist and a *filter.
 582  * It removes everything from **slist that isn't in *filter.
 583  * The reason you would want to do this is if you want to
 584  * know what other states are true if one state is true.  (smatch_implied).
 585  */
 586 void filter(struct state_list **slist, struct state_list *filter,
 587         struct state_list *cur_slist)
 588 {
 589         struct sm_state *s_one, *s_two;
 590         struct state_list *results = NULL;
 591
 592 #ifdef CHECKORDER
 593         check_order(*slist);
 594         check_order(filter);
 595 #endif
 596
 597         PREPARE_PTR_LIST(*slist, s_one);
 598         PREPARE_PTR_LIST(filter, s_two);
 599         for (;;) {
 600                 if (!s_one || !s_two)
 601                         break;
 602                 if (cmp_tracker(s_one, s_two) < 0) {
 603                         NEXT_PTR_LIST(s_one);
 604                 } else if (cmp_tracker(s_one, s_two) == 0) {
 605                         /* todo.  pointer comparison works fine for most things
 606                            except smatch_extra.  we may need a hook here. */
 607                         if (s_one->state == s_two->state &&
 608                                 is_currently_in_pool(s_two, filter, cur_slist)) {
 609                                 add_ptr_list(&results, s_one);
 610                         }
 611                         NEXT_PTR_LIST(s_one);
 612                         NEXT_PTR_LIST(s_two);
 613                 } else {
 614                         NEXT_PTR_LIST(s_two);
 615                 }
 616         }
 617         FINISH_PTR_LIST(s_two);
 618         FINISH_PTR_LIST(s_one);
 619
 620         del_slist(slist);
 621         *slist = results;
 622 }
 623
 624 /*
 625  * and_slist_stack() is basically the same as popping the top two slists,
 626  * overwriting the one with the other and pushing it back on the stack.
 627  * The difference is that it checks to see that a mutually exclusive
 628  * state isn't included in both stacks.  If smatch sees something like
 629  * "if (a && !a)" it prints a warning.
 630  */
 631 void and_slist_stack(struct state_list_stack **slist_stack)
 632 {
 633         struct sm_state *tmp;
 634         struct smatch_state *tmp_state;
 635         struct state_list *tmp_slist = pop_slist(slist_stack);
 636
 637         FOR_EACH_PTR(tmp_slist, tmp) {
 638                 tmp_state = get_state_stack(*slist_stack, tmp->name,
 639                                             tmp->owner, tmp->sym);
 640                 if (tmp_state && tmp_state != tmp->state) {
 641                         struct smatch_state *s;
 642
 643                         s = merge_states(tmp->name, tmp->owner, tmp->sym,
 644                                         tmp->state, tmp_state);
 645                         smatch_msg("mutually exclusive 'and' conditions states "
 646                                 "'%s': %s + %s => %s",
 647                                 tmp->name, show_state(tmp_state),
 648                                 show_state(tmp->state), show_state(s));
 649                         tmp->state = s;
 650
 651                 }
 652                 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
 653                                 tmp->state);
 654         } END_FOR_EACH_PTR(tmp);
 655         del_slist(&tmp_slist);
 656 }
 657
 658 /*
 659  * or_slist_stack() is for if we have:  if (foo || bar) { foo->baz;
 660  * It pops the two slists from the top of the stack and merges them
 661  * together in a way that preserves the things they have in common
 662  * but creates a merged state for most of the rest.
 663  * You could have code that had:  if (foo || foo) { foo->baz;
 664  * It's this function which ensures smatch does the right thing.
 665  */
 666 void or_slist_stack(struct state_list_stack **slist_stack)
 667 {
 668         struct state_list *one;
 669         struct state_list *two;
 670         struct state_list *res = NULL;
 671         struct sm_state *tmp;
 672         struct sm_state *sm;
 673         struct sm_state *new_sm;
 674
 675         one = pop_slist(slist_stack);
 676         two = pop_slist(slist_stack);
 677
 678         FOR_EACH_PTR(one, tmp) {
 679                 sm = get_sm_state_slist(two, tmp->name, tmp->owner, tmp->sym);
 680                 new_sm = merge_sm_states(tmp, sm);
 681                 add_ptr_list(&res, new_sm);
 682         } END_FOR_EACH_PTR(tmp);
 683
 684         FOR_EACH_PTR(two, tmp) {
 685                 sm = get_sm_state_slist(one, tmp->name, tmp->owner, tmp->sym);
 686                 new_sm = merge_sm_states(tmp, sm);
 687                 add_ptr_list(&res, new_sm);
 688         } END_FOR_EACH_PTR(tmp);
 689
 690         push_slist(slist_stack, res);
 691
 692         del_slist(&one);
 693         del_slist(&two);
 694 }
 695
 696 /*
 697  * get_slist_from_named_stack() is only used for gotos.
 698  */
 699 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
 700                                               const char *name)
 701 {
 702         struct named_slist *tmp;
 703
 704         FOR_EACH_PTR(stack, tmp) {
 705                 if (!strcmp(tmp->name, name))
 706                         return &tmp->slist;
 707         } END_FOR_EACH_PTR(tmp);
 708         return NULL;
 709 }
 710
 711 void overwrite_slist(struct state_list *from, struct state_list **to)
 712 {
 713         struct sm_state *tmp;
 714
 715         FOR_EACH_PTR(from, tmp) {
 716                 overwrite_sm_state(to, tmp);
 717         } END_FOR_EACH_PTR(tmp);
 718 }