smatch_slist.c

   1 /*
   2  * sparse/smatch_slist.c
   3  *
   4  * Copyright (C) 2008 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("'%s'=%s\n", state->name, 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 struct sm_state *alloc_state(const char *name, int owner,
  44                              struct symbol *sym, struct smatch_state *state)
  45 {
  46         struct sm_state *sm_state = __alloc_sm_state(0);
  47
  48         sm_state->name = (char *)name;
  49         sm_state->owner = owner;
  50         sm_state->sym = sym;
  51         sm_state->state = state;
  52         sm_state->line_history = NULL;
  53         add_history(sm_state);
  54         sm_state->pools = NULL;
  55         return sm_state;
  56 }
  57
  58 struct sm_state *clone_state(struct sm_state *s)
  59 {
  60         struct sm_state *tmp;
  61
  62         tmp = alloc_state(s->name, s->owner, s->sym, s->state);
  63         tmp->pools = clone_stack(s->pools);
  64         return tmp;
  65 }
  66
  67 /* NULL states go at the end to simplify merge_slist */
  68 static int cmp_sm_states(const void *_a, const void *_b)
  69 {
  70         const struct sm_state *a = _a;
  71         const struct sm_state *b = _b;
  72         int ret;
  73
  74         if (!a && !b)
  75                 return 0;
  76         if (!b)
  77                 return -1;
  78         if (!a)
  79                 return 1;
  80
  81         if (a->owner > b->owner)
  82                 return -1;
  83         if (a->owner < b->owner)
  84                 return 1;
  85
  86         ret = strcmp(a->name, b->name);
  87         if (ret)
  88                 return ret;
  89
  90         if (!b->sym && a->sym)
  91                 return -1;
  92         if (!a->sym && b->sym)
  93                 return 1;
  94         if (a->sym > b->sym)
  95                 return -1;
  96         if (a->sym < b->sym)
  97                 return 1;
  98
  99         return 0;
 100 }
 101
 102 #ifdef CHECKORDER
 103 static void check_order(struct state_list *slist)
 104 {
 105         struct sm_state *state;
 106         struct sm_state *last = NULL;
 107         int printed = 0;
 108
 109         FOR_EACH_PTR(slist, state) {
 110                 if (last && cmp_sm_states(state, last) <= 0) {
 111                         printf("Error.  Unsorted slist %d vs %d, %p vs %p, "
 112                                "%s vs %s\n", last->owner, state->owner,
 113                                last->sym, state->sym, last->name, state->name);
 114                 printed = 1;
 115                 }
 116                 last = state;
 117         } END_FOR_EACH_PTR(state);
 118
 119         if (printed)
 120                 printf("======\n");
 121 }
 122 #endif
 123
 124 struct state_list *clone_slist(struct state_list *from_slist)
 125 {
 126         struct sm_state *state;
 127         struct sm_state *tmp;
 128         struct state_list *to_slist = NULL;
 129
 130         FOR_EACH_PTR(from_slist, state) {
 131                 tmp = clone_state(state);
 132                 add_ptr_list(&to_slist, tmp);
 133         } END_FOR_EACH_PTR(state);
 134 #ifdef CHECKORDER
 135         check_order(to_slist);
 136 #endif
 137         return to_slist;
 138 }
 139
 140 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
 141 {
 142         struct state_list *slist;
 143         struct state_list_stack *to_stack = NULL;
 144
 145         FOR_EACH_PTR(from_stack, slist) {
 146                 push_slist(&to_stack, slist);
 147         } END_FOR_EACH_PTR(slist);
 148         return to_stack;
 149 }
 150
 151 // FIXME...  shouldn't we free some of these state pointers?
 152 struct smatch_state *merge_states(const char *name, int owner,
 153                                   struct symbol *sym,
 154                                   struct smatch_state *state1,
 155                                   struct smatch_state *state2)
 156 {
 157         struct smatch_state *ret;
 158
 159         if (state1 == state2)
 160                 ret = state1;
 161         else if (__has_merge_function(owner))
 162                 ret = __client_merge_function(owner, name, sym, state1, state2);
 163         else
 164                 ret = &undefined;
 165
 166         SM_DEBUG("%d merge name='%s' owner=%d: %s + %s => %s\n",
 167                  get_lineno(), name, owner, show_state(state1),
 168                  show_state(state2), show_state(ret));
 169
 170         return ret;
 171 }
 172
 173 struct smatch_state *get_state_slist(struct state_list *slist, const char *name, int owner,
 174                     struct symbol *sym)
 175 {
 176         struct sm_state *state;
 177
 178         if (!name)
 179                 return NULL;
 180
 181         FOR_EACH_PTR(slist, state) {
 182                 if (state->owner == owner && state->sym == sym
 183                     && !strcmp(state->name, name))
 184                         return state->state;
 185         } END_FOR_EACH_PTR(state);
 186         return NULL;
 187 }
 188
 189 struct sm_state *get_sm_state_slist(struct state_list *slist, const char *name, int owner,
 190                     struct symbol *sym)
 191 {
 192         struct sm_state *state;
 193
 194         if (!name)
 195                 return NULL;
 196
 197         FOR_EACH_PTR(slist, state) {
 198                 if (state->owner == owner && state->sym == sym
 199                     && !strcmp(state->name, name))
 200                         return state;
 201         } END_FOR_EACH_PTR(state);
 202         return NULL;
 203 }
 204
 205 static void overwrite_sm_state(struct state_list **slist,
 206                                struct sm_state *state)
 207 {
 208         struct sm_state *tmp;
 209         struct sm_state *new = clone_state(state);
 210
 211         FOR_EACH_PTR(*slist, tmp) {
 212                 if (cmp_sm_states(tmp, new) < 0)
 213                         continue;
 214                 else if (cmp_sm_states(tmp, new) == 0) {
 215                         tmp->state = new->state;
 216                         tmp->pools = new->pools;
 217                         __free_sm_state(new);
 218                         return;
 219                 } else {
 220                         INSERT_CURRENT(new, tmp);
 221                         return;
 222                 }
 223         } END_FOR_EACH_PTR(tmp);
 224         add_ptr_list(slist, new);
 225 }
 226
 227 void set_state_slist(struct state_list **slist, const char *name, int owner,
 228                      struct symbol *sym, struct smatch_state *state)
 229 {
 230         struct sm_state *tmp;
 231         struct sm_state *new = alloc_state(name, owner, sym, state);
 232
 233         FOR_EACH_PTR(*slist, tmp) {
 234                 if (cmp_sm_states(tmp, new) < 0)
 235                         continue;
 236                 else if (cmp_sm_states(tmp, new) == 0) {
 237                         __free_sm_state(new);
 238                         tmp->state = state;
 239                         tmp->pools = NULL;
 240                         return;
 241                 } else {
 242                         INSERT_CURRENT(new, tmp);
 243                         return;
 244                 }
 245         } END_FOR_EACH_PTR(tmp);
 246         add_ptr_list(slist, new);
 247 }
 248
 249 void delete_state_slist(struct state_list **slist, const char *name, int owner,
 250                         struct symbol *sym)
 251 {
 252         struct sm_state *state;
 253
 254         FOR_EACH_PTR(*slist, state) {
 255                 if (state->owner == owner && state->sym == sym
 256                     && !strcmp(state->name, name)){
 257                         delete_ptr_list_entry((struct ptr_list **)slist,
 258                                               state, 1);
 259                         __free_sm_state(state);
 260                         return;
 261                 }
 262         } END_FOR_EACH_PTR(state);
 263 }
 264
 265
 266 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 267 {
 268         add_ptr_list(list_stack, slist);
 269 }
 270
 271 struct state_list *pop_slist(struct state_list_stack **list_stack)
 272 {
 273         struct state_list *slist;
 274
 275         slist = last_ptr_list((struct ptr_list *)*list_stack);
 276         delete_ptr_list_last((struct ptr_list **)list_stack);
 277         return slist;
 278 }
 279
 280 void del_slist(struct state_list **slist)
 281 {
 282         __free_ptr_list((struct ptr_list **)slist);
 283 }
 284
 285 void del_slist_stack(struct state_list_stack **slist_stack)
 286 {
 287         struct state_list *slist;
 288
 289         FOR_EACH_PTR(*slist_stack, slist) {
 290                 __free_ptr_list((struct ptr_list **)&slist);
 291         } END_FOR_EACH_PTR(slist);
 292         __free_ptr_list((struct ptr_list **)slist_stack);
 293 }
 294
 295 /*
 296  * set_state_stack() sets the state for the top slist on the stack.
 297  */
 298 void set_state_stack(struct state_list_stack **stack, const char *name,
 299                      int owner, struct symbol *sym, struct smatch_state *state)
 300 {
 301         struct state_list *slist;
 302
 303         slist = pop_slist(stack);
 304         set_state_slist(&slist, name, owner, sym, state);
 305         push_slist(stack, slist);
 306 }
 307
 308 /*
 309  * get_state_stack() gets the state for the top slist on the stack.
 310  */
 311 struct smatch_state *get_state_stack(struct state_list_stack *stack,
 312                                      const char *name, int owner,
 313                                      struct symbol *sym)
 314 {
 315         struct state_list *slist;
 316         struct smatch_state *ret;
 317
 318         slist = pop_slist(&stack);
 319         ret = get_state_slist(slist, name, owner, sym);
 320         push_slist(&stack, slist);
 321         return ret;
 322 }
 323
 324 static void add_pool(struct sm_state *state, struct state_list **pool)
 325 {
 326         add_ptr_list(pool, state);
 327         push_slist(&state->pools, *pool);
 328 }
 329
 330 void merge_slist(struct state_list **to, struct state_list *slist)
 331 {
 332         struct sm_state *to_state, *state, *tmp;
 333         struct state_list *results = NULL;
 334         struct smatch_state *s;
 335         struct state_list *implied_to = NULL;
 336         struct state_list *implied_from = NULL;
 337
 338 #ifdef CHECKORDER
 339         check_order(*to);
 340         check_order(slist);
 341 #endif
 342
 343         /* merging a null and nonnull path gives you only the nonnull path */
 344         if (!slist) {
 345                 return;
 346         }
 347         if (!*to) {
 348                 *to = clone_slist(slist);
 349                 return;
 350         }
 351
 352         PREPARE_PTR_LIST(*to, to_state);
 353         PREPARE_PTR_LIST(slist, state);
 354         for (;;) {
 355                 if (!to_state && !state)
 356                         break;
 357                 if (cmp_sm_states(to_state, state) < 0) {
 358                         s = merge_states(to_state->name, to_state->owner,
 359                                          to_state->sym, to_state->state, NULL);
 360                         tmp = alloc_state(to_state->name, to_state->owner,
 361                                           to_state->sym, s);
 362                         add_ptr_list(&results, tmp);
 363                         add_pool(to_state, &implied_to);
 364                         NEXT_PTR_LIST(to_state);
 365                 } else if (cmp_sm_states(to_state, state) == 0) {
 366                         if (to_state->state == state->state) {
 367                                 s = to_state->state;
 368                         } else {
 369                                 s = merge_states(to_state->name,
 370                                                  to_state->owner,
 371                                                  to_state->sym, to_state->state,
 372                                                  state->state);
 373                                 add_pool(to_state, &implied_to);
 374                                 add_pool(state, &implied_from);
 375                         }
 376                         tmp = alloc_state(to_state->name, to_state->owner,
 377                                           to_state->sym, s);
 378                         add_ptr_list(&results, tmp);
 379                         NEXT_PTR_LIST(to_state);
 380                         NEXT_PTR_LIST(state);
 381                 } else {
 382                         s = merge_states(state->name, state->owner,
 383                                          state->sym, state->state, NULL);
 384                         tmp = alloc_state(state->name, state->owner,
 385                                           state->sym, s);
 386                         add_ptr_list(&results, tmp);
 387                         add_pool(state, &implied_from);
 388                         NEXT_PTR_LIST(state);
 389                 }
 390         }
 391         FINISH_PTR_LIST(state);
 392         FINISH_PTR_LIST(to_state);
 393
 394         del_slist(to);
 395         *to = results;
 396
 397         if (implied_from)
 398                 push_slist(&implied_pools, implied_from);
 399         if (implied_to)
 400                 push_slist(&implied_pools, implied_to);
 401 }
 402
 403 void filter(struct state_list **slist, struct state_list *filter)
 404 {
 405         struct sm_state *s_one, *s_two;
 406         struct state_list **results;
 407
 408 #ifdef CHECKORDER
 409         check_order(*slist);
 410         check_order(filter);
 411 #endif
 412
 413         results = malloc(sizeof(*results));
 414         *results = NULL;
 415
 416         PREPARE_PTR_LIST(*slist, s_one);
 417         PREPARE_PTR_LIST(filter, s_two);
 418         for (;;) {
 419                 if (!s_one || !s_two)
 420                         break;
 421                 if (cmp_sm_states(s_one, s_two) < 0) {
 422                         SM_DEBUG("different missing in new %s\n", s_one->name);
 423                         NEXT_PTR_LIST(s_one);
 424                 } else if (cmp_sm_states(s_one, s_two) == 0) {
 425                         if (s_one->state == s_two->state) {
 426                                 add_ptr_list(results, s_one);
 427                                 SM_DEBUG("same %s\n", s_one->name);
 428                         } else
 429                                 SM_DEBUG("different %s %s vs %s\n", s_one->name,
 430                                        show_state(s_one->state),
 431                                        show_state(s_two->state));
 432                         NEXT_PTR_LIST(s_one);
 433                         NEXT_PTR_LIST(s_two);
 434                 } else {
 435                         SM_DEBUG("different missing in old%s\n", s_two->name);
 436                         NEXT_PTR_LIST(s_two);
 437                 }
 438         }
 439         FINISH_PTR_LIST(s_two);
 440         FINISH_PTR_LIST(s_one);
 441
 442         del_slist(slist);
 443         *slist = *results;
 444 }
 445
 446 /*
 447  * This function is basically the same as popping the top two slists,
 448  * overwriting the one with the other and pushing it back on the stack.
 449  * The difference is that it checks to see that a mutually exclusive
 450  * state isn't included in both stacks.
 451  */
 452
 453 void and_slist_stack(struct state_list_stack **slist_stack)
 454 {
 455         struct sm_state *tmp;
 456         struct smatch_state *tmp_state;
 457         struct state_list *tmp_slist = pop_slist(slist_stack);
 458
 459         FOR_EACH_PTR(tmp_slist, tmp) {
 460                 tmp_state = get_state_stack(*slist_stack, tmp->name,
 461                                             tmp->owner, tmp->sym);
 462                 if (tmp_state && tmp_state != tmp->state) {
 463                         smatch_msg("mutually exclusive 'and' conditions states "
 464                                    "'%s': %s & %s.\n",
 465                                    tmp->name, show_state(tmp_state),
 466                                    show_state(tmp->state));
 467                         tmp->state = merge_states(tmp->name, tmp->owner,
 468                                                   tmp->sym, tmp->state,
 469                                                   tmp_state);
 470                 }
 471                 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
 472                                 tmp->state);
 473
 474         } END_FOR_EACH_PTR(tmp);
 475         del_slist(&tmp_slist);
 476 }
 477
 478 void or_slist_stack(struct state_list_stack **slist_stack)
 479 {
 480         struct state_list *one;
 481         struct state_list *two;
 482         struct state_list *res = NULL;
 483         struct sm_state *tmp;
 484         struct smatch_state *s;
 485
 486         one = pop_slist(slist_stack);
 487         two = pop_slist(slist_stack);
 488
 489         FOR_EACH_PTR(one, tmp) {
 490                 s = get_state_slist(two, tmp->name, tmp->owner, tmp->sym);
 491                 s = merge_states(tmp->name, tmp->owner, tmp->sym,
 492                                  tmp->state, s);
 493                 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
 494         } END_FOR_EACH_PTR(tmp);
 495
 496
 497         FOR_EACH_PTR(two, tmp) {
 498                 s = get_state_slist(one, tmp->name, tmp->owner, tmp->sym);
 499                 s = merge_states(tmp->name, tmp->owner, tmp->sym,
 500                                  tmp->state, s);
 501                 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
 502         } END_FOR_EACH_PTR(tmp);
 503
 504         push_slist(slist_stack, res);
 505
 506         del_slist(&one);
 507         del_slist(&two);
 508 }
 509
 510 struct state_list **get_slist_from_slist_stack(struct slist_stack *stack,
 511                                               const char *name)
 512 {
 513         struct named_slist *tmp;
 514
 515         FOR_EACH_PTR(stack, tmp) {
 516                 if (!strcmp(tmp->name, name))
 517                         return &tmp->slist;
 518         } END_FOR_EACH_PTR(tmp);
 519         return NULL;
 520 }
 521
 522 void overwrite_slist(struct state_list *from, struct state_list **to)
 523 {
 524         struct sm_state *tmp;
 525
 526         FOR_EACH_PTR(from, tmp) {
 527                 overwrite_sm_state(to, tmp);
 528         } END_FOR_EACH_PTR(tmp);
 529 }
 530