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