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