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("new state. name='%s' [%s] %s",
98 name
, check_name(owner
), show_state(state
));
100 sm_msg("state change name='%s' [%s] %s => %s",
101 name
, check_name(owner
), 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
);
113 if (cond_true_stack
) {
114 set_state_stree_stack(&cond_true_stack
, owner
, name
, sym
, state
);
115 set_state_stree_stack(&cond_false_stack
, owner
, name
, sym
, state
);
120 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
124 struct sm_state
*ret
= NULL
;
126 expr
= strip_expr(expr
);
127 name
= expr_to_var_sym(expr
, &sym
);
130 ret
= set_state(owner
, name
, sym
, state
);
136 void __push_fake_cur_stree(void)
138 push_stree(&fake_cur_stree_stack
, NULL
);
139 __save_pre_cond_states();
142 struct stree
*__pop_fake_cur_stree(void)
144 if (!fake_cur_stree_stack
)
145 sm_msg("INTERNAL error: popping too many fake cur strees.");
146 __use_pre_cond_states();
147 return pop_stree(&fake_cur_stree_stack
);
150 void __free_fake_cur_stree(void)
154 __use_pre_cond_states();
155 stree
= pop_stree(&fake_cur_stree_stack
);
159 void __set_fake_cur_stree_fast(struct stree
*stree
)
161 push_stree(&pre_cond_stack
, cur_stree
);
166 void __pop_fake_cur_stree_fast(void)
168 cur_stree
= pop_stree(&pre_cond_stack
);
172 void __merge_stree_into_cur(struct stree
*stree
)
175 struct sm_state
*orig
;
176 struct sm_state
*merged
;
178 FOR_EACH_SM(stree
, sm
) {
179 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
181 merged
= merge_sm_states(orig
, sm
);
185 } END_FOR_EACH_SM(sm
);
188 void __set_sm(struct sm_state
*sm
)
191 sm_msg("Smatch Internal Error: cur_stree is read only.");
194 strcmp(check_name(sm
->owner
), option_debug_check
) == 0) {
195 struct smatch_state
*s
;
197 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
199 sm_msg("new state. name='%s' [%s] %s",
200 sm
->name
, check_name(sm
->owner
),
201 show_state(sm
->state
));
203 sm_msg("state change name='%s' [%s] %s => %s",
204 sm
->name
, check_name(sm
->owner
), show_state(s
),
205 show_state(sm
->state
));
211 if (fake_cur_stree_stack
)
212 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
214 overwrite_sm_state_stree(&cur_stree
, sm
);
216 if (cond_true_stack
) {
217 overwrite_sm_state_stree_stack(&cond_true_stack
, sm
);
218 overwrite_sm_state_stree_stack(&cond_false_stack
, sm
);
222 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
224 return get_state_stree(cur_stree
, owner
, name
, sym
);
227 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
231 struct smatch_state
*ret
= NULL
;
233 expr
= strip_expr(expr
);
234 name
= expr_to_var_sym(expr
, &sym
);
237 ret
= get_state(owner
, name
, sym
);
243 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
245 struct sm_state
*sms
;
247 sms
= get_sm_state_stree(cur_stree
, owner
, name
, sym
);
249 return sms
->possible
;
253 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
257 struct state_list
*ret
= NULL
;
259 expr
= strip_expr(expr
);
260 name
= expr_to_var_sym(expr
, &sym
);
263 ret
= get_possible_states(owner
, name
, sym
);
269 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
271 return get_sm_state_stree(cur_stree
, owner
, name
, sym
);
274 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
278 struct sm_state
*ret
= NULL
;
280 expr
= strip_expr(expr
);
281 name
= expr_to_var_sym(expr
, &sym
);
284 ret
= get_sm_state(owner
, name
, sym
);
290 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
292 delete_state_stree(&cur_stree
, owner
, name
, sym
);
293 if (cond_true_stack
) {
294 delete_state_stree_stack(&pre_cond_stack
, owner
, name
, sym
);
295 delete_state_stree_stack(&cond_true_stack
, owner
, name
, sym
);
296 delete_state_stree_stack(&cond_false_stack
, owner
, name
, sym
);
300 void delete_state_expr(int owner
, struct expression
*expr
)
305 expr
= strip_expr(expr
);
306 name
= expr_to_var_sym(expr
, &sym
);
309 delete_state(owner
, name
, sym
);
314 struct stree
*get_all_states_from_stree(int owner
, struct stree
*source
)
316 struct stree
*ret
= NULL
;
317 struct sm_state
*tmp
;
319 FOR_EACH_SM(source
, tmp
) {
320 if (tmp
->owner
== owner
)
321 avl_insert(&ret
, tmp
);
322 } END_FOR_EACH_SM(tmp
);
327 struct stree
*get_all_states_stree(int owner
)
329 return get_all_states_from_stree(owner
, cur_stree
);
332 struct stree
*__get_cur_stree(void)
337 int is_reachable(void)
344 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
345 struct smatch_state
*true_state
,
346 struct smatch_state
*false_state
)
349 sm_msg("Smatch Internal Error: cur_stree is read only.");
351 if (option_debug
|| strcmp(check_name(owner
), option_debug_check
) == 0) {
352 struct smatch_state
*tmp
;
354 tmp
= get_state(owner
, name
, sym
);
355 sm_msg("set_true_false '%s'. Was %s. Now T:%s F:%s\n",
356 name
, show_state(tmp
),
357 show_state(true_state
), show_state(false_state
));
363 if (!cond_false_stack
|| !cond_true_stack
) {
364 printf("Error: missing true/false stacks\n");
369 set_state_stree(&cur_stree
, owner
, name
, sym
, true_state
);
370 set_state_stree_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
373 set_state_stree_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
376 void set_true_false_states_expr(int owner
, struct expression
*expr
,
377 struct smatch_state
*true_state
,
378 struct smatch_state
*false_state
)
383 expr
= strip_expr(expr
);
384 name
= expr_to_var_sym(expr
, &sym
);
387 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
392 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
397 if (!cond_false_stack
|| !cond_true_stack
) {
398 printf("Error: missing true/false stacks\n");
403 overwrite_sm_state_stree(&cur_stree
, true_sm
);
404 overwrite_sm_state_stree_stack(&cond_true_stack
, true_sm
);
407 overwrite_sm_state_stree_stack(&cond_false_stack
, false_sm
);
410 void nullify_path(void)
412 free_stree(&cur_stree
);
415 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
422 * At the start of every function we mark the path
423 * as unnull. That way there is always at least one state
424 * in the cur_stree until nullify_path is called. This
425 * is used in merge_slist() for the first null check.
427 void __unnullify_path(void)
430 set_state(-1, "unnull_path", NULL
, &true_state
);
433 int __path_is_null(void)
440 static void check_stree_stack_free(struct stree_stack
**stack
)
443 sm_msg("smatch internal error: stack not empty");
444 free_stack_and_strees(stack
);
448 void save_all_states(void)
450 __add_ptr_list(&backup
, cur_stree
, 0);
453 __add_ptr_list(&backup
, true_stack
, 0);
455 __add_ptr_list(&backup
, false_stack
, 0);
457 __add_ptr_list(&backup
, pre_cond_stack
, 0);
458 pre_cond_stack
= NULL
;
460 __add_ptr_list(&backup
, cond_true_stack
, 0);
461 cond_true_stack
= NULL
;
462 __add_ptr_list(&backup
, cond_false_stack
, 0);
463 cond_false_stack
= NULL
;
465 __add_ptr_list(&backup
, fake_cur_stree_stack
, 0);
466 fake_cur_stree_stack
= NULL
;
468 __add_ptr_list(&backup
, break_stack
, 0);
470 __add_ptr_list(&backup
, switch_stack
, 0);
472 __add_ptr_list(&backup
, remaining_cases
, 0);
473 remaining_cases
= NULL
;
474 __add_ptr_list(&backup
, default_stack
, 0);
475 default_stack
= NULL
;
476 __add_ptr_list(&backup
, continue_stack
, 0);
477 continue_stack
= NULL
;
479 __add_ptr_list(&backup
, goto_stack
, 0);
483 static void *pop_backup(void)
487 ret
= last_ptr_list(backup
);
488 delete_ptr_list_last(&backup
);
492 void restore_all_states(void)
494 goto_stack
= pop_backup();
496 continue_stack
= pop_backup();
497 default_stack
= pop_backup();
498 remaining_cases
= pop_backup();
499 switch_stack
= pop_backup();
500 break_stack
= pop_backup();
502 fake_cur_stree_stack
= pop_backup();
504 cond_false_stack
= pop_backup();
505 cond_true_stack
= pop_backup();
507 pre_cond_stack
= pop_backup();
508 false_stack
= pop_backup();
509 true_stack
= pop_backup();
511 cur_stree
= pop_backup();
514 void free_goto_stack(void)
516 struct named_stree
*named_stree
;
518 FOR_EACH_PTR(goto_stack
, named_stree
) {
519 free_stree(&named_stree
->stree
);
520 } END_FOR_EACH_PTR(named_stree
);
521 __free_ptr_list((struct ptr_list
**)&goto_stack
);
524 void clear_all_states(void)
527 check_stree_stack_free(&true_stack
);
528 check_stree_stack_free(&false_stack
);
529 check_stree_stack_free(&pre_cond_stack
);
530 check_stree_stack_free(&cond_true_stack
);
531 check_stree_stack_free(&cond_false_stack
);
532 check_stree_stack_free(&break_stack
);
533 check_stree_stack_free(&switch_stack
);
534 check_stree_stack_free(&continue_stack
);
538 free_every_single_sm_state();
541 void __push_cond_stacks(void)
543 push_stree(&cond_true_stack
, NULL
);
544 push_stree(&cond_false_stack
, NULL
);
547 struct stree
*__copy_cond_true_states(void)
551 ret
= pop_stree(&cond_true_stack
);
552 push_stree(&cond_true_stack
, clone_stree(ret
));
556 struct stree
*__copy_cond_false_states(void)
560 ret
= pop_stree(&cond_false_stack
);
561 push_stree(&cond_false_stack
, clone_stree(ret
));
565 struct stree
*__pop_cond_true_stack(void)
567 return pop_stree(&cond_true_stack
);
570 struct stree
*__pop_cond_false_stack(void)
572 return pop_stree(&cond_false_stack
);
576 * This combines the pre cond states with either the true or false states.
578 * a = kmalloc() ; if (a !! foo(a)
579 * In the pre state a is possibly null. In the true state it is non null.
580 * In the false state it is null. Combine the pre and the false to get
581 * that when we call 'foo', 'a' is null.
583 static void __use_cond_stack(struct stree_stack
**stack
)
587 free_stree(&cur_stree
);
589 cur_stree
= pop_stree(&pre_cond_stack
);
590 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
592 stree
= pop_stree(stack
);
593 overwrite_stree(stree
, &cur_stree
);
594 push_stree(stack
, stree
);
597 void __use_pre_cond_states(void)
599 free_stree(&cur_stree
);
600 cur_stree
= pop_stree(&pre_cond_stack
);
603 void __use_cond_true_states(void)
605 __use_cond_stack(&cond_true_stack
);
608 void __use_cond_false_states(void)
610 __use_cond_stack(&cond_false_stack
);
613 void __negate_cond_stacks(void)
615 struct stree
*old_false
, *old_true
;
617 __use_cond_stack(&cond_false_stack
);
618 old_false
= pop_stree(&cond_false_stack
);
619 old_true
= pop_stree(&cond_true_stack
);
620 push_stree(&cond_false_stack
, old_true
);
621 push_stree(&cond_true_stack
, old_false
);
624 void __and_cond_states(void)
626 and_stree_stack(&cond_true_stack
);
627 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_false_stack
);
630 void __or_cond_states(void)
632 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_true_stack
);
633 and_stree_stack(&cond_false_stack
);
636 void __save_pre_cond_states(void)
638 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
641 void __discard_pre_cond_states(void)
645 tmp
= pop_stree(&pre_cond_stack
);
649 void __use_cond_states(void)
651 struct stree
*pre
, *pre_clone
, *true_states
, *false_states
;
653 pre
= pop_stree(&pre_cond_stack
);
654 pre_clone
= clone_stree(pre
);
656 true_states
= pop_stree(&cond_true_stack
);
657 overwrite_stree(true_states
, &pre
);
658 free_stree(&true_states
);
659 /* we use the true states right away */
660 free_stree(&cur_stree
);
663 false_states
= pop_stree(&cond_false_stack
);
664 overwrite_stree(false_states
, &pre_clone
);
665 free_stree(&false_states
);
666 push_stree(&false_stack
, pre_clone
);
669 void __push_true_states(void)
671 push_stree(&true_stack
, clone_stree(cur_stree
));
674 void __use_false_states(void)
676 free_stree(&cur_stree
);
677 cur_stree
= pop_stree(&false_stack
);
680 void __discard_false_states(void)
684 stree
= pop_stree(&false_stack
);
688 void __merge_false_states(void)
692 stree
= pop_stree(&false_stack
);
693 merge_stree(&cur_stree
, stree
);
697 void __merge_true_states(void)
701 stree
= pop_stree(&true_stack
);
702 merge_stree(&cur_stree
, stree
);
706 void __push_continues(void)
708 push_stree(&continue_stack
, NULL
);
711 void __discard_continues(void)
715 stree
= pop_stree(&continue_stack
);
719 void __process_continues(void)
723 stree
= pop_stree(&continue_stack
);
725 stree
= clone_stree(cur_stree
);
727 merge_stree(&stree
, cur_stree
);
729 push_stree(&continue_stack
, stree
);
732 static int top_stree_empty(struct stree_stack
**stack
)
737 tmp
= pop_stree(stack
);
740 push_stree(stack
, tmp
);
744 /* a silly loop does this: while(i--) { return; } */
745 void __warn_on_silly_pre_loops(void)
747 if (!__path_is_null())
749 if (!top_stree_empty(&continue_stack
))
751 if (!top_stree_empty(&break_stack
))
753 /* if the path was nullified before the loop, then we already
754 printed an error earlier */
755 if (top_stree_empty(&false_stack
))
757 sm_msg("info: loop could be replaced with if statement.");
760 void __merge_continues(void)
764 stree
= pop_stree(&continue_stack
);
765 merge_stree(&cur_stree
, stree
);
769 void __push_breaks(void)
771 push_stree(&break_stack
, NULL
);
774 void __process_breaks(void)
778 stree
= pop_stree(&break_stack
);
780 stree
= clone_stree(cur_stree
);
782 merge_stree(&stree
, cur_stree
);
784 push_stree(&break_stack
, stree
);
787 int __has_breaks(void)
792 stree
= pop_stree(&break_stack
);
794 push_stree(&break_stack
, stree
);
798 void __merge_breaks(void)
802 stree
= pop_stree(&break_stack
);
803 merge_stree(&cur_stree
, stree
);
807 void __use_breaks(void)
809 free_stree(&cur_stree
);
810 cur_stree
= pop_stree(&break_stack
);
813 void __save_switch_states(struct expression
*switch_expr
)
815 push_rl(&remaining_cases
, __get_implied_values(switch_expr
));
816 push_stree(&switch_stack
, clone_stree(cur_stree
));
819 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
822 struct stree
*implied_stree
;
824 stree
= pop_stree(&switch_stack
);
825 implied_stree
= __implied_case_stree(switch_expr
, case_expr
, &remaining_cases
, &stree
);
826 merge_stree(&cur_stree
, implied_stree
);
827 free_stree(&implied_stree
);
828 push_stree(&switch_stack
, stree
);
831 void __discard_switches(void)
835 pop_rl(&remaining_cases
);
836 stree
= pop_stree(&switch_stack
);
840 void __push_default(void)
842 push_stree(&default_stack
, NULL
);
845 void __set_default(void)
847 set_state_stree_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
850 int __pop_default(void)
854 stree
= pop_stree(&default_stack
);
862 static struct named_stree
*alloc_named_stree(const char *name
, struct stree
*stree
)
864 struct named_stree
*named_stree
= __alloc_named_stree(0);
866 named_stree
->name
= (char *)name
;
867 named_stree
->stree
= stree
;
871 void __save_gotos(const char *name
)
873 struct stree
**stree
;
876 stree
= get_named_stree(goto_stack
, name
);
878 merge_stree(stree
, cur_stree
);
881 struct named_stree
*named_stree
;
883 clone
= clone_stree(cur_stree
);
884 named_stree
= alloc_named_stree(name
, clone
);
885 add_ptr_list(&goto_stack
, named_stree
);
889 void __merge_gotos(const char *name
)
891 struct stree
**stree
;
893 stree
= get_named_stree(goto_stack
, name
);
895 merge_stree(&cur_stree
, *stree
);