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