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