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, show_state(state1),
  79                  show_state(state2), show_state(ret));
  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,
 205                                      const char *name, int owner,
 206                                      struct symbol *sym)
 207 {
 208         struct state_list *slist;
 209         struct smatch_state *ret;
 210
 211         slist = pop_slist(&stack);
 212         ret = get_state_slist(slist, name, owner, sym);
 213         push_slist(&stack, slist);
 214         return ret;
 215 }
 216
 217 void merge_state_stack(struct state_list_stack **stack, const char *name,
 218                        int owner, struct symbol *sym,
 219                        struct smatch_state *state)
 220 {
 221         struct state_list *slist;
 222
 223         slist = pop_slist(stack);
 224         merge_state_slist(&slist, name, owner, sym, state);
 225         push_slist(stack, slist);
 226 }
 227
 228 void merge_slist(struct state_list **to, struct state_list *slist)
 229 {
 230         struct sm_state *state;
 231
 232         if (!slist) {
 233                 return;
 234         }
 235
 236         FOR_EACH_PTR(slist, state) {
 237                 merge_state_slist(to, state->name, state->owner,
 238                                   state->sym, state->state);
 239         } END_FOR_EACH_PTR(state);
 240
 241         FOR_EACH_PTR(*to, state) {
 242                 if (!get_state_slist(slist, state->name, state->owner,
 243                                     state->sym)) {
 244                         merge_state_slist(to, state->name, state->owner,
 245                                           state->sym, NULL);
 246                 }
 247         } END_FOR_EACH_PTR(state);
 248 }
 249
 250 /*
 251  * and_slist_stack() ands an slist with the top slist in an slist stack.
 252  */
 253
 254 void and_slist_stack(struct state_list_stack **slist_stack,
 255                      struct state_list *tmp_slist)
 256 {
 257         struct sm_state *tmp;
 258         struct smatch_state *tmp_state;
 259
 260         FOR_EACH_PTR(tmp_slist, tmp) {
 261                 tmp_state = get_state_stack(*slist_stack, tmp->name,
 262                                             tmp->owner, tmp->sym);
 263                 if (tmp_state && tmp_state != &undefined && tmp_state != tmp->state) {
 264                         smatch_msg("wierdness merging 'and' conditions states '%s': %s & %s.\n",
 265                                    tmp->name, show_state(tmp_state),
 266                                    show_state(tmp->state));
 267                         tmp->state = merge_states(tmp->name, tmp->owner,
 268                                                   tmp->sym, tmp->state,
 269                                                   tmp_state);
 270                 }
 271
 272                 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
 273                                 tmp->state);
 274
 275         } END_FOR_EACH_PTR(tmp);
 276         del_slist(&tmp_slist);
 277 }
 278
 279 void or_slist_stack(struct state_list_stack **slist_stack)
 280 {
 281         struct state_list *one;
 282         struct state_list *two;
 283         struct state_list *res = NULL;
 284         struct sm_state *tmp;
 285         struct smatch_state *s;
 286
 287         one = pop_slist(slist_stack);
 288         two = pop_slist(slist_stack);
 289
 290         FOR_EACH_PTR(one, tmp) {
 291                 s = get_state_slist(two, tmp->name, tmp->owner, tmp->sym);
 292                 s = merge_states(tmp->name, tmp->owner, tmp->sym,
 293                                  tmp->state, s);
 294                 set_state_slist(&res, tmp->name, tmp->owner, tmp->sym, s);
 295         } END_FOR_EACH_PTR(tmp);
 296
 297         push_slist(slist_stack, res);
 298
 299         del_slist(&one);
 300         del_slist(&two);
 301 }
 302
 303 struct state_list *get_slist_from_slist_stack(struct slist_stack *stack,
 304                                               const char *name)
 305 {
 306         struct named_slist *tmp;
 307
 308         FOR_EACH_PTR(stack, tmp) {
 309                 if (!strcmp(tmp->name, name))
 310                         return tmp->slist;
 311         } END_FOR_EACH_PTR(tmp);
 312         return NULL;
 313 }
 314
 315 void overwrite_slist(struct state_list *from, struct state_list **to)
 316 {
 317         struct sm_state *tmp;
 318
 319         FOR_EACH_PTR(from, tmp) {
 320                 set_state_slist(to, tmp->name, tmp->owner, tmp->sym, tmp->state);
 321         } END_FOR_EACH_PTR(tmp);
 322 }
 323