Don't set the implied state to &merged.
[smatch.git] / smatch_slist.c
blobdecf1ce0b41f5184ff5dd399a894bd9e52523f35
1 /*
2 * sparse/smatch_slist.c
4 * Copyright (C) 2008,2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include "smatch.h"
13 #include "smatch_slist.h"
15 #undef CHECKORDER
17 ALLOCATOR(sm_state, "smatch state");
18 ALLOCATOR(named_slist, "named slist");
20 void __print_slist(struct state_list *slist)
22 struct sm_state *state;
24 printf("dumping slist at %d\n", get_lineno());
25 FOR_EACH_PTR(slist, state) {
26 printf("%d '%s'=%s\n", state->owner, state->name,
27 show_state(state->state));
28 } END_FOR_EACH_PTR(state);
29 printf("---\n");
32 void add_history(struct sm_state *state)
34 struct state_history *tmp;
36 if (!state)
37 return;
38 tmp = malloc(sizeof(*tmp));
39 tmp->loc = get_lineno();
40 add_ptr_list(&state->line_history, tmp);
44 /* NULL states go at the end to simplify merge_slist */
45 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
47 int ret;
49 if (!a && !b)
50 return 0;
51 if (!b)
52 return -1;
53 if (!a)
54 return 1;
56 if (a->owner > b->owner)
57 return -1;
58 if (a->owner < b->owner)
59 return 1;
61 ret = strcmp(a->name, b->name);
62 if (ret)
63 return ret;
65 if (!b->sym && a->sym)
66 return -1;
67 if (!a->sym && b->sym)
68 return 1;
69 if (a->sym > b->sym)
70 return -1;
71 if (a->sym < b->sym)
72 return 1;
74 return 0;
77 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b)
79 int ret;
81 ret = cmp_tracker(a, b);
82 if (ret)
83 return ret;
85 /* todo: add hook for smatch_extra.c */
86 if (a->state > b->state)
87 return -1;
88 if (a->state < b->state)
89 return 1;
90 return 0;
93 void add_sm_state_slist(struct state_list **slist, struct sm_state *new)
95 struct sm_state *tmp;
97 FOR_EACH_PTR(*slist, tmp) {
98 if (cmp_sm_states(tmp, new) < 0)
99 continue;
100 else if (cmp_sm_states(tmp, new) == 0) {
101 return;
102 } else {
103 INSERT_CURRENT(new, tmp);
104 return;
106 } END_FOR_EACH_PTR(tmp);
107 add_ptr_list(slist, new);
110 static void add_possible(struct sm_state *sm, struct sm_state *new)
112 struct sm_state *tmp;
115 if (!new) {
116 struct smatch_state *s;
118 s = merge_states(sm->name, sm->owner, sm->sym, sm->state, NULL);
119 tmp = alloc_state(sm->name, sm->owner, sm->sym, s);
120 add_sm_state_slist(&sm->possible, tmp);
121 return;
123 FOR_EACH_PTR(new->possible, tmp) {
124 add_sm_state_slist(&sm->possible, tmp);
125 } END_FOR_EACH_PTR(tmp);
128 struct sm_state *alloc_state(const char *name, int owner,
129 struct symbol *sym, struct smatch_state *state)
131 struct sm_state *sm_state = __alloc_sm_state(0);
133 sm_state->name = (char *)name;
134 sm_state->owner = owner;
135 sm_state->sym = sym;
136 sm_state->state = state;
137 sm_state->line_history = NULL;
138 add_history(sm_state);
139 sm_state->pools = NULL;
140 sm_state->possible = NULL;
141 add_ptr_list(&sm_state->possible, sm_state);
142 return sm_state;
145 struct sm_state *clone_state(struct sm_state *s)
147 struct sm_state *tmp;
149 tmp = alloc_state(s->name, s->owner, s->sym, s->state);
150 tmp->pools = clone_stack(s->pools);
151 tmp->possible = s->possible;
152 return tmp;
155 int slist_has_state(struct state_list *slist, struct smatch_state *state)
157 struct sm_state *tmp;
159 FOR_EACH_PTR(slist, tmp) {
160 if (tmp->state == state)
161 return 1;
162 } END_FOR_EACH_PTR(tmp);
163 return 0;
166 #ifdef CHECKORDER
167 static void check_order(struct state_list *slist)
169 struct sm_state *state;
170 struct sm_state *last = NULL;
171 int printed = 0;
173 FOR_EACH_PTR(slist, state) {
174 if (last && cmp_tracker(state, last) <= 0) {
175 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
176 "%s vs %s\n", last->owner, state->owner,
177 last->sym, state->sym, last->name, state->name);
178 printed = 1;
180 last = state;
181 } END_FOR_EACH_PTR(state);
183 if (printed)
184 printf("======\n");
186 #endif
188 struct state_list *clone_slist(struct state_list *from_slist)
190 struct sm_state *state;
191 struct sm_state *tmp;
192 struct state_list *to_slist = NULL;
194 FOR_EACH_PTR(from_slist, state) {
195 tmp = clone_state(state);
196 add_ptr_list(&to_slist, tmp);
197 } END_FOR_EACH_PTR(state);
198 #ifdef CHECKORDER
199 check_order(to_slist);
200 #endif
201 return to_slist;
204 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
206 struct state_list *slist;
207 struct state_list_stack *to_stack = NULL;
209 FOR_EACH_PTR(from_stack, slist) {
210 push_slist(&to_stack, slist);
211 } END_FOR_EACH_PTR(slist);
212 return to_stack;
215 // FIXME... shouldn't we free some of these state pointers?
216 struct smatch_state *merge_states(const char *name, int owner,
217 struct symbol *sym,
218 struct smatch_state *state1,
219 struct smatch_state *state2)
221 struct smatch_state *ret;
223 if (state1 == state2)
224 ret = state1;
225 else if (__has_merge_function(owner))
226 ret = __client_merge_function(owner, name, sym, state1, state2);
227 else if (!state1 || !state2)
228 ret = &undefined;
229 else
230 ret = &merged;
231 return ret;
235 * add_pool() adds a slist to ->pools. If the slist has already been
236 * added earlier then it doesn't get added a second time.
238 static void add_pool(struct sm_state *to, struct state_list *new)
240 struct state_list *tmp;
242 FOR_EACH_PTR(to->pools, tmp) {
243 if (tmp < new)
244 continue;
245 else if (tmp == new) {
246 return;
247 } else {
248 INSERT_CURRENT(new, tmp);
249 return;
251 } END_FOR_EACH_PTR(tmp);
252 add_ptr_list(&to->pools, new);
255 static void copy_pools(struct sm_state *to, struct sm_state *sm)
257 struct state_list *tmp;
259 if (!sm)
260 return;
262 FOR_EACH_PTR(sm->pools, tmp) {
263 add_pool(to, tmp);
264 } END_FOR_EACH_PTR(tmp);
267 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
269 struct smatch_state *s;
270 struct sm_state *result;
272 s = merge_states(one->name, one->owner, one->sym, one->state,
273 (two?two->state:NULL));
274 result = alloc_state(one->name, one->owner, one->sym, s);
275 add_possible(result, one);
276 add_possible(result, two);
277 copy_pools(result, one);
278 copy_pools(result, two);
280 if (debug_states) {
281 struct sm_state *tmp;
282 int i = 0;
284 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
285 get_lineno(), one->name, one->owner,
286 show_state(one->state), show_state(two?two->state:NULL),
287 show_state(s));
289 FOR_EACH_PTR(result->possible, tmp) {
290 if (i++) {
291 printf(", ");
293 printf("%s", show_state(tmp->state));
294 } END_FOR_EACH_PTR(tmp);
295 printf(")\n");
298 return result;
301 struct sm_state *get_sm_state_slist(struct state_list *slist, const char *name,
302 int owner, struct symbol *sym)
304 struct sm_state *state;
306 if (!name)
307 return NULL;
309 FOR_EACH_PTR(slist, state) {
310 if (state->owner == owner && state->sym == sym
311 && !strcmp(state->name, name))
312 return state;
313 } END_FOR_EACH_PTR(state);
314 return NULL;
317 struct smatch_state *get_state_slist(struct state_list *slist,
318 const char *name, int owner,
319 struct symbol *sym)
321 struct sm_state *state;
323 state = get_sm_state_slist(slist, name, owner, sym);
324 if (state)
325 return state->state;
326 return NULL;
329 static void overwrite_sm_state(struct state_list **slist,
330 struct sm_state *state)
332 struct sm_state *tmp;
333 struct sm_state *new = clone_state(state); //fixme. why?
335 FOR_EACH_PTR(*slist, tmp) {
336 if (cmp_tracker(tmp, new) < 0)
337 continue;
338 else if (cmp_tracker(tmp, new) == 0) {
339 tmp->state = new->state;
340 tmp->pools = new->pools;
341 tmp->possible = new->possible;
342 __free_sm_state(new);
343 return;
344 } else {
345 INSERT_CURRENT(new, tmp);
346 return;
348 } END_FOR_EACH_PTR(tmp);
349 add_ptr_list(slist, new);
352 void set_state_slist(struct state_list **slist, const char *name, int owner,
353 struct symbol *sym, struct smatch_state *state)
355 struct sm_state *tmp;
356 struct sm_state *new = alloc_state(name, owner, sym, state);
358 FOR_EACH_PTR(*slist, tmp) {
359 if (cmp_tracker(tmp, new) < 0)
360 continue;
361 else if (cmp_tracker(tmp, new) == 0) {
362 tmp->state = state;
363 tmp->pools = NULL;
364 tmp->possible = NULL;
365 add_ptr_list(&tmp->possible, tmp);
366 __free_sm_state(new);
367 return;
368 } else {
369 INSERT_CURRENT(new, tmp);
370 return;
372 } END_FOR_EACH_PTR(tmp);
373 add_ptr_list(slist, new);
376 void delete_state_slist(struct state_list **slist, const char *name, int owner,
377 struct symbol *sym)
379 struct sm_state *state;
381 FOR_EACH_PTR(*slist, state) {
382 if (state->owner == owner && state->sym == sym
383 && !strcmp(state->name, name)){
384 delete_ptr_list_entry((struct ptr_list **)slist,
385 state, 1);
386 __free_sm_state(state);
387 return;
389 } END_FOR_EACH_PTR(state);
393 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
395 add_ptr_list(list_stack, slist);
398 struct state_list *pop_slist(struct state_list_stack **list_stack)
400 struct state_list *slist;
402 slist = last_ptr_list((struct ptr_list *)*list_stack);
403 delete_ptr_list_last((struct ptr_list **)list_stack);
404 return slist;
407 void del_slist(struct state_list **slist)
409 __free_ptr_list((struct ptr_list **)slist);
412 void del_slist_stack(struct state_list_stack **slist_stack)
414 struct state_list *slist;
416 FOR_EACH_PTR(*slist_stack, slist) {
417 __free_ptr_list((struct ptr_list **)&slist);
418 } END_FOR_EACH_PTR(slist);
419 __free_ptr_list((struct ptr_list **)slist_stack);
423 * set_state_stack() sets the state for the top slist on the stack.
425 void set_state_stack(struct state_list_stack **stack, const char *name,
426 int owner, struct symbol *sym, struct smatch_state *state)
428 struct state_list *slist;
430 slist = pop_slist(stack);
431 set_state_slist(&slist, name, owner, sym, state);
432 push_slist(stack, slist);
436 * get_state_stack() gets the state for the top slist on the stack.
438 struct smatch_state *get_state_stack(struct state_list_stack *stack,
439 const char *name, int owner,
440 struct symbol *sym)
442 struct state_list *slist;
443 struct smatch_state *ret;
445 slist = pop_slist(&stack);
446 ret = get_state_slist(slist, name, owner, sym);
447 push_slist(&stack, slist);
448 return ret;
452 * merge_slist() is called whenever paths merge, such as after
453 * an if statement. It takes the two slists and creates one.
455 void merge_slist(struct state_list **to, struct state_list *slist)
457 struct sm_state *to_state, *state, *tmp;
458 struct state_list *results = NULL;
459 struct state_list *implied_to = NULL;
460 struct state_list *implied_from = NULL;
462 #ifdef CHECKORDER
463 check_order(*to);
464 check_order(slist);
465 #endif
467 /* merging a null and nonnull path gives you only the nonnull path */
468 if (!slist) {
469 return;
471 if (!*to) {
472 *to = clone_slist(slist);
473 return;
476 implied_to = clone_slist(*to);
477 implied_from = clone_slist(slist);
479 PREPARE_PTR_LIST(*to, to_state);
480 PREPARE_PTR_LIST(slist, state);
481 for (;;) {
482 if (!to_state && !state)
483 break;
484 if (cmp_tracker(to_state, state) < 0) {
485 tmp = merge_sm_states(to_state, NULL);
486 add_pool(tmp, implied_to);
487 add_ptr_list(&results, tmp);
488 NEXT_PTR_LIST(to_state);
489 } else if (cmp_tracker(to_state, state) == 0) {
490 tmp = merge_sm_states(to_state, state);
491 add_pool(tmp, implied_to);
492 add_pool(tmp, implied_from);
493 add_ptr_list(&results, tmp);
494 NEXT_PTR_LIST(to_state);
495 NEXT_PTR_LIST(state);
496 } else {
497 tmp = merge_sm_states(state, NULL);
498 add_pool(tmp, implied_from);
499 add_ptr_list(&results, tmp);
500 NEXT_PTR_LIST(state);
503 FINISH_PTR_LIST(state);
504 FINISH_PTR_LIST(to_state);
506 del_slist(to);
507 *to = results;
509 push_slist(&implied_pools, implied_from);
510 push_slist(&implied_pools, implied_to);
514 * is_currently_in_pool() is used because we remove states from pools.
515 * When set_state() is called then we set ->pools to NULL, but on
516 * other paths the state is still a member of those pools.
517 * Confusing huh?
518 * if (foo) {
519 * bar = 1;
520 * a = malloc();
522 * if (!a)
523 * return;
524 * if (bar)
525 * a->b = x;
527 static int is_currently_in_pool(struct sm_state *sm, struct state_list *pool,
528 struct state_list *cur_slist)
530 struct sm_state *cur_state;
531 struct state_list *tmp;
533 cur_state = get_sm_state_slist(cur_slist, sm->name, sm->owner, sm->sym);
534 if (!cur_state)
535 return 0;
537 FOR_EACH_PTR(cur_state->pools, tmp) {
538 if (tmp == pool)
539 return 1;
540 } END_FOR_EACH_PTR(tmp);
541 return 0;
544 struct state_list *clone_states_in_pool(struct state_list *pool,
545 struct state_list *cur_slist)
547 struct sm_state *state;
548 struct sm_state *tmp;
549 struct state_list *to_slist = NULL;
551 FOR_EACH_PTR(pool, state) {
552 if (state->state == &merged)
553 continue;
554 if (is_currently_in_pool(state, pool, cur_slist)) {
555 tmp = clone_state(state);
556 add_ptr_list(&to_slist, tmp);
558 } END_FOR_EACH_PTR(state);
559 #ifdef CHECKORDER
560 check_order(to_slist);
561 #endif
562 return to_slist;
566 * filter() is used to find what states are the same across
567 * a series of slists.
568 * It takes a **slist and a *filter.
569 * It removes everything from **slist that isn't in *filter.
570 * The reason you would want to do this is if you want to
571 * know what other states are true if one state is true. (smatch_implied).
573 void filter(struct state_list **slist, struct state_list *filter,
574 struct state_list *cur_slist)
576 struct sm_state *s_one, *s_two;
577 struct state_list *results = NULL;
579 #ifdef CHECKORDER
580 check_order(*slist);
581 check_order(filter);
582 #endif
584 PREPARE_PTR_LIST(*slist, s_one);
585 PREPARE_PTR_LIST(filter, s_two);
586 for (;;) {
587 if (!s_one || !s_two)
588 break;
589 if (cmp_tracker(s_one, s_two) < 0) {
590 NEXT_PTR_LIST(s_one);
591 } else if (cmp_tracker(s_one, s_two) == 0) {
592 /* todo. pointer comparison works fine for most things
593 except smatch_extra. we may need a hook here. */
594 if (s_one->state == s_two->state &&
595 is_currently_in_pool(s_two, filter, cur_slist)
596 && s_one->state != &merged) {
597 add_ptr_list(&results, s_one);
599 NEXT_PTR_LIST(s_one);
600 NEXT_PTR_LIST(s_two);
601 } else {
602 NEXT_PTR_LIST(s_two);
605 FINISH_PTR_LIST(s_two);
606 FINISH_PTR_LIST(s_one);
608 del_slist(slist);
609 *slist = results;
613 * and_slist_stack() is basically the same as popping the top two slists,
614 * overwriting the one with the other and pushing it back on the stack.
615 * The difference is that it checks to see that a mutually exclusive
616 * state isn't included in both stacks. If smatch sees something like
617 * "if (a && !a)" it prints a warning.
619 void and_slist_stack(struct state_list_stack **slist_stack)
621 struct sm_state *tmp;
622 struct smatch_state *tmp_state;
623 struct state_list *tmp_slist = pop_slist(slist_stack);
625 FOR_EACH_PTR(tmp_slist, tmp) {
626 tmp_state = get_state_stack(*slist_stack, tmp->name,
627 tmp->owner, tmp->sym);
628 if (tmp_state && tmp_state != tmp->state) {
629 struct smatch_state *s;
631 s = merge_states(tmp->name, tmp->owner, tmp->sym,
632 tmp->state, tmp_state);
633 smatch_msg("mutually exclusive 'and' conditions states "
634 "'%s': %s + %s => %s",
635 tmp->name, show_state(tmp_state),
636 show_state(tmp->state), show_state(s));
637 tmp->state = s;
640 set_state_stack(slist_stack, tmp->name, tmp->owner, tmp->sym,
641 tmp->state);
642 } END_FOR_EACH_PTR(tmp);
643 del_slist(&tmp_slist);
647 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
648 * It pops the two slists from the top of the stack and merges them
649 * together in a way that preserves the things they have in common
650 * but creates a merged state for most of the rest.
651 * You could have code that had: if (foo || foo) { foo->baz;
652 * It's this function which ensures smatch does the right thing.
654 void or_slist_stack(struct state_list_stack **slist_stack)
656 struct state_list *one;
657 struct state_list *two;
658 struct state_list *res = NULL;
659 struct sm_state *tmp;
660 struct sm_state *sm;
661 struct sm_state *new_sm;
663 one = pop_slist(slist_stack);
664 two = pop_slist(slist_stack);
666 FOR_EACH_PTR(one, tmp) {
667 sm = get_sm_state_slist(two, tmp->name, tmp->owner, tmp->sym);
668 new_sm = merge_sm_states(tmp, sm);
669 add_ptr_list(&res, new_sm);
670 } END_FOR_EACH_PTR(tmp);
672 FOR_EACH_PTR(two, tmp) {
673 sm = get_sm_state_slist(one, tmp->name, tmp->owner, tmp->sym);
674 new_sm = merge_sm_states(tmp, sm);
675 add_ptr_list(&res, new_sm);
676 } END_FOR_EACH_PTR(tmp);
678 push_slist(slist_stack, res);
680 del_slist(&one);
681 del_slist(&two);
685 * get_slist_from_named_stack() is only used for gotos.
687 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
688 const char *name)
690 struct named_slist *tmp;
692 FOR_EACH_PTR(stack, tmp) {
693 if (!strcmp(tmp->name, name))
694 return &tmp->slist;
695 } END_FOR_EACH_PTR(tmp);
696 return NULL;
699 void overwrite_slist(struct state_list *from, struct state_list **to)
701 struct sm_state *tmp;
703 FOR_EACH_PTR(from, tmp) {
704 overwrite_sm_state(to, tmp);
705 } END_FOR_EACH_PTR(tmp);