smatch_slist.c

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