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 merged
= { .name
= "merged" };
42 struct smatch_state true_state
= { .name
= "true" };
43 struct smatch_state false_state
= { .name
= "false" };
45 static struct AVL
*cur_stree
; /* current states */
47 static struct stree_stack
*true_stack
; /* states after a t/f branch */
48 static struct stree_stack
*false_stack
;
49 static struct state_list_stack
*pre_cond_stack
; /* states before a t/f branch */
51 static struct state_list_stack
*cond_true_stack
; /* states affected by a branch */
52 static struct state_list_stack
*cond_false_stack
;
54 static struct stree_stack
*fake_cur_stree_stack
;
57 static struct stree_stack
*break_stack
;
58 static struct stree_stack
*switch_stack
;
59 static struct range_list_stack
*remaining_cases
;
60 static struct stree_stack
*default_stack
;
61 static struct stree_stack
*continue_stack
;
63 static struct named_stree_stack
*goto_stack
;
65 static struct ptr_list
*backup
;
67 struct state_list_stack
*implied_pools
;
71 void __print_cur_slist(void)
73 __print_stree(cur_stree
);
76 static int in_declarations_bit(void)
78 struct statement
*tmp
;
80 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
81 if (tmp
->type
== STMT_DECLARATION
)
84 } END_FOR_EACH_PTR_REVERSE(tmp
);
90 static int reset_warnings
= 1;
98 if (in_declarations_bit())
101 /* option spammy turns on a noisier version of this */
102 if (reset_warnings
&& !option_spammy
)
103 sm_msg("info: ignoring unreachable code.");
109 struct sm_state
*set_state(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
111 struct sm_state
*ret
;
117 sm_msg("Smatch Internal Error: cur_stree is read only.");
119 if (option_debug
|| strcmp(check_name(owner
), option_debug_check
) == 0) {
120 struct smatch_state
*s
;
122 s
= get_state(owner
, name
, sym
);
124 printf("%d new state. name='%s' [%s] %s\n",
125 get_lineno(), name
, check_name(owner
), show_state(state
));
127 printf("%d state change name='%s' [%s] %s => %s\n",
128 get_lineno(), name
, check_name(owner
), show_state(s
),
132 if (owner
!= -1 && unreachable())
135 if (fake_cur_stree_stack
)
136 set_state_stree_stack(&fake_cur_stree_stack
, owner
, name
, sym
, state
);
138 ret
= set_state_stree(&cur_stree
, owner
, name
, sym
, state
);
140 if (cond_true_stack
) {
141 set_state_stack(&cond_true_stack
, owner
, name
, sym
, state
);
142 set_state_stack(&cond_false_stack
, owner
, name
, sym
, state
);
147 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
151 struct sm_state
*ret
= NULL
;
153 expr
= strip_expr(expr
);
154 name
= expr_to_var_sym(expr
, &sym
);
157 ret
= set_state(owner
, name
, sym
, state
);
163 void __push_fake_cur_slist()
165 push_stree(&fake_cur_stree_stack
, NULL
);
166 __save_pre_cond_states();
169 struct state_list
*__pop_fake_cur_slist()
171 __use_pre_cond_states();
172 return stree_to_slist(pop_stree(&fake_cur_stree_stack
));
175 void __free_fake_cur_slist()
179 __use_pre_cond_states();
180 stree
= pop_stree(&fake_cur_stree_stack
);
184 void __set_fake_cur_slist_fast(struct state_list
*slist
)
186 push_slist(&pre_cond_stack
, stree_to_slist(cur_stree
));
187 cur_stree
= slist_to_stree(slist
);
191 void __set_fake_cur_stree_fast(struct AVL
*stree
)
193 push_slist(&pre_cond_stack
, stree_to_slist(cur_stree
));
198 void __pop_fake_cur_slist_fast()
200 cur_stree
= slist_to_stree(pop_slist(&pre_cond_stack
));
204 void __pop_fake_cur_stree_fast()
206 cur_stree
= slist_to_stree(pop_slist(&pre_cond_stack
));
210 void __merge_slist_into_cur(struct state_list
*slist
)
213 struct sm_state
*orig
;
214 struct sm_state
*merged
;
216 FOR_EACH_PTR(slist
, sm
) {
217 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
219 merged
= merge_sm_states(orig
, sm
);
223 } END_FOR_EACH_PTR(sm
);
226 void __set_sm(struct sm_state
*sm
)
229 sm_msg("Smatch Internal Error: cur_stree is read only.");
232 strcmp(check_name(sm
->owner
), option_debug_check
) == 0) {
233 struct smatch_state
*s
;
235 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
237 printf("%d new state. name='%s' [%s] %s\n",
238 get_lineno(), sm
->name
, check_name(sm
->owner
),
239 show_state(sm
->state
));
241 printf("%d state change name='%s' [%s] %s => %s\n",
242 get_lineno(), sm
->name
, check_name(sm
->owner
), show_state(s
),
243 show_state(sm
->state
));
249 if (fake_cur_stree_stack
)
250 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
252 overwrite_sm_state_stree(&cur_stree
, sm
);
254 if (cond_true_stack
) {
255 overwrite_sm_state_stack(&cond_true_stack
, sm
);
256 overwrite_sm_state_stack(&cond_false_stack
, sm
);
260 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
262 return get_state_stree(cur_stree
, owner
, name
, sym
);
265 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
269 struct smatch_state
*ret
= NULL
;
271 expr
= strip_expr(expr
);
272 name
= expr_to_var_sym(expr
, &sym
);
275 ret
= get_state(owner
, name
, sym
);
281 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
283 struct sm_state
*sms
;
285 sms
= get_sm_state_stree(cur_stree
, owner
, name
, sym
);
287 return sms
->possible
;
291 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
295 struct state_list
*ret
= NULL
;
297 expr
= strip_expr(expr
);
298 name
= expr_to_var_sym(expr
, &sym
);
301 ret
= get_possible_states(owner
, name
, sym
);
307 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
309 return get_sm_state_stree(cur_stree
, owner
, name
, sym
);
312 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
316 struct sm_state
*ret
= NULL
;
318 expr
= strip_expr(expr
);
319 name
= expr_to_var_sym(expr
, &sym
);
322 ret
= get_sm_state(owner
, name
, sym
);
328 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
330 delete_state_stree(&cur_stree
, owner
, name
, sym
);
331 if (cond_true_stack
) {
332 delete_state_stack(&pre_cond_stack
, owner
, name
, sym
);
333 delete_state_stack(&cond_true_stack
, owner
, name
, sym
);
334 delete_state_stack(&cond_false_stack
, owner
, name
, sym
);
338 void delete_state_expr(int owner
, struct expression
*expr
)
343 expr
= strip_expr(expr
);
344 name
= expr_to_var_sym(expr
, &sym
);
347 delete_state(owner
, name
, sym
);
352 struct state_list
*get_all_states_slist(int owner
, struct state_list
*source
)
354 struct state_list
*slist
= NULL
;
355 struct sm_state
*tmp
;
357 FOR_EACH_PTR(source
, tmp
) {
358 if (tmp
->owner
== owner
)
359 add_ptr_list(&slist
, tmp
);
360 } END_FOR_EACH_PTR(tmp
);
365 struct state_list
*get_all_states(int owner
)
367 struct state_list
*slist
= NULL
;
368 struct sm_state
*tmp
;
370 FOR_EACH_SM(cur_stree
, tmp
) {
371 if (tmp
->owner
== owner
)
372 add_ptr_list(&slist
, tmp
);
373 } END_FOR_EACH_SM(tmp
);
378 int is_reachable(void)
385 struct state_list
*__get_cur_slist(void)
387 return stree_to_slist(cur_stree
);
390 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
391 struct smatch_state
*true_state
,
392 struct smatch_state
*false_state
)
394 if (option_debug
|| strcmp(check_name(owner
), option_debug_check
) == 0) {
395 struct smatch_state
*tmp
;
397 tmp
= get_state(owner
, name
, sym
);
398 printf("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
399 get_lineno(), name
, show_state(tmp
),
400 show_state(true_state
), show_state(false_state
));
406 if (!cond_false_stack
|| !cond_true_stack
) {
407 printf("Error: missing true/false stacks\n");
412 set_state_stree(&cur_stree
, owner
, name
, sym
, true_state
);
413 set_state_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
416 set_state_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
419 void set_true_false_states_expr(int owner
, struct expression
*expr
,
420 struct smatch_state
*true_state
,
421 struct smatch_state
*false_state
)
426 expr
= strip_expr(expr
);
427 name
= expr_to_var_sym(expr
, &sym
);
430 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
435 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
440 if (!cond_false_stack
|| !cond_true_stack
) {
441 printf("Error: missing true/false stacks\n");
446 overwrite_sm_state_stree(&cur_stree
, true_sm
);
447 overwrite_sm_state_stack(&cond_true_stack
, true_sm
);
450 overwrite_sm_state_stack(&cond_false_stack
, false_sm
);
453 void nullify_path(void)
455 free_stree(&cur_stree
);
458 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
465 * At the start of every function we mark the path
466 * as unnull. That way there is always at least one state
467 * in the cur_stree until nullify_path is called. This
468 * is used in merge_slist() for the first null check.
470 void __unnullify_path(void)
472 set_state(-1, "unnull_path", NULL
, &true_state
);
475 int __path_is_null(void)
482 static void check_stack_free(struct state_list_stack
**stack
)
485 sm_msg("smatch internal error: stack not empty");
486 free_stack_and_slists(stack
);
490 static void check_stree_stack_free(struct stree_stack
**stack
)
493 sm_msg("smatch internal error: stack not empty");
494 free_stack_and_strees(stack
);
498 void save_all_states(void)
500 __add_ptr_list(&backup
, stree_to_slist(cur_stree
), 0);
502 __add_ptr_list(&backup
, true_stack
, 0);
503 __add_ptr_list(&backup
, false_stack
, 0);
504 __add_ptr_list(&backup
, pre_cond_stack
, 0);
506 __add_ptr_list(&backup
, cond_true_stack
, 0);
507 __add_ptr_list(&backup
, cond_false_stack
, 0);
509 __add_ptr_list(&backup
, fake_cur_stree_stack
, 0);
511 __add_ptr_list(&backup
, break_stack
, 0);
512 __add_ptr_list(&backup
, switch_stack
, 0);
513 __add_ptr_list(&backup
, remaining_cases
, 0);
514 __add_ptr_list(&backup
, default_stack
, 0);
515 __add_ptr_list(&backup
, continue_stack
, 0);
517 __add_ptr_list(&backup
, goto_stack
, 0);
520 void nullify_all_states(void)
522 /* FIXME: These should call free_stree() */
527 pre_cond_stack
= NULL
;
529 cond_true_stack
= NULL
;
530 cond_false_stack
= NULL
;
532 fake_cur_stree_stack
= NULL
;
536 remaining_cases
= NULL
;
537 default_stack
= NULL
;
538 continue_stack
= NULL
;
543 static void *pop_backup(void)
547 ret
= last_ptr_list(backup
);
548 delete_ptr_list_last(&backup
);
552 void restore_all_states(void)
554 goto_stack
= pop_backup();
556 continue_stack
= pop_backup();
557 default_stack
= pop_backup();
558 remaining_cases
= pop_backup();
559 switch_stack
= pop_backup();
560 break_stack
= pop_backup();
562 fake_cur_stree_stack
= pop_backup();
564 cond_false_stack
= pop_backup();
565 cond_true_stack
= pop_backup();
567 pre_cond_stack
= pop_backup();
568 false_stack
= pop_backup();
569 true_stack
= pop_backup();
571 cur_stree
= slist_to_stree(pop_backup());
574 void clear_all_states(void)
576 struct named_stree
*named_stree
;
579 check_stree_stack_free(&true_stack
);
580 check_stree_stack_free(&false_stack
);
581 check_stack_free(&pre_cond_stack
);
582 check_stack_free(&cond_true_stack
);
583 check_stack_free(&cond_false_stack
);
584 check_stree_stack_free(&break_stack
);
585 check_stree_stack_free(&switch_stack
);
586 check_stree_stack_free(&continue_stack
);
587 free_stack_and_slists(&implied_pools
);
589 FOR_EACH_PTR(goto_stack
, named_stree
) {
590 free_stree(&named_stree
->stree
);
591 } END_FOR_EACH_PTR(named_stree
);
592 __free_ptr_list((struct ptr_list
**)&goto_stack
);
593 free_every_single_sm_state();
596 void __push_cond_stacks(void)
598 push_slist(&cond_true_stack
, NULL
);
599 push_slist(&cond_false_stack
, NULL
);
602 struct state_list
*__copy_cond_true_states(void)
604 struct state_list
*ret
;
606 ret
= pop_slist(&cond_true_stack
);
607 push_slist(&cond_true_stack
, clone_slist(ret
));
611 struct state_list
*__copy_cond_false_states(void)
613 struct state_list
*ret
;
615 ret
= pop_slist(&cond_false_stack
);
616 push_slist(&cond_false_stack
, clone_slist(ret
));
620 struct state_list
*__pop_cond_true_stack(void)
622 return pop_slist(&cond_true_stack
);
625 struct state_list
*__pop_cond_false_stack(void)
627 return pop_slist(&cond_false_stack
);
631 * This combines the pre cond states with either the true or false states.
633 * a = kmalloc() ; if (a !! foo(a)
634 * In the pre state a is possibly null. In the true state it is non null.
635 * In the false state it is null. Combine the pre and the false to get
636 * that when we call 'foo', 'a' is null.
638 static void __use_cond_stack(struct state_list_stack
**stack
)
640 struct state_list
*slist
;
642 free_stree(&cur_stree
);
644 cur_stree
= slist_to_stree(pop_slist(&pre_cond_stack
));
645 push_slist(&pre_cond_stack
, stree_to_slist(clone_stree(cur_stree
)));
647 slist
= pop_slist(stack
);
648 overwrite_stree(slist_to_stree(slist
), &cur_stree
);
649 push_slist(stack
, slist
);
652 void __use_pre_cond_states(void)
654 free_stree(&cur_stree
);
655 cur_stree
= slist_to_stree(pop_slist(&pre_cond_stack
));
658 void __use_cond_true_states(void)
660 __use_cond_stack(&cond_true_stack
);
663 void __use_cond_false_states(void)
665 __use_cond_stack(&cond_false_stack
);
668 void __negate_cond_stacks(void)
670 struct state_list
*old_false
, *old_true
;
672 __use_cond_stack(&cond_false_stack
);
673 old_false
= pop_slist(&cond_false_stack
);
674 old_true
= pop_slist(&cond_true_stack
);
675 push_slist(&cond_false_stack
, old_true
);
676 push_slist(&cond_true_stack
, old_false
);
679 void __and_cond_states(void)
681 and_slist_stack(&cond_true_stack
);
682 or_slist_stack(&pre_cond_stack
, stree_to_slist(cur_stree
), &cond_false_stack
);
685 void __or_cond_states(void)
687 or_slist_stack(&pre_cond_stack
, stree_to_slist(cur_stree
), &cond_true_stack
);
688 and_slist_stack(&cond_false_stack
);
691 void __save_pre_cond_states(void)
693 push_slist(&pre_cond_stack
, stree_to_slist(clone_stree(cur_stree
)));
696 void __discard_pre_cond_states(void)
698 struct state_list
*tmp
;
700 tmp
= pop_slist(&pre_cond_stack
);
704 void __use_cond_states(void)
706 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
708 pre
= pop_slist(&pre_cond_stack
);
709 pre_clone
= clone_slist(pre
);
711 true_states
= pop_slist(&cond_true_stack
);
712 overwrite_slist(true_states
, &pre
);
713 /* we use the true states right away */
714 free_stree(&cur_stree
);
715 cur_stree
= slist_to_stree(pre
);
717 false_states
= pop_slist(&cond_false_stack
);
718 overwrite_slist(false_states
, &pre_clone
);
719 push_stree(&false_stack
, slist_to_stree(pre_clone
));
722 void __push_true_states(void)
724 push_stree(&true_stack
, clone_stree(cur_stree
));
727 void __use_false_states(void)
729 free_stree(&cur_stree
);
730 cur_stree
= pop_stree(&false_stack
);
733 void __discard_false_states(void)
737 stree
= pop_stree(&false_stack
);
741 void __merge_false_states(void)
745 stree
= pop_stree(&false_stack
);
746 merge_stree(&cur_stree
, stree
);
750 void __merge_true_states(void)
754 stree
= pop_stree(&true_stack
);
755 merge_stree(&cur_stree
, stree
);
759 void __push_continues(void)
761 push_stree(&continue_stack
, NULL
);
764 void __discard_continues(void)
768 stree
= pop_stree(&continue_stack
);
772 void __process_continues(void)
776 stree
= pop_stree(&continue_stack
);
778 stree
= clone_stree(cur_stree
);
780 merge_stree(&stree
, cur_stree
);
782 push_stree(&continue_stack
, stree
);
785 static int top_stree_empty(struct stree_stack
**stack
)
790 tmp
= pop_stree(stack
);
793 push_stree(stack
, tmp
);
797 /* a silly loop does this: while(i--) { return; } */
798 void __warn_on_silly_pre_loops(void)
800 if (!__path_is_null())
802 if (!top_stree_empty(&continue_stack
))
804 if (!top_stree_empty(&break_stack
))
806 /* if the path was nullified before the loop, then we already
807 printed an error earlier */
808 if (top_stree_empty(&false_stack
))
810 sm_msg("info: loop could be replaced with if statement.");
813 void __merge_continues(void)
817 stree
= pop_stree(&continue_stack
);
818 merge_stree(&cur_stree
, stree
);
822 void __push_breaks(void)
824 push_stree(&break_stack
, NULL
);
827 void __process_breaks(void)
831 stree
= pop_stree(&break_stack
);
833 stree
= clone_stree(cur_stree
);
835 merge_stree(&stree
, cur_stree
);
837 push_stree(&break_stack
, stree
);
840 int __has_breaks(void)
845 stree
= pop_stree(&break_stack
);
847 push_stree(&break_stack
, stree
);
851 void __merge_breaks(void)
855 stree
= pop_stree(&break_stack
);
856 merge_stree(&cur_stree
, stree
);
860 void __use_breaks(void)
862 free_stree(&cur_stree
);
863 cur_stree
= pop_stree(&break_stack
);
866 void __save_switch_states(struct expression
*switch_expr
)
868 push_rl(&remaining_cases
, __get_implied_values(switch_expr
));
869 push_stree(&switch_stack
, clone_stree(cur_stree
));
872 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
875 struct state_list
*implied_slist
;
877 stree
= pop_stree(&switch_stack
);
878 implied_slist
= __implied_case_slist(switch_expr
, case_expr
, &remaining_cases
, &stree
);
879 merge_stree(&cur_stree
, slist_to_stree(implied_slist
));
880 free_slist(&implied_slist
);
881 push_stree(&switch_stack
, stree
);
884 void __discard_switches(void)
888 pop_rl(&remaining_cases
);
889 stree
= pop_stree(&switch_stack
);
893 void __push_default(void)
895 push_stree(&default_stack
, NULL
);
898 void __set_default(void)
900 set_state_stree_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
903 int __pop_default(void)
907 stree
= pop_stree(&default_stack
);
915 static struct named_stree
*alloc_named_stree(const char *name
, struct AVL
*stree
)
917 struct named_stree
*named_stree
= __alloc_named_stree(0);
919 named_stree
->name
= (char *)name
;
920 named_stree
->stree
= stree
;
924 void __save_gotos(const char *name
)
929 stree
= get_named_stree(goto_stack
, name
);
931 merge_stree(stree
, cur_stree
);
934 struct named_stree
*named_stree
;
936 clone
= clone_stree(cur_stree
);
937 named_stree
= alloc_named_stree(name
, clone
);
938 add_ptr_list(&goto_stack
, named_stree
);
942 void __merge_gotos(const char *name
)
946 stree
= get_named_stree(goto_stack
, name
);
948 merge_stree(&cur_stree
, *stree
);