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