2 * Copyright (C) 2006 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * You have a lists of states. kernel = locked, foo = NULL, ...
20 * When you hit an if {} else {} statement then you swap the list
21 * of states for a different list of states. The lists are stored
24 * At the beginning of this file there are list of the stacks that
25 * we use. Each function in this file does something to one of
28 * So the smatch_flow.c understands code but it doesn't understand states.
29 * smatch_flow calls functions in this file. This file calls functions
30 * in smatch_slist.c which just has boring generic plumbing for handling
31 * state lists. But really it's this file where all the magic happens.
37 #include "smatch_slist.h"
38 #include "smatch_extra.h"
40 struct smatch_state undefined
= { .name
= "undefined" };
41 struct smatch_state ghost
= { .name
= "ghost" };
42 struct smatch_state merged
= { .name
= "merged" };
43 struct smatch_state true_state
= { .name
= "true" };
44 struct smatch_state false_state
= { .name
= "false" };
46 static struct stree
*cur_stree
; /* current states */
48 static struct stree_stack
*true_stack
; /* states after a t/f branch */
49 static struct stree_stack
*false_stack
;
50 static struct stree_stack
*pre_cond_stack
; /* states before a t/f branch */
52 static struct stree_stack
*cond_true_stack
; /* states affected by a branch */
53 static struct stree_stack
*cond_false_stack
;
55 static struct stree_stack
*fake_cur_stree_stack
;
58 static struct stree_stack
*break_stack
;
59 static struct stree_stack
*switch_stack
;
60 static struct range_list_stack
*remaining_cases
;
61 static struct stree_stack
*default_stack
;
62 static struct stree_stack
*continue_stack
;
64 static struct named_stree_stack
*goto_stack
;
66 static struct ptr_list
*backup
;
70 void __print_cur_stree(void)
72 __print_stree(cur_stree
);
82 struct sm_state
*set_state(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
90 sm_msg("Smatch Internal Error: cur_stree is read only.");
92 if (option_debug
|| strcmp(check_name(owner
), option_debug_check
) == 0) {
93 struct smatch_state
*s
;
95 s
= get_state(owner
, name
, sym
);
97 sm_msg("%s new [%s] '%s' %s", __func__
,
98 check_name(owner
), name
, show_state(state
));
100 sm_msg("%s change [%s] '%s' %s => %s",
101 __func__
, check_name(owner
), name
, show_state(s
),
105 if (owner
!= -1 && unreachable())
108 if (fake_cur_stree_stack
)
109 set_state_stree_stack(&fake_cur_stree_stack
, owner
, name
, sym
, state
);
111 ret
= set_state_stree(&cur_stree
, owner
, name
, sym
, state
);
116 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
120 struct sm_state
*ret
= NULL
;
122 expr
= strip_expr(expr
);
123 name
= expr_to_var_sym(expr
, &sym
);
126 ret
= set_state(owner
, name
, sym
, state
);
132 void __swap_cur_stree(struct stree
*stree
)
134 free_stree(&cur_stree
);
138 void __push_fake_cur_stree(void)
140 push_stree(&fake_cur_stree_stack
, NULL
);
141 __save_pre_cond_states();
144 struct stree
*__pop_fake_cur_stree(void)
146 if (!fake_cur_stree_stack
)
147 sm_msg("INTERNAL error: popping too many fake cur strees.");
148 __use_pre_cond_states();
149 return pop_stree(&fake_cur_stree_stack
);
152 void __free_fake_cur_stree(void)
156 stree
= __pop_fake_cur_stree();
160 void __set_fake_cur_stree_fast(struct stree
*stree
)
162 push_stree(&pre_cond_stack
, cur_stree
);
167 void __pop_fake_cur_stree_fast(void)
169 cur_stree
= pop_stree(&pre_cond_stack
);
173 void __merge_stree_into_cur(struct stree
*stree
)
176 struct sm_state
*orig
;
177 struct sm_state
*merged
;
179 FOR_EACH_SM(stree
, sm
) {
180 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
182 merged
= merge_sm_states(orig
, sm
);
186 } END_FOR_EACH_SM(sm
);
189 void __set_sm(struct sm_state
*sm
)
192 sm_msg("Smatch Internal Error: cur_stree is read only.");
195 strcmp(check_name(sm
->owner
), option_debug_check
) == 0) {
196 struct smatch_state
*s
;
198 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
200 sm_msg("%s new %s", __func__
, show_sm(sm
));
202 sm_msg("%s change %s (was %s)", __func__
, show_sm(sm
),
209 if (fake_cur_stree_stack
)
210 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
212 overwrite_sm_state_stree(&cur_stree
, sm
);
215 void __set_sm_cur_stree(struct sm_state
*sm
)
218 sm_msg("Smatch Internal Error: cur_stree is read only.");
221 strcmp(check_name(sm
->owner
), option_debug_check
) == 0) {
222 struct smatch_state
*s
;
224 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
226 sm_msg("%s new %s", __func__
, show_sm(sm
));
228 sm_msg("%s change %s (was %s)",
229 __func__
, show_sm(sm
), show_state(s
));
235 overwrite_sm_state_stree(&cur_stree
, sm
);
238 void __set_sm_fake_stree(struct sm_state
*sm
)
241 sm_msg("Smatch Internal Error: cur_stree is read only.");
244 strcmp(check_name(sm
->owner
), option_debug_check
) == 0) {
245 struct smatch_state
*s
;
247 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
249 sm_msg("%s new %s", __func__
, show_sm(sm
));
251 sm_msg("%s change %s (was %s)",
252 __func__
, show_sm(sm
), show_state(s
));
258 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
261 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
263 __get_state_hook(owner
, name
, sym
);
265 return get_state_stree(cur_stree
, owner
, name
, sym
);
268 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
272 struct smatch_state
*ret
= NULL
;
274 expr
= strip_expr(expr
);
275 name
= expr_to_var_sym(expr
, &sym
);
278 ret
= get_state(owner
, name
, sym
);
284 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
286 struct sm_state
*sms
;
288 sms
= get_sm_state_stree(cur_stree
, owner
, name
, sym
);
290 return sms
->possible
;
294 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
298 struct state_list
*ret
= NULL
;
300 expr
= strip_expr(expr
);
301 name
= expr_to_var_sym(expr
, &sym
);
304 ret
= get_possible_states(owner
, name
, sym
);
310 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
312 return get_sm_state_stree(cur_stree
, owner
, name
, sym
);
315 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
319 struct sm_state
*ret
= NULL
;
321 expr
= strip_expr(expr
);
322 name
= expr_to_var_sym(expr
, &sym
);
325 ret
= get_sm_state(owner
, name
, sym
);
331 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
333 delete_state_stree(&cur_stree
, owner
, name
, sym
);
334 if (cond_true_stack
) {
335 delete_state_stree_stack(&pre_cond_stack
, owner
, name
, sym
);
336 delete_state_stree_stack(&cond_true_stack
, owner
, name
, sym
);
337 delete_state_stree_stack(&cond_false_stack
, owner
, name
, sym
);
341 void delete_state_expr(int owner
, struct expression
*expr
)
346 expr
= strip_expr(expr
);
347 name
= expr_to_var_sym(expr
, &sym
);
350 delete_state(owner
, name
, sym
);
355 static void delete_all_states_stree_sym(struct stree
**stree
, struct symbol
*sym
)
357 struct state_list
*slist
= NULL
;
360 FOR_EACH_SM(*stree
, sm
) {
362 add_ptr_list(&slist
, sm
);
363 } END_FOR_EACH_SM(sm
);
365 FOR_EACH_PTR(slist
, sm
) {
366 delete_state_stree(stree
, sm
->owner
, sm
->name
, sm
->sym
);
367 } END_FOR_EACH_PTR(sm
);
372 static void delete_all_states_stree_stack_sym(struct stree_stack
**stack
, struct symbol
*sym
)
379 stree
= pop_stree(stack
);
380 delete_all_states_stree_sym(&stree
, sym
);
381 push_stree(stack
, stree
);
384 void __delete_all_states_sym(struct symbol
*sym
)
386 delete_all_states_stree_sym(&cur_stree
, sym
);
388 delete_all_states_stree_stack_sym(&true_stack
, sym
);
389 delete_all_states_stree_stack_sym(&true_stack
, sym
);
390 delete_all_states_stree_stack_sym(&false_stack
, sym
);
391 delete_all_states_stree_stack_sym(&pre_cond_stack
, sym
);
392 delete_all_states_stree_stack_sym(&cond_true_stack
, sym
);
393 delete_all_states_stree_stack_sym(&cond_false_stack
, sym
);
394 delete_all_states_stree_stack_sym(&fake_cur_stree_stack
, sym
);
395 delete_all_states_stree_stack_sym(&break_stack
, sym
);
396 delete_all_states_stree_stack_sym(&switch_stack
, sym
);
397 delete_all_states_stree_stack_sym(&continue_stack
, sym
);
400 * deleting from the goto stack is problematic because we don't know
401 * if the label is in scope and also we need the value for --two-passes.
405 struct stree
*get_all_states_from_stree(int owner
, struct stree
*source
)
407 struct stree
*ret
= NULL
;
408 struct sm_state
*tmp
;
410 FOR_EACH_SM(source
, tmp
) {
411 if (tmp
->owner
== owner
)
412 avl_insert(&ret
, tmp
);
413 } END_FOR_EACH_SM(tmp
);
418 struct stree
*get_all_states_stree(int owner
)
420 return get_all_states_from_stree(owner
, cur_stree
);
423 struct stree
*__get_cur_stree(void)
428 int is_reachable(void)
435 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
436 struct smatch_state
*true_state
,
437 struct smatch_state
*false_state
)
440 sm_msg("Smatch Internal Error: cur_stree is read only.");
442 if (option_debug
|| strcmp(check_name(owner
), option_debug_check
) == 0) {
443 struct smatch_state
*tmp
;
445 tmp
= get_state(owner
, name
, sym
);
446 sm_msg("set_true_false [%s] '%s'. Was %s. Now T:%s F:%s\n",
447 check_name(owner
), name
, show_state(tmp
),
448 show_state(true_state
), show_state(false_state
));
454 if (!cond_false_stack
|| !cond_true_stack
) {
455 printf("Error: missing true/false stacks\n");
460 set_state_stree_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
462 set_state_stree_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
465 void set_true_false_states_expr(int owner
, struct expression
*expr
,
466 struct smatch_state
*true_state
,
467 struct smatch_state
*false_state
)
472 expr
= strip_expr(expr
);
473 name
= expr_to_var_sym(expr
, &sym
);
476 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
481 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
486 if (!cond_false_stack
|| !cond_true_stack
) {
487 printf("Error: missing true/false stacks\n");
492 overwrite_sm_state_stree_stack(&cond_true_stack
, true_sm
);
494 overwrite_sm_state_stree_stack(&cond_false_stack
, false_sm
);
497 void nullify_path(void)
499 free_stree(&cur_stree
);
502 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
509 * At the start of every function we mark the path
510 * as unnull. That way there is always at least one state
511 * in the cur_stree until nullify_path is called. This
512 * is used in merge_slist() for the first null check.
514 void __unnullify_path(void)
517 set_state(-1, "unnull_path", NULL
, &true_state
);
520 int __path_is_null(void)
527 static void check_stree_stack_free(struct stree_stack
**stack
)
530 sm_msg("smatch internal error: stack not empty");
531 free_stack_and_strees(stack
);
535 void save_all_states(void)
537 __add_ptr_list(&backup
, cur_stree
, 0);
540 __add_ptr_list(&backup
, true_stack
, 0);
542 __add_ptr_list(&backup
, false_stack
, 0);
544 __add_ptr_list(&backup
, pre_cond_stack
, 0);
545 pre_cond_stack
= NULL
;
547 __add_ptr_list(&backup
, cond_true_stack
, 0);
548 cond_true_stack
= NULL
;
549 __add_ptr_list(&backup
, cond_false_stack
, 0);
550 cond_false_stack
= NULL
;
552 __add_ptr_list(&backup
, fake_cur_stree_stack
, 0);
553 fake_cur_stree_stack
= NULL
;
555 __add_ptr_list(&backup
, break_stack
, 0);
557 __add_ptr_list(&backup
, switch_stack
, 0);
559 __add_ptr_list(&backup
, remaining_cases
, 0);
560 remaining_cases
= NULL
;
561 __add_ptr_list(&backup
, default_stack
, 0);
562 default_stack
= NULL
;
563 __add_ptr_list(&backup
, continue_stack
, 0);
564 continue_stack
= NULL
;
566 __add_ptr_list(&backup
, goto_stack
, 0);
570 static void *pop_backup(void)
574 ret
= last_ptr_list(backup
);
575 delete_ptr_list_last(&backup
);
579 void restore_all_states(void)
581 goto_stack
= pop_backup();
583 continue_stack
= pop_backup();
584 default_stack
= pop_backup();
585 remaining_cases
= pop_backup();
586 switch_stack
= pop_backup();
587 break_stack
= pop_backup();
589 fake_cur_stree_stack
= pop_backup();
591 cond_false_stack
= pop_backup();
592 cond_true_stack
= pop_backup();
594 pre_cond_stack
= pop_backup();
595 false_stack
= pop_backup();
596 true_stack
= pop_backup();
598 cur_stree
= pop_backup();
601 void free_goto_stack(void)
603 struct named_stree
*named_stree
;
605 FOR_EACH_PTR(goto_stack
, named_stree
) {
606 free_stree(&named_stree
->stree
);
607 } END_FOR_EACH_PTR(named_stree
);
608 __free_ptr_list((struct ptr_list
**)&goto_stack
);
611 void clear_all_states(void)
614 check_stree_stack_free(&true_stack
);
615 check_stree_stack_free(&false_stack
);
616 check_stree_stack_free(&pre_cond_stack
);
617 check_stree_stack_free(&cond_true_stack
);
618 check_stree_stack_free(&cond_false_stack
);
619 check_stree_stack_free(&break_stack
);
620 check_stree_stack_free(&switch_stack
);
621 check_stree_stack_free(&continue_stack
);
622 check_stree_stack_free(&fake_cur_stree_stack
);
626 free_every_single_sm_state();
629 void __push_cond_stacks(void)
631 push_stree(&cond_true_stack
, NULL
);
632 push_stree(&cond_false_stack
, NULL
);
633 __push_fake_cur_stree();
636 void __fold_in_set_states(void)
638 struct stree
*new_states
;
641 new_states
= __pop_fake_cur_stree();
642 FOR_EACH_SM(new_states
, sm
) {
644 __set_true_false_sm(sm
, sm
);
645 } END_FOR_EACH_SM(sm
);
646 free_stree(&new_states
);
649 void __free_set_states(void)
651 struct stree
*new_states
;
653 new_states
= __pop_fake_cur_stree();
654 free_stree(&new_states
);
657 struct stree
*__copy_cond_true_states(void)
661 ret
= pop_stree(&cond_true_stack
);
662 push_stree(&cond_true_stack
, clone_stree(ret
));
666 struct stree
*__copy_cond_false_states(void)
670 ret
= pop_stree(&cond_false_stack
);
671 push_stree(&cond_false_stack
, clone_stree(ret
));
675 struct stree
*__pop_cond_true_stack(void)
677 return pop_stree(&cond_true_stack
);
680 struct stree
*__pop_cond_false_stack(void)
682 return pop_stree(&cond_false_stack
);
686 * This combines the pre cond states with either the true or false states.
688 * a = kmalloc() ; if (a !! foo(a)
689 * In the pre state a is possibly null. In the true state it is non null.
690 * In the false state it is null. Combine the pre and the false to get
691 * that when we call 'foo', 'a' is null.
693 static void __use_cond_stack(struct stree_stack
**stack
)
697 free_stree(&cur_stree
);
699 cur_stree
= pop_stree(&pre_cond_stack
);
700 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
702 stree
= pop_stree(stack
);
703 overwrite_stree(stree
, &cur_stree
);
704 push_stree(stack
, stree
);
707 void __use_pre_cond_states(void)
709 free_stree(&cur_stree
);
710 cur_stree
= pop_stree(&pre_cond_stack
);
713 void __use_cond_true_states(void)
715 __use_cond_stack(&cond_true_stack
);
718 void __use_cond_false_states(void)
720 __use_cond_stack(&cond_false_stack
);
723 void __negate_cond_stacks(void)
725 struct stree
*old_false
, *old_true
;
727 __use_cond_stack(&cond_false_stack
);
728 old_false
= pop_stree(&cond_false_stack
);
729 old_true
= pop_stree(&cond_true_stack
);
730 push_stree(&cond_false_stack
, old_true
);
731 push_stree(&cond_true_stack
, old_false
);
734 void __and_cond_states(void)
736 and_stree_stack(&cond_true_stack
);
737 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_false_stack
);
740 void __or_cond_states(void)
742 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_true_stack
);
743 and_stree_stack(&cond_false_stack
);
746 void __save_pre_cond_states(void)
748 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
751 void __discard_pre_cond_states(void)
755 tmp
= pop_stree(&pre_cond_stack
);
759 struct stree
*__get_true_states(void)
761 return clone_stree(top_stree(cond_true_stack
));
764 struct stree
*__get_false_states(void)
766 return clone_stree(top_stree(cond_false_stack
));
769 void __use_cond_states(void)
771 struct stree
*pre
, *pre_clone
, *true_states
, *false_states
;
773 pre
= pop_stree(&pre_cond_stack
);
774 pre_clone
= clone_stree(pre
);
776 true_states
= pop_stree(&cond_true_stack
);
777 overwrite_stree(true_states
, &pre
);
778 free_stree(&true_states
);
779 /* we use the true states right away */
780 free_stree(&cur_stree
);
783 false_states
= pop_stree(&cond_false_stack
);
784 overwrite_stree(false_states
, &pre_clone
);
785 free_stree(&false_states
);
786 push_stree(&false_stack
, pre_clone
);
789 void __push_true_states(void)
791 push_stree(&true_stack
, clone_stree(cur_stree
));
794 void __use_false_states(void)
796 free_stree(&cur_stree
);
797 cur_stree
= pop_stree(&false_stack
);
800 void __discard_false_states(void)
804 stree
= pop_stree(&false_stack
);
808 void __merge_false_states(void)
812 stree
= pop_stree(&false_stack
);
813 merge_stree(&cur_stree
, stree
);
817 static void update_fake_stree_with_merged(void)
820 struct state_list
*slist
= NULL
;
821 struct sm_state
*sm
, *new;
823 if (!fake_cur_stree_stack
)
825 stree
= pop_stree(&fake_cur_stree_stack
);
826 FOR_EACH_SM(stree
, sm
) {
827 new = get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
830 add_ptr_list(&slist
, new);
831 } END_FOR_EACH_SM(sm
);
833 FOR_EACH_PTR(slist
, sm
) {
834 overwrite_sm_state_stree(&stree
, sm
);
835 } END_FOR_EACH_PTR(sm
);
838 push_stree(&fake_cur_stree_stack
, stree
);
841 void __merge_true_states(void)
845 stree
= pop_stree(&true_stack
);
846 merge_stree(&cur_stree
, stree
);
847 update_fake_stree_with_merged();
851 void __push_continues(void)
853 push_stree(&continue_stack
, NULL
);
856 void __discard_continues(void)
860 stree
= pop_stree(&continue_stack
);
864 void __process_continues(void)
868 stree
= pop_stree(&continue_stack
);
870 stree
= clone_stree(cur_stree
);
872 merge_stree(&stree
, cur_stree
);
874 push_stree(&continue_stack
, stree
);
877 void __merge_continues(void)
881 stree
= pop_stree(&continue_stack
);
882 merge_stree(&cur_stree
, stree
);
886 void __push_breaks(void)
888 push_stree(&break_stack
, NULL
);
891 void __process_breaks(void)
895 stree
= pop_stree(&break_stack
);
897 stree
= clone_stree(cur_stree
);
899 merge_stree(&stree
, cur_stree
);
901 push_stree(&break_stack
, stree
);
904 int __has_breaks(void)
909 stree
= pop_stree(&break_stack
);
911 push_stree(&break_stack
, stree
);
915 void __merge_breaks(void)
919 stree
= pop_stree(&break_stack
);
920 merge_stree(&cur_stree
, stree
);
924 void __use_breaks(void)
926 free_stree(&cur_stree
);
927 cur_stree
= pop_stree(&break_stack
);
930 void __save_switch_states(struct expression
*switch_expr
)
932 struct range_list
*rl
;
934 get_absolute_rl(switch_expr
, &rl
);
936 push_rl(&remaining_cases
, rl
);
937 push_stree(&switch_stack
, clone_stree(cur_stree
));
940 void __merge_switches(struct expression
*switch_expr
, struct range_list
*case_rl
)
943 struct stree
*implied_stree
;
945 stree
= pop_stree(&switch_stack
);
946 implied_stree
= __implied_case_stree(switch_expr
, case_rl
, &remaining_cases
, &stree
);
947 merge_stree(&cur_stree
, implied_stree
);
948 free_stree(&implied_stree
);
949 push_stree(&switch_stack
, stree
);
952 void __discard_switches(void)
956 pop_rl(&remaining_cases
);
957 stree
= pop_stree(&switch_stack
);
961 void __push_default(void)
963 push_stree(&default_stack
, NULL
);
966 void __set_default(void)
968 set_state_stree_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
971 int __pop_default(void)
975 stree
= pop_stree(&default_stack
);
983 static struct named_stree
*alloc_named_stree(const char *name
, struct stree
*stree
)
985 struct named_stree
*named_stree
= __alloc_named_stree(0);
987 named_stree
->name
= (char *)name
;
988 named_stree
->stree
= stree
;
992 void __save_gotos(const char *name
)
994 struct stree
**stree
;
997 stree
= get_named_stree(goto_stack
, name
);
999 merge_stree(stree
, cur_stree
);
1002 struct named_stree
*named_stree
;
1004 clone
= clone_stree(cur_stree
);
1005 named_stree
= alloc_named_stree(name
, clone
);
1006 add_ptr_list(&goto_stack
, named_stree
);
1010 void __merge_gotos(const char *name
)
1012 struct stree
**stree
;
1014 stree
= get_named_stree(goto_stack
, name
);
1016 merge_stree(&cur_stree
, *stree
);