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 #define CHECKORDER 1
  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         sm_state->path_history = NULL;
  43         add_history(sm_state);
  44         return sm_state;
  45 }
  46
  47 struct sm_state *clone_state(struct sm_state *s)
  48 {
  49         return alloc_state(s->name, s->owner, s->sym, s->state);
  50 }
  51
  52 /* NULL states go at the end to simplify merge_slist */
  53 static int cmp_sm_states(const void *_a, const void *_b)
  54 {
  55         const struct sm_state *a = _a;
  56         const struct sm_state *b = _b;
  57         int ret;
  58
  59         if (!a && !b)
  60                 return 0;
  61         if (!b)
  62                 return -1;
  63         if (!a)
  64                 return 1;
  65
  66         if (a->owner > b->owner)
  67                 return -1;
  68         if (a->owner < b->owner)
  69                 return 1;
  70
  71         ret = strcmp(a->name, b->name);
  72         if (ret)
  73                 return ret;
  74
  75         if (!b->sym && a->sym)
  76                 return -1;
  77         if (!a->sym && b->sym)
  78                 return 1;
  79         if (a->sym > b->sym)
  80                 return -1;
  81         if (a->sym < b->sym)
  82                 return 1;
  83
  84         return 0;
  85 }
  86
  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
 107 struct state_list *clone_slist(struct state_list *from_slist)
 108 {
 109         struct sm_state *state;
 110         struct sm_state *tmp;
 111         struct state_list *to_slist = NULL;
 112
 113         FOR_EACH_PTR(from_slist, state) {
 114                 tmp = clone_state(state);
 115                 add_ptr_list(&to_slist, tmp);
 116         } END_FOR_EACH_PTR(state);
 117         check_order(to_slist);
 118         return to_slist;
 119 }
 120
 121 struct smatch_state *merge_states(const char *name, int owner,
 122                                   struct symbol *sym,
 123                                   struct smatch_state *state1,
 124                                   struct smatch_state *state2)
 125 {
 126         struct smatch_state *ret;
 127
 128         if (state1 == state2)
 129                 ret = state1;
 130         else if (__has_merge_function(owner))
 131                 ret = __client_merge_function(owner, name, sym, state1, state2);
 132         else
 133                 ret = &undefined;
 134
 135         SM_DEBUG("%d merge name='%s' owner=%d: %s + %s => %s\n",
 136                  get_lineno(), name, owner, show_state(state1),
 137                  show_state(state2), show_state(ret));
 138
 139         return ret;
 140 }
 141
 142 void merge_state_slist(struct state_list **slist, const char *name, int owner,
 143                        struct symbol *sym, struct smatch_state *state)
 144 {
 145         struct sm_state *tmp;
 146         struct smatch_state *s;
 147
 148         FOR_EACH_PTR(*slist, tmp) {
 149                 if (tmp->owner == owner && tmp->sym == sym
 150                     && !strcmp(tmp->name, name)){
 151                         s = merge_states(name, owner, sym, tmp->state, state);
 152                         if (tmp->state != s) {
 153                                 add_history(tmp);
 154                         }
 155                         tmp->state = s;
 156                         return;
 157                 }
 158         } END_FOR_EACH_PTR(tmp);
 159         set_state_slist(slist, name, owner, sym, state);
 160 }
 161
 162 struct smatch_state *get_state_slist(struct state_list *slist, const char *name, int owner,
 163                     struct symbol *sym)
 164 {
 165         struct sm_state *state;
 166
 167         if (!name)
 168                 return NULL;
 169
 170         FOR_EACH_PTR(slist, state) {
 171                 if (state->owner == owner && state->sym == sym
 172                     && !strcmp(state->name, name))
 173                         return state->state;
 174         } END_FOR_EACH_PTR(state);
 175         return NULL;
 176 }
 177
 178 void set_state_slist(struct state_list **slist, const char *name, int owner,
 179                      struct symbol *sym, struct smatch_state *state)
 180 {
 181         struct sm_state *tmp;
 182         struct sm_state *new = alloc_state(name, owner, sym, state);
 183
 184         FOR_EACH_PTR(*slist, tmp) {
 185                 if (cmp_sm_states(tmp, new) < 0)
 186                         continue;
 187                 else if (cmp_sm_states(tmp, new) == 0) {
 188                         __free_sm_state(new);
 189                         tmp->state = state;
 190                         check_order(*slist);
 191                         return;
 192                 } else {
 193                         INSERT_CURRENT(new, tmp);
 194                         check_order(*slist);
 195                         return;
 196                 }
 197         } END_FOR_EACH_PTR(tmp);
 198         add_ptr_list(slist, new);
 199         check_order(*slist);
 200 }
 201
 202 void delete_state_slist(struct state_list **slist, const char *name, int owner,
 203                         struct symbol *sym)
 204 {
 205         struct sm_state *state;
 206
 207         FOR_EACH_PTR(*slist, state) {
 208                 if (state->owner == owner && state->sym == sym
 209                     && !strcmp(state->name, name)){
 210                         delete_ptr_list_entry((struct ptr_list **)slist,
 211                                               state, 1);
 212                         __free_sm_state(state);
 213                         return;
 214                 }
 215         } END_FOR_EACH_PTR(state);
 216 }
 217
 218
 219 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 220 {
 221         add_ptr_list(list_stack, slist);
 222 }
 223
 224 struct state_list *pop_slist(struct state_list_stack **list_stack)
 225 {
 226         struct state_list *slist;
 227
 228         slist = last_ptr_list((struct ptr_list *)*list_stack);
 229         delete_ptr_list_last((struct ptr_list **)list_stack);
 230         return slist;
 231 }
 232
 233 void del_slist(struct state_list **slist)
 234 {
 235         __free_ptr_list((struct ptr_list **)slist);
 236 }
 237
 238 void del_slist_stack(struct state_list_stack **slist_stack)
 239 {
 240         struct state_list *slist;
 241
 242         FOR_EACH_PTR(*slist_stack, slist) {
 243                 __free_ptr_list((struct ptr_list **)&slist);
 244         } END_FOR_EACH_PTR(slist);
 245         __free_ptr_list((struct ptr_list **)slist_stack);
 246 }
 247
 248 /*
 249  * set_state_stack() sets the state for the top slist on the stack.
 250  */
 251 void set_state_stack(struct state_list_stack **stack, const char *name,
 252                      int owner, struct symbol *sym, struct smatch_state *state)
 253 {
 254         struct state_list *slist;
 255
 256         slist = pop_slist(stack);
 257         set_state_slist(&slist, name, owner, sym, state);
 258         push_slist(stack, slist);
 259 }
 260
 261 /*
 262  * get_state_stack() gets the state for the top slist on the stack.
 263  */
 264 struct smatch_state *get_state_stack(struct state_list_stack *stack,
 265                                      const char *name, int owner,
 266                                      struct symbol *sym)
 267 {
 268         struct state_list *slist;
 269         struct smatch_state *ret;
 270
 271         slist = pop_slist(&stack);
 272         ret = get_state_slist(slist, name, owner, sym);
 273         push_slist(&stack, slist);
 274         return ret;
 275 }
 276
 277 void merge_slist(struct state_list **to, struct state_list *slist)
 278 {
 279         struct sm_state *state;
 280
 281 #ifdef CHECKORDER
 282         check_order(*to);
 283         check_order(slist);
 284 #endif
 285
 286         if (!slist) {
 287                 return;
 288         }
 289
 290         FOR_EACH_PTR(slist, state) {
 291                 merge_state_slist(to, state->name, state->owner,
 292                                   state->sym, state->state);
 293         } END_FOR_EACH_PTR(state);
 294
 295         FOR_EACH_PTR(*to, state) {
 296                 if (!get_state_slist(slist, state->name, state->owner,
 297                                     state->sym)) {
 298                         merge_state_slist(to, state->name, state->owner,
 299                                           state->sym, NULL);
 300                 }
 301         } END_FOR_EACH_PTR(state);
 302 }
 303
 304 /*
 305  * This function is basically the same as popping the top two slists,
 306  * overwriting the one with the other and pushing it back on the stack.
 307  * The difference is that it checks to see that a mutually exclusive
 308  * state isn't included in both stacks.
 309  */
 310
 311 void and_slist_stack(struct state_list_stack **slist_stack)
 312 {
 313         struct sm_state *tmp;
 314         struct smatch_state *tmp_state;
 315         struct state_list *tmp_slist = pop_slist(slist_stack);
 316
 317         FOR_EACH_PTR(tmp_slist, tmp) {
 318                 tmp_state = get_state_stack(*slist_stack, tmp->name,
 319                                             tmp->owner, tmp->sym);
 320                 if (tmp_state && tmp_state != tmp->state) {
 321                         smatch_msg("mutually exclusive 'and' conditions states "
 322                                    "'%s': %s & %s.\n",
 323                                    tmp->name, show_state(tmp_state),
 324                                    show_state(tmp->state));
 325                         tmp->state = merge_states(tmp->name, tmp->owner,
 326                                                   tmp->sym, tmp->state,
 327                                                   tmp_state);
 328                 }
 329                 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
 330                                 tmp->state);
 331
 332         } END_FOR_EACH_PTR(tmp);
 333         del_slist(&tmp_slist);
 334 }
 335
 336 void or_slist_stack(struct state_list_stack **slist_stack)
 337 {
 338         struct state_list *one;
 339         struct state_list *two;
 340         struct state_list *res = NULL;
 341         struct sm_state *tmp;
 342         struct smatch_state *s;
 343
 344         one = pop_slist(slist_stack);
 345         two = pop_slist(slist_stack);
 346
 347         FOR_EACH_PTR(one, tmp) {
 348                 s = get_state_slist(two, tmp->name, tmp->owner, tmp->sym);
 349                 s = merge_states(tmp->name, tmp->owner, tmp->sym,
 350                                  tmp->state, s);
 351                 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
 352         } END_FOR_EACH_PTR(tmp);
 353
 354
 355         FOR_EACH_PTR(two, tmp) {
 356                 s = get_state_slist(one, tmp->name, tmp->owner, tmp->sym);
 357                 s = merge_states(tmp->name, tmp->owner, tmp->sym,
 358                                  tmp->state, s);
 359                 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
 360         } END_FOR_EACH_PTR(tmp);
 361
 362         push_slist(slist_stack, res);
 363
 364         del_slist(&one);
 365         del_slist(&two);
 366 }
 367
 368 struct state_list *get_slist_from_slist_stack(struct slist_stack *stack,
 369                                               const char *name)
 370 {
 371         struct named_slist *tmp;
 372
 373         FOR_EACH_PTR(stack, tmp) {
 374                 if (!strcmp(tmp->name, name))
 375                         return tmp->slist;
 376         } END_FOR_EACH_PTR(tmp);
 377         return NULL;
 378 }
 379
 380 void overwrite_slist(struct state_list *from, struct state_list **to)
 381 {
 382         struct sm_state *tmp;
 383
 384         FOR_EACH_PTR(from, tmp) {
 385                 set_state_slist(to, tmp->name, tmp->owner, tmp->sym, tmp->state);
 386         } END_FOR_EACH_PTR(tmp);
 387 }
 388