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 void add_history(struct sm_state *state)
  20 {
  21         struct state_history *tmp;
  22
  23         if (!state)
  24                 return;
  25         tmp = malloc(sizeof(*tmp));
  26         tmp->loc = get_lineno();
  27         add_ptr_list(&state->line_history, tmp);
  28 }
  29
  30 struct sm_state *alloc_state(const char *name, int owner,
  31                                  struct symbol *sym, struct smatch_state *state)
  32 {
  33         struct sm_state *sm_state = __alloc_sm_state(0);
  34
  35         sm_state->name = (char *)name;
  36         sm_state->owner = owner;
  37         sm_state->sym = sym;
  38         sm_state->state = state;
  39         sm_state->line_history = NULL;
  40         sm_state->path_history = NULL;
  41         add_history(sm_state);
  42         return sm_state;
  43 }
  44
  45 struct sm_state *clone_state(struct sm_state *s)
  46 {
  47         return alloc_state(s->name, s->owner, s->sym, s->state);
  48 }
  49
  50 struct state_list *clone_slist(struct state_list *from_slist)
  51 {
  52         struct sm_state *state;
  53         struct sm_state *tmp;
  54         struct state_list *to_slist = NULL;
  55
  56         FOR_EACH_PTR(from_slist, state) {
  57                 tmp = clone_state(state);
  58                 add_ptr_list(&to_slist, tmp);
  59         } END_FOR_EACH_PTR(state);
  60         return to_slist;
  61 }
  62
  63 struct smatch_state *merge_states(const char *name, int owner,
  64                                   struct symbol *sym,
  65                                   struct smatch_state *state1,
  66                                   struct smatch_state *state2)
  67 {
  68         struct smatch_state *ret;
  69
  70         if (state1 == state2)
  71                 ret = state1;
  72         else if (__has_merge_function(owner))
  73                 ret = __client_merge_function(owner, name, sym, state1, state2);
  74         else
  75                 ret = &undefined;
  76
  77         SM_DEBUG("%d merge name='%s' owner=%d: %s + %s => %s\n",
  78                  get_lineno(), name, owner, (state1?state1->name:NULL),
  79                  (state2?state2->name:NULL), ret->name);
  80
  81         return ret;
  82 }
  83
  84 void merge_state_slist(struct state_list **slist, const char *name, int owner,
  85                        struct symbol *sym, struct smatch_state *state)
  86 {
  87         struct sm_state *tmp;
  88         struct smatch_state *s;
  89
  90         FOR_EACH_PTR(*slist, tmp) {
  91                 if (tmp->owner == owner && tmp->sym == sym
  92                     && !strcmp(tmp->name, name)){
  93                         s = merge_states(name, owner, sym, tmp->state, state);
  94                         if (tmp->state != s) {
  95                                 add_history(tmp);
  96                         }
  97                         tmp->state = s;
  98                         return;
  99                 }
 100         } END_FOR_EACH_PTR(tmp);
 101         tmp = alloc_state(name, owner, sym, state);
 102         add_state_slist(slist, tmp);
 103 }
 104
 105 struct smatch_state *get_state_slist(struct state_list *slist, const char *name, int owner,
 106                     struct symbol *sym)
 107 {
 108         struct sm_state *state;
 109
 110         if (!name)
 111                 return NULL;
 112
 113         FOR_EACH_PTR(slist, state) {
 114                 if (state->owner == owner && state->sym == sym
 115                     && !strcmp(state->name, name))
 116                         return state->state;
 117         } END_FOR_EACH_PTR(state);
 118         return NULL;
 119 }
 120
 121 void add_state_slist(struct state_list **slist, struct sm_state *state)
 122 {
 123         add_ptr_list(slist, state);
 124 }
 125
 126 void set_state_slist(struct state_list **slist, const char *name, int owner,
 127                      struct symbol *sym, struct smatch_state *state)
 128 {
 129         struct sm_state *tmp;
 130
 131         FOR_EACH_PTR(*slist, tmp) {
 132                 if (tmp->owner == owner && tmp->sym == sym
 133                     && !strcmp(tmp->name, name)){
 134                         tmp->state = state;
 135                         return;
 136                 }
 137         } END_FOR_EACH_PTR(tmp);
 138         tmp = alloc_state(name, owner, sym, state);
 139         add_state_slist(slist, tmp);
 140 }
 141
 142 void delete_state_slist(struct state_list **slist, const char *name, int owner,
 143                         struct symbol *sym)
 144 {
 145         struct sm_state *state;
 146
 147         FOR_EACH_PTR(*slist, state) {
 148                 if (state->owner == owner && state->sym == sym
 149                     && !strcmp(state->name, name)){
 150                         delete_ptr_list_entry((struct ptr_list **)slist,
 151                                               state, 1);
 152                         __free_sm_state(state);
 153                         return;
 154                 }
 155         } END_FOR_EACH_PTR(state);
 156 }
 157
 158
 159 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
 160 {
 161         add_ptr_list(list_stack, slist);
 162 }
 163
 164 struct state_list *pop_slist(struct state_list_stack **list_stack)
 165 {
 166         struct state_list *slist;
 167
 168         slist = last_ptr_list((struct ptr_list *)*list_stack);
 169         delete_ptr_list_last((struct ptr_list **)list_stack);
 170         return slist;
 171 }
 172
 173 void del_slist(struct state_list **slist)
 174 {
 175         __free_ptr_list((struct ptr_list **)slist);
 176 }
 177
 178 void del_slist_stack(struct state_list_stack **slist_stack)
 179 {
 180         struct state_list *slist;
 181
 182         FOR_EACH_PTR(*slist_stack, slist) {
 183                 __free_ptr_list((struct ptr_list **)&slist);
 184         } END_FOR_EACH_PTR(slist);
 185         __free_ptr_list((struct ptr_list **)slist_stack);
 186 }
 187
 188 /*
 189  * set_state_stack() sets the state for the top slist on the stack.
 190  */
 191 void set_state_stack(struct state_list_stack **stack, const char *name,
 192                      int owner, struct symbol *sym, struct smatch_state *state)
 193 {
 194         struct state_list *slist;
 195
 196         slist = pop_slist(stack);
 197         set_state_slist(&slist, name, owner, sym, state);
 198         push_slist(stack, slist);
 199 }
 200
 201 /*
 202  * get_state_stack() gets the state for the top slist on the stack.
 203  */
 204 struct smatch_state *get_state_stack(struct state_list_stack *stack, const char *name,
 205                     int owner, struct symbol *sym)
 206 {
 207         struct state_list *slist;
 208         struct smatch_state *ret;
 209
 210         slist = pop_slist(&stack);
 211         ret = get_state_slist(slist, name, owner, sym);
 212         push_slist(&stack, slist);
 213         return ret;
 214 }
 215
 216 void merge_state_stack(struct state_list_stack **stack, const char *name,
 217                        int owner, struct symbol *sym, struct smatch_state *state)
 218 {
 219         struct state_list *slist;
 220
 221         slist = pop_slist(stack);
 222         merge_state_slist(&slist, name, owner, sym, state);
 223         push_slist(stack, slist);
 224 }
 225
 226 void merge_slist(struct state_list **to, struct state_list *slist)
 227 {
 228         struct sm_state *state;
 229
 230         if (!slist) {
 231                 return;
 232         }
 233
 234         FOR_EACH_PTR(slist, state) {
 235                 merge_state_slist(to, state->name, state->owner,
 236                                   state->sym, state->state);
 237         } END_FOR_EACH_PTR(state);
 238
 239         FOR_EACH_PTR(*to, state) {
 240                 if (!get_state_slist(slist, state->name, state->owner,
 241                                     state->sym)) {
 242                         merge_state_slist(to, state->name, state->owner,
 243                                           state->sym, NULL);
 244                 }
 245         } END_FOR_EACH_PTR(state);
 246 }
 247
 248 /*
 249  * and_slist_stack() ands an slist with the top slist in an slist stack.
 250  */
 251
 252 void and_slist_stack(struct state_list_stack **slist_stack,
 253                      struct state_list *tmp_slist)
 254 {
 255         struct sm_state *tmp;
 256         struct smatch_state *tmp_state;
 257
 258         FOR_EACH_PTR(tmp_slist, tmp) {
 259                 tmp_state = get_state_stack(*slist_stack, tmp->name,
 260                                             tmp->owner, tmp->sym);
 261                 if (tmp_state && tmp_state != &undefined && tmp_state != tmp->state) {
 262                         smatch_msg("wierdness merging 'and' conditions states '%s': %s & %s.\n",
 263                                    tmp->name, (tmp_state?tmp_state->name:NULL),
 264                                    (tmp->state?tmp->state->name:NULL));
 265                         tmp->state = merge_states(tmp->name, tmp->owner,
 266                                                   tmp->sym, tmp->state,
 267                                                   tmp_state);
 268                 }
 269
 270                 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
 271                                 tmp->state);
 272
 273         } END_FOR_EACH_PTR(tmp);
 274         del_slist(&tmp_slist);
 275 }
 276
 277 void or_slist_stack(struct state_list_stack **slist_stack)
 278 {
 279         struct state_list *one;
 280         struct state_list *two;
 281         struct state_list *res = NULL;
 282         struct sm_state *tmp;
 283         struct smatch_state *s;
 284
 285         one = pop_slist(slist_stack);
 286         two = pop_slist(slist_stack);
 287
 288         FOR_EACH_PTR(one, tmp) {
 289                 s = get_state_slist(two, tmp->name, tmp->owner, tmp->sym);
 290                 s = merge_states(tmp->name, tmp->owner, tmp->sym,
 291                                  tmp->state, s);
 292                 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
 293         } END_FOR_EACH_PTR(tmp);
 294
 295         push_slist(slist_stack, res);
 296
 297         del_slist(&one);
 298         del_slist(&two);
 299 }
 300
 301 struct state_list *get_slist_from_slist_stack(struct slist_stack *stack,
 302                                               const char *name)
 303 {
 304         struct named_slist *tmp;
 305
 306         FOR_EACH_PTR(stack, tmp) {
 307                 if (!strcmp(tmp->name, name))
 308                         return tmp->slist;
 309         } END_FOR_EACH_PTR(tmp);
 310         return NULL;
 311 }
 312
 313 void overwrite_slist(struct state_list *from, struct state_list **to)
 314 {
 315         struct sm_state *tmp;
 316
 317         FOR_EACH_PTR(from, tmp) {
 318                 set_state_slist(to, tmp->name, tmp->owner, tmp->sym, tmp->state);
 319         } END_FOR_EACH_PTR(tmp);
 320 }
 321