2 * sparse/smatch_slist.c
4 * Copyright (C) 2008,2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
13 #include "smatch_slist.h"
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
);
32 void add_history(struct sm_state
*state
)
34 struct state_history
*tmp
;
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
)
56 if (a
->owner
> b
->owner
)
58 if (a
->owner
< b
->owner
)
61 ret
= strcmp(a
->name
, b
->name
);
65 if (!b
->sym
&& a
->sym
)
67 if (!a
->sym
&& b
->sym
)
77 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
81 ret
= cmp_tracker(a
, b
);
85 /* todo: add hook for smatch_extra.c */
86 if (a
->state
> b
->state
)
88 if (a
->state
< b
->state
)
93 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
97 FOR_EACH_PTR(*slist
, tmp
) {
98 if (cmp_sm_states(tmp
, new) < 0)
100 else if (cmp_sm_states(tmp
, new) == 0) {
103 INSERT_CURRENT(new, tmp
);
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
;
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
);
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
;
136 sm_state
->state
= state
;
137 sm_state
->line_history
= NULL
;
138 add_history(sm_state
);
139 sm_state
->my_pools
= NULL
;
140 sm_state
->all_pools
= NULL
;
141 sm_state
->possible
= NULL
;
142 add_ptr_list(&sm_state
->possible
, sm_state
);
146 struct sm_state
*clone_state(struct sm_state
*s
)
148 struct sm_state
*tmp
;
150 tmp
= alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
151 tmp
->my_pools
= clone_stack(s
->my_pools
);
152 tmp
->all_pools
= clone_stack(s
->all_pools
);
153 tmp
->possible
= s
->possible
;
157 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
159 struct sm_state
*tmp
;
161 FOR_EACH_PTR(slist
, tmp
) {
162 if (tmp
->state
== state
)
164 } END_FOR_EACH_PTR(tmp
);
169 static void check_order(struct state_list
*slist
)
171 struct sm_state
*state
;
172 struct sm_state
*last
= NULL
;
175 FOR_EACH_PTR(slist
, state
) {
176 if (last
&& cmp_tracker(state
, last
) <= 0) {
177 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
178 "%s vs %s\n", last
->owner
, state
->owner
,
179 last
->sym
, state
->sym
, last
->name
, state
->name
);
183 } END_FOR_EACH_PTR(state
);
190 struct state_list
*clone_slist(struct state_list
*from_slist
)
192 struct sm_state
*state
;
193 struct sm_state
*tmp
;
194 struct state_list
*to_slist
= NULL
;
196 FOR_EACH_PTR(from_slist
, state
) {
197 tmp
= clone_state(state
);
198 add_ptr_list(&to_slist
, tmp
);
199 } END_FOR_EACH_PTR(state
);
201 check_order(to_slist
);
206 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
208 struct state_list
*slist
;
209 struct state_list_stack
*to_stack
= NULL
;
211 FOR_EACH_PTR(from_stack
, slist
) {
212 push_slist(&to_stack
, slist
);
213 } END_FOR_EACH_PTR(slist
);
217 // FIXME... shouldn't we free some of these state pointers?
218 struct smatch_state
*merge_states(const char *name
, int owner
,
220 struct smatch_state
*state1
,
221 struct smatch_state
*state2
)
223 struct smatch_state
*ret
;
225 if (state1
== state2
)
227 else if (__has_merge_function(owner
))
228 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
229 else if (!state1
|| !state2
)
237 * add_pool() adds a slist to ->pools. If the slist has already been
238 * added earlier then it doesn't get added a second time.
240 static void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
242 struct state_list
*tmp
;
244 FOR_EACH_PTR(*pools
, tmp
) {
247 else if (tmp
== new) {
250 INSERT_CURRENT(new, tmp
);
253 } END_FOR_EACH_PTR(tmp
);
254 add_ptr_list(pools
, new);
257 static void copy_pools(struct sm_state
*to
, struct sm_state
*sm
)
259 struct state_list
*tmp
;
264 FOR_EACH_PTR(sm
->my_pools
, tmp
) {
265 add_pool(&to
->my_pools
, tmp
);
266 } END_FOR_EACH_PTR(tmp
);
268 FOR_EACH_PTR(sm
->all_pools
, tmp
) {
269 add_pool(&to
->all_pools
, tmp
);
270 } END_FOR_EACH_PTR(tmp
);
273 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
275 struct smatch_state
*s
;
276 struct sm_state
*result
;
278 s
= merge_states(one
->name
, one
->owner
, one
->sym
, one
->state
,
279 (two
?two
->state
:NULL
));
280 result
= alloc_state(one
->name
, one
->owner
, one
->sym
, s
);
281 add_possible(result
, one
);
282 add_possible(result
, two
);
283 copy_pools(result
, one
);
284 copy_pools(result
, two
);
287 struct sm_state
*tmp
;
290 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
291 get_lineno(), one
->name
, one
->owner
,
292 show_state(one
->state
), show_state(two
?two
->state
:NULL
),
295 FOR_EACH_PTR(result
->possible
, tmp
) {
299 printf("%s", show_state(tmp
->state
));
300 } END_FOR_EACH_PTR(tmp
);
307 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, const char *name
,
308 int owner
, struct symbol
*sym
)
310 struct sm_state
*state
;
315 FOR_EACH_PTR(slist
, state
) {
316 if (state
->owner
== owner
&& state
->sym
== sym
317 && !strcmp(state
->name
, name
))
319 } END_FOR_EACH_PTR(state
);
323 struct smatch_state
*get_state_slist(struct state_list
*slist
,
324 const char *name
, int owner
,
327 struct sm_state
*state
;
329 state
= get_sm_state_slist(slist
, name
, owner
, sym
);
335 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*state
)
337 struct sm_state
*tmp
;
338 struct sm_state
*new = clone_state(state
); //fixme. why?
340 FOR_EACH_PTR(*slist
, tmp
) {
341 if (cmp_tracker(tmp
, new) < 0)
343 else if (cmp_tracker(tmp
, new) == 0) {
344 tmp
->state
= new->state
;
345 tmp
->my_pools
= new->my_pools
;
346 tmp
->all_pools
= new->all_pools
;
347 tmp
->possible
= new->possible
;
348 __free_sm_state(new);
351 INSERT_CURRENT(new, tmp
);
354 } END_FOR_EACH_PTR(tmp
);
355 add_ptr_list(slist
, new);
358 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
359 struct sm_state
*state
)
361 struct state_list
*slist
;
363 slist
= pop_slist(stack
);
364 overwrite_sm_state(&slist
, state
);
365 push_slist(stack
, slist
);
368 void set_state_slist(struct state_list
**slist
, const char *name
, int owner
,
369 struct symbol
*sym
, struct smatch_state
*state
)
371 struct sm_state
*tmp
;
372 struct sm_state
*new = alloc_state(name
, owner
, sym
, state
);
374 FOR_EACH_PTR(*slist
, tmp
) {
375 if (cmp_tracker(tmp
, new) < 0)
377 else if (cmp_tracker(tmp
, new) == 0) {
379 tmp
->my_pools
= NULL
;
380 tmp
->all_pools
= NULL
;
381 tmp
->possible
= NULL
;
382 add_ptr_list(&tmp
->possible
, tmp
);
383 __free_sm_state(new);
386 INSERT_CURRENT(new, tmp
);
389 } END_FOR_EACH_PTR(tmp
);
390 add_ptr_list(slist
, new);
393 void delete_state_slist(struct state_list
**slist
, const char *name
, int owner
,
396 struct sm_state
*state
;
398 FOR_EACH_PTR(*slist
, state
) {
399 if (state
->owner
== owner
&& state
->sym
== sym
400 && !strcmp(state
->name
, name
)){
401 delete_ptr_list_entry((struct ptr_list
**)slist
,
403 __free_sm_state(state
);
406 } END_FOR_EACH_PTR(state
);
410 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
412 add_ptr_list(list_stack
, slist
);
415 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
417 struct state_list
*slist
;
419 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
420 delete_ptr_list_last((struct ptr_list
**)list_stack
);
424 void del_slist(struct state_list
**slist
)
426 __free_ptr_list((struct ptr_list
**)slist
);
429 void del_slist_stack(struct state_list_stack
**slist_stack
)
431 struct state_list
*slist
;
433 FOR_EACH_PTR(*slist_stack
, slist
) {
434 __free_ptr_list((struct ptr_list
**)&slist
);
435 } END_FOR_EACH_PTR(slist
);
436 __free_ptr_list((struct ptr_list
**)slist_stack
);
440 * set_state_stack() sets the state for the top slist on the stack.
442 void set_state_stack(struct state_list_stack
**stack
, const char *name
,
443 int owner
, struct symbol
*sym
, struct smatch_state
*state
)
445 struct state_list
*slist
;
447 slist
= pop_slist(stack
);
448 set_state_slist(&slist
, name
, owner
, sym
, state
);
449 push_slist(stack
, slist
);
453 * get_state_stack() gets the state for the top slist on the stack.
455 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
456 const char *name
, int owner
,
459 struct state_list
*slist
;
460 struct smatch_state
*ret
;
462 slist
= pop_slist(&stack
);
463 ret
= get_state_slist(slist
, name
, owner
, sym
);
464 push_slist(&stack
, slist
);
469 * We want to find which states have been modified inside a branch.
470 * If you have 2 &merged states they could be different states really
471 * and maybe one or both were modified. We say it is unchanged if
472 * the ->state pointers are the same and they belong to the same pools.
473 * If they have been modified on both sides of a branch to the same thing,
474 * it's still OK to say they are the same, because that means they won't
475 * belong to any pools.
477 static int is_really_same(struct sm_state
*one
, struct sm_state
*two
)
479 struct state_list
*tmp1
;
480 struct state_list
*tmp2
;
482 if (one
->state
!= two
->state
)
485 PREPARE_PTR_LIST(one
->my_pools
, tmp1
);
486 PREPARE_PTR_LIST(two
->my_pools
, tmp2
);
492 } else if (tmp1
== tmp2
) {
499 FINISH_PTR_LIST(tmp2
);
500 FINISH_PTR_LIST(tmp1
);
505 * merge_slist() is called whenever paths merge, such as after
506 * an if statement. It takes the two slists and creates one.
508 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
510 struct sm_state
*to_state
, *state
, *tmp
;
511 struct state_list
*results
= NULL
;
512 struct state_list
*implied_to
= NULL
;
513 struct state_list
*implied_from
= NULL
;
520 /* merging a null and nonnull path gives you only the nonnull path */
525 *to
= clone_slist(slist
);
529 implied_to
= clone_slist(*to
);
530 implied_from
= clone_slist(slist
);
532 PREPARE_PTR_LIST(*to
, to_state
);
533 PREPARE_PTR_LIST(slist
, state
);
535 if (!to_state
&& !state
)
537 if (cmp_tracker(to_state
, state
) < 0) {
538 tmp
= merge_sm_states(to_state
, NULL
);
539 add_pool(&tmp
->my_pools
, implied_to
);
540 add_pool(&tmp
->all_pools
, implied_to
);
541 add_ptr_list(&results
, tmp
);
542 NEXT_PTR_LIST(to_state
);
543 } else if (cmp_tracker(to_state
, state
) == 0) {
544 tmp
= merge_sm_states(to_state
, state
);
545 if (!is_really_same(to_state
, state
)) {
546 add_pool(&tmp
->my_pools
, implied_to
);
547 add_pool(&tmp
->my_pools
, implied_from
);
549 add_pool(&tmp
->all_pools
, implied_to
);
550 add_pool(&tmp
->all_pools
, implied_from
);
551 add_ptr_list(&results
, tmp
);
552 NEXT_PTR_LIST(to_state
);
553 NEXT_PTR_LIST(state
);
555 tmp
= merge_sm_states(state
, NULL
);
556 add_pool(&tmp
->my_pools
, implied_from
);
557 add_pool(&tmp
->all_pools
, implied_from
);
558 add_ptr_list(&results
, tmp
);
559 NEXT_PTR_LIST(state
);
562 FINISH_PTR_LIST(state
);
563 FINISH_PTR_LIST(to_state
);
568 push_slist(&implied_pools
, implied_from
);
569 push_slist(&implied_pools
, implied_to
);
572 static int pool_in_pools(struct state_list_stack
*pools
,
573 struct state_list
*pool
)
575 struct state_list
*tmp
;
577 FOR_EACH_PTR(pools
, tmp
) {
580 } END_FOR_EACH_PTR(tmp
);
584 struct state_list
*clone_states_in_pool(struct state_list
*pool
,
585 struct state_list
*cur_slist
)
587 struct sm_state
*state
;
588 struct sm_state
*cur_state
;
589 struct sm_state
*tmp
;
590 struct state_list
*to_slist
= NULL
;
592 FOR_EACH_PTR(pool
, state
) {
593 cur_state
= get_sm_state_slist(cur_slist
, state
->name
,
594 state
->owner
, state
->sym
);
597 if (is_really_same(state
, cur_state
))
599 if (pool_in_pools(cur_state
->all_pools
, pool
)) {
600 tmp
= clone_state(state
);
601 add_ptr_list(&to_slist
, tmp
);
603 } END_FOR_EACH_PTR(state
);
608 * merge_implied() takes an implied state and another possibly implied state
609 * from another pool. It checks that the second pool is reachable from
610 * cur_slist then merges the two states and returns the result.
612 struct sm_state
*merge_implied(struct sm_state
*one
, struct sm_state
*two
,
613 struct state_list
*pool
,
614 struct state_list
*cur_slist
)
616 struct sm_state
*cur_state
;
618 // fixme: do we not need to check this?
619 cur_state
= get_sm_state_slist(cur_slist
, two
->name
, two
->owner
,
622 return NULL
; /* this can't actually happen */
623 if (!pool_in_pools(cur_state
->all_pools
, pool
))
625 return merge_sm_states(one
, two
);
629 * filter() is used to find what states are the same across
630 * a series of slists.
631 * It takes a **slist and a *filter.
632 * It removes everything from **slist that isn't in *filter.
633 * The reason you would want to do this is if you want to
634 * know what other states are true if one state is true. (smatch_implied).
636 void filter(struct state_list
**slist
, struct state_list
*filter
,
637 struct state_list
*cur_slist
)
639 struct sm_state
*s_one
, *s_two
;
640 struct state_list
*results
= NULL
;
641 struct sm_state
*tmp
;
648 PREPARE_PTR_LIST(*slist
, s_one
);
649 PREPARE_PTR_LIST(filter
, s_two
);
651 if (!s_one
|| !s_two
)
653 if (cmp_tracker(s_one
, s_two
) < 0) {
654 NEXT_PTR_LIST(s_one
);
655 } else if (cmp_tracker(s_one
, s_two
) == 0) {
656 tmp
= merge_implied(s_one
, s_two
, filter
, cur_slist
);
658 add_ptr_list(&results
, tmp
);
659 NEXT_PTR_LIST(s_one
);
660 NEXT_PTR_LIST(s_two
);
662 NEXT_PTR_LIST(s_two
);
665 FINISH_PTR_LIST(s_two
);
666 FINISH_PTR_LIST(s_one
);
673 * and_slist_stack() is basically the same as popping the top two slists,
674 * overwriting the one with the other and pushing it back on the stack.
675 * The difference is that it checks to see that a mutually exclusive
676 * state isn't included in both stacks. If smatch sees something like
677 * "if (a && !a)" it prints a warning.
679 void and_slist_stack(struct state_list_stack
**slist_stack
)
681 struct sm_state
*tmp
;
682 struct smatch_state
*tmp_state
;
683 struct state_list
*tmp_slist
= pop_slist(slist_stack
);
685 FOR_EACH_PTR(tmp_slist
, tmp
) {
686 tmp_state
= get_state_stack(*slist_stack
, tmp
->name
,
687 tmp
->owner
, tmp
->sym
);
688 if (tmp_state
&& tmp_state
!= tmp
->state
) {
689 smatch_msg("mutually exclusive 'and' conditions states "
691 tmp
->name
, show_state(tmp_state
),
692 show_state(tmp
->state
));
694 set_state_stack(slist_stack
, tmp
->name
, tmp
->owner
, tmp
->sym
,
696 } END_FOR_EACH_PTR(tmp
);
697 del_slist(&tmp_slist
);
701 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
702 * It pops the two slists from the top of the stack and merges them
703 * together in a way that preserves the things they have in common
704 * but creates a merged state for most of the rest.
705 * You could have code that had: if (foo || foo) { foo->baz;
706 * It's this function which ensures smatch does the right thing.
708 void or_slist_stack(struct state_list_stack
**slist_stack
)
710 struct state_list
*one
;
711 struct state_list
*two
;
712 struct state_list
*res
= NULL
;
713 struct sm_state
*tmp
;
715 struct sm_state
*new_sm
;
717 one
= pop_slist(slist_stack
);
718 two
= pop_slist(slist_stack
);
720 FOR_EACH_PTR(one
, tmp
) {
721 sm
= get_sm_state_slist(two
, tmp
->name
, tmp
->owner
, tmp
->sym
);
722 new_sm
= merge_sm_states(tmp
, sm
);
723 add_ptr_list(&res
, new_sm
);
724 } END_FOR_EACH_PTR(tmp
);
726 FOR_EACH_PTR(two
, tmp
) {
727 sm
= get_sm_state_slist(one
, tmp
->name
, tmp
->owner
, tmp
->sym
);
728 new_sm
= merge_sm_states(tmp
, sm
);
729 add_ptr_list(&res
, new_sm
);
730 } END_FOR_EACH_PTR(tmp
);
732 push_slist(slist_stack
, res
);
739 * get_slist_from_named_stack() is only used for gotos.
741 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
744 struct named_slist
*tmp
;
746 FOR_EACH_PTR(stack
, tmp
) {
747 if (!strcmp(tmp
->name
, name
))
749 } END_FOR_EACH_PTR(tmp
);
753 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
755 struct sm_state
*tmp
;
757 FOR_EACH_PTR(from
, tmp
) {
758 overwrite_sm_state(to
, tmp
);
759 } END_FOR_EACH_PTR(tmp
);